Branch data Line data Source code
1 : : // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2 : : // Use of this source code is governed by a BSD-style license that can be
3 : : // found in the LICENSE file. See the AUTHORS file for names of contributors.
4 : : //
5 : : // Decodes the blocks generated by block_builder.cc.
6 : :
7 : : #include "table/block.h"
8 : :
9 : : #include <algorithm>
10 : : #include <cstdint>
11 : : #include <vector>
12 : :
13 : : #include "leveldb/comparator.h"
14 : : #include "table/format.h"
15 : : #include "util/coding.h"
16 : : #include "util/logging.h"
17 : :
18 : : namespace leveldb {
19 : :
20 : 2388782 : inline uint32_t Block::NumRestarts() const {
21 [ - + ]: 2388782 : assert(size_ >= sizeof(uint32_t));
22 : 2388782 : return DecodeFixed32(data_ + size_ - sizeof(uint32_t));
23 : : }
24 : :
25 : 52752 : Block::Block(const BlockContents& contents)
26 [ - + ]: 52752 : : data_(contents.data.data()),
27 [ - + ]: 52752 : size_(contents.data.size()),
28 : 52752 : owned_(contents.heap_allocated) {
29 [ - + ]: 52752 : if (size_ < sizeof(uint32_t)) {
30 : 0 : size_ = 0; // Error marker
31 : : } else {
32 : 52752 : size_t max_restarts_allowed = (size_ - sizeof(uint32_t)) / sizeof(uint32_t);
33 [ - + ]: 52752 : if (NumRestarts() > max_restarts_allowed) {
34 : : // The size is too small for NumRestarts()
35 : 0 : size_ = 0;
36 : : } else {
37 : 52752 : restart_offset_ = size_ - (1 + NumRestarts()) * sizeof(uint32_t);
38 : : }
39 : : }
40 : 52752 : }
41 : :
42 : 52750 : Block::~Block() {
43 [ + + ]: 52750 : if (owned_) {
44 [ + - ]: 257 : delete[] data_;
45 : : }
46 : 52750 : }
47 : :
48 : : // Helper routine: decode the next block entry starting at "p",
49 : : // storing the number of shared key bytes, non_shared key bytes,
50 : : // and the length of the value in "*shared", "*non_shared", and
51 : : // "*value_length", respectively. Will not dereference past "limit".
52 : : //
53 : : // If any errors are detected, returns nullptr. Otherwise, returns a
54 : : // pointer to the key delta (just past the three decoded values).
55 : 17359649 : static inline const char* DecodeEntry(const char* p, const char* limit,
56 : : uint32_t* shared, uint32_t* non_shared,
57 : : uint32_t* value_length) {
58 [ + - ]: 17359649 : if (limit - p < 3) return nullptr;
59 : 17359649 : *shared = reinterpret_cast<const uint8_t*>(p)[0];
60 : 17359649 : *non_shared = reinterpret_cast<const uint8_t*>(p)[1];
61 : 17359649 : *value_length = reinterpret_cast<const uint8_t*>(p)[2];
62 [ + + ]: 17359649 : if ((*shared | *non_shared | *value_length) < 128) {
63 : : // Fast path: all three values are encoded in one byte each
64 : 17355264 : p += 3;
65 : : } else {
66 [ + - ]: 4385 : if ((p = GetVarint32Ptr(p, limit, shared)) == nullptr) return nullptr;
67 [ + - ]: 4385 : if ((p = GetVarint32Ptr(p, limit, non_shared)) == nullptr) return nullptr;
68 [ + - ]: 4385 : if ((p = GetVarint32Ptr(p, limit, value_length)) == nullptr) return nullptr;
69 : : }
70 : :
71 [ - + ]: 17359649 : if (static_cast<uint32_t>(limit - p) < (*non_shared + *value_length)) {
72 : 0 : return nullptr;
73 : : }
74 : : return p;
75 : : }
76 : :
77 : : class Block::Iter : public Iterator {
78 : : private:
79 : : const Comparator* const comparator_;
80 : : const char* const data_; // underlying block contents
81 : : uint32_t const restarts_; // Offset of restart array (list of fixed32)
82 : : uint32_t const num_restarts_; // Number of uint32_t entries in restart array
83 : :
84 : : // current_ is offset in data_ of current entry. >= restarts_ if !Valid
85 : : uint32_t current_;
86 : : uint32_t restart_index_; // Index of restart block in which current_ falls
87 : : std::string key_;
88 : : Slice value_;
89 : : Status status_;
90 : :
91 : 16923322 : inline int Compare(const Slice& a, const Slice& b) const {
92 : 16923322 : return comparator_->Compare(a, b);
93 : : }
94 : :
95 : : // Return the offset in data_ just past the end of the current entry.
96 : 4970561 : inline uint32_t NextEntryOffset() const {
97 [ # # # # ]: 0 : return (value_.data() + value_.size()) - data_;
98 : : }
99 : :
100 : 19481872 : uint32_t GetRestartPoint(uint32_t index) {
101 [ - + ]: 19481872 : assert(index < num_restarts_);
102 : 19481872 : return DecodeFixed32(data_ + restarts_ + index * sizeof(uint32_t));
103 : : }
104 : :
105 : 2333838 : void SeekToRestartPoint(uint32_t index) {
106 : 2333838 : key_.clear();
107 : 2333838 : restart_index_ = index;
108 : : // current_ will be fixed by ParseNextKey();
109 : :
110 : : // ParseNextKey() starts at the end of value_, so set value_ accordingly
111 : 2333838 : uint32_t offset = GetRestartPoint(index);
112 : 2333838 : value_ = Slice(data_ + offset, 0);
113 : 2333838 : }
114 : :
115 : : public:
116 : 2336030 : Iter(const Comparator* comparator, const char* data, uint32_t restarts,
117 : : uint32_t num_restarts)
118 : 4672060 : : comparator_(comparator),
119 : 2336030 : data_(data),
120 : 2336030 : restarts_(restarts),
121 : 2336030 : num_restarts_(num_restarts),
122 : 2336030 : current_(restarts_),
123 [ - + ]: 2336030 : restart_index_(num_restarts_) {
124 [ - + ]: 2336030 : assert(num_restarts_ > 0);
125 : 2336030 : }
126 : :
127 : 6884132 : bool Valid() const override { return current_ < restarts_; }
128 [ - + ]: 2327473 : Status status() const override { return status_; }
129 : 539745 : Slice key() const override {
130 [ - + ]: 539745 : assert(Valid());
131 [ - + ]: 539745 : return key_;
132 : : }
133 : 3114731 : Slice value() const override {
134 [ - + ]: 3114731 : assert(Valid());
135 : 3114731 : return value_;
136 : : }
137 : :
138 : 437814 : void Next() override {
139 [ - + ]: 437814 : assert(Valid());
140 : 437814 : ParseNextKey();
141 : 437814 : }
142 : :
143 : 0 : void Prev() override {
144 [ # # ]: 0 : assert(Valid());
145 : :
146 : : // Scan backwards to a restart point before current_
147 : 0 : const uint32_t original = current_;
148 [ # # ]: 0 : while (GetRestartPoint(restart_index_) >= original) {
149 [ # # ]: 0 : if (restart_index_ == 0) {
150 : : // No more entries
151 : 0 : current_ = restarts_;
152 : 0 : restart_index_ = num_restarts_;
153 : 0 : return;
154 : : }
155 : 0 : restart_index_--;
156 : : }
157 : :
158 : 0 : SeekToRestartPoint(restart_index_);
159 : 0 : do {
160 : : // Loop until end of current entry hits the start of original entry
161 [ # # # # : 0 : } while (ParseNextKey() && NextEntryOffset() < original);
# # ]
162 : : }
163 : :
164 : 2321850 : void Seek(const Slice& target) override {
165 : : // Binary search in restart array to find the last restart point
166 : : // with a key < target
167 : 2321850 : uint32_t left = 0;
168 : 2321850 : uint32_t right = num_restarts_ - 1;
169 [ + + ]: 14725854 : while (left < right) {
170 : 12404004 : uint32_t mid = (left + right + 1) / 2;
171 : 12404004 : uint32_t region_offset = GetRestartPoint(mid);
172 : 12404004 : uint32_t shared, non_shared, value_length;
173 : 12404004 : const char* key_ptr =
174 : 12404004 : DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,
175 : : &non_shared, &value_length);
176 [ + - - + ]: 12404004 : if (key_ptr == nullptr || (shared != 0)) {
177 : 0 : CorruptionError();
178 : 0 : return;
179 : : }
180 : 12404004 : Slice mid_key(key_ptr, non_shared);
181 [ + + ]: 12404004 : if (Compare(mid_key, target) < 0) {
182 : : // Key at "mid" is smaller than "target". Therefore all
183 : : // blocks before "mid" are uninteresting.
184 : : left = mid;
185 : : } else {
186 : : // Key at "mid" is >= "target". Therefore all blocks at or
187 : : // after "mid" are uninteresting.
188 : 6658973 : right = mid - 1;
189 : : }
190 : : }
191 : :
192 : : // Linear search (within restart block) for first key >= target
193 : 2321850 : SeekToRestartPoint(left);
194 : 4520759 : while (true) {
195 [ + + ]: 4520759 : if (!ParseNextKey()) {
196 : : return;
197 : : }
198 [ - + + + ]: 4519318 : if (Compare(key_, target) >= 0) {
199 : : return;
200 : : }
201 : : }
202 : : }
203 : :
204 : 11988 : void SeekToFirst() override {
205 : 11988 : SeekToRestartPoint(0);
206 : 11988 : ParseNextKey();
207 : 11988 : }
208 : :
209 : 0 : void SeekToLast() override {
210 : 0 : SeekToRestartPoint(num_restarts_ - 1);
211 [ # # # # : 0 : while (ParseNextKey() && NextEntryOffset() < restarts_) {
# # ]
212 : : // Keep skipping
213 : : }
214 : 0 : }
215 : :
216 : : private:
217 : 0 : void CorruptionError() {
218 : 0 : current_ = restarts_;
219 : 0 : restart_index_ = num_restarts_;
220 [ # # ]: 0 : status_ = Status::Corruption("bad entry in block");
221 : 0 : key_.clear();
222 : 0 : value_.clear();
223 : 0 : }
224 : :
225 : 4970561 : bool ParseNextKey() {
226 [ + + ]: 4970561 : current_ = NextEntryOffset();
227 : 4970561 : const char* p = data_ + current_;
228 : 4970561 : const char* limit = data_ + restarts_; // Restarts come right after data
229 [ + + ]: 4970561 : if (p >= limit) {
230 : : // No more entries to return. Mark as invalid.
231 : 14916 : current_ = restarts_;
232 : 14916 : restart_index_ = num_restarts_;
233 : 14916 : return false;
234 : : }
235 : :
236 : : // Decode next entry
237 : 4955645 : uint32_t shared, non_shared, value_length;
238 : 4955645 : p = DecodeEntry(p, limit, &shared, &non_shared, &value_length);
239 [ + - - + : 4955645 : if (p == nullptr || key_.size() < shared) {
- + ]
240 : 0 : CorruptionError();
241 : 0 : return false;
242 : : } else {
243 : 4955645 : key_.resize(shared);
244 : 4955645 : key_.append(p, non_shared);
245 : 4955645 : value_ = Slice(p + non_shared, value_length);
246 [ + + ]: 4981881 : while (restart_index_ + 1 < num_restarts_ &&
247 [ + + ]: 4744030 : GetRestartPoint(restart_index_ + 1) < current_) {
248 : 26236 : ++restart_index_;
249 : : }
250 : : return true;
251 : : }
252 : : }
253 : : };
254 : :
255 : 2336030 : Iterator* Block::NewIterator(const Comparator* comparator) {
256 [ - + ]: 2336030 : if (size_ < sizeof(uint32_t)) {
257 [ # # # # ]: 0 : return NewErrorIterator(Status::Corruption("bad block contents"));
258 : : }
259 : 2336030 : const uint32_t num_restarts = NumRestarts();
260 [ - + ]: 2336030 : if (num_restarts == 0) {
261 : 0 : return NewEmptyIterator();
262 : : } else {
263 [ + - ]: 2336030 : return new Iter(comparator, data_, restart_offset_, num_restarts);
264 : : }
265 : : }
266 : :
267 : : } // namespace leveldb
|
