Loading...
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 suplied 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 tc_htb_xstats xstats; /* our special stats */
118
119 /* token bucket parameters */
120 s64 tokens, ctokens;/* current number of tokens */
121 s64 t_c; /* checkpoint time */
122
123 union {
124 struct htb_class_leaf {
125 int deficit[TC_HTB_MAXDEPTH];
126 struct Qdisc *q;
127 } leaf;
128 struct htb_class_inner {
129 struct htb_prio clprio[TC_HTB_NUMPRIO];
130 } inner;
131 };
132 s64 pq_key;
133
134 int prio_activity; /* for which prios are we active */
135 enum htb_cmode cmode; /* current mode of the class */
136 struct rb_node pq_node; /* node for event queue */
137 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
138
139 unsigned int drops ____cacheline_aligned_in_smp;
140 unsigned int overlimits;
141};
142
143struct htb_level {
144 struct rb_root wait_pq;
145 struct htb_prio hprio[TC_HTB_NUMPRIO];
146};
147
148struct htb_sched {
149 struct Qdisc_class_hash clhash;
150 int defcls; /* class where unclassified flows go to */
151 int rate2quantum; /* quant = rate / rate2quantum */
152
153 /* filters for qdisc itself */
154 struct tcf_proto __rcu *filter_list;
155 struct tcf_block *block;
156
157#define HTB_WARN_TOOMANYEVENTS 0x1
158 unsigned int warned; /* only one warning */
159 int direct_qlen;
160 struct work_struct work;
161
162 /* non shaped skbs; let them go directly thru */
163 struct qdisc_skb_head direct_queue;
164 u32 direct_pkts;
165 u32 overlimits;
166
167 struct qdisc_watchdog watchdog;
168
169 s64 now; /* cached dequeue time */
170
171 /* time of nearest event per level (row) */
172 s64 near_ev_cache[TC_HTB_MAXDEPTH];
173
174 int row_mask[TC_HTB_MAXDEPTH];
175
176 struct htb_level hlevel[TC_HTB_MAXDEPTH];
177};
178
179/* find class in global hash table using given handle */
180static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
181{
182 struct htb_sched *q = qdisc_priv(sch);
183 struct Qdisc_class_common *clc;
184
185 clc = qdisc_class_find(&q->clhash, handle);
186 if (clc == NULL)
187 return NULL;
188 return container_of(clc, struct htb_class, common);
189}
190
191static unsigned long htb_search(struct Qdisc *sch, u32 handle)
192{
193 return (unsigned long)htb_find(handle, sch);
194}
195/**
196 * htb_classify - classify a packet into class
197 *
198 * It returns NULL if the packet should be dropped or -1 if the packet
199 * should be passed directly thru. In all other cases leaf class is returned.
200 * We allow direct class selection by classid in priority. The we examine
201 * filters in qdisc and in inner nodes (if higher filter points to the inner
202 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
203 * internal fifo (direct). These packets then go directly thru. If we still
204 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessful
205 * then finish and return direct queue.
206 */
207#define HTB_DIRECT ((struct htb_class *)-1L)
208
209static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
210 int *qerr)
211{
212 struct htb_sched *q = qdisc_priv(sch);
213 struct htb_class *cl;
214 struct tcf_result res;
215 struct tcf_proto *tcf;
216 int result;
217
218 /* allow to select class by setting skb->priority to valid classid;
219 * note that nfmark can be used too by attaching filter fw with no
220 * rules in it
221 */
222 if (skb->priority == sch->handle)
223 return HTB_DIRECT; /* X:0 (direct flow) selected */
224 cl = htb_find(skb->priority, sch);
225 if (cl) {
226 if (cl->level == 0)
227 return cl;
228 /* Start with inner filter chain if a non-leaf class is selected */
229 tcf = rcu_dereference_bh(cl->filter_list);
230 } else {
231 tcf = rcu_dereference_bh(q->filter_list);
232 }
233
234 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
235 while (tcf && (result = tcf_classify(skb, tcf, &res, false)) >= 0) {
236#ifdef CONFIG_NET_CLS_ACT
237 switch (result) {
238 case TC_ACT_QUEUED:
239 case TC_ACT_STOLEN:
240 case TC_ACT_TRAP:
241 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
242 /* fall through */
243 case TC_ACT_SHOT:
244 return NULL;
245 }
246#endif
247 cl = (void *)res.class;
248 if (!cl) {
249 if (res.classid == sch->handle)
250 return HTB_DIRECT; /* X:0 (direct flow) */
251 cl = htb_find(res.classid, sch);
252 if (!cl)
253 break; /* filter selected invalid classid */
254 }
255 if (!cl->level)
256 return cl; /* we hit leaf; return it */
257
258 /* we have got inner class; apply inner filter chain */
259 tcf = rcu_dereference_bh(cl->filter_list);
260 }
261 /* classification failed; try to use default class */
262 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
263 if (!cl || cl->level)
264 return HTB_DIRECT; /* bad default .. this is safe bet */
265 return cl;
266}
267
268/**
269 * htb_add_to_id_tree - adds class to the round robin list
270 *
271 * Routine adds class to the list (actually tree) sorted by classid.
272 * Make sure that class is not already on such list for given prio.
273 */
274static void htb_add_to_id_tree(struct rb_root *root,
275 struct htb_class *cl, int prio)
276{
277 struct rb_node **p = &root->rb_node, *parent = NULL;
278
279 while (*p) {
280 struct htb_class *c;
281 parent = *p;
282 c = rb_entry(parent, struct htb_class, node[prio]);
283
284 if (cl->common.classid > c->common.classid)
285 p = &parent->rb_right;
286 else
287 p = &parent->rb_left;
288 }
289 rb_link_node(&cl->node[prio], parent, p);
290 rb_insert_color(&cl->node[prio], root);
291}
292
293/**
294 * htb_add_to_wait_tree - adds class to the event queue with delay
295 *
296 * The class is added to priority event queue to indicate that class will
297 * change its mode in cl->pq_key microseconds. Make sure that class is not
298 * already in the queue.
299 */
300static void htb_add_to_wait_tree(struct htb_sched *q,
301 struct htb_class *cl, s64 delay)
302{
303 struct rb_node **p = &q->hlevel[cl->level].wait_pq.rb_node, *parent = NULL;
304
305 cl->pq_key = q->now + delay;
306 if (cl->pq_key == q->now)
307 cl->pq_key++;
308
309 /* update the nearest event cache */
310 if (q->near_ev_cache[cl->level] > cl->pq_key)
311 q->near_ev_cache[cl->level] = cl->pq_key;
312
313 while (*p) {
314 struct htb_class *c;
315 parent = *p;
316 c = rb_entry(parent, struct htb_class, pq_node);
317 if (cl->pq_key >= c->pq_key)
318 p = &parent->rb_right;
319 else
320 p = &parent->rb_left;
321 }
322 rb_link_node(&cl->pq_node, parent, p);
323 rb_insert_color(&cl->pq_node, &q->hlevel[cl->level].wait_pq);
324}
325
326/**
327 * htb_next_rb_node - finds next node in binary tree
328 *
329 * When we are past last key we return NULL.
330 * Average complexity is 2 steps per call.
331 */
332static inline void htb_next_rb_node(struct rb_node **n)
333{
334 *n = rb_next(*n);
335}
336
337/**
338 * htb_add_class_to_row - add class to its row
339 *
340 * The class is added to row at priorities marked in mask.
341 * It does nothing if mask == 0.
342 */
343static inline void htb_add_class_to_row(struct htb_sched *q,
344 struct htb_class *cl, int mask)
345{
346 q->row_mask[cl->level] |= mask;
347 while (mask) {
348 int prio = ffz(~mask);
349 mask &= ~(1 << prio);
350 htb_add_to_id_tree(&q->hlevel[cl->level].hprio[prio].row, cl, prio);
351 }
352}
353
354/* If this triggers, it is a bug in this code, but it need not be fatal */
355static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
356{
357 if (RB_EMPTY_NODE(rb)) {
358 WARN_ON(1);
359 } else {
360 rb_erase(rb, root);
361 RB_CLEAR_NODE(rb);
362 }
363}
364
365
366/**
367 * htb_remove_class_from_row - removes class from its row
368 *
369 * The class is removed from row at priorities marked in mask.
370 * It does nothing if mask == 0.
371 */
372static inline void htb_remove_class_from_row(struct htb_sched *q,
373 struct htb_class *cl, int mask)
374{
375 int m = 0;
376 struct htb_level *hlevel = &q->hlevel[cl->level];
377
378 while (mask) {
379 int prio = ffz(~mask);
380 struct htb_prio *hprio = &hlevel->hprio[prio];
381
382 mask &= ~(1 << prio);
383 if (hprio->ptr == cl->node + prio)
384 htb_next_rb_node(&hprio->ptr);
385
386 htb_safe_rb_erase(cl->node + prio, &hprio->row);
387 if (!hprio->row.rb_node)
388 m |= 1 << prio;
389 }
390 q->row_mask[cl->level] &= ~m;
391}
392
393/**
394 * htb_activate_prios - creates active classe's feed chain
395 *
396 * The class is connected to ancestors and/or appropriate rows
397 * for priorities it is participating on. cl->cmode must be new
398 * (activated) mode. It does nothing if cl->prio_activity == 0.
399 */
400static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
401{
402 struct htb_class *p = cl->parent;
403 long m, mask = cl->prio_activity;
404
405 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
406 m = mask;
407 while (m) {
408 int prio = ffz(~m);
409 m &= ~(1 << prio);
410
411 if (p->inner.clprio[prio].feed.rb_node)
412 /* parent already has its feed in use so that
413 * reset bit in mask as parent is already ok
414 */
415 mask &= ~(1 << prio);
416
417 htb_add_to_id_tree(&p->inner.clprio[prio].feed, cl, prio);
418 }
419 p->prio_activity |= mask;
420 cl = p;
421 p = cl->parent;
422
423 }
424 if (cl->cmode == HTB_CAN_SEND && mask)
425 htb_add_class_to_row(q, cl, mask);
426}
427
428/**
429 * htb_deactivate_prios - remove class from feed chain
430 *
431 * cl->cmode must represent old mode (before deactivation). It does
432 * nothing if cl->prio_activity == 0. Class is removed from all feed
433 * chains and rows.
434 */
435static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
436{
437 struct htb_class *p = cl->parent;
438 long m, mask = cl->prio_activity;
439
440 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
441 m = mask;
442 mask = 0;
443 while (m) {
444 int prio = ffz(~m);
445 m &= ~(1 << prio);
446
447 if (p->inner.clprio[prio].ptr == cl->node + prio) {
448 /* we are removing child which is pointed to from
449 * parent feed - forget the pointer but remember
450 * classid
451 */
452 p->inner.clprio[prio].last_ptr_id = cl->common.classid;
453 p->inner.clprio[prio].ptr = NULL;
454 }
455
456 htb_safe_rb_erase(cl->node + prio,
457 &p->inner.clprio[prio].feed);
458
459 if (!p->inner.clprio[prio].feed.rb_node)
460 mask |= 1 << prio;
461 }
462
463 p->prio_activity &= ~mask;
464 cl = p;
465 p = cl->parent;
466
467 }
468 if (cl->cmode == HTB_CAN_SEND && mask)
469 htb_remove_class_from_row(q, cl, mask);
470}
471
472static inline s64 htb_lowater(const struct htb_class *cl)
473{
474 if (htb_hysteresis)
475 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
476 else
477 return 0;
478}
479static inline s64 htb_hiwater(const struct htb_class *cl)
480{
481 if (htb_hysteresis)
482 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
483 else
484 return 0;
485}
486
487
488/**
489 * htb_class_mode - computes and returns current class mode
490 *
491 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
492 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
493 * from now to time when cl will change its state.
494 * Also it is worth to note that class mode doesn't change simply
495 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
496 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
497 * mode transitions per time unit. The speed gain is about 1/6.
498 */
499static inline enum htb_cmode
500htb_class_mode(struct htb_class *cl, s64 *diff)
501{
502 s64 toks;
503
504 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
505 *diff = -toks;
506 return HTB_CANT_SEND;
507 }
508
509 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
510 return HTB_CAN_SEND;
511
512 *diff = -toks;
513 return HTB_MAY_BORROW;
514}
515
516/**
517 * htb_change_class_mode - changes classe's mode
518 *
519 * This should be the only way how to change classe's mode under normal
520 * cirsumstances. Routine will update feed lists linkage, change mode
521 * and add class to the wait event queue if appropriate. New mode should
522 * be different from old one and cl->pq_key has to be valid if changing
523 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
524 */
525static void
526htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, s64 *diff)
527{
528 enum htb_cmode new_mode = htb_class_mode(cl, diff);
529
530 if (new_mode == cl->cmode)
531 return;
532
533 if (new_mode == HTB_CANT_SEND) {
534 cl->overlimits++;
535 q->overlimits++;
536 }
537
538 if (cl->prio_activity) { /* not necessary: speed optimization */
539 if (cl->cmode != HTB_CANT_SEND)
540 htb_deactivate_prios(q, cl);
541 cl->cmode = new_mode;
542 if (new_mode != HTB_CANT_SEND)
543 htb_activate_prios(q, cl);
544 } else
545 cl->cmode = new_mode;
546}
547
548/**
549 * htb_activate - inserts leaf cl into appropriate active feeds
550 *
551 * Routine learns (new) priority of leaf and activates feed chain
552 * for the prio. It can be called on already active leaf safely.
553 * It also adds leaf into droplist.
554 */
555static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
556{
557 WARN_ON(cl->level || !cl->leaf.q || !cl->leaf.q->q.qlen);
558
559 if (!cl->prio_activity) {
560 cl->prio_activity = 1 << cl->prio;
561 htb_activate_prios(q, cl);
562 }
563}
564
565/**
566 * htb_deactivate - remove leaf cl from active feeds
567 *
568 * Make sure that leaf is active. In the other words it can't be called
569 * with non-active leaf. It also removes class from the drop list.
570 */
571static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
572{
573 WARN_ON(!cl->prio_activity);
574
575 htb_deactivate_prios(q, cl);
576 cl->prio_activity = 0;
577}
578
579static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch,
580 struct sk_buff **to_free)
581{
582 int uninitialized_var(ret);
583 unsigned int len = qdisc_pkt_len(skb);
584 struct htb_sched *q = qdisc_priv(sch);
585 struct htb_class *cl = htb_classify(skb, sch, &ret);
586
587 if (cl == HTB_DIRECT) {
588 /* enqueue to helper queue */
589 if (q->direct_queue.qlen < q->direct_qlen) {
590 __qdisc_enqueue_tail(skb, &q->direct_queue);
591 q->direct_pkts++;
592 } else {
593 return qdisc_drop(skb, sch, to_free);
594 }
595#ifdef CONFIG_NET_CLS_ACT
596 } else if (!cl) {
597 if (ret & __NET_XMIT_BYPASS)
598 qdisc_qstats_drop(sch);
599 __qdisc_drop(skb, to_free);
600 return ret;
601#endif
602 } else if ((ret = qdisc_enqueue(skb, cl->leaf.q,
603 to_free)) != NET_XMIT_SUCCESS) {
604 if (net_xmit_drop_count(ret)) {
605 qdisc_qstats_drop(sch);
606 cl->drops++;
607 }
608 return ret;
609 } else {
610 htb_activate(q, cl);
611 }
612
613 sch->qstats.backlog += len;
614 sch->q.qlen++;
615 return NET_XMIT_SUCCESS;
616}
617
618static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, s64 diff)
619{
620 s64 toks = diff + cl->tokens;
621
622 if (toks > cl->buffer)
623 toks = cl->buffer;
624 toks -= (s64) psched_l2t_ns(&cl->rate, bytes);
625 if (toks <= -cl->mbuffer)
626 toks = 1 - cl->mbuffer;
627
628 cl->tokens = toks;
629}
630
631static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, s64 diff)
632{
633 s64 toks = diff + cl->ctokens;
634
635 if (toks > cl->cbuffer)
636 toks = cl->cbuffer;
637 toks -= (s64) psched_l2t_ns(&cl->ceil, bytes);
638 if (toks <= -cl->mbuffer)
639 toks = 1 - cl->mbuffer;
640
641 cl->ctokens = toks;
642}
643
644/**
645 * htb_charge_class - charges amount "bytes" to leaf and ancestors
646 *
647 * Routine assumes that packet "bytes" long was dequeued from leaf cl
648 * borrowing from "level". It accounts bytes to ceil leaky bucket for
649 * leaf and all ancestors and to rate bucket for ancestors at levels
650 * "level" and higher. It also handles possible change of mode resulting
651 * from the update. Note that mode can also increase here (MAY_BORROW to
652 * CAN_SEND) because we can use more precise clock that event queue here.
653 * In such case we remove class from event queue first.
654 */
655static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
656 int level, struct sk_buff *skb)
657{
658 int bytes = qdisc_pkt_len(skb);
659 enum htb_cmode old_mode;
660 s64 diff;
661
662 while (cl) {
663 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
664 if (cl->level >= level) {
665 if (cl->level == level)
666 cl->xstats.lends++;
667 htb_accnt_tokens(cl, bytes, diff);
668 } else {
669 cl->xstats.borrows++;
670 cl->tokens += diff; /* we moved t_c; update tokens */
671 }
672 htb_accnt_ctokens(cl, bytes, diff);
673 cl->t_c = q->now;
674
675 old_mode = cl->cmode;
676 diff = 0;
677 htb_change_class_mode(q, cl, &diff);
678 if (old_mode != cl->cmode) {
679 if (old_mode != HTB_CAN_SEND)
680 htb_safe_rb_erase(&cl->pq_node, &q->hlevel[cl->level].wait_pq);
681 if (cl->cmode != HTB_CAN_SEND)
682 htb_add_to_wait_tree(q, cl, diff);
683 }
684
685 /* update basic stats except for leaves which are already updated */
686 if (cl->level)
687 bstats_update(&cl->bstats, skb);
688
689 cl = cl->parent;
690 }
691}
692
693/**
694 * htb_do_events - make mode changes to classes at the level
695 *
696 * Scans event queue for pending events and applies them. Returns time of
697 * next pending event (0 for no event in pq, q->now for too many events).
698 * Note: Applied are events whose have cl->pq_key <= q->now.
699 */
700static s64 htb_do_events(struct htb_sched *q, const int level,
701 unsigned long start)
702{
703 /* don't run for longer than 2 jiffies; 2 is used instead of
704 * 1 to simplify things when jiffy is going to be incremented
705 * too soon
706 */
707 unsigned long stop_at = start + 2;
708 struct rb_root *wait_pq = &q->hlevel[level].wait_pq;
709
710 while (time_before(jiffies, stop_at)) {
711 struct htb_class *cl;
712 s64 diff;
713 struct rb_node *p = rb_first(wait_pq);
714
715 if (!p)
716 return 0;
717
718 cl = rb_entry(p, struct htb_class, pq_node);
719 if (cl->pq_key > q->now)
720 return cl->pq_key;
721
722 htb_safe_rb_erase(p, wait_pq);
723 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
724 htb_change_class_mode(q, cl, &diff);
725 if (cl->cmode != HTB_CAN_SEND)
726 htb_add_to_wait_tree(q, cl, diff);
727 }
728
729 /* too much load - let's continue after a break for scheduling */
730 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
731 pr_warn("htb: too many events!\n");
732 q->warned |= HTB_WARN_TOOMANYEVENTS;
733 }
734
735 return q->now;
736}
737
738/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
739 * is no such one exists.
740 */
741static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
742 u32 id)
743{
744 struct rb_node *r = NULL;
745 while (n) {
746 struct htb_class *cl =
747 rb_entry(n, struct htb_class, node[prio]);
748
749 if (id > cl->common.classid) {
750 n = n->rb_right;
751 } else if (id < cl->common.classid) {
752 r = n;
753 n = n->rb_left;
754 } else {
755 return n;
756 }
757 }
758 return r;
759}
760
761/**
762 * htb_lookup_leaf - returns next leaf class in DRR order
763 *
764 * Find leaf where current feed pointers points to.
765 */
766static struct htb_class *htb_lookup_leaf(struct htb_prio *hprio, const int prio)
767{
768 int i;
769 struct {
770 struct rb_node *root;
771 struct rb_node **pptr;
772 u32 *pid;
773 } stk[TC_HTB_MAXDEPTH], *sp = stk;
774
775 BUG_ON(!hprio->row.rb_node);
776 sp->root = hprio->row.rb_node;
777 sp->pptr = &hprio->ptr;
778 sp->pid = &hprio->last_ptr_id;
779
780 for (i = 0; i < 65535; i++) {
781 if (!*sp->pptr && *sp->pid) {
782 /* ptr was invalidated but id is valid - try to recover
783 * the original or next ptr
784 */
785 *sp->pptr =
786 htb_id_find_next_upper(prio, sp->root, *sp->pid);
787 }
788 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
789 * can become out of date quickly
790 */
791 if (!*sp->pptr) { /* we are at right end; rewind & go up */
792 *sp->pptr = sp->root;
793 while ((*sp->pptr)->rb_left)
794 *sp->pptr = (*sp->pptr)->rb_left;
795 if (sp > stk) {
796 sp--;
797 if (!*sp->pptr) {
798 WARN_ON(1);
799 return NULL;
800 }
801 htb_next_rb_node(sp->pptr);
802 }
803 } else {
804 struct htb_class *cl;
805 struct htb_prio *clp;
806
807 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
808 if (!cl->level)
809 return cl;
810 clp = &cl->inner.clprio[prio];
811 (++sp)->root = clp->feed.rb_node;
812 sp->pptr = &clp->ptr;
813 sp->pid = &clp->last_ptr_id;
814 }
815 }
816 WARN_ON(1);
817 return NULL;
818}
819
820/* dequeues packet at given priority and level; call only if
821 * you are sure that there is active class at prio/level
822 */
823static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, const int prio,
824 const int level)
825{
826 struct sk_buff *skb = NULL;
827 struct htb_class *cl, *start;
828 struct htb_level *hlevel = &q->hlevel[level];
829 struct htb_prio *hprio = &hlevel->hprio[prio];
830
831 /* look initial class up in the row */
832 start = cl = htb_lookup_leaf(hprio, prio);
833
834 do {
835next:
836 if (unlikely(!cl))
837 return NULL;
838
839 /* class can be empty - it is unlikely but can be true if leaf
840 * qdisc drops packets in enqueue routine or if someone used
841 * graft operation on the leaf since last dequeue;
842 * simply deactivate and skip such class
843 */
844 if (unlikely(cl->leaf.q->q.qlen == 0)) {
845 struct htb_class *next;
846 htb_deactivate(q, cl);
847
848 /* row/level might become empty */
849 if ((q->row_mask[level] & (1 << prio)) == 0)
850 return NULL;
851
852 next = htb_lookup_leaf(hprio, prio);
853
854 if (cl == start) /* fix start if we just deleted it */
855 start = next;
856 cl = next;
857 goto next;
858 }
859
860 skb = cl->leaf.q->dequeue(cl->leaf.q);
861 if (likely(skb != NULL))
862 break;
863
864 qdisc_warn_nonwc("htb", cl->leaf.q);
865 htb_next_rb_node(level ? &cl->parent->inner.clprio[prio].ptr:
866 &q->hlevel[0].hprio[prio].ptr);
867 cl = htb_lookup_leaf(hprio, prio);
868
869 } while (cl != start);
870
871 if (likely(skb != NULL)) {
872 bstats_update(&cl->bstats, skb);
873 cl->leaf.deficit[level] -= qdisc_pkt_len(skb);
874 if (cl->leaf.deficit[level] < 0) {
875 cl->leaf.deficit[level] += cl->quantum;
876 htb_next_rb_node(level ? &cl->parent->inner.clprio[prio].ptr :
877 &q->hlevel[0].hprio[prio].ptr);
878 }
879 /* this used to be after charge_class but this constelation
880 * gives us slightly better performance
881 */
882 if (!cl->leaf.q->q.qlen)
883 htb_deactivate(q, cl);
884 htb_charge_class(q, cl, level, skb);
885 }
886 return skb;
887}
888
889static struct sk_buff *htb_dequeue(struct Qdisc *sch)
890{
891 struct sk_buff *skb;
892 struct htb_sched *q = qdisc_priv(sch);
893 int level;
894 s64 next_event;
895 unsigned long start_at;
896
897 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
898 skb = __qdisc_dequeue_head(&q->direct_queue);
899 if (skb != NULL) {
900ok:
901 qdisc_bstats_update(sch, skb);
902 qdisc_qstats_backlog_dec(sch, skb);
903 sch->q.qlen--;
904 return skb;
905 }
906
907 if (!sch->q.qlen)
908 goto fin;
909 q->now = ktime_get_ns();
910 start_at = jiffies;
911
912 next_event = q->now + 5LLU * NSEC_PER_SEC;
913
914 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
915 /* common case optimization - skip event handler quickly */
916 int m;
917 s64 event = q->near_ev_cache[level];
918
919 if (q->now >= event) {
920 event = htb_do_events(q, level, start_at);
921 if (!event)
922 event = q->now + NSEC_PER_SEC;
923 q->near_ev_cache[level] = event;
924 }
925
926 if (next_event > event)
927 next_event = event;
928
929 m = ~q->row_mask[level];
930 while (m != (int)(-1)) {
931 int prio = ffz(m);
932
933 m |= 1 << prio;
934 skb = htb_dequeue_tree(q, prio, level);
935 if (likely(skb != NULL))
936 goto ok;
937 }
938 }
939 if (likely(next_event > q->now))
940 qdisc_watchdog_schedule_ns(&q->watchdog, next_event);
941 else
942 schedule_work(&q->work);
943fin:
944 return skb;
945}
946
947/* reset all classes */
948/* always caled under BH & queue lock */
949static void htb_reset(struct Qdisc *sch)
950{
951 struct htb_sched *q = qdisc_priv(sch);
952 struct htb_class *cl;
953 unsigned int i;
954
955 for (i = 0; i < q->clhash.hashsize; i++) {
956 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
957 if (cl->level)
958 memset(&cl->inner, 0, sizeof(cl->inner));
959 else {
960 if (cl->leaf.q)
961 qdisc_reset(cl->leaf.q);
962 }
963 cl->prio_activity = 0;
964 cl->cmode = HTB_CAN_SEND;
965 }
966 }
967 qdisc_watchdog_cancel(&q->watchdog);
968 __qdisc_reset_queue(&q->direct_queue);
969 sch->q.qlen = 0;
970 sch->qstats.backlog = 0;
971 memset(q->hlevel, 0, sizeof(q->hlevel));
972 memset(q->row_mask, 0, sizeof(q->row_mask));
973}
974
975static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
976 [TCA_HTB_PARMS] = { .len = sizeof(struct tc_htb_opt) },
977 [TCA_HTB_INIT] = { .len = sizeof(struct tc_htb_glob) },
978 [TCA_HTB_CTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
979 [TCA_HTB_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
980 [TCA_HTB_DIRECT_QLEN] = { .type = NLA_U32 },
981 [TCA_HTB_RATE64] = { .type = NLA_U64 },
982 [TCA_HTB_CEIL64] = { .type = NLA_U64 },
983};
984
985static void htb_work_func(struct work_struct *work)
986{
987 struct htb_sched *q = container_of(work, struct htb_sched, work);
988 struct Qdisc *sch = q->watchdog.qdisc;
989
990 rcu_read_lock();
991 __netif_schedule(qdisc_root(sch));
992 rcu_read_unlock();
993}
994
995static int htb_init(struct Qdisc *sch, struct nlattr *opt,
996 struct netlink_ext_ack *extack)
997{
998 struct htb_sched *q = qdisc_priv(sch);
999 struct nlattr *tb[TCA_HTB_MAX + 1];
1000 struct tc_htb_glob *gopt;
1001 int err;
1002
1003 qdisc_watchdog_init(&q->watchdog, sch);
1004 INIT_WORK(&q->work, htb_work_func);
1005
1006 if (!opt)
1007 return -EINVAL;
1008
1009 err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
1010 if (err)
1011 return err;
1012
1013 err = nla_parse_nested_deprecated(tb, TCA_HTB_MAX, opt, htb_policy,
1014 NULL);
1015 if (err < 0)
1016 return err;
1017
1018 if (!tb[TCA_HTB_INIT])
1019 return -EINVAL;
1020
1021 gopt = nla_data(tb[TCA_HTB_INIT]);
1022 if (gopt->version != HTB_VER >> 16)
1023 return -EINVAL;
1024
1025 err = qdisc_class_hash_init(&q->clhash);
1026 if (err < 0)
1027 return err;
1028
1029 qdisc_skb_head_init(&q->direct_queue);
1030
1031 if (tb[TCA_HTB_DIRECT_QLEN])
1032 q->direct_qlen = nla_get_u32(tb[TCA_HTB_DIRECT_QLEN]);
1033 else
1034 q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
1035
1036 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1037 q->rate2quantum = 1;
1038 q->defcls = gopt->defcls;
1039
1040 return 0;
1041}
1042
1043static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1044{
1045 struct htb_sched *q = qdisc_priv(sch);
1046 struct nlattr *nest;
1047 struct tc_htb_glob gopt;
1048
1049 sch->qstats.overlimits = q->overlimits;
1050 /* Its safe to not acquire qdisc lock. As we hold RTNL,
1051 * no change can happen on the qdisc parameters.
1052 */
1053
1054 gopt.direct_pkts = q->direct_pkts;
1055 gopt.version = HTB_VER;
1056 gopt.rate2quantum = q->rate2quantum;
1057 gopt.defcls = q->defcls;
1058 gopt.debug = 0;
1059
1060 nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
1061 if (nest == NULL)
1062 goto nla_put_failure;
1063 if (nla_put(skb, TCA_HTB_INIT, sizeof(gopt), &gopt) ||
1064 nla_put_u32(skb, TCA_HTB_DIRECT_QLEN, q->direct_qlen))
1065 goto nla_put_failure;
1066
1067 return nla_nest_end(skb, nest);
1068
1069nla_put_failure:
1070 nla_nest_cancel(skb, nest);
1071 return -1;
1072}
1073
1074static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
1075 struct sk_buff *skb, struct tcmsg *tcm)
1076{
1077 struct htb_class *cl = (struct htb_class *)arg;
1078 struct nlattr *nest;
1079 struct tc_htb_opt opt;
1080
1081 /* Its safe to not acquire qdisc lock. As we hold RTNL,
1082 * no change can happen on the class parameters.
1083 */
1084 tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
1085 tcm->tcm_handle = cl->common.classid;
1086 if (!cl->level && cl->leaf.q)
1087 tcm->tcm_info = cl->leaf.q->handle;
1088
1089 nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
1090 if (nest == NULL)
1091 goto nla_put_failure;
1092
1093 memset(&opt, 0, sizeof(opt));
1094
1095 psched_ratecfg_getrate(&opt.rate, &cl->rate);
1096 opt.buffer = PSCHED_NS2TICKS(cl->buffer);
1097 psched_ratecfg_getrate(&opt.ceil, &cl->ceil);
1098 opt.cbuffer = PSCHED_NS2TICKS(cl->cbuffer);
1099 opt.quantum = cl->quantum;
1100 opt.prio = cl->prio;
1101 opt.level = cl->level;
1102 if (nla_put(skb, TCA_HTB_PARMS, sizeof(opt), &opt))
1103 goto nla_put_failure;
1104 if ((cl->rate.rate_bytes_ps >= (1ULL << 32)) &&
1105 nla_put_u64_64bit(skb, TCA_HTB_RATE64, cl->rate.rate_bytes_ps,
1106 TCA_HTB_PAD))
1107 goto nla_put_failure;
1108 if ((cl->ceil.rate_bytes_ps >= (1ULL << 32)) &&
1109 nla_put_u64_64bit(skb, TCA_HTB_CEIL64, cl->ceil.rate_bytes_ps,
1110 TCA_HTB_PAD))
1111 goto nla_put_failure;
1112
1113 return nla_nest_end(skb, nest);
1114
1115nla_put_failure:
1116 nla_nest_cancel(skb, nest);
1117 return -1;
1118}
1119
1120static int
1121htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
1122{
1123 struct htb_class *cl = (struct htb_class *)arg;
1124 struct gnet_stats_queue qs = {
1125 .drops = cl->drops,
1126 .overlimits = cl->overlimits,
1127 };
1128 __u32 qlen = 0;
1129
1130 if (!cl->level && cl->leaf.q)
1131 qdisc_qstats_qlen_backlog(cl->leaf.q, &qlen, &qs.backlog);
1132
1133 cl->xstats.tokens = clamp_t(s64, PSCHED_NS2TICKS(cl->tokens),
1134 INT_MIN, INT_MAX);
1135 cl->xstats.ctokens = clamp_t(s64, PSCHED_NS2TICKS(cl->ctokens),
1136 INT_MIN, INT_MAX);
1137
1138 if (gnet_stats_copy_basic(qdisc_root_sleeping_running(sch),
1139 d, NULL, &cl->bstats) < 0 ||
1140 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1141 gnet_stats_copy_queue(d, NULL, &qs, qlen) < 0)
1142 return -1;
1143
1144 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1145}
1146
1147static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1148 struct Qdisc **old, struct netlink_ext_ack *extack)
1149{
1150 struct htb_class *cl = (struct htb_class *)arg;
1151
1152 if (cl->level)
1153 return -EINVAL;
1154 if (new == NULL &&
1155 (new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1156 cl->common.classid, extack)) == NULL)
1157 return -ENOBUFS;
1158
1159 *old = qdisc_replace(sch, new, &cl->leaf.q);
1160 return 0;
1161}
1162
1163static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
1164{
1165 struct htb_class *cl = (struct htb_class *)arg;
1166 return !cl->level ? cl->leaf.q : NULL;
1167}
1168
1169static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
1170{
1171 struct htb_class *cl = (struct htb_class *)arg;
1172
1173 htb_deactivate(qdisc_priv(sch), cl);
1174}
1175
1176static inline int htb_parent_last_child(struct htb_class *cl)
1177{
1178 if (!cl->parent)
1179 /* the root class */
1180 return 0;
1181 if (cl->parent->children > 1)
1182 /* not the last child */
1183 return 0;
1184 return 1;
1185}
1186
1187static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl,
1188 struct Qdisc *new_q)
1189{
1190 struct htb_class *parent = cl->parent;
1191
1192 WARN_ON(cl->level || !cl->leaf.q || cl->prio_activity);
1193
1194 if (parent->cmode != HTB_CAN_SEND)
1195 htb_safe_rb_erase(&parent->pq_node,
1196 &q->hlevel[parent->level].wait_pq);
1197
1198 parent->level = 0;
1199 memset(&parent->inner, 0, sizeof(parent->inner));
1200 parent->leaf.q = new_q ? new_q : &noop_qdisc;
1201 parent->tokens = parent->buffer;
1202 parent->ctokens = parent->cbuffer;
1203 parent->t_c = ktime_get_ns();
1204 parent->cmode = HTB_CAN_SEND;
1205}
1206
1207static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
1208{
1209 if (!cl->level) {
1210 WARN_ON(!cl->leaf.q);
1211 qdisc_put(cl->leaf.q);
1212 }
1213 gen_kill_estimator(&cl->rate_est);
1214 tcf_block_put(cl->block);
1215 kfree(cl);
1216}
1217
1218static void htb_destroy(struct Qdisc *sch)
1219{
1220 struct htb_sched *q = qdisc_priv(sch);
1221 struct hlist_node *next;
1222 struct htb_class *cl;
1223 unsigned int i;
1224
1225 cancel_work_sync(&q->work);
1226 qdisc_watchdog_cancel(&q->watchdog);
1227 /* This line used to be after htb_destroy_class call below
1228 * and surprisingly it worked in 2.4. But it must precede it
1229 * because filter need its target class alive to be able to call
1230 * unbind_filter on it (without Oops).
1231 */
1232 tcf_block_put(q->block);
1233
1234 for (i = 0; i < q->clhash.hashsize; i++) {
1235 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
1236 tcf_block_put(cl->block);
1237 cl->block = NULL;
1238 }
1239 }
1240 for (i = 0; i < q->clhash.hashsize; i++) {
1241 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],
1242 common.hnode)
1243 htb_destroy_class(sch, cl);
1244 }
1245 qdisc_class_hash_destroy(&q->clhash);
1246 __qdisc_reset_queue(&q->direct_queue);
1247}
1248
1249static int htb_delete(struct Qdisc *sch, unsigned long arg)
1250{
1251 struct htb_sched *q = qdisc_priv(sch);
1252 struct htb_class *cl = (struct htb_class *)arg;
1253 struct Qdisc *new_q = NULL;
1254 int last_child = 0;
1255
1256 /* TODO: why don't allow to delete subtree ? references ? does
1257 * tc subsys guarantee us that in htb_destroy it holds no class
1258 * refs so that we can remove children safely there ?
1259 */
1260 if (cl->children || cl->filter_cnt)
1261 return -EBUSY;
1262
1263 if (!cl->level && htb_parent_last_child(cl)) {
1264 new_q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1265 cl->parent->common.classid,
1266 NULL);
1267 last_child = 1;
1268 }
1269
1270 sch_tree_lock(sch);
1271
1272 if (!cl->level)
1273 qdisc_purge_queue(cl->leaf.q);
1274
1275 /* delete from hash and active; remainder in destroy_class */
1276 qdisc_class_hash_remove(&q->clhash, &cl->common);
1277 if (cl->parent)
1278 cl->parent->children--;
1279
1280 if (cl->prio_activity)
1281 htb_deactivate(q, cl);
1282
1283 if (cl->cmode != HTB_CAN_SEND)
1284 htb_safe_rb_erase(&cl->pq_node,
1285 &q->hlevel[cl->level].wait_pq);
1286
1287 if (last_child)
1288 htb_parent_to_leaf(q, cl, new_q);
1289
1290 sch_tree_unlock(sch);
1291
1292 htb_destroy_class(sch, cl);
1293 return 0;
1294}
1295
1296static int htb_change_class(struct Qdisc *sch, u32 classid,
1297 u32 parentid, struct nlattr **tca,
1298 unsigned long *arg, struct netlink_ext_ack *extack)
1299{
1300 int err = -EINVAL;
1301 struct htb_sched *q = qdisc_priv(sch);
1302 struct htb_class *cl = (struct htb_class *)*arg, *parent;
1303 struct nlattr *opt = tca[TCA_OPTIONS];
1304 struct nlattr *tb[TCA_HTB_MAX + 1];
1305 struct Qdisc *parent_qdisc = NULL;
1306 struct tc_htb_opt *hopt;
1307 u64 rate64, ceil64;
1308 int warn = 0;
1309
1310 /* extract all subattrs from opt attr */
1311 if (!opt)
1312 goto failure;
1313
1314 err = nla_parse_nested_deprecated(tb, TCA_HTB_MAX, opt, htb_policy,
1315 NULL);
1316 if (err < 0)
1317 goto failure;
1318
1319 err = -EINVAL;
1320 if (tb[TCA_HTB_PARMS] == NULL)
1321 goto failure;
1322
1323 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
1324
1325 hopt = nla_data(tb[TCA_HTB_PARMS]);
1326 if (!hopt->rate.rate || !hopt->ceil.rate)
1327 goto failure;
1328
1329 /* Keeping backward compatible with rate_table based iproute2 tc */
1330 if (hopt->rate.linklayer == TC_LINKLAYER_UNAWARE)
1331 qdisc_put_rtab(qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB],
1332 NULL));
1333
1334 if (hopt->ceil.linklayer == TC_LINKLAYER_UNAWARE)
1335 qdisc_put_rtab(qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB],
1336 NULL));
1337
1338 if (!cl) { /* new class */
1339 struct Qdisc *new_q;
1340 int prio;
1341 struct {
1342 struct nlattr nla;
1343 struct gnet_estimator opt;
1344 } est = {
1345 .nla = {
1346 .nla_len = nla_attr_size(sizeof(est.opt)),
1347 .nla_type = TCA_RATE,
1348 },
1349 .opt = {
1350 /* 4s interval, 16s averaging constant */
1351 .interval = 2,
1352 .ewma_log = 2,
1353 },
1354 };
1355
1356 /* check for valid classid */
1357 if (!classid || TC_H_MAJ(classid ^ sch->handle) ||
1358 htb_find(classid, sch))
1359 goto failure;
1360
1361 /* check maximal depth */
1362 if (parent && parent->parent && parent->parent->level < 2) {
1363 pr_err("htb: tree is too deep\n");
1364 goto failure;
1365 }
1366 err = -ENOBUFS;
1367 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1368 if (!cl)
1369 goto failure;
1370
1371 err = tcf_block_get(&cl->block, &cl->filter_list, sch, extack);
1372 if (err) {
1373 kfree(cl);
1374 goto failure;
1375 }
1376 if (htb_rate_est || tca[TCA_RATE]) {
1377 err = gen_new_estimator(&cl->bstats, NULL,
1378 &cl->rate_est,
1379 NULL,
1380 qdisc_root_sleeping_running(sch),
1381 tca[TCA_RATE] ? : &est.nla);
1382 if (err) {
1383 tcf_block_put(cl->block);
1384 kfree(cl);
1385 goto failure;
1386 }
1387 }
1388
1389 cl->children = 0;
1390 RB_CLEAR_NODE(&cl->pq_node);
1391
1392 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1393 RB_CLEAR_NODE(&cl->node[prio]);
1394
1395 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
1396 * so that can't be used inside of sch_tree_lock
1397 * -- thanks to Karlis Peisenieks
1398 */
1399 new_q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
1400 classid, NULL);
1401 sch_tree_lock(sch);
1402 if (parent && !parent->level) {
1403 /* turn parent into inner node */
1404 qdisc_purge_queue(parent->leaf.q);
1405 parent_qdisc = parent->leaf.q;
1406 if (parent->prio_activity)
1407 htb_deactivate(q, parent);
1408
1409 /* remove from evt list because of level change */
1410 if (parent->cmode != HTB_CAN_SEND) {
1411 htb_safe_rb_erase(&parent->pq_node, &q->hlevel[0].wait_pq);
1412 parent->cmode = HTB_CAN_SEND;
1413 }
1414 parent->level = (parent->parent ? parent->parent->level
1415 : TC_HTB_MAXDEPTH) - 1;
1416 memset(&parent->inner, 0, sizeof(parent->inner));
1417 }
1418 /* leaf (we) needs elementary qdisc */
1419 cl->leaf.q = new_q ? new_q : &noop_qdisc;
1420
1421 cl->common.classid = classid;
1422 cl->parent = parent;
1423
1424 /* set class to be in HTB_CAN_SEND state */
1425 cl->tokens = PSCHED_TICKS2NS(hopt->buffer);
1426 cl->ctokens = PSCHED_TICKS2NS(hopt->cbuffer);
1427 cl->mbuffer = 60ULL * NSEC_PER_SEC; /* 1min */
1428 cl->t_c = ktime_get_ns();
1429 cl->cmode = HTB_CAN_SEND;
1430
1431 /* attach to the hash list and parent's family */
1432 qdisc_class_hash_insert(&q->clhash, &cl->common);
1433 if (parent)
1434 parent->children++;
1435 if (cl->leaf.q != &noop_qdisc)
1436 qdisc_hash_add(cl->leaf.q, true);
1437 } else {
1438 if (tca[TCA_RATE]) {
1439 err = gen_replace_estimator(&cl->bstats, NULL,
1440 &cl->rate_est,
1441 NULL,
1442 qdisc_root_sleeping_running(sch),
1443 tca[TCA_RATE]);
1444 if (err)
1445 return err;
1446 }
1447 sch_tree_lock(sch);
1448 }
1449
1450 rate64 = tb[TCA_HTB_RATE64] ? nla_get_u64(tb[TCA_HTB_RATE64]) : 0;
1451
1452 ceil64 = tb[TCA_HTB_CEIL64] ? nla_get_u64(tb[TCA_HTB_CEIL64]) : 0;
1453
1454 psched_ratecfg_precompute(&cl->rate, &hopt->rate, rate64);
1455 psched_ratecfg_precompute(&cl->ceil, &hopt->ceil, ceil64);
1456
1457 /* it used to be a nasty bug here, we have to check that node
1458 * is really leaf before changing cl->leaf !
1459 */
1460 if (!cl->level) {
1461 u64 quantum = cl->rate.rate_bytes_ps;
1462
1463 do_div(quantum, q->rate2quantum);
1464 cl->quantum = min_t(u64, quantum, INT_MAX);
1465
1466 if (!hopt->quantum && cl->quantum < 1000) {
1467 warn = -1;
1468 cl->quantum = 1000;
1469 }
1470 if (!hopt->quantum && cl->quantum > 200000) {
1471 warn = 1;
1472 cl->quantum = 200000;
1473 }
1474 if (hopt->quantum)
1475 cl->quantum = hopt->quantum;
1476 if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO)
1477 cl->prio = TC_HTB_NUMPRIO - 1;
1478 }
1479
1480 cl->buffer = PSCHED_TICKS2NS(hopt->buffer);
1481 cl->cbuffer = PSCHED_TICKS2NS(hopt->cbuffer);
1482
1483 sch_tree_unlock(sch);
1484 qdisc_put(parent_qdisc);
1485
1486 if (warn)
1487 pr_warn("HTB: quantum of class %X is %s. Consider r2q change.\n",
1488 cl->common.classid, (warn == -1 ? "small" : "big"));
1489
1490 qdisc_class_hash_grow(sch, &q->clhash);
1491
1492 *arg = (unsigned long)cl;
1493 return 0;
1494
1495failure:
1496 return err;
1497}
1498
1499static struct tcf_block *htb_tcf_block(struct Qdisc *sch, unsigned long arg,
1500 struct netlink_ext_ack *extack)
1501{
1502 struct htb_sched *q = qdisc_priv(sch);
1503 struct htb_class *cl = (struct htb_class *)arg;
1504
1505 return cl ? cl->block : q->block;
1506}
1507
1508static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
1509 u32 classid)
1510{
1511 struct htb_class *cl = htb_find(classid, sch);
1512
1513 /*if (cl && !cl->level) return 0;
1514 * The line above used to be there to prevent attaching filters to
1515 * leaves. But at least tc_index filter uses this just to get class
1516 * for other reasons so that we have to allow for it.
1517 * ----
1518 * 19.6.2002 As Werner explained it is ok - bind filter is just
1519 * another way to "lock" the class - unlike "get" this lock can
1520 * be broken by class during destroy IIUC.
1521 */
1522 if (cl)
1523 cl->filter_cnt++;
1524 return (unsigned long)cl;
1525}
1526
1527static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1528{
1529 struct htb_class *cl = (struct htb_class *)arg;
1530
1531 if (cl)
1532 cl->filter_cnt--;
1533}
1534
1535static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1536{
1537 struct htb_sched *q = qdisc_priv(sch);
1538 struct htb_class *cl;
1539 unsigned int i;
1540
1541 if (arg->stop)
1542 return;
1543
1544 for (i = 0; i < q->clhash.hashsize; i++) {
1545 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
1546 if (arg->count < arg->skip) {
1547 arg->count++;
1548 continue;
1549 }
1550 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1551 arg->stop = 1;
1552 return;
1553 }
1554 arg->count++;
1555 }
1556 }
1557}
1558
1559static const struct Qdisc_class_ops htb_class_ops = {
1560 .graft = htb_graft,
1561 .leaf = htb_leaf,
1562 .qlen_notify = htb_qlen_notify,
1563 .find = htb_search,
1564 .change = htb_change_class,
1565 .delete = htb_delete,
1566 .walk = htb_walk,
1567 .tcf_block = htb_tcf_block,
1568 .bind_tcf = htb_bind_filter,
1569 .unbind_tcf = htb_unbind_filter,
1570 .dump = htb_dump_class,
1571 .dump_stats = htb_dump_class_stats,
1572};
1573
1574static struct Qdisc_ops htb_qdisc_ops __read_mostly = {
1575 .cl_ops = &htb_class_ops,
1576 .id = "htb",
1577 .priv_size = sizeof(struct htb_sched),
1578 .enqueue = htb_enqueue,
1579 .dequeue = htb_dequeue,
1580 .peek = qdisc_peek_dequeued,
1581 .init = htb_init,
1582 .reset = htb_reset,
1583 .destroy = htb_destroy,
1584 .dump = htb_dump,
1585 .owner = THIS_MODULE,
1586};
1587
1588static int __init htb_module_init(void)
1589{
1590 return register_qdisc(&htb_qdisc_ops);
1591}
1592static void __exit htb_module_exit(void)
1593{
1594 unregister_qdisc(&htb_qdisc_ops);
1595}
1596
1597module_init(htb_module_init)
1598module_exit(htb_module_exit)
1599MODULE_LICENSE("GPL");
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 kfree_skb(skb);
562 sch->qstats.drops++;
563 return NET_XMIT_DROP;
564 }
565#ifdef CONFIG_NET_CLS_ACT
566 } else if (!cl) {
567 if (ret & __NET_XMIT_BYPASS)
568 sch->qstats.drops++;
569 kfree_skb(skb);
570 return ret;
571#endif
572 } else if ((ret = qdisc_enqueue(skb, cl->un.leaf.q)) != NET_XMIT_SUCCESS) {
573 if (net_xmit_drop_count(ret)) {
574 sch->qstats.drops++;
575 cl->qstats.drops++;
576 }
577 return ret;
578 } else {
579 bstats_update(&cl->bstats, skb);
580 htb_activate(q, cl);
581 }
582
583 sch->q.qlen++;
584 return NET_XMIT_SUCCESS;
585}
586
587static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, long diff)
588{
589 long toks = diff + cl->tokens;
590
591 if (toks > cl->buffer)
592 toks = cl->buffer;
593 toks -= (long) qdisc_l2t(cl->rate, bytes);
594 if (toks <= -cl->mbuffer)
595 toks = 1 - cl->mbuffer;
596
597 cl->tokens = toks;
598}
599
600static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, long diff)
601{
602 long toks = diff + cl->ctokens;
603
604 if (toks > cl->cbuffer)
605 toks = cl->cbuffer;
606 toks -= (long) qdisc_l2t(cl->ceil, bytes);
607 if (toks <= -cl->mbuffer)
608 toks = 1 - cl->mbuffer;
609
610 cl->ctokens = toks;
611}
612
613/**
614 * htb_charge_class - charges amount "bytes" to leaf and ancestors
615 *
616 * Routine assumes that packet "bytes" long was dequeued from leaf cl
617 * borrowing from "level". It accounts bytes to ceil leaky bucket for
618 * leaf and all ancestors and to rate bucket for ancestors at levels
619 * "level" and higher. It also handles possible change of mode resulting
620 * from the update. Note that mode can also increase here (MAY_BORROW to
621 * CAN_SEND) because we can use more precise clock that event queue here.
622 * In such case we remove class from event queue first.
623 */
624static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
625 int level, struct sk_buff *skb)
626{
627 int bytes = qdisc_pkt_len(skb);
628 enum htb_cmode old_mode;
629 long diff;
630
631 while (cl) {
632 diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
633 if (cl->level >= level) {
634 if (cl->level == level)
635 cl->xstats.lends++;
636 htb_accnt_tokens(cl, bytes, diff);
637 } else {
638 cl->xstats.borrows++;
639 cl->tokens += diff; /* we moved t_c; update tokens */
640 }
641 htb_accnt_ctokens(cl, bytes, diff);
642 cl->t_c = q->now;
643
644 old_mode = cl->cmode;
645 diff = 0;
646 htb_change_class_mode(q, cl, &diff);
647 if (old_mode != cl->cmode) {
648 if (old_mode != HTB_CAN_SEND)
649 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
650 if (cl->cmode != HTB_CAN_SEND)
651 htb_add_to_wait_tree(q, cl, diff);
652 }
653
654 /* update basic stats except for leaves which are already updated */
655 if (cl->level)
656 bstats_update(&cl->bstats, skb);
657
658 cl = cl->parent;
659 }
660}
661
662/**
663 * htb_do_events - make mode changes to classes at the level
664 *
665 * Scans event queue for pending events and applies them. Returns time of
666 * next pending event (0 for no event in pq, q->now for too many events).
667 * Note: Applied are events whose have cl->pq_key <= q->now.
668 */
669static psched_time_t htb_do_events(struct htb_sched *q, int level,
670 unsigned long start)
671{
672 /* don't run for longer than 2 jiffies; 2 is used instead of
673 * 1 to simplify things when jiffy is going to be incremented
674 * too soon
675 */
676 unsigned long stop_at = start + 2;
677 while (time_before(jiffies, stop_at)) {
678 struct htb_class *cl;
679 long diff;
680 struct rb_node *p = rb_first(&q->wait_pq[level]);
681
682 if (!p)
683 return 0;
684
685 cl = rb_entry(p, struct htb_class, pq_node);
686 if (cl->pq_key > q->now)
687 return cl->pq_key;
688
689 htb_safe_rb_erase(p, q->wait_pq + level);
690 diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
691 htb_change_class_mode(q, cl, &diff);
692 if (cl->cmode != HTB_CAN_SEND)
693 htb_add_to_wait_tree(q, cl, diff);
694 }
695
696 /* too much load - let's continue after a break for scheduling */
697 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
698 pr_warning("htb: too many events!\n");
699 q->warned |= HTB_WARN_TOOMANYEVENTS;
700 }
701
702 return q->now;
703}
704
705/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
706 * is no such one exists.
707 */
708static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
709 u32 id)
710{
711 struct rb_node *r = NULL;
712 while (n) {
713 struct htb_class *cl =
714 rb_entry(n, struct htb_class, node[prio]);
715
716 if (id > cl->common.classid) {
717 n = n->rb_right;
718 } else if (id < cl->common.classid) {
719 r = n;
720 n = n->rb_left;
721 } else {
722 return n;
723 }
724 }
725 return r;
726}
727
728/**
729 * htb_lookup_leaf - returns next leaf class in DRR order
730 *
731 * Find leaf where current feed pointers points to.
732 */
733static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio,
734 struct rb_node **pptr, u32 * pid)
735{
736 int i;
737 struct {
738 struct rb_node *root;
739 struct rb_node **pptr;
740 u32 *pid;
741 } stk[TC_HTB_MAXDEPTH], *sp = stk;
742
743 BUG_ON(!tree->rb_node);
744 sp->root = tree->rb_node;
745 sp->pptr = pptr;
746 sp->pid = pid;
747
748 for (i = 0; i < 65535; i++) {
749 if (!*sp->pptr && *sp->pid) {
750 /* ptr was invalidated but id is valid - try to recover
751 * the original or next ptr
752 */
753 *sp->pptr =
754 htb_id_find_next_upper(prio, sp->root, *sp->pid);
755 }
756 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
757 * can become out of date quickly
758 */
759 if (!*sp->pptr) { /* we are at right end; rewind & go up */
760 *sp->pptr = sp->root;
761 while ((*sp->pptr)->rb_left)
762 *sp->pptr = (*sp->pptr)->rb_left;
763 if (sp > stk) {
764 sp--;
765 if (!*sp->pptr) {
766 WARN_ON(1);
767 return NULL;
768 }
769 htb_next_rb_node(sp->pptr);
770 }
771 } else {
772 struct htb_class *cl;
773 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
774 if (!cl->level)
775 return cl;
776 (++sp)->root = cl->un.inner.feed[prio].rb_node;
777 sp->pptr = cl->un.inner.ptr + prio;
778 sp->pid = cl->un.inner.last_ptr_id + prio;
779 }
780 }
781 WARN_ON(1);
782 return NULL;
783}
784
785/* dequeues packet at given priority and level; call only if
786 * you are sure that there is active class at prio/level
787 */
788static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
789 int level)
790{
791 struct sk_buff *skb = NULL;
792 struct htb_class *cl, *start;
793 /* look initial class up in the row */
794 start = cl = htb_lookup_leaf(q->row[level] + prio, prio,
795 q->ptr[level] + prio,
796 q->last_ptr_id[level] + prio);
797
798 do {
799next:
800 if (unlikely(!cl))
801 return NULL;
802
803 /* class can be empty - it is unlikely but can be true if leaf
804 * qdisc drops packets in enqueue routine or if someone used
805 * graft operation on the leaf since last dequeue;
806 * simply deactivate and skip such class
807 */
808 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
809 struct htb_class *next;
810 htb_deactivate(q, cl);
811
812 /* row/level might become empty */
813 if ((q->row_mask[level] & (1 << prio)) == 0)
814 return NULL;
815
816 next = htb_lookup_leaf(q->row[level] + prio,
817 prio, q->ptr[level] + prio,
818 q->last_ptr_id[level] + prio);
819
820 if (cl == start) /* fix start if we just deleted it */
821 start = next;
822 cl = next;
823 goto next;
824 }
825
826 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
827 if (likely(skb != NULL))
828 break;
829
830 qdisc_warn_nonwc("htb", cl->un.leaf.q);
831 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
832 ptr[0]) + prio);
833 cl = htb_lookup_leaf(q->row[level] + prio, prio,
834 q->ptr[level] + prio,
835 q->last_ptr_id[level] + prio);
836
837 } while (cl != start);
838
839 if (likely(skb != NULL)) {
840 cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb);
841 if (cl->un.leaf.deficit[level] < 0) {
842 cl->un.leaf.deficit[level] += cl->quantum;
843 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
844 ptr[0]) + prio);
845 }
846 /* this used to be after charge_class but this constelation
847 * gives us slightly better performance
848 */
849 if (!cl->un.leaf.q->q.qlen)
850 htb_deactivate(q, cl);
851 htb_charge_class(q, cl, level, skb);
852 }
853 return skb;
854}
855
856static struct sk_buff *htb_dequeue(struct Qdisc *sch)
857{
858 struct sk_buff *skb;
859 struct htb_sched *q = qdisc_priv(sch);
860 int level;
861 psched_time_t next_event;
862 unsigned long start_at;
863
864 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
865 skb = __skb_dequeue(&q->direct_queue);
866 if (skb != NULL) {
867ok:
868 qdisc_bstats_update(sch, skb);
869 qdisc_unthrottled(sch);
870 sch->q.qlen--;
871 return skb;
872 }
873
874 if (!sch->q.qlen)
875 goto fin;
876 q->now = psched_get_time();
877 start_at = jiffies;
878
879 next_event = q->now + 5 * PSCHED_TICKS_PER_SEC;
880
881 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
882 /* common case optimization - skip event handler quickly */
883 int m;
884 psched_time_t event;
885
886 if (q->now >= q->near_ev_cache[level]) {
887 event = htb_do_events(q, level, start_at);
888 if (!event)
889 event = q->now + PSCHED_TICKS_PER_SEC;
890 q->near_ev_cache[level] = event;
891 } else
892 event = q->near_ev_cache[level];
893
894 if (next_event > event)
895 next_event = event;
896
897 m = ~q->row_mask[level];
898 while (m != (int)(-1)) {
899 int prio = ffz(m);
900
901 m |= 1 << prio;
902 skb = htb_dequeue_tree(q, prio, level);
903 if (likely(skb != NULL))
904 goto ok;
905 }
906 }
907 sch->qstats.overlimits++;
908 if (likely(next_event > q->now))
909 qdisc_watchdog_schedule(&q->watchdog, next_event);
910 else
911 schedule_work(&q->work);
912fin:
913 return skb;
914}
915
916/* try to drop from each class (by prio) until one succeed */
917static unsigned int htb_drop(struct Qdisc *sch)
918{
919 struct htb_sched *q = qdisc_priv(sch);
920 int prio;
921
922 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
923 struct list_head *p;
924 list_for_each(p, q->drops + prio) {
925 struct htb_class *cl = list_entry(p, struct htb_class,
926 un.leaf.drop_list);
927 unsigned int len;
928 if (cl->un.leaf.q->ops->drop &&
929 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
930 sch->q.qlen--;
931 if (!cl->un.leaf.q->q.qlen)
932 htb_deactivate(q, cl);
933 return len;
934 }
935 }
936 }
937 return 0;
938}
939
940/* reset all classes */
941/* always caled under BH & queue lock */
942static void htb_reset(struct Qdisc *sch)
943{
944 struct htb_sched *q = qdisc_priv(sch);
945 struct htb_class *cl;
946 struct hlist_node *n;
947 unsigned int i;
948
949 for (i = 0; i < q->clhash.hashsize; i++) {
950 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
951 if (cl->level)
952 memset(&cl->un.inner, 0, sizeof(cl->un.inner));
953 else {
954 if (cl->un.leaf.q)
955 qdisc_reset(cl->un.leaf.q);
956 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
957 }
958 cl->prio_activity = 0;
959 cl->cmode = HTB_CAN_SEND;
960
961 }
962 }
963 qdisc_watchdog_cancel(&q->watchdog);
964 __skb_queue_purge(&q->direct_queue);
965 sch->q.qlen = 0;
966 memset(q->row, 0, sizeof(q->row));
967 memset(q->row_mask, 0, sizeof(q->row_mask));
968 memset(q->wait_pq, 0, sizeof(q->wait_pq));
969 memset(q->ptr, 0, sizeof(q->ptr));
970 for (i = 0; i < TC_HTB_NUMPRIO; i++)
971 INIT_LIST_HEAD(q->drops + i);
972}
973
974static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
975 [TCA_HTB_PARMS] = { .len = sizeof(struct tc_htb_opt) },
976 [TCA_HTB_INIT] = { .len = sizeof(struct tc_htb_glob) },
977 [TCA_HTB_CTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
978 [TCA_HTB_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
979};
980
981static void htb_work_func(struct work_struct *work)
982{
983 struct htb_sched *q = container_of(work, struct htb_sched, work);
984 struct Qdisc *sch = q->watchdog.qdisc;
985
986 __netif_schedule(qdisc_root(sch));
987}
988
989static int htb_init(struct Qdisc *sch, struct nlattr *opt)
990{
991 struct htb_sched *q = qdisc_priv(sch);
992 struct nlattr *tb[TCA_HTB_INIT + 1];
993 struct tc_htb_glob *gopt;
994 int err;
995 int i;
996
997 if (!opt)
998 return -EINVAL;
999
1000 err = nla_parse_nested(tb, TCA_HTB_INIT, opt, htb_policy);
1001 if (err < 0)
1002 return err;
1003
1004 if (tb[TCA_HTB_INIT] == NULL) {
1005 pr_err("HTB: hey probably you have bad tc tool ?\n");
1006 return -EINVAL;
1007 }
1008 gopt = nla_data(tb[TCA_HTB_INIT]);
1009 if (gopt->version != HTB_VER >> 16) {
1010 pr_err("HTB: need tc/htb version %d (minor is %d), you have %d\n",
1011 HTB_VER >> 16, HTB_VER & 0xffff, gopt->version);
1012 return -EINVAL;
1013 }
1014
1015 err = qdisc_class_hash_init(&q->clhash);
1016 if (err < 0)
1017 return err;
1018 for (i = 0; i < TC_HTB_NUMPRIO; i++)
1019 INIT_LIST_HEAD(q->drops + i);
1020
1021 qdisc_watchdog_init(&q->watchdog, sch);
1022 INIT_WORK(&q->work, htb_work_func);
1023 skb_queue_head_init(&q->direct_queue);
1024
1025 q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
1026 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
1027 q->direct_qlen = 2;
1028
1029 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1030 q->rate2quantum = 1;
1031 q->defcls = gopt->defcls;
1032
1033 return 0;
1034}
1035
1036static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1037{
1038 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1039 struct htb_sched *q = qdisc_priv(sch);
1040 struct nlattr *nest;
1041 struct tc_htb_glob gopt;
1042
1043 spin_lock_bh(root_lock);
1044
1045 gopt.direct_pkts = q->direct_pkts;
1046 gopt.version = HTB_VER;
1047 gopt.rate2quantum = q->rate2quantum;
1048 gopt.defcls = q->defcls;
1049 gopt.debug = 0;
1050
1051 nest = nla_nest_start(skb, TCA_OPTIONS);
1052 if (nest == NULL)
1053 goto nla_put_failure;
1054 NLA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
1055 nla_nest_end(skb, nest);
1056
1057 spin_unlock_bh(root_lock);
1058 return skb->len;
1059
1060nla_put_failure:
1061 spin_unlock_bh(root_lock);
1062 nla_nest_cancel(skb, nest);
1063 return -1;
1064}
1065
1066static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
1067 struct sk_buff *skb, struct tcmsg *tcm)
1068{
1069 struct htb_class *cl = (struct htb_class *)arg;
1070 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1071 struct nlattr *nest;
1072 struct tc_htb_opt opt;
1073
1074 spin_lock_bh(root_lock);
1075 tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
1076 tcm->tcm_handle = cl->common.classid;
1077 if (!cl->level && cl->un.leaf.q)
1078 tcm->tcm_info = cl->un.leaf.q->handle;
1079
1080 nest = nla_nest_start(skb, TCA_OPTIONS);
1081 if (nest == NULL)
1082 goto nla_put_failure;
1083
1084 memset(&opt, 0, sizeof(opt));
1085
1086 opt.rate = cl->rate->rate;
1087 opt.buffer = cl->buffer;
1088 opt.ceil = cl->ceil->rate;
1089 opt.cbuffer = cl->cbuffer;
1090 opt.quantum = cl->quantum;
1091 opt.prio = cl->prio;
1092 opt.level = cl->level;
1093 NLA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
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");