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

[Stuart Marks]

Hi Martin,

Thanks for adding the comments and @ignore.
On readObject(), ok, you went ahead and rearranged some stuff. You hit a couple 
of the issues I had spotted, namely the multiple assignment to elementData and 
the potentially confusing reuse of the name 'elementData'.

The other issue was if size is less than zero. This could only occur with a 
corrupted or tampered serialized data stream. The old code would "successfully" 
deserialize a dysfunctional ArrayList instance, whereas the modified code will 
throw NegativeArraySizeException from readObject().

I don't know if that was intentional, but I prefer the new behavior!

Strictly speaking I think throwing InvalidObjectException would preferable, but 
if you want to push what you have, I'm ok with it.

s'marks

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