[PATCH 09/10] Change perturb_period to unsigned.

[PATCH 09/10] Change perturb_period to unsigned.

[Corey Hickey]

perturb_period is currently a signed integer, but I can't see any good
reason why this is so--a negative perturbation period will add a timer
that expires in the past, causing constant perturbation, which makes
hashing useless.

	if (q->perturb_period) {
		q->perturb_timer.expires = jiffies + q->perturb_period;
		add_timer(&q->perturb_timer);
	}

Strictly speaking, this will break binary compatibility with older
versions of tc, but that ought not to be a problem because (a) there's
no valid use for a negative perturb_period, and (b) negative values
will be seen as high values (> INT_MAX), which don't work anyway.

If perturb_period is too large, (perturb_period * HZ) will overflow the
size of an unsigned int and wrap around. So, check for thet and reject
values that are too high.

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 include/linux/pkt_sched.h |    2 +-
 net/sched/sch_sfq.c       |    8 ++++++--
 2 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index 58a0ea6..8559974 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -142,7 +142,7 @@ enum
 struct tc_sfq_qopt
 {
 	unsigned	quantum;	/* Bytes per round allocated to flow */
-	int		perturb_period;	/* Period of hash perturbation */
+	unsigned	perturb_period;	/* Period of hash perturbation */
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index f9f4460..157adc8 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -74,6 +74,9 @@
 typedef unsigned int sfq_index;
 #define SFQ_MAX_DEPTH (UINT_MAX / 2 - 1)
 
+/* We don't want perturb_period * HZ to overflow an unsigned int. */
+#define SFQ_MAX_PERTURB (UINT_MAX / HZ)
+
 struct sfq_head
 {
 	sfq_index	next;
@@ -83,7 +86,7 @@ struct sfq_head
 struct sfq_sched_data
 {
 /* Parameters */
-	int		perturb_period;
+	unsigned	perturb_period;
 	unsigned	quantum;	/* Allotment per round: MUST BE >= MTU */
 	int		limit;
 	unsigned	depth;
@@ -440,7 +443,8 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 		if (ctl->limit)
 			q->limit = ctl->limit;
 
-		if (q->depth > SFQ_MAX_DEPTH)
+		if (q->perturb_period > SFQ_MAX_PERTURB ||
+		    q->depth > SFQ_MAX_DEPTH)
 			return -EINVAL;
 	}
 	q->limit = min_t(u32, q->limit, q->depth);
-- 
1.5.2.4

SFQ: backport some features from ESFQ (try 4)

[Corey Hickey]

Patchset try 2 addresses the review by Michael Buesch.
Patchset try 3 addresses the review by Patrick McHardy.
Patchset try 4 has a few cosmetic improvements.

Nobody reviewed my last set of patches, and I wasn't pushy about asking.
Since it's been a while, I ported the kernel and userspace patchsets to
current git of net-2.6 and iproute2, respectively.

The first 7 patches in this series resemble the corresponding 7 patches
in patchset try 2. There aren't any major changes--just modifications
to address errors noticed in review and slight reorganizations to make
the next patches easier.

Patches 8-10 implement parameter passing via nested compat attributes.
This is necessary for using 'tc qdisc change' to disable perturbation.
The rest of the parameters were added for consistency.

Iproute2 patches will follow shortly.



The following is the original patch text.

This set of patches adds some of ESFQ's modifications to the original 
SFQ. Thus far, I have received support for this approach rather than for 
trying to get ESFQ included as a separate qdisc.

http://mailman.ds9a.nl/pipermail/lartc/2007q2/021056.html

My patches here implement "tc qdisc change", user-configurable depth 
(number of flows), and user-configurable divisor (for setting hash table 
size). I've left out the remaining ESFQ features (usage of jhash and 
different hashing methods) because Patrick McHardy intends to submit a 
patch that will supersede that functionality; see the URL above.

Default values remain the same, and SFQ's default behavior remains the 
same, so there should be no user disruption.

Thanks for your consideration,
Corey



 include/linux/pkt_sched.h |   23 ++--
 net/sched/sch_sfq.c       |  353 ++++++++++++++++++++++++++++++---------------
 2 files changed, 254 insertions(+), 122 deletions(-)


[PATCH 01/10] Preparatory refactoring part 1.
[PATCH 02/10] Preparatory refactoring part 2.
[PATCH 03/10] Move two functions.
[PATCH 04/10] Make "depth" (number of queues) user-configurable:
[PATCH 05/10] Add divisor.
[PATCH 06/10] Make qdisc changeable.
[PATCH 07/10] Remove comments about hardcoded values.
[PATCH 08/10] Multiply perturb_period by HZ when used rather than when assigned.
[PATCH 09/10] Change perturb_period to unsigned.
[PATCH 10/10] Use nested compat attributes to pass parameters.

[PATCH 01/10] Preparatory refactoring part 1.

[Corey Hickey]

Make a new function sfq_q_enqueue() that operates directly on the
queue data. This will be useful for implementing sfq_change() in
a later patch. A pleasant side-effect is reducing most of the
duplicate code in sfq_enqueue() and sfq_requeue().

Similarly, make a new function sfq_q_dequeue().

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 net/sched/sch_sfq.c |   72 +++++++++++++++++++++++++++------------------------
 1 files changed, 38 insertions(+), 34 deletions(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 3a23e30..57485ef 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -77,6 +77,9 @@
 #define SFQ_DEPTH		128
 #define SFQ_HASH_DIVISOR	1024
 
+#define SFQ_HEAD 0
+#define SFQ_TAIL 1
+
 /* This type should contain at least SFQ_DEPTH*2 values */
 typedef unsigned char sfq_index;
 
@@ -244,10 +247,9 @@ static unsigned int sfq_drop(struct Qdisc *sch)
 	return 0;
 }
 
-static int
-sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
+static void
+sfq_q_enqueue(struct sk_buff *skb, struct sfq_sched_data *q, unsigned int end)
 {
-	struct sfq_sched_data *q = qdisc_priv(sch);
 	unsigned hash = sfq_hash(q, skb);
 	sfq_index x;
 
@@ -256,8 +258,12 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 		q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
 		q->hash[x] = hash;
 	}
-	sch->qstats.backlog += skb->len;
-	__skb_queue_tail(&q->qs[x], skb);
+
+	if (end == SFQ_TAIL)
+		__skb_queue_tail(&q->qs[x], skb);
+	else
+		__skb_queue_head(&q->qs[x], skb);
+
 	sfq_inc(q, x);
 	if (q->qs[x].qlen == 1) {		/* The flow is new */
 		if (q->tail == SFQ_DEPTH) {	/* It is the first flow */
@@ -270,6 +276,15 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 			q->tail = x;
 		}
 	}
+}
+
+static int
+sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
+{
+	struct sfq_sched_data *q = qdisc_priv(sch);
+
+	sfq_q_enqueue(skb, q, SFQ_TAIL);
+	sch->qstats.backlog += skb->len;
 	if (++sch->q.qlen <= q->limit) {
 		sch->bstats.bytes += skb->len;
 		sch->bstats.packets++;
@@ -284,45 +299,21 @@ static int
 sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
-	unsigned hash = sfq_hash(q, skb);
-	sfq_index x;
 
-	x = q->ht[hash];
-	if (x == SFQ_DEPTH) {
-		q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
-		q->hash[x] = hash;
-	}
+	sfq_q_enqueue(skb, q, SFQ_HEAD);
 	sch->qstats.backlog += skb->len;
-	__skb_queue_head(&q->qs[x], skb);
-	sfq_inc(q, x);
-	if (q->qs[x].qlen == 1) {		/* The flow is new */
-		if (q->tail == SFQ_DEPTH) {	/* It is the first flow */
-			q->tail = x;
-			q->next[x] = x;
-			q->allot[x] = q->quantum;
-		} else {
-			q->next[x] = q->next[q->tail];
-			q->next[q->tail] = x;
-			q->tail = x;
-		}
-	}
 	if (++sch->q.qlen <= q->limit) {
 		sch->qstats.requeues++;
 		return 0;
 	}
 
-	sch->qstats.drops++;
 	sfq_drop(sch);
 	return NET_XMIT_CN;
 }
 
-
-
-
-static struct sk_buff *
-sfq_dequeue(struct Qdisc* sch)
+static struct
+sk_buff *sfq_q_dequeue(struct sfq_sched_data *q)
 {
-	struct sfq_sched_data *q = qdisc_priv(sch);
 	struct sk_buff *skb;
 	sfq_index a, old_a;
 
@@ -335,8 +326,6 @@ sfq_dequeue(struct Qdisc* sch)
 	/* Grab packet */
 	skb = __skb_dequeue(&q->qs[a]);
 	sfq_dec(q, a);
-	sch->q.qlen--;
-	sch->qstats.backlog -= skb->len;
 
 	/* Is the slot empty? */
 	if (q->qs[a].qlen == 0) {
@@ -353,6 +342,21 @@ sfq_dequeue(struct Qdisc* sch)
 		a = q->next[a];
 		q->allot[a] += q->quantum;
 	}
+
+	return skb;
+}
+
+static struct sk_buff
+*sfq_dequeue(struct Qdisc* sch)
+{
+	struct sfq_sched_data *q = qdisc_priv(sch);
+	struct sk_buff *skb;
+
+	skb = sfq_q_dequeue(q);
+	if (skb == NULL)
+		return NULL;
+	sch->q.qlen--;
+	sch->qstats.backlog -= skb->len;
 	return skb;
 }
 
-- 
1.5.3

[PATCH 02/10] Preparatory refactoring part 2.

[Corey Hickey]

Factor code out of sfq_init() and sfq_destroy(), again so that the
new functions can be used by sfq_change() later.

Actually, as the diff itself shows, most of the sfq_q_init() code
comes from the original sfq_change(), but sfq_change() is only
called by sfq_init() right now. Thus, it is safe to remove
sfq_change(); "tc qdisc change" doesn't yet work for sfq anyway.

Setting default parameters is moved into a separate function for
clarity.

The sfq_destroy() --> sfq_q_destroy() change looks pointless here,
but it's cleaner to split now and add code to sfq_q_destroy() in a
later patch.

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 net/sched/sch_sfq.c |   95 +++++++++++++++++++++++++++++----------------------
 1 files changed, 54 insertions(+), 41 deletions(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 57485ef..1ba3d1a 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -382,43 +382,41 @@ static void sfq_perturbation(unsigned long arg)
 	}
 }
 
