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 : : #include "db/db_iter.h"
6 : :
7 : : #include "db/db_impl.h"
8 : : #include "db/dbformat.h"
9 : : #include "db/filename.h"
10 : : #include "leveldb/env.h"
11 : : #include "leveldb/iterator.h"
12 : : #include "port/port.h"
13 : : #include "util/logging.h"
14 : : #include "util/mutexlock.h"
15 : : #include "util/random.h"
16 : :
17 : : namespace leveldb {
18 : :
19 : : #if 0
20 : : static void DumpInternalIter(Iterator* iter) {
21 : : for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
22 : : ParsedInternalKey k;
23 : : if (!ParseInternalKey(iter->key(), &k)) {
24 : : fprintf(stderr, "Corrupt '%s'\n", EscapeString(iter->key()).c_str());
25 : : } else {
26 : : fprintf(stderr, "@ '%s'\n", k.DebugString().c_str());
27 : : }
28 : : }
29 : : }
30 : : #endif
31 : :
32 : : namespace {
33 : :
34 : : // Memtables and sstables that make the DB representation contain
35 : : // (userkey,seq,type) => uservalue entries. DBIter
36 : : // combines multiple entries for the same userkey found in the DB
37 : : // representation into a single entry while accounting for sequence
38 : : // numbers, deletion markers, overwrites, etc.
39 : : class DBIter : public Iterator {
40 : : public:
41 : : // Which direction is the iterator currently moving?
42 : : // (1) When moving forward, the internal iterator is positioned at
43 : : // the exact entry that yields this->key(), this->value()
44 : : // (2) When moving backwards, the internal iterator is positioned
45 : : // just before all entries whose user key == this->key().
46 : : enum Direction { kForward, kReverse };
47 : :
48 : 5033 : DBIter(DBImpl* db, const Comparator* cmp, Iterator* iter, SequenceNumber s,
49 : : uint32_t seed)
50 : 10066 : : db_(db),
51 : 5033 : user_comparator_(cmp),
52 : 5033 : iter_(iter),
53 : 5033 : sequence_(s),
54 : 5033 : direction_(kForward),
55 : 5033 : valid_(false),
56 [ - + ]: 5033 : rnd_(seed),
57 [ - + ]: 5033 : bytes_until_read_sampling_(RandomCompactionPeriod()) {}
58 : :
59 : : DBIter(const DBIter&) = delete;
60 : : DBIter& operator=(const DBIter&) = delete;
61 : :
62 [ + - - + ]: 10066 : ~DBIter() override { delete iter_; }
63 : 401349 : bool Valid() const override { return valid_; }
64 : 397437 : Slice key() const override {
65 [ - + ]: 397437 : assert(valid_);
66 [ + - - - ]: 397437 : return (direction_ == kForward) ? ExtractUserKey(iter_->key()) : saved_key_;
67 : : }
68 : 396476 : Slice value() const override {
69 [ - + ]: 396476 : assert(valid_);
70 [ + - - - ]: 396476 : return (direction_ == kForward) ? iter_->value() : saved_value_;
71 : : }
72 : 0 : Status status() const override {
73 [ # # ]: 0 : if (status_.ok()) {
74 : 0 : return iter_->status();
75 : : } else {
76 : 0 : return status_;
77 : : }
78 : : }
79 : :
80 : : void Next() override;
81 : : void Prev() override;
82 : : void Seek(const Slice& target) override;
83 : : void SeekToFirst() override;
84 : : void SeekToLast() override;
85 : :
86 : : private:
87 : : void FindNextUserEntry(bool skipping, std::string* skip);
88 : : void FindPrevUserEntry();
89 : : bool ParseKey(ParsedInternalKey* key);
90 : :
91 : 480264 : inline void SaveKey(const Slice& k, std::string* dst) {
92 : 480264 : dst->assign(k.data(), k.size());
93 : 0 : }
94 : :
95 : 5035 : inline void ClearSavedValue() {
96 [ + - - + ]: 10070 : if (saved_value_.capacity() > 1048576) {
97 : 0 : std::string empty;
98 : 0 : swap(empty, saved_value_);
99 : 0 : } else {
100 : 5035 : saved_value_.clear();
101 : : }
102 : 5035 : }
103 : :
104 : : // Picks the number of bytes that can be read until a compaction is scheduled.
105 : 5659 : size_t RandomCompactionPeriod() {
106 [ - + ]: 5659 : return rnd_.Uniform(2 * config::kReadBytesPeriod);
107 : : }
108 : :
109 : : DBImpl* db_;
110 : : const Comparator* const user_comparator_;
111 : : Iterator* const iter_;
112 : : SequenceNumber const sequence_;
113 : : Status status_;
114 : : std::string saved_key_; // == current key when direction_==kReverse
115 : : std::string saved_value_; // == current raw value when direction_==kReverse
116 : : Direction direction_;
117 : : bool valid_;
118 : : Random rnd_;
119 : : size_t bytes_until_read_sampling_;
120 : : };
121 : :
122 : 578908 : inline bool DBIter::ParseKey(ParsedInternalKey* ikey) {
123 : 578908 : Slice k = iter_->key();
124 : :
125 : 578908 : size_t bytes_read = k.size() + iter_->value().size();
126 [ + + ]: 579534 : while (bytes_until_read_sampling_ < bytes_read) {
127 : 626 : bytes_until_read_sampling_ += RandomCompactionPeriod();
128 : 626 : db_->RecordReadSample(k);
129 : : }
130 : 578908 : assert(bytes_until_read_sampling_ >= bytes_read);
131 : 578908 : bytes_until_read_sampling_ -= bytes_read;
132 : :
133 [ - + ]: 578908 : if (!ParseInternalKey(k, ikey)) {
134 [ # # ]: 0 : status_ = Status::Corruption("corrupted internal key in DBIter");
135 : 0 : return false;
136 : : } else {
137 : : return true;
138 : : }
139 : : }
140 : :
141 : 396160 : void DBIter::Next() {
142 [ - + ]: 396160 : assert(valid_);
143 : :
144 [ - + ]: 396160 : if (direction_ == kReverse) { // Switch directions?
145 : 0 : direction_ = kForward;
146 : : // iter_ is pointing just before the entries for this->key(),
147 : : // so advance into the range of entries for this->key() and then
148 : : // use the normal skipping code below.
149 [ # # ]: 0 : if (!iter_->Valid()) {
150 : 0 : iter_->SeekToFirst();
151 : : } else {
152 : 0 : iter_->Next();
153 : : }
154 [ # # ]: 0 : if (!iter_->Valid()) {
155 : 0 : valid_ = false;
156 : 0 : saved_key_.clear();
157 : 0 : return;
158 : : }
159 : : // saved_key_ already contains the key to skip past.
160 : : } else {
161 : : // Store in saved_key_ the current key so we skip it below.
162 : 396160 : SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
163 : :
164 : : // iter_ is pointing to current key. We can now safely move to the next to
165 : : // avoid checking current key.
166 : 396160 : iter_->Next();
167 [ + + ]: 396160 : if (!iter_->Valid()) {
168 : 18 : valid_ = false;
169 : 18 : saved_key_.clear();
170 : 18 : return;
171 : : }
172 : : }
173 : :
174 : 396142 : FindNextUserEntry(true, &saved_key_);
175 : : }
176 : :
177 : 398709 : void DBIter::FindNextUserEntry(bool skipping, std::string* skip) {
178 : : // Loop until we hit an acceptable entry to yield
179 [ - + ]: 398709 : assert(iter_->Valid());
180 [ - + ]: 398709 : assert(direction_ == kForward);
181 : 578908 : do {
182 : 578908 : ParsedInternalKey ikey;
183 [ + - + + ]: 578908 : if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
184 [ + + - ]: 578716 : switch (ikey.type) {
185 : 84104 : case kTypeDeletion:
186 : : // Arrange to skip all upcoming entries for this key since
187 : : // they are hidden by this deletion.
188 : 84104 : SaveKey(ikey.user_key, skip);
189 : 84104 : skipping = true;
190 : 84104 : break;
191 : 494612 : case kTypeValue:
192 [ + + + + ]: 986686 : if (skipping &&
193 [ - + ]: 492074 : user_comparator_->Compare(ikey.user_key, *skip) <= 0) {
194 : : // Entry hidden
195 : : } else {
196 : 397487 : valid_ = true;
197 : 397487 : saved_key_.clear();
198 : 397487 : return;
199 : : }
200 : : break;
201 : : }
202 : : }
203 : 181421 : iter_->Next();
204 [ + + ]: 181421 : } while (iter_->Valid());
205 : 1222 : saved_key_.clear();
206 : 1222 : valid_ = false;
207 : : }
208 : :
209 : 0 : void DBIter::Prev() {
210 [ # # ]: 0 : assert(valid_);
211 : :
212 [ # # ]: 0 : if (direction_ == kForward) { // Switch directions?
213 : : // iter_ is pointing at the current entry. Scan backwards until
214 : : // the key changes so we can use the normal reverse scanning code.
215 [ # # ]: 0 : assert(iter_->Valid()); // Otherwise valid_ would have been false
216 : 0 : SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
217 : 0 : while (true) {
218 : 0 : iter_->Prev();
219 [ # # ]: 0 : if (!iter_->Valid()) {
220 : 0 : valid_ = false;
221 : 0 : saved_key_.clear();
222 : 0 : ClearSavedValue();
223 : 0 : return;
224 : : }
225 [ # # # # ]: 0 : if (user_comparator_->Compare(ExtractUserKey(iter_->key()), saved_key_) <
226 : : 0) {
227 : : break;
228 : : }
229 : : }
230 : 0 : direction_ = kReverse;
231 : : }
232 : :
233 : 0 : FindPrevUserEntry();
234 : : }
235 : :
236 : 0 : void DBIter::FindPrevUserEntry() {
237 [ # # ]: 0 : assert(direction_ == kReverse);
238 : :
239 : 0 : ValueType value_type = kTypeDeletion;
240 [ # # ]: 0 : if (iter_->Valid()) {
241 : 0 : do {
242 : 0 : ParsedInternalKey ikey;
243 [ # # # # ]: 0 : if (ParseKey(&ikey) && ikey.sequence <= sequence_) {
244 [ # # # # ]: 0 : if ((value_type != kTypeDeletion) &&
245 [ # # ]: 0 : user_comparator_->Compare(ikey.user_key, saved_key_) < 0) {
246 : : // We encountered a non-deleted value in entries for previous keys,
247 : : break;
248 : : }
249 : 0 : value_type = ikey.type;
250 [ # # ]: 0 : if (value_type == kTypeDeletion) {
251 : 0 : saved_key_.clear();
252 : 0 : ClearSavedValue();
253 : : } else {
254 : 0 : Slice raw_value = iter_->value();
255 [ # # # # ]: 0 : if (saved_value_.capacity() > raw_value.size() + 1048576) {
256 : 0 : std::string empty;
257 : 0 : swap(empty, saved_value_);
258 : 0 : }
259 : 0 : SaveKey(ExtractUserKey(iter_->key()), &saved_key_);
260 : 0 : saved_value_.assign(raw_value.data(), raw_value.size());
261 : : }
262 : : }
263 : 0 : iter_->Prev();
264 [ # # ]: 0 : } while (iter_->Valid());
265 : : }
266 : :
267 [ # # ]: 0 : if (value_type == kTypeDeletion) {
268 : : // End
269 : 0 : valid_ = false;
270 : 0 : saved_key_.clear();
271 : 0 : ClearSavedValue();
272 : 0 : direction_ = kForward;
273 : : } else {
274 : 0 : valid_ = true;
275 : : }
276 : 0 : }
277 : :
278 : 4491 : void DBIter::Seek(const Slice& target) {
279 : 4491 : direction_ = kForward;
280 : 4491 : ClearSavedValue();
281 : 4491 : saved_key_.clear();
282 : 4491 : AppendInternalKey(&saved_key_,
283 : 4491 : ParsedInternalKey(target, sequence_, kValueTypeForSeek));
284 [ - + ]: 4491 : iter_->Seek(saved_key_);
285 [ + + ]: 4491 : if (iter_->Valid()) {
286 : 2564 : FindNextUserEntry(false, &saved_key_ /* temporary storage */);
287 : : } else {
288 : 1927 : valid_ = false;
289 : : }
290 : 4491 : }
291 : :
292 : 544 : void DBIter::SeekToFirst() {
293 : 544 : direction_ = kForward;
294 : 544 : ClearSavedValue();
295 : 544 : iter_->SeekToFirst();
296 [ + + ]: 544 : if (iter_->Valid()) {
297 : 3 : FindNextUserEntry(false, &saved_key_ /* temporary storage */);
298 : : } else {
299 : 541 : valid_ = false;
300 : : }
301 : 544 : }
302 : :
303 : 0 : void DBIter::SeekToLast() {
304 : 0 : direction_ = kReverse;
305 : 0 : ClearSavedValue();
306 : 0 : iter_->SeekToLast();
307 : 0 : FindPrevUserEntry();
308 : 0 : }
309 : :
310 : : } // anonymous namespace
311 : :
312 : 5033 : Iterator* NewDBIterator(DBImpl* db, const Comparator* user_key_comparator,
313 : : Iterator* internal_iter, SequenceNumber sequence,
314 : : uint32_t seed) {
315 [ + - ]: 5033 : return new DBIter(db, user_key_comparator, internal_iter, sequence, seed);
316 : : }
317 : :
318 : : } // namespace leveldb
|
