diff options
Diffstat (limited to 'tools/testing')
60 files changed, 3989 insertions, 25 deletions
diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore new file mode 100644 index 000000000000..11d888ca6a92 --- /dev/null +++ b/tools/testing/radix-tree/.gitignore @@ -0,0 +1,2 @@ +main +radix-tree.c diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile new file mode 100644 index 000000000000..604212db9d4b --- /dev/null +++ b/tools/testing/radix-tree/Makefile @@ -0,0 +1,19 @@ + +CFLAGS += -I. -g -Wall -D_LGPL_SOURCE +LDFLAGS += -lpthread -lurcu +TARGETS = main +OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \ + regression1.o regression2.o regression3.o + +targets: $(TARGETS) + +main: $(OFILES) + $(CC) $(CFLAGS) $(LDFLAGS) $(OFILES) -o main + +clean: + $(RM) -f $(TARGETS) *.o radix-tree.c + +$(OFILES): *.h */*.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 new file mode 100644 index 000000000000..d1c2178bb2d4 --- /dev/null +++ b/tools/testing/radix-tree/find_next_bit.c @@ -0,0 +1,57 @@ +/* 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 <linux/types.h> +#include <linux/bitops.h> + +#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.c b/tools/testing/radix-tree/linux.c new file mode 100644 index 000000000000..154823737b20 --- /dev/null +++ b/tools/testing/radix-tree/linux.c @@ -0,0 +1,60 @@ +#include <stdlib.h> +#include <string.h> +#include <malloc.h> +#include <unistd.h> +#include <assert.h> + +#include <linux/mempool.h> +#include <linux/slab.h> +#include <urcu/uatomic.h> + +int nr_allocated; + +void *mempool_alloc(mempool_t *pool, int gfp_mask) +{ + return pool->alloc(gfp_mask, pool->data); +} + +void mempool_free(void *element, mempool_t *pool) +{ + pool->free(element, pool->data); +} + +mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn, + mempool_free_t *free_fn, void *pool_data) +{ + mempool_t *ret = malloc(sizeof(*ret)); + + ret->alloc = alloc_fn; + ret->free = free_fn; + ret->data = pool_data; + return ret; +} + +void *kmem_cache_alloc(struct kmem_cache *cachep, int flags) +{ + void *ret = malloc(cachep->size); + if (cachep->ctor) + cachep->ctor(ret); + uatomic_inc(&nr_allocated); + return ret; +} + +void kmem_cache_free(struct kmem_cache *cachep, void *objp) +{ + assert(objp); + uatomic_dec(&nr_allocated); + memset(objp, 0, cachep->size); + free(objp); +} + +struct kmem_cache * +kmem_cache_create(const char *name, size_t size, size_t offset, + unsigned long flags, void (*ctor)(void *)) +{ + struct kmem_cache *ret = malloc(sizeof(*ret)); + + ret->size = size; + ret->ctor = ctor; + return ret; +} diff --git a/tools/testing/radix-tree/linux/bitops.h b/tools/testing/radix-tree/linux/bitops.h new file mode 100644 index 000000000000..71d58427ab60 --- /dev/null +++ b/tools/testing/radix-tree/linux/bitops.h @@ -0,0 +1,150 @@ +#ifndef _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ +#define _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ + +#include <linux/types.h> + +#define BITOP_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) + +/** + * __set_bit - Set a bit in memory + * @nr: the bit to set + * @addr: the address to start counting from + * + * Unlike set_bit(), this function is non-atomic and may be reordered. + * If it's called on the same region of memory simultaneously, the effect + * may be that only one operation succeeds. + */ +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); + + *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); + + *p &= ~mask; +} + +/** + * __change_bit - Toggle a bit in memory + * @nr: the bit to change + * @addr: the address to start counting from + * + * Unlike change_bit(), this function is non-atomic and may be reordered. + * If it's called on the same region of memory simultaneously, the effect + * may be that only one operation succeeds. + */ +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); + + *p ^= mask; +} + +/** + * __test_and_set_bit - Set a bit and return its old value + * @nr: Bit to set + * @addr: Address to count from + * + * This operation is non-atomic and can be reordered. + * If two examples of this operation race, one can appear to succeed + * but actually fail. You must protect multiple accesses with a lock. + */ +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 old = *p; + + *p = old | mask; + return (old & mask) != 0; +} + +/** + * __test_and_clear_bit - Clear a bit and return its old value + * @nr: Bit to clear + * @addr: Address to count from + * + * This operation is non-atomic and can be reordered. + * If two examples of this operation race, one can appear to succeed + * but actually fail. You must protect multiple accesses with a lock. + */ +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 old = *p; + + *p = old & ~mask; + return (old & mask) != 0; +} + +/* WARNING: non atomic and it can be reordered! */ +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 old = *p; + + *p = old ^ mask; + return (old & mask) != 0; +} + +/** + * test_bit - Determine whether a bit is set + * @nr: bit number to test + * @addr: Address to start counting from + */ +static inline int test_bit(int nr, const volatile unsigned long *addr) +{ + return 1UL & (addr[BITOP_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); +} + +/** + * __ffs - find first bit in word. + * @word: The word to search + * + * Undefined if no bit exists, so code should check against 0 first. + */ +static inline unsigned long __ffs(unsigned long word) +{ + int num = 0; + + if ((word & 0xffffffff) == 0) { + num += 32; + word >>= 32; + } + if ((word & 0xffff) == 0) { + num += 16; + word >>= 16; + } + if ((word & 0xff) == 0) { + num += 8; + word >>= 8; + } + if ((word & 0xf) == 0) { + num += 4; + word >>= 4; + } + if ((word & 0x3) == 0) { + num += 2; + word >>= 2; + } + if ((word & 0x1) == 0) + num += 1; + return num; +} + +unsigned long find_next_bit(const unsigned long *addr, + unsigned long size, + unsigned long offset); + +#endif /* _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/__ffs.h b/tools/testing/radix-tree/linux/bitops/__ffs.h new file mode 100644 index 000000000000..9a3274aecf83 --- /dev/null +++ b/tools/testing/radix-tree/linux/bitops/__ffs.h @@ -0,0 +1,43 @@ +#ifndef _ASM_GENERIC_BITOPS___FFS_H_ +#define _ASM_GENERIC_BITOPS___FFS_H_ + +#include <asm/types.h> + +/** + * __ffs - find first bit in word. + * @word: The word to search + * + * Undefined if no bit exists, so code should check against 0 first. + */ +static inline unsigned long __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 & 0xf) == 0) { + num += 4; + word >>= 4; + } + if ((word & 0x3) == 0) { + num += 2; + word >>= 2; + } + if ((word & 0x1) == 0) + num += 1; + return num; +} + +#endif /* _ASM_GENERIC_BITOPS___FFS_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/ffs.h b/tools/testing/radix-tree/linux/bitops/ffs.h new file mode 100644 index 000000000000..fbbb43af7dc0 --- /dev/null +++ b/tools/testing/radix-tree/linux/bitops/ffs.h @@ -0,0 +1,41 @@ +#ifndef _ASM_GENERIC_BITOPS_FFS_H_ +#define _ASM_GENERIC_BITOPS_FFS_H_ + +/** + * ffs - find first bit set + * @x: the word to search + * + * This is defined the same way as + * the libc and compiler builtin ffs routines, therefore + * differs in spirit from the above ffz (man ffs). + */ +static inline int ffs(int x) +{ + int r = 1; + + if (!x) + return 0; + if (!(x & 0xffff)) { + x >>= 16; + r += 16; + } + if (!(x & 0xff)) { + x >>= 8; + r += 8; + } + if (!(x & 0xf)) { + x >>= 4; + r += 4; + } + if (!(x & 3)) { + x >>= 2; + r += 2; + } + if (!(x & 1)) { + x >>= 1; + r += 1; + } + return r; +} + +#endif /* _ASM_GENERIC_BITOPS_FFS_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/ffz.h b/tools/testing/radix-tree/linux/bitops/ffz.h new file mode 100644 index 000000000000..6744bd4cdf46 --- /dev/null +++ b/tools/testing/radix-tree/linux/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/testing/radix-tree/linux/bitops/find.h b/tools/testing/radix-tree/linux/bitops/find.h new file mode 100644 index 000000000000..72a51e5a12ef --- /dev/null +++ b/tools/testing/radix-tree/linux/bitops/find.h @@ -0,0 +1,13 @@ +#ifndef _ASM_GENERIC_BITOPS_FIND_H_ +#define _ASM_GENERIC_BITOPS_FIND_H_ + +extern unsigned long find_next_bit(const unsigned long *addr, unsigned long + size, unsigned long offset); + +extern unsigned long find_next_zero_bit(const unsigned long *addr, unsigned + long size, unsigned long offset); + +#define find_first_bit(addr, size) find_next_bit((addr), (size), 0) +#define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0) + +#endif /*_ASM_GENERIC_BITOPS_FIND_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/fls.h b/tools/testing/radix-tree/linux/bitops/fls.h new file mode 100644 index 000000000000..850859bc5069 --- /dev/null +++ b/tools/testing/radix-tree/linux/bitops/fls.h @@ -0,0 +1,41 @@ +#ifndef _ASM_GENERIC_BITOPS_FLS_H_ +#define _ASM_GENERIC_BITOPS_FLS_H_ + +/** + * fls - find last (most-significant) bit set + * @x: the word to search + * + * This is defined the same way as ffs. + * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. + */ + +static inline int fls(int x) +{ + int r = 32; + + if (!x) + return 0; + if (!(x & 0xffff0000u)) { + x <<= 16; + r -= 16; + } + if (!(x & 0xff000000u)) { + x <<= 8; + r -= 8; + } + if (!(x & 0xf0000000u)) { + x <<= 4; + r -= 4; + } + if (!(x & 0xc0000000u)) { + x <<= 2; + r -= 2; + } + if (!(x & 0x80000000u)) { + x <<= 1; + r -= 1; + } + return r; +} + +#endif /* _ASM_GENERIC_BITOPS_FLS_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/fls64.h b/tools/testing/radix-tree/linux/bitops/fls64.h new file mode 100644 index 000000000000..1b6b17ce2428 --- /dev/null +++ b/tools/testing/radix-tree/linux/bitops/fls64.h @@ -0,0 +1,14 @@ +#ifndef _ASM_GENERIC_BITOPS_FLS64_H_ +#define _ASM_GENERIC_BITOPS_FLS64_H_ + +#include <asm/types.h> + +static inline int fls64(__u64 x) +{ + __u32 h = x >> 32; + if (h) + return fls(h) + 32; + return fls(x); +} + +#endif /* _ASM_GENERIC_BITOPS_FLS64_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/hweight.h b/tools/testing/radix-tree/linux/bitops/hweight.h new file mode 100644 index 000000000000..fbbc383771da --- /dev/null +++ b/tools/testing/radix-tree/linux/bitops/hweight.h @@ -0,0 +1,11 @@ +#ifndef _ASM_GENERIC_BITOPS_HWEIGHT_H_ +#define _ASM_GENERIC_BITOPS_HWEIGHT_H_ + +#include <asm/types.h> + +extern unsigned int hweight32(unsigned int w); +extern unsigned int hweight16(unsigned int w); +extern unsigned int hweight8(unsigned int w); +extern unsigned long hweight64(__u64 w); + +#endif /* _ASM_GENERIC_BITOPS_HWEIGHT_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/le.h b/tools/testing/radix-tree/linux/bitops/le.h new file mode 100644 index 000000000000..b9c7e5d2d2ad --- /dev/null +++ b/tools/testing/radix-tree/linux/bitops/le.h @@ -0,0 +1,53 @@ +#ifndef _ASM_GENERIC_BITOPS_LE_H_ +#define _ASM_GENERIC_BITOPS_LE_H_ + +#include <asm/types.h> +#include <asm/byteorder.h> + +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) +#define BITOP_LE_SWIZZLE ((BITS_PER_LONG-1) & ~0x7) + +#if defined(__LITTLE_ENDIAN) + +#define generic_test_le_bit(nr, addr) test_bit(nr, addr) +#define generic___set_le_bit(nr, addr) __set_bit(nr, addr) +#define generic___clear_le_bit(nr, addr) __clear_bit(nr, addr) + +#define generic_test_and_set_le_bit(nr, addr) test_and_set_bit(nr, addr) +#define generic_test_and_clear_le_bit(nr, addr) test_and_clear_bit(nr, addr) + +#define generic___test_and_set_le_bit(nr, addr) __test_and_set_bit(nr, addr) +#define generic___test_and_clear_le_bit(nr, addr) __test_and_clear_bit(nr, addr) + +#define generic_find_next_zero_le_bit(addr, size, offset) find_next_zero_bit(addr, size, offset) + +#elif defined(__BIG_ENDIAN) + +#define generic_test_le_bit(nr, addr) \ + test_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) +#define generic___set_le_bit(nr, addr) \ + __set_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) +#define generic___clear_le_bit(nr, addr) \ + __clear_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) + +#define generic_test_and_set_le_bit(nr, addr) \ + test_and_set_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) +#define generic_test_and_clear_le_bit(nr, addr) \ + test_and_clear_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) + +#define generic___test_and_set_le_bit(nr, addr) \ + __test_and_set_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) +#define generic___test_and_clear_le_bit(nr, addr) \ + __test_and_clear_bit((nr) ^ BITOP_LE_SWIZZLE, (addr)) + +extern unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, + unsigned long size, unsigned long offset); + +#else +#error "Please fix <asm/byteorder.h>" +#endif + +#define generic_find_first_zero_le_bit(addr, size) \ + generic_find_next_zero_le_bit((addr), (size), 0) + +#endif /* _ASM_GENERIC_BITOPS_LE_H_ */ diff --git a/tools/testing/radix-tree/linux/bitops/non-atomic.h b/tools/testing/radix-tree/linux/bitops/non-atomic.h new file mode 100644 index 000000000000..46a825cf2ae1 --- /dev/null +++ b/tools/testing/radix-tree/linux/bitops/non-atomic.h @@ -0,0 +1,111 @@ +#ifndef _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ +#define _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ + +#include <asm/types.h> + +#define BITOP_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) + +/** + * __set_bit - Set a bit in memory + * @nr: the bit to set + * @addr: the address to start counting from + * + * Unlike set_bit(), this function is non-atomic and may be reordered. + * If it's called on the same region of memory simultaneously, the effect + * may be that only one operation succeeds. + */ +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); + + *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); + + *p &= ~mask; +} + +/** + * __change_bit - Toggle a bit in memory + * @nr: the bit to change + * @addr: the address to start counting from + * + * Unlike change_bit(), this function is non-atomic and may be reordered. + * If it's called on the same region of memory simultaneously, the effect + * may be that only one operation succeeds. + */ +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); + + *p ^= mask; +} + +/** + * __test_and_set_bit - Set a bit and return its old value + * @nr: Bit to set + * @addr: Address to count from + * + * This operation is non-atomic and can be reordered. + * If two examples of this operation race, one can appear to succeed + * but actually fail. You must protect multiple accesses with a lock. + */ +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 old = *p; + + *p = old | mask; + return (old & mask) != 0; +} + +/** + * __test_and_clear_bit - Clear a bit and return its old value + * @nr: Bit to clear + * @addr: Address to count from + * + * This operation is non-atomic and can be reordered. + * If two examples of this operation race, one can appear to succeed + * but actually fail. You must protect multiple accesses with a lock. + */ +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 old = *p; + + *p = old & ~mask; + return (old & mask) != 0; +} + +/* WARNING: non atomic and it can be reordered! */ +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 old = *p; + + *p = old ^ mask; + return (old & mask) != 0; +} + +/** + * test_bit - Determine whether a bit is set + * @nr: bit number to test + * @addr: Address to start counting from + */ +static inline int test_bit(int nr, const volatile unsigned long *addr) +{ + return 1UL & (addr[BITOP_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); +} + +#endif /* _ASM_GENERIC_BITOPS_NON_ATOMIC_H_ */ diff --git a/tools/testing/radix-tree/linux/bug.h b/tools/testing/radix-tree/linux/bug.h new file mode 100644 index 000000000000..ccbe444977df --- /dev/null +++ b/tools/testing/radix-tree/linux/bug.h @@ -0,0 +1 @@ +#define WARN_ON_ONCE(x) assert(x) diff --git a/tools/testing/radix-tree/linux/cpu.h b/tools/testing/radix-tree/linux/cpu.h new file mode 100644 index 000000000000..60a40459f269 --- /dev/null +++ b/tools/testing/radix-tree/linux/cpu.h @@ -0,0 +1,34 @@ + +#define hotcpu_notifier(a, b) + +#define CPU_ONLINE 0x0002 /* CPU (unsigned)v is up */ +#define CPU_UP_PREPARE 0x0003 /* CPU (unsigned)v coming up */ +#define CPU_UP_CANCELED 0x0004 /* CPU (unsigned)v NOT coming up */ +#define CPU_DOWN_PREPARE 0x0005 /* CPU (unsigned)v going down */ +#define CPU_DOWN_FAILED 0x0006 /* CPU (unsigned)v NOT going down */ +#define CPU_DEAD 0x0007 /* CPU (unsigned)v dead */ +#define CPU_DYING 0x0008 /* CPU (unsigned)v not running any task, + * not handling interrupts, soon dead. + * Called on the dying cpu, interrupts + * are already disabled. Must not + * sleep, must not fail */ +#define CPU_POST_DEAD 0x0009 /* CPU (unsigned)v dead, cpu_hotplug + * lock is dropped */ +#define CPU_STARTING 0x000A /* CPU (unsigned)v soon running. + * Called on the new cpu, just before + * enabling interrupts. Must not sleep, + * must not fail */ +#define CPU_DYING_IDLE 0x000B /* CPU (unsigned)v dying, reached + * idle loop. */ +#define CPU_BROKEN 0x000C /* CPU (unsigned)v did not die properly, + * perhaps due to preemption. */ +#define CPU_TASKS_FROZEN 0x0010 + +#define CPU_ONLINE_FROZEN (CPU_ONLINE | CPU_TASKS_FROZEN) +#define CPU_UP_PREPARE_FROZEN (CPU_UP_PREPARE | CPU_TASKS_FROZEN) +#define CPU_UP_CANCELED_FROZEN (CPU_UP_CANCELED | CPU_TASKS_FROZEN) +#define CPU_DOWN_PREPARE_FROZEN (CPU_DOWN_PREPARE | CPU_TASKS_FROZEN) +#define CPU_DOWN_FAILED_FROZEN (CPU_DOWN_FAILED | CPU_TASKS_FROZEN) +#define CPU_DEAD_FROZEN (CPU_DEAD | CPU_TASKS_FROZEN) +#define CPU_DYING_FROZEN (CPU_DYING | CPU_TASKS_FROZEN) +#define CPU_STARTING_FROZEN (CPU_STARTING | CPU_TASKS_FROZEN) diff --git a/tools/testing/radix-tree/linux/export.h b/tools/testing/radix-tree/linux/export.h new file mode 100644 index 000000000000..b6afd131998d --- /dev/null +++ b/tools/testing/radix-tree/linux/export.h @@ -0,0 +1,2 @@ + +#define EXPORT_SYMBOL(sym) diff --git a/tools/testing/radix-tree/linux/gfp.h b/tools/testing/radix-tree/linux/gfp.h new file mode 100644 index 000000000000..0e37f7a760eb --- /dev/null +++ b/tools/testing/radix-tree/linux/gfp.h @@ -0,0 +1,10 @@ +#ifndef _GFP_H +#define _GFP_H + +#define __GFP_BITS_SHIFT 22 +#define __GFP_BITS_MASK ((gfp_t)((1 << __GFP_BITS_SHIFT) - 1)) +#define __GFP_WAIT 1 +#define __GFP_ACCOUNT 0 +#define __GFP_NOWARN 0 + +#endif diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h new file mode 100644 index 000000000000..ae013b0160ac --- /dev/null +++ b/tools/testing/radix-tree/linux/kernel.h @@ -0,0 +1,35 @@ +#ifndef _KERNEL_H +#define _KERNEL_H + +#include <assert.h> +#include <string.h> +#include <stdio.h> +#include <stddef.h> +#include <limits.h> + +#ifndef NULL +#define NULL 0 +#endif + +#define BUG_ON(expr) assert(!(expr)) +#define __init +#define __must_check +#define panic(expr) +#define printk printf +#define __force +#define likely(c) (c) +#define unlikely(c) (c) +#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) + +#define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0])) + +#define container_of(ptr, type, member) ({ \ + const typeof( ((type *)0)->member ) *__mptr = (ptr); \ + (type *)( (char *)__mptr - offsetof(type, member) );}) +#define min(a, b) ((a) < (b) ? (a) : (b)) + +static inline int in_interrupt(void) +{ + return 0; +} +#endif /* _KERNEL_H */ diff --git a/tools/testing/radix-tree/linux/kmemleak.h b/tools/testing/radix-tree/linux/kmemleak.h new file mode 100644 index 000000000000..155f112786c4 --- /dev/null +++ b/tools/testing/radix-tree/linux/kmemleak.h @@ -0,0 +1 @@ +static inline void kmemleak_update_trace(const void *ptr) { } diff --git a/tools/testing/radix-tree/linux/mempool.h b/tools/testing/radix-tree/linux/mempool.h new file mode 100644 index 000000000000..6a2dc55b41d6 --- /dev/null +++ b/tools/testing/radix-tree/linux/mempool.h @@ -0,0 +1,16 @@ + +#include <linux/slab.h> + +typedef void *(mempool_alloc_t)(int gfp_mask, void *pool_data); +typedef void (mempool_free_t)(void *element, void *pool_data); + +typedef struct { + mempool_alloc_t *alloc; + mempool_free_t *free; + void *data; +} mempool_t; + +void *mempool_alloc(mempool_t *pool, int gfp_mask); +void mempool_free(void *element, mempool_t *pool); +mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn, + mempool_free_t *free_fn, void *pool_data); diff --git a/tools/testing/radix-tree/linux/notifier.h b/tools/testing/radix-tree/linux/notifier.h new file mode 100644 index 000000000000..70e4797d5a46 --- /dev/null +++ b/tools/testing/radix-tree/linux/notifier.h @@ -0,0 +1,8 @@ +#ifndef _NOTIFIER_H +#define _NOTIFIER_H + +struct notifier_block; + +#define NOTIFY_OK 0x0001 /* Suits me */ + +#endif diff --git a/tools/testing/radix-tree/linux/percpu.h b/tools/testing/radix-tree/linux/percpu.h new file mode 100644 index 000000000000..5837f1d56f17 --- /dev/null +++ b/tools/testing/radix-tree/linux/percpu.h @@ -0,0 +1,7 @@ + +#define DEFINE_PER_CPU(type, val) type val + +#define __get_cpu_var(var) var +#define this_cpu_ptr(var) var +#define per_cpu_ptr(ptr, cpu) ({ (void)(cpu); (ptr); }) +#define per_cpu(var, cpu) (*per_cpu_ptr(&(var), cpu)) diff --git a/tools/testing/radix-tree/linux/preempt.h b/tools/testing/radix-tree/linux/preempt.h new file mode 100644 index 000000000000..6210672e3baa --- /dev/null +++ b/tools/testing/radix-tree/linux/preempt.h @@ -0,0 +1,4 @@ +/* */ + +#define preempt_disable() do { } while (0) +#define preempt_enable() do { } while (0) diff --git a/tools/testing/radix-tree/linux/radix-tree.h b/tools/testing/radix-tree/linux/radix-tree.h new file mode 100644 index 000000000000..ce694ddd4aea --- /dev/null +++ b/tools/testing/radix-tree/linux/radix-tree.h @@ -0,0 +1 @@ +#include "../../../../include/linux/radix-tree.h" diff --git a/tools/testing/radix-tree/linux/rcupdate.h b/tools/testing/radix-tree/linux/rcupdate.h new file mode 100644 index 000000000000..f7129ea2a899 --- /dev/null +++ b/tools/testing/radix-tree/linux/rcupdate.h @@ -0,0 +1,9 @@ +#ifndef _RCUPDATE_H +#define _RCUPDATE_H + +#include <urcu.h> + +#define rcu_dereference_raw(p) rcu_dereference(p) +#define rcu_dereference_protected(p, cond) rcu_dereference(p) + +#endif diff --git a/tools/testing/radix-tree/linux/slab.h b/tools/testing/radix-tree/linux/slab.h new file mode 100644 index 000000000000..57282506c21d --- /dev/null +++ b/tools/testing/radix-tree/linux/slab.h @@ -0,0 +1,28 @@ +#ifndef SLAB_H +#define SLAB_H + +#include <linux/types.h> + +#define GFP_KERNEL 1 +#define SLAB_HWCACHE_ALIGN 1 +#define SLAB_PANIC 2 +#define SLAB_RECLAIM_ACCOUNT 0x00020000UL /* Objects are reclaimable */ + +static inline int gfpflags_allow_blocking(gfp_t mask) +{ + return 1; +} + +struct kmem_cache { + int size; + void (*ctor)(void *); +}; + +void *kmem_cache_alloc(struct kmem_cache *cachep, int flags); +void kmem_cache_free(struct kmem_cache *cachep, void *objp); + +struct kmem_cache * +kmem_cache_create(const char *name, size_t size, size_t offset, + unsigned long flags, void (*ctor)(void *)); + +#endif /* SLAB_H */ diff --git a/tools/testing/radix-tree/linux/types.h b/tools/testing/radix-tree/linux/types.h new file mode 100644 index 000000000000..72a9d85f6c76 --- /dev/null +++ b/tools/testing/radix-tree/linux/types.h @@ -0,0 +1,28 @@ +#ifndef _TYPES_H +#define _TYPES_H + +#define __rcu +#define __read_mostly + +#define BITS_PER_LONG (sizeof(long) * 8) + +struct list_head { + struct list_head *next, *prev; +}; + +static inline void INIT_LIST_HEAD(struct list_head *list) +{ + list->next = list; + list->prev = list; +} + +typedef struct { + unsigned int x; +} spinlock_t; + +#define uninitialized_var(x) x = x + +typedef unsigned gfp_t; +#include <linux/gfp.h> + +#endif diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c new file mode 100644 index 000000000000..0e83cad27a9f --- /dev/null +++ b/tools/testing/radix-tree/main.c @@ -0,0 +1,272 @@ +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <time.h> +#include <assert.h> + +#include <linux/slab.h> +#include <linux/radix-tree.h> + +#include "test.h" +#include "regression.h" + +void __gang_check(unsigned long middle, long down, long up, int chunk, int hop) +{ + long idx; + RADIX_TREE(tree, GFP_KERNEL); + + middle = 1 << 30; + + for (idx = -down; idx < up; idx++) + item_insert(&tree, middle + idx); + + item_check_absent(&tree, middle - down - 1); + for (idx = -down; idx < up; idx++) + item_check_present(&tree, middle + idx); + item_check_absent(&tree, middle + up); + + item_gang_check_present(&tree, middle - down, + up + down, chunk, hop); + item_full_scan(&tree, middle - down, down + up, chunk); + item_kill_tree(&tree); +} + +void gang_check(void) +{ + __gang_check(1 << 30, 128, 128, 35, 2); + __gang_check(1 << 31, 128, 128, 32, 32); + __gang_check(1 << 31, 128, 128, 32, 100); + __gang_check(1 << 31, 128, 128, 17, 7); + __gang_check(0xffff0000, 0, 65536, 17, 7); + __gang_check(0xfffffffe, 1, 1, 17, 7); +} + +void __big_gang_check(void) +{ + unsigned long start; + int wrapped = 0; + + start = 0; + do { + unsigned long old_start; + +// printf("0x%08lx\n", start); + __gang_check(start, rand() % 113 + 1, rand() % 71, + rand() % 157, rand() % 91 + 1); + old_start = start; + start += rand() % 1000000; + start %= 1ULL << 33; + if (start < old_start) + wrapped = 1; + } while (!wrapped); +} + +void big_gang_check(void) +{ + int i; + + for (i = 0; i < 1000; i++) { + __big_gang_check(); + srand(time(0)); + printf("%d ", i); + fflush(stdout); + } +} + +void add_and_check(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + + item_insert(&tree, 44); + item_check_present(&tree, 44); + item_check_absent(&tree, 43); + item_kill_tree(&tree); +} + +void dynamic_height_check(void) +{ + int i; + RADIX_TREE(tree, GFP_KERNEL); + tree_verify_min_height(&tree, 0); + + item_insert(&tree, 42); + tree_verify_min_height(&tree, 42); + + item_insert(&tree, 1000000); + tree_verify_min_height(&tree, 1000000); + + assert(item_delete(&tree, 1000000)); + tree_verify_min_height(&tree, 42); + + assert(item_delete(&tree, 42)); + tree_verify_min_height(&tree, 0); + + for (i = 0; i < 1000; i++) { + item_insert(&tree, i); + tree_verify_min_height(&tree, i); + } + + i--; + for (;;) { + assert(item_delete(&tree, i)); + if (i == 0) { + tree_verify_min_height(&tree, 0); + break; + } + i--; + tree_verify_min_height(&tree, i); + } + + item_kill_tree(&tree); +} + +void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag) +{ + int i; + + for (i = 0; i < count; i++) { +/* if (i % 1000 == 0) + putchar('.'); */ + if (idx[i] < start || idx[i] > end) { + if (item_tag_get(tree, idx[i], totag)) { + printf("%lu-%lu: %lu, tags %d-%d\n", start, end, idx[i], item_tag_get(tree, idx[i], fromtag), item_tag_get(tree, idx[i], totag)); + } + assert(!item_tag_get(tree, idx[i], totag)); + continue; + } + if (item_tag_get(tree, idx[i], fromtag) ^ + item_tag_get(tree, idx[i], totag)) { + printf("%lu-%lu: %lu, tags %d-%d\n", start, end, idx[i], item_tag_get(tree, idx[i], fromtag), item_tag_get(tree, idx[i], totag)); + } + assert(!(item_tag_get(tree, idx[i], fromtag) ^ + item_tag_get(tree, idx[i], totag))); + } +} + +#define ITEMS 50000 + +void copy_tag_check(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + unsigned long idx[ITEMS]; + unsigned long start, end, count = 0, tagged, cur, tmp; + int i; + +// printf("generating radix tree indices...\n"); + start = rand(); + end = rand(); + if (start > end && (rand() % 10)) { + cur = start; + start = end; + end = cur; + } + /* Specifically create items around the start and the end of the range + * with high probability to check for off by one errors */ + cur = rand(); + if (cur & 1) { + item_insert(&tree, start); + if (cur & 2) { + if (start <= end) + count++; + item_tag_set(&tree, start, 0); + } + } + if (cur & 4) { + item_insert(&tree, start-1); + if (cur & 8) + item_tag_set(&tree, start-1, 0); + } + if (cur & 16) { + item_insert(&tree, end); + if (cur & 32) { + if (start <= end) + count++; + item_tag_set(&tree, end, 0); + } + } + if (cur & 64) { + item_insert(&tree, end+1); + if (cur & 128) + item_tag_set(&tree, end+1, 0); + } + + for (i = 0; i < ITEMS; i++) { + do { + idx[i] = rand(); + } while (item_lookup(&tree, idx[i])); + + item_insert(&tree, idx[i]); + if (rand() & 1) { + item_tag_set(&tree, idx[i], 0); + if (idx[i] >= start && idx[i] <= end) + count++; + } +/* if (i % 1000 == 0) + putchar('.'); */ + } + +// printf("\ncopying tags...\n"); + cur = start; + tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1); + +// printf("checking copied tags\n"); + assert(tagged == count); + check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1); + + /* Copy tags in several rounds */ +// printf("\ncopying tags...\n"); + cur = start; + do { + tmp = rand() % (count/10+2); + tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0, 2); + } while (tmp == tagged); + +// printf("%lu %lu %lu\n", tagged, tmp, count); +// printf("checking copied tags\n"); + check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2); + assert(tagged < tmp); + verify_tag_consistency(&tree, 0); + verify_tag_consistency(&tree, 1); + verify_tag_consistency(&tree, 2); +// printf("\n"); + item_kill_tree(&tree); +} + +static void single_thread_tests(void) +{ + int i; + + tag_check(); + printf("after tag_check: %d allocated\n", nr_allocated); + gang_check(); + printf("after gang_check: %d allocated\n", nr_allocated); + add_and_check(); + printf("after add_and_check: %d allocated\n", nr_allocated); + dynamic_height_check(); + printf("after dynamic_height_check: %d allocated\n", nr_allocated); + big_gang_check(); + printf("after big_gang_check: %d allocated\n", nr_allocated); + for (i = 0; i < 2000; i++) { + copy_tag_check(); + printf("%d ", i); + fflush(stdout); + } + printf("after copy_tag_check: %d allocated\n", nr_allocated); +} + +int main(void) +{ + rcu_register_thread(); + radix_tree_init(); + + regression1_test(); + regression2_test(); + regression3_test(); + single_thread_tests(); + + sleep(1); + printf("after sleep(1): %d allocated\n", nr_allocated); + rcu_unregister_thread(); + + exit(0); +} diff --git a/tools/testing/radix-tree/rcupdate.c b/tools/testing/radix-tree/rcupdate.c new file mode 100644 index 000000000000..31a2d14225d6 --- /dev/null +++ b/tools/testing/radix-tree/rcupdate.c @@ -0,0 +1,86 @@ +#include <linux/rcupdate.h> +#include <pthread.h> +#include <stdio.h> +#include <assert.h> + +static pthread_mutex_t rculock = PTHREAD_MUTEX_INITIALIZER; +static struct rcu_head *rcuhead_global = NULL; +static __thread int nr_rcuhead = 0; +static __thread struct rcu_head *rcuhead = NULL; +static __thread struct rcu_head *rcutail = NULL; + +static pthread_cond_t rcu_worker_cond = PTHREAD_COND_INITIALIZER; + +/* switch to urcu implementation when it is merged. */ +void call_rcu(struct rcu_head *head, void (*func)(struct rcu_head *head)) +{ + head->func = func; + head->next = rcuhead; + rcuhead = head; + if (!rcutail) + rcutail = head; + nr_rcuhead++; + if (nr_rcuhead >= 1000) { + int signal = 0; + + pthread_mutex_lock(&rculock); + if (!rcuhead_global) + signal = 1; + rcutail->next = rcuhead_global; + rcuhead_global = head; + pthread_mutex_unlock(&rculock); + + nr_rcuhead = 0; + rcuhead = NULL; + rcutail = NULL; + + if (signal) { + pthread_cond_signal(&rcu_worker_cond); + } + } +} + +static void *rcu_worker(void *arg) +{ + struct rcu_head *r; + + rcupdate_thread_init(); + + while (1) { + pthread_mutex_lock(&rculock); + while (!rcuhead_global) { + pthread_cond_wait(&rcu_worker_cond, &rculock); + } + r = rcuhead_global; + rcuhead_global = NULL; + + pthread_mutex_unlock(&rculock); + + synchronize_rcu(); + + while (r) { + struct rcu_head *tmp = r->next; + r->func(r); + r = tmp; + } + } + + rcupdate_thread_exit(); + + return NULL; +} + +static pthread_t worker_thread; +void rcupdate_init(void) +{ + pthread_create(&worker_thread, NULL, rcu_worker, NULL); +} + +void rcupdate_thread_init(void) +{ + rcu_register_thread(); +} +void rcupdate_thread_exit(void) +{ + rcu_unregister_thread(); +} diff --git a/tools/testing/radix-tree/regression.h b/tools/testing/radix-tree/regression.h new file mode 100644 index 000000000000..e018c4816688 --- /dev/null +++ b/tools/testing/radix-tree/regression.h @@ -0,0 +1,8 @@ +#ifndef __REGRESSION_H__ +#define __REGRESSION_H__ + +void regression1_test(void); +void regression2_test(void); +void regression3_test(void); + +#endif diff --git a/tools/testing/radix-tree/regression1.c b/tools/testing/radix-tree/regression1.c new file mode 100644 index 000000000000..2d03a63bb79c --- /dev/null +++ b/tools/testing/radix-tree/regression1.c @@ -0,0 +1,220 @@ +/* + * Regression1 + * Description: + * Salman Qazi describes the following radix-tree bug: + * + * In the following case, we get can get a deadlock: + * + * 0. The radix tree contains two items, one has the index 0. + * 1. The reader (in this case find_get_pages) takes the rcu_read_lock. + * 2. The reader acquires slot(s) for item(s) including the index 0 item. + * 3. The non-zero index item is deleted, and as a consequence the other item + * is moved to the root of the tree. The place where it used to be is queued + * for deletion after the readers finish. + * 3b. The zero item is deleted, removing it from the direct slot, it remains in + * the rcu-delayed indirect node. + * 4. The reader looks at the index 0 slot, and finds that the page has 0 ref + * count + * 5. The reader looks at it again, hoping that the item will either be freed + * or the ref count will increase. This never happens, as the slot it is + * looking at will never be updated. Also, this slot can never be reclaimed + * because the reader is holding rcu_read_lock and is in an infinite loop. + * + * The fix is to re-use the same "indirect" pointer case that requires a slot + * lookup retry into a general "retry the lookup" bit. + * + * Running: + * This test should run to completion in a few seconds. The above bug would + * cause it to hang indefinitely. + * + * Upstream commit: + * Not yet + */ +#include <linux/kernel.h> +#include <linux/gfp.h> +#include <linux/slab.h> +#include <linux/radix-tree.h> +#include <linux/rcupdate.h> +#include <stdlib.h> +#include <pthread.h> +#include <stdio.h> +#include <assert.h> + +#include "regression.h" + +static RADIX_TREE(mt_tree, GFP_KERNEL); +static pthread_mutex_t mt_lock; + +struct page { + pthread_mutex_t lock; + struct rcu_head rcu; + int count; + unsigned long index; +}; + +static struct page *page_alloc(void) +{ + struct page *p; + p = malloc(sizeof(struct page)); + p->count = 1; + p->index = 1; + pthread_mutex_init(&p->lock, NULL); + + return p; +} + +static void page_rcu_free(struct rcu_head *rcu) +{ + struct page *p = container_of(rcu, struct page, rcu); + assert(!p->count); + pthread_mutex_destroy(&p->lock); + free(p); +} + +static void page_free(struct page *p) +{ + call_rcu(&p->rcu, page_rcu_free); +} + +static unsigned find_get_pages(unsigned long start, + unsigned int nr_pages, struct page **pages) +{ + unsigned int i; + unsigned int ret; + unsigned int nr_found; + + rcu_read_lock(); +restart: + nr_found = radix_tree_gang_lookup_slot(&mt_tree, + (void ***)pages, NULL, start, nr_pages); + ret = 0; + for (i = 0; i < nr_found; i++) { + struct page *page; +repeat: + page = radix_tree_deref_slot((void **)pages[i]); + if (unlikely(!page)) + continue; + + if (radix_tree_exception(page)) { + if (radix_tree_deref_retry(page)) { + /* + * Transient condition which can only trigger + * when entry at index 0 moves out of or back + * to root: none yet gotten, safe to restart. + */ + assert((start | i) == 0); + goto restart; + } + /* + * No exceptional entries are inserted in this test. + */ + assert(0); + } + + pthread_mutex_lock(&page->lock); + if (!page->count) { + pthread_mutex_unlock(&page->lock); + goto repeat; + } + /* don't actually update page refcount */ + pthread_mutex_unlock(&page->lock); + + /* Has the page moved? */ + if (unlikely(page != *((void **)pages[i]))) { + goto repeat; + } + + pages[ret] = page; + ret++; + } + rcu_read_unlock(); + return ret; +} + +static pthread_barrier_t worker_barrier; + +static void *regression1_fn(void *arg) +{ + rcu_register_thread(); + + if (pthread_barrier_wait(&worker_barrier) == + PTHREAD_BARRIER_SERIAL_THREAD) { + int j; + + for (j = 0; j < 1000000; j++) { + struct page *p; + + p = page_alloc(); + pthread_mutex_lock(&mt_lock); + radix_tree_insert(&mt_tree, 0, p); + pthread_mutex_unlock(&mt_lock); + + p = page_alloc(); + pthread_mutex_lock(&mt_lock); + radix_tree_insert(&mt_tree, 1, p); + pthread_mutex_unlock(&mt_lock); + + pthread_mutex_lock(&mt_lock); + p = radix_tree_delete(&mt_tree, 1); + pthread_mutex_lock(&p->lock); + p->count--; + pthread_mutex_unlock(&p->lock); + pthread_mutex_unlock(&mt_lock); + page_free(p); + + pthread_mutex_lock(&mt_lock); + p = radix_tree_delete(&mt_tree, 0); + pthread_mutex_lock(&p->lock); + p->count--; + pthread_mutex_unlock(&p->lock); + pthread_mutex_unlock(&mt_lock); + page_free(p); + } + } else { + int j; + + for (j = 0; j < 100000000; j++) { + struct page *pages[10]; + + find_get_pages(0, 10, pages); + } + } + + rcu_unregister_thread(); + + return NULL; +} + +static pthread_t *threads; +void regression1_test(void) +{ + int nr_threads; + int i; + long arg; + + /* Regression #1 */ + printf("running regression test 1, should finish in under a minute\n"); + nr_threads = 2; + pthread_barrier_init(&worker_barrier, NULL, nr_threads); + + threads = malloc(nr_threads * sizeof(pthread_t *)); + + for (i = 0; i < nr_threads; i++) { + arg = i; + if (pthread_create(&threads[i], NULL, regression1_fn, (void *)arg)) { + perror("pthread_create"); + exit(1); + } + } + + for (i = 0; i < nr_threads; i++) { + if (pthread_join(threads[i], NULL)) { + perror("pthread_join"); + exit(1); + } + } + + free(threads); + + printf("regression test 1, done\n"); +} diff --git a/tools/testing/radix-tree/regression2.c b/tools/testing/radix-tree/regression2.c new file mode 100644 index 000000000000..5d2fa28cdca3 --- /dev/null +++ b/tools/testing/radix-tree/regression2.c @@ -0,0 +1,126 @@ +/* + * Regression2 + * Description: + * Toshiyuki Okajima describes the following radix-tree bug: + * + * In the following case, we can get a hangup on + * radix_radix_tree_gang_lookup_tag_slot. + * + * 0. The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of + * a certain item has PAGECACHE_TAG_DIRTY. + * 1. radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY, + * PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag + * for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with + * PAGECACHE_TAG_DIRTY within the range from start to end. As the result, + * There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has + * PAGECACHE_TAG_TOWRITE. + * 2. An item is added into the radix tree and then the level of it is + * extended into 2 from 1. At that time, the new radix tree node succeeds + * the tag status of the root tag. Therefore the tag of the new radix tree + * node has PAGECACHE_TAG_TOWRITE but there is not slot with + * PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node. + * 3. The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY. + * 4. All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are + * released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the + * radix tree.) As the result, the slot of the radix tree node is NULL but + * the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE. + * 5. radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls + * __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't + * change the index that is the input and output parameter. Because the 1st + * slot of the radix tree node is NULL, but the tag which corresponds to + * the slot has PAGECACHE_TAG_TOWRITE. + * Therefore radix_tree_gang_lookup_tag_slot tries to get some items by + * calling __lookup_tag, but it cannot get any items forever. + * + * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag + * if it doesn't set any tags within the specified range. + * + * Running: + * This test should run to completion immediately. The above bug would cause it + * to hang indefinitely. + * + * Upstream commit: + * Not yet + */ +#include <linux/kernel.h> +#include <linux/gfp.h> +#include <linux/slab.h> +#include <linux/radix-tree.h> +#include <stdlib.h> +#include <stdio.h> + +#include "regression.h" + +#ifdef __KERNEL__ +#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) +#else +#define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ +#endif + +#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT) +#define PAGECACHE_TAG_DIRTY 0 +#define PAGECACHE_TAG_WRITEBACK 1 +#define PAGECACHE_TAG_TOWRITE 2 + +static RADIX_TREE(mt_tree, GFP_KERNEL); +unsigned long page_count = 0; + +struct page { + unsigned long index; +}; + +static struct page *page_alloc(void) +{ + struct page *p; + p = malloc(sizeof(struct page)); + p->index = page_count++; + + return p; +} + +void regression2_test(void) +{ + int i; + struct page *p; + int max_slots = RADIX_TREE_MAP_SIZE; + unsigned long int start, end; + struct page *pages[1]; + + printf("running regression test 2 (should take milliseconds)\n"); + /* 0. */ + for (i = 0; i <= max_slots - 1; i++) { + p = page_alloc(); + radix_tree_insert(&mt_tree, i, p); + } + radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); + + /* 1. */ + start = 0; + end = max_slots - 2; + radix_tree_range_tag_if_tagged(&mt_tree, &start, end, 1, + PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE); + + /* 2. */ + p = page_alloc(); + radix_tree_insert(&mt_tree, max_slots, p); + + /* 3. */ + radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); + + /* 4. */ + for (i = max_slots - 1; i >= 0; i--) + radix_tree_delete(&mt_tree, i); + + /* 5. */ + // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot + // can return. + start = 1; + end = max_slots - 2; + radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end, + PAGECACHE_TAG_TOWRITE); + + /* We remove all the remained nodes */ + radix_tree_delete(&mt_tree, max_slots); + + printf("regression test 2, done\n"); +} diff --git a/tools/testing/radix-tree/regression3.c b/tools/testing/radix-tree/regression3.c new file mode 100644 index 000000000000..1f06ed73d0a8 --- /dev/null +++ b/tools/testing/radix-tree/regression3.c @@ -0,0 +1,117 @@ +/* + * Regression3 + * Description: + * Helper radix_tree_iter_retry resets next_index to the current index. + * In following radix_tree_next_slot current chunk size becomes zero. + * This isn't checked and it tries to dereference null pointer in slot. + * + * Helper radix_tree_iter_next reset slot to NULL and next_index to index + 1, + * for tagger iteraction it also must reset cached tags in iterator to abort + * next radix_tree_next_slot and go to slow-path into radix_tree_next_chunk. + * + * Running: + * This test should run to completion immediately. The above bug would + * cause it to segfault. + * + * Upstream commit: + * Not yet + */ +#include <linux/kernel.h> +#include <linux/gfp.h> +#include <linux/slab.h> +#include <linux/radix-tree.h> +#include <stdlib.h> +#include <stdio.h> + +#include "regression.h" + +void regression3_test(void) +{ + RADIX_TREE(root, GFP_KERNEL); + void *ptr0 = (void *)4ul; + void *ptr = (void *)8ul; + struct radix_tree_iter iter; + void **slot; + bool first; + + printf("running regression test 3 (should take milliseconds)\n"); + + radix_tree_insert(&root, 0, ptr0); + radix_tree_tag_set(&root, 0, 0); + + first = true; + radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) { + printf("tagged %ld %p\n", iter.index, *slot); + if (first) { + radix_tree_insert(&root, 1, ptr); + radix_tree_tag_set(&root, 1, 0); + first = false; + } + if (radix_tree_deref_retry(*slot)) { + printf("retry at %ld\n", iter.index); + slot = radix_tree_iter_retry(&iter); + continue; + } + } + radix_tree_delete(&root, 1); + + first = true; + radix_tree_for_each_slot(slot, &root, &iter, 0) { + printf("slot %ld %p\n", iter.index, *slot); + if (first) { + radix_tree_insert(&root, 1, ptr); + first = false; + } + if (radix_tree_deref_retry(*slot)) { + printk("retry at %ld\n", iter.index); + slot = radix_tree_iter_retry(&iter); + continue; + } + } + radix_tree_delete(&root, 1); + + first = true; + radix_tree_for_each_contig(slot, &root, &iter, 0) { + printk("contig %ld %p\n", iter.index, *slot); + if (first) { + radix_tree_insert(&root, 1, ptr); + first = false; + } + if (radix_tree_deref_retry(*slot)) { + printk("retry at %ld\n", iter.index); + slot = radix_tree_iter_retry(&iter); + continue; + } + } + + radix_tree_for_each_slot(slot, &root, &iter, 0) { + printf("slot %ld %p\n", iter.index, *slot); + if (!iter.index) { + printf("next at %ld\n", iter.index); + slot = radix_tree_iter_next(&iter); + } + } + + radix_tree_for_each_contig(slot, &root, &iter, 0) { + printf("contig %ld %p\n", iter.index, *slot); + if (!iter.index) { + printf("next at %ld\n", iter.index); + slot = radix_tree_iter_next(&iter); + } + } + + radix_tree_tag_set(&root, 0, 0); + radix_tree_tag_set(&root, 1, 0); + radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) { + printf("tagged %ld %p\n", iter.index, *slot); + if (!iter.index) { + printf("next at %ld\n", iter.index); + slot = radix_tree_iter_next(&iter); + } + } + + radix_tree_delete(&root, 0); + radix_tree_delete(&root, 1); + + printf("regression test 3 passed\n"); +} diff --git a/tools/testing/radix-tree/tag_check.c b/tools/testing/radix-tree/tag_check.c new file mode 100644 index 000000000000..83136be552a0 --- /dev/null +++ b/tools/testing/radix-tree/tag_check.c @@ -0,0 +1,332 @@ +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <string.h> + +#include <linux/slab.h> +#include <linux/radix-tree.h> + +#include "test.h" + + +static void +__simple_checks(struct radix_tree_root *tree, unsigned long index, int tag) +{ + int ret; + + item_check_absent(tree, index); + assert(item_tag_get(tree, index, tag) == 0); + + item_insert(tree, index); + assert(item_tag_get(tree, index, tag) == 0); + item_tag_set(tree, index, tag); + ret = item_tag_get(tree, index, tag); + assert(ret != 0); + ret = item_delete(tree, index); + assert(ret != 0); + item_insert(tree, index); + ret = item_tag_get(tree, index, tag); + assert(ret == 0); + ret = item_delete(tree, index); + assert(ret != 0); + ret = item_delete(tree, index); + assert(ret == 0); +} + +void simple_checks(void) +{ + unsigned long index; + RADIX_TREE(tree, GFP_KERNEL); + + for (index = 0; index < 10000; index++) { + __simple_checks(&tree, index, 0); + __simple_checks(&tree, index, 1); + } + verify_tag_consistency(&tree, 0); + verify_tag_consistency(&tree, 1); + printf("before item_kill_tree: %d allocated\n", nr_allocated); + item_kill_tree(&tree); + printf("after item_kill_tree: %d allocated\n", nr_allocated); +} + +/* + * Check that tags propagate correctly when extending a tree. + */ +static void extend_checks(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + + item_insert(&tree, 43); + assert(item_tag_get(&tree, 43, 0) == 0); + item_tag_set(&tree, 43, 0); + assert(item_tag_get(&tree, 43, 0) == 1); + item_insert(&tree, 1000000); + assert(item_tag_get(&tree, 43, 0) == 1); + + item_insert(&tree, 0); + item_tag_set(&tree, 0, 0); + item_delete(&tree, 1000000); + assert(item_tag_get(&tree, 43, 0) != 0); + item_delete(&tree, 43); + assert(item_tag_get(&tree, 43, 0) == 0); /* crash */ + assert(item_tag_get(&tree, 0, 0) == 1); + + verify_tag_consistency(&tree, 0); + + item_kill_tree(&tree); +} + +/* + * Check that tags propagate correctly when contracting a tree. + */ +static void contract_checks(void) +{ + struct item *item; + int tmp; + RADIX_TREE(tree, GFP_KERNEL); + + tmp = 1<<RADIX_TREE_MAP_SHIFT; + item_insert(&tree, tmp); + item_insert(&tree, tmp+1); + item_tag_set(&tree, tmp, 0); + item_tag_set(&tree, tmp, 1); + item_tag_set(&tree, tmp+1, 0); + item_delete(&tree, tmp+1); + item_tag_clear(&tree, tmp, 1); + + assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 0) == 1); + assert(radix_tree_gang_lookup_tag(&tree, (void **)&item, 0, 1, 1) == 0); + + assert(item_tag_get(&tree, tmp, 0) == 1); + assert(item_tag_get(&tree, tmp, 1) == 0); + + verify_tag_consistency(&tree, 0); + item_kill_tree(&tree); +} + +/* + * Stupid tag thrasher + * + * Create a large linear array corresponding to the tree. Each element in + * the array is coherent with each node in the tree + */ + +enum { + NODE_ABSENT = 0, + NODE_PRESENT = 1, + NODE_TAGGED = 2, +}; + +#define THRASH_SIZE 1000 * 1000 +#define N 127 +#define BATCH 33 + +static void gang_check(struct radix_tree_root *tree, + char *thrash_state, int tag) +{ + struct item *items[BATCH]; + int nr_found; + unsigned long index = 0; + unsigned long last_index = 0; + + while ((nr_found = radix_tree_gang_lookup_tag(tree, (void **)items, + index, BATCH, tag))) { + int i; + + for (i = 0; i < nr_found; i++) { + struct item *item = items[i]; + + while (last_index < item->index) { + assert(thrash_state[last_index] != NODE_TAGGED); + last_index++; + } + assert(thrash_state[last_index] == NODE_TAGGED); + last_index++; + } + index = items[nr_found - 1]->index + 1; + } +} + +static void do_thrash(struct radix_tree_root *tree, char *thrash_state, int tag) +{ + int insert_chunk; + int delete_chunk; + int tag_chunk; + int untag_chunk; + int total_tagged = 0; + int total_present = 0; + + for (insert_chunk = 1; insert_chunk < THRASH_SIZE; insert_chunk *= N) + for (delete_chunk = 1; delete_chunk < THRASH_SIZE; delete_chunk *= N) + for (tag_chunk = 1; tag_chunk < THRASH_SIZE; tag_chunk *= N) + for (untag_chunk = 1; untag_chunk < THRASH_SIZE; untag_chunk *= N) { + int i; + unsigned long index; + int nr_inserted = 0; + int nr_deleted = 0; + int nr_tagged = 0; + int nr_untagged = 0; + int actual_total_tagged; + int actual_total_present; + + for (i = 0; i < insert_chunk; i++) { + index = rand() % THRASH_SIZE; + if (thrash_state[index] != NODE_ABSENT) + continue; + item_check_absent(tree, index); + item_insert(tree, index); + assert(thrash_state[index] != NODE_PRESENT); + thrash_state[index] = NODE_PRESENT; + nr_inserted++; + total_present++; + } + + for (i = 0; i < delete_chunk; i++) { + index = rand() % THRASH_SIZE; + if (thrash_state[index] == NODE_ABSENT) + continue; + item_check_present(tree, index); + if (item_tag_get(tree, index, tag)) { + assert(thrash_state[index] == NODE_TAGGED); + total_tagged--; + } else { + assert(thrash_state[index] == NODE_PRESENT); + } + item_delete(tree, index); + assert(thrash_state[index] != NODE_ABSENT); + thrash_state[index] = NODE_ABSENT; + nr_deleted++; + total_present--; + } + + for (i = 0; i < tag_chunk; i++) { + index = rand() % THRASH_SIZE; + if (thrash_state[index] != NODE_PRESENT) { + if (item_lookup(tree, index)) + assert(item_tag_get(tree, index, tag)); + continue; + } + item_tag_set(tree, index, tag); + item_tag_set(tree, index, tag); + assert(thrash_state[index] != NODE_TAGGED); + thrash_state[index] = NODE_TAGGED; + nr_tagged++; + total_tagged++; + } + + for (i = 0; i < untag_chunk; i++) { + index = rand() % THRASH_SIZE; + if (thrash_state[index] != NODE_TAGGED) + continue; + item_check_present(tree, index); + assert(item_tag_get(tree, index, tag)); + item_tag_clear(tree, index, tag); + item_tag_clear(tree, index, tag); + assert(thrash_state[index] != NODE_PRESENT); + thrash_state[index] = NODE_PRESENT; + nr_untagged++; + total_tagged--; + } + + actual_total_tagged = 0; + actual_total_present = 0; + for (index = 0; index < THRASH_SIZE; index++) { + switch (thrash_state[index]) { + case NODE_ABSENT: + item_check_absent(tree, index); + break; + case NODE_PRESENT: + item_check_present(tree, index); + assert(!item_tag_get(tree, index, tag)); + actual_total_present++; + break; + case NODE_TAGGED: + item_check_present(tree, index); + assert(item_tag_get(tree, index, tag)); + actual_total_present++; + actual_total_tagged++; + break; + } + } + + gang_check(tree, thrash_state, tag); + + printf("%d(%d) %d(%d) %d(%d) %d(%d) / " + "%d(%d) present, %d(%d) tagged\n", + insert_chunk, nr_inserted, + delete_chunk, nr_deleted, + tag_chunk, nr_tagged, + untag_chunk, nr_untagged, + total_present, actual_total_present, + total_tagged, actual_total_tagged); + } +} + +static void thrash_tags(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + char *thrash_state; + + thrash_state = malloc(THRASH_SIZE); + memset(thrash_state, 0, THRASH_SIZE); + + do_thrash(&tree, thrash_state, 0); + + verify_tag_consistency(&tree, 0); + item_kill_tree(&tree); + free(thrash_state); +} + +static void leak_check(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + + item_insert(&tree, 1000000); + item_delete(&tree, 1000000); + item_kill_tree(&tree); +} + +static void __leak_check(void) +{ + RADIX_TREE(tree, GFP_KERNEL); + + printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); + item_insert(&tree, 1000000); + printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); + item_delete(&tree, 1000000); + printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); + item_kill_tree(&tree); + printf("%d: nr_allocated=%d\n", __LINE__, nr_allocated); +} + +static void single_check(void) +{ + struct item *items[BATCH]; + RADIX_TREE(tree, GFP_KERNEL); + int ret; + + item_insert(&tree, 0); + item_tag_set(&tree, 0, 0); + ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 0, BATCH, 0); + assert(ret == 1); + ret = radix_tree_gang_lookup_tag(&tree, (void **)items, 1, BATCH, 0); + assert(ret == 0); + verify_tag_consistency(&tree, 0); + verify_tag_consistency(&tree, 1); + item_kill_tree(&tree); +} + +void tag_check(void) +{ + single_check(); + extend_checks(); + contract_checks(); + printf("after extend_checks: %d allocated\n", nr_allocated); + __leak_check(); + leak_check(); + printf("after leak_check: %d allocated\n", nr_allocated); + simple_checks(); + printf("after simple_checks: %d allocated\n", nr_allocated); + thrash_tags(); + printf("after thrash_tags: %d allocated\n", nr_allocated); +} diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c new file mode 100644 index 000000000000..2bebf34cdc27 --- /dev/null +++ b/tools/testing/radix-tree/test.c @@ -0,0 +1,219 @@ +#include <stdlib.h> +#include <assert.h> +#include <stdio.h> +#include <linux/types.h> +#include <linux/kernel.h> +#include <linux/bitops.h> + +#include "test.h" + +struct item * +item_tag_set(struct radix_tree_root *root, unsigned long index, int tag) +{ + return radix_tree_tag_set(root, index, tag); +} + +struct item * +item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag) +{ + return radix_tree_tag_clear(root, index, tag); +} + +int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag) +{ + return radix_tree_tag_get(root, index, tag); +} + +int __item_insert(struct radix_tree_root *root, struct item *item) +{ + return radix_tree_insert(root, item->index, item); +} + +int item_insert(struct radix_tree_root *root, unsigned long index) +{ + return __item_insert(root, item_create(index)); +} + +int item_delete(struct radix_tree_root *root, unsigned long index) +{ + struct item *item = radix_tree_delete(root, index); + + if (item) { + assert(item->index == index); + free(item); + return 1; + } + return 0; +} + +struct item *item_create(unsigned long index) +{ + struct item *ret = malloc(sizeof(*ret)); + + ret->index = index; + return ret; +} + +void item_check_present(struct radix_tree_root *root, unsigned long index) +{ + struct item *item; + + item = radix_tree_lookup(root, index); + assert(item != 0); + assert(item->index == index); +} + +struct item *item_lookup(struct radix_tree_root *root, unsigned long index) +{ + return radix_tree_lookup(root, index); +} + +void item_check_absent(struct radix_tree_root *root, unsigned long index) +{ + struct item *item; + + item = radix_tree_lookup(root, index); + assert(item == 0); +} + +/* + * Scan only the passed (start, start+nr] for present items + */ +void item_gang_check_present(struct radix_tree_root *root, + unsigned long start, unsigned long nr, + int chunk, int hop) +{ + struct item *items[chunk]; + unsigned long into; + + for (into = 0; into < nr; ) { + int nfound; + int nr_to_find = chunk; + int i; + + if (nr_to_find > (nr - into)) + nr_to_find = nr - into; + + nfound = radix_tree_gang_lookup(root, (void **)items, + start + into, nr_to_find); + assert(nfound == nr_to_find); + for (i = 0; i < nfound; i++) + assert(items[i]->index == start + into + i); + into += hop; + } +} + +/* + * Scan the entire tree, only expecting present items (start, start+nr] + */ +void item_full_scan(struct radix_tree_root *root, unsigned long start, + unsigned long nr, int chunk) +{ + struct item *items[chunk]; + unsigned long into = 0; + unsigned long this_index = start; + int nfound; + int i; + +// printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk); + + while ((nfound = radix_tree_gang_lookup(root, (void **)items, into, + chunk))) { +// printf("At 0x%08lx, nfound=%d\n", into, nfound); + for (i = 0; i < nfound; i++) { + assert(items[i]->index == this_index); + this_index++; + } +// printf("Found 0x%08lx->0x%08lx\n", +// items[0]->index, items[nfound-1]->index); + into = this_index; + } + if (chunk) + assert(this_index == start + nr); + nfound = radix_tree_gang_lookup(root, (void **)items, + this_index, chunk); + assert(nfound == 0); +} + +static int verify_node(struct radix_tree_node *slot, unsigned int tag, + unsigned int height, int tagged) +{ + int anyset = 0; + int i; + int j; + + slot = indirect_to_ptr(slot); + + /* Verify consistency at this level */ + for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) { + if (slot->tags[tag][i]) { + anyset = 1; + break; + } + } + if (tagged != anyset) { + printf("tag: %u, height %u, tagged: %d, anyset: %d\n", tag, height, tagged, anyset); + for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { + printf("tag %d: ", j); + for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) + printf("%016lx ", slot->tags[j][i]); + printf("\n"); + } + return 1; + } + assert(tagged == anyset); + + /* Go for next level */ + if (height > 1) { + for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) + if (slot->slots[i]) + if (verify_node(slot->slots[i], tag, height - 1, + !!test_bit(i, slot->tags[tag]))) { + printf("Failure at off %d\n", i); + for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) { + printf("tag %d: ", j); + for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) + printf("%016lx ", slot->tags[j][i]); + printf("\n"); + } + return 1; + } + } + return 0; +} + +void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag) +{ + if (!root->height) + return; + verify_node(root->rnode, tag, root->height, !!root_tag_get(root, tag)); +} + +void item_kill_tree(struct radix_tree_root *root) +{ + struct item *items[32]; + int nfound; + + while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) { + int i; + + for (i = 0; i < nfound; i++) { + void *ret; + + ret = radix_tree_delete(root, items[i]->index); + assert(ret == items[i]); + free(items[i]); + } + } + assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0); + assert(root->rnode == NULL); +} + +void tree_verify_min_height(struct radix_tree_root *root, int maxindex) +{ + assert(radix_tree_maxindex(root->height) >= maxindex); + if (root->height > 1) + assert(radix_tree_maxindex(root->height-1) < maxindex); + else if (root->height == 1) + assert(radix_tree_maxindex(root->height-1) <= maxindex); +} diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h new file mode 100644 index 000000000000..4e1d95faaa94 --- /dev/null +++ b/tools/testing/radix-tree/test.h @@ -0,0 +1,40 @@ +#include <linux/gfp.h> +#include <linux/types.h> +#include <linux/radix-tree.h> +#include <linux/rcupdate.h> + +struct item { + unsigned long index; +}; + +struct item *item_create(unsigned long index); +int __item_insert(struct radix_tree_root *root, struct item *item); +int item_insert(struct radix_tree_root *root, unsigned long index); +int item_delete(struct radix_tree_root *root, unsigned long index); +struct item *item_lookup(struct radix_tree_root *root, unsigned long index); + +void item_check_present(struct radix_tree_root *root, unsigned long index); +void item_check_absent(struct radix_tree_root *root, unsigned long index); +void item_gang_check_present(struct radix_tree_root *root, + unsigned long start, unsigned long nr, + int chunk, int hop); +void item_full_scan(struct radix_tree_root *root, unsigned long start, + unsigned long nr, int chunk); +void item_kill_tree(struct radix_tree_root *root); + +void tag_check(void); + +struct item * +item_tag_set(struct radix_tree_root *root, unsigned long index, int tag); +struct item * +item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag); +int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag); +void tree_verify_min_height(struct radix_tree_root *root, int maxindex); +void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag); + +extern int nr_allocated; + +/* Normally private parts of lib/radix-tree.c */ +void *indirect_to_ptr(void *ptr); +int root_tag_get(struct radix_tree_root *root, unsigned int tag); +unsigned long radix_tree_maxindex(unsigned int height); diff --git a/tools/testing/selftests/lib/Makefile b/tools/testing/selftests/lib/Makefile index 47147b968514..08360060ab14 100644 --- a/tools/testing/selftests/lib/Makefile +++ b/tools/testing/selftests/lib/Makefile @@ -3,6 +3,6 @@ # No binaries, but make sure arg-less "make" doesn't trigger "run_tests" all: -TEST_PROGS := printf.sh +TEST_PROGS := printf.sh bitmap.sh include ../lib.mk diff --git a/tools/testing/selftests/lib/bitmap.sh b/tools/testing/selftests/lib/bitmap.sh new file mode 100755 index 000000000000..2da187b6ddad --- /dev/null +++ b/tools/testing/selftests/lib/bitmap.sh @@ -0,0 +1,10 @@ +#!/bin/sh +# Runs bitmap infrastructure tests using test_bitmap kernel module + +if /sbin/modprobe -q test_bitmap; then + /sbin/modprobe -q -r test_bitmap + echo "bitmap: ok" +else + echo "bitmap: [FAIL]" + exit 1 +fi diff --git a/tools/testing/selftests/net/.gitignore b/tools/testing/selftests/net/.gitignore index 6fb23366b258..69bb3fc38fb2 100644 --- a/tools/testing/selftests/net/.gitignore +++ b/tools/testing/selftests/net/.gitignore @@ -2,3 +2,4 @@ socket psock_fanout psock_tpacket reuseport_bpf +reuseport_bpf_cpu diff --git a/tools/testing/selftests/net/Makefile b/tools/testing/selftests/net/Makefile index 41449b5ad0a9..c658792d47b4 100644 --- a/tools/testing/selftests/net/Makefile +++ b/tools/testing/selftests/net/Makefile @@ -4,7 +4,7 @@ CFLAGS = -Wall -O2 -g CFLAGS += -I../../../../usr/include/ -NET_PROGS = socket psock_fanout psock_tpacket reuseport_bpf +NET_PROGS = socket psock_fanout psock_tpacket reuseport_bpf reuseport_bpf_cpu all: $(NET_PROGS) %: %.c diff --git a/tools/testing/selftests/net/reuseport_bpf.c b/tools/testing/selftests/net/reuseport_bpf.c index bec1b5dd2530..96ba386b1b7b 100644 --- a/tools/testing/selftests/net/reuseport_bpf.c +++ b/tools/testing/selftests/net/reuseport_bpf.c @@ -9,10 +9,12 @@ #include <errno.h> #include <error.h> +#include <fcntl.h> #include <linux/bpf.h> #include <linux/filter.h> #include <linux/unistd.h> #include <netinet/in.h> +#include <netinet/tcp.h> #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -169,9 +171,15 @@ static void build_recv_group(const struct test_params p, int fd[], uint16_t mod, if (bind(fd[i], addr, sockaddr_size())) error(1, errno, "failed to bind recv socket %d", i); - if (p.protocol == SOCK_STREAM) + if (p.protocol == SOCK_STREAM) { + opt = 4; + if (setsockopt(fd[i], SOL_TCP, TCP_FASTOPEN, &opt, + sizeof(opt))) + error(1, errno, + "failed to set TCP_FASTOPEN on %d", i); if (listen(fd[i], p.recv_socks * 10)) error(1, errno, "failed to listen on socket"); + } } free(addr); } @@ -189,10 +197,8 @@ static void send_from(struct test_params p, uint16_t sport, char *buf, if (bind(fd, saddr, sockaddr_size())) error(1, errno, "failed to bind send socket"); - if (connect(fd, daddr, sockaddr_size())) - error(1, errno, "failed to connect"); - if (send(fd, buf, len, 0) < 0) + if (sendto(fd, buf, len, MSG_FASTOPEN, daddr, sockaddr_size()) < 0) error(1, errno, "failed to send message"); close(fd); @@ -260,7 +266,7 @@ static void test_recv_order(const struct test_params p, int fd[], int mod) } } -static void test_reuseport_ebpf(const struct test_params p) +static void test_reuseport_ebpf(struct test_params p) { int i, fd[p.recv_socks]; @@ -268,6 +274,7 @@ static void test_reuseport_ebpf(const struct test_params p) build_recv_group(p, fd, p.recv_socks, attach_ebpf); test_recv_order(p, fd, p.recv_socks); + p.send_port_min += p.recv_socks * 2; fprintf(stderr, "Reprograming, testing mod %zd...\n", p.recv_socks / 2); attach_ebpf(fd[0], p.recv_socks / 2); test_recv_order(p, fd, p.recv_socks / 2); @@ -276,7 +283,7 @@ static void test_reuseport_ebpf(const struct test_params p) close(fd[i]); } -static void test_reuseport_cbpf(const struct test_params p) +static void test_reuseport_cbpf(struct test_params p) { int i, fd[p.recv_socks]; @@ -284,6 +291,7 @@ static void test_reuseport_cbpf(const struct test_params p) build_recv_group(p, fd, p.recv_socks, attach_cbpf); test_recv_order(p, fd, p.recv_socks); + p.send_port_min += p.recv_socks * 2; fprintf(stderr, "Reprograming, testing mod %zd...\n", p.recv_socks / 2); attach_cbpf(fd[0], p.recv_socks / 2); test_recv_order(p, fd, p.recv_socks / 2); @@ -377,7 +385,7 @@ static void test_filter_no_reuseport(const struct test_params p) static void test_filter_without_bind(void) { - int fd1, fd2; + int fd1, fd2, opt = 1; fprintf(stderr, "Testing filter add without bind...\n"); fd1 = socket(AF_INET, SOCK_DGRAM, 0); @@ -386,6 +394,10 @@ static void test_filter_without_bind(void) fd2 = socket(AF_INET, SOCK_DGRAM, 0); if (fd2 < 0) error(1, errno, "failed to create socket 2"); + if (setsockopt(fd1, SOL_SOCKET, SO_REUSEPORT, &opt, sizeof(opt))) + error(1, errno, "failed to set SO_REUSEPORT on socket 1"); + if (setsockopt(fd2, SOL_SOCKET, SO_REUSEPORT, &opt, sizeof(opt))) + error(1, errno, "failed to set SO_REUSEPORT on socket 2"); attach_ebpf(fd1, 10); attach_cbpf(fd2, 10); @@ -394,6 +406,32 @@ static void test_filter_without_bind(void) close(fd2); } +void enable_fastopen(void) +{ + int fd = open("/proc/sys/net/ipv4/tcp_fastopen", 0); + int rw_mask = 3; /* bit 1: client side; bit-2 server side */ + int val, size; + char buf[16]; + + if (fd < 0) + error(1, errno, "Unable to open tcp_fastopen sysctl"); + if (read(fd, buf, sizeof(buf)) <= 0) + error(1, errno, "Unable to read tcp_fastopen sysctl"); + val = atoi(buf); + close(fd); + + if ((val & rw_mask) != rw_mask) { + fd = open("/proc/sys/net/ipv4/tcp_fastopen", O_RDWR); + if (fd < 0) + error(1, errno, + "Unable to open tcp_fastopen sysctl for writing"); + val |= rw_mask; + size = snprintf(buf, 16, "%d", val); + if (write(fd, buf, size) <= 0) + error(1, errno, "Unable to write tcp_fastopen sysctl"); + close(fd); + } +} int main(void) { @@ -506,6 +544,71 @@ int main(void) .recv_port = 8007, .send_port_min = 9100}); + /* TCP fastopen is required for the TCP tests */ + enable_fastopen(); + fprintf(stderr, "---- IPv4 TCP ----\n"); + test_reuseport_ebpf((struct test_params) { + .recv_family = AF_INET, + .send_family = AF_INET, + .protocol = SOCK_STREAM, + .recv_socks = 10, + .recv_port = 8008, + .send_port_min = 9120}); + test_reuseport_cbpf((struct test_params) { + .recv_family = AF_INET, + .send_family = AF_INET, + .protocol = SOCK_STREAM, + .recv_socks = 10, + .recv_port = 8009, + .send_port_min = 9160}); + test_extra_filter((struct test_params) { + .recv_family = AF_INET, + .protocol = SOCK_STREAM, + .recv_port = 8010}); + test_filter_no_reuseport((struct test_params) { + .recv_family = AF_INET, + .protocol = SOCK_STREAM, + .recv_port = 8011}); + + fprintf(stderr, "---- IPv6 TCP ----\n"); + test_reuseport_ebpf((struct test_params) { + .recv_family = AF_INET6, + .send_family = AF_INET6, + .protocol = SOCK_STREAM, + .recv_socks = 10, + .recv_port = 8012, + .send_port_min = 9200}); + test_reuseport_cbpf((struct test_params) { + .recv_family = AF_INET6, + .send_family = AF_INET6, + .protocol = SOCK_STREAM, + .recv_socks = 10, + .recv_port = 8013, + .send_port_min = 9240}); + test_extra_filter((struct test_params) { + .recv_family = AF_INET6, + .protocol = SOCK_STREAM, + .recv_port = 8014}); + test_filter_no_reuseport((struct test_params) { + .recv_family = AF_INET6, + .protocol = SOCK_STREAM, + .recv_port = 8015}); + + fprintf(stderr, "---- IPv6 TCP w/ mapped IPv4 ----\n"); + test_reuseport_ebpf((struct test_params) { + .recv_family = AF_INET6, + .send_family = AF_INET, + .protocol = SOCK_STREAM, + .recv_socks = 10, + .recv_port = 8016, + .send_port_min = 9320}); + test_reuseport_cbpf((struct test_params) { + .recv_family = AF_INET6, + .send_family = AF_INET, + .protocol = SOCK_STREAM, + .recv_socks = 10, + .recv_port = 8017, + .send_port_min = 9360}); test_filter_without_bind(); diff --git a/tools/testing/selftests/net/reuseport_bpf_cpu.c b/tools/testing/selftests/net/reuseport_bpf_cpu.c new file mode 100644 index 000000000000..b23d6f54de7b --- /dev/null +++ b/tools/testing/selftests/net/reuseport_bpf_cpu.c @@ -0,0 +1,258 @@ +/* + * Test functionality of BPF filters with SO_REUSEPORT. This program creates + * an SO_REUSEPORT receiver group containing one socket per CPU core. It then + * creates a BPF program that will select a socket from this group based + * on the core id that receives the packet. The sending code artificially + * moves itself to run on different core ids and sends one message from + * each core. Since these packets are delivered over loopback, they should + * arrive on the same core that sent them. The receiving code then ensures + * that the packet was received on the socket for the corresponding core id. + * This entire process is done for several different core id permutations + * and for each IPv4/IPv6 and TCP/UDP combination. + */ + +#define _GNU_SOURCE + +#include <arpa/inet.h> +#include <errno.h> +#include <error.h> +#include <linux/filter.h> +#include <linux/in.h> +#include <linux/unistd.h> +#include <sched.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/epoll.h> +#include <sys/types.h> +#include <sys/socket.h> +#include <unistd.h> + +static const int PORT = 8888; + +static void build_rcv_group(int *rcv_fd, size_t len, int family, int proto) +{ + struct sockaddr_storage addr; + struct sockaddr_in *addr4; + struct sockaddr_in6 *addr6; + size_t i; + int opt; + + switch (family) { + case AF_INET: + addr4 = (struct sockaddr_in *)&addr; + addr4->sin_family = AF_INET; + addr4->sin_addr.s_addr = htonl(INADDR_ANY); + addr4->sin_port = htons(PORT); + break; + case AF_INET6: + addr6 = (struct sockaddr_in6 *)&addr; + addr6->sin6_family = AF_INET6; + addr6->sin6_addr = in6addr_any; + addr6->sin6_port = htons(PORT); + break; + default: + error(1, 0, "Unsupported family %d", family); + } + + for (i = 0; i < len; ++i) { + rcv_fd[i] = socket(family, proto, 0); + if (rcv_fd[i] < 0) + error(1, errno, "failed to create receive socket"); + + opt = 1; + if (setsockopt(rcv_fd[i], SOL_SOCKET, SO_REUSEPORT, &opt, + sizeof(opt))) + error(1, errno, "failed to set SO_REUSEPORT"); + + if (bind(rcv_fd[i], (struct sockaddr *)&addr, sizeof(addr))) + error(1, errno, "failed to bind receive socket"); + + if (proto == SOCK_STREAM && listen(rcv_fd[i], len * 10)) + error(1, errno, "failed to listen on receive port"); + } +} + +static void attach_bpf(int fd) +{ + struct sock_filter code[] = { + /* A = raw_smp_processor_id() */ + { BPF_LD | BPF_W | BPF_ABS, 0, 0, SKF_AD_OFF + SKF_AD_CPU }, + /* return A */ + { BPF_RET | BPF_A, 0, 0, 0 }, + }; + struct sock_fprog p = { + .len = 2, + .filter = code, + }; + + if (setsockopt(fd, SOL_SOCKET, SO_ATTACH_REUSEPORT_CBPF, &p, sizeof(p))) + error(1, errno, "failed to set SO_ATTACH_REUSEPORT_CBPF"); +} + +static void send_from_cpu(int cpu_id, int family, int proto) +{ + struct sockaddr_storage saddr, daddr; + struct sockaddr_in *saddr4, *daddr4; + struct sockaddr_in6 *saddr6, *daddr6; + cpu_set_t cpu_set; + int fd; + + switch (family) { + case AF_INET: + saddr4 = (struct sockaddr_in *)&saddr; + saddr4->sin_family = AF_INET; + saddr4->sin_addr.s_addr = htonl(INADDR_ANY); + saddr4->sin_port = 0; + + daddr4 = (struct sockaddr_in *)&daddr; + daddr4->sin_family = AF_INET; + daddr4->sin_addr.s_addr = htonl(INADDR_LOOPBACK); + daddr4->sin_port = htons(PORT); + break; + case AF_INET6: + saddr6 = (struct sockaddr_in6 *)&saddr; + saddr6->sin6_family = AF_INET6; + saddr6->sin6_addr = in6addr_any; + saddr6->sin6_port = 0; + + daddr6 = (struct sockaddr_in6 *)&daddr; + daddr6->sin6_family = AF_INET6; + daddr6->sin6_addr = in6addr_loopback; + daddr6->sin6_port = htons(PORT); + break; + default: + error(1, 0, "Unsupported family %d", family); + } + + memset(&cpu_set, 0, sizeof(cpu_set)); + CPU_SET(cpu_id, &cpu_set); + if (sched_setaffinity(0, sizeof(cpu_set), &cpu_set) < 0) + error(1, errno, "failed to pin to cpu"); + + fd = socket(family, proto, 0); + if (fd < 0) + error(1, errno, "failed to create send socket"); + + if (bind(fd, (struct sockaddr *)&saddr, sizeof(saddr))) + error(1, errno, "failed to bind send socket"); + + if (connect(fd, (struct sockaddr *)&daddr, sizeof(daddr))) + error(1, errno, "failed to connect send socket"); + + if (send(fd, "a", 1, 0) < 0) + error(1, errno, "failed to send message"); + + close(fd); +} + +static +void receive_on_cpu(int *rcv_fd, int len, int epfd, int cpu_id, int proto) +{ + struct epoll_event ev; + int i, fd; + char buf[8]; + + i = epoll_wait(epfd, &ev, 1, -1); + if (i < 0) + error(1, errno, "epoll_wait failed"); + + if (proto == SOCK_STREAM) { + fd = accept(ev.data.fd, NULL, NULL); + if (fd < 0) + error(1, errno, "failed to accept"); + i = recv(fd, buf, sizeof(buf), 0); + close(fd); + } else { + i = recv(ev.data.fd, buf, sizeof(buf), 0); + } + + if (i < 0) + error(1, errno, "failed to recv"); + + for (i = 0; i < len; ++i) + if (ev.data.fd == rcv_fd[i]) + break; + if (i == len) + error(1, 0, "failed to find socket"); + fprintf(stderr, "send cpu %d, receive socket %d\n", cpu_id, i); + if (cpu_id != i) + error(1, 0, "cpu id/receive socket mismatch"); +} + +static void test(int *rcv_fd, int len, int family, int proto) +{ + struct epoll_event ev; + int epfd, cpu; + + build_rcv_group(rcv_fd, len, family, proto); + attach_bpf(rcv_fd[0]); + + epfd = epoll_create(1); + if (epfd < 0) + error(1, errno, "failed to create epoll"); + for (cpu = 0; cpu < len; ++cpu) { + ev.events = EPOLLIN; + ev.data.fd = rcv_fd[cpu]; + if (epoll_ctl(epfd, EPOLL_CTL_ADD, rcv_fd[cpu], &ev)) + error(1, errno, "failed to register sock epoll"); + } + + /* Forward iterate */ + for (cpu = 0; cpu < len; ++cpu) { + send_from_cpu(cpu, family, proto); + receive_on_cpu(rcv_fd, len, epfd, cpu, proto); + } + + /* Reverse iterate */ + for (cpu = len - 1; cpu >= 0; --cpu) { + send_from_cpu(cpu, family, proto); + receive_on_cpu(rcv_fd, len, epfd, cpu, proto); + } + + /* Even cores */ + for (cpu = 0; cpu < len; cpu += 2) { + send_from_cpu(cpu, family, proto); + receive_on_cpu(rcv_fd, len, epfd, cpu, proto); + } + + /* Odd cores */ + for (cpu = 1; cpu < len; cpu += 2) { + send_from_cpu(cpu, family, proto); + receive_on_cpu(rcv_fd, len, epfd, cpu, proto); + } + + close(epfd); + for (cpu = 0; cpu < len; ++cpu) + close(rcv_fd[cpu]); +} + +int main(void) +{ + int *rcv_fd, cpus; + + cpus = sysconf(_SC_NPROCESSORS_ONLN); + if (cpus <= 0) + error(1, errno, "failed counting cpus"); + + rcv_fd = calloc(cpus, sizeof(int)); + if (!rcv_fd) + error(1, 0, "failed to allocate array"); + + fprintf(stderr, "---- IPv4 UDP ----\n"); + test(rcv_fd, cpus, AF_INET, SOCK_DGRAM); + + fprintf(stderr, "---- IPv6 UDP ----\n"); + test(rcv_fd, cpus, AF_INET6, SOCK_DGRAM); + + fprintf(stderr, "---- IPv4 TCP ----\n"); + test(rcv_fd, cpus, AF_INET, SOCK_STREAM); + + fprintf(stderr, "---- IPv6 TCP ----\n"); + test(rcv_fd, cpus, AF_INET6, SOCK_STREAM); + + free(rcv_fd); + + fprintf(stderr, "SUCCESS\n"); + return 0; +} diff --git a/tools/testing/selftests/powerpc/Makefile b/tools/testing/selftests/powerpc/Makefile index 0c2706bda330..b08f77cbe31b 100644 --- a/tools/testing/selftests/powerpc/Makefile +++ b/tools/testing/selftests/powerpc/Makefile @@ -8,7 +8,7 @@ ifeq ($(ARCH),powerpc) GIT_VERSION = $(shell git describe --always --long --dirty || echo "unknown") -CFLAGS := -Wall -O2 -flto -Wall -Werror -DGIT_VERSION='"$(GIT_VERSION)"' -I$(CURDIR) $(CFLAGS) +CFLAGS := -Wall -O2 -Wall -Werror -DGIT_VERSION='"$(GIT_VERSION)"' -I$(CURDIR) $(CFLAGS) export CFLAGS @@ -22,7 +22,8 @@ SUB_DIRS = benchmarks \ switch_endian \ syscalls \ tm \ - vphn + vphn \ + math endif diff --git a/tools/testing/selftests/powerpc/basic_asm.h b/tools/testing/selftests/powerpc/basic_asm.h new file mode 100644 index 000000000000..3349a0704d1a --- /dev/null +++ b/tools/testing/selftests/powerpc/basic_asm.h @@ -0,0 +1,70 @@ +#ifndef _SELFTESTS_POWERPC_BASIC_ASM_H +#define _SELFTESTS_POWERPC_BASIC_ASM_H + +#include <ppc-asm.h> +#include <asm/unistd.h> + +#define LOAD_REG_IMMEDIATE(reg,expr) \ + lis reg,(expr)@highest; \ + ori reg,reg,(expr)@higher; \ + rldicr reg,reg,32,31; \ + oris reg,reg,(expr)@high; \ + ori reg,reg,(expr)@l; + +/* + * Note: These macros assume that variables being stored on the stack are + * doublewords, while this is usually the case it may not always be the + * case for each use case. + */ +#if defined(_CALL_ELF) && _CALL_ELF == 2 +#define STACK_FRAME_MIN_SIZE 32 +#define STACK_FRAME_TOC_POS 24 +#define __STACK_FRAME_PARAM(_param) (32 + ((_param)*8)) +#define __STACK_FRAME_LOCAL(_num_params,_var_num) ((STACK_FRAME_PARAM(_num_params)) + ((_var_num)*8)) +#else +#define STACK_FRAME_MIN_SIZE 112 +#define STACK_FRAME_TOC_POS 40 +#define __STACK_FRAME_PARAM(i) (48 + ((i)*8)) + +/* + * Caveat: if a function passed more than 8 doublewords, the caller will have + * made more space... which would render the 112 incorrect. + */ +#define __STACK_FRAME_LOCAL(_num_params,_var_num) (112 + ((_var_num)*8)) +#endif + +/* Parameter x saved to the stack */ +#define STACK_FRAME_PARAM(var) __STACK_FRAME_PARAM(var) + +/* Local variable x saved to the stack after x parameters */ +#define STACK_FRAME_LOCAL(num_params,var) __STACK_FRAME_LOCAL(num_params,var) +#define STACK_FRAME_LR_POS 16 +#define STACK_FRAME_CR_POS 8 + +/* + * It is very important to note here that _extra is the extra amount of + * stack space needed. This space can be accessed using STACK_FRAME_PARAM() + * or STACK_FRAME_LOCAL() macros. + * + * r1 and r2 are not defined in ppc-asm.h (instead they are defined as sp + * and toc). Kernel programmers tend to prefer rX even for r1 and r2, hence + * %1 and %r2. r0 is defined in ppc-asm.h and therefore %r0 gets + * preprocessed incorrectly, hence r0. + */ +#define PUSH_BASIC_STACK(_extra) \ + mflr r0; \ + std r0,STACK_FRAME_LR_POS(%r1); \ + stdu %r1,-(_extra + STACK_FRAME_MIN_SIZE)(%r1); \ + mfcr r0; \ + stw r0,STACK_FRAME_CR_POS(%r1); \ + std %r2,STACK_FRAME_TOC_POS(%r1); + +#define POP_BASIC_STACK(_extra) \ + ld %r2,STACK_FRAME_TOC_POS(%r1); \ + lwz r0,STACK_FRAME_CR_POS(%r1); \ + mtcr r0; \ + addi %r1,%r1,(_extra + STACK_FRAME_MIN_SIZE); \ + ld r0,STACK_FRAME_LR_POS(%r1); \ + mtlr r0; + +#endif /* _SELFTESTS_POWERPC_BASIC_ASM_H */ diff --git a/tools/testing/selftests/powerpc/math/.gitignore b/tools/testing/selftests/powerpc/math/.gitignore new file mode 100644 index 000000000000..4fe13a439fd7 --- /dev/null +++ b/tools/testing/selftests/powerpc/math/.gitignore @@ -0,0 +1,6 @@ +fpu_syscall +vmx_syscall +fpu_preempt +vmx_preempt +fpu_signal +vmx_signal diff --git a/tools/testing/selftests/powerpc/math/Makefile b/tools/testing/selftests/powerpc/math/Makefile new file mode 100644 index 000000000000..5b88875d5955 --- /dev/null +++ b/tools/testing/selftests/powerpc/math/Makefile @@ -0,0 +1,19 @@ +TEST_PROGS := fpu_syscall fpu_preempt fpu_signal vmx_syscall vmx_preempt vmx_signal + +all: $(TEST_PROGS) + +$(TEST_PROGS): ../harness.c +$(TEST_PROGS): CFLAGS += -O2 -g -pthread -m64 -maltivec + +fpu_syscall: fpu_asm.S +fpu_preempt: fpu_asm.S +fpu_signal: fpu_asm.S + +vmx_syscall: vmx_asm.S +vmx_preempt: vmx_asm.S +vmx_signal: vmx_asm.S + +include ../../lib.mk + +clean: + rm -f $(TEST_PROGS) *.o diff --git a/tools/testing/selftests/powerpc/math/fpu_asm.S b/tools/testing/selftests/powerpc/math/fpu_asm.S new file mode 100644 index 000000000000..f3711d80e709 --- /dev/null +++ b/tools/testing/selftests/powerpc/math/fpu_asm.S @@ -0,0 +1,198 @@ +/* + * Copyright 2015, Cyril Bur, IBM Corp. + * + * 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 "../basic_asm.h" + +#define PUSH_FPU(pos) \ + stfd f14,pos(sp); \ + stfd f15,pos+8(sp); \ + stfd f16,pos+16(sp); \ + stfd f17,pos+24(sp); \ + stfd f18,pos+32(sp); \ + stfd f19,pos+40(sp); \ + stfd f20,pos+48(sp); \ + stfd f21,pos+56(sp); \ + stfd f22,pos+64(sp); \ + stfd f23,pos+72(sp); \ + stfd f24,pos+80(sp); \ + stfd f25,pos+88(sp); \ + stfd f26,pos+96(sp); \ + stfd f27,pos+104(sp); \ + stfd f28,pos+112(sp); \ + stfd f29,pos+120(sp); \ + stfd f30,pos+128(sp); \ + stfd f31,pos+136(sp); + +#define POP_FPU(pos) \ + lfd f14,pos(sp); \ + lfd f15,pos+8(sp); \ + lfd f16,pos+16(sp); \ + lfd f17,pos+24(sp); \ + lfd f18,pos+32(sp); \ + lfd f19,pos+40(sp); \ + lfd f20,pos+48(sp); \ + lfd f21,pos+56(sp); \ + lfd f22,pos+64(sp); \ + lfd f23,pos+72(sp); \ + lfd f24,pos+80(sp); \ + lfd f25,pos+88(sp); \ + lfd f26,pos+96(sp); \ + lfd f27,pos+104(sp); \ + lfd f28,pos+112(sp); \ + lfd f29,pos+120(sp); \ + lfd f30,pos+128(sp); \ + lfd f31,pos+136(sp); + +# Careful calling this, it will 'clobber' fpu (by design) +# Don't call this from C +FUNC_START(load_fpu) + lfd f14,0(r3) + lfd f15,8(r3) + lfd f16,16(r3) + lfd f17,24(r3) + lfd f18,32(r3) + lfd f19,40(r3) + lfd f20,48(r3) + lfd f21,56(r3) + lfd f22,64(r3) + lfd f23,72(r3) + lfd f24,80(r3) + lfd f25,88(r3) + lfd f26,96(r3) + lfd f27,104(r3) + lfd f28,112(r3) + lfd f29,120(r3) + lfd f30,128(r3) + lfd f31,136(r3) + blr +FUNC_END(load_fpu) + +FUNC_START(check_fpu) + mr r4,r3 + li r3,1 # assume a bad result + lfd f0,0(r4) + fcmpu cr1,f0,f14 + bne cr1,1f + lfd f0,8(r4) + fcmpu cr1,f0,f15 + bne cr1,1f + lfd f0,16(r4) + fcmpu cr1,f0,f16 + bne cr1,1f + lfd f0,24(r4) + fcmpu cr1,f0,f17 + bne cr1,1f + lfd f0,32(r4) + fcmpu cr1,f0,f18 + bne cr1,1f + lfd f0,40(r4) + fcmpu cr1,f0,f19 + bne cr1,1f + lfd f0,48(r4) + fcmpu cr1,f0,f20 + bne cr1,1f + lfd f0,56(r4) + fcmpu cr1,f0,f21 + bne cr1,1f + lfd f0,64(r4) + fcmpu cr1,f0,f22 + bne cr1,1f + lfd f0,72(r4) + fcmpu cr1,f0,f23 + bne cr1,1f + lfd f0,80(r4) + fcmpu cr1,f0,f24 + bne cr1,1f + lfd f0,88(r4) + fcmpu cr1,f0,f25 + bne cr1,1f + lfd f0,96(r4) + fcmpu cr1,f0,f26 + bne cr1,1f + lfd f0,104(r4) + fcmpu cr1,f0,f27 + bne cr1,1f + lfd f0,112(r4) + fcmpu cr1,f0,f28 + bne cr1,1f + lfd f0,120(r4) + fcmpu cr1,f0,f29 + bne cr1,1f + lfd f0,128(r4) + fcmpu cr1,f0,f30 + bne cr1,1f + lfd f0,136(r4) + fcmpu cr1,f0,f31 + bne cr1,1f + li r3,0 # Success!!! +1: blr + +FUNC_START(test_fpu) + # r3 holds pointer to where to put the result of fork + # r4 holds pointer to the pid + # f14-f31 are non volatiles + PUSH_BASIC_STACK(256) + std r3,STACK_FRAME_PARAM(0)(sp) # Address of darray + std r4,STACK_FRAME_PARAM(1)(sp) # Address of pid + PUSH_FPU(STACK_FRAME_LOCAL(2,0)) + + bl load_fpu + nop + li r0,__NR_fork + sc + + # pass the result of the fork to the caller + ld r9,STACK_FRAME_PARAM(1)(sp) + std r3,0(r9) + + ld r3,STACK_FRAME_PARAM(0)(sp) + bl check_fpu + nop + + POP_FPU(STACK_FRAME_LOCAL(2,0)) + POP_BASIC_STACK(256) + blr +FUNC_END(test_fpu) + +# int preempt_fpu(double *darray, int *threads_running, int *running) +# On starting will (atomically) decrement not_ready as a signal that the FPU +# has been loaded with darray. Will proceed to check the validity of the FPU +# registers while running is not zero. +FUNC_START(preempt_fpu) + PUSH_BASIC_STACK(256) + std r3,STACK_FRAME_PARAM(0)(sp) # double *darray + std r4,STACK_FRAME_PARAM(1)(sp) # int *threads_starting + std r5,STACK_FRAME_PARAM(2)(sp) # int *running + PUSH_FPU(STACK_FRAME_LOCAL(3,0)) + + bl load_fpu + nop + + sync + # Atomic DEC + ld r3,STACK_FRAME_PARAM(1)(sp) +1: lwarx r4,0,r3 + addi r4,r4,-1 + stwcx. r4,0,r3 + bne- 1b + +2: ld r3,STACK_FRAME_PARAM(0)(sp) + bl check_fpu + nop + cmpdi r3,0 + bne 3f + ld r4,STACK_FRAME_PARAM(2)(sp) + ld r5,0(r4) + cmpwi r5,0 + bne 2b + +3: POP_FPU(STACK_FRAME_LOCAL(3,0)) + POP_BASIC_STACK(256) + blr +FUNC_END(preempt_fpu) diff --git a/tools/testing/selftests/powerpc/math/fpu_preempt.c b/tools/testing/selftests/powerpc/math/fpu_preempt.c new file mode 100644 index 000000000000..0f85b79d883d --- /dev/null +++ b/tools/testing/selftests/powerpc/math/fpu_preempt.c @@ -0,0 +1,113 @@ +/* + * Copyright 2015, Cyril Bur, IBM Corp. + * + * 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. + * + * This test attempts to see if the FPU registers change across preemption. + * Two things should be noted here a) The check_fpu function in asm only checks + * the non volatile registers as it is reused from the syscall test b) There is + * no way to be sure preemption happened so this test just uses many threads + * and a long wait. As such, a successful test doesn't mean much but a failure + * is bad. + */ + +#include <stdio.h> +#include <unistd.h> +#include <sys/syscall.h> +#include <sys/time.h> +#include <sys/types.h> +#include <sys/wait.h> +#include <stdlib.h> +#include <pthread.h> + +#include "utils.h" + +/* Time to wait for workers to get preempted (seconds) */ +#define PREEMPT_TIME 20 +/* + * Factor by which to multiply number of online CPUs for total number of + * worker threads + */ +#define THREAD_FACTOR 8 + + +__thread double darray[] = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, + 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0, + 2.1}; + +int threads_starting; +int running; + +extern void preempt_fpu(double *darray, int *threads_starting, int *running); + +void *preempt_fpu_c(void *p) +{ + int i; + srand(pthread_self()); + for (i = 0; i < 21; i++) + darray[i] = rand(); + + /* Test failed if it ever returns */ + preempt_fpu(darray, &threads_starting, &running); + + return p; +} + +int test_preempt_fpu(void) +{ + int i, rc, threads; + pthread_t *tids; + + threads = sysconf(_SC_NPROCESSORS_ONLN) * THREAD_FACTOR; + tids = malloc((threads) * sizeof(pthread_t)); + FAIL_IF(!tids); + + running = true; + threads_starting = threads; + for (i = 0; i < threads; i++) { + rc = pthread_create(&tids[i], NULL, preempt_fpu_c, NULL); + FAIL_IF(rc); + } + + setbuf(stdout, NULL); + /* Not really necessary but nice to wait for every thread to start */ + printf("\tWaiting for all workers to start..."); + while(threads_starting) + asm volatile("": : :"memory"); + printf("done\n"); + + printf("\tWaiting for %d seconds to let some workers get preempted...", PREEMPT_TIME); + sleep(PREEMPT_TIME); + printf("done\n"); + + printf("\tStopping workers..."); + /* + * Working are checking this value every loop. In preempt_fpu 'cmpwi r5,0; bne 2b'. + * r5 will have loaded the value of running. + */ + running = 0; + for (i = 0; i < threads; i++) { + void *rc_p; + pthread_join(tids[i], &rc_p); + + /* + * Harness will say the fail was here, look at why preempt_fpu + * returned + */ + if ((long) rc_p) + printf("oops\n"); + FAIL_IF((long) rc_p); + } + printf("done\n"); + + free(tids); + return 0; +} + +int main(int argc, char *argv[]) +{ + return test_harness(test_preempt_fpu, "fpu_preempt"); +} diff --git a/tools/testing/selftests/powerpc/math/fpu_signal.c b/tools/testing/selftests/powerpc/math/fpu_signal.c new file mode 100644 index 000000000000..888aa51b4204 --- /dev/null +++ b/tools/testing/selftests/powerpc/math/fpu_signal.c @@ -0,0 +1,135 @@ +/* + * Copyright 2015, Cyril Bur, IBM Corp. + * + * 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. + * + * This test attempts to see if the FPU registers are correctly reported in a + * signal context. Each worker just spins checking its FPU registers, at some + * point a signal will interrupt it and C code will check the signal context + * ensuring it is also the same. + */ + +#include <stdio.h> +#include <unistd.h> +#include <sys/syscall.h> +#include <sys/time.h> +#include <sys/types.h> +#include <sys/wait.h> +#include <stdlib.h> +#include <pthread.h> + +#include "utils.h" + +/* Number of times each thread should receive the signal */ +#define ITERATIONS 10 +/* + * Factor by which to multiply number of online CPUs for total number of + * worker threads + */ +#define THREAD_FACTOR 8 + +__thread double darray[] = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, + 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0, + 2.1}; + +bool bad_context; +int threads_starting; +int running; + +extern long preempt_fpu(double *darray, int *threads_starting, int *running); + +void signal_fpu_sig(int sig, siginfo_t *info, void *context) +{ + int i; + ucontext_t *uc = context; + mcontext_t *mc = &uc->uc_mcontext; + + /* Only the non volatiles were loaded up */ + for (i = 14; i < 32; i++) { + if (mc->fp_regs[i] != darray[i - 14]) { + bad_context = true; + break; + } + } +} + +void *signal_fpu_c(void *p) +{ + int i; + long rc; + struct sigaction act; + act.sa_sigaction = signal_fpu_sig; + act.sa_flags = SA_SIGINFO; + rc = sigaction(SIGUSR1, &act, NULL); + if (rc) + return p; + + srand(pthread_self()); + for (i = 0; i < 21; i++) + darray[i] = rand(); + + rc = preempt_fpu(darray, &threads_starting, &running); + + return (void *) rc; +} + +int test_signal_fpu(void) +{ + int i, j, rc, threads; + void *rc_p; + pthread_t *tids; + + threads = sysconf(_SC_NPROCESSORS_ONLN) * THREAD_FACTOR; + tids = malloc(threads * sizeof(pthread_t)); + FAIL_IF(!tids); + + running = true; + threads_starting = threads; + for (i = 0; i < threads; i++) { + rc = pthread_create(&tids[i], NULL, signal_fpu_c, NULL); + FAIL_IF(rc); + } + + setbuf(stdout, NULL); + printf("\tWaiting for all workers to start..."); + while (threads_starting) + asm volatile("": : :"memory"); + printf("done\n"); + + printf("\tSending signals to all threads %d times...", ITERATIONS); + for (i = 0; i < ITERATIONS; i++) { + for (j = 0; j < threads; j++) { + pthread_kill(tids[j], SIGUSR1); + } + sleep(1); + } + printf("done\n"); + + printf("\tStopping workers..."); + running = 0; + for (i = 0; i < threads; i++) { + pthread_join(tids[i], &rc_p); + + /* + * Harness will say the fail was here, look at why signal_fpu + * returned + */ + if ((long) rc_p || bad_context) + printf("oops\n"); + if (bad_context) + fprintf(stderr, "\t!! bad_context is true\n"); + FAIL_IF((long) rc_p || bad_context); + } + printf("done\n"); + + free(tids); + return 0; +} + +int main(int argc, char *argv[]) +{ + return test_harness(test_signal_fpu, "fpu_signal"); +} diff --git a/tools/testing/selftests/powerpc/math/fpu_syscall.c b/tools/testing/selftests/powerpc/math/fpu_syscall.c new file mode 100644 index 000000000000..949e6721256d --- /dev/null +++ b/tools/testing/selftests/powerpc/math/fpu_syscall.c @@ -0,0 +1,90 @@ +/* + * Copyright 2015, Cyril Bur, IBM Corp. + * + * 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. + * + * This test attempts to see if the FPU registers change across a syscall (fork). + */ + +#include <stdio.h> +#include <unistd.h> +#include <sys/syscall.h> +#include <sys/time.h> +#include <sys/types.h> +#include <sys/wait.h> +#include <stdlib.h> + +#include "utils.h" + +extern int test_fpu(double *darray, pid_t *pid); + +double darray[] = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0, + 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9, 2.0, + 2.1}; + +int syscall_fpu(void) +{ + pid_t fork_pid; + int i; + int ret; + int child_ret; + for (i = 0; i < 1000; i++) { + /* test_fpu will fork() */ + ret = test_fpu(darray, &fork_pid); + if (fork_pid == -1) + return -1; + if (fork_pid == 0) + exit(ret); + waitpid(fork_pid, &child_ret, 0); + if (ret || child_ret) + return 1; + } + + return 0; +} + +int test_syscall_fpu(void) +{ + /* + * Setup an environment with much context switching + */ + pid_t pid2; + pid_t pid = fork(); + int ret; + int child_ret; + FAIL_IF(pid == -1); + + pid2 = fork(); + /* Can't FAIL_IF(pid2 == -1); because already forked once */ + if (pid2 == -1) { + /* + * Couldn't fork, ensure test is a fail + */ + child_ret = ret = 1; + } else { + ret = syscall_fpu(); + if (pid2) + waitpid(pid2, &child_ret, 0); + else + exit(ret); + } + + ret |= child_ret; + + if (pid) + waitpid(pid, &child_ret, 0); + else + exit(ret); + + FAIL_IF(ret || child_ret); + return 0; +} + +int main(int argc, char *argv[]) +{ + return test_harness(test_syscall_fpu, "syscall_fpu"); + +} diff --git a/tools/testing/selftests/powerpc/math/vmx_asm.S b/tools/testing/selftests/powerpc/math/vmx_asm.S new file mode 100644 index 000000000000..1b8c248b3ac1 --- /dev/null +++ b/tools/testing/selftests/powerpc/math/vmx_asm.S @@ -0,0 +1,235 @@ +/* + * Copyright 2015, Cyril Bur, IBM Corp. + * + * 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 "../basic_asm.h" + +# POS MUST BE 16 ALIGNED! +#define PUSH_VMX(pos,reg) \ + li reg,pos; \ + stvx v20,reg,sp; \ + addi reg,reg,16; \ + stvx v21,reg,sp; \ + addi reg,reg,16; \ + stvx v22,reg,sp; \ + addi reg,reg,16; \ + stvx v23,reg,sp; \ + addi reg,reg,16; \ + stvx v24,reg,sp; \ + addi reg,reg,16; \ + stvx v25,reg,sp; \ + addi reg,reg,16; \ + stvx v26,reg,sp; \ + addi reg,reg,16; \ + stvx v27,reg,sp; \ + addi reg,reg,16; \ + stvx v28,reg,sp; \ + addi reg,reg,16; \ + stvx v29,reg,sp; \ + addi reg,reg,16; \ + stvx v30,reg,sp; \ + addi reg,reg,16; \ + stvx v31,reg,sp; + +# POS MUST BE 16 ALIGNED! +#define POP_VMX(pos,reg) \ + li reg,pos; \ + lvx v20,reg,sp; \ + addi reg,reg,16; \ + lvx v21,reg,sp; \ + addi reg,reg,16; \ + lvx v22,reg,sp; \ + addi reg,reg,16; \ + lvx v23,reg,sp; \ + addi reg,reg,16; \ + lvx v24,reg,sp; \ + addi reg,reg,16; \ + lvx v25,reg,sp; \ + addi reg,reg,16; \ + lvx v26,reg,sp; \ + addi reg,reg,16; \ + lvx v27,reg,sp; \ + addi reg,reg,16; \ + lvx v28,reg,sp; \ + addi reg,reg,16; \ + lvx v29,reg,sp; \ + addi reg,reg,16; \ + lvx v30,reg,sp; \ + addi reg,reg,16; \ + lvx v31,reg,sp; + +# Carefull this will 'clobber' vmx (by design) +# Don't call this from C +FUNC_START(load_vmx) + li r5,0 + lvx v20,r5,r3 + addi r5,r5,16 + lvx v21,r5,r3 + addi r5,r5,16 + lvx v22,r5,r3 + addi r5,r5,16 + lvx v23,r5,r3 + addi r5,r5,16 + lvx v24,r5,r3 + addi r5,r5,16 + lvx v25,r5,r3 + addi r5,r5,16 + lvx v26,r5,r3 + addi r5,r5,16 + lvx v27,r5,r3 + addi r5,r5,16 + lvx v28,r5,r3 + addi r5,r5,16 + lvx v29,r5,r3 + addi r5,r5,16 + lvx v30,r5,r3 + addi r5,r5,16 + lvx v31,r5,r3 + blr +FUNC_END(load_vmx) + +# Should be safe from C, only touches r4, r5 and v0,v1,v2 +FUNC_START(check_vmx) + PUSH_BASIC_STACK(32) + mr r4,r3 + li r3,1 # assume a bad result + li r5,0 + lvx v0,r5,r4 + vcmpequd. v1,v0,v20 + vmr v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v21 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v22 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v23 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v24 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v25 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v26 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v27 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v28 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v29 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v30 + vand v2,v2,v1 + + addi r5,r5,16 + lvx v0,r5,r4 + vcmpequd. v1,v0,v31 + vand v2,v2,v1 + + li r5,STACK_FRAME_LOCAL(0,0) + stvx v2,r5,sp + ldx r0,r5,sp + cmpdi r0,0xffffffffffffffff + bne 1f + li r3,0 +1: POP_BASIC_STACK(32) + blr +FUNC_END(check_vmx) + +# Safe from C +FUNC_START(test_vmx) + # r3 holds pointer to where to put the result of fork + # r4 holds pointer to the pid + # v20-v31 are non-volatile + PUSH_BASIC_STACK(512) + std r3,STACK_FRAME_PARAM(0)(sp) # Address of varray + std r4,STACK_FRAME_PARAM(1)(sp) # address of pid + PUSH_VMX(STACK_FRAME_LOCAL(2,0),r4) + + bl load_vmx + nop + + li r0,__NR_fork + sc + # Pass the result of fork back to the caller + ld r9,STACK_FRAME_PARAM(1)(sp) + std r3,0(r9) + + ld r3,STACK_FRAME_PARAM(0)(sp) + bl check_vmx + nop + + POP_VMX(STACK_FRAME_LOCAL(2,0),r4) + POP_BASIC_STACK(512) + blr +FUNC_END(test_vmx) + +# int preempt_vmx(vector int *varray, int *threads_starting, int *running) +# On starting will (atomically) decrement threads_starting as a signal that +# the VMX have been loaded with varray. Will proceed to check the validity of +# the VMX registers while running is not zero. +FUNC_START(preempt_vmx) + PUSH_BASIC_STACK(512) + std r3,STACK_FRAME_PARAM(0)(sp) # vector int *varray + std r4,STACK_FRAME_PARAM(1)(sp) # int *threads_starting + std r5,STACK_FRAME_PARAM(2)(sp) # int *running + # VMX need to write to 16 byte aligned addresses, skip STACK_FRAME_LOCAL(3,0) + PUSH_VMX(STACK_FRAME_LOCAL(4,0),r4) + + bl load_vmx + nop + + sync + # Atomic DEC + ld r3,STACK_FRAME_PARAM(1)(sp) +1: lwarx r4,0,r3 + addi r4,r4,-1 + stwcx. r4,0,r3 + bne- 1b + +2: ld r3,STACK_FRAME_PARAM(0)(sp) + bl check_vmx + nop + cmpdi r3,0 + bne 3f + ld r4,STACK_FRAME_PARAM(2)(sp) + ld r5,0(r4) + cmpwi r5,0 + bne 2b + +3: POP_VMX(STACK_FRAME_LOCAL(4,0),r4) + POP_BASIC_STACK(512) + blr +FUNC_END(preempt_vmx) diff --git a/tools/testing/selftests/powerpc/math/vmx_preempt.c b/tools/testing/selftests/powerpc/math/vmx_preempt.c new file mode 100644 index 000000000000..9ef376c55b13 --- /dev/null +++ b/tools/testing/selftests/powerpc/math/vmx_preempt.c @@ -0,0 +1,112 @@ +/* + * Copyright 2015, Cyril Bur, IBM Corp. + * + * 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. + * + * This test attempts to see if the VMX registers change across preemption. + * Two things should be noted here a) The check_vmx function in asm only checks + * the non volatile registers as it is reused from the syscall test b) There is + * no way to be sure preemption happened so this test just uses many threads + * and a long wait. As such, a successful test doesn't mean much but a failure + * is bad. + */ + +#include <stdio.h> +#include <unistd.h> +#include <sys/syscall.h> +#include <sys/time.h> +#include <sys/types.h> +#include <sys/wait.h> +#include <stdlib.h> +#include <pthread.h> + +#include "utils.h" + +/* Time to wait for workers to get preempted (seconds) */ +#define PREEMPT_TIME 20 +/* + * Factor by which to multiply number of online CPUs for total number of + * worker threads + */ +#define THREAD_FACTOR 8 + +__thread vector int varray[] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10,11,12}, + {13,14,15,16},{17,18,19,20},{21,22,23,24}, + {25,26,27,28},{29,30,31,32},{33,34,35,36}, + {37,38,39,40},{41,42,43,44},{45,46,47,48}}; + +int threads_starting; +int running; + +extern void preempt_vmx(vector int *varray, int *threads_starting, int *running); + +void *preempt_vmx_c(void *p) +{ + int i, j; + srand(pthread_self()); + for (i = 0; i < 12; i++) + for (j = 0; j < 4; j++) + varray[i][j] = rand(); + + /* Test fails if it ever returns */ + preempt_vmx(varray, &threads_starting, &running); + return p; +} + +int test_preempt_vmx(void) +{ + int i, rc, threads; + pthread_t *tids; + + threads = sysconf(_SC_NPROCESSORS_ONLN) * THREAD_FACTOR; + tids = malloc(threads * sizeof(pthread_t)); + FAIL_IF(!tids); + + running = true; + threads_starting = threads; + for (i = 0; i < threads; i++) { + rc = pthread_create(&tids[i], NULL, preempt_vmx_c, NULL); + FAIL_IF(rc); + } + + setbuf(stdout, NULL); + /* Not really nessesary but nice to wait for every thread to start */ + printf("\tWaiting for all workers to start..."); + while(threads_starting) + asm volatile("": : :"memory"); + printf("done\n"); + + printf("\tWaiting for %d seconds to let some workers get preempted...", PREEMPT_TIME); + sleep(PREEMPT_TIME); + printf("done\n"); + + printf("\tStopping workers..."); + /* + * Working are checking this value every loop. In preempt_vmx 'cmpwi r5,0; bne 2b'. + * r5 will have loaded the value of running. + */ + running = 0; + for (i = 0; i < threads; i++) { + void *rc_p; + pthread_join(tids[i], &rc_p); + + /* + * Harness will say the fail was here, look at why preempt_vmx + * returned + */ + if ((long) rc_p) + printf("oops\n"); + FAIL_IF((long) rc_p); + } + printf("done\n"); + + return 0; +} + +int main(int argc, char *argv[]) +{ + return test_harness(test_preempt_vmx, "vmx_preempt"); +} diff --git a/tools/testing/selftests/powerpc/math/vmx_signal.c b/tools/testing/selftests/powerpc/math/vmx_signal.c new file mode 100644 index 000000000000..671d7533a557 --- /dev/null +++ b/tools/testing/selftests/powerpc/math/vmx_signal.c @@ -0,0 +1,156 @@ +/* + * Copyright 2015, Cyril Bur, IBM Corp. + * + * 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. + * + * This test attempts to see if the VMX registers are correctly reported in a + * signal context. Each worker just spins checking its VMX registers, at some + * point a signal will interrupt it and C code will check the signal context + * ensuring it is also the same. + */ + +#include <stdio.h> +#include <unistd.h> +#include <sys/syscall.h> +#include <sys/time.h> +#include <sys/types.h> +#include <sys/wait.h> +#include <stdlib.h> +#include <string.h> +#include <pthread.h> +#include <altivec.h> + +#include "utils.h" + +/* Number of times each thread should receive the signal */ +#define ITERATIONS 10 +/* + * Factor by which to multiply number of online CPUs for total number of + * worker threads + */ +#define THREAD_FACTOR 8 + +__thread vector int varray[] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10,11,12}, + {13,14,15,16},{17,18,19,20},{21,22,23,24}, + {25,26,27,28},{29,30,31,32},{33,34,35,36}, + {37,38,39,40},{41,42,43,44},{45,46,47,48}}; + +bool bad_context; +int running; +int threads_starting; + +extern int preempt_vmx(vector int *varray, int *threads_starting, int *sentinal); + +void signal_vmx_sig(int sig, siginfo_t *info, void *context) +{ + int i; + ucontext_t *uc = context; + mcontext_t *mc = &uc->uc_mcontext; + + /* Only the non volatiles were loaded up */ + for (i = 20; i < 32; i++) { + if (memcmp(mc->v_regs->vrregs[i], &varray[i - 20], 16)) { + int j; + /* + * Shouldn't printf() in a signal handler, however, this is a + * test and we've detected failure. Understanding what failed + * is paramount. All that happens after this is tests exit with + * failure. + */ + printf("VMX mismatch at reg %d!\n", i); + printf("Reg | Actual | Expected\n"); + for (j = 20; j < 32; j++) { + printf("%d | 0x%04x%04x%04x%04x | 0x%04x%04x%04x%04x\n", j, mc->v_regs->vrregs[j][0], + mc->v_regs->vrregs[j][1], mc->v_regs->vrregs[j][2], mc->v_regs->vrregs[j][3], + varray[j - 20][0], varray[j - 20][1], varray[j - 20][2], varray[j - 20][3]); + } + bad_context = true; + break; + } + } +} + +void *signal_vmx_c(void *p) +{ + int i, j; + long rc; + struct sigaction act; + act.sa_sigaction = signal_vmx_sig; + act.sa_flags = SA_SIGINFO; + rc = sigaction(SIGUSR1, &act, NULL); + if (rc) + return p; + + srand(pthread_self()); + for (i = 0; i < 12; i++) + for (j = 0; j < 4; j++) + varray[i][j] = rand(); + + rc = preempt_vmx(varray, &threads_starting, &running); + + return (void *) rc; +} + +int test_signal_vmx(void) +{ + int i, j, rc, threads; + void *rc_p; + pthread_t *tids; + + threads = sysconf(_SC_NPROCESSORS_ONLN) * THREAD_FACTOR; + tids = malloc(threads * sizeof(pthread_t)); + FAIL_IF(!tids); + + running = true; + threads_starting = threads; + for (i = 0; i < threads; i++) { + rc = pthread_create(&tids[i], NULL, signal_vmx_c, NULL); + FAIL_IF(rc); + } + + setbuf(stdout, NULL); + printf("\tWaiting for %d workers to start... %d", threads, threads_starting); + while (threads_starting) { + asm volatile("": : :"memory"); + usleep(1000); + printf(", %d", threads_starting); + } + printf(" ...done\n"); + + printf("\tSending signals to all threads %d times...", ITERATIONS); + for (i = 0; i < ITERATIONS; i++) { + for (j = 0; j < threads; j++) { + pthread_kill(tids[j], SIGUSR1); + } + sleep(1); + } + printf("done\n"); + + printf("\tKilling workers..."); + running = 0; + for (i = 0; i < threads; i++) { + pthread_join(tids[i], &rc_p); + + /* + * Harness will say the fail was here, look at why signal_vmx + * returned + */ + if ((long) rc_p || bad_context) + printf("oops\n"); + if (bad_context) + fprintf(stderr, "\t!! bad_context is true\n"); + FAIL_IF((long) rc_p || bad_context); + } + printf("done\n"); + + free(tids); + return 0; +} + +int main(int argc, char *argv[]) +{ + return test_harness(test_signal_vmx, "vmx_signal"); +} diff --git a/tools/testing/selftests/powerpc/math/vmx_syscall.c b/tools/testing/selftests/powerpc/math/vmx_syscall.c new file mode 100644 index 000000000000..a017918ee1ca --- /dev/null +++ b/tools/testing/selftests/powerpc/math/vmx_syscall.c @@ -0,0 +1,91 @@ +/* + * Copyright 2015, Cyril Bur, IBM Corp. + * + * 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. + * + * This test attempts to see if the VMX registers change across a syscall (fork). + */ + +#include <altivec.h> +#include <stdio.h> +#include <unistd.h> +#include <sys/syscall.h> +#include <sys/time.h> +#include <stdlib.h> +#include <sys/types.h> +#include <sys/wait.h> +#include "utils.h" + +vector int varray[] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10,11,12}, + {13,14,15,16},{17,18,19,20},{21,22,23,24}, + {25,26,27,28},{29,30,31,32},{33,34,35,36}, + {37,38,39,40},{41,42,43,44},{45,46,47,48}}; + +extern int test_vmx(vector int *varray, pid_t *pid); + +int vmx_syscall(void) +{ + pid_t fork_pid; + int i; + int ret; + int child_ret; + for (i = 0; i < 1000; i++) { + /* test_vmx will fork() */ + ret = test_vmx(varray, &fork_pid); + if (fork_pid == -1) + return -1; + if (fork_pid == 0) + exit(ret); + waitpid(fork_pid, &child_ret, 0); + if (ret || child_ret) + return 1; + } + + return 0; +} + +int test_vmx_syscall(void) +{ + /* + * Setup an environment with much context switching + */ + pid_t pid2; + pid_t pid = fork(); + int ret; + int child_ret; + FAIL_IF(pid == -1); + + pid2 = fork(); + ret = vmx_syscall(); + /* Can't FAIL_IF(pid2 == -1); because we've already forked */ + if (pid2 == -1) { + /* + * Couldn't fork, ensure child_ret is set and is a fail + */ + ret = child_ret = 1; + } else { + if (pid2) + waitpid(pid2, &child_ret, 0); + else + exit(ret); + } + + ret |= child_ret; + + if (pid) + waitpid(pid, &child_ret, 0); + else + exit(ret); + + FAIL_IF(ret || child_ret); + return 0; +} + +int main(int argc, char *argv[]) +{ + return test_harness(test_vmx_syscall, "vmx_syscall"); + +} diff --git a/tools/testing/selftests/powerpc/tm/tm-signal-msr-resv.c b/tools/testing/selftests/powerpc/tm/tm-signal-msr-resv.c index d86653f282b1..8c54d18b3e9a 100644 --- a/tools/testing/selftests/powerpc/tm/tm-signal-msr-resv.c +++ b/tools/testing/selftests/powerpc/tm/tm-signal-msr-resv.c @@ -40,7 +40,7 @@ void signal_usr1(int signum, siginfo_t *info, void *uc) #ifdef __powerpc64__ ucp->uc_mcontext.gp_regs[PT_MSR] |= (7ULL << 32); #else - ucp->uc_mcontext.regs->gpr[PT_MSR] |= (7ULL); + ucp->uc_mcontext.uc_regs->gregs[PT_MSR] |= (7ULL); #endif /* Should segv on return becuase of invalid context */ segv_expected = 1; diff --git a/tools/testing/selftests/seccomp/seccomp_bpf.c b/tools/testing/selftests/seccomp/seccomp_bpf.c index b9453b838162..150829dd7998 100644 --- a/tools/testing/selftests/seccomp/seccomp_bpf.c +++ b/tools/testing/selftests/seccomp/seccomp_bpf.c @@ -1497,15 +1497,15 @@ TEST_F(TRACE_syscall, syscall_dropped) #define SECCOMP_SET_MODE_FILTER 1 #endif -#ifndef SECCOMP_FLAG_FILTER_TSYNC -#define SECCOMP_FLAG_FILTER_TSYNC 1 +#ifndef SECCOMP_FILTER_FLAG_TSYNC +#define SECCOMP_FILTER_FLAG_TSYNC 1 #endif #ifndef seccomp -int seccomp(unsigned int op, unsigned int flags, struct sock_fprog *filter) +int seccomp(unsigned int op, unsigned int flags, void *args) { errno = 0; - return syscall(__NR_seccomp, op, flags, filter); + return syscall(__NR_seccomp, op, flags, args); } #endif @@ -1613,7 +1613,7 @@ TEST(TSYNC_first) TH_LOG("Kernel does not support PR_SET_NO_NEW_PRIVS!"); } - ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FLAG_FILTER_TSYNC, + ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FILTER_FLAG_TSYNC, &prog); ASSERT_NE(ENOSYS, errno) { TH_LOG("Kernel does not support seccomp syscall!"); @@ -1831,7 +1831,7 @@ TEST_F(TSYNC, two_siblings_with_ancestor) self->sibling_count++; } - ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FLAG_FILTER_TSYNC, + ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FILTER_FLAG_TSYNC, &self->apply_prog); ASSERT_EQ(0, ret) { TH_LOG("Could install filter on all threads!"); @@ -1892,7 +1892,7 @@ TEST_F(TSYNC, two_siblings_with_no_filter) TH_LOG("Kernel does not support PR_SET_NO_NEW_PRIVS!"); } - ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FLAG_FILTER_TSYNC, + ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FILTER_FLAG_TSYNC, &self->apply_prog); ASSERT_NE(ENOSYS, errno) { TH_LOG("Kernel does not support seccomp syscall!"); @@ -1940,7 +1940,7 @@ TEST_F(TSYNC, two_siblings_with_one_divergence) self->sibling_count++; } - ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FLAG_FILTER_TSYNC, + ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FILTER_FLAG_TSYNC, &self->apply_prog); ASSERT_EQ(self->sibling[0].system_tid, ret) { TH_LOG("Did not fail on diverged sibling."); @@ -1992,7 +1992,7 @@ TEST_F(TSYNC, two_siblings_not_under_filter) TH_LOG("Kernel does not support SECCOMP_SET_MODE_FILTER!"); } - ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FLAG_FILTER_TSYNC, + ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FILTER_FLAG_TSYNC, &self->apply_prog); ASSERT_EQ(ret, self->sibling[0].system_tid) { TH_LOG("Did not fail on diverged sibling."); @@ -2021,7 +2021,7 @@ TEST_F(TSYNC, two_siblings_not_under_filter) /* Switch to the remaining sibling */ sib = !sib; - ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FLAG_FILTER_TSYNC, + ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FILTER_FLAG_TSYNC, &self->apply_prog); ASSERT_EQ(0, ret) { TH_LOG("Expected the remaining sibling to sync"); @@ -2044,7 +2044,7 @@ TEST_F(TSYNC, two_siblings_not_under_filter) while (!kill(self->sibling[sib].system_tid, 0)) sleep(0.1); - ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FLAG_FILTER_TSYNC, + ret = seccomp(SECCOMP_SET_MODE_FILTER, SECCOMP_FILTER_FLAG_TSYNC, &self->apply_prog); ASSERT_EQ(0, ret); /* just us chickens */ } diff --git a/tools/testing/selftests/timers/alarmtimer-suspend.c b/tools/testing/selftests/timers/alarmtimer-suspend.c index 72cacf5383dd..2b361b830395 100644 --- a/tools/testing/selftests/timers/alarmtimer-suspend.c +++ b/tools/testing/selftests/timers/alarmtimer-suspend.c @@ -153,7 +153,7 @@ int main(void) alarmcount = 0; if (timer_create(alarm_clock_id, &se, &tm1) == -1) { - printf("timer_create failled, %s unspported?\n", + printf("timer_create failed, %s unsupported?\n", clockstring(alarm_clock_id)); break; } diff --git a/tools/testing/selftests/x86/Makefile b/tools/testing/selftests/x86/Makefile index d5ce7d7aae3e..b47ebd170690 100644 --- a/tools/testing/selftests/x86/Makefile +++ b/tools/testing/selftests/x86/Makefile @@ -5,7 +5,7 @@ include ../lib.mk .PHONY: all all_32 all_64 warn_32bit_failure clean TARGETS_C_BOTHBITS := single_step_syscall sysret_ss_attrs syscall_nt ptrace_syscall \ - check_initial_reg_state sigreturn ldt_gdt + check_initial_reg_state sigreturn ldt_gdt iopl TARGETS_C_32BIT_ONLY := entry_from_vm86 syscall_arg_fault test_syscall_vdso unwind_vdso \ test_FCMOV test_FCOMI test_FISTTP \ vdso_restorer diff --git a/tools/testing/selftests/x86/iopl.c b/tools/testing/selftests/x86/iopl.c new file mode 100644 index 000000000000..c496ca97bc18 --- /dev/null +++ b/tools/testing/selftests/x86/iopl.c @@ -0,0 +1,135 @@ +/* + * iopl.c - Test case for a Linux on Xen 64-bit bug + * Copyright (c) 2015 Andrew Lutomirski + */ + +#define _GNU_SOURCE +#include <err.h> +#include <stdio.h> +#include <stdint.h> +#include <signal.h> +#include <setjmp.h> +#include <stdlib.h> +#include <string.h> +#include <errno.h> +#include <unistd.h> +#include <sys/types.h> +#include <sys/wait.h> +#include <stdbool.h> +#include <sched.h> +#include <sys/io.h> + +static int nerrs = 0; + +static void sethandler(int sig, void (*handler)(int, siginfo_t *, void *), + int flags) +{ + struct sigaction sa; + memset(&sa, 0, sizeof(sa)); + sa.sa_sigaction = handler; + sa.sa_flags = SA_SIGINFO | flags; + sigemptyset(&sa.sa_mask); + if (sigaction(sig, &sa, 0)) + err(1, "sigaction"); + +} + +static jmp_buf jmpbuf; + +static void sigsegv(int sig, siginfo_t *si, void *ctx_void) +{ + siglongjmp(jmpbuf, 1); +} + +int main(void) +{ + cpu_set_t cpuset; + CPU_ZERO(&cpuset); + CPU_SET(0, &cpuset); + if (sched_setaffinity(0, sizeof(cpuset), &cpuset) != 0) + err(1, "sched_setaffinity to CPU 0"); + + /* Probe for iopl support. Note that iopl(0) works even as nonroot. */ + if (iopl(3) != 0) { + printf("[OK]\tiopl(3) failed (%d) -- try running as root\n", + errno); + return 0; + } + + /* Restore our original state prior to starting the test. */ + if (iopl(0) != 0) + err(1, "iopl(0)"); + + pid_t child = fork(); + if (child == -1) + err(1, "fork"); + + if (child == 0) { + printf("\tchild: set IOPL to 3\n"); + if (iopl(3) != 0) + err(1, "iopl"); + + printf("[RUN]\tchild: write to 0x80\n"); + asm volatile ("outb %%al, $0x80" : : "a" (0)); + + return 0; + } else { + int status; + if (waitpid(child, &status, 0) != child || + !WIFEXITED(status)) { + printf("[FAIL]\tChild died\n"); + nerrs++; + } else if (WEXITSTATUS(status) != 0) { + printf("[FAIL]\tChild failed\n"); + nerrs++; + } else { + printf("[OK]\tChild succeeded\n"); + } + } + + printf("[RUN]\tparent: write to 0x80 (should fail)\n"); + + sethandler(SIGSEGV, sigsegv, 0); + if (sigsetjmp(jmpbuf, 1) != 0) { + printf("[OK]\twrite was denied\n"); + } else { + asm volatile ("outb %%al, $0x80" : : "a" (0)); + printf("[FAIL]\twrite was allowed\n"); + nerrs++; + } + + /* Test the capability checks. */ + printf("\tiopl(3)\n"); + if (iopl(3) != 0) + err(1, "iopl(3)"); + + printf("\tDrop privileges\n"); + if (setresuid(1, 1, 1) != 0) { + printf("[WARN]\tDropping privileges failed\n"); + goto done; + } + + printf("[RUN]\tiopl(3) unprivileged but with IOPL==3\n"); + if (iopl(3) != 0) { + printf("[FAIL]\tiopl(3) should work if iopl is already 3 even if unprivileged\n"); + nerrs++; + } + + printf("[RUN]\tiopl(0) unprivileged\n"); + if (iopl(0) != 0) { + printf("[FAIL]\tiopl(0) should work if iopl is already 3 even if unprivileged\n"); + nerrs++; + } + + printf("[RUN]\tiopl(3) unprivileged\n"); + if (iopl(3) == 0) { + printf("[FAIL]\tiopl(3) should fail if when unprivileged if iopl==0\n"); + nerrs++; + } else { + printf("[OK]\tFailed as expected\n"); + } + +done: + return nerrs ? 1 : 0; +} + |