?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Linux 3.12.28
[linux/fpc-iii.git] / net / sched / sch_fq.c
blob52229f91b1157d25bb885f4723d076c8c154f017
1 /*
2 * net/sched/sch_fq.c Fair Queue Packet Scheduler (per flow pacing)
3 *
4 * Copyright (C) 2013 Eric Dumazet <edumazet@google.com>
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
10 *
11 * Meant to be mostly used for localy generated traffic :
12 * Fast classification depends on skb->sk being set before reaching us.
13 * If not, (router workload), we use rxhash as fallback, with 32 bits wide hash.
14 * All packets belonging to a socket are considered as a 'flow'.
15 *
16 * Flows are dynamically allocated and stored in a hash table of RB trees
17 * They are also part of one Round Robin 'queues' (new or old flows)
18 *
19 * Burst avoidance (aka pacing) capability :
20 *
21 * Transport (eg TCP) can set in sk->sk_pacing_rate a rate, enqueue a
22 * bunch of packets, and this packet scheduler adds delay between
23 * packets to respect rate limitation.
24 *
25 * enqueue() :
26 * - lookup one RB tree (out of 1024 or more) to find the flow.
27 * If non existent flow, create it, add it to the tree.
28 * Add skb to the per flow list of skb (fifo).
29 * - Use a special fifo for high prio packets
30 *
31 * dequeue() : serves flows in Round Robin
32 * Note : When a flow becomes empty, we do not immediately remove it from
33 * rb trees, for performance reasons (its expected to send additional packets,
34 * or SLAB cache will reuse socket for another flow)
35 */
36
37 #include <linux/module.h>
38 #include <linux/types.h>
39 #include <linux/kernel.h>
40 #include <linux/jiffies.h>
41 #include <linux/string.h>
42 #include <linux/in.h>
43 #include <linux/errno.h>
44 #include <linux/init.h>
45 #include <linux/skbuff.h>
46 #include <linux/slab.h>
47 #include <linux/rbtree.h>
48 #include <linux/hash.h>
49 #include <linux/prefetch.h>
50 #include <net/netlink.h>
51 #include <net/pkt_sched.h>
52 #include <net/sock.h>
53 #include <net/tcp_states.h>
54
55 /*
56 * Per flow structure, dynamically allocated
57 */
58 struct fq_flow {
59 struct sk_buff *head; /* list of skbs for this flow : first skb */
60 union {
61 struct sk_buff *tail; /* last skb in the list */
62 unsigned long age; /* jiffies when flow was emptied, for gc */
63 };
64 struct rb_node fq_node; /* anchor in fq_root[] trees */
65 struct sock *sk;
66 int qlen; /* number of packets in flow queue */
67 int credit;
68 u32 socket_hash; /* sk_hash */
69 struct fq_flow *next; /* next pointer in RR lists, or &detached */
70
71 struct rb_node rate_node; /* anchor in q->delayed tree */
72 u64 time_next_packet;
73 };
74
75 struct fq_flow_head {
76 struct fq_flow *first;
77 struct fq_flow *last;
78 };
79
80 struct fq_sched_data {
81 struct fq_flow_head new_flows;
82
83 struct fq_flow_head old_flows;
84
85 struct rb_root delayed; /* for rate limited flows */
86 u64 time_next_delayed_flow;
87
88 struct fq_flow internal; /* for non classified or high prio packets */
89 u32 quantum;
90 u32 initial_quantum;
91 u32 flow_refill_delay;
92 u32 flow_max_rate; /* optional max rate per flow */
93 u32 flow_plimit; /* max packets per flow */
94 struct rb_root *fq_root;
95 u8 rate_enable;
96 u8 fq_trees_log;
97
98 u32 flows;
99 u32 inactive_flows;
100 u32 throttled_flows;
101
102 u64 stat_gc_flows;
103 u64 stat_internal_packets;
104 u64 stat_tcp_retrans;
105 u64 stat_throttled;
106 u64 stat_flows_plimit;
107 u64 stat_pkts_too_long;
108 u64 stat_allocation_errors;
109 struct qdisc_watchdog watchdog;
110 };
111
112 /* special value to mark a detached flow (not on old/new list) */
113 static struct fq_flow detached, throttled;
114
115 static void fq_flow_set_detached(struct fq_flow *f)
116 {
117 f->next = &detached;
118 f->age = jiffies;
119 }
120
121 static bool fq_flow_is_detached(const struct fq_flow *f)
122 {
123 return f->next == &detached;
124 }
125
126 static void fq_flow_set_throttled(struct fq_sched_data *q, struct fq_flow *f)
127 {
128 struct rb_node **p = &q->delayed.rb_node, *parent = NULL;
129
130 while (*p) {
131 struct fq_flow *aux;
132
133 parent = *p;
134 aux = container_of(parent, struct fq_flow, rate_node);
135 if (f->time_next_packet >= aux->time_next_packet)
136 p = &parent->rb_right;
137 else
138 p = &parent->rb_left;
139 }
140 rb_link_node(&f->rate_node, parent, p);
141 rb_insert_color(&f->rate_node, &q->delayed);
142 q->throttled_flows++;
143 q->stat_throttled++;
144
145 f->next = &throttled;
146 if (q->time_next_delayed_flow > f->time_next_packet)
147 q->time_next_delayed_flow = f->time_next_packet;
148 }
149
150
151 static struct kmem_cache *fq_flow_cachep __read_mostly;
152
153 static void fq_flow_add_tail(struct fq_flow_head *head, struct fq_flow *flow)
154 {
155 if (head->first)
156 head->last->next = flow;
157 else
158 head->first = flow;
159 head->last = flow;
160 flow->next = NULL;
161 }
162
163 /* limit number of collected flows per round */
164 #define FQ_GC_MAX 8
165 #define FQ_GC_AGE (3*HZ)
166
167 static bool fq_gc_candidate(const struct fq_flow *f)
168 {
169 return fq_flow_is_detached(f) &&
170 time_after(jiffies, f->age + FQ_GC_AGE);
171 }
172
173 static void fq_gc(struct fq_sched_data *q,
174 struct rb_root *root,
175 struct sock *sk)
176 {
177 struct fq_flow *f, *tofree[FQ_GC_MAX];
178 struct rb_node **p, *parent;
179 int fcnt = 0;
180
181 p = &root->rb_node;
182 parent = NULL;
183 while (*p) {
184 parent = *p;
185
186 f = container_of(parent, struct fq_flow, fq_node);
187 if (f->sk == sk)
188 break;
189
190 if (fq_gc_candidate(f)) {
191 tofree[fcnt++] = f;
192 if (fcnt == FQ_GC_MAX)
193 break;
194 }
195
196 if (f->sk > sk)
197 p = &parent->rb_right;
198 else
199 p = &parent->rb_left;
200 }
201
202 q->flows -= fcnt;
203 q->inactive_flows -= fcnt;
204 q->stat_gc_flows += fcnt;
205 while (fcnt) {
206 struct fq_flow *f = tofree[--fcnt];
207
208 rb_erase(&f->fq_node, root);
209 kmem_cache_free(fq_flow_cachep, f);
210 }
211 }
212
213 static struct fq_flow *fq_classify(struct sk_buff *skb, struct fq_sched_data *q)
214 {
215 struct rb_node **p, *parent;
216 struct sock *sk = skb->sk;
217 struct rb_root *root;
218 struct fq_flow *f;
219
220 /* warning: no starvation prevention... */
221 if (unlikely((skb->priority & TC_PRIO_MAX) == TC_PRIO_CONTROL))
222 return &q->internal;
223
224 if (unlikely(!sk)) {
225 /* By forcing low order bit to 1, we make sure to not
226 * collide with a local flow (socket pointers are word aligned)
227 */
228 sk = (struct sock *)(skb_get_rxhash(skb) | 1L);
229 }
230
231 root = &q->fq_root[hash_32((u32)(long)sk, q->fq_trees_log)];
232
233 if (q->flows >= (2U << q->fq_trees_log) &&
234 q->inactive_flows > q->flows/2)
235 fq_gc(q, root, sk);
236
237 p = &root->rb_node;
238 parent = NULL;
239 while (*p) {
240 parent = *p;
241
242 f = container_of(parent, struct fq_flow, fq_node);
243 if (f->sk == sk) {
244 /* socket might have been reallocated, so check
245 * if its sk_hash is the same.
246 * It not, we need to refill credit with
247 * initial quantum
248 */
249 if (unlikely(skb->sk &&
250 f->socket_hash != sk->sk_hash)) {
251 f->credit = q->initial_quantum;
252 f->socket_hash = sk->sk_hash;
253 }
254 return f;
255 }
256 if (f->sk > sk)
257 p = &parent->rb_right;
258 else
259 p = &parent->rb_left;
260 }
261
262 f = kmem_cache_zalloc(fq_flow_cachep, GFP_ATOMIC | __GFP_NOWARN);
263 if (unlikely(!f)) {
264 q->stat_allocation_errors++;
265 return &q->internal;
266 }
267 fq_flow_set_detached(f);
268 f->sk = sk;
269 if (skb->sk)
270 f->socket_hash = sk->sk_hash;
271 f->credit = q->initial_quantum;
272
273 rb_link_node(&f->fq_node, parent, p);
274 rb_insert_color(&f->fq_node, root);
275
276 q->flows++;
277 q->inactive_flows++;
278 return f;
279 }
280
281
282 /* remove one skb from head of flow queue */
283 static struct sk_buff *fq_dequeue_head(struct Qdisc *sch, struct fq_flow *flow)
284 {
285 struct sk_buff *skb = flow->head;
286
287 if (skb) {
288 flow->head = skb->next;
289 skb->next = NULL;
290 flow->qlen--;
291 sch->qstats.backlog -= qdisc_pkt_len(skb);
292 sch->q.qlen--;
293 }
294 return skb;
295 }
296
297 /* We might add in the future detection of retransmits
298 * For the time being, just return false
299 */
300 static bool skb_is_retransmit(struct sk_buff *skb)
301 {
302 return false;
303 }
304
305 /* add skb to flow queue
306 * flow queue is a linked list, kind of FIFO, except for TCP retransmits
307 * We special case tcp retransmits to be transmitted before other packets.
308 * We rely on fact that TCP retransmits are unlikely, so we do not waste
309 * a separate queue or a pointer.
310 * head-> [retrans pkt 1]
311 * [retrans pkt 2]
312 * [ normal pkt 1]
313 * [ normal pkt 2]
314 * [ normal pkt 3]
315 * tail-> [ normal pkt 4]
316 */
317 static void flow_queue_add(struct fq_flow *flow, struct sk_buff *skb)
318 {
319 struct sk_buff *prev, *head = flow->head;
320
321 skb->next = NULL;
322 if (!head) {
323 flow->head = skb;
324 flow->tail = skb;
325 return;
326 }
327 if (likely(!skb_is_retransmit(skb))) {
328 flow->tail->next = skb;
329 flow->tail = skb;
330 return;
331 }
332
333 /* This skb is a tcp retransmit,
334 * find the last retrans packet in the queue
335 */
336 prev = NULL;
337 while (skb_is_retransmit(head)) {
338 prev = head;
339 head = head->next;
340 if (!head)
341 break;
342 }
343 if (!prev) { /* no rtx packet in queue, become the new head */
344 skb->next = flow->head;
345 flow->head = skb;
346 } else {
347 if (prev == flow->tail)
348 flow->tail = skb;
349 else
350 skb->next = prev->next;
351 prev->next = skb;
352 }
353 }
354
355 static int fq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
356 {
357 struct fq_sched_data *q = qdisc_priv(sch);
358 struct fq_flow *f;
359
360 if (unlikely(sch->q.qlen >= sch->limit))
361 return qdisc_drop(skb, sch);
362
363 f = fq_classify(skb, q);
364 if (unlikely(f->qlen >= q->flow_plimit && f != &q->internal)) {
365 q->stat_flows_plimit++;
366 return qdisc_drop(skb, sch);
367 }
368
369 f->qlen++;
370 if (skb_is_retransmit(skb))
371 q->stat_tcp_retrans++;
372 sch->qstats.backlog += qdisc_pkt_len(skb);
373 if (fq_flow_is_detached(f)) {
374 fq_flow_add_tail(&q->new_flows, f);
375 if (time_after(jiffies, f->age + q->flow_refill_delay))
376 f->credit = max_t(u32, f->credit, q->quantum);
377 q->inactive_flows--;
378 qdisc_unthrottled(sch);
379 }
380
381 /* Note: this overwrites f->age */
382 flow_queue_add(f, skb);
383
384 if (unlikely(f == &q->internal)) {
385 q->stat_internal_packets++;
386 qdisc_unthrottled(sch);
387 }
388 sch->q.qlen++;
389
390 return NET_XMIT_SUCCESS;
391 }
392
393 static void fq_check_throttled(struct fq_sched_data *q, u64 now)
394 {
395 struct rb_node *p;
396
397 if (q->time_next_delayed_flow > now)
398 return;
399
400 q->time_next_delayed_flow = ~0ULL;
401 while ((p = rb_first(&q->delayed)) != NULL) {
402 struct fq_flow *f = container_of(p, struct fq_flow, rate_node);
403
404 if (f->time_next_packet > now) {
405 q->time_next_delayed_flow = f->time_next_packet;
406 break;
407 }
408 rb_erase(p, &q->delayed);
409 q->throttled_flows--;
410 fq_flow_add_tail(&q->old_flows, f);
411 }
412 }
413
414 static struct sk_buff *fq_dequeue(struct Qdisc *sch)
415 {
416 struct fq_sched_data *q = qdisc_priv(sch);
417 u64 now = ktime_to_ns(ktime_get());
418 struct fq_flow_head *head;
419 struct sk_buff *skb;
420 struct fq_flow *f;
421 u32 rate;
422
423 skb = fq_dequeue_head(sch, &q->internal);
424 if (skb)
425 goto out;
426 fq_check_throttled(q, now);
427 begin:
428 head = &q->new_flows;
429 if (!head->first) {
430 head = &q->old_flows;
431 if (!head->first) {
432 if (q->time_next_delayed_flow != ~0ULL)
433 qdisc_watchdog_schedule_ns(&q->watchdog,
434 q->time_next_delayed_flow);
435 return NULL;
436 }
437 }
438 f = head->first;
439
440 if (f->credit <= 0) {
441 f->credit += q->quantum;
442 head->first = f->next;
443 fq_flow_add_tail(&q->old_flows, f);
444 goto begin;
445 }
446
447 if (unlikely(f->head && now < f->time_next_packet)) {
448 head->first = f->next;
449 fq_flow_set_throttled(q, f);
450 goto begin;
451 }
452
453 skb = fq_dequeue_head(sch, f);
454 if (!skb) {
455 head->first = f->next;
456 /* force a pass through old_flows to prevent starvation */
457 if ((head == &q->new_flows) && q->old_flows.first) {
458 fq_flow_add_tail(&q->old_flows, f);
459 } else {
460 fq_flow_set_detached(f);
461 q->inactive_flows++;
462 }
463 goto begin;
464 }
465 prefetch(&skb->end);
466 f->time_next_packet = now;
467 f->credit -= qdisc_pkt_len(skb);
468
469 if (f->credit > 0 || !q->rate_enable)
470 goto out;
471
472 rate = q->flow_max_rate;
473 if (skb->sk && skb->sk->sk_state != TCP_TIME_WAIT)
474 rate = min(skb->sk->sk_pacing_rate, rate);
475
476 if (rate != ~0U) {
477 u32 plen = max(qdisc_pkt_len(skb), q->quantum);
478 u64 len = (u64)plen * NSEC_PER_SEC;
479
480 if (likely(rate))
481 do_div(len, rate);
482 /* Since socket rate can change later,
483 * clamp the delay to 125 ms.
484 * TODO: maybe segment the too big skb, as in commit
485 * e43ac79a4bc ("sch_tbf: segment too big GSO packets")
486 */
487 if (unlikely(len > 125 * NSEC_PER_MSEC)) {
488 len = 125 * NSEC_PER_MSEC;
489 q->stat_pkts_too_long++;
490 }
491
492 f->time_next_packet = now + len;
493 }
494 out:
495 qdisc_bstats_update(sch, skb);
496 qdisc_unthrottled(sch);
497 return skb;
498 }
499
500 static void fq_reset(struct Qdisc *sch)
501 {
502 struct fq_sched_data *q = qdisc_priv(sch);
503 struct rb_root *root;
504 struct sk_buff *skb;
505 struct rb_node *p;
506 struct fq_flow *f;
507 unsigned int idx;
508
509 while ((skb = fq_dequeue_head(sch, &q->internal)) != NULL)
510 kfree_skb(skb);
511
512 if (!q->fq_root)
513 return;
514
515 for (idx = 0; idx < (1U << q->fq_trees_log); idx++) {
516 root = &q->fq_root[idx];
517 while ((p = rb_first(root)) != NULL) {
518 f = container_of(p, struct fq_flow, fq_node);
519 rb_erase(p, root);
520
521 while ((skb = fq_dequeue_head(sch, f)) != NULL)
522 kfree_skb(skb);
523
524 kmem_cache_free(fq_flow_cachep, f);
525 }
526 }
527 q->new_flows.first = NULL;
528 q->old_flows.first = NULL;
529 q->delayed = RB_ROOT;
530 q->flows = 0;
531 q->inactive_flows = 0;
532 q->throttled_flows = 0;
533 }
534
535 static void fq_rehash(struct fq_sched_data *q,
536 struct rb_root *old_array, u32 old_log,
537 struct rb_root *new_array, u32 new_log)
538 {
539 struct rb_node *op, **np, *parent;
540 struct rb_root *oroot, *nroot;
541 struct fq_flow *of, *nf;
542 int fcnt = 0;
543 u32 idx;
544
545 for (idx = 0; idx < (1U << old_log); idx++) {
546 oroot = &old_array[idx];
547 while ((op = rb_first(oroot)) != NULL) {
548 rb_erase(op, oroot);
549 of = container_of(op, struct fq_flow, fq_node);
550 if (fq_gc_candidate(of)) {
551 fcnt++;
552 kmem_cache_free(fq_flow_cachep, of);
553 continue;
554 }
555 nroot = &new_array[hash_32((u32)(long)of->sk, new_log)];
556
557 np = &nroot->rb_node;
558 parent = NULL;
559 while (*np) {
560 parent = *np;
561
562 nf = container_of(parent, struct fq_flow, fq_node);
563 BUG_ON(nf->sk == of->sk);
564
565 if (nf->sk > of->sk)
566 np = &parent->rb_right;
567 else
568 np = &parent->rb_left;
569 }
570
571 rb_link_node(&of->fq_node, parent, np);
572 rb_insert_color(&of->fq_node, nroot);
573 }
574 }
575 q->flows -= fcnt;
576 q->inactive_flows -= fcnt;
577 q->stat_gc_flows += fcnt;
578 }
579
580 static int fq_resize(struct Qdisc *sch, u32 log)
581 {
582 struct fq_sched_data *q = qdisc_priv(sch);
583 struct rb_root *array;
584 void *old_fq_root;
585 u32 idx;
586
587 if (q->fq_root && log == q->fq_trees_log)
588 return 0;
589
590 array = kmalloc(sizeof(struct rb_root) << log, GFP_KERNEL);
591 if (!array)
592 return -ENOMEM;
593
594 for (idx = 0; idx < (1U << log); idx++)
595 array[idx] = RB_ROOT;
596
597 sch_tree_lock(sch);
598
599 old_fq_root = q->fq_root;
600 if (old_fq_root)
601 fq_rehash(q, old_fq_root, q->fq_trees_log, array, log);
602
603 q->fq_root = array;
604 q->fq_trees_log = log;
605
606 sch_tree_unlock(sch);
607
608 kfree(old_fq_root);
609
610 return 0;
611 }
612
613 static const struct nla_policy fq_policy[TCA_FQ_MAX + 1] = {
614 [TCA_FQ_PLIMIT] = { .type = NLA_U32 },
615 [TCA_FQ_FLOW_PLIMIT] = { .type = NLA_U32 },
616 [TCA_FQ_QUANTUM] = { .type = NLA_U32 },
617 [TCA_FQ_INITIAL_QUANTUM] = { .type = NLA_U32 },
618 [TCA_FQ_RATE_ENABLE] = { .type = NLA_U32 },
619 [TCA_FQ_FLOW_DEFAULT_RATE] = { .type = NLA_U32 },
620 [TCA_FQ_FLOW_MAX_RATE] = { .type = NLA_U32 },
621 [TCA_FQ_BUCKETS_LOG] = { .type = NLA_U32 },
622 [TCA_FQ_FLOW_REFILL_DELAY] = { .type = NLA_U32 },
623 };
624
625 static int fq_change(struct Qdisc *sch, struct nlattr *opt)
626 {
627 struct fq_sched_data *q = qdisc_priv(sch);
628 struct nlattr *tb[TCA_FQ_MAX + 1];
629 int err, drop_count = 0;
630 u32 fq_log;
631
632 if (!opt)
633 return -EINVAL;
634
635 err = nla_parse_nested(tb, TCA_FQ_MAX, opt, fq_policy);
636 if (err < 0)
637 return err;
638
639 sch_tree_lock(sch);
640
641 fq_log = q->fq_trees_log;
642
643 if (tb[TCA_FQ_BUCKETS_LOG]) {
644 u32 nval = nla_get_u32(tb[TCA_FQ_BUCKETS_LOG]);
645
646 if (nval >= 1 && nval <= ilog2(256*1024))
647 fq_log = nval;
648 else
649 err = -EINVAL;
650 }
651 if (tb[TCA_FQ_PLIMIT])
652 sch->limit = nla_get_u32(tb[TCA_FQ_PLIMIT]);
653
654 if (tb[TCA_FQ_FLOW_PLIMIT])
655 q->flow_plimit = nla_get_u32(tb[TCA_FQ_FLOW_PLIMIT]);
656
657 if (tb[TCA_FQ_QUANTUM])
658 q->quantum = nla_get_u32(tb[TCA_FQ_QUANTUM]);
659
660 if (tb[TCA_FQ_INITIAL_QUANTUM])
661 q->initial_quantum = nla_get_u32(tb[TCA_FQ_INITIAL_QUANTUM]);
662
663 if (tb[TCA_FQ_FLOW_DEFAULT_RATE])
664 pr_warn_ratelimited("sch_fq: defrate %u ignored.\n",
665 nla_get_u32(tb[TCA_FQ_FLOW_DEFAULT_RATE]));
666
667 if (tb[TCA_FQ_FLOW_MAX_RATE])
668 q->flow_max_rate = nla_get_u32(tb[TCA_FQ_FLOW_MAX_RATE]);
669
670 if (tb[TCA_FQ_RATE_ENABLE]) {
671 u32 enable = nla_get_u32(tb[TCA_FQ_RATE_ENABLE]);
672
673 if (enable <= 1)
674 q->rate_enable = enable;
675 else
676 err = -EINVAL;
677 }
678
679 if (tb[TCA_FQ_FLOW_REFILL_DELAY]) {
680 u32 usecs_delay = nla_get_u32(tb[TCA_FQ_FLOW_REFILL_DELAY]) ;
681
682 q->flow_refill_delay = usecs_to_jiffies(usecs_delay);
683 }
684
685 if (!err) {
686 sch_tree_unlock(sch);
687 err = fq_resize(sch, fq_log);
688 sch_tree_lock(sch);
689 }
690 while (sch->q.qlen > sch->limit) {
691 struct sk_buff *skb = fq_dequeue(sch);
692
693 if (!skb)
694 break;
695 kfree_skb(skb);
696 drop_count++;
697 }
698 qdisc_tree_decrease_qlen(sch, drop_count);
699
700 sch_tree_unlock(sch);
701 return err;
702 }
703
704 static void fq_destroy(struct Qdisc *sch)
705 {
706 struct fq_sched_data *q = qdisc_priv(sch);
707
708 fq_reset(sch);
709 kfree(q->fq_root);
710 qdisc_watchdog_cancel(&q->watchdog);
711 }
712
713 static int fq_init(struct Qdisc *sch, struct nlattr *opt)
714 {
715 struct fq_sched_data *q = qdisc_priv(sch);
716 int err;
717
718 sch->limit = 10000;
719 q->flow_plimit = 100;
720 q->quantum = 2 * psched_mtu(qdisc_dev(sch));
721 q->initial_quantum = 10 * psched_mtu(qdisc_dev(sch));
722 q->flow_refill_delay = msecs_to_jiffies(40);
723 q->flow_max_rate = ~0U;
724 q->rate_enable = 1;
725 q->new_flows.first = NULL;
726 q->old_flows.first = NULL;
727 q->delayed = RB_ROOT;
728 q->fq_root = NULL;
729 q->fq_trees_log = ilog2(1024);
730 qdisc_watchdog_init(&q->watchdog, sch);
731
732 if (opt)
733 err = fq_change(sch, opt);
734 else
735 err = fq_resize(sch, q->fq_trees_log);
736
737 return err;
738 }
739
740 static int fq_dump(struct Qdisc *sch, struct sk_buff *skb)
741 {
742 struct fq_sched_data *q = qdisc_priv(sch);
743 struct nlattr *opts;
744
745 opts = nla_nest_start(skb, TCA_OPTIONS);
746 if (opts == NULL)
747 goto nla_put_failure;
748
749 /* TCA_FQ_FLOW_DEFAULT_RATE is not used anymore */
750
751 if (nla_put_u32(skb, TCA_FQ_PLIMIT, sch->limit) ||
752 nla_put_u32(skb, TCA_FQ_FLOW_PLIMIT, q->flow_plimit) ||
753 nla_put_u32(skb, TCA_FQ_QUANTUM, q->quantum) ||
754 nla_put_u32(skb, TCA_FQ_INITIAL_QUANTUM, q->initial_quantum) ||
755 nla_put_u32(skb, TCA_FQ_RATE_ENABLE, q->rate_enable) ||
756 nla_put_u32(skb, TCA_FQ_FLOW_MAX_RATE, q->flow_max_rate) ||
757 nla_put_u32(skb, TCA_FQ_FLOW_REFILL_DELAY,
758 jiffies_to_usecs(q->flow_refill_delay)) ||
759 nla_put_u32(skb, TCA_FQ_BUCKETS_LOG, q->fq_trees_log))
760 goto nla_put_failure;
761
762 nla_nest_end(skb, opts);
763 return skb->len;
764
765 nla_put_failure:
766 return -1;
767 }
768
769 static int fq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
770 {
771 struct fq_sched_data *q = qdisc_priv(sch);
772 u64 now = ktime_to_ns(ktime_get());
773 struct tc_fq_qd_stats st = {
774 .gc_flows = q->stat_gc_flows,
775 .highprio_packets = q->stat_internal_packets,
776 .tcp_retrans = q->stat_tcp_retrans,
777 .throttled = q->stat_throttled,
778 .flows_plimit = q->stat_flows_plimit,
779 .pkts_too_long = q->stat_pkts_too_long,
780 .allocation_errors = q->stat_allocation_errors,
781 .flows = q->flows,
782 .inactive_flows = q->inactive_flows,
783 .throttled_flows = q->throttled_flows,
784 .time_next_delayed_flow = q->time_next_delayed_flow - now,
785 };
786
787 return gnet_stats_copy_app(d, &st, sizeof(st));
788 }
789
790 static struct Qdisc_ops fq_qdisc_ops __read_mostly = {
791 .id = "fq",
792 .priv_size = sizeof(struct fq_sched_data),
793
794 .enqueue = fq_enqueue,
795 .dequeue = fq_dequeue,
796 .peek = qdisc_peek_dequeued,
797 .init = fq_init,
798 .reset = fq_reset,
799 .destroy = fq_destroy,
800 .change = fq_change,
801 .dump = fq_dump,
802 .dump_stats = fq_dump_stats,
803 .owner = THIS_MODULE,
804 };
805
806 static int __init fq_module_init(void)
807 {
808 int ret;
809
810 fq_flow_cachep = kmem_cache_create("fq_flow_cache",
811 sizeof(struct fq_flow),
812 0, 0, NULL);
813 if (!fq_flow_cachep)
814 return -ENOMEM;
815
816 ret = register_qdisc(&fq_qdisc_ops);
817 if (ret)
818 kmem_cache_destroy(fq_flow_cachep);
819 return ret;
820 }
821
822 static void __exit fq_module_exit(void)
823 {
824 unregister_qdisc(&fq_qdisc_ops);
825 kmem_cache_destroy(fq_flow_cachep);
826 }
827
828 module_init(fq_module_init)
829 module_exit(fq_module_exit)
830 MODULE_AUTHOR("Eric Dumazet");
831 MODULE_LICENSE("GPL");
Linux with added FPC-III support