Skip to contentSkip to conversation

ESFQ?

LARTC Justin Schoeman 6 participants 12 messages Jan 4, 2005 – Jan 12, 2005

Subsystems (2)
lore
Share & tools
lore
#1 lore raw

To the best of my knowledge, ESFQ for Linux is essentially dead. There's a patchset - QNet - which does port ESFQ to the 2.6.8/2.6.9 kernels, but ESFQ is not split out, so it looks like an all-or-nothing deal.

http://kem.p.lodz.pl/~peter/qnet/

I don't know if QNet is still being maintained - the last update on the page refers to October 2004 - and there's nothing to indicate how well the forward ports actually work in practice.

A search using Google shows only older ESFQ versions (one for 2.6.0-test11, for example) but nothing newer.

There was one posting about ESFQ to the kernel developers mailing list, but I couldn't see any follow-ups to it. Nor does it appear to be in Andrew Morton's patchset (an excellent indicator of interest level and the probability of ending up in the official kernel).

Unfortunately, this seems to be fairly common in Linux QoS - too many one-man projects and too few resources too keep them going.

Quoted 9 lines · --- Justin Schoeman

Hi again,

I was just looking around for ESFQ sources, and I
see that the main site
is down, and only has kernel 2.6.4 patches.

Is ESFQ maintained? If so, where can I find patches for 2.6.10?

Quoted 7 lines

Thanks,
-justin
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO:
http://lartc.org/

__________________________________
Do you Yahoo!?
Yahoo! Mail - You care about security. So do we.
http://promotions.yahoo.com/new_mail
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#2 lore raw
In reply to Justin Schoeman

