1 #include <ccan/alloc/alloc.h>
2 #include <ccan/tap/tap.h>
3 #include <ccan/alloc/alloc.c>
8 #define POOL_SIZE (1 << POOL_ORD)
10 #define sort(p, num, cmp) \
11 qsort((p), (num), sizeof(*p), (int(*)(const void *, const void *))cmp)
13 static int addr_cmp(void **a, void **b)
18 static bool unique(void *p[], unsigned int num)
22 for (i = 1; i < num; i++)
28 static bool free_every_second_one(void *mem, unsigned int num, void *p[])
32 /* Free every second one. */
33 for (i = 0; i < num; i += 2) {
34 alloc_free(mem, POOL_SIZE, p[i]);
35 if (!alloc_check(mem, POOL_SIZE))
38 for (i = 1; i < num; i += 2) {
39 alloc_free(mem, POOL_SIZE, p[i]);
40 if (!alloc_check(mem, POOL_SIZE))
47 int main(int argc, char *argv[])
50 unsigned int i, num, max_size;
55 /* FIXME: Needs to be page aligned for now. */
56 if (posix_memalign(&mem, 1 << POOL_ORD, POOL_SIZE) != 0)
57 errx(1, "Failed allocating aligned memory");
59 /* Small pool, all allocs fail, even 0-length. */
61 ok1(alloc_check(mem, 0));
62 ok1(alloc_get(mem, 0, 1, 1) == NULL);
63 ok1(alloc_get(mem, 0, 128, 1) == NULL);
64 ok1(alloc_get(mem, 0, 0, 1) == NULL);
66 /* Free of NULL should work. */
67 alloc_free(mem, 0, NULL);
69 alloc_init(mem, POOL_SIZE);
70 ok1(alloc_check(mem, POOL_SIZE));
71 /* Find largest allocation which works. */
72 for (max_size = POOL_SIZE * 2; max_size; max_size--) {
73 p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
77 ok1(max_size < POOL_SIZE);
79 ok1(alloc_check(mem, POOL_SIZE));
80 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
82 /* Free it, should be able to reallocate it. */
83 alloc_free(mem, POOL_SIZE, p[0]);
84 ok1(alloc_check(mem, POOL_SIZE));
86 p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
88 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
89 ok1(alloc_check(mem, POOL_SIZE));
90 alloc_free(mem, POOL_SIZE, p[0]);
91 ok1(alloc_check(mem, POOL_SIZE));
93 /* Allocate a whole heap. */
94 for (i = 0; i < POOL_SIZE; i++) {
95 p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
100 /* Uncomment this for a more intuitive view of what the
101 * allocator looks like after all these 1 byte allocs. */
103 alloc_visualize(stderr, mem, POOL_SIZE);
107 /* Can't allocate this many. */
108 ok1(num != POOL_SIZE);
109 ok1(alloc_check(mem, POOL_SIZE));
112 sort(p, num, addr_cmp);
114 /* Uniqueness check */
117 ok1(free_every_second_one(mem, num, p));
118 ok1(alloc_check(mem, POOL_SIZE));
120 /* Should be able to reallocate max size. */
121 p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
123 ok1(alloc_check(mem, POOL_SIZE));
124 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
126 /* Re-initializing should be the same as freeing everything */
127 alloc_init(mem, POOL_SIZE);
128 ok1(alloc_check(mem, POOL_SIZE));
129 p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
131 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
132 ok1(alloc_check(mem, POOL_SIZE));
133 alloc_free(mem, POOL_SIZE, p[0]);
134 ok1(alloc_check(mem, POOL_SIZE));
136 /* Alignment constraints should be met, as long as powers of two */
137 for (i = 0; i < POOL_ORD-1; i++) {
138 p[i] = alloc_get(mem, POOL_SIZE, i, 1 << i);
140 ok1(((unsigned long)p[i] % (1 << i)) == 0);
141 ok1(alloc_check(mem, POOL_SIZE));
142 ok1(alloc_size(mem, POOL_SIZE, p[i]) >= i);
145 for (i = 0; i < POOL_ORD-1; i++) {
146 alloc_free(mem, POOL_SIZE, p[i]);
147 ok1(alloc_check(mem, POOL_SIZE));
150 /* Alignment constraints for a single-byte allocation. */
151 for (i = 0; i < POOL_ORD; i++) {
152 p[0] = alloc_get(mem, POOL_SIZE, 1, 1 << i);
154 ok1(alloc_check(mem, POOL_SIZE));
155 ok1(alloc_size(mem, POOL_SIZE, p[i]) >= 1);
156 alloc_free(mem, POOL_SIZE, p[0]);
157 ok1(alloc_check(mem, POOL_SIZE));
160 /* Alignment check for a 0-byte allocation. Corner case. */
161 p[0] = alloc_get(mem, POOL_SIZE, 0, 1 << (POOL_ORD - 1));
162 ok1(alloc_check(mem, POOL_SIZE));
163 ok1(alloc_size(mem, POOL_SIZE, p[0]) < POOL_SIZE);
164 alloc_free(mem, POOL_SIZE, p[0]);
165 ok1(alloc_check(mem, POOL_SIZE));
167 /* Force the testing of split metadata. */
168 alloc_init(mem, POOL_SIZE);
169 for (i = 0; i < POOL_SIZE; i++) {
170 p[i] = alloc_get(mem, POOL_SIZE, getpagesize(), getpagesize());
174 ok1(alloc_check(mem, POOL_SIZE));
175 ok1(alloc_size(mem, POOL_SIZE, p[i-1]) >= getpagesize());
178 sort(p, i-1, addr_cmp);
180 /* Free all but the one next to the metadata. */
181 for (i = 1; p[i]; i++)
182 alloc_free(mem, POOL_SIZE, p[i]);
183 ok1(alloc_check(mem, POOL_SIZE));
184 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= getpagesize());
186 /* Now do a whole heap of subpage allocs. */
187 for (i = 1; i < POOL_SIZE; i++) {
188 p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
192 ok1(alloc_check(mem, POOL_SIZE));
194 /* Free up our page next to metadata, and should be able to alloc */
195 alloc_free(mem, POOL_SIZE, p[0]);
196 ok1(alloc_check(mem, POOL_SIZE));
197 p[0] = alloc_get(mem, POOL_SIZE, 1, 1);
199 ok1(alloc_size(mem, POOL_SIZE, p[0]) >= 1);
202 for (i = 0; p[i]; i++)
203 alloc_free(mem, POOL_SIZE, p[i]);
204 ok1(alloc_check(mem, POOL_SIZE));
206 return exit_status();