sch_htb.c 41.4 KB
Newer Older
Stephen Hemminger's avatar
Stephen Hemminger committed
1
/*
Linus Torvalds's avatar
Linus Torvalds committed
2
3
4
5
6
7
8
9
10
11
12
13
 * net/sched/sch_htb.c	Hierarchical token bucket, feed tree version
 *
 *		This program is free software; you can redistribute it and/or
 *		modify it under the terms of the GNU General Public License
 *		as published by the Free Software Foundation; either version
 *		2 of the License, or (at your option) any later version.
 *
 * Authors:	Martin Devera, <devik@cdi.cz>
 *
 * Credits (in time order) for older HTB versions:
 *              Stef Coene <stef.coene@docum.org>
 *			HTB support at LARTC mailing list
14
 *		Ondrej Kraus, <krauso@barr.cz>
Linus Torvalds's avatar
Linus Torvalds committed
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 *			found missing INIT_QDISC(htb)
 *		Vladimir Smelhaus, Aamer Akhter, Bert Hubert
 *			helped a lot to locate nasty class stall bug
 *		Andi Kleen, Jamal Hadi, Bert Hubert
 *			code review and helpful comments on shaping
 *		Tomasz Wrona, <tw@eter.tym.pl>
 *			created test case so that I was able to fix nasty bug
 *		Wilfried Weissmann
 *			spotted bug in dequeue code and helped with fix
 *		Jiri Fojtasek
 *			fixed requeue routine
 *		and many others. thanks.
 */
#include <linux/module.h>
29
#include <linux/moduleparam.h>
Linus Torvalds's avatar
Linus Torvalds committed
30
31
32
33
34
35
36
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/string.h>
#include <linux/errno.h>
#include <linux/skbuff.h>
#include <linux/list.h>
#include <linux/compiler.h>
37
#include <linux/rbtree.h>
38
#include <net/netlink.h>
Linus Torvalds's avatar
Linus Torvalds committed
39
40
41
42
43
44
#include <net/pkt_sched.h>

/* HTB algorithm.
    Author: devik@cdi.cz
    ========================================================================
    HTB is like TBF with multiple classes. It is also similar to CBQ because
45
    it allows to assign priority to each class in hierarchy.
Linus Torvalds's avatar
Linus Torvalds committed
46
47
48
    In fact it is another implementation of Floyd's formal sharing.

    Levels:
49
    Each class is assigned level. Leaf has ALWAYS level 0 and root
Linus Torvalds's avatar
Linus Torvalds committed
50
51
52
53
    classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
    one less than their parent.
*/

54
static int htb_hysteresis __read_mostly = 0; /* whether to use mode hysteresis for speedup */
Stephen Hemminger's avatar
Stephen Hemminger committed
55
#define HTB_VER 0x30011		/* major must be matched with number suplied by TC as version */
Linus Torvalds's avatar
Linus Torvalds committed
56
57
58
59
60

#if HTB_VER >> 16 != TC_HTB_PROTOVER
#error "Mismatched sch_htb.c and pkt_sch.h"
#endif

61
62
63
64
/* Module parameter and sysfs export */
module_param    (htb_hysteresis, int, 0640);
MODULE_PARM_DESC(htb_hysteresis, "Hysteresis mode, less CPU load, less accurate");

Linus Torvalds's avatar
Linus Torvalds committed
65
66
/* used internaly to keep status of single class */
enum htb_cmode {
Stephen Hemminger's avatar
Stephen Hemminger committed
67
68
69
	HTB_CANT_SEND,		/* class can't send and can't borrow */
	HTB_MAY_BORROW,		/* class can't send but may borrow */
	HTB_CAN_SEND		/* class can send */
Linus Torvalds's avatar
Linus Torvalds committed
70
71
72
};

/* interior & leaf nodes; props specific to leaves are marked L: */
Stephen Hemminger's avatar
Stephen Hemminger committed
73
struct htb_class {
74
	struct Qdisc_class_common common;
Stephen Hemminger's avatar
Stephen Hemminger committed
75
76
77
78
79
80
	/* general class parameters */
	struct gnet_stats_basic bstats;
	struct gnet_stats_queue qstats;
	struct gnet_stats_rate_est rate_est;
	struct tc_htb_xstats xstats;	/* our special stats */
	int refcnt;		/* usage count of this class */
Linus Torvalds's avatar
Linus Torvalds committed
81

Stephen Hemminger's avatar
Stephen Hemminger committed
82
83
	/* topology */
	int level;		/* our level (see above) */
84
	unsigned int children;
Stephen Hemminger's avatar
Stephen Hemminger committed
85
86
	struct htb_class *parent;	/* parent class */

87
88
89
	int prio;		/* these two are used only by leaves... */
	int quantum;		/* but stored for parent-to-leaf return */

Stephen Hemminger's avatar
Stephen Hemminger committed
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
	union {
		struct htb_class_leaf {
			struct Qdisc *q;
			int deficit[TC_HTB_MAXDEPTH];
			struct list_head drop_list;
		} leaf;
		struct htb_class_inner {
			struct rb_root feed[TC_HTB_NUMPRIO];	/* feed trees */
			struct rb_node *ptr[TC_HTB_NUMPRIO];	/* current class ptr */
			/* When class changes from state 1->2 and disconnects from
			   parent's feed then we lost ptr value and start from the
			   first child again. Here we store classid of the
			   last valid ptr (used when ptr is NULL). */
			u32 last_ptr_id[TC_HTB_NUMPRIO];
		} inner;
	} un;
	struct rb_node node[TC_HTB_NUMPRIO];	/* node for self or feed tree */
	struct rb_node pq_node;	/* node for event queue */
108
	psched_time_t pq_key;
Stephen Hemminger's avatar
Stephen Hemminger committed
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

	int prio_activity;	/* for which prios are we active */
	enum htb_cmode cmode;	/* current mode of the class */

	/* class attached filters */
	struct tcf_proto *filter_list;
	int filter_cnt;

	int warned;		/* only one warning about non work conserving .. */

	/* token bucket parameters */
	struct qdisc_rate_table *rate;	/* rate table of the class itself */
	struct qdisc_rate_table *ceil;	/* ceiling rate (limits borrows too) */
	long buffer, cbuffer;	/* token bucket depth/rate */
	psched_tdiff_t mbuffer;	/* max wait time */
	long tokens, ctokens;	/* current number of tokens */
	psched_time_t t_c;	/* checkpoint time */
Linus Torvalds's avatar
Linus Torvalds committed
126
127
};

