Blame view
net/sched/sch_drr.c
11.3 KB
13d2a1d2b pkt_sched: add DR... |
1 2 3 4 5 6 7 8 9 10 11 |
/* * net/sched/sch_drr.c Deficit Round Robin scheduler * * Copyright (c) 2008 Patrick McHardy <kaber@trash.net> * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * version 2 as published by the Free Software Foundation. */ #include <linux/module.h> |
5a0e3ad6a include cleanup: ... |
12 |
#include <linux/slab.h> |
13d2a1d2b pkt_sched: add DR... |
13 14 15 16 17 18 19 20 21 22 23 24 |
#include <linux/init.h> #include <linux/errno.h> #include <linux/netdevice.h> #include <linux/pkt_sched.h> #include <net/sch_generic.h> #include <net/pkt_sched.h> #include <net/pkt_cls.h> struct drr_class { struct Qdisc_class_common common; unsigned int refcnt; unsigned int filter_cnt; |
c1a8f1f1c net: restore gnet... |
25 |
struct gnet_stats_basic_packed bstats; |
13d2a1d2b pkt_sched: add DR... |
26 |
struct gnet_stats_queue qstats; |
45203a3b3 net_sched: add 64... |
27 |
struct gnet_stats_rate_est64 rate_est; |
13d2a1d2b pkt_sched: add DR... |
28 29 30 31 32 33 34 35 36 |
struct list_head alist; struct Qdisc *qdisc; u32 quantum; u32 deficit; }; struct drr_sched { struct list_head active; |
25d8c0d55 net: rcu-ify tcf_... |
37 |
struct tcf_proto __rcu *filter_list; |
13d2a1d2b pkt_sched: add DR... |
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
struct Qdisc_class_hash clhash; }; static struct drr_class *drr_find_class(struct Qdisc *sch, u32 classid) { struct drr_sched *q = qdisc_priv(sch); struct Qdisc_class_common *clc; clc = qdisc_class_find(&q->clhash, classid); if (clc == NULL) return NULL; return container_of(clc, struct drr_class, common); } static void drr_purge_queue(struct drr_class *cl) { unsigned int len = cl->qdisc->q.qlen; |
2ccccf5fb net_sched: update... |
55 |
unsigned int backlog = cl->qdisc->qstats.backlog; |
13d2a1d2b pkt_sched: add DR... |
56 57 |
qdisc_reset(cl->qdisc); |
2ccccf5fb net_sched: update... |
58 |
qdisc_tree_reduce_backlog(cl->qdisc, len, backlog); |
13d2a1d2b pkt_sched: add DR... |
59 60 61 62 63 64 65 66 67 68 69 |
} static const struct nla_policy drr_policy[TCA_DRR_MAX + 1] = { [TCA_DRR_QUANTUM] = { .type = NLA_U32 }, }; static int drr_change_class(struct Qdisc *sch, u32 classid, u32 parentid, struct nlattr **tca, unsigned long *arg) { struct drr_sched *q = qdisc_priv(sch); struct drr_class *cl = (struct drr_class *)*arg; |
1844f7479 pkt_sched: sch_dr... |
70 |
struct nlattr *opt = tca[TCA_OPTIONS]; |
13d2a1d2b pkt_sched: add DR... |
71 72 73 |
struct nlattr *tb[TCA_DRR_MAX + 1]; u32 quantum; int err; |
1844f7479 pkt_sched: sch_dr... |
74 75 76 77 |
if (!opt) return -EINVAL; err = nla_parse_nested(tb, TCA_DRR_MAX, opt, drr_policy); |
13d2a1d2b pkt_sched: add DR... |
78 79 80 81 82 83 84 85 86 87 88 |
if (err < 0) return err; if (tb[TCA_DRR_QUANTUM]) { quantum = nla_get_u32(tb[TCA_DRR_QUANTUM]); if (quantum == 0) return -EINVAL; } else quantum = psched_mtu(qdisc_dev(sch)); if (cl != NULL) { |
71bcb09a5 tc: check for err... |
89 |
if (tca[TCA_RATE]) { |
22e0f8b93 net: sched: make ... |
90 91 |
err = gen_replace_estimator(&cl->bstats, NULL, &cl->rate_est, |
edb09eb17 net: sched: do no... |
92 93 |
NULL, qdisc_root_sleeping_running(sch), |
71bcb09a5 tc: check for err... |
94 95 96 97 |
tca[TCA_RATE]); if (err) return err; } |
13d2a1d2b pkt_sched: add DR... |
98 99 100 101 |
sch_tree_lock(sch); if (tb[TCA_DRR_QUANTUM]) cl->quantum = quantum; sch_tree_unlock(sch); |
13d2a1d2b pkt_sched: add DR... |
102 103 104 105 106 107 108 109 110 111 |
return 0; } cl = kzalloc(sizeof(struct drr_class), GFP_KERNEL); if (cl == NULL) return -ENOBUFS; cl->refcnt = 1; cl->common.classid = classid; cl->quantum = quantum; |
3511c9132 net_sched: remove... |
112 |
cl->qdisc = qdisc_create_dflt(sch->dev_queue, |
13d2a1d2b pkt_sched: add DR... |
113 114 115 |
&pfifo_qdisc_ops, classid); if (cl->qdisc == NULL) cl->qdisc = &noop_qdisc; |
71bcb09a5 tc: check for err... |
116 |
if (tca[TCA_RATE]) { |
22e0f8b93 net: sched: make ... |
117 |
err = gen_replace_estimator(&cl->bstats, NULL, &cl->rate_est, |
edb09eb17 net: sched: do no... |
118 119 |
NULL, qdisc_root_sleeping_running(sch), |
71bcb09a5 tc: check for err... |
120 121 122 123 124 125 126 |
tca[TCA_RATE]); if (err) { qdisc_destroy(cl->qdisc); kfree(cl); return err; } } |
13d2a1d2b pkt_sched: add DR... |
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 |
sch_tree_lock(sch); qdisc_class_hash_insert(&q->clhash, &cl->common); sch_tree_unlock(sch); qdisc_class_hash_grow(sch, &q->clhash); *arg = (unsigned long)cl; return 0; } static void drr_destroy_class(struct Qdisc *sch, struct drr_class *cl) { gen_kill_estimator(&cl->bstats, &cl->rate_est); qdisc_destroy(cl->qdisc); kfree(cl); } static int drr_delete_class(struct Qdisc *sch, unsigned long arg) { struct drr_sched *q = qdisc_priv(sch); struct drr_class *cl = (struct drr_class *)arg; if (cl->filter_cnt > 0) return -EBUSY; sch_tree_lock(sch); drr_purge_queue(cl); qdisc_class_hash_remove(&q->clhash, &cl->common); |
7cd0a6387 pkt_sched: Change... |
157 158 159 160 161 |
BUG_ON(--cl->refcnt == 0); /* * This shouldn't happen: we "hold" one cops->get() when called * from tc_ctl_tclass; the destroy method is done from cops->put(). */ |
13d2a1d2b pkt_sched: add DR... |
162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 |
sch_tree_unlock(sch); return 0; } static unsigned long drr_get_class(struct Qdisc *sch, u32 classid) { struct drr_class *cl = drr_find_class(sch, classid); if (cl != NULL) cl->refcnt++; return (unsigned long)cl; } static void drr_put_class(struct Qdisc *sch, unsigned long arg) { struct drr_class *cl = (struct drr_class *)arg; if (--cl->refcnt == 0) drr_destroy_class(sch, cl); } |
25d8c0d55 net: rcu-ify tcf_... |
184 185 |
static struct tcf_proto __rcu **drr_tcf_chain(struct Qdisc *sch, unsigned long cl) |
13d2a1d2b pkt_sched: add DR... |
186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 |
{ struct drr_sched *q = qdisc_priv(sch); if (cl) return NULL; return &q->filter_list; } static unsigned long drr_bind_tcf(struct Qdisc *sch, unsigned long parent, u32 classid) { struct drr_class *cl = drr_find_class(sch, classid); if (cl != NULL) cl->filter_cnt++; return (unsigned long)cl; } static void drr_unbind_tcf(struct Qdisc *sch, unsigned long arg) { struct drr_class *cl = (struct drr_class *)arg; cl->filter_cnt--; } static int drr_graft_class(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, struct Qdisc **old) { struct drr_class *cl = (struct drr_class *)arg; if (new == NULL) { |
3511c9132 net_sched: remove... |
219 |
new = qdisc_create_dflt(sch->dev_queue, |
13d2a1d2b pkt_sched: add DR... |
220 221 222 223 |
&pfifo_qdisc_ops, cl->common.classid); if (new == NULL) new = &noop_qdisc; } |
86a7996cc net_sched: introd... |
224 |
*old = qdisc_replace(sch, new, &cl->qdisc); |
13d2a1d2b pkt_sched: add DR... |
225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 |
return 0; } static struct Qdisc *drr_class_leaf(struct Qdisc *sch, unsigned long arg) { struct drr_class *cl = (struct drr_class *)arg; return cl->qdisc; } static void drr_qlen_notify(struct Qdisc *csh, unsigned long arg) { struct drr_class *cl = (struct drr_class *)arg; if (cl->qdisc->q.qlen == 0) list_del(&cl->alist); } static int drr_dump_class(struct Qdisc *sch, unsigned long arg, struct sk_buff *skb, struct tcmsg *tcm) { struct drr_class *cl = (struct drr_class *)arg; struct nlattr *nest; tcm->tcm_parent = TC_H_ROOT; tcm->tcm_handle = cl->common.classid; tcm->tcm_info = cl->qdisc->handle; nest = nla_nest_start(skb, TCA_OPTIONS); if (nest == NULL) goto nla_put_failure; |
1b34ec43c pkt_sched: Stop u... |
256 257 |
if (nla_put_u32(skb, TCA_DRR_QUANTUM, cl->quantum)) goto nla_put_failure; |
13d2a1d2b pkt_sched: add DR... |
258 259 260 261 262 263 264 265 266 267 268 |
return nla_nest_end(skb, nest); nla_put_failure: nla_nest_cancel(skb, nest); return -EMSGSIZE; } static int drr_dump_class_stats(struct Qdisc *sch, unsigned long arg, struct gnet_dump *d) { struct drr_class *cl = (struct drr_class *)arg; |
640158536 net: sched: restr... |
269 |
__u32 qlen = cl->qdisc->q.qlen; |
13d2a1d2b pkt_sched: add DR... |
270 271 272 |
struct tc_drr_stats xstats; memset(&xstats, 0, sizeof(xstats)); |
640158536 net: sched: restr... |
273 |
if (qlen) |
13d2a1d2b pkt_sched: add DR... |
274 |
xstats.deficit = cl->deficit; |
edb09eb17 net: sched: do no... |
275 276 |
if (gnet_stats_copy_basic(qdisc_root_sleeping_running(sch), d, NULL, &cl->bstats) < 0 || |
d250a5f90 pkt_sched: gen_es... |
277 |
gnet_stats_copy_rate_est(d, &cl->bstats, &cl->rate_est) < 0 || |
b0ab6f927 net: sched: enabl... |
278 |
gnet_stats_copy_queue(d, NULL, &cl->qdisc->qstats, qlen) < 0) |
13d2a1d2b pkt_sched: add DR... |
279 280 281 282 283 284 285 286 287 |
return -1; return gnet_stats_copy_app(d, &xstats, sizeof(xstats)); } static void drr_walk(struct Qdisc *sch, struct qdisc_walker *arg) { struct drr_sched *q = qdisc_priv(sch); struct drr_class *cl; |
13d2a1d2b pkt_sched: add DR... |
288 289 290 291 292 293 |
unsigned int i; if (arg->stop) return; for (i = 0; i < q->clhash.hashsize; i++) { |
b67bfe0d4 hlist: drop the n... |
294 |
hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { |
13d2a1d2b pkt_sched: add DR... |
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 |
if (arg->count < arg->skip) { arg->count++; continue; } if (arg->fn(sch, (unsigned long)cl, arg) < 0) { arg->stop = 1; return; } arg->count++; } } } static struct drr_class *drr_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr) { struct drr_sched *q = qdisc_priv(sch); struct drr_class *cl; struct tcf_result res; |
25d8c0d55 net: rcu-ify tcf_... |
314 |
struct tcf_proto *fl; |
13d2a1d2b pkt_sched: add DR... |
315 316 317 318 319 320 321 322 323 |
int result; if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) { cl = drr_find_class(sch, skb->priority); if (cl != NULL) return cl; } *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; |
25d8c0d55 net: rcu-ify tcf_... |
324 |
fl = rcu_dereference_bh(q->filter_list); |
3b3ae8802 net: sched: conso... |
325 |
result = tc_classify(skb, fl, &res, false); |
13d2a1d2b pkt_sched: add DR... |
326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 |
if (result >= 0) { #ifdef CONFIG_NET_CLS_ACT switch (result) { case TC_ACT_QUEUED: case TC_ACT_STOLEN: *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN; case TC_ACT_SHOT: return NULL; } #endif cl = (struct drr_class *)res.class; if (cl == NULL) cl = drr_find_class(sch, res.classid); return cl; } return NULL; } |
520ac30f4 net_sched: drop p... |
343 344 |
static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch, struct sk_buff **to_free) |
13d2a1d2b pkt_sched: add DR... |
345 346 347 |
{ struct drr_sched *q = qdisc_priv(sch); struct drr_class *cl; |
f54ba7798 pkt_sched: Fix wa... |
348 |
int err = 0; |
13d2a1d2b pkt_sched: add DR... |
349 350 351 352 |
cl = drr_classify(skb, sch, &err); if (cl == NULL) { if (err & __NET_XMIT_BYPASS) |
25331d6ce net: sched: imple... |
353 |
qdisc_qstats_drop(sch); |
520ac30f4 net_sched: drop p... |
354 |
__qdisc_drop(skb, to_free); |
13d2a1d2b pkt_sched: add DR... |
355 356 |
return err; } |
520ac30f4 net_sched: drop p... |
357 |
err = qdisc_enqueue(skb, cl->qdisc, to_free); |
13d2a1d2b pkt_sched: add DR... |
358 359 360 |
if (unlikely(err != NET_XMIT_SUCCESS)) { if (net_xmit_drop_count(err)) { cl->qstats.drops++; |
25331d6ce net: sched: imple... |
361 |
qdisc_qstats_drop(sch); |
13d2a1d2b pkt_sched: add DR... |
362 363 364 365 366 367 368 369 |
} return err; } if (cl->qdisc->q.qlen == 1) { list_add_tail(&cl->alist, &q->active); cl->deficit = cl->quantum; } |
6a73b571b sch_drr: update b... |
370 |
qdisc_qstats_backlog_inc(sch, skb); |
13d2a1d2b pkt_sched: add DR... |
371 372 373 374 375 376 377 378 379 380 |
sch->q.qlen++; return err; } static struct sk_buff *drr_dequeue(struct Qdisc *sch) { struct drr_sched *q = qdisc_priv(sch); struct drr_class *cl; struct sk_buff *skb; unsigned int len; |
3f0947c3f pkt_sched: sch_dr... |
381 382 383 |
if (list_empty(&q->active)) goto out; while (1) { |
13d2a1d2b pkt_sched: add DR... |
384 385 |
cl = list_first_entry(&q->active, struct drr_class, alist); skb = cl->qdisc->ops->peek(cl->qdisc); |
6e765a009 net_sched: drr: w... |
386 387 |
if (skb == NULL) { qdisc_warn_nonwc(__func__, cl->qdisc); |
3f0947c3f pkt_sched: sch_dr... |
388 |
goto out; |
6e765a009 net_sched: drr: w... |
389 |
} |
13d2a1d2b pkt_sched: add DR... |
390 391 392 393 394 |
len = qdisc_pkt_len(skb); if (len <= cl->deficit) { cl->deficit -= len; skb = qdisc_dequeue_peeked(cl->qdisc); |
df3eb6cd6 net_sched: drr: c... |
395 396 |
if (unlikely(skb == NULL)) goto out; |
13d2a1d2b pkt_sched: add DR... |
397 398 |
if (cl->qdisc->q.qlen == 0) list_del(&cl->alist); |
2dd875ff3 net_sched: update... |
399 400 |
bstats_update(&cl->bstats, skb); |
9190b3b32 net_sched: accura... |
401 |
qdisc_bstats_update(sch, skb); |
6a73b571b sch_drr: update b... |
402 |
qdisc_qstats_backlog_dec(sch, skb); |
13d2a1d2b pkt_sched: add DR... |
403 404 405 406 407 |
sch->q.qlen--; return skb; } cl->deficit += cl->quantum; |
13d2a1d2b pkt_sched: add DR... |
408 409 |
list_move_tail(&cl->alist, &q->active); } |
3f0947c3f pkt_sched: sch_dr... |
410 |
out: |
13d2a1d2b pkt_sched: add DR... |
411 412 |
return NULL; } |
13d2a1d2b pkt_sched: add DR... |
413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 |
static int drr_init_qdisc(struct Qdisc *sch, struct nlattr *opt) { struct drr_sched *q = qdisc_priv(sch); int err; err = qdisc_class_hash_init(&q->clhash); if (err < 0) return err; INIT_LIST_HEAD(&q->active); return 0; } static void drr_reset_qdisc(struct Qdisc *sch) { struct drr_sched *q = qdisc_priv(sch); struct drr_class *cl; |
13d2a1d2b pkt_sched: add DR... |
429 430 431 |
unsigned int i; for (i = 0; i < q->clhash.hashsize; i++) { |
b67bfe0d4 hlist: drop the n... |
432 |
hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { |
13d2a1d2b pkt_sched: add DR... |
433 434 435 436 437 |
if (cl->qdisc->q.qlen) list_del(&cl->alist); qdisc_reset(cl->qdisc); } } |
6a73b571b sch_drr: update b... |
438 |
sch->qstats.backlog = 0; |
13d2a1d2b pkt_sched: add DR... |
439 440 441 442 443 444 445 |
sch->q.qlen = 0; } static void drr_destroy_qdisc(struct Qdisc *sch) { struct drr_sched *q = qdisc_priv(sch); struct drr_class *cl; |
b67bfe0d4 hlist: drop the n... |
446 |
struct hlist_node *next; |
13d2a1d2b pkt_sched: add DR... |
447 448 449 450 451 |
unsigned int i; tcf_destroy_chain(&q->filter_list); for (i = 0; i < q->clhash.hashsize; i++) { |
b67bfe0d4 hlist: drop the n... |
452 |
hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i], |
13d2a1d2b pkt_sched: add DR... |
453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 |
common.hnode) drr_destroy_class(sch, cl); } qdisc_class_hash_destroy(&q->clhash); } static const struct Qdisc_class_ops drr_class_ops = { .change = drr_change_class, .delete = drr_delete_class, .get = drr_get_class, .put = drr_put_class, .tcf_chain = drr_tcf_chain, .bind_tcf = drr_bind_tcf, .unbind_tcf = drr_unbind_tcf, .graft = drr_graft_class, .leaf = drr_class_leaf, .qlen_notify = drr_qlen_notify, .dump = drr_dump_class, .dump_stats = drr_dump_class_stats, .walk = drr_walk, }; static struct Qdisc_ops drr_qdisc_ops __read_mostly = { .cl_ops = &drr_class_ops, .id = "drr", .priv_size = sizeof(struct drr_sched), .enqueue = drr_enqueue, .dequeue = drr_dequeue, .peek = qdisc_peek_dequeued, |
13d2a1d2b pkt_sched: add DR... |
482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 |
.init = drr_init_qdisc, .reset = drr_reset_qdisc, .destroy = drr_destroy_qdisc, .owner = THIS_MODULE, }; static int __init drr_init(void) { return register_qdisc(&drr_qdisc_ops); } static void __exit drr_exit(void) { unregister_qdisc(&drr_qdisc_ops); } module_init(drr_init); module_exit(drr_exit); MODULE_LICENSE("GPL"); |