Annotation of embedaddon/strongswan/src/libcharon/attributes/mem_pool.c, revision 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>