[PATCH v2 1/2] [iproute2/tc] tc_core: add size table

[PATCH v2 1/2] [iproute2/tc] tc_core: add size table

[Jussi Kivilinna]

Patch adds size table that is similiar to rate table, with difference that
size table stores link layer packet size. It's needed for HFSC link
layer adaption patch as it converts skb->len to link layer packet size
directly, unlike HTB/CFQ/etc that convert packet length to link layer
transfer time using rate tables.

Signed-off-by: Jussi Kivilinna <jussi.kivilinna@mbnet.fi>
---

 include/linux/pkt_sched.h |   10 ++++++
 tc/tc_core.c              |   73 ++++++++++++++++++++++++++++++++++++---------
 tc/tc_core.h              |    2 +
 3 files changed, 70 insertions(+), 15 deletions(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index dbb7ac3..b8366fb 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -85,6 +85,16 @@ struct tc_ratespec
 
 #define TC_RTAB_SIZE	1024
 
+struct tc_sizespec {
+	unsigned char	cell_log;
+	unsigned char	size_log;
+	unsigned short	overhead;
+	short		cell_align;
+	unsigned short	mpu;
+};
+
+#define TC_STAB_SIZE	1024
+
 /* FIFO section */
 
 struct tc_fifo_qopt
diff --git a/tc/tc_core.c b/tc/tc_core.c
index 855c115..ca509d9 100644
--- a/tc/tc_core.c
+++ b/tc/tc_core.c
@@ -87,6 +87,25 @@ unsigned tc_align_to_atm(unsigned size)
 	return linksize;
 }
 
+unsigned tc_adjust_size(unsigned sz, unsigned mpu, enum link_layer linklayer)
+{
+	if (sz < mpu)
+		sz = mpu;
+
+	switch (linklayer) {
+	case LINKLAYER_ATM:
+		sz = tc_align_to_atm(sz);
+		break;
+	case LINKLAYER_ETHERNET:
+		// No size adjustments on Ethernet
+		break;
+	default:
+		break;
+	}
+
+	return sz;
+}
+
 /*
    rtab[pkt_len>>cell_log] = pkt_xmit_time
  */
@@ -109,21 +128,7 @@ int tc_calc_rtable(struct tc_ratespec *r, __u32 *rtab,
 	}
 
 	for (i=0; i<256; i++) {
-		unsigned sz = (i+1)<<cell_log;
-		if (sz < mpu)
-			sz = mpu;
-
-		switch (linklayer) {
-		case LINKLAYER_ATM:
-			sz = tc_align_to_atm(sz);
-			break;
-		case LINKLAYER_ETHERNET:
-			// No size adjustments on Ethernet
-			break;
-		default:
-			break;
-		}
-
+		unsigned sz = tc_adjust_size((i+1)<<cell_log, mpu, linklayer);
 		rtab[i] = tc_calc_xmittime(bps, sz);
 	}
 
@@ -132,6 +137,44 @@ int tc_calc_rtable(struct tc_ratespec *r, __u32 *rtab,
 	return cell_log;
 }
 
