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