1436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// Performance test for the leak checker from bug #191182. 2436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// Nb: it must be run with --leak-resolution=high to show the quadratic 3436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// behaviour caused by the large number of loss records. 4436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// By Philippe Waroquiers. 5436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// 6436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// On my machine, before being fixed, building the loss record list took about 7436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// 36 seconds, and sorting + printing it took about 20 seconds. After being 8436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// fixed it took about 2 seconds, and the leak checking was only a small 9436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov// fraction of that. --njn 10436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 11436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov#include <stdlib.h> 12436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov#include <strings.h> 13436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov#include <stdio.h> 14436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov#include <math.h> 15436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 16436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* parameters */ 17436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 18436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* we will create stack_fan_out ^ stack_depth different call stacks */ 19436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint stack_fan_out = 15; 20436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint stack_depth = 4; 21436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 22436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* for each call stack, allocate malloc_fan blocks */ 23436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint malloc_fan = 4; 24436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 25436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* for each call stack, allocate data structures having malloc_depth 26436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov indirection at each malloc-ed level */ 27436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint malloc_depth = 2; 28436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 29436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* in addition to the pointer needed to maintain the levels; some more 30436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov bytes are allocated simulating the data stored in the data structure */ 31436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint malloc_data = 5; 32436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 33436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* every n top blocks, 1 block and all its children will be freed instead of 34436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov being kept */ 35436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint free_every_n = 2; 36436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 37436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* every n release block operation, 1 block and its children will be leaked */ 38436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint leak_every_n = 250; 39436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 40436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 41436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 42436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovstruct Chunk { 43436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov struct Chunk* child; 44436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov char s[]; 45436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov}; 46436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 47436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovstruct Chunk** topblocks; 48436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint freetop = 0; 49436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 50436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* statistics */ 51436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovlong total_malloced = 0; 52436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint blocknr = 0; 53436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint blockfreed = 0; 54436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint blockleaked = 0; 55436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint total_stacks = 0; 56436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint releaseop = 0; 57436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 58436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid free_chunks (struct Chunk ** mem) 59436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov{ 60436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (*mem == 0) 61436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return; 62436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 63436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov free_chunks ((&(*mem)->child)); 64436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 65436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov blockfreed++; 66436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov free (*mem); 67436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov *mem = 0; 68436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov} 69436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 70436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid release (struct Chunk ** mem) 71436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov{ 72436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov releaseop++; 73436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 74436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (releaseop % leak_every_n == 0) { 75436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov blockleaked++; 76436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov *mem = 0; // lose the pointer without free-ing the blocks 77436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } else { 78436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov free_chunks (mem); 79436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 80436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov} 81436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 82436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid call_stack (int level) 83436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov{ 84436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov int call_fan_out = 1; 85436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 86436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (level == stack_depth) { 87436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov int sz = sizeof(struct Chunk*) + malloc_data; 88436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov int d; 89436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov int f; 90436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 91436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov for (f = 0; f < malloc_fan; f++) { 92436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov struct Chunk *new = NULL; // shut gcc up 93436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov struct Chunk *prev = NULL; 94436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 95436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov for (d = 0; d < malloc_depth; d++) { 96436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov new = malloc (sz); 97436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov total_malloced += sz; 98436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov blocknr++; 99436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov new->child = prev; 100436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov prev = new; 101436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 102436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov topblocks[freetop] = new; 103436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 104436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (freetop % free_every_n == 0) { 105436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov release (&topblocks[freetop]); 106436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 107436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov freetop++; 108436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 109436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 110436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov total_stacks++; 111436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 112436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } else { 113436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov /* Nb: don't common these up into a loop! We need different code 114436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov locations to exercise the problem. */ 115436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 116436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 117436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 118436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 119436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 120436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 121436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 122436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 123436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 124436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 125436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 126436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 127436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 128436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 129436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 130436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 131436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 132436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 133436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 134436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 135436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 136436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 137436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 138436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 139436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 140436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 141436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 142436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 143436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 144436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 145436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 146436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 147436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 148436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 149436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 150436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 151436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 152436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 153436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 154436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 155436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 156436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 157436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 158436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 159436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 160436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 161436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 162436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 163436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 164436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 165436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 166436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 167436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 168436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 169436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 170436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 171436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 172436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 173436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 174436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 175436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 176436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 177436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 178436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 179436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 180436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 181436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 182436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 183436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 184436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 185436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 186436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 187436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 188436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 189436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 190436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 191436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (level + 1); 192436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov if (call_fan_out == stack_fan_out) return; 193436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_fan_out++; 194436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 195436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov printf ("maximum stack_fan_out exceeded\n"); 196436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov } 197436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov} 198436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 199436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint main() 200436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov{ 201436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov int d; 202436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov int stacks = 1; 203436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov for (d = 0; d < stack_depth; d++) 204436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov stacks *= stack_fan_out; 205436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov printf ("will generate %d different stacks\n", stacks); 206436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov topblocks = malloc(sizeof(struct Chunk*) * stacks * malloc_fan); 207436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov call_stack (0); 208436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov printf ("total stacks %d\n", total_stacks); 209436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov printf ("total bytes malloc-ed: %ld\n", total_malloced); 210436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov printf ("total blocks malloc-ed: %d\n", blocknr); 211436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov printf ("total blocks free-ed: %d\n", blockfreed); 212436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov printf ("total blocks leak-ed: %d\n", blockleaked); 213436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov return 0; 214436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov} 215