From 5aa5bd14c5f8660c64ceedf14a549781be47e53d Mon Sep 17 00:00:00 2001 From: Daniel Borkmann Date: Mon, 17 Oct 2016 14:28:36 +0200 Subject: bpf: add initial suite for selftests Add a start of a test suite for kernel selftests. This moves test_verifier and test_maps over to tools/testing/selftests/bpf/ along with various code improvements and also adds a script for invoking test_bpf module. The test suite can simply be run via selftest framework, f.e.: # cd tools/testing/selftests/bpf/ # make # make run_tests Both test_verifier and test_maps were kind of misplaced in samples/bpf/ directory and we were looking into adding them to selftests for a while now, so it can be picked up by kbuild bot et al and hopefully also get more exposure and thus new test case additions. Signed-off-by: Daniel Borkmann Acked-by: Alexei Starovoitov Signed-off-by: David S. Miller --- tools/include/linux/filter.h | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) (limited to 'tools/include/linux') diff --git a/tools/include/linux/filter.h b/tools/include/linux/filter.h index 3276625595b2..122153b16ea4 100644 --- a/tools/include/linux/filter.h +++ b/tools/include/linux/filter.h @@ -218,6 +218,30 @@ .off = OFF, \ .imm = IMM }) +/* BPF_LD_IMM64 macro encodes single 'load 64-bit immediate' insn */ + +#define BPF_LD_IMM64(DST, IMM) \ + BPF_LD_IMM64_RAW(DST, 0, IMM) + +#define BPF_LD_IMM64_RAW(DST, SRC, IMM) \ + ((struct bpf_insn) { \ + .code = BPF_LD | BPF_DW | BPF_IMM, \ + .dst_reg = DST, \ + .src_reg = SRC, \ + .off = 0, \ + .imm = (__u32) (IMM) }), \ + ((struct bpf_insn) { \ + .code = 0, /* zero is reserved opcode */ \ + .dst_reg = 0, \ + .src_reg = 0, \ + .off = 0, \ + .imm = ((__u64) (IMM)) >> 32 }) + +/* pseudo BPF_LD_IMM64 insn used to refer to process-local map_fd */ + +#define BPF_LD_MAP_FD(DST, MAP_FD) \ + BPF_LD_IMM64_RAW(DST, BPF_PSEUDO_MAP_FD, MAP_FD) + /* Program exit */ #define BPF_EXIT_INSN() \ -- cgit v1.2.3 From 02bc11de567273da8ab25c54336ddbb71986f38f Mon Sep 17 00:00:00 2001 From: Jiri Olsa Date: Mon, 10 Oct 2016 09:26:33 +0200 Subject: tools lib: Add for_each_clear_bit macro Adding for_each_clear_bit macro plus all its the necessary backbone functions. Taken from related kernel code. It will be used in following patch. Signed-off-by: Jiri Olsa Cc: Adrian Hunter Cc: David Ahern Cc: Namhyung Kim Cc: Wang Nan Link: http://lkml.kernel.org/n/tip-cayv2zbqi0nlmg5sjjxs1775@git.kernel.org Signed-off-by: Arnaldo Carvalho de Melo --- tools/include/asm-generic/bitops.h | 1 + tools/include/asm-generic/bitops/__ffz.h | 12 ++++++++++++ tools/include/asm-generic/bitops/find.h | 28 ++++++++++++++++++++++++++++ tools/include/linux/bitops.h | 5 +++++ tools/lib/find_bit.c | 25 +++++++++++++++++++++++++ tools/perf/MANIFEST | 1 + 6 files changed, 72 insertions(+) create mode 100644 tools/include/asm-generic/bitops/__ffz.h (limited to 'tools/include/linux') diff --git a/tools/include/asm-generic/bitops.h b/tools/include/asm-generic/bitops.h index 653d1bad77de..0304600121da 100644 --- a/tools/include/asm-generic/bitops.h +++ b/tools/include/asm-generic/bitops.h @@ -13,6 +13,7 @@ */ #include +#include #include #include #include diff --git a/tools/include/asm-generic/bitops/__ffz.h b/tools/include/asm-generic/bitops/__ffz.h new file mode 100644 index 000000000000..6744bd4cdf46 --- /dev/null +++ b/tools/include/asm-generic/bitops/__ffz.h @@ -0,0 +1,12 @@ +#ifndef _ASM_GENERIC_BITOPS_FFZ_H_ +#define _ASM_GENERIC_BITOPS_FFZ_H_ + +/* + * ffz - find first zero in word. + * @word: The word to search + * + * Undefined if no zero exists, so code should check against ~0UL first. + */ +#define ffz(x) __ffs(~(x)) + +#endif /* _ASM_GENERIC_BITOPS_FFZ_H_ */ diff --git a/tools/include/asm-generic/bitops/find.h b/tools/include/asm-generic/bitops/find.h index 31f51547fcd4..5538ecdc964a 100644 --- a/tools/include/asm-generic/bitops/find.h +++ b/tools/include/asm-generic/bitops/find.h @@ -15,6 +15,21 @@ extern unsigned long find_next_bit(const unsigned long *addr, unsigned long size, unsigned long offset); #endif +#ifndef find_next_zero_bit + +/** + * 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 + * + * Returns the bit number of the next zero bit + * If no bits are zero, returns @size. + */ +unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, + unsigned long offset); +#endif + #ifndef find_first_bit /** @@ -30,4 +45,17 @@ extern unsigned long find_first_bit(const unsigned long *addr, #endif /* find_first_bit */ +#ifndef find_first_zero_bit + +/** + * find_first_zero_bit - find the first cleared bit in a memory region + * @addr: The address to start the search at + * @size: The maximum number of bits to search + * + * Returns the bit number of the first cleared bit. + * If no bits are zero, returns @size. + */ +unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size); +#endif + #endif /*_TOOLS_LINUX_ASM_GENERIC_BITOPS_FIND_H_ */ diff --git a/tools/include/linux/bitops.h b/tools/include/linux/bitops.h index 49c929a104ee..fc446343ff41 100644 --- a/tools/include/linux/bitops.h +++ b/tools/include/linux/bitops.h @@ -39,6 +39,11 @@ extern unsigned long __sw_hweight64(__u64 w); (bit) < (size); \ (bit) = find_next_bit((addr), (size), (bit) + 1)) +#define for_each_clear_bit(bit, addr, size) \ + for ((bit) = find_first_zero_bit((addr), (size)); \ + (bit) < (size); \ + (bit) = find_next_zero_bit((addr), (size), (bit) + 1)) + /* same as for_each_set_bit() but use bit as value to start with */ #define for_each_set_bit_from(bit, addr, size) \ for ((bit) = find_next_bit((addr), (size), (bit)); \ diff --git a/tools/lib/find_bit.c b/tools/lib/find_bit.c index 9122a9e80046..6d8b8f22cf55 100644 --- a/tools/lib/find_bit.c +++ b/tools/lib/find_bit.c @@ -82,3 +82,28 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size) return size; } #endif + +#ifndef find_first_zero_bit +/* + * Find the first cleared bit in a memory region. + */ +unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) +{ + unsigned long idx; + + for (idx = 0; idx * BITS_PER_LONG < size; idx++) { + if (addr[idx] != ~0UL) + return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); + } + + return size; +} +#endif + +#ifndef find_next_zero_bit +unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, + unsigned long offset) +{ + return _find_next_bit(addr, size, offset, ~0UL); +} +#endif diff --git a/tools/perf/MANIFEST b/tools/perf/MANIFEST index 0bda2cca2b3a..a511e5f31e36 100644 --- a/tools/perf/MANIFEST +++ b/tools/perf/MANIFEST @@ -51,6 +51,7 @@ tools/include/asm-generic/bitops/arch_hweight.h tools/include/asm-generic/bitops/atomic.h tools/include/asm-generic/bitops/const_hweight.h tools/include/asm-generic/bitops/__ffs.h +tools/include/asm-generic/bitops/__ffz.h tools/include/asm-generic/bitops/__fls.h tools/include/asm-generic/bitops/find.h tools/include/asm-generic/bitops/fls64.h -- cgit v1.2.3 From b328daf3b7130098b105c18bdae694ddaad5b6e3 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Wed, 14 Dec 2016 15:08:26 -0800 Subject: tools: add more bitmap functions I need the following functions for the radix tree: bitmap_fill bitmap_empty bitmap_full Copy the implementations from include/linux/bitmap.h Signed-off-by: Matthew Wilcox Tested-by: Kirill A. Shutemov Cc: Konstantin Khlebnikov Cc: Ross Zwisler Cc: Matthew Wilcox Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- tools/include/linux/bitmap.h | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'tools/include/linux') diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h index 43c1c5021e4b..eef41d500e9e 100644 --- a/tools/include/linux/bitmap.h +++ b/tools/include/linux/bitmap.h @@ -35,6 +35,32 @@ static inline void bitmap_zero(unsigned long *dst, int nbits) } } +static inline void bitmap_fill(unsigned long *dst, unsigned int nbits) +{ + unsigned int nlongs = BITS_TO_LONGS(nbits); + if (!small_const_nbits(nbits)) { + unsigned int len = (nlongs - 1) * sizeof(unsigned long); + memset(dst, 0xff, len); + } + dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits); +} + +static inline int bitmap_empty(const unsigned long *src, unsigned nbits) +{ + if (small_const_nbits(nbits)) + return ! (*src & BITMAP_LAST_WORD_MASK(nbits)); + + return find_first_bit(src, nbits) == nbits; +} + +static inline int bitmap_full(const unsigned long *src, unsigned int nbits) +{ + if (small_const_nbits(nbits)) + return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits)); + + return find_first_zero_bit(src, nbits) == nbits; +} + static inline int bitmap_weight(const unsigned long *src, int nbits) { if (small_const_nbits(nbits)) -- cgit v1.2.3 From 376a5fb34b04524af501a0c5979c5920be940e05 Mon Sep 17 00:00:00 2001 From: "Michael S. Tsirkin" Date: Sun, 11 Dec 2016 06:27:21 +0200 Subject: tools: enable endian checks for all sparse builds We dropped need for __CHECK_ENDIAN__ for linux, this mirrors this for tools. Signed-off-by: Michael S. Tsirkin --- tools/include/linux/types.h | 4 ---- 1 file changed, 4 deletions(-) (limited to 'tools/include/linux') diff --git a/tools/include/linux/types.h b/tools/include/linux/types.h index 8ebf6278b2ef..c24b3e3ae296 100644 --- a/tools/include/linux/types.h +++ b/tools/include/linux/types.h @@ -42,11 +42,7 @@ typedef __s8 s8; #else #define __bitwise__ #endif -#ifdef __CHECK_ENDIAN__ #define __bitwise __bitwise__ -#else -#define __bitwise -#endif #define __force #define __user -- cgit v1.2.3