Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755267AbcK1T5i (ORCPT ); Mon, 28 Nov 2016 14:57:38 -0500 Received: from p3plsmtps2ded03.prod.phx3.secureserver.net ([208.109.80.60]:39700 "EHLO p3plsmtps2ded03.prod.phx3.secureserver.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755074AbcK1T4s (ORCPT ); Mon, 28 Nov 2016 14:56:48 -0500 x-originating-ip: 72.167.245.219 From: Matthew Wilcox To: linux-kernel@vger.kernel.org, Andrew Morton , Konstantin Khlebnikov , Ross Zwisler Cc: Matthew Wilcox , linux-mm@kvack.org, linux-fsdevel@vger.kernel.org, "Kirill A . Shutemov" Subject: [PATCH v3 13/33] radix tree test suite: Use common find-bit code Date: Mon, 28 Nov 2016 13:50:17 -0800 Message-Id: <1480369871-5271-14-git-send-email-mawilcox@linuxonhyperv.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1480369871-5271-1-git-send-email-mawilcox@linuxonhyperv.com> References: <1480369871-5271-1-git-send-email-mawilcox@linuxonhyperv.com> X-CMAE-Envelope: MS4wfPu6VWr3ivE3AIRQlphy6f7oXVzSquxKUZ7iqShwBAcoNjJTrtPDLpHLBxVf53avmhYmqJIIp85RK1qa7Nqv3khOlpG2bi06X3hJrxuz9NB+gmWEWLZF 5Ok0U+ClfhKJ4H2IoyRzY5wFTlWBrXEFRdKN/6MQLbT2oG6N++tLNFXOFy7nSUurQHXYqDXsnQXfwlF3U5bGCUUjeRWm9ccuDDyoGkN0UKyaUZdOaHK8gU7k dLQNsPwNjDquqf6HuVkVDTDuMHQK16tfbb2w/OvmTB0NlwxWgvAtaWq8nB5Dzadi9pO0/5YUjnuWa1y9hUk/1Ml3Jy1IxU4rjN6/Eav+8DQiLo+V1rUZ/ZbH THx+LDxwKlIw43tIOietHX3k1I6VWNnUKITKl2ET/rgX4mCMfpChjeT6xG6num6ctTTDNKmvFdF+WTjoPkRkuRVfwSaVkYOlwyGzCA0UBz23t21FavE= Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 9702 Lines: 289 From: Matthew Wilcox Remove the old find_next_bit code in favour of linking in the find_bit code from tools/lib. Signed-off-by: Matthew Wilcox --- tools/testing/radix-tree/Makefile | 7 ++- tools/testing/radix-tree/find_next_bit.c | 57 ---------------------- tools/testing/radix-tree/linux/bitops.h | 40 +++++++++------ tools/testing/radix-tree/linux/bitops/non-atomic.h | 13 +++-- tools/testing/radix-tree/linux/kernel.h | 11 +++++ 5 files changed, 48 insertions(+), 80 deletions(-) delete mode 100644 tools/testing/radix-tree/find_next_bit.c diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 08283a8..3635e4d 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -18,7 +18,12 @@ main: $(OFILES) clean: $(RM) -f $(TARGETS) *.o radix-tree.c -$(OFILES): *.h */*.h ../../../include/linux/radix-tree.h ../../include/linux/*.h +find_next_bit.o: ../../lib/find_bit.c + $(CC) $(CFLAGS) -c -o $@ $< + +$(OFILES): *.h */*.h \ + ../../include/linux/*.h \ + ../../../include/linux/radix-tree.h radix-tree.c: ../../../lib/radix-tree.c sed -e 's/^static //' -e 's/__always_inline //' -e 's/inline //' < $< > $@ diff --git a/tools/testing/radix-tree/find_next_bit.c b/tools/testing/radix-tree/find_next_bit.c deleted file mode 100644 index d1c2178..0000000 --- a/tools/testing/radix-tree/find_next_bit.c +++ /dev/null @@ -1,57 +0,0 @@ -/* find_next_bit.c: fallback find next bit implementation - * - * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved. - * Written by David Howells (dhowells@redhat.com) - * - * This program is free software; you can redistribute it and/or - * modify it under the terms of the GNU General Public License - * as published by the Free Software Foundation; either version - * 2 of the License, or (at your option) any later version. - */ - -#include -#include - -#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) - -/* - * Find the next set bit in a memory region. - */ -unsigned long find_next_bit(const unsigned long *addr, unsigned long size, - unsigned long offset) -{ - const unsigned long *p = addr + BITOP_WORD(offset); - unsigned long result = offset & ~(BITS_PER_LONG-1); - unsigned long tmp; - - if (offset >= size) - return size; - size -= result; - offset %= BITS_PER_LONG; - if (offset) { - tmp = *(p++); - tmp &= (~0UL << offset); - if (size < BITS_PER_LONG) - goto found_first; - if (tmp) - goto found_middle; - size -= BITS_PER_LONG; - result += BITS_PER_LONG; - } - while (size & ~(BITS_PER_LONG-1)) { - if ((tmp = *(p++))) - 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 + __ffs(tmp); -} diff --git a/tools/testing/radix-tree/linux/bitops.h b/tools/testing/radix-tree/linux/bitops.h index 71d58427..a13e9bc 100644 --- a/tools/testing/radix-tree/linux/bitops.h +++ b/tools/testing/radix-tree/linux/bitops.h @@ -2,9 +2,14 @@ #define _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ #include +#include +#include +#include -#define BITOP_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) -#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) +#define BIT_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) +#define BITS_PER_BYTE 8 +#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long)) /** * __set_bit - Set a bit in memory @@ -17,16 +22,16 @@ */ static inline void __set_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); *p |= mask; } static inline void __clear_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); *p &= ~mask; } @@ -42,8 +47,8 @@ static inline void __clear_bit(int nr, volatile unsigned long *addr) */ static inline void __change_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); *p ^= mask; } @@ -59,8 +64,8 @@ static inline void __change_bit(int nr, volatile unsigned long *addr) */ static inline int __test_and_set_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); unsigned long old = *p; *p = old | mask; @@ -78,8 +83,8 @@ static inline int __test_and_set_bit(int nr, volatile unsigned long *addr) */ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); unsigned long old = *p; *p = old & ~mask; @@ -90,8 +95,8 @@ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr) static inline int __test_and_change_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); - unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); + unsigned long mask = BIT_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BIT_WORD(nr); unsigned long old = *p; *p = old ^ mask; @@ -105,7 +110,7 @@ static inline int __test_and_change_bit(int nr, */ static inline int test_bit(int nr, const volatile unsigned long *addr) { - return 1UL & (addr[BITOP_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); + return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); } /** @@ -147,4 +152,9 @@ unsigned long find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset); +static inline unsigned long hweight_long(unsigned long w) +{ + return sizeof(w) == 4 ? hweight32(w) : hweight64(w); +} + #endif /* _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/non-atomic.h b/tools/testing/radix-tree/linux/bitops/non-atomic.h index 46a825c..6a1bcb9 100644 --- a/tools/testing/radix-tree/linux/bitops/non-atomic.h +++ b/tools/testing/radix-tree/linux/bitops/non-atomic.h @@ -3,7 +3,6 @@ #include -#define BITOP_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) /** @@ -17,7 +16,7 @@ */ static inline void __set_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); + unsigned long mask = BIT_MASK(nr); unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); *p |= mask; @@ -25,7 +24,7 @@ static inline void __set_bit(int nr, volatile unsigned long *addr) static inline void __clear_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); + unsigned long mask = BIT_MASK(nr); unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); *p &= ~mask; @@ -42,7 +41,7 @@ static inline void __clear_bit(int nr, volatile unsigned long *addr) */ static inline void __change_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); + unsigned long mask = BIT_MASK(nr); unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); *p ^= mask; @@ -59,7 +58,7 @@ static inline void __change_bit(int nr, volatile unsigned long *addr) */ static inline int __test_and_set_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); + unsigned long mask = BIT_MASK(nr); unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); unsigned long old = *p; @@ -78,7 +77,7 @@ static inline int __test_and_set_bit(int nr, volatile unsigned long *addr) */ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); + unsigned long mask = BIT_MASK(nr); unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); unsigned long old = *p; @@ -90,7 +89,7 @@ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr) static inline int __test_and_change_bit(int nr, volatile unsigned long *addr) { - unsigned long mask = BITOP_MASK(nr); + unsigned long mask = BIT_MASK(nr); unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); unsigned long old = *p; diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index dbe4b92..23e77f5 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -47,4 +47,15 @@ static inline int in_interrupt(void) { return 0; } + +/* + * This looks more complex than it should be. But we need to + * get the type for the ~ right in round_down (it needs to be + * as wide as the result!), and we want to evaluate the macro + * arguments just once each. + */ +#define __round_mask(x, y) ((__typeof__(x))((y)-1)) +#define round_up(x, y) ((((x)-1) | __round_mask(x, y))+1) +#define round_down(x, y) ((x) & ~__round_mask(x, y)) + #endif /* _KERNEL_H */ -- 2.10.2