Patchwork [v3] bitops: unify bitops_ffsl with the one in host-utils.h, call it bitops_ctzl

login
register
mail settings
Submitter Paolo Bonzini
Date Feb. 1, 2013, 10:03 p.m.
Message ID <1359756196-5588-1-git-send-email-pbonzini@redhat.com>
Download mbox | patch
Permalink /patch/217603/
State New
Headers show

Comments

Paolo Bonzini - Feb. 1, 2013, 10:03 p.m.
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(-)
Eric Blake - Feb. 1, 2013, 11:58 p.m.
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>
Andreas Färber - Feb. 2, 2013, 10:13 a.m.
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
Peter Maydell - Feb. 2, 2013, 1:30 p.m.
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
Eric Blake - Feb. 2, 2013, 3:11 p.m.
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.
Paolo Bonzini - Feb. 3, 2013, 3:47 a.m.
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.
>
Peter Maydell - Feb. 3, 2013, 10:32 a.m.
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
Blue Swirl - Feb. 3, 2013, 4:15 p.m.
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
>

Patch

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.  */