Loading...
1/*
2 * net/sched/sch_htb.c Hierarchical token bucket, feed tree version
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version
7 * 2 of the License, or (at your option) any later version.
8 *
9 * Authors: Martin Devera, <devik@cdi.cz>
10 *
11 * Credits (in time order) for older HTB versions:
12 * Stef Coene <stef.coene@docum.org>
13 * HTB support at LARTC mailing list
14 * Ondrej Kraus, <krauso@barr.cz>
15 * found missing INIT_QDISC(htb)
16 * Vladimir Smelhaus, Aamer Akhter, Bert Hubert
17 * helped a lot to locate nasty class stall bug
18 * Andi Kleen, Jamal Hadi, Bert Hubert
19 * code review and helpful comments on shaping
20 * Tomasz Wrona, <tw@eter.tym.pl>
21 * created test case so that I was able to fix nasty bug
22 * Wilfried Weissmann
23 * spotted bug in dequeue code and helped with fix
24 * Jiri Fojtasek
25 * fixed requeue routine
26 * and many others. thanks.
27 */
28#include <linux/module.h>
29#include <linux/moduleparam.h>
30#include <linux/types.h>
31#include <linux/kernel.h>
32#include <linux/string.h>
33#include <linux/errno.h>
34#include <linux/skbuff.h>
35#include <linux/list.h>
36#include <linux/compiler.h>
37#include <linux/rbtree.h>
38#include <linux/workqueue.h>
39#include <linux/slab.h>
40#include <net/netlink.h>
41#include <net/pkt_sched.h>
42
43/* HTB algorithm.
44 Author: devik@cdi.cz
45 ========================================================================
46 HTB is like TBF with multiple classes. It is also similar to CBQ because
47 it allows to assign priority to each class in hierarchy.
48 In fact it is another implementation of Floyd's formal sharing.
49
50 Levels:
51 Each class is assigned level. Leaf has ALWAYS level 0 and root
52 classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
53 one less than their parent.
54*/
55
56static int htb_hysteresis __read_mostly = 0; /* whether to use mode hysteresis for speedup */
57#define HTB_VER 0x30011 /* major must be matched with number suplied by TC as version */
58
59#if HTB_VER >> 16 != TC_HTB_PROTOVER
60#error "Mismatched sch_htb.c and pkt_sch.h"
61#endif
62
63/* Module parameter and sysfs export */
64module_param (htb_hysteresis, int, 0640);
65MODULE_PARM_DESC(htb_hysteresis, "Hysteresis mode, less CPU load, less accurate");
66
67/* used internaly to keep status of single class */
68enum htb_cmode {
69 HTB_CANT_SEND, /* class can't send and can't borrow */
70 HTB_MAY_BORROW, /* class can't send but may borrow */
71 HTB_CAN_SEND /* class can send */
72};
73
74/* interior & leaf nodes; props specific to leaves are marked L: */
75struct htb_class {
76 struct Qdisc_class_common common;
77 /* general class parameters */
78 struct gnet_stats_basic_packed bstats;
79 struct gnet_stats_queue qstats;
80 struct gnet_stats_rate_est rate_est;
81 struct tc_htb_xstats xstats; /* our special stats */
82 int refcnt; /* usage count of this class */
83
84 /* topology */
85 int level; /* our level (see above) */
86 unsigned int children;
87 struct htb_class *parent; /* parent class */
88
89 int prio; /* these two are used only by leaves... */
90 int quantum; /* but stored for parent-to-leaf return */
91
92 union {
93 struct htb_class_leaf {
94 struct Qdisc *q;
95 int deficit[TC_HTB_MAXDEPTH];
96 struct list_head drop_list;
97 } leaf;
98 struct htb_class_inner {
99 struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */
100 struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class ptr */
101 /* When class changes from state 1->2 and disconnects from
102 * parent's feed then we lost ptr value and start from the
103 * first child again. Here we store classid of the
104 * last valid ptr (used when ptr is NULL).
105 */
106 u32 last_ptr_id[TC_HTB_NUMPRIO];
107 } inner;
108 } un;
109 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
110 struct rb_node pq_node; /* node for event queue */
111 psched_time_t pq_key;
112
113 int prio_activity; /* for which prios are we active */
114 enum htb_cmode cmode; /* current mode of the class */
115
116 /* class attached filters */
117 struct tcf_proto *filter_list;
118 int filter_cnt;
119
120 /* token bucket parameters */
121 struct qdisc_rate_table *rate; /* rate table of the class itself */
122 struct qdisc_rate_table *ceil; /* ceiling rate (limits borrows too) */
123 long buffer, cbuffer; /* token bucket depth/rate */
124 psched_tdiff_t mbuffer; /* max wait time */
125 long tokens, ctokens; /* current number of tokens */
126 psched_time_t t_c; /* checkpoint time */
127};
128
129struct htb_sched {
130 struct Qdisc_class_hash clhash;
131 struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
132
133 /* self list - roots of self generating tree */
134 struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
135 int row_mask[TC_HTB_MAXDEPTH];
136 struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
137 u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
138
139 /* self wait list - roots of wait PQs per row */
140 struct rb_root wait_pq[TC_HTB_MAXDEPTH];
141
142 /* time of nearest event per level (row) */
143 psched_time_t near_ev_cache[TC_HTB_MAXDEPTH];
144
145 int defcls; /* class where unclassified flows go to */
146
147 /* filters for qdisc itself */
148 struct tcf_proto *filter_list;
149
150 int rate2quantum; /* quant = rate / rate2quantum */
151 psched_time_t now; /* cached dequeue time */
152 struct qdisc_watchdog watchdog;
153
154 /* non shaped skbs; let them go directly thru */
155 struct sk_buff_head direct_queue;
156 int direct_qlen; /* max qlen of above */
157
158 long direct_pkts;
159
160#define HTB_WARN_TOOMANYEVENTS 0x1
161 unsigned int warned; /* only one warning */
162 struct work_struct work;
163};
164
165/* find class in global hash table using given handle */
166static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
167{
168 struct htb_sched *q = qdisc_priv(sch);
169 struct Qdisc_class_common *clc;
170
171 clc = qdisc_class_find(&q->clhash, handle);
172 if (clc == NULL)
173 return NULL;
174 return container_of(clc, struct htb_class, common);
175}
176
177/**
178 * htb_classify - classify a packet into class
179 *
180 * It returns NULL if the packet should be dropped or -1 if the packet
181 * should be passed directly thru. In all other cases leaf class is returned.
182 * We allow direct class selection by classid in priority. The we examine
183 * filters in qdisc and in inner nodes (if higher filter points to the inner
184 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
185 * internal fifo (direct). These packets then go directly thru. If we still
186 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessful
187 * then finish and return direct queue.
188 */
189#define HTB_DIRECT ((struct htb_class *)-1L)
190
191static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
192 int *qerr)
193{
194 struct htb_sched *q = qdisc_priv(sch);
195 struct htb_class *cl;
196 struct tcf_result res;
197 struct tcf_proto *tcf;
198 int result;
199
200 /* allow to select class by setting skb->priority to valid classid;
201 * note that nfmark can be used too by attaching filter fw with no
202 * rules in it
203 */
204 if (skb->priority == sch->handle)
205 return HTB_DIRECT; /* X:0 (direct flow) selected */
206 cl = htb_find(skb->priority, sch);
207 if (cl && cl->level == 0)
208 return cl;
209
210 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
211 tcf = q->filter_list;
212 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
213#ifdef CONFIG_NET_CLS_ACT
214 switch (result) {
215 case TC_ACT_QUEUED:
216 case TC_ACT_STOLEN:
217 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
218 case TC_ACT_SHOT:
219 return NULL;
220 }
221#endif
222 cl = (void *)res.class;
223 if (!cl) {
224 if (res.classid == sch->handle)
225 return HTB_DIRECT; /* X:0 (direct flow) */
226 cl = htb_find(res.classid, sch);
227 if (!cl)
228 break; /* filter selected invalid classid */
229 }
230 if (!cl->level)
231 return cl; /* we hit leaf; return it */
232
233 /* we have got inner class; apply inner filter chain */
234 tcf = cl->filter_list;
235 }
236 /* classification failed; try to use default class */
237 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
238 if (!cl || cl->level)
239 return HTB_DIRECT; /* bad default .. this is safe bet */
240 return cl;
241}
242
243/**
244 * htb_add_to_id_tree - adds class to the round robin list
245 *
246 * Routine adds class to the list (actually tree) sorted by classid.
247 * Make sure that class is not already on such list for given prio.
248 */
249static void htb_add_to_id_tree(struct rb_root *root,
250 struct htb_class *cl, int prio)
251{
252 struct rb_node **p = &root->rb_node, *parent = NULL;
253
254 while (*p) {
255 struct htb_class *c;
256 parent = *p;
257 c = rb_entry(parent, struct htb_class, node[prio]);
258
259 if (cl->common.classid > c->common.classid)
260 p = &parent->rb_right;
261 else
262 p = &parent->rb_left;
263 }
264 rb_link_node(&cl->node[prio], parent, p);
265 rb_insert_color(&cl->node[prio], root);
266}
267
268/**
269 * htb_add_to_wait_tree - adds class to the event queue with delay
270 *
271 * The class is added to priority event queue to indicate that class will
272 * change its mode in cl->pq_key microseconds. Make sure that class is not
273 * already in the queue.
274 */
275static void htb_add_to_wait_tree(struct htb_sched *q,
276 struct htb_class *cl, long delay)
277{
278 struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
279
280 cl->pq_key = q->now + delay;
281 if (cl->pq_key == q->now)
282 cl->pq_key++;
283
284 /* update the nearest event cache */
285 if (q->near_ev_cache[cl->level] > cl->pq_key)
286 q->near_ev_cache[cl->level] = cl->pq_key;
287
288 while (*p) {
289 struct htb_class *c;
290 parent = *p;
291 c = rb_entry(parent, struct htb_class, pq_node);
292 if (cl->pq_key >= c->pq_key)
293 p = &parent->rb_right;
294 else
295 p = &parent->rb_left;
296 }
297 rb_link_node(&cl->pq_node, parent, p);
298 rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
299}
300
301/**
302 * htb_next_rb_node - finds next node in binary tree
303 *
304 * When we are past last key we return NULL.
305 * Average complexity is 2 steps per call.
306 */
307static inline void htb_next_rb_node(struct rb_node **n)
308{
309 *n = rb_next(*n);
310}
311
312/**
313 * htb_add_class_to_row - add class to its row
314 *
315 * The class is added to row at priorities marked in mask.
316 * It does nothing if mask == 0.
317 */
318static inline void htb_add_class_to_row(struct htb_sched *q,
319 struct htb_class *cl, int mask)
320{
321 q->row_mask[cl->level] |= mask;
322 while (mask) {
323 int prio = ffz(~mask);
324 mask &= ~(1 << prio);
325 htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio);
326 }
327}
328
329/* If this triggers, it is a bug in this code, but it need not be fatal */
330static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
331{
332 if (RB_EMPTY_NODE(rb)) {
333 WARN_ON(1);
334 } else {
335 rb_erase(rb, root);
336 RB_CLEAR_NODE(rb);
337 }
338}
339
340
341/**
342 * htb_remove_class_from_row - removes class from its row
343 *
344 * The class is removed from row at priorities marked in mask.
345 * It does nothing if mask == 0.
346 */
347static inline void htb_remove_class_from_row(struct htb_sched *q,
348 struct htb_class *cl, int mask)
349{
350 int m = 0;
351
352 while (mask) {
353 int prio = ffz(~mask);
354
355 mask &= ~(1 << prio);
356 if (q->ptr[cl->level][prio] == cl->node + prio)
357 htb_next_rb_node(q->ptr[cl->level] + prio);
358
359 htb_safe_rb_erase(cl->node + prio, q->row[cl->level] + prio);
360 if (!q->row[cl->level][prio].rb_node)
361 m |= 1 << prio;
362 }
363 q->row_mask[cl->level] &= ~m;
364}
365
366/**
367 * htb_activate_prios - creates active classe's feed chain
368 *
369 * The class is connected to ancestors and/or appropriate rows
370 * for priorities it is participating on. cl->cmode must be new
371 * (activated) mode. It does nothing if cl->prio_activity == 0.
372 */
373static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
374{
375 struct htb_class *p = cl->parent;
376 long m, mask = cl->prio_activity;
377
378 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
379 m = mask;
380 while (m) {
381 int prio = ffz(~m);
382 m &= ~(1 << prio);
383
384 if (p->un.inner.feed[prio].rb_node)
385 /* parent already has its feed in use so that
386 * reset bit in mask as parent is already ok
387 */
388 mask &= ~(1 << prio);
389
390 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
391 }
392 p->prio_activity |= mask;
393 cl = p;
394 p = cl->parent;
395
396 }
397 if (cl->cmode == HTB_CAN_SEND && mask)
398 htb_add_class_to_row(q, cl, mask);
399}
400
401/**
402 * htb_deactivate_prios - remove class from feed chain
403 *
404 * cl->cmode must represent old mode (before deactivation). It does
405 * nothing if cl->prio_activity == 0. Class is removed from all feed
406 * chains and rows.
407 */
408static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
409{
410 struct htb_class *p = cl->parent;
411 long m, mask = cl->prio_activity;
412
413 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
414 m = mask;
415 mask = 0;
416 while (m) {
417 int prio = ffz(~m);
418 m &= ~(1 << prio);
419
420 if (p->un.inner.ptr[prio] == cl->node + prio) {
421 /* we are removing child which is pointed to from
422 * parent feed - forget the pointer but remember
423 * classid
424 */
425 p->un.inner.last_ptr_id[prio] = cl->common.classid;
426 p->un.inner.ptr[prio] = NULL;
427 }
428
429 htb_safe_rb_erase(cl->node + prio, p->un.inner.feed + prio);
430
431 if (!p->un.inner.feed[prio].rb_node)
432 mask |= 1 << prio;
433 }
434
435 p->prio_activity &= ~mask;
436 cl = p;
437 p = cl->parent;
438
439 }
440 if (cl->cmode == HTB_CAN_SEND && mask)
441 htb_remove_class_from_row(q, cl, mask);
442}
443
444static inline long htb_lowater(const struct htb_class *cl)
445{
446 if (htb_hysteresis)
447 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
448 else
449 return 0;
450}
451static inline long htb_hiwater(const struct htb_class *cl)
452{
453 if (htb_hysteresis)
454 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
455 else
456 return 0;
457}
458
459
460/**
461 * htb_class_mode - computes and returns current class mode
462 *
463 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
464 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
465 * from now to time when cl will change its state.
466 * Also it is worth to note that class mode doesn't change simply
467 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
468 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
469 * mode transitions per time unit. The speed gain is about 1/6.
470 */
471static inline enum htb_cmode
472htb_class_mode(struct htb_class *cl, long *diff)
473{
474 long toks;
475
476 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
477 *diff = -toks;
478 return HTB_CANT_SEND;
479 }
480
481 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
482 return HTB_CAN_SEND;
483
484 *diff = -toks;
485 return HTB_MAY_BORROW;
486}
487
488/**
489 * htb_change_class_mode - changes classe's mode
490 *
491 * This should be the only way how to change classe's mode under normal
492 * cirsumstances. Routine will update feed lists linkage, change mode
493 * and add class to the wait event queue if appropriate. New mode should
494 * be different from old one and cl->pq_key has to be valid if changing
495 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
496 */
497static void
498htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
499{
500 enum htb_cmode new_mode = htb_class_mode(cl, diff);
501
502 if (new_mode == cl->cmode)
503 return;
504
505 if (cl->prio_activity) { /* not necessary: speed optimization */
506 if (cl->cmode != HTB_CANT_SEND)
507 htb_deactivate_prios(q, cl);
508 cl->cmode = new_mode;
509 if (new_mode != HTB_CANT_SEND)
510 htb_activate_prios(q, cl);
511 } else
512 cl->cmode = new_mode;
513}
514
515/**
516 * htb_activate - inserts leaf cl into appropriate active feeds
517 *
518 * Routine learns (new) priority of leaf and activates feed chain
519 * for the prio. It can be called on already active leaf safely.
520 * It also adds leaf into droplist.
521 */
522static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
523{
524 WARN_ON(cl->level || !cl->un.leaf.q || !cl->un.leaf.q->q.qlen);
525
526 if (!cl->prio_activity) {
527 cl->prio_activity = 1 << cl->prio;
528 htb_activate_prios(q, cl);
529 list_add_tail(&cl->un.leaf.drop_list,
530 q->drops + cl->prio);
531 }
532}
533
534/**
535 * htb_deactivate - remove leaf cl from active feeds
536 *
537 * Make sure that leaf is active. In the other words it can't be called
538 * with non-active leaf. It also removes class from the drop list.
539 */
540static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
541{
542 WARN_ON(!cl->prio_activity);
543
544 htb_deactivate_prios(q, cl);
545 cl->prio_activity = 0;
546 list_del_init(&cl->un.leaf.drop_list);
547}
548
549static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
550{
551 int uninitialized_var(ret);
552 struct htb_sched *q = qdisc_priv(sch);
553 struct htb_class *cl = htb_classify(skb, sch, &ret);
554
555 if (cl == HTB_DIRECT) {
556 /* enqueue to helper queue */
557 if (q->direct_queue.qlen < q->direct_qlen) {
558 __skb_queue_tail(&q->direct_queue, skb);
559 q->direct_pkts++;
560 } else {
561 return qdisc_drop(skb, sch);
562 }
563#ifdef CONFIG_NET_CLS_ACT
564 } else if (!cl) {
565 if (ret & __NET_XMIT_BYPASS)
566 sch->qstats.drops++;
567 kfree_skb(skb);
568 return ret;
569#endif
570 } else if ((ret = qdisc_enqueue(skb, cl->un.leaf.q)) != NET_XMIT_SUCCESS) {
571 if (net_xmit_drop_count(ret)) {
572 sch->qstats.drops++;
573 cl->qstats.drops++;
574 }
575 return ret;
576 } else {
577 htb_activate(q, cl);
578 }
579
580 sch->q.qlen++;
581 return NET_XMIT_SUCCESS;
582}
583
584static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, long diff)
585{
586 long toks = diff + cl->tokens;
587
588 if (toks > cl->buffer)
589 toks = cl->buffer;
590 toks -= (long) qdisc_l2t(cl->rate, bytes);
591 if (toks <= -cl->mbuffer)
592 toks = 1 - cl->mbuffer;
593
594 cl->tokens = toks;
595}
596
597static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, long diff)
598{
599 long toks = diff + cl->ctokens;
600
601 if (toks > cl->cbuffer)
602 toks = cl->cbuffer;
603 toks -= (long) qdisc_l2t(cl->ceil, bytes);
604 if (toks <= -cl->mbuffer)
605 toks = 1 - cl->mbuffer;
606
607 cl->ctokens = toks;
608}
609
610/**
611 * htb_charge_class - charges amount "bytes" to leaf and ancestors
612 *
613 * Routine assumes that packet "bytes" long was dequeued from leaf cl
614 * borrowing from "level". It accounts bytes to ceil leaky bucket for
615 * leaf and all ancestors and to rate bucket for ancestors at levels
616 * "level" and higher. It also handles possible change of mode resulting
617 * from the update. Note that mode can also increase here (MAY_BORROW to
618 * CAN_SEND) because we can use more precise clock that event queue here.
619 * In such case we remove class from event queue first.
620 */
621static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
622 int level, struct sk_buff *skb)
623{
624 int bytes = qdisc_pkt_len(skb);
625 enum htb_cmode old_mode;
626 long diff;
627
628 while (cl) {
629 diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
630 if (cl->level >= level) {
631 if (cl->level == level)
632 cl->xstats.lends++;
633 htb_accnt_tokens(cl, bytes, diff);
634 } else {
635 cl->xstats.borrows++;
636 cl->tokens += diff; /* we moved t_c; update tokens */
637 }
638 htb_accnt_ctokens(cl, bytes, diff);
639 cl->t_c = q->now;
640
641 old_mode = cl->cmode;
642 diff = 0;
643 htb_change_class_mode(q, cl, &diff);
644 if (old_mode != cl->cmode) {
645 if (old_mode != HTB_CAN_SEND)
646 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
647 if (cl->cmode != HTB_CAN_SEND)
648 htb_add_to_wait_tree(q, cl, diff);
649 }
650
651 /* update basic stats except for leaves which are already updated */
652 if (cl->level)
653 bstats_update(&cl->bstats, skb);
654
655 cl = cl->parent;
656 }
657}
658
659/**
660 * htb_do_events - make mode changes to classes at the level
661 *
662 * Scans event queue for pending events and applies them. Returns time of
663 * next pending event (0 for no event in pq, q->now for too many events).
664 * Note: Applied are events whose have cl->pq_key <= q->now.
665 */
666static psched_time_t htb_do_events(struct htb_sched *q, int level,
667 unsigned long start)
668{
669 /* don't run for longer than 2 jiffies; 2 is used instead of
670 * 1 to simplify things when jiffy is going to be incremented
671 * too soon
672 */
673 unsigned long stop_at = start + 2;
674 while (time_before(jiffies, stop_at)) {
675 struct htb_class *cl;
676 long diff;
677 struct rb_node *p = rb_first(&q->wait_pq[level]);
678
679 if (!p)
680 return 0;
681
682 cl = rb_entry(p, struct htb_class, pq_node);
683 if (cl->pq_key > q->now)
684 return cl->pq_key;
685
686 htb_safe_rb_erase(p, q->wait_pq + level);
687 diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
688 htb_change_class_mode(q, cl, &diff);
689 if (cl->cmode != HTB_CAN_SEND)
690 htb_add_to_wait_tree(q, cl, diff);
691 }
692
693 /* too much load - let's continue after a break for scheduling */
694 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
695 pr_warning("htb: too many events!\n");
696 q->warned |= HTB_WARN_TOOMANYEVENTS;
697 }
698
699 return q->now;
700}
701
702/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
703 * is no such one exists.
704 */
705static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
706 u32 id)
707{
708 struct rb_node *r = NULL;
709 while (n) {
710 struct htb_class *cl =
711 rb_entry(n, struct htb_class, node[prio]);
712
713 if (id > cl->common.classid) {
714 n = n->rb_right;
715 } else if (id < cl->common.classid) {
716 r = n;
717 n = n->rb_left;
718 } else {
719 return n;
720 }
721 }
722 return r;
723}
724
725/**
726 * htb_lookup_leaf - returns next leaf class in DRR order
727 *
728 * Find leaf where current feed pointers points to.
729 */
730static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio,
731 struct rb_node **pptr, u32 * pid)
732{
733 int i;
734 struct {
735 struct rb_node *root;
736 struct rb_node **pptr;
737 u32 *pid;
738 } stk[TC_HTB_MAXDEPTH], *sp = stk;
739
740 BUG_ON(!tree->rb_node);
741 sp->root = tree->rb_node;
742 sp->pptr = pptr;
743 sp->pid = pid;
744
745 for (i = 0; i < 65535; i++) {
746 if (!*sp->pptr && *sp->pid) {
747 /* ptr was invalidated but id is valid - try to recover
748 * the original or next ptr
749 */
750 *sp->pptr =
751 htb_id_find_next_upper(prio, sp->root, *sp->pid);
752 }
753 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
754 * can become out of date quickly
755 */
756 if (!*sp->pptr) { /* we are at right end; rewind & go up */
757 *sp->pptr = sp->root;
758 while ((*sp->pptr)->rb_left)
759 *sp->pptr = (*sp->pptr)->rb_left;
760 if (sp > stk) {
761 sp--;
762 if (!*sp->pptr) {
763 WARN_ON(1);
764 return NULL;
765 }
766 htb_next_rb_node(sp->pptr);
767 }
768 } else {
769 struct htb_class *cl;
770 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
771 if (!cl->level)
772 return cl;
773 (++sp)->root = cl->un.inner.feed[prio].rb_node;
774 sp->pptr = cl->un.inner.ptr + prio;
775 sp->pid = cl->un.inner.last_ptr_id + prio;
776 }
777 }
778 WARN_ON(1);
779 return NULL;
780}
781
782/* dequeues packet at given priority and level; call only if
783 * you are sure that there is active class at prio/level
784 */
785static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
786 int level)
787{
788 struct sk_buff *skb = NULL;
789 struct htb_class *cl, *start;
790 /* look initial class up in the row */
791 start = cl = htb_lookup_leaf(q->row[level] + prio, prio,
792 q->ptr[level] + prio,
793 q->last_ptr_id[level] + prio);
794
795 do {
796next:
797 if (unlikely(!cl))
798 return NULL;
799
800 /* class can be empty - it is unlikely but can be true if leaf
801 * qdisc drops packets in enqueue routine or if someone used
802 * graft operation on the leaf since last dequeue;
803 * simply deactivate and skip such class
804 */
805 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
806 struct htb_class *next;
807 htb_deactivate(q, cl);
808
809 /* row/level might become empty */
810 if ((q->row_mask[level] & (1 << prio)) == 0)
811 return NULL;
812
813 next = htb_lookup_leaf(q->row[level] + prio,
814 prio, q->ptr[level] + prio,
815 q->last_ptr_id[level] + prio);
816
817 if (cl == start) /* fix start if we just deleted it */
818 start = next;
819 cl = next;
820 goto next;
821 }
822
823 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
824 if (likely(skb != NULL))
825 break;
826
827 qdisc_warn_nonwc("htb", cl->un.leaf.q);
828 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
829 ptr[0]) + prio);
830 cl = htb_lookup_leaf(q->row[level] + prio, prio,
831 q->ptr[level] + prio,
832 q->last_ptr_id[level] + prio);
833
834 } while (cl != start);
835
836 if (likely(skb != NULL)) {
837 bstats_update(&cl->bstats, skb);
838 cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb);
839 if (cl->un.leaf.deficit[level] < 0) {
840 cl->un.leaf.deficit[level] += cl->quantum;
841 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
842 ptr[0]) + prio);
843 }
844 /* this used to be after charge_class but this constelation
845 * gives us slightly better performance
846 */
847 if (!cl->un.leaf.q->q.qlen)
848 htb_deactivate(q, cl);
849 htb_charge_class(q, cl, level, skb);
850 }
851 return skb;
852}
853
854static struct sk_buff *htb_dequeue(struct Qdisc *sch)
855{
856 struct sk_buff *skb;
857 struct htb_sched *q = qdisc_priv(sch);
858 int level;
859 psched_time_t next_event;
860 unsigned long start_at;
861
862 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
863 skb = __skb_dequeue(&q->direct_queue);
864 if (skb != NULL) {
865ok:
866 qdisc_bstats_update(sch, skb);
867 qdisc_unthrottled(sch);
868 sch->q.qlen--;
869 return skb;
870 }
871
872 if (!sch->q.qlen)
873 goto fin;
874 q->now = psched_get_time();
875 start_at = jiffies;
876
877 next_event = q->now + 5 * PSCHED_TICKS_PER_SEC;
878
879 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
880 /* common case optimization - skip event handler quickly */
881 int m;
882 psched_time_t event;
883
884 if (q->now >= q->near_ev_cache[level]) {
885 event = htb_do_events(q, level, start_at);
886 if (!event)
887 event = q->now + PSCHED_TICKS_PER_SEC;
888 q->near_ev_cache[level] = event;
889 } else
890 event = q->near_ev_cache[level];
891
892 if (next_event > event)
893 next_event = event;
894
895 m = ~q->row_mask[level];
896 while (m != (int)(-1)) {
897 int prio = ffz(m);
898
899 m |= 1 << prio;
900 skb = htb_dequeue_tree(q, prio, level);
901 if (likely(skb != NULL))
902 goto ok;
903 }
904 }
905 sch->qstats.overlimits++;
906 if (likely(next_event > q->now))
907 qdisc_watchdog_schedule(&q->watchdog, next_event);
908 else
909 schedule_work(&q->work);
910fin:
911 return skb;
912}
913
914/* try to drop from each class (by prio) until one succeed */
915static unsigned int htb_drop(struct Qdisc *sch)
916{
917 struct htb_sched *q = qdisc_priv(sch);
918 int prio;
919
920 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
921 struct list_head *p;
922 list_for_each(p, q->drops + prio) {
923 struct htb_class *cl = list_entry(p, struct htb_class,
924 un.leaf.drop_list);
925 unsigned int len;
926 if (cl->un.leaf.q->ops->drop &&
927 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
928 sch->q.qlen--;
929 if (!cl->un.leaf.q->q.qlen)
930 htb_deactivate(q, cl);
931 return len;
932 }
933 }
934 }
935 return 0;
936}
937
938/* reset all classes */
939/* always caled under BH & queue lock */
940static void htb_reset(struct Qdisc *sch)
941{
942 struct htb_sched *q = qdisc_priv(sch);
943 struct htb_class *cl;
944 struct hlist_node *n;
945 unsigned int i;
946
947 for (i = 0; i < q->clhash.hashsize; i++) {
948 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
949 if (cl->level)
950 memset(&cl->un.inner, 0, sizeof(cl->un.inner));
951 else {
952 if (cl->un.leaf.q)
953 qdisc_reset(cl->un.leaf.q);
954 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
955 }
956 cl->prio_activity = 0;
957 cl->cmode = HTB_CAN_SEND;
958
959 }
960 }
961 qdisc_watchdog_cancel(&q->watchdog);
962 __skb_queue_purge(&q->direct_queue);
963 sch->q.qlen = 0;
964 memset(q->row, 0, sizeof(q->row));
965 memset(q->row_mask, 0, sizeof(q->row_mask));
966 memset(q->wait_pq, 0, sizeof(q->wait_pq));
967 memset(q->ptr, 0, sizeof(q->ptr));
968 for (i = 0; i < TC_HTB_NUMPRIO; i++)
969 INIT_LIST_HEAD(q->drops + i);
970}
971
972static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
973 [TCA_HTB_PARMS] = { .len = sizeof(struct tc_htb_opt) },
974 [TCA_HTB_INIT] = { .len = sizeof(struct tc_htb_glob) },
975 [TCA_HTB_CTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
976 [TCA_HTB_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
977};
978
979static void htb_work_func(struct work_struct *work)
980{
981 struct htb_sched *q = container_of(work, struct htb_sched, work);
982 struct Qdisc *sch = q->watchdog.qdisc;
983
984 __netif_schedule(qdisc_root(sch));
985}
986
987static int htb_init(struct Qdisc *sch, struct nlattr *opt)
988{
989 struct htb_sched *q = qdisc_priv(sch);
990 struct nlattr *tb[TCA_HTB_INIT + 1];
991 struct tc_htb_glob *gopt;
992 int err;
993 int i;
994
995 if (!opt)
996 return -EINVAL;
997
998 err = nla_parse_nested(tb, TCA_HTB_INIT, opt, htb_policy);
999 if (err < 0)
1000 return err;
1001
1002 if (tb[TCA_HTB_INIT] == NULL) {
1003 pr_err("HTB: hey probably you have bad tc tool ?\n");
1004 return -EINVAL;
1005 }
1006 gopt = nla_data(tb[TCA_HTB_INIT]);
1007 if (gopt->version != HTB_VER >> 16) {
1008 pr_err("HTB: need tc/htb version %d (minor is %d), you have %d\n",
1009 HTB_VER >> 16, HTB_VER & 0xffff, gopt->version);
1010 return -EINVAL;
1011 }
1012
1013 err = qdisc_class_hash_init(&q->clhash);
1014 if (err < 0)
1015 return err;
1016 for (i = 0; i < TC_HTB_NUMPRIO; i++)
1017 INIT_LIST_HEAD(q->drops + i);
1018
1019 qdisc_watchdog_init(&q->watchdog, sch);
1020 INIT_WORK(&q->work, htb_work_func);
1021 skb_queue_head_init(&q->direct_queue);
1022
1023 q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
1024 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
1025 q->direct_qlen = 2;
1026
1027 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1028 q->rate2quantum = 1;
1029 q->defcls = gopt->defcls;
1030
1031 return 0;
1032}
1033
1034static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1035{
1036 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1037 struct htb_sched *q = qdisc_priv(sch);
1038 struct nlattr *nest;
1039 struct tc_htb_glob gopt;
1040
1041 spin_lock_bh(root_lock);
1042
1043 gopt.direct_pkts = q->direct_pkts;
1044 gopt.version = HTB_VER;
1045 gopt.rate2quantum = q->rate2quantum;
1046 gopt.defcls = q->defcls;
1047 gopt.debug = 0;
1048
1049 nest = nla_nest_start(skb, TCA_OPTIONS);
1050 if (nest == NULL)
1051 goto nla_put_failure;
1052 if (nla_put(skb, TCA_HTB_INIT, sizeof(gopt), &gopt))
1053 goto nla_put_failure;
1054 nla_nest_end(skb, nest);
1055
1056 spin_unlock_bh(root_lock);
1057 return skb->len;
1058
1059nla_put_failure:
1060 spin_unlock_bh(root_lock);
1061 nla_nest_cancel(skb, nest);
1062 return -1;
1063}
1064
1065static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
1066 struct sk_buff *skb, struct tcmsg *tcm)
1067{
1068 struct htb_class *cl = (struct htb_class *)arg;
1069 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1070 struct nlattr *nest;
1071 struct tc_htb_opt opt;
1072
1073 spin_lock_bh(root_lock);
1074 tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
1075 tcm->tcm_handle = cl->common.classid;
1076 if (!cl->level && cl->un.leaf.q)
1077 tcm->tcm_info = cl->un.leaf.q->handle;
1078
1079 nest = nla_nest_start(skb, TCA_OPTIONS);
1080 if (nest == NULL)
1081 goto nla_put_failure;
1082
1083 memset(&opt, 0, sizeof(opt));
1084
1085 opt.rate = cl->rate->rate;
1086 opt.buffer = cl->buffer;
1087 opt.ceil = cl->ceil->rate;
1088 opt.cbuffer = cl->cbuffer;
1089 opt.quantum = cl->quantum;
1090 opt.prio = cl->prio;
1091 opt.level = cl->level;
1092 if (nla_put(skb, TCA_HTB_PARMS, sizeof(opt), &opt))
1093 goto nla_put_failure;
1094
1095 nla_nest_end(skb, nest);
1096 spin_unlock_bh(root_lock);
1097 return skb->len;
1098
1099nla_put_failure:
1100 spin_unlock_bh(root_lock);
1101 nla_nest_cancel(skb, nest);
1102 return -1;
1103}
1104
1105static int
1106htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
1107{
1108 struct htb_class *cl = (struct htb_class *)arg;
1109
1110 if (!cl->level && cl->un.leaf.q)
1111 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
1112 cl->xstats.tokens = cl->tokens;
1113 cl->xstats.ctokens = cl->ctokens;
1114
1115 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1116 gnet_stats_copy_rate_est(d, NULL, &cl->rate_est) < 0 ||
1117 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1118 return -1;
1119
1120 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1121}
1122
1123static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1124 struct Qdisc **old)
1125{
1126 struct htb_class *cl = (struct htb_class *)arg;
1127
1128 if (cl->level)
1129 return -EINVAL;
1130 if (new == NULL &&
1131 (new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1132 cl->common.classid)) == NULL)
1133 return -ENOBUFS;
1134
1135 sch_tree_lock(sch);
1136 *old = cl->un.leaf.q;
1137 cl->un.leaf.q = new;
1138 if (*old != NULL) {
1139 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1140 qdisc_reset(*old);
1141 }
1142 sch_tree_unlock(sch);
1143 return 0;
1144}
1145
1146static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
1147{
1148 struct htb_class *cl = (struct htb_class *)arg;
1149 return !cl->level ? cl->un.leaf.q : NULL;
1150}
1151
1152static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
1153{
1154 struct htb_class *cl = (struct htb_class *)arg;
1155
1156 if (cl->un.leaf.q->q.qlen == 0)
1157 htb_deactivate(qdisc_priv(sch), cl);
1158}
1159
1160static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1161{
1162 struct htb_class *cl = htb_find(classid, sch);
1163 if (cl)
1164 cl->refcnt++;
1165 return (unsigned long)cl;
1166}
1167
1168static inline int htb_parent_last_child(struct htb_class *cl)
1169{
1170 if (!cl->parent)
1171 /* the root class */
1172 return 0;
1173 if (cl->parent->children > 1)
1174 /* not the last child */
1175 return 0;
1176 return 1;
1177}
1178
1179static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl,
1180 struct Qdisc *new_q)
1181{
1182 struct htb_class *parent = cl->parent;
1183
1184 WARN_ON(cl->level || !cl->un.leaf.q || cl->prio_activity);
1185
1186 if (parent->cmode != HTB_CAN_SEND)
1187 htb_safe_rb_erase(&parent->pq_node, q->wait_pq + parent->level);
1188
1189 parent->level = 0;
1190 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
1191 INIT_LIST_HEAD(&parent->un.leaf.drop_list);
1192 parent->un.leaf.q = new_q ? new_q : &noop_qdisc;
1193 parent->tokens = parent->buffer;
1194 parent->ctokens = parent->cbuffer;
1195 parent->t_c = psched_get_time();
1196 parent->cmode = HTB_CAN_SEND;
1197}
1198
1199static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
1200{
1201 if (!cl->level) {
1202 WARN_ON(!cl->un.leaf.q);
1203 qdisc_destroy(cl->un.leaf.q);
1204 }
1205 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1206 qdisc_put_rtab(cl->rate);
1207 qdisc_put_rtab(cl->ceil);
1208
1209 tcf_destroy_chain(&cl->filter_list);
1210 kfree(cl);
1211}
1212
1213static void htb_destroy(struct Qdisc *sch)
1214{
1215 struct htb_sched *q = qdisc_priv(sch);
1216 struct hlist_node *n, *next;
1217 struct htb_class *cl;
1218 unsigned int i;
1219
1220 cancel_work_sync(&q->work);
1221 qdisc_watchdog_cancel(&q->watchdog);
1222 /* This line used to be after htb_destroy_class call below
1223 * and surprisingly it worked in 2.4. But it must precede it
1224 * because filter need its target class alive to be able to call
1225 * unbind_filter on it (without Oops).
1226 */
1227 tcf_destroy_chain(&q->filter_list);
1228
1229 for (i = 0; i < q->clhash.hashsize; i++) {
1230 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
1231 tcf_destroy_chain(&cl->filter_list);
1232 }
1233 for (i = 0; i < q->clhash.hashsize; i++) {
1234 hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[i],
1235 common.hnode)
1236 htb_destroy_class(sch, cl);
1237 }
1238 qdisc_class_hash_destroy(&q->clhash);
1239 __skb_queue_purge(&q->direct_queue);
1240}
1241
1242static int htb_delete(struct Qdisc *sch, unsigned long arg)
1243{
1244 struct htb_sched *q = qdisc_priv(sch);
1245 struct htb_class *cl = (struct htb_class *)arg;
1246 unsigned int qlen;
1247 struct Qdisc *new_q = NULL;
1248 int last_child = 0;
1249
1250 // TODO: why don't allow to delete subtree ? references ? does
1251 // tc subsys quarantee us that in htb_destroy it holds no class
1252 // refs so that we can remove children safely there ?
1253 if (cl->children || cl->filter_cnt)
1254 return -EBUSY;
1255
1256 if (!cl->level && htb_parent_last_child(cl)) {
1257 new_q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1258 cl->parent->common.classid);
1259 last_child = 1;
1260 }
1261
1262 sch_tree_lock(sch);
1263
1264 if (!cl->level) {
1265 qlen = cl->un.leaf.q->q.qlen;
1266 qdisc_reset(cl->un.leaf.q);
1267 qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
1268 }
1269
1270 /* delete from hash and active; remainder in destroy_class */
1271 qdisc_class_hash_remove(&q->clhash, &cl->common);
1272 if (cl->parent)
1273 cl->parent->children--;
1274
1275 if (cl->prio_activity)
1276 htb_deactivate(q, cl);
1277
1278 if (cl->cmode != HTB_CAN_SEND)
1279 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
1280
1281 if (last_child)
1282 htb_parent_to_leaf(q, cl, new_q);
1283
1284 BUG_ON(--cl->refcnt == 0);
1285 /*
1286 * This shouldn't happen: we "hold" one cops->get() when called
1287 * from tc_ctl_tclass; the destroy method is done from cops->put().
1288 */
1289
1290 sch_tree_unlock(sch);
1291 return 0;
1292}
1293
1294static void htb_put(struct Qdisc *sch, unsigned long arg)
1295{
1296 struct htb_class *cl = (struct htb_class *)arg;
1297
1298 if (--cl->refcnt == 0)
1299 htb_destroy_class(sch, cl);
1300}
1301
1302static int htb_change_class(struct Qdisc *sch, u32 classid,
1303 u32 parentid, struct nlattr **tca,
1304 unsigned long *arg)
1305{
1306 int err = -EINVAL;
1307 struct htb_sched *q = qdisc_priv(sch);
1308 struct htb_class *cl = (struct htb_class *)*arg, *parent;
1309 struct nlattr *opt = tca[TCA_OPTIONS];
1310 struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
1311 struct nlattr *tb[__TCA_HTB_MAX];
1312 struct tc_htb_opt *hopt;
1313
1314 /* extract all subattrs from opt attr */
1315 if (!opt)
1316 goto failure;
1317
1318 err = nla_parse_nested(tb, TCA_HTB_MAX, opt, htb_policy);
1319 if (err < 0)
1320 goto failure;
1321
1322 err = -EINVAL;
1323 if (tb[TCA_HTB_PARMS] == NULL)
1324 goto failure;
1325
1326 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
1327
1328 hopt = nla_data(tb[TCA_HTB_PARMS]);
1329
1330 rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB]);
1331 ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB]);
1332 if (!rtab || !ctab)
1333 goto failure;
1334
1335 if (!cl) { /* new class */
1336 struct Qdisc *new_q;
1337 int prio;
1338 struct {
1339 struct nlattr nla;
1340 struct gnet_estimator opt;
1341 } est = {
1342 .nla = {
1343 .nla_len = nla_attr_size(sizeof(est.opt)),
1344 .nla_type = TCA_RATE,
1345 },
1346 .opt = {
1347 /* 4s interval, 16s averaging constant */
1348 .interval = 2,
1349 .ewma_log = 2,
1350 },
1351 };
1352
1353 /* check for valid classid */
1354 if (!classid || TC_H_MAJ(classid ^ sch->handle) ||
1355 htb_find(classid, sch))
1356 goto failure;
1357
1358 /* check maximal depth */
1359 if (parent && parent->parent && parent->parent->level < 2) {
1360 pr_err("htb: tree is too deep\n");
1361 goto failure;
1362 }
1363 err = -ENOBUFS;
1364 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1365 if (!cl)
1366 goto failure;
1367
1368 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1369 qdisc_root_sleeping_lock(sch),
1370 tca[TCA_RATE] ? : &est.nla);
1371 if (err) {
1372 kfree(cl);
1373 goto failure;
1374 }
1375
1376 cl->refcnt = 1;
1377 cl->children = 0;
1378 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1379 RB_CLEAR_NODE(&cl->pq_node);
1380
1381 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1382 RB_CLEAR_NODE(&cl->node[prio]);
1383
1384 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
1385 * so that can't be used inside of sch_tree_lock
1386 * -- thanks to Karlis Peisenieks
1387 */
1388 new_q = qdisc_create_dflt(sch->dev_queue,
1389 &pfifo_qdisc_ops, classid);
1390 sch_tree_lock(sch);
1391 if (parent && !parent->level) {
1392 unsigned int qlen = parent->un.leaf.q->q.qlen;
1393
1394 /* turn parent into inner node */
1395 qdisc_reset(parent->un.leaf.q);
1396 qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen);
1397 qdisc_destroy(parent->un.leaf.q);
1398 if (parent->prio_activity)
1399 htb_deactivate(q, parent);
1400
1401 /* remove from evt list because of level change */
1402 if (parent->cmode != HTB_CAN_SEND) {
1403 htb_safe_rb_erase(&parent->pq_node, q->wait_pq);
1404 parent->cmode = HTB_CAN_SEND;
1405 }
1406 parent->level = (parent->parent ? parent->parent->level
1407 : TC_HTB_MAXDEPTH) - 1;
1408 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
1409 }
1410 /* leaf (we) needs elementary qdisc */
1411 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1412
1413 cl->common.classid = classid;
1414 cl->parent = parent;
1415
1416 /* set class to be in HTB_CAN_SEND state */
1417 cl->tokens = hopt->buffer;
1418 cl->ctokens = hopt->cbuffer;
1419 cl->mbuffer = 60 * PSCHED_TICKS_PER_SEC; /* 1min */
1420 cl->t_c = psched_get_time();
1421 cl->cmode = HTB_CAN_SEND;
1422
1423 /* attach to the hash list and parent's family */
1424 qdisc_class_hash_insert(&q->clhash, &cl->common);
1425 if (parent)
1426 parent->children++;
1427 } else {
1428 if (tca[TCA_RATE]) {
1429 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1430 qdisc_root_sleeping_lock(sch),
1431 tca[TCA_RATE]);
1432 if (err)
1433 return err;
1434 }
1435 sch_tree_lock(sch);
1436 }
1437
1438 /* it used to be a nasty bug here, we have to check that node
1439 * is really leaf before changing cl->un.leaf !
1440 */
1441 if (!cl->level) {
1442 cl->quantum = rtab->rate.rate / q->rate2quantum;
1443 if (!hopt->quantum && cl->quantum < 1000) {
1444 pr_warning(
1445 "HTB: quantum of class %X is small. Consider r2q change.\n",
1446 cl->common.classid);
1447 cl->quantum = 1000;
1448 }
1449 if (!hopt->quantum && cl->quantum > 200000) {
1450 pr_warning(
1451 "HTB: quantum of class %X is big. Consider r2q change.\n",
1452 cl->common.classid);
1453 cl->quantum = 200000;
1454 }
1455 if (hopt->quantum)
1456 cl->quantum = hopt->quantum;
1457 if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO)
1458 cl->prio = TC_HTB_NUMPRIO - 1;
1459 }
1460
1461 cl->buffer = hopt->buffer;
1462 cl->cbuffer = hopt->cbuffer;
1463 if (cl->rate)
1464 qdisc_put_rtab(cl->rate);
1465 cl->rate = rtab;
1466 if (cl->ceil)
1467 qdisc_put_rtab(cl->ceil);
1468 cl->ceil = ctab;
1469 sch_tree_unlock(sch);
1470
1471 qdisc_class_hash_grow(sch, &q->clhash);
1472
1473 *arg = (unsigned long)cl;
1474 return 0;
1475
1476failure:
1477 if (rtab)
1478 qdisc_put_rtab(rtab);
1479 if (ctab)
1480 qdisc_put_rtab(ctab);
1481 return err;
1482}
1483
1484static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1485{
1486 struct htb_sched *q = qdisc_priv(sch);
1487 struct htb_class *cl = (struct htb_class *)arg;
1488 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
1489
1490 return fl;
1491}
1492
1493static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
1494 u32 classid)
1495{
1496 struct htb_class *cl = htb_find(classid, sch);
1497
1498 /*if (cl && !cl->level) return 0;
1499 * The line above used to be there to prevent attaching filters to
1500 * leaves. But at least tc_index filter uses this just to get class
1501 * for other reasons so that we have to allow for it.
1502 * ----
1503 * 19.6.2002 As Werner explained it is ok - bind filter is just
1504 * another way to "lock" the class - unlike "get" this lock can
1505 * be broken by class during destroy IIUC.
1506 */
1507 if (cl)
1508 cl->filter_cnt++;
1509 return (unsigned long)cl;
1510}
1511
1512static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1513{
1514 struct htb_class *cl = (struct htb_class *)arg;
1515
1516 if (cl)
1517 cl->filter_cnt--;
1518}
1519
1520static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1521{
1522 struct htb_sched *q = qdisc_priv(sch);
1523 struct htb_class *cl;
1524 struct hlist_node *n;
1525 unsigned int i;
1526
1527 if (arg->stop)
1528 return;
1529
1530 for (i = 0; i < q->clhash.hashsize; i++) {
1531 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
1532 if (arg->count < arg->skip) {
1533 arg->count++;
1534 continue;
1535 }
1536 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1537 arg->stop = 1;
1538 return;
1539 }
1540 arg->count++;
1541 }
1542 }
1543}
1544
1545static const struct Qdisc_class_ops htb_class_ops = {
1546 .graft = htb_graft,
1547 .leaf = htb_leaf,
1548 .qlen_notify = htb_qlen_notify,
1549 .get = htb_get,
1550 .put = htb_put,
1551 .change = htb_change_class,
1552 .delete = htb_delete,
1553 .walk = htb_walk,
1554 .tcf_chain = htb_find_tcf,
1555 .bind_tcf = htb_bind_filter,
1556 .unbind_tcf = htb_unbind_filter,
1557 .dump = htb_dump_class,
1558 .dump_stats = htb_dump_class_stats,
1559};
1560
1561static struct Qdisc_ops htb_qdisc_ops __read_mostly = {
1562 .cl_ops = &htb_class_ops,
1563 .id = "htb",
1564 .priv_size = sizeof(struct htb_sched),
1565 .enqueue = htb_enqueue,
1566 .dequeue = htb_dequeue,
1567 .peek = qdisc_peek_dequeued,
1568 .drop = htb_drop,
1569 .init = htb_init,
1570 .reset = htb_reset,
1571 .destroy = htb_destroy,
1572 .dump = htb_dump,
1573 .owner = THIS_MODULE,
1574};
1575
1576static int __init htb_module_init(void)
1577{
1578 return register_qdisc(&htb_qdisc_ops);
1579}
1580static void __exit htb_module_exit(void)
1581{
1582 unregister_qdisc(&htb_qdisc_ops);
1583}
1584
1585module_init(htb_module_init)
1586module_exit(htb_module_exit)
1587MODULE_LICENSE("GPL");
1// SPDX-License-Identifier: GPL-2.0-or-later
2/*
3 * net/sched/sch_htb.c Hierarchical token bucket, feed tree version
4 *
5 * Authors: Martin Devera, <devik@cdi.cz>
6 *
7 * Credits (in time order) for older HTB versions:
8 * Stef Coene <stef.coene@docum.org>
9 * HTB support at LARTC mailing list
10 * Ondrej Kraus, <krauso@barr.cz>
11 * found missing INIT_QDISC(htb)
12 * Vladimir Smelhaus, Aamer Akhter, Bert Hubert
13 * helped a lot to locate nasty class stall bug
14 * Andi Kleen, Jamal Hadi, Bert Hubert
15 * code review and helpful comments on shaping
16 * Tomasz Wrona, <tw@eter.tym.pl>
17 * created test case so that I was able to fix nasty bug
18 * Wilfried Weissmann
19 * spotted bug in dequeue code and helped with fix
20 * Jiri Fojtasek
21 * fixed requeue routine
22 * and many others. thanks.
23 */
24#include <linux/module.h>
25#include <linux/moduleparam.h>
26#include <linux/types.h>
27#include <linux/kernel.h>
28#include <linux/string.h>
29#include <linux/errno.h>
30#include <linux/skbuff.h>
31#include <linux/list.h>
32#include <linux/compiler.h>
33#include <linux/rbtree.h>
34#include <linux/workqueue.h>
35#include <linux/slab.h>
36#include <net/netlink.h>
37#include <net/sch_generic.h>
38#include <net/pkt_sched.h>
39#include <net/pkt_cls.h>
40
41/* HTB algorithm.
42 Author: devik@cdi.cz
43 ========================================================================
44 HTB is like TBF with multiple classes. It is also similar to CBQ because
45 it allows to assign priority to each class in hierarchy.
46 In fact it is another implementation of Floyd's formal sharing.
47
48 Levels:
49 Each class is assigned level. Leaf has ALWAYS level 0 and root
50 classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
51 one less than their parent.
52*/
53
54static int htb_hysteresis __read_mostly = 0; /* whether to use mode hysteresis for speedup */
55#define HTB_VER 0x30011 /* major must be matched with number supplied by TC as version */
56
57#if HTB_VER >> 16 != TC_HTB_PROTOVER
58#error "Mismatched sch_htb.c and pkt_sch.h"
59#endif
60
61/* Module parameter and sysfs export */
62module_param (htb_hysteresis, int, 0640);
63MODULE_PARM_DESC(htb_hysteresis, "Hysteresis mode, less CPU load, less accurate");
64
65static int htb_rate_est = 0; /* htb classes have a default rate estimator */
66module_param(htb_rate_est, int, 0640);
67MODULE_PARM_DESC(htb_rate_est, "setup a default rate estimator (4sec 16sec) for htb classes");
68
69/* used internaly to keep status of single class */
70enum htb_cmode {
71 HTB_CANT_SEND, /* class can't send and can't borrow */
72 HTB_MAY_BORROW, /* class can't send but may borrow */
73 HTB_CAN_SEND /* class can send */
74};
75
76struct htb_prio {
77 union {
78 struct rb_root row;
79 struct rb_root feed;
80 };
81 struct rb_node *ptr;
82 /* When class changes from state 1->2 and disconnects from
83 * parent's feed then we lost ptr value and start from the
84 * first child again. Here we store classid of the
85 * last valid ptr (used when ptr is NULL).
86 */
87 u32 last_ptr_id;
88};
89
90/* interior & leaf nodes; props specific to leaves are marked L:
91 * To reduce false sharing, place mostly read fields at beginning,
92 * and mostly written ones at the end.
93 */
94struct htb_class {
95 struct Qdisc_class_common common;
96 struct psched_ratecfg rate;
97 struct psched_ratecfg ceil;
98 s64 buffer, cbuffer;/* token bucket depth/rate */
99 s64 mbuffer; /* max wait time */
100 u32 prio; /* these two are used only by leaves... */
101 int quantum; /* but stored for parent-to-leaf return */
102
103 struct tcf_proto __rcu *filter_list; /* class attached filters */
104 struct tcf_block *block;
105 int filter_cnt;
106
107 int level; /* our level (see above) */
108 unsigned int children;
109 struct htb_class *parent; /* parent class */
110
111 struct net_rate_estimator __rcu *rate_est;
112
113 /*
114 * Written often fields
115 */
116 struct gnet_stats_basic_packed bstats;
117 struct gnet_stats_basic_packed bstats_bias;
118 struct tc_htb_xstats xstats; /* our special stats */
119
120 /* token bucket parameters */
121 s64 tokens, ctokens;/* current number of tokens */
122 s64 t_c; /* checkpoint time */
123
124 union {
125 struct htb_class_leaf {
126 int deficit[TC_HTB_MAXDEPTH];
127 struct Qdisc *q;
128 struct netdev_queue *offload_queue;
129 } leaf;
130 struct htb_class_inner {
131 struct htb_prio clprio[TC_HTB_NUMPRIO];
132 } inner;
133 };
134 s64 pq_key;
135
136 int prio_activity; /* for which prios are we active */
137 enum htb_cmode cmode; /* current mode of the class */
138 struct rb_node pq_node; /* node for event queue */
139 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
140
141 unsigned int drops ____cacheline_aligned_in_smp;
142 unsigned int overlimits;
143};
144
145struct htb_level {
146 struct rb_root wait_pq;
147 struct htb_prio hprio[TC_HTB_NUMPRIO];
148};
149
150struct htb_sched {
151 struct Qdisc_class_hash clhash;
152 int defcls; /* class where unclassified flows go to */
153 int rate2quantum; /* quant = rate / rate2quantum */
154
155 /* filters for qdisc itself */
156 struct tcf_proto __rcu *filter_list;
157 struct tcf_block *block;
158
159#define HTB_WARN_TOOMANYEVENTS 0x1
160 unsigned int warned; /* only one warning */
161 int direct_qlen;
162 struct work_struct work;
163
164 /* non shaped skbs; let them go directly thru */
165 struct qdisc_skb_head direct_queue;
166 u32 direct_pkts;
167 u32 overlimits;
168
169 struct qdisc_watchdog watchdog;
170
171 s64 now; /* cached dequeue time */
172
173 /* time of nearest event per level (row) */
174 s64 near_ev_cache[TC_HTB_MAXDEPTH];
175
176 int row_mask[TC_HTB_MAXDEPTH];
177
178 struct htb_level hlevel[TC_HTB_MAXDEPTH];
179
180 struct Qdisc **direct_qdiscs;
181 unsigned int num_direct_qdiscs;
182
183 bool offload;
184};
185
186/* find class in global hash table using given handle */
187static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
188{
189 struct htb_sched *q = qdisc_priv(sch);
190 struct Qdisc_class_common *clc;
191
192 clc = qdisc_class_find(&q->clhash, handle);
193 if (clc == NULL)
194 return NULL;
195 return container_of(clc, struct htb_class, common);
196}
197
198static unsigned long htb_search(struct Qdisc *sch, u32 handle)
199{
200 return (unsigned long)htb_find(handle, sch);
201}
202/**
203 * htb_classify - classify a packet into class
204 *
205 * It returns NULL if the packet should be dropped or -1 if the packet
206 * should be passed directly thru. In all other cases leaf class is returned.
207 * We allow direct class selection by classid in priority. The we examine
208 * filters in qdisc and in inner nodes (if higher filter points to the inner
209 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
210 * internal fifo (direct). These packets then go directly thru. If we still
211 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessful
212 * then finish and return direct queue.
213 */
214#define HTB_DIRECT ((struct htb_class *)-1L)
215
216static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
217 int *qerr)
218{
219 struct htb_sched *q = qdisc_priv(sch);
220 struct htb_class *cl;
221 struct tcf_result res;
222 struct tcf_proto *tcf;
223 int result;
224
225 /* allow to select class by setting skb->priority to valid classid;
226 * note that nfmark can be used too by attaching filter fw with no
227 * rules in it
228 */
229 if (skb->priority == sch->handle)
230 return HTB_DIRECT; /* X:0 (direct flow) selected */
231 cl = htb_find(skb->priority, sch);
232 if (cl) {
233 if (cl->level == 0)
234 return cl;
235 /* Start with inner filter chain if a non-leaf class is selected */
236 tcf = rcu_dereference_bh(cl->filter_list);
237 } else {
238 tcf = rcu_dereference_bh(q->filter_list);
239 }
240
241 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
242 while (tcf && (result = tcf_classify(skb, tcf, &res, false)) >= 0) {
243#ifdef CONFIG_NET_CLS_ACT
244 switch (result) {
245 case TC_ACT_QUEUED:
246 case TC_ACT_STOLEN:
247 case TC_ACT_TRAP:
248 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
249 fallthrough;
250 case TC_ACT_SHOT:
251 return NULL;
252 }
253#endif
254 cl = (void *)res.class;
255 if (!cl) {
256 if (res.classid == sch->handle)
257 return HTB_DIRECT; /* X:0 (direct flow) */
258 cl = htb_find(res.classid, sch);
259 if (!cl)
260 break; /* filter selected invalid classid */
261 }
262 if (!cl->level)
263 return cl; /* we hit leaf; return it */
264
265 /* we have got inner class; apply inner filter chain */
266 tcf = rcu_dereference_bh(cl->filter_list);
267 }
268 /* classification failed; try to use default class */
269 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
270 if (!cl || cl->level)
271 return HTB_DIRECT; /* bad default .. this is safe bet */
272 return cl;
273}
274
275/**
276 * htb_add_to_id_tree - adds class to the round robin list
277 * @root: the root of the tree
278 * @cl: the class to add
279 * @prio: the give prio in class
280 *
281 * Routine adds class to the list (actually tree) sorted by classid.
282 * Make sure that class is not already on such list for given prio.
283 */
284static void htb_add_to_id_tree(struct rb_root *root,
285 struct htb_class *cl, int prio)
286{
287 struct rb_node **p = &root->rb_node, *parent = NULL;
288
289 while (*p) {
290 struct htb_class *c;
291 parent = *p;
292 c = rb_entry(parent, struct htb_class, node[prio]);
293
294 if (cl->common.classid > c->common.classid)
295 p = &parent->rb_right;
296 else
297 p = &parent->rb_left;
298 }
299 rb_link_node(&cl->node[prio], parent, p);
300 rb_insert_color(&cl->node[prio], root);
301}
302
303/**
304 * htb_add_to_wait_tree - adds class to the event queue with delay
305 * @q: the priority event queue
306 * @cl: the class to add
307 * @delay: delay in microseconds
308 *
309 * The class is added to priority event queue to indicate that class will
310 * change its mode in cl->pq_key microseconds. Make sure that class is not
311 * already in the queue.
312 */
313static void htb_add_to_wait_tree(struct htb_sched *q,
314 struct htb_class *cl, s64 delay)
315{
316 struct rb_node **p = &q->hlevel[cl->level].wait_pq.rb_node, *parent = NULL;
317
318 cl->pq_key = q->now + delay;
319 if (cl->pq_key == q->now)
320 cl->pq_key++;
321
322 /* update the nearest event cache */
323 if (q->near_ev_cache[cl->level] > cl->pq_key)
324 q->near_ev_cache[cl->level] = cl->pq_key;
325
326 while (*p) {
327 struct htb_class *c;
328 parent = *p;
329 c = rb_entry(parent, struct htb_class, pq_node);
330 if (cl->pq_key >= c->pq_key)
331 p = &parent->rb_right;
332 else
333 p = &parent->rb_left;
334 }
335 rb_link_node(&cl->pq_node, parent, p);
336 rb_insert_color(&cl->pq_node, &q->hlevel[cl->level].wait_pq);
337}
338
339/**
340 * htb_next_rb_node - finds next node in binary tree
341 * @n: the current node in binary tree
342 *
343 * When we are past last key we return NULL.
344 * Average complexity is 2 steps per call.
345 */
346static inline void htb_next_rb_node(struct rb_node **n)
347{
348 *n = rb_next(*n);
349}
350
351/**
352 * htb_add_class_to_row - add class to its row
353 * @q: the priority event queue
354 * @cl: the class to add
355 * @mask: the given priorities in class in bitmap
356 *
357 * The class is added to row at priorities marked in mask.
358 * It does nothing if mask == 0.
359 */
360static inline void htb_add_class_to_row(struct htb_sched *q,
361 struct htb_class *cl, int mask)
362{
363 q->row_mask[cl->level] |= mask;
364 while (mask) {
365 int prio = ffz(~mask);
366 mask &= ~(1 << prio);
367 htb_add_to_id_tree(&q->hlevel[cl->level].hprio[prio].row, cl, prio);
368 }
369}
370
371/* If this triggers, it is a bug in this code, but it need not be fatal */
372static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
373{
374 if (RB_EMPTY_NODE(rb)) {
375 WARN_ON(1);
376 } else {
377 rb_erase(rb, root);
378 RB_CLEAR_NODE(rb);
379 }
380}
381
382
383/**
384 * htb_remove_class_from_row - removes class from its row
385 * @q: the priority event queue
386 * @cl: the class to add
387 * @mask: the given priorities in class in bitmap
388 *
389 * The class is removed from row at priorities marked in mask.
390 * It does nothing if mask == 0.
391 */
392static inline void htb_remove_class_from_row(struct htb_sched *q,
393 struct htb_class *cl, int mask)
394{
395 int m = 0;
396 struct htb_level *hlevel = &q->hlevel[cl->level];
397
398 while (mask) {
399 int prio = ffz(~mask);
400 struct htb_prio *hprio = &hlevel->hprio[prio];
401
402 mask &= ~(1 << prio);
403 if (hprio->ptr == cl->node + prio)
404 htb_next_rb_node(&hprio->ptr);
405
406 htb_safe_rb_erase(cl->node + prio, &hprio->row);
407 if (!hprio->row.rb_node)
408 m |= 1 << prio;
409 }
410 q->row_mask[cl->level] &= ~m;
411}
412
413/**
414 * htb_activate_prios - creates active classe's feed chain
415 * @q: the priority event queue
416 * @cl: the class to activate
417 *
418 * The class is connected to ancestors and/or appropriate rows
419 * for priorities it is participating on. cl->cmode must be new
420 * (activated) mode. It does nothing if cl->prio_activity == 0.
421 */
422static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
423{
424 struct htb_class *p = cl->parent;
425 long m, mask = cl->prio_activity;
426
427 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
428 m = mask;
429 while (m) {
430 int prio = ffz(~m);
431 m &= ~(1 << prio);
432
433 if (p->inner.clprio[prio].feed.rb_node)
434 /* parent already has its feed in use so that
435 * reset bit in mask as parent is already ok
436 */
437 mask &= ~(1 << prio);
438
439 htb_add_to_id_tree(&p->inner.clprio[prio].feed, cl, prio);
440 }
441 p->prio_activity |= mask;
442 cl = p;
443 p = cl->parent;
444
445 }
446 if (cl->cmode == HTB_CAN_SEND && mask)
447 htb_add_class_to_row(q, cl, mask);
448}
449
450/**
451 * htb_deactivate_prios - remove class from feed chain
452 * @q: the priority event queue
453 * @cl: the class to deactivate
454 *
455 * cl->cmode must represent old mode (before deactivation). It does
456 * nothing if cl->prio_activity == 0. Class is removed from all feed
457 * chains and rows.
458 */
459static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
460{
461 struct htb_class *p = cl->parent;
462 long m, mask = cl->prio_activity;
463
464 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
465 m = mask;
466 mask = 0;
467 while (m) {
468 int prio = ffz(~m);
469 m &= ~(1 << prio);
470
471 if (p->inner.clprio[prio].ptr == cl->node + prio) {
472 /* we are removing child which is pointed to from
473 * parent feed - forget the pointer but remember
474 * classid
475 */
476 p->inner.clprio[prio].last_ptr_id = cl->common.classid;
477 p->inner.clprio[prio].ptr = NULL;
478 }
479
480 htb_safe_rb_erase(cl->node + prio,
481 &p->inner.clprio[prio].feed);
482
483 if (!p->inner.clprio[prio].feed.rb_node)
484 mask |= 1 << prio;
485 }
486
487 p->prio_activity &= ~mask;
488 cl = p;
489 p = cl->parent;
490
491 }
492 if (cl->cmode == HTB_CAN_SEND && mask)
493 htb_remove_class_from_row(q, cl, mask);
494}
495
496static inline s64 htb_lowater(const struct htb_class *cl)
497{
498 if (htb_hysteresis)
499 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
500 else
501 return 0;
502}
503static inline s64 htb_hiwater(const struct htb_class *cl)
504{
505 if (htb_hysteresis)
506 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
507 else
508 return 0;
509}
510
511
512/**
513 * htb_class_mode - computes and returns current class mode
514 * @cl: the target class
515 * @diff: diff time in microseconds
516 *
517 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
518 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
519 * from now to time when cl will change its state.
520 * Also it is worth to note that class mode doesn't change simply
521 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
522 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
523 * mode transitions per time unit. The speed gain is about 1/6.
524 */
525static inline enum htb_cmode
526htb_class_mode(struct htb_class *cl, s64 *diff)
527{
528 s64 toks;
529
530 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
531 *diff = -toks;
532 return HTB_CANT_SEND;
533 }
534
535 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
536 return HTB_CAN_SEND;
537
538 *diff = -toks;
539 return HTB_MAY_BORROW;
540}
541
542/**
543 * htb_change_class_mode - changes classe's mode
544 * @q: the priority event queue
545 * @cl: the target class
546 * @diff: diff time in microseconds
547 *
548 * This should be the only way how to change classe's mode under normal
549 * circumstances. Routine will update feed lists linkage, change mode
550 * and add class to the wait event queue if appropriate. New mode should
551 * be different from old one and cl->pq_key has to be valid if changing
552 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
553 */
554static void
555htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, s64 *diff)
556{
557 enum htb_cmode new_mode = htb_class_mode(cl, diff);
558
559 if (new_mode == cl->cmode)
560 return;
561
562 if (new_mode == HTB_CANT_SEND) {
563 cl->overlimits++;
564 q->overlimits++;
565 }
566
567 if (cl->prio_activity) { /* not necessary: speed optimization */
568 if (cl->cmode != HTB_CANT_SEND)
569 htb_deactivate_prios(q, cl);
570 cl->cmode = new_mode;
571 if (new_mode != HTB_CANT_SEND)
572 htb_activate_prios(q, cl);
573 } else
574 cl->cmode = new_mode;
575}
576
577/**
578 * htb_activate - inserts leaf cl into appropriate active feeds
579 * @q: the priority event queue
580 * @cl: the target class
581 *
582 * Routine learns (new) priority of leaf and activates feed chain
583 * for the prio. It can be called on already active leaf safely.
584 * It also adds leaf into droplist.
585 */
586static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
587{
588 WARN_ON(cl->level || !cl->leaf.q || !cl->leaf.q->q.qlen);
589
590 if (!cl->prio_activity) {
591 cl->prio_activity = 1 << cl->prio;
592 htb_activate_prios(q, cl);
593 }
594}
595
596/**
597 * htb_deactivate - remove leaf cl from active feeds
598 * @q: the priority event queue
599 * @cl: the target class
600 *
601 * Make sure that leaf is active. In the other words it can't be called
602 * with non-active leaf. It also removes class from the drop list.
603 */
604static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
605{
606 WARN_ON(!cl->prio_activity);
607
608 htb_deactivate_prios(q, cl);
609 cl->prio_activity = 0;
610}
611
612static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch,
613 struct sk_buff **to_free)
614{
615 int ret;
616 unsigned int len = qdisc_pkt_len(skb);
617 struct htb_sched *q = qdisc_priv(sch);
618 struct htb_class *cl = htb_classify(skb, sch, &ret);
619
620 if (cl == HTB_DIRECT) {
621 /* enqueue to helper queue */
622 if (q->direct_queue.qlen < q->direct_qlen) {
623 __qdisc_enqueue_tail(skb, &q->direct_queue);
624 q->direct_pkts++;
625 } else {
626 return qdisc_drop(skb, sch, to_free);
627 }
628#ifdef CONFIG_NET_CLS_ACT
629 } else if (!cl) {
630 if (ret & __NET_XMIT_BYPASS)
631 qdisc_qstats_drop(sch);
632 __qdisc_drop(skb, to_free);
633 return ret;
634#endif
635 } else if ((ret = qdisc_enqueue(skb, cl->leaf.q,
636 to_free)) != NET_XMIT_SUCCESS) {
637 if (net_xmit_drop_count(ret)) {
638 qdisc_qstats_drop(sch);
639 cl->drops++;
640 }
641 return ret;
642 } else {
643 htb_activate(q, cl);
644 }
645
646 sch->qstats.backlog += len;
647 sch->q.qlen++;
648 return NET_XMIT_SUCCESS;
649}
650
651static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, s64 diff)
652{
653 s64 toks = diff + cl->tokens;
654
655 if (toks > cl->buffer)
656 toks = cl->buffer;
657 toks -= (s64) psched_l2t_ns(&cl->rate, bytes);
658 if (toks <= -cl->mbuffer)
659 toks = 1 - cl->mbuffer;
660
661 cl->tokens = toks;
662}
663
664static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, s64 diff)
665{
666 s64 toks = diff + cl->ctokens;
667
668 if (toks > cl->cbuffer)
669 toks = cl->cbuffer;
670 toks -= (s64) psched_l2t_ns(&cl->ceil, bytes);
671 if (toks <= -cl->mbuffer)
672 toks = 1 - cl->mbuffer;
673
674 cl->ctokens = toks;
675}
676
677/**
678 * htb_charge_class - charges amount "bytes" to leaf and ancestors
679 * @q: the priority event queue
680 * @cl: the class to start iterate
681 * @level: the minimum level to account
682 * @skb: the socket buffer
683 *
684 * Routine assumes that packet "bytes" long was dequeued from leaf cl
685 * borrowing from "level". It accounts bytes to ceil leaky bucket for
686 * leaf and all ancestors and to rate bucket for ancestors at levels
687 * "level" and higher. It also handles possible change of mode resulting
688 * from the update. Note that mode can also increase here (MAY_BORROW to
689 * CAN_SEND) because we can use more precise clock that event queue here.
690 * In such case we remove class from event queue first.
691 */
692static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
693 int level, struct sk_buff *skb)
694{
695 int bytes = qdisc_pkt_len(skb);
696 enum htb_cmode old_mode;
697 s64 diff;
698
699 while (cl) {
700 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
701 if (cl->level >= level) {
702 if (cl->level == level)
703 cl->xstats.lends++;
704 htb_accnt_tokens(cl, bytes, diff);
705 } else {
706 cl->xstats.borrows++;
707 cl->tokens += diff; /* we moved t_c; update tokens */
708 }
709 htb_accnt_ctokens(cl, bytes, diff);
710 cl->t_c = q->now;
711
712 old_mode = cl->cmode;
713 diff = 0;
714 htb_change_class_mode(q, cl, &diff);
715 if (old_mode != cl->cmode) {
716 if (old_mode != HTB_CAN_SEND)
717 htb_safe_rb_erase(&cl->pq_node, &q->hlevel[cl->level].wait_pq);
718 if (cl->cmode != HTB_CAN_SEND)
719 htb_add_to_wait_tree(q, cl, diff);
720 }
721
722 /* update basic stats except for leaves which are already updated */
723 if (cl->level)
724 bstats_update(&cl->bstats, skb);
725
726 cl = cl->parent;
727 }
728}
729
730/**
731 * htb_do_events - make mode changes to classes at the level
732 * @q: the priority event queue
733 * @level: which wait_pq in 'q->hlevel'
734 * @start: start jiffies
735 *
736 * Scans event queue for pending events and applies them. Returns time of
737 * next pending event (0 for no event in pq, q->now for too many events).
738 * Note: Applied are events whose have cl->pq_key <= q->now.
739 */
740static s64 htb_do_events(struct htb_sched *q, const int level,
741 unsigned long start)
742{
743 /* don't run for longer than 2 jiffies; 2 is used instead of
744 * 1 to simplify things when jiffy is going to be incremented
745 * too soon
746 */
747 unsigned long stop_at = start + 2;
748 struct rb_root *wait_pq = &q->hlevel[level].wait_pq;
749
750 while (time_before(jiffies, stop_at)) {
751 struct htb_class *cl;
752 s64 diff;
753 struct rb_node *p = rb_first(wait_pq);
754
755 if (!p)
756 return 0;
757
758 cl = rb_entry(p, struct htb_class, pq_node);
759 if (cl->pq_key > q->now)
760 return cl->pq_key;
761
762 htb_safe_rb_erase(p, wait_pq);
763 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
764 htb_change_class_mode(q, cl, &diff);
765 if (cl->cmode != HTB_CAN_SEND)
766 htb_add_to_wait_tree(q, cl, diff);
767 }
768
769 /* too much load - let's continue after a break for scheduling */
770 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
771 pr_warn("htb: too many events!\n");
772 q->warned |= HTB_WARN_TOOMANYEVENTS;
773 }
774
775 return q->now;
776}
777
778/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
779 * is no such one exists.
780 */
781static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
782 u32 id)
783{
784 struct rb_node *r = NULL;
785 while (n) {
786 struct htb_class *cl =
787 rb_entry(n, struct htb_class, node[prio]);
788
789 if (id > cl->common.classid) {
790 n = n->rb_right;
791 } else if (id < cl->common.classid) {
792 r = n;
793 n = n->rb_left;
794 } else {
795 return n;
796 }
797 }
798 return r;
799}
800
801/**
802 * htb_lookup_leaf - returns next leaf class in DRR order
803 * @hprio: the current one
804 * @prio: which prio in class
805 *
806 * Find leaf where current feed pointers points to.
807 */
808static struct htb_class *htb_lookup_leaf(struct htb_prio *hprio, const int prio)
809{
810 int i;
811 struct {
812 struct rb_node *root;
813 struct rb_node **pptr;
814 u32 *pid;
815 } stk[TC_HTB_MAXDEPTH], *sp = stk;
816
817 BUG_ON(!hprio->row.rb_node);
818 sp->root = hprio->row.rb_node;
819 sp->pptr = &hprio->ptr;
820 sp->pid = &hprio->last_ptr_id;
821
822 for (i = 0; i < 65535; i++) {
823 if (!*sp->pptr && *sp->pid) {
824 /* ptr was invalidated but id is valid - try to recover
825 * the original or next ptr
826 */
827 *sp->pptr =
828 htb_id_find_next_upper(prio, sp->root, *sp->pid);
829 }
830 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
831 * can become out of date quickly
832 */
833 if (!*sp->pptr) { /* we are at right end; rewind & go up */
834 *sp->pptr = sp->root;
835 while ((*sp->pptr)->rb_left)
836 *sp->pptr = (*sp->pptr)->rb_left;
837 if (sp > stk) {
838 sp--;
839 if (!*sp->pptr) {
840 WARN_ON(1);
841 return NULL;
842 }
843 htb_next_rb_node(sp->pptr);
844 }
845 } else {
846 struct htb_class *cl;
847 struct htb_prio *clp;
848
849 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
850 if (!cl->level)
851 return cl;
852 clp = &cl->inner.clprio[prio];
853 (++sp)->root = clp->feed.rb_node;
854 sp->pptr = &clp->ptr;
855 sp->pid = &clp->last_ptr_id;
856 }
857 }
858 WARN_ON(1);
859 return NULL;
860}
861
862/* dequeues packet at given priority and level; call only if
863 * you are sure that there is active class at prio/level
864 */
865static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, const int prio,
866 const int level)
867{
868 struct sk_buff *skb = NULL;
869 struct htb_class *cl, *start;
870 struct htb_level *hlevel = &q->hlevel[level];
871 struct htb_prio *hprio = &hlevel->hprio[prio];
872
873 /* look initial class up in the row */
874 start = cl = htb_lookup_leaf(hprio, prio);
875
876 do {
877next:
878 if (unlikely(!cl))
879 return NULL;
880
881 /* class can be empty - it is unlikely but can be true if leaf
882 * qdisc drops packets in enqueue routine or if someone used
883 * graft operation on the leaf since last dequeue;
884 * simply deactivate and skip such class
885 */
886 if (unlikely(cl->leaf.q->q.qlen == 0)) {
887 struct htb_class *next;
888 htb_deactivate(q, cl);
889
890 /* row/level might become empty */
891 if ((q->row_mask[level] & (1 << prio)) == 0)
892 return NULL;
893
894 next = htb_lookup_leaf(hprio, prio);
895
896 if (cl == start) /* fix start if we just deleted it */
897 start = next;
898 cl = next;
899 goto next;
900 }
901
902 skb = cl->leaf.q->dequeue(cl->leaf.q);
903 if (likely(skb != NULL))
904 break;
905
906 qdisc_warn_nonwc("htb", cl->leaf.q);
907 htb_next_rb_node(level ? &cl->parent->inner.clprio[prio].ptr:
908 &q->hlevel[0].hprio[prio].ptr);
909 cl = htb_lookup_leaf(hprio, prio);
910
911 } while (cl != start);
912
913 if (likely(skb != NULL)) {
914 bstats_update(&cl->bstats, skb);
915 cl->leaf.deficit[level] -= qdisc_pkt_len(skb);
916 if (cl->leaf.deficit[level] < 0) {
917 cl->leaf.deficit[level] += cl->quantum;
918 htb_next_rb_node(level ? &cl->parent->inner.clprio[prio].ptr :
919 &q->hlevel[0].hprio[prio].ptr);
920 }
921 /* this used to be after charge_class but this constelation
922 * gives us slightly better performance
923 */
924 if (!cl->leaf.q->q.qlen)
925 htb_deactivate(q, cl);
926 htb_charge_class(q, cl, level, skb);
927 }
928 return skb;
929}
930
931static struct sk_buff *htb_dequeue(struct Qdisc *sch)
932{
933 struct sk_buff *skb;
934 struct htb_sched *q = qdisc_priv(sch);
935 int level;
936 s64 next_event;
937 unsigned long start_at;
938
939 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
940 skb = __qdisc_dequeue_head(&q->direct_queue);
941 if (skb != NULL) {
942ok:
943 qdisc_bstats_update(sch, skb);
944 qdisc_qstats_backlog_dec(sch, skb);
945 sch->q.qlen--;
946 return skb;
947 }
948
949 if (!sch->q.qlen)
950 goto fin;
951 q->now = ktime_get_ns();
952 start_at = jiffies;
953
954 next_event = q->now + 5LLU * NSEC_PER_SEC;
955
956 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
957 /* common case optimization - skip event handler quickly */
958 int m;
959 s64 event = q->near_ev_cache[level];
960
961 if (q->now >= event) {
962 event = htb_do_events(q, level, start_at);
963 if (!event)
964 event = q->now + NSEC_PER_SEC;
965 q->near_ev_cache[level] = event;
966 }
967
968 if (next_event > event)
969 next_event = event;
970
971 m = ~q->row_mask[level];
972 while (m != (int)(-1)) {
973 int prio = ffz(m);
974
975 m |= 1 << prio;
976 skb = htb_dequeue_tree(q, prio, level);
977 if (likely(skb != NULL))
978 goto ok;
979 }
980 }
981 if (likely(next_event > q->now))
982 qdisc_watchdog_schedule_ns(&q->watchdog, next_event);
983 else
984 schedule_work(&q->work);
985fin:
986 return skb;
987}
988
989/* reset all classes */
990/* always caled under BH & queue lock */
991static void htb_reset(struct Qdisc *sch)
992{
993 struct htb_sched *q = qdisc_priv(sch);
994 struct htb_class *cl;
995 unsigned int i;
996
997 for (i = 0; i < q->clhash.hashsize; i++) {
998 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
999 if (cl->level)
1000 memset(&cl->inner, 0, sizeof(cl->inner));
1001 else {
1002 if (cl->leaf.q && !q->offload)
1003 qdisc_reset(cl->leaf.q);
1004 }
1005 cl->prio_activity = 0;
1006 cl->cmode = HTB_CAN_SEND;
1007 }
1008 }
1009 qdisc_watchdog_cancel(&q->watchdog);
1010 __qdisc_reset_queue(&q->direct_queue);
1011 sch->q.qlen = 0;
1012 sch->qstats.backlog = 0;
1013 memset(q->hlevel, 0, sizeof(q->hlevel));
1014 memset(q->row_mask, 0, sizeof(q->row_mask));
1015}
1016
1017static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
1018 [TCA_HTB_PARMS] = { .len = sizeof(struct tc_htb_opt) },
1019 [TCA_HTB_INIT] = { .len = sizeof(struct tc_htb_glob) },
1020 [TCA_HTB_CTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1021 [TCA_HTB_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1022 [TCA_HTB_DIRECT_QLEN] = { .type = NLA_U32 },
1023 [TCA_HTB_RATE64] = { .type = NLA_U64 },
1024 [TCA_HTB_CEIL64] = { .type = NLA_U64 },
1025 [TCA_HTB_OFFLOAD] = { .type = NLA_FLAG },
1026};
1027
1028static void htb_work_func(struct work_struct *work)
1029{
1030 struct htb_sched *q = container_of(work, struct htb_sched, work);
1031 struct Qdisc *sch = q->watchdog.qdisc;
1032
1033 rcu_read_lock();
1034 __netif_schedule(qdisc_root(sch));
1035 rcu_read_unlock();
1036}
1037
1038static void htb_set_lockdep_class_child(struct Qdisc *q)
1039{
1040 static struct lock_class_key child_key;
1041
1042 lockdep_set_class(qdisc_lock(q), &child_key);
1043}
1044
1045static int htb_offload(struct net_device *dev, struct tc_htb_qopt_offload *opt)
1046{
1047 return dev->netdev_ops->ndo_setup_tc(dev, TC_SETUP_QDISC_HTB, opt);
1048}
1049
1050static int htb_init(struct Qdisc *sch, struct nlattr *opt,
1051 struct netlink_ext_ack *extack)
1052{
1053 struct net_device *dev = qdisc_dev(sch);
1054 struct tc_htb_qopt_offload offload_opt;
1055 struct htb_sched *q = qdisc_priv(sch);
1056 struct nlattr *tb[TCA_HTB_MAX + 1];
1057 struct tc_htb_glob *gopt;
1058 unsigned int ntx;
1059 bool offload;
1060 int err;
1061
1062 qdisc_watchdog_init(&q->watchdog, sch);
1063 INIT_WORK(&q->work, htb_work_func);
1064
1065 if (!opt)
1066 return -EINVAL;
1067
1068 err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
1069 if (err)
1070 return err;
1071
1072 err = nla_parse_nested_deprecated(tb, TCA_HTB_MAX, opt, htb_policy,
1073 NULL);
1074 if (err < 0)
1075 return err;
1076
1077 if (!tb[TCA_HTB_INIT])
1078 return -EINVAL;
1079
1080 gopt = nla_data(tb[TCA_HTB_INIT]);
1081 if (gopt->version != HTB_VER >> 16)
1082 return -EINVAL;
1083
1084 offload = nla_get_flag(tb[TCA_HTB_OFFLOAD]);
1085
1086 if (offload) {
1087 if (sch->parent != TC_H_ROOT)
1088 return -EOPNOTSUPP;
1089
1090 if (!tc_can_offload(dev) || !dev->netdev_ops->ndo_setup_tc)
1091 return -EOPNOTSUPP;
1092
1093 q->num_direct_qdiscs = dev->real_num_tx_queues;
1094 q->direct_qdiscs = kcalloc(q->num_direct_qdiscs,
1095 sizeof(*q->direct_qdiscs),
1096 GFP_KERNEL);
1097 if (!q->direct_qdiscs)
1098 return -ENOMEM;
1099 }
1100
1101 err = qdisc_class_hash_init(&q->clhash);
1102 if (err < 0)
1103 goto err_free_direct_qdiscs;
1104
1105 qdisc_skb_head_init(&q->direct_queue);
1106
1107 if (tb[TCA_HTB_DIRECT_QLEN])
1108 q->direct_qlen = nla_get_u32(tb[TCA_HTB_DIRECT_QLEN]);
1109 else
1110 q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
1111
1112 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1113 q->rate2quantum = 1;
1114 q->defcls = gopt->defcls;
1115
1116 if (!offload)
1117 return 0;
1118
1119 for (ntx = 0; ntx < q->num_direct_qdiscs; ntx++) {
1120 struct netdev_queue *dev_queue = netdev_get_tx_queue(dev, ntx);
1121 struct Qdisc *qdisc;
1122
1123 qdisc = qdisc_create_dflt(dev_queue, &pfifo_qdisc_ops,
1124 TC_H_MAKE(sch->handle, 0), extack);
1125 if (!qdisc) {
1126 err = -ENOMEM;
1127 goto err_free_qdiscs;
1128 }
1129
1130 htb_set_lockdep_class_child(qdisc);
1131 q->direct_qdiscs[ntx] = qdisc;
1132 qdisc->flags |= TCQ_F_ONETXQUEUE | TCQ_F_NOPARENT;
1133 }
1134
1135 sch->flags |= TCQ_F_MQROOT;
1136
1137 offload_opt = (struct tc_htb_qopt_offload) {
1138 .command = TC_HTB_CREATE,
1139 .parent_classid = TC_H_MAJ(sch->handle) >> 16,
1140 .classid = TC_H_MIN(q->defcls),
1141 .extack = extack,
1142 };
1143 err = htb_offload(dev, &offload_opt);
1144 if (err)
1145 goto err_free_qdiscs;
1146
1147 /* Defer this assignment, so that htb_destroy skips offload-related
1148 * parts (especially calling ndo_setup_tc) on errors.
1149 */
1150 q->offload = true;
1151
1152 return 0;
1153
1154err_free_qdiscs:
1155 for (ntx = 0; ntx < q->num_direct_qdiscs && q->direct_qdiscs[ntx];
1156 ntx++)
1157 qdisc_put(q->direct_qdiscs[ntx]);
1158
1159 qdisc_class_hash_destroy(&q->clhash);
1160 /* Prevent use-after-free and double-free when htb_destroy gets called.
1161 */
1162 q->clhash.hash = NULL;
1163 q->clhash.hashsize = 0;
1164
1165err_free_direct_qdiscs:
1166 kfree(q->direct_qdiscs);
1167 q->direct_qdiscs = NULL;
1168 return err;
1169}
1170
1171static void htb_attach_offload(struct Qdisc *sch)
1172{
1173 struct net_device *dev = qdisc_dev(sch);
1174 struct htb_sched *q = qdisc_priv(sch);
1175 unsigned int ntx;
1176
1177 for (ntx = 0; ntx < q->num_direct_qdiscs; ntx++) {
1178 struct Qdisc *old, *qdisc = q->direct_qdiscs[ntx];
1179
1180 old = dev_graft_qdisc(qdisc->dev_queue, qdisc);
1181 qdisc_put(old);
1182 qdisc_hash_add(qdisc, false);
1183 }
1184 for (ntx = q->num_direct_qdiscs; ntx < dev->num_tx_queues; ntx++) {
1185 struct netdev_queue *dev_queue = netdev_get_tx_queue(dev, ntx);
1186 struct Qdisc *old = dev_graft_qdisc(dev_queue, NULL);
1187
1188 qdisc_put(old);
1189 }
1190
1191 kfree(q->direct_qdiscs);
1192 q->direct_qdiscs = NULL;
1193}
1194
1195static void htb_attach_software(struct Qdisc *sch)
1196{
1197 struct net_device *dev = qdisc_dev(sch);
1198 unsigned int ntx;
1199
1200 /* Resemble qdisc_graft behavior. */
1201 for (ntx = 0; ntx < dev->num_tx_queues; ntx++) {
1202 struct netdev_queue *dev_queue = netdev_get_tx_queue(dev, ntx);
1203 struct Qdisc *old = dev_graft_qdisc(dev_queue, sch);
1204
1205 qdisc_refcount_inc(sch);
1206
1207 qdisc_put(old);
1208 }
1209}
1210
1211static void htb_attach(struct Qdisc *sch)
1212{
1213 struct htb_sched *q = qdisc_priv(sch);
1214
1215 if (q->offload)
1216 htb_attach_offload(sch);
1217 else
1218 htb_attach_software(sch);
1219}
1220
1221static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1222{
1223 struct htb_sched *q = qdisc_priv(sch);
1224 struct nlattr *nest;
1225 struct tc_htb_glob gopt;
1226
1227 if (q->offload)
1228 sch->flags |= TCQ_F_OFFLOADED;
1229 else
1230 sch->flags &= ~TCQ_F_OFFLOADED;
1231
1232 sch->qstats.overlimits = q->overlimits;
1233 /* Its safe to not acquire qdisc lock. As we hold RTNL,
1234 * no change can happen on the qdisc parameters.
1235 */
1236
1237 gopt.direct_pkts = q->direct_pkts;
1238 gopt.version = HTB_VER;
1239 gopt.rate2quantum = q->rate2quantum;
1240 gopt.defcls = q->defcls;
1241 gopt.debug = 0;
1242
1243 nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
1244 if (nest == NULL)
1245 goto nla_put_failure;
1246 if (nla_put(skb, TCA_HTB_INIT, sizeof(gopt), &gopt) ||
1247 nla_put_u32(skb, TCA_HTB_DIRECT_QLEN, q->direct_qlen))
1248 goto nla_put_failure;
1249 if (q->offload && nla_put_flag(skb, TCA_HTB_OFFLOAD))
1250 goto nla_put_failure;
1251
1252 return nla_nest_end(skb, nest);
1253
1254nla_put_failure:
1255 nla_nest_cancel(skb, nest);
1256 return -1;
1257}
1258
1259static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
1260 struct sk_buff *skb, struct tcmsg *tcm)
1261{
1262 struct htb_class *cl = (struct htb_class *)arg;
1263 struct htb_sched *q = qdisc_priv(sch);
1264 struct nlattr *nest;
1265 struct tc_htb_opt opt;
1266
1267 /* Its safe to not acquire qdisc lock. As we hold RTNL,
1268 * no change can happen on the class parameters.
1269 */
1270 tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
1271 tcm->tcm_handle = cl->common.classid;
1272 if (!cl->level && cl->leaf.q)
1273 tcm->tcm_info = cl->leaf.q->handle;
1274
1275 nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
1276 if (nest == NULL)
1277 goto nla_put_failure;
1278
1279 memset(&opt, 0, sizeof(opt));
1280
1281 psched_ratecfg_getrate(&opt.rate, &cl->rate);
1282 opt.buffer = PSCHED_NS2TICKS(cl->buffer);
1283 psched_ratecfg_getrate(&opt.ceil, &cl->ceil);
1284 opt.cbuffer = PSCHED_NS2TICKS(cl->cbuffer);
1285 opt.quantum = cl->quantum;
1286 opt.prio = cl->prio;
1287 opt.level = cl->level;
1288 if (nla_put(skb, TCA_HTB_PARMS, sizeof(opt), &opt))
1289 goto nla_put_failure;
1290 if (q->offload && nla_put_flag(skb, TCA_HTB_OFFLOAD))
1291 goto nla_put_failure;
1292 if ((cl->rate.rate_bytes_ps >= (1ULL << 32)) &&
1293 nla_put_u64_64bit(skb, TCA_HTB_RATE64, cl->rate.rate_bytes_ps,
1294 TCA_HTB_PAD))
1295 goto nla_put_failure;
1296 if ((cl->ceil.rate_bytes_ps >= (1ULL << 32)) &&
1297 nla_put_u64_64bit(skb, TCA_HTB_CEIL64, cl->ceil.rate_bytes_ps,
1298 TCA_HTB_PAD))
1299 goto nla_put_failure;
1300
1301 return nla_nest_end(skb, nest);
1302
1303nla_put_failure:
1304 nla_nest_cancel(skb, nest);
1305 return -1;
1306}
1307
1308static void htb_offload_aggregate_stats(struct htb_sched *q,
1309 struct htb_class *cl)
1310{
1311 struct htb_class *c;
1312 unsigned int i;
1313
1314 memset(&cl->bstats, 0, sizeof(cl->bstats));
1315
1316 for (i = 0; i < q->clhash.hashsize; i++) {
1317 hlist_for_each_entry(c, &q->clhash.hash[i], common.hnode) {
1318 struct htb_class *p = c;
1319
1320 while (p && p->level < cl->level)
1321 p = p->parent;
1322
1323 if (p != cl)
1324 continue;
1325
1326 cl->bstats.bytes += c->bstats_bias.bytes;
1327 cl->bstats.packets += c->bstats_bias.packets;
1328 if (c->level == 0) {
1329 cl->bstats.bytes += c->leaf.q->bstats.bytes;
1330 cl->bstats.packets += c->leaf.q->bstats.packets;
1331 }
1332 }
1333 }
1334}
1335
1336static int
1337htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
1338{
1339 struct htb_class *cl = (struct htb_class *)arg;
1340 struct htb_sched *q = qdisc_priv(sch);
1341 struct gnet_stats_queue qs = {
1342 .drops = cl->drops,
1343 .overlimits = cl->overlimits,
1344 };
1345 __u32 qlen = 0;
1346
1347 if (!cl->level && cl->leaf.q)
1348 qdisc_qstats_qlen_backlog(cl->leaf.q, &qlen, &qs.backlog);
1349
1350 cl->xstats.tokens = clamp_t(s64, PSCHED_NS2TICKS(cl->tokens),
1351 INT_MIN, INT_MAX);
1352 cl->xstats.ctokens = clamp_t(s64, PSCHED_NS2TICKS(cl->ctokens),
1353 INT_MIN, INT_MAX);
1354
1355 if (q->offload) {
1356 if (!cl->level) {
1357 if (cl->leaf.q)
1358 cl->bstats = cl->leaf.q->bstats;
1359 else
1360 memset(&cl->bstats, 0, sizeof(cl->bstats));
1361 cl->bstats.bytes += cl->bstats_bias.bytes;
1362 cl->bstats.packets += cl->bstats_bias.packets;
1363 } else {
1364 htb_offload_aggregate_stats(q, cl);
1365 }
1366 }
1367
1368 if (gnet_stats_copy_basic(qdisc_root_sleeping_running(sch),
1369 d, NULL, &cl->bstats) < 0 ||
1370 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1371 gnet_stats_copy_queue(d, NULL, &qs, qlen) < 0)
1372 return -1;
1373
1374 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1375}
1376
1377static struct netdev_queue *
1378htb_select_queue(struct Qdisc *sch, struct tcmsg *tcm)
1379{
1380 struct net_device *dev = qdisc_dev(sch);
1381 struct tc_htb_qopt_offload offload_opt;
1382 struct htb_sched *q = qdisc_priv(sch);
1383 int err;
1384
1385 if (!q->offload)
1386 return sch->dev_queue;
1387
1388 offload_opt = (struct tc_htb_qopt_offload) {
1389 .command = TC_HTB_LEAF_QUERY_QUEUE,
1390 .classid = TC_H_MIN(tcm->tcm_parent),
1391 };
1392 err = htb_offload(dev, &offload_opt);
1393 if (err || offload_opt.qid >= dev->num_tx_queues)
1394 return NULL;
1395 return netdev_get_tx_queue(dev, offload_opt.qid);
1396}
1397
1398static struct Qdisc *
1399htb_graft_helper(struct netdev_queue *dev_queue, struct Qdisc *new_q)
1400{
1401 struct net_device *dev = dev_queue->dev;
1402 struct Qdisc *old_q;
1403
1404 if (dev->flags & IFF_UP)
1405 dev_deactivate(dev);
1406 old_q = dev_graft_qdisc(dev_queue, new_q);
1407 if (new_q)
1408 new_q->flags |= TCQ_F_ONETXQUEUE | TCQ_F_NOPARENT;
1409 if (dev->flags & IFF_UP)
1410 dev_activate(dev);
1411
1412 return old_q;
1413}
1414
1415static struct netdev_queue *htb_offload_get_queue(struct htb_class *cl)
1416{
1417 struct netdev_queue *queue;
1418
1419 queue = cl->leaf.offload_queue;
1420 if (!(cl->leaf.q->flags & TCQ_F_BUILTIN))
1421 WARN_ON(cl->leaf.q->dev_queue != queue);
1422
1423 return queue;
1424}
1425
1426static void htb_offload_move_qdisc(struct Qdisc *sch, struct htb_class *cl_old,
1427 struct htb_class *cl_new, bool destroying)
1428{
1429 struct netdev_queue *queue_old, *queue_new;
1430 struct net_device *dev = qdisc_dev(sch);
1431
1432 queue_old = htb_offload_get_queue(cl_old);
1433 queue_new = htb_offload_get_queue(cl_new);
1434
1435 if (!destroying) {
1436 struct Qdisc *qdisc;
1437
1438 if (dev->flags & IFF_UP)
1439 dev_deactivate(dev);
1440 qdisc = dev_graft_qdisc(queue_old, NULL);
1441 WARN_ON(qdisc != cl_old->leaf.q);
1442 }
1443
1444 if (!(cl_old->leaf.q->flags & TCQ_F_BUILTIN))
1445 cl_old->leaf.q->dev_queue = queue_new;
1446 cl_old->leaf.offload_queue = queue_new;
1447
1448 if (!destroying) {
1449 struct Qdisc *qdisc;
1450
1451 qdisc = dev_graft_qdisc(queue_new, cl_old->leaf.q);
1452 if (dev->flags & IFF_UP)
1453 dev_activate(dev);
1454 WARN_ON(!(qdisc->flags & TCQ_F_BUILTIN));
1455 }
1456}
1457
1458static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1459 struct Qdisc **old, struct netlink_ext_ack *extack)
1460{
1461 struct netdev_queue *dev_queue = sch->dev_queue;
1462 struct htb_class *cl = (struct htb_class *)arg;
1463 struct htb_sched *q = qdisc_priv(sch);
1464 struct Qdisc *old_q;
1465
1466 if (cl->level)
1467 return -EINVAL;
1468
1469 if (q->offload)
1470 dev_queue = htb_offload_get_queue(cl);
1471
1472 if (!new) {
1473 new = qdisc_create_dflt(dev_queue, &pfifo_qdisc_ops,
1474 cl->common.classid, extack);
1475 if (!new)
1476 return -ENOBUFS;
1477 }
1478
1479 if (q->offload) {
1480 htb_set_lockdep_class_child(new);
1481 /* One ref for cl->leaf.q, the other for dev_queue->qdisc. */
1482 qdisc_refcount_inc(new);
1483 old_q = htb_graft_helper(dev_queue, new);
1484 }
1485
1486 *old = qdisc_replace(sch, new, &cl->leaf.q);
1487
1488 if (q->offload) {
1489 WARN_ON(old_q != *old);
1490 qdisc_put(old_q);
1491 }
1492
1493 return 0;
1494}
1495
1496static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
1497{
1498 struct htb_class *cl = (struct htb_class *)arg;
1499 return !cl->level ? cl->leaf.q : NULL;
1500}
1501
1502static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
1503{
1504 struct htb_class *cl = (struct htb_class *)arg;
1505
1506 htb_deactivate(qdisc_priv(sch), cl);
1507}
1508
1509static inline int htb_parent_last_child(struct htb_class *cl)
1510{
1511 if (!cl->parent)
1512 /* the root class */
1513 return 0;
1514 if (cl->parent->children > 1)
1515 /* not the last child */
1516 return 0;
1517 return 1;
1518}
1519
1520static void htb_parent_to_leaf(struct Qdisc *sch, struct htb_class *cl,
1521 struct Qdisc *new_q)
1522{
1523 struct htb_sched *q = qdisc_priv(sch);
1524 struct htb_class *parent = cl->parent;
1525
1526 WARN_ON(cl->level || !cl->leaf.q || cl->prio_activity);
1527
1528 if (parent->cmode != HTB_CAN_SEND)
1529 htb_safe_rb_erase(&parent->pq_node,
1530 &q->hlevel[parent->level].wait_pq);
1531
1532 parent->level = 0;
1533 memset(&parent->inner, 0, sizeof(parent->inner));
1534 parent->leaf.q = new_q ? new_q : &noop_qdisc;
1535 parent->tokens = parent->buffer;
1536 parent->ctokens = parent->cbuffer;
1537 parent->t_c = ktime_get_ns();
1538 parent->cmode = HTB_CAN_SEND;
1539 if (q->offload)
1540 parent->leaf.offload_queue = cl->leaf.offload_queue;
1541}
1542
1543static void htb_parent_to_leaf_offload(struct Qdisc *sch,
1544 struct netdev_queue *dev_queue,
1545 struct Qdisc *new_q)
1546{
1547 struct Qdisc *old_q;
1548
1549 /* One ref for cl->leaf.q, the other for dev_queue->qdisc. */
1550 if (new_q)
1551 qdisc_refcount_inc(new_q);
1552 old_q = htb_graft_helper(dev_queue, new_q);
1553 WARN_ON(!(old_q->flags & TCQ_F_BUILTIN));
1554}
1555
1556static int htb_destroy_class_offload(struct Qdisc *sch, struct htb_class *cl,
1557 bool last_child, bool destroying,
1558 struct netlink_ext_ack *extack)
1559{
1560 struct tc_htb_qopt_offload offload_opt;
1561 struct netdev_queue *dev_queue;
1562 struct Qdisc *q = cl->leaf.q;
1563 struct Qdisc *old = NULL;
1564 int err;
1565
1566 if (cl->level)
1567 return -EINVAL;
1568
1569 WARN_ON(!q);
1570 dev_queue = htb_offload_get_queue(cl);
1571 old = htb_graft_helper(dev_queue, NULL);
1572 if (destroying)
1573 /* Before HTB is destroyed, the kernel grafts noop_qdisc to
1574 * all queues.
1575 */
1576 WARN_ON(!(old->flags & TCQ_F_BUILTIN));
1577 else
1578 WARN_ON(old != q);
1579
1580 if (cl->parent) {
1581 cl->parent->bstats_bias.bytes += q->bstats.bytes;
1582 cl->parent->bstats_bias.packets += q->bstats.packets;
1583 }
1584
1585 offload_opt = (struct tc_htb_qopt_offload) {
1586 .command = !last_child ? TC_HTB_LEAF_DEL :
1587 destroying ? TC_HTB_LEAF_DEL_LAST_FORCE :
1588 TC_HTB_LEAF_DEL_LAST,
1589 .classid = cl->common.classid,
1590 .extack = extack,
1591 };
1592 err = htb_offload(qdisc_dev(sch), &offload_opt);
1593
1594 if (!err || destroying)
1595 qdisc_put(old);
1596 else
1597 htb_graft_helper(dev_queue, old);
1598
1599 if (last_child)
1600 return err;
1601
1602 if (!err && offload_opt.classid != TC_H_MIN(cl->common.classid)) {
1603 u32 classid = TC_H_MAJ(sch->handle) |
1604 TC_H_MIN(offload_opt.classid);
1605 struct htb_class *moved_cl = htb_find(classid, sch);
1606
1607 htb_offload_move_qdisc(sch, moved_cl, cl, destroying);
1608 }
1609
1610 return err;
1611}
1612
1613static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
1614{
1615 if (!cl->level) {
1616 WARN_ON(!cl->leaf.q);
1617 qdisc_put(cl->leaf.q);
1618 }
1619 gen_kill_estimator(&cl->rate_est);
1620 tcf_block_put(cl->block);
1621 kfree(cl);
1622}
1623
1624static void htb_destroy(struct Qdisc *sch)
1625{
1626 struct net_device *dev = qdisc_dev(sch);
1627 struct tc_htb_qopt_offload offload_opt;
1628 struct htb_sched *q = qdisc_priv(sch);
1629 struct hlist_node *next;
1630 bool nonempty, changed;
1631 struct htb_class *cl;
1632 unsigned int i;
1633
1634 cancel_work_sync(&q->work);
1635 qdisc_watchdog_cancel(&q->watchdog);
1636 /* This line used to be after htb_destroy_class call below
1637 * and surprisingly it worked in 2.4. But it must precede it
1638 * because filter need its target class alive to be able to call
1639 * unbind_filter on it (without Oops).
1640 */
1641 tcf_block_put(q->block);
1642
1643 for (i = 0; i < q->clhash.hashsize; i++) {
1644 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
1645 tcf_block_put(cl->block);
1646 cl->block = NULL;
1647 }
1648 }
1649
1650 do {
1651 nonempty = false;
1652 changed = false;
1653 for (i = 0; i < q->clhash.hashsize; i++) {
1654 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],
1655 common.hnode) {
1656 bool last_child;
1657
1658 if (!q->offload) {
1659 htb_destroy_class(sch, cl);
1660 continue;
1661 }
1662
1663 nonempty = true;
1664
1665 if (cl->level)
1666 continue;
1667
1668 changed = true;
1669
1670 last_child = htb_parent_last_child(cl);
1671 htb_destroy_class_offload(sch, cl, last_child,
1672 true, NULL);
1673 qdisc_class_hash_remove(&q->clhash,
1674 &cl->common);
1675 if (cl->parent)
1676 cl->parent->children--;
1677 if (last_child)
1678 htb_parent_to_leaf(sch, cl, NULL);
1679 htb_destroy_class(sch, cl);
1680 }
1681 }
1682 } while (changed);
1683 WARN_ON(nonempty);
1684
1685 qdisc_class_hash_destroy(&q->clhash);
1686 __qdisc_reset_queue(&q->direct_queue);
1687
1688 if (!q->offload)
1689 return;
1690
1691 offload_opt = (struct tc_htb_qopt_offload) {
1692 .command = TC_HTB_DESTROY,
1693 };
1694 htb_offload(dev, &offload_opt);
1695
1696 if (!q->direct_qdiscs)
1697 return;
1698 for (i = 0; i < q->num_direct_qdiscs && q->direct_qdiscs[i]; i++)
1699 qdisc_put(q->direct_qdiscs[i]);
1700 kfree(q->direct_qdiscs);
1701}
1702
1703static int htb_delete(struct Qdisc *sch, unsigned long arg,
1704 struct netlink_ext_ack *extack)
1705{
1706 struct htb_sched *q = qdisc_priv(sch);
1707 struct htb_class *cl = (struct htb_class *)arg;
1708 struct Qdisc *new_q = NULL;
1709 int last_child = 0;
1710 int err;
1711
1712 /* TODO: why don't allow to delete subtree ? references ? does
1713 * tc subsys guarantee us that in htb_destroy it holds no class
1714 * refs so that we can remove children safely there ?
1715 */
1716 if (cl->children || cl->filter_cnt)
1717 return -EBUSY;
1718
1719 if (!cl->level && htb_parent_last_child(cl))
1720 last_child = 1;
1721
1722 if (q->offload) {
1723 err = htb_destroy_class_offload(sch, cl, last_child, false,
1724 extack);
1725 if (err)
1726 return err;
1727 }
1728
1729 if (last_child) {
1730 struct netdev_queue *dev_queue = sch->dev_queue;
1731
1732 if (q->offload)
1733 dev_queue = htb_offload_get_queue(cl);
1734
1735 new_q = qdisc_create_dflt(dev_queue, &pfifo_qdisc_ops,
1736 cl->parent->common.classid,
1737 NULL);
1738 if (q->offload) {
1739 if (new_q)
1740 htb_set_lockdep_class_child(new_q);
1741 htb_parent_to_leaf_offload(sch, dev_queue, new_q);
1742 }
1743 }
1744
1745 sch_tree_lock(sch);
1746
1747 if (!cl->level)
1748 qdisc_purge_queue(cl->leaf.q);
1749
1750 /* delete from hash and active; remainder in destroy_class */
1751 qdisc_class_hash_remove(&q->clhash, &cl->common);
1752 if (cl->parent)
1753 cl->parent->children--;
1754
1755 if (cl->prio_activity)
1756 htb_deactivate(q, cl);
1757
1758 if (cl->cmode != HTB_CAN_SEND)
1759 htb_safe_rb_erase(&cl->pq_node,
1760 &q->hlevel[cl->level].wait_pq);
1761
1762 if (last_child)
1763 htb_parent_to_leaf(sch, cl, new_q);
1764
1765 sch_tree_unlock(sch);
1766
1767 htb_destroy_class(sch, cl);
1768 return 0;
1769}
1770
1771static int htb_change_class(struct Qdisc *sch, u32 classid,
1772 u32 parentid, struct nlattr **tca,
1773 unsigned long *arg, struct netlink_ext_ack *extack)
1774{
1775 int err = -EINVAL;
1776 struct htb_sched *q = qdisc_priv(sch);
1777 struct htb_class *cl = (struct htb_class *)*arg, *parent;
1778 struct tc_htb_qopt_offload offload_opt;
1779 struct nlattr *opt = tca[TCA_OPTIONS];
1780 struct nlattr *tb[TCA_HTB_MAX + 1];
1781 struct Qdisc *parent_qdisc = NULL;
1782 struct netdev_queue *dev_queue;
1783 struct tc_htb_opt *hopt;
1784 u64 rate64, ceil64;
1785 int warn = 0;
1786
1787 /* extract all subattrs from opt attr */
1788 if (!opt)
1789 goto failure;
1790
1791 err = nla_parse_nested_deprecated(tb, TCA_HTB_MAX, opt, htb_policy,
1792 NULL);
1793 if (err < 0)
1794 goto failure;
1795
1796 err = -EINVAL;
1797 if (tb[TCA_HTB_PARMS] == NULL)
1798 goto failure;
1799
1800 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
1801
1802 hopt = nla_data(tb[TCA_HTB_PARMS]);
1803 if (!hopt->rate.rate || !hopt->ceil.rate)
1804 goto failure;
1805
1806 /* Keeping backward compatible with rate_table based iproute2 tc */
1807 if (hopt->rate.linklayer == TC_LINKLAYER_UNAWARE)
1808 qdisc_put_rtab(qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB],
1809 NULL));
1810
1811 if (hopt->ceil.linklayer == TC_LINKLAYER_UNAWARE)
1812 qdisc_put_rtab(qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB],
1813 NULL));
1814
1815 rate64 = tb[TCA_HTB_RATE64] ? nla_get_u64(tb[TCA_HTB_RATE64]) : 0;
1816 ceil64 = tb[TCA_HTB_CEIL64] ? nla_get_u64(tb[TCA_HTB_CEIL64]) : 0;
1817
1818 if (!cl) { /* new class */
1819 struct net_device *dev = qdisc_dev(sch);
1820 struct Qdisc *new_q, *old_q;
1821 int prio;
1822 struct {
1823 struct nlattr nla;
1824 struct gnet_estimator opt;
1825 } est = {
1826 .nla = {
1827 .nla_len = nla_attr_size(sizeof(est.opt)),
1828 .nla_type = TCA_RATE,
1829 },
1830 .opt = {
1831 /* 4s interval, 16s averaging constant */
1832 .interval = 2,
1833 .ewma_log = 2,
1834 },
1835 };
1836
1837 /* check for valid classid */
1838 if (!classid || TC_H_MAJ(classid ^ sch->handle) ||
1839 htb_find(classid, sch))
1840 goto failure;
1841
1842 /* check maximal depth */
1843 if (parent && parent->parent && parent->parent->level < 2) {
1844 pr_err("htb: tree is too deep\n");
1845 goto failure;
1846 }
1847 err = -ENOBUFS;
1848 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1849 if (!cl)
1850 goto failure;
1851
1852 err = tcf_block_get(&cl->block, &cl->filter_list, sch, extack);
1853 if (err) {
1854 kfree(cl);
1855 goto failure;
1856 }
1857 if (htb_rate_est || tca[TCA_RATE]) {
1858 err = gen_new_estimator(&cl->bstats, NULL,
1859 &cl->rate_est,
1860 NULL,
1861 qdisc_root_sleeping_running(sch),
1862 tca[TCA_RATE] ? : &est.nla);
1863 if (err)
1864 goto err_block_put;
1865 }
1866
1867 cl->children = 0;
1868 RB_CLEAR_NODE(&cl->pq_node);
1869
1870 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1871 RB_CLEAR_NODE(&cl->node[prio]);
1872
1873 cl->common.classid = classid;
1874
1875 /* Make sure nothing interrupts us in between of two
1876 * ndo_setup_tc calls.
1877 */
1878 ASSERT_RTNL();
1879
1880 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
1881 * so that can't be used inside of sch_tree_lock
1882 * -- thanks to Karlis Peisenieks
1883 */
1884 if (!q->offload) {
1885 dev_queue = sch->dev_queue;
1886 } else if (!(parent && !parent->level)) {
1887 /* Assign a dev_queue to this classid. */
1888 offload_opt = (struct tc_htb_qopt_offload) {
1889 .command = TC_HTB_LEAF_ALLOC_QUEUE,
1890 .classid = cl->common.classid,
1891 .parent_classid = parent ?
1892 TC_H_MIN(parent->common.classid) :
1893 TC_HTB_CLASSID_ROOT,
1894 .rate = max_t(u64, hopt->rate.rate, rate64),
1895 .ceil = max_t(u64, hopt->ceil.rate, ceil64),
1896 .extack = extack,
1897 };
1898 err = htb_offload(dev, &offload_opt);
1899 if (err) {
1900 pr_err("htb: TC_HTB_LEAF_ALLOC_QUEUE failed with err = %d\n",
1901 err);
1902 goto err_kill_estimator;
1903 }
1904 dev_queue = netdev_get_tx_queue(dev, offload_opt.qid);
1905 } else { /* First child. */
1906 dev_queue = htb_offload_get_queue(parent);
1907 old_q = htb_graft_helper(dev_queue, NULL);
1908 WARN_ON(old_q != parent->leaf.q);
1909 offload_opt = (struct tc_htb_qopt_offload) {
1910 .command = TC_HTB_LEAF_TO_INNER,
1911 .classid = cl->common.classid,
1912 .parent_classid =
1913 TC_H_MIN(parent->common.classid),
1914 .rate = max_t(u64, hopt->rate.rate, rate64),
1915 .ceil = max_t(u64, hopt->ceil.rate, ceil64),
1916 .extack = extack,
1917 };
1918 err = htb_offload(dev, &offload_opt);
1919 if (err) {
1920 pr_err("htb: TC_HTB_LEAF_TO_INNER failed with err = %d\n",
1921 err);
1922 htb_graft_helper(dev_queue, old_q);
1923 goto err_kill_estimator;
1924 }
1925 parent->bstats_bias.bytes += old_q->bstats.bytes;
1926 parent->bstats_bias.packets += old_q->bstats.packets;
1927 qdisc_put(old_q);
1928 }
1929 new_q = qdisc_create_dflt(dev_queue, &pfifo_qdisc_ops,
1930 classid, NULL);
1931 if (q->offload) {
1932 if (new_q) {
1933 htb_set_lockdep_class_child(new_q);
1934 /* One ref for cl->leaf.q, the other for
1935 * dev_queue->qdisc.
1936 */
1937 qdisc_refcount_inc(new_q);
1938 }
1939 old_q = htb_graft_helper(dev_queue, new_q);
1940 /* No qdisc_put needed. */
1941 WARN_ON(!(old_q->flags & TCQ_F_BUILTIN));
1942 }
1943 sch_tree_lock(sch);
1944 if (parent && !parent->level) {
1945 /* turn parent into inner node */
1946 qdisc_purge_queue(parent->leaf.q);
1947 parent_qdisc = parent->leaf.q;
1948 if (parent->prio_activity)
1949 htb_deactivate(q, parent);
1950
1951 /* remove from evt list because of level change */
1952 if (parent->cmode != HTB_CAN_SEND) {
1953 htb_safe_rb_erase(&parent->pq_node, &q->hlevel[0].wait_pq);
1954 parent->cmode = HTB_CAN_SEND;
1955 }
1956 parent->level = (parent->parent ? parent->parent->level
1957 : TC_HTB_MAXDEPTH) - 1;
1958 memset(&parent->inner, 0, sizeof(parent->inner));
1959 }
1960
1961 /* leaf (we) needs elementary qdisc */
1962 cl->leaf.q = new_q ? new_q : &noop_qdisc;
1963 if (q->offload)
1964 cl->leaf.offload_queue = dev_queue;
1965
1966 cl->parent = parent;
1967
1968 /* set class to be in HTB_CAN_SEND state */
1969 cl->tokens = PSCHED_TICKS2NS(hopt->buffer);
1970 cl->ctokens = PSCHED_TICKS2NS(hopt->cbuffer);
1971 cl->mbuffer = 60ULL * NSEC_PER_SEC; /* 1min */
1972 cl->t_c = ktime_get_ns();
1973 cl->cmode = HTB_CAN_SEND;
1974
1975 /* attach to the hash list and parent's family */
1976 qdisc_class_hash_insert(&q->clhash, &cl->common);
1977 if (parent)
1978 parent->children++;
1979 if (cl->leaf.q != &noop_qdisc)
1980 qdisc_hash_add(cl->leaf.q, true);
1981 } else {
1982 if (tca[TCA_RATE]) {
1983 err = gen_replace_estimator(&cl->bstats, NULL,
1984 &cl->rate_est,
1985 NULL,
1986 qdisc_root_sleeping_running(sch),
1987 tca[TCA_RATE]);
1988 if (err)
1989 return err;
1990 }
1991
1992 if (q->offload) {
1993 struct net_device *dev = qdisc_dev(sch);
1994
1995 offload_opt = (struct tc_htb_qopt_offload) {
1996 .command = TC_HTB_NODE_MODIFY,
1997 .classid = cl->common.classid,
1998 .rate = max_t(u64, hopt->rate.rate, rate64),
1999 .ceil = max_t(u64, hopt->ceil.rate, ceil64),
2000 .extack = extack,
2001 };
2002 err = htb_offload(dev, &offload_opt);
2003 if (err)
2004 /* Estimator was replaced, and rollback may fail
2005 * as well, so we don't try to recover it, and
2006 * the estimator won't work property with the
2007 * offload anyway, because bstats are updated
2008 * only when the stats are queried.
2009 */
2010 return err;
2011 }
2012
2013 sch_tree_lock(sch);
2014 }
2015
2016 psched_ratecfg_precompute(&cl->rate, &hopt->rate, rate64);
2017 psched_ratecfg_precompute(&cl->ceil, &hopt->ceil, ceil64);
2018
2019 /* it used to be a nasty bug here, we have to check that node
2020 * is really leaf before changing cl->leaf !
2021 */
2022 if (!cl->level) {
2023 u64 quantum = cl->rate.rate_bytes_ps;
2024
2025 do_div(quantum, q->rate2quantum);
2026 cl->quantum = min_t(u64, quantum, INT_MAX);
2027
2028 if (!hopt->quantum && cl->quantum < 1000) {
2029 warn = -1;
2030 cl->quantum = 1000;
2031 }
2032 if (!hopt->quantum && cl->quantum > 200000) {
2033 warn = 1;
2034 cl->quantum = 200000;
2035 }
2036 if (hopt->quantum)
2037 cl->quantum = hopt->quantum;
2038 if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO)
2039 cl->prio = TC_HTB_NUMPRIO - 1;
2040 }
2041
2042 cl->buffer = PSCHED_TICKS2NS(hopt->buffer);
2043 cl->cbuffer = PSCHED_TICKS2NS(hopt->cbuffer);
2044
2045 sch_tree_unlock(sch);
2046 qdisc_put(parent_qdisc);
2047
2048 if (warn)
2049 pr_warn("HTB: quantum of class %X is %s. Consider r2q change.\n",
2050 cl->common.classid, (warn == -1 ? "small" : "big"));
2051
2052 qdisc_class_hash_grow(sch, &q->clhash);
2053
2054 *arg = (unsigned long)cl;
2055 return 0;
2056
2057err_kill_estimator:
2058 gen_kill_estimator(&cl->rate_est);
2059err_block_put:
2060 tcf_block_put(cl->block);
2061 kfree(cl);
2062failure:
2063 return err;
2064}
2065
2066static struct tcf_block *htb_tcf_block(struct Qdisc *sch, unsigned long arg,
2067 struct netlink_ext_ack *extack)
2068{
2069 struct htb_sched *q = qdisc_priv(sch);
2070 struct htb_class *cl = (struct htb_class *)arg;
2071
2072 return cl ? cl->block : q->block;
2073}
2074
2075static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
2076 u32 classid)
2077{
2078 struct htb_class *cl = htb_find(classid, sch);
2079
2080 /*if (cl && !cl->level) return 0;
2081 * The line above used to be there to prevent attaching filters to
2082 * leaves. But at least tc_index filter uses this just to get class
2083 * for other reasons so that we have to allow for it.
2084 * ----
2085 * 19.6.2002 As Werner explained it is ok - bind filter is just
2086 * another way to "lock" the class - unlike "get" this lock can
2087 * be broken by class during destroy IIUC.
2088 */
2089 if (cl)
2090 cl->filter_cnt++;
2091 return (unsigned long)cl;
2092}
2093
2094static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
2095{
2096 struct htb_class *cl = (struct htb_class *)arg;
2097
2098 if (cl)
2099 cl->filter_cnt--;
2100}
2101
2102static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2103{
2104 struct htb_sched *q = qdisc_priv(sch);
2105 struct htb_class *cl;
2106 unsigned int i;
2107
2108 if (arg->stop)
2109 return;
2110
2111 for (i = 0; i < q->clhash.hashsize; i++) {
2112 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
2113 if (arg->count < arg->skip) {
2114 arg->count++;
2115 continue;
2116 }
2117 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2118 arg->stop = 1;
2119 return;
2120 }
2121 arg->count++;
2122 }
2123 }
2124}
2125
2126static const struct Qdisc_class_ops htb_class_ops = {
2127 .select_queue = htb_select_queue,
2128 .graft = htb_graft,
2129 .leaf = htb_leaf,
2130 .qlen_notify = htb_qlen_notify,
2131 .find = htb_search,
2132 .change = htb_change_class,
2133 .delete = htb_delete,
2134 .walk = htb_walk,
2135 .tcf_block = htb_tcf_block,
2136 .bind_tcf = htb_bind_filter,
2137 .unbind_tcf = htb_unbind_filter,
2138 .dump = htb_dump_class,
2139 .dump_stats = htb_dump_class_stats,
2140};
2141
2142static struct Qdisc_ops htb_qdisc_ops __read_mostly = {
2143 .cl_ops = &htb_class_ops,
2144 .id = "htb",
2145 .priv_size = sizeof(struct htb_sched),
2146 .enqueue = htb_enqueue,
2147 .dequeue = htb_dequeue,
2148 .peek = qdisc_peek_dequeued,
2149 .init = htb_init,
2150 .attach = htb_attach,
2151 .reset = htb_reset,
2152 .destroy = htb_destroy,
2153 .dump = htb_dump,
2154 .owner = THIS_MODULE,
2155};
2156
2157static int __init htb_module_init(void)
2158{
2159 return register_qdisc(&htb_qdisc_ops);
2160}
2161static void __exit htb_module_exit(void)
2162{
2163 unregister_qdisc(&htb_qdisc_ops);
2164}
2165
2166module_init(htb_module_init)
2167module_exit(htb_module_exit)
2168MODULE_LICENSE("GPL");