Stephen Hemminger's avatar
Stephen Hemminger committed
128
struct htb_sched {
129
	struct Qdisc_class_hash clhash;
130
	struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
Stephen Hemminger's avatar
Stephen Hemminger committed
131
132
133
134
135
136

	/* self list - roots of self generating tree */
	struct rb_root row[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
	int row_mask[TC_HTB_MAXDEPTH];
	struct rb_node *ptr[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
	u32 last_ptr_id[TC_HTB_MAXDEPTH][TC_HTB_NUMPRIO];
Linus Torvalds's avatar
Linus Torvalds committed
137

Stephen Hemminger's avatar
Stephen Hemminger committed
138
139
	/* self wait list - roots of wait PQs per row */
	struct rb_root wait_pq[TC_HTB_MAXDEPTH];
Linus Torvalds's avatar
Linus Torvalds committed
140

Stephen Hemminger's avatar
Stephen Hemminger committed
141
	/* time of nearest event per level (row) */
142
	psched_time_t near_ev_cache[TC_HTB_MAXDEPTH];
Linus Torvalds's avatar
Linus Torvalds committed
143

Stephen Hemminger's avatar
Stephen Hemminger committed
144
	int defcls;		/* class where unclassified flows go to */
Linus Torvalds's avatar
Linus Torvalds committed
145

Stephen Hemminger's avatar
Stephen Hemminger committed
146
147
	/* filters for qdisc itself */
	struct tcf_proto *filter_list;
Linus Torvalds's avatar
Linus Torvalds committed
148

Stephen Hemminger's avatar
Stephen Hemminger committed
149
150
	int rate2quantum;	/* quant = rate / rate2quantum */
	psched_time_t now;	/* cached dequeue time */
151
	struct qdisc_watchdog watchdog;
Linus Torvalds's avatar
Linus Torvalds committed
152

Stephen Hemminger's avatar
Stephen Hemminger committed
153
154
155
156
157
	/* non shaped skbs; let them go directly thru */
	struct sk_buff_head direct_queue;
	int direct_qlen;	/* max qlen of above */

	long direct_pkts;
Linus Torvalds's avatar
Linus Torvalds committed
158
159
160
};

/* find class in global hash table using given handle */
Stephen Hemminger's avatar
Stephen Hemminger committed
161
static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
Linus Torvalds's avatar
Linus Torvalds committed
162
163
{
	struct htb_sched *q = qdisc_priv(sch);
164
	struct Qdisc_class_common *clc;
165

166
167
	clc = qdisc_class_find(&q->clhash, handle);
	if (clc == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
168
		return NULL;
169
	return container_of(clc, struct htb_class, common);
Linus Torvalds's avatar
Linus Torvalds committed
170
171
172
173
174
175
176
177
178
179
}

/**
 * htb_classify - classify a packet into class
 *
 * It returns NULL if the packet should be dropped or -1 if the packet
 * should be passed directly thru. In all other cases leaf class is returned.
 * We allow direct class selection by classid in priority. The we examine
 * filters in qdisc and in inner nodes (if higher filter points to the inner
 * node). If we end up with classid MAJOR:0 we enqueue the skb into special
180
 * internal fifo (direct). These packets then go directly thru. If we still
Linus Torvalds's avatar
Linus Torvalds committed
181
182
183
184
185
 * have no valid leaf we try to use MAJOR:default leaf. It still unsuccessfull
 * then finish and return direct queue.
 */
#define HTB_DIRECT (struct htb_class*)-1

Stephen Hemminger's avatar
Stephen Hemminger committed
186
187
static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
				      int *qerr)
Linus Torvalds's avatar
Linus Torvalds committed
188
189
190
191
192
193
194
195
196
197
198
{
	struct htb_sched *q = qdisc_priv(sch);
	struct htb_class *cl;
	struct tcf_result res;
	struct tcf_proto *tcf;
	int result;

	/* allow to select class by setting skb->priority to valid classid;
	   note that nfmark can be used too by attaching filter fw with no
	   rules in it */
	if (skb->priority == sch->handle)
Stephen Hemminger's avatar
Stephen Hemminger committed
199
200
		return HTB_DIRECT;	/* X:0 (direct flow) selected */
	if ((cl = htb_find(skb->priority, sch)) != NULL && cl->level == 0)
Linus Torvalds's avatar
Linus Torvalds committed
201
202
		return cl;

203
	*qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Linus Torvalds's avatar
Linus Torvalds committed
204
205
206
207
208
	tcf = q->filter_list;
	while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) {
#ifdef CONFIG_NET_CLS_ACT
		switch (result) {
		case TC_ACT_QUEUED:
Stephen Hemminger's avatar
Stephen Hemminger committed
209
		case TC_ACT_STOLEN:
210
			*qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
Linus Torvalds's avatar
Linus Torvalds committed
211
212
213
214
		case TC_ACT_SHOT:
			return NULL;
		}
#endif
Stephen Hemminger's avatar
Stephen Hemminger committed
215
		if ((cl = (void *)res.class) == NULL) {
Linus Torvalds's avatar
Linus Torvalds committed
216
			if (res.classid == sch->handle)
Stephen Hemminger's avatar
Stephen Hemminger committed
217
218
219
				return HTB_DIRECT;	/* X:0 (direct flow) */
			if ((cl = htb_find(res.classid, sch)) == NULL)
				break;	/* filter selected invalid classid */
Linus Torvalds's avatar
Linus Torvalds committed
220
221
		}
		if (!cl->level)
Stephen Hemminger's avatar
Stephen Hemminger committed
222
			return cl;	/* we hit leaf; return it */
Linus Torvalds's avatar
Linus Torvalds committed
223
224
225
226
227

		/* we have got inner class; apply inner filter chain */
		tcf = cl->filter_list;
	}
	/* classification failed; try to use default class */
Stephen Hemminger's avatar
Stephen Hemminger committed
228
	cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
Linus Torvalds's avatar
Linus Torvalds committed
229
	if (!cl || cl->level)
Stephen Hemminger's avatar
Stephen Hemminger committed
230
		return HTB_DIRECT;	/* bad default .. this is safe bet */
Linus Torvalds's avatar
Linus Torvalds committed
231
232
233
234
235
236
237
238
239
	return cl;
}

/**
 * htb_add_to_id_tree - adds class to the round robin list
 *
 * Routine adds class to the list (actually tree) sorted by classid.
 * Make sure that class is not already on such list for given prio.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
240
241
static void htb_add_to_id_tree(struct rb_root *root,
			       struct htb_class *cl, int prio)
Linus Torvalds's avatar
Linus Torvalds committed
242
243
{
	struct rb_node **p = &root->rb_node, *parent = NULL;
244

Linus Torvalds's avatar
Linus Torvalds committed
245
	while (*p) {
Stephen Hemminger's avatar
Stephen Hemminger committed
246
247
		struct htb_class *c;
		parent = *p;
Linus Torvalds's avatar
Linus Torvalds committed
248
		c = rb_entry(parent, struct htb_class, node[prio]);
249

250
		if (cl->common.classid > c->common.classid)
Linus Torvalds's avatar
Linus Torvalds committed
251
			p = &parent->rb_right;
Stephen Hemminger's avatar
Stephen Hemminger committed
252
		else
Linus Torvalds's avatar
Linus Torvalds committed
253
254
255
256
257
258
259
260
261
262
263
264
265
			p = &parent->rb_left;
	}
	rb_link_node(&cl->node[prio], parent, p);
	rb_insert_color(&cl->node[prio], root);
}

/**
 * htb_add_to_wait_tree - adds class to the event queue with delay
 *
 * The class is added to priority event queue to indicate that class will
 * change its mode in cl->pq_key microseconds. Make sure that class is not
 * already in the queue.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
266
267
static void htb_add_to_wait_tree(struct htb_sched *q,
				 struct htb_class *cl, long delay)
Linus Torvalds's avatar
Linus Torvalds committed
268
269
{
	struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
270

271
272
	cl->pq_key = q->now + delay;
	if (cl->pq_key == q->now)
Linus Torvalds's avatar
Linus Torvalds committed
273
274
275
		cl->pq_key++;

	/* update the nearest event cache */
276
	if (q->near_ev_cache[cl->level] > cl->pq_key)
Linus Torvalds's avatar
Linus Torvalds committed
277
		q->near_ev_cache[cl->level] = cl->pq_key;
Stephen Hemminger's avatar
Stephen Hemminger committed
278

Linus Torvalds's avatar
Linus Torvalds committed
279
	while (*p) {
Stephen Hemminger's avatar
Stephen Hemminger committed
280
281
		struct htb_class *c;
		parent = *p;
Linus Torvalds's avatar
Linus Torvalds committed
282
		c = rb_entry(parent, struct htb_class, pq_node);
283
		if (cl->pq_key >= c->pq_key)
Linus Torvalds's avatar
Linus Torvalds committed
284
			p = &parent->rb_right;
Stephen Hemminger's avatar
Stephen Hemminger committed
285
		else
Linus Torvalds's avatar
Linus Torvalds committed
286
287
288
289
290
291
292
293
294
295
296
297
			p = &parent->rb_left;
	}
	rb_link_node(&cl->pq_node, parent, p);
	rb_insert_color(&cl->pq_node, &q->wait_pq[cl->level]);
}