Ouch... Is there any other way to do host-based fair sharing (well, other than actually classifying each host :-( )?

Thanks,
-justin

Quoted 52 lines · Jonathan Day

To the best of my knowledge, ESFQ for Linux is essentially dead. There's a patchset - QNet - which does port ESFQ to the 2.6.8/2.6.9 kernels, but ESFQ is not split out, so it looks like an all-or-nothing deal.

http://kem.p.lodz.pl/~peter/qnet/

I don't know if QNet is still being maintained - the last update on the page refers to October 2004 - and there's nothing to indicate how well the forward ports actually work in practice.

A search using Google shows only older ESFQ versions (one for 2.6.0-test11, for example) but nothing newer.

There was one posting about ESFQ to the kernel developers mailing list, but I couldn't see any follow-ups to it. Nor does it appear to be in Andrew Morton's patchset (an excellent indicator of interest level and the probability of ending up in the official kernel).

Unfortunately, this seems to be fairly common in Linux QoS - too many one-man projects and too few resources too keep them going.

Quoted 9 lines · --- Justin Schoeman

Hi again,

I was just looking around for ESFQ sources, and I
see that the main site
is down, and only has kernel 2.6.4 patches.

Is ESFQ maintained? If so, where can I find patches for 2.6.10?

Quoted 7 lines

Thanks,
-justin
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO:
http://lartc.org/

Quoted 4 lines

__________________________________
Do you Yahoo!?
Yahoo! Mail - You care about security. So do we.
http://promotions.yahoo.com/new_mail

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#3 lore raw
In reply to Justin Schoeman
Quoted 2 lines · Justin Schoeman

Ouch... Is there any other way to do host-based fair sharing (well, other than actually classifying each host :-( )?

I don't think it will take much to get it to work - though I haven't tried :-) .

I'll have a look at doing a 2.6.10 in the next few days.

Andy.

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#4 lore raw
In reply to Justin Schoeman

Woohoo - that would be great!

-justin

Quoted 9 lines · Andy Furniss
Quoted 2 lines · Justin Schoeman

Ouch... Is there any other way to do host-based fair sharing (well, other than actually classifying each host :-( )?

I don't think it will take much to get it to work - though I haven't tried :-) .

Quoted 8 lines

I'll have a look at doing a 2.6.10 in the next few days.

Andy.

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#5 lore raw
In reply to Justin Schoeman
Quoted 15 lines · Justin Schoeman

Woohoo - that would be great!

-justin

Quoted 9 lines · Andy Furniss
Quoted 1 line · Justin Schoeman

Ouch... Is there any other way to do host-based fair sharing (well, other than actually classifying each host :-( )?

I don't think it will take much to get it to work - though I haven't tried :-) .

I'll have a look at doing a 2.6.10 in the next few days.

Well I gave it a go (first patches I've made) and they work for me though Thomas or Stephen may notice something :-) .

Hopefully they won't be needed in the future if Thomas gets esfq in mainline.

They are based on Alexander Clouters patches at www.digriz.org.uk. I only used the first iproute one.

I was hampered a bit because kernel.org have turned off the diff viewer.

The remove db iproute patch is from LFS, you may not need it if you have Berkley DB installed ( search for db_185.h ).

If you don't have it *and* you don't use arpd then use the patch, it just removes arpd from the build.

Andy.

include/linux/pkt_sched.h +10 -0
diff -urN iproute2-2.6.9.orig/include/linux/pkt_sched.h iproute2-2.6.9/include/linux/pkt_sched.h
@@ -126,6 +126,13 @@
 
 /* SFQ section */
 
+enum
+{
+	TCA_SFQ_HASH_CLASSIC,
+	TCA_SFQ_HASH_DST,
+	TCA_SFQ_HASH_SRC,
+};
+
 struct tc_sfq_qopt
 {
 	unsigned	quantum;	/* Bytes per round allocated to flow */
@@ -133,6 +140,7 @@
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
+	unsigned	hash_kind;	/* Hash function to use for flow identification */
 };
 
 /*
@@ -142,6 +150,8 @@
  *
  *	The only reason for this is efficiency, it is possible
  *	to change these parameters in compile time.
+ *
+ *	If you need to play with this values use esfq
  */
 
 /* RED section */
tc/Makefile +1 -0
diff -urN iproute2-2.6.9.orig/tc/Makefile iproute2-2.6.9/tc/Makefile
@@ -6,6 +6,7 @@
 TCMODULES :=
 TCMODULES += q_fifo.o
 TCMODULES += q_sfq.o
+TCMODULES += q_esfq.o
 TCMODULES += q_red.o
 TCMODULES += q_prio.o
 TCMODULES += q_tbf.o
tc/q_esfq.c +168 -0

168 lines not on this page · raw message

include/linux/pkt_sched.h +10 -0
diff -urN linux-2.6.10.orig/include/linux/pkt_sched.h linux-2.6.10/include/linux/pkt_sched.h
@@ -129,6 +129,13 @@
 
 /* SFQ section */
 
+enum
+{
+	TCA_SFQ_HASH_CLASSIC,
+	TCA_SFQ_HASH_DST,
+	TCA_SFQ_HASH_SRC,
+};
+
 struct tc_sfq_qopt
 {
 	unsigned	quantum;	/* Bytes per round allocated to flow */
@@ -136,6 +143,7 @@
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
+	unsigned	hash_kind;	/* Hash function to use for flow identification */
 };
 
 /*
@@ -145,6 +153,8 @@
  *
  *	The only reason for this is efficiency, it is possible
  *	to change these parameters in compile time.
+ *	
+ *	If you need to play with this values use esfq.
  */
 
 /* RED section */
net/sched/Kconfig +18 -0
diff -urN linux-2.6.10.orig/net/sched/Kconfig linux-2.6.10/net/sched/Kconfig
@@ -154,6 +154,24 @@
 	  To compile this code as a module, choose M here: the
 	  module will be called sch_sfq.
 
+config NET_SCH_ESFQ
+	tristate "ESFQ queue"
+	depends on NET_SCHED
+	---help---
+	  Say Y here if you want to use the Enhanced Stochastic Fairness
+	  Queueing (ESFQ) packet scheduling algorithm for some of your network
+	  devices or as a leaf discipline for the CBQ scheduling algorithm (see
+	  the top of <file:net/sched/sch_esfq.c> for details and references
+	  about the SFQ algorithm).
+	  
+	  This is an enchanced SFQ version which allows you to control the
+	  hardcoded values in the SFQ scheduler: queue depth, hash table size,
+	  queues limit. Also adds control to the hash function used to identify
+	  packet flows. Hash by src or dst ip and original sfq hash.
+	  
+	  To compile this code as a module, choose M here: the
+	  module will be called sch_esfq.
+
 config NET_SCH_TEQL
 	tristate "TEQL queue"
 	depends on NET_SCHED
net/sched/Makefile +1 -0
diff -urN linux-2.6.10.orig/net/sched/Makefile linux-2.6.10/net/sched/Makefile
@@ -22,6 +22,7 @@
 obj-$(CONFIG_NET_SCH_INGRESS)	+= sch_ingress.o 
 obj-$(CONFIG_NET_SCH_DSMARK)	+= sch_dsmark.o
 obj-$(CONFIG_NET_SCH_SFQ)	+= sch_sfq.o
+obj-$(CONFIG_NET_SCH_ESFQ)	+= sch_esfq.o
 obj-$(CONFIG_NET_SCH_TBF)	+= sch_tbf.o
 obj-$(CONFIG_NET_SCH_TEQL)	+= sch_teql.o
 obj-$(CONFIG_NET_SCH_PRIO)	+= sch_prio.o
net/sched/sch_esfq.c +585 -0

585 lines not on this page · raw message

Submitted By: Jeremy Utley <[email protected]>
Date: 2004-11-04
Initial Package Version: 2.6.9-041019
Upstream Status - Not submitted - LFS Specific
Origin: Based on inital work by Jim Gifford, ported to apply to the latest version
Description: Disables compilation of the arpd program, which requres Berkley DB.

misc/Makefile +1 -4
diff -Naur iproute2-2.6.9/misc/Makefile iproute2-2.6.9-new/misc/Makefile
@@ -1,7 +1,7 @@
 SSOBJ=ss.o ssfilter.o
 LNSTATOBJ=lnstat.o lnstat_util.o
 
-TARGETS=ss nstat ifstat rtacct arpd lnstat
+TARGETS=ss nstat ifstat rtacct lnstat
 
 include ../Config
 
@@ -18,9 +18,6 @@
 rtacct: rtacct.c
 	$(CC) $(CFLAGS) $(LDFLAGS) -o rtacct rtacct.c $(LIBNETLINK) -lm
 
-arpd: arpd.c
-	$(CC) $(CFLAGS) -I$(DBM_INCLUDE) $(LDFLAGS) -o arpd arpd.c $(LIBNETLINK) -ldb -lpthread
-
 ssfilter.c: ssfilter.y
 	bison ssfilter.y -o ssfilter.c
 
#6 lore raw
In reply to Justin Schoeman

Cheers Andy, great work.

Brian

Quoted 41 lines · Andy Furniss
Quoted 17 lines · Justin Schoeman

Woohoo - that would be great!

-justin

Quoted 11 lines · Andy Furniss
Quoted 2 lines · Justin Schoeman

Ouch... Is there any other way to do host-based fair sharing (well, other than actually classifying each host :-( )?

I don't think it will take much to get it to work - though I haven't tried :-) .

I'll have a look at doing a 2.6.10 in the next few days.

Well I gave it a go (first patches I've made) and they work for me though Thomas or Stephen may notice something :-) .

Hopefully they won't be needed in the future if Thomas gets esfq in mainline.

They are based on Alexander Clouters patches at www.digriz.org.uk. I only used the first iproute one.

I was hampered a bit because kernel.org have turned off the diff viewer.

The remove db iproute patch is from LFS, you may not need it if you have Berkley DB installed ( search for db_185.h ).

If you don't have it *and* you don't use arpd then use the patch, it just removes arpd from the build.

Andy.

Signature · 8 lines
Brian Carrig
Research Assistant
Department of Computing & Networking
Institute of Technology, Carlow
Tel. No.: +353 59 9176314
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
#7 lore raw
In reply to Justin Schoeman

Thanks - really appreciate the help!
-justin

Quoted 951 lines · Andy Furniss
Quoted 18 lines · Justin Schoeman

Woohoo - that would be great!

-justin

Quoted 12 lines · Andy Furniss
Quoted 2 lines · Justin Schoeman

Ouch... Is there any other way to do host-based fair sharing (well, other than actually classifying each host :-( )?

I don't think it will take much to get it to work - though I haven't tried :-) .

I'll have a look at doing a 2.6.10 in the next few days.

Well I gave it a go (first patches I've made) and they work for me though Thomas or Stephen may notice something :-) .

Hopefully they won't be needed in the future if Thomas gets esfq in mainline.

They are based on Alexander Clouters patches at www.digriz.org.uk. I only used the first iproute one.

I was hampered a bit because kernel.org have turned off the diff viewer.

The remove db iproute patch is from LFS, you may not need it if you have Berkley DB installed ( search for db_185.h ).

If you don't have it *and* you don't use arpd then use the patch, it just removes arpd from the build.

Andy.

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

diff -urN iproute2-2.6.9.orig/include/linux/pkt_sched.h iproute2-2.6.9/include/linux/pkt_sched.h

include/linux/pkt_sched.h +10 -0
@@ -126,6 +126,13 @@
 
 /* SFQ section */
 
+enum
+{
+	TCA_SFQ_HASH_CLASSIC,
+	TCA_SFQ_HASH_DST,
+	TCA_SFQ_HASH_SRC,
+};
+
 struct tc_sfq_qopt
 {
 	unsigned	quantum;	/* Bytes per round allocated to flow */
@@ -133,6 +140,7 @@
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
+	unsigned	hash_kind;	/* Hash function to use for flow identification */
 };
 
 /*
@@ -142,6 +150,8 @@
  *
  *	The only reason for this is efficiency, it is possible
  *	to change these parameters in compile time.
+ *
+ *	If you need to play with this values use esfq
  */
 
 /* RED section */

diff -urN iproute2-2.6.9.orig/tc/Makefile iproute2-2.6.9/tc/Makefile

tc/Makefile +1 -0
@@ -6,6 +6,7 @@
 TCMODULES :>  TCMODULES += q_fifo.o
 TCMODULES += q_sfq.o
+TCMODULES += q_esfq.o
 TCMODULES += q_red.o
 TCMODULES += q_prio.o
 TCMODULES += q_tbf.o

diff -urN iproute2-2.6.9.orig/tc/q_esfq.c iproute2-2.6.9/tc/q_esfq.c

tc/q_esfq.c +168 -1
@@ -0,0 +1,168 @@
+/*
+ * q_esfq.c		ESFQ.
+ *
+ *		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.
+ *
+ * Authors:	Alexey Kuznetsov, <[email protected]>
+ *
+ * Changes:	Alexander Atanasov, <[email protected]>
+ *		Added depth,limit,divisor,hash_kind options.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <syslog.h>
+#include <fcntl.h>
+#include <math.h> 
+#include <sys/socket.h>
+#include <netinet/in.h>
+#include <arpa/inet.h>
+#include <string.h>
+
+#include "utils.h"
+#include "tc_util.h"
+
+static void explain(void)
+{
+	fprintf(stderr, "Usage: ... esfq [ perturb SECS ] [ quantum BYTES ] [ depth FLOWS ]\n\t[ divisor HASHBITS ] [ limit PKTS ] [ hash HASHTYPE]\n");
+	fprintf(stderr,"Where: \n");
+	fprintf(stderr,"HASHTYPE := { classic | src | dst }\n");
+}
+
+#define usage() return(-1)
+
+static int esfq_parse_opt(struct qdisc_util *qu, int argc, char **argv, struct nlmsghdr *n)
+{
+	int ok=0;
+	struct tc_sfq_qopt opt;
+
+	memset(&opt, 0, sizeof(opt));
+
+	opt.hash_kind= TCA_SFQ_HASH_CLASSIC;
+	
+	while (argc > 0) {
+		if (strcmp(*argv, "quantum") = 0) {
+			NEXT_ARG();
+			if (get_size(&opt.quantum, *argv)) {
+				fprintf(stderr, "Illegal \"quantum\"\n");
+				return -1;
+			}
+			ok++;
+		} else if (strcmp(*argv, "perturb") = 0) {
+			NEXT_ARG();
+			if (get_integer(&opt.perturb_period, *argv, 0)) {
+				fprintf(stderr, "Illegal \"perturb\"\n");
+				return -1;
+			}
+			ok++;
+		} else if (strcmp(*argv, "depth") = 0) {
+			NEXT_ARG();
+			if (get_integer(&opt.flows, *argv, 0)) {
+				fprintf(stderr, "Illegal \"depth\"\n");
+				return -1;
+			}
+			ok++;
+		} else if (strcmp(*argv, "divisor") = 0) {
+			NEXT_ARG();
+			if (get_integer(&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=pow(2,opt.divisor);
+			ok++;
+		} else if (strcmp(*argv, "limit") = 0) {
+			NEXT_ARG();
+			if (get_integer(&opt.limit, *argv, 0)) {
+				fprintf(stderr, "Illegal \"limit\"\n");
+				return -1;
+			}
+			ok++;
+		} else if (strcmp(*argv, "hash") = 0) {
+			NEXT_ARG();
+			if(strcmp(*argv,"classic") = 0) {
+				opt.hash_kind= TCA_SFQ_HASH_CLASSIC;
+			} else 
+			if(strcmp(*argv,"dst") = 0) {
+				opt.hash_kind= TCA_SFQ_HASH_DST;
+			} else
+			if(strcmp(*argv,"src") = 0) {
+				opt.hash_kind= TCA_SFQ_HASH_SRC;
+			} else {
+				fprintf(stderr, "Illegal \"hash\"\n");
+				explain();
+				return -1;
+			}
+			ok++;
+		} else if (strcmp(*argv, "help") = 0) {
+			explain();
+			return -1;
+		} else {
+			fprintf(stderr, "What is \"%s\"?\n", *argv);
+			explain();
+			return -1;
+		}
+		argc--; argv++;
+	}
+
+	if (ok)
+		addattr_l(n, 1024, TCA_OPTIONS, &opt, sizeof(opt));
+	return 0;
+}
+
+static int esfq_print_opt(struct qdisc_util *qu, FILE *f, struct rtattr *opt)
+{
+	struct tc_sfq_qopt *qopt;
+	SPRINT_BUF(b1);
+
+	if (opt = NULL)
+		return 0;
+
+	if (RTA_PAYLOAD(opt)  < sizeof(*qopt))
+		return -1;
+	qopt = RTA_DATA(opt);
+	fprintf(f, "quantum %s ", sprint_size(qopt->quantum, b1));
+	if (show_details) {
+		fprintf(f, "limit %up flows %u/%u ",
+			qopt->limit, qopt->flows, qopt->divisor);
+	}
+	if (qopt->perturb_period)
+		fprintf(f, "perturb %dsec ", qopt->perturb_period);
+
+		fprintf(f,"hash: ");
+	switch(qopt->hash_kind)
+	{
+	case TCA_SFQ_HASH_CLASSIC:
+		fprintf(f,"classic");
+		break;
+	case TCA_SFQ_HASH_DST:
+		fprintf(f,"dst");
+		break;
+	case TCA_SFQ_HASH_SRC:
+		fprintf(f,"src");
+		break;
+	default:
+		fprintf(f,"Unknown");
+	}
+	return 0;
+}
+
+static int esfq_print_xstats(struct qdisc_util *qu, FILE *f, struct rtattr *xstats)
+{
+	return 0;
+}
+
+
+struct qdisc_util esfq_qdisc_util = {
+	.id		= "esfq",
+	.parse_qopt	= esfq_parse_opt,
+	.print_qopt	= esfq_print_opt,
+	.print_xstats	= esfq_print_xstats,
+};
 
 
------------------------------------------------------------------------

diff -urN linux-2.6.10.orig/include/linux/pkt_sched.h linux-2.6.10/include/linux/pkt_sched.h

include/linux/pkt_sched.h +10 -0
@@ -129,6 +129,13 @@
 
 /* SFQ section */
 
+enum
+{
+	TCA_SFQ_HASH_CLASSIC,
+	TCA_SFQ_HASH_DST,
+	TCA_SFQ_HASH_SRC,
+};
+
 struct tc_sfq_qopt
 {
 	unsigned	quantum;	/* Bytes per round allocated to flow */
@@ -136,6 +143,7 @@
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
+	unsigned	hash_kind;	/* Hash function to use for flow identification */
 };
 
 /*
@@ -145,6 +153,8 @@
  *
  *	The only reason for this is efficiency, it is possible
  *	to change these parameters in compile time.
+ *	
+ *	If you need to play with this values use esfq.
  */
 
 /* RED section */

diff -urN linux-2.6.10.orig/net/sched/Kconfig linux-2.6.10/net/sched/Kconfig

net/sched/Kconfig +18 -0
@@ -154,6 +154,24 @@
 	  To compile this code as a module, choose M here: the
 	  module will be called sch_sfq.
 
+config NET_SCH_ESFQ
+	tristate "ESFQ queue"
+	depends on NET_SCHED
+	---help---
+	  Say Y here if you want to use the Enhanced Stochastic Fairness
+	  Queueing (ESFQ) packet scheduling algorithm for some of your network
+	  devices or as a leaf discipline for the CBQ scheduling algorithm (see
+	  the top of <file:net/sched/sch_esfq.c> for details and references
+	  about the SFQ algorithm).
+	  
+	  This is an enchanced SFQ version which allows you to control the
+	  hardcoded values in the SFQ scheduler: queue depth, hash table size,
+	  queues limit. Also adds control to the hash function used to identify
+	  packet flows. Hash by src or dst ip and original sfq hash.
+	  
+	  To compile this code as a module, choose M here: the
+	  module will be called sch_esfq.
+
 config NET_SCH_TEQL
 	tristate "TEQL queue"
 	depends on NET_SCHED

diff -urN linux-2.6.10.orig/net/sched/Makefile linux-2.6.10/net/sched/Makefile

net/sched/Makefile +1 -0
@@ -22,6 +22,7 @@
 obj-$(CONFIG_NET_SCH_INGRESS)	+= sch_ingress.o 
 obj-$(CONFIG_NET_SCH_DSMARK)	+= sch_dsmark.o
 obj-$(CONFIG_NET_SCH_SFQ)	+= sch_sfq.o
+obj-$(CONFIG_NET_SCH_ESFQ)	+= sch_esfq.o
 obj-$(CONFIG_NET_SCH_TBF)	+= sch_tbf.o
 obj-$(CONFIG_NET_SCH_TEQL)	+= sch_teql.o
 obj-$(CONFIG_NET_SCH_PRIO)	+= sch_prio.o

diff -urN linux-2.6.10.orig/net/sched/sch_esfq.c linux-2.6.10/net/sched/sch_esfq.c

net/sched/sch_esfq.c +584 -1
@@ -0,0 +1,585 @@
+/*
+ * net/sched/sch_esfq.c	Extended Stochastic Fairness Queueing discipline.
+ *
+ *		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.
+ *
+ * Authors:	Alexey Kuznetsov, <[email protected]>
+ *
+ * Changes:	Alexander Atanasov, <[email protected]>
+ *		Added dynamic depth,limit,divisor,hash_kind options.
+ *		Added dst and src hashes.
+ */
+
+#include <linux/config.h>
+#include <linux/module.h>
+#include <asm/uaccess.h>
+#include <asm/system.h>
+#include <asm/bitops.h>
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/jiffies.h>
+#include <linux/string.h>
+#include <linux/mm.h>
+#include <linux/socket.h>
+#include <linux/sockios.h>
+#include <linux/in.h>
+#include <linux/errno.h>
+#include <linux/interrupt.h>
+#include <linux/if_ether.h>
+#include <linux/inet.h>
+#include <linux/netdevice.h>
+#include <linux/etherdevice.h>
+#include <linux/notifier.h>
+#include <linux/init.h>
+#include <net/ip.h>
+#include <linux/ipv6.h>
+#include <net/route.h>
+#include <linux/skbuff.h>
+#include <net/sock.h>
+#include <net/pkt_sched.h>
+
+
+/*	Stochastic Fairness Queuing algorithm.
+	For more comments look at sch_sfq.c.
+	The difference is that you can change limit, depth,
+	hash table size and choose 3 hash types.
+	
+	classic:	same as in sch_sfq.c
+	dst:		destination IP address
+	src:		source IP address
+	
+	TODO: 
+		make sfq_change work.
+*/
+
+
+/* This type should contain at least SFQ_DEPTH*2 values */
+typedef unsigned int esfq_index;
+
+struct esfq_head
+{
+	esfq_index	next;
+	esfq_index	prev;
+};
+
+struct esfq_sched_data
+{
+/* Parameters */
+	int		perturb_period;
+	unsigned	quantum;	/* Allotment per round: MUST BE >= MTU */
+	int		limit;
+	unsigned	depth;
+	unsigned	hash_divisor;
+	unsigned	hash_kind;
+/* Variables */
+	struct timer_list perturb_timer;
+	int		perturbation;
+	esfq_index	tail;		/* Index of current slot in round */
+	esfq_index	max_depth;	/* Maximal depth */
+
+	esfq_index	*ht;			/* Hash table */
+	esfq_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 esfq_head	*dep;		/* Linked list of slots, indexed by depth */
+};
+
+static __inline__ unsigned esfq_hash_u32(struct esfq_sched_data *q,u32 h)
+{
+	int pert = q->perturbation;
+
+	if (pert)
+		h = (h<<pert) ^ (h>>(0x1F - pert));
+
+	h = ntohl(h) * 2654435761UL;
+	return h & (q->hash_divisor-1);
+}
+
+static __inline__ unsigned esfq_fold_hash_classic(struct esfq_sched_data *q, u32 h, u32 h1)
+{
+	int pert = q->perturbation;
+
+	/* Have we any rotation primitives? If not, WHY? */
+	h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
+	h ^= h>>10;
+	return h & (q->hash_divisor-1);
+}
+
+static unsigned esfq_hash(struct esfq_sched_data *q, struct sk_buff *skb)
+{
+	u32 h, h2;
+	u32 hs;
+
+	switch (skb->protocol) {
+	case __constant_htons(ETH_P_IP):
+	{
+		struct iphdr *iph = skb->nh.iph;
+		h = iph->daddr;
+		hs = iph->saddr;
+		h2 = hs^iph->protocol;
+		if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
+		    (iph->protocol = IPPROTO_TCP ||
+		     iph->protocol = IPPROTO_UDP ||
+		     iph->protocol = IPPROTO_ESP))
+			h2 ^= *(((u32*)iph) + iph->ihl);
+		break;
+	}
+	case __constant_htons(ETH_P_IPV6):
+	{
+		struct ipv6hdr *iph = skb->nh.ipv6h;
+		h = iph->daddr.s6_addr32[3];
+		hs = iph->saddr.s6_addr32[3];
+		h2 = hs^iph->nexthdr;
+		if (iph->nexthdr = IPPROTO_TCP ||
+		    iph->nexthdr = IPPROTO_UDP ||
+		    iph->nexthdr = IPPROTO_ESP)
+			h2 ^= *(u32*)&iph[1];
+		break;
+	}
+	default:
+		h = (u32)(unsigned long)skb->dst;
+		hs = (u32)(unsigned long)skb->sk;
+		h2 = hs^skb->protocol;
+	}
+	switch(q->hash_kind)
+	{
+	case TCA_SFQ_HASH_CLASSIC:
+		return esfq_fold_hash_classic(q, h, h2);
+	case TCA_SFQ_HASH_DST:
+		return esfq_hash_u32(q,h);
+	case TCA_SFQ_HASH_SRC:
+		return esfq_hash_u32(q,hs);
+	default:
+		if (net_ratelimit())
+			printk(KERN_DEBUG "esfq unknown hash method, fallback to classic\n");
+	}
+	return esfq_fold_hash_classic(q, h, h2);
+}
+
+static inline void esfq_link(struct esfq_sched_data *q, esfq_index x)
+{
+	esfq_index p, n;
+	int d = q->qs[x].qlen + q->depth;
+
+	p = d;
+	n = q->dep[d].next;
+	q->dep[x].next = n;
+	q->dep[x].prev = p;
+	q->dep[p].next = q->dep[n].prev = x;
+}
+
+static inline void esfq_dec(struct esfq_sched_data *q, esfq_index x)
+{
+	esfq_index p, n;
+
+	n = q->dep[x].next;
+	p = q->dep[x].prev;
+	q->dep[p].next = n;
+	q->dep[n].prev = p;
+
+	if (n = p && q->max_depth = q->qs[x].qlen + 1)
+		q->max_depth--;
+
+	esfq_link(q, x);
+}
+
+static inline void esfq_inc(struct esfq_sched_data *q, esfq_index x)
+{
+	esfq_index p, n;
+	int d;
+
+	n = q->dep[x].next;
+	p = q->dep[x].prev;
+	q->dep[p].next = n;
+	q->dep[n].prev = p;
+	d = q->qs[x].qlen;
+	if (q->max_depth < d)
+		q->max_depth = d;
+
+	esfq_link(q, x);
+}
+
+static unsigned int esfq_drop(struct Qdisc *sch)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	esfq_index d = q->max_depth;
+	struct sk_buff *skb;
+	unsigned int len;
+
+	/* Queue is full! Find the longest slot and
+	   drop a packet from it */
+
+	if (d > 1) {
+		esfq_index x = q->dep[d+q->depth].next;
+		skb = q->qs[x].prev;
+		len = skb->len;
+		__skb_unlink(skb, &q->qs[x]);
+		kfree_skb(skb);
+		esfq_dec(q, x);
+		sch->q.qlen--;
+		sch->qstats.drops++;
+		return len;
+	}
+
+	if (d = 1) {
+		/* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
+		d = q->next[q->tail];
+		q->next[q->tail] = q->next[d];
+		q->allot[q->next[d]] += q->quantum;
+		skb = q->qs[d].prev;
+		len = skb->len;
+		__skb_unlink(skb, &q->qs[d]);
+		kfree_skb(skb);
+		esfq_dec(q, d);
+		sch->q.qlen--;
+		q->ht[q->hash[d]] = q->depth;
+		sch->qstats.drops++;
+		return len;
+	}
+
+	return 0;
+}
+
+static int
+esfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	unsigned hash = esfq_hash(q, skb);
+	unsigned depth = q->depth;
+	esfq_index x;
+
+	x = q->ht[hash];
+	if (x = depth) {
+		q->ht[hash] = x = q->dep[depth].next;
+		q->hash[x] = hash;
+	}
+	__skb_queue_tail(&q->qs[x], skb);
+	esfq_inc(q, x);
+	if (q->qs[x].qlen = 1) {		/* The flow is new */
+		if (q->tail = 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-1) {
+		sch->bstats.bytes += skb->len;
+		sch->bstats.packets++;
+		return 0;
+	}
+
+	esfq_drop(sch);
+	return NET_XMIT_CN;
+}
+
+static int
+esfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	unsigned hash = esfq_hash(q, skb);
+	unsigned depth = q->depth;
+	esfq_index x;
+
+	x = q->ht[hash];
+	if (x = depth) {
+		q->ht[hash] = x = q->dep[depth].next;
+		q->hash[x] = hash;
+	}
+	__skb_queue_head(&q->qs[x], skb);
+	esfq_inc(q, x);
+	if (q->qs[x].qlen = 1) {		/* The flow is new */
+		if (q->tail = 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 - 1) {
+		sch->qstats.requeues++;
+		return 0;
+	}
+
+	sch->qstats.drops++;
+	esfq_drop(sch);
+	return NET_XMIT_CN;
+}
+
+
+
+
+static struct sk_buff *
+esfq_dequeue(struct Qdisc* sch)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	struct sk_buff *skb;
+	unsigned depth = q->depth;
+	esfq_index a, old_a;
+
+	/* No active slots */
+	if (q->tail = depth)
+		return NULL;
+
+	a = old_a = q->next[q->tail];
+
+	/* Grab packet */
+	skb = __skb_dequeue(&q->qs[a]);
+	esfq_dec(q, a);
+	sch->q.qlen--;
+
+	/* Is the slot empty? */
+	if (q->qs[a].qlen = 0) {
+		q->ht[q->hash[a]] = depth;
+		a = q->next[a];
+		if (a = old_a) {
+			q->tail = depth;
+			return skb;
+		}
+		q->next[q->tail] = a;
+		q->allot[a] += q->quantum;
+	} else if ((q->allot[a] -= skb->len) <= 0) {
+		q->tail = a;
+		a = q->next[a];
+		q->allot[a] += q->quantum;
+	}
+
+	return skb;
+}
+
+static void
+esfq_reset(struct Qdisc* sch)
+{
+	struct sk_buff *skb;
+
+	while ((skb = esfq_dequeue(sch)) != NULL)
+		kfree_skb(skb);
+}
+
+static void esfq_perturbation(unsigned long arg)
+{
+	struct Qdisc *sch = (struct Qdisc*)arg;
+	struct esfq_sched_data *q = qdisc_priv(sch);
+
+	q->perturbation = net_random()&0x1F;
+	q->perturb_timer.expires = jiffies + q->perturb_period;
+
+	if (q->perturb_period) {
+		q->perturb_timer.expires = jiffies + q->perturb_period;
+		add_timer(&q->perturb_timer);
+	}
+}
+
+static int esfq_change(struct Qdisc *sch, struct rtattr *opt)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	struct tc_sfq_qopt *ctl = RTA_DATA(opt);
+	int old_perturb = q->perturb_period;
+
+	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;
+//	q->hash_divisor = ctl->divisor;
+//	q->tail = q->limit = q->depth = ctl->flows;
+
+	if (ctl->limit)
+		q->limit = min_t(u32, ctl->limit, q->depth);
+	
+	if (ctl->hash_kind) {
+		q->hash_kind = ctl->hash_kind;
+		if (q->hash_kind !=  TCA_SFQ_HASH_CLASSIC)
+			q->perturb_period = 0;
+	}
+	
+	// is sch_tree_lock enough to do this ?
+	while (sch->q.qlen >= q->limit-1)
+		esfq_drop(sch);
+	
+	if (old_perturb)
+		del_timer(&q->perturb_timer);
+	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 esfq_init(struct Qdisc *sch, struct rtattr *opt)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	struct tc_sfq_qopt *ctl;
+	esfq_index p = ~0UL/2;
+	int i;
+	
+	if (opt && opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
+		return -EINVAL;
+
+	init_timer(&q->perturb_timer);
+	q->perturb_timer.data = (unsigned long)sch;
+	q->perturb_timer.function = esfq_perturbation;
+	q->perturbation = 0;
+	q->hash_kind = TCA_SFQ_HASH_CLASSIC;
+	q->max_depth = 0;
+	if (opt = NULL) {
+		q->quantum = psched_mtu(sch->dev);
+		q->perturb_period = 0;
+		q->hash_divisor = 1024;
+		q->tail = q->limit = q->depth = 128;
+		
+	} else {
+		ctl = RTA_DATA(opt);
+		q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
+		q->perturb_period = ctl->perturb_period*HZ;
+		q->hash_divisor = ctl->divisor ? : 1024;
+		q->tail = q->limit = q->depth = ctl->flows ? : 128;
+		
+		if ( q->depth > p - 1 )
+			return -EINVAL;
+		
+		if (ctl->limit)
+			q->limit = min_t(u32, ctl->limit, q->depth);
+		
+		if (ctl->hash_kind) {
+			q->hash_kind = ctl->hash_kind;
+		}
+		
+		if (q->perturb_period) {
+			q->perturb_timer.expires = jiffies + q->perturb_period;
+			add_timer(&q->perturb_timer);
+		}
+	}
+	
+	q->ht = kmalloc(q->hash_divisor*sizeof(esfq_index), GFP_KERNEL);
+	if (!q->ht)
+		goto err_case;
+		
+	q->dep = kmalloc((1+q->depth*2)*sizeof(struct esfq_head), GFP_KERNEL);
+	if (!q->dep)
+		goto err_case;
+	q->next = kmalloc(q->depth*sizeof(esfq_index), GFP_KERNEL);
+	if (!q->next)
+		goto err_case;
+	
+	q->allot = kmalloc(q->depth*sizeof(short), GFP_KERNEL);
+	if (!q->allot)
+		goto err_case;
+	q->hash = kmalloc(q->depth*sizeof(unsigned short), GFP_KERNEL);
+	if (!q->hash)
+		goto err_case;
+	q->qs = kmalloc(q->depth*sizeof(struct sk_buff_head), GFP_KERNEL);
+	if (!q->qs)
+		goto err_case;
+	
+	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]);
+		q->dep[i+q->depth].next = i+q->depth;
+		q->dep[i+q->depth].prev = i+q->depth;
+	}
+	
+	for (i=0; i<q->depth; i++)
+		esfq_link(q, i);
+	return 0;
+err_case:
+	if (q->ht)
+		kfree(q->ht);
+	if (q->dep)
+		kfree(q->dep);
+	if (q->next)
+		kfree(q->next);
+	if (q->allot)
+		kfree(q->allot);
+	if (q->hash)
+		kfree(q->hash);
+	if (q->qs)
+		kfree(q->qs);
+	return -ENOBUFS;
+}
+
+static void esfq_destroy(struct Qdisc *sch)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	del_timer(&q->perturb_timer);
+	if(q->ht)
+		kfree(q->ht);
+	if(q->dep)
+		kfree(q->dep);
+	if(q->next)
+		kfree(q->next);
+	if(q->allot)
+		kfree(q->allot);
+	if(q->hash)
+		kfree(q->hash);
+	if(q->qs)
+		kfree(q->qs);
+}
+
+static int esfq_dump(struct Qdisc *sch, struct sk_buff *skb)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	unsigned char	 *b = skb->tail;
+	struct tc_sfq_qopt opt;
+
+	opt.quantum = q->quantum;
+	opt.perturb_period = q->perturb_period/HZ;
+
+	opt.limit = q->limit;
+	opt.divisor = q->hash_divisor;
+	opt.flows = q->depth;
+	opt.hash_kind = q->hash_kind;
+
+	RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
+
+	return skb->len;
+
+rtattr_failure:
+	skb_trim(skb, b - skb->data);
+	return -1;
+}
+
+static struct Qdisc_ops esfq_qdisc_ops > +{
+	.next		=	NULL,
+	.cl_ops		=	NULL,
+	.id		=	"esfq",
+	.priv_size	=	sizeof(struct esfq_sched_data),
+	.enqueue	=	esfq_enqueue,
+	.dequeue	=	esfq_dequeue,
+	.requeue	=	esfq_requeue,
+	.drop		=	esfq_drop,
+	.init		=	esfq_init,
+	.reset		=	esfq_reset,
+	.destroy	=	esfq_destroy,
+	.change		=	NULL, /* esfq_change - needs more work */
+	.dump		=	esfq_dump,
+	.owner		=	THIS_MODULE,
+};
+
+static int __init esfq_module_init(void)
+{
+	return register_qdisc(&esfq_qdisc_ops);
+}
+static void __exit esfq_module_exit(void) 
+{
+	unregister_qdisc(&esfq_qdisc_ops);
+}
+module_init(esfq_module_init)
+module_exit(esfq_module_exit)
+MODULE_LICENSE("GPL");
 
 
------------------------------------------------------------------------

