[mirror_frr.git] / lib / id_alloc.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * FRR ID Number Allocator
 * Copyright (C) 2018  Amazon.com, Inc. or its affiliates
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "id_alloc.h"

#include "log.h"
#include "lib_errors.h"
#include "memory.h"

#include <inttypes.h>

DEFINE_MTYPE_STATIC(LIB, IDALLOC_ALLOCATOR, "ID Number Allocator");
DEFINE_MTYPE_STATIC(LIB, IDALLOC_ALLOCATOR_NAME, "ID Number Allocator Name");
DEFINE_MTYPE_STATIC(LIB, IDALLOC_DIRECTORY, "ID Number Allocator Directory");
DEFINE_MTYPE_STATIC(LIB, IDALLOC_SUBDIRECTORY,
		    "ID Number Allocator Subdirectory");
DEFINE_MTYPE_STATIC(LIB, IDALLOC_PAGE, "ID Number Allocator Page");
DEFINE_MTYPE_STATIC(LIB, IDALLOC_POOL,
		    "ID Number temporary holding pool entry");

#if UINT_MAX >= UINT32_MAX
#define FFS32(x) ffs(x)
#else
/* ints less than 32 bits? Yikes. */
#define FFS32(x) ffsl(x)
#endif

#define DIR_MASK    ((1<<IDALLOC_DIR_BITS)-1)
#define SUBDIR_MASK ((1<<IDALLOC_SUBDIR_BITS)-1)
#define FRR_ID_PAGE_MASK ((1<<IDALLOC_PAGE_BITS)-1)
#define WORD_MASK   ((1<<IDALLOC_WORD_BITS)-1)
#define OFFSET_MASK ((1<<IDALLOC_OFFSET_BITS)-1)

#define DIR_SHIFT    (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS + \
		      IDALLOC_PAGE_BITS + IDALLOC_SUBDIR_BITS)
#define SUBDIR_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS + \
		      IDALLOC_PAGE_BITS)
#define FRR_ID_PAGE_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS)
#define WORD_SHIFT   (IDALLOC_OFFSET_BITS)
#define OFFSET_SHIFT (0)

#define ID_DIR(id)    ((id >> DIR_SHIFT)    & DIR_MASK)
#define ID_SUBDIR(id) ((id >> SUBDIR_SHIFT) & SUBDIR_MASK)
#define ID_PAGE(id)   ((id >> FRR_ID_PAGE_SHIFT) & FRR_ID_PAGE_MASK)
#define ID_WORD(id)   ((id >> WORD_SHIFT)   & WORD_MASK)
#define ID_OFFSET(id) ((id >> OFFSET_SHIFT) & OFFSET_MASK)

/*
 * Find the page that an ID number belongs to in an allocator.
 * Optionally create the page if it doesn't exist.
 */
static struct id_alloc_page *find_or_create_page(struct id_alloc *alloc,
						 uint32_t id, int create)
{
	struct id_alloc_dir *dir = NULL;
	struct id_alloc_subdir *subdir = NULL;
	struct id_alloc_page *page = NULL;

	dir = alloc->sublevels[ID_DIR(id)];
	if (dir == NULL) {
		if (create) {
			dir = XCALLOC(MTYPE_IDALLOC_DIRECTORY, sizeof(*dir));
			alloc->sublevels[ID_DIR(id)] = dir;
		} else {
			return NULL;
		}
	}

	subdir = dir->sublevels[ID_SUBDIR(id)];
	if (subdir == NULL) {
		if (create) {
			subdir = XCALLOC(MTYPE_IDALLOC_SUBDIRECTORY,
					 sizeof(*subdir));
			dir->sublevels[ID_SUBDIR(id)] = subdir;
		} else {
			return NULL;
		}
	}

	page = subdir->sublevels[ID_PAGE(id)];
	if (page == NULL && create) {
		page = XCALLOC(MTYPE_IDALLOC_PAGE, sizeof(*page));
		page->base_value = id;
		subdir->sublevels[ID_PAGE(id)] = page;

		alloc->capacity += 1 << FRR_ID_PAGE_SHIFT;
		page->next_has_free = alloc->has_free;
		alloc->has_free = page;
	} else if (page != NULL && create) {
		flog_err(
			EC_LIB_ID_CONSISTENCY,
			"ID Allocator %s attempt to re-create page at %u",
			alloc->name, id);
	}

	return page;
}

