This is an automated email from the ASF dual-hosted git repository. achennaka pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/kudu.git
The following commit(s) were added to refs/heads/master by this push: new 3d5497cf2 [cfile] clean up on IndexBlock{Builder,Iterator,Reader} 3d5497cf2 is described below commit 3d5497cf299ee18f937efb9176190c35a33a9215 Author: Alexey Serbin <ale...@apache.org> AuthorDate: Wed Oct 25 15:15:13 2023 -0700 [cfile] clean up on IndexBlock{Builder,Iterator,Reader} This patch contains the following updates: * the code in IndexBlockReader::Parse() now catches corruption of index block's trailer in a more robust manner * fixed index overruns and possible memory corruption in IndexBlockReader::GetKeyPointer() when working with not-so-expected input for an empty BTree file and when the data read from the index file is corrupted * removed a few unused fields * a few class member functions became static * added PREDICT_{TRUE,FALSE} macros for better branch prediction where appropriate * fixed const-correctness * changed CHECK() to DCHECK() for the code paths where the assertions might trigger due to the variation of control paths, but independent of the input data * added more DCHECK() assertions where appropriate * updated the code to conform to the project's current style guide * addressed a few Clang-Tidy warnings * other minor updates I also added a test to cover various error paths in IndexBlockReader::Parse() when parsing corrupted index blocks. Change-Id: If83dd132b577a481a2ddaa09e2657639f8b92c7d Reviewed-on: http://gerrit.cloudera.org:8080/20690 Reviewed-by: Ashwani Raina <ara...@cloudera.com> Reviewed-by: Abhishek Chennaka <achenn...@cloudera.com> Tested-by: Abhishek Chennaka <achenn...@cloudera.com> --- src/kudu/cfile/index-test.cc | 242 ++++++++++++++++++++++++++++++++++---- src/kudu/cfile/index_block.cc | 263 +++++++++++++++++++++++++----------------- src/kudu/cfile/index_block.h | 62 +++++----- src/kudu/cfile/index_btree.cc | 150 ++++++++++++------------ src/kudu/cfile/index_btree.h | 62 +++++----- 5 files changed, 508 insertions(+), 271 deletions(-) diff --git a/src/kudu/cfile/index-test.cc b/src/kudu/cfile/index-test.cc index e676d75ee..0b61b8738 100644 --- a/src/kudu/cfile/index-test.cc +++ b/src/kudu/cfile/index-test.cc @@ -26,13 +26,17 @@ #include <gtest/gtest.h> #include "kudu/cfile/block_pointer.h" +#include "kudu/cfile/cfile.pb.h" #include "kudu/cfile/cfile_util.h" #include "kudu/cfile/index_block.h" #include "kudu/common/common.pb.h" #include "kudu/common/key_encoder.h" #include "kudu/gutil/endian.h" +#include "kudu/util/coding.h" +#include "kudu/util/coding-inl.h" #include "kudu/util/faststring.h" #include "kudu/util/hexdump.h" +#include "kudu/util/protobuf_util.h" #include "kudu/util/slice.h" #include "kudu/util/status.h" #include "kudu/util/test_macros.h" @@ -43,17 +47,17 @@ using std::unique_ptr; namespace kudu { namespace cfile { -Status SearchInReaderString(const IndexBlockReader &reader, - const string &search_key, - BlockPointer *ptr, Slice *match) { +Status SearchInReaderString(const IndexBlockReader& reader, + const string& search_key, + BlockPointer* ptr, + Slice* match) { static faststring dst; unique_ptr<IndexBlockIterator> iter(reader.NewIterator()); dst.clear(); KeyEncoderTraits<BINARY, faststring>::Encode(search_key, &dst); - Status s = iter->SeekAtOrBefore(Slice(dst)); - RETURN_NOT_OK(s); + RETURN_NOT_OK(iter->SeekAtOrBefore(Slice(dst))); *ptr = iter->GetCurrentBlockPointer(); *match = iter->GetCurrentKey(); @@ -61,17 +65,17 @@ Status SearchInReaderString(const IndexBlockReader &reader, } -Status SearchInReaderUint32(const IndexBlockReader &reader, +Status SearchInReaderUint32(const IndexBlockReader& reader, uint32_t search_key, - BlockPointer *ptr, Slice *match) { + BlockPointer* ptr, + Slice* match) { static faststring dst; unique_ptr<IndexBlockIterator> iter(reader.NewIterator()); dst.clear(); KeyEncoderTraits<UINT32, faststring>::Encode(search_key, &dst); - Status s = iter->SeekAtOrBefore(Slice(dst)); - RETURN_NOT_OK(s); + RETURN_NOT_OK(iter->SeekAtOrBefore(Slice(dst))); *ptr = iter->GetCurrentBlockPointer(); *match = iter->GetCurrentKey(); @@ -79,32 +83,35 @@ Status SearchInReaderUint32(const IndexBlockReader &reader, } // Expects a Slice containing a big endian encoded int -static uint32_t SliceAsUInt32(const Slice &slice) { - CHECK_EQ(slice.size(), 4); - uint32_t val; +static uint32_t SliceAsUInt32(const Slice& slice) { + CHECK_EQ(4, slice.size()); + uint32_t val = 0; memcpy(&val, slice.data(), slice.size()); val = BigEndian::FromHost32(val); return val; } -static void AddToIndex(IndexBlockBuilder *idx, uint32_t val, - const BlockPointer &block_pointer) { - +static void AddToIndex(IndexBlockBuilder* idx, + uint32_t val, + const BlockPointer& block_pointer) { static faststring dst; dst.clear(); KeyEncoderTraits<UINT32, faststring>::Encode(val, &dst); idx->Add(Slice(dst), block_pointer); } +static void AddEmptyKeyToIndex(IndexBlockBuilder* idx, + const BlockPointer& block_pointer) { + idx->Add({}, block_pointer); +} // Test IndexBlockBuilder and IndexReader with integers TEST(TestIndexBuilder, TestIndexWithInts) { // Encode an index block. - WriterOptions opts; - IndexBlockBuilder idx(&opts, true); + IndexBlockBuilder idx(true); - const int EXPECTED_NUM_ENTRIES = 4; + static constexpr int EXPECTED_NUM_ENTRIES = 4; uint32_t i; @@ -204,8 +211,7 @@ TEST(TestIndexBuilder, TestIndexWithInts) { } TEST(TestIndexBlock, TestIndexBlockWithStrings) { - WriterOptions opts; - IndexBlockBuilder idx(&opts, true); + IndexBlockBuilder idx(true); // Insert data for "hello-10" through "hello-40" by 10s const int EXPECTED_NUM_ENTRIES = 4; @@ -302,8 +308,7 @@ TEST(TestIndexBlock, TestIndexBlockWithStrings) { // Test seeking around using the IndexBlockIterator class TEST(TestIndexBlock, TestIterator) { // Encode an index block with 1000 entries. - WriterOptions opts; - IndexBlockBuilder idx(&opts, true); + IndexBlockBuilder idx(true); for (int i = 0; i < 1000; i++) { uint32_t key = i * 10; @@ -340,6 +345,199 @@ TEST(TestIndexBlock, TestIterator) { ASSERT_TRUE(iter->HasNext()); } +// Parse an empty index block and make sure the IndexBlockReader's API works +// as expected. +TEST(TestIndexBlock, EmptyBlock) { + IndexBlockBuilder idx(true); + ASSERT_TRUE(idx.empty()); + ASSERT_EQ(0, idx.count()); + Slice key; + const auto s = idx.GetFirstKey(&key); + ASSERT_TRUE(s.IsNotFound()) << s.ToString(); + + const Slice b = idx.Finish(); + IndexBlockReader reader; + ASSERT_OK(reader.Parse(b)); + ASSERT_TRUE(reader.IsLeaf()); + ASSERT_EQ(0, reader.Count()); + unique_ptr<IndexBlockIterator> it(reader.NewIterator()); + ASSERT_FALSE(it->HasNext()); + { + const auto s = it->SeekToIndex(0); + ASSERT_TRUE(s.IsNotFound()) << s.ToString(); + } + { + const auto s = it->Next(); + ASSERT_TRUE(s.IsNotFound()) << s.ToString(); + } + { + const Slice key; + const auto s = it->SeekAtOrBefore(key); + ASSERT_TRUE(s.IsNotFound()) << s.ToString(); + } +} + +// Test how IndexBlockBuilder and IndexBlockReader work with empty keys +// in an index block. +TEST(TestIndexBlock, EmptyKeys) { + // All the sanity checks in the parser are based on min/max estimates, + // and there might be variations in the size of the encoded fields because + // of varint encoding, where higher values consume more space when serialized. + // That's exercised below by using different number of blocks in the generated + // index file. + + // One empty key. + { + IndexBlockBuilder idx(true); + AddEmptyKeyToIndex(&idx, BlockPointer(0, 1)); + const Slice b = idx.Finish(); + + IndexBlockReader reader; + ASSERT_OK(reader.Parse(b)); + } + + // Several empty keys. + { + IndexBlockBuilder idx(true); + for (auto i = 0; i < 8; ++i) { + AddEmptyKeyToIndex(&idx, BlockPointer(i, 1)); + } + const Slice b = idx.Finish(); + + IndexBlockReader reader; + ASSERT_OK(reader.Parse(b)); + } + + // Many empty keys. + { + IndexBlockBuilder idx(true); + for (auto i = 0; i < 65536; ++i) { + AddEmptyKeyToIndex(&idx, BlockPointer(i, 1)); + } + const Slice b = idx.Finish(); + + IndexBlockReader reader; + ASSERT_OK(reader.Parse(b)); + } +} + +// Corrupt the trailer or its size in the block and try to parse the block. +TEST(TestIndexBlock, CorruptedTrailer) { + // Data chunk is too small. + { + uint8_t buf[3]; + Slice b(buf, sizeof(buf)); + IndexBlockReader reader; + const auto s = reader.Parse(b); + ASSERT_TRUE(s.IsCorruption()) << s.ToString(); + ASSERT_STR_CONTAINS(s.ToString(), "index block too small"); + } + + // The trailer's size is too small. + { + IndexBlockBuilder idx(true); + AddToIndex(&idx, 0, BlockPointer(1, 1024)); + const Slice b = idx.Finish(); + + const uint8_t* trailer_size_ptr = b.data() + b.size() - sizeof(uint32_t); + + faststring buf; + InlinePutFixed32(&buf, 3); + memmove(const_cast<uint8_t*>(trailer_size_ptr), buf.data(), buf.size()); + + IndexBlockReader reader; + const auto s = reader.Parse(b); + ASSERT_TRUE(s.IsCorruption()) << s.ToString(); + ASSERT_STR_CONTAINS(s.ToString(), "3: invalid index block trailer size"); + } + + // The trailer's size is too big. + { + IndexBlockBuilder idx(true); + AddToIndex(&idx, 1, BlockPointer(2, 1024)); + const Slice b = idx.Finish(); + + const uint8_t* trailer_size_ptr = b.data() + b.size() - sizeof(uint32_t); + + faststring buf; + InlinePutFixed32(&buf, 1234); + memmove(const_cast<uint8_t*>(trailer_size_ptr), buf.data(), buf.size()); + + IndexBlockReader reader; + const auto s = reader.Parse(b); + ASSERT_TRUE(s.IsCorruption()) << s.ToString(); + ASSERT_STR_CONTAINS(s.ToString(), "1234: invalid index block trailer size"); + } + + // The number of key offsets too high for the actual amount of data stored. + { + IndexBlockBuilder idx(true); + AddToIndex(&idx, 2, BlockPointer(3, 1024)); + const Slice b = idx.Finish(); + + const uint8_t* trailer_size_ptr = b.data() + b.size() - sizeof(uint32_t); + const size_t trailer_size = DecodeFixed32(trailer_size_ptr); + const uint8_t* trailer_ptr = trailer_size_ptr - trailer_size; + IndexBlockTrailerPB t; + ASSERT_TRUE(t.ParseFromArray(trailer_ptr, trailer_size)); + t.set_num_entries(5); + + // To make sure writing over the new serialized message doesn't require + // updating the encoded trailer size, check that the new serialized + // PB message is the same size as the original message. + ASSERT_EQ(trailer_size, t.ByteSizeLong()); + + faststring buf; + ASSERT_TRUE(AppendPBToString(t, &buf)); + memmove(const_cast<uint8_t*>(trailer_ptr), buf.data(), buf.size()); + + IndexBlockReader reader; + const auto s = reader.Parse(b); + ASSERT_TRUE(s.IsCorruption()) << s.ToString(); + ASSERT_STR_CONTAINS(s.ToString(), "5: too many entries in trailer"); + } + + // Negative number of key offsets. + { + IndexBlockBuilder idx(true); + AddToIndex(&idx, 3, BlockPointer(4, 1024)); + const Slice b = idx.Finish(); + + IndexBlockTrailerPB t; + { + const uint8_t* trailer_size_ptr = b.data() + b.size() - sizeof(uint32_t); + const size_t trailer_size = DecodeFixed32(trailer_size_ptr); + const uint8_t* trailer_ptr = trailer_size_ptr - trailer_size; + ASSERT_TRUE(t.ParseFromArray(trailer_ptr, trailer_size)); + } + + IndexBlockTrailerPB tc(t); + tc.set_num_entries(-3); + // The new trailer serialized into a bigger message due to negative value + // of the int32_t field. + ASSERT_GT(tc.ByteSizeLong(), t.ByteSizeLong()); + + unique_ptr<uint8_t[]> bc_data( + new uint8_t[b.size() + tc.ByteSizeLong() - t.ByteSizeLong()]); + Slice bc(b); + bc.relocate(bc_data.get()); + + faststring buf; + ASSERT_TRUE(AppendPBToString(tc, &buf)); + InlinePutFixed32(&buf, tc.ByteSizeLong()); + + // Overwrite the trailer and the trailer size. + memmove(bc.mutable_data() + bc.size() - tc.ByteSizeLong() - sizeof(uint32_t), + buf.data(), + buf.size()); + + IndexBlockReader reader; + const auto s = reader.Parse(bc); + ASSERT_TRUE(s.IsCorruption()) << s.ToString(); + ASSERT_STR_CONTAINS(s.ToString(), "-3: bad number of entries in trailer"); + } +} + TEST(TestIndexKeys, TestGetSeparatingKey) { // Test example cases Slice left = ""; diff --git a/src/kudu/cfile/index_block.cc b/src/kudu/cfile/index_block.cc index ecfef4bf3..c003d1e3e 100644 --- a/src/kudu/cfile/index_block.cc +++ b/src/kudu/cfile/index_block.cc @@ -19,7 +19,6 @@ #include <cstdint> #include <ostream> -#include <string> #include <glog/logging.h> @@ -30,24 +29,28 @@ #include "kudu/util/pb_util.h" #include "kudu/util/protobuf_util.h" +using strings::Substitute; + namespace kudu { namespace cfile { -inline void SliceEncode(const Slice &key, faststring *buf) { +inline void SliceEncode(const Slice& key, faststring* buf) { InlinePutVarint32(buf, key.size()); buf->append(key.data(), key.size()); } -inline const uint8_t *SliceDecode(const uint8_t *encoded_ptr, const uint8_t *limit, - Slice *retptr) { +inline const uint8_t* SliceDecode( + const uint8_t* encoded_ptr, + const uint8_t* limit, + Slice* retptr) { uint32_t len; - const uint8_t *data_start = GetVarint32Ptr(encoded_ptr, limit, &len); - if (data_start == nullptr) { + const uint8_t* data_start = GetVarint32Ptr(encoded_ptr, limit, &len); + if (PREDICT_FALSE(!data_start)) { // bad varint return nullptr; } - if (data_start + len > limit) { + if (PREDICT_FALSE(data_start + len > limit)) { // length extends past end of valid area return nullptr; } @@ -56,28 +59,23 @@ inline const uint8_t *SliceDecode(const uint8_t *encoded_ptr, const uint8_t *lim return data_start + len; } -IndexBlockBuilder::IndexBlockBuilder( - const WriterOptions *options, - bool is_leaf) - : options_(options), - finished_(false), - is_leaf_(is_leaf) { +IndexBlockBuilder::IndexBlockBuilder(bool is_leaf) + : finished_(false), + is_leaf_(is_leaf) { } +void IndexBlockBuilder::Add(const Slice& keyptr, + const BlockPointer& ptr) { + DCHECK(!finished_) << "Must Reset() after Finish() before more Add()"; -void IndexBlockBuilder::Add(const Slice &keyptr, - const BlockPointer &ptr) { - DCHECK(!finished_) << - "Must Reset() after Finish() before more Add()"; - - size_t entry_offset = buffer_.size(); + const size_t entry_offset = buffer_.size(); SliceEncode(keyptr, &buffer_); ptr.EncodeTo(&buffer_); entry_offsets_.push_back(entry_offset); } Slice IndexBlockBuilder::Finish() { - CHECK(!finished_) << "already called Finish()"; + DCHECK(!finished_) << "already called Finish()"; for (uint32_t off : entry_offsets_) { InlinePutFixed32(&buffer_, off); @@ -85,8 +83,8 @@ Slice IndexBlockBuilder::Finish() { IndexBlockTrailerPB trailer; trailer.set_num_entries(entry_offsets_.size()); - trailer.set_type( - is_leaf_ ? IndexBlockTrailerPB::LEAF : IndexBlockTrailerPB::INTERNAL); + trailer.set_type(is_leaf_ ? IndexBlockTrailerPB::LEAF + : IndexBlockTrailerPB::INTERNAL); AppendPBToString(trailer, &buffer_); InlinePutFixed32(&buffer_, trailer.GetCachedSize()); @@ -95,28 +93,23 @@ Slice IndexBlockBuilder::Finish() { return Slice(buffer_); } - // Return the key of the first entry in this index block. -Status IndexBlockBuilder::GetFirstKey(Slice *key) const { - // TODO: going to need to be able to pass an arena or something +Status IndexBlockBuilder::GetFirstKey(Slice* key) const { + // TODO(todd): going to need to be able to pass an arena or something // for slices, which need to copy - - if (entry_offsets_.empty()) { + if (PREDICT_FALSE(entry_offsets_.empty())) { return Status::NotFound("no keys in builder"); } - - bool success = nullptr != SliceDecode(buffer_.data(),buffer_.data() + buffer_.size(),key); - - if (success) { - return Status::OK(); - } else { - return Status::Corruption("Unable to decode first key"); + if (PREDICT_FALSE(!SliceDecode( + buffer_.data(), buffer_.data() + buffer_.size(), key))) { + return Status::Corruption("unable to decode first key"); } + return Status::OK(); } size_t IndexBlockBuilder::EstimateEncodedSize() const { // the actual encoded index entries - int size = buffer_.size(); + auto size = buffer_.size(); // entry offsets size += sizeof(uint32_t) * entry_offsets_.size(); @@ -129,48 +122,76 @@ size_t IndexBlockBuilder::EstimateEncodedSize() const { } // Construct a reader. -// After construtoin, call +// After construction, call Parse() to read the data. IndexBlockReader::IndexBlockReader() - : parsed_(false) { + : key_offsets_(nullptr), + parsed_(false) { } void IndexBlockReader::Reset() { - data_ = Slice(); + data_.clear(); + trailer_.Clear(); + key_offsets_ = nullptr; parsed_ = false; } -Status IndexBlockReader::Parse(const Slice &data) { - parsed_ = false; +Status IndexBlockReader::Parse(const Slice& data) { data_ = data; - - if (data_.size() < sizeof(uint32_t)) { + // The code below parses the data of an index block, checking for invariants + // based on index block layout and protobuf serialization and encoding rules. + // + // For details on protobuf's serialization and encoding, see [2] and [3]. + // For details on Kudu's index block layout, see [3]. + // + // [1] https://protobuf.dev/programming-guides/encoding/ + // [2] https://stackoverflow.com/questions/30915704/maximum-serialized-protobuf-message-size + // [3] https://github.com/apache/kudu/blob/master/docs/design-docs/cfile.md#cfile-index + if (PREDICT_FALSE(data_.size() < sizeof(uint32_t))) { return Status::Corruption("index block too small"); } - const uint8_t *trailer_size_ptr = - data_.data() + data_.size() - sizeof(uint32_t); - uint32_t trailer_size = DecodeFixed32(trailer_size_ptr); - - size_t max_size = trailer_size_ptr - data_.data(); - if (trailer_size <= 0 || - trailer_size > max_size) { - std::string err = strings::Substitute( - "invalid index block trailer size: $0", trailer_size); - return Status::Corruption(err); + const uint8_t* trailer_size_ptr = + data_.data() + data_.size() - sizeof(uint32_t); + const size_t trailer_size = DecodeFixed32(trailer_size_ptr); + + // A serialized IndexBlockTrailerPB message cannot be shorter than four bytes. + // In protobuf, each serialized field contains a tag followed by some data. + // The tag is at least one byte. As for the serialized fields of the + // IndexBlockTrailerPB message, it contains at least two required fields now: + // * int32_t num_entries: at least one byte serialized with varint encoding + // * BlockType type: enum, at least one byte serialized + // So, the total for the minimum length of these two fields serialized + // in protobuf format is four bytes: (1 + 1) + (1 + 1). + if (PREDICT_FALSE(trailer_size < 4 || + trailer_size > trailer_size_ptr - data_.data())) { + return Status::Corruption(Substitute( + "$0: invalid index block trailer size", trailer_size)); } - const uint8_t *trailer_ptr = trailer_size_ptr - trailer_size; + const uint8_t* trailer_ptr = trailer_size_ptr - trailer_size; + if (PREDICT_FALSE(!trailer_.ParseFromArray(trailer_ptr, trailer_size))) { + return Status::Corruption("unable to parse trailer", + trailer_.InitializationErrorString()); + } - bool success = trailer_.ParseFromArray(trailer_ptr, trailer_size); - if (!success) { - return Status::Corruption( - "unable to parse trailer", - trailer_.InitializationErrorString()); + const auto num_entries = trailer_.num_entries(); + if (PREDICT_FALSE(num_entries < 0)) { + return Status::Corruption(Substitute( + "$0: bad number of entries in trailer", num_entries)); } - key_offsets_ = trailer_ptr - sizeof(uint32_t) * trailer_.num_entries(); - CHECK(trailer_ptr >= data_.data()); + key_offsets_ = trailer_ptr - sizeof(uint32_t) * num_entries; + // Each entry is three bytes at least (integers use varint encoding): + // * key + // ** the size of the key: at least one byte + // ** the key's data: zero or more bytes (zero bytes for an empty key) + // * the offset of the block: at least one byte + // * the size of the block: at least one byte + if (PREDICT_FALSE(key_offsets_ < data_.data() + 3 * num_entries)) { + return Status::Corruption(Substitute( + "$0: too many entries in trailer", num_entries)); + } VLOG(2) << "Parsed index trailer: " << pb_util::SecureDebugString(trailer_); @@ -179,70 +200,94 @@ Status IndexBlockReader::Parse(const Slice &data) { } size_t IndexBlockReader::Count() const { - CHECK(parsed_) << "not parsed"; + DCHECK(parsed_) << "not parsed"; return trailer_.num_entries(); } -IndexBlockIterator *IndexBlockReader::NewIterator() const { - CHECK(parsed_) << "not parsed"; +IndexBlockIterator* IndexBlockReader::NewIterator() const { + DCHECK(parsed_) << "not parsed"; return new IndexBlockIterator(this); } -bool IndexBlockReader::IsLeaf() { +bool IndexBlockReader::IsLeaf() const { + DCHECK(parsed_) << "not parsed"; return trailer_.type() == IndexBlockTrailerPB::LEAF; } -int IndexBlockReader::CompareKey(int idx_in_block, - const Slice &search_key) const { - const uint8_t *key_ptr, *limit; - GetKeyPointer(idx_in_block, &key_ptr, &limit); +int IndexBlockReader::CompareKey(size_t idx_in_block, + const Slice& search_key) const { + const uint8_t* key_ptr = nullptr; + const uint8_t* limit = nullptr; + if (auto s = GetKeyPointer(idx_in_block, &key_ptr, &limit); + PREDICT_FALSE(!s.ok())) { + LOG(WARNING) << Substitute("failed to position in block: $0", s.ToString()); + return 0; + } Slice this_slice; - if (PREDICT_FALSE(SliceDecode(key_ptr, limit, &this_slice) == nullptr)) { - LOG(WARNING)<< "Invalid data in block!"; + if (PREDICT_FALSE(!SliceDecode(key_ptr, limit, &this_slice))) { + LOG(WARNING) << Substitute("invalid data in block at index $0", idx_in_block); return 0; } return this_slice.compare(search_key); } -Status IndexBlockReader::ReadEntry(size_t idx, Slice *key, BlockPointer *block_ptr) const { - if (idx >= trailer_.num_entries()) { - return Status::NotFound("Invalid index"); +Status IndexBlockReader::ReadEntry(size_t idx, + Slice* key, + BlockPointer* block_ptr) const { + DCHECK(parsed_) << "not parsed"; + if (PREDICT_FALSE(idx >= trailer_.num_entries())) { + return Status::NotFound(Substitute("$0: invalid index", idx)); } // At 'ptr', data is encoded as follows: // <key> <block offset> <block length> - const uint8_t *ptr, *limit; + const uint8_t* ptr = nullptr; + const uint8_t* limit = nullptr; GetKeyPointer(idx, &ptr, &limit); ptr = SliceDecode(ptr, limit, key); - if (ptr == nullptr) { - return Status::Corruption("Invalid key in index"); + if (PREDICT_FALSE(!ptr)) { + return Status::Corruption(Substitute("invalid key in index $0", idx)); } return block_ptr->DecodeFrom(ptr, data_.data() + data_.size()); } -void IndexBlockReader::GetKeyPointer(int idx_in_block, const uint8_t **ptr, - const uint8_t **limit) const { - size_t offset_in_block = DecodeFixed32( - &key_offsets_[idx_in_block * sizeof(uint32_t)]); +Status IndexBlockReader::GetKeyPointer(size_t idx_in_block, + const uint8_t** ptr, + const uint8_t** limit) const { + DCHECK(parsed_) << "not parsed"; + if (PREDICT_FALSE(trailer_.num_entries() <= idx_in_block)) { + return Status::NotFound(Substitute("$0: no such index", idx_in_block)); + } + DCHECK(key_offsets_); + const size_t offset_in_block = DecodeFixed32( + &key_offsets_[idx_in_block * sizeof(uint32_t)]); + if (PREDICT_FALSE(data_.data() + offset_in_block >= key_offsets_)) { + return Status::Corruption(Substitute( + "$0: invalid block offset at index $1", offset_in_block, idx_in_block)); + } *ptr = data_.data() + offset_in_block; - int next_idx = idx_in_block + 1; - - if (PREDICT_FALSE(next_idx >= trailer_.num_entries())) { - DCHECK(next_idx == Count()) << "Bad index: " << idx_in_block - << " Count: " << Count(); - // last key in block: limit is the beginning of the offsets array - *limit = key_offsets_; - } else { - // otherwise limit is the beginning of the next key - offset_in_block = DecodeFixed32( - &key_offsets_[next_idx * sizeof(uint32_t)]); + const size_t next_idx = idx_in_block + 1; + if (PREDICT_TRUE(next_idx < trailer_.num_entries())) { + // The limit is the beginning of the next key. + const size_t offset_in_block = DecodeFixed32( + &key_offsets_[next_idx * sizeof(uint32_t)]); + if (PREDICT_FALSE(data_.data() + offset_in_block >= key_offsets_)) { + return Status::Corruption(Substitute( + "$0: invalid block offset at index $1", offset_in_block, next_idx)); + } *limit = data_.data() + offset_in_block; + } else { + // For the last key in block, the limit is the beginning of the offsets array. + DCHECK(next_idx == Count()) << Substitute("bad index: $0 count: $1", + idx_in_block, Count()); + *limit = key_offsets_; } + return Status::OK(); } void IndexBlockBuilder::Reset() { @@ -251,22 +296,25 @@ void IndexBlockBuilder::Reset() { finished_ = false; } -IndexBlockIterator::IndexBlockIterator(const IndexBlockReader *reader) - : reader_(reader), - cur_idx_(-1), - seeked_(false) { +IndexBlockIterator::IndexBlockIterator(const IndexBlockReader* reader) + : reader_(reader), + cur_idx_(-1), + seeked_(false) { } void IndexBlockIterator::Reset() { - seeked_ = false; cur_idx_ = -1; + cur_key_.clear(); + cur_ptr_ = BlockPointer(); + seeked_ = false; } -Status IndexBlockIterator::SeekAtOrBefore(const Slice &search_key) { +Status IndexBlockIterator::SeekAtOrBefore(const Slice& search_key) { + const auto num_entries = reader_->Count(); size_t left = 0; - size_t right = reader_->Count() - 1; + size_t right = num_entries > 0 ? num_entries - 1 : 0; while (left < right) { - int mid = (left + right + 1) / 2; + size_t mid = (left + right + 1) / 2; int compare = reader_->CompareKey(mid, search_key); if (compare < 0) { // mid < search @@ -280,8 +328,7 @@ Status IndexBlockIterator::SeekAtOrBefore(const Slice &search_key) { } // closest is now 'left' - int compare = reader_->CompareKey(left, search_key); - if (compare > 0) { + if (reader_->CompareKey(left, search_key) > 0) { // The last midpoint was still greater than the // provided key, which implies that the key is // lower than the lowest in the block. @@ -298,21 +345,27 @@ Status IndexBlockIterator::SeekToIndex(size_t idx) { return s; } +// Unsigned cur_idx_ overflow is intended and works as expected when +// cur_idx_ has its initial value, so quell UBSAN warnings. +ATTRIBUTE_NO_SANITIZE_INTEGER bool IndexBlockIterator::HasNext() const { return cur_idx_ + 1 < reader_->Count(); } +// Unsigned cur_idx_ overflow is intended and works as expected when +// cur_idx_ has its initial value, so quell UBSAN warnings. +ATTRIBUTE_NO_SANITIZE_INTEGER Status IndexBlockIterator::Next() { return SeekToIndex(cur_idx_ + 1); } -const BlockPointer &IndexBlockIterator::GetCurrentBlockPointer() const { - CHECK(seeked_) << "not seeked"; +const BlockPointer& IndexBlockIterator::GetCurrentBlockPointer() const { + DCHECK(seeked_) << "not seeked"; return cur_ptr_; } -const Slice IndexBlockIterator::GetCurrentKey() const { - CHECK(seeked_) << "not seeked"; +const Slice& IndexBlockIterator::GetCurrentKey() const { + DCHECK(seeked_) << "not seeked"; return cur_key_; } diff --git a/src/kudu/cfile/index_block.h b/src/kudu/cfile/index_block.h index 045c0101e..fafd18f4b 100644 --- a/src/kudu/cfile/index_block.h +++ b/src/kudu/cfile/index_block.h @@ -15,8 +15,7 @@ // specific language governing permissions and limitations // under the License. -#ifndef KUDU_CFILE_INDEX_BLOCK_H -#define KUDU_CFILE_INDEX_BLOCK_H +#pragma once #include <cstddef> #include <cstdint> @@ -35,19 +34,16 @@ namespace cfile { // Forward decl. class IndexBlockIterator; -struct WriterOptions; - // Index Block Builder for a particular key type. // This works like the rest of the builders in the cfile package. // After repeatedly calling Add(), call Finish() to encode it // into a Slice, then you may Reset to re-use buffers. class IndexBlockBuilder { public: - explicit IndexBlockBuilder(const WriterOptions *options, - bool is_leaf); + explicit IndexBlockBuilder(bool is_leaf); // Append an entry into the index. - void Add(const Slice &key, const BlockPointer &ptr); + void Add(const Slice& key, const BlockPointer& ptr); // Finish the current index block. // Returns a fully encoded Slice including the data @@ -58,14 +54,19 @@ class IndexBlockBuilder { // Return the key of the first entry in this index block. // The pointed-to data is only valid until the next call to this builder. - Status GetFirstKey(Slice *key) const; + Status GetFirstKey(Slice* key) const; - // Return the number of entries already added to this index - // block. + // Return the number of entries already added to this index block. size_t count() const { return entry_offsets_.size(); } + // Return 'true' if there aren't any entries added to this index block, + // 'false' otherwise. + bool empty() const { + return entry_offsets_.empty(); + } + // Return an estimate of the post-encoding size of this // index block. This estimate should be conservative -- // it will over-estimate rather than under-estimate, and @@ -78,16 +79,11 @@ class IndexBlockBuilder { private: DISALLOW_COPY_AND_ASSIGN(IndexBlockBuilder); -#ifdef __clang__ - __attribute__((__unused__)) -#endif - const WriterOptions *options_; - // Is the builder currently between Finish() and Reset() bool finished_; // Is this a leaf block? - bool is_leaf_; + const bool is_leaf_; faststring buffer_; std::vector<uint32_t> entry_offsets_; @@ -106,34 +102,35 @@ class IndexBlockReader { // // Note: this does not copy the data, so the slice must // remain valid for the lifetime of the reader (or until the next Parse call). - Status Parse(const Slice &data); + Status Parse(const Slice& data); size_t Count() const; - IndexBlockIterator *NewIterator() const; + IndexBlockIterator* NewIterator() const; - bool IsLeaf(); + bool IsLeaf() const; private: friend class IndexBlockIterator; - int CompareKey(int idx_in_block, const Slice &search_key) const; + int CompareKey(size_t idx_in_block, const Slice& search_key) const; - Status ReadEntry(size_t idx, Slice *key, BlockPointer *block_ptr) const; + Status ReadEntry(size_t idx, Slice* key, BlockPointer* block_ptr) const; - // Set *ptr to the beginning of the index data for the given index - // entry. + // Set *ptr to the beginning of the index data for the given index entry. // Set *limit to the 'limit' pointer for that entry (i.e a pointer // beyond which the data no longer is part of that entry). // - *limit can be used to prevent overrunning in the case of a // corrupted length varint or length prefix - void GetKeyPointer(int idx_in_block, const uint8_t **ptr, const uint8_t **limit) const; + // Return Status::NotFound() if the given index isn't present. + // Return Status::Corruption() if inconsistency in block offset is detected. + Status GetKeyPointer(size_t idx_in_block, + const uint8_t** ptr, + const uint8_t** limit) const; - static const int kMaxTrailerSize = 64*1024; Slice data_; - IndexBlockTrailerPB trailer_; - const uint8_t *key_offsets_; + const uint8_t* key_offsets_; bool parsed_; DISALLOW_COPY_AND_ASSIGN(IndexBlockReader); @@ -141,7 +138,7 @@ class IndexBlockReader { class IndexBlockIterator { public: - explicit IndexBlockIterator(const IndexBlockReader *reader); + explicit IndexBlockIterator(const IndexBlockReader* reader); // Reset the state of this iterator. This should be used // after the associated 'reader' object parses a different block. @@ -157,7 +154,7 @@ class IndexBlockIterator { // If this function returns an error, then the state of this // iterator is undefined (i.e it may or may not have moved // since the previous call) - Status SeekAtOrBefore(const Slice &search_key); + Status SeekAtOrBefore(const Slice& search_key); Status SeekToIndex(size_t idx); @@ -165,12 +162,12 @@ class IndexBlockIterator { Status Next(); - const BlockPointer &GetCurrentBlockPointer() const; + const BlockPointer& GetCurrentBlockPointer() const; - const Slice GetCurrentKey() const; + const Slice& GetCurrentKey() const; private: - const IndexBlockReader *reader_; + const IndexBlockReader* reader_; size_t cur_idx_; Slice cur_key_; BlockPointer cur_ptr_; @@ -181,4 +178,3 @@ class IndexBlockIterator { } // namespace cfile } // namespace kudu -#endif diff --git a/src/kudu/cfile/index_btree.cc b/src/kudu/cfile/index_btree.cc index 887cbcaf7..942ff389c 100644 --- a/src/kudu/cfile/index_btree.cc +++ b/src/kudu/cfile/index_btree.cc @@ -33,6 +33,7 @@ #include "kudu/cfile/cfile_writer.h" #include "kudu/cfile/index_block.h" #include "kudu/fs/block_id.h" +#include "kudu/gutil/port.h" #include "kudu/gutil/ref_counted.h" #include "kudu/gutil/strings/substitute.h" #include "kudu/util/debug-util.h" @@ -47,31 +48,30 @@ namespace kudu { namespace cfile { IndexTreeBuilder::IndexTreeBuilder( - const WriterOptions *options, - CFileWriter *writer) : - options_(options), - writer_(writer) { + const WriterOptions* options, + CFileWriter* writer) + : options_(options), + writer_(writer) { idx_blocks_.emplace_back(CreateBlockBuilder(true)); } - -IndexBlockBuilder *IndexTreeBuilder::CreateBlockBuilder(bool is_leaf) { - return new IndexBlockBuilder(options_, is_leaf); +IndexBlockBuilder* IndexTreeBuilder::CreateBlockBuilder(bool is_leaf) { + return new IndexBlockBuilder(is_leaf); } -Status IndexTreeBuilder::Append(const Slice &key, - const BlockPointer &block) { - return Append(key, block, 0); +Status IndexTreeBuilder::Append(const Slice& key, + const BlockPointer& block_ptr) { + return Append(key, block_ptr, 0); } -Status IndexTreeBuilder::Append( - const Slice &key, const BlockPointer &block_ptr, - size_t level) { +Status IndexTreeBuilder::Append(const Slice& key, + const BlockPointer& block_ptr, + size_t level) { if (level >= idx_blocks_.size()) { // Need to create a new level - CHECK(level == idx_blocks_.size()) << - "trying to create level " << level << " but size is only " - << idx_blocks_.size(); + DCHECK(level == idx_blocks_.size()) << + Substitute("trying to create level $0 but size is only $1", + level, idx_blocks_.size()); VLOG(1) << "Creating level-" << level << " in index b-tree"; idx_blocks_.emplace_back(CreateBlockBuilder(false)); } @@ -79,35 +79,31 @@ Status IndexTreeBuilder::Append( IndexBlockBuilder* idx_block = idx_blocks_[level].get(); idx_block->Add(key, block_ptr); - // This index block is full, and there are at least two entries, - // flush it. - size_t est_size = idx_block->EstimateEncodedSize(); - if (est_size > options_->index_block_size && - idx_block->count() > 1) { + // If this index block is full and there are at least two entries, + // then flush it. + if (idx_block->count() > 1 && + idx_block->EstimateEncodedSize() > options_->index_block_size) { RETURN_NOT_OK(FinishBlockAndPropagate(level)); } return Status::OK(); } - -Status IndexTreeBuilder::Finish(BTreeInfoPB *info) { - // Now do the same for the positional index blocks, starting - // with leaf - VLOG(1) << "flushing tree, b-tree has " << - idx_blocks_.size() << " levels"; +Status IndexTreeBuilder::Finish(BTreeInfoPB* info) { + DCHECK(!idx_blocks_.empty()); + // Now do the same for the positional index blocks, starting with leaf. + VLOG(1) << "flushing tree, b-tree has " << idx_blocks_.size() << " levels"; // Flush all but the root of the index. - for (size_t i = 0; i < idx_blocks_.size() - 1; i++) { - RETURN_NOT_OK(FinishBlockAndPropagate(i)); + for (size_t i = 1; i < idx_blocks_.size(); ++i) { + RETURN_NOT_OK(FinishBlockAndPropagate(i - 1)); } // Flush the root - int root_level = idx_blocks_.size() - 1; + const size_t root_level = idx_blocks_.size() - 1; BlockPointer ptr; - Status s = FinishAndWriteBlock(root_level, &ptr); - if (!s.ok()) { - return s.CloneAndPrepend("Unable to flush root index block"); + if (auto s = FinishAndWriteBlock(root_level, &ptr); PREDICT_FALSE(!s.ok())) { + return s.CloneAndPrepend("unable to flush root index block"); } VLOG(1) << "Flushed root index block: " << ptr.ToString(); @@ -117,6 +113,7 @@ Status IndexTreeBuilder::Finish(BTreeInfoPB *info) { } Status IndexTreeBuilder::FinishBlockAndPropagate(size_t level) { + DCHECK_LT(level, idx_blocks_.size()); IndexBlockBuilder* idx_block = idx_blocks_[level].get(); // If the block doesn't have any data in it, we don't need to @@ -124,8 +121,8 @@ Status IndexTreeBuilder::FinishBlockAndPropagate(size_t level) { // This happens if a lower-level block fills up exactly, // and then the file completes. // - // TODO: add a test case which exercises this explicitly. - if (idx_block->count() == 0) { + // TODO(todd): add a test case which exercises this explicitly. + if (idx_block->empty()) { return Status::OK(); } @@ -135,18 +132,15 @@ Status IndexTreeBuilder::FinishBlockAndPropagate(size_t level) { // Get the first key of the finished block. Slice first_in_idx_block; - Status s = idx_block->GetFirstKey(&first_in_idx_block); - - if (!s.ok()) { - LOG(ERROR) << "Unable to get first key of level-" << level - << " index block: " << s.ToString() << std::endl - << GetStackTrace(); + if (auto s = idx_block->GetFirstKey(&first_in_idx_block); PREDICT_FALSE(!s.ok())) { + LOG(ERROR) << Substitute( + "unable to get first key of level-$0 index block: $1\n$2", + level, s.ToString(), GetStackTrace()); return s; } // Add to higher-level index. - RETURN_NOT_OK(Append(first_in_idx_block, idx_block_ptr, - level + 1)); + RETURN_NOT_OK(Append(first_in_idx_block, idx_block_ptr, level + 1)); // Finally, reset the block we just wrote. It's important to wait until // here to do this, since the first_in_idx_block data may point to internal @@ -159,13 +153,12 @@ Status IndexTreeBuilder::FinishBlockAndPropagate(size_t level) { // Finish the current block at the given level, writing it // to the file. Return the location of the written block // in 'written'. -Status IndexTreeBuilder::FinishAndWriteBlock(size_t level, BlockPointer *written) { - IndexBlockBuilder* idx_block = idx_blocks_[level].get(); - vector<Slice> v { idx_block->Finish() }; - Status s = writer_->AddBlock(std::move(v), written, "index block"); - if (!s.ok()) { - LOG(ERROR) << "Unable to append level-" << level << " index " - << "block to file"; +Status IndexTreeBuilder::FinishAndWriteBlock(size_t level, BlockPointer* written) { + DCHECK_LT(level, idx_blocks_.size()); + vector<Slice> v { idx_blocks_[level].get()->Finish() }; + if (auto s = writer_->AddBlock(std::move(v), written, "index block"); + PREDICT_FALSE(!s.ok())) { + LOG(ERROR) << Substitute("unable to append level-$0 index block to file", level); return s; } @@ -189,15 +182,16 @@ struct IndexTreeIterator::SeekedIndex { IndexBlockIterator iter; }; -IndexTreeIterator::IndexTreeIterator(const IOContext* io_context, const CFileReader *reader, - const BlockPointer &root_blockptr) +IndexTreeIterator::IndexTreeIterator(const IOContext* io_context, + const CFileReader* reader, + const BlockPointer& root_blockptr) : reader_(reader), root_block_(root_blockptr), io_context_(io_context) { } IndexTreeIterator::~IndexTreeIterator() = default; -Status IndexTreeIterator::SeekAtOrBefore(const Slice &search_key) { +Status IndexTreeIterator::SeekAtOrBefore(const Slice& search_key) { return SeekDownward(search_key, root_block_, 0); } @@ -205,7 +199,7 @@ Status IndexTreeIterator::SeekToFirst() { return SeekToFirstDownward(root_block_, 0); } -bool IndexTreeIterator::HasNext() { +bool IndexTreeIterator::HasNext() const { for (int i = seeked_indexes_.size(); i > 0; i--) { if (seeked_indexes_[i - 1]->iter.HasNext()) return true; @@ -214,7 +208,7 @@ bool IndexTreeIterator::HasNext() { } Status IndexTreeIterator::Next() { - CHECK(!seeked_indexes_.empty()) << "not seeked"; + DCHECK(!seeked_indexes_.empty()) << "not seeked"; // Start at the bottom level of the BTree, calling Next(), // until one succeeds. If any does not succeed, then @@ -249,34 +243,34 @@ Status IndexTreeIterator::Next() { return Status::OK(); } -const Slice IndexTreeIterator::GetCurrentKey() const { +const Slice& IndexTreeIterator::GetCurrentKey() const { return seeked_indexes_.back()->iter.GetCurrentKey(); } -const BlockPointer &IndexTreeIterator::GetCurrentBlockPointer() const { +const BlockPointer& IndexTreeIterator::GetCurrentBlockPointer() const { return seeked_indexes_.back()->iter.GetCurrentBlockPointer(); } -IndexBlockIterator *IndexTreeIterator::BottomIter() { +IndexBlockIterator* IndexTreeIterator::BottomIter() { return &seeked_indexes_.back()->iter; } -IndexBlockReader *IndexTreeIterator::BottomReader() { +const IndexBlockReader* IndexTreeIterator::BottomReader() const { return &seeked_indexes_.back()->reader; } -IndexBlockIterator *IndexTreeIterator::seeked_iter(int depth) { +IndexBlockIterator* IndexTreeIterator::seeked_iter(size_t depth) { + DCHECK_LT(depth, seeked_indexes_.size()); return &seeked_indexes_[depth]->iter; } -IndexBlockReader *IndexTreeIterator::seeked_reader(int depth) { +const IndexBlockReader* IndexTreeIterator::seeked_reader(size_t depth) const { + DCHECK_LT(depth, seeked_indexes_.size()); return &seeked_indexes_[depth]->reader; } -Status IndexTreeIterator::LoadBlock(const BlockPointer &block, - int depth) { - - SeekedIndex *seeked; +Status IndexTreeIterator::LoadBlock(const BlockPointer& block, size_t depth) { + SeekedIndex* seeked; if (depth < seeked_indexes_.size()) { // We have a cached instance from previous seek. seeked = seeked_indexes_[depth].get(); @@ -294,7 +288,7 @@ Status IndexTreeIterator::LoadBlock(const BlockPointer &block, seeked->iter.Reset(); } else { // No cached instance, make a new one. - seeked_indexes_.emplace_back(new SeekedIndex()); + seeked_indexes_.emplace_back(new SeekedIndex); seeked = seeked_indexes_.back().get(); } @@ -307,16 +301,15 @@ Status IndexTreeIterator::LoadBlock(const BlockPointer &block, Substitute("failed to parse index block in block $0 at $1", reader_->block_id().ToString(), block.ToString())); - return Status::OK(); } -Status IndexTreeIterator::SeekDownward(const Slice &search_key, const BlockPointer &in_block, - int cur_depth) { - +Status IndexTreeIterator::SeekDownward(const Slice& search_key, + const BlockPointer& in_block, + size_t cur_depth) { // Read the block. RETURN_NOT_OK(LoadBlock(in_block, cur_depth)); - IndexBlockIterator *iter = seeked_iter(cur_depth); + IndexBlockIterator* iter = seeked_iter(cur_depth); RETURN_NOT_OK(iter->SeekAtOrBefore(search_key)); @@ -330,10 +323,11 @@ Status IndexTreeIterator::SeekDownward(const Slice &search_key, const BlockPoint return SeekDownward(search_key, iter->GetCurrentBlockPointer(), cur_depth + 1); } -Status IndexTreeIterator::SeekToFirstDownward(const BlockPointer &in_block, int cur_depth) { +Status IndexTreeIterator::SeekToFirstDownward(const BlockPointer& in_block, + size_t cur_depth) { // Read the block. RETURN_NOT_OK(LoadBlock(in_block, cur_depth)); - IndexBlockIterator *iter = seeked_iter(cur_depth); + IndexBlockIterator* iter = seeked_iter(cur_depth); RETURN_NOT_OK(iter->SeekToIndex(0)); @@ -343,18 +337,16 @@ Status IndexTreeIterator::SeekToFirstDownward(const BlockPointer &in_block, int if (seeked_reader(cur_depth)->IsLeaf()) { seeked_indexes_.resize(cur_depth + 1); return Status::OK(); - } else { - return SeekToFirstDownward(iter->GetCurrentBlockPointer(), cur_depth + 1); } + return SeekToFirstDownward(iter->GetCurrentBlockPointer(), cur_depth + 1); } -IndexTreeIterator *IndexTreeIterator::IndexTreeIterator::Create( +IndexTreeIterator* IndexTreeIterator::IndexTreeIterator::Create( const IOContext* io_context, - const CFileReader *reader, - const BlockPointer &root_blockptr) { + const CFileReader* reader, + const BlockPointer& root_blockptr) { return new IndexTreeIterator(io_context, reader, root_blockptr); } - } // namespace cfile } // namespace kudu diff --git a/src/kudu/cfile/index_btree.h b/src/kudu/cfile/index_btree.h index 108c7067c..53340639e 100644 --- a/src/kudu/cfile/index_btree.h +++ b/src/kudu/cfile/index_btree.h @@ -15,8 +15,7 @@ // specific language governing permissions and limitations // under the License. -#ifndef KUDU_CFILE_INDEX_BTREE_H -#define KUDU_CFILE_INDEX_BTREE_H +#pragma once #include <cstddef> #include <memory> @@ -44,18 +43,17 @@ struct WriterOptions; class IndexTreeBuilder { public: explicit IndexTreeBuilder( - const WriterOptions *options, - CFileWriter *writer); + const WriterOptions* options, + CFileWriter* writer); // Append the given key into the index. - // The key is copied into the builder's internal - // memory. - Status Append(const Slice &key, const BlockPointer &block); - Status Finish(BTreeInfoPB *info); + // The key is copied into the builder's internal memory. + Status Append(const Slice& key, const BlockPointer& block_ptr); + Status Finish(BTreeInfoPB* info); + private: - IndexBlockBuilder *CreateBlockBuilder(bool is_leaf); - Status Append(const Slice &key, const BlockPointer &block_ptr, - size_t level); + static IndexBlockBuilder* CreateBlockBuilder(bool is_leaf); + Status Append(const Slice& key, const BlockPointer& block_ptr, size_t level); // Finish the current block at the given index level, and then // propagate by inserting this block into the next higher-up @@ -65,10 +63,10 @@ class IndexTreeBuilder { // Finish the current block at the given level, writing it // to the file. Return the location of the written block // in 'written'. - Status FinishAndWriteBlock(size_t level, BlockPointer *written); + Status FinishAndWriteBlock(size_t level, BlockPointer* written); - const WriterOptions *options_; - CFileWriter *writer_; + const WriterOptions* options_; + CFileWriter* writer_; std::vector<std::unique_ptr<IndexBlockBuilder>> idx_blocks_; @@ -77,21 +75,21 @@ class IndexTreeBuilder { class IndexTreeIterator { public: - explicit IndexTreeIterator( + IndexTreeIterator( const fs::IOContext* io_context, - const CFileReader *reader, - const BlockPointer &root_blockptr); + const CFileReader* reader, + const BlockPointer& root_blockptr); ~IndexTreeIterator(); Status SeekToFirst(); - Status SeekAtOrBefore(const Slice &search_key); - bool HasNext(); + Status SeekAtOrBefore(const Slice& search_key); + bool HasNext() const; Status Next(); // The slice key at which the iterator // is currently seeked to. - const Slice GetCurrentKey() const; - const BlockPointer &GetCurrentBlockPointer() const; + const Slice& GetCurrentKey() const; + const BlockPointer& GetCurrentBlockPointer() const; static IndexTreeIterator* Create( const fs::IOContext* io_context, @@ -103,20 +101,21 @@ class IndexTreeIterator { } private: - IndexBlockIterator *BottomIter(); - IndexBlockReader *BottomReader(); - IndexBlockIterator *seeked_iter(int depth); - IndexBlockReader *seeked_reader(int depth); - Status LoadBlock(const BlockPointer &block, int depth); - Status SeekDownward(const Slice &search_key, const BlockPointer &in_block, - int cur_depth); - Status SeekToFirstDownward(const BlockPointer &in_block, int cur_depth); + IndexBlockIterator* BottomIter(); + const IndexBlockReader* BottomReader() const; + IndexBlockIterator* seeked_iter(size_t depth); + const IndexBlockReader* seeked_reader(size_t depth) const; + Status LoadBlock(const BlockPointer& block, size_t depth); + Status SeekDownward(const Slice& search_key, + const BlockPointer& in_block, + size_t cur_depth); + Status SeekToFirstDownward(const BlockPointer& in_block, size_t cur_depth); struct SeekedIndex; - const CFileReader *reader_; + const CFileReader* reader_; - BlockPointer root_block_; + const BlockPointer root_block_; std::vector<std::unique_ptr<SeekedIndex>> seeked_indexes_; @@ -127,4 +126,3 @@ class IndexTreeIterator { } // namespace cfile } // namespace kudu -#endif