1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * net/sched/sch_drr.c Deficit Round Robin scheduler 4 * 5 * Copyright (c) 2008 Patrick McHardy <kaber@trash.net> 6 */ 7 8 #include <linux/module.h> 9 #include <linux/slab.h> 10 #include <linux/init.h> 11 #include <linux/errno.h> 12 #include <linux/netdevice.h> 13 #include <linux/pkt_sched.h> 14 #include <net/sch_generic.h> 15 #include <net/pkt_sched.h> 16 #include <net/pkt_cls.h> 17 18 struct drr_class { 19 struct Qdisc_class_common common; 20 21 struct gnet_stats_basic_sync bstats; 22 struct gnet_stats_queue qstats; 23 struct net_rate_estimator __rcu *rate_est; 24 struct list_head alist; 25 struct Qdisc *qdisc; 26 27 u32 quantum; 28 u32 deficit; 29 }; 30 31 struct drr_sched { 32 struct list_head active; 33 struct tcf_proto __rcu *filter_list; 34 struct tcf_block *block; 35 struct Qdisc_class_hash clhash; 36 }; 37 38 static struct drr_class *drr_find_class(struct Qdisc *sch, u32 classid) 39 { 40 struct drr_sched *q = qdisc_priv(sch); 41 struct Qdisc_class_common *clc; 42 43 clc = qdisc_class_find(&q->clhash, classid); 44 if (clc == NULL) 45 return NULL; 46 return container_of(clc, struct drr_class, common); 47 } 48 49 static const struct nla_policy drr_policy[TCA_DRR_MAX + 1] = { 50 [TCA_DRR_QUANTUM] = { .type = NLA_U32 }, 51 }; 52 53 static int drr_change_class(struct Qdisc *sch, u32 classid, u32 parentid, 54 struct nlattr **tca, unsigned long *arg, 55 struct netlink_ext_ack *extack) 56 { 57 struct drr_sched *q = qdisc_priv(sch); 58 struct drr_class *cl = (struct drr_class *)*arg; 59 struct nlattr *opt = tca[TCA_OPTIONS]; 60 struct nlattr *tb[TCA_DRR_MAX + 1]; 61 u32 quantum; 62 int err; 63 64 if (!opt) { 65 NL_SET_ERR_MSG(extack, "DRR options are required for this operation"); 66 return -EINVAL; 67 } 68 69 err = nla_parse_nested_deprecated(tb, TCA_DRR_MAX, opt, drr_policy, 70 extack); 71 if (err < 0) 72 return err; 73 74 if (tb[TCA_DRR_QUANTUM]) { 75 quantum = nla_get_u32(tb[TCA_DRR_QUANTUM]); 76 if (quantum == 0) { 77 NL_SET_ERR_MSG(extack, "Specified DRR quantum cannot be zero"); 78 return -EINVAL; 79 } 80 } else 81 quantum = psched_mtu(qdisc_dev(sch)); 82 83 if (cl != NULL) { 84 if (tca[TCA_RATE]) { 85 err = gen_replace_estimator(&cl->bstats, NULL, 86 &cl->rate_est, 87 NULL, true, 88 tca[TCA_RATE]); 89 if (err) { 90 NL_SET_ERR_MSG(extack, "Failed to replace estimator"); 91 return err; 92 } 93 } 94 95 sch_tree_lock(sch); 96 if (tb[TCA_DRR_QUANTUM]) 97 cl->quantum = quantum; 98 sch_tree_unlock(sch); 99 100 return 0; 101 } 102 103 cl = kzalloc(sizeof(struct drr_class), GFP_KERNEL); 104 if (cl == NULL) 105 return -ENOBUFS; 106 107 gnet_stats_basic_sync_init(&cl->bstats); 108 INIT_LIST_HEAD(&cl->alist); 109 cl->common.classid = classid; 110 cl->quantum = quantum; 111 cl->qdisc = qdisc_create_dflt(sch->dev_queue, 112 &pfifo_qdisc_ops, classid, 113 NULL); 114 if (cl->qdisc == NULL) 115 cl->qdisc = &noop_qdisc; 116 else 117 qdisc_hash_add(cl->qdisc, true); 118 119 if (tca[TCA_RATE]) { 120 err = gen_replace_estimator(&cl->bstats, NULL, &cl->rate_est, 121 NULL, true, tca[TCA_RATE]); 122 if (err) { 123 NL_SET_ERR_MSG(extack, "Failed to replace estimator"); 124 qdisc_put(cl->qdisc); 125 kfree(cl); 126 return err; 127 } 128 } 129 130 sch_tree_lock(sch); 131 qdisc_class_hash_insert(&q->clhash, &cl->common); 132 sch_tree_unlock(sch); 133 134 qdisc_class_hash_grow(sch, &q->clhash); 135 136 *arg = (unsigned long)cl; 137 return 0; 138 } 139 140 static void drr_destroy_class(struct Qdisc *sch, struct drr_class *cl) 141 { 142 gen_kill_estimator(&cl->rate_est); 143 qdisc_put(cl->qdisc); 144 kfree(cl); 145 } 146 147 static int drr_delete_class(struct Qdisc *sch, unsigned long arg, 148 struct netlink_ext_ack *extack) 149 { 150 struct drr_sched *q = qdisc_priv(sch); 151 struct drr_class *cl = (struct drr_class *)arg; 152 153 if (qdisc_class_in_use(&cl->common)) { 154 NL_SET_ERR_MSG(extack, "DRR class is in use"); 155 return -EBUSY; 156 } 157 158 sch_tree_lock(sch); 159 160 qdisc_purge_queue(cl->qdisc); 161 qdisc_class_hash_remove(&q->clhash, &cl->common); 162 163 sch_tree_unlock(sch); 164 165 drr_destroy_class(sch, cl); 166 return 0; 167 } 168 169 static unsigned long drr_search_class(struct Qdisc *sch, u32 classid) 170 { 171 return (unsigned long)drr_find_class(sch, classid); 172 } 173 174 static struct tcf_block *drr_tcf_block(struct Qdisc *sch, unsigned long cl, 175 struct netlink_ext_ack *extack) 176 { 177 struct drr_sched *q = qdisc_priv(sch); 178 179 if (cl) { 180 NL_SET_ERR_MSG(extack, "DRR classid must be zero"); 181 return NULL; 182 } 183 184 return q->block; 185 } 186 187 static unsigned long drr_bind_tcf(struct Qdisc *sch, unsigned long parent, 188 u32 classid) 189 { 190 struct drr_class *cl = drr_find_class(sch, classid); 191 192 if (cl) 193 qdisc_class_get(&cl->common); 194 195 return (unsigned long)cl; 196 } 197 198 static void drr_unbind_tcf(struct Qdisc *sch, unsigned long arg) 199 { 200 struct drr_class *cl = (struct drr_class *)arg; 201 202 qdisc_class_put(&cl->common); 203 } 204 205 static int drr_graft_class(struct Qdisc *sch, unsigned long arg, 206 struct Qdisc *new, struct Qdisc **old, 207 struct netlink_ext_ack *extack) 208 { 209 struct drr_class *cl = (struct drr_class *)arg; 210 211 if (new == NULL) { 212 new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, 213 cl->common.classid, NULL); 214 if (new == NULL) 215 new = &noop_qdisc; 216 } 217 218 *old = qdisc_replace(sch, new, &cl->qdisc); 219 return 0; 220 } 221 222 static struct Qdisc *drr_class_leaf(struct Qdisc *sch, unsigned long arg) 223 { 224 struct drr_class *cl = (struct drr_class *)arg; 225 226 return cl->qdisc; 227 } 228 229 static void drr_qlen_notify(struct Qdisc *csh, unsigned long arg) 230 { 231 struct drr_class *cl = (struct drr_class *)arg; 232 233 list_del_init(&cl->alist); 234 } 235 236 static int drr_dump_class(struct Qdisc *sch, unsigned long arg, 237 struct sk_buff *skb, struct tcmsg *tcm) 238 { 239 struct drr_class *cl = (struct drr_class *)arg; 240 struct nlattr *nest; 241 242 tcm->tcm_parent = TC_H_ROOT; 243 tcm->tcm_handle = cl->common.classid; 244 tcm->tcm_info = cl->qdisc->handle; 245 246 nest = nla_nest_start_noflag(skb, TCA_OPTIONS); 247 if (nest == NULL) 248 goto nla_put_failure; 249 if (nla_put_u32(skb, TCA_DRR_QUANTUM, cl->quantum)) 250 goto nla_put_failure; 251 return nla_nest_end(skb, nest); 252 253 nla_put_failure: 254 nla_nest_cancel(skb, nest); 255 return -EMSGSIZE; 256 } 257 258 static int drr_dump_class_stats(struct Qdisc *sch, unsigned long arg, 259 struct gnet_dump *d) 260 { 261 struct drr_class *cl = (struct drr_class *)arg; 262 __u32 qlen = qdisc_qlen_sum(cl->qdisc); 263 struct Qdisc *cl_q = cl->qdisc; 264 struct tc_drr_stats xstats; 265 266 memset(&xstats, 0, sizeof(xstats)); 267 if (qlen) 268 xstats.deficit = cl->deficit; 269 270 if (gnet_stats_copy_basic(d, NULL, &cl->bstats, true) < 0 || 271 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 || 272 gnet_stats_copy_queue(d, cl_q->cpu_qstats, &cl_q->qstats, qlen) < 0) 273 return -1; 274 275 return gnet_stats_copy_app(d, &xstats, sizeof(xstats)); 276 } 277 278 static void drr_walk(struct Qdisc *sch, struct qdisc_walker *arg) 279 { 280 struct drr_sched *q = qdisc_priv(sch); 281 struct drr_class *cl; 282 unsigned int i; 283 284 if (arg->stop) 285 return; 286 287 for (i = 0; i < q->clhash.hashsize; i++) { 288 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { 289 if (!tc_qdisc_stats_dump(sch, (unsigned long)cl, arg)) 290 return; 291 } 292 } 293 } 294 295 static struct drr_class *drr_classify(struct sk_buff *skb, struct Qdisc *sch, 296 int *qerr) 297 { 298 struct drr_sched *q = qdisc_priv(sch); 299 struct drr_class *cl; 300 struct tcf_result res; 301 struct tcf_proto *fl; 302 int result; 303 304 if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) { 305 cl = drr_find_class(sch, skb->priority); 306 if (cl != NULL) 307 return cl; 308 } 309 310 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; 311 fl = rcu_dereference_bh(q->filter_list); 312 result = tcf_classify(skb, NULL, fl, &res, false); 313 if (result >= 0) { 314 #ifdef CONFIG_NET_CLS_ACT 315 switch (result) { 316 case TC_ACT_QUEUED: 317 case TC_ACT_STOLEN: 318 case TC_ACT_TRAP: 319 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN; 320 fallthrough; 321 case TC_ACT_SHOT: 322 return NULL; 323 } 324 #endif 325 cl = (struct drr_class *)res.class; 326 if (cl == NULL) 327 cl = drr_find_class(sch, res.classid); 328 return cl; 329 } 330 return NULL; 331 } 332 333 static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch, 334 struct sk_buff **to_free) 335 { 336 unsigned int len = qdisc_pkt_len(skb); 337 struct drr_sched *q = qdisc_priv(sch); 338 struct drr_class *cl; 339 int err = 0; 340 bool first; 341 342 cl = drr_classify(skb, sch, &err); 343 if (cl == NULL) { 344 if (err & __NET_XMIT_BYPASS) 345 qdisc_qstats_drop(sch); 346 __qdisc_drop(skb, to_free); 347 return err; 348 } 349 350 first = !cl->qdisc->q.qlen; 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 (first) { 361 list_add_tail(&cl->alist, &q->active); 362 cl->deficit = cl->quantum; 363 } 364 365 sch->qstats.backlog += len; 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_init(&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 struct netlink_ext_ack *extack) 412 { 413 struct drr_sched *q = qdisc_priv(sch); 414 int err; 415 416 err = tcf_block_get(&q->block, &q->filter_list, sch, extack); 417 if (err) 418 return err; 419 err = qdisc_class_hash_init(&q->clhash); 420 if (err < 0) 421 return err; 422 INIT_LIST_HEAD(&q->active); 423 return 0; 424 } 425 426 static void drr_reset_qdisc(struct Qdisc *sch) 427 { 428 struct drr_sched *q = qdisc_priv(sch); 429 struct drr_class *cl; 430 unsigned int i; 431 432 for (i = 0; i < q->clhash.hashsize; i++) { 433 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { 434 if (cl->qdisc->q.qlen) 435 list_del_init(&cl->alist); 436 qdisc_reset(cl->qdisc); 437 } 438 } 439 } 440 441 static void drr_destroy_qdisc(struct Qdisc *sch) 442 { 443 struct drr_sched *q = qdisc_priv(sch); 444 struct drr_class *cl; 445 struct hlist_node *next; 446 unsigned int i; 447 448 tcf_block_put(q->block); 449 450 for (i = 0; i < q->clhash.hashsize; i++) { 451 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i], 452 common.hnode) 453 drr_destroy_class(sch, cl); 454 } 455 qdisc_class_hash_destroy(&q->clhash); 456 } 457 458 static const struct Qdisc_class_ops drr_class_ops = { 459 .change = drr_change_class, 460 .delete = drr_delete_class, 461 .find = drr_search_class, 462 .tcf_block = drr_tcf_block, 463 .bind_tcf = drr_bind_tcf, 464 .unbind_tcf = drr_unbind_tcf, 465 .graft = drr_graft_class, 466 .leaf = drr_class_leaf, 467 .qlen_notify = drr_qlen_notify, 468 .dump = drr_dump_class, 469 .dump_stats = drr_dump_class_stats, 470 .walk = drr_walk, 471 }; 472 473 static struct Qdisc_ops drr_qdisc_ops __read_mostly = { 474 .cl_ops = &drr_class_ops, 475 .id = "drr", 476 .priv_size = sizeof(struct drr_sched), 477 .enqueue = drr_enqueue, 478 .dequeue = drr_dequeue, 479 .peek = qdisc_peek_dequeued, 480 .init = drr_init_qdisc, 481 .reset = drr_reset_qdisc, 482 .destroy = drr_destroy_qdisc, 483 .owner = THIS_MODULE, 484 }; 485 MODULE_ALIAS_NET_SCH("drr"); 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 MODULE_DESCRIPTION("Deficit Round Robin scheduler"); 501