-static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
+static void
+sfq_default_parameters(struct Qdisc *sch)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
-	struct tc_sfq_qopt *ctl = RTA_DATA(opt);
-	unsigned int qlen;
-
-	if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
-		return -EINVAL;
-
-	sch_tree_lock(sch);
-	q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
-	q->perturb_period = ctl->perturb_period*HZ;
-	if (ctl->limit)
-		q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 2);
 
-	qlen = sch->q.qlen;
-	while (sch->q.qlen > q->limit)
-		sfq_drop(sch);
-	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
-
-	del_timer(&q->perturb_timer);
-	if (q->perturb_period) {
-		q->perturb_timer.expires = jiffies + q->perturb_period;
-		add_timer(&q->perturb_timer);
-	}
-	sch_tree_unlock(sch);
-	return 0;
+	q->quantum        = psched_mtu(sch->dev);
+	q->perturbation   = 0;
+	q->perturb_period = 0;
+	q->limit          = SFQ_DEPTH - 2;
 }
 
-static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
+static int
+sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 {
-	struct sfq_sched_data *q = qdisc_priv(sch);
 	int i;
 
-	init_timer(&q->perturb_timer);
-	q->perturb_timer.data = (unsigned long)sch;
-	q->perturb_timer.function = sfq_perturbation;
+	/* At this point, parameters are set to either defaults (sfq_init) or
+	 * the previous values (sfq_change). So, overwrite the parameters as
+	 * specified. */
+	if (opt) {
+		struct tc_sfq_qopt *ctl = RTA_DATA(opt);
+
+		if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
+			return -EINVAL;
+
+		if (ctl->quantum)
+			q->quantum = ctl->quantum;
+		if (ctl->perturb_period)
+			q->perturb_period = ctl->perturb_period * HZ;
+		if (ctl->limit)
+			q->limit = ctl->limit;
+	}
+	q->limit = min_t(u32, q->limit, SFQ_DEPTH - 2);
+	q->tail = SFQ_DEPTH;
+	q->max_depth = 0;
 
 	for (i=0; i<SFQ_HASH_DIVISOR; i++)
 		q->ht[i] = SFQ_DEPTH;
@@ -427,28 +425,43 @@ static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 		q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
 		q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
 	}
-	q->limit = SFQ_DEPTH - 2;
-	q->max_depth = 0;
-	q->tail = SFQ_DEPTH;
-	if (opt == NULL) {
-		q->quantum = psched_mtu(sch->dev);
-		q->perturb_period = 0;
-	} else {
-		int err = sfq_change(sch, opt);
-		if (err)
-			return err;
-	}
+
 	for (i=0; i<SFQ_DEPTH; i++)
 		sfq_link(q, i);
 	return 0;
 }
 
-static void sfq_destroy(struct Qdisc *sch)
+static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
+	int err;
+
+	sfq_default_parameters(sch);
+	if ((err = sfq_q_init(q, opt)))
+		return err;
+
+	init_timer(&q->perturb_timer);
+	q->perturb_timer.data = (unsigned long)sch;
+	q->perturb_timer.function = sfq_perturbation;
+	if (q->perturb_period) {
+		q->perturb_timer.expires = jiffies + q->perturb_period;
+		add_timer(&q->perturb_timer);
+	}
+
+	return 0;
+}
+
+static void sfq_q_destroy(struct sfq_sched_data *q)
+{
 	del_timer(&q->perturb_timer);
 }
 
+static void sfq_destroy(struct Qdisc *sch)
+{
+	struct sfq_sched_data *q = qdisc_priv(sch);
+	sfq_q_destroy(q);
+}
+
 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
-- 
1.5.3

[PATCH 03/10] Move two functions.

[Corey Hickey]

Move sfq_q_destroy() to above sfq_q_init() so that it can be used
by an error case in a later patch.

Move sfq_destroy() as well, for clarity.

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 net/sched/sch_sfq.c |   22 +++++++++++-----------
 1 files changed, 11 insertions(+), 11 deletions(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 1ba3d1a..ca22cb7 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -382,6 +382,17 @@ static void sfq_perturbation(unsigned long arg)
 	}
 }
 
+static void sfq_q_destroy(struct sfq_sched_data *q)
+{
+	del_timer(&q->perturb_timer);
+}
+
+static void sfq_destroy(struct Qdisc *sch)
+{
+	struct sfq_sched_data *q = qdisc_priv(sch);
+	sfq_q_destroy(q);
+}
+
 static void
 sfq_default_parameters(struct Qdisc *sch)
 {
@@ -451,17 +462,6 @@ static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 	return 0;
 }
 
-static void sfq_q_destroy(struct sfq_sched_data *q)
-{
-	del_timer(&q->perturb_timer);
-}
-
-static void sfq_destroy(struct Qdisc *sch)
-{
-	struct sfq_sched_data *q = qdisc_priv(sch);
-	sfq_q_destroy(q);
-}
-
 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
-- 
1.5.3

[PATCH 04/10] Make "depth" (number of queues) user-configurable:

[Corey Hickey]

