United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-7121314 (coll) Behavior mismatch between AbstractCollection.toArray(T[] ) and its spec
JDK-7121314 : (coll) Behavior mismatch between AbstractCollection.toArray(T[] ) and its spec

Details
Type:
Bug
Submit Date:
2011-12-14
Status:
Closed
Updated Date:
2013-06-26
Project Name:
JDK
Resolved Date:
2012-05-14
Component:
core-libs
OS:
linux
Sub-Component:
java.util:collections
CPU:
x86
Priority:
P4
Resolution:
Fixed
Affected Versions:
7
Fixed Versions:

Related Reports
Backport:
Backport:

Sub Tasks

Description
FULL PRODUCT VERSION :
java version "1.7.0_01"
Java(TM) SE Runtime Environment (build 1.7.0_01-b08)
Java HotSpot(TM) Client VM (build 21.1-b02, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
OS independent, all linux, solaris and windows are affected.

A DESCRIPTION OF THE PROBLEM :
AbstractCollection.toArray(T[] ) 's behavior maybe different from the spec in multithread environment. The spec says "If the collection fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this collection."  However, in multithread environment, it is not easy to tell if the collection fits in the specified array, because the items may be removed when toArray is copying.  The current implementation get the size before copying the items, so the returned array may fits into the specified array but a new array is returned.

There are more detail on mailinglist:
http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-December/008686.html

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
 Compile and run the testcase

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
 The testcase prints : Is buffer used : true
ACTUAL -
 The testcase prints : Is buffer used : false

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class CollectionToArrayTest {

    static volatile Map<String, String> map = new TConcurrentHashMap<String, String>();
    static volatile boolean gosleep = true;

    static class TConcurrentHashMap<K, V> extends ConcurrentHashMap<K, V> {
        public int size() {
            int oldresult = super.size();
            System.out.println("map size before concurrent remove is "
                    + oldresult);
            while (gosleep) {
                try {
                    // Make sure the map is modified during toArray is called,
                    // between getsize and being iterated.
                    Thread.sleep(1000);
                    // System.out.println("size called, size is " + oldresult +
                    // " take a sleep to make sure the element is deleted before size is returned.");
                } catch (Exception e) {
                }
            }
            return oldresult;
        }
    }

    static class ToArrayThread implements Runnable {
        public void run() {
            for (int i = 0; i < 5; i++) {
                String str = Integer.toString(i);
                map.put(str, str);
            }
            String[] buffer = new String[4];
            String[] strings = map.values().toArray(buffer);
            // System.out.println("length is " + strings.length);
            if (strings.length <= buffer.length) {
                System.out.println("given array size is "
                                + buffer.length
                                + " \nreturned array size is "
                                + strings.length
                                + ", \nbuffer should be used according to spec. Is buffer used : "
                                + (strings == buffer));
            }
        }
    }

    static class RemoveThread implements Runnable {
        public void run() {
            String str = Integer.toString(0);
            map.remove(str);
            gosleep = false;
        }
    }

    public static void main(String args[]) {
        CollectionToArrayTest app = new CollectionToArrayTest();
        app.test_concurrentRemove();
    }

    public void test_concurrentRemove() {
        System.out.println("//////////////////////////////////////////////\n" +
        		        "The spec says if the given array is large\n "  +
                        "enough to hold all elements, the given array\n" +
                        "should be returned by toArray. This \n" +
                        "testcase checks this case. \n" +
                        "//////////////////////////////////////////////");

        Thread[] threads = new Thread[2];
        threads[0] = new Thread(new ToArrayThread());
        threads[1] = new Thread(new RemoveThread());

        threads[0].start();

        try {
            // Take a sleep to make sure toArray is already called.
            Thread.sleep(1200);
        } catch (Exception e) {
        }

        threads[1].start();
    }
}

---------- END SOURCE ----------

                                    

Comments
EVALUATION

AbstractCollection.toArray(T[] as) states:

"This implementation returns an array containing all the elements returned by this collection's iterator in the same order, stored in consecutive elements of the array, starting with index 0. If the number of elements returned by the iterator is too large to fit into the specified array, then the elements are returned in a newly allocated array with length equal to the number of elements returned by the iterator, even if the size of this collection changes during iteration, as might happen if the collection permits concurrent modification during iteration. The size method is called only as an optimization hint; the correct result is returned even if the iterator returns a different number of elements. "

As the number of elements to be returned by the iterator can not be known until iteration completes, it follows that only then can the question of whether or not the specified array is large enough, be answered. Consequently if the number of elements returned by the iterator would fit in the specified array then the specified array must be returned. So I would say that this is a bug in the JDK's AbstractCollection implementation.

We use size() at the start of the method to determine if the supplied array is large enough, but don't consider that the collection may shrink during iteration. Before returning we need to check if the actual number of elements retrived will fit in the original array.
                                     
2011-12-14
EVALUATION

Changeset: e06ea0dd9207
Author:    littlee
Date:      2012-04-10 10:17 +0800
URL:       http://hg.openjdk.java.net/jdk8/tl/jdk/rev/e06ea0dd9207

7121314: Behavior mismatch between AbstractCollection.toArray(T[] ) and its spec
Reviewed-by: dholmes, mduigou
Contributed-by: Sean Zhou <###@###.###>, Ulf Zibis <###@###.###>, David Holmes <###@###.###>

! src/share/classes/java/util/AbstractCollection.java
+ test/java/util/AbstractCollection/ToArrayTest.java
                                     
2012-04-17



Hardware and Software, Engineered to Work Together