: External SFQ classifiers/flow classifier

These patches add support for external classifiers to SFQ and add a new "flow" classifier, which can do hashing based on user-specified keys or deterministic mapping of keys to classes. Additionally there is a patch to make the SFQ queues visisble as classes to verify that the hash is indeed doing something useful and a patch to consifiy struct tcf_ext_map, which I had queued in the same tree.

Please apply, thanks.

 include/linux/pkt_cls.h   |   50 ++++
 include/linux/pkt_sched.h |    5 +
 include/net/pkt_cls.h     |    6 +-
 net/sched/Kconfig         |   11 +
 net/sched/Makefile        |    1 +
 net/sched/cls_api.c       |    6 +-
 net/sched/cls_basic.c     |    2 +-
 net/sched/cls_flow.c      |  660 +++++++++++++++++++++++++++++++++++++++++++++
 net/sched/cls_fw.c        |    2 +-
 net/sched/cls_route.c     |    2 +-
 net/sched/cls_tcindex.c   |    2 +-
 net/sched/cls_u32.c       |    2 +-
 net/sched/sch_sfq.c       |  134 +++++++++-
 13 files changed, 868 insertions(+), 15 deletions(-)
 create mode 100644 net/sched/cls_flow.c

Patrick McHardy (4):
[NET_SCHED]: Constify struct tcf_ext_map [NET_SCHED]: sch_sfq: add support for external classifiers [NET_SCHED]: sch_sfq: make internal queues visible as classes [NET_SCHED]: Add flow classifier

[NET_SCHED]: Constify struct tcf_ext_map

---
commit 12e33ddf57910b685501df10bd92223ea9b98fd6
tree 1ce47c7b6b6b968940f3dc28f9d7839e78c85089
parent 8af03e782cae1e0a0f530ddd22301cdd12cf9dc0
author Patrick McHardy <[email protected]> Wed, 30 Jan 2008 21:59:26 +0100 committer Patrick McHardy <[email protected]> Thu, 31 Jan 2008 18:52:55 +0100

 include/net/pkt_cls.h   |    6 +++---
 net/sched/cls_api.c     |    6 +++---
 net/sched/cls_basic.c   |    2 +-
 net/sched/cls_fw.c      |    2 +-
 net/sched/cls_route.c   |    2 +-
 net/sched/cls_tcindex.c |    2 +-
 net/sched/cls_u32.c     |    2 +-
 7 files changed, 11 insertions(+), 11 deletions(-)