+/*
+   stab[pkt_len>>cell_log] = pkt_xmit_size
+ */
+
+int tc_calc_stable(struct tc_sizespec *s, __u16 *stab,
+		   int cell_log, unsigned mtu,
+		   enum link_layer linklayer)
+{
+	int i;
+	unsigned mpu = s->mpu;
+	unsigned size_log = 0;
+	unsigned sz;
+
+	if (mtu == 0)
+		mtu = 2047;
+
+	if (cell_log < 0) {
+		cell_log = 0;
+		while ((mtu >> cell_log) > 512 - 1)
+			cell_log++;
+	}
+
+again:
+	for (i = 512 - 1; i >= 0; i--) {
+		sz = tc_adjust_size((i + 1) << cell_log, mpu, linklayer);
+		if ((sz >> size_log) > UINT16_MAX) {
+			size_log++;
+			goto again;
+		}
+		stab[i] = sz >> size_log;
+	}
+
+	s->size_log = size_log;
+	s->cell_align = -1; // Due to the sz calc
+	s->cell_log = cell_log;
+	return cell_log;
+}
+
 int tc_core_init()
 {
 	FILE *fp;
diff --git a/tc/tc_core.h b/tc/tc_core.h
index 9f835e8..97a4894 100644
--- a/tc/tc_core.h
+++ b/tc/tc_core.h
@@ -21,6 +21,8 @@ unsigned tc_calc_xmittime(unsigned rate, unsigned size);
 unsigned tc_calc_xmitsize(unsigned rate, unsigned ticks);
 int tc_calc_rtable(struct tc_ratespec *r, __u32 *rtab,
 		   int cell_log, unsigned mtu, enum link_layer link_layer);
+int tc_calc_stable(struct tc_sizespec *r, __u16 *stab,
+		   int cell_log, unsigned mtu, enum link_layer link_layer);
 
 int tc_setup_estimator(unsigned A, unsigned time_const, struct tc_estimator *est);
 

[PATCH v2 2/2] [iproute2/tc] hfsc: add link layer overhead adaption

[Jussi Kivilinna]

Patch adds 'mpu', 'mtu', 'overhead' and 'linklayer' options to hfsc. These
options are used to create size table for sch_hfsc. Size table is only used
and passed to kernel if these options are used.

Signed-off-by: Jussi Kivilinna <jussi.kivilinna@mbnet.fi>
---

 include/linux/pkt_sched.h |    2 +
 tc/q_hfsc.c               |   71 ++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 72 insertions(+), 1 deletions(-)

diff --git a/include/linux/pkt_sched.h b/include/linux/pkt_sched.h
index b8366fb..43c11f2 100644
--- a/include/linux/pkt_sched.h
+++ b/include/linux/pkt_sched.h
@@ -326,6 +326,8 @@ enum
 	TCA_HFSC_RSC,
 	TCA_HFSC_FSC,
 	TCA_HFSC_USC,
+	TCA_HFSC_SZOPTS,
+	TCA_HFSC_STAB,
 	__TCA_HFSC_MAX,
 };
 
