The Tor Browser / file comparison
comparison: tools/trace-malloc/leaksoup.cpp
tools/trace-malloc/leaksoup.cpp
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
equal
deleted
inserted
replaced
| -1:000000000000 | 0:2e3588a8cc31 |
|---|---|
| 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/. */ | |
| 4 | |
| 5 #include "adreader.h" | |
| 6 | |
| 7 #include <stdio.h> | |
| 8 #include "plhash.h" | |
| 9 | |
| 10 #include "nsTArray.h" | |
| 11 #include "nsQuickSort.h" | |
| 12 #include "nsXPCOM.h" | |
| 13 | |
| 14 const uint32_t kPointersDefaultSize = 8; | |
| 15 | |
| 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 */ | |
| 24 | |
| 25 struct AllocationNode { | |
| 26 const ADLog::Entry *entry; | |
| 27 | |
| 28 // Other |AllocationNode| objects whose memory has a pointer to | |
| 29 // this object. | |
| 30 nsAutoTArray<AllocationNode*, kPointersDefaultSize> pointers_to; | |
| 31 | |
| 32 // The reverse. | |
| 33 nsAutoTArray<AllocationNode*, kPointersDefaultSize> pointers_from; | |
| 34 | |
| 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; | |
| 39 | |
| 40 bool reached; | |
| 41 bool is_root; | |
| 42 }; | |
| 43 | |
| 44 static PLHashNumber hash_pointer(const void *key) | |
| 45 { | |
| 46 return (PLHashNumber) NS_PTR_TO_INT32(key); | |
| 47 } | |
| 48 | |
| 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 } | |
| 55 | |
| 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 } | |
| 62 | |
| 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 } | |
| 94 | |
| 95 static const char *allocation_format = | |
| 96 (sizeof(ADLog::Pointer) == 4) ? "0x%08zX" : | |
| 97 (sizeof(ADLog::Pointer) == 8) ? "0x%016zX" : | |
| 98 "UNEXPECTED sizeof(void*)"; | |
| 99 | |
| 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 } | |
| 109 | |
| 110 NS_InitXPCOM2(nullptr, nullptr, nullptr); | |
| 111 | |
| 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 } | |
| 117 | |
| 118 const size_t count = log.count(); | |
| 119 | |
| 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 } | |
| 127 | |
| 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 } | |
| 135 | |
| 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; | |
| 142 | |
| 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 } | |
| 154 | |
| 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 } | |
| 170 | |
| 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; | |
| 176 | |
| 177 for (AllocationNode *n = nodes, *n_end = nodes+count; n != n_end; ++n) { | |
| 178 if (n->reached) { | |
| 179 continue; | |
| 180 } | |
| 181 stack.AppendElement(n); | |
| 182 | |
| 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; | |
| 191 | |
| 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 } | |
| 204 | |
| 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 } | |
| 212 | |
| 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 } | |
| 220 | |
| 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 } | |
| 233 | |
| 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); | |
| 240 | |
| 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 } | |
| 250 | |
| 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 } | |
| 258 | |
| 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 } | |
| 264 | |
| 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 } | |
| 273 | |
| 274 while (stack.Length() > 0) { | |
| 275 uint32_t pos = stack.Length() - 1; | |
| 276 AllocationNode *n = stack[pos]; | |
| 277 stack.RemoveElementAt(pos); | |
| 278 | |
| 279 if (n->is_root) { | |
| 280 n->is_root = false; | |
| 281 --num_root_nodes; | |
| 282 stack.AppendElements(n->pointers_to); | |
| 283 } | |
| 284 } | |
| 285 } | |
| 286 } | |
| 287 | |
| 288 // Sort the nodes by their SCC index. | |
| 289 NS_QuickSort(sorted_nodes, count, sizeof(AllocationNode*), | |
| 290 sort_by_index, 0); | |
| 291 | |
| 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); | |
| 306 | |
| 307 for (size_t i = 0; i < count; ++i) { | |
| 308 nodes[i].reached = false; | |
| 309 } | |
| 310 | |
| 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; | |
| 333 | |
| 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 } | |
| 342 | |
| 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 } | |
| 377 | |
| 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 } | |
| 396 | |
| 397 print_escaped(stdout, e->allocation_stack); | |
| 398 | |
| 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 } | |
| 409 | |
| 410 delete [] sorted_nodes; | |
| 411 delete [] nodes; | |
| 412 | |
| 413 NS_ShutdownXPCOM(nullptr); | |
| 414 | |
| 415 return 0; | |
| 416 } |
