f2fs: refactor __find_rev_next_{zero}_bit
This patch refactors __find_rev_next_{zero}_bit which was disabled previously
due to bugs.
Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
index f37c212..7835e41 100644
--- a/fs/f2fs/segment.c
+++ b/fs/f2fs/segment.c
@@ -29,6 +29,21 @@
static struct kmem_cache *sit_entry_set_slab;
static struct kmem_cache *inmem_entry_slab;
+static unsigned long __reverse_ulong(unsigned char *str)
+{
+ unsigned long tmp = 0;
+ int shift = 24, idx = 0;
+
+#if BITS_PER_LONG == 64
+ shift = 56;
+#endif
+ while (shift >= 0) {
+ tmp |= (unsigned long)str[idx++] << shift;
+ shift -= BITS_PER_BYTE;
+ }
+ return tmp;
+}
+
/*
* __reverse_ffs is copied from include/asm-generic/bitops/__ffs.h since
* MSB and LSB are reversed in a byte by f2fs_set_bit.
@@ -38,27 +53,31 @@
int num = 0;
#if BITS_PER_LONG == 64
- if ((word & 0xffffffff) == 0) {
+ if ((word & 0xffffffff00000000UL) == 0)
num += 32;
+ else
word >>= 32;
- }
#endif
- if ((word & 0xffff) == 0) {
+ if ((word & 0xffff0000) == 0)
num += 16;
+ else
word >>= 16;
- }
- if ((word & 0xff) == 0) {
+
+ if ((word & 0xff00) == 0)
num += 8;
+ else
word >>= 8;
- }
+
if ((word & 0xf0) == 0)
num += 4;
else
word >>= 4;
+
if ((word & 0xc) == 0)
num += 2;
else
word >>= 2;
+
if ((word & 0x2) == 0)
num += 1;
return num;
@@ -68,26 +87,16 @@
* __find_rev_next(_zero)_bit is copied from lib/find_next_bit.c because
* f2fs_set_bit makes MSB and LSB reversed in a byte.
* Example:
- * LSB <--> MSB
- * f2fs_set_bit(0, bitmap) => 0000 0001
- * f2fs_set_bit(7, bitmap) => 1000 0000
+ * MSB <--> LSB
+ * f2fs_set_bit(0, bitmap) => 1000 0000
+ * f2fs_set_bit(7, bitmap) => 0000 0001
*/
static unsigned long __find_rev_next_bit(const unsigned long *addr,
unsigned long size, unsigned long offset)
{
- while (!f2fs_test_bit(offset, (unsigned char *)addr))
- offset++;
-
- if (offset > size)
- offset = size;
-
- return offset;
-#if 0
const unsigned long *p = addr + BIT_WORD(offset);
unsigned long result = offset & ~(BITS_PER_LONG - 1);
unsigned long tmp;
- unsigned long mask, submask;
- unsigned long quot, rest;
if (offset >= size)
return size;
@@ -97,14 +106,9 @@
if (!offset)
goto aligned;
- tmp = *(p++);
- quot = (offset >> 3) << 3;
- rest = offset & 0x7;
- mask = ~0UL << quot;
- submask = (unsigned char)(0xff << rest) >> rest;
- submask <<= quot;
- mask &= submask;
- tmp &= mask;
+ tmp = __reverse_ulong((unsigned char *)p);
+ tmp &= ~0UL >> offset;
+
if (size < BITS_PER_LONG)
goto found_first;
if (tmp)
@@ -112,42 +116,34 @@
size -= BITS_PER_LONG;
result += BITS_PER_LONG;
+ p++;
aligned:
while (size & ~(BITS_PER_LONG-1)) {
- tmp = *(p++);
+ tmp = __reverse_ulong((unsigned char *)p);
if (tmp)
goto found_middle;
result += BITS_PER_LONG;
size -= BITS_PER_LONG;
+ p++;
}
if (!size)
return result;
- tmp = *p;
+
+ tmp = __reverse_ulong((unsigned char *)p);
found_first:
- tmp &= (~0UL >> (BITS_PER_LONG - size));
- if (tmp == 0UL) /* Are any bits set? */
+ tmp &= (~0UL << (BITS_PER_LONG - size));
+ if (!tmp) /* Are any bits set? */
return result + size; /* Nope. */
found_middle:
return result + __reverse_ffs(tmp);
-#endif
}
static unsigned long __find_rev_next_zero_bit(const unsigned long *addr,
unsigned long size, unsigned long offset)
{
- while (f2fs_test_bit(offset, (unsigned char *)addr))
- offset++;
-
- if (offset > size)
- offset = size;
-
- return offset;
-#if 0
const unsigned long *p = addr + BIT_WORD(offset);
unsigned long result = offset & ~(BITS_PER_LONG - 1);
unsigned long tmp;
- unsigned long mask, submask;
- unsigned long quot, rest;
if (offset >= size)
return size;
@@ -157,40 +153,36 @@
if (!offset)
goto aligned;
- tmp = *(p++);
- quot = (offset >> 3) << 3;
- rest = offset & 0x7;
- mask = ~(~0UL << quot);
- submask = (unsigned char)~((unsigned char)(0xff << rest) >> rest);
- submask <<= quot;
- mask += submask;
- tmp |= mask;
+ tmp = __reverse_ulong((unsigned char *)p);
+ tmp |= ~((~0UL << offset) >> offset);
+
if (size < BITS_PER_LONG)
goto found_first;
- if (~tmp)
+ if (tmp != ~0UL)
goto found_middle;
size -= BITS_PER_LONG;
result += BITS_PER_LONG;
+ p++;
aligned:
while (size & ~(BITS_PER_LONG - 1)) {
- tmp = *(p++);
- if (~tmp)
+ tmp = __reverse_ulong((unsigned char *)p);
+ if (tmp != ~0UL)
goto found_middle;
result += BITS_PER_LONG;
size -= BITS_PER_LONG;
+ p++;
}
if (!size)
return result;
- tmp = *p;
+ tmp = __reverse_ulong((unsigned char *)p);
found_first:
- tmp |= ~0UL << size;
- if (tmp == ~0UL) /* Are any bits zero? */
+ tmp |= ~(~0UL << (BITS_PER_LONG - size));
+ if (tmp == ~0UL) /* Are any bits zero? */
return result + size; /* Nope. */
found_middle:
return result + __reverse_ffz(tmp);
-#endif
}
void register_inmem_page(struct inode *inode, struct page *page)