Submitted By: Jeremy Utley <[email protected]>
Date: 2004-11-04
Initial Package Version: 2.6.9-041019
Upstream Status - Not submitted - LFS Specific
Origin: Based on inital work by Jim Gifford, ported to apply to the latest version
Description: Disables compilation of the arpd program, which requres Berkley DB.

diff -Naur iproute2-2.6.9/misc/Makefile iproute2-2.6.9-new/misc/Makefile

misc/Makefile +1 -1
@@ -1,7 +1,7 @@
 SSOBJ=ss.o ssfilter.o
 LNSTATOBJ=lnstat.o lnstat_util.o
 
-TARGETS=ss nstat ifstat rtacct arpd lnstat
+TARGETS=ss nstat ifstat rtacct lnstat
 
 include ../Config
 

misc/Makefile line 23

Quoted 9 lines
misc/Makefile +0 -3
@@ -18,9 +18,6 @@
 rtacct: rtacct.c
 	$(CC) $(CFLAGS) $(LDFLAGS) -o rtacct rtacct.c $(LIBNETLINK) -lm
 
-arpd: arpd.c
-	$(CC) $(CFLAGS) -I$(DBM_INCLUDE) $(LDFLAGS) -o arpd arpd.c $(LIBNETLINK) -ldb -lpthread
-
 ssfilter.c: ssfilter.y
 	bison ssfilter.y -o ssfilter.c
 

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#8 lore raw
In reply to Justin Schoeman

