[PATCH v2 1/2] eal: provide leading and trailing zero bit count abstraction

[Tyler Retzlaff]

On Wed, Apr 05, 2023 at 04:51:42PM +0100, Bruce Richardson wrote:
> On Wed, Apr 05, 2023 at 08:22:16AM -0700, Tyler Retzlaff wrote:
> > On Wed, Apr 05, 2023 at 09:44:54AM +0100, Bruce Richardson wrote:
> > > On Tue, Apr 04, 2023 at 02:23:22PM -0700, Tyler Retzlaff wrote:
> > > > On Thu, Jan 05, 2023 at 08:09:19AM +0100, Morten Brørup wrote:
> > > > > > From: Tyler Retzlaff [mailto:roretzla at linux.microsoft.com]
> > > > > > Sent: Thursday, 24 November 2022 00.43
> > > > > > 
> > > > > > Provide an abstraction for leading and trailing zero bit counting
> > > > > > functions to hide compiler specific intrinsics and builtins.
> > > > > > 
> > > > > > Signed-off-by: Tyler Retzlaff <roretzla at linux.microsoft.com>
> > > > > > ---
> > > > > >  lib/eal/include/meson.build    |   1 +
> > > > > >  lib/eal/include/rte_bitcount.h | 265
> > > > > > +++++++++++++++++++++++++++++++++++++++++
> > > > > >  2 files changed, 266 insertions(+)
> > > > > >  create mode 100644 lib/eal/include/rte_bitcount.h
> > > > > > 
> > > > > > diff --git a/lib/eal/include/meson.build b/lib/eal/include/meson.build
> > > > > > index cfcd40a..8ff1d65 100644
> > > > > > --- a/lib/eal/include/meson.build
> > > > > > +++ b/lib/eal/include/meson.build
> > > > > > @@ -5,6 +5,7 @@ includes += include_directories('.')
> > > > > > 
> > > > > >  headers += files(
> > > > > >          'rte_alarm.h',
> > > > > > +        'rte_bitcount.h',
> > > > > >          'rte_bitmap.h',
> > > > > >          'rte_bitops.h',
> > > > > >          'rte_branch_prediction.h',
> > > > > > diff --git a/lib/eal/include/rte_bitcount.h
> > > > > > b/lib/eal/include/rte_bitcount.h
> > > > > > new file mode 100644
> > > > > > index 0000000..587de52
> > > > > > --- /dev/null
> > > > > > +++ b/lib/eal/include/rte_bitcount.h
> > > > > > @@ -0,0 +1,265 @@
> > > > > > +/* SPDX-License-Identifier: BSD-3-Clause
> > > > > > + * Copyright (C) 2022 Microsoft Corporation
> > > > > > + */
> > > > > > +
> > > > > > +#ifndef _RTE_BITCOUNT_H_
> > > > > > +#define _RTE_BITCOUNT_H_
> > > > > > +
> > > > > > +#include <rte_compat.h>
> > > > > > +
> > > > > > +#ifdef __cplusplus
> > > > > > +extern "C" {
> > > > > > +#endif
> > > > > > +
> > > > > > +#ifdef RTE_TOOLCHAIN_MSVC
> > > > > > +
> > > > > > +/**
> > > > > > + * @warning
> > > > > > + * @b EXPERIMENTAL: this API may change, or be removed, without prior
> > > > > > notice
> > > > > > + *
> > > > > > + * Get the count of leading 0-bits in v.
> > > > > > + *
> > > > > > + * @param v
> > > > > > + *   The value.
> > > > > > + * @return
> > > > > > + *   The count of leading zero bits.
> > > > > > + */
> > > > > > +__rte_experimental
> > > > > > +static inline unsigned int
> > > > > > +rte_clz(unsigned int v)
> > > > > > +{
> > > > > > +	unsigned long rv;
> > > > > > +
> > > > > > +	(void)_BitScanReverse(&rv, v);
> > > > > > +
> > > > > > +	return (unsigned int)rv;
> > > > > > +}
> > > > > > +
> > > > > > +/**
> > > > > > + * @warning
> > > > > > + * @b EXPERIMENTAL: this API may change, or be removed, without prior
> > > > > > notice
> > > > > > + *
> > > > > > + * Get the count of leading 0-bits in v.
> > > > > > + *
> > > > > > + * @param v
> > > > > > + *   The value.
> > > > > > + * @return
> > > > > > + *   The count of leading zero bits.
> > > > > > + */
> > > > > > +__rte_experimental
> > > > > > +static inline unsigned int
> > > > > > +rte_clzl(unsigned long v)
> > > > > 
> > > > > Don't use l (long) and ll (long long) for names (and types), use explicit bit lengths, 32 and 64.
> > > > > 
> > > > > E.g.: rte_clz32(uint32_t v)
> > > > 
> > > > so i just noticed this, but sometimes these functions receive size_t so
> > > > naming them specifically 32/64 bit becomes problematic because are going
> > > > to end up with promotion on sizeof(size_t) == sizeof(long) == 4
> > > > platforms.
> > > > 
> > > > i.e.
> > > > size_t s = ...;
> > > > x = rte_clz64(s); // assume 64-bit today
> > > > 
> > > > this code is now broken because on 32-bit platform s will get promoted
> > > > and the extra 32 zero-bits will be returned in the result breaking
> > > > calculations.
> > > > 
> > > > any thoughts? should we go back to l, ll?
> > > > 
> > > 
> > > Yes, promotion will happen, but I still think that the 32 and 64 versions
> > > are far clearer here in all cases. Anyone looking at the code will
> > > recognise that the result will be the leading zero count of a 64-bit number
> > > irrespective of the type actually passed in. It's less confusing now IMHO.
> > 
> > here's an example in the code that would result in a bad calculation or
> > at least i believe so at a glance. switching to rte_clz32() would break
> > on 64-bit since it would truncate.
> > 
> > lib/eal/common/malloc_elem.c
> > 
> > -log2 = sizeof(size) * 8 - __builtin_clzl(size);
> > +log2 = sizeof(size) * 8 - rte_clz64(size);
> > 
> > if i'm right you'd have to conditionally compile at the site.
> > 
> > #ifdef 64-bit
> > rte_clz64()
> > #else
> > rte_clz32()
> > #endif
> > 
> 
> Why can clz64 not be used in both 32 and 64 bit cases? You know the result
> will always include zeros in high bits of a 64-bit value, and the result
> will still fit inside even an 8-bit variable?

of course. doh.

sorry for the noise!

and thank you as always.

> 
> /Bruce