Android LruCache 的 Bug

原创
2016/08/20 04:17
阅读数 1.2W

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

由于在电脑上(Java SE环境,非手机上)测试code比较方便,我便将最近写在Android项目中的框架代码copy到Java项目中进行测试,然后缺少一个LruCache, 我也直接将其源码复制过来,但是报了一个错误,正是下面第一段代码中map.eldest();这句,但是这个方法由于不是Java标准API而被@hide了,我便想也没想,直接改成了遍历map并取出最后一个元素(思维定式,以为LinkedHashMap的最后一个元素就是那个eldest()的,即LRU的),但是测试中很快发现了问题,然后在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。然而紧接着的一句话:

Each time a value is accessed, it is moved to the head of a queue.
每次访问一个值时,它都会被移动到队列的head(意思是说head是 most-recently,不是 least-recently)。

就说错了,有LinkedHashMap的文档为证:

 * A special {@link #LinkedHashMap(int,float,boolean) constructor} is
 * provided to create a linked hash map whose order of iteration is the order
 * in which its entries were last accessed, from least-recently accessed to
 * most-recently (<i>access-order</i>).  This kind of map is well-suited to
 * building LRU caches.

从“较远的近”(最近最少访问)到“极为最近”排序,说明head是“较远的近”,是 least-recently,是eldest

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

需要注意的是,LruCache的map是这么构造的:this.map = new LinkedHashMap<K, V>(0, 0.75f, true);,重点在这个true, 表示任何一个操作(get, put等)都将触发重排序,将这个被操作的元素排到链表的末尾,因此末尾的是最近“频繁”使用的,而不是 LRU(Least Recently Used)最近“最少”使用的,那么这个取出末尾的那个元素并将其驱逐的逻辑,显然是错误的!

那么我们还是回过头来看看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了。
展开阅读全文
加载中

作者的其它热门文章

打赏
6
17 收藏
分享
打赏
6 评论
17 收藏
6
分享
返回顶部
顶部