From patchwork Wed Oct 21 21:16:43 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jaegeuk Kim X-Patchwork-Id: 7460691 Return-Path: X-Original-To: patchwork-linux-fsdevel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork1.web.kernel.org (Postfix) with ESMTP id 0C8249F37F for ; Wed, 21 Oct 2015 21:17:28 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id F2CC420800 for ; Wed, 21 Oct 2015 21:17:26 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id CE8B6207F7 for ; Wed, 21 Oct 2015 21:17:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753777AbbJUVRJ (ORCPT ); Wed, 21 Oct 2015 17:17:09 -0400 Received: from mail.kernel.org ([198.145.29.136]:58239 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751575AbbJUVRI (ORCPT ); Wed, 21 Oct 2015 17:17:08 -0400 Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 27A2520800; Wed, 21 Oct 2015 21:17:07 +0000 (UTC) Received: from localhost (unknown [166.177.251.2]) (using TLSv1.2 with cipher AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id 35EB9207F7; Wed, 21 Oct 2015 21:17:06 +0000 (UTC) From: Jaegeuk Kim To: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, linux-f2fs-devel@lists.sourceforge.net Cc: Jaegeuk Kim Subject: [PATCH] f2fs: refactor __find_rev_next_{zero}_bit Date: Wed, 21 Oct 2015 14:16:43 -0700 Message-Id: <1445462203-44072-1-git-send-email-jaegeuk@kernel.org> X-Mailer: git-send-email 2.1.1 X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Sender: linux-fsdevel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP This patch refactors __find_rev_next_{zero}_bit which was disabled previously due to bugs. Signed-off-by: Jaegeuk Kim --- fs/f2fs/segment.c | 106 +++++++++++++++++++++++++----------------------------- 1 file changed, 49 insertions(+), 57 deletions(-) diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c index f37c212..50afc93 100644 --- a/fs/f2fs/segment.c +++ b/fs/f2fs/segment.c @@ -29,6 +29,21 @@ static struct kmem_cache *discard_entry_slab; 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 @@ static inline unsigned long __reverse_ffs(unsigned long word) int num = 0; #if BITS_PER_LONG == 64 - if ((word & 0xffffffff) == 0) { + if ((word & 0xffffffff00000000) == 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 @@ static inline unsigned long __reverse_ffs(unsigned long word) * __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 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr, 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 @@ static unsigned long __find_rev_next_bit(const unsigned long *addr, 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 @@ static unsigned long __find_rev_next_zero_bit(const unsigned long *addr, 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)