/*
 * Return an ID number back to the allocator.
 * While this ID can be re-assigned through idalloc_allocate, the underlying
 * memory will not be freed. If this is the first free ID in the page, the page
 * will be added to the allocator's list of pages with free IDs.
 */
void idalloc_free(struct id_alloc *alloc, uint32_t id)
{
	struct id_alloc_page *page = NULL;

	int word, offset;
	uint32_t old_word, old_word_mask;

	page = find_or_create_page(alloc, id, 0);
	if (!page) {
		flog_err(EC_LIB_ID_CONSISTENCY,
			"ID Allocator %s cannot free #%u. ID Block does not exist.",
			alloc->name, id);
		return;
	}

	word = ID_WORD(id);
	offset = ID_OFFSET(id);

	if ((page->allocated_mask[word] & (1 << offset)) == 0) {
		flog_err(EC_LIB_ID_CONSISTENCY,
			"ID Allocator %s cannot free #%u. ID was not allocated at the time of free.",
			alloc->name, id);
		return;
	}

	old_word = page->allocated_mask[word];
	page->allocated_mask[word] &= ~(((uint32_t)1) << offset);
	alloc->allocated -= 1;

	if (old_word == UINT32_MAX) {
		/* first bit in this block of 32 to be freed.*/

		old_word_mask = page->full_word_mask;
		page->full_word_mask &= ~(((uint32_t)1) << word);

		if (old_word_mask == UINT32_MAX) {
			/* first bit in page freed, add this to the allocator's
			 * list of pages with free space
			 */
			page->next_has_free = alloc->has_free;
			alloc->has_free = page;
		}
	}
}

/*
 * Add a allocation page to the end of the allocator's current range.
 * Returns null if the allocator has had all possible pages allocated already.
 */
static struct id_alloc_page *create_next_page(struct id_alloc *alloc)
{
	if (alloc->capacity == 0 && alloc->sublevels[0])
		return NULL; /* All IDs allocated and the capacity looped. */

	return find_or_create_page(alloc, alloc->capacity, 1);
}

/*
 * Marks an ID within an allocator page as in use.
 * If the ID was the last free ID in the page, the page is removed from the
 * allocator's list of free IDs. In the typical allocation case, this page is
 * the first page in the list, and removing the page is fast. If instead an ID
 * is being reserved by number, this may end up scanning the whole single linked
 * list of pages in order to remove it.
 */
static void reserve_bit(struct id_alloc *alloc, struct id_alloc_page *page,
			int word, int offset)
{
	struct id_alloc_page *itr;

	page->allocated_mask[word] |= ((uint32_t)1) << offset;
	alloc->allocated += 1;

	if (page->allocated_mask[word] == UINT32_MAX) {
		page->full_word_mask |= ((uint32_t)1) << word;
		if (page->full_word_mask == UINT32_MAX) {
			if (alloc->has_free == page) {
				/* allocate always pulls from alloc->has_free */
				alloc->has_free = page->next_has_free;
			} else {
				/* reserve could pull from any page with free
				 * bits
				 */
				itr = alloc->has_free;
				while (itr) {
					if (itr->next_has_free == page) {
						itr->next_has_free =
							page->next_has_free;
						return;
					}

					itr = itr->next_has_free;
				}
			}
		}
	}
}

/*
 * Reserve an ID number from the allocator. Returns IDALLOC_INVALID (0) if the
 * allocator has no more IDs available.
 */
uint32_t idalloc_allocate(struct id_alloc *alloc)
{
	struct id_alloc_page *page;
	int word, offset;
	uint32_t return_value;

	if (alloc->has_free == NULL)
		create_next_page(alloc);

	if (alloc->has_free == NULL) {
		flog_err(EC_LIB_ID_EXHAUST,
			"ID Allocator %s has run out of IDs.", alloc->name);
		return IDALLOC_INVALID;
	}

	page = alloc->has_free;
	word = FFS32(~(page->full_word_mask)) - 1;

	if (word < 0 || word >= 32) {
		flog_err(EC_LIB_ID_CONSISTENCY,
			"ID Allocator %s internal error. Page starting at %d is inconsistent.",
			alloc->name, page->base_value);
		return IDALLOC_INVALID;
	}

	offset = FFS32(~(page->allocated_mask[word])) - 1;
	if (offset < 0 || offset >= 32) {
		flog_err(EC_LIB_ID_CONSISTENCY,
			"ID Allocator %s internal error. Page starting at %d is inconsistent on word %d",
			alloc->name, page->base_value, word);
		return IDALLOC_INVALID;
	}
	return_value = page->base_value + word * 32 + offset;

	reserve_bit(alloc, page, word, offset);

	return return_value;
}

