mem-pool: Fix potential memory leak and lost leases when reassigning leases
[strongswan.git] / src / libhydra / attributes / mem_pool.c
1 /*
2 * Copyright (C) 2010 Tobias Brunner
3 * Copyright (C) 2008-2010 Martin Willi
4 * 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 "mem_pool.h"
18
19 #include <library.h>
20 #include <hydra.h>
21 #include <utils/debug.h>
22 #include <collections/hashtable.h>
23 #include <collections/array.h>
24 #include <threading/mutex.h>
25
26 #define POOL_LIMIT (sizeof(u_int)*8 - 1)
27
28 typedef struct private_mem_pool_t private_mem_pool_t;
29
30 /**
31 * private data of mem_pool_t
32 */
33 struct private_mem_pool_t {
34 /**
35 * public interface
36 */
37 mem_pool_t public;
38
39 /**
40 * name of the pool
41 */
42 char *name;
43
44 /**
45 * base address of the pool
46 */
47 host_t *base;
48
49 /**
50 * whether base is the network id of the subnet on which the pool is based
51 */
52 bool base_is_network_id;
53
54 /**
55 * size of the pool
56 */
57 u_int size;
58
59 /**
60 * next unused address
61 */
62 u_int unused;
63
64 /**
65 * lease hashtable [identity => entry]
66 */
67 hashtable_t *leases;
68
69 /**
70 * lock to safely access the pool
71 */
72 mutex_t *mutex;
73
74 /**
75 * Do we reassign online leases to the same identity, if requested?
76 */
77 bool reassign_online;
78 };
79
80 /**
81 * Lease entry.
82 */
83 typedef struct {
84 /* identitiy reference */
85 identification_t *id;
86 /* array of online leases, as u_int offset */
87 array_t *online;
88 /* array of offline leases, as u_int offset */
89 array_t *offline;
90 } entry_t;
91
92 /**
93 * Create a new entry
94 */
95 static entry_t* entry_create(identification_t *id)
96 {
97 entry_t *entry;
98
99 INIT(entry,
100 .id = id->clone(id),
101 .online = array_create(sizeof(u_int), 0),
102 .offline = array_create(sizeof(u_int), 0),
103 );
104 return entry;
105 }
106
107 /**
108 * hashtable hash function for identities
109 */
110 static u_int id_hash(identification_t *id)
111 {
112 return chunk_hash(id->get_encoding(id));
113 }
114
115 /**
116 * hashtable equals function for identities
117 */
118 static bool id_equals(identification_t *a, identification_t *b)
119 {
120 return a->equals(a, b);
121 }
122
123 /**
124 * convert a pool offset to an address
125 */
126 static host_t* offset2host(private_mem_pool_t *pool, int offset)
127 {
128 chunk_t addr;
129 host_t *host;
130 u_int32_t *pos;
131
132 offset--;
133 if (offset > pool->size)
134 {
135 return NULL;
136 }
137
138 addr = chunk_clone(pool->base->get_address(pool->base));
139 if (pool->base->get_family(pool->base) == AF_INET6)
140 {
141 pos = (u_int32_t*)(addr.ptr + 12);
142 }
143 else
144 {
145 pos = (u_int32_t*)addr.ptr;
146 }
147 *pos = htonl(offset + ntohl(*pos));
148 host = host_create_from_chunk(pool->base->get_family(pool->base), addr, 0);
149 free(addr.ptr);
150 return host;
151 }
152
153 /**
154 * convert a host to a pool offset
155 */
156 static int host2offset(private_mem_pool_t *pool, host_t *addr)
157 {
158 chunk_t host, base;
159 u_int32_t hosti, basei;
160
161 if (addr->get_family(addr) != pool->base->get_family(pool->base))
162 {
163 return -1;
164 }
165 host = addr->get_address(addr);
166 base = pool->base->get_address(pool->base);
167 if (addr->get_family(addr) == AF_INET6)
168 {
169 /* only look at last /32 block */
170 if (!memeq(host.ptr, base.ptr, 12))
171 {
172 return -1;
173 }
174 host = chunk_skip(host, 12);
175 base = chunk_skip(base, 12);
176 }
177 hosti = ntohl(*(u_int32_t*)(host.ptr));
178 basei = ntohl(*(u_int32_t*)(base.ptr));
179 if (hosti > basei + pool->size)
180 {
181 return -1;
182 }
183 return hosti - basei + 1;
184 }
185
186 METHOD(mem_pool_t, get_name, const char*,
187 private_mem_pool_t *this)
188 {
189 return this->name;
190 }
191
192 METHOD(mem_pool_t, get_base, host_t*,
193 private_mem_pool_t *this)
194 {
195 return this->base;
196 }
197
198 METHOD(mem_pool_t, get_size, u_int,
199 private_mem_pool_t *this)
200 {
201 return this->size;
202 }
203
204 METHOD(mem_pool_t, get_online, u_int,
205 private_mem_pool_t *this)
206 {
207 enumerator_t *enumerator;
208 entry_t *entry;
209 u_int count = 0;
210
211 this->mutex->lock(this->mutex);
212 enumerator = this->leases->create_enumerator(this->leases);
213 while (enumerator->enumerate(enumerator, NULL, &entry))
214 {
215 count += array_count(entry->online);
216 }
217 enumerator->destroy(enumerator);
218 this->mutex->unlock(this->mutex);
219
220 return count;
221 }
222
223 METHOD(mem_pool_t, get_offline, u_int,
224 private_mem_pool_t *this)
225 {
226 enumerator_t *enumerator;
227 entry_t *entry;
228 u_int count = 0;
229
230 this->mutex->lock(this->mutex);
231 enumerator = this->leases->create_enumerator(this->leases);
232 while (enumerator->enumerate(enumerator, NULL, &entry))
233 {
234 count += array_count(entry->offline);
235 }
236 enumerator->destroy(enumerator);
237 this->mutex->unlock(this->mutex);
238
239 return count;
240 }
241
242 /**
243 * Get an existing lease for id
244 */
245 static int get_existing(private_mem_pool_t *this, identification_t *id,
246 host_t *requested)
247 {
248 enumerator_t *enumerator;
249 u_int *current;
250 entry_t *entry;
251 int offset = 0;
252
253 entry = this->leases->get(this->leases, id);
254 if (!entry)
255 {
256 return 0;
257 }
258
259 /* check for a valid offline lease, refresh */
260 enumerator = array_create_enumerator(entry->offline);
261 if (enumerator->enumerate(enumerator, &current))
262 {
263 offset = *current;
264 array_insert(entry->online, ARRAY_TAIL, current);
265 array_remove_at(entry->offline, enumerator);
266 }
267 enumerator->destroy(enumerator);
268 if (offset)
269 {
270 DBG1(DBG_CFG, "reassigning offline lease to '%Y'", id);
271 return offset;
272 }
273 if (!this->reassign_online)
274 {
275 return 0;
276 }
277 /* check for a valid online lease to reassign */
278 enumerator = array_create_enumerator(entry->online);
279 while (enumerator->enumerate(enumerator, &current))
280 {
281 if (*current == host2offset(this, requested))
282 {
283 offset = *current;
284 /* add an additional "online" entry */
285 array_insert(entry->online, ARRAY_TAIL, current);
286 break;
287 }
288 }
289 enumerator->destroy(enumerator);
290 if (offset)
291 {
292 DBG1(DBG_CFG, "reassigning online lease to '%Y'", id);
293 }
294 return offset;
295 }
296
297 /**
298 * Get a new lease for id
299 */
300 static int get_new(private_mem_pool_t *this, identification_t *id)
301 {
302 entry_t *entry;
303 u_int offset = 0;
304
305 if (this->unused < this->size)
306 {
307 entry = this->leases->get(this->leases, id);
308 if (!entry)
309 {
310 entry = entry_create(id);
311 this->leases->put(this->leases, entry->id, entry);
312 }
313 /* assigning offset, starting by 1 */
314 offset = ++this->unused + (this->base_is_network_id ? 1 : 0);
315 array_insert(entry->online, ARRAY_TAIL, &offset);
316 DBG1(DBG_CFG, "assigning new lease to '%Y'", id);
317 }
318 return offset;
319 }
320
321 /**
322 * Get a reassigned lease for id in case the pool is full
323 */
324 static int get_reassigned(private_mem_pool_t *this, identification_t *id)
325 {
326 enumerator_t *enumerator;
327 entry_t *entry;
328 u_int current, offset = 0;
329
330 enumerator = this->leases->create_enumerator(this->leases);
331 while (enumerator->enumerate(enumerator, NULL, &entry))
332 {
333 if (array_remove(entry->offline, ARRAY_HEAD, &current))
334 {
335 offset = current;
336 DBG1(DBG_CFG, "reassigning existing offline lease by '%Y'"
337 " to '%Y'", entry->id, id);
338 break;
339 }
340 }
341 enumerator->destroy(enumerator);
342
343 if (offset)
344 {
345 entry = this->leases->get(this->leases, id);
346 if (!entry)
347 {
348 entry = entry_create(id);
349 this->leases->put(this->leases, entry->id, entry);
350 }
351 array_insert(entry->online, ARRAY_TAIL, &offset);
352 }
353 return offset;
354 }
355
356 METHOD(mem_pool_t, acquire_address, host_t*,
357 private_mem_pool_t *this, identification_t *id, host_t *requested,
358 mem_pool_op_t operation)
359 {
360 int offset = 0;
361
362 /* if the pool is empty (e.g. in the %config case) we simply return the
363 * requested address */
364 if (this->size == 0)
365 {
366 return requested->clone(requested);
367 }
368
369 if (requested->get_family(requested) !=
370 this->base->get_family(this->base))
371 {
372 return NULL;
373 }
374
375 this->mutex->lock(this->mutex);
376 switch (operation)
377 {
378 case MEM_POOL_EXISTING:
379 offset = get_existing(this, id, requested);
380 break;
381 case MEM_POOL_NEW:
382 offset = get_new(this, id);
383 break;
384 case MEM_POOL_REASSIGN:
385 offset = get_reassigned(this, id);
386 if (!offset)
387 {
388 DBG1(DBG_CFG, "pool '%s' is full, unable to assign address",
389 this->name);
390 }
391 break;
392 default:
393 break;
394 }
395 this->mutex->unlock(this->mutex);
396
397 if (offset)
398 {
399 return offset2host(this, offset);
400 }
401 return NULL;
402 }
403
404 METHOD(mem_pool_t, release_address, bool,
405 private_mem_pool_t *this, host_t *address, identification_t *id)
406 {
407 enumerator_t *enumerator;
408 bool found = FALSE, more = FALSE;
409 entry_t *entry;
410 u_int offset, *current;
411
412 if (this->size != 0)
413 {
414 this->mutex->lock(this->mutex);
415 entry = this->leases->get(this->leases, id);
416 if (entry)
417 {
418 offset = host2offset(this, address);
419
420 enumerator = array_create_enumerator(entry->online);
421 while (enumerator->enumerate(enumerator, &current))
422 {
423 if (*current == offset)
424 {
425 if (!found)
426 { /* remove the first entry only */
427 array_remove_at(entry->online, enumerator);
428 found = TRUE;
429 }
430 else
431 { /* but check for more entries */
432 more = TRUE;
433 break;
434 }
435 }
436 }
437 enumerator->destroy(enumerator);
438
439 if (found && !more)
440 {
441 /* no tunnels are online anymore for this lease, make offline */
442 array_insert(entry->offline, ARRAY_TAIL, &offset);
443 DBG1(DBG_CFG, "lease %H by '%Y' went offline", address, id);
444 }
445 }
446 this->mutex->unlock(this->mutex);
447 }
448 return found;
449 }
450
451 /**
452 * lease enumerator
453 */
454 typedef struct {
455 /** implemented enumerator interface */
456 enumerator_t public;
457 /** hash-table enumerator */
458 enumerator_t *entries;
459 /** online enumerator */
460 enumerator_t *online;
461 /** offline enumerator */
462 enumerator_t *offline;
463 /** enumerated pool */
464 private_mem_pool_t *pool;
465 /** currently enumerated entry */
466 entry_t *entry;
467 /** currently enumerated lease address */
468 host_t *addr;
469 } lease_enumerator_t;
470
471 METHOD(enumerator_t, lease_enumerate, bool,
472 lease_enumerator_t *this, identification_t **id, host_t **addr, bool *online)
473 {
474 u_int *offset;
475
476 DESTROY_IF(this->addr);
477 this->addr = NULL;
478
479 while (TRUE)
480 {
481 if (this->entry)
482 {
483 if (this->online->enumerate(this->online, &offset))
484 {
485 *id = this->entry->id;
486 *addr = this->addr = offset2host(this->pool, *offset);
487 *online = TRUE;
488 return TRUE;
489 }
490 if (this->offline->enumerate(this->offline, &offset))
491 {
492 *id = this->entry->id;
493 *addr = this->addr = offset2host(this->pool, *offset);
494 *online = FALSE;
495 return TRUE;
496 }
497 this->online->destroy(this->online);
498 this->offline->destroy(this->offline);
499 this->online = this->offline = NULL;
500 }
501 if (!this->entries->enumerate(this->entries, NULL, &this->entry))
502 {
503 return FALSE;
504 }
505 this->online = array_create_enumerator(this->entry->online);
506 this->offline = array_create_enumerator(this->entry->offline);
507 }
508 }
509
510 METHOD(enumerator_t, lease_enumerator_destroy, void,
511 lease_enumerator_t *this)
512 {
513 DESTROY_IF(this->addr);
514 DESTROY_IF(this->online);
515 DESTROY_IF(this->offline);
516 this->entries->destroy(this->entries);
517 this->pool->mutex->unlock(this->pool->mutex);
518 free(this);
519 }
520
521 METHOD(mem_pool_t, create_lease_enumerator, enumerator_t*,
522 private_mem_pool_t *this)
523 {
524 lease_enumerator_t *enumerator;
525
526 this->mutex->lock(this->mutex);
527 INIT(enumerator,
528 .public = {
529 .enumerate = (void*)_lease_enumerate,
530 .destroy = _lease_enumerator_destroy,
531 },
532 .pool = this,
533 .entries = this->leases->create_enumerator(this->leases),
534 );
535 return &enumerator->public;
536 }
537
538 METHOD(mem_pool_t, destroy, void,
539 private_mem_pool_t *this)
540 {
541 enumerator_t *enumerator;
542 entry_t *entry;
543
544 enumerator = this->leases->create_enumerator(this->leases);
545 while (enumerator->enumerate(enumerator, NULL, &entry))
546 {
547 entry->id->destroy(entry->id);
548 array_destroy(entry->online);
549 array_destroy(entry->offline);
550 free(entry);
551 }
552 enumerator->destroy(enumerator);
553
554 this->leases->destroy(this->leases);
555 this->mutex->destroy(this->mutex);
556 DESTROY_IF(this->base);
557 free(this->name);
558 free(this);
559 }
560
561 /**
562 * Generic constructor
563 */
564 static private_mem_pool_t *create_generic(char *name)
565 {
566 private_mem_pool_t *this;
567
568 INIT(this,
569 .public = {
570 .get_name = _get_name,
571 .get_base = _get_base,
572 .get_size = _get_size,
573 .get_online = _get_online,
574 .get_offline = _get_offline,
575 .acquire_address = _acquire_address,
576 .release_address = _release_address,
577 .create_lease_enumerator = _create_lease_enumerator,
578 .destroy = _destroy,
579 },
580 .name = strdup(name),
581 .leases = hashtable_create((hashtable_hash_t)id_hash,
582 (hashtable_equals_t)id_equals, 16),
583 .mutex = mutex_create(MUTEX_TYPE_DEFAULT),
584 .reassign_online = lib->settings->get_bool(lib->settings,
585 "%s.mem-pool.reassign_online", FALSE, lib->ns),
586 );
587
588 return this;
589 }
590
591 /**
592 * Check if the given host is the network ID of a subnet, that is, if hostbits
593 * are zero. Since we limit pools to 2^31 addresses we only have to check the
594 * last 4 bytes.
595 */
596 static u_int network_id_diff(host_t *host, int hostbits)
597 {
598 u_int32_t last;
599 chunk_t addr;
600
601 if (!hostbits)
602 {
603 return 0;
604 }
605 addr = host->get_address(host);
606 last = untoh32(addr.ptr + addr.len - sizeof(last));
607 hostbits = sizeof(last) * 8 - hostbits;
608 return (last << hostbits) >> hostbits;
609 }
610
611 /**
612 * Described in header
613 */
614 mem_pool_t *mem_pool_create(char *name, host_t *base, int bits)
615 {
616 private_mem_pool_t *this;
617 u_int diff;
618 int addr_bits;
619
620 this = create_generic(name);
621 if (base)
622 {
623 addr_bits = base->get_family(base) == AF_INET ? 32 : 128;
624 bits = max(0, min(bits, addr_bits));
625 /* net bits -> host bits */
626 bits = addr_bits - bits;
627 if (bits > POOL_LIMIT)
628 {
629 bits = POOL_LIMIT;
630 DBG1(DBG_CFG, "virtual IP pool too large, limiting to %H/%d",
631 base, addr_bits - bits);
632 }
633 this->size = 1 << bits;
634 this->base = base->clone(base);
635
636 if (this->size > 2)
637 {
638 /* if base is the network id we later skip the first address,
639 * otherwise adjust the size to represent the actual number
640 * of assignable addresses */
641 diff = network_id_diff(base, bits);
642 if (!diff)
643 {
644 this->base_is_network_id = TRUE;
645 this->size--;
646 }
647 else
648 {
649 this->size -= diff;
650 }
651 /* skip the last address (broadcast) of the subnet */
652 this->size--;
653 }
654 else if (network_id_diff(base, bits))
655 { /* only serve the second address of the subnet */
656 this->size--;
657 }
658 }
659 return &this->public;
660 }
661
662 /**
663 * Described in header
664 */
665 mem_pool_t *mem_pool_create_range(char *name, host_t *from, host_t *to)
666 {
667 private_mem_pool_t *this;
668 chunk_t fromaddr, toaddr;
669 u_int32_t diff;
670
671 fromaddr = from->get_address(from);
672 toaddr = to->get_address(to);
673
674 if (from->get_family(from) != to->get_family(to) ||
675 fromaddr.len != toaddr.len || fromaddr.len < sizeof(diff) ||
676 memcmp(fromaddr.ptr, toaddr.ptr, toaddr.len) > 0)
677 {
678 DBG1(DBG_CFG, "invalid IP address range: %H-%H", from, to);
679 return NULL;
680 }
681 if (fromaddr.len > sizeof(diff) &&
682 !chunk_equals(chunk_create(fromaddr.ptr, fromaddr.len - sizeof(diff)),
683 chunk_create(toaddr.ptr, toaddr.len - sizeof(diff))))
684 {
685 DBG1(DBG_CFG, "IP address range too large: %H-%H", from, to);
686 return NULL;
687 }
688 this = create_generic(name);
689 this->base = from->clone(from);
690 diff = untoh32(toaddr.ptr + toaddr.len - sizeof(diff)) -
691 untoh32(fromaddr.ptr + fromaddr.len - sizeof(diff));
692 this->size = diff + 1;
693
694 return &this->public;
695 }