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 %u",
 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 #%u. ID Block does not exist.",
 135                         alloc->name, id);
 136                 return;
 137         }
 138
 139         word = ID_WORD(id);
 140         offset = ID_OFFSET(id);
 141
 142         if ((page->allocated_mask[word] & (1 << offset)) == 0) {
 143                 flog_err(EC_LIB_ID_CONSISTENCY,
 144                         "ID Allocator %s cannot free #%u. ID was not allocated at the time of free.",
 145                         alloc->name, id);
 146                 return;
 147         }
 148
 149         old_word = page->allocated_mask[word];
 150         page->allocated_mask[word] &= ~(((uint32_t)1) << offset);
 151         alloc->allocated -= 1;
 152
 153         if (old_word == UINT32_MAX) {
 154                 /* first bit in this block of 32 to be freed.*/
 155
 156                 old_word_mask = page->full_word_mask;
 157                 page->full_word_mask &= ~(((uint32_t)1) << word);
 158
 159                 if (old_word_mask == UINT32_MAX) {
 160                         /* first bit in page freed, add this to the allocator's
 161                          * list of pages with free space
 162                          */
 163                         page->next_has_free = alloc->has_free;
 164                         alloc->has_free = page;
 165                 }
 166         }
 167 }
 168
 169 /*
 170  * Add a allocation page to the end of the allocator's current range.
 171  * Returns null if the allocator has had all possible pages allocated already.
 172  */
 173 static struct id_alloc_page *create_next_page(struct id_alloc *alloc)
 174 {
 175         if (alloc->capacity == 0 && alloc->sublevels[0])
 176                 return NULL; /* All IDs allocated and the capacity looped. */
 177
 178         return find_or_create_page(alloc, alloc->capacity, 1);
 179 }
 180
 181 /*
 182  * Marks an ID within an allocator page as in use.
 183  * If the ID was the last free ID in the page, the page is removed from the
 184  * allocator's list of free IDs. In the typical allocation case, this page is
 185  * the first page in the list, and removing the page is fast. If instead an ID
 186  * is being reserved by number, this may end up scanning the whole single linked
 187  * list of pages in order to remove it.
 188  */
 189 static void reserve_bit(struct id_alloc *alloc, struct id_alloc_page *page,
 190                         int word, int offset)
 191 {
 192         struct id_alloc_page *itr;
 193
 194         page->allocated_mask[word] |= ((uint32_t)1) << offset;
 195         alloc->allocated += 1;
 196
 197         if (page->allocated_mask[word] == UINT32_MAX) {
 198                 page->full_word_mask |= ((uint32_t)1) << word;
 199                 if (page->full_word_mask == UINT32_MAX) {
 200                         if (alloc->has_free == page) {
 201                                 /* allocate always pulls from alloc->has_free */
 202                                 alloc->has_free = page->next_has_free;
 203                         } else {
 204                                 /* reserve could pull from any page with free
 205                                  * bits
 206                                  */
 207                                 itr = alloc->has_free;
 208                                 while (itr) {
 209                                         if (itr->next_has_free == page) {
 210                                                 itr->next_has_free =
 211                                                         page->next_has_free;
 212                                                 return;
 213                                         }
 214
 215                                         itr = itr->next_has_free;
 216                                 }
 217                         }
 218                 }
 219         }
 220 }
 221
 222 /*
 223  * Reserve an ID number from the allocator. Returns IDALLOC_INVALID (0) if the
 224  * allocator has no more IDs available.
 225  */
 226 uint32_t idalloc_allocate(struct id_alloc *alloc)
 227 {
 228         struct id_alloc_page *page;
 229         int word, offset;
 230         uint32_t return_value;
 231
 232         if (alloc->has_free == NULL)
 233                 create_next_page(alloc);
 234
 235         if (alloc->has_free == NULL) {
 236                 flog_err(EC_LIB_ID_EXHAUST,
 237                         "ID Allocator %s has run out of IDs.", alloc->name);
 238                 return IDALLOC_INVALID;
 239         }
 240
 241         page = alloc->has_free;
 242         word = FFS32(~(page->full_word_mask)) - 1;
 243
 244         if (word < 0 || word >= 32) {
 245                 flog_err(EC_LIB_ID_CONSISTENCY,
 246                         "ID Allocator %s internal error. Page starting at %d is inconsistent.",
 247                         alloc->name, page->base_value);
 248                 return IDALLOC_INVALID;
 249         }
 250
 251         offset = FFS32(~(page->allocated_mask[word])) - 1;
 252         if (offset < 0 || offset >= 32) {
 253                 flog_err(EC_LIB_ID_CONSISTENCY,
 254                         "ID Allocator %s internal error. Page starting at %d is inconsistent on word %d",
 255                         alloc->name, page->base_value, word);
 256                 return IDALLOC_INVALID;
 257         }
 258         return_value = page->base_value + word * 32 + offset;
 259
 260         reserve_bit(alloc, page, word, offset);
 261
 262         return return_value;
 263 }
 264
 265 /*
 266  * Tries to allocate a specific ID from the allocator. Returns IDALLOC_INVALID
 267  * when the ID being "reserved" has allready been assigned/reserved. This should
 268  * only be done with low numbered IDs, as the allocator needs to reserve bit-map
 269  * pages in order
 270  */
 271 uint32_t idalloc_reserve(struct id_alloc *alloc, uint32_t id)
 272 {
 273         struct id_alloc_page *page;
 274         int word, offset;
 275
 276         while (alloc->capacity <= id)
 277                 create_next_page(alloc);
 278
 279         word = ID_WORD(id);
 280         offset = ID_OFFSET(id);
 281         page = find_or_create_page(alloc, id, 0);
 282         /* page can't be null because the loop above ensured it was created. */
 283
 284         if (page->allocated_mask[word] & (((uint32_t)1) << offset)) {
 285                 flog_err(EC_LIB_ID_CONSISTENCY,
 286                         "ID Allocator %s could not reserve %u because it is already allocated.",
 287                         alloc->name, id);
 288                 return IDALLOC_INVALID;
 289         }
 290
 291         reserve_bit(alloc, page, word, offset);
 292         return id;
 293 }
 294
 295 /*
 296  * Set up an empty ID allocator, with IDALLOC_INVALID pre-reserved.
 297  */
 298 struct id_alloc *idalloc_new(const char *name)
 299 {
 300         struct id_alloc *ret;
 301
 302         ret = XCALLOC(MTYPE_IDALLOC_ALLOCATOR, sizeof(*ret));
 303         ret->name = XSTRDUP(MTYPE_IDALLOC_ALLOCATOR_NAME, name);
 304
 305         idalloc_reserve(ret, IDALLOC_INVALID);
 306
 307         return ret;
 308 }
 309
 310 /*
 311  * Free a subdir, and all pages below it.
 312  */
 313 static void idalloc_destroy_subdir(struct id_alloc_subdir *subdir)
 314 {
 315         int i;
 316
 317         for (i = 0; i < IDALLOC_PAGE_COUNT; i++) {
 318                 if (subdir->sublevels[i])
 319                         XFREE(MTYPE_IDALLOC_PAGE, subdir->sublevels[i]);
 320                 else
 321                         break;
 322         }
 323         XFREE(MTYPE_IDALLOC_SUBDIRECTORY, subdir);
 324 }
 325
 326 /*
 327  * Free a dir, and all subdirs/pages below it.
 328  */
 329 static void idalloc_destroy_dir(struct id_alloc_dir *dir)
 330 {
 331         int i;
 332
 333         for (i = 0; i < IDALLOC_SUBDIR_COUNT; i++) {
 334                 if (dir->sublevels[i])
 335                         idalloc_destroy_subdir(dir->sublevels[i]);
 336                 else
 337                         break;
 338         }
 339         XFREE(MTYPE_IDALLOC_DIRECTORY, dir);
 340 }
 341
 342 /*
 343  * Free all memory associated with an ID allocator.
 344  */
 345 void idalloc_destroy(struct id_alloc *alloc)
 346 {
 347         int i;
 348
 349         for (i = 0; i < IDALLOC_DIR_COUNT; i++) {
 350                 if (alloc->sublevels[i])
 351                         idalloc_destroy_dir(alloc->sublevels[i]);
 352                 else
 353                         break;
 354         }
 355
 356         XFREE(MTYPE_IDALLOC_ALLOCATOR_NAME, alloc->name);
 357         XFREE(MTYPE_IDALLOC_ALLOCATOR, alloc);
 358 }
 359
 360 /*
 361  * Give an ID number to temporary holding pool.
 362  */
 363 void idalloc_free_to_pool(struct id_alloc_pool **pool_ptr, uint32_t id)
 364 {
 365         struct id_alloc_pool *new_pool;
 366
 367         new_pool = XMALLOC(MTYPE_IDALLOC_POOL, sizeof(*new_pool));
 368         new_pool->id = id;
 369         new_pool->next = *pool_ptr;
 370         *pool_ptr = new_pool;
 371 }
 372
 373 /*
 374  * Free all ID numbers held in a holding pool back to the main allocator.
 375  */
 376 void idalloc_drain_pool(struct id_alloc *alloc, struct id_alloc_pool **pool_ptr)
 377 {
 378         struct id_alloc_pool *current, *next;
 379
 380         while (*pool_ptr) {
 381                 current = *pool_ptr;
 382                 next = current->next;
 383                 idalloc_free(alloc, current->id);
 384                 XFREE(MTYPE_IDALLOC_POOL, current);
 385                 *pool_ptr = next;
 386         }
 387 }
 388
 389 /*
 390  * Allocate an ID from either a holding pool, or the main allocator. IDs will
 391  * only be pulled form the main allocator when the pool is empty.
 392  */
 393 uint32_t idalloc_allocate_prefer_pool(struct id_alloc *alloc,
 394                                       struct id_alloc_pool **pool_ptr)
 395 {
 396         uint32_t ret;
 397         struct id_alloc_pool *pool_head = *pool_ptr;
 398
 399         if (pool_head) {
 400                 ret = pool_head->id;
 401                 *pool_ptr = pool_head->next;
 402                 XFREE(MTYPE_IDALLOC_POOL, pool_head);
 403                 return ret;
 404         } else {
 405                 return idalloc_allocate(alloc);
 406         }
 407 }