2 * net/sched/sch_drr.c Deficit Round Robin scheduler
4 * Copyright (c) 2008 Patrick McHardy <kaber@trash.net>
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * version 2 as published by the Free Software Foundation.
11 #include <linux/module.h>
12 #include <linux/slab.h>
13 #include <linux/init.h>
14 #include <linux/errno.h>
15 #include <linux/netdevice.h>
16 #include <linux/pkt_sched.h>
17 #include <net/sch_generic.h>
18 #include <net/pkt_sched.h>
19 #include <net/pkt_cls.h>
22 struct Qdisc_class_common common
;
24 unsigned int filter_cnt
;
26 struct gnet_stats_basic_packed bstats
;
27 struct gnet_stats_queue qstats
;
28 struct net_rate_estimator __rcu
*rate_est
;
29 struct list_head alist
;
37 struct list_head active
;
38 struct tcf_proto __rcu
*filter_list
;
39 struct Qdisc_class_hash clhash
;
42 static struct drr_class
*drr_find_class(struct Qdisc
*sch
, u32 classid
)
44 struct drr_sched
*q
= qdisc_priv(sch
);
45 struct Qdisc_class_common
*clc
;
47 clc
= qdisc_class_find(&q
->clhash
, classid
);
50 return container_of(clc
, struct drr_class
, common
);
53 static void drr_purge_queue(struct drr_class
*cl
)
55 unsigned int len
= cl
->qdisc
->q
.qlen
;
56 unsigned int backlog
= cl
->qdisc
->qstats
.backlog
;
58 qdisc_reset(cl
->qdisc
);
59 qdisc_tree_reduce_backlog(cl
->qdisc
, len
, backlog
);
62 static const struct nla_policy drr_policy
[TCA_DRR_MAX
+ 1] = {
63 [TCA_DRR_QUANTUM
] = { .type
= NLA_U32
},
66 static int drr_change_class(struct Qdisc
*sch
, u32 classid
, u32 parentid
,
67 struct nlattr
**tca
, unsigned long *arg
)
69 struct drr_sched
*q
= qdisc_priv(sch
);
70 struct drr_class
*cl
= (struct drr_class
*)*arg
;
71 struct nlattr
*opt
= tca
[TCA_OPTIONS
];
72 struct nlattr
*tb
[TCA_DRR_MAX
+ 1];
79 err
= nla_parse_nested(tb
, TCA_DRR_MAX
, opt
, drr_policy
, NULL
);
83 if (tb
[TCA_DRR_QUANTUM
]) {
84 quantum
= nla_get_u32(tb
[TCA_DRR_QUANTUM
]);
88 quantum
= psched_mtu(qdisc_dev(sch
));
92 err
= gen_replace_estimator(&cl
->bstats
, NULL
,
95 qdisc_root_sleeping_running(sch
),
102 if (tb
[TCA_DRR_QUANTUM
])
103 cl
->quantum
= quantum
;
104 sch_tree_unlock(sch
);
109 cl
= kzalloc(sizeof(struct drr_class
), GFP_KERNEL
);
114 cl
->common
.classid
= classid
;
115 cl
->quantum
= quantum
;
116 cl
->qdisc
= qdisc_create_dflt(sch
->dev_queue
,
117 &pfifo_qdisc_ops
, classid
);
118 if (cl
->qdisc
== NULL
)
119 cl
->qdisc
= &noop_qdisc
;
121 qdisc_hash_add(cl
->qdisc
, true);
124 err
= gen_replace_estimator(&cl
->bstats
, NULL
, &cl
->rate_est
,
126 qdisc_root_sleeping_running(sch
),
129 qdisc_destroy(cl
->qdisc
);
136 qdisc_class_hash_insert(&q
->clhash
, &cl
->common
);
137 sch_tree_unlock(sch
);
139 qdisc_class_hash_grow(sch
, &q
->clhash
);
141 *arg
= (unsigned long)cl
;
145 static void drr_destroy_class(struct Qdisc
*sch
, struct drr_class
*cl
)
147 gen_kill_estimator(&cl
->rate_est
);
148 qdisc_destroy(cl
->qdisc
);
152 static int drr_delete_class(struct Qdisc
*sch
, unsigned long arg
)
154 struct drr_sched
*q
= qdisc_priv(sch
);
155 struct drr_class
*cl
= (struct drr_class
*)arg
;
157 if (cl
->filter_cnt
> 0)
163 qdisc_class_hash_remove(&q
->clhash
, &cl
->common
);
165 BUG_ON(--cl
->refcnt
== 0);
167 * This shouldn't happen: we "hold" one cops->get() when called
168 * from tc_ctl_tclass; the destroy method is done from cops->put().
171 sch_tree_unlock(sch
);
175 static unsigned long drr_get_class(struct Qdisc
*sch
, u32 classid
)
177 struct drr_class
*cl
= drr_find_class(sch
, classid
);
182 return (unsigned long)cl
;
185 static void drr_put_class(struct Qdisc
*sch
, unsigned long arg
)
187 struct drr_class
*cl
= (struct drr_class
*)arg
;
189 if (--cl
->refcnt
== 0)
190 drr_destroy_class(sch
, cl
);
193 static struct tcf_proto __rcu
**drr_tcf_chain(struct Qdisc
*sch
,
196 struct drr_sched
*q
= qdisc_priv(sch
);
201 return &q
->filter_list
;
204 static unsigned long drr_bind_tcf(struct Qdisc
*sch
, unsigned long parent
,
207 struct drr_class
*cl
= drr_find_class(sch
, classid
);
212 return (unsigned long)cl
;
215 static void drr_unbind_tcf(struct Qdisc
*sch
, unsigned long arg
)
217 struct drr_class
*cl
= (struct drr_class
*)arg
;
222 static int drr_graft_class(struct Qdisc
*sch
, unsigned long arg
,
223 struct Qdisc
*new, struct Qdisc
**old
)
225 struct drr_class
*cl
= (struct drr_class
*)arg
;
228 new = qdisc_create_dflt(sch
->dev_queue
,
229 &pfifo_qdisc_ops
, cl
->common
.classid
);
234 *old
= qdisc_replace(sch
, new, &cl
->qdisc
);
238 static struct Qdisc
*drr_class_leaf(struct Qdisc
*sch
, unsigned long arg
)
240 struct drr_class
*cl
= (struct drr_class
*)arg
;
245 static void drr_qlen_notify(struct Qdisc
*csh
, unsigned long arg
)
247 struct drr_class
*cl
= (struct drr_class
*)arg
;
249 if (cl
->qdisc
->q
.qlen
== 0)
250 list_del(&cl
->alist
);
253 static int drr_dump_class(struct Qdisc
*sch
, unsigned long arg
,
254 struct sk_buff
*skb
, struct tcmsg
*tcm
)
256 struct drr_class
*cl
= (struct drr_class
*)arg
;
259 tcm
->tcm_parent
= TC_H_ROOT
;
260 tcm
->tcm_handle
= cl
->common
.classid
;
261 tcm
->tcm_info
= cl
->qdisc
->handle
;
263 nest
= nla_nest_start(skb
, TCA_OPTIONS
);
265 goto nla_put_failure
;
266 if (nla_put_u32(skb
, TCA_DRR_QUANTUM
, cl
->quantum
))
267 goto nla_put_failure
;
268 return nla_nest_end(skb
, nest
);
271 nla_nest_cancel(skb
, nest
);
275 static int drr_dump_class_stats(struct Qdisc
*sch
, unsigned long arg
,
278 struct drr_class
*cl
= (struct drr_class
*)arg
;
279 __u32 qlen
= cl
->qdisc
->q
.qlen
;
280 struct tc_drr_stats xstats
;
282 memset(&xstats
, 0, sizeof(xstats
));
284 xstats
.deficit
= cl
->deficit
;
286 if (gnet_stats_copy_basic(qdisc_root_sleeping_running(sch
),
287 d
, NULL
, &cl
->bstats
) < 0 ||
288 gnet_stats_copy_rate_est(d
, &cl
->rate_est
) < 0 ||
289 gnet_stats_copy_queue(d
, NULL
, &cl
->qdisc
->qstats
, qlen
) < 0)
292 return gnet_stats_copy_app(d
, &xstats
, sizeof(xstats
));
295 static void drr_walk(struct Qdisc
*sch
, struct qdisc_walker
*arg
)
297 struct drr_sched
*q
= qdisc_priv(sch
);
298 struct drr_class
*cl
;
304 for (i
= 0; i
< q
->clhash
.hashsize
; i
++) {
305 hlist_for_each_entry(cl
, &q
->clhash
.hash
[i
], common
.hnode
) {
306 if (arg
->count
< arg
->skip
) {
310 if (arg
->fn(sch
, (unsigned long)cl
, arg
) < 0) {
319 static struct drr_class
*drr_classify(struct sk_buff
*skb
, struct Qdisc
*sch
,
322 struct drr_sched
*q
= qdisc_priv(sch
);
323 struct drr_class
*cl
;
324 struct tcf_result res
;
325 struct tcf_proto
*fl
;
328 if (TC_H_MAJ(skb
->priority
^ sch
->handle
) == 0) {
329 cl
= drr_find_class(sch
, skb
->priority
);
334 *qerr
= NET_XMIT_SUCCESS
| __NET_XMIT_BYPASS
;
335 fl
= rcu_dereference_bh(q
->filter_list
);
336 result
= tc_classify(skb
, fl
, &res
, false);
338 #ifdef CONFIG_NET_CLS_ACT
342 *qerr
= NET_XMIT_SUCCESS
| __NET_XMIT_STOLEN
;
347 cl
= (struct drr_class
*)res
.class;
349 cl
= drr_find_class(sch
, res
.classid
);
355 static int drr_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
,
356 struct sk_buff
**to_free
)
358 struct drr_sched
*q
= qdisc_priv(sch
);
359 struct drr_class
*cl
;
362 cl
= drr_classify(skb
, sch
, &err
);
364 if (err
& __NET_XMIT_BYPASS
)
365 qdisc_qstats_drop(sch
);
366 __qdisc_drop(skb
, to_free
);
370 err
= qdisc_enqueue(skb
, cl
->qdisc
, to_free
);
371 if (unlikely(err
!= NET_XMIT_SUCCESS
)) {
372 if (net_xmit_drop_count(err
)) {
374 qdisc_qstats_drop(sch
);
379 if (cl
->qdisc
->q
.qlen
== 1) {
380 list_add_tail(&cl
->alist
, &q
->active
);
381 cl
->deficit
= cl
->quantum
;
384 qdisc_qstats_backlog_inc(sch
, skb
);
389 static struct sk_buff
*drr_dequeue(struct Qdisc
*sch
)
391 struct drr_sched
*q
= qdisc_priv(sch
);
392 struct drr_class
*cl
;
396 if (list_empty(&q
->active
))
399 cl
= list_first_entry(&q
->active
, struct drr_class
, alist
);
400 skb
= cl
->qdisc
->ops
->peek(cl
->qdisc
);
402 qdisc_warn_nonwc(__func__
, cl
->qdisc
);
406 len
= qdisc_pkt_len(skb
);
407 if (len
<= cl
->deficit
) {
409 skb
= qdisc_dequeue_peeked(cl
->qdisc
);
410 if (unlikely(skb
== NULL
))
412 if (cl
->qdisc
->q
.qlen
== 0)
413 list_del(&cl
->alist
);
415 bstats_update(&cl
->bstats
, skb
);
416 qdisc_bstats_update(sch
, skb
);
417 qdisc_qstats_backlog_dec(sch
, skb
);
422 cl
->deficit
+= cl
->quantum
;
423 list_move_tail(&cl
->alist
, &q
->active
);
429 static int drr_init_qdisc(struct Qdisc
*sch
, struct nlattr
*opt
)
431 struct drr_sched
*q
= qdisc_priv(sch
);
434 err
= qdisc_class_hash_init(&q
->clhash
);
437 INIT_LIST_HEAD(&q
->active
);
441 static void drr_reset_qdisc(struct Qdisc
*sch
)
443 struct drr_sched
*q
= qdisc_priv(sch
);
444 struct drr_class
*cl
;
447 for (i
= 0; i
< q
->clhash
.hashsize
; i
++) {
448 hlist_for_each_entry(cl
, &q
->clhash
.hash
[i
], common
.hnode
) {
449 if (cl
->qdisc
->q
.qlen
)
450 list_del(&cl
->alist
);
451 qdisc_reset(cl
->qdisc
);
454 sch
->qstats
.backlog
= 0;
458 static void drr_destroy_qdisc(struct Qdisc
*sch
)
460 struct drr_sched
*q
= qdisc_priv(sch
);
461 struct drr_class
*cl
;
462 struct hlist_node
*next
;
465 tcf_destroy_chain(&q
->filter_list
);
467 for (i
= 0; i
< q
->clhash
.hashsize
; i
++) {
468 hlist_for_each_entry_safe(cl
, next
, &q
->clhash
.hash
[i
],
470 drr_destroy_class(sch
, cl
);
472 qdisc_class_hash_destroy(&q
->clhash
);
475 static const struct Qdisc_class_ops drr_class_ops
= {
476 .change
= drr_change_class
,
477 .delete = drr_delete_class
,
478 .get
= drr_get_class
,
479 .put
= drr_put_class
,
480 .tcf_chain
= drr_tcf_chain
,
481 .bind_tcf
= drr_bind_tcf
,
482 .unbind_tcf
= drr_unbind_tcf
,
483 .graft
= drr_graft_class
,
484 .leaf
= drr_class_leaf
,
485 .qlen_notify
= drr_qlen_notify
,
486 .dump
= drr_dump_class
,
487 .dump_stats
= drr_dump_class_stats
,
491 static struct Qdisc_ops drr_qdisc_ops __read_mostly
= {
492 .cl_ops
= &drr_class_ops
,
494 .priv_size
= sizeof(struct drr_sched
),
495 .enqueue
= drr_enqueue
,
496 .dequeue
= drr_dequeue
,
497 .peek
= qdisc_peek_dequeued
,
498 .init
= drr_init_qdisc
,
499 .reset
= drr_reset_qdisc
,
500 .destroy
= drr_destroy_qdisc
,
501 .owner
= THIS_MODULE
,
504 static int __init
drr_init(void)
506 return register_qdisc(&drr_qdisc_ops
);
509 static void __exit
drr_exit(void)
511 unregister_qdisc(&drr_qdisc_ops
);
514 module_init(drr_init
);
515 module_exit(drr_exit
);
516 MODULE_LICENSE("GPL");