/**
 * htb_next_rb_node - finds next node in binary tree
 *
 * When we are past last key we return NULL.
 * Average complexity is 2 steps per call.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
298
static inline void htb_next_rb_node(struct rb_node **n)
Linus Torvalds's avatar
Linus Torvalds committed
299
300
301
302
303
304
305
306
307
308
{
	*n = rb_next(*n);
}

/**
 * htb_add_class_to_row - add class to its row
 *
 * The class is added to row at priorities marked in mask.
 * It does nothing if mask == 0.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
309
310
static inline void htb_add_class_to_row(struct htb_sched *q,
					struct htb_class *cl, int mask)
Linus Torvalds's avatar
Linus Torvalds committed
311
312
313
314
315
{
	q->row_mask[cl->level] |= mask;
	while (mask) {
		int prio = ffz(~mask);
		mask &= ~(1 << prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
316
		htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio);
Linus Torvalds's avatar
Linus Torvalds committed
317
318
319
	}
}

Stephen Hemminger's avatar
Stephen Hemminger committed
320
321
322
/* If this triggers, it is a bug in this code, but it need not be fatal */
static void htb_safe_rb_erase(struct rb_node *rb, struct rb_root *root)
{
323
	if (RB_EMPTY_NODE(rb)) {
Stephen Hemminger's avatar
Stephen Hemminger committed
324
325
326
327
328
329
330
331
		WARN_ON(1);
	} else {
		rb_erase(rb, root);
		RB_CLEAR_NODE(rb);
	}
}


Linus Torvalds's avatar
Linus Torvalds committed
332
333
334
335
336
337
/**
 * htb_remove_class_from_row - removes class from its row
 *
 * The class is removed from row at priorities marked in mask.
 * It does nothing if mask == 0.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
338
339
static inline void htb_remove_class_from_row(struct htb_sched *q,
						 struct htb_class *cl, int mask)
Linus Torvalds's avatar
Linus Torvalds committed
340
341
{
	int m = 0;
342

Linus Torvalds's avatar
Linus Torvalds committed
343
344
	while (mask) {
		int prio = ffz(~mask);
Stephen Hemminger's avatar
Stephen Hemminger committed
345

Linus Torvalds's avatar
Linus Torvalds committed
346
		mask &= ~(1 << prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
347
348
		if (q->ptr[cl->level][prio] == cl->node + prio)
			htb_next_rb_node(q->ptr[cl->level] + prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
349
350

		htb_safe_rb_erase(cl->node + prio, q->row[cl->level] + prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
351
		if (!q->row[cl->level][prio].rb_node)
Linus Torvalds's avatar
Linus Torvalds committed
352
353
354
355
356
357
358
359
360
			m |= 1 << prio;
	}
	q->row_mask[cl->level] &= ~m;
}

/**
 * htb_activate_prios - creates active classe's feed chain
 *
 * The class is connected to ancestors and/or appropriate rows
361
 * for priorities it is participating on. cl->cmode must be new
Linus Torvalds's avatar
Linus Torvalds committed
362
363
 * (activated) mode. It does nothing if cl->prio_activity == 0.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
364
static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds's avatar
Linus Torvalds committed
365
366
{
	struct htb_class *p = cl->parent;
Stephen Hemminger's avatar
Stephen Hemminger committed
367
	long m, mask = cl->prio_activity;
Linus Torvalds's avatar
Linus Torvalds committed
368
369

	while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger's avatar
Stephen Hemminger committed
370
371
		m = mask;
		while (m) {
Linus Torvalds's avatar
Linus Torvalds committed
372
373
			int prio = ffz(~m);
			m &= ~(1 << prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
374

Linus Torvalds's avatar
Linus Torvalds committed
375
376
377
378
			if (p->un.inner.feed[prio].rb_node)
				/* parent already has its feed in use so that
				   reset bit in mask as parent is already ok */
				mask &= ~(1 << prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
379
380

			htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
Linus Torvalds's avatar
Linus Torvalds committed
381
382
		}
		p->prio_activity |= mask;
