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