diff --git a/tc/q_hfsc.c b/tc/q_hfsc.c
index b190c71..aa1c9b0 100644
--- a/tc/q_hfsc.c
+++ b/tc/q_hfsc.c
@@ -42,6 +42,13 @@ explain_class(void)
 {
 	fprintf(stderr,
 		"Usage: ... hfsc [ [ rt SC ] [ ls SC ] | [ sc SC ] ] [ ul SC ]\n"
+		"                [ mtu BYTES] [ mpu BYTES ] [ overhead BYTES ]\n"
+		"                [ linklayer TYPE ]\n"
+		"\n"
+		" mtu       : max packet size we create rate map for {2047}\n"
+		" mpu       : minimum packet size used in rate computations\n"
+		" overhead  : per-packet size overhead used in rate computations\n"
+		" linklayer : adapting to a linklayer e.g. atm\n"
 		"\n"
 		"SC := [ [ m1 BPS ] [ d SEC ] m2 BPS\n"
 		"\n"
@@ -145,14 +152,45 @@ hfsc_parse_class_opt(struct qdisc_util *qu, int argc, char **argv,
 	struct tc_service_curve rsc, fsc, usc;
 	int rsc_ok, fsc_ok, usc_ok;
 	struct rtattr *tail;
+	struct tc_sizespec szopts;
+	__u16 stab[512];
+	int use_stab;
+	unsigned mtu = 0;
+	unsigned int linklayer = LINKLAYER_ETHERNET; /* Assume ethernet */
+	unsigned short overhead = 0, mpu = 0;
 
 	memset(&rsc, 0, sizeof(rsc));
 	memset(&fsc, 0, sizeof(fsc));
 	memset(&usc, 0, sizeof(usc));
+	memset(&szopts, 0, sizeof(szopts));
 	rsc_ok = fsc_ok = usc_ok = 0;
 
 	while (argc > 0) {
-		if (matches(*argv, "rt") == 0) {
+		if (matches(*argv, "mtu") == 0) {
+			NEXT_ARG();
+			if (get_u32(&mtu, *argv, 10)) {
+				explain1("mtu");
+				return -1;
+			}
+		} else if (matches(*argv, "mpu") == 0) {
+			NEXT_ARG();
+			if (get_u16(&mpu, *argv, 10)) {
+				explain1("mpu");
+				return -1;
+			}
+		} else if (matches(*argv, "overhead") == 0) {
+			NEXT_ARG();
+			if (get_u16(&overhead, *argv, 10)) {
+				explain1("overhead");
+				return -1;
+			}
+		} else if (matches(*argv, "linklayer") == 0) {
+			NEXT_ARG();
+			if (get_linklayer(&linklayer, *argv)) {
+				explain1("linklayer");
+				return -1;
+			}
+		} else if (matches(*argv, "rt") == 0) {
 			NEXT_ARG();
 			if (hfsc_get_sc(&argc, &argv, &rsc) < 0) {
 				explain1("rt");
@@ -205,6 +243,18 @@ hfsc_parse_class_opt(struct qdisc_util *qu, int argc, char **argv,
 		return -1;
 	}
 
+	/* Only use stab when needed, mtu only defines stab properties so
+	 * it is not checked for. */
+	use_stab = (linklayer != LINKLAYER_ETHERNET || mpu != 0 || overhead != 0);
+	if (use_stab) {
+		szopts.mpu = mpu;
+		szopts.overhead = overhead;
+		if (tc_calc_stable(&szopts, stab, -1, mtu, linklayer) < 0) {
+			fprintf(stderr, "HFSC: failed to calculate rate table.\n");
+			return -1;
+		}
+	}
+
 	tail = NLMSG_TAIL(n);
 
 	addattr_l(n, 1024, TCA_OPTIONS, NULL, 0);
@@ -214,6 +264,10 @@ hfsc_parse_class_opt(struct qdisc_util *qu, int argc, char **argv,
 		addattr_l(n, 1024, TCA_HFSC_FSC, &fsc, sizeof(fsc));
 	if (usc_ok)
 		addattr_l(n, 1024, TCA_HFSC_USC, &usc, sizeof(usc));
+	if (use_stab) {
+		addattr_l(n, 2024, TCA_HFSC_SZOPTS, &szopts, sizeof(szopts));
+		addattr_l(n, 3024, TCA_HFSC_STAB, stab, TC_STAB_SIZE);
+	}
 
 	tail->rta_len = (void *) NLMSG_TAIL(n) - (void *) tail;
 	return 0;
@@ -235,6 +289,8 @@ hfsc_print_class_opt(struct qdisc_util *qu, FILE *f, struct rtattr *opt)
 {
 	struct rtattr *tb[TCA_HFSC_MAX+1];
 	struct tc_service_curve *rsc = NULL, *fsc = NULL, *usc = NULL;
+	struct tc_sizespec *szopts = NULL;
+	SPRINT_BUF(b1);
 
 	if (opt == NULL)
 		return 0;
@@ -259,6 +315,12 @@ hfsc_print_class_opt(struct qdisc_util *qu, FILE *f, struct rtattr *opt)
 		else
 			usc = RTA_DATA(tb[TCA_HFSC_USC]);
 	}
+	if (tb[TCA_HFSC_SZOPTS]) {
+		if (RTA_PAYLOAD(tb[TCA_HFSC_SZOPTS]) < sizeof(*szopts))
+			fprintf(stderr, "HFSC: truncated rate options\n");
+		else
+			szopts = RTA_DATA(tb[TCA_HFSC_SZOPTS]);
+	}
 
 
 	if (rsc != NULL && fsc != NULL &&
@@ -273,6 +335,13 @@ hfsc_print_class_opt(struct qdisc_util *qu, FILE *f, struct rtattr *opt)
 	if (usc != NULL)
 		hfsc_print_sc(f, "ul", usc);
 
+	if (szopts != NULL && show_details) {
+		if (szopts->mpu)
+			fprintf(f, "mpu %s ", sprint_size(szopts->mpu, b1));
+		if (szopts->overhead)
+			fprintf(f, "overhead %s ", sprint_size(szopts->overhead, b1));
+	}
+
 	return 0;
 }
 

Re: [PATCH v2 2/2] [iproute2/tc] hfsc: add link layer overhead adaption

[Andy Furniss]

Jussi Kivilinna wrote:
> Patch adds 'mpu', 'mtu', 'overhead' and 'linklayer' options to hfsc. These
> options are used to create size table for sch_hfsc. Size table is only used
> and passed to kernel if these options are used.

> +	unsigned short overhead = 0, mpu = 0;

overhead may need to be negative because skb->len on eth is payload + 14

Andy.

Re: [PATCH v2 2/2] [iproute2/tc] hfsc: add link layer overhead adaption

[Jussi Kivilinna]

Quoting Andy Furniss <lists@andyfurniss.entadsl.com>:

> Jussi Kivilinna wrote:
>> Patch adds 'mpu', 'mtu', 'overhead' and 'linklayer' options to hfsc. These
>> options are used to create size table for sch_hfsc. Size table is only used
>> and passed to kernel if these options are used.
>
>> +	unsigned short overhead = 0, mpu = 0;
>
> overhead may need to be negative because skb->len on eth is payload + 14
>
> Andy.

Ok, I made size tables use signed short for overhead instead. But this  
makes me think should htb/cfq/tfb be changed to support negative  
overhead too? Rate table they use have unsigned overhead.

  - Jussi

Re: [PATCH v2 2/2] [iproute2/tc] hfsc: add link layer overhead adaption

[Andy Furniss]

Jussi Kivilinna wrote:
> Quoting Andy Furniss <lists@andyfurniss.entadsl.com>:
> 
>> Jussi Kivilinna wrote:
>>> Patch adds 'mpu', 'mtu', 'overhead' and 'linklayer' options to hfsc. 
>>> These
>>> options are used to create size table for sch_hfsc. Size table is 
>>> only used
>>> and passed to kernel if these options are used.
>>
>>> +    unsigned short overhead = 0, mpu = 0;
>>
>> overhead may need to be negative because skb->len on eth is payload + 14
>>
>> Andy.
> 
> Ok, I made size tables use signed short for overhead instead. But this 
> makes me think should htb/cfq/tfb be changed to support negative 
> overhead too? Rate table they use have unsigned overhead.

Yea they should really, somehow - eventually :-) It was discussed here -

http://news.gmane.org/find-root.php?group=gmane.linux.network&article=90386

Andy.

Re: [PATCH v2 2/2] [iproute2/tc] hfsc: add link layer overhead adaption

[Patrick McHardy]

Jussi Kivilinna wrote:
> Quoting Andy Furniss <lists@andyfurniss.entadsl.com>:
> 
>> Jussi Kivilinna wrote:
>>> Patch adds 'mpu', 'mtu', 'overhead' and 'linklayer' options to hfsc. 
>>> These
>>> options are used to create size table for sch_hfsc. Size table is 
>>> only used
>>> and passed to kernel if these options are used.
>>
>>> +    unsigned short overhead = 0, mpu = 0;
>>
>> overhead may need to be negative because skb->len on eth is payload + 14
>>
>> Andy.
> 
> Ok, I made size tables use signed short for overhead instead.

Please wait with resending until I get a chance to review the
patches (probably later today) in case something else comes up.

Re: [PATCH v2 2/2] [iproute2/tc] hfsc: add link layer overhead adaption

[Jussi Kivilinna]

Quoting Patrick McHardy <kaber@trash.net>:

> Jussi Kivilinna wrote:
>> Quoting Andy Furniss <lists@andyfurniss.entadsl.com>:
>>
>>> Jussi Kivilinna wrote:
>>>> Patch adds 'mpu', 'mtu', 'overhead' and 'linklayer' options to hfsc. These
>>>> options are used to create size table for sch_hfsc. Size table is  
>>>>  only used
>>>> and passed to kernel if these options are used.
>>>
>>>> +    unsigned short overhead = 0, mpu = 0;
>>>
>>> overhead may need to be negative because skb->len on eth is payload + 14
>>>
>>> Andy.
>>
>> Ok, I made size tables use signed short for overhead instead.
>
> Please wait with resending until I get a chance to review the
> patches (probably later today) in case something else comes up.

Ok.