Stephen Hemminger's avatar
Stephen Hemminger committed
383
384
		cl = p;
		p = cl->parent;
385

Linus Torvalds's avatar
Linus Torvalds committed
386
387
	}
	if (cl->cmode == HTB_CAN_SEND && mask)
Stephen Hemminger's avatar
Stephen Hemminger committed
388
		htb_add_class_to_row(q, cl, mask);
Linus Torvalds's avatar
Linus Torvalds committed
389
390
391
392
393
}

/**
 * htb_deactivate_prios - remove class from feed chain
 *
394
 * cl->cmode must represent old mode (before deactivation). It does
Linus Torvalds's avatar
Linus Torvalds committed
395
396
397
398
399
400
 * nothing if cl->prio_activity == 0. Class is removed from all feed
 * chains and rows.
 */
static void htb_deactivate_prios(struct htb_sched *q, struct htb_class *cl)
{
	struct htb_class *p = cl->parent;
Stephen Hemminger's avatar
Stephen Hemminger committed
401
	long m, mask = cl->prio_activity;
Linus Torvalds's avatar
Linus Torvalds committed
402
403

	while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger's avatar
Stephen Hemminger committed
404
405
		m = mask;
		mask = 0;
Linus Torvalds's avatar
Linus Torvalds committed
406
407
408
		while (m) {
			int prio = ffz(~m);
			m &= ~(1 << prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
409
410

			if (p->un.inner.ptr[prio] == cl->node + prio) {
Linus Torvalds's avatar
Linus Torvalds committed
411
412
413
				/* we are removing child which is pointed to from
				   parent feed - forget the pointer but remember
				   classid */
414
				p->un.inner.last_ptr_id[prio] = cl->common.classid;
Linus Torvalds's avatar
Linus Torvalds committed
415
416
				p->un.inner.ptr[prio] = NULL;
			}
Stephen Hemminger's avatar
Stephen Hemminger committed
417

Stephen Hemminger's avatar
Stephen Hemminger committed
418
			htb_safe_rb_erase(cl->node + prio, p->un.inner.feed + prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
419
420

			if (!p->un.inner.feed[prio].rb_node)
Linus Torvalds's avatar
Linus Torvalds committed
421
422
				mask |= 1 << prio;
		}
423

Linus Torvalds's avatar
Linus Torvalds committed
424
		p->prio_activity &= ~mask;
Stephen Hemminger's avatar
Stephen Hemminger committed
425
426
		cl = p;
		p = cl->parent;
427

Linus Torvalds's avatar
Linus Torvalds committed
428
	}
Stephen Hemminger's avatar
Stephen Hemminger committed
429
430
	if (cl->cmode == HTB_CAN_SEND && mask)
		htb_remove_class_from_row(q, cl, mask);
Linus Torvalds's avatar
Linus Torvalds committed
431
432
}

433
434
static inline long htb_lowater(const struct htb_class *cl)
{
435
436
437
438
	if (htb_hysteresis)
		return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
	else
		return 0;
439
440
441
}
static inline long htb_hiwater(const struct htb_class *cl)
{
442
443
444
445
	if (htb_hysteresis)
		return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
	else
		return 0;
446
}
447

448

Linus Torvalds's avatar
Linus Torvalds committed
449
450
451
452
453
/**
 * htb_class_mode - computes and returns current class mode
 *
 * It computes cl's mode at time cl->t_c+diff and returns it. If mode
 * is not HTB_CAN_SEND then cl->pq_key is updated to time difference
454
 * from now to time when cl will change its state.
Linus Torvalds's avatar
Linus Torvalds committed
455
 * Also it is worth to note that class mode doesn't change simply
456
 * at cl->{c,}tokens == 0 but there can rather be hysteresis of
Linus Torvalds's avatar
Linus Torvalds committed
457
458
459
 * 0 .. -cl->{c,}buffer range. It is meant to limit number of
 * mode transitions per time unit. The speed gain is about 1/6.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
460
461
static inline enum htb_cmode
htb_class_mode(struct htb_class *cl, long *diff)
Linus Torvalds's avatar
Linus Torvalds committed
462
{
Stephen Hemminger's avatar
Stephen Hemminger committed
463
	long toks;
Linus Torvalds's avatar
Linus Torvalds committed
464

Stephen Hemminger's avatar
Stephen Hemminger committed
465
466
467
468
	if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
		*diff = -toks;
		return HTB_CANT_SEND;
	}
469

Stephen Hemminger's avatar
Stephen Hemminger committed
470
471
	if ((toks = (cl->tokens + *diff)) >= htb_hiwater(cl))
		return HTB_CAN_SEND;
Linus Torvalds's avatar
Linus Torvalds committed
472

Stephen Hemminger's avatar
Stephen Hemminger committed
473
474
	*diff = -toks;
	return HTB_MAY_BORROW;
Linus Torvalds's avatar
Linus Torvalds committed
475
476
477
478
479
480
481
482
483
484
485
}

/**
 * htb_change_class_mode - changes classe's mode
 *
 * This should be the only way how to change classe's mode under normal
 * cirsumstances. Routine will update feed lists linkage, change mode
 * and add class to the wait event queue if appropriate. New mode should
 * be different from old one and cl->pq_key has to be valid if changing
 * to mode other than HTB_CAN_SEND (see htb_add_to_wait_tree).
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
486
static void
Linus Torvalds's avatar
Linus Torvalds committed
487
htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
Stephen Hemminger's avatar
Stephen Hemminger committed
488
489
{
	enum htb_cmode new_mode = htb_class_mode(cl, diff);
Linus Torvalds's avatar
Linus Torvalds committed
490
491

	if (new_mode == cl->cmode)
Stephen Hemminger's avatar
Stephen Hemminger committed
492
493
494
495
496
		return;

	if (cl->prio_activity) {	/* not necessary: speed optimization */
		if (cl->cmode != HTB_CANT_SEND)
			htb_deactivate_prios(q, cl);
Linus Torvalds's avatar
Linus Torvalds committed
497
		cl->cmode = new_mode;
Stephen Hemminger's avatar
Stephen Hemminger committed
498
499
500
		if (new_mode != HTB_CANT_SEND)
			htb_activate_prios(q, cl);
	} else
Linus Torvalds's avatar
Linus Torvalds committed
501
502
503
504
		cl->cmode = new_mode;
}

