cregit-Linux how code gets into the kernel

Release 4.11 net/sched/sch_fq_codel.c

Directory: net/sched
/*
 * Fair Queue CoDel discipline
 *
 *      This program is free software; you can redistribute it and/or
 *      modify it under the terms of the GNU General Public License
 *      as published by the Free Software Foundation; either version
 *      2 of the License, or (at your option) any later version.
 *
 *  Copyright (C) 2012,2015 Eric Dumazet <edumazet@google.com>
 */

#include <linux/module.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/jiffies.h>
#include <linux/string.h>
#include <linux/in.h>
#include <linux/errno.h>
#include <linux/init.h>
#include <linux/skbuff.h>
#include <linux/jhash.h>
#include <linux/slab.h>
#include <linux/vmalloc.h>
#include <net/netlink.h>
#include <net/pkt_sched.h>
#include <net/pkt_cls.h>
#include <net/codel.h>
#include <net/codel_impl.h>
#include <net/codel_qdisc.h>

/*      Fair Queue CoDel.
 *
 * Principles :
 * Packets are classified (internal classifier or external) on flows.
 * This is a Stochastic model (as we use a hash, several flows
 *                             might be hashed on same slot)
 * Each flow has a CoDel managed queue.
 * Flows are linked onto two (Round Robin) lists,
 * so that new flows have priority on old ones.
 *
 * For a given flow, packets are not reordered (CoDel uses a FIFO)
 * head drops only.
 * ECN capability is on by default.
 * Low memory footprint (64 bytes per flow)
 */


struct fq_codel_flow {
	
struct sk_buff	  *head;
	
struct sk_buff	  *tail;
	
struct list_head  flowchain;
	
int		  deficit;
	
u32		  dropped; /* number of drops (or ECN marks) on this flow */
	
struct codel_vars cvars;
}; /* please try to keep this structure <= 64 bytes */


struct fq_codel_sched_data {
	
struct tcf_proto __rcu *filter_list; /* optional external classifier */
	
struct fq_codel_flow *flows;	/* Flows table [flows_cnt] */
	
u32		*backlogs;	/* backlog table [flows_cnt] */
	
u32		flows_cnt;	/* number of flows */
	
u32		quantum;	/* psched_mtu(qdisc_dev(sch)); */
	
u32		drop_batch_size;
	
u32		memory_limit;
	
struct codel_params cparams;
	
struct codel_stats cstats;
	
u32		memory_usage;
	
u32		drop_overmemory;
	
u32		drop_overlimit;
	
u32		new_flow_count;

	
struct list_head new_flows;	/* list of new flows */
	
struct list_head old_flows;	/* list of old flows */
};


static unsigned int fq_codel_hash(const struct fq_codel_sched_data *q, struct sk_buff *skb) { return reciprocal_scale(skb_get_hash(skb), q->flows_cnt); }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet2374.19%133.33%
Andrew Collins412.90%133.33%
Daniel Borkmann412.90%133.33%
Total31100.00%3100.00%


