Endianness problem with u32 classifier hash masks

Endianness problem with u32 classifier hash masks

[Radu Rendec]

Hi,

While trying to implement u32 hashes in my shaping machine I ran into a
possible bug in the u32 hash/bucket computing algorithm
(net/sched/cls_u32.c).

The problem occurs only with hash masks that extend over the octet
boundary, on little endian machines (where htonl() actually does
something).

I'm not 100% sure this is a problem with u32 itself, but at least I'm
sure u32 with the same configuration would behave differently on little
endian and big endian machines. Detailed description of the problem and
proposed patch follow.

Let's say that I would like to use 0x3fc0 as the hash mask. This means 8
contiguous "1" bits starting at b6. With such a mask, the expected (and
logical) behavior is to hash any address in, for instance,
192.168.0.0/26 in bucket 0, then any address in 192.168.0.64/26 in
bucket 1, then 192.168.0.128/26 in bucket 2 and so on.

This is exactly what would happen on a big endian machine, but on little
endian machines, what would actually happen with current implementation
is 0x3fc0 being reversed (into 0xc03f0000) by htonl() in the userspace
tool and then applied to 192.168.x.x in the u32 classifier. When
shifting right by 16 bits (rank of first "1" bit in the reversed mask)
and applying the divisor mask (0xff for divisor 256), what would
actually remain is 0x3f applied on the "168" octet of the address.

One could say is this can be easily worked around by taking endianness
into account in userspace and supplying an appropriate mask (0xfc03)
that would be turned into contiguous "1" bits when reversed
(0x03fc0000). But the actual problem is the network address (inside the
packet) not being converted to host order, but used as a host-order
value when computing the bucket.

Let's say the network address is written as n31 n30 ... n0, with n0
being the least significant bit. When used directly (without any
conversion) on a little endian machine, it becomes
n7 ... n0 n8 ..n15 etc in the machine's registers. Thus bits n7 and n8
would no longer be adjacent and 192.168.64.0/26 and 192.168.128.0/26
would no longer be consecutive.

My approach to this issue was keeping the hash mask in host order and
converting the octets in the packet to host order before applying the
mask. This proved to work just fine on my little endian machine, but I'm
interested in finding out (from you) if this really is an issue with u32
itself.

My changes to the u32 classifier are attached below as a patch. It was
made against 2.6.22.9, but applies cleanly on Dave Miller's net-2.6
tree.

The idea behind my changes is to keep the user space tool intact and
work everything out in kernel space (because converting the packet
octets to host order must be done in kernel anyway).

Therefore, hash masks are converted back to host order when a selector
is configured - in u32_change() - and converted to network order
(because userspace tools expect to get them in network order from the
kernel) when a selector is dumped - in u32_dump().

I would like at least to know your opinion about this issue.

Thanks,

Radu Rendec

--- linux-2.6.22.9/net/sched/cls_u32.c.orig	2007-10-30 17:08:03.000000000 +0200
+++ linux-2.6.22.9/net/sched/cls_u32.c	2007-10-30 17:04:49.000000000 +0200
@@ -198,7 +198,7 @@
 		ht = n->ht_down;
 		sel = 0;
 		if (ht->divisor)
-			sel = ht->divisor&u32_hash_fold(*(u32*)(ptr+n->sel.hoff), &n->sel,n->fshift);
+			sel = ht->divisor&u32_hash_fold(ntohl(*(u32*)(ptr+n->sel.hoff)), &n->sel,n->fshift);
 
 		if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT)))
 			goto next_ht;
@@ -626,6 +626,10 @@
 	}
 #endif
 
+	/* userspace tc tool sends us the hmask in network order, but we
+	 * need host order, so change it here */
+	s->hmask = ntohl(s->hmask);
+
 	memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
 	n->ht_up = ht;
 	n->handle = handle;
