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