blob: 9f949abcacef1680dcdc15579c7fe56611f21852 [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);
Harry Mason29824312014-01-17 13:22:32 +0000222 if (cl) {
223 if (cl->level == 0)
224 return cl;
225 /* Start with inner filter chain if a non-leaf class is selected */
226 tcf = cl->filter_list;
227 } else {
228 tcf = q->filter_list;
229 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700230
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700231 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700232 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
233#ifdef CONFIG_NET_CLS_ACT
234 switch (result) {
235 case TC_ACT_QUEUED:
Stephen Hemminger87990462006-08-10 23:35:16 -0700236 case TC_ACT_STOLEN:
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700237 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700238 case TC_ACT_SHOT:
239 return NULL;
240 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241#endif
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000242 cl = (void *)res.class;
243 if (!cl) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700244 if (res.classid == sch->handle)
Stephen Hemminger87990462006-08-10 23:35:16 -0700245 return HTB_DIRECT; /* X:0 (direct flow) */
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000246 cl = htb_find(res.classid, sch);
247 if (!cl)
Stephen Hemminger87990462006-08-10 23:35:16 -0700248 break; /* filter selected invalid classid */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700249 }
250 if (!cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700251 return cl; /* we hit leaf; return it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700252
253 /* we have got inner class; apply inner filter chain */
254 tcf = cl->filter_list;
255 }
256 /* classification failed; try to use default class */
Stephen Hemminger87990462006-08-10 23:35:16 -0700257 cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258 if (!cl || cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700259 return HTB_DIRECT; /* bad default .. this is safe bet */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700260 return cl;
261}
262
Linus Torvalds1da177e2005-04-16 15:20:36 -0700263/**
264 * htb_add_to_id_tree - adds class to the round robin list
265 *
266 * Routine adds class to the list (actually tree) sorted by classid.
267 * Make sure that class is not already on such list for given prio.
268 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700269static void htb_add_to_id_tree(struct rb_root *root,
270 struct htb_class *cl, int prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700271{
272 struct rb_node **p = &root->rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700273
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700275 struct htb_class *c;
276 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700277 c = rb_entry(parent, struct htb_class, node[prio]);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700278
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700279 if (cl->common.classid > c->common.classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700281 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700282 p = &parent->rb_left;
283 }
284 rb_link_node(&cl->node[prio], parent, p);
285 rb_insert_color(&cl->node[prio], root);
286}
287
288/**
289 * htb_add_to_wait_tree - adds class to the event queue with delay
290 *
291 * The class is added to priority event queue to indicate that class will
292 * change its mode in cl->pq_key microseconds. Make sure that class is not
293 * already in the queue.
294 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700295static void htb_add_to_wait_tree(struct htb_sched *q,
Vimalkumar56b765b2012-10-31 06:04:11 +0000296 struct htb_class *cl, s64 delay)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700297{
Eric Dumazetc9364632013-06-15 03:30:10 -0700298 struct rb_node **p = &q->hlevel[cl->level].wait_pq.rb_node, *parent = NULL;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700299
Patrick McHardyfb983d42007-03-16 01:22:39 -0700300 cl->pq_key = q->now + delay;
301 if (cl->pq_key == q->now)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302 cl->pq_key++;
303
304 /* update the nearest event cache */
Patrick McHardyfb983d42007-03-16 01:22:39 -0700305 if (q->near_ev_cache[cl->level] > cl->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700306 q->near_ev_cache[cl->level] = cl->pq_key;
Stephen Hemminger87990462006-08-10 23:35:16 -0700307
Linus Torvalds1da177e2005-04-16 15:20:36 -0700308 while (*p) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700309 struct htb_class *c;
310 parent = *p;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700311 c = rb_entry(parent, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700312 if (cl->pq_key >= c->pq_key)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700313 p = &parent->rb_right;
Stephen Hemminger87990462006-08-10 23:35:16 -0700314 else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315 p = &parent->rb_left;
316 }
317 rb_link_node(&cl->pq_node, parent, p);
Eric Dumazetc9364632013-06-15 03:30:10 -0700318 rb_insert_color(&cl->pq_node, &q->hlevel[cl->level].wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700319}
320
321/**
322 * htb_next_rb_node - finds next node in binary tree
323 *
324 * When we are past last key we return NULL.
325 * Average complexity is 2 steps per call.
326 */
Stephen Hemminger3696f622006-08-10 23:36:01 -0700327static inline void htb_next_rb_node(struct rb_node **n)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700328{
329 *n = rb_next(*n);
330}
331
332/**
333 * htb_add_class_to_row - add class to its row
334 *
335 * The class is added to row at priorities marked in mask.
336 * It does nothing if mask == 0.
337 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700338static inline void htb_add_class_to_row(struct htb_sched *q,
339 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700340{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341 q->row_mask[cl->level] |= mask;
342 while (mask) {
343 int prio = ffz(~mask);
344 mask &= ~(1 << prio);
Eric Dumazetc9364632013-06-15 03:30:10 -0700345 htb_add_to_id_tree(&q->hlevel[cl->level].hprio[prio].row, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700346 }
347}
348
Stephen Hemminger3696f622006-08-10 23:36:01 -0700349/* If this triggers, it is a bug in this code, but it need not be fatal */
350static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
351{
Ismail Donmez81771b32006-10-03 13:49:10 -0700352 if (RB_EMPTY_NODE(rb)) {
Stephen Hemminger3696f622006-08-10 23:36:01 -0700353 WARN_ON(1);
354 } else {
355 rb_erase(rb, root);
356 RB_CLEAR_NODE(rb);
357 }
358}
359
360
Linus Torvalds1da177e2005-04-16 15:20:36 -0700361/**
362 * htb_remove_class_from_row - removes class from its row
363 *
364 * The class is removed from row at priorities marked in mask.
365 * It does nothing if mask == 0.
366 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700367static inline void htb_remove_class_from_row(struct htb_sched *q,
368 struct htb_class *cl, int mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700369{
370 int m = 0;
Eric Dumazetc9364632013-06-15 03:30:10 -0700371 struct htb_level *hlevel = &q->hlevel[cl->level];
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700372
Linus Torvalds1da177e2005-04-16 15:20:36 -0700373 while (mask) {
374 int prio = ffz(~mask);
Eric Dumazetc9364632013-06-15 03:30:10 -0700375 struct htb_prio *hprio = &hlevel->hprio[prio];
Stephen Hemminger3696f622006-08-10 23:36:01 -0700376
Linus Torvalds1da177e2005-04-16 15:20:36 -0700377 mask &= ~(1 << prio);
Eric Dumazetc9364632013-06-15 03:30:10 -0700378 if (hprio->ptr == cl->node + prio)
379 htb_next_rb_node(&hprio->ptr);
Stephen Hemminger3696f622006-08-10 23:36:01 -0700380
Eric Dumazetc9364632013-06-15 03:30:10 -0700381 htb_safe_rb_erase(cl->node + prio, &hprio->row);
382 if (!hprio->row.rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700383 m |= 1 << prio;
384 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700385 q->row_mask[cl->level] &= ~m;
386}
387
388/**
389 * htb_activate_prios - creates active classe's feed chain
390 *
391 * The class is connected to ancestors and/or appropriate rows
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900392 * for priorities it is participating on. cl->cmode must be new
Linus Torvalds1da177e2005-04-16 15:20:36 -0700393 * (activated) mode. It does nothing if cl->prio_activity == 0.
394 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700395static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396{
397 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700398 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399
400 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700401 m = mask;
402 while (m) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700403 int prio = ffz(~m);
404 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700405
Eric Dumazetc9364632013-06-15 03:30:10 -0700406 if (p->un.inner.clprio[prio].feed.rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700407 /* parent already has its feed in use so that
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000408 * reset bit in mask as parent is already ok
409 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700410 mask &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700411
Eric Dumazetc9364632013-06-15 03:30:10 -0700412 htb_add_to_id_tree(&p->un.inner.clprio[prio].feed, cl, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700413 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700414 p->prio_activity |= mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700415 cl = p;
416 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700417
Linus Torvalds1da177e2005-04-16 15:20:36 -0700418 }
419 if (cl->cmode == HTB_CAN_SEND && mask)
Stephen Hemminger87990462006-08-10 23:35:16 -0700420 htb_add_class_to_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700421}
422
423/**
424 * htb_deactivate_prios - remove class from feed chain
425 *
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900426 * cl->cmode must represent old mode (before deactivation). It does
Linus Torvalds1da177e2005-04-16 15:20:36 -0700427 * nothing if cl->prio_activity == 0. Class is removed from all feed
428 * chains and rows.
429 */
430static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
431{
432 struct htb_class *p = cl->parent;
Stephen Hemminger87990462006-08-10 23:35:16 -0700433 long m, mask = cl->prio_activity;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700434
435 while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700436 m = mask;
437 mask = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700438 while (m) {
439 int prio = ffz(~m);
440 m &= ~(1 << prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700441
Eric Dumazetc9364632013-06-15 03:30:10 -0700442 if (p->un.inner.clprio[prio].ptr == cl->node + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443 /* we are removing child which is pointed to from
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000444 * parent feed - forget the pointer but remember
445 * classid
446 */
Eric Dumazetc9364632013-06-15 03:30:10 -0700447 p->un.inner.clprio[prio].last_ptr_id = cl->common.classid;
448 p->un.inner.clprio[prio].ptr = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700449 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700450
Eric Dumazetc9364632013-06-15 03:30:10 -0700451 htb_safe_rb_erase(cl->node + prio,
452 &p->un.inner.clprio[prio].feed);
Stephen Hemminger87990462006-08-10 23:35:16 -0700453
Eric Dumazetc9364632013-06-15 03:30:10 -0700454 if (!p->un.inner.clprio[prio].feed.rb_node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700455 mask |= 1 << prio;
456 }
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700457
Linus Torvalds1da177e2005-04-16 15:20:36 -0700458 p->prio_activity &= ~mask;
Stephen Hemminger87990462006-08-10 23:35:16 -0700459 cl = p;
460 p = cl->parent;
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700461
Linus Torvalds1da177e2005-04-16 15:20:36 -0700462 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700463 if (cl->cmode == HTB_CAN_SEND && mask)
464 htb_remove_class_from_row(q, cl, mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465}
466
Vimalkumar56b765b2012-10-31 06:04:11 +0000467static inline s64 htb_lowater(const struct htb_class *cl)
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700468{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700469 if (htb_hysteresis)
470 return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
471 else
472 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700473}
Vimalkumar56b765b2012-10-31 06:04:11 +0000474static inline s64 htb_hiwater(const struct htb_class *cl)
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700475{
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700476 if (htb_hysteresis)
477 return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
478 else
479 return 0;
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700480}
Jesper Dangaard Brouer47083fc2008-06-16 16:39:32 -0700481
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700482
Linus Torvalds1da177e2005-04-16 15:20:36 -0700483/**
484 * htb_class_mode - computes and returns current class mode
485 *
486 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
487 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900488 * from now to time when cl will change its state.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700489 * Also it is worth to note that class mode doesn't change simply
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900490 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
Linus Torvalds1da177e2005-04-16 15:20:36 -0700491 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
492 * mode transitions per time unit. The speed gain is about 1/6.
493 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700494static inline enum htb_cmode
Vimalkumar56b765b2012-10-31 06:04:11 +0000495htb_class_mode(struct htb_class *cl, s64 *diff)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700496{
Vimalkumar56b765b2012-10-31 06:04:11 +0000497 s64 toks;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700498
Stephen Hemminger87990462006-08-10 23:35:16 -0700499 if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
500 *diff = -toks;
501 return HTB_CANT_SEND;
502 }
Stephen Hemminger18a63e82006-08-10 23:34:02 -0700503
Stephen Hemminger87990462006-08-10 23:35:16 -0700504 if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
505 return HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700506
Stephen Hemminger87990462006-08-10 23:35:16 -0700507 *diff = -toks;
508 return HTB_MAY_BORROW;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700509}
510
511/**
512 * htb_change_class_mode - changes classe's mode
513 *
514 * This should be the only way how to change classe's mode under normal
515 * cirsumstances. Routine will update feed lists linkage, change mode
516 * and add class to the wait event queue if appropriate. New mode should
517 * be different from old one and cl->pq_key has to be valid if changing
518 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
519 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700520static void
Vimalkumar56b765b2012-10-31 06:04:11 +0000521htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, s64 *diff)
Stephen Hemminger87990462006-08-10 23:35:16 -0700522{
523 enum htb_cmode new_mode = htb_class_mode(cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700524
525 if (new_mode == cl->cmode)
Stephen Hemminger87990462006-08-10 23:35:16 -0700526 return;
527
528 if (cl->prio_activity) { /* not necessary: speed optimization */
529 if (cl->cmode != HTB_CANT_SEND)
530 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531 cl->cmode = new_mode;
Stephen Hemminger87990462006-08-10 23:35:16 -0700532 if (new_mode != HTB_CANT_SEND)
533 htb_activate_prios(q, cl);
534 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700535 cl->cmode = new_mode;
536}
537
538/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900539 * htb_activate - inserts leaf cl into appropriate active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700540 *
541 * Routine learns (new) priority of leaf and activates feed chain
542 * for the prio. It can be called on already active leaf safely.
543 * It also adds leaf into droplist.
544 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700545static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700546{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700547 WARN_ON(cl->level || !cl->un.leaf.q || !cl->un.leaf.q->q.qlen);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700548
Linus Torvalds1da177e2005-04-16 15:20:36 -0700549 if (!cl->prio_activity) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800550 cl->prio_activity = 1 << cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700551 htb_activate_prios(q, cl);
552 list_add_tail(&cl->un.leaf.drop_list,
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800553 q->drops + cl->prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700554 }
555}
556
557/**
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900558 * htb_deactivate - remove leaf cl from active feeds
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559 *
560 * Make sure that leaf is active. In the other words it can't be called
561 * with non-active leaf. It also removes class from the drop list.
562 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700563static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700564{
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700565 WARN_ON(!cl->prio_activity);
Stephen Hemminger3bf72952006-08-10 23:31:08 -0700566
Stephen Hemminger87990462006-08-10 23:35:16 -0700567 htb_deactivate_prios(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700568 cl->prio_activity = 0;
569 list_del_init(&cl->un.leaf.drop_list);
570}
571
572static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
573{
Jarek Poplawskif30ab412008-11-13 22:56:30 -0800574 int uninitialized_var(ret);
Stephen Hemminger87990462006-08-10 23:35:16 -0700575 struct htb_sched *q = qdisc_priv(sch);
576 struct htb_class *cl = htb_classify(skb, sch, &ret);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700577
Stephen Hemminger87990462006-08-10 23:35:16 -0700578 if (cl == HTB_DIRECT) {
579 /* enqueue to helper queue */
580 if (q->direct_queue.qlen < q->direct_qlen) {
581 __skb_queue_tail(&q->direct_queue, skb);
582 q->direct_pkts++;
583 } else {
Eric Dumazet17045752012-05-04 04:37:21 +0000584 return qdisc_drop(skb, sch);
Stephen Hemminger87990462006-08-10 23:35:16 -0700585 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700586#ifdef CONFIG_NET_CLS_ACT
Stephen Hemminger87990462006-08-10 23:35:16 -0700587 } else if (!cl) {
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700588 if (ret & __NET_XMIT_BYPASS)
Stephen Hemminger87990462006-08-10 23:35:16 -0700589 sch->qstats.drops++;
590 kfree_skb(skb);
591 return ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700592#endif
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700593 } else if ((ret = qdisc_enqueue(skb, cl->un.leaf.q)) != NET_XMIT_SUCCESS) {
594 if (net_xmit_drop_count(ret)) {
595 sch->qstats.drops++;
596 cl->qstats.drops++;
597 }
David S. Miller69747652008-08-17 23:55:36 -0700598 return ret;
Stephen Hemminger87990462006-08-10 23:35:16 -0700599 } else {
Stephen Hemminger87990462006-08-10 23:35:16 -0700600 htb_activate(q, cl);
601 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700602
Stephen Hemminger87990462006-08-10 23:35:16 -0700603 sch->q.qlen++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700604 return NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700605}
606
Vimalkumar56b765b2012-10-31 06:04:11 +0000607static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, s64 diff)
Jarek Poplawski59e42202008-12-03 21:17:27 -0800608{
Vimalkumar56b765b2012-10-31 06:04:11 +0000609 s64 toks = diff + cl->tokens;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800610
611 if (toks > cl->buffer)
612 toks = cl->buffer;
Jiri Pirko292f1c72013-02-12 00:12:03 +0000613 toks -= (s64) psched_l2t_ns(&cl->rate, bytes);
Jarek Poplawski59e42202008-12-03 21:17:27 -0800614 if (toks <= -cl->mbuffer)
615 toks = 1 - cl->mbuffer;
616
617 cl->tokens = toks;
618}
619
Vimalkumar56b765b2012-10-31 06:04:11 +0000620static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, s64 diff)
Jarek Poplawski59e42202008-12-03 21:17:27 -0800621{
Vimalkumar56b765b2012-10-31 06:04:11 +0000622 s64 toks = diff + cl->ctokens;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800623
624 if (toks > cl->cbuffer)
625 toks = cl->cbuffer;
Jiri Pirko292f1c72013-02-12 00:12:03 +0000626 toks -= (s64) psched_l2t_ns(&cl->ceil, bytes);
Jarek Poplawski59e42202008-12-03 21:17:27 -0800627 if (toks <= -cl->mbuffer)
628 toks = 1 - cl->mbuffer;
629
630 cl->ctokens = toks;
631}
632
Linus Torvalds1da177e2005-04-16 15:20:36 -0700633/**
634 * htb_charge_class - charges amount "bytes" to leaf and ancestors
635 *
636 * Routine assumes that packet "bytes" long was dequeued from leaf cl
637 * borrowing from "level". It accounts bytes to ceil leaky bucket for
638 * leaf and all ancestors and to rate bucket for ancestors at levels
639 * "level" and higher. It also handles possible change of mode resulting
640 * from the update. Note that mode can also increase here (MAY_BORROW to
641 * CAN_SEND) because we can use more precise clock that event queue here.
642 * In such case we remove class from event queue first.
643 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700644static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700645 int level, struct sk_buff *skb)
Stephen Hemminger87990462006-08-10 23:35:16 -0700646{
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700647 int bytes = qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700648 enum htb_cmode old_mode;
Vimalkumar56b765b2012-10-31 06:04:11 +0000649 s64 diff;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700650
651 while (cl) {
Vimalkumar56b765b2012-10-31 06:04:11 +0000652 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653 if (cl->level >= level) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700654 if (cl->level == level)
655 cl->xstats.lends++;
Jarek Poplawski59e42202008-12-03 21:17:27 -0800656 htb_accnt_tokens(cl, bytes, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700657 } else {
658 cl->xstats.borrows++;
Stephen Hemminger87990462006-08-10 23:35:16 -0700659 cl->tokens += diff; /* we moved t_c; update tokens */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700660 }
Jarek Poplawski59e42202008-12-03 21:17:27 -0800661 htb_accnt_ctokens(cl, bytes, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700662 cl->t_c = q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700663
Stephen Hemminger87990462006-08-10 23:35:16 -0700664 old_mode = cl->cmode;
665 diff = 0;
666 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700667 if (old_mode != cl->cmode) {
668 if (old_mode != HTB_CAN_SEND)
Eric Dumazetc9364632013-06-15 03:30:10 -0700669 htb_safe_rb_erase(&cl->pq_node, &q->hlevel[cl->level].wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700670 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700671 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700672 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700673
Eric Dumazetbfe0d022011-01-09 08:30:54 +0000674 /* update basic stats except for leaves which are already updated */
675 if (cl->level)
676 bstats_update(&cl->bstats, skb);
677
Linus Torvalds1da177e2005-04-16 15:20:36 -0700678 cl = cl->parent;
679 }
680}
681
682/**
683 * htb_do_events - make mode changes to classes at the level
684 *
Patrick McHardyfb983d42007-03-16 01:22:39 -0700685 * Scans event queue for pending events and applies them. Returns time of
Jarek Poplawski12247362009-02-01 01:13:22 -0800686 * next pending event (0 for no event in pq, q->now for too many events).
Patrick McHardyfb983d42007-03-16 01:22:39 -0700687 * Note: Applied are events whose have cl->pq_key <= q->now.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700688 */
Eric Dumazetc9364632013-06-15 03:30:10 -0700689static s64 htb_do_events(struct htb_sched *q, const int level,
Eric Dumazet5343a7f2013-06-04 07:11:48 +0000690 unsigned long start)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700691{
Martin Devera8f3ea332008-03-23 22:00:38 -0700692 /* don't run for longer than 2 jiffies; 2 is used instead of
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000693 * 1 to simplify things when jiffy is going to be incremented
694 * too soon
695 */
Jarek Poplawskia73be042009-01-12 21:54:40 -0800696 unsigned long stop_at = start + 2;
Eric Dumazetc9364632013-06-15 03:30:10 -0700697 struct rb_root *wait_pq = &q->hlevel[level].wait_pq;
698
Martin Devera8f3ea332008-03-23 22:00:38 -0700699 while (time_before(jiffies, stop_at)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700700 struct htb_class *cl;
Vimalkumar56b765b2012-10-31 06:04:11 +0000701 s64 diff;
Eric Dumazetc9364632013-06-15 03:30:10 -0700702 struct rb_node *p = rb_first(wait_pq);
Akinbou Mita30bdbe32006-10-12 01:52:05 -0700703
Stephen Hemminger87990462006-08-10 23:35:16 -0700704 if (!p)
705 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700706
707 cl = rb_entry(p, struct htb_class, pq_node);
Patrick McHardyfb983d42007-03-16 01:22:39 -0700708 if (cl->pq_key > q->now)
709 return cl->pq_key;
710
Eric Dumazetc9364632013-06-15 03:30:10 -0700711 htb_safe_rb_erase(p, wait_pq);
Vimalkumar56b765b2012-10-31 06:04:11 +0000712 diff = min_t(s64, q->now - cl->t_c, cl->mbuffer);
Stephen Hemminger87990462006-08-10 23:35:16 -0700713 htb_change_class_mode(q, cl, &diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700714 if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger87990462006-08-10 23:35:16 -0700715 htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700716 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800717
718 /* too much load - let's continue after a break for scheduling */
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800719 if (!(q->warned & HTB_WARN_TOOMANYEVENTS)) {
Yang Yingliangc17988a2013-12-23 17:38:58 +0800720 pr_warn("htb: too many events!\n");
Jarek Poplawskie82181d2009-02-01 01:13:05 -0800721 q->warned |= HTB_WARN_TOOMANYEVENTS;
722 }
Jarek Poplawski12247362009-02-01 01:13:22 -0800723
724 return q->now;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700725}
726
727/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000728 * is no such one exists.
729 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700730static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
731 u32 id)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700732{
733 struct rb_node *r = NULL;
734 while (n) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700735 struct htb_class *cl =
736 rb_entry(n, struct htb_class, node[prio]);
Stephen Hemminger87990462006-08-10 23:35:16 -0700737
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700738 if (id > cl->common.classid) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700739 n = n->rb_right;
Jarek Poplawski1b5c0072008-12-09 22:34:40 -0800740 } else if (id < cl->common.classid) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700741 r = n;
742 n = n->rb_left;
Jarek Poplawski1b5c0072008-12-09 22:34:40 -0800743 } else {
744 return n;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700745 }
746 }
747 return r;
748}
749
750/**
751 * htb_lookup_leaf - returns next leaf class in DRR order
752 *
753 * Find leaf where current feed pointers points to.
754 */
Eric Dumazetc9364632013-06-15 03:30:10 -0700755static struct htb_class *htb_lookup_leaf(struct htb_prio *hprio, const int prio)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700756{
757 int i;
758 struct {
759 struct rb_node *root;
760 struct rb_node **pptr;
761 u32 *pid;
Stephen Hemminger87990462006-08-10 23:35:16 -0700762 } stk[TC_HTB_MAXDEPTH], *sp = stk;
763
Eric Dumazetc9364632013-06-15 03:30:10 -0700764 BUG_ON(!hprio->row.rb_node);
765 sp->root = hprio->row.rb_node;
766 sp->pptr = &hprio->ptr;
767 sp->pid = &hprio->last_ptr_id;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700768
769 for (i = 0; i < 65535; i++) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700770 if (!*sp->pptr && *sp->pid) {
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900771 /* ptr was invalidated but id is valid - try to recover
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000772 * the original or next ptr
773 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700774 *sp->pptr =
775 htb_id_find_next_upper(prio, sp->root, *sp->pid);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700776 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700777 *sp->pid = 0; /* ptr is valid now so that remove this hint as it
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000778 * can become out of date quickly
779 */
Stephen Hemminger87990462006-08-10 23:35:16 -0700780 if (!*sp->pptr) { /* we are at right end; rewind & go up */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700781 *sp->pptr = sp->root;
Stephen Hemminger87990462006-08-10 23:35:16 -0700782 while ((*sp->pptr)->rb_left)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700783 *sp->pptr = (*sp->pptr)->rb_left;
784 if (sp > stk) {
785 sp--;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800786 if (!*sp->pptr) {
787 WARN_ON(1);
Stephen Hemminger87990462006-08-10 23:35:16 -0700788 return NULL;
Jarek Poplawski512bb432008-12-09 22:35:02 -0800789 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700790 htb_next_rb_node(sp->pptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700791 }
792 } else {
793 struct htb_class *cl;
Eric Dumazetc9364632013-06-15 03:30:10 -0700794 struct htb_prio *clp;
795
Stephen Hemminger87990462006-08-10 23:35:16 -0700796 cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
797 if (!cl->level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700798 return cl;
Eric Dumazetc9364632013-06-15 03:30:10 -0700799 clp = &cl->un.inner.clprio[prio];
800 (++sp)->root = clp->feed.rb_node;
801 sp->pptr = &clp->ptr;
802 sp->pid = &clp->last_ptr_id;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700803 }
804 }
Ilpo Järvinen547b7922008-07-25 21:43:18 -0700805 WARN_ON(1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700806 return NULL;
807}
808
809/* dequeues packet at given priority and level; call only if
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000810 * you are sure that there is active class at prio/level
811 */
Eric Dumazetc9364632013-06-15 03:30:10 -0700812static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, const int prio,
813 const int level)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700814{
815 struct sk_buff *skb = NULL;
Stephen Hemminger87990462006-08-10 23:35:16 -0700816 struct htb_class *cl, *start;
Eric Dumazetc9364632013-06-15 03:30:10 -0700817 struct htb_level *hlevel = &q->hlevel[level];
818 struct htb_prio *hprio = &hlevel->hprio[prio];
819
Linus Torvalds1da177e2005-04-16 15:20:36 -0700820 /* look initial class up in the row */
Eric Dumazetc9364632013-06-15 03:30:10 -0700821 start = cl = htb_lookup_leaf(hprio, prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700822
Linus Torvalds1da177e2005-04-16 15:20:36 -0700823 do {
824next:
Jarek Poplawski512bb432008-12-09 22:35:02 -0800825 if (unlikely(!cl))
Stephen Hemminger87990462006-08-10 23:35:16 -0700826 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700827
828 /* class can be empty - it is unlikely but can be true if leaf
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000829 * qdisc drops packets in enqueue routine or if someone used
830 * graft operation on the leaf since last dequeue;
831 * simply deactivate and skip such class
832 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700833 if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
834 struct htb_class *next;
Stephen Hemminger87990462006-08-10 23:35:16 -0700835 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700836
837 /* row/level might become empty */
838 if ((q->row_mask[level] & (1 << prio)) == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -0700839 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700840
Eric Dumazetc9364632013-06-15 03:30:10 -0700841 next = htb_lookup_leaf(hprio, prio);
Stephen Hemminger87990462006-08-10 23:35:16 -0700842
843 if (cl == start) /* fix start if we just deleted it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700844 start = next;
845 cl = next;
846 goto next;
847 }
Stephen Hemminger87990462006-08-10 23:35:16 -0700848
849 skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
850 if (likely(skb != NULL))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700851 break;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800852
Jarek Poplawskib00355d2009-02-01 01:12:42 -0800853 qdisc_warn_nonwc("htb", cl->un.leaf.q);
Eric Dumazetc9364632013-06-15 03:30:10 -0700854 htb_next_rb_node(level ? &cl->parent->un.inner.clprio[prio].ptr:
855 &q->hlevel[0].hprio[prio].ptr);
856 cl = htb_lookup_leaf(hprio, prio);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700857
858 } while (cl != start);
859
860 if (likely(skb != NULL)) {
Eric Dumazet196d97f2012-11-05 16:40:49 +0000861 bstats_update(&cl->bstats, skb);
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700862 cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb);
863 if (cl->un.leaf.deficit[level] < 0) {
Jarek Poplawskic19f7a32008-12-03 21:09:45 -0800864 cl->un.leaf.deficit[level] += cl->quantum;
Eric Dumazetc9364632013-06-15 03:30:10 -0700865 htb_next_rb_node(level ? &cl->parent->un.inner.clprio[prio].ptr :
866 &q->hlevel[0].hprio[prio].ptr);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700867 }
868 /* this used to be after charge_class but this constelation
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000869 * gives us slightly better performance
870 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700871 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700872 htb_deactivate(q, cl);
Ranjit Manomohanc9726d62007-07-10 22:43:16 -0700873 htb_charge_class(q, cl, level, skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700874 }
875 return skb;
876}
877
Linus Torvalds1da177e2005-04-16 15:20:36 -0700878static struct sk_buff *htb_dequeue(struct Qdisc *sch)
879{
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800880 struct sk_buff *skb;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700881 struct htb_sched *q = qdisc_priv(sch);
882 int level;
Eric Dumazet5343a7f2013-06-04 07:11:48 +0000883 s64 next_event;
Jarek Poplawskia73be042009-01-12 21:54:40 -0800884 unsigned long start_at;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700885
886 /* try to dequeue direct packets as high prio (!) to minimize cpu work */
Stephen Hemminger87990462006-08-10 23:35:16 -0700887 skb = __skb_dequeue(&q->direct_queue);
888 if (skb != NULL) {
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800889ok:
890 qdisc_bstats_update(sch, skb);
Eric Dumazetfd245a42011-01-20 05:27:16 +0000891 qdisc_unthrottled(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700892 sch->q.qlen--;
893 return skb;
894 }
895
Stephen Hemminger87990462006-08-10 23:35:16 -0700896 if (!sch->q.qlen)
897 goto fin;
Vimalkumar56b765b2012-10-31 06:04:11 +0000898 q->now = ktime_to_ns(ktime_get());
Jarek Poplawskia73be042009-01-12 21:54:40 -0800899 start_at = jiffies;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700900
Stefan Haskod2fe85d2012-12-21 15:04:59 +0000901 next_event = q->now + 5LLU * NSEC_PER_SEC;
Jarek Poplawski633fe662008-12-03 21:09:10 -0800902
Linus Torvalds1da177e2005-04-16 15:20:36 -0700903 for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
904 /* common case optimization - skip event handler quickly */
905 int m;
Eric Dumazetc9364632013-06-15 03:30:10 -0700906 s64 event = q->near_ev_cache[level];
Stephen Hemminger87990462006-08-10 23:35:16 -0700907
Eric Dumazetc9364632013-06-15 03:30:10 -0700908 if (q->now >= event) {
Jarek Poplawskia73be042009-01-12 21:54:40 -0800909 event = htb_do_events(q, level, start_at);
Patrick McHardy2e4b3b02007-05-23 23:39:54 -0700910 if (!event)
Vimalkumar56b765b2012-10-31 06:04:11 +0000911 event = q->now + NSEC_PER_SEC;
Patrick McHardy2e4b3b02007-05-23 23:39:54 -0700912 q->near_ev_cache[level] = event;
Eric Dumazetc9364632013-06-15 03:30:10 -0700913 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700914
Jarek Poplawskic0851342009-01-12 21:54:16 -0800915 if (next_event > event)
Patrick McHardyfb983d42007-03-16 01:22:39 -0700916 next_event = event;
917
Linus Torvalds1da177e2005-04-16 15:20:36 -0700918 m = ~q->row_mask[level];
919 while (m != (int)(-1)) {
Stephen Hemminger87990462006-08-10 23:35:16 -0700920 int prio = ffz(m);
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000921
Linus Torvalds1da177e2005-04-16 15:20:36 -0700922 m |= 1 << prio;
Stephen Hemminger87990462006-08-10 23:35:16 -0700923 skb = htb_dequeue_tree(q, prio, level);
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800924 if (likely(skb != NULL))
925 goto ok;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700926 }
927 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700928 sch->qstats.overlimits++;
Vimalkumar56b765b2012-10-31 06:04:11 +0000929 if (likely(next_event > q->now)) {
930 if (!test_bit(__QDISC_STATE_DEACTIVATED,
931 &qdisc_root_sleeping(q->watchdog.qdisc)->state)) {
932 ktime_t time = ns_to_ktime(next_event);
933 qdisc_throttled(q->watchdog.qdisc);
934 hrtimer_start(&q->watchdog.timer, time,
935 HRTIMER_MODE_ABS);
936 }
937 } else {
Jarek Poplawski12247362009-02-01 01:13:22 -0800938 schedule_work(&q->work);
Vimalkumar56b765b2012-10-31 06:04:11 +0000939 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700940fin:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700941 return skb;
942}
943
944/* try to drop from each class (by prio) until one succeed */
Stephen Hemminger87990462006-08-10 23:35:16 -0700945static unsigned int htb_drop(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700946{
947 struct htb_sched *q = qdisc_priv(sch);
948 int prio;
949
950 for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
951 struct list_head *p;
Stephen Hemminger87990462006-08-10 23:35:16 -0700952 list_for_each(p, q->drops + prio) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700953 struct htb_class *cl = list_entry(p, struct htb_class,
954 un.leaf.drop_list);
955 unsigned int len;
Stephen Hemminger87990462006-08-10 23:35:16 -0700956 if (cl->un.leaf.q->ops->drop &&
957 (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700958 sch->q.qlen--;
959 if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger87990462006-08-10 23:35:16 -0700960 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700961 return len;
962 }
963 }
964 }
965 return 0;
966}
967
968/* reset all classes */
969/* always caled under BH & queue lock */
Stephen Hemminger87990462006-08-10 23:35:16 -0700970static void htb_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700971{
972 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700973 struct htb_class *cl;
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700974 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700975
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -0700976 for (i = 0; i < q->clhash.hashsize; i++) {
Sasha Levinb67bfe02013-02-27 17:06:00 -0800977 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700978 if (cl->level)
Stephen Hemminger87990462006-08-10 23:35:16 -0700979 memset(&cl->un.inner, 0, sizeof(cl->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700980 else {
Stephen Hemminger87990462006-08-10 23:35:16 -0700981 if (cl->un.leaf.q)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700982 qdisc_reset(cl->un.leaf.q);
983 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
984 }
985 cl->prio_activity = 0;
986 cl->cmode = HTB_CAN_SEND;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700987
988 }
989 }
Patrick McHardyfb983d42007-03-16 01:22:39 -0700990 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700991 __skb_queue_purge(&q->direct_queue);
992 sch->q.qlen = 0;
Eric Dumazetc9364632013-06-15 03:30:10 -0700993 memset(q->hlevel, 0, sizeof(q->hlevel));
Stephen Hemminger87990462006-08-10 23:35:16 -0700994 memset(q->row_mask, 0, sizeof(q->row_mask));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700995 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -0700996 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700997}
998
Patrick McHardy27a34212008-01-23 20:35:39 -0800999static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
1000 [TCA_HTB_PARMS] = { .len = sizeof(struct tc_htb_opt) },
1001 [TCA_HTB_INIT] = { .len = sizeof(struct tc_htb_glob) },
1002 [TCA_HTB_CTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
1003 [TCA_HTB_RTAB] = { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001004 [TCA_HTB_DIRECT_QLEN] = { .type = NLA_U32 },
Eric Dumazetdf62cdf2013-09-19 09:10:20 -07001005 [TCA_HTB_RATE64] = { .type = NLA_U64 },
1006 [TCA_HTB_CEIL64] = { .type = NLA_U64 },
Patrick McHardy27a34212008-01-23 20:35:39 -08001007};
1008
Jarek Poplawski12247362009-02-01 01:13:22 -08001009static void htb_work_func(struct work_struct *work)
1010{
1011 struct htb_sched *q = container_of(work, struct htb_sched, work);
1012 struct Qdisc *sch = q->watchdog.qdisc;
1013
1014 __netif_schedule(qdisc_root(sch));
1015}
1016
Patrick McHardy1e904742008-01-22 22:11:17 -08001017static int htb_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001018{
1019 struct htb_sched *q = qdisc_priv(sch);
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001020 struct nlattr *tb[TCA_HTB_MAX + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001021 struct tc_htb_glob *gopt;
Patrick McHardycee63722008-01-23 20:33:32 -08001022 int err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001023 int i;
Patrick McHardycee63722008-01-23 20:33:32 -08001024
1025 if (!opt)
1026 return -EINVAL;
1027
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001028 err = nla_parse_nested(tb, TCA_HTB_MAX, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -08001029 if (err < 0)
1030 return err;
1031
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001032 if (!tb[TCA_HTB_INIT])
Linus Torvalds1da177e2005-04-16 15:20:36 -07001033 return -EINVAL;
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001034
Patrick McHardy1e904742008-01-22 22:11:17 -08001035 gopt = nla_data(tb[TCA_HTB_INIT]);
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001036 if (gopt->version != HTB_VER >> 16)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001037 return -EINVAL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001038
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001039 err = qdisc_class_hash_init(&q->clhash);
1040 if (err < 0)
1041 return err;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001042 for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger87990462006-08-10 23:35:16 -07001043 INIT_LIST_HEAD(q->drops + i);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001044
Patrick McHardyfb983d42007-03-16 01:22:39 -07001045 qdisc_watchdog_init(&q->watchdog, sch);
Jarek Poplawski12247362009-02-01 01:13:22 -08001046 INIT_WORK(&q->work, htb_work_func);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001047 skb_queue_head_init(&q->direct_queue);
1048
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001049 if (tb[TCA_HTB_DIRECT_QLEN])
1050 q->direct_qlen = nla_get_u32(tb[TCA_HTB_DIRECT_QLEN]);
1051 else {
1052 q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
1053 if (q->direct_qlen < 2) /* some devices have zero tx_queue_len */
1054 q->direct_qlen = 2;
1055 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001056 if ((q->rate2quantum = gopt->rate2quantum) < 1)
1057 q->rate2quantum = 1;
1058 q->defcls = gopt->defcls;
1059
1060 return 0;
1061}
1062
1063static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
1064{
1065 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001066 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001067 struct tc_htb_glob gopt;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001068
Eric Dumazet6f542ef2014-03-05 10:14:34 -08001069 /* Its safe to not acquire qdisc lock. As we hold RTNL,
1070 * no change can happen on the qdisc parameters.
1071 */
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001072
1073 gopt.direct_pkts = q->direct_pkts;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001074 gopt.version = HTB_VER;
1075 gopt.rate2quantum = q->rate2quantum;
1076 gopt.defcls = q->defcls;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001077 gopt.debug = 0;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001078
1079 nest = nla_nest_start(skb, TCA_OPTIONS);
1080 if (nest == NULL)
1081 goto nla_put_failure;
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001082 if (nla_put(skb, TCA_HTB_INIT, sizeof(gopt), &gopt) ||
1083 nla_put_u32(skb, TCA_HTB_DIRECT_QLEN, q->direct_qlen))
David S. Miller1b34ec42012-03-29 05:11:39 -04001084 goto nla_put_failure;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001085
Eric Dumazet6f542ef2014-03-05 10:14:34 -08001086 return nla_nest_end(skb, nest);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001087
Patrick McHardy1e904742008-01-22 22:11:17 -08001088nla_put_failure:
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001089 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001090 return -1;
1091}
1092
1093static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
Stephen Hemminger87990462006-08-10 23:35:16 -07001094 struct sk_buff *skb, struct tcmsg *tcm)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001095{
Stephen Hemminger87990462006-08-10 23:35:16 -07001096 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001097 struct nlattr *nest;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001098 struct tc_htb_opt opt;
1099
Eric Dumazet6f542ef2014-03-05 10:14:34 -08001100 /* Its safe to not acquire qdisc lock. As we hold RTNL,
1101 * no change can happen on the class parameters.
1102 */
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001103 tcm->tcm_parent = cl->parent ? cl->parent->common.classid : TC_H_ROOT;
1104 tcm->tcm_handle = cl->common.classid;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001105 if (!cl->level && cl->un.leaf.q)
1106 tcm->tcm_info = cl->un.leaf.q->handle;
1107
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001108 nest = nla_nest_start(skb, TCA_OPTIONS);
1109 if (nest == NULL)
1110 goto nla_put_failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001111
Stephen Hemminger87990462006-08-10 23:35:16 -07001112 memset(&opt, 0, sizeof(opt));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001113
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001114 psched_ratecfg_getrate(&opt.rate, &cl->rate);
Jiri Pirko9c10f412013-02-12 00:12:00 +00001115 opt.buffer = PSCHED_NS2TICKS(cl->buffer);
Eric Dumazet01cb71d2013-06-02 13:55:05 +00001116 psched_ratecfg_getrate(&opt.ceil, &cl->ceil);
Jiri Pirko9c10f412013-02-12 00:12:00 +00001117 opt.cbuffer = PSCHED_NS2TICKS(cl->cbuffer);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001118 opt.quantum = cl->quantum;
1119 opt.prio = cl->prio;
Stephen Hemminger87990462006-08-10 23:35:16 -07001120 opt.level = cl->level;
David S. Miller1b34ec42012-03-29 05:11:39 -04001121 if (nla_put(skb, TCA_HTB_PARMS, sizeof(opt), &opt))
1122 goto nla_put_failure;
Eric Dumazetdf62cdf2013-09-19 09:10:20 -07001123 if ((cl->rate.rate_bytes_ps >= (1ULL << 32)) &&
1124 nla_put_u64(skb, TCA_HTB_RATE64, cl->rate.rate_bytes_ps))
1125 goto nla_put_failure;
1126 if ((cl->ceil.rate_bytes_ps >= (1ULL << 32)) &&
1127 nla_put_u64(skb, TCA_HTB_CEIL64, cl->ceil.rate_bytes_ps))
1128 goto nla_put_failure;
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001129
Eric Dumazet6f542ef2014-03-05 10:14:34 -08001130 return nla_nest_end(skb, nest);
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001131
Patrick McHardy1e904742008-01-22 22:11:17 -08001132nla_put_failure:
Patrick McHardy4b3550ef2008-01-23 20:34:11 -08001133 nla_nest_cancel(skb, nest);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001134 return -1;
1135}
1136
1137static int
Stephen Hemminger87990462006-08-10 23:35:16 -07001138htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001139{
Stephen Hemminger87990462006-08-10 23:35:16 -07001140 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001141
Linus Torvalds1da177e2005-04-16 15:20:36 -07001142 if (!cl->level && cl->un.leaf.q)
1143 cl->qstats.qlen = cl->un.leaf.q->q.qlen;
Eric Dumazet5343a7f2013-06-04 07:11:48 +00001144 cl->xstats.tokens = PSCHED_NS2TICKS(cl->tokens);
1145 cl->xstats.ctokens = PSCHED_NS2TICKS(cl->ctokens);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001146
1147 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
Eric Dumazetd250a5f2009-10-02 10:32:18 +00001148 gnet_stats_copy_rate_est(d, NULL, &cl->rate_est) < 0 ||
Linus Torvalds1da177e2005-04-16 15:20:36 -07001149 gnet_stats_copy_queue(d, &cl->qstats) < 0)
1150 return -1;
1151
1152 return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
1153}
1154
1155static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
Stephen Hemminger87990462006-08-10 23:35:16 -07001156 struct Qdisc **old)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001157{
Stephen Hemminger87990462006-08-10 23:35:16 -07001158 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001159
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001160 if (cl->level)
1161 return -EINVAL;
1162 if (new == NULL &&
Changli Gao3511c912010-10-16 13:04:08 +00001163 (new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001164 cl->common.classid)) == NULL)
1165 return -ENOBUFS;
1166
1167 sch_tree_lock(sch);
1168 *old = cl->un.leaf.q;
1169 cl->un.leaf.q = new;
1170 if (*old != NULL) {
1171 qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
1172 qdisc_reset(*old);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001173 }
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001174 sch_tree_unlock(sch);
1175 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001176}
1177
Stephen Hemminger87990462006-08-10 23:35:16 -07001178static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001179{
Stephen Hemminger87990462006-08-10 23:35:16 -07001180 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy5b9a9cc2009-09-04 06:41:17 +00001181 return !cl->level ? cl->un.leaf.q : NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001182}
1183
Patrick McHardy256d61b2006-11-29 17:37:05 -08001184static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
1185{
1186 struct htb_class *cl = (struct htb_class *)arg;
1187
1188 if (cl->un.leaf.q->q.qlen == 0)
1189 htb_deactivate(qdisc_priv(sch), cl);
1190}
1191
Linus Torvalds1da177e2005-04-16 15:20:36 -07001192static unsigned long htb_get(struct Qdisc *sch, u32 classid)
1193{
Stephen Hemminger87990462006-08-10 23:35:16 -07001194 struct htb_class *cl = htb_find(classid, sch);
1195 if (cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001196 cl->refcnt++;
1197 return (unsigned long)cl;
1198}
1199
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001200static inline int htb_parent_last_child(struct htb_class *cl)
1201{
1202 if (!cl->parent)
1203 /* the root class */
1204 return 0;
Patrick McHardy42077592008-07-05 23:22:53 -07001205 if (cl->parent->children > 1)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001206 /* not the last child */
1207 return 0;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001208 return 1;
1209}
1210
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001211static void htb_parent_to_leaf(struct htb_sched *q, struct htb_class *cl,
1212 struct Qdisc *new_q)
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001213{
1214 struct htb_class *parent = cl->parent;
1215
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001216 WARN_ON(cl->level || !cl->un.leaf.q || cl->prio_activity);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001217
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001218 if (parent->cmode != HTB_CAN_SEND)
Eric Dumazetc9364632013-06-15 03:30:10 -07001219 htb_safe_rb_erase(&parent->pq_node,
1220 &q->hlevel[parent->level].wait_pq);
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001221
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001222 parent->level = 0;
1223 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
1224 INIT_LIST_HEAD(&parent->un.leaf.drop_list);
1225 parent->un.leaf.q = new_q ? new_q : &noop_qdisc;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001226 parent->tokens = parent->buffer;
1227 parent->ctokens = parent->cbuffer;
Eric Dumazet5343a7f2013-06-04 07:11:48 +00001228 parent->t_c = ktime_to_ns(ktime_get());
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001229 parent->cmode = HTB_CAN_SEND;
1230}
1231
Stephen Hemminger87990462006-08-10 23:35:16 -07001232static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001233{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001234 if (!cl->level) {
Ilpo Järvinen547b7922008-07-25 21:43:18 -07001235 WARN_ON(!cl->un.leaf.q);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001236 qdisc_destroy(cl->un.leaf.q);
1237 }
Patrick McHardyee39e102007-07-02 22:48:13 -07001238 gen_kill_estimator(&cl->bstats, &cl->rate_est);
Patrick McHardyff31ab52008-07-01 19:52:38 -07001239 tcf_destroy_chain(&cl->filter_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001240 kfree(cl);
1241}
1242
Stephen Hemminger87990462006-08-10 23:35:16 -07001243static void htb_destroy(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001244{
1245 struct htb_sched *q = qdisc_priv(sch);
Sasha Levinb67bfe02013-02-27 17:06:00 -08001246 struct hlist_node *next;
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001247 struct htb_class *cl;
1248 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001249
Jarek Poplawski12247362009-02-01 01:13:22 -08001250 cancel_work_sync(&q->work);
Patrick McHardyfb983d42007-03-16 01:22:39 -07001251 qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001252 /* This line used to be after htb_destroy_class call below
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001253 * and surprisingly it worked in 2.4. But it must precede it
1254 * because filter need its target class alive to be able to call
1255 * unbind_filter on it (without Oops).
1256 */
Patrick McHardyff31ab52008-07-01 19:52:38 -07001257 tcf_destroy_chain(&q->filter_list);
Stephen Hemminger87990462006-08-10 23:35:16 -07001258
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001259 for (i = 0; i < q->clhash.hashsize; i++) {
Sasha Levinb67bfe02013-02-27 17:06:00 -08001260 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001261 tcf_destroy_chain(&cl->filter_list);
1262 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001263 for (i = 0; i < q->clhash.hashsize; i++) {
Sasha Levinb67bfe02013-02-27 17:06:00 -08001264 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001265 common.hnode)
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001266 htb_destroy_class(sch, cl);
1267 }
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001268 qdisc_class_hash_destroy(&q->clhash);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001269 __skb_queue_purge(&q->direct_queue);
1270}
1271
1272static int htb_delete(struct Qdisc *sch, unsigned long arg)
1273{
1274 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001275 struct htb_class *cl = (struct htb_class *)arg;
Patrick McHardy256d61b2006-11-29 17:37:05 -08001276 unsigned int qlen;
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001277 struct Qdisc *new_q = NULL;
1278 int last_child = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001279
Yang Yinglianga071d272013-12-23 17:38:59 +08001280 /* TODO: why don't allow to delete subtree ? references ? does
1281 * tc subsys guarantee us that in htb_destroy it holds no class
1282 * refs so that we can remove children safely there ?
1283 */
Patrick McHardy42077592008-07-05 23:22:53 -07001284 if (cl->children || cl->filter_cnt)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001285 return -EBUSY;
Stephen Hemminger87990462006-08-10 23:35:16 -07001286
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001287 if (!cl->level && htb_parent_last_child(cl)) {
Changli Gao3511c912010-10-16 13:04:08 +00001288 new_q = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
David S. Millerbb949fb2008-07-08 16:55:56 -07001289 cl->parent->common.classid);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001290 last_child = 1;
1291 }
1292
Linus Torvalds1da177e2005-04-16 15:20:36 -07001293 sch_tree_lock(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001294
Patrick McHardy814a175e2006-11-29 17:34:50 -08001295 if (!cl->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001296 qlen = cl->un.leaf.q->q.qlen;
Patrick McHardy814a175e2006-11-29 17:34:50 -08001297 qdisc_reset(cl->un.leaf.q);
Patrick McHardy256d61b2006-11-29 17:37:05 -08001298 qdisc_tree_decrease_qlen(cl->un.leaf.q, qlen);
Patrick McHardy814a175e2006-11-29 17:34:50 -08001299 }
1300
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001301 /* delete from hash and active; remainder in destroy_class */
1302 qdisc_class_hash_remove(&q->clhash, &cl->common);
Jarek Poplawski26b284d2008-08-13 15:16:43 -07001303 if (cl->parent)
1304 cl->parent->children--;
Patrick McHardyc38c83c2007-03-27 14:04:24 -07001305
Linus Torvalds1da177e2005-04-16 15:20:36 -07001306 if (cl->prio_activity)
Stephen Hemminger87990462006-08-10 23:35:16 -07001307 htb_deactivate(q, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001308
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001309 if (cl->cmode != HTB_CAN_SEND)
Eric Dumazetc9364632013-06-15 03:30:10 -07001310 htb_safe_rb_erase(&cl->pq_node,
1311 &q->hlevel[cl->level].wait_pq);
Patrick McHardyfbd8f132008-07-05 23:22:19 -07001312
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001313 if (last_child)
Jarek Poplawski3ba08b02008-05-03 20:46:29 -07001314 htb_parent_to_leaf(q, cl, new_q);
Jarek Poplawski160d5e12006-12-08 00:26:56 -08001315
Jarek Poplawski7cd0a632009-03-15 20:00:19 -07001316 BUG_ON(--cl->refcnt == 0);
1317 /*
1318 * This shouldn't happen: we "hold" one cops->get() when called
1319 * from tc_ctl_tclass; the destroy method is done from cops->put().
1320 */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001321
1322 sch_tree_unlock(sch);
1323 return 0;
1324}
1325
1326static void htb_put(struct Qdisc *sch, unsigned long arg)
1327{
Stephen Hemminger87990462006-08-10 23:35:16 -07001328 struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001329
1330 if (--cl->refcnt == 0)
Stephen Hemminger87990462006-08-10 23:35:16 -07001331 htb_destroy_class(sch, cl);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001332}
1333
Stephen Hemminger87990462006-08-10 23:35:16 -07001334static int htb_change_class(struct Qdisc *sch, u32 classid,
Patrick McHardy1e904742008-01-22 22:11:17 -08001335 u32 parentid, struct nlattr **tca,
Stephen Hemminger87990462006-08-10 23:35:16 -07001336 unsigned long *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001337{
1338 int err = -EINVAL;
1339 struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger87990462006-08-10 23:35:16 -07001340 struct htb_class *cl = (struct htb_class *)*arg, *parent;
Patrick McHardy1e904742008-01-22 22:11:17 -08001341 struct nlattr *opt = tca[TCA_OPTIONS];
Eric Dumazet6906f4e2013-03-06 06:49:21 +00001342 struct nlattr *tb[TCA_HTB_MAX + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -07001343 struct tc_htb_opt *hopt;
Eric Dumazetdf62cdf2013-09-19 09:10:20 -07001344 u64 rate64, ceil64;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001345
1346 /* extract all subattrs from opt attr */
Patrick McHardycee63722008-01-23 20:33:32 -08001347 if (!opt)
1348 goto failure;
1349
Changli Gaoe18434c2010-09-30 06:17:44 +00001350 err = nla_parse_nested(tb, TCA_HTB_MAX, opt, htb_policy);
Patrick McHardycee63722008-01-23 20:33:32 -08001351 if (err < 0)
1352 goto failure;
1353
1354 err = -EINVAL;
Patrick McHardy27a34212008-01-23 20:35:39 -08001355 if (tb[TCA_HTB_PARMS] == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001356 goto failure;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001357
Stephen Hemminger87990462006-08-10 23:35:16 -07001358 parent = parentid == TC_H_ROOT ? NULL : htb_find(parentid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001359
Patrick McHardy1e904742008-01-22 22:11:17 -08001360 hopt = nla_data(tb[TCA_HTB_PARMS]);
Eric Dumazet196d97f2012-11-05 16:40:49 +00001361 if (!hopt->rate.rate || !hopt->ceil.rate)
Stephen Hemminger87990462006-08-10 23:35:16 -07001362 goto failure;
1363
Jesper Dangaard Brouer8a8e3d82013-08-14 23:47:11 +02001364 /* Keeping backward compatible with rate_table based iproute2 tc */
Yang Yingliang6b1dd852013-12-11 15:48:37 +08001365 if (hopt->rate.linklayer == TC_LINKLAYER_UNAWARE)
1366 qdisc_put_rtab(qdisc_get_rtab(&hopt->rate, tb[TCA_HTB_RTAB]));
1367
1368 if (hopt->ceil.linklayer == TC_LINKLAYER_UNAWARE)
1369 qdisc_put_rtab(qdisc_get_rtab(&hopt->ceil, tb[TCA_HTB_CTAB]));
Jesper Dangaard Brouer8a8e3d82013-08-14 23:47:11 +02001370
Stephen Hemminger87990462006-08-10 23:35:16 -07001371 if (!cl) { /* new class */
Linus Torvalds1da177e2005-04-16 15:20:36 -07001372 struct Qdisc *new_q;
Stephen Hemminger3696f622006-08-10 23:36:01 -07001373 int prio;
Patrick McHardyee39e102007-07-02 22:48:13 -07001374 struct {
Patrick McHardy1e904742008-01-22 22:11:17 -08001375 struct nlattr nla;
Patrick McHardyee39e102007-07-02 22:48:13 -07001376 struct gnet_estimator opt;
1377 } est = {
Patrick McHardy1e904742008-01-22 22:11:17 -08001378 .nla = {
1379 .nla_len = nla_attr_size(sizeof(est.opt)),
1380 .nla_type = TCA_RATE,
Patrick McHardyee39e102007-07-02 22:48:13 -07001381 },
1382 .opt = {
1383 /* 4s interval, 16s averaging constant */
1384 .interval = 2,
1385 .ewma_log = 2,
1386 },
1387 };
Stephen Hemminger3696f622006-08-10 23:36:01 -07001388
Linus Torvalds1da177e2005-04-16 15:20:36 -07001389 /* check for valid classid */
Joe Perchesf64f9e72009-11-29 16:55:45 -08001390 if (!classid || TC_H_MAJ(classid ^ sch->handle) ||
1391 htb_find(classid, sch))
Linus Torvalds1da177e2005-04-16 15:20:36 -07001392 goto failure;
1393
1394 /* check maximal depth */
1395 if (parent && parent->parent && parent->parent->level < 2) {
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001396 pr_err("htb: tree is too deep\n");
Linus Torvalds1da177e2005-04-16 15:20:36 -07001397 goto failure;
1398 }
1399 err = -ENOBUFS;
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001400 cl = kzalloc(sizeof(*cl), GFP_KERNEL);
1401 if (!cl)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001402 goto failure;
Stephen Hemminger87990462006-08-10 23:35:16 -07001403
Eric Dumazet64153ce2013-06-06 14:53:16 -07001404 if (htb_rate_est || tca[TCA_RATE]) {
1405 err = gen_new_estimator(&cl->bstats, &cl->rate_est,
1406 qdisc_root_sleeping_lock(sch),
1407 tca[TCA_RATE] ? : &est.nla);
1408 if (err) {
1409 kfree(cl);
1410 goto failure;
1411 }
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001412 }
1413
Linus Torvalds1da177e2005-04-16 15:20:36 -07001414 cl->refcnt = 1;
Patrick McHardy42077592008-07-05 23:22:53 -07001415 cl->children = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001416 INIT_LIST_HEAD(&cl->un.leaf.drop_list);
Stephen Hemminger3696f622006-08-10 23:36:01 -07001417 RB_CLEAR_NODE(&cl->pq_node);
1418
1419 for (prio = 0; prio < TC_HTB_NUMPRIO; prio++)
1420 RB_CLEAR_NODE(&cl->node[prio]);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001421
1422 /* create leaf qdisc early because it uses kmalloc(GFP_KERNEL)
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001423 * so that can't be used inside of sch_tree_lock
1424 * -- thanks to Karlis Peisenieks
1425 */
Changli Gao3511c912010-10-16 13:04:08 +00001426 new_q = qdisc_create_dflt(sch->dev_queue,
David S. Millerbb949fb2008-07-08 16:55:56 -07001427 &pfifo_qdisc_ops, classid);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001428 sch_tree_lock(sch);
1429 if (parent && !parent->level) {
Patrick McHardy256d61b2006-11-29 17:37:05 -08001430 unsigned int qlen = parent->un.leaf.q->q.qlen;
1431
Linus Torvalds1da177e2005-04-16 15:20:36 -07001432 /* turn parent into inner node */
Patrick McHardy256d61b2006-11-29 17:37:05 -08001433 qdisc_reset(parent->un.leaf.q);
1434 qdisc_tree_decrease_qlen(parent->un.leaf.q, qlen);
Stephen Hemminger87990462006-08-10 23:35:16 -07001435 qdisc_destroy(parent->un.leaf.q);
1436 if (parent->prio_activity)
1437 htb_deactivate(q, parent);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001438
1439 /* remove from evt list because of level change */
1440 if (parent->cmode != HTB_CAN_SEND) {
Eric Dumazetc9364632013-06-15 03:30:10 -07001441 htb_safe_rb_erase(&parent->pq_node, &q->hlevel[0].wait_pq);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001442 parent->cmode = HTB_CAN_SEND;
1443 }
1444 parent->level = (parent->parent ? parent->parent->level
Stephen Hemminger87990462006-08-10 23:35:16 -07001445 : TC_HTB_MAXDEPTH) - 1;
1446 memset(&parent->un.inner, 0, sizeof(parent->un.inner));
Linus Torvalds1da177e2005-04-16 15:20:36 -07001447 }
1448 /* leaf (we) needs elementary qdisc */
1449 cl->un.leaf.q = new_q ? new_q : &noop_qdisc;
1450
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001451 cl->common.classid = classid;
Stephen Hemminger87990462006-08-10 23:35:16 -07001452 cl->parent = parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001453
1454 /* set class to be in HTB_CAN_SEND state */
Jiri Pirkob9a7afd2013-02-12 00:12:02 +00001455 cl->tokens = PSCHED_TICKS2NS(hopt->buffer);
1456 cl->ctokens = PSCHED_TICKS2NS(hopt->cbuffer);
Eric Dumazet5343a7f2013-06-04 07:11:48 +00001457 cl->mbuffer = 60ULL * NSEC_PER_SEC; /* 1min */
1458 cl->t_c = ktime_to_ns(ktime_get());
Linus Torvalds1da177e2005-04-16 15:20:36 -07001459 cl->cmode = HTB_CAN_SEND;
1460
1461 /* attach to the hash list and parent's family */
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001462 qdisc_class_hash_insert(&q->clhash, &cl->common);
Patrick McHardy42077592008-07-05 23:22:53 -07001463 if (parent)
1464 parent->children++;
Patrick McHardyee39e102007-07-02 22:48:13 -07001465 } else {
Stephen Hemminger71bcb092008-11-25 21:13:31 -08001466 if (tca[TCA_RATE]) {
1467 err = gen_replace_estimator(&cl->bstats, &cl->rate_est,
1468 qdisc_root_sleeping_lock(sch),
1469 tca[TCA_RATE]);
1470 if (err)
1471 return err;
1472 }
Stephen Hemminger87990462006-08-10 23:35:16 -07001473 sch_tree_lock(sch);
Patrick McHardyee39e102007-07-02 22:48:13 -07001474 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001475
Yang Yingliang1598f7c2013-12-10 14:59:28 +08001476 rate64 = tb[TCA_HTB_RATE64] ? nla_get_u64(tb[TCA_HTB_RATE64]) : 0;
1477
1478 ceil64 = tb[TCA_HTB_CEIL64] ? nla_get_u64(tb[TCA_HTB_CEIL64]) : 0;
1479
1480 psched_ratecfg_precompute(&cl->rate, &hopt->rate, rate64);
1481 psched_ratecfg_precompute(&cl->ceil, &hopt->ceil, ceil64);
1482
Linus Torvalds1da177e2005-04-16 15:20:36 -07001483 /* 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) {
Yang Yingliang1598f7c2013-12-10 14:59:28 +08001487 u64 quantum = cl->rate.rate_bytes_ps;
1488
1489 do_div(quantum, q->rate2quantum);
1490 cl->quantum = min_t(u64, quantum, INT_MAX);
1491
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001492 if (!hopt->quantum && cl->quantum < 1000) {
Yang Yingliangc17988a2013-12-23 17:38:58 +08001493 pr_warn("HTB: quantum of class %X is small. Consider r2q change.\n",
1494 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001495 cl->quantum = 1000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001496 }
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001497 if (!hopt->quantum && cl->quantum > 200000) {
Yang Yingliangc17988a2013-12-23 17:38:58 +08001498 pr_warn("HTB: quantum of class %X is big. Consider r2q change.\n",
1499 cl->common.classid);
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001500 cl->quantum = 200000;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001501 }
1502 if (hopt->quantum)
Jarek Poplawskic19f7a32008-12-03 21:09:45 -08001503 cl->quantum = hopt->quantum;
1504 if ((cl->prio = hopt->prio) >= TC_HTB_NUMPRIO)
1505 cl->prio = TC_HTB_NUMPRIO - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001506 }
1507
Jiri Pirko324f5aa2013-02-12 00:11:59 +00001508 cl->buffer = PSCHED_TICKS2NS(hopt->buffer);
Vimalkumarf3ad8572013-09-10 17:36:37 -07001509 cl->cbuffer = PSCHED_TICKS2NS(hopt->cbuffer);
Vimalkumar56b765b2012-10-31 06:04:11 +00001510
Linus Torvalds1da177e2005-04-16 15:20:36 -07001511 sch_tree_unlock(sch);
1512
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001513 qdisc_class_hash_grow(sch, &q->clhash);
1514
Linus Torvalds1da177e2005-04-16 15:20:36 -07001515 *arg = (unsigned long)cl;
1516 return 0;
1517
1518failure:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001519 return err;
1520}
1521
1522static struct tcf_proto **htb_find_tcf(struct Qdisc *sch, unsigned long arg)
1523{
1524 struct htb_sched *q = qdisc_priv(sch);
1525 struct htb_class *cl = (struct htb_class *)arg;
1526 struct tcf_proto **fl = cl ? &cl->filter_list : &q->filter_list;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001527
Linus Torvalds1da177e2005-04-16 15:20:36 -07001528 return fl;
1529}
1530
1531static unsigned long htb_bind_filter(struct Qdisc *sch, unsigned long parent,
Stephen Hemminger87990462006-08-10 23:35:16 -07001532 u32 classid)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001533{
Stephen Hemminger87990462006-08-10 23:35:16 -07001534 struct htb_class *cl = htb_find(classid, sch);
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001535
Linus Torvalds1da177e2005-04-16 15:20:36 -07001536 /*if (cl && !cl->level) return 0;
Eric Dumazetcc7ec452011-01-19 19:26:56 +00001537 * The line above used to be there to prevent attaching filters to
1538 * leaves. But at least tc_index filter uses this just to get class
1539 * for other reasons so that we have to allow for it.
1540 * ----
1541 * 19.6.2002 As Werner explained it is ok - bind filter is just
1542 * another way to "lock" the class - unlike "get" this lock can
1543 * be broken by class during destroy IIUC.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001544 */
Stephen Hemminger87990462006-08-10 23:35:16 -07001545 if (cl)
1546 cl->filter_cnt++;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001547 return (unsigned long)cl;
1548}
1549
1550static void htb_unbind_filter(struct Qdisc *sch, unsigned long arg)
1551{
Linus Torvalds1da177e2005-04-16 15:20:36 -07001552 struct htb_class *cl = (struct htb_class *)arg;
Stephen Hemminger3bf72952006-08-10 23:31:08 -07001553
Stephen Hemminger87990462006-08-10 23:35:16 -07001554 if (cl)
1555 cl->filter_cnt--;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001556}
1557
1558static void htb_walk(struct Qdisc *sch, struct qdisc_walker *arg)
1559{
1560 struct htb_sched *q = qdisc_priv(sch);
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001561 struct htb_class *cl;
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001562 unsigned int i;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001563
1564 if (arg->stop)
1565 return;
1566
Patrick McHardyf4c1f3e2008-07-05 23:22:35 -07001567 for (i = 0; i < q->clhash.hashsize; i++) {
Sasha Levinb67bfe02013-02-27 17:06:00 -08001568 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001569 if (arg->count < arg->skip) {
1570 arg->count++;
1571 continue;
1572 }
1573 if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
1574 arg->stop = 1;
1575 return;
1576 }
1577 arg->count++;
1578 }
1579 }
1580}
1581
Eric Dumazet20fea082007-11-14 01:44:41 -08001582static const struct Qdisc_class_ops htb_class_ops = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001583 .graft = htb_graft,
1584 .leaf = htb_leaf,
Patrick McHardy256d61b2006-11-29 17:37:05 -08001585 .qlen_notify = htb_qlen_notify,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001586 .get = htb_get,
1587 .put = htb_put,
1588 .change = htb_change_class,
1589 .delete = htb_delete,
1590 .walk = htb_walk,
1591 .tcf_chain = htb_find_tcf,
1592 .bind_tcf = htb_bind_filter,
1593 .unbind_tcf = htb_unbind_filter,
1594 .dump = htb_dump_class,
1595 .dump_stats = htb_dump_class_stats,
1596};
1597
Eric Dumazet20fea082007-11-14 01:44:41 -08001598static struct Qdisc_ops htb_qdisc_ops __read_mostly = {
Linus Torvalds1da177e2005-04-16 15:20:36 -07001599 .cl_ops = &htb_class_ops,
1600 .id = "htb",
1601 .priv_size = sizeof(struct htb_sched),
1602 .enqueue = htb_enqueue,
1603 .dequeue = htb_dequeue,
Jarek Poplawski77be1552008-10-31 00:47:01 -07001604 .peek = qdisc_peek_dequeued,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001605 .drop = htb_drop,
1606 .init = htb_init,
1607 .reset = htb_reset,
1608 .destroy = htb_destroy,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001609 .dump = htb_dump,
1610 .owner = THIS_MODULE,
1611};
1612
1613static int __init htb_module_init(void)
1614{
Stephen Hemminger87990462006-08-10 23:35:16 -07001615 return register_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001616}
Stephen Hemminger87990462006-08-10 23:35:16 -07001617static void __exit htb_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001618{
Stephen Hemminger87990462006-08-10 23:35:16 -07001619 unregister_qdisc(&htb_qdisc_ops);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001620}
Stephen Hemminger87990462006-08-10 23:35:16 -07001621
Linus Torvalds1da177e2005-04-16 15:20:36 -07001622module_init(htb_module_init)
1623module_exit(htb_module_exit)
1624MODULE_LICENSE("GPL");