Diff markup
1 /* 1 /*
2 * net/sched/sch_cbq.c Class-Based Queueing d 2 * net/sched/sch_cbq.c Class-Based Queueing discipline.
3 * 3 *
4 * This program is free software; 4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of t 5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Softw 6 * as published by the Free Software Foundation; either version
7 * 2 of the License, or (at your 7 * 2 of the License, or (at your option) any later version.
8 * 8 *
9 * Authors: Alexey Kuznetsov, <kuznet@ms2. 9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
10 * 10 *
11 */ 11 */
12 12
13 #include <linux/module.h> 13 #include <linux/module.h>
14 #include <linux/types.h> 14 #include <linux/types.h>
15 #include <linux/kernel.h> 15 #include <linux/kernel.h>
16 #include <linux/string.h> 16 #include <linux/string.h>
17 #include <linux/errno.h> 17 #include <linux/errno.h>
18 #include <linux/skbuff.h> 18 #include <linux/skbuff.h>
19 #include <net/netlink.h> 19 #include <net/netlink.h>
20 #include <net/pkt_sched.h> 20 #include <net/pkt_sched.h>
21 21
22 22
23 /* Class-Based Queueing (CBQ) algorithm. 23 /* Class-Based Queueing (CBQ) algorithm.
24 ====================================== 24 =======================================
25 25
26 Sources: [1] Sally Floyd and Van Jacob 26 Sources: [1] Sally Floyd and Van Jacobson, "Link-sharing and Resource
27 Management Models for Packet 27 Management Models for Packet Networks",
28 IEEE/ACM Transactions on Netw 28 IEEE/ACM Transactions on Networking, Vol.3, No.4, 1995
29 29
30 [2] Sally Floyd, "Notes on CB 30 [2] Sally Floyd, "Notes on CBQ and Guaranteed Service", 1995
31 31
32 [3] Sally Floyd, "Notes on Cl 32 [3] Sally Floyd, "Notes on Class-Based Queueing: Setting
33 Parameters", 1996 33 Parameters", 1996
34 34
35 [4] Sally Floyd and Michael S 35 [4] Sally Floyd and Michael Speer, "Experimental Results
36 for Class-Based Queueing", 19 36 for Class-Based Queueing", 1998, not published.
37 37
38 -------------------------------------- 38 -----------------------------------------------------------------------
39 39
40 Algorithm skeleton was taken from NS s 40 Algorithm skeleton was taken from NS simulator cbq.cc.
41 If someone wants to check this code ag 41 If someone wants to check this code against the LBL version,
42 he should take into account that ONLY 42 he should take into account that ONLY the skeleton was borrowed,
43 the implementation is different. Parti 43 the implementation is different. Particularly:
44 44
45 --- The WRR algorithm is different. Ou 45 --- The WRR algorithm is different. Our version looks more
46 reasonable (I hope) and works when qua 46 reasonable (I hope) and works when quanta are allowed to be
47 less than MTU, which is always the cas 47 less than MTU, which is always the case when real time classes
48 have small rates. Note, that the state 48 have small rates. Note, that the statement of [3] is
49 incomplete, delay may actually be esti 49 incomplete, delay may actually be estimated even if class
50 per-round allotment is less than MTU. 50 per-round allotment is less than MTU. Namely, if per-round
51 allotment is W*r_i, and r_1+...+r_k = 51 allotment is W*r_i, and r_1+...+r_k = r < 1
52 52
53 delay_i <= ([MTU/(W*r_i)]*W*r + W*r + 53 delay_i <= ([MTU/(W*r_i)]*W*r + W*r + k*MTU)/B
54 54
55 In the worst case we have IntServ esti 55 In the worst case we have IntServ estimate with D = W*r+k*MTU
56 and C = MTU*r. The proof (if correct a 56 and C = MTU*r. The proof (if correct at all) is trivial.
57 57
58 58
59 --- It seems that cbq-2.0 is not very 59 --- It seems that cbq-2.0 is not very accurate. At least, I cannot
60 interpret some places, which look like 60 interpret some places, which look like wrong translations
61 from NS. Anyone is advised to find the 61 from NS. Anyone is advised to find these differences
62 and explain to me, why I am wrong 8). 62 and explain to me, why I am wrong 8).
63 63
64 --- Linux has no EOI event, so that we 64 --- Linux has no EOI event, so that we cannot estimate true class
65 idle time. Workaround is to consider t 65 idle time. Workaround is to consider the next dequeue event
66 as sign that previous packet is finish 66 as sign that previous packet is finished. This is wrong because of
67 internal device queueing, but on a per 67 internal device queueing, but on a permanently loaded link it is true.
68 Moreover, combined with clock integrat 68 Moreover, combined with clock integrator, this scheme looks
69 very close to an ideal solution. */ 69 very close to an ideal solution. */
70 70
71 struct cbq_sched_data; 71 struct cbq_sched_data;
72 72
73 73
74 struct cbq_class 74 struct cbq_class
75 { 75 {
76 struct cbq_class *next; !! 76 struct Qdisc_class_common common;
77 struct cbq_class *next_alive; 77 struct cbq_class *next_alive; /* next class with backlog in this priority band */
78 78
79 /* Parameters */ 79 /* Parameters */
80 u32 classid; <<
81 unsigned char priority; 80 unsigned char priority; /* class priority */
82 unsigned char priority2; 81 unsigned char priority2; /* priority to be used after overlimit */
83 unsigned char ewma_log; 82 unsigned char ewma_log; /* time constant for idle time calculation */
84 unsigned char ovl_strategy; 83 unsigned char ovl_strategy;
85 #ifdef CONFIG_NET_CLS_ACT 84 #ifdef CONFIG_NET_CLS_ACT
86 unsigned char police; 85 unsigned char police;
87 #endif 86 #endif
88 87
89 u32 defmap; 88 u32 defmap;
90 89
91 /* Link-sharing scheduler parameters * 90 /* Link-sharing scheduler parameters */
92 long maxidle; 91 long maxidle; /* Class parameters: see below. */
93 long offtime; 92 long offtime;
94 long minidle; 93 long minidle;
95 u32 avpkt; 94 u32 avpkt;
96 struct qdisc_rate_table *R_tab; 95 struct qdisc_rate_table *R_tab;
97 96
98 /* Overlimit strategy parameters */ 97 /* Overlimit strategy parameters */
99 void (*overlimit)(s 98 void (*overlimit)(struct cbq_class *cl);
100 psched_tdiff_t penalty; 99 psched_tdiff_t penalty;
101 100
102 /* General scheduler (WRR) parameters 101 /* General scheduler (WRR) parameters */
103 long allot; 102 long allot;
104 long quantum; 103 long quantum; /* Allotment per WRR round */
105 long weight; 104 long weight; /* Relative allotment: see below */
106 105
107 struct Qdisc *qdisc; 106 struct Qdisc *qdisc; /* Ptr to CBQ discipline */
108 struct cbq_class *split; 107 struct cbq_class *split; /* Ptr to split node */
109 struct cbq_class *share; 108 struct cbq_class *share; /* Ptr to LS parent in the class tree */
110 struct cbq_class *tparent; 109 struct cbq_class *tparent; /* Ptr to tree parent in the class tree */
111 struct cbq_class *borrow; 110 struct cbq_class *borrow; /* NULL if class is bandwidth limited;
112 111 parent otherwise */
113 struct cbq_class *sibling; 112 struct cbq_class *sibling; /* Sibling chain */
114 struct cbq_class *children; 113 struct cbq_class *children; /* Pointer to children chain */
115 114
116 struct Qdisc *q; 115 struct Qdisc *q; /* Elementary queueing discipline */
117 116
118 117
119 /* Variables */ 118 /* Variables */
120 unsigned char cpriority; 119 unsigned char cpriority; /* Effective priority */
121 unsigned char delayed; 120 unsigned char delayed;
122 unsigned char level; 121 unsigned char level; /* level of the class in hierarchy:
123 122 0 for leaf classes, and maximal
124 123 level of children + 1 for nodes.
125 124 */
126 125
127 psched_time_t last; 126 psched_time_t last; /* Last end of service */
128 psched_time_t undertime; 127 psched_time_t undertime;
129 long avgidle; 128 long avgidle;
130 long deficit; 129 long deficit; /* Saved deficit for WRR */
131 psched_time_t penalized; 130 psched_time_t penalized;
132 struct gnet_stats_basic bstats; !! 131 struct gnet_stats_basic_packed bstats;
133 struct gnet_stats_queue qstats; 132 struct gnet_stats_queue qstats;
134 struct gnet_stats_rate_est rate_est; 133 struct gnet_stats_rate_est rate_est;
135 struct tc_cbq_xstats xstats; 134 struct tc_cbq_xstats xstats;
136 135
137 struct tcf_proto *filter_list; 136 struct tcf_proto *filter_list;
138 137
139 int refcnt; 138 int refcnt;
140 int filters; 139 int filters;
141 140
142 struct cbq_class *defaults[TC_P 141 struct cbq_class *defaults[TC_PRIO_MAX+1];
143 }; 142 };
144 143
145 struct cbq_sched_data 144 struct cbq_sched_data
146 { 145 {
147 struct cbq_class *classes[16]; !! 146 struct Qdisc_class_hash clhash; /* Hash table of all classes */
148 int nclasses[TC_CB 147 int nclasses[TC_CBQ_MAXPRIO+1];
149 unsigned quanta[TC_CBQ_ 148 unsigned quanta[TC_CBQ_MAXPRIO+1];
150 149
151 struct cbq_class link; 150 struct cbq_class link;
152 151
153 unsigned activemask; 152 unsigned activemask;
154 struct cbq_class *active[TC_CBQ 153 struct cbq_class *active[TC_CBQ_MAXPRIO+1]; /* List of all classes
155 154 with backlog */
156 155
157 #ifdef CONFIG_NET_CLS_ACT 156 #ifdef CONFIG_NET_CLS_ACT
158 struct cbq_class *rx_class; 157 struct cbq_class *rx_class;
159 #endif 158 #endif
160 struct cbq_class *tx_class; 159 struct cbq_class *tx_class;
161 struct cbq_class *tx_borrowed; 160 struct cbq_class *tx_borrowed;
162 int tx_len; 161 int tx_len;
163 psched_time_t now; 162 psched_time_t now; /* Cached timestamp */
164 psched_time_t now_rt; 163 psched_time_t now_rt; /* Cached real time */
165 unsigned pmask; 164 unsigned pmask;
166 165
167 struct hrtimer delay_timer; 166 struct hrtimer delay_timer;
168 struct qdisc_watchdog watchdog; 167 struct qdisc_watchdog watchdog; /* Watchdog timer,
169 168 started when CBQ has
170 169 backlog, but cannot
171 170 transmit just now */
172 psched_tdiff_t wd_expires; 171 psched_tdiff_t wd_expires;
173 int toplevel; 172 int toplevel;
174 u32 hgenerator; 173 u32 hgenerator;
175 }; 174 };
176 175
177 176
178 #define L2T(cl,len) qdisc_l2t((cl)->R_tab, 177 #define L2T(cl,len) qdisc_l2t((cl)->R_tab,len)
179 178
180 <<
181 static __inline__ unsigned cbq_hash(u32 h) <<
182 { <<
183 h ^= h>>8; <<
184 h ^= h>>4; <<
185 return h&0xF; <<
186 } <<
187 <<
188 static __inline__ struct cbq_class * 179 static __inline__ struct cbq_class *
189 cbq_class_lookup(struct cbq_sched_data *q, u32 180 cbq_class_lookup(struct cbq_sched_data *q, u32 classid)
190 { 181 {
191 struct cbq_class *cl; !! 182 struct Qdisc_class_common *clc;
192 183
193 for (cl = q->classes[cbq_hash(classid) !! 184 clc = qdisc_class_find(&q->clhash, classid);
194 if (cl->classid == classid) !! 185 if (clc == NULL)
195 return cl; !! 186 return NULL;
196 return NULL; !! 187 return container_of(clc, struct cbq_class, common);
197 } 188 }
198 189
199 #ifdef CONFIG_NET_CLS_ACT 190 #ifdef CONFIG_NET_CLS_ACT
200 191
201 static struct cbq_class * 192 static struct cbq_class *
202 cbq_reclassify(struct sk_buff *skb, struct cbq 193 cbq_reclassify(struct sk_buff *skb, struct cbq_class *this)
203 { 194 {
204 struct cbq_class *cl, *new; 195 struct cbq_class *cl, *new;
205 196
206 for (cl = this->tparent; cl; cl = cl-> 197 for (cl = this->tparent; cl; cl = cl->tparent)
207 if ((new = cl->defaults[TC_PRI 198 if ((new = cl->defaults[TC_PRIO_BESTEFFORT]) != NULL && new != this)
208 return new; 199 return new;
209 200
210 return NULL; 201 return NULL;
211 } 202 }
212 203
213 #endif 204 #endif
214 205
215 /* Classify packet. The procedure is pretty co 206 /* Classify packet. The procedure is pretty complicated, but
216 it allows us to combine link sharing and pr 207 it allows us to combine link sharing and priority scheduling
217 transparently. 208 transparently.
218 209
219 Namely, you can put link sharing rules (f.e 210 Namely, you can put link sharing rules (f.e. route based) at root of CBQ,
220 so that it resolves to split nodes. Then pa 211 so that it resolves to split nodes. Then packets are classified
221 by logical priority, or a more specific cla 212 by logical priority, or a more specific classifier may be attached
222 to the split node. 213 to the split node.
223 */ 214 */
224 215
225 static struct cbq_class * 216 static struct cbq_class *
226 cbq_classify(struct sk_buff *skb, struct Qdisc 217 cbq_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr)
227 { 218 {
228 struct cbq_sched_data *q = qdisc_priv( 219 struct cbq_sched_data *q = qdisc_priv(sch);
229 struct cbq_class *head = &q->link; 220 struct cbq_class *head = &q->link;
230 struct cbq_class **defmap; 221 struct cbq_class **defmap;
231 struct cbq_class *cl = NULL; 222 struct cbq_class *cl = NULL;
232 u32 prio = skb->priority; 223 u32 prio = skb->priority;
233 struct tcf_result res; 224 struct tcf_result res;
234 225
235 /* 226 /*
236 * Step 1. If skb->priority points to 227 * Step 1. If skb->priority points to one of our classes, use it.
237 */ 228 */
238 if (TC_H_MAJ(prio^sch->handle) == 0 && 229 if (TC_H_MAJ(prio^sch->handle) == 0 &&
239 (cl = cbq_class_lookup(q, prio)) ! 230 (cl = cbq_class_lookup(q, prio)) != NULL)
240 return cl; 231 return cl;
241 232
242 *qerr = NET_XMIT_BYPASS; !! 233 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
243 for (;;) { 234 for (;;) {
244 int result = 0; 235 int result = 0;
245 defmap = head->defaults; 236 defmap = head->defaults;
246 237
247 /* 238 /*
248 * Step 2+n. Apply classifier. 239 * Step 2+n. Apply classifier.
249 */ 240 */
250 if (!head->filter_list || 241 if (!head->filter_list ||
251 (result = tc_classify_comp 242 (result = tc_classify_compat(skb, head->filter_list, &res)) < 0)
252 goto fallback; 243 goto fallback;
253 244
254 if ((cl = (void*)res.class) == 245 if ((cl = (void*)res.class) == NULL) {
255 if (TC_H_MAJ(res.class 246 if (TC_H_MAJ(res.classid))
256 cl = cbq_class 247 cl = cbq_class_lookup(q, res.classid);
257 else if ((cl = defmap[ 248 else if ((cl = defmap[res.classid&TC_PRIO_MAX]) == NULL)
258 cl = defmap[TC 249 cl = defmap[TC_PRIO_BESTEFFORT];
259 250
260 if (cl == NULL || cl-> 251 if (cl == NULL || cl->level >= head->level)
261 goto fallback; 252 goto fallback;
262 } 253 }
263 254
264 #ifdef CONFIG_NET_CLS_ACT 255 #ifdef CONFIG_NET_CLS_ACT
265 switch (result) { 256 switch (result) {
266 case TC_ACT_QUEUED: 257 case TC_ACT_QUEUED:
267 case TC_ACT_STOLEN: 258 case TC_ACT_STOLEN:
268 *qerr = NET_XMIT_SUCCE !! 259 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
269 case TC_ACT_SHOT: 260 case TC_ACT_SHOT:
270 return NULL; 261 return NULL;
271 case TC_ACT_RECLASSIFY: 262 case TC_ACT_RECLASSIFY:
272 return cbq_reclassify( 263 return cbq_reclassify(skb, cl);
273 } 264 }
274 #endif 265 #endif
275 if (cl->level == 0) 266 if (cl->level == 0)
276 return cl; 267 return cl;
277 268
278 /* 269 /*
279 * Step 3+n. If classifier sel 270 * Step 3+n. If classifier selected a link sharing class,
280 * apply agency specif 271 * apply agency specific classifier.
281 * Repeat this procdur 272 * Repeat this procdure until we hit a leaf node.
282 */ 273 */
283 head = cl; 274 head = cl;
284 } 275 }
285 276
286 fallback: 277 fallback:
287 cl = head; 278 cl = head;
288 279
289 /* 280 /*
290 * Step 4. No success... 281 * Step 4. No success...
291 */ 282 */
292 if (TC_H_MAJ(prio) == 0 && 283 if (TC_H_MAJ(prio) == 0 &&
293 !(cl = head->defaults[prio&TC_PRIO 284 !(cl = head->defaults[prio&TC_PRIO_MAX]) &&
294 !(cl = head->defaults[TC_PRIO_BEST 285 !(cl = head->defaults[TC_PRIO_BESTEFFORT]))
295 return head; 286 return head;
296 287
297 return cl; 288 return cl;
298 } 289 }
299 290
300 /* 291 /*
301 A packet has just been enqueued on the empt 292 A packet has just been enqueued on the empty class.
302 cbq_activate_class adds it to the tail of a 293 cbq_activate_class adds it to the tail of active class list
303 of its priority band. 294 of its priority band.
304 */ 295 */
305 296
306 static __inline__ void cbq_activate_class(stru 297 static __inline__ void cbq_activate_class(struct cbq_class *cl)
307 { 298 {
308 struct cbq_sched_data *q = qdisc_priv( 299 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
309 int prio = cl->cpriority; 300 int prio = cl->cpriority;
310 struct cbq_class *cl_tail; 301 struct cbq_class *cl_tail;
311 302
312 cl_tail = q->active[prio]; 303 cl_tail = q->active[prio];
313 q->active[prio] = cl; 304 q->active[prio] = cl;
314 305
315 if (cl_tail != NULL) { 306 if (cl_tail != NULL) {
316 cl->next_alive = cl_tail->next 307 cl->next_alive = cl_tail->next_alive;
317 cl_tail->next_alive = cl; 308 cl_tail->next_alive = cl;
318 } else { 309 } else {
319 cl->next_alive = cl; 310 cl->next_alive = cl;
320 q->activemask |= (1<<prio); 311 q->activemask |= (1<<prio);
321 } 312 }
322 } 313 }
323 314
324 /* 315 /*
325 Unlink class from active chain. 316 Unlink class from active chain.
326 Note that this same procedure is done direc 317 Note that this same procedure is done directly in cbq_dequeue*
327 during round-robin procedure. 318 during round-robin procedure.
328 */ 319 */
329 320
330 static void cbq_deactivate_class(struct cbq_cl 321 static void cbq_deactivate_class(struct cbq_class *this)
331 { 322 {
332 struct cbq_sched_data *q = qdisc_priv( 323 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
333 int prio = this->cpriority; 324 int prio = this->cpriority;
334 struct cbq_class *cl; 325 struct cbq_class *cl;
335 struct cbq_class *cl_prev = q->active[ 326 struct cbq_class *cl_prev = q->active[prio];
336 327
337 do { 328 do {
338 cl = cl_prev->next_alive; 329 cl = cl_prev->next_alive;
339 if (cl == this) { 330 if (cl == this) {
340 cl_prev->next_alive = 331 cl_prev->next_alive = cl->next_alive;
341 cl->next_alive = NULL; 332 cl->next_alive = NULL;
342 333
343 if (cl == q->active[pr 334 if (cl == q->active[prio]) {
344 q->active[prio 335 q->active[prio] = cl_prev;
345 if (cl == q->a 336 if (cl == q->active[prio]) {
346 q->act 337 q->active[prio] = NULL;
347 q->act 338 q->activemask &= ~(1<<prio);
348 return 339 return;
349 } 340 }
350 } 341 }
351 return; 342 return;
352 } 343 }
353 } while ((cl_prev = cl) != q->active[p 344 } while ((cl_prev = cl) != q->active[prio]);
354 } 345 }
355 346
356 static void 347 static void
357 cbq_mark_toplevel(struct cbq_sched_data *q, st 348 cbq_mark_toplevel(struct cbq_sched_data *q, struct cbq_class *cl)
358 { 349 {
359 int toplevel = q->toplevel; 350 int toplevel = q->toplevel;
360 351
361 if (toplevel > cl->level && !(cl->q->f 352 if (toplevel > cl->level && !(cl->q->flags&TCQ_F_THROTTLED)) {
362 psched_time_t now; 353 psched_time_t now;
363 psched_tdiff_t incr; 354 psched_tdiff_t incr;
364 355
365 now = psched_get_time(); 356 now = psched_get_time();
366 incr = now - q->now_rt; 357 incr = now - q->now_rt;
367 now = q->now + incr; 358 now = q->now + incr;
368 359
369 do { 360 do {
370 if (cl->undertime < no 361 if (cl->undertime < now) {
371 q->toplevel = 362 q->toplevel = cl->level;
372 return; 363 return;
373 } 364 }
374 } while ((cl=cl->borrow) != NU 365 } while ((cl=cl->borrow) != NULL && toplevel > cl->level);
375 } 366 }
376 } 367 }
377 368
378 static int 369 static int
379 cbq_enqueue(struct sk_buff *skb, struct Qdisc 370 cbq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
380 { 371 {
381 struct cbq_sched_data *q = qdisc_priv( 372 struct cbq_sched_data *q = qdisc_priv(sch);
382 int len = skb->len; <<
383 int uninitialized_var(ret); 373 int uninitialized_var(ret);
384 struct cbq_class *cl = cbq_classify(sk 374 struct cbq_class *cl = cbq_classify(skb, sch, &ret);
385 375
386 #ifdef CONFIG_NET_CLS_ACT 376 #ifdef CONFIG_NET_CLS_ACT
387 q->rx_class = cl; 377 q->rx_class = cl;
388 #endif 378 #endif
389 if (cl == NULL) { 379 if (cl == NULL) {
390 if (ret == NET_XMIT_BYPASS) !! 380 if (ret & __NET_XMIT_BYPASS)
391 sch->qstats.drops++; 381 sch->qstats.drops++;
392 kfree_skb(skb); 382 kfree_skb(skb);
393 return ret; 383 return ret;
394 } 384 }
395 385
396 #ifdef CONFIG_NET_CLS_ACT 386 #ifdef CONFIG_NET_CLS_ACT
397 cl->q->__parent = sch; 387 cl->q->__parent = sch;
398 #endif 388 #endif
399 if ((ret = cl->q->enqueue(skb, cl->q)) !! 389 ret = qdisc_enqueue(skb, cl->q);
>> 390 if (ret == NET_XMIT_SUCCESS) {
400 sch->q.qlen++; 391 sch->q.qlen++;
401 sch->bstats.packets++; 392 sch->bstats.packets++;
402 sch->bstats.bytes+=len; !! 393 sch->bstats.bytes += qdisc_pkt_len(skb);
403 cbq_mark_toplevel(q, cl); 394 cbq_mark_toplevel(q, cl);
404 if (!cl->next_alive) 395 if (!cl->next_alive)
405 cbq_activate_class(cl) 396 cbq_activate_class(cl);
406 return ret; 397 return ret;
407 } 398 }
408 399
409 sch->qstats.drops++; !! 400 if (net_xmit_drop_count(ret)) {
410 cbq_mark_toplevel(q, cl); <<
411 cl->qstats.drops++; <<
412 return ret; <<
413 } <<
414 <<
415 static int <<
416 cbq_requeue(struct sk_buff *skb, struct Qdisc <<
417 { <<
418 struct cbq_sched_data *q = qdisc_priv( <<
419 struct cbq_class *cl; <<
420 int ret; <<
421 <<
422 if ((cl = q->tx_class) == NULL) { <<
423 kfree_skb(skb); <<
424 sch->qstats.drops++; 401 sch->qstats.drops++;
425 return NET_XMIT_CN; !! 402 cbq_mark_toplevel(q, cl);
426 } !! 403 cl->qstats.drops++;
427 q->tx_class = NULL; <<
428 <<
429 cbq_mark_toplevel(q, cl); <<
430 <<
431 #ifdef CONFIG_NET_CLS_ACT <<
432 q->rx_class = cl; <<
433 cl->q->__parent = sch; <<
434 #endif <<
435 if ((ret = cl->q->ops->requeue(skb, cl <<
436 sch->q.qlen++; <<
437 sch->qstats.requeues++; <<
438 if (!cl->next_alive) <<
439 cbq_activate_class(cl) <<
440 return 0; <<
441 } 404 }
442 sch->qstats.drops++; <<
443 cl->qstats.drops++; <<
444 return ret; 405 return ret;
445 } 406 }
446 407
447 /* Overlimit actions */ 408 /* Overlimit actions */
448 409
449 /* TC_CBQ_OVL_CLASSIC: (default) penalize leaf 410 /* TC_CBQ_OVL_CLASSIC: (default) penalize leaf class by adding offtime */
450 411
451 static void cbq_ovl_classic(struct cbq_class * 412 static void cbq_ovl_classic(struct cbq_class *cl)
452 { 413 {
453 struct cbq_sched_data *q = qdisc_priv( 414 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
454 psched_tdiff_t delay = cl->undertime - 415 psched_tdiff_t delay = cl->undertime - q->now;
455 416
456 if (!cl->delayed) { 417 if (!cl->delayed) {
457 delay += cl->offtime; 418 delay += cl->offtime;
458 419
459 /* 420 /*
460 Class goes to sleep, so tha 421 Class goes to sleep, so that it will have no
461 chance to work avgidle. Let 422 chance to work avgidle. Let's forgive it 8)
462 423
463 BTW cbq-2.0 has a crap in t 424 BTW cbq-2.0 has a crap in this
464 place, apparently they forg 425 place, apparently they forgot to shift it by cl->ewma_log.
465 */ 426 */
466 if (cl->avgidle < 0) 427 if (cl->avgidle < 0)
467 delay -= (-cl->avgidle 428 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
468 if (cl->avgidle < cl->minidle) 429 if (cl->avgidle < cl->minidle)
469 cl->avgidle = cl->mini 430 cl->avgidle = cl->minidle;
470 if (delay <= 0) 431 if (delay <= 0)
471 delay = 1; 432 delay = 1;
472 cl->undertime = q->now + delay 433 cl->undertime = q->now + delay;
473 434
474 cl->xstats.overactions++; 435 cl->xstats.overactions++;
475 cl->delayed = 1; 436 cl->delayed = 1;
476 } 437 }
477 if (q->wd_expires == 0 || q->wd_expire 438 if (q->wd_expires == 0 || q->wd_expires > delay)
478 q->wd_expires = delay; 439 q->wd_expires = delay;
479 440
480 /* Dirty work! We must schedule wakeup 441 /* Dirty work! We must schedule wakeups based on
481 real available rate, rather than le 442 real available rate, rather than leaf rate,
482 which may be tiny (even zero). 443 which may be tiny (even zero).
483 */ 444 */
484 if (q->toplevel == TC_CBQ_MAXLEVEL) { 445 if (q->toplevel == TC_CBQ_MAXLEVEL) {
485 struct cbq_class *b; 446 struct cbq_class *b;
486 psched_tdiff_t base_delay = q- 447 psched_tdiff_t base_delay = q->wd_expires;
487 448
488 for (b = cl->borrow; b; b = b- 449 for (b = cl->borrow; b; b = b->borrow) {
489 delay = b->undertime - 450 delay = b->undertime - q->now;
490 if (delay < base_delay 451 if (delay < base_delay) {
491 if (delay <= 0 452 if (delay <= 0)
492 delay 453 delay = 1;
493 base_delay = d 454 base_delay = delay;
494 } 455 }
495 } 456 }
496 457
497 q->wd_expires = base_delay; 458 q->wd_expires = base_delay;
498 } 459 }
499 } 460 }
500 461
501 /* TC_CBQ_OVL_RCLASSIC: penalize by offtime cl 462 /* TC_CBQ_OVL_RCLASSIC: penalize by offtime classes in hierarchy, when
502 they go overlimit 463 they go overlimit
503 */ 464 */
504 465
505 static void cbq_ovl_rclassic(struct cbq_class 466 static void cbq_ovl_rclassic(struct cbq_class *cl)
506 { 467 {
507 struct cbq_sched_data *q = qdisc_priv( 468 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
508 struct cbq_class *this = cl; 469 struct cbq_class *this = cl;
509 470
510 do { 471 do {
511 if (cl->level > q->toplevel) { 472 if (cl->level > q->toplevel) {
512 cl = NULL; 473 cl = NULL;
513 break; 474 break;
514 } 475 }
515 } while ((cl = cl->borrow) != NULL); 476 } while ((cl = cl->borrow) != NULL);
516 477
517 if (cl == NULL) 478 if (cl == NULL)
518 cl = this; 479 cl = this;
519 cbq_ovl_classic(cl); 480 cbq_ovl_classic(cl);
520 } 481 }
521 482
522 /* TC_CBQ_OVL_DELAY: delay until it will go to 483 /* TC_CBQ_OVL_DELAY: delay until it will go to underlimit */
523 484
524 static void cbq_ovl_delay(struct cbq_class *cl 485 static void cbq_ovl_delay(struct cbq_class *cl)
525 { 486 {
526 struct cbq_sched_data *q = qdisc_priv( 487 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
527 psched_tdiff_t delay = cl->undertime - 488 psched_tdiff_t delay = cl->undertime - q->now;
528 489
>> 490 if (test_bit(__QDISC_STATE_DEACTIVATED,
>> 491 &qdisc_root_sleeping(cl->qdisc)->state))
>> 492 return;
>> 493
529 if (!cl->delayed) { 494 if (!cl->delayed) {
530 psched_time_t sched = q->now; 495 psched_time_t sched = q->now;
531 ktime_t expires; 496 ktime_t expires;
532 497
533 delay += cl->offtime; 498 delay += cl->offtime;
534 if (cl->avgidle < 0) 499 if (cl->avgidle < 0)
535 delay -= (-cl->avgidle 500 delay -= (-cl->avgidle) - ((-cl->avgidle) >> cl->ewma_log);
536 if (cl->avgidle < cl->minidle) 501 if (cl->avgidle < cl->minidle)
537 cl->avgidle = cl->mini 502 cl->avgidle = cl->minidle;
538 cl->undertime = q->now + delay 503 cl->undertime = q->now + delay;
539 504
540 if (delay > 0) { 505 if (delay > 0) {
541 sched += delay + cl->p 506 sched += delay + cl->penalty;
542 cl->penalized = sched; 507 cl->penalized = sched;
543 cl->cpriority = TC_CBQ 508 cl->cpriority = TC_CBQ_MAXPRIO;
544 q->pmask |= (1<<TC_CBQ 509 q->pmask |= (1<<TC_CBQ_MAXPRIO);
545 510
546 expires = ktime_set(0, 511 expires = ktime_set(0, 0);
547 expires = ktime_add_ns !! 512 expires = ktime_add_ns(expires, PSCHED_TICKS2NS(sched));
548 if (hrtimer_try_to_can 513 if (hrtimer_try_to_cancel(&q->delay_timer) &&
549 ktime_to_ns(ktime_ !! 514 ktime_to_ns(ktime_sub(
550 !! 515 hrtimer_get_expires(&q->delay_timer),
551 q->delay_timer !! 516 expires)) > 0)
>> 517 hrtimer_set_expires(&q->delay_timer, expires);
552 hrtimer_restart(&q->de 518 hrtimer_restart(&q->delay_timer);
553 cl->delayed = 1; 519 cl->delayed = 1;
554 cl->xstats.overactions 520 cl->xstats.overactions++;
555 return; 521 return;
556 } 522 }
557 delay = 1; 523 delay = 1;
558 } 524 }
559 if (q->wd_expires == 0 || q->wd_expire 525 if (q->wd_expires == 0 || q->wd_expires > delay)
560 q->wd_expires = delay; 526 q->wd_expires = delay;
561 } 527 }
562 528
563 /* TC_CBQ_OVL_LOWPRIO: penalize class by lower 529 /* TC_CBQ_OVL_LOWPRIO: penalize class by lowering its priority band */
564 530
565 static void cbq_ovl_lowprio(struct cbq_class * 531 static void cbq_ovl_lowprio(struct cbq_class *cl)
566 { 532 {
567 struct cbq_sched_data *q = qdisc_priv( 533 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
568 534
569 cl->penalized = q->now + cl->penalty; 535 cl->penalized = q->now + cl->penalty;
570 536
571 if (cl->cpriority != cl->priority2) { 537 if (cl->cpriority != cl->priority2) {
572 cl->cpriority = cl->priority2; 538 cl->cpriority = cl->priority2;
573 q->pmask |= (1<<cl->cpriority) 539 q->pmask |= (1<<cl->cpriority);
574 cl->xstats.overactions++; 540 cl->xstats.overactions++;
575 } 541 }
576 cbq_ovl_classic(cl); 542 cbq_ovl_classic(cl);
577 } 543 }
578 544
579 /* TC_CBQ_OVL_DROP: penalize class by dropping 545 /* TC_CBQ_OVL_DROP: penalize class by dropping */
580 546
581 static void cbq_ovl_drop(struct cbq_class *cl) 547 static void cbq_ovl_drop(struct cbq_class *cl)
582 { 548 {
583 if (cl->q->ops->drop) 549 if (cl->q->ops->drop)
584 if (cl->q->ops->drop(cl->q)) 550 if (cl->q->ops->drop(cl->q))
585 cl->qdisc->q.qlen--; 551 cl->qdisc->q.qlen--;
586 cl->xstats.overactions++; 552 cl->xstats.overactions++;
587 cbq_ovl_classic(cl); 553 cbq_ovl_classic(cl);
588 } 554 }
589 555
590 static psched_tdiff_t cbq_undelay_prio(struct 556 static psched_tdiff_t cbq_undelay_prio(struct cbq_sched_data *q, int prio,
591 psched_ 557 psched_time_t now)
592 { 558 {
593 struct cbq_class *cl; 559 struct cbq_class *cl;
594 struct cbq_class *cl_prev = q->active[ 560 struct cbq_class *cl_prev = q->active[prio];
595 psched_time_t sched = now; 561 psched_time_t sched = now;
596 562
597 if (cl_prev == NULL) 563 if (cl_prev == NULL)
598 return 0; 564 return 0;
599 565
600 do { 566 do {
601 cl = cl_prev->next_alive; 567 cl = cl_prev->next_alive;
602 if (now - cl->penalized > 0) { 568 if (now - cl->penalized > 0) {
603 cl_prev->next_alive = 569 cl_prev->next_alive = cl->next_alive;
604 cl->next_alive = NULL; 570 cl->next_alive = NULL;
605 cl->cpriority = cl->pr 571 cl->cpriority = cl->priority;
606 cl->delayed = 0; 572 cl->delayed = 0;
607 cbq_activate_class(cl) 573 cbq_activate_class(cl);
608 574
609 if (cl == q->active[pr 575 if (cl == q->active[prio]) {
610 q->active[prio 576 q->active[prio] = cl_prev;
611 if (cl == q->a 577 if (cl == q->active[prio]) {
612 q->act 578 q->active[prio] = NULL;
613 return 579 return 0;
614 } 580 }
615 } 581 }
616 582
617 cl = cl_prev->next_ali 583 cl = cl_prev->next_alive;
618 } else if (sched - cl->penaliz 584 } else if (sched - cl->penalized > 0)
619 sched = cl->penalized; 585 sched = cl->penalized;
620 } while ((cl_prev = cl) != q->active[p 586 } while ((cl_prev = cl) != q->active[prio]);
621 587
622 return sched - now; 588 return sched - now;
623 } 589 }
624 590
625 static enum hrtimer_restart cbq_undelay(struct 591 static enum hrtimer_restart cbq_undelay(struct hrtimer *timer)
626 { 592 {
627 struct cbq_sched_data *q = container_o 593 struct cbq_sched_data *q = container_of(timer, struct cbq_sched_data,
628 594 delay_timer);
629 struct Qdisc *sch = q->watchdog.qdisc; 595 struct Qdisc *sch = q->watchdog.qdisc;
630 psched_time_t now; 596 psched_time_t now;
631 psched_tdiff_t delay = 0; 597 psched_tdiff_t delay = 0;
632 unsigned pmask; 598 unsigned pmask;
633 599
634 now = psched_get_time(); 600 now = psched_get_time();
635 601
636 pmask = q->pmask; 602 pmask = q->pmask;
637 q->pmask = 0; 603 q->pmask = 0;
638 604
639 while (pmask) { 605 while (pmask) {
640 int prio = ffz(~pmask); 606 int prio = ffz(~pmask);
641 psched_tdiff_t tmp; 607 psched_tdiff_t tmp;
642 608
643 pmask &= ~(1<<prio); 609 pmask &= ~(1<<prio);
644 610
645 tmp = cbq_undelay_prio(q, prio 611 tmp = cbq_undelay_prio(q, prio, now);
646 if (tmp > 0) { 612 if (tmp > 0) {
647 q->pmask |= 1<<prio; 613 q->pmask |= 1<<prio;
648 if (tmp < delay || del 614 if (tmp < delay || delay == 0)
649 delay = tmp; 615 delay = tmp;
650 } 616 }
651 } 617 }
652 618
653 if (delay) { 619 if (delay) {
654 ktime_t time; 620 ktime_t time;
655 621
656 time = ktime_set(0, 0); 622 time = ktime_set(0, 0);
657 time = ktime_add_ns(time, PSCH !! 623 time = ktime_add_ns(time, PSCHED_TICKS2NS(now + delay));
658 hrtimer_start(&q->delay_timer, 624 hrtimer_start(&q->delay_timer, time, HRTIMER_MODE_ABS);
659 } 625 }
660 626
661 sch->flags &= ~TCQ_F_THROTTLED; 627 sch->flags &= ~TCQ_F_THROTTLED;
662 netif_schedule(sch->dev); !! 628 __netif_schedule(qdisc_root(sch));
663 return HRTIMER_NORESTART; 629 return HRTIMER_NORESTART;
664 } 630 }
665 631
666 #ifdef CONFIG_NET_CLS_ACT 632 #ifdef CONFIG_NET_CLS_ACT
667 static int cbq_reshape_fail(struct sk_buff *sk 633 static int cbq_reshape_fail(struct sk_buff *skb, struct Qdisc *child)
668 { 634 {
669 int len = skb->len; <<
670 struct Qdisc *sch = child->__parent; 635 struct Qdisc *sch = child->__parent;
671 struct cbq_sched_data *q = qdisc_priv( 636 struct cbq_sched_data *q = qdisc_priv(sch);
672 struct cbq_class *cl = q->rx_class; 637 struct cbq_class *cl = q->rx_class;
673 638
674 q->rx_class = NULL; 639 q->rx_class = NULL;
675 640
676 if (cl && (cl = cbq_reclassify(skb, cl 641 if (cl && (cl = cbq_reclassify(skb, cl)) != NULL) {
>> 642 int ret;
677 643
678 cbq_mark_toplevel(q, cl); 644 cbq_mark_toplevel(q, cl);
679 645
680 q->rx_class = cl; 646 q->rx_class = cl;
681 cl->q->__parent = sch; 647 cl->q->__parent = sch;
682 648
683 if (cl->q->enqueue(skb, cl->q) !! 649 ret = qdisc_enqueue(skb, cl->q);
>> 650 if (ret == NET_XMIT_SUCCESS) {
684 sch->q.qlen++; 651 sch->q.qlen++;
685 sch->bstats.packets++; 652 sch->bstats.packets++;
686 sch->bstats.bytes+=len !! 653 sch->bstats.bytes += qdisc_pkt_len(skb);
687 if (!cl->next_alive) 654 if (!cl->next_alive)
688 cbq_activate_c 655 cbq_activate_class(cl);
689 return 0; 656 return 0;
690 } 657 }
691 sch->qstats.drops++; !! 658 if (net_xmit_drop_count(ret))
>> 659 sch->qstats.drops++;
692 return 0; 660 return 0;
693 } 661 }
694 662
695 sch->qstats.drops++; 663 sch->qstats.drops++;
696 return -1; 664 return -1;
697 } 665 }
698 #endif 666 #endif
699 667
700 /* 668 /*
701 It is mission critical procedure. 669 It is mission critical procedure.
702 670
703 We "regenerate" toplevel cutoff, if transmi 671 We "regenerate" toplevel cutoff, if transmitting class
704 has backlog and it is not regulated. It is 672 has backlog and it is not regulated. It is not part of
705 original CBQ description, but looks more re 673 original CBQ description, but looks more reasonable.
706 Probably, it is wrong. This question needs 674 Probably, it is wrong. This question needs further investigation.
707 */ 675 */
708 676
709 static __inline__ void 677 static __inline__ void
710 cbq_update_toplevel(struct cbq_sched_data *q, 678 cbq_update_toplevel(struct cbq_sched_data *q, struct cbq_class *cl,
711 struct cbq_class *borrowed 679 struct cbq_class *borrowed)
712 { 680 {
713 if (cl && q->toplevel >= borrowed->lev 681 if (cl && q->toplevel >= borrowed->level) {
714 if (cl->q->q.qlen > 1) { 682 if (cl->q->q.qlen > 1) {
715 do { 683 do {
716 if (borrowed-> 684 if (borrowed->undertime == PSCHED_PASTPERFECT) {
717 q->top 685 q->toplevel = borrowed->level;
718 return 686 return;
719 } 687 }
720 } while ((borrowed=bor 688 } while ((borrowed=borrowed->borrow) != NULL);
721 } 689 }
722 #if 0 690 #if 0
723 /* It is not necessary now. Uncommenti 691 /* It is not necessary now. Uncommenting it
724 will save CPU cycles, but decrease 692 will save CPU cycles, but decrease fairness.
725 */ 693 */
726 q->toplevel = TC_CBQ_MAXLEVEL; 694 q->toplevel = TC_CBQ_MAXLEVEL;
727 #endif 695 #endif
728 } 696 }
729 } 697 }
730 698
731 static void 699 static void
732 cbq_update(struct cbq_sched_data *q) 700 cbq_update(struct cbq_sched_data *q)
733 { 701 {
734 struct cbq_class *this = q->tx_class; 702 struct cbq_class *this = q->tx_class;
735 struct cbq_class *cl = this; 703 struct cbq_class *cl = this;
736 int len = q->tx_len; 704 int len = q->tx_len;
737 705
738 q->tx_class = NULL; 706 q->tx_class = NULL;
739 707
740 for ( ; cl; cl = cl->share) { 708 for ( ; cl; cl = cl->share) {
741 long avgidle = cl->avgidle; 709 long avgidle = cl->avgidle;
742 long idle; 710 long idle;
743 711
744 cl->bstats.packets++; 712 cl->bstats.packets++;
745 cl->bstats.bytes += len; 713 cl->bstats.bytes += len;
746 714
747 /* 715 /*
748 (now - last) is total time 716 (now - last) is total time between packet right edges.
749 (last_pktlen/rate) is "virt 717 (last_pktlen/rate) is "virtual" busy time, so that
750 718
751 idle = (now - last) - 719 idle = (now - last) - last_pktlen/rate
752 */ 720 */
753 721
754 idle = q->now - cl->last; 722 idle = q->now - cl->last;
755 if ((unsigned long)idle > 128* 723 if ((unsigned long)idle > 128*1024*1024) {
756 avgidle = cl->maxidle; 724 avgidle = cl->maxidle;
757 } else { 725 } else {
758 idle -= L2T(cl, len); 726 idle -= L2T(cl, len);
759 727
760 /* true_avgidle := (1-W)*true_ 728 /* true_avgidle := (1-W)*true_avgidle + W*idle,
761 where W=2^{-ewma_log}. But 729 where W=2^{-ewma_log}. But cl->avgidle is scaled:
762 cl->avgidle == true_avgidle 730 cl->avgidle == true_avgidle/W,
763 hence: 731 hence:
764 */ 732 */
765 avgidle += idle - (avg 733 avgidle += idle - (avgidle>>cl->ewma_log);
766 } 734 }
767 735
768 if (avgidle <= 0) { 736 if (avgidle <= 0) {
769 /* Overlimit or at-lim 737 /* Overlimit or at-limit */
770 738
771 if (avgidle < cl->mini 739 if (avgidle < cl->minidle)
772 avgidle = cl-> 740 avgidle = cl->minidle;
773 741
774 cl->avgidle = avgidle; 742 cl->avgidle = avgidle;
775 743
776 /* Calculate expected 744 /* Calculate expected time, when this class
777 will be allowed to 745 will be allowed to send.
778 It will occur, when 746 It will occur, when:
779 (1-W)*true_avgidle 747 (1-W)*true_avgidle + W*delay = 0, i.e.
780 idle = (1/W - 1)*(- 748 idle = (1/W - 1)*(-true_avgidle)
781 or 749 or
782 idle = (1 - W)*(-cl 750 idle = (1 - W)*(-cl->avgidle);
783 */ 751 */
784 idle = (-avgidle) - (( 752 idle = (-avgidle) - ((-avgidle) >> cl->ewma_log);
785 753
786 /* 754 /*
787 That is not all. 755 That is not all.
788 To maintain the rat 756 To maintain the rate allocated to the class,
789 we add to undertime 757 we add to undertime virtual clock,
790 necessary to comple 758 necessary to complete transmitted packet.
791 (len/phys_bandwidth 759 (len/phys_bandwidth has been already passed
792 to the moment of cb 760 to the moment of cbq_update)
793 */ 761 */
794 762
795 idle -= L2T(&q->link, 763 idle -= L2T(&q->link, len);
796 idle += L2T(cl, len); 764 idle += L2T(cl, len);
797 765
798 cl->undertime = q->now 766 cl->undertime = q->now + idle;
799 } else { 767 } else {
800 /* Underlimit */ 768 /* Underlimit */
801 769
802 cl->undertime = PSCHED 770 cl->undertime = PSCHED_PASTPERFECT;
803 if (avgidle > cl->maxi 771 if (avgidle > cl->maxidle)
804 cl->avgidle = 772 cl->avgidle = cl->maxidle;
805 else 773 else
806 cl->avgidle = 774 cl->avgidle = avgidle;
807 } 775 }
808 cl->last = q->now; 776 cl->last = q->now;
809 } 777 }
810 778
811 cbq_update_toplevel(q, this, q->tx_bor 779 cbq_update_toplevel(q, this, q->tx_borrowed);
812 } 780 }
813 781
814 static __inline__ struct cbq_class * 782 static __inline__ struct cbq_class *
815 cbq_under_limit(struct cbq_class *cl) 783 cbq_under_limit(struct cbq_class *cl)
816 { 784 {
817 struct cbq_sched_data *q = qdisc_priv( 785 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
818 struct cbq_class *this_cl = cl; 786 struct cbq_class *this_cl = cl;
819 787
820 if (cl->tparent == NULL) 788 if (cl->tparent == NULL)
821 return cl; 789 return cl;
822 790
823 if (cl->undertime == PSCHED_PASTPERFEC 791 if (cl->undertime == PSCHED_PASTPERFECT || q->now >= cl->undertime) {
824 cl->delayed = 0; 792 cl->delayed = 0;
825 return cl; 793 return cl;
826 } 794 }
827 795
828 do { 796 do {
829 /* It is very suspicious place 797 /* It is very suspicious place. Now overlimit
830 action is generated for not 798 action is generated for not bounded classes
831 only if link is completely 799 only if link is completely congested.
832 Though it is in agree with 800 Though it is in agree with ancestor-only paradigm,
833 it looks very stupid. Parti 801 it looks very stupid. Particularly,
834 it means that this chunk of 802 it means that this chunk of code will either
835 never be called or result i 803 never be called or result in strong amplification
836 of burstiness. Dangerous, s 804 of burstiness. Dangerous, silly, and, however,
837 no another solution exists. 805 no another solution exists.
838 */ 806 */
839 if ((cl = cl->borrow) == NULL) 807 if ((cl = cl->borrow) == NULL) {
840 this_cl->qstats.overli 808 this_cl->qstats.overlimits++;
841 this_cl->overlimit(thi 809 this_cl->overlimit(this_cl);
842 return NULL; 810 return NULL;
843 } 811 }
844 if (cl->level > q->toplevel) 812 if (cl->level > q->toplevel)
845 return NULL; 813 return NULL;
846 } while (cl->undertime != PSCHED_PASTP 814 } while (cl->undertime != PSCHED_PASTPERFECT && q->now < cl->undertime);
847 815
848 cl->delayed = 0; 816 cl->delayed = 0;
849 return cl; 817 return cl;
850 } 818 }
851 819
852 static __inline__ struct sk_buff * 820 static __inline__ struct sk_buff *
853 cbq_dequeue_prio(struct Qdisc *sch, int prio) 821 cbq_dequeue_prio(struct Qdisc *sch, int prio)
854 { 822 {
855 struct cbq_sched_data *q = qdisc_priv( 823 struct cbq_sched_data *q = qdisc_priv(sch);
856 struct cbq_class *cl_tail, *cl_prev, * 824 struct cbq_class *cl_tail, *cl_prev, *cl;
857 struct sk_buff *skb; 825 struct sk_buff *skb;
858 int deficit; 826 int deficit;
859 827
860 cl_tail = cl_prev = q->active[prio]; 828 cl_tail = cl_prev = q->active[prio];
861 cl = cl_prev->next_alive; 829 cl = cl_prev->next_alive;
862 830
863 do { 831 do {
864 deficit = 0; 832 deficit = 0;
865 833
866 /* Start round */ 834 /* Start round */
867 do { 835 do {
868 struct cbq_class *borr 836 struct cbq_class *borrow = cl;
869 837
870 if (cl->q->q.qlen && 838 if (cl->q->q.qlen &&
871 (borrow = cbq_unde 839 (borrow = cbq_under_limit(cl)) == NULL)
872 goto skip_clas 840 goto skip_class;
873 841
874 if (cl->deficit <= 0) 842 if (cl->deficit <= 0) {
875 /* Class exhau 843 /* Class exhausted its allotment per
876 this round. 844 this round. Switch to the next one.
877 */ 845 */
878 deficit = 1; 846 deficit = 1;
879 cl->deficit += 847 cl->deficit += cl->quantum;
880 goto next_clas 848 goto next_class;
881 } 849 }
882 850
883 skb = cl->q->dequeue(c 851 skb = cl->q->dequeue(cl->q);
884 852
885 /* Class did not give 853 /* Class did not give us any skb :-(
886 It could occur even 854 It could occur even if cl->q->q.qlen != 0
887 f.e. if cl->q == "t 855 f.e. if cl->q == "tbf"
888 */ 856 */
889 if (skb == NULL) 857 if (skb == NULL)
890 goto skip_clas 858 goto skip_class;
891 859
892 cl->deficit -= skb->le !! 860 cl->deficit -= qdisc_pkt_len(skb);
893 q->tx_class = cl; 861 q->tx_class = cl;
894 q->tx_borrowed = borro 862 q->tx_borrowed = borrow;
895 if (borrow != cl) { 863 if (borrow != cl) {
896 #ifndef CBQ_XSTATS_BORROWS_BYTES 864 #ifndef CBQ_XSTATS_BORROWS_BYTES
897 borrow->xstats 865 borrow->xstats.borrows++;
898 cl->xstats.bor 866 cl->xstats.borrows++;
899 #else 867 #else
900 borrow->xstats !! 868 borrow->xstats.borrows += qdisc_pkt_len(skb);
901 cl->xstats.bor !! 869 cl->xstats.borrows += qdisc_pkt_len(skb);
902 #endif 870 #endif
903 } 871 }
904 q->tx_len = skb->len; !! 872 q->tx_len = qdisc_pkt_len(skb);
905 873
906 if (cl->deficit <= 0) 874 if (cl->deficit <= 0) {
907 q->active[prio 875 q->active[prio] = cl;
908 cl = cl->next_ 876 cl = cl->next_alive;
909 cl->deficit += 877 cl->deficit += cl->quantum;
910 } 878 }
911 return skb; 879 return skb;
912 880
913 skip_class: 881 skip_class:
914 if (cl->q->q.qlen == 0 882 if (cl->q->q.qlen == 0 || prio != cl->cpriority) {
915 /* Class is em 883 /* Class is empty or penalized.
916 Unlink it f 884 Unlink it from active chain.
917 */ 885 */
918 cl_prev->next_ 886 cl_prev->next_alive = cl->next_alive;
919 cl->next_alive 887 cl->next_alive = NULL;
920 888
921 /* Did cl_tail 889 /* Did cl_tail point to it? */
922 if (cl == cl_t 890 if (cl == cl_tail) {
923 /* Rep 891 /* Repair it! */
924 cl_tai 892 cl_tail = cl_prev;
925 893
926 /* Was 894 /* Was it the last class in this band? */
927 if (cl 895 if (cl == cl_tail) {
928 896 /* Kill the band! */
929 897 q->active[prio] = NULL;
930 898 q->activemask &= ~(1<<prio);
931 899 if (cl->q->q.qlen)
932 900 cbq_activate_class(cl);
933 901 return NULL;
934 } 902 }
935 903
936 q->act 904 q->active[prio] = cl_tail;
937 } 905 }
938 if (cl->q->q.q 906 if (cl->q->q.qlen)
939 cbq_ac 907 cbq_activate_class(cl);
940 908
941 cl = cl_prev; 909 cl = cl_prev;
942 } 910 }
943 911
944 next_class: 912 next_class:
945 cl_prev = cl; 913 cl_prev = cl;
946 cl = cl->next_alive; 914 cl = cl->next_alive;
947 } while (cl_prev != cl_tail); 915 } while (cl_prev != cl_tail);
948 } while (deficit); 916 } while (deficit);
949 917
950 q->active[prio] = cl_prev; 918 q->active[prio] = cl_prev;
951 919
952 return NULL; 920 return NULL;
953 } 921 }
954 922
955 static __inline__ struct sk_buff * 923 static __inline__ struct sk_buff *
956 cbq_dequeue_1(struct Qdisc *sch) 924 cbq_dequeue_1(struct Qdisc *sch)
957 { 925 {
958 struct cbq_sched_data *q = qdisc_priv( 926 struct cbq_sched_data *q = qdisc_priv(sch);
959 struct sk_buff *skb; 927 struct sk_buff *skb;
960 unsigned activemask; 928 unsigned activemask;
961 929
962 activemask = q->activemask&0xFF; 930 activemask = q->activemask&0xFF;
963 while (activemask) { 931 while (activemask) {
964 int prio = ffz(~activemask); 932 int prio = ffz(~activemask);
965 activemask &= ~(1<<prio); 933 activemask &= ~(1<<prio);
966 skb = cbq_dequeue_prio(sch, pr 934 skb = cbq_dequeue_prio(sch, prio);
967 if (skb) 935 if (skb)
968 return skb; 936 return skb;
969 } 937 }
970 return NULL; 938 return NULL;
971 } 939 }
972 940
973 static struct sk_buff * 941 static struct sk_buff *
974 cbq_dequeue(struct Qdisc *sch) 942 cbq_dequeue(struct Qdisc *sch)
975 { 943 {
976 struct sk_buff *skb; 944 struct sk_buff *skb;
977 struct cbq_sched_data *q = qdisc_priv( 945 struct cbq_sched_data *q = qdisc_priv(sch);
978 psched_time_t now; 946 psched_time_t now;
979 psched_tdiff_t incr; 947 psched_tdiff_t incr;
980 948
981 now = psched_get_time(); 949 now = psched_get_time();
982 incr = now - q->now_rt; 950 incr = now - q->now_rt;
983 951
984 if (q->tx_class) { 952 if (q->tx_class) {
985 psched_tdiff_t incr2; 953 psched_tdiff_t incr2;
986 /* Time integrator. We calcula 954 /* Time integrator. We calculate EOS time
987 by adding expected packet t 955 by adding expected packet transmission time.
988 If real time is greater, we 956 If real time is greater, we warp artificial clock,
989 so that: 957 so that:
990 958
991 cbq_time = max(real_time, w 959 cbq_time = max(real_time, work);
992 */ 960 */
993 incr2 = L2T(&q->link, q->tx_le 961 incr2 = L2T(&q->link, q->tx_len);
994 q->now += incr2; 962 q->now += incr2;
995 cbq_update(q); 963 cbq_update(q);
996 if ((incr -= incr2) < 0) 964 if ((incr -= incr2) < 0)
997 incr = 0; 965 incr = 0;
998 } 966 }
999 q->now += incr; 967 q->now += incr;
1000 q->now_rt = now; 968 q->now_rt = now;
1001 969
1002 for (;;) { 970 for (;;) {
1003 q->wd_expires = 0; 971 q->wd_expires = 0;
1004 972
1005 skb = cbq_dequeue_1(sch); 973 skb = cbq_dequeue_1(sch);
1006 if (skb) { 974 if (skb) {
1007 sch->q.qlen--; 975 sch->q.qlen--;
1008 sch->flags &= ~TCQ_F_ 976 sch->flags &= ~TCQ_F_THROTTLED;
1009 return skb; 977 return skb;
1010 } 978 }
1011 979
1012 /* All the classes are overli 980 /* All the classes are overlimit.
1013 981
1014 It is possible, if: 982 It is possible, if:
1015 983
1016 1. Scheduler is empty. 984 1. Scheduler is empty.
1017 2. Toplevel cutoff inhibit 985 2. Toplevel cutoff inhibited borrowing.
1018 3. Root class is overlimit 986 3. Root class is overlimit.
1019 987
1020 Reset 2d and 3d conditions 988 Reset 2d and 3d conditions and retry.
1021 989
1022 Note, that NS and cbq-2.0 990 Note, that NS and cbq-2.0 are buggy, peeking
1023 an arbitrary class is appr 991 an arbitrary class is appropriate for ancestor-only
1024 sharing, but not for tople 992 sharing, but not for toplevel algorithm.
1025 993
1026 Our version is better, but 994 Our version is better, but slower, because it requires
1027 two passes, but it is unav 995 two passes, but it is unavoidable with top-level sharing.
1028 */ 996 */
1029 997
1030 if (q->toplevel == TC_CBQ_MAX 998 if (q->toplevel == TC_CBQ_MAXLEVEL &&
1031 q->link.undertime == PSCH 999 q->link.undertime == PSCHED_PASTPERFECT)
1032 break; 1000 break;
1033 1001
1034 q->toplevel = TC_CBQ_MAXLEVEL 1002 q->toplevel = TC_CBQ_MAXLEVEL;
1035 q->link.undertime = PSCHED_PA 1003 q->link.undertime = PSCHED_PASTPERFECT;
1036 } 1004 }
1037 1005
1038 /* No packets in scheduler or nobody 1006 /* No packets in scheduler or nobody wants to give them to us :-(
1039 Sigh... start watchdog timer in th 1007 Sigh... start watchdog timer in the last case. */
1040 1008
1041 if (sch->q.qlen) { 1009 if (sch->q.qlen) {
1042 sch->qstats.overlimits++; 1010 sch->qstats.overlimits++;
1043 if (q->wd_expires) 1011 if (q->wd_expires)
1044 qdisc_watchdog_schedu 1012 qdisc_watchdog_schedule(&q->watchdog,
1045 1013 now + q->wd_expires);
1046 } 1014 }
1047 return NULL; 1015 return NULL;
1048 } 1016 }
1049 1017
1050 /* CBQ class maintanance routines */ 1018 /* CBQ class maintanance routines */
1051 1019
1052 static void cbq_adjust_levels(struct cbq_clas 1020 static void cbq_adjust_levels(struct cbq_class *this)
1053 { 1021 {
1054 if (this == NULL) 1022 if (this == NULL)
1055 return; 1023 return;
1056 1024
1057 do { 1025 do {
1058 int level = 0; 1026 int level = 0;
1059 struct cbq_class *cl; 1027 struct cbq_class *cl;
1060 1028
1061 if ((cl = this->children) != 1029 if ((cl = this->children) != NULL) {
1062 do { 1030 do {
1063 if (cl->level 1031 if (cl->level > level)
1064 level 1032 level = cl->level;
1065 } while ((cl = cl->si 1033 } while ((cl = cl->sibling) != this->children);
1066 } 1034 }
1067 this->level = level+1; 1035 this->level = level+1;
1068 } while ((this = this->tparent) != NU 1036 } while ((this = this->tparent) != NULL);
1069 } 1037 }
1070 1038
1071 static void cbq_normalize_quanta(struct cbq_s 1039 static void cbq_normalize_quanta(struct cbq_sched_data *q, int prio)
1072 { 1040 {
1073 struct cbq_class *cl; 1041 struct cbq_class *cl;
1074 unsigned h; !! 1042 struct hlist_node *n;
>> 1043 unsigned int h;
1075 1044
1076 if (q->quanta[prio] == 0) 1045 if (q->quanta[prio] == 0)
1077 return; 1046 return;
1078 1047
1079 for (h=0; h<16; h++) { !! 1048 for (h = 0; h < q->clhash.hashsize; h++) {
1080 for (cl = q->classes[h]; cl; !! 1049 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
1081 /* BUGGGG... Beware! 1050 /* BUGGGG... Beware! This expression suffer of
1082 arithmetic overflo 1051 arithmetic overflows!
1083 */ 1052 */
1084 if (cl->priority == p 1053 if (cl->priority == prio) {
1085 cl->quantum = 1054 cl->quantum = (cl->weight*cl->allot*q->nclasses[prio])/
1086 q->qu 1055 q->quanta[prio];
1087 } 1056 }
1088 if (cl->quantum <= 0 !! 1057 if (cl->quantum <= 0 || cl->quantum>32*qdisc_dev(cl->qdisc)->mtu) {
1089 printk(KERN_W !! 1058 printk(KERN_WARNING "CBQ: class %08x has bad quantum==%ld, repaired.\n", cl->common.classid, cl->quantum);
1090 cl->quantum = !! 1059 cl->quantum = qdisc_dev(cl->qdisc)->mtu/2 + 1;
1091 } 1060 }
1092 } 1061 }
1093 } 1062 }
1094 } 1063 }
1095 1064
1096 static void cbq_sync_defmap(struct cbq_class 1065 static void cbq_sync_defmap(struct cbq_class *cl)
1097 { 1066 {
1098 struct cbq_sched_data *q = qdisc_priv 1067 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1099 struct cbq_class *split = cl->split; 1068 struct cbq_class *split = cl->split;
1100 unsigned h; 1069 unsigned h;
1101 int i; 1070 int i;
1102 1071
1103 if (split == NULL) 1072 if (split == NULL)
1104 return; 1073 return;
1105 1074
1106 for (i=0; i<=TC_PRIO_MAX; i++) { 1075 for (i=0; i<=TC_PRIO_MAX; i++) {
1107 if (split->defaults[i] == cl 1076 if (split->defaults[i] == cl && !(cl->defmap&(1<<i)))
1108 split->defaults[i] = 1077 split->defaults[i] = NULL;
1109 } 1078 }
1110 1079
1111 for (i=0; i<=TC_PRIO_MAX; i++) { 1080 for (i=0; i<=TC_PRIO_MAX; i++) {
1112 int level = split->level; 1081 int level = split->level;
1113 1082
1114 if (split->defaults[i]) 1083 if (split->defaults[i])
1115 continue; 1084 continue;
1116 1085
1117 for (h=0; h<16; h++) { !! 1086 for (h = 0; h < q->clhash.hashsize; h++) {
>> 1087 struct hlist_node *n;
1118 struct cbq_class *c; 1088 struct cbq_class *c;
1119 1089
1120 for (c = q->classes[h !! 1090 hlist_for_each_entry(c, n, &q->clhash.hash[h],
>> 1091 common.hnode) {
1121 if (c->split 1092 if (c->split == split && c->level < level &&
1122 c->defmap 1093 c->defmap&(1<<i)) {
1123 split 1094 split->defaults[i] = c;
1124 level 1095 level = c->level;
1125 } 1096 }
1126 } 1097 }
1127 } 1098 }
1128 } 1099 }
1129 } 1100 }
1130 1101
1131 static void cbq_change_defmap(struct cbq_clas 1102 static void cbq_change_defmap(struct cbq_class *cl, u32 splitid, u32 def, u32 mask)
1132 { 1103 {
1133 struct cbq_class *split = NULL; 1104 struct cbq_class *split = NULL;
1134 1105
1135 if (splitid == 0) { 1106 if (splitid == 0) {
1136 if ((split = cl->split) == NU 1107 if ((split = cl->split) == NULL)
1137 return; 1108 return;
1138 splitid = split->classid; !! 1109 splitid = split->common.classid;
1139 } 1110 }
1140 1111
1141 if (split == NULL || split->classid ! !! 1112 if (split == NULL || split->common.classid != splitid) {
1142 for (split = cl->tparent; spl 1113 for (split = cl->tparent; split; split = split->tparent)
1143 if (split->classid == !! 1114 if (split->common.classid == splitid)
1144 break; 1115 break;
1145 } 1116 }
1146 1117
1147 if (split == NULL) 1118 if (split == NULL)
1148 return; 1119 return;
1149 1120
1150 if (cl->split != split) { 1121 if (cl->split != split) {
1151 cl->defmap = 0; 1122 cl->defmap = 0;
1152 cbq_sync_defmap(cl); 1123 cbq_sync_defmap(cl);
1153 cl->split = split; 1124 cl->split = split;
1154 cl->defmap = def&mask; 1125 cl->defmap = def&mask;
1155 } else 1126 } else
1156 cl->defmap = (cl->defmap&~mas 1127 cl->defmap = (cl->defmap&~mask)|(def&mask);
1157 1128
1158 cbq_sync_defmap(cl); 1129 cbq_sync_defmap(cl);
1159 } 1130 }
1160 1131
1161 static void cbq_unlink_class(struct cbq_class 1132 static void cbq_unlink_class(struct cbq_class *this)
1162 { 1133 {
1163 struct cbq_class *cl, **clp; 1134 struct cbq_class *cl, **clp;
1164 struct cbq_sched_data *q = qdisc_priv 1135 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1165 1136
1166 for (clp = &q->classes[cbq_hash(this- !! 1137 qdisc_class_hash_remove(&q->clhash, &this->common);
1167 if (cl == this) { <<
1168 *clp = cl->next; <<
1169 cl->next = NULL; <<
1170 break; <<
1171 } <<
1172 } <<
1173 1138
1174 if (this->tparent) { 1139 if (this->tparent) {
1175 clp=&this->sibling; 1140 clp=&this->sibling;
1176 cl = *clp; 1141 cl = *clp;
1177 do { 1142 do {
1178 if (cl == this) { 1143 if (cl == this) {
1179 *clp = cl->si 1144 *clp = cl->sibling;
1180 break; 1145 break;
1181 } 1146 }
1182 clp = &cl->sibling; 1147 clp = &cl->sibling;
1183 } while ((cl = *clp) != this- 1148 } while ((cl = *clp) != this->sibling);
1184 1149
1185 if (this->tparent->children = 1150 if (this->tparent->children == this) {
1186 this->tparent->childr 1151 this->tparent->children = this->sibling;
1187 if (this->sibling == 1152 if (this->sibling == this)
1188 this->tparent 1153 this->tparent->children = NULL;
1189 } 1154 }
1190 } else { 1155 } else {
1191 BUG_TRAP(this->sibling == thi !! 1156 WARN_ON(this->sibling != this);
1192 } 1157 }
1193 } 1158 }
1194 1159
1195 static void cbq_link_class(struct cbq_class * 1160 static void cbq_link_class(struct cbq_class *this)
1196 { 1161 {
1197 struct cbq_sched_data *q = qdisc_priv 1162 struct cbq_sched_data *q = qdisc_priv(this->qdisc);
1198 unsigned h = cbq_hash(this->classid); <<
1199 struct cbq_class *parent = this->tpar 1163 struct cbq_class *parent = this->tparent;
1200 1164
1201 this->sibling = this; 1165 this->sibling = this;
1202 this->next = q->classes[h]; !! 1166 qdisc_class_hash_insert(&q->clhash, &this->common);
1203 q->classes[h] = this; <<
1204 1167
1205 if (parent == NULL) 1168 if (parent == NULL)
1206 return; 1169 return;
1207 1170
1208 if (parent->children == NULL) { 1171 if (parent->children == NULL) {
1209 parent->children = this; 1172 parent->children = this;
1210 } else { 1173 } else {
1211 this->sibling = parent->child 1174 this->sibling = parent->children->sibling;
1212 parent->children->sibling = t 1175 parent->children->sibling = this;
1213 } 1176 }
1214 } 1177 }
1215 1178
1216 static unsigned int cbq_drop(struct Qdisc* sc 1179 static unsigned int cbq_drop(struct Qdisc* sch)
1217 { 1180 {
1218 struct cbq_sched_data *q = qdisc_priv 1181 struct cbq_sched_data *q = qdisc_priv(sch);
1219 struct cbq_class *cl, *cl_head; 1182 struct cbq_class *cl, *cl_head;
1220 int prio; 1183 int prio;
1221 unsigned int len; 1184 unsigned int len;
1222 1185
1223 for (prio = TC_CBQ_MAXPRIO; prio >= 0 1186 for (prio = TC_CBQ_MAXPRIO; prio >= 0; prio--) {
1224 if ((cl_head = q->active[prio 1187 if ((cl_head = q->active[prio]) == NULL)
1225 continue; 1188 continue;
1226 1189
1227 cl = cl_head; 1190 cl = cl_head;
1228 do { 1191 do {
1229 if (cl->q->ops->drop 1192 if (cl->q->ops->drop && (len = cl->q->ops->drop(cl->q))) {
1230 sch->q.qlen-- 1193 sch->q.qlen--;
1231 if (!cl->q->q 1194 if (!cl->q->q.qlen)
1232 cbq_d 1195 cbq_deactivate_class(cl);
1233 return len; 1196 return len;
1234 } 1197 }
1235 } while ((cl = cl->next_alive 1198 } while ((cl = cl->next_alive) != cl_head);
1236 } 1199 }
1237 return 0; 1200 return 0;
1238 } 1201 }
1239 1202
1240 static void 1203 static void
1241 cbq_reset(struct Qdisc* sch) 1204 cbq_reset(struct Qdisc* sch)
1242 { 1205 {
1243 struct cbq_sched_data *q = qdisc_priv 1206 struct cbq_sched_data *q = qdisc_priv(sch);
1244 struct cbq_class *cl; 1207 struct cbq_class *cl;
>> 1208 struct hlist_node *n;
1245 int prio; 1209 int prio;
1246 unsigned h; 1210 unsigned h;
1247 1211
1248 q->activemask = 0; 1212 q->activemask = 0;
1249 q->pmask = 0; 1213 q->pmask = 0;
1250 q->tx_class = NULL; 1214 q->tx_class = NULL;
1251 q->tx_borrowed = NULL; 1215 q->tx_borrowed = NULL;
1252 qdisc_watchdog_cancel(&q->watchdog); 1216 qdisc_watchdog_cancel(&q->watchdog);
1253 hrtimer_cancel(&q->delay_timer); 1217 hrtimer_cancel(&q->delay_timer);
1254 q->toplevel = TC_CBQ_MAXLEVEL; 1218 q->toplevel = TC_CBQ_MAXLEVEL;
1255 q->now = psched_get_time(); 1219 q->now = psched_get_time();
1256 q->now_rt = q->now; 1220 q->now_rt = q->now;
1257 1221
1258 for (prio = 0; prio <= TC_CBQ_MAXPRIO 1222 for (prio = 0; prio <= TC_CBQ_MAXPRIO; prio++)
1259 q->active[prio] = NULL; 1223 q->active[prio] = NULL;
1260 1224
1261 for (h = 0; h < 16; h++) { !! 1225 for (h = 0; h < q->clhash.hashsize; h++) {
1262 for (cl = q->classes[h]; cl; !! 1226 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
1263 qdisc_reset(cl->q); 1227 qdisc_reset(cl->q);
1264 1228
1265 cl->next_alive = NULL 1229 cl->next_alive = NULL;
1266 cl->undertime = PSCHE 1230 cl->undertime = PSCHED_PASTPERFECT;
1267 cl->avgidle = cl->max 1231 cl->avgidle = cl->maxidle;
1268 cl->deficit = cl->qua 1232 cl->deficit = cl->quantum;
1269 cl->cpriority = cl->p 1233 cl->cpriority = cl->priority;
1270 } 1234 }
1271 } 1235 }
1272 sch->q.qlen = 0; 1236 sch->q.qlen = 0;
1273 } 1237 }
1274 1238
1275 1239
1276 static int cbq_set_lss(struct cbq_class *cl, 1240 static int cbq_set_lss(struct cbq_class *cl, struct tc_cbq_lssopt *lss)
1277 { 1241 {
1278 if (lss->change&TCF_CBQ_LSS_FLAGS) { 1242 if (lss->change&TCF_CBQ_LSS_FLAGS) {
1279 cl->share = (lss->flags&TCF_C 1243 cl->share = (lss->flags&TCF_CBQ_LSS_ISOLATED) ? NULL : cl->tparent;
1280 cl->borrow = (lss->flags&TCF_ 1244 cl->borrow = (lss->flags&TCF_CBQ_LSS_BOUNDED) ? NULL : cl->tparent;
1281 } 1245 }
1282 if (lss->change&TCF_CBQ_LSS_EWMA) 1246 if (lss->change&TCF_CBQ_LSS_EWMA)
1283 cl->ewma_log = lss->ewma_log; 1247 cl->ewma_log = lss->ewma_log;
1284 if (lss->change&TCF_CBQ_LSS_AVPKT) 1248 if (lss->change&TCF_CBQ_LSS_AVPKT)
1285 cl->avpkt = lss->avpkt; 1249 cl->avpkt = lss->avpkt;
1286 if (lss->change&TCF_CBQ_LSS_MINIDLE) 1250 if (lss->change&TCF_CBQ_LSS_MINIDLE)
1287 cl->minidle = -(long)lss->min 1251 cl->minidle = -(long)lss->minidle;
1288 if (lss->change&TCF_CBQ_LSS_MAXIDLE) 1252 if (lss->change&TCF_CBQ_LSS_MAXIDLE) {
1289 cl->maxidle = lss->maxidle; 1253 cl->maxidle = lss->maxidle;
1290 cl->avgidle = lss->maxidle; 1254 cl->avgidle = lss->maxidle;
1291 } 1255 }
1292 if (lss->change&TCF_CBQ_LSS_OFFTIME) 1256 if (lss->change&TCF_CBQ_LSS_OFFTIME)
1293 cl->offtime = lss->offtime; 1257 cl->offtime = lss->offtime;
1294 return 0; 1258 return 0;
1295 } 1259 }
1296 1260
1297 static void cbq_rmprio(struct cbq_sched_data 1261 static void cbq_rmprio(struct cbq_sched_data *q, struct cbq_class *cl)
1298 { 1262 {
1299 q->nclasses[cl->priority]--; 1263 q->nclasses[cl->priority]--;
1300 q->quanta[cl->priority] -= cl->weight 1264 q->quanta[cl->priority] -= cl->weight;
1301 cbq_normalize_quanta(q, cl->priority) 1265 cbq_normalize_quanta(q, cl->priority);
1302 } 1266 }
1303 1267
1304 static void cbq_addprio(struct cbq_sched_data 1268 static void cbq_addprio(struct cbq_sched_data *q, struct cbq_class *cl)
1305 { 1269 {
1306 q->nclasses[cl->priority]++; 1270 q->nclasses[cl->priority]++;
1307 q->quanta[cl->priority] += cl->weight 1271 q->quanta[cl->priority] += cl->weight;
1308 cbq_normalize_quanta(q, cl->priority) 1272 cbq_normalize_quanta(q, cl->priority);
1309 } 1273 }
1310 1274
1311 static int cbq_set_wrr(struct cbq_class *cl, 1275 static int cbq_set_wrr(struct cbq_class *cl, struct tc_cbq_wrropt *wrr)
1312 { 1276 {
1313 struct cbq_sched_data *q = qdisc_priv 1277 struct cbq_sched_data *q = qdisc_priv(cl->qdisc);
1314 1278
1315 if (wrr->allot) 1279 if (wrr->allot)
1316 cl->allot = wrr->allot; 1280 cl->allot = wrr->allot;
1317 if (wrr->weight) 1281 if (wrr->weight)
1318 cl->weight = wrr->weight; 1282 cl->weight = wrr->weight;
1319 if (wrr->priority) { 1283 if (wrr->priority) {
1320 cl->priority = wrr->priority- 1284 cl->priority = wrr->priority-1;
1321 cl->cpriority = cl->priority; 1285 cl->cpriority = cl->priority;
1322 if (cl->priority >= cl->prior 1286 if (cl->priority >= cl->priority2)
1323 cl->priority2 = TC_CB 1287 cl->priority2 = TC_CBQ_MAXPRIO-1;
1324 } 1288 }
1325 1289
1326 cbq_addprio(q, cl); 1290 cbq_addprio(q, cl);
1327 return 0; 1291 return 0;
1328 } 1292 }
1329 1293
1330 static int cbq_set_overlimit(struct cbq_class 1294 static int cbq_set_overlimit(struct cbq_class *cl, struct tc_cbq_ovl *ovl)
1331 { 1295 {
1332 switch (ovl->strategy) { 1296 switch (ovl->strategy) {
1333 case TC_CBQ_OVL_CLASSIC: 1297 case TC_CBQ_OVL_CLASSIC:
1334 cl->overlimit = cbq_ovl_class 1298 cl->overlimit = cbq_ovl_classic;
1335 break; 1299 break;
1336 case TC_CBQ_OVL_DELAY: 1300 case TC_CBQ_OVL_DELAY:
1337 cl->overlimit = cbq_ovl_delay 1301 cl->overlimit = cbq_ovl_delay;
1338 break; 1302 break;
1339 case TC_CBQ_OVL_LOWPRIO: 1303 case TC_CBQ_OVL_LOWPRIO:
1340 if (ovl->priority2-1 >= TC_CB 1304 if (ovl->priority2-1 >= TC_CBQ_MAXPRIO ||
1341 ovl->priority2-1 <= cl->p 1305 ovl->priority2-1 <= cl->priority)
1342 return -EINVAL; 1306 return -EINVAL;
1343 cl->priority2 = ovl->priority 1307 cl->priority2 = ovl->priority2-1;
1344 cl->overlimit = cbq_ovl_lowpr 1308 cl->overlimit = cbq_ovl_lowprio;
1345 break; 1309 break;
1346 case TC_CBQ_OVL_DROP: 1310 case TC_CBQ_OVL_DROP:
1347 cl->overlimit = cbq_ovl_drop; 1311 cl->overlimit = cbq_ovl_drop;
1348 break; 1312 break;
1349 case TC_CBQ_OVL_RCLASSIC: 1313 case TC_CBQ_OVL_RCLASSIC:
1350 cl->overlimit = cbq_ovl_rclas 1314 cl->overlimit = cbq_ovl_rclassic;
1351 break; 1315 break;
1352 default: 1316 default:
1353 return -EINVAL; 1317 return -EINVAL;
1354 } 1318 }
1355 cl->penalty = ovl->penalty; 1319 cl->penalty = ovl->penalty;
1356 return 0; 1320 return 0;
1357 } 1321 }
1358 1322
1359 #ifdef CONFIG_NET_CLS_ACT 1323 #ifdef CONFIG_NET_CLS_ACT
1360 static int cbq_set_police(struct cbq_class *c 1324 static int cbq_set_police(struct cbq_class *cl, struct tc_cbq_police *p)
1361 { 1325 {
1362 cl->police = p->police; 1326 cl->police = p->police;
1363 1327
1364 if (cl->q->handle) { 1328 if (cl->q->handle) {
1365 if (p->police == TC_POLICE_RE 1329 if (p->police == TC_POLICE_RECLASSIFY)
1366 cl->q->reshape_fail = 1330 cl->q->reshape_fail = cbq_reshape_fail;
1367 else 1331 else
1368 cl->q->reshape_fail = 1332 cl->q->reshape_fail = NULL;
1369 } 1333 }
1370 return 0; 1334 return 0;
1371 } 1335 }
1372 #endif 1336 #endif
1373 1337
1374 static int cbq_set_fopt(struct cbq_class *cl, 1338 static int cbq_set_fopt(struct cbq_class *cl, struct tc_cbq_fopt *fopt)
1375 { 1339 {
1376 cbq_change_defmap(cl, fopt->split, fo 1340 cbq_change_defmap(cl, fopt->split, fopt->defmap, fopt->defchange);
1377 return 0; 1341 return 0;
1378 } 1342 }
1379 1343
1380 static const struct nla_policy cbq_policy[TCA 1344 static const struct nla_policy cbq_policy[TCA_CBQ_MAX + 1] = {
1381 [TCA_CBQ_LSSOPT] = { .len = si 1345 [TCA_CBQ_LSSOPT] = { .len = sizeof(struct tc_cbq_lssopt) },
1382 [TCA_CBQ_WRROPT] = { .len = si 1346 [TCA_CBQ_WRROPT] = { .len = sizeof(struct tc_cbq_wrropt) },
1383 [TCA_CBQ_FOPT] = { .len = si 1347 [TCA_CBQ_FOPT] = { .len = sizeof(struct tc_cbq_fopt) },
1384 [TCA_CBQ_OVL_STRATEGY] = { .len = si 1348 [TCA_CBQ_OVL_STRATEGY] = { .len = sizeof(struct tc_cbq_ovl) },
1385 [TCA_CBQ_RATE] = { .len = si 1349 [TCA_CBQ_RATE] = { .len = sizeof(struct tc_ratespec) },
1386 [TCA_CBQ_RTAB] = { .type = N 1350 [TCA_CBQ_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1387 [TCA_CBQ_POLICE] = { .len = si 1351 [TCA_CBQ_POLICE] = { .len = sizeof(struct tc_cbq_police) },
1388 }; 1352 };
1389 1353
1390 static int cbq_init(struct Qdisc *sch, struct 1354 static int cbq_init(struct Qdisc *sch, struct nlattr *opt)
1391 { 1355 {
1392 struct cbq_sched_data *q = qdisc_priv 1356 struct cbq_sched_data *q = qdisc_priv(sch);
1393 struct nlattr *tb[TCA_CBQ_MAX + 1]; 1357 struct nlattr *tb[TCA_CBQ_MAX + 1];
1394 struct tc_ratespec *r; 1358 struct tc_ratespec *r;
1395 int err; 1359 int err;
1396 1360
1397 err = nla_parse_nested(tb, TCA_CBQ_MA 1361 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1398 if (err < 0) 1362 if (err < 0)
1399 return err; 1363 return err;
1400 1364
1401 if (tb[TCA_CBQ_RTAB] == NULL || tb[TC 1365 if (tb[TCA_CBQ_RTAB] == NULL || tb[TCA_CBQ_RATE] == NULL)
1402 return -EINVAL; 1366 return -EINVAL;
1403 1367
1404 r = nla_data(tb[TCA_CBQ_RATE]); 1368 r = nla_data(tb[TCA_CBQ_RATE]);
1405 1369
1406 if ((q->link.R_tab = qdisc_get_rtab(r 1370 if ((q->link.R_tab = qdisc_get_rtab(r, tb[TCA_CBQ_RTAB])) == NULL)
1407 return -EINVAL; 1371 return -EINVAL;
1408 1372
>> 1373 err = qdisc_class_hash_init(&q->clhash);
>> 1374 if (err < 0)
>> 1375 goto put_rtab;
>> 1376
1409 q->link.refcnt = 1; 1377 q->link.refcnt = 1;
1410 q->link.sibling = &q->link; 1378 q->link.sibling = &q->link;
1411 q->link.classid = sch->handle; !! 1379 q->link.common.classid = sch->handle;
1412 q->link.qdisc = sch; 1380 q->link.qdisc = sch;
1413 if (!(q->link.q = qdisc_create_dflt(s !! 1381 if (!(q->link.q = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
>> 1382 &pfifo_qdisc_ops,
1414 s 1383 sch->handle)))
1415 q->link.q = &noop_qdisc; 1384 q->link.q = &noop_qdisc;
1416 1385
1417 q->link.priority = TC_CBQ_MAXPRIO-1; 1386 q->link.priority = TC_CBQ_MAXPRIO-1;
1418 q->link.priority2 = TC_CBQ_MAXPRIO-1; 1387 q->link.priority2 = TC_CBQ_MAXPRIO-1;
1419 q->link.cpriority = TC_CBQ_MAXPRIO-1; 1388 q->link.cpriority = TC_CBQ_MAXPRIO-1;
1420 q->link.ovl_strategy = TC_CBQ_OVL_CLA 1389 q->link.ovl_strategy = TC_CBQ_OVL_CLASSIC;
1421 q->link.overlimit = cbq_ovl_classic; 1390 q->link.overlimit = cbq_ovl_classic;
1422 q->link.allot = psched_mtu(sch->dev); !! 1391 q->link.allot = psched_mtu(qdisc_dev(sch));
1423 q->link.quantum = q->link.allot; 1392 q->link.quantum = q->link.allot;
1424 q->link.weight = q->link.R_tab->rate. 1393 q->link.weight = q->link.R_tab->rate.rate;
1425 1394
1426 q->link.ewma_log = TC_CBQ_DEF_EWMA; 1395 q->link.ewma_log = TC_CBQ_DEF_EWMA;
1427 q->link.avpkt = q->link.allot/2; 1396 q->link.avpkt = q->link.allot/2;
1428 q->link.minidle = -0x7FFFFFFF; 1397 q->link.minidle = -0x7FFFFFFF;
1429 1398
1430 qdisc_watchdog_init(&q->watchdog, sch 1399 qdisc_watchdog_init(&q->watchdog, sch);
1431 hrtimer_init(&q->delay_timer, CLOCK_M 1400 hrtimer_init(&q->delay_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
1432 q->delay_timer.function = cbq_undelay 1401 q->delay_timer.function = cbq_undelay;
1433 q->toplevel = TC_CBQ_MAXLEVEL; 1402 q->toplevel = TC_CBQ_MAXLEVEL;
1434 q->now = psched_get_time(); 1403 q->now = psched_get_time();
1435 q->now_rt = q->now; 1404 q->now_rt = q->now;
1436 1405
1437 cbq_link_class(&q->link); 1406 cbq_link_class(&q->link);
1438 1407
1439 if (tb[TCA_CBQ_LSSOPT]) 1408 if (tb[TCA_CBQ_LSSOPT])
1440 cbq_set_lss(&q->link, nla_dat 1409 cbq_set_lss(&q->link, nla_data(tb[TCA_CBQ_LSSOPT]));
1441 1410
1442 cbq_addprio(q, &q->link); 1411 cbq_addprio(q, &q->link);
1443 return 0; 1412 return 0;
>> 1413
>> 1414 put_rtab:
>> 1415 qdisc_put_rtab(q->link.R_tab);
>> 1416 return err;
1444 } 1417 }
1445 1418
1446 static __inline__ int cbq_dump_rate(struct sk 1419 static __inline__ int cbq_dump_rate(struct sk_buff *skb, struct cbq_class *cl)
1447 { 1420 {
1448 unsigned char *b = skb_tail_pointer(s 1421 unsigned char *b = skb_tail_pointer(skb);
1449 1422
1450 NLA_PUT(skb, TCA_CBQ_RATE, sizeof(cl- 1423 NLA_PUT(skb, TCA_CBQ_RATE, sizeof(cl->R_tab->rate), &cl->R_tab->rate);
1451 return skb->len; 1424 return skb->len;
1452 1425
1453 nla_put_failure: 1426 nla_put_failure:
1454 nlmsg_trim(skb, b); 1427 nlmsg_trim(skb, b);
1455 return -1; 1428 return -1;
1456 } 1429 }
1457 1430
1458 static __inline__ int cbq_dump_lss(struct sk_ 1431 static __inline__ int cbq_dump_lss(struct sk_buff *skb, struct cbq_class *cl)
1459 { 1432 {
1460 unsigned char *b = skb_tail_pointer(s 1433 unsigned char *b = skb_tail_pointer(skb);
1461 struct tc_cbq_lssopt opt; 1434 struct tc_cbq_lssopt opt;
1462 1435
1463 opt.flags = 0; 1436 opt.flags = 0;
1464 if (cl->borrow == NULL) 1437 if (cl->borrow == NULL)
1465 opt.flags |= TCF_CBQ_LSS_BOUN 1438 opt.flags |= TCF_CBQ_LSS_BOUNDED;
1466 if (cl->share == NULL) 1439 if (cl->share == NULL)
1467 opt.flags |= TCF_CBQ_LSS_ISOL 1440 opt.flags |= TCF_CBQ_LSS_ISOLATED;
1468 opt.ewma_log = cl->ewma_log; 1441 opt.ewma_log = cl->ewma_log;
1469 opt.level = cl->level; 1442 opt.level = cl->level;
1470 opt.avpkt = cl->avpkt; 1443 opt.avpkt = cl->avpkt;
1471 opt.maxidle = cl->maxidle; 1444 opt.maxidle = cl->maxidle;
1472 opt.minidle = (u32)(-cl->minidle); 1445 opt.minidle = (u32)(-cl->minidle);
1473 opt.offtime = cl->offtime; 1446 opt.offtime = cl->offtime;
1474 opt.change = ~0; 1447 opt.change = ~0;
1475 NLA_PUT(skb, TCA_CBQ_LSSOPT, sizeof(o 1448 NLA_PUT(skb, TCA_CBQ_LSSOPT, sizeof(opt), &opt);
1476 return skb->len; 1449 return skb->len;
1477 1450
1478 nla_put_failure: 1451 nla_put_failure:
1479 nlmsg_trim(skb, b); 1452 nlmsg_trim(skb, b);
1480 return -1; 1453 return -1;
1481 } 1454 }
1482 1455
1483 static __inline__ int cbq_dump_wrr(struct sk_ 1456 static __inline__ int cbq_dump_wrr(struct sk_buff *skb, struct cbq_class *cl)
1484 { 1457 {
1485 unsigned char *b = skb_tail_pointer(s 1458 unsigned char *b = skb_tail_pointer(skb);
1486 struct tc_cbq_wrropt opt; 1459 struct tc_cbq_wrropt opt;
1487 1460
1488 opt.flags = 0; 1461 opt.flags = 0;
1489 opt.allot = cl->allot; 1462 opt.allot = cl->allot;
1490 opt.priority = cl->priority+1; 1463 opt.priority = cl->priority+1;
1491 opt.cpriority = cl->cpriority+1; 1464 opt.cpriority = cl->cpriority+1;
1492 opt.weight = cl->weight; 1465 opt.weight = cl->weight;
1493 NLA_PUT(skb, TCA_CBQ_WRROPT, sizeof(o 1466 NLA_PUT(skb, TCA_CBQ_WRROPT, sizeof(opt), &opt);
1494 return skb->len; 1467 return skb->len;
1495 1468
1496 nla_put_failure: 1469 nla_put_failure:
1497 nlmsg_trim(skb, b); 1470 nlmsg_trim(skb, b);
1498 return -1; 1471 return -1;
1499 } 1472 }
1500 1473
1501 static __inline__ int cbq_dump_ovl(struct sk_ 1474 static __inline__ int cbq_dump_ovl(struct sk_buff *skb, struct cbq_class *cl)
1502 { 1475 {
1503 unsigned char *b = skb_tail_pointer(s 1476 unsigned char *b = skb_tail_pointer(skb);
1504 struct tc_cbq_ovl opt; 1477 struct tc_cbq_ovl opt;
1505 1478
1506 opt.strategy = cl->ovl_strategy; 1479 opt.strategy = cl->ovl_strategy;
1507 opt.priority2 = cl->priority2+1; 1480 opt.priority2 = cl->priority2+1;
1508 opt.pad = 0; 1481 opt.pad = 0;
1509 opt.penalty = cl->penalty; 1482 opt.penalty = cl->penalty;
1510 NLA_PUT(skb, TCA_CBQ_OVL_STRATEGY, si 1483 NLA_PUT(skb, TCA_CBQ_OVL_STRATEGY, sizeof(opt), &opt);
1511 return skb->len; 1484 return skb->len;
1512 1485
1513 nla_put_failure: 1486 nla_put_failure:
1514 nlmsg_trim(skb, b); 1487 nlmsg_trim(skb, b);
1515 return -1; 1488 return -1;
1516 } 1489 }
1517 1490
1518 static __inline__ int cbq_dump_fopt(struct sk 1491 static __inline__ int cbq_dump_fopt(struct sk_buff *skb, struct cbq_class *cl)
1519 { 1492 {
1520 unsigned char *b = skb_tail_pointer(s 1493 unsigned char *b = skb_tail_pointer(skb);
1521 struct tc_cbq_fopt opt; 1494 struct tc_cbq_fopt opt;
1522 1495
1523 if (cl->split || cl->defmap) { 1496 if (cl->split || cl->defmap) {
1524 opt.split = cl->split ? cl->s !! 1497 opt.split = cl->split ? cl->split->common.classid : 0;
1525 opt.defmap = cl->defmap; 1498 opt.defmap = cl->defmap;
1526 opt.defchange = ~0; 1499 opt.defchange = ~0;
1527 NLA_PUT(skb, TCA_CBQ_FOPT, si 1500 NLA_PUT(skb, TCA_CBQ_FOPT, sizeof(opt), &opt);
1528 } 1501 }
1529 return skb->len; 1502 return skb->len;
1530 1503
1531 nla_put_failure: 1504 nla_put_failure:
1532 nlmsg_trim(skb, b); 1505 nlmsg_trim(skb, b);
1533 return -1; 1506 return -1;
1534 } 1507 }
1535 1508
1536 #ifdef CONFIG_NET_CLS_ACT 1509 #ifdef CONFIG_NET_CLS_ACT
1537 static __inline__ int cbq_dump_police(struct 1510 static __inline__ int cbq_dump_police(struct sk_buff *skb, struct cbq_class *cl)
1538 { 1511 {
1539 unsigned char *b = skb_tail_pointer(s 1512 unsigned char *b = skb_tail_pointer(skb);
1540 struct tc_cbq_police opt; 1513 struct tc_cbq_police opt;
1541 1514
1542 if (cl->police) { 1515 if (cl->police) {
1543 opt.police = cl->police; 1516 opt.police = cl->police;
1544 opt.__res1 = 0; 1517 opt.__res1 = 0;
1545 opt.__res2 = 0; 1518 opt.__res2 = 0;
1546 NLA_PUT(skb, TCA_CBQ_POLICE, 1519 NLA_PUT(skb, TCA_CBQ_POLICE, sizeof(opt), &opt);
1547 } 1520 }
1548 return skb->len; 1521 return skb->len;
1549 1522
1550 nla_put_failure: 1523 nla_put_failure:
1551 nlmsg_trim(skb, b); 1524 nlmsg_trim(skb, b);
1552 return -1; 1525 return -1;
1553 } 1526 }
1554 #endif 1527 #endif
1555 1528
1556 static int cbq_dump_attr(struct sk_buff *skb, 1529 static int cbq_dump_attr(struct sk_buff *skb, struct cbq_class *cl)
1557 { 1530 {
1558 if (cbq_dump_lss(skb, cl) < 0 || 1531 if (cbq_dump_lss(skb, cl) < 0 ||
1559 cbq_dump_rate(skb, cl) < 0 || 1532 cbq_dump_rate(skb, cl) < 0 ||
1560 cbq_dump_wrr(skb, cl) < 0 || 1533 cbq_dump_wrr(skb, cl) < 0 ||
1561 cbq_dump_ovl(skb, cl) < 0 || 1534 cbq_dump_ovl(skb, cl) < 0 ||
1562 #ifdef CONFIG_NET_CLS_ACT 1535 #ifdef CONFIG_NET_CLS_ACT
1563 cbq_dump_police(skb, cl) < 0 || 1536 cbq_dump_police(skb, cl) < 0 ||
1564 #endif 1537 #endif
1565 cbq_dump_fopt(skb, cl) < 0) 1538 cbq_dump_fopt(skb, cl) < 0)
1566 return -1; 1539 return -1;
1567 return 0; 1540 return 0;
1568 } 1541 }
1569 1542
1570 static int cbq_dump(struct Qdisc *sch, struct 1543 static int cbq_dump(struct Qdisc *sch, struct sk_buff *skb)
1571 { 1544 {
1572 struct cbq_sched_data *q = qdisc_priv 1545 struct cbq_sched_data *q = qdisc_priv(sch);
1573 struct nlattr *nest; 1546 struct nlattr *nest;
1574 1547
1575 nest = nla_nest_start(skb, TCA_OPTION 1548 nest = nla_nest_start(skb, TCA_OPTIONS);
1576 if (nest == NULL) 1549 if (nest == NULL)
1577 goto nla_put_failure; 1550 goto nla_put_failure;
1578 if (cbq_dump_attr(skb, &q->link) < 0) 1551 if (cbq_dump_attr(skb, &q->link) < 0)
1579 goto nla_put_failure; 1552 goto nla_put_failure;
1580 nla_nest_end(skb, nest); 1553 nla_nest_end(skb, nest);
1581 return skb->len; 1554 return skb->len;
1582 1555
1583 nla_put_failure: 1556 nla_put_failure:
1584 nla_nest_cancel(skb, nest); 1557 nla_nest_cancel(skb, nest);
1585 return -1; 1558 return -1;
1586 } 1559 }
1587 1560
1588 static int 1561 static int
1589 cbq_dump_stats(struct Qdisc *sch, struct gnet 1562 cbq_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
1590 { 1563 {
1591 struct cbq_sched_data *q = qdisc_priv 1564 struct cbq_sched_data *q = qdisc_priv(sch);
1592 1565
1593 q->link.xstats.avgidle = q->link.avgi 1566 q->link.xstats.avgidle = q->link.avgidle;
1594 return gnet_stats_copy_app(d, &q->lin 1567 return gnet_stats_copy_app(d, &q->link.xstats, sizeof(q->link.xstats));
1595 } 1568 }
1596 1569
1597 static int 1570 static int
1598 cbq_dump_class(struct Qdisc *sch, unsigned lo 1571 cbq_dump_class(struct Qdisc *sch, unsigned long arg,
1599 struct sk_buff *skb, struct tc 1572 struct sk_buff *skb, struct tcmsg *tcm)
1600 { 1573 {
1601 struct cbq_class *cl = (struct cbq_cl 1574 struct cbq_class *cl = (struct cbq_class*)arg;
1602 struct nlattr *nest; 1575 struct nlattr *nest;
1603 1576
1604 if (cl->tparent) 1577 if (cl->tparent)
1605 tcm->tcm_parent = cl->tparent !! 1578 tcm->tcm_parent = cl->tparent->common.classid;
1606 else 1579 else
1607 tcm->tcm_parent = TC_H_ROOT; 1580 tcm->tcm_parent = TC_H_ROOT;
1608 tcm->tcm_handle = cl->classid; !! 1581 tcm->tcm_handle = cl->common.classid;
1609 tcm->tcm_info = cl->q->handle; 1582 tcm->tcm_info = cl->q->handle;
1610 1583
1611 nest = nla_nest_start(skb, TCA_OPTION 1584 nest = nla_nest_start(skb, TCA_OPTIONS);
1612 if (nest == NULL) 1585 if (nest == NULL)
1613 goto nla_put_failure; 1586 goto nla_put_failure;
1614 if (cbq_dump_attr(skb, cl) < 0) 1587 if (cbq_dump_attr(skb, cl) < 0)
1615 goto nla_put_failure; 1588 goto nla_put_failure;
1616 nla_nest_end(skb, nest); 1589 nla_nest_end(skb, nest);
1617 return skb->len; 1590 return skb->len;
1618 1591
1619 nla_put_failure: 1592 nla_put_failure:
1620 nla_nest_cancel(skb, nest); 1593 nla_nest_cancel(skb, nest);
1621 return -1; 1594 return -1;
1622 } 1595 }
1623 1596
1624 static int 1597 static int
1625 cbq_dump_class_stats(struct Qdisc *sch, unsig 1598 cbq_dump_class_stats(struct Qdisc *sch, unsigned long arg,
1626 struct gnet_dump *d) 1599 struct gnet_dump *d)
1627 { 1600 {
1628 struct cbq_sched_data *q = qdisc_priv 1601 struct cbq_sched_data *q = qdisc_priv(sch);
1629 struct cbq_class *cl = (struct cbq_cl 1602 struct cbq_class *cl = (struct cbq_class*)arg;
1630 1603
1631 cl->qstats.qlen = cl->q->q.qlen; 1604 cl->qstats.qlen = cl->q->q.qlen;
1632 cl->xstats.avgidle = cl->avgidle; 1605 cl->xstats.avgidle = cl->avgidle;
1633 cl->xstats.undertime = 0; 1606 cl->xstats.undertime = 0;
1634 1607
1635 if (cl->undertime != PSCHED_PASTPERFE 1608 if (cl->undertime != PSCHED_PASTPERFECT)
1636 cl->xstats.undertime = cl->un 1609 cl->xstats.undertime = cl->undertime - q->now;
1637 1610
1638 if (gnet_stats_copy_basic(d, &cl->bst 1611 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1639 gnet_stats_copy_rate_est(d, &cl-> 1612 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1640 gnet_stats_copy_queue(d, &cl->qst 1613 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1641 return -1; 1614 return -1;
1642 1615
1643 return gnet_stats_copy_app(d, &cl->xs 1616 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1644 } 1617 }
1645 1618
1646 static int cbq_graft(struct Qdisc *sch, unsig 1619 static int cbq_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
1647 struct Qdisc **old) 1620 struct Qdisc **old)
1648 { 1621 {
1649 struct cbq_class *cl = (struct cbq_cl 1622 struct cbq_class *cl = (struct cbq_class*)arg;
1650 1623
1651 if (cl) { 1624 if (cl) {
1652 if (new == NULL) { 1625 if (new == NULL) {
1653 if ((new = qdisc_crea !! 1626 new = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
1654 !! 1627 &pfifo_qdisc_ops,
>> 1628 cl->common.classid);
>> 1629 if (new == NULL)
1655 return -ENOBU 1630 return -ENOBUFS;
1656 } else { 1631 } else {
1657 #ifdef CONFIG_NET_CLS_ACT 1632 #ifdef CONFIG_NET_CLS_ACT
1658 if (cl->police == TC_ 1633 if (cl->police == TC_POLICE_RECLASSIFY)
1659 new->reshape_ 1634 new->reshape_fail = cbq_reshape_fail;
1660 #endif 1635 #endif
1661 } 1636 }
1662 sch_tree_lock(sch); 1637 sch_tree_lock(sch);
1663 *old = xchg(&cl->q, new); !! 1638 *old = cl->q;
>> 1639 cl->q = new;
1664 qdisc_tree_decrease_qlen(*old 1640 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1665 qdisc_reset(*old); 1641 qdisc_reset(*old);
1666 sch_tree_unlock(sch); 1642 sch_tree_unlock(sch);
1667 1643
1668 return 0; 1644 return 0;
1669 } 1645 }
1670 return -ENOENT; 1646 return -ENOENT;
1671 } 1647 }
1672 1648
1673 static struct Qdisc * 1649 static struct Qdisc *
1674 cbq_leaf(struct Qdisc *sch, unsigned long arg 1650 cbq_leaf(struct Qdisc *sch, unsigned long arg)
1675 { 1651 {
1676 struct cbq_class *cl = (struct cbq_cl 1652 struct cbq_class *cl = (struct cbq_class*)arg;
1677 1653
1678 return cl ? cl->q : NULL; 1654 return cl ? cl->q : NULL;
1679 } 1655 }
1680 1656
1681 static void cbq_qlen_notify(struct Qdisc *sch 1657 static void cbq_qlen_notify(struct Qdisc *sch, unsigned long arg)
1682 { 1658 {
1683 struct cbq_class *cl = (struct cbq_cl 1659 struct cbq_class *cl = (struct cbq_class *)arg;
1684 1660
1685 if (cl->q->q.qlen == 0) 1661 if (cl->q->q.qlen == 0)
1686 cbq_deactivate_class(cl); 1662 cbq_deactivate_class(cl);
1687 } 1663 }
1688 1664
1689 static unsigned long cbq_get(struct Qdisc *sc 1665 static unsigned long cbq_get(struct Qdisc *sch, u32 classid)
1690 { 1666 {
1691 struct cbq_sched_data *q = qdisc_priv 1667 struct cbq_sched_data *q = qdisc_priv(sch);
1692 struct cbq_class *cl = cbq_class_look 1668 struct cbq_class *cl = cbq_class_lookup(q, classid);
1693 1669
1694 if (cl) { 1670 if (cl) {
1695 cl->refcnt++; 1671 cl->refcnt++;
1696 return (unsigned long)cl; 1672 return (unsigned long)cl;
1697 } 1673 }
1698 return 0; 1674 return 0;
1699 } 1675 }
1700 1676
1701 static void cbq_destroy_class(struct Qdisc *s 1677 static void cbq_destroy_class(struct Qdisc *sch, struct cbq_class *cl)
1702 { 1678 {
1703 struct cbq_sched_data *q = qdisc_priv 1679 struct cbq_sched_data *q = qdisc_priv(sch);
1704 1680
1705 BUG_TRAP(!cl->filters); !! 1681 WARN_ON(cl->filters);
1706 1682
1707 tcf_destroy_chain(cl->filter_list); !! 1683 tcf_destroy_chain(&cl->filter_list);
1708 qdisc_destroy(cl->q); 1684 qdisc_destroy(cl->q);
1709 qdisc_put_rtab(cl->R_tab); 1685 qdisc_put_rtab(cl->R_tab);
1710 gen_kill_estimator(&cl->bstats, &cl-> 1686 gen_kill_estimator(&cl->bstats, &cl->rate_est);
1711 if (cl != &q->link) 1687 if (cl != &q->link)
1712 kfree(cl); 1688 kfree(cl);
1713 } 1689 }
1714 1690
1715 static void 1691 static void
1716 cbq_destroy(struct Qdisc* sch) 1692 cbq_destroy(struct Qdisc* sch)
1717 { 1693 {
1718 struct cbq_sched_data *q = qdisc_priv 1694 struct cbq_sched_data *q = qdisc_priv(sch);
>> 1695 struct hlist_node *n, *next;
1719 struct cbq_class *cl; 1696 struct cbq_class *cl;
1720 unsigned h; 1697 unsigned h;
1721 1698
1722 #ifdef CONFIG_NET_CLS_ACT 1699 #ifdef CONFIG_NET_CLS_ACT
1723 q->rx_class = NULL; 1700 q->rx_class = NULL;
1724 #endif 1701 #endif
1725 /* 1702 /*
1726 * Filters must be destroyed first be 1703 * Filters must be destroyed first because we don't destroy the
1727 * classes from root to leafs which m 1704 * classes from root to leafs which means that filters can still
1728 * be bound to classes which have bee 1705 * be bound to classes which have been destroyed already. --TGR '04
1729 */ 1706 */
1730 for (h = 0; h < 16; h++) { !! 1707 for (h = 0; h < q->clhash.hashsize; h++) {
1731 for (cl = q->classes[h]; cl; !! 1708 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode)
1732 tcf_destroy_chain(cl- !! 1709 tcf_destroy_chain(&cl->filter_list);
1733 cl->filter_list = NUL !! 1710 }
1734 } !! 1711 for (h = 0; h < q->clhash.hashsize; h++) {
1735 } !! 1712 hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[h],
1736 for (h = 0; h < 16; h++) { !! 1713 common.hnode)
1737 struct cbq_class *next; <<
1738 <<
1739 for (cl = q->classes[h]; cl; <<
1740 next = cl->next; <<
1741 cbq_destroy_class(sch 1714 cbq_destroy_class(sch, cl);
1742 } <<
1743 } 1715 }
>> 1716 qdisc_class_hash_destroy(&q->clhash);
1744 } 1717 }
1745 1718
1746 static void cbq_put(struct Qdisc *sch, unsign 1719 static void cbq_put(struct Qdisc *sch, unsigned long arg)
1747 { 1720 {
1748 struct cbq_class *cl = (struct cbq_cl 1721 struct cbq_class *cl = (struct cbq_class*)arg;
1749 1722
1750 if (--cl->refcnt == 0) { 1723 if (--cl->refcnt == 0) {
1751 #ifdef CONFIG_NET_CLS_ACT 1724 #ifdef CONFIG_NET_CLS_ACT
>> 1725 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
1752 struct cbq_sched_data *q = qd 1726 struct cbq_sched_data *q = qdisc_priv(sch);
1753 1727
1754 spin_lock_bh(&sch->dev->queue !! 1728 spin_lock_bh(root_lock);
1755 if (q->rx_class == cl) 1729 if (q->rx_class == cl)
1756 q->rx_class = NULL; 1730 q->rx_class = NULL;
1757 spin_unlock_bh(&sch->dev->que !! 1731 spin_unlock_bh(root_lock);
1758 #endif 1732 #endif
1759 1733
1760 cbq_destroy_class(sch, cl); 1734 cbq_destroy_class(sch, cl);
1761 } 1735 }
1762 } 1736 }
1763 1737
1764 static int 1738 static int
1765 cbq_change_class(struct Qdisc *sch, u32 class 1739 cbq_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca,
1766 unsigned long *arg) 1740 unsigned long *arg)
1767 { 1741 {
1768 int err; 1742 int err;
1769 struct cbq_sched_data *q = qdisc_priv 1743 struct cbq_sched_data *q = qdisc_priv(sch);
1770 struct cbq_class *cl = (struct cbq_cl 1744 struct cbq_class *cl = (struct cbq_class*)*arg;
1771 struct nlattr *opt = tca[TCA_OPTIONS] 1745 struct nlattr *opt = tca[TCA_OPTIONS];
1772 struct nlattr *tb[TCA_CBQ_MAX + 1]; 1746 struct nlattr *tb[TCA_CBQ_MAX + 1];
1773 struct cbq_class *parent; 1747 struct cbq_class *parent;
1774 struct qdisc_rate_table *rtab = NULL; 1748 struct qdisc_rate_table *rtab = NULL;
1775 1749
1776 if (opt == NULL) 1750 if (opt == NULL)
1777 return -EINVAL; 1751 return -EINVAL;
1778 1752
1779 err = nla_parse_nested(tb, TCA_CBQ_MA 1753 err = nla_parse_nested(tb, TCA_CBQ_MAX, opt, cbq_policy);
1780 if (err < 0) 1754 if (err < 0)
1781 return err; 1755 return err;
1782 1756
1783 if (cl) { 1757 if (cl) {
1784 /* Check parent */ 1758 /* Check parent */
1785 if (parentid) { 1759 if (parentid) {
1786 if (cl->tparent && cl !! 1760 if (cl->tparent &&
>> 1761 cl->tparent->common.classid != parentid)
1787 return -EINVA 1762 return -EINVAL;
1788 if (!cl->tparent && p 1763 if (!cl->tparent && parentid != TC_H_ROOT)
1789 return -EINVA 1764 return -EINVAL;
1790 } 1765 }
1791 1766
1792 if (tb[TCA_CBQ_RATE]) { 1767 if (tb[TCA_CBQ_RATE]) {
1793 rtab = qdisc_get_rtab !! 1768 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]),
>> 1769 tb[TCA_CBQ_RTAB]);
1794 if (rtab == NULL) 1770 if (rtab == NULL)
1795 return -EINVA 1771 return -EINVAL;
1796 } 1772 }
1797 1773
>> 1774 if (tca[TCA_RATE]) {
>> 1775 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
>> 1776 qdisc_root_sleeping_lock(sch),
>> 1777 tca[TCA_RATE]);
>> 1778 if (err) {
>> 1779 if (rtab)
>> 1780 qdisc_put_rtab(rtab);
>> 1781 return err;
>> 1782 }
>> 1783 }
>> 1784
1798 /* Change class parameters */ 1785 /* Change class parameters */
1799 sch_tree_lock(sch); 1786 sch_tree_lock(sch);
1800 1787
1801 if (cl->next_alive != NULL) 1788 if (cl->next_alive != NULL)
1802 cbq_deactivate_class( 1789 cbq_deactivate_class(cl);
1803 1790
1804 if (rtab) { 1791 if (rtab) {
1805 rtab = xchg(&cl->R_ta !! 1792 qdisc_put_rtab(cl->R_tab);
1806 qdisc_put_rtab(rtab); !! 1793 cl->R_tab = rtab;
1807 } 1794 }
1808 1795
1809 if (tb[TCA_CBQ_LSSOPT]) 1796 if (tb[TCA_CBQ_LSSOPT])
1810 cbq_set_lss(cl, nla_d 1797 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1811 1798
1812 if (tb[TCA_CBQ_WRROPT]) { 1799 if (tb[TCA_CBQ_WRROPT]) {
1813 cbq_rmprio(q, cl); 1800 cbq_rmprio(q, cl);
1814 cbq_set_wrr(cl, nla_d 1801 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1815 } 1802 }
1816 1803
1817 if (tb[TCA_CBQ_OVL_STRATEGY]) 1804 if (tb[TCA_CBQ_OVL_STRATEGY])
1818 cbq_set_overlimit(cl, 1805 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1819 1806
1820 #ifdef CONFIG_NET_CLS_ACT 1807 #ifdef CONFIG_NET_CLS_ACT
1821 if (tb[TCA_CBQ_POLICE]) 1808 if (tb[TCA_CBQ_POLICE])
1822 cbq_set_police(cl, nl 1809 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1823 #endif 1810 #endif
1824 1811
1825 if (tb[TCA_CBQ_FOPT]) 1812 if (tb[TCA_CBQ_FOPT])
1826 cbq_set_fopt(cl, nla_ 1813 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1827 1814
1828 if (cl->q->q.qlen) 1815 if (cl->q->q.qlen)
1829 cbq_activate_class(cl 1816 cbq_activate_class(cl);
1830 1817
1831 sch_tree_unlock(sch); 1818 sch_tree_unlock(sch);
1832 1819
1833 if (tca[TCA_RATE]) <<
1834 gen_replace_estimator <<
1835 <<
1836 <<
1837 return 0; 1820 return 0;
1838 } 1821 }
1839 1822
1840 if (parentid == TC_H_ROOT) 1823 if (parentid == TC_H_ROOT)
1841 return -EINVAL; 1824 return -EINVAL;
1842 1825
1843 if (tb[TCA_CBQ_WRROPT] == NULL || tb[ 1826 if (tb[TCA_CBQ_WRROPT] == NULL || tb[TCA_CBQ_RATE] == NULL ||
1844 tb[TCA_CBQ_LSSOPT] == NULL) 1827 tb[TCA_CBQ_LSSOPT] == NULL)
1845 return -EINVAL; 1828 return -EINVAL;
1846 1829
1847 rtab = qdisc_get_rtab(nla_data(tb[TCA 1830 rtab = qdisc_get_rtab(nla_data(tb[TCA_CBQ_RATE]), tb[TCA_CBQ_RTAB]);
1848 if (rtab == NULL) 1831 if (rtab == NULL)
1849 return -EINVAL; 1832 return -EINVAL;
1850 1833
1851 if (classid) { 1834 if (classid) {
1852 err = -EINVAL; 1835 err = -EINVAL;
1853 if (TC_H_MAJ(classid^sch->han 1836 if (TC_H_MAJ(classid^sch->handle) || cbq_class_lookup(q, classid))
1854 goto failure; 1837 goto failure;
1855 } else { 1838 } else {
1856 int i; 1839 int i;
1857 classid = TC_H_MAKE(sch->hand 1840 classid = TC_H_MAKE(sch->handle,0x8000);
1858 1841
1859 for (i=0; i<0x8000; i++) { 1842 for (i=0; i<0x8000; i++) {
1860 if (++q->hgenerator > 1843 if (++q->hgenerator >= 0x8000)
1861 q->hgenerator 1844 q->hgenerator = 1;
1862 if (cbq_class_lookup( 1845 if (cbq_class_lookup(q, classid|q->hgenerator) == NULL)
1863 break; 1846 break;
1864 } 1847 }
1865 err = -ENOSR; 1848 err = -ENOSR;
1866 if (i >= 0x8000) 1849 if (i >= 0x8000)
1867 goto failure; 1850 goto failure;
1868 classid = classid|q->hgenerat 1851 classid = classid|q->hgenerator;
1869 } 1852 }
1870 1853
1871 parent = &q->link; 1854 parent = &q->link;
1872 if (parentid) { 1855 if (parentid) {
1873 parent = cbq_class_lookup(q, 1856 parent = cbq_class_lookup(q, parentid);
1874 err = -EINVAL; 1857 err = -EINVAL;
1875 if (parent == NULL) 1858 if (parent == NULL)
1876 goto failure; 1859 goto failure;
1877 } 1860 }
1878 1861
1879 err = -ENOBUFS; 1862 err = -ENOBUFS;
1880 cl = kzalloc(sizeof(*cl), GFP_KERNEL) 1863 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1881 if (cl == NULL) 1864 if (cl == NULL)
1882 goto failure; 1865 goto failure;
>> 1866
>> 1867 if (tca[TCA_RATE]) {
>> 1868 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
>> 1869 qdisc_root_sleeping_lock(sch),
>> 1870 tca[TCA_RATE]);
>> 1871 if (err) {
>> 1872 kfree(cl);
>> 1873 goto failure;
>> 1874 }
>> 1875 }
>> 1876
1883 cl->R_tab = rtab; 1877 cl->R_tab = rtab;
1884 rtab = NULL; 1878 rtab = NULL;
1885 cl->refcnt = 1; 1879 cl->refcnt = 1;
1886 if (!(cl->q = qdisc_create_dflt(sch-> !! 1880 if (!(cl->q = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
>> 1881 &pfifo_qdisc_ops, classid)))
1887 cl->q = &noop_qdisc; 1882 cl->q = &noop_qdisc;
1888 cl->classid = classid; !! 1883 cl->common.classid = classid;
1889 cl->tparent = parent; 1884 cl->tparent = parent;
1890 cl->qdisc = sch; 1885 cl->qdisc = sch;
1891 cl->allot = parent->allot; 1886 cl->allot = parent->allot;
1892 cl->quantum = cl->allot; 1887 cl->quantum = cl->allot;
1893 cl->weight = cl->R_tab->rate.rate; 1888 cl->weight = cl->R_tab->rate.rate;
1894 1889
1895 sch_tree_lock(sch); 1890 sch_tree_lock(sch);
1896 cbq_link_class(cl); 1891 cbq_link_class(cl);
1897 cl->borrow = cl->tparent; 1892 cl->borrow = cl->tparent;
1898 if (cl->tparent != &q->link) 1893 if (cl->tparent != &q->link)
1899 cl->share = cl->tparent; 1894 cl->share = cl->tparent;
1900 cbq_adjust_levels(parent); 1895 cbq_adjust_levels(parent);
1901 cl->minidle = -0x7FFFFFFF; 1896 cl->minidle = -0x7FFFFFFF;
1902 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_L 1897 cbq_set_lss(cl, nla_data(tb[TCA_CBQ_LSSOPT]));
1903 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_W 1898 cbq_set_wrr(cl, nla_data(tb[TCA_CBQ_WRROPT]));
1904 if (cl->ewma_log==0) 1899 if (cl->ewma_log==0)
1905 cl->ewma_log = q->link.ewma_l 1900 cl->ewma_log = q->link.ewma_log;
1906 if (cl->maxidle==0) 1901 if (cl->maxidle==0)
1907 cl->maxidle = q->link.maxidle 1902 cl->maxidle = q->link.maxidle;
1908 if (cl->avpkt==0) 1903 if (cl->avpkt==0)
1909 cl->avpkt = q->link.avpkt; 1904 cl->avpkt = q->link.avpkt;
1910 cl->overlimit = cbq_ovl_classic; 1905 cl->overlimit = cbq_ovl_classic;
1911 if (tb[TCA_CBQ_OVL_STRATEGY]) 1906 if (tb[TCA_CBQ_OVL_STRATEGY])
1912 cbq_set_overlimit(cl, nla_dat 1907 cbq_set_overlimit(cl, nla_data(tb[TCA_CBQ_OVL_STRATEGY]));
1913 #ifdef CONFIG_NET_CLS_ACT 1908 #ifdef CONFIG_NET_CLS_ACT
1914 if (tb[TCA_CBQ_POLICE]) 1909 if (tb[TCA_CBQ_POLICE])
1915 cbq_set_police(cl, nla_data(t 1910 cbq_set_police(cl, nla_data(tb[TCA_CBQ_POLICE]));
1916 #endif 1911 #endif
1917 if (tb[TCA_CBQ_FOPT]) 1912 if (tb[TCA_CBQ_FOPT])
1918 cbq_set_fopt(cl, nla_data(tb[ 1913 cbq_set_fopt(cl, nla_data(tb[TCA_CBQ_FOPT]));
1919 sch_tree_unlock(sch); 1914 sch_tree_unlock(sch);
1920 1915
1921 if (tca[TCA_RATE]) !! 1916 qdisc_class_hash_grow(sch, &q->clhash);
1922 gen_new_estimator(&cl->bstats <<
1923 &sch->dev-> <<
1924 1917
1925 *arg = (unsigned long)cl; 1918 *arg = (unsigned long)cl;
1926 return 0; 1919 return 0;
1927 1920
1928 failure: 1921 failure:
1929 qdisc_put_rtab(rtab); 1922 qdisc_put_rtab(rtab);
1930 return err; 1923 return err;
1931 } 1924 }
1932 1925
1933 static int cbq_delete(struct Qdisc *sch, unsi 1926 static int cbq_delete(struct Qdisc *sch, unsigned long arg)
1934 { 1927 {
1935 struct cbq_sched_data *q = qdisc_priv 1928 struct cbq_sched_data *q = qdisc_priv(sch);
1936 struct cbq_class *cl = (struct cbq_cl 1929 struct cbq_class *cl = (struct cbq_class*)arg;
1937 unsigned int qlen; 1930 unsigned int qlen;
1938 1931
1939 if (cl->filters || cl->children || cl 1932 if (cl->filters || cl->children || cl == &q->link)
1940 return -EBUSY; 1933 return -EBUSY;
1941 1934
1942 sch_tree_lock(sch); 1935 sch_tree_lock(sch);
1943 1936
1944 qlen = cl->q->q.qlen; 1937 qlen = cl->q->q.qlen;
1945 qdisc_reset(cl->q); 1938 qdisc_reset(cl->q);
1946 qdisc_tree_decrease_qlen(cl->q, qlen) 1939 qdisc_tree_decrease_qlen(cl->q, qlen);
1947 1940
1948 if (cl->next_alive) 1941 if (cl->next_alive)
1949 cbq_deactivate_class(cl); 1942 cbq_deactivate_class(cl);
1950 1943
1951 if (q->tx_borrowed == cl) 1944 if (q->tx_borrowed == cl)
1952 q->tx_borrowed = q->tx_class; 1945 q->tx_borrowed = q->tx_class;
1953 if (q->tx_class == cl) { 1946 if (q->tx_class == cl) {
1954 q->tx_class = NULL; 1947 q->tx_class = NULL;
1955 q->tx_borrowed = NULL; 1948 q->tx_borrowed = NULL;
1956 } 1949 }
1957 #ifdef CONFIG_NET_CLS_ACT 1950 #ifdef CONFIG_NET_CLS_ACT
1958 if (q->rx_class == cl) 1951 if (q->rx_class == cl)
1959 q->rx_class = NULL; 1952 q->rx_class = NULL;
1960 #endif 1953 #endif
1961 1954
1962 cbq_unlink_class(cl); 1955 cbq_unlink_class(cl);
1963 cbq_adjust_levels(cl->tparent); 1956 cbq_adjust_levels(cl->tparent);
1964 cl->defmap = 0; 1957 cl->defmap = 0;
1965 cbq_sync_defmap(cl); 1958 cbq_sync_defmap(cl);
1966 1959
1967 cbq_rmprio(q, cl); 1960 cbq_rmprio(q, cl);
1968 sch_tree_unlock(sch); 1961 sch_tree_unlock(sch);
1969 1962
1970 if (--cl->refcnt == 0) !! 1963 BUG_ON(--cl->refcnt == 0);
1971 cbq_destroy_class(sch, cl); !! 1964 /*
>> 1965 * This shouldn't happen: we "hold" one cops->get() when called
>> 1966 * from tc_ctl_tclass; the destroy method is done from cops->put().
>> 1967 */
1972 1968
1973 return 0; 1969 return 0;
1974 } 1970 }
1975 1971
1976 static struct tcf_proto **cbq_find_tcf(struct 1972 static struct tcf_proto **cbq_find_tcf(struct Qdisc *sch, unsigned long arg)
1977 { 1973 {
1978 struct cbq_sched_data *q = qdisc_priv 1974 struct cbq_sched_data *q = qdisc_priv(sch);
1979 struct cbq_class *cl = (struct cbq_cl 1975 struct cbq_class *cl = (struct cbq_class *)arg;
1980 1976
1981 if (cl == NULL) 1977 if (cl == NULL)
1982 cl = &q->link; 1978 cl = &q->link;
1983 1979
1984 return &cl->filter_list; 1980 return &cl->filter_list;
1985 } 1981 }
1986 1982
1987 static unsigned long cbq_bind_filter(struct Q 1983 static unsigned long cbq_bind_filter(struct Qdisc *sch, unsigned long parent,
1988 u32 clas 1984 u32 classid)
1989 { 1985 {
1990 struct cbq_sched_data *q = qdisc_priv 1986 struct cbq_sched_data *q = qdisc_priv(sch);
1991 struct cbq_class *p = (struct cbq_cla 1987 struct cbq_class *p = (struct cbq_class*)parent;
1992 struct cbq_class *cl = cbq_class_look 1988 struct cbq_class *cl = cbq_class_lookup(q, classid);
1993 1989
1994 if (cl) { 1990 if (cl) {
1995 if (p && p->level <= cl->leve 1991 if (p && p->level <= cl->level)
1996 return 0; 1992 return 0;
1997 cl->filters++; 1993 cl->filters++;
1998 return (unsigned long)cl; 1994 return (unsigned long)cl;
1999 } 1995 }
2000 return 0; 1996 return 0;
2001 } 1997 }
2002 1998
2003 static void cbq_unbind_filter(struct Qdisc *s 1999 static void cbq_unbind_filter(struct Qdisc *sch, unsigned long arg)
2004 { 2000 {
2005 struct cbq_class *cl = (struct cbq_cl 2001 struct cbq_class *cl = (struct cbq_class*)arg;
2006 2002
2007 cl->filters--; 2003 cl->filters--;
2008 } 2004 }
2009 2005
2010 static void cbq_walk(struct Qdisc *sch, struc 2006 static void cbq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
2011 { 2007 {
2012 struct cbq_sched_data *q = qdisc_priv 2008 struct cbq_sched_data *q = qdisc_priv(sch);
>> 2009 struct cbq_class *cl;
>> 2010 struct hlist_node *n;
2013 unsigned h; 2011 unsigned h;
2014 2012
2015 if (arg->stop) 2013 if (arg->stop)
2016 return; 2014 return;
2017 2015
2018 for (h = 0; h < 16; h++) { !! 2016 for (h = 0; h < q->clhash.hashsize; h++) {
2019 struct cbq_class *cl; !! 2017 hlist_for_each_entry(cl, n, &q->clhash.hash[h], common.hnode) {
2020 <<
2021 for (cl = q->classes[h]; cl; <<
2022 if (arg->count < arg- 2018 if (arg->count < arg->skip) {
2023 arg->count++; 2019 arg->count++;
2024 continue; 2020 continue;
2025 } 2021 }
2026 if (arg->fn(sch, (uns 2022 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
2027 arg->stop = 1 2023 arg->stop = 1;
2028 return; 2024 return;
2029 } 2025 }
2030 arg->count++; 2026 arg->count++;
2031 } 2027 }
2032 } 2028 }
2033 } 2029 }
2034 2030
2035 static const struct Qdisc_class_ops cbq_class 2031 static const struct Qdisc_class_ops cbq_class_ops = {
2036 .graft = cbq_graft, 2032 .graft = cbq_graft,
2037 .leaf = cbq_leaf, 2033 .leaf = cbq_leaf,
2038 .qlen_notify = cbq_qlen_noti 2034 .qlen_notify = cbq_qlen_notify,
2039 .get = cbq_get, 2035 .get = cbq_get,
2040 .put = cbq_put, 2036 .put = cbq_put,
2041 .change = cbq_change_cl 2037 .change = cbq_change_class,
2042 .delete = cbq_delete, 2038 .delete = cbq_delete,
2043 .walk = cbq_walk, 2039 .walk = cbq_walk,
2044 .tcf_chain = cbq_find_tcf, 2040 .tcf_chain = cbq_find_tcf,
2045 .bind_tcf = cbq_bind_filt 2041 .bind_tcf = cbq_bind_filter,
2046 .unbind_tcf = cbq_unbind_fi 2042 .unbind_tcf = cbq_unbind_filter,
2047 .dump = cbq_dump_clas 2043 .dump = cbq_dump_class,
2048 .dump_stats = cbq_dump_clas 2044 .dump_stats = cbq_dump_class_stats,
2049 }; 2045 };
2050 2046
2051 static struct Qdisc_ops cbq_qdisc_ops __read_ 2047 static struct Qdisc_ops cbq_qdisc_ops __read_mostly = {
2052 .next = NULL, 2048 .next = NULL,
2053 .cl_ops = &cbq_class_op 2049 .cl_ops = &cbq_class_ops,
2054 .id = "cbq", 2050 .id = "cbq",
2055 .priv_size = sizeof(struct 2051 .priv_size = sizeof(struct cbq_sched_data),
2056 .enqueue = cbq_enqueue, 2052 .enqueue = cbq_enqueue,
2057 .dequeue = cbq_dequeue, 2053 .dequeue = cbq_dequeue,
2058 .requeue = cbq_requeue, !! 2054 .peek = qdisc_peek_dequeued,
2059 .drop = cbq_drop, 2055 .drop = cbq_drop,
2060 .init = cbq_init, 2056 .init = cbq_init,
2061 .reset = cbq_reset, 2057 .reset = cbq_reset,
2062 .destroy = cbq_destroy, 2058 .destroy = cbq_destroy,
2063 .change = NULL, 2059 .change = NULL,
2064 .dump = cbq_dump, 2060 .dump = cbq_dump,
2065 .dump_stats = cbq_dump_stat 2061 .dump_stats = cbq_dump_stats,
2066 .owner = THIS_MODULE, 2062 .owner = THIS_MODULE,
2067 }; 2063 };
2068 2064
2069 static int __init cbq_module_init(void) 2065 static int __init cbq_module_init(void)
2070 { 2066 {
2071 return register_qdisc(&cbq_qdisc_ops) 2067 return register_qdisc(&cbq_qdisc_ops);
2072 } 2068 }
2073 static void __exit cbq_module_exit(void) 2069 static void __exit cbq_module_exit(void)
2074 { 2070 {
2075 unregister_qdisc(&cbq_qdisc_ops); 2071 unregister_qdisc(&cbq_qdisc_ops);
2076 } 2072 }
2077 module_init(cbq_module_init) 2073 module_init(cbq_module_init)
2078 module_exit(cbq_module_exit) 2074 module_exit(cbq_module_exit)
2079 MODULE_LICENSE("GPL"); 2075 MODULE_LICENSE("GPL");
2080 2076
|
This page was automatically generated by the
LXR engine.
|