[mirror_frr.git] / tests / lib / test_idalloc.c

#include "id_alloc.h"

#include <inttypes.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>

#define IDS_PER_PAGE (1<<(IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS))
char allocated_markers[IDS_PER_PAGE*3];

int main(int argc, char **argv)
{
	int i, val;
	uint32_t pg;
	struct id_alloc *a;

	/* 1. Rattle test, shake it a little and make sure it doesn't make any
	 * noise :)
	 */
	a = idalloc_new("Rattle test");
	for (i = 0; i < 1000000; i++)
		assert(idalloc_allocate(a) != 0);

	idalloc_destroy(a);

	/* 2. Reserve a few low IDs, make sure they are skipped by normal
	 * allocation.
	 */
	a = idalloc_new("Low Reservations");
	assert(idalloc_reserve(a, 1) == 1);
	assert(idalloc_reserve(a, 3) == 3);
	assert(idalloc_reserve(a, 5) == 5);
	for (i = 0; i < 100; i++) {
		val = idalloc_allocate(a);
		assert(val != 1 && val != 3 && val != 5);
	}
	idalloc_destroy(a);

	/* 3. Single page testing. Check that IDs are kept unique, and all IDs
	 * in the existing page are allocated before a new page is added.
	 */
	memset(allocated_markers, 0, sizeof(allocated_markers));
	allocated_markers[IDALLOC_INVALID] = 1;

	a = idalloc_new("Single Page");

	/* reserve the rest of the first page */
	for (i = 0; i < IDS_PER_PAGE - 1; i++) {
		val = idalloc_allocate(a);
		assert(val < IDS_PER_PAGE);
		assert(allocated_markers[val] == 0);
		assert(a->capacity == IDS_PER_PAGE);
		allocated_markers[val] = 1;
	}
	/* Check that the count is right */
	assert(a->allocated == IDS_PER_PAGE);

	/* Free some IDs out of the middle. */
	idalloc_free(a, 300);
	allocated_markers[300] = 0;
	idalloc_free(a, 400);
	allocated_markers[400] = 0;
	idalloc_free(a, 500);
	allocated_markers[500] = 0;

	assert(a->allocated == IDS_PER_PAGE-3);

	/* Allocate the three IDs back and make sure they are pulled from the
	 * set just freed
	 */
	for (i = 0; i < 3; i++) {
		val = idalloc_allocate(a);
		assert(val < IDS_PER_PAGE);
		assert(allocated_markers[val] == 0);
		assert(a->capacity == IDS_PER_PAGE);
		allocated_markers[val] = 1;
	}
	idalloc_destroy(a);

	/* 4. Multi-page testing. */
	memset(allocated_markers, 0, sizeof(allocated_markers));
	allocated_markers[IDALLOC_INVALID] = 1;

	a = idalloc_new("Multi-page");

	/* reserve the rest of the first page and all of the second and third */
	for (i = 0; i < 3 * IDS_PER_PAGE - 1; i++) {
		val = idalloc_allocate(a);
		assert(val < 3*IDS_PER_PAGE);
		assert(allocated_markers[val] == 0);
		allocated_markers[val] = 1;
	}
	assert(a->capacity == 3*IDS_PER_PAGE);
	assert(a->allocated == 3*IDS_PER_PAGE);

	/* Free two IDs from each page. */
	for (i = 0; i < 3; i++) {
		idalloc_free(a, 7 + i*IDS_PER_PAGE);
		allocated_markers[7 + i*IDS_PER_PAGE] = 0;

		idalloc_free(a, 4 + i*IDS_PER_PAGE);
		allocated_markers[4 + i*IDS_PER_PAGE] = 0;
	}

	assert(a->allocated == 3*IDS_PER_PAGE - 6);

	/* Allocate the six IDs back and make sure they are pulled from the set
	 * just freed.
	 */
	for (i = 0; i < 6; i++) {
		val = idalloc_allocate(a);
		assert(val < 3*IDS_PER_PAGE);
		assert(allocated_markers[val] == 0);
		assert(a->capacity == 3*IDS_PER_PAGE);
		allocated_markers[val] = 1;
	}

	assert(a->capacity == 3*IDS_PER_PAGE);
	assert(a->allocated == 3*IDS_PER_PAGE);

	/* Walk each allocated ID. Free it, then re-allocate it back. */
	for (i = 1; i < 3 * IDS_PER_PAGE - 1; i++) {
		idalloc_free(a, i);
		val = idalloc_allocate(a);
		assert(val == i);
		assert(a->capacity == 3*IDS_PER_PAGE);
		assert(a->allocated == 3*IDS_PER_PAGE);
	}
	idalloc_destroy(a);

	/* 5. Weird Reservations
	 * idalloc_reserve exists primarily to black out low numbered IDs that
	 * are reserved for special cases. However, we will test it for more
	 * complex use cases to avoid unpleasant surprises.
	 */

	memset(allocated_markers, 0, sizeof(allocated_markers));
	allocated_markers[IDALLOC_INVALID] = 1;

	a = idalloc_new("Weird Reservations");

	/* Start with 3 pages fully allocated. */
	for (i = 0; i < 3 * IDS_PER_PAGE - 1; i++) {
		val = idalloc_allocate(a);
		assert(val < 3*IDS_PER_PAGE);
		assert(allocated_markers[val] == 0);
		allocated_markers[val] = 1;
	}
	assert(a->capacity == 3*IDS_PER_PAGE);
	assert(a->allocated == 3*IDS_PER_PAGE);

	/* Free a bit out of each of the three pages. Then reserve one of the
	 * three freed IDs. Finally, allocate the other two freed IDs. Do this
	 * each of three ways. (Reserve out of the first, seconds then third
	 * page.)
	 * The intent here is to exercise the rare cases on reserve_bit's
	 * linked-list removal in the case that it is not removing the first
	 * page with a free bit in its list of pages with free bits.
	 */

	for (pg = 0; pg < 3; pg++) {
		/* free a bit out of each of the three pages */
		for (i = 0; i < 3; i++) {
			idalloc_free(a, i*IDS_PER_PAGE + 17);
			allocated_markers[i*IDS_PER_PAGE + 17] = 0;
		}

		assert(a->capacity == 3*IDS_PER_PAGE);
		assert(a->allocated == 3*IDS_PER_PAGE-3);

		/* Reserve one of the freed IDs */
		assert(idalloc_reserve(a, pg*IDS_PER_PAGE + 17) ==
		       pg*IDS_PER_PAGE + 17);
		allocated_markers[pg*IDS_PER_PAGE + 17] = 1;

		assert(a->capacity == 3*IDS_PER_PAGE);
		assert(a->allocated == 3*IDS_PER_PAGE-2);

		/* Allocate the other two back */
		for (i = 0; i < 2; i++) {
			val = idalloc_allocate(a);
			assert(val < 3*IDS_PER_PAGE);
			assert(allocated_markers[val] == 0);
			allocated_markers[val] = 1;
		}
		assert(a->capacity == 3*IDS_PER_PAGE);
		assert(a->allocated == 3*IDS_PER_PAGE);
	}
	idalloc_destroy(a);

	puts("ID Allocator test successful.\n");
	return 0;
}
Commit	Line	Data
a94eca09 MS	1	#include "id_alloc.h"
	2
	3	#include <inttypes.h>
	4	#include <string.h>
	5	#include <assert.h>
	6	#include <stdio.h>
	7
	8	#define IDS_PER_PAGE (1<<(IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS))
	9	char allocated_markers[IDS_PER_PAGE*3];
	10
	11	int main(int argc, char **argv)
	12	{
	13	int i, val;
	14	uint32_t pg;
	15	struct id_alloc *a;
	16
	17	/* 1. Rattle test, shake it a little and make sure it doesn't make any
	18	* noise :)
	19	*/
	20	a = idalloc_new("Rattle test");
	21	for (i = 0; i < 1000000; i++)
	22	assert(idalloc_allocate(a) != 0);
	23
	24	idalloc_destroy(a);
	25
	26	/* 2. Reserve a few low IDs, make sure they are skipped by normal
	27	* allocation.
	28	*/
	29	a = idalloc_new("Low Reservations");
	30	assert(idalloc_reserve(a, 1) == 1);
	31	assert(idalloc_reserve(a, 3) == 3);
	32	assert(idalloc_reserve(a, 5) == 5);
	33	for (i = 0; i < 100; i++) {
	34	val = idalloc_allocate(a);
	35	assert(val != 1 && val != 3 && val != 5);
	36	}
	37	idalloc_destroy(a);
	38
	39	/* 3. Single page testing. Check that IDs are kept unique, and all IDs
	40	* in the existing page are allocated before a new page is added.
	41	*/
	42	memset(allocated_markers, 0, sizeof(allocated_markers));
	43	allocated_markers[IDALLOC_INVALID] = 1;
	44
	45	a = idalloc_new("Single Page");
	46
	47	/* reserve the rest of the first page */
	48	for (i = 0; i < IDS_PER_PAGE - 1; i++) {
	49	val = idalloc_allocate(a);
	50	assert(val < IDS_PER_PAGE);
	51	assert(allocated_markers[val] == 0);
	52	assert(a->capacity == IDS_PER_PAGE);
	53	allocated_markers[val] = 1;
	54	}
	55	/* Check that the count is right */
	56	assert(a->allocated == IDS_PER_PAGE);
	57
	58	/* Free some IDs out of the middle. */
	59	idalloc_free(a, 300);
	60	allocated_markers[300] = 0;
	61	idalloc_free(a, 400);
	62	allocated_markers[400] = 0;
	63	idalloc_free(a, 500);
	64	allocated_markers[500] = 0;
65
66	assert(a->allocated == IDS_PER_PAGE-3);
67
68	/* Allocate the three IDs back and make sure they are pulled from the
69	* set just freed
70	*/
71	for (i = 0; i < 3; i++) {
72	val = idalloc_allocate(a);
73	assert(val < IDS_PER_PAGE);
74	assert(allocated_markers[val] == 0);
75	assert(a->capacity == IDS_PER_PAGE);
76	allocated_markers[val] = 1;
77	}
78	idalloc_destroy(a);
79
80	/* 4. Multi-page testing. */
81	memset(allocated_markers, 0, sizeof(allocated_markers));
82	allocated_markers[IDALLOC_INVALID] = 1;
83
84	a = idalloc_new("Multi-page");
85
86	/* reserve the rest of the first page and all of the second and third */
87	for (i = 0; i < 3 * IDS_PER_PAGE - 1; i++) {
88	val = idalloc_allocate(a);
89	assert(val < 3*IDS_PER_PAGE);
90	assert(allocated_markers[val] == 0);
91	allocated_markers[val] = 1;
92	}
93	assert(a->capacity == 3*IDS_PER_PAGE);
94	assert(a->allocated == 3*IDS_PER_PAGE);
95
96	/* Free two IDs from each page. */
97	for (i = 0; i < 3; i++) {
98	idalloc_free(a, 7 + i*IDS_PER_PAGE);
99	allocated_markers[7 + i*IDS_PER_PAGE] = 0;
100
101	idalloc_free(a, 4 + i*IDS_PER_PAGE);
102	allocated_markers[4 + i*IDS_PER_PAGE] = 0;
103	}
104
105	assert(a->allocated == 3*IDS_PER_PAGE - 6);
106
107	/* Allocate the six IDs back and make sure they are pulled from the set
108	* just freed.
109	*/
110	for (i = 0; i < 6; i++) {
111	val = idalloc_allocate(a);
112	assert(val < 3*IDS_PER_PAGE);
113	assert(allocated_markers[val] == 0);
114	assert(a->capacity == 3*IDS_PER_PAGE);
115	allocated_markers[val] = 1;
116	}
117
118	assert(a->capacity == 3*IDS_PER_PAGE);
119	assert(a->allocated == 3*IDS_PER_PAGE);
120
121	/* Walk each allocated ID. Free it, then re-allocate it back. */
122	for (i = 1; i < 3 * IDS_PER_PAGE - 1; i++) {
123	idalloc_free(a, i);
124	val = idalloc_allocate(a);
125	assert(val == i);
126	assert(a->capacity == 3*IDS_PER_PAGE);
127	assert(a->allocated == 3*IDS_PER_PAGE);
128	}
129	idalloc_destroy(a);
130
131	/* 5. Weird Reservations
132	* idalloc_reserve exists primarily to black out low numbered IDs that
133	* are reserved for special cases. However, we will test it for more
134	* complex use cases to avoid unpleasant surprises.
135	*/
136
137	memset(allocated_markers, 0, sizeof(allocated_markers));
138	allocated_markers[IDALLOC_INVALID] = 1;
139
140	a = idalloc_new("Weird Reservations");
141
142	/* Start with 3 pages fully allocated. */
143	for (i = 0; i < 3 * IDS_PER_PAGE - 1; i++) {
144	val = idalloc_allocate(a);
145	assert(val < 3*IDS_PER_PAGE);
146	assert(allocated_markers[val] == 0);
147	allocated_markers[val] = 1;
148	}
149	assert(a->capacity == 3*IDS_PER_PAGE);
150	assert(a->allocated == 3*IDS_PER_PAGE);
151
152	/* Free a bit out of each of the three pages. Then reserve one of the
153	* three freed IDs. Finally, allocate the other two freed IDs. Do this
154	* each of three ways. (Reserve out of the first, seconds then third
155	* page.)
156	* The intent here is to exercise the rare cases on reserve_bit's
157	* linked-list removal in the case that it is not removing the first
158	* page with a free bit in its list of pages with free bits.
159	*/
160
161	for (pg = 0; pg < 3; pg++) {
162	/* free a bit out of each of the three pages */
163	for (i = 0; i < 3; i++) {
164	idalloc_free(a, i*IDS_PER_PAGE + 17);
165	allocated_markers[i*IDS_PER_PAGE + 17] = 0;
166	}
167
168	assert(a->capacity == 3*IDS_PER_PAGE);
169	assert(a->allocated == 3*IDS_PER_PAGE-3);
170
171	/* Reserve one of the freed IDs */
172	assert(idalloc_reserve(a, pg*IDS_PER_PAGE + 17) ==
173	pg*IDS_PER_PAGE + 17);
174	allocated_markers[pg*IDS_PER_PAGE + 17] = 1;
175
176	assert(a->capacity == 3*IDS_PER_PAGE);
177	assert(a->allocated == 3*IDS_PER_PAGE-2);
178
179	/* Allocate the other two back */
180	for (i = 0; i < 2; i++) {
181	val = idalloc_allocate(a);
182	assert(val < 3*IDS_PER_PAGE);
183	assert(allocated_markers[val] == 0);
184	allocated_markers[val] = 1;
185	}
186	assert(a->capacity == 3*IDS_PER_PAGE);
187	assert(a->allocated == 3*IDS_PER_PAGE);
188	}
189	idalloc_destroy(a);
190
191	puts("ID Allocator test successful.\n");
192	return 0;
193	}