11da177e4SLinus Torvalds /* 21da177e4SLinus Torvalds * net/sched/sch_prio.c Simple 3-band priority "scheduler". 31da177e4SLinus Torvalds * 41da177e4SLinus Torvalds * This program is free software; you can redistribute it and/or 51da177e4SLinus Torvalds * modify it under the terms of the GNU General Public License 61da177e4SLinus Torvalds * as published by the Free Software Foundation; either version 71da177e4SLinus Torvalds * 2 of the License, or (at your option) any later version. 81da177e4SLinus Torvalds * 91da177e4SLinus Torvalds * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru> 101da177e4SLinus Torvalds * Fixes: 19990609: J Hadi Salim <hadi@nortelnetworks.com>: 111da177e4SLinus Torvalds * Init -- EINVAL when opt undefined 121da177e4SLinus Torvalds */ 131da177e4SLinus Torvalds 141da177e4SLinus Torvalds #include <linux/module.h> 155a0e3ad6STejun Heo #include <linux/slab.h> 161da177e4SLinus Torvalds #include <linux/types.h> 171da177e4SLinus Torvalds #include <linux/kernel.h> 181da177e4SLinus Torvalds #include <linux/string.h> 191da177e4SLinus Torvalds #include <linux/errno.h> 201da177e4SLinus Torvalds #include <linux/skbuff.h> 21dc5fc579SArnaldo Carvalho de Melo #include <net/netlink.h> 221da177e4SLinus Torvalds #include <net/pkt_sched.h> 23cf1facdaSJiri Pirko #include <net/pkt_cls.h> 241da177e4SLinus Torvalds 25cc7ec456SEric Dumazet struct prio_sched_data { 261da177e4SLinus Torvalds int bands; 2725d8c0d5SJohn Fastabend struct tcf_proto __rcu *filter_list; 286529eabaSJiri Pirko struct tcf_block *block; 291da177e4SLinus Torvalds u8 prio2band[TC_PRIO_MAX+1]; 301da177e4SLinus Torvalds struct Qdisc *queues[TCQ_PRIO_BANDS]; 311da177e4SLinus Torvalds }; 321da177e4SLinus Torvalds 331da177e4SLinus Torvalds 341da177e4SLinus Torvalds static struct Qdisc * 351da177e4SLinus Torvalds prio_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr) 361da177e4SLinus Torvalds { 371da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 381da177e4SLinus Torvalds u32 band = skb->priority; 391da177e4SLinus Torvalds struct tcf_result res; 4025d8c0d5SJohn Fastabend struct tcf_proto *fl; 41bdba91ecSPatrick McHardy int err; 421da177e4SLinus Torvalds 43c27f339aSJarek Poplawski *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; 441da177e4SLinus Torvalds if (TC_H_MAJ(skb->priority) != sch->handle) { 4525d8c0d5SJohn Fastabend fl = rcu_dereference_bh(q->filter_list); 4687d83093SJiri Pirko err = tcf_classify(skb, fl, &res, false); 471da177e4SLinus Torvalds #ifdef CONFIG_NET_CLS_ACT 48dbaaa07aSLucas Nussbaum switch (err) { 491da177e4SLinus Torvalds case TC_ACT_STOLEN: 501da177e4SLinus Torvalds case TC_ACT_QUEUED: 51*e25ea21fSJiri Pirko case TC_ACT_TRAP: 52378a2f09SJarek Poplawski *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN; 531da177e4SLinus Torvalds case TC_ACT_SHOT: 541da177e4SLinus Torvalds return NULL; 553ff50b79SStephen Hemminger } 561da177e4SLinus Torvalds #endif 5725d8c0d5SJohn Fastabend if (!fl || err < 0) { 581da177e4SLinus Torvalds if (TC_H_MAJ(band)) 591da177e4SLinus Torvalds band = 0; 601d8ae3fdSDavid S. Miller return q->queues[q->prio2band[band & TC_PRIO_MAX]]; 611da177e4SLinus Torvalds } 621da177e4SLinus Torvalds band = res.classid; 631da177e4SLinus Torvalds } 641da177e4SLinus Torvalds band = TC_H_MIN(band) - 1; 653e5c2d3bSJamal Hadi Salim if (band >= q->bands) 661d8ae3fdSDavid S. Miller return q->queues[q->prio2band[0]]; 671d8ae3fdSDavid S. Miller 681da177e4SLinus Torvalds return q->queues[band]; 691da177e4SLinus Torvalds } 701da177e4SLinus Torvalds 711da177e4SLinus Torvalds static int 72520ac30fSEric Dumazet prio_enqueue(struct sk_buff *skb, struct Qdisc *sch, struct sk_buff **to_free) 731da177e4SLinus Torvalds { 741da177e4SLinus Torvalds struct Qdisc *qdisc; 751da177e4SLinus Torvalds int ret; 761da177e4SLinus Torvalds 771da177e4SLinus Torvalds qdisc = prio_classify(skb, sch, &ret); 781da177e4SLinus Torvalds #ifdef CONFIG_NET_CLS_ACT 791da177e4SLinus Torvalds if (qdisc == NULL) { 8029f1df6cSJamal Hadi Salim 81c27f339aSJarek Poplawski if (ret & __NET_XMIT_BYPASS) 8225331d6cSJohn Fastabend qdisc_qstats_drop(sch); 831da177e4SLinus Torvalds kfree_skb(skb); 841da177e4SLinus Torvalds return ret; 851da177e4SLinus Torvalds } 861da177e4SLinus Torvalds #endif 871da177e4SLinus Torvalds 88520ac30fSEric Dumazet ret = qdisc_enqueue(skb, qdisc, to_free); 895f86173bSJussi Kivilinna if (ret == NET_XMIT_SUCCESS) { 906529d75aSWANG Cong qdisc_qstats_backlog_inc(sch, skb); 911da177e4SLinus Torvalds sch->q.qlen++; 921da177e4SLinus Torvalds return NET_XMIT_SUCCESS; 931da177e4SLinus Torvalds } 94378a2f09SJarek Poplawski if (net_xmit_drop_count(ret)) 9525331d6cSJohn Fastabend qdisc_qstats_drop(sch); 961da177e4SLinus Torvalds return ret; 971da177e4SLinus Torvalds } 981da177e4SLinus Torvalds 9948a8f519SPatrick McHardy static struct sk_buff *prio_peek(struct Qdisc *sch) 10048a8f519SPatrick McHardy { 10148a8f519SPatrick McHardy struct prio_sched_data *q = qdisc_priv(sch); 10248a8f519SPatrick McHardy int prio; 10348a8f519SPatrick McHardy 10448a8f519SPatrick McHardy for (prio = 0; prio < q->bands; prio++) { 10548a8f519SPatrick McHardy struct Qdisc *qdisc = q->queues[prio]; 10648a8f519SPatrick McHardy struct sk_buff *skb = qdisc->ops->peek(qdisc); 10748a8f519SPatrick McHardy if (skb) 10848a8f519SPatrick McHardy return skb; 10948a8f519SPatrick McHardy } 11048a8f519SPatrick McHardy return NULL; 11148a8f519SPatrick McHardy } 1121da177e4SLinus Torvalds 1131d8ae3fdSDavid S. Miller static struct sk_buff *prio_dequeue(struct Qdisc *sch) 1141da177e4SLinus Torvalds { 1151da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 1161da177e4SLinus Torvalds int prio; 1171da177e4SLinus Torvalds 1181da177e4SLinus Torvalds for (prio = 0; prio < q->bands; prio++) { 1191d8ae3fdSDavid S. Miller struct Qdisc *qdisc = q->queues[prio]; 1203557619fSFlorian Westphal struct sk_buff *skb = qdisc_dequeue_peeked(qdisc); 1211da177e4SLinus Torvalds if (skb) { 1229190b3b3SEric Dumazet qdisc_bstats_update(sch, skb); 1236529d75aSWANG Cong qdisc_qstats_backlog_dec(sch, skb); 1241da177e4SLinus Torvalds sch->q.qlen--; 1251da177e4SLinus Torvalds return skb; 1261da177e4SLinus Torvalds } 1271da177e4SLinus Torvalds } 1281da177e4SLinus Torvalds return NULL; 1291da177e4SLinus Torvalds 1301da177e4SLinus Torvalds } 1311da177e4SLinus Torvalds 1321da177e4SLinus Torvalds static void 1331da177e4SLinus Torvalds prio_reset(struct Qdisc *sch) 1341da177e4SLinus Torvalds { 1351da177e4SLinus Torvalds int prio; 1361da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 1371da177e4SLinus Torvalds 1381da177e4SLinus Torvalds for (prio = 0; prio < q->bands; prio++) 1391da177e4SLinus Torvalds qdisc_reset(q->queues[prio]); 1406529d75aSWANG Cong sch->qstats.backlog = 0; 1411da177e4SLinus Torvalds sch->q.qlen = 0; 1421da177e4SLinus Torvalds } 1431da177e4SLinus Torvalds 1441da177e4SLinus Torvalds static void 1451da177e4SLinus Torvalds prio_destroy(struct Qdisc *sch) 1461da177e4SLinus Torvalds { 1471da177e4SLinus Torvalds int prio; 1481da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 1491da177e4SLinus Torvalds 1506529eabaSJiri Pirko tcf_block_put(q->block); 1511da177e4SLinus Torvalds for (prio = 0; prio < q->bands; prio++) 1521da177e4SLinus Torvalds qdisc_destroy(q->queues[prio]); 1531da177e4SLinus Torvalds } 1541da177e4SLinus Torvalds 1551e90474cSPatrick McHardy static int prio_tune(struct Qdisc *sch, struct nlattr *opt) 1561da177e4SLinus Torvalds { 1571da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 1583d7c8257SEric Dumazet struct Qdisc *queues[TCQ_PRIO_BANDS]; 1593d7c8257SEric Dumazet int oldbands = q->bands, i; 160d62733c8SPeter P Waskiewicz Jr struct tc_prio_qopt *qopt; 1611da177e4SLinus Torvalds 1621d8ae3fdSDavid S. Miller if (nla_len(opt) < sizeof(*qopt)) 163d62733c8SPeter P Waskiewicz Jr return -EINVAL; 1641d8ae3fdSDavid S. Miller qopt = nla_data(opt); 165d62733c8SPeter P Waskiewicz Jr 1661d8ae3fdSDavid S. Miller if (qopt->bands > TCQ_PRIO_BANDS || qopt->bands < 2) 1671da177e4SLinus Torvalds return -EINVAL; 1681da177e4SLinus Torvalds 1691da177e4SLinus Torvalds for (i = 0; i <= TC_PRIO_MAX; i++) { 1701d8ae3fdSDavid S. Miller if (qopt->priomap[i] >= qopt->bands) 1711da177e4SLinus Torvalds return -EINVAL; 1721da177e4SLinus Torvalds } 1731da177e4SLinus Torvalds 1743d7c8257SEric Dumazet /* Before commit, make sure we can allocate all new qdiscs */ 1753d7c8257SEric Dumazet for (i = oldbands; i < qopt->bands; i++) { 1763d7c8257SEric Dumazet queues[i] = qdisc_create_dflt(sch->dev_queue, &pfifo_qdisc_ops, 1773d7c8257SEric Dumazet TC_H_MAKE(sch->handle, i + 1)); 1783d7c8257SEric Dumazet if (!queues[i]) { 1793d7c8257SEric Dumazet while (i > oldbands) 1803d7c8257SEric Dumazet qdisc_destroy(queues[--i]); 1813d7c8257SEric Dumazet return -ENOMEM; 1823d7c8257SEric Dumazet } 1833d7c8257SEric Dumazet } 1843d7c8257SEric Dumazet 1851da177e4SLinus Torvalds sch_tree_lock(sch); 1861d8ae3fdSDavid S. Miller q->bands = qopt->bands; 1871da177e4SLinus Torvalds memcpy(q->prio2band, qopt->priomap, TC_PRIO_MAX+1); 1881da177e4SLinus Torvalds 1893d7c8257SEric Dumazet for (i = q->bands; i < oldbands; i++) { 190b94c8afcSPatrick McHardy struct Qdisc *child = q->queues[i]; 1913d7c8257SEric Dumazet 1923d7c8257SEric Dumazet qdisc_tree_reduce_backlog(child, child->q.qlen, 1933d7c8257SEric Dumazet child->qstats.backlog); 1941da177e4SLinus Torvalds qdisc_destroy(child); 1951da177e4SLinus Torvalds } 1963d7c8257SEric Dumazet 19749b49971SJiri Kosina for (i = oldbands; i < q->bands; i++) { 1983d7c8257SEric Dumazet q->queues[i] = queues[i]; 19949b49971SJiri Kosina if (q->queues[i] != &noop_qdisc) 20049b49971SJiri Kosina qdisc_hash_add(q->queues[i], true); 20149b49971SJiri Kosina } 2023d7c8257SEric Dumazet 2031da177e4SLinus Torvalds sch_tree_unlock(sch); 2041da177e4SLinus Torvalds return 0; 2051da177e4SLinus Torvalds } 2061da177e4SLinus Torvalds 2071e90474cSPatrick McHardy static int prio_init(struct Qdisc *sch, struct nlattr *opt) 2081da177e4SLinus Torvalds { 2096529eabaSJiri Pirko struct prio_sched_data *q = qdisc_priv(sch); 2106529eabaSJiri Pirko int err; 2116529eabaSJiri Pirko 2123d7c8257SEric Dumazet if (!opt) 2131da177e4SLinus Torvalds return -EINVAL; 2141da177e4SLinus Torvalds 2156529eabaSJiri Pirko err = tcf_block_get(&q->block, &q->filter_list); 2166529eabaSJiri Pirko if (err) 2176529eabaSJiri Pirko return err; 2186529eabaSJiri Pirko 2193d7c8257SEric Dumazet return prio_tune(sch, opt); 2201da177e4SLinus Torvalds } 2211da177e4SLinus Torvalds 2221da177e4SLinus Torvalds static int prio_dump(struct Qdisc *sch, struct sk_buff *skb) 2231da177e4SLinus Torvalds { 2241da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 22527a884dcSArnaldo Carvalho de Melo unsigned char *b = skb_tail_pointer(skb); 2261da177e4SLinus Torvalds struct tc_prio_qopt opt; 2271da177e4SLinus Torvalds 2281da177e4SLinus Torvalds opt.bands = q->bands; 2291da177e4SLinus Torvalds memcpy(&opt.priomap, q->prio2band, TC_PRIO_MAX + 1); 230d62733c8SPeter P Waskiewicz Jr 2311b34ec43SDavid S. Miller if (nla_put(skb, TCA_OPTIONS, sizeof(opt), &opt)) 2321b34ec43SDavid S. Miller goto nla_put_failure; 233d62733c8SPeter P Waskiewicz Jr 2341da177e4SLinus Torvalds return skb->len; 2351da177e4SLinus Torvalds 2361e90474cSPatrick McHardy nla_put_failure: 237dc5fc579SArnaldo Carvalho de Melo nlmsg_trim(skb, b); 2381da177e4SLinus Torvalds return -1; 2391da177e4SLinus Torvalds } 2401da177e4SLinus Torvalds 2411da177e4SLinus Torvalds static int prio_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, 2421da177e4SLinus Torvalds struct Qdisc **old) 2431da177e4SLinus Torvalds { 2441da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 2451da177e4SLinus Torvalds unsigned long band = arg - 1; 2461da177e4SLinus Torvalds 2471da177e4SLinus Torvalds if (new == NULL) 2481da177e4SLinus Torvalds new = &noop_qdisc; 2491da177e4SLinus Torvalds 25086a7996cSWANG Cong *old = qdisc_replace(sch, new, &q->queues[band]); 2511da177e4SLinus Torvalds return 0; 2521da177e4SLinus Torvalds } 2531da177e4SLinus Torvalds 2541da177e4SLinus Torvalds static struct Qdisc * 2551da177e4SLinus Torvalds prio_leaf(struct Qdisc *sch, unsigned long arg) 2561da177e4SLinus Torvalds { 2571da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 2581da177e4SLinus Torvalds unsigned long band = arg - 1; 2591da177e4SLinus Torvalds 2601da177e4SLinus Torvalds return q->queues[band]; 2611da177e4SLinus Torvalds } 2621da177e4SLinus Torvalds 2631da177e4SLinus Torvalds static unsigned long prio_get(struct Qdisc *sch, u32 classid) 2641da177e4SLinus Torvalds { 2651da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 2661da177e4SLinus Torvalds unsigned long band = TC_H_MIN(classid); 2671da177e4SLinus Torvalds 2681da177e4SLinus Torvalds if (band - 1 >= q->bands) 2691da177e4SLinus Torvalds return 0; 2701da177e4SLinus Torvalds return band; 2711da177e4SLinus Torvalds } 2721da177e4SLinus Torvalds 2731da177e4SLinus Torvalds static unsigned long prio_bind(struct Qdisc *sch, unsigned long parent, u32 classid) 2741da177e4SLinus Torvalds { 2751da177e4SLinus Torvalds return prio_get(sch, classid); 2761da177e4SLinus Torvalds } 2771da177e4SLinus Torvalds 2781da177e4SLinus Torvalds 2791da177e4SLinus Torvalds static void prio_put(struct Qdisc *q, unsigned long cl) 2801da177e4SLinus Torvalds { 2811da177e4SLinus Torvalds } 2821da177e4SLinus Torvalds 2831da177e4SLinus Torvalds static int prio_dump_class(struct Qdisc *sch, unsigned long cl, struct sk_buff *skb, 2841da177e4SLinus Torvalds struct tcmsg *tcm) 2851da177e4SLinus Torvalds { 2861da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 2871da177e4SLinus Torvalds 2881da177e4SLinus Torvalds tcm->tcm_handle |= TC_H_MIN(cl); 2891da177e4SLinus Torvalds tcm->tcm_info = q->queues[cl-1]->handle; 2901da177e4SLinus Torvalds return 0; 2911da177e4SLinus Torvalds } 2921da177e4SLinus Torvalds 2932cf6c36cSJarek Poplawski static int prio_dump_class_stats(struct Qdisc *sch, unsigned long cl, 2942cf6c36cSJarek Poplawski struct gnet_dump *d) 2952cf6c36cSJarek Poplawski { 2962cf6c36cSJarek Poplawski struct prio_sched_data *q = qdisc_priv(sch); 2972cf6c36cSJarek Poplawski struct Qdisc *cl_q; 2982cf6c36cSJarek Poplawski 2992cf6c36cSJarek Poplawski cl_q = q->queues[cl - 1]; 300edb09eb1SEric Dumazet if (gnet_stats_copy_basic(qdisc_root_sleeping_running(sch), 301edb09eb1SEric Dumazet d, NULL, &cl_q->bstats) < 0 || 302b0ab6f92SJohn Fastabend gnet_stats_copy_queue(d, NULL, &cl_q->qstats, cl_q->q.qlen) < 0) 3032cf6c36cSJarek Poplawski return -1; 3042cf6c36cSJarek Poplawski 3052cf6c36cSJarek Poplawski return 0; 3062cf6c36cSJarek Poplawski } 3072cf6c36cSJarek Poplawski 3081da177e4SLinus Torvalds static void prio_walk(struct Qdisc *sch, struct qdisc_walker *arg) 3091da177e4SLinus Torvalds { 3101da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 3111da177e4SLinus Torvalds int prio; 3121da177e4SLinus Torvalds 3131da177e4SLinus Torvalds if (arg->stop) 3141da177e4SLinus Torvalds return; 3151da177e4SLinus Torvalds 3161da177e4SLinus Torvalds for (prio = 0; prio < q->bands; prio++) { 3171da177e4SLinus Torvalds if (arg->count < arg->skip) { 3181da177e4SLinus Torvalds arg->count++; 3191da177e4SLinus Torvalds continue; 3201da177e4SLinus Torvalds } 3211da177e4SLinus Torvalds if (arg->fn(sch, prio + 1, arg) < 0) { 3221da177e4SLinus Torvalds arg->stop = 1; 3231da177e4SLinus Torvalds break; 3241da177e4SLinus Torvalds } 3251da177e4SLinus Torvalds arg->count++; 3261da177e4SLinus Torvalds } 3271da177e4SLinus Torvalds } 3281da177e4SLinus Torvalds 3296529eabaSJiri Pirko static struct tcf_block *prio_tcf_block(struct Qdisc *sch, unsigned long cl) 3301da177e4SLinus Torvalds { 3311da177e4SLinus Torvalds struct prio_sched_data *q = qdisc_priv(sch); 3321da177e4SLinus Torvalds 3331da177e4SLinus Torvalds if (cl) 3341da177e4SLinus Torvalds return NULL; 3356529eabaSJiri Pirko return q->block; 3361da177e4SLinus Torvalds } 3371da177e4SLinus Torvalds 33820fea08bSEric Dumazet static const struct Qdisc_class_ops prio_class_ops = { 3391da177e4SLinus Torvalds .graft = prio_graft, 3401da177e4SLinus Torvalds .leaf = prio_leaf, 3411da177e4SLinus Torvalds .get = prio_get, 3421da177e4SLinus Torvalds .put = prio_put, 3431da177e4SLinus Torvalds .walk = prio_walk, 3446529eabaSJiri Pirko .tcf_block = prio_tcf_block, 3451da177e4SLinus Torvalds .bind_tcf = prio_bind, 3461da177e4SLinus Torvalds .unbind_tcf = prio_put, 3471da177e4SLinus Torvalds .dump = prio_dump_class, 3482cf6c36cSJarek Poplawski .dump_stats = prio_dump_class_stats, 3491da177e4SLinus Torvalds }; 3501da177e4SLinus Torvalds 35120fea08bSEric Dumazet static struct Qdisc_ops prio_qdisc_ops __read_mostly = { 3521da177e4SLinus Torvalds .next = NULL, 3531da177e4SLinus Torvalds .cl_ops = &prio_class_ops, 3541da177e4SLinus Torvalds .id = "prio", 3551da177e4SLinus Torvalds .priv_size = sizeof(struct prio_sched_data), 3561da177e4SLinus Torvalds .enqueue = prio_enqueue, 3571da177e4SLinus Torvalds .dequeue = prio_dequeue, 35848a8f519SPatrick McHardy .peek = prio_peek, 3591da177e4SLinus Torvalds .init = prio_init, 3601da177e4SLinus Torvalds .reset = prio_reset, 3611da177e4SLinus Torvalds .destroy = prio_destroy, 3621da177e4SLinus Torvalds .change = prio_tune, 3631da177e4SLinus Torvalds .dump = prio_dump, 3641da177e4SLinus Torvalds .owner = THIS_MODULE, 3651da177e4SLinus Torvalds }; 3661da177e4SLinus Torvalds 3671da177e4SLinus Torvalds static int __init prio_module_init(void) 3681da177e4SLinus Torvalds { 3691d8ae3fdSDavid S. Miller return register_qdisc(&prio_qdisc_ops); 3701da177e4SLinus Torvalds } 3711da177e4SLinus Torvalds 3721da177e4SLinus Torvalds static void __exit prio_module_exit(void) 3731da177e4SLinus Torvalds { 3741da177e4SLinus Torvalds unregister_qdisc(&prio_qdisc_ops); 3751da177e4SLinus Torvalds } 3761da177e4SLinus Torvalds 3771da177e4SLinus Torvalds module_init(prio_module_init) 3781da177e4SLinus Torvalds module_exit(prio_module_exit) 3791da177e4SLinus Torvalds 3801da177e4SLinus Torvalds MODULE_LICENSE("GPL"); 381