summaryrefslogtreecommitdiffstats
path: root/lib/id_alloc.c
blob: 9179dc4299428da8e0173a01e800d44b54b3f04b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
/*
 * FRR ID Number Allocator
 * Copyright (C) 2018  Amazon.com, Inc. or its affiliates
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 * more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#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);
	}
}