index 8716eb7..d349c66 100644
@@ -131,14 +131,14 @@ tcf_exts_exec(struct sk_buff *skb, struct tcf_exts *exts,
 
 extern int tcf_exts_validate(struct tcf_proto *tp, struct nlattr **tb,
 	                     struct nlattr *rate_tlv, struct tcf_exts *exts,
-	                     struct tcf_ext_map *map);
+	                     const struct tcf_ext_map *map);
 extern void tcf_exts_destroy(struct tcf_proto *tp, struct tcf_exts *exts);
 extern void tcf_exts_change(struct tcf_proto *tp, struct tcf_exts *dst,
 	                     struct tcf_exts *src);
 extern int tcf_exts_dump(struct sk_buff *skb, struct tcf_exts *exts,
-	                 struct tcf_ext_map *map);
+	                 const struct tcf_ext_map *map);
 extern int tcf_exts_dump_stats(struct sk_buff *skb, struct tcf_exts *exts,
-	                       struct tcf_ext_map *map);
+	                       const struct tcf_ext_map *map);
 
 /**
  * struct tcf_pkt_info - packet information

index 3377ca0..0fbedca 100644
@@ -482,7 +482,7 @@ EXPORT_SYMBOL(tcf_exts_destroy);
 
 int tcf_exts_validate(struct tcf_proto *tp, struct nlattr **tb,
 		  struct nlattr *rate_tlv, struct tcf_exts *exts,
-		  struct tcf_ext_map *map)
+		  const struct tcf_ext_map *map)
 {
 	memset(exts, 0, sizeof(*exts));
 

@@ -535,7 +535,7 @@ void tcf_exts_change(struct tcf_proto *tp, struct tcf_exts *dst,
 EXPORT_SYMBOL(tcf_exts_change);
 
 int tcf_exts_dump(struct sk_buff *skb, struct tcf_exts *exts,
-	      struct tcf_ext_map *map)
+		  const struct tcf_ext_map *map)
 {
 #ifdef CONFIG_NET_CLS_ACT
 	if (map->action && exts->action) {

@@ -571,7 +571,7 @@ EXPORT_SYMBOL(tcf_exts_dump);
 
 
 int tcf_exts_dump_stats(struct sk_buff *skb, struct tcf_exts *exts,
-			struct tcf_ext_map *map)
+			const struct tcf_ext_map *map)
 {
 #ifdef CONFIG_NET_CLS_ACT
 	if (exts->action)

index bfb4342..956915c 100644
@@ -35,7 +35,7 @@ struct basic_filter
 	struct list_head	link;
 };
 
-static struct tcf_ext_map basic_ext_map = {
+static const struct tcf_ext_map basic_ext_map = {
 	.action = TCA_BASIC_ACT,
 	.police = TCA_BASIC_POLICE
 };

index 436a6e7..b0f90e5 100644
@@ -47,7 +47,7 @@ struct fw_filter
 	struct tcf_exts		exts;
 };
 
-static struct tcf_ext_map fw_ext_map = {
+static const struct tcf_ext_map fw_ext_map = {
 	.action = TCA_FW_ACT,
 	.police = TCA_FW_POLICE
 };

index f7e7d39..784dcb8 100644
@@ -62,7 +62,7 @@ struct route4_filter
 
 #define ROUTE4_FAILURE ((struct route4_filter*)(-1L))
 
-static struct tcf_ext_map route_ext_map = {
+static const struct tcf_ext_map route_ext_map = {
 	.police = TCA_ROUTE4_POLICE,
 	.action = TCA_ROUTE4_ACT
 };

index ee60b2d..7a7bff5 100644
@@ -55,7 +55,7 @@ struct tcindex_data {
 	int fall_through;	/* 0: only classify if explicit match */
 };
 
-static struct tcf_ext_map tcindex_ext_map = {
+static const struct tcf_ext_map tcindex_ext_map = {
 	.police = TCA_TCINDEX_POLICE,
 	.action = TCA_TCINDEX_ACT
 };

index e8a7756..b18fa95 100644
@@ -82,7 +82,7 @@ struct tc_u_common
 	u32			hgenerator;
 };
 
-static struct tcf_ext_map u32_ext_map = {
+static const struct tcf_ext_map u32_ext_map = {
 	.action = TCA_U32_ACT,
 	.police = TCA_U32_POLICE
 };

[NET_SCHED]: sch_sfq: add support for external classifiers

Add support for external classifiers to allow using different flow hash functions similar to ESFQ. When no classifier is attached the built-in hash is used as before.

---
commit 6049892cc4acca9af393e134e4cdaf6b3e1ccad9
tree 9a8347d45808de2aef14486e5792fcab58baf3fe
parent 12e33ddf57910b685501df10bd92223ea9b98fd6
author Patrick McHardy <[email protected]> Wed, 30 Jan 2008 21:59:27 +0100 committer Patrick McHardy <[email protected]> Thu, 31 Jan 2008 18:52:55 +0100

 net/sched/sch_sfq.c |   95 +++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 91 insertions(+), 4 deletions(-)

index 91af539..d818d19 100644
@@ -95,6 +95,7 @@ struct sfq_sched_data
 	int		limit;
 
 /* Variables */
+	struct tcf_proto *filter_list;
 	struct timer_list perturb_timer;
 	u32		perturbation;
 	sfq_index	tail;		/* Index of current slot in round */

@@ -155,6 +156,39 @@ static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
 	return sfq_fold_hash(q, h, h2);
 }
 
