RFR: 8247755: Leaner and more versatile GrowableArray classes

[Stefan Karlsson]

Hi all,

Please review and/or comment on this patch to create leaner and more 
versatile GrowableArray classes.

https://cr.openjdk.java.net/~stefank/8247755/webrev.01
https://bugs.openjdk.java.net/browse/JDK-8247755

This is a proposal to rewrite the GrowableArray classes, with two main 
goals:

1) Allow a GrowableArray instance to be allocated on the stack or 
embedded in other objects. This removes one of the two indirections when 
operating on the array elements.

2) Make the GrowableArray instances smaller, so that there's no extra 
overhead when they are embedded in other objects.

This will enable us to use GrowableArray effectively in ZGC, without 
having to rely on our own implementations. See follow-up patch:
https://cr.openjdk.java.net/~stefank/8247759/webrev.01

Some background about the GrowableArray:

GrowableArray is split into two memory parts. One for the instance of 
the GrowableArray, and a second, separate memory part for the elements. 
This memory can come from these places:

a) Resource area in the thread
b) CHeap (malloc)
c) Arena (malloced arena)
d) Stack
e) Embedded in other object

 From the C++ compiler's point-of-view, (a)-(e) can be used to allocate 
the GrowableArray, and (a)-(c) can be used to allocate the elements. 
However, there are runtime asserts that restricts the combinations.

One of the restrictions is that if either of the GrowableArray instance 
memory, or the elements memory, comes from the CHeap, then the other 
must also come from the CHeap.

I've found two reasons why we want to be restrictive with our CHeap 
allocated elements:

- if the GrowableArray instance is allocated in (a) or (c), then the 
destructor will never run and we get a memory leak because the elements 
are not deallocated.

However, for stack allocated instances the destructor will be run, and 
the memory will be handed back. For embedded instances it all depends on 
how the parent instance was allocated.

- There's no proper support for copying/moving of the elements, just a 
simple pointer copy. So, if a copy would be done, the source 
GrowableArray would still have a pointer to the elements, and if the 
source were destructed (maybe because it was stack allocated and went 
out-of-scope) then the memory of the destination GrowableArray will be 
deallocated. This isn't a problem with instances in (a) or (c), since 
their destructors won't be run.

Proposal for Goal 1:

- Allow stack allocated and embedded GrowableArrays to have CHeap 
allocated elements.
- Add an assert in a copy constructor and assignment operator that 
checks that the GrowableArray elements are not CHeap allocated.

The rest of the patch mainly deals with Goal 2:

The current fields of GrowableArrays, in product builds, are:
    int _len;
    int _max;
    Arena* _arena;
    MEMFLAGS _memflags;
    E* _data;

and the resulting is 32 bytes: 4 + 4 + 8 + 8 + 8. The _memflags size is 
due to alignment requirements for the _data field.

- By combining _arena and _memflags, this is reduced to 24 bytes.
- By having a specialized CHeap version with the MEMFLAGS encoded as a 
template parameter, we can get rid of both _memflags and _arena fields, 
and reduce this to 16 bytes.

Things to note about the patch:

- GrowableArrayMetadata: I've fused _arena and _memflags into one 
uintptr_t field, and encapsulated all bookkeeping about where and how 
the memory is allocated for the GrowableArray. The hope is to simplify 
the code a bit, and also to move some of the checking out into a 
non-template class, so that the code can be put in the .cpp file.

- GrowableArrayNestingCheck: Simplify and encapsulate resource area 
nesting checks.

- I'm using CRTP because I don't want a vtable in the class. This means 
that the super class can cast to derived type, responsible for 
allocation and deallocation:

template <typename E> class GrowableArray : public GrowableArrayWithAllocator<E, GrowableArray<E> >

and then:

void GrowableArrayWithAllocator<E, S>::grow(int j) {
...
   E* newData = static_cast<S*>(this)->allocate();

- Since I'm chainging so much of the structure of the code, I've also 
made some stylistic changes to make the code more consistent.

- Moved the CompareClosure to iterator.hpp, where many of our other 
closures are located.

- Moved _sort_Fn, since it was already used by non-GrowableArray code

- I've added a GrowableArrayCHeap class to be able to mostly side-step 
the complication of the GrowableArray elements allocation, and to 
minimize the instance size.

- The metaspaceShared.cpp was used to show how GrowableArrayCHeap can be 
used. It's not strictly necessary, and could be reverted.

-  The arguments.cpp change shows a usage of GrowableArrayView as a way 
to only expose an interface that don't allow the array to be grown.

- The arguments.cpp change also shows stack allocated 
GrowableArrayCHeap, that automatically gets deallocated when the 
function returns, and the cleanups we can do because of this.

- The hashtable.* changes show an embedded GrowableArrayCHeap.

- The SA agent. I didn't bother renaming the GenericGrowableArray file. 
I can do that upon request.

- I added gtest for GrowableArray. There was not a single unit test of 
GrowableArray before. The creates all possible memory allocation 
combinations and run limited set of sanity checks. It also checks that 
the different memory allocation combinations return the correct 
allocation types when queried. I've added negative tests to show that 
GrowableArrays with CHeap allocated elements assert when being copied.

Testing: will run at least tier1-3, but most likely more tiers on Linux 
x64. Suggestions on what to test welcome.

Thanks,
StefanK