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).
5
6 #include "table/plain/plain_table_bloom.h"
7
8 #include <algorithm>
9 #include <string>
10 #include "util/dynamic_bloom.h"
11
12 #include "memory/allocator.h"
13
14 namespace ROCKSDB_NAMESPACE {
15
16 namespace {
17
GetTotalBitsForLocality(uint32_t total_bits)18 uint32_t GetTotalBitsForLocality(uint32_t total_bits) {
19 uint32_t num_blocks =
20 (total_bits + CACHE_LINE_SIZE * 8 - 1) / (CACHE_LINE_SIZE * 8);
21
22 // Make num_blocks an odd number to make sure more bits are involved
23 // when determining which block.
24 if (num_blocks % 2 == 0) {
25 num_blocks++;
26 }
27
28 return num_blocks * (CACHE_LINE_SIZE * 8);
29 }
30 } // namespace
31
PlainTableBloomV1(uint32_t num_probes)32 PlainTableBloomV1::PlainTableBloomV1(uint32_t num_probes)
33 : kTotalBits(0), kNumBlocks(0), kNumProbes(num_probes), data_(nullptr) {}
34
SetRawData(char * raw_data,uint32_t total_bits,uint32_t num_blocks)35 void PlainTableBloomV1::SetRawData(char* raw_data, uint32_t total_bits,
36 uint32_t num_blocks) {
37 data_ = raw_data;
38 kTotalBits = total_bits;
39 kNumBlocks = num_blocks;
40 }
41
SetTotalBits(Allocator * allocator,uint32_t total_bits,uint32_t locality,size_t huge_page_tlb_size,Logger * logger)42 void PlainTableBloomV1::SetTotalBits(Allocator* allocator, uint32_t total_bits,
43 uint32_t locality,
44 size_t huge_page_tlb_size,
45 Logger* logger) {
46 kTotalBits = (locality > 0) ? GetTotalBitsForLocality(total_bits)
47 : (total_bits + 7) / 8 * 8;
48 kNumBlocks = (locality > 0) ? (kTotalBits / (CACHE_LINE_SIZE * 8)) : 0;
49
50 assert(kNumBlocks > 0 || kTotalBits > 0);
51 assert(kNumProbes > 0);
52
53 uint32_t sz = kTotalBits / 8;
54 if (kNumBlocks > 0) {
55 sz += CACHE_LINE_SIZE - 1;
56 }
57 assert(allocator);
58
59 char* raw = allocator->AllocateAligned(sz, huge_page_tlb_size, logger);
60 memset(raw, 0, sz);
61 auto cache_line_offset = reinterpret_cast<uintptr_t>(raw) % CACHE_LINE_SIZE;
62 if (kNumBlocks > 0 && cache_line_offset > 0) {
63 raw += CACHE_LINE_SIZE - cache_line_offset;
64 }
65 data_ = raw;
66 }
67
AddKeysHashes(const std::vector<uint32_t> & keys_hashes)68 void BloomBlockBuilder::AddKeysHashes(
69 const std::vector<uint32_t>& keys_hashes) {
70 for (auto hash : keys_hashes) {
71 bloom_.AddHash(hash);
72 }
73 }
74
Finish()75 Slice BloomBlockBuilder::Finish() { return bloom_.GetRawData(); }
76
77 const std::string BloomBlockBuilder::kBloomBlock = "kBloomBlock";
78 } // namespace ROCKSDB_NAMESPACE
79