@@ -735,9 +739,14 @@
 		u32 divisor = ht->divisor+1;
 		RTA_PUT(skb, TCA_U32_DIVISOR, 4, &divisor);
 	} else {
+		/* get the address where the selector will be put, then
+		 * change the hmask after it is put there */
+		struct tc_u32_sel *s =
+			(struct tc_u32_sel *)RTA_DATA(skb_tail_pointer(skb));
 		RTA_PUT(skb, TCA_U32_SEL,
 			sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
 			&n->sel);
+		s->hmask = htonl(s->hmask);
 		if (n->ht_up) {
 			u32 htid = n->handle & 0xFFFFF000;
 			RTA_PUT(skb, TCA_U32_HASH, 4, &htid);

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

Radu Rendec wrote:

> Hi,
> 
> While trying to implement u32 hashes in my shaping machine I ran into a
> possible bug in the u32 hash/bucket computing algorithm
> (net/sched/cls_u32.c).
> 
> The problem occurs only with hash masks that extend over the octet
> boundary, on little endian machines (where htonl() actually does
> something).
> 
> I'm not 100% sure this is a problem with u32 itself, but at least I'm
> sure u32 with the same configuration would behave differently on little
> endian and big endian machines. Detailed description of the problem and
> proposed patch follow.


I think you are right about this different behavior, so it looks like a bug.
And since little endian way is uncontrollable in such a case, your proposal
should be right.

But, since there is a maintainer for this, let's check what is he not payed
for?! (Cc: Jamal Hadi Salim)

Regards,
Jarek P.



> 
> Let's say that I would like to use 0x3fc0 as the hash mask. This means 8
> contiguous "1" bits starting at b6. With such a mask, the expected (and
> logical) behavior is to hash any address in, for instance,
> 192.168.0.0/26 in bucket 0, then any address in 192.168.0.64/26 in
> bucket 1, then 192.168.0.128/26 in bucket 2 and so on.
> 
> This is exactly what would happen on a big endian machine, but on little
> endian machines, what would actually happen with current implementation
> is 0x3fc0 being reversed (into 0xc03f0000) by htonl() in the userspace
> tool and then applied to 192.168.x.x in the u32 classifier. When
> shifting right by 16 bits (rank of first "1" bit in the reversed mask)
> and applying the divisor mask (0xff for divisor 256), what would
> actually remain is 0x3f applied on the "168" octet of the address.
> 
> One could say is this can be easily worked around by taking endianness
> into account in userspace and supplying an appropriate mask (0xfc03)
> that would be turned into contiguous "1" bits when reversed
> (0x03fc0000). But the actual problem is the network address (inside the
> packet) not being converted to host order, but used as a host-order
> value when computing the bucket.
> 
> Let's say the network address is written as n31 n30 ... n0, with n0
> being the least significant bit. When used directly (without any
> conversion) on a little endian machine, it becomes
> n7 ... n0 n8 ..n15 etc in the machine's registers. Thus bits n7 and n8
> would no longer be adjacent and 192.168.64.0/26 and 192.168.128.0/26
> would no longer be consecutive.
> 
> My approach to this issue was keeping the hash mask in host order and
> converting the octets in the packet to host order before applying the
> mask. This proved to work just fine on my little endian machine, but I'm
> interested in finding out (from you) if this really is an issue with u32
> itself.
> 
> My changes to the u32 classifier are attached below as a patch. It was
> made against 2.6.22.9, but applies cleanly on Dave Miller's net-2.6
> tree.
> 
> The idea behind my changes is to keep the user space tool intact and
> work everything out in kernel space (because converting the packet
> octets to host order must be done in kernel anyway).
> 
> Therefore, hash masks are converted back to host order when a selector
> is configured - in u32_change() - and converted to network order
> (because userspace tools expect to get them in network order from the
> kernel) when a selector is dumped - in u32_dump().
> 
> I would like at least to know your opinion about this issue.
> 
> Thanks,
> 
> Radu Rendec
> 
> --- linux-2.6.22.9/net/sched/cls_u32.c.orig	2007-10-30 17:08:03.000000000 +0200
> +++ linux-2.6.22.9/net/sched/cls_u32.c	2007-10-30 17:04:49.000000000 +0200
> @@ -198,7 +198,7 @@
>  		ht = n->ht_down;
>  		sel = 0;
>  		if (ht->divisor)
> -			sel = ht->divisor&u32_hash_fold(*(u32*)(ptr+n->sel.hoff), &n->sel,n->fshift);
> +			sel = ht->divisor&u32_hash_fold(ntohl(*(u32*)(ptr+n->sel.hoff)), &n->sel,n->fshift);
>  
>  		if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT)))
>  			goto next_ht;
> @@ -626,6 +626,10 @@
>  	}
>  #endif
>  
> +	/* userspace tc tool sends us the hmask in network order, but we
> +	 * need host order, so change it here */
> +	s->hmask = ntohl(s->hmask);
> +
>  	memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
>  	n->ht_up = ht;
>  	n->handle = handle;
> @@ -735,9 +739,14 @@
>  		u32 divisor = ht->divisor+1;
>  		RTA_PUT(skb, TCA_U32_DIVISOR, 4, &divisor);
>  	} else {
> +		/* get the address where the selector will be put, then
> +		 * change the hmask after it is put there */
> +		struct tc_u32_sel *s =
> +			(struct tc_u32_sel *)RTA_DATA(skb_tail_pointer(skb));
>  		RTA_PUT(skb, TCA_U32_SEL,
>  			sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
>  			&n->sel);
> +		s->hmask = htonl(s->hmask);
>  		if (n->ht_up) {
>  			u32 htid = n->handle & 0xFFFFF000;
>  			RTA_PUT(skb, TCA_U32_HASH, 4, &htid);
> 
> 
> -
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: Endianness problem with u32 classifier hash masks

[jamal]

On Fri, 2007-02-11 at 18:31 +0100, Jarek Poplawski wrote:
> Radu Rendec wrote:
> 
> > Hi,
> > 
> > While trying to implement u32 hashes in my shaping machine I ran into a
> > possible bug in the u32 hash/bucket computing algorithm
> > (net/sched/cls_u32.c).
> > 
> > The problem occurs only with hash masks that extend over the octet
> > boundary, on little endian machines (where htonl() actually does
> > something).
> > 
> > I'm not 100% sure this is a problem with u32 itself, but at least I'm
> > sure u32 with the same configuration would behave differently on little
> > endian and big endian machines. Detailed description of the problem and
> > proposed patch follow.
> 
> 
> I think you are right about this different behavior, so it looks like a bug.
> And since little endian way is uncontrollable in such a case, your proposal
> should be right.
> 
> But, since there is a maintainer for this, let's check what is he not payed
> for?! (Cc: Jamal Hadi Salim)
> 

Thanks for the CC Jarek - and i promise to share the loot with you when
i lay my hands on it;->

I see that given the mask described (the 0 bits bounding the two
nibbles), the same packet in that network will hit two different buckets
depending on endianness. In other words there is lack of consistency. So
good catch.
The patch would certainly resolve it.
The only thing that bothers me with the patch approach is the extra
conversion in the fast path. Radu, since this is not a show stopper -
can you give me a short time to sip on it? I am thinking it is probably
resolvable by using the right tuning at config time - one knob that
looks usable is fshift and that all this can be done at config time; but
i may need more than one coffee to get it right, but if you see it just
send a patch. I will try to use the data you used to see if i am making
any sense.

cheers,
jamal

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

jamal wrote, On 11/03/2007 12:23 AM:

> On Fri, 2007-02-11 at 18:31 +0100, Jarek Poplawski wrote:
>> Radu Rendec wrote:
>>
>>> Hi,
>>>
>>> While trying to implement u32 hashes in my shaping machine I ran into a
>>> possible bug in the u32 hash/bucket computing algorithm
>>> (net/sched/cls_u32.c).
>>>
>>> The problem occurs only with hash masks that extend over the octet
>>> boundary, on little endian machines (where htonl() actually does
>>> something).
>>>
>>> I'm not 100% sure this is a problem with u32 itself, but at least I'm
>>> sure u32 with the same configuration would behave differently on little
>>> endian and big endian machines. Detailed description of the problem and
>>> proposed patch follow.
>>
>> I think you are right about this different behavior, so it looks like a bug.
>> And since little endian way is uncontrollable in such a case, your proposal
>> should be right.
>>
>> But, since there is a maintainer for this, let's check what is he not payed
>> for?! (Cc: Jamal Hadi Salim)
>>
> 
> Thanks for the CC Jarek - and i promise to share the loot with you when
> i lay my hands on it;->
> 
> I see that given the mask described (the 0 bits bounding the two
> nibbles), the same packet in that network will hit two different buckets
> depending on endianness. In other words there is lack of consistency. So
> good catch.
> The patch would certainly resolve it.
> The only thing that bothers me with the patch approach is the extra
> conversion in the fast path. Radu, since this is not a show stopper -
> can you give me a short time to sip on it? I am thinking it is probably
> resolvable by using the right tuning at config time - one knob that
> looks usable is fshift and that all this can be done at config time; but
> i may need more than one coffee to get it right, but if you see it just
> send a patch. I will try to use the data you used to see if i am making
> any sense.
> 
> cheers,
> jamal
> 
> -
> To unsubscribe from this list: send the line "unsubscribe netdev" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 


static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel, u8 fshift)
{
#ifdef __LITTLE_ENDIAN
	/*
	 * It's a hack/optimization to avoid ntohl(). Since
	 * it's only used in u32_classify(), and masked with
	 * divisor (1 byte), one, least signinificant byte
	 * of selection is enough.
	 */
	fshift = 32 - 8 - fshift;
#endif
	unsigned h = (key & sel->hmask) >> fshift;

	return h;
}




> --- linux-2.6.22.9/net/sched/cls_u32.c.orig	2007-10-30 17:08:03.000000000 +0200
> +++ linux-2.6.22.9/net/sched/cls_u32.c	2007-10-30 17:04:49.000000000 +0200
> @@ -198,7 +198,7 @@
>  		ht = n->ht_down;
>  		sel = 0;
>  		if (ht->divisor)
> -			sel = ht->divisor&u32_hash_fold(*(u32*)(ptr+n->sel.hoff), &n->sel,n->fshift);
> +			sel = ht->divisor&u32_hash_fold(ntohl(*(u32*)(ptr+n->sel.hoff)), &n->sel,n->fshift);
>  
>  		if (!(n->sel.flags&(TC_U32_VAROFFSET|TC_U32_OFFSET|TC_U32_EAT)))
>  			goto next_ht;
> @@ -626,6 +626,10 @@
>  	}
>  #endif
>  
> +	/* userspace tc tool sends us the hmask in network order, but we
> +	 * need host order, so change it here */
> +	s->hmask = ntohl(s->hmask);
> +
>  	memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
>  	n->ht_up = ht;
>  	n->handle = handle;
> @@ -735,9 +739,14 @@
>  		u32 divisor = ht->divisor+1;
>  		RTA_PUT(skb, TCA_U32_DIVISOR, 4, &divisor);
>  	} else {
> +		/* get the address where the selector will be put, then
> +		 * change the hmask after it is put there */
> +		struct tc_u32_sel *s =
> +			(struct tc_u32_sel *)RTA_DATA(skb_tail_pointer(skb));
>  		RTA_PUT(skb, TCA_U32_SEL,
>  			sizeof(n->sel) + n->sel.nkeys*sizeof(struct tc_u32_key),
>  			&n->sel);
> +		s->hmask = htonl(s->hmask);
>  		if (n->ht_up) {
>  			u32 htid = n->handle & 0xFFFFF000;
>  			RTA_PUT(skb, TCA_U32_HASH, 4, &htid);
> 
> 
> -

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

Jarek Poplawski wrote, On 11/04/2007 12:39 AM:
...

OOPS!!! Went too early! I've tried to save not send. Probably my
bad pronunciation...

But, it seems this could be something like this (instead of Radu's
change in u32_classify()). The change of hmask is needed.

But it needs more checking...

Jarek P.

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

Jarek Poplawski wrote, On 11/04/2007 12:58 AM:

> Jarek Poplawski wrote, On 11/04/2007 12:39 AM:
> ...
> 
> OOPS!!! Went too early! I've tried to save not send. Probably my
> bad pronunciation...
> 
> But, it seems this could be something like this (instead of Radu's
> change in u32_classify()). The change of hmask is needed.


OK, not exactly... hmask should be ntohl'ed only for fshift:

u32 mask = ntohl(s->hmask);
...

Other changes seem to be not needed.

> 
> But it needs more checking...

Jarek P.

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

Jarek Poplawski wrote, On 11/04/2007 01:30 AM:

> Jarek Poplawski wrote, On 11/04/2007 12:58 AM:
... 
> Other changes seem to be not needed.
> 
>> But it needs more checking...


But not much more: it's a piece of fshit!

So, even if not full ntohl(), some byte moving seems to be
necessary here.

Sorry for this mess, 
Jarek P

Re: Endianness problem with u32 classifier hash masks

[jamal]

[-- Attachment #1: Type: text/plain, Size: 461 bytes --]

On Sun, 2007-04-11 at 02:17 +0100, Jarek Poplawski wrote:

> So, even if not full ntohl(), some byte moving seems to be
> necessary here.

I thinking you were close. I am afraid my brain is congested, even the
esspresso didnt help my thinking. 
It could be done with just fshift on the slow path (config time) of one
was to think hard;-> I am not too happy with the extra conversion on the
fast path, but how about the untested attached patch?

cheers,
jamal
 

[-- Attachment #2: p0-u32 --]
[-- Type: text/x-patch, Size: 646 bytes --]

diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 9e98c6e..6dd569b 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -93,7 +93,7 @@ static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel, u8 fsh
 {
 	unsigned h = (key & sel->hmask)>>fshift;
 
-	return h;
+	return ntohl(h);
 }
 
 static int u32_classify(struct sk_buff *skb, struct tcf_proto *tp, struct tcf_result *res)
@@ -615,7 +615,7 @@ static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
 	n->handle = handle;
 {
 	u8 i = 0;
-	u32 mask = s->hmask;
+	u32 mask = ntohl(s->hmask);
 	if (mask) {
 		while (!(mask & 1)) {
 			i++;

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

On Sun, Nov 04, 2007 at 06:58:13PM -0500, jamal wrote:
> On Sun, 2007-04-11 at 02:17 +0100, Jarek Poplawski wrote:
> 
> > So, even if not full ntohl(), some byte moving seems to be
> > necessary here.
> 
> I thinking you were close. I am afraid my brain is congested, even the
> esspresso didnt help my thinking. 
> It could be done with just fshift on the slow path (config time) of one
> was to think hard;-> I am not too happy with the extra conversion on the
> fast path, but how about the untested attached patch?
> 
> cheers,
> jamal
>  
> diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
> index 9e98c6e..6dd569b 100644
> --- a/net/sched/cls_u32.c
> +++ b/net/sched/cls_u32.c
> @@ -93,7 +93,7 @@ static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel, u8 fsh
>  {
>  	unsigned h = (key & sel->hmask)>>fshift;
>  
> -	return h;
> +	return ntohl(h);
>  }

Seems not good or I miss something:

host order:
address: xx.xx.xf.fx
hmask  : 00.00.0f.f0

net order:
address: fx.xf.xx.xx
hmask  : f0.0f.00.00

fshift after ntohl(s->hmask): 4
so, above:
h = (fx.xf.xx.xx & f0.0f.00.00) >> 4;
h == 0f.00.f0.00
return 00.f0.00.0f (?)

But, I hope, maybe Radu could check this better - after his analyze
it looks like his coffee is the best!

Currently I think this should be possible to get this one important
byte with 2 shifts, but it needs much more coffee on my slow path...
But, this wouldn't be very readable and I'm not sure the gain would
be really visible with current cpus, so maybe this first proposal is
quite reasonable. Then, I'd only suggest to Radu to change the '*'
style a bit in the comment and to sign this off, if you agree?

Cheers,
Jarek P.

BTW: when looking around this I think, maybe, in u32_change():

1) if (--divisor > 0x100) should be probably ">=", but is it really
needed to check this 2 times (including tc)?
2) this while() loop for n->fshift could be replaced with ffs()?

>  
>  static int u32_classify(struct sk_buff *skb, struct tcf_proto *tp, struct tcf_result *res)
> @@ -615,7 +615,7 @@ static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
>  	n->handle = handle;
>  {
>  	u8 i = 0;
> -	u32 mask = s->hmask;
> +	u32 mask = ntohl(s->hmask);
>  	if (mask) {
>  		while (!(mask & 1)) {
>  			i++;

Re: Endianness problem with u32 classifier hash masks

[Radu Rendec]

Jarek, thanks for replying my message on the list and pointing it to the
right direction.

Your example with "1" bits laying on exact nibble boundary is much
easier to analyze than my original example. And your computation seems
to be right: u32_hash_fold() would return 00.f0.00.0f (and would be cut
off to 0f after applying the divisor mask).

When I ran into this issue and figured out what was happening in
u32_classify(), at first I thought it could be fixed without any change
at all (in either kernel or tc). For a moment, computing the mask and
resulting bucket by taking into account the host<->net conversions and
supplying them "correctly" to tc seemed to be the best/easiest approach.

Then I figured out what the real problem is: if you look at network
ordered bytes and treat them as a host ordered u32, logically adjacent
bits from different bytes (in network order) will no longer be adjacent
in the host ordered u32. And this has nothing to with bitwise anding
(masking) or shifting. In other words, whatever mask or fshift values
you choose, those bits will still not be adjacent.

Jamal, I am aware that any computation on the fast path involves some
performance loss. However, I don't see any speed gain with your patch,
because you just moved the ntohl() call inside u32_hash_fold(). Since
u32_hash_fold() is called unconditionally and the only call is that one
in u32_classify(), htohl() will be called exactly the same number of
times.

After almost a week of dealing with this, I still don't think it can be
solved without byte re-ordering. If you guys think my patch is good, I
would be more than glad to send it properly (change the comments as
Jarek suggested and use git). Since I'm quite a newbie with git and
haven't worked with kernel maintainers before, please be patient if it's
not perfect at the first attempt :) What tree/branch should I make the
patch against?

Thanks,

Radu Rendec

On Mon, 2007-11-05 at 10:12 +0100, Jarek Poplawski wrote:
> On Sun, Nov 04, 2007 at 06:58:13PM -0500, jamal wrote:
> > On Sun, 2007-04-11 at 02:17 +0100, Jarek Poplawski wrote:
...
> > diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
> > index 9e98c6e..6dd569b 100644
> > --- a/net/sched/cls_u32.c
> > +++ b/net/sched/cls_u32.c
> > @@ -93,7 +93,7 @@ static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel, u8 fsh
> >  {
> >  	unsigned h = (key & sel->hmask)>>fshift;
> >  
> > -	return h;
> > +	return ntohl(h);
> >  }
> 
> Seems not good or I miss something:
> 
> host order:
> address: xx.xx.xf.fx
> hmask  : 00.00.0f.f0
> 
> net order:
> address: fx.xf.xx.xx
> hmask  : f0.0f.00.00
> 
> fshift after ntohl(s->hmask): 4
> so, above:
> h = (fx.xf.xx.xx & f0.0f.00.00) >> 4;
> h == 0f.00.f0.00
> return 00.f0.00.0f (?)
> 
> But, I hope, maybe Radu could check this better - after his analyze
> it looks like his coffee is the best!
> 
> Currently I think this should be possible to get this one important
> byte with 2 shifts, but it needs much more coffee on my slow path...
> But, this wouldn't be very readable and I'm not sure the gain would
> be really visible with current cpus, so maybe this first proposal is
> quite reasonable. Then, I'd only suggest to Radu to change the '*'
> style a bit in the comment and to sign this off, if you agree?
> 
> Cheers,
> Jarek P.
> 
> BTW: when looking around this I think, maybe, in u32_change():
> 
> 1) if (--divisor > 0x100) should be probably ">=", but is it really
> needed to check this 2 times (including tc)?
> 2) this while() loop for n->fshift could be replaced with ffs()?

Re: Endianness problem with u32 classifier hash masks

[jamal]

On Mon, 2007-05-11 at 14:59 +0200, Radu Rendec wrote:
> Jarek, thanks for replying my message on the list and pointing it to the
> right direction.
> 
> Your example with "1" bits laying on exact nibble boundary is much
> easier to analyze than my original example. And your computation seems
> to be right: u32_hash_fold() would return 00.f0.00.0f (and would be cut
> off to 0f after applying the divisor mask).

Yes, that example i believe would work just fine today as is with no
changes.

[...]

> Jamal, I am aware that any computation on the fast path involves some
> performance loss. However, I don't see any speed gain with your patch,
> because you just moved the ntohl() call inside u32_hash_fold(). Since
> u32_hash_fold() is called unconditionally and the only call is that one
> in u32_classify(), htohl() will be called exactly the same number of
> times.
> 

Sorry, I didnt mean that to be a better approach - it suffers the same
problem as what you posted and infact is just your patch simplified
essentially (or my attempt at doing that).
A simpler version would be to do something in u32_change() only and
nowhere else. Thats what i alluded at using fshift. And even after
taking a shower i cant think of a simple way to achieve it.

> After almost a week of dealing with this, I still don't think it can be
> solved without byte re-ordering. If you guys think my patch is good, I
> would be more than glad to send it properly (change the comments as
> Jarek suggested and use git). Since I'm quite a newbie with git and
> haven't worked with kernel maintainers before, please be patient if it's
> not perfect at the first attempt :) What tree/branch should I make the
> patch against?
> 

Please try the patch i sent since it is simpler. It is your work more or
less - so you should get the credit as author. 
Use Davem's net-2.6 as basis. If it works send it to him and CC me and i
will just wsignoff/ack.
If it doesnt work, can you cutdown on the conversion in u32_change()
instead and send that?

cheers,
jamal

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

On Mon, Nov 05, 2007 at 08:43:32AM -0500, jamal wrote:
> On Mon, 2007-05-11 at 14:59 +0200, Radu Rendec wrote:
> > Jarek, thanks for replying my message on the list and pointing it to the
> > right direction.
> > 
> > Your example with "1" bits laying on exact nibble boundary is much
> > easier to analyze than my original example. And your computation seems
> > to be right: u32_hash_fold() would return 00.f0.00.0f (and would be cut
> > off to 0f after applying the divisor mask).
> 
> Yes, that example i believe would work just fine today as is with no
> changes.
...
> Please try the patch i sent since it is simpler. It is your work more or
> less - so you should get the credit as author. 

Jamal + Houston, we have a problem...
...Or talk about different things or patches...

IMHO, both 'today as is' and your 1-st proposal get this example
wrong: we need 00.00.00.ff at the end, don't we? 

Jarek P.

Re: Endianness problem with u32 classifier hash masks

[Radu Rendec]

On Mon, 2007-11-05 at 15:49 +0100, Jarek Poplawski wrote:
> > Yes, that example i believe would work just fine today as is with no
> > changes.
> ...
> > Please try the patch i sent since it is simpler. It is your work more or
> > less - so you should get the credit as author. 
> 
> Jamal + Houston, we have a problem...
> ...Or talk about different things or patches...
> 
> IMHO, both 'today as is' and your 1-st proposal get this example
> wrong: we need 00.00.00.ff at the end, don't we? 
> 
> Jarek P.

"Today as is" certainly doesn't work with masks extending across byte
boundary. I think Jarek's example (with all "1" bits in nibbles) is the
most straightforward to illustrate this.

Jarek, after I had replied you earlier, I figured out it can indeed be
solved with two shifts, but results need to be masked separately and
then merged to properly align resulting bits. Of course, this is my idea
about the two shifts, maybe you thought of something else.

On the other hand, after a quick browsing through a lxr, it seems that
(at least on i386) ntohl() is actually a swab32(), which is defined in
include/asm-i386/byteorder.h on line 13. In the worst scenario (with
CONFIG_X86_BSWAP being undefined) it's done in 3 instructions (asm
level). It may actually be faster than the two shift approach in C.

Jamal, sometime later in the evening I'll try the patch you sent,
although my guess is that it won't work (most probably it will produce
what Jarek suggested earlier). What exactly did you mean by "cutdown on
the conversion in u32_change()"?

Cheers,
Radu Rendec

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

On Mon, Nov 05, 2007 at 02:59:21PM +0200, Radu Rendec wrote:
...
> Jamal, I am aware that any computation on the fast path involves some
> performance loss. However, I don't see any speed gain with your patch,
> because you just moved the ntohl() call inside u32_hash_fold(). Since
> u32_hash_fold() is called unconditionally and the only call is that one
> in u32_classify(), htohl() will be called exactly the same number of
> times.

It seems this performance loss shouldn't be so big because ntohl()
is probably quite well optimized in assembler. But, as I've written,
since there is max. 1 byte meaningful to us there is some additional
possibility to get it other way, but I doubt it's worth to bother,
and this can be done with some later patch, after all.

> 
> After almost a week of dealing with this, I still don't think it can be
> solved without byte re-ordering. If you guys think my patch is good, I
> would be more than glad to send it properly (change the comments as
> Jarek suggested and use git). Since I'm quite a newbie with git and
> haven't worked with kernel maintainers before, please be patient if it's
> not perfect at the first attempt :) What tree/branch should I make the
> patch against?

If we manage to convince Jamal, IMHO a patch to something current like
2.6.24-rc1-git14 (or maybe -rc2 soon), should suffice (plus some
options to diff to get function names etc. eg.: diff -Nurp). Try with
Documentation/SubmittingPatches. Git isn't necessary at all. And don't
forget about a changelog.

Regards,
Jarek P.

Re: Endianness problem with u32 classifier hash masks

[jamal]

On Mon, 2007-05-11 at 14:52 +0100, Jarek Poplawski wrote:

> It seems this performance loss shouldn't be so big because ntohl()
> is probably quite well optimized in assembler. But, as I've written,
> since there is max. 1 byte meaningful to us there is some additional
> possibility to get it other way, but I doubt it's worth to bother,
> and this can be done with some later patch, after all.

Agreed on optimizing later. It will probably keep nagging at me for
sometime....

> If we manage to convince Jamal, IMHO a patch to something current like
> 2.6.24-rc1-git14 (or maybe -rc2 soon), should suffice (plus some
> options to diff to get function names etc. eg.: diff -Nurp). Try with
> Documentation/SubmittingPatches. Git isn't necessary at all. And don't
> forget about a changelog.

That code hasnt changed at all in a few years, so even against
2.6.24-rc1 should be fine and can be applied cleanly to Daves net-2.6.
Radu, please refer to my earlier email on things to try.

cheers,
jamal

Re: Endianness problem with u32 classifier hash masks

[Radu Rendec]

On Mon, 2007-11-05 at 09:06 -0500, jamal wrote:
> On Mon, 2007-05-11 at 14:52 +0100, Jarek Poplawski wrote:
> 
...
> > If we manage to convince Jamal, IMHO a patch to something current like
> > 2.6.24-rc1-git14 (or maybe -rc2 soon), should suffice (plus some
> > options to diff to get function names etc. eg.: diff -Nurp). Try with
> > Documentation/SubmittingPatches. Git isn't necessary at all. And don't
> > forget about a changelog.
> 
> That code hasnt changed at all in a few years, so even against
> 2.6.24-rc1 should be fine and can be applied cleanly to Daves net-2.6.
> Radu, please refer to my earlier email on things to try.

Ok, silly procmail rules + threaded view = bad idea. I just didn't see
your last messages earlier when I replied. Sorry!

But still, Jamal, I need more explanations on what you meant by "cutdown
on the conversion in u32_change()". And, before proceeding, I'd like to
see your reply to Jarek's last email (at 15:49 +0100) about not getting
0xff in the end.

Jarek, because I have to test anyway, I'll include ffs(mask) in my patch
and have it tested too.

I already have a clone of Dave's net-2.6 tree, so it shouldn't be such a
big effort to use git after all. I can also make the patch against
2.6.24-rc1, so please tell me which is more convinient for you.

Cheers,
Radu Rendec

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

Radu Rendec wrote, On 11/05/2007 06:31 PM:

> On Mon, 2007-11-05 at 09:06 -0500, jamal wrote:
>> On Mon, 2007-05-11 at 14:52 +0100, Jarek Poplawski wrote:
>>
> ...
>>> If we manage to convince Jamal, IMHO a patch to something current like
>>> 2.6.24-rc1-git14 (or maybe -rc2 soon), should suffice (plus some
>>> options to diff to get function names etc. eg.: diff -Nurp). Try with
>>> Documentation/SubmittingPatches. Git isn't necessary at all. And don't
>>> forget about a changelog.
>> That code hasnt changed at all in a few years, so even against
>> 2.6.24-rc1 should be fine and can be applied cleanly to Daves net-2.6.
>> Radu, please refer to my earlier email on things to try.
> 
> Ok, silly procmail rules + threaded view = bad idea. I just didn't see
> your last messages earlier when I replied. Sorry!
> 
> But still, Jamal, I need more explanations on what you meant by "cutdown
> on the conversion in u32_change()". And, before proceeding, I'd like to
> see your reply to Jarek's last email (at 15:49 +0100) about not getting
> 0xff in the end.


Radu, as far as I know Jamal (from reading) he most probably is busy with
some conference! Since these patches aren't so big I think you could
try Jamal's at first, and if it doesn't work, and nothing new from Jamal
in the meantime, resend your version. Cutdown in u32_change() seems to
add more to the fastpath, but maybe Jamal thinks about something else.

> 
> Jarek, because I have to test anyway, I'll include ffs(mask) in my patch
> and have it tested too.


Thanks! But, I did it wrong: + 1 is unnecessary. And since, ffs() checks
for 0 anyway, this should be simpler:

- {
- 	u8 i = 0;
- 	u32 mask = s->hmask;
- 	if (mask) {
- 		while (!(mask & 1)) {
- 			i++;
- 			mask>>=1;
- 		}
- 	}
- 	n->fshift = i;
+ 	n->fshift = ffs(s->hmask);
- }

Plus maybe (u8) cast on warnings...

On the other hand, only now I see here is some hack (or bug) with this
u8, so ffs() would mean a change here. I definitely need to rethink this.
So, it's probably better to make and test this ffs() patch separately
(2 parts).

> 
> I already have a clone of Dave's net-2.6 tree, so it shouldn't be such a
> big effort to use git after all. I can also make the patch against
> 2.6.24-rc1, so please tell me which is more convinient for you.


Since, there is only this one file, with no changes, there will be no
difference, so it's up to your taste.

Cheers,

Jarek P.

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

Jarek Poplawski wrote, On 11/05/2007 10:06 PM:

> Radu Rendec wrote, On 11/05/2007 06:31 PM:

...

>> Jarek, because I have to test anyway, I'll include ffs(mask) in my patch
>> and have it tested too.
> 
> 
> Thanks! But, I did it wrong: + 1 is unnecessary. And since, ffs() checks
> for 0 anyway, this should be simpler:
> 
> - {
> - 	u8 i = 0;
> - 	u32 mask = s->hmask;
> - 	if (mask) {
> - 		while (!(mask & 1)) {
> - 			i++;
> - 			mask>>=1;
> - 		}
> - 	}
> - 	n->fshift = i;
> + 	n->fshift = ffs(s->hmask);
> - }
> 
> Plus maybe (u8) cast on warnings...
> 
> On the other hand, only now I see here is some hack (or bug) with this
> u8, so ffs() would mean a change here. I definitely need to rethink this.

> So, it's probably better to make and test this ffs() patch separately
> (2 parts).


Sorry, I'm only sleeping... u8 is fine of course, and it could be 1 part
as well, or as you like!

Jarek P.

Re: Endianness problem with u32 classifier hash masks

[jamal]

On Mon, 2007-05-11 at 22:06 +0100, Jarek Poplawski wrote:
> Radu Rendec wrote, On 11/05/2007 06:31 PM:

> > But still, Jamal, I need more explanations on what you meant by "cutdown
> > on the conversion in u32_change()". 

I meant that it didnt seem necessary to me you have to do the conversion
back and forth of the hmask as you do in the u32_change(). The basis of
the patch i posted - which is based on yours - is to remove that change.
If that doesnt work, please just send your patch as is and we can think
of optimization later.

> > And, before proceeding, I'd like to
> > see your reply to Jarek's last email (at 15:49 +0100) about not getting
> > 0xff in the end.

On paper i get the same result with the new or old scheme for the bucket selection.
As i stated on the patch - i never did test the theory.

> Radu, as far as I know Jamal (from reading) he most probably is busy with
> some conference! 

I actually have a day job and have to show up and meet TheMan, Jarek;->
Most of the days at work, i dont have time to look at external email
account - but you can bet all horses you own i will get back to you
within a few hours if you CC me on email.

> Since these patches aren't so big I think you could
> try Jamal's at first, and if it doesn't work, and nothing new from Jamal
> in the meantime, resend your version. Cutdown in u32_change() seems to
> add more to the fastpath, but maybe Jamal thinks about something else.

I mean do most work on slow/config path.

> > Jarek, because I have to test anyway, I'll include ffs(mask) in my patch
> > and have it tested too.

Lets have two patches - one for the le/be bucket selection and another
for ffs.

cheers,
jamal

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

jamal wrote, On 11/05/2007 11:27 PM:

> On Mon, 2007-05-11 at 22:06 +0100, Jarek Poplawski wrote:
>> Radu Rendec wrote, On 11/05/2007 06:31 PM:
> 
>>> But still, Jamal, I need more explanations on what you meant by "cutdown
>>> on the conversion in u32_change()". 
> 
> I meant that it didnt seem necessary to me you have to do the conversion
> back and forth of the hmask as you do in the u32_change(). The basis of
> the patch i posted - which is based on yours - is to remove that change.
> If that doesnt work, please just send your patch as is and we can think
> of optimization later.
> 

>>> And, before proceeding, I'd like to

>>> see your reply to Jarek's last email (at 15:49 +0100) about not getting
>>> 0xff in the end.
> 
> On paper i get the same result with the new or old scheme for the bucket selection.
> As i stated on the patch - i never did test the theory.
> 


In Radu's patch all calculations are done with data in host order, and
still only this one transformation on the fast path. In your version orders
are mixed, and this makes a difference. And, since the old scheme gives
wrong result on little endian, I don't get it why you would want it again?
So, with your patch with the same address and mask: 00.00.0f.f0 (host order
on little endian) we have:

on big endian (net and host order):
f0.0f.00.00 >> 4  gives: ff.00.00.00 with lsb: ff
on little endian (net order):
f0.0f.00.00 >> 4  gives: 0f.00.0f.00 then ntohl: 00.0f.00.0f with lsb: 0f
on little endian with Radu's patch (host order):
00.00.0f.f0 >> 4  gives: 00.00.00.ff with lsb: ff


>> Radu, as far as I know Jamal (from reading) he most probably is busy with
>> some conference! 
> 
> I actually have a day job and have to show up and meet TheMan, Jarek;->
> Most of the days at work, i dont have time to look at external email
> account - but you can bet all horses you own i will get back to you
> within a few hours if you CC me on email.


No offence! I've thought Radu gets a bit impatient, and don't know if he
knows about your scientific and international achievements. On the other
hand I can't imagine why anybody would ever like to go out of Canada!
(Btw, in Polish the second meaning of Kanada is something like paradise
or extreme welfare.) And, on the other hand, I'm very honoured, but I'm
a really modest guy, far from this universities' high life here...

> 
>> Since these patches aren't so big I think you could
>> try Jamal's at first, and if it doesn't work, and nothing new from Jamal
>> in the meantime, resend your version. Cutdown in u32_change() seems to
>> add more to the fastpath, but maybe Jamal thinks about something else.
> 
> I mean do most work on slow/config path.
> 


We have hshift & hamask from there.

Cheers,
Jarek P.

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

Jarek Poplawski wrote, On 11/06/2007 01:02 AM:
...

> on little endian (net order):
> f0.0f.00.00 >> 4  gives: 0f.00.0f.00 then ntohl: 00.0f.00.0f with lsb: 0f

should be:
f0.0f.00.00 >> 4  gives: 0f.00.f0.00 then ntohl: 00.f0.00.0f with lsb: 0f

Jarek "Sleeping" P.

Re: Endianness problem with u32 classifier hash masks

[Radu Rendec]

On Tue, 2007-11-06 at 01:02 +0100, Jarek Poplawski wrote:
> > I meant that it didnt seem necessary to me you have to do the conversion
> > back and forth of the hmask as you do in the u32_change(). The basis of
> > the patch i posted - which is based on yours - is to remove that change.
> > If that doesnt work, please just send your patch as is and we can think
> > of optimization later.

Yup, you're right. Bitwise anding is the same regardless of the byte
ordering of the operands. As long as you don't have one operand in host
order and the other in net order, it's ok.

However, Jarek's computations with his mask and your patch seemed
correct to me yesterday. And I think I know the answer: data must be
changed to host order _before_ shifting. I mean something like this:

static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel
*sel, u8 fshift)
{
       unsigned h = ntohl(key & sel->hmask) >> fshift;
       return h;
}