+static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
+				 int *qerr)
+{
+	struct sfq_sched_data *q = qdisc_priv(sch);
+	struct tcf_result res;
+	int result;
+
+	if (TC_H_MAJ(skb->priority) == sch->handle &&
+	    TC_H_MIN(skb->priority) > 0 &&
+	    TC_H_MIN(skb->priority) <= SFQ_HASH_DIVISOR)
+		return TC_H_MIN(skb->priority);
+
+	if (!q->filter_list)
+		return sfq_hash(q, skb) + 1;
+
+	*qerr = NET_XMIT_BYPASS;
+	result = tc_classify(skb, q->filter_list, &res);
+	if (result >= 0) {
+#ifdef CONFIG_NET_CLS_ACT
+		switch (result) {
+		case TC_ACT_STOLEN:
+		case TC_ACT_QUEUED:
+			*qerr = NET_XMIT_SUCCESS;
+		case TC_ACT_SHOT:
+			return 0;
+		}
+#endif
+		if (TC_H_MIN(res.classid) <= SFQ_HASH_DIVISOR)
+			return TC_H_MIN(res.classid);
+	}
+	return 0;
+}
+
 static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
 {
 	sfq_index p, n;

@@ -245,8 +279,18 @@ static int
 sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
-	unsigned hash = sfq_hash(q, skb);
+	unsigned int hash;
 	sfq_index x;
+	int ret;
+
+	hash = sfq_classify(skb, sch, &ret);
+	if (hash == 0) {
+		if (ret == NET_XMIT_BYPASS)
+			sch->qstats.drops++;
+		kfree_skb(skb);
+		return ret;
+	}
+	hash--;
 
 	x = q->ht[hash];
 	if (x == SFQ_DEPTH) {

@@ -289,8 +333,18 @@ 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);
+	unsigned int hash;
 	sfq_index x;
+	int ret;
+
+	hash = sfq_classify(skb, sch, &ret);
+	if (hash == 0) {
+		if (ret == NET_XMIT_BYPASS)
+			sch->qstats.drops++;
+		kfree_skb(skb);
+		return ret;
+	}
+	hash--;
 
 	x = q->ht[hash];
 	if (x == SFQ_DEPTH) {

@@ -465,6 +519,8 @@ static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
 static void sfq_destroy(struct Qdisc *sch)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
+
+	tcf_destroy_chain(q->filter_list);
 	del_timer(&q->perturb_timer);
 }
 

@@ -490,9 +546,40 @@ nla_put_failure:
 	return -1;
 }
 
+static int sfq_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
+			    struct nlattr **tca, unsigned long *arg)
+{
+	return -EOPNOTSUPP;
+}
+
+static unsigned long sfq_get(struct Qdisc *sch, u32 classid)
+{
+	return 0;
+}
+
+static struct tcf_proto **sfq_find_tcf(struct Qdisc *sch, unsigned long cl)
+{
+	struct sfq_sched_data *q = qdisc_priv(sch);
+
+	if (cl)
+		return NULL;
+	return &q->filter_list;
+}
+
+static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
+{
+	return;
+}
+
+static const struct Qdisc_class_ops sfq_class_ops = {
+	.get		=	sfq_get,
+	.change		=	sfq_change_class,
+	.tcf_chain	=	sfq_find_tcf,
+	.walk		=	sfq_walk,
+};
+
 static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
-	.next		=	NULL,
-	.cl_ops		=	NULL,
+	.cl_ops		=	&sfq_class_ops,
 	.id		=	"sfq",
 	.priv_size	=	sizeof(struct sfq_sched_data),
 	.enqueue	=	sfq_enqueue,

[NET_SCHED]: sch_sfq: make internal queues visible as classes

Add support for dumping statistics and make internal queues visible as classes.

