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