]>
git.proxmox.com Git - ceph.git/blob - ceph/src/rocksdb/util/dynamic_bloom.h
1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
10 #include "rocksdb/slice.h"
12 #include "port/port.h"
13 #include "util/hash.h"
26 // allocator: pass allocator to bloom filter, hence trace the usage of memory
27 // total_bits: fixed total bits for the bloom
28 // num_probes: number of hash probes for a single key
29 // locality: If positive, optimize for cache line locality, 0 otherwise.
30 // hash_func: customized hash function
31 // huge_page_tlb_size: if >0, try to allocate bloom bytes from huge page TLB
32 // within this page size. Need to reserve huge pages for
33 // it to be allocated, like:
34 // sysctl -w vm.nr_hugepages=20
35 // See linux doc Documentation/vm/hugetlbpage.txt
36 explicit DynamicBloom(Allocator
* allocator
,
37 uint32_t total_bits
, uint32_t locality
= 0,
38 uint32_t num_probes
= 6,
39 size_t huge_page_tlb_size
= 0,
40 Logger
* logger
= nullptr);
42 explicit DynamicBloom(uint32_t num_probes
= 6);
44 void SetTotalBits(Allocator
* allocator
, uint32_t total_bits
,
45 uint32_t locality
, size_t huge_page_tlb_size
,
50 // Assuming single threaded access to this function.
51 void Add(const Slice
& key
);
53 // Like Add, but may be called concurrent with other functions.
54 void AddConcurrently(const Slice
& key
);
56 // Assuming single threaded access to this function.
57 void AddHash(uint32_t hash
);
59 // Like AddHash, but may be called concurrent with other functions.
60 void AddHashConcurrently(uint32_t hash
);
62 // Multithreaded access to this function is OK
63 bool MayContain(const Slice
& key
) const;
65 // Multithreaded access to this function is OK
66 bool MayContainHash(uint32_t hash
) const;
68 void Prefetch(uint32_t h
);
70 uint32_t GetNumBlocks() const { return kNumBlocks
; }
72 Slice
GetRawData() const {
73 return Slice(reinterpret_cast<char*>(data_
), GetTotalBits() / 8);
76 void SetRawData(unsigned char* raw_data
, uint32_t total_bits
,
77 uint32_t num_blocks
= 0);
79 uint32_t GetTotalBits() const { return kTotalBits
; }
81 bool IsInitialized() const { return kNumBlocks
> 0 || kTotalBits
> 0; }
86 const uint32_t kNumProbes
;
88 std::atomic
<uint8_t>* data_
;
90 // or_func(ptr, mask) should effect *ptr |= mask with the appropriate
91 // concurrency safety, working with bytes.
92 template <typename OrFunc
>
93 void AddHash(uint32_t hash
, const OrFunc
& or_func
);
96 inline void DynamicBloom::Add(const Slice
& key
) { AddHash(BloomHash(key
)); }
98 inline void DynamicBloom::AddConcurrently(const Slice
& key
) {
99 AddHashConcurrently(BloomHash(key
));
102 inline void DynamicBloom::AddHash(uint32_t hash
) {
103 AddHash(hash
, [](std::atomic
<uint8_t>* ptr
, uint8_t mask
) {
104 ptr
->store(ptr
->load(std::memory_order_relaxed
) | mask
,
105 std::memory_order_relaxed
);
109 inline void DynamicBloom::AddHashConcurrently(uint32_t hash
) {
110 AddHash(hash
, [](std::atomic
<uint8_t>* ptr
, uint8_t mask
) {
111 // Happens-before between AddHash and MaybeContains is handled by
112 // access to versions_->LastSequence(), so all we have to do here is
113 // avoid races (so we don't give the compiler a license to mess up
114 // our code) and not lose bits. std::memory_order_relaxed is enough
116 if ((mask
& ptr
->load(std::memory_order_relaxed
)) != mask
) {
117 ptr
->fetch_or(mask
, std::memory_order_relaxed
);
122 inline bool DynamicBloom::MayContain(const Slice
& key
) const {
123 return (MayContainHash(BloomHash(key
)));
126 #if defined(_MSC_VER)
127 #pragma warning(push)
128 // local variable is initialized but not referenced
129 #pragma warning(disable : 4189)
131 inline void DynamicBloom::Prefetch(uint32_t h
) {
132 if (kNumBlocks
!= 0) {
133 uint32_t b
= ((h
>> 11 | (h
<< 21)) % kNumBlocks
) * (CACHE_LINE_SIZE
* 8);
134 PREFETCH(&(data_
[b
/ 8]), 0, 3);
137 #if defined(_MSC_VER)
141 inline bool DynamicBloom::MayContainHash(uint32_t h
) const {
142 assert(IsInitialized());
143 const uint32_t delta
= (h
>> 17) | (h
<< 15); // Rotate right 17 bits
144 if (kNumBlocks
!= 0) {
145 uint32_t b
= ((h
>> 11 | (h
<< 21)) % kNumBlocks
) * (CACHE_LINE_SIZE
* 8);
146 for (uint32_t i
= 0; i
< kNumProbes
; ++i
) {
147 // Since CACHE_LINE_SIZE is defined as 2^n, this line will be optimized
148 // to a simple and operation by compiler.
149 const uint32_t bitpos
= b
+ (h
% (CACHE_LINE_SIZE
* 8));
150 uint8_t byteval
= data_
[bitpos
/ 8].load(std::memory_order_relaxed
);
151 if ((byteval
& (1 << (bitpos
% 8))) == 0) {
154 // Rotate h so that we don't reuse the same bytes.
155 h
= h
/ (CACHE_LINE_SIZE
* 8) +
156 (h
% (CACHE_LINE_SIZE
* 8)) * (0x20000000U
/ CACHE_LINE_SIZE
);
160 for (uint32_t i
= 0; i
< kNumProbes
; ++i
) {
161 const uint32_t bitpos
= h
% kTotalBits
;
162 uint8_t byteval
= data_
[bitpos
/ 8].load(std::memory_order_relaxed
);
163 if ((byteval
& (1 << (bitpos
% 8))) == 0) {
172 template <typename OrFunc
>
173 inline void DynamicBloom::AddHash(uint32_t h
, const OrFunc
& or_func
) {
174 assert(IsInitialized());
175 const uint32_t delta
= (h
>> 17) | (h
<< 15); // Rotate right 17 bits
176 if (kNumBlocks
!= 0) {
177 uint32_t b
= ((h
>> 11 | (h
<< 21)) % kNumBlocks
) * (CACHE_LINE_SIZE
* 8);
178 for (uint32_t i
= 0; i
< kNumProbes
; ++i
) {
179 // Since CACHE_LINE_SIZE is defined as 2^n, this line will be optimized
180 // to a simple and operation by compiler.
181 const uint32_t bitpos
= b
+ (h
% (CACHE_LINE_SIZE
* 8));
182 or_func(&data_
[bitpos
/ 8], (1 << (bitpos
% 8)));
183 // Rotate h so that we don't reuse the same bytes.
184 h
= h
/ (CACHE_LINE_SIZE
* 8) +
185 (h
% (CACHE_LINE_SIZE
* 8)) * (0x20000000U
/ CACHE_LINE_SIZE
);
189 for (uint32_t i
= 0; i
< kNumProbes
; ++i
) {
190 const uint32_t bitpos
= h
% kTotalBits
;
191 or_func(&data_
[bitpos
/ 8], (1 << (bitpos
% 8)));