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