lib/id_alloc.c

   1 /*
   2  * FRR ID Number Allocator
   3  * Copyright (C) 2018  Amazon.com, Inc. or its affiliates
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the Free
   7  * Software Foundation; either version 2 of the License, or (at your option)
   8  * any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  13  * more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; see the file COPYING; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  18  */
  19
  20 #ifdef HAVE_CONFIG_H
  21 #include "config.h"
  22 #endif
  23
  24 #include "id_alloc.h"
  25
  26 #include "log.h"
  27 #include "lib_errors.h"
  28 #include "memory.h"
  29
  30 #include <inttypes.h>
  31
  32 DEFINE_MTYPE_STATIC(LIB, IDALLOC_ALLOCATOR, "ID Number Allocator")
  33 DEFINE_MTYPE_STATIC(LIB, IDALLOC_ALLOCATOR_NAME, "ID Number Allocator Name")
  34 DEFINE_MTYPE_STATIC(LIB, IDALLOC_DIRECTORY, "ID Number Allocator Directory")
  35 DEFINE_MTYPE_STATIC(LIB, IDALLOC_SUBDIRECTORY,
  36                     "ID Number Allocator Subdirectory")
  37 DEFINE_MTYPE_STATIC(LIB, IDALLOC_PAGE, "ID Number Allocator Page")
  38 DEFINE_MTYPE_STATIC(LIB, IDALLOC_POOL, "ID Number temporary holding pool entry")
  39
  40 #if UINT_MAX >= UINT32_MAX
  41 #define FFS32(x) ffs(x)
  42 #else
  43 /* ints less than 32 bits? Yikes. */
  44 #define FFS32(x) ffsl(x)
  45 #endif
  46
  47 #define DIR_MASK    ((1<<IDALLOC_DIR_BITS)-1)
  48 #define SUBDIR_MASK ((1<<IDALLOC_SUBDIR_BITS)-1)
  49 #define FRR_ID_PAGE_MASK ((1<<IDALLOC_PAGE_BITS)-1)
  50 #define WORD_MASK   ((1<<IDALLOC_WORD_BITS)-1)
  51 #define OFFSET_MASK ((1<<IDALLOC_OFFSET_BITS)-1)
  52
  53 #define DIR_SHIFT    (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS + \
  54                       IDALLOC_PAGE_BITS + IDALLOC_SUBDIR_BITS)
  55 #define SUBDIR_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS + \
  56                       IDALLOC_PAGE_BITS)
  57 #define FRR_ID_PAGE_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS)
  58 #define WORD_SHIFT   (IDALLOC_OFFSET_BITS)
  59 #define OFFSET_SHIFT (0)
  60
  61 #define ID_DIR(id)    ((id >> DIR_SHIFT)    & DIR_MASK)
  62 #define ID_SUBDIR(id) ((id >> SUBDIR_SHIFT) & SUBDIR_MASK)
  63 #define ID_PAGE(id)   ((id >> FRR_ID_PAGE_SHIFT) & FRR_ID_PAGE_MASK)
  64 #define ID_WORD(id)   ((id >> WORD_SHIFT)   & WORD_MASK)
  65 #define ID_OFFSET(id) ((id >> OFFSET_SHIFT) & OFFSET_MASK)
  66
  67 /*
  68  * Find the page that an ID number belongs to in an allocator.
  69  * Optionally create the page if it doesn't exist.
  70  */
  71 static struct id_alloc_page *find_or_create_page(struct id_alloc *alloc,
  72                                                  uint32_t id, int create)
  73 {
  74         struct id_alloc_dir *dir = NULL;
  75         struct id_alloc_subdir *subdir = NULL;
  76         struct id_alloc_page *page = NULL;
  77
  78         dir = alloc->sublevels[ID_DIR(id)];
  79         if (dir == NULL) {
  80                 if (create) {
  81                         dir = XCALLOC(MTYPE_IDALLOC_DIRECTORY, sizeof(*dir));
  82                         alloc->sublevels[ID_DIR(id)] = dir;
  83                 } else {
  84                         return NULL;
  85                 }
  86         }
  87
  88         subdir = dir->sublevels[ID_SUBDIR(id)];
  89         if (subdir == NULL) {
  90                 if (create) {
  91                         subdir = XCALLOC(MTYPE_IDALLOC_SUBDIRECTORY,
  92                                          sizeof(*subdir));
  93                         dir->sublevels[ID_SUBDIR(id)] = subdir;
  94                 } else {
  95                         return NULL;
  96                 }
  97         }
  98
  99         page = subdir->sublevels[ID_PAGE(id)];
 100         if (page == NULL && create) {
 101                 page = XCALLOC(MTYPE_IDALLOC_PAGE, sizeof(*page));
 102                 page->base_value = id;
 103                 subdir->sublevels[ID_PAGE(id)] = page;
 104
 105                 alloc->capacity += 1 << FRR_ID_PAGE_SHIFT;
 106                 page->next_has_free = alloc->has_free;
 107                 alloc->has_free = page;
 108         } else if (page != NULL && create) {
 109                 flog_err(
 110                         EC_LIB_ID_CONSISTENCY,
 111                         "ID Allocator %s attempt to re-create page at %" PRIu32,
 112                         alloc->name, id);
 113         }
 114
 115         return page;
 116 }
 117
 118 /*
 119  * Return an ID number back to the allocator.
 120  * While this ID can be re-assigned through idalloc_allocate, the underlying
 121  * memory will not be freed. If this is the first free ID in the page, the page
 122  * will be added to the allocator's list of pages with free IDs.
 123  */
 124 void idalloc_free(struct id_alloc *alloc, uint32_t id)
 125 {
 126         struct id_alloc_page *page = NULL;
 127
 128         int word, offset;
 129         uint32_t old_word, old_word_mask;
 130
 131         page = find_or_create_page(alloc, id, 0);
 132         if (!page) {
 133                 flog_err(EC_LIB_ID_CONSISTENCY,
 134                         "ID Allocator %s cannot free #%" PRIu32
 135                         ". ID Block does not exist.",
 136                         alloc->name, id);
 137                 return;
 138         }
 139
 140         word = ID_WORD(id);
 141         offset = ID_OFFSET(id);
 142
 143         if ((page->allocated_mask[word] & (1 << offset)) == 0) {
 144                 flog_err(EC_LIB_ID_CONSISTENCY,
 145                         "ID Allocator %s cannot free #%" PRIu32
 146                         ". ID was not allocated at the time of free.",
 147                         alloc->name, id);
 148                 return;
 149         }
 150
 151         old_word = page->allocated_mask[word];
 152         page->allocated_mask[word] &= ~(((uint32_t)1) << offset);
 153         alloc->allocated -= 1;
 154
 155         if (old_word == UINT32_MAX) {
 156                 /* first bit in this block of 32 to be freed.*/
 157
 158                 old_word_mask = page->full_word_mask;
 159                 page->full_word_mask &= ~(((uint32_t)1) << word);
 160
 161                 if (old_word_mask == UINT32_MAX) {
 162                         /* first bit in page freed, add this to the allocator's
 163                          * list of pages with free space
 164                          */
 165                         page->next_has_free = alloc->has_free;
 166                         alloc->has_free = page;
 167                 }
 168         }
 169 }
 170
 171 /*
 172  * Add a allocation page to the end of the allocator's current range.
 173  * Returns null if the allocator has had all possible pages allocated already.
 174  */
 175 static struct id_alloc_page *create_next_page(struct id_alloc *alloc)
 176 {
 177         if (alloc->capacity == 0 && alloc->sublevels[0])
 178                 return NULL; /* All IDs allocated and the capacity looped. */
 179
 180         return find_or_create_page(alloc, alloc->capacity, 1);
 181 }
 182
 183 /*
 184  * Marks an ID within an allocator page as in use.
 185  * If the ID was the last free ID in the page, the page is removed from the
 186  * allocator's list of free IDs. In the typical allocation case, this page is
 187  * the first page in the list, and removing the page is fast. If instead an ID
 188  * is being reserved by number, this may end up scanning the whole single linked
 189  * list of pages in order to remove it.
 190  */
 191 static void reserve_bit(struct id_alloc *alloc, struct id_alloc_page *page,
 192                         int word, int offset)
 193 {
 194         struct id_alloc_page *itr;
 195
 196         page->allocated_mask[word] |= ((uint32_t)1) << offset;
 197         alloc->allocated += 1;
 198
 199         if (page->allocated_mask[word] == UINT32_MAX) {
 200                 page->full_word_mask |= ((uint32_t)1) << word;
 201                 if (page->full_word_mask == UINT32_MAX) {
 202                         if (alloc->has_free == page) {
 203                                 /* allocate always pulls from alloc->has_free */
 204                                 alloc->has_free = page->next_has_free;
 205                         } else {
 206                                 /* reserve could pull from any page with free
 207                                  * bits
 208                                  */
 209                                 itr = alloc->has_free;
 210                                 while (itr) {
 211                                         if (itr->next_has_free == page) {
 212                                                 itr->next_has_free =
 213                                                         page->next_has_free;
 214                                                 return;
 215                                         }
 216
 217                                         itr = itr->next_has_free;
 218                                 }
 219                         }
 220                 }
 221         }
 222 }
 223
 224 /*
 225  * Reserve an ID number from the allocator. Returns IDALLOC_INVALID (0) if the
 226  * allocator has no more IDs available.
 227  */
 228 uint32_t idalloc_allocate(struct id_alloc *alloc)
 229 {
 230         struct id_alloc_page *page;
 231         int word, offset;
 232         uint32_t return_value;
 233
 234         if (alloc->has_free == NULL)
 235                 create_next_page(alloc);
 236
 237         if (alloc->has_free == NULL) {
 238                 flog_err(EC_LIB_ID_EXHAUST,
 239                         "ID Allocator %s has run out of IDs.", alloc->name);
 240                 return IDALLOC_INVALID;
 241         }
 242
 243         page = alloc->has_free;
 244         word = FFS32(~(page->full_word_mask)) - 1;
 245
 246         if (word < 0 || word >= 32) {
 247                 flog_err(EC_LIB_ID_CONSISTENCY,
 248                         "ID Allocator %s internal error. Page starting at %d is inconsistent.",
 249                         alloc->name, page->base_value);
 250                 return IDALLOC_INVALID;
 251         }
 252
 253         offset = FFS32(~(page->allocated_mask[word])) - 1;
 254         if (offset < 0 || offset >= 32) {
 255                 flog_err(EC_LIB_ID_CONSISTENCY,
 256                         "ID Allocator %s internal error. Page starting at %d is inconsistent on word %d",
 257                         alloc->name, page->base_value, word);
 258                 return IDALLOC_INVALID;
 259         }
 260         return_value = page->base_value + word * 32 + offset;
 261
 262         reserve_bit(alloc, page, word, offset);
 263
 264         return return_value;
 265 }
 266
 267 /*
 268  * Tries to allocate a specific ID from the allocator. Returns IDALLOC_INVALID
 269  * when the ID being "reserved" has allready been assigned/reserved. This should
 270  * only be done with low numbered IDs, as the allocator needs to reserve bit-map
 271  * pages in order
 272  */
 273 uint32_t idalloc_reserve(struct id_alloc *alloc, uint32_t id)
 274 {
 275         struct id_alloc_page *page;
 276         int word, offset;
 277
 278         while (alloc->capacity <= id)
 279                 create_next_page(alloc);
 280
 281         word = ID_WORD(id);
 282         offset = ID_OFFSET(id);
 283         page = find_or_create_page(alloc, id, 0);
 284         /* page can't be null because the loop above ensured it was created. */
 285
 286         if (page->allocated_mask[word] & (((uint32_t)1) << offset)) {
 287                 flog_err(EC_LIB_ID_CONSISTENCY,
 288                         "ID Allocator %s could not reserve %" PRIu32
 289                         " because it is already allocated.",
 290                         alloc->name, id);
 291                 return IDALLOC_INVALID;
 292         }
 293
 294         reserve_bit(alloc, page, word, offset);
 295         return id;
 296 }
 297
 298 /*
 299  * Set up an empty ID allocator, with IDALLOC_INVALID pre-reserved.
 300  */
 301 struct id_alloc *idalloc_new(const char *name)
 302 {
 303         struct id_alloc *ret;
 304
 305         ret = XCALLOC(MTYPE_IDALLOC_ALLOCATOR, sizeof(*ret));
 306         ret->name = XSTRDUP(MTYPE_IDALLOC_ALLOCATOR_NAME, name);
 307
 308         idalloc_reserve(ret, IDALLOC_INVALID);
 309
 310         return ret;
 311 }
 312
 313 /*
 314  * Free a subdir, and all pages below it.
 315  */
 316 static void idalloc_destroy_subdir(struct id_alloc_subdir *subdir)
 317 {
 318         int i;
 319
 320         for (i = 0; i < IDALLOC_PAGE_COUNT; i++) {
 321                 if (subdir->sublevels[i])
 322                         XFREE(MTYPE_IDALLOC_PAGE, subdir->sublevels[i]);
 323                 else
 324                         break;
 325         }
 326         XFREE(MTYPE_IDALLOC_SUBDIRECTORY, subdir);
 327 }
 328
 329 /*
 330  * Free a dir, and all subdirs/pages below it.
 331  */
 332 static void idalloc_destroy_dir(struct id_alloc_dir *dir)
 333 {
 334         int i;
 335
 336         for (i = 0; i < IDALLOC_SUBDIR_COUNT; i++) {
 337                 if (dir->sublevels[i])
 338                         idalloc_destroy_subdir(dir->sublevels[i]);
 339                 else
 340                         break;
 341         }
 342         XFREE(MTYPE_IDALLOC_DIRECTORY, dir);
 343 }
 344
 345 /*
 346  * Free all memory associated with an ID allocator.
 347  */
 348 void idalloc_destroy(struct id_alloc *alloc)
 349 {
 350         int i;
 351
 352         for (i = 0; i < IDALLOC_DIR_COUNT; i++) {
 353                 if (alloc->sublevels[i])
 354                         idalloc_destroy_dir(alloc->sublevels[i]);
 355                 else
 356                         break;
 357         }
 358
 359         XFREE(MTYPE_IDALLOC_ALLOCATOR_NAME, alloc->name);
 360         XFREE(MTYPE_IDALLOC_ALLOCATOR, alloc);
 361 }
 362
 363 /*
 364  * Give an ID number to temporary holding pool.
 365  */
 366 void idalloc_free_to_pool(struct id_alloc_pool **pool_ptr, uint32_t id)
 367 {
 368         struct id_alloc_pool *new_pool;
 369
 370         new_pool = XMALLOC(MTYPE_IDALLOC_POOL, sizeof(*new_pool));
 371         new_pool->id = id;
 372         new_pool->next = *pool_ptr;
 373         *pool_ptr = new_pool;
 374 }
 375
 376 /*
 377  * Free all ID numbers held in a holding pool back to the main allocator.
 378  */
 379 void idalloc_drain_pool(struct id_alloc *alloc, struct id_alloc_pool **pool_ptr)
 380 {
 381         struct id_alloc_pool *current, *next;
 382
 383         while (*pool_ptr) {
 384                 current = *pool_ptr;
 385                 next = current->next;
 386                 idalloc_free(alloc, current->id);
 387                 XFREE(MTYPE_IDALLOC_POOL, current);
 388                 *pool_ptr = next;
 389         }
 390 }
 391
 392 /*
 393  * Allocate an ID from either a holding pool, or the main allocator. IDs will
 394  * only be pulled form the main allocator when the pool is empty.
 395  */
 396 uint32_t idalloc_allocate_prefer_pool(struct id_alloc *alloc,
 397                                       struct id_alloc_pool **pool_ptr)
 398 {
 399         uint32_t ret;
 400         struct id_alloc_pool *pool_head = *pool_ptr;
 401
 402         if (pool_head) {
 403                 ret = pool_head->id;
 404                 *pool_ptr = pool_head->next;
 405                 XFREE(MTYPE_IDALLOC_POOL, pool_head);
 406                 return ret;
 407         } else {
 408                 return idalloc_allocate(alloc);
 409         }
 410 }