| Message ID | 1359756196-5588-1-git-send-email-pbonzini@redhat.com |
|---|---|
| State | New |
| Headers | show |
On 02/01/2013 03:03 PM, Paolo Bonzini wrote: > We had two copies of a ffs function for longs with subtly different > semantics and, for the one in bitops.h, a confusing name: the result > was off-by-one compared to the library function ffsl. > > Unify the functions into one, and solve the name problem by calling > the 0-based functions "bitops_ctzl" and "bitops_ctol" respectively. > > This also fixes the build on platforms with ffsl, including Mac OS X > and Windows. > > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> > --- > > /** > - * bitops_ffs - find first bit in word. > + * bitops_ctzl - count trailing zeroes in word. > * @word: The word to search > * > - * Undefined if no bit exists, so code should check against 0 first. > + * Returns -1 if no bit exists. Note that compared to the C library > + * routine ffsl, this one returns one less. > */ > -static unsigned long bitops_ffsl(unsigned long word) > +static unsigned long bitops_ctzl(unsigned long word) The C library ffsl() returns 'int', not 'unsigned long'. Given that your bitops_ctzl returns -1, does it make sense to fix this to return a signed type? > > /** > - * ffz - find first zero in word. > + * cto - count trailing ones in word. > * @word: The word to search > * > - * Undefined if no zero exists, so code should check against ~0UL first. > + * Returns -1 if all bit are set. > */ > -static inline unsigned long ffz(unsigned long word) > +static inline unsigned long bitops_ctol(unsigned long word) Likewise; if we are changing this name, should we also change the return type to be signed? However, the wrong return type doesn't impact any of the callers, and this time around, your conversion looks correct. Reviewed-by: Eric Blake <eblake@redhat.com>
Am 01.02.2013 23:03, schrieb Paolo Bonzini: > We had two copies of a ffs function for longs with subtly different > semantics and, for the one in bitops.h, a confusing name: the result > was off-by-one compared to the library function ffsl. > > Unify the functions into one, and solve the name problem by calling > the 0-based functions "bitops_ctzl" and "bitops_ctol" respectively. > > This also fixes the build on platforms with ffsl, including Mac OS X > and Windows. > > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Tested-by: Andreas Färber <afaerber@suse.de> This fixes the build on OpenIndiana, too. Thanks, Andreas
On 1 February 2013 22:03, Paolo Bonzini <pbonzini@redhat.com> wrote: > We had two copies of a ffs function for longs with subtly different > semantics and, for the one in bitops.h, a confusing name: the result > was off-by-one compared to the library function ffsl. > > Unify the functions into one, and solve the name problem by calling > the 0-based functions "bitops_ctzl" and "bitops_ctol" respectively. > > This also fixes the build on platforms with ffsl, including Mac OS X > and Windows. > > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> Tested-by: Peter Maydell <peter.maydell@linaro.org> This fixes the MacOSX build failure and boots a guest OK. > /** > - * bitops_ffs - find first bit in word. > + * bitops_ctzl - count trailing zeroes in word. > * @word: The word to search > * > - * Undefined if no bit exists, so code should check against 0 first. > + * Returns -1 if no bit exists. Note that compared to the C library > + * routine ffsl, this one returns one less. > */ Do any of our callers actually use the "-1 on 0 input" semantics? (I guess that means "your new code you added" since the previous callers all were happy with the undefined-on-zero semantics). It seems an odd choice, since I can see a justification for: (a) "return number of bits in word" [every bit in the word is a trailing zero in some sense] (b) "undefined" [matches gcc builtin_ctz semantics] However I'm more interested in getting a reasonable patch for the build issues committed before the next rc rather than spending too much time nitpicking details. -- PMM
On 02/02/2013 06:30 AM, Peter Maydell wrote: >> - * Undefined if no bit exists, so code should check against 0 first. >> + * Returns -1 if no bit exists. Note that compared to the C library >> + * routine ffsl, this one returns one less. >> */ > > Do any of our callers actually use the "-1 on 0 input" semantics? > (I guess that means "your new code you added" since the previous > callers all were happy with the undefined-on-zero semantics). Yes, Paolo's code was replacing: ffsl(var) - 1 with bitops_ctzl(var) where var==0 was a definite possibility, so we DO have code that depends on this semantic of returning -1. > It seems an odd choice, since I can see a justification for: > (a) "return number of bits in word" [every bit in the word is > a trailing zero in some sense] > (b) "undefined" [matches gcc builtin_ctz semantics] For all non-zero values of var, ffsl(var) == bitops_ctzl(var)+1. Extending the equivalency for var==0 makes the function usable in the most places.
Il 02/02/2013 16:11, Eric Blake ha scritto: > On 02/02/2013 06:30 AM, Peter Maydell wrote: > >>> - * Undefined if no bit exists, so code should check against 0 first. >>> + * Returns -1 if no bit exists. Note that compared to the C library >>> + * routine ffsl, this one returns one less. >>> */ >> >> Do any of our callers actually use the "-1 on 0 input" semantics? >> (I guess that means "your new code you added" since the previous >> callers all were happy with the undefined-on-zero semantics). > > Yes, Paolo's code was replacing: > > ffsl(var) - 1 > > with > > bitops_ctzl(var) > > where var==0 was a definite possibility, so we DO have code that depends > on this semantic of returning -1. Actually I'm pretty sure that var == 0 is not possible in hbitmap. But I still prefer having total functions, and also keeping the function monotonic. For example, I would use the number of bits in word for clz(0), since clz(x) is monotonic decreasing. Paolo >> It seems an odd choice, since I can see a justification for: >> (a) "return number of bits in word" [every bit in the word is >> a trailing zero in some sense] >> (b) "undefined" [matches gcc builtin_ctz semantics] > > For all non-zero values of var, ffsl(var) == bitops_ctzl(var)+1. > Extending the equivalency for var==0 makes the function usable in the > most places. >
On 3 February 2013 03:47, Paolo Bonzini <pbonzini@redhat.com> wrote: > Actually I'm pretty sure that var == 0 is not possible in hbitmap. But > I still prefer having total functions, and also keeping the function > monotonic. Er, ctz() isn't monotonic: 1 => 0 2 => 1 3 => 0 4 => 2 etc... -- PMM
Thanks, applied. On Fri, Feb 1, 2013 at 10:03 PM, Paolo Bonzini <pbonzini@redhat.com> wrote: > We had two copies of a ffs function for longs with subtly different > semantics and, for the one in bitops.h, a confusing name: the result > was off-by-one compared to the library function ffsl. > > Unify the functions into one, and solve the name problem by calling > the 0-based functions "bitops_ctzl" and "bitops_ctol" respectively. > > This also fixes the build on platforms with ffsl, including Mac OS X > and Windows. > > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> > --- > include/qemu/bitops.h | 55 +++++++++++++++++++---------------------------- > include/qemu/hbitmap.h | 2 +- > include/qemu/host-utils.h | 26 ---------------------- > memory.c | 4 ++-- > util/bitops.c | 4 ++-- > util/hbitmap.c | 2 +- > 6 files changed, 28 insertions(+), 65 deletions(-) > > diff --git a/include/qemu/bitops.h b/include/qemu/bitops.h > index 74e14e5..8b88791 100644 > --- a/include/qemu/bitops.h > +++ b/include/qemu/bitops.h > @@ -13,6 +13,7 @@ > #define BITOPS_H > > #include "qemu-common.h" > +#include "host-utils.h" > > #define BITS_PER_BYTE CHAR_BIT > #define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) > @@ -23,41 +24,29 @@ > #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) > > /** > - * bitops_ffs - find first bit in word. > + * bitops_ctzl - count trailing zeroes in word. > * @word: The word to search > * > - * Undefined if no bit exists, so code should check against 0 first. > + * Returns -1 if no bit exists. Note that compared to the C library > + * routine ffsl, this one returns one less. > */ > -static unsigned long bitops_ffsl(unsigned long word) > +static unsigned long bitops_ctzl(unsigned long word) > { > - int num = 0; > +#if QEMU_GNUC_PREREQ(3, 4) > + return __builtin_ffsl(word) - 1; > +#else > + if (!word) { > + return -1; > + } > > -#if LONG_MAX > 0x7FFFFFFF > - if ((word & 0xffffffff) == 0) { > - num += 32; > - word >>= 32; > - } > + if (sizeof(long) == 4) { > + return ctz32(word); > + } else if (sizeof(long) == 8) { > + return ctz64(word); > + } else { > + abort(); > + } > #endif > - if ((word & 0xffff) == 0) { > - num += 16; > - word >>= 16; > - } > - if ((word & 0xff) == 0) { > - num += 8; > - word >>= 8; > - } > - if ((word & 0xf) == 0) { > - num += 4; > - word >>= 4; > - } > - if ((word & 0x3) == 0) { > - num += 2; > - word >>= 2; > - } > - if ((word & 0x1) == 0) { > - num += 1; > - } > - return num; > } > > /** > @@ -99,14 +88,14 @@ static inline unsigned long bitops_flsl(unsigned long word) > } > > /** > - * ffz - find first zero in word. > + * cto - count trailing ones in word. > * @word: The word to search > * > - * Undefined if no zero exists, so code should check against ~0UL first. > + * Returns -1 if all bit are set. > */ > -static inline unsigned long ffz(unsigned long word) > +static inline unsigned long bitops_ctol(unsigned long word) > { > - return bitops_ffsl(~word); > + return bitops_ctzl(~word); > } > > /** > diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h > index 73f5d1d..250de03 100644 > --- a/include/qemu/hbitmap.h > +++ b/include/qemu/hbitmap.h > @@ -170,7 +170,7 @@ static inline int64_t hbitmap_iter_next(HBitmapIter *hbi) > > /* The next call will resume work from the next bit. */ > hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1); > - item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ffsl(cur) - 1; > + item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + bitops_ctzl(cur); > > return item << hbi->granularity; > } > diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h > index 2a32be4..81c9a75 100644 > --- a/include/qemu/host-utils.h > +++ b/include/qemu/host-utils.h > @@ -26,7 +26,6 @@ > #define HOST_UTILS_H 1 > > #include "qemu/compiler.h" /* QEMU_GNUC_PREREQ */ > -#include <string.h> /* ffsl */ > > #if defined(__x86_64__) > #define __HAVE_FAST_MULU64__ > @@ -238,29 +237,4 @@ static inline int ctpop64(uint64_t val) > #endif > } > > -/* glibc does not provide an inline version of ffsl, so always define > - * ours. We need to give it a different name, however. > - */ > -#ifdef __GLIBC__ > -#define ffsl qemu_ffsl > -#endif > -static inline int ffsl(long val) > -{ > - if (!val) { > - return 0; > - } > - > -#if QEMU_GNUC_PREREQ(3, 4) > - return __builtin_ctzl(val) + 1; > -#else > - if (sizeof(long) == 4) { > - return ctz32(val) + 1; > - } else if (sizeof(long) == 8) { > - return ctz64(val) + 1; > - } else { > - abort(); > - } > -#endif > -} > - > #endif > diff --git a/memory.c b/memory.c > index 410c5f8..cd7d5e0 100644 > --- a/memory.c > +++ b/memory.c > @@ -855,7 +855,7 @@ static uint64_t memory_region_dispatch_read1(MemoryRegion *mr, > } > > if (!mr->ops->read) { > - return mr->ops->old_mmio.read[bitops_ffsl(size)](mr->opaque, addr); > + return mr->ops->old_mmio.read[bitops_ctzl(size)](mr->opaque, addr); > } > > /* FIXME: support unaligned access */ > @@ -908,7 +908,7 @@ static void memory_region_dispatch_write(MemoryRegion *mr, > adjust_endianness(mr, &data, size); > > if (!mr->ops->write) { > - mr->ops->old_mmio.write[bitops_ffsl(size)](mr->opaque, addr, data); > + mr->ops->old_mmio.write[bitops_ctzl(size)](mr->opaque, addr, data); > return; > } > > diff --git a/util/bitops.c b/util/bitops.c > index 4c3a836..7b853cf 100644 > --- a/util/bitops.c > +++ b/util/bitops.c > @@ -60,7 +60,7 @@ found_first: > return result + size; /* Nope. */ > } > found_middle: > - return result + bitops_ffsl(tmp); > + return result + bitops_ctzl(tmp); > } > > /* > @@ -109,7 +109,7 @@ found_first: > return result + size; /* Nope. */ > } > found_middle: > - return result + ffz(tmp); > + return result + bitops_ctol(tmp); > } > > unsigned long find_last_bit(const unsigned long *addr, unsigned long size) > diff --git a/util/hbitmap.c b/util/hbitmap.c > index 2aa487d..a0df5d3 100644 > --- a/util/hbitmap.c > +++ b/util/hbitmap.c > @@ -126,7 +126,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) > * The index of this word's least significant set bit provides > * the low-order bits. > */ > - pos = (pos << BITS_PER_LEVEL) + ffsl(cur) - 1; > + pos = (pos << BITS_PER_LEVEL) + bitops_ctzl(cur); > hbi->cur[i] = cur & (cur - 1); > > /* Set up next level for iteration. */ > -- > 1.8.1 >
diff --git a/include/qemu/bitops.h b/include/qemu/bitops.h index 74e14e5..8b88791 100644 --- a/include/qemu/bitops.h +++ b/include/qemu/bitops.h @@ -13,6 +13,7 @@ #define BITOPS_H #include "qemu-common.h" +#include "host-utils.h" #define BITS_PER_BYTE CHAR_BIT #define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) @@ -23,41 +24,29 @@ #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) /** - * bitops_ffs - find first bit in word. + * bitops_ctzl - count trailing zeroes in word. * @word: The word to search * - * Undefined if no bit exists, so code should check against 0 first. + * Returns -1 if no bit exists. Note that compared to the C library + * routine ffsl, this one returns one less. */ -static unsigned long bitops_ffsl(unsigned long word) +static unsigned long bitops_ctzl(unsigned long word) { - int num = 0; +#if QEMU_GNUC_PREREQ(3, 4) + return __builtin_ffsl(word) - 1; +#else + if (!word) { + return -1; + } -#if LONG_MAX > 0x7FFFFFFF - if ((word & 0xffffffff) == 0) { - num += 32; - word >>= 32; - } + if (sizeof(long) == 4) { + return ctz32(word); + } else if (sizeof(long) == 8) { + return ctz64(word); + } else { + abort(); + } #endif - if ((word & 0xffff) == 0) { - num += 16; - word >>= 16; - } - if ((word & 0xff) == 0) { - num += 8; - word >>= 8; - } - if ((word & 0xf) == 0) { - num += 4; - word >>= 4; - } - if ((word & 0x3) == 0) { - num += 2; - word >>= 2; - } - if ((word & 0x1) == 0) { - num += 1; - } - return num; } /** @@ -99,14 +88,14 @@ static inline unsigned long bitops_flsl(unsigned long word) } /** - * ffz - find first zero in word. + * cto - count trailing ones in word. * @word: The word to search * - * Undefined if no zero exists, so code should check against ~0UL first. + * Returns -1 if all bit are set. */ -static inline unsigned long ffz(unsigned long word) +static inline unsigned long bitops_ctol(unsigned long word) { - return bitops_ffsl(~word); + return bitops_ctzl(~word); } /** diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 73f5d1d..250de03 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -170,7 +170,7 @@ static inline int64_t hbitmap_iter_next(HBitmapIter *hbi) /* The next call will resume work from the next bit. */ hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1); - item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ffsl(cur) - 1; + item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + bitops_ctzl(cur); return item << hbi->granularity; } diff --git a/include/qemu/host-utils.h b/include/qemu/host-utils.h index 2a32be4..81c9a75 100644 --- a/include/qemu/host-utils.h +++ b/include/qemu/host-utils.h @@ -26,7 +26,6 @@ #define HOST_UTILS_H 1 #include "qemu/compiler.h" /* QEMU_GNUC_PREREQ */ -#include <string.h> /* ffsl */ #if defined(__x86_64__) #define __HAVE_FAST_MULU64__ @@ -238,29 +237,4 @@ static inline int ctpop64(uint64_t val) #endif } -/* glibc does not provide an inline version of ffsl, so always define - * ours. We need to give it a different name, however. - */ -#ifdef __GLIBC__ -#define ffsl qemu_ffsl -#endif -static inline int ffsl(long val) -{ - if (!val) { - return 0; - } - -#if QEMU_GNUC_PREREQ(3, 4) - return __builtin_ctzl(val) + 1; -#else - if (sizeof(long) == 4) { - return ctz32(val) + 1; - } else if (sizeof(long) == 8) { - return ctz64(val) + 1; - } else { - abort(); - } -#endif -} - #endif diff --git a/memory.c b/memory.c index 410c5f8..cd7d5e0 100644 --- a/memory.c +++ b/memory.c @@ -855,7 +855,7 @@ static uint64_t memory_region_dispatch_read1(MemoryRegion *mr, } if (!mr->ops->read) { - return mr->ops->old_mmio.read[bitops_ffsl(size)](mr->opaque, addr); + return mr->ops->old_mmio.read[bitops_ctzl(size)](mr->opaque, addr); } /* FIXME: support unaligned access */ @@ -908,7 +908,7 @@ static void memory_region_dispatch_write(MemoryRegion *mr, adjust_endianness(mr, &data, size); if (!mr->ops->write) { - mr->ops->old_mmio.write[bitops_ffsl(size)](mr->opaque, addr, data); + mr->ops->old_mmio.write[bitops_ctzl(size)](mr->opaque, addr, data); return; } diff --git a/util/bitops.c b/util/bitops.c index 4c3a836..7b853cf 100644 --- a/util/bitops.c +++ b/util/bitops.c @@ -60,7 +60,7 @@ found_first: return result + size; /* Nope. */ } found_middle: - return result + bitops_ffsl(tmp); + return result + bitops_ctzl(tmp); } /* @@ -109,7 +109,7 @@ found_first: return result + size; /* Nope. */ } found_middle: - return result + ffz(tmp); + return result + bitops_ctol(tmp); } unsigned long find_last_bit(const unsigned long *addr, unsigned long size) diff --git a/util/hbitmap.c b/util/hbitmap.c index 2aa487d..a0df5d3 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -126,7 +126,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi) * The index of this word's least significant set bit provides * the low-order bits. */ - pos = (pos << BITS_PER_LEVEL) + ffsl(cur) - 1; + pos = (pos << BITS_PER_LEVEL) + bitops_ctzl(cur); hbi->cur[i] = cur & (cur - 1); /* Set up next level for iteration. */
We had two copies of a ffs function for longs with subtly different semantics and, for the one in bitops.h, a confusing name: the result was off-by-one compared to the library function ffsl. Unify the functions into one, and solve the name problem by calling the 0-based functions "bitops_ctzl" and "bitops_ctol" respectively. This also fixes the build on platforms with ffsl, including Mac OS X and Windows. Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> --- include/qemu/bitops.h | 55 +++++++++++++++++++---------------------------- include/qemu/hbitmap.h | 2 +- include/qemu/host-utils.h | 26 ---------------------- memory.c | 4 ++-- util/bitops.c | 4 ++-- util/hbitmap.c | 2 +- 6 files changed, 28 insertions(+), 65 deletions(-)