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@cyberus.ca) 1998-2002
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 <linux/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>
51 #define DPRINTK(format,args...) printk(KERN_DEBUG format,##args)
53 #define DPRINTK(format,args...)
57 #define D2PRINTK(format,args...) printk(KERN_DEBUG format,##args)
59 #define D2PRINTK(format,args...)
62 #define GRED_DEF_PRIO (MAX_DPs / 2)
64 struct gred_sched_data
;
67 struct gred_sched_data
69 u32 limit
; /* HARD maximal queue length */
70 u32 DP
; /* the drop pramaters */
71 u32 bytesin
; /* bytes seen on virtualQ so far*/
72 u32 packetsin
; /* packets seen on virtualQ so far*/
73 u32 backlog
; /* bytes on the virtualQ */
74 u8 prio
; /* the prio of this vq */
76 struct red_parms parms
;
77 struct red_stats stats
;
87 struct gred_sched_data
*tab
[MAX_DPs
];
94 static inline int gred_wred_mode(struct gred_sched
*table
)
96 return test_bit(GRED_WRED_MODE
, &table
->flags
);
99 static inline void gred_enable_wred_mode(struct gred_sched
*table
)
101 __set_bit(GRED_WRED_MODE
, &table
->flags
);
104 static inline void gred_disable_wred_mode(struct gred_sched
*table
)
106 __clear_bit(GRED_WRED_MODE
, &table
->flags
);
109 static inline int gred_rio_mode(struct gred_sched
*table
)
111 return test_bit(GRED_RIO_MODE
, &table
->flags
);
114 static inline void gred_enable_rio_mode(struct gred_sched
*table
)
116 __set_bit(GRED_RIO_MODE
, &table
->flags
);
119 static inline void gred_disable_rio_mode(struct gred_sched
*table
)
121 __clear_bit(GRED_RIO_MODE
, &table
->flags
);
124 static inline int gred_wred_mode_check(struct Qdisc
*sch
)
126 struct gred_sched
*table
= qdisc_priv(sch
);
129 /* Really ugly O(n^2) but shouldn't be necessary too frequent. */
130 for (i
= 0; i
< table
->DPs
; i
++) {
131 struct gred_sched_data
*q
= table
->tab
[i
];
137 for (n
= 0; n
< table
->DPs
; n
++)
138 if (table
->tab
[n
] && table
->tab
[n
] != q
&&
139 table
->tab
[n
]->prio
== q
->prio
)
146 static inline unsigned int gred_backlog(struct gred_sched
*table
,
147 struct gred_sched_data
*q
,
150 if (gred_wred_mode(table
))
151 return sch
->qstats
.backlog
;
157 gred_enqueue(struct sk_buff
*skb
, struct Qdisc
* sch
)
159 struct gred_sched_data
*q
=NULL
;
160 struct gred_sched
*t
= qdisc_priv(sch
);
161 unsigned long qavg
= 0;
164 if (!t
->initd
&& skb_queue_len(&sch
->q
) < (sch
->dev
->tx_queue_len
? : 1)) {
165 D2PRINTK("NO GRED Queues setup yet! Enqueued anyway\n");
170 if ( ((skb
->tc_index
&0xf) > (t
->DPs
-1)) || !(q
=t
->tab
[skb
->tc_index
&0xf])) {
171 printk("GRED: setting to default (%d)\n ",t
->def
);
172 if (!(q
=t
->tab
[t
->def
])) {
173 DPRINTK("GRED: setting to default FAILED! dropping!! "
177 /* fix tc_index? --could be controvesial but needed for
179 skb
->tc_index
=(skb
->tc_index
&0xfffffff0) | t
->def
;
182 D2PRINTK("gred_enqueue virtualQ 0x%x classid %x backlog %d "
183 "general backlog %d\n",skb
->tc_index
&0xf,sch
->handle
,q
->backlog
,
184 sch
->qstats
.backlog
);
185 /* sum up all the qaves of prios <= to ours to get the new qave*/
186 if (!gred_wred_mode(t
) && gred_rio_mode(t
)) {
187 for (i
=0;i
<t
->DPs
;i
++) {
188 if ((!t
->tab
[i
]) || (i
==q
->DP
))
191 if (t
->tab
[i
]->prio
< q
->prio
&&
192 !red_is_idling(&t
->tab
[i
]->parms
))
193 qavg
+=t
->tab
[i
]->parms
.qavg
;
199 q
->bytesin
+=skb
->len
;
201 if (gred_wred_mode(t
)) {
203 q
->parms
.qavg
= t
->tab
[t
->def
]->parms
.qavg
;
204 q
->parms
.qidlestart
= t
->tab
[t
->def
]->parms
.qidlestart
;
207 q
->parms
.qavg
= red_calc_qavg(&q
->parms
, gred_backlog(t
, q
, sch
));
209 if (red_is_idling(&q
->parms
))
210 red_end_of_idle_period(&q
->parms
);
212 if (gred_wred_mode(t
))
213 t
->tab
[t
->def
]->parms
.qavg
= q
->parms
.qavg
;
215 switch (red_action(&q
->parms
, q
->parms
.qavg
+ qavg
)) {
220 sch
->qstats
.overlimits
++;
221 q
->stats
.prob_drop
++;
225 sch
->qstats
.overlimits
++;
226 q
->stats
.forced_drop
++;
230 if (q
->backlog
+ skb
->len
<= q
->limit
) {
231 q
->backlog
+= skb
->len
;
233 __skb_queue_tail(&sch
->q
, skb
);
234 sch
->qstats
.backlog
+= skb
->len
;
235 sch
->bstats
.bytes
+= skb
->len
;
236 sch
->bstats
.packets
++;
244 return NET_XMIT_DROP
;
248 gred_requeue(struct sk_buff
*skb
, struct Qdisc
* sch
)
250 struct gred_sched_data
*q
;
251 struct gred_sched
*t
= qdisc_priv(sch
);
252 q
= t
->tab
[(skb
->tc_index
&0xf)];
253 /* error checking here -- probably unnecessary */
255 if (red_is_idling(&q
->parms
))
256 red_end_of_idle_period(&q
->parms
);
258 __skb_queue_head(&sch
->q
, skb
);
259 sch
->qstats
.backlog
+= skb
->len
;
260 sch
->qstats
.requeues
++;
261 q
->backlog
+= skb
->len
;
265 static struct sk_buff
*
266 gred_dequeue(struct Qdisc
* sch
)
269 struct gred_sched_data
*q
;
270 struct gred_sched
*t
= qdisc_priv(sch
);
272 skb
= __skb_dequeue(&sch
->q
);
274 sch
->qstats
.backlog
-= skb
->len
;
275 q
= t
->tab
[(skb
->tc_index
&0xf)];
277 q
->backlog
-= skb
->len
;
278 if (!q
->backlog
&& !gred_wred_mode(t
))
279 red_start_of_idle_period(&q
->parms
);
281 D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb
->tc_index
&0xf);
286 if (gred_wred_mode(t
)) {
289 D2PRINTK("no default VQ set: Results will be "
292 red_start_of_idle_period(&q
->parms
);
298 static unsigned int gred_drop(struct Qdisc
* sch
)
302 struct gred_sched_data
*q
;
303 struct gred_sched
*t
= qdisc_priv(sch
);
305 skb
= __skb_dequeue_tail(&sch
->q
);
307 unsigned int len
= skb
->len
;
308 sch
->qstats
.backlog
-= len
;
310 q
= t
->tab
[(skb
->tc_index
&0xf)];
314 if (!q
->backlog
&& !gred_wred_mode(t
))
315 red_start_of_idle_period(&q
->parms
);
317 D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb
->tc_index
&0xf);
326 D2PRINTK("no default VQ set: Results might be screwed up\n");
330 red_start_of_idle_period(&q
->parms
);
335 static void gred_reset(struct Qdisc
* sch
)
338 struct gred_sched_data
*q
;
339 struct gred_sched
*t
= qdisc_priv(sch
);
341 __skb_queue_purge(&sch
->q
);
343 sch
->qstats
.backlog
= 0;
345 for (i
=0;i
<t
->DPs
;i
++) {
349 red_restart(&q
->parms
);
352 q
->stats
.forced_drop
= 0;
353 q
->stats
.prob_drop
= 0;
358 static inline void gred_destroy_vq(struct gred_sched_data
*q
)
363 static inline int gred_change_table_def(struct Qdisc
*sch
, struct rtattr
*dps
)
365 struct gred_sched
*table
= qdisc_priv(sch
);
366 struct tc_gred_sopt
*sopt
;
369 if (dps
== NULL
|| RTA_PAYLOAD(dps
) < sizeof(*sopt
))
372 sopt
= RTA_DATA(dps
);
374 if (sopt
->DPs
> MAX_DPs
|| sopt
->DPs
== 0 || sopt
->def_DP
>= sopt
->DPs
)
378 table
->DPs
= sopt
->DPs
;
379 table
->def
= sopt
->def_DP
;
382 * Every entry point to GRED is synchronized with the above code
383 * and the DP is checked against DPs, i.e. shadowed VQs can no
384 * longer be found so we can unlock right here.
386 sch_tree_unlock(sch
);
389 gred_enable_rio_mode(table
);
390 gred_disable_wred_mode(table
);
391 if (gred_wred_mode_check(sch
))
392 gred_enable_wred_mode(table
);
394 gred_disable_rio_mode(table
);
395 gred_disable_wred_mode(table
);
398 for (i
= table
->DPs
; i
< MAX_DPs
; i
++) {
400 printk(KERN_WARNING
"GRED: Warning: Destroying "
401 "shadowed VQ 0x%x\n", i
);
402 gred_destroy_vq(table
->tab
[i
]);
403 table
->tab
[i
] = NULL
;
412 static inline int gred_change_vq(struct Qdisc
*sch
, int dp
,
413 struct tc_gred_qopt
*ctl
, int prio
, u8
*stab
)
415 struct gred_sched
*table
= qdisc_priv(sch
);
416 struct gred_sched_data
*q
;
418 if (table
->tab
[dp
] == NULL
) {
419 table
->tab
[dp
] = kmalloc(sizeof(*q
), GFP_KERNEL
);
420 if (table
->tab
[dp
] == NULL
)
422 memset(table
->tab
[dp
], 0, sizeof(*q
));
428 q
->limit
= ctl
->limit
;
431 red_end_of_idle_period(&q
->parms
);
433 red_set_parms(&q
->parms
,
434 ctl
->qth_min
, ctl
->qth_max
, ctl
->Wlog
, ctl
->Plog
,
435 ctl
->Scell_log
, stab
);
438 q
->stats
.forced_drop
= 0;
439 q
->stats
.prob_drop
= 0;
445 static int gred_change(struct Qdisc
*sch
, struct rtattr
*opt
)
447 struct gred_sched
*table
= qdisc_priv(sch
);
448 struct tc_gred_qopt
*ctl
;
449 struct rtattr
*tb
[TCA_GRED_MAX
];
450 int err
= -EINVAL
, prio
= GRED_DEF_PRIO
;
453 if (opt
== NULL
|| rtattr_parse_nested(tb
, TCA_GRED_MAX
, opt
))
456 if (tb
[TCA_GRED_PARMS
-1] == NULL
&& tb
[TCA_GRED_STAB
-1] == NULL
)
457 return gred_change_table_def(sch
, opt
);
459 if (tb
[TCA_GRED_PARMS
-1] == NULL
||
460 RTA_PAYLOAD(tb
[TCA_GRED_PARMS
-1]) < sizeof(*ctl
) ||
461 tb
[TCA_GRED_STAB
-1] == NULL
||
462 RTA_PAYLOAD(tb
[TCA_GRED_STAB
-1]) < 256)
465 ctl
= RTA_DATA(tb
[TCA_GRED_PARMS
-1]);
466 stab
= RTA_DATA(tb
[TCA_GRED_STAB
-1]);
468 if (ctl
->DP
>= table
->DPs
)
471 if (gred_rio_mode(table
)) {
472 if (ctl
->prio
== 0) {
473 int def_prio
= GRED_DEF_PRIO
;
475 if (table
->tab
[table
->def
])
476 def_prio
= table
->tab
[table
->def
]->prio
;
478 printk(KERN_DEBUG
"GRED: DP %u does not have a prio "
479 "setting default to %d\n", ctl
->DP
, def_prio
);
488 err
= gred_change_vq(sch
, ctl
->DP
, ctl
, prio
, stab
);
492 if (table
->tab
[table
->def
] == NULL
) {
493 if (gred_rio_mode(table
))
494 prio
= table
->tab
[ctl
->DP
]->prio
;
496 err
= gred_change_vq(sch
, table
->def
, ctl
, prio
, stab
);
503 if (gred_rio_mode(table
)) {
504 gred_disable_wred_mode(table
);
505 if (gred_wred_mode_check(sch
))
506 gred_enable_wred_mode(table
);
512 sch_tree_unlock(sch
);
517 static int gred_init(struct Qdisc
*sch
, struct rtattr
*opt
)
519 struct rtattr
*tb
[TCA_GRED_MAX
];
521 if (opt
== NULL
|| rtattr_parse_nested(tb
, TCA_GRED_MAX
, opt
))
524 if (tb
[TCA_GRED_PARMS
-1] || tb
[TCA_GRED_STAB
-1])
527 return gred_change_table_def(sch
, tb
[TCA_GRED_DPS
-1]);
530 static int gred_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
532 struct gred_sched
*table
= qdisc_priv(sch
);
533 struct rtattr
*parms
, *opts
= NULL
;
535 struct tc_gred_sopt sopt
= {
537 .def_DP
= table
->def
,
538 .grio
= gred_rio_mode(table
),
541 opts
= RTA_NEST(skb
, TCA_OPTIONS
);
542 RTA_PUT(skb
, TCA_GRED_DPS
, sizeof(sopt
), &sopt
);
543 parms
= RTA_NEST(skb
, TCA_GRED_PARMS
);
545 for (i
= 0; i
< MAX_DPs
; i
++) {
546 struct gred_sched_data
*q
= table
->tab
[i
];
547 struct tc_gred_qopt opt
;
549 memset(&opt
, 0, sizeof(opt
));
552 /* hack -- fix at some point with proper message
553 This is how we indicate to tc that there is no VQ
556 opt
.DP
= MAX_DPs
+ i
;
560 opt
.limit
= q
->limit
;
562 opt
.backlog
= q
->backlog
;
564 opt
.qth_min
= q
->parms
.qth_min
>> q
->parms
.Wlog
;
565 opt
.qth_max
= q
->parms
.qth_max
>> q
->parms
.Wlog
;
566 opt
.Wlog
= q
->parms
.Wlog
;
567 opt
.Plog
= q
->parms
.Plog
;
568 opt
.Scell_log
= q
->parms
.Scell_log
;
569 opt
.other
= q
->stats
.other
;
570 opt
.early
= q
->stats
.prob_drop
;
571 opt
.forced
= q
->stats
.forced_drop
;
572 opt
.pdrop
= q
->stats
.pdrop
;
573 opt
.packets
= q
->packetsin
;
574 opt
.bytesin
= q
->bytesin
;
576 if (gred_wred_mode(table
)) {
577 q
->parms
.qidlestart
=
578 table
->tab
[table
->def
]->parms
.qidlestart
;
579 q
->parms
.qavg
= table
->tab
[table
->def
]->parms
.qavg
;
582 opt
.qave
= red_calc_qavg(&q
->parms
, q
->parms
.qavg
);
585 RTA_APPEND(skb
, sizeof(opt
), &opt
);
588 RTA_NEST_END(skb
, parms
);
590 return RTA_NEST_END(skb
, opts
);
593 return RTA_NEST_CANCEL(skb
, opts
);
596 static void gred_destroy(struct Qdisc
*sch
)
598 struct gred_sched
*table
= qdisc_priv(sch
);
601 for (i
= 0;i
< table
->DPs
; i
++) {
603 gred_destroy_vq(table
->tab
[i
]);
607 static struct Qdisc_ops gred_qdisc_ops
= {
611 .priv_size
= sizeof(struct gred_sched
),
612 .enqueue
= gred_enqueue
,
613 .dequeue
= gred_dequeue
,
614 .requeue
= gred_requeue
,
618 .destroy
= gred_destroy
,
619 .change
= gred_change
,
621 .owner
= THIS_MODULE
,
624 static int __init
gred_module_init(void)
626 return register_qdisc(&gred_qdisc_ops
);
628 static void __exit
gred_module_exit(void)
630 unregister_qdisc(&gred_qdisc_ops
);
632 module_init(gred_module_init
)
633 module_exit(gred_module_exit
)
634 MODULE_LICENSE("GPL");