CernVM-FS  2.10.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 "atomic.h"
52 #include "platform.h"
53 #include "smallhash.h"
54 #include "smalloc.h"
55 #include "statistics.h"
56 #include "util/single_copy.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");
85  n_insert_negative = statistics.RegisterTemplated("n_insert_negative",
86  "Number of negative inserts");
87  n_update = statistics.RegisterTemplated("n_update",
88  "Number of updates");
89  n_update_value = statistics.RegisterTemplated("n_update_value",
90  "Number of value changes");
91  n_replace = statistics.RegisterTemplated("n_replace", "Number of replaces");
92  n_forget = statistics.RegisterTemplated("n_forget", "Number of forgets");
93  n_drop = statistics.RegisterTemplated("n_drop", "Number of drops");
94  sz_allocated = statistics.RegisterTemplated("sz_allocated",
95  "Number of allocated bytes ");
96  }
97 };
98 
99 
105 template<class Key, class Value>
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 
121  typedef struct {
123  Value value;
124  } CacheEntry;
125 
126  // static uint64_t GetEntrySize() { return sizeof(Key) + sizeof(Value); }
127 
137  template<class T> class MemoryAllocator : SingleCopy {
138  public:
143  explicit MemoryAllocator(const unsigned int num_slots) {
144  // how many bitmap chunks (chars) do we need?
145  unsigned int num_bytes_bitmap = num_slots / 8;
146  bits_per_block_ = 8 * sizeof(bitmap_[0]);
147  assert((num_slots % bits_per_block_) == 0);
148  assert(num_slots >= 2*bits_per_block_);
149 
150  // How much actual memory do we need?
151  const unsigned int num_bytes_memory = sizeof(T) * num_slots;
152 
153  // Allocate zero'd memory
154  bitmap_ = reinterpret_cast<uint64_t *>(scalloc(num_bytes_bitmap, 1));
155  memory_ = reinterpret_cast<T *>(scalloc(num_bytes_memory, 1));
156 
157  // Create initial state
158  num_slots_ = num_slots;
159  num_free_slots_ = num_slots;
160  next_free_slot_ = 0;
161  bytes_allocated_ = num_bytes_bitmap + num_bytes_memory;
162  }
163 
167  static double GetEntrySize() {
168  return static_cast<double>(sizeof(T)) + 1.0/8.0;
169  }
170 
174  virtual ~MemoryAllocator() {
175  free(bitmap_);
176  free(memory_);
177  }
178 
183  inline bool IsFull() const { return num_free_slots_ == 0; }
184 
185  T* Construct(const T object) {
186  T* mem = Allocate();
187  if (mem != NULL) {
188  new (static_cast<void*>(mem)) T(object);
189  }
190  return mem;
191  }
192 
193  void Destruct(T *object) {
194  object->~T();
195  Deallocate(object);
196  }
197 
202  T* Allocate() {
203  if (this->IsFull())
204  return NULL;
205 
206  // Allocate a slot
207  this->SetBit(next_free_slot_);
208  --num_free_slots_;
209  T *slot = memory_ + next_free_slot_;
210 
211  // Find a new free slot if there are some left
212  if (!this->IsFull()) {
213  unsigned bitmap_block = next_free_slot_ / bits_per_block_;
214  while (~bitmap_[bitmap_block] == 0)
215  bitmap_block = (bitmap_block + 1) % (num_slots_ / bits_per_block_);
216  // TODO(jblomer): faster search inside the int
217  next_free_slot_ = bitmap_block * bits_per_block_;
218  while (this->GetBit(next_free_slot_))
219  next_free_slot_++;
220  }
221 
222  return slot;
223  }
224 
229  void Deallocate(T* slot) {
230  // Check if given slot is in bounds
231  assert((slot >= memory_) && (slot <= memory_ + num_slots_));
232 
233  // Get position of slot
234  const unsigned int position = slot - memory_;
235 
236  // Check if slot was already freed
237  assert(this->GetBit(position));
238 
239  // Free slot, save the position of this slot as free (faster reallocation)
240  this->UnsetBit(position);
241  next_free_slot_ = position;
242  ++num_free_slots_;
243  }
244 
245  uint64_t bytes_allocated() { return bytes_allocated_; }
246 
247  private:
253  inline bool GetBit(const unsigned position) {
254  assert(position < num_slots_);
255  return ((bitmap_[position / bits_per_block_] &
256  (uint64_t(1) << (position % bits_per_block_))) != 0);
257  }
258 
263  inline void SetBit(const unsigned position) {
264  assert(position < num_slots_);
265  bitmap_[position / bits_per_block_] |=
266  uint64_t(1) << (position % bits_per_block_);
267  }
268 
273  inline void UnsetBit(const unsigned position) {
274  assert(position < num_slots_);
275  bitmap_[position / bits_per_block_] &=
276  ~(uint64_t(1) << (position % bits_per_block_));
277  }
278 
279  unsigned int num_slots_;
280  unsigned int num_free_slots_;
281  unsigned int next_free_slot_;
283  uint64_t *bitmap_;
284  unsigned bits_per_block_;
285  T *memory_;
286  };
287 
288 
293  template<class T> class ListEntry {
294  friend class LruCache;
295  public:
300  this->next = this;
301  this->prev = this;
302  }
303 
304  ListEntry(const ListEntry<T> &other) {
305  next = (other.next == &other) ? this : other.next;
306  prev = (other.prev == &other) ? this : other.prev;
307  }
308 
309  virtual ~ListEntry() {}
310 
315  virtual bool IsListHead() const = 0;
316 
321  bool IsLonely() const { return (this->next == this && this->prev == this); }
322 
326  protected:
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 
349  assert(entry->IsLonely());
350  assert(!entry->IsListHead());
351 
352  // Mount the new element between this and this->prev
353  entry->next = this;
354  entry->prev = this->prev;
355 
356  // Fix pointers of existing list elements
357  this->prev->next = entry;
358  this->prev = entry;
359 
360  assert(!entry->IsLonely());
361  }
362 
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 
379  template<class T> class ListEntryContent : public ListEntry<T> {
380  public:
381  explicit ListEntryContent(T content) {
382  content_ = content;
383  }
384 
385  inline bool IsListHead() const { return false; }
386  inline T content() const { return content_; }
387 
391  inline void RemoveFromList() {
392  assert(!this->IsLonely());
393 
394  // Remove this from list
395  this->prev->next = this->next;
396  this->next->prev = this->prev;
397 
398  // Make this lonely
399  this->next = this;
400  this->prev = this;
401  }
402 
403  private:
405  };
406 
412  template<class T> class ListEntryHead : public ListEntry<T> {
413  public:
414  explicit ListEntryHead(ConcreteMemoryAllocator *allocator) :
415  allocator_(allocator) {}
416 
417  virtual ~ListEntryHead() {
418  this->clear();
419  }
420 
425  void clear() {
426  // Delete all list entries
427  ListEntry<T> *entry = this->next;
428  ListEntry<T> *delete_me;
429  while (!entry->IsListHead()) {
430  delete_me = entry;
431  entry = entry->next;
432  allocator_->Destruct(static_cast<ConcreteListEntryContent*>(delete_me));
433  }
434 
435  // Reset the list to lonely
436  this->next = this;
437  this->prev = this;
438  }
439 
440  inline bool IsListHead() const { return true; }
441  inline bool IsEmpty() const { return this->IsLonely(); }
442 
448  inline ListEntryContent<T>* PushBack(T content) {
449  ListEntryContent<T> *new_entry =
451  this->InsertAsPredecessor(new_entry);
452  return new_entry;
453  }
454 
460  inline T PopFront() {
461  assert(!this->IsEmpty());
462  return Pop(this->next);
463  }
464 
469  inline void MoveToBack(ListEntryContent<T> *entry) {
470  assert(!entry->IsLonely());
471 
472  entry->RemoveFromList();
473  this->InsertAsPredecessor(entry);
474  }
475 
479  inline void RemoveFromList() { assert(false); }
480 
481  private:
489  inline T Pop(ListEntry<T> *popped_entry) {
490  assert(!popped_entry->IsListHead());
491 
492  ListEntryContent<T> *popped = (ListEntryContent<T> *)popped_entry;
493  popped->RemoveFromList();
494  T result = popped->content();
495  allocator_->Destruct(static_cast<ConcreteListEntryContent*>(
496  popped_entry));
497  return result;
498  }
499 
500  private:
502  };
503 
504  public: // LruCache
509  LruCache(const unsigned cache_size,
510  const Key &empty_key,
511  uint32_t (*hasher)(const Key &key),
512  perf::StatisticsTemplate statistics) :
513  counters_(statistics),
514  pause_(false),
515  cache_gauge_(0),
516  cache_size_(cache_size),
517  allocator_(cache_size),
519  {
520  assert(cache_size > 0);
521 
523  filter_entry_ = NULL;
524  // cache_ = Cache(cache_size_);
525  cache_.Init(cache_size_, empty_key, hasher);
527  cache_.bytes_allocated());
528 
529 #ifdef LRU_CACHE_THREAD_SAFE
530  int retval = pthread_mutex_init(&lock_, NULL);
531  assert(retval == 0);
532 #endif
533  }
534 
535  static double GetEntrySize() {
538  }
539 
540  virtual ~LruCache() {
541 #ifdef LRU_CACHE_THREAD_SAFE
542  pthread_mutex_destroy(&lock_);
543 #endif
544  }
545 
556  virtual bool Insert(const Key &key, const Value &value) {
557  this->Lock();
558  if (pause_) {
559  Unlock();
560  return false;
561  }
562 
563  CacheEntry entry;
564 
565  // Check if we have to update an existent entry
566  if (this->DoLookup(key, &entry)) {
568  entry.value = value;
569  cache_.Insert(key, entry);
570  this->Touch(entry);
571  this->Unlock();
572  return false;
573  }
574 
576  // Check if we have to make some space in the cache a
577  if (this->IsFull())
578  this->DeleteOldest();
579 
580  entry.list_entry = lru_list_.PushBack(key);
581  entry.value = value;
582 
583  cache_.Insert(key, entry);
584  cache_gauge_++;
585 
586  Unlock();
587  return true;
588  }
589 
590 
595  virtual void Update(const Key &key) {
596  Lock();
597  // Is not called from the client, only from the cache plugin
598  assert(!pause_);
599  CacheEntry entry;
600  bool retval = DoLookup(key, &entry);
601  assert(retval);
603  Touch(entry);
604  Unlock();
605  }
606 
607 
612  virtual bool UpdateValue(const Key &key, const Value &value) {
613  this->Lock();
614  if (pause_) {
615  Unlock();
616  return false;
617  }
618 
619  CacheEntry entry;
620  if (!this->DoLookup(key, &entry)) {
621  this->Unlock();
622  return false;
623  }
624 
626  entry.value = value;
627  cache_.Insert(key, entry);
628  this->Unlock();
629  return true;
630  }
631 
632 
640  virtual bool Lookup(const Key &key, Value *value, bool update_lru = true) {
641  bool found = false;
642  Lock();
643  if (pause_) {
644  Unlock();
645  return false;
646  }
647 
648  CacheEntry entry;
649  if (DoLookup(key, &entry)) {
650  // Hit
652  if (update_lru)
653  Touch(entry);
654  *value = entry.value;
655  found = true;
656  } else {
658  }
659 
660  Unlock();
661  return found;
662  }
663 
669  virtual bool Forget(const Key &key) {
670  bool found = false;
671  this->Lock();
672  if (pause_) {
673  Unlock();
674  return false;
675  }
676 
677  CacheEntry entry;
678  if (this->DoLookup(key, &entry)) {
679  found = true;
681 
682  entry.list_entry->RemoveFromList();
683  allocator_.Destruct(entry.list_entry);
684  cache_.Erase(key);
685  --cache_gauge_;
686  }
687 
688  this->Unlock();
689  return found;
690  }
691 
697  virtual void Drop() {
698  this->Lock();
699 
700  cache_gauge_ = 0;
701  lru_list_.clear();
702  cache_.Clear();
706  cache_.bytes_allocated());
707 
708  this->Unlock();
709  }
710 
711  void Pause() {
712  Lock();
713  pause_ = true;
714  Unlock();
715  }
716 
717  void Resume() {
718  Lock();
719  pause_ = false;
720  Unlock();
721  }
722 
723  inline bool IsFull() const { return cache_gauge_ >= cache_size_; }
724  inline bool IsEmpty() const { return cache_gauge_ == 0; }
725 
727  Lock();
728  cache_.GetCollisionStats(&counters_.num_collisions,
730  Unlock();
731  return counters_;
732  }
733 
739  virtual void FilterBegin() {
741  Lock();
743  }
744 
750  virtual void FilterGet(Key *key, Value *value) {
751  CacheEntry entry;
754  *key = static_cast<ConcreteListEntryContent *>(filter_entry_)->content();
755  bool rc = this->DoLookup(*key, &entry);
756  assert(rc);
757  *value = entry.value;
758  }
759 
764  virtual bool FilterNext() {
767  return !filter_entry_->IsListHead();
768  }
769 
773  virtual void FilterDelete() {
776  ListEntry<Key> *new_current = filter_entry_->prev;
778  Key k = static_cast<ConcreteListEntryContent *>(filter_entry_)->content();
780  allocator_.Destruct(static_cast<ConcreteListEntryContent *>(filter_entry_));
781  cache_.Erase(k);
782  --cache_gauge_;
783  filter_entry_ = new_current;
784  }
785 
789  virtual void FilterEnd() {
791  filter_entry_ = NULL;
792  Unlock();
793  }
794 
795  protected:
797 
798  private:
806  inline bool DoLookup(const Key &key, CacheEntry *entry) {
807  return cache_.Lookup(key, entry);
808  }
809 
816  inline void Touch(const CacheEntry &entry) {
817  lru_list_.MoveToBack(entry.list_entry);
818  }
819 
823  inline void DeleteOldest() {
824  assert(!this->IsEmpty());
825 
827  Key delete_me = lru_list_.PopFront();
828  cache_.Erase(delete_me);
829 
830  --cache_gauge_;
831  }
832 
836  inline void Lock() {
837 #ifdef LRU_CACHE_THREAD_SAFE
838  pthread_mutex_lock(&lock_);
839 #endif
840  }
841 
845  inline void Unlock() {
846 #ifdef LRU_CACHE_THREAD_SAFE
847  pthread_mutex_unlock(&lock_);
848 #endif
849  }
850 
851  bool pause_;
853  // Internal data fields
854  unsigned int cache_gauge_;
855  const unsigned int cache_size_;
857 
865  ListEntryHead<Key> lru_list_;
867 
868  ListEntry<Key> *filter_entry_;
869 #ifdef LRU_CACHE_THREAD_SAFE
870  pthread_mutex_t lock_;
871 #endif
872 }; // class LruCache
873 
874 } // namespace lru
875 
876 #endif // CVMFS_LRU_H_
static double GetEntrySize()
Definition: lru.h:167
virtual ~MemoryAllocator()
Definition: lru.h:174
bool IsEmpty() const
Definition: lru.h:441
virtual void FilterEnd()
Definition: lru.h:789
int64_t Xadd(class Counter *counter, const int64_t delta)
Definition: statistics.h:51
void Destruct(T *object)
Definition: lru.h:193
perf::Counter * n_hit
Definition: lru.h:65
virtual bool IsListHead() const =0
uint64_t bytes_allocated()
Definition: lru.h:245
SmallHashFixed< Key, CacheEntry > cache_
Definition: lru.h:866
void InsertAsSuccessor(ListEntryContent< T > *entry)
Definition: lru.h:331
void RemoveFromList()
Definition: lru.h:479
Counters(perf::StatisticsTemplate statistics)
Definition: lru.h:78
const unsigned int cache_size_
Definition: lru.h:855
ListEntry< T > * next
Definition: lru.h:323
pthread_mutex_t lock_
Definition: lru.h:870
Definition: lru.h:109
T PopFront()
Definition: lru.h:460
ListEntry()
Definition: lru.h:299
Counters counters()
Definition: lru.h:726
ListEntryHead< Key > lru_list_
Definition: lru.h:865
perf::Counter * n_miss
Definition: lru.h:66
virtual bool Insert(const Key &key, const Value &value)
Definition: lru.h:556
void Lock()
Definition: lru.h:836
ListEntry(const ListEntry< T > &other)
Definition: lru.h:304
assert((mem||(size==0))&&"Out Of Memory")
Value value
Definition: lru.h:123
perf::Counter * sz_size
Definition: lru.h:64
virtual void FilterGet(Key *key, Value *value)
Definition: lru.h:750
MemoryAllocator(const unsigned int num_slots)
Definition: lru.h:143
ListEntryContent< Key > * list_entry
Definition: lru.h:122
Definition: lru.h:110
static double GetEntrySize()
Definition: lru.h:535
Counters counters_
Definition: lru.h:796
virtual bool FilterNext()
Definition: lru.h:764
bool IsEmpty() const
Definition: lru.h:724
perf::Counter * n_drop
Definition: lru.h:75
void RemoveFromList()
Definition: lru.h:391
ListEntryHead(ConcreteMemoryAllocator *allocator)
Definition: lru.h:414
ListEntryContent< T > * PushBack(T content)
Definition: lru.h:448
perf::Counter * n_forget
Definition: lru.h:74
void UnsetBit(const unsigned position)
Definition: lru.h:273
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:348
ListEntryContent< Key > ConcreteListEntryContent
Definition: lru.h:112
T Pop(ListEntry< T > *popped_entry)
Definition: lru.h:489
bool IsListHead() const
Definition: lru.h:440
Definition: lru.h:111
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:281
bool GetBit(const unsigned position)
Definition: lru.h:253
bool DoLookup(const Key &key, CacheEntry *entry)
Definition: lru.h:806
uint64_t num_collisions
Definition: lru.h:69
ListEntry< T > * prev
Definition: lru.h:324
void Deallocate(T *slot)
Definition: lru.h:229
virtual void FilterDelete()
Definition: lru.h:773
virtual bool UpdateValue(const Key &key, const Value &value)
Definition: lru.h:612
ListEntryContent(T content)
Definition: lru.h:381
void Unlock()
Definition: lru.h:845
Definition: lru.h:121
perf::Counter * n_insert_negative
Definition: lru.h:68
virtual void FilterBegin()
Definition: lru.h:739
void MoveToBack(ListEntryContent< T > *entry)
Definition: lru.h:469
unsigned int num_slots_
Definition: lru.h:279
virtual void Update(const Key &key)
Definition: lru.h:595
void Inc(class Counter *counter)
Definition: statistics.h:50
bool IsFull() const
Definition: lru.h:183
bool IsLonely() const
Definition: lru.h:321
void Pause()
Definition: lru.h:711
T * Construct(const T object)
Definition: lru.h:185
unsigned int num_free_slots_
Definition: lru.h:280
unsigned int cache_gauge_
Definition: lru.h:854
void DeleteOldest()
Definition: lru.h:823
virtual ~ListEntry()
Definition: lru.h:309
ListEntry< Key > * filter_entry_
Definition: lru.h:868
LruCache(const unsigned cache_size, const Key &empty_key, uint32_t(*hasher)(const Key &key), perf::StatisticsTemplate statistics)
Definition: lru.h:509
T content() const
Definition: lru.h:386
virtual bool Lookup(const Key &key, Value *value, bool update_lru=true)
Definition: lru.h:640
bool IsFull() const
Definition: lru.h:723
uint32_t max_collisions
Definition: lru.h:70
ConcreteMemoryAllocator * allocator_
Definition: lru.h:501
void SetBit(const unsigned position)
Definition: lru.h:263
ConcreteMemoryAllocator allocator_
Definition: lru.h:856
void Resume()
Definition: lru.h:717
ListEntry< T > & operator=(const ListEntry< T > &other)
virtual ~LruCache()
Definition: lru.h:540
virtual bool Forget(const Key &key)
Definition: lru.h:669
T content_
Definition: lru.h:404
virtual ~ListEntryHead()
Definition: lru.h:417
void clear()
Definition: lru.h:425
virtual void Drop()
Definition: lru.h:697
bool IsListHead() const
Definition: lru.h:385
return mem
Definition: smalloc.h:50
MemoryAllocator< ConcreteListEntryContent > ConcreteMemoryAllocator
Definition: lru.h:116
perf::Counter * n_update_value
Definition: lru.h:72
bool pause_
Definition: lru.h:851
void Touch(const CacheEntry &entry)
Definition: lru.h:816
perf::Counter * n_update
Definition: lru.h:71
perf::Counter * n_replace
Definition: lru.h:73