[PATCH v4 2/2] eal: provide leading and trailing zero bit count abstraction
Tyler Retzlaff
roretzla at linux.microsoft.com
Tue Jan 10 18:34:28 CET 2023
On Tue, Jan 10, 2023 at 01:55:59PM +0000, Ferruh Yigit wrote:
> On 1/9/2023 5:36 PM, Tyler Retzlaff wrote:
> > From: Tyler Retzlaff <roretzla at microsoft.com>
> >
> > Provide an abstraction for leading and trailing zero bit counting
> > functions to hide compiler specific intrinsics and builtins.
> >
> > Include basic unit test of following functions added.
> >
> > rte_clz32
> > rte_clz64
> > rte_ctz32
> > rte_ctz64
> >
> > Signed-off-by: Tyler Retzlaff <roretzla at linux.microsoft.com>
> > ---
> > app/test/meson.build | 2 +
> > app/test/test_bitcount.c | 71 ++++++++++++++++++
> > lib/eal/include/rte_bitops.h | 168 +++++++++++++++++++++++++++++++++++++++++++
> > 3 files changed, 241 insertions(+)
> > create mode 100644 app/test/test_bitcount.c
> >
> > diff --git a/app/test/meson.build b/app/test/meson.build
> > index f34d19e..d1277bc 100644
> > --- a/app/test/meson.build
> > +++ b/app/test/meson.build
> > @@ -13,6 +13,7 @@ test_sources = files(
> > 'test_alarm.c',
> > 'test_atomic.c',
> > 'test_barrier.c',
> > + 'test_bitcount.c',
> > 'test_bitops.c',
> > 'test_bitmap.c',
> > 'test_bpf.c',
> > @@ -160,6 +161,7 @@ test_deps += ['bus_pci', 'bus_vdev']
> > fast_tests = [
> > ['acl_autotest', true, true],
> > ['atomic_autotest', false, true],
> > + ['bitcount_autotest', true, true],
> > ['bitmap_autotest', true, true],
> > ['bpf_autotest', true, true],
> > ['bpf_convert_autotest', true, true],
> > diff --git a/app/test/test_bitcount.c b/app/test/test_bitcount.c
> > new file mode 100644
> > index 0000000..36eb05c
> > --- /dev/null
> > +++ b/app/test/test_bitcount.c
> > @@ -0,0 +1,71 @@
> > +/* SPDX-License-Identifier: BSD-3-Clause
> > + * Copyright (C) 2022 Microsoft Corporation
> > + */
> > +
> > +#include <string.h>
> > +
> > +#include <rte_bitops.h>
> > +#include <rte_debug.h>
> > +
> > +#include "test.h"
> > +
> > +RTE_LOG_REGISTER(bitcount_logtype_test, test.bitcount, INFO);
> > +
> > +static int
> > +test_clz32(void)
> > +{
> > + uint32_t v = 1;
> > + RTE_TEST_ASSERT(rte_clz32(v) == sizeof(v) * CHAR_BIT - 1,
> > + "Unexpected count.");
> > +
> > + return 0;
> > +}
> > +
> > +static int
> > +test_clz64(void)
> > +{
> > + uint64_t v = 1;
> > + RTE_TEST_ASSERT(rte_clz64(v) == sizeof(v) * CHAR_BIT - 1,
> > + "Unexpected count.");
> > +
> > + return 0;
> > +}
> > +
> > +static int
> > +test_ctz32(void)
> > +{
> > + uint32_t v = 2;
> > + RTE_TEST_ASSERT(rte_ctz32(v) == 1, "Unexpected count.");
> > +
> > + return 0;
> > +}
> > +
> > +static int
> > +test_ctz64(void)
> > +{
> > + uint64_t v = 2;
> > + RTE_TEST_ASSERT(rte_ctz64(v) == 1, "Unexpected count.");
> > +
> > + return 0;
> > +}
> > +
> > +static struct unit_test_suite bitcount_test_suite = {
> > + .suite_name = "bitcount autotest",
> > + .setup = NULL,
> > + .teardown = NULL,
> > + .unit_test_cases = {
> > + TEST_CASE(test_clz32),
> > + TEST_CASE(test_clz64),
> > + TEST_CASE(test_ctz32),
> > + TEST_CASE(test_ctz64),
> > + TEST_CASES_END()
> > + }
> > +};
> > +
> > +static int
> > +test_bitcount(void)
> > +{
> > + return unit_test_suite_runner(&bitcount_test_suite);
> > +}
> > +
> > +REGISTER_TEST_COMMAND(bitcount_autotest, test_bitcount);
> > diff --git a/lib/eal/include/rte_bitops.h b/lib/eal/include/rte_bitops.h
> > index 531479e..387d7aa 100644
> > --- a/lib/eal/include/rte_bitops.h
> > +++ b/lib/eal/include/rte_bitops.h
> > @@ -1,5 +1,7 @@
> > /* SPDX-License-Identifier: BSD-3-Clause
> > * Copyright(c) 2020 Arm Limited
> > + * Copyright(c) 2010-2019 Intel Corporation
> > + * Copyright(c) 2023 Microsoft Corporation
> > */
> >
> > #ifndef _RTE_BITOPS_H_
> > @@ -275,6 +277,172 @@
> > return val & mask;
> > }
> >
> > +#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_clz32(uint32_t v)
> > +{
> > + unsigned long rv;
> > +
> > + (void)_BitScanReverse(&rv, v);
> > +
> > + return (unsigned int)rv;
> > +}
>
>
> OK, this looks wrong to me,
>
>
> '_BitScanReverse' is [1]:
> "Search the mask data from most significant bit (MSB) to least
> significant bit (LSB) for a set bit (1)."
>
> As far as I can see index starts from zero and from lsb to msb.
>
> So _BitScanReverse() returns following index values:
> 0x2 => 1
> 0xffffffff => 31
>
> If above is correct, above function doesn't return number of leading
> zeros, but it should return "31 - (unsigned int)rv".
>
> Please check godbolt experiment for above:
> https://godbolt.org/z/znYn54f57
>
>
> As far as I can see unit test is correct, so above should fail with
> windows compiler, and I assume you run unit test with windows compiler,
> so probably I am missing something but please help me understand.
>
>
>
> [1]
> https://learn.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64?view=msvc-170
>
> > +
> > +/**
> > + * @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_clz64(uint64_t v)
> > +{
> > + unsigned long rv;
> > +
> > + (void)_BitScanReverse64(&rv, v);
> > +
> > + return (unsigned int)rv;
> > +}
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of trailing 0-bits in v.
> > + *
> > + * @param v
> > + * The value.
> > + * @return
> > + * The count of trailing zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_ctz32(uint32_t v)
> > +{
> > + unsigned long rv;
> > +
> > + (void)_BitScanForward(&rv, v);
> > +
> > + return (unsigned int)rv;
> > +}
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of trailing 0-bits in v.
> > + *
> > + * @param v
> > + * The value.
> > + * @return
> > + * The count of trailing zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_ctz64(uint64_t v)
> > +{
> > + unsigned long rv;
> > +
> > + (void)_BitScanForward64(&rv, v);
> > +
> > + return (unsigned int)rv;
> > +}
> > +
> > +#else
> > +
> > +/**
> > + * @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_clz32(uint32_t v)
> > +{
> > + return (unsigned int)__builtin_clz(v);
> > +}
> > +
> > +/**
> > + * @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_clz64(uint64_t v)
> > +{
> > + return (unsigned int)__builtin_clzll(v);
> > +}
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of trailing 0-bits in v.
> > + *
> > + * @param v
> > + * The value.
> > + * @return
> > + * The count of trailing zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_ctz32(uint32_t v)
> > +{
> > + return (unsigned int)__builtin_ctz(v);
> > +}
> > +
> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change, or be removed, without prior notice
> > + *
> > + * Get the count of trailing 0-bits in v.
> > + *
> > + * @param v
> > + * The value.
> > + * @return
> > + * The count of trailing zero bits.
> > + */
> > +__rte_experimental
> > +static inline unsigned int
> > +rte_ctz64(uint64_t v)
> > +{
> > + return (unsigned int)__builtin_ctzll(v);
> > +}
>
> 'rte_ctz32()' & 'rte_ctz64()' are practically exact same with
> 'rte_bsf32()' & 'rte_bsf64()',
>
> Although I can see description is different, do we need same
> functionality with new function name,
> why not add 'rte_bsf32()' & 'rte_bsf64()' versions for the Windows?
i agree. i need a consensus from reviewers if they think this series
should be changed.
if we do take bsf{32,64} instead then does that mean we ban the use of
__ctz{32,64} in dpdk? keeping in mind the end goal is portability.
>
>
>
> btw, do you guys know what 'bsf' & 'fls' (rte_fls_u32) stands for?
no idea. before my time.
>
> > +
> > +#endif
> > +
> > /**
> > * Combines 32b inputs most significant set bits into the least
> > * significant bits to construct a value with the same MSBs as x
More information about the dev
mailing list