* Andy Furniss <[email protected]> 2005-01-11 15:28

Review line 147

Quoted 7 lines

diff -urN linux-2.6.10.orig/include/linux/pkt_sched.h linux-2.6.10/include/linux/pkt_sched.h

(quoted diff) +1 -0
@@ -136,6 +143,7 @@
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
+	unsigned	hash_kind;	/* Hash function to use for flow identification */
 };

This breaks compatibility to older iproute2 versions compiled with older header versions (not including the additional 4 octets). sch_sfq.c:

        if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
	                return -EINVAL;
Quoted 29 lines
(quoted diff) +29 -0
+static int esfq_change(struct Qdisc *sch, struct rtattr *opt)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	struct tc_sfq_qopt *ctl = RTA_DATA(opt);
+	int old_perturb = q->perturb_period;
+
+	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;
+//	q->hash_divisor = ctl->divisor;
+//	q->tail = q->limit = q->depth = ctl->flows;
+
+	if (ctl->limit)
+		q->limit = min_t(u32, ctl->limit, q->depth);
+	
+	if (ctl->hash_kind) {
+		q->hash_kind = ctl->hash_kind;
+		if (q->hash_kind !=  TCA_SFQ_HASH_CLASSIC)
+			q->perturb_period = 0;
+	}
+	
+	// is sch_tree_lock enough to do this ?
+	while (sch->q.qlen >= q->limit-1)
+		esfq_drop(sch);
+	
+	if (old_perturb)

