Add alloc_size(): every allocator has to be able to answer this, since
[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(178);
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         ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
79
80         /* Free it, should be able to reallocate it. */
81         alloc_free(mem, POOL_SIZE, p[0]);
82         ok1(alloc_check(mem, POOL_SIZE));
83
84         p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
85         ok1(p[0]);
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));
90
91         /* Allocate a whole heap. */
92         for (i = 0; i < POOL_SIZE; i++) {
93                 p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
94                 if (!p[i])
95                         break;
96         }
97
98         /* Uncomment this for a more intuitive view of what the
99          * allocator looks like after all these 1 byte allocs. */
100 #if 0
101         alloc_visualize(stderr, mem, POOL_SIZE);
102 #endif
103
104         num = i;
105         /* Can't allocate this many. */
106         ok1(num != POOL_SIZE);
107         ok1(alloc_check(mem, POOL_SIZE));
108
109         /* Sort them. */
110         sort(p, num, addr_cmp);
111
112         /* Uniqueness check */
113         ok1(unique(p, num));
114
115         ok1(free_every_second_one(mem, num, p));
116         ok1(alloc_check(mem, POOL_SIZE));
117
118         /* Should be able to reallocate max size. */
119         p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
120         ok1(p[0]);
121         ok1(alloc_check(mem, POOL_SIZE));
122         ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
123
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);
128         ok1(p[0]);
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));
133
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);
137                 ok1(p[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);
141         }
142
143         for (i = 0; i < POOL_ORD-1; i++) {
144                 alloc_free(mem, POOL_SIZE, p[i]);
145                 ok1(alloc_check(mem, POOL_SIZE));
146         }
147
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);
151                 ok1(p[0]);
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));
156         }
157
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));
164
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());
169                 if (!p[i])
170                         break;
171         }
172         ok1(alloc_check(mem, POOL_SIZE));
173         ok1(alloc_size(mem, POOL_SIZE, p[i-1]) >= getpagesize());
174
175         /* Sort them. */
176         sort(p, i-1, addr_cmp);
177
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());
183
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);
187                 if (!p[i])
188                         break;
189         }
190         ok1(alloc_check(mem, POOL_SIZE));
191
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);
196         ok1(p[0]);
197         ok1(alloc_size(mem, POOL_SIZE, p[0]) >= 1);
198
199         /* Clean up. */
200         for (i = 0; p[i]; i++)
201                 alloc_free(mem, POOL_SIZE, p[i]);
202         ok1(alloc_check(mem, POOL_SIZE));
203
204         return exit_status();
205 }