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

[Stuart Marks]

On 1/21/16 1:57 PM, Martin Buchholz wrote:
>> 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.

The code may be correct, but I'm concerned about maintenance. If things shift 
around, it might be easy to miss the possibility that negative minCapacity could 
be passed to grow() if overflow had occurred. So perhaps at least a comment 
would be warranted.

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

Ah, MAX_ARRAY_SIZE applies only to grow-by-50%, not to all array allocations. 
Perhaps it was my mistake for having believed its comment, which is

     The maximum size of array to allocate.

You know what they say about comments not matching the code.... :-)

I do think this comment needs to be adjusted to say that MAX_ARRAY_SIZE applies 
only to the 50% growth policy. I was certainly misled by it.

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

I don't think a global change is necessary, as the prevailing style in this file 
is to use the elementData field or to have a local elementData that's an alias 
of the field. I think readObject() is the outlier for using both the field and 
the local variable. But there are several other funny things going on here in 
readObject()... well I won't insist that you address them right now, as they're 
a distraction from this bugfix. So the change as you've proposed is fine.

(But let me know if you're interested in discussing readObject() further.)

>> 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?)

Yes, I think jtreg's default behavior has taught everyone, including our 
automated systems, to use -ignore:quiet. So I think @ignore is fine.

Thanks.

s'marks