And everything else remains unchanged (except for the ntohl() applied to
hmask before computing fshift). In other words, the idea behind your
patch now seems to be right (it's easier not to convert the hmask back
and forth as long as ntohl() in u32_hash_fold() is applied before
shifting).

> > On paper i get the same result with the new or old scheme for the bucket selection.
> > As i stated on the patch - i never did test the theory.

Well, neither did I (about what I stated above). But still I think,
Jarek was right yesterday and I can't figure out how it worked for you
on paper. How about this new version?

> In Radu's patch all calculations are done with data in host order, and
> still only this one transformation on the fast path. In your version orders
> are mixed, and this makes a difference. And, since the old scheme gives
> wrong result on little endian, I don't get it why you would want it again?
> So, with your patch with the same address and mask: 00.00.0f.f0 (host order
> on little endian) we have:
> 
> on big endian (net and host order):
> f0.0f.00.00 >> 4  gives: ff.00.00.00 with lsb: ff
> on little endian (net order):
> f0.0f.00.00 >> 4  gives: 0f.00.0f.00 then ntohl: 00.0f.00.0f with lsb: 0f
> on little endian with Radu's patch (host order):
> 00.00.0f.f0 >> 4  gives: 00.00.00.ff with lsb: ff

Ok, but now (moving ntohl() before shifting), it's like this:
ntohl(f0.0f.00.00) gives: 00.00.0f.f0, then >>4 gives 00.00.00.ff

