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(conn_credits_lock);
  24
  25 /* credit_lock must be held while calling this */
  26 int refresh_credits_state(struct neighbor *nb)
  27 {
  28         long jiffies_tmp = jiffies;
  29
  30         __s64 creditrate = 1000 * ((__s64)(nb->creditrate_initial +
  31                         nb->creditrate_earning - nb->creditrate_spending));
  32
  33         __s64 crediterrorrate = 1000 * ((__s64)(nb->creditrate_spending -
  34                         nb->creditrate_spending_expected)) -
  35                         /**
  36                          * tolerance is 50% of creditsrate_initial + 2.5% of
  37                          * both spending+earning
  38                          */
  39                         500 * ((__s64)(nb->creditrate_initial)) -
  40                         25 * ((__s64)(nb->creditrate_spending_expected)) -
  41                         25 * ((__s64)(nb->creditrate_earning));
  42
  43         __s64 debitrate = 1000 * ((__s64)(nb->debitrate_initial +
  44                         nb->debitrate_initial_adj + nb->debitrate_earning -
  45                         nb->debitrate_spending));
  46
  47
  48         __s64 credits_adj = (jiffies_tmp - nb->jiffies_credit_update) *
  49                         creditrate + nb->credits_fract;
  50
  51         __s64 creditsd_adj = (jiffies_tmp - nb->jiffies_credit_update) *
  52                         crediterrorrate + nb->credits_diff_fract;
  53
  54         __s64 debits_adj = (jiffies_tmp - nb->jiffies_credit_update) *
  55                         debitrate + nb->debits_fract;
  56
  57
  58         nb->jiffies_credit_update = jiffies_tmp;
  59
  60
  61         if (unlikely(credits_adj < 0 && (nb->credits < -(credits_adj/HZ)))) {
  62                 nb->credits = 0;
  63                 nb->credits_fract = 0;
  64         } else {
  65                 nb->credits += credits_adj / HZ;
  66                 nb->credits_fract = credits_adj % HZ;
  67         }
  68
  69         if (unlikely(creditsd_adj < 0 && (nb->credits_diff <
  70                         -(creditsd_adj/HZ)))) {
  71                 nb->credits_diff = 0;
  72                 nb->credits_diff_fract = 0;
  73         } else {
  74                 nb->credits_diff += creditsd_adj / HZ;
  75                 nb->credits_diff_fract = creditsd_adj % HZ;
  76         }
  77
  78         if (unlikely(debits_adj < 0 && (nb->debits < -(debits_adj/HZ)))) {
  79                 nb->debits = 0;
  80                 nb->debits_fract = 0;
  81
  82                 return 1;
  83         } else {
  84                 nb->debits += debits_adj / HZ;
  85                 nb->debits_fract = debits_adj % HZ;
  86         }
  87
  88         return 0;
  89 }
  90
  91 void check_credit_state(struct neighbor *nb)
  92 {
  93         unsigned long iflags;
  94         int resetconns;
  95         int sendcredits = 0;
  96         struct list_head *currlh;
  97
  98 start:
  99         spin_lock_irqsave( &(nb->credits_lock), iflags );
 100         refresh_credits_state(nb);
 101         resetconns = (nb->debits == 0 && ((
 102                         (__s64) nb->debitrate_initial_adj +
 103                         (__s64) nb->debitrate_earning -
 104                         (__s64) nb->debitrate_spending) < 0));
 105         spin_unlock_irqrestore( &(nb->credits_lock), iflags );
 106
 107         if (likely(resetconns == 0)) {
 108                 if (unlikely(sendcredits))
 109                         send_credits(nb);
 110                 return;
 111         } else {
 112                 sendcredits = 1;
 113         }
 114
 115         mutex_lock(&(nb->conn_list_lock));
 116         BUG_ON(list_empty(&(nb->snd_conn_list)) && nb->num_send_conns != 0);
 117         currlh = nb->snd_conn_list.next;
 118
 119         while (currlh != &(nb->snd_conn_list)) {
 120                 int ispaying;
 121                 struct conn *sconn = container_of(currlh, struct conn,
 122                                         target.out.nb_list);
 123                 struct conn *rconn = sconn->reversedir;
 124
 125                 mutex_lock(&(rconn->rcv_lock));
 126                 BUG_ON(sconn->targettype != TARGET_OUT);
 127                 BUG_ON(rconn->sourcetype != SOURCE_IN);
 128
 129                 spin_lock_irqsave(&conn_credits_lock, iflags);
 130                 if (rconn->targettype == TARGET_UNCONNECTED ||
 131                                 (rconn->targettype == TARGET_SOCK &&
 132                                 rconn->target.sock.credituser != 0))
 133                         ispaying = 1;
 134                 else
 135                         ispaying = (sconn->recp_crate > rconn->sender_crate);
 136                 spin_unlock_irqrestore(&conn_credits_lock, iflags );
 137
 138                 mutex_unlock(&(rconn->rcv_lock));
 139
 140                 if (ispaying) {
 141                         /**
 142                         * reset_conn must not be called with conn_list_lock
 143                         * held
 144                         */
 145                         mutex_unlock(&(nb->conn_list_lock));
 146                         reset_conn(rconn);
 147                         goto start;
 148                 }
 149                 currlh = currlh->next;
 150         }
 151
 152         BUG();
 153 }
 154
 155 int debit_adj_needed(struct neighbor *nb)
 156 {
 157         int rc = 0;
 158         unsigned long iflags;
 159         __s32 expected_adj;
 160         spin_lock_irqsave( &(nb->credits_lock), iflags );
 161
 162         refresh_credits_state(nb);
 163
 164         expected_adj = nb->creditrate_initial - nb->credits_diff/10000;
 165         if (unlikely((expected_adj < 0 || nb->debitrate_initial_adj < 0) &&
 166                         ( (expected_adj * 2 < nb->debitrate_initial_adj) ||
 167                         (expected_adj > nb->debitrate_initial_adj * 2) ))) {
 168                 nb->debitrate_initial_adj = (nb->debitrate_initial_adj * 15 +
 169                                 expected_adj) / 16;
 170                 rc = 1;
 171         }
 172
 173         spin_unlock_irqrestore( &(nb->credits_lock), iflags );
 174
 175         return rc;
 176 }
 177
 178 void set_credits(struct neighbor *nb, __u64 credits, __s32 creditrate_initial,
 179                 __u32 creditrate_earning, __u32 creditrate_spending)
 180 {
 181         unsigned long iflags;
 182
 183         spin_lock_irqsave( &(nb->credits_lock), iflags );
 184
 185         refresh_credits_state(nb);
 186
 187         if (nb->credits_diff + nb->credits < credits)
 188                 nb->credits_diff = 0;
 189         else
 190                 nb->credits_diff += nb->credits - credits;
 191         nb->credits = credits;
 192         nb->creditrate_initial = creditrate_initial;
 193         nb->creditrate_earning = creditrate_earning;
 194         nb->creditrate_spending = creditrate_spending;
 195
 196         spin_unlock_irqrestore( &(nb->credits_lock), iflags );
 197 }
 198
 199 void set_debitrate_initial(struct neighbor *nb, __u32 debitrate)
 200 {
 201         unsigned long iflags;
 202
 203         spin_lock_irqsave( &(nb->credits_lock), iflags );
 204
 205         refresh_credits_state(nb);
 206         nb->debitrate_initial = debitrate;
 207
 208         spin_unlock_irqrestore( &(nb->credits_lock), iflags );
 209
 210         send_credits(nb);
 211 }
 212
 213 static __u32 credit_exchange_in(struct neighbor *nb, __u32 crate_in_raw)
 214 {
 215         unsigned long iflags;
 216         __u64 ret;
 217         spin_lock_irqsave( &(nb->credits_lock), iflags );
 218         if (unlikely(nb->debits == 0))
 219                 ret = crate_in_raw;
 220         else
 221                 ret = multiply_div(nb->credits, crate_in_raw, nb->debits);
 222         spin_unlock_irqrestore( &(nb->credits_lock), iflags );
 223
 224         if ((ret >> 32) != 0)
 225                 return -1;
 226         return (__u32) ret;
 227 }
 228
 229 static void refresh_crate_forward(struct conn *conn, long jiffies_diff)
 230 {
 231         __u8 last_bufferstate = conn->last_bufferstate;
 232
 233         int shift_base;
 234
 235         if (conn->tos == TOS_NORMAL)
 236                 shift_base = 3;
 237         else if (conn->tos == TOS_LATENCY)
 238                 shift_base = 2;
 239         else if (conn->tos == TOS_THROUGHPUT)
 240                 shift_base = 5;
 241         else if (conn->tos == TOS_PRIVACY)
 242                 shift_base = 6;
 243         else
 244                 BUG();
 245
 246         /* buffer full shifts 1 bit more so that  */
 247
 248         BUG_ON(conn->crate_forward > (1 << 31));
 249
 250         for (;jiffies_diff < 0;jiffies_diff--) {
 251                 if (last_bufferstate == 0)
 252                         conn->crate_forward = ( ((__u64) conn->crate_forward) *
 253                                         (HZ << (shift_base - 2))) /
 254                                         (HZ << shift_base);
 255                 else
 256                         conn->crate_forward = ( ((__u64) conn->crate_forward) *
 257                                         (HZ << shift_base)) /
 258                                         (HZ << (shift_base - 1));
 259
 260                 if (conn->crate_forward > (1 << 31)) {
 261                         conn->crate_forward = (1 << 31);
 262                         break;
 263                 }
 264
 265                 if (conn->crate_forward < (1 << 16)) {
 266                         conn->crate_forward = (1 << 16);
 267                         break;
 268                 }
 269         }
 270 }
 271
 272 static int get_crate_forward_grace_period(struct conn *conn)
 273 {
 274         if (conn->tos == TOS_NORMAL)
 275                 return HZ * 2;
 276         if (conn->tos == TOS_LATENCY)
 277                 return HZ;
 278         if (conn->tos == TOS_THROUGHPUT)
 279                 return HZ * 5;
 280         if (conn->tos == TOS_PRIVACY)
 281                 return HZ * 10;
 282
 283         BUG();
 284 }
 285
 286 static void refresh_conn_crates(struct conn *conn, long jiffies_diff)
 287 {
 288         if (conn->sourcetype == SOURCE_NONE) {
 289                 conn->sender_crate = conn->reversedir->recp_crate;
 290         } else if (conn->sourcetype == SOURCE_IN) {
 291                 conn->sender_crate = credit_exchange_in(conn->source.in.nb,
 292                                 conn->source.in.crate_in_raw);
 293         } else if (conn->sourcetype == SOURCE_SOCK) {
 294                 BUG_ON(conn->reversedir->target.sock.credituser == 0 &&
 295                                 conn->targettype == TARGET_SOCK &&
 296                                 conn->reversedir->recp_crate != 0);
 297
 298                 #warning todo ???
 299                 if ((conn->source.sock.crate + conn->reversedir->recp_crate) <
 300                                 conn->reversedir->recp_crate || (
 301                                 conn->reversedir->recp_crate +
 302                                 conn->source.sock.crate) > MAX_CREDITRATE_SOCK)
 303                         conn->sender_crate = MAX_CREDITRATE_SOCK;
 304                 else
 305                         conn->sender_crate = conn->reversedir->recp_crate +
 306                                         conn->source.sock.crate;
 307         } else {
 308                 BUG();
 309         }
 310
 311         if (conn->targettype == TARGET_UNCONNECTED) {
 312                 conn->recp_crate = conn->sender_crate;
 313                 conn->reversedir->sender_crate = conn->recp_crate;
 314         } else if (conn->targettype == TARGET_SOCK) {
 315                 if (conn->target.sock.credituser == 0) {
 316                         conn->recp_crate = conn->sender_crate;
 317                 } else {
 318                         refresh_crate_forward(conn, jiffies_diff);
 319                         conn->recp_crate = (((__u64) conn->sender_crate) *
 320                                         conn->crate_forward) / (1 << 31);
 321                 }
 322                 conn->reversedir->sender_crate = conn->recp_crate +
 323                                         conn->reversedir->source.sock.crate;
 324                 if ((conn->reversedir->source.sock.crate + conn->recp_crate) <
 325                                 conn->recp_crate || (conn->recp_crate +
 326                                 conn->reversedir->source.sock.crate) >
 327                                 MAX_CREDITRATE_SOCK)
 328                         conn->reversedir->sender_crate = MAX_CREDITRATE_SOCK;
 329                 #warning todo last bufferstate
 330                 conn->last_bufferstate = 0;
 331         } else if (conn->targettype == TARGET_OUT) {
 332                 int grace = get_crate_forward_grace_period(conn);
 333                 if (conn->target.out.jiffies_crate_send + grace >
 334                                 conn->jiffies_credit_update) {
 335                         jiffies_diff += conn->jiffies_credit_update;
 336                         jiffies_diff -= conn->target.out.jiffies_crate_send;
 337                         jiffies_diff -= grace;
 338
 339                         if (jiffies_diff < 0)
 340                                 jiffies_diff = 0;
 341                 }
 342                 refresh_crate_forward(conn, jiffies_diff);
 343                 if (((__s32) (conn->target.out.seqno_nextsend -
 344                                 conn->target.out.seqno_windowlimit )) <= 0)
 345                         conn->last_bufferstate = 1;
 346                 else
 347                         conn->last_bufferstate = 0;
 348                 #warning todo send credits
 349         } else {
 350                 BUG();
 351         }
 352 }
 353
 354 static void _refresh_conn_credits(struct conn *conn, long jiffies_diff)
 355 {
 356         __s64 diff = 1000 * ((__s64) conn->sender_crate -
 357                         (__s64) conn->recp_crate) * jiffies_diff +
 358                         conn->credits_fract;
 359
 360         conn->credits += diff / HZ;
 361         conn->credits_fract = diff % HZ;
 362 }
 363
 364 /**
 365  * locked for access to credits + source.* + target.*
 366  * lock both sides, if either source or target is not out/in
 367  */
 368 static __u32 credits_lock_conn(struct conn *conn)
 369 {
 370         __u32 rc = 1;
 371         mutex_lock(&(conn->rcv_lock));
 372         if (conn->sourcetype != SOURCE_IN) {
 373                 mutex_unlock(&(conn->rcv_lock));
 374
 375                 mutex_lock(&(conn->reversedir->rcv_lock));
 376                 mutex_lock(&(conn->rcv_lock));
 377
 378                 rc = 6;
 379         } else if (conn->targettype != TARGET_OUT) {
 380                 mutex_lock(&(conn->reversedir->rcv_lock));
 381
 382                 rc = 3;
 383         }
 384         return rc;
 385 }
 386
 387 static void credits_unlock_conn(struct conn *conn, __u32 hints)
 388 {
 389         if ((hints & 1) != 0)
 390                 mutex_unlock(&(conn->rcv_lock));
 391         if ((hints & 2) != 0)
 392                 mutex_unlock(&(conn->reversedir->rcv_lock));
 393         if ((hints & 4) != 0)
 394                 mutex_unlock(&(conn->rcv_lock));
 395 }
 396
 397 #warning todo call periodically
 398 void refresh_conn_credits(struct conn *conn)
 399 {
 400         unsigned long iflags;
 401         long jiffies_tmp;
 402         __u32 unlockhints = credits_lock_conn(conn);
 403
 404         if (unlikely(conn->targettype == TARGET_SOCK &&
 405                         conn->reversedir->targettype == TARGET_SOCK &&
 406                         conn->target.sock.credituser == 0 &&
 407                         conn->reversedir->target.sock.credituser == 0))
 408                 goto out;
 409         spin_lock_irqsave(&conn_credits_lock, iflags);
 410
 411         jiffies_tmp = jiffies;
 412         _refresh_conn_credits(conn, jiffies_tmp - conn->jiffies_credit_update);
 413         refresh_conn_crates(conn, jiffies_tmp - conn->jiffies_credit_update);
 414         conn->jiffies_credit_update = jiffies_tmp;
 415
 416         spin_unlock_irqrestore(&conn_credits_lock, iflags );
 417 out:
 418         credits_unlock_conn(conn, unlockhints);
 419 }
 420
 421 void set_conn_in_crate(struct conn *rconn, __u32 crate_in)
 422 {
 423         unsigned long iflags;
 424         long jiffies_tmp;
 425
 426         __u32 unlockhints = credits_lock_conn(rconn);
 427         spin_lock_irqsave(&conn_credits_lock, iflags);
 428
 429         BUG_ON(rconn->sourcetype != SOURCE_IN);
 430
 431         jiffies_tmp = jiffies;
 432         _refresh_conn_credits(rconn, jiffies_tmp-rconn->jiffies_credit_update);
 433         rconn->source.in.crate_in_raw = crate_in;
 434         refresh_conn_crates(rconn, jiffies_tmp - rconn->jiffies_credit_update);
 435         rconn->jiffies_credit_update = jiffies_tmp;
 436
 437         spin_unlock_irqrestore(&conn_credits_lock, iflags );
 438         credits_unlock_conn(rconn, unlockhints);
 439 }
 440
 441 MODULE_LICENSE("GPL");