sch_htb.c 44.6 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
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 * 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
 *		Ondrej Kraus, <krauso@barr.cz> 
 *			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.
 *
 * $Id: sch_htb.c,v 1.25 2003/12/07 11:08:25 devik Exp devik $
 */
#include <linux/module.h>
#include <asm/uaccess.h>
#include <asm/system.h>
#include <linux/bitops.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/sched.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/in.h>
#include <linux/errno.h>
#include <linux/interrupt.h>
#include <linux/if_ether.h>
#include <linux/inet.h>
#include <linux/netdevice.h>
#include <linux/etherdevice.h>
#include <linux/notifier.h>
#include <net/ip.h>
#include <net/route.h>
#include <linux/skbuff.h>
#include <linux/list.h>
#include <linux/compiler.h>
#include <net/sock.h>
#include <net/pkt_sched.h>
#include <linux/rbtree.h>

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

    Levels:
    Each class is assigned level. Leaf has ALWAYS level 0 and root 
    classes have level TC_HTB_MAXDEPTH-1. Interior nodes has level
    one less than their parent.
*/

Stephen Hemminger's avatar
Stephen Hemminger committed
71
72
73
74
75
#define HTB_HSIZE 16		/* classid hash size */
#define HTB_EWMAC 2		/* rate average over HTB_EWMAC*HTB_HSIZE sec */
#define HTB_RATECM 1		/* whether to use rate computer */
#define HTB_HYSTERESIS 1	/* whether to use mode hysteresis for speedup */
#define HTB_VER 0x30011		/* major must be matched with number suplied by TC as version */
Linus Torvalds's avatar
Linus Torvalds committed
76
77
78
79
80
81
82

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

/* used internaly to keep status of single class */
enum htb_cmode {
Stephen Hemminger's avatar
Stephen Hemminger committed
83
84
85
	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
86
87
88
};

/* interior & leaf nodes; props specific to leaves are marked L: */
Stephen Hemminger's avatar
Stephen Hemminger committed
89
90
91
92
93
94
95
96
struct htb_class {
	/* general class parameters */
	u32 classid;
	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
97
98

#ifdef HTB_RATECM
Stephen Hemminger's avatar
Stephen Hemminger committed
99
100
101
	/* rate measurement counters */
	unsigned long rate_bytes, sum_bytes;
	unsigned long rate_packets, sum_packets;
Linus Torvalds's avatar
Linus Torvalds committed
102
103
#endif

Stephen Hemminger's avatar
Stephen Hemminger committed
104
105
106
	/* topology */
	int level;		/* our level (see above) */
	struct htb_class *parent;	/* parent class */
107
	struct hlist_node hlist;	/* classid hash list item */
Stephen Hemminger's avatar
Stephen Hemminger committed
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
	struct list_head sibling;	/* sibling list item */
	struct list_head children;	/* children list */

	union {
		struct htb_class_leaf {
			struct Qdisc *q;
			int prio;
			int aprio;
			int quantum;
			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 */
	unsigned long pq_key;	/* the same type as jiffies global */

	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 */
150
151
152
153

	int prio;		/* For parent to leaf return possible here */
	int quantum;		/* we do backup. Finally full replacement  */
				/* of un.leaf originals should be done. */
Linus Torvalds's avatar
Linus Torvalds committed
154
155
156
};

/* TODO: maybe compute rate when size is too large .. or drop ? */
Stephen Hemminger's avatar
Stephen Hemminger committed
157
158
159
160
161
162
163
164
165
static inline long L2T(struct htb_class *cl, struct qdisc_rate_table *rate,
			   int size)
{
	int slot = size >> rate->rate.cell_log;
	if (slot > 255) {
		cl->xstats.giants++;
		slot = 255;
	}
	return rate->data[slot];
Linus Torvalds's avatar
Linus Torvalds committed
166
167
}

Stephen Hemminger's avatar
Stephen Hemminger committed
168
169
struct htb_sched {
	struct list_head root;	/* root classes list */
170
171
	struct hlist_head hash[HTB_HSIZE];	/* hashed by classid */
	struct list_head drops[TC_HTB_NUMPRIO];/* active leaves (for drops) */
Stephen Hemminger's avatar
Stephen Hemminger committed
172
173
174
175
176
177

	/* 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
178

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

Stephen Hemminger's avatar
Stephen Hemminger committed
182
183
	/* time of nearest event per level (row) */
	unsigned long near_ev_cache[TC_HTB_MAXDEPTH];
Linus Torvalds's avatar
Linus Torvalds committed
184

Stephen Hemminger's avatar
Stephen Hemminger committed
185
186
	/* cached value of jiffies in dequeue */
	unsigned long jiffies;
Linus Torvalds's avatar
Linus Torvalds committed
187

Stephen Hemminger's avatar
Stephen Hemminger committed
188
189
	/* whether we hit non-work conserving class during this dequeue; we use */
	int nwc_hit;		/* this to disable mindelay complaint in dequeue */
Linus Torvalds's avatar
Linus Torvalds committed
190

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

Stephen Hemminger's avatar
Stephen Hemminger committed
193
194
195
	/* filters for qdisc itself */
	struct tcf_proto *filter_list;
	int filter_cnt;
Linus Torvalds's avatar
Linus Torvalds committed
196

Stephen Hemminger's avatar
Stephen Hemminger committed
197
198
199
	int rate2quantum;	/* quant = rate / rate2quantum */
	psched_time_t now;	/* cached dequeue time */
	struct timer_list timer;	/* send delay timer */
Linus Torvalds's avatar
Linus Torvalds committed
200
#ifdef HTB_RATECM
Stephen Hemminger's avatar
Stephen Hemminger committed
201
202
	struct timer_list rttim;	/* rate computer timer */
	int recmp_bucket;	/* which hash bucket to recompute next */
Linus Torvalds's avatar
Linus Torvalds committed
203
204
#endif

Stephen Hemminger's avatar
Stephen Hemminger committed
205
206
207
208
209
	/* 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
210
211
212
};

/* compute hash of size HTB_HSIZE for given handle */
Stephen Hemminger's avatar
Stephen Hemminger committed
213
static inline int htb_hash(u32 h)
Linus Torvalds's avatar
Linus Torvalds committed
214
215
{
#if HTB_HSIZE != 16
Stephen Hemminger's avatar
Stephen Hemminger committed
216
#error "Declare new hash for your HTB_HSIZE"
Linus Torvalds's avatar
Linus Torvalds committed
217
#endif
Stephen Hemminger's avatar
Stephen Hemminger committed
218
219
220
	h ^= h >> 8;		/* stolen from cbq_hash */
	h ^= h >> 4;
	return h & 0xf;
Linus Torvalds's avatar
Linus Torvalds committed
221
222
223
}

/* find class in global hash table using given handle */
Stephen Hemminger's avatar
Stephen Hemminger committed
224
static inline struct htb_class *htb_find(u32 handle, struct Qdisc *sch)
Linus Torvalds's avatar
Linus Torvalds committed
225
226
{
	struct htb_sched *q = qdisc_priv(sch);
227
228
229
	struct hlist_node *p;
	struct htb_class *cl;

Stephen Hemminger's avatar
Stephen Hemminger committed
230
	if (TC_H_MAJ(handle) != sch->handle)
Linus Torvalds's avatar
Linus Torvalds committed
231
		return NULL;
Stephen Hemminger's avatar
Stephen Hemminger committed
232

233
	hlist_for_each_entry(cl, p, q->hash + htb_hash(handle), hlist) {
Linus Torvalds's avatar
Linus Torvalds committed
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
		if (cl->classid == handle)
			return cl;
	}
	return NULL;
}

/**
 * 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
 * internal fifo (direct). These packets then go directly thru. If we still 
 * 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
static inline u32 htb_classid(struct htb_class *cl)
{
	return (cl && cl != HTB_DIRECT) ? cl->classid : TC_H_UNSPEC;
}

Stephen Hemminger's avatar
Stephen Hemminger committed
258
259
static struct htb_class *htb_classify(struct sk_buff *skb, struct Qdisc *sch,
				      int *qerr)
Linus Torvalds's avatar
Linus Torvalds committed
260
261
262
263
264
265
266
267
268
269
270
{
	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
271
272
		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
273
274
		return cl;

275
	*qerr = NET_XMIT_BYPASS;
Linus Torvalds's avatar
Linus Torvalds committed
276
277
278
279
280
	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
281
		case TC_ACT_STOLEN:
Linus Torvalds's avatar
Linus Torvalds committed
282
283
284
285
286
287
288
289
			*qerr = NET_XMIT_SUCCESS;
		case TC_ACT_SHOT:
			return NULL;
		}
#elif defined(CONFIG_NET_CLS_POLICE)
		if (result == TC_POLICE_SHOT)
			return HTB_DIRECT;
#endif
Stephen Hemminger's avatar
Stephen Hemminger committed
290
		if ((cl = (void *)res.class) == NULL) {
Linus Torvalds's avatar
Linus Torvalds committed
291
			if (res.classid == sch->handle)
Stephen Hemminger's avatar
Stephen Hemminger committed
292
293
294
				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
295
296
		}
		if (!cl->level)
Stephen Hemminger's avatar
Stephen Hemminger committed
297
			return cl;	/* we hit leaf; return it */
Linus Torvalds's avatar
Linus Torvalds committed
298
299
300
301
302