> >> Radu, as far as I know Jamal (from reading) he most probably is busy with
> >> some conference! 
> > 
> > I actually have a day job and have to show up and meet TheMan, Jarek;->
> > Most of the days at work, i dont have time to look at external email
> > account - but you can bet all horses you own i will get back to you
> > within a few hours if you CC me on email.
> 
> 
> No offence! I've thought Radu gets a bit impatient, and don't know if he
> knows about your scientific and international achievements. On the other
> hand I can't imagine why anybody would ever like to go out of Canada!
> (Btw, in Polish the second meaning of Kanada is something like paradise
> or extreme welfare.) And, on the other hand, I'm very honoured, but I'm
> a really modest guy, far from this universities' high life here...

Actually I'm not impatient at all, because the shaping machine at the
ISP where I work is already patched with my original patch, and cpu
usage has gone from 100% to 8% after implementing hashes ;->

Still, I thought it would be a good idea to share what I found out with
the maintainers and have it fixed in the next kernel release. Now all I
want is to help you out fixing it "right" and test it. And... who
knows... if it's fixed in the official kernel, I won't need to bother
patching if i upgrade my machine ;->

BTW, I also have a steady job and don't have much time there to work on
the kernel. It's ok.

> >> Since these patches aren't so big I think you could
> >> try Jamal's at first, and if it doesn't work, and nothing new from Jamal
> >> in the meantime, resend your version. Cutdown in u32_change() seems to
> >> add more to the fastpath, but maybe Jamal thinks about something else.
> > 
> > I mean do most work on slow/config path.

