RFR: Add generations to freeset [v8]

[Kelvin Nilsen]

On Thu, 20 Apr 2023 02:18:22 GMT, Y. Srinivas Ramakrishna <ysr at openjdk.org> wrote:

>> 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
>
> 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.

Yes.  It is possible that all three can overlap.  I'll fix this description.

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

PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1173028004