lru.h

Go to the documentation of this file.

#ifndef CVMFS_LRU_H_
#define CVMFS_LRU_H_

// If defined the cache is secured by a posix mutex
#define LRU_CACHE_THREAD_SAFE

#include <stdint.h>

#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <map>
#include <string>

#include "smallhash.h"
#include "statistics.h"
#include "util/atomic.h"
#include "util/platform.h"
#include "util/single_copy.h"
#include "util/smalloc.h"

namespace lru {

struct Counters {
  perf::Counter *sz_size;
  perf::Counter *n_hit;
  perf::Counter *n_miss;
  perf::Counter *n_insert;
  perf::Counter *n_insert_negative;
  uint64_t num_collisions;
  uint32_t max_collisions;
  perf::Counter *n_update;
  perf::Counter *n_update_value;
  perf::Counter *n_replace;
  perf::Counter *n_forget;
  perf::Counter *n_drop;
  perf::Counter *sz_allocated;

  explicit Counters(perf::StatisticsTemplate statistics) {
    sz_size = statistics.RegisterTemplated("sz_size", "Total size");
    num_collisions = 0;
    max_collisions = 0;
    n_hit = statistics.RegisterTemplated("n_hit", "Number of hits");
    n_miss = statistics.RegisterTemplated("n_miss", "Number of misses");
    n_insert = statistics.RegisterTemplated("n_insert", "Number of inserts");
    n_insert_negative = statistics.RegisterTemplated("n_insert_negative",
        "Number of negative inserts");
    n_update = statistics.RegisterTemplated("n_update",
        "Number of updates");
    n_update_value = statistics.RegisterTemplated("n_update_value",
        "Number of value changes");
    n_replace = statistics.RegisterTemplated("n_replace", "Number of replaces");
    n_forget = statistics.RegisterTemplated("n_forget", "Number of forgets");
    n_drop = statistics.RegisterTemplated("n_drop", "Number of drops");
    sz_allocated = statistics.RegisterTemplated("sz_allocated",
        "Number of allocated bytes ");
  }
};


template<class Key, class Value>
class LruCache : SingleCopy {
 private:
  // Forward declarations of private internal data structures
  template<class T> class ListEntry;
  template<class T> class ListEntryHead;
  template<class T> class ListEntryContent;
  template<class M> class MemoryAllocator;

  // Helpers to get the template magic right
  typedef ListEntryContent<Key> ConcreteListEntryContent;
  typedef MemoryAllocator<ConcreteListEntryContent> ConcreteMemoryAllocator;

  typedef struct {
    ListEntryContent<Key> *list_entry;
    Value value;
  } CacheEntry;

  // static uint64_t GetEntrySize() { return sizeof(Key) + sizeof(Value); }

