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