prime_numbers.c

  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
 11static 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
 36static 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
 57static DEFINE_MUTEX(lock);
 58static 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 */
 65void with_primes(void *ctx, primes_fn fn)
 66{
 67	rcu_read_lock();
 68	fn(ctx, rcu_dereference(primes));
 69	rcu_read_unlock();
 70}
 71EXPORT_SYMBOL(with_primes);
 72
 73EXPORT_SYMBOL(slow_is_prime_number);
 74
 75#else
 76static
 77#endif
 78bool 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
 91static 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
 99static 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
118static 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
165unlock:
166	mutex_unlock(&lock);
167	return true;
168}
169
170static 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 */
197unsigned 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}
217EXPORT_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 */
230bool 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}
251EXPORT_SYMBOL(is_prime_number);
252
253static void __exit primes_exit(void)
254{
255	free_primes();
256}
257
258module_exit(primes_exit);
259
260MODULE_AUTHOR("Intel Corporation");
261MODULE_DESCRIPTION("Prime number library");
262MODULE_LICENSE("GPL");