blob: 0b52b8de562c40db1bd4541a08389885af621cb2 [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
102 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 u32 last_ptr_id[TC_HTB_NUMPRIO];
106 } inner;
107 } un;
108 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
109 struct rb_node pq_node; /* node for event queue */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700110 psched_time_t pq_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700111
Stephen Hemminger87990462006-08-10 23:35:16 -0700112 int prio_activity; /* for which prios are we active */
113 enum htb_cmode cmode; /* current mode of the class */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114
Stephen Hemminger87990462006-08-10 23:35:16 -0700115 /* class attached filters */
116 struct tcf_proto *filter_list;
117 int filter_cnt;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700118
Stephen Hemminger87990462006-08-10 23:35:16 -0700119 /* token bucket parameters */
120 struct qdisc_rate_table *rate; /* rate table of the class itself */
121 struct qdisc_rate_table *ceil; /* ceiling rate (limits borrows too) */
122 long buffer, cbuffer; /* token bucket depth/rate */
123 psched_tdiff_t mbuffer; /* max wait time */
124 long tokens, ctokens; /* current number of tokens */
125 psched_time_t t_c; /* checkpoint time */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700126};
127
Stephen Hemminger87990462006-08-10 23:35:16 -0700128struct htb_sched {
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700129 struct Qdisc_class_hash clhash;
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700130 struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700131
Stephen Hemminger87990462006-08-10 23:35:16 -0700132 /* self list - roots of self generating tree */
133 struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
134 int row_mask[TC_HTB_MAXDEPTH];
135 struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
136 u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700137
Stephen Hemminger87990462006-08-10 23:35:16 -0700138 /* self wait list - roots of wait PQs per row */
139 struct rb_root wait_pq[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700140
Stephen Hemminger87990462006-08-10 23:35:16 -0700141 /* time of nearest event per level (row) */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700142 psched_time_t near_ev_cache[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143
Stephen Hemminger87990462006-08-10 23:35:16 -0700144 int defcls; /* class where unclassified flows go to */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700145
Stephen Hemminger87990462006-08-10 23:35:16 -0700146 /* filters for qdisc itself */
147 struct tcf_proto *filter_list;
Stephen Hemminger87990462006-08-10 23:35:16 -0700148
149 int rate2quantum; /* quant = rate / rate2quantum */
150 psched_time_t now; /* cached dequeue time */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700151 struct qdisc_watchdog watchdog;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152
Stephen Hemminger87990462006-08-10 23:35:16 -0700153 /* non shaped skbs; let them go directly thru */
154 struct sk_buff_head direct_queue;
155 int direct_qlen; /* max qlen of above */
156
157 long direct_pkts;
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800158
159#define HTB_WARN_TOOMANYEVENTS 0x1
160 unsigned int warned; /* only one warning */
Jarek Poplawski12247362009-02-01 01:13:22 -0800161 struct work_struct work;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700162};
163
Linus Torvalds1da177e2005-04-16 15:20:36 -0700164/* find class in global hash table using given handle */
Stephen Hemminger87990462006-08-10 23:35:16 -0700165static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700166{
167 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700168 struct Qdisc_class_common *clc;
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700169
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700170 clc = qdisc_class_find(&q->clhash, handle);
171 if (clc == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700172 return NULL;
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700173 return container_of(clc, struct htb_class, common);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174}
175
176/**
177 * htb_classify - classify a packet into class
178 *
179 * It returns NULL if the packet should be dropped or -1 if the packet
180 * should be passed directly thru. In all other cases leaf class is returned.
181 * We allow direct class selection by classid in priority. The we examine
182 * filters in qdisc and in inner nodes (if higher filter points to the inner
183 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900184 * internal fifo (direct). These packets then go directly thru. If we still
Linus Torvalds1da177e2005-04-16 15:20:36 -0700185 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
186 * then finish and return direct queue.
187 */
188#define HTB_DIRECT (struct htb_class*)-1
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189
Stephen Hemminger87990462006-08-10 23:35:16 -0700190static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
191 int *qerr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700192{
193 struct htb_sched *q = qdisc_priv(sch);
194 struct htb_class *cl;
195 struct tcf_result res;
196 struct tcf_proto *tcf;
197 int result;
198
199 /* allow to select class by setting skb->priority to valid classid;
200 note that nfmark can be used too by attaching filter fw with no
201 rules in it */
202 if (skb->priority == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700203 return HTB_DIRECT; /* X:0 (direct flow) selected */
204 if ((cl = htb_find(skb->priority, sch)) != NULL && cl->level == 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700205 return cl;
206
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700207 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208 tcf = q->filter_list;
209 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
210#ifdef CONFIG_NET_CLS_ACT
211 switch (result) {
212 case TC_ACT_QUEUED:
Stephen Hemminger87990462006-08-10 23:35:16 -0700213 case TC_ACT_STOLEN:
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700214 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700215 case TC_ACT_SHOT:
216 return NULL;
217 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700218#endif
Stephen Hemminger87990462006-08-10 23:35:16 -0700219 if ((cl = (void *)res.class) == NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700220 if (res.classid == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700221 return HTB_DIRECT; /* X:0 (direct flow) */
222 if ((cl = htb_find(res.classid, sch)) == NULL)
223 break; /* filter selected invalid classid */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700224 }
225 if (!cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700226 return cl; /* we hit leaf; return it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227
228 /* we have got inner class; apply inner filter chain */
229 tcf = cl->filter_list;
230 }
231 /* classification failed; try to use default class */
Stephen Hemminger87990462006-08-10 23:35:16 -0700232 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700233 if (!cl || cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700234 return HTB_DIRECT; /* bad default .. this is safe bet */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700235 return cl;
236}
237
Linus Torvalds1da177e2005-04-16 15:20:36 -0700238/**
239 * htb_add_to_id_tree - adds class to the round robin list
240 *
241 * Routine adds class to the list (actually tree) sorted by classid.
242 * Make sure that class is not already on such list for given prio.
243 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700244static void htb_add_to_id_tree(struct rb_root *root,
245 struct htb_class *cl, int prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700246{
247 struct rb_node **p = &root->rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700248
Linus Torvalds1da177e2005-04-16 15:20:36 -0700249 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700250 struct htb_class *c;
251 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700252 c = rb_entry(parent, struct htb_class, node[prio]);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700253
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700254 if (cl->common.classid > c->common.classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700255 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700256 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700257 p = &parent->rb_left;
258 }
259 rb_link_node(&cl->node[prio], parent, p);
260 rb_insert_color(&cl->node[prio], root);
261}
262
263/**
264 * htb_add_to_wait_tree - adds class to the event queue with delay
265 *
266 * The class is added to priority event queue to indicate that class will
267 * change its mode in cl->pq_key microseconds. Make sure that class is not
268 * already in the queue.
269 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700270static void htb_add_to_wait_tree(struct htb_sched *q,
271 struct htb_class *cl, long delay)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700272{
273 struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700274
Patrick McHardyfb983d42007-03-16 01:22:39 -0700275 cl->pq_key = q->now + delay;
276 if (cl->pq_key == q->now)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700277 cl->pq_key++;
278
279 /* update the nearest event cache */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700280 if (q->near_ev_cache[cl->level] > cl->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700281 q->near_ev_cache[cl->level] = cl->pq_key;
Stephen Hemminger87990462006-08-10 23:35:16 -0700282
Linus Torvalds1da177e2005-04-16 15:20:36 -0700283 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700284 struct htb_class *c;
285 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700286 c = rb_entry(parent, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700287 if (cl->pq_key >= c->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700289 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700290 p = &parent->rb_left;
291 }
292 rb_link_node(&cl->pq_node, parent, p);
293 rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
294}
295
296/**
297 * htb_next_rb_node - finds next node in binary tree
298 *
299 * When we are past last key we return NULL.
300 * Average complexity is 2 steps per call.
301 */
Stephen Hemminger3696f622006-08-10 23:36:01 -0700302static inline void htb_next_rb_node(struct rb_node **n)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700303{
304 *n = rb_next(*n);
305}
306
307/**
308 * htb_add_class_to_row - add class to its row
309 *
310 * The class is added to row at priorities marked in mask.
311 * It does nothing if mask == 0.
312 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700313static inline void htb_add_class_to_row(struct htb_sched *q,
314 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700316 q->row_mask[cl->level] |= mask;
317 while (mask) {
318 int prio = ffz(~mask);
319 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700320 htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700321 }
322}
323
Stephen Hemminger3696f622006-08-10 23:36:01 -0700324/* If this triggers, it is a bug in this code, but it need not be fatal */
325static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
326{
Ismail Donmez81771b32006-10-03 13:49:10 -0700327 if (RB_EMPTY_NODE(rb)) {
Stephen Hemminger3696f622006-08-10 23:36:01 -0700328 WARN_ON(1);
329 } else {
330 rb_erase(rb, root);
331 RB_CLEAR_NODE(rb);
332 }
333}
334
335
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336/**
337 * htb_remove_class_from_row - removes class from its row
338 *
339 * The class is removed from row at priorities marked in mask.
340 * It does nothing if mask == 0.
341 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700342static inline void htb_remove_class_from_row(struct htb_sched *q,
343 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344{
345 int m = 0;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700346
Linus Torvalds1da177e2005-04-16 15:20:36 -0700347 while (mask) {
348 int prio = ffz(~mask);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700349
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700351 if (q->ptr[cl->level][prio] == cl->node + prio)
352 htb_next_rb_node(q->ptr[cl->level] + prio);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700353
354 htb_safe_rb_erase(cl->node + prio, q->row[cl->level] + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700355 if (!q->row[cl->level][prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700356 m |= 1 << prio;
357 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700358 q->row_mask[cl->level] &= ~m;
359}
360
361/**
362 * htb_activate_prios - creates active classe's feed chain
363 *
364 * The class is connected to ancestors and/or appropriate rows
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900365 * for priorities it is participating on. cl->cmode must be new
Linus Torvalds1da177e2005-04-16 15:20:36 -0700366 * (activated) mode. It does nothing if cl->prio_activity == 0.
367 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700368static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700369{
370 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700371 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700372
373 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700374 m = mask;
375 while (m) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376 int prio = ffz(~m);
377 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700378
Linus Torvalds1da177e2005-04-16 15:20:36 -0700379 if (p->un.inner.feed[prio].rb_node)
380 /* parent already has its feed in use so that
381 reset bit in mask as parent is already ok */
382 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700383
384 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700385 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700386 p->prio_activity |= mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700387 cl = p;
388 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700389
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390 }
391 if (cl->cmode == HTB_CAN_SEND && mask)
Stephen Hemminger87990462006-08-10 23:35:16 -0700392 htb_add_class_to_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700393}
394
395/**
396 * htb_deactivate_prios - remove class from feed chain
397 *
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900398 * cl->cmode must represent old mode (before deactivation). It does
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399 * nothing if cl->prio_activity == 0. Class is removed from all feed
400 * chains and rows.
401 */
402static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
403{
404 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700405 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700406
407 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700408 m = mask;
409 mask = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700410 while (m) {
411 int prio = ffz(~m);
412 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700413
414 if (p->un.inner.ptr[prio] == cl->node + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700415 /* we are removing child which is pointed to from
416 parent feed - forget the pointer but remember
417 classid */
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700418 p->un.inner.last_ptr_id[prio] = cl->common.classid;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700419 p->un.inner.ptr[prio] = NULL;
420 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700421
Stephen Hemminger3696f622006-08-10 23:36:01 -0700422 htb_safe_rb_erase(cl->node + prio, p->un.inner.feed + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700423
424 if (!p->un.inner.feed[prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425 mask |= 1 << prio;
426 }
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700427
Linus Torvalds1da177e2005-04-16 15:20:36 -0700428 p->prio_activity &= ~mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700429 cl = p;
430 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700431
Linus Torvalds1da177e2005-04-16 15:20:36 -0700432 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700433 if (cl->cmode == HTB_CAN_SEND && mask)
434 htb_remove_class_from_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700435}
436
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700437static inline long htb_lowater(const struct htb_class *cl)
438{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700439 if (htb_hysteresis)
440 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
441 else
442 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700443}
444static inline long htb_hiwater(const struct htb_class *cl)
445{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700446 if (htb_hysteresis)
447 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
448 else
449 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700450}
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700451
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700452
Linus Torvalds1da177e2005-04-16 15:20:36 -0700453/**
454 * htb_class_mode - computes and returns current class mode
455 *
456 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
457 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900458 * from now to time when cl will change its state.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700459 * Also it is worth to note that class mode doesn't change simply
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900460 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
Linus Torvalds1da177e2005-04-16 15:20:36 -0700461 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
462 * mode transitions per time unit. The speed gain is about 1/6.
463 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700464static inline enum htb_cmode
465htb_class_mode(struct htb_class *cl, long *diff)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700466{
Stephen Hemminger87990462006-08-10 23:35:16 -0700467 long toks;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700468
Stephen Hemminger87990462006-08-10 23:35:16 -0700469 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
470 *diff = -toks;
471 return HTB_CANT_SEND;
472 }
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700473
Stephen Hemminger87990462006-08-10 23:35:16 -0700474 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
475 return HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700476
Stephen Hemminger87990462006-08-10 23:35:16 -0700477 *diff = -toks;
478 return HTB_MAY_BORROW;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700479}
480
481/**
482 * htb_change_class_mode - changes classe's mode
483 *
484 * This should be the only way how to change classe's mode under normal
485 * cirsumstances. Routine will update feed lists linkage, change mode
486 * and add class to the wait event queue if appropriate. New mode should
487 * be different from old one and cl->pq_key has to be valid if changing
488 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
489 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700490static void
Linus Torvalds1da177e2005-04-16 15:20:36 -0700491htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
Stephen Hemminger87990462006-08-10 23:35:16 -0700492{
493 enum htb_cmode new_mode = htb_class_mode(cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700494
495 if (new_mode == cl->cmode)
Stephen Hemminger87990462006-08-10 23:35:16 -0700496 return;
497
498 if (cl->prio_activity) { /* not necessary: speed optimization */
499 if (cl->cmode != HTB_CANT_SEND)
500 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700501 cl->cmode = new_mode;
Stephen Hemminger87990462006-08-10 23:35:16 -0700502 if (new_mode != HTB_CANT_SEND)
503 htb_activate_prios(q, cl);
504 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505 cl->cmode = new_mode;
506}
507
508/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900509 * htb_activate - inserts leaf cl into appropriate active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510 *
511 * Routine learns (new) priority of leaf and activates feed chain
512 * for the prio. It can be called on already active leaf safely.
513 * It also adds leaf into droplist.
514 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700515static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700516{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700517 WARN_ON(cl->level || !cl->un.leaf.q || !cl->un.leaf.q->q.qlen);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700518
Linus Torvalds1da177e2005-04-16 15:20:36 -0700519 if (!cl->prio_activity) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800520 cl->prio_activity = 1 << cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700521 htb_activate_prios(q, cl);
522 list_add_tail(&cl->un.leaf.drop_list,
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800523 q->drops + cl->prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700524 }
525}
526
527/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900528 * htb_deactivate - remove leaf cl from active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700529 *
530 * Make sure that leaf is active. In the other words it can't be called
531 * with non-active leaf. It also removes class from the drop list.
532 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700533static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700534{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700535 WARN_ON(!cl->prio_activity);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700536
Stephen Hemminger87990462006-08-10 23:35:16 -0700537 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700538 cl->prio_activity = 0;
539 list_del_init(&cl->un.leaf.drop_list);
540}
541
542static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
543{
Jarek Poplawskif30ab412008-11-13 22:56:30 -0800544 int uninitialized_var(ret);
Stephen Hemminger87990462006-08-10 23:35:16 -0700545 struct htb_sched *q = qdisc_priv(sch);
546 struct htb_class *cl = htb_classify(skb, sch, &ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700547
Stephen Hemminger87990462006-08-10 23:35:16 -0700548 if (cl == HTB_DIRECT) {
549 /* enqueue to helper queue */
550 if (q->direct_queue.qlen < q->direct_qlen) {
551 __skb_queue_tail(&q->direct_queue, skb);
552 q->direct_pkts++;
553 } else {
554 kfree_skb(skb);
555 sch->qstats.drops++;
556 return NET_XMIT_DROP;
557 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700558#ifdef CONFIG_NET_CLS_ACT
Stephen Hemminger87990462006-08-10 23:35:16 -0700559 } else if (!cl) {
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700560 if (ret & __NET_XMIT_BYPASS)
Stephen Hemminger87990462006-08-10 23:35:16 -0700561 sch->qstats.drops++;
562 kfree_skb(skb);
563 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564#endif
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700565 } else if ((ret = qdisc_enqueue(skb, cl->un.leaf.q)) != NET_XMIT_SUCCESS) {
566 if (net_xmit_drop_count(ret)) {
567 sch->qstats.drops++;
568 cl->qstats.drops++;
569 }
David S. Miller69747652008-08-17 23:55:36 -0700570 return ret;
Stephen Hemminger87990462006-08-10 23:35:16 -0700571 } else {
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700572 cl->bstats.packets +=
573 skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700574 cl->bstats.bytes += qdisc_pkt_len(skb);
Stephen Hemminger87990462006-08-10 23:35:16 -0700575 htb_activate(q, cl);
576 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577
Stephen Hemminger87990462006-08-10 23:35:16 -0700578 sch->q.qlen++;
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700579 sch->bstats.packets += skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700580 sch->bstats.bytes += qdisc_pkt_len(skb);
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
651 /* update byte stats except for leaves which are already updated */
652 if (cl->level) {
653 cl->bstats.bytes += bytes;
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700654 cl->bstats.packets += skb_is_gso(skb)?
655 skb_shinfo(skb)->gso_segs:1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700656 }
657 cl = cl->parent;
658 }
659}
660
661/**
662 * htb_do_events - make mode changes to classes at the level
663 *
Patrick McHardyfb983d42007-03-16 01:22:39 -0700664 * Scans event queue for pending events and applies them. Returns time of
Jarek Poplawski12247362009-02-01 01:13:22 -0800665 * next pending event (0 for no event in pq, q->now for too many events).
Patrick McHardyfb983d42007-03-16 01:22:39 -0700666 * Note: Applied are events whose have cl->pq_key <= q->now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700667 */
Jarek Poplawskia73be042009-01-12 21:54:40 -0800668static psched_time_t htb_do_events(struct htb_sched *q, int level,
669 unsigned long start)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670{
Martin Devera8f3ea332008-03-23 22:00:38 -0700671 /* don't run for longer than 2 jiffies; 2 is used instead of
672 1 to simplify things when jiffy is going to be incremented
673 too soon */
Jarek Poplawskia73be042009-01-12 21:54:40 -0800674 unsigned long stop_at = start + 2;
Martin Devera8f3ea332008-03-23 22:00:38 -0700675 while (time_before(jiffies, stop_at)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700676 struct htb_class *cl;
677 long diff;
Akinbou Mita30bdbe32006-10-12 01:52:05 -0700678 struct rb_node *p = rb_first(&q->wait_pq[level]);
679
Stephen Hemminger87990462006-08-10 23:35:16 -0700680 if (!p)
681 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700682
683 cl = rb_entry(p, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700684 if (cl->pq_key > q->now)
685 return cl->pq_key;
686
Stephen Hemminger3696f622006-08-10 23:36:01 -0700687 htb_safe_rb_erase(p, q->wait_pq + level);
Patrick McHardy03cc45c2007-03-23 11:29:11 -0700688 diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
Stephen Hemminger87990462006-08-10 23:35:16 -0700689 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700690 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700691 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700692 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800693
694 /* too much load - let's continue after a break for scheduling */
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800695 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
696 printk(KERN_WARNING "htb: too many events!\n");
697 q->warned |= HTB_WARN_TOOMANYEVENTS;
698 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800699
700 return q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700701}
702
703/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
704 is no such one exists. */
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
Linus Torvalds1da177e2005-04-16 15:20:36 -0700748 the original or next ptr */
Stephen Hemminger87990462006-08-10 23:35:16 -0700749 *sp->pptr =
750 htb_id_find_next_upper(prio, sp->root, *sp->pid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700751 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700752 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
753 can become out of date quickly */
754 if (!*sp->pptr) { /* we are at right end; rewind & go up */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700755 *sp->pptr = sp->root;
Stephen Hemminger87990462006-08-10 23:35:16 -0700756 while ((*sp->pptr)->rb_left)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757 *sp->pptr = (*sp->pptr)->rb_left;
758 if (sp > stk) {
759 sp--;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800760 if (!*sp->pptr) {
761 WARN_ON(1);
Stephen Hemminger87990462006-08-10 23:35:16 -0700762 return NULL;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800763 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700764 htb_next_rb_node(sp->pptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700765 }
766 } else {
767 struct htb_class *cl;
Stephen Hemminger87990462006-08-10 23:35:16 -0700768 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
769 if (!cl->level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700770 return cl;
771 (++sp)->root = cl->un.inner.feed[prio].rb_node;
Stephen Hemminger87990462006-08-10 23:35:16 -0700772 sp->pptr = cl->un.inner.ptr + prio;
773 sp->pid = cl->un.inner.last_ptr_id + prio;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700774 }
775 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700776 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700777 return NULL;
778}
779
780/* dequeues packet at given priority and level; call only if
781 you are sure that there is active class at prio/level */
Stephen Hemminger87990462006-08-10 23:35:16 -0700782static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
783 int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700784{
785 struct sk_buff *skb = NULL;
Stephen Hemminger87990462006-08-10 23:35:16 -0700786 struct htb_class *cl, *start;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700787 /* look initial class up in the row */
Stephen Hemminger87990462006-08-10 23:35:16 -0700788 start = cl = htb_lookup_leaf(q->row[level] + prio, prio,
789 q->ptr[level] + prio,
790 q->last_ptr_id[level] + prio);
791
Linus Torvalds1da177e2005-04-16 15:20:36 -0700792 do {
793next:
Jarek Poplawski512bb432008-12-09 22:35:02 -0800794 if (unlikely(!cl))
Stephen Hemminger87990462006-08-10 23:35:16 -0700795 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700796
797 /* class can be empty - it is unlikely but can be true if leaf
798 qdisc drops packets in enqueue routine or if someone used
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900799 graft operation on the leaf since last dequeue;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700800 simply deactivate and skip such class */
801 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
802 struct htb_class *next;
Stephen Hemminger87990462006-08-10 23:35:16 -0700803 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700804
805 /* row/level might become empty */
806 if ((q->row_mask[level] & (1 << prio)) == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -0700807 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700808
Stephen Hemminger87990462006-08-10 23:35:16 -0700809 next = htb_lookup_leaf(q->row[level] + prio,
810 prio, q->ptr[level] + prio,
811 q->last_ptr_id[level] + prio);
812
813 if (cl == start) /* fix start if we just deleted it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700814 start = next;
815 cl = next;
816 goto next;
817 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700818
819 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
820 if (likely(skb != NULL))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700821 break;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800822
Jarek Poplawskib00355d2009-02-01 01:12:42 -0800823 qdisc_warn_nonwc("htb", cl->un.leaf.q);
Stephen Hemminger87990462006-08-10 23:35:16 -0700824 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
825 ptr[0]) + prio);
826 cl = htb_lookup_leaf(q->row[level] + prio, prio,
827 q->ptr[level] + prio,
828 q->last_ptr_id[level] + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700829
830 } while (cl != start);
831
832 if (likely(skb != NULL)) {
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700833 cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb);
834 if (cl->un.leaf.deficit[level] < 0) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800835 cl->un.leaf.deficit[level] += cl->quantum;
Stephen Hemminger87990462006-08-10 23:35:16 -0700836 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
837 ptr[0]) + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838 }
839 /* this used to be after charge_class but this constelation
840 gives us slightly better performance */
841 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700842 htb_deactivate(q, cl);
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700843 htb_charge_class(q, cl, level, skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844 }
845 return skb;
846}
847
Linus Torvalds1da177e2005-04-16 15:20:36 -0700848static struct sk_buff *htb_dequeue(struct Qdisc *sch)
849{
850 struct sk_buff *skb = NULL;
851 struct htb_sched *q = qdisc_priv(sch);
852 int level;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700853 psched_time_t next_event;
Jarek Poplawskia73be042009-01-12 21:54:40 -0800854 unsigned long start_at;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700855
856 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
Stephen Hemminger87990462006-08-10 23:35:16 -0700857 skb = __skb_dequeue(&q->direct_queue);
858 if (skb != NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700859 sch->flags &= ~TCQ_F_THROTTLED;
860 sch->q.qlen--;
861 return skb;
862 }
863
Stephen Hemminger87990462006-08-10 23:35:16 -0700864 if (!sch->q.qlen)
865 goto fin;
Patrick McHardy3bebcda2007-03-23 11:29:25 -0700866 q->now = psched_get_time();
Jarek Poplawskia73be042009-01-12 21:54:40 -0800867 start_at = jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700868
Patrick McHardyfb983d42007-03-16 01:22:39 -0700869 next_event = q->now + 5 * PSCHED_TICKS_PER_SEC;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800870
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
872 /* common case optimization - skip event handler quickly */
873 int m;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700874 psched_time_t event;
Stephen Hemminger87990462006-08-10 23:35:16 -0700875
Patrick McHardyfb983d42007-03-16 01:22:39 -0700876 if (q->now >= q->near_ev_cache[level]) {
Jarek Poplawskia73be042009-01-12 21:54:40 -0800877 event = htb_do_events(q, level, start_at);
Patrick McHardy2e4b3b02007-05-23 23:39:54 -0700878 if (!event)
879 event = q->now + PSCHED_TICKS_PER_SEC;
880 q->near_ev_cache[level] = event;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700881 } else
882 event = q->near_ev_cache[level];
883
Jarek Poplawskic0851342009-01-12 21:54:16 -0800884 if (next_event > event)
Patrick McHardyfb983d42007-03-16 01:22:39 -0700885 next_event = event;
886
Linus Torvalds1da177e2005-04-16 15:20:36 -0700887 m = ~q->row_mask[level];
888 while (m != (int)(-1)) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700889 int prio = ffz(m);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700890 m |= 1 << prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700891 skb = htb_dequeue_tree(q, prio, level);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892 if (likely(skb != NULL)) {
893 sch->q.qlen--;
894 sch->flags &= ~TCQ_F_THROTTLED;
895 goto fin;
896 }
897 }
898 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700899 sch->qstats.overlimits++;
Jarek Poplawski12247362009-02-01 01:13:22 -0800900 if (likely(next_event > q->now))
901 qdisc_watchdog_schedule(&q->watchdog, next_event);
902 else
903 schedule_work(&q->work);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700904fin:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700905 return skb;
906}
907
908/* try to drop from each class (by prio) until one succeed */
Stephen Hemminger87990462006-08-10 23:35:16 -0700909static unsigned int htb_drop(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700910{
911 struct htb_sched *q = qdisc_priv(sch);
912 int prio;
913
914 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
915 struct list_head *p;
Stephen Hemminger87990462006-08-10 23:35:16 -0700916 list_for_each(p, q->drops + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700917 struct htb_class *cl = list_entry(p, struct htb_class,
918 un.leaf.drop_list);
919 unsigned int len;
Stephen Hemminger87990462006-08-10 23:35:16 -0700920 if (cl->un.leaf.q->ops->drop &&
921 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700922 sch->q.qlen--;
923 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700924 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700925 return len;
926 }
927 }
928 }
929 return 0;
930}
931
932/* reset all classes */
933/* always caled under BH & queue lock */
Stephen Hemminger87990462006-08-10 23:35:16 -0700934static void htb_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700935{
936 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700937 struct htb_class *cl;
938 struct hlist_node *n;
939 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700940
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700941 for (i = 0; i < q->clhash.hashsize; i++) {
942 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700943 if (cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700944 memset(&cl->un.inner, 0, sizeof(cl->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700945 else {
Stephen Hemminger87990462006-08-10 23:35:16 -0700946 if (cl->un.leaf.q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700947 qdisc_reset(cl->un.leaf.q);
948 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
949 }
950 cl->prio_activity = 0;
951 cl->cmode = HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700952
953 }
954 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700955 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700956 __skb_queue_purge(&q->direct_queue);
957 sch->q.qlen = 0;
Stephen Hemminger87990462006-08-10 23:35:16 -0700958 memset(q->row, 0, sizeof(q->row));
959 memset(q->row_mask, 0, sizeof(q->row_mask));
960 memset(q->wait_pq, 0, sizeof(q->wait_pq));
961 memset(q->ptr, 0, sizeof(q->ptr));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700962 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -0700963 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700964}
965
Patrick McHardy27a34212008-01-23 20:35:39 -0800966static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
967 [TCA_HTB_PARMS] = { .len = sizeof(struct tc_htb_opt) },
968 [TCA_HTB_INIT] = { .len = sizeof(struct tc_htb_glob) },
969 [TCA_HTB_CTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
970 [TCA_HTB_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
971};
972
Jarek Poplawski12247362009-02-01 01:13:22 -0800973static void htb_work_func(struct work_struct *work)
974{
975 struct htb_sched *q = container_of(work, struct htb_sched, work);
976 struct Qdisc *sch = q->watchdog.qdisc;
977
978 __netif_schedule(qdisc_root(sch));
979}
980
Patrick McHardy1e904742008-01-22 22:11:17 -0800981static int htb_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700982{
983 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800984 struct nlattr *tb[TCA_HTB_INIT + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700985 struct tc_htb_glob *gopt;
Patrick McHardycee63722008-01-23 20:33:32 -0800986 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700987 int i;
Patrick McHardycee63722008-01-23 20:33:32 -0800988
989 if (!opt)
990 return -EINVAL;
991
Patrick McHardy27a34212008-01-23 20:35:39 -0800992 err = nla_parse_nested(tb, TCA_HTB_INIT, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -0800993 if (err < 0)
994 return err;
995
Patrick McHardy27a34212008-01-23 20:35:39 -0800996 if (tb[TCA_HTB_INIT] == NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700997 printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n");
998 return -EINVAL;
999 }
Patrick McHardy1e904742008-01-22 22:11:17 -08001000 gopt = nla_data(tb[TCA_HTB_INIT]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001001 if (gopt->version != HTB_VER >> 16) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001002 printk(KERN_ERR
1003 "HTB: need tc/htb version %d (minor is %d), you have %d\n",
1004 HTB_VER >> 16, HTB_VER & 0xffff, gopt->version);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001005 return -EINVAL;
1006 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001007
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001008 err = qdisc_class_hash_init(&q->clhash);
1009 if (err < 0)
1010 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001011 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -07001012 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001013
Patrick McHardyfb983d42007-03-16 01:22:39 -07001014 qdisc_watchdog_init(&q->watchdog, sch);
Jarek Poplawski12247362009-02-01 01:13:22 -08001015 INIT_WORK(&q->work, htb_work_func);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001016 skb_queue_head_init(&q->direct_queue);
1017
David S. Miller5ce2d482008-07-08 17:06:30 -07001018 q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
Stephen Hemminger87990462006-08-10 23:35:16 -07001019 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001020 q->direct_qlen = 2;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001021
Linus Torvalds1da177e2005-04-16 15:20:36 -07001022 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1023 q->rate2quantum = 1;
1024 q->defcls = gopt->defcls;
1025
1026 return 0;
1027}
1028
1029static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1030{
Jarek Poplawski102396a2008-08-29 14:21:52 -07001031 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001032 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001033 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001034 struct tc_htb_glob gopt;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001035
David S. Miller7698b4f2008-07-16 01:42:40 -07001036 spin_lock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001037
1038 gopt.direct_pkts = q->direct_pkts;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001039 gopt.version = HTB_VER;
1040 gopt.rate2quantum = q->rate2quantum;
1041 gopt.defcls = q->defcls;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001042 gopt.debug = 0;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001043
1044 nest = nla_nest_start(skb, TCA_OPTIONS);
1045 if (nest == NULL)
1046 goto nla_put_failure;
Patrick McHardy1e904742008-01-22 22:11:17 -08001047 NLA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001048 nla_nest_end(skb, nest);
1049
David S. Miller7698b4f2008-07-16 01:42:40 -07001050 spin_unlock_bh(root_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001051 return skb->len;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001052
Patrick McHardy1e904742008-01-22 22:11:17 -08001053nla_put_failure:
David S. Miller7698b4f2008-07-16 01:42:40 -07001054 spin_unlock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001055 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001056 return -1;
1057}
1058
1059static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
Stephen Hemminger87990462006-08-10 23:35:16 -07001060 struct sk_buff *skb, struct tcmsg *tcm)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001061{
Stephen Hemminger87990462006-08-10 23:35:16 -07001062 struct htb_class *cl = (struct htb_class *)arg;
Jarek Poplawski102396a2008-08-29 14:21:52 -07001063 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001064 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001065 struct tc_htb_opt opt;
1066
David S. Miller7698b4f2008-07-16 01:42:40 -07001067 spin_lock_bh(root_lock);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001068 tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
1069 tcm->tcm_handle = cl->common.classid;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001070 if (!cl->level && cl->un.leaf.q)
1071 tcm->tcm_info = cl->un.leaf.q->handle;
1072
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001073 nest = nla_nest_start(skb, TCA_OPTIONS);
1074 if (nest == NULL)
1075 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001076
Stephen Hemminger87990462006-08-10 23:35:16 -07001077 memset(&opt, 0, sizeof(opt));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001078
Stephen Hemminger87990462006-08-10 23:35:16 -07001079 opt.rate = cl->rate->rate;
1080 opt.buffer = cl->buffer;
1081 opt.ceil = cl->ceil->rate;
1082 opt.cbuffer = cl->cbuffer;
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001083 opt.quantum = cl->quantum;
1084 opt.prio = cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -07001085 opt.level = cl->level;
Patrick McHardy1e904742008-01-22 22:11:17 -08001086 NLA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001087
1088 nla_nest_end(skb, nest);
David S. Miller7698b4f2008-07-16 01:42:40 -07001089 spin_unlock_bh(root_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001090 return skb->len;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001091
Patrick McHardy1e904742008-01-22 22:11:17 -08001092nla_put_failure:
David S. Miller7698b4f2008-07-16 01:42:40 -07001093 spin_unlock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001094 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001095 return -1;
1096}
1097
1098static int
Stephen Hemminger87990462006-08-10 23:35:16 -07001099htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001100{
Stephen Hemminger87990462006-08-10 23:35:16 -07001101 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001102
Linus Torvalds1da177e2005-04-16 15:20:36 -07001103 if (!cl->level && cl->un.leaf.q)
1104 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
1105 cl->xstats.tokens = cl->tokens;
1106 cl->xstats.ctokens = cl->ctokens;
1107
1108 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
Eric Dumazetd250a5f2009-10-02 10:32:18 +00001109 gnet_stats_copy_rate_est(d, NULL, &cl->rate_est) < 0 ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001110 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1111 return -1;
1112
1113 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1114}
1115
1116static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
Stephen Hemminger87990462006-08-10 23:35:16 -07001117 struct Qdisc **old)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001118{
Stephen Hemminger87990462006-08-10 23:35:16 -07001119 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001120
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001121 if (cl->level)
1122 return -EINVAL;
1123 if (new == NULL &&
1124 (new = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
1125 &pfifo_qdisc_ops,
1126 cl->common.classid)) == NULL)
1127 return -ENOBUFS;
1128
1129 sch_tree_lock(sch);
1130 *old = cl->un.leaf.q;
1131 cl->un.leaf.q = new;
1132 if (*old != NULL) {
1133 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1134 qdisc_reset(*old);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001135 }
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001136 sch_tree_unlock(sch);
1137 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001138}
1139
Stephen Hemminger87990462006-08-10 23:35:16 -07001140static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001141{
Stephen Hemminger87990462006-08-10 23:35:16 -07001142 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001143 return !cl->level ? cl->un.leaf.q : NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001144}
1145
Patrick McHardy256d61b2006-11-29 17:37:05 -08001146static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
1147{
1148 struct htb_class *cl = (struct htb_class *)arg;
1149
1150 if (cl->un.leaf.q->q.qlen == 0)
1151 htb_deactivate(qdisc_priv(sch), cl);
1152}
1153
Linus Torvalds1da177e2005-04-16 15:20:36 -07001154static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1155{
Stephen Hemminger87990462006-08-10 23:35:16 -07001156 struct htb_class *cl = htb_find(classid, sch);
1157 if (cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001158 cl->refcnt++;
1159 return (unsigned long)cl;
1160}
1161
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001162static inline int htb_parent_last_child(struct htb_class *cl)
1163{
1164 if (!cl->parent)
1165 /* the root class */
1166 return 0;
Patrick McHardy42077592008-07-05 23:22:53 -07001167 if (cl->parent->children > 1)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001168 /* not the last child */
1169 return 0;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001170 return 1;
1171}
1172
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001173static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl,
1174 struct Qdisc *new_q)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001175{
1176 struct htb_class *parent = cl->parent;
1177
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001178 WARN_ON(cl->level || !cl->un.leaf.q || cl->prio_activity);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001179
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001180 if (parent->cmode != HTB_CAN_SEND)
1181 htb_safe_rb_erase(&parent->pq_node, q->wait_pq + parent->level);
1182
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001183 parent->level = 0;
1184 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
1185 INIT_LIST_HEAD(&parent->un.leaf.drop_list);
1186 parent->un.leaf.q = new_q ? new_q : &noop_qdisc;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001187 parent->tokens = parent->buffer;
1188 parent->ctokens = parent->cbuffer;
Patrick McHardy3bebcda2007-03-23 11:29:25 -07001189 parent->t_c = psched_get_time();
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001190 parent->cmode = HTB_CAN_SEND;
1191}
1192
Stephen Hemminger87990462006-08-10 23:35:16 -07001193static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001194{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001195 if (!cl->level) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001196 WARN_ON(!cl->un.leaf.q);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001197 qdisc_destroy(cl->un.leaf.q);
1198 }
Patrick McHardyee39e102007-07-02 22:48:13 -07001199 gen_kill_estimator(&cl->bstats, &cl->rate_est);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001200 qdisc_put_rtab(cl->rate);
1201 qdisc_put_rtab(cl->ceil);
Stephen Hemminger87990462006-08-10 23:35:16 -07001202
Patrick McHardyff31ab52008-07-01 19:52:38 -07001203 tcf_destroy_chain(&cl->filter_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001204 kfree(cl);
1205}
1206
Stephen Hemminger87990462006-08-10 23:35:16 -07001207static void htb_destroy(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001208{
1209 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001210 struct hlist_node *n, *next;
1211 struct htb_class *cl;
1212 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001213
Jarek Poplawski12247362009-02-01 01:13:22 -08001214 cancel_work_sync(&q->work);
Patrick McHardyfb983d42007-03-16 01:22:39 -07001215 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001216 /* This line used to be after htb_destroy_class call below
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +09001217 and surprisingly it worked in 2.4. But it must precede it
Linus Torvalds1da177e2005-04-16 15:20:36 -07001218 because filter need its target class alive to be able to call
1219 unbind_filter on it (without Oops). */
Patrick McHardyff31ab52008-07-01 19:52:38 -07001220 tcf_destroy_chain(&q->filter_list);
Stephen Hemminger87990462006-08-10 23:35:16 -07001221
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001222 for (i = 0; i < q->clhash.hashsize; i++) {
1223 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001224 tcf_destroy_chain(&cl->filter_list);
1225 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001226 for (i = 0; i < q->clhash.hashsize; i++) {
1227 hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[i],
1228 common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001229 htb_destroy_class(sch, cl);
1230 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001231 qdisc_class_hash_destroy(&q->clhash);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001232 __skb_queue_purge(&q->direct_queue);
1233}
1234
1235static int htb_delete(struct Qdisc *sch, unsigned long arg)
1236{
1237 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001238 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy256d61b2006-11-29 17:37:05 -08001239 unsigned int qlen;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001240 struct Qdisc *new_q = NULL;
1241 int last_child = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001242
1243 // TODO: why don't allow to delete subtree ? references ? does
1244 // tc subsys quarantee us that in htb_destroy it holds no class
1245 // refs so that we can remove children safely there ?
Patrick McHardy42077592008-07-05 23:22:53 -07001246 if (cl->children || cl->filter_cnt)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001247 return -EBUSY;
Stephen Hemminger87990462006-08-10 23:35:16 -07001248
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001249 if (!cl->level && htb_parent_last_child(cl)) {
David S. Miller5ce2d482008-07-08 17:06:30 -07001250 new_q = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
David S. Millerbb949fb2008-07-08 16:55:56 -07001251 &pfifo_qdisc_ops,
1252 cl->parent->common.classid);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001253 last_child = 1;
1254 }
1255
Linus Torvalds1da177e2005-04-16 15:20:36 -07001256 sch_tree_lock(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001257
Patrick McHardy814a175e2006-11-29 17:34:50 -08001258 if (!cl->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001259 qlen = cl->un.leaf.q->q.qlen;
Patrick McHardy814a175e2006-11-29 17:34:50 -08001260 qdisc_reset(cl->un.leaf.q);
Patrick McHardy256d61b2006-11-29 17:37:05 -08001261 qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
Patrick McHardy814a175e2006-11-29 17:34:50 -08001262 }
1263
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001264 /* delete from hash and active; remainder in destroy_class */
1265 qdisc_class_hash_remove(&q->clhash, &cl->common);
Jarek Poplawski26b284d2008-08-13 15:16:43 -07001266 if (cl->parent)
1267 cl->parent->children--;
Patrick McHardyc38c83c2007-03-27 14:04:24 -07001268
Linus Torvalds1da177e2005-04-16 15:20:36 -07001269 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001270 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001271
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001272 if (cl->cmode != HTB_CAN_SEND)
1273 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
1274
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001275 if (last_child)
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001276 htb_parent_to_leaf(q, cl, new_q);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001277
Jarek Poplawski7cd0a632009-03-15 20:00:19 -07001278 BUG_ON(--cl->refcnt == 0);
1279 /*
1280 * This shouldn't happen: we "hold" one cops->get() when called
1281 * from tc_ctl_tclass; the destroy method is done from cops->put().
1282 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001283
1284 sch_tree_unlock(sch);
1285 return 0;
1286}
1287
1288static void htb_put(struct Qdisc *sch, unsigned long arg)
1289{
Stephen Hemminger87990462006-08-10 23:35:16 -07001290 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001291
1292 if (--cl->refcnt == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -07001293 htb_destroy_class(sch, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001294}
1295
Stephen Hemminger87990462006-08-10 23:35:16 -07001296static int htb_change_class(struct Qdisc *sch, u32 classid,
Patrick McHardy1e904742008-01-22 22:11:17 -08001297 u32 parentid, struct nlattr **tca,
Stephen Hemminger87990462006-08-10 23:35:16 -07001298 unsigned long *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001299{
1300 int err = -EINVAL;
1301 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001302 struct htb_class *cl = (struct htb_class *)*arg, *parent;
Patrick McHardy1e904742008-01-22 22:11:17 -08001303 struct nlattr *opt = tca[TCA_OPTIONS];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001304 struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
Patrick McHardy1e904742008-01-22 22:11:17 -08001305 struct nlattr *tb[TCA_HTB_RTAB + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001306 struct tc_htb_opt *hopt;
1307
1308 /* extract all subattrs from opt attr */
Patrick McHardycee63722008-01-23 20:33:32 -08001309 if (!opt)
1310 goto failure;
1311
Patrick McHardy27a34212008-01-23 20:35:39 -08001312 err = nla_parse_nested(tb, TCA_HTB_RTAB, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -08001313 if (err < 0)
1314 goto failure;
1315
1316 err = -EINVAL;
Patrick McHardy27a34212008-01-23 20:35:39 -08001317 if (tb[TCA_HTB_PARMS] == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001318 goto failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001319
Stephen Hemminger87990462006-08-10 23:35:16 -07001320 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001321
Patrick McHardy1e904742008-01-22 22:11:17 -08001322 hopt = nla_data(tb[TCA_HTB_PARMS]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001323
Patrick McHardy1e904742008-01-22 22:11:17 -08001324 rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB]);
1325 ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB]);
Stephen Hemminger87990462006-08-10 23:35:16 -07001326 if (!rtab || !ctab)
1327 goto failure;
1328
1329 if (!cl) { /* new class */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001330 struct Qdisc *new_q;
Stephen Hemminger3696f622006-08-10 23:36:01 -07001331 int prio;
Patrick McHardyee39e102007-07-02 22:48:13 -07001332 struct {
Patrick McHardy1e904742008-01-22 22:11:17 -08001333 struct nlattr nla;
Patrick McHardyee39e102007-07-02 22:48:13 -07001334 struct gnet_estimator opt;
1335 } est = {
Patrick McHardy1e904742008-01-22 22:11:17 -08001336 .nla = {
1337 .nla_len = nla_attr_size(sizeof(est.opt)),
1338 .nla_type = TCA_RATE,
Patrick McHardyee39e102007-07-02 22:48:13 -07001339 },
1340 .opt = {
1341 /* 4s interval, 16s averaging constant */
1342 .interval = 2,
1343 .ewma_log = 2,
1344 },
1345 };
Stephen Hemminger3696f622006-08-10 23:36:01 -07001346
Linus Torvalds1da177e2005-04-16 15:20:36 -07001347 /* check for valid classid */
Joe Perchesf64f9e72009-11-29 16:55:45 -08001348 if (!classid || TC_H_MAJ(classid ^ sch->handle) ||
1349 htb_find(classid, sch))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001350 goto failure;
1351
1352 /* check maximal depth */
1353 if (parent && parent->parent && parent->parent->level < 2) {
1354 printk(KERN_ERR "htb: tree is too deep\n");
1355 goto failure;
1356 }
1357 err = -ENOBUFS;
Panagiotis Issaris0da974f2006-07-21 14:51:30 -07001358 if ((cl = kzalloc(sizeof(*cl), GFP_KERNEL)) == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001359 goto failure;
Stephen Hemminger87990462006-08-10 23:35:16 -07001360
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001361 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1362 qdisc_root_sleeping_lock(sch),
1363 tca[TCA_RATE] ? : &est.nla);
1364 if (err) {
1365 kfree(cl);
1366 goto failure;
1367 }
1368
Linus Torvalds1da177e2005-04-16 15:20:36 -07001369 cl->refcnt = 1;
Patrick McHardy42077592008-07-05 23:22:53 -07001370 cl->children = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001371 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
Stephen Hemminger3696f622006-08-10 23:36:01 -07001372 RB_CLEAR_NODE(&cl->pq_node);
1373
1374 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1375 RB_CLEAR_NODE(&cl->node[prio]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001376
1377 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
1378 so that can't be used inside of sch_tree_lock
1379 -- thanks to Karlis Peisenieks */
David S. Miller5ce2d482008-07-08 17:06:30 -07001380 new_q = qdisc_create_dflt(qdisc_dev(sch), sch->dev_queue,
David S. Millerbb949fb2008-07-08 16:55:56 -07001381 &pfifo_qdisc_ops, classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001382 sch_tree_lock(sch);
1383 if (parent && !parent->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001384 unsigned int qlen = parent->un.leaf.q->q.qlen;
1385
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386 /* turn parent into inner node */
Patrick McHardy256d61b2006-11-29 17:37:05 -08001387 qdisc_reset(parent->un.leaf.q);
1388 qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen);
Stephen Hemminger87990462006-08-10 23:35:16 -07001389 qdisc_destroy(parent->un.leaf.q);
1390 if (parent->prio_activity)
1391 htb_deactivate(q, parent);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001392
1393 /* remove from evt list because of level change */
1394 if (parent->cmode != HTB_CAN_SEND) {
Stephen Hemminger3696f622006-08-10 23:36:01 -07001395 htb_safe_rb_erase(&parent->pq_node, q->wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001396 parent->cmode = HTB_CAN_SEND;
1397 }
1398 parent->level = (parent->parent ? parent->parent->level
Stephen Hemminger87990462006-08-10 23:35:16 -07001399 : TC_HTB_MAXDEPTH) - 1;
1400 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 }
1402 /* leaf (we) needs elementary qdisc */
1403 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1404
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001405 cl->common.classid = classid;
Stephen Hemminger87990462006-08-10 23:35:16 -07001406 cl->parent = parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001407
1408 /* set class to be in HTB_CAN_SEND state */
1409 cl->tokens = hopt->buffer;
1410 cl->ctokens = hopt->cbuffer;
Patrick McHardy00c04af2007-03-16 01:23:02 -07001411 cl->mbuffer = 60 * PSCHED_TICKS_PER_SEC; /* 1min */
Patrick McHardy3bebcda2007-03-23 11:29:25 -07001412 cl->t_c = psched_get_time();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001413 cl->cmode = HTB_CAN_SEND;
1414
1415 /* attach to the hash list and parent's family */
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001416 qdisc_class_hash_insert(&q->clhash, &cl->common);
Patrick McHardy42077592008-07-05 23:22:53 -07001417 if (parent)
1418 parent->children++;
Patrick McHardyee39e102007-07-02 22:48:13 -07001419 } else {
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001420 if (tca[TCA_RATE]) {
1421 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1422 qdisc_root_sleeping_lock(sch),
1423 tca[TCA_RATE]);
1424 if (err)
1425 return err;
1426 }
Stephen Hemminger87990462006-08-10 23:35:16 -07001427 sch_tree_lock(sch);
Patrick McHardyee39e102007-07-02 22:48:13 -07001428 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001429
1430 /* it used to be a nasty bug here, we have to check that node
Stephen Hemminger87990462006-08-10 23:35:16 -07001431 is really leaf before changing cl->un.leaf ! */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001432 if (!cl->level) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001433 cl->quantum = rtab->rate.rate / q->rate2quantum;
1434 if (!hopt->quantum && cl->quantum < 1000) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001435 printk(KERN_WARNING
1436 "HTB: quantum of class %X is small. Consider r2q change.\n",
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001437 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001438 cl->quantum = 1000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001439 }
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001440 if (!hopt->quantum && cl->quantum > 200000) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001441 printk(KERN_WARNING
1442 "HTB: quantum of class %X is big. Consider r2q change.\n",
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001443 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001444 cl->quantum = 200000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001445 }
1446 if (hopt->quantum)
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001447 cl->quantum = hopt->quantum;
1448 if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO)
1449 cl->prio = TC_HTB_NUMPRIO - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001450 }
1451
1452 cl->buffer = hopt->buffer;
1453 cl->cbuffer = hopt->cbuffer;
Stephen Hemminger87990462006-08-10 23:35:16 -07001454 if (cl->rate)
1455 qdisc_put_rtab(cl->rate);
1456 cl->rate = rtab;
1457 if (cl->ceil)
1458 qdisc_put_rtab(cl->ceil);
1459 cl->ceil = ctab;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001460 sch_tree_unlock(sch);
1461
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001462 qdisc_class_hash_grow(sch, &q->clhash);
1463
Linus Torvalds1da177e2005-04-16 15:20:36 -07001464 *arg = (unsigned long)cl;
1465 return 0;
1466
1467failure:
Stephen Hemminger87990462006-08-10 23:35:16 -07001468 if (rtab)
1469 qdisc_put_rtab(rtab);
1470 if (ctab)
1471 qdisc_put_rtab(ctab);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001472 return err;
1473}
1474
1475static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1476{
1477 struct htb_sched *q = qdisc_priv(sch);
1478 struct htb_class *cl = (struct htb_class *)arg;
1479 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001480
Linus Torvalds1da177e2005-04-16 15:20:36 -07001481 return fl;
1482}
1483
1484static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
Stephen Hemminger87990462006-08-10 23:35:16 -07001485 u32 classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001486{
Stephen Hemminger87990462006-08-10 23:35:16 -07001487 struct htb_class *cl = htb_find(classid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001488
Linus Torvalds1da177e2005-04-16 15:20:36 -07001489 /*if (cl && !cl->level) return 0;
Stephen Hemminger87990462006-08-10 23:35:16 -07001490 The line above used to be there to prevent attaching filters to
1491 leaves. But at least tc_index filter uses this just to get class
1492 for other reasons so that we have to allow for it.
1493 ----
1494 19.6.2002 As Werner explained it is ok - bind filter is just
1495 another way to "lock" the class - unlike "get" this lock can
1496 be broken by class during destroy IIUC.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001497 */
Stephen Hemminger87990462006-08-10 23:35:16 -07001498 if (cl)
1499 cl->filter_cnt++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001500 return (unsigned long)cl;
1501}
1502
1503static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1504{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001505 struct htb_class *cl = (struct htb_class *)arg;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001506
Stephen Hemminger87990462006-08-10 23:35:16 -07001507 if (cl)
1508 cl->filter_cnt--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001509}
1510
1511static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1512{
1513 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001514 struct htb_class *cl;
1515 struct hlist_node *n;
1516 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001517
1518 if (arg->stop)
1519 return;
1520
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001521 for (i = 0; i < q->clhash.hashsize; i++) {
1522 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001523 if (arg->count < arg->skip) {
1524 arg->count++;
1525 continue;
1526 }
1527 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1528 arg->stop = 1;
1529 return;
1530 }
1531 arg->count++;
1532 }
1533 }
1534}
1535
Eric Dumazet20fea082007-11-14 01:44:41 -08001536static const struct Qdisc_class_ops htb_class_ops = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001537 .graft = htb_graft,
1538 .leaf = htb_leaf,
Patrick McHardy256d61b2006-11-29 17:37:05 -08001539 .qlen_notify = htb_qlen_notify,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001540 .get = htb_get,
1541 .put = htb_put,
1542 .change = htb_change_class,
1543 .delete = htb_delete,
1544 .walk = htb_walk,
1545 .tcf_chain = htb_find_tcf,
1546 .bind_tcf = htb_bind_filter,
1547 .unbind_tcf = htb_unbind_filter,
1548 .dump = htb_dump_class,
1549 .dump_stats = htb_dump_class_stats,
1550};
1551
Eric Dumazet20fea082007-11-14 01:44:41 -08001552static struct Qdisc_ops htb_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001553 .next = NULL,
1554 .cl_ops = &htb_class_ops,
1555 .id = "htb",
1556 .priv_size = sizeof(struct htb_sched),
1557 .enqueue = htb_enqueue,
1558 .dequeue = htb_dequeue,
Jarek Poplawski77be1552008-10-31 00:47:01 -07001559 .peek = qdisc_peek_dequeued,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001560 .drop = htb_drop,
1561 .init = htb_init,
1562 .reset = htb_reset,
1563 .destroy = htb_destroy,
1564 .change = NULL /* htb_change */,
1565 .dump = htb_dump,
1566 .owner = THIS_MODULE,
1567};
1568
1569static int __init htb_module_init(void)
1570{
Stephen Hemminger87990462006-08-10 23:35:16 -07001571 return register_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001572}
Stephen Hemminger87990462006-08-10 23:35:16 -07001573static void __exit htb_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001574{
Stephen Hemminger87990462006-08-10 23:35:16 -07001575 unregister_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001576}
Stephen Hemminger87990462006-08-10 23:35:16 -07001577
Linus Torvalds1da177e2005-04-16 15:20:36 -07001578module_init(htb_module_init)
1579module_exit(htb_module_exit)
1580MODULE_LICENSE("GPL");