---
commit 7a281f8ef334a35d699682315e9f80a3e006376c
tree 0a2cbd55e22f1913e9cf0cc28da2956952110243
parent 6049892cc4acca9af393e134e4cdaf6b3e1ccad9
author Patrick McHardy <[email protected]> Wed, 30 Jan 2008 21:59:29 +0100 committer Patrick McHardy <[email protected]> Thu, 31 Jan 2008 18:52:56 +0100

 include/linux/pkt_sched.h |    5 +++++
 net/sched/sch_sfq.c       |   41 ++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 45 insertions(+), 1 deletions(-)

index 3276135..dbb7ac3 100644
@@ -150,6 +150,11 @@ struct tc_sfq_qopt
 	unsigned	flows;		/* Maximal number of flows  */
 };
 
+struct tc_sfq_xstats
+{
+	__s32		allot;
+};
+
 /*
  *  NOTE: limit, divisor and flows are hardwired to code at the moment.
  *

[NET_SCHED]: Add flow classifier

Add new "flow" classifier, which is meant to extend the SFQ hashing capabilities without hard-coding new hash functions and also allows deterministic mappings of keys to classes, replacing some out of tree iptables patches like IPCLASSIFY (maps IPs to classes), IPMARK (maps IPs to marks, with fw filters to classes), ...

Some examples:

- Classic SFQ hash:

  tc filter add ... flow hash \
  	keys src,dst,proto,proto-src,proto-dst divisor 1024

- Classic SFQ hash, but using information from conntrack to work properly in combination with NAT:

  tc filter add ... flow hash \
  	keys nfct-src,nfct-dst,proto,nfct-proto-src,nfct-proto-dst divisor 1024

- Map destination IPs of 192.168.0.0/24 to classids 1-257:

  tc filter add ... flow map \
  	key dst addend -192.168.0.0 divisor 256

- alternatively:

  tc filter add ... flow map \
  	key dst and 0xff

- similar, but reverse ordered:

  tc filter add ... flow map \
  	key dst and 0xff xor 0xff

Perturbation is currently not supported because we can't reliable kill the timer on destruction.

---
commit 91a3a09ce63cba8df30ac42133a40dd64c0a7259
tree 2572feb8ffd88e6abf9270d2137af2a4cf7f542a
parent 7a281f8ef334a35d699682315e9f80a3e006376c
author Patrick McHardy <[email protected]> Wed, 30 Jan 2008 21:59:31 +0100 committer Patrick McHardy <[email protected]> Thu, 31 Jan 2008 18:52:56 +0100

 include/linux/pkt_cls.h |   50 ++++
 net/sched/Kconfig       |   11 +
 net/sched/Makefile      |    1 
 net/sched/cls_flow.c    |  660 +++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 722 insertions(+), 0 deletions(-)

index 30b8571..1c1dba9 100644
@@ -328,6 +328,56 @@ enum
 
 #define TCA_TCINDEX_MAX     (__TCA_TCINDEX_MAX - 1)
 
+/* Flow filter */
+
+enum
+{
+	FLOW_KEY_SRC,
+	FLOW_KEY_DST,
+	FLOW_KEY_PROTO,
+	FLOW_KEY_PROTO_SRC,
+	FLOW_KEY_PROTO_DST,
+	FLOW_KEY_IIF,
+	FLOW_KEY_PRIORITY,
+	FLOW_KEY_MARK,
+	FLOW_KEY_NFCT,
+	FLOW_KEY_NFCT_SRC,
+	FLOW_KEY_NFCT_DST,
+	FLOW_KEY_NFCT_PROTO_SRC,
+	FLOW_KEY_NFCT_PROTO_DST,
+	FLOW_KEY_RTCLASSID,
+	FLOW_KEY_SKUID,
+	FLOW_KEY_SKGID,
+	__FLOW_KEY_MAX,
+};
+
+#define FLOW_KEY_MAX	(__FLOW_KEY_MAX - 1)
+
+enum
+{
+	FLOW_MODE_MAP,
+	FLOW_MODE_HASH,
+};
+
+enum
+{
+	TCA_FLOW_UNSPEC,
+	TCA_FLOW_KEYS,
+	TCA_FLOW_MODE,
+	TCA_FLOW_BASECLASS,
+	TCA_FLOW_RSHIFT,
+	TCA_FLOW_ADDEND,
+	TCA_FLOW_MASK,
+	TCA_FLOW_XOR,
+	TCA_FLOW_DIVISOR,
+	TCA_FLOW_ACT,
+	TCA_FLOW_POLICE,
+	TCA_FLOW_EMATCHES,
+	__TCA_FLOW_MAX
+};
+
+#define TCA_FLOW_MAX	(__TCA_FLOW_MAX - 1)
+
 /* Basic filter */
 
 enum