* replace #define with a parameter
* use old hardcoded value as a default
* kcalloc() arrays in sfq_q_init()
* free() arrays in sfq_q_destroy()

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 net/sched/sch_sfq.c |   85 +++++++++++++++++++++++++++++++++++---------------
 1 files changed, 59 insertions(+), 26 deletions(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index ca22cb7..34a299d 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -74,14 +74,16 @@
 
 	It is easy to increase these values, but not in flight.  */
 
-#define SFQ_DEPTH		128
+#define SFQ_DEPTH_DEFAULT	128
 #define SFQ_HASH_DIVISOR	1024
 
 #define SFQ_HEAD 0
 #define SFQ_TAIL 1
 
-/* This type should contain at least SFQ_DEPTH*2 values */
-typedef unsigned char sfq_index;
+/* This type must contain greater than depth*2 values, so depth is constrained 
+ * accordingly. */
+typedef unsigned int sfq_index;
+#define SFQ_MAX_DEPTH (UINT_MAX / 2 - 1)
 
 struct sfq_head
 {
@@ -95,6 +97,7 @@ struct sfq_sched_data
 	int		perturb_period;
 	unsigned	quantum;	/* Allotment per round: MUST BE >= MTU */
 	int		limit;
+	unsigned	depth;
 
 /* Variables */
 	struct timer_list perturb_timer;
@@ -103,11 +106,11 @@ struct sfq_sched_data
 	sfq_index	max_depth;	/* Maximal depth */
 
 	sfq_index	ht[SFQ_HASH_DIVISOR];	/* Hash table */
-	sfq_index	next[SFQ_DEPTH];	/* Active slots link */
-	short		allot[SFQ_DEPTH];	/* Current allotment per slot */
-	unsigned short	hash[SFQ_DEPTH];	/* Hash value indexed by slots */
-	struct sk_buff_head	qs[SFQ_DEPTH];		/* Slot queue */
-	struct sfq_head	dep[SFQ_DEPTH*2];	/* Linked list of slots, indexed by depth */
+	sfq_index	*next;			/* Active slots link */
+	short		*allot;			/* Current allotment per slot */
+	unsigned short	*hash;			/* Hash value indexed by slots */
+	struct sk_buff_head	*qs;		/* Slot queue */
+	struct sfq_head	*dep;			/* Linked list of slots, indexed by depth */
 };
 
 static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
@@ -164,7 +167,7 @@ static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
 {
 	sfq_index p, n;
-	int d = q->qs[x].qlen + SFQ_DEPTH;
+	int d = q->qs[x].qlen + q->depth;
 
 	p = d;
 	n = q->dep[d].next;
@@ -215,7 +218,7 @@ static unsigned int sfq_drop(struct Qdisc *sch)
 	   drop a packet from it */
 
 	if (d > 1) {
-		sfq_index x = q->dep[d+SFQ_DEPTH].next;
+		sfq_index x = q->dep[d + q->depth].next;
 		skb = q->qs[x].prev;
 		len = skb->len;
 		__skb_unlink(skb, &q->qs[x]);
@@ -238,7 +241,7 @@ static unsigned int sfq_drop(struct Qdisc *sch)
 		kfree_skb(skb);
 		sfq_dec(q, d);
 		sch->q.qlen--;
-		q->ht[q->hash[d]] = SFQ_DEPTH;
+		q->ht[q->hash[d]] = q->depth;
 		sch->qstats.drops++;
 		sch->qstats.backlog -= len;
 		return len;
@@ -254,8 +257,8 @@ sfq_q_enqueue(struct sk_buff *skb, struct sfq_sched_data *q, unsigned int end)
 	sfq_index x;
 
 	x = q->ht[hash];
-	if (x == SFQ_DEPTH) {
-		q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
+	if (x == q->depth) {
+		q->ht[hash] = x = q->dep[q->depth].next;
 		q->hash[x] = hash;
 	}
 
@@ -266,7 +269,7 @@ sfq_q_enqueue(struct sk_buff *skb, struct sfq_sched_data *q, unsigned int end)
 
 	sfq_inc(q, x);
 	if (q->qs[x].qlen == 1) {		/* The flow is new */
-		if (q->tail == SFQ_DEPTH) {	/* It is the first flow */
+		if (q->tail == q->depth) {	/* It is the first flow */
 			q->tail = x;
 			q->next[x] = x;
 			q->allot[x] = q->quantum;
@@ -318,7 +321,7 @@ sk_buff *sfq_q_dequeue(struct sfq_sched_data *q)
 	sfq_index a, old_a;
 
 	/* No active slots */
-	if (q->tail == SFQ_DEPTH)
+	if (q->tail == q->depth)
 		return NULL;
 
 	a = old_a = q->next[q->tail];
@@ -329,10 +332,10 @@ sk_buff *sfq_q_dequeue(struct sfq_sched_data *q)
 
 	/* Is the slot empty? */
 	if (q->qs[a].qlen == 0) {
-		q->ht[q->hash[a]] = SFQ_DEPTH;
+		q->ht[q->hash[a]] = q->depth;
 		a = q->next[a];
 		if (a == old_a) {
-			q->tail = SFQ_DEPTH;
+			q->tail = q->depth;
 			return skb;
 		}
 		q->next[q->tail] = a;
@@ -385,6 +388,11 @@ static void sfq_perturbation(unsigned long arg)
 static void sfq_q_destroy(struct sfq_sched_data *q)
 {
 	del_timer(&q->perturb_timer);
+	kfree(q->dep);
+	kfree(q->next);
+	kfree(q->allot);
+	kfree(q->hash);
+	kfree(q->qs);
 }
 
 static void sfq_destroy(struct Qdisc *sch)
@@ -401,7 +409,8 @@ sfq_default_parameters(struct Qdisc *sch)
 	q->quantum        = psched_mtu(sch->dev);
 	q->perturbation   = 0;
 	q->perturb_period = 0;
-	q->limit          = SFQ_DEPTH - 2;
+	q->depth          = SFQ_DEPTH_DEFAULT;
+	q->limit          = SFQ_DEPTH_DEFAULT - 2;
 }
 
 static int
@@ -422,24 +431,48 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 			q->quantum = ctl->quantum;
 		if (ctl->perturb_period)
 			q->perturb_period = ctl->perturb_period * HZ;
+		if (ctl->flows)
+			q->depth = ctl->flows;
 		if (ctl->limit)
 			q->limit = ctl->limit;
+
+		if (q->depth > SFQ_MAX_DEPTH)
+			return -EINVAL;
 	}
-	q->limit = min_t(u32, q->limit, SFQ_DEPTH - 2);
-	q->tail = SFQ_DEPTH;
+	q->limit = min_t(u32, q->limit, q->depth - 2);
+	q->tail = q->depth;
 	q->max_depth = 0;
 
+	q->dep = kcalloc(1 + q->depth*2, sizeof(struct sfq_head), GFP_KERNEL);
+	if (!q->dep)
+		goto err_case;
+	q->next = kcalloc(q->depth, sizeof(sfq_index), GFP_KERNEL);
+	if (!q->next)
+		goto err_case;
+	q->allot = kcalloc(q->depth, sizeof(short), GFP_KERNEL);
+	if (!q->allot)
+		goto err_case;
+	q->hash = kcalloc(q->depth, sizeof(unsigned short), GFP_KERNEL);
+	if (!q->hash)
+		goto err_case;
+	q->qs = kcalloc(q->depth, sizeof(struct sk_buff_head), GFP_KERNEL);
+	if (!q->qs)
+		goto err_case;
+
 	for (i=0; i<SFQ_HASH_DIVISOR; i++)
-		q->ht[i] = SFQ_DEPTH;
-	for (i=0; i<SFQ_DEPTH; i++) {
+		q->ht[i] = q->depth;
+	for (i=0; i < q->depth; i++) {
 		skb_queue_head_init(&q->qs[i]);
-		q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
-		q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
+		q->dep[i + q->depth].next = i + q->depth;
+		q->dep[i + q->depth].prev = i + q->depth;
 	}
 
-	for (i=0; i<SFQ_DEPTH; i++)
+	for (i=0; i < q->depth; i++)
 		sfq_link(q, i);
 	return 0;
+err_case:
+	sfq_q_destroy(q);
+	return -ENOBUFS;
 }
 
 static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
@@ -473,7 +506,7 @@ static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 
 	opt.limit = q->limit;
 	opt.divisor = SFQ_HASH_DIVISOR;
-	opt.flows = q->limit;
+	opt.flows = q->depth;
 
 	RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 
-- 
1.5.3

[PATCH 05/10] Add divisor.

[Corey Hickey]

Make hash divisor user-configurable.

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 net/sched/sch_sfq.c |   18 +++++++++++++-----
 1 files changed, 13 insertions(+), 5 deletions(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 34a299d..d72ea7c 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -75,7 +75,7 @@
 	It is easy to increase these values, but not in flight.  */
 
 #define SFQ_DEPTH_DEFAULT	128
-#define SFQ_HASH_DIVISOR	1024
+#define SFQ_DIVISOR_DEFAULT	1024
 
 #define SFQ_HEAD 0
 #define SFQ_TAIL 1
@@ -98,6 +98,7 @@ struct sfq_sched_data
 	unsigned	quantum;	/* Allotment per round: MUST BE >= MTU */
 	int		limit;
 	unsigned	depth;
+	unsigned	hash_divisor;
 
 /* Variables */
 	struct timer_list perturb_timer;
@@ -105,7 +106,7 @@ struct sfq_sched_data
 	sfq_index	tail;		/* Index of current slot in round */
 	sfq_index	max_depth;	/* Maximal depth */
 
-	sfq_index	ht[SFQ_HASH_DIVISOR];	/* Hash table */
+	sfq_index	*ht;			/* Hash table */
 	sfq_index	*next;			/* Active slots link */
 	short		*allot;			/* Current allotment per slot */
 	unsigned short	*hash;			/* Hash value indexed by slots */
@@ -120,7 +121,7 @@ static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1
 	/* Have we any rotation primitives? If not, WHY? */
 	h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
 	h ^= h>>10;
-	return h & 0x3FF;
+	return h & (q->hash_divisor-1);
 }
 
 static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
@@ -388,6 +389,7 @@ static void sfq_perturbation(unsigned long arg)
 static void sfq_q_destroy(struct sfq_sched_data *q)
 {
 	del_timer(&q->perturb_timer);
+	kfree(q->ht);
 	kfree(q->dep);
 	kfree(q->next);
 	kfree(q->allot);
@@ -409,6 +411,7 @@ sfq_default_parameters(struct Qdisc *sch)
 	q->quantum        = psched_mtu(sch->dev);
 	q->perturbation   = 0;
 	q->perturb_period = 0;
+	q->hash_divisor   = SFQ_DIVISOR_DEFAULT;
 	q->depth          = SFQ_DEPTH_DEFAULT;
 	q->limit          = SFQ_DEPTH_DEFAULT - 2;
 }
@@ -431,6 +434,8 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 			q->quantum = ctl->quantum;
 		if (ctl->perturb_period)
 			q->perturb_period = ctl->perturb_period * HZ;
+		if (ctl->divisor)
+			q->hash_divisor = ctl->divisor;
 		if (ctl->flows)
 			q->depth = ctl->flows;
 		if (ctl->limit)
@@ -443,6 +448,9 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 	q->tail = q->depth;
 	q->max_depth = 0;
 
+	q->ht = kcalloc(q->hash_divisor, sizeof(sfq_index), GFP_KERNEL);
+	if (!q->ht)
+		goto err_case;
 	q->dep = kcalloc(1 + q->depth*2, sizeof(struct sfq_head), GFP_KERNEL);
 	if (!q->dep)
 		goto err_case;
@@ -459,7 +467,7 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 	if (!q->qs)
 		goto err_case;
 
-	for (i=0; i<SFQ_HASH_DIVISOR; i++)
+	for (i=0; i<q->hash_divisor; i++)
 		q->ht[i] = q->depth;
 	for (i=0; i < q->depth; i++) {
 		skb_queue_head_init(&q->qs[i]);
@@ -505,7 +513,7 @@ static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 	opt.perturb_period = q->perturb_period/HZ;
 
 	opt.limit = q->limit;
-	opt.divisor = SFQ_HASH_DIVISOR;
+	opt.divisor = q->hash_divisor;
 	opt.flows = q->depth;
 
 	RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
-- 
1.5.3

[PATCH 06/10] Make qdisc changeable.

[Corey Hickey]

Re-implement sfq_change() and enable Qdisc_opts.change so "tc qdisc
change" will work.

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 net/sched/sch_sfq.c |   61 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 60 insertions(+), 1 deletions(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index d72ea7c..b8e8fa5 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -416,6 +416,17 @@ sfq_default_parameters(struct Qdisc *sch)
 	q->limit          = SFQ_DEPTH_DEFAULT - 2;
 }
 
+static void
+sfq_copy_parameters(struct sfq_sched_data *dst, struct sfq_sched_data *src)
+{
+	dst->quantum        = src->quantum;
+	dst->perturbation   = src->perturbation;
+	dst->perturb_period = src->perturb_period;
+	dst->hash_divisor   = src->hash_divisor;
+	dst->limit          = src->limit;
+	dst->depth          = src->depth;
+}
+
 static int
 sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 {
@@ -503,6 +514,54 @@ static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 	return 0;
 }
 
+static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
+{
+	struct sfq_sched_data *q = qdisc_priv(sch);
+	struct sfq_sched_data tmp;
+	struct sk_buff *skb;
+	unsigned int qlen;
+	int err;
+	
+	/* set up tmp queue */
+	memset(&tmp, 0, sizeof(struct sfq_sched_data));
+	sfq_copy_parameters(&tmp, q);
+	if ((err = sfq_q_init(&tmp, opt)))
+		return err;
+
+	/* copy packets from the old queue to the tmp queue */
+	sch_tree_lock(sch);
+	qlen = sch->q.qlen;
+	while (sch->q.qlen >= tmp.limit - 1)
+		sfq_drop(sch);
+	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
+	while ((skb = sfq_q_dequeue(q)) != NULL)
+		sfq_q_enqueue(skb, &tmp, SFQ_TAIL);
+	
+	/* clean up the old queue */
+	sfq_q_destroy(q);
+
+	/* copy elements of the tmp queue into the old queue */
+	sfq_copy_parameters(q, &tmp);
+	q->tail      = tmp.tail;
+	q->max_depth = tmp.max_depth;
+	q->ht        = tmp.ht;
+	q->dep       = tmp.dep;
+	q->next      = tmp.next;
+	q->allot     = tmp.allot;
+	q->hash      = tmp.hash;
+	q->qs        = tmp.qs;
+
+	/* finish up */
+	if (q->perturb_period) {
+		q->perturb_timer.expires = jiffies + q->perturb_period;
+		add_timer(&q->perturb_timer);
+	} else {
+		q->perturbation = 0;
+	}
+	sch_tree_unlock(sch);
+	return 0;
+}
+
 static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
@@ -537,7 +596,7 @@ static struct Qdisc_ops sfq_qdisc_ops = {
 	.init		=	sfq_init,
 	.reset		=	sfq_reset,
 	.destroy	=	sfq_destroy,
-	.change		=	NULL,
+	.change		=	sfq_change,
 	.dump		=	sfq_dump,
 	.owner		=	THIS_MODULE,
 };
-- 
1.5.3

[PATCH 07/10] Remove comments about hardcoded values.

[Corey Hickey]

None of these are true anymore (hooray!).

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 include/linux/pkt_sched.h |    8 --------
 net/sched/sch_sfq.c       |   17 +++--------------
 2 files changed, 3 insertions(+), 22 deletions(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index 268c515..58a0ea6 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -148,14 +148,6 @@ struct tc_sfq_qopt
 	unsigned	flows;		/* Maximal number of flows  */
 };
 
-/*
- *  NOTE: limit, divisor and flows are hardwired to code at the moment.
- *
- *	limit=flows=128, divisor=1024;
- *
- *	The only reason for this is efficiency, it is possible
- *	to change these parameters in compile time.
- */
 
 /* RED section */
 
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index b8e8fa5..341a9a1 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -61,18 +61,7 @@
 
 	We still need true WFQ for top level CSZ, but using WFQ
 	for the best effort traffic is absolutely pointless:
-	SFQ is superior for this purpose.
-
-	IMPLEMENTATION:
-	This implementation limits maximal queue length to 128;
-	maximal mtu to 2^15-1; number of hash buckets to 1024.
-	The only goal of this restrictions was that all data
-	fit into one 4K page :-). Struct sfq_sched_data is
-	organized in anti-cache manner: all the data for a bucket
-	are scattered over different locations. This is not good,
-	but it allowed me to put it into 4K.
-
-	It is easy to increase these values, but not in flight.  */
+	SFQ is superior for this purpose. */
 
 #define SFQ_DEPTH_DEFAULT	128
 #define SFQ_DIVISOR_DEFAULT	1024
@@ -521,7 +510,7 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 	struct sk_buff *skb;
 	unsigned int qlen;
 	int err;
-	
+
 	/* set up tmp queue */
 	memset(&tmp, 0, sizeof(struct sfq_sched_data));
 	sfq_copy_parameters(&tmp, q);
@@ -536,7 +525,7 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 	qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
 	while ((skb = sfq_q_dequeue(q)) != NULL)
 		sfq_q_enqueue(skb, &tmp, SFQ_TAIL);
-	
+
 	/* clean up the old queue */
 	sfq_q_destroy(q);
 
-- 
1.5.3

[PATCH 08/10] Multiply perturb_period by HZ when used rather than when assigned.

[Corey Hickey]

perturb_period is the only parameter that doesn't match 1:1 with the
value from userspace. This change makes it easy and clean to use a
small macro for setting parameters (in a subsequent patch).

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 net/sched/sch_sfq.c |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 341a9a1..2d3cc38 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -370,7 +370,7 @@ static void sfq_perturbation(unsigned long arg)
 	q->perturbation = net_random()&0x1F;
 
 	if (q->perturb_period) {
-		q->perturb_timer.expires = jiffies + q->perturb_period;
+		q->perturb_timer.expires = jiffies + q->perturb_period * HZ;
 		add_timer(&q->perturb_timer);
 	}
 }
@@ -433,7 +433,7 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 		if (ctl->quantum)
 			q->quantum = ctl->quantum;
 		if (ctl->perturb_period)
-			q->perturb_period = ctl->perturb_period * HZ;
+			q->perturb_period = ctl->perturb_period;
 		if (ctl->divisor)
 			q->hash_divisor = ctl->divisor;
 		if (ctl->flows)
@@ -496,7 +496,7 @@ static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
 	q->perturb_timer.data = (unsigned long)sch;
 	q->perturb_timer.function = sfq_perturbation;
 	if (q->perturb_period) {
-		q->perturb_timer.expires = jiffies + q->perturb_period;
+		q->perturb_timer.expires = jiffies + q->perturb_period * HZ;
 		add_timer(&q->perturb_timer);
 	}
 
@@ -542,7 +542,7 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
 
 	/* finish up */
 	if (q->perturb_period) {
-		q->perturb_timer.expires = jiffies + q->perturb_period;
+		q->perturb_timer.expires = jiffies + q->perturb_period * HZ;
 		add_timer(&q->perturb_timer);
 	} else {
 		q->perturbation = 0;
@@ -558,7 +558,7 @@ static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 	struct tc_sfq_qopt opt;
 
 	opt.quantum = q->quantum;
-	opt.perturb_period = q->perturb_period/HZ;
+	opt.perturb_period = q->perturb_period;
 
 	opt.limit = q->limit;
 	opt.divisor = q->hash_divisor;
-- 
1.5.3

[PATCH 09/10] Change perturb_period to unsigned.

[Corey Hickey]

perturb_period is currently a signed integer, but I can't see any good
reason why this is so--a negative perturbation period will add a timer
that expires in the past, causing constant perturbation, which makes
hashing useless.

	if (q->perturb_period) {
		q->perturb_timer.expires = jiffies + q->perturb_period;
		add_timer(&q->perturb_timer);
	}

Strictly speaking, this will break binary compatibility with older
versions of tc, but that ought not to be a problem because (a) there's
no valid use for a negative perturb_period, and (b) negative values
will be seen as high values (> INT_MAX), which don't work anyway.

If perturb_period is too large, (perturb_period * HZ) will overflow the
size of an unsigned int and wrap around. So, check for thet and reject
values that are too high.

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 include/linux/pkt_sched.h |    2 +-
 net/sched/sch_sfq.c       |    8 ++++++--
 2 files changed, 7 insertions(+), 3 deletions(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index 58a0ea6..8559974 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -142,7 +142,7 @@ enum
 struct tc_sfq_qopt
 {
 	unsigned	quantum;	/* Bytes per round allocated to flow */
-	int		perturb_period;	/* Period of hash perturbation */
+	unsigned	perturb_period;	/* Period of hash perturbation */
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 2d3cc38..170fd37 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -74,6 +74,9 @@
 typedef unsigned int sfq_index;
 #define SFQ_MAX_DEPTH (UINT_MAX / 2 - 1)
 
+/* We don't want perturb_period * HZ to overflow an unsigned int. */
+#define SFQ_MAX_PERTURB (UINT_MAX / HZ)
+
 struct sfq_head
 {
 	sfq_index	next;
@@ -83,7 +86,7 @@ struct sfq_head
 struct sfq_sched_data
 {
 /* Parameters */
-	int		perturb_period;
+	unsigned	perturb_period;
 	unsigned	quantum;	/* Allotment per round: MUST BE >= MTU */
 	int		limit;
 	unsigned	depth;
@@ -441,7 +444,8 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 		if (ctl->limit)
 			q->limit = ctl->limit;
 
-		if (q->depth > SFQ_MAX_DEPTH)
+		if (q->perturb_period > SFQ_MAX_PERTURB ||
+		    q->depth > SFQ_MAX_DEPTH)
 			return -EINVAL;
 	}
 	q->limit = min_t(u32, q->limit, q->depth - 2);
-- 
1.5.3

[PATCH 10/10] Use nested compat attributes to pass parameters.

[Corey Hickey]

This fixes the ambiguity between, for example:
tc qdisc change ... perturb 0
tc qdisc change ...

Without this patch, there is no way for SFQ to differentiate between
a parameter specified to be 0 and a parameter that was omitted.

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 include/linux/pkt_sched.h |   13 +++++++++++
 net/sched/sch_sfq.c       |   53 +++++++++++++++++++++++++++++---------------
 2 files changed, 48 insertions(+), 18 deletions(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index 8559974..aad04eb 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -148,6 +148,19 @@ struct tc_sfq_qopt
 	unsigned	flows;		/* Maximal number of flows  */
 };
 
+enum
+{
+	TCA_SFQ_UNSPEC,
+	TCA_SFQ_COMPAT,
+	TCA_SFQ_QUANTUM,
+	TCA_SFQ_PERTURB,
+	TCA_SFQ_LIMIT,
+	TCA_SFQ_DIVISOR,
+	TCA_SFQ_FLOWS,
+	__TCA_SFQ_MAX,
+};
+
+#define TCA_SFQ_MAX (__TCA_SFQ_MAX - 1)
 
 /* RED section */
 
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 170fd37..36197f6 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -428,25 +428,31 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 	 * the previous values (sfq_change). So, overwrite the parameters as
 	 * specified. */
 	if (opt) {
-		struct tc_sfq_qopt *ctl = RTA_DATA(opt);
-
-		if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
-			return -EINVAL;
-
-		if (ctl->quantum)
-			q->quantum = ctl->quantum;
-		if (ctl->perturb_period)
-			q->perturb_period = ctl->perturb_period;
-		if (ctl->divisor)
-			q->hash_divisor = ctl->divisor;
-		if (ctl->flows)
-			q->depth = ctl->flows;
-		if (ctl->limit)
-			q->limit = ctl->limit;
-
+		struct tc_sfq_qopt *ctl;
+		struct rtattr *tb[TCA_SFQ_MAX];
+
+		if (rtattr_parse_nested_compat(tb, TCA_SFQ_MAX, opt, ctl,
+				       sizeof(*ctl)))
+			goto rtattr_failure;
+
+#define GET_PARAM(dst, nest, compat) do { \
+	struct rtattr *rta = tb[(nest) - 1]; \
+	if (rta) \
+		(dst) = RTA_GET_U32(rta); \
+	else if ((compat)) \
+		(dst) = (compat); \
+} while (0)
+
+		GET_PARAM(q->quantum,        TCA_SFQ_QUANTUM, ctl->quantum);
+		GET_PARAM(q->perturb_period, TCA_SFQ_PERTURB,
+				ctl->perturb_period);
+		GET_PARAM(q->hash_divisor,   TCA_SFQ_DIVISOR, ctl->divisor);
+		GET_PARAM(q->depth,          TCA_SFQ_FLOWS,   ctl->flows);
+		GET_PARAM(q->limit,          TCA_SFQ_LIMIT,   ctl->limit);
+		
 		if (q->perturb_period > SFQ_MAX_PERTURB ||
 		    q->depth > SFQ_MAX_DEPTH)
-			return -EINVAL;
+			goto rtattr_failure;
 	}
 	q->limit = min_t(u32, q->limit, q->depth - 2);
 	q->tail = q->depth;
@@ -482,6 +488,8 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
 	for (i=0; i < q->depth; i++)
 		sfq_link(q, i);
 	return 0;
+rtattr_failure:
+	return -EINVAL;
 err_case:
 	sfq_q_destroy(q);
 	return -ENOBUFS;
@@ -559,17 +567,26 @@ static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
 	unsigned char *b = skb_tail_pointer(skb);
+	struct rtattr *nest;
 	struct tc_sfq_qopt opt;
 
 	opt.quantum = q->quantum;
 	opt.perturb_period = q->perturb_period;
-
 	opt.limit = q->limit;
 	opt.divisor = q->hash_divisor;
 	opt.flows = q->depth;
 
+	nest = RTA_NEST_COMPAT(skb, TCA_OPTIONS, sizeof(opt), &opt);
+
+	RTA_PUT_U32(skb, TCA_SFQ_QUANTUM, q->quantum);
+	RTA_PUT_U32(skb, TCA_SFQ_PERTURB, q->perturb_period);
+	RTA_PUT_U32(skb, TCA_SFQ_LIMIT,   q->limit);
+	RTA_PUT_U32(skb, TCA_SFQ_DIVISOR, q->hash_divisor);
+	RTA_PUT_U32(skb, TCA_SFQ_FLOWS,   q->depth);
 	RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
 
+	RTA_NEST_COMPAT_END(skb, nest);
+
 	return skb->len;
 
 rtattr_failure:
-- 
1.5.3

sfq

[Corey Hickey]

These patches follow the ESFQ-->SFQ kernel patches. See the kernel
patch summary for general information.

Thanks,
Corey



 include/linux/pkt_sched.h |   23 ++++++++++++++---------
 tc/q_sfq.c                |   43 ++++++++++++++++++++++++++++++++++++++-----
 2 files changed, 52 insertions(+), 14 deletions(-)


[PATCH 1/3] SFQ: Support changing depth and divisor.
[PATCH 2/3] Change perturb_period to unsigned.
[PATCH 3/3] Use nested compat attributes for passing parameters to the kernel.

[PATCH 1/3] SFQ: Support changing depth and divisor.

[Corey Hickey]

This can safely be applied either before or after the kernel
patches because the tc_sfq_qopt struct is unchanged:

- old kernels will ignore the parameters from new iproute2
- new kernels will use the same default parameters

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 include/linux/pkt_sched.h |    9 ---------
 tc/q_sfq.c                |   21 ++++++++++++++++++++-
 2 files changed, 20 insertions(+), 10 deletions(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index 268c515..9d41f63 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -148,15 +148,6 @@ struct tc_sfq_qopt
 	unsigned	flows;		/* Maximal number of flows  */
 };
 
-/*
- *  NOTE: limit, divisor and flows are hardwired to code at the moment.
- *
- *	limit=flows=128, divisor=1024;
- *
- *	The only reason for this is efficiency, it is possible
- *	to change these parameters in compile time.
- */
-
 /* RED section */
 
 enum
diff --git a/tc/q_sfq.c b/tc/q_sfq.c
index 05385cf..7754db7 100644
--- a/tc/q_sfq.c
+++ b/tc/q_sfq.c
@@ -25,7 +25,7 @@
 
 static void explain(void)
 {
-	fprintf(stderr, "Usage: ... sfq [ limit NUMBER ] [ perturb SECS ] [ quantum BYTES ]\n");
+	fprintf(stderr, "Usage: ... sfq [ limit NUMBER ] [ depth FLOWS ] [ divisor HASHBITS ] [ perturb SECS ] [ quantum BYTES ]\n");
 }
 
 #define usage() return(-1)
@@ -63,6 +63,25 @@ static int sfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nl
 				return -1;
 			}
 			ok++;
+		} else if (strcmp(*argv, "depth") == 0) {
+			NEXT_ARG();
+			if (get_unsigned(&opt.flows, *argv, 0)) {
+				fprintf(stderr, "Illegal \"depth\"\n");
+				return -1;
+			}
+			ok++;
+		} else if (strcmp(*argv, "divisor") == 0) {
+			NEXT_ARG();
+			if (get_unsigned(&opt.divisor, *argv, 0)) {
+				fprintf(stderr, "Illegal \"divisor\"\n");
+				return -1;
+			}
+			if (opt.divisor >= 15) {
+				fprintf(stderr, "Illegal \"divisor\", must be < 15\n");
+				return -1;
+			}
+			opt.divisor = 1<<opt.divisor;
+			ok++;
 		} else if (strcmp(*argv, "help") == 0) {
 			explain();
 			return -1;
-- 
1.5.3

[PATCH 2/3] Change perturb_period to unsigned.

[Corey Hickey]

This corresponds to the kernel patch doing the same.

Here, too, this will technically break binary compatibility with older
kernels, but that shouldn't be a problem because negative perturb_period
values aren't usable anyway.

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 include/linux/pkt_sched.h |    2 +-
 tc/q_sfq.c                |    4 ++--
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index 9d41f63..fb04a89 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -142,7 +142,7 @@ enum
 struct tc_sfq_qopt
 {
 	unsigned	quantum;	/* Bytes per round allocated to flow */
-	int		perturb_period;	/* Period of hash perturbation */
+	unsigned	perturb_period;	/* Period of hash perturbation */
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
diff --git a/tc/q_sfq.c b/tc/q_sfq.c
index 7754db7..c9fcc53 100644
--- a/tc/q_sfq.c
+++ b/tc/q_sfq.c
@@ -47,7 +47,7 @@ static int sfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nl
 			ok++;
 		} else if (strcmp(*argv, "perturb") == 0) {
 			NEXT_ARG();
-			if (get_integer(&opt.perturb_period, *argv, 0)) {
+			if (get_u32(&opt.perturb_period, *argv, 0)) {
 				fprintf(stderr, "Illegal \"perturb\"\n");
 				return -1;
 			}
@@ -115,7 +115,7 @@ static int sfq_print_opt(struct qdisc_util *qu, FILE *f, struct rtattr *opt)
 		fprintf(f, "flows %u/%u ", qopt->flows, qopt->divisor);
 	}
 	if (qopt->perturb_period)
-		fprintf(f, "perturb %dsec ", qopt->perturb_period);
+		fprintf(f, "perturb %usec ", qopt->perturb_period);
 	return 0;
 }
 
-- 
1.5.3

[PATCH 3/3] Use nested compat attributes for passing parameters to the kernel.

[Corey Hickey]

Note that I have left sfq_print_opt() alone. At this point, there
can be no difference between the data in the nested rtattrs and the
data in the compat rtattr, and I didn't want to add clutter that
isn't useful. Let me know if I should do differently.

Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
---
 include/linux/pkt_sched.h |   14 ++++++++++++++
 tc/q_sfq.c                |   18 ++++++++++++++++--
 2 files changed, 30 insertions(+), 2 deletions(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index fb04a89..aad04eb 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -148,6 +148,20 @@ struct tc_sfq_qopt
 	unsigned	flows;		/* Maximal number of flows  */
 };
 
+enum
+{
+	TCA_SFQ_UNSPEC,
+	TCA_SFQ_COMPAT,
+	TCA_SFQ_QUANTUM,
+	TCA_SFQ_PERTURB,
+	TCA_SFQ_LIMIT,
+	TCA_SFQ_DIVISOR,
+	TCA_SFQ_FLOWS,
+	__TCA_SFQ_MAX,
+};
+
+#define TCA_SFQ_MAX (__TCA_SFQ_MAX - 1)
+
 /* RED section */
 
 enum
diff --git a/tc/q_sfq.c b/tc/q_sfq.c
index c9fcc53..5bb3eb7 100644
--- a/tc/q_sfq.c
+++ b/tc/q_sfq.c
@@ -34,9 +34,13 @@ static int sfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nl
 {
 	int ok=0;
 	struct tc_sfq_qopt opt;
+	struct rtattr *nest;
 
 	memset(&opt, 0, sizeof(opt));
 
+	/* put blank data in rtattr so there is a "hole" to fill later */
+	nest = addattr_nest_compat(n, 1024, TCA_OPTIONS, &opt, sizeof(opt));
+
 	while (argc > 0) {
 		if (strcmp(*argv, "quantum") == 0) {
 			NEXT_ARG();
@@ -44,6 +48,7 @@ static int sfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nl
 				fprintf(stderr, "Illegal \"limit\"\n");
 				return -1;
 			}
+			addattr32(n, 1024, TCA_SFQ_QUANTUM, opt.quantum);
 			ok++;
 		} else if (strcmp(*argv, "perturb") == 0) {
 			NEXT_ARG();
@@ -51,6 +56,7 @@ static int sfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nl
 				fprintf(stderr, "Illegal \"perturb\"\n");
 				return -1;
 			}
+			addattr32(n, 1024, TCA_SFQ_PERTURB, opt.perturb_period);
 			ok++;
 		} else if (strcmp(*argv, "limit") == 0) {
 			NEXT_ARG();
@@ -62,6 +68,7 @@ static int sfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nl
 				fprintf(stderr, "Illegal \"limit\", must be > 1\n");
 				return -1;
 			}
+			addattr32(n, 1024, TCA_SFQ_LIMIT, opt.limit);
 			ok++;
 		} else if (strcmp(*argv, "depth") == 0) {
 			NEXT_ARG();
@@ -69,6 +76,7 @@ static int sfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nl
 				fprintf(stderr, "Illegal \"depth\"\n");
 				return -1;
 			}
+			addattr32(n, 1024, TCA_SFQ_FLOWS, opt.flows);
 			ok++;
 		} else if (strcmp(*argv, "divisor") == 0) {
 			NEXT_ARG();
@@ -81,6 +89,7 @@ static int sfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nl
 				return -1;
 			}
 			opt.divisor = 1<<opt.divisor;
+			addattr32(n, 1024, TCA_SFQ_DIVISOR, opt.divisor);
 			ok++;
 		} else if (strcmp(*argv, "help") == 0) {
 			explain();
@@ -93,8 +102,13 @@ static int sfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nl
 		argc--; argv++;
 	}
 
-	if (ok)
-		addattr_l(n, 1024, TCA_OPTIONS, &opt, sizeof(opt));
+	if (ok) {
+		/* fill the "hole" we left earlier with real compat data */
+		memcpy(RTA_DATA(nest), &opt, sizeof(opt));
+		addattr_nest_compat_end(n, nest);
+	}
+	else
+		nest->rta_len = 0;
 	return 0;
 }
 
-- 
1.5.3

Re: sfq (iproute2 patches)

[Corey Hickey]

Corey Hickey wrote:
> These patches follow the ESFQ-->SFQ kernel patches. See the kernel
> patch summary for general information.

Dang, I forgot to set the subject; these are the iproute2 patches.

-Corey

Re: SFQ: backport some features from ESFQ (try 4)

[Patrick McHardy]

Corey Hickey wrote:
> Patchset try 2 addresses the review by Michael Buesch.
> Patchset try 3 addresses the review by Patrick McHardy.
> Patchset try 4 has a few cosmetic improvements.
> 
> Nobody reviewed my last set of patches, and I wasn't pushy about asking.
> Since it's been a while, I ported the kernel and userspace patchsets to
> current git of net-2.6 and iproute2, respectively.


Thanks for posting these patches, I'll have a closer look tommorrow.

Re: SFQ: backport some features from ESFQ (try 4)

[Corey Hickey]

Patrick McHardy wrote:
> Corey Hickey wrote:
>> Patchset try 2 addresses the review by Michael Buesch.
>> Patchset try 3 addresses the review by Patrick McHardy.
>> Patchset try 4 has a few cosmetic improvements.
>>
>> Nobody reviewed my last set of patches, and I wasn't pushy about asking.
>> Since it's been a while, I ported the kernel and userspace patchsets to
>> current git of net-2.6 and iproute2, respectively.
> 
> Thanks for posting these patches, I'll have a closer look tommorrow.

Many thanks for reviewing.

-Corey

Re: [PATCH 01/10] Preparatory refactoring part 1.

[Patrick McHardy]

Corey Hickey wrote:
> Make a new function sfq_q_enqueue() that operates directly on the
> queue data. This will be useful for implementing sfq_change() in
> a later patch. A pleasant side-effect is reducing most of the
> duplicate code in sfq_enqueue() and sfq_requeue().
> 
> Similarly, make a new function sfq_q_dequeue().
> 
> Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
> ---
>  net/sched/sch_sfq.c |   72 +++++++++++++++++++++++++++------------------------
>  1 files changed, 38 insertions(+), 34 deletions(-)
> 
> diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
> index 3a23e30..57485ef 100644
> --- a/net/sched/sch_sfq.c
> +++ b/net/sched/sch_sfq.c
> 


The sfq_q_enqueue part looks fine.

>  
> -	sch->qstats.drops++;


A line in the changelog explaining that this was increased twice
would have been nice.

>  	sfq_drop(sch);
>  	return NET_XMIT_CN;
>  }
>  
> -
> -
> -
> -static struct sk_buff *
> -sfq_dequeue(struct Qdisc* sch)
> +static struct
> +sk_buff *sfq_q_dequeue(struct sfq_sched_data *q)


What is this function needed for?

Re: [PATCH 03/10] Move two functions.

[Patrick McHardy]

Corey Hickey wrote:
> Move sfq_q_destroy() to above sfq_q_init() so that it can be used
> by an error case in a later patch.
> 
> Move sfq_destroy() as well, for clarity.


This patch looks pointless, just put them where you need them
in the patch introducing them.

Re: [PATCH 02/10] Preparatory refactoring part 2.

[Patrick McHardy]

Corey Hickey wrote:
> The sfq_destroy() --> sfq_q_destroy() change looks pointless here,
> but it's cleaner to split now and add code to sfq_q_destroy() in a
> later patch.
> 
> +static void sfq_destroy(struct Qdisc *sch)
> +{
> +	struct sfq_sched_data *q = qdisc_priv(sch);
> +	sfq_q_destroy(q);
> +}


It does look pointless, after applying all patches sfq_destroy still
remains a simply wrapper around sfq_q_destroy.

Re: [PATCH 05/10] Add divisor.

[Patrick McHardy]

Corey Hickey wrote:
> Make hash divisor user-configurable.
> 

> @@ -120,7 +121,7 @@ static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1
>  	/* Have we any rotation primitives? If not, WHY? */
>  	h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
>  	h ^= h>>10;
> -	return h & 0x3FF;
> +	return h & (q->hash_divisor-1);


This assumes that hash_divisor is a power of two, but this is
not enforced anywhere.

Re: [PATCH 06/10] Make qdisc changeable.

[Patrick McHardy]

Corey Hickey wrote:
> Re-implement sfq_change() and enable Qdisc_opts.change so "tc qdisc
> change" will work.
> 

> +static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
> +{
> +	...
> +
> +	/* finish up */
> +	if (q->perturb_period) {
> +		q->perturb_timer.expires = jiffies + q->perturb_period;
> +		add_timer(&q->perturb_timer);
> +	} else {
> +		q->perturbation = 0;


Seems counter-productive to explicitly set it to zero since
it was still used during tranfering the packets with the
old value. So I'd suggest to remove this or alternatively
set it to the final value *before* transfering the packets.

Re: [PATCH 09/10] Change perturb_period to unsigned.

[Patrick McHardy]

Corey Hickey wrote:
> perturb_period is currently a signed integer, but I can't see any good
> reason why this is so--a negative perturbation period will add a timer
> that expires in the past, causing constant perturbation, which makes
> hashing useless.
> 
> 	if (q->perturb_period) {
> 		q->perturb_timer.expires = jiffies + q->perturb_period;
> 		add_timer(&q->perturb_timer);
> 	}
> 
> Strictly speaking, this will break binary compatibility with older
> versions of tc, but that ought not to be a problem because (a) there's
> no valid use for a negative perturb_period, and (b) negative values
> will be seen as high values (> INT_MAX), which don't work anyway.
> 
> If perturb_period is too large, (perturb_period * HZ) will overflow the
> size of an unsigned int and wrap around. So, check for thet and reject
> values that are too high.


Sounds reasonable.

> --- a/net/sched/sch_sfq.c
> +++ b/net/sched/sch_sfq.c
> @@ -74,6 +74,9 @@
>  typedef unsigned int sfq_index;
>  #define SFQ_MAX_DEPTH (UINT_MAX / 2 - 1)
>  
> +/* We don't want perturb_period * HZ to overflow an unsigned int. */
> +#define SFQ_MAX_PERTURB (UINT_MAX / HZ)


jiffies are unsigned long.

Re: [PATCH 10/10] Use nested compat attributes to pass parameters.

[Patrick McHardy]

Corey Hickey wrote:
> This fixes the ambiguity between, for example:
> tc qdisc change ... perturb 0
> tc qdisc change ...
> 
> Without this patch, there is no way for SFQ to differentiate between
> a parameter specified to be 0 and a parameter that was omitted.
> 

> diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
> index 170fd37..36197f6 100644
> --- a/net/sched/sch_sfq.c
> +++ b/net/sched/sch_sfq.c
> @@ -428,25 +428,31 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
>  	 * the previous values (sfq_change). So, overwrite the parameters as
>  	 * specified. */
>  	if (opt) {
> -		struct tc_sfq_qopt *ctl = RTA_DATA(opt);
> -
> -		if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
> -			return -EINVAL;
> -
> -		if (ctl->quantum)
> -			q->quantum = ctl->quantum;
> -		if (ctl->perturb_period)
> -			q->perturb_period = ctl->perturb_period;
> -		if (ctl->divisor)
> -			q->hash_divisor = ctl->divisor;
> -		if (ctl->flows)
> -			q->depth = ctl->flows;
> -		if (ctl->limit)
> -			q->limit = ctl->limit;
> -
> +		struct tc_sfq_qopt *ctl;
> +		struct rtattr *tb[TCA_SFQ_MAX];
> +
> +		if (rtattr_parse_nested_compat(tb, TCA_SFQ_MAX, opt, ctl,
> +				       sizeof(*ctl)))
> +			goto rtattr_failure;
> +
> +#define GET_PARAM(dst, nest, compat) do { \
> +	struct rtattr *rta = tb[(nest) - 1]; \
> +	if (rta) \
> +		(dst) = RTA_GET_U32(rta); \
> +	else if ((compat)) \
> +		(dst) = (compat); \
> +} while (0)


An inline function and a comment why this is done would increase
readability.

> +
> +		GET_PARAM(q->quantum,        TCA_SFQ_QUANTUM, ctl->quantum);
> +		GET_PARAM(q->perturb_period, TCA_SFQ_PERTURB,
> +				ctl->perturb_period);
> +		GET_PARAM(q->hash_divisor,   TCA_SFQ_DIVISOR, ctl->divisor);
> +		GET_PARAM(q->depth,          TCA_SFQ_FLOWS,   ctl->flows);
> +		GET_PARAM(q->limit,          TCA_SFQ_LIMIT,   ctl->limit);
> +		
>  		if (q->perturb_period > SFQ_MAX_PERTURB ||
>  		    q->depth > SFQ_MAX_DEPTH)
> -			return -EINVAL;
> +			goto rtattr_failure;
>  	}
>  	q->limit = min_t(u32, q->limit, q->depth - 2);
>  	q->tail = q->depth;
> @@ -482,6 +488,8 @@ sfq_q_init(struct sfq_sched_data *q, struct rtattr *opt)
>  	for (i=0; i < q->depth; i++)
>  		sfq_link(q, i);
>  	return 0;
> +rtattr_failure:
> +	return -EINVAL;
>  err_case:
>  	sfq_q_destroy(q);
>  	return -ENOBUFS;
> @@ -559,17 +567,26 @@ static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
>  {
>  	struct sfq_sched_data *q = qdisc_priv(sch);
>  	unsigned char *b = skb_tail_pointer(skb);
> +	struct rtattr *nest;
>  	struct tc_sfq_qopt opt;
>  
>  	opt.quantum = q->quantum;
>  	opt.perturb_period = q->perturb_period;
> -
>  	opt.limit = q->limit;
>  	opt.divisor = q->hash_divisor;
>  	opt.flows = q->depth;
>  
> +	nest = RTA_NEST_COMPAT(skb, TCA_OPTIONS, sizeof(opt), &opt);
> +
> +	RTA_PUT_U32(skb, TCA_SFQ_QUANTUM, q->quantum);
> +	RTA_PUT_U32(skb, TCA_SFQ_PERTURB, q->perturb_period);
> +	RTA_PUT_U32(skb, TCA_SFQ_LIMIT,   q->limit);
> +	RTA_PUT_U32(skb, TCA_SFQ_DIVISOR, q->hash_divisor);
> +	RTA_PUT_U32(skb, TCA_SFQ_FLOWS,   q->depth);
>  	RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);


This is wrong, RTA_NEST_COMPAT already dumps the structure.

>  
> +	RTA_NEST_COMPAT_END(skb, nest);
> +
>  	return skb->len;
>  
>  rtattr_failure:

Re: [PATCH 01/10] Preparatory refactoring part 1.

[Corey Hickey]

Patrick McHardy wrote:
> Corey Hickey wrote:
>> Make a new function sfq_q_enqueue() that operates directly on the
>> queue data. This will be useful for implementing sfq_change() in
>> a later patch. A pleasant side-effect is reducing most of the
>> duplicate code in sfq_enqueue() and sfq_requeue().
>>
>> Similarly, make a new function sfq_q_dequeue().
>>
>> Signed-off-by: Corey Hickey <bugfood-ml@fatooh.org>
>> ---
>>  net/sched/sch_sfq.c |   72 +++++++++++++++++++++++++++------------------------
>>  1 files changed, 38 insertions(+), 34 deletions(-)
>>
>> diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
>> index 3a23e30..57485ef 100644
>> --- a/net/sched/sch_sfq.c
>> +++ b/net/sched/sch_sfq.c
>>
> 
> 
> The sfq_q_enqueue part looks fine.
> 
>>  
>> -	sch->qstats.drops++;
> 
> 
> A line in the changelog explaining that this was increased twice
> would have been nice.

Certainly; I think I didn't realize, when you originally pointed out the 
duplicate incrementing, that it was a bug in the original version and 
not in my patch. Otherwise, I would have sent it as a separate patch.

If a note in this patch will suffice, though, I'll definitely do so.

>>  	sfq_drop(sch);
>>  	return NET_XMIT_CN;
>>  }
>>  
>> -
>> -
>> -
>> -static struct sk_buff *
>> -sfq_dequeue(struct Qdisc* sch)
>> +static struct
>> +sk_buff *sfq_q_dequeue(struct sfq_sched_data *q)
> 
> 
> What is this function needed for?

It gets used in sfq_change for moving packets from the old queue into 
the new one. In this case, we don't want to modify sch->q.qlen or 
sch->qstats.backlog, since those don't actually change.

          while ((skb = sfq_q_dequeue(q)) != NULL)
                  sfq_q_enqueue(skb, &tmp, SFQ_TAIL);


I'll improve the description of this patch to make that more clear.

-Corey

Re: [PATCH 02/10] Preparatory refactoring part 2.

[Corey Hickey]

Patrick McHardy wrote:
> Corey Hickey wrote:
>> The sfq_destroy() --> sfq_q_destroy() change looks pointless here,
>> but it's cleaner to split now and add code to sfq_q_destroy() in a
>> later patch.
>>
>> +static void sfq_destroy(struct Qdisc *sch)
>> +{
>> +	struct sfq_sched_data *q = qdisc_priv(sch);
>> +	sfq_q_destroy(q);
>> +}
> 
> 
> It does look pointless, after applying all patches sfq_destroy still
> remains a simply wrapper around sfq_q_destroy.

It does remain a wrapper, but both functions are used. It doesn't have 
to be this way, but I wanted to avoid duplicating code and I didn't see 
a better layout.

sfq_q_destroy is used in sfq_q_init if a kcalloc fails. sfq_q_init knows 
nothing about "struct Qdisc *sch", so it can't call sfq_destroy.

sfq_destroy is still marked as the destroy function in sfq_qdisc_ops.

-Corey

Re: [PATCH 03/10] Move two functions.

[Corey Hickey]

Patrick McHardy wrote:
> Corey Hickey wrote:
>> Move sfq_q_destroy() to above sfq_q_init() so that it can be used
>> by an error case in a later patch.
>>
>> Move sfq_destroy() as well, for clarity.
> 
> 
> This patch looks pointless, just put them where you need them
> in the patch introducing them.

As you wish. I thought having a separate patch would ease reviewing.

-Corey

Re: [PATCH 05/10] Add divisor.

[Corey Hickey]

Patrick McHardy wrote:
> Corey Hickey wrote:
>> Make hash divisor user-configurable.
>>
> 
>> @@ -120,7 +121,7 @@ static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1
>>  	/* Have we any rotation primitives? If not, WHY? */
>>  	h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
>>  	h ^= h>>10;
>> -	return h & 0x3FF;
>> +	return h & (q->hash_divisor-1);
> 
> 
> This assumes that hash_divisor is a power of two, but this is
> not enforced anywhere.

Ok. I'll move that part from userspace to the kernel. That should be 
better anyway.

-Corey

Re: [PATCH 06/10] Make qdisc changeable.

[Corey Hickey]

Patrick McHardy wrote:
> Corey Hickey wrote:
>> Re-implement sfq_change() and enable Qdisc_opts.change so "tc qdisc
>> change" will work.
>>
> 
>> +static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
>> +{
>> +	...
>> +
>> +	/* finish up */
>> +	if (q->perturb_period) {
>> +		q->perturb_timer.expires = jiffies + q->perturb_period;
>> +		add_timer(&q->perturb_timer);
>> +	} else {
>> +		q->perturbation = 0;
> 
> 
> Seems counter-productive to explicitly set it to zero since
> it was still used during tranfering the packets with the
> old value. So I'd suggest to remove this or alternatively
> set it to the final value *before* transfering the packets.

I suppose so; you're right. I'll adapt that part to fit before 
transferring the packets.

-Corey

Re: [PATCH 09/10] Change perturb_period to unsigned.

[Corey Hickey]

Patrick McHardy wrote:
> Corey Hickey wrote:
>> perturb_period is currently a signed integer, but I can't see any good
>> reason why this is so--a negative perturbation period will add a timer
>> that expires in the past, causing constant perturbation, which makes
>> hashing useless.
>>
>> 	if (q->perturb_period) {
>> 		q->perturb_timer.expires = jiffies + q->perturb_period;
>> 		add_timer(&q->perturb_timer);
>> 	}
>>
>> Strictly speaking, this will break binary compatibility with older
>> versions of tc, but that ought not to be a problem because (a) there's
>> no valid use for a negative perturb_period, and (b) negative values
>> will be seen as high values (> INT_MAX), which don't work anyway.
>>
>> If perturb_period is too large, (perturb_period * HZ) will overflow the
>> size of an unsigned int and wrap around. So, check for thet and reject
>> values that are too high.
> 
> 
> Sounds reasonable.
> 
>> --- a/net/sched/sch_sfq.c
>> +++ b/net/sched/sch_sfq.c
>> @@ -74,6 +74,9 @@
>>  typedef unsigned int sfq_index;
>>  #define SFQ_MAX_DEPTH (UINT_MAX / 2 - 1)
>>  
>> +/* We don't want perturb_period * HZ to overflow an unsigned int. */
>> +#define SFQ_MAX_PERTURB (UINT_MAX / HZ)
> 
> 
> jiffies are unsigned long.

Hmm. You're right. It looks like my previous patch obviated the need for 
this part. I'll remove it.

-Corey

Re: [PATCH 10/10] Use nested compat attributes to pass parameters.

[Corey Hickey]

Patrick McHardy wrote:
> Corey Hickey wrote:
>> +
>> +#define GET_PARAM(dst, nest, compat) do { \
>> +	struct rtattr *rta = tb[(nest) - 1]; \
>> +	if (rta) \
>> +		(dst) = RTA_GET_U32(rta); \
>> +	else if ((compat)) \
>> +		(dst) = (compat); \
>> +} while (0)
> 
> 
> An inline function and a comment why this is done would increase
> readability.

Well, I had a reason for making a macro, but it probably wasn't a good 
reason. Looking now, I don't see why not to make a function. I'll see 
what I can do.

>> +	nest = RTA_NEST_COMPAT(skb, TCA_OPTIONS, sizeof(opt), &opt);
>> +
>> +	RTA_PUT_U32(skb, TCA_SFQ_QUANTUM, q->quantum);
>> +	RTA_PUT_U32(skb, TCA_SFQ_PERTURB, q->perturb_period);
>> +	RTA_PUT_U32(skb, TCA_SFQ_LIMIT,   q->limit);
>> +	RTA_PUT_U32(skb, TCA_SFQ_DIVISOR, q->hash_divisor);
>> +	RTA_PUT_U32(skb, TCA_SFQ_FLOWS,   q->depth);
>>  	RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
> 
> 
> This is wrong, RTA_NEST_COMPAT already dumps the structure.

You mean that last line (RTA_PUT) is superfluous, right? I can't see a 
reason for it to be there, so I must have just forgotten to delete it 
from the original code.

If I'm wrong, I might need a little hand-holding here. My understanding 
of all the RTA stuff is a bit shaky.


Much thanks for the review. I'll make a new set of patches soon.

-Corey

Re: [PATCH 01/10] Preparatory refactoring part 1.

[Patrick McHardy]

Corey Hickey wrote:
> Patrick McHardy wrote:
> 
>>> -    sch->qstats.drops++;
>>
>> A line in the changelog explaining that this was increased twice
>> would have been nice.
> 
> 
> Certainly; I think I didn't realize, when you originally pointed out the
> duplicate incrementing, that it was a bug in the original version and
> not in my patch. Otherwise, I would have sent it as a separate patch.


I didn't remember that :)

> If a note in this patch will suffice, though, I'll definitely do so.


Sure, a note in the changelog will be fine.

>>> +static struct
>>> +sk_buff *sfq_q_dequeue(struct sfq_sched_data *q)
>>
>>
>>
>> What is this function needed for?
> 
> 
> It gets used in sfq_change for moving packets from the old queue into
> the new one. In this case, we don't want to modify sch->q.qlen or
> sch->qstats.backlog, since those don't actually change.
> 
>          while ((skb = sfq_q_dequeue(q)) != NULL)
>                  sfq_q_enqueue(skb, &tmp, SFQ_TAIL);


I missed that, thanks for the explanation.

Re: [PATCH 02/10] Preparatory refactoring part 2.

[Patrick McHardy]

Corey Hickey wrote:
> Patrick McHardy wrote:
> 
>>> +static void sfq_destroy(struct Qdisc *sch)
>>> +{
>>> +    struct sfq_sched_data *q = qdisc_priv(sch);
>>> +    sfq_q_destroy(q);
>>> +}
>>
>>
>> It does look pointless, after applying all patches sfq_destroy still
>> remains a simply wrapper around sfq_q_destroy.
> 
> 
> It does remain a wrapper, but both functions are used. It doesn't have
> to be this way, but I wanted to avoid duplicating code and I didn't see
> a better layout.
> 
> sfq_q_destroy is used in sfq_q_init if a kcalloc fails. sfq_q_init knows
> nothing about "struct Qdisc *sch", so it can't call sfq_destroy.


Thats fine, I didn't realize it was used without the struct Qdisc *
context. Changing sfq_destroy to sfq_q_destroy(qdisc_priv(sch));
would be a bit nicer though.

Re: [PATCH 10/10] Use nested compat attributes to pass parameters.

[Patrick McHardy]

Corey Hickey wrote:
> Patrick McHardy wrote:
> 
>>> +    nest = RTA_NEST_COMPAT(skb, TCA_OPTIONS, sizeof(opt), &opt);
>>> +
>>> +    RTA_PUT_U32(skb, TCA_SFQ_QUANTUM, q->quantum);
>>> +    RTA_PUT_U32(skb, TCA_SFQ_PERTURB, q->perturb_period);
>>> +    RTA_PUT_U32(skb, TCA_SFQ_LIMIT,   q->limit);
>>> +    RTA_PUT_U32(skb, TCA_SFQ_DIVISOR, q->hash_divisor);
>>> +    RTA_PUT_U32(skb, TCA_SFQ_FLOWS,   q->depth);
>>>      RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
>>
>>
>>
>> This is wrong, RTA_NEST_COMPAT already dumps the structure.
> 
> 
> You mean that last line (RTA_PUT) is superfluous, right?


Exactly.

> Much thanks for the review. I'll make a new set of patches soon.


Thanks.