CoDel AQM discussions
 help / color / mirror / Atom feed
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




  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