cregit-Linux how code gets into the kernel

Release 4.11 net/sched/sch_gred.c

Directory: net/sched
/*
 * net/sched/sch_gred.c Generic Random Early Detection queue.
 *
 *
 *              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.
 *
 * Authors:    J Hadi Salim (hadi@cyberus.ca) 1998-2002
 *
 *             991129: -  Bug fix with grio mode
 *                     - a better sing. AvgQ mode with Grio(WRED)
 *                     - A finer grained VQ dequeue based on sugestion
 *                       from Ren Liu
 *                     - More error checks
 *
 *  For all the glorious comments look at include/net/red.h
 */

#include <linux/slab.h>
#include <linux/module.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/skbuff.h>
#include <net/pkt_sched.h>
#include <net/red.h>


#define GRED_DEF_PRIO (MAX_DPs / 2)

#define GRED_VQ_MASK (MAX_DPs - 1)

struct gred_sched_data;
struct gred_sched;


struct gred_sched_data {
	
u32		limit;		/* HARD maximal queue length    */
	
u32		DP;		/* the drop parameters */
	
u32		bytesin;	/* bytes seen on virtualQ so far*/
	
u32		packetsin;	/* packets seen on virtualQ so far*/
	
u32		backlog;	/* bytes on the virtualQ */
	
u8		prio;		/* the prio of this vq */

	
struct red_parms parms;
	
struct red_vars  vars;
	
struct red_stats stats;
};

enum {
	
GRED_WRED_MODE = 1,
	
GRED_RIO_MODE,
};


struct gred_sched {
	
struct gred_sched_data *tab[MAX_DPs];
	
unsigned long	flags;
	
u32		red_flags;
	
u32 		DPs;
	
u32 		def;
	
struct red_vars wred_set;
};


static inline int gred_wred_mode(struct gred_sched *table) { return test_bit(GRED_WRED_MODE, &table->flags); }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf23100.00%1100.00%
Total23100.00%1100.00%


static inline void gred_enable_wred_mode(struct gred_sched *table) { __set_bit(GRED_WRED_MODE, &table->flags); }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf22100.00%1100.00%
Total22100.00%1100.00%


static inline void gred_disable_wred_mode(struct gred_sched *table) { __clear_bit(GRED_WRED_MODE, &table->flags); }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf22100.00%1100.00%
Total22100.00%1100.00%


static inline int gred_rio_mode(struct gred_sched *table) { return test_bit(GRED_RIO_MODE, &table->flags); }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf23100.00%1100.00%
Total23100.00%1100.00%


static inline void gred_enable_rio_mode(struct gred_sched *table) { __set_bit(GRED_RIO_MODE, &table->flags); }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf22100.00%1100.00%
Total22100.00%1100.00%


static inline void gred_disable_rio_mode(struct gred_sched *table) { __clear_bit(GRED_RIO_MODE, &table->flags); }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf22100.00%1100.00%
Total22100.00%1100.00%


