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