Fixed in-place update of cached base and delta CRLs
[strongswan.git] / src / libstrongswan / credentials / sets / cert_cache.c
1 /*
2 * Copyright (C) 2008 Martin Willi
3 * Copyright (C) 2016 Andreas Steffen
4 * HSR Hochschule fuer Technik Rapperswil
5 *
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the
8 * Free Software Foundation; either version 2 of the License, or (at your
9 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * for more details.
15 */
16
17 #include "cert_cache.h"
18
19 #include <time.h>
20
21 #include <library.h>
22 #include <threading/rwlock.h>
23 #include <collections/linked_list.h>
24 #include <credentials/certificates/crl.h>
25
26 /** cache size, a power of 2 for fast modulo */
27 #define CACHE_SIZE 32
28
29 /** attempts to acquire a cache lock */
30 #define REPLACE_TRIES 5
31
32 typedef struct private_cert_cache_t private_cert_cache_t;
33 typedef struct relation_t relation_t;
34
35 /**
36 * A trusted relation between subject and issuer
37 */
38 struct relation_t {
39
40 /**
41 * subject of this relation
42 */
43 certificate_t *subject;
44
45 /**
46 * issuer of this relation
47 */
48 certificate_t *issuer;
49
50 /**
51 * Signature scheme used to sign this relation
52 */
53 signature_scheme_t scheme;
54
55 /**
56 * Cache hits
57 */
58 u_int hits;
59
60 /**
61 * Lock for this relation
62 */
63 rwlock_t *lock;
64 };
65
66 /**
67 * private data of cert_cache
68 */
69 struct private_cert_cache_t {
70
71 /**
72 * public functions
73 */
74 cert_cache_t public;
75
76 /**
77 * array of trusted subject-issuer relations
78 */
79 relation_t relations[CACHE_SIZE];
80 };
81
82 /**
83 * Cache relation in a free slot/replace an other
84 */
85 static void cache(private_cert_cache_t *this,
86 certificate_t *subject, certificate_t *issuer,
87 signature_scheme_t scheme)
88 {
89 relation_t *rel;
90 int i, offset, try;
91 u_int total_hits = 0;
92
93 /* cache a CRL by replacing a previous CRL cache entry if present */
94 if (subject->get_type(subject) == CERT_X509_CRL)
95 {
96 crl_t *crl, *cached_crl;
97
98 /* cache a delta CRL ? */
99 crl = (crl_t*)subject;
100
101 for (i = 0; i < CACHE_SIZE; i++)
102 {
103 rel = &this->relations[i];
104
105 if (rel->subject &&
106 rel->subject->get_type(rel->subject) == CERT_X509_CRL &&
107 rel->lock->try_write_lock(rel->lock))
108 {
109 /* double-check having lock */
110 if (rel->subject->get_type(rel->subject) == CERT_X509_CRL &&
111 rel->issuer->equals(rel->issuer, issuer))
112 {
113 cached_crl = (crl_t*)rel->subject;
114
115 if (cached_crl->is_delta_crl(cached_crl, NULL) ==
116 crl->is_delta_crl(crl, NULL) &&
117 crl_is_newer(crl, cached_crl))
118 {
119 rel->subject->destroy(rel->subject);
120 rel->subject = subject->get_ref(subject);
121 rel->scheme = scheme;
122 return rel->lock->unlock(rel->lock);
123 }
124 }
125 rel->lock->unlock(rel->lock);
126 }
127 }
128 }
129
130 /* check for a unused relation slot first */
131 for (i = 0; i < CACHE_SIZE; i++)
132 {
133 rel = &this->relations[i];
134
135 if (!rel->subject && rel->lock->try_write_lock(rel->lock))
136 {
137 /* double-check having lock */
138 if (!rel->subject)
139 {
140 rel->subject = subject->get_ref(subject);
141 rel->issuer = issuer->get_ref(issuer);
142 rel->scheme = scheme;
143 return rel->lock->unlock(rel->lock);
144 }
145 rel->lock->unlock(rel->lock);
146 }
147 total_hits += rel->hits;
148 }
149 /* run several attempts to replace a random slot, never block. */
150 for (try = 0; try < REPLACE_TRIES; try++)
151 {
152 /* replace a random relation */
153 offset = random();
154 for (i = 0; i < CACHE_SIZE; i++)
155 {
156 rel = &this->relations[(i + offset) % CACHE_SIZE];
157
158 if (rel->hits > total_hits / CACHE_SIZE)
159 { /* skip often used slots */
160 continue;
161 }
162 if (rel->lock->try_write_lock(rel->lock))
163 {
164 if (rel->subject)
165 {
166 rel->subject->destroy(rel->subject);
167 rel->issuer->destroy(rel->issuer);
168 }
169 rel->subject = subject->get_ref(subject);
170 rel->issuer = issuer->get_ref(issuer);
171 rel->scheme = scheme;
172 rel->hits = 0;
173 return rel->lock->unlock(rel->lock);
174 }
175 }
176 /* give other threads a chance to release locks */
177 sched_yield();
178 }
179 }
180
181 METHOD(cert_cache_t, issued_by, bool,
182 private_cert_cache_t *this, certificate_t *subject, certificate_t *issuer,
183 signature_scheme_t *schemep)
184 {
185 certificate_t *cached_issuer = NULL;
186 relation_t *found = NULL, *current;
187 signature_scheme_t scheme;
188 int i;
189
190 for (i = 0; i < CACHE_SIZE; i++)
191 {
192 current = &this->relations[i];
193
194 current->lock->read_lock(current->lock);
195 if (current->subject)
196 {
197 if (issuer->equals(issuer, current->issuer))
198 {
199 if (subject->equals(subject, current->subject))
200 {
201 current->hits++;
202 found = current;
203 if (schemep)
204 {
205 *schemep = current->scheme;
206 }
207 }
208 else if (!cached_issuer)
209 {
210 cached_issuer = current->issuer->get_ref(current->issuer);
211 }
212 }
213 }
214 current->lock->unlock(current->lock);
215 if (found)
216 {
217 DESTROY_IF(cached_issuer);
218 return TRUE;
219 }
220 }
221 if (subject->issued_by(subject, issuer, &scheme))
222 {
223 cache(this, subject, cached_issuer ?: issuer, scheme);
224 if (schemep)
225 {
226 *schemep = scheme;
227 }
228 DESTROY_IF(cached_issuer);
229 return TRUE;
230 }
231 DESTROY_IF(cached_issuer);
232 return FALSE;
233 }
234
235 /**
236 * certificate enumerator implemenation
237 */
238 typedef struct {
239 /** implements enumerator_t interface */
240 enumerator_t public;
241 /** type of requested certificate */
242 certificate_type_t cert;
243 /** type of requested key */
244 key_type_t key;
245 /** ID to get a cert for */
246 identification_t *id;
247 /** cache */
248 relation_t *relations;
249 /** current position in array cache */
250 int index;
251 /** currently locked relation */
252 int locked;
253 } cert_enumerator_t;
254
255 /**
256 * filter function for certs enumerator
257 */
258 static bool cert_enumerate(cert_enumerator_t *this, certificate_t **out)
259 {
260 public_key_t *public;
261 relation_t *rel;
262
263 if (this->locked >= 0)
264 {
265 rel = &this->relations[this->locked];
266 rel->lock->unlock(rel->lock);
267 this->locked = -1;
268 }
269
270 while (++this->index < CACHE_SIZE)
271 {
272 rel = &this->relations[this->index];
273 rel->lock->read_lock(rel->lock);
274 this->locked = this->index;
275 if (rel->subject)
276 {
277 /* CRL lookup is done using issuer/authkeyidentifier */
278 if (this->key == KEY_ANY && this->id &&
279 (this->cert == CERT_ANY || this->cert == CERT_X509_CRL) &&
280 rel->subject->get_type(rel->subject) == CERT_X509_CRL &&
281 rel->subject->has_issuer(rel->subject, this->id))
282 {
283 *out = rel->subject;
284 return TRUE;
285 }
286 if ((this->cert == CERT_ANY ||
287 rel->subject->get_type(rel->subject) == this->cert) &&
288 (!this->id || rel->subject->has_subject(rel->subject, this->id)))
289 {
290 if (this->key == KEY_ANY)
291 {
292 *out = rel->subject;
293 return TRUE;
294 }
295 public = rel->subject->get_public_key(rel->subject);
296 if (public)
297 {
298 if (public->get_type(public) == this->key)
299 {
300 public->destroy(public);
301 *out = rel->subject;
302 return TRUE;
303 }
304 public->destroy(public);
305 }
306 }
307 }
308 this->locked = -1;
309 rel->lock->unlock(rel->lock);
310 }
311 return FALSE;
312 }
313
314 /**
315 * clean up enumeration data
316 */
317 static void cert_enumerator_destroy(cert_enumerator_t *this)
318 {
319 relation_t *rel;
320
321 if (this->locked >= 0)
322 {
323 rel = &this->relations[this->locked];
324 rel->lock->unlock(rel->lock);
325 }
326 free(this);
327 }
328
329 METHOD(credential_set_t, create_enumerator, enumerator_t*,
330 private_cert_cache_t *this, certificate_type_t cert, key_type_t key,
331 identification_t *id, bool trusted)
332 {
333 cert_enumerator_t *enumerator;
334
335 if (trusted)
336 {
337 return NULL;
338 }
339 enumerator = malloc_thing(cert_enumerator_t);
340 enumerator->public.enumerate = (void*)cert_enumerate;
341 enumerator->public.destroy = (void*)cert_enumerator_destroy;
342 enumerator->cert = cert;
343 enumerator->key = key;
344 enumerator->id = id;
345 enumerator->relations = this->relations;
346 enumerator->index = -1;
347 enumerator->locked = -1;
348
349 return &enumerator->public;
350 }
351
352 METHOD(cert_cache_t, flush, void,
353 private_cert_cache_t *this, certificate_type_t type)
354 {
355 relation_t *rel;
356 int i;
357
358 for (i = 0; i < CACHE_SIZE; i++)
359 {
360 rel = &this->relations[i];
361 if (!rel->subject)
362 {
363 continue;
364 }
365 /* check with cheap read lock first */
366 if (type != CERT_ANY)
367 {
368 rel->lock->read_lock(rel->lock);
369 if (!rel->subject || type != rel->subject->get_type(rel->subject))
370 {
371 rel->lock->unlock(rel->lock);
372 continue;
373 }
374 rel->lock->unlock(rel->lock);
375 }
376 /* double check in write lock */
377 rel->lock->write_lock(rel->lock);
378 if (rel->subject)
379 {
380 if (type == CERT_ANY || type == rel->subject->get_type(rel->subject))
381 {
382 rel->subject->destroy(rel->subject);
383 rel->issuer->destroy(rel->issuer);
384 rel->subject = NULL;
385 rel->issuer = NULL;
386 rel->hits = 0;
387 }
388 }
389 rel->lock->unlock(rel->lock);
390 }
391 }
392
393 METHOD(cert_cache_t, destroy, void,
394 private_cert_cache_t *this)
395 {
396 relation_t *rel;
397 int i;
398
399 for (i = 0; i < CACHE_SIZE; i++)
400 {
401 rel = &this->relations[i];
402 if (rel->subject)
403 {
404 rel->subject->destroy(rel->subject);
405 rel->issuer->destroy(rel->issuer);
406 }
407 rel->lock->destroy(rel->lock);
408 }
409 free(this);
410 }
411
412 /*
413 * see header file
414 */
415 cert_cache_t *cert_cache_create()
416 {
417 private_cert_cache_t *this;
418 int i;
419
420 INIT(this,
421 .public = {
422 .set = {
423 .create_cert_enumerator = _create_enumerator,
424 .create_private_enumerator = (void*)return_null,
425 .create_shared_enumerator = (void*)return_null,
426 .create_cdp_enumerator = (void*)return_null,
427 .cache_cert = (void*)nop,
428 },
429 .issued_by = _issued_by,
430 .flush = _flush,
431 .destroy = _destroy,
432 },
433 );
434
435 for (i = 0; i < CACHE_SIZE; i++)
436 {
437 this->relations[i].subject = NULL;
438 this->relations[i].issuer = NULL;
439 this->relations[i].hits = 0;
440 this->relations[i].lock = rwlock_create(RWLOCK_TYPE_DEFAULT);
441 }
442
443 return &this->public;
444 }