From: Jim Gettys <jg@freedesktop.org>
To: "Dave Täht" <dave.taht@bufferbloat.net>
Cc: codel@lists.bufferbloat.net
Subject: Re: [Codel] [PATCH] Preliminary codel implementation
Date: Thu, 03 May 2012 16:47:52 -0400 [thread overview]
Message-ID: <4FA2EEF8.2070109@freedesktop.org> (raw)
In-Reply-To: <1336067533-16923-2-git-send-email-dave.taht@bufferbloat.net>
On 05/03/2012 01:52 PM, Dave Täht wrote:
> ---
> include/linux/pkt_sched.h | 29 +++++
> net/sched/Kconfig | 11 ++
> net/sched/Makefile | 1 +
> net/sched/sch_codel.c | 296 +++++++++++++++++++++++++++++++++++++++++++++
> 4 files changed, 337 insertions(+)
> create mode 100644 net/sched/sch_codel.c
>
> diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
> index 0d5b793..c21b720 100644
> --- a/include/linux/pkt_sched.h
> +++ b/include/linux/pkt_sched.h
> @@ -633,4 +633,33 @@ struct tc_qfq_stats {
> __u32 lmax;
> };
>
> +/* CODEL */
> +
> +enum {
> + TCA_CODEL_UNSPEC,
> + TCA_CODEL_PARMS,
> + TCA_CODEL_TARGET,
> + TCA_CODEL_DEPTH,
> + TCA_CODEL_MINBYTES,
> + TCA_CODEL_INTERVAL,
> + __TCA_CODEL_MAX
> +};
> +
> +#define TCA_CODEL_MAX (__TCA_CODEL_MAX - 1)
> +#define TC_CODEL_ECN 1
> +
> +struct tc_codel_qopt {
> + __u32 flags; /* flags (e.g. ecn) */
> + __u32 target; /* max delay, in us */
> + __u32 depth; /* queue depth in packets */
> + __u32 minbytes; /* MTU (usually) */
> + __u32 interval; /* Sliding min time window width (us) */
> +};
> +
> +struct tc_codel_stats {
> + __u64 drops;
> + __u64 marks;
> +};
> +
> +
> #endif
> diff --git a/net/sched/Kconfig b/net/sched/Kconfig
> index 2590e91..8106c42 100644
> --- a/net/sched/Kconfig
> +++ b/net/sched/Kconfig
> @@ -250,6 +250,17 @@ config NET_SCH_QFQ
>
> If unsure, say N.
>
> +config NET_SCH_CODEL
> + tristate "Controlled Delay AQM (CODEL)"
> + help
> + Say Y here if you want to use the Controlled Delay (CODEL)
> + packet scheduling algorithm.
> +
> + To compile this driver as a module, choose M here: the module
> + will be called sch_codel.
> +
> + If unsure, say N.
> +
> config NET_SCH_INGRESS
> tristate "Ingress Qdisc"
> depends on NET_CLS_ACT
> diff --git a/net/sched/Makefile b/net/sched/Makefile
> index dc5889c..41130b5 100644
> --- a/net/sched/Makefile
> +++ b/net/sched/Makefile
> @@ -36,6 +36,7 @@ obj-$(CONFIG_NET_SCH_DRR) += sch_drr.o
> obj-$(CONFIG_NET_SCH_MQPRIO) += sch_mqprio.o
> obj-$(CONFIG_NET_SCH_CHOKE) += sch_choke.o
> obj-$(CONFIG_NET_SCH_QFQ) += sch_qfq.o
> +obj-$(CONFIG_NET_SCH_CODEL) += sch_codel.o
>
> obj-$(CONFIG_NET_CLS_U32) += cls_u32.o
> obj-$(CONFIG_NET_CLS_ROUTE4) += cls_route.o
> diff --git a/net/sched/sch_codel.c b/net/sched/sch_codel.c
> new file mode 100644
> index 0000000..159df47
> --- /dev/null
> +++ b/net/sched/sch_codel.c
> @@ -0,0 +1,296 @@
> +/*
> + * net/sched/sch_codel.c A Codel implementation
> + *
> + * 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.
> + *
> + * Based on ns2 simulation code presented by Kathie Nichols
> + * Authors: Dave Täht <d@taht.net>
> + */
> +
> +#include <linux/module.h>
> +#include <linux/slab.h>
> +#include <linux/types.h>
> +#include <linux/kernel.h>
> +#include <linux/errno.h>
> +#include <linux/ktime.h>
> +#include <linux/skbuff.h>
> +#include <net/pkt_sched.h>
> +
> +#define MS2TIME(a) (ns_to_ktime( (u64) a*1000000))
> +#define DEFAULT_CODEL_DEPTH 1000
> +
> +/* Per-queue state (codel_queue_t instance variables) */
> +
> +struct codel_sched_data {
> + u32 flags;
> + u32 minbytes;
> + u32 count; /* packets dropped since we went into drop state */
> + bool dropping; /* 1 if in drop state, might just add to flags */
> + ktime_t target;
> + ktime_t interval;
> + /* time to declare above q->target (0 if below)*/
> + ktime_t first_above_time;
> + ktime_t drop_next; /* time to drop next packet */
> +};
> +
> +struct codel_skb_cb {
> + ktime_t enqueue_time;
> + char data[16];
> +};
> +
> +static inline struct codel_skb_cb *get_codel_cb(const struct sk_buff *skb)
> +{
> + return (struct codel_skb_cb *)skb->cb;
> +}
> +
> +static inline ktime_t get_enqueue_time(const struct sk_buff *skb) {
> + struct codel_skb_cb *cb = get_codel_cb(skb);
> + return cb->enqueue_time;
> +}
> +
> +static inline ktime_t set_enqueue_time(struct sk_buff *skb, ktime_t t ) {
> + struct codel_skb_cb *cb = get_codel_cb(skb);
> + cb->enqueue_time = t;
> + return t;
> +}
> +
> +static inline ktime_t control_law(const struct codel_sched_data *q, ktime_t t)
> +{
> + t.tv64 = t.tv64 + q->interval.tv64 / int_sqrt(q->count);
> + return t;
> +}
There is a note in the article at this point in its exposition of the
pseudo code:
"Note that for embedded systems or kernel implementation that the
inverse *sqrt* can be computed efficiently using only integer
multiplication."
That will likely be faster than the division by sqrt; if/when this
optimisation is done, we should leave comments about why it is division
by a square root, to correspond to TCP's control law.
Before we upstream this, I'd recommend taking the comments documenting
the algorithm from the article and including them. I think Kathie had
to trim on the slides.
- Jim
next prev parent reply other threads:[~2012-05-03 20:47 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-05-03 17:52 [Codel] [PATCH] iproute2: added preliminary codel support Dave Täht
2012-05-03 17:52 ` [Codel] [PATCH] Preliminary codel implementation Dave Täht
2012-05-03 18:01 ` Dave Taht
2012-05-03 18:17 ` Rick Jones
2012-05-03 18:19 ` Eric Dumazet
2012-05-03 18:17 ` Eric Dumazet
2012-05-03 22:38 ` Dave Taht
2012-05-03 20:47 ` Jim Gettys [this message]
2012-05-03 21:35 ` Dave Taht
2012-05-03 23:12 ` Jim Gettys
2012-05-03 17:59 ` [Codel] [PATCH] iproute2: added preliminary codel support Dave Taht
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://lists.bufferbloat.net/postorius/lists/codel.lists.bufferbloat.net/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=4FA2EEF8.2070109@freedesktop.org \
--to=jg@freedesktop.org \
--cc=codel@lists.bufferbloat.net \
--cc=dave.taht@bufferbloat.net \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox