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
23 #include "lib_errors.h"
28 DEFINE_MTYPE_STATIC(LIB
, IDALLOC_ALLOCATOR
, "ID Number Allocator")
29 DEFINE_MTYPE_STATIC(LIB
, IDALLOC_ALLOCATOR_NAME
, "ID Number Allocator Name")
30 DEFINE_MTYPE_STATIC(LIB
, IDALLOC_DIRECTORY
, "ID Number Allocator Directory")
31 DEFINE_MTYPE_STATIC(LIB
, IDALLOC_SUBDIRECTORY
,
32 "ID Number Allocator Subdirectory")
33 DEFINE_MTYPE_STATIC(LIB
, IDALLOC_PAGE
, "ID Number Allocator Page")
34 DEFINE_MTYPE_STATIC(LIB
, IDALLOC_POOL
, "ID Number temporary holding pool entry")
36 #if UINT_MAX >= UINT32_MAX
37 #define FFS32(x) ffs(x)
39 /* ints less than 32 bits? Yikes. */
40 #define FFS32(x) ffsl(x)
43 #define DIR_MASK ((1<<IDALLOC_DIR_BITS)-1)
44 #define SUBDIR_MASK ((1<<IDALLOC_SUBDIR_BITS)-1)
45 #define FRR_ID_PAGE_MASK ((1<<IDALLOC_PAGE_BITS)-1)
46 #define WORD_MASK ((1<<IDALLOC_WORD_BITS)-1)
47 #define OFFSET_MASK ((1<<IDALLOC_OFFSET_BITS)-1)
49 #define DIR_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS + \
50 IDALLOC_PAGE_BITS + IDALLOC_SUBDIR_BITS)
51 #define SUBDIR_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS + \
53 #define FRR_ID_PAGE_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS)
54 #define WORD_SHIFT (IDALLOC_OFFSET_BITS)
55 #define OFFSET_SHIFT (0)
57 #define ID_DIR(id) ((id >> DIR_SHIFT) & DIR_MASK)
58 #define ID_SUBDIR(id) ((id >> SUBDIR_SHIFT) & SUBDIR_MASK)
59 #define ID_PAGE(id) ((id >> FRR_ID_PAGE_SHIFT) & FRR_ID_PAGE_MASK)
60 #define ID_WORD(id) ((id >> WORD_SHIFT) & WORD_MASK)
61 #define ID_OFFSET(id) ((id >> OFFSET_SHIFT) & OFFSET_MASK)
64 * Find the page that an ID number belongs to in an allocator.
65 * Optionally create the page if it doesn't exist.
67 static struct id_alloc_page
*find_or_create_page(struct id_alloc
*alloc
,
68 uint32_t id
, int create
)
70 struct id_alloc_dir
*dir
= NULL
;
71 struct id_alloc_subdir
*subdir
= NULL
;
72 struct id_alloc_page
*page
= NULL
;
74 dir
= alloc
->sublevels
[ID_DIR(id
)];
77 dir
= XCALLOC(MTYPE_IDALLOC_DIRECTORY
, sizeof(*dir
));
78 alloc
->sublevels
[ID_DIR(id
)] = dir
;
84 subdir
= dir
->sublevels
[ID_SUBDIR(id
)];
87 subdir
= XCALLOC(MTYPE_IDALLOC_SUBDIRECTORY
,
89 dir
->sublevels
[ID_SUBDIR(id
)] = subdir
;
95 page
= subdir
->sublevels
[ID_PAGE(id
)];
96 if (page
== NULL
&& create
) {
97 page
= XCALLOC(MTYPE_IDALLOC_PAGE
, sizeof(*page
));
98 page
->base_value
= id
;
99 subdir
->sublevels
[ID_PAGE(id
)] = page
;
101 alloc
->capacity
+= 1 << FRR_ID_PAGE_SHIFT
;
102 page
->next_has_free
= alloc
->has_free
;
103 alloc
->has_free
= page
;
104 } else if (page
!= NULL
&& create
) {
106 EC_LIB_ID_CONSISTENCY
,
107 "ID Allocator %s attempt to re-create page at %" PRIu32
,
115 * Return an ID number back to the allocator.
116 * While this ID can be re-assigned through idalloc_allocate, the underlying
117 * memory will not be freed. If this is the first free ID in the page, the page
118 * will be added to the allocator's list of pages with free IDs.
120 void idalloc_free(struct id_alloc
*alloc
, uint32_t id
)
122 struct id_alloc_page
*page
= NULL
;
125 uint32_t old_word
, old_word_mask
;
127 page
= find_or_create_page(alloc
, id
, 0);
129 flog_err(EC_LIB_ID_CONSISTENCY
,
130 "ID Allocator %s cannot free #%" PRIu32
131 ". ID Block does not exist.",
137 offset
= ID_OFFSET(id
);
139 if ((page
->allocated_mask
[word
] & (1 << offset
)) == 0) {
140 flog_err(EC_LIB_ID_CONSISTENCY
,
141 "ID Allocator %s cannot free #%" PRIu32
142 ". ID was not allocated at the time of free.",
147 old_word
= page
->allocated_mask
[word
];
148 page
->allocated_mask
[word
] &= ~(((uint32_t)1) << offset
);
149 alloc
->allocated
-= 1;
151 if (old_word
== UINT32_MAX
) {
152 /* first bit in this block of 32 to be freed.*/
154 old_word_mask
= page
->full_word_mask
;
155 page
->full_word_mask
&= ~(((uint32_t)1) << word
);
157 if (old_word_mask
== UINT32_MAX
) {
158 /* first bit in page freed, add this to the allocator's
159 * list of pages with free space
161 page
->next_has_free
= alloc
->has_free
;
162 alloc
->has_free
= page
;
168 * Add a allocation page to the end of the allocator's current range.
169 * Returns null if the allocator has had all possible pages allocated already.
171 static struct id_alloc_page
*create_next_page(struct id_alloc
*alloc
)
173 if (alloc
->capacity
== 0 && alloc
->sublevels
[0])
174 return NULL
; /* All IDs allocated and the capacity looped. */
176 return find_or_create_page(alloc
, alloc
->capacity
, 1);
180 * Marks an ID within an allocator page as in use.
181 * If the ID was the last free ID in the page, the page is removed from the
182 * allocator's list of free IDs. In the typical allocation case, this page is
183 * the first page in the list, and removing the page is fast. If instead an ID
184 * is being reserved by number, this may end up scanning the whole single linked
185 * list of pages in order to remove it.
187 static void reserve_bit(struct id_alloc
*alloc
, struct id_alloc_page
*page
,
188 int word
, int offset
)
190 struct id_alloc_page
*itr
;
192 page
->allocated_mask
[word
] |= ((uint32_t)1) << offset
;
193 alloc
->allocated
+= 1;
195 if (page
->allocated_mask
[word
] == UINT32_MAX
) {
196 page
->full_word_mask
|= ((uint32_t)1) << word
;
197 if (page
->full_word_mask
== UINT32_MAX
) {
198 if (alloc
->has_free
== page
) {
199 /* allocate always pulls from alloc->has_free */
200 alloc
->has_free
= page
->next_has_free
;
202 /* reserve could pull from any page with free
205 itr
= alloc
->has_free
;
207 if (itr
->next_has_free
== page
) {
213 itr
= itr
->next_has_free
;
221 * Reserve an ID number from the allocator. Returns IDALLOC_INVALID (0) if the
222 * allocator has no more IDs available.
224 uint32_t idalloc_allocate(struct id_alloc
*alloc
)
226 struct id_alloc_page
*page
;
228 uint32_t return_value
;
230 if (alloc
->has_free
== NULL
)
231 create_next_page(alloc
);
233 if (alloc
->has_free
== NULL
) {
234 flog_err(EC_LIB_ID_EXHAUST
,
235 "ID Allocator %s has run out of IDs.", alloc
->name
);
236 return IDALLOC_INVALID
;
239 page
= alloc
->has_free
;
240 word
= FFS32(~(page
->full_word_mask
)) - 1;
242 if (word
< 0 || word
>= 32) {
243 flog_err(EC_LIB_ID_CONSISTENCY
,
244 "ID Allocator %s internal error. Page starting at %d is inconsistent.",
245 alloc
->name
, page
->base_value
);
246 return IDALLOC_INVALID
;
249 offset
= FFS32(~(page
->allocated_mask
[word
])) - 1;
250 if (offset
< 0 || offset
>= 32) {
251 flog_err(EC_LIB_ID_CONSISTENCY
,
252 "ID Allocator %s internal error. Page starting at %d is inconsistent on word %d",
253 alloc
->name
, page
->base_value
, word
);
254 return IDALLOC_INVALID
;
256 return_value
= page
->base_value
+ word
* 32 + offset
;
258 reserve_bit(alloc
, page
, word
, offset
);
264 * Tries to allocate a specific ID from the allocator. Returns IDALLOC_INVALID
265 * when the ID being "reserved" has allready been assigned/reserved. This should
266 * only be done with low numbered IDs, as the allocator needs to reserve bit-map
269 uint32_t idalloc_reserve(struct id_alloc
*alloc
, uint32_t id
)
271 struct id_alloc_page
*page
;
274 while (alloc
->capacity
<= id
)
275 create_next_page(alloc
);
278 offset
= ID_OFFSET(id
);
279 page
= find_or_create_page(alloc
, id
, 0);
280 /* page can't be null because the loop above ensured it was created. */
282 if (page
->allocated_mask
[word
] & (((uint32_t)1) << offset
)) {
283 flog_err(EC_LIB_ID_CONSISTENCY
,
284 "ID Allocator %s could not reserve %" PRIu32
285 " because it is already allocated.",
287 return IDALLOC_INVALID
;
290 reserve_bit(alloc
, page
, word
, offset
);
295 * Set up an empty ID allocator, with IDALLOC_INVALID pre-reserved.
297 struct id_alloc
*idalloc_new(const char *name
)
299 struct id_alloc
*ret
;
301 ret
= XCALLOC(MTYPE_IDALLOC_ALLOCATOR
, sizeof(*ret
));
302 ret
->name
= XSTRDUP(MTYPE_IDALLOC_ALLOCATOR_NAME
, name
);
304 idalloc_reserve(ret
, IDALLOC_INVALID
);
310 * Free a subdir, and all pages below it.
312 static void idalloc_destroy_subdir(struct id_alloc_subdir
*subdir
)
316 for (i
= 0; i
< IDALLOC_PAGE_COUNT
; i
++) {
317 if (subdir
->sublevels
[i
])
318 XFREE(MTYPE_IDALLOC_PAGE
, subdir
->sublevels
[i
]);
322 XFREE(MTYPE_IDALLOC_SUBDIRECTORY
, subdir
);
326 * Free a dir, and all subdirs/pages below it.
328 static void idalloc_destroy_dir(struct id_alloc_dir
*dir
)
332 for (i
= 0; i
< IDALLOC_SUBDIR_COUNT
; i
++) {
333 if (dir
->sublevels
[i
])
334 idalloc_destroy_subdir(dir
->sublevels
[i
]);
338 XFREE(MTYPE_IDALLOC_DIRECTORY
, dir
);
342 * Free all memory associated with an ID allocator.
344 void idalloc_destroy(struct id_alloc
*alloc
)
348 for (i
= 0; i
< IDALLOC_DIR_COUNT
; i
++) {
349 if (alloc
->sublevels
[i
])
350 idalloc_destroy_dir(alloc
->sublevels
[i
]);
355 XFREE(MTYPE_IDALLOC_ALLOCATOR_NAME
, alloc
->name
);
356 XFREE(MTYPE_IDALLOC_ALLOCATOR
, alloc
);
360 * Give an ID number to temporary holding pool.
362 void idalloc_free_to_pool(struct id_alloc_pool
**pool_ptr
, uint32_t id
)
364 struct id_alloc_pool
*new_pool
;
366 new_pool
= XMALLOC(MTYPE_IDALLOC_POOL
, sizeof(*new_pool
));
368 new_pool
->next
= *pool_ptr
;
369 *pool_ptr
= new_pool
;
373 * Free all ID numbers held in a holding pool back to the main allocator.
375 void idalloc_drain_pool(struct id_alloc
*alloc
, struct id_alloc_pool
**pool_ptr
)
377 struct id_alloc_pool
*current
, *next
;
381 next
= current
->next
;
382 idalloc_free(alloc
, current
->id
);
383 XFREE(MTYPE_IDALLOC_POOL
, current
);
389 * Allocate an ID from either a holding pool, or the main allocator. IDs will
390 * only be pulled form the main allocator when the pool is empty.
392 uint32_t idalloc_allocate_prefer_pool(struct id_alloc
*alloc
,
393 struct id_alloc_pool
**pool_ptr
)
396 struct id_alloc_pool
*pool_head
= *pool_ptr
;
400 *pool_ptr
= pool_head
->next
;
401 XFREE(MTYPE_IDALLOC_POOL
, pool_head
);
404 return idalloc_allocate(alloc
);