1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tools/trace-malloc/leaksoup.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,416 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +#include "adreader.h"
1.9 +
1.10 +#include <stdio.h>
1.11 +#include "plhash.h"
1.12 +
1.13 +#include "nsTArray.h"
1.14 +#include "nsQuickSort.h"
1.15 +#include "nsXPCOM.h"
1.16 +
1.17 +const uint32_t kPointersDefaultSize = 8;
1.18 +
1.19 +/*
1.20 + * Read in an allocation dump, presumably one taken at shutdown (using
1.21 + * the --shutdown-leaks=file option, which must be used along with
1.22 + * --trace-malloc=tmlog), and treat the memory in the dump as leaks.
1.23 + * Find the leak roots, including cycles that are roots, by finding the
1.24 + * strongly connected components in the graph. Print output to stdout
1.25 + * as HTML.
1.26 + */
1.27 +
1.28 +struct AllocationNode {
1.29 + const ADLog::Entry *entry;
1.30 +
1.31 + // Other |AllocationNode| objects whose memory has a pointer to
1.32 + // this object.
1.33 + nsAutoTArray<AllocationNode*, kPointersDefaultSize> pointers_to;
1.34 +
1.35 + // The reverse.
1.36 + nsAutoTArray<AllocationNode*, kPointersDefaultSize> pointers_from;
1.37 +
1.38 + // Early on in the algorithm, the pre-order index from a DFS.
1.39 + // Later on, set to the index of the strongly connected component to
1.40 + // which this node belongs.
1.41 + uint32_t index;
1.42 +
1.43 + bool reached;
1.44 + bool is_root;
1.45 +};
1.46 +
1.47 +static PLHashNumber hash_pointer(const void *key)
1.48 +{
1.49 + return (PLHashNumber) NS_PTR_TO_INT32(key);
1.50 +}
1.51 +
1.52 +static int sort_by_index(const void* e1, const void* e2, void*)
1.53 +{
1.54 + const AllocationNode *n1 = *static_cast<const AllocationNode*const*>(e1);
1.55 + const AllocationNode *n2 = *static_cast<const AllocationNode*const*>(e2);
1.56 + return n1->index - n2->index;
1.57 +}
1.58 +
1.59 +static int sort_by_reverse_index(const void* e1, const void* e2, void*)
1.60 +{
1.61 + const AllocationNode *n1 = *static_cast<const AllocationNode*const*>(e1);
1.62 + const AllocationNode *n2 = *static_cast<const AllocationNode*const*>(e2);
1.63 + return n2->index - n1->index;
1.64 +}
1.65 +
1.66 +static void print_escaped(FILE *aStream, const char* aData)
1.67 +{
1.68 + char c;
1.69 + char buf[1000];
1.70 + char *p = buf;
1.71 + while ((c = *aData++)) {
1.72 + switch (c) {
1.73 +#define CH(char) *p++ = char
1.74 + case '<':
1.75 + CH('&'); CH('l'); CH('t'); CH(';');
1.76 + break;
1.77 + case '>':
1.78 + CH('&'); CH('g'); CH('t'); CH(';');
1.79 + break;
1.80 + case '&':
1.81 + CH('&'); CH('a'); CH('m'); CH('p'); CH(';');
1.82 + break;
1.83 + default:
1.84 + CH(c);
1.85 + break;
1.86 +#undef CH
1.87 + }
1.88 + if (p + 10 > buf + sizeof(buf)) {
1.89 + *p = '\0';
1.90 + fputs(buf, aStream);
1.91 + p = buf;
1.92 + }
1.93 + }
1.94 + *p = '\0';
1.95 + fputs(buf, aStream);
1.96 +}
1.97 +
1.98 +static const char *allocation_format =
1.99 + (sizeof(ADLog::Pointer) == 4) ? "0x%08zX" :
1.100 + (sizeof(ADLog::Pointer) == 8) ? "0x%016zX" :
1.101 + "UNEXPECTED sizeof(void*)";
1.102 +
1.103 +int main(int argc, char **argv)
1.104 +{
1.105 + if (argc != 2) {
1.106 + fprintf(stderr,
1.107 + "Expected usage: %s <sd-leak-file>\n"
1.108 + " sd-leak-file: Output of --shutdown-leaks=<file> option.\n",
1.109 + argv[0]);
1.110 + return 1;
1.111 + }
1.112 +
1.113 + NS_InitXPCOM2(nullptr, nullptr, nullptr);
1.114 +
1.115 + ADLog log;
1.116 + if (!log.Read(argv[1])) {
1.117 + fprintf(stderr,
1.118 + "%s: Error reading input file %s.\n", argv[0], argv[1]);
1.119 + }
1.120 +
1.121 + const size_t count = log.count();
1.122 +
1.123 + PLHashTable *memory_map =
1.124 + PL_NewHashTable(count * 8, hash_pointer, PL_CompareValues,
1.125 + PL_CompareValues, 0, 0);
1.126 + if (!memory_map) {
1.127 + fprintf(stderr, "%s: Out of memory.\n", argv[0]);
1.128 + return 1;
1.129 + }
1.130 +
1.131 + // Create one |AllocationNode| object for each log entry, and create
1.132 + // entries in the hashtable pointing to it for each byte it occupies.
1.133 + AllocationNode *nodes = new AllocationNode[count];
1.134 + if (!nodes) {
1.135 + fprintf(stderr, "%s: Out of memory.\n", argv[0]);
1.136 + return 1;
1.137 + }
1.138 +
1.139 + {
1.140 + AllocationNode *cur_node = nodes;
1.141 + for (ADLog::const_iterator entry = log.begin(), entry_end = log.end();
1.142 + entry != entry_end; ++entry, ++cur_node) {
1.143 + const ADLog::Entry *e = cur_node->entry = *entry;
1.144 + cur_node->reached = false;
1.145 +
1.146 + for (ADLog::Pointer p = e->address,
1.147 + p_end = e->address + e->datasize;
1.148 + p != p_end; ++p) {
1.149 + PLHashEntry *he = PL_HashTableAdd(memory_map, p, cur_node);
1.150 + if (!he) {
1.151 + fprintf(stderr, "%s: Out of memory.\n", argv[0]);
1.152 + return 1;
1.153 + }
1.154 + }
1.155 + }
1.156 + }
1.157 +
1.158 + // Construct graph based on pointers.
1.159 + for (AllocationNode *node = nodes, *node_end = nodes + count;
1.160 + node != node_end; ++node) {
1.161 + const ADLog::Entry *e = node->entry;
1.162 + for (const char *d = e->data, *d_end = e->data + e->datasize -
1.163 + e->datasize % sizeof(ADLog::Pointer);
1.164 + d != d_end; d += sizeof(ADLog::Pointer)) {
1.165 + AllocationNode *target = (AllocationNode*)
1.166 + PL_HashTableLookup(memory_map, *(void**)d);
1.167 + if (target) {
1.168 + target->pointers_from.AppendElement(node);
1.169 + node->pointers_to.AppendElement(target);
1.170 + }
1.171 + }
1.172 + }
1.173 +
1.174 + // Do a depth-first search on the graph (i.e., by following
1.175 + // |pointers_to|) and assign the post-order index to |index|.
1.176 + {
1.177 + uint32_t dfs_index = 0;
1.178 + nsTArray<AllocationNode*> stack;
1.179 +
1.180 + for (AllocationNode *n = nodes, *n_end = nodes+count; n != n_end; ++n) {
1.181 + if (n->reached) {
1.182 + continue;
1.183 + }
1.184 + stack.AppendElement(n);
1.185 +
1.186 + do {
1.187 + uint32_t pos = stack.Length() - 1;
1.188 + AllocationNode *n = stack[pos];
1.189 + if (n->reached) {
1.190 + n->index = dfs_index++;
1.191 + stack.RemoveElementAt(pos);
1.192 + } else {
1.193 + n->reached = true;
1.194 +
1.195 + // When doing post-order processing, we have to be
1.196 + // careful not to put reached nodes into the stack.
1.197 + for (int32_t i = n->pointers_to.Length() - 1; i >= 0; --i) {
1.198 + AllocationNode* e = n->pointers_to[i];
1.199 + if (!e->reached) {
1.200 + stack.AppendElement(e);
1.201 + }
1.202 + }
1.203 + }
1.204 + } while (stack.Length() > 0);
1.205 + }
1.206 + }
1.207 +
1.208 + // Sort the nodes by their DFS index, in reverse, so that the first
1.209 + // node is guaranteed to be in a root SCC.
1.210 + AllocationNode **sorted_nodes = new AllocationNode*[count];
1.211 + if (!sorted_nodes) {
1.212 + fprintf(stderr, "%s: Out of memory.\n", argv[0]);
1.213 + return 1;
1.214 + }
1.215 +
1.216 + {
1.217 + for (size_t i = 0; i < count; ++i) {
1.218 + sorted_nodes[i] = nodes + i;
1.219 + }
1.220 + NS_QuickSort(sorted_nodes, count, sizeof(AllocationNode*),
1.221 + sort_by_reverse_index, 0);
1.222 + }
1.223 +
1.224 + // Put the nodes into their strongly-connected components.
1.225 + uint32_t num_sccs = 0;
1.226 + {
1.227 + for (size_t i = 0; i < count; ++i) {
1.228 + nodes[i].reached = false;
1.229 + }
1.230 + nsTArray<AllocationNode*> stack;
1.231 + for (AllocationNode **sn = sorted_nodes,
1.232 + **sn_end = sorted_nodes + count; sn != sn_end; ++sn) {
1.233 + if ((*sn)->reached) {
1.234 + continue;
1.235 + }
1.236 +
1.237 + // We found a new strongly connected index.
1.238 + stack.AppendElement(*sn);
1.239 + do {
1.240 + uint32_t pos = stack.Length() - 1;
1.241 + AllocationNode *n = stack[pos];
1.242 + stack.RemoveElementAt(pos);
1.243 +
1.244 + if (!n->reached) {
1.245 + n->reached = true;
1.246 + n->index = num_sccs;
1.247 + stack.AppendElements(n->pointers_from);
1.248 + }
1.249 + } while (stack.Length() > 0);
1.250 + ++num_sccs;
1.251 + }
1.252 + }
1.253 +
1.254 + // Identify which nodes are leak roots by using DFS, and watching
1.255 + // for component transitions.
1.256 + uint32_t num_root_nodes = count;
1.257 + {
1.258 + for (size_t i = 0; i < count; ++i) {
1.259 + nodes[i].is_root = true;
1.260 + }
1.261 +
1.262 + nsTArray<AllocationNode*> stack;
1.263 + for (AllocationNode *n = nodes, *n_end = nodes+count; n != n_end; ++n) {
1.264 + if (!n->is_root) {
1.265 + continue;
1.266 + }
1.267 +
1.268 + // Loop through pointers_to, and add any that are in a
1.269 + // different SCC to stack:
1.270 + for (int i = n->pointers_to.Length() - 1; i >= 0; --i) {
1.271 + AllocationNode *target = n->pointers_to[i];
1.272 + if (n->index != target->index) {
1.273 + stack.AppendElement(target);
1.274 + }
1.275 + }
1.276 +
1.277 + while (stack.Length() > 0) {
1.278 + uint32_t pos = stack.Length() - 1;
1.279 + AllocationNode *n = stack[pos];
1.280 + stack.RemoveElementAt(pos);
1.281 +
1.282 + if (n->is_root) {
1.283 + n->is_root = false;
1.284 + --num_root_nodes;
1.285 + stack.AppendElements(n->pointers_to);
1.286 + }
1.287 + }
1.288 + }
1.289 + }
1.290 +
1.291 + // Sort the nodes by their SCC index.
1.292 + NS_QuickSort(sorted_nodes, count, sizeof(AllocationNode*),
1.293 + sort_by_index, 0);
1.294 +
1.295 + // Print output.
1.296 + {
1.297 + printf("<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\">\n"
1.298 + "<html>\n"
1.299 + "<head>\n"
1.300 + "<title>Leak analysis</title>\n"
1.301 + "<style type=\"text/css\">\n"
1.302 + " .root { background: white; color: black; }\n"
1.303 + " .nonroot { background: #ccc; color: black; }\n"
1.304 + "</style>\n"
1.305 + "</head>\n");
1.306 + printf("<body>\n\n"
1.307 + "<p>Generated %zd entries (%d in root SCCs) and %d SCCs.</p>\n\n",
1.308 + count, num_root_nodes, num_sccs);
1.309 +
1.310 + for (size_t i = 0; i < count; ++i) {
1.311 + nodes[i].reached = false;
1.312 + }
1.313 +
1.314 + // Loop over the sorted nodes twice, first printing the roots
1.315 + // and then the non-roots.
1.316 + for (int32_t root_type = true;
1.317 + root_type == true || root_type == false; --root_type) {
1.318 + if (root_type) {
1.319 + printf("\n\n"
1.320 + "<div class=\"root\">\n"
1.321 + "<h1 id=\"root\">Root components</h1>\n");
1.322 + } else {
1.323 + printf("\n\n"
1.324 + "<div class=\"nonroot\">\n"
1.325 + "<h1 id=\"nonroot\">Non-root components</h1>\n");
1.326 + }
1.327 + uint32_t component = (uint32_t)-1;
1.328 + bool one_object_component;
1.329 + for (const AllocationNode *const* sn = sorted_nodes,
1.330 + *const* sn_end = sorted_nodes + count;
1.331 + sn != sn_end; ++sn) {
1.332 + const AllocationNode *n = *sn;
1.333 + if (n->is_root != root_type)
1.334 + continue;
1.335 + const ADLog::Entry *e = n->entry;
1.336 +
1.337 + if (n->index != component) {
1.338 + component = n->index;
1.339 + one_object_component =
1.340 + sn + 1 == sn_end || (*(sn+1))->index != component;
1.341 + if (!one_object_component)
1.342 + printf("\n\n<h2 id=\"c%d\">Component %d</h2>\n",
1.343 + component, component);
1.344 + }
1.345 +
1.346 + if (one_object_component) {
1.347 + printf("\n\n<div id=\"c%d\">\n", component);
1.348 + printf("<h2 id=\"o%td\">Object %td "
1.349 + "(single-object component %d)</h2>\n",
1.350 + n-nodes, n-nodes, component);
1.351 + } else {
1.352 + printf("\n\n<h3 id=\"o%td\">Object %td</h3>\n",
1.353 + n-nodes, n-nodes);
1.354 + }
1.355 + printf("<pre>\n");
1.356 + printf("%p <%s> (%zd)\n",
1.357 + e->address, e->type, e->datasize);
1.358 + for (size_t d = 0; d < e->datasize;
1.359 + d += sizeof(ADLog::Pointer)) {
1.360 + AllocationNode *target = (AllocationNode*)
1.361 + PL_HashTableLookup(memory_map, *(void**)(e->data + d));
1.362 + if (target) {
1.363 + printf(" <a href=\"#o%td\">",
1.364 + target - nodes);
1.365 + printf(allocation_format,
1.366 + *(size_t*)(e->data + d));
1.367 + printf("</a> <%s>",
1.368 + target->entry->type);
1.369 + if (target->index != n->index) {
1.370 + printf(", component %d", target->index);
1.371 + }
1.372 + printf("\n");
1.373 + } else {
1.374 + printf(" ");
1.375 + printf(allocation_format,
1.376 + *(size_t*)(e->data + d));
1.377 + printf("\n");
1.378 + }
1.379 + }
1.380 +
1.381 + if (n->pointers_from.Length()) {
1.382 + printf("\nPointers from:\n");
1.383 + for (uint32_t i = 0, i_end = n->pointers_from.Length();
1.384 + i != i_end; ++i) {
1.385 + AllocationNode *t = n->pointers_from[i];
1.386 + const ADLog::Entry *te = t->entry;
1.387 + printf(" <a href=\"#o%td\">%s</a> (Object %td, ",
1.388 + t - nodes, te->type, t - nodes);
1.389 + if (t->index != n->index) {
1.390 + printf("component %d, ", t->index);
1.391 + }
1.392 + if (t == n) {
1.393 + printf("self)\n");
1.394 + } else {
1.395 + printf("%p)\n", te->address);
1.396 + }
1.397 + }
1.398 + }
1.399 +
1.400 + print_escaped(stdout, e->allocation_stack);
1.401 +
1.402 + printf("</pre>\n");
1.403 + if (one_object_component) {
1.404 + printf("</div>\n");
1.405 + }
1.406 + }
1.407 + printf("</div>\n");
1.408 + }
1.409 + printf("</body>\n"
1.410 + "</html>\n");
1.411 + }
1.412 +
1.413 + delete [] sorted_nodes;
1.414 + delete [] nodes;
1.415 +
1.416 + NS_ShutdownXPCOM(nullptr);
1.417 +
1.418 + return 0;
1.419 +}
