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 bool cl_is_active(struct drr_class *cl) 39 { 40 return !list_empty(&cl->alist); 41 } 42 43 static struct drr_class *drr_find_class(struct Qdisc *sch, u32 classid) 44 { 45 struct drr_sched *q = qdisc_priv(sch); 46 struct Qdisc_class_common *clc; 47 48 clc = qdisc_class_find(&q->clhash, classid); 49 if (clc == NULL) 50 return NULL; 51 return container_of(clc, struct drr_class, common); 52 } 53 54 static const struct nla_policy drr_policy[TCA_DRR_MAX + 1] = { 55 [TCA_DRR_QUANTUM] = { .type = NLA_U32 }, 56 }; 57 58 static int drr_change_class(struct Qdisc *sch, u32 classid, u32 parentid, 59 struct nlattr **tca, unsigned long *arg, 60 struct netlink_ext_ack *extack) 61 { 62 struct drr_sched *q = qdisc_priv(sch); 63 struct drr_class *cl = (struct drr_class *)*arg; 64 struct nlattr *opt = tca[TCA_OPTIONS]; 65 struct nlattr *tb[TCA_DRR_MAX + 1]; 66 u32 quantum; 67 int err; 68 69 if (!opt) { 70 NL_SET_ERR_MSG(extack, "DRR options are required for this operation"); 71 return -EINVAL; 72 } 73 74 err = nla_parse_nested_deprecated(tb, TCA_DRR_MAX, opt, drr_policy, 75 extack); 76 if (err < 0) 77 return err; 78 79 if (tb[TCA_DRR_QUANTUM]) { 80 quantum = nla_get_u32(tb[TCA_DRR_QUANTUM]); 81 if (quantum == 0) { 82 NL_SET_ERR_MSG(extack, "Specified DRR quantum cannot be zero"); 83 return -EINVAL; 84 } 85 } else 86 quantum = psched_mtu(qdisc_dev(sch)); 87 88 if (cl != NULL) { 89 if (tca[TCA_RATE]) { 90 err = gen_replace_estimator(&cl->bstats, NULL, 91 &cl->rate_est, 92 NULL, true, 93 tca[TCA_RATE]); 94 if (err) { 95 NL_SET_ERR_MSG(extack, "Failed to replace estimator"); 96 return err; 97 } 98 } 99 100 if (tb[TCA_DRR_QUANTUM]) 101 WRITE_ONCE(cl->quantum, quantum); 102 103 return 0; 104 } 105 106 cl = kzalloc_obj(struct drr_class); 107 if (cl == NULL) 108 return -ENOBUFS; 109 110 gnet_stats_basic_sync_init(&cl->bstats); 111 INIT_LIST_HEAD(&cl->alist); 112 cl->common.classid = classid; 113 cl->quantum = quantum; 114 cl->qdisc = qdisc_create_dflt(sch->dev_queue, 115 &pfifo_qdisc_ops, classid, 116 NULL); 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, true, tca[TCA_RATE]); 125 if (err) { 126 NL_SET_ERR_MSG(extack, "Failed to replace estimator"); 127 qdisc_put(cl->qdisc); 128 kfree(cl); 129 return err; 130 } 131 } 132 133 sch_tree_lock(sch); 134 qdisc_class_hash_insert(&q->clhash, &cl->common); 135 sch_tree_unlock(sch); 136 137 qdisc_class_hash_grow(sch, &q->clhash); 138 139 *arg = (unsigned long)cl; 140 return 0; 141 } 142 143 static void drr_destroy_class(struct Qdisc *sch, struct drr_class *cl) 144 { 145 gen_kill_estimator(&cl->rate_est); 146 qdisc_put(cl->qdisc); 147 kfree(cl); 148 } 149 150 static int drr_delete_class(struct Qdisc *sch, unsigned long arg, 151 struct netlink_ext_ack *extack) 152 { 153 struct drr_sched *q = qdisc_priv(sch); 154 struct drr_class *cl = (struct drr_class *)arg; 155 156 if (qdisc_class_in_use(&cl->common)) { 157 NL_SET_ERR_MSG(extack, "DRR class is in use"); 158 return -EBUSY; 159 } 160 161 sch_tree_lock(sch); 162 163 qdisc_purge_queue(cl->qdisc); 164 qdisc_class_hash_remove(&q->clhash, &cl->common); 165 166 sch_tree_unlock(sch); 167 168 drr_destroy_class(sch, cl); 169 return 0; 170 } 171 172 static unsigned long drr_search_class(struct Qdisc *sch, u32 classid) 173 { 174 return (unsigned long)drr_find_class(sch, classid); 175 } 176 177 static struct tcf_block *drr_tcf_block(struct Qdisc *sch, unsigned long cl, 178 struct netlink_ext_ack *extack) 179 { 180 struct drr_sched *q = qdisc_priv(sch); 181 182 if (cl) { 183 NL_SET_ERR_MSG(extack, "DRR classid must be zero"); 184 return NULL; 185 } 186 187 return q->block; 188 } 189 190 static unsigned long drr_bind_tcf(struct Qdisc *sch, unsigned long parent, 191 u32 classid) 192 { 193 struct drr_class *cl = drr_find_class(sch, classid); 194 195 if (cl) 196 qdisc_class_get(&cl->common); 197 198 return (unsigned long)cl; 199 } 200 201 static void drr_unbind_tcf(struct Qdisc *sch, unsigned long arg) 202 { 203 struct drr_class *cl = (struct drr_class *)arg; 204 205 qdisc_class_put(&cl->common); 206 } 207 208 static int drr_graft_class(struct Qdisc *sch, unsigned long arg, 209 struct Qdisc *new, struct Qdisc **old, 210 struct netlink_ext_ack *extack) 211 { 212 struct drr_class *cl = (struct drr_class *)arg; 213 214 if (new == NULL) { 215 new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, 216 cl->common.classid, NULL); 217 if (new == NULL) 218 new = &noop_qdisc; 219 } 220 221 *old = qdisc_replace(sch, new, &cl->qdisc); 222 return 0; 223 } 224 225 static struct Qdisc *drr_class_leaf(struct Qdisc *sch, unsigned long arg) 226 { 227 struct drr_class *cl = (struct drr_class *)arg; 228 229 return cl->qdisc; 230 } 231 232 static void drr_qlen_notify(struct Qdisc *csh, unsigned long arg) 233 { 234 struct drr_class *cl = (struct drr_class *)arg; 235 236 list_del_init(&cl->alist); 237 } 238 239 static int drr_dump_class(struct Qdisc *sch, unsigned long arg, 240 struct sk_buff *skb, struct tcmsg *tcm) 241 { 242 struct drr_class *cl = (struct drr_class *)arg; 243 struct nlattr *nest; 244 245 tcm->tcm_parent = TC_H_ROOT; 246 tcm->tcm_handle = cl->common.classid; 247 tcm->tcm_info = cl->qdisc->handle; 248 249 nest = nla_nest_start_noflag(skb, TCA_OPTIONS); 250 if (nest == NULL) 251 goto nla_put_failure; 252 if (nla_put_u32(skb, TCA_DRR_QUANTUM, READ_ONCE(cl->quantum))) 253 goto nla_put_failure; 254 return nla_nest_end(skb, nest); 255 256 nla_put_failure: 257 nla_nest_cancel(skb, nest); 258 return -EMSGSIZE; 259 } 260 261 static int drr_dump_class_stats(struct Qdisc *sch, unsigned long arg, 262 struct gnet_dump *d) 263 { 264 struct drr_class *cl = (struct drr_class *)arg; 265 __u32 qlen = qdisc_qlen_sum(cl->qdisc); 266 struct Qdisc *cl_q = cl->qdisc; 267 struct tc_drr_stats xstats; 268 269 memset(&xstats, 0, sizeof(xstats)); 270 if (qlen) 271 xstats.deficit = READ_ONCE(cl->deficit); 272 273 if (gnet_stats_copy_basic(d, NULL, &cl->bstats, true) < 0 || 274 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 || 275 gnet_stats_copy_queue(d, cl_q->cpu_qstats, &cl_q->qstats, qlen) < 0) 276 return -1; 277 278 return gnet_stats_copy_app(d, &xstats, sizeof(xstats)); 279 } 280 281 static void drr_walk(struct Qdisc *sch, struct qdisc_walker *arg) 282 { 283 struct drr_sched *q = qdisc_priv(sch); 284 struct drr_class *cl; 285 unsigned int i; 286 287 if (arg->stop) 288 return; 289 290 for (i = 0; i < q->clhash.hashsize; i++) { 291 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { 292 if (!tc_qdisc_stats_dump(sch, (unsigned long)cl, arg)) 293 return; 294 } 295 } 296 } 297 298 static struct drr_class *drr_classify(struct sk_buff *skb, struct Qdisc *sch, 299 int *qerr) 300 { 301 struct drr_sched *q = qdisc_priv(sch); 302 struct drr_class *cl; 303 struct tcf_result res; 304 struct tcf_proto *fl; 305 int result; 306 307 if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) { 308 cl = drr_find_class(sch, skb->priority); 309 if (cl != NULL) 310 return cl; 311 } 312 313 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; 314 fl = rcu_dereference_bh(q->filter_list); 315 result = tcf_classify(skb, NULL, fl, &res, false); 316 if (result >= 0) { 317 #ifdef CONFIG_NET_CLS_ACT 318 switch (result) { 319 case TC_ACT_QUEUED: 320 case TC_ACT_STOLEN: 321 case TC_ACT_TRAP: 322 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN; 323 fallthrough; 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 unsigned int len = qdisc_pkt_len(skb); 340 struct drr_sched *q = qdisc_priv(sch); 341 struct drr_class *cl; 342 int err = 0; 343 344 cl = drr_classify(skb, sch, &err); 345 if (cl == NULL) { 346 if (err & __NET_XMIT_BYPASS) 347 qdisc_qstats_drop(sch); 348 __qdisc_drop(skb, to_free); 349 return err; 350 } 351 352 err = qdisc_enqueue(skb, cl->qdisc, to_free); 353 if (unlikely(err != NET_XMIT_SUCCESS)) { 354 if (net_xmit_drop_count(err)) { 355 cl->qstats.drops++; 356 qdisc_qstats_drop(sch); 357 } 358 return err; 359 } 360 361 if (!cl_is_active(cl)) { 362 list_add_tail(&cl->alist, &q->active); 363 WRITE_ONCE(cl->deficit, READ_ONCE(cl->quantum)); 364 } 365 366 qstats_backlog_add(sch, len); 367 qdisc_qlen_inc(sch); 368 return err; 369 } 370 371 static struct sk_buff *drr_dequeue(struct Qdisc *sch) 372 { 373 struct drr_sched *q = qdisc_priv(sch); 374 struct drr_class *cl; 375 struct sk_buff *skb; 376 unsigned int len; 377 378 if (list_empty(&q->active)) 379 goto out; 380 while (1) { 381 cl = list_first_entry(&q->active, struct drr_class, alist); 382 skb = cl->qdisc->ops->peek(cl->qdisc); 383 if (skb == NULL) { 384 qdisc_warn_nonwc(__func__, cl->qdisc); 385 goto out; 386 } 387 388 len = qdisc_pkt_len(skb); 389 if (len <= cl->deficit) { 390 WRITE_ONCE(cl->deficit, cl->deficit - len); 391 skb = qdisc_dequeue_peeked(cl->qdisc); 392 if (unlikely(skb == NULL)) 393 goto out; 394 if (cl->qdisc->q.qlen == 0) 395 list_del_init(&cl->alist); 396 397 bstats_update(&cl->bstats, skb); 398 qdisc_bstats_update(sch, skb); 399 qdisc_qstats_backlog_dec(sch, skb); 400 qdisc_qlen_dec(sch); 401 return skb; 402 } 403 404 WRITE_ONCE(cl->deficit, cl->deficit + READ_ONCE(cl->quantum)); 405 list_move_tail(&cl->alist, &q->active); 406 } 407 out: 408 return NULL; 409 } 410 411 static int drr_init_qdisc(struct Qdisc *sch, struct nlattr *opt, 412 struct netlink_ext_ack *extack) 413 { 414 struct drr_sched *q = qdisc_priv(sch); 415 int err; 416 417 err = tcf_block_get(&q->block, &q->filter_list, sch, extack); 418 if (err) 419 return err; 420 err = qdisc_class_hash_init(&q->clhash); 421 if (err < 0) 422 return err; 423 INIT_LIST_HEAD(&q->active); 424 return 0; 425 } 426 427 static void drr_reset_qdisc(struct Qdisc *sch) 428 { 429 struct drr_sched *q = qdisc_priv(sch); 430 struct drr_class *cl; 431 unsigned int i; 432 433 for (i = 0; i < q->clhash.hashsize; i++) { 434 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { 435 if (cl->qdisc->q.qlen) 436 list_del_init(&cl->alist); 437 qdisc_reset(cl->qdisc); 438 } 439 } 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 MODULE_ALIAS_NET_SCH("drr"); 487 488 static int __init drr_init(void) 489 { 490 return register_qdisc(&drr_qdisc_ops); 491 } 492 493 static void __exit drr_exit(void) 494 { 495 unregister_qdisc(&drr_qdisc_ops); 496 } 497 498 module_init(drr_init); 499 module_exit(drr_exit); 500 MODULE_LICENSE("GPL"); 501 MODULE_DESCRIPTION("Deficit Round Robin scheduler"); 502