Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/x86/linux-2.6-generic-bitops-v3

* 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/x86/linux-2.6-generic-bitops-v3:
  x86, bitops: select the generic bitmap search functions
  x86: include/asm-x86/pgalloc.h/bitops.h: checkpatch cleanups - formatting only
  x86: finalize bitops unification
  x86, UML: remove x86-specific implementations of find_first_bit
  x86: optimize find_first_bit for small bitmaps
  x86: switch 64-bit to generic find_first_bit
  x86: generic versions of find_first_(zero_)bit, convert i386
  bitops: use __fls for fls64 on 64-bit archs
  generic: implement __fls on all 64-bit archs
  generic: introduce a generic __fls implementation
  x86: merge the simple bitops and move them to bitops.h
  x86, generic: optimize find_next_(zero_)bit for small constant-size bitmaps
  x86, uml: fix uml with generic find_next_bit for x86
  x86: change x86 to use generic find_next_bit
  uml: Kconfig cleanup
  uml: fix build error

1 files changed, 140 insertions, 0 deletions

diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 40d54731de7e..48bde600a2db 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -112,4 +112,144 @@ static inline unsigned fls_long(unsigned long l)
         return fls64(l);
 }
 
+#ifdef __KERNEL__
+#ifdef CONFIG_GENERIC_FIND_FIRST_BIT
+extern unsigned long __find_first_bit(const unsigned long *addr,
+                unsigned long size);
+
+/**
+ * find_first_bit - find the first set bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The maximum size to search
+ *
+ * Returns the bit number of the first set bit.
+ */
+static __always_inline unsigned long
+find_first_bit(const unsigned long *addr, unsigned long size)
+{
+        /* Avoid a function call if the bitmap size is a constant */
+        /* and not bigger than BITS_PER_LONG. */
+
+        /* insert a sentinel so that __ffs returns size if there */
+        /* are no set bits in the bitmap */
+        if (__builtin_constant_p(size) && (size < BITS_PER_LONG))
+                return __ffs((*addr) | (1ul << size));
+
+        /* the result of __ffs(0) is undefined, so it needs to be */
+        /* handled separately */
+        if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
+                return ((*addr) == 0) ? BITS_PER_LONG : __ffs(*addr);
+
+        /* size is not constant or too big */
+        return __find_first_bit(addr, size);
+}
+
+extern unsigned long __find_first_zero_bit(const unsigned long *addr,
+                unsigned long size);
+
+/**
+ * find_first_zero_bit - find the first cleared bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The maximum size to search
+ *
+ * Returns the bit number of the first cleared bit.
+ */
+static __always_inline unsigned long
+find_first_zero_bit(const unsigned long *addr, unsigned long size)
+{
+        /* Avoid a function call if the bitmap size is a constant */
+        /* and not bigger than BITS_PER_LONG. */
+
+        /* insert a sentinel so that __ffs returns size if there */
+        /* are no set bits in the bitmap */
+        if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
+                return __ffs(~(*addr) | (1ul << size));
+        }
+
+        /* the result of __ffs(0) is undefined, so it needs to be */
+        /* handled separately */
+        if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
+                return (~(*addr) == 0) ? BITS_PER_LONG : __ffs(~(*addr));
+
+        /* size is not constant or too big */
+        return __find_first_zero_bit(addr, size);
+}
+#endif /* CONFIG_GENERIC_FIND_FIRST_BIT */
+
+#ifdef CONFIG_GENERIC_FIND_NEXT_BIT
+extern unsigned long __find_next_bit(const unsigned long *addr,
+                unsigned long size, unsigned long offset);
+
+/**
+ * find_next_bit - find the next set bit in a memory region
+ * @addr: The address to base the search on
+ * @offset: The bitnumber to start searching at
+ * @size: The bitmap size in bits
+ */
+static __always_inline unsigned long
+find_next_bit(const unsigned long *addr, unsigned long size,
+                unsigned long offset)
+{
+        unsigned long value;
+
+        /* Avoid a function call if the bitmap size is a constant */
+        /* and not bigger than BITS_PER_LONG. */
+
+        /* insert a sentinel so that __ffs returns size if there */
+        /* are no set bits in the bitmap */
+        if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
+                value = (*addr) & ((~0ul) << offset);
+                value |= (1ul << size);
+                return __ffs(value);
+        }
+
+        /* the result of __ffs(0) is undefined, so it needs to be */
+        /* handled separately */
+        if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
+                value = (*addr) & ((~0ul) << offset);
+                return (value == 0) ? BITS_PER_LONG : __ffs(value);
+        }
+
+        /* size is not constant or too big */
+        return __find_next_bit(addr, size, offset);
+}
+
+extern unsigned long __find_next_zero_bit(const unsigned long *addr,
+                unsigned long size, unsigned long offset);
+
+/**
+ * find_next_zero_bit - find the next cleared bit in a memory region
+ * @addr: The address to base the search on
+ * @offset: The bitnumber to start searching at
+ * @size: The bitmap size in bits
+ */
+static __always_inline unsigned long
+find_next_zero_bit(const unsigned long *addr, unsigned long size,
+                unsigned long offset)
+{
+        unsigned long value;
+
+        /* Avoid a function call if the bitmap size is a constant */
+        /* and not bigger than BITS_PER_LONG. */
+
+        /* insert a sentinel so that __ffs returns size if there */
+        /* are no set bits in the bitmap */
+        if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
+                value = (~(*addr)) & ((~0ul) << offset);
+                value |= (1ul << size);
+                return __ffs(value);
+        }
+
+        /* the result of __ffs(0) is undefined, so it needs to be */
+        /* handled separately */
+        if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
+                value = (~(*addr)) & ((~0ul) << offset);
+                return (value == 0) ? BITS_PER_LONG : __ffs(value);
+        }
+
+        /* size is not constant or too big */
+        return __find_next_zero_bit(addr, size, offset);
+}
+#endif /* CONFIG_GENERIC_FIND_NEXT_BIT */
+#endif /* __KERNEL__ */
 #endif