alloc: first cut of tiny allocator (down to 2 bytes!)
[ccan] / ccan / alloc / test / run.c
1 #include <ccan/alloc/alloc.h>
2 #include <ccan/tap/tap.h>
3 #include <ccan/alloc/alloc.c>
4 #include <ccan/alloc/bitops.c>
5 #include <ccan/alloc/tiny.c>
6 #include <stdlib.h>
7 #include <err.h>
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, 
28                                   unsigned long pool_size, void *p[])
29 {
30         unsigned int i;
31
32         /* Free every second one. */
33         for (i = 0; i < num; i += 2) {
34                 alloc_free(mem, pool_size, p[i]);
35         }
36         if (!alloc_check(mem, pool_size))
37                 return false;
38         for (i = 1; i < num; i += 2) {
39                 alloc_free(mem, pool_size, p[i]);
40         }
41         if (!alloc_check(mem, pool_size))
42                 return false;
43         return true;
44 }
45
46 static void test(unsigned int pool_size)
47 {
48         void *mem;
49         unsigned int i, num, max_size;
50         void **p = calloc(pool_size, sizeof(*p));
51         /* FIXME: Should be pool_size! */
52         unsigned alloc_limit = (pool_size / MAX_LARGE_PAGES) >> MAX_PAGE_OBJECT_ORDER;
53
54         /* FIXME: Needs to be page aligned for now. */
55         if (posix_memalign(&mem, pool_size, pool_size) != 0)
56                 errx(1, "Failed allocating aligned memory"); 
57
58         /* Small pool, all allocs fail, even 0-length. */
59         alloc_init(mem, 0);
60         ok1(alloc_check(mem, 0));
61         ok1(alloc_get(mem, 0, 1, 1) == NULL);
62         ok1(alloc_get(mem, 0, 128, 1) == NULL);
63         ok1(alloc_get(mem, 0, 0, 1) == NULL);
64
65         /* Free of NULL should work. */
66         alloc_free(mem, 0, NULL);
67
68         alloc_init(mem, pool_size);
69         ok1(alloc_check(mem, pool_size));
70         /* Find largest allocation which works. */
71         for (max_size = pool_size + 1; max_size; max_size--) {
72                 p[0] = alloc_get(mem, pool_size, max_size, 1);
73                 if (p[0])
74                         break;
75         }
76         ok1(max_size < pool_size);
77         ok1(max_size > 0);
78         ok1(alloc_check(mem, pool_size));
79         ok1(alloc_size(mem, pool_size, p[0]) >= max_size);
80
81         /* Free it, should be able to reallocate it. */
82         alloc_free(mem, pool_size, p[0]);
83         ok1(alloc_check(mem, pool_size));
84
85         p[0] = alloc_get(mem, pool_size, max_size, 1);
86         ok1(p[0]);
87         ok1(alloc_size(mem, pool_size, p[0]) >= max_size);
88         ok1(alloc_check(mem, pool_size));
89         alloc_free(mem, pool_size, p[0]);
90         ok1(alloc_check(mem, pool_size));
91
92         /* Allocate a whole heap. */
93         for (i = 0; i < pool_size; i++) {
94                 p[i] = alloc_get(mem, pool_size, 1, 1);
95                 if (!p[i])
96                         break;
97         }
98
99         /* Uncomment this for a more intuitive view of what the
100          * allocator looks like after all these 1 byte allocs. */
101 #if 0
102         alloc_visualize(stderr, mem, pool_size);
103 #endif
104
105         num = i;
106         /* Can't allocate this many. */
107         ok1(num != pool_size);
108         ok1(alloc_check(mem, pool_size));
109
110         /* Sort them. */
111         sort(p, num, addr_cmp);
112
113         /* Uniqueness check */
114         ok1(unique(p, num));
115
116         ok1(free_every_second_one(mem, num, pool_size, p));
117         ok1(alloc_check(mem, pool_size));
118
119         /* Should be able to reallocate max size. */
120         p[0] = alloc_get(mem, pool_size, max_size, 1);
121         ok1(p[0]);
122         ok1(alloc_check(mem, pool_size));
123         ok1(alloc_size(mem, pool_size, p[0]) >= max_size);
124
125         /* Re-initializing should be the same as freeing everything */
126         alloc_init(mem, pool_size);
127         ok1(alloc_check(mem, pool_size));
128         p[0] = alloc_get(mem, pool_size, max_size, 1);
129         ok1(p[0]);
130         ok1(alloc_size(mem, pool_size, p[0]) >= max_size);
131         ok1(alloc_check(mem, pool_size));
132         alloc_free(mem, pool_size, p[0]);
133         ok1(alloc_check(mem, pool_size));
134
135         /* Alignment constraints should be met, as long as powers of two */
136         for (i = 0; (1 << i) < alloc_limit; i++) {
137                 p[i] = alloc_get(mem, pool_size, i, 1 << i);
138                 ok1(p[i]);
139                 ok1(((unsigned long)p[i] % (1 << i)) == 0);
140                 ok1(alloc_check(mem, pool_size));
141                 ok1(alloc_size(mem, pool_size, p[i]) >= i);
142         }
143
144         for (i = 0; (1 << i) < alloc_limit; i++) {
145                 alloc_free(mem, pool_size, p[i]);
146                 ok1(alloc_check(mem, pool_size));
147         }
148
149         /* Alignment constraints for a single-byte allocation. */
150         for (i = 0; (1 << i) < alloc_limit; i++) {
151                 p[0] = alloc_get(mem, pool_size, 1, 1 << i);
152                 ok1(p[0]);
153                 ok1(alloc_check(mem, pool_size));
154                 ok1(alloc_size(mem, pool_size, p[i]) >= 1);
155                 alloc_free(mem, pool_size, p[0]);
156                 ok1(alloc_check(mem, pool_size));
157         }
158
159         /* Alignment check for a 0-byte allocation.  Corner case. */
160         p[0] = alloc_get(mem, pool_size, 0, alloc_limit);
161         ok1(alloc_check(mem, pool_size));
162         ok1(alloc_size(mem, pool_size, p[0]) < pool_size);
163         alloc_free(mem, pool_size, p[0]);
164         ok1(alloc_check(mem, pool_size));
165 }
166
167 int main(int argc, char *argv[])
168 {
169         plan_tests(112 + 92);
170
171         /* Large test. */
172         test(MIN_USEFUL_SIZE * 2);
173
174         /* Small test. */
175         test(MIN_USEFUL_SIZE / 2);
176
177         return exit_status();
178 }