michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "adreader.h"
michael@0: 
michael@0: #include <stdio.h>
michael@0: #include "plhash.h"
michael@0: 
michael@0: #include "nsTArray.h"
michael@0: #include "nsQuickSort.h"
michael@0: #include "nsXPCOM.h"
michael@0: 
michael@0: const uint32_t kPointersDefaultSize = 8;
michael@0: 
michael@0: /*
michael@0:  * Read in an allocation dump, presumably one taken at shutdown (using
michael@0:  * the --shutdown-leaks=file option, which must be used along with
michael@0:  * --trace-malloc=tmlog), and treat the memory in the dump as leaks.
michael@0:  * Find the leak roots, including cycles that are roots, by finding the
michael@0:  * strongly connected components in the graph.  Print output to stdout
michael@0:  * as HTML.
michael@0:  */
michael@0: 
michael@0: struct AllocationNode {
michael@0:     const ADLog::Entry *entry;
michael@0: 
michael@0:     // Other |AllocationNode| objects whose memory has a pointer to
michael@0:     // this object.
michael@0:     nsAutoTArray<AllocationNode*, kPointersDefaultSize> pointers_to;
michael@0: 
michael@0:     // The reverse.
michael@0:     nsAutoTArray<AllocationNode*, kPointersDefaultSize> pointers_from;
michael@0: 
michael@0:     // Early on in the algorithm, the pre-order index from a DFS.
michael@0:     // Later on, set to the index of the strongly connected component to
michael@0:     // which this node belongs.
michael@0:     uint32_t index;
michael@0: 
michael@0:     bool reached;
michael@0:     bool is_root;
michael@0: };
michael@0: 
michael@0: static PLHashNumber hash_pointer(const void *key)
michael@0: {
michael@0:     return (PLHashNumber) NS_PTR_TO_INT32(key);
michael@0: }
michael@0: 
michael@0: static int sort_by_index(const void* e1, const void* e2, void*)
michael@0: {
michael@0:     const AllocationNode *n1 = *static_cast<const AllocationNode*const*>(e1);
michael@0:     const AllocationNode *n2 = *static_cast<const AllocationNode*const*>(e2);
michael@0:     return n1->index - n2->index;
michael@0: }
michael@0: 
michael@0: static int sort_by_reverse_index(const void* e1, const void* e2, void*)
michael@0: {
michael@0:     const AllocationNode *n1 = *static_cast<const AllocationNode*const*>(e1);
michael@0:     const AllocationNode *n2 = *static_cast<const AllocationNode*const*>(e2);
michael@0:     return n2->index - n1->index;
michael@0: }
michael@0: 
michael@0: static void print_escaped(FILE *aStream, const char* aData)
michael@0: {
michael@0:     char c;
michael@0:     char buf[1000];
michael@0:     char *p = buf;
michael@0:     while ((c = *aData++)) {
michael@0:         switch (c) {
michael@0: #define CH(char) *p++ = char
michael@0:             case '<':
michael@0:                 CH('&'); CH('l'); CH('t'); CH(';');
michael@0:                 break;
michael@0:             case '>':
michael@0:                 CH('&'); CH('g'); CH('t'); CH(';');
michael@0:                 break;
michael@0:             case '&':
michael@0:                 CH('&'); CH('a'); CH('m'); CH('p'); CH(';');
michael@0:                 break;
michael@0:             default:
michael@0:                 CH(c);
michael@0:                 break;
michael@0: #undef CH
michael@0:         }
michael@0:         if (p + 10 > buf + sizeof(buf)) {
michael@0:             *p = '\0';
michael@0:             fputs(buf, aStream);
michael@0:             p = buf;
michael@0:         }
michael@0:     }
michael@0:     *p = '\0';
michael@0:     fputs(buf, aStream);
michael@0: }
michael@0: 
michael@0: static const char *allocation_format =
michael@0:   (sizeof(ADLog::Pointer) == 4) ? "0x%08zX" :
michael@0:   (sizeof(ADLog::Pointer) == 8) ? "0x%016zX" :
michael@0:   "UNEXPECTED sizeof(void*)";
michael@0: 
michael@0: int main(int argc, char **argv)
michael@0: {
michael@0:     if (argc != 2) {
michael@0:         fprintf(stderr,
michael@0:                 "Expected usage:  %s <sd-leak-file>\n"
michael@0:                 "  sd-leak-file: Output of --shutdown-leaks=<file> option.\n",
michael@0:                 argv[0]);
michael@0:         return 1;
michael@0:     }
michael@0: 
michael@0:     NS_InitXPCOM2(nullptr, nullptr, nullptr);
michael@0: 
michael@0:     ADLog log;
michael@0:     if (!log.Read(argv[1])) {
michael@0:         fprintf(stderr,
michael@0:                 "%s: Error reading input file %s.\n", argv[0], argv[1]);
michael@0:     }
michael@0: 
michael@0:     const size_t count = log.count();
michael@0: 
michael@0:     PLHashTable *memory_map =
michael@0:         PL_NewHashTable(count * 8, hash_pointer, PL_CompareValues,
michael@0:                         PL_CompareValues, 0, 0);
michael@0:     if (!memory_map) {
michael@0:         fprintf(stderr, "%s: Out of memory.\n", argv[0]);
michael@0:         return 1;
michael@0:     }
michael@0: 
michael@0:     // Create one |AllocationNode| object for each log entry, and create
michael@0:     // entries in the hashtable pointing to it for each byte it occupies.
michael@0:     AllocationNode *nodes = new AllocationNode[count];
michael@0:     if (!nodes) {
michael@0:         fprintf(stderr, "%s: Out of memory.\n", argv[0]);
michael@0:         return 1;
michael@0:     }
michael@0: 
michael@0:     {
michael@0:         AllocationNode *cur_node = nodes;
michael@0:         for (ADLog::const_iterator entry = log.begin(), entry_end = log.end();
michael@0:              entry != entry_end; ++entry, ++cur_node) {
michael@0:             const ADLog::Entry *e = cur_node->entry = *entry;
michael@0:             cur_node->reached = false;
michael@0: 
michael@0:             for (ADLog::Pointer p = e->address,
michael@0:                             p_end = e->address + e->datasize;
michael@0:                  p != p_end; ++p) {
michael@0:                 PLHashEntry *he = PL_HashTableAdd(memory_map, p, cur_node);
michael@0:                 if (!he) {
michael@0:                     fprintf(stderr, "%s: Out of memory.\n", argv[0]);
michael@0:                     return 1;
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Construct graph based on pointers.
michael@0:     for (AllocationNode *node = nodes, *node_end = nodes + count;
michael@0:          node != node_end; ++node) {
michael@0:         const ADLog::Entry *e = node->entry;
michael@0:         for (const char *d = e->data, *d_end = e->data + e->datasize -
michael@0:                                          e->datasize % sizeof(ADLog::Pointer);
michael@0:              d != d_end; d += sizeof(ADLog::Pointer)) {
michael@0:             AllocationNode *target = (AllocationNode*)
michael@0:                 PL_HashTableLookup(memory_map, *(void**)d);
michael@0:             if (target) {
michael@0:                 target->pointers_from.AppendElement(node);
michael@0:                 node->pointers_to.AppendElement(target);
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Do a depth-first search on the graph (i.e., by following
michael@0:     // |pointers_to|) and assign the post-order index to |index|.
michael@0:     {
michael@0:         uint32_t dfs_index = 0;
michael@0:         nsTArray<AllocationNode*> stack;
michael@0: 
michael@0:         for (AllocationNode *n = nodes, *n_end = nodes+count; n != n_end; ++n) {
michael@0:             if (n->reached) {
michael@0:                 continue;
michael@0:             }
michael@0:             stack.AppendElement(n);
michael@0: 
michael@0:             do {
michael@0:                 uint32_t pos = stack.Length() - 1;
michael@0:                 AllocationNode *n = stack[pos];
michael@0:                 if (n->reached) {
michael@0:                     n->index = dfs_index++;
michael@0:                     stack.RemoveElementAt(pos);
michael@0:                 } else {
michael@0:                     n->reached = true;
michael@0: 
michael@0:                     // When doing post-order processing, we have to be
michael@0:                     // careful not to put reached nodes into the stack.
michael@0:                     for (int32_t i = n->pointers_to.Length() - 1; i >= 0; --i) {
michael@0:                         AllocationNode* e = n->pointers_to[i];
michael@0:                         if (!e->reached) {
michael@0:                             stack.AppendElement(e);
michael@0:                         }
michael@0:                     }
michael@0:                 }
michael@0:             } while (stack.Length() > 0);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Sort the nodes by their DFS index, in reverse, so that the first
michael@0:     // node is guaranteed to be in a root SCC.
michael@0:     AllocationNode **sorted_nodes = new AllocationNode*[count];
michael@0:     if (!sorted_nodes) {
michael@0:         fprintf(stderr, "%s: Out of memory.\n", argv[0]);
michael@0:         return 1;
michael@0:     }
michael@0: 
michael@0:     {
michael@0:         for (size_t i = 0; i < count; ++i) {
michael@0:             sorted_nodes[i] = nodes + i;
michael@0:         }
michael@0:         NS_QuickSort(sorted_nodes, count, sizeof(AllocationNode*),
michael@0:                      sort_by_reverse_index, 0);
michael@0:     }
michael@0: 
michael@0:     // Put the nodes into their strongly-connected components.
michael@0:     uint32_t num_sccs = 0;
michael@0:     {
michael@0:         for (size_t i = 0; i < count; ++i) {
michael@0:             nodes[i].reached = false;
michael@0:         }
michael@0:         nsTArray<AllocationNode*> stack;
michael@0:         for (AllocationNode **sn = sorted_nodes,
michael@0:                         **sn_end = sorted_nodes + count; sn != sn_end; ++sn) {
michael@0:             if ((*sn)->reached) {
michael@0:                 continue;
michael@0:             }
michael@0: 
michael@0:             // We found a new strongly connected index.
michael@0:             stack.AppendElement(*sn);
michael@0:             do {
michael@0:                 uint32_t pos = stack.Length() - 1;
michael@0:                 AllocationNode *n = stack[pos];
michael@0:                 stack.RemoveElementAt(pos);
michael@0: 
michael@0:                 if (!n->reached) {
michael@0:                     n->reached = true;
michael@0:                     n->index = num_sccs;
michael@0:                     stack.AppendElements(n->pointers_from);
michael@0:                 }
michael@0:             } while (stack.Length() > 0);
michael@0:             ++num_sccs;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Identify which nodes are leak roots by using DFS, and watching
michael@0:     // for component transitions.
michael@0:     uint32_t num_root_nodes = count;
michael@0:     {
michael@0:         for (size_t i = 0; i < count; ++i) {
michael@0:             nodes[i].is_root = true;
michael@0:         }
michael@0: 
michael@0:         nsTArray<AllocationNode*> stack;
michael@0:         for (AllocationNode *n = nodes, *n_end = nodes+count; n != n_end; ++n) {
michael@0:             if (!n->is_root) {
michael@0:                 continue;
michael@0:             }
michael@0: 
michael@0:             // Loop through pointers_to, and add any that are in a
michael@0:             // different SCC to stack:
michael@0:             for (int i = n->pointers_to.Length() - 1; i >= 0; --i) {
michael@0:                 AllocationNode *target = n->pointers_to[i];
michael@0:                 if (n->index != target->index) {
michael@0:                     stack.AppendElement(target);
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             while (stack.Length() > 0) {
michael@0:                 uint32_t pos = stack.Length() - 1;
michael@0:                 AllocationNode *n = stack[pos];
michael@0:                 stack.RemoveElementAt(pos);
michael@0: 
michael@0:                 if (n->is_root) {
michael@0:                     n->is_root = false;
michael@0:                     --num_root_nodes;
michael@0:                     stack.AppendElements(n->pointers_to);
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Sort the nodes by their SCC index.
michael@0:     NS_QuickSort(sorted_nodes, count, sizeof(AllocationNode*),
michael@0:                  sort_by_index, 0);
michael@0: 
michael@0:     // Print output.
michael@0:     {
michael@0:         printf("<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\">\n"
michael@0:                "<html>\n"
michael@0:                "<head>\n"
michael@0:                "<title>Leak analysis</title>\n"
michael@0:                "<style type=\"text/css\">\n"
michael@0:                "  .root { background: white; color: black; }\n"
michael@0:                "  .nonroot { background: #ccc; color: black; }\n"
michael@0:                "</style>\n"
michael@0:                "</head>\n");
michael@0:         printf("<body>\n\n"
michael@0:                "<p>Generated %zd entries (%d in root SCCs) and %d SCCs.</p>\n\n",
michael@0:                count, num_root_nodes, num_sccs);
michael@0: 
michael@0:         for (size_t i = 0; i < count; ++i) {
michael@0:             nodes[i].reached = false;
michael@0:         }
michael@0: 
michael@0:         // Loop over the sorted nodes twice, first printing the roots
michael@0:         // and then the non-roots.
michael@0:         for (int32_t root_type = true;
michael@0:              root_type == true || root_type == false; --root_type) {
michael@0:             if (root_type) {
michael@0:                 printf("\n\n"
michael@0:                        "<div class=\"root\">\n"
michael@0:                        "<h1 id=\"root\">Root components</h1>\n");
michael@0:             } else {
michael@0:                 printf("\n\n"
michael@0:                        "<div class=\"nonroot\">\n"
michael@0:                        "<h1 id=\"nonroot\">Non-root components</h1>\n");
michael@0:             }
michael@0:             uint32_t component = (uint32_t)-1;
michael@0:             bool one_object_component;
michael@0:             for (const AllocationNode *const* sn = sorted_nodes,
michael@0:                                   *const* sn_end = sorted_nodes + count;
michael@0:                  sn != sn_end; ++sn) {
michael@0:                 const AllocationNode *n = *sn;
michael@0:                 if (n->is_root != root_type)
michael@0:                     continue;
michael@0:                 const ADLog::Entry *e = n->entry;
michael@0: 
michael@0:                 if (n->index != component) {
michael@0:                     component = n->index;
michael@0:                     one_object_component =
michael@0:                         sn + 1 == sn_end || (*(sn+1))->index != component;
michael@0:                     if (!one_object_component)
michael@0:                         printf("\n\n<h2 id=\"c%d\">Component %d</h2>\n",
michael@0:                                component, component);
michael@0:                 }
michael@0: 
michael@0:                 if (one_object_component) {
michael@0:                     printf("\n\n<div id=\"c%d\">\n", component);
michael@0:                     printf("<h2 id=\"o%td\">Object %td "
michael@0:                            "(single-object component %d)</h2>\n",
michael@0:                            n-nodes, n-nodes, component);
michael@0:                 } else {
michael@0:                     printf("\n\n<h3 id=\"o%td\">Object %td</h3>\n",
michael@0:                            n-nodes, n-nodes);
michael@0:                 }
michael@0:                 printf("<pre>\n");
michael@0:                 printf("%p &lt;%s&gt; (%zd)\n",
michael@0:                        e->address, e->type, e->datasize);
michael@0:                 for (size_t d = 0; d < e->datasize;
michael@0:                      d += sizeof(ADLog::Pointer)) {
michael@0:                     AllocationNode *target = (AllocationNode*)
michael@0:                         PL_HashTableLookup(memory_map, *(void**)(e->data + d));
michael@0:                     if (target) {
michael@0:                         printf("        <a href=\"#o%td\">",
michael@0:                                target - nodes);
michael@0:                         printf(allocation_format,
michael@0:                                *(size_t*)(e->data + d));
michael@0:                         printf("</a> &lt;%s&gt;",
michael@0:                                target->entry->type);
michael@0:                         if (target->index != n->index) {
michael@0:                             printf(", component %d", target->index);
michael@0:                         }
michael@0:                         printf("\n");
michael@0:                     } else {
michael@0:                         printf("        ");
michael@0:                         printf(allocation_format,
michael@0:                                *(size_t*)(e->data + d));
michael@0:                         printf("\n");
michael@0:                     }
michael@0:                 }
michael@0: 
michael@0:                 if (n->pointers_from.Length()) {
michael@0:                     printf("\nPointers from:\n");
michael@0:                     for (uint32_t i = 0, i_end = n->pointers_from.Length();
michael@0:                          i != i_end; ++i) {
michael@0:                         AllocationNode *t = n->pointers_from[i];
michael@0:                         const ADLog::Entry *te = t->entry;
michael@0:                         printf("    <a href=\"#o%td\">%s</a> (Object %td, ",
michael@0:                                t - nodes, te->type, t - nodes);
michael@0:                         if (t->index != n->index) {
michael@0:                             printf("component %d, ", t->index);
michael@0:                         }
michael@0:                         if (t == n) {
michael@0:                             printf("self)\n");
michael@0:                         } else {
michael@0:                             printf("%p)\n", te->address);
michael@0:                         }
michael@0:                     }
michael@0:                 }
michael@0: 
michael@0:                 print_escaped(stdout, e->allocation_stack);
michael@0: 
michael@0:                 printf("</pre>\n");
michael@0:                 if (one_object_component) {
michael@0:                     printf("</div>\n");
michael@0:                 }
michael@0:             }
michael@0:             printf("</div>\n");
michael@0:         }
michael@0:         printf("</body>\n"
michael@0:                "</html>\n");
michael@0:     }
michael@0: 
michael@0:     delete [] sorted_nodes;
michael@0:     delete [] nodes;
michael@0: 
michael@0:     NS_ShutdownXPCOM(nullptr);
michael@0: 
michael@0:     return 0;
michael@0: }