CernVM-FS  2.13.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
lru.h
Go to the documentation of this file.
1 
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 
63 struct Counters {
69  uint64_t num_collisions;
70  uint32_t max_collisions;
77 
78  explicit Counters(perf::StatisticsTemplate statistics) {
79  sz_size = statistics.RegisterTemplated("sz_size", "Total size");
80  num_collisions = 0;
81  max_collisions = 0;
82  n_hit = statistics.RegisterTemplated("n_hit", "Number of hits");
83  n_miss = statistics.RegisterTemplated("n_miss", "Number of misses");
84  n_insert = statistics.RegisterTemplated("n_insert", "Number of inserts");
86  "n_insert_negative", "Number of negative inserts");
87  n_update = statistics.RegisterTemplated("n_update", "Number of updates");
88  n_update_value = statistics.RegisterTemplated("n_update_value",
89  "Number of value changes");
90  n_replace = statistics.RegisterTemplated("n_replace", "Number of replaces");
91  n_forget = statistics.RegisterTemplated("n_forget", "Number of forgets");
92  n_drop = statistics.RegisterTemplated("n_drop", "Number of drops");
93  sz_allocated = statistics.RegisterTemplated("sz_allocated",
94  "Number of allocated bytes ");
95  }
96 };
97 
98 
104 template<class Key, class Value>
106  private:
107  // Forward declarations of private internal data structures
108  template<class T>
109  class ListEntry;
110  template<class T>
112  template<class T>
114  template<class M>
115  class MemoryAllocator;
116 
117  // Helpers to get the template magic right
118  typedef ListEntryContent<Key> ConcreteListEntryContent;
119  typedef MemoryAllocator<ConcreteListEntryContent> ConcreteMemoryAllocator;
120 
124  typedef struct {
126  Value value;
127  } CacheEntry;
128 
129  // static uint64_t GetEntrySize() { return sizeof(Key) + sizeof(Value); }
130 
140  template<class T>
141  class MemoryAllocator : SingleCopy {
142  public:
148  explicit MemoryAllocator(const unsigned int num_slots) {
149  // how many bitmap chunks (chars) do we need?
150  unsigned int num_bytes_bitmap = num_slots / 8;
151  bits_per_block_ = 8 * sizeof(bitmap_[0]);
152  assert((num_slots % bits_per_block_) == 0);
153  assert(num_slots >= 2 * bits_per_block_);
154 
155  // How much actual memory do we need?
156  const unsigned int num_bytes_memory = sizeof(T) * num_slots;
157 
158  // Allocate zero'd memory
159  bitmap_ = reinterpret_cast<uint64_t *>(scalloc(num_bytes_bitmap, 1));
160  memory_ = reinterpret_cast<T *>(scalloc(num_bytes_memory, 1));
161 
162  // Create initial state
163  num_slots_ = num_slots;
164  num_free_slots_ = num_slots;
165  next_free_slot_ = 0;
166  bytes_allocated_ = num_bytes_bitmap + num_bytes_memory;
167  }
168 
172  static double GetEntrySize() {
173  return static_cast<double>(sizeof(T)) + 1.0 / 8.0;
174  }
175 
179  virtual ~MemoryAllocator() {
180  free(bitmap_);
181  free(memory_);
182  }
183 
188  inline bool IsFull() const { return num_free_slots_ == 0; }
189 
190  T *Construct(const T object) {
191  T *mem = Allocate();
192  if (mem != NULL) {
193  new (static_cast<void *>(mem)) T(object);
194  }
195  return mem;
196  }
197 
198  void Destruct(T *object) {
199  object->~T();
200  Deallocate(object);
201  }
202 
207  T *Allocate() {
208  if (this->IsFull())
209  return NULL;
210 
211  // Allocate a slot
212  this->SetBit(next_free_slot_);
213  --num_free_slots_;
214  T *slot = memory_ + next_free_slot_;
215 
216  // Find a new free slot if there are some left
217  if (!this->IsFull()) {
218  unsigned bitmap_block = next_free_slot_ / bits_per_block_;
219  while (~bitmap_[bitmap_block] == 0)
220  bitmap_block = (bitmap_block + 1) % (num_slots_ / bits_per_block_);
221  // TODO(jblomer): faster search inside the int
222  next_free_slot_ = bitmap_block * bits_per_block_;
223  while (this->GetBit(next_free_slot_))
224  next_free_slot_++;
225  }
226 
227  return slot;
228  }
229 
234  void Deallocate(T *slot) {
235  // Check if given slot is in bounds
236  assert((slot >= memory_) && (slot <= memory_ + num_slots_));
237 
238  // Get position of slot
239  const unsigned int position = slot - memory_;
240 
241  // Check if slot was already freed
242  assert(this->GetBit(position));
243 
244  // Free slot, save the position of this slot as free (faster reallocation)
245  this->UnsetBit(position);
246  next_free_slot_ = position;
247  ++num_free_slots_;
248  }
249 
250  uint64_t bytes_allocated() { return bytes_allocated_; }
251 
252  private:
258  inline bool GetBit(const unsigned position) {
259  assert(position < num_slots_);
260  return ((bitmap_[position / bits_per_block_]
261  & (uint64_t(1) << (position % bits_per_block_)))
262  != 0);
263  }
264 
269  inline void SetBit(const unsigned position) {
270  assert(position < num_slots_);
271  bitmap_[position / bits_per_block_] |= uint64_t(1)
272  << (position % bits_per_block_);
273  }
274 
279  inline void UnsetBit(const unsigned position) {
280  assert(position < num_slots_);
281  bitmap_[position / bits_per_block_] &= ~(uint64_t(1)
282  << (position % bits_per_block_));
283  }
284 
285  unsigned int num_slots_;
286  unsigned int num_free_slots_;
287  unsigned int next_free_slot_;
289  uint64_t *bitmap_;
290  unsigned bits_per_block_;
291  T *memory_;
292  };
293 
294 
299  template<class T>
300  class ListEntry {
301  friend class LruCache;
302 
303  public:
308  this->next = this;
309  this->prev = this;
310  }
311 
312  ListEntry(const ListEntry<T> &other) {
313  next = (other.next == &other) ? this : other.next;
314  prev = (other.prev == &other) ? this : other.prev;
315  }
316 
317  virtual ~ListEntry() { }
318 
323  virtual bool IsListHead() const = 0;
324 
329  bool IsLonely() const { return (this->next == this && this->prev == this); }
330 
334  protected:
340  assert(entry->IsLonely());
341 
342  // Mount the new element between this and this->next
343  entry->next = this->next;
344  entry->prev = this;
345 
346  // Fix pointers of existing list elements
347  this->next->prev = entry;
348  this->next = entry;
349  assert(!entry->IsLonely());
350  }
351 
357  assert(entry->IsLonely());
358  assert(!entry->IsListHead());
359 
360  // Mount the new element between this and this->prev
361  entry->next = this;
362  entry->prev = this->prev;
363 
364  // Fix pointers of existing list elements
365  this->prev->next = entry;
366  this->prev = entry;
367 
368  assert(!entry->IsLonely());
369  }
370 
377  virtual void RemoveFromList() = 0;
378 
379  private:
380  // No assignment operator (enforced by linker error)
381  ListEntry<T> &operator=(const ListEntry<T> &other);
382  }; // template<class T> class ListEntry
383 
387  template<class T>
388  class ListEntryContent : public ListEntry<T> {
389  public:
391 
392  inline bool IsListHead() const { return false; }
393  inline T content() const { return content_; }
394 
398  inline void RemoveFromList() {
399  assert(!this->IsLonely());
400 
401  // Remove this from list
402  this->prev->next = this->next;
403  this->next->prev = this->prev;
404 
405  // Make this lonely
406  this->next = this;
407  this->prev = this;
408  }
409 
410  private:
412  };
413 
419  template<class T>
420  class ListEntryHead : public ListEntry<T> {
421  public:
423  : allocator_(allocator) { }
424 
425  virtual ~ListEntryHead() { this->clear(); }
426 
431  void clear() {
432  // Delete all list entries
433  ListEntry<T> *entry = this->next;
434  ListEntry<T> *delete_me;
435  while (!entry->IsListHead()) {
436  delete_me = entry;
437  entry = entry->next;
439  static_cast<ConcreteListEntryContent *>(delete_me));
440  }
441 
442  // Reset the list to lonely
443  this->next = this;
444  this->prev = this;
445  }
446 
447  inline bool IsListHead() const { return true; }
448  inline bool IsEmpty() const { return this->IsLonely(); }
449 
455  inline ListEntryContent<T> *PushBack(T content) {
457  ListEntryContent<T>(content));
458  this->InsertAsPredecessor(new_entry);
459  return new_entry;
460  }
461 
467  inline T PopFront() {
468  assert(!this->IsEmpty());
469  return Pop(this->next);
470  }
471 
476  inline void MoveToBack(ListEntryContent<T> *entry) {
477  assert(!entry->IsLonely());
478 
479  entry->RemoveFromList();
480  this->InsertAsPredecessor(entry);
481  }
482 
486  inline void RemoveFromList() { assert(false); }
487 
488  private:
496  inline T Pop(ListEntry<T> *popped_entry) {
497  assert(!popped_entry->IsListHead());
498 
499  ListEntryContent<T> *popped = (ListEntryContent<T> *)popped_entry;
500  popped->RemoveFromList();
501  T result = popped->content();
503  static_cast<ConcreteListEntryContent *>(popped_entry));
504  return result;
505  }
506 
507  private:
509  };
510 
511  public: // LruCache
516  LruCache(const unsigned cache_size,
517  const Key &empty_key,
518  uint32_t (*hasher)(const Key &key),
519  perf::StatisticsTemplate statistics)
520  : counters_(statistics)
521  , pause_(false)
522  , cache_gauge_(0)
523  , cache_size_(cache_size)
524  , allocator_(cache_size)
525  , lru_list_(&allocator_) {
526  assert(cache_size > 0);
527 
529  filter_entry_ = NULL;
530  // cache_ = Cache(cache_size_);
531  cache_.Init(cache_size_, empty_key, hasher);
533  allocator_.bytes_allocated() + cache_.bytes_allocated());
534 
535 #ifdef LRU_CACHE_THREAD_SAFE
536  int retval = pthread_mutex_init(&lock_, NULL);
537  assert(retval == 0);
538 #endif
539  }
540 
541  static double GetEntrySize() {
544  }
545 
546  virtual ~LruCache() {
547 #ifdef LRU_CACHE_THREAD_SAFE
548  pthread_mutex_destroy(&lock_);
549 #endif
550  }
551 
562  virtual bool Insert(const Key &key, const Value &value) {
563  this->Lock();
564  if (pause_) {
565  Unlock();
566  return false;
567  }
568 
569  CacheEntry entry;
570 
571  // Check if we have to update an existent entry
572  if (this->DoLookup(key, &entry)) {
574  entry.value = value;
575  cache_.Insert(key, entry);
576  this->Touch(entry);
577  this->Unlock();
578  return false;
579  }
580 
582  // Check if we have to make some space in the cache a
583  if (this->IsFull())
584  this->DeleteOldest();
585 
586  entry.list_entry = lru_list_.PushBack(key);
587  entry.value = value;
588 
589  cache_.Insert(key, entry);
590  cache_gauge_++;
591 
592  Unlock();
593  return true;
594  }
595 
596 
601  virtual void Update(const Key &key) {
602  Lock();
603  // Is not called from the client, only from the cache plugin
604  assert(!pause_);
605  CacheEntry entry;
606  bool retval = DoLookup(key, &entry);
607  assert(retval);
609  Touch(entry);
610  Unlock();
611  }
612 
613 
618  virtual bool UpdateValue(const Key &key, const Value &value) {
619  this->Lock();
620  if (pause_) {
621  Unlock();
622  return false;
623  }
624 
625  CacheEntry entry;
626  if (!this->DoLookup(key, &entry)) {
627  this->Unlock();
628  return false;
629  }
630 
632  entry.value = value;
633  cache_.Insert(key, entry);
634  this->Unlock();
635  return true;
636  }
637 
638 
646  virtual bool Lookup(const Key &key, Value *value, bool update_lru = true) {
647  bool found = false;
648  Lock();
649  if (pause_) {
650  Unlock();
651  return false;
652  }
653 
654  CacheEntry entry;
655  if (DoLookup(key, &entry)) {
656  // Hit
658  if (update_lru)
659  Touch(entry);
660  *value = entry.value;
661  found = true;
662  } else {
664  }
665 
666  Unlock();
667  return found;
668  }
669 
675  virtual bool Forget(const Key &key) {
676  bool found = false;
677  this->Lock();
678  if (pause_) {
679  Unlock();
680  return false;
681  }
682 
683  CacheEntry entry;
684  if (this->DoLookup(key, &entry)) {
685  found = true;
687 
688  entry.list_entry->RemoveFromList();
689  allocator_.Destruct(entry.list_entry);
690  cache_.Erase(key);
691  --cache_gauge_;
692  }
693 
694  this->Unlock();
695  return found;
696  }
697 
703  virtual void Drop() {
704  this->Lock();
705 
706  cache_gauge_ = 0;
707  lru_list_.clear();
708  cache_.Clear();
712  allocator_.bytes_allocated() + cache_.bytes_allocated());
713 
714  this->Unlock();
715  }
716 
717  void Pause() {
718  Lock();
719  pause_ = true;
720  Unlock();
721  }
722 
723  void Resume() {
724  Lock();
725  pause_ = false;
726  Unlock();
727  }
728 
729  inline bool IsFull() const { return cache_gauge_ >= cache_size_; }
730  inline bool IsEmpty() const { return cache_gauge_ == 0; }
731 
733  Lock();
734  cache_.GetCollisionStats(&counters_.num_collisions,
736  Unlock();
737  return counters_;
738  }
739 
745  virtual void FilterBegin() {
747  Lock();
749  }
750 
756  virtual void FilterGet(Key *key, Value *value) {
757  CacheEntry entry;
760  *key = static_cast<ConcreteListEntryContent *>(filter_entry_)->content();
761  bool rc = this->DoLookup(*key, &entry);
762  assert(rc);
763  *value = entry.value;
764  }
765 
770  virtual bool FilterNext() {
773  return !filter_entry_->IsListHead();
774  }
775 
779  virtual void FilterDelete() {
782  ListEntry<Key> *new_current = filter_entry_->prev;
784  Key k = static_cast<ConcreteListEntryContent *>(filter_entry_)->content();
786  allocator_.Destruct(static_cast<ConcreteListEntryContent *>(filter_entry_));
787  cache_.Erase(k);
788  --cache_gauge_;
789  filter_entry_ = new_current;
790  }
791 
795  virtual void FilterEnd() {
797  filter_entry_ = NULL;
798  Unlock();
799  }
800 
801  protected:
803 
804  private:
812  inline bool DoLookup(const Key &key, CacheEntry *entry) {
813  return cache_.Lookup(key, entry);
814  }
815 
823  inline void Touch(const CacheEntry &entry) {
824  lru_list_.MoveToBack(entry.list_entry);
825  }
826 
830  inline void DeleteOldest() {
831  assert(!this->IsEmpty());
832 
834  Key delete_me = lru_list_.PopFront();
835  cache_.Erase(delete_me);
836 
837  --cache_gauge_;
838  }
839 
843  inline void Lock() {
844 #ifdef LRU_CACHE_THREAD_SAFE
845  pthread_mutex_lock(&lock_);
846 #endif
847  }
848 
852  inline void Unlock() {
853 #ifdef LRU_CACHE_THREAD_SAFE
854  pthread_mutex_unlock(&lock_);
855 #endif
856  }
857 
858  bool pause_;
860  // Internal data fields
861  unsigned int cache_gauge_;
862  const unsigned int cache_size_;
864 
872  ListEntryHead<Key> lru_list_;
874 
875  ListEntry<Key> *filter_entry_;
876 #ifdef LRU_CACHE_THREAD_SAFE
877  pthread_mutex_t lock_;
878 #endif
879 }; // class LruCache
880 
881 } // namespace lru
882 
883 #endif // CVMFS_LRU_H_
static double GetEntrySize()
Definition: lru.h:172
virtual ~MemoryAllocator()
Definition: lru.h:179
bool IsEmpty() const
Definition: lru.h:448
virtual void FilterEnd()
Definition: lru.h:795
int64_t Xadd(class Counter *counter, const int64_t delta)
Definition: statistics.h:51
void Destruct(T *object)
Definition: lru.h:198
perf::Counter * n_hit
Definition: lru.h:65
virtual bool IsListHead() const =0
uint64_t bytes_allocated()
Definition: lru.h:250
SmallHashFixed< Key, CacheEntry > cache_
Definition: lru.h:873
void InsertAsSuccessor(ListEntryContent< T > *entry)
Definition: lru.h:339
void RemoveFromList()
Definition: lru.h:486
Counters(perf::StatisticsTemplate statistics)
Definition: lru.h:78
const unsigned int cache_size_
Definition: lru.h:862
ListEntry< T > * next
Definition: lru.h:331
pthread_mutex_t lock_
Definition: lru.h:877
Definition: lru.h:109
T PopFront()
Definition: lru.h:467
ListEntry()
Definition: lru.h:307
Counters counters()
Definition: lru.h:732
ListEntryHead< Key > lru_list_
Definition: lru.h:872
perf::Counter * n_miss
Definition: lru.h:66
virtual bool Insert(const Key &key, const Value &value)
Definition: lru.h:562
void Lock()
Definition: lru.h:843
ListEntry(const ListEntry< T > &other)
Definition: lru.h:312
assert((mem||(size==0))&&"Out Of Memory")
Value value
Definition: lru.h:126
perf::Counter * sz_size
Definition: lru.h:64
virtual void FilterGet(Key *key, Value *value)
Definition: lru.h:756
MemoryAllocator(const unsigned int num_slots)
Definition: lru.h:148
ListEntryContent< Key > * list_entry
Definition: lru.h:125
Definition: lru.h:111
static double GetEntrySize()
Definition: lru.h:541
Counters counters_
Definition: lru.h:802
virtual bool FilterNext()
Definition: lru.h:770
bool IsEmpty() const
Definition: lru.h:730
perf::Counter * n_drop
Definition: lru.h:75
void RemoveFromList()
Definition: lru.h:398
ListEntryHead(ConcreteMemoryAllocator *allocator)
Definition: lru.h:422
ListEntryContent< T > * PushBack(T content)
Definition: lru.h:455
perf::Counter * n_forget
Definition: lru.h:74
void UnsetBit(const unsigned position)
Definition: lru.h:279
Counter * RegisterTemplated(const std::string &name_minor, const std::string &desc)
Definition: statistics.h:109
perf::Counter * sz_allocated
Definition: lru.h:76
void InsertAsPredecessor(ListEntryContent< T > *entry)
Definition: lru.h:356
ListEntryContent< Key > ConcreteListEntryContent
Definition: lru.h:115
T Pop(ListEntry< T > *popped_entry)
Definition: lru.h:496
bool IsListHead() const
Definition: lru.h:447
Definition: lru.h:113
virtual void RemoveFromList()=0
perf::Counter * n_insert
Definition: lru.h:67
void Set(const int64_t val)
Definition: statistics.h:33
unsigned int next_free_slot_
Definition: lru.h:287
bool GetBit(const unsigned position)
Definition: lru.h:258
bool DoLookup(const Key &key, CacheEntry *entry)
Definition: lru.h:812
uint64_t num_collisions
Definition: lru.h:69
ListEntry< T > * prev
Definition: lru.h:332
void Deallocate(T *slot)
Definition: lru.h:234
virtual void FilterDelete()
Definition: lru.h:779
virtual bool UpdateValue(const Key &key, const Value &value)
Definition: lru.h:618
ListEntryContent(T content)
Definition: lru.h:390
void Unlock()
Definition: lru.h:852
Definition: lru.h:124
perf::Counter * n_insert_negative
Definition: lru.h:68
virtual void FilterBegin()
Definition: lru.h:745
void MoveToBack(ListEntryContent< T > *entry)
Definition: lru.h:476
unsigned int num_slots_
Definition: lru.h:285
virtual void Update(const Key &key)
Definition: lru.h:601
void Inc(class Counter *counter)
Definition: statistics.h:50
bool IsFull() const
Definition: lru.h:188
bool IsLonely() const
Definition: lru.h:329
void Pause()
Definition: lru.h:717
T * Construct(const T object)
Definition: lru.h:190
unsigned int num_free_slots_
Definition: lru.h:286
unsigned int cache_gauge_
Definition: lru.h:861
void DeleteOldest()
Definition: lru.h:830
virtual ~ListEntry()
Definition: lru.h:317
ListEntry< Key > * filter_entry_
Definition: lru.h:875
LruCache(const unsigned cache_size, const Key &empty_key, uint32_t(*hasher)(const Key &key), perf::StatisticsTemplate statistics)
Definition: lru.h:516
T content() const
Definition: lru.h:393
virtual bool Lookup(const Key &key, Value *value, bool update_lru=true)
Definition: lru.h:646
bool IsFull() const
Definition: lru.h:729
uint32_t max_collisions
Definition: lru.h:70
ConcreteMemoryAllocator * allocator_
Definition: lru.h:508
void SetBit(const unsigned position)
Definition: lru.h:269
ConcreteMemoryAllocator allocator_
Definition: lru.h:863
void Resume()
Definition: lru.h:723
ListEntry< T > & operator=(const ListEntry< T > &other)
virtual ~LruCache()
Definition: lru.h:546
virtual bool Forget(const Key &key)
Definition: lru.h:675
T content_
Definition: lru.h:411
virtual ~ListEntryHead()
Definition: lru.h:425
void clear()
Definition: lru.h:431
virtual void Drop()
Definition: lru.h:703
bool IsListHead() const
Definition: lru.h:392
mem
Definition: smalloc.h:60
MemoryAllocator< ConcreteListEntryContent > ConcreteMemoryAllocator
Definition: lru.h:119
perf::Counter * n_update_value
Definition: lru.h:72
bool pause_
Definition: lru.h:858
void Touch(const CacheEntry &entry)
Definition: lru.h:823
perf::Counter * n_update
Definition: lru.h:71
perf::Counter * n_replace
Definition: lru.h:73