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