../svn-commit.tmp
[strongswan.git] / Source / charon / threads / prime_pool.c
1 /**
2 * @file prime_pool.c
3 *
4 * @brief Implementation of prime_pool_t.
5 *
6 */
7
8 /*
9 * Copyright (C) 2005 Jan Hutter, Martin Willi
10 * Hochschule fuer Technik Rapperswil
11 *
12 * This program is free software; you can redistribute it and/or modify it
13 * under the terms of the GNU General Public License as published by the
14 * Free Software Foundation; either version 2 of the License, or (at your
15 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
16 *
17 * This program is distributed in the hope that it will be useful, but
18 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
19 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 * for more details.
21 */
22
23 #include <pthread.h>
24
25 #include "prime_pool.h"
26
27 #include <daemon.h>
28 #include <utils/allocator.h>
29 #include <utils/linked_list.h>
30 #include <utils/randomizer.h>
31
32
33 typedef struct prime_list_t prime_list_t;
34
35 /**
36 * A prime_list_t contains prime values of a specific size.
37 */
38 struct prime_list_t {
39 /**
40 * Size of the stored primes .
41 */
42 size_t prime_size;
43
44 /**
45 * Is this much used prime_size ?
46 */
47 u_int32_t usage;
48
49 /**
50 * List of primes.
51 */
52 linked_list_t *primes;
53 };
54
55 typedef struct private_prime_pool_t private_prime_pool_t;
56
57 /**
58 * @brief Private data of prime_pool_t.
59 */
60 struct private_prime_pool_t {
61 /**
62 * Public part of the prime_pool_t object.
63 */
64 prime_pool_t public;
65
66 /**
67 * A list which contains a set of prime_list_t's.
68 */
69 linked_list_t *prime_lists;
70
71 /**
72 * prime generation is stopped if more than
73 * that primes of a kind are already generated.
74 */
75 int generation_limit;
76
77 /**
78 * Access to prime_lists is locked through this mutex.
79 */
80 pthread_mutex_t mutex;
81
82 /**
83 * If the queue is empty a thread has to wait
84 * This condvar is used to wake up such a thread.
85 */
86 pthread_cond_t condvar;
87
88 /**
89 * Prime generation thread.
90 */
91 pthread_t thread;
92
93 /**
94 * Logger instance for the prime_pool.
95 */
96 logger_t *logger;
97
98 /**
99 * Function for the prime thread, generate primes.
100 */
101 void (*generate_primes) (private_prime_pool_t *this);
102
103 /**
104 * Calculate a prime of requested size.
105 */
106 void (*compute_prime) (private_prime_pool_t *this, size_t prime_size, mpz_t *prime);
107 };
108
109
110 /**
111 * Implementation of prime_pool_t.get_count.
112 */
113 static int get_count(private_prime_pool_t *this, size_t prime_size)
114 {
115 int count = 0;
116 iterator_t *iterator;
117
118 pthread_mutex_lock(&(this->mutex));
119
120 iterator = this->prime_lists->create_iterator(this->prime_lists, TRUE);
121 while (iterator->has_next(iterator))
122 {
123 prime_list_t *prime_list;
124 iterator->current(iterator, (void*)&prime_list);
125 if (prime_list->prime_size == prime_size)
126 {
127 count = prime_list->primes->get_count(prime_list->primes);
128 break;
129 }
130 }
131 iterator->destroy(iterator);
132
133 pthread_mutex_unlock(&(this->mutex));
134 return count;
135 }
136
137 /**
138 * Implementation of prime_pool_t.get_prime.
139 */
140 static void get_prime(private_prime_pool_t *this, size_t prime_size, mpz_t *prime)
141 {
142 bool prime_found = FALSE;
143 iterator_t *iterator;
144 bool create_new_list = TRUE;
145
146 pthread_mutex_lock(&(this->mutex));
147
148 iterator = this->prime_lists->create_iterator(this->prime_lists, TRUE);
149 while (iterator->has_next(iterator))
150 {
151 prime_list_t *prime_list;
152 iterator->current(iterator, (void*)&prime_list);
153 /* decrease usage marker for every kind of prime */
154 prime_list->usage = max(prime_list->usage - 1, 0);
155 if (prime_list->prime_size == prime_size)
156 {
157 mpz_t *removed_prime;
158 create_new_list = FALSE;
159 /* this prime is well selling, increase usage marker by number of different prime sizes */
160 prime_list->usage += this->prime_lists->get_count(this->prime_lists);
161 if (prime_list->primes->remove_first(prime_list->primes, (void*)&removed_prime) == SUCCESS)
162 {
163 this->logger->log(this->logger, CONTROL|LEVEL2, "Thread removed a prime with size %d", prime_size);
164 mpz_init_set(*prime, *removed_prime);
165 mpz_clear(*removed_prime);
166 allocator_free(removed_prime);
167 prime_found = TRUE;
168 }
169 /* wake up prime thread, he may be sleeping */
170 pthread_cond_signal(&(this->condvar));
171 }
172 }
173 iterator->destroy(iterator);
174
175 if (create_new_list)
176 {
177 this->logger->log(this->logger, CONTROL|LEVEL1, "Creating a new list for primes with size %d", prime_size);
178 /* there is no list for this prime size, create one */
179 prime_list_t *prime_list;
180 prime_list = allocator_alloc_thing(prime_list_t);
181 prime_list->usage = 1;
182 prime_list->primes = linked_list_create();
183 prime_list->prime_size = prime_size;
184 this->prime_lists->insert_last(this->prime_lists, (void*)prime_list);
185 /* wake up prime thread, he may be sleeping */
186 pthread_cond_signal(&(this->condvar));
187 }
188
189 pthread_mutex_unlock(&(this->mutex));
190
191 if (!prime_found)
192 {
193 /* no prime found, create one ourself */
194 this->logger->log(this->logger, CONTROL|LEVEL2, "Caller didn't find a prime, generates on it's own.");
195 this->compute_prime(this, prime_size, prime);
196 }
197 }
198
199 /**
200 * Implementation of private_prime_pool_t.compute_prime.
201 */
202 void compute_prime(private_prime_pool_t *this, size_t prime_size, mpz_t *prime)
203 {
204 randomizer_t *randomizer;
205 chunk_t random_bytes;
206
207 randomizer = randomizer_create();
208 mpz_init(*prime);
209
210 do
211 {
212 /* TODO change to true random device ? */
213 randomizer->allocate_pseudo_random_bytes(randomizer, prime_size, &random_bytes);
214
215 /* make sure most significant bit is set */
216 random_bytes.ptr[0] = random_bytes.ptr[0] | 0x80;
217
218 /* convert chunk to mpz value */
219 mpz_import(*prime, random_bytes.len, 1, 1, 1, 0, random_bytes.ptr);
220
221 /* get next prime */
222 mpz_nextprime (*prime, *prime);
223
224 allocator_free(random_bytes.ptr);
225 }
226 /* check if it isnt too large */
227 while (((mpz_sizeinbase(*prime, 2) + 7) / 8) > prime_size);
228
229 randomizer->destroy(randomizer);
230 }
231
232 /**
233 * Implementation of private_prime_pool_t.generate_primes.
234 */
235 void generate_primes(private_prime_pool_t *this)
236 {
237 /* allow cancellation */
238 pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, NULL);
239
240 while (TRUE)
241 {
242 prime_list_t *selected_prime_list = NULL;
243 u_int32_t max_usage = 0;
244 iterator_t *iterator;
245 mpz_t *prime;
246
247
248 this->logger->log(this->logger, CONTROL|LEVEL2, "Finding most important prime size...");
249
250 pthread_mutex_lock(&(this->mutex));
251
252 /* get aprime to generate */
253 iterator = this->prime_lists->create_iterator(this->prime_lists, TRUE);
254 while (iterator->has_next(iterator))
255 {
256 prime_list_t *prime_list;
257 iterator->current(iterator, (void*)&prime_list);
258 this->logger->log(this->logger, CONTROL|LEVEL2, "Primes with size %d have usage %d, %d in list",
259 prime_list->prime_size, prime_list->usage,
260 prime_list->primes->get_count(prime_list->primes));
261 /* get the prime_size with the highest usage factor */
262 if (prime_list->usage > max_usage)
263 {
264 if (prime_list->primes->get_count(prime_list->primes) < this->generation_limit)
265 {
266 /* there is work to do */
267 max_usage = prime_list->usage;
268 selected_prime_list = prime_list;
269 }
270 }
271 }
272 iterator->destroy(iterator);
273
274 if (selected_prime_list == NULL)
275 {
276 this->logger->log(this->logger, CONTROL|LEVEL1, "Nothing to do, goint to sleep");
277 /* nothing to do. wait, while able to cancel */
278 pthread_cleanup_push((void(*)(void*))pthread_mutex_unlock, (void*)&(this->mutex));
279 pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, NULL);
280
281 pthread_cond_wait(&(this->condvar), &(this->mutex));
282
283 pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, NULL);
284 pthread_cleanup_pop(0);
285 }
286
287 pthread_mutex_unlock(&(this->mutex));
288
289 if (selected_prime_list != NULL)
290 {
291 this->logger->log(this->logger, CONTROL|LEVEL1, "Going to generate a prime with size %d",
292 selected_prime_list->prime_size);
293 /* generate the prime of requested size */
294 prime = allocator_alloc_thing(mpz_t);
295 compute_prime(this, selected_prime_list->prime_size, prime);
296
297 /* insert prime */
298 this->logger->log(this->logger, CONTROL|LEVEL2, "Prime generated, inserting in list");
299 pthread_mutex_lock(&(this->mutex));
300 selected_prime_list->primes->insert_last(selected_prime_list->primes, (void*)prime);
301 pthread_mutex_unlock(&(this->mutex));
302 }
303 /* abort if requested */
304 pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, NULL);
305 pthread_testcancel();
306 pthread_setcancelstate(PTHREAD_CANCEL_DISABLE, NULL);
307 }
308 }
309
310 /**
311 * Implementation of prime_pool_t.destroy.
312 */
313 static void destroy (private_prime_pool_t *this)
314 {
315 /* cancel thread, if available */
316 if (this->generation_limit > 0)
317 {
318 pthread_cancel(this->thread);
319 pthread_join(this->thread, NULL);
320 }
321 /* get every prime list */
322 while ((this->prime_lists->get_count(this->prime_lists) > 0))
323 {
324 prime_list_t *prime_list;
325
326 this->prime_lists->remove_last(this->prime_lists, (void*)&prime_list);
327
328 /* clear every mpz */
329 while (prime_list->primes->get_count(prime_list->primes) > 0)
330 {
331 mpz_t *prime;
332 prime_list->primes->remove_last(prime_list->primes, (void**)&prime);
333 mpz_clear(*prime);
334 allocator_free(prime);
335 }
336 prime_list->primes->destroy(prime_list->primes);
337 allocator_free(prime_list);
338 }
339 this->prime_lists->destroy(this->prime_lists);
340
341 pthread_mutex_destroy(&(this->mutex));
342 pthread_cond_destroy(&(this->condvar));
343
344 charon->logger_manager->destroy_logger(charon->logger_manager, this->logger);
345
346 allocator_free(this);
347 }
348
349 /*
350 * Documented in header,
351 */
352 prime_pool_t *prime_pool_create(int generation_limit)
353 {
354 private_prime_pool_t *this = allocator_alloc_thing(private_prime_pool_t);
355
356 /* public functions */
357 this->public.get_count = (int(*)(prime_pool_t*,size_t)) get_count;
358 this->public.get_prime = (void(*)(prime_pool_t*,size_t,mpz_t*)) get_prime;
359 this->public.destroy = (void(*)(prime_pool_t*)) destroy;
360
361 /* private members */
362 this->logger = charon->logger_manager->create_logger(charon->logger_manager, PRIME_POOL, NULL);
363 this->generate_primes = generate_primes;
364 this->compute_prime = compute_prime;
365 this->generation_limit = generation_limit;
366 this->prime_lists = linked_list_create();
367 pthread_mutex_init(&(this->mutex), NULL);
368 pthread_cond_init(&(this->condvar), NULL);
369
370
371 /* thread is only created if he has anything to do */
372 if (generation_limit > 0)
373 {
374 if (pthread_create(&(this->thread), NULL, (void*(*)(void*))this->generate_primes, this) != 0)
375 {
376 /* failed. we live with that problem, since getting primes is still possible */
377 this->logger->log(this->logger, ERROR, "Thread creation failed, working without thread!");
378 }
379 /* set priority */
380 else
381 {
382 struct sched_param param;
383 int policy;
384 /* get params first */
385 if (pthread_getschedparam(this->thread, &policy, &param) == 0)
386 {
387 param.sched_priority = sched_get_priority_min(policy);
388 if (pthread_setschedparam(this->thread, policy, &param) != 0)
389 {
390 /* failed to set priority */
391 this->logger->log(this->logger, ERROR, "Could not reduce priority of thread, running in default priority!");
392 }
393 }
394 else
395 {
396 /* failed to get priority */
397 this->logger->log(this->logger, ERROR, "Could not reduce priority of thread, running in default priority!");
398 }
399 }
400 }
401 return (&this->public);
402 }