From cf4a7207b1cb4a3c3fe3aa11a83c9d673722a7f5 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Thu, 22 Dec 2016 14:45:14 +0000 Subject: lib: Add a simple prime number generator Prime numbers are interesting for testing components that use multiplies and divides, such as testing DRM's struct drm_mm alignment computations. v2: Move to lib/, add selftest v3: Fix initial constants (exclude 0/1 from being primes) v4: More RCU markup to keep 0day/sparse happy v5: Fix RCU unwind on module exit, add to kselftests v6: Tidy computation of bitmap size v7: for_each_prime_number_from() v8: Compose small-primes using BIT() for easier verification v9: Move rcu dance entirely into callers. v10: Improve quote for Betrand's Postulate (aka Chebyshev's theorem) Signed-off-by: Chris Wilson Cc: Lukas Wunner Reviewed-by: Joonas Lahtinen Signed-off-by: Daniel Vetter Link: http://patchwork.freedesktop.org/patch/msgid/20161222144514.3911-1-chris@chris-wilson.co.uk --- lib/Kconfig | 7 ++ lib/Makefile | 2 + lib/prime_numbers.c | 314 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 323 insertions(+) create mode 100644 lib/prime_numbers.c (limited to 'lib') diff --git a/lib/Kconfig b/lib/Kconfig index 260a80e313b9..1788a1f50d28 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -550,4 +550,11 @@ config STACKDEPOT config SBITMAP bool +config PRIME_NUMBERS + tristate "Prime number generator" + default n + help + Provides a helper module to generate prime numbers. Useful for writing + test code, especially when checking multiplication and divison. + endmenu diff --git a/lib/Makefile b/lib/Makefile index 50144a3aeebd..c664143fd917 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -197,6 +197,8 @@ obj-$(CONFIG_ASN1) += asn1_decoder.o obj-$(CONFIG_FONT_SUPPORT) += fonts/ +obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/prime_numbers.c b/lib/prime_numbers.c new file mode 100644 index 000000000000..c9b3c29614aa --- /dev/null +++ b/lib/prime_numbers.c @@ -0,0 +1,314 @@ +#define pr_fmt(fmt) "prime numbers: " fmt "\n" + +#include +#include +#include +#include + +#define bitmap_size(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long)) + +struct primes { + struct rcu_head rcu; + unsigned long last, sz; + unsigned long primes[]; +}; + +#if BITS_PER_LONG == 64 +static const struct primes small_primes = { + .last = 61, + .sz = 64, + .primes = { + BIT(2) | + BIT(3) | + BIT(5) | + BIT(7) | + BIT(11) | + BIT(13) | + BIT(17) | + BIT(19) | + BIT(23) | + BIT(29) | + BIT(31) | + BIT(37) | + BIT(41) | + BIT(43) | + BIT(47) | + BIT(53) | + BIT(59) | + BIT(61) + } +}; +#elif BITS_PER_LONG == 32 +static const struct primes small_primes = { + .last = 31, + .sz = 32, + .primes = { + BIT(2) | + BIT(3) | + BIT(5) | + BIT(7) | + BIT(11) | + BIT(13) | + BIT(17) | + BIT(19) | + BIT(23) | + BIT(29) | + BIT(31) + } +}; +#else +#error "unhandled BITS_PER_LONG" +#endif + +static DEFINE_MUTEX(lock); +static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes); + +static unsigned long selftest_max; + +static bool slow_is_prime_number(unsigned long x) +{ + unsigned long y = int_sqrt(x); + + while (y > 1) { + if ((x % y) == 0) + break; + y--; + } + + return y == 1; +} + +static unsigned long slow_next_prime_number(unsigned long x) +{ + while (x < ULONG_MAX && !slow_is_prime_number(++x)) + ; + + return x; +} + +static unsigned long clear_multiples(unsigned long x, + unsigned long *p, + unsigned long start, + unsigned long end) +{ + unsigned long m; + + m = 2 * x; + if (m < start) + m = roundup(start, x); + + while (m < end) { + __clear_bit(m, p); + m += x; + } + + return x; +} + +static bool expand_to_next_prime(unsigned long x) +{ + const struct primes *p; + struct primes *new; + unsigned long sz, y; + + /* Betrand's Postulate (or Chebyshev's theorem) states that if n > 3, + * there is always at least one prime p between n and 2n - 2. + * Equivalently, if n > 1, then there is always at least one prime p + * such that n < p < 2n. + * + * http://mathworld.wolfram.com/BertrandsPostulate.html + * https://en.wikipedia.org/wiki/Bertrand's_postulate + */ + sz = 2 * x; + if (sz < x) + return false; + + sz = round_up(sz, BITS_PER_LONG); + new = kmalloc(sizeof(*new) + bitmap_size(sz), GFP_KERNEL); + if (!new) + return false; + + mutex_lock(&lock); + p = rcu_dereference_protected(primes, lockdep_is_held(&lock)); + if (x < p->last) { + kfree(new); + goto unlock; + } + + /* Where memory permits, track the primes using the + * Sieve of Eratosthenes. The sieve is to remove all multiples of known + * primes from the set, what remains in the set is therefore prime. + */ + bitmap_fill(new->primes, sz); + bitmap_copy(new->primes, p->primes, p->sz); + for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1)) + new->last = clear_multiples(y, new->primes, p->sz, sz); + new->sz = sz; + + BUG_ON(new->last <= x); + + rcu_assign_pointer(primes, new); + if (p != &small_primes) + kfree_rcu((struct primes *)p, rcu); + +unlock: + mutex_unlock(&lock); + return true; +} + +static void free_primes(void) +{ + const struct primes *p; + + mutex_lock(&lock); + p = rcu_dereference_protected(primes, lockdep_is_held(&lock)); + if (p != &small_primes) { + rcu_assign_pointer(primes, &small_primes); + kfree_rcu((struct primes *)p, rcu); + } + mutex_unlock(&lock); +} + +/** + * next_prime_number - return the next prime number + * @x: the starting point for searching to test + * + * A prime number is an integer greater than 1 that is only divisible by + * itself and 1. The set of prime numbers is computed using the Sieve of + * Eratoshenes (on finding a prime, all multiples of that prime are removed + * from the set) enabling a fast lookup of the next prime number larger than + * @x. If the sieve fails (memory limitation), the search falls back to using + * slow trial-divison, up to the value of ULONG_MAX (which is reported as the + * final prime as a sentinel). + * + * Returns: the next prime number larger than @x + */ +unsigned long next_prime_number(unsigned long x) +{ + const struct primes *p; + + rcu_read_lock(); + p = rcu_dereference(primes); + while (x >= p->last) { + rcu_read_unlock(); + + if (!expand_to_next_prime(x)) + return slow_next_prime_number(x); + + rcu_read_lock(); + p = rcu_dereference(primes); + } + x = find_next_bit(p->primes, p->last, x + 1); + rcu_read_unlock(); + + return x; +} +EXPORT_SYMBOL(next_prime_number); + +/** + * is_prime_number - test whether the given number is prime + * @x: the number to test + * + * A prime number is an integer greater than 1 that is only divisible by + * itself and 1. Internally a cache of prime numbers is kept (to speed up + * searching for sequential primes, see next_prime_number()), but if the number + * falls outside of that cache, its primality is tested using trial-divison. + * + * Returns: true if @x is prime, false for composite numbers. + */ +bool is_prime_number(unsigned long x) +{ + const struct primes *p; + bool result; + + rcu_read_lock(); + p = rcu_dereference(primes); + while (x >= p->sz) { + rcu_read_unlock(); + + if (!expand_to_next_prime(x)) + return slow_is_prime_number(x); + + rcu_read_lock(); + p = rcu_dereference(primes); + } + result = test_bit(x, p->primes); + rcu_read_unlock(); + + return result; +} +EXPORT_SYMBOL(is_prime_number); + +static void dump_primes(void) +{ + const struct primes *p; + char *buf; + + buf = kmalloc(PAGE_SIZE, GFP_KERNEL); + + rcu_read_lock(); + p = rcu_dereference(primes); + + if (buf) + bitmap_print_to_pagebuf(true, buf, p->primes, p->sz); + pr_info("primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s", + p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf); + + rcu_read_unlock(); + + kfree(buf); +} + +static int selftest(unsigned long max) +{ + unsigned long x, last; + + if (!max) + return 0; + + for (last = 0, x = 2; x < max; x++) { + bool slow = slow_is_prime_number(x); + bool fast = is_prime_number(x); + + if (slow != fast) { + pr_err("inconsistent result for is-prime(%lu): slow=%s, fast=%s!", + x, slow ? "yes" : "no", fast ? "yes" : "no"); + goto err; + } + + if (!slow) + continue; + + if (next_prime_number(last) != x) { + pr_err("incorrect result for next-prime(%lu): expected %lu, got %lu", + last, x, next_prime_number(last)); + goto err; + } + last = x; + } + + pr_info("selftest(%lu) passed, last prime was %lu", x, last); + return 0; + +err: + dump_primes(); + return -EINVAL; +} + +static int __init primes_init(void) +{ + return selftest(selftest_max); +} + +static void __exit primes_exit(void) +{ + free_primes(); +} + +module_init(primes_init); +module_exit(primes_exit); + +module_param_named(selftest, selftest_max, ulong, 0400); + +MODULE_AUTHOR("Intel Corporation"); +MODULE_LICENSE("GPL"); -- cgit v1.2.3-59-g8ed1b From 717c8ae7aae4f23100cbd33f9aa6772fe67a74f4 Mon Sep 17 00:00:00 2001 From: Chris Wilson Date: Fri, 13 Jan 2017 23:51:19 +0000 Subject: lib/prime_numbers: Suppress warn on kmalloc failure The allocation for the bitmap may become very large, larger than MAX_ORDER, for large requests. We fail gracefully by falling back to trail-division, so disable the warning from kmalloc: 521.961092] WARNING: CPU: 0 PID: 30637 at mm/page_alloc.c:3548 __alloc_pages_slowpath+0x237/0x9a0 [ 521.961105] Modules linked in: i915(+) drm_kms_helper intel_gtt prime_numbers [last unloaded: drm_kms_helper] [ 521.961126] CPU: 0 PID: 30637 Comm: drv_selftest Tainted: G U W 4.10.0-rc3+ #321 [ 521.961137] Hardware name: / , BIOS PYBSWCEL.86A.0027.2015.0507.1758 05/07/2015 [ 521.961148] Call Trace: [ 521.961161] dump_stack+0x4d/0x6f [ 521.961172] __warn+0xc1/0xe0 [ 521.961181] warn_slowpath_null+0x18/0x20 [ 521.961189] __alloc_pages_slowpath+0x237/0x9a0 [ 521.961200] ? sg_init_table+0x1a/0x40 [ 521.961208] ? get_page_from_freelist+0x3fa/0x910 [ 521.961275] ? i915_gem_object_get_sg+0x272/0x2b0 [i915] [ 521.961285] __alloc_pages_nodemask+0x1ea/0x220 [ 521.961295] kmalloc_order+0x1c/0x50 [ 521.961304] __kmalloc+0x115/0x170 [ 521.961314] expand_to_next_prime+0x43/0x180 [prime_numbers] [ 521.961324] next_prime_number+0x47/0xc0 [prime_numbers] [ 521.961377] igt_vma_rotate+0x386/0x590 [i915] [ 521.961429] i915_subtests+0x37/0xc0 [i915] [ 521.961481] i915_vma_mock_selftests+0x3d/0x70 [i915] [ 521.961532] run_selftests+0x16e/0x1f0 [i915] [ 521.961541] ? 0xffffffffa02a4000 [ 521.961592] i915_mock_selftests+0x29/0x40 [i915] [ 521.961638] i915_init+0xa/0x5e [i915] [ 521.961646] ? 0xffffffffa02a4000 [ 521.961655] do_one_initcall+0x3e/0x160 [ 521.961664] ? __vunmap+0x7c/0xc0 [ 521.961672] ? vfree+0x29/0x70 [ 521.961680] ? kmem_cache_alloc+0xcf/0x120 [ 521.961690] do_init_module+0x55/0x1c4 [ 521.961699] load_module+0x1f3f/0x25b0 [ 521.961707] ? __symbol_put+0x40/0x40 [ 521.961716] ? kernel_read_file+0x100/0x190 [ 521.961725] SYSC_finit_module+0xbc/0xf0 [ 521.961734] SyS_finit_module+0x9/0x10 [ 521.961744] entry_SYSCALL_64_fastpath+0x17/0x98 [ 521.961752] RIP: 0033:0x7f111aca4119 [ 521.961760] RSP: 002b:00007ffd8be6cbe8 EFLAGS: 00000246 ORIG_RAX: 0000000000000139 [ 521.961773] RAX: ffffffffffffffda RBX: 0000000000000006 RCX: 00007f111aca4119 [ 521.961781] RDX: 0000000000000000 RSI: 000055dfc18bc8e0 RDI: 0000000000000006 [ 521.961789] RBP: 00007ffd8be6bbe0 R08: 0000000000000000 R09: 0000000000000000 [ 521.961796] R10: 0000000000000006 R11: 0000000000000246 R12: 0000000000000005 [ 521.961805] R13: 000055dfc18bd3a0 R14: 00007ffd8be6bbc0 R15: 0000000000000005 Signed-off-by: Chris Wilson Cc: Joonas Lahtinen Cc: Daniel Vetter Reviewed-by: Joonas Lahtinen Signed-off-by: Daniel Vetter Link: http://patchwork.freedesktop.org/patch/msgid/20170113235119.22528-1-chris@chris-wilson.co.uk --- lib/prime_numbers.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/prime_numbers.c b/lib/prime_numbers.c index c9b3c29614aa..550eec457c2e 100644 --- a/lib/prime_numbers.c +++ b/lib/prime_numbers.c @@ -124,7 +124,8 @@ static bool expand_to_next_prime(unsigned long x) return false; sz = round_up(sz, BITS_PER_LONG); - new = kmalloc(sizeof(*new) + bitmap_size(sz), GFP_KERNEL); + new = kmalloc(sizeof(*new) + bitmap_size(sz), + GFP_KERNEL | __GFP_NOWARN); if (!new) return false; -- cgit v1.2.3-59-g8ed1b From 64a577196d66b44e37384bc5c4d78c61f59d5b2a Mon Sep 17 00:00:00 2001 From: Dave Airlie Date: Fri, 24 Feb 2017 12:11:21 +1000 Subject: lib/Kconfig: make PRIME_NUMBERS not user selectable. Linus doesn't like it user selectable, so kill it until someone needs it for something else. Signed-off-by: Dave Airlie --- lib/Kconfig | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib') diff --git a/lib/Kconfig b/lib/Kconfig index 1788a1f50d28..f4193a3d9301 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -551,7 +551,7 @@ config SBITMAP bool config PRIME_NUMBERS - tristate "Prime number generator" + tristate default n help Provides a helper module to generate prime numbers. Useful for writing -- cgit v1.2.3-59-g8ed1b