[PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Jan Beulich]

... to match its two callers (i.e. the alternative would have been to
swap the arguments at the call sites).

Signed-off-by: Jan Beulich <jbeulich@suse.com>
Cc: Francesco Fusco <ffusco@redhat.com>
Cc: Daniel Borkmann <dborkman@redhat.com>
Cc: Thomas Graf <tgraf@redhat.com>
Cc: David S. Miller <davem@davemloft.net>
---
 arch/x86/lib/hash.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

--- 3.14-rc3-x86-hash-crc32.orig/arch/x86/lib/hash.c
+++ 3.14-rc3-x86-hash-crc32/arch/x86/lib/hash.c
@@ -37,7 +37,7 @@
 #include <asm/cpufeature.h>
 #include <asm/hash.h>
 
-static inline u32 crc32_u32(u32 crc, u32 val)
+static inline u32 crc32_u32(u32 val, u32 crc)
 {
 #ifdef CONFIG_AS_CRC32
 	asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Daniel Borkmann]

On 02/21/2014 11:33 AM, Jan Beulich wrote:
> ... to match its two callers (i.e. the alternative would have been to
> swap the arguments at the call sites).
>
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> Cc: Francesco Fusco <ffusco@redhat.com>
> Cc: Daniel Borkmann <dborkman@redhat.com>
> Cc: Thomas Graf <tgraf@redhat.com>
> Cc: David S. Miller <davem@davemloft.net>
> ---
>   arch/x86/lib/hash.c |    2 +-
>   1 file changed, 1 insertion(+), 1 deletion(-)
>
> --- 3.14-rc3-x86-hash-crc32.orig/arch/x86/lib/hash.c
> +++ 3.14-rc3-x86-hash-crc32/arch/x86/lib/hash.c
> @@ -37,7 +37,7 @@
>   #include <asm/cpufeature.h>
>   #include <asm/hash.h>
>
> -static inline u32 crc32_u32(u32 crc, u32 val)
> +static inline u32 crc32_u32(u32 val, u32 crc)
>   {
>   #ifdef CONFIG_AS_CRC32
>   	asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));

Can you elaborate?

Sorry, I need to ask here (even if it's a stupid question ;)) if this
change is safe to do; are referring to a cleanup or fixing a concrete
bug? The code is a modified version of the DPDK hash which you can find
in [1]. Arguments of the caller are in the correct order, afaik.

   [1] http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_hash_crc.h

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Jan Beulich]

>>> On 22.02.14 at 13:09, Daniel Borkmann <dborkman@redhat.com> wrote:
> On 02/21/2014 11:33 AM, Jan Beulich wrote:
>> ... to match its two callers (i.e. the alternative would have been to
>> swap the arguments at the call sites).
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>> Cc: Francesco Fusco <ffusco@redhat.com>
>> Cc: Daniel Borkmann <dborkman@redhat.com>
>> Cc: Thomas Graf <tgraf@redhat.com>
>> Cc: David S. Miller <davem@davemloft.net>
>> ---
>>   arch/x86/lib/hash.c |    2 +-
>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> --- 3.14-rc3-x86-hash-crc32.orig/arch/x86/lib/hash.c
>> +++ 3.14-rc3-x86-hash-crc32/arch/x86/lib/hash.c
>> @@ -37,7 +37,7 @@
>>   #include <asm/cpufeature.h>
>>   #include <asm/hash.h>
>>
>> -static inline u32 crc32_u32(u32 crc, u32 val)
>> +static inline u32 crc32_u32(u32 val, u32 crc)
>>   {
>>   #ifdef CONFIG_AS_CRC32
>>   	asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));
> 
> Can you elaborate?
> 
> Sorry, I need to ask here (even if it's a stupid question ;)) if this
> change is safe to do; are referring to a cleanup or fixing a concrete
> bug? The code is a modified version of the DPDK hash which you can find
> in [1]. Arguments of the caller are in the correct order, afaik.
> 
>    [1] http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_hash_crc.h 

Yes, that file appears to be correct:

rte_hash_crc_4byte(uint32_t data, uint32_t init_val)

as opposed to 

static inline u32 crc32_u32(u32 crc, u32 val)

(quite obviously data <-> val and crc <-> init_val, supported
by the second argument in each caller being named "seed").

Jan

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Daniel Borkmann]

