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