lib/math/prime_numbers.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 #define pr_fmt(fmt) "prime numbers: " fmt
   3
   4 #include <linux/module.h>
   5 #include <linux/mutex.h>
   6 #include <linux/prime_numbers.h>
   7 #include <linux/slab.h>
   8
   9 struct primes {
  10         struct rcu_head rcu;
  11         unsigned long last, sz;
  12         unsigned long primes[];
  13 };
  14
  15 #if BITS_PER_LONG == 64
  16 static 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 == 32
  41 static 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 #else
  59 #error "unhandled BITS_PER_LONG"
  60 #endif
  61
  62 static DEFINE_MUTEX(lock);
  63 static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes);
  64
  65 static unsigned long selftest_max;
  66
  67 static 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
  80 static 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
  88 static 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
 107 static 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 p
 116          * such that n < p < 2n.
 117          *
 118          * http://mathworld.wolfram.com/BertrandsPostulate.html
 119          * https://en.wikipedia.org/wiki/Bertrand's_postulate
 120          */
 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 the
 139          * Sieve of Eratosthenes. The sieve is to remove all multiples of known
 140          * 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
 154 unlock:
 155         mutex_unlock(&lock);
 156         return true;
 157 }
 158
 159 static 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 number
 174  * @x: the starting point for searching to test
 175  *
 176  * A prime number is an integer greater than 1 that is only divisible by
 177  * itself and 1.  The set of prime numbers is computed using the Sieve of
 178  * Eratoshenes (on finding a prime, all multiples of that prime are removed
 179  * from the set) enabling a fast lookup of the next prime number larger than
 180  * @x. If the sieve fails (memory limitation), the search falls back to using
 181  * slow trial-divison, up to the value of ULONG_MAX (which is reported as the
 182  * final prime as a sentinel).
 183  *
 184  * Returns: the next prime number larger than @x
 185  */
 186 unsigned 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 }
 206 EXPORT_SYMBOL(next_prime_number);
 207
 208 /**
 209  * is_prime_number - test whether the given number is prime
 210  * @x: the number to test
 211  *
 212  * A prime number is an integer greater than 1 that is only divisible by
 213  * itself and 1. Internally a cache of prime numbers is kept (to speed up
 214  * searching for sequential primes, see next_prime_number()), but if the number
 215  * 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  */
 219 bool 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 }
 240 EXPORT_SYMBOL(is_prime_number);
 241
 242 static 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
 262 static 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
 293 err:
 294         dump_primes();
 295         return -EINVAL;
 296 }
 297
 298 static int __init primes_init(void)
 299 {
 300         return selftest(selftest_max);
 301 }
 302
 303 static void __exit primes_exit(void)
 304 {
 305         free_primes();
 306 }
 307
 308 module_init(primes_init);
 309 module_exit(primes_exit);
 310
 311 module_param_named(selftest, selftest_max, ulong, 0400);
 312
 313 MODULE_AUTHOR("Intel Corporation");
 314 MODULE_DESCRIPTION("Prime number library");
 315 MODULE_LICENSE("GPL");