RFR: JDK-8146568 NegativeArraySizeException in ArrayList.grow(int)

[Martin Buchholz]

On Thu, Jan 21, 2016 at 11:39 AM, Stuart Marks <stuart.marks at oracle.com> wrote:
> Hi Martin,
>
> Thanks for digging into this. There are some subtle issues here. I have a
> few questions.
>
> One is that in list.addAll(other), the sizes of list and other exceeds
> Integer.MAX_VALUE, then grow(int) will be called with a negative value for
> minCapacity. The code *seems* to handle this ok, but the negative
> minCapacity value can get pretty deeply into the helper methods before being
> caught. Would it be better to check it at the top of grow(int) and throw an
> exception there? (Probably OOME.) I think it would make the subsequent code
> easier to follow.

It's true that the code is rather tricky, "overflow-conscious code".
But this is ArrayList, so it seems worth optimizing even for grow.

The common case is that we grow by 50% and then if  (newCapacity -
MAX_ARRAY_SIZE <= 0) we can be sure that newCapacity is not negative.

> It looks like there are a variety of ways for minCapacity that is positive
> but greater than MAX_ARRAY_SIZE to reach newCapacity(). If this occurs, and
> other conditions are right, it looks like the code will end up attempting to
> allocate an array greater than MAX_ARRAY_SIZE.

If grow(n) is called with MAX_ARRAY_SIZE < n <= MAX_VALUE, then we no
choice but to allocate an array of that size!  It's only when we use
the grow-by-50% strategy that we can change our minds by scaling back.
I don't see a bug.

> One style point I noticed (which might be an issue of me not being used to
> it) is the use of an elementData local variable to shadow the elementData
> field. This is more-or-less ok in places where elementData is initialized
> from this.elementData, but in readObject(), the local elementData is
> introduced in a nested scope. This means that elementData has different
> meanings in different parts of the method.

Yeah, elementData is not great but I couldn't find anything better.
"a" is already taken.  "snapshot" has the wrong connotations.  If you
prefer e.g. "elements" I will change it throughout, but in either case
a reader needs to understand that "elements" and "elementData" are
"almost" the same.

> For the test Bug8146568 I think the preferred way to disable a test with
> extreme memory requirements is to use @ignore; see

I've never liked @ignore in practice, because jtreg is very noisy
unless you also say
 -ignore:quiet
(which I always do, but does everyone else?)