[NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Patrick McHardy]

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 01/04]: Constify struct tcf_ext_map

[Patrick McHardy]

[NET_SCHED]: Constify struct tcf_ext_map

Signed-off-by: Patrick McHardy <kaber@trash.net>

---
commit 12e33ddf57910b685501df10bd92223ea9b98fd6
tree 1ce47c7b6b6b968940f3dc28f9d7839e78c85089
parent 8af03e782cae1e0a0f530ddd22301cdd12cf9dc0
author Patrick McHardy <kaber@trash.net> Wed, 30 Jan 2008 21:59:26 +0100
committer Patrick McHardy <kaber@trash.net> 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(-)

diff --git a/include/net/pkt_cls.h b/include/net/pkt_cls.h
index 8716eb7..d349c66 100644
--- a/include/net/pkt_cls.h
+++ b/include/net/pkt_cls.h
@@ -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
diff --git a/net/sched/cls_api.c b/net/sched/cls_api.c
index 3377ca0..0fbedca 100644
--- a/net/sched/cls_api.c
+++ b/net/sched/cls_api.c
@@ -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)
diff --git a/net/sched/cls_basic.c b/net/sched/cls_basic.c
index bfb4342..956915c 100644
--- a/net/sched/cls_basic.c
+++ b/net/sched/cls_basic.c
@@ -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
 };
diff --git a/net/sched/cls_fw.c b/net/sched/cls_fw.c
index 436a6e7..b0f90e5 100644
--- a/net/sched/cls_fw.c
+++ b/net/sched/cls_fw.c
@@ -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
 };
diff --git a/net/sched/cls_route.c b/net/sched/cls_route.c
index f7e7d39..784dcb8 100644
--- a/net/sched/cls_route.c
+++ b/net/sched/cls_route.c
@@ -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
 };
diff --git a/net/sched/cls_tcindex.c b/net/sched/cls_tcindex.c
index ee60b2d..7a7bff5 100644
--- a/net/sched/cls_tcindex.c
+++ b/net/sched/cls_tcindex.c
@@ -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
 };
diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index e8a7756..b18fa95 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -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 02/04]: sch_sfq: add support for external classifiers

[Patrick McHardy]

[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.

Signed-off-by: Patrick McHardy <kaber@trash.net>

---
commit 6049892cc4acca9af393e134e4cdaf6b3e1ccad9
tree 9a8347d45808de2aef14486e5792fcab58baf3fe
parent 12e33ddf57910b685501df10bd92223ea9b98fd6
author Patrick McHardy <kaber@trash.net> Wed, 30 Jan 2008 21:59:27 +0100
committer Patrick McHardy <kaber@trash.net> Thu, 31 Jan 2008 18:52:55 +0100

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

diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 91af539..d818d19 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -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 03/04]: sch_sfq: make internal queues visible as classes

[Patrick McHardy]

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

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

Signed-off-by: Patrick McHardy <kaber@trash.net>

---
commit 7a281f8ef334a35d699682315e9f80a3e006376c
tree 0a2cbd55e22f1913e9cf0cc28da2956952110243
parent 6049892cc4acca9af393e134e4cdaf6b3e1ccad9
author Patrick McHardy <kaber@trash.net> Wed, 30 Jan 2008 21:59:29 +0100
committer Patrick McHardy <kaber@trash.net> 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(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index 3276135..dbb7ac3 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -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.
  *
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index d818d19..a20e2ef 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -566,15 +566,54 @@ static struct tcf_proto **sfq_find_tcf(struct Qdisc *sch, unsigned long cl)
 	return &q->filter_list;
 }
 
