1 | #define pr_fmt(fmt) "prime numbers: " fmt "\n" |
---|---|

2 | |

3 | #include <linux/module.h> |

4 | #include <linux/mutex.h> |

5 | #include <linux/prime_numbers.h> |

6 | #include <linux/slab.h> |

7 | |

8 | #define bitmap_size(nbits) (BITS_TO_LONGS(nbits) * sizeof(unsigned long)) |

9 | |

10 | struct primes { |

11 | struct rcu_head rcu; |

12 | unsigned long last, sz; |

13 | unsigned long primes[]; |

14 | }; |

15 | |

16 | #if BITS_PER_LONG == 64 |

17 | static const struct primes small_primes = { |

18 | .last = 61, |

19 | .sz = 64, |

20 | .primes = { |

21 | BIT(2) | |

22 | BIT(3) | |

23 | BIT(5) | |

24 | BIT(7) | |

25 | BIT(11) | |

26 | BIT(13) | |

27 | BIT(17) | |

28 | BIT(19) | |

29 | BIT(23) | |

30 | BIT(29) | |

31 | BIT(31) | |

32 | BIT(37) | |

33 | BIT(41) | |

34 | BIT(43) | |

35 | BIT(47) | |

36 | BIT(53) | |

37 | BIT(59) | |

38 | BIT(61) |

39 | } |

40 | }; |

41 | #elif BITS_PER_LONG == 32 |

42 | static const struct primes small_primes = { |

43 | .last = 31, |

44 | .sz = 32, |

45 | .primes = { |

46 | BIT(2) | |

47 | BIT(3) | |

48 | BIT(5) | |

49 | BIT(7) | |

50 | BIT(11) | |

51 | BIT(13) | |

52 | BIT(17) | |

53 | BIT(19) | |

54 | BIT(23) | |

55 | BIT(29) | |

56 | BIT(31) |

57 | } |

58 | }; |

59 | #else |

60 | #error "unhandled BITS_PER_LONG" |

61 | #endif |

62 | |

63 | static DEFINE_MUTEX(lock); |

64 | static const struct primes __rcu *primes = RCU_INITIALIZER(&small_primes); |

65 | |

66 | static unsigned long selftest_max; |

67 | |

68 | static bool slow_is_prime_number(unsigned long x) |

69 | { |

70 | unsigned long y = int_sqrt(x); |

71 | |

72 | while (y > 1) { |

73 | if ((x % y) == 0) |

74 | break; |

75 | y--; |

76 | } |

77 | |

78 | return y == 1; |

79 | } |

80 | |

81 | static unsigned long slow_next_prime_number(unsigned long x) |

82 | { |

83 | while (x < ULONG_MAX && !slow_is_prime_number(++x)) |

84 | ; |

85 | |

86 | return x; |

87 | } |

88 | |

89 | static unsigned long clear_multiples(unsigned long x, |

90 | unsigned long *p, |

91 | unsigned long start, |

92 | unsigned long end) |

93 | { |

94 | unsigned long m; |

95 | |

96 | m = 2 * x; |

97 | if (m < start) |

98 | m = roundup(start, x); |

99 | |

100 | while (m < end) { |

101 | __clear_bit(m, p); |

102 | m += x; |

103 | } |

104 | |

105 | return x; |

106 | } |

107 | |

108 | static bool expand_to_next_prime(unsigned long x) |

109 | { |

110 | const struct primes *p; |

111 | struct primes *new; |

112 | unsigned long sz, y; |

113 | |

114 | /* Betrand's Postulate (or Chebyshev's theorem) states that if n > 3, |

115 | * there is always at least one prime p between n and 2n - 2. |

116 | * Equivalently, if n > 1, then there is always at least one prime p |

117 | * such that n < p < 2n. |

118 | * |

119 | * http://mathworld.wolfram.com/BertrandsPostulate.html |

120 | * https://en.wikipedia.org/wiki/Bertrand's_postulate |

121 | */ |

122 | sz = 2 * x; |

123 | if (sz < x) |

124 | return false; |

125 | |

126 | sz = round_up(sz, BITS_PER_LONG); |

127 | new = kmalloc(sizeof(*new) + bitmap_size(sz), |

128 | GFP_KERNEL | __GFP_NOWARN); |

129 | if (!new) |

130 | return false; |

131 | |

132 | mutex_lock(&lock); |

133 | p = rcu_dereference_protected(primes, lockdep_is_held(&lock)); |

134 | if (x < p->last) { |

135 | kfree(new); |

136 | goto unlock; |

137 | } |

138 | |

139 | /* Where memory permits, track the primes using the |

140 | * Sieve of Eratosthenes. The sieve is to remove all multiples of known |

141 | * primes from the set, what remains in the set is therefore prime. |

142 | */ |

143 | bitmap_fill(new->primes, sz); |

144 | bitmap_copy(new->primes, p->primes, p->sz); |

145 | for (y = 2UL; y < sz; y = find_next_bit(new->primes, sz, y + 1)) |

146 | new->last = clear_multiples(y, new->primes, p->sz, sz); |

147 | new->sz = sz; |

148 | |

149 | BUG_ON(new->last <= x); |

150 | |

151 | rcu_assign_pointer(primes, new); |

152 | if (p != &small_primes) |

153 | kfree_rcu((struct primes *)p, rcu); |

154 | |

155 | unlock: |

156 | mutex_unlock(&lock); |

157 | return true; |

158 | } |

159 | |

160 | static void free_primes(void) |

