179212 - trace-malloc memory dump reader for analyzing leak graph

Status: RESOLVED FIXED

(Core :: XPCOM, defect, P2)

Description

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I've written yet another version of leaksoup.  The original version
(mozilla/gc/boehm/leaksoup/), by Patrick Beard, is in Java, and reads
Boehm GC output.  The second version
(mozilla/tools/trace-malloc/leak-soup.pl), by Chris Waterson and Jim
Roskind, is in perl, and reads trace-malloc allocation dumps.

This version also reads trace-malloc allocation dumps.  However, it has
two main advantages:
 * It's in C++, so it's a lot faster than perl.  In fact, it generates
   the HTML output much faster than Mozilla can display it.  I probably
   overoptimized (mainly by avoiding callbacks), but it's not that
   bad.
 * It finds the strongly connected clusters in the graph using a
   linear-time algorithm that I learned in my algorithms class, and thus
   finds root cycles in addition to lone roots.  In other words, if a
   leak is rooted by a circular ownership pattern, it can differentiate
   the participants in the circular ownership pattern from the rest of
   the garbage they entrain.

The output still needs a good bit of work.  For each root cluster, it
should probably list the number of bytes entrained by that cluster
(although it's worth noting that some of those bytes may also be
entrained by other roots).  It would probably be good to sort in that
order too.  There are probably other modifications to the output that
would make it easier to read.  It also might be worth adding an option
that causes the output to be omitted for non-roots, since that makes the
HTML output even bigger.  etc.

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch v. 1

Comment 2

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch v. 2

This properly escapes <, >, and & in the stacks.  I think it makes loading the
output a bit easier on Mozilla.

Comment 3

[Brendan Eich [:brendan]]

Comment on attachment 105684 [details] [diff] [review]
patch v. 2

>+    struct EntryBlockLink {
>+        EntryBlock *mPrev;
>+        EntryBlock *mNext;
>+    };

BTW, not that I'm recommending it, just wondering: did you consider using
prclist.h type and macros instead?

>+        char *data = (char*)malloc(((datasize-1)/4 + 1)*4);

I prefer (((datasize + 3) / 4) * 4), which is PR_ROUNDUP(datasize, 4).

>+
>+        for (char *cur_data = data; cur_data - data < datasize;
>+             cur_data = cur_data + 4) {

Why not:

	       cur_data += 4) {

instead?

>+        char *stack = stackbuf;
>+        int len = 0;

Useless len init.

>+        do {
>+            fgets(stack, sizeof(stackbuf) - (stack - stackbuf), in);
>+            len = strlen(stack);
>+            stack += len;
>+        } while (len > 1);

 . . .

>+ADLog::const_iterator::const_iterator(ADLog::EntryBlock *aBlock,
>+                                      size_t aOffset)
>+{
>+    SetBlock(aBlock);
>+    mCur = mBlockStart + aOffset;

What if aOffset >= ADLOG_ENTRY_BLOCK_SIZE?

>+}
>+
>+ADLog::const_iterator&
>+ADLog::const_iterator::operator++()
>+{
>+    ++mCur;
>+    if (mCur == mBlockEnd) {

Loop while >= mBlockEnd, advancing till aOffset that overflowed the first entry
block has been reduced to fit in mCur?

>+        SetBlock(mBlock->mNext);
>+        mCur = mBlockStart;
>+    }
>+
>+    return *this;
>+}
>+
>+ADLog::const_iterator&
>+ADLog::const_iterator::operator--()
>+{
>+    if (mCur == mBlockStart) {
>+        SetBlock(mBlock->mNext);

mPrev, surely?

>+        mCur = mBlockEnd;
>+    }
>+    --mCur;
>+
>+    return *this;
>+}

More in a bit, I hope this helps.

/be

Comment 4

[Brendan Eich [:brendan]]

Comment on attachment 105684 [details] [diff] [review]
patch v. 2

>+
>+struct AllocationNode {
>+    const ADLog::Entry *entry;

Hrm, don't you want to use pldhash.h, not plhash.h, and derive an entry struct
from PLDHashEntryHdr that adds just an AllocateNode *node; member?  Then you
can hash and key-compare ((AllocationNode*)hdr)->node->entry->address, and
avoid lots of tiny mallocs for the PLHashEntry structs incurred with plhash.h. 
You're in the k=3 case for the tradeoff relation formula from
http://lxr.mozilla.org/mozilla/source/js/src/jsdhash.h#149, which is a good
case for using double hashing.

>+static void print_escaped(FILE *aStream, const char* aData)
>+{
>+    char c;
>+    char buf[1000];
>+    char *p = buf;
>+    while ((c = *aData++)) {
>+        switch (c) {
>+            case '<':
>+                *p++ = '&';
>+                *p++ = 'l';
>+                *p++ = 't';
>+                *p++ = ';';
>+                break;
>+            case '>':
>+                *p++ = '&';
>+                *p++ = 'g';
>+                *p++ = 't';
>+                *p++ = ';';
>+                break;
>+            case '&':
>+                *p++ = '&';
>+                *p++ = 'a';
>+                *p++ = 'm';
>+                *p++ = 'p';
>+                *p++ = ';';
>+                break;
>+            default:
>+                *p++ = c;
>+                break;
>+        }
>+        if (p - 10 > buf + sizeof(buf)) {

p + 10, surely?

>+            *p = '\0';
>+            fputs(buf, aStream);
>+            p = buf;
>+        }
>+    }
>+    *p = '\0';
>+    fputs(buf, aStream);
>+}
>+        for (ADLog::const_iterator entry = log.begin(), entry_end = log.end();
>+                entry != entry_end; ++entry, ++cur_node) {

Recurrent nit, picked once only here: make the overflow lines of the for loop
header indent to underhang the initialization part?

Yet more in a bit.

When did the third letter in SCC change to stand for "Cluster"?  In my day
(when we walked uphill both ways through snow to school), it was "Component". 
Just curious about your algorithms class's text.  I prefer "Cluster".

/be

Comment 5

[Brendan Eich [:brendan]]

I meant, of course, a different type than AllocationNode, in

>can hash and key-compare ((AllocationNode*)hdr)->node->entry->address, and

the type in the cast would be AllocationNodeEntry or some such, derived from
PLDHashEntryHdr, adding the AllocationNode *node; member.  And with modern cast
sugar, of course!

/be

Comment 6

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch v. 3

This addresses most of brendan's comments (comments on the comments in a bit),
and also prevents printing "Component" headers for single-object components.

Comment 7

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I landed what I had, with brendan's comments incorporated, this morning, so that
this won't risk getting lost as I let it rot.

Comment 8

[Aleksey Nogin]

This checkin have added a warning on brad TBox:

+tools/trace-malloc/leaksoup.cpp:352
+ `PRBool one_object_component' might be used uninitialized in this function

It appears to be a real issue - if (n->index == component), the code will end up
doing "if (one_object_component)" before the one_object_component is ever
initialized! See
http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/tools/trace-malloc/leaksoup.cpp&rev=1.2&mark=352,361,370#351

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

The warning is erroneous.  The variable persists across iterations of the loop
and is guaranteed to be initialized the first iteration.

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Fixed long ago, and documented at
http://mozilla.org/performance/leak-brownbag.html#leaksoup