		/* 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
303
	cl = htb_find(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch);
Linus Torvalds's avatar
Linus Torvalds committed
304
	if (!cl || cl->level)
Stephen Hemminger's avatar
Stephen Hemminger committed
305
		return HTB_DIRECT;	/* bad default .. this is safe bet */
Linus Torvalds's avatar
Linus Torvalds committed
306
307
308
309
310
311
312
313
314
	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
315
316
static void htb_add_to_id_tree(struct rb_root *root,
			       struct htb_class *cl, int prio)
Linus Torvalds's avatar
Linus Torvalds committed
317
318
{
	struct rb_node **p = &root->rb_node, *parent = NULL;
319

Linus Torvalds's avatar
Linus Torvalds committed
320
	while (*p) {
Stephen Hemminger's avatar
Stephen Hemminger committed
321
322
		struct htb_class *c;
		parent = *p;
Linus Torvalds's avatar
Linus Torvalds committed
323
		c = rb_entry(parent, struct htb_class, node[prio]);
324

Linus Torvalds's avatar
Linus Torvalds committed
325
326
		if (cl->classid > c->classid)
			p = &parent->rb_right;
Stephen Hemminger's avatar
Stephen Hemminger committed
327
		else
Linus Torvalds's avatar
Linus Torvalds committed
328
329
330
331
332
333
334
335
336
337
338
339
340
			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
341
342
static void htb_add_to_wait_tree(struct htb_sched *q,
				 struct htb_class *cl, long delay)
Linus Torvalds's avatar
Linus Torvalds committed
343
344
{
	struct rb_node **p = &q->wait_pq[cl->level].rb_node, *parent = NULL;
345

Linus Torvalds's avatar
Linus Torvalds committed
346
347
348
349
350
351
352
	cl->pq_key = q->jiffies + PSCHED_US2JIFFIE(delay);
	if (cl->pq_key == q->jiffies)
		cl->pq_key++;

	/* update the nearest event cache */
	if (time_after(q->near_ev_cache[cl->level], cl->pq_key))
		q->near_ev_cache[cl->level] = cl->pq_key;
Stephen Hemminger's avatar
Stephen Hemminger committed
353

Linus Torvalds's avatar
Linus Torvalds committed
354
	while (*p) {
Stephen Hemminger's avatar
Stephen Hemminger committed
355
356
		struct htb_class *c;
		parent = *p;
Linus Torvalds's avatar
Linus Torvalds committed
357
358
359
		c = rb_entry(parent, struct htb_class, pq_node);
		if (time_after_eq(cl->pq_key, c->pq_key))
			p = &parent->rb_right;
Stephen Hemminger's avatar
Stephen Hemminger committed
360
		else
Linus Torvalds's avatar
Linus Torvalds committed
361
362
363
364
365
366
367
368
369
370
371
372
			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
373
static inline void htb_next_rb_node(struct rb_node **n)
Linus Torvalds's avatar
Linus Torvalds committed
374
375
376
377
378
379
380
381
382
383
{
	*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
384
385
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
386
387
388
389
390
{
	q->row_mask[cl->level] |= mask;
	while (mask) {
		int prio = ffz(~mask);
		mask &= ~(1 << prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
391
		htb_add_to_id_tree(q->row[cl->level] + prio, cl, prio);
Linus Torvalds's avatar
Linus Torvalds committed
392
393
394
	}
}

Stephen Hemminger's avatar
Stephen Hemminger committed
395
396
397
/* 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)
{
398
	if (RB_EMPTY_NODE(rb)) {
Stephen Hemminger's avatar
Stephen Hemminger committed
399
400
401
402
403
404
405
406
		WARN_ON(1);
	} else {
		rb_erase(rb, root);
		RB_CLEAR_NODE(rb);
	}
}


Linus Torvalds's avatar
Linus Torvalds committed
407
408
409
410
411
412
/**
 * 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
413
414
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
415
416
{
	int m = 0;
417

Linus Torvalds's avatar
Linus Torvalds committed
418
419
	while (mask) {
		int prio = ffz(~mask);
Stephen Hemminger's avatar
Stephen Hemminger committed
420

Linus Torvalds's avatar
Linus Torvalds committed
421
		mask &= ~(1 << prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
422
423
		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
424
425

		htb_safe_rb_erase(cl->node + prio, q->row[cl->level] + prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
426
		if (!q->row[cl->level][prio].rb_node)
Linus Torvalds's avatar
Linus Torvalds committed
427
428
429
430
431
432
433
434
435
436
437
438
			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
 * for priorities it is participating on. cl->cmode must be new 
 * (activated) mode. It does nothing if cl->prio_activity == 0.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
439
static void htb_activate_prios(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds's avatar
Linus Torvalds committed
440
441
{
	struct htb_class *p = cl->parent;
Stephen Hemminger's avatar
Stephen Hemminger committed
442
	long m, mask = cl->prio_activity;
Linus Torvalds's avatar
Linus Torvalds committed
443
444

	while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger's avatar
Stephen Hemminger committed
445
446
		m = mask;
		while (m) {
Linus Torvalds's avatar
Linus Torvalds committed
447
448
			int prio = ffz(~m);
			m &= ~(1 << prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
449

Linus Torvalds's avatar
Linus Torvalds committed
450
451
452
453
			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
454
455

			htb_add_to_id_tree(p->un.inner.feed + prio, cl, prio);
Linus Torvalds's avatar
Linus Torvalds committed
456
457
		}
		p->prio_activity |= mask;
Stephen Hemminger's avatar
Stephen Hemminger committed
458
459
		cl = p;
		p = cl->parent;
460

Linus Torvalds's avatar
Linus Torvalds committed
461
462
	}
	if (cl->cmode == HTB_CAN_SEND && mask)
Stephen Hemminger's avatar
Stephen Hemminger committed
463
		htb_add_class_to_row(q, cl, mask);
Linus Torvalds's avatar
Linus Torvalds committed
464
465
466
467
468
469
470
471
472
473
474
475
}

/**
 * htb_deactivate_prios - remove class from feed chain
 *
 * cl->cmode must represent old mode (before deactivation). It does 
 * 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
476
	long m, mask = cl->prio_activity;
Linus Torvalds's avatar
Linus Torvalds committed
477
478

	while (cl->cmode == HTB_MAY_BORROW && p && mask) {
Stephen Hemminger's avatar
Stephen Hemminger committed
479
480
		m = mask;
		mask = 0;
Linus Torvalds's avatar
Linus Torvalds committed
481
482
483
		while (m) {
			int prio = ffz(~m);
			m &= ~(1 << prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
484
485

			if (p->un.inner.ptr[prio] == cl->node + prio) {
Linus Torvalds's avatar
Linus Torvalds committed
486
487
488
489
490
491
				/* we are removing child which is pointed to from
				   parent feed - forget the pointer but remember
				   classid */
				p->un.inner.last_ptr_id[prio] = cl->classid;
				p->un.inner.ptr[prio] = NULL;
			}
Stephen Hemminger's avatar
Stephen Hemminger committed
492

Stephen Hemminger's avatar
Stephen Hemminger committed
493
			htb_safe_rb_erase(cl->node + prio, p->un.inner.feed + prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
494
495

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

Linus Torvalds's avatar
Linus Torvalds committed
499
		p->prio_activity &= ~mask;
Stephen Hemminger's avatar
Stephen Hemminger committed
500
501
		cl = p;
		p = cl->parent;
502

Linus Torvalds's avatar
Linus Torvalds committed
503
	}
Stephen Hemminger's avatar
Stephen Hemminger committed
504
505
	if (cl->cmode == HTB_CAN_SEND && mask)
		htb_remove_class_from_row(q, cl, mask);
Linus Torvalds's avatar
Linus Torvalds committed
506
507
}

508
509
510
511
512
513
514
515
516
517
518
519
520
521
#if HTB_HYSTERESIS
static inline long htb_lowater(const struct htb_class *cl)
{
	return cl->cmode != HTB_CANT_SEND ? -cl->cbuffer : 0;
}
static inline long htb_hiwater(const struct htb_class *cl)
{
	return cl->cmode == HTB_CAN_SEND ? -cl->buffer : 0;
}
#else
#define htb_lowater(cl)	(0)
#define htb_hiwater(cl)	(0)
#endif

Linus Torvalds's avatar
Linus Torvalds committed
522
523
524
525
526
527
528
529
530
531
532
/**
 * 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
 * from now to time when cl will change its state. 
 * Also it is worth to note that class mode doesn't change simply
 * at cl->{c,}tokens == 0 but there can rather be hysteresis of 
 * 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
533
534
static inline enum htb_cmode
htb_class_mode(struct htb_class *cl, long *diff)
Linus Torvalds's avatar
Linus Torvalds committed
535
{
Stephen Hemminger's avatar
Stephen Hemminger committed
536
	long toks;
Linus Torvalds's avatar
Linus Torvalds committed
537

Stephen Hemminger's avatar
Stephen Hemminger committed
538
539
540
541
	if ((toks = (cl->ctokens + *diff)) < htb_lowater(cl)) {
		*diff = -toks;
		return HTB_CANT_SEND;
	}
542

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

Stephen Hemminger's avatar
Stephen Hemminger committed
546
547
	*diff = -toks;
	return HTB_MAY_BORROW;
Linus Torvalds's avatar
Linus Torvalds committed
548
549
550
551
552
553
554
555
556
557
558
}

/**
 * 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
559
static void
Linus Torvalds's avatar
Linus Torvalds committed
560
htb_change_class_mode(struct htb_sched *q, struct htb_class *cl, long *diff)
Stephen Hemminger's avatar
Stephen Hemminger committed
561
562
{
	enum htb_cmode new_mode = htb_class_mode(cl, diff);
Linus Torvalds's avatar
Linus Torvalds committed
563
564

	if (new_mode == cl->cmode)
Stephen Hemminger's avatar
Stephen Hemminger committed
565
566
567
568
569
		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
570
		cl->cmode = new_mode;
Stephen Hemminger's avatar
Stephen Hemminger committed
571
572
573
		if (new_mode != HTB_CANT_SEND)
			htb_activate_prios(q, cl);
	} else
Linus Torvalds's avatar
Linus Torvalds committed
574
575
576
577
578
579
580
581
582
583
		cl->cmode = new_mode;
}

/**
 * htb_activate - inserts leaf cl into appropriate active feeds 
 *
 * 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
584
static inline void htb_activate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds's avatar
Linus Torvalds committed
585
586
{
	BUG_TRAP(!cl->level && cl->un.leaf.q && cl->un.leaf.q->q.qlen);
587

Linus Torvalds's avatar
Linus Torvalds committed
588
589
	if (!cl->prio_activity) {
		cl->prio_activity = 1 << (cl->un.leaf.aprio = cl->un.leaf.prio);
Stephen Hemminger's avatar
Stephen Hemminger committed
590
591
592
		htb_activate_prios(q, cl);
		list_add_tail(&cl->un.leaf.drop_list,
			      q->drops + cl->un.leaf.aprio);
Linus Torvalds's avatar
Linus Torvalds committed
593
594
595
596
597
598
599
600
601
	}
}

/**
 * htb_deactivate - remove leaf cl from active feeds 
 *
 * 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
602
static inline void htb_deactivate(struct htb_sched *q, struct htb_class *cl)
Linus Torvalds's avatar
Linus Torvalds committed
603
604
{
	BUG_TRAP(cl->prio_activity);
605

Stephen Hemminger's avatar
Stephen Hemminger committed
606
	htb_deactivate_prios(q, cl);
Linus Torvalds's avatar
Linus Torvalds committed
607
608
609
610
611
612
	cl->prio_activity = 0;
	list_del_init(&cl->un.leaf.drop_list);
}

static int htb_enqueue(struct sk_buff *skb, struct Qdisc *sch)
{
Stephen Hemminger's avatar
Stephen Hemminger committed
613
614
615
616
617
618
619
620
621
622
623
624
625
626
	int ret;
	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
627
#ifdef CONFIG_NET_CLS_ACT
Stephen Hemminger's avatar
Stephen Hemminger committed
628
629
630
631
632
	} else if (!cl) {
		if (ret == NET_XMIT_BYPASS)
			sch->qstats.drops++;
		kfree_skb(skb);
		return ret;
Linus Torvalds's avatar
Linus Torvalds committed
633
#endif
Stephen Hemminger's avatar
Stephen Hemminger committed
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
	} else if (cl->un.leaf.q->enqueue(skb, cl->un.leaf.q) !=
		   NET_XMIT_SUCCESS) {
		sch->qstats.drops++;
		cl->qstats.drops++;
		return NET_XMIT_DROP;
	} else {
		cl->bstats.packets++;
		cl->bstats.bytes += skb->len;
		htb_activate(q, cl);
	}

	sch->q.qlen++;
	sch->bstats.packets++;
	sch->bstats.bytes += skb->len;
	return NET_XMIT_SUCCESS;
Linus Torvalds's avatar
Linus Torvalds committed
649
650
651
652
653
}

/* TODO: requeuing packet charges it to policers again !! */
static int htb_requeue(struct sk_buff *skb, struct Qdisc *sch)
{
Stephen Hemminger's avatar
Stephen Hemminger committed
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
	struct htb_sched *q = qdisc_priv(sch);
	int ret = NET_XMIT_SUCCESS;
	struct htb_class *cl = htb_classify(skb, sch, &ret);
	struct sk_buff *tskb;

	if (cl == HTB_DIRECT || !cl) {
		/* enqueue to helper queue */
		if (q->direct_queue.qlen < q->direct_qlen && cl) {
			__skb_queue_head(&q->direct_queue, skb);
		} else {
			__skb_queue_head(&q->direct_queue, skb);
			tskb = __skb_dequeue_tail(&q->direct_queue);
			kfree_skb(tskb);
			sch->qstats.drops++;
			return NET_XMIT_CN;
		}
	} else if (cl->un.leaf.q->ops->requeue(skb, cl->un.leaf.q) !=
		   NET_XMIT_SUCCESS) {
		sch->qstats.drops++;
		cl->qstats.drops++;
		return NET_XMIT_DROP;
	} else
		htb_activate(q, cl);

	sch->q.qlen++;
	sch->qstats.requeues++;
	return NET_XMIT_SUCCESS;
Linus Torvalds's avatar
Linus Torvalds committed
681
682
683
684
}

static void htb_timer(unsigned long arg)
{
Stephen Hemminger's avatar
Stephen Hemminger committed
685
686
687
688
	struct Qdisc *sch = (struct Qdisc *)arg;
	sch->flags &= ~TCQ_F_THROTTLED;
	wmb();
	netif_schedule(sch->dev);
Linus Torvalds's avatar
Linus Torvalds committed
689
690
691
692
693
694
}

#ifdef HTB_RATECM
#define RT_GEN(D,R) R+=D-(R/HTB_EWMAC);D=0
static void htb_rate_timer(unsigned long arg)
{
Stephen Hemminger's avatar
Stephen Hemminger committed
695
	struct Qdisc *sch = (struct Qdisc *)arg;
Linus Torvalds's avatar
Linus Torvalds committed
696
	struct htb_sched *q = qdisc_priv(sch);
697
698
699
	struct hlist_node *p;
	struct htb_class *cl;

Linus Torvalds's avatar
Linus Torvalds committed
700
701

	/* lock queue so that we can muck with it */
Stephen Hemminger's avatar
Stephen Hemminger committed
702
	spin_lock_bh(&sch->dev->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
703
704
705
706
707

	q->rttim.expires = jiffies + HZ;
	add_timer(&q->rttim);

	/* scan and recompute one bucket at time */
Stephen Hemminger's avatar
Stephen Hemminger committed
708
	if (++q->recmp_bucket >= HTB_HSIZE)
Linus Torvalds's avatar
Linus Torvalds committed
709
		q->recmp_bucket = 0;
710

711
	hlist_for_each_entry(cl,p, q->hash + q->recmp_bucket, hlist) {
Stephen Hemminger's avatar
Stephen Hemminger committed
712
713
		RT_GEN(cl->sum_bytes, cl->rate_bytes);
		RT_GEN(cl->sum_packets, cl->rate_packets);
Linus Torvalds's avatar
Linus Torvalds committed
714
	}
Stephen Hemminger's avatar
Stephen Hemminger committed
715
	spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
716
717
718
719
720
721
722
723
724
725
726
727
728
729
}
#endif

/**
 * 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
730
731
732
733
static void htb_charge_class(struct htb_sched *q, struct htb_class *cl,
			     int level, int bytes)
{
	long toks, diff;
Linus Torvalds's avatar
Linus Torvalds committed
734
735
736
737
738
739
740
741
742
	enum htb_cmode old_mode;

#define HTB_ACCNT(T,B,R) toks = diff + cl->T; \
	if (toks > cl->B) toks = cl->B; \
	toks -= L2T(cl, cl->R, bytes); \
	if (toks <= -cl->mbuffer) toks = 1-cl->mbuffer; \
	cl->T = toks

	while (cl) {
Stephen Hemminger's avatar
Stephen Hemminger committed
743
		diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32) cl->mbuffer);
Linus Torvalds's avatar
Linus Torvalds committed
744
		if (cl->level >= level) {
Stephen Hemminger's avatar
Stephen Hemminger committed
745
746
747
			if (cl->level == level)
				cl->xstats.lends++;
			HTB_ACCNT(tokens, buffer, rate);
Linus Torvalds's avatar
Linus Torvalds committed
748
749
		} else {
			cl->xstats.borrows++;
Stephen Hemminger's avatar
Stephen Hemminger committed
750
			cl->tokens += diff;	/* we moved t_c; update tokens */
Linus Torvalds's avatar
Linus Torvalds committed
751
		}
Stephen Hemminger's avatar
Stephen Hemminger committed
752
		HTB_ACCNT(ctokens, cbuffer, ceil);
Linus Torvalds's avatar
Linus Torvalds committed
753
754
		cl->t_c = q->now;

Stephen Hemminger's avatar
Stephen Hemminger committed
755
756
757
		old_mode = cl->cmode;
		diff = 0;
		htb_change_class_mode(q, cl, &diff);
Linus Torvalds's avatar
Linus Torvalds committed
758
759
		if (old_mode != cl->cmode) {
			if (old_mode != HTB_CAN_SEND)
Stephen Hemminger's avatar
Stephen Hemminger committed
760
				htb_safe_rb_erase(&cl->pq_node, q->wait_pq + cl->level);
Linus Torvalds's avatar
Linus Torvalds committed
761
			if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger's avatar
Stephen Hemminger committed
762
				htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds's avatar
Linus Torvalds committed
763
764
765
		}
#ifdef HTB_RATECM
		/* update rate counters */
Stephen Hemminger's avatar
Stephen Hemminger committed
766
767
		cl->sum_bytes += bytes;
		cl->sum_packets++;
Linus Torvalds's avatar
Linus Torvalds committed
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
#endif

		/* update byte stats except for leaves which are already updated */
		if (cl->level) {
			cl->bstats.bytes += bytes;
			cl->bstats.packets++;
		}
		cl = cl->parent;
	}
}

/**
 * htb_do_events - make mode changes to classes at the level
 *
 * Scans event queue for pending events and applies them. Returns jiffies to
 * next pending event (0 for no event in pq).
 * Note: Aplied are events whose have cl->pq_key <= jiffies.
 */
Stephen Hemminger's avatar
Stephen Hemminger committed
786
static long htb_do_events(struct htb_sched *q, int level)
Linus Torvalds's avatar
Linus Torvalds committed
787
788
{
	int i;
789

Linus Torvalds's avatar
Linus Torvalds committed
790
791
792
	for (i = 0; i < 500; i++) {
		struct htb_class *cl;
		long diff;
793
794
		struct rb_node *p = rb_first(&q->wait_pq[level]);

Stephen Hemminger's avatar
Stephen Hemminger committed
795
796
		if (!p)
			return 0;
Linus Torvalds's avatar
Linus Torvalds committed
797
798
799
800
801

		cl = rb_entry(p, struct htb_class, pq_node);
		if (time_after(cl->pq_key, q->jiffies)) {
			return cl->pq_key - q->jiffies;
		}
Stephen Hemminger's avatar
Stephen Hemminger committed
802
		htb_safe_rb_erase(p, q->wait_pq + level);
Stephen Hemminger's avatar
Stephen Hemminger committed
803
804
		diff = PSCHED_TDIFF_SAFE(q->now, cl->t_c, (u32) cl->mbuffer);
		htb_change_class_mode(q, cl, &diff);
Linus Torvalds's avatar
Linus Torvalds committed
805
		if (cl->cmode != HTB_CAN_SEND)
Stephen Hemminger's avatar
Stephen Hemminger committed
806
			htb_add_to_wait_tree(q, cl, diff);
Linus Torvalds's avatar
Linus Torvalds committed
807
808
809
	}
	if (net_ratelimit())
		printk(KERN_WARNING "htb: too many events !\n");
Stephen Hemminger's avatar
Stephen Hemminger committed
810
	return HZ / 10;
Linus Torvalds's avatar
Linus Torvalds committed
811
812
813
814
}

/* 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
815
816
static struct rb_node *htb_id_find_next_upper(int prio, struct rb_node *n,
					      u32 id)
Linus Torvalds's avatar
Linus Torvalds committed
817
818
819
{
	struct rb_node *r = NULL;
	while (n) {
Stephen Hemminger's avatar
Stephen Hemminger committed
820
821
822
823
824
		struct htb_class *cl =
		    rb_entry(n, struct htb_class, node[prio]);
		if (id == cl->classid)
			return n;

Linus Torvalds's avatar
Linus Torvalds committed
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
		if (id > cl->classid) {
			n = n->rb_right;
		} else {
			r = n;
			n = n->rb_left;
		}
	}
	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
840
841
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
842
843
844
845
846
847
{
	int i;
	struct {
		struct rb_node *root;
		struct rb_node **pptr;
		u32 *pid;
Stephen Hemminger's avatar
Stephen Hemminger committed
848
849
	} stk[TC_HTB_MAXDEPTH], *sp = stk;

Linus Torvalds's avatar
Linus Torvalds committed
850
851
852
853
854
855
	BUG_TRAP(tree->rb_node);
	sp->root = tree->rb_node;
	sp->pptr = pptr;
	sp->pid = pid;

	for (i = 0; i < 65535; i++) {
Stephen Hemminger's avatar
Stephen Hemminger committed
856
		if (!*sp->pptr && *sp->pid) {
Linus Torvalds's avatar
Linus Torvalds committed
857
858
			/* ptr was invalidated but id is valid - try to recover 
			   the original or next ptr */
Stephen Hemminger's avatar
Stephen Hemminger committed
859
860
			*sp->pptr =
			    htb_id_find_next_upper(prio, sp->root, *sp->pid);
Linus Torvalds's avatar
Linus Torvalds committed
861
		}
Stephen Hemminger's avatar
Stephen Hemminger committed
862
863
864
		*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
865
			*sp->pptr = sp->root;
Stephen Hemminger's avatar
Stephen Hemminger committed
866
			while ((*sp->pptr)->rb_left)
Linus Torvalds's avatar
Linus Torvalds committed
867
868
869
				*sp->pptr = (*sp->pptr)->rb_left;
			if (sp > stk) {
				sp--;
Stephen Hemminger's avatar
Stephen Hemminger committed
870
871
872
873
				BUG_TRAP(*sp->pptr);
				if (!*sp->pptr)
					return NULL;
				htb_next_rb_node(sp->pptr);
Linus Torvalds's avatar
Linus Torvalds committed
874
875
876
			}
		} else {
			struct htb_class *cl;
Stephen Hemminger's avatar
Stephen Hemminger committed
877
878
			cl = rb_entry(*sp->pptr, struct htb_class, node[prio]);
			if (!cl->level)
Linus Torvalds's avatar
Linus Torvalds committed
879
880
				return cl;
			(++sp)->root = cl->un.inner.feed[prio].rb_node;
Stephen Hemminger's avatar
Stephen Hemminger committed
881
882
			sp->pptr = cl->un.inner.ptr + prio;
			sp->pid = cl->un.inner.last_ptr_id + prio;
Linus Torvalds's avatar
Linus Torvalds committed
883
884
885
886
887
888
889
890
		}
	}
	BUG_TRAP(0);
	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
891
892
static struct sk_buff *htb_dequeue_tree(struct htb_sched *q, int prio,
					int level)
Linus Torvalds's avatar
Linus Torvalds committed
893
894
{
	struct sk_buff *skb = NULL;
Stephen Hemminger's avatar
Stephen Hemminger committed
895
	struct htb_class *cl, *start;
Linus Torvalds's avatar
Linus Torvalds committed
896
	/* look initial class up in the row */
Stephen Hemminger's avatar
Stephen Hemminger committed
897
898
899
900
	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
901
902
	do {
next:
Stephen Hemminger's avatar
Stephen Hemminger committed
903
904
905
		BUG_TRAP(cl);
		if (!cl)
			return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
906
907
908
909
910
911
912

		/* class can be empty - it is unlikely but can be true if leaf
		   qdisc drops packets in enqueue routine or if someone used
		   graft operation on the leaf since last dequeue; 
		   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
913
			htb_deactivate(q, cl);
Linus Torvalds's avatar
Linus Torvalds committed
914
915
916

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

Stephen Hemminger's avatar
Stephen Hemminger committed
919
920
921
922
923
			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
924
925
926
927
				start = next;
			cl = next;
			goto next;
		}
Stephen Hemminger's avatar
Stephen Hemminger committed
928
929
930

		skb = cl->un.leaf.q->dequeue(cl->un.leaf.q);
		if (likely(skb != NULL))
Linus Torvalds's avatar
Linus Torvalds committed
931
932
			break;
		if (!cl->warned) {
Stephen Hemminger's avatar
Stephen Hemminger committed
933
934
935
			printk(KERN_WARNING
			       "htb: class %X isn't work conserving ?!\n",
			       cl->classid);
Linus Torvalds's avatar
Linus Torvalds committed
936
937
938
			cl->warned = 1;
		}
		q->nwc_hit++;
Stephen Hemminger's avatar
Stephen Hemminger committed
939
940
941
942
943
		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
944
945
946
947
948
949

	} while (cl != start);

	if (likely(skb != NULL)) {
		if ((cl->un.leaf.deficit[level] -= skb->len) < 0) {
			cl->un.leaf.deficit[level] += cl->un.leaf.quantum;
Stephen Hemminger's avatar
Stephen Hemminger committed
950
951
			htb_next_rb_node((level ? cl->parent->un.inner.ptr : q->
					  ptr[0]) + prio);
Linus Torvalds's avatar
Linus Torvalds committed
952
953
954
955
		}
		/* 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
956
957
			htb_deactivate(q, cl);
		htb_charge_class(q, cl, level, skb->len);
Linus Torvalds's avatar
Linus Torvalds committed
958
959
960
961
	}
	return skb;
}

Stephen Hemminger's avatar
Stephen Hemminger committed
962
static void htb_delay_by(struct Qdisc *sch, long delay)
Linus Torvalds's avatar
Linus Torvalds committed
963
964
{
	struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger's avatar
Stephen Hemminger committed
965
966
967
	if (delay <= 0)
		delay = 1;
	if (unlikely(delay > 5 * HZ)) {
Linus Torvalds's avatar
Linus Torvalds committed
968
969
		if (net_ratelimit())
			printk(KERN_INFO "HTB delay %ld > 5sec\n", delay);
Stephen Hemminger's avatar
Stephen Hemminger committed
970
		delay = 5 * HZ;
Linus Torvalds's avatar
Linus Torvalds committed
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
	}
	/* why don't use jiffies here ? because expires can be in past */
	mod_timer(&q->timer, q->jiffies + delay);
	sch->flags |= TCQ_F_THROTTLED;
	sch->qstats.overlimits++;
}

static struct sk_buff *htb_dequeue(struct Qdisc *sch)
{
	struct sk_buff *skb = NULL;
	struct htb_sched *q = qdisc_priv(sch);
	int level;
	long min_delay;

	q->jiffies = jiffies;

	/* try to dequeue direct packets as high prio (!) to minimize cpu work */
Stephen Hemminger's avatar
Stephen Hemminger committed
988
989
	skb = __skb_dequeue(&q->direct_queue);
	if (skb != NULL) {
Linus Torvalds's avatar
Linus Torvalds committed
990
991
992
993
994
		sch->flags &= ~TCQ_F_THROTTLED;
		sch->q.qlen--;
		return skb;
	}

Stephen Hemminger's avatar
Stephen Hemminger committed
995
996
	if (!sch->q.qlen)
		goto fin;
Linus Torvalds's avatar
Linus Torvalds committed
997
998
999
1000
1001
1002
1003
1004
1005
	PSCHED_GET_TIME(q->now);

	min_delay = LONG_MAX;
	q->nwc_hit = 0;
	for (level = 0; level < TC_HTB_MAXDEPTH; level++) {
		/* common case optimization - skip event handler quickly */
		int m;
		long delay;
		if (time_after_eq(q->jiffies, q->near_ev_cache[level])) {
Stephen Hemminger's avatar
Stephen Hemminger committed
1006
1007
1008
			delay = htb_do_events(q, level);
			q->near_ev_cache[level] =
			    q->jiffies + (delay ? delay : HZ);
Linus Torvalds's avatar
Linus Torvalds committed
1009
		} else
Stephen Hemminger's avatar
Stephen Hemminger committed
1010
1011
1012
			delay = q->near_ev_cache[level] - q->jiffies;

		if (delay && min_delay > delay)
Linus Torvalds's avatar
Linus Torvalds committed
1013
1014
1015
			min_delay = delay;
		m = ~q->row_mask[level];
		while (m != (int)(-1)) {
Stephen Hemminger's avatar
Stephen Hemminger committed
1016
			int prio = ffz(m);
Linus Torvalds's avatar
Linus Torvalds committed
1017
			m |= 1 << prio;
Stephen Hemminger's avatar
Stephen Hemminger committed
1018
			skb = htb_dequeue_tree(q, prio, level);
Linus Torvalds's avatar
Linus Torvalds committed
1019
1020
1021
1022
1023
1024
1025
			if (likely(skb != NULL)) {
				sch->q.qlen--;
				sch->flags &= ~TCQ_F_THROTTLED;
				goto fin;
			}
		}
	}
Stephen Hemminger's avatar
Stephen Hemminger committed
1026
	htb_delay_by(sch, min_delay > 5 * HZ ? 5 * HZ : min_delay);
Linus Torvalds's avatar
Linus Torvalds committed
1027
1028
1029
1030
1031
fin:
	return skb;
}

/* try to drop from each class (by prio) until one succeed */
Stephen Hemminger's avatar
Stephen Hemminger committed
1032
static unsigned int htb_drop(struct Qdisc *sch)
Linus Torvalds's avatar
Linus Torvalds committed
1033
1034
1035
1036
1037
1038
{
	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
1039
		list_for_each(p, q->drops + prio) {
Linus Torvalds's avatar
Linus Torvalds committed
1040
1041
1042
			struct htb_class *cl = list_entry(p, struct htb_class,
							  un.leaf.drop_list);
			unsigned int len;
Stephen Hemminger's avatar
Stephen Hemminger committed
1043
1044
			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
1045
1046
				sch->q.qlen--;
				if (!cl->un.leaf.q->q.qlen)
Stephen Hemminger's avatar
Stephen Hemminger committed
1047
					htb_deactivate(q, cl);
Linus Torvalds's avatar
Linus Torvalds committed
1048
1049
1050
1051
1052
1053
1054
1055
1056
				return len;
			}
		}
	}
	return 0;
}

/* reset all classes */
/* always caled under BH & queue lock */
Stephen Hemminger's avatar
Stephen Hemminger committed
1057
static void htb_reset(struct Qdisc *sch)
Linus Torvalds's avatar
Linus Torvalds committed
1058
1059
1060
1061
1062
{
	struct htb_sched *q = qdisc_priv(sch);
	int i;

	for (i = 0; i < HTB_HSIZE; i++) {
1063
1064
1065
1066
		struct hlist_node *p;
		struct htb_class *cl;

		hlist_for_each_entry(cl, p, q->hash + i, hlist) {
Linus Torvalds's avatar
Linus Torvalds committed
1067
			if (cl->level)
Stephen Hemminger's avatar
Stephen Hemminger committed
1068
				memset(&cl->un.inner, 0, sizeof(cl->un.inner));
Linus Torvalds's avatar
Linus Torvalds committed
1069
			else {
Stephen Hemminger's avatar
Stephen Hemminger committed
1070
				if (cl->un.leaf.q)
Linus Torvalds's avatar
Linus Torvalds committed
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
					qdisc_reset(cl->un.leaf.q);
				INIT_LIST_HEAD(&cl->un.leaf.drop_list);
			}
			cl->prio_activity = 0;
			cl->cmode = HTB_CAN_SEND;

		}
	}
	sch->flags &= ~TCQ_F_THROTTLED;
	del_timer(&q->timer);
	__skb_queue_purge(&q->direct_queue);
	sch->q.qlen = 0;
Stephen Hemminger's avatar
Stephen Hemminger committed
1083
1084
1085
1086
	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
1087
	for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger's avatar
Stephen Hemminger committed
1088
		INIT_LIST_HEAD(q->drops + i);
Linus Torvalds's avatar
Linus Torvalds committed
1089
1090
1091
1092
1093
1094
1095
1096
1097
}

static int htb_init(struct Qdisc *sch, struct rtattr *opt)
{
	struct htb_sched *q = qdisc_priv(sch);
	struct rtattr *tb[TCA_HTB_INIT];
	struct tc_htb_glob *gopt;
	int i;
	if (!opt || rtattr_parse_nested(tb, TCA_HTB_INIT, opt) ||
Stephen Hemminger's avatar
Stephen Hemminger committed
1098
1099
	    tb[TCA_HTB_INIT - 1] == NULL ||
	    RTA_PAYLOAD(tb[TCA_HTB_INIT - 1]) < sizeof(*gopt)) {
Linus Torvalds's avatar
Linus Torvalds committed
1100
1101
1102
		printk(KERN_ERR "HTB: hey probably you have bad tc tool ?\n");
		return -EINVAL;
	}
Stephen Hemminger's avatar
Stephen Hemminger committed
1103
	gopt = RTA_DATA(tb[TCA_HTB_INIT - 1]);
Linus Torvalds's avatar
Linus Torvalds committed
1104
	if (gopt->version != HTB_VER >> 16) {
Stephen Hemminger's avatar
Stephen Hemminger committed
1105
1106
1107
		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
1108
1109
1110
1111
1112
		return -EINVAL;
	}

	INIT_LIST_HEAD(&q->root);
	for (i = 0; i < HTB_HSIZE; i++)
1113
		INIT_HLIST_HEAD(q->hash + i);
Linus Torvalds's avatar
Linus Torvalds committed
1114
	for (i = 0; i < TC_HTB_NUMPRIO; i++)
Stephen Hemminger's avatar
Stephen Hemminger committed
1115
		INIT_LIST_HEAD(q->drops + i);
Linus Torvalds's avatar
Linus Torvalds committed
1116
1117
1118
1119
1120

	init_timer(&q->timer);
	skb_queue_head_init(&q->direct_queue);

	q->direct_qlen = sch->dev->tx_queue_len;
Stephen Hemminger's avatar
Stephen Hemminger committed
1121
	if (q->direct_qlen < 2)	/* some devices have zero tx_queue_len */
Linus Torvalds's avatar
Linus Torvalds committed
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
		q->direct_qlen = 2;
	q->timer.function = htb_timer;
	q->timer.data = (unsigned long)sch;

#ifdef HTB_RATECM
	init_timer(&q->rttim);
	q->rttim.function = htb_rate_timer;
	q->rttim.data = (unsigned long)sch;
	q->rttim.expires = jiffies + HZ;
	add_timer(&q->rttim);
#endif
	if ((q->rate2quantum = gopt->rate2quantum) < 1)
		q->rate2quantum = 1;
	q->defcls = gopt->defcls;

	return 0;
}

static int htb_dump(struct Qdisc *sch, struct sk_buff *skb)
{
	struct htb_sched *q = qdisc_priv(sch);
Stephen Hemminger's avatar
Stephen Hemminger committed
1143
	unsigned char *b = skb->tail;
Linus Torvalds's avatar
Linus Torvalds committed
1144
1145
	struct rtattr *rta;
	struct tc_htb_glob gopt;
Stephen Hemminger's avatar
Stephen Hemminger committed
1146
	spin_lock_bh(&sch->dev->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1147
1148
1149
1150
1151
	gopt.direct_pkts = q->direct_pkts;

	gopt.version = HTB_VER;
	gopt.rate2quantum = q->rate2quantum;
	gopt.defcls = q->defcls;
1152
	gopt.debug = 0;
Stephen Hemminger's avatar
Stephen Hemminger committed
1153
	rta = (struct rtattr *)b;
Linus Torvalds's avatar
Linus Torvalds committed
1154
1155
1156
	RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
	RTA_PUT(skb, TCA_HTB_INIT, sizeof(gopt), &gopt);
	rta->rta_len = skb->tail - b;
Stephen Hemminger's avatar
Stephen Hemminger committed
1157
	spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1158
1159
	return skb->len;
rtattr_failure:
Stephen Hemminger's avatar
Stephen Hemminger committed
1160
	spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1161
1162
1163
1164
1165
	skb_trim(skb, skb->tail - skb->data);
	return -1;
}

static int htb_dump_class(struct Qdisc *sch, unsigned long arg,
Stephen Hemminger's avatar
Stephen Hemminger committed
1166
			  struct sk_buff *skb, struct tcmsg *tcm)
Linus Torvalds's avatar
Linus Torvalds committed
1167
{
Stephen Hemminger's avatar
Stephen Hemminger committed
1168
1169
	struct htb_class *cl = (struct htb_class *)arg;
	unsigned char *b = skb->tail;
Linus Torvalds's avatar
Linus Torvalds committed
1170
1171
1172
	struct rtattr *rta;
	struct tc_htb_opt opt;

Stephen Hemminger's avatar
Stephen Hemminger committed
1173
	spin_lock_bh(&sch->dev->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1174
1175
1176
1177
1178
	tcm->tcm_parent = cl->parent ? cl->parent->classid : TC_H_ROOT;
	tcm->tcm_handle = cl->classid;
	if (!cl->level && cl->un.leaf.q)
		tcm->tcm_info = cl->un.leaf.q->handle;

Stephen Hemminger's avatar
Stephen Hemminger committed
1179
	rta = (struct rtattr *)b;
Linus Torvalds's avatar
Linus Torvalds committed
1180
1181
	RTA_PUT(skb, TCA_OPTIONS, 0, NULL);

Stephen Hemminger's avatar
Stephen Hemminger committed
1182
	memset(&opt, 0, sizeof(opt));
Linus Torvalds's avatar
Linus Torvalds committed
1183

Stephen Hemminger's avatar
Stephen Hemminger committed
1184
1185
1186
1187
1188
1189
1190
	opt.rate = cl->rate->rate;
	opt.buffer = cl->buffer;
	opt.ceil = cl->ceil->rate;
	opt.cbuffer = cl->cbuffer;
	opt.quantum = cl->un.leaf.quantum;
	opt.prio = cl->un.leaf.prio;
	opt.level = cl->level;
Linus Torvalds's avatar
Linus Torvalds committed
1191
1192
	RTA_PUT(skb, TCA_HTB_PARMS, sizeof(opt), &opt);
	rta->rta_len = skb->tail - b;
Stephen Hemminger's avatar
Stephen Hemminger committed
1193
	spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1194
1195
	return skb->len;
rtattr_failure:
Stephen Hemminger's avatar
Stephen Hemminger committed
1196
	spin_unlock_bh(&sch->dev->queue_lock);
Linus Torvalds's avatar
Linus Torvalds committed
1197
1198
1199
1200
1201
	skb_trim(skb, b - skb->data);
	return -1;
}

static int
Stephen Hemminger's avatar
Stephen Hemminger committed
1202
htb_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d)
Linus Torvalds's avatar
Linus Torvalds committed
1203
{
Stephen Hemminger's avatar
Stephen Hemminger committed
1204
	struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds's avatar
Linus Torvalds committed
1205
1206

#ifdef HTB_RATECM
Stephen Hemminger's avatar
Stephen Hemminger committed
1207
1208
	cl->rate_est.bps = cl->rate_bytes / (HTB_EWMAC * HTB_HSIZE);
	cl->rate_est.pps = cl->rate_packets / (HTB_EWMAC * HTB_HSIZE);
Linus Torvalds's avatar
Linus Torvalds committed
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
#endif

	if (!cl->level && cl->un.leaf.q)
		cl->qstats.qlen = cl->un.leaf.q->q.qlen;
	cl->xstats.tokens = cl->tokens;
	cl->xstats.ctokens = cl->ctokens;

	if (gnet_stats_copy_basic(d, &cl->bstats) < 0 ||
	    gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
	    gnet_stats_copy_queue(d, &cl->qstats) < 0)
		return -1;

	return gnet_stats_copy_app(d, &cl->xstats, sizeof(cl->xstats));
}

static int htb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new,
Stephen Hemminger's avatar
Stephen Hemminger committed
1225
		     struct Qdisc **old)
Linus Torvalds's avatar
Linus Torvalds committed
1226
{
Stephen Hemminger's avatar
Stephen Hemminger committed
1227
	struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds's avatar
Linus Torvalds committed
1228
1229

	if (cl && !cl->level) {
1230
1231
1232
		if (new == NULL &&
		    (new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops,
		    			     cl->classid))
Stephen Hemminger's avatar
Stephen Hemminger committed
1233
1234
		    == NULL)
			return -ENOBUFS;
Linus Torvalds's avatar
Linus Torvalds committed
1235
1236
		sch_tree_lock(sch);
		if ((*old = xchg(&cl->un.leaf.q, new)) != NULL) {
1237
			qdisc_tree_decrease_qlen(*old, (*old)->q.qlen);
Linus Torvalds's avatar
Linus Torvalds committed
1238
1239
1240
1241
1242
1243
1244
1245
			qdisc_reset(*old);
		}
		sch_tree_unlock(sch);
		return 0;
	}
	return -ENOENT;
}