  template<class T> class MemoryAllocator : SingleCopy {
   public:
    explicit MemoryAllocator(const unsigned int num_slots) {
      // how many bitmap chunks (chars) do we need?
      unsigned int num_bytes_bitmap = num_slots / 8;
      bits_per_block_ = 8 * sizeof(bitmap_[0]);
      assert((num_slots % bits_per_block_) == 0);
      assert(num_slots >= 2*bits_per_block_);

      // How much actual memory do we need?
      const unsigned int num_bytes_memory = sizeof(T) * num_slots;

      // Allocate zero'd memory
      bitmap_ = reinterpret_cast<uint64_t *>(scalloc(num_bytes_bitmap, 1));
      memory_ = reinterpret_cast<T *>(scalloc(num_bytes_memory, 1));

      // Create initial state
      num_slots_ = num_slots;
      num_free_slots_ = num_slots;
      next_free_slot_ = 0;
      bytes_allocated_ = num_bytes_bitmap + num_bytes_memory;
    }

    static double GetEntrySize() {
      return static_cast<double>(sizeof(T)) + 1.0/8.0;
    }

    virtual ~MemoryAllocator() {
      free(bitmap_);
      free(memory_);
    }

    inline bool IsFull() const { return num_free_slots_ == 0; }

    T* Construct(const T object) {
      T* mem = Allocate();
      if (mem != NULL) {
        new (static_cast<void*>(mem)) T(object);
      }
      return mem;
    }

    void Destruct(T *object) {
      object->~T();
      Deallocate(object);
    }

    T* Allocate() {
      if (this->IsFull())
        return NULL;

      // Allocate a slot
      this->SetBit(next_free_slot_);
      --num_free_slots_;
      T *slot = memory_ + next_free_slot_;

      // Find a new free slot if there are some left
      if (!this->IsFull()) {
        unsigned bitmap_block = next_free_slot_ / bits_per_block_;
        while (~bitmap_[bitmap_block] == 0)
          bitmap_block = (bitmap_block + 1) % (num_slots_ / bits_per_block_);
        // TODO(jblomer): faster search inside the int
        next_free_slot_ = bitmap_block * bits_per_block_;
        while (this->GetBit(next_free_slot_))
          next_free_slot_++;
      }

      return slot;
    }

    void Deallocate(T* slot) {
      // Check if given slot is in bounds
      assert((slot >= memory_) && (slot <= memory_ + num_slots_));

      // Get position of slot
      const unsigned int position = slot - memory_;

      // Check if slot was already freed
      assert(this->GetBit(position));

      // Free slot, save the position of this slot as free (faster reallocation)
      this->UnsetBit(position);
      next_free_slot_ = position;
      ++num_free_slots_;
    }

    uint64_t bytes_allocated() { return bytes_allocated_; }

   private:
    inline bool GetBit(const unsigned position) {
      assert(position < num_slots_);
      return ((bitmap_[position / bits_per_block_] &
               (uint64_t(1) << (position % bits_per_block_))) != 0);
    }

    inline void SetBit(const unsigned position) {
      assert(position < num_slots_);
      bitmap_[position / bits_per_block_] |=
        uint64_t(1) << (position % bits_per_block_);
    }

    inline void UnsetBit(const unsigned position) {
      assert(position < num_slots_);
      bitmap_[position / bits_per_block_] &=
        ~(uint64_t(1) << (position % bits_per_block_));
    }

    unsigned int num_slots_;  
    unsigned int num_free_slots_;  
    unsigned int next_free_slot_;  
    uint64_t bytes_allocated_;
    uint64_t *bitmap_;  
    unsigned bits_per_block_;
    T *memory_;  
  };


  template<class T> class ListEntry {
  friend class LruCache;
   public:
    ListEntry() {
      this->next = this;
      this->prev = this;
    }

    ListEntry(const ListEntry<T> &other) {
      next = (other.next == &other) ? this : other.next;
      prev = (other.prev == &other) ? this : other.prev;
    }

    virtual ~ListEntry() {}

    virtual bool IsListHead() const = 0;

    bool IsLonely() const { return (this->next == this && this->prev == this); }

    ListEntry<T> *next;  
    ListEntry<T> *prev;  
   protected:
    inline void InsertAsSuccessor(ListEntryContent<T> *entry) {
      assert(entry->IsLonely());

      // Mount the new element between this and this->next
      entry->next = this->next;
      entry->prev = this;

      // Fix pointers of existing list elements
      this->next->prev = entry;
      this->next = entry;
      assert(!entry->IsLonely());
    }

    inline void InsertAsPredecessor(ListEntryContent<T> *entry) {
      assert(entry->IsLonely());
      assert(!entry->IsListHead());

      // Mount the new element between this and this->prev
      entry->next = this;
      entry->prev = this->prev;

      // Fix pointers of existing list elements
      this->prev->next = entry;
      this->prev = entry;

      assert(!entry->IsLonely());
    }

    virtual void RemoveFromList() = 0;

   private:
    // No assignment operator (enforced by linker error)
    ListEntry<T>& operator=(const ListEntry<T> &other);
  };  // template<class T> class ListEntry

  template<class T> class ListEntryContent : public ListEntry<T> {
   public:
    explicit ListEntryContent(T content) {
      content_ = content;
    }

    inline bool IsListHead() const { return false; }
    inline T content() const { return content_; }

    inline void RemoveFromList() {
      assert(!this->IsLonely());

      // Remove this from list
      this->prev->next = this->next;
      this->next->prev = this->prev;

      // Make this lonely
      this->next = this;
      this->prev = this;
    }

   private:
    T content_;  
  };

