core/LruCache.h
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #ifndef AVS_LRUCACHE_H | ||
| 2 | #define AVS_LRUCACHE_H | ||
| 3 | |||
| 4 | #include <mutex> | ||
| 5 | #include <condition_variable> | ||
| 6 | #include <memory> | ||
| 7 | #include <cassert> | ||
| 8 | #include "ObjectPool.h" | ||
| 9 | #include "SimpleLruCache.h" | ||
| 10 | #include "InternalEnvironment.h" | ||
| 11 | |||
| 12 | enum LruLookupResult | ||
| 13 | { | ||
| 14 | LRU_LOOKUP_NOT_FOUND, // Item has not been found, storage is reserved to be used by caller | ||
| 15 | LRU_LOOKUP_FOUND_AND_READY, // Item has been found and returned | ||
| 16 | LRU_LOOKUP_FOUND_BUT_NOTAVAIL, // Item has been found, but is waiting for completion and is not yet ready | ||
| 17 | LRU_LOOKUP_NO_CACHE // Item will not be cached, no storage is returned | ||
| 18 | }; | ||
| 19 | |||
| 20 | template<typename K, typename V> | ||
| 21 | class LruCache : public std::enable_shared_from_this<LruCache<K, V> > | ||
| 22 | { | ||
| 23 | private: | ||
| 24 | enum LruEntryState | ||
| 25 | { | ||
| 26 | LRU_ENTRY_EMPTY, | ||
| 27 | LRU_ENTRY_AVAILABLE, | ||
| 28 | LRU_ENTRY_ROLLED_BACK | ||
| 29 | }; | ||
| 30 | |||
| 31 | struct LruGhostEntry | ||
| 32 | { | ||
| 33 | K key; | ||
| 34 | size_t ghosted; | ||
| 35 | |||
| 36 | 5 | LruGhostEntry() : | |
| 37 | 5 | key(0), ghosted(0) | |
| 38 | { | ||
| 39 | 5 | } | |
| 40 | |||
| 41 | 5 | LruGhostEntry(K key, size_t ghosted) : | |
| 42 | 5 | key(key), ghosted(ghosted) | |
| 43 | { | ||
| 44 | 5 | } | |
| 45 | }; | ||
| 46 | |||
| 47 | struct LruEntry | ||
| 48 | { | ||
| 49 | K key; | ||
| 50 | V value; | ||
| 51 | size_t locks; // the number of threads waiting on this entry. used to prevent eviction when readers are waiting on it | ||
| 52 | size_t ghosted; // the number of times this entry has entered the ghost list | ||
| 53 | std::condition_variable ready_cond; | ||
| 54 | enum LruEntryState state; | ||
| 55 | |||
| 56 | ✗ | LruEntry(const K& key) | |
| 57 | ✗ | { | |
| 58 | ✗ | reset(key, V()); | |
| 59 | ✗ | } | |
| 60 | |||
| 61 | ✗ | void reset(const K& k, const V& v) | |
| 62 | { | ||
| 63 | ✗ | key = k; | |
| 64 | ✗ | value = v; | |
| 65 | ✗ | locks = 0; | |
| 66 | ✗ | ghosted = 0; | |
| 67 | ✗ | state = LRU_ENTRY_EMPTY; | |
| 68 | ✗ | } | |
| 69 | |||
| 70 | private: | ||
| 71 | LruEntry(const LruEntry&); | ||
| 72 | LruEntry& operator=(const LruEntry&); | ||
| 73 | }; | ||
| 74 | |||
| 75 | const int GHOSTS_MIN_CAPACITY; | ||
| 76 | typedef LruEntry entry_type; | ||
| 77 | typedef entry_type* entry_ptr; | ||
| 78 | typedef SimpleLruCache<K, entry_ptr> CacheType; | ||
| 79 | typedef SimpleLruCache<K, LruGhostEntry> GhostCacheType; | ||
| 80 | |||
| 81 | typedef size_t size_type; | ||
| 82 | |||
| 83 | CacheMode mode; | ||
| 84 | CacheType MainCache; | ||
| 85 | GhostCacheType Ghosts; | ||
| 86 | ObjectPool<entry_type> EntryPool; | ||
| 87 | mutable std::mutex mutex; | ||
| 88 | |||
| 89 | ✗ | static bool MainEvictEvent(CacheType* cache, const typename CacheType::Entry& entry, void* userData) | |
| 90 | { | ||
| 91 | ✗ | if (entry.value->locks > 0) | |
| 92 | ✗ | return false; | |
| 93 | |||
| 94 | ✗ | LruCache* me = reinterpret_cast<LruCache*>(userData); | |
| 95 | |||
| 96 | bool ghost_found; | ||
| 97 | ✗ | auto *g = me->Ghosts.lookup(entry.key, &ghost_found); | |
| 98 | ✗ | if (!ghost_found) | |
| 99 | { | ||
| 100 | ✗ | *g = LruGhostEntry(entry.key, entry.value->ghosted + 1); | |
| 101 | } | ||
| 102 | else | ||
| 103 | { | ||
| 104 | ✗ | g->ghosted++; | |
| 105 | } | ||
| 106 | |||
| 107 | ✗ | entry.value->reset(0, NULL); | |
| 108 | ✗ | me->EntryPool.Destruct(entry.value); | |
| 109 | ✗ | return true; | |
| 110 | } | ||
| 111 | |||
| 112 | public: | ||
| 113 | |||
| 114 | typedef std::pair<entry_ptr, std::shared_ptr<LruCache> > handle; | ||
| 115 | |||
| 116 | 5 | LruCache(size_type capacity, CacheMode mode) : | |
| 117 | 5 | GHOSTS_MIN_CAPACITY(50), | |
| 118 | 5 | mode(mode), | |
| 119 |
1/2✓ Branch 4 → 5 taken 5 times.
✗ Branch 4 → 12 not taken.
|
5 | MainCache(capacity, &MainEvictEvent, reinterpret_cast<void*>(this)), |
| 120 |
1/2✓ Branch 7 → 8 taken 5 times.
✗ Branch 7 → 16 not taken.
|
10 | Ghosts(GHOSTS_MIN_CAPACITY, typename GhostCacheType::EvictEventType(), reinterpret_cast<void*>(this)) |
| 121 | { | ||
| 122 | 5 | } | |
| 123 | |||
| 124 | ✗ | size_type size() const | |
| 125 | { | ||
| 126 | ✗ | return MainCache.size(); | |
| 127 | } | ||
| 128 | |||
| 129 | 5 | size_t requested_capacity() const | |
| 130 | { | ||
| 131 | 5 | return MainCache.requested_capacity(); | |
| 132 | } | ||
| 133 | |||
| 134 | 5 | size_t capacity() const | |
| 135 | { | ||
| 136 | 5 | return MainCache.capacity(); | |
| 137 | } | ||
| 138 | |||
| 139 | ✗ | void limits(size_t* min, size_t* max) const | |
| 140 | { | ||
| 141 | ✗ | std::unique_lock<std::mutex> global_lock(mutex); | |
| 142 | |||
| 143 | ✗ | MainCache.limits(min, max); | |
| 144 | ✗ | } | |
| 145 | |||
| 146 | ✗ | void set_limits(size_t min, size_t max) | |
| 147 | { | ||
| 148 | ✗ | std::unique_lock<std::mutex> global_lock(mutex); | |
| 149 | |||
| 150 | ✗ | MainCache.set_limits(min, max); | |
| 151 | ✗ | } | |
| 152 | |||
| 153 | 5 | LruLookupResult lookup(const K& key, handle *hndl, bool block_for_completion, V& foundItem, bool* suppressCaching = nullptr) | |
| 154 | { | ||
| 155 |
2/4✓ Branch 2 → 3 taken 5 times.
✗ Branch 2 → 5 not taken.
✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 5 times.
|
5 | bool suppress = (suppressCaching != nullptr) && *suppressCaching; |
| 156 | 5 | hndl->first = nullptr; // clear handle | |
| 157 | |||
| 158 |
1/2✓ Branch 6 → 7 taken 5 times.
✗ Branch 6 → 71 not taken.
|
5 | std::unique_lock<std::mutex> global_lock(mutex); |
| 159 | |||
| 160 | bool found; | ||
| 161 |
1/2✓ Branch 7 → 8 taken 5 times.
✗ Branch 7 → 69 not taken.
|
5 | entry_ptr* entryp = MainCache.lookup(key, &found, suppress); |
| 162 | |||
| 163 |
1/2✗ Branch 8 → 9 not taken.
✓ Branch 8 → 29 taken 5 times.
|
5 | if (found) |
| 164 | { | ||
| 165 | ✗ | entry_ptr entry = *entryp; | |
| 166 | |||
| 167 | ✗ | if (!block_for_completion && (entry->state != LRU_ENTRY_AVAILABLE)) | |
| 168 | { | ||
| 169 | ✗ | return LRU_LOOKUP_FOUND_BUT_NOTAVAIL; | |
| 170 | } | ||
| 171 | |||
| 172 | // wait until data becomes available | ||
| 173 | ✗ | ++(entry->locks); | |
| 174 | ✗ | while (entry->state == LRU_ENTRY_EMPTY) | |
| 175 | { | ||
| 176 | ✗ | entry->ready_cond.wait(global_lock); | |
| 177 | |||
| 178 | ✗ | switch (entry->state) | |
| 179 | { | ||
| 180 | ✗ | case LRU_ENTRY_EMPTY: // do nothing, spurious wakeup | |
| 181 | ✗ | break; | |
| 182 | ✗ | case LRU_ENTRY_AVAILABLE: // finally, data available | |
| 183 | ✗ | break; | |
| 184 | ✗ | case LRU_ENTRY_ROLLED_BACK: // whoever we were waiting for decided to step back. we take over his place. | |
| 185 | ✗ | entry->state = LRU_ENTRY_EMPTY; | |
| 186 | ✗ | *hndl = handle(entry, this->shared_from_this()); | |
| 187 | ✗ | return LRU_LOOKUP_NOT_FOUND; | |
| 188 | ✗ | default: | |
| 189 | ✗ | assert(0); | |
| 190 | } | ||
| 191 | } | ||
| 192 | // copy and return entry->value before releasing lock | ||
| 193 | ✗ | foundItem = entry->value; | |
| 194 | ✗ | --(entry->locks); | |
| 195 | ✗ | return LRU_LOOKUP_FOUND_AND_READY; | |
| 196 | } | ||
| 197 |
1/2✓ Branch 29 → 30 taken 5 times.
✗ Branch 29 → 56 not taken.
|
5 | else if (suppress == false) |
| 198 | { | ||
| 199 | // ghost: self-tuning caching algorithm | ||
| 200 | bool ghost_found; | ||
| 201 |
1/2✓ Branch 30 → 31 taken 5 times.
✗ Branch 30 → 68 not taken.
|
5 | auto *g = Ghosts.lookup(key, &ghost_found); |
| 202 |
1/2✗ Branch 31 → 32 not taken.
✓ Branch 31 → 33 taken 5 times.
|
5 | assert(g != NULL); |
| 203 |
1/2✓ Branch 33 → 34 taken 5 times.
✗ Branch 33 → 36 not taken.
|
5 | if (!ghost_found) |
| 204 | { | ||
| 205 | 5 | *g = LruGhostEntry(key, 0); | |
| 206 | } | ||
| 207 | ✗ | else if (g->ghosted > 1) | |
| 208 | { | ||
| 209 | // Fix for Issues #270 and #379: require a frame to have been evicted | ||
| 210 | // at least twice (ghosted > 1) before triggering a cache resize. | ||
| 211 | // | ||
| 212 | // With the old condition (ghosted > 0), any single eviction + re-request | ||
| 213 | // caused a +1 resize. This led to unbounded cache growth in two cases: | ||
| 214 | // | ||
| 215 | // 1. Backward seeking (Issue #379): frames played forward get evicted and | ||
| 216 | // ghosted=1. Every backstep hits a ghost (1 > 0 was true) → +1 on each | ||
| 217 | // step. | ||
| 218 | // | ||
| 219 | // 2. Bob()/SeparateFields access pattern (Issue #270): the n, n/2 pattern | ||
| 220 | // keeps evicting the same frames with ghosted=1, so every GetFrame call | ||
| 221 | // triggered a resize. | ||
| 222 | // Infinite cache growth occured when the requested frame number pattern from | ||
| 223 | // source filter is something like that: | ||
| 224 | // 0,0, 0,1, 1,2, 1,3, 2,4, 2,5, 3,6, 3,7, 4,8,... | ||
| 225 | // Sample script: | ||
| 226 | // ConvertToY8() | ||
| 227 | // org = last | ||
| 228 | // Bob() | ||
| 229 | // Merge(last, org) | ||
| 230 | // With ghosted > 1: both cases are suppressed because frames evicted only | ||
| 231 | // once stay at ghosted=1 (1 > 1 is false). An undersized cache | ||
| 232 | // still grows: frames that keep cycling will be evicted a second time, | ||
| 233 | // pushing ghosted to 2, and growth resumes from that point forward. | ||
| 234 | ✗ | if (mode != CACHE_NO_RESIZE) { | |
| 235 | #ifdef CACHE_GROWTH_INFINITELY_TEST | ||
| 236 | // When the above (g->ghosted > 1) was (g->ghosted > 0) | ||
| 237 | _RPT1(0, "Not in cache but in ghost! g->ghosted > 0 => resize! MainCache.capacity()=%d -> += 1", MainCache.capacity() + 1); | ||
| 238 | #endif | ||
| 239 | ✗ | MainCache.resize(MainCache.capacity() + 1); | |
| 240 | ✗ | Ghosts.resize(GHOSTS_MIN_CAPACITY + MainCache.capacity() * 2); | |
| 241 | } | ||
| 242 | |||
| 243 | // Nekopanda: reduce amount of cache. | ||
| 244 | // when this filter increased the cache, we prevent lower filters increase their cache | ||
| 245 | // because the requests to the lower filters were not needed if this filter cached the frame. | ||
| 246 | ✗ | if (mode == CACHE_OPTIMAL_SIZE && suppressCaching != nullptr) { | |
| 247 | ✗ | *suppressCaching = true; | |
| 248 | } | ||
| 249 | } | ||
| 250 | else | ||
| 251 | { | ||
| 252 | // This cannot happen | ||
| 253 | //assert(0); LOL maybe it can... | ||
| 254 | } | ||
| 255 | |||
| 256 |
1/2✗ Branch 45 → 46 not taken.
✓ Branch 45 → 54 taken 5 times.
|
5 | if (entryp != NULL) |
| 257 | { | ||
| 258 | ✗ | *entryp = EntryPool.Construct(key); | |
| 259 | ✗ | entry_ptr entry = *entryp; | |
| 260 | ✗ | *hndl = handle(entry, this->shared_from_this()); | |
| 261 | ✗ | entry->locks = 1; | |
| 262 | ✗ | entry->ghosted = g->ghosted; | |
| 263 | ✗ | entry->value = NULL; | |
| 264 | ✗ | return LRU_LOOKUP_NOT_FOUND; | |
| 265 | } | ||
| 266 | else | ||
| 267 | { | ||
| 268 | 5 | g->ghosted++; | |
| 269 | 5 | return LRU_LOOKUP_NO_CACHE; | |
| 270 | } | ||
| 271 | } // if | ||
| 272 | else { | ||
| 273 | ✗ | assert(entryp == nullptr); | |
| 274 | ✗ | return LRU_LOOKUP_NO_CACHE; | |
| 275 | } | ||
| 276 | 5 | } | |
| 277 | |||
| 278 | ✗ | void commit_value(handle *hndl) | |
| 279 | { | ||
| 280 | ✗ | std::unique_lock<std::mutex> global_lock(mutex); | |
| 281 | |||
| 282 | // mark data as ready | ||
| 283 | ✗ | entry_ptr e = hndl->first; | |
| 284 | ✗ | e->state = LRU_ENTRY_AVAILABLE; | |
| 285 | ✗ | --(e->locks); | |
| 286 | |||
| 287 | // notify waiters | ||
| 288 | ✗ | global_lock.unlock(); | |
| 289 | ✗ | e->ready_cond.notify_all(); | |
| 290 | |||
| 291 | ✗ | hndl->second.reset(); | |
| 292 | ✗ | } | |
| 293 | |||
| 294 | ✗ | void rollback(handle *hndl) | |
| 295 | { | ||
| 296 | ✗ | std::unique_lock<std::mutex> global_lock(mutex); | |
| 297 | |||
| 298 | ✗ | entry_ptr e = hndl->first; | |
| 299 | ✗ | assert(e->locks > 0); | |
| 300 | |||
| 301 | ✗ | if (e->locks == 1) | |
| 302 | { | ||
| 303 | ✗ | MainCache.remove(e->key); | |
| 304 | } | ||
| 305 | else | ||
| 306 | { | ||
| 307 | // others have started waiting for this data, so another one will have to take over | ||
| 308 | ✗ | --(e->locks); | |
| 309 | ✗ | e->state = LRU_ENTRY_ROLLED_BACK; | |
| 310 | |||
| 311 | // notify one waiter | ||
| 312 | ✗ | global_lock.unlock(); | |
| 313 | ✗ | e->ready_cond.notify_one(); | |
| 314 | } | ||
| 315 | |||
| 316 | ✗ | hndl->second.reset(); | |
| 317 | ✗ | } | |
| 318 | }; | ||
| 319 | |||
| 320 | #endif // AVS_LRUCACHE_H | ||
| 321 |