net/cor/credits.c

   1 /*
   2  *      Connection oriented routing
   3  *      Copyright (C) 2007-2010 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 *conn, long jiffies_diff)
 144 {
 145         __u8 last_bufferstate = conn->last_bufferstate;
 146
 147         int shift_base;
 148
 149         if (conn->tos == TOS_NORMAL)
 150                 shift_base = 3;
 151         else if (conn->tos == TOS_LATENCY)
 152                 shift_base = 2;
 153         else if (conn->tos == TOS_THROUGHPUT)
 154                 shift_base = 5;
 155         else if (conn->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 there is no
 162          * bufferspace left
 163          */
 164
 165         BUG_ON(conn->crate_forward > (1 << 31));
 166
 167         for (;jiffies_diff < 0;jiffies_diff--) {
 168                 if (last_bufferstate == 0)
 169                         conn->crate_forward = ( ((__u64) conn->crate_forward) *
 170                                         (HZ << (shift_base - 2))) /
 171                                         (HZ << shift_base);
 172                 else
 173                         conn->crate_forward = ( ((__u64) conn->crate_forward) *
 174                                         (HZ << shift_base)) /
 175                                         (HZ << (shift_base - 1));
 176
 177                 if (conn->crate_forward > (1 << 31)) {
 178                         conn->crate_forward = (1 << 31);
 179                         break;
 180                 }
 181
 182                 if (conn->crate_forward < (1 << 16)) {
 183                         conn->crate_forward = (1 << 16);
 184                         break;
 185                 }
 186         }
 187
 188         conn->crate_out = multiply_div(conn->crate_in, conn->crate_forward,
 189                         1 << 31);
 190 }
 191
 192 static int decaytime_send_needed(struct conn *conn, __u16 *decaytime)
 193 {
 194         __u16 diff = 0;
 195
 196         if (conn->target.out.decaytime_send_allowed == 0)
 197                 return 0;
 198
 199         *decaytime = crate_to_decay_time(conn->target.out.nb, conn->crate_out);
 200
 201         if (unlikely(conn->target.out.conn_id == 0)) {
 202                 conn->reversedir->source.in.decaytime = *decaytime;
 203                 conn->target.out.decaytime_last = *decaytime;
 204                 conn->target.out.decaytime_send_allowed = 0;
 205                 return 0;
 206         }
 207
 208         if (*decaytime > conn->target.out.decaytime_last)
 209                 diff = *decaytime - conn->target.out.decaytime_last;
 210         if (*decaytime < conn->target.out.decaytime_last)
 211                 diff = conn->target.out.decaytime_last - *decaytime;
 212
 213         if (diff != 0 && (*decaytime == 0 ||
 214                         conn->target.out.decaytime_last == 0))
 215                 return 2;
 216
 217         if (conn->tos == TOS_PRIVACY) {
 218                 if (diff >= 5)
 219                         return 2;
 220                 if (diff >= 3)
 221                         return 1;
 222
 223         } else {
 224                 if (diff >= 2)
 225                         return 2;
 226                 if (diff >= 1)
 227                         return 1;
 228         }
 229
 230         return 0;
 231 }
 232
 233 static __u64 newnbrate(__u64 nbrate, __u64 oldconnrate, __u64 newconnrate)
 234 {
 235         if (unlikely(nbrate < oldconnrate))
 236                 nbrate = 0;
 237         else
 238                 nbrate -= oldconnrate;
 239
 240         if (unlikely(nbrate + newconnrate < nbrate))
 241                 nbrate = -1;
 242         else
 243                 nbrate += newconnrate;
 244
 245         return nbrate;
 246 }
 247
 248 static void refresh_conn_crate_out(struct conn *conn,
 249                 unsigned long jiffies_diff)
 250 {
 251         unsigned long iflags;
 252
 253         __u64 oldrate;
 254
 255         int send;
 256         __u16 crate;
 257
 258         if (likely(conn->target.out.conn_id != 0)) {
 259                 refresh_crate_forward(conn, jiffies_diff);
 260
 261                 if (((__s32) (conn->target.out.seqno_nextsend -
 262                                 conn->target.out.seqno_windowlimit )) <= 0)
 263                         conn->last_bufferstate = 1;
 264                 else
 265                         conn->last_bufferstate = 0;
 266         }
 267
 268         spin_lock_irqsave( &(conn->target.out.nb->credits_lock), iflags );
 269
 270         oldrate = conn->crate_out;
 271         refresh_credits_state(conn->target.out.nb);
 272         conn->target.out.nb->creditrate_spending = newnbrate(
 273                         conn->target.out.nb->creditrate_spending, oldrate,
 274                         conn->crate_out);
 275
 276         send = decaytime_send_needed(conn, &crate);
 277
 278         spin_unlock_irqrestore( &(conn->target.out.nb->credits_lock), iflags );
 279
 280         if (unlikely(send != 0)) {
 281                 send_decaytime(conn, (send == 2), crate);
 282                 return;
 283         }
 284 }
 285
 286 static void refresh_conn_crate_in(struct conn *conn)
 287 {
 288         unsigned long iflags;
 289
 290         __u64 oldrate = conn->crate_in;
 291
 292         spin_lock_irqsave( &(conn->source.in.nb->credits_lock), iflags );
 293
 294         refresh_credits_state(conn->source.in.nb);
 295
 296         conn->crate_in = decay_time_to_crate(conn->source.in.nb,
 297                         conn->source.in.decaytime);
 298         conn->source.in.nb->creditrate_earning = newnbrate(
 299                         conn->source.in.nb->creditrate_earning, oldrate,
 300                         conn->crate_in);
 301
 302         spin_unlock_irqrestore( &(conn->source.in.nb->credits_lock), iflags );
 303 }
 304
 305 static void refresh_conn_crates(struct conn *conn, unsigned long jiffies_diff)
 306 {
 307         /* set conn->crate_in */
 308         if (conn->sourcetype == SOURCE_NONE) {
 309                 conn->crate_in = conn->reversedir->crate_out;
 310         } else if (conn->sourcetype == SOURCE_IN) {
 311                 refresh_conn_crate_in(conn);
 312         } else if (conn->sourcetype == SOURCE_SOCK) {
 313                 if (conn->reversedir->target.sock.credituser == 1)
 314                         conn->crate_in = conn->reversedir->crate_out;
 315                 else if ((conn->source.sock.crate +
 316                                 conn->reversedir->crate_out) <
 317                                 conn->reversedir->crate_out)
 318                         conn->crate_in = -1;
 319                 else
 320                         conn->crate_in = conn->reversedir->crate_out +
 321                                         conn->source.sock.crate;
 322         } else {
 323                 BUG();
 324         }
 325
 326         /* set conn->crate_forward + conn->crate_out */
 327         if (conn->targettype == TARGET_UNCONNECTED) {
 328                 conn->crate_out = conn->crate_in;
 329         } else if (conn->targettype == TARGET_SOCK) {
 330                 if (conn->target.sock.credituser == 0) {
 331                         conn->crate_out = conn->crate_in;
 332                 } else {
 333                         refresh_crate_forward(conn, jiffies_diff);
 334                         conn->last_bufferstate = (
 335                                         conn->reversedir->source.sock.wait_len
 336                                 != 0);
 337                 }
 338         } else if (conn->targettype == TARGET_OUT) {
 339                 refresh_conn_crate_out(conn, jiffies_diff);
 340         } else {
 341                 BUG();
 342         }
 343 }
 344
 345 static void _refresh_conn_credits(struct conn *conn)
 346 {
 347         unsigned long jiffies_tmp = jiffies;
 348         unsigned long jiffies_diff = jiffies_tmp - conn->jiffies_credit_update;
 349
 350         if (jiffies_diff == 0)
 351                 goto crates;
 352
 353         #warning todo rates in in secs
 354
 355         if (unlikely(conn->crate_out > conn->crate_in)) {
 356                 __u64 diff = conn->crate_out - conn->crate_in;
 357                 if (unlikely((diff * jiffies_diff) / jiffies_diff != diff))
 358                         diff = -1;
 359                 else
 360                         diff *= jiffies_diff;
 361
 362                 if (unlikely(conn->credits - diff > conn->credits))
 363                         conn->credits = 0;
 364                 else
 365                         conn->credits -= diff;
 366         } else {
 367                 __u64 diff = conn->crate_in - conn->crate_out;
 368                 if (unlikely((diff * jiffies_diff) / jiffies_diff != diff))
 369                         diff = -1;
 370                 else
 371                         diff *= jiffies_diff;
 372
 373                 if (unlikely(conn->credits + diff < conn->credits))
 374                         conn->credits = -1;
 375                 else
 376                         conn->credits += diff;
 377         }
 378
 379 crates:
 380         refresh_conn_crates(conn, jiffies_tmp - conn->jiffies_credit_update);
 381
 382         conn->jiffies_credit_update = jiffies_tmp;
 383 }
 384
 385 /**
 386  * locked for access to credits + source.* + target.*
 387  * lock both sides, if either source or target is not out/in
 388  */
 389 static __u32 credits_lock_conn(struct conn *conn)
 390 {
 391         __u32 rc = 1;
 392
 393         mutex_lock(&(conn->rcv_lock));
 394         if (conn->sourcetype == SOURCE_SOCK &&
 395                         conn->targettype == TARGET_SOCK) {
 396
 397                 if (conn->source.sock.is_client == 1) {
 398                         mutex_lock(&(conn->reversedir->rcv_lock));
 399
 400                         BUG_ON(conn->reversedir->source.sock.is_client == 1);
 401
 402                         rc = 3;
 403                 } else {
 404                         mutex_unlock(&(conn->rcv_lock));
 405
 406                         mutex_lock(&(conn->reversedir->rcv_lock));
 407                         mutex_lock(&(conn->rcv_lock));
 408
 409                         BUG_ON(conn->reversedir->source.sock.is_client != 1);
 410
 411                         rc = 6;
 412                 }
 413         } else if (conn->targettype == TARGET_UNCONNECTED) {
 414                 mutex_lock(&(conn->reversedir->rcv_lock));
 415
 416                 rc = 3;
 417         } else if (conn->sourcetype == SOURCE_NONE ||
 418                         conn->sourcetype == SOURCE_SOCK) {
 419                 mutex_unlock(&(conn->rcv_lock));
 420
 421                 mutex_lock(&(conn->reversedir->rcv_lock));
 422                 mutex_lock(&(conn->rcv_lock));
 423
 424                 rc = 6;
 425         } else if (conn->targettype == TARGET_SOCK) {
 426                 mutex_lock(&(conn->reversedir->rcv_lock));
 427
 428                 rc = 3;
 429         } else if (conn->sourcetype == SOURCE_IN &&
 430                         conn->targettype == TARGET_OUT) {
 431                 if (unlikely(conn->target.out.conn_id == 0)) {
 432                         mutex_lock(&(conn->reversedir->rcv_lock));
 433                         rc = 3;
 434                 } else {
 435                         mutex_unlock(&(conn->rcv_lock));
 436
 437                         mutex_lock(&(conn->reversedir->rcv_lock));
 438
 439                         if (unlikely(conn->reversedir->target.out.conn_id==0)) {
 440                                 mutex_lock(&(conn->rcv_lock));
 441                                 rc = 6;
 442                         } else {
 443                                 mutex_unlock(&(conn->reversedir->rcv_lock));
 444                                 mutex_lock(&(conn->rcv_lock));
 445                         }
 446                 }
 447         }
 448         return rc;
 449 }
 450
 451 static void credits_unlock_conn(struct conn *conn, __u32 hints)
 452 {
 453         if ((hints & 1) != 0)
 454                 mutex_unlock(&(conn->rcv_lock));
 455         if ((hints & 2) != 0)
 456                 mutex_unlock(&(conn->reversedir->rcv_lock));
 457         if ((hints & 4) != 0)
 458                 mutex_unlock(&(conn->rcv_lock));
 459 }
 460
 461 int refresh_conn_credits(struct conn *conn, int fromperiodic, int locked)
 462 {
 463         unsigned long iflags;
 464         __u32 unlockhints = 0;
 465         int rc = 0;
 466         int put = 0;
 467
 468         if (likely(locked == 0))
 469                 unlockhints = credits_lock_conn(conn);
 470
 471         if (atomic_read(&(conn->isreset)) != 0) {
 472                 if (fromperiodic)
 473                         rc = 1;
 474                 goto out;
 475         }
 476
 477         if (fromperiodic) {
 478                 /* quit if not time for refresh yet */
 479                 unsigned long jiffies_tmp = jiffies;
 480                 if (time_after(conn->jiffies_credit_update +
 481                                 HZ*CREDIT_REFRESHINTERVAL_SEC, jiffies_tmp)) {
 482                         int alreadyrefreshed;
 483
 484                         spin_lock_irqsave(&credits_list_lock, iflags);
 485                         alreadyrefreshed = &(conn->credit_list) !=
 486                                         credit_refresh_conns.next;
 487                         spin_unlock_irqrestore(&credits_list_lock, iflags );
 488
 489                         if (unlikely(alreadyrefreshed))
 490                                 goto out;
 491
 492                         rc = conn->jiffies_credit_update - jiffies_tmp;
 493                         if (rc < HZ)
 494                                 rc = HZ;
 495                         if (rc > HZ * CREDIT_REFRESHINTERVAL_SEC)
 496                                 rc = HZ * CREDIT_REFRESHINTERVAL_SEC;
 497                         goto out;
 498                 }
 499         }
 500
 501         if (conn->targettype == TARGET_UNCONNECTED || (
 502                         conn->targettype == TARGET_SOCK &&
 503                         conn->target.sock.credituser == 0)) {
 504                 if (unlikely(conn->in_credit_list)) {
 505                         spin_lock_irqsave(&credits_list_lock, iflags);
 506                         list_del(&(conn->credit_list));
 507                         conn->in_credit_list = 0;
 508                         spin_unlock_irqrestore(&credits_list_lock, iflags );
 509                         put = 1;
 510                 }
 511
 512                 if (conn->sourcetype == SOURCE_NONE || (
 513                                 conn->sourcetype == SOURCE_SOCK &&
 514                                 conn->reversedir->target.sock.credituser == 0))
 515                         goto out;
 516
 517                 goto refresh;
 518         }
 519
 520         spin_lock_irqsave(&credits_list_lock, iflags);
 521
 522         if (unlikely(conn->in_credit_list == 0)) {
 523                 conn->in_credit_list = 1;
 524                 kref_get(&(conn->ref));
 525                 if (refresh_running == 0) {
 526                         schedule_delayed_work(&credit_refresh_work, HZ *
 527                                         CREDIT_REFRESHINTERVAL_SEC);
 528                         refresh_running = 1;
 529                 }
 530         } else {
 531                 list_del(&(conn->credit_list));
 532         }
 533         list_add_tail(&(conn->credit_list), &credit_refresh_conns);
 534
 535
 536         spin_unlock_irqrestore(&credits_list_lock, iflags );
 537
 538 refresh:
 539         if (conn->sourcetype == SOURCE_NONE || (
 540                         conn->sourcetype == SOURCE_SOCK &&
 541                         conn->reversedir->target.sock.credituser == 0))
 542                 _refresh_conn_credits(conn->reversedir);
 543         _refresh_conn_credits(conn);
 544         if (conn->targettype == TARGET_UNCONNECTED || (
 545                         conn->targettype == TARGET_OUT &&
 546                         conn->target.out.conn_id == 0) || (
 547                         conn->targettype == TARGET_SOCK &&
 548                         conn->target.sock.credituser == 0))
 549                 _refresh_conn_credits(conn->reversedir);
 550
 551 out:
 552         if (likely(locked == 0))
 553                 credits_unlock_conn(conn, unlockhints);
 554
 555         if (put)
 556                 kref_put(&(conn->ref), free_conn);
 557
 558         return rc;
 559 }
 560
 561 void connreset_credits(struct conn *conn)
 562 {
 563         unsigned long iflags;
 564
 565         __u32 unlockhints = credits_lock_conn(conn);
 566         if (conn->in_credit_list) {
 567                 spin_lock_irqsave(&credits_list_lock, iflags);
 568                 list_del(&(conn->credit_list));
 569                 conn->in_credit_list = 0;
 570                 spin_unlock_irqrestore(&credits_list_lock, iflags);
 571                 kref_put(&(conn->ref), free_conn);
 572         }
 573
 574         if (conn->sourcetype == SOURCE_IN) {
 575                 struct neighbor *nb = conn->source.in.nb;
 576                 spin_lock_irqsave( &(nb->credits_lock), iflags);
 577                 refresh_credits_state(nb);
 578                 nb->creditrate_earning = newnbrate(nb->creditrate_earning,
 579                                 conn->crate_in, 0);
 580                 spin_unlock_irqrestore( &(nb->credits_lock), iflags );
 581         }
 582
 583         if (conn->targettype == TARGET_OUT) {
 584                 struct neighbor *nb = conn->target.out.nb;
 585                 spin_lock_irqsave( &(nb->credits_lock), iflags);
 586                 refresh_credits_state(nb);
 587                 nb->creditrate_spending = newnbrate(nb->creditrate_spending,
 588                                 conn->crate_out, 0);
 589                 spin_unlock_irqrestore( &(nb->credits_lock), iflags );
 590         }
 591         credits_unlock_conn(conn, unlockhints);
 592 }
 593
 594 void set_conn_in_decaytime(struct conn *rconn, __u8 decaytime_seqno,
 595                 __u16 decaytime)
 596 {
 597         __u32 unlockhints = credits_lock_conn(rconn);
 598
 599         BUG_ON(rconn->sourcetype != SOURCE_IN);
 600
 601         if (unlikely(rconn->source.in.decaytime_seqno == 255)) {
 602                 rconn->source.in.decaytime_seqno = decaytime_seqno;
 603                 goto set;
 604         }
 605
 606         if (rconn->source.in.decaytime_seqno != decaytime_seqno)
 607                 goto out;
 608         rconn->source.in.decaytime_seqno = (rconn->source.in.decaytime_seqno +
 609                         1) % 64;
 610
 611 set:
 612         rconn->source.in.decaytime = decaytime;
 613         refresh_conn_credits(rconn, 0, 1);
 614
 615 out:
 616         credits_unlock_conn(rconn, unlockhints);
 617 }
 618
 619 static void background_refresh_credits(struct work_struct *work)
 620 {
 621         unsigned long iflags;
 622         struct conn *conn;
 623         int rc = 0;
 624
 625         while (rc == 0) {
 626                 spin_lock_irqsave(&credits_list_lock, iflags);
 627                 if (unlikely(list_empty(&(credit_refresh_conns)))) {
 628                         rc = -1;
 629                         refresh_running = 0;
 630                         conn = 0;
 631                 } else {
 632                         conn = container_of(credit_refresh_conns.next,
 633                                         struct conn, credit_list);
 634                 }
 635                 spin_unlock_irqrestore(&credits_list_lock, iflags);
 636
 637                 if (conn != 0)
 638                         rc = refresh_conn_credits(conn, 1, 0);
 639         }
 640
 641         if (likely(rc > 0)) {
 642                 schedule_delayed_work(&credit_refresh_work, rc);
 643         }
 644 }
 645
 646 void __init credits_init(void)
 647 {
 648         INIT_DELAYED_WORK(&credit_refresh_work, background_refresh_credits);
 649 }
 650
 651 MODULE_LICENSE("GPL");