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