index 87af7c9..bccf42b 100644
@@ -307,6 +307,17 @@ config NET_CLS_RSVP6
 	  To compile this code as a module, choose M here: the
 	  module will be called cls_rsvp6.
 
+config NET_CLS_FLOW
+	tristate "Flow classifier"
+	select NET_CLS
+	---help---
+	  If you say Y here, you will be able to classify packets based on
+	  a configurable combination of packet keys. This is mostly useful
+	  in combination with SFQ.
+
+	  To compile this code as a module, choose M here: the
+	  module will be called cls_flow.
+
 config NET_EMATCH
 	bool "Extended Matches"
 	select NET_CLS

index 81ecbe8..1d2b0f7 100644
@@ -35,6 +35,7 @@ obj-$(CONFIG_NET_CLS_RSVP)	+= cls_rsvp.o
 obj-$(CONFIG_NET_CLS_TCINDEX)	+= cls_tcindex.o
 obj-$(CONFIG_NET_CLS_RSVP6)	+= cls_rsvp6.o
 obj-$(CONFIG_NET_CLS_BASIC)	+= cls_basic.o
+obj-$(CONFIG_NET_CLS_FLOW)	+= cls_flow.o
 obj-$(CONFIG_NET_EMATCH)	+= ematch.o
 obj-$(CONFIG_NET_EMATCH_CMP)	+= em_cmp.o
 obj-$(CONFIG_NET_EMATCH_NBYTE)	+= em_nbyte.o

From: Patrick McHardy <[email protected]>
Date: Thu, 31 Jan 2008 18:58:02 +0100 (MET)

Applied, thanks Patrick.

Excellent! I'm glad this is applied. I'm having trouble figuring out how it works, though. As a test, I'm trying to set up SFQ equivalent to ESFQ's "hash dst". Here's what I do, and this is what I get:

------------------------------------------------------------------------

# ./tc qdisc add dev eth0 root handle 1: sfq
# ./tc filter add dev eth0 parent 1: flow hash keys dst
RTNETLINK answers: Invalid argument
We have an error talking to the kernel
------------------------------------------------------------------------

I've tried a few different keys with the same results. I don't know what I'm doing wrong, or even where to start figuring it out. Can you point me in the right direction?

Here are some details that may be pertinent:

- current net-2.6 git (I double-checked)
- CONFIG_NET_CLS_FLOW=y
- current iproute2 git
- running on amd64 user-mode Linux

Thanks,
Corey

You're missing protocol, handle etc. Try something like this:

tc filter add dev eth0 protocol ip pref 1 parent 1: handle 1 \

flow hash keys dst divisor 1024

Thanks, the kernel accepts that. I guess I understand tc filter usage less than I thought I did.... Time to teach myself better.

-Corey

I've been trying to incorporate this into my own setup but haven't got very far :-)

I don't even know if it's possible to attach to htb subclasses and expect it to work. If it is do you have an example (is this what baseclass is for?).

I can attach to a filter to other than parent 1:0 OK but it doesn't do anything.

I have also tried incorporating flow into the 1:0 filters that filter to the htb subclasses that have the sfqs attached to them, but can't get ematch to work - but then I have never been able to get ematch to work. I can't find any examples. All I need if this is the way to go is to match on mark and match on anything.

Is this possible and if so, do you have/know of any examples?

