2 * Copyright (C) 2010 Tobias Brunner
3 * Copyright (C) 2008-2010 Martin Willi
4 * HSR Hochschule fuer Technik Rapperswil
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>.
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
20 #include <utils/debug.h>
21 #include <collections/hashtable.h>
22 #include <collections/array.h>
23 #include <threading/mutex.h>
25 #define POOL_LIMIT (sizeof(u_int)*8 - 1)
27 typedef struct private_mem_pool_t private_mem_pool_t
;
30 * private data of mem_pool_t
32 struct private_mem_pool_t
{
44 * base address of the pool
49 * whether base is the network id of the subnet on which the pool is based
51 bool base_is_network_id
;
64 * lease hashtable [identity => entry]
69 * lock to safely access the pool
75 * A unique lease address offset, with a hash of the peer host address
78 /** lease, as offset */
80 /** hash of remote address, to allow duplicates */
88 /* identity reference */
90 /* array of online leases, as unique_lease_t */
92 /* array of offline leases, as u_int offset */
99 static entry_t
* entry_create(identification_t
*id
)
105 .online
= array_create(sizeof(unique_lease_t
), 0),
106 .offline
= array_create(sizeof(u_int
), 0),
114 static void entry_destroy(entry_t
*this)
116 this->id
->destroy(this->id
);
117 array_destroy(this->online
);
118 array_destroy(this->offline
);
123 * hashtable hash function for identities
125 static u_int
id_hash(identification_t
*id
)
127 return chunk_hash(id
->get_encoding(id
));
131 * hashtable equals function for identities
133 static bool id_equals(identification_t
*a
, identification_t
*b
)
135 return a
->equals(a
, b
);
139 * convert a pool offset to an address
141 static host_t
* offset2host(private_mem_pool_t
*pool
, int offset
)
148 if (offset
> pool
->size
)
153 addr
= chunk_clone(pool
->base
->get_address(pool
->base
));
154 if (pool
->base
->get_family(pool
->base
) == AF_INET6
)
156 pos
= (uint32_t*)(addr
.ptr
+ 12);
160 pos
= (uint32_t*)addr
.ptr
;
162 *pos
= htonl(offset
+ ntohl(*pos
));
163 host
= host_create_from_chunk(pool
->base
->get_family(pool
->base
), addr
, 0);
169 * convert a host to a pool offset
171 static int host2offset(private_mem_pool_t
*pool
, host_t
*addr
)
174 uint32_t hosti
, basei
;
176 if (addr
->get_family(addr
) != pool
->base
->get_family(pool
->base
))
180 host
= addr
->get_address(addr
);
181 base
= pool
->base
->get_address(pool
->base
);
182 if (addr
->get_family(addr
) == AF_INET6
)
184 /* only look at last /32 block */
185 if (!memeq(host
.ptr
, base
.ptr
, 12))
189 host
= chunk_skip(host
, 12);
190 base
= chunk_skip(base
, 12);
192 hosti
= ntohl(*(uint32_t*)(host
.ptr
));
193 basei
= ntohl(*(uint32_t*)(base
.ptr
));
194 if (hosti
> basei
+ pool
->size
)
198 return hosti
- basei
+ 1;
201 METHOD(mem_pool_t
, get_name
, const char*,
202 private_mem_pool_t
*this)
207 METHOD(mem_pool_t
, get_base
, host_t
*,
208 private_mem_pool_t
*this)
213 METHOD(mem_pool_t
, get_size
, u_int
,
214 private_mem_pool_t
*this)
219 METHOD(mem_pool_t
, get_online
, u_int
,
220 private_mem_pool_t
*this)
222 enumerator_t
*enumerator
;
226 this->mutex
->lock(this->mutex
);
227 enumerator
= this->leases
->create_enumerator(this->leases
);
228 while (enumerator
->enumerate(enumerator
, NULL
, &entry
))
230 count
+= array_count(entry
->online
);
232 enumerator
->destroy(enumerator
);
233 this->mutex
->unlock(this->mutex
);
238 METHOD(mem_pool_t
, get_offline
, u_int
,
239 private_mem_pool_t
*this)
241 enumerator_t
*enumerator
;
245 this->mutex
->lock(this->mutex
);
246 enumerator
= this->leases
->create_enumerator(this->leases
);
247 while (enumerator
->enumerate(enumerator
, NULL
, &entry
))
249 count
+= array_count(entry
->offline
);
251 enumerator
->destroy(enumerator
);
252 this->mutex
->unlock(this->mutex
);
258 * Create a unique hash for a remote address
260 static u_int
hash_addr(host_t
*addr
)
264 return chunk_hash_inc(addr
->get_address(addr
), addr
->get_port(addr
));
270 * Get an existing lease for id
272 static int get_existing(private_mem_pool_t
*this, identification_t
*id
,
273 host_t
*requested
, host_t
*peer
)
275 enumerator_t
*enumerator
;
276 unique_lease_t
*lease
, reassign
;
281 entry
= this->leases
->get(this->leases
, id
);
287 /* check for a valid offline lease, refresh */
288 enumerator
= array_create_enumerator(entry
->offline
);
289 if (enumerator
->enumerate(enumerator
, ¤t
))
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
);
296 enumerator
->destroy(enumerator
);
299 DBG1(DBG_CFG
, "reassigning offline lease to '%Y'", id
);
306 /* check for a valid online lease to reassign */
307 enumerator
= array_create_enumerator(entry
->online
);
308 while (enumerator
->enumerate(enumerator
, &lease
))
310 if (lease
->offset
== host2offset(this, requested
) &&
311 lease
->hash
== hash_addr(peer
))
313 offset
= lease
->offset
;
314 /* add an additional "online" entry */
315 array_insert(entry
->online
, ARRAY_TAIL
, lease
);
319 enumerator
->destroy(enumerator
);
322 DBG1(DBG_CFG
, "reassigning online lease to '%Y'", id
);
328 * Get a new lease for id
330 static int get_new(private_mem_pool_t
*this, identification_t
*id
, host_t
*peer
)
333 unique_lease_t lease
= {};
335 if (this->unused
< this->size
)
337 entry
= this->leases
->get(this->leases
, id
);
340 entry
= entry_create(id
);
341 this->leases
->put(this->leases
, entry
->id
, entry
);
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
);
353 * Get a reassigned lease for id in case the pool is full
355 static int get_reassigned(private_mem_pool_t
*this, identification_t
*id
,
358 enumerator_t
*enumerator
;
361 unique_lease_t lease
= {};
363 enumerator
= this->leases
->create_enumerator(this->leases
);
364 while (enumerator
->enumerate(enumerator
, NULL
, &entry
))
366 if (array_remove(entry
->offline
, ARRAY_HEAD
, ¤t
))
368 lease
.offset
= current
;
369 DBG1(DBG_CFG
, "reassigning existing offline lease by '%Y' "
370 "to '%Y'", entry
->id
, id
);
372 if (!array_count(entry
->online
) && !array_count(entry
->offline
))
374 this->leases
->remove_at(this->leases
, enumerator
);
375 entry_destroy(entry
);
382 enumerator
->destroy(enumerator
);
386 entry
= this->leases
->get(this->leases
, id
);
389 entry
= entry_create(id
);
390 this->leases
->put(this->leases
, entry
->id
, entry
);
392 lease
.hash
= hash_addr(peer
);
393 array_insert(entry
->online
, ARRAY_TAIL
, &lease
);
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
)
404 /* if the pool is empty (e.g. in the %config case) we simply return the
405 * requested address */
408 return requested
->clone(requested
);
411 if (requested
->get_family(requested
) !=
412 this->base
->get_family(this->base
))
417 this->mutex
->lock(this->mutex
);
420 case MEM_POOL_EXISTING
:
421 offset
= get_existing(this, id
, requested
, peer
);
424 offset
= get_new(this, id
, peer
);
426 case MEM_POOL_REASSIGN
:
427 offset
= get_reassigned(this, id
, peer
);
430 DBG1(DBG_CFG
, "pool '%s' is full, unable to assign address",
437 this->mutex
->unlock(this->mutex
);
441 return offset2host(this, offset
);
446 METHOD(mem_pool_t
, release_address
, bool,
447 private_mem_pool_t
*this, host_t
*address
, identification_t
*id
)
449 enumerator_t
*enumerator
;
450 bool found
= FALSE
, more
= FALSE
;
453 unique_lease_t
*current
;
457 this->mutex
->lock(this->mutex
);
458 entry
= this->leases
->get(this->leases
, id
);
461 offset
= host2offset(this, address
);
463 enumerator
= array_create_enumerator(entry
->online
);
464 while (enumerator
->enumerate(enumerator
, ¤t
))
466 if (current
->offset
== offset
)
469 { /* remove the first entry only */
470 array_remove_at(entry
->online
, enumerator
);
474 { /* but check for more entries */
480 enumerator
->destroy(enumerator
);
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
);
489 this->mutex
->unlock(this->mutex
);
498 /** implemented enumerator interface */
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 */
510 /** currently enumerated lease address */
512 } lease_enumerator_t
;
514 METHOD(enumerator_t
, lease_enumerate
, bool,
515 lease_enumerator_t
*this, va_list args
)
517 identification_t
**id
;
518 unique_lease_t
*lease
;
523 VA_ARGS_VGET(args
, id
, addr
, online
);
525 DESTROY_IF(this->addr
);
532 if (this->online
->enumerate(this->online
, &lease
))
534 *id
= this->entry
->id
;
535 *addr
= this->addr
= offset2host(this->pool
, lease
->offset
);
539 if (this->offline
->enumerate(this->offline
, &offset
))
541 *id
= this->entry
->id
;
542 *addr
= this->addr
= offset2host(this->pool
, *offset
);
546 this->online
->destroy(this->online
);
547 this->offline
->destroy(this->offline
);
548 this->online
= this->offline
= NULL
;
550 if (!this->entries
->enumerate(this->entries
, NULL
, &this->entry
))
554 this->online
= array_create_enumerator(this->entry
->online
);
555 this->offline
= array_create_enumerator(this->entry
->offline
);
559 METHOD(enumerator_t
, lease_enumerator_destroy
, void,
560 lease_enumerator_t
*this)
562 DESTROY_IF(this->addr
);
563 DESTROY_IF(this->online
);
564 DESTROY_IF(this->offline
);
565 this->entries
->destroy(this->entries
);
566 this->pool
->mutex
->unlock(this->pool
->mutex
);
570 METHOD(mem_pool_t
, create_lease_enumerator
, enumerator_t
*,
571 private_mem_pool_t
*this)
573 lease_enumerator_t
*enumerator
;
575 this->mutex
->lock(this->mutex
);
578 .enumerate
= enumerator_enumerate_default
,
579 .venumerate
= _lease_enumerate
,
580 .destroy
= _lease_enumerator_destroy
,
583 .entries
= this->leases
->create_enumerator(this->leases
),
585 return &enumerator
->public;
588 METHOD(mem_pool_t
, destroy
, void,
589 private_mem_pool_t
*this)
591 enumerator_t
*enumerator
;
594 enumerator
= this->leases
->create_enumerator(this->leases
);
595 while (enumerator
->enumerate(enumerator
, NULL
, &entry
))
597 entry_destroy(entry
);
599 enumerator
->destroy(enumerator
);
601 this->leases
->destroy(this->leases
);
602 this->mutex
->destroy(this->mutex
);
603 DESTROY_IF(this->base
);
609 * Generic constructor
611 static private_mem_pool_t
*create_generic(char *name
)
613 private_mem_pool_t
*this;
617 .get_name
= _get_name
,
618 .get_base
= _get_base
,
619 .get_size
= _get_size
,
620 .get_online
= _get_online
,
621 .get_offline
= _get_offline
,
622 .acquire_address
= _acquire_address
,
623 .release_address
= _release_address
,
624 .create_lease_enumerator
= _create_lease_enumerator
,
627 .name
= strdup(name
),
628 .leases
= hashtable_create((hashtable_hash_t
)id_hash
,
629 (hashtable_equals_t
)id_equals
, 16),
630 .mutex
= mutex_create(MUTEX_TYPE_DEFAULT
),
637 * Check if the given host is the network ID of a subnet, that is, if hostbits
638 * are zero. Since we limit pools to 2^31 addresses we only have to check the
641 static u_int
network_id_diff(host_t
*host
, int hostbits
)
650 addr
= host
->get_address(host
);
651 last
= untoh32(addr
.ptr
+ addr
.len
- sizeof(last
));
652 hostbits
= sizeof(last
) * 8 - hostbits
;
653 return (last
<< hostbits
) >> hostbits
;
657 * Described in header
659 mem_pool_t
*mem_pool_create(char *name
, host_t
*base
, int bits
)
661 private_mem_pool_t
*this;
665 this = create_generic(name
);
668 addr_bits
= base
->get_family(base
) == AF_INET
? 32 : 128;
669 bits
= max(0, min(bits
, addr_bits
));
670 /* net bits -> host bits */
671 bits
= addr_bits
- bits
;
672 if (bits
> POOL_LIMIT
)
675 DBG1(DBG_CFG
, "virtual IP pool too large, limiting to %H/%d",
676 base
, addr_bits
- bits
);
678 this->size
= 1 << bits
;
679 this->base
= base
->clone(base
);
683 /* if base is the network id we later skip the first address,
684 * otherwise adjust the size to represent the actual number
685 * of assignable addresses */
686 diff
= network_id_diff(base
, bits
);
689 this->base_is_network_id
= TRUE
;
696 /* skip the last address (broadcast) of the subnet */
699 else if (network_id_diff(base
, bits
))
700 { /* only serve the second address of the subnet */
704 return &this->public;
708 * Described in header
710 mem_pool_t
*mem_pool_create_range(char *name
, host_t
*from
, host_t
*to
)
712 private_mem_pool_t
*this;
713 chunk_t fromaddr
, toaddr
;
716 fromaddr
= from
->get_address(from
);
717 toaddr
= to
->get_address(to
);
719 if (from
->get_family(from
) != to
->get_family(to
) ||
720 fromaddr
.len
!= toaddr
.len
|| fromaddr
.len
< sizeof(diff
) ||
721 memcmp(fromaddr
.ptr
, toaddr
.ptr
, toaddr
.len
) > 0)
723 DBG1(DBG_CFG
, "invalid IP address range: %H-%H", from
, to
);
726 if (fromaddr
.len
> sizeof(diff
) &&
727 !chunk_equals(chunk_create(fromaddr
.ptr
, fromaddr
.len
- sizeof(diff
)),
728 chunk_create(toaddr
.ptr
, toaddr
.len
- sizeof(diff
))))
730 DBG1(DBG_CFG
, "IP address range too large: %H-%H", from
, to
);
733 this = create_generic(name
);
734 this->base
= from
->clone(from
);
735 diff
= untoh32(toaddr
.ptr
+ toaddr
.len
- sizeof(diff
)) -
736 untoh32(fromaddr
.ptr
+ fromaddr
.len
- sizeof(diff
));
737 this->size
= diff
+ 1;
739 return &this->public;