Well, I think it's pretty clear now: I'll try my version of Jamal's
patch :) But not right now, because I also have to show up at work.
 
Cheers,

Radu Rendec

Re: Endianness problem with u32 classifier hash masks

[jamal]

On Tue, 2007-06-11 at 10:09 +0200, Radu Rendec wrote:

> Yup, you're right. Bitwise anding is the same regardless of the byte
> ordering of the operands. As long as you don't have one operand in host
> order and the other in net order, it's ok.

Ok

> However, Jarek's computations with his mask and your patch seemed
> correct to me yesterday. And I think I know the answer: data must be
> changed to host order _before_ shifting. I mean something like this:
> 
> static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel
> *sel, u8 fshift)
> {
>        unsigned h = ntohl(key & sel->hmask) >> fshift;
>        return h;
> }

Even better than what i suggested ;->

> > > On paper i get the same result with the new or old scheme for the bucket selection.
> > > As i stated on the patch - i never did test the theory.
> 
> Well, neither did I (about what I stated above). But still I think,
> Jarek was right yesterday and I can't figure out how it worked for you
> on paper. How about this new version?

Looks good - we can think of optimizing later.

> Well, I think it's pretty clear now: I'll try my version of Jamal's
> patch :) 

Which derived from your original patch using little effort in comparison
to yours. All the hardwork is yours.
You did quiet an impressive debug work. Please give yourself a little
pat on the back for me.

