]> git.proxmox.com Git - mirror_frr.git/blob - lib/id_alloc.c
Merge pull request #13278 from FRRouting/mergify/bp/stable/8.5/pr-13269
[mirror_frr.git] / 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 }