blob: 9d75b7761313c5789ca51fb47d5f0fe49fec6966 [file] [log] [blame]
Stephen Hemminger87990462006-08-10 23:35:16 -07001/*
Linus Torvalds1da177e2005-04-16 15:20:36 -07002 * net/sched/sch_htb.c Hierarchical token bucket, feed tree version
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 *
9 * Authors: Martin Devera, <devik@cdi.cz>
10 *
11 * Credits (in time order) for older HTB versions:
12 * Stef Coene <stef.coene@docum.org>
13 * HTB support at LARTC mailing list
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090014 * Ondrej Kraus, <krauso@barr.cz>
Linus Torvalds1da177e2005-04-16 15:20:36 -070015 * found missing INIT_QDISC(htb)
16 * Vladimir Smelhaus, Aamer Akhter, Bert Hubert
17 * helped a lot to locate nasty class stall bug
18 * Andi Kleen, Jamal Hadi, Bert Hubert
19 * code review and helpful comments on shaping
20 * Tomasz Wrona, <tw@eter.tym.pl>
21 * created test case so that I was able to fix nasty bug
22 * Wilfried Weissmann
23 * spotted bug in dequeue code and helped with fix
24 * Jiri Fojtasek
25 * fixed requeue routine
26 * and many others. thanks.
Linus Torvalds1da177e2005-04-16 15:20:36 -070027 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070028#include <linux/module.h>
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -070029#include <linux/moduleparam.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070030#include <linux/types.h>
31#include <linux/kernel.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070032#include <linux/string.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070033#include <linux/errno.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070034#include <linux/skbuff.h>
35#include <linux/list.h>
36#include <linux/compiler.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070037#include <linux/rbtree.h>
Jarek Poplawski12247362009-02-01 01:13:22 -080038#include <linux/workqueue.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090039#include <linux/slab.h>
Patrick McHardy0ba48052007-07-02 22:49:07 -070040#include <net/netlink.h>
41#include <net/pkt_sched.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070042
43/* HTB algorithm.
44 Author: devik@cdi.cz
45 ========================================================================
46 HTB is like TBF with multiple classes. It is also similar to CBQ because
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090047 it allows to assign priority to each class in hierarchy.
Linus Torvalds1da177e2005-04-16 15:20:36 -070048 In fact it is another implementation of Floyd's formal sharing.
49
50 Levels:
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090051 Each class is assigned level. Leaf has ALWAYS level 0 and root
Linus Torvalds1da177e2005-04-16 15:20:36 -070052 classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
53 one less than their parent.
54*/
55
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -070056static int htb_hysteresis __read_mostly = 0; /* whether to use mode hysteresis for speedup */
Stephen Hemminger87990462006-08-10 23:35:16 -070057#define HTB_VER 0x30011 /* major must be matched with number suplied by TC as version */
Linus Torvalds1da177e2005-04-16 15:20:36 -070058
59#if HTB_VER >> 16 != TC_HTB_PROTOVER
60#error "Mismatched sch_htb.c and pkt_sch.h"
61#endif
62
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -070063/* Module parameter and sysfs export */
64module_param (htb_hysteresis, int, 0640);
65MODULE_PARM_DESC(htb_hysteresis, "Hysteresis mode, less CPU load, less accurate");
66
Linus Torvalds1da177e2005-04-16 15:20:36 -070067/* used internaly to keep status of single class */
68enum htb_cmode {
Stephen Hemminger87990462006-08-10 23:35:16 -070069 HTB_CANT_SEND, /* class can't send and can't borrow */
70 HTB_MAY_BORROW, /* class can't send but may borrow */
71 HTB_CAN_SEND /* class can send */
Linus Torvalds1da177e2005-04-16 15:20:36 -070072};
73
74/* interior & leaf nodes; props specific to leaves are marked L: */
Stephen Hemminger87990462006-08-10 23:35:16 -070075struct htb_class {
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -070076 struct Qdisc_class_common common;
Stephen Hemminger87990462006-08-10 23:35:16 -070077 /* general class parameters */
Eric Dumazetc1a8f1f2009-08-16 09:36:49 +000078 struct gnet_stats_basic_packed bstats;
Stephen Hemminger87990462006-08-10 23:35:16 -070079 struct gnet_stats_queue qstats;
80 struct gnet_stats_rate_est rate_est;
81 struct tc_htb_xstats xstats; /* our special stats */
82 int refcnt; /* usage count of this class */
Linus Torvalds1da177e2005-04-16 15:20:36 -070083
Stephen Hemminger87990462006-08-10 23:35:16 -070084 /* topology */
85 int level; /* our level (see above) */
Patrick McHardy42077592008-07-05 23:22:53 -070086 unsigned int children;
Stephen Hemminger87990462006-08-10 23:35:16 -070087 struct htb_class *parent; /* parent class */
Linus Torvalds1da177e2005-04-16 15:20:36 -070088
Jarek Poplawskic19f7a32008-12-03 21:09:45 -080089 int prio; /* these two are used only by leaves... */
90 int quantum; /* but stored for parent-to-leaf return */
91
Stephen Hemminger87990462006-08-10 23:35:16 -070092 union {
93 struct htb_class_leaf {
94 struct Qdisc *q;
Stephen Hemminger87990462006-08-10 23:35:16 -070095 int deficit[TC_HTB_MAXDEPTH];
96 struct list_head drop_list;
97 } leaf;
98 struct htb_class_inner {
99 struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */
100 struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class ptr */
101 /* When class changes from state 1->2 and disconnects from
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000102 * parent's feed then we lost ptr value and start from the
103 * first child again. Here we store classid of the
104 * last valid ptr (used when ptr is NULL).
105 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700106 u32 last_ptr_id[TC_HTB_NUMPRIO];
107 } inner;
108 } un;
109 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
110 struct rb_node pq_node; /* node for event queue */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700111 psched_time_t pq_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700112
Stephen Hemminger87990462006-08-10 23:35:16 -0700113 int prio_activity; /* for which prios are we active */
114 enum htb_cmode cmode; /* current mode of the class */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700115
Stephen Hemminger87990462006-08-10 23:35:16 -0700116 /* class attached filters */
117 struct tcf_proto *filter_list;
118 int filter_cnt;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700119
Stephen Hemminger87990462006-08-10 23:35:16 -0700120 /* token bucket parameters */
121 struct qdisc_rate_table *rate; /* rate table of the class itself */
122 struct qdisc_rate_table *ceil; /* ceiling rate (limits borrows too) */
123 long buffer, cbuffer; /* token bucket depth/rate */
124 psched_tdiff_t mbuffer; /* max wait time */
125 long tokens, ctokens; /* current number of tokens */
126 psched_time_t t_c; /* checkpoint time */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700127};
128
Stephen Hemminger87990462006-08-10 23:35:16 -0700129struct htb_sched {
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700130 struct Qdisc_class_hash clhash;
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700131 struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700132
Stephen Hemminger87990462006-08-10 23:35:16 -0700133 /* self list - roots of self generating tree */
134 struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
135 int row_mask[TC_HTB_MAXDEPTH];
136 struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
137 u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700138
Stephen Hemminger87990462006-08-10 23:35:16 -0700139 /* self wait list - roots of wait PQs per row */
140 struct rb_root wait_pq[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141
Stephen Hemminger87990462006-08-10 23:35:16 -0700142 /* time of nearest event per level (row) */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700143 psched_time_t near_ev_cache[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144
Stephen Hemminger87990462006-08-10 23:35:16 -0700145 int defcls; /* class where unclassified flows go to */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146
Stephen Hemminger87990462006-08-10 23:35:16 -0700147 /* filters for qdisc itself */
148 struct tcf_proto *filter_list;
Stephen Hemminger87990462006-08-10 23:35:16 -0700149
150 int rate2quantum; /* quant = rate / rate2quantum */
151 psched_time_t now; /* cached dequeue time */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700152 struct qdisc_watchdog watchdog;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153
Stephen Hemminger87990462006-08-10 23:35:16 -0700154 /* non shaped skbs; let them go directly thru */
155 struct sk_buff_head direct_queue;
156 int direct_qlen; /* max qlen of above */
157
158 long direct_pkts;
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800159
160#define HTB_WARN_TOOMANYEVENTS 0x1
161 unsigned int warned; /* only one warning */
Jarek Poplawski12247362009-02-01 01:13:22 -0800162 struct work_struct work;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700163};
164
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165/* find class in global hash table using given handle */
Stephen Hemminger87990462006-08-10 23:35:16 -0700166static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700167{
168 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700169 struct Qdisc_class_common *clc;
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700170
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700171 clc = qdisc_class_find(&q->clhash, handle);
172 if (clc == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700173 return NULL;
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700174 return container_of(clc, struct htb_class, common);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700175}
176
177/**
178 * htb_classify - classify a packet into class
179 *
180 * It returns NULL if the packet should be dropped or -1 if the packet
181 * should be passed directly thru. In all other cases leaf class is returned.
182 * We allow direct class selection by classid in priority. The we examine
183 * filters in qdisc and in inner nodes (if higher filter points to the inner
184 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900185 * internal fifo (direct). These packets then go directly thru. If we still
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300186 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessful
Linus Torvalds1da177e2005-04-16 15:20:36 -0700187 * then finish and return direct queue.
188 */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000189#define HTB_DIRECT ((struct htb_class *)-1L)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700190
Stephen Hemminger87990462006-08-10 23:35:16 -0700191static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
192 int *qerr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700193{
194 struct htb_sched *q = qdisc_priv(sch);
195 struct htb_class *cl;
196 struct tcf_result res;
197 struct tcf_proto *tcf;
198 int result;
199
200 /* allow to select class by setting skb->priority to valid classid;
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000201 * note that nfmark can be used too by attaching filter fw with no
202 * rules in it
203 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700204 if (skb->priority == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700205 return HTB_DIRECT; /* X:0 (direct flow) selected */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000206 cl = htb_find(skb->priority, sch);
207 if (cl && cl->level == 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208 return cl;
209
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700210 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700211 tcf = q->filter_list;
212 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
213#ifdef CONFIG_NET_CLS_ACT
214 switch (result) {
215 case TC_ACT_QUEUED:
Stephen Hemminger87990462006-08-10 23:35:16 -0700216 case TC_ACT_STOLEN:
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700217 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700218 case TC_ACT_SHOT:
219 return NULL;
220 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700221#endif
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000222 cl = (void *)res.class;
223 if (!cl) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224 if (res.classid == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700225 return HTB_DIRECT; /* X:0 (direct flow) */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000226 cl = htb_find(res.classid, sch);
227 if (!cl)
Stephen Hemminger87990462006-08-10 23:35:16 -0700228 break; /* filter selected invalid classid */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229 }
230 if (!cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700231 return cl; /* we hit leaf; return it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700232
233 /* we have got inner class; apply inner filter chain */
234 tcf = cl->filter_list;
235 }
236 /* classification failed; try to use default class */
Stephen Hemminger87990462006-08-10 23:35:16 -0700237 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700238 if (!cl || cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700239 return HTB_DIRECT; /* bad default .. this is safe bet */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700240 return cl;
241}
242
Linus Torvalds1da177e2005-04-16 15:20:36 -0700243/**
244 * htb_add_to_id_tree - adds class to the round robin list
245 *
246 * Routine adds class to the list (actually tree) sorted by classid.
247 * Make sure that class is not already on such list for given prio.
248 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700249static void htb_add_to_id_tree(struct rb_root *root,
250 struct htb_class *cl, int prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700251{
252 struct rb_node **p = &root->rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700253
Linus Torvalds1da177e2005-04-16 15:20:36 -0700254 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700255 struct htb_class *c;
256 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700257 c = rb_entry(parent, struct htb_class, node[prio]);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700258
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700259 if (cl->common.classid > c->common.classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700260 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700261 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700262 p = &parent->rb_left;
263 }
264 rb_link_node(&cl->node[prio], parent, p);
265 rb_insert_color(&cl->node[prio], root);
266}
267
268/**
269 * htb_add_to_wait_tree - adds class to the event queue with delay
270 *
271 * The class is added to priority event queue to indicate that class will
272 * change its mode in cl->pq_key microseconds. Make sure that class is not
273 * already in the queue.
274 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700275static void htb_add_to_wait_tree(struct htb_sched *q,
276 struct htb_class *cl, long delay)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700277{
278 struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700279
Patrick McHardyfb983d42007-03-16 01:22:39 -0700280 cl->pq_key = q->now + delay;
281 if (cl->pq_key == q->now)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700282 cl->pq_key++;
283
284 /* update the nearest event cache */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700285 if (q->near_ev_cache[cl->level] > cl->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700286 q->near_ev_cache[cl->level] = cl->pq_key;
Stephen Hemminger87990462006-08-10 23:35:16 -0700287
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700289 struct htb_class *c;
290 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700291 c = rb_entry(parent, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700292 if (cl->pq_key >= c->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700293 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700294 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700295 p = &parent->rb_left;
296 }
297 rb_link_node(&cl->pq_node, parent, p);
298 rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
299}
300
301/**
302 * htb_next_rb_node - finds next node in binary tree
303 *
304 * When we are past last key we return NULL.
305 * Average complexity is 2 steps per call.
306 */
Stephen Hemminger3696f622006-08-10 23:36:01 -0700307static inline void htb_next_rb_node(struct rb_node **n)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700308{
309 *n = rb_next(*n);
310}
311
312/**
313 * htb_add_class_to_row - add class to its row
314 *
315 * The class is added to row at priorities marked in mask.
316 * It does nothing if mask == 0.
317 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700318static inline void htb_add_class_to_row(struct htb_sched *q,
319 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700320{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700321 q->row_mask[cl->level] |= mask;
322 while (mask) {
323 int prio = ffz(~mask);
324 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700325 htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700326 }
327}
328
Stephen Hemminger3696f622006-08-10 23:36:01 -0700329/* If this triggers, it is a bug in this code, but it need not be fatal */
330static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
331{
Ismail Donmez81771b32006-10-03 13:49:10 -0700332 if (RB_EMPTY_NODE(rb)) {
Stephen Hemminger3696f622006-08-10 23:36:01 -0700333 WARN_ON(1);
334 } else {
335 rb_erase(rb, root);
336 RB_CLEAR_NODE(rb);
337 }
338}
339
340
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341/**
342 * htb_remove_class_from_row - removes class from its row
343 *
344 * The class is removed from row at priorities marked in mask.
345 * It does nothing if mask == 0.
346 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700347static inline void htb_remove_class_from_row(struct htb_sched *q,
348 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700349{
350 int m = 0;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700351
Linus Torvalds1da177e2005-04-16 15:20:36 -0700352 while (mask) {
353 int prio = ffz(~mask);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700354
Linus Torvalds1da177e2005-04-16 15:20:36 -0700355 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700356 if (q->ptr[cl->level][prio] == cl->node + prio)
357 htb_next_rb_node(q->ptr[cl->level] + prio);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700358
359 htb_safe_rb_erase(cl->node + prio, q->row[cl->level] + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700360 if (!q->row[cl->level][prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700361 m |= 1 << prio;
362 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700363 q->row_mask[cl->level] &= ~m;
364}
365
366/**
367 * htb_activate_prios - creates active classe's feed chain
368 *
369 * The class is connected to ancestors and/or appropriate rows
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900370 * for priorities it is participating on. cl->cmode must be new
Linus Torvalds1da177e2005-04-16 15:20:36 -0700371 * (activated) mode. It does nothing if cl->prio_activity == 0.
372 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700373static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700374{
375 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700376 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700377
378 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700379 m = mask;
380 while (m) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381 int prio = ffz(~m);
382 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700383
Linus Torvalds1da177e2005-04-16 15:20:36 -0700384 if (p->un.inner.feed[prio].rb_node)
385 /* parent already has its feed in use so that
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000386 * reset bit in mask as parent is already ok
387 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700389
390 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700391 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700392 p->prio_activity |= mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700393 cl = p;
394 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700395
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396 }
397 if (cl->cmode == HTB_CAN_SEND && mask)
Stephen Hemminger87990462006-08-10 23:35:16 -0700398 htb_add_class_to_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399}
400
401/**
402 * htb_deactivate_prios - remove class from feed chain
403 *
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900404 * cl->cmode must represent old mode (before deactivation). It does
Linus Torvalds1da177e2005-04-16 15:20:36 -0700405 * nothing if cl->prio_activity == 0. Class is removed from all feed
406 * chains and rows.
407 */
408static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
409{
410 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700411 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700412
413 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700414 m = mask;
415 mask = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700416 while (m) {
417 int prio = ffz(~m);
418 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700419
420 if (p->un.inner.ptr[prio] == cl->node + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700421 /* we are removing child which is pointed to from
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000422 * parent feed - forget the pointer but remember
423 * classid
424 */
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700425 p->un.inner.last_ptr_id[prio] = cl->common.classid;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426 p->un.inner.ptr[prio] = NULL;
427 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700428
Stephen Hemminger3696f622006-08-10 23:36:01 -0700429 htb_safe_rb_erase(cl->node + prio, p->un.inner.feed + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700430
431 if (!p->un.inner.feed[prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700432 mask |= 1 << prio;
433 }
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700434
Linus Torvalds1da177e2005-04-16 15:20:36 -0700435 p->prio_activity &= ~mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700436 cl = p;
437 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700438
Linus Torvalds1da177e2005-04-16 15:20:36 -0700439 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700440 if (cl->cmode == HTB_CAN_SEND && mask)
441 htb_remove_class_from_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700442}
443
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700444static inline long htb_lowater(const struct htb_class *cl)
445{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700446 if (htb_hysteresis)
447 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
448 else
449 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700450}
451static inline long htb_hiwater(const struct htb_class *cl)
452{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700453 if (htb_hysteresis)
454 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
455 else
456 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700457}
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700458
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700459
Linus Torvalds1da177e2005-04-16 15:20:36 -0700460/**
461 * htb_class_mode - computes and returns current class mode
462 *
463 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
464 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900465 * from now to time when cl will change its state.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700466 * Also it is worth to note that class mode doesn't change simply
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900467 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
Linus Torvalds1da177e2005-04-16 15:20:36 -0700468 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
469 * mode transitions per time unit. The speed gain is about 1/6.
470 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700471static inline enum htb_cmode
472htb_class_mode(struct htb_class *cl, long *diff)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700473{
Stephen Hemminger87990462006-08-10 23:35:16 -0700474 long toks;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700475
Stephen Hemminger87990462006-08-10 23:35:16 -0700476 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
477 *diff = -toks;
478 return HTB_CANT_SEND;
479 }
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700480
Stephen Hemminger87990462006-08-10 23:35:16 -0700481 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
482 return HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700483
Stephen Hemminger87990462006-08-10 23:35:16 -0700484 *diff = -toks;
485 return HTB_MAY_BORROW;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700486}
487
488/**
489 * htb_change_class_mode - changes classe's mode
490 *
491 * This should be the only way how to change classe's mode under normal
492 * cirsumstances. Routine will update feed lists linkage, change mode
493 * and add class to the wait event queue if appropriate. New mode should
494 * be different from old one and cl->pq_key has to be valid if changing
495 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
496 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700497static void
Linus Torvalds1da177e2005-04-16 15:20:36 -0700498htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
Stephen Hemminger87990462006-08-10 23:35:16 -0700499{
500 enum htb_cmode new_mode = htb_class_mode(cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700501
502 if (new_mode == cl->cmode)
Stephen Hemminger87990462006-08-10 23:35:16 -0700503 return;
504
505 if (cl->prio_activity) { /* not necessary: speed optimization */
506 if (cl->cmode != HTB_CANT_SEND)
507 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700508 cl->cmode = new_mode;
Stephen Hemminger87990462006-08-10 23:35:16 -0700509 if (new_mode != HTB_CANT_SEND)
510 htb_activate_prios(q, cl);
511 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700512 cl->cmode = new_mode;
513}
514
515/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900516 * htb_activate - inserts leaf cl into appropriate active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700517 *
518 * Routine learns (new) priority of leaf and activates feed chain
519 * for the prio. It can be called on already active leaf safely.
520 * It also adds leaf into droplist.
521 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700522static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700523{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700524 WARN_ON(cl->level || !cl->un.leaf.q || !cl->un.leaf.q->q.qlen);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700525
Linus Torvalds1da177e2005-04-16 15:20:36 -0700526 if (!cl->prio_activity) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800527 cl->prio_activity = 1 << cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700528 htb_activate_prios(q, cl);
529 list_add_tail(&cl->un.leaf.drop_list,
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800530 q->drops + cl->prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531 }
532}
533
534/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900535 * htb_deactivate - remove leaf cl from active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700536 *
537 * Make sure that leaf is active. In the other words it can't be called
538 * with non-active leaf. It also removes class from the drop list.
539 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700540static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700541{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700542 WARN_ON(!cl->prio_activity);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700543
Stephen Hemminger87990462006-08-10 23:35:16 -0700544 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700545 cl->prio_activity = 0;
546 list_del_init(&cl->un.leaf.drop_list);
547}
548
549static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
550{
Jarek Poplawskif30ab412008-11-13 22:56:30 -0800551 int uninitialized_var(ret);
Stephen Hemminger87990462006-08-10 23:35:16 -0700552 struct htb_sched *q = qdisc_priv(sch);
553 struct htb_class *cl = htb_classify(skb, sch, &ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554
Stephen Hemminger87990462006-08-10 23:35:16 -0700555 if (cl == HTB_DIRECT) {
556 /* enqueue to helper queue */
557 if (q->direct_queue.qlen < q->direct_qlen) {
558 __skb_queue_tail(&q->direct_queue, skb);
559 q->direct_pkts++;
560 } else {
Eric Dumazet17045752012-05-04 04:37:21 +0000561 return qdisc_drop(skb, sch);
Stephen Hemminger87990462006-08-10 23:35:16 -0700562 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700563#ifdef CONFIG_NET_CLS_ACT
Stephen Hemminger87990462006-08-10 23:35:16 -0700564 } else if (!cl) {
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700565 if (ret & __NET_XMIT_BYPASS)
Stephen Hemminger87990462006-08-10 23:35:16 -0700566 sch->qstats.drops++;
567 kfree_skb(skb);
568 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700569#endif
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700570 } else if ((ret = qdisc_enqueue(skb, cl->un.leaf.q)) != NET_XMIT_SUCCESS) {
571 if (net_xmit_drop_count(ret)) {
572 sch->qstats.drops++;
573 cl->qstats.drops++;
574 }
David S. Miller69747652008-08-17 23:55:36 -0700575 return ret;
Stephen Hemminger87990462006-08-10 23:35:16 -0700576 } else {
Stephen Hemminger87990462006-08-10 23:35:16 -0700577 htb_activate(q, cl);
578 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700579
Stephen Hemminger87990462006-08-10 23:35:16 -0700580 sch->q.qlen++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700581 return NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700582}
583
Jarek Poplawski59e42202008-12-03 21:17:27 -0800584static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, long diff)
585{
586 long toks = diff + cl->tokens;
587
588 if (toks > cl->buffer)
589 toks = cl->buffer;
590 toks -= (long) qdisc_l2t(cl->rate, bytes);
591 if (toks <= -cl->mbuffer)
592 toks = 1 - cl->mbuffer;
593
594 cl->tokens = toks;
595}
596
597static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, long diff)
598{
599 long toks = diff + cl->ctokens;
600
601 if (toks > cl->cbuffer)
602 toks = cl->cbuffer;
603 toks -= (long) qdisc_l2t(cl->ceil, bytes);
604 if (toks <= -cl->mbuffer)
605 toks = 1 - cl->mbuffer;
606
607 cl->ctokens = toks;
608}
609
Linus Torvalds1da177e2005-04-16 15:20:36 -0700610/**
611 * htb_charge_class - charges amount "bytes" to leaf and ancestors
612 *
613 * Routine assumes that packet "bytes" long was dequeued from leaf cl
614 * borrowing from "level". It accounts bytes to ceil leaky bucket for
615 * leaf and all ancestors and to rate bucket for ancestors at levels
616 * "level" and higher. It also handles possible change of mode resulting
617 * from the update. Note that mode can also increase here (MAY_BORROW to
618 * CAN_SEND) because we can use more precise clock that event queue here.
619 * In such case we remove class from event queue first.
620 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700621static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700622 int level, struct sk_buff *skb)
Stephen Hemminger87990462006-08-10 23:35:16 -0700623{
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700624 int bytes = qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700625 enum htb_cmode old_mode;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800626 long diff;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700627
628 while (cl) {
Patrick McHardy03cc45c2007-03-23 11:29:11 -0700629 diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700630 if (cl->level >= level) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700631 if (cl->level == level)
632 cl->xstats.lends++;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800633 htb_accnt_tokens(cl, bytes, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634 } else {
635 cl->xstats.borrows++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700636 cl->tokens += diff; /* we moved t_c; update tokens */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700637 }
Jarek Poplawski59e42202008-12-03 21:17:27 -0800638 htb_accnt_ctokens(cl, bytes, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700639 cl->t_c = q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640
Stephen Hemminger87990462006-08-10 23:35:16 -0700641 old_mode = cl->cmode;
642 diff = 0;
643 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700644 if (old_mode != cl->cmode) {
645 if (old_mode != HTB_CAN_SEND)
Stephen Hemminger3696f622006-08-10 23:36:01 -0700646 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700647 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700648 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700649 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700650
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000651 /* update basic stats except for leaves which are already updated */
652 if (cl->level)
653 bstats_update(&cl->bstats, skb);
654
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655 cl = cl->parent;
656 }
657}
658
659/**
660 * htb_do_events - make mode changes to classes at the level
661 *
Patrick McHardyfb983d42007-03-16 01:22:39 -0700662 * Scans event queue for pending events and applies them. Returns time of
Jarek Poplawski12247362009-02-01 01:13:22 -0800663 * next pending event (0 for no event in pq, q->now for too many events).
Patrick McHardyfb983d42007-03-16 01:22:39 -0700664 * Note: Applied are events whose have cl->pq_key <= q->now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700665 */
Jarek Poplawskia73be042009-01-12 21:54:40 -0800666static psched_time_t htb_do_events(struct htb_sched *q, int level,
667 unsigned long start)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700668{
Martin Devera8f3ea332008-03-23 22:00:38 -0700669 /* don't run for longer than 2 jiffies; 2 is used instead of
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000670 * 1 to simplify things when jiffy is going to be incremented
671 * too soon
672 */
Jarek Poplawskia73be042009-01-12 21:54:40 -0800673 unsigned long stop_at = start + 2;
Martin Devera8f3ea332008-03-23 22:00:38 -0700674 while (time_before(jiffies, stop_at)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675 struct htb_class *cl;
676 long diff;
Akinbou Mita30bdbe32006-10-12 01:52:05 -0700677 struct rb_node *p = rb_first(&q->wait_pq[level]);
678
Stephen Hemminger87990462006-08-10 23:35:16 -0700679 if (!p)
680 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700681
682 cl = rb_entry(p, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700683 if (cl->pq_key > q->now)
684 return cl->pq_key;
685
Stephen Hemminger3696f622006-08-10 23:36:01 -0700686 htb_safe_rb_erase(p, q->wait_pq + level);
Patrick McHardy03cc45c2007-03-23 11:29:11 -0700687 diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
Stephen Hemminger87990462006-08-10 23:35:16 -0700688 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700689 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700690 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700691 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800692
693 /* too much load - let's continue after a break for scheduling */
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800694 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000695 pr_warning("htb: too many events!\n");
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800696 q->warned |= HTB_WARN_TOOMANYEVENTS;
697 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800698
699 return q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700}
701
702/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000703 * is no such one exists.
704 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700705static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
706 u32 id)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700707{
708 struct rb_node *r = NULL;
709 while (n) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700710 struct htb_class *cl =
711 rb_entry(n, struct htb_class, node[prio]);
Stephen Hemminger87990462006-08-10 23:35:16 -0700712
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700713 if (id > cl->common.classid) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700714 n = n->rb_right;
Jarek Poplawski1b5c0072008-12-09 22:34:40 -0800715 } else if (id < cl->common.classid) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700716 r = n;
717 n = n->rb_left;
Jarek Poplawski1b5c0072008-12-09 22:34:40 -0800718 } else {
719 return n;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720 }
721 }
722 return r;
723}
724
725/**
726 * htb_lookup_leaf - returns next leaf class in DRR order
727 *
728 * Find leaf where current feed pointers points to.
729 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700730static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio,
731 struct rb_node **pptr, u32 * pid)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700732{
733 int i;
734 struct {
735 struct rb_node *root;
736 struct rb_node **pptr;
737 u32 *pid;
Stephen Hemminger87990462006-08-10 23:35:16 -0700738 } stk[TC_HTB_MAXDEPTH], *sp = stk;
739
Jarek Poplawski512bb432008-12-09 22:35:02 -0800740 BUG_ON(!tree->rb_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700741 sp->root = tree->rb_node;
742 sp->pptr = pptr;
743 sp->pid = pid;
744
745 for (i = 0; i < 65535; i++) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700746 if (!*sp->pptr && *sp->pid) {
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900747 /* ptr was invalidated but id is valid - try to recover
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000748 * the original or next ptr
749 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700750 *sp->pptr =
751 htb_id_find_next_upper(prio, sp->root, *sp->pid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700752 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700753 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000754 * can become out of date quickly
755 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700756 if (!*sp->pptr) { /* we are at right end; rewind & go up */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757 *sp->pptr = sp->root;
Stephen Hemminger87990462006-08-10 23:35:16 -0700758 while ((*sp->pptr)->rb_left)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700759 *sp->pptr = (*sp->pptr)->rb_left;
760 if (sp > stk) {
761 sp--;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800762 if (!*sp->pptr) {
763 WARN_ON(1);
Stephen Hemminger87990462006-08-10 23:35:16 -0700764 return NULL;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800765 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700766 htb_next_rb_node(sp->pptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700767 }
768 } else {
769 struct htb_class *cl;
Stephen Hemminger87990462006-08-10 23:35:16 -0700770 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
771 if (!cl->level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700772 return cl;
773 (++sp)->root = cl->un.inner.feed[prio].rb_node;
Stephen Hemminger87990462006-08-10 23:35:16 -0700774 sp->pptr = cl->un.inner.ptr + prio;
775 sp->pid = cl->un.inner.last_ptr_id + prio;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700776 }
777 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700778 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700779 return NULL;
780}
781
782/* dequeues packet at given priority and level; call only if
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000783 * you are sure that there is active class at prio/level
784 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700785static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
786 int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700787{
788 struct sk_buff *skb = NULL;
Stephen Hemminger87990462006-08-10 23:35:16 -0700789 struct htb_class *cl, *start;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700790 /* look initial class up in the row */
Stephen Hemminger87990462006-08-10 23:35:16 -0700791 start = cl = htb_lookup_leaf(q->row[level] + prio, prio,
792 q->ptr[level] + prio,
793 q->last_ptr_id[level] + prio);
794
Linus Torvalds1da177e2005-04-16 15:20:36 -0700795 do {
796next:
Jarek Poplawski512bb432008-12-09 22:35:02 -0800797 if (unlikely(!cl))
Stephen Hemminger87990462006-08-10 23:35:16 -0700798 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700799
800 /* class can be empty - it is unlikely but can be true if leaf
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000801 * qdisc drops packets in enqueue routine or if someone used
802 * graft operation on the leaf since last dequeue;
803 * simply deactivate and skip such class
804 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700805 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
806 struct htb_class *next;
Stephen Hemminger87990462006-08-10 23:35:16 -0700807 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700808
809 /* row/level might become empty */
810 if ((q->row_mask[level] & (1 << prio)) == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -0700811 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700812
Stephen Hemminger87990462006-08-10 23:35:16 -0700813 next = htb_lookup_leaf(q->row[level] + prio,
814 prio, q->ptr[level] + prio,
815 q->last_ptr_id[level] + prio);
816
817 if (cl == start) /* fix start if we just deleted it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700818 start = next;
819 cl = next;
820 goto next;
821 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700822
823 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
824 if (likely(skb != NULL))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700825 break;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800826
Jarek Poplawskib00355d2009-02-01 01:12:42 -0800827 qdisc_warn_nonwc("htb", cl->un.leaf.q);
Stephen Hemminger87990462006-08-10 23:35:16 -0700828 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
829 ptr[0]) + prio);
830 cl = htb_lookup_leaf(q->row[level] + prio, prio,
831 q->ptr[level] + prio,
832 q->last_ptr_id[level] + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700833
834 } while (cl != start);
835
836 if (likely(skb != NULL)) {
Eric Dumazet2dd875f2012-05-10 05:36:34 +0000837 bstats_update(&cl->bstats, skb);
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700838 cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb);
839 if (cl->un.leaf.deficit[level] < 0) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800840 cl->un.leaf.deficit[level] += cl->quantum;
Stephen Hemminger87990462006-08-10 23:35:16 -0700841 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
842 ptr[0]) + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700843 }
844 /* this used to be after charge_class but this constelation
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000845 * gives us slightly better performance
846 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700847 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700848 htb_deactivate(q, cl);
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700849 htb_charge_class(q, cl, level, skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700850 }
851 return skb;
852}
853
Linus Torvalds1da177e2005-04-16 15:20:36 -0700854static struct sk_buff *htb_dequeue(struct Qdisc *sch)
855{
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800856 struct sk_buff *skb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700857 struct htb_sched *q = qdisc_priv(sch);
858 int level;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700859 psched_time_t next_event;
Jarek Poplawskia73be042009-01-12 21:54:40 -0800860 unsigned long start_at;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700861
862 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
Stephen Hemminger87990462006-08-10 23:35:16 -0700863 skb = __skb_dequeue(&q->direct_queue);
864 if (skb != NULL) {
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800865ok:
866 qdisc_bstats_update(sch, skb);
Eric Dumazetfd245a42011-01-20 05:27:16 +0000867 qdisc_unthrottled(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700868 sch->q.qlen--;
869 return skb;
870 }
871
Stephen Hemminger87990462006-08-10 23:35:16 -0700872 if (!sch->q.qlen)
873 goto fin;
Patrick McHardy3bebcda2007-03-23 11:29:25 -0700874 q->now = psched_get_time();
Jarek Poplawskia73be042009-01-12 21:54:40 -0800875 start_at = jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700876
Patrick McHardyfb983d42007-03-16 01:22:39 -0700877 next_event = q->now + 5 * PSCHED_TICKS_PER_SEC;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800878
Linus Torvalds1da177e2005-04-16 15:20:36 -0700879 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
880 /* common case optimization - skip event handler quickly */
881 int m;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700882 psched_time_t event;
Stephen Hemminger87990462006-08-10 23:35:16 -0700883
Patrick McHardyfb983d42007-03-16 01:22:39 -0700884 if (q->now >= q->near_ev_cache[level]) {
Jarek Poplawskia73be042009-01-12 21:54:40 -0800885 event = htb_do_events(q, level, start_at);
Patrick McHardy2e4b3b02007-05-23 23:39:54 -0700886 if (!event)
887 event = q->now + PSCHED_TICKS_PER_SEC;
888 q->near_ev_cache[level] = event;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700889 } else
890 event = q->near_ev_cache[level];
891
Jarek Poplawskic0851342009-01-12 21:54:16 -0800892 if (next_event > event)
Patrick McHardyfb983d42007-03-16 01:22:39 -0700893 next_event = event;
894
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895 m = ~q->row_mask[level];
896 while (m != (int)(-1)) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700897 int prio = ffz(m);
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000898
Linus Torvalds1da177e2005-04-16 15:20:36 -0700899 m |= 1 << prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700900 skb = htb_dequeue_tree(q, prio, level);
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800901 if (likely(skb != NULL))
902 goto ok;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700903 }
904 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700905 sch->qstats.overlimits++;
Jarek Poplawski12247362009-02-01 01:13:22 -0800906 if (likely(next_event > q->now))
907 qdisc_watchdog_schedule(&q->watchdog, next_event);
908 else
909 schedule_work(&q->work);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700910fin:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700911 return skb;
912}
913
914/* try to drop from each class (by prio) until one succeed */
Stephen Hemminger87990462006-08-10 23:35:16 -0700915static unsigned int htb_drop(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700916{
917 struct htb_sched *q = qdisc_priv(sch);
918 int prio;
919
920 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
921 struct list_head *p;
Stephen Hemminger87990462006-08-10 23:35:16 -0700922 list_for_each(p, q->drops + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700923 struct htb_class *cl = list_entry(p, struct htb_class,
924 un.leaf.drop_list);
925 unsigned int len;
Stephen Hemminger87990462006-08-10 23:35:16 -0700926 if (cl->un.leaf.q->ops->drop &&
927 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700928 sch->q.qlen--;
929 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700930 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700931 return len;
932 }
933 }
934 }
935 return 0;
936}
937
938/* reset all classes */
939/* always caled under BH & queue lock */
Stephen Hemminger87990462006-08-10 23:35:16 -0700940static void htb_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700941{
942 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700943 struct htb_class *cl;
944 struct hlist_node *n;
945 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700946
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700947 for (i = 0; i < q->clhash.hashsize; i++) {
948 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700949 if (cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700950 memset(&cl->un.inner, 0, sizeof(cl->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700951 else {
Stephen Hemminger87990462006-08-10 23:35:16 -0700952 if (cl->un.leaf.q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700953 qdisc_reset(cl->un.leaf.q);
954 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
955 }
956 cl->prio_activity = 0;
957 cl->cmode = HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700958
959 }
960 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700961 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700962 __skb_queue_purge(&q->direct_queue);
963 sch->q.qlen = 0;
Stephen Hemminger87990462006-08-10 23:35:16 -0700964 memset(q->row, 0, sizeof(q->row));
965 memset(q->row_mask, 0, sizeof(q->row_mask));
966 memset(q->wait_pq, 0, sizeof(q->wait_pq));
967 memset(q->ptr, 0, sizeof(q->ptr));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -0700969 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700970}
971
Patrick McHardy27a34212008-01-23 20:35:39 -0800972static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
973 [TCA_HTB_PARMS] = { .len = sizeof(struct tc_htb_opt) },
974 [TCA_HTB_INIT] = { .len = sizeof(struct tc_htb_glob) },
975 [TCA_HTB_CTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
976 [TCA_HTB_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
977};
978
Jarek Poplawski12247362009-02-01 01:13:22 -0800979static void htb_work_func(struct work_struct *work)
980{
981 struct htb_sched *q = container_of(work, struct htb_sched, work);
982 struct Qdisc *sch = q->watchdog.qdisc;
983
984 __netif_schedule(qdisc_root(sch));
985}
986
Patrick McHardy1e904742008-01-22 22:11:17 -0800987static int htb_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700988{
989 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800990 struct nlattr *tb[TCA_HTB_INIT + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700991 struct tc_htb_glob *gopt;
Patrick McHardycee63722008-01-23 20:33:32 -0800992 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700993 int i;
Patrick McHardycee63722008-01-23 20:33:32 -0800994
995 if (!opt)
996 return -EINVAL;
997
Patrick McHardy27a34212008-01-23 20:35:39 -0800998 err = nla_parse_nested(tb, TCA_HTB_INIT, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -0800999 if (err < 0)
1000 return err;
1001
Patrick McHardy27a34212008-01-23 20:35:39 -08001002 if (tb[TCA_HTB_INIT] == NULL) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001003 pr_err("HTB: hey probably you have bad tc tool ?\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001004 return -EINVAL;
1005 }
Patrick McHardy1e904742008-01-22 22:11:17 -08001006 gopt = nla_data(tb[TCA_HTB_INIT]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001007 if (gopt->version != HTB_VER >> 16) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001008 pr_err("HTB: need tc/htb version %d (minor is %d), you have %d\n",
Stephen Hemminger87990462006-08-10 23:35:16 -07001009 HTB_VER >> 16, HTB_VER & 0xffff, gopt->version);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001010 return -EINVAL;
1011 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001012
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001013 err = qdisc_class_hash_init(&q->clhash);
1014 if (err < 0)
1015 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001016 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -07001017 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001018
Patrick McHardyfb983d42007-03-16 01:22:39 -07001019 qdisc_watchdog_init(&q->watchdog, sch);
Jarek Poplawski12247362009-02-01 01:13:22 -08001020 INIT_WORK(&q->work, htb_work_func);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001021 skb_queue_head_init(&q->direct_queue);
1022
David S. Miller5ce2d482008-07-08 17:06:30 -07001023 q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
Stephen Hemminger87990462006-08-10 23:35:16 -07001024 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001025 q->direct_qlen = 2;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001026
Linus Torvalds1da177e2005-04-16 15:20:36 -07001027 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1028 q->rate2quantum = 1;
1029 q->defcls = gopt->defcls;
1030
1031 return 0;
1032}
1033
1034static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1035{
Jarek Poplawski102396a2008-08-29 14:21:52 -07001036 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001037 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001038 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001039 struct tc_htb_glob gopt;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001040
David S. Miller7698b4f2008-07-16 01:42:40 -07001041 spin_lock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001042
1043 gopt.direct_pkts = q->direct_pkts;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001044 gopt.version = HTB_VER;
1045 gopt.rate2quantum = q->rate2quantum;
1046 gopt.defcls = q->defcls;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001047 gopt.debug = 0;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001048
1049 nest = nla_nest_start(skb, TCA_OPTIONS);
1050 if (nest == NULL)
1051 goto nla_put_failure;
David S. Miller1b34ec42012-03-29 05:11:39 -04001052 if (nla_put(skb, TCA_HTB_INIT, sizeof(gopt), &gopt))
1053 goto nla_put_failure;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001054 nla_nest_end(skb, nest);
1055
David S. Miller7698b4f2008-07-16 01:42:40 -07001056 spin_unlock_bh(root_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001057 return skb->len;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001058
Patrick McHardy1e904742008-01-22 22:11:17 -08001059nla_put_failure:
David S. Miller7698b4f2008-07-16 01:42:40 -07001060 spin_unlock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001061 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001062 return -1;
1063}
1064
1065static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
Stephen Hemminger87990462006-08-10 23:35:16 -07001066 struct sk_buff *skb, struct tcmsg *tcm)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001067{
Stephen Hemminger87990462006-08-10 23:35:16 -07001068 struct htb_class *cl = (struct htb_class *)arg;
Jarek Poplawski102396a2008-08-29 14:21:52 -07001069 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001070 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001071 struct tc_htb_opt opt;
1072
David S. Miller7698b4f2008-07-16 01:42:40 -07001073 spin_lock_bh(root_lock);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001074 tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
1075 tcm->tcm_handle = cl->common.classid;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001076 if (!cl->level && cl->un.leaf.q)
1077 tcm->tcm_info = cl->un.leaf.q->handle;
1078
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001079 nest = nla_nest_start(skb, TCA_OPTIONS);
1080 if (nest == NULL)
1081 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001082
Stephen Hemminger87990462006-08-10 23:35:16 -07001083 memset(&opt, 0, sizeof(opt));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001084
Stephen Hemminger87990462006-08-10 23:35:16 -07001085 opt.rate = cl->rate->rate;
1086 opt.buffer = cl->buffer;
1087 opt.ceil = cl->ceil->rate;
1088 opt.cbuffer = cl->cbuffer;
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001089 opt.quantum = cl->quantum;
1090 opt.prio = cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -07001091 opt.level = cl->level;
David S. Miller1b34ec42012-03-29 05:11:39 -04001092 if (nla_put(skb, TCA_HTB_PARMS, sizeof(opt), &opt))
1093 goto nla_put_failure;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001094
1095 nla_nest_end(skb, nest);
David S. Miller7698b4f2008-07-16 01:42:40 -07001096 spin_unlock_bh(root_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001097 return skb->len;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001098
Patrick McHardy1e904742008-01-22 22:11:17 -08001099nla_put_failure:
David S. Miller7698b4f2008-07-16 01:42:40 -07001100 spin_unlock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001101 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001102 return -1;
1103}
1104
1105static int
Stephen Hemminger87990462006-08-10 23:35:16 -07001106htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001107{
Stephen Hemminger87990462006-08-10 23:35:16 -07001108 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001109
Linus Torvalds1da177e2005-04-16 15:20:36 -07001110 if (!cl->level && cl->un.leaf.q)
1111 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
1112 cl->xstats.tokens = cl->tokens;
1113 cl->xstats.ctokens = cl->ctokens;
1114
1115 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
Eric Dumazetd250a5f2009-10-02 10:32:18 +00001116 gnet_stats_copy_rate_est(d, NULL, &cl->rate_est) < 0 ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001117 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1118 return -1;
1119
1120 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1121}
1122
1123static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
Stephen Hemminger87990462006-08-10 23:35:16 -07001124 struct Qdisc **old)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001125{
Stephen Hemminger87990462006-08-10 23:35:16 -07001126 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001127
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001128 if (cl->level)
1129 return -EINVAL;
1130 if (new == NULL &&
Changli Gao3511c912010-10-16 13:04:08 +00001131 (new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001132 cl->common.classid)) == NULL)
1133 return -ENOBUFS;
1134
1135 sch_tree_lock(sch);
1136 *old = cl->un.leaf.q;
1137 cl->un.leaf.q = new;
1138 if (*old != NULL) {
1139 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1140 qdisc_reset(*old);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001141 }
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001142 sch_tree_unlock(sch);
1143 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001144}
1145
Stephen Hemminger87990462006-08-10 23:35:16 -07001146static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001147{
Stephen Hemminger87990462006-08-10 23:35:16 -07001148 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001149 return !cl->level ? cl->un.leaf.q : NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150}
1151
Patrick McHardy256d61b2006-11-29 17:37:05 -08001152static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
1153{
1154 struct htb_class *cl = (struct htb_class *)arg;
1155
1156 if (cl->un.leaf.q->q.qlen == 0)
1157 htb_deactivate(qdisc_priv(sch), cl);
1158}
1159
Linus Torvalds1da177e2005-04-16 15:20:36 -07001160static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1161{
Stephen Hemminger87990462006-08-10 23:35:16 -07001162 struct htb_class *cl = htb_find(classid, sch);
1163 if (cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001164 cl->refcnt++;
1165 return (unsigned long)cl;
1166}
1167
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001168static inline int htb_parent_last_child(struct htb_class *cl)
1169{
1170 if (!cl->parent)
1171 /* the root class */
1172 return 0;
Patrick McHardy42077592008-07-05 23:22:53 -07001173 if (cl->parent->children > 1)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001174 /* not the last child */
1175 return 0;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001176 return 1;
1177}
1178
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001179static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl,
1180 struct Qdisc *new_q)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001181{
1182 struct htb_class *parent = cl->parent;
1183
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001184 WARN_ON(cl->level || !cl->un.leaf.q || cl->prio_activity);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001185
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001186 if (parent->cmode != HTB_CAN_SEND)
1187 htb_safe_rb_erase(&parent->pq_node, q->wait_pq + parent->level);
1188
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001189 parent->level = 0;
1190 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
1191 INIT_LIST_HEAD(&parent->un.leaf.drop_list);
1192 parent->un.leaf.q = new_q ? new_q : &noop_qdisc;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001193 parent->tokens = parent->buffer;
1194 parent->ctokens = parent->cbuffer;
Patrick McHardy3bebcda2007-03-23 11:29:25 -07001195 parent->t_c = psched_get_time();
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001196 parent->cmode = HTB_CAN_SEND;
1197}
1198
Stephen Hemminger87990462006-08-10 23:35:16 -07001199static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001200{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001201 if (!cl->level) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001202 WARN_ON(!cl->un.leaf.q);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001203 qdisc_destroy(cl->un.leaf.q);
1204 }
Patrick McHardyee39e102007-07-02 22:48:13 -07001205 gen_kill_estimator(&cl->bstats, &cl->rate_est);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001206 qdisc_put_rtab(cl->rate);
1207 qdisc_put_rtab(cl->ceil);
Stephen Hemminger87990462006-08-10 23:35:16 -07001208
Patrick McHardyff31ab52008-07-01 19:52:38 -07001209 tcf_destroy_chain(&cl->filter_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001210 kfree(cl);
1211}
1212
Stephen Hemminger87990462006-08-10 23:35:16 -07001213static void htb_destroy(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001214{
1215 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001216 struct hlist_node *n, *next;
1217 struct htb_class *cl;
1218 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001219
Jarek Poplawski12247362009-02-01 01:13:22 -08001220 cancel_work_sync(&q->work);
Patrick McHardyfb983d42007-03-16 01:22:39 -07001221 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222 /* This line used to be after htb_destroy_class call below
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001223 * and surprisingly it worked in 2.4. But it must precede it
1224 * because filter need its target class alive to be able to call
1225 * unbind_filter on it (without Oops).
1226 */
Patrick McHardyff31ab52008-07-01 19:52:38 -07001227 tcf_destroy_chain(&q->filter_list);
Stephen Hemminger87990462006-08-10 23:35:16 -07001228
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001229 for (i = 0; i < q->clhash.hashsize; i++) {
1230 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001231 tcf_destroy_chain(&cl->filter_list);
1232 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001233 for (i = 0; i < q->clhash.hashsize; i++) {
1234 hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[i],
1235 common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001236 htb_destroy_class(sch, cl);
1237 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001238 qdisc_class_hash_destroy(&q->clhash);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001239 __skb_queue_purge(&q->direct_queue);
1240}
1241
1242static int htb_delete(struct Qdisc *sch, unsigned long arg)
1243{
1244 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001245 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy256d61b2006-11-29 17:37:05 -08001246 unsigned int qlen;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001247 struct Qdisc *new_q = NULL;
1248 int last_child = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001249
1250 // TODO: why don't allow to delete subtree ? references ? does
1251 // tc subsys quarantee us that in htb_destroy it holds no class
1252 // refs so that we can remove children safely there ?
Patrick McHardy42077592008-07-05 23:22:53 -07001253 if (cl->children || cl->filter_cnt)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001254 return -EBUSY;
Stephen Hemminger87990462006-08-10 23:35:16 -07001255
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001256 if (!cl->level && htb_parent_last_child(cl)) {
Changli Gao3511c912010-10-16 13:04:08 +00001257 new_q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
David S. Millerbb949fb2008-07-08 16:55:56 -07001258 cl->parent->common.classid);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001259 last_child = 1;
1260 }
1261
Linus Torvalds1da177e2005-04-16 15:20:36 -07001262 sch_tree_lock(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001263
Patrick McHardy814a175e2006-11-29 17:34:50 -08001264 if (!cl->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001265 qlen = cl->un.leaf.q->q.qlen;
Patrick McHardy814a175e2006-11-29 17:34:50 -08001266 qdisc_reset(cl->un.leaf.q);
Patrick McHardy256d61b2006-11-29 17:37:05 -08001267 qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
Patrick McHardy814a175e2006-11-29 17:34:50 -08001268 }
1269
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001270 /* delete from hash and active; remainder in destroy_class */
1271 qdisc_class_hash_remove(&q->clhash, &cl->common);
Jarek Poplawski26b284d2008-08-13 15:16:43 -07001272 if (cl->parent)
1273 cl->parent->children--;
Patrick McHardyc38c83c2007-03-27 14:04:24 -07001274
Linus Torvalds1da177e2005-04-16 15:20:36 -07001275 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001276 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001277
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001278 if (cl->cmode != HTB_CAN_SEND)
1279 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
1280
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001281 if (last_child)
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001282 htb_parent_to_leaf(q, cl, new_q);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001283
Jarek Poplawski7cd0a632009-03-15 20:00:19 -07001284 BUG_ON(--cl->refcnt == 0);
1285 /*
1286 * This shouldn't happen: we "hold" one cops->get() when called
1287 * from tc_ctl_tclass; the destroy method is done from cops->put().
1288 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001289
1290 sch_tree_unlock(sch);
1291 return 0;
1292}
1293
1294static void htb_put(struct Qdisc *sch, unsigned long arg)
1295{
Stephen Hemminger87990462006-08-10 23:35:16 -07001296 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001297
1298 if (--cl->refcnt == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -07001299 htb_destroy_class(sch, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001300}
1301
Stephen Hemminger87990462006-08-10 23:35:16 -07001302static int htb_change_class(struct Qdisc *sch, u32 classid,
Patrick McHardy1e904742008-01-22 22:11:17 -08001303 u32 parentid, struct nlattr **tca,
Stephen Hemminger87990462006-08-10 23:35:16 -07001304 unsigned long *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001305{
1306 int err = -EINVAL;
1307 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001308 struct htb_class *cl = (struct htb_class *)*arg, *parent;
Patrick McHardy1e904742008-01-22 22:11:17 -08001309 struct nlattr *opt = tca[TCA_OPTIONS];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001310 struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
Changli Gaoe18434c2010-09-30 06:17:44 +00001311 struct nlattr *tb[__TCA_HTB_MAX];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001312 struct tc_htb_opt *hopt;
1313
1314 /* extract all subattrs from opt attr */
Patrick McHardycee63722008-01-23 20:33:32 -08001315 if (!opt)
1316 goto failure;
1317
Changli Gaoe18434c2010-09-30 06:17:44 +00001318 err = nla_parse_nested(tb, TCA_HTB_MAX, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -08001319 if (err < 0)
1320 goto failure;
1321
1322 err = -EINVAL;
Patrick McHardy27a34212008-01-23 20:35:39 -08001323 if (tb[TCA_HTB_PARMS] == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001324 goto failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001325
Stephen Hemminger87990462006-08-10 23:35:16 -07001326 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001327
Patrick McHardy1e904742008-01-22 22:11:17 -08001328 hopt = nla_data(tb[TCA_HTB_PARMS]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001329
Patrick McHardy1e904742008-01-22 22:11:17 -08001330 rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB]);
1331 ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB]);
Stephen Hemminger87990462006-08-10 23:35:16 -07001332 if (!rtab || !ctab)
1333 goto failure;
1334
1335 if (!cl) { /* new class */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001336 struct Qdisc *new_q;
Stephen Hemminger3696f622006-08-10 23:36:01 -07001337 int prio;
Patrick McHardyee39e102007-07-02 22:48:13 -07001338 struct {
Patrick McHardy1e904742008-01-22 22:11:17 -08001339 struct nlattr nla;
Patrick McHardyee39e102007-07-02 22:48:13 -07001340 struct gnet_estimator opt;
1341 } est = {
Patrick McHardy1e904742008-01-22 22:11:17 -08001342 .nla = {
1343 .nla_len = nla_attr_size(sizeof(est.opt)),
1344 .nla_type = TCA_RATE,
Patrick McHardyee39e102007-07-02 22:48:13 -07001345 },
1346 .opt = {
1347 /* 4s interval, 16s averaging constant */
1348 .interval = 2,
1349 .ewma_log = 2,
1350 },
1351 };
Stephen Hemminger3696f622006-08-10 23:36:01 -07001352
Linus Torvalds1da177e2005-04-16 15:20:36 -07001353 /* check for valid classid */
Joe Perchesf64f9e72009-11-29 16:55:45 -08001354 if (!classid || TC_H_MAJ(classid ^ sch->handle) ||
1355 htb_find(classid, sch))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001356 goto failure;
1357
1358 /* check maximal depth */
1359 if (parent && parent->parent && parent->parent->level < 2) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001360 pr_err("htb: tree is too deep\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001361 goto failure;
1362 }
1363 err = -ENOBUFS;
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001364 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1365 if (!cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001366 goto failure;
Stephen Hemminger87990462006-08-10 23:35:16 -07001367
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001368 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1369 qdisc_root_sleeping_lock(sch),
1370 tca[TCA_RATE] ? : &est.nla);
1371 if (err) {
1372 kfree(cl);
1373 goto failure;
1374 }
1375
Linus Torvalds1da177e2005-04-16 15:20:36 -07001376 cl->refcnt = 1;
Patrick McHardy42077592008-07-05 23:22:53 -07001377 cl->children = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001378 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
Stephen Hemminger3696f622006-08-10 23:36:01 -07001379 RB_CLEAR_NODE(&cl->pq_node);
1380
1381 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1382 RB_CLEAR_NODE(&cl->node[prio]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001383
1384 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001385 * so that can't be used inside of sch_tree_lock
1386 * -- thanks to Karlis Peisenieks
1387 */
Changli Gao3511c912010-10-16 13:04:08 +00001388 new_q = qdisc_create_dflt(sch->dev_queue,
David S. Millerbb949fb2008-07-08 16:55:56 -07001389 &pfifo_qdisc_ops, classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001390 sch_tree_lock(sch);
1391 if (parent && !parent->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001392 unsigned int qlen = parent->un.leaf.q->q.qlen;
1393
Linus Torvalds1da177e2005-04-16 15:20:36 -07001394 /* turn parent into inner node */
Patrick McHardy256d61b2006-11-29 17:37:05 -08001395 qdisc_reset(parent->un.leaf.q);
1396 qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen);
Stephen Hemminger87990462006-08-10 23:35:16 -07001397 qdisc_destroy(parent->un.leaf.q);
1398 if (parent->prio_activity)
1399 htb_deactivate(q, parent);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001400
1401 /* remove from evt list because of level change */
1402 if (parent->cmode != HTB_CAN_SEND) {
Stephen Hemminger3696f622006-08-10 23:36:01 -07001403 htb_safe_rb_erase(&parent->pq_node, q->wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001404 parent->cmode = HTB_CAN_SEND;
1405 }
1406 parent->level = (parent->parent ? parent->parent->level
Stephen Hemminger87990462006-08-10 23:35:16 -07001407 : TC_HTB_MAXDEPTH) - 1;
1408 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001409 }
1410 /* leaf (we) needs elementary qdisc */
1411 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1412
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001413 cl->common.classid = classid;
Stephen Hemminger87990462006-08-10 23:35:16 -07001414 cl->parent = parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001415
1416 /* set class to be in HTB_CAN_SEND state */
1417 cl->tokens = hopt->buffer;
1418 cl->ctokens = hopt->cbuffer;
Patrick McHardy00c04af2007-03-16 01:23:02 -07001419 cl->mbuffer = 60 * PSCHED_TICKS_PER_SEC; /* 1min */
Patrick McHardy3bebcda2007-03-23 11:29:25 -07001420 cl->t_c = psched_get_time();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001421 cl->cmode = HTB_CAN_SEND;
1422
1423 /* attach to the hash list and parent's family */
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001424 qdisc_class_hash_insert(&q->clhash, &cl->common);
Patrick McHardy42077592008-07-05 23:22:53 -07001425 if (parent)
1426 parent->children++;
Patrick McHardyee39e102007-07-02 22:48:13 -07001427 } else {
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001428 if (tca[TCA_RATE]) {
1429 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1430 qdisc_root_sleeping_lock(sch),
1431 tca[TCA_RATE]);
1432 if (err)
1433 return err;
1434 }
Stephen Hemminger87990462006-08-10 23:35:16 -07001435 sch_tree_lock(sch);
Patrick McHardyee39e102007-07-02 22:48:13 -07001436 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001437
1438 /* it used to be a nasty bug here, we have to check that node
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001439 * is really leaf before changing cl->un.leaf !
1440 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001441 if (!cl->level) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001442 cl->quantum = rtab->rate.rate / q->rate2quantum;
1443 if (!hopt->quantum && cl->quantum < 1000) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001444 pr_warning(
Stephen Hemminger87990462006-08-10 23:35:16 -07001445 "HTB: quantum of class %X is small. Consider r2q change.\n",
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001446 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001447 cl->quantum = 1000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001448 }
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001449 if (!hopt->quantum && cl->quantum > 200000) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001450 pr_warning(
Stephen Hemminger87990462006-08-10 23:35:16 -07001451 "HTB: quantum of class %X is big. Consider r2q change.\n",
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001452 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001453 cl->quantum = 200000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001454 }
1455 if (hopt->quantum)
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001456 cl->quantum = hopt->quantum;
1457 if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO)
1458 cl->prio = TC_HTB_NUMPRIO - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001459 }
1460
1461 cl->buffer = hopt->buffer;
1462 cl->cbuffer = hopt->cbuffer;
Stephen Hemminger87990462006-08-10 23:35:16 -07001463 if (cl->rate)
1464 qdisc_put_rtab(cl->rate);
1465 cl->rate = rtab;
1466 if (cl->ceil)
1467 qdisc_put_rtab(cl->ceil);
1468 cl->ceil = ctab;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001469 sch_tree_unlock(sch);
1470
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001471 qdisc_class_hash_grow(sch, &q->clhash);
1472
Linus Torvalds1da177e2005-04-16 15:20:36 -07001473 *arg = (unsigned long)cl;
1474 return 0;
1475
1476failure:
Stephen Hemminger87990462006-08-10 23:35:16 -07001477 if (rtab)
1478 qdisc_put_rtab(rtab);
1479 if (ctab)
1480 qdisc_put_rtab(ctab);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001481 return err;
1482}
1483
1484static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1485{
1486 struct htb_sched *q = qdisc_priv(sch);
1487 struct htb_class *cl = (struct htb_class *)arg;
1488 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001489
Linus Torvalds1da177e2005-04-16 15:20:36 -07001490 return fl;
1491}
1492
1493static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
Stephen Hemminger87990462006-08-10 23:35:16 -07001494 u32 classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001495{
Stephen Hemminger87990462006-08-10 23:35:16 -07001496 struct htb_class *cl = htb_find(classid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001497
Linus Torvalds1da177e2005-04-16 15:20:36 -07001498 /*if (cl && !cl->level) return 0;
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001499 * The line above used to be there to prevent attaching filters to
1500 * leaves. But at least tc_index filter uses this just to get class
1501 * for other reasons so that we have to allow for it.
1502 * ----
1503 * 19.6.2002 As Werner explained it is ok - bind filter is just
1504 * another way to "lock" the class - unlike "get" this lock can
1505 * be broken by class during destroy IIUC.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001506 */
Stephen Hemminger87990462006-08-10 23:35:16 -07001507 if (cl)
1508 cl->filter_cnt++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001509 return (unsigned long)cl;
1510}
1511
1512static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1513{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001514 struct htb_class *cl = (struct htb_class *)arg;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001515
Stephen Hemminger87990462006-08-10 23:35:16 -07001516 if (cl)
1517 cl->filter_cnt--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001518}
1519
1520static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1521{
1522 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001523 struct htb_class *cl;
1524 struct hlist_node *n;
1525 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001526
1527 if (arg->stop)
1528 return;
1529
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001530 for (i = 0; i < q->clhash.hashsize; i++) {
1531 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001532 if (arg->count < arg->skip) {
1533 arg->count++;
1534 continue;
1535 }
1536 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1537 arg->stop = 1;
1538 return;
1539 }
1540 arg->count++;
1541 }
1542 }
1543}
1544
Eric Dumazet20fea082007-11-14 01:44:41 -08001545static const struct Qdisc_class_ops htb_class_ops = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001546 .graft = htb_graft,
1547 .leaf = htb_leaf,
Patrick McHardy256d61b2006-11-29 17:37:05 -08001548 .qlen_notify = htb_qlen_notify,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001549 .get = htb_get,
1550 .put = htb_put,
1551 .change = htb_change_class,
1552 .delete = htb_delete,
1553 .walk = htb_walk,
1554 .tcf_chain = htb_find_tcf,
1555 .bind_tcf = htb_bind_filter,
1556 .unbind_tcf = htb_unbind_filter,
1557 .dump = htb_dump_class,
1558 .dump_stats = htb_dump_class_stats,
1559};
1560
Eric Dumazet20fea082007-11-14 01:44:41 -08001561static struct Qdisc_ops htb_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001562 .cl_ops = &htb_class_ops,
1563 .id = "htb",
1564 .priv_size = sizeof(struct htb_sched),
1565 .enqueue = htb_enqueue,
1566 .dequeue = htb_dequeue,
Jarek Poplawski77be1552008-10-31 00:47:01 -07001567 .peek = qdisc_peek_dequeued,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001568 .drop = htb_drop,
1569 .init = htb_init,
1570 .reset = htb_reset,
1571 .destroy = htb_destroy,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001572 .dump = htb_dump,
1573 .owner = THIS_MODULE,
1574};
1575
1576static int __init htb_module_init(void)
1577{
Stephen Hemminger87990462006-08-10 23:35:16 -07001578 return register_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001579}
Stephen Hemminger87990462006-08-10 23:35:16 -07001580static void __exit htb_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001581{
Stephen Hemminger87990462006-08-10 23:35:16 -07001582 unregister_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001583}
Stephen Hemminger87990462006-08-10 23:35:16 -07001584
Linus Torvalds1da177e2005-04-16 15:20:36 -07001585module_init(htb_module_init)
1586module_exit(htb_module_exit)
1587MODULE_LICENSE("GPL");