?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
discard data after unsuccessful connect_neigh, implement unknown addrtype errorcode...
[cor_2_6_31.git] / net / cor / credits.c
blob1e08bc499306a257071a0be18c0926f4046b4f79
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->targettype == TARGET_DISCARD) {
336 cn_lc->crate_out = cn_lc->crate_in;
337 } else if (cn_lc->targettype == TARGET_SOCK) {
338 if (cn_lc->target.sock.credituser == 0) {
339 cn_lc->crate_out = cn_lc->crate_in;
340 } else {
341 refresh_crate_forward(cn_lc, timediff_ns);
342 cn_lc->last_bufferstate = (
343 cn_lc->reversedir->source.sock.wait_len
344 != 0);
345 }
346 } else if (cn_lc->targettype == TARGET_OUT) {
347 refresh_conn_crate_out(cn_lc, now, timediff_ns);
348 } else {
349 BUG();
350 }
351 }
352
353 static void _refresh_conn_credits(struct conn *cn_lc, ktime_t now)
354 {
355 __u64 timediff_ns = ktime_to_ns(now) -
356 ktime_to_ns(cn_lc->ktime_credit_update);
357
358 if (ktime_before_eq(now, cn_lc->ktime_credit_update)) {
359 timediff_ns = 0;
360 goto crates;
361 }
362
363 if (unlikely(cn_lc->crate_out > cn_lc->crate_in)) {
364 __u64 rem;
365
366 __u64 adj = multiply_div2(cn_lc->crate_out - cn_lc->crate_in,
367 0 - cn_lc->credits_rem, timediff_ns,
368 1000000000, &rem);
369
370 BUG_ON(rem >= 1000000000);
371
372 if (unlikely(cn_lc->credits < adj)) {
373 cn_lc->credits = 0;
374 cn_lc->credits_rem = 0;
375 } else {
376 cn_lc->credits -= adj;
377 cn_lc->credits_rem = 0 - rem;
378 }
379 } else {
380 __u64 rem;
381
382 __u64 adj = multiply_div2(cn_lc->crate_in - cn_lc->crate_out,
383 cn_lc->credits_rem, timediff_ns,
384 1000000000, &rem);
385
386 BUG_ON(rem >= 1000000000);
387
388 if (unlikely(cn_lc->credits + adj < cn_lc->credits)) {
389 cn_lc->credits = -1;
390 cn_lc->credits_rem = 0;
391 } else {
392 cn_lc->credits += adj;
393 cn_lc->credits_rem = rem;
394 }
395 }
396
397 crates:
398 refresh_conn_crates(cn_lc, now, timediff_ns);
399
400 if (timediff_ns != 0)
401 cn_lc->ktime_credit_update = now;
402 }
403
404 static void credits_unlock_conn(struct conn *cn, __u32 hints)
405 {
406 if ((hints & 1) != 0)
407 mutex_unlock(&(cn->rcv_lock));
408 if ((hints & 2) != 0)
409 mutex_unlock(&(cn->reversedir->rcv_lock));
410 if ((hints & 4) != 0)
411 mutex_unlock(&(cn->rcv_lock));
412 }
413
414 static __u32 credits_lock_conn(struct conn *cn)
415 {
416 mutex_lock(&(cn->rcv_lock));
417 if (cn->sourcetype == SOURCE_IN && cn->targettype == TARGET_OUT) {
418 if (likely(cn->target.out.conn_id != 0))
419 return 1;
420 }
421
422 if (cn->is_client) {
423 mutex_lock(&(cn->reversedir->rcv_lock));
424 return 6;
425 } else {
426 mutex_unlock(&(cn->rcv_lock));
427
428 mutex_lock(&(cn->reversedir->rcv_lock));
429 mutex_lock(&(cn->rcv_lock));
430
431 return 3;
432 }
433 }
434
435 int refresh_conn_credits(struct conn *cn, int fromperiodic, int locked)
436 {
437 unsigned long iflags;
438 __u32 unlockhints = 0;
439 int rc = 0;
440 int put = 0;
441 ktime_t now;
442
443 if (likely(locked == 0))
444 unlockhints = credits_lock_conn(cn);
445
446 if (unlikely(cn->isreset != 0)) {
447 if (fromperiodic)
448 rc = 1;
449 goto out;
450 }
451
452 now = ktime_get();
453
454 if (fromperiodic) {
455 /* quit if not time for refresh yet */
456 if (ktime_after(ktime_add_us(cn->ktime_credit_update,
457 CREDIT_REFRESHINTERVAL_SEC * 1000000), now)) {
458 int alreadyrefreshed;
459
460 spin_lock_irqsave(&credits_list_lock, iflags);
461 alreadyrefreshed = &(cn->credit_list) !=
462 credit_refresh_conns.next;
463 spin_unlock_irqrestore(&credits_list_lock, iflags);
464
465 if (unlikely(alreadyrefreshed))
466 goto out;
467
468 rc = usecs_to_jiffies(ktime_us_delta(ktime_add_us(
469 cn->ktime_credit_update,
470 CREDIT_REFRESHINTERVAL_SEC * 1000000),
471 now)) + 1;
472 if (rc < HZ)
473 rc = HZ;
474 if (unlikely(rc > HZ * CREDIT_REFRESHINTERVAL_SEC))
475 rc = HZ * CREDIT_REFRESHINTERVAL_SEC;
476 goto out;
477 }
478 }
479
480 if (cn->targettype == TARGET_UNCONNECTED ||
481 cn->targettype == TARGET_DISCARD || (
482 cn->targettype == TARGET_SOCK &&
483 cn->target.sock.credituser == 0)) {
484 if (unlikely(cn->in_credit_list)) {
485 spin_lock_irqsave(&credits_list_lock, iflags);
486 list_del(&(cn->credit_list));
487 cn->in_credit_list = 0;
488 spin_unlock_irqrestore(&credits_list_lock, iflags);
489 put = 1;
490 }
491
492 if (cn->sourcetype == SOURCE_NONE || (
493 cn->sourcetype == SOURCE_SOCK &&
494 cn->reversedir->target.sock.credituser == 0))
495 goto out;
496
497 goto refresh;
498 }
499
500 spin_lock_irqsave(&credits_list_lock, iflags);
501
502 if (unlikely(cn->in_credit_list == 0)) {
503 cn->in_credit_list = 1;
504 kref_get(&(cn->ref));
505 if (refresh_running == 0) {
506 schedule_delayed_work(&credit_refresh_work, HZ *
507 CREDIT_REFRESHINTERVAL_SEC);
508 refresh_running = 1;
509 }
510 } else {
511 list_del(&(cn->credit_list));
512 }
513 list_add_tail(&(cn->credit_list), &credit_refresh_conns);
514
515
516 spin_unlock_irqrestore(&credits_list_lock, iflags);
517
518 refresh:
519 if (cn->sourcetype == SOURCE_NONE || (
520 cn->sourcetype == SOURCE_SOCK &&
521 cn->reversedir->target.sock.credituser == 0))
522 _refresh_conn_credits(cn->reversedir, now);
523 _refresh_conn_credits(cn, now);
524 if (cn->targettype == TARGET_UNCONNECTED ||
525 cn->targettype == TARGET_DISCARD || (
526 cn->targettype == TARGET_OUT &&
527 cn->target.out.conn_id == 0) || (
528 cn->targettype == TARGET_SOCK &&
529 cn->target.sock.credituser == 0))
530 _refresh_conn_credits(cn->reversedir, now);
531
532 out:
533 if (likely(locked == 0))
534 credits_unlock_conn(cn, unlockhints);
535
536 if (put)
537 kref_put(&(cn->ref), free_conn);
538
539 return rc;
540 }
541
542 void connreset_credits(struct conn *cn)
543 {
544 unsigned long iflags;
545
546 __u32 unlockhints = credits_lock_conn(cn);
547 if (cn->in_credit_list) {
548 spin_lock_irqsave(&credits_list_lock, iflags);
549 list_del(&(cn->credit_list));
550 cn->in_credit_list = 0;
551 spin_unlock_irqrestore(&credits_list_lock, iflags);
552 kref_put(&(cn->ref), free_conn);
553 }
554
555 if (cn->sourcetype == SOURCE_IN) {
556 struct neighbor *nb = cn->source.in.nb;
557 spin_lock_irqsave(&(nb->credits_lock), iflags);
558 refresh_credits_state(nb, ktime_get());
559 nb->creditrate_earning = newnbrate(nb->creditrate_earning,
560 cn->crate_in, 0);
561 spin_unlock_irqrestore(&(nb->credits_lock), iflags);
562 }
563
564 if (cn->targettype == TARGET_OUT) {
565 struct neighbor *nb = cn->target.out.nb;
566 spin_lock_irqsave(&(nb->credits_lock), iflags);
567 refresh_credits_state(nb, ktime_get());
568 nb->creditrate_spending = newnbrate(nb->creditrate_spending,
569 cn->crate_out, 0);
570 spin_unlock_irqrestore(&(nb->credits_lock), iflags);
571 }
572 credits_unlock_conn(cn, unlockhints);
573 }
574
575 void set_conn_in_decaytime(struct neighbor *nb, __u32 conn_id,
576 struct conn *src_in, __u8 decaytime_seqno, __u16 decaytime)
577 {
578 __u32 unlockhints = credits_lock_conn(src_in);
579
580 if (unlikely(is_conn_in(src_in, nb, conn_id) == 0))
581 goto out;
582
583 if (unlikely(src_in->source.in.decaytime_seqno == 255)) {
584 src_in->source.in.decaytime_seqno = decaytime_seqno;
585 goto set;
586 }
587
588 if (src_in->source.in.decaytime_seqno != decaytime_seqno)
589 goto out;
590 src_in->source.in.decaytime_seqno = (src_in->source.in.decaytime_seqno +
591 1) % 64;
592
593 set:
594 src_in->source.in.decaytime = decaytime;
595 refresh_conn_credits(src_in, 0, 1);
596
597 out:
598 credits_unlock_conn(src_in, unlockhints);
599 }
600
601 static void background_refresh_credits(struct work_struct *work)
602 {
603 unsigned long iflags;
604 struct conn *cn;
605 int rc = 0;
606
607 while (rc == 0) {
608 spin_lock_irqsave(&credits_list_lock, iflags);
609 if (unlikely(list_empty(&(credit_refresh_conns)))) {
610 rc = -1;
611 refresh_running = 0;
612 cn = 0;
613 } else {
614 cn = container_of(credit_refresh_conns.next,
615 struct conn, credit_list);
616 }
617 spin_unlock_irqrestore(&credits_list_lock, iflags);
618
619 if (cn != 0)
620 rc = refresh_conn_credits(cn, 1, 0);
621 }
622
623 if (likely(rc > 0)) {
624 schedule_delayed_work(&credit_refresh_work, rc);
625 }
626 }
627
628 void __init credits_init(void)
629 {
630 INIT_DELAYED_WORK(&credit_refresh_work, background_refresh_credits);
631 }
632
633 MODULE_LICENSE("GPL");
connection oriented routing - ARCHIVE NO UPDATES HERE