On 02/24/2014 09:03 AM, Jan Beulich wrote:
>>>> On 22.02.14 at 13:09, Daniel Borkmann <dborkman@redhat.com> wrote:
>> On 02/21/2014 11:33 AM, Jan Beulich wrote:
>>> ... to match its two callers (i.e. the alternative would have been to
>>> swap the arguments at the call sites).
>>>
>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>> Cc: Francesco Fusco <ffusco@redhat.com>
>>> Cc: Daniel Borkmann <dborkman@redhat.com>
>>> Cc: Thomas Graf <tgraf@redhat.com>
>>> Cc: David S. Miller <davem@davemloft.net>
>>> ---
>>>    arch/x86/lib/hash.c |    2 +-
>>>    1 file changed, 1 insertion(+), 1 deletion(-)
>>>
>>> --- 3.14-rc3-x86-hash-crc32.orig/arch/x86/lib/hash.c
>>> +++ 3.14-rc3-x86-hash-crc32/arch/x86/lib/hash.c
>>> @@ -37,7 +37,7 @@
>>>    #include <asm/cpufeature.h>
>>>    #include <asm/hash.h>
>>>
>>> -static inline u32 crc32_u32(u32 crc, u32 val)
>>> +static inline u32 crc32_u32(u32 val, u32 crc)
>>>    {
>>>    #ifdef CONFIG_AS_CRC32
>>>    	asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));
>>
>> Can you elaborate?
>>
>> Sorry, I need to ask here (even if it's a stupid question ;)) if this
>> change is safe to do; are referring to a cleanup or fixing a concrete
>> bug? The code is a modified version of the DPDK hash which you can find
>> in [1]. Arguments of the caller are in the correct order, afaik.
>>
>>     [1] http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_hash_crc.h
>
> Yes, that file appears to be correct:
>
> rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
>
> as opposed to
>
> static inline u32 crc32_u32(u32 crc, u32 val)
>
> (quite obviously data <-> val and crc <-> init_val, supported
> by the second argument in each caller being named "seed").

If you want a more descriptive name, feel free to rename these vars,
but check it yourself, it's not a bug as you claim; results are the
same:

/* gcc -march=corei7 -Wall -O2 intel_crc.c -lgsl
  * ./a.out
  * Result: good:10000 bad:0
  */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <nmmintrin.h>
#include <gsl/gsl_rng.h>

/* Kernel code */
static inline uint32_t crc32_u32(uint32_t crc, uint32_t val)
{
	asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));
	return crc;
}

static uint32_t intel_crc4_2_hash(const void *data, uint32_t len, uint32_t seed)
{
	const uint32_t *p32 = (const uint32_t *) data;
	uint32_t i;

	for (i = 0; i < len / 4; i++)
		seed = crc32_u32(*p32++, seed);

	return seed;
}

/* DPDK code */
static inline uint32_t rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
{
	return _mm_crc32_u32(data, init_val);
}

static inline uint32_t rte_hash_crc(const void *data, uint32_t data_len,
				    uint32_t init_val)
{
	const uint32_t *p32 = (const uint32_t *) data;
	unsigned i;

	for (i = 0; i < data_len / 4; i++)
		init_val = rte_hash_crc_4byte(*p32++, init_val);

	return init_val;
}

/* Test case */
static void fill_foo(gsl_rng *rng, void *foo, size_t len)
{
	uint32_t *foo_32 = foo;
	int i;

	for (i = 0; i < len; i += sizeof(uint32_t))
		foo_32[i] = gsl_rng_get(rng);
}

