blob: 4b52fa78935a025dfd338c374e939bd630c06111 [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
14 * Ondrej Kraus, <krauso@barr.cz>
15 * 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.
27 *
28 * $Id: sch_htb.c,v 1.25 2003/12/07 11:08:25 devik Exp devik $
29 */
Linus Torvalds1da177e2005-04-16 15:20:36 -070030#include <linux/module.h>
31#include <asm/uaccess.h>
32#include <asm/system.h>
33#include <linux/bitops.h>
34#include <linux/types.h>
35#include <linux/kernel.h>
36#include <linux/sched.h>
37#include <linux/string.h>
38#include <linux/mm.h>
39#include <linux/socket.h>
40#include <linux/sockios.h>
41#include <linux/in.h>
42#include <linux/errno.h>
43#include <linux/interrupt.h>
44#include <linux/if_ether.h>
45#include <linux/inet.h>
46#include <linux/netdevice.h>
47#include <linux/etherdevice.h>
48#include <linux/notifier.h>
49#include <net/ip.h>
50#include <net/route.h>
51#include <linux/skbuff.h>
52#include <linux/list.h>
53#include <linux/compiler.h>
54#include <net/sock.h>
55#include <net/pkt_sched.h>
56#include <linux/rbtree.h>
57
58/* HTB algorithm.
59 Author: devik@cdi.cz
60 ========================================================================
61 HTB is like TBF with multiple classes. It is also similar to CBQ because
62 it allows to assign priority to each class in hierarchy.
63 In fact it is another implementation of Floyd's formal sharing.
64
65 Levels:
66 Each class is assigned level. Leaf has ALWAYS level 0 and root
67 classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
68 one less than their parent.
69*/
70
Stephen Hemminger87990462006-08-10 23:35:16 -070071#define HTB_HSIZE 16 /* classid hash size */
72#define HTB_EWMAC 2 /* rate average over HTB_EWMAC*HTB_HSIZE sec */
73#define HTB_RATECM 1 /* whether to use rate computer */
74#define HTB_HYSTERESIS 1 /* whether to use mode hysteresis for speedup */
75#define HTB_VER 0x30011 /* major must be matched with number suplied by TC as version */
Linus Torvalds1da177e2005-04-16 15:20:36 -070076
77#if HTB_VER >> 16 != TC_HTB_PROTOVER
78#error "Mismatched sch_htb.c and pkt_sch.h"
79#endif
80
Linus Torvalds1da177e2005-04-16 15:20:36 -070081/* used internaly to keep status of single class */
82enum htb_cmode {
Stephen Hemminger87990462006-08-10 23:35:16 -070083 HTB_CANT_SEND, /* class can't send and can't borrow */
84 HTB_MAY_BORROW, /* class can't send but may borrow */
85 HTB_CAN_SEND /* class can send */
Linus Torvalds1da177e2005-04-16 15:20:36 -070086};
87
88/* interior & leaf nodes; props specific to leaves are marked L: */
Stephen Hemminger87990462006-08-10 23:35:16 -070089struct htb_class {
90 /* general class parameters */
91 u32 classid;
92 struct gnet_stats_basic bstats;
93 struct gnet_stats_queue qstats;
94 struct gnet_stats_rate_est rate_est;
95 struct tc_htb_xstats xstats; /* our special stats */
96 int refcnt; /* usage count of this class */
Linus Torvalds1da177e2005-04-16 15:20:36 -070097
98#ifdef HTB_RATECM
Stephen Hemminger87990462006-08-10 23:35:16 -070099 /* rate measurement counters */
100 unsigned long rate_bytes, sum_bytes;
101 unsigned long rate_packets, sum_packets;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102#endif
103
Stephen Hemminger87990462006-08-10 23:35:16 -0700104 /* topology */
105 int level; /* our level (see above) */
106 struct htb_class *parent; /* parent class */
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700107 struct hlist_node hlist; /* classid hash list item */
Stephen Hemminger87990462006-08-10 23:35:16 -0700108 struct list_head sibling; /* sibling list item */
109 struct list_head children; /* children list */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700110
Stephen Hemminger87990462006-08-10 23:35:16 -0700111 union {
112 struct htb_class_leaf {
113 struct Qdisc *q;
114 int prio;
115 int aprio;
116 int quantum;
117 int deficit[TC_HTB_MAXDEPTH];
118 struct list_head drop_list;
119 } leaf;
120 struct htb_class_inner {
121 struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */
122 struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class ptr */
123 /* When class changes from state 1->2 and disconnects from
124 parent's feed then we lost ptr value and start from the
125 first child again. Here we store classid of the
126 last valid ptr (used when ptr is NULL). */
127 u32 last_ptr_id[TC_HTB_NUMPRIO];
128 } inner;
129 } un;
130 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
131 struct rb_node pq_node; /* node for event queue */
132 unsigned long pq_key; /* the same type as jiffies global */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700133
Stephen Hemminger87990462006-08-10 23:35:16 -0700134 int prio_activity; /* for which prios are we active */
135 enum htb_cmode cmode; /* current mode of the class */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700136
Stephen Hemminger87990462006-08-10 23:35:16 -0700137 /* class attached filters */
138 struct tcf_proto *filter_list;
139 int filter_cnt;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700140
Stephen Hemminger87990462006-08-10 23:35:16 -0700141 int warned; /* only one warning about non work conserving .. */
142
143 /* token bucket parameters */
144 struct qdisc_rate_table *rate; /* rate table of the class itself */
145 struct qdisc_rate_table *ceil; /* ceiling rate (limits borrows too) */
146 long buffer, cbuffer; /* token bucket depth/rate */
147 psched_tdiff_t mbuffer; /* max wait time */
148 long tokens, ctokens; /* current number of tokens */
149 psched_time_t t_c; /* checkpoint time */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700150};
151
152/* TODO: maybe compute rate when size is too large .. or drop ? */
Stephen Hemminger87990462006-08-10 23:35:16 -0700153static inline long L2T(struct htb_class *cl, struct qdisc_rate_table *rate,
154 int size)
155{
156 int slot = size >> rate->rate.cell_log;
157 if (slot > 255) {
158 cl->xstats.giants++;
159 slot = 255;
160 }
161 return rate->data[slot];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700162}
163
Stephen Hemminger87990462006-08-10 23:35:16 -0700164struct htb_sched {
165 struct list_head root; /* root classes list */
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700166 struct hlist_head hash[HTB_HSIZE]; /* hashed by classid */
167 struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168
Stephen Hemminger87990462006-08-10 23:35:16 -0700169 /* self list - roots of self generating tree */
170 struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
171 int row_mask[TC_HTB_MAXDEPTH];
172 struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
173 u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700174
Stephen Hemminger87990462006-08-10 23:35:16 -0700175 /* self wait list - roots of wait PQs per row */
176 struct rb_root wait_pq[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700177
Stephen Hemminger87990462006-08-10 23:35:16 -0700178 /* time of nearest event per level (row) */
179 unsigned long near_ev_cache[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700180
Stephen Hemminger87990462006-08-10 23:35:16 -0700181 /* cached value of jiffies in dequeue */
182 unsigned long jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700183
Stephen Hemminger87990462006-08-10 23:35:16 -0700184 /* whether we hit non-work conserving class during this dequeue; we use */
185 int nwc_hit; /* this to disable mindelay complaint in dequeue */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186
Stephen Hemminger87990462006-08-10 23:35:16 -0700187 int defcls; /* class where unclassified flows go to */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700188
Stephen Hemminger87990462006-08-10 23:35:16 -0700189 /* filters for qdisc itself */
190 struct tcf_proto *filter_list;
191 int filter_cnt;
192
193 int rate2quantum; /* quant = rate / rate2quantum */
194 psched_time_t now; /* cached dequeue time */
195 struct timer_list timer; /* send delay timer */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196#ifdef HTB_RATECM
Stephen Hemminger87990462006-08-10 23:35:16 -0700197 struct timer_list rttim; /* rate computer timer */
198 int recmp_bucket; /* which hash bucket to recompute next */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199#endif
Linus Torvalds1da177e2005-04-16 15:20:36 -0700200
Stephen Hemminger87990462006-08-10 23:35:16 -0700201 /* non shaped skbs; let them go directly thru */
202 struct sk_buff_head direct_queue;
203 int direct_qlen; /* max qlen of above */
204
205 long direct_pkts;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700206};
207
208/* compute hash of size HTB_HSIZE for given handle */
Stephen Hemminger87990462006-08-10 23:35:16 -0700209static inline int htb_hash(u32 h)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210{
211#if HTB_HSIZE != 16
Stephen Hemminger87990462006-08-10 23:35:16 -0700212#error "Declare new hash for your HTB_HSIZE"
Linus Torvalds1da177e2005-04-16 15:20:36 -0700213#endif
Stephen Hemminger87990462006-08-10 23:35:16 -0700214 h ^= h >> 8; /* stolen from cbq_hash */
215 h ^= h >> 4;
216 return h & 0xf;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700217}
218
219/* find class in global hash table using given handle */
Stephen Hemminger87990462006-08-10 23:35:16 -0700220static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700221{
222 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700223 struct hlist_node *p;
224 struct htb_class *cl;
225
Stephen Hemminger87990462006-08-10 23:35:16 -0700226 if (TC_H_MAJ(handle) != sch->handle)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700227 return NULL;
Stephen Hemminger87990462006-08-10 23:35:16 -0700228
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700229 hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700230 if (cl->classid == handle)
231 return cl;
232 }
233 return NULL;
234}
235
236/**
237 * htb_classify - classify a packet into class
238 *
239 * It returns NULL if the packet should be dropped or -1 if the packet
240 * should be passed directly thru. In all other cases leaf class is returned.
241 * We allow direct class selection by classid in priority. The we examine
242 * filters in qdisc and in inner nodes (if higher filter points to the inner
243 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
244 * internal fifo (direct). These packets then go directly thru. If we still
245 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
246 * then finish and return direct queue.
247 */
248#define HTB_DIRECT (struct htb_class*)-1
249static inline u32 htb_classid(struct htb_class *cl)
250{
251 return (cl && cl != HTB_DIRECT) ? cl->classid : TC_H_UNSPEC;
252}
253
Stephen Hemminger87990462006-08-10 23:35:16 -0700254static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
255 int *qerr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256{
257 struct htb_sched *q = qdisc_priv(sch);
258 struct htb_class *cl;
259 struct tcf_result res;
260 struct tcf_proto *tcf;
261 int result;
262
263 /* allow to select class by setting skb->priority to valid classid;
264 note that nfmark can be used too by attaching filter fw with no
265 rules in it */
266 if (skb->priority == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700267 return HTB_DIRECT; /* X:0 (direct flow) selected */
268 if ((cl = htb_find(skb->priority, sch)) != NULL && cl->level == 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700269 return cl;
270
Jamal Hadi Salim29f1df62006-01-08 22:35:55 -0800271 *qerr = NET_XMIT_BYPASS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700272 tcf = q->filter_list;
273 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
274#ifdef CONFIG_NET_CLS_ACT
275 switch (result) {
276 case TC_ACT_QUEUED:
Stephen Hemminger87990462006-08-10 23:35:16 -0700277 case TC_ACT_STOLEN:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700278 *qerr = NET_XMIT_SUCCESS;
279 case TC_ACT_SHOT:
280 return NULL;
281 }
282#elif defined(CONFIG_NET_CLS_POLICE)
283 if (result == TC_POLICE_SHOT)
284 return HTB_DIRECT;
285#endif
Stephen Hemminger87990462006-08-10 23:35:16 -0700286 if ((cl = (void *)res.class) == NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700287 if (res.classid == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700288 return HTB_DIRECT; /* X:0 (direct flow) */
289 if ((cl = htb_find(res.classid, sch)) == NULL)
290 break; /* filter selected invalid classid */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700291 }
292 if (!cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700293 return cl; /* we hit leaf; return it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700294
295 /* we have got inner class; apply inner filter chain */
296 tcf = cl->filter_list;
297 }
298 /* classification failed; try to use default class */
Stephen Hemminger87990462006-08-10 23:35:16 -0700299 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700300 if (!cl || cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700301 return HTB_DIRECT; /* bad default .. this is safe bet */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302 return cl;
303}
304
Linus Torvalds1da177e2005-04-16 15:20:36 -0700305/**
306 * htb_add_to_id_tree - adds class to the round robin list
307 *
308 * Routine adds class to the list (actually tree) sorted by classid.
309 * Make sure that class is not already on such list for given prio.
310 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700311static void htb_add_to_id_tree(struct rb_root *root,
312 struct htb_class *cl, int prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700313{
314 struct rb_node **p = &root->rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700315
Linus Torvalds1da177e2005-04-16 15:20:36 -0700316 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700317 struct htb_class *c;
318 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700319 c = rb_entry(parent, struct htb_class, node[prio]);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700320
Linus Torvalds1da177e2005-04-16 15:20:36 -0700321 if (cl->classid > c->classid)
322 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700323 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700324 p = &parent->rb_left;
325 }
326 rb_link_node(&cl->node[prio], parent, p);
327 rb_insert_color(&cl->node[prio], root);
328}
329
330/**
331 * htb_add_to_wait_tree - adds class to the event queue with delay
332 *
333 * The class is added to priority event queue to indicate that class will
334 * change its mode in cl->pq_key microseconds. Make sure that class is not
335 * already in the queue.
336 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700337static void htb_add_to_wait_tree(struct htb_sched *q,
338 struct htb_class *cl, long delay)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700339{
340 struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700341
Linus Torvalds1da177e2005-04-16 15:20:36 -0700342 cl->pq_key = q->jiffies + PSCHED_US2JIFFIE(delay);
343 if (cl->pq_key == q->jiffies)
344 cl->pq_key++;
345
346 /* update the nearest event cache */
347 if (time_after(q->near_ev_cache[cl->level], cl->pq_key))
348 q->near_ev_cache[cl->level] = cl->pq_key;
Stephen Hemminger87990462006-08-10 23:35:16 -0700349
Linus Torvalds1da177e2005-04-16 15:20:36 -0700350 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700351 struct htb_class *c;
352 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700353 c = rb_entry(parent, struct htb_class, pq_node);
354 if (time_after_eq(cl->pq_key, c->pq_key))
355 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700356 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700357 p = &parent->rb_left;
358 }
359 rb_link_node(&cl->pq_node, parent, p);
360 rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
361}
362
363/**
364 * htb_next_rb_node - finds next node in binary tree
365 *
366 * When we are past last key we return NULL.
367 * Average complexity is 2 steps per call.
368 */
Stephen Hemminger3696f622006-08-10 23:36:01 -0700369static inline void htb_next_rb_node(struct rb_node **n)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700370{
371 *n = rb_next(*n);
372}
373
374/**
375 * htb_add_class_to_row - add class to its row
376 *
377 * The class is added to row at priorities marked in mask.
378 * It does nothing if mask == 0.
379 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700380static inline void htb_add_class_to_row(struct htb_sched *q,
381 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700382{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700383 q->row_mask[cl->level] |= mask;
384 while (mask) {
385 int prio = ffz(~mask);
386 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700387 htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388 }
389}
390
Stephen Hemminger3696f622006-08-10 23:36:01 -0700391/* If this triggers, it is a bug in this code, but it need not be fatal */
392static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
393{
Ismail Donmez81771b32006-10-03 13:49:10 -0700394 if (RB_EMPTY_NODE(rb)) {
Stephen Hemminger3696f622006-08-10 23:36:01 -0700395 WARN_ON(1);
396 } else {
397 rb_erase(rb, root);
398 RB_CLEAR_NODE(rb);
399 }
400}
401
402
Linus Torvalds1da177e2005-04-16 15:20:36 -0700403/**
404 * htb_remove_class_from_row - removes class from its row
405 *
406 * The class is removed from row at priorities marked in mask.
407 * It does nothing if mask == 0.
408 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700409static inline void htb_remove_class_from_row(struct htb_sched *q,
410 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700411{
412 int m = 0;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700413
Linus Torvalds1da177e2005-04-16 15:20:36 -0700414 while (mask) {
415 int prio = ffz(~mask);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700416
Linus Torvalds1da177e2005-04-16 15:20:36 -0700417 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700418 if (q->ptr[cl->level][prio] == cl->node + prio)
419 htb_next_rb_node(q->ptr[cl->level] + prio);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700420
421 htb_safe_rb_erase(cl->node + prio, q->row[cl->level] + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700422 if (!q->row[cl->level][prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700423 m |= 1 << prio;
424 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700425 q->row_mask[cl->level] &= ~m;
426}
427
428/**
429 * htb_activate_prios - creates active classe's feed chain
430 *
431 * The class is connected to ancestors and/or appropriate rows
432 * for priorities it is participating on. cl->cmode must be new
433 * (activated) mode. It does nothing if cl->prio_activity == 0.
434 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700435static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700436{
437 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700438 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700439
440 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700441 m = mask;
442 while (m) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443 int prio = ffz(~m);
444 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700445
Linus Torvalds1da177e2005-04-16 15:20:36 -0700446 if (p->un.inner.feed[prio].rb_node)
447 /* parent already has its feed in use so that
448 reset bit in mask as parent is already ok */
449 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700450
451 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700452 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700453 p->prio_activity |= mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700454 cl = p;
455 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700456
Linus Torvalds1da177e2005-04-16 15:20:36 -0700457 }
458 if (cl->cmode == HTB_CAN_SEND && mask)
Stephen Hemminger87990462006-08-10 23:35:16 -0700459 htb_add_class_to_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700460}
461
462/**
463 * htb_deactivate_prios - remove class from feed chain
464 *
465 * cl->cmode must represent old mode (before deactivation). It does
466 * nothing if cl->prio_activity == 0. Class is removed from all feed
467 * chains and rows.
468 */
469static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
470{
471 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700472 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700473
474 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700475 m = mask;
476 mask = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477 while (m) {
478 int prio = ffz(~m);
479 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700480
481 if (p->un.inner.ptr[prio] == cl->node + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700482 /* we are removing child which is pointed to from
483 parent feed - forget the pointer but remember
484 classid */
485 p->un.inner.last_ptr_id[prio] = cl->classid;
486 p->un.inner.ptr[prio] = NULL;
487 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700488
Stephen Hemminger3696f622006-08-10 23:36:01 -0700489 htb_safe_rb_erase(cl->node + prio, p->un.inner.feed + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700490
491 if (!p->un.inner.feed[prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492 mask |= 1 << prio;
493 }
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700494
Linus Torvalds1da177e2005-04-16 15:20:36 -0700495 p->prio_activity &= ~mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700496 cl = p;
497 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700498
Linus Torvalds1da177e2005-04-16 15:20:36 -0700499 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700500 if (cl->cmode == HTB_CAN_SEND && mask)
501 htb_remove_class_from_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502}
503
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700504#if HTB_HYSTERESIS
505static inline long htb_lowater(const struct htb_class *cl)
506{
507 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
508}
509static inline long htb_hiwater(const struct htb_class *cl)
510{
511 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
512}
513#else
514#define htb_lowater(cl) (0)
515#define htb_hiwater(cl) (0)
516#endif
517
Linus Torvalds1da177e2005-04-16 15:20:36 -0700518/**
519 * htb_class_mode - computes and returns current class mode
520 *
521 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
522 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
523 * from now to time when cl will change its state.
524 * Also it is worth to note that class mode doesn't change simply
525 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
526 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
527 * mode transitions per time unit. The speed gain is about 1/6.
528 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700529static inline enum htb_cmode
530htb_class_mode(struct htb_class *cl, long *diff)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531{
Stephen Hemminger87990462006-08-10 23:35:16 -0700532 long toks;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700533
Stephen Hemminger87990462006-08-10 23:35:16 -0700534 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
535 *diff = -toks;
536 return HTB_CANT_SEND;
537 }
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700538
Stephen Hemminger87990462006-08-10 23:35:16 -0700539 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
540 return HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700541
Stephen Hemminger87990462006-08-10 23:35:16 -0700542 *diff = -toks;
543 return HTB_MAY_BORROW;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700544}
545
546/**
547 * htb_change_class_mode - changes classe's mode
548 *
549 * This should be the only way how to change classe's mode under normal
550 * cirsumstances. Routine will update feed lists linkage, change mode
551 * and add class to the wait event queue if appropriate. New mode should
552 * be different from old one and cl->pq_key has to be valid if changing
553 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
554 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700555static void
Linus Torvalds1da177e2005-04-16 15:20:36 -0700556htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
Stephen Hemminger87990462006-08-10 23:35:16 -0700557{
558 enum htb_cmode new_mode = htb_class_mode(cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559
560 if (new_mode == cl->cmode)
Stephen Hemminger87990462006-08-10 23:35:16 -0700561 return;
562
563 if (cl->prio_activity) { /* not necessary: speed optimization */
564 if (cl->cmode != HTB_CANT_SEND)
565 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566 cl->cmode = new_mode;
Stephen Hemminger87990462006-08-10 23:35:16 -0700567 if (new_mode != HTB_CANT_SEND)
568 htb_activate_prios(q, cl);
569 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700570 cl->cmode = new_mode;
571}
572
573/**
574 * htb_activate - inserts leaf cl into appropriate active feeds
575 *
576 * Routine learns (new) priority of leaf and activates feed chain
577 * for the prio. It can be called on already active leaf safely.
578 * It also adds leaf into droplist.
579 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700580static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700581{
582 BUG_TRAP(!cl->level && cl->un.leaf.q && cl->un.leaf.q->q.qlen);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700583
Linus Torvalds1da177e2005-04-16 15:20:36 -0700584 if (!cl->prio_activity) {
585 cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700586 htb_activate_prios(q, cl);
587 list_add_tail(&cl->un.leaf.drop_list,
588 q->drops + cl->un.leaf.aprio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700589 }
590}
591
592/**
593 * htb_deactivate - remove leaf cl from active feeds
594 *
595 * Make sure that leaf is active. In the other words it can't be called
596 * with non-active leaf. It also removes class from the drop list.
597 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700598static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700599{
600 BUG_TRAP(cl->prio_activity);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700601
Stephen Hemminger87990462006-08-10 23:35:16 -0700602 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700603 cl->prio_activity = 0;
604 list_del_init(&cl->un.leaf.drop_list);
605}
606
607static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
608{
Stephen Hemminger87990462006-08-10 23:35:16 -0700609 int ret;
610 struct htb_sched *q = qdisc_priv(sch);
611 struct htb_class *cl = htb_classify(skb, sch, &ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700612
Stephen Hemminger87990462006-08-10 23:35:16 -0700613 if (cl == HTB_DIRECT) {
614 /* enqueue to helper queue */
615 if (q->direct_queue.qlen < q->direct_qlen) {
616 __skb_queue_tail(&q->direct_queue, skb);
617 q->direct_pkts++;
618 } else {
619 kfree_skb(skb);
620 sch->qstats.drops++;
621 return NET_XMIT_DROP;
622 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700623#ifdef CONFIG_NET_CLS_ACT
Stephen Hemminger87990462006-08-10 23:35:16 -0700624 } else if (!cl) {
625 if (ret == NET_XMIT_BYPASS)
626 sch->qstats.drops++;
627 kfree_skb(skb);
628 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700629#endif
Stephen Hemminger87990462006-08-10 23:35:16 -0700630 } else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) !=
631 NET_XMIT_SUCCESS) {
632 sch->qstats.drops++;
633 cl->qstats.drops++;
634 return NET_XMIT_DROP;
635 } else {
636 cl->bstats.packets++;
637 cl->bstats.bytes += skb->len;
638 htb_activate(q, cl);
639 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700640
Stephen Hemminger87990462006-08-10 23:35:16 -0700641 sch->q.qlen++;
642 sch->bstats.packets++;
643 sch->bstats.bytes += skb->len;
644 return NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700645}
646
647/* TODO: requeuing packet charges it to policers again !! */
648static int htb_requeue(struct sk_buff *skb, struct Qdisc *sch)
649{
Stephen Hemminger87990462006-08-10 23:35:16 -0700650 struct htb_sched *q = qdisc_priv(sch);
651 int ret = NET_XMIT_SUCCESS;
652 struct htb_class *cl = htb_classify(skb, sch, &ret);
653 struct sk_buff *tskb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700654
Stephen Hemminger87990462006-08-10 23:35:16 -0700655 if (cl == HTB_DIRECT || !cl) {
656 /* enqueue to helper queue */
657 if (q->direct_queue.qlen < q->direct_qlen && cl) {
658 __skb_queue_head(&q->direct_queue, skb);
659 } else {
660 __skb_queue_head(&q->direct_queue, skb);
661 tskb = __skb_dequeue_tail(&q->direct_queue);
662 kfree_skb(tskb);
663 sch->qstats.drops++;
664 return NET_XMIT_CN;
665 }
666 } else if (cl->un.leaf.q->ops->requeue(skb, cl->un.leaf.q) !=
667 NET_XMIT_SUCCESS) {
668 sch->qstats.drops++;
669 cl->qstats.drops++;
670 return NET_XMIT_DROP;
671 } else
672 htb_activate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700673
Stephen Hemminger87990462006-08-10 23:35:16 -0700674 sch->q.qlen++;
675 sch->qstats.requeues++;
676 return NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700677}
678
679static void htb_timer(unsigned long arg)
680{
Stephen Hemminger87990462006-08-10 23:35:16 -0700681 struct Qdisc *sch = (struct Qdisc *)arg;
682 sch->flags &= ~TCQ_F_THROTTLED;
683 wmb();
684 netif_schedule(sch->dev);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685}
686
687#ifdef HTB_RATECM
688#define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0
689static void htb_rate_timer(unsigned long arg)
690{
Stephen Hemminger87990462006-08-10 23:35:16 -0700691 struct Qdisc *sch = (struct Qdisc *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700692 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700693 struct hlist_node *p;
694 struct htb_class *cl;
695
Linus Torvalds1da177e2005-04-16 15:20:36 -0700696
697 /* lock queue so that we can muck with it */
Stephen Hemminger9ac961e2006-08-10 23:33:16 -0700698 spin_lock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700699
700 q->rttim.expires = jiffies + HZ;
701 add_timer(&q->rttim);
702
703 /* scan and recompute one bucket at time */
Stephen Hemminger87990462006-08-10 23:35:16 -0700704 if (++q->recmp_bucket >= HTB_HSIZE)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700705 q->recmp_bucket = 0;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700706
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700707 hlist_for_each_entry(cl,p, q->hash + q->recmp_bucket, hlist) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700708 RT_GEN(cl->sum_bytes, cl->rate_bytes);
709 RT_GEN(cl->sum_packets, cl->rate_packets);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700710 }
Stephen Hemminger9ac961e2006-08-10 23:33:16 -0700711 spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700712}
713#endif
714
715/**
716 * htb_charge_class - charges amount "bytes" to leaf and ancestors
717 *
718 * Routine assumes that packet "bytes" long was dequeued from leaf cl
719 * borrowing from "level". It accounts bytes to ceil leaky bucket for
720 * leaf and all ancestors and to rate bucket for ancestors at levels
721 * "level" and higher. It also handles possible change of mode resulting
722 * from the update. Note that mode can also increase here (MAY_BORROW to
723 * CAN_SEND) because we can use more precise clock that event queue here.
724 * In such case we remove class from event queue first.
725 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700726static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
727 int level, int bytes)
728{
729 long toks, diff;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700730 enum htb_cmode old_mode;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700731
732#define HTB_ACCNT(T,B,R) toks = diff + cl->T; \
733 if (toks > cl->B) toks = cl->B; \
734 toks -= L2T(cl, cl->R, bytes); \
735 if (toks <= -cl->mbuffer) toks = 1-cl->mbuffer; \
736 cl->T = toks
737
738 while (cl) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700739 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32) cl->mbuffer);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700740 if (cl->level >= level) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700741 if (cl->level == level)
742 cl->xstats.lends++;
743 HTB_ACCNT(tokens, buffer, rate);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700744 } else {
745 cl->xstats.borrows++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700746 cl->tokens += diff; /* we moved t_c; update tokens */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700747 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700748 HTB_ACCNT(ctokens, cbuffer, ceil);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700749 cl->t_c = q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700750
Stephen Hemminger87990462006-08-10 23:35:16 -0700751 old_mode = cl->cmode;
752 diff = 0;
753 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700754 if (old_mode != cl->cmode) {
755 if (old_mode != HTB_CAN_SEND)
Stephen Hemminger3696f622006-08-10 23:36:01 -0700756 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700757 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700758 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700759 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700760#ifdef HTB_RATECM
761 /* update rate counters */
Stephen Hemminger87990462006-08-10 23:35:16 -0700762 cl->sum_bytes += bytes;
763 cl->sum_packets++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700764#endif
765
766 /* update byte stats except for leaves which are already updated */
767 if (cl->level) {
768 cl->bstats.bytes += bytes;
769 cl->bstats.packets++;
770 }
771 cl = cl->parent;
772 }
773}
774
775/**
776 * htb_do_events - make mode changes to classes at the level
777 *
778 * Scans event queue for pending events and applies them. Returns jiffies to
779 * next pending event (0 for no event in pq).
780 * Note: Aplied are events whose have cl->pq_key <= jiffies.
781 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700782static long htb_do_events(struct htb_sched *q, int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700783{
784 int i;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700785
Linus Torvalds1da177e2005-04-16 15:20:36 -0700786 for (i = 0; i < 500; i++) {
787 struct htb_class *cl;
788 long diff;
Akinbou Mita30bdbe32006-10-12 01:52:05 -0700789 struct rb_node *p = rb_first(&q->wait_pq[level]);
790
Stephen Hemminger87990462006-08-10 23:35:16 -0700791 if (!p)
792 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700793
794 cl = rb_entry(p, struct htb_class, pq_node);
795 if (time_after(cl->pq_key, q->jiffies)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700796 return cl->pq_key - q->jiffies;
797 }
Stephen Hemminger3696f622006-08-10 23:36:01 -0700798 htb_safe_rb_erase(p, q->wait_pq + level);
Stephen Hemminger87990462006-08-10 23:35:16 -0700799 diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32) cl->mbuffer);
800 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700801 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700802 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700803 }
804 if (net_ratelimit())
805 printk(KERN_WARNING "htb: too many events !\n");
Stephen Hemminger87990462006-08-10 23:35:16 -0700806 return HZ / 10;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700807}
808
809/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
810 is no such one exists. */
Stephen Hemminger87990462006-08-10 23:35:16 -0700811static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
812 u32 id)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700813{
814 struct rb_node *r = NULL;
815 while (n) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700816 struct htb_class *cl =
817 rb_entry(n, struct htb_class, node[prio]);
818 if (id == cl->classid)
819 return n;
820
Linus Torvalds1da177e2005-04-16 15:20:36 -0700821 if (id > cl->classid) {
822 n = n->rb_right;
823 } else {
824 r = n;
825 n = n->rb_left;
826 }
827 }
828 return r;
829}
830
831/**
832 * htb_lookup_leaf - returns next leaf class in DRR order
833 *
834 * Find leaf where current feed pointers points to.
835 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700836static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio,
837 struct rb_node **pptr, u32 * pid)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838{
839 int i;
840 struct {
841 struct rb_node *root;
842 struct rb_node **pptr;
843 u32 *pid;
Stephen Hemminger87990462006-08-10 23:35:16 -0700844 } stk[TC_HTB_MAXDEPTH], *sp = stk;
845
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846 BUG_TRAP(tree->rb_node);
847 sp->root = tree->rb_node;
848 sp->pptr = pptr;
849 sp->pid = pid;
850
851 for (i = 0; i < 65535; i++) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700852 if (!*sp->pptr && *sp->pid) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853 /* ptr was invalidated but id is valid - try to recover
854 the original or next ptr */
Stephen Hemminger87990462006-08-10 23:35:16 -0700855 *sp->pptr =
856 htb_id_find_next_upper(prio, sp->root, *sp->pid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700857 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700858 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
859 can become out of date quickly */
860 if (!*sp->pptr) { /* we are at right end; rewind & go up */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700861 *sp->pptr = sp->root;
Stephen Hemminger87990462006-08-10 23:35:16 -0700862 while ((*sp->pptr)->rb_left)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700863 *sp->pptr = (*sp->pptr)->rb_left;
864 if (sp > stk) {
865 sp--;
Stephen Hemminger87990462006-08-10 23:35:16 -0700866 BUG_TRAP(*sp->pptr);
867 if (!*sp->pptr)
868 return NULL;
869 htb_next_rb_node(sp->pptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700870 }
871 } else {
872 struct htb_class *cl;
Stephen Hemminger87990462006-08-10 23:35:16 -0700873 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
874 if (!cl->level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700875 return cl;
876 (++sp)->root = cl->un.inner.feed[prio].rb_node;
Stephen Hemminger87990462006-08-10 23:35:16 -0700877 sp->pptr = cl->un.inner.ptr + prio;
878 sp->pid = cl->un.inner.last_ptr_id + prio;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700879 }
880 }
881 BUG_TRAP(0);
882 return NULL;
883}
884
885/* dequeues packet at given priority and level; call only if
886 you are sure that there is active class at prio/level */
Stephen Hemminger87990462006-08-10 23:35:16 -0700887static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
888 int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700889{
890 struct sk_buff *skb = NULL;
Stephen Hemminger87990462006-08-10 23:35:16 -0700891 struct htb_class *cl, *start;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892 /* look initial class up in the row */
Stephen Hemminger87990462006-08-10 23:35:16 -0700893 start = cl = htb_lookup_leaf(q->row[level] + prio, prio,
894 q->ptr[level] + prio,
895 q->last_ptr_id[level] + prio);
896
Linus Torvalds1da177e2005-04-16 15:20:36 -0700897 do {
898next:
Stephen Hemminger87990462006-08-10 23:35:16 -0700899 BUG_TRAP(cl);
900 if (!cl)
901 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700902
903 /* class can be empty - it is unlikely but can be true if leaf
904 qdisc drops packets in enqueue routine or if someone used
905 graft operation on the leaf since last dequeue;
906 simply deactivate and skip such class */
907 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
908 struct htb_class *next;
Stephen Hemminger87990462006-08-10 23:35:16 -0700909 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700910
911 /* row/level might become empty */
912 if ((q->row_mask[level] & (1 << prio)) == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -0700913 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700914
Stephen Hemminger87990462006-08-10 23:35:16 -0700915 next = htb_lookup_leaf(q->row[level] + prio,
916 prio, q->ptr[level] + prio,
917 q->last_ptr_id[level] + prio);
918
919 if (cl == start) /* fix start if we just deleted it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700920 start = next;
921 cl = next;
922 goto next;
923 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700924
925 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
926 if (likely(skb != NULL))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700927 break;
928 if (!cl->warned) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700929 printk(KERN_WARNING
930 "htb: class %X isn't work conserving ?!\n",
931 cl->classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700932 cl->warned = 1;
933 }
934 q->nwc_hit++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700935 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
936 ptr[0]) + prio);
937 cl = htb_lookup_leaf(q->row[level] + prio, prio,
938 q->ptr[level] + prio,
939 q->last_ptr_id[level] + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700940
941 } while (cl != start);
942
943 if (likely(skb != NULL)) {
944 if ((cl->un.leaf.deficit[level] -= skb->len) < 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700945 cl->un.leaf.deficit[level] += cl->un.leaf.quantum;
Stephen Hemminger87990462006-08-10 23:35:16 -0700946 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
947 ptr[0]) + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700948 }
949 /* this used to be after charge_class but this constelation
950 gives us slightly better performance */
951 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700952 htb_deactivate(q, cl);
953 htb_charge_class(q, cl, level, skb->len);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700954 }
955 return skb;
956}
957
Stephen Hemminger87990462006-08-10 23:35:16 -0700958static void htb_delay_by(struct Qdisc *sch, long delay)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700959{
960 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -0700961 if (delay <= 0)
962 delay = 1;
963 if (unlikely(delay > 5 * HZ)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700964 if (net_ratelimit())
965 printk(KERN_INFO "HTB delay %ld > 5sec\n", delay);
Stephen Hemminger87990462006-08-10 23:35:16 -0700966 delay = 5 * HZ;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700967 }
968 /* why don't use jiffies here ? because expires can be in past */
969 mod_timer(&q->timer, q->jiffies + delay);
970 sch->flags |= TCQ_F_THROTTLED;
971 sch->qstats.overlimits++;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700972}
973
974static struct sk_buff *htb_dequeue(struct Qdisc *sch)
975{
976 struct sk_buff *skb = NULL;
977 struct htb_sched *q = qdisc_priv(sch);
978 int level;
979 long min_delay;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980
981 q->jiffies = jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700982
983 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
Stephen Hemminger87990462006-08-10 23:35:16 -0700984 skb = __skb_dequeue(&q->direct_queue);
985 if (skb != NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700986 sch->flags &= ~TCQ_F_THROTTLED;
987 sch->q.qlen--;
988 return skb;
989 }
990
Stephen Hemminger87990462006-08-10 23:35:16 -0700991 if (!sch->q.qlen)
992 goto fin;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700993 PSCHED_GET_TIME(q->now);
994
995 min_delay = LONG_MAX;
996 q->nwc_hit = 0;
997 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
998 /* common case optimization - skip event handler quickly */
999 int m;
1000 long delay;
1001 if (time_after_eq(q->jiffies, q->near_ev_cache[level])) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001002 delay = htb_do_events(q, level);
1003 q->near_ev_cache[level] =
1004 q->jiffies + (delay ? delay : HZ);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001005 } else
Stephen Hemminger87990462006-08-10 23:35:16 -07001006 delay = q->near_ev_cache[level] - q->jiffies;
1007
1008 if (delay && min_delay > delay)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001009 min_delay = delay;
1010 m = ~q->row_mask[level];
1011 while (m != (int)(-1)) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001012 int prio = ffz(m);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001013 m |= 1 << prio;
Stephen Hemminger87990462006-08-10 23:35:16 -07001014 skb = htb_dequeue_tree(q, prio, level);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001015 if (likely(skb != NULL)) {
1016 sch->q.qlen--;
1017 sch->flags &= ~TCQ_F_THROTTLED;
1018 goto fin;
1019 }
1020 }
1021 }
Stephen Hemminger87990462006-08-10 23:35:16 -07001022 htb_delay_by(sch, min_delay > 5 * HZ ? 5 * HZ : min_delay);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001023fin:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001024 return skb;
1025}
1026
1027/* try to drop from each class (by prio) until one succeed */
Stephen Hemminger87990462006-08-10 23:35:16 -07001028static unsigned int htb_drop(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001029{
1030 struct htb_sched *q = qdisc_priv(sch);
1031 int prio;
1032
1033 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
1034 struct list_head *p;
Stephen Hemminger87990462006-08-10 23:35:16 -07001035 list_for_each(p, q->drops + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001036 struct htb_class *cl = list_entry(p, struct htb_class,
1037 un.leaf.drop_list);
1038 unsigned int len;
Stephen Hemminger87990462006-08-10 23:35:16 -07001039 if (cl->un.leaf.q->ops->drop &&
1040 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001041 sch->q.qlen--;
1042 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -07001043 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001044 return len;
1045 }
1046 }
1047 }
1048 return 0;
1049}
1050
1051/* reset all classes */
1052/* always caled under BH & queue lock */
Stephen Hemminger87990462006-08-10 23:35:16 -07001053static void htb_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001054{
1055 struct htb_sched *q = qdisc_priv(sch);
1056 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001057
1058 for (i = 0; i < HTB_HSIZE; i++) {
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001059 struct hlist_node *p;
1060 struct htb_class *cl;
1061
1062 hlist_for_each_entry(cl, p, q->hash + i, hlist) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001063 if (cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -07001064 memset(&cl->un.inner, 0, sizeof(cl->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001065 else {
Stephen Hemminger87990462006-08-10 23:35:16 -07001066 if (cl->un.leaf.q)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001067 qdisc_reset(cl->un.leaf.q);
1068 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1069 }
1070 cl->prio_activity = 0;
1071 cl->cmode = HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001072
1073 }
1074 }
1075 sch->flags &= ~TCQ_F_THROTTLED;
1076 del_timer(&q->timer);
1077 __skb_queue_purge(&q->direct_queue);
1078 sch->q.qlen = 0;
Stephen Hemminger87990462006-08-10 23:35:16 -07001079 memset(q->row, 0, sizeof(q->row));
1080 memset(q->row_mask, 0, sizeof(q->row_mask));
1081 memset(q->wait_pq, 0, sizeof(q->wait_pq));
1082 memset(q->ptr, 0, sizeof(q->ptr));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001083 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -07001084 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001085}
1086
1087static int htb_init(struct Qdisc *sch, struct rtattr *opt)
1088{
1089 struct htb_sched *q = qdisc_priv(sch);
1090 struct rtattr *tb[TCA_HTB_INIT];
1091 struct tc_htb_glob *gopt;
1092 int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001093 if (!opt || rtattr_parse_nested(tb, TCA_HTB_INIT, opt) ||
Stephen Hemminger87990462006-08-10 23:35:16 -07001094 tb[TCA_HTB_INIT - 1] == NULL ||
1095 RTA_PAYLOAD(tb[TCA_HTB_INIT - 1]) < sizeof(*gopt)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001096 printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n");
1097 return -EINVAL;
1098 }
Stephen Hemminger87990462006-08-10 23:35:16 -07001099 gopt = RTA_DATA(tb[TCA_HTB_INIT - 1]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001100 if (gopt->version != HTB_VER >> 16) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001101 printk(KERN_ERR
1102 "HTB: need tc/htb version %d (minor is %d), you have %d\n",
1103 HTB_VER >> 16, HTB_VER & 0xffff, gopt->version);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001104 return -EINVAL;
1105 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001106
1107 INIT_LIST_HEAD(&q->root);
1108 for (i = 0; i < HTB_HSIZE; i++)
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001109 INIT_HLIST_HEAD(q->hash + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001110 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -07001111 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001112
1113 init_timer(&q->timer);
1114 skb_queue_head_init(&q->direct_queue);
1115
1116 q->direct_qlen = sch->dev->tx_queue_len;
Stephen Hemminger87990462006-08-10 23:35:16 -07001117 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001118 q->direct_qlen = 2;
1119 q->timer.function = htb_timer;
1120 q->timer.data = (unsigned long)sch;
1121
1122#ifdef HTB_RATECM
1123 init_timer(&q->rttim);
1124 q->rttim.function = htb_rate_timer;
1125 q->rttim.data = (unsigned long)sch;
1126 q->rttim.expires = jiffies + HZ;
1127 add_timer(&q->rttim);
1128#endif
1129 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1130 q->rate2quantum = 1;
1131 q->defcls = gopt->defcls;
1132
1133 return 0;
1134}
1135
1136static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1137{
1138 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001139 unsigned char *b = skb->tail;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001140 struct rtattr *rta;
1141 struct tc_htb_glob gopt;
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001142 spin_lock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001143 gopt.direct_pkts = q->direct_pkts;
1144
Linus Torvalds1da177e2005-04-16 15:20:36 -07001145 gopt.version = HTB_VER;
1146 gopt.rate2quantum = q->rate2quantum;
1147 gopt.defcls = q->defcls;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001148 gopt.debug = 0;
Stephen Hemminger87990462006-08-10 23:35:16 -07001149 rta = (struct rtattr *)b;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1151 RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
1152 rta->rta_len = skb->tail - b;
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001153 spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001154 return skb->len;
1155rtattr_failure:
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001156 spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001157 skb_trim(skb, skb->tail - skb->data);
1158 return -1;
1159}
1160
1161static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
Stephen Hemminger87990462006-08-10 23:35:16 -07001162 struct sk_buff *skb, struct tcmsg *tcm)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001163{
Stephen Hemminger87990462006-08-10 23:35:16 -07001164 struct htb_class *cl = (struct htb_class *)arg;
1165 unsigned char *b = skb->tail;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001166 struct rtattr *rta;
1167 struct tc_htb_opt opt;
1168
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001169 spin_lock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001170 tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
1171 tcm->tcm_handle = cl->classid;
1172 if (!cl->level && cl->un.leaf.q)
1173 tcm->tcm_info = cl->un.leaf.q->handle;
1174
Stephen Hemminger87990462006-08-10 23:35:16 -07001175 rta = (struct rtattr *)b;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001176 RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
1177
Stephen Hemminger87990462006-08-10 23:35:16 -07001178 memset(&opt, 0, sizeof(opt));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001179
Stephen Hemminger87990462006-08-10 23:35:16 -07001180 opt.rate = cl->rate->rate;
1181 opt.buffer = cl->buffer;
1182 opt.ceil = cl->ceil->rate;
1183 opt.cbuffer = cl->cbuffer;
1184 opt.quantum = cl->un.leaf.quantum;
1185 opt.prio = cl->un.leaf.prio;
1186 opt.level = cl->level;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001187 RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
1188 rta->rta_len = skb->tail - b;
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001189 spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001190 return skb->len;
1191rtattr_failure:
Stephen Hemminger9ac961e2006-08-10 23:33:16 -07001192 spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001193 skb_trim(skb, b - skb->data);
1194 return -1;
1195}
1196
1197static int
Stephen Hemminger87990462006-08-10 23:35:16 -07001198htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001199{
Stephen Hemminger87990462006-08-10 23:35:16 -07001200 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001201
1202#ifdef HTB_RATECM
Stephen Hemminger87990462006-08-10 23:35:16 -07001203 cl->rate_est.bps = cl->rate_bytes / (HTB_EWMAC * HTB_HSIZE);
1204 cl->rate_est.pps = cl->rate_packets / (HTB_EWMAC * HTB_HSIZE);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001205#endif
1206
1207 if (!cl->level && cl->un.leaf.q)
1208 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
1209 cl->xstats.tokens = cl->tokens;
1210 cl->xstats.ctokens = cl->ctokens;
1211
1212 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
1213 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
1214 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1215 return -1;
1216
1217 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1218}
1219
1220static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
Stephen Hemminger87990462006-08-10 23:35:16 -07001221 struct Qdisc **old)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001222{
Stephen Hemminger87990462006-08-10 23:35:16 -07001223 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001224
1225 if (cl && !cl->level) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001226 if (new == NULL && (new = qdisc_create_dflt(sch->dev,
1227 &pfifo_qdisc_ops))
1228 == NULL)
1229 return -ENOBUFS;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001230 sch_tree_lock(sch);
1231 if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
1232 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001233 htb_deactivate(qdisc_priv(sch), cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001234
1235 /* TODO: is it correct ? Why CBQ doesn't do it ? */
Stephen Hemminger87990462006-08-10 23:35:16 -07001236 sch->q.qlen -= (*old)->q.qlen;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001237 qdisc_reset(*old);
1238 }
1239 sch_tree_unlock(sch);
1240 return 0;
1241 }
1242 return -ENOENT;
1243}
1244
Stephen Hemminger87990462006-08-10 23:35:16 -07001245static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001246{
Stephen Hemminger87990462006-08-10 23:35:16 -07001247 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001248 return (cl && !cl->level) ? cl->un.leaf.q : NULL;
1249}
1250
1251static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1252{
Stephen Hemminger87990462006-08-10 23:35:16 -07001253 struct htb_class *cl = htb_find(classid, sch);
1254 if (cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001255 cl->refcnt++;
1256 return (unsigned long)cl;
1257}
1258
1259static void htb_destroy_filters(struct tcf_proto **fl)
1260{
1261 struct tcf_proto *tp;
1262
1263 while ((tp = *fl) != NULL) {
1264 *fl = tp->next;
1265 tcf_destroy(tp);
1266 }
1267}
1268
Stephen Hemminger87990462006-08-10 23:35:16 -07001269static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001270{
1271 struct htb_sched *q = qdisc_priv(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001272 if (!cl->level) {
1273 BUG_TRAP(cl->un.leaf.q);
1274 sch->q.qlen -= cl->un.leaf.q->q.qlen;
1275 qdisc_destroy(cl->un.leaf.q);
1276 }
1277 qdisc_put_rtab(cl->rate);
1278 qdisc_put_rtab(cl->ceil);
Stephen Hemminger87990462006-08-10 23:35:16 -07001279
1280 htb_destroy_filters(&cl->filter_list);
1281
1282 while (!list_empty(&cl->children))
1283 htb_destroy_class(sch, list_entry(cl->children.next,
1284 struct htb_class, sibling));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001285
1286 /* note: this delete may happen twice (see htb_delete) */
Stephen Hemmingerda33e3e2006-11-07 14:54:46 -08001287 hlist_del_init(&cl->hlist);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001288 list_del(&cl->sibling);
Stephen Hemminger87990462006-08-10 23:35:16 -07001289
Linus Torvalds1da177e2005-04-16 15:20:36 -07001290 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001291 htb_deactivate(q, cl);
1292
Linus Torvalds1da177e2005-04-16 15:20:36 -07001293 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger3696f622006-08-10 23:36:01 -07001294 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
Stephen Hemminger87990462006-08-10 23:35:16 -07001295
Linus Torvalds1da177e2005-04-16 15:20:36 -07001296 kfree(cl);
1297}
1298
1299/* always caled under BH & queue lock */
Stephen Hemminger87990462006-08-10 23:35:16 -07001300static void htb_destroy(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001301{
1302 struct htb_sched *q = qdisc_priv(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001303
Stephen Hemminger87990462006-08-10 23:35:16 -07001304 del_timer_sync(&q->timer);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001305#ifdef HTB_RATECM
Stephen Hemminger87990462006-08-10 23:35:16 -07001306 del_timer_sync(&q->rttim);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001307#endif
1308 /* This line used to be after htb_destroy_class call below
1309 and surprisingly it worked in 2.4. But it must precede it
1310 because filter need its target class alive to be able to call
1311 unbind_filter on it (without Oops). */
1312 htb_destroy_filters(&q->filter_list);
Stephen Hemminger87990462006-08-10 23:35:16 -07001313
1314 while (!list_empty(&q->root))
1315 htb_destroy_class(sch, list_entry(q->root.next,
1316 struct htb_class, sibling));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001317
1318 __skb_queue_purge(&q->direct_queue);
1319}
1320
1321static int htb_delete(struct Qdisc *sch, unsigned long arg)
1322{
1323 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001324 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001325
1326 // TODO: why don't allow to delete subtree ? references ? does
1327 // tc subsys quarantee us that in htb_destroy it holds no class
1328 // refs so that we can remove children safely there ?
1329 if (!list_empty(&cl->children) || cl->filter_cnt)
1330 return -EBUSY;
Stephen Hemminger87990462006-08-10 23:35:16 -07001331
Linus Torvalds1da177e2005-04-16 15:20:36 -07001332 sch_tree_lock(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001333
Linus Torvalds1da177e2005-04-16 15:20:36 -07001334 /* delete from hash and active; remainder in destroy_class */
Stephen Hemmingerda33e3e2006-11-07 14:54:46 -08001335 hlist_del_init(&cl->hlist);
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001336
Linus Torvalds1da177e2005-04-16 15:20:36 -07001337 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001338 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001339
1340 if (--cl->refcnt == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -07001341 htb_destroy_class(sch, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001342
1343 sch_tree_unlock(sch);
1344 return 0;
1345}
1346
1347static void htb_put(struct Qdisc *sch, unsigned long arg)
1348{
Stephen Hemminger87990462006-08-10 23:35:16 -07001349 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001350
1351 if (--cl->refcnt == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -07001352 htb_destroy_class(sch, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001353}
1354
Stephen Hemminger87990462006-08-10 23:35:16 -07001355static int htb_change_class(struct Qdisc *sch, u32 classid,
1356 u32 parentid, struct rtattr **tca,
1357 unsigned long *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001358{
1359 int err = -EINVAL;
1360 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001361 struct htb_class *cl = (struct htb_class *)*arg, *parent;
1362 struct rtattr *opt = tca[TCA_OPTIONS - 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001363 struct qdisc_rate_table *rtab = NULL, *ctab = NULL;
1364 struct rtattr *tb[TCA_HTB_RTAB];
1365 struct tc_htb_opt *hopt;
1366
1367 /* extract all subattrs from opt attr */
1368 if (!opt || rtattr_parse_nested(tb, TCA_HTB_RTAB, opt) ||
Stephen Hemminger87990462006-08-10 23:35:16 -07001369 tb[TCA_HTB_PARMS - 1] == NULL ||
1370 RTA_PAYLOAD(tb[TCA_HTB_PARMS - 1]) < sizeof(*hopt))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001371 goto failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001372
Stephen Hemminger87990462006-08-10 23:35:16 -07001373 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001374
Stephen Hemminger87990462006-08-10 23:35:16 -07001375 hopt = RTA_DATA(tb[TCA_HTB_PARMS - 1]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001376
Stephen Hemminger87990462006-08-10 23:35:16 -07001377 rtab = qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB - 1]);
1378 ctab = qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB - 1]);
1379 if (!rtab || !ctab)
1380 goto failure;
1381
1382 if (!cl) { /* new class */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001383 struct Qdisc *new_q;
Stephen Hemminger3696f622006-08-10 23:36:01 -07001384 int prio;
1385
Linus Torvalds1da177e2005-04-16 15:20:36 -07001386 /* check for valid classid */
Stephen Hemminger87990462006-08-10 23:35:16 -07001387 if (!classid || TC_H_MAJ(classid ^ sch->handle)
1388 || htb_find(classid, sch))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001389 goto failure;
1390
1391 /* check maximal depth */
1392 if (parent && parent->parent && parent->parent->level < 2) {
1393 printk(KERN_ERR "htb: tree is too deep\n");
1394 goto failure;
1395 }
1396 err = -ENOBUFS;
Panagiotis Issaris0da974f2006-07-21 14:51:30 -07001397 if ((cl = kzalloc(sizeof(*cl), GFP_KERNEL)) == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001398 goto failure;
Stephen Hemminger87990462006-08-10 23:35:16 -07001399
Linus Torvalds1da177e2005-04-16 15:20:36 -07001400 cl->refcnt = 1;
1401 INIT_LIST_HEAD(&cl->sibling);
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001402 INIT_HLIST_NODE(&cl->hlist);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001403 INIT_LIST_HEAD(&cl->children);
1404 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
Stephen Hemminger3696f622006-08-10 23:36:01 -07001405 RB_CLEAR_NODE(&cl->pq_node);
1406
1407 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1408 RB_CLEAR_NODE(&cl->node[prio]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001409
1410 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
1411 so that can't be used inside of sch_tree_lock
1412 -- thanks to Karlis Peisenieks */
1413 new_q = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops);
1414 sch_tree_lock(sch);
1415 if (parent && !parent->level) {
1416 /* turn parent into inner node */
1417 sch->q.qlen -= parent->un.leaf.q->q.qlen;
Stephen Hemminger87990462006-08-10 23:35:16 -07001418 qdisc_destroy(parent->un.leaf.q);
1419 if (parent->prio_activity)
1420 htb_deactivate(q, parent);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001421
1422 /* remove from evt list because of level change */
1423 if (parent->cmode != HTB_CAN_SEND) {
Stephen Hemminger3696f622006-08-10 23:36:01 -07001424 htb_safe_rb_erase(&parent->pq_node, q->wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001425 parent->cmode = HTB_CAN_SEND;
1426 }
1427 parent->level = (parent->parent ? parent->parent->level
Stephen Hemminger87990462006-08-10 23:35:16 -07001428 : TC_HTB_MAXDEPTH) - 1;
1429 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001430 }
1431 /* leaf (we) needs elementary qdisc */
1432 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1433
Stephen Hemminger87990462006-08-10 23:35:16 -07001434 cl->classid = classid;
1435 cl->parent = parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001436
1437 /* set class to be in HTB_CAN_SEND state */
1438 cl->tokens = hopt->buffer;
1439 cl->ctokens = hopt->cbuffer;
Stephen Hemminger87990462006-08-10 23:35:16 -07001440 cl->mbuffer = PSCHED_JIFFIE2US(HZ * 60); /* 1min */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001441 PSCHED_GET_TIME(cl->t_c);
1442 cl->cmode = HTB_CAN_SEND;
1443
1444 /* attach to the hash list and parent's family */
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001445 hlist_add_head(&cl->hlist, q->hash + htb_hash(classid));
Stephen Hemminger87990462006-08-10 23:35:16 -07001446 list_add_tail(&cl->sibling,
1447 parent ? &parent->children : &q->root);
1448 } else
1449 sch_tree_lock(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001450
1451 /* it used to be a nasty bug here, we have to check that node
Stephen Hemminger87990462006-08-10 23:35:16 -07001452 is really leaf before changing cl->un.leaf ! */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001453 if (!cl->level) {
1454 cl->un.leaf.quantum = rtab->rate.rate / q->rate2quantum;
1455 if (!hopt->quantum && cl->un.leaf.quantum < 1000) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001456 printk(KERN_WARNING
1457 "HTB: quantum of class %X is small. Consider r2q change.\n",
1458 cl->classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001459 cl->un.leaf.quantum = 1000;
1460 }
1461 if (!hopt->quantum && cl->un.leaf.quantum > 200000) {
Stephen Hemminger87990462006-08-10 23:35:16 -07001462 printk(KERN_WARNING
1463 "HTB: quantum of class %X is big. Consider r2q change.\n",
1464 cl->classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001465 cl->un.leaf.quantum = 200000;
1466 }
1467 if (hopt->quantum)
1468 cl->un.leaf.quantum = hopt->quantum;
1469 if ((cl->un.leaf.prio = hopt->prio) >= TC_HTB_NUMPRIO)
1470 cl->un.leaf.prio = TC_HTB_NUMPRIO - 1;
1471 }
1472
1473 cl->buffer = hopt->buffer;
1474 cl->cbuffer = hopt->cbuffer;
Stephen Hemminger87990462006-08-10 23:35:16 -07001475 if (cl->rate)
1476 qdisc_put_rtab(cl->rate);
1477 cl->rate = rtab;
1478 if (cl->ceil)
1479 qdisc_put_rtab(cl->ceil);
1480 cl->ceil = ctab;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001481 sch_tree_unlock(sch);
1482
1483 *arg = (unsigned long)cl;
1484 return 0;
1485
1486failure:
Stephen Hemminger87990462006-08-10 23:35:16 -07001487 if (rtab)
1488 qdisc_put_rtab(rtab);
1489 if (ctab)
1490 qdisc_put_rtab(ctab);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001491 return err;
1492}
1493
1494static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1495{
1496 struct htb_sched *q = qdisc_priv(sch);
1497 struct htb_class *cl = (struct htb_class *)arg;
1498 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001499
Linus Torvalds1da177e2005-04-16 15:20:36 -07001500 return fl;
1501}
1502
1503static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
Stephen Hemminger87990462006-08-10 23:35:16 -07001504 u32 classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001505{
1506 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001507 struct htb_class *cl = htb_find(classid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001508
Linus Torvalds1da177e2005-04-16 15:20:36 -07001509 /*if (cl && !cl->level) return 0;
Stephen Hemminger87990462006-08-10 23:35:16 -07001510 The line above used to be there to prevent attaching filters to
1511 leaves. But at least tc_index filter uses this just to get class
1512 for other reasons so that we have to allow for it.
1513 ----
1514 19.6.2002 As Werner explained it is ok - bind filter is just
1515 another way to "lock" the class - unlike "get" this lock can
1516 be broken by class during destroy IIUC.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001517 */
Stephen Hemminger87990462006-08-10 23:35:16 -07001518 if (cl)
1519 cl->filter_cnt++;
1520 else
Linus Torvalds1da177e2005-04-16 15:20:36 -07001521 q->filter_cnt++;
1522 return (unsigned long)cl;
1523}
1524
1525static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1526{
1527 struct htb_sched *q = qdisc_priv(sch);
1528 struct htb_class *cl = (struct htb_class *)arg;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001529
Stephen Hemminger87990462006-08-10 23:35:16 -07001530 if (cl)
1531 cl->filter_cnt--;
1532 else
Linus Torvalds1da177e2005-04-16 15:20:36 -07001533 q->filter_cnt--;
1534}
1535
1536static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1537{
1538 struct htb_sched *q = qdisc_priv(sch);
1539 int i;
1540
1541 if (arg->stop)
1542 return;
1543
1544 for (i = 0; i < HTB_HSIZE; i++) {
Stephen Hemminger0cef2962006-08-10 23:35:38 -07001545 struct hlist_node *p;
1546 struct htb_class *cl;
1547
1548 hlist_for_each_entry(cl, p, q->hash + i, hlist) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001549 if (arg->count < arg->skip) {
1550 arg->count++;
1551 continue;
1552 }
1553 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1554 arg->stop = 1;
1555 return;
1556 }
1557 arg->count++;
1558 }
1559 }
1560}
1561
1562static struct Qdisc_class_ops htb_class_ops = {
1563 .graft = htb_graft,
1564 .leaf = htb_leaf,
1565 .get = htb_get,
1566 .put = htb_put,
1567 .change = htb_change_class,
1568 .delete = htb_delete,
1569 .walk = htb_walk,
1570 .tcf_chain = htb_find_tcf,
1571 .bind_tcf = htb_bind_filter,
1572 .unbind_tcf = htb_unbind_filter,
1573 .dump = htb_dump_class,
1574 .dump_stats = htb_dump_class_stats,
1575};
1576
1577static struct Qdisc_ops htb_qdisc_ops = {
1578 .next = NULL,
1579 .cl_ops = &htb_class_ops,
1580 .id = "htb",
1581 .priv_size = sizeof(struct htb_sched),
1582 .enqueue = htb_enqueue,
1583 .dequeue = htb_dequeue,
1584 .requeue = htb_requeue,
1585 .drop = htb_drop,
1586 .init = htb_init,
1587 .reset = htb_reset,
1588 .destroy = htb_destroy,
1589 .change = NULL /* htb_change */,
1590 .dump = htb_dump,
1591 .owner = THIS_MODULE,
1592};
1593
1594static int __init htb_module_init(void)
1595{
Stephen Hemminger87990462006-08-10 23:35:16 -07001596 return register_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001597}
Stephen Hemminger87990462006-08-10 23:35:16 -07001598static void __exit htb_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001599{
Stephen Hemminger87990462006-08-10 23:35:16 -07001600 unregister_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001601}
Stephen Hemminger87990462006-08-10 23:35:16 -07001602
Linus Torvalds1da177e2005-04-16 15:20:36 -07001603module_init(htb_module_init)
1604module_exit(htb_module_exit)
1605MODULE_LICENSE("GPL");