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 */
19int stack_fan_out = 15;
20int stack_depth = 4;
21
22/* for each call stack, allocate malloc_fan blocks */
23int malloc_fan = 4;
24
25/* for each call stack, allocate data structures having malloc_depth
26   indirection at each malloc-ed level */
27int 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 */
31int malloc_data = 5;
32
33/* every n top blocks, 1 block and all its children will be freed instead of
34   being kept */
35int free_every_n = 2;
36
37/* every n release block operation, 1 block and its children will be leaked */
38int leak_every_n = 250;
39
40
41
42struct Chunk {
43   struct Chunk* child;
44   char   s[];
45};
46
47struct Chunk** topblocks;
48int freetop = 0;
49
50/* statistics */
51long total_malloced = 0;
52int blocknr = 0;
53int blockfreed = 0;
54int blockleaked = 0;
55int total_stacks = 0;
56int releaseop = 0;
57
58void 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
70void 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
82void 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
199int 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