Review

Quoted 10 lines
(quoted diff) +10 -0
+		del_timer(&q->perturb_timer);
+	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;
+}

Must be changed to use tcf_exts and ematch api once those patches are merged. I will take care of this.

I'll have a closer look later on this week.
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#9 lore raw
In reply to Justin Schoeman
Quoted 15 lines · Thomas Graf

* Andy Furniss <[email protected]> 2005-01-11 15:28

Review line 147

Quoted 7 lines

diff -urN linux-2.6.10.orig/include/linux/pkt_sched.h linux-2.6.10/include/linux/pkt_sched.h

(quoted diff) +1 -0
@@ -136,6 +143,7 @@
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
+	unsigned	hash_kind;	/* Hash function to use for flow identification */
 };

This breaks compatibility to older iproute2 versions compiled with older header versions (not including the additional 4 octets). sch_sfq.c:

Quoted 2 lines
        if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
	                return -EINVAL;

I did wonder if it could just come out now that iproute2 uses its own pkt_sched.h.

Just to be sure I understand - it's a risk that always existed eg. before Stephen maintained iproute2, when it compiled against kernel headers. If I patched kernel and failed to compile new tc/had old tc ahead in path etc. then sfq would be broken.

So if you patch make sure you build and use new tc do tc -V / check you don't have an old one in /sbin as iproute2's make install uses /usr/sbin by default.