int main(void)
{
	int i, good = 0, bad = 0;
	gsl_rng *rng;

	srand(time(NULL));
	gsl_rng_default_seed = rand();
	rng = gsl_rng_alloc(gsl_rng_taus113);
	if (rng == NULL)
		return -1;

	for (i = 0; i < 10000; i++) {
		char foo[sizeof(uint32_t) * 128];
		uint32_t val1, val2, seed = gsl_rng_get(rng);

		fill_foo(rng, foo, sizeof(foo));

		val1 = rte_hash_crc(foo, sizeof(foo), seed);
		val2 = intel_crc4_2_hash(foo, sizeof(foo), seed);

		if (val1 != val2)
			bad++;
		else
			good++;
	}

	gsl_rng_free(rng);
	printf("Result: good:%d bad:%d\n", good, bad);

	return 0;
}

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Jan Beulich]

>>> On 24.02.14 at 11:22, Daniel Borkmann <dborkman@redhat.com> wrote:
> On 02/24/2014 09:03 AM, Jan Beulich wrote:
>>>>> On 22.02.14 at 13:09, Daniel Borkmann <dborkman@redhat.com> wrote:
>>> On 02/21/2014 11:33 AM, Jan Beulich wrote:
>>>> ... to match its two callers (i.e. the alternative would have been to
>>>> swap the arguments at the call sites).
>>>>
>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>>> Cc: Francesco Fusco <ffusco@redhat.com>
>>>> Cc: Daniel Borkmann <dborkman@redhat.com>
>>>> Cc: Thomas Graf <tgraf@redhat.com>
>>>> Cc: David S. Miller <davem@davemloft.net>
>>>> ---
>>>>    arch/x86/lib/hash.c |    2 +-
>>>>    1 file changed, 1 insertion(+), 1 deletion(-)
>>>>
>>>> --- 3.14-rc3-x86-hash-crc32.orig/arch/x86/lib/hash.c
>>>> +++ 3.14-rc3-x86-hash-crc32/arch/x86/lib/hash.c
>>>> @@ -37,7 +37,7 @@
>>>>    #include <asm/cpufeature.h>
>>>>    #include <asm/hash.h>
>>>>
>>>> -static inline u32 crc32_u32(u32 crc, u32 val)
>>>> +static inline u32 crc32_u32(u32 val, u32 crc)
>>>>    {
>>>>    #ifdef CONFIG_AS_CRC32
>>>>    	asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));
>>>
>>> Can you elaborate?
>>>
>>> Sorry, I need to ask here (even if it's a stupid question ;)) if this
>>> change is safe to do; are referring to a cleanup or fixing a concrete
>>> bug? The code is a modified version of the DPDK hash which you can find
>>> in [1]. Arguments of the caller are in the correct order, afaik.
>>>
>>>     [1] http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_hash_crc.h 
>>
>> Yes, that file appears to be correct:
>>
>> rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
>>
>> as opposed to
>>
>> static inline u32 crc32_u32(u32 crc, u32 val)
>>
>> (quite obviously data <-> val and crc <-> init_val, supported
>> by the second argument in each caller being named "seed").
> 
> If you want a more descriptive name, feel free to rename these vars,
> but check it yourself, it's not a bug as you claim; results are the
> same:

Even if the results are the same (operands being symmetric?), check
the generated code for your version and the fixed up one: The crc32
instruction allows one of its operands to be in memory for a reason.

Jan

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Daniel Borkmann]

