1 // SPDX-License-Identifier: GPL-2.0-only 2 3 #include <linux/module.h> 4 #include <linux/mutex.h> 5 #include <linux/prime_numbers.h> 6 #include <linux/slab.h> 7 8 #include "prime_numbers_private.h" 9 10 #if BITS_PER_LONG == 64 11 static const struct primes small_primes = { 12 .last = 61, 13 .sz = 64, 14 .primes = { 15 BIT(2) | 16 BIT(3) | 17 BIT(5) | 18 BIT(7) | 19 BIT(11) | 20 BIT(13) | 21 BIT(17) | 22 BIT(19) | 23 BIT(23) | 24 BIT(29) | 25 BIT(31) | 26 BIT(37) | 27 BIT(41) | 28 BIT(43) | 29 BIT(47) | 30 BIT(53) | 31 BIT(59) | 32 BIT(61) 33 } 34 }; 35 #elif BITS_PER_LONG == 32 36 static const struct primes small_primes = { 37 .last = 31, 38 .sz = 32, 39 .primes = { 40 BIT(2) | 41 BIT(3) | 42 BIT(5) | 43 BIT(7) | 44 BIT(11) | 45 BIT(13) | 46 BIT(17) | 47 BIT(19) | 48 BIT(23) | 49 BIT(29) | 50 BIT(31) 51 } 52 }; 53 #else 54 #error "unhandled BITS_PER_LONG" 55 #endif 56 57 static DEFINE_MUTEX(lock); 58 static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes); 59 60 #if IS_ENABLED(CONFIG_PRIME_NUMBERS_KUNIT_TEST) 61 /* 62 * Calls the callback under RCU lock. The callback must not retain 63 * the primes pointer. 64 */ 65 void with_primes(void *ctx, primes_fn fn) 66 { 67 rcu_read_lock(); 68 fn(ctx, rcu_dereference(primes)); 69 rcu_read_unlock(); 70 } 71 EXPORT_SYMBOL(with_primes); 72 73 EXPORT_SYMBOL(slow_is_prime_number); 74 75 #else 76 static 77 #endif 78 bool slow_is_prime_number(unsigned long x) 79 { 80 unsigned long y = int_sqrt(x); 81 82 while (y > 1) { 83 if ((x % y) == 0) 84 break; 85 y--; 86 } 87 88 return y == 1; 89 } 90 91 static unsigned long slow_next_prime_number(unsigned long x) 92 { 93 while (x < ULONG_MAX && !slow_is_prime_number(++x)) 94 ; 95 96 return x; 97 } 98 99 static unsigned long clear_multiples(unsigned long x, 100 unsigned long *p, 101 unsigned long start, 102 unsigned long end) 103 { 104 unsigned long m; 105 106 m = 2 * x; 107 if (m < start) 108 m = roundup(start, x); 109 110 while (m < end) { 111 __clear_bit(m, p); 112 m += x; 113 } 114 115 return x; 116 } 117 118 static bool expand_to_next_prime(unsigned long x) 119 { 120 const struct primes *p; 121 struct primes *new; 122 unsigned long sz, y; 123 124 /* Betrand's Postulate (or Chebyshev's theorem) states that if n > 3, 125 * there is always at least one prime p between n and 2n - 2. 126 * Equivalently, if n > 1, then there is always at least one prime p 127 * such that n < p < 2n. 128 * 129 * http://mathworld.wolfram.com/BertrandsPostulate.html 130 * https://en.wikipedia.org/wiki/Bertrand's_postulate 131 */ 132 sz = 2 * x; 133 if (sz < x) 134 return false; 135 136 sz = round_up(sz, BITS_PER_LONG); 137 new = kmalloc(sizeof(*new) + bitmap_size(sz), 138 GFP_KERNEL | __GFP_NOWARN); 139 if (!new) 140 return false; 141 142 mutex_lock(&lock); 143 p = rcu_dereference_protected(primes, lockdep_is_held(&lock)); 144 if (x < p->last) { 145 kfree(new); 146 goto unlock; 147 } 148 149 /* Where memory permits, track the primes using the 150 * Sieve of Eratosthenes. The sieve is to remove all multiples of known 151 * primes from the set, what remains in the set is therefore prime. 152 */ 153 bitmap_fill(new->primes, sz); 154 bitmap_copy(new->primes, p->primes, p->sz); 155 for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1)) 156 new->last = clear_multiples(y, new->primes, p->sz, sz); 157 new->sz = sz; 158 159 BUG_ON(new->last <= x); 160 161 rcu_assign_pointer(primes, new); 162 if (p != &small_primes) 163 kfree_rcu((struct primes *)p, rcu); 164 165 unlock: 166 mutex_unlock(&lock); 167 return true; 168 } 169 170 static void free_primes(void) 171 { 172 const struct primes *p; 173 174 mutex_lock(&lock); 175 p = rcu_dereference_protected(primes, lockdep_is_held(&lock)); 176 if (p != &small_primes) { 177 rcu_assign_pointer(primes, &small_primes); 178 kfree_rcu((struct primes *)p, rcu); 179 } 180 mutex_unlock(&lock); 181 } 182 183 /** 184 * next_prime_number - return the next prime number 185 * @x: the starting point for searching to test 186 * 187 * A prime number is an integer greater than 1 that is only divisible by 188 * itself and 1. The set of prime numbers is computed using the Sieve of 189 * Eratoshenes (on finding a prime, all multiples of that prime are removed 190 * from the set) enabling a fast lookup of the next prime number larger than 191 * @x. If the sieve fails (memory limitation), the search falls back to using 192 * slow trial-divison, up to the value of ULONG_MAX (which is reported as the 193 * final prime as a sentinel). 194 * 195 * Returns: the next prime number larger than @x 196 */ 197 unsigned long next_prime_number(unsigned long x) 198 { 199 const struct primes *p; 200 201 rcu_read_lock(); 202 p = rcu_dereference(primes); 203 while (x >= p->last) { 204 rcu_read_unlock(); 205 206 if (!expand_to_next_prime(x)) 207 return slow_next_prime_number(x); 208 209 rcu_read_lock(); 210 p = rcu_dereference(primes); 211 } 212 x = find_next_bit(p->primes, p->last, x + 1); 213 rcu_read_unlock(); 214 215 return x; 216 } 217 EXPORT_SYMBOL(next_prime_number); 218 219 /** 220 * is_prime_number - test whether the given number is prime 221 * @x: the number to test 222 * 223 * A prime number is an integer greater than 1 that is only divisible by 224 * itself and 1. Internally a cache of prime numbers is kept (to speed up 225 * searching for sequential primes, see next_prime_number()), but if the number 226 * falls outside of that cache, its primality is tested using trial-divison. 227 * 228 * Returns: true if @x is prime, false for composite numbers. 229 */ 230 bool is_prime_number(unsigned long x) 231 { 232 const struct primes *p; 233 bool result; 234 235 rcu_read_lock(); 236 p = rcu_dereference(primes); 237 while (x >= p->sz) { 238 rcu_read_unlock(); 239 240 if (!expand_to_next_prime(x)) 241 return slow_is_prime_number(x); 242 243 rcu_read_lock(); 244 p = rcu_dereference(primes); 245 } 246 result = test_bit(x, p->primes); 247 rcu_read_unlock(); 248 249 return result; 250 } 251 EXPORT_SYMBOL(is_prime_number); 252 253 static void __exit primes_exit(void) 254 { 255 free_primes(); 256 } 257 258 module_exit(primes_exit); 259 260 MODULE_AUTHOR("Intel Corporation"); 261 MODULE_DESCRIPTION("Prime number library"); 262 MODULE_LICENSE("GPL"); 263