net/sched/sch_drr.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * net/sched/sch_drr.c         Deficit Round Robin scheduler
0004  *
0005  * Copyright (c) 2008 Patrick McHardy <kaber@trash.net>
0006  */
0007
0008 #include <linux/module.h>
0009 #include <linux/slab.h>
0010 #include <linux/init.h>
0011 #include <linux/errno.h>
0012 #include <linux/netdevice.h>
0013 #include <linux/pkt_sched.h>
0014 #include <net/sch_generic.h>
0015 #include <net/pkt_sched.h>
0016 #include <net/pkt_cls.h>
0017
0018 struct drr_class {
0019     struct Qdisc_class_common   common;
0020     unsigned int            filter_cnt;
0021
0022     struct gnet_stats_basic_sync        bstats;
0023     struct gnet_stats_queue     qstats;
0024     struct net_rate_estimator __rcu *rate_est;
0025     struct list_head        alist;
0026     struct Qdisc            *qdisc;
0027
0028     u32             quantum;
0029     u32             deficit;
0030 };
0031
0032 struct drr_sched {
0033     struct list_head        active;
0034     struct tcf_proto __rcu      *filter_list;
0035     struct tcf_block        *block;
0036     struct Qdisc_class_hash     clhash;
0037 };
0038
0039 static struct drr_class *drr_find_class(struct Qdisc *sch, u32 classid)
0040 {
0041     struct drr_sched *q = qdisc_priv(sch);
0042     struct Qdisc_class_common *clc;
0043
0044     clc = qdisc_class_find(&q->clhash, classid);
0045     if (clc == NULL)
0046         return NULL;
0047     return container_of(clc, struct drr_class, common);
0048 }
0049
0050 static const struct nla_policy drr_policy[TCA_DRR_MAX + 1] = {
0051     [TCA_DRR_QUANTUM]   = { .type = NLA_U32 },
0052 };
0053
0054 static int drr_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
0055                 struct nlattr **tca, unsigned long *arg,
0056                 struct netlink_ext_ack *extack)
0057 {
0058     struct drr_sched *q = qdisc_priv(sch);
0059     struct drr_class *cl = (struct drr_class *)*arg;
0060     struct nlattr *opt = tca[TCA_OPTIONS];
0061     struct nlattr *tb[TCA_DRR_MAX + 1];
0062     u32 quantum;
0063     int err;
0064
0065     if (!opt) {
0066         NL_SET_ERR_MSG(extack, "DRR options are required for this operation");
0067         return -EINVAL;
0068     }
0069
0070     err = nla_parse_nested_deprecated(tb, TCA_DRR_MAX, opt, drr_policy,
0071                       extack);
0072     if (err < 0)
0073         return err;
0074
0075     if (tb[TCA_DRR_QUANTUM]) {
0076         quantum = nla_get_u32(tb[TCA_DRR_QUANTUM]);
0077         if (quantum == 0) {
0078             NL_SET_ERR_MSG(extack, "Specified DRR quantum cannot be zero");
0079             return -EINVAL;
0080         }
0081     } else
0082         quantum = psched_mtu(qdisc_dev(sch));
0083
0084     if (cl != NULL) {
0085         if (tca[TCA_RATE]) {
0086             err = gen_replace_estimator(&cl->bstats, NULL,
0087                             &cl->rate_est,
0088                             NULL, true,
0089                             tca[TCA_RATE]);
0090             if (err) {
0091                 NL_SET_ERR_MSG(extack, "Failed to replace estimator");
0092                 return err;
0093             }
0094         }
0095
0096         sch_tree_lock(sch);
0097         if (tb[TCA_DRR_QUANTUM])
0098             cl->quantum = quantum;
0099         sch_tree_unlock(sch);
0100
0101         return 0;
0102     }
0103
0104     cl = kzalloc(sizeof(struct drr_class), GFP_KERNEL);
0105     if (cl == NULL)
0106         return -ENOBUFS;
0107
0108     gnet_stats_basic_sync_init(&cl->bstats);
0109     cl->common.classid = classid;
0110     cl->quantum    = quantum;
0111     cl->qdisc      = qdisc_create_dflt(sch->dev_queue,
0112                            &pfifo_qdisc_ops, classid,
0113                            NULL);
0114     if (cl->qdisc == NULL)
0115         cl->qdisc = &noop_qdisc;
0116     else
0117         qdisc_hash_add(cl->qdisc, true);
0118
0119     if (tca[TCA_RATE]) {
0120         err = gen_replace_estimator(&cl->bstats, NULL, &cl->rate_est,
0121                         NULL, true, tca[TCA_RATE]);
0122         if (err) {
0123             NL_SET_ERR_MSG(extack, "Failed to replace estimator");
0124             qdisc_put(cl->qdisc);
0125             kfree(cl);
0126             return err;
0127         }
0128     }
0129
0130     sch_tree_lock(sch);
0131     qdisc_class_hash_insert(&q->clhash, &cl->common);
0132     sch_tree_unlock(sch);
0133
0134     qdisc_class_hash_grow(sch, &q->clhash);
0135
0136     *arg = (unsigned long)cl;
0137     return 0;
0138 }
0139
0140 static void drr_destroy_class(struct Qdisc *sch, struct drr_class *cl)
0141 {
0142     gen_kill_estimator(&cl->rate_est);
0143     qdisc_put(cl->qdisc);
0144     kfree(cl);
0145 }
0146
0147 static int drr_delete_class(struct Qdisc *sch, unsigned long arg,
0148                 struct netlink_ext_ack *extack)
0149 {
0150     struct drr_sched *q = qdisc_priv(sch);
0151     struct drr_class *cl = (struct drr_class *)arg;
0152
0153     if (cl->filter_cnt > 0)
0154         return -EBUSY;
0155
0156     sch_tree_lock(sch);
0157
0158     qdisc_purge_queue(cl->qdisc);
0159     qdisc_class_hash_remove(&q->clhash, &cl->common);
0160
0161     sch_tree_unlock(sch);
0162
0163     drr_destroy_class(sch, cl);
0164     return 0;
0165 }
0166
0167 static unsigned long drr_search_class(struct Qdisc *sch, u32 classid)
0168 {
0169     return (unsigned long)drr_find_class(sch, classid);
0170 }
0171
0172 static struct tcf_block *drr_tcf_block(struct Qdisc *sch, unsigned long cl,
0173                        struct netlink_ext_ack *extack)
0174 {
0175     struct drr_sched *q = qdisc_priv(sch);
0176
0177     if (cl) {
0178         NL_SET_ERR_MSG(extack, "DRR classid must be zero");
0179         return NULL;
0180     }
0181
0182     return q->block;
0183 }
0184
0185 static unsigned long drr_bind_tcf(struct Qdisc *sch, unsigned long parent,
0186                   u32 classid)
0187 {
0188     struct drr_class *cl = drr_find_class(sch, classid);
0189
0190     if (cl != NULL)
0191         cl->filter_cnt++;
0192
0193     return (unsigned long)cl;
0194 }
0195
0196 static void drr_unbind_tcf(struct Qdisc *sch, unsigned long arg)
0197 {
0198     struct drr_class *cl = (struct drr_class *)arg;
0199
0200     cl->filter_cnt--;
0201 }
0202
0203 static int drr_graft_class(struct Qdisc *sch, unsigned long arg,
0204                struct Qdisc *new, struct Qdisc **old,
0205                struct netlink_ext_ack *extack)
0206 {
0207     struct drr_class *cl = (struct drr_class *)arg;
0208
0209     if (new == NULL) {
0210         new = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops,
0211                     cl->common.classid, NULL);
0212         if (new == NULL)
0213             new = &noop_qdisc;
0214     }
0215
0216     *old = qdisc_replace(sch, new, &cl->qdisc);
0217     return 0;
0218 }
0219
0220 static struct Qdisc *drr_class_leaf(struct Qdisc *sch, unsigned long arg)
0221 {
0222     struct drr_class *cl = (struct drr_class *)arg;
0223
0224     return cl->qdisc;
0225 }
0226
0227 static void drr_qlen_notify(struct Qdisc *csh, unsigned long arg)
0228 {
0229     struct drr_class *cl = (struct drr_class *)arg;
0230
0231     list_del(&cl->alist);
0232 }
0233
0234 static int drr_dump_class(struct Qdisc *sch, unsigned long arg,
0235               struct sk_buff *skb, struct tcmsg *tcm)
0236 {
0237     struct drr_class *cl = (struct drr_class *)arg;
0238     struct nlattr *nest;
0239
0240     tcm->tcm_parent = TC_H_ROOT;
0241     tcm->tcm_handle = cl->common.classid;
0242     tcm->tcm_info   = cl->qdisc->handle;
0243
0244     nest = nla_nest_start_noflag(skb, TCA_OPTIONS);
0245     if (nest == NULL)
0246         goto nla_put_failure;
0247     if (nla_put_u32(skb, TCA_DRR_QUANTUM, cl->quantum))
0248         goto nla_put_failure;
0249     return nla_nest_end(skb, nest);
0250
0251 nla_put_failure:
0252     nla_nest_cancel(skb, nest);
0253     return -EMSGSIZE;
0254 }
0255
0256 static int drr_dump_class_stats(struct Qdisc *sch, unsigned long arg,
0257                 struct gnet_dump *d)
0258 {
0259     struct drr_class *cl = (struct drr_class *)arg;
0260     __u32 qlen = qdisc_qlen_sum(cl->qdisc);
0261     struct Qdisc *cl_q = cl->qdisc;
0262     struct tc_drr_stats xstats;
0263
0264     memset(&xstats, 0, sizeof(xstats));
0265     if (qlen)
0266         xstats.deficit = cl->deficit;
0267
0268     if (gnet_stats_copy_basic(d, NULL, &cl->bstats, true) < 0 ||
0269         gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 ||
0270         gnet_stats_copy_queue(d, cl_q->cpu_qstats, &cl_q->qstats, qlen) < 0)
0271         return -1;
0272
0273     return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
0274 }
0275
0276 static void drr_walk(struct Qdisc *sch, struct qdisc_walker *arg)
0277 {
0278     struct drr_sched *q = qdisc_priv(sch);
0279     struct drr_class *cl;
0280     unsigned int i;
0281
0282     if (arg->stop)
0283         return;
0284
0285     for (i = 0; i < q->clhash.hashsize; i++) {
0286         hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
0287             if (arg->count < arg->skip) {
0288                 arg->count++;
0289                 continue;
0290             }
0291             if (arg->fn(sch, (unsigned long)cl, arg) < 0) {
0292                 arg->stop = 1;
0293                 return;
0294             }
0295             arg->count++;
0296         }
0297     }
0298 }
0299
0300 static struct drr_class *drr_classify(struct sk_buff *skb, struct Qdisc *sch,
0301                       int *qerr)
0302 {
0303     struct drr_sched *q = qdisc_priv(sch);
0304     struct drr_class *cl;
0305     struct tcf_result res;
0306     struct tcf_proto *fl;
0307     int result;
0308
0309     if (TC_H_MAJ(skb->priority ^ sch->handle) == 0) {
0310         cl = drr_find_class(sch, skb->priority);
0311         if (cl != NULL)
0312             return cl;
0313     }
0314
0315     *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
0316     fl = rcu_dereference_bh(q->filter_list);
0317     result = tcf_classify(skb, NULL, fl, &res, false);
0318     if (result >= 0) {
0319 #ifdef CONFIG_NET_CLS_ACT
0320         switch (result) {
0321         case TC_ACT_QUEUED:
0322         case TC_ACT_STOLEN:
0323         case TC_ACT_TRAP:
0324             *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
0325             fallthrough;
0326         case TC_ACT_SHOT:
0327             return NULL;
0328         }
0329 #endif
0330         cl = (struct drr_class *)res.class;
0331         if (cl == NULL)
0332             cl = drr_find_class(sch, res.classid);
0333         return cl;
0334     }
0335     return NULL;
0336 }
0337
0338 static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch,
0339                struct sk_buff **to_free)
0340 {
0341     unsigned int len = qdisc_pkt_len(skb);
0342     struct drr_sched *q = qdisc_priv(sch);
0343     struct drr_class *cl;
0344     int err = 0;
0345     bool first;
0346
0347     cl = drr_classify(skb, sch, &err);
0348     if (cl == NULL) {
0349         if (err & __NET_XMIT_BYPASS)
0350             qdisc_qstats_drop(sch);
0351         __qdisc_drop(skb, to_free);
0352         return err;
0353     }
0354
0355     first = !cl->qdisc->q.qlen;
0356     err = qdisc_enqueue(skb, cl->qdisc, to_free);
0357     if (unlikely(err != NET_XMIT_SUCCESS)) {
0358         if (net_xmit_drop_count(err)) {
0359             cl->qstats.drops++;
0360             qdisc_qstats_drop(sch);
0361         }
0362         return err;
0363     }
0364
0365     if (first) {
0366         list_add_tail(&cl->alist, &q->active);
0367         cl->deficit = cl->quantum;
0368     }
0369
0370     sch->qstats.backlog += len;
0371     sch->q.qlen++;
0372     return err;
0373 }
0374
0375 static struct sk_buff *drr_dequeue(struct Qdisc *sch)
0376 {
0377     struct drr_sched *q = qdisc_priv(sch);
0378     struct drr_class *cl;
0379     struct sk_buff *skb;
0380     unsigned int len;
0381
0382     if (list_empty(&q->active))
0383         goto out;
0384     while (1) {
0385         cl = list_first_entry(&q->active, struct drr_class, alist);
0386         skb = cl->qdisc->ops->peek(cl->qdisc);
0387         if (skb == NULL) {
0388             qdisc_warn_nonwc(__func__, cl->qdisc);
0389             goto out;
0390         }
0391
0392         len = qdisc_pkt_len(skb);
0393         if (len <= cl->deficit) {
0394             cl->deficit -= len;
0395             skb = qdisc_dequeue_peeked(cl->qdisc);
0396             if (unlikely(skb == NULL))
0397                 goto out;
0398             if (cl->qdisc->q.qlen == 0)
0399                 list_del(&cl->alist);
0400
0401             bstats_update(&cl->bstats, skb);
0402             qdisc_bstats_update(sch, skb);
0403             qdisc_qstats_backlog_dec(sch, skb);
0404             sch->q.qlen--;
0405             return skb;
0406         }
0407
0408         cl->deficit += cl->quantum;
0409         list_move_tail(&cl->alist, &q->active);
0410     }
0411 out:
0412     return NULL;
0413 }
0414
0415 static int drr_init_qdisc(struct Qdisc *sch, struct nlattr *opt,
0416               struct netlink_ext_ack *extack)
0417 {
0418     struct drr_sched *q = qdisc_priv(sch);
0419     int err;
0420
0421     err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
0422     if (err)
0423         return err;
0424     err = qdisc_class_hash_init(&q->clhash);
0425     if (err < 0)
0426         return err;
0427     INIT_LIST_HEAD(&q->active);
0428     return 0;
0429 }
0430
0431 static void drr_reset_qdisc(struct Qdisc *sch)
0432 {
0433     struct drr_sched *q = qdisc_priv(sch);
0434     struct drr_class *cl;
0435     unsigned int i;
0436
0437     for (i = 0; i < q->clhash.hashsize; i++) {
0438         hlist_for_each_entry(cl, &q->clhash.hash[i], common.hnode) {
0439             if (cl->qdisc->q.qlen)
0440                 list_del(&cl->alist);
0441             qdisc_reset(cl->qdisc);
0442         }
0443     }
0444     sch->qstats.backlog = 0;
0445     sch->q.qlen = 0;
0446 }
0447
0448 static void drr_destroy_qdisc(struct Qdisc *sch)
0449 {
0450     struct drr_sched *q = qdisc_priv(sch);
0451     struct drr_class *cl;
0452     struct hlist_node *next;
0453     unsigned int i;
0454
0455     tcf_block_put(q->block);
0456
0457     for (i = 0; i < q->clhash.hashsize; i++) {
0458         hlist_for_each_entry_safe(cl, next, &q->clhash.hash[i],
0459                       common.hnode)
0460             drr_destroy_class(sch, cl);
0461     }
0462     qdisc_class_hash_destroy(&q->clhash);
0463 }
0464
0465 static const struct Qdisc_class_ops drr_class_ops = {
0466     .change     = drr_change_class,
0467     .delete     = drr_delete_class,
0468     .find       = drr_search_class,
0469     .tcf_block  = drr_tcf_block,
0470     .bind_tcf   = drr_bind_tcf,
0471     .unbind_tcf = drr_unbind_tcf,
0472     .graft      = drr_graft_class,
0473     .leaf       = drr_class_leaf,
0474     .qlen_notify    = drr_qlen_notify,
0475     .dump       = drr_dump_class,
0476     .dump_stats = drr_dump_class_stats,
0477     .walk       = drr_walk,
0478 };
0479
0480 static struct Qdisc_ops drr_qdisc_ops __read_mostly = {
0481     .cl_ops     = &drr_class_ops,
0482     .id     = "drr",
0483     .priv_size  = sizeof(struct drr_sched),
0484     .enqueue    = drr_enqueue,
0485     .dequeue    = drr_dequeue,
0486     .peek       = qdisc_peek_dequeued,
0487     .init       = drr_init_qdisc,
0488     .reset      = drr_reset_qdisc,
0489     .destroy    = drr_destroy_qdisc,
0490     .owner      = THIS_MODULE,
0491 };
0492
0493 static int __init drr_init(void)
0494 {
0495     return register_qdisc(&drr_qdisc_ops);
0496 }
0497
0498 static void __exit drr_exit(void)
0499 {
0500     unregister_qdisc(&drr_qdisc_ops);
0501 }
0502
0503 module_init(drr_init);
0504 module_exit(drr_exit);
0505 MODULE_LICENSE("GPL");