On 02/24/2014 11:53 AM, Jan Beulich wrote:
>>>> On 24.02.14 at 11:22, Daniel Borkmann <dborkman@redhat.com> wrote:
>> On 02/24/2014 09:03 AM, Jan Beulich wrote:
>>>>>> On 22.02.14 at 13:09, Daniel Borkmann <dborkman@redhat.com> wrote:
>>>> On 02/21/2014 11:33 AM, Jan Beulich wrote:
>>>>> ... to match its two callers (i.e. the alternative would have been to
>>>>> swap the arguments at the call sites).
>>>>>
>>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>>>> Cc: Francesco Fusco <ffusco@redhat.com>
>>>>> Cc: Daniel Borkmann <dborkman@redhat.com>
>>>>> Cc: Thomas Graf <tgraf@redhat.com>
>>>>> Cc: David S. Miller <davem@davemloft.net>
>>>>> ---
>>>>>     arch/x86/lib/hash.c |    2 +-
>>>>>     1 file changed, 1 insertion(+), 1 deletion(-)
>>>>>
>>>>> --- 3.14-rc3-x86-hash-crc32.orig/arch/x86/lib/hash.c
>>>>> +++ 3.14-rc3-x86-hash-crc32/arch/x86/lib/hash.c
>>>>> @@ -37,7 +37,7 @@
>>>>>     #include <asm/cpufeature.h>
>>>>>     #include <asm/hash.h>
>>>>>
>>>>> -static inline u32 crc32_u32(u32 crc, u32 val)
>>>>> +static inline u32 crc32_u32(u32 val, u32 crc)
>>>>>     {
>>>>>     #ifdef CONFIG_AS_CRC32
>>>>>     	asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));
>>>>
>>>> Can you elaborate?
>>>>
>>>> Sorry, I need to ask here (even if it's a stupid question ;)) if this
>>>> change is safe to do; are referring to a cleanup or fixing a concrete
>>>> bug? The code is a modified version of the DPDK hash which you can find
>>>> in [1]. Arguments of the caller are in the correct order, afaik.
>>>>
>>>>      [1] http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_hash_crc.h
>>>
>>> Yes, that file appears to be correct:
>>>
>>> rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
>>>
>>> as opposed to
>>>
>>> static inline u32 crc32_u32(u32 crc, u32 val)
>>>
>>> (quite obviously data <-> val and crc <-> init_val, supported
>>> by the second argument in each caller being named "seed").
>>
>> If you want a more descriptive name, feel free to rename these vars,
>> but check it yourself, it's not a bug as you claim; results are the
>> same:
>
> Even if the results are the same (operands being symmetric?), check
> the generated code for your version and the fixed up one: The crc32
> instruction allows one of its operands to be in memory for a reason.

I'm fine with that. But then, please reflect these details in your
commit message.

Thanks !

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Jan Beulich]

>>> On 24.02.14 at 12:46, Daniel Borkmann <dborkman@redhat.com> wrote:
> On 02/24/2014 11:53 AM, Jan Beulich wrote:
>>>>> On 24.02.14 at 11:22, Daniel Borkmann <dborkman@redhat.com> wrote:
>>> On 02/24/2014 09:03 AM, Jan Beulich wrote:
>>>>>>> On 22.02.14 at 13:09, Daniel Borkmann <dborkman@redhat.com> wrote:
>>>>> On 02/21/2014 11:33 AM, Jan Beulich wrote:
>>>>>> ... to match its two callers (i.e. the alternative would have been to
>>>>>> swap the arguments at the call sites).
>>>>>>
>>>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>>>>> Cc: Francesco Fusco <ffusco@redhat.com>
>>>>>> Cc: Daniel Borkmann <dborkman@redhat.com>
>>>>>> Cc: Thomas Graf <tgraf@redhat.com>
>>>>>> Cc: David S. Miller <davem@davemloft.net>
>>>>>> ---
>>>>>>     arch/x86/lib/hash.c |    2 +-
>>>>>>     1 file changed, 1 insertion(+), 1 deletion(-)
>>>>>>
>>>>>> --- 3.14-rc3-x86-hash-crc32.orig/arch/x86/lib/hash.c
>>>>>> +++ 3.14-rc3-x86-hash-crc32/arch/x86/lib/hash.c
>>>>>> @@ -37,7 +37,7 @@
>>>>>>     #include <asm/cpufeature.h>
>>>>>>     #include <asm/hash.h>
>>>>>>
>>>>>> -static inline u32 crc32_u32(u32 crc, u32 val)
>>>>>> +static inline u32 crc32_u32(u32 val, u32 crc)
>>>>>>     {
>>>>>>     #ifdef CONFIG_AS_CRC32
>>>>>>     	asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));
>>>>>
>>>>> Can you elaborate?
>>>>>
>>>>> Sorry, I need to ask here (even if it's a stupid question ;)) if this
>>>>> change is safe to do; are referring to a cleanup or fixing a concrete
>>>>> bug? The code is a modified version of the DPDK hash which you can find
>>>>> in [1]. Arguments of the caller are in the correct order, afaik.
>>>>>
>>>>>      [1] http://dpdk.org/browse/dpdk/tree/lib/librte_hash/rte_hash_crc.h 
>>>>
>>>> Yes, that file appears to be correct:
>>>>
>>>> rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
>>>>
>>>> as opposed to
>>>>
>>>> static inline u32 crc32_u32(u32 crc, u32 val)
>>>>
>>>> (quite obviously data <-> val and crc <-> init_val, supported
>>>> by the second argument in each caller being named "seed").
>>>
>>> If you want a more descriptive name, feel free to rename these vars,
>>> but check it yourself, it's not a bug as you claim; results are the
>>> same:
>>
>> Even if the results are the same (operands being symmetric?), check
>> the generated code for your version and the fixed up one: The crc32
>> instruction allows one of its operands to be in memory for a reason.
> 
> I'm fine with that. But then, please reflect these details in your
> commit message.

Hmm, to me it says exactly that.

Jan

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[H. Peter Anvin]

On 02/24/2014 03:46 AM, Daniel Borkmann wrote:
>>>>>>
>>>>>> --- 3.14-rc3-x86-hash-crc32.orig/arch/x86/lib/hash.c
>>>>>> +++ 3.14-rc3-x86-hash-crc32/arch/x86/lib/hash.c
>>>>>> @@ -37,7 +37,7 @@
>>>>>>     #include <asm/cpufeature.h>
>>>>>>     #include <asm/hash.h>
>>>>>>
>>>>>> -static inline u32 crc32_u32(u32 crc, u32 val)
>>>>>> +static inline u32 crc32_u32(u32 val, u32 crc)
>>>>>>     {
>>>>>>     #ifdef CONFIG_AS_CRC32
>>>>>>         asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));
>>>>>

