ceph/src/rocksdb/util/dynamic_bloom.h

   1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
   2 // This source code is licensed under the BSD-style license found in the
   3 // LICENSE file in the root directory of this source tree. An additional grant
   4 // of patent rights can be found in the PATENTS file in the same directory.
   5
   6 #pragma once
   7
   8 #include <string>
   9
  10 #include "rocksdb/slice.h"
  11
  12 #include "port/port.h"
  13
  14 #include <atomic>
  15 #include <memory>
  16
  17 namespace rocksdb {
  18
  19 class Slice;
  20 class Allocator;
  21 class Logger;
  22
  23 class DynamicBloom {
  24  public:
  25   // allocator: pass allocator to bloom filter, hence trace the usage of memory
  26   // total_bits: fixed total bits for the bloom
  27   // num_probes: number of hash probes for a single key
  28   // locality:  If positive, optimize for cache line locality, 0 otherwise.
  29   // hash_func:  customized hash function
  30   // huge_page_tlb_size:  if >0, try to allocate bloom bytes from huge page TLB
  31   //                      withi this page size. Need to reserve huge pages for
  32   //                      it to be allocated, like:
  33   //                         sysctl -w vm.nr_hugepages=20
  34   //                     See linux doc Documentation/vm/hugetlbpage.txt
  35   explicit DynamicBloom(Allocator* allocator,
  36                         uint32_t total_bits, uint32_t locality = 0,
  37                         uint32_t num_probes = 6,
  38                         uint32_t (*hash_func)(const Slice& key) = nullptr,
  39                         size_t huge_page_tlb_size = 0,
  40                         Logger* logger = nullptr);
  41
  42   explicit DynamicBloom(uint32_t num_probes = 6,
  43                         uint32_t (*hash_func)(const Slice& key) = nullptr);
  44
  45   void SetTotalBits(Allocator* allocator, uint32_t total_bits,
  46                     uint32_t locality, size_t huge_page_tlb_size,
  47                     Logger* logger);
  48
  49   ~DynamicBloom() {}
  50
  51   // Assuming single threaded access to this function.
  52   void Add(const Slice& key);
  53
  54   // Like Add, but may be called concurrent with other functions.
  55   void AddConcurrently(const Slice& key);
  56
  57   // Assuming single threaded access to this function.
  58   void AddHash(uint32_t hash);
  59
  60   // Like AddHash, but may be called concurrent with other functions.
  61   void AddHashConcurrently(uint32_t hash);
  62
  63   // Multithreaded access to this function is OK
  64   bool MayContain(const Slice& key) const;
  65
  66   // Multithreaded access to this function is OK
  67   bool MayContainHash(uint32_t hash) const;
  68
  69   void Prefetch(uint32_t h);
  70
  71   uint32_t GetNumBlocks() const { return kNumBlocks; }
  72
  73   Slice GetRawData() const {
  74     return Slice(reinterpret_cast<char*>(data_), GetTotalBits() / 8);
  75   }
  76
  77   void SetRawData(unsigned char* raw_data, uint32_t total_bits,
  78                   uint32_t num_blocks = 0);
  79
  80   uint32_t GetTotalBits() const { return kTotalBits; }
  81
  82   bool IsInitialized() const { return kNumBlocks > 0 || kTotalBits > 0; }
  83
  84  private:
  85   uint32_t kTotalBits;
  86   uint32_t kNumBlocks;
  87   const uint32_t kNumProbes;
  88
  89   uint32_t (*hash_func_)(const Slice& key);
  90   std::atomic<uint8_t>* data_;
  91
  92   // or_func(ptr, mask) should effect *ptr |= mask with the appropriate
  93   // concurrency safety, working with bytes.
  94   template <typename OrFunc>
  95   void AddHash(uint32_t hash, const OrFunc& or_func);
  96 };
  97
  98 inline void DynamicBloom::Add(const Slice& key) { AddHash(hash_func_(key)); }
  99
 100 inline void DynamicBloom::AddConcurrently(const Slice& key) {
 101   AddHashConcurrently(hash_func_(key));
 102 }
 103
 104 inline void DynamicBloom::AddHash(uint32_t hash) {
 105   AddHash(hash, [](std::atomic<uint8_t>* ptr, uint8_t mask) {
 106     ptr->store(ptr->load(std::memory_order_relaxed) | mask,
 107                std::memory_order_relaxed);
 108   });
 109 }
 110
 111 inline void DynamicBloom::AddHashConcurrently(uint32_t hash) {
 112   AddHash(hash, [](std::atomic<uint8_t>* ptr, uint8_t mask) {
 113     // Happens-before between AddHash and MaybeContains is handled by
 114     // access to versions_->LastSequence(), so all we have to do here is
 115     // avoid races (so we don't give the compiler a license to mess up
 116     // our code) and not lose bits.  std::memory_order_relaxed is enough
 117     // for that.
 118     if ((mask & ptr->load(std::memory_order_relaxed)) != mask) {
 119       ptr->fetch_or(mask, std::memory_order_relaxed);
 120     }
 121   });
 122 }
 123
 124 inline bool DynamicBloom::MayContain(const Slice& key) const {
 125   return (MayContainHash(hash_func_(key)));
 126 }
 127
 128 inline void DynamicBloom::Prefetch(uint32_t h) {
 129   if (kNumBlocks != 0) {
 130     uint32_t b = ((h >> 11 | (h << 21)) % kNumBlocks) * (CACHE_LINE_SIZE * 8);
 131     PREFETCH(&(data_[b / 8]), 0, 3);
 132   }
 133 }
 134
 135 inline bool DynamicBloom::MayContainHash(uint32_t h) const {
 136   assert(IsInitialized());
 137   const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
 138   if (kNumBlocks != 0) {
 139     uint32_t b = ((h >> 11 | (h << 21)) % kNumBlocks) * (CACHE_LINE_SIZE * 8);
 140     for (uint32_t i = 0; i < kNumProbes; ++i) {
 141       // Since CACHE_LINE_SIZE is defined as 2^n, this line will be optimized
 142       //  to a simple and operation by compiler.
 143       const uint32_t bitpos = b + (h % (CACHE_LINE_SIZE * 8));
 144       uint8_t byteval = data_[bitpos / 8].load(std::memory_order_relaxed);
 145       if ((byteval & (1 << (bitpos % 8))) == 0) {
 146         return false;
 147       }
 148       // Rotate h so that we don't reuse the same bytes.
 149       h = h / (CACHE_LINE_SIZE * 8) +
 150           (h % (CACHE_LINE_SIZE * 8)) * (0x20000000U / CACHE_LINE_SIZE);
 151       h += delta;
 152     }
 153   } else {
 154     for (uint32_t i = 0; i < kNumProbes; ++i) {
 155       const uint32_t bitpos = h % kTotalBits;
 156       uint8_t byteval = data_[bitpos / 8].load(std::memory_order_relaxed);
 157       if ((byteval & (1 << (bitpos % 8))) == 0) {
 158         return false;
 159       }
 160       h += delta;
 161     }
 162   }
 163   return true;
 164 }
 165
 166 template <typename OrFunc>
 167 inline void DynamicBloom::AddHash(uint32_t h, const OrFunc& or_func) {
 168   assert(IsInitialized());
 169   const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
 170   if (kNumBlocks != 0) {
 171     uint32_t b = ((h >> 11 | (h << 21)) % kNumBlocks) * (CACHE_LINE_SIZE * 8);
 172     for (uint32_t i = 0; i < kNumProbes; ++i) {
 173       // Since CACHE_LINE_SIZE is defined as 2^n, this line will be optimized
 174       // to a simple and operation by compiler.
 175       const uint32_t bitpos = b + (h % (CACHE_LINE_SIZE * 8));
 176       or_func(&data_[bitpos / 8], (1 << (bitpos % 8)));
 177       // Rotate h so that we don't reuse the same bytes.
 178       h = h / (CACHE_LINE_SIZE * 8) +
 179           (h % (CACHE_LINE_SIZE * 8)) * (0x20000000U / CACHE_LINE_SIZE);
 180       h += delta;
 181     }
 182   } else {
 183     for (uint32_t i = 0; i < kNumProbes; ++i) {
 184       const uint32_t bitpos = h % kTotalBits;
 185       or_func(&data_[bitpos / 8], (1 << (bitpos % 8)));
 186       h += delta;
 187     }
 188   }
 189 }
 190
 191 }  // rocksdb