> But not right now, because I also have to show up at work.

I empathize. 
Please send two patches instead of one. One for this and the next for
the ffs conversion (please run some simple tests in both cases).

Jarek,
Heres a few more derivations of Canada for you:

Legend has it that Canada's name is derived from  
"settlement" in Iroquoian (One the First Nations in present day Canada).
I think it was pronounced "Kanata"
An alternative legend says the early Spanish called it acánada  meaning
"nothing here"

I tend to believe the Iroquoian version since to this day Canada
continues to serve as a new settlement for many people. And the Spanish
were totaly wrong - there is something here ;-> At least Tim Hortons
coffee.

cheers,
jamal

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

On Tue, Nov 06, 2007 at 08:34:31AM -0500, jamal wrote:
> On Tue, 2007-06-11 at 10:09 +0200, Radu Rendec wrote:
> 
> > Yup, you're right. Bitwise anding is the same regardless of the byte
> > ordering of the operands. As long as you don't have one operand in host
> > order and the other in net order, it's ok.
> 
> Ok
> 
> > However, Jarek's computations with his mask and your patch seemed
> > correct to me yesterday. And I think I know the answer: data must be
> > changed to host order _before_ shifting. I mean something like this:
> > 
> > static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel
> > *sel, u8 fshift)
> > {
> >        unsigned h = ntohl(key & sel->hmask) >> fshift;
> >        return h;
> > }
> 
> Even better than what i suggested ;->

Yes, it saves one htonl() on the slow path!

> 
> > > > On paper i get the same result with the new or old scheme for the bucket selection.
> > > > As i stated on the patch - i never did test the theory.
> > 
> > Well, neither did I (about what I stated above). But still I think,
> > Jarek was right yesterday and I can't figure out how it worked for you
> > on paper. How about this new version?
> 
> Looks good - we can think of optimizing later.
> 
> > Well, I think it's pretty clear now: I'll try my version of Jamal's
> > patch :) 
> 
> Which derived from your original patch using little effort in comparison
> to yours. All the hardwork is yours.
> You did quiet an impressive debug work. Please give yourself a little
> pat on the back for me.

Wait a minute! Don't forget to take a picture or something!

> 
> > But not right now, because I also have to show up at work.
> 
> I empathize. 
> Please send two patches instead of one. One for this and the next for
> the ffs conversion (please run some simple tests in both cases).
> 
> Jarek,
> Heres a few more derivations of Canada for you:
> 
> Legend has it that Canada's name is derived from  
> "settlement" in Iroquoian (One the First Nations in present day Canada).
> I think it was pronounced "Kanata"
> An alternative legend says the early Spanish called it acánada  meaning
> "nothing here"
> 
> I tend to believe the Iroquoian version since to this day Canada
> continues to serve as a new settlement for many people. And the Spanish
> were totaly wrong - there is something here ;-> At least Tim Hortons
> coffee.

Nice stories! Thanks. Btw, with this Polish saying, the strangest thing
is US was always preferred as a settlment, after all.

Regards,
Jarek P.

Re: Endianness problem with u32 classifier hash masks

[jamal]

On Tue, 2007-06-11 at 15:25 +0100, Jarek Poplawski wrote:

> Yes, it saves one htonl() on the slow path!

Would it feel better to say grew down exponentially from version 1 to
3? ;->

> > Please give yourself a little pat on the back for me.
> 
> Wait a minute! Don't forget to take a picture or something!

He needs the other arm for balance;-> so unless someone else takes the
photo, i would say that should he be successful taking the photo, that
achievement itself needs a double-self-pat-on-the-back (which i am going
to say if he can also take a photo of needs to go on some records book)

cheers,
jamal

Re: Endianness problem with u32 classifier hash masks

[Radu Rendec]

On Tue, 2007-11-06 at 09:43 -0500, jamal wrote:
> On Tue, 2007-06-11 at 15:25 +0100, Jarek Poplawski wrote:
> 
> > Yes, it saves one htonl() on the slow path!
> 
> Would it feel better to say grew down exponentially from version 1 to
> 3? ;->

Not only it saves one htonl(), but also keeps the code readable :)
Computing offsets within the rtnetlink response skb and applying htonl()
there is quite tricky and might get broken if RTA_PUT() is changed.
Unfortunately I spent about an hour figuring out how to do that :))

The bad news is that today I haven't got the chance to work on the two
patches. But the good news is that I managed to finish the (urgent) task
that had been assigned to me at work, and tomorrow I will be able to
work on the kernel and test it leisurely.

> > > Please give yourself a little pat on the back for me.
> > 
> > Wait a minute! Don't forget to take a picture or something!
> 
> He needs the other arm for balance;-> so unless someone else takes the
> photo, i would say that should he be successful taking the photo, that
> achievement itself needs a double-self-pat-on-the-back (which i am going
> to say if he can also take a photo of needs to go on some records book)

I'm sorry to disappoint you, guys, but most probably I'll pat myself on
the back here at work, after I get enthusiastic about the patches. So my
fellow colleagues will take the picture for me. If I get really
enthusiastic, then I'll have my both arms available for patting :)

Cheers,

Radu

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

Radu Rendec wrote, On 11/06/2007 06:00 PM:

> On Tue, 2007-11-06 at 09:43 -0500, jamal wrote:
>> On Tue, 2007-06-11 at 15:25 +0100, Jarek Poplawski wrote:
>>
>>> Yes, it saves one htonl() on the slow path!
>> Would it feel better to say grew down exponentially from version 1 to
>> 3? ;->


Sure, but I felt much better after this:

> Actually I'm not impatient at all, because the shaping machine at the
> ISP where I work is already patched with my original patch, and cpu
> usage has gone from 100% to 8% after implementing hashes ;->
 

I'm not so lucky to see this code working, so I didn't expect earlier
this place could be so meaningful. As a matter of fact I've thought
Jamal exaggerates about this fast path... Now, I try to understand
why it didn't come out earlier. Anyway, Radu - my congratulations!

>>>> Please give yourself a little pat on the back for me.
>>> Wait a minute! Don't forget to take a picture or something!
>> He needs the other arm for balance;-> so unless someone else takes the
>> photo, i would say that should he be successful taking the photo, that
>> achievement itself needs a double-self-pat-on-the-back (which i am going
>> to say if he can also take a photo of needs to go on some records book)
> 
> I'm sorry to disappoint you, guys, but most probably I'll pat myself on
> the back here at work, after I get enthusiastic about the patches. So my
> fellow colleagues will take the picture for me. If I get really
> enthusiastic, then I'll have my both arms available for patting :)


Alas, I don't take pictures either, but, it seems, any way should be
good if it's visible for whom are you patted by!

Cheers,
Jarek P.

Re: Endianness problem with u32 classifier hash masks

[David Miller]

From: Radu Rendec <radu.rendec@ines.ro>
Date: Tue, 06 Nov 2007 19:00:16 +0200

