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
free_chunks(struct Chunk ** mem)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
release(struct Chunk ** mem)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
call_stack(int level)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
main()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