Quoted 45 lines
Quoted 30 lines
(quoted diff) +29 -0
+static int esfq_change(struct Qdisc *sch, struct rtattr *opt)
+{
+	struct esfq_sched_data *q = qdisc_priv(sch);
+	struct tc_sfq_qopt *ctl = RTA_DATA(opt);
+	int old_perturb = q->perturb_period;
+
+	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;
+//	q->hash_divisor = ctl->divisor;
+//	q->tail = q->limit = q->depth = ctl->flows;
+
+	if (ctl->limit)
+		q->limit = min_t(u32, ctl->limit, q->depth);
+	
+	if (ctl->hash_kind) {
+		q->hash_kind = ctl->hash_kind;
+		if (q->hash_kind !=  TCA_SFQ_HASH_CLASSIC)
+			q->perturb_period = 0;
+	}
+	
+	// is sch_tree_lock enough to do this ?
+	while (sch->q.qlen >= q->limit-1)
+		esfq_drop(sch);
+	
+	if (old_perturb)

Review

Quoted 10 lines
(quoted diff) +10 -0
+		del_timer(&q->perturb_timer);
+	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;
+}

Must be changed to use tcf_exts and ematch api once those patches are merged. I will take care of this.

Quoted 2 lines

I'll have a closer look later on this week.