/**
505
 * htb_activate - inserts leaf cl into appropriate active feeds
Linus Torvalds's avatar
Linus Torvalds committed
506
507
508
509
510
 *
 * Routine learns (new) priority of leaf and activates feed chain
 * for the prio. It can be called on already active leaf safely.
 * It also adds leaf into droplist.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
511
static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds's avatar
Linus Torvalds committed
512
{
513
	WARN_ON(cl->level || !cl->un.leaf.q || !cl->un.leaf.q->q.qlen);
514

Linus Torvalds's avatar
Linus Torvalds committed
515
	if (!cl->prio_activity) {
516
		cl->prio_activity = 1 << cl->prio;
Stephen Hemminger's avatar
Stephen Hemminger committed
517
518
		htb_activate_prios(q, cl);
		list_add_tail(&cl->un.leaf.drop_list,
519
			      q->drops + cl->prio);
Linus Torvalds's avatar
Linus Torvalds committed
520
521
522
523
	}
}

/**
524
 * htb_deactivate - remove leaf cl from active feeds
Linus Torvalds's avatar
Linus Torvalds committed
525
526
527
528
 *
 * Make sure that leaf is active. In the other words it can't be called
 * with non-active leaf. It also removes class from the drop list.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
529
static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds's avatar
Linus Torvalds committed
530
{
531
	WARN_ON(!cl->prio_activity);
532

Stephen Hemminger's avatar
Stephen Hemminger committed
533
	htb_deactivate_prios(q, cl);
Linus Torvalds's avatar
Linus Torvalds committed
534
535
536
537
538
539
	cl->prio_activity = 0;
	list_del_init(&cl->un.leaf.drop_list);
}

static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
{
540
	int uninitialized_var(ret);
Stephen Hemminger's avatar
Stephen Hemminger committed
541
542
543
544
545
546
547
548
549
550
551
552
553
	struct htb_sched *q = qdisc_priv(sch);
	struct htb_class *cl = htb_classify(skb, sch, &ret);

	if (cl == HTB_DIRECT) {
		/* enqueue to helper queue */
		if (q->direct_queue.qlen < q->direct_qlen) {
			__skb_queue_tail(&q->direct_queue, skb);
			q->direct_pkts++;
		} else {
			kfree_skb(skb);
			sch->qstats.drops++;
			return NET_XMIT_DROP;
		}
Linus Torvalds's avatar
Linus Torvalds committed
554
#ifdef CONFIG_NET_CLS_ACT
Stephen Hemminger's avatar
Stephen Hemminger committed
555
	} else if (!cl) {
556
		if (ret & __NET_XMIT_BYPASS)
Stephen Hemminger's avatar
Stephen Hemminger committed
557
558
559
			sch->qstats.drops++;
		kfree_skb(skb);
		return ret;
Linus Torvalds's avatar
Linus Torvalds committed
560
#endif
561
562
563
564
565
	} else if ((ret = qdisc_enqueue(skb, cl->un.leaf.q)) != NET_XMIT_SUCCESS) {
		if (net_xmit_drop_count(ret)) {
			sch->qstats.drops++;
			cl->qstats.drops++;
		}
566
		return ret;
Stephen Hemminger's avatar
Stephen Hemminger committed
567
	} else {
568
569
		cl->bstats.packets +=
			skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
570
		cl->bstats.bytes += qdisc_pkt_len(skb);
Stephen Hemminger's avatar
Stephen Hemminger committed
571
572
573
574
		htb_activate(q, cl);
	}

	sch->q.qlen++;
575
	sch->bstats.packets += skb_is_gso(skb)?skb_shinfo(skb)->gso_segs:1;
576
	sch->bstats.bytes += qdisc_pkt_len(skb);
Stephen Hemminger's avatar
Stephen Hemminger committed
577
	return NET_XMIT_SUCCESS;
Linus Torvalds's avatar
Linus Torvalds committed
578
579
}

580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
static inline void htb_accnt_tokens(struct htb_class *cl, int bytes, long diff)
{
	long toks = diff + cl->tokens;

	if (toks > cl->buffer)
		toks = cl->buffer;
	toks -= (long) qdisc_l2t(cl->rate, bytes);
	if (toks <= -cl->mbuffer)
		toks = 1 - cl->mbuffer;

	cl->tokens = toks;
}

static inline void htb_accnt_ctokens(struct htb_class *cl, int bytes, long diff)
{
	long toks = diff + cl->ctokens;

	if (toks > cl->cbuffer)
		toks = cl->cbuffer;
	toks -= (long) qdisc_l2t(cl->ceil, bytes);
	if (toks <= -cl->mbuffer)
		toks = 1 - cl->mbuffer;

	cl->ctokens = toks;
}

Linus Torvalds's avatar
Linus Torvalds committed
606
607
608
609
610
611
612
613
614
615
616
/**
 * htb_charge_class - charges amount "bytes" to leaf and ancestors
 *
 * Routine assumes that packet "bytes" long was dequeued from leaf cl
 * borrowing from "level". It accounts bytes to ceil leaky bucket for
 * leaf and all ancestors and to rate bucket for ancestors at levels
 * "level" and higher. It also handles possible change of mode resulting
 * from the update. Note that mode can also increase here (MAY_BORROW to
 * CAN_SEND) because we can use more precise clock that event queue here.
 * In such case we remove class from event queue first.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
617
static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
618
			     int level, struct sk_buff *skb)
Stephen Hemminger's avatar
Stephen Hemminger committed
619
{
620
	int bytes = qdisc_pkt_len(skb);
Linus Torvalds's avatar
Linus Torvalds committed
621
	enum htb_cmode old_mode;
622
	long diff;
Linus Torvalds's avatar
Linus Torvalds committed
623
624

	while (cl) {
625
		diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
Linus Torvalds's avatar
Linus Torvalds committed
626
		if (cl->level >= level) {
Stephen Hemminger's avatar
Stephen Hemminger committed
627
628
			if (cl->level == level)
				cl->xstats.lends++;
629
			htb_accnt_tokens(cl, bytes, diff);
Linus Torvalds's avatar
Linus Torvalds committed
630
631
		} else {
			cl->xstats.borrows++;
Stephen Hemminger's avatar
Stephen Hemminger committed
632
			cl->tokens += diff;	/* we moved t_c; update tokens */
Linus Torvalds's avatar
Linus Torvalds committed
633
		}
634
		htb_accnt_ctokens(cl, bytes, diff);
Linus Torvalds's avatar
Linus Torvalds committed
635
636
		cl->t_c = q->now;

Stephen Hemminger's avatar
Stephen Hemminger committed
637
638
639
		old_mode = cl->cmode;
		diff = 0;
		htb_change_class_mode(q, cl, &diff);
