From d0ecb1ed10725a6b2c84d64e212984cd4c0d26d2 Mon Sep 17 00:00:00 2001 From: Dan Sandler Date: Thu, 13 Apr 2017 20:21:12 -0400 Subject: [PATCH] Avoid ClassCastException in ArrayMap. Only happens if you're put()ing and clear()ing the map from different threads, and Dianne told you not to do that. In addition to avoiding the cache poisoning that results from concurrent access, ArrayMap now attempts to throw ConcurrentModificationException if clear() or ensureCapacity() or put() notices you've modified the map elsewhere. Bug: 32994281 Test: runtest -x frameworks/base/core/tests/coretests/src/android/util/ArrayMapTest.java runtest -x cts/tests/tests/util/src/android/util/cts/ArrayMapTest.java Change-Id: Ia75970aa9e2b2b65692179f51243584b9773797f --- core/java/android/util/ArrayMap.java | 114 +++++++++++++++------ .../coretests/src/android/util/ArrayMapTest.java | 108 +++++++++++++++++++ 2 files changed, 192 insertions(+), 30 deletions(-) create mode 100644 core/tests/coretests/src/android/util/ArrayMapTest.java diff --git a/core/java/android/util/ArrayMap.java b/core/java/android/util/ArrayMap.java index 92a5803b5ddb..d51a13f3d119 100644 --- a/core/java/android/util/ArrayMap.java +++ b/core/java/android/util/ArrayMap.java @@ -19,6 +19,7 @@ package android.util; import libcore.util.EmptyArray; import java.util.Collection; +import java.util.ConcurrentModificationException; import java.util.Map; import java.util.Set; @@ -49,6 +50,18 @@ public final class ArrayMap implements Map { private static final String TAG = "ArrayMap"; /** + * Attempt to spot concurrent modifications to this data structure. + * + * It's best-effort, but any time we can throw something more diagnostic than an + * ArrayIndexOutOfBoundsException deep in the ArrayMap internals it's going to + * save a lot of development time. + * + * Good times to look for CME include after any allocArrays() call and at the end of + * functions that change mSize (put/remove/clear). + */ + private static final boolean CONCURRENT_MODIFICATION_EXCEPTIONS = true; + + /** * The minimum amount by which the capacity of a ArrayMap will increase. * This is tuned to be relatively space-efficient. */ @@ -86,6 +99,18 @@ public final class ArrayMap implements Map { int mSize; MapCollections mCollections; + private static int binarySearchHashes(int[] hashes, int N, int hash) { + try { + return ContainerHelpers.binarySearch(hashes, N, hash); + } catch (ArrayIndexOutOfBoundsException e) { + if (CONCURRENT_MODIFICATION_EXCEPTIONS) { + throw new ConcurrentModificationException(); + } else { + throw e; // the cache is poisoned at this point, there's not much we can do + } + } + } + int indexOf(Object key, int hash) { final int N = mSize; @@ -94,7 +119,7 @@ public final class ArrayMap implements Map { return ~0; } - int index = ContainerHelpers.binarySearch(mHashes, N, hash); + int index = binarySearchHashes(mHashes, N, hash); // If the hash code wasn't found, then we have no entry for this key. if (index < 0) { @@ -132,7 +157,7 @@ public final class ArrayMap implements Map { return ~0; } - int index = ContainerHelpers.binarySearch(mHashes, N, 0); + int index = binarySearchHashes(mHashes, N, 0); // If the hash code wasn't found, then we have no entry for this key. if (index < 0) { @@ -282,10 +307,16 @@ public final class ArrayMap implements Map { @Override public void clear() { if (mSize > 0) { - freeArrays(mHashes, mArray, mSize); + final int[] ohashes = mHashes; + final Object[] oarray = mArray; + final int osize = mSize; mHashes = EmptyArray.INT; mArray = EmptyArray.OBJECT; mSize = 0; + freeArrays(ohashes, oarray, osize); + } + if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize > 0) { + throw new ConcurrentModificationException(); } } @@ -309,15 +340,19 @@ public final class ArrayMap implements Map { * items. */ public void ensureCapacity(int minimumCapacity) { + final int osize = mSize; if (mHashes.length < minimumCapacity) { final int[] ohashes = mHashes; final Object[] oarray = mArray; allocArrays(minimumCapacity); if (mSize > 0) { - System.arraycopy(ohashes, 0, mHashes, 0, mSize); - System.arraycopy(oarray, 0, mArray, 0, mSize<<1); + System.arraycopy(ohashes, 0, mHashes, 0, osize); + System.arraycopy(oarray, 0, mArray, 0, osize<<1); } - freeArrays(ohashes, oarray, mSize); + freeArrays(ohashes, oarray, osize); + } + if (CONCURRENT_MODIFICATION_EXCEPTIONS && mSize != osize) { + throw new ConcurrentModificationException(); } } @@ -435,6 +470,7 @@ public final class ArrayMap implements Map { */ @Override public V put(K key, V value) { + final int osize = mSize; final int hash; int index; if (key == null) { @@ -452,9 +488,9 @@ public final class ArrayMap implements Map { } index = ~index; - if (mSize >= mHashes.length) { - final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1)) - : (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); + if (osize >= mHashes.length) { + final int n = osize >= (BASE_SIZE*2) ? (osize+(osize>>1)) + : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE); if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n); @@ -462,22 +498,31 @@ public final class ArrayMap implements Map { final Object[] oarray = mArray; allocArrays(n); + if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { + throw new ConcurrentModificationException(); + } + if (mHashes.length > 0) { - if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0"); + if (DEBUG) Log.d(TAG, "put: copy 0-" + osize + " to 0"); System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length); System.arraycopy(oarray, 0, mArray, 0, oarray.length); } - freeArrays(ohashes, oarray, mSize); + freeArrays(ohashes, oarray, osize); } - if (index < mSize) { - if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (mSize-index) + if (index < osize) { + if (DEBUG) Log.d(TAG, "put: move " + index + "-" + (osize-index) + " to " + (index+1)); - System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index); + System.arraycopy(mHashes, index, mHashes, index + 1, osize - index); System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1); } + if (CONCURRENT_MODIFICATION_EXCEPTIONS) { + if (osize != mSize || index >= mHashes.length) { + throw new ConcurrentModificationException(); + } + } mHashes[index] = hash; mArray[index<<1] = key; mArray[(index<<1)+1] = value; @@ -594,19 +639,22 @@ public final class ArrayMap implements Map { */ public V removeAt(int index) { final Object old = mArray[(index << 1) + 1]; - if (mSize <= 1) { + final int osize = mSize; + final int nsize; + if (osize <= 1) { // Now empty. if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to 0"); - freeArrays(mHashes, mArray, mSize); + freeArrays(mHashes, mArray, osize); mHashes = EmptyArray.INT; mArray = EmptyArray.OBJECT; - mSize = 0; + nsize = 0; } else { + nsize = osize - 1; if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) { // Shrunk enough to reduce size of arrays. We don't allow it to // shrink smaller than (BASE_SIZE*2) to avoid flapping between // that and BASE_SIZE. - final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2); + final int n = osize > (BASE_SIZE*2) ? (osize + (osize>>1)) : (BASE_SIZE*2); if (DEBUG) Log.d(TAG, "remove: shrink from " + mHashes.length + " to " + n); @@ -614,32 +662,38 @@ public final class ArrayMap implements Map { final Object[] oarray = mArray; allocArrays(n); - mSize--; + if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { + throw new ConcurrentModificationException(); + } + if (index > 0) { if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0"); System.arraycopy(ohashes, 0, mHashes, 0, index); System.arraycopy(oarray, 0, mArray, 0, index << 1); } - if (index < mSize) { - if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + mSize + if (index < nsize) { + if (DEBUG) Log.d(TAG, "remove: copy from " + (index+1) + "-" + nsize + " to " + index); - System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index); + System.arraycopy(ohashes, index + 1, mHashes, index, nsize - index); System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, - (mSize - index) << 1); + (nsize - index) << 1); } } else { - mSize--; - if (index < mSize) { - if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + mSize + if (index < nsize) { + if (DEBUG) Log.d(TAG, "remove: move " + (index+1) + "-" + nsize + " to " + index); - System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index); + System.arraycopy(mHashes, index + 1, mHashes, index, nsize - index); System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, - (mSize - index) << 1); + (nsize - index) << 1); } - mArray[mSize << 1] = null; - mArray[(mSize << 1) + 1] = null; + mArray[nsize << 1] = null; + mArray[(nsize << 1) + 1] = null; } } + if (CONCURRENT_MODIFICATION_EXCEPTIONS && osize != mSize) { + throw new ConcurrentModificationException(); + } + mSize = nsize; return (V)old; } diff --git a/core/tests/coretests/src/android/util/ArrayMapTest.java b/core/tests/coretests/src/android/util/ArrayMapTest.java new file mode 100644 index 000000000000..32aa29fa3339 --- /dev/null +++ b/core/tests/coretests/src/android/util/ArrayMapTest.java @@ -0,0 +1,108 @@ +/* + * Copyright (C) 2017 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software distributed under the + * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the specific language governing + * permissions and limitations under the License. + */ + +package android.util; + +import android.util.ArrayMap; + +import junit.framework.TestCase; +import org.junit.Test; + +import java.util.ConcurrentModificationException; + +/** + * Unit tests for ArrayMap that don't belong in CTS. + */ +public class ArrayMapTest extends TestCase { + private static final String TAG = "ArrayMapTest"; + ArrayMap map = new ArrayMap<>(); + + /** + * Attempt to generate a ConcurrentModificationException in ArrayMap. + *

+ * ArrayMap is explicitly documented to be non-thread-safe, yet it's easy to accidentally screw + * this up; ArrayMap should (in the spirit of the core Java collection types) make an effort to + * catch this and throw ConcurrentModificationException instead of crashing somewhere in its + * internals. + * + * @throws Exception + */ + @Test + public void testConcurrentModificationException() throws Exception { + final int TEST_LEN_MS = 5000; + System.out.println("Starting ArrayMap concurrency test"); + new Thread(() -> { + int i = 0; + while (map != null) { + try { + map.put(String.format("key %d", i++), "B_DONT_DO_THAT"); + } catch (ArrayIndexOutOfBoundsException e) { + Log.e(TAG, "concurrent modification uncaught, causing indexing failure", e); + fail(); + } catch (ClassCastException e) { + Log.e(TAG, "concurrent modification uncaught, causing cache corruption", e); + fail(); + } catch (ConcurrentModificationException e) { + System.out.println("[successfully caught CME at put #" + i + + " size=" + (map == null ? "??" : String.valueOf(map.size())) + "]"); + } + if (i % 200 == 0) { + System.out.print("."); + } + } + }).start(); + for (int i = 0; i < (TEST_LEN_MS / 100); i++) { + try { + Thread.sleep(100); + map.clear(); + System.out.print("X"); + } catch (InterruptedException e) { + } catch (ArrayIndexOutOfBoundsException e) { + Log.e(TAG, "concurrent modification uncaught, causing indexing failure"); + fail(); + } catch (ClassCastException e) { + Log.e(TAG, "concurrent modification uncaught, causing cache corruption"); + fail(); + } catch (ConcurrentModificationException e) { + System.out.println( + "[successfully caught CME at clear #" + + i + " size=" + map.size() + "]"); + } + } + map = null; // will stop other thread + System.out.println(); + } + + /** + * Check to make sure the same operations behave as expected in a single thread. + */ + @Test + public void testNonConcurrentAccesses() throws Exception { + for (int i = 0; i < 100000; i++) { + try { + map.put(String.format("key %d", i++), "B_DONT_DO_THAT"); + if (i % 200 == 0) { + System.out.print("."); + } + if (i % 500 == 0) { + map.clear(); + System.out.print("X"); + } + } catch (ConcurrentModificationException e) { + Log.e(TAG, "concurrent modification caught on single thread", e); + fail(); + } + } + } +} -- 2.11.0