Line data Source code
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 670 : DEFINE_MTYPE_STATIC(LIB, IDALLOC_ALLOCATOR, "ID Number Allocator");
33 670 : DEFINE_MTYPE_STATIC(LIB, IDALLOC_ALLOCATOR_NAME, "ID Number Allocator Name");
34 670 : DEFINE_MTYPE_STATIC(LIB, IDALLOC_DIRECTORY, "ID Number Allocator Directory");
35 670 : DEFINE_MTYPE_STATIC(LIB, IDALLOC_SUBDIRECTORY,
36 : "ID Number Allocator Subdirectory");
37 670 : DEFINE_MTYPE_STATIC(LIB, IDALLOC_PAGE, "ID Number Allocator Page");
38 670 : 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 7 : static struct id_alloc_page *find_or_create_page(struct id_alloc *alloc,
73 : uint32_t id, int create)
74 : {
75 7 : struct id_alloc_dir *dir = NULL;
76 7 : struct id_alloc_subdir *subdir = NULL;
77 7 : struct id_alloc_page *page = NULL;
78 :
79 7 : dir = alloc->sublevels[ID_DIR(id)];
80 7 : if (dir == NULL) {
81 1 : if (create) {
82 1 : dir = XCALLOC(MTYPE_IDALLOC_DIRECTORY, sizeof(*dir));
83 1 : alloc->sublevels[ID_DIR(id)] = dir;
84 : } else {
85 : return NULL;
86 : }
87 : }
88 :
89 7 : subdir = dir->sublevels[ID_SUBDIR(id)];
90 7 : if (subdir == NULL) {
91 1 : if (create) {
92 1 : subdir = XCALLOC(MTYPE_IDALLOC_SUBDIRECTORY,
93 : sizeof(*subdir));
94 1 : dir->sublevels[ID_SUBDIR(id)] = subdir;
95 : } else {
96 : return NULL;
97 : }
98 : }
99 :
100 7 : page = subdir->sublevels[ID_PAGE(id)];
101 7 : if (page == NULL && create) {
102 1 : page = XCALLOC(MTYPE_IDALLOC_PAGE, sizeof(*page));
103 1 : page->base_value = id;
104 1 : subdir->sublevels[ID_PAGE(id)] = page;
105 :
106 1 : alloc->capacity += 1 << FRR_ID_PAGE_SHIFT;
107 1 : page->next_has_free = alloc->has_free;
108 1 : alloc->has_free = page;
109 6 : } else if (page != NULL && create) {
110 0 : 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 4 : void idalloc_free(struct id_alloc *alloc, uint32_t id)
126 : {
127 4 : struct id_alloc_page *page = NULL;
128 :
129 4 : int word, offset;
130 4 : uint32_t old_word, old_word_mask;
131 :
132 4 : page = find_or_create_page(alloc, id, 0);
133 4 : if (!page) {
134 0 : flog_err(EC_LIB_ID_CONSISTENCY,
135 : "ID Allocator %s cannot free #%u. ID Block does not exist.",
136 : alloc->name, id);
137 0 : return;
138 : }
139 :
140 4 : word = ID_WORD(id);
141 4 : offset = ID_OFFSET(id);
142 :
143 4 : if ((page->allocated_mask[word] & (1 << offset)) == 0) {
144 0 : 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 0 : return;
148 : }
149 :
150 4 : old_word = page->allocated_mask[word];
151 4 : page->allocated_mask[word] &= ~(((uint32_t)1) << offset);
152 4 : alloc->allocated -= 1;
153 :
154 4 : if (old_word == UINT32_MAX) {
155 : /* first bit in this block of 32 to be freed.*/
156 :
157 0 : old_word_mask = page->full_word_mask;
158 0 : page->full_word_mask &= ~(((uint32_t)1) << word);
159 :
160 0 : 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 0 : page->next_has_free = alloc->has_free;
165 0 : 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 1 : static struct id_alloc_page *create_next_page(struct id_alloc *alloc)
175 : {
176 1 : if (alloc->capacity == 0 && alloc->sublevels[0])
177 : return NULL; /* All IDs allocated and the capacity looped. */
178 :
179 1 : 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 6 : static void reserve_bit(struct id_alloc *alloc, struct id_alloc_page *page,
191 : int word, int offset)
192 : {
193 6 : struct id_alloc_page *itr;
194 :
195 6 : page->allocated_mask[word] |= ((uint32_t)1) << offset;
196 6 : alloc->allocated += 1;
197 :
198 6 : if (page->allocated_mask[word] == UINT32_MAX) {
199 0 : page->full_word_mask |= ((uint32_t)1) << word;
200 0 : if (page->full_word_mask == UINT32_MAX) {
201 0 : if (alloc->has_free == page) {
202 : /* allocate always pulls from alloc->has_free */
203 0 : 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 0 : while (itr) {
210 0 : if (itr->next_has_free == page) {
211 0 : itr->next_has_free =
212 0 : page->next_has_free;
213 0 : 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 4 : uint32_t idalloc_allocate(struct id_alloc *alloc)
228 : {
229 4 : struct id_alloc_page *page;
230 4 : int word, offset;
231 4 : uint32_t return_value;
232 :
233 4 : if (alloc->has_free == NULL)
234 0 : create_next_page(alloc);
235 :
236 4 : if (alloc->has_free == NULL) {
237 0 : flog_err(EC_LIB_ID_EXHAUST,
238 : "ID Allocator %s has run out of IDs.", alloc->name);
239 0 : return IDALLOC_INVALID;
240 : }
241 :
242 4 : page = alloc->has_free;
243 4 : word = FFS32(~(page->full_word_mask)) - 1;
244 :
245 4 : if (word < 0 || word >= 32) {
246 0 : 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 0 : return IDALLOC_INVALID;
250 : }
251 :
252 4 : offset = FFS32(~(page->allocated_mask[word])) - 1;
253 4 : if (offset < 0 || offset >= 32) {
254 0 : 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 0 : return IDALLOC_INVALID;
258 : }
259 4 : return_value = page->base_value + word * 32 + offset;
260 :
261 4 : reserve_bit(alloc, page, word, offset);
262 :
263 4 : 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 2 : uint32_t idalloc_reserve(struct id_alloc *alloc, uint32_t id)
273 : {
274 2 : struct id_alloc_page *page;
275 2 : int word, offset;
276 :
277 3 : while (alloc->capacity <= id)
278 1 : create_next_page(alloc);
279 :
280 2 : word = ID_WORD(id);
281 2 : offset = ID_OFFSET(id);
282 2 : page = find_or_create_page(alloc, id, 0);
283 : /* page can't be null because the loop above ensured it was created. */
284 :
285 2 : if (page->allocated_mask[word] & (((uint32_t)1) << offset)) {
286 0 : flog_err(EC_LIB_ID_CONSISTENCY,
287 : "ID Allocator %s could not reserve %u because it is already allocated.",
288 : alloc->name, id);
289 0 : return IDALLOC_INVALID;
290 : }
291 :
292 2 : reserve_bit(alloc, page, word, offset);
293 2 : return id;
294 : }
295 :
296 : /*
297 : * Set up an empty ID allocator, with IDALLOC_INVALID pre-reserved.
298 : */
299 1 : struct id_alloc *idalloc_new(const char *name)
300 : {
301 1 : struct id_alloc *ret;
302 :
303 1 : ret = XCALLOC(MTYPE_IDALLOC_ALLOCATOR, sizeof(*ret));
304 1 : ret->name = XSTRDUP(MTYPE_IDALLOC_ALLOCATOR_NAME, name);
305 :
306 1 : idalloc_reserve(ret, IDALLOC_INVALID);
307 :
308 1 : return ret;
309 : }
310 :
311 : /*
312 : * Free a subdir, and all pages below it.
313 : */
314 1 : static void idalloc_destroy_subdir(struct id_alloc_subdir *subdir)
315 : {
316 1 : int i;
317 :
318 2 : for (i = 0; i < IDALLOC_PAGE_COUNT; i++) {
319 2 : if (subdir->sublevels[i])
320 1 : XFREE(MTYPE_IDALLOC_PAGE, subdir->sublevels[i]);
321 : else
322 : break;
323 : }
324 1 : XFREE(MTYPE_IDALLOC_SUBDIRECTORY, subdir);
325 1 : }
326 :
327 : /*
328 : * Free a dir, and all subdirs/pages below it.
329 : */
330 1 : static void idalloc_destroy_dir(struct id_alloc_dir *dir)
331 : {
332 1 : int i;
333 :
334 2 : for (i = 0; i < IDALLOC_SUBDIR_COUNT; i++) {
335 2 : if (dir->sublevels[i])
336 1 : idalloc_destroy_subdir(dir->sublevels[i]);
337 : else
338 : break;
339 : }
340 1 : XFREE(MTYPE_IDALLOC_DIRECTORY, dir);
341 1 : }
342 :
343 : /*
344 : * Free all memory associated with an ID allocator.
345 : */
346 1 : void idalloc_destroy(struct id_alloc *alloc)
347 : {
348 1 : int i;
349 :
350 2 : for (i = 0; i < IDALLOC_DIR_COUNT; i++) {
351 2 : if (alloc->sublevels[i])
352 1 : idalloc_destroy_dir(alloc->sublevels[i]);
353 : else
354 : break;
355 : }
356 :
357 1 : XFREE(MTYPE_IDALLOC_ALLOCATOR_NAME, alloc->name);
358 1 : XFREE(MTYPE_IDALLOC_ALLOCATOR, alloc);
359 1 : }
360 :
361 : /*
362 : * Give an ID number to temporary holding pool.
363 : */
364 0 : void idalloc_free_to_pool(struct id_alloc_pool **pool_ptr, uint32_t id)
365 : {
366 0 : struct id_alloc_pool *new_pool;
367 :
368 0 : new_pool = XMALLOC(MTYPE_IDALLOC_POOL, sizeof(*new_pool));
369 0 : new_pool->id = id;
370 0 : new_pool->next = *pool_ptr;
371 0 : *pool_ptr = new_pool;
372 0 : }
373 :
374 : /*
375 : * Free all ID numbers held in a holding pool back to the main allocator.
376 : */
377 857 : void idalloc_drain_pool(struct id_alloc *alloc, struct id_alloc_pool **pool_ptr)
378 : {
379 857 : struct id_alloc_pool *current, *next;
380 :
381 857 : while (*pool_ptr) {
382 0 : current = *pool_ptr;
383 0 : next = current->next;
384 0 : idalloc_free(alloc, current->id);
385 0 : XFREE(MTYPE_IDALLOC_POOL, current);
386 0 : *pool_ptr = next;
387 : }
388 857 : }
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 4 : uint32_t idalloc_allocate_prefer_pool(struct id_alloc *alloc,
395 : struct id_alloc_pool **pool_ptr)
396 : {
397 4 : uint32_t ret;
398 4 : struct id_alloc_pool *pool_head = *pool_ptr;
399 :
400 4 : if (pool_head) {
401 0 : ret = pool_head->id;
402 0 : *pool_ptr = pool_head->next;
403 0 : XFREE(MTYPE_IDALLOC_POOL, pool_head);
404 0 : return ret;
405 : } else {
406 4 : return idalloc_allocate(alloc);
407 : }
408 : }
|
