From patchwork Mon Dec 19 10:05:47 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chris Wilson X-Patchwork-Id: 9480005 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 0204860237 for ; Mon, 19 Dec 2016 10:05:57 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id DFED828383 for ; Mon, 19 Dec 2016 10:05:56 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D4AB7284B0; Mon, 19 Dec 2016 10:05:56 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-4.1 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_MED, T_DKIM_INVALID autolearn=unavailable version=3.3.1 Received: from gabe.freedesktop.org (gabe.freedesktop.org [131.252.210.177]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id 54DDB28383 for ; Mon, 19 Dec 2016 10:05:56 +0000 (UTC) Received: from gabe.freedesktop.org (localhost [127.0.0.1]) by gabe.freedesktop.org (Postfix) with ESMTP id AEDAF6E585; Mon, 19 Dec 2016 10:05:54 +0000 (UTC) X-Original-To: dri-devel@lists.freedesktop.org Delivered-To: dri-devel@lists.freedesktop.org Received: from mail-wm0-x242.google.com (mail-wm0-x242.google.com [IPv6:2a00:1450:400c:c09::242]) by gabe.freedesktop.org (Postfix) with ESMTPS id 3F80F6E584; Mon, 19 Dec 2016 10:05:52 +0000 (UTC) Received: by mail-wm0-x242.google.com with SMTP id g23so17668078wme.1; Mon, 19 Dec 2016 02:05:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references; bh=So791fexORo1Ig1ZQMgP8yWNdh3f1u/7Q6W28GEdLmE=; b=MuTvKKD0R3+hixBinkhToOP1nmliOKd8qP0HuhV3v0vZo5+MAAMl1K1FXTWUNNhR3g q5EMzJ2Pys4c9DxbU/QwX4+DsMFYrRx19+yMu1CyTNeOLOKYpp3hFZnN3SiZCKCzOrXZ TZClwRZwAKUOIPraZWzJuJAsgyG3adk9Q6SamLHnlQJAZdeNPK020NlwXeSZ9AgtU3o/ 60+Dp0UAYoYeWyXWeBI5Ws6Vbu2Zx1z9SzkmWxhLF8bAqcov85y81LGhRiaX26vdarRk fnOlAG5neCQThzBCgUx+Wn1exiEhzvYfA6tDV2zO1wNriTjbIaTG7UlOwYQLJGj8NjMV kl3Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :in-reply-to:references; bh=So791fexORo1Ig1ZQMgP8yWNdh3f1u/7Q6W28GEdLmE=; b=jWfYyEeTrDlEWHGgkbe12tjlAV7yt54yZaNsI5+H4Wb/jl45qgKRrcUv7nFIB+4G8D j3P9zW4F+oQ6QVuZi19QWf/J7+n/HlUKSphKndMhDdJ2TA0CIJApWNeJedUTjlqXnOet TSOGOoy2dGm4K68tQIyRGRYN51myYW/rsoumwNO+W8hK3n8CvNA8DAMKApdhFkNoIYsg Ca2oR4Iy71NUkVyLkXrIlq5jZb7ACjwyI+uO5rhBOd4iZz6u6ARCrxeSSPNMAZdea3JP YchQZA7Nt7Q5DRgrnwxmGTlswRZ9n/SQ73E70XtcEaeN2zsP9Kt67Q4DpqwAzngMORYs m2qA== X-Gm-Message-State: AIkVDXIBgAKlu1qoc9zlXYWe/TKwOQsvNnDKnFQLDWN5NL2DRgaYCkI1wYgXljJGm6V/nA== X-Received: by 10.28.198.67 with SMTP id w64mr13670721wmf.13.1482141950418; Mon, 19 Dec 2016 02:05:50 -0800 (PST) Received: from haswell.alporthouse.com ([78.156.65.138]) by smtp.gmail.com with ESMTPSA id c202sm19506929wme.1.2016.12.19.02.05.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 19 Dec 2016 02:05:49 -0800 (PST) From: Chris Wilson To: dri-devel@lists.freedesktop.org Subject: [PATCH v6] lib: Add a simple prime number generator Date: Mon, 19 Dec 2016 10:05:47 +0000 Message-Id: <20161219100547.7199-1-chris@chris-wilson.co.uk> X-Mailer: git-send-email 2.11.0 In-Reply-To: <20161217124102.6520-1-chris@chris-wilson.co.uk> References: <20161217124102.6520-1-chris@chris-wilson.co.uk> Cc: intel-gfx@lists.freedesktop.org X-BeenThere: dri-devel@lists.freedesktop.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Direct Rendering Infrastructure - Development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: dri-devel-bounces@lists.freedesktop.org Sender: "dri-devel" X-Virus-Scanned: ClamAV using ClamSMTP 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 Signed-off-by: Chris Wilson Cc: Lukas Wunner --- include/linux/prime_numbers.h | 23 +++ lib/Kconfig | 7 + lib/Makefile | 2 + lib/prime_numbers.c | 266 +++++++++++++++++++++++++++ tools/testing/selftests/lib/prime_numbers.sh | 15 ++ 5 files changed, 313 insertions(+) create mode 100644 include/linux/prime_numbers.h create mode 100644 lib/prime_numbers.c create mode 100755 tools/testing/selftests/lib/prime_numbers.sh diff --git a/include/linux/prime_numbers.h b/include/linux/prime_numbers.h new file mode 100644 index 000000000000..6ba642c3f95d --- /dev/null +++ b/include/linux/prime_numbers.h @@ -0,0 +1,23 @@ +#ifndef __LINUX_PRIME_NUMBERS_H +#define __LINUX_PRIME_NUMBERS_H + +#include + +bool is_prime_number(unsigned long x); +unsigned long next_prime_number(unsigned long x); + +/** + * for_each_prime_number - iterate over each prime upto a value + * @prime: the current prime number in this iteration + * @max: the upper limit + * + * Starting from 1 (which is only considered prime for convenience + * of using for_each_prime_number(), a useful white lie), iterate over each + * prime number up to the @max value. On each iteration, @prime is set to the + * current prime number. @max should be less than ULONG_MAX to ensure + * termination. + */ +#define for_each_prime_number(prime, max) \ + for (prime = 1; prime <= (max); prime = next_prime_number(prime)) + +#endif /* !__LINUX_PRIME_NUMBERS_H */ 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..02795aa0e820 --- /dev/null +++ b/lib/prime_numbers.c @@ -0,0 +1,266 @@ +#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 = { 0x28208a20a08a28acUL } +}; +#elif BITS_PER_LONG == 32 +static const struct primes small_primes = { + .last = 31, + .sz = 32, + .primes = { 0xa08a28acUL } +}; +#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 mark_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 const struct primes *expand_to_next_prime(unsigned long x) +{ + const struct primes *p; + struct primes *new; + unsigned long sz, y; + + rcu_read_unlock(); + + /* Betrand's Theorem states: + * For all n > 1, there exists a prime p: n < p <= 2*n. + */ + sz = 2 * x + 1; + if (sz < x) + return NULL; + + sz = round_up(sz, BITS_PER_LONG); + new = kmalloc(sizeof(*new) + bitmap_size(sz), GFP_KERNEL); + if (!new) + return NULL; + + mutex_lock(&lock); + p = rcu_dereference_protected(primes, lockdep_is_held(&lock)); + if (x < p->last) { + kfree(new); + goto relock; + } + + /* Where memory permits, track the primes using the + * Sieve of Eratosthenes. + */ + bitmap_copy(new->primes, p->primes, p->sz); + memset(new->primes + BITS_TO_LONGS(p->sz), -1, bitmap_size(sz - p->sz)); + for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1)) + new->last = mark_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); + p = new; + +relock: + rcu_read_lock(); + mutex_unlock(&lock); + return p; +} + +static const struct primes *get_primes(unsigned long x) +{ + const struct primes *p; + + rcu_read_lock(); + p = rcu_dereference(primes); + if (!p || x >= p->last) + p = expand_to_next_prime(x); + + /* returns under RCU iff p != NULL */ + return p; +} + +/** + * 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 seive 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; + + p = get_primes(x); + if (unlikely(!p)) + return slow_next_prime_number(x); + + 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; + + p = get_primes(x); + if (unlikely(!p)) + return slow_is_prime_number(x); + + 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; + + rcu_read_lock(); + p = rcu_dereference(primes); + pr_info("primes.{last=%lu, .sz=%lu, .primes[]=...x%lx}", + p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1]); + rcu_read_unlock(); +} + +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) +{ + 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); +} + +module_init(primes_init); +module_exit(primes_exit); + +module_param_named(selftest, selftest_max, ulong, 0400); + +MODULE_AUTHOR("Intel Corporation"); +MODULE_LICENSE("GPL"); diff --git a/tools/testing/selftests/lib/prime_numbers.sh b/tools/testing/selftests/lib/prime_numbers.sh new file mode 100755 index 000000000000..da4cbcd766f5 --- /dev/null +++ b/tools/testing/selftests/lib/prime_numbers.sh @@ -0,0 +1,15 @@ +#!/bin/sh +# Checks fast/slow prime_number generation for inconsistencies + +if ! /sbin/modprobe -q -r prime_numbers; then + echo "prime_numbers: [SKIP]" + exit 77 +fi + +if /sbin/modprobe -q prime_numbers selftest=65536; then + /sbin/modprobe -q -r prime_numbers + echo "prime_numbers: ok" +else + echo "prime_numbers: [FAIL]" + exit 1 +fi