GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/lru.h
Date: 2024-04-21 02:33:16
Exec Total Coverage
Lines: 321 325 98.8%
Branches: 135 246 54.9%
Line Branch Exec Source
1 /**
2 * This file is part of the CernVM File System.
3 *
4 * This class provides an Least Recently Used (LRU) cache for arbitrary data
5 * It stores Key-Value pairs of arbitrary data types in a hash table and
6 * automatically deletes the entries which are least touched in the last time
7 * to prevent the structure from growing beyond a given maximal cache size.
8 * The cache uses a hand crafted memory allocator to use memory efficiently
9 *
10 * Hash functions have to be provided. They should return an equal distribution
11 * of keys in uint32_t. In addition, a special key has to be provided that is
12 * used to mark "empty" elements in the hash table.
13 *
14 * The cache size has to be a multiply of 64.
15 *
16 * usage:
17 * // 100 entries, -1 special key
18 * LruCache<int, string> cache(100, -1, hasher_int);
19 *
20 * // Inserting some stuff
21 * cache.insert(42, "fourtytwo");
22 * cache.insert(2, "small prime number");
23 * cache.insert(1337, "leet");
24 *
25 * // Trying to retrieve a value
26 * int result;
27 * if (cache.lookup(21, result)) {
28 * cout << "cache hit: " << result << endl;
29 * } else {
30 * cout << "cache miss" << endl;
31 * }
32 *
33 * cache.drop(); // Empty the cache
34 */
35
36 #ifndef CVMFS_LRU_H_
37 #define CVMFS_LRU_H_
38
39 // If defined the cache is secured by a posix mutex
40 #define LRU_CACHE_THREAD_SAFE
41
42 #include <stdint.h>
43
44 #include <algorithm>
45 #include <cassert>
46 #include <cstring>
47 #include <functional>
48 #include <map>
49 #include <string>
50
51 #include "smallhash.h"
52 #include "statistics.h"
53 #include "util/atomic.h"
54 #include "util/platform.h"
55 #include "util/single_copy.h"
56 #include "util/smalloc.h"
57
58 namespace lru {
59
60 /**
61 * Counting of cache operations.
62 */
63 struct Counters {
64 perf::Counter *sz_size;
65 perf::Counter *n_hit;
66 perf::Counter *n_miss;
67 perf::Counter *n_insert;
68 perf::Counter *n_insert_negative;
69 uint64_t num_collisions;
70 uint32_t max_collisions;
71 perf::Counter *n_update;
72 perf::Counter *n_update_value;
73 perf::Counter *n_replace;
74 perf::Counter *n_forget;
75 perf::Counter *n_drop;
76 perf::Counter *sz_allocated;
77
78 129 explicit Counters(perf::StatisticsTemplate statistics) {
79
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 sz_size = statistics.RegisterTemplated("sz_size", "Total size");
80 129 num_collisions = 0;
81 129 max_collisions = 0;
82
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 n_hit = statistics.RegisterTemplated("n_hit", "Number of hits");
83
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 n_miss = statistics.RegisterTemplated("n_miss", "Number of misses");
84
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 n_insert = statistics.RegisterTemplated("n_insert", "Number of inserts");
85
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 n_insert_negative = statistics.RegisterTemplated("n_insert_negative",
86 "Number of negative inserts");
87
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 n_update = statistics.RegisterTemplated("n_update",
88 "Number of updates");
89
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 n_update_value = statistics.RegisterTemplated("n_update_value",
90 "Number of value changes");
91
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 n_replace = statistics.RegisterTemplated("n_replace", "Number of replaces");
92
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 n_forget = statistics.RegisterTemplated("n_forget", "Number of forgets");
93
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 n_drop = statistics.RegisterTemplated("n_drop", "Number of drops");
94
3/6
✓ Branch 2 taken 129 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 129 times.
✗ Branch 10 not taken.
 129 sz_allocated = statistics.RegisterTemplated("sz_allocated",
95 "Number of allocated bytes ");
96 129 }
97 };
98
99
100 /**
101 * Template class to create a LRU cache
102 * @param Key type of the key values
103 * @param Value type of the value values
104 */
105 template<class Key, class Value>
106 class LruCache : SingleCopy {
107 private:
108 // Forward declarations of private internal data structures
109 template<class T> class ListEntry;
110 template<class T> class ListEntryHead;
111 template<class T> class ListEntryContent;
112 template<class M> class MemoryAllocator;
113
114 // Helpers to get the template magic right
115 typedef ListEntryContent<Key> ConcreteListEntryContent;
116 typedef MemoryAllocator<ConcreteListEntryContent> ConcreteMemoryAllocator;
117
118 /**
119 * This structure wraps the user data and relates it to the LRU list entry
120 */
121 typedef struct {
122 ListEntryContent<Key> *list_entry;
123 Value value;
124 } CacheEntry;
125
126 // static uint64_t GetEntrySize() { return sizeof(Key) + sizeof(Value); }
127
128 /**
129 * A special purpose memory allocator for the cache entries.
130 * It allocates enough memory for the maximal number of cache entries at
131 * startup, and assigns new ListEntryContent objects to a free spot in this
132 * memory pool (by overriding the 'new' and 'delete' operators of
133 * ListEntryContent).
134 *
135 * @param T the type of object to be allocated by this MemoryAllocator
136 */
137 template<class T> class MemoryAllocator : SingleCopy {
138 public:
139 /**
140 * Creates a MemoryAllocator to handle a memory pool for objects of type T
141 * @param num_slots the number of slots to be allocated for the given datatype T
142 */
143 184 explicit MemoryAllocator(const unsigned int num_slots) {
144 // how many bitmap chunks (chars) do we need?
145 184 unsigned int num_bytes_bitmap = num_slots / 8;
146 184 bits_per_block_ = 8 * sizeof(bitmap_[0]);
147
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 129 times.
 184 assert((num_slots % bits_per_block_) == 0);
148
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 129 times.
 184 assert(num_slots >= 2*bits_per_block_);
149
150 // How much actual memory do we need?
151 184 const unsigned int num_bytes_memory = sizeof(T) * num_slots;
152
153 // Allocate zero'd memory
154 184 bitmap_ = reinterpret_cast<uint64_t *>(scalloc(num_bytes_bitmap, 1));
155 184 memory_ = reinterpret_cast<T *>(scalloc(num_bytes_memory, 1));
156
157 // Create initial state
158 184 num_slots_ = num_slots;
159 184 num_free_slots_ = num_slots;
160 184 next_free_slot_ = 0;
161 184 bytes_allocated_ = num_bytes_bitmap + num_bytes_memory;
162 184 }
163
164 /**
165 * Number of bytes for a single entry
166 */
167 96 static double GetEntrySize() {
168 96 return static_cast<double>(sizeof(T)) + 1.0/8.0;
169 }
170
171 /**
172 * The memory allocator also frees all allocated data
173 */
174 258 virtual ~MemoryAllocator() {
175 258 free(bitmap_);
176 258 free(memory_);
177 }
178
179 /**
180 * Check if the memory pool is full.
181 * @return true if all slots are occupied, otherwise false
182 */
183 8638 inline bool IsFull() const { return num_free_slots_ == 0; }
184
185 4319 T* Construct(const T object) {
186 4319 T* mem = Allocate();
187
1/2
✓ Branch 0 taken 4302 times.
✗ Branch 1 not taken.
 4319 if (mem != NULL) {
188
1/2
✓ Branch 2 taken 4302 times.
✗ Branch 3 not taken.
 4319 new (static_cast<void*>(mem)) T(object);
189 }
190 4319 return mem;
191 }
192
193 4319 void Destruct(T *object) {
194 4319 object->~T();
195 4319 Deallocate(object);
196 4319 }
197
198 /**
199 * Allocate a slot and returns a pointer to the memory.
200 * @return a pointer to a chunk of the memory pool
201 */
202 4319 T* Allocate() {
203
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4302 times.
 4319 if (this->IsFull())
204 ✗ return NULL;
205
206 // Allocate a slot
207 4319 this->SetBit(next_free_slot_);
208 4319 --num_free_slots_;
209 4319 T *slot = memory_ + next_free_slot_;
210
211 // Find a new free slot if there are some left
212
2/2
✓ Branch 1 taken 3280 times.
✓ Branch 2 taken 1022 times.
 4319 if (!this->IsFull()) {
213 3297 unsigned bitmap_block = next_free_slot_ / bits_per_block_;
214
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 3280 times.
 3343 while (~bitmap_[bitmap_block] == 0)
215 46 bitmap_block = (bitmap_block + 1) % (num_slots_ / bits_per_block_);
216 // TODO(jblomer): faster search inside the int
217 3297 next_free_slot_ = bitmap_block * bits_per_block_;
218
2/2
✓ Branch 1 taken 99814 times.
✓ Branch 2 taken 3280 times.
 103148 while (this->GetBit(next_free_slot_))
219 99851 next_free_slot_++;
220 }
221
222 4319 return slot;
223 }
224
225 /**
226 * Free a given slot in the memory pool
227 * @param slot a pointer to the slot be freed
228 */
229 4319 void Deallocate(T* slot) {
230 // Check if given slot is in bounds
231
2/4
✓ Branch 0 taken 4302 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4302 times.
✗ Branch 3 not taken.
 4319 assert((slot >= memory_) && (slot <= memory_ + num_slots_));
232
233 // Get position of slot
234 4319 const unsigned int position = slot - memory_;
235
236 // Check if slot was already freed
237
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4302 times.
 4319 assert(this->GetBit(position));
238
239 // Free slot, save the position of this slot as free (faster reallocation)
240 4319 this->UnsetBit(position);
241 4319 next_free_slot_ = position;
242 4319 ++num_free_slots_;
243 4319 }
244
245 186 uint64_t bytes_allocated() { return bytes_allocated_; }
246
247 private:
248 /**
249 * Check a bit in the internal allocation bitmap.
250 * @param position the position to check
251 * @return true if bit is set, otherwise false
252 */
253 107467 inline bool GetBit(const unsigned position) {
254
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 107396 times.
 107467 assert(position < num_slots_);
255 107467 return ((bitmap_[position / bits_per_block_] &
256 107467 (uint64_t(1) << (position % bits_per_block_))) != 0);
257 }
258
259 /**
260 * set a bit in the internal allocation bitmap
261 * @param position the number of the bit to be set
262 */
263 4319 inline void SetBit(const unsigned position) {
264
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4302 times.
 4319 assert(position < num_slots_);
265 4319 bitmap_[position / bits_per_block_] |=
266 4319 uint64_t(1) << (position % bits_per_block_);
267 4319 }
268
269 /**
270 * Clear a bit in the internal allocation bitmap
271 * @param position the number of the bit to be cleared
272 */
273 4319 inline void UnsetBit(const unsigned position) {
274
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4302 times.
 4319 assert(position < num_slots_);
275 4319 bitmap_[position / bits_per_block_] &=
276 4319 ~(uint64_t(1) << (position % bits_per_block_));
277 4319 }
278
279 unsigned int num_slots_; /**< Overall number of slots in memory pool. */
280 unsigned int num_free_slots_; /**< Current number of free slots left. */
281 unsigned int next_free_slot_; /**< Position of next free slot in pool. */
282 uint64_t bytes_allocated_;
283 uint64_t *bitmap_; /**< A bitmap to mark slots as allocated. */
284 unsigned bits_per_block_;
285 T *memory_; /**< The memory pool, array of Ms. */
286 };
287
288
289 /**
290 * Internal LRU list entry, to maintain the doubly linked list.
291 * The list keeps track of the least recently used keys in the cache.
292 */
293 template<class T> class ListEntry {
294 friend class LruCache;
295 public:
296 /**
297 * Create a new list entry as lonely, both next and prev pointing to this.
298 */
299 4503 ListEntry() {
300 4503 this->next = this;
301 4503 this->prev = this;
302 4503 }
303
304 4319 ListEntry(const ListEntry<T> &other) {
305
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4302 times.
 4319 next = (other.next == &other) ? this : other.next;
306
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4302 times.
 4319 prev = (other.prev == &other) ? this : other.prev;
307 4319 }
308
309 17466 virtual ~ListEntry() {}
310
311 /**
312 * Checks if the ListEntry is the list head
313 * @return true if ListEntry is list head otherwise false
314 */
315 virtual bool IsListHead() const = 0;
316
317 /**
318 * A lonely ListEntry has no connection to other elements.
319 * @return true if ListEntry is lonely otherwise false
320 */
321
3/4
✓ Branch 0 taken 50618 times.
✓ Branch 1 taken 145407 times.
✓ Branch 2 taken 50618 times.
✗ Branch 3 not taken.
 196107 bool IsLonely() const { return (this->next == this && this->prev == this); }
322
323 ListEntry<T> *next; /**< Pointer to next element in the list. */
324 ListEntry<T> *prev; /**< Pointer to previous element in the list. */
325
326 protected:
327 /**
328 * Insert a given ListEntry after this one.
329 * @param entry the ListEntry to insert after this one
330 */
331 inline void InsertAsSuccessor(ListEntryContent<T> *entry) {
332 assert(entry->IsLonely());
333
334 // Mount the new element between this and this->next
335 entry->next = this->next;
336 entry->prev = this;
337
338 // Fix pointers of existing list elements
339 this->next->prev = entry;
340 this->next = entry;
341 assert(!entry->IsLonely());
342 }
343
344 /**
345 * Insert a given ListEntry in front of this one
346 * @param entry the ListEntry to insert in front of this one
347 */
348 50647 inline void InsertAsPredecessor(ListEntryContent<T> *entry) {
349
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 50618 times.
 50647 assert(entry->IsLonely());
350
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 50618 times.
 50647 assert(!entry->IsListHead());
351
352 // Mount the new element between this and this->prev
353 50647 entry->next = this;
354 50647 entry->prev = this->prev;
355
356 // Fix pointers of existing list elements
357 50647 this->prev->next = entry;
358 50647 this->prev = entry;
359
360
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 50618 times.
 50647 assert(!entry->IsLonely());
361 50647 }
362
363 /**
364 * Remove this element from it's list.
365 * The function connects this->next with this->prev leaving the list
366 * in a consistent state. The ListEntry itself is lonely afterwards,
367 * but not deleted.
368 */
369 virtual void RemoveFromList() = 0;
370
371 private:
372 // No assignment operator (enforced by linker error)
373 ListEntry<T>& operator=(const ListEntry<T> &other);
374 }; // template<class T> class ListEntry
375
376 /**
377 * Specialized ListEntry to contain a data entry of type T
378 */
379 template<class T> class ListEntryContent : public ListEntry<T> {
380 public:
381
1/2
✓ Branch 2 taken 157 times.
✗ Branch 3 not taken.
 4319 explicit ListEntryContent(T content) {
382 4319 content_ = content;
383 4319 }
384
385 55188 inline bool IsListHead() const { return false; }
386 1239 inline T content() const { return content_; }
387
388 /**
389 * See ListEntry base class.
390 */
391 47466 inline void RemoveFromList() {
392
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 47454 times.
 47466 assert(!this->IsLonely());
393
394 // Remove this from list
395 47466 this->prev->next = this->next;
396 47466 this->next->prev = this->prev;
397
398 // Make this lonely
399 47466 this->next = this;
400 47466 this->prev = this;
401 47466 }
402
403 private:
404 T content_; /**< The data content of this ListEntry */
405 };
406
407 /**
408 * Specialized ListEntry to form a list head.
409 * Every list has exactly one list head which is also the entry point
410 * in the list. It is used to manipulate the list.
411 */
412 template<class T> class ListEntryHead : public ListEntry<T> {
413 public:
414 184 explicit ListEntryHead(ConcreteMemoryAllocator *allocator) :
415 184 allocator_(allocator) {}
416
417 258 virtual ~ListEntryHead() {
418 258 this->clear();
419 }
420
421 /**
422 * Remove all entries from the list.
423 * ListEntry objects are deleted but contained data keeps available
424 */
425 186 void clear() {
426 // Delete all list entries
427 186 ListEntry<T> *entry = this->next;
428 ListEntry<T> *delete_me;
429
2/2
✓ Branch 1 taken 3164 times.
✓ Branch 2 taken 131 times.
 3367 while (!entry->IsListHead()) {
430 3181 delete_me = entry;
431 3181 entry = entry->next;
432 3181 allocator_->Destruct(static_cast<ConcreteListEntryContent*>(delete_me));
433 }
434
435 // Reset the list to lonely
436 186 this->next = this;
437 186 this->prev = this;
438 186 }
439
440 191 inline bool IsListHead() const { return true; }
441 1019 inline bool IsEmpty() const { return this->IsLonely(); }
442
443 /**
444 * Push a new data object to the end of the list.
445 * @param the data object to insert
446 * @return the ListEntryContent structure wrapped around the data object
447 */
448 4319 inline ListEntryContent<T>* PushBack(T content) {
449 ListEntryContent<T> *new_entry =
450
1/2
✓ Branch 2 taken 4302 times.
✗ Branch 3 not taken.
 4319 allocator_->Construct(ListEntryContent<T>(content));
451 4319 this->InsertAsPredecessor(new_entry);
452 4319 return new_entry;
453 }
454
455 /**
456 * Pop the first object of the list.
457 * The object is returned and removed from the list
458 * @return the data object which resided in the first list entry
459 */
460 1019 inline T PopFront() {
461
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1019 times.
 1019 assert(!this->IsEmpty());
462 1019 return Pop(this->next);
463 }
464
465 /**
466 * Take a list entry out of it's list and reinsert at the end of this list.
467 * @param the ListEntry to be moved to the end of this list
468 */
469 46328 inline void MoveToBack(ListEntryContent<T> *entry) {
470
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 46316 times.
 46328 assert(!entry->IsLonely());
471
472 46328 entry->RemoveFromList();
473 46328 this->InsertAsPredecessor(entry);
474 46328 }
475
476 /**
477 * See ListEntry base class
478 */
479 ✗ inline void RemoveFromList() { assert(false); }
480
481 private:
482 /**
483 * Pop a ListEntry from the list (arbitrary position).
484 * The given ListEntry is removed from the list, deleted and it's
485 * data content is returned
486 * @param popped_entry the entry to be popped
487 * @return the data object of the popped ListEntry
488 */
489 1019 inline T Pop(ListEntry<T> *popped_entry) {
490
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1019 times.
 1019 assert(!popped_entry->IsListHead());
491
492 1019 ListEntryContent<T> *popped = (ListEntryContent<T> *)popped_entry;
493 1019 popped->RemoveFromList();
494 1019 T result = popped->content();
495 1019 allocator_->Destruct(static_cast<ConcreteListEntryContent*>(
496 popped_entry));
497 1019 return result;
498 }
499
500 private:
501 ConcreteMemoryAllocator *allocator_;
502 };
503
504 public: // LruCache
505 /**
506 * Create a new LRU cache object
507 * @param cache_size the maximal size of the cache
508 */
509 184 LruCache(const unsigned cache_size,
510 const Key &empty_key,
511 uint32_t (*hasher)(const Key &key),
512 perf::StatisticsTemplate statistics) :
513
1/2
✓ Branch 1 taken 129 times.
✗ Branch 2 not taken.
 184 counters_(statistics),
514 184 pause_(false),
515 184 cache_gauge_(0),
516 184 cache_size_(cache_size),
517 184 allocator_(cache_size),
518
2/4
✓ Branch 3 taken 129 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 129 times.
✗ Branch 7 not taken.
 368 lru_list_(&allocator_)
519 {
520
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 129 times.
 184 assert(cache_size > 0);
521
522 184 counters_.sz_size->Set(cache_size_);
523 184 filter_entry_ = NULL;
524 // cache_ = Cache(cache_size_);
525
1/2
✓ Branch 1 taken 129 times.
✗ Branch 2 not taken.
 184 cache_.Init(cache_size_, empty_key, hasher);
526 368 perf::Xadd(counters_.sz_allocated, allocator_.bytes_allocated() +
527 184 cache_.bytes_allocated());
528
529 #ifdef LRU_CACHE_THREAD_SAFE
530 184 int retval = pthread_mutex_init(&lock_, NULL);
531
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 129 times.
 184 assert(retval == 0);
532 #endif
533 184 }
534
535 96 static double GetEntrySize() {
536 96 return SmallHashFixed<Key, CacheEntry>::GetEntrySize() +
537 96 ConcreteMemoryAllocator::GetEntrySize();
538 }
539
540 258 virtual ~LruCache() {
541 #ifdef LRU_CACHE_THREAD_SAFE
542 258 pthread_mutex_destroy(&lock_);
543 #endif
544 }
545
546 /**
547 * Insert a new key-value pair to the list.
548 * If the cache is already full, the least recently used object is removed;
549 * afterwards the new object is inserted.
550 * If the object is already present it is updated and moved back to the end
551 * of the list
552 * @param key the key where the value is saved
553 * @param value the value of the cache entry
554 * @return true on insert, false on update
555 */
556 26417 virtual bool Insert(const Key &key, const Value &value) {
557 26417 this->Lock();
558
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 26398 times.
 26417 if (pause_) {
559 2 Unlock();
560 2 return false;
561 }
562
563
1/2
✓ Branch 1 taken 22244 times.
✗ Branch 2 not taken.
 26415 CacheEntry entry;
564
565 // Check if we have to update an existent entry
566
3/4
✓ Branch 1 taken 26398 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 22096 times.
✓ Branch 4 taken 4302 times.
 26415 if (this->DoLookup(key, &entry)) {
567 22096 perf::Inc(counters_.n_update);
568
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 22096 entry.value = value;
569
1/2
✓ Branch 1 taken 22096 times.
✗ Branch 2 not taken.
 22096 cache_.Insert(key, entry);
570
1/2
✓ Branch 1 taken 22096 times.
✗ Branch 2 not taken.
 22096 this->Touch(entry);
571 22096 this->Unlock();
572 22096 return false;
573 }
574
575 4319 perf::Inc(counters_.n_insert);
576 // Check if we have to make some space in the cache a
577
2/2
✓ Branch 1 taken 1019 times.
✓ Branch 2 taken 3283 times.
 4319 if (this->IsFull())
578
1/2
✓ Branch 1 taken 1019 times.
✗ Branch 2 not taken.
 1019 this->DeleteOldest();
579
580
1/2
✓ Branch 1 taken 4302 times.
✗ Branch 2 not taken.
 4319 entry.list_entry = lru_list_.PushBack(key);
581
1/2
✓ Branch 1 taken 4162 times.
✗ Branch 2 not taken.
 4319 entry.value = value;
582
583
1/2
✓ Branch 1 taken 4302 times.
✗ Branch 2 not taken.
 4319 cache_.Insert(key, entry);
584 4319 cache_gauge_++;
585
586 4319 Unlock();
587 4319 return true;
588 4188 }
589
590
591 /**
592 * Updates object and moves back to the end of the list. The object must be
593 * present.
594 */
595 1 virtual void Update(const Key &key) {
596 1 Lock();
597 // Is not called from the client, only from the cache plugin
598
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 assert(!pause_);
599
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 1 CacheEntry entry;
600
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 bool retval = DoLookup(key, &entry);
601
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
 1 assert(retval);
602 1 perf::Inc(counters_.n_update);
603
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 Touch(entry);
604 1 Unlock();
605 1 }
606
607
608 /**
609 * Changes the value of an entry in the LRU cache without updating the LRU
610 * order.
611 */
612 3 virtual bool UpdateValue(const Key &key, const Value &value) {
613 3 this->Lock();
614
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3 times.
 3 if (pause_) {
615 ✗ Unlock();
616 ✗ return false;
617 }
618
619
0/2
✗ Branch 1 not taken.
✗ Branch 2 not taken.
 3 CacheEntry entry;
620
3/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 2 times.
 3 if (!this->DoLookup(key, &entry)) {
621 1 this->Unlock();
622 1 return false;
623 }
624
625 2 perf::Inc(counters_.n_update_value);
626
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 entry.value = value;
627
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 cache_.Insert(key, entry);
628 2 this->Unlock();
629 2 return true;
630 3 }
631
632
633 /**
634 * Retrieve an element from the cache.
635 * If the element was found, it will be marked as 'recently used' and returned
636 * @param key the key to perform a lookup on
637 * @param value (out) here the result is saved (not touch in case of miss)
638 * @return true on successful lookup, false if key was not found
639 */
640 24534 virtual bool Lookup(const Key &key, Value *value, bool update_lru = true) {
641 24534 bool found = false;
642 24534 Lock();
643
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 24485 times.
 24534 if (pause_) {
644 20 Unlock();
645 20 return false;
646 }
647
648
1/2
✓ Branch 1 taken 22332 times.
✗ Branch 2 not taken.
 24514 CacheEntry entry;
649
3/4
✓ Branch 1 taken 24485 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24250 times.
✓ Branch 4 taken 235 times.
 24514 if (DoLookup(key, &entry)) {
650 // Hit
651 24262 perf::Inc(counters_.n_hit);
652
2/2
✓ Branch 0 taken 24219 times.
✓ Branch 1 taken 31 times.
 24262 if (update_lru)
653
1/2
✓ Branch 1 taken 24219 times.
✗ Branch 2 not taken.
 24231 Touch(entry);
654
1/2
✓ Branch 1 taken 2122 times.
✗ Branch 2 not taken.
 24262 *value = entry.value;
655 24262 found = true;
656 } else {
657 252 perf::Inc(counters_.n_miss);
658 }
659
660 24514 Unlock();
661 24514 return found;
662 2211 }
663
664 /**
665 * Forgets about a specific cache entry
666 * @param key the key to delete from the cache
667 * @return true if key was deleted, false if key was not in the cache
668 */
669 24 virtual bool Forget(const Key &key) {
670 24 bool found = false;
671 24 this->Lock();
672
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 22 times.
 24 if (pause_) {
673 2 Unlock();
674 2 return false;
675 }
676
677
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 22 CacheEntry entry;
678
3/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 7 times.
 22 if (this->DoLookup(key, &entry)) {
679 15 found = true;
680 15 perf::Inc(counters_.n_forget);
681
682
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 entry.list_entry->RemoveFromList();
683
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 allocator_.Destruct(entry.list_entry);
684
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 cache_.Erase(key);
685 15 --cache_gauge_;
686 }
687
688 22 this->Unlock();
689 22 return found;
690 18 }
691
692 /**
693 * Clears all elements from the cache.
694 * All memory of internal data structures will be freed but data of
695 * cache entries may stay in use, we do not call delete on any user data.
696 */
697 2 virtual void Drop() {
698 2 this->Lock();
699
700 2 cache_gauge_ = 0;
701 2 lru_list_.clear();
702 2 cache_.Clear();
703 2 perf::Inc(counters_.n_drop);
704 2 counters_.sz_allocated->Set(0);
705 4 perf::Xadd(counters_.sz_allocated, allocator_.bytes_allocated() +
706 2 cache_.bytes_allocated());
707
708 2 this->Unlock();
709 2 }
710
711 6 void Pause() {
712 6 Lock();
713 6 pause_ = true;
714 6 Unlock();
715 6 }
716
717 3 void Resume() {
718 3 Lock();
719 3 pause_ = false;
720 3 Unlock();
721 3 }
722
723 9473 inline bool IsFull() const { return cache_gauge_ >= cache_size_; }
724 1059 inline bool IsEmpty() const { return cache_gauge_ == 0; }
725
726 Counters counters() {
727 Lock();
728 cache_.GetCollisionStats(&counters_.num_collisions,
729 &counters_.max_collisions);
730 Unlock();
731 return counters_;
732 }
733
734 /**
735 * Prepares for in-order iteration of the cache entries to perform a filter
736 * operation. To ensure consistency, the LruCache must be locked for the
737 * duration of the filter operation.
738 */
739 12 virtual void FilterBegin() {
740
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 assert(!filter_entry_);
741 12 Lock();
742 12 filter_entry_ = &lru_list_;
743 12 }
744
745 /**
746 * Get the current key and value for the filter operation
747 * @param key Address to write the key
748 * @param value Address to write the value
749 */
750 116 virtual void FilterGet(Key *key, Value *value) {
751
1/2
✓ Branch 1 taken 114 times.
✗ Branch 2 not taken.
 116 CacheEntry entry;
752
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 116 times.
 116 assert(filter_entry_);
753
2/4
✓ Branch 1 taken 116 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 116 times.
 116 assert(!filter_entry_->IsListHead());
754 116 *key = static_cast<ConcreteListEntryContent *>(filter_entry_)->content();
755
1/2
✓ Branch 1 taken 116 times.
✗ Branch 2 not taken.
 116 bool rc = this->DoLookup(*key, &entry);
756
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 116 times.
 116 assert(rc);
757
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 116 *value = entry.value;
758 116 }
759
760 /**
761 * Advance to the next entry in the list
762 * @returns false upon reaching the end of the cache list
763 */
764 126 virtual bool FilterNext() {
765
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 126 times.
 126 assert(filter_entry_);
766 126 filter_entry_ = filter_entry_->next;
767 126 return !filter_entry_->IsListHead();
768 }
769
770 /**
771 * Delete the current cache list entry
772 */
773 104 virtual void FilterDelete() {
774
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 104 times.
 104 assert(filter_entry_);
775
2/4
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 104 times.
 104 assert(!filter_entry_->IsListHead());
776 104 ListEntry<Key> *new_current = filter_entry_->prev;
777 104 perf::Inc(counters_.n_forget);
778 104 Key k = static_cast<ConcreteListEntryContent *>(filter_entry_)->content();
779
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 filter_entry_->RemoveFromList();
780
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 allocator_.Destruct(static_cast<ConcreteListEntryContent *>(filter_entry_));
781
1/2
✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
 104 cache_.Erase(k);
782 104 --cache_gauge_;
783 104 filter_entry_ = new_current;
784 104 }
785
786 /**
787 * Finish filtering the entries and unlock the cache
788 */
789 12 virtual void FilterEnd() {
790
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 assert(filter_entry_);
791 12 filter_entry_ = NULL;
792 12 Unlock();
793 12 }
794
795 protected:
796 Counters counters_;
797
798 private:
799 /**
800 * this just performs a lookup in the cache
801 * WITHOUT changing the LRU order
802 * @param key the key to perform a lookup on
803 * @param entry a pointer to the entry structure
804 * @return true on successful lookup, false otherwise
805 */
806 51071 inline bool DoLookup(const Key &key, CacheEntry *entry) {
807 51071 return cache_.Lookup(key, entry);
808 }
809
810 /**
811 * Touch an entry.
812 * The entry will be moved to the back of the LRU list to mark it
813 * as 'recently used'... this saves the entry from being deleted
814 * @param entry the CacheEntry to be touched (CacheEntry is the internal wrapper data structure)
815 */
816 46328 inline void Touch(const CacheEntry &entry) {
817 46328 lru_list_.MoveToBack(entry.list_entry);
818 46328 }
819
820 /**
821 * Deletes the least recently used entry from the cache.
822 */
823 1019 inline void DeleteOldest() {
824
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1019 times.
 1019 assert(!this->IsEmpty());
825
826 1019 perf::Inc(counters_.n_replace);
827
1/2
✓ Branch 1 taken 1019 times.
✗ Branch 2 not taken.
 1019 Key delete_me = lru_list_.PopFront();
828
1/2
✓ Branch 1 taken 1019 times.
✗ Branch 2 not taken.
 1019 cache_.Erase(delete_me);
829
830 1019 --cache_gauge_;
831 1019 }
832
833 /**
834 * Locks the cache (thread safety).
835 */
836 51002 inline void Lock() {
837 #ifdef LRU_CACHE_THREAD_SAFE
838 51002 pthread_mutex_lock(&lock_);
839 #endif
840 51002 }
841
842 /**
843 * Unlocks the cache (thread safety).
844 */
845 51002 inline void Unlock() {
846 #ifdef LRU_CACHE_THREAD_SAFE
847 51002 pthread_mutex_unlock(&lock_);
848 #endif
849 51002 }
850
851 bool pause_; /**< Temporarily stops the cache in order to avoid poisoning */
852
853 // Internal data fields
854 unsigned int cache_gauge_;
855 const unsigned int cache_size_;
856 ConcreteMemoryAllocator allocator_;
857
858 /**
859 * A doubly linked list to keep track of the least recently used data entries.
860 * New entries get pushed back to the list. If an entry is touched
861 * it is moved to the back of the list again.
862 * If the cache gets too long, the first element (the oldest) gets
863 * deleted to obtain some space.
864 */
865 ListEntryHead<Key> lru_list_;
866 SmallHashFixed<Key, CacheEntry> cache_;
867
868 ListEntry<Key> *filter_entry_;
869 #ifdef LRU_CACHE_THREAD_SAFE
870 pthread_mutex_t lock_; /**< Mutex to make cache thread safe. */
871 #endif
872 }; // class LruCache
873
874 } // namespace lru
875
876 #endif // CVMFS_LRU_H_
877