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