Andy.

What exactly are you trying to do? If you attach the classifier to HTB, it will classify to HTB classes. I guess you actually want to use it for SFQ, which should work with:

tc qdisc add ... handle x: sfq
tc filter add parent x: protocol all flow ...

Ahh thanks. It's so obvious now :-)

I didn't have handles specified on the sfqs and was trying to use the htb leafs handles.

It's cool being able to see the sfq flows.

Andy.

It's also interesting to notice that allot varies so much.

I have seen +/- 10 * my quantum which I didn't expect, I wonder if it needs to be cleared when a flow empties or something.

The source for sfq is a bit hard to follow so I don't really know what's happening. I was dropping with limit of 40 (about a second at my rate) and had quite a few connections active, hashing on dst.

tcpdump also shows that single flows are getting 3/4/5 packets dequeued in a row when there are other flows active.

I guess it's hard to tell the state at any one instant when dropping and making flows dis/reappear but it does seem to behave in a way that amplifies burstyness.

My quantum = mtu + 14 and there are no giants.

Andy.

I'm not really sure myself. SFQ and CBQ DRR differ slightly from the original DRR algorithm by allowing the quantum to go negative and carrying it over in the next round, where it has to be made up for. CBQ DRR differs from SFQ in that it keeps an inactive flow (==empty queue) active until it reaches a positive quantum again, which is necessary for this implementation if you want to reset the quantum to avoid having a bursty flow send out its last packet by overusing its quantum, then going passive and immediately active again with a full new quantum. This would cause unfairness against constantly active flows. CBQ does not reset the quantum when activating a class though, which also looks like a bug.

I haven't fully understood the differences between the SFQ/CBQ DRR implementations and the original DRR algorithm, but I'm looking into it for other reasons anyways (my DRR scheduler uses a similar implementation because it avoids the need to requeue and I want to properly understand this before pushing it upstream), so I can hopefully soon tell you more :)

OK - FWIW I've been looking harder and have now seen the full range of +/- 32k so I assume it's just not getting initialised properly.

Andy.

Hmm I am not so sure now maybe it's a stats thing - I have seen flows apparently stuck with -ve allot but behaving normally.

I notice allot is short (16bits?) in sfq but see

+struct tc_sfq_xstats
+{
+ __s32 allot;
+};

Andy.

OK - I have the __s32 version in iproute git and in kernel 2.6.25-rc7.

I did have some hassle building iproute2 though, tc built OK once I removed ip from the build, so maybe I'll try again over the weekend from scratch just incase I messed something up.

Looking at the sfq code it seems that enqueue doesn't init/zero allot for a new flow unless it's the first and most of what I see fits with this. But rarely it doesn't look like that's all there is to it.

Andy.

Actually it fits perfectly, so that is all there is to it. Dequeue dequeues first then checks allot so even if the allot is stuck at -20345 or something the flow will still get 1 packet per round which is what I've seen. I first thought it should have moved towards 0 like it does when it starts too high.

Andy.

Seems like this change fixes it for me, though I since noticed that requeue will need the same change as well.

@@ -317,6 +317,7 @@
                        q->next[x] = q->next[q->tail];
                        q->next[q->tail] = x;
                        q->tail = x;
+                       q->allot[x] = 0;
                }
        }
        if (++sch->q.qlen <= q->limit) {

Andy.

I guess it would be nice in some ways to make a drr that has memory but I think this is a bug.

It was the same pre jhash when perturb was needed so the slots would change anyway.

If it were intended to be a memory of allot it fails because allot should never be as wide as +/- 32k (maybe that could be fixed - but only recently became practical with jhash/no perturb).

Currently a new flow (but not the fist) gets dealt a seemingly random allot of +/- 32k which means it either gets to monopolise the link until it has wound down to <=0 or if allot is -ve it gets disadvantaged in the case that it's packet size is < than the others until its allot has crept up to 0. If it's packets are MTU size it just gets 1 packet per round and allot stays -ve.

Andy.