Linus Torvalds's avatar
Linus Torvalds committed
640
641
		if (old_mode != cl->cmode) {
			if (old_mode != HTB_CAN_SEND)
Stephen Hemminger's avatar
Stephen Hemminger committed
642
				htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
Linus Torvalds's avatar
Linus Torvalds committed
643
			if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger's avatar
Stephen Hemminger committed
644
				htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds's avatar
Linus Torvalds committed
645
646
647
648
649
		}

		/* update byte stats except for leaves which are already updated */
		if (cl->level) {
			cl->bstats.bytes += bytes;
650
651
			cl->bstats.packets += skb_is_gso(skb)?
					skb_shinfo(skb)->gso_segs:1;
Linus Torvalds's avatar
Linus Torvalds committed
652
653
654
655
656
657
658
659
		}
		cl = cl->parent;
	}
}

/**
 * htb_do_events - make mode changes to classes at the level
 *
660
 * Scans event queue for pending events and applies them. Returns time of
Linus Torvalds's avatar
Linus Torvalds committed
661
 * next pending event (0 for no event in pq).
662
 * Note: Applied are events whose have cl->pq_key <= q->now.
Linus Torvalds's avatar
Linus Torvalds committed
663
 */
664
static psched_time_t htb_do_events(struct htb_sched *q, int level)
Linus Torvalds's avatar
Linus Torvalds committed
665
{
666
667
668
669
670
	/* don't run for longer than 2 jiffies; 2 is used instead of
	   1 to simplify things when jiffy is going to be incremented
	   too soon */
	unsigned long stop_at = jiffies + 2;
	while (time_before(jiffies, stop_at)) {
Linus Torvalds's avatar
Linus Torvalds committed
671
672
		struct htb_class *cl;
		long diff;
673
674
		struct rb_node *p = rb_first(&q->wait_pq[level]);

Stephen Hemminger's avatar
Stephen Hemminger committed
675
676
		if (!p)
			return 0;
Linus Torvalds's avatar
Linus Torvalds committed
677
678

		cl = rb_entry(p, struct htb_class, pq_node);
679
680
681
		if (cl->pq_key > q->now)
			return cl->pq_key;

Stephen Hemminger's avatar
Stephen Hemminger committed
682
		htb_safe_rb_erase(p, q->wait_pq + level);
683
		diff = psched_tdiff_bounded(q->now, cl->t_c, cl->mbuffer);
Stephen Hemminger's avatar
Stephen Hemminger committed
684
		htb_change_class_mode(q, cl, &diff);
Linus Torvalds's avatar
Linus Torvalds committed
685
		if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger's avatar
Stephen Hemminger committed
686
			htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds's avatar
Linus Torvalds committed
687
	}
688
689
	/* too much load - let's continue on next jiffie */
	return q->now + PSCHED_TICKS_PER_SEC / HZ;
Linus Torvalds's avatar
Linus Torvalds committed
690
691
692
693
}

/* Returns class->node+prio from id-tree where classe's id is >= id. NULL
   is no such one exists. */
Stephen Hemminger's avatar
Stephen Hemminger committed
694
695
static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
					      u32 id)
Linus Torvalds's avatar
Linus Torvalds committed
696
697
698
{
	struct rb_node *r = NULL;
	while (n) {
Stephen Hemminger's avatar
Stephen Hemminger committed
699
700
701
		struct htb_class *cl =
		    rb_entry(n, struct htb_class, node[prio]);

702
		if (id > cl->common.classid) {
Linus Torvalds's avatar
Linus Torvalds committed
703
			n = n->rb_right;
704
		} else if (id < cl->common.classid) {
Linus Torvalds's avatar
Linus Torvalds committed
705
706
			r = n;
			n = n->rb_left;
707
708
		} else {
			return n;
Linus Torvalds's avatar
Linus Torvalds committed
709
710
711
712
713
714
715
716
717
718
		}
	}
	return r;
}

/**
 * htb_lookup_leaf - returns next leaf class in DRR order
 *
 * Find leaf where current feed pointers points to.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
719
720
static struct htb_class *htb_lookup_leaf(struct rb_root *tree, int prio,
					 struct rb_node **pptr, u32 * pid)
Linus Torvalds's avatar
Linus Torvalds committed
721
722
723
724
725
726
{
	int i;
	struct {
		struct rb_node *root;
		struct rb_node **pptr;
		u32 *pid;
Stephen Hemminger's avatar
Stephen Hemminger committed
727
728
	} stk[TC_HTB_MAXDEPTH], *sp = stk;

729
	WARN_ON(!tree->rb_node);
Linus Torvalds's avatar
Linus Torvalds committed
730
731
732
733
734
	sp->root = tree->rb_node;
	sp->pptr = pptr;
	sp->pid = pid;

	for (i = 0; i < 65535; i++) {
Stephen Hemminger's avatar
Stephen Hemminger committed
735
		if (!*sp->pptr && *sp->pid) {
736
			/* ptr was invalidated but id is valid - try to recover
Linus Torvalds's avatar
Linus Torvalds committed
737
			   the original or next ptr */
Stephen Hemminger's avatar
Stephen Hemminger committed
738
739
			*sp->pptr =
			    htb_id_find_next_upper(prio, sp->root, *sp->pid);
Linus Torvalds's avatar
Linus Torvalds committed
740
		}
Stephen Hemminger's avatar
Stephen Hemminger committed
741
742
743
		*sp->pid = 0;	/* ptr is valid now so that remove this hint as it
				   can become out of date quickly */
		if (!*sp->pptr) {	/* we are at right end; rewind & go up */
Linus Torvalds's avatar
Linus Torvalds committed
744
			*sp->pptr = sp->root;
Stephen Hemminger's avatar
Stephen Hemminger committed
745
			while ((*sp->pptr)->rb_left)
Linus Torvalds's avatar
Linus Torvalds committed
746
747
748
				*sp->pptr = (*sp->pptr)->rb_left;
			if (sp > stk) {
				sp--;
749
				WARN_ON(!*sp->pptr);
Stephen Hemminger's avatar
Stephen Hemminger committed
750
751
752
				if (!*sp->pptr)
					return NULL;
				htb_next_rb_node(sp->pptr);
Linus Torvalds's avatar
Linus Torvalds committed
753
754
755
			}
		} else {
			struct htb_class *cl;
Stephen Hemminger's avatar
Stephen Hemminger committed
756
757
			cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
			if (!cl->level)
Linus Torvalds's avatar
Linus Torvalds committed
758
759
				return cl;
			(++sp)->root = cl->un.inner.feed[prio].rb_node;
Stephen Hemminger's avatar
Stephen Hemminger committed
760
761
			sp->pptr = cl->un.inner.ptr + prio;
			sp->pid = cl->un.inner.last_ptr_id + prio;
Linus Torvalds's avatar
Linus Torvalds committed
762
763
		}
	}
