git.ozlabs.org Git - ccan/blob - 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 16
   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                 if (!alloc_check(mem, POOL_SIZE))
  36                         return false;
  37         }
  38         for (i = 1; i < num; i += 2) {
  39                 alloc_free(mem, POOL_SIZE, p[i]);
  40                 if (!alloc_check(mem, POOL_SIZE))
  41                         return false;
  42         }
  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[POOL_SIZE];
  52
  53         plan_tests(178);
  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 < POOL_ORD-1; 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 < POOL_ORD-1; 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 < POOL_ORD; 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 << (POOL_ORD - 1));
 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         /* Force the testing of split metadata. */
 168         alloc_init(mem, POOL_SIZE);
 169         for (i = 0; i < POOL_SIZE; i++) {
 170                 p[i] = alloc_get(mem, POOL_SIZE, getpagesize(), getpagesize());
 171                 if (!p[i])
 172                         break;
 173         }
 174         ok1(alloc_check(mem, POOL_SIZE));
 175         ok1(alloc_size(mem, POOL_SIZE, p[i-1]) >= getpagesize());
 176
 177         /* Sort them. */
 178         sort(p, i-1, addr_cmp);
 179
 180         /* Free all but the one next to the metadata. */
 181         for (i = 1; p[i]; i++)
 182                 alloc_free(mem, POOL_SIZE, p[i]);
 183         ok1(alloc_check(mem, POOL_SIZE));
 184         ok1(alloc_size(mem, POOL_SIZE, p[0]) >= getpagesize());
 185
 186         /* Now do a whole heap of subpage allocs. */
 187         for (i = 1; i < POOL_SIZE; i++) {
 188                 p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
 189                 if (!p[i])
 190                         break;
 191         }
 192         ok1(alloc_check(mem, POOL_SIZE));
 193
 194         /* Free up our page next to metadata, and should be able to alloc */
 195         alloc_free(mem, POOL_SIZE, p[0]);
 196         ok1(alloc_check(mem, POOL_SIZE));
 197         p[0] = alloc_get(mem, POOL_SIZE, 1, 1);
 198         ok1(p[0]);
 199         ok1(alloc_size(mem, POOL_SIZE, p[0]) >= 1);
 200
 201         /* Clean up. */
 202         for (i = 0; p[i]; i++)
 203                 alloc_free(mem, POOL_SIZE, p[i]);
 204         ok1(alloc_check(mem, POOL_SIZE));
 205
 206         return exit_status();
 207 }