RFR: Add generations to freeset [v8]

[Y. Srinivas Ramakrishna]

On Wed, 19 Apr 2023 15:27:57 GMT, Kelvin Nilsen <kdnilsen at openjdk.org> wrote:

>> ShenandoahFreeSet has not yet been modified to deal efficiently with the combination of old-gen and young-gen collection set reserves.  This PR makes changes so that we can distinguish between collector_is_free, old_collector_is_free, and mutator_is_free.  Further, it endeavors to keep each set of free regions tightly packed, so the range of regions representing each set is small.
>> 
>> In its current form, this no longer fails existing regression tests (except for known problems that are being addressed independently)
>
> Kelvin Nilsen has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 207 commits:
> 
>  - Merge remote-tracking branch 'origin' into add-generations-to-freeset
>  - Respond to reviewer feedback
>    
>    Various improvements suggested by reviewers.  Mostly improved comments
>    and some minor refactoring.
>  - Add TODO comment for exapnsion of old-gen
>  - Remove debug instrumentation
>  - Merge master
>  - Fix calculation of minimum fill size
>    
>    We were incorrectly using byte size rather than word size.
>  - Fix error in ShenandoahFreeSet usage accounting
>    
>    We were incorrectly increasing used for plab padding.  That is
>    old_collector memory and should not affect mutator usage.  This commit
>    also includes some refactoring, additional assertions, and additional
>    verification of consistent free-space accounting.
>  - Fix typo in a comment
>  - Fix white space
>  - Merge remote-tracking branch 'GitFarmBranch/add-generations-to-freeset' into add-generations-to-freeset
>  - ... and 197 more: https://git.openjdk.org/shenandoah/compare/016bf071...7319eeeb

I'll leave these comments here for now and finish the rest of the review in a bit.

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp line 63:

> 61: 
> 62: inline bool ShenandoahFreeSet::in_mutator_set(size_t idx) const {
> 63:   bool is_mutator_free = _mutator_free_bitmap.at(idx);

Should line 63 go after the assert on the next line 64?

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp line 534:

> 532:         _heap->notify_mutator_alloc_words(waste >> LogHeapWordSize, true);
> 533:       }
> 534:       assert(probe_mutator_set(idx), "Must be mutator free: " SIZE_FORMAT, idx);

Looking at the assertions in `in_mutator_set()`, could you explain which of those wouldn't hold if you used `in_mutator_set()` in this assert, rather than `probe_mutator_set()`?

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp line 537:

> 535:       remove_from_mutator_set(idx);
> 536:       assert(!in_collector_set(idx) && !in_old_collector_set(idx), "Region cannot be in multiple free sets");
> 537:       adjust_mutator_bounds_if_touched(idx);

Would it be too expensive if `remove_from_mutator_set()` and `add_to_mutator_set()` were to always adjust the bounds if needed (i.e. we traffick an extremal element into or out of the set). Adjustments at additions are of course much less expensive. Then, the interval end-points would always stay faithful to membership index extrema, establishing a good invariant.

Is the concern that the adjustments necessitated when removing elements might be  too expensive to do at each removal (addition is no problem).

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 53:

> 51:   // Left-most and right-most region indexes. There are no free regions outside of [left-most; right-most] index intervals.
> 52:   // The sets are not necessarily contiguous.  It is common for collector_is_free regions to reside within the mutator_is_free
> 53:   // range, and for _old_collector_is_free regions to reside within the collector_is_free range.

Is the following a reasonable interpretation of the state of affairs:

For a free set of a given kind (mutator, collector, old_collector), we maintain left and right indices to limit searching. The intervals induced by these extremal indices designate the lowest and highest indices at which that kind of free region exists. However, these intervals may overlap. In particular, it is quite common for the collector free interval to overlap the mutator free interval on one side (the low end) and the old_collector free interval on the other (the high end).

Q: Can it then be also the case that the mutator free interval may also, in a worst case situation, overlap with the old_collector free interval? In other words, in a worst case entropic situation, all intervals may overlap (even though each non-empty interval has unique extremal points).

The interval bounds for these sets serve only as a performance optimization to reduce some search interval in the allocation paths?

PS: If the above understanding is correct, then I wouldn't use the term `contiguous set` in your description, but rather replace it with non-overlapping intervals, and stay with the interval abstraction when talking about these in comments.

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 92:

> 90:   //       idx >= leftmost &&
> 91:   //       idx <= rightmost
> 92:   //     }

Nice; thank you for the precise characterization!

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 115:

> 113:   inline bool probe_collector_set(size_t idx) const;
> 114:   inline bool probe_old_collector_set(size_t idx) const;
> 115: 

May be you can add a delineating comment below:


// Methods that change set membership:

-------------

PR Review: https://git.openjdk.org/shenandoah/pull/250#pullrequestreview-1393096855
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1172004084
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1172829252
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1172832769
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1172013452
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1172017161
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1172018455