static unsigned int fq_codel_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr) { struct fq_codel_sched_data *q = qdisc_priv(sch); struct tcf_proto *filter; struct tcf_result res; int result; if (TC_H_MAJ(skb->priority) == sch->handle && TC_H_MIN(skb->priority) > 0 && TC_H_MIN(skb->priority) <= q->flows_cnt) return TC_H_MIN(skb->priority); filter = rcu_dereference_bh(q->filter_list); if (!filter) return fq_codel_hash(q, skb) + 1; *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; result = tc_classify(skb, filter, &res, false); if (result >= 0) { #ifdef CONFIG_NET_CLS_ACT switch (result) { case TC_ACT_STOLEN: case TC_ACT_QUEUED: *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN; case TC_ACT_SHOT: return 0; } #endif if (TC_H_MIN(res.classid) <= q->flows_cnt) return TC_H_MIN(res.classid); } return 0; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet17390.58%125.00%
John Fastabend157.85%125.00%
Daniel Borkmann21.05%125.00%
Valdis Kletnieks10.52%125.00%
Total191100.00%4100.00%

/* helper functions : might be changed when/if skb use a standard list_head */ /* remove one skb from head of slot queue */
static inline struct sk_buff *dequeue_head(struct fq_codel_flow *flow) { struct sk_buff *skb = flow->head; flow->head = skb->next; skb->next = NULL; return skb; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet40100.00%1100.00%
Total40100.00%1100.00%

/* add skb to flow queue (tail add) */
static inline void flow_queue_add(struct fq_codel_flow *flow, struct sk_buff *skb) { if (flow->head == NULL) flow->head = skb; else flow->tail->next = skb; flow->tail = skb; skb->next = NULL; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet52100.00%1100.00%
Total52100.00%1100.00%


static unsigned int fq_codel_drop(struct Qdisc *sch, unsigned int max_packets, struct sk_buff **to_free) { struct fq_codel_sched_data *q = qdisc_priv(sch); struct sk_buff *skb; unsigned int maxbacklog = 0, idx = 0, i, len; struct fq_codel_flow *flow; unsigned int threshold; unsigned int mem = 0; /* Queue is full! Find the fat flow and drop packet(s) from it. * This might sound expensive, but with 1024 flows, we scan * 4KB of memory, and we dont need to handle a complex tree * in fast path (packet queue/enqueue) with many cache misses. * In stress mode, we'll try to drop 64 packets from the flow, * amortizing this linear lookup to one cache line per drop. */ for (i = 0; i < q->flows_cnt; i++) { if (q->backlogs[i] > maxbacklog) { maxbacklog = q->backlogs[i]; idx = i; } } /* Our goal is to drop half of this fat flow backlog */ threshold = maxbacklog >> 1; flow = &q->flows[idx]; len = 0; i = 0; do { skb = dequeue_head(flow); len += qdisc_pkt_len(skb); mem += get_codel_cb(skb)->mem_usage; __qdisc_drop(skb, to_free); } while (++i < max_packets && len < threshold); flow->dropped += i; q->backlogs[idx] -= len; q->memory_usage -= mem; sch->qstats.drops += i; sch->qstats.backlog -= len; sch->q.qlen -= i; return idx; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet228100.00%5100.00%
Total228100.00%5100.00%


static int fq_codel_enqueue(struct sk_buff *skb, struct Qdisc *sch, struct sk_buff **to_free) { struct fq_codel_sched_data *q = qdisc_priv(sch); unsigned int idx, prev_backlog, prev_qlen; struct fq_codel_flow *flow; int uninitialized_var(ret); unsigned int pkt_len; bool memory_limited; idx = fq_codel_classify(skb, sch, &ret); if (idx == 0) { if (ret & __NET_XMIT_BYPASS) qdisc_qstats_drop(sch); __qdisc_drop(skb, to_free); return ret; } idx--; codel_set_enqueue_time(skb); flow = &q->flows[idx]; flow_queue_add(flow, skb); q->backlogs[idx] += qdisc_pkt_len(skb); qdisc_qstats_backlog_inc(sch, skb); if (list_empty(&flow->flowchain)) { list_add_tail(&flow->flowchain, &q->new_flows); q->new_flow_count++; flow->deficit = q->quantum; flow->dropped = 0; } get_codel_cb(skb)->mem_usage = skb->truesize; q->memory_usage += get_codel_cb(skb)->mem_usage; memory_limited = q->memory_usage > q->memory_limit; if (++sch->q.qlen <= sch->limit && !memory_limited) return NET_XMIT_SUCCESS; prev_backlog = sch->qstats.backlog; prev_qlen = sch->q.qlen; /* save this packet length as it might be dropped by fq_codel_drop() */ pkt_len = qdisc_pkt_len(skb); /* fq_codel_drop() is quite expensive, as it performs a linear search * in q->backlogs[] to find a fat flow. * So instead of dropping a single packet, drop half of its backlog * with a 64 packets limit to not add a too big cpu spike here. */ ret = fq_codel_drop(sch, q->drop_batch_size, to_free); prev_qlen -= sch->q.qlen; prev_backlog -= sch->qstats.backlog; q->drop_overlimit += prev_qlen; if (memory_limited) q->drop_overmemory += prev_qlen; /* As we dropped packet(s), better let upper stack know this. * If we dropped a packet for this flow, return NET_XMIT_CN, * but in this case, our parents wont increase their backlogs. */ if (ret == idx) { qdisc_tree_reduce_backlog(sch, prev_qlen - 1, prev_backlog - pkt_len); return NET_XMIT_CN; } qdisc_tree_reduce_backlog(sch, prev_qlen, prev_backlog); return NET_XMIT_SUCCESS; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet32493.91%666.67%
Américo Wang144.06%111.11%
John Fastabend61.74%111.11%
Vijay Subramanian10.29%111.11%
Total345100.00%9100.00%

/* This is the specific function called from codel_dequeue() * to dequeue a packet from queue. Note: backlog is handled in * codel, we dont need to reduce it here. */
static struct sk_buff *dequeue_func(struct codel_vars *vars, void *ctx) { struct Qdisc *sch = ctx; struct fq_codel_sched_data *q = qdisc_priv(sch); struct fq_codel_flow *flow; struct sk_buff *skb = NULL; flow = container_of(vars, struct fq_codel_flow, cvars); if (flow->head) { skb = dequeue_head(flow); q->backlogs[flow - q->flows] -= qdisc_pkt_len(skb); q->memory_usage -= get_codel_cb(skb)->mem_usage; sch->q.qlen--; sch->qstats.backlog -= qdisc_pkt_len(skb); } return skb; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet10183.47%480.00%
Michal Kazior2016.53%120.00%
Total121100.00%5100.00%


static void drop_func(struct sk_buff *skb, void *ctx) { struct Qdisc *sch = ctx; kfree_skb(skb); qdisc_qstats_drop(sch); }

Contributors

PersonTokensPropCommitsCommitProp
Michal Kazior2784.38%150.00%
Eric Dumazet515.62%150.00%
Total32100.00%2100.00%


static struct sk_buff *fq_codel_dequeue(struct Qdisc *sch) { struct fq_codel_sched_data *q = qdisc_priv(sch); struct sk_buff *skb; struct fq_codel_flow *flow; struct list_head *head; u32 prev_drop_count, prev_ecn_mark; unsigned int prev_backlog; begin: head = &q->new_flows; if (list_empty(head)) { head = &q->old_flows; if (list_empty(head)) return NULL; } flow = list_first_entry(head, struct fq_codel_flow, flowchain); if (flow->deficit <= 0) { flow->deficit += q->quantum; list_move_tail(&flow->flowchain, &q->old_flows); goto begin; } prev_drop_count = q->cstats.drop_count; prev_ecn_mark = q->cstats.ecn_mark; prev_backlog = sch->qstats.backlog; skb = codel_dequeue(sch, &sch->qstats.backlog, &q->cparams, &flow->cvars, &q->cstats, qdisc_pkt_len, codel_get_enqueue_time, drop_func, dequeue_func); flow->dropped += q->cstats.drop_count - prev_drop_count; flow->dropped += q->cstats.ecn_mark - prev_ecn_mark; if (!skb) { /* force a pass through old_flows to prevent starvation */ if ((head == &q->new_flows) && !list_empty(&q->old_flows)) list_move_tail(&flow->flowchain, &q->old_flows); else list_del_init(&flow->flowchain); goto begin; } qdisc_bstats_update(sch, skb); flow->deficit -= qdisc_pkt_len(skb); /* We cant call qdisc_tree_reduce_backlog() if our qlen is 0, * or HTB crashes. Defer it for next round. */ if (q->cstats.drop_count && sch->q.qlen) { qdisc_tree_reduce_backlog(sch, q->cstats.drop_count, q->cstats.drop_len); q->cstats.drop_count = 0; q->cstats.drop_len = 0; } return skb; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet29387.46%133.33%
Américo Wang288.36%133.33%
Michal Kazior144.18%133.33%
Total335100.00%3100.00%


static void fq_codel_flow_purge(struct fq_codel_flow *flow) { rtnl_kfree_skbs(flow->head, flow->tail); flow->head = NULL; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet28100.00%1100.00%
Total28100.00%1100.00%


static void fq_codel_reset(struct Qdisc *sch) { struct fq_codel_sched_data *q = qdisc_priv(sch); int i; INIT_LIST_HEAD(&q->new_flows); INIT_LIST_HEAD(&q->old_flows); for (i = 0; i < q->flows_cnt; i++) { struct fq_codel_flow *flow = q->flows + i; fq_codel_flow_purge(flow); INIT_LIST_HEAD(&flow->flowchain); codel_vars_init(&flow->cvars); } memset(q->backlogs, 0, q->flows_cnt * sizeof(u32)); sch->q.qlen = 0; sch->qstats.backlog = 0; q->memory_usage = 0; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet129100.00%4100.00%
Total129100.00%4100.00%

static const struct nla_policy fq_codel_policy[TCA_FQ_CODEL_MAX + 1] = { [TCA_FQ_CODEL_TARGET] = { .type = NLA_U32 }, [TCA_FQ_CODEL_LIMIT] = { .type = NLA_U32 }, [TCA_FQ_CODEL_INTERVAL] = { .type = NLA_U32 }, [TCA_FQ_CODEL_ECN] = { .type = NLA_U32 }, [TCA_FQ_CODEL_FLOWS] = { .type = NLA_U32 }, [TCA_FQ_CODEL_QUANTUM] = { .type = NLA_U32 }, [TCA_FQ_CODEL_CE_THRESHOLD] = { .type = NLA_U32 }, [TCA_FQ_CODEL_DROP_BATCH_SIZE] = { .type = NLA_U32 }, [TCA_FQ_CODEL_MEMORY_LIMIT] = { .type = NLA_U32 }, };
static int fq_codel_change(struct Qdisc *sch, struct nlattr *opt) { struct fq_codel_sched_data *q = qdisc_priv(sch); struct nlattr *tb[TCA_FQ_CODEL_MAX + 1]; int err; if (!opt) return -EINVAL; err = nla_parse_nested(tb, TCA_FQ_CODEL_MAX, opt, fq_codel_policy); if (err < 0) return err; if (tb[TCA_FQ_CODEL_FLOWS]) { if (q->flows) return -EINVAL; q->flows_cnt = nla_get_u32(tb[TCA_FQ_CODEL_FLOWS]); if (!q->flows_cnt || q->flows_cnt > 65536) return -EINVAL; } sch_tree_lock(sch); if (tb[TCA_FQ_CODEL_TARGET]) { u64 target = nla_get_u32(tb[TCA_FQ_CODEL_TARGET]); q->cparams.target = (target * NSEC_PER_USEC) >> CODEL_SHIFT; } if (tb[TCA_FQ_CODEL_CE_THRESHOLD]) { u64 val = nla_get_u32(tb[TCA_FQ_CODEL_CE_THRESHOLD]); q->cparams.ce_threshold = (val * NSEC_PER_USEC) >> CODEL_SHIFT; } if (tb[TCA_FQ_CODEL_INTERVAL]) { u64 interval = nla_get_u32(tb[TCA_FQ_CODEL_INTERVAL]); q->cparams.interval = (interval * NSEC_PER_USEC) >> CODEL_SHIFT; } if (tb[TCA_FQ_CODEL_LIMIT]) sch->limit = nla_get_u32(tb[TCA_FQ_CODEL_LIMIT]); if (tb[TCA_FQ_CODEL_ECN]) q->cparams.ecn = !!nla_get_u32(tb[TCA_FQ_CODEL_ECN]); if (tb[TCA_FQ_CODEL_QUANTUM]) q->quantum = max(256U, nla_get_u32(tb[TCA_FQ_CODEL_QUANTUM])); if (tb[TCA_FQ_CODEL_DROP_BATCH_SIZE]) q->drop_batch_size = min(1U, nla_get_u32(tb[TCA_FQ_CODEL_DROP_BATCH_SIZE])); if (tb[TCA_FQ_CODEL_MEMORY_LIMIT]) q->memory_limit = min(1U << 31, nla_get_u32(tb[TCA_FQ_CODEL_MEMORY_LIMIT])); while (sch->q.qlen > sch->limit || q->memory_usage > q->memory_limit) { struct sk_buff *skb = fq_codel_dequeue(sch); q->cstats.drop_len += qdisc_pkt_len(skb); rtnl_kfree_skbs(skb, skb); q->cstats.drop_count++; } qdisc_tree_reduce_backlog(sch, q->cstats.drop_count, q->cstats.drop_len); q->cstats.drop_count = 0; q->cstats.drop_len = 0; sch_tree_unlock(sch); return 0; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet41394.08%583.33%
Américo Wang265.92%116.67%
Total439100.00%6100.00%


static void *fq_codel_zalloc(size_t sz) { void *ptr = kzalloc(sz, GFP_KERNEL | __GFP_NOWARN); if (!ptr) ptr = vzalloc(sz); return ptr; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet38100.00%1100.00%
Total38100.00%1100.00%


static void fq_codel_free(void *addr) { kvfree(addr); }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet1493.33%150.00%
Américo Wang16.67%150.00%
Total15100.00%2100.00%


static void fq_codel_destroy(struct Qdisc *sch) { struct fq_codel_sched_data *q = qdisc_priv(sch); tcf_destroy_chain(&q->filter_list); fq_codel_free(q->backlogs); fq_codel_free(q->flows); }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet43100.00%1100.00%
Total43100.00%1100.00%


static int fq_codel_init(struct Qdisc *sch, struct nlattr *opt) { struct fq_codel_sched_data *q = qdisc_priv(sch); int i; sch->limit = 10*1024; q->flows_cnt = 1024; q->memory_limit = 32 << 20; /* 32 MBytes */ q->drop_batch_size = 64; q->quantum = psched_mtu(qdisc_dev(sch)); INIT_LIST_HEAD(&q->new_flows); INIT_LIST_HEAD(&q->old_flows); codel_params_init(&q->cparams); codel_stats_init(&q->cstats); q->cparams.ecn = true; q->cparams.mtu = psched_mtu(qdisc_dev(sch)); if (opt) { int err = fq_codel_change(sch, opt); if (err) return err; } if (!q->flows) { q->flows = fq_codel_zalloc(q->flows_cnt * sizeof(struct fq_codel_flow)); if (!q->flows) return -ENOMEM; q->backlogs = fq_codel_zalloc(q->flows_cnt * sizeof(u32)); if (!q->backlogs) { fq_codel_free(q->flows); return -ENOMEM; } for (i = 0; i < q->flows_cnt; i++) { struct fq_codel_flow *flow = q->flows + i; INIT_LIST_HEAD(&flow->flowchain); codel_vars_init(&flow->cvars); } } if (sch->limit >= 1) sch->flags |= TCQ_F_CAN_BYPASS; else sch->flags &= ~TCQ_F_CAN_BYPASS; return 0; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet27595.16%480.00%
Michal Kazior144.84%120.00%
Total289100.00%5100.00%


static int fq_codel_dump(struct Qdisc *sch, struct sk_buff *skb) { struct fq_codel_sched_data *q = qdisc_priv(sch); struct nlattr *opts; opts = nla_nest_start(skb, TCA_OPTIONS); if (opts == NULL) goto nla_put_failure; if (nla_put_u32(skb, TCA_FQ_CODEL_TARGET, codel_time_to_us(q->cparams.target)) || nla_put_u32(skb, TCA_FQ_CODEL_LIMIT, sch->limit) || nla_put_u32(skb, TCA_FQ_CODEL_INTERVAL, codel_time_to_us(q->cparams.interval)) || nla_put_u32(skb, TCA_FQ_CODEL_ECN, q->cparams.ecn) || nla_put_u32(skb, TCA_FQ_CODEL_QUANTUM, q->quantum) || nla_put_u32(skb, TCA_FQ_CODEL_DROP_BATCH_SIZE, q->drop_batch_size) || nla_put_u32(skb, TCA_FQ_CODEL_MEMORY_LIMIT, q->memory_limit) || nla_put_u32(skb, TCA_FQ_CODEL_FLOWS, q->flows_cnt)) goto nla_put_failure; if (q->cparams.ce_threshold != CODEL_DISABLED_THRESHOLD && nla_put_u32(skb, TCA_FQ_CODEL_CE_THRESHOLD, codel_time_to_us(q->cparams.ce_threshold))) goto nla_put_failure; return nla_nest_end(skb, opts); nla_put_failure: return -1; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet19699.49%480.00%
Yang Yingliang10.51%120.00%
Total197100.00%5100.00%


static int fq_codel_dump_stats(struct Qdisc *sch, struct gnet_dump *d) { struct fq_codel_sched_data *q = qdisc_priv(sch); struct tc_fq_codel_xstats st = { .type = TCA_FQ_CODEL_XSTATS_QDISC, }; struct list_head *pos; st.qdisc_stats.maxpacket = q->cstats.maxpacket; st.qdisc_stats.drop_overlimit = q->drop_overlimit; st.qdisc_stats.ecn_mark = q->cstats.ecn_mark; st.qdisc_stats.new_flow_count = q->new_flow_count; st.qdisc_stats.ce_mark = q->cstats.ce_mark; st.qdisc_stats.memory_usage = q->memory_usage; st.qdisc_stats.drop_overmemory = q->drop_overmemory; sch_tree_lock(sch); list_for_each(pos, &q->new_flows) st.qdisc_stats.new_flows_len++; list_for_each(pos, &q->old_flows) st.qdisc_stats.old_flows_len++; sch_tree_unlock(sch); return gnet_stats_copy_app(d, &st, sizeof(st)); }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet15391.07%480.00%
Sasha Levin158.93%120.00%
Total168100.00%5100.00%


static struct Qdisc *fq_codel_leaf(struct Qdisc *sch, unsigned long arg) { return NULL; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet20100.00%1100.00%
Total20100.00%1100.00%


static unsigned long fq_codel_get(struct Qdisc *sch, u32 classid) { return 0; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet18100.00%1100.00%
Total18100.00%1100.00%


static unsigned long fq_codel_bind(struct Qdisc *sch, unsigned long parent, u32 classid) { /* we cannot bypass queue discipline anymore */ sch->flags &= ~TCQ_F_CAN_BYPASS; return 0; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet30100.00%1100.00%
Total30100.00%1100.00%


static void fq_codel_put(struct Qdisc *q, unsigned long cl) { }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet14100.00%1100.00%
Total14100.00%1100.00%


static struct tcf_proto __rcu **fq_codel_find_tcf(struct Qdisc *sch, unsigned long cl) { struct fq_codel_sched_data *q = qdisc_priv(sch); if (cl) return NULL; return &q->filter_list; }

Contributors

PersonTokensPropCommitsCommitProp
Eric Dumazet4197.62%150.00%
John Fastabend12.38%150.00%
Total42100.00%2100.00%


static int fq_codel_dump_class(struct Qdisc *sch, unsigned long cl, struct sk_buff *skb, struct tcmsg *tcm) { tcm->tcm_handle |=