cache_hashtable.hpp

Go to the documentation of this file.

/*
 * Copyright (c) 2014-2015, Hewlett-Packard Development Company, LP.
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 * more details. You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * HP designates this particular file as subject to the "Classpath" exception
 * as provided by HP in the LICENSE.txt file that accompanied this code.
 */
#ifndef FOEDUS_CACHE_CACHE_HASHTABLE_HPP_
#define FOEDUS_CACHE_CACHE_HASHTABLE_HPP_

#include <stdint.h>

#include <iosfwd>

#include "foedus/assert_nd.hpp"
#include "foedus/compiler.hpp"
#include "foedus/cxx11.hpp"
#include "foedus/error_code.hpp"
#include "foedus/error_stack.hpp"
#include "foedus/assorted/atomic_fences.hpp"
#include "foedus/assorted/cacheline.hpp"
#include "foedus/assorted/const_div.hpp"
#include "foedus/cache/fwd.hpp"
#include "foedus/memory/aligned_memory.hpp"
#include "foedus/memory/fwd.hpp"
#include "foedus/memory/memory_id.hpp"
#include "foedus/soc/shared_mutex.hpp"
#include "foedus/storage/page.hpp"
#include "foedus/storage/storage_id.hpp"
#include "foedus/thread/fwd.hpp"

namespace foedus {
namespace cache {

// these are actually of the same integer type, but have very different meanings.
typedef uint32_t BucketId;
typedef memory::PagePoolOffset ContentId;

typedef uint32_t PageIdTag;

typedef uint32_t OverflowPointer;

const uint16_t kHopNeighbors = 16U;

struct HashFunc CXX11_FINAL {
  const BucketId            logical_buckets_;
  const BucketId            physical_buckets_;
  const assorted::ConstDiv  bucket_div_;

  explicit HashFunc(BucketId physical_buckets);

  static uint32_t get_hash(storage::SnapshotPagePointer page_id) ALWAYS_INLINE;
  static PageIdTag get_tag(storage::SnapshotPagePointer page_id) ALWAYS_INLINE;

  BucketId get_bucket_number(storage::SnapshotPagePointer page_id) const ALWAYS_INLINE {
    uint32_t seed = get_hash(page_id);
    uint32_t quotient = bucket_div_.div32(seed);
    uint32_t bucket = bucket_div_.rem32(seed, logical_buckets_, quotient);
    ASSERT_ND(bucket == seed % logical_buckets_);
    return bucket;
  }

  friend std::ostream& operator<<(std::ostream& o, const HashFunc& v);
};

struct CacheBucket CXX11_FINAL {
  uint64_t data_;

  void    reset(ContentId id = 0, PageIdTag tag = 0) {
    data_ = (static_cast<uint64_t>(tag) << 32) | id;
  }

  ContentId get_content_id() const { return data_; }
  void      set_content_id(ContentId id) { data_ = (data_ & 0xFFFFFFFF00000000ULL) | id; }
  bool      is_content_set() const { return get_content_id() != 0; }

  PageIdTag get_tag() const { return static_cast<PageIdTag>(data_ >> 32); }
  void      set_tag(PageIdTag tag) {
    data_ = (data_ & 0x00000000FFFFFFFFULL) | (static_cast<uint64_t>(tag) << 32);
  }
};

struct CacheRefCount CXX11_FINAL {
  uint16_t count_;

  void increment() ALWAYS_INLINE {
    if (count_ < 0xFFFFU) {
      ++count_;
    }
  }
  bool decrement(uint16_t subtract) ALWAYS_INLINE {
    if (count_ >= subtract) {
      count_ -= subtract;
    } else {
      count_ = 0;
    }
    return (count_ > 0);
  }
};

struct CacheOverflowEntry CXX11_FINAL {
  CacheBucket     bucket_;    // +8 -> 8
  OverflowPointer next_;      // +4 -> 12
  CacheRefCount   refcount_;  // +2 -> 14
  uint16_t        padding_;   // +2 -> 16 (unused)
};

class CacheHashtable CXX11_FINAL {
 public:
  enum Constants {
    kMaxFindBatchSize = 32,
  };
  CacheHashtable(BucketId physical_buckets, uint16_t numa_node);

  ContentId find(storage::SnapshotPagePointer page_id) const ALWAYS_INLINE;

  ErrorCode find_batch(
    uint16_t batch_size,
    const storage::SnapshotPagePointer* page_ids,
    ContentId* out) const;

  ErrorCode install(storage::SnapshotPagePointer page_id, ContentId content);

  struct EvictArgs {
    uint64_t  target_count_;
    uint64_t  evicted_count_;
    ContentId* evicted_contents_;
    // probably will add more in/out parameters to fine-tune its behavior later.

    void add_evicted(ContentId content) {
      // because of the loose synchronization, we might get zero. skip it.
      if (content) {
        evicted_contents_[evicted_count_] = content;
        ++evicted_count_;
      }
    }
  };
  void evict(EvictArgs* args);