OK, this whole tread is really confusing, but the change proposed seems 
actively wrong.

First of all:

static inline uint32_t
rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
{
	return _mm_crc32_u32(data, init_val);
}

... from the DPDK code is confusing all by itself, because the 
definition of the _mm_crc32_u32() intrinsic per the Intel SDM is:

unsigned int _mm_crc32_u32(unsigned int crc, unsigned int data);

... where "crc" is the destination operand, i.e. the accumulator if you 
actually would be computing a CRC32C.

So I'm guessing this hash is deliberately using the CRC32 instruction 
"backwards", which would actually make sense: an actual CRC is actually 
a pretty poor hash due to linearity.

This has confused people elsewhere, too:

http://permalink.gmane.org/gmane.comp.networking.dpdk.devel/954

So if this is a bug it is a bug in the upstream code, but I'm guessing 
the operand reversal is intentional.

Therefore, this patch should be actively NAKed.

Nacked-by: H. Peter Anvin <hpa@zytor.com>

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Jan Beulich]

>>> On 24.02.14 at 13:32, "H. Peter Anvin" <hpa@zytor.com> wrote:
> On 02/24/2014 03:46 AM, Daniel Borkmann wrote:
>>>>>>>
>>>>>>> --- 3.14-rc3-x86-hash-crc32.orig/arch/x86/lib/hash.c
>>>>>>> +++ 3.14-rc3-x86-hash-crc32/arch/x86/lib/hash.c
>>>>>>> @@ -37,7 +37,7 @@
>>>>>>>     #include <asm/cpufeature.h>
>>>>>>>     #include <asm/hash.h>
>>>>>>>
>>>>>>> -static inline u32 crc32_u32(u32 crc, u32 val)
>>>>>>> +static inline u32 crc32_u32(u32 val, u32 crc)
>>>>>>>     {
>>>>>>>     #ifdef CONFIG_AS_CRC32
>>>>>>>         asm ("crc32l %1,%0\n" : "+r" (crc) : "rm" (val));
>>>>>>
> 
> OK, this whole tread is really confusing, but the change proposed seems 
> actively wrong.
> 
> First of all:
> 
> static inline uint32_t
> rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
> {
> 	return _mm_crc32_u32(data, init_val);
> }
> 
> ... from the DPDK code is confusing all by itself, because the 
> definition of the _mm_crc32_u32() intrinsic per the Intel SDM is:
> 
> unsigned int _mm_crc32_u32(unsigned int crc, unsigned int data);
> 
> ... where "crc" is the destination operand, i.e. the accumulator if you 
> actually would be computing a CRC32C.
> 
> So I'm guessing this hash is deliberately using the CRC32 instruction 
> "backwards", which would actually make sense: an actual CRC is actually 
> a pretty poor hash due to linearity.
> 
> This has confused people elsewhere, too:
> 
> http://permalink.gmane.org/gmane.comp.networking.dpdk.devel/954 
> 
> So if this is a bug it is a bug in the upstream code, but I'm guessing 
> the operand reversal is intentional.

Ah, right. So the issue really is that this should have been stated
somewhere explicitly, avoiding the confusion.

> Therefore, this patch should be actively NAKed.
> 
> Nacked-by: H. Peter Anvin <hpa@zytor.com>

Agreed based on the above.

Jan

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[H. Peter Anvin]

On 02/24/2014 04:41 AM, Jan Beulich wrote:
>>
>> So I'm guessing this hash is deliberately using the CRC32 instruction
>> "backwards", which would actually make sense: an actual CRC is actually
>> a pretty poor hash due to linearity.
>>

OK, it really is even more confusing than that.

It does seem like the crc32 instruction really *is* commutative, which 
isn't something I would personally have expected at all.

Given that fact, I suspect the ordering in the DPDK is actually a bug, 
and that we should correct the ordering (which I would do at the call 
sites because it seems to make the code clearer) because it reduces the 
size of the loop by two instructions.

I guess I should find out how to file a bug report against DPDK too...

	-hpa

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[H. Peter Anvin]

On 02/24/2014 04:51 AM, H. Peter Anvin wrote:
> On 02/24/2014 04:41 AM, Jan Beulich wrote:
>>>
>>> So I'm guessing this hash is deliberately using the CRC32 instruction
>>> "backwards", which would actually make sense: an actual CRC is actually
>>> a pretty poor hash due to linearity.
>>>
>
> OK, it really is even more confusing than that.
>
> It does seem like the crc32 instruction really *is* commutative, which
> isn't something I would personally have expected at all.
>
> Given that fact, I suspect the ordering in the DPDK is actually a bug,
> and that we should correct the ordering (which I would do at the call
> sites because it seems to make the code clearer) because it reduces the
> size of the loop by two instructions.
>
> I guess I should find out how to file a bug report against DPDK too...
>

Looking through the DPDK project git history, it seems that this was a 
bug introduced when changing from using inline assembly to using intrinsics:

  static inline uint32_t
  rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
  {
-	asm volatile("crc32 %[data], %[init_val]"
-	             : [init_val]"=r" (init_val)
-	             : [data]"r" (data), "[init_val]" (init_val));
-	return init_val;
+	return _mm_crc32_u32(data, init_val);
  }

The operand order, of course, of the intrinsic being the opposite of 
AT&T-style assembly.

I never expected that the CRC32 operation would be commutative.  Very 
fascinating.

	-hpa

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Jan Beulich]

