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/. */
11 #include "nsQuickSort.h"
14 const uint32_t kPointersDefaultSize
= 8;
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
25 struct AllocationNode
{
26 const ADLog::Entry
*entry
;
28 // Other |AllocationNode| objects whose memory has a pointer to
30 nsAutoTArray
<AllocationNode
*, kPointersDefaultSize
> pointers_to
;
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.
44 static PLHashNumber
hash_pointer(const void *key
)
46 return (PLHashNumber
) NS_PTR_TO_INT32(key
);
49 static int sort_by_index(const void* e1
, const void* e2
, void*)
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
;
56 static int sort_by_reverse_index(const void* e1
, const void* e2
, void*)
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
;
63 static void print_escaped(FILE *aStream
, const char* aData
)
68 while ((c
= *aData
++)) {
70 #define CH(char) *p++ = char
72 CH('&'); CH('l'); CH('t'); CH(';');
75 CH('&'); CH('g'); CH('t'); CH(';');
78 CH('&'); CH('a'); CH('m'); CH('p'); CH(';');
85 if (p
+ 10 > buf
+ sizeof(buf
)) {
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
)
104 "Expected usage: %s <sd-leak-file>\n"
105 " sd-leak-file: Output of --shutdown-leaks=<file> option.\n",
110 NS_InitXPCOM2(nullptr, nullptr, nullptr);
113 if (!log
.Read(argv
[1])) {
115 "%s: Error reading input file %s.\n", argv
[0], argv
[1]);
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);
124 fprintf(stderr
, "%s: Out of memory.\n", argv
[0]);
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
];
132 fprintf(stderr
, "%s: Out of memory.\n", argv
[0]);
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
;
146 PLHashEntry
*he
= PL_HashTableAdd(memory_map
, p
, cur_node
);
148 fprintf(stderr
, "%s: Out of memory.\n", argv
[0]);
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
);
165 target
->pointers_from
.AppendElement(node
);
166 node
->pointers_to
.AppendElement(target
);
171 // Do a depth-first search on the graph (i.e., by following
172 // |pointers_to|) and assign the post-order index to |index|.
174 uint32_t dfs_index
= 0;
175 nsTArray
<AllocationNode
*> stack
;
177 for (AllocationNode
*n
= nodes
, *n_end
= nodes
+count
; n
!= n_end
; ++n
) {
181 stack
.AppendElement(n
);
184 uint32_t pos
= stack
.Length() - 1;
185 AllocationNode
*n
= stack
[pos
];
187 n
->index
= dfs_index
++;
188 stack
.RemoveElementAt(pos
);
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
];
197 stack
.AppendElement(e
);
201 } while (stack
.Length() > 0);
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
];
209 fprintf(stderr
, "%s: Out of memory.\n", argv
[0]);
214 for (size_t i
= 0; i
< count
; ++i
) {
215 sorted_nodes
[i
] = nodes
+ i
;
217 NS_QuickSort(sorted_nodes
, count
, sizeof(AllocationNode
*),
218 sort_by_reverse_index
, 0);
221 // Put the nodes into their strongly-connected components.
222 uint32_t num_sccs
= 0;
224 for (size_t i
= 0; i
< count
; ++i
) {
225 nodes
[i
].reached
= false;
227 nsTArray
<AllocationNode
*> stack
;
228 for (AllocationNode
**sn
= sorted_nodes
,
229 **sn_end
= sorted_nodes
+ count
; sn
!= sn_end
; ++sn
) {
230 if ((*sn
)->reached
) {
234 // We found a new strongly connected index.
235 stack
.AppendElement(*sn
);
237 uint32_t pos
= stack
.Length() - 1;
238 AllocationNode
*n
= stack
[pos
];
239 stack
.RemoveElementAt(pos
);
244 stack
.AppendElements(n
->pointers_from
);
246 } while (stack
.Length() > 0);
251 // Identify which nodes are leak roots by using DFS, and watching
252 // for component transitions.
253 uint32_t num_root_nodes
= count
;
255 for (size_t i
= 0; i
< count
; ++i
) {
256 nodes
[i
].is_root
= true;
259 nsTArray
<AllocationNode
*> stack
;
260 for (AllocationNode
*n
= nodes
, *n_end
= nodes
+count
; n
!= n_end
; ++n
) {
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
);
274 while (stack
.Length() > 0) {
275 uint32_t pos
= stack
.Length() - 1;
276 AllocationNode
*n
= stack
[pos
];
277 stack
.RemoveElementAt(pos
);
282 stack
.AppendElements(n
->pointers_to
);
288 // Sort the nodes by their SCC index.
289 NS_QuickSort(sorted_nodes
, count
, sizeof(AllocationNode
*),
294 printf("<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\">\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"
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;
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
) {
317 "<div class=\"root\">\n"
318 "<h1 id=\"root\">Root components</h1>\n");
321 "<div class=\"nonroot\">\n"
322 "<h1 id=\"nonroot\">Non-root components</h1>\n");
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
)
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
);
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
);
349 printf("\n\n<h3 id=\"o%td\">Object %td</h3>\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
));
360 printf(" <a href=\"#o%td\">",
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
);
372 printf(allocation_format
,
373 *(size_t*)(e
->data
+ d
));
378 if (n
->pointers_from
.Length()) {
379 printf("\nPointers from:\n");
380 for (uint32_t i
= 0, i_end
= n
->pointers_from
.Length();
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
);
392 printf("%p)\n", te
->address
);
397 print_escaped(stdout
, e
->allocation_stack
);
400 if (one_object_component
) {
410 delete [] sorted_nodes
;
413 NS_ShutdownXPCOM(nullptr);