1 //
2 // Copyright 2017 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6 // SizedMRUCache.h: A hashing map that stores blobs of sized, untyped data.
7
8 #ifndef LIBANGLE_SIZED_MRU_CACHE_H_
9 #define LIBANGLE_SIZED_MRU_CACHE_H_
10
11 #include <anglebase/containers/mru_cache.h>
12 #include "common/third_party/smhasher/src/PMurHash.h"
13
14 namespace angle
15 {
16
17 template <typename Key, typename Value>
18 class SizedMRUCache final : angle::NonCopyable
19 {
20 public:
SizedMRUCache(size_t maximumTotalSize)21 SizedMRUCache(size_t maximumTotalSize)
22 : mMaximumTotalSize(maximumTotalSize),
23 mCurrentSize(0),
24 mStore(SizedMRUCacheStore::NO_AUTO_EVICT)
25 {
26 }
27
28 // Returns nullptr on failure.
put(const Key & key,Value && value,size_t size)29 const Value *put(const Key &key, Value &&value, size_t size)
30 {
31 if (size > mMaximumTotalSize)
32 {
33 return nullptr;
34 }
35
36 // Check for existing key.
37 eraseByKey(key);
38
39 auto retVal = mStore.Put(key, ValueAndSize(std::move(value), size));
40 mCurrentSize += size;
41
42 shrinkToSize(mMaximumTotalSize);
43
44 return &retVal->second.value;
45 }
46
get(const Key & key,const Value ** valueOut)47 bool get(const Key &key, const Value **valueOut)
48 {
49 const auto &iter = mStore.Get(key);
50 if (iter == mStore.end())
51 {
52 return false;
53 }
54 *valueOut = &iter->second.value;
55 return true;
56 }
57
getAt(size_t index,Key * keyOut,const Value ** valueOut)58 bool getAt(size_t index, Key *keyOut, const Value **valueOut)
59 {
60 if (index < mStore.size())
61 {
62 auto it = mStore.begin();
63 std::advance(it, index);
64 *keyOut = it->first;
65 *valueOut = &it->second.value;
66 return true;
67 }
68 *valueOut = nullptr;
69 return false;
70 }
71
empty()72 bool empty() const { return mStore.empty(); }
73
clear()74 void clear()
75 {
76 mStore.Clear();
77 mCurrentSize = 0;
78 }
79
eraseByKey(const Key & key)80 bool eraseByKey(const Key &key)
81 {
82 // Check for existing key.
83 auto existing = mStore.Peek(key);
84 if (existing != mStore.end())
85 {
86 mCurrentSize -= existing->second.size;
87 mStore.Erase(existing);
88 return true;
89 }
90
91 return false;
92 }
93
entryCount()94 size_t entryCount() const { return mStore.size(); }
95
size()96 size_t size() const { return mCurrentSize; }
97
98 // Also discards the cache contents.
resize(size_t maximumTotalSize)99 void resize(size_t maximumTotalSize)
100 {
101 clear();
102 mMaximumTotalSize = maximumTotalSize;
103 }
104
105 // Reduce current memory usage.
shrinkToSize(size_t limit)106 size_t shrinkToSize(size_t limit)
107 {
108 size_t initialSize = mCurrentSize;
109
110 while (mCurrentSize > limit)
111 {
112 ASSERT(!mStore.empty());
113 auto iter = mStore.rbegin();
114 mCurrentSize -= iter->second.size;
115 mStore.Erase(iter);
116 }
117
118 return (initialSize - mCurrentSize);
119 }
120
maxSize()121 size_t maxSize() const { return mMaximumTotalSize; }
122
123 private:
124 struct ValueAndSize
125 {
ValueAndSizeValueAndSize126 ValueAndSize() : value(), size(0) {}
ValueAndSizeValueAndSize127 ValueAndSize(Value &&value, size_t size) : value(std::move(value)), size(size) {}
ValueAndSizeValueAndSize128 ValueAndSize(ValueAndSize &&other) : ValueAndSize() { *this = std::move(other); }
129 ValueAndSize &operator=(ValueAndSize &&other)
130 {
131 std::swap(value, other.value);
132 std::swap(size, other.size);
133 return *this;
134 }
135
136 Value value;
137 size_t size;
138 };
139
140 using SizedMRUCacheStore = base::HashingMRUCache<Key, ValueAndSize>;
141
142 size_t mMaximumTotalSize;
143 size_t mCurrentSize;
144 SizedMRUCacheStore mStore;
145 };
146
147 // Helper function used in a few places.
148 template <typename T>
TrimCache(size_t maxStates,size_t gcLimit,const char * name,T * cache)149 void TrimCache(size_t maxStates, size_t gcLimit, const char *name, T *cache)
150 {
151 const size_t kGarbageCollectionLimit = maxStates / 2 + gcLimit;
152
153 if (cache->size() >= kGarbageCollectionLimit)
154 {
155 WARN() << "Overflowed the " << name << " cache limit of " << (maxStates / 2)
156 << " elements, removing the least recently used to make room.";
157 cache->ShrinkToSize(maxStates / 2);
158 }
159 }
160
161 // Computes a hash of struct "key". Any structs passed to this function must be multiples of
162 // 4 bytes, since the PMurhHas32 method can only operate increments of 4-byte words.
163 template <typename T>
ComputeGenericHash(const T & key)164 std::size_t ComputeGenericHash(const T &key)
165 {
166 static const unsigned int seed = 0xABCDEF98;
167
168 // We can't support "odd" alignments.
169 static_assert(sizeof(key) % 4 == 0, "ComputeGenericHash requires aligned types");
170 return PMurHash32(seed, &key, sizeof(T));
171 }
172
173 } // namespace angle
174 #endif // LIBANGLE_SIZED_MRU_CACHE_H_
175