Thanks.

Andy.

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#10 lore raw
In reply to Justin Schoeman
Quoted 22 lines · On Tue, 11 Jan 2005 23:06:27 +0000 Andy Furniss <[email protected]>…
Quoted 15 lines · Thomas Graf

* Andy Furniss <[email protected]> 2005-01-11 15:28

Review line 147

Quoted 7 lines

diff -urN linux-2.6.10.orig/include/linux/pkt_sched.h linux-2.6.10/include/linux/pkt_sched.h

(quoted diff) +1 -0
@@ -136,6 +143,7 @@
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
+	unsigned	hash_kind;	/* Hash function to use for flow identification */
 };

This breaks compatibility to older iproute2 versions compiled with older header versions (not including the additional 4 octets). sch_sfq.c:

Quoted 2 lines
        if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
	                return -EINVAL;

I did wonder if it could just come out now that iproute2 uses its own pkt_sched.h.

Quoted 9 lines

Just to be sure I understand - it's a risk that always existed eg. before Stephen maintained iproute2, when it compiled against kernel headers. If I patched kernel and failed to compile new tc/had old tc ahead in path etc. then sfq would be broken.

So if you patch make sure you build and use new tc do tc -V / check you don't have an old one in /sbin as iproute2's make install uses /usr/sbin by default.

