projects / openwrt / staging / yousong.git / blob
? search:


2a05f0345643ab8c65f7c8a59dfcd0e1a72118ab
[openwrt/staging/yousong.git] / target / linux / generic-2.4 / patches / 622-tc_esfq.patch
1 Index: linux-2.4.35.4/Documentation/Configure.help
2 ===================================================================
3 --- linux-2.4.35.4.orig/Documentation/Configure.help
4 +++ linux-2.4.35.4/Documentation/Configure.help
5 @@ -11153,6 +11153,24 @@ CONFIG_NET_SCH_HFSC
6 whenever you want). If you want to compile it as a module, say M
7 here and read <file:Documentation/modules.txt>.
8
9 +ESFQ queue
10 +CONFIG_NET_SCH_ESFQ
11 + Say Y here if you want to use the Stochastic Fairness Queueing (SFQ)
12 + packet scheduling algorithm for some of your network devices or as a
13 + leaf discipline for the CBQ scheduling algorithm (see the top of
14 + <file:net/sched/sch_esfq.c> for details and references about the SFQ
15 + algorithm).
16 +
17 + This is an enchanced SFQ version which allows you to control the
18 + hardcoded values in the SFQ scheduler: queue depth, hash table size,
19 + queues limit. Also adds control to the hash function used to identify
20 + packet flows. Hash by src or dst ip and original sfq hash.
21 +
22 + This code is also available as a module called sch_esfq.o ( = code
23 + which can be inserted in and removed from the running kernel
24 + whenever you want). If you want to compile it as a module, say M
25 + here and read <file:Documentation/modules.txt>.
26 +
27 CSZ packet scheduler
28 CONFIG_NET_SCH_CSZ
29 Say Y here if you want to use the Clark-Shenker-Zhang (CSZ) packet
30 Index: linux-2.4.35.4/include/linux/pkt_sched.h
31 ===================================================================
32 --- linux-2.4.35.4.orig/include/linux/pkt_sched.h
33 +++ linux-2.4.35.4/include/linux/pkt_sched.h
34 @@ -173,8 +173,36 @@ struct tc_sfq_qopt
35 *
36 * The only reason for this is efficiency, it is possible
37 * to change these parameters in compile time.
38 + *
39 + * If you need to play with these values use esfq instead.
40 */
41
42 +/* ESFQ section */
43 +
44 +enum
45 +{
46 + /* traditional */
47 + TCA_SFQ_HASH_CLASSIC,
48 + TCA_SFQ_HASH_DST,
49 + TCA_SFQ_HASH_SRC,
50 + /* conntrack */
51 + TCA_SFQ_HASH_CTORIGDST,
52 + TCA_SFQ_HASH_CTORIGSRC,
53 + TCA_SFQ_HASH_CTREPLDST,
54 + TCA_SFQ_HASH_CTREPLSRC,
55 + TCA_SFQ_HASH_CTNATCHG,
56 +};
57 +
58 +struct tc_esfq_qopt
59 +{
60 + unsigned quantum; /* Bytes per round allocated to flow */
61 + int perturb_period; /* Period of hash perturbation */
62 + __u32 limit; /* Maximal packets in queue */
63 + unsigned divisor; /* Hash divisor */
64 + unsigned flows; /* Maximal number of flows */
65 + unsigned hash_kind; /* Hash function to use for flow identification */
66 +};
67 +
68 /* RED section */
69
70 enum
71 Index: linux-2.4.35.4/net/sched/Config.in
72 ===================================================================
73 --- linux-2.4.35.4.orig/net/sched/Config.in
74 +++ linux-2.4.35.4/net/sched/Config.in
75 @@ -12,6 +12,7 @@ fi
76 tristate ' The simplest PRIO pseudoscheduler' CONFIG_NET_SCH_PRIO
77 tristate ' RED queue' CONFIG_NET_SCH_RED
78 tristate ' SFQ queue' CONFIG_NET_SCH_SFQ
79 +tristate ' ESFQ queue' CONFIG_NET_SCH_ESFQ
80 tristate ' TEQL queue' CONFIG_NET_SCH_TEQL
81 tristate ' TBF queue' CONFIG_NET_SCH_TBF
82 tristate ' GRED queue' CONFIG_NET_SCH_GRED
83 Index: linux-2.4.35.4/net/sched/Makefile
84 ===================================================================
85 --- linux-2.4.35.4.orig/net/sched/Makefile
86 +++ linux-2.4.35.4/net/sched/Makefile
87 @@ -19,6 +19,7 @@ obj-$(CONFIG_NET_SCH_HPFQ) += sch_hpfq.o
88 obj-$(CONFIG_NET_SCH_HFSC) += sch_hfsc.o
89 obj-$(CONFIG_NET_SCH_HTB) += sch_htb.o
90 obj-$(CONFIG_NET_SCH_SFQ) += sch_sfq.o
91 +obj-$(CONFIG_NET_SCH_ESFQ) += sch_esfq.o
92 obj-$(CONFIG_NET_SCH_RED) += sch_red.o
93 obj-$(CONFIG_NET_SCH_TBF) += sch_tbf.o
94 obj-$(CONFIG_NET_SCH_PRIO) += sch_prio.o
95 Index: linux-2.4.35.4/net/sched/sch_esfq.c
96 ===================================================================
97 --- /dev/null
98 +++ linux-2.4.35.4/net/sched/sch_esfq.c
99 @@ -0,0 +1,649 @@
100 +/*
101 + * net/sched/sch_esfq.c Extended Stochastic Fairness Queueing discipline.
102 + *
103 + * This program is free software; you can redistribute it and/or
104 + * modify it under the terms of the GNU General Public License
105 + * as published by the Free Software Foundation; either version
106 + * 2 of the License, or (at your option) any later version.
107 + *
108 + * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
109 + *
110 + * Changes: Alexander Atanasov, <alex@ssi.bg>
111 + * Added dynamic depth,limit,divisor,hash_kind options.
112 + * Added dst and src hashes.
113 + *
114 + * Alexander Clouter, <alex@digriz.org.uk>
115 + * Ported ESFQ to Linux 2.6.
116 + *
117 + * Corey Hickey, <bugfood-c@fatooh.org>
118 + * Maintenance of the Linux 2.6 port.
119 + * Added fwmark hash (thanks to Robert Kurjata).
120 + * Added usage of jhash.
121 + *
122 + */
123 +
124 +#include <linux/config.h>
125 +#include <linux/module.h>
126 +#include <asm/uaccess.h>
127 +#include <asm/system.h>
128 +#include <linux/bitops.h>
129 +#include <linux/types.h>
130 +#include <linux/kernel.h>
131 +#include <linux/sched.h>
132 +#include <linux/string.h>
133 +#include <linux/mm.h>
134 +#include <linux/socket.h>
135 +#include <linux/sockios.h>
136 +#include <linux/in.h>
137 +#include <linux/errno.h>
138 +#include <linux/interrupt.h>
139 +#include <linux/if_ether.h>
140 +#include <linux/inet.h>
141 +#include <linux/netdevice.h>
142 +#include <linux/etherdevice.h>
143 +#include <linux/notifier.h>
144 +#include <linux/init.h>
145 +#include <net/ip.h>
146 +#include <net/route.h>
147 +#include <linux/skbuff.h>
148 +#include <net/sock.h>
149 +#include <net/pkt_sched.h>
150 +#include <linux/jhash.h>
151 +
152 +#define IPPROTO_DCCP 33
153 +#define qdisc_priv(q) ((void *)(q->data))
154 +
155 +#ifdef CONFIG_IP_NF_CONNTRACK
156 +/* #include <net/netfilter/nf_conntrack.h> */
157 +#include <linux/netfilter_ipv4/ip_conntrack.h>
158 +#endif
159 +
160 +/* Stochastic Fairness Queuing algorithm.
161 + For more comments look at sch_sfq.c.
162 + The difference is that you can change limit, depth,
163 + hash table size and choose alternate hash types.
164 +
165 + classic: same as in sch_sfq.c
166 + dst: destination IP address
167 + src: source IP address
168 + ctorigdst: original destination IP address
169 + ctorigsrc: original source IP address
170 + ctrepldst: reply destination IP address
171 + ctreplsrc: reply source IP
172 + ctnatchg: use the address which changed via nat
173 +
174 +*/
175 +
176 +
177 +/* This type should contain at least SFQ_DEPTH*2 values */
178 +typedef unsigned int esfq_index;
179 +
180 +struct esfq_head
181 +{
182 + esfq_index next;
183 + esfq_index prev;
184 +};
185 +
186 +struct esfq_sched_data
187 +{
188 +/* Parameters */
189 + int perturb_period;
190 + unsigned quantum; /* Allotment per round: MUST BE >= MTU */
191 + int limit;
192 + unsigned depth;
193 + unsigned hash_divisor;
194 + unsigned hash_kind;
195 +/* Variables */
196 + struct timer_list perturb_timer;
197 + int perturbation;
198 + esfq_index tail; /* Index of current slot in round */
199 + esfq_index max_depth; /* Maximal depth */
200 +
201 + esfq_index *ht; /* Hash table */
202 + esfq_index *next; /* Active slots link */
203 + short *allot; /* Current allotment per slot */
204 + unsigned short *hash; /* Hash value indexed by slots */
205 + struct sk_buff_head *qs; /* Slot queue */
206 + struct esfq_head *dep; /* Linked list of slots, indexed by depth */
207 + unsigned dyn_min; /* For dynamic divisor adjustment; minimum value seen */
208 + unsigned dyn_max; /* maximum value seen */
209 + unsigned dyn_range; /* saved range */
210 +};
211 +
212 +/* This contains the info we will hash. */
213 +struct esfq_packet_info
214 +{
215 + u32 proto; /* protocol or port */
216 + u32 src; /* source from packet header */
217 + u32 dst; /* destination from packet header */
218 + u32 ctorigsrc; /* original source from conntrack */
219 + u32 ctorigdst; /* original destination from conntrack */
220 + u32 ctreplsrc; /* reply source from conntrack */
221 + u32 ctrepldst; /* reply destination from conntrack */
222 +};
223 +
224 +static __inline__ unsigned esfq_jhash_1word(struct esfq_sched_data *q,u32 a)
225 +{
226 + return jhash_1word(a, q->perturbation) & (q->hash_divisor-1);
227 +}
228 +
229 +static __inline__ unsigned esfq_jhash_2words(struct esfq_sched_data *q, u32 a, u32 b)
230 +{
231 + return jhash_2words(a, b, q->perturbation) & (q->hash_divisor-1);
232 +}
233 +
234 +static __inline__ unsigned esfq_jhash_3words(struct esfq_sched_data *q, u32 a, u32 b, u32 c)
235 +{
236 + return jhash_3words(a, b, c, q->perturbation) & (q->hash_divisor-1);
237 +}
238 +
239 +
240 +static unsigned esfq_hash(struct esfq_sched_data *q, struct sk_buff *skb)
241 +{
242 + struct esfq_packet_info info;
243 +#ifdef CONFIG_IP_NF_CONNTRACK
244 + enum ip_conntrack_info ctinfo;
245 + struct ip_conntrack *ct = ip_conntrack_get(skb, &ctinfo);
246 +#endif
247 +
248 + switch (skb->protocol) {
249 + case __constant_htons(ETH_P_IP):
250 + {
251 + struct iphdr *iph = skb->nh.iph;
252 + info.dst = iph->daddr;
253 + info.src = iph->saddr;
254 + if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
255 + (iph->protocol == IPPROTO_TCP ||
256 + iph->protocol == IPPROTO_UDP ||
257 + iph->protocol == IPPROTO_SCTP ||
258 + iph->protocol == IPPROTO_DCCP ||
259 + iph->protocol == IPPROTO_ESP))
260 + info.proto = *(((u32*)iph) + iph->ihl);
261 + else
262 + info.proto = iph->protocol;
263 + break;
264 + }
265 + default:
266 + info.dst = (u32)(unsigned long)skb->dst;
267 + info.src = (u32)(unsigned long)skb->sk;
268 + info.proto = skb->protocol;
269 + }
270 +
271 +#ifdef CONFIG_IP_NF_CONNTRACK
272 + /* defaults if there is no conntrack info */
273 + info.ctorigsrc = info.src;
274 + info.ctorigdst = info.dst;
275 + info.ctreplsrc = info.dst;
276 + info.ctrepldst = info.src;
277 + /* collect conntrack info */
278 + IP_NF_ASSERT(ct);
279 + if (ct) {
280 + if (skb->protocol == __constant_htons(ETH_P_IP)) {
281 + info.ctorigsrc = ct->tuplehash[IP_CT_DIR_ORIGINAL].tuple.src.ip;
282 + info.ctorigdst = ct->tuplehash[IP_CT_DIR_ORIGINAL].tuple.dst.ip;
283 + info.ctreplsrc = ct->tuplehash[IP_CT_DIR_REPLY].tuple.src.ip;
284 + info.ctrepldst = ct->tuplehash[IP_CT_DIR_REPLY].tuple.dst.ip;
285 + }
286 + }
287 +#endif
288 +
289 + switch(q->hash_kind)
290 + {
291 + case TCA_SFQ_HASH_CLASSIC:
292 + return esfq_jhash_3words(q, info.dst, info.src, info.proto);
293 + case TCA_SFQ_HASH_DST:
294 + return esfq_jhash_1word(q, info.dst);
295 + case TCA_SFQ_HASH_SRC:
296 + return esfq_jhash_1word(q, info.src);
297 +#ifdef CONFIG_IP_NF_CONNTRACK
298 + case TCA_SFQ_HASH_CTORIGDST:
299 + return esfq_jhash_1word(q, info.ctorigdst);
300 + case TCA_SFQ_HASH_CTORIGSRC:
301 + return esfq_jhash_1word(q, info.ctorigsrc);
302 + case TCA_SFQ_HASH_CTREPLDST:
303 + return esfq_jhash_1word(q, info.ctrepldst);
304 + case TCA_SFQ_HASH_CTREPLSRC:
305 + return esfq_jhash_1word(q, info.ctreplsrc);
306 + case TCA_SFQ_HASH_CTNATCHG:
307 + {
308 + if (info.ctorigdst == info.ctreplsrc)
309 + return esfq_jhash_1word(q, info.ctorigsrc);
310 + else
311 + return esfq_jhash_1word(q, info.ctreplsrc);
312 + }
313 +#endif
314 + default:
315 + if (net_ratelimit())
316 + printk(KERN_WARNING "ESFQ: Unknown hash method. Falling back to classic.\n");
317 + }
318 + return esfq_jhash_3words(q, info.dst, info.src, info.proto);
319 +}
320 +
321 +static inline void esfq_link(struct esfq_sched_data *q, esfq_index x)
322 +{
323 + esfq_index p, n;
324 + int d = q->qs[x].qlen + q->depth;
325 +
326 + p = d;
327 + n = q->dep[d].next;
328 + q->dep[x].next = n;
329 + q->dep[x].prev = p;
330 + q->dep[p].next = q->dep[n].prev = x;
331 +}
332 +
333 +static inline void esfq_dec(struct esfq_sched_data *q, esfq_index x)
334 +{
335 + esfq_index p, n;
336 +
337 + n = q->dep[x].next;
338 + p = q->dep[x].prev;
339 + q->dep[p].next = n;
340 + q->dep[n].prev = p;
341 +
342 + if (n == p && q->max_depth == q->qs[x].qlen + 1)
343 + q->max_depth--;
344 +
345 + esfq_link(q, x);
346 +}
347 +
348 +static inline void esfq_inc(struct esfq_sched_data *q, esfq_index x)
349 +{
350 + esfq_index p, n;
351 + int d;
352 +
353 + n = q->dep[x].next;
354 + p = q->dep[x].prev;
355 + q->dep[p].next = n;
356 + q->dep[n].prev = p;
357 + d = q->qs[x].qlen;
358 + if (q->max_depth < d)
359 + q->max_depth = d;
360 +
361 + esfq_link(q, x);
362 +}
363 +
364 +static unsigned int esfq_drop(struct Qdisc *sch)
365 +{
366 + struct esfq_sched_data *q = qdisc_priv(sch);
367 + esfq_index d = q->max_depth;
368 + struct sk_buff *skb;
369 + unsigned int len;
370 +
371 + /* Queue is full! Find the longest slot and
372 + drop a packet from it */
373 +
374 + if (d > 1) {
375 + esfq_index x = q->dep[d+q->depth].next;
376 + skb = q->qs[x].prev;
377 + len = skb->len;
378 + __skb_unlink(skb, &q->qs[x]);
379 + kfree_skb(skb);
380 + esfq_dec(q, x);
381 + sch->q.qlen--;
382 + sch->stats.drops++;
383 + sch->stats.backlog -= len;
384 + return len;
385 + }
386 +
387 + if (d == 1) {
388 + /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
389 + d = q->next[q->tail];
390 + q->next[q->tail] = q->next[d];
391 + q->allot[q->next[d]] += q->quantum;
392 + skb = q->qs[d].prev;
393 + len = skb->len;
394 + __skb_unlink(skb, &q->qs[d]);
395 + kfree_skb(skb);
396 + esfq_dec(q, d);
397 + sch->q.qlen--;
398 + q->ht[q->hash[d]] = q->depth;
399 + sch->stats.drops++;
400 + sch->stats.backlog -= len;
401 + return len;
402 + }
403 +
404 + return 0;
405 +}
406 +
407 +static int
408 +esfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
409 +{
410 + struct esfq_sched_data *q = qdisc_priv(sch);
411 + unsigned hash = esfq_hash(q, skb);
412 + unsigned depth = q->depth;
413 + esfq_index x;
414 +
415 + x = q->ht[hash];
416 + if (x == depth) {
417 + q->ht[hash] = x = q->dep[depth].next;
418 + q->hash[x] = hash;
419 + }
420 + sch->stats.backlog += skb->len;
421 + __skb_queue_tail(&q->qs[x], skb);
422 + esfq_inc(q, x);
423 + if (q->qs[x].qlen == 1) { /* The flow is new */
424 + if (q->tail == depth) { /* It is the first flow */
425 + q->tail = x;
426 + q->next[x] = x;
427 + q->allot[x] = q->quantum;
428 + } else {
429 + q->next[x] = q->next[q->tail];
430 + q->next[q->tail] = x;
431 + q->tail = x;
432 + }
433 + }
434 + if (++sch->q.qlen < q->limit-1) {
435 + sch->stats.bytes += skb->len;
436 + sch->stats.packets++;
437 + return 0;
438 + }
439 +
440 + esfq_drop(sch);
441 + return NET_XMIT_CN;
442 +}
443 +
444 +static int
445 +esfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
446 +{
447 + struct esfq_sched_data *q = qdisc_priv(sch);
448 + unsigned hash = esfq_hash(q, skb);
449 + unsigned depth = q->depth;
450 + esfq_index x;
451 +
452 + x = q->ht[hash];
453 + if (x == depth) {
454 + q->ht[hash] = x = q->dep[depth].next;
455 + q->hash[x] = hash;
456 + }
457 + sch->stats.backlog += skb->len;
458 + __skb_queue_head(&q->qs[x], skb);
459 + esfq_inc(q, x);
460 + if (q->qs[x].qlen == 1) { /* The flow is new */
461 + if (q->tail == depth) { /* It is the first flow */
462 + q->tail = x;
463 + q->next[x] = x;
464 + q->allot[x] = q->quantum;
465 + } else {
466 + q->next[x] = q->next[q->tail];
467 + q->next[q->tail] = x;
468 + q->tail = x;
469 + }
470 + }
471 + if (++sch->q.qlen < q->limit - 1) {
472 + return 0;
473 + }
474 +
475 + sch->stats.drops++;
476 + esfq_drop(sch);
477 + return NET_XMIT_CN;
478 +}
479 +
480 +
481 +
482 +
483 +static struct sk_buff *
484 +esfq_dequeue(struct Qdisc* sch)
485 +{
486 + struct esfq_sched_data *q = qdisc_priv(sch);
487 + struct sk_buff *skb;
488 + unsigned depth = q->depth;
489 + esfq_index a, old_a;
490 +
491 + /* No active slots */
492 + if (q->tail == depth)
493 + return NULL;
494 +
495 + a = old_a = q->next[q->tail];
496 +
497 + /* Grab packet */
498 + skb = __skb_dequeue(&q->qs[a]);
499 + esfq_dec(q, a);
500 + sch->q.qlen--;
501 + sch->stats.backlog -= skb->len;
502 +
503 + /* Is the slot empty? */
504 + if (q->qs[a].qlen == 0) {
505 + q->ht[q->hash[a]] = depth;
506 + a = q->next[a];
507 + if (a == old_a) {
508 + q->tail = depth;
509 + return skb;
510 + }
511 + q->next[q->tail] = a;
512 + q->allot[a] += q->quantum;
513 + } else if ((q->allot[a] -= skb->len) <= 0) {
514 + q->tail = a;
515 + a = q->next[a];
516 + q->allot[a] += q->quantum;
517 + }
518 +
519 + return skb;
520 +}
521 +
522 +static void
523 +esfq_reset(struct Qdisc* sch)
524 +{
525 + struct sk_buff *skb;
526 +
527 + while ((skb = esfq_dequeue(sch)) != NULL)
528 + kfree_skb(skb);
529 +}
530 +
531 +static void esfq_perturbation(unsigned long arg)
532 +{
533 + struct Qdisc *sch = (struct Qdisc*)arg;
534 + struct esfq_sched_data *q = qdisc_priv(sch);
535 +
536 + q->perturbation = net_random()&0x1F;
537 +
538 + if (q->perturb_period) {
539 + q->perturb_timer.expires = jiffies + q->perturb_period;
540 + add_timer(&q->perturb_timer);
541 + }
542 +}
543 +
544 +static int esfq_change(struct Qdisc *sch, struct rtattr *opt)
545 +{
546 + struct esfq_sched_data *q = qdisc_priv(sch);
547 + struct tc_esfq_qopt *ctl = RTA_DATA(opt);
548 + int old_perturb = q->perturb_period;
549 +
550 + if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
551 + return -EINVAL;
552 +
553 + sch_tree_lock(sch);
554 + q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
555 + q->perturb_period = ctl->perturb_period*HZ;
556 +// q->hash_divisor = ctl->divisor;
557 +// q->tail = q->limit = q->depth = ctl->flows;
558 +
559 + if (ctl->limit)
560 + q->limit = min_t(u32, ctl->limit, q->depth);
561 +
562 + if (ctl->hash_kind) {
563 + q->hash_kind = ctl->hash_kind;
564 + if (q->hash_kind != TCA_SFQ_HASH_CLASSIC)
565 + q->perturb_period = 0;
566 + }
567 +
568 + // is sch_tree_lock enough to do this ?
569 + while (sch->q.qlen >= q->limit-1)
570 + esfq_drop(sch);
571 +
572 + if (old_perturb)
573 + del_timer(&q->perturb_timer);
574 + if (q->perturb_period) {
575 + q->perturb_timer.expires = jiffies + q->perturb_period;
576 + add_timer(&q->perturb_timer);
577 + } else {
578 + q->perturbation = 0;
579 + }
580 + sch_tree_unlock(sch);
581 + return 0;
582 +}
583 +
584 +static int esfq_init(struct Qdisc *sch, struct rtattr *opt)
585 +{
586 + struct esfq_sched_data *q = qdisc_priv(sch);
587 + struct tc_esfq_qopt *ctl;
588 + esfq_index p = ~0U/2;
589 + int i;
590 +
591 + if (opt && opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
592 + return -EINVAL;
593 +
594 + init_timer(&q->perturb_timer);
595 + q->perturb_timer.data = (unsigned long)sch;
596 + q->perturb_timer.function = esfq_perturbation;
597 + q->perturbation = 0;
598 + q->hash_kind = TCA_SFQ_HASH_CLASSIC;
599 + q->max_depth = 0;
600 + q->dyn_min = ~0U; /* maximum value for this type */
601 + q->dyn_max = 0; /* dyn_min/dyn_max will be set properly upon first packet */
602 + if (opt == NULL) {
603 + q->quantum = psched_mtu(sch->dev);
604 + q->perturb_period = 0;
605 + q->hash_divisor = 1024;
606 + q->tail = q->limit = q->depth = 128;
607 +
608 + } else {
609 + ctl = RTA_DATA(opt);
610 + q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
611 + q->perturb_period = ctl->perturb_period*HZ;
612 + q->hash_divisor = ctl->divisor ? : 1024;
613 + q->tail = q->limit = q->depth = ctl->flows ? : 128;
614 +
615 + if ( q->depth > p - 1 )
616 + return -EINVAL;
617 +
618 + if (ctl->limit)
619 + q->limit = min_t(u32, ctl->limit, q->depth);
620 +
621 + if (ctl->hash_kind) {
622 + q->hash_kind = ctl->hash_kind;
623 + }
624 +
625 + if (q->perturb_period) {
626 + q->perturb_timer.expires = jiffies + q->perturb_period;
627 + add_timer(&q->perturb_timer);
628 + }
629 + }
630 +
631 + q->ht = kmalloc(q->hash_divisor*sizeof(esfq_index), GFP_KERNEL);
632 + if (!q->ht)
633 + goto err_case;
634 +
635 + q->dep = kmalloc((1+q->depth*2)*sizeof(struct esfq_head), GFP_KERNEL);
636 + if (!q->dep)
637 + goto err_case;
638 + q->next = kmalloc(q->depth*sizeof(esfq_index), GFP_KERNEL);
639 + if (!q->next)
640 + goto err_case;
641 +
642 + q->allot = kmalloc(q->depth*sizeof(short), GFP_KERNEL);
643 + if (!q->allot)
644 + goto err_case;
645 + q->hash = kmalloc(q->depth*sizeof(unsigned short), GFP_KERNEL);
646 + if (!q->hash)
647 + goto err_case;
648 + q->qs = kmalloc(q->depth*sizeof(struct sk_buff_head), GFP_KERNEL);
649 + if (!q->qs)
650 + goto err_case;
651 +
652 + for (i=0; i< q->hash_divisor; i++)
653 + q->ht[i] = q->depth;
654 + for (i=0; i<q->depth; i++) {
655 + skb_queue_head_init(&q->qs[i]);
656 + q->dep[i+q->depth].next = i+q->depth;
657 + q->dep[i+q->depth].prev = i+q->depth;
658 + }
659 +
660 + for (i=0; i<q->depth; i++)
661 + esfq_link(q, i);
662 + return 0;
663 +err_case:
664 + del_timer(&q->perturb_timer);
665 + if (q->ht)
666 + kfree(q->ht);
667 + if (q->dep)
668 + kfree(q->dep);
669 + if (q->next)
670 + kfree(q->next);
671 + if (q->allot)
672 + kfree(q->allot);
673 + if (q->hash)
674 + kfree(q->hash);
675 + if (q->qs)
676 + kfree(q->qs);
677 + return -ENOBUFS;
678 +}
679 +
680 +static void esfq_destroy(struct Qdisc *sch)
681 +{
682 + struct esfq_sched_data *q = qdisc_priv(sch);
683 + del_timer(&q->perturb_timer);
684 + if(q->ht)
685 + kfree(q->ht);
686 + if(q->dep)
687 + kfree(q->dep);
688 + if(q->next)
689 + kfree(q->next);
690 + if(q->allot)
691 + kfree(q->allot);
692 + if(q->hash)
693 + kfree(q->hash);
694 + if(q->qs)
695 + kfree(q->qs);
696 +}
697 +
698 +static int esfq_dump(struct Qdisc *sch, struct sk_buff *skb)
699 +{
700 + struct esfq_sched_data *q = qdisc_priv(sch);
701 + unsigned char *b = skb->tail;
702 + struct tc_esfq_qopt opt;
703 +
704 + opt.quantum = q->quantum;
705 + opt.perturb_period = q->perturb_period/HZ;
706 +
707 + opt.limit = q->limit;
708 + opt.divisor = q->hash_divisor;
709 + opt.flows = q->depth;
710 + opt.hash_kind = q->hash_kind;
711 +
712 + RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
713 +
714 + return skb->len;
715 +
716 +rtattr_failure:
717 + skb_trim(skb, b - skb->data);
718 + return -1;
719 +}
720 +
721 +static struct Qdisc_ops esfq_qdisc_ops =
722 +{
723 + .next = NULL,
724 + .cl_ops = NULL,
725 + .id = "esfq",
726 + .priv_size = sizeof(struct esfq_sched_data),
727 + .enqueue = esfq_enqueue,
728 + .dequeue = esfq_dequeue,
729 + .requeue = esfq_requeue,
730 + .drop = esfq_drop,
731 + .init = esfq_init,
732 + .reset = esfq_reset,
733 + .destroy = esfq_destroy,
734 + .change = NULL, /* esfq_change - needs more work */
735 + .dump = esfq_dump,
736 +};
737 +
738 +static int __init esfq_module_init(void)
739 +{
740 + return register_qdisc(&esfq_qdisc_ops);
741 +}
742 +static void __exit esfq_module_exit(void)
743 +{
744 + unregister_qdisc(&esfq_qdisc_ops);
745 +}
746 +module_init(esfq_module_init)
747 +module_exit(esfq_module_exit)
748 +MODULE_LICENSE("GPL");
Yousong Zhou staging tree