+static int sfq_dump_class(struct Qdisc *sch, unsigned long cl,
+			  struct sk_buff *skb, struct tcmsg *tcm)
+{
+	tcm->tcm_handle |= TC_H_MIN(cl);
+	return 0;
+}
+
+static int sfq_dump_class_stats(struct Qdisc *sch, unsigned long cl,
+				struct gnet_dump *d)
+{
+	struct sfq_sched_data *q = qdisc_priv(sch);
+	sfq_index idx = q->ht[cl-1];
+	struct gnet_stats_queue qs = { .qlen = q->qs[idx].qlen };
+	struct tc_sfq_xstats xstats = { .allot = q->allot[idx] };
+
+	if (gnet_stats_copy_queue(d, &qs) < 0)
+		return -1;
+	return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
+}
+
 static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 {
-	return;
+	struct sfq_sched_data *q = qdisc_priv(sch);
+	unsigned int i;
+
+	if (arg->stop)
+		return;
+
+	for (i = 0; i < SFQ_HASH_DIVISOR; i++) {
+		if (q->ht[i] == SFQ_DEPTH ||
+		    arg->count < arg->skip) {
+			arg->count++;
+			continue;
+		}
+		if (arg->fn(sch, i + 1, arg) < 0) {
+			arg->stop = 1;
+			break;
+		}
+		arg->count++;
+	}
 }
 
 static const struct Qdisc_class_ops sfq_class_ops = {
 	.get		=	sfq_get,
 	.change		=	sfq_change_class,
 	.tcf_chain	=	sfq_find_tcf,
+	.dump		=	sfq_dump_class,
+	.dump_stats	=	sfq_dump_class_stats,
 	.walk		=	sfq_walk,
 };
 

[NET_SCHED 04/04]: Add flow classifier

[Patrick McHardy]

