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