764
	WARN_ON(1);
Linus Torvalds's avatar
Linus Torvalds committed
765
766
767
768
769
	return NULL;
}

/* dequeues packet at given priority and level; call only if
   you are sure that there is active class at prio/level */
Stephen Hemminger's avatar
Stephen Hemminger committed
770
771
static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
					int level)
Linus Torvalds's avatar
Linus Torvalds committed
772
773
{
	struct sk_buff *skb = NULL;
Stephen Hemminger's avatar
Stephen Hemminger committed
774
	struct htb_class *cl, *start;
Linus Torvalds's avatar
Linus Torvalds committed
775
	/* look initial class up in the row */
Stephen Hemminger's avatar
Stephen Hemminger committed
776
777
778
779
	start = cl = htb_lookup_leaf(q->row[level] + prio, prio,
				     q->ptr[level] + prio,
				     q->last_ptr_id[level] + prio);

Linus Torvalds's avatar
Linus Torvalds committed
780
781
	do {
next:
782
		WARN_ON(!cl);
Stephen Hemminger's avatar
Stephen Hemminger committed
783
784
		if (!cl)
			return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
785
786
787

		/* class can be empty - it is unlikely but can be true if leaf
		   qdisc drops packets in enqueue routine or if someone used
788
		   graft operation on the leaf since last dequeue;
Linus Torvalds's avatar
Linus Torvalds committed
789
790
791
		   simply deactivate and skip such class */
		if (unlikely(cl->un.leaf.q->q.qlen == 0)) {
			struct htb_class *next;
Stephen Hemminger's avatar
Stephen Hemminger committed
792
			htb_deactivate(q, cl);
Linus Torvalds's avatar
Linus Torvalds committed
793
794
795

			/* row/level might become empty */
			if ((q->row_mask[level] & (1 << prio)) == 0)
Stephen Hemminger's avatar
Stephen Hemminger committed
796
				return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
797

Stephen Hemminger's avatar
Stephen Hemminger committed
798
799
800
801
802
			next = htb_lookup_leaf(q->row[level] + prio,
					       prio, q->ptr[level] + prio,
					       q->last_ptr_id[level] + prio);

			if (cl == start)	/* fix start if we just deleted it */
Linus Torvalds's avatar
Linus Torvalds committed
803
804
805
806
				start = next;
			cl = next;
			goto next;
		}
Stephen Hemminger's avatar
Stephen Hemminger committed
807
808
809

		skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
		if (likely(skb != NULL))
Linus Torvalds's avatar
Linus Torvalds committed
810
811
			break;
		if (!cl->warned) {
Stephen Hemminger's avatar
Stephen Hemminger committed
812
813
			printk(KERN_WARNING
			       "htb: class %X isn't work conserving ?!\n",
814
			       cl->common.classid);
Linus Torvalds's avatar
Linus Torvalds committed
815
816
			cl->warned = 1;
		}
817

Stephen Hemminger's avatar
Stephen Hemminger committed
818
819
820
821
822
		htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
				  ptr[0]) + prio);
		cl = htb_lookup_leaf(q->row[level] + prio, prio,
				     q->ptr[level] + prio,
				     q->last_ptr_id[level] + prio);
Linus Torvalds's avatar
Linus Torvalds committed
823
824
825
826

	} while (cl != start);

	if (likely(skb != NULL)) {
827
828
		cl->un.leaf.deficit[level] -= qdisc_pkt_len(skb);
		if (cl->un.leaf.deficit[level] < 0) {
829
			cl->un.leaf.deficit[level] += cl->quantum;
Stephen Hemminger's avatar
Stephen Hemminger committed
830
831
			htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
					  ptr[0]) + prio);
Linus Torvalds's avatar
Linus Torvalds committed
832
833
834
835
		}
		/* this used to be after charge_class but this constelation
		   gives us slightly better performance */
		if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger's avatar
Stephen Hemminger committed
836
			htb_deactivate(q, cl);
837
		htb_charge_class(q, cl, level, skb);
Linus Torvalds's avatar
Linus Torvalds committed
838
839
840
841
842
843
844
845
846
	}
	return skb;
}

static struct sk_buff *htb_dequeue(struct Qdisc *sch)
{
	struct sk_buff *skb = NULL;
	struct htb_sched *q = qdisc_priv(sch);
	int level;
847
	psched_time_t next_event;
Linus Torvalds's avatar
Linus Torvalds committed
848
849

	/* try to dequeue direct packets as high prio (!) to minimize cpu work */
Stephen Hemminger's avatar
Stephen Hemminger committed
850
851
	skb = __skb_dequeue(&q->direct_queue);
	if (skb != NULL) {
Linus Torvalds's avatar
Linus Torvalds committed
852
853
854
855
856
		sch->flags &= ~TCQ_F_THROTTLED;
		sch->q.qlen--;
		return skb;
	}

Stephen Hemminger's avatar
Stephen Hemminger committed
857
858
	if (!sch->q.qlen)
		goto fin;
859
	q->now = psched_get_time();
Linus Torvalds's avatar
Linus Torvalds committed
860

861
	next_event = q->now + 5 * PSCHED_TICKS_PER_SEC;
862

Linus Torvalds's avatar
Linus Torvalds committed
863
864
865
	for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
		/* common case optimization - skip event handler quickly */
		int m;
866
867
868
869
		psched_time_t event;

		if (q->now >= q->near_ev_cache[level]) {
			event = htb_do_events(q, level);
870
871
872
			if (!event)
				event = q->now + PSCHED_TICKS_PER_SEC;
			q->near_ev_cache[level] = event;
Linus Torvalds's avatar
Linus Torvalds committed
873
		} else
874
875
876
877
			event = q->near_ev_cache[level];

		if (event && next_event > event)
			next_event = event;
Stephen Hemminger's avatar
Stephen Hemminger committed
878

Linus Torvalds's avatar
Linus Torvalds committed
879
880
		m = ~q->row_mask[level];
		while (m != (int)(-1)) {
Stephen Hemminger's avatar
Stephen Hemminger committed
881
			int prio = ffz(m);
Linus Torvalds's avatar
Linus Torvalds committed
882
			m |= 1 << prio;
Stephen Hemminger's avatar
Stephen Hemminger committed
883
			skb = htb_dequeue_tree(q, prio, level);
Linus Torvalds's avatar
Linus Torvalds committed
884
885
886
887
888
889
890
			if (likely(skb != NULL)) {
				sch->q.qlen--;
				sch->flags &= ~TCQ_F_THROTTLED;
				goto fin;
			}
		}
	}