[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.

Signed-off-by: Patrick McHardy <kaber@trash.net>

---
commit 91a3a09ce63cba8df30ac42133a40dd64c0a7259
tree 2572feb8ffd88e6abf9270d2137af2a4cf7f542a
parent 7a281f8ef334a35d699682315e9f80a3e006376c
author Patrick McHardy <kaber@trash.net> Wed, 30 Jan 2008 21:59:31 +0100
committer Patrick McHardy <kaber@trash.net> 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(-)

diff --git a/include/linux/pkt_cls.h b/include/linux/pkt_cls.h
index 30b8571..1c1dba9 100644
--- a/include/linux/pkt_cls.h
+++ b/include/linux/pkt_cls.h
@@ -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
diff --git a/net/sched/Kconfig b/net/sched/Kconfig
index 87af7c9..bccf42b 100644
--- a/net/sched/Kconfig
+++ b/net/sched/Kconfig
@@ -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
diff --git a/net/sched/Makefile b/net/sched/Makefile
index 81ecbe8..1d2b0f7 100644
--- a/net/sched/Makefile
+++ b/net/sched/Makefile
@@ -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
diff --git a/net/sched/cls_flow.c b/net/sched/cls_flow.c
new file mode 100644
index 0000000..5a7f6a3
--- /dev/null
+++ b/net/sched/cls_flow.c
@@ -0,0 +1,660 @@
+/*
+ * net/sched/cls_flow.c		Generic flow classifier
+ *
+ * Copyright (c) 2007, 2008 Patrick McHardy <kaber@trash.net>
+ *
+ * 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.
+ */
+
+#include <linux/kernel.h>
+#include <linux/init.h>
+#include <linux/list.h>
+#include <linux/jhash.h>
+#include <linux/random.h>
+#include <linux/pkt_cls.h>
+#include <linux/skbuff.h>
+#include <linux/in.h>
+#include <linux/ip.h>
+#include <linux/ipv6.h>
+
+#include <net/pkt_cls.h>
+#include <net/ip.h>
+#include <net/route.h>
+#if defined(CONFIG_NF_CONNTRACK) || defined(CONFIG_NF_CONNTRACK_MODULE)
+#include <net/netfilter/nf_conntrack.h>
+#endif
+
+struct flow_head {
+	struct list_head	filters;
+};
+
+struct flow_filter {
+	struct list_head	list;
+	struct tcf_exts		exts;
+	struct tcf_ematch_tree	ematches;
+	u32			handle;
+
+	u32			nkeys;
+	u32			keymask;
+	u32			mode;
+	u32			mask;
+	u32			xor;
+	u32			rshift;
+	u32			addend;
+	u32			divisor;
+	u32			baseclass;
+};
+
+static u32 flow_hashrnd __read_mostly;
+static int flow_hashrnd_initted __read_mostly;
+
+static const struct tcf_ext_map flow_ext_map = {
+	.action	= TCA_FLOW_ACT,
+	.police	= TCA_FLOW_POLICE,
+};
+
+static inline u32 addr_fold(void *addr)
+{
+	unsigned long a = (unsigned long)addr;
+
+	return (a & 0xFFFFFFFF) ^ (BITS_PER_LONG > 32 ? a >> 32 : 0);
+}
+
+static u32 flow_get_src(const struct sk_buff *skb)
+{
+	switch (skb->protocol) {
+	case __constant_htons(ETH_P_IP):
+		return ntohl(ip_hdr(skb)->saddr);
+	case __constant_htons(ETH_P_IPV6):
+		return ntohl(ipv6_hdr(skb)->saddr.s6_addr32[3]);
+	default:
+		return addr_fold(skb->sk);
+	}
+}
+
+static u32 flow_get_dst(const struct sk_buff *skb)
+{
+	switch (skb->protocol) {
+	case __constant_htons(ETH_P_IP):
+		return ntohl(ip_hdr(skb)->daddr);
+	case __constant_htons(ETH_P_IPV6):
+		return ntohl(ipv6_hdr(skb)->daddr.s6_addr32[3]);
+	default:
+		return addr_fold(skb->dst) ^ (__force u16)skb->protocol;
+	}
+}
+
+static u32 flow_get_proto(const struct sk_buff *skb)
+{
+	switch (skb->protocol) {
+	case __constant_htons(ETH_P_IP):
+		return ip_hdr(skb)->protocol;
+	case __constant_htons(ETH_P_IPV6):
+		return ipv6_hdr(skb)->nexthdr;
+	default:
+		return 0;
+	}
+}
+
+static int has_ports(u8 protocol)
+{
+	switch (protocol) {
+	case IPPROTO_TCP:
+	case IPPROTO_UDP:
+	case IPPROTO_UDPLITE:
+	case IPPROTO_SCTP:
+	case IPPROTO_DCCP:
+	case IPPROTO_ESP:
+		return 1;
+	default:
+		return 0;
+	}
+}
+
+static u32 flow_get_proto_src(const struct sk_buff *skb)
+{
+	u32 res = 0;
+
+	switch (skb->protocol) {
+	case __constant_htons(ETH_P_IP): {
+		struct iphdr *iph = ip_hdr(skb);
+
+		if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
+		    has_ports(iph->protocol))
+			res = ntohs(*(__be16 *)((void *)iph + iph->ihl * 4));
+		break;
+	}
+	case __constant_htons(ETH_P_IPV6): {
+		struct ipv6hdr *iph = ipv6_hdr(skb);
+
+		if (has_ports(iph->nexthdr))
+			res = ntohs(*(__be16 *)&iph[1]);
+		break;
+	}
+	default:
+		res = addr_fold(skb->sk);
+	}
+
+	return res;
+}
+
+static u32 flow_get_proto_dst(const struct sk_buff *skb)
+{
+	u32 res = 0;
+
+	switch (skb->protocol) {
+	case __constant_htons(ETH_P_IP): {
+		struct iphdr *iph = ip_hdr(skb);
+
+		if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
+		    has_ports(iph->protocol))
+			res = ntohs(*(__be16 *)((void *)iph + iph->ihl * 4 + 2));
+		break;
+	}
+	case __constant_htons(ETH_P_IPV6): {
+		struct ipv6hdr *iph = ipv6_hdr(skb);
+
+		if (has_ports(iph->nexthdr))
+			res = ntohs(*(__be16 *)((void *)&iph[1] + 2));
+		break;
+	}
+	default:
+		res = addr_fold(skb->dst) ^ (__force u16)skb->protocol;
+	}
+
+	return res;
+}
+
+static u32 flow_get_iif(const struct sk_buff *skb)
+{
+	return skb->iif;
+}
+
+static u32 flow_get_priority(const struct sk_buff *skb)
+{
+	return skb->priority;
+}
+
+static u32 flow_get_mark(const struct sk_buff *skb)
+{
+	return skb->mark;
+}
+
+static u32 flow_get_nfct(const struct sk_buff *skb)
+{
+#if defined(CONFIG_NF_CONNTRACK) || defined(CONFIG_NF_CONNTRACK_MODULE)
+	return addr_fold(skb->nfct);
+#else
+	return 0;
+#endif
+}
+
+#if defined(CONFIG_NF_CONNTRACK) || defined(CONFIG_NF_CONNTRACK_MODULE)
+#define CTTUPLE(skb, member)						\
+({									\
+	enum ip_conntrack_info ctinfo;					\
+	struct nf_conn *ct = nf_ct_get(skb, &ctinfo);			\
+	if (ct == NULL)							\
+		goto fallback;						\
+	ct->tuplehash[CTINFO2DIR(ctinfo)].tuple.member;			\
+})
+#else
+#define CTTUPLE(skb, member)						\
+({									\
+	goto fallback;							\
+	0;								\
+})
+#endif
+
+static u32 flow_get_nfct_src(const struct sk_buff *skb)
+{
+	switch (skb->protocol) {
+	case __constant_htons(ETH_P_IP):
+		return ntohl(CTTUPLE(skb, src.u3.ip));
+	case __constant_htons(ETH_P_IPV6):
+		return ntohl(CTTUPLE(skb, src.u3.ip6[3]));
+	}
+fallback:
+	return flow_get_src(skb);
+}
+
+static u32 flow_get_nfct_dst(const struct sk_buff *skb)
+{
+	switch (skb->protocol) {
+	case __constant_htons(ETH_P_IP):
+		return ntohl(CTTUPLE(skb, dst.u3.ip));
+	case __constant_htons(ETH_P_IPV6):
+		return ntohl(CTTUPLE(skb, dst.u3.ip6[3]));
+	}
+fallback:
+	return flow_get_dst(skb);
+}
+
+static u32 flow_get_nfct_proto_src(const struct sk_buff *skb)
+{
+	return ntohs(CTTUPLE(skb, src.u.all));
+fallback:
+	return flow_get_proto_src(skb);
+}
+
+static u32 flow_get_nfct_proto_dst(const struct sk_buff *skb)
+{
+	return ntohs(CTTUPLE(skb, dst.u.all));
+fallback:
+	return flow_get_proto_dst(skb);
+}
+
+static u32 flow_get_rtclassid(const struct sk_buff *skb)
+{
+#ifdef CONFIG_NET_CLS_ROUTE
+	if (skb->dst)
+		return skb->dst->tclassid;
+#endif
+	return 0;
+}
+
+static u32 flow_get_skuid(const struct sk_buff *skb)
+{
+	if (skb->sk && skb->sk->sk_socket && skb->sk->sk_socket->file)
+		return skb->sk->sk_socket->file->f_uid;
+	return 0;
+}
+
+static u32 flow_get_skgid(const struct sk_buff *skb)
+{
+	if (skb->sk && skb->sk->sk_socket && skb->sk->sk_socket->file)
+		return skb->sk->sk_socket->file->f_gid;
+	return 0;
+}
+
+static u32 flow_key_get(const struct sk_buff *skb, int key)
+{
+	switch (key) {
+	case FLOW_KEY_SRC:
+		return flow_get_src(skb);
+	case FLOW_KEY_DST:
+		return flow_get_dst(skb);
+	case FLOW_KEY_PROTO:
+		return flow_get_proto(skb);
+	case FLOW_KEY_PROTO_SRC:
+		return flow_get_proto_src(skb);
+	case FLOW_KEY_PROTO_DST:
+		return flow_get_proto_dst(skb);
+	case FLOW_KEY_IIF:
+		return flow_get_iif(skb);
+	case FLOW_KEY_PRIORITY:
+		return flow_get_priority(skb);
+	case FLOW_KEY_MARK:
+		return flow_get_mark(skb);
+	case FLOW_KEY_NFCT:
+		return flow_get_nfct(skb);
+	case FLOW_KEY_NFCT_SRC:
+		return flow_get_nfct_src(skb);
+	case FLOW_KEY_NFCT_DST:
+		return flow_get_nfct_dst(skb);
+	case FLOW_KEY_NFCT_PROTO_SRC:
+		return flow_get_nfct_proto_src(skb);
+	case FLOW_KEY_NFCT_PROTO_DST:
+		return flow_get_nfct_proto_dst(skb);
+	case FLOW_KEY_RTCLASSID:
+		return flow_get_rtclassid(skb);
+	case FLOW_KEY_SKUID:
+		return flow_get_skuid(skb);
+	case FLOW_KEY_SKGID:
+		return flow_get_skgid(skb);
+	default:
+		WARN_ON(1);
+		return 0;
+	}
+}
+
+static int flow_classify(struct sk_buff *skb, struct tcf_proto *tp,
+			 struct tcf_result *res)
+{
+	struct flow_head *head = tp->root;
+	struct flow_filter *f;
+	u32 keymask;
+	u32 classid;
+	unsigned int n, key;
+	int r;
+
+	list_for_each_entry(f, &head->filters, list) {
+		u32 keys[f->nkeys];
+
+		if (!tcf_em_tree_match(skb, &f->ematches, NULL))
+			continue;
+
+		keymask = f->keymask;
+
+		for (n = 0; n < f->nkeys; n++) {
+			key = ffs(keymask) - 1;
+			keymask &= ~(1 << key);
+			keys[n] = flow_key_get(skb, key);
+		}
+
+		if (f->mode == FLOW_MODE_HASH)
+			classid = jhash2(keys, f->nkeys, flow_hashrnd);
+		else {
+			classid = keys[0];
+			classid = (classid & f->mask) ^ f->xor;
+			classid = (classid >> f->rshift) + f->addend;
+		}
+
+		if (f->divisor)
+			classid %= f->divisor;
+
+		res->class   = 0;
+		res->classid = TC_H_MAKE(f->baseclass, f->baseclass + classid);
+
+		r = tcf_exts_exec(skb, &f->exts, res);
+		if (r < 0)
+			continue;
+		return r;
+	}
+	return -1;
+}
+
+static const struct nla_policy flow_policy[TCA_FLOW_MAX + 1] = {
+	[TCA_FLOW_KEYS]		= { .type = NLA_U32 },
+	[TCA_FLOW_MODE]		= { .type = NLA_U32 },
+	[TCA_FLOW_BASECLASS]	= { .type = NLA_U32 },
+	[TCA_FLOW_RSHIFT]	= { .type = NLA_U32 },
+	[TCA_FLOW_ADDEND]	= { .type = NLA_U32 },
+	[TCA_FLOW_MASK]		= { .type = NLA_U32 },
+	[TCA_FLOW_XOR]		= { .type = NLA_U32 },
+	[TCA_FLOW_DIVISOR]	= { .type = NLA_U32 },
+	[TCA_FLOW_ACT]		= { .type = NLA_NESTED },
+	[TCA_FLOW_POLICE]	= { .type = NLA_NESTED },
+	[TCA_FLOW_EMATCHES]	= { .type = NLA_NESTED },
+};
+
+static int flow_change(struct tcf_proto *tp, unsigned long base,
+		       u32 handle, struct nlattr **tca,
+		       unsigned long *arg)
+{
+	struct flow_head *head = tp->root;
+	struct flow_filter *f;
+	struct nlattr *opt = tca[TCA_OPTIONS];
+	struct nlattr *tb[TCA_FLOW_MAX + 1];
+	struct tcf_exts e;
+	struct tcf_ematch_tree t;
+	unsigned int nkeys = 0;
+	u32 baseclass = 0;
+	u32 keymask = 0;
+	u32 mode;
+	int err;
+
+	if (opt == NULL)
+		return -EINVAL;
+
+	err = nla_parse_nested(tb, TCA_FLOW_MAX, opt, flow_policy);
+	if (err < 0)
+		return err;
+
+	if (tb[TCA_FLOW_BASECLASS]) {
+		baseclass = nla_get_u32(tb[TCA_FLOW_BASECLASS]);
+		if (TC_H_MIN(baseclass) == 0)
+			return -EINVAL;
+	}
+
+	if (tb[TCA_FLOW_KEYS]) {
+		keymask = nla_get_u32(tb[TCA_FLOW_KEYS]);
+		if (fls(keymask) - 1 > FLOW_KEY_MAX)
+			return -EOPNOTSUPP;
+
+		nkeys = hweight32(keymask);
+		if (nkeys == 0)
+			return -EINVAL;
+	}
+
+	err = tcf_exts_validate(tp, tb, tca[TCA_RATE], &e, &flow_ext_map);
+	if (err < 0)
+		return err;
+
+	err = tcf_em_tree_validate(tp, tb[TCA_FLOW_EMATCHES], &t);
+	if (err < 0)
+		goto err1;
+
+	f = (struct flow_filter *)*arg;
+	if (f != NULL) {
+		err = -EINVAL;
+		if (f->handle != handle && handle)
+			goto err2;
+
+		mode = f->mode;
+		if (tb[TCA_FLOW_MODE])
+			mode = nla_get_u32(tb[TCA_FLOW_MODE]);
+		if (mode != FLOW_MODE_HASH && nkeys > 1)
+			goto err2;
+	} else {
+		err = -EINVAL;
+		if (!handle)
+			goto err2;
+		if (!tb[TCA_FLOW_KEYS])
+			goto err2;
+
+		mode = FLOW_MODE_MAP;
+		if (tb[TCA_FLOW_MODE])
+			mode = nla_get_u32(tb[TCA_FLOW_MODE]);
+		if (mode != FLOW_MODE_HASH && nkeys > 1)
+			goto err2;
+
+		if (TC_H_MAJ(baseclass) == 0)
+			baseclass = TC_H_MAKE(tp->q->handle, baseclass);
+		if (TC_H_MIN(baseclass) == 0)
+			baseclass = TC_H_MAKE(baseclass, 1);
+
+		err = -ENOBUFS;
+		f = kzalloc(sizeof(*f), GFP_KERNEL);
+		if (f == NULL)
+			goto err2;
+
+		f->handle = handle;
+		f->mask	  = ~0U;
+	}
+
+	tcf_exts_change(tp, &f->exts, &e);
+	tcf_em_tree_change(tp, &f->ematches, &t);
+
+	tcf_tree_lock(tp);
+
+	if (tb[TCA_FLOW_KEYS]) {
+		f->keymask = keymask;
+		f->nkeys   = nkeys;
+	}
+
+	f->mode = mode;
+
+	if (tb[TCA_FLOW_MASK])
+		f->mask = nla_get_u32(tb[TCA_FLOW_MASK]);
+	if (tb[TCA_FLOW_XOR])
+		f->xor = nla_get_u32(tb[TCA_FLOW_XOR]);
+	if (tb[TCA_FLOW_RSHIFT])
+		f->rshift = nla_get_u32(tb[TCA_FLOW_RSHIFT]);
+	if (tb[TCA_FLOW_ADDEND])
+		f->addend = nla_get_u32(tb[TCA_FLOW_ADDEND]);
+
+	if (tb[TCA_FLOW_DIVISOR])
+		f->divisor = nla_get_u32(tb[TCA_FLOW_DIVISOR]);
+	if (baseclass)
+		f->baseclass = baseclass;
+
+	if (*arg == 0)
+		list_add_tail(&f->list, &head->filters);
+
+	tcf_tree_unlock(tp);
+
+	*arg = (unsigned long)f;
+	return 0;
+
+err2:
+	tcf_em_tree_destroy(tp, &t);
+err1:
+	tcf_exts_destroy(tp, &e);
+	return err;
+}
+
+static void flow_destroy_filter(struct tcf_proto *tp, struct flow_filter *f)
+{
+	tcf_exts_destroy(tp, &f->exts);
+	tcf_em_tree_destroy(tp, &f->ematches);
+	kfree(f);
+}
+
+static int flow_delete(struct tcf_proto *tp, unsigned long arg)
+{
+	struct flow_filter *f = (struct flow_filter *)arg;
+
+	tcf_tree_lock(tp);
+	list_del(&f->list);
+	tcf_tree_unlock(tp);
+	flow_destroy_filter(tp, f);
+	return 0;
+}
+
+static int flow_init(struct tcf_proto *tp)
+{
+	struct flow_head *head;
+
+	if (!flow_hashrnd_initted) {
+		get_random_bytes(&flow_hashrnd, 4);
+		flow_hashrnd_initted = 1;
+	}
+
+	head = kzalloc(sizeof(*head), GFP_KERNEL);
+	if (head == NULL)
+		return -ENOBUFS;
+	INIT_LIST_HEAD(&head->filters);
+	tp->root = head;
+	return 0;
+}
+
+static void flow_destroy(struct tcf_proto *tp)
+{
+	struct flow_head *head = tp->root;
+	struct flow_filter *f, *next;
+
+	list_for_each_entry_safe(f, next, &head->filters, list) {
+		list_del(&f->list);
+		flow_destroy_filter(tp, f);
+	}
+	kfree(head);
+}
+
+static unsigned long flow_get(struct tcf_proto *tp, u32 handle)
+{
+	struct flow_head *head = tp->root;
+	struct flow_filter *f;
+
+	list_for_each_entry(f, &head->filters, list)
+		if (f->handle == handle)
+			return (unsigned long)f;
+	return 0;
+}
+
+static void flow_put(struct tcf_proto *tp, unsigned long f)
+{
+	return;
+}
+
+static int flow_dump(struct tcf_proto *tp, unsigned long fh,
+		     struct sk_buff *skb, struct tcmsg *t)
+{
+	struct flow_filter *f = (struct flow_filter *)fh;
+	struct nlattr *nest;
+
+	if (f == NULL)
+		return skb->len;
+
+	t->tcm_handle = f->handle;
+
+	nest = nla_nest_start(skb, TCA_OPTIONS);
+	if (nest == NULL)
+		goto nla_put_failure;
+
+	NLA_PUT_U32(skb, TCA_FLOW_KEYS, f->keymask);
+	NLA_PUT_U32(skb, TCA_FLOW_MODE, f->mode);
+
+	if (f->mask != ~0 || f->xor != 0) {
+		NLA_PUT_U32(skb, TCA_FLOW_MASK, f->mask);
+		NLA_PUT_U32(skb, TCA_FLOW_XOR, f->xor);
+	}
+	if (f->rshift)
+		NLA_PUT_U32(skb, TCA_FLOW_RSHIFT, f->rshift);
+	if (f->addend)
+		NLA_PUT_U32(skb, TCA_FLOW_ADDEND, f->addend);
+
+	if (f->divisor)
+		NLA_PUT_U32(skb, TCA_FLOW_DIVISOR, f->divisor);
+	if (f->baseclass)
+		NLA_PUT_U32(skb, TCA_FLOW_BASECLASS, f->baseclass);
+
+	if (tcf_exts_dump(skb, &f->exts, &flow_ext_map) < 0)
+		goto nla_put_failure;
+
+	if (f->ematches.hdr.nmatches &&
+	    tcf_em_tree_dump(skb, &f->ematches, TCA_FLOW_EMATCHES) < 0)
+		goto nla_put_failure;
+
+	nla_nest_end(skb, nest);
+
+	if (tcf_exts_dump_stats(skb, &f->exts, &flow_ext_map) < 0)
+		goto nla_put_failure;
+
+	return skb->len;
+
+nla_put_failure:
+	nlmsg_trim(skb, nest);
+	return -1;
+}
+
+static void flow_walk(struct tcf_proto *tp, struct tcf_walker *arg)
+{
+	struct flow_head *head = tp->root;
+	struct flow_filter *f;
+
+	list_for_each_entry(f, &head->filters, list) {
+		if (arg->count < arg->skip)
+			goto skip;
+		if (arg->fn(tp, (unsigned long)f, arg) < 0) {
+			arg->stop = 1;
+			break;
+		}
+skip:
+		arg->count++;
+	}
+}
+
+static struct tcf_proto_ops cls_flow_ops __read_mostly = {
+	.kind		= "flow",
+	.classify	= flow_classify,
+	.init		= flow_init,
+	.destroy	= flow_destroy,
+	.change		= flow_change,
+	.delete		= flow_delete,
+	.get		= flow_get,
+	.put		= flow_put,
+	.dump		= flow_dump,
+	.walk		= flow_walk,
+	.owner		= THIS_MODULE,
+};
+
+static int __init cls_flow_init(void)
+{
+	return register_tcf_proto_ops(&cls_flow_ops);
+}
+
+static void __exit cls_flow_exit(void)
+{
+	unregister_tcf_proto_ops(&cls_flow_ops);
+}
+
+module_init(cls_flow_init);
+module_exit(cls_flow_exit);
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
+MODULE_DESCRIPTION("TC flow classifier");

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[David Miller]