/*
 * Tries to allocate a specific ID from the allocator. Returns IDALLOC_INVALID
 * when the ID being "reserved" has allready been assigned/reserved. This should
 * only be done with low numbered IDs, as the allocator needs to reserve bit-map
 * pages in order
 */
uint32_t idalloc_reserve(struct id_alloc *alloc, uint32_t id)
{
	struct id_alloc_page *page;
	int word, offset;

	while (alloc->capacity <= id)
		create_next_page(alloc);

	word = ID_WORD(id);
	offset = ID_OFFSET(id);
	page = find_or_create_page(alloc, id, 0);
	/* page can't be null because the loop above ensured it was created. */

	if (page->allocated_mask[word] & (((uint32_t)1) << offset)) {
		flog_err(EC_LIB_ID_CONSISTENCY,
			"ID Allocator %s could not reserve %u because it is already allocated.",
			alloc->name, id);
		return IDALLOC_INVALID;
	}

	reserve_bit(alloc, page, word, offset);
	return id;
}

/*
 * Set up an empty ID allocator, with IDALLOC_INVALID pre-reserved.
 */
struct id_alloc *idalloc_new(const char *name)
{
	struct id_alloc *ret;

	ret = XCALLOC(MTYPE_IDALLOC_ALLOCATOR, sizeof(*ret));
	ret->name = XSTRDUP(MTYPE_IDALLOC_ALLOCATOR_NAME, name);

	idalloc_reserve(ret, IDALLOC_INVALID);

	return ret;
}

/*
 * Free a subdir, and all pages below it.
 */
static void idalloc_destroy_subdir(struct id_alloc_subdir *subdir)
{
	int i;

	for (i = 0; i < IDALLOC_PAGE_COUNT; i++) {
		if (subdir->sublevels[i])
			XFREE(MTYPE_IDALLOC_PAGE, subdir->sublevels[i]);
		else
			break;
	}
	XFREE(MTYPE_IDALLOC_SUBDIRECTORY, subdir);
}

/*
 * Free a dir, and all subdirs/pages below it.
 */
static void idalloc_destroy_dir(struct id_alloc_dir *dir)
{
	int i;

	for (i = 0; i < IDALLOC_SUBDIR_COUNT; i++) {
		if (dir->sublevels[i])
			idalloc_destroy_subdir(dir->sublevels[i]);
		else
			break;
	}
	XFREE(MTYPE_IDALLOC_DIRECTORY, dir);
}

/*
 * Free all memory associated with an ID allocator.
 */
void idalloc_destroy(struct id_alloc *alloc)
{
	int i;

	for (i = 0; i < IDALLOC_DIR_COUNT; i++) {
		if (alloc->sublevels[i])
			idalloc_destroy_dir(alloc->sublevels[i]);
		else
			break;
	}

	XFREE(MTYPE_IDALLOC_ALLOCATOR_NAME, alloc->name);
	XFREE(MTYPE_IDALLOC_ALLOCATOR, alloc);
}

/*
 * Give an ID number to temporary holding pool.
 */
void idalloc_free_to_pool(struct id_alloc_pool **pool_ptr, uint32_t id)
{
	struct id_alloc_pool *new_pool;

	new_pool = XMALLOC(MTYPE_IDALLOC_POOL, sizeof(*new_pool));
	new_pool->id = id;
	new_pool->next = *pool_ptr;
	*pool_ptr = new_pool;
}

/*
 * Free all ID numbers held in a holding pool back to the main allocator.
 */
void idalloc_drain_pool(struct id_alloc *alloc, struct id_alloc_pool **pool_ptr)
{
	struct id_alloc_pool *current, *next;

	while (*pool_ptr) {
		current = *pool_ptr;
		next = current->next;
		idalloc_free(alloc, current->id);
		XFREE(MTYPE_IDALLOC_POOL, current);
		*pool_ptr = next;
	}
}

