Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?

ArrayMap ClassCastException Deep Analyze

preface

I'm a developer of 企鹅FM. Our app constantly report ClassCastException on ArrayMap, some stack trace looks like this.

Intent i = new Intent(ACTION);
i.putExtra(KEY, VALUE); // crashes here

Just incredible.

Conclusion

  1. A buggy program uses ArrayMap without proper synchronization causing data stored in ArrayMap being corrupted.
  2. ArrayMap has a Memory Pool, which stores that corrupted data, causing anyone obtaining data from that pool crashes!

So the very cause of the issue is a program using ArrayMap (or Intent, Bundle, etc... which is backed by ArrayMap) with thread issue(s).

And the bad design of the memory pool in ArrayMap causing anyone uses it may crash. (propagated error) Besides, it is hard to find out who is using ArrayMap improperly only according to the crash stack trace.

Short Analyze

ArrayMap is designed to be memory efficient. It has a memory pool caches short Object[] array. When a new array is obtained, ArrayMap first tries to obtain one from the memory pool. And when an array is abandoned AM tries to put it in the memory pool as long as the pool is not full (10 at most).

And the reason is multi-thread manipulation of the same ArrayMap.

Assume we have an ArrayMap, say am.

  • am recycle an array to the memory pool.
  • just before the recycle is complete, another thread use am set some value to array[0].

then the array in the memory pool is corrupted!

Anyone obtains an array from the memory pool will crash!

Deep Analyze

DataStructure of ArrayMap

public final class ArrayMap<K, V> {
    // memory pool, array reference is guard by ArrayMap.class
    // but the content of the array is not guarded!
    static Object[] mBaseCache;
    static int mBaseCacheSize;

    int[] mHashes;
    // holds data in arrayMap, not guarded by anything in ArrayMap
    // code 0, more info in later this article
    Object[] mArray;

    // write operation
     public void put(K key, V value) {
        //..
        mArray[index] = value;
        //...
    }
}

recycle array to memory pool

// mArray is passed in as array
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
    if (hashes.length == BASE_SIZE) {
        synchronized (android.util.ArrayMap.class) {
            if (mBaseCacheSize < CACHE_SIZE) {
                // code 1, more info in later this article
                array[0] = mBaseCache;
                array[1] = hashes;
                for (int i = (size << 1) - 1; i >= 2; i--) {
                    array[i] = null;
                }
                // code 2, more info in later this article
                mBaseCache = array;
                mBaseCacheSize++;
            }
        }
    }
}

code 0

The parameter array is always the mArray field of an ArrayMap. This is the array used to keep data, in ArrayMap, similar to HashMap. Each time this array needs to grow, it first called freeArray to check if the old array can be put in the memory pool.

code 1

mBaseCache stores as much as 10 arrays, arranged as a Singly Linked List. the array[0] is a reference/pointer to the next element, and array[1] is some payload (which we can ignore).

code 2

Make current array as the head of Link List, and assume this array will not be touched until it been polled from the memory pool.

poll from the memory pool

 private void allocArrays(final int size) {
    if (size == BASE_SIZE) {
        synchronized (android.util.ArrayMap.class) {
            if (mBaseCache != null) {
                final Object[] array = mBaseCache;
                mArray = array;
                mBaseCache = (Object[]) array[0]; // code 3
                mHashes = (int[]) array[1];
                array[0] = array[1] = null;
                mBaseCacheSize--;
                return;
            }
        }
    }
}

code 3

This is where most crash happens! I've seen all kind classes cast to Object[] when crash.

In terms of Singly Linked List as described above, the array[0] is a reference/pointer to next element, so what this code does is:

  1. poll one element from the linked list
  2. make it head be the next element

crash scenerio

1. CORRUPT the Memory Pool

We explain the conclusion again with some code.

We still assume an ArrayMap is ben used in multi-thread without synchronization.

  1. "Thread one" is running at freeArrays, putting an array, say am.mArray, to the memory pool, and has run after "code 1" and just before "code 2".
  2. At the same time, "thread two" operates 'am', putting something to am.mArray[0]

So the array in memory pool is corrupted! The first element is supposed to be next element of the Singly Linked List, but it's now something else been put int thread-2.

2. pool data from the memory pool

After the corruption happened, and no one will realize that.

At some time in the future, an ArrayMap (maybe still am) happily polled an array from the memory pool. Then it will crash as we analyzed in code3.

How to fix this issue

There is no good way to avoid corruption, without making the WHOLE ArrayMap thread safe.

The best way I preferred is to avoid any kind of memory pool since JVM and GC is the best memory pool!

I DO WISH THIS BUG FIX WILL BE RELEASED TOGETHER WITH ANDROID O.

How to reproduce this crash

Just following the conclusion, we came up with this demo. It will crash with a ClassCastException after a short time.

    private void arrayMapClassCastExceptionDemo() {
        final ArrayMap<String, String> criminal = new ArrayMap<>();
        final ArrayMap<String, String> victim = new ArrayMap<>();

        new Thread(() -> {
            while (true) {
                try {
                    if (criminal.size() >= 8) {
                        // trigger freeArrays
                        criminal.clear();
                    }
                } catch (IndexOutOfBoundsException ingnore) {
                    // multi thread issue
                    continue;
                }
            }
        }, "criminal-thread-0").start();

        new Thread(() -> {
            // may corrupt ArrayMap
            while (true) {
                try {
                    // may crash here
                    criminal.put("" + System.currentTimeMillis(), "");
                } catch (ArrayIndexOutOfBoundsException e) {
                    // ignore
                }
            }
        }, "criminal-thread-1").start();

        new Thread(() -> {
            while (true) {
                // poll array from memory pool
                victim.put("x", ""); // may crash here
                victim.clear();
            }
        }, "victim").start();
    }
@cutler

This comment has been minimized.

Show comment
Hide comment
@cutler

cutler May 4, 2017

can you speek in chinese? ok? brother!

cutler commented May 4, 2017

can you speek in chinese? ok? brother!

@ryecrow

This comment has been minimized.

Show comment
Hide comment
@ryecrow

ryecrow May 12, 2017

@cutler
Such an analysis is beneficial to developers around the world, not only to Chinese developers like us. So the usage of English is a better option as it is more widely used than Chinese.

ryecrow commented May 12, 2017

@cutler
Such an analysis is beneficial to developers around the world, not only to Chinese developers like us. So the usage of English is a better option as it is more widely used than Chinese.

@dkmeteor

This comment has been minimized.

Show comment
Hide comment
@dkmeteor

dkmeteor May 19, 2017

Great work.

dkmeteor commented May 19, 2017

Great work.

@dbof10

This comment has been minimized.

Show comment
Hide comment
@dbof10

dbof10 May 10, 2018

Thank you

dbof10 commented May 10, 2018

Thank you

@JeffyLi1991

This comment has been minimized.

Show comment
Hide comment
@JeffyLi1991

JeffyLi1991 May 18, 2018

最后的复现方式,我试了很久,没有复现。你那边什么系统版本,能稳定复现吗?

JeffyLi1991 commented May 18, 2018

最后的复现方式,我试了很久,没有复现。你那边什么系统版本,能稳定复现吗?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment