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 quantum = clamp_t(u32, quantum, 256, 1 << 20); 86 } else 87 quantum = clamp_t(u32, (u32)psched_mtu(qdisc_dev(sch)), 256, 1 << 20); 88 89 if (cl != NULL) { 90 if (tca[TCA_RATE]) { 91 err = gen_replace_estimator(&cl->bstats, NULL, 92 &cl->rate_est, 93 NULL, true, 94 tca[TCA_RATE]); 95 if (err) { 96 NL_SET_ERR_MSG(extack, "Failed to replace estimator"); 97 return err; 98 } 99 } 100 101 if (tb[TCA_DRR_QUANTUM]) 102 WRITE_ONCE(cl->quantum, quantum); 103 104 return 0; 105 } 106 107 cl = kzalloc_obj(struct drr_class); 108 if (cl == NULL) 109 return -ENOBUFS; 110 111 gnet_stats_basic_sync_init(&cl->bstats); 112 INIT_LIST_HEAD(&cl->alist); 113 cl->common.classid = classid; 114 cl->quantum = quantum; 115 cl->qdisc = qdisc_create_dflt(sch->dev_queue, 116 &pfifo_qdisc_ops, classid, 117 NULL); 118 if (cl->qdisc == NULL) 119 cl->qdisc = &noop_qdisc; 120 else 121 qdisc_hash_add(cl->qdisc, true); 122 123 if (tca[TCA_RATE]) { 124 err = gen_replace_estimator(&cl->bstats, NULL, &cl->rate_est, 125 NULL, true, tca[TCA_RATE]); 126 if (err) { 127 NL_SET_ERR_MSG(extack, "Failed to replace estimator"); 128 qdisc_put(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_put(cl->qdisc); 148 kfree(cl); 149 } 150 151 static int drr_delete_class(struct Qdisc *sch, unsigned long arg, 152 struct netlink_ext_ack *extack) 153 { 154 struct drr_sched *q = qdisc_priv(sch); 155 struct drr_class *cl = (struct drr_class *)arg; 156 157 if (qdisc_class_in_use(&cl->common)) { 158 NL_SET_ERR_MSG(extack, "DRR class is in use"); 159 return -EBUSY; 160 } 161 162 sch_tree_lock(sch); 163 164 qdisc_purge_queue(cl->qdisc); 165 qdisc_class_hash_remove(&q->clhash, &cl->common); 166 167 sch_tree_unlock(sch); 168 169 drr_destroy_class(sch, cl); 170 return 0; 171 } 172 173 static unsigned long drr_search_class(struct Qdisc *sch, u32 classid) 174 { 175 return (unsigned long)drr_find_class(sch, classid); 176 } 177 178 static struct tcf_block *drr_tcf_block(struct Qdisc *sch, unsigned long cl, 179 struct netlink_ext_ack *extack) 180 { 181 struct drr_sched *q = qdisc_priv(sch); 182 183 if (cl) { 184 NL_SET_ERR_MSG(extack, "DRR classid must be zero"); 185 return NULL; 186 } 187 188 return q->block; 189 } 190 191 static unsigned long drr_bind_tcf(struct Qdisc *sch, unsigned long parent, 192 u32 classid) 193 { 194 struct drr_class *cl = drr_find_class(sch, classid); 195 196 if (cl) 197 qdisc_class_get(&cl->common); 198 199 return (unsigned long)cl; 200 } 201 202 static void drr_unbind_tcf(struct Qdisc *sch, unsigned long arg) 203 { 204 struct drr_class *cl = (struct drr_class *)arg; 205 206 qdisc_class_put(&cl->common); 207 } 208 209 static int drr_graft_class(struct Qdisc *sch, unsigned long arg, 210 struct Qdisc *new, struct Qdisc **old, 211 struct netlink_ext_ack *extack) 212 { 213 struct drr_class *cl = (struct drr_class *)arg; 214 215 if (new == NULL) { 216 new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, 217 cl->common.classid, NULL); 218 if (new == NULL) 219 new = &noop_qdisc; 220 } 221 222 *old = qdisc_replace(sch, new, &cl->qdisc); 223 return 0; 224 } 225 226 static struct Qdisc *drr_class_leaf(struct Qdisc *sch, unsigned long arg) 227 { 228 struct drr_class *cl = (struct drr_class *)arg; 229 230 return cl->qdisc; 231 } 232 233 static void drr_qlen_notify(struct Qdisc *csh, unsigned long arg) 234 { 235 struct drr_class *cl = (struct drr_class *)arg; 236 237 list_del_init(&cl->alist); 238 } 239 240 static int drr_dump_class(struct Qdisc *sch, unsigned long arg, 241 struct sk_buff *skb, struct tcmsg *tcm) 242 { 243 struct drr_class *cl = (struct drr_class *)arg; 244 struct nlattr *nest; 245 246 tcm->tcm_parent = TC_H_ROOT; 247 tcm->tcm_handle = cl->common.classid; 248 tcm->tcm_info = cl->qdisc->handle; 249 250 nest = nla_nest_start_noflag(skb, TCA_OPTIONS); 251 if (nest == NULL) 252 goto nla_put_failure; 253 if (nla_put_u32(skb, TCA_DRR_QUANTUM, READ_ONCE(cl->quantum))) 254 goto nla_put_failure; 255 return nla_nest_end(skb, nest); 256 257 nla_put_failure: 258 nla_nest_cancel(skb, nest); 259 return -EMSGSIZE; 260 } 261 262 static int drr_dump_class_stats(struct Qdisc *sch, unsigned long arg, 263 struct gnet_dump *d) 264 { 265 struct drr_class *cl = (struct drr_class *)arg; 266 __u32 qlen = qdisc_qlen_sum(cl->qdisc); 267 struct Qdisc *cl_q = cl->qdisc; 268 struct tc_drr_stats xstats; 269 270 memset(&xstats, 0, sizeof(xstats)); 271 if (qlen) 272 xstats.deficit = READ_ONCE(cl->deficit); 273 274 if (gnet_stats_copy_basic(d, NULL, &cl->bstats, true) < 0 || 275 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 || 276 gnet_stats_copy_queue(d, cl_q->cpu_qstats, &cl_q->qstats, qlen) < 0) 277 return -1; 278 279 return gnet_stats_copy_app(d, &xstats, sizeof(xstats)); 280 } 281 282 static void drr_walk(struct Qdisc *sch, struct qdisc_walker *arg) 283 { 284 struct drr_sched *q = qdisc_priv(sch); 285 struct drr_class *cl; 286 unsigned int i; 287 288 if (arg->stop) 289 return; 290 291 for (i = 0; i < q->clhash.hashsize; i++) { 292 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { 293 if (!tc_qdisc_stats_dump(sch, (unsigned long)cl, arg)) 294 return; 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_qdisc(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 fallthrough; 325 case TC_ACT_SHOT: 326 return NULL; 327 } 328 #endif 329 cl = (struct drr_class *)res.class; 330 if (cl == NULL) 331 cl = drr_find_class(sch, res.classid); 332 return cl; 333 } 334 return NULL; 335 } 336 337 static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch, 338 struct sk_buff **to_free) 339 { 340 unsigned int len = qdisc_pkt_len(skb); 341 struct drr_sched *q = qdisc_priv(sch); 342 struct drr_class *cl; 343 int err = 0; 344 345 cl = drr_classify(skb, sch, &err); 346 if (cl == NULL) { 347 if (err & __NET_XMIT_BYPASS) 348 qdisc_qstats_drop(sch); 349 __qdisc_drop(skb, to_free); 350 return err; 351 } 352 353 err = qdisc_enqueue(skb, cl->qdisc, to_free); 354 if (unlikely(err != NET_XMIT_SUCCESS)) { 355 if (net_xmit_drop_count(err)) { 356 cl->qstats.drops++; 357 qdisc_qstats_drop(sch); 358 } 359 return err; 360 } 361 362 if (!cl_is_active(cl)) { 363 list_add_tail(&cl->alist, &q->active); 364 WRITE_ONCE(cl->deficit, READ_ONCE(cl->quantum)); 365 } 366 367 qstats_backlog_add(sch, len); 368 qdisc_qlen_inc(sch); 369 return err; 370 } 371 372 static struct sk_buff *drr_dequeue(struct Qdisc *sch) 373 { 374 struct drr_sched *q = qdisc_priv(sch); 375 struct drr_class *cl; 376 struct sk_buff *skb; 377 unsigned int len; 378 379 if (list_empty(&q->active)) 380 goto out; 381 while (1) { 382 cl = list_first_entry(&q->active, struct drr_class, alist); 383 skb = cl->qdisc->ops->peek(cl->qdisc); 384 if (skb == NULL) { 385 qdisc_warn_nonwc(__func__, cl->qdisc); 386 goto out; 387 } 388 389 len = qdisc_pkt_len(skb); 390 if (len <= cl->deficit) { 391 WRITE_ONCE(cl->deficit, cl->deficit - len); 392 skb = qdisc_dequeue_peeked(cl->qdisc); 393 if (unlikely(skb == NULL)) 394 goto out; 395 if (cl->qdisc->q.qlen == 0) 396 list_del_init(&cl->alist); 397 398 bstats_update(&cl->bstats, skb); 399 qdisc_bstats_update(sch, skb); 400 qdisc_qstats_backlog_dec(sch, skb); 401 qdisc_qlen_dec(sch); 402 return skb; 403 } 404 405 WRITE_ONCE(cl->deficit, cl->deficit + READ_ONCE(cl->quantum)); 406 list_move_tail(&cl->alist, &q->active); 407 } 408 out: 409 return NULL; 410 } 411 412 static int drr_init_qdisc(struct Qdisc *sch, struct nlattr *opt, 413 struct netlink_ext_ack *extack) 414 { 415 struct drr_sched *q = qdisc_priv(sch); 416 int err; 417 418 err = tcf_block_get(&q->block, &q->filter_list, sch, extack); 419 if (err) 420 return err; 421 err = qdisc_class_hash_init(&q->clhash); 422 if (err < 0) 423 return err; 424 INIT_LIST_HEAD(&q->active); 425 return 0; 426 } 427 428 static void drr_reset_qdisc(struct Qdisc *sch) 429 { 430 struct drr_sched *q = qdisc_priv(sch); 431 struct drr_class *cl; 432 unsigned int i; 433 434 for (i = 0; i < q->clhash.hashsize; i++) { 435 hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) { 436 if (cl->qdisc->q.qlen) 437 list_del_init(&cl->alist); 438 qdisc_reset(cl->qdisc); 439 } 440 } 441 } 442 443 static void drr_destroy_qdisc(struct Qdisc *sch) 444 { 445 struct drr_sched *q = qdisc_priv(sch); 446 struct drr_class *cl; 447 struct hlist_node *next; 448 unsigned int i; 449 450 tcf_block_put(q->block); 451 452 for (i = 0; i < q->clhash.hashsize; i++) { 453 hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i], 454 common.hnode) 455 drr_destroy_class(sch, cl); 456 } 457 qdisc_class_hash_destroy(&q->clhash); 458 } 459 460 static const struct Qdisc_class_ops drr_class_ops = { 461 .change = drr_change_class, 462 .delete = drr_delete_class, 463 .find = drr_search_class, 464 .tcf_block = drr_tcf_block, 465 .bind_tcf = drr_bind_tcf, 466 .unbind_tcf = drr_unbind_tcf, 467 .graft = drr_graft_class, 468 .leaf = drr_class_leaf, 469 .qlen_notify = drr_qlen_notify, 470 .dump = drr_dump_class, 471 .dump_stats = drr_dump_class_stats, 472 .walk = drr_walk, 473 }; 474 475 static struct Qdisc_ops drr_qdisc_ops __read_mostly = { 476 .cl_ops = &drr_class_ops, 477 .id = "drr", 478 .priv_size = sizeof(struct drr_sched), 479 .enqueue = drr_enqueue, 480 .dequeue = drr_dequeue, 481 .peek = qdisc_peek_dequeued, 482 .init = drr_init_qdisc, 483 .reset = drr_reset_qdisc, 484 .destroy = drr_destroy_qdisc, 485 .owner = THIS_MODULE, 486 }; 487 MODULE_ALIAS_NET_SCH("drr"); 488 489 static int __init drr_init(void) 490 { 491 return register_qdisc(&drr_qdisc_ops); 492 } 493 494 static void __exit drr_exit(void) 495 { 496 unregister_qdisc(&drr_qdisc_ops); 497 } 498 499 module_init(drr_init); 500 module_exit(drr_exit); 501 MODULE_LICENSE("GPL"); 502 MODULE_DESCRIPTION("Deficit Round Robin scheduler"); 503