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

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

mercurial