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