ia64/xen-unstable

changeset 17500:fec632d30571

x86: Fix handling of BSF and BSR instructions.

1. We cannot rely on BSF/BSR leaving the destination register intact
if the source is zero (according to Intel manuals)
2. We race clear_bit() in find_first_bit(), which may occur after
SCAS but before BSF. So we must handle zero input to BSF.

Signed-off-by: Naoki Nishiguchi <nisiguti@jp.fujitsu.com>
Signed-off-by: Keir Fraser <keir.fraser@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Tue Apr 22 11:43:10 2008 +0100 (2008-04-22)
parents 78d0a147216f
children 1cc4df5c7fe8
files xen/arch/x86/bitops.c xen/include/asm-x86/bitops.h
line diff
     1.1 --- a/xen/arch/x86/bitops.c	Tue Apr 22 10:34:55 2008 +0100
     1.2 +++ b/xen/arch/x86/bitops.c	Tue Apr 22 11:43:10 2008 +0100
     1.3 @@ -8,17 +8,18 @@ unsigned int __find_first_bit(
     1.4      unsigned long d0, d1, res;
     1.5  
     1.6      asm volatile (
     1.7 -        "   xor %%eax,%%eax\n\t" /* also ensures ZF==1 if size==0 */
     1.8 +        "1: xor %%eax,%%eax\n\t" /* also ensures ZF==1 if size==0 */
     1.9          "   repe; scas"__OS"\n\t"
    1.10 -        "   je 1f\n\t"
    1.11 +        "   je 2f\n\t"
    1.12 +        "   bsf -"STR(BITS_PER_LONG/8)"(%2),%0\n\t"
    1.13 +        "   jz 1b\n\t"
    1.14          "   lea -"STR(BITS_PER_LONG/8)"(%2),%2\n\t"
    1.15 -        "   bsf (%2),%0\n"
    1.16 -        "1: sub %%ebx,%%edi\n\t"
    1.17 +        "2: sub %%ebx,%%edi\n\t"
    1.18          "   shl $3,%%edi\n\t"
    1.19          "   add %%edi,%%eax"
    1.20          : "=&a" (res), "=&c" (d0), "=&D" (d1)
    1.21 -        : "1" ((size + BITS_PER_LONG - 1) / BITS_PER_LONG),
    1.22 -          "2" (addr), "b" ((int)(long)addr) : "memory" );
    1.23 +        : "1" (BITS_TO_LONGS(size)), "2" (addr), "b" ((int)(long)addr)
    1.24 +        : "memory" );
    1.25  
    1.26      return res;
    1.27  }
    1.28 @@ -34,8 +35,7 @@ unsigned int __find_next_bit(
    1.29      if ( bit != 0 )
    1.30      {
    1.31          /* Look for a bit in the first word. */
    1.32 -        asm ( "bsf %1,%%"__OP"ax"
    1.33 -              : "=a" (set) : "r" (*p >> bit), "0" (BITS_PER_LONG) );
    1.34 +        set = __scanbit(*p >> bit, BITS_PER_LONG - bit);
    1.35          if ( set < (BITS_PER_LONG - bit) )
    1.36              return (offset + set);
    1.37          offset += BITS_PER_LONG - bit;
    1.38 @@ -56,18 +56,20 @@ unsigned int __find_first_zero_bit(
    1.39      unsigned long d0, d1, d2, res;
    1.40  
    1.41      asm volatile (
    1.42 +        "1: xor %%eax,%%eax ; not %3\n\t" /* rAX == ~0ul */
    1.43          "   xor %%edx,%%edx\n\t" /* also ensures ZF==1 if size==0 */
    1.44          "   repe; scas"__OS"\n\t"
    1.45 -        "   je 1f\n\t"
    1.46 +        "   je 2f\n\t"
    1.47 +        "   xor -"STR(BITS_PER_LONG/8)"(%2),%3\n\t"
    1.48 +        "   jz 1b\n\t"
    1.49 +        "   bsf %3,%0\n\t"
    1.50          "   lea -"STR(BITS_PER_LONG/8)"(%2),%2\n\t"
    1.51 -        "   xor (%2),%3\n\t"
    1.52 -        "   bsf %3,%0\n"
    1.53 -        "1: sub %%ebx,%%edi\n\t"
    1.54 +        "2: sub %%ebx,%%edi\n\t"
    1.55          "   shl $3,%%edi\n\t"
    1.56          "   add %%edi,%%edx"
    1.57          : "=&d" (res), "=&c" (d0), "=&D" (d1), "=&a" (d2)
    1.58 -        : "1" ((size + BITS_PER_LONG - 1) / BITS_PER_LONG),
    1.59 -          "2" (addr), "b" ((int)(long)addr), "3" (-1L) : "memory" );
    1.60 +        : "1" (BITS_TO_LONGS(size)), "2" (addr), "b" ((int)(long)addr)
    1.61 +        : "memory" );
    1.62  
    1.63      return res;
    1.64  }
    1.65 @@ -83,7 +85,7 @@ unsigned int __find_next_zero_bit(
    1.66      if ( bit != 0 )
    1.67      {
    1.68          /* Look for zero in the first word. */
    1.69 -        asm ( "bsf %1,%%"__OP"ax" : "=a" (set) : "r" (~(*p >> bit)) );
    1.70 +        set = __scanbit(~(*p >> bit), BITS_PER_LONG - bit);
    1.71          if ( set < (BITS_PER_LONG - bit) )
    1.72              return (offset + set);
    1.73          offset += BITS_PER_LONG - bit;
     2.1 --- a/xen/include/asm-x86/bitops.h	Tue Apr 22 10:34:55 2008 +0100
     2.2 +++ b/xen/include/asm-x86/bitops.h	Tue Apr 22 11:43:10 2008 +0100
     2.3 @@ -331,10 +331,9 @@ extern unsigned int __find_first_zero_bi
     2.4  extern unsigned int __find_next_zero_bit(
     2.5      const unsigned long *addr, unsigned int size, unsigned int offset);
     2.6  
     2.7 -/* return index of first bit set in val or BITS_PER_LONG when no bit is set */
     2.8 -static inline unsigned int __scanbit(unsigned long val)
     2.9 +static inline unsigned int __scanbit(unsigned long val, unsigned long max)
    2.10  {
    2.11 -    asm ( "bsf %1,%0" : "=r" (val) : "r" (val), "0" (BITS_PER_LONG) );
    2.12 +    asm ( "bsf %1,%0 ; cmovz %2,%0" : "=&r" (val) : "r" (val), "r" (max) );
    2.13      return (unsigned int)val;
    2.14  }
    2.15  
    2.16 @@ -346,9 +345,9 @@ static inline unsigned int __scanbit(uns
    2.17   * Returns the bit-number of the first set bit, not the number of the byte
    2.18   * containing a bit.
    2.19   */
    2.20 -#define find_first_bit(addr,size) \
    2.21 -((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \
    2.22 -  (__scanbit(*(const unsigned long *)addr)) : \
    2.23 +#define find_first_bit(addr,size)                               \
    2.24 +((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ?       \
    2.25 +  (__scanbit(*(const unsigned long *)addr, size)) :             \
    2.26    __find_first_bit(addr,size)))
    2.27  
    2.28  /**
    2.29 @@ -357,9 +356,9 @@ static inline unsigned int __scanbit(uns
    2.30   * @offset: The bitnumber to start searching at
    2.31   * @size: The maximum size to search
    2.32   */
    2.33 -#define find_next_bit(addr,size,off) \
    2.34 -((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \
    2.35 -  ((off) + (__scanbit((*(const unsigned long *)addr) >> (off)))) : \
    2.36 +#define find_next_bit(addr,size,off)                                     \
    2.37 +((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ?                \
    2.38 +  ((off) + (__scanbit((*(const unsigned long *)addr) >> (off), size))) : \
    2.39    __find_next_bit(addr,size,off)))
    2.40  
    2.41  /**
    2.42 @@ -370,9 +369,9 @@ static inline unsigned int __scanbit(uns
    2.43   * Returns the bit-number of the first zero bit, not the number of the byte
    2.44   * containing a bit.
    2.45   */
    2.46 -#define find_first_zero_bit(addr,size) \
    2.47 -((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \
    2.48 -  (__scanbit(~*(const unsigned long *)addr)) : \
    2.49 +#define find_first_zero_bit(addr,size)                          \
    2.50 +((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ?       \
    2.51 +  (__scanbit(~*(const unsigned long *)addr, size)) :            \
    2.52    __find_first_zero_bit(addr,size)))
    2.53  
    2.54  /**
    2.55 @@ -381,9 +380,9 @@ static inline unsigned int __scanbit(uns
    2.56   * @offset: The bitnumber to start searching at
    2.57   * @size: The maximum size to search
    2.58   */
    2.59 -#define find_next_zero_bit(addr,size,off) \
    2.60 -((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ? \
    2.61 -  ((off)+(__scanbit(~(((*(const unsigned long *)addr)) >> (off))))) : \
    2.62 +#define find_next_zero_bit(addr,size,off)                                   \
    2.63 +((__builtin_constant_p(size) && (size) <= BITS_PER_LONG ?                   \
    2.64 +  ((off)+(__scanbit(~(((*(const unsigned long *)addr)) >> (off)), size))) : \
    2.65    __find_next_zero_bit(addr,size,off)))
    2.66  
    2.67  
    2.68 @@ -391,8 +390,7 @@ static inline unsigned int __scanbit(uns
    2.69   * find_first_set_bit - find the first set bit in @word
    2.70   * @word: the word to search
    2.71   * 
    2.72 - * Returns the bit-number of the first set bit. If no bits are set then the
    2.73 - * result is undefined.
    2.74 + * Returns the bit-number of the first set bit. The input must *not* be zero.
    2.75   */
    2.76  static inline unsigned int find_first_set_bit(unsigned long word)
    2.77  {
    2.78 @@ -401,26 +399,10 @@ static inline unsigned int find_first_se
    2.79  }
    2.80  
    2.81  /**
    2.82 - * ffz - find first zero in word.
    2.83 - * @word: The word to search
    2.84 - *
    2.85 - * Undefined if no zero exists, so code should check against ~0UL first.
    2.86 - */
    2.87 -static inline unsigned long ffz(unsigned long word)
    2.88 -{
    2.89 -    asm ( "bsf %1,%0"
    2.90 -          :"=r" (word)
    2.91 -          :"r" (~word));
    2.92 -    return word;
    2.93 -}
    2.94 -
    2.95 -/**
    2.96   * ffs - find first bit set
    2.97   * @x: the word to search
    2.98   *
    2.99 - * This is defined the same way as
   2.100 - * the libc and compiler builtin ffs routines, therefore
   2.101 - * differs in spirit from the above ffz (man ffs).
   2.102 + * This is defined the same way as the libc and compiler builtin ffs routines.
   2.103   */
   2.104  static inline int ffs(unsigned long x)
   2.105  {