Move modules to ccan/ tools to tools/
[ccan] / ccan / alloc / test / run.c
1 #include "alloc/alloc.h"
2 #include "tap/tap.h"
3 #include "alloc/alloc.c"
4 #include <stdlib.h>
5
6 #define POOL_ORD 16
7 #define POOL_SIZE (1 << POOL_ORD)
8
9 #define sort(p, num, cmp) \
10         qsort((p), (num), sizeof(*p), (int(*)(const void *, const void *))cmp)
11
12 static int addr_cmp(void **a, void **b)
13 {
14         return (*a) - (*b);
15 }
16
17 static bool unique(void *p[], unsigned int num)
18 {
19         unsigned int i;
20
21         for (i = 1; i < num; i++)
22                 if (p[i] == p[i-1])
23                         return false;
24         return true;
25 }       
26
27 static bool free_every_second_one(void *mem, unsigned int num, void *p[])
28 {
29         unsigned int i;
30
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))
35                         return false;
36         }
37         for (i = 1; i < num; i += 2) {
38                 alloc_free(mem, POOL_SIZE, p[i]);
39                 if (!alloc_check(mem, POOL_SIZE))
40                         return false;
41         }
42         return true;
43 }
44
45
46 int main(int argc, char *argv[])
47 {
48         void *mem;
49         unsigned int i, num, max_size;
50         void *p[POOL_SIZE];
51
52         plan_tests(139);
53
54         /* FIXME: Needs to be page aligned for now. */
55         posix_memalign(&mem, 1 << POOL_ORD, POOL_SIZE);
56
57         /* Small pool, all allocs fail, even 0-length. */
58         alloc_init(mem, 0);
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);
63
64         /* Free of NULL should work. */
65         alloc_free(mem, 0, NULL);
66
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);
72                 if (p[0])
73                         break;
74         }
75         ok1(max_size < POOL_SIZE);
76         ok1(max_size > 0);
77         ok1(alloc_check(mem, POOL_SIZE));
78
79         /* Free it, should be able to reallocate it. */
80         alloc_free(mem, POOL_SIZE, p[0]);
81         ok1(alloc_check(mem, POOL_SIZE));
82
83         p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
84         ok1(p[0]);
85         ok1(alloc_check(mem, POOL_SIZE));
86         alloc_free(mem, POOL_SIZE, p[0]);
87         ok1(alloc_check(mem, POOL_SIZE));
88
89         /* Allocate a whole heap. */
90         for (i = 0; i < POOL_SIZE; i++) {
91                 p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
92                 if (!p[i])
93                         break;
94         }
95
96         /* Uncomment this for a more intuitive view of what the
97          * allocator looks like after all these 1 byte allocs. */
98 #if 0
99         alloc_visualize(stderr, mem, POOL_SIZE);
100 #endif
101
102         num = i;
103         /* Can't allocate this many. */
104         ok1(num != POOL_SIZE);
105         ok1(alloc_check(mem, POOL_SIZE));
106
107         /* Sort them. */
108         sort(p, num, addr_cmp);
109
110         /* Uniqueness check */
111         ok1(unique(p, num));
112
113         ok1(free_every_second_one(mem, num, p));
114         ok1(alloc_check(mem, POOL_SIZE));
115
116         /* Should be able to reallocate max size. */
117         p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
118         ok1(p[0]);
119         ok1(alloc_check(mem, POOL_SIZE));
120
121         /* Re-initializing should be the same as freeing everything */
122         alloc_init(mem, POOL_SIZE);
123         ok1(alloc_check(mem, POOL_SIZE));
124         p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
125         ok1(p[0]);
126         ok1(alloc_check(mem, POOL_SIZE));
127         alloc_free(mem, POOL_SIZE, p[0]);
128         ok1(alloc_check(mem, POOL_SIZE));
129
130         /* Alignment constraints should be met, as long as powers of two */
131         for (i = 0; i < POOL_ORD-1; i++) {
132                 p[i] = alloc_get(mem, POOL_SIZE, i, 1 << i);
133                 ok1(p[i]);
134                 ok1(((unsigned long)p[i] % (1 << i)) == 0);
135                 ok1(alloc_check(mem, POOL_SIZE));
136         }
137
138         for (i = 0; i < POOL_ORD-1; i++) {
139                 alloc_free(mem, POOL_SIZE, p[i]);
140                 ok1(alloc_check(mem, POOL_SIZE));
141         }
142
143         /* Alignment constraints for a single-byte allocation. */
144         for (i = 0; i < POOL_ORD; i++) {
145                 p[0] = alloc_get(mem, POOL_SIZE, 1, 1 << i);
146                 ok1(p[0]);
147                 ok1(alloc_check(mem, POOL_SIZE));
148                 alloc_free(mem, POOL_SIZE, p[0]);
149                 ok1(alloc_check(mem, POOL_SIZE));
150         }
151
152         /* Alignment check for a 0-byte allocation.  Corner case. */
153         p[0] = alloc_get(mem, POOL_SIZE, 0, 1 << (POOL_ORD - 1));
154         ok1(alloc_check(mem, POOL_SIZE));
155         alloc_free(mem, POOL_SIZE, p[0]);
156         ok1(alloc_check(mem, POOL_SIZE));
157
158         /* Force the testing of split metadata. */
159         alloc_init(mem, POOL_SIZE);
160         for (i = 0; i < POOL_SIZE; i++) {
161                 p[i] = alloc_get(mem, POOL_SIZE, getpagesize(), getpagesize());
162                 if (!p[i])
163                         break;
164         }
165         ok1(alloc_check(mem, POOL_SIZE));
166
167         /* Sort them. */
168         sort(p, i-1, addr_cmp);
169
170         /* Free all but the one next to the metadata. */
171         for (i = 1; p[i]; i++)
172                 alloc_free(mem, POOL_SIZE, p[i]);
173         ok1(alloc_check(mem, POOL_SIZE));
174
175         /* Now do a whole heap of subpage allocs. */
176         for (i = 1; i < POOL_SIZE; i++) {
177                 p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
178                 if (!p[i])
179                         break;
180         }
181         ok1(alloc_check(mem, POOL_SIZE));
182
183         /* Free up our page next to metadata, and should be able to alloc */
184         alloc_free(mem, POOL_SIZE, p[0]);
185         ok1(alloc_check(mem, POOL_SIZE));
186         p[0] = alloc_get(mem, POOL_SIZE, 1, 1);
187         ok1(p[0]);
188
189         /* Clean up. */
190         for (i = 0; p[i]; i++)
191                 alloc_free(mem, POOL_SIZE, p[i]);
192         ok1(alloc_check(mem, POOL_SIZE));
193
194         return exit_status();
195 }