  template<class T> class ListEntryHead : public ListEntry<T> {
   public:
    explicit ListEntryHead(ConcreteMemoryAllocator *allocator) :
      allocator_(allocator) {}

    virtual ~ListEntryHead() {
      this->clear();
    }

    void clear() {
      // Delete all list entries
      ListEntry<T> *entry = this->next;
      ListEntry<T> *delete_me;
      while (!entry->IsListHead()) {
        delete_me = entry;
        entry = entry->next;
        allocator_->Destruct(static_cast<ConcreteListEntryContent*>(delete_me));
      }

      // Reset the list to lonely
      this->next = this;
      this->prev = this;
    }

    inline bool IsListHead() const { return true; }
    inline bool IsEmpty() const { return this->IsLonely(); }

    inline ListEntryContent<T>* PushBack(T content) {
      ListEntryContent<T> *new_entry =
        allocator_->Construct(ListEntryContent<T>(content));
      this->InsertAsPredecessor(new_entry);
      return new_entry;
    }

    inline T PopFront() {
      assert(!this->IsEmpty());
      return Pop(this->next);
    }

    inline void MoveToBack(ListEntryContent<T> *entry) {
      assert(!entry->IsLonely());

      entry->RemoveFromList();
      this->InsertAsPredecessor(entry);
    }

    inline void RemoveFromList() { assert(false); }

   private:
    inline T Pop(ListEntry<T> *popped_entry) {
      assert(!popped_entry->IsListHead());

      ListEntryContent<T> *popped = (ListEntryContent<T> *)popped_entry;
      popped->RemoveFromList();
      T result = popped->content();
      allocator_->Destruct(static_cast<ConcreteListEntryContent*>(
        popped_entry));
      return result;
    }

   private:
    ConcreteMemoryAllocator *allocator_;
  };

 public:  // LruCache
  LruCache(const unsigned   cache_size,
           const Key       &empty_key,
           uint32_t (*hasher)(const Key &key),
           perf::StatisticsTemplate statistics) :
    counters_(statistics),
    pause_(false),
    cache_gauge_(0),
    cache_size_(cache_size),
    allocator_(cache_size),
    lru_list_(&allocator_)
  {
    assert(cache_size > 0);

    counters_.sz_size->Set(cache_size_);
    filter_entry_ = NULL;
    // cache_ = Cache(cache_size_);
    cache_.Init(cache_size_, empty_key, hasher);
    perf::Xadd(counters_.sz_allocated, allocator_.bytes_allocated() +
                  cache_.bytes_allocated());

#ifdef LRU_CACHE_THREAD_SAFE
    int retval = pthread_mutex_init(&lock_, NULL);
    assert(retval == 0);
#endif
  }

  static double GetEntrySize() {
    return SmallHashFixed<Key, CacheEntry>::GetEntrySize() +
           ConcreteMemoryAllocator::GetEntrySize();
  }

  virtual ~LruCache() {
#ifdef LRU_CACHE_THREAD_SAFE
    pthread_mutex_destroy(&lock_);
#endif
  }

  virtual bool Insert(const Key &key, const Value &value) {
    this->Lock();
    if (pause_) {
      Unlock();
      return false;
    }

    CacheEntry entry;

    // Check if we have to update an existent entry
    if (this->DoLookup(key, &entry)) {
      perf::Inc(counters_.n_update);
      entry.value = value;
      cache_.Insert(key, entry);
      this->Touch(entry);
      this->Unlock();
      return false;
    }

    perf::Inc(counters_.n_insert);
    // Check if we have to make some space in the cache a
    if (this->IsFull())
      this->DeleteOldest();

    entry.list_entry = lru_list_.PushBack(key);
    entry.value = value;

    cache_.Insert(key, entry);
    cache_gauge_++;

    Unlock();
    return true;
  }


  virtual void Update(const Key &key) {
    Lock();
    // Is not called from the client, only from the cache plugin
    assert(!pause_);
    CacheEntry entry;
    bool retval = DoLookup(key, &entry);
    assert(retval);
    perf::Inc(counters_.n_update);
    Touch(entry);
    Unlock();
  }


  virtual bool UpdateValue(const Key &key, const Value &value) {
    this->Lock();
    if (pause_) {
      Unlock();
      return false;
    }

    CacheEntry entry;
    if (!this->DoLookup(key, &entry)) {
      this->Unlock();
      return false;
    }

    perf::Inc(counters_.n_update_value);
    entry.value = value;
    cache_.Insert(key, entry);
    this->Unlock();
    return true;
  }


