从源码解析一个 SparseArray 线程不安全的崩溃

2023-04-12

前言

工作中遇到一个崩溃，将无关逻辑去掉，最后的崩溃部分是：

1if (sparseArray.get(1) != null) {  
2  Log.i("SparseArray", sparseArray.get(1).toString());  
3}

抛出的异常是空指针：java.lang.NullPointerException，其实根据经验也知道是线程安全问题，但是排查的过程中却越来越觉得我们的应用场景中不应该出现 null 的存在。

排查

删除

这个问题第一反应是有一个线程从 sparseArray 中删除了对象，然后导致第二次获取成了 null，但是继续排查代码发现并没有任何地方调用过删除（另外根据后面翻阅源码得知 SparseArray#delete() 并不会立刻删除代码，而是先标记为 DELETED）。

扩容

下一个思路就是类似 HashMap 扩容时搬运数据造成的线程安全问题。但是经检查，所有 sparseArray.put() 的 key 是固定的三个值：0、1、2，甚至都是主线程 put 的，而 SparseArray 初始化的源码可以知道默认构造函数是初始化了两个长度为 10 的数组：

 1public SparseArray() {
 2    this(10);
 3}
 4
 5public SparseArray(int initialCapacity) {
 6    if (initialCapacity == 0) {
 7        mKeys = EmptyArray.INT;
 8        mValues = EmptyArray.OBJECT;
 9    } else {
10        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
11        mKeys = new int[mValues.length];
12    }
13    mSize = 0;
14}

有个有趣的点：其中 ArrayUtils.newUnpaddedObjectArray(initialCapacity) 会调用 VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen) 返回一个至少为 minLen 长度的数组，因为数据对齐可能会分配大于申请的空间使 CPU 读写更加高效，即会有一些 padding 空间，为了不浪费这个空间，直接返回个更大的 array。

重排

既然无论如何，都不会有扩容的产生，那么还有什么情况下会造成在某一瞬间会获取到 null 呢？这里需要介绍一下 SparseArray 的基本原理：

内部结构是两个数组，一个储存 key 的 int 数组，一个储存 value 的 Object 数组。
get() 使用二分查找，所以 key 数组是有序的。

那么问题就能猜到：会不会是添加数据的时候因为构建有序数组而重排时导致了数据的搬运，我们可以从源码中看一下：

  1// android.util.SparseArray
  2public void put(int key, E value) {
  3    // 首先二分查找 key 数组中要插入的 key 的位置，如果存在 key 直接返回 key 的下标，如果不存在，则返回期望插入的位置的取反（参见下面的源码，不详解释）
  4    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
  5
  6    // 如果存在 key，直接更新对应的 value 即可
  7    if (i >= 0) {
  8        mValues[i] = value;
  9    } else {
 10        // 如果不存在，则拿到插入期望的位置
 11        i = ~i;
 12
 13        // mSize 是当前实际已插入的数据量，在未调用 gc() 之前包括已经标记为 DELETED 的数据
 14        // DELETED 是在 delete() 后并不会立刻删除代码，而是先标记为 DELETED
 15        // 如果期望插入的位置小于 mSize，并且此处是已经被标记删除的数据，则直接更新 kv 两个数组
 16        if (i < mSize && mValues[i] == DELETED) {
 17            mKeys[i] = key;
 18            mValues[i] = value;
 19            return;
 20        }
 21
 22        // 如果需要垃圾回收并且现在已经插入的数量大于等于 key 数组的长度，则垃圾回收
 23        if (mGarbage && mSize >= mKeys.length) {
 24            // 将被标记为 DELETED 的位置后面的数据向前搬运来垃圾回收（参见下面的源码，不详解释）
 25            gc();
 26
 27            // 回收后重新查找期望插入的位置
 28            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
 29        }
 30
 31        // 通过 System.arraycopy 创建一个插入 i 位置后的递增新数组（参见下面的源码，不详解释）
 32        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
 33        // 通过 System.arraycopy 创建一个插入 i 位置后的递增新数组
 34        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
 35        // mSize 自增 1
 36        mSize++;
 37    }
 38}
 39
 40// com.android.internal.util.GrowingArrayUtils
 41public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
 42    assert currentSize <= array.length;
 43    if (currentSize + 1 <= array.length) {
 44        System.arraycopy(array, index, array, index + 1, currentSize - index);
 45        array[index] = element;
 46        return array;
 47    }
 48    @SuppressWarnings("unchecked")
 49    T[] newArray = ArrayUtils.newUnpaddedArray((Class<T>)array.getClass().getComponentType(),
 50            growSize(currentSize));
 51    System.arraycopy(array, 0, newArray, 0, index);
 52    newArray[index] = element;
 53    System.arraycopy(array, index, newArray, index + 1, array.length - index);
 54    return newArray;
 55}
 56
 57// android.util.ContainerHelpers
 58static int binarySearch(int[] array, int size, int value) {
 59    int lo = 0;
 60    int hi = size - 1;
 61
 62    while (lo <= hi) {
 63        final int mid = (lo + hi) >>> 1;
 64        final int midVal = array[mid];
 65
 66        if (midVal < value) {
 67            lo = mid + 1;
 68        } else if (midVal > value) {
 69            hi = mid - 1;
 70        } else {
 71            return mid;  // value found
 72        }
 73    }
 74    return ~lo;  // value not present
 75}
 76
 77// android.util.SparseArray
 78private void gc() {
 79    int n = mSize;
 80    int o = 0;
 81    int[] keys = mKeys;
 82    Object[] values = mValues;
 83
 84    for (int i = 0; i < n; i++) {
 85        Object val = values[i];
 86
 87        if (val != DELETED) {
 88            if (i != o) {
 89                keys[o] = keys[i];
 90                values[o] = val;
 91                values[i] = null;
 92            }
 93
 94            o++;
 95        }
 96    }
 97
 98    mGarbage = false;
 99    mSize = o;
100}