We need to maintain binary compatibility so that old command with latest kernel, and new command works with old kernel. That restricts message formats.

But not source compatibility for iproute2, the iproute2 package needs to be self-contained and not depend on external (kernel) headers that may or may not be up to date.

Also, older version of iproute2 compiled with current kernel headers should be supported. I would rather see all versions of iproute2 tarball's as self contained and not depend on kernel headers.
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

#11 lore raw
In reply to Justin Schoeman
Quoted 42 lines · Stephen Hemminger
Quoted 24 lines · On Tue, 11 Jan 2005 23:06:27 +0000 Andy Furniss <[email protected]>…
Quoted 16 lines · Thomas Graf

* Andy Furniss <[email protected]> 2005-01-11 15:28

Review line 147

Quoted 7 lines

diff -urN linux-2.6.10.orig/include/linux/pkt_sched.h linux-2.6.10/include/linux/pkt_sched.h

(quoted diff) +1 -0
@@ -136,6 +143,7 @@
 	__u32		limit;		/* Maximal packets in queue */
 	unsigned	divisor;	/* Hash divisor  */
 	unsigned	flows;		/* Maximal number of flows  */
+	unsigned	hash_kind;	/* Hash function to use for flow identification */
 };

This breaks compatibility to older iproute2 versions compiled with older header versions (not including the additional 4 octets). sch_sfq.c:

Quoted 2 lines
       if (opt->rta_len < RTA_LENGTH(sizeof(*ctl)))
	                return -EINVAL;

I did wonder if it could just come out now that iproute2 uses its own pkt_sched.h.

Quoted 9 lines

Just to be sure I understand - it's a risk that always existed eg. before Stephen maintained iproute2, when it compiled against kernel headers. If I patched kernel and failed to compile new tc/had old tc ahead in path etc. then sfq would be broken.

So if you patch make sure you build and use new tc do tc -V / check you don't have an old one in /sbin as iproute2's make install uses /usr/sbin by default.

We need to maintain binary compatibility so that old command with latest kernel, and new command works with old kernel. That restricts message formats.

Quoted 7 lines

But not source compatibility for iproute2, the iproute2 package needs to be self-contained and not depend on external (kernel) headers that may or may not be up to date.

Also, older version of iproute2 compiled with current kernel headers should be supported. I would rather see all versions of iproute2 tarball's as self contained and not depend on kernel headers.

Ahh - I think I see what you mean.

If esfq wants to get into kernel then it has to become a completly new queue and not mess with sfq options at all.

Andy.

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/