> On Tue, 2007-11-06 at 09:43 -0500, jamal wrote:
> > On Tue, 2007-06-11 at 15:25 +0100, Jarek Poplawski wrote:
> > 
> > > Yes, it saves one htonl() on the slow path!
> > 
> > Would it feel better to say grew down exponentially from version 1 to
> > 3? ;->
> 
> Not only it saves one htonl(), but also keeps the code readable :)
> Computing offsets within the rtnetlink response skb and applying htonl()
> there is quite tricky and might get broken if RTA_PUT() is changed.
> Unfortunately I spent about an hour figuring out how to do that :))
> 
> The bad news is that today I haven't got the chance to work on the two
> patches. But the good news is that I managed to finish the (urgent) task
> that had been assigned to me at work, and tomorrow I will be able to
> work on the kernel and test it leisurely.

I've grown impatient and done the work for you :-)  I've applied
the patch below to my tree, thank you!

If someone wants to send me the ffs() thing relative to this,
I'd appreciate it.  Thanks again!

>From 8e36263f10a054479636b57943cdeaf37470acc5 Mon Sep 17 00:00:00 2001
From: Radu Rendec <radu.rendec@ines.ro>
Date: Wed, 7 Nov 2007 01:20:12 -0800
Subject: [PATCH] [PKT_SCHED] CLS_U32: Fix endianness problem with u32 classifier hash masks.

From: Radu Rendec <radu.rendec@ines.ro>

While trying to implement u32 hashes in my shaping machine I ran into
a possible bug in the u32 hash/bucket computing algorithm
(net/sched/cls_u32.c).

The problem occurs only with hash masks that extend over the octet
boundary, on little endian machines (where htonl() actually does
something).

Let's say that I would like to use 0x3fc0 as the hash mask. This means
8 contiguous "1" bits starting at b6. With such a mask, the expected
(and logical) behavior is to hash any address in, for instance,
192.168.0.0/26 in bucket 0, then any address in 192.168.0.64/26 in
bucket 1, then 192.168.0.128/26 in bucket 2 and so on.

This is exactly what would happen on a big endian machine, but on
little endian machines, what would actually happen with current
implementation is 0x3fc0 being reversed (into 0xc03f0000) by htonl()
in the userspace tool and then applied to 192.168.x.x in the u32
classifier. When shifting right by 16 bits (rank of first "1" bit in
the reversed mask) and applying the divisor mask (0xff for divisor
256), what would actually remain is 0x3f applied on the "168" octet of
the address.

One could say is this can be easily worked around by taking endianness
into account in userspace and supplying an appropriate mask (0xfc03)
that would be turned into contiguous "1" bits when reversed
(0x03fc0000). But the actual problem is the network address (inside
the packet) not being converted to host order, but used as a
host-order value when computing the bucket.

Let's say the network address is written as n31 n30 ... n0, with n0
being the least significant bit. When used directly (without any
conversion) on a little endian machine, it becomes n7 ... n0 n8 ..n15
etc in the machine's registers. Thus bits n7 and n8 would no longer be
adjacent and 192.168.64.0/26 and 192.168.128.0/26 would no longer be
consecutive.

The fix is to apply ntohl() on the hmask before computing fshift,
and in u32_hash_fold() convert the packet data to host order before
shifting down by fshift.

With helpful feedback from Jamal Hadi Salim and Jarek Poplawski.

Signed-off-by: David S. Miller <davem@davemloft.net>
---
 net/sched/cls_u32.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 9e98c6e..5317102 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -91,7 +91,7 @@ static struct tc_u_common *u32_list;
 
 static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel, u8 fshift)
 {
-	unsigned h = (key & sel->hmask)>>fshift;
+	unsigned h = ntohl(key & sel->hmask)>>fshift;
 
 	return h;
 }
@@ -615,7 +615,7 @@ static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
 	n->handle = handle;
 {
 	u8 i = 0;
-	u32 mask = s->hmask;
+	u32 mask = ntohl(s->hmask);
 	if (mask) {
 		while (!(mask & 1)) {
 			i++;
-- 
1.5.3.5

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

On Wed, Nov 07, 2007 at 01:22:20AM -0800, David Miller wrote:
> From: Radu Rendec <radu.rendec@ines.ro>
> Date: Tue, 06 Nov 2007 19:00:16 +0200
> 
> > On Tue, 2007-11-06 at 09:43 -0500, jamal wrote:
> > > On Tue, 2007-06-11 at 15:25 +0100, Jarek Poplawski wrote:
> > > 
> > > > Yes, it saves one htonl() on the slow path!
> > > 
> > > Would it feel better to say grew down exponentially from version 1 to
> > > 3? ;->
> > 
> > Not only it saves one htonl(), but also keeps the code readable :)
> > Computing offsets within the rtnetlink response skb and applying htonl()
> > there is quite tricky and might get broken if RTA_PUT() is changed.
> > Unfortunately I spent about an hour figuring out how to do that :))
> > 
> > The bad news is that today I haven't got the chance to work on the two
> > patches. But the good news is that I managed to finish the (urgent) task
> > that had been assigned to me at work, and tomorrow I will be able to
> > work on the kernel and test it leisurely.
> 
> I've grown impatient and done the work for you :-)  I've applied
> the patch below to my tree, thank you!
> 
> If someone wants to send me the ffs() thing relative to this,
> I'd appreciate it.  Thanks again!

...And Radu has spend so much time on this git vs. which tree to cut
for the beginning... I hope this ffs() patch will be enough to check
on some bush at least!

> 
> From 8e36263f10a054479636b57943cdeaf37470acc5 Mon Sep 17 00:00:00 2001
> From: Radu Rendec <radu.rendec@ines.ro>
> Date: Wed, 7 Nov 2007 01:20:12 -0800
> Subject: [PATCH] [PKT_SCHED] CLS_U32: Fix endianness problem with u32 classifier hash masks.
> 
> From: Radu Rendec <radu.rendec@ines.ro>
> 
> While trying to implement u32 hashes in my shaping machine I ran into
> a possible bug in the u32 hash/bucket computing algorithm
> (net/sched/cls_u32.c).
> 
> The problem occurs only with hash masks that extend over the octet
> boundary, on little endian machines (where htonl() actually does
> something).
> 
> Let's say that I would like to use 0x3fc0 as the hash mask. This means
> 8 contiguous "1" bits starting at b6. With such a mask, the expected
> (and logical) behavior is to hash any address in, for instance,
> 192.168.0.0/26 in bucket 0, then any address in 192.168.0.64/26 in
> bucket 1, then 192.168.0.128/26 in bucket 2 and so on.
> 
> This is exactly what would happen on a big endian machine, but on
> little endian machines, what would actually happen with current
> implementation is 0x3fc0 being reversed (into 0xc03f0000) by htonl()
> in the userspace tool and then applied to 192.168.x.x in the u32
> classifier. When shifting right by 16 bits (rank of first "1" bit in
> the reversed mask) and applying the divisor mask (0xff for divisor
> 256), what would actually remain is 0x3f applied on the "168" octet of
> the address.
> 
> One could say is this can be easily worked around by taking endianness
> into account in userspace and supplying an appropriate mask (0xfc03)
> that would be turned into contiguous "1" bits when reversed
> (0x03fc0000). But the actual problem is the network address (inside
> the packet) not being converted to host order, but used as a
> host-order value when computing the bucket.
> 
> Let's say the network address is written as n31 n30 ... n0, with n0
> being the least significant bit. When used directly (without any
> conversion) on a little endian machine, it becomes n7 ... n0 n8 ..n15
> etc in the machine's registers. Thus bits n7 and n8 would no longer be
> adjacent and 192.168.64.0/26 and 192.168.128.0/26 would no longer be
> consecutive.
> 
> The fix is to apply ntohl() on the hmask before computing fshift,
> and in u32_hash_fold() convert the packet data to host order before
> shifting down by fshift.
> 
> With helpful feedback from Jamal Hadi Salim and Jarek Poplawski.

Acked-by: Jarek Poplawski <jarkao2@o2.pl>