static inline int gred_wred_mode_check(struct Qdisc *sch) { struct gred_sched *table = qdisc_priv(sch); int i; /* Really ugly O(n^2) but shouldn't be necessary too frequent. */ for (i = 0; i < table->DPs; i++) { struct gred_sched_data *q = table->tab[i]; int n; if (q == NULL) continue; for (n = i + 1; n < table->DPs; n++) if (table->tab[n] && table->tab[n]->prio == q->prio) return 1; } return 0; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf10797.27%150.00%
David Ward32.73%150.00%
Total110100.00%2100.00%


static inline unsigned int gred_backlog(struct gred_sched *table, struct gred_sched_data *q, struct Qdisc *sch) { if (gred_wred_mode(table)) return sch->qstats.backlog; else return q->backlog; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf43100.00%1100.00%
Total43100.00%1100.00%


static inline u16 tc_index_to_dp(struct sk_buff *skb) { return skb->tc_index & GRED_VQ_MASK; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf19100.00%1100.00%
Total19100.00%1100.00%


static inline void gred_load_wred_set(const struct gred_sched *table, struct gred_sched_data *q) { q->vars.qavg = table->wred_set.qavg; q->vars.qidlestart = table->wred_set.qidlestart; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf3992.86%150.00%
Eric Dumazet37.14%150.00%
Total42100.00%2100.00%


static inline void gred_store_wred_set(struct gred_sched *table, struct gred_sched_data *q) { table->wred_set.qavg = q->vars.qavg; table->wred_set.qidlestart = q->vars.qidlestart; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf2868.29%133.33%
David Ward1229.27%133.33%
Eric Dumazet12.44%133.33%
Total41100.00%3100.00%


static inline int gred_use_ecn(struct gred_sched *t) { return t->red_flags & TC_RED_ECN; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf19100.00%1100.00%
Total19100.00%1100.00%


static inline int gred_use_harddrop(struct gred_sched *t) { return t->red_flags & TC_RED_HARDDROP; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf19100.00%1100.00%
Total19100.00%1100.00%


static int gred_enqueue(struct sk_buff *skb, struct Qdisc *sch, struct sk_buff **to_free) { struct gred_sched_data *q = NULL; struct gred_sched *t = qdisc_priv(sch); unsigned long qavg = 0; u16 dp = tc_index_to_dp(skb); if (dp >= t->DPs || (q = t->tab[dp]) == NULL) { dp = t->def; q = t->tab[dp]; if (!q) { /* Pass through packets not assigned to a DP * if no default DP has been configured. This * allows for DP flows to be left untouched. */ if (likely(sch->qstats.backlog + qdisc_pkt_len(skb) <= sch->limit)) return qdisc_enqueue_tail(skb, sch); else goto drop; } /* fix tc_index? --could be controversial but needed for requeueing */ skb->tc_index = (skb->tc_index & ~GRED_VQ_MASK) | dp; } /* sum up all the qaves of prios < ours to get the new qave */ if (!gred_wred_mode(t) && gred_rio_mode(t)) { int i; for (i = 0; i < t->DPs; i++) { if (t->tab[i] && t->tab[i]->prio < q->prio && !red_is_idling(&t->tab[i]->vars)) qavg += t->tab[i]->vars.qavg; } } q->packetsin++; q->bytesin += qdisc_pkt_len(skb); if (gred_wred_mode(t)) gred_load_wred_set(t, q); q->vars.qavg = red_calc_qavg(&q->parms, &q->vars, gred_backlog(t, q, sch)); if (red_is_idling(&q->vars)) red_end_of_idle_period(&q->vars); if (gred_wred_mode(t)) gred_store_wred_set(t, q); switch (red_action(&q->parms, &q->vars, q->vars.qavg + qavg)) { case RED_DONT_MARK: break; case RED_PROB_MARK: qdisc_qstats_overlimit(sch); if (!gred_use_ecn(t) || !INET_ECN_set_ce(skb)) { q->stats.prob_drop++; goto congestion_drop; } q->stats.prob_mark++; break; case RED_HARD_MARK: qdisc_qstats_overlimit(sch); if (gred_use_harddrop(t) || !gred_use_ecn(t) || !INET_ECN_set_ce(skb)) { q->stats.forced_drop++; goto congestion_drop; } q->stats.forced_mark++; break; } if (gred_backlog(t, q, sch) + qdisc_pkt_len(skb) <= q->limit) { q->backlog += qdisc_pkt_len(skb); return qdisc_enqueue_tail(skb, sch); } q->stats.pdrop++; drop: return qdisc_drop(skb, sch, to_free); congestion_drop: qdisc_drop(skb, sch, to_free); return NET_XMIT_CN; }

Contributors

PersonTokensPropCommitsCommitProp
Linus Torvalds (pre-git)22844.71%27.69%
Thomas Graf20339.80%1246.15%
Eric Dumazet326.27%311.54%
David Ward193.73%311.54%
Jussi Kivilinna91.76%13.85%
John Fastabend61.18%13.85%
Linus Torvalds61.18%13.85%
Stephen Hemminger30.59%13.85%
Patrick McHardy20.39%13.85%
David S. Miller20.39%13.85%
Total510100.00%26100.00%


static struct sk_buff *gred_dequeue(struct Qdisc *sch) { struct sk_buff *skb; struct gred_sched *t = qdisc_priv(sch); skb = qdisc_dequeue_head(sch); if (skb) { struct gred_sched_data *q; u16 dp = tc_index_to_dp(skb); if (dp >= t->DPs || (q = t->tab[dp]) == NULL) { net_warn_ratelimited("GRED: Unable to relocate VQ 0x%x after dequeue, screwing up backlog\n", tc_index_to_dp(skb)); } else { q->backlog -= qdisc_pkt_len(skb); if (gred_wred_mode(t)) { if (!sch->qstats.backlog) red_start_of_idle_period(&t->wred_set); } else { if (!q->backlog) red_start_of_idle_period(&q->vars); } } return skb; } return NULL; }

Contributors

PersonTokensPropCommitsCommitProp
Linus Torvalds (pre-git)7046.98%215.38%
Thomas Graf4731.54%753.85%
David Ward2416.11%17.69%
Jussi Kivilinna32.01%17.69%
Stephen Hemminger32.01%17.69%
Joe Perches21.34%17.69%
Total149100.00%13100.00%


static void gred_reset(struct Qdisc *sch) { int i; struct gred_sched *t = qdisc_priv(sch); qdisc_reset_queue(sch); for (i = 0; i < t->DPs; i++) { struct gred_sched_data *q = t->tab[i]; if (!q) continue; red_restart(&q->vars); q->backlog = 0; } }

Contributors

PersonTokensPropCommitsCommitProp
Linus Torvalds (pre-git)6684.62%116.67%
Thomas Graf810.26%350.00%
Stephen Hemminger33.85%116.67%
Eric Dumazet11.28%116.67%
Total78100.00%6100.00%


static inline void gred_destroy_vq(struct gred_sched_data *q) { kfree(q); }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf17100.00%1100.00%
Total17100.00%1100.00%


static inline int gred_change_table_def(struct Qdisc *sch, struct nlattr *dps) { struct gred_sched *table = qdisc_priv(sch); struct tc_gred_sopt *sopt; int i; if (dps == NULL) return -EINVAL; sopt = nla_data(dps); if (sopt->DPs > MAX_DPs || sopt->DPs == 0 || sopt->def_DP >= sopt->DPs) return -EINVAL; sch_tree_lock(sch); table->DPs = sopt->DPs; table->def = sopt->def_DP; table->red_flags = sopt->flags; /* * Every entry point to GRED is synchronized with the above code * and the DP is checked against DPs, i.e. shadowed VQs can no * longer be found so we can unlock right here. */ sch_tree_unlock(sch); if (sopt->grio) { gred_enable_rio_mode(table); gred_disable_wred_mode(table); if (gred_wred_mode_check(sch)) gred_enable_wred_mode(table); } else { gred_disable_rio_mode(table); gred_disable_wred_mode(table); } for (i = table->DPs; i < MAX_DPs; i++) { if (table->tab[i]) { pr_warn("GRED: Warning: Destroying shadowed VQ 0x%x\n", i); gred_destroy_vq(table->tab[i]); table->tab[i] = NULL; } } return 0; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf13563.38%444.44%
Linus Torvalds (pre-git)6229.11%111.11%
Jamal Hadi Salim94.23%111.11%
Stephen Hemminger31.41%111.11%
Yang Yingliang20.94%111.11%
Patrick McHardy20.94%111.11%
Total213100.00%9100.00%


static inline int gred_change_vq(struct Qdisc *sch, int dp, struct tc_gred_qopt *ctl, int prio, u8 *stab, u32 max_P, struct gred_sched_data **prealloc) { struct gred_sched *table = qdisc_priv(sch); struct gred_sched_data *q = table->tab[dp]; if (!q) { table->tab[dp] = q = *prealloc; *prealloc = NULL; if (!q) return -ENOMEM; } q->DP = dp; q->prio = prio; if (ctl->limit > sch->limit) q->limit = sch->limit; else q->limit = ctl->limit; if (q->backlog == 0) red_end_of_idle_period(&q->vars); red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog, ctl->Plog, ctl->Scell_log, stab, max_P); red_set_vars(&q->vars); return 0; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf8042.33%333.33%
Linus Torvalds (pre-git)5428.57%222.22%
Eric Dumazet3619.05%333.33%
David Ward1910.05%111.11%
Total189100.00%9100.00%

static const struct nla_policy gred_policy[TCA_GRED_MAX + 1] = { [TCA_GRED_PARMS] = { .len = sizeof(struct tc_gred_qopt) }, [TCA_GRED_STAB] = { .len = 256 }, [TCA_GRED_DPS] = { .len = sizeof(struct tc_gred_sopt) }, [TCA_GRED_MAX_P] = { .type = NLA_U32 }, [TCA_GRED_LIMIT] = { .type = NLA_U32 }, };
static int gred_change(struct Qdisc *sch, struct nlattr *opt) { struct gred_sched *table = qdisc_priv(sch); struct tc_gred_qopt *ctl; struct nlattr *tb[TCA_GRED_MAX + 1]; int err, prio = GRED_DEF_PRIO; u8 *stab; u32 max_P; struct gred_sched_data *prealloc; if (opt == NULL) return -EINVAL; err = nla_parse_nested(tb, TCA_GRED_MAX, opt, gred_policy); if (err < 0) return err; if (tb[TCA_GRED_PARMS] == NULL && tb[TCA_GRED_STAB] == NULL) { if (tb[TCA_GRED_LIMIT] != NULL) sch->limit = nla_get_u32(tb[TCA_GRED_LIMIT]); return gred_change_table_def(sch, opt); } if (tb[TCA_GRED_PARMS] == NULL || tb[TCA_GRED_STAB] == NULL || tb[TCA_GRED_LIMIT] != NULL) return -EINVAL; max_P = tb[TCA_GRED_MAX_P] ? nla_get_u32(tb[TCA_GRED_MAX_P]) : 0; err = -EINVAL; ctl = nla_data(tb[TCA_GRED_PARMS]); stab = nla_data(tb[TCA_GRED_STAB]); if (ctl->DP >= table->DPs) goto errout; if (gred_rio_mode(table)) { if (ctl->prio == 0) { int def_prio = GRED_DEF_PRIO; if (table->tab[table->def]) def_prio = table->tab[table->def]->prio; printk(KERN_DEBUG "GRED: DP %u does not have a prio " "setting default to %d\n", ctl->DP, def_prio); prio = def_prio; } else prio = ctl->prio; } prealloc = kzalloc(sizeof(*prealloc), GFP_KERNEL); sch_tree_lock(sch); err = gred_change_vq(sch, ctl->DP, ctl, prio, stab, max_P, &prealloc); if (err < 0) goto errout_locked; if (gred_rio_mode(table)) { gred_disable_wred_mode(table); if (gred_wred_mode_check(sch)) gred_enable_wred_mode(table); } err = 0; errout_locked: sch_tree_unlock(sch); kfree(prealloc); errout: return err; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf22156.81%218.18%
Linus Torvalds (pre-git)6215.94%327.27%
Eric Dumazet4812.34%218.18%
David Ward307.71%19.09%
Patrick McHardy287.20%327.27%
Total389100.00%11100.00%


static int gred_init(struct Qdisc *sch, struct nlattr *opt) { struct nlattr *tb[TCA_GRED_MAX + 1]; int err; if (opt == NULL) return -EINVAL; err = nla_parse_nested(tb, TCA_GRED_MAX, opt, gred_policy); if (err < 0) return err; if (tb[TCA_GRED_PARMS] || tb[TCA_GRED_STAB]) return -EINVAL; if (tb[TCA_GRED_LIMIT]) sch->limit = nla_get_u32(tb[TCA_GRED_LIMIT]); else sch->limit = qdisc_dev(sch)->tx_queue_len * psched_mtu(qdisc_dev(sch)); return gred_change_table_def(sch, tb[TCA_GRED_DPS]); }

Contributors

PersonTokensPropCommitsCommitProp
Linus Torvalds (pre-git)5140.16%112.50%
David Ward3527.56%112.50%
Patrick McHardy2418.90%337.50%
Thomas Graf86.30%112.50%
Jamal Hadi Salim53.94%112.50%
Phil Sutter43.15%112.50%
Total127100.00%8100.00%


static int gred_dump(struct Qdisc *sch, struct sk_buff *skb) { struct gred_sched *table = qdisc_priv(sch); struct nlattr *parms, *opts = NULL; int i; u32 max_p[MAX_DPs]; struct tc_gred_sopt sopt = { .DPs = table->DPs, .def_DP = table->def, .grio = gred_rio_mode(table), .flags = table->red_flags, }; opts = nla_nest_start(skb, TCA_OPTIONS); if (opts == NULL) goto nla_put_failure; if (nla_put(skb, TCA_GRED_DPS, sizeof(sopt), &sopt)) goto nla_put_failure; for (i = 0; i < MAX_DPs; i++) { struct gred_sched_data *q = table->tab[i]; max_p[i] = q ? q->parms.max_P : 0; } if (nla_put(skb, TCA_GRED_MAX_P, sizeof(max_p), max_p)) goto nla_put_failure; if (nla_put_u32(skb, TCA_GRED_LIMIT, sch->limit)) goto nla_put_failure; parms = nla_nest_start(skb, TCA_GRED_PARMS); if (parms == NULL) goto nla_put_failure; for (i = 0; i < MAX_DPs; i++) { struct gred_sched_data *q = table->tab[i]; struct tc_gred_qopt opt; unsigned long qavg; memset(&opt, 0, sizeof(opt)); if (!q) { /* hack -- fix at some point with proper message This is how we indicate to tc that there is no VQ at this DP */ opt.DP = MAX_DPs + i; goto append_opt; } opt.limit = q->limit; opt.DP = q->DP; opt.backlog = gred_backlog(table, q, sch); opt.prio = q->prio; opt.qth_min = q->parms.qth_min >> q->parms.Wlog; opt.qth_max = q->parms.qth_max >> q->parms.Wlog; opt.Wlog = q->parms.Wlog; opt.Plog = q->parms.Plog; opt.Scell_log = q->parms.Scell_log; opt.other = q->stats.other; opt.early = q->stats.prob_drop; opt.forced = q->stats.forced_drop; opt.pdrop = q->stats.pdrop; opt.packets = q->packetsin; opt.bytesin = q->bytesin; if (gred_wred_mode(table)) gred_load_wred_set(table, q); qavg = red_calc_qavg(&q->parms, &q->vars, q->vars.qavg >> q->parms.Wlog); opt.qave = qavg >> q->parms.Wlog; append_opt: if (nla_append(skb, sizeof(opt), &opt) < 0) goto nla_put_failure; } nla_nest_end(skb, parms); return nla_nest_end(skb, opts); nla_put_failure: nla_nest_cancel(skb, opts); return -EMSGSIZE; }

Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf22341.45%635.29%
Linus Torvalds (pre-git)14526.95%15.88%
Eric Dumazet6612.27%211.76%
David Ward509.29%423.53%
Patrick McHardy346.32%15.88%
David S. Miller173.16%211.76%
Stephen Hemminger30.56%15.88%
Total538100.00%17100.00%


static void gred_destroy(struct Qdisc *sch) { struct gred_sched *table = qdisc_priv(sch); int i; for (i = 0; i < table->DPs; i++) { if (table->tab[i]) gred_destroy_vq(table->tab[i]); } }

Contributors

PersonTokensPropCommitsCommitProp
Linus Torvalds (pre-git)5693.33%133.33%
Stephen Hemminger35.00%133.33%
Thomas Graf11.67%133.33%
Total60100.00%3100.00%

static struct Qdisc_ops gred_qdisc_ops __read_mostly = { .id = "gred", .priv_size = sizeof(struct gred_sched), .enqueue = gred_enqueue, .dequeue = gred_dequeue, .peek = qdisc_peek_head, .init = gred_init, .reset = gred_reset, .destroy = gred_destroy, .change = gred_change, .dump = gred_dump, .owner = THIS_MODULE, };
static int __init gred_module_init(void) { return register_qdisc(&gred_qdisc_ops); }

Contributors

PersonTokensPropCommitsCommitProp
Linus Torvalds (pre-git)1381.25%150.00%
Al Viro318.75%150.00%
Total16100.00%2100.00%


static void __exit gred_module_exit(void) { unregister_qdisc(&gred_qdisc_ops); }

Contributors

PersonTokensPropCommitsCommitProp
Linus Torvalds (pre-git)1280.00%150.00%
Al Viro320.00%150.00%
Total15100.00%2100.00%

module_init(gred_module_init) module_exit(gred_module_exit) MODULE_LICENSE("GPL");

Overall Contributors

PersonTokensPropCommitsCommitProp
Thomas Graf138846.27%1832.14%
Linus Torvalds (pre-git)91630.53%35.36%
Eric Dumazet2056.83%610.71%
David Ward2036.77%712.50%
Patrick McHardy1444.80%47.14%
Dave Jones270.90%11.79%
David S. Miller240.80%47.14%
Stephen Hemminger180.60%11.79%
Al Viro150.50%11.79%
Jamal Hadi Salim140.47%11.79%
Jussi Kivilinna120.40%11.79%
Linus Torvalds120.40%35.36%
John Fastabend60.20%11.79%
Jarek Poplawski50.17%11.79%
Phil Sutter40.13%11.79%
Tejun Heo30.10%11.79%
Joe Perches20.07%11.79%