From: Patrick McHardy <kaber@trash.net>
Date: Thu, 31 Jan 2008 18:58:02 +0100 (MET)

> 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.

Applied, thanks Patrick.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Corey Hickey]

Patrick McHardy wrote:
> 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.

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

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Patrick McHardy]

Corey Hickey wrote:
> Patrick McHardy wrote:
>> 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.
> 
> 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?


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

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Corey Hickey]

Patrick McHardy wrote:
> 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

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Andy Furniss]

Patrick McHardy wrote:

> tc filter add dev eth0 protocol ip pref 1 parent 1: handle 1 \
>         flow hash keys dst divisor 1024
> 

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.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Patrick McHardy]

Andy Furniss wrote:
> Patrick McHardy wrote:
> 
>> tc filter add dev eth0 protocol ip pref 1 parent 1: handle 1 \
>>         flow hash keys dst divisor 1024
>>
> 
> 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?

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 ...

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Andy Furniss]

Patrick McHardy wrote:
> Andy Furniss wrote:
>> Patrick McHardy wrote:
>>
>>> tc filter add dev eth0 protocol ip pref 1 parent 1: handle 1 \
>>>         flow hash keys dst divisor 1024
>>>
>>
>> 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?
> 
> 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.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Andy Furniss]

Andy Furniss wrote:

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

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.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Patrick McHardy]

