* [PATCH] f2fs: introduce f2fs_find_next(_zero)_bit
@ 2013-11-15 1:42 Changman Lee
2013-11-15 4:31 ` Jaegeuk Kim
0 siblings, 1 reply; 3+ messages in thread
From: Changman Lee @ 2013-11-15 1:42 UTC (permalink / raw)
To: linux-f2fs-devel, linux-fsdevel; +Cc: Changman Lee
When f2fs_set_bit is used, in a byte MSB and LSB is reversed,
in that case we can use f2fs_find_next_bit or f2fs_find_next_zero_bit.
Signed-off-by: Changman Lee <cm224.lee@samsung.com>
---
fs/f2fs/segment.c | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 143 insertions(+)
diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
index fa284d3..b2de887 100644
--- a/fs/f2fs/segment.c
+++ b/fs/f2fs/segment.c
@@ -21,6 +21,149 @@
#include <trace/events/f2fs.h>
/*
+ * f2fs_ffs is copied from include/asm-generic/bitops/__ffs.h because
+ * MSB and LSB is reversed in a byte by f2fs_set_bit.
+ */
+static inline unsigned long f2fs_ffs(unsigned long word)
+{
+ int num = 0;
+
+#if BITS_PER_LONG == 64
+ if ((word & 0xffffffff) == 0) {
+ num += 32;
+ word >>= 32;
+ }
+#endif
+ if ((word & 0xffff) == 0) {
+ num += 16;
+ word >>= 16;
+ }
+ if ((word & 0xff) == 0) {
+ num += 8;
+ 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;
+}
+
+#define f2fs_ffz(x) f2fs_ffs(~(x))
+
+/*
+ * f2fs_find_next(_zero)_bit is copied from lib/find_next_bit.c becasue
+ * 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
+ */
+static unsigned long f2fs_find_next_bit(const unsigned long *addr,
+ unsigned long size, unsigned long offset)
+{
+ 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;
+ size -= result;
+ offset %= BITS_PER_LONG;
+ 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;
+ if (size < BITS_PER_LONG)
+ goto found_first;
+ if (tmp)
+ goto found_middle;
+ size -= BITS_PER_LONG;
+ result += BITS_PER_LONG;
+aligned:
+ while (size & ~(BITS_PER_LONG-1)) {
+ tmp = *(p++);
+ if (tmp)
+ goto found_middle;
+ result += BITS_PER_LONG;
+ size -= BITS_PER_LONG;
+ }
+ if (!size)
+ return result;
+ tmp = *p;
+
+found_first:
+ tmp &= (~0UL >> (BITS_PER_LONG - size));
+ if (tmp == 0UL) /* Are any bits set? */
+ return result + size; /* Nope. */
+found_middle:
+ return result + f2fs_ffs(tmp);
+}
+
+static unsigned long f2fs_find_next_zero_bit(const unsigned long *addr,
+ unsigned long size, unsigned long offset)
+{
+ 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;
+ size -= result;
+ offset %= BITS_PER_LONG;
+ 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;
+ if (size < BITS_PER_LONG)
+ goto found_first;
+ if (~tmp)
+ goto found_middle;
+ size -= BITS_PER_LONG;
+ result += BITS_PER_LONG;
+aligned:
+ while (size & ~(BITS_PER_LONG - 1)) {
+ tmp = *(p++);
+ if (~tmp)
+ goto found_middle;
+ result += BITS_PER_LONG;
+ size -= BITS_PER_LONG;
+ }
+ if (!size)
+ return result;
+ tmp = *p;
+
+found_first:
+ tmp |= ~0UL << size;
+ if (tmp == ~0UL) /* Are any bits zero? */
+ return result + size; /* Nope. */
+found_middle:
+ return result + f2fs_ffz(tmp);
+}
+
+/*
* This function balances dirty node and dentry pages.
* In addition, it controls garbage collection.
*/
--
1.7.10.4
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH] f2fs: introduce f2fs_find_next(_zero)_bit
2013-11-15 1:42 [PATCH] f2fs: introduce f2fs_find_next(_zero)_bit Changman Lee
@ 2013-11-15 4:31 ` Jaegeuk Kim
2013-11-15 5:19 ` Changman Lee
0 siblings, 1 reply; 3+ messages in thread
From: Jaegeuk Kim @ 2013-11-15 4:31 UTC (permalink / raw)
To: Changman Lee; +Cc: linux-fsdevel, linux-f2fs-devel
Hi,
IMO, it would be better give names like __find_rev_next(_zero)_bit.
If there is no objection, I'll modify and apply them by myself.
Thanks, :)
2013-11-15 (금), 10:42 +0900, Changman Lee:
> When f2fs_set_bit is used, in a byte MSB and LSB is reversed,
> in that case we can use f2fs_find_next_bit or f2fs_find_next_zero_bit.
>
> Signed-off-by: Changman Lee <cm224.lee@samsung.com>
> ---
> fs/f2fs/segment.c | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 143 insertions(+)
>
> diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
> index fa284d3..b2de887 100644
> --- a/fs/f2fs/segment.c
> +++ b/fs/f2fs/segment.c
> @@ -21,6 +21,149 @@
> #include <trace/events/f2fs.h>
>
> /*
> + * f2fs_ffs is copied from include/asm-generic/bitops/__ffs.h because
> + * MSB and LSB is reversed in a byte by f2fs_set_bit.
> + */
> +static inline unsigned long f2fs_ffs(unsigned long word)
> +{
> + int num = 0;
> +
> +#if BITS_PER_LONG == 64
> + if ((word & 0xffffffff) == 0) {
> + num += 32;
> + word >>= 32;
> + }
> +#endif
> + if ((word & 0xffff) == 0) {
> + num += 16;
> + word >>= 16;
> + }
> + if ((word & 0xff) == 0) {
> + num += 8;
> + 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;
> +}
> +
> +#define f2fs_ffz(x) f2fs_ffs(~(x))
> +
> +/*
> + * f2fs_find_next(_zero)_bit is copied from lib/find_next_bit.c becasue
> + * 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
> + */
> +static unsigned long f2fs_find_next_bit(const unsigned long *addr,
> + unsigned long size, unsigned long offset)
> +{
> + 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;
> + size -= result;
> + offset %= BITS_PER_LONG;
> + 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;
> + if (size < BITS_PER_LONG)
> + goto found_first;
> + if (tmp)
> + goto found_middle;
> + size -= BITS_PER_LONG;
> + result += BITS_PER_LONG;
> +aligned:
> + while (size & ~(BITS_PER_LONG-1)) {
> + tmp = *(p++);
> + if (tmp)
> + goto found_middle;
> + result += BITS_PER_LONG;
> + size -= BITS_PER_LONG;
> + }
> + if (!size)
> + return result;
> + tmp = *p;
> +
> +found_first:
> + tmp &= (~0UL >> (BITS_PER_LONG - size));
> + if (tmp == 0UL) /* Are any bits set? */
> + return result + size; /* Nope. */
> +found_middle:
> + return result + f2fs_ffs(tmp);
> +}
> +
> +static unsigned long f2fs_find_next_zero_bit(const unsigned long *addr,
> + unsigned long size, unsigned long offset)
> +{
> + 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;
> + size -= result;
> + offset %= BITS_PER_LONG;
> + 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;
> + if (size < BITS_PER_LONG)
> + goto found_first;
> + if (~tmp)
> + goto found_middle;
> + size -= BITS_PER_LONG;
> + result += BITS_PER_LONG;
> +aligned:
> + while (size & ~(BITS_PER_LONG - 1)) {
> + tmp = *(p++);
> + if (~tmp)
> + goto found_middle;
> + result += BITS_PER_LONG;
> + size -= BITS_PER_LONG;
> + }
> + if (!size)
> + return result;
> + tmp = *p;
> +
> +found_first:
> + tmp |= ~0UL << size;
> + if (tmp == ~0UL) /* Are any bits zero? */
> + return result + size; /* Nope. */
> +found_middle:
> + return result + f2fs_ffz(tmp);
> +}
> +
> +/*
> * This function balances dirty node and dentry pages.
> * In addition, it controls garbage collection.
> */
--
Jaegeuk Kim
Samsung
------------------------------------------------------------------------------
DreamFactory - Open Source REST & JSON Services for HTML5 & Native Apps
OAuth, Users, Roles, SQL, NoSQL, BLOB Storage and External API Access
Free app hosting. Or install the open source package on any LAMP server.
Sign up and see examples for AngularJS, jQuery, Sencha Touch and Native!
http://pubads.g.doubleclick.net/gampad/clk?id=63469471&iu=/4140/ostg.clktrk
_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] f2fs: introduce f2fs_find_next(_zero)_bit
2013-11-15 4:31 ` Jaegeuk Kim
@ 2013-11-15 5:19 ` Changman Lee
0 siblings, 0 replies; 3+ messages in thread
From: Changman Lee @ 2013-11-15 5:19 UTC (permalink / raw)
To: jaegeuk.kim; +Cc: linux-fsdevel, linux-f2fs-devel
I agree. Your suggestion is more good.
Thanks for your review.
On 2013년 11월 15일 13:31, Jaegeuk Kim wrote:
> Hi,
>
> IMO, it would be better give names like __find_rev_next(_zero)_bit.
> If there is no objection, I'll modify and apply them by myself.
> Thanks, :)
>
> 2013-11-15 (금), 10:42 +0900, Changman Lee:
>> When f2fs_set_bit is used, in a byte MSB and LSB is reversed,
>> in that case we can use f2fs_find_next_bit or f2fs_find_next_zero_bit.
>>
>> Signed-off-by: Changman Lee <cm224.lee@samsung.com>
>> ---
>> fs/f2fs/segment.c | 143 +++++++++++++++++++++++++++++++++++++++++++++++++++++
>> 1 file changed, 143 insertions(+)
>>
>> diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
>> index fa284d3..b2de887 100644
>> --- a/fs/f2fs/segment.c
>> +++ b/fs/f2fs/segment.c
>> @@ -21,6 +21,149 @@
>> #include <trace/events/f2fs.h>
>>
>> /*
>> + * f2fs_ffs is copied from include/asm-generic/bitops/__ffs.h because
>> + * MSB and LSB is reversed in a byte by f2fs_set_bit.
>> + */
>> +static inline unsigned long f2fs_ffs(unsigned long word)
>> +{
>> + int num = 0;
>> +
>> +#if BITS_PER_LONG == 64
>> + if ((word & 0xffffffff) == 0) {
>> + num += 32;
>> + word >>= 32;
>> + }
>> +#endif
>> + if ((word & 0xffff) == 0) {
>> + num += 16;
>> + word >>= 16;
>> + }
>> + if ((word & 0xff) == 0) {
>> + num += 8;
>> + 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;
>> +}
>> +
>> +#define f2fs_ffz(x) f2fs_ffs(~(x))
>> +
>> +/*
>> + * f2fs_find_next(_zero)_bit is copied from lib/find_next_bit.c becasue
>> + * 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
>> + */
>> +static unsigned long f2fs_find_next_bit(const unsigned long *addr,
>> + unsigned long size, unsigned long offset)
>> +{
>> + 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;
>> + size -= result;
>> + offset %= BITS_PER_LONG;
>> + 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;
>> + if (size < BITS_PER_LONG)
>> + goto found_first;
>> + if (tmp)
>> + goto found_middle;
>> + size -= BITS_PER_LONG;
>> + result += BITS_PER_LONG;
>> +aligned:
>> + while (size & ~(BITS_PER_LONG-1)) {
>> + tmp = *(p++);
>> + if (tmp)
>> + goto found_middle;
>> + result += BITS_PER_LONG;
>> + size -= BITS_PER_LONG;
>> + }
>> + if (!size)
>> + return result;
>> + tmp = *p;
>> +
>> +found_first:
>> + tmp &= (~0UL >> (BITS_PER_LONG - size));
>> + if (tmp == 0UL) /* Are any bits set? */
>> + return result + size; /* Nope. */
>> +found_middle:
>> + return result + f2fs_ffs(tmp);
>> +}
>> +
>> +static unsigned long f2fs_find_next_zero_bit(const unsigned long *addr,
>> + unsigned long size, unsigned long offset)
>> +{
>> + 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;
>> + size -= result;
>> + offset %= BITS_PER_LONG;
>> + 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;
>> + if (size < BITS_PER_LONG)
>> + goto found_first;
>> + if (~tmp)
>> + goto found_middle;
>> + size -= BITS_PER_LONG;
>> + result += BITS_PER_LONG;
>> +aligned:
>> + while (size & ~(BITS_PER_LONG - 1)) {
>> + tmp = *(p++);
>> + if (~tmp)
>> + goto found_middle;
>> + result += BITS_PER_LONG;
>> + size -= BITS_PER_LONG;
>> + }
>> + if (!size)
>> + return result;
>> + tmp = *p;
>> +
>> +found_first:
>> + tmp |= ~0UL << size;
>> + if (tmp == ~0UL) /* Are any bits zero? */
>> + return result + size; /* Nope. */
>> +found_middle:
>> + return result + f2fs_ffz(tmp);
>> +}
>> +
>> +/*
>> * This function balances dirty node and dentry pages.
>> * In addition, it controls garbage collection.
>> */
------------------------------------------------------------------------------
DreamFactory - Open Source REST & JSON Services for HTML5 & Native Apps
OAuth, Users, Roles, SQL, NoSQL, BLOB Storage and External API Access
Free app hosting. Or install the open source package on any LAMP server.
Sign up and see examples for AngularJS, jQuery, Sencha Touch and Native!
http://pubads.g.doubleclick.net/gampad/clk?id=63469471&iu=/4140/ostg.clktrk
_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2013-11-15 5:19 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2013-11-15 1:42 [PATCH] f2fs: introduce f2fs_find_next(_zero)_bit Changman Lee
2013-11-15 4:31 ` Jaegeuk Kim
2013-11-15 5:19 ` Changman Lee
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).