Android LruCache的bug

傷城~ 2022-01-14 17:11 280阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

码哒，今天无意中发现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
     * ...(略)

是说，这个版本不能使用非标准API`LinkedHashMap#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了。

转载于:https://my.oschina.net/weichou/blog/735370

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/be388422204847be9da297f3bc8e68eb.png