1 #include "alloc/alloc.h"
3 #include "alloc/alloc.c"
7 #define POOL_SIZE (1 << POOL_ORD)
9 #define sort(p, num, cmp) \
10 qsort((p), (num), sizeof(*p), (int(*)(const void *, const void *))cmp)
12 static int addr_cmp(void **a, void **b)
17 static bool unique(void *p[], unsigned int num)
21 for (i = 1; i < num; i++)
27 static bool free_every_second_one(void *mem, unsigned int num, void *p[])
31 /* Free every second one. */
32 for (i = 0; i < num; i += 2) {
33 alloc_free(mem, POOL_SIZE, p[i]);
34 if (!alloc_check(mem, POOL_SIZE))
37 for (i = 1; i < num; i += 2) {
38 alloc_free(mem, POOL_SIZE, p[i]);
39 if (!alloc_check(mem, POOL_SIZE))
46 int main(int argc, char *argv[])
49 unsigned int i, num, max_size;
54 /* FIXME: Needs to be page aligned for now. */
55 posix_memalign(&mem, 1 << POOL_ORD, POOL_SIZE);
57 /* Small pool, all allocs fail, even 0-length. */
59 ok1(alloc_check(mem, 0));
60 ok1(alloc_get(mem, 0, 1, 1) == NULL);
61 ok1(alloc_get(mem, 0, 128, 1) == NULL);
62 ok1(alloc_get(mem, 0, 0, 1) == NULL);
64 /* Free of NULL should work. */
65 alloc_free(mem, 0, NULL);
67 alloc_init(mem, POOL_SIZE);
68 ok1(alloc_check(mem, POOL_SIZE));
69 /* Find largest allocation which works. */
70 for (max_size = POOL_SIZE * 2; max_size; max_size--) {
71 p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
75 ok1(max_size < POOL_SIZE);
77 ok1(alloc_check(mem, POOL_SIZE));
78 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
80 /* Free it, should be able to reallocate it. */
81 alloc_free(mem, POOL_SIZE, p[0]);
82 ok1(alloc_check(mem, POOL_SIZE));
84 p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
86 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
87 ok1(alloc_check(mem, POOL_SIZE));
88 alloc_free(mem, POOL_SIZE, p[0]);
89 ok1(alloc_check(mem, POOL_SIZE));
91 /* Allocate a whole heap. */
92 for (i = 0; i < POOL_SIZE; i++) {
93 p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
98 /* Uncomment this for a more intuitive view of what the
99 * allocator looks like after all these 1 byte allocs. */
101 alloc_visualize(stderr, mem, POOL_SIZE);
105 /* Can't allocate this many. */
106 ok1(num != POOL_SIZE);
107 ok1(alloc_check(mem, POOL_SIZE));
110 sort(p, num, addr_cmp);
112 /* Uniqueness check */
115 ok1(free_every_second_one(mem, num, p));
116 ok1(alloc_check(mem, POOL_SIZE));
118 /* Should be able to reallocate max size. */
119 p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
121 ok1(alloc_check(mem, POOL_SIZE));
122 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
124 /* Re-initializing should be the same as freeing everything */
125 alloc_init(mem, POOL_SIZE);
126 ok1(alloc_check(mem, POOL_SIZE));
127 p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
129 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
130 ok1(alloc_check(mem, POOL_SIZE));
131 alloc_free(mem, POOL_SIZE, p[0]);
132 ok1(alloc_check(mem, POOL_SIZE));
134 /* Alignment constraints should be met, as long as powers of two */
135 for (i = 0; i < POOL_ORD-1; i++) {
136 p[i] = alloc_get(mem, POOL_SIZE, i, 1 << i);
138 ok1(((unsigned long)p[i] % (1 << i)) == 0);
139 ok1(alloc_check(mem, POOL_SIZE));
140 ok1(alloc_size(mem, POOL_SIZE, p[i]) >= i);
143 for (i = 0; i < POOL_ORD-1; i++) {
144 alloc_free(mem, POOL_SIZE, p[i]);
145 ok1(alloc_check(mem, POOL_SIZE));
148 /* Alignment constraints for a single-byte allocation. */
149 for (i = 0; i < POOL_ORD; i++) {
150 p[0] = alloc_get(mem, POOL_SIZE, 1, 1 << i);
152 ok1(alloc_check(mem, POOL_SIZE));
153 ok1(alloc_size(mem, POOL_SIZE, p[i]) >= 1);
154 alloc_free(mem, POOL_SIZE, p[0]);
155 ok1(alloc_check(mem, POOL_SIZE));
158 /* Alignment check for a 0-byte allocation. Corner case. */
159 p[0] = alloc_get(mem, POOL_SIZE, 0, 1 << (POOL_ORD - 1));
160 ok1(alloc_check(mem, POOL_SIZE));
161 ok1(alloc_size(mem, POOL_SIZE, p[0]) < POOL_SIZE);
162 alloc_free(mem, POOL_SIZE, p[0]);
163 ok1(alloc_check(mem, POOL_SIZE));
165 /* Force the testing of split metadata. */
166 alloc_init(mem, POOL_SIZE);
167 for (i = 0; i < POOL_SIZE; i++) {
168 p[i] = alloc_get(mem, POOL_SIZE, getpagesize(), getpagesize());
172 ok1(alloc_check(mem, POOL_SIZE));
173 ok1(alloc_size(mem, POOL_SIZE, p[i-1]) >= getpagesize());
176 sort(p, i-1, addr_cmp);
178 /* Free all but the one next to the metadata. */
179 for (i = 1; p[i]; i++)
180 alloc_free(mem, POOL_SIZE, p[i]);
181 ok1(alloc_check(mem, POOL_SIZE));
182 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= getpagesize());
184 /* Now do a whole heap of subpage allocs. */
185 for (i = 1; i < POOL_SIZE; i++) {
186 p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
190 ok1(alloc_check(mem, POOL_SIZE));
192 /* Free up our page next to metadata, and should be able to alloc */
193 alloc_free(mem, POOL_SIZE, p[0]);
194 ok1(alloc_check(mem, POOL_SIZE));
195 p[0] = alloc_get(mem, POOL_SIZE, 1, 1);
197 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= 1);
200 for (i = 0; p[i]; i++)
201 alloc_free(mem, POOL_SIZE, p[i]);
202 ok1(alloc_check(mem, POOL_SIZE));
204 return exit_status();