linux/net/sched/sch_fq_pie.c
<<
>>
Prefs
   1// SPDX-License-Identifier: GPL-2.0-only
   2/* Flow Queue PIE discipline
   3 *
   4 * Copyright (C) 2019 Mohit P. Tahiliani <tahiliani@nitk.edu.in>
   5 * Copyright (C) 2019 Sachin D. Patil <sdp.sachin@gmail.com>
   6 * Copyright (C) 2019 V. Saicharan <vsaicharan1998@gmail.com>
   7 * Copyright (C) 2019 Mohit Bhasi <mohitbhasi1998@gmail.com>
   8 * Copyright (C) 2019 Leslie Monis <lesliemonis@gmail.com>
   9 * Copyright (C) 2019 Gautam Ramakrishnan <gautamramk@gmail.com>
  10 */
  11
  12#include <linux/jhash.h>
  13#include <linux/sizes.h>
  14#include <linux/vmalloc.h>
  15#include <net/pkt_cls.h>
  16#include <net/pie.h>
  17
  18/* Flow Queue PIE
  19 *
  20 * Principles:
  21 *   - Packets are classified on flows.
  22 *   - This is a Stochastic model (as we use a hash, several flows might
  23 *                                 be hashed to the same slot)
  24 *   - Each flow has a PIE managed queue.
  25 *   - Flows are linked onto two (Round Robin) lists,
  26 *     so that new flows have priority on old ones.
  27 *   - For a given flow, packets are not reordered.
  28 *   - Drops during enqueue only.
  29 *   - ECN capability is off by default.
  30 *   - ECN threshold (if ECN is enabled) is at 10% by default.
  31 *   - Uses timestamps to calculate queue delay by default.
  32 */
  33
  34/**
  35 * struct fq_pie_flow - contains data for each flow
  36 * @vars:       pie vars associated with the flow
  37 * @deficit:    number of remaining byte credits
  38 * @backlog:    size of data in the flow
  39 * @qlen:       number of packets in the flow
  40 * @flowchain:  flowchain for the flow
  41 * @head:       first packet in the flow
  42 * @tail:       last packet in the flow
  43 */
  44struct fq_pie_flow {
  45        struct pie_vars vars;
  46        s32 deficit;
  47        u32 backlog;
  48        u32 qlen;
  49        struct list_head flowchain;
  50        struct sk_buff *head;
  51        struct sk_buff *tail;
  52};
  53
  54struct fq_pie_sched_data {
  55        struct tcf_proto __rcu *filter_list; /* optional external classifier */
  56        struct tcf_block *block;
  57        struct fq_pie_flow *flows;
  58        struct Qdisc *sch;
  59        struct list_head old_flows;
  60        struct list_head new_flows;
  61        struct pie_params p_params;
  62        u32 ecn_prob;
  63        u32 flows_cnt;
  64        u32 quantum;
  65        u32 memory_limit;
  66        u32 new_flow_count;
  67        u32 memory_usage;
  68        u32 overmemory;
  69        struct pie_stats stats;
  70        struct timer_list adapt_timer;
  71};
  72
  73static unsigned int fq_pie_hash(const struct fq_pie_sched_data *q,
  74                                struct sk_buff *skb)
  75{
  76        return reciprocal_scale(skb_get_hash(skb), q->flows_cnt);
  77}
  78
  79static unsigned int fq_pie_classify(struct sk_buff *skb, struct Qdisc *sch,
  80                                    int *qerr)
  81{
  82        struct fq_pie_sched_data *q = qdisc_priv(sch);
  83        struct tcf_proto *filter;
  84        struct tcf_result res;
  85        int result;
  86
  87        if (TC_H_MAJ(skb->priority) == sch->handle &&
  88            TC_H_MIN(skb->priority) > 0 &&
  89            TC_H_MIN(skb->priority) <= q->flows_cnt)
  90                return TC_H_MIN(skb->priority);
  91
  92        filter = rcu_dereference_bh(q->filter_list);
  93        if (!filter)
  94                return fq_pie_hash(q, skb) + 1;
  95
  96        *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
  97        result = tcf_classify(skb, filter, &res, false);
  98        if (result >= 0) {
  99#ifdef CONFIG_NET_CLS_ACT
 100                switch (result) {
 101                case TC_ACT_STOLEN:
 102                case TC_ACT_QUEUED:
 103                case TC_ACT_TRAP:
 104                        *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
 105                        fallthrough;
 106                case TC_ACT_SHOT:
 107                        return 0;
 108                }
 109#endif
 110                if (TC_H_MIN(res.classid) <= q->flows_cnt)
 111                        return TC_H_MIN(res.classid);
 112        }
 113        return 0;
 114}
 115
 116/* add skb to flow queue (tail add) */
 117static inline void flow_queue_add(struct fq_pie_flow *flow,
 118                                  struct sk_buff *skb)
 119{
 120        if (!flow->head)
 121                flow->head = skb;
 122        else
 123                flow->tail->next = skb;
 124        flow->tail = skb;
 125        skb->next = NULL;
 126}
 127
 128static int fq_pie_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 129                                struct sk_buff **to_free)
 130{
 131        struct fq_pie_sched_data *q = qdisc_priv(sch);
 132        struct fq_pie_flow *sel_flow;
 133        int ret;
 134        u8 memory_limited = false;
 135        u8 enqueue = false;
 136        u32 pkt_len;
 137        u32 idx;
 138
 139        /* Classifies packet into corresponding flow */
 140        idx = fq_pie_classify(skb, sch, &ret);
 141        if (idx == 0) {
 142                if (ret & __NET_XMIT_BYPASS)
 143                        qdisc_qstats_drop(sch);
 144                __qdisc_drop(skb, to_free);
 145                return ret;
 146        }
 147        idx--;
 148
 149        sel_flow = &q->flows[idx];
 150        /* Checks whether adding a new packet would exceed memory limit */
 151        get_pie_cb(skb)->mem_usage = skb->truesize;
 152        memory_limited = q->memory_usage > q->memory_limit + skb->truesize;
 153
 154        /* Checks if the qdisc is full */
 155        if (unlikely(qdisc_qlen(sch) >= sch->limit)) {
 156                q->stats.overlimit++;
 157                goto out;
 158        } else if (unlikely(memory_limited)) {
 159                q->overmemory++;
 160        }
 161
 162        if (!pie_drop_early(sch, &q->p_params, &sel_flow->vars,
 163                            sel_flow->backlog, skb->len)) {
 164                enqueue = true;
 165        } else if (q->p_params.ecn &&
 166                   sel_flow->vars.prob <= (MAX_PROB / 100) * q->ecn_prob &&
 167                   INET_ECN_set_ce(skb)) {
 168                /* If packet is ecn capable, mark it if drop probability
 169                 * is lower than the parameter ecn_prob, else drop it.
 170                 */
 171                q->stats.ecn_mark++;
 172                enqueue = true;
 173        }
 174        if (enqueue) {
 175                /* Set enqueue time only when dq_rate_estimator is disabled. */
 176                if (!q->p_params.dq_rate_estimator)
 177                        pie_set_enqueue_time(skb);
 178
 179                pkt_len = qdisc_pkt_len(skb);
 180                q->stats.packets_in++;
 181                q->memory_usage += skb->truesize;
 182                sch->qstats.backlog += pkt_len;
 183                sch->q.qlen++;
 184                flow_queue_add(sel_flow, skb);
 185                if (list_empty(&sel_flow->flowchain)) {
 186                        list_add_tail(&sel_flow->flowchain, &q->new_flows);
 187                        q->new_flow_count++;
 188                        sel_flow->deficit = q->quantum;
 189                        sel_flow->qlen = 0;
 190                        sel_flow->backlog = 0;
 191                }
 192                sel_flow->qlen++;
 193                sel_flow->backlog += pkt_len;
 194                return NET_XMIT_SUCCESS;
 195        }
 196out:
 197        q->stats.dropped++;
 198        sel_flow->vars.accu_prob = 0;
 199        __qdisc_drop(skb, to_free);
 200        qdisc_qstats_drop(sch);
 201        return NET_XMIT_CN;
 202}
 203
 204static const struct nla_policy fq_pie_policy[TCA_FQ_PIE_MAX + 1] = {
 205        [TCA_FQ_PIE_LIMIT]              = {.type = NLA_U32},
 206        [TCA_FQ_PIE_FLOWS]              = {.type = NLA_U32},
 207        [TCA_FQ_PIE_TARGET]             = {.type = NLA_U32},
 208        [TCA_FQ_PIE_TUPDATE]            = {.type = NLA_U32},
 209        [TCA_FQ_PIE_ALPHA]              = {.type = NLA_U32},
 210        [TCA_FQ_PIE_BETA]               = {.type = NLA_U32},
 211        [TCA_FQ_PIE_QUANTUM]            = {.type = NLA_U32},
 212        [TCA_FQ_PIE_MEMORY_LIMIT]       = {.type = NLA_U32},
 213        [TCA_FQ_PIE_ECN_PROB]           = {.type = NLA_U32},
 214        [TCA_FQ_PIE_ECN]                = {.type = NLA_U32},
 215        [TCA_FQ_PIE_BYTEMODE]           = {.type = NLA_U32},
 216        [TCA_FQ_PIE_DQ_RATE_ESTIMATOR]  = {.type = NLA_U32},
 217};
 218
 219static inline struct sk_buff *dequeue_head(struct fq_pie_flow *flow)
 220{
 221        struct sk_buff *skb = flow->head;
 222
 223        flow->head = skb->next;
 224        skb->next = NULL;
 225        return skb;
 226}
 227
 228static struct sk_buff *fq_pie_qdisc_dequeue(struct Qdisc *sch)
 229{
 230        struct fq_pie_sched_data *q = qdisc_priv(sch);
 231        struct sk_buff *skb = NULL;
 232        struct fq_pie_flow *flow;
 233        struct list_head *head;
 234        u32 pkt_len;
 235
 236begin:
 237        head = &q->new_flows;
 238        if (list_empty(head)) {
 239                head = &q->old_flows;
 240                if (list_empty(head))
 241                        return NULL;
 242        }
 243
 244        flow = list_first_entry(head, struct fq_pie_flow, flowchain);
 245        /* Flow has exhausted all its credits */
 246        if (flow->deficit <= 0) {
 247                flow->deficit += q->quantum;
 248                list_move_tail(&flow->flowchain, &q->old_flows);
 249                goto begin;
 250        }
 251
 252        if (flow->head) {
 253                skb = dequeue_head(flow);
 254                pkt_len = qdisc_pkt_len(skb);
 255                sch->qstats.backlog -= pkt_len;
 256                sch->q.qlen--;
 257                qdisc_bstats_update(sch, skb);
 258        }
 259
 260        if (!skb) {
 261                /* force a pass through old_flows to prevent starvation */
 262                if (head == &q->new_flows && !list_empty(&q->old_flows))
 263                        list_move_tail(&flow->flowchain, &q->old_flows);
 264                else
 265                        list_del_init(&flow->flowchain);
 266                goto begin;
 267        }
 268
 269        flow->qlen--;
 270        flow->deficit -= pkt_len;
 271        flow->backlog -= pkt_len;
 272        q->memory_usage -= get_pie_cb(skb)->mem_usage;
 273        pie_process_dequeue(skb, &q->p_params, &flow->vars, flow->backlog);
 274        return skb;
 275}
 276
 277static int fq_pie_change(struct Qdisc *sch, struct nlattr *opt,
 278                         struct netlink_ext_ack *extack)
 279{
 280        struct fq_pie_sched_data *q = qdisc_priv(sch);
 281        struct nlattr *tb[TCA_FQ_PIE_MAX + 1];
 282        unsigned int len_dropped = 0;
 283        unsigned int num_dropped = 0;
 284        int err;
 285
 286        if (!opt)
 287                return -EINVAL;
 288
 289        err = nla_parse_nested(tb, TCA_FQ_PIE_MAX, opt, fq_pie_policy, extack);
 290        if (err < 0)
 291                return err;
 292
 293        sch_tree_lock(sch);
 294        if (tb[TCA_FQ_PIE_LIMIT]) {
 295                u32 limit = nla_get_u32(tb[TCA_FQ_PIE_LIMIT]);
 296
 297                q->p_params.limit = limit;
 298                sch->limit = limit;
 299        }
 300        if (tb[TCA_FQ_PIE_FLOWS]) {
 301                if (q->flows) {
 302                        NL_SET_ERR_MSG_MOD(extack,
 303                                           "Number of flows cannot be changed");
 304                        goto flow_error;
 305                }
 306                q->flows_cnt = nla_get_u32(tb[TCA_FQ_PIE_FLOWS]);
 307                if (!q->flows_cnt || q->flows_cnt > 65536) {
 308                        NL_SET_ERR_MSG_MOD(extack,
 309                                           "Number of flows must range in [1..65536]");
 310                        goto flow_error;
 311                }
 312        }
 313
 314        /* convert from microseconds to pschedtime */
 315        if (tb[TCA_FQ_PIE_TARGET]) {
 316                /* target is in us */
 317                u32 target = nla_get_u32(tb[TCA_FQ_PIE_TARGET]);
 318
 319                /* convert to pschedtime */
 320                q->p_params.target =
 321                        PSCHED_NS2TICKS((u64)target * NSEC_PER_USEC);
 322        }
 323
 324        /* tupdate is in jiffies */
 325        if (tb[TCA_FQ_PIE_TUPDATE])
 326                q->p_params.tupdate =
 327                        usecs_to_jiffies(nla_get_u32(tb[TCA_FQ_PIE_TUPDATE]));
 328
 329        if (tb[TCA_FQ_PIE_ALPHA])
 330                q->p_params.alpha = nla_get_u32(tb[TCA_FQ_PIE_ALPHA]);
 331
 332        if (tb[TCA_FQ_PIE_BETA])
 333                q->p_params.beta = nla_get_u32(tb[TCA_FQ_PIE_BETA]);
 334
 335        if (tb[TCA_FQ_PIE_QUANTUM])
 336                q->quantum = nla_get_u32(tb[TCA_FQ_PIE_QUANTUM]);
 337
 338        if (tb[TCA_FQ_PIE_MEMORY_LIMIT])
 339                q->memory_limit = nla_get_u32(tb[TCA_FQ_PIE_MEMORY_LIMIT]);
 340
 341        if (tb[TCA_FQ_PIE_ECN_PROB])
 342                q->ecn_prob = nla_get_u32(tb[TCA_FQ_PIE_ECN_PROB]);
 343
 344        if (tb[TCA_FQ_PIE_ECN])
 345                q->p_params.ecn = nla_get_u32(tb[TCA_FQ_PIE_ECN]);
 346
 347        if (tb[TCA_FQ_PIE_BYTEMODE])
 348                q->p_params.bytemode = nla_get_u32(tb[TCA_FQ_PIE_BYTEMODE]);
 349
 350        if (tb[TCA_FQ_PIE_DQ_RATE_ESTIMATOR])
 351                q->p_params.dq_rate_estimator =
 352                        nla_get_u32(tb[TCA_FQ_PIE_DQ_RATE_ESTIMATOR]);
 353
 354        /* Drop excess packets if new limit is lower */
 355        while (sch->q.qlen > sch->limit) {
 356                struct sk_buff *skb = fq_pie_qdisc_dequeue(sch);
 357
 358                len_dropped += qdisc_pkt_len(skb);
 359                num_dropped += 1;
 360                rtnl_kfree_skbs(skb, skb);
 361        }
 362        qdisc_tree_reduce_backlog(sch, num_dropped, len_dropped);
 363
 364        sch_tree_unlock(sch);
 365        return 0;
 366
 367flow_error:
 368        sch_tree_unlock(sch);
 369        return -EINVAL;
 370}
 371
 372static void fq_pie_timer(struct timer_list *t)
 373{
 374        struct fq_pie_sched_data *q = from_timer(q, t, adapt_timer);
 375        struct Qdisc *sch = q->sch;
 376        spinlock_t *root_lock; /* to lock qdisc for probability calculations */
 377        u32 idx;
 378
 379        root_lock = qdisc_lock(qdisc_root_sleeping(sch));
 380        spin_lock(root_lock);
 381
 382        for (idx = 0; idx < q->flows_cnt; idx++)
 383                pie_calculate_probability(&q->p_params, &q->flows[idx].vars,
 384                                          q->flows[idx].backlog);
 385
 386        /* reset the timer to fire after 'tupdate' jiffies. */
 387        if (q->p_params.tupdate)
 388                mod_timer(&q->adapt_timer, jiffies + q->p_params.tupdate);
 389
 390        spin_unlock(root_lock);
 391}
 392
 393static int fq_pie_init(struct Qdisc *sch, struct nlattr *opt,
 394                       struct netlink_ext_ack *extack)
 395{
 396        struct fq_pie_sched_data *q = qdisc_priv(sch);
 397        int err;
 398        u32 idx;
 399
 400        pie_params_init(&q->p_params);
 401        sch->limit = 10 * 1024;
 402        q->p_params.limit = sch->limit;
 403        q->quantum = psched_mtu(qdisc_dev(sch));
 404        q->sch = sch;
 405        q->ecn_prob = 10;
 406        q->flows_cnt = 1024;
 407        q->memory_limit = SZ_32M;
 408
 409        INIT_LIST_HEAD(&q->new_flows);
 410        INIT_LIST_HEAD(&q->old_flows);
 411        timer_setup(&q->adapt_timer, fq_pie_timer, 0);
 412
 413        if (opt) {
 414                err = fq_pie_change(sch, opt, extack);
 415
 416                if (err)
 417                        return err;
 418        }
 419
 420        err = tcf_block_get(&q->block, &q->filter_list, sch, extack);
 421        if (err)
 422                goto init_failure;
 423
 424        q->flows = kvcalloc(q->flows_cnt, sizeof(struct fq_pie_flow),
 425                            GFP_KERNEL);
 426        if (!q->flows) {
 427                err = -ENOMEM;
 428                goto init_failure;
 429        }
 430        for (idx = 0; idx < q->flows_cnt; idx++) {
 431                struct fq_pie_flow *flow = q->flows + idx;
 432
 433                INIT_LIST_HEAD(&flow->flowchain);
 434                pie_vars_init(&flow->vars);
 435        }
 436
 437        mod_timer(&q->adapt_timer, jiffies + HZ / 2);
 438
 439        return 0;
 440
 441init_failure:
 442        q->flows_cnt = 0;
 443
 444        return err;
 445}
 446
 447static int fq_pie_dump(struct Qdisc *sch, struct sk_buff *skb)
 448{
 449        struct fq_pie_sched_data *q = qdisc_priv(sch);
 450        struct nlattr *opts;
 451
 452        opts = nla_nest_start(skb, TCA_OPTIONS);
 453        if (!opts)
 454                return -EMSGSIZE;
 455
 456        /* convert target from pschedtime to us */
 457        if (nla_put_u32(skb, TCA_FQ_PIE_LIMIT, sch->limit) ||
 458            nla_put_u32(skb, TCA_FQ_PIE_FLOWS, q->flows_cnt) ||
 459            nla_put_u32(skb, TCA_FQ_PIE_TARGET,
 460                        ((u32)PSCHED_TICKS2NS(q->p_params.target)) /
 461                        NSEC_PER_USEC) ||
 462            nla_put_u32(skb, TCA_FQ_PIE_TUPDATE,
 463                        jiffies_to_usecs(q->p_params.tupdate)) ||
 464            nla_put_u32(skb, TCA_FQ_PIE_ALPHA, q->p_params.alpha) ||
 465            nla_put_u32(skb, TCA_FQ_PIE_BETA, q->p_params.beta) ||
 466            nla_put_u32(skb, TCA_FQ_PIE_QUANTUM, q->quantum) ||
 467            nla_put_u32(skb, TCA_FQ_PIE_MEMORY_LIMIT, q->memory_limit) ||
 468            nla_put_u32(skb, TCA_FQ_PIE_ECN_PROB, q->ecn_prob) ||
 469            nla_put_u32(skb, TCA_FQ_PIE_ECN, q->p_params.ecn) ||
 470            nla_put_u32(skb, TCA_FQ_PIE_BYTEMODE, q->p_params.bytemode) ||
 471            nla_put_u32(skb, TCA_FQ_PIE_DQ_RATE_ESTIMATOR,
 472                        q->p_params.dq_rate_estimator))
 473                goto nla_put_failure;
 474
 475        return nla_nest_end(skb, opts);
 476
 477nla_put_failure:
 478        nla_nest_cancel(skb, opts);
 479        return -EMSGSIZE;
 480}
 481
 482static int fq_pie_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 483{
 484        struct fq_pie_sched_data *q = qdisc_priv(sch);
 485        struct tc_fq_pie_xstats st = {
 486                .packets_in     = q->stats.packets_in,
 487                .overlimit      = q->stats.overlimit,
 488                .overmemory     = q->overmemory,
 489                .dropped        = q->stats.dropped,
 490                .ecn_mark       = q->stats.ecn_mark,
 491                .new_flow_count = q->new_flow_count,
 492                .memory_usage   = q->memory_usage,
 493        };
 494        struct list_head *pos;
 495
 496        sch_tree_lock(sch);
 497        list_for_each(pos, &q->new_flows)
 498                st.new_flows_len++;
 499
 500        list_for_each(pos, &q->old_flows)
 501                st.old_flows_len++;
 502        sch_tree_unlock(sch);
 503
 504        return gnet_stats_copy_app(d, &st, sizeof(st));
 505}
 506
 507static void fq_pie_reset(struct Qdisc *sch)
 508{
 509        struct fq_pie_sched_data *q = qdisc_priv(sch);
 510        u32 idx;
 511
 512        INIT_LIST_HEAD(&q->new_flows);
 513        INIT_LIST_HEAD(&q->old_flows);
 514        for (idx = 0; idx < q->flows_cnt; idx++) {
 515                struct fq_pie_flow *flow = q->flows + idx;
 516
 517                /* Removes all packets from flow */
 518                rtnl_kfree_skbs(flow->head, flow->tail);
 519                flow->head = NULL;
 520
 521                INIT_LIST_HEAD(&flow->flowchain);
 522                pie_vars_init(&flow->vars);
 523        }
 524
 525        sch->q.qlen = 0;
 526        sch->qstats.backlog = 0;
 527}
 528
 529static void fq_pie_destroy(struct Qdisc *sch)
 530{
 531        struct fq_pie_sched_data *q = qdisc_priv(sch);
 532
 533        tcf_block_put(q->block);
 534        del_timer_sync(&q->adapt_timer);
 535        kvfree(q->flows);
 536}
 537
 538static struct Qdisc_ops fq_pie_qdisc_ops __read_mostly = {
 539        .id             = "fq_pie",
 540        .priv_size      = sizeof(struct fq_pie_sched_data),
 541        .enqueue        = fq_pie_qdisc_enqueue,
 542        .dequeue        = fq_pie_qdisc_dequeue,
 543        .peek           = qdisc_peek_dequeued,
 544        .init           = fq_pie_init,
 545        .destroy        = fq_pie_destroy,
 546        .reset          = fq_pie_reset,
 547        .change         = fq_pie_change,
 548        .dump           = fq_pie_dump,
 549        .dump_stats     = fq_pie_dump_stats,
 550        .owner          = THIS_MODULE,
 551};
 552
 553static int __init fq_pie_module_init(void)
 554{
 555        return register_qdisc(&fq_pie_qdisc_ops);
 556}
 557
 558static void __exit fq_pie_module_exit(void)
 559{
 560        unregister_qdisc(&fq_pie_qdisc_ops);
 561}
 562
 563module_init(fq_pie_module_init);
 564module_exit(fq_pie_module_exit);
 565
 566MODULE_DESCRIPTION("Flow Queue Proportional Integral controller Enhanced (FQ-PIE)");
 567MODULE_AUTHOR("Mohit P. Tahiliani");
 568MODULE_LICENSE("GPL");
 569