源码中影响到 value 数组的操作有 gc 和最后在数组中插入数据。我们的场景不涉及删除，所以不会发生 gc。而且仔细想想这两步，gc 是把后面的数据搬运到被标记为删除的位置；插入元素直接生成新的数组，都不会导致某一时刻 value 数组中曾经的元素为 null。

原因

后面想想其实思路狭隘了，一直考虑的是 value 数组中某个位置的元素在某一时刻变为 null，但是上面的分析来看可能会因为线程不安全造成两次 get() 得到的值不同，但是不会出现其中一次为 null。

分析 put() 方法最后三行，可以发现 mKeys、mValues 和 mSize 都可能因为多线程执行 get() 导致出现问题，分别对应三种可能：

mKeys 未改变前其他线程 get()。
mValues 未改变前其他线程 get()。
mSize 未改变前其他线程 get()。

看一下 get() 的源码，非常简单，二分查找 index，从 mValues 数组中取值：

 1public E get(int key) {
 2    return get(key, null);
 3}
 4
 5public E get(int key, E valueIfKeyNotFound) {
 6    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
 7
 8    if (i < 0 || mValues[i] == DELETED) {
 9        return valueIfKeyNotFound;
10    } else {
11        return (E) mValues[i];
12    }
13}

为了方便演示，先假设我们的 key 取值为 0、1、2，value 对应取值为"零"、“一”、“二”，同时因为数组插入是递增的，涉及到了数组重排，所以我们假设两种场景来：

新插入的 key 比之前所有的 key 大：假设原有 [0,1] 插入 2。
新插入的 key 比之前最大的 key 小：假设原有 [0,2] 插入 1。

那么分析上述三种可能为：

mKeys 未改变前相当于还没有执行 put()。
1. 原有 [0,1] 插入 2：get(1) 会正常返回"一"；get(2) 会因为 binarySearch() 等于 -3，返回默认的 null。
2. 原有 [0,2] 插入 1：get(1) 会因为 binarySearch() 等于 -2，返回默认的 null；get(2) 会正常返回"二"。
3. 结论：不可能出现第一次 get 有值但第二次为 null 的情况。
mValues 未改变前 mKeys 已经插入了新 put 的值。
1. 原有 [0,1] 插入 2：get(1) 会正常返回"一"；get(2) 会因为 binarySearch() 等于 -3，返回默认的 null。
2. 原有 [0,2] 插入 1：get(1) 返回“二”；get(2) 会因为 mSize 未改变导致 binarySearch() 等于 -3，返回默认的 null。
3. 结论：第二种场景出现了没插入前 get(2) 有值，插入之后 get(2) 为 null 的情况。另外值得注意的是此时 get(1) 的返回值也是错误的。
mSize 未改变前 mKeys和 mValues 都插入了新 put 的值。
1. 原有 [0,1] 插入 2：get(1)会正常返回"一"；get(2) 会因为 binarySearch() 等于 -3，返回默认的 null。
2. 原有 [0,2] 插入 1：get(1)会正常返回"一"；get(2) 会因为 binarySearch() 等于 -3，返回默认的 null。
3. 结论：第二种场景出现了没插入前 get(2) 有值，插入之后 get(2) 为 null 的情况。

所以在发生重排的场景中，有可能因为多线程同时读写出现之前遇到的问题。

复现

既然知道了原因，复现代码还是很简单的：

 1AtomicBoolean noNull = new AtomicBoolean(true);
 2while (noNull.get()) {
 3    SparseArray<Object> sparseArray = new SparseArray<>();
 4    sparseArray.put(2, new Object());
 5    new Thread(() -> {
 6        if (sparseArray.get(2) == null) {
 7            Log.d("SparseArray", "get is null");
 8            noNull.set(false);
 9        }
10    }).start();
11
12    sparseArray.put(0, new Object());
13    sparseArray.put(1, new Object());
14}

自建NAS方案选型-基建篇