Andy Furniss wrote:
> Andy Furniss wrote:
> 
>> It's cool being able to see the sfq flows.
> 
> 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.


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 :)

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Andy Furniss]

Patrick McHardy wrote:
> Andy Furniss wrote:
>> Andy Furniss wrote:
>>
>>> It's cool being able to see the sfq flows.
>>
>> 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.
> 
> 
> 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.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Andy Furniss]

Andy Furniss wrote:

> 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.

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.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Patrick McHardy]

Andy Furniss wrote:
> Andy Furniss wrote:
> 
>> 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.
> 
> 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;
> +};

That doesn't matter, its promoted to a 32 bit value. But now
that you mention it, the SFQ patch for iproute I submitted
used a different type. Stephen has resynced it with the kernel
in the mean time, but you might be using the broken version.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Andy Furniss]

Patrick McHardy wrote:
> Andy Furniss wrote:

>> I notice allot is short (16bits?) in sfq but see
>>
>> +struct tc_sfq_xstats
>> +{
>> +    __s32        allot;
>> +};
> 
> That doesn't matter, its promoted to a 32 bit value. But now
> that you mention it, the SFQ patch for iproute I submitted
> used a different type. Stephen has resynced it with the kernel
> in the mean time, but you might be using the broken version.

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.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Andy Furniss]