  virtual bool Lookup(const Key &key, Value *value, bool update_lru = true) {
    bool found = false;
    Lock();
    if (pause_) {
      Unlock();
      return false;
    }

    CacheEntry entry;
    if (DoLookup(key, &entry)) {
      // Hit
      perf::Inc(counters_.n_hit);
      if (update_lru)
        Touch(entry);
      *value = entry.value;
      found = true;
    } else {
      perf::Inc(counters_.n_miss);
    }

    Unlock();
    return found;
  }

  virtual bool Forget(const Key &key) {
    bool found = false;
    this->Lock();
    if (pause_) {
      Unlock();
      return false;
    }

    CacheEntry entry;
    if (this->DoLookup(key, &entry)) {
      found = true;
      perf::Inc(counters_.n_forget);

      entry.list_entry->RemoveFromList();
      allocator_.Destruct(entry.list_entry);
      cache_.Erase(key);
      --cache_gauge_;
    }

    this->Unlock();
    return found;
  }

  virtual void Drop() {
    this->Lock();

    cache_gauge_ = 0;
    lru_list_.clear();
    cache_.Clear();
    perf::Inc(counters_.n_drop);
    counters_.sz_allocated->Set(0);
    perf::Xadd(counters_.sz_allocated, allocator_.bytes_allocated() +
                  cache_.bytes_allocated());

    this->Unlock();
  }

  void Pause() {
    Lock();
    pause_ = true;
    Unlock();
  }

  void Resume() {
    Lock();
    pause_ = false;
    Unlock();
  }

  inline bool IsFull() const { return cache_gauge_ >= cache_size_; }
  inline bool IsEmpty() const { return cache_gauge_ == 0; }

  Counters counters() {
    Lock();
    cache_.GetCollisionStats(&counters_.num_collisions,
                             &counters_.max_collisions);
    Unlock();
    return counters_;
  }

  virtual void FilterBegin() {
    assert(!filter_entry_);
    Lock();
    filter_entry_ = &lru_list_;
  }

  virtual void FilterGet(Key *key, Value *value) {
    CacheEntry entry;
    assert(filter_entry_);
    assert(!filter_entry_->IsListHead());
    *key = static_cast<ConcreteListEntryContent *>(filter_entry_)->content();
    bool rc = this->DoLookup(*key, &entry);
    assert(rc);
    *value = entry.value;
  }

  virtual bool FilterNext() {
    assert(filter_entry_);
    filter_entry_ = filter_entry_->next;
    return !filter_entry_->IsListHead();
  }

  virtual void FilterDelete() {
    assert(filter_entry_);
    assert(!filter_entry_->IsListHead());
    ListEntry<Key> *new_current = filter_entry_->prev;
    perf::Inc(counters_.n_forget);
    Key k = static_cast<ConcreteListEntryContent *>(filter_entry_)->content();
    filter_entry_->RemoveFromList();
    allocator_.Destruct(static_cast<ConcreteListEntryContent *>(filter_entry_));
    cache_.Erase(k);
    --cache_gauge_;
    filter_entry_ = new_current;
  }

  virtual void FilterEnd() {
    assert(filter_entry_);
    filter_entry_ = NULL;
    Unlock();
  }

 protected:
  Counters counters_;

 private:
  inline bool DoLookup(const Key &key, CacheEntry *entry) {
    return cache_.Lookup(key, entry);
  }

  inline void Touch(const CacheEntry &entry) {
    lru_list_.MoveToBack(entry.list_entry);
  }

  inline void DeleteOldest() {
    assert(!this->IsEmpty());

    perf::Inc(counters_.n_replace);
    Key delete_me = lru_list_.PopFront();
    cache_.Erase(delete_me);

    --cache_gauge_;
  }

  inline void Lock() {
#ifdef LRU_CACHE_THREAD_SAFE
    pthread_mutex_lock(&lock_);
#endif
  }

  inline void Unlock() {
#ifdef LRU_CACHE_THREAD_SAFE
    pthread_mutex_unlock(&lock_);
#endif
  }

  bool pause_;  
  // Internal data fields
  unsigned int            cache_gauge_;
  const unsigned int      cache_size_;
  ConcreteMemoryAllocator allocator_;

  ListEntryHead<Key>              lru_list_;
  SmallHashFixed<Key, CacheEntry> cache_;

  ListEntry<Key> *filter_entry_;
#ifdef LRU_CACHE_THREAD_SAFE
  pthread_mutex_t lock_;  
#endif
};  // class LruCache

}  // namespace lru

#endif  // CVMFS_LRU_H_