]>
Commit | Line | Data |
---|---|---|
a94eca09 MS |
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 | ||
2618a52e DL |
20 | #ifdef HAVE_CONFIG_H |
21 | #include "config.h" | |
22 | #endif | |
23 | ||
a94eca09 MS |
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 | ||
bf8d3d6a DL |
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"); | |
a94eca09 | 35 | DEFINE_MTYPE_STATIC(LIB, IDALLOC_SUBDIRECTORY, |
bf8d3d6a DL |
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"); | |
a94eca09 MS |
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) | |
4a600b08 | 50 | #define FRR_ID_PAGE_MASK ((1<<IDALLOC_PAGE_BITS)-1) |
a94eca09 MS |
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) | |
4a600b08 | 58 | #define FRR_ID_PAGE_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS) |
a94eca09 MS |
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) | |
4a600b08 | 64 | #define ID_PAGE(id) ((id >> FRR_ID_PAGE_SHIFT) & FRR_ID_PAGE_MASK) |
a94eca09 MS |
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 | ||
4a600b08 | 106 | alloc->capacity += 1 << FRR_ID_PAGE_SHIFT; |
a94eca09 MS |
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, | |
6cde4b45 | 112 | "ID Allocator %s attempt to re-create page at %u", |
a94eca09 MS |
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, | |
6cde4b45 | 135 | "ID Allocator %s cannot free #%u. ID Block does not exist.", |
a94eca09 MS |
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, | |
6cde4b45 | 145 | "ID Allocator %s cannot free #%u. ID was not allocated at the time of free.", |
a94eca09 MS |
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, | |
6cde4b45 | 287 | "ID Allocator %s could not reserve %u because it is already allocated.", |
a94eca09 MS |
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 | } |