net/cor/credits.c

   1 /**
   2  *      Connection oriented routing
   3  *      Copyright (C) 2007-2011 Michael Blizek
   4  *
   5  *      This program is free software; you can redistribute it and/or
   6  *      modify it under the terms of the GNU General Public License
   7  *      as published by the Free Software Foundation; either version 2
   8  *      of the License, or (at your option) any later version.
   9  *
  10  *      This program is distributed in the hope that it will be useful,
  11  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *      GNU General Public License for more details.
  14  *
  15  *      You should have received a copy of the GNU General Public License
  16  *      along with this program; if not, write to the Free Software
  17  *      Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  18  *      02110-1301, USA.
  19  */
  20
  21 #include "cor.h"
  22
  23 DEFINE_SPINLOCK(credits_list_lock);
  24 LIST_HEAD(credit_refresh_conns);
  25 static struct delayed_work credit_refresh_work;
  26 static int refresh_running = 0;
  27
  28 static inline __s64 mul_saturated_signed(__s64 a, __u64 b)
  29 {
  30         __s64 res = a*b;
  31         if (unlikely(res / a != b)) {
  32                 if (a < 0)
  33                         return S64_MIN;
  34                 else
  35                         return S64_MAX;
  36         }
  37         return res;
  38 }
  39
  40 static __u64 decay_credits(__u64 credits)
  41 {
  42         int decay_rate = (CREDIT_DECAYTIME_HOURS * 3) / 2;
  43         if (unlikely(decay_rate == 0))
  44                 return 0;
  45         return credits - credits/decay_rate;
  46 }
  47
  48 __u32 creditrate_initial(void)
  49 {
  50         __u64 rate = (CREDITS_TOTAL - decay_credits(CREDITS_TOTAL)) / 3600;
  51         if (unlikely((rate >> 32) > 0))
  52                 return -1;
  53         return rate;
  54 }
  55
  56 /* credit_lock must be held while calling this */
  57 static void refresh_credits_state(struct neighbor *nb)
  58 {
  59         unsigned long jiffies_tmp = jiffies;
  60
  61         __s64 creditrate;
  62         __s64 credits_adj;
  63
  64         if (jiffies_tmp == nb->jiffies_credit_update)
  65                 return;
  66
  67         if (unlikely(nb->creditrate_earning >= (1LL << 63)))
  68                 creditrate = S64_MAX;
  69         else
  70                 creditrate = nb->creditrate_earning;
  71
  72         if (unlikely(creditrate - nb->creditrate_spending > creditrate))
  73                 creditrate = S64_MIN;
  74         else
  75                 creditrate -= nb->creditrate_spending;
  76
  77         if (unlikely(creditrate + nb->creditrate_initial < creditrate))
  78                 creditrate = S64_MAX;
  79         else
  80                 creditrate += nb->creditrate_initial;
  81
  82         credits_adj = mul_saturated_signed(creditrate, jiffies_tmp -
  83                         nb->jiffies_credit_update);
  84
  85         if (unlikely(credits_adj + nb->credits_fract < credits_adj)) {
  86                 credits_adj = S64_MAX;
  87         } else {
  88                 credits_adj += nb->credits_fract;
  89         }
  90
  91         if (unlikely((credits_adj < 0 && (nb->credits < -(credits_adj/HZ))) ||
  92                         credits_adj == S64_MIN)) {
  93                 nb->credits = 0;
  94                 nb->credits_fract = 0;
  95         } else if (unlikely(credits_adj > 0 && (nb->credits + credits_adj/HZ) <
  96                         nb->credits)) {
  97                 nb->credits = -1;
  98                 nb->credits_fract = 0;
  99         } else {
 100                 nb->credits += credits_adj / HZ;
 101                 nb->credits_fract = credits_adj % HZ;
 102         }
 103
 104         nb->jiffies_credit_update = jiffies_tmp;
 105
 106         if (unlikely(time_after(nb->jiffies_credit_decay + 3600*HZ,
 107                         jiffies_tmp))) {
 108                 nb->credits = decay_credits(nb->credits);
 109
 110                 nb->jiffies_credit_decay += 3600*HZ;
 111                 if (unlikely(time_after(nb->jiffies_credit_decay + 3600*HZ,
 112                                 jiffies_tmp)))
 113                         nb->jiffies_credit_decay = jiffies_tmp - 3600*HZ;
 114         }
 115 }
 116
 117 void set_creditrate_initial(struct neighbor *nb, __u32 creditrate)
 118 {
 119         unsigned long iflags;
 120
 121         spin_lock_irqsave(&(nb->credits_lock), iflags);
 122         refresh_credits_state(nb);
 123         nb->creditrate_initial = creditrate;
 124         spin_unlock_irqrestore(&(nb->credits_lock), iflags);
 125 }
 126
 127 static __u64 decay_time_to_crate(struct neighbor *nb, __u16 decay_time_raw)
 128 {
 129         __u64 decay_time = dec_log_300_24(decay_time_raw);
 130         if (decay_time == 0)
 131                 return 0;
 132         return nb->credits / (decay_time * 3 / 2);
 133 }
 134
 135 #warning todo exchange tax
 136 static __u16 crate_to_decay_time(struct neighbor *nb, __u64 crate_out)
 137 {
 138         if (crate_out <= 2)
 139                 return enc_log_300_24(0);
 140         return enc_log_300_24(nb->credits / (crate_out / 3 * 2));
 141 }
 142
 143 static void refresh_crate_forward(struct conn *cn_lc, long jiffies_diff)
 144 {
 145         __u8 last_bufferstate = cn_lc->last_bufferstate;
 146
 147         int shift_base;
 148
 149         if (cn_lc->tos == TOS_NORMAL)
 150                 shift_base = 3;
 151         else if (cn_lc->tos == TOS_LATENCY)
 152                 shift_base = 2;
 153         else if (cn_lc->tos == TOS_THROUGHPUT)
 154                 shift_base = 5;
 155         else if (cn_lc->tos == TOS_PRIVACY)
 156                 shift_base = 6;
 157         else
 158                 BUG();
 159
 160         /**
 161          * buffer full shifts 1 bit more so only about 1/3rd if there is no
 162          * bufferspace left
 163          */
 164
 165         BUG_ON(cn_lc->crate_forward > (1 << 31));
 166
 167         for (;jiffies_diff < 0;jiffies_diff--) {
 168                 if (last_bufferstate == 0)
 169                         cn_lc->crate_forward = ( ((__u64) cn_lc->crate_forward) *
 170                                         (HZ << (shift_base - 2))) /
 171                                         (HZ << shift_base);
 172                 else
 173                         cn_lc->crate_forward = ( ((__u64) cn_lc->crate_forward) *
 174                                         (HZ << shift_base)) /
 175                                         (HZ << (shift_base - 1));
 176
 177                 if (cn_lc->crate_forward > (1 << 31)) {
 178                         cn_lc->crate_forward = (1 << 31);
 179                         break;
 180                 }
 181
 182                 if (cn_lc->crate_forward < (1 << 16)) {
 183                         cn_lc->crate_forward = (1 << 16);
 184                         break;
 185                 }
 186         }
 187
 188         cn_lc->crate_out = multiply_div(cn_lc->crate_in, cn_lc->crate_forward,
 189                         1 << 31);
 190 }
 191
 192 static int decaytime_send_needed(struct conn *trgt_out_lc, __u16 *decaytime)
 193 {
 194         __u16 diff = 0;
 195
 196         if (trgt_out_lc->target.out.decaytime_send_allowed == 0)
 197                 return 0;
 198
 199         *decaytime = crate_to_decay_time(trgt_out_lc->target.out.nb,
 200                         trgt_out_lc->crate_out);
 201
 202         if (unlikely(trgt_out_lc->target.out.conn_id == 0)) {
 203                 trgt_out_lc->reversedir->source.in.decaytime = *decaytime;
 204                 trgt_out_lc->target.out.decaytime_last = *decaytime;
 205                 trgt_out_lc->target.out.decaytime_send_allowed = 0;
 206                 return 0;
 207         }
 208
 209         if (*decaytime > trgt_out_lc->target.out.decaytime_last)
 210                 diff = *decaytime - trgt_out_lc->target.out.decaytime_last;
 211         if (*decaytime < trgt_out_lc->target.out.decaytime_last)
 212                 diff = trgt_out_lc->target.out.decaytime_last - *decaytime;
 213
 214         if (diff != 0 && (*decaytime == 0 ||
 215                         trgt_out_lc->target.out.decaytime_last == 0))
 216                 return 2;
 217
 218         if (trgt_out_lc->tos == TOS_PRIVACY) {
 219                 if (diff >= 5)
 220                         return 2;
 221                 if (diff >= 3)
 222                         return 1;
 223
 224         } else {
 225                 if (diff >= 2)
 226                         return 2;
 227                 if (diff >= 1)
 228                         return 1;
 229         }
 230
 231         return 0;
 232 }
 233
 234 static __u64 newnbrate(__u64 nbrate, __u64 oldconnrate, __u64 newconnrate)
 235 {
 236         if (unlikely(nbrate < oldconnrate))
 237                 nbrate = 0;
 238         else
 239                 nbrate -= oldconnrate;
 240
 241         if (unlikely(nbrate + newconnrate < nbrate))
 242                 nbrate = -1;
 243         else
 244                 nbrate += newconnrate;
 245
 246         return nbrate;
 247 }
 248
 249 static void refresh_conn_crate_out(struct conn *trgt_out_lc,
 250                 unsigned long jiffies_diff)
 251 {
 252         unsigned long iflags;
 253
 254         __u64 oldrate;
 255
 256         int send;
 257         __u16 crate;
 258
 259         if (likely(trgt_out_lc->target.out.conn_id != 0)) {
 260                 refresh_crate_forward(trgt_out_lc, jiffies_diff);
 261
 262                 if (((__s32) (trgt_out_lc->target.out.seqno_nextsend -
 263                                 trgt_out_lc->target.out.seqno_windowlimit)) <=0)
 264                         trgt_out_lc->last_bufferstate = 1;
 265                 else
 266                         trgt_out_lc->last_bufferstate = 0;
 267         }
 268
 269         spin_lock_irqsave(&(trgt_out_lc->target.out.nb->credits_lock), iflags);
 270
 271         oldrate = trgt_out_lc->crate_out;
 272         refresh_credits_state(trgt_out_lc->target.out.nb);
 273         trgt_out_lc->target.out.nb->creditrate_spending = newnbrate(
 274                         trgt_out_lc->target.out.nb->creditrate_spending,
 275                         oldrate, trgt_out_lc->crate_out);
 276
 277         send = decaytime_send_needed(trgt_out_lc, &crate);
 278
 279         spin_unlock_irqrestore(&(trgt_out_lc->target.out.nb->credits_lock),
 280                         iflags);
 281
 282         if (unlikely(send != 0)) {
 283                 send_decaytime(trgt_out_lc, (send == 2), crate);
 284                 return;
 285         }
 286 }
 287
 288 static void refresh_conn_crate_in(struct conn *src_in_lc)
 289 {
 290         unsigned long iflags;
 291
 292         __u64 oldrate = src_in_lc->crate_in;
 293
 294         spin_lock_irqsave(&(src_in_lc->source.in.nb->credits_lock), iflags);
 295
 296         refresh_credits_state(src_in_lc->source.in.nb);
 297
 298         src_in_lc->crate_in = decay_time_to_crate(src_in_lc->source.in.nb,
 299                         src_in_lc->source.in.decaytime);
 300         src_in_lc->source.in.nb->creditrate_earning = newnbrate(
 301                         src_in_lc->source.in.nb->creditrate_earning, oldrate,
 302                         src_in_lc->crate_in);
 303
 304         spin_unlock_irqrestore(&(src_in_lc->source.in.nb->credits_lock),
 305                         iflags);
 306 }
 307
 308 static void refresh_conn_crates(struct conn *cn_lc, unsigned long jiffies_diff)
 309 {
 310         /* set conn->crate_in */
 311         if (cn_lc->sourcetype == SOURCE_NONE) {
 312                 cn_lc->crate_in = cn_lc->reversedir->crate_out;
 313         } else if (cn_lc->sourcetype == SOURCE_IN) {
 314                 refresh_conn_crate_in(cn_lc);
 315         } else if (cn_lc->sourcetype == SOURCE_SOCK) {
 316                 if (cn_lc->reversedir->target.sock.credituser == 1)
 317                         cn_lc->crate_in = cn_lc->reversedir->crate_out;
 318                 else if ((cn_lc->source.sock.crate +
 319                                 cn_lc->reversedir->crate_out) <
 320                                 cn_lc->reversedir->crate_out)
 321                         cn_lc->crate_in = -1;
 322                 else
 323                         cn_lc->crate_in = cn_lc->reversedir->crate_out +
 324                                         cn_lc->source.sock.crate;
 325         } else {
 326                 BUG();
 327         }
 328
 329         /* set conn->crate_forward + conn->crate_out */
 330         if (cn_lc->targettype == TARGET_UNCONNECTED) {
 331                 cn_lc->crate_out = cn_lc->crate_in;
 332         } else if (cn_lc->targettype == TARGET_SOCK) {
 333                 if (cn_lc->target.sock.credituser == 0) {
 334                         cn_lc->crate_out = cn_lc->crate_in;
 335                 } else {
 336                         refresh_crate_forward(cn_lc, jiffies_diff);
 337                         cn_lc->last_bufferstate = (
 338                                         cn_lc->reversedir->source.sock.wait_len
 339                                 != 0);
 340                 }
 341         } else if (cn_lc->targettype == TARGET_OUT) {
 342                 refresh_conn_crate_out(cn_lc, jiffies_diff);
 343         } else {
 344                 BUG();
 345         }
 346 }
 347
 348 static void _refresh_conn_credits(struct conn *cn_lc)
 349 {
 350         unsigned long jiffies_tmp = jiffies;
 351         unsigned long jiffies_diff = jiffies_tmp - cn_lc->jiffies_credit_update;
 352
 353         if (jiffies_diff == 0)
 354                 goto crates;
 355
 356         #warning todo rates in in secs
 357
 358         if (unlikely(cn_lc->crate_out > cn_lc->crate_in)) {
 359                 __u64 diff = cn_lc->crate_out - cn_lc->crate_in;
 360                 if (unlikely((diff * jiffies_diff) / jiffies_diff != diff))
 361                         diff = -1;
 362                 else
 363                         diff *= jiffies_diff;
 364
 365                 if (unlikely(cn_lc->credits - diff > cn_lc->credits))
 366                         cn_lc->credits = 0;
 367                 else
 368                         cn_lc->credits -= diff;
 369         } else {
 370                 __u64 diff = cn_lc->crate_in - cn_lc->crate_out;
 371                 if (unlikely((diff * jiffies_diff) / jiffies_diff != diff))
 372                         diff = -1;
 373                 else
 374                         diff *= jiffies_diff;
 375
 376                 if (unlikely(cn_lc->credits + diff < cn_lc->credits))
 377                         cn_lc->credits = -1;
 378                 else
 379                         cn_lc->credits += diff;
 380         }
 381
 382 crates:
 383         refresh_conn_crates(cn_lc, jiffies_tmp - cn_lc->jiffies_credit_update);
 384
 385         cn_lc->jiffies_credit_update = jiffies_tmp;
 386 }
 387
 388 static void credits_unlock_conn(struct conn *cn, __u32 hints)
 389 {
 390         if ((hints & 1) != 0)
 391                 mutex_unlock(&(cn->rcv_lock));
 392         if ((hints & 2) != 0)
 393                 mutex_unlock(&(cn->reversedir->rcv_lock));
 394         if ((hints & 4) != 0)
 395                 mutex_unlock(&(cn->rcv_lock));
 396 }
 397
 398 static __u32 credits_lock_conn(struct conn *cn)
 399 {
 400         mutex_lock(&(cn->rcv_lock));
 401         if (cn->sourcetype == SOURCE_IN && cn->targettype == TARGET_OUT) {
 402                 if (likely(cn->target.out.conn_id != 0))
 403                         return 1;
 404         }
 405
 406         if (cn->is_client) {
 407                 mutex_lock(&(cn->reversedir->rcv_lock));
 408                 return 6;
 409         } else {
 410                 mutex_unlock(&(cn->rcv_lock));
 411
 412                 mutex_lock(&(cn->reversedir->rcv_lock));
 413                 mutex_lock(&(cn->rcv_lock));
 414
 415                 return 3;
 416         }
 417 }
 418
 419 int refresh_conn_credits(struct conn *cn, int fromperiodic, int locked)
 420 {
 421         unsigned long iflags;
 422         __u32 unlockhints = 0;
 423         int rc = 0;
 424         int put = 0;
 425
 426         if (likely(locked == 0))
 427                 unlockhints = credits_lock_conn(cn);
 428
 429         if (atomic_read(&(cn->isreset)) != 0) {
 430                 if (fromperiodic)
 431                         rc = 1;
 432                 goto out;
 433         }
 434
 435         if (fromperiodic) {
 436                 /* quit if not time for refresh yet */
 437                 unsigned long jiffies_tmp = jiffies;
 438                 if (time_after(cn->jiffies_credit_update +
 439                                 HZ*CREDIT_REFRESHINTERVAL_SEC, jiffies_tmp)) {
 440                         int alreadyrefreshed;
 441
 442                         spin_lock_irqsave(&credits_list_lock, iflags);
 443                         alreadyrefreshed = &(cn->credit_list) !=
 444                                         credit_refresh_conns.next;
 445                         spin_unlock_irqrestore(&credits_list_lock, iflags);
 446
 447                         if (unlikely(alreadyrefreshed))
 448                                 goto out;
 449
 450                         rc = cn->jiffies_credit_update - jiffies_tmp;
 451                         if (rc < HZ)
 452                                 rc = HZ;
 453                         if (rc > HZ * CREDIT_REFRESHINTERVAL_SEC)
 454                                 rc = HZ * CREDIT_REFRESHINTERVAL_SEC;
 455                         goto out;
 456                 }
 457         }
 458
 459         if (cn->targettype == TARGET_UNCONNECTED || (
 460                         cn->targettype == TARGET_SOCK &&
 461                         cn->target.sock.credituser == 0)) {
 462                 if (unlikely(cn->in_credit_list)) {
 463                         spin_lock_irqsave(&credits_list_lock, iflags);
 464                         list_del(&(cn->credit_list));
 465                         cn->in_credit_list = 0;
 466                         spin_unlock_irqrestore(&credits_list_lock, iflags);
 467                         put = 1;
 468                 }
 469
 470                 if (cn->sourcetype == SOURCE_NONE || (
 471                                 cn->sourcetype == SOURCE_SOCK &&
 472                                 cn->reversedir->target.sock.credituser == 0))
 473                         goto out;
 474
 475                 goto refresh;
 476         }
 477
 478         spin_lock_irqsave(&credits_list_lock, iflags);
 479
 480         if (unlikely(cn->in_credit_list == 0)) {
 481                 cn->in_credit_list = 1;
 482                 kref_get(&(cn->ref));
 483                 if (refresh_running == 0) {
 484                         schedule_delayed_work(&credit_refresh_work, HZ *
 485                                         CREDIT_REFRESHINTERVAL_SEC);
 486                         refresh_running = 1;
 487                 }
 488         } else {
 489                 list_del(&(cn->credit_list));
 490         }
 491         list_add_tail(&(cn->credit_list), &credit_refresh_conns);
 492
 493
 494         spin_unlock_irqrestore(&credits_list_lock, iflags);
 495
 496 refresh:
 497         if (cn->sourcetype == SOURCE_NONE || (
 498                         cn->sourcetype == SOURCE_SOCK &&
 499                         cn->reversedir->target.sock.credituser == 0))
 500                 _refresh_conn_credits(cn->reversedir);
 501         _refresh_conn_credits(cn);
 502         if (cn->targettype == TARGET_UNCONNECTED || (
 503                         cn->targettype == TARGET_OUT &&
 504                         cn->target.out.conn_id == 0) || (
 505                         cn->targettype == TARGET_SOCK &&
 506                         cn->target.sock.credituser == 0))
 507                 _refresh_conn_credits(cn->reversedir);
 508
 509 out:
 510         if (likely(locked == 0))
 511                 credits_unlock_conn(cn, unlockhints);
 512
 513         if (put)
 514                 kref_put(&(cn->ref), free_conn);
 515
 516         return rc;
 517 }
 518
 519 void connreset_credits(struct conn *cn)
 520 {
 521         unsigned long iflags;
 522
 523         __u32 unlockhints = credits_lock_conn(cn);
 524         if (cn->in_credit_list) {
 525                 spin_lock_irqsave(&credits_list_lock, iflags);
 526                 list_del(&(cn->credit_list));
 527                 cn->in_credit_list = 0;
 528                 spin_unlock_irqrestore(&credits_list_lock, iflags);
 529                 kref_put(&(cn->ref), free_conn);
 530         }
 531
 532         if (cn->sourcetype == SOURCE_IN) {
 533                 struct neighbor *nb = cn->source.in.nb;
 534                 spin_lock_irqsave(&(nb->credits_lock), iflags);
 535                 refresh_credits_state(nb);
 536                 nb->creditrate_earning = newnbrate(nb->creditrate_earning,
 537                                 cn->crate_in, 0);
 538                 spin_unlock_irqrestore(&(nb->credits_lock), iflags);
 539         }
 540
 541         if (cn->targettype == TARGET_OUT) {
 542                 struct neighbor *nb = cn->target.out.nb;
 543                 spin_lock_irqsave(&(nb->credits_lock), iflags);
 544                 refresh_credits_state(nb);
 545                 nb->creditrate_spending = newnbrate(nb->creditrate_spending,
 546                                 cn->crate_out, 0);
 547                 spin_unlock_irqrestore(&(nb->credits_lock), iflags);
 548         }
 549         credits_unlock_conn(cn, unlockhints);
 550 }
 551
 552 void set_conn_in_decaytime(struct neighbor *nb, __u32 conn_id,
 553                 struct conn *src_in, __u8 decaytime_seqno, __u16 decaytime)
 554 {
 555         __u32 unlockhints = credits_lock_conn(src_in);
 556
 557         if (unlikely(is_conn_in(src_in, nb, conn_id) == 0))
 558                 goto out;
 559
 560         if (unlikely(src_in->source.in.decaytime_seqno == 255)) {
 561                 src_in->source.in.decaytime_seqno = decaytime_seqno;
 562                 goto set;
 563         }
 564
 565         if (src_in->source.in.decaytime_seqno != decaytime_seqno)
 566                 goto out;
 567         src_in->source.in.decaytime_seqno = (src_in->source.in.decaytime_seqno +
 568                         1) % 64;
 569
 570 set:
 571         src_in->source.in.decaytime = decaytime;
 572         refresh_conn_credits(src_in, 0, 1);
 573
 574 out:
 575         credits_unlock_conn(src_in, unlockhints);
 576 }
 577
 578 static void background_refresh_credits(struct work_struct *work)
 579 {
 580         unsigned long iflags;
 581         struct conn *cn;
 582         int rc = 0;
 583
 584         while (rc == 0) {
 585                 spin_lock_irqsave(&credits_list_lock, iflags);
 586                 if (unlikely(list_empty(&(credit_refresh_conns)))) {
 587                         rc = -1;
 588                         refresh_running = 0;
 589                         cn = 0;
 590                 } else {
 591                         cn = container_of(credit_refresh_conns.next,
 592                                         struct conn, credit_list);
 593                 }
 594                 spin_unlock_irqrestore(&credits_list_lock, iflags);
 595
 596                 if (cn != 0)
 597                         rc = refresh_conn_credits(cn, 1, 0);
 598         }
 599
 600         if (likely(rc > 0)) {
 601                 schedule_delayed_work(&credit_refresh_work, rc);
 602         }
 603 }
 604
 605 void __init credits_init(void)
 606 {
 607         INIT_DELAYED_WORK(&credit_refresh_work, background_refresh_credits);
 608 }
 609
 610 MODULE_LICENSE("GPL");