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