2 * net/sched/sch_gred.c Generic Random Early Detection queue.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * as published by the Free Software Foundation; either version
8 * 2 of the License, or (at your option) any later version.
10 * Authors: J Hadi Salim (hadi@nortelnetworks.com) 1998,1999
12 * 991129: - Bug fix with grio mode
13 * - a better sing. AvgQ mode with Grio(WRED)
14 * - A finer grained VQ dequeue based on sugestion
20 * For all the glorious comments look at Alexey's sch_red.c
23 #include <linux/config.h>
24 #include <linux/module.h>
25 #include <asm/uaccess.h>
26 #include <asm/system.h>
27 #include <asm/bitops.h>
28 #include <linux/types.h>
29 #include <linux/kernel.h>
30 #include <linux/sched.h>
31 #include <linux/string.h>
33 #include <linux/socket.h>
34 #include <linux/sockios.h>
36 #include <linux/errno.h>
37 #include <linux/interrupt.h>
38 #include <linux/if_ether.h>
39 #include <linux/inet.h>
40 #include <linux/netdevice.h>
41 #include <linux/etherdevice.h>
42 #include <linux/notifier.h>
44 #include <net/route.h>
45 #include <linux/skbuff.h>
47 #include <net/pkt_sched.h>
50 #define DPRINTK(format,args...) printk(KERN_DEBUG format,##args)
52 #define DPRINTK(format,args...)
56 #define D2PRINTK(format,args...) printk(KERN_DEBUG format,##args)
58 #define D2PRINTK(format,args...)
61 struct gred_sched_data
;
64 struct gred_sched_data
67 u32 limit
; /* HARD maximal queue length */
68 u32 qth_min
; /* Min average length threshold: A scaled */
69 u32 qth_max
; /* Max average length threshold: A scaled */
70 u32 DP
; /* the drop pramaters */
71 char Wlog
; /* log(W) */
72 char Plog
; /* random number bits */
75 u32 bytesin
; /* bytes seen on virtualQ so far*/
76 u32 packetsin
; /* packets seen on virtualQ so far*/
77 u32 backlog
; /* bytes on the virtualQ */
78 u32 forced
; /* packets dropped for exceeding limits */
79 u32 early
; /* packets dropped as a warning */
80 u32 other
; /* packets dropped by invoking drop() */
81 u32 pdrop
; /* packets dropped because we exceeded physical queue limits */
84 u8 prio
; /* the prio of this vq */
87 unsigned long qave
; /* Average queue length: A scaled */
88 int qcount
; /* Packets since last random number generation */
89 u32 qR
; /* Cached random number */
91 psched_time_t qidlestart
; /* Start of idle period */
96 struct gred_sched_data
*tab
[MAX_DPs
];
105 gred_enqueue(struct sk_buff
*skb
, struct Qdisc
* sch
)
108 struct gred_sched_data
*q
=NULL
;
109 struct gred_sched
*t
= (struct gred_sched
*)sch
->data
;
110 unsigned long qave
=0;
114 DPRINTK("NO GRED Queues setup yet! Enqueued anyway\n");
115 if (q
->backlog
<= q
->limit
) {
116 __skb_queue_tail(&sch
->q
, skb
);
117 return NET_XMIT_DROP
; /* @@@@ */
122 if ( ((skb
->tc_index
&0xf) > t
->DPs
) || !(q
=t
->tab
[skb
->tc_index
&0xf])) {
123 printk("GRED: setting to default (%d)\n ",t
->def
);
124 if (!(q
=t
->tab
[t
->def
])) {
125 DPRINTK("GRED: setting to default FAILED! dropping!! "
129 /* fix tc_index? --could be controvesial but needed for
131 skb
->tc_index
=(skb
->tc_index
&0xfffffff0) | t
->def
;
134 D2PRINTK("gred_enqueue virtualQ 0x%x classid %x backlog %d "
135 "general backlog %d\n",skb
->tc_index
&0xf,sch
->handle
,q
->backlog
,
137 /* sum up all the qaves of prios <= to ours to get the new qave*/
138 if (!t
->eqp
&& t
->grio
) {
139 for (i
=0;i
<t
->DPs
;i
++) {
140 if ((!t
->tab
[i
]) || (i
==q
->DP
))
143 if ((t
->tab
[i
]->prio
< q
->prio
) && (PSCHED_IS_PASTPERFECT(t
->tab
[i
]->qidlestart
)))
144 qave
+=t
->tab
[i
]->qave
;
150 q
->bytesin
+=skb
->len
;
152 if (t
->eqp
&& t
->grio
) {
154 q
->qave
=t
->tab
[t
->def
]->qave
;
155 q
->qidlestart
=t
->tab
[t
->def
]->qidlestart
;
158 if (!PSCHED_IS_PASTPERFECT(q
->qidlestart
)) {
160 PSCHED_GET_TIME(now
);
161 us_idle
= PSCHED_TDIFF_SAFE(now
, q
->qidlestart
, q
->Scell_max
, 0);
162 PSCHED_SET_PASTPERFECT(q
->qidlestart
);
164 q
->qave
>>= q
->Stab
[(us_idle
>>q
->Scell_log
)&0xFF];
167 q
->qave
+= sch
->stats
.backlog
- (q
->qave
>> q
->Wlog
);
169 q
->qave
+= q
->backlog
- (q
->qave
>> q
->Wlog
);
175 if (t
->eqp
&& t
->grio
)
176 t
->tab
[t
->def
]->qave
=q
->qave
;
178 if ((q
->qave
+qave
) < q
->qth_min
) {
181 if (q
->backlog
<= q
->limit
) {
182 __skb_queue_tail(&sch
->q
, skb
);
183 sch
->stats
.backlog
+= skb
->len
;
184 sch
->stats
.bytes
+= skb
->len
;
185 sch
->stats
.packets
++;
186 q
->backlog
+= skb
->len
;
195 return NET_XMIT_DROP
;
197 if ((q
->qave
+qave
) >= q
->qth_max
) {
199 sch
->stats
.overlimits
++;
204 if ((((qave
+q
->qave
) - q
->qth_min
)>>q
->Wlog
)*q
->qcount
< q
->qR
)
207 q
->qR
= net_random()&q
->Rmask
;
208 sch
->stats
.overlimits
++;
212 q
->qR
= net_random()&q
->Rmask
;
217 gred_requeue(struct sk_buff
*skb
, struct Qdisc
* sch
)
219 struct gred_sched_data
*q
;
220 struct gred_sched
*t
= (struct gred_sched
*)sch
->data
;
221 q
= t
->tab
[(skb
->tc_index
&0xf)];
222 /* error checking here -- probably unnecessary */
223 PSCHED_SET_PASTPERFECT(q
->qidlestart
);
225 __skb_queue_head(&sch
->q
, skb
);
226 sch
->stats
.backlog
+= skb
->len
;
227 q
->backlog
+= skb
->len
;
231 static struct sk_buff
*
232 gred_dequeue(struct Qdisc
* sch
)
235 struct gred_sched_data
*q
;
236 struct gred_sched
*t
= (struct gred_sched
*)sch
->data
;
238 skb
= __skb_dequeue(&sch
->q
);
240 sch
->stats
.backlog
-= skb
->len
;
241 q
= t
->tab
[(skb
->tc_index
&0xf)];
243 q
->backlog
-= skb
->len
;
244 if (!q
->backlog
&& !t
->eqp
)
245 PSCHED_GET_TIME(q
->qidlestart
);
247 D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb
->tc_index
&0xf);
255 D2PRINTK("no default VQ set: Results will be "
258 PSCHED_GET_TIME(q
->qidlestart
);
265 gred_drop(struct Qdisc
* sch
)
269 struct gred_sched_data
*q
;
270 struct gred_sched
*t
= (struct gred_sched
*)sch
->data
;
272 skb
= __skb_dequeue_tail(&sch
->q
);
274 sch
->stats
.backlog
-= skb
->len
;
276 q
= t
->tab
[(skb
->tc_index
&0xf)];
278 q
->backlog
-= skb
->len
;
280 if (!q
->backlog
&& !t
->eqp
)
281 PSCHED_GET_TIME(q
->qidlestart
);
283 D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb
->tc_index
&0xf);
292 D2PRINTK("no default VQ set: Results might be screwed up\n");
296 PSCHED_GET_TIME(q
->qidlestart
);
301 static void gred_reset(struct Qdisc
* sch
)
306 struct gred_sched_data
*q
;
307 struct gred_sched
*t
= (struct gred_sched
*)sch
->data
;
309 while((skb
=__skb_dequeue(&sch
->q
))!=NULL
)
312 sch
->stats
.backlog
= 0;
314 for (i
=0;i
<t
->DPs
;i
++) {
318 PSCHED_SET_PASTPERFECT(q
->qidlestart
);
329 static int gred_change(struct Qdisc
*sch
, struct rtattr
*opt
)
331 struct gred_sched
*table
= (struct gred_sched
*)sch
->data
;
332 struct gred_sched_data
*q
;
333 struct tc_gred_qopt
*ctl
;
334 struct tc_gred_sopt
*sopt
;
335 struct rtattr
*tb
[TCA_GRED_STAB
];
336 struct rtattr
*tb2
[TCA_GRED_STAB
];
340 rtattr_parse(tb
, TCA_GRED_STAB
, RTA_DATA(opt
), RTA_PAYLOAD(opt
)) )
343 if (tb
[TCA_GRED_PARMS
-1] == 0 && tb
[TCA_GRED_STAB
-1] == 0 &&
344 tb
[TCA_GRED_DPS
-1] != 0) {
345 rtattr_parse(tb2
, TCA_GRED_DPS
, RTA_DATA(opt
),
348 sopt
= RTA_DATA(tb2
[TCA_GRED_DPS
-1]);
349 table
->DPs
=sopt
->DPs
;
350 table
->def
=sopt
->def_DP
;
351 table
->grio
=sopt
->grio
;
353 /* probably need to clear all the table DP entries as well */
359 if (!table
->DPs
|| tb
[TCA_GRED_PARMS
-1] == 0 || tb
[TCA_GRED_STAB
-1] == 0 ||
360 RTA_PAYLOAD(tb
[TCA_GRED_PARMS
-1]) < sizeof(*ctl
) ||
361 RTA_PAYLOAD(tb
[TCA_GRED_STAB
-1]) < 256)
364 ctl
= RTA_DATA(tb
[TCA_GRED_PARMS
-1]);
365 if (ctl
->DP
> MAX_DPs
-1 ) {
366 /* misbehaving is punished! Put in the default drop probability */
367 DPRINTK("\nGRED: DP %u not in the proper range fixed. New DP "
368 "set to default at %d\n",ctl
->DP
,table
->def
);
372 if (table
->tab
[ctl
->DP
] == NULL
) {
373 table
->tab
[ctl
->DP
]=kmalloc(sizeof(struct gred_sched_data
),
375 if (NULL
== table
->tab
[ctl
->DP
])
377 memset(table
->tab
[ctl
->DP
], 0, (sizeof(struct gred_sched_data
)));
379 q
= table
->tab
[ctl
->DP
];
383 if (table
->def
&& table
->tab
[table
->def
]) {
384 DPRINTK("\nGRED: DP %u does not have a prio"
385 "setting default to %d\n",ctl
->DP
,
386 table
->tab
[table
->def
]->prio
);
387 q
->prio
=table
->tab
[table
->def
]->prio
;
389 DPRINTK("\nGRED: DP %u does not have a prio"
390 " setting default to 8\n",ctl
->DP
);
404 q
->limit
= ctl
->limit
;
405 q
->Scell_log
= ctl
->Scell_log
;
406 q
->Rmask
= ctl
->Plog
< 32 ? ((1<<ctl
->Plog
) - 1) : ~0UL;
407 q
->Scell_max
= (255<<q
->Scell_log
);
408 q
->qth_min
= ctl
->qth_min
<<ctl
->Wlog
;
409 q
->qth_max
= ctl
->qth_max
<<ctl
->Wlog
;
418 PSCHED_SET_PASTPERFECT(q
->qidlestart
);
419 memcpy(q
->Stab
, RTA_DATA(tb
[TCA_GRED_STAB
-1]), 256);
421 if ( table
->initd
&& table
->grio
) {
422 /* this looks ugly but its not in the fast path */
423 for (i
=0;i
<table
->DPs
;i
++) {
424 if ((!table
->tab
[i
]) || (i
==q
->DP
) )
426 if (table
->tab
[i
]->prio
== q
->prio
){
427 /* WRED mode detected */
437 the first entry also goes into the default until
441 if (table
->tab
[table
->def
] == NULL
) {
442 table
->tab
[table
->def
]=
443 kmalloc(sizeof(struct gred_sched_data
), GFP_KERNEL
);
444 if (NULL
== table
->tab
[ctl
->DP
])
447 memset(table
->tab
[table
->def
], 0,
448 (sizeof(struct gred_sched_data
)));
450 q
= table
->tab
[table
->def
];
454 q
->limit
= ctl
->limit
;
455 q
->Scell_log
= ctl
->Scell_log
;
456 q
->Rmask
= ctl
->Plog
< 32 ? ((1<<ctl
->Plog
) - 1) : ~0UL;
457 q
->Scell_max
= (255<<q
->Scell_log
);
458 q
->qth_min
= ctl
->qth_min
<<ctl
->Wlog
;
459 q
->qth_max
= ctl
->qth_max
<<ctl
->Wlog
;
462 q
->prio
=table
->tab
[ctl
->DP
]->prio
;
467 PSCHED_SET_PASTPERFECT(q
->qidlestart
);
468 memcpy(q
->Stab
, RTA_DATA(tb
[TCA_GRED_STAB
-1]), 256);
474 static int gred_init(struct Qdisc
*sch
, struct rtattr
*opt
)
476 struct gred_sched
*table
= (struct gred_sched
*)sch
->data
;
477 struct tc_gred_sopt
*sopt
;
478 struct rtattr
*tb
[TCA_GRED_STAB
];
479 struct rtattr
*tb2
[TCA_GRED_STAB
];
482 rtattr_parse(tb
, TCA_GRED_STAB
, RTA_DATA(opt
), RTA_PAYLOAD(opt
)) )
485 if (tb
[TCA_GRED_PARMS
-1] == 0 && tb
[TCA_GRED_STAB
-1] == 0 &&
486 tb
[TCA_GRED_DPS
-1] != 0) {
487 rtattr_parse(tb2
, TCA_GRED_DPS
, RTA_DATA(opt
),RTA_PAYLOAD(opt
));
489 sopt
= RTA_DATA(tb2
[TCA_GRED_DPS
-1]);
490 table
->DPs
=sopt
->DPs
;
491 table
->def
=sopt
->def_DP
;
492 table
->grio
=sopt
->grio
;
498 DPRINTK("\n GRED_INIT error!\n");
502 #ifdef CONFIG_RTNETLINK
503 static int gred_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
507 struct tc_gred_qopt
*opt
;
508 struct tc_gred_qopt
*dst
;
509 struct gred_sched
*table
= (struct gred_sched
*)sch
->data
;
510 struct gred_sched_data
*q
;
512 unsigned char *b
= skb
->tail
;
514 rta
= (struct rtattr
*)b
;
515 RTA_PUT(skb
, TCA_OPTIONS
, 0, NULL
);
517 opt
=kmalloc(sizeof(struct tc_gred_qopt
)*MAX_DPs
, GFP_KERNEL
);
520 DPRINTK("gred_dump:failed to malloc for %Zd\n",
521 sizeof(struct tc_gred_qopt
)*MAX_DPs
);
525 memset(opt
, 0, (sizeof(struct tc_gred_qopt
))*table
->DPs
);
528 DPRINTK("NO GRED Queues setup!\n");
532 for (i
=0;i
<MAX_DPs
;i
++) {
537 /* hack -- fix at some point with proper message
538 This is how we indicate to tc that there is no VQ
546 dst
->qth_min
=q
->qth_min
>>q
->Wlog
;
547 dst
->qth_max
=q
->qth_max
>>q
->Wlog
;
549 dst
->backlog
=q
->backlog
;
551 if (table
->eqp
&& table
->grio
) {
552 q
->qidlestart
=table
->tab
[table
->def
]->qidlestart
;
553 q
->qave
=table
->tab
[table
->def
]->qave
;
555 if (!PSCHED_IS_PASTPERFECT(q
->qidlestart
)) {
558 PSCHED_GET_TIME(now
);
559 idle
= PSCHED_TDIFF_SAFE(now
, q
->qidlestart
, q
->Scell_max
, 0);
560 qave
= q
->qave
>> q
->Stab
[(idle
>>q
->Scell_log
)&0xFF];
561 dst
->qave
= qave
>> q
->Wlog
;
564 dst
->qave
= q
->qave
>> q
->Wlog
;
573 dst
->Scell_log
= q
->Scell_log
;
574 dst
->other
= q
->other
;
575 dst
->forced
= q
->forced
;
576 dst
->early
= q
->early
;
577 dst
->pdrop
= q
->pdrop
;
579 dst
->packets
=q
->packetsin
;
580 dst
->bytesin
=q
->bytesin
;
583 RTA_PUT(skb
, TCA_GRED_PARMS
, sizeof(struct tc_gred_qopt
)*MAX_DPs
, opt
);
584 rta
->rta_len
= skb
->tail
- b
;
589 DPRINTK("gred_dump: FAILURE!!!!\n");
591 /* also free the opt struct here */
592 skb_trim(skb
, b
- skb
->data
);
597 static void gred_destroy(struct Qdisc
*sch
)
599 struct gred_sched
*table
= (struct gred_sched
*)sch
->data
;
602 for (i
= 0;i
< table
->DPs
; i
++) {
604 kfree(table
->tab
[i
]);
609 struct Qdisc_ops gred_qdisc_ops
=
614 sizeof(struct gred_sched
),
622 gred_change
, /* change */
623 #ifdef CONFIG_RTNETLINK
630 int init_module(void)
632 return register_qdisc(&gred_qdisc_ops
);
635 void cleanup_module(void)
637 unregister_qdisc(&gred_qdisc_ops
);