Stephen Hemminger's avatar
Stephen Hemminger committed
1246
static struct Qdisc *htb_leaf(struct Qdisc *sch, unsigned long arg)
Linus Torvalds's avatar
Linus Torvalds committed
1247
{
Stephen Hemminger's avatar
Stephen Hemminger committed
1248
	struct htb_class *cl = (struct htb_class *)arg;
Linus Torvalds's avatar
Linus Torvalds committed
1249
1250
1251
	return (cl && !cl->level) ? cl->un.leaf.q : NULL;
}

1252
1253
1254
1255
1256
1257
1258
1259
static void htb_qlen_notify(struct Qdisc *sch, unsigned long arg)
{
	struct htb_class *cl = (struct htb_class *)arg;

	if (cl->un.leaf.q->q.qlen == 0)
		htb_deactivate(qdisc_priv(sch), cl);
}

Linus Torvalds's avatar
Linus Torvalds committed
1260
1261
static unsigned long htb_get(struct Qdisc *sch, u32 classid)
{
Stephen Hemminger's avatar
Stephen Hemminger committed
1262
1263
	struct htb_class *cl = htb_find(classid, sch);
	if (cl)
Linus Torvalds's avatar
Linus Torvalds committed
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
		cl->refcnt++;
	return (unsigned long)cl;
}

