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