cache.cpp

#include "cache.hpp"
#include "fast_hash.hpp"
#include <limits>

namespace AppenDB {
  namespace Cache {
    // TODO: use a custom memory allocator for this

    Cacheable::CachePool Cacheable::pools[Constants::NUM_SHARD_PARTITIONS];

    size_t Cacheable::CachePool::pick_bucket(const char *key_begin, size_t key_length){
      return hash64(key_begin, key_length) % HASHTABLE_SIZE;
    }

    void Cacheable::CachePool::free_entry(CacheEntry*& entry){
      assert(entry->cacheable()->is_evictable());

      // destroy cacheable
      Cacheable* cacheable = entry->cacheable();
      cacheable->~Cacheable();

      // destroy cache entry
      size_t const memory_used = entry->total_memory_allocated;
      ::operator delete(entry);

      // accounting
      total_memory_used -= (ACCOUNTING_OVERHEAD_SIZE_OF_EACH_CACHE_ENTRY + memory_used);

      // fix up the ones after this
      CacheEntry** iterator = &entry;
      for(;;){
        CacheEntry **next = hash_table + ((iterator - hash_table + 1) % HASHTABLE_SIZE);
        if(!*next){ *iterator = 0; break; }
        size_t const next_bucket = pick_bucket((*next)->extra + (*next)->offset_to_key_begin, (*next)->key_length);
        if(next_bucket == static_cast<size_t>(next - hash_table)){ *iterator = 0; break; }
        *iterator = *next;
        ++iterator;
      }
    }

    CacheEntry*& Cacheable::CachePool::find_cacheable(const char *key_begin, size_t key_length){
      size_t bucket_index = pick_bucket(key_begin, key_length);
      for(;;){
        CacheEntry*& entry = hash_table[bucket_index];
        if(!entry) return entry;
        if(
          (entry->key_length == key_length) &&
          (0 == ::std::memcmp(entry->extra + entry->offset_to_key_begin, key_begin, key_length))
        ) return entry;
        bucket_index = (bucket_index + 1) % HASHTABLE_SIZE;
      }
    }

    void Cacheable::CachePool::_evict(const char *key_begin, size_t key_length){
      CacheEntry*& entry = find_cacheable(key_begin, key_length);
      if(!entry) return;
      free_entry(entry);
    }

    void Cacheable::CachePool::create_entry(CacheEntry*& entry, size_t cast_offset, size_t cacheable_size, const char *key_begin, size_t key_length){
      size_t const memory_needed = cacheable_size + key_length + sizeof(CacheEntry);
      total_memory_used += ACCOUNTING_OVERHEAD_SIZE_OF_EACH_CACHE_ENTRY + memory_needed;
      entry = reinterpret_cast<CacheEntry*>(::operator new(memory_needed));
      entry->offset_to_key_begin = cacheable_size;
      entry->key_length = key_length;
      entry->offset_to_cacheable = cast_offset;
      entry->total_memory_allocated = memory_needed;
      ::std::memcpy(entry->extra + entry->offset_to_key_begin, key_begin, key_length);
    }

    void Cacheable::CachePool::find_something_to_free_from_the_cache(){
      size_t num_considered = 0;
      unsigned int last_used_best = ::std::numeric_limits<unsigned int>::max();
      size_t cache_entry_best;
      for(;;){
        if(num_considered == CACHE_FREE_SAMPLE_RATE) break;
        CacheEntry *entry = hash_table[next_entry_to_check_for_eviction];
        if(entry){
          Cacheable* cacheable = entry->cacheable();
          if(cacheable->is_evictable()){
            ++num_considered;
            unsigned int time_since_use = last_used_counter - cacheable->last_used();
            if(last_used_best > time_since_use){
              cache_entry_best = next_entry_to_check_for_eviction;
              last_used_best = time_since_use;
            }
          }
        }
        next_entry_to_check_for_eviction = (next_entry_to_check_for_eviction + 1) % HASHTABLE_SIZE;
      }
      free_entry(hash_table[cache_entry_best]);
    }

    Cacheable::~Cacheable(){
      _pool.cache_eviction();
      --_pool.num_cached_items;
      assert(_num_locks == 0);
      assert(_ready);
      assert(_memory_used == 0);
    }

    Cacheable::Cacheable(CachePool &pool) : _num_locks(0), _memory_used(0), _ready(false), _callbacks(0), _num_callbacks(0), _callback_capacity(0), _pool(pool) { ++_pool.num_cached_items; }

    Cacheable* Cacheable::CachePool::_try_fetch_cacheable(const char *key_begin, size_t key_length){
      CacheEntry*& cache_entry = find_cacheable(key_begin, key_length);
      return (cache_entry) ? (cache_entry)->cacheable() : 0;
    }

    char* Cacheable::CachePool::_create_cacheable_entry(size_t cast_offset, size_t cacheable_size, const char *key_begin, size_t key_length){
      if((num_cached_items == MAX_CACHED_ITEMS) || (total_memory_used > CACHE_HIGH_WATER_MARK)) find_something_to_free_from_the_cache();

      size_t bucket_index = pick_bucket(key_begin, key_length);
      for(;;){
        CacheEntry*& entry = hash_table[bucket_index];
        if(!entry){
          create_entry(entry, cast_offset, cacheable_size, key_begin, key_length);
          return entry->extra + entry->offset_to_cacheable;
        }
        bucket_index = (bucket_index + 1) % HASHTABLE_SIZE;
      }
    }

    void Cacheable::set_as_used_now(){
      _last_used = ++_pool.last_used_counter;
    }

    void* Cacheable::allocate_memory(size_t size){
      size_t const memory_counted = size + ACCOUNTING_OVERHEAD_SIZE_OF_EACH_ALLOCATION;
      _pool.total_memory_used += memory_counted;
      _memory_used += memory_counted;
      if(_pool.total_memory_used > CACHE_SIZE) _pool.find_something_to_free_from_the_cache();
      auto rv = ::operator new(size);
      return rv;
    }

    // cacheables should use this to free memory
    void Cacheable::free_memory(void* memory, size_t size){
      size_t const memory_counted = size + ACCOUNTING_OVERHEAD_SIZE_OF_EACH_ALLOCATION;
      assert(memory_counted <= _memory_used);
      _pool.total_memory_used -= memory_counted;
      _memory_used -= memory_counted;
      ::operator delete(memory);
    }
  }
}