>>> On 24.02.14 at 14:01, "H. Peter Anvin" <hpa@zytor.com> wrote:
> I never expected that the CRC32 operation would be commutative.  Very 
> fascinating.

Neither did I, which is why I was very surprised for Daniel to say that
things worked with the apparently wrong order.

Jan

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Daniel Borkmann]

On 02/24/2014 02:01 PM, H. Peter Anvin wrote:
> On 02/24/2014 04:51 AM, H. Peter Anvin wrote:
>> On 02/24/2014 04:41 AM, Jan Beulich wrote:
>>>>
>>>> So I'm guessing this hash is deliberately using the CRC32 instruction
>>>> "backwards", which would actually make sense: an actual CRC is actually
>>>> a pretty poor hash due to linearity.
>>
>> OK, it really is even more confusing than that.
>>
>> It does seem like the crc32 instruction really *is* commutative, which
>> isn't something I would personally have expected at all.
>>
>> Given that fact, I suspect the ordering in the DPDK is actually a bug,
>> and that we should correct the ordering (which I would do at the call
>> sites because it seems to make the code clearer) because it reduces the
>> size of the loop by two instructions.
>>
>> I guess I should find out how to file a bug report against DPDK too...
>
> Looking through the DPDK project git history, it seems that this was a bug introduced when changing from using inline assembly to using intrinsics:
>
>   static inline uint32_t
>   rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
>   {
> -    asm volatile("crc32 %[data], %[init_val]"
> -                 : [init_val]"=r" (init_val)
> -                 : [data]"r" (data), "[init_val]" (init_val));
> -    return init_val;
> +    return _mm_crc32_u32(data, init_val);
>   }

