1 // Performance test for the leak checker from bug #191182. 2 // Nb: it must be run with --leak-resolution=high to show the quadratic 3 // behaviour caused by the large number of loss records. 4 // By Philippe Waroquiers. 5 // 6 // On my machine, before being fixed, building the loss record list took about 7 // 36 seconds, and sorting + printing it took about 20 seconds. After being 8 // fixed it took about 2 seconds, and the leak checking was only a small 9 // fraction of that. --njn 10 11 #include <stdlib.h> 12 #include <strings.h> 13 #include <stdio.h> 14 #include <math.h> 15 16 /* parameters */ 17 18 /* we will create stack_fan_out ^ stack_depth different call stacks */ 19 int stack_fan_out = 15; 20 int stack_depth = 4; 21 22 /* for each call stack, allocate malloc_fan blocks */ 23 int malloc_fan = 4; 24 25 /* for each call stack, allocate data structures having malloc_depth 26 indirection at each malloc-ed level */ 27 int malloc_depth = 2; 28 29 /* in addition to the pointer needed to maintain the levels; some more 30 bytes are allocated simulating the data stored in the data structure */ 31 int malloc_data = 5; 32 33 /* every n top blocks, 1 block and all its children will be freed instead of 34 being kept */ 35 int free_every_n = 2; 36 37 /* every n release block operation, 1 block and its children will be leaked */ 38 int leak_every_n = 250; 39 40 41 42 struct Chunk { 43 struct Chunk* child; 44 char s[]; 45 }; 46 47 struct Chunk** topblocks; 48 int freetop = 0; 49 50 /* statistics */ 51 long total_malloced = 0; 52 int blocknr = 0; 53 int blockfreed = 0; 54 int blockleaked = 0; 55 int total_stacks = 0; 56 int releaseop = 0; 57 58 void free_chunks (struct Chunk ** mem) 59 { 60 if (*mem == 0) 61 return; 62 63 free_chunks ((&(*mem)->child)); 64 65 blockfreed++; 66 free (*mem); 67 *mem = 0; 68 } 69 70 void release (struct Chunk ** mem) 71 { 72 releaseop++; 73 74 if (releaseop % leak_every_n == 0) { 75 blockleaked++; 76 *mem = 0; // lose the pointer without free-ing the blocks 77 } else { 78 free_chunks (mem); 79 } 80 } 81 82 void call_stack (int level) 83 { 84 int call_fan_out = 1; 85 86 if (level == stack_depth) { 87 int sz = sizeof(struct Chunk*) + malloc_data; 88 int d; 89 int f; 90 91 for (f = 0; f < malloc_fan; f++) { 92 struct Chunk *new = NULL; // shut gcc up 93 struct Chunk *prev = NULL; 94 95 for (d = 0; d < malloc_depth; d++) { 96 new = malloc (sz); 97 total_malloced += sz; 98 blocknr++; 99 new->child = prev; 100 prev = new; 101 } 102 topblocks[freetop] = new; 103 104 if (freetop % free_every_n == 0) { 105 release (&topblocks[freetop]); 106 } 107 freetop++; 108 } 109 110 total_stacks++; 111 112 } else { 113 /* Nb: don't common these up into a loop! We need different code 114 locations to exercise the problem. */ 115 call_stack (level + 1); 116 if (call_fan_out == stack_fan_out) return; 117 call_fan_out++; 118 119 call_stack (level + 1); 120 if (call_fan_out == stack_fan_out) return; 121 call_fan_out++; 122 123 call_stack (level + 1); 124 if (call_fan_out == stack_fan_out) return; 125 call_fan_out++; 126 127 call_stack (level + 1); 128 if (call_fan_out == stack_fan_out) return; 129 call_fan_out++; 130 131 call_stack (level + 1); 132 if (call_fan_out == stack_fan_out) return; 133 call_fan_out++; 134 135 call_stack (level + 1); 136 if (call_fan_out == stack_fan_out) return; 137 call_fan_out++; 138 139 call_stack (level + 1); 140 if (call_fan_out == stack_fan_out) return; 141 call_fan_out++; 142 143 call_stack (level + 1); 144 if (call_fan_out == stack_fan_out) return; 145 call_fan_out++; 146 147 call_stack (level + 1); 148 if (call_fan_out == stack_fan_out) return; 149 call_fan_out++; 150 151 call_stack (level + 1); 152 if (call_fan_out == stack_fan_out) return; 153 call_fan_out++; 154 155 call_stack (level + 1); 156 if (call_fan_out == stack_fan_out) return; 157 call_fan_out++; 158 159 call_stack (level + 1); 160 if (call_fan_out == stack_fan_out) return; 161 call_fan_out++; 162 163 call_stack (level + 1); 164 if (call_fan_out == stack_fan_out) return; 165 call_fan_out++; 166 167 call_stack (level + 1); 168 if (call_fan_out == stack_fan_out) return; 169 call_fan_out++; 170 171 call_stack (level + 1); 172 if (call_fan_out == stack_fan_out) return; 173 call_fan_out++; 174 175 call_stack (level + 1); 176 if (call_fan_out == stack_fan_out) return; 177 call_fan_out++; 178 179 call_stack (level + 1); 180 if (call_fan_out == stack_fan_out) return; 181 call_fan_out++; 182 183 call_stack (level + 1); 184 if (call_fan_out == stack_fan_out) return; 185 call_fan_out++; 186 187 call_stack (level + 1); 188 if (call_fan_out == stack_fan_out) return; 189 call_fan_out++; 190 191 call_stack (level + 1); 192 if (call_fan_out == stack_fan_out) return; 193 call_fan_out++; 194 195 printf ("maximum stack_fan_out exceeded\n"); 196 } 197 } 198 199 int main() 200 { 201 int d; 202 int stacks = 1; 203 for (d = 0; d < stack_depth; d++) 204 stacks *= stack_fan_out; 205 printf ("will generate %d different stacks\n", stacks); 206 topblocks = malloc(sizeof(struct Chunk*) * stacks * malloc_fan); 207 call_stack (0); 208 printf ("total stacks %d\n", total_stacks); 209 printf ("total bytes malloc-ed: %ld\n", total_malloced); 210 printf ("total blocks malloc-ed: %d\n", blocknr); 211 printf ("total blocks free-ed: %d\n", blockfreed); 212 printf ("total blocks leak-ed: %d\n", blockleaked); 213 return 0; 214 } 215
