a6d021ff9e5dc87b3d1f25cf821fc15215031208
[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         unsigned alloc_limit = pool_size / 2;
52
53         mem = malloc(pool_size);
54
55         /* Small pool, all allocs fail, even 0-length. */
56         alloc_init(mem, 0);
57         ok1(alloc_check(mem, 0));
58         ok1(alloc_get(mem, 0, 1, 1) == NULL);
59         ok1(alloc_get(mem, 0, 128, 1) == NULL);
60         ok1(alloc_get(mem, 0, 0, 1) == NULL);
61
62         /* Free of NULL should work. */
63         alloc_free(mem, 0, NULL);
64
65         alloc_init(mem, pool_size);
66         ok1(alloc_check(mem, pool_size));
67         /* Find largest allocation which works. */
68         for (max_size = pool_size + 1; max_size; max_size--) {
69                 p[0] = alloc_get(mem, pool_size, max_size, 1);
70                 if (p[0])
71                         break;
72         }
73         ok1(max_size < pool_size);
74         ok1(max_size > 0);
75         ok1(alloc_check(mem, pool_size));
76         ok1(alloc_size(mem, pool_size, p[0]) >= max_size);
77
78         /* Free it, should be able to reallocate it. */
79         alloc_free(mem, pool_size, p[0]);
80         ok1(alloc_check(mem, pool_size));
81
82         p[0] = alloc_get(mem, pool_size, max_size, 1);
83         ok1(p[0]);
84         ok1(alloc_size(mem, pool_size, p[0]) >= max_size);
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, pool_size, 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         ok1(alloc_size(mem, pool_size, p[0]) >= max_size);
121
122         /* Re-initializing should be the same as freeing everything */
123         alloc_init(mem, pool_size);
124         ok1(alloc_check(mem, pool_size));
125         p[0] = alloc_get(mem, pool_size, max_size, 1);
126         ok1(p[0]);
127         ok1(alloc_size(mem, pool_size, p[0]) >= max_size);
128         ok1(alloc_check(mem, pool_size));
129         alloc_free(mem, pool_size, p[0]);
130         ok1(alloc_check(mem, pool_size));
131
132         /* Alignment constraints should be met, as long as powers of two */
133         for (i = 0; (1 << i) < alloc_limit; i++) {
134                 p[i] = alloc_get(mem, pool_size, i, 1 << i);
135                 ok1(p[i]);
136                 ok1(((char *)p[i] - (char *)mem) % (1 << i) == 0);
137                 ok1(alloc_check(mem, pool_size));
138                 ok1(alloc_size(mem, pool_size, p[i]) >= i);
139         }
140
141         for (i = 0; (1 << i) < alloc_limit; i++) {
142                 alloc_free(mem, pool_size, p[i]);
143                 ok1(alloc_check(mem, pool_size));
144         }
145
146         /* Alignment constraints for a single-byte allocation. */
147         for (i = 0; (1 << i) < alloc_limit; i++) {
148                 p[0] = alloc_get(mem, pool_size, 1, 1 << i);
149                 ok1(p[0]);
150                 ok1(((char *)p[0] - (char *)mem) % (1 << i) == 0);
151                 ok1(alloc_check(mem, pool_size));
152                 ok1(alloc_size(mem, pool_size, p[0]) >= 1);
153                 alloc_free(mem, pool_size, p[0]);
154                 ok1(alloc_check(mem, pool_size));
155         }
156
157         /* Alignment check for a 0-byte allocation.  Corner case. */
158         p[0] = alloc_get(mem, pool_size, 0, alloc_limit);
159         ok1(alloc_check(mem, pool_size));
160         ok1(alloc_size(mem, pool_size, p[0]) < pool_size);
161         alloc_free(mem, pool_size, p[0]);
162         ok1(alloc_check(mem, pool_size));
163 }
164
165 int main(int argc, char *argv[])
166 {
167         plan_tests(440);
168
169         /* Large test. */
170         test(MIN_USEFUL_SIZE * 2);
171
172         /* Small test. */
173         test(MIN_USEFUL_SIZE / 2);
174
175         return exit_status();
176 }