Good point, I also just noticed that in the git blame.

> The operand order, of course, of the intrinsic being the opposite of AT&T-style assembly.
>
> I never expected that the CRC32 operation would be commutative.  Very fascinating.

Indeed.

>      -hpa

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[H. Peter Anvin]

On a totally different note, it would probably be a good idea to use 
intrinsics more in the kernel where possible.  Intrinsics do allow the 
compiler to generate better scheduling.

The trick of course is that we'd want to have machinery that can fall 
back to inline assembly if the compiler doesn't support the intrinsics, 
and perhaps even to .bytes if needed.  This pretty much involves a bunch 
of compiler and assembler-probing machinery and then wrapping things in 
neat little inline functions.

	-hpa

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[H. Peter Anvin]

On 02/24/2014 12:03 AM, Jan Beulich wrote:
> rte_hash_crc_4byte(uint32_t data, uint32_t init_val)
>
> as opposed to
>
> static inline u32 crc32_u32(u32 crc, u32 val)
>
> (quite obviously data <-> val and crc <-> init_val, supported
> by the second argument in each caller being named "seed").
>

"Quite obviously", but unfortunately wrong (see other email).

	-hpa

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[H. Peter Anvin]

On 02/21/2014 02:33 AM, Jan Beulich wrote:
> ... to match its two callers (i.e. the alternative would have been to
> swap the arguments at the call sites).
> 
> Signed-off-by: Jan Beulich <jbeulich@suse.com>
> Cc: Francesco Fusco <ffusco@redhat.com>
> Cc: Daniel Borkmann <dborkman@redhat.com>
> Cc: Thomas Graf <tgraf@redhat.com>
> Cc: David S. Miller <davem@davemloft.net>
> ---
>  arch/x86/lib/hash.c |    2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 

Jan, do you want to do an updated version of this patch?  Daniel, I
presume you are going to push this patch?

	-hpa

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Daniel Borkmann]

On 02/25/2014 09:26 PM, H. Peter Anvin wrote:
> On 02/21/2014 02:33 AM, Jan Beulich wrote:
>> ... to match its two callers (i.e. the alternative would have been to
>> swap the arguments at the call sites).
>>
>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>> Cc: Francesco Fusco <ffusco@redhat.com>
>> Cc: Daniel Borkmann <dborkman@redhat.com>
>> Cc: Thomas Graf <tgraf@redhat.com>
>> Cc: David S. Miller <davem@davemloft.net>
>> ---
>>   arch/x86/lib/hash.c |    2 +-
>>   1 file changed, 1 insertion(+), 1 deletion(-)
>
> Jan, do you want to do an updated version of this patch?  Daniel, I
> presume you are going to push this patch?

Good point. I'm fine if this is going to be picked up
by x86 maintainers. Feel free to add my ...

Acked-by: Daniel Borkmann <dborkman@redhat.com>

... if you want to do an updated version that also
includes our recent findings/discussion, Jan.

Thanks!

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[H. Peter Anvin]

