Annotation of embedaddon/strongswan/src/libcharon/attributes/mem_pool.c, revision 1.1.1.1
1.1 misho 1: /*
2: * Copyright (C) 2010 Tobias Brunner
3: * Copyright (C) 2008-2010 Martin Willi
4: * HSR 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: /* identity 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: uint32_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 = (uint32_t*)(addr.ptr + 12);
157: }
158: else
159: {
160: pos = (uint32_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: uint32_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(*(uint32_t*)(host.ptr));
193: basei = ntohl(*(uint32_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, ¤t))
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, ¤t))
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, ¤t))
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, va_list args)
516: {
517: identification_t **id;
518: unique_lease_t *lease;
519: host_t **addr;
520: u_int *offset;
521: bool *online;
522:
523: VA_ARGS_VGET(args, id, addr, online);
524:
525: DESTROY_IF(this->addr);
526: this->addr = NULL;
527:
528: while (TRUE)
529: {
530: if (this->entry)
531: {
532: if (this->online->enumerate(this->online, &lease))
533: {
534: *id = this->entry->id;
535: *addr = this->addr = offset2host(this->pool, lease->offset);
536: *online = TRUE;
537: return TRUE;
538: }
539: if (this->offline->enumerate(this->offline, &offset))
540: {
541: *id = this->entry->id;
542: *addr = this->addr = offset2host(this->pool, *offset);
543: *online = FALSE;
544: return TRUE;
545: }
546: this->online->destroy(this->online);
547: this->offline->destroy(this->offline);
548: this->online = this->offline = NULL;
549: }
550: if (!this->entries->enumerate(this->entries, NULL, &this->entry))
551: {
552: return FALSE;
553: }
554: this->online = array_create_enumerator(this->entry->online);
555: this->offline = array_create_enumerator(this->entry->offline);
556: }
557: }
558:
559: METHOD(enumerator_t, lease_enumerator_destroy, void,
560: lease_enumerator_t *this)
561: {
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);
567: free(this);
568: }
569:
570: METHOD(mem_pool_t, create_lease_enumerator, enumerator_t*,
571: private_mem_pool_t *this)
572: {
573: lease_enumerator_t *enumerator;
574:
575: this->mutex->lock(this->mutex);
576: INIT(enumerator,
577: .public = {
578: .enumerate = enumerator_enumerate_default,
579: .venumerate = _lease_enumerate,
580: .destroy = _lease_enumerator_destroy,
581: },
582: .pool = this,
583: .entries = this->leases->create_enumerator(this->leases),
584: );
585: return &enumerator->public;
586: }
587:
588: METHOD(mem_pool_t, destroy, void,
589: private_mem_pool_t *this)
590: {
591: enumerator_t *enumerator;
592: entry_t *entry;
593:
594: enumerator = this->leases->create_enumerator(this->leases);
595: while (enumerator->enumerate(enumerator, NULL, &entry))
596: {
597: entry_destroy(entry);
598: }
599: enumerator->destroy(enumerator);
600:
601: this->leases->destroy(this->leases);
602: this->mutex->destroy(this->mutex);
603: DESTROY_IF(this->base);
604: free(this->name);
605: free(this);
606: }
607:
608: /**
609: * Generic constructor
610: */
611: static private_mem_pool_t *create_generic(char *name)
612: {
613: private_mem_pool_t *this;
614:
615: INIT(this,
616: .public = {
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,
625: .destroy = _destroy,
626: },
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),
631: );
632:
633: return this;
634: }
635:
636: /**
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
639: * last 4 bytes.
640: */
641: static u_int network_id_diff(host_t *host, int hostbits)
642: {
643: uint32_t last;
644: chunk_t addr;
645:
646: if (!hostbits)
647: {
648: return 0;
649: }
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;
654: }
655:
656: /**
657: * Described in header
658: */
659: mem_pool_t *mem_pool_create(char *name, host_t *base, int bits)
660: {
661: private_mem_pool_t *this;
662: u_int diff;
663: int addr_bits;
664:
665: this = create_generic(name);
666: if (base)
667: {
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)
673: {
674: bits = POOL_LIMIT;
675: DBG1(DBG_CFG, "virtual IP pool too large, limiting to %H/%d",
676: base, addr_bits - bits);
677: }
678: this->size = 1 << bits;
679: this->base = base->clone(base);
680:
681: if (this->size > 2)
682: {
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);
687: if (!diff)
688: {
689: this->base_is_network_id = TRUE;
690: this->size--;
691: }
692: else
693: {
694: this->size -= diff;
695: }
696: /* skip the last address (broadcast) of the subnet */
697: this->size--;
698: }
699: else if (network_id_diff(base, bits))
700: { /* only serve the second address of the subnet */
701: this->size--;
702: }
703: }
704: return &this->public;
705: }
706:
707: /**
708: * Described in header
709: */
710: mem_pool_t *mem_pool_create_range(char *name, host_t *from, host_t *to)
711: {
712: private_mem_pool_t *this;
713: chunk_t fromaddr, toaddr;
714: uint32_t diff;
715:
716: fromaddr = from->get_address(from);
717: toaddr = to->get_address(to);
718:
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)
722: {
723: DBG1(DBG_CFG, "invalid IP address range: %H-%H", from, to);
724: return NULL;
725: }
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))))
729: {
730: DBG1(DBG_CFG, "IP address range too large: %H-%H", from, to);
731: return NULL;
732: }
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;
738:
739: return &this->public;
740: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>