Android LruCache的bug

转载:弹一曲Happy颂 所写的 Android LruCache的bug

码哒,今天无意中发现Android 5.0(api level 21)之前的LruCache实现居然存在一个bug.

由于在电脑上(Java SE环境)测试code比较方便,我便将最近写在Android项目中的框架代码copy到Java项目中进行测试,然后缺少一个LruCache, 我也直接将其源码copy过来,但是报了一个错误,正是下面第一段代码中map.eldest();这句,但是这个方法由于不是Java标准API而被@hide了,我便想都不想,直接改成了遍历map并取出最后一个元素(思维定式,以为LinkedHashMap的最后一个元素就是那个eldest()的,即LRU(Least Recently Used)的),但是测试中很快发现了问题,然后在LinkedHashMap源码中找到其定义及注释,修改为取出链表的第一个元素了。

然而凑巧的是,今天下班我把代码copy到自己的本上带回家测试,再次copy这个LruCache源码的时候,发现居然没有报错,纳闷中,我去翻看那行怎么不报错,便发现了该问题。那段代码正好跟我昨天刚开始犯的错误一样,遍历最后一个元素当做LRU的,并将去驱逐。并且加了注释,大意是说:由于map.eldest();为非标准API, 所以将其修改了。

OK,看代码吧。

首先来看看正确的实现 Android 6.0(API Level 23):

	 /**
	     * Remove the eldest entries until the total of remaining entries is at or
	     * below the requested size.
	     *
	     * @param maxSize the maximum size of the cache before returning. May be -1
	     *            to evict even 0-sized elements.
	     */
	    public void trimToSize(int maxSize) {
	        while (true) {
	            K key;
	            V value;
	            synchronized (this) {
	                if (size < 0 || (map.isEmpty() && size != 0)) {
	                    throw new IllegalStateException(getClass().getName()
	                            + ".sizeOf() is reporting inconsistent results!");
	                }
	
	                if (size <= maxSize) {
	                    break;
	                }
	
	                Map.Entry<K, V> toEvict = map.eldest();
	                if (toEvict == null) {
	                    break;
	                }
	
	                key = toEvict.getKey();
	                value = toEvict.getValue();
	                map.remove(key);
	                size -= safeSizeOf(key, value);
	                evictionCount++;
	            }
	
	            entryRemoved(true, key, value, null);
	        }
	    }

其中有个map.eldest();方法,表示取出LinkedHashMap中最年长的元素,并将其驱逐。

下面来看看错误的实现 Android 5.0(API Level 21):

	/**
     * @param maxSize the maximum size of the cache before returning. May be -1
     *                to evict even 0-sized elements.
     */
    private void trimToSize(int maxSize) {
        while (true) {
            K key;
            V value;
            synchronized (this) {
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }

                if (size <= maxSize) {
                    break;
                }

                // BEGIN LAYOUTLIB CHANGE
                // get the last item in the linked list.
                // This is not efficient, the goal here is to minimize the changes
                // compared to the platform version.
                Map.Entry<K, V> toEvict = null;
                for (Map.Entry<K, V> entry : map.entrySet()) {
                    toEvict = entry;
                }
                // END LAYOUTLIB CHANGE

                if (toEvict == null) {
                    break;
                }

                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }

            entryRemoved(true, key, value, null);
        }
    }

注意其中这段以及其注释说明:

	Map.Entry<K, V> toEvict = null;
	for (Map.Entry<K, V> entry : map.entrySet()) {
	    toEvict = entry;
	}

遍历取出最后一个元素,这个正是将被驱逐的元素。同时在类说明中给了一段注释:

	import java.util.LinkedHashMap;
	import java.util.Map;
	
	/**
	 * BEGIN LAYOUTLIB CHANGE
	 * This is a custom version that doesn't use the non standard LinkedHashMap#eldest.
	 * END LAYOUTLIB CHANGE
	 * <p>
	 * A cache that holds strong references to a limited number of values. Each time
	 * a value is accessed, it is moved to the head of a queue. When a value is
	 * ...(略)

是说,这个版本不能使用非标准APILinkedHashMap#eldest.

然而这段代码经过测试,在Cache Size填满后,确实总是驱逐最后添加进去的元素。显然不符合Lru的意图。

需要注意的是,LruCache的map是这么构造的:

	this.map = new LinkedHashMap<K, V>(0, 0.75f, true);

重点在这个true, 表示任何一个操作(get, put等)都将触发重排序,将这个被操作的元素排到链表的末尾,因此末尾的是最近“频繁”使用的,而不是LRU的,那么这个取出末尾的那个元素并将其驱逐的逻辑,显然是错误的!

那么我们还是回过头来看看eldest()到底做了什么吧!

	 /**
     * Returns the eldest entry in the map, or {@code null} if the map is empty.
     * @hide
     */
    public Entry<K, V> eldest() {
        LinkedEntry<K, V> eldest = header.nxt;
        return eldest != header ? eldest : null;
    }

eldest()直接返回了header.nxt.

		public class LinkedHashMap<K, V> extends HashMap<K, V> {
    /**
     * A dummy entry in the circular linked list of entries in the map.
     * The first real entry is header.nxt, and the last is header.prv.
     * If the map is empty, header.nxt == header && header.prv == header.
     */
    transient LinkedEntry<K, V> header;

而header.nxt又是The first real entry. 意思很明确了,就是返回链表的第一个元素。

那么可以肯定Android 5.0(API Level 21)及以前对LruCache的实现就是一个bug了。

文章目录
  1. 1. 首先来看看正确的实现 Android 6.0(API Level 23):
  • 下面来看看错误的实现 Android 5.0(API Level 21):
    1. 1. 那么我们还是回过头来看看eldest()到底做了什么吧!
  • |