On 02/25/2014 12:34 PM, Daniel Borkmann wrote:
> On 02/25/2014 09:26 PM, H. Peter Anvin wrote:
>> On 02/21/2014 02:33 AM, Jan Beulich wrote:
>>> ... to match its two callers (i.e. the alternative would have been to
>>> swap the arguments at the call sites).
>>>
>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>> Cc: Francesco Fusco <ffusco@redhat.com>
>>> Cc: Daniel Borkmann <dborkman@redhat.com>
>>> Cc: Thomas Graf <tgraf@redhat.com>
>>> Cc: David S. Miller <davem@davemloft.net>
>>> ---
>>>   arch/x86/lib/hash.c |    2 +-
>>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> Jan, do you want to do an updated version of this patch?  Daniel, I
>> presume you are going to push this patch?
> 
> Good point. I'm fine if this is going to be picked up
> by x86 maintainers. Feel free to add my ...
> 
> Acked-by: Daniel Borkmann <dborkman@redhat.com>
> 
> ... if you want to do an updated version that also
> includes our recent findings/discussion, Jan.
> 

Well, I don't want to change the names of the arguments in the inline
function unless we also change the their functions and actually reverse
the order of the operands as used.

	-hpa

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[Jan Beulich]

>>> On 25.02.14 at 21:37, "H. Peter Anvin" <hpa@zytor.com> wrote:
> On 02/25/2014 12:34 PM, Daniel Borkmann wrote:
>> On 02/25/2014 09:26 PM, H. Peter Anvin wrote:
>>> On 02/21/2014 02:33 AM, Jan Beulich wrote:
>>>> ... to match its two callers (i.e. the alternative would have been to
>>>> swap the arguments at the call sites).
>>>>
>>>> Signed-off-by: Jan Beulich <jbeulich@suse.com>
>>>> Cc: Francesco Fusco <ffusco@redhat.com>
>>>> Cc: Daniel Borkmann <dborkman@redhat.com>
>>>> Cc: Thomas Graf <tgraf@redhat.com>
>>>> Cc: David S. Miller <davem@davemloft.net>
>>>> ---
>>>>   arch/x86/lib/hash.c |    2 +-
>>>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>>
>>> Jan, do you want to do an updated version of this patch?  Daniel, I
>>> presume you are going to push this patch?
>> 
>> Good point. I'm fine if this is going to be picked up
>> by x86 maintainers. Feel free to add my ...
>> 
>> Acked-by: Daniel Borkmann <dborkman@redhat.com>
>> 
>> ... if you want to do an updated version that also
>> includes our recent findings/discussion, Jan.
>> 
> 
> Well, I don't want to change the names of the arguments in the inline
> function unless we also change the their functions and actually reverse
> the order of the operands as used.

So I'm confused now: Whether we change the function's
parameters or the callers' argument order has the same net effect:
It's either (with the current patch)

static inline u32 crc32_u32(u32 val, u32 crc)
		seed = crc32_u32(*p32++, seed);
		seed = crc32_u32(tmp, seed);
		seed = crc32_u32(*p32++, seed);

or it would be (with parameter order kept and argument order
swapped)

static inline u32 crc32_u32(u32 crc, u32 val)
		seed = crc32_u32(seed, *p32++);
		seed = crc32_u32(seed, tmp);
		seed = crc32_u32(seed, *p32++);

I.e. it is precisely the case that their names and functions disagree
in the current (unpatched) version.

Jan

Re: [PATCH 2/3] x86/hash: swap parameters of crc32_u32()

[H. Peter Anvin]

On 02/26/2014 01:29 AM, Jan Beulich wrote:
> 
> or it would be (with parameter order kept and argument order
> swapped)
> 
> static inline u32 crc32_u32(u32 crc, u32 val)
> 		seed = crc32_u32(seed, *p32++);
> 		seed = crc32_u32(seed, tmp);
> 		seed = crc32_u32(seed, *p32++);
> 
> I.e. it is precisely the case that their names and functions disagree
> in the current (unpatched) version.
> 

I guess I think this version seems more logical especially/when this
inline is moved into a global place somewhere.

It's not a big deal, though.

	-hpa