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
18 * For all the glorious comments look at include/net/red.h
21 #include <linux/slab.h>
22 #include <linux/module.h>
23 #include <linux/types.h>
24 #include <linux/kernel.h>
25 #include <linux/skbuff.h>
26 #include <net/pkt_sched.h>
29 #define GRED_DEF_PRIO (MAX_DPs / 2)
30 #define GRED_VQ_MASK (MAX_DPs - 1)
32 struct gred_sched_data
;
35 struct gred_sched_data
{
36 u32 limit
; /* HARD maximal queue length */
37 u32 DP
; /* the drop parameters */
38 u32 bytesin
; /* bytes seen on virtualQ so far*/
39 u32 packetsin
; /* packets seen on virtualQ so far*/
40 u32 backlog
; /* bytes on the virtualQ */
41 u8 prio
; /* the prio of this vq */
43 struct red_parms parms
;
45 struct red_stats stats
;
54 struct gred_sched_data
*tab
[MAX_DPs
];
59 struct red_vars wred_set
;
62 static inline int gred_wred_mode(struct gred_sched
*table
)
64 return test_bit(GRED_WRED_MODE
, &table
->flags
);
67 static inline void gred_enable_wred_mode(struct gred_sched
*table
)
69 __set_bit(GRED_WRED_MODE
, &table
->flags
);
72 static inline void gred_disable_wred_mode(struct gred_sched
*table
)
74 __clear_bit(GRED_WRED_MODE
, &table
->flags
);
77 static inline int gred_rio_mode(struct gred_sched
*table
)
79 return test_bit(GRED_RIO_MODE
, &table
->flags
);
82 static inline void gred_enable_rio_mode(struct gred_sched
*table
)
84 __set_bit(GRED_RIO_MODE
, &table
->flags
);
87 static inline void gred_disable_rio_mode(struct gred_sched
*table
)
89 __clear_bit(GRED_RIO_MODE
, &table
->flags
);
92 static inline int gred_wred_mode_check(struct Qdisc
*sch
)
94 struct gred_sched
*table
= qdisc_priv(sch
);
97 /* Really ugly O(n^2) but shouldn't be necessary too frequent. */
98 for (i
= 0; i
< table
->DPs
; i
++) {
99 struct gred_sched_data
*q
= table
->tab
[i
];
105 for (n
= i
+ 1; n
< table
->DPs
; n
++)
106 if (table
->tab
[n
] && table
->tab
[n
]->prio
== q
->prio
)
113 static inline unsigned int gred_backlog(struct gred_sched
*table
,
114 struct gred_sched_data
*q
,
117 if (gred_wred_mode(table
))
118 return sch
->qstats
.backlog
;
123 static inline u16
tc_index_to_dp(struct sk_buff
*skb
)
125 return skb
->tc_index
& GRED_VQ_MASK
;
128 static inline void gred_load_wred_set(const struct gred_sched
*table
,
129 struct gred_sched_data
*q
)
131 q
->vars
.qavg
= table
->wred_set
.qavg
;
132 q
->vars
.qidlestart
= table
->wred_set
.qidlestart
;
135 static inline void gred_store_wred_set(struct gred_sched
*table
,
136 struct gred_sched_data
*q
)
138 table
->wred_set
.qavg
= q
->vars
.qavg
;
141 static inline int gred_use_ecn(struct gred_sched
*t
)
143 return t
->red_flags
& TC_RED_ECN
;
146 static inline int gred_use_harddrop(struct gred_sched
*t
)
148 return t
->red_flags
& TC_RED_HARDDROP
;
151 static int gred_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
)
153 struct gred_sched_data
*q
= NULL
;
154 struct gred_sched
*t
= qdisc_priv(sch
);
155 unsigned long qavg
= 0;
156 u16 dp
= tc_index_to_dp(skb
);
158 if (dp
>= t
->DPs
|| (q
= t
->tab
[dp
]) == NULL
) {
163 /* Pass through packets not assigned to a DP
164 * if no default DP has been configured. This
165 * allows for DP flows to be left untouched.
167 if (skb_queue_len(&sch
->q
) < qdisc_dev(sch
)->tx_queue_len
)
168 return qdisc_enqueue_tail(skb
, sch
);
173 /* fix tc_index? --could be controversial but needed for
175 skb
->tc_index
= (skb
->tc_index
& ~GRED_VQ_MASK
) | dp
;
178 /* sum up all the qaves of prios < ours to get the new qave */
179 if (!gred_wred_mode(t
) && gred_rio_mode(t
)) {
182 for (i
= 0; i
< t
->DPs
; i
++) {
183 if (t
->tab
[i
] && t
->tab
[i
]->prio
< q
->prio
&&
184 !red_is_idling(&t
->tab
[i
]->vars
))
185 qavg
+= t
->tab
[i
]->vars
.qavg
;
191 q
->bytesin
+= qdisc_pkt_len(skb
);
193 if (gred_wred_mode(t
))
194 gred_load_wred_set(t
, q
);
196 q
->vars
.qavg
= red_calc_qavg(&q
->parms
,
198 gred_backlog(t
, q
, sch
));
200 if (red_is_idling(&q
->vars
))
201 red_end_of_idle_period(&q
->vars
);
203 if (gred_wred_mode(t
))
204 gred_store_wred_set(t
, q
);
206 switch (red_action(&q
->parms
, &q
->vars
, q
->vars
.qavg
+ qavg
)) {
211 sch
->qstats
.overlimits
++;
212 if (!gred_use_ecn(t
) || !INET_ECN_set_ce(skb
)) {
213 q
->stats
.prob_drop
++;
214 goto congestion_drop
;
217 q
->stats
.prob_mark
++;
221 sch
->qstats
.overlimits
++;
222 if (gred_use_harddrop(t
) || !gred_use_ecn(t
) ||
223 !INET_ECN_set_ce(skb
)) {
224 q
->stats
.forced_drop
++;
225 goto congestion_drop
;
227 q
->stats
.forced_mark
++;
231 if (q
->backlog
+ qdisc_pkt_len(skb
) <= q
->limit
) {
232 q
->backlog
+= qdisc_pkt_len(skb
);
233 return qdisc_enqueue_tail(skb
, sch
);
238 return qdisc_drop(skb
, sch
);
241 qdisc_drop(skb
, sch
);
245 static struct sk_buff
*gred_dequeue(struct Qdisc
*sch
)
248 struct gred_sched
*t
= qdisc_priv(sch
);
250 skb
= qdisc_dequeue_head(sch
);
253 struct gred_sched_data
*q
;
254 u16 dp
= tc_index_to_dp(skb
);
256 if (dp
>= t
->DPs
|| (q
= t
->tab
[dp
]) == NULL
) {
257 net_warn_ratelimited("GRED: Unable to relocate VQ 0x%x after dequeue, screwing up backlog\n",
258 tc_index_to_dp(skb
));
260 q
->backlog
-= qdisc_pkt_len(skb
);
262 if (!q
->backlog
&& !gred_wred_mode(t
))
263 red_start_of_idle_period(&q
->vars
);
269 if (gred_wred_mode(t
) && !red_is_idling(&t
->wred_set
))
270 red_start_of_idle_period(&t
->wred_set
);
275 static unsigned int gred_drop(struct Qdisc
*sch
)
278 struct gred_sched
*t
= qdisc_priv(sch
);
280 skb
= qdisc_dequeue_tail(sch
);
282 unsigned int len
= qdisc_pkt_len(skb
);
283 struct gred_sched_data
*q
;
284 u16 dp
= tc_index_to_dp(skb
);
286 if (dp
>= t
->DPs
|| (q
= t
->tab
[dp
]) == NULL
) {
287 net_warn_ratelimited("GRED: Unable to relocate VQ 0x%x while dropping, screwing up backlog\n",
288 tc_index_to_dp(skb
));
293 if (!q
->backlog
&& !gred_wred_mode(t
))
294 red_start_of_idle_period(&q
->vars
);
297 qdisc_drop(skb
, sch
);
301 if (gred_wred_mode(t
) && !red_is_idling(&t
->wred_set
))
302 red_start_of_idle_period(&t
->wred_set
);
308 static void gred_reset(struct Qdisc
*sch
)
311 struct gred_sched
*t
= qdisc_priv(sch
);
313 qdisc_reset_queue(sch
);
315 for (i
= 0; i
< t
->DPs
; i
++) {
316 struct gred_sched_data
*q
= t
->tab
[i
];
321 red_restart(&q
->vars
);
326 static inline void gred_destroy_vq(struct gred_sched_data
*q
)
331 static inline int gred_change_table_def(struct Qdisc
*sch
, struct nlattr
*dps
)
333 struct gred_sched
*table
= qdisc_priv(sch
);
334 struct tc_gred_sopt
*sopt
;
340 sopt
= nla_data(dps
);
342 if (sopt
->DPs
> MAX_DPs
|| sopt
->DPs
== 0 || sopt
->def_DP
>= sopt
->DPs
)
346 table
->DPs
= sopt
->DPs
;
347 table
->def
= sopt
->def_DP
;
348 table
->red_flags
= sopt
->flags
;
351 * Every entry point to GRED is synchronized with the above code
352 * and the DP is checked against DPs, i.e. shadowed VQs can no
353 * longer be found so we can unlock right here.
355 sch_tree_unlock(sch
);
358 gred_enable_rio_mode(table
);
359 gred_disable_wred_mode(table
);
360 if (gred_wred_mode_check(sch
))
361 gred_enable_wred_mode(table
);
363 gred_disable_rio_mode(table
);
364 gred_disable_wred_mode(table
);
367 for (i
= table
->DPs
; i
< MAX_DPs
; i
++) {
369 pr_warning("GRED: Warning: Destroying "
370 "shadowed VQ 0x%x\n", i
);
371 gred_destroy_vq(table
->tab
[i
]);
372 table
->tab
[i
] = NULL
;
379 static inline int gred_change_vq(struct Qdisc
*sch
, int dp
,
380 struct tc_gred_qopt
*ctl
, int prio
,
382 struct gred_sched_data
**prealloc
)
384 struct gred_sched
*table
= qdisc_priv(sch
);
385 struct gred_sched_data
*q
= table
->tab
[dp
];
388 table
->tab
[dp
] = q
= *prealloc
;
396 q
->limit
= ctl
->limit
;
399 red_end_of_idle_period(&q
->vars
);
401 red_set_parms(&q
->parms
,
402 ctl
->qth_min
, ctl
->qth_max
, ctl
->Wlog
, ctl
->Plog
,
403 ctl
->Scell_log
, stab
, max_P
);
404 red_set_vars(&q
->vars
);
408 static const struct nla_policy gred_policy
[TCA_GRED_MAX
+ 1] = {
409 [TCA_GRED_PARMS
] = { .len
= sizeof(struct tc_gred_qopt
) },
410 [TCA_GRED_STAB
] = { .len
= 256 },
411 [TCA_GRED_DPS
] = { .len
= sizeof(struct tc_gred_sopt
) },
412 [TCA_GRED_MAX_P
] = { .type
= NLA_U32
},
415 static int gred_change(struct Qdisc
*sch
, struct nlattr
*opt
)
417 struct gred_sched
*table
= qdisc_priv(sch
);
418 struct tc_gred_qopt
*ctl
;
419 struct nlattr
*tb
[TCA_GRED_MAX
+ 1];
420 int err
, prio
= GRED_DEF_PRIO
;
423 struct gred_sched_data
*prealloc
;
428 err
= nla_parse_nested(tb
, TCA_GRED_MAX
, opt
, gred_policy
);
432 if (tb
[TCA_GRED_PARMS
] == NULL
&& tb
[TCA_GRED_STAB
] == NULL
)
433 return gred_change_table_def(sch
, opt
);
435 if (tb
[TCA_GRED_PARMS
] == NULL
||
436 tb
[TCA_GRED_STAB
] == NULL
)
439 max_P
= tb
[TCA_GRED_MAX_P
] ? nla_get_u32(tb
[TCA_GRED_MAX_P
]) : 0;
442 ctl
= nla_data(tb
[TCA_GRED_PARMS
]);
443 stab
= nla_data(tb
[TCA_GRED_STAB
]);
445 if (ctl
->DP
>= table
->DPs
)
448 if (gred_rio_mode(table
)) {
449 if (ctl
->prio
== 0) {
450 int def_prio
= GRED_DEF_PRIO
;
452 if (table
->tab
[table
->def
])
453 def_prio
= table
->tab
[table
->def
]->prio
;
455 printk(KERN_DEBUG
"GRED: DP %u does not have a prio "
456 "setting default to %d\n", ctl
->DP
, def_prio
);
463 prealloc
= kzalloc(sizeof(*prealloc
), GFP_KERNEL
);
466 err
= gred_change_vq(sch
, ctl
->DP
, ctl
, prio
, stab
, max_P
, &prealloc
);
470 if (gred_rio_mode(table
)) {
471 gred_disable_wred_mode(table
);
472 if (gred_wred_mode_check(sch
))
473 gred_enable_wred_mode(table
);
479 sch_tree_unlock(sch
);
485 static int gred_init(struct Qdisc
*sch
, struct nlattr
*opt
)
487 struct nlattr
*tb
[TCA_GRED_MAX
+ 1];
493 err
= nla_parse_nested(tb
, TCA_GRED_MAX
, opt
, gred_policy
);
497 if (tb
[TCA_GRED_PARMS
] || tb
[TCA_GRED_STAB
])
500 return gred_change_table_def(sch
, tb
[TCA_GRED_DPS
]);
503 static int gred_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
505 struct gred_sched
*table
= qdisc_priv(sch
);
506 struct nlattr
*parms
, *opts
= NULL
;
509 struct tc_gred_sopt sopt
= {
511 .def_DP
= table
->def
,
512 .grio
= gred_rio_mode(table
),
513 .flags
= table
->red_flags
,
516 opts
= nla_nest_start(skb
, TCA_OPTIONS
);
518 goto nla_put_failure
;
519 if (nla_put(skb
, TCA_GRED_DPS
, sizeof(sopt
), &sopt
))
520 goto nla_put_failure
;
522 for (i
= 0; i
< MAX_DPs
; i
++) {
523 struct gred_sched_data
*q
= table
->tab
[i
];
525 max_p
[i
] = q
? q
->parms
.max_P
: 0;
527 if (nla_put(skb
, TCA_GRED_MAX_P
, sizeof(max_p
), max_p
))
528 goto nla_put_failure
;
530 parms
= nla_nest_start(skb
, TCA_GRED_PARMS
);
532 goto nla_put_failure
;
534 for (i
= 0; i
< MAX_DPs
; i
++) {
535 struct gred_sched_data
*q
= table
->tab
[i
];
536 struct tc_gred_qopt opt
;
538 memset(&opt
, 0, sizeof(opt
));
541 /* hack -- fix at some point with proper message
542 This is how we indicate to tc that there is no VQ
545 opt
.DP
= MAX_DPs
+ i
;
549 opt
.limit
= q
->limit
;
551 opt
.backlog
= q
->backlog
;
553 opt
.qth_min
= q
->parms
.qth_min
>> q
->parms
.Wlog
;
554 opt
.qth_max
= q
->parms
.qth_max
>> q
->parms
.Wlog
;
555 opt
.Wlog
= q
->parms
.Wlog
;
556 opt
.Plog
= q
->parms
.Plog
;
557 opt
.Scell_log
= q
->parms
.Scell_log
;
558 opt
.other
= q
->stats
.other
;
559 opt
.early
= q
->stats
.prob_drop
;
560 opt
.forced
= q
->stats
.forced_drop
;
561 opt
.pdrop
= q
->stats
.pdrop
;
562 opt
.packets
= q
->packetsin
;
563 opt
.bytesin
= q
->bytesin
;
565 if (gred_wred_mode(table
))
566 gred_load_wred_set(table
, q
);
568 opt
.qave
= red_calc_qavg(&q
->parms
, &q
->vars
, q
->vars
.qavg
);
571 if (nla_append(skb
, sizeof(opt
), &opt
) < 0)
572 goto nla_put_failure
;
575 nla_nest_end(skb
, parms
);
577 return nla_nest_end(skb
, opts
);
580 nla_nest_cancel(skb
, opts
);
584 static void gred_destroy(struct Qdisc
*sch
)
586 struct gred_sched
*table
= qdisc_priv(sch
);
589 for (i
= 0; i
< table
->DPs
; i
++) {
591 gred_destroy_vq(table
->tab
[i
]);
595 static struct Qdisc_ops gred_qdisc_ops __read_mostly
= {
597 .priv_size
= sizeof(struct gred_sched
),
598 .enqueue
= gred_enqueue
,
599 .dequeue
= gred_dequeue
,
600 .peek
= qdisc_peek_head
,
604 .destroy
= gred_destroy
,
605 .change
= gred_change
,
607 .owner
= THIS_MODULE
,
610 static int __init
gred_module_init(void)
612 return register_qdisc(&gred_qdisc_ops
);
615 static void __exit
gred_module_exit(void)
617 unregister_qdisc(&gred_qdisc_ops
);
620 module_init(gred_module_init
)
621 module_exit(gred_module_exit
)
623 MODULE_LICENSE("GPL");