[bmalloc] Merging of XLargeRanges can leak the upper range

• Component: bmalloc
• Status: RESOLVED FIXED

[Zan Dobersek]

merge in XLargeRange.h first deduces the lower range and then checks if the size of the lower range matches the physical size. If so, the two ranges are merged into one, summing both logical and physical sizes.

But if the logical size of the lower range does not match the physical size, the returned range discards any physical size for the upper range. At least on Linux systems, this results in leaking pages that are described in the upper XLargeRange.

Using memfds and some simple tagging, I was able to get bmalloc to differentiate between small, large and misc allocations (Vector and Cache). This helped properly measure which types of allocations used the largest amount of memory, along with verbosely outlining memory mappings for any process using bmalloc.

The JetStream benchmark was used to analyze the issue. After completing, on the GTK+ port, the WebProcess was using over 500MB there. Investigating the mappings, over 200MB was used for large allocations, even when m_largeAllocated map in the bmalloc::Heap object was reporting only 47MB of large allocations. Further inspection then led to the XLargeRange merging, showing that the upper range can have its physical size information ignored if the lower range is not fully allocated.

[Zan Dobersek]

Created attachment 285013 [details]
Patch

[Geoffrey Garen]

Comment on attachment 285013 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=285013&action=review

> Source/bmalloc/ChangeLog:18
> +        ignored. At least on Linux systems, this resulted in such
> +        memory allocations being leaked.

Can you explain in more detail why we end up with a leak on Linux?

On Mac and Windows, at least, it's OK to call vmAllocatePhysicalPages twice for the same address range.

> Source/bmalloc/bmalloc/XLargeRange.h:70
>  {
> -    if (a.end() == b.begin())
> +    if (a.end() == b.begin() && (a.size() == a.physicalSize() || (!a.physicalSize() && !b.physicalSize())))
>          return true;
>      
> -    if (b.end() == a.begin())
> +    if (b.end() == a.begin() && (b.size() == b.physicalSize() || (!a.physicalSize() && !b.physicalSize())))
>          return true;
>      

This will cause serious virtual memory fragmentation, triggering jetsam on iOS.

[Geoffrey Garen]

I think I understand what you're reporting now:

If we merge(A, B), and B has physicalSize and A doesn't, we produce an XLargeRange with no physicalSize.

In principle, this is OK: physicalSize is just an optimization to remember the contiguous committed space at the head of a range, and the optimization has failed since there is none.

The problem happens later, in Heap::scavengeLargeObjects. We scavenge by calling XLargeMap::removePhysical -- but the [A, B] range has no physicalSize, so we never scavenge it.

I still don't think we want to change the behavior of merge() -- instead, we want to change the behavior of Heap::scavengeLargeObjects.

[Zan Dobersek]

(In reply to comment #2)
> Comment on attachment 285013 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=285013&action=review
> 
> > Source/bmalloc/ChangeLog:18
> > +        ignored. At least on Linux systems, this resulted in such
> > +        memory allocations being leaked.
> 
> Can you explain in more detail why we end up with a leak on Linux?
> 
> On Mac and Windows, at least, it's OK to call vmAllocatePhysicalPages twice
> for the same address range.
> 

It's OK on Linux as well. The problem I'm trying to address here is that right-hand XLargeRanges with some physical size can get ignored during merging if the left-hand ranges have partial physical size or no physical size. So the merged range only has information on any physical allocation that was done for the left-hand range, while the allocated memory from the right-hand range doesn't get deallocated during scavenging, but instead relies on some future allocation to reuse that range.

(In reply to comment #3)
> I think I understand what you're reporting now:
> 
> If we merge(A, B), and B has physicalSize and A doesn't, we produce an
> XLargeRange with no physicalSize.
> 

Also if A has physicalSize that's less that its size, which can be the case if A was previously merged from A1 that had physicalSize matching its size, and A2 that had no physicalSize.

> In principle, this is OK: physicalSize is just an optimization to remember
> the contiguous committed space at the head of a range, and the optimization
> has failed since there is none.
> 
> The problem happens later, in Heap::scavengeLargeObjects. We scavenge by
> calling XLargeMap::removePhysical -- but the [A, B] range has no
> physicalSize, so we never scavenge it.
> 
> I still don't think we want to change the behavior of merge() -- instead, we
> want to change the behavior of Heap::scavengeLargeObjects.

How exactly? Would it be acceptable to delay merging of ranges until after all the large allocations have been scavenged?

[Geoffrey Garen]

> > If we merge(A, B), and B has physicalSize and A doesn't, we produce an
> > XLargeRange with no physicalSize.
> > 
> 
> Also if A has physicalSize that's less that its size, which can be the case
> if A was previously merged from A1 that had physicalSize matching its size,
> and A2 that had no physicalSize.

If we merge(A, B), and B has no physicalSize and A has physicalSize less than its size, we'll do this:

    return XLargeRange(
        left.begin(),
        a.size() + b.size(),
        left.physicalSize());

So, A's physicalSize is not lost.

[Geoffrey Garen]

Created attachment 285252 [details]
Patch

[Michael Saboff]

Comment on attachment 285252 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=285252&action=review

r=me

> Source/bmalloc/ChangeLog:11
> +        Recorded physical size is a performance optimization is not the truth,
> +        so depending on it can cause you to forget physical ranges.

Wording seems awkward.  Should the second "is" be "and"?  The second part of the sentence probably needs some work as well.

> Source/bmalloc/ChangeLog:16
> +        Be careful each time through the loop to decrement our iterator if
> +        the map shrunk while we released the lock.

Seems awkward as well.

[Geoffrey Garen]

Committed r204091: <http://trac.webkit.org/changeset/204091>

[Geoffrey Garen]

> > Source/bmalloc/ChangeLog:11
> > +        Recorded physical size is a performance optimization is not the truth,
> > +        so depending on it can cause you to forget physical ranges.
> 
> Wording seems awkward.  Should the second "is" be "and"?  The second part of
> the sentence probably needs some work as well.

        (bmalloc::Heap::scavengeLargeObjects): Don't use removePhysical().
        Recorded physical size is a performance optimization. It is not the
        truth. So it might be zero even if a range contains physical pages.

> > Source/bmalloc/ChangeLog:16
> > +        Be careful each time through the loop to decrement our iterator if
> > +        the map shrunk while we released the lock.
> 

        The map can shrink when we release the lock, so we must clamp our
        iterator each time through the loop.

[Zan Dobersek]

(In reply to comment #5)
> > > If we merge(A, B), and B has physicalSize and A doesn't, we produce an
> > > XLargeRange with no physicalSize.
> > > 
> > 
> > Also if A has physicalSize that's less that its size, which can be the case
> > if A was previously merged from A1 that had physicalSize matching its size,
> > and A2 that had no physicalSize.
> 
> If we merge(A, B), and B has no physicalSize and A has physicalSize less
> than its size, we'll do this:
> 
>     return XLargeRange(
>         left.begin(),
>         a.size() + b.size(),
>         left.physicalSize());
> 
> So, A's physicalSize is not lost.

Right, I misread your comment. What I was writing about was that if A has some physicalSize that doesn't match its whole size, and B has some physicalSize as well, then B's physicalSize would be lost.

Shouldn't be a problem anymore though, thanks for the quick fix.

[David Kilzer (:ddkilzer)]

<rdar://problem/27696655>