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