static void htb_destroy_filters(struct tcf_proto **fl)
{
	struct tcf_proto *tp;

	while ((tp = *fl) != NULL) {
		*fl = tp->next;
		tcf_destroy(tp);
	}
}

1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
static inline int htb_parent_last_child(struct htb_class *cl)
{
	if (!cl->parent)
		/* the root class */
		return 0;

	if (!(cl->parent->children.next == &cl->sibling &&
		cl->parent->children.prev == &cl->sibling))
		/* not the last child */
		return 0;

	return 1;
}

static void htb_parent_to_leaf(struct htb_class *cl, struct Qdisc *new_q)
{
	struct htb_class *parent = cl->parent;

	BUG_TRAP(!cl->level && cl->un.leaf.q && !cl->prio_activity);

	parent->level = 0;
	memset(&parent->un.inner, 0, sizeof(parent->un.inner));
	INIT_LIST_HEAD(&parent->un.leaf.drop_list);
	parent->un.leaf.q = new_q ? new_q : &noop_qdisc;
	parent->un.leaf.quantum = parent->quantum;
	parent->un.leaf.prio = parent->prio;
	parent->tokens = parent->buffer;
	parent->ctokens = parent->cbuffer;
	PSCHED_GET_TIME(parent->t_c);
	parent->cmode = HTB_CAN_SEND;
}

Stephen Hemminger's avatar
Stephen Hemminger committed
1310
static void htb_destroy_class(struct Qdisc *sch, struct htb_class *cl)
Linus Torvalds's avatar
Linus Torvalds committed
1311
1312
{
	struct htb_sched *q = qdisc_priv(sch);
1313

Linus Torvalds's avatar
Linus Torvalds committed
1314
1315
1316
1317
1318
1319
	if (!cl->level) {
		BUG_TRAP(cl->un.leaf.q);
		qdisc_destroy(cl->un.leaf.q);
	}
	qdisc_put_rtab(cl->rate);
	qdisc_put_rtab(cl->ceil);
Stephen Hemminger's avatar
Stephen Hemminger committed
1320
1321
1322
1323
1324
1325

	htb_destroy_filters(&cl->filter_list);

	while (!list_empty(&cl->children))
		htb_destroy_class(sch, list_entry(cl->children.next,
						  struct htb_class, sibling));
Linus Torvalds's avatar
Linus Torvalds committed
1326
1327

	/* note: this delete may happen twice (see htb_delete) */
1328
	hlist_del_init(&cl->hlist);
Linus Torvalds's avatar
Linus Torvalds committed
1329