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