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