  BucketId get_logical_buckets() const ALWAYS_INLINE { return hash_func_.logical_buckets_; }
  BucketId get_physical_buckets() const ALWAYS_INLINE { return hash_func_.physical_buckets_; }

  BucketId get_bucket_number(storage::SnapshotPagePointer page_id) const ALWAYS_INLINE {
    return hash_func_.get_bucket_number(page_id);
  }

  ErrorStack verify_single_thread() const;

  const CacheBucket& get_bucket(BucketId bucket_id) const { return buckets_[bucket_id]; }

  struct Stat {
    uint32_t normal_entries_;
    uint32_t overflow_entries_;
  };
  Stat  get_stat_single_thread() const;

  friend std::ostream& operator<<(std::ostream& o, const CacheHashtable& v);

 protected:
  const uint16_t            numa_node_;
  const uint32_t            overflow_buckets_count_;
  const HashFunc            hash_func_;
  memory::AlignedMemory     buckets_memory_;
  memory::AlignedMemory     refcounts_memory_;
  memory::AlignedMemory     overflow_buckets_memory_;

  // these two have the same indexes.
  CacheBucket*              buckets_;
  CacheRefCount*            refcounts_;

  // these are for overflow linked list
  CacheOverflowEntry*       overflow_buckets_;
  OverflowPointer           overflow_buckets_head_;

  OverflowPointer           overflow_free_buckets_head_;

  soc::SharedMutex          overflow_free_buckets_mutex_;

  BucketId                  clockhand_;

  BucketId  evict_main_loop(EvictArgs* args, BucketId cur, uint16_t loop);
  void      evict_overflow_loop(EvictArgs* args, uint16_t loop);
};

inline uint32_t HashFunc::get_hash(storage::SnapshotPagePointer page_id) {
  uint16_t snapshot_id = storage::extract_snapshot_id_from_snapshot_pointer(page_id);
  uint8_t numa_node = storage::extract_numa_node_from_snapshot_pointer(page_id);
  uint64_t local_page_id = storage::extract_local_page_id_from_snapshot_pointer(page_id);
  // snapshot_id is usually very sparse. and has no correlation with local_page_id.
  // numa_node too. thus just use them as seeds for good old multiplicative hashing.
  uint32_t seed = snapshot_id * 0x5a2948074497175aULL;
  seed += numa_node * 0xc30a95f6e63dd908ULL;

  // local_page_id is 40 bits. 32-40 bits are very sparse, and it has no correlation with
  // other bits (how come 4kb-th page and 16Tb+4kb-th page has anything in common..).
  // so, let's treat it with another multiplicative.
  uint8_t highest_bits = static_cast<uint8_t>(local_page_id >> 32);
  uint32_t folded_local_page_id = local_page_id + highest_bits * 0xd3561f5bedac324cULL;

  // now, we don't want to place adjacent pages in adjacent hash buckets. so, let's swap bytes.
  // this benefits hop-scotch hashing table.
  uint32_t swaped_page_id = __builtin_bswap32(folded_local_page_id);
  seed ^= swaped_page_id;
  return seed;
}

inline PageIdTag HashFunc::get_tag(storage::SnapshotPagePointer page_id) {
  PageIdTag high_bits = static_cast<PageIdTag>(page_id >> 32);
  PageIdTag tag = high_bits * 0x8e1d76486c3e638dULL + static_cast<PageIdTag>(page_id);
  if (tag == 0) {
    tag = 1;  // we avoid 0 as a valid value. this enables sanity checks.
  }
  return tag;
}

inline ContentId CacheHashtable::find(storage::SnapshotPagePointer page_id) const {
  ASSERT_ND(page_id > 0);
  BucketId bucket_number = get_bucket_number(page_id);
  ASSERT_ND(bucket_number < get_logical_buckets());

  // we prefetch up to 128 bytes (16 entries).
  assorted::prefetch_cachelines(buckets_ + bucket_number, 2);

  PageIdTag tag = HashFunc::get_tag(page_id);
  ASSERT_ND(tag != 0);
  for (uint16_t i = 0; i < kHopNeighbors; ++i) {
    const CacheBucket& bucket = buckets_[bucket_number + i];
    if (bucket.get_tag() == tag) {
      // found (probably)!
      refcounts_[bucket_number + i].increment();
      return bucket.get_content_id();
    }
  }

  // Not found. let's check overflow list
  if (overflow_buckets_head_) {
    for (OverflowPointer i = overflow_buckets_head_; i != 0;) {
      if (overflow_buckets_[i].bucket_.get_tag() == tag) {
        overflow_buckets_[i].refcount_.increment();
        return overflow_buckets_[i].bucket_.get_content_id();
      }
      i = overflow_buckets_[i].next_;
    }
  }

  return 0;
}

}  // namespace cache
}  // namespace foedus
#endif  // FOEDUS_CACHE_CACHE_HASHTABLE_HPP_