/*
 * Allocate an ID from either a holding pool, or the main allocator. IDs will
 * only be pulled form the main allocator when the pool is empty.
 */
uint32_t idalloc_allocate_prefer_pool(struct id_alloc *alloc,
				      struct id_alloc_pool **pool_ptr)
{
	uint32_t ret;
	struct id_alloc_pool *pool_head = *pool_ptr;

	if (pool_head) {
		ret = pool_head->id;
		*pool_ptr = pool_head->next;
		XFREE(MTYPE_IDALLOC_POOL, pool_head);
		return ret;
	} else {
		return idalloc_allocate(alloc);
	}
}
Commit	Line	Data
acddc0ed	1	// SPDX-License-Identifier: GPL-2.0-or-later
a94eca09 MS	2	/*
	3	* FRR ID Number Allocator
	4	* Copyright (C) 2018 Amazon.com, Inc. or its affiliates
a94eca09 MS	5	*/
a94eca09 MS	6
2618a52e DL	7	#ifdef HAVE_CONFIG_H
	8	#include "config.h"
	9	#endif
	10
a94eca09 MS	11	#include "id_alloc.h"
	12
	13	#include "log.h"
	14	#include "lib_errors.h"
	15	#include "memory.h"
	16
	17	#include <inttypes.h>
	18
bf8d3d6a DL	19	DEFINE_MTYPE_STATIC(LIB, IDALLOC_ALLOCATOR, "ID Number Allocator");
	20	DEFINE_MTYPE_STATIC(LIB, IDALLOC_ALLOCATOR_NAME, "ID Number Allocator Name");
	21	DEFINE_MTYPE_STATIC(LIB, IDALLOC_DIRECTORY, "ID Number Allocator Directory");
a94eca09	22	DEFINE_MTYPE_STATIC(LIB, IDALLOC_SUBDIRECTORY,
bf8d3d6a DL	23	"ID Number Allocator Subdirectory");
	24	DEFINE_MTYPE_STATIC(LIB, IDALLOC_PAGE, "ID Number Allocator Page");
	25	DEFINE_MTYPE_STATIC(LIB, IDALLOC_POOL,
	26	"ID Number temporary holding pool entry");
a94eca09 MS	27
	28	#if UINT_MAX >= UINT32_MAX
	29	#define FFS32(x) ffs(x)
	30	#else
	31	/* ints less than 32 bits? Yikes. */
	32	#define FFS32(x) ffsl(x)
	33	#endif
	34
	35	#define DIR_MASK ((1<<IDALLOC_DIR_BITS)-1)
	36	#define SUBDIR_MASK ((1<<IDALLOC_SUBDIR_BITS)-1)
4a600b08	37	#define FRR_ID_PAGE_MASK ((1<<IDALLOC_PAGE_BITS)-1)
a94eca09 MS	38	#define WORD_MASK ((1<<IDALLOC_WORD_BITS)-1)
	39	#define OFFSET_MASK ((1<<IDALLOC_OFFSET_BITS)-1)
	40
	41	#define DIR_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS + \
	42	IDALLOC_PAGE_BITS + IDALLOC_SUBDIR_BITS)
	43	#define SUBDIR_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS + \
	44	IDALLOC_PAGE_BITS)
4a600b08	45	#define FRR_ID_PAGE_SHIFT (IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS)
a94eca09 MS	46	#define WORD_SHIFT (IDALLOC_OFFSET_BITS)
	47	#define OFFSET_SHIFT (0)
	48
	49	#define ID_DIR(id) ((id >> DIR_SHIFT) & DIR_MASK)
	50	#define ID_SUBDIR(id) ((id >> SUBDIR_SHIFT) & SUBDIR_MASK)
