git.ozlabs.org Git - ccan/blob - ccan/block_pool/test/run.c

   1 #include <ccan/block_pool/block_pool.h>
   2 #include <ccan/block_pool/block_pool.c>
   3 #include <ccan/tap/tap.h>
   4
   5 struct alloc_record {
   6         size_t size;
   7         char *ptr;
   8 };
   9
  10 static int compar_alloc_record_by_ptr(const void *ap, const void *bp) {
  11         const struct alloc_record *a=ap, *b=bp;
  12
  13         if (a->ptr < b->ptr)
  14                 return -1;
  15         else if (a->ptr > b->ptr)
  16                 return 1;
  17         else
  18                 return 0;
  19 }
  20
  21 static size_t random_block_size(void) {
  22         int scale = random() % 11;
  23         switch (scale) {
  24                 case 0:
  25                 case 1:
  26                 case 2:
  27                 case 3:
  28                 case 4: return random() % 25;
  29                 case 5:
  30                 case 6:
  31                 case 7: return random() % 100;
  32                 case 8:
  33                 case 9: return random() % 1000;
  34                 case 10: return random() % 10000;
  35                 default:
  36                         fprintf(stderr, "random() %% 3 returned %d somehow!\n", scale);
  37                         exit(EXIT_FAILURE);
  38         }
  39 }
  40
  41 #define L(node) (node+node+1)
  42 #define R(node) (node+node+2)
  43 #define P(node) ((node-1)>>1)
  44
  45 #define V(node) (bp->block[node].remaining)
  46
  47 //used by test_block_pool to make sure the pool's block array is a max heap
  48 //set node=0 to scan the whole heap (starting at the root)
  49 //returns nonzero on success
  50 static int check_heap(struct block_pool *bp, size_t node) {
  51         if (node < bp->count) {
  52                 if (node) { //the root node need not be the max, but its subtrees must be valid
  53                         if (L(node) < bp->count && V(L(node)) > V(node))
  54                                 return 0;
  55                         if (R(node) < bp->count && V(R(node)) > V(node))
  56                                 return 0;
  57                 }
  58                 return check_heap(bp, L(node)) && check_heap(bp, R(node));
  59         } else
  60                 return 1;
  61 }
  62
  63 #undef L
  64 #undef R
  65 #undef P
  66 #undef V
  67
  68 /* Performs a self-test of block_pool.
  69    Returns 1 on success, 0 on failure.
  70    If verify_heap is nonzero, the test will check the heap structure every
  71    single allocation, making test_block_pool take n^2 time. */
  72 static int test_block_pool(size_t blocks_to_try, FILE *out, int verify_heap) {
  73         struct block_pool *bp = block_pool_new(NULL);
  74         struct alloc_record *record = malloc(sizeof(*record) * blocks_to_try);
  75         size_t i;
  76         size_t bytes_allocated = 0;
  77         #define print(...) do { \
  78                         if (out) \
  79                                 printf(__VA_ARGS__); \
  80                 } while(0)
  81
  82         print("Allocating %zu blocks...\n", blocks_to_try);
  83
  84         for (i=0; i<blocks_to_try; i++) {
  85                 record[i].size = random_block_size();
  86                 record[i].ptr = block_pool_alloc(bp, record[i].size);
  87
  88                 bytes_allocated += record[i].size;
  89
  90                 memset(record[i].ptr, 0x55, record[i].size);
  91
  92                 if (verify_heap && !check_heap(bp, 0)) {
  93                         print("Block pool's max-heap is wrong (allocation %zu)\n", i);
  94                         return 0;
  95                 }
  96         }
  97
  98         print("Finished allocating\n"
  99                "    %zu blocks\n"
 100                "    %zu bytes\n"
 101                "    %zu pages\n",
 102                 blocks_to_try, bytes_allocated, bp->count);
 103
 104         qsort(record, blocks_to_try,
 105                 sizeof(*record), compar_alloc_record_by_ptr);
 106
 107         print("Making sure block ranges are unique...\n");
 108         //print("0: %p ... %p\n", record[0].ptr, record[0].ptr+record[0].size);
 109         for (i=1; i<blocks_to_try; i++) {
 110                 struct alloc_record *a = &record[i-1];
 111                 struct alloc_record *b = &record[i];
 112
 113                 //print("%zu: %p ... %p\n", i, b->ptr, b->ptr+b->size);
 114
 115                 if (a->ptr > b->ptr) {
 116                         struct alloc_record *tmp = a;
 117                         a = b;
 118                         b = tmp;
 119                 }
 120
 121                 if (a->ptr <= b->ptr && a->ptr+a->size <= b->ptr)
 122                         continue;
 123
 124                 print("Allocations %zu and %zu overlap\n", i-1, i);
 125                 return 0;
 126         }
 127
 128         print("Checking heap structure...\n");
 129         if (!check_heap(bp, 0)) {
 130                 print("Block pool's max-heap is wrong\n");
 131                         return 0;
 132         }
 133
 134         block_pool_free(bp);
 135         free(record);
 136
 137         return 1;
 138
 139         #undef print
 140 }
 141
 142
 143 int main(void)
 144 {
 145         plan_tests(1);
 146
 147         //test a few blocks with heap verification
 148         ok1(test_block_pool(10000, NULL, 1));
 149
 150         return exit_status();
 151 }