c3f09626446497512993443722609315485571df
[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 <stdlib.h>
5 #include <err.h>
6
7 #define POOL_ORD 20
8 #define POOL_SIZE (1 << POOL_ORD)
9
10 #define sort(p, num, cmp) \
11         qsort((p), (num), sizeof(*p), (int(*)(const void *, const void *))cmp)
12
13 static int addr_cmp(void **a, void **b)
14 {
15         return (*a) - (*b);
16 }
17
18 static bool unique(void *p[], unsigned int num)
19 {
20         unsigned int i;
21
22         for (i = 1; i < num; i++)
23                 if (p[i] == p[i-1])
24                         return false;
25         return true;
26 }       
27
28 static bool free_every_second_one(void *mem, unsigned int num, 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
47 int main(int argc, char *argv[])
48 {
49         void *mem;
50         unsigned int i, num, max_size;
51         void **p = calloc(POOL_SIZE, sizeof(*p));
52
53         plan_tests(120);
54
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"); 
58
59         /* Small pool, all allocs fail, even 0-length. */
60         alloc_init(mem, 0);
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);
65
66         /* Free of NULL should work. */
67         alloc_free(mem, 0, NULL);
68
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);
74                 if (p[0])
75                         break;
76         }
77         ok1(max_size < POOL_SIZE);
78         ok1(max_size > 0);
79         ok1(alloc_check(mem, POOL_SIZE));
80         ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
81
82         /* Free it, should be able to reallocate it. */
83         alloc_free(mem, POOL_SIZE, p[0]);
84         ok1(alloc_check(mem, POOL_SIZE));
85
86         p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
87         ok1(p[0]);
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));
92
93         /* Allocate a whole heap. */
94         for (i = 0; i < POOL_SIZE; i++) {
95                 p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
96                 if (!p[i])
97                         break;
98         }
99
100         /* Uncomment this for a more intuitive view of what the
101          * allocator looks like after all these 1 byte allocs. */
102 #if 0
103         alloc_visualize(stderr, mem, POOL_SIZE);
104 #endif
105
106         num = i;
107         /* Can't allocate this many. */
108         ok1(num != POOL_SIZE);
109         ok1(alloc_check(mem, POOL_SIZE));
110
111         /* Sort them. */
112         sort(p, num, addr_cmp);
113
114         /* Uniqueness check */
115         ok1(unique(p, num));
116
117         ok1(free_every_second_one(mem, num, p));
118         ok1(alloc_check(mem, POOL_SIZE));
119
120         /* Should be able to reallocate max size. */
121         p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
122         ok1(p[0]);
123         ok1(alloc_check(mem, POOL_SIZE));
124         ok1(alloc_size(mem, POOL_SIZE, p[0]) >= max_size);
125
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);
130         ok1(p[0]);
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));
135
136         /* Alignment constraints should be met, as long as powers of two */
137         for (i = 0; i < /*FIXME: POOL_ORD-1*/ 10; i++) {
138                 p[i] = alloc_get(mem, POOL_SIZE, i, 1 << i);
139                 ok1(p[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);
143         }
144
145         for (i = 0; i < /*FIXME: POOL_ORD-1*/ 10; i++) {
146                 alloc_free(mem, POOL_SIZE, p[i]);
147                 ok1(alloc_check(mem, POOL_SIZE));
148         }
149
150         /* Alignment constraints for a single-byte allocation. */
151         for (i = 0; i < /*FIXME: POOL_ORD*/ 10; i++) {
152                 p[0] = alloc_get(mem, POOL_SIZE, 1, 1 << i);
153                 ok1(p[0]);
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));
158         }
159
160         /* Alignment check for a 0-byte allocation.  Corner case. */
161         p[0] = alloc_get(mem, POOL_SIZE, 0, 1 << (/*FIXME: POOL_ORD - 1*/ 10));
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));
166
167         return exit_status();
168 }