git.ozlabs.org Git - ccan/blob - 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 }