blob: 79e8ed4ac7ce7de355895b63fc06991be0b6af26 [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
Vimalkumar56b765b2012-10-31 06:04:11 +000074struct htb_rate_cfg {
75 u64 rate_bps;
76 u32 mult;
77 u32 shift;
78};
79
Linus Torvalds1da177e2005-04-16 15:20:36 -070080/* interior & leaf nodes; props specific to leaves are marked L: */
Stephen Hemminger87990462006-08-10 23:35:16 -070081struct htb_class {
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -070082 struct Qdisc_class_common common;
Stephen Hemminger87990462006-08-10 23:35:16 -070083 /* general class parameters */
Eric Dumazetc1a8f1f2009-08-16 09:36:49 +000084 struct gnet_stats_basic_packed bstats;
Stephen Hemminger87990462006-08-10 23:35:16 -070085 struct gnet_stats_queue qstats;
86 struct gnet_stats_rate_est rate_est;
87 struct tc_htb_xstats xstats; /* our special stats */
88 int refcnt; /* usage count of this class */
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
Stephen Hemminger87990462006-08-10 23:35:16 -070090 /* topology */
91 int level; /* our level (see above) */
Patrick McHardy42077592008-07-05 23:22:53 -070092 unsigned int children;
Stephen Hemminger87990462006-08-10 23:35:16 -070093 struct htb_class *parent; /* parent class */
Linus Torvalds1da177e2005-04-16 15:20:36 -070094
Jarek Poplawskic19f7a32008-12-03 21:09:45 -080095 int prio; /* these two are used only by leaves... */
96 int quantum; /* but stored for parent-to-leaf return */
97
Stephen Hemminger87990462006-08-10 23:35:16 -070098 union {
99 struct htb_class_leaf {
100 struct Qdisc *q;
Stephen Hemminger87990462006-08-10 23:35:16 -0700101 int deficit[TC_HTB_MAXDEPTH];
102 struct list_head drop_list;
103 } leaf;
104 struct htb_class_inner {
105 struct rb_root feed[TC_HTB_NUMPRIO]; /* feed trees */
106 struct rb_node *ptr[TC_HTB_NUMPRIO]; /* current class ptr */
107 /* When class changes from state 1->2 and disconnects from
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000108 * parent's feed then we lost ptr value and start from the
109 * first child again. Here we store classid of the
110 * last valid ptr (used when ptr is NULL).
111 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700112 u32 last_ptr_id[TC_HTB_NUMPRIO];
113 } inner;
114 } un;
115 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
116 struct rb_node pq_node; /* node for event queue */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700117 psched_time_t pq_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700118
Stephen Hemminger87990462006-08-10 23:35:16 -0700119 int prio_activity; /* for which prios are we active */
120 enum htb_cmode cmode; /* current mode of the class */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700121
Stephen Hemminger87990462006-08-10 23:35:16 -0700122 /* class attached filters */
123 struct tcf_proto *filter_list;
124 int filter_cnt;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700125
Stephen Hemminger87990462006-08-10 23:35:16 -0700126 /* token bucket parameters */
Vimalkumar56b765b2012-10-31 06:04:11 +0000127 struct htb_rate_cfg rate;
128 struct htb_rate_cfg ceil;
129 s64 buffer, cbuffer; /* token bucket depth/rate */
Stephen Hemminger87990462006-08-10 23:35:16 -0700130 psched_tdiff_t mbuffer; /* max wait time */
Vimalkumar56b765b2012-10-31 06:04:11 +0000131 s64 tokens, ctokens; /* current number of tokens */
Stephen Hemminger87990462006-08-10 23:35:16 -0700132 psched_time_t t_c; /* checkpoint time */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700133};
134
Stephen Hemminger87990462006-08-10 23:35:16 -0700135struct htb_sched {
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700136 struct Qdisc_class_hash clhash;
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700137 struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700138
Stephen Hemminger87990462006-08-10 23:35:16 -0700139 /* self list - roots of self generating tree */
140 struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
141 int row_mask[TC_HTB_MAXDEPTH];
142 struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
143 u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700144
Stephen Hemminger87990462006-08-10 23:35:16 -0700145 /* self wait list - roots of wait PQs per row */
146 struct rb_root wait_pq[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700147
Stephen Hemminger87990462006-08-10 23:35:16 -0700148 /* time of nearest event per level (row) */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700149 psched_time_t near_ev_cache[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700150
Stephen Hemminger87990462006-08-10 23:35:16 -0700151 int defcls; /* class where unclassified flows go to */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152
Stephen Hemminger87990462006-08-10 23:35:16 -0700153 /* filters for qdisc itself */
154 struct tcf_proto *filter_list;
Stephen Hemminger87990462006-08-10 23:35:16 -0700155
156 int rate2quantum; /* quant = rate / rate2quantum */
157 psched_time_t now; /* cached dequeue time */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700158 struct qdisc_watchdog watchdog;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700159
Stephen Hemminger87990462006-08-10 23:35:16 -0700160 /* non shaped skbs; let them go directly thru */
161 struct sk_buff_head direct_queue;
162 int direct_qlen; /* max qlen of above */
163
164 long direct_pkts;
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800165
166#define HTB_WARN_TOOMANYEVENTS 0x1
167 unsigned int warned; /* only one warning */
Jarek Poplawski12247362009-02-01 01:13:22 -0800168 struct work_struct work;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700169};
170
Vimalkumar56b765b2012-10-31 06:04:11 +0000171static u64 l2t_ns(struct htb_rate_cfg *r, unsigned int len)
172{
173 return ((u64)len * r->mult) >> r->shift;
174}
175
176static void htb_precompute_ratedata(struct htb_rate_cfg *r)
177{
178 u64 factor;
179 u64 mult;
180 int shift;
181
182 r->shift = 0;
183 r->mult = 1;
184 /*
185 * Calibrate mult, shift so that token counting is accurate
186 * for smallest packet size (64 bytes). Token (time in ns) is
187 * computed as (bytes * 8) * NSEC_PER_SEC / rate_bps. It will
188 * work as long as the smallest packet transfer time can be
189 * accurately represented in nanosec.
190 */
191 if (r->rate_bps > 0) {
192 /*
193 * Higher shift gives better accuracy. Find the largest
194 * shift such that mult fits in 32 bits.
195 */
196 for (shift = 0; shift < 16; shift++) {
197 r->shift = shift;
198 factor = 8LLU * NSEC_PER_SEC * (1 << r->shift);
199 mult = div64_u64(factor, r->rate_bps);
200 if (mult > UINT_MAX)
201 break;
202 }
203
204 r->shift = shift - 1;
205 factor = 8LLU * NSEC_PER_SEC * (1 << r->shift);
206 r->mult = div64_u64(factor, r->rate_bps);
207 }
208}
209
Linus Torvalds1da177e2005-04-16 15:20:36 -0700210/* find class in global hash table using given handle */
Stephen Hemminger87990462006-08-10 23:35:16 -0700211static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700212{
213 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700214 struct Qdisc_class_common *clc;
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700215
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700216 clc = qdisc_class_find(&q->clhash, handle);
217 if (clc == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700218 return NULL;
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700219 return container_of(clc, struct htb_class, common);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700220}
221
222/**
223 * htb_classify - classify a packet into class
224 *
225 * It returns NULL if the packet should be dropped or -1 if the packet
226 * should be passed directly thru. In all other cases leaf class is returned.
227 * We allow direct class selection by classid in priority. The we examine
228 * filters in qdisc and in inner nodes (if higher filter points to the inner
229 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900230 * internal fifo (direct). These packets then go directly thru. If we still
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300231 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessful
Linus Torvalds1da177e2005-04-16 15:20:36 -0700232 * then finish and return direct queue.
233 */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000234#define HTB_DIRECT ((struct htb_class *)-1L)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700235
Stephen Hemminger87990462006-08-10 23:35:16 -0700236static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
237 int *qerr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700238{
239 struct htb_sched *q = qdisc_priv(sch);
240 struct htb_class *cl;
241 struct tcf_result res;
242 struct tcf_proto *tcf;
243 int result;
244
245 /* allow to select class by setting skb->priority to valid classid;
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000246 * note that nfmark can be used too by attaching filter fw with no
247 * rules in it
248 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700249 if (skb->priority == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700250 return HTB_DIRECT; /* X:0 (direct flow) selected */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000251 cl = htb_find(skb->priority, sch);
252 if (cl && cl->level == 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700253 return cl;
254
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700255 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256 tcf = q->filter_list;
257 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
258#ifdef CONFIG_NET_CLS_ACT
259 switch (result) {
260 case TC_ACT_QUEUED:
Stephen Hemminger87990462006-08-10 23:35:16 -0700261 case TC_ACT_STOLEN:
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700262 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700263 case TC_ACT_SHOT:
264 return NULL;
265 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700266#endif
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000267 cl = (void *)res.class;
268 if (!cl) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700269 if (res.classid == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700270 return HTB_DIRECT; /* X:0 (direct flow) */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000271 cl = htb_find(res.classid, sch);
272 if (!cl)
Stephen Hemminger87990462006-08-10 23:35:16 -0700273 break; /* filter selected invalid classid */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274 }
275 if (!cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700276 return cl; /* we hit leaf; return it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700277
278 /* we have got inner class; apply inner filter chain */
279 tcf = cl->filter_list;
280 }
281 /* classification failed; try to use default class */
Stephen Hemminger87990462006-08-10 23:35:16 -0700282 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700283 if (!cl || cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700284 return HTB_DIRECT; /* bad default .. this is safe bet */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700285 return cl;
286}
287
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288/**
289 * htb_add_to_id_tree - adds class to the round robin list
290 *
291 * Routine adds class to the list (actually tree) sorted by classid.
292 * Make sure that class is not already on such list for given prio.
293 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700294static void htb_add_to_id_tree(struct rb_root *root,
295 struct htb_class *cl, int prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700296{
297 struct rb_node **p = &root->rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700298
Linus Torvalds1da177e2005-04-16 15:20:36 -0700299 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700300 struct htb_class *c;
301 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302 c = rb_entry(parent, struct htb_class, node[prio]);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700303
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700304 if (cl->common.classid > c->common.classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700305 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700306 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700307 p = &parent->rb_left;
308 }
309 rb_link_node(&cl->node[prio], parent, p);
310 rb_insert_color(&cl->node[prio], root);
311}
312
313/**
314 * htb_add_to_wait_tree - adds class to the event queue with delay
315 *
316 * The class is added to priority event queue to indicate that class will
317 * change its mode in cl->pq_key microseconds. Make sure that class is not
318 * already in the queue.
319 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700320static void htb_add_to_wait_tree(struct htb_sched *q,
Vimalkumar56b765b2012-10-31 06:04:11 +0000321 struct htb_class *cl, s64 delay)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700322{
323 struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700324
Patrick McHardyfb983d42007-03-16 01:22:39 -0700325 cl->pq_key = q->now + delay;
326 if (cl->pq_key == q->now)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700327 cl->pq_key++;
328
329 /* update the nearest event cache */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700330 if (q->near_ev_cache[cl->level] > cl->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700331 q->near_ev_cache[cl->level] = cl->pq_key;
Stephen Hemminger87990462006-08-10 23:35:16 -0700332
Linus Torvalds1da177e2005-04-16 15:20:36 -0700333 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700334 struct htb_class *c;
335 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336 c = rb_entry(parent, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700337 if (cl->pq_key >= c->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700338 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700339 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700340 p = &parent->rb_left;
341 }
342 rb_link_node(&cl->pq_node, parent, p);
343 rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
344}
345
346/**
347 * htb_next_rb_node - finds next node in binary tree
348 *
349 * When we are past last key we return NULL.
350 * Average complexity is 2 steps per call.
351 */
Stephen Hemminger3696f622006-08-10 23:36:01 -0700352static inline void htb_next_rb_node(struct rb_node **n)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700353{
354 *n = rb_next(*n);
355}
356
357/**
358 * htb_add_class_to_row - add class to its row
359 *
360 * The class is added to row at priorities marked in mask.
361 * It does nothing if mask == 0.
362 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700363static inline void htb_add_class_to_row(struct htb_sched *q,
364 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700365{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700366 q->row_mask[cl->level] |= mask;
367 while (mask) {
368 int prio = ffz(~mask);
369 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700370 htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700371 }
372}
373
Stephen Hemminger3696f622006-08-10 23:36:01 -0700374/* If this triggers, it is a bug in this code, but it need not be fatal */
375static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
376{
Ismail Donmez81771b32006-10-03 13:49:10 -0700377 if (RB_EMPTY_NODE(rb)) {
Stephen Hemminger3696f622006-08-10 23:36:01 -0700378 WARN_ON(1);
379 } else {
380 rb_erase(rb, root);
381 RB_CLEAR_NODE(rb);
382 }
383}
384
385
Linus Torvalds1da177e2005-04-16 15:20:36 -0700386/**
387 * htb_remove_class_from_row - removes class from its row
388 *
389 * The class is removed from row at priorities marked in mask.
390 * It does nothing if mask == 0.
391 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700392static inline void htb_remove_class_from_row(struct htb_sched *q,
393 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700394{
395 int m = 0;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700396
Linus Torvalds1da177e2005-04-16 15:20:36 -0700397 while (mask) {
398 int prio = ffz(~mask);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700399
Linus Torvalds1da177e2005-04-16 15:20:36 -0700400 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700401 if (q->ptr[cl->level][prio] == cl->node + prio)
402 htb_next_rb_node(q->ptr[cl->level] + prio);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700403
404 htb_safe_rb_erase(cl->node + prio, q->row[cl->level] + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700405 if (!q->row[cl->level][prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700406 m |= 1 << prio;
407 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700408 q->row_mask[cl->level] &= ~m;
409}
410
411/**
412 * htb_activate_prios - creates active classe's feed chain
413 *
414 * The class is connected to ancestors and/or appropriate rows
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900415 * for priorities it is participating on. cl->cmode must be new
Linus Torvalds1da177e2005-04-16 15:20:36 -0700416 * (activated) mode. It does nothing if cl->prio_activity == 0.
417 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700418static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700419{
420 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700421 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700422
423 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700424 m = mask;
425 while (m) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426 int prio = ffz(~m);
427 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700428
Linus Torvalds1da177e2005-04-16 15:20:36 -0700429 if (p->un.inner.feed[prio].rb_node)
430 /* parent already has its feed in use so that
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000431 * reset bit in mask as parent is already ok
432 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700433 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700434
435 htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700436 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700437 p->prio_activity |= mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700438 cl = p;
439 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700440
Linus Torvalds1da177e2005-04-16 15:20:36 -0700441 }
442 if (cl->cmode == HTB_CAN_SEND && mask)
Stephen Hemminger87990462006-08-10 23:35:16 -0700443 htb_add_class_to_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700444}
445
446/**
447 * htb_deactivate_prios - remove class from feed chain
448 *
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900449 * cl->cmode must represent old mode (before deactivation). It does
Linus Torvalds1da177e2005-04-16 15:20:36 -0700450 * nothing if cl->prio_activity == 0. Class is removed from all feed
451 * chains and rows.
452 */
453static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
454{
455 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700456 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700457
458 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700459 m = mask;
460 mask = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700461 while (m) {
462 int prio = ffz(~m);
463 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700464
465 if (p->un.inner.ptr[prio] == cl->node + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700466 /* we are removing child which is pointed to from
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000467 * parent feed - forget the pointer but remember
468 * classid
469 */
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700470 p->un.inner.last_ptr_id[prio] = cl->common.classid;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700471 p->un.inner.ptr[prio] = NULL;
472 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700473
Stephen Hemminger3696f622006-08-10 23:36:01 -0700474 htb_safe_rb_erase(cl->node + prio, p->un.inner.feed + prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700475
476 if (!p->un.inner.feed[prio].rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477 mask |= 1 << prio;
478 }
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700479
Linus Torvalds1da177e2005-04-16 15:20:36 -0700480 p->prio_activity &= ~mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700481 cl = p;
482 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700483
Linus Torvalds1da177e2005-04-16 15:20:36 -0700484 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700485 if (cl->cmode == HTB_CAN_SEND && mask)
486 htb_remove_class_from_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700487}
488
Vimalkumar56b765b2012-10-31 06:04:11 +0000489static inline s64 htb_lowater(const struct htb_class *cl)
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700490{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700491 if (htb_hysteresis)
492 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
493 else
494 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700495}
Vimalkumar56b765b2012-10-31 06:04:11 +0000496static inline s64 htb_hiwater(const struct htb_class *cl)
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700497{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700498 if (htb_hysteresis)
499 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
500 else
501 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700502}
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700503
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700504
Linus Torvalds1da177e2005-04-16 15:20:36 -0700505/**
506 * htb_class_mode - computes and returns current class mode
507 *
508 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
509 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900510 * from now to time when cl will change its state.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700511 * Also it is worth to note that class mode doesn't change simply
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900512 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
Linus Torvalds1da177e2005-04-16 15:20:36 -0700513 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
514 * mode transitions per time unit. The speed gain is about 1/6.
515 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700516static inline enum htb_cmode
Vimalkumar56b765b2012-10-31 06:04:11 +0000517htb_class_mode(struct htb_class *cl, s64 *diff)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700518{
Vimalkumar56b765b2012-10-31 06:04:11 +0000519 s64 toks;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700520
Stephen Hemminger87990462006-08-10 23:35:16 -0700521 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
522 *diff = -toks;
523 return HTB_CANT_SEND;
524 }
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700525
Stephen Hemminger87990462006-08-10 23:35:16 -0700526 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
527 return HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700528
Stephen Hemminger87990462006-08-10 23:35:16 -0700529 *diff = -toks;
530 return HTB_MAY_BORROW;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531}
532
533/**
534 * htb_change_class_mode - changes classe's mode
535 *
536 * This should be the only way how to change classe's mode under normal
537 * cirsumstances. Routine will update feed lists linkage, change mode
538 * and add class to the wait event queue if appropriate. New mode should
539 * be different from old one and cl->pq_key has to be valid if changing
540 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
541 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700542static void
Vimalkumar56b765b2012-10-31 06:04:11 +0000543htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, s64 *diff)
Stephen Hemminger87990462006-08-10 23:35:16 -0700544{
545 enum htb_cmode new_mode = htb_class_mode(cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700546
547 if (new_mode == cl->cmode)
Stephen Hemminger87990462006-08-10 23:35:16 -0700548 return;
549
550 if (cl->prio_activity) { /* not necessary: speed optimization */
551 if (cl->cmode != HTB_CANT_SEND)
552 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700553 cl->cmode = new_mode;
Stephen Hemminger87990462006-08-10 23:35:16 -0700554 if (new_mode != HTB_CANT_SEND)
555 htb_activate_prios(q, cl);
556 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700557 cl->cmode = new_mode;
558}
559
560/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900561 * htb_activate - inserts leaf cl into appropriate active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700562 *
563 * Routine learns (new) priority of leaf and activates feed chain
564 * for the prio. It can be called on already active leaf safely.
565 * It also adds leaf into droplist.
566 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700567static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700568{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700569 WARN_ON(cl->level || !cl->un.leaf.q || !cl->un.leaf.q->q.qlen);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700570
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571 if (!cl->prio_activity) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800572 cl->prio_activity = 1 << cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700573 htb_activate_prios(q, cl);
574 list_add_tail(&cl->un.leaf.drop_list,
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800575 q->drops + cl->prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700576 }
577}
578
579/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900580 * htb_deactivate - remove leaf cl from active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700581 *
582 * Make sure that leaf is active. In the other words it can't be called
583 * with non-active leaf. It also removes class from the drop list.
584 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700585static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700586{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700587 WARN_ON(!cl->prio_activity);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700588
Stephen Hemminger87990462006-08-10 23:35:16 -0700589 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700590 cl->prio_activity = 0;
591 list_del_init(&cl->un.leaf.drop_list);
592}
593
594static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
595{
Jarek Poplawskif30ab412008-11-13 22:56:30 -0800596 int uninitialized_var(ret);
Stephen Hemminger87990462006-08-10 23:35:16 -0700597 struct htb_sched *q = qdisc_priv(sch);
598 struct htb_class *cl = htb_classify(skb, sch, &ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700599
Stephen Hemminger87990462006-08-10 23:35:16 -0700600 if (cl == HTB_DIRECT) {
601 /* enqueue to helper queue */
602 if (q->direct_queue.qlen < q->direct_qlen) {
603 __skb_queue_tail(&q->direct_queue, skb);
604 q->direct_pkts++;
605 } else {
Eric Dumazet17045752012-05-04 04:37:21 +0000606 return qdisc_drop(skb, sch);
Stephen Hemminger87990462006-08-10 23:35:16 -0700607 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700608#ifdef CONFIG_NET_CLS_ACT
Stephen Hemminger87990462006-08-10 23:35:16 -0700609 } else if (!cl) {
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700610 if (ret & __NET_XMIT_BYPASS)
Stephen Hemminger87990462006-08-10 23:35:16 -0700611 sch->qstats.drops++;
612 kfree_skb(skb);
613 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700614#endif
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700615 } else if ((ret = qdisc_enqueue(skb, cl->un.leaf.q)) != NET_XMIT_SUCCESS) {
616 if (net_xmit_drop_count(ret)) {
617 sch->qstats.drops++;
618 cl->qstats.drops++;
619 }
David S. Miller69747652008-08-17 23:55:36 -0700620 return ret;
Stephen Hemminger87990462006-08-10 23:35:16 -0700621 } else {
Stephen Hemminger87990462006-08-10 23:35:16 -0700622 htb_activate(q, cl);
623 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700624
Stephen Hemminger87990462006-08-10 23:35:16 -0700625 sch->q.qlen++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700626 return NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700627}
628
Vimalkumar56b765b2012-10-31 06:04:11 +0000629static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, s64 diff)
Jarek Poplawski59e42202008-12-03 21:17:27 -0800630{
Vimalkumar56b765b2012-10-31 06:04:11 +0000631 s64 toks = diff + cl->tokens;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800632
633 if (toks > cl->buffer)
634 toks = cl->buffer;
Vimalkumar56b765b2012-10-31 06:04:11 +0000635 toks -= (s64) l2t_ns(&cl->rate, bytes);
Jarek Poplawski59e42202008-12-03 21:17:27 -0800636 if (toks <= -cl->mbuffer)
637 toks = 1 - cl->mbuffer;
638
639 cl->tokens = toks;
640}
641
Vimalkumar56b765b2012-10-31 06:04:11 +0000642static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, s64 diff)
Jarek Poplawski59e42202008-12-03 21:17:27 -0800643{
Vimalkumar56b765b2012-10-31 06:04:11 +0000644 s64 toks = diff + cl->ctokens;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800645
646 if (toks > cl->cbuffer)
647 toks = cl->cbuffer;
Vimalkumar56b765b2012-10-31 06:04:11 +0000648 toks -= (s64) l2t_ns(&cl->ceil, bytes);
Jarek Poplawski59e42202008-12-03 21:17:27 -0800649 if (toks <= -cl->mbuffer)
650 toks = 1 - cl->mbuffer;
651
652 cl->ctokens = toks;
653}
654
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655/**
656 * htb_charge_class - charges amount "bytes" to leaf and ancestors
657 *
658 * Routine assumes that packet "bytes" long was dequeued from leaf cl
659 * borrowing from "level". It accounts bytes to ceil leaky bucket for
660 * leaf and all ancestors and to rate bucket for ancestors at levels
661 * "level" and higher. It also handles possible change of mode resulting
662 * from the update. Note that mode can also increase here (MAY_BORROW to
663 * CAN_SEND) because we can use more precise clock that event queue here.
664 * In such case we remove class from event queue first.
665 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700666static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700667 int level, struct sk_buff *skb)
Stephen Hemminger87990462006-08-10 23:35:16 -0700668{
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700669 int bytes = qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670 enum htb_cmode old_mode;
Vimalkumar56b765b2012-10-31 06:04:11 +0000671 s64 diff;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672
673 while (cl) {
Vimalkumar56b765b2012-10-31 06:04:11 +0000674 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700675 if (cl->level >= level) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700676 if (cl->level == level)
677 cl->xstats.lends++;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800678 htb_accnt_tokens(cl, bytes, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700679 } else {
680 cl->xstats.borrows++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700681 cl->tokens += diff; /* we moved t_c; update tokens */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700682 }
Jarek Poplawski59e42202008-12-03 21:17:27 -0800683 htb_accnt_ctokens(cl, bytes, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700684 cl->t_c = q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685
Stephen Hemminger87990462006-08-10 23:35:16 -0700686 old_mode = cl->cmode;
687 diff = 0;
688 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700689 if (old_mode != cl->cmode) {
690 if (old_mode != HTB_CAN_SEND)
Stephen Hemminger3696f622006-08-10 23:36:01 -0700691 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700692 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700693 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700694 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700695
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000696 /* update basic stats except for leaves which are already updated */
697 if (cl->level)
698 bstats_update(&cl->bstats, skb);
699
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700 cl = cl->parent;
701 }
702}
703
704/**
705 * htb_do_events - make mode changes to classes at the level
706 *
Patrick McHardyfb983d42007-03-16 01:22:39 -0700707 * Scans event queue for pending events and applies them. Returns time of
Jarek Poplawski12247362009-02-01 01:13:22 -0800708 * next pending event (0 for no event in pq, q->now for too many events).
Patrick McHardyfb983d42007-03-16 01:22:39 -0700709 * Note: Applied are events whose have cl->pq_key <= q->now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700710 */
Jarek Poplawskia73be042009-01-12 21:54:40 -0800711static psched_time_t htb_do_events(struct htb_sched *q, int level,
712 unsigned long start)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700713{
Martin Devera8f3ea332008-03-23 22:00:38 -0700714 /* don't run for longer than 2 jiffies; 2 is used instead of
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000715 * 1 to simplify things when jiffy is going to be incremented
716 * too soon
717 */
Jarek Poplawskia73be042009-01-12 21:54:40 -0800718 unsigned long stop_at = start + 2;
Martin Devera8f3ea332008-03-23 22:00:38 -0700719 while (time_before(jiffies, stop_at)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720 struct htb_class *cl;
Vimalkumar56b765b2012-10-31 06:04:11 +0000721 s64 diff;
Akinbou Mita30bdbe32006-10-12 01:52:05 -0700722 struct rb_node *p = rb_first(&q->wait_pq[level]);
723
Stephen Hemminger87990462006-08-10 23:35:16 -0700724 if (!p)
725 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700726
727 cl = rb_entry(p, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700728 if (cl->pq_key > q->now)
729 return cl->pq_key;
730
Stephen Hemminger3696f622006-08-10 23:36:01 -0700731 htb_safe_rb_erase(p, q->wait_pq + level);
Vimalkumar56b765b2012-10-31 06:04:11 +0000732 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
Stephen Hemminger87990462006-08-10 23:35:16 -0700733 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700734 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700735 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700736 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800737
738 /* too much load - let's continue after a break for scheduling */
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800739 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000740 pr_warning("htb: too many events!\n");
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800741 q->warned |= HTB_WARN_TOOMANYEVENTS;
742 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800743
744 return q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700745}
746
747/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000748 * is no such one exists.
749 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700750static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
751 u32 id)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700752{
753 struct rb_node *r = NULL;
754 while (n) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700755 struct htb_class *cl =
756 rb_entry(n, struct htb_class, node[prio]);
Stephen Hemminger87990462006-08-10 23:35:16 -0700757
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700758 if (id > cl->common.classid) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700759 n = n->rb_right;
Jarek Poplawski1b5c0072008-12-09 22:34:40 -0800760 } else if (id < cl->common.classid) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700761 r = n;
762 n = n->rb_left;
Jarek Poplawski1b5c0072008-12-09 22:34:40 -0800763 } else {
764 return n;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700765 }
766 }
767 return r;
768}
769
770/**
771 * htb_lookup_leaf - returns next leaf class in DRR order
772 *
773 * Find leaf where current feed pointers points to.
774 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700775static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio,
776 struct rb_node **pptr, u32 * pid)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700777{
778 int i;
779 struct {
780 struct rb_node *root;
781 struct rb_node **pptr;
782 u32 *pid;
Stephen Hemminger87990462006-08-10 23:35:16 -0700783 } stk[TC_HTB_MAXDEPTH], *sp = stk;
784
Jarek Poplawski512bb432008-12-09 22:35:02 -0800785 BUG_ON(!tree->rb_node);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700786 sp->root = tree->rb_node;
787 sp->pptr = pptr;
788 sp->pid = pid;
789
790 for (i = 0; i < 65535; i++) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700791 if (!*sp->pptr && *sp->pid) {
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900792 /* ptr was invalidated but id is valid - try to recover
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000793 * the original or next ptr
794 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700795 *sp->pptr =
796 htb_id_find_next_upper(prio, sp->root, *sp->pid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700797 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700798 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000799 * can become out of date quickly
800 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700801 if (!*sp->pptr) { /* we are at right end; rewind & go up */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700802 *sp->pptr = sp->root;
Stephen Hemminger87990462006-08-10 23:35:16 -0700803 while ((*sp->pptr)->rb_left)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700804 *sp->pptr = (*sp->pptr)->rb_left;
805 if (sp > stk) {
806 sp--;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800807 if (!*sp->pptr) {
808 WARN_ON(1);
Stephen Hemminger87990462006-08-10 23:35:16 -0700809 return NULL;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800810 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700811 htb_next_rb_node(sp->pptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700812 }
813 } else {
814 struct htb_class *cl;
Stephen Hemminger87990462006-08-10 23:35:16 -0700815 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
816 if (!cl->level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700817 return cl;
818 (++sp)->root = cl->un.inner.feed[prio].rb_node;
Stephen Hemminger87990462006-08-10 23:35:16 -0700819 sp->pptr = cl->un.inner.ptr + prio;
820 sp->pid = cl->un.inner.last_ptr_id + prio;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700821 }
822 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700823 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700824 return NULL;
825}
826
827/* dequeues packet at given priority and level; call only if
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000828 * you are sure that there is active class at prio/level
829 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700830static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
831 int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700832{
833 struct sk_buff *skb = NULL;
Stephen Hemminger87990462006-08-10 23:35:16 -0700834 struct htb_class *cl, *start;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700835 /* look initial class up in the row */
Stephen Hemminger87990462006-08-10 23:35:16 -0700836 start = cl = htb_lookup_leaf(q->row[level] + prio, prio,
837 q->ptr[level] + prio,
838 q->last_ptr_id[level] + prio);
839
Linus Torvalds1da177e2005-04-16 15:20:36 -0700840 do {
841next:
Jarek Poplawski512bb432008-12-09 22:35:02 -0800842 if (unlikely(!cl))
Stephen Hemminger87990462006-08-10 23:35:16 -0700843 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844
845 /* class can be empty - it is unlikely but can be true if leaf
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000846 * qdisc drops packets in enqueue routine or if someone used
847 * graft operation on the leaf since last dequeue;
848 * simply deactivate and skip such class
849 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700850 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
851 struct htb_class *next;
Stephen Hemminger87990462006-08-10 23:35:16 -0700852 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700853
854 /* row/level might become empty */
855 if ((q->row_mask[level] & (1 << prio)) == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -0700856 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700857
Stephen Hemminger87990462006-08-10 23:35:16 -0700858 next = htb_lookup_leaf(q->row[level] + prio,
859 prio, q->ptr[level] + prio,
860 q->last_ptr_id[level] + prio);
861
862 if (cl == start) /* fix start if we just deleted it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700863 start = next;
864 cl = next;
865 goto next;
866 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700867
868 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
869 if (likely(skb != NULL))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700870 break;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800871
Jarek Poplawskib00355d2009-02-01 01:12:42 -0800872 qdisc_warn_nonwc("htb", cl->un.leaf.q);
Stephen Hemminger87990462006-08-10 23:35:16 -0700873 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
874 ptr[0]) + prio);
875 cl = htb_lookup_leaf(q->row[level] + prio, prio,
876 q->ptr[level] + prio,
877 q->last_ptr_id[level] + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700878
879 } while (cl != start);
880
881 if (likely(skb != NULL)) {
Eric Dumazet196d97f2012-11-05 16:40:49 +0000882 bstats_update(&cl->bstats, skb);
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700883 cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb);
884 if (cl->un.leaf.deficit[level] < 0) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800885 cl->un.leaf.deficit[level] += cl->quantum;
Stephen Hemminger87990462006-08-10 23:35:16 -0700886 htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
887 ptr[0]) + prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700888 }
889 /* this used to be after charge_class but this constelation
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000890 * gives us slightly better performance
891 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700893 htb_deactivate(q, cl);
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700894 htb_charge_class(q, cl, level, skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895 }
896 return skb;
897}
898
Linus Torvalds1da177e2005-04-16 15:20:36 -0700899static struct sk_buff *htb_dequeue(struct Qdisc *sch)
900{
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800901 struct sk_buff *skb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700902 struct htb_sched *q = qdisc_priv(sch);
903 int level;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700904 psched_time_t next_event;
Jarek Poplawskia73be042009-01-12 21:54:40 -0800905 unsigned long start_at;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700906
907 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
Stephen Hemminger87990462006-08-10 23:35:16 -0700908 skb = __skb_dequeue(&q->direct_queue);
909 if (skb != NULL) {
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800910ok:
911 qdisc_bstats_update(sch, skb);
Eric Dumazetfd245a42011-01-20 05:27:16 +0000912 qdisc_unthrottled(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700913 sch->q.qlen--;
914 return skb;
915 }
916
Stephen Hemminger87990462006-08-10 23:35:16 -0700917 if (!sch->q.qlen)
918 goto fin;
Vimalkumar56b765b2012-10-31 06:04:11 +0000919 q->now = ktime_to_ns(ktime_get());
Jarek Poplawskia73be042009-01-12 21:54:40 -0800920 start_at = jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700921
Stefan Haskod2fe85d2012-12-21 15:04:59 +0000922 next_event = q->now + 5LLU * NSEC_PER_SEC;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800923
Linus Torvalds1da177e2005-04-16 15:20:36 -0700924 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
925 /* common case optimization - skip event handler quickly */
926 int m;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700927 psched_time_t event;
Stephen Hemminger87990462006-08-10 23:35:16 -0700928
Patrick McHardyfb983d42007-03-16 01:22:39 -0700929 if (q->now >= q->near_ev_cache[level]) {
Jarek Poplawskia73be042009-01-12 21:54:40 -0800930 event = htb_do_events(q, level, start_at);
Patrick McHardy2e4b3b02007-05-23 23:39:54 -0700931 if (!event)
Vimalkumar56b765b2012-10-31 06:04:11 +0000932 event = q->now + NSEC_PER_SEC;
Patrick McHardy2e4b3b02007-05-23 23:39:54 -0700933 q->near_ev_cache[level] = event;
Patrick McHardyfb983d42007-03-16 01:22:39 -0700934 } else
935 event = q->near_ev_cache[level];
936
Jarek Poplawskic0851342009-01-12 21:54:16 -0800937 if (next_event > event)
Patrick McHardyfb983d42007-03-16 01:22:39 -0700938 next_event = event;
939
Linus Torvalds1da177e2005-04-16 15:20:36 -0700940 m = ~q->row_mask[level];
941 while (m != (int)(-1)) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700942 int prio = ffz(m);
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000943
Linus Torvalds1da177e2005-04-16 15:20:36 -0700944 m |= 1 << prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700945 skb = htb_dequeue_tree(q, prio, level);
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800946 if (likely(skb != NULL))
947 goto ok;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700948 }
949 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700950 sch->qstats.overlimits++;
Vimalkumar56b765b2012-10-31 06:04:11 +0000951 if (likely(next_event > q->now)) {
952 if (!test_bit(__QDISC_STATE_DEACTIVATED,
953 &qdisc_root_sleeping(q->watchdog.qdisc)->state)) {
954 ktime_t time = ns_to_ktime(next_event);
955 qdisc_throttled(q->watchdog.qdisc);
956 hrtimer_start(&q->watchdog.timer, time,
957 HRTIMER_MODE_ABS);
958 }
959 } else {
Jarek Poplawski12247362009-02-01 01:13:22 -0800960 schedule_work(&q->work);
Vimalkumar56b765b2012-10-31 06:04:11 +0000961 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700962fin:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700963 return skb;
964}
965
966/* try to drop from each class (by prio) until one succeed */
Stephen Hemminger87990462006-08-10 23:35:16 -0700967static unsigned int htb_drop(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700968{
969 struct htb_sched *q = qdisc_priv(sch);
970 int prio;
971
972 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
973 struct list_head *p;
Stephen Hemminger87990462006-08-10 23:35:16 -0700974 list_for_each(p, q->drops + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700975 struct htb_class *cl = list_entry(p, struct htb_class,
976 un.leaf.drop_list);
977 unsigned int len;
Stephen Hemminger87990462006-08-10 23:35:16 -0700978 if (cl->un.leaf.q->ops->drop &&
979 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980 sch->q.qlen--;
981 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700982 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700983 return len;
984 }
985 }
986 }
987 return 0;
988}
989
990/* reset all classes */
991/* always caled under BH & queue lock */
Stephen Hemminger87990462006-08-10 23:35:16 -0700992static void htb_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700993{
994 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700995 struct htb_class *cl;
996 struct hlist_node *n;
997 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700998
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700999 for (i = 0; i < q->clhash.hashsize; i++) {
1000 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001001 if (cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -07001002 memset(&cl->un.inner, 0, sizeof(cl->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001003 else {
Stephen Hemminger87990462006-08-10 23:35:16 -07001004 if (cl->un.leaf.q)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001005 qdisc_reset(cl->un.leaf.q);
1006 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
1007 }
1008 cl->prio_activity = 0;
1009 cl->cmode = HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001010
1011 }
1012 }
Patrick McHardyfb983d42007-03-16 01:22:39 -07001013 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001014 __skb_queue_purge(&q->direct_queue);
1015 sch->q.qlen = 0;
Stephen Hemminger87990462006-08-10 23:35:16 -07001016 memset(q->row, 0, sizeof(q->row));
1017 memset(q->row_mask, 0, sizeof(q->row_mask));
1018 memset(q->wait_pq, 0, sizeof(q->wait_pq));
1019 memset(q->ptr, 0, sizeof(q->ptr));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001020 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -07001021 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001022}
1023
Patrick McHardy27a34212008-01-23 20:35:39 -08001024static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
1025 [TCA_HTB_PARMS] = { .len = sizeof(struct tc_htb_opt) },
1026 [TCA_HTB_INIT] = { .len = sizeof(struct tc_htb_glob) },
1027 [TCA_HTB_CTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1028 [TCA_HTB_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1029};
1030
Jarek Poplawski12247362009-02-01 01:13:22 -08001031static void htb_work_func(struct work_struct *work)
1032{
1033 struct htb_sched *q = container_of(work, struct htb_sched, work);
1034 struct Qdisc *sch = q->watchdog.qdisc;
1035
1036 __netif_schedule(qdisc_root(sch));
1037}
1038
Patrick McHardy1e904742008-01-22 22:11:17 -08001039static int htb_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001040{
1041 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -08001042 struct nlattr *tb[TCA_HTB_INIT + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001043 struct tc_htb_glob *gopt;
Patrick McHardycee63722008-01-23 20:33:32 -08001044 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001045 int i;
Patrick McHardycee63722008-01-23 20:33:32 -08001046
1047 if (!opt)
1048 return -EINVAL;
1049
Patrick McHardy27a34212008-01-23 20:35:39 -08001050 err = nla_parse_nested(tb, TCA_HTB_INIT, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -08001051 if (err < 0)
1052 return err;
1053
Patrick McHardy27a34212008-01-23 20:35:39 -08001054 if (tb[TCA_HTB_INIT] == NULL) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001055 pr_err("HTB: hey probably you have bad tc tool ?\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001056 return -EINVAL;
1057 }
Patrick McHardy1e904742008-01-22 22:11:17 -08001058 gopt = nla_data(tb[TCA_HTB_INIT]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001059 if (gopt->version != HTB_VER >> 16) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001060 pr_err("HTB: need tc/htb version %d (minor is %d), you have %d\n",
Stephen Hemminger87990462006-08-10 23:35:16 -07001061 HTB_VER >> 16, HTB_VER & 0xffff, gopt->version);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001062 return -EINVAL;
1063 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001064
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001065 err = qdisc_class_hash_init(&q->clhash);
1066 if (err < 0)
1067 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001068 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -07001069 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001070
Patrick McHardyfb983d42007-03-16 01:22:39 -07001071 qdisc_watchdog_init(&q->watchdog, sch);
Jarek Poplawski12247362009-02-01 01:13:22 -08001072 INIT_WORK(&q->work, htb_work_func);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001073 skb_queue_head_init(&q->direct_queue);
1074
David S. Miller5ce2d482008-07-08 17:06:30 -07001075 q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
Stephen Hemminger87990462006-08-10 23:35:16 -07001076 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001077 q->direct_qlen = 2;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001078
Linus Torvalds1da177e2005-04-16 15:20:36 -07001079 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1080 q->rate2quantum = 1;
1081 q->defcls = gopt->defcls;
1082
1083 return 0;
1084}
1085
1086static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1087{
Jarek Poplawski102396a2008-08-29 14:21:52 -07001088 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001089 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001090 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001091 struct tc_htb_glob gopt;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001092
David S. Miller7698b4f2008-07-16 01:42:40 -07001093 spin_lock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001094
1095 gopt.direct_pkts = q->direct_pkts;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001096 gopt.version = HTB_VER;
1097 gopt.rate2quantum = q->rate2quantum;
1098 gopt.defcls = q->defcls;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001099 gopt.debug = 0;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001100
1101 nest = nla_nest_start(skb, TCA_OPTIONS);
1102 if (nest == NULL)
1103 goto nla_put_failure;
David S. Miller1b34ec42012-03-29 05:11:39 -04001104 if (nla_put(skb, TCA_HTB_INIT, sizeof(gopt), &gopt))
1105 goto nla_put_failure;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001106 nla_nest_end(skb, nest);
1107
David S. Miller7698b4f2008-07-16 01:42:40 -07001108 spin_unlock_bh(root_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001109 return skb->len;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001110
Patrick McHardy1e904742008-01-22 22:11:17 -08001111nla_put_failure:
David S. Miller7698b4f2008-07-16 01:42:40 -07001112 spin_unlock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001113 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001114 return -1;
1115}
1116
1117static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
Stephen Hemminger87990462006-08-10 23:35:16 -07001118 struct sk_buff *skb, struct tcmsg *tcm)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001119{
Stephen Hemminger87990462006-08-10 23:35:16 -07001120 struct htb_class *cl = (struct htb_class *)arg;
Jarek Poplawski102396a2008-08-29 14:21:52 -07001121 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001122 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001123 struct tc_htb_opt opt;
1124
David S. Miller7698b4f2008-07-16 01:42:40 -07001125 spin_lock_bh(root_lock);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001126 tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
1127 tcm->tcm_handle = cl->common.classid;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001128 if (!cl->level && cl->un.leaf.q)
1129 tcm->tcm_info = cl->un.leaf.q->handle;
1130
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001131 nest = nla_nest_start(skb, TCA_OPTIONS);
1132 if (nest == NULL)
1133 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001134
Stephen Hemminger87990462006-08-10 23:35:16 -07001135 memset(&opt, 0, sizeof(opt));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001136
Vimalkumar56b765b2012-10-31 06:04:11 +00001137 opt.rate.rate = cl->rate.rate_bps >> 3;
Jiri Pirko9c10f412013-02-12 00:12:00 +00001138 opt.buffer = PSCHED_NS2TICKS(cl->buffer);
Vimalkumar56b765b2012-10-31 06:04:11 +00001139 opt.ceil.rate = cl->ceil.rate_bps >> 3;
Jiri Pirko9c10f412013-02-12 00:12:00 +00001140 opt.cbuffer = PSCHED_NS2TICKS(cl->cbuffer);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001141 opt.quantum = cl->quantum;
1142 opt.prio = cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -07001143 opt.level = cl->level;
David S. Miller1b34ec42012-03-29 05:11:39 -04001144 if (nla_put(skb, TCA_HTB_PARMS, sizeof(opt), &opt))
1145 goto nla_put_failure;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001146
1147 nla_nest_end(skb, nest);
David S. Miller7698b4f2008-07-16 01:42:40 -07001148 spin_unlock_bh(root_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001149 return skb->len;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001150
Patrick McHardy1e904742008-01-22 22:11:17 -08001151nla_put_failure:
David S. Miller7698b4f2008-07-16 01:42:40 -07001152 spin_unlock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001153 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001154 return -1;
1155}
1156
1157static int
Stephen Hemminger87990462006-08-10 23:35:16 -07001158htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001159{
Stephen Hemminger87990462006-08-10 23:35:16 -07001160 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001161
Linus Torvalds1da177e2005-04-16 15:20:36 -07001162 if (!cl->level && cl->un.leaf.q)
1163 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
1164 cl->xstats.tokens = cl->tokens;
1165 cl->xstats.ctokens = cl->ctokens;
1166
1167 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
Eric Dumazetd250a5f2009-10-02 10:32:18 +00001168 gnet_stats_copy_rate_est(d, NULL, &cl->rate_est) < 0 ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001169 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1170 return -1;
1171
1172 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1173}
1174
1175static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
Stephen Hemminger87990462006-08-10 23:35:16 -07001176 struct Qdisc **old)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001177{
Stephen Hemminger87990462006-08-10 23:35:16 -07001178 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001179
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001180 if (cl->level)
1181 return -EINVAL;
1182 if (new == NULL &&
Changli Gao3511c912010-10-16 13:04:08 +00001183 (new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001184 cl->common.classid)) == NULL)
1185 return -ENOBUFS;
1186
1187 sch_tree_lock(sch);
1188 *old = cl->un.leaf.q;
1189 cl->un.leaf.q = new;
1190 if (*old != NULL) {
1191 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1192 qdisc_reset(*old);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001193 }
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001194 sch_tree_unlock(sch);
1195 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001196}
1197
Stephen Hemminger87990462006-08-10 23:35:16 -07001198static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001199{
Stephen Hemminger87990462006-08-10 23:35:16 -07001200 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001201 return !cl->level ? cl->un.leaf.q : NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001202}
1203
Patrick McHardy256d61b2006-11-29 17:37:05 -08001204static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
1205{
1206 struct htb_class *cl = (struct htb_class *)arg;
1207
1208 if (cl->un.leaf.q->q.qlen == 0)
1209 htb_deactivate(qdisc_priv(sch), cl);
1210}
1211
Linus Torvalds1da177e2005-04-16 15:20:36 -07001212static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1213{
Stephen Hemminger87990462006-08-10 23:35:16 -07001214 struct htb_class *cl = htb_find(classid, sch);
1215 if (cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001216 cl->refcnt++;
1217 return (unsigned long)cl;
1218}
1219
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001220static inline int htb_parent_last_child(struct htb_class *cl)
1221{
1222 if (!cl->parent)
1223 /* the root class */
1224 return 0;
Patrick McHardy42077592008-07-05 23:22:53 -07001225 if (cl->parent->children > 1)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001226 /* not the last child */
1227 return 0;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001228 return 1;
1229}
1230
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001231static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl,
1232 struct Qdisc *new_q)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001233{
1234 struct htb_class *parent = cl->parent;
1235
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001236 WARN_ON(cl->level || !cl->un.leaf.q || cl->prio_activity);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001237
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001238 if (parent->cmode != HTB_CAN_SEND)
1239 htb_safe_rb_erase(&parent->pq_node, q->wait_pq + parent->level);
1240
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001241 parent->level = 0;
1242 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
1243 INIT_LIST_HEAD(&parent->un.leaf.drop_list);
1244 parent->un.leaf.q = new_q ? new_q : &noop_qdisc;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001245 parent->tokens = parent->buffer;
1246 parent->ctokens = parent->cbuffer;
Patrick McHardy3bebcda2007-03-23 11:29:25 -07001247 parent->t_c = psched_get_time();
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001248 parent->cmode = HTB_CAN_SEND;
1249}
1250
Stephen Hemminger87990462006-08-10 23:35:16 -07001251static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001253 if (!cl->level) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001254 WARN_ON(!cl->un.leaf.q);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001255 qdisc_destroy(cl->un.leaf.q);
1256 }
Patrick McHardyee39e102007-07-02 22:48:13 -07001257 gen_kill_estimator(&cl->bstats, &cl->rate_est);
Patrick McHardyff31ab52008-07-01 19:52:38 -07001258 tcf_destroy_chain(&cl->filter_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001259 kfree(cl);
1260}
1261
Stephen Hemminger87990462006-08-10 23:35:16 -07001262static void htb_destroy(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001263{
1264 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001265 struct hlist_node *n, *next;
1266 struct htb_class *cl;
1267 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001268
Jarek Poplawski12247362009-02-01 01:13:22 -08001269 cancel_work_sync(&q->work);
Patrick McHardyfb983d42007-03-16 01:22:39 -07001270 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001271 /* This line used to be after htb_destroy_class call below
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001272 * and surprisingly it worked in 2.4. But it must precede it
1273 * because filter need its target class alive to be able to call
1274 * unbind_filter on it (without Oops).
1275 */
Patrick McHardyff31ab52008-07-01 19:52:38 -07001276 tcf_destroy_chain(&q->filter_list);
Stephen Hemminger87990462006-08-10 23:35:16 -07001277
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001278 for (i = 0; i < q->clhash.hashsize; i++) {
1279 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001280 tcf_destroy_chain(&cl->filter_list);
1281 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001282 for (i = 0; i < q->clhash.hashsize; i++) {
1283 hlist_for_each_entry_safe(cl, n, next, &q->clhash.hash[i],
1284 common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001285 htb_destroy_class(sch, cl);
1286 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001287 qdisc_class_hash_destroy(&q->clhash);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001288 __skb_queue_purge(&q->direct_queue);
1289}
1290
1291static int htb_delete(struct Qdisc *sch, unsigned long arg)
1292{
1293 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001294 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy256d61b2006-11-29 17:37:05 -08001295 unsigned int qlen;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001296 struct Qdisc *new_q = NULL;
1297 int last_child = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001298
1299 // TODO: why don't allow to delete subtree ? references ? does
1300 // tc subsys quarantee us that in htb_destroy it holds no class
1301 // refs so that we can remove children safely there ?
Patrick McHardy42077592008-07-05 23:22:53 -07001302 if (cl->children || cl->filter_cnt)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001303 return -EBUSY;
Stephen Hemminger87990462006-08-10 23:35:16 -07001304
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001305 if (!cl->level && htb_parent_last_child(cl)) {
Changli Gao3511c912010-10-16 13:04:08 +00001306 new_q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
David S. Millerbb949fb2008-07-08 16:55:56 -07001307 cl->parent->common.classid);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001308 last_child = 1;
1309 }
1310
Linus Torvalds1da177e2005-04-16 15:20:36 -07001311 sch_tree_lock(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001312
Patrick McHardy814a175e2006-11-29 17:34:50 -08001313 if (!cl->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001314 qlen = cl->un.leaf.q->q.qlen;
Patrick McHardy814a175e2006-11-29 17:34:50 -08001315 qdisc_reset(cl->un.leaf.q);
Patrick McHardy256d61b2006-11-29 17:37:05 -08001316 qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
Patrick McHardy814a175e2006-11-29 17:34:50 -08001317 }
1318
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001319 /* delete from hash and active; remainder in destroy_class */
1320 qdisc_class_hash_remove(&q->clhash, &cl->common);
Jarek Poplawski26b284d2008-08-13 15:16:43 -07001321 if (cl->parent)
1322 cl->parent->children--;
Patrick McHardyc38c83c2007-03-27 14:04:24 -07001323
Linus Torvalds1da177e2005-04-16 15:20:36 -07001324 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001325 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001326
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001327 if (cl->cmode != HTB_CAN_SEND)
1328 htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
1329
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001330 if (last_child)
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001331 htb_parent_to_leaf(q, cl, new_q);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001332
Jarek Poplawski7cd0a632009-03-15 20:00:19 -07001333 BUG_ON(--cl->refcnt == 0);
1334 /*
1335 * This shouldn't happen: we "hold" one cops->get() when called
1336 * from tc_ctl_tclass; the destroy method is done from cops->put().
1337 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001338
1339 sch_tree_unlock(sch);
1340 return 0;
1341}
1342
1343static void htb_put(struct Qdisc *sch, unsigned long arg)
1344{
Stephen Hemminger87990462006-08-10 23:35:16 -07001345 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001346
1347 if (--cl->refcnt == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -07001348 htb_destroy_class(sch, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001349}
1350
Stephen Hemminger87990462006-08-10 23:35:16 -07001351static int htb_change_class(struct Qdisc *sch, u32 classid,
Patrick McHardy1e904742008-01-22 22:11:17 -08001352 u32 parentid, struct nlattr **tca,
Stephen Hemminger87990462006-08-10 23:35:16 -07001353 unsigned long *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001354{
1355 int err = -EINVAL;
1356 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001357 struct htb_class *cl = (struct htb_class *)*arg, *parent;
Patrick McHardy1e904742008-01-22 22:11:17 -08001358 struct nlattr *opt = tca[TCA_OPTIONS];
Changli Gaoe18434c2010-09-30 06:17:44 +00001359 struct nlattr *tb[__TCA_HTB_MAX];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001360 struct tc_htb_opt *hopt;
1361
1362 /* extract all subattrs from opt attr */
Patrick McHardycee63722008-01-23 20:33:32 -08001363 if (!opt)
1364 goto failure;
1365
Changli Gaoe18434c2010-09-30 06:17:44 +00001366 err = nla_parse_nested(tb, TCA_HTB_MAX, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -08001367 if (err < 0)
1368 goto failure;
1369
1370 err = -EINVAL;
Patrick McHardy27a34212008-01-23 20:35:39 -08001371 if (tb[TCA_HTB_PARMS] == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001372 goto failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001373
Stephen Hemminger87990462006-08-10 23:35:16 -07001374 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001375
Patrick McHardy1e904742008-01-22 22:11:17 -08001376 hopt = nla_data(tb[TCA_HTB_PARMS]);
Eric Dumazet196d97f2012-11-05 16:40:49 +00001377 if (!hopt->rate.rate || !hopt->ceil.rate)
Stephen Hemminger87990462006-08-10 23:35:16 -07001378 goto failure;
1379
1380 if (!cl) { /* new class */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001381 struct Qdisc *new_q;
Stephen Hemminger3696f622006-08-10 23:36:01 -07001382 int prio;
Patrick McHardyee39e102007-07-02 22:48:13 -07001383 struct {
Patrick McHardy1e904742008-01-22 22:11:17 -08001384 struct nlattr nla;
Patrick McHardyee39e102007-07-02 22:48:13 -07001385 struct gnet_estimator opt;
1386 } est = {
Patrick McHardy1e904742008-01-22 22:11:17 -08001387 .nla = {
1388 .nla_len = nla_attr_size(sizeof(est.opt)),
1389 .nla_type = TCA_RATE,
Patrick McHardyee39e102007-07-02 22:48:13 -07001390 },
1391 .opt = {
1392 /* 4s interval, 16s averaging constant */
1393 .interval = 2,
1394 .ewma_log = 2,
1395 },
1396 };
Stephen Hemminger3696f622006-08-10 23:36:01 -07001397
Linus Torvalds1da177e2005-04-16 15:20:36 -07001398 /* check for valid classid */
Joe Perchesf64f9e72009-11-29 16:55:45 -08001399 if (!classid || TC_H_MAJ(classid ^ sch->handle) ||
1400 htb_find(classid, sch))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001401 goto failure;
1402
1403 /* check maximal depth */
1404 if (parent && parent->parent && parent->parent->level < 2) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001405 pr_err("htb: tree is too deep\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001406 goto failure;
1407 }
1408 err = -ENOBUFS;
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001409 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1410 if (!cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001411 goto failure;
Stephen Hemminger87990462006-08-10 23:35:16 -07001412
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001413 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1414 qdisc_root_sleeping_lock(sch),
1415 tca[TCA_RATE] ? : &est.nla);
1416 if (err) {
1417 kfree(cl);
1418 goto failure;
1419 }
1420
Linus Torvalds1da177e2005-04-16 15:20:36 -07001421 cl->refcnt = 1;
Patrick McHardy42077592008-07-05 23:22:53 -07001422 cl->children = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001423 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
Stephen Hemminger3696f622006-08-10 23:36:01 -07001424 RB_CLEAR_NODE(&cl->pq_node);
1425
1426 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1427 RB_CLEAR_NODE(&cl->node[prio]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001428
1429 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001430 * so that can't be used inside of sch_tree_lock
1431 * -- thanks to Karlis Peisenieks
1432 */
Changli Gao3511c912010-10-16 13:04:08 +00001433 new_q = qdisc_create_dflt(sch->dev_queue,
David S. Millerbb949fb2008-07-08 16:55:56 -07001434 &pfifo_qdisc_ops, classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001435 sch_tree_lock(sch);
1436 if (parent && !parent->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001437 unsigned int qlen = parent->un.leaf.q->q.qlen;
1438
Linus Torvalds1da177e2005-04-16 15:20:36 -07001439 /* turn parent into inner node */
Patrick McHardy256d61b2006-11-29 17:37:05 -08001440 qdisc_reset(parent->un.leaf.q);
1441 qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen);
Stephen Hemminger87990462006-08-10 23:35:16 -07001442 qdisc_destroy(parent->un.leaf.q);
1443 if (parent->prio_activity)
1444 htb_deactivate(q, parent);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001445
1446 /* remove from evt list because of level change */
1447 if (parent->cmode != HTB_CAN_SEND) {
Stephen Hemminger3696f622006-08-10 23:36:01 -07001448 htb_safe_rb_erase(&parent->pq_node, q->wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001449 parent->cmode = HTB_CAN_SEND;
1450 }
1451 parent->level = (parent->parent ? parent->parent->level
Stephen Hemminger87990462006-08-10 23:35:16 -07001452 : TC_HTB_MAXDEPTH) - 1;
1453 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001454 }
1455 /* leaf (we) needs elementary qdisc */
1456 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1457
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001458 cl->common.classid = classid;
Stephen Hemminger87990462006-08-10 23:35:16 -07001459 cl->parent = parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001460
1461 /* set class to be in HTB_CAN_SEND state */
1462 cl->tokens = hopt->buffer;
1463 cl->ctokens = hopt->cbuffer;
Patrick McHardy00c04af2007-03-16 01:23:02 -07001464 cl->mbuffer = 60 * PSCHED_TICKS_PER_SEC; /* 1min */
Patrick McHardy3bebcda2007-03-23 11:29:25 -07001465 cl->t_c = psched_get_time();
Linus Torvalds1da177e2005-04-16 15:20:36 -07001466 cl->cmode = HTB_CAN_SEND;
1467
1468 /* attach to the hash list and parent's family */
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001469 qdisc_class_hash_insert(&q->clhash, &cl->common);
Patrick McHardy42077592008-07-05 23:22:53 -07001470 if (parent)
1471 parent->children++;
Patrick McHardyee39e102007-07-02 22:48:13 -07001472 } else {
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001473 if (tca[TCA_RATE]) {
1474 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1475 qdisc_root_sleeping_lock(sch),
1476 tca[TCA_RATE]);
1477 if (err)
1478 return err;
1479 }
Stephen Hemminger87990462006-08-10 23:35:16 -07001480 sch_tree_lock(sch);
Patrick McHardyee39e102007-07-02 22:48:13 -07001481 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001482
1483 /* it used to be a nasty bug here, we have to check that node
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001484 * is really leaf before changing cl->un.leaf !
1485 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001486 if (!cl->level) {
Eric Dumazet196d97f2012-11-05 16:40:49 +00001487 cl->quantum = hopt->rate.rate / q->rate2quantum;
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001488 if (!hopt->quantum && cl->quantum < 1000) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001489 pr_warning(
Stephen Hemminger87990462006-08-10 23:35:16 -07001490 "HTB: quantum of class %X is small. Consider r2q change.\n",
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001491 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001492 cl->quantum = 1000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001493 }
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001494 if (!hopt->quantum && cl->quantum > 200000) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001495 pr_warning(
Stephen Hemminger87990462006-08-10 23:35:16 -07001496 "HTB: quantum of class %X is big. Consider r2q change.\n",
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001497 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001498 cl->quantum = 200000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001499 }
1500 if (hopt->quantum)
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001501 cl->quantum = hopt->quantum;
1502 if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO)
1503 cl->prio = TC_HTB_NUMPRIO - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001504 }
1505
1506 cl->buffer = hopt->buffer;
1507 cl->cbuffer = hopt->cbuffer;
Vimalkumar56b765b2012-10-31 06:04:11 +00001508
Eric Dumazet196d97f2012-11-05 16:40:49 +00001509 cl->rate.rate_bps = (u64)hopt->rate.rate << 3;
1510 cl->ceil.rate_bps = (u64)hopt->ceil.rate << 3;
Vimalkumar56b765b2012-10-31 06:04:11 +00001511
1512 htb_precompute_ratedata(&cl->rate);
1513 htb_precompute_ratedata(&cl->ceil);
1514
1515 cl->buffer = hopt->buffer << PSCHED_SHIFT;
1516 cl->cbuffer = hopt->buffer << PSCHED_SHIFT;
1517
Linus Torvalds1da177e2005-04-16 15:20:36 -07001518 sch_tree_unlock(sch);
1519
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001520 qdisc_class_hash_grow(sch, &q->clhash);
1521
Linus Torvalds1da177e2005-04-16 15:20:36 -07001522 *arg = (unsigned long)cl;
1523 return 0;
1524
1525failure:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001526 return err;
1527}
1528
1529static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1530{
1531 struct htb_sched *q = qdisc_priv(sch);
1532 struct htb_class *cl = (struct htb_class *)arg;
1533 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001534
Linus Torvalds1da177e2005-04-16 15:20:36 -07001535 return fl;
1536}
1537
1538static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
Stephen Hemminger87990462006-08-10 23:35:16 -07001539 u32 classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001540{
Stephen Hemminger87990462006-08-10 23:35:16 -07001541 struct htb_class *cl = htb_find(classid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001542
Linus Torvalds1da177e2005-04-16 15:20:36 -07001543 /*if (cl && !cl->level) return 0;
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001544 * The line above used to be there to prevent attaching filters to
1545 * leaves. But at least tc_index filter uses this just to get class
1546 * for other reasons so that we have to allow for it.
1547 * ----
1548 * 19.6.2002 As Werner explained it is ok - bind filter is just
1549 * another way to "lock" the class - unlike "get" this lock can
1550 * be broken by class during destroy IIUC.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001551 */
Stephen Hemminger87990462006-08-10 23:35:16 -07001552 if (cl)
1553 cl->filter_cnt++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001554 return (unsigned long)cl;
1555}
1556
1557static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1558{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001559 struct htb_class *cl = (struct htb_class *)arg;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001560
Stephen Hemminger87990462006-08-10 23:35:16 -07001561 if (cl)
1562 cl->filter_cnt--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001563}
1564
1565static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1566{
1567 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001568 struct htb_class *cl;
1569 struct hlist_node *n;
1570 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001571
1572 if (arg->stop)
1573 return;
1574
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001575 for (i = 0; i < q->clhash.hashsize; i++) {
1576 hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001577 if (arg->count < arg->skip) {
1578 arg->count++;
1579 continue;
1580 }
1581 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1582 arg->stop = 1;
1583 return;
1584 }
1585 arg->count++;
1586 }
1587 }
1588}
1589
Eric Dumazet20fea082007-11-14 01:44:41 -08001590static const struct Qdisc_class_ops htb_class_ops = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001591 .graft = htb_graft,
1592 .leaf = htb_leaf,
Patrick McHardy256d61b2006-11-29 17:37:05 -08001593 .qlen_notify = htb_qlen_notify,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001594 .get = htb_get,
1595 .put = htb_put,
1596 .change = htb_change_class,
1597 .delete = htb_delete,
1598 .walk = htb_walk,
1599 .tcf_chain = htb_find_tcf,
1600 .bind_tcf = htb_bind_filter,
1601 .unbind_tcf = htb_unbind_filter,
1602 .dump = htb_dump_class,
1603 .dump_stats = htb_dump_class_stats,
1604};
1605
Eric Dumazet20fea082007-11-14 01:44:41 -08001606static struct Qdisc_ops htb_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001607 .cl_ops = &htb_class_ops,
1608 .id = "htb",
1609 .priv_size = sizeof(struct htb_sched),
1610 .enqueue = htb_enqueue,
1611 .dequeue = htb_dequeue,
Jarek Poplawski77be1552008-10-31 00:47:01 -07001612 .peek = qdisc_peek_dequeued,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001613 .drop = htb_drop,
1614 .init = htb_init,
1615 .reset = htb_reset,
1616 .destroy = htb_destroy,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001617 .dump = htb_dump,
1618 .owner = THIS_MODULE,
1619};
1620
1621static int __init htb_module_init(void)
1622{
Stephen Hemminger87990462006-08-10 23:35:16 -07001623 return register_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001624}
Stephen Hemminger87990462006-08-10 23:35:16 -07001625static void __exit htb_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001626{
Stephen Hemminger87990462006-08-10 23:35:16 -07001627 unregister_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001628}
Stephen Hemminger87990462006-08-10 23:35:16 -07001629
Linus Torvalds1da177e2005-04-16 15:20:36 -07001630module_init(htb_module_init)
1631module_exit(htb_module_exit)
1632MODULE_LICENSE("GPL");