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 %u",
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 #%u. ID Block does not exist.",
140 offset
= ID_OFFSET(id
);
142 if ((page
->allocated_mask
[word
] & (1 << offset
)) == 0) {
143 flog_err(EC_LIB_ID_CONSISTENCY
,
144 "ID Allocator %s cannot free #%u. ID was not allocated at the time of free.",
149 old_word
= page
->allocated_mask
[word
];
150 page
->allocated_mask
[word
] &= ~(((uint32_t)1) << offset
);
151 alloc
->allocated
-= 1;
153 if (old_word
== UINT32_MAX
) {
154 /* first bit in this block of 32 to be freed.*/
156 old_word_mask
= page
->full_word_mask
;
157 page
->full_word_mask
&= ~(((uint32_t)1) << word
);
159 if (old_word_mask
== UINT32_MAX
) {
160 /* first bit in page freed, add this to the allocator's
161 * list of pages with free space
163 page
->next_has_free
= alloc
->has_free
;
164 alloc
->has_free
= page
;
170 * Add a allocation page to the end of the allocator's current range.
171 * Returns null if the allocator has had all possible pages allocated already.
173 static struct id_alloc_page
*create_next_page(struct id_alloc
*alloc
)
175 if (alloc
->capacity
== 0 && alloc
->sublevels
[0])
176 return NULL
; /* All IDs allocated and the capacity looped. */
178 return find_or_create_page(alloc
, alloc
->capacity
, 1);
182 * Marks an ID within an allocator page as in use.
183 * If the ID was the last free ID in the page, the page is removed from the
184 * allocator's list of free IDs. In the typical allocation case, this page is
185 * the first page in the list, and removing the page is fast. If instead an ID
186 * is being reserved by number, this may end up scanning the whole single linked
187 * list of pages in order to remove it.
189 static void reserve_bit(struct id_alloc
*alloc
, struct id_alloc_page
*page
,
190 int word
, int offset
)
192 struct id_alloc_page
*itr
;
194 page
->allocated_mask
[word
] |= ((uint32_t)1) << offset
;
195 alloc
->allocated
+= 1;
197 if (page
->allocated_mask
[word
] == UINT32_MAX
) {
198 page
->full_word_mask
|= ((uint32_t)1) << word
;
199 if (page
->full_word_mask
== UINT32_MAX
) {
200 if (alloc
->has_free
== page
) {
201 /* allocate always pulls from alloc->has_free */
202 alloc
->has_free
= page
->next_has_free
;
204 /* reserve could pull from any page with free
207 itr
= alloc
->has_free
;
209 if (itr
->next_has_free
== page
) {
215 itr
= itr
->next_has_free
;
223 * Reserve an ID number from the allocator. Returns IDALLOC_INVALID (0) if the
224 * allocator has no more IDs available.
226 uint32_t idalloc_allocate(struct id_alloc
*alloc
)
228 struct id_alloc_page
*page
;
230 uint32_t return_value
;
232 if (alloc
->has_free
== NULL
)
233 create_next_page(alloc
);
235 if (alloc
->has_free
== NULL
) {
236 flog_err(EC_LIB_ID_EXHAUST
,
237 "ID Allocator %s has run out of IDs.", alloc
->name
);
238 return IDALLOC_INVALID
;
241 page
= alloc
->has_free
;
242 word
= FFS32(~(page
->full_word_mask
)) - 1;
244 if (word
< 0 || word
>= 32) {
245 flog_err(EC_LIB_ID_CONSISTENCY
,
246 "ID Allocator %s internal error. Page starting at %d is inconsistent.",
247 alloc
->name
, page
->base_value
);
248 return IDALLOC_INVALID
;
251 offset
= FFS32(~(page
->allocated_mask
[word
])) - 1;
252 if (offset
< 0 || offset
>= 32) {
253 flog_err(EC_LIB_ID_CONSISTENCY
,
254 "ID Allocator %s internal error. Page starting at %d is inconsistent on word %d",
255 alloc
->name
, page
->base_value
, word
);
256 return IDALLOC_INVALID
;
258 return_value
= page
->base_value
+ word
* 32 + offset
;
260 reserve_bit(alloc
, page
, word
, offset
);
266 * Tries to allocate a specific ID from the allocator. Returns IDALLOC_INVALID
267 * when the ID being "reserved" has allready been assigned/reserved. This should
268 * only be done with low numbered IDs, as the allocator needs to reserve bit-map
271 uint32_t idalloc_reserve(struct id_alloc
*alloc
, uint32_t id
)
273 struct id_alloc_page
*page
;
276 while (alloc
->capacity
<= id
)
277 create_next_page(alloc
);
280 offset
= ID_OFFSET(id
);
281 page
= find_or_create_page(alloc
, id
, 0);
282 /* page can't be null because the loop above ensured it was created. */
284 if (page
->allocated_mask
[word
] & (((uint32_t)1) << offset
)) {
285 flog_err(EC_LIB_ID_CONSISTENCY
,
286 "ID Allocator %s could not reserve %u because it is already allocated.",
288 return IDALLOC_INVALID
;
291 reserve_bit(alloc
, page
, word
, offset
);
296 * Set up an empty ID allocator, with IDALLOC_INVALID pre-reserved.
298 struct id_alloc
*idalloc_new(const char *name
)
300 struct id_alloc
*ret
;
302 ret
= XCALLOC(MTYPE_IDALLOC_ALLOCATOR
, sizeof(*ret
));
303 ret
->name
= XSTRDUP(MTYPE_IDALLOC_ALLOCATOR_NAME
, name
);
305 idalloc_reserve(ret
, IDALLOC_INVALID
);
311 * Free a subdir, and all pages below it.
313 static void idalloc_destroy_subdir(struct id_alloc_subdir
*subdir
)
317 for (i
= 0; i
< IDALLOC_PAGE_COUNT
; i
++) {
318 if (subdir
->sublevels
[i
])
319 XFREE(MTYPE_IDALLOC_PAGE
, subdir
->sublevels
[i
]);
323 XFREE(MTYPE_IDALLOC_SUBDIRECTORY
, subdir
);
327 * Free a dir, and all subdirs/pages below it.
329 static void idalloc_destroy_dir(struct id_alloc_dir
*dir
)
333 for (i
= 0; i
< IDALLOC_SUBDIR_COUNT
; i
++) {
334 if (dir
->sublevels
[i
])
335 idalloc_destroy_subdir(dir
->sublevels
[i
]);
339 XFREE(MTYPE_IDALLOC_DIRECTORY
, dir
);
343 * Free all memory associated with an ID allocator.
345 void idalloc_destroy(struct id_alloc
*alloc
)
349 for (i
= 0; i
< IDALLOC_DIR_COUNT
; i
++) {
350 if (alloc
->sublevels
[i
])
351 idalloc_destroy_dir(alloc
->sublevels
[i
]);
356 XFREE(MTYPE_IDALLOC_ALLOCATOR_NAME
, alloc
->name
);
357 XFREE(MTYPE_IDALLOC_ALLOCATOR
, alloc
);
361 * Give an ID number to temporary holding pool.
363 void idalloc_free_to_pool(struct id_alloc_pool
**pool_ptr
, uint32_t id
)
365 struct id_alloc_pool
*new_pool
;
367 new_pool
= XMALLOC(MTYPE_IDALLOC_POOL
, sizeof(*new_pool
));
369 new_pool
->next
= *pool_ptr
;
370 *pool_ptr
= new_pool
;
374 * Free all ID numbers held in a holding pool back to the main allocator.
376 void idalloc_drain_pool(struct id_alloc
*alloc
, struct id_alloc_pool
**pool_ptr
)
378 struct id_alloc_pool
*current
, *next
;
382 next
= current
->next
;
383 idalloc_free(alloc
, current
->id
);
384 XFREE(MTYPE_IDALLOC_POOL
, current
);
390 * Allocate an ID from either a holding pool, or the main allocator. IDs will
391 * only be pulled form the main allocator when the pool is empty.
393 uint32_t idalloc_allocate_prefer_pool(struct id_alloc
*alloc
,
394 struct id_alloc_pool
**pool_ptr
)
397 struct id_alloc_pool
*pool_head
= *pool_ptr
;
401 *pool_ptr
= pool_head
->next
;
402 XFREE(MTYPE_IDALLOC_POOL
, pool_head
);
405 return idalloc_allocate(alloc
);