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