[dpdk-dev] hash: fix breaking strict-aliasing rules

  Fix rte_hash_crc() function. Casting uint64_t pointer to uin32_t
may trigger a compiler warning about breaking strict-aliasing rules.
To avoid that, introduce a lookup table which is used to mask out
a remainder of data.

See issue #1, http://dpdk.org/ml/archives/dev/2015-March/015174.html

Signed-off-by: Yerden Zhumabekov <e_zhumabekov@sts.kz>
---
 lib/librte_hash/rte_hash_crc.h |   31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)
  

On Wed, Mar 18, 2015 at 10:51:12PM +0600, Yerden Zhumabekov wrote:
> Fix rte_hash_crc() function. Casting uint64_t pointer to uin32_t
> may trigger a compiler warning about breaking strict-aliasing rules.
> To avoid that, introduce a lookup table which is used to mask out
> a remainder of data.
> 
> See issue #1, http://dpdk.org/ml/archives/dev/2015-March/015174.html
> 
> Signed-off-by: Yerden Zhumabekov <e_zhumabekov@sts.kz>

Looks ok to me. Couple of minor suggestions below.

/Bruce

> ---
>  lib/librte_hash/rte_hash_crc.h |   31 +++++++++++++++----------------
>  1 file changed, 15 insertions(+), 16 deletions(-)
> 
> diff --git a/lib/librte_hash/rte_hash_crc.h b/lib/librte_hash/rte_hash_crc.h
> index 3dcd362..e81920f 100644
> --- a/lib/librte_hash/rte_hash_crc.h
> +++ b/lib/librte_hash/rte_hash_crc.h
> @@ -323,6 +323,16 @@ static const uint32_t crc32c_tables[8][256] = {{
>   0xE54C35A1, 0xAC704886, 0x7734CFEF, 0x3E08B2C8, 0xC451B7CC, 0x8D6DCAEB, 0x56294D82, 0x1F1530A5
>  }};
>  
> +static const uint64_t odd_8byte_mask[] = {

Where does the name of this variable come from, it seems unclear to me?

> +	0x00FFFFFFFFFFFFFF,
> +	0x0000FFFFFFFFFFFF,
> +	0x000000FFFFFFFFFF,
> +	0x00000000FFFFFFFF,
> +	0x0000000000FFFFFF,
> +	0x000000000000FFFF,
> +	0x00000000000000FF,
> +};
> +
>  #define CRC32_UPD(crc, n) \
>  	(crc32c_tables[(n)][(crc) & 0xFF] ^ \
>  	 crc32c_tables[(n)-1][((crc) >> 8) & 0xFF])
> @@ -535,38 +545,27 @@ static inline uint32_t
>  rte_hash_crc(const void *data, uint32_t data_len, uint32_t init_val)
>  {
>  	unsigned i;
> -	uint64_t temp = 0;
> +	uint64_t temp;

It is worth keeping variable "temp" at all, it looks to me like it could be done
away with without seriously affecting readability.

>  	const uint64_t *p64 = (const uint64_t *)data;
>  
>  	for (i = 0; i < data_len / 8; i++) {
>  		init_val = rte_hash_crc_8byte(*p64++, init_val);
>  	}
>  
> -	switch (7 - (data_len & 0x07)) {
> +	i = 7 - (data_len & 0x07);

i is not a terribly meaningful variable name, perhaps a slightly longer, more
meaningful name might improve readability.

> +	switch (i) {
>  	case 0:
> -		temp |= (uint64_t) *((const uint8_t *)p64 + 6) << 48;
> -		/* Fallthrough */
>  	case 1:
> -		temp |= (uint64_t) *((const uint8_t *)p64 + 5) << 40;
> -		/* Fallthrough */
>  	case 2:
> -		temp |= (uint64_t) *((const uint8_t *)p64 + 4) << 32;
> -		temp |= *((const uint32_t *)p64);
> +		temp = odd_8byte_mask[i] & *p64;
>  		init_val = rte_hash_crc_8byte(temp, init_val);
>  		break;
>  	case 3:
> -		init_val = rte_hash_crc_4byte(*(const uint32_t *)p64, init_val);
> -		break;
>  	case 4:
> -		temp |= *((const uint8_t *)p64 + 2) << 16;
> -		/* Fallthrough */
>  	case 5:
> -		temp |= *((const uint8_t *)p64 + 1) << 8;
> -		/* Fallthrough */
>  	case 6:
> -		temp |= *((const uint8_t *)p64);
> +		temp = odd_8byte_mask[i] & *p64;
>  		init_val = rte_hash_crc_4byte(temp, init_val);
> -		/* Fallthrough */
>  	default:
>  		break;
>  	}
> -- 
> 1.7.9.5
>
  

On Thu, Mar 19, 2015 at 04:25:47PM +0000, Bruce Richardson wrote:
> On Wed, Mar 18, 2015 at 10:51:12PM +0600, Yerden Zhumabekov wrote:
> > Fix rte_hash_crc() function. Casting uint64_t pointer to uin32_t
> > may trigger a compiler warning about breaking strict-aliasing rules.
> > To avoid that, introduce a lookup table which is used to mask out
> > a remainder of data.
> > 
> > See issue #1, http://dpdk.org/ml/archives/dev/2015-March/015174.html
> > 
> > Signed-off-by: Yerden Zhumabekov <e_zhumabekov@sts.kz>
> 
> Looks ok to me. Couple of minor suggestions below.
> 
> /Bruce

Other than the below suggestions:

Acked-by: Bruce Richardson <bruce.richardson@intel.com>
> 
> > ---
> >  lib/librte_hash/rte_hash_crc.h |   31 +++++++++++++++----------------
> >  1 file changed, 15 insertions(+), 16 deletions(-)
> > 
> > diff --git a/lib/librte_hash/rte_hash_crc.h b/lib/librte_hash/rte_hash_crc.h
> > index 3dcd362..e81920f 100644
> > --- a/lib/librte_hash/rte_hash_crc.h
> > +++ b/lib/librte_hash/rte_hash_crc.h
> > @@ -323,6 +323,16 @@ static const uint32_t crc32c_tables[8][256] = {{
> >   0xE54C35A1, 0xAC704886, 0x7734CFEF, 0x3E08B2C8, 0xC451B7CC, 0x8D6DCAEB, 0x56294D82, 0x1F1530A5
> >  }};
> >  
> > +static const uint64_t odd_8byte_mask[] = {
> 
> Where does the name of this variable come from, it seems unclear to me?
> 
> > +	0x00FFFFFFFFFFFFFF,
> > +	0x0000FFFFFFFFFFFF,
> > +	0x000000FFFFFFFFFF,
> > +	0x00000000FFFFFFFF,
> > +	0x0000000000FFFFFF,
> > +	0x000000000000FFFF,
> > +	0x00000000000000FF,
> > +};
> > +
> >  #define CRC32_UPD(crc, n) \
> >  	(crc32c_tables[(n)][(crc) & 0xFF] ^ \
> >  	 crc32c_tables[(n)-1][((crc) >> 8) & 0xFF])
> > @@ -535,38 +545,27 @@ static inline uint32_t
> >  rte_hash_crc(const void *data, uint32_t data_len, uint32_t init_val)
> >  {
> >  	unsigned i;
> > -	uint64_t temp = 0;
> > +	uint64_t temp;
> 
> It is worth keeping variable "temp" at all, it looks to me like it could be done
> away with without seriously affecting readability.
> 
> >  	const uint64_t *p64 = (const uint64_t *)data;
> >  
> >  	for (i = 0; i < data_len / 8; i++) {
> >  		init_val = rte_hash_crc_8byte(*p64++, init_val);
> >  	}
> >  
> > -	switch (7 - (data_len & 0x07)) {
> > +	i = 7 - (data_len & 0x07);
> 
> i is not a terribly meaningful variable name, perhaps a slightly longer, more
> meaningful name might improve readability.
> 
> > +	switch (i) {
> >  	case 0:
> > -		temp |= (uint64_t) *((const uint8_t *)p64 + 6) << 48;
> > -		/* Fallthrough */
> >  	case 1:
> > -		temp |= (uint64_t) *((const uint8_t *)p64 + 5) << 40;
> > -		/* Fallthrough */
> >  	case 2:
> > -		temp |= (uint64_t) *((const uint8_t *)p64 + 4) << 32;
> > -		temp |= *((const uint32_t *)p64);
> > +		temp = odd_8byte_mask[i] & *p64;
> >  		init_val = rte_hash_crc_8byte(temp, init_val);
> >  		break;
> >  	case 3:
> > -		init_val = rte_hash_crc_4byte(*(const uint32_t *)p64, init_val);
> > -		break;
> >  	case 4:
> > -		temp |= *((const uint8_t *)p64 + 2) << 16;
> > -		/* Fallthrough */
> >  	case 5:
> > -		temp |= *((const uint8_t *)p64 + 1) << 8;
> > -		/* Fallthrough */
> >  	case 6:
> > -		temp |= *((const uint8_t *)p64);
> > +		temp = odd_8byte_mask[i] & *p64;
> >  		init_val = rte_hash_crc_4byte(temp, init_val);
> > -		/* Fallthrough */
> >  	default:
> >  		break;
> >  	}
> > -- 
> > 1.7.9.5
> >
  

Hi Bruce,

Answers below.

19.03.2015 22:25, Bruce Richardson пишет:
> On Wed, Mar 18, 2015 at 10:51:12PM +0600, Yerden Zhumabekov wrote:
>> Fix rte_hash_crc() function. Casting uint64_t pointer to uin32_t
>> may trigger a compiler warning about breaking strict-aliasing rules.
>> To avoid that, introduce a lookup table which is used to mask out
>> a remainder of data.
>>
>> See issue #1, http://dpdk.org/ml/archives/dev/2015-March/015174.html
>>
>> Signed-off-by: Yerden Zhumabekov <e_zhumabekov@sts.kz>
> Looks ok to me. Couple of minor suggestions below.
>
> /Bruce
>
>> ---
>>  lib/librte_hash/rte_hash_crc.h |   31 +++++++++++++++----------------
>>  1 file changed, 15 insertions(+), 16 deletions(-)
>>
>> diff --git a/lib/librte_hash/rte_hash_crc.h b/lib/librte_hash/rte_hash_crc.h
>> index 3dcd362..e81920f 100644
>> --- a/lib/librte_hash/rte_hash_crc.h
>> +++ b/lib/librte_hash/rte_hash_crc.h
>> @@ -323,6 +323,16 @@ static const uint32_t crc32c_tables[8][256] = {{
>>   0xE54C35A1, 0xAC704886, 0x7734CFEF, 0x3E08B2C8, 0xC451B7CC, 0x8D6DCAEB, 0x56294D82, 0x1F1530A5
>>  }};
>>  
>> +static const uint64_t odd_8byte_mask[] = {
> Where does the name of this variable come from, it seems unclear to me?

If the number of bytes in data for CRC hashing cannot be evenly divided
by 8, the remainder is extracted with these masks. Hence, we have 'odd'
bytes to mask out. Maybe my poor english. :) Suggestions are welcome.
What about remainder_8byte_mask?

>> +	0x00FFFFFFFFFFFFFF,
>> +	0x0000FFFFFFFFFFFF,
>> +	0x000000FFFFFFFFFF,
>> +	0x00000000FFFFFFFF,
>> +	0x0000000000FFFFFF,
>> +	0x000000000000FFFF,
>> +	0x00000000000000FF,
>> +};
>> +
>>  #define CRC32_UPD(crc, n) \
>>  	(crc32c_tables[(n)][(crc) & 0xFF] ^ \
>>  	 crc32c_tables[(n)-1][((crc) >> 8) & 0xFF])
>> @@ -535,38 +545,27 @@ static inline uint32_t
>>  rte_hash_crc(const void *data, uint32_t data_len, uint32_t init_val)
>>  {
>>  	unsigned i;
>> -	uint64_t temp = 0;
>> +	uint64_t temp;
> It is worth keeping variable "temp" at all, it looks to me like it could be done
> away with without seriously affecting readability.

Noted.

>>  	const uint64_t *p64 = (const uint64_t *)data;
>>  
>>  	for (i = 0; i < data_len / 8; i++) {
>>  		init_val = rte_hash_crc_8byte(*p64++, init_val);
>>  	}
>>  
>> -	switch (7 - (data_len & 0x07)) {
>> +	i = 7 - (data_len & 0x07);
> i is not a terribly meaningful variable name, perhaps a slightly longer, more
> meaningful name might improve readability.

Noted, I'll declare a new one.
  

On 2015-03-18 17:51, Yerden Zhumabekov wrote:
> Fix rte_hash_crc() function. Casting uint64_t pointer to uin32_t
> may trigger a compiler warning about breaking strict-aliasing rules.
> To avoid that, introduce a lookup table which is used to mask out
> a remainder of data.
>
> See issue #1, http://dpdk.org/ml/archives/dev/2015-March/015174.html
>
> Signed-off-by: Yerden Zhumabekov <e_zhumabekov@sts.kz>
> ---
>   lib/librte_hash/rte_hash_crc.h |   31 +++++++++++++++----------------
>   1 file changed, 15 insertions(+), 16 deletions(-)
>
> diff --git a/lib/librte_hash/rte_hash_crc.h b/lib/librte_hash/rte_hash_crc.h
> index 3dcd362..e81920f 100644
> --- a/lib/librte_hash/rte_hash_crc.h
> +++ b/lib/librte_hash/rte_hash_crc.h
> @@ -323,6 +323,16 @@ static const uint32_t crc32c_tables[8][256] = {{
>    0xE54C35A1, 0xAC704886, 0x7734CFEF, 0x3E08B2C8, 0xC451B7CC, 0x8D6DCAEB, 0x56294D82, 0x1F1530A5
>   }};
>
> +static const uint64_t odd_8byte_mask[] = {
> +	0x00FFFFFFFFFFFFFF,
> +	0x0000FFFFFFFFFFFF,
> +	0x000000FFFFFFFFFF,
> +	0x00000000FFFFFFFF,
> +	0x0000000000FFFFFF,
> +	0x000000000000FFFF,
> +	0x00000000000000FF,
> +};
> +
>   #define CRC32_UPD(crc, n) \
>   	(crc32c_tables[(n)][(crc) & 0xFF] ^ \
>   	 crc32c_tables[(n)-1][((crc) >> 8) & 0xFF])
> @@ -535,38 +545,27 @@ static inline uint32_t
>   rte_hash_crc(const void *data, uint32_t data_len, uint32_t init_val)
>   {
>   	unsigned i;
> -	uint64_t temp = 0;
> +	uint64_t temp;
>   	const uint64_t *p64 = (const uint64_t *)data;
>
>   	for (i = 0; i < data_len / 8; i++) {
>   		init_val = rte_hash_crc_8byte(*p64++, init_val);
>   	}
>
> -	switch (7 - (data_len & 0x07)) {
> +	i = 7 - (data_len & 0x07);

Great idea with lookup table!
Only one question here: why keeping this magic at all now?
If you sort odd_8byte_mask opposite direction you can do something like that

	data_len &= 0x07;
	switch (data_len & 0x07) {
	case 1:
	case 2:
	case 3:
	case 4:
		temp = odd_8byte_mask[data_len] & *p64;
		init_val = rte_hash_crc_4byte(temp, init_val);
	case 5:
	case 6:
	case 7:
		temp = odd_8byte_mask[data_len] & *p64;
		init_val = rte_hash_crc_8byte(temp, init_val);
		break;
	default:
		break;
	}
Or

	data_len &= 0x07;
	if (data_len > 0) {
		temp = odd_8byte_mask[data_len] & *p64;
		if (data_len <= 4)
			init_val = rte_hash_crc_4byte(temp, init_val);
		else
			init_val = rte_hash_crc_8byte(temp, init_val);
	}
	
Is there something obvious what I am not seeing here?

Pawel

> +	switch (i) {
>   	case 0:
> -		temp |= (uint64_t) *((const uint8_t *)p64 + 6) << 48;
> -		/* Fallthrough */
>   	case 1:
> -		temp |= (uint64_t) *((const uint8_t *)p64 + 5) << 40;
> -		/* Fallthrough */
>   	case 2:
> -		temp |= (uint64_t) *((const uint8_t *)p64 + 4) << 32;
> -		temp |= *((const uint32_t *)p64);
> +		temp = odd_8byte_mask[i] & *p64;
>   		init_val = rte_hash_crc_8byte(temp, init_val);
>   		break;
>   	case 3:
> -		init_val = rte_hash_crc_4byte(*(const uint32_t *)p64, init_val);
> -		break;
>   	case 4:
> -		temp |= *((const uint8_t *)p64 + 2) << 16;
> -		/* Fallthrough */
>   	case 5:
> -		temp |= *((const uint8_t *)p64 + 1) << 8;
> -		/* Fallthrough */
>   	case 6:
> -		temp |= *((const uint8_t *)p64);
> +		temp = odd_8byte_mask[i] & *p64;
>   		init_val = rte_hash_crc_4byte(temp, init_val);
> -		/* Fallthrough */
>   	default:
>   		break;
>   	}
>
  

On 2015-03-18 17:51, Yerden Zhumabekov wrote:

>
> -	switch (7 - (data_len & 0x07)) {
> +	i = 7 - (data_len & 0x07);
> +	switch (i) {
>   	case 0:
> -		temp |= (uint64_t) *((const uint8_t *)p64 + 6) << 48;
> -		/* Fallthrough */
>   	case 1:
> -		temp |= (uint64_t) *((const uint8_t *)p64 + 5) << 40;
> -		/* Fallthrough */
>   	case 2:
> -		temp |= (uint64_t) *((const uint8_t *)p64 + 4) << 32;
> -		temp |= *((const uint32_t *)p64);
> +		temp = odd_8byte_mask[i] & *p64;
>   		init_val = rte_hash_crc_8byte(temp, init_val);
>   		break;
>   	case 3:
> -		init_val = rte_hash_crc_4byte(*(const uint32_t *)p64, init_val);
> -		break;
>   	case 4:
> -		temp |= *((const uint8_t *)p64 + 2) << 16;
> -		/* Fallthrough */
>   	case 5:
> -		temp |= *((const uint8_t *)p64 + 1) << 8;
> -		/* Fallthrough */
>   	case 6:
> -		temp |= *((const uint8_t *)p64);
> +		temp = odd_8byte_mask[i] & *p64;
>   		init_val = rte_hash_crc_4byte(temp, init_val);
> -		/* Fallthrough */
>   	default:
>   		break;
>   	}
>

Second thought: is this not an issue here reading 8 bytes by 
dereferencing *p64 if there is less bytes in buffer?
  

Hi Pawel,

Oops, thanks for the clue. I have a buffer over-read here leading to undefined behaviour.
The only solution I see here is to declare uint32_t pointer and evaluate it to (uint8_t *) data + data_len - (data_len & 0x07). Ideas are welcome. That would resolve strict-aliasing violation.