blob: 5e608a64935af6b644c6ecf3596f7dd84c32d35a [file] [log] [blame]
Stephen Hemminger87990462006-08-10 23:35:16 -07001/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07002 * 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
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090014 * Ondrej Kraus, <krauso@barr.cz>
Linus Torvalds1da177e2005-04-16 15:20:36 -070015 * 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 * $Id: sch_htb.c,v 1.25 2003/12/07 11:08:25 devik Exp devik $
29 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070030#include <linux/module.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070031#include <linux/types.h>
32#include <linux/kernel.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070033#include <linux/string.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070034#include <linux/errno.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070035#include <linux/skbuff.h>
36#include <linux/list.h>
37#include <linux/compiler.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070038#include <linux/rbtree.h>
Patrick McHardy0ba48052007-07-02 22:49:07 -070039#include <net/netlink.h>
40#include <net/pkt_sched.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070041
42/* HTB algorithm.
43 Author: devik@cdi.cz
44 ========================================================================
45 HTB is like TBF with multiple classes. It is also similar to CBQ because
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090046 it allows to assign priority to each class in hierarchy.
Linus Torvalds1da177e2005-04-16 15:20:36 -070047 In fact it is another implementation of Floyd's formal sharing.
48
49 Levels:
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090050 Each class is assigned level. Leaf has ALWAYS level 0 and root
Linus Torvalds1da177e2005-04-16 15:20:36 -070051 classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
52 one less than their parent.
53*/
54
Stephen Hemminger87990462006-08-10 23:35:16 -070055#define HTB_HSIZE 16 /* classid hash size */
Stephen Hemminger87990462006-08-10 23:35:16 -070056#define HTB_HYSTERESIS 1 /* whether to use mode hysteresis for speedup */
57#define HTB_VER 0x30011 /* major must be matched with number suplied by TC as version */
Linus Torvalds1da177e2005-04-16 15:20:36 -070058
59#if HTB_VER >> 16 != TC_HTB_PROTOVER
60#error "Mismatched sch_htb.c and pkt_sch.h"
61#endif
62
Linus Torvalds1da177e2005-04-16 15:20:36 -070063/* used internaly to keep status of single class */
64enum htb_cmode {
Stephen Hemminger87990462006-08-10 23:35:16 -070065 HTB_CANT_SEND, /* class can't send and can't borrow */
66 HTB_MAY_BORROW, /* class can't send but may borrow */
67 HTB_CAN_SEND /* class can send */
Linus Torvalds1da177e2005-04-16 15:20:36 -070068};
69
70/* interior & leaf nodes; props specific to leaves are marked L: */
Stephen Hemminger87990462006-08-10 23:35:16 -070071struct htb_class {
72 /* general class parameters */
73 u32 classid;
74 struct gnet_stats_basic bstats;
75 struct gnet_stats_queue qstats;
76 struct gnet_stats_rate_est rate_est;
77 struct tc_htb_xstats xstats; /* our special stats */
78 int refcnt; /* usage count of this class */
Linus Torvalds1da177e2005-04-16 15:20:36 -070079
Stephen Hemminger87990462006-08-10 23:35:16 -070080 /* topology */
81 int level; /* our level (see above) */
82 struct htb_class *parent; /* parent class */
Stephen Hemminger0cef2962006-08-10 23:35:38 -070083 struct hlist_node hlist; /* classid hash list item */
Stephen Hemminger87990462006-08-10 23:35:16 -070084 struct list_head sibling; /* sibling list item */
85 struct list_head children; /* children list */
Linus Torvalds1da177e2005-04-16 15:20:36 -070086
Stephen Hemminger87990462006-08-10 23:35:16 -070087 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 */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700108 psched_time_t pq_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700109
Stephen Hemminger87990462006-08-10 23:35:16 -0700110 int prio_activity; /* for which prios are we active */
111 enum htb_cmode cmode; /* current mode of the class */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700112
Stephen Hemminger87990462006-08-10 23:35:16 -0700113 /* class attached filters */
114 struct tcf_proto *filter_list;
115 int filter_cnt;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700116
Stephen Hemminger87990462006-08-10 23:35:16 -0700117 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 */
Jarek Poplawski160d5e12006-12-08 00:26:56 -0800126
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. */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700130};
131
Stephen Hemminger87990462006-08-10 23:35:16 -0700132static inline long L2T(struct htb_class *cl, struct qdisc_rate_table *rate,
133 int size)
134{
Jesper Dangaard Brouere9bef552007-09-12 16:35:24 +0200135 long result = qdisc_l2t(rate, size);
136 return result;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700137}
138
Stephen Hemminger87990462006-08-10 23:35:16 -0700139struct htb_sched {
140 struct list_head root; /* root classes list */
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700141 struct hlist_head hash[HTB_HSIZE]; /* hashed by classid */
142 struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143
Stephen Hemminger87990462006-08-10 23:35:16 -0700144 /* self list - roots of self generating tree */
145 struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
146 int row_mask[TC_HTB_MAXDEPTH];
147 struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
148 u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149
Stephen Hemminger87990462006-08-10 23:35:16 -0700150 /* self wait list - roots of wait PQs per row */
151 struct rb_root wait_pq[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152
Stephen Hemminger87990462006-08-10 23:35:16 -0700153 /* time of nearest event per level (row) */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700154 psched_time_t near_ev_cache[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155
Stephen Hemminger87990462006-08-10 23:35:16 -0700156 /* whether we hit non-work conserving class during this dequeue; we use */
157 int nwc_hit; /* this to disable mindelay complaint in dequeue */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700158
Stephen Hemminger87990462006-08-10 23:35:16 -0700159 int defcls; /* class where unclassified flows go to */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700160
Stephen Hemminger87990462006-08-10 23:35:16 -0700161 /* filters for qdisc itself */
162 struct tcf_proto *filter_list;
163 int filter_cnt;
164
165 int rate2quantum; /* quant = rate / rate2quantum */
166 psched_time_t now; /* cached dequeue time */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700167 struct qdisc_watchdog watchdog;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168
Stephen Hemminger87990462006-08-10 23:35:16 -0700169 /* non shaped skbs; let them go directly thru */
170 struct sk_buff_head direct_queue;
171 int direct_qlen; /* max qlen of above */
172
173 long direct_pkts;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174};
175
176/* compute hash of size HTB_HSIZE for given handle */
Stephen Hemminger87990462006-08-10 23:35:16 -0700177static inline int htb_hash(u32 h)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700178{
179#if HTB_HSIZE != 16
Stephen Hemminger87990462006-08-10 23:35:16 -0700180#error "Declare new hash for your HTB_HSIZE"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700181#endif
Stephen Hemminger87990462006-08-10 23:35:16 -0700182 h ^= h >> 8; /* stolen from cbq_hash */
183 h ^= h >> 4;
184 return h & 0xf;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700185}
186
187/* find class in global hash table using given handle */
Stephen Hemminger87990462006-08-10 23:35:16 -0700188static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189{
190 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700191 struct hlist_node *p;
192 struct htb_class *cl;
193
Stephen Hemminger87990462006-08-10 23:35:16 -0700194 if (TC_H_MAJ(handle) != sch->handle)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700195 return NULL;
Stephen Hemminger87990462006-08-10 23:35:16 -0700196
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700197 hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700198 if (cl->classid == handle)
199 return cl;
200 }
201 return NULL;
202}
203
204/**
205 * htb_classify - classify a packet into class
206 *
207 * It returns NULL if the packet should be dropped or -1 if the packet
208 * should be passed directly thru. In all other cases leaf class is returned.
209 * We allow direct class selection by classid in priority. The we examine
210 * filters in qdisc and in inner nodes (if higher filter points to the inner
211 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900212 * internal fifo (direct). These packets then go directly thru. If we still
Linus Torvalds1da177e2005-04-16 15:20:36 -0700213 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
214 * then finish and return direct queue.
215 */
216#define HTB_DIRECT (struct htb_class*)-1
217static inline u32 htb_classid(struct htb_class *cl)
218{
219 return (cl && cl != HTB_DIRECT) ? cl->classid : TC_H_UNSPEC;
220}
221
Stephen Hemminger87990462006-08-10 23:35:16 -0700222static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
223 int *qerr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224{
225 struct htb_sched *q = qdisc_priv(sch);
226 struct htb_class *cl;
227 struct tcf_result res;
228 struct tcf_proto *tcf;
229 int result;
230
231 /* allow to select class by setting skb->priority to valid classid;
232 note that nfmark can be used too by attaching filter fw with no
233 rules in it */
234 if (skb->priority == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700235 return HTB_DIRECT; /* X:0 (direct flow) selected */
236 if ((cl = htb_find(skb->priority, sch)) != NULL && cl->level == 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700237 return cl;
238
Jamal Hadi Salim29f1df62006-01-08 22:35:55 -0800239 *qerr = NET_XMIT_BYPASS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700240 tcf = q->filter_list;
241 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
242#ifdef CONFIG_NET_CLS_ACT
243 switch (result) {
244 case TC_ACT_QUEUED:
Stephen Hemminger87990462006-08-10 23:35:16 -0700245 case TC_ACT_STOLEN:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700246 *qerr = NET_XMIT_SUCCESS;
247 case TC_ACT_SHOT:
248 return NULL;
249 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700250#endif
Stephen Hemminger87990462006-08-10 23:35:16 -0700251 if ((cl = (void *)res.class) == NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700252 if (res.classid == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700253 return HTB_DIRECT; /* X:0 (direct flow) */
254 if ((cl = htb_find(res.classid, sch)) == NULL)
255 break; /* filter selected invalid classid */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256 }
257 if (!cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700258 return cl; /* we hit leaf; return it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700259
260 /* we have got inner class; apply inner filter chain */
261 tcf = cl->filter_list;
262 }
263 /* classification failed; try to use default class */
Stephen Hemminger87990462006-08-10 23:35:16 -0700264 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700265 if (!cl || cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700266 return HTB_DIRECT; /* bad default .. this is safe bet */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700267 return cl;
268}
269
Linus Torvalds1da177e2005-04-16 15:20:36 -0700270/**
271 * htb_add_to_id_tree - adds class to the round robin list
272 *
273 * Routine adds class to the list (actually tree) sorted by classid.
274 * Make sure that class is not already on such list for given prio.
275 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700276static void htb_add_to_id_tree(struct rb_root *root,
277 struct htb_class *cl, int prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700278{
279 struct rb_node **p = &root->rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700280
Linus Torvalds1da177e2005-04-16 15:20:36 -0700281 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700282 struct htb_class *c;
283 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700284 c = rb_entry(parent, struct htb_class, node[prio]);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700285
Linus Torvalds1da177e2005-04-16 15:20:36 -0700286 if (cl->classid > c->classid)
287 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700288 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700289 p = &parent->rb_left;
290 }
291 rb_link_node(&cl->node[prio], parent, p);
292 rb_insert_color(&cl->node[prio], root);
293}
294
295/**
296 * htb_add_to_wait_tree - adds class to the event queue with delay
297 *
298 * The class is added to priority event queue to indicate that class will
299 * change its mode in cl->pq_key microseconds. Make sure that class is not
300 * already in the queue.
301 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700302static void htb_add_to_wait_tree(struct htb_sched *q,
303 struct htb_class *cl, long delay)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700304{
305 struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700306
Patrick McHardyfb983d42007-03-16 01:22:39 -0700307 cl->pq_key = q->now + delay;
308 if (cl->pq_key == q->now)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700309 cl->pq_key++;
310
311 /* update the nearest event cache */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700312 if (q->near_ev_cache[cl->level] > cl->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700313 q->near_ev_cache[cl->level] = cl->pq_key;
Stephen Hemminger87990462006-08-10 23:35:16 -0700314
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700316 struct htb_class *c;
317 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700318 c = rb_entry(parent, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700319 if (cl->pq_key >= c->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700320 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700321 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700322 p = &parent->rb_left;
323 }
324 rb_link_node(&cl->pq_node, parent, p);
325 rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
326}
327
328/**
329 * htb_next_rb_node - finds next node in binary tree
330 *
331 * When we are past last key we return NULL.
332 * Average complexity is 2 steps per call.
333 */
Stephen Hemminger3696f622006-08-10 23:36:01 -0700334static inline void htb_next_rb_node(struct rb_node **n)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700335{
336 *n = rb_next(*n);
337}
338
339/**
340 * htb_add_class_to_row - add class to its row
341 *
342 * The class is added to row at priorities marked in mask.
343 * It does nothing if mask == 0.
344 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700345static inline void htb_add_class_to_row(struct htb_sched *q,
346 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700347{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700348 q->row_mask[cl->level] |= mask;
349 while (mask) {
350 int prio = ffz(~mask);
351 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700352 htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700353 }
354}
355
Stephen Hemminger3696f622006-08-10 23:36:01 -0700356/* If this triggers, it is a bug in this code, but it need not be fatal */
357static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
358{
Ismail Donmez81771b32006-10-03 13:49:10 -0700359 if (RB_EMPTY_NODE(rb)) {
Stephen Hemminger3696f622006-08-10 23:36:01 -0700360 WARN_ON(1);
361 } else {
362 rb_erase(rb, root);
363 RB_CLEAR_NODE(rb);
364 }
365}
366
367
Linus Torvalds1da177e2005-04-16 15:20:36 -0700368/**
369 * htb_remove_class_from_row - removes class from its row
370 *
371 * The class is removed from row at priorities marked in mask.
372 * It does nothing if mask == 0.
373 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700374static inline void htb_remove_class_from_row(struct htb_sched *q,
375 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376{
377 int m = 0;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700378
Linus Torvalds1da177e2005-04-16 15:20:36 -0700379 while (mask) {
380 int prio = ffz(~mask);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700381
Linus Torvalds1da177e2005-04-16 15:20:36 -0700382 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700383 if (q->ptr[cl->level][prio] == cl->node + prio)
384 htb_next_rb_node(q->ptr[cl->level] + prio);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700385
386 htb_safe_rb_erase(cl->node + prio, q->row[cl->level] + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700387 if (!q->row[cl->level][prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388 m |= 1 << prio;
389 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390 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
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900397 * for priorities it is participating on. cl->cmode must be new
Linus Torvalds1da177e2005-04-16 15:20:36 -0700398 * (activated) mode. It does nothing if cl->prio_activity == 0.
399 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700400static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700401{
402 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700403 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700404
405 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700406 m = mask;
407 while (m) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700408 int prio = ffz(~m);
409 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700410
Linus Torvalds1da177e2005-04-16 15:20:36 -0700411 if (p->un.inner.feed[prio].rb_node)
412 /* parent already has its feed in use so that
413 reset bit in mask as parent is already ok */
414 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700415
416 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700417 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700418 p->prio_activity |= mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700419 cl = p;
420 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700421
Linus Torvalds1da177e2005-04-16 15:20:36 -0700422 }
423 if (cl->cmode == HTB_CAN_SEND && mask)
Stephen Hemminger87990462006-08-10 23:35:16 -0700424 htb_add_class_to_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425}
426
427/**
428 * htb_deactivate_prios - remove class from feed chain
429 *
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900430 * cl->cmode must represent old mode (before deactivation). It does
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431 * nothing if cl->prio_activity == 0. Class is removed from all feed
432 * chains and rows.
433 */
434static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
435{
436 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700437 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438
439 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700440 m = mask;
441 mask = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700442 while (m) {
443 int prio = ffz(~m);
444 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700445
446 if (p->un.inner.ptr[prio] == cl->node + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700447 /* we are removing child which is pointed to from
448 parent feed - forget the pointer but remember
449 classid */
450 p->un.inner.last_ptr_id[prio] = cl->classid;
451 p->un.inner.ptr[prio] = NULL;
452 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700453
Stephen Hemminger3696f622006-08-10 23:36:01 -0700454 htb_safe_rb_erase(cl->node + prio, p->un.inner.feed + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700455
456 if (!p->un.inner.feed[prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700457 mask |= 1 << prio;
458 }
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700459
Linus Torvalds1da177e2005-04-16 15:20:36 -0700460 p->prio_activity &= ~mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700461 cl = p;
462 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700463
Linus Torvalds1da177e2005-04-16 15:20:36 -0700464 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700465 if (cl->cmode == HTB_CAN_SEND && mask)
466 htb_remove_class_from_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467}
468
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700469#if HTB_HYSTERESIS
470static inline long htb_lowater(const struct htb_class *cl)
471{
472 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
473}
474static inline long htb_hiwater(const struct htb_class *cl)
475{
476 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
477}
478#else
479#define htb_lowater(cl) (0)
480#define htb_hiwater(cl) (0)
481#endif
482
Linus Torvalds1da177e2005-04-16 15:20:36 -0700483/**
484 * htb_class_mode - computes and returns current class mode
485 *
486 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
487 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900488 * from now to time when cl will change its state.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700489 * Also it is worth to note that class mode doesn't change simply
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900490 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
Linus Torvalds1da177e2005-04-16 15:20:36 -0700491 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
492 * mode transitions per time unit. The speed gain is about 1/6.
493 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700494static inline enum htb_cmode
495htb_class_mode(struct htb_class *cl, long *diff)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700496{
Stephen Hemminger87990462006-08-10 23:35:16 -0700497 long toks;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700498
Stephen Hemminger87990462006-08-10 23:35:16 -0700499 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
500 *diff = -toks;
501 return HTB_CANT_SEND;
502 }
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700503
Stephen Hemminger87990462006-08-10 23:35:16 -0700504 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
505 return HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700506
Stephen Hemminger87990462006-08-10 23:35:16 -0700507 *diff = -toks;
508 return HTB_MAY_BORROW;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700509}
510
511/**
512 * htb_change_class_mode - changes classe's mode
513 *
514 * This should be the only way how to change classe's mode under normal
515 * cirsumstances. Routine will update feed lists linkage, change mode
516 * and add class to the wait event queue if appropriate. New mode should
517 * be different from old one and cl->pq_key has to be valid if changing
518 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
519 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700520static void
Linus Torvalds1da177e2005-04-16 15:20:36 -0700521htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
Stephen Hemminger87990462006-08-10 23:35:16 -0700522{
523 enum htb_cmode new_mode = htb_class_mode(cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700524
525 if (new_mode == cl->cmode)
Stephen Hemminger87990462006-08-10 23:35:16 -0700526 return;
527
528 if (cl->prio_activity) { /* not necessary: speed optimization */
529 if (cl->cmode != HTB_CANT_SEND)
530 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531 cl->cmode = new_mode;
Stephen Hemminger87990462006-08-10 23:35:16 -0700532 if (new_mode != HTB_CANT_SEND)
533 htb_activate_prios(q, cl);
534 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700535 cl->cmode = new_mode;
536}
537
538/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900539 * htb_activate - inserts leaf cl into appropriate active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700540 *
541 * Routine learns (new) priority of leaf and activates feed chain
542 * for the prio. It can be called on already active leaf safely.
543 * It also adds leaf into droplist.
544 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700545static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700546{
547 BUG_TRAP(!cl->level && cl->un.leaf.q && cl->un.leaf.q->q.qlen);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700548
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549 if (!cl->prio_activity) {
550 cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700551 htb_activate_prios(q, cl);
552 list_add_tail(&cl->un.leaf.drop_list,
553 q->drops + cl->un.leaf.aprio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554 }
555}
556
557/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900558 * htb_deactivate - remove leaf cl from active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559 *
560 * Make sure that leaf is active. In the other words it can't be called
561 * with non-active leaf. It also removes class from the drop list.
562 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700563static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564{
565 BUG_TRAP(cl->prio_activity);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700566
Stephen Hemminger87990462006-08-10 23:35:16 -0700567 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700568 cl->prio_activity = 0;
569 list_del_init(&cl->un.leaf.drop_list);
570}
571
572static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
573{
Stephen Hemminger87990462006-08-10 23:35:16 -0700574 int ret;
575 struct htb_sched *q = qdisc_priv(sch);
576 struct htb_class *cl = htb_classify(skb, sch, &ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577
Stephen Hemminger87990462006-08-10 23:35:16 -0700578 if (cl == HTB_DIRECT) {
579 /* enqueue to helper queue */
580 if (q->direct_queue.qlen < q->direct_qlen) {
581 __skb_queue_tail(&q->direct_queue, skb);
582 q->direct_pkts++;
583 } else {
584 kfree_skb(skb);
585 sch->qstats.drops++;
586 return NET_XMIT_DROP;
587 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700588#ifdef CONFIG_NET_CLS_ACT
Stephen Hemminger87990462006-08-10 23:35:16 -0700589 } else if (!cl) {
590 if (ret == NET_XMIT_BYPASS)
591 sch->qstats.drops++;
592 kfree_skb(skb);
593 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700594#endif
Stephen Hemminger87990462006-08-10 23:35:16 -0700595 } else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) !=
596 NET_XMIT_SUCCESS) {
597 sch->qstats.drops++;
598 cl->qstats.drops++;
599 return NET_XMIT_DROP;
600 } else {
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700601 cl->bstats.packets +=
602 skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
Stephen Hemminger87990462006-08-10 23:35:16 -0700603 cl->bstats.bytes += skb->len;
604 htb_activate(q, cl);
605 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700606
Stephen Hemminger87990462006-08-10 23:35:16 -0700607 sch->q.qlen++;
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700608 sch->bstats.packets += skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
Stephen Hemminger87990462006-08-10 23:35:16 -0700609 sch->bstats.bytes += skb->len;
610 return NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700611}
612
613/* TODO: requeuing packet charges it to policers again !! */
614static int htb_requeue(struct sk_buff *skb, struct Qdisc *sch)
615{
Stephen Hemminger87990462006-08-10 23:35:16 -0700616 struct htb_sched *q = qdisc_priv(sch);
617 int ret = NET_XMIT_SUCCESS;
618 struct htb_class *cl = htb_classify(skb, sch, &ret);
619 struct sk_buff *tskb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700620
Stephen Hemminger87990462006-08-10 23:35:16 -0700621 if (cl == HTB_DIRECT || !cl) {
622 /* enqueue to helper queue */
623 if (q->direct_queue.qlen < q->direct_qlen && cl) {
624 __skb_queue_head(&q->direct_queue, skb);
625 } else {
626 __skb_queue_head(&q->direct_queue, skb);
627 tskb = __skb_dequeue_tail(&q->direct_queue);
628 kfree_skb(tskb);
629 sch->qstats.drops++;
630 return NET_XMIT_CN;
631 }
632 } else if (cl->un.leaf.q->ops->requeue(skb, cl->un.leaf.q) !=
633 NET_XMIT_SUCCESS) {
634 sch->qstats.drops++;
635 cl->qstats.drops++;
636 return NET_XMIT_DROP;
637 } else
638 htb_activate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700639
Stephen Hemminger87990462006-08-10 23:35:16 -0700640 sch->q.qlen++;
641 sch->qstats.requeues++;
642 return NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700643}
644
Linus Torvalds1da177e2005-04-16 15:20:36 -0700645/**
646 * htb_charge_class - charges amount "bytes" to leaf and ancestors
647 *
648 * Routine assumes that packet "bytes" long was dequeued from leaf cl
649 * borrowing from "level". It accounts bytes to ceil leaky bucket for
650 * leaf and all ancestors and to rate bucket for ancestors at levels
651 * "level" and higher. It also handles possible change of mode resulting
652 * from the update. Note that mode can also increase here (MAY_BORROW to
653 * CAN_SEND) because we can use more precise clock that event queue here.
654 * In such case we remove class from event queue first.
655 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700656static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700657 int level, struct sk_buff *skb)
Stephen Hemminger87990462006-08-10 23:35:16 -0700658{
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700659 int bytes = skb->len;
Stephen Hemminger87990462006-08-10 23:35:16 -0700660 long toks, diff;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700661 enum htb_cmode old_mode;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662
663#define HTB_ACCNT(T,B,R) toks = diff + cl->T; \
664 if (toks > cl->B) toks = cl->B; \
665 toks -= L2T(cl, cl->R, bytes); \
666 if (toks <= -cl->mbuffer) toks = 1-cl->mbuffer; \
667 cl->T = toks
668
669 while (cl) {
Patrick McHardy03cc45c2007-03-23 11:29:11 -0700670 diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700671 if (cl->level >= level) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700672 if (cl->level == level)
673 cl->xstats.lends++;
674 HTB_ACCNT(tokens, buffer, rate);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675 } else {
676 cl->xstats.borrows++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700677 cl->tokens += diff; /* we moved t_c; update tokens */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700678 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700679 HTB_ACCNT(ctokens, cbuffer, ceil);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680 cl->t_c = q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700681
Stephen Hemminger87990462006-08-10 23:35:16 -0700682 old_mode = cl->cmode;
683 diff = 0;
684 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685 if (old_mode != cl->cmode) {
686 if (old_mode != HTB_CAN_SEND)
Stephen Hemminger3696f622006-08-10 23:36:01 -0700687 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700688 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700689 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700690 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700691
692 /* update byte stats except for leaves which are already updated */
693 if (cl->level) {
694 cl->bstats.bytes += bytes;
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700695 cl->bstats.packets += skb_is_gso(skb)?
696 skb_shinfo(skb)->gso_segs:1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700697 }
698 cl = cl->parent;
699 }
700}
701
702/**
703 * htb_do_events - make mode changes to classes at the level
704 *
Patrick McHardyfb983d42007-03-16 01:22:39 -0700705 * Scans event queue for pending events and applies them. Returns time of
Linus Torvalds1da177e2005-04-16 15:20:36 -0700706 * next pending event (0 for no event in pq).
Patrick McHardyfb983d42007-03-16 01:22:39 -0700707 * Note: Applied are events whose have cl->pq_key <= q->now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700708 */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700709static psched_time_t htb_do_events(struct htb_sched *q, int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700710{
711 int i;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700712
Linus Torvalds1da177e2005-04-16 15:20:36 -0700713 for (i = 0; i < 500; i++) {
714 struct htb_class *cl;
715 long diff;
Akinbou Mita30bdbe32006-10-12 01:52:05 -0700716 struct rb_node *p = rb_first(&q->wait_pq[level]);
717
Stephen Hemminger87990462006-08-10 23:35:16 -0700718 if (!p)
719 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720
721 cl = rb_entry(p, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700722 if (cl->pq_key > q->now)
723 return cl->pq_key;
724
Stephen Hemminger3696f622006-08-10 23:36:01 -0700725 htb_safe_rb_erase(p, q->wait_pq + level);
Patrick McHardy03cc45c2007-03-23 11:29:11 -0700726 diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
Stephen Hemminger87990462006-08-10 23:35:16 -0700727 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700728 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700729 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700730 }
731 if (net_ratelimit())
732 printk(KERN_WARNING "htb: too many events !\n");
Patrick McHardyfb983d42007-03-16 01:22:39 -0700733 return q->now + PSCHED_TICKS_PER_SEC / 10;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700734}
735
736/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
737 is no such one exists. */
Stephen Hemminger87990462006-08-10 23:35:16 -0700738static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
739 u32 id)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700740{
741 struct rb_node *r = NULL;
742 while (n) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700743 struct htb_class *cl =
744 rb_entry(n, struct htb_class, node[prio]);
745 if (id == cl->classid)
746 return n;
747
Linus Torvalds1da177e2005-04-16 15:20:36 -0700748 if (id > cl->classid) {
749 n = n->rb_right;
750 } else {
751 r = n;
752 n = n->rb_left;
753 }
754 }
755 return r;
756}
757
758/**
759 * htb_lookup_leaf - returns next leaf class in DRR order
760 *
761 * Find leaf where current feed pointers points to.
762 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700763static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio,
764 struct rb_node **pptr, u32 * pid)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700765{
766 int i;
767 struct {
768 struct rb_node *root;
769 struct rb_node **pptr;
770 u32 *pid;
Stephen Hemminger87990462006-08-10 23:35:16 -0700771 } stk[TC_HTB_MAXDEPTH], *sp = stk;
772
Linus Torvalds1da177e2005-04-16 15:20:36 -0700773 BUG_TRAP(tree->rb_node);
774 sp->root = tree->rb_node;
775 sp->pptr = pptr;
776 sp->pid = pid;
777
778 for (i = 0; i < 65535; i++) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700779 if (!*sp->pptr && *sp->pid) {
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900780 /* ptr was invalidated but id is valid - try to recover
Linus Torvalds1da177e2005-04-16 15:20:36 -0700781 the original or next ptr */
Stephen Hemminger87990462006-08-10 23:35:16 -0700782 *sp->pptr =
783 htb_id_find_next_upper(prio, sp->root, *sp->pid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700784 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700785 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
786 can become out of date quickly */
787 if (!*sp->pptr) { /* we are at right end; rewind & go up */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700788 *sp->pptr = sp->root;
Stephen Hemminger87990462006-08-10 23:35:16 -0700789 while ((*sp->pptr)->rb_left)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700790 *sp->pptr = (*sp->pptr)->rb_left;
791 if (sp > stk) {
792 sp--;
Stephen Hemminger87990462006-08-10 23:35:16 -0700793 BUG_TRAP(*sp->pptr);
794 if (!*sp->pptr)
795 return NULL;
796 htb_next_rb_node(sp->pptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700797 }
798 } else {
799 struct htb_class *cl;
Stephen Hemminger87990462006-08-10 23:35:16 -0700800 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
801 if (!cl->level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700802 return cl;
803 (++sp)->root = cl->un.inner.feed[prio].rb_node;
Stephen Hemminger87990462006-08-10 23:35:16 -0700804 sp->pptr = cl->un.inner.ptr + prio;
805 sp->pid = cl->un.inner.last_ptr_id + prio;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700806 }
807 }
808 BUG_TRAP(0);
809 return NULL;
810}
811
812/* dequeues packet at given priority and level; call only if
813 you are sure that there is active class at prio/level */
Stephen Hemminger87990462006-08-10 23:35:16 -0700814static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
815 int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700816{
817 struct sk_buff *skb = NULL;
Stephen Hemminger87990462006-08-10 23:35:16 -0700818 struct htb_class *cl, *start;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700819 /* look initial class up in the row */
Stephen Hemminger87990462006-08-10 23:35:16 -0700820 start = cl = htb_lookup_leaf(q->row[level] + prio, prio,
821 q->ptr[level] + prio,
822 q->last_ptr_id[level] + prio);
823
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824 do {
825next:
Stephen Hemminger87990462006-08-10 23:35:16 -0700826 BUG_TRAP(cl);
827 if (!cl)
828 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700829
830 /* class can be empty - it is unlikely but can be true if leaf
831 qdisc drops packets in enqueue routine or if someone used
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900832 graft operation on the leaf since last dequeue;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700833 simply deactivate and skip such class */
834 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
835 struct htb_class *next;
Stephen Hemminger87990462006-08-10 23:35:16 -0700836 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700837
838 /* row/level might become empty */
839 if ((q->row_mask[level] & (1 << prio)) == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -0700840 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700841
Stephen Hemminger87990462006-08-10 23:35:16 -0700842 next = htb_lookup_leaf(q->row[level] + prio,
843 prio, q->ptr[level] + prio,
844 q->last_ptr_id[level] + prio);
845
846 if (cl == start) /* fix start if we just deleted it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700847 start = next;
848 cl = next;
849 goto next;
850 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700851
852 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
853 if (likely(skb != NULL))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700854 break;
855 if (!cl->warned) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700856 printk(KERN_WARNING
857 "htb: class %X isn't work conserving ?!\n",
858 cl->classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700859 cl->warned = 1;
860 }
861 q->nwc_hit++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700862 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
863 ptr[0]) + prio);
864 cl = htb_lookup_leaf(q->row[level] + prio, prio,
865 q->ptr[level] + prio,
866 q->last_ptr_id[level] + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867
868 } while (cl != start);
869
870 if (likely(skb != NULL)) {
871 if ((cl->un.leaf.deficit[level] -= skb->len) < 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700872 cl->un.leaf.deficit[level] += cl->un.leaf.quantum;
Stephen Hemminger87990462006-08-10 23:35:16 -0700873 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
874 ptr[0]) + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875 }
876 /* this used to be after charge_class but this constelation
877 gives us slightly better performance */
878 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700879 htb_deactivate(q, cl);
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700880 htb_charge_class(q, cl, level, skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700881 }
882 return skb;
883}
884
Linus Torvalds1da177e2005-04-16 15:20:36 -0700885static struct sk_buff *htb_dequeue(struct Qdisc *sch)
886{
887 struct sk_buff *skb = NULL;
888 struct htb_sched *q = qdisc_priv(sch);
889 int level;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700890 psched_time_t next_event;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700891
892 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
Stephen Hemminger87990462006-08-10 23:35:16 -0700893 skb = __skb_dequeue(&q->direct_queue);
894 if (skb != NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895 sch->flags &= ~TCQ_F_THROTTLED;
896 sch->q.qlen--;
897 return skb;
898 }
899
Stephen Hemminger87990462006-08-10 23:35:16 -0700900 if (!sch->q.qlen)
901 goto fin;
Patrick McHardy3bebcda2007-03-23 11:29:25 -0700902 q->now = psched_get_time();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700903
Patrick McHardyfb983d42007-03-16 01:22:39 -0700904 next_event = q->now + 5 * PSCHED_TICKS_PER_SEC;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700905 q->nwc_hit = 0;
906 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
907 /* common case optimization - skip event handler quickly */
908 int m;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700909 psched_time_t event;
Stephen Hemminger87990462006-08-10 23:35:16 -0700910
Patrick McHardyfb983d42007-03-16 01:22:39 -0700911 if (q->now >= q->near_ev_cache[level]) {
912 event = htb_do_events(q, level);
Patrick McHardy2e4b3b02007-05-23 23:39:54 -0700913 if (!event)
914 event = q->now + PSCHED_TICKS_PER_SEC;
915 q->near_ev_cache[level] = event;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700916 } else
917 event = q->near_ev_cache[level];
918
919 if (event && next_event > event)
920 next_event = event;
921
Linus Torvalds1da177e2005-04-16 15:20:36 -0700922 m = ~q->row_mask[level];
923 while (m != (int)(-1)) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700924 int prio = ffz(m);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700925 m |= 1 << prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700926 skb = htb_dequeue_tree(q, prio, level);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700927 if (likely(skb != NULL)) {
928 sch->q.qlen--;
929 sch->flags &= ~TCQ_F_THROTTLED;
930 goto fin;
931 }
932 }
933 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700934 sch->qstats.overlimits++;
935 qdisc_watchdog_schedule(&q->watchdog, next_event);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700936fin:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700937 return skb;
938}
939
940/* try to drop from each class (by prio) until one succeed */
Stephen Hemminger87990462006-08-10 23:35:16 -0700941static unsigned int htb_drop(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700942{
943 struct htb_sched *q = qdisc_priv(sch);
944 int prio;
945
946 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
947 struct list_head *p;
Stephen Hemminger87990462006-08-10 23:35:16 -0700948 list_for_each(p, q->drops + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700949 struct htb_class *cl = list_entry(p, struct htb_class,
950 un.leaf.drop_list);
951 unsigned int len;
Stephen Hemminger87990462006-08-10 23:35:16 -0700952 if (cl->un.leaf.q->ops->drop &&
953 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700954 sch->q.qlen--;
955 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700956 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700957 return len;
958 }
959 }
960 }
961 return 0;
962}
963
964/* reset all classes */
965/* always caled under BH & queue lock */
Stephen Hemminger87990462006-08-10 23:35:16 -0700966static void htb_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700967{
968 struct htb_sched *q = qdisc_priv(sch);
969 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700970
971 for (i = 0; i < HTB_HSIZE; i++) {
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700972 struct hlist_node *p;
973 struct htb_class *cl;
974
975 hlist_for_each_entry(cl, p, q->hash + i, hlist) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700976 if (cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700977 memset(&cl->un.inner, 0, sizeof(cl->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700978 else {
Stephen Hemminger87990462006-08-10 23:35:16 -0700979 if (cl->un.leaf.q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980 qdisc_reset(cl->un.leaf.q);
981 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
982 }
983 cl->prio_activity = 0;
984 cl->cmode = HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700985
986 }
987 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700988 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700989 __skb_queue_purge(&q->direct_queue);
990 sch->q.qlen = 0;
Stephen Hemminger87990462006-08-10 23:35:16 -0700991 memset(q->row, 0, sizeof(q->row));
992 memset(q->row_mask, 0, sizeof(q->row_mask));
993 memset(q->wait_pq, 0, sizeof(q->wait_pq));
994 memset(q->ptr, 0, sizeof(q->ptr));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700995 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -0700996 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700997}
998
999static int htb_init(struct Qdisc *sch, struct rtattr *opt)
1000{
1001 struct htb_sched *q = qdisc_priv(sch);
1002 struct rtattr *tb[TCA_HTB_INIT];
1003 struct tc_htb_glob *gopt;
1004 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001005 if (!opt || rtattr_parse_nested(tb, TCA_HTB_INIT, opt) ||
Stephen Hemminger87990462006-08-10 23:35:16 -07001006 tb[TCA_HTB_INIT - 1] == NULL ||
1007 RTA_PAYLOAD(tb[TCA_HTB_INIT - 1]) < sizeof(*gopt)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001008 printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n");
1009 return -EINVAL;
1010 }
Stephen Hemminger87990462006-08-10 23:35:16 -07001011 gopt = RTA_DATA(tb[TCA_HTB_INIT - 1]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001012 if (gopt->version != HTB_VER >> 16) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001013 printk(KERN_ERR
1014 "HTB: need tc/htb version %d (minor is %d), you have %d\n",
1015 HTB_VER >> 16, HTB_VER & 0xffff, gopt->version);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001016 return -EINVAL;
1017 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001018
1019 INIT_LIST_HEAD(&q->root);
1020 for (i = 0; i < HTB_HSIZE; i++)
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001021 INIT_HLIST_HEAD(q->hash + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001022 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -07001023 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001024
Patrick McHardyfb983d42007-03-16 01:22:39 -07001025 qdisc_watchdog_init(&q->watchdog, sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001026 skb_queue_head_init(&q->direct_queue);
1027
1028 q->direct_qlen = sch->dev->tx_queue_len;
Stephen Hemminger87990462006-08-10 23:35:16 -07001029 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001030 q->direct_qlen = 2;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001031
Linus Torvalds1da177e2005-04-16 15:20:36 -07001032 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1033 q->rate2quantum = 1;
1034 q->defcls = gopt->defcls;
1035
1036 return 0;
1037}
1038
1039static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1040{
1041 struct htb_sched *q = qdisc_priv(sch);
Arnaldo Carvalho de Melo27a884d2007-04-19 20:29:13 -07001042 unsigned char *b = skb_tail_pointer(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001043 struct rtattr *rta;
1044 struct tc_htb_glob gopt;
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001045 spin_lock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001046 gopt.direct_pkts = q->direct_pkts;
1047
Linus Torvalds1da177e2005-04-16 15:20:36 -07001048 gopt.version = HTB_VER;
1049 gopt.rate2quantum = q->rate2quantum;
1050 gopt.defcls = q->defcls;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001051 gopt.debug = 0;
Stephen Hemminger87990462006-08-10 23:35:16 -07001052 rta = (struct rtattr *)b;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001053 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1054 RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
Arnaldo Carvalho de Melo27a884d2007-04-19 20:29:13 -07001055 rta->rta_len = skb_tail_pointer(skb) - b;
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001056 spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001057 return skb->len;
1058rtattr_failure:
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001059 spin_unlock_bh(&sch->dev->queue_lock);
Arnaldo Carvalho de Melodc5fc572007-03-25 23:06:12 -07001060 nlmsg_trim(skb, skb_tail_pointer(skb));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001061 return -1;
1062}
1063
1064static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
Stephen Hemminger87990462006-08-10 23:35:16 -07001065 struct sk_buff *skb, struct tcmsg *tcm)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001066{
Stephen Hemminger87990462006-08-10 23:35:16 -07001067 struct htb_class *cl = (struct htb_class *)arg;
Arnaldo Carvalho de Melo27a884d2007-04-19 20:29:13 -07001068 unsigned char *b = skb_tail_pointer(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001069 struct rtattr *rta;
1070 struct tc_htb_opt opt;
1071
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001072 spin_lock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001073 tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
1074 tcm->tcm_handle = cl->classid;
1075 if (!cl->level && cl->un.leaf.q)
1076 tcm->tcm_info = cl->un.leaf.q->handle;
1077
Stephen Hemminger87990462006-08-10 23:35:16 -07001078 rta = (struct rtattr *)b;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001079 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1080
Stephen Hemminger87990462006-08-10 23:35:16 -07001081 memset(&opt, 0, sizeof(opt));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001082
Stephen Hemminger87990462006-08-10 23:35:16 -07001083 opt.rate = cl->rate->rate;
1084 opt.buffer = cl->buffer;
1085 opt.ceil = cl->ceil->rate;
1086 opt.cbuffer = cl->cbuffer;
1087 opt.quantum = cl->un.leaf.quantum;
1088 opt.prio = cl->un.leaf.prio;
1089 opt.level = cl->level;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001090 RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
Arnaldo Carvalho de Melo27a884d2007-04-19 20:29:13 -07001091 rta->rta_len = skb_tail_pointer(skb) - b;
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001092 spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001093 return skb->len;
1094rtattr_failure:
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001095 spin_unlock_bh(&sch->dev->queue_lock);
Arnaldo Carvalho de Melodc5fc572007-03-25 23:06:12 -07001096 nlmsg_trim(skb, b);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001097 return -1;
1098}
1099
1100static int
Stephen Hemminger87990462006-08-10 23:35:16 -07001101htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001102{
Stephen Hemminger87990462006-08-10 23:35:16 -07001103 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001104
Linus Torvalds1da177e2005-04-16 15:20:36 -07001105 if (!cl->level && cl->un.leaf.q)
1106 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
1107 cl->xstats.tokens = cl->tokens;
1108 cl->xstats.ctokens = cl->ctokens;
1109
1110 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1111 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1112 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1113 return -1;
1114
1115 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1116}
1117
1118static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
Stephen Hemminger87990462006-08-10 23:35:16 -07001119 struct Qdisc **old)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001120{
Stephen Hemminger87990462006-08-10 23:35:16 -07001121 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001122
1123 if (cl && !cl->level) {
Patrick McHardy9f9afec2006-11-29 17:35:18 -08001124 if (new == NULL &&
1125 (new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +09001126 cl->classid))
Stephen Hemminger87990462006-08-10 23:35:16 -07001127 == NULL)
1128 return -ENOBUFS;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001129 sch_tree_lock(sch);
1130 if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001131 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001132 qdisc_reset(*old);
1133 }
1134 sch_tree_unlock(sch);
1135 return 0;
1136 }
1137 return -ENOENT;
1138}
1139
Stephen Hemminger87990462006-08-10 23:35:16 -07001140static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001141{
Stephen Hemminger87990462006-08-10 23:35:16 -07001142 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001143 return (cl && !cl->level) ? cl->un.leaf.q : NULL;
1144}
1145
Patrick McHardy256d61b2006-11-29 17:37:05 -08001146static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
1147{
1148 struct htb_class *cl = (struct htb_class *)arg;
1149
1150 if (cl->un.leaf.q->q.qlen == 0)
1151 htb_deactivate(qdisc_priv(sch), cl);
1152}
1153
Linus Torvalds1da177e2005-04-16 15:20:36 -07001154static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1155{
Stephen Hemminger87990462006-08-10 23:35:16 -07001156 struct htb_class *cl = htb_find(classid, sch);
1157 if (cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001158 cl->refcnt++;
1159 return (unsigned long)cl;
1160}
1161
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001162static inline int htb_parent_last_child(struct htb_class *cl)
1163{
1164 if (!cl->parent)
1165 /* the root class */
1166 return 0;
1167
1168 if (!(cl->parent->children.next == &cl->sibling &&
1169 cl->parent->children.prev == &cl->sibling))
1170 /* not the last child */
1171 return 0;
1172
1173 return 1;
1174}
1175
1176static void htb_parent_to_leaf(struct htb_class *cl, struct Qdisc *new_q)
1177{
1178 struct htb_class *parent = cl->parent;
1179
1180 BUG_TRAP(!cl->level && cl->un.leaf.q && !cl->prio_activity);
1181
1182 parent->level = 0;
1183 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
1184 INIT_LIST_HEAD(&parent->un.leaf.drop_list);
1185 parent->un.leaf.q = new_q ? new_q : &noop_qdisc;
1186 parent->un.leaf.quantum = parent->quantum;
1187 parent->un.leaf.prio = parent->prio;
1188 parent->tokens = parent->buffer;
1189 parent->ctokens = parent->cbuffer;
Patrick McHardy3bebcda2007-03-23 11:29:25 -07001190 parent->t_c = psched_get_time();
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001191 parent->cmode = HTB_CAN_SEND;
1192}
1193
Stephen Hemminger87990462006-08-10 23:35:16 -07001194static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001195{
1196 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardy814a175e2006-11-29 17:34:50 -08001197
Linus Torvalds1da177e2005-04-16 15:20:36 -07001198 if (!cl->level) {
1199 BUG_TRAP(cl->un.leaf.q);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001200 qdisc_destroy(cl->un.leaf.q);
1201 }
Patrick McHardyee39e102007-07-02 22:48:13 -07001202 gen_kill_estimator(&cl->bstats, &cl->rate_est);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001203 qdisc_put_rtab(cl->rate);
1204 qdisc_put_rtab(cl->ceil);
Stephen Hemminger87990462006-08-10 23:35:16 -07001205
Patrick McHardya48b5a62007-03-23 11:29:43 -07001206 tcf_destroy_chain(cl->filter_list);
Stephen Hemminger87990462006-08-10 23:35:16 -07001207
1208 while (!list_empty(&cl->children))
1209 htb_destroy_class(sch, list_entry(cl->children.next,
1210 struct htb_class, sibling));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001211
1212 /* note: this delete may happen twice (see htb_delete) */
Stephen Hemmingerda33e3e2006-11-07 14:54:46 -08001213 hlist_del_init(&cl->hlist);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001214 list_del(&cl->sibling);
Stephen Hemminger87990462006-08-10 23:35:16 -07001215
Linus Torvalds1da177e2005-04-16 15:20:36 -07001216 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001217 htb_deactivate(q, cl);
1218
Linus Torvalds1da177e2005-04-16 15:20:36 -07001219 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger3696f622006-08-10 23:36:01 -07001220 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
Stephen Hemminger87990462006-08-10 23:35:16 -07001221
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222 kfree(cl);
1223}
1224
1225/* always caled under BH & queue lock */
Stephen Hemminger87990462006-08-10 23:35:16 -07001226static void htb_destroy(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001227{
1228 struct htb_sched *q = qdisc_priv(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001229
Patrick McHardyfb983d42007-03-16 01:22:39 -07001230 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001231 /* This line used to be after htb_destroy_class call below
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +09001232 and surprisingly it worked in 2.4. But it must precede it
Linus Torvalds1da177e2005-04-16 15:20:36 -07001233 because filter need its target class alive to be able to call
1234 unbind_filter on it (without Oops). */
Patrick McHardya48b5a62007-03-23 11:29:43 -07001235 tcf_destroy_chain(q->filter_list);
Stephen Hemminger87990462006-08-10 23:35:16 -07001236
1237 while (!list_empty(&q->root))
1238 htb_destroy_class(sch, list_entry(q->root.next,
1239 struct htb_class, sibling));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001240
1241 __skb_queue_purge(&q->direct_queue);
1242}
1243
1244static int htb_delete(struct Qdisc *sch, unsigned long arg)
1245{
1246 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001247 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy256d61b2006-11-29 17:37:05 -08001248 unsigned int qlen;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001249 struct Qdisc *new_q = NULL;
1250 int last_child = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001251
1252 // TODO: why don't allow to delete subtree ? references ? does
1253 // tc subsys quarantee us that in htb_destroy it holds no class
1254 // refs so that we can remove children safely there ?
1255 if (!list_empty(&cl->children) || cl->filter_cnt)
1256 return -EBUSY;
Stephen Hemminger87990462006-08-10 23:35:16 -07001257
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001258 if (!cl->level && htb_parent_last_child(cl)) {
1259 new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
1260 cl->parent->classid);
1261 last_child = 1;
1262 }
1263
Linus Torvalds1da177e2005-04-16 15:20:36 -07001264 sch_tree_lock(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001265
Patrick McHardy814a175e2006-11-29 17:34:50 -08001266 if (!cl->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001267 qlen = cl->un.leaf.q->q.qlen;
Patrick McHardy814a175e2006-11-29 17:34:50 -08001268 qdisc_reset(cl->un.leaf.q);
Patrick McHardy256d61b2006-11-29 17:37:05 -08001269 qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
Patrick McHardy814a175e2006-11-29 17:34:50 -08001270 }
1271
Patrick McHardyc38c83c2007-03-27 14:04:24 -07001272 /* delete from hash and active; remainder in destroy_class */
1273 hlist_del_init(&cl->hlist);
1274
Linus Torvalds1da177e2005-04-16 15:20:36 -07001275 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001276 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001277
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001278 if (last_child)
1279 htb_parent_to_leaf(cl, new_q);
1280
Linus Torvalds1da177e2005-04-16 15:20:36 -07001281 if (--cl->refcnt == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -07001282 htb_destroy_class(sch, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001283
1284 sch_tree_unlock(sch);
1285 return 0;
1286}
1287
1288static void htb_put(struct Qdisc *sch, unsigned long arg)
1289{
Stephen Hemminger87990462006-08-10 23:35:16 -07001290 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001291
1292 if (--cl->refcnt == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -07001293 htb_destroy_class(sch, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001294}
1295
Stephen Hemminger87990462006-08-10 23:35:16 -07001296static int htb_change_class(struct Qdisc *sch, u32 classid,
1297 u32 parentid, struct rtattr **tca,
1298 unsigned long *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299{
1300 int err = -EINVAL;
1301 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001302 struct htb_class *cl = (struct htb_class *)*arg, *parent;
1303 struct rtattr *opt = tca[TCA_OPTIONS - 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001304 struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
1305 struct rtattr *tb[TCA_HTB_RTAB];
1306 struct tc_htb_opt *hopt;
1307
1308 /* extract all subattrs from opt attr */
1309 if (!opt || rtattr_parse_nested(tb, TCA_HTB_RTAB, opt) ||
Stephen Hemminger87990462006-08-10 23:35:16 -07001310 tb[TCA_HTB_PARMS - 1] == NULL ||
1311 RTA_PAYLOAD(tb[TCA_HTB_PARMS - 1]) < sizeof(*hopt))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001312 goto failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001313
Stephen Hemminger87990462006-08-10 23:35:16 -07001314 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001315
Stephen Hemminger87990462006-08-10 23:35:16 -07001316 hopt = RTA_DATA(tb[TCA_HTB_PARMS - 1]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001317
Stephen Hemminger87990462006-08-10 23:35:16 -07001318 rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB - 1]);
1319 ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB - 1]);
1320 if (!rtab || !ctab)
1321 goto failure;
1322
1323 if (!cl) { /* new class */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001324 struct Qdisc *new_q;
Stephen Hemminger3696f622006-08-10 23:36:01 -07001325 int prio;
Patrick McHardyee39e102007-07-02 22:48:13 -07001326 struct {
1327 struct rtattr rta;
1328 struct gnet_estimator opt;
1329 } est = {
1330 .rta = {
1331 .rta_len = RTA_LENGTH(sizeof(est.opt)),
1332 .rta_type = TCA_RATE,
1333 },
1334 .opt = {
1335 /* 4s interval, 16s averaging constant */
1336 .interval = 2,
1337 .ewma_log = 2,
1338 },
1339 };
Stephen Hemminger3696f622006-08-10 23:36:01 -07001340
Linus Torvalds1da177e2005-04-16 15:20:36 -07001341 /* check for valid classid */
Stephen Hemminger87990462006-08-10 23:35:16 -07001342 if (!classid || TC_H_MAJ(classid ^ sch->handle)
1343 || htb_find(classid, sch))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001344 goto failure;
1345
1346 /* check maximal depth */
1347 if (parent && parent->parent && parent->parent->level < 2) {
1348 printk(KERN_ERR "htb: tree is too deep\n");
1349 goto failure;
1350 }
1351 err = -ENOBUFS;
Panagiotis Issaris0da974f2006-07-21 14:51:30 -07001352 if ((cl = kzalloc(sizeof(*cl), GFP_KERNEL)) == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001353 goto failure;
Stephen Hemminger87990462006-08-10 23:35:16 -07001354
Patrick McHardyee39e102007-07-02 22:48:13 -07001355 gen_new_estimator(&cl->bstats, &cl->rate_est,
1356 &sch->dev->queue_lock,
1357 tca[TCA_RATE-1] ? : &est.rta);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001358 cl->refcnt = 1;
1359 INIT_LIST_HEAD(&cl->sibling);
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001360 INIT_HLIST_NODE(&cl->hlist);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001361 INIT_LIST_HEAD(&cl->children);
1362 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
Stephen Hemminger3696f622006-08-10 23:36:01 -07001363 RB_CLEAR_NODE(&cl->pq_node);
1364
1365 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1366 RB_CLEAR_NODE(&cl->node[prio]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001367
1368 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
1369 so that can't be used inside of sch_tree_lock
1370 -- thanks to Karlis Peisenieks */
Patrick McHardy9f9afec2006-11-29 17:35:18 -08001371 new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001372 sch_tree_lock(sch);
1373 if (parent && !parent->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001374 unsigned int qlen = parent->un.leaf.q->q.qlen;
1375
Linus Torvalds1da177e2005-04-16 15:20:36 -07001376 /* turn parent into inner node */
Patrick McHardy256d61b2006-11-29 17:37:05 -08001377 qdisc_reset(parent->un.leaf.q);
1378 qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen);
Stephen Hemminger87990462006-08-10 23:35:16 -07001379 qdisc_destroy(parent->un.leaf.q);
1380 if (parent->prio_activity)
1381 htb_deactivate(q, parent);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001382
1383 /* remove from evt list because of level change */
1384 if (parent->cmode != HTB_CAN_SEND) {
Stephen Hemminger3696f622006-08-10 23:36:01 -07001385 htb_safe_rb_erase(&parent->pq_node, q->wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386 parent->cmode = HTB_CAN_SEND;
1387 }
1388 parent->level = (parent->parent ? parent->parent->level
Stephen Hemminger87990462006-08-10 23:35:16 -07001389 : TC_HTB_MAXDEPTH) - 1;
1390 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001391 }
1392 /* leaf (we) needs elementary qdisc */
1393 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1394
Stephen Hemminger87990462006-08-10 23:35:16 -07001395 cl->classid = classid;
1396 cl->parent = parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001397
1398 /* set class to be in HTB_CAN_SEND state */
1399 cl->tokens = hopt->buffer;
1400 cl->ctokens = hopt->cbuffer;
Patrick McHardy00c04af2007-03-16 01:23:02 -07001401 cl->mbuffer = 60 * PSCHED_TICKS_PER_SEC; /* 1min */
Patrick McHardy3bebcda2007-03-23 11:29:25 -07001402 cl->t_c = psched_get_time();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001403 cl->cmode = HTB_CAN_SEND;
1404
1405 /* attach to the hash list and parent's family */
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001406 hlist_add_head(&cl->hlist, q->hash + htb_hash(classid));
Stephen Hemminger87990462006-08-10 23:35:16 -07001407 list_add_tail(&cl->sibling,
1408 parent ? &parent->children : &q->root);
Patrick McHardyee39e102007-07-02 22:48:13 -07001409 } else {
1410 if (tca[TCA_RATE-1])
1411 gen_replace_estimator(&cl->bstats, &cl->rate_est,
1412 &sch->dev->queue_lock,
1413 tca[TCA_RATE-1]);
Stephen Hemminger87990462006-08-10 23:35:16 -07001414 sch_tree_lock(sch);
Patrick McHardyee39e102007-07-02 22:48:13 -07001415 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001416
1417 /* it used to be a nasty bug here, we have to check that node
Stephen Hemminger87990462006-08-10 23:35:16 -07001418 is really leaf before changing cl->un.leaf ! */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001419 if (!cl->level) {
1420 cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum;
1421 if (!hopt->quantum && cl->un.leaf.quantum < 1000) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001422 printk(KERN_WARNING
1423 "HTB: quantum of class %X is small. Consider r2q change.\n",
1424 cl->classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001425 cl->un.leaf.quantum = 1000;
1426 }
1427 if (!hopt->quantum && cl->un.leaf.quantum > 200000) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001428 printk(KERN_WARNING
1429 "HTB: quantum of class %X is big. Consider r2q change.\n",
1430 cl->classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001431 cl->un.leaf.quantum = 200000;
1432 }
1433 if (hopt->quantum)
1434 cl->un.leaf.quantum = hopt->quantum;
1435 if ((cl->un.leaf.prio = hopt->prio) >= TC_HTB_NUMPRIO)
1436 cl->un.leaf.prio = TC_HTB_NUMPRIO - 1;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001437
1438 /* backup for htb_parent_to_leaf */
1439 cl->quantum = cl->un.leaf.quantum;
1440 cl->prio = cl->un.leaf.prio;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001441 }
1442
1443 cl->buffer = hopt->buffer;
1444 cl->cbuffer = hopt->cbuffer;
Stephen Hemminger87990462006-08-10 23:35:16 -07001445 if (cl->rate)
1446 qdisc_put_rtab(cl->rate);
1447 cl->rate = rtab;
1448 if (cl->ceil)
1449 qdisc_put_rtab(cl->ceil);
1450 cl->ceil = ctab;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001451 sch_tree_unlock(sch);
1452
1453 *arg = (unsigned long)cl;
1454 return 0;
1455
1456failure:
Stephen Hemminger87990462006-08-10 23:35:16 -07001457 if (rtab)
1458 qdisc_put_rtab(rtab);
1459 if (ctab)
1460 qdisc_put_rtab(ctab);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001461 return err;
1462}
1463
1464static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1465{
1466 struct htb_sched *q = qdisc_priv(sch);
1467 struct htb_class *cl = (struct htb_class *)arg;
1468 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001469
Linus Torvalds1da177e2005-04-16 15:20:36 -07001470 return fl;
1471}
1472
1473static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
Stephen Hemminger87990462006-08-10 23:35:16 -07001474 u32 classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001475{
1476 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001477 struct htb_class *cl = htb_find(classid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001478
Linus Torvalds1da177e2005-04-16 15:20:36 -07001479 /*if (cl && !cl->level) return 0;
Stephen Hemminger87990462006-08-10 23:35:16 -07001480 The line above used to be there to prevent attaching filters to
1481 leaves. But at least tc_index filter uses this just to get class
1482 for other reasons so that we have to allow for it.
1483 ----
1484 19.6.2002 As Werner explained it is ok - bind filter is just
1485 another way to "lock" the class - unlike "get" this lock can
1486 be broken by class during destroy IIUC.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001487 */
Stephen Hemminger87990462006-08-10 23:35:16 -07001488 if (cl)
1489 cl->filter_cnt++;
1490 else
Linus Torvalds1da177e2005-04-16 15:20:36 -07001491 q->filter_cnt++;
1492 return (unsigned long)cl;
1493}
1494
1495static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1496{
1497 struct htb_sched *q = qdisc_priv(sch);
1498 struct htb_class *cl = (struct htb_class *)arg;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001499
Stephen Hemminger87990462006-08-10 23:35:16 -07001500 if (cl)
1501 cl->filter_cnt--;
1502 else
Linus Torvalds1da177e2005-04-16 15:20:36 -07001503 q->filter_cnt--;
1504}
1505
1506static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1507{
1508 struct htb_sched *q = qdisc_priv(sch);
1509 int i;
1510
1511 if (arg->stop)
1512 return;
1513
1514 for (i = 0; i < HTB_HSIZE; i++) {
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001515 struct hlist_node *p;
1516 struct htb_class *cl;
1517
1518 hlist_for_each_entry(cl, p, q->hash + i, hlist) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001519 if (arg->count < arg->skip) {
1520 arg->count++;
1521 continue;
1522 }
1523 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1524 arg->stop = 1;
1525 return;
1526 }
1527 arg->count++;
1528 }
1529 }
1530}
1531
1532static struct Qdisc_class_ops htb_class_ops = {
1533 .graft = htb_graft,
1534 .leaf = htb_leaf,
Patrick McHardy256d61b2006-11-29 17:37:05 -08001535 .qlen_notify = htb_qlen_notify,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001536 .get = htb_get,
1537 .put = htb_put,
1538 .change = htb_change_class,
1539 .delete = htb_delete,
1540 .walk = htb_walk,
1541 .tcf_chain = htb_find_tcf,
1542 .bind_tcf = htb_bind_filter,
1543 .unbind_tcf = htb_unbind_filter,
1544 .dump = htb_dump_class,
1545 .dump_stats = htb_dump_class_stats,
1546};
1547
1548static struct Qdisc_ops htb_qdisc_ops = {
1549 .next = NULL,
1550 .cl_ops = &htb_class_ops,
1551 .id = "htb",
1552 .priv_size = sizeof(struct htb_sched),
1553 .enqueue = htb_enqueue,
1554 .dequeue = htb_dequeue,
1555 .requeue = htb_requeue,
1556 .drop = htb_drop,
1557 .init = htb_init,
1558 .reset = htb_reset,
1559 .destroy = htb_destroy,
1560 .change = NULL /* htb_change */,
1561 .dump = htb_dump,
1562 .owner = THIS_MODULE,
1563};
1564
1565static int __init htb_module_init(void)
1566{
Stephen Hemminger87990462006-08-10 23:35:16 -07001567 return register_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001568}
Stephen Hemminger87990462006-08-10 23:35:16 -07001569static void __exit htb_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001570{
Stephen Hemminger87990462006-08-10 23:35:16 -07001571 unregister_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001572}
Stephen Hemminger87990462006-08-10 23:35:16 -07001573
Linus Torvalds1da177e2005-04-16 15:20:36 -07001574module_init(htb_module_init)
1575module_exit(htb_module_exit)
1576MODULE_LICENSE("GPL");