891
892
	sch->qstats.overlimits++;
	qdisc_watchdog_schedule(&q->watchdog, next_event);
Linus Torvalds's avatar
Linus Torvalds committed
893
894
895
896
897
fin:
	return skb;
}

/* try to drop from each class (by prio) until one succeed */
Stephen Hemminger's avatar
Stephen Hemminger committed
898
static unsigned int htb_drop(struct Qdisc *sch)
Linus Torvalds's avatar
Linus Torvalds committed
899
900
901
902
903
904
{
	struct htb_sched *q = qdisc_priv(sch);
	int prio;

	for (prio = TC_HTB_NUMPRIO - 1; prio >= 0; prio--) {
		struct list_head *p;
Stephen Hemminger's avatar
Stephen Hemminger committed
905
		list_for_each(p, q->drops + prio) {
Linus Torvalds's avatar
Linus Torvalds committed
906
907
908
			struct htb_class *cl = list_entry(p, struct htb_class,
							  un.leaf.drop_list);
			unsigned int len;
Stephen Hemminger's avatar
Stephen Hemminger committed
909
910
			if (cl->un.leaf.q->ops->drop &&
			    (len = cl->un.leaf.q->ops->drop(cl->un.leaf.q))) {
Linus Torvalds's avatar
Linus Torvalds committed
911
912
				sch->q.qlen--;
				if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger's avatar
Stephen Hemminger committed
913
					htb_deactivate(q, cl);
Linus Torvalds's avatar
Linus Torvalds committed
914
915
916
917
918
919
920
921
922
				return len;
			}
		}
	}
	return 0;
}

/* reset all classes */
/* always caled under BH & queue lock */
Stephen Hemminger's avatar
Stephen Hemminger committed
923
static void htb_reset(struct Qdisc *sch)
Linus Torvalds's avatar
Linus Torvalds committed
924
925
{
	struct htb_sched *q = qdisc_priv(sch);
926
927
928
	struct htb_class *cl;
	struct hlist_node *n;
	unsigned int i;
929

930
931
	for (i = 0; i < q->clhash.hashsize; i++) {
		hlist_for_each_entry(cl, n, &q->clhash.hash[i], common.hnode) {
Linus Torvalds's avatar
Linus Torvalds committed
932
			if (cl->level)
Stephen Hemminger's avatar
Stephen Hemminger committed
933
				memset(&cl->un.inner, 0, sizeof(cl->un.inner));
Linus Torvalds's avatar
Linus Torvalds committed
934
			else {
Stephen Hemminger's avatar
Stephen Hemminger committed
935
				if (cl->un.leaf.q)
Linus Torvalds's avatar
Linus Torvalds committed
936
937
938
939
940
941
942
943
					qdisc_reset(cl->un.leaf.q);
				INIT_LIST_HEAD(&cl->un.leaf.drop_list);
			}
			cl->prio_activity = 0;
			cl->cmode = HTB_CAN_SEND;

		}
	}
944
	qdisc_watchdog_cancel(&q->watchdog);
Linus Torvalds's avatar
Linus Torvalds committed
945
946
	__skb_queue_purge(&q->direct_queue);
	sch->q.qlen = 0;
Stephen Hemminger's avatar
Stephen Hemminger committed
947
948
949
950
	memset(q->row, 0, sizeof(q->row));
	memset(q->row_mask, 0, sizeof(q->row_mask));
	memset(q->wait_pq, 0, sizeof(q->wait_pq));
	memset(q->ptr, 0, sizeof(q->ptr));
Linus Torvalds's avatar
Linus Torvalds committed
951
	for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger's avatar
Stephen Hemminger committed
952
		INIT_LIST_HEAD(q->drops + i);
Linus Torvalds's avatar
Linus Torvalds committed
953
954
}

955
956
957
958
959
960
961
static const struct nla_policy htb_policy[TCA_HTB_MAX + 1] = {
	[TCA_HTB_PARMS]	= { .len = sizeof(struct tc_htb_opt) },
	[TCA_HTB_INIT]	= { .len = sizeof(struct tc_htb_glob) },
	[TCA_HTB_CTAB]	= { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
	[TCA_HTB_RTAB]	= { .type = NLA_BINARY, .len = TC_RTAB_SIZE },
};

962
static int htb_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds's avatar
Linus Torvalds committed
963
964
{
	struct htb_sched *q = qdisc_priv(sch);
965
	struct nlattr *tb[TCA_HTB_INIT + 1];
Linus Torvalds's avatar
Linus Torvalds committed
966
	struct tc_htb_glob *gopt;
967
	int err;
Linus Torvalds's avatar
Linus Torvalds committed
968
	int i;
969
970
971
972

	if (!opt)
		return -EINVAL;

973
	err = nla_parse_nested(tb, TCA_HTB_INIT, opt, htb_policy);
974
975
976
	if (err < 0)
		return err;

977
	if (tb[TCA_HTB_INIT] == NULL) {
Linus Torvalds's avatar
Linus Torvalds committed
978
979
980
		printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n");
		return -EINVAL;
	}
981
	gopt = nla_data(tb[TCA_HTB_INIT]);
Linus Torvalds's avatar
Linus Torvalds committed
982
	if (gopt->version != HTB_VER >> 16) {
Stephen Hemminger's avatar
Stephen Hemminger committed
983
984
985
		printk(KERN_ERR
		       "HTB: need tc/htb version %d (minor is %d), you have %d\n",
		       HTB_VER >> 16, HTB_VER & 0xffff, gopt->version);
Linus Torvalds's avatar
Linus Torvalds committed
986
987
988
		return -EINVAL;
	}

989
990
991
	err = qdisc_class_hash_init(&q->clhash);
	if (err < 0)
		return err;
Linus Torvalds's avatar
Linus Torvalds committed
992
	for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger's avatar
Stephen Hemminger committed
993
		INIT_LIST_HEAD(q->drops + i);
Linus Torvalds's avatar
Linus Torvalds committed
994

995
	qdisc_watchdog_init(&q->watchdog, sch);
Linus Torvalds's avatar
Linus Torvalds committed
996
997
	skb_queue_head_init(&q->direct_queue);

998
	q->direct_qlen = qdisc_dev(sch)->tx_queue_len;
Stephen Hemminger's avatar
Stephen Hemminger committed
999
	if (q->direct_qlen < 2)	/* some devices have zero tx_queue_len */
Linus Torvalds's avatar
Linus Torvalds committed
1000
		q->direct_qlen = 2;
For faster browsing, not all history is shown. View entire blame