mem-pool: Correctly ignore first and last addresses of subnets and adjust size
[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 = entry_create(id);
346 array_insert(entry->online, ARRAY_TAIL, &offset);
347 this->leases->put(this->leases, entry->id, entry);
348 }
349 return offset;
350 }
351
352 METHOD(mem_pool_t, acquire_address, host_t*,
353 private_mem_pool_t *this, identification_t *id, host_t *requested,
354 mem_pool_op_t operation)
355 {
356 int offset = 0;
357
358 /* if the pool is empty (e.g. in the %config case) we simply return the
359 * requested address */
360 if (this->size == 0)
361 {
362 return requested->clone(requested);
363 }
364
365 if (requested->get_family(requested) !=
366 this->base->get_family(this->base))
367 {
368 return NULL;
369 }
370
371 this->mutex->lock(this->mutex);
372 switch (operation)
373 {
374 case MEM_POOL_EXISTING:
375 offset = get_existing(this, id, requested);
376 break;
377 case MEM_POOL_NEW:
378 offset = get_new(this, id);
379 break;
380 case MEM_POOL_REASSIGN:
381 offset = get_reassigned(this, id);
382 if (!offset)
383 {
384 DBG1(DBG_CFG, "pool '%s' is full, unable to assign address",
385 this->name);
386 }
387 break;
388 default:
389 break;
390 }
391 this->mutex->unlock(this->mutex);
392
393 if (offset)
394 {
395 return offset2host(this, offset);
396 }
397 return NULL;
398 }
399
400 METHOD(mem_pool_t, release_address, bool,
401 private_mem_pool_t *this, host_t *address, identification_t *id)
402 {
403 enumerator_t *enumerator;
404 bool found = FALSE, more = FALSE;
405 entry_t *entry;
406 u_int offset, *current;
407
408 if (this->size != 0)
409 {
410 this->mutex->lock(this->mutex);
411 entry = this->leases->get(this->leases, id);
412 if (entry)
413 {
414 offset = host2offset(this, address);
415
416 enumerator = array_create_enumerator(entry->online);
417 while (enumerator->enumerate(enumerator, &current))
418 {
419 if (*current == offset)
420 {
421 if (!found)
422 { /* remove the first entry only */
423 array_remove_at(entry->online, enumerator);
424 found = TRUE;
425 }
426 else
427 { /* but check for more entries */
428 more = TRUE;
429 break;
430 }
431 }
432 }
433 enumerator->destroy(enumerator);
434
435 if (found && !more)
436 {
437 /* no tunnels are online anymore for this lease, make offline */
438 array_insert(entry->offline, ARRAY_TAIL, &offset);
439 DBG1(DBG_CFG, "lease %H by '%Y' went offline", address, id);
440 }
441 }
442 this->mutex->unlock(this->mutex);
443 }
444 return found;
445 }
446
447 /**
448 * lease enumerator
449 */
450 typedef struct {
451 /** implemented enumerator interface */
452 enumerator_t public;
453 /** hash-table enumerator */
454 enumerator_t *entries;
455 /** online enumerator */
456 enumerator_t *online;
457 /** offline enumerator */
458 enumerator_t *offline;
459 /** enumerated pool */
460 private_mem_pool_t *pool;
461 /** currently enumerated entry */
462 entry_t *entry;
463 /** currently enumerated lease address */
464 host_t *addr;
465 } lease_enumerator_t;
466
467 METHOD(enumerator_t, lease_enumerate, bool,
468 lease_enumerator_t *this, identification_t **id, host_t **addr, bool *online)
469 {
470 u_int *offset;
471
472 DESTROY_IF(this->addr);
473 this->addr = NULL;
474
475 while (TRUE)
476 {
477 if (this->entry)
478 {
479 if (this->online->enumerate(this->online, &offset))
480 {
481 *id = this->entry->id;
482 *addr = this->addr = offset2host(this->pool, *offset);
483 *online = TRUE;
484 return TRUE;
485 }
486 if (this->offline->enumerate(this->offline, &offset))
487 {
488 *id = this->entry->id;
489 *addr = this->addr = offset2host(this->pool, *offset);
490 *online = FALSE;
491 return TRUE;
492 }
493 this->online->destroy(this->online);
494 this->offline->destroy(this->offline);
495 this->online = this->offline = NULL;
496 }
497 if (!this->entries->enumerate(this->entries, NULL, &this->entry))
498 {
499 return FALSE;
500 }
501 this->online = array_create_enumerator(this->entry->online);
502 this->offline = array_create_enumerator(this->entry->offline);
503 }
504 }
505
506 METHOD(enumerator_t, lease_enumerator_destroy, void,
507 lease_enumerator_t *this)
508 {
509 DESTROY_IF(this->addr);
510 DESTROY_IF(this->online);
511 DESTROY_IF(this->offline);
512 this->entries->destroy(this->entries);
513 this->pool->mutex->unlock(this->pool->mutex);
514 free(this);
515 }
516
517 METHOD(mem_pool_t, create_lease_enumerator, enumerator_t*,
518 private_mem_pool_t *this)
519 {
520 lease_enumerator_t *enumerator;
521
522 this->mutex->lock(this->mutex);
523 INIT(enumerator,
524 .public = {
525 .enumerate = (void*)_lease_enumerate,
526 .destroy = _lease_enumerator_destroy,
527 },
528 .pool = this,
529 .entries = this->leases->create_enumerator(this->leases),
530 );
531 return &enumerator->public;
532 }
533
534 METHOD(mem_pool_t, destroy, void,
535 private_mem_pool_t *this)
536 {
537 enumerator_t *enumerator;
538 entry_t *entry;
539
540 enumerator = this->leases->create_enumerator(this->leases);
541 while (enumerator->enumerate(enumerator, NULL, &entry))
542 {
543 entry->id->destroy(entry->id);
544 array_destroy(entry->online);
545 array_destroy(entry->offline);
546 free(entry);
547 }
548 enumerator->destroy(enumerator);
549
550 this->leases->destroy(this->leases);
551 this->mutex->destroy(this->mutex);
552 DESTROY_IF(this->base);
553 free(this->name);
554 free(this);
555 }
556
557 /**
558 * Generic constructor
559 */
560 static private_mem_pool_t *create_generic(char *name)
561 {
562 private_mem_pool_t *this;
563
564 INIT(this,
565 .public = {
566 .get_name = _get_name,
567 .get_base = _get_base,
568 .get_size = _get_size,
569 .get_online = _get_online,
570 .get_offline = _get_offline,
571 .acquire_address = _acquire_address,
572 .release_address = _release_address,
573 .create_lease_enumerator = _create_lease_enumerator,
574 .destroy = _destroy,
575 },
576 .name = strdup(name),
577 .leases = hashtable_create((hashtable_hash_t)id_hash,
578 (hashtable_equals_t)id_equals, 16),
579 .mutex = mutex_create(MUTEX_TYPE_DEFAULT),
580 .reassign_online = lib->settings->get_bool(lib->settings,
581 "%s.mem-pool.reassign_online", FALSE, lib->ns),
582 );
583
584 return this;
585 }
586
587 /**
588 * Check if the given host is the network ID of a subnet, that is, if hostbits
589 * are zero. Since we limit pools to 2^31 addresses we only have to check the
590 * last 4 bytes.
591 */
592 static u_int network_id_diff(host_t *host, int hostbits)
593 {
594 u_int32_t last;
595 chunk_t addr;
596
597 if (!hostbits)
598 {
599 return 0;
600 }
601 addr = host->get_address(host);
602 last = untoh32(addr.ptr + addr.len - sizeof(last));
603 hostbits = sizeof(last) * 8 - hostbits;
604 return (last << hostbits) >> hostbits;
605 }
606
607 /**
608 * Described in header
609 */
610 mem_pool_t *mem_pool_create(char *name, host_t *base, int bits)
611 {
612 private_mem_pool_t *this;
613 u_int diff;
614 int addr_bits;
615
616 this = create_generic(name);
617 if (base)
618 {
619 addr_bits = base->get_family(base) == AF_INET ? 32 : 128;
620 bits = max(0, min(bits, addr_bits));
621 /* net bits -> host bits */
622 bits = addr_bits - bits;
623 if (bits > POOL_LIMIT)
624 {
625 bits = POOL_LIMIT;
626 DBG1(DBG_CFG, "virtual IP pool too large, limiting to %H/%d",
627 base, addr_bits - bits);
628 }
629 this->size = 1 << bits;
630 this->base = base->clone(base);
631
632 if (this->size > 2)
633 {
634 /* if base is the network id we later skip the first address,
635 * otherwise adjust the size to represent the actual number
636 * of assignable addresses */
637 diff = network_id_diff(base, bits);
638 if (!diff)
639 {
640 this->base_is_network_id = TRUE;
641 this->size--;
642 }
643 else
644 {
645 this->size -= diff;
646 }
647 /* skip the last address (broadcast) of the subnet */
648 this->size--;
649 }
650 else if (network_id_diff(base, bits))
651 { /* only serve the second address of the subnet */
652 this->size--;
653 }
654 }
655 return &this->public;
656 }
657
658 /**
659 * Described in header
660 */
661 mem_pool_t *mem_pool_create_range(char *name, host_t *from, host_t *to)
662 {
663 private_mem_pool_t *this;
664 chunk_t fromaddr, toaddr;
665 u_int32_t diff;
666
667 fromaddr = from->get_address(from);
668 toaddr = to->get_address(to);
669
670 if (from->get_family(from) != to->get_family(to) ||
671 fromaddr.len != toaddr.len || fromaddr.len < sizeof(diff) ||
672 memcmp(fromaddr.ptr, toaddr.ptr, toaddr.len) > 0)
673 {
674 DBG1(DBG_CFG, "invalid IP address range: %H-%H", from, to);
675 return NULL;
676 }
677 if (fromaddr.len > sizeof(diff) &&
678 !chunk_equals(chunk_create(fromaddr.ptr, fromaddr.len - sizeof(diff)),
679 chunk_create(toaddr.ptr, toaddr.len - sizeof(diff))))
680 {
681 DBG1(DBG_CFG, "IP address range too large: %H-%H", from, to);
682 return NULL;
683 }
684 this = create_generic(name);
685 this->base = from->clone(from);
686 diff = untoh32(toaddr.ptr + toaddr.len - sizeof(diff)) -
687 untoh32(fromaddr.ptr + fromaddr.len - sizeof(diff));
688 this->size = diff + 1;
689
690 return &this->public;
691 }