^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) #define pr_fmt(fmt) "prime numbers: " fmt
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) #include <linux/module.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) #include <linux/mutex.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) #include <linux/prime_numbers.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) #define bitmap_size(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) struct primes {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) struct rcu_head rcu;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) unsigned long last, sz;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) unsigned long primes[];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) #if BITS_PER_LONG == 64
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) static const struct primes small_primes = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) .last = 61,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) .sz = 64,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) .primes = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) BIT(2) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) BIT(3) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) BIT(5) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) BIT(7) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) BIT(11) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) BIT(13) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) BIT(17) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) BIT(19) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) BIT(23) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) BIT(29) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) BIT(31) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) BIT(37) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) BIT(41) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) BIT(43) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) BIT(47) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) BIT(53) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) BIT(59) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) BIT(61)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) #elif BITS_PER_LONG == 32
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) static const struct primes small_primes = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) .last = 31,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) .sz = 32,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) .primes = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) BIT(2) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) BIT(3) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) BIT(5) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) BIT(7) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) BIT(11) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) BIT(13) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) BIT(17) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) BIT(19) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) BIT(23) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) BIT(29) |
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) BIT(31)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) #else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) #error "unhandled BITS_PER_LONG"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) static DEFINE_MUTEX(lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) static unsigned long selftest_max;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) static bool slow_is_prime_number(unsigned long x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) unsigned long y = int_sqrt(x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) while (y > 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) if ((x % y) == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) y--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) return y == 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) static unsigned long slow_next_prime_number(unsigned long x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) while (x < ULONG_MAX && !slow_is_prime_number(++x))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) ;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) return x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) static unsigned long clear_multiples(unsigned long x,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) unsigned long *p,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) unsigned long start,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) unsigned long end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) unsigned long m;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) m = 2 * x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) if (m < start)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) m = roundup(start, x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) while (m < end) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) __clear_bit(m, p);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) m += x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) return x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) static bool expand_to_next_prime(unsigned long x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) const struct primes *p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) struct primes *new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) unsigned long sz, y;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) /* Betrand's Postulate (or Chebyshev's theorem) states that if n > 3,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) * there is always at least one prime p between n and 2n - 2.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) * Equivalently, if n > 1, then there is always at least one prime p
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) * such that n < p < 2n.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) * http://mathworld.wolfram.com/BertrandsPostulate.html
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) * https://en.wikipedia.org/wiki/Bertrand's_postulate
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) sz = 2 * x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) if (sz < x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) sz = round_up(sz, BITS_PER_LONG);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) new = kmalloc(sizeof(*new) + bitmap_size(sz),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) GFP_KERNEL | __GFP_NOWARN);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) if (!new)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) return false;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) mutex_lock(&lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) if (x < p->last) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) kfree(new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) goto unlock;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) /* Where memory permits, track the primes using the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) * Sieve of Eratosthenes. The sieve is to remove all multiples of known
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) * primes from the set, what remains in the set is therefore prime.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) bitmap_fill(new->primes, sz);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) bitmap_copy(new->primes, p->primes, p->sz);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) new->last = clear_multiples(y, new->primes, p->sz, sz);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) new->sz = sz;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) BUG_ON(new->last <= x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) rcu_assign_pointer(primes, new);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) if (p != &small_primes)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) kfree_rcu((struct primes *)p, rcu);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) unlock:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) mutex_unlock(&lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) return true;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) static void free_primes(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) const struct primes *p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) mutex_lock(&lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) p = rcu_dereference_protected(primes, lockdep_is_held(&lock));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) if (p != &small_primes) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) rcu_assign_pointer(primes, &small_primes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) kfree_rcu((struct primes *)p, rcu);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) mutex_unlock(&lock);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) * next_prime_number - return the next prime number
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) * @x: the starting point for searching to test
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) * A prime number is an integer greater than 1 that is only divisible by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) * itself and 1. The set of prime numbers is computed using the Sieve of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) * Eratoshenes (on finding a prime, all multiples of that prime are removed
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) * from the set) enabling a fast lookup of the next prime number larger than
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) * @x. If the sieve fails (memory limitation), the search falls back to using
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) * slow trial-divison, up to the value of ULONG_MAX (which is reported as the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) * final prime as a sentinel).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) * Returns: the next prime number larger than @x
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) unsigned long next_prime_number(unsigned long x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) const struct primes *p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) rcu_read_lock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) p = rcu_dereference(primes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) while (x >= p->last) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) if (!expand_to_next_prime(x))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) return slow_next_prime_number(x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) rcu_read_lock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) p = rcu_dereference(primes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) x = find_next_bit(p->primes, p->last, x + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) return x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) EXPORT_SYMBOL(next_prime_number);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) * is_prime_number - test whether the given number is prime
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) * @x: the number to test
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) * A prime number is an integer greater than 1 that is only divisible by
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) * itself and 1. Internally a cache of prime numbers is kept (to speed up
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) * searching for sequential primes, see next_prime_number()), but if the number
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) * falls outside of that cache, its primality is tested using trial-divison.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) * Returns: true if @x is prime, false for composite numbers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) bool is_prime_number(unsigned long x)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) const struct primes *p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) bool result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) rcu_read_lock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) p = rcu_dereference(primes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) while (x >= p->sz) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) if (!expand_to_next_prime(x))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) return slow_is_prime_number(x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) rcu_read_lock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) p = rcu_dereference(primes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) result = test_bit(x, p->primes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) return result;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) EXPORT_SYMBOL(is_prime_number);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) static void dump_primes(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) const struct primes *p;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) char *buf;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) rcu_read_lock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) p = rcu_dereference(primes);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) if (buf)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) bitmap_print_to_pagebuf(true, buf, p->primes, p->sz);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) pr_info("primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) rcu_read_unlock();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) kfree(buf);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) static int selftest(unsigned long max)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) unsigned long x, last;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) if (!max)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) for (last = 0, x = 2; x < max; x++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) bool slow = slow_is_prime_number(x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) bool fast = is_prime_number(x);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) if (slow != fast) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) pr_err("inconsistent result for is-prime(%lu): slow=%s, fast=%s!\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) x, slow ? "yes" : "no", fast ? "yes" : "no");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) goto err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) if (!slow)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) if (next_prime_number(last) != x) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) pr_err("incorrect result for next-prime(%lu): expected %lu, got %lu\n",
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) last, x, next_prime_number(last));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) goto err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) last = x;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) pr_info("%s(%lu) passed, last prime was %lu\n", __func__, x, last);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) err:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) dump_primes();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) return -EINVAL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) static int __init primes_init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) return selftest(selftest_max);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) static void __exit primes_exit(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) free_primes();
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) module_init(primes_init);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) module_exit(primes_exit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) module_param_named(selftest, selftest_max, ulong, 0400);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) MODULE_AUTHOR("Intel Corporation");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) MODULE_LICENSE("GPL");
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags