1 #include <ccan/block_pool/block_pool.h>
2 #include <ccan/block_pool/block_pool.c>
3 #include <ccan/tap/tap.h>
10 static int compar_alloc_record_by_ptr(const void *ap, const void *bp) {
11 const struct alloc_record *a=ap, *b=bp;
15 else if (a->ptr > b->ptr)
21 static size_t random_block_size(void) {
22 int scale = random() % 11;
28 case 4: return random() % 25;
31 case 7: return random() % 100;
33 case 9: return random() % 1000;
34 case 10: return random() % 10000;
36 fprintf(stderr, "random() %% 3 returned %d somehow!\n", scale);
41 #define L(node) (node+node+1)
42 #define R(node) (node+node+2)
43 #define P(node) ((node-1)>>1)
45 #define V(node) (bp->block[node].remaining)
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))
55 if (R(node) < bp->count && V(R(node)) > V(node))
58 return check_heap(bp, L(node)) && check_heap(bp, R(node));
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);
76 size_t bytes_allocated = 0;
77 #define print(...) do { \
79 printf(__VA_ARGS__); \
82 print("Allocating %zu blocks...\n", blocks_to_try);
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);
88 bytes_allocated += record[i].size;
90 memset(record[i].ptr, 0x55, record[i].size);
92 if (verify_heap && !check_heap(bp, 0)) {
93 print("Block pool's max-heap is wrong (allocation %zu)\n", i);
98 print("Finished allocating\n"
102 blocks_to_try, bytes_allocated, bp->count);
104 qsort(record, blocks_to_try,
105 sizeof(*record), compar_alloc_record_by_ptr);
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];
113 //print("%zu: %p ... %p\n", i, b->ptr, b->ptr+b->size);
115 if (a->ptr > b->ptr) {
116 struct alloc_record *tmp = a;
121 if (a->ptr <= b->ptr && a->ptr+a->size <= b->ptr)
124 print("Allocations %zu and %zu overlap\n", i-1, i);
128 print("Checking heap structure...\n");
129 if (!check_heap(bp, 0)) {
130 print("Block pool's max-heap is wrong\n");
147 //test a few blocks with heap verification
148 ok1(test_block_pool(10000, NULL, 1));
150 return exit_status();