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