perf/many-loss-records.c

   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 }