blob: 45e751527dfcc57ed533c4b259bbf5c56e093cfc [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>
Jiri Pirko292f1c72013-02-12 00:12:03 +000041#include <net/sch_generic.h>
Patrick McHardy0ba48052007-07-02 22:49:07 -070042#include <net/pkt_sched.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070043
44/* HTB algorithm.
45 Author: devik@cdi.cz
46 ========================================================================
47 HTB is like TBF with multiple classes. It is also similar to CBQ because
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090048 it allows to assign priority to each class in hierarchy.
Linus Torvalds1da177e2005-04-16 15:20:36 -070049 In fact it is another implementation of Floyd's formal sharing.
50
51 Levels:
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090052 Each class is assigned level. Leaf has ALWAYS level 0 and root
Linus Torvalds1da177e2005-04-16 15:20:36 -070053 classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
54 one less than their parent.
55*/
56
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -070057static int htb_hysteresis __read_mostly = 0; /* whether to use mode hysteresis for speedup */
Stephen Hemminger87990462006-08-10 23:35:16 -070058#define HTB_VER 0x30011 /* major must be matched with number suplied by TC as version */
Linus Torvalds1da177e2005-04-16 15:20:36 -070059
60#if HTB_VER >> 16 != TC_HTB_PROTOVER
61#error "Mismatched sch_htb.c and pkt_sch.h"
62#endif
63
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -070064/* Module parameter and sysfs export */
65module_param (htb_hysteresis, int, 0640);
66MODULE_PARM_DESC(htb_hysteresis, "Hysteresis mode, less CPU load, less accurate");
67
Eric Dumazet64153ce2013-06-06 14:53:16 -070068static int htb_rate_est = 0; /* htb classes have a default rate estimator */
69module_param(htb_rate_est, int, 0640);
70MODULE_PARM_DESC(htb_rate_est, "setup a default rate estimator (4sec 16sec) for htb classes");
71
Linus Torvalds1da177e2005-04-16 15:20:36 -070072/* used internaly to keep status of single class */
73enum htb_cmode {
Stephen Hemminger87990462006-08-10 23:35:16 -070074 HTB_CANT_SEND, /* class can't send and can't borrow */
75 HTB_MAY_BORROW, /* class can't send but may borrow */
76 HTB_CAN_SEND /* class can send */
Linus Torvalds1da177e2005-04-16 15:20:36 -070077};
78
Eric Dumazetc9364632013-06-15 03:30:10 -070079struct htb_prio {
80 union {
81 struct rb_root row;
82 struct rb_root feed;
83 };
84 struct rb_node *ptr;
85 /* When class changes from state 1->2 and disconnects from
86 * parent's feed then we lost ptr value and start from the
87 * first child again. Here we store classid of the
88 * last valid ptr (used when ptr is NULL).
89 */
90 u32 last_ptr_id;
91};
92
Eric Dumazetca4ec902013-06-13 07:58:30 -070093/* interior & leaf nodes; props specific to leaves are marked L:
94 * To reduce false sharing, place mostly read fields at beginning,
95 * and mostly written ones at the end.
96 */
Stephen Hemminger87990462006-08-10 23:35:16 -070097struct htb_class {
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -070098 struct Qdisc_class_common common;
Eric Dumazetca4ec902013-06-13 07:58:30 -070099 struct psched_ratecfg rate;
100 struct psched_ratecfg ceil;
101 s64 buffer, cbuffer;/* token bucket depth/rate */
102 s64 mbuffer; /* max wait time */
stephen hemmingercbd37552013-08-01 22:32:07 -0700103 u32 prio; /* these two are used only by leaves... */
Eric Dumazetca4ec902013-06-13 07:58:30 -0700104 int quantum; /* but stored for parent-to-leaf return */
105
106 struct tcf_proto *filter_list; /* class attached filters */
107 int filter_cnt;
108 int refcnt; /* usage count of this class */
109
110 int level; /* our level (see above) */
111 unsigned int children;
112 struct htb_class *parent; /* parent class */
113
Eric Dumazet45203a32013-06-06 08:43:22 -0700114 struct gnet_stats_rate_est64 rate_est;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700115
Eric Dumazetca4ec902013-06-13 07:58:30 -0700116 /*
117 * Written often fields
118 */
119 struct gnet_stats_basic_packed bstats;
120 struct gnet_stats_queue qstats;
121 struct tc_htb_xstats xstats; /* our special stats */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700122
Eric Dumazetca4ec902013-06-13 07:58:30 -0700123 /* token bucket parameters */
124 s64 tokens, ctokens;/* current number of tokens */
125 s64 t_c; /* checkpoint time */
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800126
Stephen Hemminger87990462006-08-10 23:35:16 -0700127 union {
128 struct htb_class_leaf {
Stephen Hemminger87990462006-08-10 23:35:16 -0700129 struct list_head drop_list;
Eric Dumazetc9364632013-06-15 03:30:10 -0700130 int deficit[TC_HTB_MAXDEPTH];
131 struct Qdisc *q;
Stephen Hemminger87990462006-08-10 23:35:16 -0700132 } leaf;
133 struct htb_class_inner {
Eric Dumazetc9364632013-06-15 03:30:10 -0700134 struct htb_prio clprio[TC_HTB_NUMPRIO];
Stephen Hemminger87990462006-08-10 23:35:16 -0700135 } inner;
136 } un;
Eric Dumazetca4ec902013-06-13 07:58:30 -0700137 s64 pq_key;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700138
Eric Dumazetca4ec902013-06-13 07:58:30 -0700139 int prio_activity; /* for which prios are we active */
140 enum htb_cmode cmode; /* current mode of the class */
141 struct rb_node pq_node; /* node for event queue */
142 struct rb_node node[TC_HTB_NUMPRIO]; /* node for self or feed tree */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143};
144
Eric Dumazetc9364632013-06-15 03:30:10 -0700145struct htb_level {
146 struct rb_root wait_pq;
147 struct htb_prio hprio[TC_HTB_NUMPRIO];
148};
149
Stephen Hemminger87990462006-08-10 23:35:16 -0700150struct htb_sched {
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700151 struct Qdisc_class_hash clhash;
Eric Dumazetc9364632013-06-15 03:30:10 -0700152 int defcls; /* class where unclassified flows go to */
153 int rate2quantum; /* quant = rate / rate2quantum */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700154
Stephen Hemminger87990462006-08-10 23:35:16 -0700155 /* filters for qdisc itself */
Eric Dumazetc9364632013-06-15 03:30:10 -0700156 struct tcf_proto *filter_list;
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800157
158#define HTB_WARN_TOOMANYEVENTS 0x1
Eric Dumazetc9364632013-06-15 03:30:10 -0700159 unsigned int warned; /* only one warning */
160 int direct_qlen;
161 struct work_struct work;
162
163 /* non shaped skbs; let them go directly thru */
164 struct sk_buff_head direct_queue;
165 long direct_pkts;
166
167 struct qdisc_watchdog watchdog;
168
169 s64 now; /* cached dequeue time */
170 struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
171
172 /* time of nearest event per level (row) */
173 s64 near_ev_cache[TC_HTB_MAXDEPTH];
174
175 int row_mask[TC_HTB_MAXDEPTH];
176
177 struct htb_level hlevel[TC_HTB_MAXDEPTH];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700178};
179
Linus Torvalds1da177e2005-04-16 15:20:36 -0700180/* find class in global hash table using given handle */
Stephen Hemminger87990462006-08-10 23:35:16 -0700181static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700182{
183 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700184 struct Qdisc_class_common *clc;
Stephen Hemminger0cef2962006-08-10 23:35:38 -0700185
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700186 clc = qdisc_class_find(&q->clhash, handle);
187 if (clc == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700188 return NULL;
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700189 return container_of(clc, struct htb_class, common);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700190}
191
192/**
193 * htb_classify - classify a packet into class
194 *
195 * It returns NULL if the packet should be dropped or -1 if the packet
196 * should be passed directly thru. In all other cases leaf class is returned.
197 * We allow direct class selection by classid in priority. The we examine
198 * filters in qdisc and in inner nodes (if higher filter points to the inner
199 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900200 * internal fifo (direct). These packets then go directly thru. If we still
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300201 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessful
Linus Torvalds1da177e2005-04-16 15:20:36 -0700202 * then finish and return direct queue.
203 */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000204#define HTB_DIRECT ((struct htb_class *)-1L)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700205
Stephen Hemminger87990462006-08-10 23:35:16 -0700206static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
207 int *qerr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208{
209 struct htb_sched *q = qdisc_priv(sch);
210 struct htb_class *cl;
211 struct tcf_result res;
212 struct tcf_proto *tcf;
213 int result;
214
215 /* allow to select class by setting skb->priority to valid classid;
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000216 * note that nfmark can be used too by attaching filter fw with no
217 * rules in it
218 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700219 if (skb->priority == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700220 return HTB_DIRECT; /* X:0 (direct flow) selected */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000221 cl = htb_find(skb->priority, sch);
222 if (cl && cl->level == 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700223 return cl;
224
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700225 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700226 tcf = q->filter_list;
227 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
228#ifdef CONFIG_NET_CLS_ACT
229 switch (result) {
230 case TC_ACT_QUEUED:
Stephen Hemminger87990462006-08-10 23:35:16 -0700231 case TC_ACT_STOLEN:
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700232 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700233 case TC_ACT_SHOT:
234 return NULL;
235 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700236#endif
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000237 cl = (void *)res.class;
238 if (!cl) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700239 if (res.classid == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700240 return HTB_DIRECT; /* X:0 (direct flow) */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000241 cl = htb_find(res.classid, sch);
242 if (!cl)
Stephen Hemminger87990462006-08-10 23:35:16 -0700243 break; /* filter selected invalid classid */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700244 }
245 if (!cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700246 return cl; /* we hit leaf; return it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700247
248 /* we have got inner class; apply inner filter chain */
249 tcf = cl->filter_list;
250 }
251 /* classification failed; try to use default class */
Stephen Hemminger87990462006-08-10 23:35:16 -0700252 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700253 if (!cl || cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700254 return HTB_DIRECT; /* bad default .. this is safe bet */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700255 return cl;
256}
257
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258/**
259 * htb_add_to_id_tree - adds class to the round robin list
260 *
261 * Routine adds class to the list (actually tree) sorted by classid.
262 * Make sure that class is not already on such list for given prio.
263 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700264static void htb_add_to_id_tree(struct rb_root *root,
265 struct htb_class *cl, int prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700266{
267 struct rb_node **p = &root->rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700268
Linus Torvalds1da177e2005-04-16 15:20:36 -0700269 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700270 struct htb_class *c;
271 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700272 c = rb_entry(parent, struct htb_class, node[prio]);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700273
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700274 if (cl->common.classid > c->common.classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700275 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700276 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700277 p = &parent->rb_left;
278 }
279 rb_link_node(&cl->node[prio], parent, p);
280 rb_insert_color(&cl->node[prio], root);
281}
282
283/**
284 * htb_add_to_wait_tree - adds class to the event queue with delay
285 *
286 * The class is added to priority event queue to indicate that class will
287 * change its mode in cl->pq_key microseconds. Make sure that class is not
288 * already in the queue.
289 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700290static void htb_add_to_wait_tree(struct htb_sched *q,
Vimalkumar56b765b2012-10-31 06:04:11 +0000291 struct htb_class *cl, s64 delay)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700292{
Eric Dumazetc9364632013-06-15 03:30:10 -0700293 struct rb_node **p = &q->hlevel[cl->level].wait_pq.rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700294
Patrick McHardyfb983d42007-03-16 01:22:39 -0700295 cl->pq_key = q->now + delay;
296 if (cl->pq_key == q->now)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700297 cl->pq_key++;
298
299 /* update the nearest event cache */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700300 if (q->near_ev_cache[cl->level] > cl->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301 q->near_ev_cache[cl->level] = cl->pq_key;
Stephen Hemminger87990462006-08-10 23:35:16 -0700302
Linus Torvalds1da177e2005-04-16 15:20:36 -0700303 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700304 struct htb_class *c;
305 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700306 c = rb_entry(parent, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700307 if (cl->pq_key >= c->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700308 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700309 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700310 p = &parent->rb_left;
311 }
312 rb_link_node(&cl->pq_node, parent, p);
Eric Dumazetc9364632013-06-15 03:30:10 -0700313 rb_insert_color(&cl->pq_node, &q->hlevel[cl->level].wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700314}
315
316/**
317 * htb_next_rb_node - finds next node in binary tree
318 *
319 * When we are past last key we return NULL.
320 * Average complexity is 2 steps per call.
321 */
Stephen Hemminger3696f622006-08-10 23:36:01 -0700322static inline void htb_next_rb_node(struct rb_node **n)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700323{
324 *n = rb_next(*n);
325}
326
327/**
328 * htb_add_class_to_row - add class to its row
329 *
330 * The class is added to row at priorities marked in mask.
331 * It does nothing if mask == 0.
332 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700333static inline void htb_add_class_to_row(struct htb_sched *q,
334 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700335{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700336 q->row_mask[cl->level] |= mask;
337 while (mask) {
338 int prio = ffz(~mask);
339 mask &= ~(1 << prio);
Eric Dumazetc9364632013-06-15 03:30:10 -0700340 htb_add_to_id_tree(&q->hlevel[cl->level].hprio[prio].row, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341 }
342}
343
Stephen Hemminger3696f622006-08-10 23:36:01 -0700344/* If this triggers, it is a bug in this code, but it need not be fatal */
345static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
346{
Ismail Donmez81771b32006-10-03 13:49:10 -0700347 if (RB_EMPTY_NODE(rb)) {
Stephen Hemminger3696f622006-08-10 23:36:01 -0700348 WARN_ON(1);
349 } else {
350 rb_erase(rb, root);
351 RB_CLEAR_NODE(rb);
352 }
353}
354
355
Linus Torvalds1da177e2005-04-16 15:20:36 -0700356/**
357 * htb_remove_class_from_row - removes class from its row
358 *
359 * The class is removed from row at priorities marked in mask.
360 * It does nothing if mask == 0.
361 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700362static inline void htb_remove_class_from_row(struct htb_sched *q,
363 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700364{
365 int m = 0;
Eric Dumazetc9364632013-06-15 03:30:10 -0700366 struct htb_level *hlevel = &q->hlevel[cl->level];
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700367
Linus Torvalds1da177e2005-04-16 15:20:36 -0700368 while (mask) {
369 int prio = ffz(~mask);
Eric Dumazetc9364632013-06-15 03:30:10 -0700370 struct htb_prio *hprio = &hlevel->hprio[prio];
Stephen Hemminger3696f622006-08-10 23:36:01 -0700371
Linus Torvalds1da177e2005-04-16 15:20:36 -0700372 mask &= ~(1 << prio);
Eric Dumazetc9364632013-06-15 03:30:10 -0700373 if (hprio->ptr == cl->node + prio)
374 htb_next_rb_node(&hprio->ptr);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700375
Eric Dumazetc9364632013-06-15 03:30:10 -0700376 htb_safe_rb_erase(cl->node + prio, &hprio->row);
377 if (!hprio->row.rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700378 m |= 1 << prio;
379 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700380 q->row_mask[cl->level] &= ~m;
381}
382
383/**
384 * htb_activate_prios - creates active classe's feed chain
385 *
386 * The class is connected to ancestors and/or appropriate rows
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900387 * for priorities it is participating on. cl->cmode must be new
Linus Torvalds1da177e2005-04-16 15:20:36 -0700388 * (activated) mode. It does nothing if cl->prio_activity == 0.
389 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700390static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700391{
392 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700393 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700394
395 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700396 m = mask;
397 while (m) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700398 int prio = ffz(~m);
399 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700400
Eric Dumazetc9364632013-06-15 03:30:10 -0700401 if (p->un.inner.clprio[prio].feed.rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402 /* parent already has its feed in use so that
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000403 * reset bit in mask as parent is already ok
404 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700405 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700406
Eric Dumazetc9364632013-06-15 03:30:10 -0700407 htb_add_to_id_tree(&p->un.inner.clprio[prio].feed, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700408 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700409 p->prio_activity |= mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700410 cl = p;
411 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700412
Linus Torvalds1da177e2005-04-16 15:20:36 -0700413 }
414 if (cl->cmode == HTB_CAN_SEND && mask)
Stephen Hemminger87990462006-08-10 23:35:16 -0700415 htb_add_class_to_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700416}
417
418/**
419 * htb_deactivate_prios - remove class from feed chain
420 *
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900421 * cl->cmode must represent old mode (before deactivation). It does
Linus Torvalds1da177e2005-04-16 15:20:36 -0700422 * nothing if cl->prio_activity == 0. Class is removed from all feed
423 * chains and rows.
424 */
425static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
426{
427 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700428 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700429
430 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700431 m = mask;
432 mask = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700433 while (m) {
434 int prio = ffz(~m);
435 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700436
Eric Dumazetc9364632013-06-15 03:30:10 -0700437 if (p->un.inner.clprio[prio].ptr == cl->node + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438 /* we are removing child which is pointed to from
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000439 * parent feed - forget the pointer but remember
440 * classid
441 */
Eric Dumazetc9364632013-06-15 03:30:10 -0700442 p->un.inner.clprio[prio].last_ptr_id = cl->common.classid;
443 p->un.inner.clprio[prio].ptr = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700444 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700445
Eric Dumazetc9364632013-06-15 03:30:10 -0700446 htb_safe_rb_erase(cl->node + prio,
447 &p->un.inner.clprio[prio].feed);
Stephen Hemminger87990462006-08-10 23:35:16 -0700448
Eric Dumazetc9364632013-06-15 03:30:10 -0700449 if (!p->un.inner.clprio[prio].feed.rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700450 mask |= 1 << prio;
451 }
Stephen Hemminger3bf72952006-08-10 23:31:08 -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 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700458 if (cl->cmode == HTB_CAN_SEND && mask)
459 htb_remove_class_from_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700460}
461
Vimalkumar56b765b2012-10-31 06:04:11 +0000462static inline s64 htb_lowater(const struct htb_class *cl)
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700463{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700464 if (htb_hysteresis)
465 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
466 else
467 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700468}
Vimalkumar56b765b2012-10-31 06:04:11 +0000469static inline s64 htb_hiwater(const struct htb_class *cl)
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700470{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700471 if (htb_hysteresis)
472 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
473 else
474 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700475}
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700476
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700477
Linus Torvalds1da177e2005-04-16 15:20:36 -0700478/**
479 * htb_class_mode - computes and returns current class mode
480 *
481 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
482 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900483 * from now to time when cl will change its state.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700484 * Also it is worth to note that class mode doesn't change simply
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900485 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
Linus Torvalds1da177e2005-04-16 15:20:36 -0700486 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
487 * mode transitions per time unit. The speed gain is about 1/6.
488 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700489static inline enum htb_cmode
Vimalkumar56b765b2012-10-31 06:04:11 +0000490htb_class_mode(struct htb_class *cl, s64 *diff)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700491{
Vimalkumar56b765b2012-10-31 06:04:11 +0000492 s64 toks;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700493
Stephen Hemminger87990462006-08-10 23:35:16 -0700494 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
495 *diff = -toks;
496 return HTB_CANT_SEND;
497 }
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700498
Stephen Hemminger87990462006-08-10 23:35:16 -0700499 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
500 return HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700501
Stephen Hemminger87990462006-08-10 23:35:16 -0700502 *diff = -toks;
503 return HTB_MAY_BORROW;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700504}
505
506/**
507 * htb_change_class_mode - changes classe's mode
508 *
509 * This should be the only way how to change classe's mode under normal
510 * cirsumstances. Routine will update feed lists linkage, change mode
511 * and add class to the wait event queue if appropriate. New mode should
512 * be different from old one and cl->pq_key has to be valid if changing
513 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
514 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700515static void
Vimalkumar56b765b2012-10-31 06:04:11 +0000516htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, s64 *diff)
Stephen Hemminger87990462006-08-10 23:35:16 -0700517{
518 enum htb_cmode new_mode = htb_class_mode(cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700519
520 if (new_mode == cl->cmode)
Stephen Hemminger87990462006-08-10 23:35:16 -0700521 return;
522
523 if (cl->prio_activity) { /* not necessary: speed optimization */
524 if (cl->cmode != HTB_CANT_SEND)
525 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700526 cl->cmode = new_mode;
Stephen Hemminger87990462006-08-10 23:35:16 -0700527 if (new_mode != HTB_CANT_SEND)
528 htb_activate_prios(q, cl);
529 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700530 cl->cmode = new_mode;
531}
532
533/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900534 * htb_activate - inserts leaf cl into appropriate active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700535 *
536 * Routine learns (new) priority of leaf and activates feed chain
537 * for the prio. It can be called on already active leaf safely.
538 * It also adds leaf into droplist.
539 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700540static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700541{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700542 WARN_ON(cl->level || !cl->un.leaf.q || !cl->un.leaf.q->q.qlen);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700543
Linus Torvalds1da177e2005-04-16 15:20:36 -0700544 if (!cl->prio_activity) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800545 cl->prio_activity = 1 << cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700546 htb_activate_prios(q, cl);
547 list_add_tail(&cl->un.leaf.drop_list,
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800548 q->drops + cl->prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549 }
550}
551
552/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900553 * htb_deactivate - remove leaf cl from active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554 *
555 * Make sure that leaf is active. In the other words it can't be called
556 * with non-active leaf. It also removes class from the drop list.
557 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700558static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700560 WARN_ON(!cl->prio_activity);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700561
Stephen Hemminger87990462006-08-10 23:35:16 -0700562 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700563 cl->prio_activity = 0;
564 list_del_init(&cl->un.leaf.drop_list);
565}
566
567static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
568{
Jarek Poplawskif30ab412008-11-13 22:56:30 -0800569 int uninitialized_var(ret);
Stephen Hemminger87990462006-08-10 23:35:16 -0700570 struct htb_sched *q = qdisc_priv(sch);
571 struct htb_class *cl = htb_classify(skb, sch, &ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700572
Stephen Hemminger87990462006-08-10 23:35:16 -0700573 if (cl == HTB_DIRECT) {
574 /* enqueue to helper queue */
575 if (q->direct_queue.qlen < q->direct_qlen) {
576 __skb_queue_tail(&q->direct_queue, skb);
577 q->direct_pkts++;
578 } else {
Eric Dumazet17045752012-05-04 04:37:21 +0000579 return qdisc_drop(skb, sch);
Stephen Hemminger87990462006-08-10 23:35:16 -0700580 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700581#ifdef CONFIG_NET_CLS_ACT
Stephen Hemminger87990462006-08-10 23:35:16 -0700582 } else if (!cl) {
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700583 if (ret & __NET_XMIT_BYPASS)
Stephen Hemminger87990462006-08-10 23:35:16 -0700584 sch->qstats.drops++;
585 kfree_skb(skb);
586 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700587#endif
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700588 } else if ((ret = qdisc_enqueue(skb, cl->un.leaf.q)) != NET_XMIT_SUCCESS) {
589 if (net_xmit_drop_count(ret)) {
590 sch->qstats.drops++;
591 cl->qstats.drops++;
592 }
David S. Miller69747652008-08-17 23:55:36 -0700593 return ret;
Stephen Hemminger87990462006-08-10 23:35:16 -0700594 } else {
Stephen Hemminger87990462006-08-10 23:35:16 -0700595 htb_activate(q, cl);
596 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700597
Stephen Hemminger87990462006-08-10 23:35:16 -0700598 sch->q.qlen++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700599 return NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700600}
601
Vimalkumar56b765b2012-10-31 06:04:11 +0000602static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, s64 diff)
Jarek Poplawski59e42202008-12-03 21:17:27 -0800603{
Vimalkumar56b765b2012-10-31 06:04:11 +0000604 s64 toks = diff + cl->tokens;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800605
606 if (toks > cl->buffer)
607 toks = cl->buffer;
Jiri Pirko292f1c72013-02-12 00:12:03 +0000608 toks -= (s64) psched_l2t_ns(&cl->rate, bytes);
Jarek Poplawski59e42202008-12-03 21:17:27 -0800609 if (toks <= -cl->mbuffer)
610 toks = 1 - cl->mbuffer;
611
612 cl->tokens = toks;
613}
614
Vimalkumar56b765b2012-10-31 06:04:11 +0000615static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, s64 diff)
Jarek Poplawski59e42202008-12-03 21:17:27 -0800616{
Vimalkumar56b765b2012-10-31 06:04:11 +0000617 s64 toks = diff + cl->ctokens;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800618
619 if (toks > cl->cbuffer)
620 toks = cl->cbuffer;
Jiri Pirko292f1c72013-02-12 00:12:03 +0000621 toks -= (s64) psched_l2t_ns(&cl->ceil, bytes);
Jarek Poplawski59e42202008-12-03 21:17:27 -0800622 if (toks <= -cl->mbuffer)
623 toks = 1 - cl->mbuffer;
624
625 cl->ctokens = toks;
626}
627
Linus Torvalds1da177e2005-04-16 15:20:36 -0700628/**
629 * htb_charge_class - charges amount "bytes" to leaf and ancestors
630 *
631 * Routine assumes that packet "bytes" long was dequeued from leaf cl
632 * borrowing from "level". It accounts bytes to ceil leaky bucket for
633 * leaf and all ancestors and to rate bucket for ancestors at levels
634 * "level" and higher. It also handles possible change of mode resulting
635 * from the update. Note that mode can also increase here (MAY_BORROW to
636 * CAN_SEND) because we can use more precise clock that event queue here.
637 * In such case we remove class from event queue first.
638 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700639static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700640 int level, struct sk_buff *skb)
Stephen Hemminger87990462006-08-10 23:35:16 -0700641{
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700642 int bytes = qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700643 enum htb_cmode old_mode;
Vimalkumar56b765b2012-10-31 06:04:11 +0000644 s64 diff;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700645
646 while (cl) {
Vimalkumar56b765b2012-10-31 06:04:11 +0000647 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700648 if (cl->level >= level) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700649 if (cl->level == level)
650 cl->xstats.lends++;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800651 htb_accnt_tokens(cl, bytes, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700652 } else {
653 cl->xstats.borrows++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700654 cl->tokens += diff; /* we moved t_c; update tokens */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700655 }
Jarek Poplawski59e42202008-12-03 21:17:27 -0800656 htb_accnt_ctokens(cl, bytes, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700657 cl->t_c = q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700658
Stephen Hemminger87990462006-08-10 23:35:16 -0700659 old_mode = cl->cmode;
660 diff = 0;
661 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662 if (old_mode != cl->cmode) {
663 if (old_mode != HTB_CAN_SEND)
Eric Dumazetc9364632013-06-15 03:30:10 -0700664 htb_safe_rb_erase(&cl->pq_node, &q->hlevel[cl->level].wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700665 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700666 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700667 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700668
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000669 /* update basic stats except for leaves which are already updated */
670 if (cl->level)
671 bstats_update(&cl->bstats, skb);
672
Linus Torvalds1da177e2005-04-16 15:20:36 -0700673 cl = cl->parent;
674 }
675}
676
677/**
678 * htb_do_events - make mode changes to classes at the level
679 *
Patrick McHardyfb983d42007-03-16 01:22:39 -0700680 * Scans event queue for pending events and applies them. Returns time of
Jarek Poplawski12247362009-02-01 01:13:22 -0800681 * next pending event (0 for no event in pq, q->now for too many events).
Patrick McHardyfb983d42007-03-16 01:22:39 -0700682 * Note: Applied are events whose have cl->pq_key <= q->now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700683 */
Eric Dumazetc9364632013-06-15 03:30:10 -0700684static s64 htb_do_events(struct htb_sched *q, const int level,
Eric Dumazet5343a7f2013-06-04 07:11:48 +0000685 unsigned long start)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700686{
Martin Devera8f3ea332008-03-23 22:00:38 -0700687 /* don't run for longer than 2 jiffies; 2 is used instead of
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000688 * 1 to simplify things when jiffy is going to be incremented
689 * too soon
690 */
Jarek Poplawskia73be042009-01-12 21:54:40 -0800691 unsigned long stop_at = start + 2;
Eric Dumazetc9364632013-06-15 03:30:10 -0700692 struct rb_root *wait_pq = &q->hlevel[level].wait_pq;
693
Martin Devera8f3ea332008-03-23 22:00:38 -0700694 while (time_before(jiffies, stop_at)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700695 struct htb_class *cl;
Vimalkumar56b765b2012-10-31 06:04:11 +0000696 s64 diff;
Eric Dumazetc9364632013-06-15 03:30:10 -0700697 struct rb_node *p = rb_first(wait_pq);
Akinbou Mita30bdbe32006-10-12 01:52:05 -0700698
Stephen Hemminger87990462006-08-10 23:35:16 -0700699 if (!p)
700 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700701
702 cl = rb_entry(p, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700703 if (cl->pq_key > q->now)
704 return cl->pq_key;
705
Eric Dumazetc9364632013-06-15 03:30:10 -0700706 htb_safe_rb_erase(p, wait_pq);
Vimalkumar56b765b2012-10-31 06:04:11 +0000707 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
Stephen Hemminger87990462006-08-10 23:35:16 -0700708 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700709 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700710 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700711 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800712
713 /* too much load - let's continue after a break for scheduling */
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800714 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000715 pr_warning("htb: too many events!\n");
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800716 q->warned |= HTB_WARN_TOOMANYEVENTS;
717 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800718
719 return q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720}
721
722/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000723 * is no such one exists.
724 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700725static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
726 u32 id)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700727{
728 struct rb_node *r = NULL;
729 while (n) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700730 struct htb_class *cl =
731 rb_entry(n, struct htb_class, node[prio]);
Stephen Hemminger87990462006-08-10 23:35:16 -0700732
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700733 if (id > cl->common.classid) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700734 n = n->rb_right;
Jarek Poplawski1b5c0072008-12-09 22:34:40 -0800735 } else if (id < cl->common.classid) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700736 r = n;
737 n = n->rb_left;
Jarek Poplawski1b5c0072008-12-09 22:34:40 -0800738 } else {
739 return n;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700740 }
741 }
742 return r;
743}
744
745/**
746 * htb_lookup_leaf - returns next leaf class in DRR order
747 *
748 * Find leaf where current feed pointers points to.
749 */
Eric Dumazetc9364632013-06-15 03:30:10 -0700750static struct htb_class *htb_lookup_leaf(struct htb_prio *hprio, const int prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700751{
752 int i;
753 struct {
754 struct rb_node *root;
755 struct rb_node **pptr;
756 u32 *pid;
Stephen Hemminger87990462006-08-10 23:35:16 -0700757 } stk[TC_HTB_MAXDEPTH], *sp = stk;
758
Eric Dumazetc9364632013-06-15 03:30:10 -0700759 BUG_ON(!hprio->row.rb_node);
760 sp->root = hprio->row.rb_node;
761 sp->pptr = &hprio->ptr;
762 sp->pid = &hprio->last_ptr_id;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700763
764 for (i = 0; i < 65535; i++) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700765 if (!*sp->pptr && *sp->pid) {
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900766 /* ptr was invalidated but id is valid - try to recover
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000767 * the original or next ptr
768 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700769 *sp->pptr =
770 htb_id_find_next_upper(prio, sp->root, *sp->pid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700771 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700772 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000773 * can become out of date quickly
774 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700775 if (!*sp->pptr) { /* we are at right end; rewind & go up */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700776 *sp->pptr = sp->root;
Stephen Hemminger87990462006-08-10 23:35:16 -0700777 while ((*sp->pptr)->rb_left)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700778 *sp->pptr = (*sp->pptr)->rb_left;
779 if (sp > stk) {
780 sp--;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800781 if (!*sp->pptr) {
782 WARN_ON(1);
Stephen Hemminger87990462006-08-10 23:35:16 -0700783 return NULL;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800784 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700785 htb_next_rb_node(sp->pptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700786 }
787 } else {
788 struct htb_class *cl;
Eric Dumazetc9364632013-06-15 03:30:10 -0700789 struct htb_prio *clp;
790
Stephen Hemminger87990462006-08-10 23:35:16 -0700791 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
792 if (!cl->level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700793 return cl;
Eric Dumazetc9364632013-06-15 03:30:10 -0700794 clp = &cl->un.inner.clprio[prio];
795 (++sp)->root = clp->feed.rb_node;
796 sp->pptr = &clp->ptr;
797 sp->pid = &clp->last_ptr_id;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700798 }
799 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700800 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700801 return NULL;
802}
803
804/* dequeues packet at given priority and level; call only if
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000805 * you are sure that there is active class at prio/level
806 */
Eric Dumazetc9364632013-06-15 03:30:10 -0700807static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, const int prio,
808 const int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700809{
810 struct sk_buff *skb = NULL;
Stephen Hemminger87990462006-08-10 23:35:16 -0700811 struct htb_class *cl, *start;
Eric Dumazetc9364632013-06-15 03:30:10 -0700812 struct htb_level *hlevel = &q->hlevel[level];
813 struct htb_prio *hprio = &hlevel->hprio[prio];
814
Linus Torvalds1da177e2005-04-16 15:20:36 -0700815 /* look initial class up in the row */
Eric Dumazetc9364632013-06-15 03:30:10 -0700816 start = cl = htb_lookup_leaf(hprio, prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700817
Linus Torvalds1da177e2005-04-16 15:20:36 -0700818 do {
819next:
Jarek Poplawski512bb432008-12-09 22:35:02 -0800820 if (unlikely(!cl))
Stephen Hemminger87990462006-08-10 23:35:16 -0700821 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700822
823 /* class can be empty - it is unlikely but can be true if leaf
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000824 * qdisc drops packets in enqueue routine or if someone used
825 * graft operation on the leaf since last dequeue;
826 * simply deactivate and skip such class
827 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700828 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
829 struct htb_class *next;
Stephen Hemminger87990462006-08-10 23:35:16 -0700830 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700831
832 /* row/level might become empty */
833 if ((q->row_mask[level] & (1 << prio)) == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -0700834 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700835
Eric Dumazetc9364632013-06-15 03:30:10 -0700836 next = htb_lookup_leaf(hprio, prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700837
838 if (cl == start) /* fix start if we just deleted it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700839 start = next;
840 cl = next;
841 goto next;
842 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700843
844 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
845 if (likely(skb != NULL))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700846 break;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800847
Jarek Poplawskib00355d2009-02-01 01:12:42 -0800848 qdisc_warn_nonwc("htb", cl->un.leaf.q);
Eric Dumazetc9364632013-06-15 03:30:10 -0700849 htb_next_rb_node(level ? &cl->parent->un.inner.clprio[prio].ptr:
850 &q->hlevel[0].hprio[prio].ptr);
851 cl = htb_lookup_leaf(hprio, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700852
853 } while (cl != start);
854
855 if (likely(skb != NULL)) {
Eric Dumazet196d97f2012-11-05 16:40:49 +0000856 bstats_update(&cl->bstats, skb);
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700857 cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb);
858 if (cl->un.leaf.deficit[level] < 0) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800859 cl->un.leaf.deficit[level] += cl->quantum;
Eric Dumazetc9364632013-06-15 03:30:10 -0700860 htb_next_rb_node(level ? &cl->parent->un.inner.clprio[prio].ptr :
861 &q->hlevel[0].hprio[prio].ptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700862 }
863 /* this used to be after charge_class but this constelation
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000864 * gives us slightly better performance
865 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700866 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700867 htb_deactivate(q, cl);
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700868 htb_charge_class(q, cl, level, skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700869 }
870 return skb;
871}
872
Linus Torvalds1da177e2005-04-16 15:20:36 -0700873static struct sk_buff *htb_dequeue(struct Qdisc *sch)
874{
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800875 struct sk_buff *skb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700876 struct htb_sched *q = qdisc_priv(sch);
877 int level;
Eric Dumazet5343a7f2013-06-04 07:11:48 +0000878 s64 next_event;
Jarek Poplawskia73be042009-01-12 21:54:40 -0800879 unsigned long start_at;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700880
881 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
Stephen Hemminger87990462006-08-10 23:35:16 -0700882 skb = __skb_dequeue(&q->direct_queue);
883 if (skb != NULL) {
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800884ok:
885 qdisc_bstats_update(sch, skb);
Eric Dumazetfd245a42011-01-20 05:27:16 +0000886 qdisc_unthrottled(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700887 sch->q.qlen--;
888 return skb;
889 }
890
Stephen Hemminger87990462006-08-10 23:35:16 -0700891 if (!sch->q.qlen)
892 goto fin;
Vimalkumar56b765b2012-10-31 06:04:11 +0000893 q->now = ktime_to_ns(ktime_get());
Jarek Poplawskia73be042009-01-12 21:54:40 -0800894 start_at = jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700895
Stefan Haskod2fe85d2012-12-21 15:04:59 +0000896 next_event = q->now + 5LLU * NSEC_PER_SEC;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800897
Linus Torvalds1da177e2005-04-16 15:20:36 -0700898 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
899 /* common case optimization - skip event handler quickly */
900 int m;
Eric Dumazetc9364632013-06-15 03:30:10 -0700901 s64 event = q->near_ev_cache[level];
Stephen Hemminger87990462006-08-10 23:35:16 -0700902
Eric Dumazetc9364632013-06-15 03:30:10 -0700903 if (q->now >= event) {
Jarek Poplawskia73be042009-01-12 21:54:40 -0800904 event = htb_do_events(q, level, start_at);
Patrick McHardy2e4b3b02007-05-23 23:39:54 -0700905 if (!event)
Vimalkumar56b765b2012-10-31 06:04:11 +0000906 event = q->now + NSEC_PER_SEC;
Patrick McHardy2e4b3b02007-05-23 23:39:54 -0700907 q->near_ev_cache[level] = event;
Eric Dumazetc9364632013-06-15 03:30:10 -0700908 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700909
Jarek Poplawskic0851342009-01-12 21:54:16 -0800910 if (next_event > event)
Patrick McHardyfb983d42007-03-16 01:22:39 -0700911 next_event = event;
912
Linus Torvalds1da177e2005-04-16 15:20:36 -0700913 m = ~q->row_mask[level];
914 while (m != (int)(-1)) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700915 int prio = ffz(m);
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000916
Linus Torvalds1da177e2005-04-16 15:20:36 -0700917 m |= 1 << prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700918 skb = htb_dequeue_tree(q, prio, level);
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800919 if (likely(skb != NULL))
920 goto ok;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700921 }
922 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700923 sch->qstats.overlimits++;
Vimalkumar56b765b2012-10-31 06:04:11 +0000924 if (likely(next_event > q->now)) {
925 if (!test_bit(__QDISC_STATE_DEACTIVATED,
926 &qdisc_root_sleeping(q->watchdog.qdisc)->state)) {
927 ktime_t time = ns_to_ktime(next_event);
928 qdisc_throttled(q->watchdog.qdisc);
929 hrtimer_start(&q->watchdog.timer, time,
930 HRTIMER_MODE_ABS);
931 }
932 } else {
Jarek Poplawski12247362009-02-01 01:13:22 -0800933 schedule_work(&q->work);
Vimalkumar56b765b2012-10-31 06:04:11 +0000934 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700935fin:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700936 return skb;
937}
938
939/* try to drop from each class (by prio) until one succeed */
Stephen Hemminger87990462006-08-10 23:35:16 -0700940static unsigned int htb_drop(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700941{
942 struct htb_sched *q = qdisc_priv(sch);
943 int prio;
944
945 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
946 struct list_head *p;
Stephen Hemminger87990462006-08-10 23:35:16 -0700947 list_for_each(p, q->drops + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700948 struct htb_class *cl = list_entry(p, struct htb_class,
949 un.leaf.drop_list);
950 unsigned int len;
Stephen Hemminger87990462006-08-10 23:35:16 -0700951 if (cl->un.leaf.q->ops->drop &&
952 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700953 sch->q.qlen--;
954 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700955 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700956 return len;
957 }
958 }
959 }
960 return 0;
961}
962
963/* reset all classes */
964/* always caled under BH & queue lock */
Stephen Hemminger87990462006-08-10 23:35:16 -0700965static void htb_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700966{
967 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700968 struct htb_class *cl;
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700969 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700970
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700971 for (i = 0; i < q->clhash.hashsize; i++) {
Sasha Levinb67bfe02013-02-27 17:06:00 -0800972 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700973 if (cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700974 memset(&cl->un.inner, 0, sizeof(cl->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700975 else {
Stephen Hemminger87990462006-08-10 23:35:16 -0700976 if (cl->un.leaf.q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700977 qdisc_reset(cl->un.leaf.q);
978 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
979 }
980 cl->prio_activity = 0;
981 cl->cmode = HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700982
983 }
984 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700985 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700986 __skb_queue_purge(&q->direct_queue);
987 sch->q.qlen = 0;
Eric Dumazetc9364632013-06-15 03:30:10 -0700988 memset(q->hlevel, 0, sizeof(q->hlevel));
Stephen Hemminger87990462006-08-10 23:35:16 -0700989 memset(q->row_mask, 0, sizeof(q->row_mask));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700990 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -0700991 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700992}
993
Patrick McHardy27a34212008-01-23 20:35:39 -0800994static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
995 [TCA_HTB_PARMS] = { .len = sizeof(struct tc_htb_opt) },
996 [TCA_HTB_INIT] = { .len = sizeof(struct tc_htb_glob) },
997 [TCA_HTB_CTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
998 [TCA_HTB_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
Eric Dumazet6906f4e2013-03-06 06:49:21 +0000999 [TCA_HTB_DIRECT_QLEN] = { .type = NLA_U32 },
Patrick McHardy27a34212008-01-23 20:35:39 -08001000};
1001
Jarek Poplawski12247362009-02-01 01:13:22 -08001002static void htb_work_func(struct work_struct *work)
1003{
1004 struct htb_sched *q = container_of(work, struct htb_sched, work);
1005 struct Qdisc *sch = q->watchdog.qdisc;
1006
1007 __netif_schedule(qdisc_root(sch));
1008}
1009
Patrick McHardy1e904742008-01-22 22:11:17 -08001010static int htb_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001011{
1012 struct htb_sched *q = qdisc_priv(sch);
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001013 struct nlattr *tb[TCA_HTB_MAX + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001014 struct tc_htb_glob *gopt;
Patrick McHardycee63722008-01-23 20:33:32 -08001015 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001016 int i;
Patrick McHardycee63722008-01-23 20:33:32 -08001017
1018 if (!opt)
1019 return -EINVAL;
1020
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001021 err = nla_parse_nested(tb, TCA_HTB_MAX, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -08001022 if (err < 0)
1023 return err;
1024
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001025 if (!tb[TCA_HTB_INIT])
Linus Torvalds1da177e2005-04-16 15:20:36 -07001026 return -EINVAL;
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001027
Patrick McHardy1e904742008-01-22 22:11:17 -08001028 gopt = nla_data(tb[TCA_HTB_INIT]);
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001029 if (gopt->version != HTB_VER >> 16)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001030 return -EINVAL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001031
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001032 err = qdisc_class_hash_init(&q->clhash);
1033 if (err < 0)
1034 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001035 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -07001036 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001037
Patrick McHardyfb983d42007-03-16 01:22:39 -07001038 qdisc_watchdog_init(&q->watchdog, sch);
Jarek Poplawski12247362009-02-01 01:13:22 -08001039 INIT_WORK(&q->work, htb_work_func);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001040 skb_queue_head_init(&q->direct_queue);
1041
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001042 if (tb[TCA_HTB_DIRECT_QLEN])
1043 q->direct_qlen = nla_get_u32(tb[TCA_HTB_DIRECT_QLEN]);
1044 else {
1045 q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
1046 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
1047 q->direct_qlen = 2;
1048 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001049 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1050 q->rate2quantum = 1;
1051 q->defcls = gopt->defcls;
1052
1053 return 0;
1054}
1055
1056static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1057{
Jarek Poplawski102396a2008-08-29 14:21:52 -07001058 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001059 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001060 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001061 struct tc_htb_glob gopt;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001062
David S. Miller7698b4f2008-07-16 01:42:40 -07001063 spin_lock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001064
1065 gopt.direct_pkts = q->direct_pkts;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001066 gopt.version = HTB_VER;
1067 gopt.rate2quantum = q->rate2quantum;
1068 gopt.defcls = q->defcls;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001069 gopt.debug = 0;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001070
1071 nest = nla_nest_start(skb, TCA_OPTIONS);
1072 if (nest == NULL)
1073 goto nla_put_failure;
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001074 if (nla_put(skb, TCA_HTB_INIT, sizeof(gopt), &gopt) ||
1075 nla_put_u32(skb, TCA_HTB_DIRECT_QLEN, q->direct_qlen))
David S. Miller1b34ec42012-03-29 05:11:39 -04001076 goto nla_put_failure;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001077 nla_nest_end(skb, nest);
1078
David S. Miller7698b4f2008-07-16 01:42:40 -07001079 spin_unlock_bh(root_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001080 return skb->len;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001081
Patrick McHardy1e904742008-01-22 22:11:17 -08001082nla_put_failure:
David S. Miller7698b4f2008-07-16 01:42:40 -07001083 spin_unlock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001084 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001085 return -1;
1086}
1087
1088static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
Stephen Hemminger87990462006-08-10 23:35:16 -07001089 struct sk_buff *skb, struct tcmsg *tcm)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001090{
Stephen Hemminger87990462006-08-10 23:35:16 -07001091 struct htb_class *cl = (struct htb_class *)arg;
Jarek Poplawski102396a2008-08-29 14:21:52 -07001092 spinlock_t *root_lock = qdisc_root_sleeping_lock(sch);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001093 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001094 struct tc_htb_opt opt;
1095
David S. Miller7698b4f2008-07-16 01:42:40 -07001096 spin_lock_bh(root_lock);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001097 tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
1098 tcm->tcm_handle = cl->common.classid;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001099 if (!cl->level && cl->un.leaf.q)
1100 tcm->tcm_info = cl->un.leaf.q->handle;
1101
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001102 nest = nla_nest_start(skb, TCA_OPTIONS);
1103 if (nest == NULL)
1104 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001105
Stephen Hemminger87990462006-08-10 23:35:16 -07001106 memset(&opt, 0, sizeof(opt));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001107
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001108 psched_ratecfg_getrate(&opt.rate, &cl->rate);
Jiri Pirko9c10f412013-02-12 00:12:00 +00001109 opt.buffer = PSCHED_NS2TICKS(cl->buffer);
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001110 psched_ratecfg_getrate(&opt.ceil, &cl->ceil);
Jiri Pirko9c10f412013-02-12 00:12:00 +00001111 opt.cbuffer = PSCHED_NS2TICKS(cl->cbuffer);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001112 opt.quantum = cl->quantum;
1113 opt.prio = cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -07001114 opt.level = cl->level;
David S. Miller1b34ec42012-03-29 05:11:39 -04001115 if (nla_put(skb, TCA_HTB_PARMS, sizeof(opt), &opt))
1116 goto nla_put_failure;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001117
1118 nla_nest_end(skb, nest);
David S. Miller7698b4f2008-07-16 01:42:40 -07001119 spin_unlock_bh(root_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001120 return skb->len;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001121
Patrick McHardy1e904742008-01-22 22:11:17 -08001122nla_put_failure:
David S. Miller7698b4f2008-07-16 01:42:40 -07001123 spin_unlock_bh(root_lock);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001124 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001125 return -1;
1126}
1127
1128static int
Stephen Hemminger87990462006-08-10 23:35:16 -07001129htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001130{
Stephen Hemminger87990462006-08-10 23:35:16 -07001131 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001132
Linus Torvalds1da177e2005-04-16 15:20:36 -07001133 if (!cl->level && cl->un.leaf.q)
1134 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
Eric Dumazet5343a7f2013-06-04 07:11:48 +00001135 cl->xstats.tokens = PSCHED_NS2TICKS(cl->tokens);
1136 cl->xstats.ctokens = PSCHED_NS2TICKS(cl->ctokens);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001137
1138 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
Eric Dumazetd250a5f2009-10-02 10:32:18 +00001139 gnet_stats_copy_rate_est(d, NULL, &cl->rate_est) < 0 ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001140 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1141 return -1;
1142
1143 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1144}
1145
1146static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
Stephen Hemminger87990462006-08-10 23:35:16 -07001147 struct Qdisc **old)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001148{
Stephen Hemminger87990462006-08-10 23:35:16 -07001149 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001150
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001151 if (cl->level)
1152 return -EINVAL;
1153 if (new == NULL &&
Changli Gao3511c912010-10-16 13:04:08 +00001154 (new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001155 cl->common.classid)) == NULL)
1156 return -ENOBUFS;
1157
1158 sch_tree_lock(sch);
1159 *old = cl->un.leaf.q;
1160 cl->un.leaf.q = new;
1161 if (*old != NULL) {
1162 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1163 qdisc_reset(*old);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001164 }
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001165 sch_tree_unlock(sch);
1166 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001167}
1168
Stephen Hemminger87990462006-08-10 23:35:16 -07001169static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001170{
Stephen Hemminger87990462006-08-10 23:35:16 -07001171 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001172 return !cl->level ? cl->un.leaf.q : NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001173}
1174
Patrick McHardy256d61b2006-11-29 17:37:05 -08001175static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
1176{
1177 struct htb_class *cl = (struct htb_class *)arg;
1178
1179 if (cl->un.leaf.q->q.qlen == 0)
1180 htb_deactivate(qdisc_priv(sch), cl);
1181}
1182
Linus Torvalds1da177e2005-04-16 15:20:36 -07001183static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1184{
Stephen Hemminger87990462006-08-10 23:35:16 -07001185 struct htb_class *cl = htb_find(classid, sch);
1186 if (cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001187 cl->refcnt++;
1188 return (unsigned long)cl;
1189}
1190
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001191static inline int htb_parent_last_child(struct htb_class *cl)
1192{
1193 if (!cl->parent)
1194 /* the root class */
1195 return 0;
Patrick McHardy42077592008-07-05 23:22:53 -07001196 if (cl->parent->children > 1)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001197 /* not the last child */
1198 return 0;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001199 return 1;
1200}
1201
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001202static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl,
1203 struct Qdisc *new_q)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001204{
1205 struct htb_class *parent = cl->parent;
1206
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001207 WARN_ON(cl->level || !cl->un.leaf.q || cl->prio_activity);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001208
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001209 if (parent->cmode != HTB_CAN_SEND)
Eric Dumazetc9364632013-06-15 03:30:10 -07001210 htb_safe_rb_erase(&parent->pq_node,
1211 &q->hlevel[parent->level].wait_pq);
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001212
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001213 parent->level = 0;
1214 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
1215 INIT_LIST_HEAD(&parent->un.leaf.drop_list);
1216 parent->un.leaf.q = new_q ? new_q : &noop_qdisc;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001217 parent->tokens = parent->buffer;
1218 parent->ctokens = parent->cbuffer;
Eric Dumazet5343a7f2013-06-04 07:11:48 +00001219 parent->t_c = ktime_to_ns(ktime_get());
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001220 parent->cmode = HTB_CAN_SEND;
1221}
1222
Stephen Hemminger87990462006-08-10 23:35:16 -07001223static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001224{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001225 if (!cl->level) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001226 WARN_ON(!cl->un.leaf.q);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001227 qdisc_destroy(cl->un.leaf.q);
1228 }
Patrick McHardyee39e102007-07-02 22:48:13 -07001229 gen_kill_estimator(&cl->bstats, &cl->rate_est);
Patrick McHardyff31ab52008-07-01 19:52:38 -07001230 tcf_destroy_chain(&cl->filter_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001231 kfree(cl);
1232}
1233
Stephen Hemminger87990462006-08-10 23:35:16 -07001234static void htb_destroy(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001235{
1236 struct htb_sched *q = qdisc_priv(sch);
Sasha Levinb67bfe02013-02-27 17:06:00 -08001237 struct hlist_node *next;
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001238 struct htb_class *cl;
1239 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001240
Jarek Poplawski12247362009-02-01 01:13:22 -08001241 cancel_work_sync(&q->work);
Patrick McHardyfb983d42007-03-16 01:22:39 -07001242 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001243 /* This line used to be after htb_destroy_class call below
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001244 * and surprisingly it worked in 2.4. But it must precede it
1245 * because filter need its target class alive to be able to call
1246 * unbind_filter on it (without Oops).
1247 */
Patrick McHardyff31ab52008-07-01 19:52:38 -07001248 tcf_destroy_chain(&q->filter_list);
Stephen Hemminger87990462006-08-10 23:35:16 -07001249
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001250 for (i = 0; i < q->clhash.hashsize; i++) {
Sasha Levinb67bfe02013-02-27 17:06:00 -08001251 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001252 tcf_destroy_chain(&cl->filter_list);
1253 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001254 for (i = 0; i < q->clhash.hashsize; i++) {
Sasha Levinb67bfe02013-02-27 17:06:00 -08001255 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001256 common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001257 htb_destroy_class(sch, cl);
1258 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001259 qdisc_class_hash_destroy(&q->clhash);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001260 __skb_queue_purge(&q->direct_queue);
1261}
1262
1263static int htb_delete(struct Qdisc *sch, unsigned long arg)
1264{
1265 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001266 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy256d61b2006-11-29 17:37:05 -08001267 unsigned int qlen;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001268 struct Qdisc *new_q = NULL;
1269 int last_child = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001270
1271 // TODO: why don't allow to delete subtree ? references ? does
1272 // tc subsys quarantee us that in htb_destroy it holds no class
1273 // refs so that we can remove children safely there ?
Patrick McHardy42077592008-07-05 23:22:53 -07001274 if (cl->children || cl->filter_cnt)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001275 return -EBUSY;
Stephen Hemminger87990462006-08-10 23:35:16 -07001276
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001277 if (!cl->level && htb_parent_last_child(cl)) {
Changli Gao3511c912010-10-16 13:04:08 +00001278 new_q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
David S. Millerbb949fb2008-07-08 16:55:56 -07001279 cl->parent->common.classid);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001280 last_child = 1;
1281 }
1282
Linus Torvalds1da177e2005-04-16 15:20:36 -07001283 sch_tree_lock(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001284
Patrick McHardy814a175e2006-11-29 17:34:50 -08001285 if (!cl->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001286 qlen = cl->un.leaf.q->q.qlen;
Patrick McHardy814a175e2006-11-29 17:34:50 -08001287 qdisc_reset(cl->un.leaf.q);
Patrick McHardy256d61b2006-11-29 17:37:05 -08001288 qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
Patrick McHardy814a175e2006-11-29 17:34:50 -08001289 }
1290
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001291 /* delete from hash and active; remainder in destroy_class */
1292 qdisc_class_hash_remove(&q->clhash, &cl->common);
Jarek Poplawski26b284d2008-08-13 15:16:43 -07001293 if (cl->parent)
1294 cl->parent->children--;
Patrick McHardyc38c83c2007-03-27 14:04:24 -07001295
Linus Torvalds1da177e2005-04-16 15:20:36 -07001296 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001297 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001298
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001299 if (cl->cmode != HTB_CAN_SEND)
Eric Dumazetc9364632013-06-15 03:30:10 -07001300 htb_safe_rb_erase(&cl->pq_node,
1301 &q->hlevel[cl->level].wait_pq);
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001302
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001303 if (last_child)
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001304 htb_parent_to_leaf(q, cl, new_q);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001305
Jarek Poplawski7cd0a632009-03-15 20:00:19 -07001306 BUG_ON(--cl->refcnt == 0);
1307 /*
1308 * This shouldn't happen: we "hold" one cops->get() when called
1309 * from tc_ctl_tclass; the destroy method is done from cops->put().
1310 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001311
1312 sch_tree_unlock(sch);
1313 return 0;
1314}
1315
1316static void htb_put(struct Qdisc *sch, unsigned long arg)
1317{
Stephen Hemminger87990462006-08-10 23:35:16 -07001318 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001319
1320 if (--cl->refcnt == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -07001321 htb_destroy_class(sch, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001322}
1323
Stephen Hemminger87990462006-08-10 23:35:16 -07001324static int htb_change_class(struct Qdisc *sch, u32 classid,
Patrick McHardy1e904742008-01-22 22:11:17 -08001325 u32 parentid, struct nlattr **tca,
Stephen Hemminger87990462006-08-10 23:35:16 -07001326 unsigned long *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001327{
1328 int err = -EINVAL;
1329 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001330 struct htb_class *cl = (struct htb_class *)*arg, *parent;
Patrick McHardy1e904742008-01-22 22:11:17 -08001331 struct nlattr *opt = tca[TCA_OPTIONS];
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001332 struct nlattr *tb[TCA_HTB_MAX + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001333 struct tc_htb_opt *hopt;
1334
1335 /* extract all subattrs from opt attr */
Patrick McHardycee63722008-01-23 20:33:32 -08001336 if (!opt)
1337 goto failure;
1338
Changli Gaoe18434c2010-09-30 06:17:44 +00001339 err = nla_parse_nested(tb, TCA_HTB_MAX, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -08001340 if (err < 0)
1341 goto failure;
1342
1343 err = -EINVAL;
Patrick McHardy27a34212008-01-23 20:35:39 -08001344 if (tb[TCA_HTB_PARMS] == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001345 goto failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001346
Stephen Hemminger87990462006-08-10 23:35:16 -07001347 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001348
Patrick McHardy1e904742008-01-22 22:11:17 -08001349 hopt = nla_data(tb[TCA_HTB_PARMS]);
Eric Dumazet196d97f2012-11-05 16:40:49 +00001350 if (!hopt->rate.rate || !hopt->ceil.rate)
Stephen Hemminger87990462006-08-10 23:35:16 -07001351 goto failure;
1352
1353 if (!cl) { /* new class */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001354 struct Qdisc *new_q;
Stephen Hemminger3696f622006-08-10 23:36:01 -07001355 int prio;
Patrick McHardyee39e102007-07-02 22:48:13 -07001356 struct {
Patrick McHardy1e904742008-01-22 22:11:17 -08001357 struct nlattr nla;
Patrick McHardyee39e102007-07-02 22:48:13 -07001358 struct gnet_estimator opt;
1359 } est = {
Patrick McHardy1e904742008-01-22 22:11:17 -08001360 .nla = {
1361 .nla_len = nla_attr_size(sizeof(est.opt)),
1362 .nla_type = TCA_RATE,
Patrick McHardyee39e102007-07-02 22:48:13 -07001363 },
1364 .opt = {
1365 /* 4s interval, 16s averaging constant */
1366 .interval = 2,
1367 .ewma_log = 2,
1368 },
1369 };
Stephen Hemminger3696f622006-08-10 23:36:01 -07001370
Linus Torvalds1da177e2005-04-16 15:20:36 -07001371 /* check for valid classid */
Joe Perchesf64f9e72009-11-29 16:55:45 -08001372 if (!classid || TC_H_MAJ(classid ^ sch->handle) ||
1373 htb_find(classid, sch))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001374 goto failure;
1375
1376 /* check maximal depth */
1377 if (parent && parent->parent && parent->parent->level < 2) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001378 pr_err("htb: tree is too deep\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001379 goto failure;
1380 }
1381 err = -ENOBUFS;
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001382 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1383 if (!cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001384 goto failure;
Stephen Hemminger87990462006-08-10 23:35:16 -07001385
Eric Dumazet64153ce2013-06-06 14:53:16 -07001386 if (htb_rate_est || tca[TCA_RATE]) {
1387 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1388 qdisc_root_sleeping_lock(sch),
1389 tca[TCA_RATE] ? : &est.nla);
1390 if (err) {
1391 kfree(cl);
1392 goto failure;
1393 }
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001394 }
1395
Linus Torvalds1da177e2005-04-16 15:20:36 -07001396 cl->refcnt = 1;
Patrick McHardy42077592008-07-05 23:22:53 -07001397 cl->children = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001398 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
Stephen Hemminger3696f622006-08-10 23:36:01 -07001399 RB_CLEAR_NODE(&cl->pq_node);
1400
1401 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1402 RB_CLEAR_NODE(&cl->node[prio]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001403
1404 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001405 * so that can't be used inside of sch_tree_lock
1406 * -- thanks to Karlis Peisenieks
1407 */
Changli Gao3511c912010-10-16 13:04:08 +00001408 new_q = qdisc_create_dflt(sch->dev_queue,
David S. Millerbb949fb2008-07-08 16:55:56 -07001409 &pfifo_qdisc_ops, classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001410 sch_tree_lock(sch);
1411 if (parent && !parent->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001412 unsigned int qlen = parent->un.leaf.q->q.qlen;
1413
Linus Torvalds1da177e2005-04-16 15:20:36 -07001414 /* turn parent into inner node */
Patrick McHardy256d61b2006-11-29 17:37:05 -08001415 qdisc_reset(parent->un.leaf.q);
1416 qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen);
Stephen Hemminger87990462006-08-10 23:35:16 -07001417 qdisc_destroy(parent->un.leaf.q);
1418 if (parent->prio_activity)
1419 htb_deactivate(q, parent);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001420
1421 /* remove from evt list because of level change */
1422 if (parent->cmode != HTB_CAN_SEND) {
Eric Dumazetc9364632013-06-15 03:30:10 -07001423 htb_safe_rb_erase(&parent->pq_node, &q->hlevel[0].wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001424 parent->cmode = HTB_CAN_SEND;
1425 }
1426 parent->level = (parent->parent ? parent->parent->level
Stephen Hemminger87990462006-08-10 23:35:16 -07001427 : TC_HTB_MAXDEPTH) - 1;
1428 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001429 }
1430 /* leaf (we) needs elementary qdisc */
1431 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1432
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001433 cl->common.classid = classid;
Stephen Hemminger87990462006-08-10 23:35:16 -07001434 cl->parent = parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001435
1436 /* set class to be in HTB_CAN_SEND state */
Jiri Pirkob9a7afd2013-02-12 00:12:02 +00001437 cl->tokens = PSCHED_TICKS2NS(hopt->buffer);
1438 cl->ctokens = PSCHED_TICKS2NS(hopt->cbuffer);
Eric Dumazet5343a7f2013-06-04 07:11:48 +00001439 cl->mbuffer = 60ULL * NSEC_PER_SEC; /* 1min */
1440 cl->t_c = ktime_to_ns(ktime_get());
Linus Torvalds1da177e2005-04-16 15:20:36 -07001441 cl->cmode = HTB_CAN_SEND;
1442
1443 /* attach to the hash list and parent's family */
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001444 qdisc_class_hash_insert(&q->clhash, &cl->common);
Patrick McHardy42077592008-07-05 23:22:53 -07001445 if (parent)
1446 parent->children++;
Patrick McHardyee39e102007-07-02 22:48:13 -07001447 } else {
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001448 if (tca[TCA_RATE]) {
1449 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1450 qdisc_root_sleeping_lock(sch),
1451 tca[TCA_RATE]);
1452 if (err)
1453 return err;
1454 }
Stephen Hemminger87990462006-08-10 23:35:16 -07001455 sch_tree_lock(sch);
Patrick McHardyee39e102007-07-02 22:48:13 -07001456 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001457
1458 /* it used to be a nasty bug here, we have to check that node
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001459 * is really leaf before changing cl->un.leaf !
1460 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001461 if (!cl->level) {
Eric Dumazet196d97f2012-11-05 16:40:49 +00001462 cl->quantum = hopt->rate.rate / q->rate2quantum;
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001463 if (!hopt->quantum && cl->quantum < 1000) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001464 pr_warning(
Stephen Hemminger87990462006-08-10 23:35:16 -07001465 "HTB: quantum of class %X is small. Consider r2q change.\n",
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001466 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001467 cl->quantum = 1000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001468 }
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001469 if (!hopt->quantum && cl->quantum > 200000) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001470 pr_warning(
Stephen Hemminger87990462006-08-10 23:35:16 -07001471 "HTB: quantum of class %X is big. Consider r2q change.\n",
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001472 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001473 cl->quantum = 200000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001474 }
1475 if (hopt->quantum)
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001476 cl->quantum = hopt->quantum;
1477 if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO)
1478 cl->prio = TC_HTB_NUMPRIO - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001479 }
1480
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001481 psched_ratecfg_precompute(&cl->rate, &hopt->rate);
1482 psched_ratecfg_precompute(&cl->ceil, &hopt->ceil);
Vimalkumar56b765b2012-10-31 06:04:11 +00001483
Jiri Pirko324f5aa2013-02-12 00:11:59 +00001484 cl->buffer = PSCHED_TICKS2NS(hopt->buffer);
1485 cl->cbuffer = PSCHED_TICKS2NS(hopt->buffer);
Vimalkumar56b765b2012-10-31 06:04:11 +00001486
Linus Torvalds1da177e2005-04-16 15:20:36 -07001487 sch_tree_unlock(sch);
1488
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001489 qdisc_class_hash_grow(sch, &q->clhash);
1490
Linus Torvalds1da177e2005-04-16 15:20:36 -07001491 *arg = (unsigned long)cl;
1492 return 0;
1493
1494failure:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001495 return err;
1496}
1497
1498static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1499{
1500 struct htb_sched *q = qdisc_priv(sch);
1501 struct htb_class *cl = (struct htb_class *)arg;
1502 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001503
Linus Torvalds1da177e2005-04-16 15:20:36 -07001504 return fl;
1505}
1506
1507static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
Stephen Hemminger87990462006-08-10 23:35:16 -07001508 u32 classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001509{
Stephen Hemminger87990462006-08-10 23:35:16 -07001510 struct htb_class *cl = htb_find(classid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001511
Linus Torvalds1da177e2005-04-16 15:20:36 -07001512 /*if (cl && !cl->level) return 0;
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001513 * The line above used to be there to prevent attaching filters to
1514 * leaves. But at least tc_index filter uses this just to get class
1515 * for other reasons so that we have to allow for it.
1516 * ----
1517 * 19.6.2002 As Werner explained it is ok - bind filter is just
1518 * another way to "lock" the class - unlike "get" this lock can
1519 * be broken by class during destroy IIUC.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001520 */
Stephen Hemminger87990462006-08-10 23:35:16 -07001521 if (cl)
1522 cl->filter_cnt++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001523 return (unsigned long)cl;
1524}
1525
1526static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1527{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001528 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--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001532}
1533
1534static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1535{
1536 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001537 struct htb_class *cl;
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001538 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001539
1540 if (arg->stop)
1541 return;
1542
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001543 for (i = 0; i < q->clhash.hashsize; i++) {
Sasha Levinb67bfe02013-02-27 17:06:00 -08001544 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001545 if (arg->count < arg->skip) {
1546 arg->count++;
1547 continue;
1548 }
1549 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1550 arg->stop = 1;
1551 return;
1552 }
1553 arg->count++;
1554 }
1555 }
1556}
1557
Eric Dumazet20fea082007-11-14 01:44:41 -08001558static const struct Qdisc_class_ops htb_class_ops = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001559 .graft = htb_graft,
1560 .leaf = htb_leaf,
Patrick McHardy256d61b2006-11-29 17:37:05 -08001561 .qlen_notify = htb_qlen_notify,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001562 .get = htb_get,
1563 .put = htb_put,
1564 .change = htb_change_class,
1565 .delete = htb_delete,
1566 .walk = htb_walk,
1567 .tcf_chain = htb_find_tcf,
1568 .bind_tcf = htb_bind_filter,
1569 .unbind_tcf = htb_unbind_filter,
1570 .dump = htb_dump_class,
1571 .dump_stats = htb_dump_class_stats,
1572};
1573
Eric Dumazet20fea082007-11-14 01:44:41 -08001574static struct Qdisc_ops htb_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001575 .cl_ops = &htb_class_ops,
1576 .id = "htb",
1577 .priv_size = sizeof(struct htb_sched),
1578 .enqueue = htb_enqueue,
1579 .dequeue = htb_dequeue,
Jarek Poplawski77be1552008-10-31 00:47:01 -07001580 .peek = qdisc_peek_dequeued,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001581 .drop = htb_drop,
1582 .init = htb_init,
1583 .reset = htb_reset,
1584 .destroy = htb_destroy,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001585 .dump = htb_dump,
1586 .owner = THIS_MODULE,
1587};
1588
1589static int __init htb_module_init(void)
1590{
Stephen Hemminger87990462006-08-10 23:35:16 -07001591 return register_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001592}
Stephen Hemminger87990462006-08-10 23:35:16 -07001593static void __exit htb_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001594{
Stephen Hemminger87990462006-08-10 23:35:16 -07001595 unregister_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001596}
Stephen Hemminger87990462006-08-10 23:35:16 -07001597
Linus Torvalds1da177e2005-04-16 15:20:36 -07001598module_init(htb_module_init)
1599module_exit(htb_module_exit)
1600MODULE_LICENSE("GPL");