tools/trace-malloc/leaksoup.cpp@b8a032363ba2
tools/trace-malloc/leaksoup.cpp
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 #include "adreader.h"
7 #include <stdio.h>
8 #include "plhash.h"
10 #include "nsTArray.h"
11 #include "nsQuickSort.h"
12 #include "nsXPCOM.h"
14 const uint32_t kPointersDefaultSize = 8;
16 /*
17 * Read in an allocation dump, presumably one taken at shutdown (using
18 * the --shutdown-leaks=file option, which must be used along with
19 * --trace-malloc=tmlog), and treat the memory in the dump as leaks.
20 * Find the leak roots, including cycles that are roots, by finding the
21 * strongly connected components in the graph. Print output to stdout
22 * as HTML.
23 */
25 struct AllocationNode {
26 const ADLog::Entry *entry;
28 // Other |AllocationNode| objects whose memory has a pointer to
29 // this object.
30 nsAutoTArray<AllocationNode*, kPointersDefaultSize> pointers_to;
32 // The reverse.
33 nsAutoTArray<AllocationNode*, kPointersDefaultSize> pointers_from;
35 // Early on in the algorithm, the pre-order index from a DFS.
36 // Later on, set to the index of the strongly connected component to
37 // which this node belongs.
38 uint32_t index;
40 bool reached;
41 bool is_root;
42 };
44 static PLHashNumber hash_pointer(const void *key)
45 {
46 return (PLHashNumber) NS_PTR_TO_INT32(key);
47 }
49 static int sort_by_index(const void* e1, const void* e2, void*)
50 {
51 const AllocationNode *n1 = *static_cast<const AllocationNode*const*>(e1);
52 const AllocationNode *n2 = *static_cast<const AllocationNode*const*>(e2);
53 return n1->index - n2->index;
54 }
56 static int sort_by_reverse_index(const void* e1, const void* e2, void*)
57 {
58 const AllocationNode *n1 = *static_cast<const AllocationNode*const*>(e1);
59 const AllocationNode *n2 = *static_cast<const AllocationNode*const*>(e2);
60 return n2->index - n1->index;
61 }
63 static void print_escaped(FILE *aStream, const char* aData)
64 {
65 char c;
66 char buf[1000];
67 char *p = buf;
68 while ((c = *aData++)) {
69 switch (c) {
70 #define CH(char) *p++ = char
71 case '<':
72 CH('&'); CH('l'); CH('t'); CH(';');
73 break;
74 case '>':
75 CH('&'); CH('g'); CH('t'); CH(';');
76 break;
77 case '&':
78 CH('&'); CH('a'); CH('m'); CH('p'); CH(';');
79 break;
80 default:
81 CH(c);
82 break;
83 #undef CH
84 }
85 if (p + 10 > buf + sizeof(buf)) {
86 *p = '\0';
87 fputs(buf, aStream);
88 p = buf;
89 }
90 }
91 *p = '\0';
92 fputs(buf, aStream);
93 }
95 static const char *allocation_format =
96 (sizeof(ADLog::Pointer) == 4) ? "0x%08zX" :
97 (sizeof(ADLog::Pointer) == 8) ? "0x%016zX" :
98 "UNEXPECTED sizeof(void*)";
100 int main(int argc, char **argv)
101 {
102 if (argc != 2) {
103 fprintf(stderr,
104 "Expected usage: %s <sd-leak-file>\n"
105 " sd-leak-file: Output of --shutdown-leaks=<file> option.\n",
106 argv[0]);
107 return 1;
108 }
110 NS_InitXPCOM2(nullptr, nullptr, nullptr);
112 ADLog log;
113 if (!log.Read(argv[1])) {
114 fprintf(stderr,
115 "%s: Error reading input file %s.\n", argv[0], argv[1]);
116 }
118 const size_t count = log.count();
120 PLHashTable *memory_map =
121 PL_NewHashTable(count * 8, hash_pointer, PL_CompareValues,
122 PL_CompareValues, 0, 0);
123 if (!memory_map) {
124 fprintf(stderr, "%s: Out of memory.\n", argv[0]);
125 return 1;
126 }
128 // Create one |AllocationNode| object for each log entry, and create
129 // entries in the hashtable pointing to it for each byte it occupies.
130 AllocationNode *nodes = new AllocationNode[count];
131 if (!nodes) {
132 fprintf(stderr, "%s: Out of memory.\n", argv[0]);
133 return 1;
134 }
136 {
137 AllocationNode *cur_node = nodes;
138 for (ADLog::const_iterator entry = log.begin(), entry_end = log.end();
139 entry != entry_end; ++entry, ++cur_node) {
140 const ADLog::Entry *e = cur_node->entry = *entry;
141 cur_node->reached = false;
143 for (ADLog::Pointer p = e->address,
144 p_end = e->address + e->datasize;
145 p != p_end; ++p) {
146 PLHashEntry *he = PL_HashTableAdd(memory_map, p, cur_node);
147 if (!he) {
148 fprintf(stderr, "%s: Out of memory.\n", argv[0]);
149 return 1;
150 }
151 }
152 }
153 }
155 // Construct graph based on pointers.
156 for (AllocationNode *node = nodes, *node_end = nodes + count;
157 node != node_end; ++node) {
158 const ADLog::Entry *e = node->entry;
159 for (const char *d = e->data, *d_end = e->data + e->datasize -
160 e->datasize % sizeof(ADLog::Pointer);
161 d != d_end; d += sizeof(ADLog::Pointer)) {
162 AllocationNode *target = (AllocationNode*)
163 PL_HashTableLookup(memory_map, *(void**)d);
164 if (target) {
165 target->pointers_from.AppendElement(node);
166 node->pointers_to.AppendElement(target);
167 }
168 }
169 }
171 // Do a depth-first search on the graph (i.e., by following
172 // |pointers_to|) and assign the post-order index to |index|.
173 {
174 uint32_t dfs_index = 0;
175 nsTArray<AllocationNode*> stack;
177 for (AllocationNode *n = nodes, *n_end = nodes+count; n != n_end; ++n) {
178 if (n->reached) {
179 continue;
180 }
181 stack.AppendElement(n);
183 do {
184 uint32_t pos = stack.Length() - 1;
185 AllocationNode *n = stack[pos];
186 if (n->reached) {
187 n->index = dfs_index++;
188 stack.RemoveElementAt(pos);
189 } else {
190 n->reached = true;
192 // When doing post-order processing, we have to be
193 // careful not to put reached nodes into the stack.
194 for (int32_t i = n->pointers_to.Length() - 1; i >= 0; --i) {
195 AllocationNode* e = n->pointers_to[i];
196 if (!e->reached) {
197 stack.AppendElement(e);
198 }
199 }
200 }
201 } while (stack.Length() > 0);
202 }
203 }
205 // Sort the nodes by their DFS index, in reverse, so that the first
206 // node is guaranteed to be in a root SCC.
207 AllocationNode **sorted_nodes = new AllocationNode*[count];
208 if (!sorted_nodes) {
209 fprintf(stderr, "%s: Out of memory.\n", argv[0]);
210 return 1;
211 }
213 {
214 for (size_t i = 0; i < count; ++i) {
215 sorted_nodes[i] = nodes + i;
216 }
217 NS_QuickSort(sorted_nodes, count, sizeof(AllocationNode*),
218 sort_by_reverse_index, 0);
219 }
221 // Put the nodes into their strongly-connected components.
222 uint32_t num_sccs = 0;
223 {
224 for (size_t i = 0; i < count; ++i) {
225 nodes[i].reached = false;
226 }
227 nsTArray<AllocationNode*> stack;
228 for (AllocationNode **sn = sorted_nodes,
229 **sn_end = sorted_nodes + count; sn != sn_end; ++sn) {
230 if ((*sn)->reached) {
231 continue;
232 }
234 // We found a new strongly connected index.
235 stack.AppendElement(*sn);
236 do {
237 uint32_t pos = stack.Length() - 1;
238 AllocationNode *n = stack[pos];
239 stack.RemoveElementAt(pos);
241 if (!n->reached) {
242 n->reached = true;
243 n->index = num_sccs;
244 stack.AppendElements(n->pointers_from);
245 }
246 } while (stack.Length() > 0);
247 ++num_sccs;
248 }
249 }
251 // Identify which nodes are leak roots by using DFS, and watching
252 // for component transitions.
253 uint32_t num_root_nodes = count;
254 {
255 for (size_t i = 0; i < count; ++i) {
256 nodes[i].is_root = true;
257 }
259 nsTArray<AllocationNode*> stack;
260 for (AllocationNode *n = nodes, *n_end = nodes+count; n != n_end; ++n) {
261 if (!n->is_root) {
262 continue;
263 }
265 // Loop through pointers_to, and add any that are in a
266 // different SCC to stack:
267 for (int i = n->pointers_to.Length() - 1; i >= 0; --i) {
268 AllocationNode *target = n->pointers_to[i];
269 if (n->index != target->index) {
270 stack.AppendElement(target);
271 }
272 }
274 while (stack.Length() > 0) {
275 uint32_t pos = stack.Length() - 1;
276 AllocationNode *n = stack[pos];
277 stack.RemoveElementAt(pos);
279 if (n->is_root) {
280 n->is_root = false;
281 --num_root_nodes;
282 stack.AppendElements(n->pointers_to);
283 }
284 }
285 }
286 }
288 // Sort the nodes by their SCC index.
289 NS_QuickSort(sorted_nodes, count, sizeof(AllocationNode*),
290 sort_by_index, 0);
292 // Print output.
293 {
294 printf("<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\">\n"
295 "<html>\n"
296 "<head>\n"
297 "<title>Leak analysis</title>\n"
298 "<style type=\"text/css\">\n"
299 " .root { background: white; color: black; }\n"
300 " .nonroot { background: #ccc; color: black; }\n"
301 "</style>\n"
302 "</head>\n");
303 printf("<body>\n\n"
304 "<p>Generated %zd entries (%d in root SCCs) and %d SCCs.</p>\n\n",
305 count, num_root_nodes, num_sccs);
307 for (size_t i = 0; i < count; ++i) {
308 nodes[i].reached = false;
309 }
311 // Loop over the sorted nodes twice, first printing the roots
312 // and then the non-roots.
313 for (int32_t root_type = true;
314 root_type == true || root_type == false; --root_type) {
315 if (root_type) {
316 printf("\n\n"
317 "<div class=\"root\">\n"
318 "<h1 id=\"root\">Root components</h1>\n");
319 } else {
320 printf("\n\n"
321 "<div class=\"nonroot\">\n"
322 "<h1 id=\"nonroot\">Non-root components</h1>\n");
323 }
324 uint32_t component = (uint32_t)-1;
325 bool one_object_component;
326 for (const AllocationNode *const* sn = sorted_nodes,
327 *const* sn_end = sorted_nodes + count;
328 sn != sn_end; ++sn) {
329 const AllocationNode *n = *sn;
330 if (n->is_root != root_type)
331 continue;
332 const ADLog::Entry *e = n->entry;
334 if (n->index != component) {
335 component = n->index;
336 one_object_component =
337 sn + 1 == sn_end || (*(sn+1))->index != component;
338 if (!one_object_component)
339 printf("\n\n<h2 id=\"c%d\">Component %d</h2>\n",
340 component, component);
341 }
343 if (one_object_component) {
344 printf("\n\n<div id=\"c%d\">\n", component);
345 printf("<h2 id=\"o%td\">Object %td "
346 "(single-object component %d)</h2>\n",
347 n-nodes, n-nodes, component);
348 } else {
349 printf("\n\n<h3 id=\"o%td\">Object %td</h3>\n",
350 n-nodes, n-nodes);
351 }
352 printf("<pre>\n");
353 printf("%p <%s> (%zd)\n",
354 e->address, e->type, e->datasize);
355 for (size_t d = 0; d < e->datasize;
356 d += sizeof(ADLog::Pointer)) {
357 AllocationNode *target = (AllocationNode*)
358 PL_HashTableLookup(memory_map, *(void**)(e->data + d));
359 if (target) {
360 printf(" <a href=\"#o%td\">",
361 target - nodes);
362 printf(allocation_format,
363 *(size_t*)(e->data + d));
364 printf("</a> <%s>",
365 target->entry->type);
366 if (target->index != n->index) {
367 printf(", component %d", target->index);
368 }
369 printf("\n");
370 } else {
371 printf(" ");
372 printf(allocation_format,
373 *(size_t*)(e->data + d));
374 printf("\n");
375 }
376 }
378 if (n->pointers_from.Length()) {
379 printf("\nPointers from:\n");
380 for (uint32_t i = 0, i_end = n->pointers_from.Length();
381 i != i_end; ++i) {
382 AllocationNode *t = n->pointers_from[i];
383 const ADLog::Entry *te = t->entry;
384 printf(" <a href=\"#o%td\">%s</a> (Object %td, ",
385 t - nodes, te->type, t - nodes);
386 if (t->index != n->index) {
387 printf("component %d, ", t->index);
388 }
389 if (t == n) {
390 printf("self)\n");
391 } else {
392 printf("%p)\n", te->address);
393 }
394 }
395 }
397 print_escaped(stdout, e->allocation_stack);
399 printf("</pre>\n");
400 if (one_object_component) {
401 printf("</div>\n");
402 }
403 }
404 printf("</div>\n");
405 }
406 printf("</body>\n"
407 "</html>\n");
408 }
410 delete [] sorted_nodes;
411 delete [] nodes;
413 NS_ShutdownXPCOM(nullptr);
415 return 0;
416 }
