RFR(L): 8198423: Improve metaspace chunk allocation (was: Proposal for improvements to the metaspace chunk allocator)

Thomas Stüfe thomas.stuefe at gmail.com
Tue Mar 6 06:10:37 UTC 2018 

 Hi Coleen,

We test nightly in windows 32bit. I'll go and run some tests on 32bit linux
too.

Thanks for the sponsoring offer! Goetz already reviewed this patch, would
that be sufficient or should I look for another reviewer from Oracle?

Kind Regards, Thomas


On Tue, Mar 6, 2018 at 12:59 AM, <coleen.phillimore at oracle.com> wrote:

>
> Hi Thomas,
>
> I've read through the new code.  I don't have any substantive comments.
> Thank you for adding the functions.
>
> Has this been tested on any 32 bit platforms?   I will sponsor this when
> you have another reviewer.
>
> Thanks for taking on the metaspace!
>
> Coleen
>
>
> On 3/1/18 5:36 AM, Thomas Stüfe wrote:
>
> Hi Coleen,
>
> thanks a lot for the review and the sponsoring offer!
>
> New version (full): http://cr.openjdk.java.net/~stuefe/webrevs/
> metaspace-coalescation/2018-03-01/webrev-full/webrev/
> incremental: http://cr.openjdk.java.net/~stuefe/webrevs/metaspace-
> coalescation/2018-03-01/webrev-incr/webrev/
>
> Please find remarks inline:
>
>
> On Tue, Feb 27, 2018 at 11:22 PM, <coleen.phillimore at oracle.com> wrote:
>
>>
>> Thomas, review comments:
>>
>> http://cr.openjdk.java.net/~stuefe/webrevs/metaspace-coalesc
>> ation/2018-02-26/webrev/src/hotspot/share/memory/metachunk.hpp.udiff.html
>>
>> +// ChunkIndex (todo: rename?) defines the type of chunk. Chunk types
>>
>>
>> It's really both, isn't it?  The type is the index into the free list or
>> in use lists.  The name seems fine.
>>
>>
> You are right. What I meant was that a lot of code needs to know about the
> different chunk sizes, but naming it "Index" and adding enum values like
> "NumberOfFreeLists" we expose implementation details no-one outside of
> SpaceManager and ChunkManager cares about (namely, the fact that these
> values are internally used as indices into arrays). A more neutral naming
> would be something like "enum ChunkTypes { spec,small, .... ,
> NumberOfNonHumongousChunkTypes, NumberOfChunkTypes }.
>
> However, I can leave this out for a possible future cleanup. The change is
> big enough as it is.
>
>
>> Can you add comments on the #endifs if the #ifdef is more than a couple
>> 2-3 lines above (it's a nit that bothers me).
>>
>> +#ifdef ASSERT
>> + // A 32bit sentinel for debugging purposes.
>> +#define CHUNK_SENTINEL 0x4d4554EF // "MET"
>> +#define CHUNK_SENTINEL_INVALID 0xFEEEEEEF
>> + uint32_t _sentinel;
>> +#endif
>> + const ChunkIndex _chunk_type;
>> + const bool _is_class;
>> + // Whether the chunk is free (in freelist) or in use by some class
>> loader.
>>    bool _is_tagged_free;
>>  +#ifdef ASSERT
>> + ChunkOrigin _origin;
>> + int _use_count;
>> +#endif
>> +
>>
>>
> I removed the asserts completely, following your suggestion below that
> "origin" would be valuable in customer scenarios too. By that logic, the
> other members are valuable too: the sentinel is valuable when examining
> memory dumps to see the start of chunks, and the in-use counter is useful
> too. What do you think?
>
> So, I leave the members in - which, depending what the C++ compiler does
> to enums and bools, may cost up to 128bit additional header space. I think
> that is ok. In one of my earlier versions of this patch I hand-crafted the
> header using chars and bitfields to be as small as possible, but that
> seemed over-engineered.
>
> However, I left out any automatic verifications accessing these debug
> members. These are still only done in debug builds.
>
>
>>
>> It seems that if you could move origin and _use_count into the ASSERT
>> block above (maybe putting use_count before _origin.
>>
>> http://cr.openjdk.java.net/~stuefe/webrevs/metaspace-coalesc
>> ation/2018-02-26/webrev/src/hotspot/share/memory/metaspace.cpp.udiff.html
>>
>> In take_from_committed, can the allocation of padding chunks be its own
>> function like add_chunks_to_aligment() lines 1574-1615? The function is too
>> long now.
>>
>>
> I moved the padding chunk allocation into an own function as you suggested.
>
>
>> I don't think coalescation is a word in English, at least my dictionary
>> cannot find it.  Although it makes sense in the context, just distracting.
>>
>>
> I replaced "coalescation" with "chunk merging" throughout the code. Also
> less of a tongue breaker.
>
>
>> + // Now check if in the coalescation area there are still life chunks.
>>
>>
>> "live" chunks I guess.   A sentence you won't read often :).
>>
>
> Now that I read it it almost sounded sinister :) Fixed.
>
>
>>
>> In free_chunks_get() can you handle the Humongous case first? The else
>> for humongous chunk size is buried tons of lines below.
>>
>> Otherwise it might be helpful to the logic to make your addition to this
>> function be a function you call like
>>   chunk = split_from_larger_free_chunk();
>>
>
> I did the latter. I moved the splitting of a larger chunk to an own
> function. This causes a slight logic change: the new function
> (ChunkManager::split_chunk()) splits an existing large free chunks into n
> smaller free chunks and adds them all back to the freelist - that includes
> the chunk we are about to return. That allows us to use the same exit path
> - which removes the chunk from the freelist and adjusts all counters - in
> the caller function "ChunkManager::free_chunks_get" instead of having to
> return in the middle of the function.
>
> To make the test more readable, I also remove the
> "test-that-free-chunks-are-optimally-merged" verification - which was
> quite lengthy - from VirtualSpaceNode::verify() to a new function,
> VirtualSpaceNode::verify_free_chunks_are_ideally_merged().
>
>
>> You might want to keep the origin in product mode if it doesn't add to
>> the chunk footprint.   Might help with customer debugging.
>>
>>
> See above
>
>
>> Awesome looking test...
>>
>>
> Thanks, I was worried it would be too complicated.
> I changed it a bit because there were sporadic errors. Not a "real" error,
> just the test itself was faulty. The "metaspaces_in_use" counter was
> slightly wrong in one corner case.
>
>
>> I've read through most of this and thank you for adding this to at least
>> partially solve the fragmentation problem.  The irony is that we
>> templatized the Dictionary from CMS so that we could use it for Metaspace
>> and that has splitting and coalescing but it seems this code makes more
>> sense than adapting that code (if it's even possible).
>>
>
> Well, it helps other metadata use cases too, no.
>
>
>>
>> Thank you for working on this.  I'll sponsor this for you.
>>
> Coleen
>>
>>
>
> Thanks again!
>
> I also updated my jdk-submit branch to include these latest changes; tests
> are still runnning.
>
> Kind Regards, Thomas
>
>
>
>>
>> On 2/26/18 9:20 AM, Thomas Stüfe wrote:
>>
>>> Hi all,
>>>
>>> I know this patch is a bit larger, but may I please have reviews and/or
>>> other input?
>>>
>>> Issue: https://bugs.openjdk.java.net/browse/JDK-8198423
>>> Latest version:
>>> http://cr.openjdk.java.net/~stuefe/webrevs/metaspace-coalesc
>>> ation/2018-02-26/webrev/
>>>
>>> For those who followed the mail thread, this is the incremental diff to
>>> the
>>> last changes (included feedback Goetz gave me on- and off-list):
>>> http://cr.openjdk.java.net/~stuefe/webrevs/metaspace-coalesc
>>> ation/2018-02-26/webrev-incr/webrev/
>>>
>>> Thank you!
>>>
>>> Kind Regards, Thomas Stuefe
>>>
>>>
>>>
>>> On Thu, Feb 8, 2018 at 12:58 PM, Thomas Stüfe <thomas.stuefe at gmail.com>
>>> wrote:
>>>
>>> Hi,
>>>>
>>>> We would like to contribute a patch developed at SAP which has been live
>>>> in our VM for some time. It improves the metaspace chunk allocation:
>>>> reduces fragmentation and raises the chance of reusing free metaspace
>>>> chunks.
>>>>
>>>> The patch: http://cr.openjdk.java.net/~stuefe/webrevs/metaspace-coalesc
>>>> ation/2018-02-05--2/webrev/
>>>>
>>>> In very short, this patch helps with a number of pathological cases
>>>> where
>>>> metaspace chunks are free but cannot be reused because they are of the
>>>> wrong size. For example, the metaspace freelist could be full of small
>>>> chunks, which would not be reusable if we need larger chunks. So, we
>>>> could
>>>> get metaspace OOMs even in situations where the metaspace was far from
>>>> exhausted. Our patch adds the ability to split and merge metaspace
>>>> chunks
>>>> dynamically and thus remove the "size-lock-in" problem.
>>>>
>>>> Note that there have been other attempts to get a grip on this problem,
>>>> see e.g. "SpaceManager::get_small_chunks_and_allocate()". But arguably
>>>> our patch attempts a more complete solution.
>>>>
>>>> In 2016 I discussed the idea for this patch with some folks off-list,
>>>> among them Jon Matsimutso. He then did advice me to create a JEP. So I
>>>> did:
>>>> [1]. However, meanwhile changes to the JEP process were discussed [2],
>>>> and
>>>> I am not sure anymore this patch needs even needs a JEP. It may be
>>>> moderately complex and hence carries the risk inherent in any patch, but
>>>> its effects would not be externally visible (if you discount seeing
>>>> fewer
>>>> metaspace OOMs). So, I'd prefer to handle this as a simple RFE.
>>>>
>>>> --
>>>>
>>>> How this patch works:
>>>>
>>>> 1) When a class loader dies, its metaspace chunks are freed and returned
>>>> to the freelist for reuse by the next class loader. With the patch, upon
>>>> returning a chunk to the freelist, an attempt is made to merge it with
>>>> its
>>>> neighboring chunks - should they happen to be free too - to form a
>>>> larger
>>>> chunk. Which then is placed in the free list.
>>>>
>>>> As a result, the freelist should be populated by larger chunks at the
>>>> expense of smaller chunks. In other words, all free chunks should
>>>> always be
>>>> as "coalesced as possible".
>>>>
>>>> 2) When a class loader needs a new chunk and a chunk of the requested
>>>> size
>>>> cannot be found in the free list, before carving out a new chunk from
>>>> the
>>>> virtual space, we first check if there is a larger chunk in the free
>>>> list.
>>>> If there is, that larger chunk is chopped up into n smaller chunks. One
>>>> of
>>>> them is returned to the callers, the others are re-added to the
>>>> freelist.
>>>>
>>>> (1) and (2) together have the effect of removing the size-lock-in for
>>>> chunks. If fragmentation allows it, small chunks are dynamically
>>>> combined
>>>> to form larger chunks, and larger chunks are split on demand.
>>>>
>>>> --
>>>>
>>>> What this patch does not:
>>>>
>>>> This is not a rewrite of the chunk allocator - most of the mechanisms
>>>> stay
>>>> intact. Specifically, chunk sizes remain unchanged, and so do chunk
>>>> allocation processes (when do which class loaders get handed which chunk
>>>> size). Almost everthing this patch does affects only internal workings
>>>> of
>>>> the ChunkManager.
>>>>
>>>> Also note that I refrained from doing any cleanups, since I wanted
>>>> reviewers to be able to gauge this patch without filtering noise.
>>>> Unfortunately this patch adds some complexity. But there are many future
>>>> opportunities for code cleanup and simplification, some of which we
>>>> already
>>>> discussed in existing RFEs ([3], [4]). All of them are out of the scope
>>>> for
>>>> this particular patch.
>>>>
>>>> --
>>>>
>>>> Details:
>>>>
>>>> Before the patch, the following rules held:
>>>> - All chunk sizes are multiples of the smallest chunk size ("specialized
>>>> chunks")
>>>> - All chunk sizes of larger chunks are also clean multiples of the next
>>>> smaller chunk size (e.g. for class space, the ratio of
>>>> specialized/small/medium chunks is 1:2:32)
>>>> - All chunk start addresses are aligned to the smallest chunk size (more
>>>> or less accidentally, see metaspace_reserve_alignment).
>>>> The patch makes the last rule explicit and more strict:
>>>> - All (non-humongous) chunk start addresses are now aligned to their own
>>>> chunk size. So, e.g. medium chunks are allocated at addresses which are
>>>> a
>>>> multiple of medium chunk size. This rule is not extended to humongous
>>>> chunks, whose start addresses continue to be aligned to the smallest
>>>> chunk
>>>> size.
>>>>
>>>> The reason for this new alignment rule is that it makes it cheap both to
>>>> find chunk predecessors of a chunk and to check which chunks are free.
>>>>
>>>> When a class loader dies and its chunk is returned to the freelist, all
>>>> we
>>>> have is its address. In order to merge it with its neighbors to form a
>>>> larger chunk, we need to find those neighbors, including those preceding
>>>> the returned chunk. Prior to this patch that was not easy - one would
>>>> have
>>>> to iterate chunks starting at the beginning of the VirtualSpaceNode. But
>>>> due to the new alignment rule, we now know where the prospective larger
>>>> chunk must start - at the next lower larger-chunk-size-aligned
>>>> boundary. We
>>>> also know that currently a smaller chunk must start there (*).
>>>>
>>>> In order to check the free-ness of chunks quickly, each VirtualSpaceNode
>>>> now keeps a bitmap which describes its occupancy. One bit in this bitmap
>>>> corresponds to a range the size of the smallest chunk size and starting
>>>> at
>>>> an address aligned to the smallest chunk size. Because of the alignment
>>>> rules above, such a range belongs to one single chunk. The bit is 1 if
>>>> the
>>>> associated chunk is in use by a class loader, 0 if it is free.
>>>>
>>>> When we have calculated the address range a prospective larger chunk
>>>> would
>>>> span, we now need to check if all chunks in that range are free. Only
>>>> then
>>>> we can merge them. We do that by querying the bitmap. Note that the most
>>>> common use case here is forming medium chunks from smaller chunks. With
>>>> the
>>>> new alignment rules, the bitmap portion covering a medium chunk now
>>>> always
>>>> happens to be 16- or 32bit in size and is 16- or 32bit aligned, so
>>>> reading
>>>> the bitmap in many cases becomes a simple 16- or 32bit load.
>>>>
>>>> If the range is free, only then we need to iterate the chunks in that
>>>> range: pull them from the freelist, combine them to one new larger
>>>> chunk,
>>>> re-add that one to the freelist.
>>>>
>>>> (*) Humongous chunks make this a bit more complicated. Since the new
>>>> alignment rule does not extend to them, a humongous chunk could still
>>>> straddle the lower or upper boundary of the prospective larger chunk.
>>>> So I
>>>> gave the occupancy map a second layer, which is used to mark the start
>>>> of
>>>> chunks.
>>>> An alternative approach could have been to make humongous chunks size
>>>> and
>>>> start address always a multiple of the largest non-humongous chunk size
>>>> (medium chunks). That would have caused a bit of waste per humongous
>>>> chunk
>>>> (<64K) in exchange for simpler coding and a simpler occupancy map.
>>>>
>>>> --
>>>>
>>>> The patch shows its best results in scenarios where a lot of smallish
>>>> class loaders are alive simultaneously. When dying, they leave
>>>> continuous
>>>> expanses of metaspace covered in small chunks, which can be merged
>>>> nicely.
>>>> However, if class loader life times vary more, we have more
>>>> interleaving of
>>>> dead and alive small chunks, and hence chunk merging does not work as
>>>> well
>>>> as it could.
>>>>
>>>> For an example of a pathological case like this see example program: [5]
>>>>
>>>> Executed like this: "java -XX:CompressedClassSpaceSize=10M -cp test3
>>>> test3.Example2" the test will load 3000 small classes in separate class
>>>> loaders, then throw them away and start loading large classes. The small
>>>> classes will have flooded the metaspace with small chunks, which are
>>>> unusable for the large classes. When executing with the rather limited
>>>> CompressedClassSpaceSize=10M, we will run into an OOM after loading
>>>> about
>>>> 800 large classes, having used only 40% of the class space, the rest is
>>>> wasted to unused small chunks. However, with our patch the example
>>>> program
>>>> will manage to allocate ~2900 large classes before running into an OOM,
>>>> and
>>>> class space will show almost no waste.
>>>>
>>>> Do demonstrate this, add -Xlog:gc+metaspace+freelist. After running into
>>>> an OOM, statistics and an ASCII representation of the class space will
>>>> be
>>>> shown. The unpatched version will show large expanses of unused small
>>>> chunks, the patched variant will show almost no waste.
>>>>
>>>> Note that the patch could be made more effective with a different size
>>>> ratio between small and medium chunks: in class space, that ratio is
>>>> 1:16,
>>>> so 16 small chunks must happen to be free to form one larger chunk.
>>>> With a
>>>> smaller ratio the chance for coalescation would be larger. So there may
>>>> be
>>>> room for future improvement here: Since we now can merge and split
>>>> chunks
>>>> on demand, we could introduce more chunk sizes. Potentially arriving at
>>>> a
>>>> buddy-ish allocator style where we drop hard-wired chunk sizes for a
>>>> dynamic model where the ratio between chunk sizes is always 1:2 and we
>>>> could in theory have no limit to the chunk size? But this is just a
>>>> thought
>>>> and well out of the scope of this patch.
>>>>
>>>> --
>>>>
>>>> What does this patch cost (memory):
>>>>
>>>>   - the occupancy bitmap adds 1 byte per 4K metaspace.
>>>>   - MetaChunk headers get larger, since we add an enum and two bools to
>>>> it.
>>>> Depending on what the c++ compiler does with that, chunk headers grow by
>>>> one or two MetaWords, reducing the payload size by that amount.
>>>> - The new alignment rules mean we may need to create padding chunks to
>>>> precede larger chunks. But since these padding chunks are added to the
>>>> freelist, they should be used up before the need for new padding chunks
>>>> arises. So, the maximally possible number of unused padding chunks
>>>> should
>>>> be limited by design to about 64K.
>>>>
>>>> The expectation is that the memory savings by this patch far outweighs
>>>> its
>>>> added memory costs.
>>>>
>>>> .. (performance):
>>>>
>>>> We did not see measurable drops in standard benchmarks raising over the
>>>> normal noise. I also measured times for a program which stresses
>>>> metaspace
>>>> chunk coalescation, with the same result.
>>>>
>>>> I am open to suggestions what else I should measure, and/or independent
>>>> measurements.
>>>>
>>>> --
>>>>
>>>> Other details:
>>>>
>>>> I removed SpaceManager::get_small_chunk_and_allocate() to reduce
>>>> complexity somewhat, because it was made mostly obsolete by this patch:
>>>> since small chunks are combined to larger chunks upon return to the
>>>> freelist, in theory we should not have that many free small chunks
>>>> anymore
>>>> anyway. However, there may be still cases where we could benefit from
>>>> this
>>>> workaround, so I am asking your opinion on this one.
>>>>
>>>> About tests: There were two native tests - ChunkManagerReturnTest and
>>>> TestVirtualSpaceNode (the former was added by me last year) - which did
>>>> not
>>>> make much sense anymore, since they relied heavily on internal behavior
>>>> which was made unpredictable with this patch.
>>>> To make up for these lost tests,  I added a new gtest which attempts to
>>>> stress the many combinations of allocation pattern but does so from a
>>>> layer
>>>> above the old tests. It now uses Metaspace::allocate() and friends. By
>>>> using that point as entry for tests, I am less dependent on
>>>> implementation
>>>> internals and still cover a lot of scenarios.
>>>>
>>>> --
>>>>
>>>> Review pointers:
>>>>
>>>> Good points to start are
>>>> - ChunkManager::return_single_chunk() - specifically,
>>>> ChunkManager::attempt_to_coalesce_around_chunk() - here we merge chunks
>>>> upon return to the free list
>>>> - ChunkManager::free_chunks_get(): Here we now split large chunks into
>>>> smaller chunks on demand
>>>> - VirtualSpaceNode::take_from_committed() : chunks are allocated
>>>> according to align rules now, padding chunks are handles
>>>> - The OccupancyMap class is the helper class implementing the new
>>>> occupancy bitmap
>>>>
>>>> The rest is mostly chaff: helper functions, added tests and
>>>> verifications.
>>>>
>>>> --
>>>>
>>>> Thanks and Best Regards, Thomas
>>>>
>>>> [1] https://bugs.openjdk.java.net/browse/JDK-8166690
>>>> [2] http://mail.openjdk.java.net/pipermail/jdk-dev/2017-November
>>>> /000128.html
>>>> [3] https://bugs.openjdk.java.net/browse/JDK-8185034
>>>> [4] https://bugs.openjdk.java.net/browse/JDK-8176808
>>>> [5] https://bugs.openjdk.java.net/secure/attachment/63532/test3.zip
>>>>
>>>>
>>>>
>>>>
>>
>
>

More information about the hotspot-runtime-dev mailing list