4a600b08	51	#define ID_PAGE(id) ((id >> FRR_ID_PAGE_SHIFT) & FRR_ID_PAGE_MASK)
a94eca09 MS	52	#define ID_WORD(id) ((id >> WORD_SHIFT) & WORD_MASK)
	53	#define ID_OFFSET(id) ((id >> OFFSET_SHIFT) & OFFSET_MASK)
	54
	55	/*
	56	* Find the page that an ID number belongs to in an allocator.
	57	* Optionally create the page if it doesn't exist.
	58	*/
	59	static struct id_alloc_page find_or_create_page(struct id_alloc alloc,
	60	uint32_t id, int create)
	61	{
	62	struct id_alloc_dir *dir = NULL;
	63	struct id_alloc_subdir *subdir = NULL;
	64	struct id_alloc_page *page = NULL;
	65
	66	dir = alloc->sublevels[ID_DIR(id)];
	67	if (dir == NULL) {
	68	if (create) {
	69	dir = XCALLOC(MTYPE_IDALLOC_DIRECTORY, sizeof(*dir));
	70	alloc->sublevels[ID_DIR(id)] = dir;
	71	} else {
	72	return NULL;
	73	}
	74	}
	75
	76	subdir = dir->sublevels[ID_SUBDIR(id)];
	77	if (subdir == NULL) {
	78	if (create) {
	79	subdir = XCALLOC(MTYPE_IDALLOC_SUBDIRECTORY,
	80	sizeof(*subdir));
	81	dir->sublevels[ID_SUBDIR(id)] = subdir;
	82	} else {
	83	return NULL;
	84	}
	85	}
	86
	87	page = subdir->sublevels[ID_PAGE(id)];
	88	if (page == NULL && create) {
	89	page = XCALLOC(MTYPE_IDALLOC_PAGE, sizeof(*page));
	90	page->base_value = id;
	91	subdir->sublevels[ID_PAGE(id)] = page;
	92
4a600b08	93	alloc->capacity += 1 << FRR_ID_PAGE_SHIFT;
a94eca09 MS	94	page->next_has_free = alloc->has_free;
	95	alloc->has_free = page;
	96	} else if (page != NULL && create) {
	97	flog_err(
	98	EC_LIB_ID_CONSISTENCY,
6cde4b45	99	"ID Allocator %s attempt to re-create page at %u",
a94eca09 MS	100	alloc->name, id);
	101	}
	102
	103	return page;
	104	}
	105
	106	/*
	107	* Return an ID number back to the allocator.
	108	* While this ID can be re-assigned through idalloc_allocate, the underlying
	109	* memory will not be freed. If this is the first free ID in the page, the page
	110	* will be added to the allocator's list of pages with free IDs.
	111	*/
	112	void idalloc_free(struct id_alloc *alloc, uint32_t id)
	113	{
	114	struct id_alloc_page *page = NULL;
	115
	116	int word, offset;
	117	uint32_t old_word, old_word_mask;
	118
	119	page = find_or_create_page(alloc, id, 0);
	120	if (!page) {
	121	flog_err(EC_LIB_ID_CONSISTENCY,
6cde4b45	122	"ID Allocator %s cannot free #%u. ID Block does not exist.",
a94eca09 MS	123	alloc->name, id);
	124	return;
	125	}
	126
	127	word = ID_WORD(id);
	128	offset = ID_OFFSET(id);
	129
	130	if ((page->allocated_mask[word] & (1 << offset)) == 0) {
	131	flog_err(EC_LIB_ID_CONSISTENCY,
6cde4b45	132	"ID Allocator %s cannot free #%u. ID was not allocated at the time of free.",
a94eca09 MS	133	alloc->name, id);
	134	return;
	135	}
	136
	137	old_word = page->allocated_mask[word];
	138	page->allocated_mask[word] &= ~(((uint32_t)1) << offset);
	139	alloc->allocated -= 1;
	140
	141	if (old_word == UINT32_MAX) {
	142	/* first bit in this block of 32 to be freed.*/
	143
	144	old_word_mask = page->full_word_mask;
	145	page->full_word_mask &= ~(((uint32_t)1) << word);
	146
	147	if (old_word_mask == UINT32_MAX) {
	148	/* first bit in page freed, add this to the allocator's
	149	* list of pages with free space
	150	*/
	151	page->next_has_free = alloc->has_free;
	152	alloc->has_free = page;
	153	}
	154	}
	155	}
	156
	157	/*
	158	* Add a allocation page to the end of the allocator's current range.
	159	* Returns null if the allocator has had all possible pages allocated already.
	160	*/
	161	static struct id_alloc_page create_next_page(struct id_alloc alloc)
	162	{
	163	if (alloc->capacity == 0 && alloc->sublevels[0])
	164	return NULL; /* All IDs allocated and the capacity looped. */
	165
	166	return find_or_create_page(alloc, alloc->capacity, 1);
	167	}
	168
	169	/*
	170	* Marks an ID within an allocator page as in use.
	171	* If the ID was the last free ID in the page, the page is removed from the
	172	* allocator's list of free IDs. In the typical allocation case, this page is
	173	* the first page in the list, and removing the page is fast. If instead an ID
	174	* is being reserved by number, this may end up scanning the whole single linked
	175	* list of pages in order to remove it.
	176	*/
	177	static void reserve_bit(struct id_alloc alloc, struct id_alloc_page page,
	178	int word, int offset)
	179	{
	180	struct id_alloc_page *itr;
	181
	182	page->allocated_mask[word] \|= ((uint32_t)1) << offset;
	183	alloc->allocated += 1;
	184
	185	if (page->allocated_mask[word] == UINT32_MAX) {
	186	page->full_word_mask \|= ((uint32_t)1) << word;
	187	if (page->full_word_mask == UINT32_MAX) {
	188	if (alloc->has_free == page) {
	189	/* allocate always pulls from alloc->has_free */
	190	alloc->has_free = page->next_has_free;
	191	} else {
	192	/* reserve could pull from any page with free
	193	* bits
	194	*/
	195	itr = alloc->has_free;
	196	while (itr) {
197	if (itr->next_has_free == page) {
198	itr->next_has_free =
199	page->next_has_free;
200	return;
201	}
202
203	itr = itr->next_has_free;
204	}
205	}
206	}
207	}
208	}
209
210	/*
211	* Reserve an ID number from the allocator. Returns IDALLOC_INVALID (0) if the
212	* allocator has no more IDs available.
213	*/
214	uint32_t idalloc_allocate(struct id_alloc *alloc)
215	{
216	struct id_alloc_page *page;
217	int word, offset;
218	uint32_t return_value;
219
220	if (alloc->has_free == NULL)
221	create_next_page(alloc);
222
223	if (alloc->has_free == NULL) {
224	flog_err(EC_LIB_ID_EXHAUST,
225	"ID Allocator %s has run out of IDs.", alloc->name);
226	return IDALLOC_INVALID;
227	}
228
229	page = alloc->has_free;
230	word = FFS32(~(page->full_word_mask)) - 1;
231
232	if (word < 0 \|\| word >= 32) {
233	flog_err(EC_LIB_ID_CONSISTENCY,
234	"ID Allocator %s internal error. Page starting at %d is inconsistent.",
235	alloc->name, page->base_value);
236	return IDALLOC_INVALID;
237	}
238
239	offset = FFS32(~(page->allocated_mask[word])) - 1;
240	if (offset < 0 \|\| offset >= 32) {
241	flog_err(EC_LIB_ID_CONSISTENCY,
242	"ID Allocator %s internal error. Page starting at %d is inconsistent on word %d",
243	alloc->name, page->base_value, word);
244	return IDALLOC_INVALID;
245	}
246	return_value = page->base_value + word * 32 + offset;
247
248	reserve_bit(alloc, page, word, offset);
249
250	return return_value;
251	}
252
253	/*
254	* Tries to allocate a specific ID from the allocator. Returns IDALLOC_INVALID
255	* when the ID being "reserved" has allready been assigned/reserved. This should
256	* only be done with low numbered IDs, as the allocator needs to reserve bit-map
257	* pages in order
258	*/
259	uint32_t idalloc_reserve(struct id_alloc *alloc, uint32_t id)
260	{
261	struct id_alloc_page *page;
262	int word, offset;
263
264	while (alloc->capacity <= id)
265	create_next_page(alloc);
266
267	word = ID_WORD(id);
268	offset = ID_OFFSET(id);
269	page = find_or_create_page(alloc, id, 0);
270	/* page can't be null because the loop above ensured it was created. */
271
272	if (page->allocated_mask[word] & (((uint32_t)1) << offset)) {
273	flog_err(EC_LIB_ID_CONSISTENCY,
6cde4b45	274	"ID Allocator %s could not reserve %u because it is already allocated.",
a94eca09 MS	275	alloc->name, id);
	276	return IDALLOC_INVALID;
	277	}
	278
	279	reserve_bit(alloc, page, word, offset);
	280	return id;
	281	}
	282
	283	/*
	284	* Set up an empty ID allocator, with IDALLOC_INVALID pre-reserved.
	285	*/
	286	struct id_alloc idalloc_new(const char name)
	287	{
	288	struct id_alloc *ret;
	289
	290	ret = XCALLOC(MTYPE_IDALLOC_ALLOCATOR, sizeof(*ret));
	291	ret->name = XSTRDUP(MTYPE_IDALLOC_ALLOCATOR_NAME, name);
	292
	293	idalloc_reserve(ret, IDALLOC_INVALID);
	294
	295	return ret;
	296	}
	297
	298	/*
	299	* Free a subdir, and all pages below it.
	300	*/
	301	static void idalloc_destroy_subdir(struct id_alloc_subdir *subdir)
	302	{
	303	int i;
	304
	305	for (i = 0; i < IDALLOC_PAGE_COUNT; i++) {
	306	if (subdir->sublevels[i])
	307	XFREE(MTYPE_IDALLOC_PAGE, subdir->sublevels[i]);
	308	else
	309	break;
	310	}
	311	XFREE(MTYPE_IDALLOC_SUBDIRECTORY, subdir);
	312	}
	313
	314	/*
	315	* Free a dir, and all subdirs/pages below it.
	316	*/
	317	static void idalloc_destroy_dir(struct id_alloc_dir *dir)
	318	{
	319	int i;
	320
	321	for (i = 0; i < IDALLOC_SUBDIR_COUNT; i++) {
	322	if (dir->sublevels[i])
	323	idalloc_destroy_subdir(dir->sublevels[i]);
	324	else
	325	break;
	326	}
	327	XFREE(MTYPE_IDALLOC_DIRECTORY, dir);
	328	}
	329
	330	/*
	331	* Free all memory associated with an ID allocator.
	332	*/
	333	void idalloc_destroy(struct id_alloc *alloc)
	334	{
	335	int i;
	336
	337	for (i = 0; i < IDALLOC_DIR_COUNT; i++) {
	338	if (alloc->sublevels[i])
339	idalloc_destroy_dir(alloc->sublevels[i]);
340	else
341	break;
342	}
343
344	XFREE(MTYPE_IDALLOC_ALLOCATOR_NAME, alloc->name);
345	XFREE(MTYPE_IDALLOC_ALLOCATOR, alloc);
346	}
347
348	/*
349	* Give an ID number to temporary holding pool.
350	*/
351	void idalloc_free_to_pool(struct id_alloc_pool **pool_ptr, uint32_t id)
352	{
353	struct id_alloc_pool *new_pool;
354
355	new_pool = XMALLOC(MTYPE_IDALLOC_POOL, sizeof(*new_pool));
356	new_pool->id = id;
357	new_pool->next = *pool_ptr;
358	*pool_ptr = new_pool;
359	}
360
361	/*
362	* Free all ID numbers held in a holding pool back to the main allocator.
363	*/
364	void idalloc_drain_pool(struct id_alloc alloc, struct id_alloc_pool *pool_ptr)
365	{
366	struct id_alloc_pool current, next;
367
368	while (*pool_ptr) {
369	current = *pool_ptr;
370	next = current->next;
371	idalloc_free(alloc, current->id);
372	XFREE(MTYPE_IDALLOC_POOL, current);
373	*pool_ptr = next;
374	}
375	}
376
377	/*
378	* Allocate an ID from either a holding pool, or the main allocator. IDs will
379	* only be pulled form the main allocator when the pool is empty.
380	*/
381	uint32_t idalloc_allocate_prefer_pool(struct id_alloc *alloc,
382	struct id_alloc_pool **pool_ptr)
383	{
384	uint32_t ret;
385	struct id_alloc_pool pool_head = pool_ptr;
386
387	if (pool_head) {
388	ret = pool_head->id;
389	*pool_ptr = pool_head->next;
390	XFREE(MTYPE_IDALLOC_POOL, pool_head);
391	return ret;
392	} else {
393	return idalloc_allocate(alloc);
394	}
395	}