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 static spinlock_t 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_conn_crates(struct conn *conn)
 230 {
 231         if (conn->sourcetype == SOURCE_NONE) {
 232                 conn->sender_crate = conn->reversedir->recp_crate;
 233         } else if (conn->sourcetype == SOURCE_IN) {
 234                 conn->sender_crate = credit_exchange_in(conn->source.in.nb,
 235                                 conn->source.in.crate_in_raw);
 236         } else if (conn->sourcetype == SOURCE_SOCK) {
 237                 BUG_ON(conn->reversedir->target.sock.credituser == 1 &&
 238                                 conn->targettype == TARGET_SOCK &&
 239                                 conn->reversedir->recp_crate != 0);
 240
 241
 242                 if ((conn->source.sock.crate + conn->reversedir->recp_crate) <
 243                                 conn->reversedir->recp_crate || (
 244                                 conn->reversedir->recp_crate +
 245                                 conn->source.sock.crate) > MAX_CREDITRATE_SOCK)
 246                         conn->sender_crate = MAX_CREDITRATE_SOCK;
 247                 else
 248                         conn->sender_crate = conn->reversedir->recp_crate +
 249                                         conn->source.sock.crate;
 250         } else {
 251                 BUG();
 252         }
 253
 254         if (conn->targettype == TARGET_UNCONNECTED) {
 255                 conn->recp_crate = conn->sender_crate;
 256                 conn->reversedir->sender_crate = conn->recp_crate;
 257         } else if ((conn->targettype == TARGET_SOCK &&
 258                         conn->target.sock.credituser == 0)) {
 259                 conn->recp_crate = conn->sender_crate;
 260                 conn->reversedir->sender_crate = conn->recp_crate +
 261                                 conn->reversedir->source.sock.crate;
 262         }
 263 }
 264
 265 static void _refresh_conn_credits(struct conn *conn)
 266 {
 267         long jiffies_tmp = jiffies;
 268
 269         __u32 scrate = conn->sender_crate;
 270         __u32 rcrate = conn->recp_crate;
 271
 272         __s64 diff;
 273
 274         refresh_conn_crates(conn);
 275
 276         refresh_conn_crates(conn);
 277
 278         /* 500 and not 1000 here: 1000 * (*_crate + *rate)/2 = 500 * ... */
 279         diff = 500 * ((__s64) conn->sender_crate + (__s64) scrate -
 280                         (__s64) conn->recp_crate - (__s64) rcrate) * (
 281                         jiffies_tmp - conn->jiffies_credit_update) +
 282                         conn->credits_fract;
 283
 284         conn->credits += diff / HZ;
 285         conn->credits_fract = diff % HZ;
 286
 287         conn->jiffies_credit_update = jiffies_tmp;
 288 }
 289
 290 /**
 291  * locked for access to credits + source.* + target.*
 292  * lock both sides, if either source or target is not out/in
 293  */
 294 static __u32 credits_lock_conn(struct conn *conn)
 295 {
 296         __u32 rc = 1;
 297         mutex_lock(&(conn->rcv_lock));
 298         if (conn->sourcetype != SOURCE_IN) {
 299                 mutex_unlock(&(conn->rcv_lock));
 300
 301                 mutex_lock(&(conn->reversedir->rcv_lock));
 302                 mutex_lock(&(conn->rcv_lock));
 303
 304                 rc = 6;
 305         } else if (conn->targettype != TARGET_OUT) {
 306                 mutex_lock(&(conn->reversedir->rcv_lock));
 307
 308                 rc = 3;
 309         }
 310         return rc;
 311 }
 312
 313 static void credits_unlock_conn(struct conn *conn, __u32 hints)
 314 {
 315         if ((hints & 1) != 0)
 316                 mutex_unlock(&(conn->rcv_lock));
 317         if ((hints & 2) != 0)
 318                 mutex_unlock(&(conn->reversedir->rcv_lock));
 319         if ((hints & 4) != 0)
 320                 mutex_unlock(&(conn->rcv_lock));
 321 }
 322
 323 void refresh_conn_credits(struct conn *conn)
 324 {
 325         unsigned long iflags;
 326         __u32 unlockhints = credits_lock_conn(conn);
 327
 328         if (unlikely(conn->targettype == TARGET_SOCK &&
 329                         conn->reversedir->targettype == TARGET_SOCK &&
 330                         conn->target.sock.credituser == 0 &&
 331                         conn->reversedir->target.sock.credituser == 0))
 332                 goto out;
 333         spin_lock_irqsave(&conn_credits_lock, iflags);
 334
 335         _refresh_conn_credits(conn);
 336         refresh_conn_crates(conn);
 337
 338         spin_unlock_irqrestore(&conn_credits_lock, iflags );
 339 out:
 340         credits_unlock_conn(conn, unlockhints);
 341 }
 342
 343 void set_conn_in_crate(struct conn *rconn, __u32 crate_in)
 344 {
 345         unsigned long iflags;
 346
 347         __u32 unlockhints = credits_lock_conn(rconn);
 348         spin_lock_irqsave(&conn_credits_lock, iflags);
 349
 350         BUG_ON(rconn->sourcetype != SOURCE_IN);
 351         _refresh_conn_credits(rconn);
 352         rconn->source.in.crate_in_raw = crate_in;
 353         refresh_conn_crates(rconn);
 354
 355         spin_unlock_irqrestore(&conn_credits_lock, iflags );
 356         credits_unlock_conn(rconn, unlockhints);
 357 }
 358
 359 int __init cor_credits_init(void)
 360 {
 361         spin_lock_init(&conn_credits_lock);
 362         return 0;
 363 }