RFR: 8189088: Add intrusive doubly-linked list utility [v8]

[Kim Barrett]

On Tue, 17 Oct 2023 09:07:26 GMT, Kim Barrett <kbarrett at openjdk.org> wrote:

>> Please review this new facility, providing a general mechanism for intrusive
>> doubly-linked lists. A class supports inclusion in a list by having an
>> IntrusiveListEntry member, and providing structured information about how to
>> access that member. A class supports inclusion in multiple lists by having
>> multiple IntrusiveListEntry members, with different lists specified to use
>> different members.
>> 
>> The IntrusiveList class template provides the list management. It is modelled
>> on bidirectional containers such as std::list and boost::intrusive::list,
>> providing many of the expected member types and functions. (Note that the
>> member types use the Standard's naming conventions.) (Not all standard
>> container requirements are met; some operations are not presently supported
>> because they haven't been needed yet.) This includes iteration support using
>> (mostly) standard-conforming iterator types (they are presently missing
>> iterator_category member types, pending being able to include <iterator> so we
>> can use std::bidirectional_iterator_tag).
>> 
>> This change only provides the new facility, and doesn't include any uses of
>> it. It is intended to replace the 4-5 (or maybe more) competing intrusive
>> doubly-linked lists presently in HotSpot.  Unlike most (or perhaps all?) of
>> those alterantives, this proposal provides a suite of unit tests.
>> 
>> An example of a place that I think might benefit from this is G1's region
>> handling. There are various places where G1 iterates over all regions in order
>> to do something with those which satisfy some property (humongous regions,
>> regions in the collection set, &etc). If it were trivial to create new region
>> sublists (and this facility makes that easy), some of these could be turned
>> into direct iteration over only the regions of interest.
>> 
>> Some specific points to consider when reviewing this proposal:
>> 
>> (1) This proposal follows Standard Library API conventions, which differ from
>> HotSpot in various ways.
>> 
>> (1a) Lists and iterators provide various type members, with names per the
>> Standard Library. There has been discussion of using some parts of the
>> Standard Library eventually, in which case this would be important. But for
>> now some of the naming choices are atypical for HotSpot.
>> 
>> (1b) Some of the function signatures follow the Standard Library APIs even
>> though the reasons for that form might not apply to HotSpot. For example, the
>> list pop operations don't return the removed...
>
> Kim Barrett has updated the pull request incrementally with four additional commits since the last revision:
> 
>  - remove unnecessary code markers in comments
>  - use override for virtual test support functions
>  - remove support for allocation base classes
>  - remove IntrusiveList::operator[]

src/hotspot/share/utilities/intrusiveList.hpp line 812:

> 810:   static constexpr bool can_splice_from() {
> 811:     return Conjunction<Impl::IsListType<Other>,
> 812:                        std::is_convertible<typename Other::iterator, iterator>>::value;

Here and in can_swap we're using `Conjunction` rather than simple `&&`
expressions of the values. The intent is to delay the iterator check until
we've verified `Other` is actually a List type. But that isn't working.
Instead, if `Other` isn't a List then we get a syntax error on
`Other::iterator`, which is not at all helpful as error reporting goes. To fix
this we need to add a level of indirection so the code containing
`Other::iterator` doesn't get instantiated until the IsListType check has
passed.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1362711685