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

[Martin Buchholz]

We have a new webrev.
Bug8146568.java now uses @ignore.
readObject has a minor rewrite, only assigning to elementData once.
(Yes, we can talk more about future improvements to ArrayList)
(maybe MAX_ARRAY_SIZE could have a better name ...)
We have some hopefully clearer internal comments:

    /**
     * The maximum size of array to allocate (unless necessary).
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1);
    }

    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {

On Thu, Jan 21, 2016 at 2:36 PM, Stuart Marks <stuart.marks at oracle.com> wrote:
>
>
> 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