2 * FRR ID Number Allocator
3 * Copyright (C) 2018 Amazon.com, Inc. or its affiliates
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)
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
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
27 #include "lib_errors.h"
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")
40 #if UINT_MAX >= UINT32_MAX
41 #define FFS32(x) ffs(x)
43 /* ints less than 32 bits? Yikes. */
44 #define FFS32(x) ffsl(x)
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)
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 + \
57 #define FRR_ID_PAGE_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS)
58 #define WORD_SHIFT (IDALLOC_OFFSET_BITS)
59 #define OFFSET_SHIFT (0)
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)
68 * Find the page that an ID number belongs to in an allocator.
69 * Optionally create the page if it doesn't exist.
71 static struct id_alloc_page
*find_or_create_page(struct id_alloc
*alloc
,
72 uint32_t id
, int create
)
74 struct id_alloc_dir
*dir
= NULL
;
75 struct id_alloc_subdir
*subdir
= NULL
;
76 struct id_alloc_page
*page
= NULL
;
78 dir
= alloc
->sublevels
[ID_DIR(id
)];
81 dir
= XCALLOC(MTYPE_IDALLOC_DIRECTORY
, sizeof(*dir
));
82 alloc
->sublevels
[ID_DIR(id
)] = dir
;
88 subdir
= dir
->sublevels
[ID_SUBDIR(id
)];
91 subdir
= XCALLOC(MTYPE_IDALLOC_SUBDIRECTORY
,
93 dir
->sublevels
[ID_SUBDIR(id
)] = subdir
;
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
;
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
) {
110 EC_LIB_ID_CONSISTENCY
,
111 "ID Allocator %s attempt to re-create page at %" PRIu32
,
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.
124 void idalloc_free(struct id_alloc
*alloc
, uint32_t id
)
126 struct id_alloc_page
*page
= NULL
;
129 uint32_t old_word
, old_word_mask
;
131 page
= find_or_create_page(alloc
, id
, 0);
133 flog_err(EC_LIB_ID_CONSISTENCY
,
134 "ID Allocator %s cannot free #%" PRIu32
135 ". ID Block does not exist.",
141 offset
= ID_OFFSET(id
);
143 if ((page
->allocated_mask
[word
] & (1 << offset
)) == 0) {
144 flog_err(EC_LIB_ID_CONSISTENCY
,
145 "ID Allocator %s cannot free #%" PRIu32
146 ". ID was not allocated at the time of free.",
151 old_word
= page
->allocated_mask
[word
];
152 page
->allocated_mask
[word
] &= ~(((uint32_t)1) << offset
);
153 alloc
->allocated
-= 1;
155 if (old_word
== UINT32_MAX
) {
156 /* first bit in this block of 32 to be freed.*/
158 old_word_mask
= page
->full_word_mask
;
159 page
->full_word_mask
&= ~(((uint32_t)1) << word
);
161 if (old_word_mask
== UINT32_MAX
) {
162 /* first bit in page freed, add this to the allocator's
163 * list of pages with free space
165 page
->next_has_free
= alloc
->has_free
;
166 alloc
->has_free
= page
;
172 * Add a allocation page to the end of the allocator's current range.
173 * Returns null if the allocator has had all possible pages allocated already.
175 static struct id_alloc_page
*create_next_page(struct id_alloc
*alloc
)
177 if (alloc
->capacity
== 0 && alloc
->sublevels
[0])
178 return NULL
; /* All IDs allocated and the capacity looped. */
180 return find_or_create_page(alloc
, alloc
->capacity
, 1);
184 * Marks an ID within an allocator page as in use.
185 * If the ID was the last free ID in the page, the page is removed from the
186 * allocator's list of free IDs. In the typical allocation case, this page is
187 * the first page in the list, and removing the page is fast. If instead an ID
188 * is being reserved by number, this may end up scanning the whole single linked
189 * list of pages in order to remove it.
191 static void reserve_bit(struct id_alloc
*alloc
, struct id_alloc_page
*page
,
192 int word
, int offset
)
194 struct id_alloc_page
*itr
;
196 page
->allocated_mask
[word
] |= ((uint32_t)1) << offset
;
197 alloc
->allocated
+= 1;
199 if (page
->allocated_mask
[word
] == UINT32_MAX
) {
200 page
->full_word_mask
|= ((uint32_t)1) << word
;
201 if (page
->full_word_mask
== UINT32_MAX
) {
202 if (alloc
->has_free
== page
) {
203 /* allocate always pulls from alloc->has_free */
204 alloc
->has_free
= page
->next_has_free
;
206 /* reserve could pull from any page with free
209 itr
= alloc
->has_free
;
211 if (itr
->next_has_free
== page
) {
217 itr
= itr
->next_has_free
;
225 * Reserve an ID number from the allocator. Returns IDALLOC_INVALID (0) if the
226 * allocator has no more IDs available.
228 uint32_t idalloc_allocate(struct id_alloc
*alloc
)
230 struct id_alloc_page
*page
;
232 uint32_t return_value
;
234 if (alloc
->has_free
== NULL
)
235 create_next_page(alloc
);
237 if (alloc
->has_free
== NULL
) {
238 flog_err(EC_LIB_ID_EXHAUST
,
239 "ID Allocator %s has run out of IDs.", alloc
->name
);
240 return IDALLOC_INVALID
;
243 page
= alloc
->has_free
;
244 word
= FFS32(~(page
->full_word_mask
)) - 1;
246 if (word
< 0 || word
>= 32) {
247 flog_err(EC_LIB_ID_CONSISTENCY
,
248 "ID Allocator %s internal error. Page starting at %d is inconsistent.",
249 alloc
->name
, page
->base_value
);
250 return IDALLOC_INVALID
;
253 offset
= FFS32(~(page
->allocated_mask
[word
])) - 1;
254 if (offset
< 0 || offset
>= 32) {
255 flog_err(EC_LIB_ID_CONSISTENCY
,
256 "ID Allocator %s internal error. Page starting at %d is inconsistent on word %d",
257 alloc
->name
, page
->base_value
, word
);
258 return IDALLOC_INVALID
;
260 return_value
= page
->base_value
+ word
* 32 + offset
;
262 reserve_bit(alloc
, page
, word
, offset
);
268 * Tries to allocate a specific ID from the allocator. Returns IDALLOC_INVALID
269 * when the ID being "reserved" has allready been assigned/reserved. This should
270 * only be done with low numbered IDs, as the allocator needs to reserve bit-map
273 uint32_t idalloc_reserve(struct id_alloc
*alloc
, uint32_t id
)
275 struct id_alloc_page
*page
;
278 while (alloc
->capacity
<= id
)
279 create_next_page(alloc
);
282 offset
= ID_OFFSET(id
);
283 page
= find_or_create_page(alloc
, id
, 0);
284 /* page can't be null because the loop above ensured it was created. */
286 if (page
->allocated_mask
[word
] & (((uint32_t)1) << offset
)) {
287 flog_err(EC_LIB_ID_CONSISTENCY
,
288 "ID Allocator %s could not reserve %" PRIu32
289 " because it is already allocated.",
291 return IDALLOC_INVALID
;
294 reserve_bit(alloc
, page
, word
, offset
);
299 * Set up an empty ID allocator, with IDALLOC_INVALID pre-reserved.
301 struct id_alloc
*idalloc_new(const char *name
)
303 struct id_alloc
*ret
;
305 ret
= XCALLOC(MTYPE_IDALLOC_ALLOCATOR
, sizeof(*ret
));
306 ret
->name
= XSTRDUP(MTYPE_IDALLOC_ALLOCATOR_NAME
, name
);
308 idalloc_reserve(ret
, IDALLOC_INVALID
);
314 * Free a subdir, and all pages below it.
316 static void idalloc_destroy_subdir(struct id_alloc_subdir
*subdir
)
320 for (i
= 0; i
< IDALLOC_PAGE_COUNT
; i
++) {
321 if (subdir
->sublevels
[i
])
322 XFREE(MTYPE_IDALLOC_PAGE
, subdir
->sublevels
[i
]);
326 XFREE(MTYPE_IDALLOC_SUBDIRECTORY
, subdir
);
330 * Free a dir, and all subdirs/pages below it.
332 static void idalloc_destroy_dir(struct id_alloc_dir
*dir
)
336 for (i
= 0; i
< IDALLOC_SUBDIR_COUNT
; i
++) {
337 if (dir
->sublevels
[i
])
338 idalloc_destroy_subdir(dir
->sublevels
[i
]);
342 XFREE(MTYPE_IDALLOC_DIRECTORY
, dir
);
346 * Free all memory associated with an ID allocator.
348 void idalloc_destroy(struct id_alloc
*alloc
)
352 for (i
= 0; i
< IDALLOC_DIR_COUNT
; i
++) {
353 if (alloc
->sublevels
[i
])
354 idalloc_destroy_dir(alloc
->sublevels
[i
]);
359 XFREE(MTYPE_IDALLOC_ALLOCATOR_NAME
, alloc
->name
);
360 XFREE(MTYPE_IDALLOC_ALLOCATOR
, alloc
);
364 * Give an ID number to temporary holding pool.
366 void idalloc_free_to_pool(struct id_alloc_pool
**pool_ptr
, uint32_t id
)
368 struct id_alloc_pool
*new_pool
;
370 new_pool
= XMALLOC(MTYPE_IDALLOC_POOL
, sizeof(*new_pool
));
372 new_pool
->next
= *pool_ptr
;
373 *pool_ptr
= new_pool
;
377 * Free all ID numbers held in a holding pool back to the main allocator.
379 void idalloc_drain_pool(struct id_alloc
*alloc
, struct id_alloc_pool
**pool_ptr
)
381 struct id_alloc_pool
*current
, *next
;
385 next
= current
->next
;
386 idalloc_free(alloc
, current
->id
);
387 XFREE(MTYPE_IDALLOC_POOL
, current
);
393 * Allocate an ID from either a holding pool, or the main allocator. IDs will
394 * only be pulled form the main allocator when the pool is empty.
396 uint32_t idalloc_allocate_prefer_pool(struct id_alloc
*alloc
,
397 struct id_alloc_pool
**pool_ptr
)
400 struct id_alloc_pool
*pool_head
= *pool_ptr
;
404 *pool_ptr
= pool_head
->next
;
405 XFREE(MTYPE_IDALLOC_POOL
, pool_head
);
408 return idalloc_allocate(alloc
);