Andy Furniss wrote:

> 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.

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.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Andy Furniss]

Andy Furniss wrote:
> Andy Furniss wrote:
> 
>> 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.
> 
> 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.

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

--- sch_sfq.c.orig      2008-04-07 11:42:36.000000000 +0100
+++ sch_sfq.c   2008-04-07 11:46:41.000000000 +0100
@@ -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.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Patrick McHardy]

Andy Furniss wrote:
> Andy Furniss wrote:
>> Andy Furniss wrote:
>>
>>> 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.
>>
>> 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.
> 
> Seems like this change fixes it for me, though I since noticed that 
> requeue will need the same change as well.
> 
> --- sch_sfq.c.orig      2008-04-07 11:42:36.000000000 +0100
> +++ sch_sfq.c   2008-04-07 11:46:41.000000000 +0100
> @@ -317,6 +317,7 @@
>                         q->next[x] = q->next[q->tail];
>                         q->next[q->tail] = x;
>                         q->tail = x;
> +                       q->allot[x] = 0;


That might fix the symptom, but I don't think its correct.
As I said, you can't simply reset to zero since it might cause
unfairness of bursty flows against non-bursty flows.

Re: [NET_SCHED 00/04]: External SFQ classifiers/flow classifier

[Andy Furniss]

Patrick McHardy wrote:
> Andy Furniss wrote:

>> --- sch_sfq.c.orig      2008-04-07 11:42:36.000000000 +0100
>> +++ sch_sfq.c   2008-04-07 11:46:41.000000000 +0100
>> @@ -317,6 +317,7 @@
>>                         q->next[x] = q->next[q->tail];
>>                         q->next[q->tail] = x;
>>                         q->tail = x;
>> +                       q->allot[x] = 0;
> 
> 
> That might fix the symptom, but I don't think its correct.
> As I said, you can't simply reset to zero since it might cause
> unfairness of bursty flows against non-bursty flows.

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.