161 | { |

162 | const struct primes *p; |

163 | |

164 | mutex_lock(&lock); |

165 | p = rcu_dereference_protected(primes, lockdep_is_held(&lock)); |

166 | if (p != &small_primes) { |

167 | rcu_assign_pointer(primes, &small_primes); |

168 | kfree_rcu((struct primes *)p, rcu); |

169 | } |

170 | mutex_unlock(&lock); |

171 | } |

172 | |

173 | /** |

174 | * next_prime_number - return the next prime number |

175 | * @x: the starting point for searching to test |

176 | * |

177 | * A prime number is an integer greater than 1 that is only divisible by |

178 | * itself and 1. The set of prime numbers is computed using the Sieve of |

179 | * Eratoshenes (on finding a prime, all multiples of that prime are removed |

180 | * from the set) enabling a fast lookup of the next prime number larger than |

181 | * @x. If the sieve fails (memory limitation), the search falls back to using |

182 | * slow trial-divison, up to the value of ULONG_MAX (which is reported as the |

183 | * final prime as a sentinel). |

184 | * |

185 | * Returns: the next prime number larger than @x |

186 | */ |

187 | unsigned long next_prime_number(unsigned long x) |

188 | { |

189 | const struct primes *p; |

190 | |

191 | rcu_read_lock(); |

192 | p = rcu_dereference(primes); |

193 | while (x >= p->last) { |

194 | rcu_read_unlock(); |

195 | |

196 | if (!expand_to_next_prime(x)) |

197 | return slow_next_prime_number(x); |

198 | |

199 | rcu_read_lock(); |

200 | p = rcu_dereference(primes); |

201 | } |

202 | x = find_next_bit(p->primes, p->last, x + 1); |

203 | rcu_read_unlock(); |

204 | |

205 | return x; |

206 | } |

207 | EXPORT_SYMBOL(next_prime_number); |

208 | |

209 | /** |

210 | * is_prime_number - test whether the given number is prime |

211 | * @x: the number to test |

212 | * |

213 | * A prime number is an integer greater than 1 that is only divisible by |

214 | * itself and 1. Internally a cache of prime numbers is kept (to speed up |

215 | * searching for sequential primes, see next_prime_number()), but if the number |

216 | * falls outside of that cache, its primality is tested using trial-divison. |

217 | * |

218 | * Returns: true if @x is prime, false for composite numbers. |

219 | */ |

220 | bool is_prime_number(unsigned long x) |

221 | { |

222 | const struct primes *p; |

223 | bool result; |

224 | |

225 | rcu_read_lock(); |

226 | p = rcu_dereference(primes); |

227 | while (x >= p->sz) { |

228 | rcu_read_unlock(); |

229 | |

230 | if (!expand_to_next_prime(x)) |

231 | return slow_is_prime_number(x); |

232 | |

233 | rcu_read_lock(); |

234 | p = rcu_dereference(primes); |

235 | } |

236 | result = test_bit(x, p->primes); |

237 | rcu_read_unlock(); |

238 | |

239 | return result; |

240 | } |

241 | EXPORT_SYMBOL(is_prime_number); |

242 | |

243 | static void dump_primes(void) |

244 | { |

245 | const struct primes *p; |

246 | char *buf; |

247 | |

248 | buf = kmalloc(PAGE_SIZE, GFP_KERNEL); |

249 | |

250 | rcu_read_lock(); |

251 | p = rcu_dereference(primes); |

252 | |

253 | if (buf) |

254 | bitmap_print_to_pagebuf(true, buf, p->primes, p->sz); |

255 | pr_info("primes.{last=%lu, .sz=%lu, .primes[]=...x%lx} = %s", |

256 | p->last, p->sz, p->primes[BITS_TO_LONGS(p->sz) - 1], buf); |

257 | |

258 | rcu_read_unlock(); |

259 | |

260 | kfree(buf); |

261 | } |

262 | |

263 | static int selftest(unsigned long max) |

264 | { |

265 | unsigned long x, last; |

266 | |

267 | if (!max) |

268 | return 0; |

269 | |

270 | for (last = 0, x = 2; x < max; x++) { |

271 | bool slow = slow_is_prime_number(x); |

272 | bool fast = is_prime_number(x); |

273 | |

274 | if (slow != fast) { |

275 | pr_err("inconsistent result for is-prime(%lu): slow=%s, fast=%s!", |

276 | x, slow ? "yes": "no", fast ? "yes": "no"); |

277 | goto err; |

278 | } |

279 | |

280 | if (!slow) |

281 | continue; |

282 | |

283 | if (next_prime_number(last) != x) { |

284 | pr_err("incorrect result for next-prime(%lu): expected %lu, got %lu", |

285 | last, x, next_prime_number(last)); |

286 | goto err; |

287 | } |

288 | last = x; |

289 | } |

290 | |

291 | pr_info("selftest(%lu) passed, last prime was %lu", x, last); |

292 | return 0; |

293 | |

294 | err: |

295 | dump_primes(); |

296 | return -EINVAL; |

297 | } |

298 | |

299 | static int __init primes_init(void) |

300 | { |

301 | return selftest(selftest_max); |

302 | } |

303 | |

304 | static void __exit primes_exit(void) |

305 | { |

306 | free_primes(); |

307 | } |

308 | |

309 | module_init(primes_init); |

310 | module_exit(primes_exit); |

311 | |

312 | module_param_named(selftest, selftest_max, ulong, 0400); |

313 | |

314 | MODULE_AUTHOR("Intel Corporation"); |

315 | MODULE_LICENSE("GPL"); |

316 |