> 
> Signed-off-by: David S. Miller <davem@davemloft.net>
> ---
>  net/sched/cls_u32.c |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
> index 9e98c6e..5317102 100644
> --- a/net/sched/cls_u32.c
> +++ b/net/sched/cls_u32.c
> @@ -91,7 +91,7 @@ static struct tc_u_common *u32_list;
>  
>  static __inline__ unsigned u32_hash_fold(u32 key, struct tc_u32_sel *sel, u8 fshift)
>  {
> -	unsigned h = (key & sel->hmask)>>fshift;
> +	unsigned h = ntohl(key & sel->hmask)>>fshift;
>  
>  	return h;
>  }
> @@ -615,7 +615,7 @@ static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
>  	n->handle = handle;
>  {
>  	u8 i = 0;
> -	u32 mask = s->hmask;
> +	u32 mask = ntohl(s->hmask);
>  	if (mask) {
>  		while (!(mask & 1)) {
>  			i++;
> -- 
> 1.5.3.5
> 

Re: Endianness problem with u32 classifier hash masks

[jamal]

On Wed, 2007-07-11 at 01:22 -0800, David Miller wrote:

> @@ -615,7 +615,7 @@ static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
>  	n->handle = handle;
>  {
>  	u8 i = 0;
> -	u32 mask = s->hmask;
> +	u32 mask = ntohl(s->hmask);


Is this line needed? Radu?

cheers,
jamal

Re: Endianness problem with u32 classifier hash masks

[Radu Rendec]

On Wed, 2007-11-07 at 08:42 -0500, jamal wrote:
> On Wed, 2007-07-11 at 01:22 -0800, David Miller wrote:
> 
> > @@ -615,7 +615,7 @@ static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
> >  	n->handle = handle;
> >  {
> >  	u8 i = 0;
> > -	u32 mask = s->hmask;
> > +	u32 mask = ntohl(s->hmask);
> 
> 
> Is this line needed? Radu?

Yup. Without it, the number of bits to shift would be computed on the
network ordered mask. The shift in u32_hash_fold() is done on a host
ordered u32 (obtained from applying the mask on the packet data).

Shifting the host ordered u32 with number of bits obtained from network
ordered mask would most probably break things.

I've just compiled the kernel from a fresh clone of Dave's tree (u32
patch included) and I'm about to test it.

Dave, thanks a lot for adding the patch to your tree. But I guess you
didn't test it. I'll get back to you in max 1 hour and tell you the
results.

If everything goes well, then I'll move on to testing the ffs() patch.

Cheers,

Radu

Re: Endianness problem with u32 classifier hash masks

[Radu Rendec]

On Wed, 2007-11-07 at 01:22 -0800, David Miller wrote:
> I've grown impatient and done the work for you :-)  I've applied
> the patch below to my tree, thank you!
> 
> If someone wants to send me the ffs() thing relative to this,
> I'd appreciate it.  Thanks again!

Thanks again for making the patch and applying. I've just tested it and
it works like a charm.

Now moving on to the ffs() thing. I will send the patch later if it
works.

Cheers,
Radu

[PATCH] [PKT_SCHED] CLS_U32: Use ffs() instead of C code on hash mask to get first set bit.

[Radu Rendec]

Computing the rank of the first set bit in the hash mask (for using later
in u32_hash_fold()) was done with plain C code. Using ffs() instead makes
the code more readable and improves performance (since ffs() is better
optimized in assembler).

Using the conditional operator on hash mask before applying ntohl() also
saves one ntohl() call if mask is 0.

Signed-off-by: Radu Rendec <radu.rendec@ines.ro>
---
 net/sched/cls_u32.c |   12 +-----------
 1 files changed, 1 insertions(+), 11 deletions(-)

diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
index 5317102..c390082 100644
--- a/net/sched/cls_u32.c
+++ b/net/sched/cls_u32.c
@@ -613,17 +613,7 @@ static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
 	memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
 	n->ht_up = ht;
 	n->handle = handle;
-{
-	u8 i = 0;
-	u32 mask = ntohl(s->hmask);
-	if (mask) {
-		while (!(mask & 1)) {
-			i++;
-			mask>>=1;
-		}
-	}
-	n->fshift = i;
-}
+	n->fshift = s->hmask ? ffs(ntohl(s->hmask)) - 1 : 0;
 
 #ifdef CONFIG_CLS_U32_MARK
 	if (tb[TCA_U32_MARK-1]) {
-- 
1.5.3.2

Re: [PATCH] [PKT_SCHED] CLS_U32: Use ffs() instead of C code on hash mask to get first set bit.

[Jarek Poplawski]

On Thu, Nov 08, 2007 at 01:07:47PM +0200, Radu Rendec wrote:
> Computing the rank of the first set bit in the hash mask (for using later
> in u32_hash_fold()) was done with plain C code. Using ffs() instead makes
> the code more readable and improves performance (since ffs() is better
> optimized in assembler).
> 
> Using the conditional operator on hash mask before applying ntohl() also
> saves one ntohl() call if mask is 0.
> 
> Signed-off-by: Radu Rendec <radu.rendec@ines.ro>

Signed-off-by: Jarek Poplawski <jarkao2@o2.pl>

> ---
>  net/sched/cls_u32.c |   12 +-----------
>  1 files changed, 1 insertions(+), 11 deletions(-)
> 
> diff --git a/net/sched/cls_u32.c b/net/sched/cls_u32.c
> index 5317102..c390082 100644
> --- a/net/sched/cls_u32.c
> +++ b/net/sched/cls_u32.c
> @@ -613,17 +613,7 @@ static int u32_change(struct tcf_proto *tp, unsigned long base, u32 handle,
>  	memcpy(&n->sel, s, sizeof(*s) + s->nkeys*sizeof(struct tc_u32_key));
>  	n->ht_up = ht;
>  	n->handle = handle;
> -{
> -	u8 i = 0;
> -	u32 mask = ntohl(s->hmask);
> -	if (mask) {
> -		while (!(mask & 1)) {
> -			i++;
> -			mask>>=1;
> -		}
> -	}
> -	n->fshift = i;
> -}
> +	n->fshift = s->hmask ? ffs(ntohl(s->hmask)) - 1 : 0;
>  
>  #ifdef CONFIG_CLS_U32_MARK
>  	if (tb[TCA_U32_MARK-1]) {
> -- 
> 1.5.3.2
> 

Re: [PATCH] [PKT_SCHED] CLS_U32: Use ffs() instead of C code on hash mask to get first set bit.

[jamal]

On Thu, 2007-08-11 at 13:07 +0200, Radu Rendec wrote:
> Computing the rank of the first set bit in the hash mask (for using later
> in u32_hash_fold()) was done with plain C code. Using ffs() instead makes
> the code more readable and improves performance (since ffs() is better
> optimized in assembler).
> 
> Using the conditional operator on hash mask before applying ntohl() also
> saves one ntohl() call if mask is 0.
> 
> Signed-off-by: Radu Rendec <radu.rendec@ines.ro>

Acked-by: Jamal Hadi Salim <hadi@cyberus.ca>


cheers,
jamal

Re: [PATCH] [PKT_SCHED] CLS_U32: Use ffs() instead of C code on hash mask to get first set bit.

[David Miller]

From: jamal <hadi@cyberus.ca>
Date: Thu, 08 Nov 2007 08:45:31 -0500

> On Thu, 2007-08-11 at 13:07 +0200, Radu Rendec wrote:
> > Computing the rank of the first set bit in the hash mask (for using later
> > in u32_hash_fold()) was done with plain C code. Using ffs() instead makes
> > the code more readable and improves performance (since ffs() is better
> > optimized in assembler).
> > 
> > Using the conditional operator on hash mask before applying ntohl() also
> > saves one ntohl() call if mask is 0.
> > 
> > Signed-off-by: Radu Rendec <radu.rendec@ines.ro>
> 
> Acked-by: Jamal Hadi Salim <hadi@cyberus.ca>

Applied, thanks everyone.

Re: Endianness problem with u32 classifier hash masks

[jamal]

On Mon, 2007-05-11 at 10:12 +0100, Jarek Poplawski wrote:

> BTW: when looking around this I think, maybe, in u32_change():
> 
> 1) if (--divisor > 0x100) should be probably ">=", 

Does it really matter? Divisor can be max of 0xff.

> but is it really needed to check this 2 times (including tc)?

I dont mind letting users shoot themselves in the foot by sending crap.
If it can be avoided with simplicity, then better.

> 2) this while() loop for n->fshift could be replaced with ffs()?

I think so. Can you please send a patch (after some testing of course
maybe using Radu's test data)?

cheers,
jamal

Re: Endianness problem with u32 classifier hash masks

[Jarek Poplawski]

On Mon, Nov 05, 2007 at 08:47:06AM -0500, jamal wrote:
> On Mon, 2007-05-11 at 10:12 +0100, Jarek Poplawski wrote:
> 
> > BTW: when looking around this I think, maybe, in u32_change():
> > 
> > 1) if (--divisor > 0x100) should be probably ">=", 
> 
> Does it really matter? Divisor can be max of 0xff.

But, according to this max is 0x100... It doesn't really matter,
but we have to wonder which one check is correct if they differ.

> 
> > but is it really needed to check this 2 times (including tc)?
> 
> I dont mind letting users shoot themselves in the foot by sending crap.
> If it can be avoided with simplicity, then better.
> 
> > 2) this while() loop for n->fshift could be replaced with ffs()?
> 
> I think so. Can you please send a patch (after some testing of course
> maybe using Radu's test data)?

Since this would be cosmetics here, I think it could wait for this
main patch. But, since testing isn't my best side, maybe I'd ask
Radu for including this "btw"... I mean only something like this:

  {
  	u8 i = 0;
  	u32 mask = s->hmask;
  	if (mask) {
- 		while (!(mask & 1)) {
- 			i++;
- 			mask>>=1;
- 		}
		i = ffs(mask) + 1;
  	}
  	n->fshift = i;
  }

Thanks,
Jarek P.