]> git.pld-linux.org Git - packages/kernel.git/blame - ds9-htb3-2.2.21-2.diff
projects / packages / kernel.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
- ported from linux-2.4.25-atmdd.patch
[packages/kernel.git] / ds9-htb3-2.2.21-2.diff
CommitLineData
49520c69
KT		 1diff -urN ../v2.2.21-ds9/linux/Documentation/Configure.help linux/Documentation/Configure.help
2--- ../v2.2.21-ds9/linux/Documentation/Configure.help Tue May 21 23:26:01 2002
3+++ linux/Documentation/Configure.help Sat Aug 10 10:48:07 2002
4@@ -6118,6 +6118,20 @@
5 whenever you want). If you want to compile it as a module, say M
6 here and read Documentation/modules.txt.
7
8+CONFIG_NET_SCH_HTB
9+ Say Y here if you want to use the Hierarchical Token Buckets (HTB)
10+ packet scheduling algorithm for some of your network devices. See
11+ URL http://luxik.cdi.cz/~devik/qos/htb/ for complete manual and
12+ in-depth articles.
13+
14+ HTB is very similar to the CBQ regarding its goals however is has
15+ different properties and different algorithm.
16+
17+ This code is also available as a module called sch_htb.o ( = code
18+ which can be inserted in and removed from the running kernel
19+ whenever you want). If you want to compile it as a module, say M
20+ here and read Documentation/modules.txt.
21+
22 CSZ packet scheduler
23 CONFIG_NET_SCH_CSZ
24 Say Y here if you want to use the Clark-Shenker-Zhang (CSZ) packet
25diff -urN ../v2.2.21-ds9/linux/include/linux/pkt_sched.h linux/include/linux/pkt_sched.h
26--- ../v2.2.21-ds9/linux/include/linux/pkt_sched.h Sun Aug 4 14:54:40 2002
27+++ linux/include/linux/pkt_sched.h Sat Aug 10 10:31:11 2002
28@@ -246,6 +246,48 @@
29 };
30
31
32+/* HTB section */
33+#define TC_HTB_NUMPRIO 8
34+#define TC_HTB_MAXDEPTH 8
35+#define TC_HTB_PROTOVER 3 /* the same as HTB and TC's major */
36+
37+struct tc_htb_opt
38+{
39+ struct tc_ratespec rate;
40+ struct tc_ratespec ceil;
41+ __u32 buffer;
42+ __u32 cbuffer;
43+ __u32 quantum;
44+ __u32 level; /* out only */
45+ __u32 prio;
46+};
47+struct tc_htb_glob
48+{
49+ __u32 version; /* to match HTB/TC */
50+ __u32 rate2quantum; /* bps->quantum divisor */
51+ __u32 defcls; /* default class number */
52+ __u32 debug; /* debug flags */
53+
54+ /* stats */
55+ __u32 direct_pkts; /* count of non shapped packets */
56+};
57+enum
58+{
59+ TCA_HTB_UNSPEC,
60+ TCA_HTB_PARMS,
61+ TCA_HTB_INIT,
62+ TCA_HTB_CTAB,
63+ TCA_HTB_RTAB,
64+};
65+struct tc_htb_xstats
66+{
67+ __u32 lends;
68+ __u32 borrows;
69+ __u32 giants; /* too big packets (rate will not be accurate) */
70+ __u32 tokens;
71+ __u32 ctokens;
72+};
73+
74 /* CBQ section */
75
76 #define TC_CBQ_MAXPRIO 8
77diff -urN ../v2.2.21-ds9/linux/net/sched/Config.in linux/net/sched/Config.in
78--- ../v2.2.21-ds9/linux/net/sched/Config.in Wed Jul 31 00:00:59 2002
79+++ linux/net/sched/Config.in Sat Aug 10 10:31:11 2002
80@@ -4,6 +4,7 @@
81 define_bool CONFIG_NETLINK y
82 define_bool CONFIG_RTNETLINK y
83 tristate 'CBQ packet scheduler' CONFIG_NET_SCH_CBQ
84+tristate 'HTB packet scheduler' CONFIG_NET_SCH_HTB
85 tristate 'CSZ packet scheduler' CONFIG_NET_SCH_CSZ
86 #tristate 'H-PFQ packet scheduler' CONFIG_NET_SCH_HPFQ
87 #tristate 'H-FSC packet scheduler' CONFIG_NET_SCH_HFCS
88diff -urN ../v2.2.21-ds9/linux/net/sched/Makefile linux/net/sched/Makefile
89--- ../v2.2.21-ds9/linux/net/sched/Makefile Wed Jul 31 00:00:59 2002
90+++ linux/net/sched/Makefile Sat Aug 10 10:31:11 2002
91@@ -68,6 +68,14 @@
92 endif
93 endif
94
95+ifeq ($(CONFIG_NET_SCH_HTB), y)
96+O_OBJS += sch_htb.o
97+else
98+ ifeq ($(CONFIG_NET_SCH_HTB), m)
99+ M_OBJS += sch_htb.o
100+ endif
101+endif
102+
103
104 ifeq ($(CONFIG_NET_SCH_SFQ), y)
105 O_OBJS += sch_sfq.o
49520c69
KT		 106diff -urN ../v2.2.21-ds9/linux/net/sched/sch_htb.c linux/net/sched/sch_htb.c
107--- ../v2.2.21-ds9/linux/net/sched/sch_htb.c Thu Jan 1 00:00:00 1970
108+++ linux/net/sched/sch_htb.c Thu Oct 24 00:45:35 2002
c8436fd6
KT		 109@@ -1,5 +1,5 @@
110-/* vim: ts=8 sw=4
111- * net/sched/sch_htb.c Hierarchical token bucket
49520c69
KT		 112+/* vim: ts=8 sw=8
113+ * net/sched/sch_htb.c Hierarchical token bucket, feed tree version
c8436fd6
KT		 114 *
115 * This program is free software; you can redistribute it and/or
116 * modify it under the terms of the GNU General Public License
117@@ -8,18 +8,19 @@
118 *
119 * Authors: Martin Devera, <devik@cdi.cz>
120 *
121- * Credits (in time order):
49520c69 122+ * Credits (in time order) for older HTB versions:
c8436fd6
KT		 123 * Ondrej Kraus, <krauso@barr.cz>
124 * found missing INIT_QDISC(htb)
125 * Vladimir Smelhaus, Aamer Akhter, Bert Hubert
126 * helped a lot to locate nasty class stall bug
127 * Andi Kleen, Jamal Hadi, Bert Hubert
128 * code review and helpful comments on shaping
49520c69
KT		 129+ * Tomasz Wrona, <tw@eter.tym.pl>
130+ * created test case so that I was able to fix nasty bug
c8436fd6
KT		 131 * and many others. thanks.
132 *
133- * $Id$
49520c69 134+ * $Id$
c8436fd6
KT		 135 */
136-
137 #include <linux/config.h>
138 #include <linux/module.h>
139 #include <asm/uaccess.h>
140@@ -44,15 +45,17 @@
141 #include <net/ip.h>
142 #include <net/route.h>
143 #include <linux/skbuff.h>
49520c69 144+#include <linux/list.h>
c8436fd6
KT		 145 #include <net/sock.h>
146 #include <net/pkt_sched.h>
49520c69 147+#include <linux/rbtree.h>
c8436fd6
KT		 148
149 /* HTB algorithm.
150 Author: devik@cdi.cz
151- =======================================
49520c69 152+ ========================================================================
c8436fd6
KT		 153 HTB is like TBF with multiple classes. It is also similar to CBQ because
154 it allows to assign priority to each class in hierarchy.
155- In fact it is another implementation os Floyd's formal sharing.
49520c69 156+ In fact it is another implementation of Floyd's formal sharing.
c8436fd6
KT		 157
158 Levels:
159 Each class is assigned level. Leaf has ALWAYS level 0 and root
160@@ -63,37 +66,19 @@
161 #define HTB_HSIZE 16 /* classid hash size */
162 #define HTB_EWMAC 2 /* rate average over HTB_EWMAC*HTB_HSIZE sec */
163 #define HTB_DEBUG 1 /* compile debugging support (activated by tc tool) */
164-#define HTB_QLOCK(S) spin_lock_bh(&(S)->dev->queue_lock)
165-#define HTB_QUNLOCK(S) spin_unlock_bh(&(S)->dev->queue_lock)
166-
167-/* ======== Begin of part to be deleted for 2.4 merged one ========= */
168-#if LINUX_VERSION_CODE < 0x20300
169-#define MODULE_LICENSE(X)
170-
171-#define NET_XMIT_SUCCESS 1
172-#define NET_XMIT_DROP 0
173-
174-static inline void __skb_queue_purge(struct sk_buff_head *list)
175-{
176- struct sk_buff *skb;
177- while ((skb=__skb_dequeue(list))!=NULL)
178- kfree_skb(skb);
179-}
180-#define del_timer_sync(t) del_timer(t)
49520c69
KT		 181+#define HTB_RATECM 1 /* whether to use rate computer */
182+#define HTB_HYSTERESIS 1/* whether to use mode hysteresis for speedup */
183+#define HTB_QLOCK(S) sch_dev_queue_lock((S)->dev)
184+#define HTB_QUNLOCK(S) sch_dev_queue_unlock((S)->dev)
185+#define HTB_VER 0x30007 /* major must be matched with number suplied by TC as version */
c8436fd6
KT		 186
187-#define netif_schedule qdisc_wakeup
188-#define netif_queue_stopped(D) (D->tbusy)
189-#define sch_tree_lock(S) start_bh_atomic()
190-#define sch_tree_unlock(S) end_bh_atomic()
191-#undef HTB_QLOCK
192-#undef HTB_QUNLOCK
193-#define HTB_QLOCK(S)
194-#define HTB_QUNLOCK(S)
195-#ifndef BUG_TRAP
196-#define BUG_TRAP(x) if (!(x)) { printk("Assertion (" #x ") failed at " __FILE__ "(%d):" __FUNCTION__ "\n", __LINE__); }
49520c69
KT		 197+#if HTB_VER >> 16 != TC_HTB_PROTOVER
198+#error "Mismatched sch_htb.c and pkt_sch.h"
c8436fd6
KT		 199 #endif
200-#endif
201-/* ======== End of part to be deleted for 2.4 merged one =========== */
49520c69
KT		 202+
203+/* temporary debug defines to be removed after beta stage */
204+#define DEVIK_MEND(N)
205+#define DEVIK_MSTART(N)
c8436fd6
KT		 206
207 /* debugging support; S is subsystem, these are defined:
208 0 - netlink messages
209@@ -102,7 +87,9 @@
210 3 - dequeue main
211 4 - dequeue one prio DRR part
212 5 - dequeue class accounting
213- 6 - dequeue rcache (ready level computation)
49520c69
KT		 214+ 6 - class overlimit status computation
215+ 7 - hint tree
216+ 8 - event queue
c8436fd6
KT		 217 10 - rate estimator
218 11 - classifier
219 12 - fast dequeue cache
220@@ -111,80 +98,88 @@
221 q->debug uint32 contains 16 2-bit fields one for subsystem starting
222 from LSB
223 */
224-#if HTB_DEBUG
49520c69 225+#ifdef HTB_DEBUG
c8436fd6
KT		 226 #define HTB_DBG(S,L,FMT,ARG...) if (((q->debug>>(2*S))&3) >= L) \
227 printk(KERN_DEBUG FMT,##ARG)
49520c69
KT		 228+#define HTB_CHCL(cl) BUG_TRAP((cl)->magic == HTB_CMAGIC)
229+#define HTB_PASSQ q,
230+#define HTB_ARGQ struct htb_sched *q,
231+#define static
232+#define __inline__
233+#define inline
234+#define HTB_CMAGIC 0xFEFAFEF1
235+#define htb_safe_rb_erase(N,R) do { BUG_TRAP((N)->rb_color != -1); \
236+ if ((N)->rb_color == -1) break; \
237+ rb_erase(N,R); \
238+ (N)->rb_color = -1; } while (0)
c8436fd6
KT		 239 #else
240 #define HTB_DBG(S,L,FMT,ARG...)
49520c69
KT		 241+#define HTB_PASSQ
242+#define HTB_ARGQ
243+#define HTB_CHCL(cl)
244+#define htb_safe_rb_erase(N,R) rb_erase(N,R)
c8436fd6
KT		 245 #endif
246
247
248-/* used internaly to pass status of single class */
49520c69 249+/* used internaly to keep status of single class */
c8436fd6
KT		 250 enum htb_cmode {
251 HTB_CANT_SEND, /* class can't send and can't borrow */
252 HTB_MAY_BORROW, /* class can't send but may borrow */
253 HTB_CAN_SEND /* class can send */
254 };
255-#define HTB_F_INJ 0x10000 /* to mark dequeue level as injected one */
256-
257-/* often used circular list of classes; I didn't use generic linux
258- double linked list to avoid casts and before I rely on some behaviour
259- of insert and delete functions; item not bound to list is guaranted
260- to have prev member NULL (we don't mangle next pointer as we often
261- need it */
262-struct htb_litem {
263- struct htb_class *prev, *next;
264-};
265-/* circular list insert and delete macros; these also maintain
266- correct value of pointer to the list; insert adds 'new' class
267- before 'cl' class using prev/next member 'list' */
268-#define HTB_INSERTB(list,cl,new) \
269-do { if (!cl) new->list.prev = cl = new; \
270- new->list.next = cl; new->list.prev = cl->list.prev; \
271- cl->list.prev->list.next = cl->list.prev = new; } while(0)
272-
273-/* remove 'cl' class from 'list' repairing 'ptr' if not null */
274-#define HTB_DELETE(list,cl,ptr) do { \
275- if (cl->list.prev) { cl->list.prev->list.next = cl->list.next; \
276- cl->list.next->list.prev = cl->list.prev; \
277- if (ptr == cl) ptr = cl->list.next; \
278- if (ptr == cl) ptr = NULL; cl->list.prev = NULL; } \
279- else printk(KERN_ERR "htb: DELETE BUG [" #list "," #cl "," #ptr "]\n"); \
280- } while (0)
281
282 /* interior & leaf nodes; props specific to leaves are marked L: */
283 struct htb_class
284 {
49520c69
KT		 285+#ifdef HTB_DEBUG
286+ unsigned magic;
287+#endif
c8436fd6
KT		 288 /* general class parameters */
289 u32 classid;
290 struct tc_stats stats; /* generic stats */
291 struct tc_htb_xstats xstats;/* our special stats */
292 int refcnt; /* usage count of this class */
293- struct Qdisc *q; /* L: elem. qdisc */
294
49520c69 295+#ifdef HTB_RATECM
c8436fd6
KT		 296 /* rate measurement counters */
297 unsigned long rate_bytes,sum_bytes;
298 unsigned long rate_packets,sum_packets;
49520c69 299+#endif
c8436fd6
KT		 300
301- /* DRR scheduler parameters */
302- int quantum; /* L: round quantum computed from rate */
303- int deficit[TC_HTB_MAXDEPTH]; /* L: deficit for class at level */
304- char prio; /* L: priority of the class; 0 is the highest */
305- char aprio; /* L: prio at which we were last adding to active list
306- it is used to change priority at runtime */
307 /* topology */
308- char level; /* our level (see above) */
309- char injectd; /* distance from injected parent */
49520c69 310+ int level; /* our level (see above) */
c8436fd6
KT		 311 struct htb_class *parent; /* parent class */
312- struct htb_class *children; /* pointer to children list */
313- struct htb_litem hlist; /* classid hash list */
314- struct htb_litem active; /* L: prio level active DRR list */
315- struct htb_litem sibling; /* sibling list */
49520c69
KT		 316+ struct list_head hlist; /* classid hash list item */
317+ struct list_head sibling; /* sibling list item */
318+ struct list_head children; /* children list */
319+
320+ union {
321+ struct htb_class_leaf {
322+ struct Qdisc *q;
323+ int prio;
324+ int aprio;
325+ int quantum;
326+ int deficit[TC_HTB_MAXDEPTH];
327+ struct list_head drop_list;
328+ } leaf;
329+ struct htb_class_inner {
330+ rb_root_t feed[TC_HTB_NUMPRIO]; /* feed trees */
331+ rb_node_t *ptr[TC_HTB_NUMPRIO]; /* current class ptr */
332+ } inner;
333+ } un;
334+ rb_node_t node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
335+ rb_node_t pq_node; /* node for event queue */
336+ unsigned long pq_key; /* the same type as jiffies global */
c8436fd6 337
49520c69
KT		 338+ int prio_activity; /* for which prios are we active */
339+ enum htb_cmode cmode; /* current mode of the class */
340+
c8436fd6
KT		 341 /* class attached filters */
342 struct tcf_proto *filter_list;
343 int filter_cnt;
344
49520c69
KT		 345+ int warned; /* only one warning about non work conserving .. */
346+
c8436fd6
KT		 347 /* token bucket parameters */
348 struct qdisc_rate_table *rate; /* rate table of the class itself */
349 struct qdisc_rate_table *ceil; /* ceiling rate (limits borrows too) */
350@@ -192,10 +187,6 @@
351 long mbuffer; /* max wait time */
352 long tokens,ctokens; /* current number of tokens */
353 psched_time_t t_c; /* checkpoint time */
354-
355- /* walk result cache for leaves */
356- unsigned long rcache_sn; /* SN of cache validity */
357- unsigned rc_level; /* victim's level */
358 };
359
360 /* TODO: maybe compute rate when size is too large .. or drop ? */
361@@ -212,19 +203,23 @@
362
363 struct htb_sched
364 {
365- struct htb_class *root; /* root classes circular list */
366- struct htb_class *hash[HTB_HSIZE]; /* hashed by classid */
49520c69
KT		 367+ struct list_head root; /* root classes list */
368+ struct list_head hash[HTB_HSIZE]; /* hashed by classid */
369+ struct list_head drops[TC_HTB_NUMPRIO]; /* active leaves (for drops) */
c8436fd6
KT		 370
371- /* active classes table; this needs explanation. This table contains
372- one set of pointers per priority, it is obvious. The set contains
373- one pointer per class level in the same way as cl->deficit is
374- independent for each level. This allows us to maintain correct
375- DRR position independent of borrowing level.
376- If we used single active/deficit items then DRR fairness'd suffer
377- from frequent class level changes.
378- Note that htb_[de]activate must be used to update this item
379- because it needs to keep all pointers in set coherent. */
380- struct htb_class *active[TC_HTB_NUMPRIO][TC_HTB_MAXDEPTH];
49520c69
KT		 381+ /* self list - roots of self generating tree */
382+ rb_root_t row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
383+ int row_mask[TC_HTB_MAXDEPTH];
384+ rb_node_t *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
385+
386+ /* self wait list - roots of wait PQs per row */
387+ rb_root_t wait_pq[TC_HTB_MAXDEPTH];
388+
389+ /* time of nearest event per level (row) */
390+ unsigned long near_ev_cache[TC_HTB_MAXDEPTH];
391+
392+ /* whether we hit non-work conserving class during this dequeue; we use */
393+ int nwc_hit; /* this to disable mindelay complaint in dequeue */
c8436fd6
KT		 394
395 int defcls; /* class where unclassified flows go to */
396 u32 debug; /* subsystem debug levels */
397@@ -233,27 +228,18 @@
398 struct tcf_proto *filter_list;
399 int filter_cnt;
400
401- unsigned long sn; /* result cache serial number */
402 int rate2quantum; /* quant = rate / rate2quantum */
403 psched_time_t now; /* cached dequeue time */
404- long delay; /* how long to deactivate for */
405 struct timer_list timer; /* send delay timer */
49520c69 406+#ifdef HTB_RATECM
c8436fd6
KT		 407 struct timer_list rttim; /* rate computer timer */
408 int recmp_bucket; /* which hash bucket to recompute next */
409-
410- /* cache of last dequeued class */
411- struct htb_class *last_tx;
412- int use_dcache;
413-
414- /* non shapped skbs; let them go directly thru */
49520c69
KT		 415+#endif
416+
417+ /* non shaped skbs; let them go directly thru */
c8436fd6
KT		 418 struct sk_buff_head direct_queue;
419 int direct_qlen; /* max qlen of above */
420
421- /* statistics (see tc_htb_glob for explanation) */
422- long deq_rate,deq_rate_c;
423- long utilz,utilz_c;
424- long trials,trials_c;
425- long dcache_hits;
426 long direct_pkts;
427 };
428
429@@ -271,117 +257,477 @@
430 /* find class in global hash table using given handle */
431 static __inline__ struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
432 {
433- struct htb_sched *q = (struct htb_sched *)sch->data;
434- int h = htb_hash(handle);
435- struct htb_class *cl;
436- if (TC_H_MAJ(handle) != sch->handle) return NULL;
437- cl = q->hash[h];
438- if (cl) do {
439- if (cl->classid == handle) return cl;
440-
441- } while ((cl = cl->hlist.next) != q->hash[h]);
442- return NULL;
49520c69
KT		 443+ struct htb_sched *q = (struct htb_sched *)sch->data;
444+ struct list_head *p;
445+ if (TC_H_MAJ(handle) != sch->handle)
446+ return NULL;
447+
448+ list_for_each (p,q->hash+htb_hash(handle)) {
449+ struct htb_class *cl = list_entry(p,struct htb_class,hlist);
450+ if (cl->classid == handle)
451+ return cl;
452+ }
453+ return NULL;
c8436fd6
KT		 454 }
455
456-/* classify packet into class TODO: use inner filters & marks here */
457-static struct htb_class *htb_clasify(struct sk_buff *skb, struct Qdisc *sch)
49520c69
KT		 458+/**
459+ * htb_classify - classify a packet into class
460+ *
461+ * It returns NULL if the packet should be dropped or -1 if the packet
462+ * should be passed directly thru. In all other cases leaf class is returned.
463+ * We allow direct class selection by classid in priority. The we examine
464+ * filters in qdisc and in inner nodes (if higher filter points to the inner
465+ * node). If we end up with classid MAJOR:0 we enqueue the skb into special
466+ * internal fifo (direct). These packets then go directly thru. If we still
467+ * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
468+ * then finish and return direct queue.
469+ */
470+#define HTB_DIRECT (struct htb_class*)-1
471+static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch)
c8436fd6
KT		 472 {
473- struct htb_sched *q = (struct htb_sched *)sch->data;
474- struct htb_class *cl;
475- struct tcf_result res;
476- struct tcf_proto *tcf;
477-
478- /* allow to select class by setting skb->priority to valid classid;
479- note that nfmark can be used too by attaching filter fw with no
480- rules in it */
481- if (skb->priority == sch->handle)
482- return NULL; /* X:0 (direct flow) selected */
483- if ((cl = htb_find(skb->priority,sch)) != NULL)
49520c69
KT		 484+ struct htb_sched *q = (struct htb_sched *)sch->data;
485+ struct htb_class *cl;
486+ struct tcf_result res;
487+ struct tcf_proto *tcf;
488+ int result;
489+
490+ /* allow to select class by setting skb->priority to valid classid;
491+ note that nfmark can be used too by attaching filter fw with no
492+ rules in it */
493+ if (skb->priority == sch->handle)
494+ return HTB_DIRECT; /* X:0 (direct flow) selected */
495+ if ((cl = htb_find(skb->priority,sch)) != NULL)
496+ return cl;
497+
498+ tcf = q->filter_list;
499+ while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
500+#ifdef CONFIG_NET_CLS_POLICE
501+ if (result == TC_POLICE_SHOT)
502+ return NULL;
503+#endif
504+ if ((cl = (void*)res.class) == NULL) {
505+ if (res.classid == sch->handle)
506+ return HTB_DIRECT; /* X:0 (direct flow) */
507+ if ((cl = htb_find(res.classid,sch)) == NULL)
508+ break; /* filter selected invalid classid */
509+ }
510+ if (!cl->level)
511+ return cl; /* we hit leaf; return it */
512+
513+ /* we have got inner class; apply inner filter chain */
514+ tcf = cl->filter_list;
515+ }
516+ /* classification failed; try to use default class */
517+ cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle),q->defcls),sch);
518+ if (!cl || cl->level)
519+ return HTB_DIRECT; /* bad default .. this is safe bet */
c8436fd6 520 return cl;
49520c69
KT		 521+}
522+
523+#ifdef HTB_DEBUG
524+static void htb_next_rb_node(rb_node_t **n);
525+#define HTB_DUMTREE(root,memb) if(root) { \
526+ rb_node_t *n = (root)->rb_node; \
527+ while (n->rb_left) n = n->rb_left; \
528+ while (n) { \
529+ struct htb_class *cl = rb_entry(n, struct htb_class, memb); \
530+ printk(" %x",cl->classid); htb_next_rb_node (&n); \
531+ } }
532+
533+static void htb_debug_dump (struct htb_sched *q)
534+{
535+ int i,p;
536+ printk(KERN_DEBUG "htb*g j=%lu\n",jiffies);
537+ /* rows */
538+ for (i=TC_HTB_MAXDEPTH-1;i>=0;i--) {
539+ printk(KERN_DEBUG "htb*r%d m=%x",i,q->row_mask[i]);
540+ for (p=0;p<TC_HTB_NUMPRIO;p++) {
541+ if (!q->row[i][p].rb_node) continue;
542+ printk(" p%d:",p);
543+ HTB_DUMTREE(q->row[i]+p,node[p]);
544+ }
545+ printk("\n");
546+ }
547+ /* classes */
548+ for (i = 0; i < HTB_HSIZE; i++) {
549+ struct list_head *l;
550+ list_for_each (l,q->hash+i) {
551+ struct htb_class *cl = list_entry(l,struct htb_class,hlist);
552+ long diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer, 0);
553+ printk(KERN_DEBUG "htb*c%x m=%d t=%ld c=%ld pq=%lu df=%ld ql=%d "
554+ "pa=%x f:",
555+ cl->classid,cl->cmode,cl->tokens,cl->ctokens,
556+ cl->pq_node.rb_color==-1?0:cl->pq_key,diff,
557+ cl->level?0:cl->un.leaf.q->q.qlen,cl->prio_activity);
558+ if (cl->level)
559+ for (p=0;p<TC_HTB_NUMPRIO;p++) {
560+ if (!cl->un.inner.feed[p].rb_node) continue;
561+ printk(" p%d a=%x:",p,cl->un.inner.ptr[p]?rb_entry(cl->un.inner.ptr[p], struct htb_class,node[p])->classid:0);
562+ HTB_DUMTREE(cl->un.inner.feed+p,node[p]);
563+ }
564+ printk("\n");
565+ }
566+ }
567+}
568+#endif
569+/**
570+ * htb_add_to_id_tree - adds class to the round robin list
571+ *
572+ * Routine adds class to the list (actually tree) sorted by classid.
573+ * Make sure that class is not already on such list for given prio.
574+ */
575+static void htb_add_to_id_tree (HTB_ARGQ rb_root_t *root,
576+ struct htb_class *cl,int prio)
577+{
578+ rb_node_t **p = &root->rb_node, *parent = NULL;
579+ HTB_DBG(7,3,"htb_add_id_tree cl=%X prio=%d\n",cl->classid,prio);
580+#ifdef HTB_DEBUG
581+ if (cl->node[prio].rb_color != -1) { BUG_TRAP(0); return; }
582+ HTB_CHCL(cl);
583+ if (*p) {
584+ struct htb_class *x = rb_entry(*p,struct htb_class,node[prio]);
585+ HTB_CHCL(x);
586+ }
587+#endif
588+ while (*p) {
589+ struct htb_class *c; parent = *p;
590+ c = rb_entry(parent, struct htb_class, node[prio]);
591+ HTB_CHCL(c);
592+ if (cl->classid > c->classid)
593+ p = &parent->rb_right;
594+ else
595+ p = &parent->rb_left;
596+ }
597+ rb_link_node(&cl->node[prio], parent, p);
598+ rb_insert_color(&cl->node[prio], root);
599+}
600+
601+/**
602+ * htb_add_to_wait_tree - adds class to the event queue with delay
603+ *
604+ * The class is added to priority event queue to indicate that class will
605+ * change its mode in cl->pq_key microseconds. Make sure that class is not
606+ * already in the queue.
607+ */
608+static void htb_add_to_wait_tree (struct htb_sched *q,
609+ struct htb_class *cl,long delay,int debug_hint)
610+{
611+ rb_node_t **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
612+ HTB_DBG(7,3,"htb_add_wt cl=%X key=%lu\n",cl->classid,cl->pq_key);
613+#ifdef HTB_DEBUG
614+ if (cl->pq_node.rb_color != -1) { BUG_TRAP(0); return; }
615+ HTB_CHCL(cl);
616+ if ((delay <= 0 || delay > cl->mbuffer) && net_ratelimit())
617+ printk(KERN_ERR "HTB: suspicious delay in wait_tree d=%ld cl=%X h=%d\n",delay,cl->classid,debug_hint);
618+#endif
619+ DEVIK_MSTART(9);
620+ cl->pq_key = jiffies + PSCHED_US2JIFFIE(delay);
621+ if (cl->pq_key == jiffies)
622+ cl->pq_key++;
623+
624+ /* update the nearest event cache */
625+ if (q->near_ev_cache[cl->level] - cl->pq_key < 0x80000000)
626+ q->near_ev_cache[cl->level] = cl->pq_key;
627+
628+ while (*p) {
629+ struct htb_class *c; parent = *p;
630+ c = rb_entry(parent, struct htb_class, pq_node);
631+ if (cl->pq_key - c->pq_key < 0x80000000)
632+ p = &parent->rb_right;
633+ else
634+ p = &parent->rb_left;
635+ }
636+ rb_link_node(&cl->pq_node, parent, p);
637+ rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
638+ DEVIK_MEND(9);
639+}
c8436fd6
KT		 640
641- tcf = q->filter_list;
642- while (tcf && !tc_classify(skb, tcf, &res)) {
643- if (res.classid == sch->handle)
644- return NULL; /* X:0 (direct flow) selected */
645- if ((cl = htb_find(res.classid,sch)) == NULL)
646- break; /* filter selected invalid classid */
647- if (!cl->level)
648- return cl; /* we hit leaf; return it */
49520c69
KT		 649+/**
650+ * htb_next_rb_node - finds next node in binary tree
651+ *
652+ * When we are past last key we return NULL.
653+ * Average complexity is 2 steps per call.
654+ */
655+static void htb_next_rb_node(rb_node_t **n)
656+{
657+ rb_node_t *p;
658+ if ((*n)->rb_right) {
659+ *n = (*n)->rb_right;
660+ while ((*n)->rb_left)
661+ *n = (*n)->rb_left;
662+ return;
663+ }
664+ while ((p = (*n)->rb_parent) != NULL) {
665+ if (p->rb_left == *n) break;
666+ *n = p;
667+ }
668+ *n = p;
669+}
c8436fd6
KT		 670
671- /* we have got inner class; apply inner filter chain */
672- tcf = cl->filter_list;
49520c69
KT		 673+/**
674+ * htb_add_class_to_row - add class to its row
675+ *
676+ * The class is added to row at priorities marked in mask.
677+ * It does nothing if mask == 0.
678+ */
679+static inline void htb_add_class_to_row(struct htb_sched *q,
680+ struct htb_class *cl,int mask)
681+{
682+ HTB_DBG(7,2,"htb_addrow cl=%X mask=%X rmask=%X\n",
683+ cl->classid,mask,q->row_mask[cl->level]);
684+ HTB_CHCL(cl);
685+ q->row_mask[cl->level] |= mask;
686+ while (mask) {
687+ int prio = ffz(~mask);
688+ mask &= ~(1 << prio);
689+ htb_add_to_id_tree(HTB_PASSQ q->row[cl->level]+prio,cl,prio);
690+ }
691+}
692+
693+/**
694+ * htb_remove_class_from_row - removes class from its row
695+ *
696+ * The class is removed from row at priorities marked in mask.
697+ * It does nothing if mask == 0.
698+ */
699+static __inline__ void htb_remove_class_from_row(struct htb_sched *q,
700+ struct htb_class *cl,int mask)
701+{
702+ int m = 0;
703+ HTB_CHCL(cl);
704+ while (mask) {
705+ int prio = ffz(~mask);
706+ mask &= ~(1 << prio);
707+ if (q->ptr[cl->level][prio] == cl->node+prio)
708+ htb_next_rb_node(q->ptr[cl->level]+prio);
709+ htb_safe_rb_erase(cl->node + prio,q->row[cl->level]+prio);
710+ if (!q->row[cl->level][prio].rb_node)
711+ m |= 1 << prio;
712+ }
713+ HTB_DBG(7,2,"htb_delrow cl=%X mask=%X rmask=%X maskdel=%X\n",
714+ cl->classid,mask,q->row_mask[cl->level],m);
715+ q->row_mask[cl->level] &= ~m;
716+}
717+
718+/**
719+ * htb_activate_prios - creates active classe's feed chain
720+ *
721+ * The class is connected to ancestors and/or appropriate rows
722+ * for priorities it is participating on. cl->cmode must be new
723+ * (activated) mode. It does nothing if cl->prio_activity == 0.
724+ */
725+static void htb_activate_prios(struct htb_sched *q,struct htb_class *cl)
726+{
727+ struct htb_class *p = cl->parent;
728+ long m,mask = cl->prio_activity;
729+ HTB_DBG(7,2,"htb_act_prios cl=%X mask=%lX cmode=%d\n",cl->classid,mask,cl->cmode);
730+ HTB_CHCL(cl);
731+
732+ while (cl->cmode == HTB_MAY_BORROW && p && mask) {
733+ HTB_CHCL(p);
734+ m = mask; while (m) {
735+ int prio = ffz(~m);
736+ m &= ~(1 << prio);
737+
738+ if (p->un.inner.feed[prio].rb_node)
739+ /* parent already has its feed in use so that
740+ reset bit in mask as parent is already ok */
741+ mask &= ~(1 << prio);
742+
743+ htb_add_to_id_tree(HTB_PASSQ p->un.inner.feed+prio,cl,prio);
744+ }
745+ HTB_DBG(7,3,"htb_act_pr_aft p=%X pact=%X mask=%lX pmode=%d\n",
746+ p->classid,p->prio_activity,mask,p->cmode);
747+ p->prio_activity |= mask;
748+ cl = p; p = cl->parent;
749+ HTB_CHCL(cl);
750+ }
751+ if (cl->cmode == HTB_CAN_SEND && mask)
752+ htb_add_class_to_row(q,cl,mask);
753+}
754+
755+/**
756+ * htb_deactivate_prios - remove class from feed chain
757+ *
758+ * cl->cmode must represent old mode (before deactivation). It does
759+ * nothing if cl->prio_activity == 0. Class is removed from all feed
760+ * chains and rows.
761+ */
762+static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
763+{
764+ struct htb_class *p = cl->parent;
765+ long m,mask = cl->prio_activity;
766+ HTB_DBG(7,2,"htb_deact_prios cl=%X mask=%lX cmode=%d\n",cl->classid,mask,cl->cmode);
767+ HTB_CHCL(cl);
768+
769+ while (cl->cmode == HTB_MAY_BORROW && p && mask) {
770+ m = mask; mask = 0;
771+ while (m) {
772+ int prio = ffz(~m);
773+ m &= ~(1 << prio);
774+
775+ if (p->un.inner.ptr[prio] == cl->node+prio)
776+ htb_next_rb_node(p->un.inner.ptr + prio);
777+
778+ htb_safe_rb_erase(cl->node + prio,p->un.inner.feed + prio);
779+
780+ if (!p->un.inner.feed[prio].rb_node)
781+ mask |= 1 << prio;
782+ }
783+ HTB_DBG(7,3,"htb_deact_pr_aft p=%X pact=%X mask=%lX pmode=%d\n",
784+ p->classid,p->prio_activity,mask,p->cmode);
785+ p->prio_activity &= ~mask;
786+ cl = p; p = cl->parent;
787+ HTB_CHCL(cl);
788+ }
789+ if (cl->cmode == HTB_CAN_SEND && mask)
790+ htb_remove_class_from_row(q,cl,mask);
791+}
792+
793+/**
794+ * htb_class_mode - computes and returns current class mode
795+ *
796+ * It computes cl's mode at time cl->t_c+diff and returns it. If mode
797+ * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
798+ * from now to time when cl will change its state.
799+ * Also it is worth to note that class mode doesn't change simply
800+ * at cl->{c,}tokens == 0 but there can rather be hysteresis of
801+ * 0 .. -cl->{c,}buffer range. It is meant to limit number of
802+ * mode transitions per time unit. The speed gain is about 1/6.
803+ */
804+static __inline__ enum htb_cmode
805+htb_class_mode(struct htb_class *cl,long *diff)
806+{
807+ long toks;
808+
809+ if ((toks = (cl->ctokens + *diff)) < (
810+#ifdef HTB_HYSTERESIS
811+ cl->cmode != HTB_CANT_SEND ? -cl->cbuffer :
812+#endif
813+ 0)) {
814+ *diff = -toks;
815+ return HTB_CANT_SEND;
c8436fd6
KT		 816 }
817- /* classification failed; try to use default class */
818- return htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle),q->defcls),sch);
49520c69
KT		 819+ if ((toks = (cl->tokens + *diff)) >= (
820+#ifdef HTB_HYSTERESIS
821+ cl->cmode == HTB_CAN_SEND ? -cl->buffer :
822+#endif
823+ 0))
824+ return HTB_CAN_SEND;
825+
826+ *diff = -toks;
827+ return HTB_MAY_BORROW;
c8436fd6
KT		 828 }
829
830-/* inserts cl into appropriate active lists (for all levels) */
49520c69
KT		 831+/**
832+ * htb_change_class_mode - changes classe's mode
833+ *
834+ * This should be the only way how to change classe's mode under normal
835+ * cirsumstances. Routine will update feed lists linkage, change mode
836+ * and add class to the wait event queue if appropriate. New mode should
837+ * be different from old one and cl->pq_key has to be valid if changing
838+ * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
839+ */
840+static void
841+htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
842+{
843+ enum htb_cmode new_mode = htb_class_mode(cl,diff);
844+
845+ HTB_CHCL(cl);
846+ HTB_DBG(7,1,"htb_chging_clmode %d->%d cl=%X\n",cl->cmode,new_mode,cl->classid);
847+
848+ if (new_mode == cl->cmode)
849+ return;
850+
851+ if (cl->prio_activity) { /* not neccessary: speed optimization */
852+ if (cl->cmode != HTB_CANT_SEND)
853+ htb_deactivate_prios(q,cl);
854+ cl->cmode = new_mode;
855+ if (new_mode != HTB_CANT_SEND)
856+ htb_activate_prios(q,cl);
857+ } else
858+ cl->cmode = new_mode;
859+}
860+
861+/**
862+ * htb_activate - inserts leaf cl into appropriate active feeds
863+ *
864+ * Routine learns (new) priority of leaf and activates feed chain
865+ * for the prio. It can be called on already active leaf safely.
866+ * It also adds leaf into droplist.
867+ */
c8436fd6
KT		 868 static __inline__ void htb_activate(struct htb_sched *q,struct htb_class *cl)
869 {
870- if (!cl->active.prev) {
871- struct htb_class **ap = q->active[(int)(cl->aprio=cl->prio)];
872- int i = !ap[0];
873- HTB_INSERTB(active,ap[0],cl);
874- if (i) /* set also all level pointers */
875- for (i = 1; i < TC_HTB_MAXDEPTH; i++) ap[i] = ap[0];
876- }
49520c69
KT		 877+ BUG_TRAP(!cl->level && cl->un.leaf.q && cl->un.leaf.q->q.qlen);
878+ HTB_CHCL(cl);
879+ if (!cl->prio_activity) {
880+ cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio);
881+ htb_activate_prios(q,cl);
882+ list_add_tail(&cl->un.leaf.drop_list,q->drops+cl->un.leaf.aprio);
883+ }
c8436fd6
KT		 884 }
885
886-/* remove cl from active lists; lev is level at which we dequeued
887- so that we know that active[prio][lev] points to cl */
49520c69
KT		 888+/**
889+ * htb_deactivate - remove leaf cl from active feeds
890+ *
891+ * Make sure that leaf is active. In the other words it can't be called
892+ * with non-active leaf. It also removes class from the drop list.
893+ */
c8436fd6
KT		 894 static __inline__ void
895-htb_deactivate(struct htb_sched *q,struct htb_class *cl,int lev)
49520c69 896+htb_deactivate(struct htb_sched *q,struct htb_class *cl)
c8436fd6
KT		 897 {
898- int i;
899- struct htb_class **ap = q->active[(int)cl->aprio];
900- HTB_DELETE(active,cl,ap[lev]);
901- if (ap[lev]) {
902- /* repair other level pointers if they've pointed
903- to the deleted class */
904- for (i = 0; i < TC_HTB_MAXDEPTH; i++)
905- if (ap[i] == cl) ap[i] = ap[lev];
906- } else
907- memset(ap,0,sizeof(*ap)*TC_HTB_MAXDEPTH);
49520c69
KT		 908+ BUG_TRAP(cl->prio_activity);
909+ HTB_CHCL(cl);
910+ htb_deactivate_prios(q,cl);
911+ cl->prio_activity = 0;
912+ list_del_init(&cl->un.leaf.drop_list);
c8436fd6
KT		 913 }
914
915 static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
916 {
917 struct htb_sched *q = (struct htb_sched *)sch->data;
918- struct htb_class *cl = htb_clasify(skb,sch);
49520c69 919+ struct htb_class *cl = htb_classify(skb,sch);
c8436fd6
KT		 920
921- if (!cl || !cl->q) {
922- /* bad class; enqueue to helper queue */
923- if (q->direct_queue.qlen < q->direct_qlen) {
49520c69
KT		 924+ DEVIK_MSTART(0);
925+ if (cl == HTB_DIRECT || !cl) {
926+ /* enqueue to helper queue */
927+ if (q->direct_queue.qlen < q->direct_qlen && cl) {
c8436fd6
KT		 928 __skb_queue_tail(&q->direct_queue, skb);
929 q->direct_pkts++;
930 } else {
931 kfree_skb (skb);
932 sch->stats.drops++;
49520c69 933+ DEVIK_MEND(0);
c8436fd6
KT		 934 return NET_XMIT_DROP;
935 }
936- } else if (cl->q->enqueue(skb, cl->q) != NET_XMIT_SUCCESS) {
49520c69 937+ } else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) {
c8436fd6
KT		 938 sch->stats.drops++;
939 cl->stats.drops++;
49520c69 940+ DEVIK_MEND(0);
c8436fd6
KT		 941 return NET_XMIT_DROP;
942 } else {
943 cl->stats.packets++; cl->stats.bytes += skb->len;
49520c69 944+ DEVIK_MSTART(1);
c8436fd6 945 htb_activate (q,cl);
49520c69 946+ DEVIK_MEND(1);
c8436fd6
KT		 947 }
948
949 sch->q.qlen++;
950 sch->stats.packets++; sch->stats.bytes += skb->len;
951 HTB_DBG(1,1,"htb_enq_ok cl=%X skb=%p\n",cl?cl->classid:0,skb);
49520c69 952+ DEVIK_MEND(0);
c8436fd6
KT		 953 return NET_XMIT_SUCCESS;
954 }
955
49520c69 956+/* TODO: requeuing packet charges it to policers again !! */
c8436fd6
KT		 957 static int htb_requeue(struct sk_buff *skb, struct Qdisc *sch)
958 {
959 struct htb_sched *q = (struct htb_sched *)sch->data;
960- struct htb_class *cl = htb_clasify(skb,sch);
49520c69 961+ struct htb_class *cl = htb_classify(skb,sch);
c8436fd6
KT		 962
963- if (!cl || !cl->q) {
964- /* bad class; enqueue to helper queue */
965- if (q->direct_queue.qlen < q->direct_qlen) {
49520c69
KT		 966+ if (cl == HTB_DIRECT || !cl) {
967+ /* enqueue to helper queue */
968+ if (q->direct_queue.qlen < q->direct_qlen && cl) {
c8436fd6
KT		 969 __skb_queue_tail(&q->direct_queue, skb);
970 q->direct_pkts++;
971 } else {
972@@ -389,12 +735,12 @@
973 sch->stats.drops++;
974 return NET_XMIT_DROP;
975 }
976- } else if (cl->q->ops->requeue(skb, cl->q) != NET_XMIT_SUCCESS) {
49520c69 977+ } else if (cl->un.leaf.q->ops->requeue(skb, cl->un.leaf.q) != NET_XMIT_SUCCESS) {
c8436fd6
KT		 978 sch->stats.drops++;
979 cl->stats.drops++;
980 return NET_XMIT_DROP;
981 } else
982- htb_activate (q,cl);
49520c69 983+ htb_activate (q,cl);
c8436fd6
KT		 984
985 sch->q.qlen++;
986 HTB_DBG(1,1,"htb_req_ok cl=%X skb=%p\n",cl?cl->classid:0,skb);
987@@ -409,315 +755,251 @@
988 netif_schedule(sch->dev);
989 }
990
49520c69 991+#ifdef HTB_RATECM
c8436fd6
KT		 992 #define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0
993 static void htb_rate_timer(unsigned long arg)
994 {
995- struct Qdisc *sch = (struct Qdisc*)arg;
996- struct htb_sched *q = (struct htb_sched *)sch->data;
997- struct htb_class *cl;
998-
999- /* lock queue so that we can muck with it */
1000- HTB_QLOCK(sch);
1001- HTB_DBG(10,1,"htb_rttmr j=%ld\n",jiffies);
1002-
1003- q->rttim.expires = jiffies + HZ;
1004- add_timer(&q->rttim);
1005-
1006- /* scan and recompute one bucket at time */
1007- if (++q->recmp_bucket >= HTB_HSIZE) q->recmp_bucket = 0;
1008- if ((cl = q->hash[q->recmp_bucket]) != NULL) do {
1009- HTB_DBG(10,2,"htb_rttmr_cl cl=%X sbyte=%lu spkt=%lu\n",cl->classid,cl->sum_bytes,cl->sum_packets);
1010- RT_GEN (cl->sum_bytes,cl->rate_bytes);
1011- RT_GEN (cl->sum_packets,cl->rate_packets);
1012- } while ((cl = cl->hlist.next) != q->hash[q->recmp_bucket]);
1013-
1014- /* global stats */
1015- RT_GEN (q->trials_c,q->trials);
1016- RT_GEN (q->utilz_c,q->utilz);
1017- RT_GEN (q->deq_rate_c,q->deq_rate);
1018-
1019- HTB_QUNLOCK(sch);
1020-}
1021-
1022-/* test whether class can send or borrow packet */
1023-static enum htb_cmode
1024-htb_class_mode(struct htb_sched *q, struct htb_class *cl)
1025-{
1026- long toks,diff;
1027- diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer, 0);
1028- HTB_DBG(6,3,"htb_cm diff=%ld\n",diff);
1029-
1030- /* check whether we are over ceil */
1031- if ((toks = (cl->ctokens + diff)) < 0) {
1032- if (q->delay > -toks || !q->delay) q->delay = -toks;
1033- return HTB_CANT_SEND;
1034- }
1035-
1036- /* our regular rate */
1037- if ((toks = (cl->tokens + diff)) >= 0)
1038- return HTB_CAN_SEND;
1039-
1040- /* record time when we can transmit */
1041- if (q->delay > -toks || !q->delay) q->delay = -toks;
1042-
1043- return HTB_MAY_BORROW;
1044-}
1045-
1046-/* computes (possibly ancestor) class ready to send; cl is leaf;
1047- cl's rc_level is then filled with level we are borrowing at;
1048- it is set to TC_HTB_MAXDEPTH if we can't borrow at all and can be
1049- ORed with HTB_F_INJ if bw was injected. */
1050-static void htb_ready_level(struct htb_sched *q,struct htb_class *cl)
1051-{
1052- struct htb_class *stack[TC_HTB_MAXDEPTH],**sp = stack;
1053- int level = TC_HTB_MAXDEPTH, injdist = cl->injectd;
1054- enum htb_cmode mode;
1055- HTB_DBG(6,1,"htb_rl cl=%X tok=%ld ctok=%ld buf=%ld cbuf=%ld\n",cl->classid,cl->tokens,cl->ctokens,cl->buffer,cl->cbuffer);
1056-
1057- /* traverse tree upward looking for ready class */
1058- for (;;) {
1059- *sp++ = cl; /* push at stack */
1060-
1061- /* test mode */
1062- mode = htb_class_mode(q,cl);
1063- HTB_DBG(6,2,"htb_clmod cl=%X m=%d tok=%ld ctok=%ld buf=%ld cbuf=%ld\n",cl->classid,mode,cl->tokens,cl->ctokens,cl->buffer,cl->cbuffer);
1064- if (mode != HTB_MAY_BORROW) {
1065- if (mode == HTB_CAN_SEND) level = cl->level;
1066- break;
1067- }
1068- /* update injdist from current node */
1069- if (injdist > cl->injectd) injdist = cl->injectd;
1070-
1071- /* if this is leaf's injector then resolve borrow positively */
1072- if (!injdist--) {
1073- /* don't cache this result in interior nodes */
1074- stack[0]->rc_level = cl->level|HTB_F_INJ;
1075- stack[0]->rcache_sn = q->sn;
1076- return;
1077- }
1078- if ((cl = cl->parent) == NULL) break;
1079- if (q->sn == cl->rcache_sn) {
1080- /* the node has already computed result; use it */
1081- level = cl->rc_level; break;
49520c69
KT		 1082+ struct Qdisc *sch = (struct Qdisc*)arg;
1083+ struct htb_sched *q = (struct htb_sched *)sch->data;
1084+ struct list_head *p;
1085+
1086+ /* lock queue so that we can muck with it */
1087+ HTB_QLOCK(sch);
1088+ HTB_DBG(10,1,"htb_rttmr j=%ld\n",jiffies);
1089+
1090+ q->rttim.expires = jiffies + HZ;
1091+ add_timer(&q->rttim);
1092+
1093+ /* scan and recompute one bucket at time */
1094+ if (++q->recmp_bucket >= HTB_HSIZE)
1095+ q->recmp_bucket = 0;
1096+ list_for_each (p,q->hash+q->recmp_bucket) {
1097+ struct htb_class *cl = list_entry(p,struct htb_class,hlist);
1098+ HTB_DBG(10,2,"htb_rttmr_cl cl=%X sbyte=%lu spkt=%lu\n",
1099+ cl->classid,cl->sum_bytes,cl->sum_packets);
1100+ RT_GEN (cl->sum_bytes,cl->rate_bytes);
1101+ RT_GEN (cl->sum_packets,cl->rate_packets);
c8436fd6
KT		 1102 }
1103- }
1104- while (--sp >= stack) { /* update mode cache */
1105- (*sp)->rcache_sn = q->sn;
1106- (*sp)->rc_level = level;
1107- }
49520c69 1108+ HTB_QUNLOCK(sch);
c8436fd6 1109 }
49520c69 1110+#endif
c8436fd6
KT		 1111
1112-/* pull packet from class and charge to ancestors */
1113-static struct sk_buff *
1114-htb_dequeue_class(struct Qdisc *sch, struct htb_class *cl)
49520c69
KT		 1115+/**
1116+ * htb_charge_class - charges ammount "bytes" to leaf and ancestors
1117+ *
1118+ * Routine assumes that packet "bytes" long was dequeued from leaf cl
1119+ * borrowing from "level". It accounts bytes to ceil leaky bucket for
1120+ * leaf and all ancestors and to rate bucket for ancestors at levels
1121+ * "level" and higher. It also handles possible change of mode resulting
1122+ * from the update. Note that mode can also increase here (MAY_BORROW to
1123+ * CAN_SEND) because we can use more precise clock that event queue here.
1124+ * In such case we remove class from event queue first.
1125+ */
1126+static void htb_charge_class(struct htb_sched *q,struct htb_class *cl,
1127+ int level,int bytes)
c8436fd6
KT		 1128 {
1129- struct htb_sched *q = (struct htb_sched *)sch->data;
1130- long toks,diff;
1131- int injecting = cl->rc_level & HTB_F_INJ, injdist = cl->injectd;
1132- int level = cl->rc_level & 0xff;
1133- struct sk_buff *skb = cl->q->dequeue(cl->q);
1134- HTB_DBG(5,1,"htb_deq_cl cl=%X skb=%p lev=%d inj=%d\n",cl->classid,skb,level,injecting);
1135- if (!skb) return NULL;
1136-
1137- /* we have got skb, account it to victim and its parents
1138- and also to all ceil estimators under victim */
1139- while (cl) {
1140- diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer, 0);
49520c69
KT		 1141+ long toks,diff;
1142+ enum htb_cmode old_mode;
1143+ HTB_DBG(5,1,"htb_chrg_cl cl=%X lev=%d len=%d\n",cl->classid,level,bytes);
c8436fd6
KT		 1144
1145 #define HTB_ACCNT(T,B,R) toks = diff + cl->T; \
1146 if (toks > cl->B) toks = cl->B; \
1147- toks -= L2T(cl, cl->R, skb->len); \
49520c69 1148+ toks -= L2T(cl, cl->R, bytes); \
c8436fd6
KT		 1149 if (toks <= -cl->mbuffer) toks = 1-cl->mbuffer; \
1150- cl->T = toks
1151-
1152- HTB_ACCNT (ctokens,cbuffer,ceil);
1153- if (cl->level >= level) {
1154- if (cl->level == level) cl->xstats.lends++;
1155- HTB_ACCNT (tokens,buffer,rate);
1156- } else {
1157- cl->xstats.borrows++;
1158- cl->tokens += diff; /* we moved t_c; update tokens */
1159- }
1160- cl->t_c = q->now;
1161- HTB_DBG(5,2,"htb_deq_clp cl=%X clev=%d diff=%ld\n",cl->classid,cl->level,diff);
49520c69 1162+ cl->T = toks
c8436fd6
KT		 1163
1164- /* update rate counters */
1165- cl->sum_bytes += skb->len; cl->sum_packets++;
49520c69
KT		 1166+ while (cl) {
1167+ HTB_CHCL(cl);
1168+ diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer, 0);
1169+#ifdef HTB_DEBUG
1170+ if (diff > cl->mbuffer || diff < 0 || PSCHED_TLESS(q->now, cl->t_c)) {
1171+ if (net_ratelimit())
1172+ printk(KERN_ERR "HTB: bad diff in charge, cl=%X diff=%lX now=%Lu then=%Lu j=%lu\n",
1173+ cl->classid, diff,
1174+ (unsigned long long) q->now,
1175+ (unsigned long long) cl->t_c,
1176+ jiffies);
1177+ diff = 1000;
1178+ }
1179+#endif
1180+ if (cl->level >= level) {
1181+ if (cl->level == level) cl->xstats.lends++;
1182+ HTB_ACCNT (tokens,buffer,rate);
1183+ } else {
1184+ cl->xstats.borrows++;
1185+ cl->tokens += diff; /* we moved t_c; update tokens */
1186+ }
1187+ HTB_ACCNT (ctokens,cbuffer,ceil);
1188+ cl->t_c = q->now;
1189+ HTB_DBG(5,2,"htb_chrg_clp cl=%X diff=%ld tok=%ld ctok=%ld\n",cl->classid,diff,cl->tokens,cl->ctokens);
1190+
1191+ old_mode = cl->cmode; diff = 0;
1192+ htb_change_class_mode(q,cl,&diff);
1193+ if (old_mode != cl->cmode) {
1194+ if (old_mode != HTB_CAN_SEND)
1195+ htb_safe_rb_erase(&cl->pq_node,q->wait_pq+cl->level);
1196+ if (cl->cmode != HTB_CAN_SEND)
1197+ htb_add_to_wait_tree (q,cl,diff,1);
1198+ }
1199+
1200+#ifdef HTB_RATECM
1201+ /* update rate counters */
1202+ cl->sum_bytes += bytes; cl->sum_packets++;
1203+#endif
c8436fd6
KT		 1204
1205- /* update byte stats except for leaves which are already updated */
1206- if (cl->level) {
1207- cl->stats.bytes += skb->len;
1208- cl->stats.packets++;
1209- }
1210- /* finish if we hit stop-class and we are injecting */
1211- if (injecting) {
1212- if (injdist > cl->injectd) injdist = cl->injectd;
1213- if (!injdist--) {
1214- cl->xstats.injects++; break;
1215- }
49520c69
KT		 1216+ /* update byte stats except for leaves which are already updated */
1217+ if (cl->level) {
1218+ cl->stats.bytes += bytes;
1219+ cl->stats.packets++;
1220+ }
1221+ cl = cl->parent;
c8436fd6
KT		 1222 }
1223- cl = cl->parent;
1224- }
1225- return skb;
1226 }
1227
1228-/* dequeues packet at given priority borrowing from given level;
1229- if unsuccessfull then it returns level at which someone can
1230- dequeue. If it sets level to TC_HTB_MAXDEPTH then no one can. */
1231-static struct sk_buff *htb_dequeue_prio(struct Qdisc *sch,int prio,int *level)
49520c69
KT		 1232+/**
1233+ * htb_do_events - make mode changes to classes at the level
1234+ *
1235+ * Scans event queue for pending events and applies them. Returns jiffies to
1236+ * next pending event (0 for no event in pq).
1237+ */
1238+static long htb_do_events(struct htb_sched *q,int level)
c8436fd6
KT		 1239 {
1240- struct sk_buff *skb = NULL;
1241- struct htb_sched *q = (struct htb_sched *)sch->data;
1242- struct htb_class **ap = q->active[prio], *cl = ap[*level];
1243- int done,top = TC_HTB_MAXDEPTH,rclev;
1244-
1245- HTB_DBG(4,1,"htb_deq_pr pr=%d lev=%d cl=%X\n",prio,*level,cl->classid);
1246- /* this is DRR algorithm */
1247- do {
1248- done = 1;
1249- do {
1250- /* catch empty classes here; note that we don't remove them
1251- immediately after dequeue but rather delay remove to next
1252- DRR round because if packet arrive for just emptied class
1253- then we don't need to remove and again add it */
1254- if (!cl->q->q.qlen) {
1255- ap[*level] = cl; /* needed for HTB_DELETE in deactivate */
1256- htb_deactivate (q,cl,*level);
1257-
1258- HTB_DBG(4,2,"htb_deq_deact cl=%X ncl=%X\n",cl->classid,ap[*level]?ap[*level]->classid:0);
1259- if (ap[*level]) continue;
1260- *level = TC_HTB_MAXDEPTH;
1261- return NULL; /* NO class remains active */
1262- }
1263- /* test whether class can send at all borrowing from level */
1264- if (cl->rcache_sn != q->sn) htb_ready_level(q,cl);
1265- rclev = cl->rc_level & 0xff; /* filter injecting flag out */
1266-
1267- HTB_DBG(4,2,"htb_deq_rd cl=%X rc_lev=0x%x dfct=%d qnt=%d\n",
1268- cl->classid,cl->rc_level,cl->deficit[*level],cl->quantum);
1269-
1270- if (rclev == TC_HTB_MAXDEPTH) {
1271- /* TODO: overlimit increment here is not proven correct */
1272- if (cl->deficit[*level] > 0) cl->stats.overlimits++;
1273- continue; /* can't send or borrow */
1274- }
1275- /* if we can't send at this level, remember where we can */
1276- if (rclev > *level) {
1277- if (rclev < top) /* keep lowest level */
1278- top = rclev;
1279-
1280- HTB_DBG(4,2,"htb_deq_badlev top=%d\n",top);
1281- continue;
1282- }
1283- if (cl->deficit[*level] <= 0) {
1284- /* haven't allotment, increase and try again */
1285- done = 0; cl->deficit[*level] += cl->quantum;
1286- continue;
1287- }
1288- if ((skb = htb_dequeue_class(sch,cl)) == NULL) {
1289- /* nonempty class can't dequeue so that mark it as such;
1290- note that rcache_sn is already set and thus this remarking
1291- will be valid only for rest of this dequeue; this is
1292- possible if child class is non work conserving */
1293- cl->rc_level = TC_HTB_MAXDEPTH;
1294-
1295- HTB_DBG(4,2,"htb_deq_noskb cl=%X len=%d\n",cl->classid,cl->q->q.qlen);
1296- continue;
1297- }
1298- sch->q.qlen--;
1299- /* prepare next class if we can't stay valid */
1300- if ((cl->deficit[*level] -= skb->len) <= 0) cl = cl->active.next;
1301- else if (q->use_dcache)
1302- q->last_tx = cl; /* cache cl if it still can transmit */
1303- ap[*level] = cl;
1304-
1305- HTB_DBG(4,1,"htb_deq_haspkt ncl=%X sqlen=%d\n",cl->classid,sch->q.qlen);
1306- return skb;
1307-
1308- } while ((cl = cl->active.next) != ap[*level]);
1309-
1310- } while (!done);
1311- *level = top;
1312- HTB_DBG(4,1,"htb_deq_quit top=%d\n",top);
1313- return NULL;
49520c69
KT		 1314+ int i;
1315+ HTB_DBG(8,1,"htb_do_events l=%d root=%p rmask=%X\n",
1316+ level,q->wait_pq[level].rb_node,q->row_mask[level]);
1317+ for (i = 0; i < 500; i++) {
1318+ struct htb_class *cl;
1319+ long diff;
1320+ rb_node_t *p = q->wait_pq[level].rb_node;
1321+ if (!p) return 0;
1322+ while (p->rb_left) p = p->rb_left;
1323+
1324+ cl = rb_entry(p, struct htb_class, pq_node);
1325+ if (cl->pq_key - (jiffies+1) < 0x80000000) {
1326+ HTB_DBG(8,3,"htb_do_ev_ret delay=%ld\n",cl->pq_key - jiffies);
1327+ return cl->pq_key - jiffies;
1328+ }
1329+ htb_safe_rb_erase(p,q->wait_pq+level);
1330+ diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32)cl->mbuffer, 0);
1331+#ifdef HTB_DEBUG
1332+ if (diff > cl->mbuffer || diff < 0 || PSCHED_TLESS(q->now, cl->t_c)) {
1333+ if (net_ratelimit())
1334+ printk(KERN_ERR "HTB: bad diff in events, cl=%X diff=%lX now=%Lu then=%Lu j=%lu\n",
1335+ cl->classid, diff,
1336+ (unsigned long long) q->now,
1337+ (unsigned long long) cl->t_c,
1338+ jiffies);
1339+ diff = 1000;
1340+ }
1341+#endif
1342+ htb_change_class_mode(q,cl,&diff);
1343+ if (cl->cmode != HTB_CAN_SEND)
1344+ htb_add_to_wait_tree (q,cl,diff,2);
1345+ }
1346+ if (net_ratelimit())
1347+ printk(KERN_WARNING "htb: too many events !\n");
1348+ return HZ/10;
c8436fd6
KT		 1349 }
1350
1351-static struct sk_buff *htb_dequeue(struct Qdisc *sch)
49520c69
KT		 1352+/**
1353+ * htb_lookup_leaf - returns next leaf class in DRR order
1354+ *
1355+ * Find leaf where current feed pointers points to.
1356+ */
1357+static struct htb_class *
1358+htb_lookup_leaf(rb_root_t *tree,int prio,rb_node_t **pptr)
c8436fd6
KT		 1359 {
1360- struct sk_buff *skb = NULL;
1361- struct htb_sched *q = (struct htb_sched *)sch->data;
1362- int prio,oklev,okprio = 0 /* avoid unused warning */,lev,i;
1363- struct htb_class *cl;
1364- psched_time_t endt;
1365-
1366- HTB_DBG(3,1,"htb_deq dircnt=%d ltx=%X\n",skb_queue_len(&q->direct_queue),
1367- q->last_tx?q->last_tx->classid:0);
1368-
1369- /* try to dequeue direct packets as high prio (!) to minimize cpu work */
1370- if ((skb = __skb_dequeue(&q->direct_queue)) != NULL) {
1371- sch->flags &= ~TCQ_F_THROTTLED;
1372- sch->q.qlen--;
1373- return skb;
1374- }
1375-
1376- PSCHED_GET_TIME(q->now); /* htb_dequeue_class needs it too */
1377- q->delay = 0; q->sn++;
49520c69
KT		 1378+ int i;
1379+ struct {
1380+ rb_node_t *root;
1381+ rb_node_t **pptr;
1382+ } stk[TC_HTB_MAXDEPTH],*sp = stk;
1383+
1384+ sp->root = tree->rb_node;
1385+ sp->pptr = pptr;
1386+
1387+ for (i = 0; i < 65535; i++) {
1388+ if (!*sp->pptr) { /* we are at right end; rewind & go up */
1389+ *sp->pptr = sp->root;
1390+ while ((*sp->pptr)->rb_left)
1391+ *sp->pptr = (*sp->pptr)->rb_left;
1392+ if (sp > stk) {
1393+ sp--;
1394+ BUG_TRAP(*sp->pptr); if(!*sp->pptr) return NULL;
1395+ htb_next_rb_node (sp->pptr);
1396+ }
1397+ } else {
1398+ struct htb_class *cl;
1399+ cl = rb_entry(*sp->pptr,struct htb_class,node[prio]);
1400+ HTB_CHCL(cl);
1401+ if (!cl->level)
1402+ return cl;
1403+ (++sp)->root = cl->un.inner.feed[prio].rb_node;
1404+ sp->pptr = cl->un.inner.ptr+prio;
1405+ }
1406+ }
1407+ BUG_TRAP(0);
1408+ return NULL;
1409+}
c8436fd6
KT		 1410
1411- /* well here I bite CBQ's speed :-) if last dequeued class is
1412- still active and is not deficit then we can dequeue it again */
1413- if ((cl = q->last_tx) != NULL && cl->q->q.qlen > 0 &&
1414- cl->deficit[cl->rc_level & 0xff] > 0 &&
1415- (skb = htb_dequeue_class(sch,cl)) != NULL) {
1416- sch->q.qlen--;
1417- cl->deficit[cl->rc_level & 0xff] -= skb->len;
1418- sch->flags &= ~TCQ_F_THROTTLED;
1419- q->dcache_hits++;
1420- HTB_DBG(3,1,"htb_deq_hit skb=%p\n",skb);
49520c69
KT		 1421+/* dequeues packet at given priority and level; call only if
1422+ you are sure that there is active class at prio/level */
1423+static struct sk_buff *
1424+htb_dequeue_tree(struct htb_sched *q,int prio,int level)
1425+{
1426+ struct sk_buff *skb = NULL;
1427+ //struct htb_sched *q = (struct htb_sched *)sch->data;
1428+ struct htb_class *cl,*start;
1429+ /* look initial class up in the row */
1430+ DEVIK_MSTART(6);
1431+ start = cl = htb_lookup_leaf (q->row[level]+prio,prio,q->ptr[level]+prio);
1432+
1433+ do {
1434+ BUG_TRAP(cl && cl->un.leaf.q->q.qlen); if (!cl) return NULL;
1435+ HTB_DBG(4,1,"htb_deq_tr prio=%d lev=%d cl=%X defic=%d\n",
1436+ prio,level,cl->classid,cl->un.leaf.deficit[level]);
1437+
1438+ if (likely((skb = cl->un.leaf.q->dequeue(cl->un.leaf.q)) != NULL))
1439+ break;
1440+ if (!cl->warned) {
1441+ printk(KERN_WARNING "htb: class %X isn't work conserving ?!\n",cl->classid);
1442+ cl->warned = 1;
1443+ }
1444+ q->nwc_hit++;
1445+ htb_next_rb_node((level?cl->parent->un.inner.ptr:q->ptr[0])+prio);
1446+ cl = htb_lookup_leaf (q->row[level]+prio,prio,q->ptr[level]+prio);
1447+ } while (cl != start);
1448+
1449+ DEVIK_MEND(6);
1450+ DEVIK_MSTART(7);
1451+ if (likely(skb != NULL)) {
1452+ if ((cl->un.leaf.deficit[level] -= skb->len) < 0) {
1453+ HTB_DBG(4,2,"htb_next_cl oldptr=%p quant_add=%d\n",
1454+ level?cl->parent->un.inner.ptr[prio]:q->ptr[0][prio],cl->un.leaf.quantum);
1455+ cl->un.leaf.deficit[level] += cl->un.leaf.quantum;
1456+ htb_next_rb_node((level?cl->parent->un.inner.ptr:q->ptr[0])+prio);
1457+ }
1458+ /* this used to be after charge_class but this constelation
1459+ gives us slightly better performance */
1460+ if (!cl->un.leaf.q->q.qlen)
1461+ htb_deactivate (q,cl);
1462+ DEVIK_MSTART(8);
1463+ htb_charge_class (q,cl,level,skb->len);
1464+ DEVIK_MEND(8);
1465+ }
1466+ DEVIK_MEND(7);
c8436fd6
KT		 1467 return skb;
1468- }
1469- q->last_tx = NULL; /* can't use cache ? invalidate */
1470-
1471- for (i = 0; i < TC_HTB_MAXDEPTH; i++) {
1472- /* first try: dequeue leaves (level 0) */
1473- oklev = TC_HTB_MAXDEPTH;
1474- q->trials_c++;
1475- for (prio = 0; prio < TC_HTB_NUMPRIO; prio++) {
1476- if (!q->active[prio][0]) continue;
1477- lev = 0; skb = htb_dequeue_prio(sch, prio, &lev);
1478- HTB_DBG(3,2,"htb_deq_1 i=%d p=%d skb=%p blev=%d\n",i,prio,skb,lev);
1479- if (skb) {
1480- sch->flags &= ~TCQ_F_THROTTLED;
1481- goto fin;
1482- }
1483- if (lev < oklev) {
1484- oklev = lev; okprio = prio;
1485- }
1486- }
1487- if (oklev >= TC_HTB_MAXDEPTH) break;
1488- /* second try: use ok level we learned in first try;
1489- it really should succeed */
1490- q->trials_c++;
1491- skb = htb_dequeue_prio(sch, okprio, &oklev);
1492- HTB_DBG(3,2,"htb_deq_2 p=%d lev=%d skb=%p\n",okprio,oklev,skb);
1493- if (skb) {
1494- sch->flags &= ~TCQ_F_THROTTLED;
1495- goto fin;
1496- }
1497- /* probably qdisc at oklev can't transmit - it is not good
1498- idea to have TBF as HTB's child ! retry with that node
1499- disabled */
1500- }
1501- if (i >= TC_HTB_MAXDEPTH)
1502- printk(KERN_ERR "htb: too many dequeue trials\n");
49520c69 1503+}
c8436fd6
KT		 1504
1505- /* no-one gave us packet, setup timer if someone wants it */
1506- if (sch->q.qlen && !netif_queue_stopped(sch->dev) && q->delay) {
1507- long delay = PSCHED_US2JIFFIE(q->delay);
1508- if (delay == 0) delay = 1;
1509- if (delay > 5*HZ) {
1510- if (net_ratelimit())
1511- printk(KERN_INFO "HTB delay %ld > 5sec\n", delay);
1512- delay = 5*HZ;
49520c69
KT		 1513+static void htb_delay_by(struct Qdisc *sch,long delay)
1514+{
1515+ struct htb_sched *q = (struct htb_sched *)sch->data;
1516+ if (netif_queue_stopped(sch->dev)) return;
1517+ if (delay <= 0) delay = 1;
1518+ if (unlikely(delay > 5*HZ)) {
1519+ if (net_ratelimit())
1520+ printk(KERN_INFO "HTB delay %ld > 5sec\n", delay);
1521+ delay = 5*HZ;
c8436fd6
KT		 1522 }
1523 del_timer(&q->timer);
1524 q->timer.expires = jiffies + delay;
1525@@ -725,439 +1007,605 @@
1526 sch->flags |= TCQ_F_THROTTLED;
1527 sch->stats.overlimits++;
1528 HTB_DBG(3,1,"htb_deq t_delay=%ld\n",delay);
1529- }
1530-fin:
1531- do {
1532- static unsigned util = 0; unsigned d;
1533- PSCHED_GET_TIME(endt); q->deq_rate_c++;
1534- d = PSCHED_TDIFF(endt,q->now);
1535- q->utilz_c += d; util += d;
1536-#if 0
1537- /* special debug hack */
1538- if (skb) {
1539- memcpy (skb->data+28,_dbg,sizeof(_dbg));
1540- memset (_dbg,0,sizeof(_dbg));
49520c69
KT		 1541+}
1542+
1543+static struct sk_buff *htb_dequeue(struct Qdisc *sch)
1544+{
1545+ struct sk_buff *skb = NULL;
1546+ struct htb_sched *q = (struct htb_sched *)sch->data;
1547+ int level;
1548+ long min_delay;
1549+
1550+ HTB_DBG(3,1,"htb_deq dircnt=%d qlen=%d\n",skb_queue_len(&q->direct_queue),
1551+ sch->q.qlen);
1552+
1553+ /* try to dequeue direct packets as high prio (!) to minimize cpu work */
1554+ if ((skb = __skb_dequeue(&q->direct_queue)) != NULL) {
1555+ sch->flags &= ~TCQ_F_THROTTLED;
1556+ sch->q.qlen--;
1557+ return skb;
1558+ }
1559+
1560+ DEVIK_MSTART(2);
1561+ if (!sch->q.qlen) goto fin;
1562+ PSCHED_GET_TIME(q->now);
1563+
1564+ min_delay = HZ*5;
1565+ q->nwc_hit = 0;
1566+ for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
1567+ /* common case optimization - skip event handler quickly */
1568+ int m;
1569+ long delay;
1570+ DEVIK_MSTART(3);
1571+ if (jiffies - q->near_ev_cache[level] < 0x80000000 || 0) {
1572+ delay = htb_do_events(q,level);
1573+ q->near_ev_cache[level] += delay ? delay : HZ;
1574+ } else
1575+ delay = q->near_ev_cache[level] - jiffies;
1576+
1577+ if (delay && min_delay > delay)
1578+ min_delay = delay;
1579+ DEVIK_MEND(3);
1580+ DEVIK_MSTART(5);
1581+ m = ~q->row_mask[level];
1582+ while (m != (int)(-1)) {
1583+ int prio = ffz (m);
1584+ m |= 1 << prio;
1585+ skb = htb_dequeue_tree(q,prio,level);
1586+ if (likely(skb != NULL)) {
1587+ sch->q.qlen--;
1588+ sch->flags &= ~TCQ_F_THROTTLED;
1589+ DEVIK_MEND(5);
1590+ goto fin;
1591+ }
1592+ }
1593+ DEVIK_MEND(5);
1594+ }
1595+ DEVIK_MSTART(4);
1596+#ifdef HTB_DEBUG
1597+ if (!q->nwc_hit && min_delay >= 5*HZ && net_ratelimit()) {
1598+ printk(KERN_ERR "HTB: mindelay=%ld, report it please !\n",min_delay);
1599+ htb_debug_dump(q);
c8436fd6
KT		 1600 }
1601 #endif
1602- } while (0);
1603- HTB_DBG(3,1,"htb_deq_end %s j=%lu skb=%p (28/11)\n",sch->dev->name,jiffies,skb);
1604- return skb;
49520c69
KT		 1605+ htb_delay_by (sch,min_delay);
1606+ DEVIK_MEND(4);
1607+fin:
1608+ HTB_DBG(3,1,"htb_deq_end %s j=%lu skb=%p\n",sch->dev->name,jiffies,skb);
1609+ DEVIK_MEND(2);
1610+ return skb;
c8436fd6
KT		 1611 }
1612
1613 /* try to drop from each class (by prio) until one succeed */
1614 static int htb_drop(struct Qdisc* sch)
1615 {
1616- struct htb_sched *q = (struct htb_sched *)sch->data;
1617- int prio;
49520c69
KT		 1618+ struct htb_sched *q = (struct htb_sched *)sch->data;
1619+ int prio;
c8436fd6
KT		 1620
1621- for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
1622- struct htb_class *cl = q->active[prio][0];
1623- if (cl) do {
1624- if (cl->q->ops->drop && cl->q->ops->drop(cl->q)) {
1625- sch->q.qlen--;
1626- return 1;
1627- }
1628- } while ((cl = cl->active.next) != q->active[prio][0]);
1629- }
1630- return 0;
49520c69
KT		 1631+ for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
1632+ struct list_head *p;
1633+ list_for_each (p,q->drops+prio) {
1634+ struct htb_class *cl = list_entry(p,struct htb_class,
1635+ un.leaf.drop_list);
1636+ if (cl->un.leaf.q->ops->drop &&
1637+ cl->un.leaf.q->ops->drop(cl->un.leaf.q)) {
1638+ sch->q.qlen--;
1639+ if (!cl->un.leaf.q->q.qlen)
1640+ htb_deactivate (q,cl);
1641+ return 1;
1642+ }
1643+ }
1644+ }
1645+ return 0;
c8436fd6
KT		 1646 }
1647
1648 /* reset all classes */
1649 /* always caled under BH & queue lock */
1650 static void htb_reset(struct Qdisc* sch)
1651 {
1652- struct htb_sched *q = (struct htb_sched *)sch->data;
1653- int i;
1654- HTB_DBG(0,1,"htb_reset sch=%X, handle=%X\n",(int)sch,sch->handle);
1655-
1656- for (i = 0; i < HTB_HSIZE; i++) {
1657- struct htb_class *cl = q->hash[i];
1658- if (cl) do {
1659- if (cl->q) qdisc_reset(cl->q);
49520c69
KT		 1660+ struct htb_sched *q = (struct htb_sched *)sch->data;
1661+ int i;
1662+ HTB_DBG(0,1,"htb_reset sch=%p, handle=%X\n",sch,sch->handle);
1663+
1664+ for (i = 0; i < HTB_HSIZE; i++) {
1665+ struct list_head *p;
1666+ list_for_each (p,q->hash+i) {
1667+ struct htb_class *cl = list_entry(p,struct htb_class,hlist);
1668+ if (cl->level)
1669+ memset(&cl->un.inner,0,sizeof(cl->un.inner));
1670+ else {
1671+ if (cl->un.leaf.q)
1672+ qdisc_reset(cl->un.leaf.q);
1673+ INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1674+ }
1675+ cl->prio_activity = 0;
1676+ cl->cmode = HTB_CAN_SEND;
1677+#ifdef HTB_DEBUG
1678+ cl->pq_node.rb_color = -1;
1679+ memset(cl->node,255,sizeof(cl->node));
1680+#endif
c8436fd6
KT		 1681
1682- } while ((cl = cl->hlist.next) != q->hash[i]);
1683- }
1684- sch->flags &= ~TCQ_F_THROTTLED;
1685- del_timer(&q->timer);
1686- __skb_queue_purge(&q->direct_queue);
1687- sch->q.qlen = 0; q->last_tx = NULL;
49520c69
KT		 1688+ }
1689+ }
1690+ sch->flags &= ~TCQ_F_THROTTLED;
1691+ del_timer(&q->timer);
1692+ __skb_queue_purge(&q->direct_queue);
1693+ sch->q.qlen = 0;
1694+ memset(q->row,0,sizeof(q->row));
1695+ memset(q->row_mask,0,sizeof(q->row_mask));
1696+ memset(q->wait_pq,0,sizeof(q->wait_pq));
1697+ memset(q->ptr,0,sizeof(q->ptr));
1698+ for (i = 0; i < TC_HTB_NUMPRIO; i++)
1699+ INIT_LIST_HEAD(q->drops+i);
c8436fd6
KT		 1700 }
1701
1702 static int htb_init(struct Qdisc *sch, struct rtattr *opt)
1703 {
1704- struct htb_sched *q = (struct htb_sched*)sch->data;
1705- struct rtattr *tb[TCA_HTB_INIT];
1706- struct tc_htb_glob *gopt;
1707-
1708- if (!opt ||
1709- rtattr_parse(tb, TCA_HTB_INIT, RTA_DATA(opt), RTA_PAYLOAD(opt)) ||
1710- tb[TCA_HTB_INIT-1] == NULL ||
1711- RTA_PAYLOAD(tb[TCA_HTB_INIT-1]) < sizeof(*gopt))
1712- return -EINVAL;
1713-
1714- gopt = RTA_DATA(tb[TCA_HTB_INIT-1]);
1715- memset(q,0,sizeof(*q));
1716- q->debug = gopt->debug;
1717- HTB_DBG(0,1,"htb_init sch=%p handle=%X r2q=%d\n",sch,sch->handle,gopt->rate2quantum);
1718- init_timer(&q->timer);
1719- init_timer(&q->rttim);
1720- skb_queue_head_init(&q->direct_queue);
1721- q->direct_qlen = sch->dev->tx_queue_len;
1722- q->timer.function = htb_timer;
1723- q->timer.data = (unsigned long)sch;
1724- q->rttim.function = htb_rate_timer;
1725- q->rttim.data = (unsigned long)sch;
1726- q->rttim.expires = jiffies + HZ;
1727- add_timer(&q->rttim);
1728- if ((q->rate2quantum = gopt->rate2quantum) < 1)
1729- q->rate2quantum = 1;
1730- q->defcls = gopt->defcls;
1731- q->use_dcache = gopt->use_dcache;
49520c69
KT		 1732+ struct htb_sched *q = (struct htb_sched*)sch->data;
1733+ struct rtattr *tb[TCA_HTB_INIT];
1734+ struct tc_htb_glob *gopt;
1735+ int i;
1736+#ifdef HTB_DEBUG
1737+ printk(KERN_INFO "HTB init, kernel part version %d.%d\n",
1738+ HTB_VER >> 16,HTB_VER & 0xffff);
1739+#endif
1740+ if (!opt || rtattr_parse(tb, TCA_HTB_INIT, RTA_DATA(opt), RTA_PAYLOAD(opt)) ||
1741+ tb[TCA_HTB_INIT-1] == NULL ||
1742+ RTA_PAYLOAD(tb[TCA_HTB_INIT-1]) < sizeof(*gopt)) {
1743+ printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n");
1744+ return -EINVAL;
1745+ }
1746+ gopt = RTA_DATA(tb[TCA_HTB_INIT-1]);
1747+ if (gopt->version != HTB_VER >> 16) {
1748+ printk(KERN_ERR "HTB: need tc/htb version %d (minor is %d), you have %d\n",
1749+ HTB_VER >> 16,HTB_VER & 0xffff,gopt->version);
1750+ return -EINVAL;
1751+ }
1752+ memset(q,0,sizeof(*q));
1753+ q->debug = gopt->debug;
1754+ HTB_DBG(0,1,"htb_init sch=%p handle=%X r2q=%d\n",sch,sch->handle,gopt->rate2quantum);
1755+
1756+ INIT_LIST_HEAD(&q->root);
1757+ for (i = 0; i < HTB_HSIZE; i++)
1758+ INIT_LIST_HEAD(q->hash+i);
1759+ for (i = 0; i < TC_HTB_NUMPRIO; i++)
1760+ INIT_LIST_HEAD(q->drops+i);
1761+
1762+ init_timer(&q->timer);
1763+ skb_queue_head_init(&q->direct_queue);
1764+
1765+ q->direct_qlen = sch->dev->tx_queue_len;
1766+ if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
1767+ q->direct_qlen = 2;
1768+ q->timer.function = htb_timer;
1769+ q->timer.data = (unsigned long)sch;
1770+
1771+#ifdef HTB_RATECM
1772+ init_timer(&q->rttim);
1773+ q->rttim.function = htb_rate_timer;
1774+ q->rttim.data = (unsigned long)sch;
1775+ q->rttim.expires = jiffies + HZ;
1776+ add_timer(&q->rttim);
1777+#endif
1778+ if ((q->rate2quantum = gopt->rate2quantum) < 1)
1779+ q->rate2quantum = 1;
1780+ q->defcls = gopt->defcls;
c8436fd6
KT		 1781
1782- MOD_INC_USE_COUNT;
1783- return 0;
49520c69
KT		 1784+ MOD_INC_USE_COUNT;
1785+ return 0;
c8436fd6
KT		 1786 }
1787
1788-#ifdef CONFIG_RTNETLINK
1789 static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1790 {
1791- struct htb_sched *q = (struct htb_sched*)sch->data;
1792- unsigned char *b = skb->tail;
1793- struct rtattr *rta;
1794- struct tc_htb_glob gopt;
1795- HTB_DBG(0,1,"htb_dump sch=%p, handle=%X\n",sch,sch->handle);
1796- /* stats */
1797- HTB_QLOCK(sch);
1798- gopt.deq_rate = q->deq_rate/HTB_EWMAC;
1799- gopt.utilz = q->utilz/HTB_EWMAC;
1800- gopt.trials = q->trials/HTB_EWMAC;
1801- gopt.dcache_hits = q->dcache_hits;
1802- gopt.direct_pkts = q->direct_pkts;
1803-
1804- gopt.use_dcache = q->use_dcache;
1805- gopt.rate2quantum = q->rate2quantum;
1806- gopt.defcls = q->defcls;
1807- gopt.debug = q->debug;
1808- rta = (struct rtattr*)b;
1809- RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1810- RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
1811- rta->rta_len = skb->tail - b;
1812- sch->stats.qlen = sch->q.qlen;
1813- RTA_PUT(skb, TCA_STATS, sizeof(sch->stats), &sch->stats);
1814- HTB_QUNLOCK(sch);
1815- return skb->len;
49520c69
KT		 1816+ struct htb_sched *q = (struct htb_sched*)sch->data;
1817+ unsigned char *b = skb->tail;
1818+ struct rtattr *rta;
1819+ struct tc_htb_glob gopt;
1820+ HTB_DBG(0,1,"htb_dump sch=%p, handle=%X\n",sch,sch->handle);
1821+ /* stats */
1822+ HTB_QLOCK(sch);
1823+ gopt.direct_pkts = q->direct_pkts;
1824+
1825+#ifdef HTB_DEBUG
1826+ htb_debug_dump(q);
1827+#endif
1828+ gopt.version = HTB_VER;
1829+ gopt.rate2quantum = q->rate2quantum;
1830+ gopt.defcls = q->defcls;
1831+ gopt.debug = q->debug;
1832+ rta = (struct rtattr*)b;
1833+ RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1834+ RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
1835+ rta->rta_len = skb->tail - b;
1836+ sch->stats.qlen = sch->q.qlen;
1837+ RTA_PUT(skb, TCA_STATS, sizeof(sch->stats), &sch->stats);
1838+ HTB_QUNLOCK(sch);
1839+ return skb->len;
c8436fd6
KT		 1840 rtattr_failure:
1841- HTB_QUNLOCK(sch);
1842- skb_trim(skb, skb->tail - skb->data);
1843- return -1;
49520c69
KT		 1844+ HTB_QUNLOCK(sch);
1845+ skb_trim(skb, skb->tail - skb->data);
1846+ return -1;
c8436fd6
KT		 1847 }
1848
1849-static int
1850-htb_dump_class(struct Qdisc *sch, unsigned long arg,
49520c69 1851+static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
c8436fd6
KT		 1852 struct sk_buff *skb, struct tcmsg *tcm)
1853 {
1854- struct htb_sched *q = (struct htb_sched*)sch->data;
1855- struct htb_class *cl = (struct htb_class*)arg;
1856- unsigned char *b = skb->tail;
1857- struct rtattr *rta;
1858- struct tc_htb_opt opt;
1859-
1860- HTB_DBG(0,1,"htb_dump_class handle=%X clid=%X\n",sch->handle,cl->classid);
1861-
1862- HTB_QLOCK(sch);
1863- tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
1864- tcm->tcm_handle = cl->classid;
1865- if (cl->q) {
1866- tcm->tcm_info = cl->q->handle;
1867- cl->stats.qlen = cl->q->q.qlen;
1868- }
49520c69
KT		 1869+#ifdef HTB_DEBUG
1870+ struct htb_sched *q = (struct htb_sched*)sch->data;
1871+#endif
1872+ struct htb_class *cl = (struct htb_class*)arg;
1873+ unsigned char *b = skb->tail;
1874+ struct rtattr *rta;
1875+ struct tc_htb_opt opt;
1876+
1877+ HTB_DBG(0,1,"htb_dump_class handle=%X clid=%X\n",sch->handle,cl->classid);
1878+
1879+ HTB_QLOCK(sch);
1880+ tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
1881+ tcm->tcm_handle = cl->classid;
1882+ if (!cl->level && cl->un.leaf.q) {
1883+ tcm->tcm_info = cl->un.leaf.q->handle;
1884+ cl->stats.qlen = cl->un.leaf.q->q.qlen;
1885+ }
1886+
1887+ rta = (struct rtattr*)b;
1888+ RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
c8436fd6
KT		 1889
1890- rta = (struct rtattr*)b;
1891- RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
49520c69 1892+ memset (&opt,0,sizeof(opt));
c8436fd6
KT		 1893
1894- memset (&opt,0,sizeof(opt));
49520c69
KT		 1895+ opt.rate = cl->rate->rate; opt.buffer = cl->buffer;
1896+ opt.ceil = cl->ceil->rate; opt.cbuffer = cl->cbuffer;
1897+ opt.quantum = cl->un.leaf.quantum; opt.prio = cl->un.leaf.prio;
1898+ opt.level = cl->level;
1899+ RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
1900+ rta->rta_len = skb->tail - b;
1901+
1902+#ifdef HTB_RATECM
1903+ cl->stats.bps = cl->rate_bytes/(HTB_EWMAC*HTB_HSIZE);
1904+ cl->stats.pps = cl->rate_packets/(HTB_EWMAC*HTB_HSIZE);
1905+#endif
c8436fd6
KT		 1906
1907- opt.rate = cl->rate->rate; opt.buffer = cl->buffer;
1908- opt.ceil = cl->ceil->rate; opt.cbuffer = cl->cbuffer;
1909- opt.quantum = cl->quantum; opt.prio = cl->prio;
1910- opt.level = cl->level; opt.injectd = cl->injectd;
1911- RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
1912- rta->rta_len = skb->tail - b;
1913-
1914- cl->stats.bps = cl->rate_bytes/(HTB_EWMAC*HTB_HSIZE);
1915- cl->stats.pps = cl->rate_packets/(HTB_EWMAC*HTB_HSIZE);
1916-
1917- cl->xstats.tokens = cl->tokens;
1918- cl->xstats.ctokens = cl->ctokens;
1919- RTA_PUT(skb, TCA_STATS, sizeof(cl->stats), &cl->stats);
1920- RTA_PUT(skb, TCA_XSTATS, sizeof(cl->xstats), &cl->xstats);
1921- HTB_QUNLOCK(sch);
1922- return skb->len;
49520c69
KT		 1923+ cl->xstats.tokens = cl->tokens;
1924+ cl->xstats.ctokens = cl->ctokens;
1925+ RTA_PUT(skb, TCA_STATS, sizeof(cl->stats), &cl->stats);
1926+ RTA_PUT(skb, TCA_XSTATS, sizeof(cl->xstats), &cl->xstats);
1927+ HTB_QUNLOCK(sch);
1928+ return skb->len;
c8436fd6
KT		 1929 rtattr_failure:
1930- HTB_QUNLOCK(sch);
1931- skb_trim(skb, b - skb->data);
1932- return -1;
49520c69
KT		 1933+ HTB_QUNLOCK(sch);
1934+ skb_trim(skb, b - skb->data);
1935+ return -1;
c8436fd6
KT		 1936 }
1937-#endif
1938
1939 static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1940 struct Qdisc **old)
1941 {
1942- struct htb_class *cl = (struct htb_class*)arg;
49520c69 1943+ struct htb_class *cl = (struct htb_class*)arg;
c8436fd6
KT		 1944
1945- if (cl && !cl->level) {
1946- if (new == NULL) {
1947- if ((new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)) == NULL)
1948- return -ENOBUFS;
1949- }
1950- if ((*old = xchg(&cl->q, new)) != NULL) /* xchg is atomical :-) */
1951- qdisc_reset(*old);
1952- return 0;
1953- }
1954- return -ENOENT;
49520c69
KT		 1955+ if (cl && !cl->level) {
1956+ if (new == NULL && (new = qdisc_create_dflt(sch->dev,
1957+ &pfifo_qdisc_ops)) == NULL)
1958+ return -ENOBUFS;
1959+ sch_tree_lock(sch);
1960+ if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
1961+ /* TODO: is it correct ? Why CBQ doesn't do it ? */
1962+ sch->q.qlen -= (*old)->q.qlen;
1963+ qdisc_reset(*old);
1964+ }
1965+ sch_tree_unlock(sch);
1966+ return 0;
1967+ }
1968+ return -ENOENT;
c8436fd6
KT		 1969 }
1970
1971-static struct Qdisc *
1972-htb_leaf(struct Qdisc *sch, unsigned long arg)
49520c69 1973+static struct Qdisc * htb_leaf(struct Qdisc *sch, unsigned long arg)
c8436fd6
KT		 1974 {
1975- struct htb_class *cl = (struct htb_class*)arg;
1976- return cl ? cl->q : NULL;
49520c69
KT		 1977+ struct htb_class *cl = (struct htb_class*)arg;
1978+ return (cl && !cl->level) ? cl->un.leaf.q : NULL;
c8436fd6
KT		 1979 }
1980
1981 static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1982 {
1983- struct htb_sched *q = (struct htb_sched *)sch->data;
1984- struct htb_class *cl = htb_find(classid,sch);
1985- HTB_DBG(0,1,"htb_get clid=%X q=%p cl=%p ref=%d\n",classid,q,cl,cl?cl->refcnt:0);
1986- if (cl) cl->refcnt++;
1987- return (unsigned long)cl;
49520c69
KT		 1988+#ifdef HTB_DEBUG
1989+ struct htb_sched *q = (struct htb_sched *)sch->data;
1990+#endif
1991+ struct htb_class *cl = htb_find(classid,sch);
1992+ HTB_DBG(0,1,"htb_get clid=%X q=%p cl=%p ref=%d\n",classid,q,cl,cl?cl->refcnt:0);
1993+ if (cl)
1994+ cl->refcnt++;
1995+ return (unsigned long)cl;
c8436fd6
KT		 1996 }
1997
1998 static void htb_destroy_filters(struct tcf_proto **fl)
1999 {
2000- struct tcf_proto *tp;
49520c69 2001+ struct tcf_proto *tp;
c8436fd6
KT		 2002
2003- while ((tp = *fl) != NULL) {
2004- *fl = tp->next;
2005- tp->ops->destroy(tp);
2006- }
49520c69
KT		 2007+ while ((tp = *fl) != NULL) {
2008+ *fl = tp->next;
2009+ tp->ops->destroy(tp);
2010+ }
c8436fd6
KT		 2011 }
2012
2013 static void htb_destroy_class(struct Qdisc* sch,struct htb_class *cl)
2014 {
2015- struct htb_sched *q = (struct htb_sched *)sch->data;
2016- HTB_DBG(0,1,"htb_destrycls clid=%X q=%p ref=%d\n", cl?cl->classid:0,cl->q,cl?cl->refcnt:0);
2017- if (cl->q) qdisc_destroy(cl->q);
2018- qdisc_put_rtab(cl->rate);
2019- qdisc_put_rtab(cl->ceil);
49520c69
KT		 2020+ struct htb_sched *q = (struct htb_sched *)sch->data;
2021+ HTB_DBG(0,1,"htb_destrycls clid=%X ref=%d\n", cl?cl->classid:0,cl?cl->refcnt:0);
2022+ if (!cl->level) {
2023+ BUG_TRAP(cl->un.leaf.q);
2024+ sch->q.qlen -= cl->un.leaf.q->q.qlen;
2025+ qdisc_destroy(cl->un.leaf.q);
2026+ }
2027+ qdisc_put_rtab(cl->rate);
2028+ qdisc_put_rtab(cl->ceil);
2029+
c8436fd6
KT		 2030 #ifdef CONFIG_NET_ESTIMATOR
2031- qdisc_kill_estimator(&cl->stats);
49520c69 2032+ qdisc_kill_estimator(&cl->stats);
c8436fd6
KT		 2033 #endif
2034- htb_destroy_filters (&cl->filter_list);
2035- /* remove children */
2036- while (cl->children) htb_destroy_class (sch,cl->children);
2037-
2038- /* remove class from all lists it is on */
2039- q->last_tx = NULL;
2040- if (cl->hlist.prev)
2041- HTB_DELETE(hlist,cl,q->hash[htb_hash(cl->classid)]);
2042- if (cl->active.prev)
2043- htb_deactivate (q,cl,0);
2044- if (cl->parent)
2045- HTB_DELETE(sibling,cl,cl->parent->children);
2046- else
2047- HTB_DELETE(sibling,cl,q->root);
2048-
2049- kfree(cl);
49520c69
KT		 2050+ htb_destroy_filters (&cl->filter_list);
2051+
2052+ while (!list_empty(&cl->children))
2053+ htb_destroy_class (sch,list_entry(cl->children.next,
2054+ struct htb_class,sibling));
2055+
2056+ /* note: this delete may happen twice (see htb_delete) */
2057+ list_del(&cl->hlist);
2058+ list_del(&cl->sibling);
2059+
2060+ if (cl->prio_activity)
2061+ htb_deactivate (q,cl);
2062+
2063+ if (cl->cmode != HTB_CAN_SEND)
2064+ htb_safe_rb_erase(&cl->pq_node,q->wait_pq+cl->level);
2065+
2066+ kfree(cl);
c8436fd6
KT		 2067 }
2068
2069 /* always caled under BH & queue lock */
2070 static void htb_destroy(struct Qdisc* sch)
2071 {
2072- struct htb_sched *q = (struct htb_sched *)sch->data;
2073- HTB_DBG(0,1,"htb_destroy q=%p\n",q);
49520c69
KT		 2074+ struct htb_sched *q = (struct htb_sched *)sch->data;
2075+ HTB_DBG(0,1,"htb_destroy q=%p\n",q);
c8436fd6
KT		 2076
2077- del_timer_sync (&q->timer);
2078- del_timer_sync (&q->rttim);
2079- while (q->root) htb_destroy_class(sch,q->root);
2080- htb_destroy_filters(&q->filter_list);
2081- __skb_queue_purge(&q->direct_queue);
2082- MOD_DEC_USE_COUNT;
49520c69
KT		 2083+ del_timer_sync (&q->timer);
2084+#ifdef HTB_RATECM
2085+ del_timer_sync (&q->rttim);
2086+#endif
2087+ while (!list_empty(&q->root))
2088+ htb_destroy_class (sch,list_entry(q->root.next,
2089+ struct htb_class,sibling));
2090+
2091+ htb_destroy_filters(&q->filter_list);
2092+ __skb_queue_purge(&q->direct_queue);
2093+ MOD_DEC_USE_COUNT;
c8436fd6
KT		 2094 }
2095
2096-static void htb_put(struct Qdisc *sch, unsigned long arg)
49520c69 2097+static int htb_delete(struct Qdisc *sch, unsigned long arg)
c8436fd6
KT		 2098 {
2099- struct htb_sched *q = (struct htb_sched *)sch->data;
2100- struct htb_class *cl = (struct htb_class*)arg;
2101- HTB_DBG(0,1,"htb_put q=%p cl=%X ref=%d\n",q,cl?cl->classid:0,cl?cl->refcnt:0);
49520c69
KT		 2102+ struct htb_sched *q = (struct htb_sched *)sch->data;
2103+ struct htb_class *cl = (struct htb_class*)arg;
2104+ HTB_DBG(0,1,"htb_delete q=%p cl=%X ref=%d\n",q,cl?cl->classid:0,cl?cl->refcnt:0);
2105+
2106+ // TODO: why don't allow to delete subtree ? references ? does
2107+ // tc subsys quarantee us that in htb_destroy it holds no class
2108+ // refs so that we can remove children safely there ?
2109+ if (!list_empty(&cl->children) || cl->filter_cnt)
2110+ return -EBUSY;
2111+
2112+ sch_tree_lock(sch);
2113+
2114+ /* delete from hash and active; remainder in destroy_class */
2115+ list_del_init(&cl->hlist);
2116+ if (cl->prio_activity)
2117+ htb_deactivate (q,cl);
2118+
2119+ if (--cl->refcnt == 0)
2120+ htb_destroy_class(sch,cl);
c8436fd6
KT		 2121
2122- if (--cl->refcnt == 0)
2123- htb_destroy_class(sch,cl);
49520c69
KT		 2124+ sch_tree_unlock(sch);
2125+ return 0;
c8436fd6
KT		 2126 }
2127
2128-static int
2129-htb_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct rtattr **tca,
2130- unsigned long *arg)
49520c69 2131+static void htb_put(struct Qdisc *sch, unsigned long arg)
c8436fd6
KT		 2132 {
2133- int err = -EINVAL,h;
2134- struct htb_sched *q = (struct htb_sched *)sch->data;
2135- struct htb_class *cl = (struct htb_class*)*arg,*parent;
2136- struct rtattr *opt = tca[TCA_OPTIONS-1];
2137- struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
2138- struct rtattr *tb[TCA_HTB_RTAB];
2139- struct tc_htb_opt *hopt;
2140-
2141- if (parentid == TC_H_ROOT) parent = NULL;
2142- else parent = htb_find (parentid,sch);
2143-
2144- /* extract all subattrs from opt attr */
2145- if (!opt ||
2146- rtattr_parse(tb, TCA_HTB_RTAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) ||
2147- tb[TCA_HTB_PARMS-1] == NULL ||
2148- RTA_PAYLOAD(tb[TCA_HTB_PARMS-1]) < sizeof(*hopt))
2149- goto failure;
2150-
2151- hopt = RTA_DATA(tb[TCA_HTB_PARMS-1]);
2152- HTB_DBG(0,1,"htb_chg cl=%p, clid=%X, opt/prio=%d, rate=%u, buff=%d, quant=%d\n", cl,cl?cl->classid:0,(int)hopt->prio,hopt->rate.rate,hopt->buffer,hopt->quantum);
2153- rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB-1]);
2154- ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB-1]);
2155- if (!rtab || !ctab) goto failure;
2156-
2157- if (!cl) { /* new class */
2158- /* check maximal depth */
2159- if (parent && parent->parent && parent->parent->level < 2) {
2160- printk(KERN_ERR "htb: tree is too deep\n");
2161- goto failure;
2162- }
2163- err = -ENOBUFS;
2164- cl = kmalloc(sizeof(*cl), GFP_KERNEL);
2165- if (cl == NULL) goto failure;
2166- memset(cl, 0, sizeof(*cl));
2167- cl->refcnt = 1; cl->level = 0; /* assume leaf */
2168-
2169- if (parent && !parent->level) {
2170- /* turn parent into inner node */
2171- qdisc_destroy (parent->q); parent->q = &noop_qdisc;
2172- parent->level = (parent->parent ?
2173- parent->parent->level : TC_HTB_MAXDEPTH) - 1;
2174- }
2175- /* leaf (we) needs elementary qdisc */
2176- if (!(cl->q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)))
2177- cl->q = &noop_qdisc;
2178-
2179- cl->classid = classid; cl->parent = parent;
2180- cl->tokens = hopt->buffer;
2181- cl->ctokens = hopt->cbuffer;
2182- cl->mbuffer = 60000000; /* 1min */
2183- PSCHED_GET_TIME(cl->t_c);
49520c69
KT		 2184+#ifdef HTB_DEBUG
2185+ struct htb_sched *q = (struct htb_sched *)sch->data;
2186+#endif
2187+ struct htb_class *cl = (struct htb_class*)arg;
2188+ HTB_DBG(0,1,"htb_put q=%p cl=%X ref=%d\n",q,cl?cl->classid:0,cl?cl->refcnt:0);
c8436fd6
KT		 2189
2190- /* attach to the hash list and parent's family */
2191- sch_tree_lock(sch);
2192- h = htb_hash(classid);
2193- if (!cl->hlist.prev)
2194- HTB_INSERTB(hlist,q->hash[h],cl);
2195- if (parent)
2196- HTB_INSERTB(sibling,parent->children,cl);
2197- else HTB_INSERTB(sibling,q->root,cl);
2198-
2199- } else sch_tree_lock(sch);
2200-
2201- q->last_tx = NULL;
2202- cl->quantum = rtab->rate.rate / q->rate2quantum;
2203- cl->injectd = hopt->injectd;
2204- if (cl->quantum < 100) cl->quantum = 100;
2205- if (cl->quantum > 60000) cl->quantum = 60000;
2206- if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO)
2207- cl->prio = TC_HTB_NUMPRIO - 1;
2208-
2209- cl->buffer = hopt->buffer;
2210- cl->cbuffer = hopt->cbuffer;
2211- if (cl->rate) qdisc_put_rtab(cl->rate); cl->rate = rtab;
2212- if (cl->ceil) qdisc_put_rtab(cl->ceil); cl->ceil = ctab;
2213- sch_tree_unlock(sch);
49520c69
KT		 2214+ if (--cl->refcnt == 0)
2215+ htb_destroy_class(sch,cl);
2216+}
c8436fd6
KT		 2217
2218- *arg = (unsigned long)cl;
2219- return 0;
49520c69
KT		 2220+static int htb_change_class(struct Qdisc *sch, u32 classid,
2221+ u32 parentid, struct rtattr **tca, unsigned long *arg)
2222+{
2223+ int err = -EINVAL;
2224+ struct htb_sched *q = (struct htb_sched *)sch->data;
2225+ struct htb_class *cl = (struct htb_class*)*arg,*parent;
2226+ struct rtattr *opt = tca[TCA_OPTIONS-1];
2227+ struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
2228+ struct rtattr *tb[TCA_HTB_RTAB];
2229+ struct tc_htb_opt *hopt;
2230+
2231+ /* extract all subattrs from opt attr */
2232+ if (!opt || rtattr_parse(tb, TCA_HTB_RTAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) ||
2233+ tb[TCA_HTB_PARMS-1] == NULL ||
2234+ RTA_PAYLOAD(tb[TCA_HTB_PARMS-1]) < sizeof(*hopt))
2235+ goto failure;
2236+
2237+ parent = parentid == TC_H_ROOT ? NULL : htb_find (parentid,sch);
2238+
2239+ hopt = RTA_DATA(tb[TCA_HTB_PARMS-1]);
2240+ HTB_DBG(0,1,"htb_chg cl=%p, clid=%X, opt/prio=%d, rate=%u, buff=%d, quant=%d\n", cl,cl?cl->classid:0,(int)hopt->prio,hopt->rate.rate,hopt->buffer,hopt->quantum);
2241+ rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB-1]);
2242+ ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB-1]);
2243+ if (!rtab || !ctab) goto failure;
2244+
2245+ if (!cl) { /* new class */
2246+ /* check for valid classid */
2247+ if (!classid || TC_H_MAJ(classid^sch->handle) || htb_find(classid,sch))
2248+ goto failure;
2249+
2250+ /* check maximal depth */
2251+ if (parent && parent->parent && parent->parent->level < 2) {
2252+ printk(KERN_ERR "htb: tree is too deep\n");
2253+ goto failure;
2254+ }
2255+ err = -ENOBUFS;
2256+ if ((cl = kmalloc(sizeof(*cl), GFP_KERNEL)) == NULL)
2257+ goto failure;
2258+
2259+ memset(cl, 0, sizeof(*cl));
2260+ cl->refcnt = 1;
2261+ INIT_LIST_HEAD(&cl->sibling);
2262+ INIT_LIST_HEAD(&cl->hlist);
2263+ INIT_LIST_HEAD(&cl->children);
2264+ INIT_LIST_HEAD(&cl->un.leaf.drop_list);
2265+#ifdef HTB_DEBUG
2266+ cl->magic = HTB_CMAGIC;
2267+#endif
c8436fd6
KT		 2268
2269-failure:
2270- if (rtab) qdisc_put_rtab(rtab);
2271- if (ctab) qdisc_put_rtab(ctab);
2272- return err;
2273-}
49520c69
KT		 2274+ sch_tree_lock(sch);
2275+ if (parent && !parent->level) {
2276+ /* turn parent into inner node */
2277+ sch->q.qlen -= parent->un.leaf.q->q.qlen;
2278+ qdisc_destroy (parent->un.leaf.q);
2279+ if (parent->prio_activity)
2280+ htb_deactivate (q,parent);
2281+
2282+ /* remove from evt list because of level change */
2283+ if (parent->cmode != HTB_CAN_SEND) {
2284+ htb_safe_rb_erase(&parent->pq_node,q->wait_pq /*+0*/);
2285+ parent->cmode = HTB_CAN_SEND;
2286+ }
2287+ parent->level = (parent->parent ? parent->parent->level
2288+ : TC_HTB_MAXDEPTH) - 1;
2289+ memset (&parent->un.inner,0,sizeof(parent->un.inner));
2290+ }
2291+ /* leaf (we) needs elementary qdisc */
2292+ if (!(cl->un.leaf.q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops)))
2293+ cl->un.leaf.q = &noop_qdisc;
2294+
2295+ cl->classid = classid; cl->parent = parent;
2296+
2297+ /* set class to be in HTB_CAN_SEND state */
2298+ cl->tokens = hopt->buffer;
2299+ cl->ctokens = hopt->cbuffer;
2300+ cl->mbuffer = 60000000; /* 1min */
2301+ PSCHED_GET_TIME(cl->t_c);
2302+ cl->cmode = HTB_CAN_SEND;
2303+
2304+ /* attach to the hash list and parent's family */
2305+ list_add_tail(&cl->hlist, q->hash+htb_hash(classid));
2306+ list_add_tail(&cl->sibling, parent ? &parent->children : &q->root);
2307+#ifdef HTB_DEBUG
2308+ {
2309+ int i;
2310+ for (i = 0; i < TC_HTB_NUMPRIO; i++) cl->node[i].rb_color = -1;
2311+ cl->pq_node.rb_color = -1;
2312+ }
2313+#endif
2314+ } else sch_tree_lock(sch);
c8436fd6
KT		 2315
2316-static int htb_delete(struct Qdisc *sch, unsigned long arg)
2317-{
2318- struct htb_sched *q = (struct htb_sched *)sch->data;
2319- struct htb_class *cl = (struct htb_class*)arg;
2320- HTB_DBG(0,1,"htb_delete q=%p cl=%X ref=%d\n",q,cl?cl->classid:0,cl?cl->refcnt:0);
49520c69
KT		 2321+ /* it used to be a nasty bug here, we have to check that node
2322+ is really leaf before changing cl->un.leaf ! */
2323+ if (!cl->level) {
2324+ cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum;
2325+ if (!hopt->quantum && cl->un.leaf.quantum < 1000) {
2326+ printk(KERN_WARNING "HTB: quantum of class %X is small. Consider r2q change.", cl->classid);
2327+ cl->un.leaf.quantum = 1000;
2328+ }
2329+ if (!hopt->quantum && cl->un.leaf.quantum > 200000) {
2330+ printk(KERN_WARNING "HTB: quantum of class %X is big. Consider r2q change.", cl->classid);
2331+ cl->un.leaf.quantum = 200000;
2332+ }
2333+ if (hopt->quantum)
2334+ cl->un.leaf.quantum = hopt->quantum;
2335+ if ((cl->un.leaf.prio = hopt->prio) >= TC_HTB_NUMPRIO)
2336+ cl->un.leaf.prio = TC_HTB_NUMPRIO - 1;
2337+ }
c8436fd6
KT		 2338
2339- if (cl->children || cl->filter_cnt) return -EBUSY;
2340- sch_tree_lock(sch);
2341- /* delete from hash and active; remainder in destroy_class */
2342- if (cl->hlist.prev)
2343- HTB_DELETE(hlist,cl,q->hash[htb_hash(cl->classid)]);
2344- if (cl->active.prev)
2345- htb_deactivate (q,cl,0);
2346- q->last_tx = NULL;
49520c69
KT		 2347+ cl->buffer = hopt->buffer;
2348+ cl->cbuffer = hopt->cbuffer;
2349+ if (cl->rate) qdisc_put_rtab(cl->rate); cl->rate = rtab;
2350+ if (cl->ceil) qdisc_put_rtab(cl->ceil); cl->ceil = ctab;
2351+ sch_tree_unlock(sch);
c8436fd6
KT		 2352
2353- if (--cl->refcnt == 0)
2354- htb_destroy_class(sch,cl);
49520c69
KT		 2355+ *arg = (unsigned long)cl;
2356+ return 0;
c8436fd6
KT		 2357
2358- sch_tree_unlock(sch);
2359- return 0;
49520c69
KT		 2360+failure:
2361+ if (rtab) qdisc_put_rtab(rtab);
2362+ if (ctab) qdisc_put_rtab(ctab);
2363+ return err;
c8436fd6
KT		 2364 }
2365
2366 static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
2367 {
2368- struct htb_sched *q = (struct htb_sched *)sch->data;
2369- struct htb_class *cl = (struct htb_class *)arg;
2370- struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
2371- HTB_DBG(0,2,"htb_tcf q=%p clid=%X fref=%d fl=%p\n",q,cl?cl->classid:0,cl?cl->filter_cnt:q->filter_cnt,*fl);
2372- return fl;
49520c69
KT		 2373+ struct htb_sched *q = (struct htb_sched *)sch->data;
2374+ struct htb_class *cl = (struct htb_class *)arg;
2375+ struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
2376+ HTB_DBG(0,2,"htb_tcf q=%p clid=%X fref=%d fl=%p\n",q,cl?cl->classid:0,cl?cl->filter_cnt:q->filter_cnt,*fl);
2377+ return fl;
c8436fd6
KT		 2378 }
2379
2380 static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
2381 u32 classid)
2382 {
2383- struct htb_sched *q = (struct htb_sched *)sch->data;
2384- struct htb_class *cl = htb_find (classid,sch);
2385- HTB_DBG(0,2,"htb_bind q=%p clid=%X cl=%p fref=%d\n",q,classid,cl,cl?cl->filter_cnt:q->filter_cnt);
2386- if (cl && !cl->level) return 0;
2387- if (cl) cl->filter_cnt++; else q->filter_cnt++;
2388- return (unsigned long)cl;
49520c69
KT		 2389+ struct htb_sched *q = (struct htb_sched *)sch->data;
2390+ struct htb_class *cl = htb_find (classid,sch);
2391+ HTB_DBG(0,2,"htb_bind q=%p clid=%X cl=%p fref=%d\n",q,classid,cl,cl?cl->filter_cnt:q->filter_cnt);
2392+ /*if (cl && !cl->level) return 0;
2393+ The line above used to be there to prevent attaching filters to
2394+ leaves. But at least tc_index filter uses this just to get class
2395+ for other reasons so that we have to allow for it.
2396+ ----
2397+ 19.6.2002 As Werner explained it is ok - bind filter is just
2398+ another way to "lock" the class - unlike "get" this lock can
2399+ be broken by class during destroy IIUC.
2400+ */
2401+ if (cl)
2402+ cl->filter_cnt++;
2403+ else
2404+ q->filter_cnt++;
2405+ return (unsigned long)cl;
c8436fd6
KT		 2406 }
2407
2408 static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
2409 {
2410- struct htb_sched *q = (struct htb_sched *)sch->data;
2411- struct htb_class *cl = (struct htb_class *)arg;
2412- HTB_DBG(0,2,"htb_unbind q=%p cl=%p fref=%d\n",q,cl,cl?cl->filter_cnt:q->filter_cnt);
2413- if (cl) cl->filter_cnt--; else q->filter_cnt--;
49520c69
KT		 2414+ struct htb_sched *q = (struct htb_sched *)sch->data;
2415+ struct htb_class *cl = (struct htb_class *)arg;
2416+ HTB_DBG(0,2,"htb_unbind q=%p cl=%p fref=%d\n",q,cl,cl?cl->filter_cnt:q->filter_cnt);
2417+ if (cl)
2418+ cl->filter_cnt--;
2419+ else
2420+ q->filter_cnt--;
c8436fd6
KT		 2421 }
2422
2423 static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2424 {
2425- struct htb_sched *q = (struct htb_sched *)sch->data;
2426- int i;
49520c69
KT		 2427+ struct htb_sched *q = (struct htb_sched *)sch->data;
2428+ int i;
c8436fd6
KT		 2429
2430- if (arg->stop)
2431- return;
2432-
2433- for (i = 0; i < HTB_HSIZE; i++) {
2434- struct htb_class *cl = q->hash[i];
2435- if (cl) do {
2436- if (arg->count < arg->skip) {
2437- arg->count++;
2438- continue;
2439- }
2440- if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2441- arg->stop = 1;
49520c69 2442+ if (arg->stop)
c8436fd6
KT		 2443 return;
2444- }
2445- arg->count++;
2446
2447- } while ((cl = cl->hlist.next) != q->hash[i]);
2448- }
49520c69
KT		 2449+ for (i = 0; i < HTB_HSIZE; i++) {
2450+ struct list_head *p;
2451+ list_for_each (p,q->hash+i) {
2452+ struct htb_class *cl = list_entry(p,struct htb_class,hlist);
2453+ if (arg->count < arg->skip) {
2454+ arg->count++;
2455+ continue;
2456+ }
2457+ if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2458+ arg->stop = 1;
2459+ return;
2460+ }
2461+ arg->count++;
2462+ }
2463+ }
c8436fd6
KT		 2464 }
2465
2466 static struct Qdisc_class_ops htb_class_ops =
2467@@ -1174,9 +1622,7 @@
2468 htb_bind_filter,
2469 htb_unbind_filter,
2470
2471-#ifdef CONFIG_RTNETLINK
2472 htb_dump_class,
2473-#endif
2474 };
2475
2476 struct Qdisc_ops htb_qdisc_ops =
2477@@ -1196,9 +1642,7 @@
2478 htb_destroy,
2479 NULL /* htb_change */,
2480
2481-#ifdef CONFIG_RTNETLINK
2482 htb_dump,
2483-#endif
2484 };
2485
2486 #ifdef MODULE
The Linux kernel (the core of the Linux operating system)
This page took 0.39984 seconds and 4 git commands to generate.