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