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/version_set.h"
6 : :
7 : : #include <stdio.h>
8 : :
9 : : #include <algorithm>
10 : :
11 : : #include "db/filename.h"
12 : : #include "db/log_reader.h"
13 : : #include "db/log_writer.h"
14 : : #include "db/memtable.h"
15 : : #include "db/table_cache.h"
16 : : #include "leveldb/env.h"
17 : : #include "leveldb/table_builder.h"
18 : : #include "table/merger.h"
19 : : #include "table/two_level_iterator.h"
20 : : #include "util/coding.h"
21 : : #include "util/logging.h"
22 : :
23 : : namespace leveldb {
24 : :
25 : 120409 : static size_t TargetFileSize(const Options* options) {
26 : 120409 : return options->max_file_size;
27 : : }
28 : :
29 : : // Maximum bytes of overlaps in grandparent (i.e., level+2) before we
30 : : // stop building a single file in a level->level+1 compaction.
31 : 120116 : static int64_t MaxGrandParentOverlapBytes(const Options* options) {
32 : 120116 : return 10 * TargetFileSize(options);
33 : : }
34 : :
35 : : // Maximum number of bytes in all compacted files. We avoid expanding
36 : : // the lower level file set of a compaction if it would make the
37 : : // total compaction cover more than this many bytes.
38 : 0 : static int64_t ExpandedCompactionByteSizeLimit(const Options* options) {
39 : 0 : return 25 * TargetFileSize(options);
40 : : }
41 : :
42 : 30165 : static double MaxBytesForLevel(const Options* options, int level) {
43 : : // Note: the result for level zero is not really used since we set
44 : : // the level-0 compaction threshold based on number of files.
45 : :
46 : : // Result for both level-0 and level-1
47 : 30165 : double result = 10. * 1048576.0;
48 [ + + ]: 90495 : while (level > 1) {
49 : 60330 : result *= 10;
50 : 60330 : level--;
51 : : }
52 : 30165 : return result;
53 : : }
54 : :
55 : 293 : static uint64_t MaxFileSizeForLevel(const Options* options, int level) {
56 : : // We could vary per level to reduce number of files?
57 : 293 : return TargetFileSize(options);
58 : : }
59 : :
60 : 30681 : static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) {
61 : 30681 : int64_t sum = 0;
62 [ - + + + ]: 33362 : for (size_t i = 0; i < files.size(); i++) {
63 : 2681 : sum += files[i]->file_size;
64 : : }
65 : 30681 : return sum;
66 : : }
67 : :
68 [ + - ]: 93912 : Version::~Version() {
69 [ - + ]: 11739 : assert(refs_ == 0);
70 : :
71 : : // Remove from linked list
72 : 11739 : prev_->next_ = next_;
73 : 11739 : next_->prev_ = prev_;
74 : :
75 : : // Drop references to files
76 [ + + ]: 93912 : for (int level = 0; level < config::kNumLevels; level++) {
77 [ - + + + ]: 88803 : for (size_t i = 0; i < files_[level].size(); i++) {
78 [ - + ]: 6630 : FileMetaData* f = files_[level][i];
79 [ - + ]: 6630 : assert(f->refs > 0);
80 : 6630 : f->refs--;
81 [ + + ]: 6630 : if (f->refs <= 0) {
82 : 8504 : delete f;
83 : : }
84 : : }
85 : : }
86 [ + + ]: 93912 : }
87 : :
88 : 1348299 : int FindFile(const InternalKeyComparator& icmp,
89 : : const std::vector<FileMetaData*>& files, const Slice& key) {
90 : 1348299 : uint32_t left = 0;
91 [ - + ]: 1348299 : uint32_t right = files.size();
92 [ + + ]: 2696803 : while (left < right) {
93 : 1348504 : uint32_t mid = (left + right) / 2;
94 : 1348504 : const FileMetaData* f = files[mid];
95 [ + + ]: 1348504 : if (icmp.InternalKeyComparator::Compare(f->largest.Encode(), key) < 0) {
96 : : // Key at "mid.largest" is < "target". Therefore all
97 : : // files at or before "mid" are uninteresting.
98 : 4020 : left = mid + 1;
99 : : } else {
100 : : // Key at "mid.largest" is >= "target". Therefore all files
101 : : // after "mid" are uninteresting.
102 : : right = mid;
103 : : }
104 : : }
105 : 1348299 : return right;
106 : : }
107 : :
108 : 10 : static bool AfterFile(const Comparator* ucmp, const Slice* user_key,
109 : : const FileMetaData* f) {
110 : : // null user_key occurs before all keys and is therefore never after *f
111 [ + - - + ]: 20 : return (user_key != nullptr &&
112 [ - + ]: 20 : ucmp->Compare(*user_key, f->largest.user_key()) > 0);
113 : : }
114 : :
115 : 2 : static bool BeforeFile(const Comparator* ucmp, const Slice* user_key,
116 : : const FileMetaData* f) {
117 : : // null user_key occurs after all keys and is therefore never before *f
118 [ + - + - ]: 4 : return (user_key != nullptr &&
119 [ - + ]: 4 : ucmp->Compare(*user_key, f->smallest.user_key()) < 0);
120 : : }
121 : :
122 : 143 : bool SomeFileOverlapsRange(const InternalKeyComparator& icmp,
123 : : bool disjoint_sorted_files,
124 : : const std::vector<FileMetaData*>& files,
125 : : const Slice* smallest_user_key,
126 : : const Slice* largest_user_key) {
127 [ + + ]: 143 : const Comparator* ucmp = icmp.user_comparator();
128 [ + + ]: 143 : if (!disjoint_sorted_files) {
129 : : // Need to check against all files
130 [ - + + + ]: 58 : for (size_t i = 0; i < files.size(); i++) {
131 : 10 : const FileMetaData* f = files[i];
132 [ - + - - ]: 10 : if (AfterFile(ucmp, smallest_user_key, f) ||
133 : 0 : BeforeFile(ucmp, largest_user_key, f)) {
134 : : // No overlap
135 : : } else {
136 : : return true; // Overlap
137 : : }
138 : : }
139 : : return false;
140 : : }
141 : :
142 : : // Binary search over file list
143 : 95 : uint32_t index = 0;
144 [ + - ]: 95 : if (smallest_user_key != nullptr) {
145 : : // Find the earliest possible internal key for smallest_user_key
146 : 95 : InternalKey small_key(*smallest_user_key, kMaxSequenceNumber,
147 : 95 : kValueTypeForSeek);
148 [ + - ]: 95 : index = FindFile(icmp, files, small_key.Encode());
149 : 95 : }
150 : :
151 [ - + + + ]: 95 : if (index >= files.size()) {
152 : : // beginning of range is after all files, so no overlap.
153 : : return false;
154 : : }
155 : :
156 : 2 : return !BeforeFile(ucmp, largest_user_key, files[index]);
157 : : }
158 : :
159 : : // An internal iterator. For a given version/level pair, yields
160 : : // information about the files in the level. For a given entry, key()
161 : : // is the largest key that occurs in the file, and value() is an
162 : : // 16-byte value containing the file number and file size, both
163 : : // encoded using EncodeFixed64.
164 : : class Version::LevelFileNumIterator : public Iterator {
165 : : public:
166 : 1525 : LevelFileNumIterator(const InternalKeyComparator& icmp,
167 : : const std::vector<FileMetaData*>* flist)
168 [ - + ]: 1525 : : icmp_(icmp), flist_(flist), index_(flist->size()) { // Marks as invalid
169 : 1525 : }
170 [ - + ]: 5172 : bool Valid() const override { return index_ < flist_->size(); }
171 : 1384 : void Seek(const Slice& target) override {
172 : 1384 : index_ = FindFile(icmp_, *flist_, target);
173 : 1384 : }
174 : 141 : void SeekToFirst() override { index_ = 0; }
175 : 0 : void SeekToLast() override {
176 [ # # # # ]: 0 : index_ = flist_->empty() ? 0 : flist_->size() - 1;
177 : 0 : }
178 : 366 : void Next() override {
179 [ - + ]: 366 : assert(Valid());
180 : 366 : index_++;
181 : 366 : }
182 : 0 : void Prev() override {
183 [ # # ]: 0 : assert(Valid());
184 [ # # ]: 0 : if (index_ == 0) {
185 [ # # ]: 0 : index_ = flist_->size(); // Marks as invalid
186 : : } else {
187 : 0 : index_--;
188 : : }
189 : 0 : }
190 : 695 : Slice key() const override {
191 [ - + ]: 695 : assert(Valid());
192 : 695 : return (*flist_)[index_]->largest.Encode();
193 : : }
194 : 695 : Slice value() const override {
195 [ - + ]: 695 : assert(Valid());
196 : 695 : EncodeFixed64(value_buf_, (*flist_)[index_]->number);
197 : 695 : EncodeFixed64(value_buf_ + 8, (*flist_)[index_]->file_size);
198 : 695 : return Slice(value_buf_, sizeof(value_buf_));
199 : : }
200 : 282 : Status status() const override { return Status::OK(); }
201 : :
202 : : private:
203 : : const InternalKeyComparator icmp_;
204 : : const std::vector<FileMetaData*>* const flist_;
205 : : uint32_t index_;
206 : :
207 : : // Backing store for value(). Holds the file number and size.
208 : : mutable char value_buf_[16];
209 : : };
210 : :
211 : 695 : static Iterator* GetFileIterator(void* arg, const ReadOptions& options,
212 : : const Slice& file_value) {
213 : 695 : TableCache* cache = reinterpret_cast<TableCache*>(arg);
214 [ - + ]: 695 : if (file_value.size() != 16) {
215 [ # # ]: 0 : return NewErrorIterator(
216 [ # # ]: 0 : Status::Corruption("FileReader invoked with unexpected value"));
217 : : } else {
218 : 695 : return cache->NewIterator(options, DecodeFixed64(file_value.data()),
219 : 695 : DecodeFixed64(file_value.data() + 8));
220 : : }
221 : : }
222 : :
223 : 1384 : Iterator* Version::NewConcatenatingIterator(const ReadOptions& options,
224 : : int level) const {
225 : 1384 : return NewTwoLevelIterator(
226 [ + - ]: 1384 : new LevelFileNumIterator(vset_->icmp_, &files_[level]), &GetFileIterator,
227 : 2768 : vset_->table_cache_, options);
228 : : }
229 : :
230 : 5033 : void Version::AddIterators(const ReadOptions& options,
231 : : std::vector<Iterator*>* iters) {
232 : : // Merge all level zero files together since they may overlap
233 [ - + + + ]: 8185 : for (size_t i = 0; i < files_[0].size(); i++) {
234 : 3152 : iters->push_back(vset_->table_cache_->NewIterator(
235 : 3152 : options, files_[0][i]->number, files_[0][i]->file_size));
236 : : }
237 : :
238 : : // For levels > 0, we can use a concatenating iterator that sequentially
239 : : // walks through the non-overlapping files in the level, opening them
240 : : // lazily.
241 [ + + ]: 35231 : for (int level = 1; level < config::kNumLevels; level++) {
242 [ + + ]: 30198 : if (!files_[level].empty()) {
243 : 1384 : iters->push_back(NewConcatenatingIterator(options, level));
244 : : }
245 : : }
246 : 5033 : }
247 : :
248 : : // Callback from TableCache::Get()
249 : : namespace {
250 : : enum SaverState {
251 : : kNotFound,
252 : : kFound,
253 : : kDeleted,
254 : : kCorrupt,
255 : : };
256 : 5875691 : struct Saver {
257 : : SaverState state;
258 : : const Comparator* ucmp;
259 : : Slice user_key;
260 : : std::string* value;
261 : : };
262 : : } // namespace
263 : 94687 : static void SaveValue(void* arg, const Slice& ikey, const Slice& v) {
264 : 94687 : Saver* s = reinterpret_cast<Saver*>(arg);
265 : 94687 : ParsedInternalKey parsed_key;
266 [ - + ]: 94687 : if (!ParseInternalKey(ikey, &parsed_key)) {
267 : 0 : s->state = kCorrupt;
268 : : } else {
269 [ + + ]: 94687 : if (s->ucmp->Compare(parsed_key.user_key, s->user_key) == 0) {
270 [ + + ]: 87672 : s->state = (parsed_key.type == kTypeValue) ? kFound : kDeleted;
271 [ + + ]: 87672 : if (s->state == kFound) {
272 : 35368 : s->value->assign(v.data(), v.size());
273 : : }
274 : : }
275 : : }
276 : 94687 : }
277 : :
278 : 35912 : static bool NewestFirst(FileMetaData* a, FileMetaData* b) {
279 : 35912 : return a->number > b->number;
280 : : }
281 : :
282 : 5876317 : void Version::ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,
283 : : bool (*func)(void*, int, FileMetaData*)) {
284 [ - + ]: 5876317 : const Comparator* ucmp = vset_->icmp_.user_comparator();
285 : :
286 : : // Search level-0 in order from newest to oldest.
287 : 5876317 : std::vector<FileMetaData*> tmp;
288 [ - + + - ]: 5876317 : tmp.reserve(files_[0].size());
289 [ - + + + ]: 6764904 : for (uint32_t i = 0; i < files_[0].size(); i++) {
290 [ - + ]: 888587 : FileMetaData* f = files_[0][i];
291 [ - + + - : 2659820 : if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
+ + + + ]
292 [ - + + - ]: 1765292 : ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
293 [ + - ]: 881666 : tmp.push_back(f);
294 : : }
295 : : }
296 [ + + ]: 5876317 : if (!tmp.empty()) {
297 [ + - ]: 859136 : std::sort(tmp.begin(), tmp.end(), NewestFirst);
298 [ - + + + ]: 1717016 : for (uint32_t i = 0; i < tmp.size(); i++) {
299 [ + - + + ]: 874551 : if (!(*func)(arg, 0, tmp[i])) {
300 : : return;
301 : : }
302 : : }
303 : : }
304 : :
305 : : // Search other levels.
306 [ + + ]: 40654158 : for (int level = 1; level < config::kNumLevels; level++) {
307 [ - + ]: 34865688 : size_t num_files = files_[level].size();
308 [ + + ]: 34865688 : if (num_files == 0) continue;
309 : :
310 : : // Binary search to find earliest index whose largest key >= internal_key.
311 [ + - ]: 1346820 : uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);
312 [ + + ]: 1346820 : if (index < num_files) {
313 [ - + ]: 1343917 : FileMetaData* f = files_[level][index];
314 [ - + + - : 2687834 : if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) {
+ + ]
315 : : // All of "f" is past any data for user_key
316 : : } else {
317 [ + - + + ]: 1343069 : if (!(*func)(arg, level, f)) {
318 : : return;
319 : : }
320 : : }
321 : : }
322 : : }
323 : 5876317 : }
324 : :
325 : 5875691 : Status Version::Get(const ReadOptions& options, const LookupKey& k,
326 : : std::string* value, GetStats* stats) {
327 : 5875691 : stats->seek_file = nullptr;
328 : 5875691 : stats->seek_file_level = -1;
329 : :
330 [ - - ]: 0 : struct State {
331 : : Saver saver;
332 : : GetStats* stats;
333 : : const ReadOptions* options;
334 : : Slice ikey;
335 : : FileMetaData* last_file_read;
336 : : int last_file_read_level;
337 : :
338 : : VersionSet* vset;
339 : : Status s;
340 : : bool found;
341 : :
342 : 2216827 : static bool Match(void* arg, int level, FileMetaData* f) {
343 : 2216827 : State* state = reinterpret_cast<State*>(arg);
344 : :
345 [ + + ]: 2216827 : if (state->stats->seek_file == nullptr &&
346 [ + + ]: 2209992 : state->last_file_read != nullptr) {
347 : : // We have had more than one seek for this read. Charge the 1st file.
348 : 20177 : state->stats->seek_file = state->last_file_read;
349 : 20177 : state->stats->seek_file_level = state->last_file_read_level;
350 : : }
351 : :
352 : 2216827 : state->last_file_read = f;
353 : 2216827 : state->last_file_read_level = level;
354 : :
355 : 4433654 : state->s = state->vset->table_cache_->Get(*state->options, f->number,
356 : 2216827 : f->file_size, state->ikey,
357 [ - + ]: 2216827 : &state->saver, SaveValue);
358 [ + + ]: 2216827 : if (!state->s.ok()) {
359 : 1 : state->found = true;
360 : 1 : return false;
361 : : }
362 [ + + - - : 2216826 : switch (state->saver.state) {
+ ]
363 : : case kNotFound:
364 : : return true; // Keep searching in other files
365 : 35368 : case kFound:
366 : 35368 : state->found = true;
367 : 35368 : return false;
368 : 52304 : case kDeleted:
369 : 52304 : return false;
370 : 0 : case kCorrupt:
371 : 0 : state->s =
372 [ # # ]: 0 : Status::Corruption("corrupted key for ", state->saver.user_key);
373 : 0 : state->found = true;
374 : 0 : return false;
375 : : }
376 : :
377 : : // Not reached. Added to avoid false compilation warnings of
378 : : // "control reaches end of non-void function".
379 : 0 : return false;
380 : : }
381 : : };
382 : :
383 [ + - ]: 5875691 : State state;
384 : 5875691 : state.found = false;
385 : 5875691 : state.stats = stats;
386 : 5875691 : state.last_file_read = nullptr;
387 : 5875691 : state.last_file_read_level = -1;
388 : :
389 : 5875691 : state.options = &options;
390 [ + - ]: 5875691 : state.ikey = k.internal_key();
391 : 5875691 : state.vset = vset_;
392 : :
393 : 5875691 : state.saver.state = kNotFound;
394 [ + - ]: 5875691 : state.saver.ucmp = vset_->icmp_.user_comparator();
395 [ + - ]: 5875691 : state.saver.user_key = k.user_key();
396 : 5875691 : state.saver.value = value;
397 : :
398 [ + - ]: 5875691 : ForEachOverlapping(state.saver.user_key, state.ikey, &state, &State::Match);
399 : :
400 [ + + + - : 5911060 : return state.found ? state.s : Status::NotFound(Slice());
+ + ]
401 : 5875691 : }
402 : :
403 : 5875865 : bool Version::UpdateStats(const GetStats& stats) {
404 : 5875865 : FileMetaData* f = stats.seek_file;
405 [ + + ]: 5875865 : if (f != nullptr) {
406 : 20351 : f->allowed_seeks--;
407 [ + + + + ]: 20351 : if (f->allowed_seeks <= 0 && file_to_compact_ == nullptr) {
408 : 96 : file_to_compact_ = f;
409 : 96 : file_to_compact_level_ = stats.seek_file_level;
410 : 96 : return true;
411 : : }
412 : : }
413 : : return false;
414 : : }
415 : :
416 : 626 : bool Version::RecordReadSample(Slice internal_key) {
417 : 626 : ParsedInternalKey ikey;
418 [ + - ]: 626 : if (!ParseInternalKey(internal_key, &ikey)) {
419 : : return false;
420 : : }
421 : :
422 : 626 : struct State {
423 : : GetStats stats; // Holds first matching file
424 : : int matches;
425 : :
426 : 793 : static bool Match(void* arg, int level, FileMetaData* f) {
427 : 793 : State* state = reinterpret_cast<State*>(arg);
428 : 793 : state->matches++;
429 [ + + ]: 793 : if (state->matches == 1) {
430 : : // Remember first match.
431 : 619 : state->stats.seek_file = f;
432 : 619 : state->stats.seek_file_level = level;
433 : : }
434 : : // We can stop iterating once we have a second match.
435 : 793 : return state->matches < 2;
436 : : }
437 : : };
438 : :
439 : 626 : State state;
440 : 626 : state.matches = 0;
441 : 626 : ForEachOverlapping(ikey.user_key, internal_key, &state, &State::Match);
442 : :
443 : : // Must have at least two matches since we want to merge across
444 : : // files. But what if we have a single file that contains many
445 : : // overwrites and deletions? Should we have another mechanism for
446 : : // finding such files?
447 [ + + ]: 626 : if (state.matches >= 2) {
448 : : // 1MB cost is about 1 seek (see comment in Builder::Apply).
449 : 174 : return UpdateStats(state.stats);
450 : : }
451 : : return false;
452 : : }
453 : :
454 : 6067572 : void Version::Ref() { ++refs_; }
455 : :
456 : 6067571 : void Version::Unref() {
457 [ - + ]: 6067571 : assert(this != &vset_->dummy_versions_);
458 [ - + ]: 6067571 : assert(refs_ >= 1);
459 : 6067571 : --refs_;
460 [ + + ]: 6067571 : if (refs_ == 0) {
461 : 8886 : delete this;
462 : : }
463 : 6067571 : }
464 : :
465 : 143 : bool Version::OverlapInLevel(int level, const Slice* smallest_user_key,
466 : : const Slice* largest_user_key) {
467 : 143 : return SomeFileOverlapsRange(vset_->icmp_, (level > 0), files_[level],
468 : 143 : smallest_user_key, largest_user_key);
469 : : }
470 : :
471 : 48 : int Version::PickLevelForMemTableOutput(const Slice& smallest_user_key,
472 : : const Slice& largest_user_key) {
473 : 48 : int level = 0;
474 [ + - ]: 48 : if (!OverlapInLevel(0, &smallest_user_key, &largest_user_key)) {
475 : : // Push to next level if there is no overlap in next level,
476 : : // and the #bytes overlapping in the level after that are limited.
477 : 48 : InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
478 [ + - ]: 48 : InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0));
479 : 48 : std::vector<FileMetaData*> overlaps;
480 [ + + ]: 141 : while (level < config::kMaxMemCompactLevel) {
481 [ + - + + ]: 95 : if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) {
482 : : break;
483 : : }
484 [ + - ]: 93 : if (level + 2 < config::kNumLevels) {
485 : : // Check that file does not overlap too many grandparent bytes.
486 [ + - ]: 93 : GetOverlappingInputs(level + 2, &start, &limit, &overlaps);
487 : 93 : const int64_t sum = TotalFileSize(overlaps);
488 [ + - ]: 93 : if (sum > MaxGrandParentOverlapBytes(vset_->options_)) {
489 : : break;
490 : : }
491 : : }
492 : : level++;
493 : : }
494 : 48 : }
495 : 48 : return level;
496 : : }
497 : :
498 : : // Store in "*inputs" all files in "level" that overlap [begin,end]
499 : 1113 : void Version::GetOverlappingInputs(int level, const InternalKey* begin,
500 : : const InternalKey* end,
501 : : std::vector<FileMetaData*>* inputs) {
502 [ - + ]: 1113 : assert(level >= 0);
503 [ - + ]: 1113 : assert(level < config::kNumLevels);
504 [ + + ]: 1113 : inputs->clear();
505 [ + - ]: 1113 : Slice user_begin, user_end;
506 [ + - ]: 1113 : if (begin != nullptr) {
507 [ - + ]: 2226 : user_begin = begin->user_key();
508 : : }
509 [ + - ]: 1113 : if (end != nullptr) {
510 [ - + ]: 2226 : user_end = end->user_key();
511 : : }
512 : 1113 : const Comparator* user_cmp = vset_->icmp_.user_comparator();
513 [ + + ]: 3917 : for (size_t i = 0; i < files_[level].size();) {
514 [ - + ]: 1691 : FileMetaData* f = files_[level][i++];
515 [ - + ]: 1691 : const Slice file_start = f->smallest.user_key();
516 [ - + ]: 1691 : const Slice file_limit = f->largest.user_key();
517 [ + - + + ]: 1691 : if (begin != nullptr && user_cmp->Compare(file_limit, user_begin) < 0) {
518 : : // "f" is completely before specified range; skip it
519 [ + - + - ]: 1549 : } else if (end != nullptr && user_cmp->Compare(file_start, user_end) > 0) {
520 : : // "f" is completely after specified range; skip it
521 : : } else {
522 : 1549 : inputs->push_back(f);
523 [ + + ]: 1549 : if (level == 0) {
524 : : // Level-0 files may overlap each other. So check if the newly
525 : : // added file has expanded the range. If so, restart search.
526 [ + - + + ]: 1406 : if (begin != nullptr && user_cmp->Compare(file_start, user_begin) < 0) {
527 : 32 : user_begin = file_start;
528 [ + - ]: 32 : inputs->clear();
529 : : i = 0;
530 [ + - + + ]: 2748 : } else if (end != nullptr &&
531 : 1374 : user_cmp->Compare(file_limit, user_end) > 0) {
532 : 5 : user_end = file_limit;
533 [ + - - + ]: 2809 : inputs->clear();
534 : : i = 0;
535 : : }
536 : : }
537 : : }
538 : : }
539 : 1113 : }
540 : :
541 : 0 : std::string Version::DebugString() const {
542 : 0 : std::string r;
543 [ # # ]: 0 : for (int level = 0; level < config::kNumLevels; level++) {
544 : : // E.g.,
545 : : // --- level 1 ---
546 : : // 17:123['a' .. 'd']
547 : : // 20:43['e' .. 'g']
548 [ # # ]: 0 : r.append("--- level ");
549 [ # # ]: 0 : AppendNumberTo(&r, level);
550 [ # # ]: 0 : r.append(" ---\n");
551 : : const std::vector<FileMetaData*>& files = files_[level];
552 [ # # # # ]: 0 : for (size_t i = 0; i < files.size(); i++) {
553 [ # # ]: 0 : r.push_back(' ');
554 [ # # ]: 0 : AppendNumberTo(&r, files[i]->number);
555 [ # # ]: 0 : r.push_back(':');
556 [ # # ]: 0 : AppendNumberTo(&r, files[i]->file_size);
557 [ # # ]: 0 : r.append("[");
558 [ # # ]: 0 : r.append(files[i]->smallest.DebugString());
559 [ # # ]: 0 : r.append(" .. ");
560 [ # # ]: 0 : r.append(files[i]->largest.DebugString());
561 [ # # ]: 0 : r.append("]\n");
562 : : }
563 : : }
564 : 0 : return r;
565 : 0 : }
566 : :
567 : : // A helper class so we can efficiently apply a whole sequence
568 : : // of edits to a particular state without creating intermediate
569 : : // Versions that contain full copies of the intermediate state.
570 : : class VersionSet::Builder {
571 : : private:
572 : : // Helper to sort by v->files_[file_number].smallest
573 : : struct BySmallestKey {
574 : : const InternalKeyComparator* internal_comparator;
575 : :
576 : 5757 : bool operator()(FileMetaData* f1, FileMetaData* f2) const {
577 : 5757 : int r = internal_comparator->Compare(f1->smallest, f2->smallest);
578 [ + + ]: 5757 : if (r != 0) {
579 : 5290 : return (r < 0);
580 : : } else {
581 : : // Break ties by file number
582 : 467 : return (f1->number < f2->number);
583 : : }
584 : : }
585 : : };
586 : :
587 : : typedef std::set<FileMetaData*, BySmallestKey> FileSet;
588 : 42231 : struct LevelState {
589 : : std::set<uint64_t> deleted_files;
590 : : FileSet* added_files;
591 : : };
592 : :
593 : : VersionSet* vset_;
594 : : Version* base_;
595 : : LevelState levels_[config::kNumLevels];
596 : :
597 : : public:
598 : : // Initialize a builder with the files from *base and other info from *vset
599 [ + + - - ]: 48264 : Builder(VersionSet* vset, Version* base) : vset_(vset), base_(base) {
600 [ + - ]: 6033 : base_->Ref();
601 : 6033 : BySmallestKey cmp;
602 : 6033 : cmp.internal_comparator = &vset_->icmp_;
603 [ + + ]: 48264 : for (int level = 0; level < config::kNumLevels; level++) {
604 [ + - ]: 42231 : levels_[level].added_files = new FileSet(cmp);
605 : : }
606 [ - - ]: 6033 : }
607 : :
608 [ + - ]: 48264 : ~Builder() {
609 [ + + ]: 48264 : for (int level = 0; level < config::kNumLevels; level++) {
610 : 42231 : const FileSet* added = levels_[level].added_files;
611 : 42231 : std::vector<FileMetaData*> to_unref;
612 : 42231 : to_unref.reserve(added->size());
613 [ + + ]: 47368 : for (FileSet::const_iterator it = added->begin(); it != added->end();
614 : 5137 : ++it) {
615 : 5137 : to_unref.push_back(*it);
616 : : }
617 [ + - ]: 84462 : delete added;
618 [ - + + + ]: 47368 : for (uint32_t i = 0; i < to_unref.size(); i++) {
619 [ + + ]: 5137 : FileMetaData* f = to_unref[i];
620 : 5137 : f->refs--;
621 [ + + ]: 5137 : if (f->refs <= 0) {
622 : 1764 : delete f;
623 : : }
624 : : }
625 : 42231 : }
626 : 6033 : base_->Unref();
627 [ + + ]: 48264 : }
628 : :
629 : : // Apply all of the edits in *edit to the current state.
630 : 8035 : void Apply(VersionEdit* edit) {
631 : : // Update compaction pointers
632 [ - + + + ]: 9050 : for (size_t i = 0; i < edit->compact_pointers_.size(); i++) {
633 : 1015 : const int level = edit->compact_pointers_[i].first;
634 : 2030 : vset_->compact_pointer_[level] =
635 : 1015 : edit->compact_pointers_[i].second.Encode().ToString();
636 : : }
637 : :
638 : : // Delete files
639 [ + + ]: 10008 : for (const auto& deleted_file_set_kvp : edit->deleted_files_) {
640 : 1973 : const int level = deleted_file_set_kvp.first;
641 : 1973 : const uint64_t number = deleted_file_set_kvp.second;
642 : 1973 : levels_[level].deleted_files.insert(number);
643 : : }
644 : :
645 : : // Add new files
646 [ - + + + ]: 13172 : for (size_t i = 0; i < edit->new_files_.size(); i++) {
647 : 5137 : const int level = edit->new_files_[i].first;
648 [ + - ]: 5137 : FileMetaData* f = new FileMetaData(edit->new_files_[i].second);
649 : 5137 : f->refs = 1;
650 : :
651 : : // We arrange to automatically compact this file after
652 : : // a certain number of seeks. Let's assume:
653 : : // (1) One seek costs 10ms
654 : : // (2) Writing or reading 1MB costs 10ms (100MB/s)
655 : : // (3) A compaction of 1MB does 25MB of IO:
656 : : // 1MB read from this level
657 : : // 10-12MB read from next level (boundaries may be misaligned)
658 : : // 10-12MB written to next level
659 : : // This implies that 25 seeks cost the same as the compaction
660 : : // of 1MB of data. I.e., one seek costs approximately the
661 : : // same as the compaction of 40KB of data. We are a little
662 : : // conservative and allow approximately one seek for every 16KB
663 : : // of data before triggering a compaction.
664 : 5137 : f->allowed_seeks = static_cast<int>((f->file_size / 16384U));
665 [ + - ]: 5137 : if (f->allowed_seeks < 100) f->allowed_seeks = 100;
666 : :
667 : 5137 : levels_[level].deleted_files.erase(f->number);
668 : 5137 : levels_[level].added_files->insert(f);
669 : : }
670 : 8035 : }
671 : :
672 : : // Save the current state in *v.
673 : 6033 : void SaveTo(Version* v) {
674 : 6033 : BySmallestKey cmp;
675 : 6033 : cmp.internal_comparator = &vset_->icmp_;
676 [ + + ]: 48264 : for (int level = 0; level < config::kNumLevels; level++) {
677 : : // Merge the set of added files with the set of pre-existing files.
678 : : // Drop any deleted files. Store the result in *v.
679 : 42231 : const std::vector<FileMetaData*>& base_files = base_->files_[level];
680 [ - + ]: 42231 : std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin();
681 [ - + ]: 42231 : std::vector<FileMetaData*>::const_iterator base_end = base_files.end();
682 : 42231 : const FileSet* added_files = levels_[level].added_files;
683 [ - + ]: 42231 : v->files_[level].reserve(base_files.size() + added_files->size());
684 [ + + ]: 47368 : for (const auto& added_file : *added_files) {
685 : : // Add all smaller files listed in base_
686 : 6039 : for (std::vector<FileMetaData*>::const_iterator bpos =
687 : 5137 : std::upper_bound(base_iter, base_end, added_file, cmp);
688 [ + + ]: 6039 : base_iter != bpos; ++base_iter) {
689 : 902 : MaybeAddFile(v, level, *base_iter);
690 : : }
691 : :
692 : 5137 : MaybeAddFile(v, level, added_file);
693 : : }
694 : :
695 : : // Add remaining base files
696 [ + + ]: 44798 : for (; base_iter != base_end; ++base_iter) {
697 : 2567 : MaybeAddFile(v, level, *base_iter);
698 : : }
699 : :
700 : : #ifndef NDEBUG
701 : : // Make sure there is no overlap in levels > 0
702 [ + + ]: 42231 : if (level > 0) {
703 [ - + + + ]: 36369 : for (uint32_t i = 1; i < v->files_[level].size(); i++) {
704 : 171 : const InternalKey& prev_end = v->files_[level][i - 1]->largest;
705 : 171 : const InternalKey& this_begin = v->files_[level][i]->smallest;
706 [ - + ]: 171 : if (vset_->icmp_.Compare(prev_end, this_begin) >= 0) {
707 [ # # ]: 0 : fprintf(stderr, "overlapping ranges in same level %s vs. %s\n",
708 [ # # ]: 0 : prev_end.DebugString().c_str(),
709 [ # # ]: 0 : this_begin.DebugString().c_str());
710 : 0 : abort();
711 : : }
712 : : }
713 : : }
714 : : #endif
715 : : }
716 : 6033 : }
717 : :
718 : 8606 : void MaybeAddFile(Version* v, int level, FileMetaData* f) {
719 [ + + ]: 8606 : if (levels_[level].deleted_files.count(f->number) > 0) {
720 : : // File is deleted: do nothing
721 : : } else {
722 : 6633 : std::vector<FileMetaData*>* files = &v->files_[level];
723 [ + + + + ]: 6633 : if (level > 0 && !files->empty()) {
724 : : // Must not overlap
725 [ - + - + ]: 171 : assert(vset_->icmp_.Compare((*files)[files->size() - 1]->largest,
726 : : f->smallest) < 0);
727 : : }
728 : 6633 : f->refs++;
729 : 6633 : files->push_back(f);
730 : : }
731 : 8606 : }
732 : : };
733 : :
734 : 2854 : VersionSet::VersionSet(const std::string& dbname, const Options* options,
735 : : TableCache* table_cache,
736 : 2854 : const InternalKeyComparator* cmp)
737 : 2854 : : env_(options->env),
738 [ - + ]: 2854 : dbname_(dbname),
739 : 2854 : options_(options),
740 : 2854 : table_cache_(table_cache),
741 : 2854 : icmp_(*cmp),
742 : 2854 : next_file_number_(2),
743 : 2854 : manifest_file_number_(0), // Filled by Recover()
744 : 2854 : last_sequence_(0),
745 : 2854 : log_number_(0),
746 : 2854 : prev_log_number_(0),
747 : 2854 : descriptor_file_(nullptr),
748 : 2854 : descriptor_log_(nullptr),
749 : 2854 : dummy_versions_(this),
750 [ + + ]: 22832 : current_(nullptr) {
751 [ + - + - ]: 2854 : AppendVersion(new Version(this));
752 [ - - ]: 2854 : }
753 : :
754 : 28530 : VersionSet::~VersionSet() {
755 : 2853 : current_->Unref();
756 [ - + ]: 2853 : assert(dummy_versions_.next_ == &dummy_versions_); // List must be empty
757 [ + + ]: 2853 : delete descriptor_log_;
758 [ + + ]: 2853 : delete descriptor_file_;
759 [ + + ]: 28530 : }
760 : :
761 : 8887 : void VersionSet::AppendVersion(Version* v) {
762 : : // Make "v" current
763 [ - + ]: 8887 : assert(v->refs_ == 0);
764 [ - + ]: 8887 : assert(v != current_);
765 [ + + ]: 8887 : if (current_ != nullptr) {
766 : 6033 : current_->Unref();
767 : : }
768 : 8887 : current_ = v;
769 : 8887 : v->Ref();
770 : :
771 : : // Append to linked list
772 : 8887 : v->prev_ = dummy_versions_.prev_;
773 : 8887 : v->next_ = &dummy_versions_;
774 : 8887 : v->prev_->next_ = v;
775 : 8887 : v->next_->prev_ = v;
776 : 8887 : }
777 : :
778 : 3181 : Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) {
779 [ + + ]: 3181 : if (edit->has_log_number_) {
780 [ - + ]: 2889 : assert(edit->log_number_ >= log_number_);
781 [ - + ]: 2889 : assert(edit->log_number_ < next_file_number_);
782 : : } else {
783 : 292 : edit->SetLogNumber(log_number_);
784 : : }
785 : :
786 [ + + ]: 3181 : if (!edit->has_prev_log_number_) {
787 : 292 : edit->SetPrevLogNumber(prev_log_number_);
788 : : }
789 : :
790 : 3181 : edit->SetNextFile(next_file_number_);
791 : 3181 : edit->SetLastSequence(last_sequence_);
792 : :
793 : 3181 : Version* v = new Version(this);
794 : 3181 : {
795 : 3181 : Builder builder(this, current_);
796 [ + - ]: 3181 : builder.Apply(edit);
797 [ + - ]: 3181 : builder.SaveTo(v);
798 : 3181 : }
799 : 3181 : Finalize(v);
800 : :
801 : : // Initialize new descriptor log file if necessary by creating
802 : : // a temporary file that contains a snapshot of the current version.
803 [ + + ]: 3181 : std::string new_manifest_file;
804 [ + + ]: 3181 : Status s;
805 [ + + ]: 3181 : if (descriptor_log_ == nullptr) {
806 : : // No reason to unlock *mu here since we only hit this path in the
807 : : // first call to LogAndApply (when opening the database).
808 [ - + ]: 2847 : assert(descriptor_file_ == nullptr);
809 [ + - ]: 2847 : new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
810 [ + - ]: 2847 : edit->SetNextFile(next_file_number_);
811 [ + - - + ]: 2847 : s = env_->NewWritableFile(new_manifest_file, &descriptor_file_);
812 [ + - ]: 2847 : if (s.ok()) {
813 [ + - + - ]: 2847 : descriptor_log_ = new log::Writer(descriptor_file_);
814 [ + - - + ]: 2847 : s = WriteSnapshot(descriptor_log_);
815 : : }
816 : : }
817 : :
818 : : // Unlock during expensive MANIFEST log write
819 : 3181 : {
820 : 3181 : mu->Unlock();
821 : :
822 : : // Write new record to MANIFEST log
823 [ + - ]: 3181 : if (s.ok()) {
824 [ + - ]: 3181 : std::string record;
825 [ + - ]: 3181 : edit->EncodeTo(&record);
826 [ - + + - : 3181 : s = descriptor_log_->AddRecord(record);
- + ]
827 [ + - ]: 3181 : if (s.ok()) {
828 [ + - - + ]: 3181 : s = descriptor_file_->Sync();
829 : : }
830 [ - + ]: 3181 : if (!s.ok()) {
831 [ # # # # ]: 0 : Log(options_->info_log, "MANIFEST write: %s\n", s.ToString().c_str());
832 : : }
833 : 3181 : }
834 : :
835 : : // If we just created a new descriptor file, install it by writing a
836 : : // new CURRENT file that points to it.
837 [ + - + + ]: 3181 : if (s.ok() && !new_manifest_file.empty()) {
838 [ + - - + ]: 2847 : s = SetCurrentFile(env_, dbname_, manifest_file_number_);
839 : : }
840 : :
841 [ + - ]: 3181 : mu->Lock();
842 : : }
843 : :
844 : : // Install the new version
845 [ + - ]: 3181 : if (s.ok()) {
846 [ + - ]: 3181 : AppendVersion(v);
847 : 3181 : log_number_ = edit->log_number_;
848 : 3181 : prev_log_number_ = edit->prev_log_number_;
849 : : } else {
850 [ # # ]: 0 : delete v;
851 [ # # ]: 0 : if (!new_manifest_file.empty()) {
852 [ # # ]: 0 : delete descriptor_log_;
853 [ # # ]: 0 : delete descriptor_file_;
854 : 0 : descriptor_log_ = nullptr;
855 : 0 : descriptor_file_ = nullptr;
856 [ # # ]: 0 : env_->DeleteFile(new_manifest_file);
857 : : }
858 : : }
859 : :
860 : 3181 : return s;
861 : 3181 : }
862 : :
863 : 2854 : Status VersionSet::Recover(bool* save_manifest) {
864 : 0 : struct LogReporter : public log::Reader::Reporter {
865 : : Status* status;
866 : 0 : void Corruption(size_t bytes, const Status& s) override {
867 [ # # ]: 0 : if (this->status->ok()) *this->status = s;
868 : 0 : }
869 : : };
870 : :
871 : : // Read "CURRENT" file, which contains a pointer to the current manifest file
872 [ + - ]: 2854 : std::string current;
873 [ + - + - ]: 2854 : Status s = ReadFileToString(env_, CurrentFileName(dbname_), ¤t);
874 [ - + ]: 2854 : if (!s.ok()) {
875 : 0 : return s;
876 : : }
877 [ + - + + ]: 5708 : if (current.empty() || current[current.size() - 1] != '\n') {
878 [ + - + + ]: 2854 : return Status::Corruption("CURRENT file does not end with newline");
879 : : }
880 [ + - ]: 2853 : current.resize(current.size() - 1);
881 : :
882 [ + - + - ]: 2853 : std::string dscname = dbname_ + "/" + current;
883 : 2853 : SequentialFile* file;
884 [ + - - + ]: 2853 : s = env_->NewSequentialFile(dscname, &file);
885 [ + + ]: 2853 : if (!s.ok()) {
886 [ + - ]: 1 : if (s.IsNotFound()) {
887 [ + - ]: 1 : return Status::Corruption("CURRENT points to a non-existent file",
888 [ + - + - ]: 2 : s.ToString());
889 : : }
890 : 0 : return s;
891 : : }
892 : :
893 : 2852 : bool have_log_number = false;
894 : 2852 : bool have_prev_log_number = false;
895 : 2852 : bool have_next_file = false;
896 : 2852 : bool have_last_sequence = false;
897 : 2852 : uint64_t next_file = 0;
898 : 2852 : uint64_t last_sequence = 0;
899 : 2852 : uint64_t log_number = 0;
900 : 2852 : uint64_t prev_log_number = 0;
901 [ + - ]: 2852 : Builder builder(this, current_);
902 : :
903 : 2852 : {
904 [ + - ]: 2852 : LogReporter reporter;
905 : 2852 : reporter.status = &s;
906 : 2852 : log::Reader reader(file, &reporter, true /*checksum*/,
907 [ + - ]: 2852 : 0 /*initial_offset*/);
908 : 2852 : Slice record;
909 : 2852 : std::string scratch;
910 [ + - + + : 7706 : while (reader.ReadRecord(&record, &scratch) && s.ok()) {
- + ]
911 [ + - ]: 4854 : VersionEdit edit;
912 [ + - - + ]: 4854 : s = edit.DecodeFrom(record);
913 [ + - ]: 4854 : if (s.ok()) {
914 [ + + ]: 4854 : if (edit.has_comparator_ &&
915 [ + - - + ]: 2852 : edit.comparator_ != icmp_.user_comparator()->Name()) {
916 [ # # ]: 0 : s = Status::InvalidArgument(
917 [ # # # # ]: 0 : edit.comparator_ + " does not match existing comparator ",
918 [ # # # # : 0 : icmp_.user_comparator()->Name());
# # ]
919 : : }
920 : : }
921 : :
922 [ + - ]: 4854 : if (s.ok()) {
923 [ + - ]: 4854 : builder.Apply(&edit);
924 : : }
925 : :
926 [ + + ]: 4854 : if (edit.has_log_number_) {
927 : 3096 : log_number = edit.log_number_;
928 : 3096 : have_log_number = true;
929 : : }
930 : :
931 [ + + ]: 4854 : if (edit.has_prev_log_number_) {
932 : 2002 : prev_log_number = edit.prev_log_number_;
933 : 2002 : have_prev_log_number = true;
934 : : }
935 : :
936 [ + + ]: 4854 : if (edit.has_next_file_number_) {
937 : 3096 : next_file = edit.next_file_number_;
938 : 3096 : have_next_file = true;
939 : : }
940 : :
941 [ + + ]: 4854 : if (edit.has_last_sequence_) {
942 : 3096 : last_sequence = edit.last_sequence_;
943 : 3096 : have_last_sequence = true;
944 : : }
945 : 4854 : }
946 : 2852 : }
947 [ + - ]: 2852 : delete file;
948 : 2852 : file = nullptr;
949 : :
950 [ + - ]: 2852 : if (s.ok()) {
951 [ - + ]: 2852 : if (!have_next_file) {
952 [ # # # # ]: 0 : s = Status::Corruption("no meta-nextfile entry in descriptor");
953 [ - + ]: 2852 : } else if (!have_log_number) {
954 [ # # # # ]: 0 : s = Status::Corruption("no meta-lognumber entry in descriptor");
955 [ - + ]: 2852 : } else if (!have_last_sequence) {
956 [ # # # # ]: 0 : s = Status::Corruption("no last-sequence-number entry in descriptor");
957 : : }
958 : :
959 [ + + ]: 2852 : if (!have_prev_log_number) {
960 : 1094 : prev_log_number = 0;
961 : : }
962 : :
963 [ + - ]: 2852 : MarkFileNumberUsed(prev_log_number);
964 [ + - ]: 2852 : MarkFileNumberUsed(log_number);
965 : : }
966 : :
967 [ + - ]: 2852 : if (s.ok()) {
968 [ + - + - ]: 2852 : Version* v = new Version(this);
969 [ + - ]: 2852 : builder.SaveTo(v);
970 : : // Install recovered version
971 [ + - ]: 2852 : Finalize(v);
972 [ + - ]: 2852 : AppendVersion(v);
973 : 2852 : manifest_file_number_ = next_file;
974 : 2852 : next_file_number_ = next_file + 1;
975 : 2852 : last_sequence_ = last_sequence;
976 : 2852 : log_number_ = log_number;
977 : 2852 : prev_log_number_ = prev_log_number;
978 : :
979 : : // See if we can reuse the existing MANIFEST file.
980 [ + - + - ]: 2852 : if (ReuseManifest(dscname, current)) {
981 : : // No need to save new manifest
982 : : } else {
983 : 2852 : *save_manifest = true;
984 : : }
985 : : }
986 : :
987 : 2852 : return s;
988 : 8559 : }
989 : :
990 : 2852 : bool VersionSet::ReuseManifest(const std::string& dscname,
991 : : const std::string& dscbase) {
992 [ - + ]: 2852 : if (!options_->reuse_logs) {
993 : : return false;
994 : : }
995 : 0 : FileType manifest_type;
996 : 0 : uint64_t manifest_number;
997 : 0 : uint64_t manifest_size;
998 [ # # ]: 0 : if (!ParseFileName(dscbase, &manifest_number, &manifest_type) ||
999 [ # # # # ]: 0 : manifest_type != kDescriptorFile ||
1000 [ # # # # ]: 0 : !env_->GetFileSize(dscname, &manifest_size).ok() ||
1001 : : // Make new compacted MANIFEST if old one is too big
1002 [ # # ]: 0 : manifest_size >= TargetFileSize(options_)) {
1003 : : return false;
1004 : : }
1005 : :
1006 [ # # ]: 0 : assert(descriptor_file_ == nullptr);
1007 [ # # ]: 0 : assert(descriptor_log_ == nullptr);
1008 : 0 : Status r = env_->NewAppendableFile(dscname, &descriptor_file_);
1009 [ # # ]: 0 : if (!r.ok()) {
1010 [ # # # # ]: 0 : Log(options_->info_log, "Reuse MANIFEST: %s\n", r.ToString().c_str());
1011 [ # # ]: 0 : assert(descriptor_file_ == nullptr);
1012 : : return false;
1013 : : }
1014 : :
1015 [ # # ]: 0 : Log(options_->info_log, "Reusing MANIFEST %s\n", dscname.c_str());
1016 [ # # # # ]: 0 : descriptor_log_ = new log::Writer(descriptor_file_, manifest_size);
1017 : 0 : manifest_file_number_ = manifest_number;
1018 : 0 : return true;
1019 : 0 : }
1020 : :
1021 : 7458 : void VersionSet::MarkFileNumberUsed(uint64_t number) {
1022 [ + + ]: 7458 : if (next_file_number_ <= number) {
1023 : 1758 : next_file_number_ = number + 1;
1024 : : }
1025 : 7458 : }
1026 : :
1027 : 6033 : void VersionSet::Finalize(Version* v) {
1028 : : // Precomputed best level for next compaction
1029 : 6033 : int best_level = -1;
1030 : 6033 : double best_score = -1;
1031 : :
1032 [ + + ]: 42231 : for (int level = 0; level < config::kNumLevels - 1; level++) {
1033 : 36198 : double score;
1034 [ + + ]: 36198 : if (level == 0) {
1035 : : // We treat level-0 specially by bounding the number of files
1036 : : // instead of number of bytes for two reasons:
1037 : : //
1038 : : // (1) With larger write-buffer sizes, it is nice not to do too
1039 : : // many level-0 compactions.
1040 : : //
1041 : : // (2) The files in level-0 are merged on every read and
1042 : : // therefore we wish to avoid too many files when the individual
1043 : : // file size is small (perhaps because of a small write-buffer
1044 : : // setting, or very high compression ratios, or lots of
1045 : : // overwrites/deletions).
1046 [ - + ]: 6033 : score = v->files_[level].size() /
1047 : : static_cast<double>(config::kL0_CompactionTrigger);
1048 : : } else {
1049 : : // Compute the ratio of current size to size limit.
1050 : 30165 : const uint64_t level_bytes = TotalFileSize(v->files_[level]);
1051 : 30165 : score =
1052 : 30165 : static_cast<double>(level_bytes) / MaxBytesForLevel(options_, level);
1053 : : }
1054 : :
1055 [ + + ]: 36198 : if (score > best_score) {
1056 : 6617 : best_level = level;
1057 : 6617 : best_score = score;
1058 : : }
1059 : : }
1060 : :
1061 : 6033 : v->compaction_level_ = best_level;
1062 : 6033 : v->compaction_score_ = best_score;
1063 : 6033 : }
1064 : :
1065 : 2847 : Status VersionSet::WriteSnapshot(log::Writer* log) {
1066 : : // TODO: Break up into multiple records to reduce memory usage on recovery?
1067 : :
1068 : : // Save metadata
1069 : 2847 : VersionEdit edit;
1070 [ + - + - ]: 2847 : edit.SetComparatorName(icmp_.user_comparator()->Name());
1071 : :
1072 : : // Save compaction pointers
1073 [ + + ]: 22776 : for (int level = 0; level < config::kNumLevels; level++) {
1074 [ + + ]: 19929 : if (!compact_pointer_[level].empty()) {
1075 [ - + ]: 596 : InternalKey key;
1076 [ - + + - ]: 596 : key.DecodeFrom(compact_pointer_[level]);
1077 [ + - ]: 596 : edit.SetCompactPointer(level, key);
1078 : 596 : }
1079 : : }
1080 : :
1081 : : // Save files
1082 [ + + ]: 22776 : for (int level = 0; level < config::kNumLevels; level++) {
1083 : 19929 : const std::vector<FileMetaData*>& files = current_->files_[level];
1084 [ - + + + ]: 22151 : for (size_t i = 0; i < files.size(); i++) {
1085 [ + - ]: 2222 : const FileMetaData* f = files[i];
1086 [ + - ]: 2222 : edit.AddFile(level, f->number, f->file_size, f->smallest, f->largest);
1087 : : }
1088 : : }
1089 : :
1090 [ + - ]: 2847 : std::string record;
1091 [ + - ]: 2847 : edit.EncodeTo(&record);
1092 [ - + + - ]: 5694 : return log->AddRecord(record);
1093 : 2847 : }
1094 : :
1095 : 41561 : int VersionSet::NumLevelFiles(int level) const {
1096 [ - + ]: 41561 : assert(level >= 0);
1097 [ - + ]: 41561 : assert(level < config::kNumLevels);
1098 [ - + ]: 41561 : return current_->files_[level].size();
1099 : : }
1100 : :
1101 : 293 : const char* VersionSet::LevelSummary(LevelSummaryStorage* scratch) const {
1102 : : // Update code if kNumLevels changes
1103 : 293 : static_assert(config::kNumLevels == 7, "");
1104 : 2344 : snprintf(scratch->buffer, sizeof(scratch->buffer),
1105 : 586 : "files[ %d %d %d %d %d %d %d ]", int(current_->files_[0].size()),
1106 [ - + - + ]: 293 : int(current_->files_[1].size()), int(current_->files_[2].size()),
1107 [ - + - + ]: 293 : int(current_->files_[3].size()), int(current_->files_[4].size()),
1108 [ - + - + : 293 : int(current_->files_[5].size()), int(current_->files_[6].size()));
- + ]
1109 : 293 : return scratch->buffer;
1110 : : }
1111 : :
1112 : 204 : uint64_t VersionSet::ApproximateOffsetOf(Version* v, const InternalKey& ikey) {
1113 : 204 : uint64_t result = 0;
1114 [ + + ]: 1632 : for (int level = 0; level < config::kNumLevels; level++) {
1115 : : const std::vector<FileMetaData*>& files = v->files_[level];
1116 [ - + + + ]: 1640 : for (size_t i = 0; i < files.size(); i++) {
1117 [ + + ]: 212 : if (icmp_.Compare(files[i]->largest, ikey) <= 0) {
1118 : : // Entire file is before "ikey", so just add the file size
1119 : 48 : result += files[i]->file_size;
1120 [ - + ]: 164 : } else if (icmp_.Compare(files[i]->smallest, ikey) > 0) {
1121 : : // Entire file is after "ikey", so ignore
1122 [ # # ]: 0 : if (level > 0) {
1123 : : // Files other than level 0 are sorted by meta->smallest, so
1124 : : // no further files in this level will contain data for
1125 : : // "ikey".
1126 : : break;
1127 : : }
1128 : : } else {
1129 : : // "ikey" falls in the range for this table. Add the
1130 : : // approximate offset of "ikey" within the table.
1131 : 164 : Table* tableptr;
1132 : 164 : Iterator* iter = table_cache_->NewIterator(
1133 : 164 : ReadOptions(), files[i]->number, files[i]->file_size, &tableptr);
1134 [ + - ]: 164 : if (tableptr != nullptr) {
1135 : 164 : result += tableptr->ApproximateOffsetOf(ikey.Encode());
1136 : : }
1137 [ + - ]: 164 : delete iter;
1138 : : }
1139 : : }
1140 : : }
1141 : 204 : return result;
1142 : : }
1143 : :
1144 : 6033 : void VersionSet::AddLiveFiles(std::set<uint64_t>* live) {
1145 [ + + ]: 12068 : for (Version* v = dummy_versions_.next_; v != &dummy_versions_;
1146 : 6035 : v = v->next_) {
1147 [ + + ]: 48280 : for (int level = 0; level < config::kNumLevels; level++) {
1148 : : const std::vector<FileMetaData*>& files = v->files_[level];
1149 [ - + + + ]: 48880 : for (size_t i = 0; i < files.size(); i++) {
1150 : 6635 : live->insert(files[i]->number);
1151 : : }
1152 : : }
1153 : : }
1154 : 6033 : }
1155 : :
1156 : 0 : int64_t VersionSet::NumLevelBytes(int level) const {
1157 [ # # ]: 0 : assert(level >= 0);
1158 [ # # ]: 0 : assert(level < config::kNumLevels);
1159 : 0 : return TotalFileSize(current_->files_[level]);
1160 : : }
1161 : :
1162 : 0 : int64_t VersionSet::MaxNextLevelOverlappingBytes() {
1163 : 0 : int64_t result = 0;
1164 : 0 : std::vector<FileMetaData*> overlaps;
1165 [ # # ]: 0 : for (int level = 1; level < config::kNumLevels - 1; level++) {
1166 [ # # # # ]: 0 : for (size_t i = 0; i < current_->files_[level].size(); i++) {
1167 [ # # ]: 0 : const FileMetaData* f = current_->files_[level][i];
1168 [ # # ]: 0 : current_->GetOverlappingInputs(level + 1, &f->smallest, &f->largest,
1169 : : &overlaps);
1170 : 0 : const int64_t sum = TotalFileSize(overlaps);
1171 [ # # ]: 0 : if (sum > result) {
1172 : 0 : result = sum;
1173 : : }
1174 : : }
1175 : : }
1176 : 0 : return result;
1177 : 0 : }
1178 : :
1179 : : // Stores the minimal range that covers all entries in inputs in
1180 : : // *smallest, *largest.
1181 : : // REQUIRES: inputs is not empty
1182 : 879 : void VersionSet::GetRange(const std::vector<FileMetaData*>& inputs,
1183 : : InternalKey* smallest, InternalKey* largest) {
1184 [ - + ]: 879 : assert(!inputs.empty());
1185 : 879 : smallest->Clear();
1186 : 879 : largest->Clear();
1187 [ - + + + ]: 3221 : for (size_t i = 0; i < inputs.size(); i++) {
1188 [ + + ]: 2342 : FileMetaData* f = inputs[i];
1189 [ + + ]: 2342 : if (i == 0) {
1190 : 879 : *smallest = f->smallest;
1191 : 879 : *largest = f->largest;
1192 : : } else {
1193 [ + + ]: 1463 : if (icmp_.Compare(f->smallest, *smallest) < 0) {
1194 : 131 : *smallest = f->smallest;
1195 : : }
1196 [ + + ]: 1463 : if (icmp_.Compare(f->largest, *largest) > 0) {
1197 : 518 : *largest = f->largest;
1198 : : }
1199 : : }
1200 : : }
1201 : 879 : }
1202 : :
1203 : : // Stores the minimal range that covers all entries in inputs1 and inputs2
1204 : : // in *smallest, *largest.
1205 : : // REQUIRES: inputs is not empty
1206 : 293 : void VersionSet::GetRange2(const std::vector<FileMetaData*>& inputs1,
1207 : : const std::vector<FileMetaData*>& inputs2,
1208 : : InternalKey* smallest, InternalKey* largest) {
1209 : 293 : std::vector<FileMetaData*> all = inputs1;
1210 [ + - ]: 293 : all.insert(all.end(), inputs2.begin(), inputs2.end());
1211 [ + - ]: 293 : GetRange(all, smallest, largest);
1212 : 293 : }
1213 : :
1214 : 293 : Iterator* VersionSet::MakeInputIterator(Compaction* c) {
1215 : 293 : ReadOptions options;
1216 : 293 : options.verify_checksums = options_->paranoid_checks;
1217 : 293 : options.fill_cache = false;
1218 : :
1219 : : // Level-0 files have to be merged together. For other levels,
1220 : : // we will make a concatenating iterator per level.
1221 : : // TODO(opt): use concatenating iterator for level-0 if there is no overlap
1222 [ + - - + ]: 293 : const int space = (c->level() == 0 ? c->inputs_[0].size() + 1 : 2);
1223 [ + - ]: 293 : Iterator** list = new Iterator*[space];
1224 : 293 : int num = 0;
1225 [ + + ]: 879 : for (int which = 0; which < 2; which++) {
1226 [ + + ]: 586 : if (!c->inputs_[which].empty()) {
1227 [ + + ]: 434 : if (c->level() + which == 0) {
1228 : : const std::vector<FileMetaData*>& files = c->inputs_[which];
1229 [ - + + + ]: 1247 : for (size_t i = 0; i < files.size(); i++) {
1230 : 954 : list[num++] = table_cache_->NewIterator(options, files[i]->number,
1231 : 954 : files[i]->file_size);
1232 : : }
1233 : : } else {
1234 : : // Create concatenating iterator for the files from this level
1235 [ + - - - ]: 141 : list[num++] = NewTwoLevelIterator(
1236 [ + - ]: 141 : new Version::LevelFileNumIterator(icmp_, &c->inputs_[which]),
1237 : 141 : &GetFileIterator, table_cache_, options);
1238 : : }
1239 : : }
1240 : : }
1241 [ - + ]: 293 : assert(num <= space);
1242 : 293 : Iterator* result = NewMergingIterator(&icmp_, list, num);
1243 [ + - ]: 293 : delete[] list;
1244 : 293 : return result;
1245 : : }
1246 : :
1247 : 293 : Compaction* VersionSet::PickCompaction() {
1248 : 293 : Compaction* c;
1249 : 293 : int level;
1250 : :
1251 : : // We prefer compactions triggered by too much data in a level over
1252 : : // the compactions triggered by seeks.
1253 : 293 : const bool size_compaction = (current_->compaction_score_ >= 1);
1254 : 293 : const bool seek_compaction = (current_->file_to_compact_ != nullptr);
1255 [ + + ]: 293 : if (size_compaction) {
1256 : 201 : level = current_->compaction_level_;
1257 [ - + ]: 201 : assert(level >= 0);
1258 [ - + ]: 201 : assert(level + 1 < config::kNumLevels);
1259 [ + - ]: 201 : c = new Compaction(options_, level);
1260 : :
1261 : : // Pick the first file that comes after compact_pointer_[level]
1262 [ - + + + ]: 511 : for (size_t i = 0; i < current_->files_[level].size(); i++) {
1263 [ + + ]: 435 : FileMetaData* f = current_->files_[level][i];
1264 [ + + ]: 316 : if (compact_pointer_[level].empty() ||
1265 [ - + ]: 316 : icmp_.Compare(f->largest.Encode(), compact_pointer_[level]) > 0) {
1266 : 125 : c->inputs_[0].push_back(f);
1267 : 125 : break;
1268 : : }
1269 : : }
1270 [ + + ]: 201 : if (c->inputs_[0].empty()) {
1271 : : // Wrap-around to the beginning of the key space
1272 : 76 : c->inputs_[0].push_back(current_->files_[level][0]);
1273 : : }
1274 [ + - ]: 92 : } else if (seek_compaction) {
1275 : 92 : level = current_->file_to_compact_level_;
1276 [ + - ]: 92 : c = new Compaction(options_, level);
1277 : 92 : c->inputs_[0].push_back(current_->file_to_compact_);
1278 : : } else {
1279 : : return nullptr;
1280 : : }
1281 : :
1282 : 293 : c->input_version_ = current_;
1283 : 293 : c->input_version_->Ref();
1284 : :
1285 : : // Files in level 0 may overlap each other, so pick up all overlapping ones
1286 [ + - ]: 293 : if (level == 0) {
1287 [ + - ]: 293 : InternalKey smallest, largest;
1288 [ + - ]: 293 : GetRange(c->inputs_[0], &smallest, &largest);
1289 : : // Note that the next call will discard the file we placed in
1290 : : // c->inputs_[0] earlier and replace it with an overlapping set
1291 : : // which will include the picked file.
1292 [ + - ]: 293 : current_->GetOverlappingInputs(0, &smallest, &largest, &c->inputs_[0]);
1293 [ - + ]: 293 : assert(!c->inputs_[0].empty());
1294 : 293 : }
1295 : :
1296 : 293 : SetupOtherInputs(c);
1297 : :
1298 : 293 : return c;
1299 : : }
1300 : :
1301 : : // Finds the largest key in a vector of files. Returns true if files it not
1302 : : // empty.
1303 : 434 : bool FindLargestKey(const InternalKeyComparator& icmp,
1304 : : const std::vector<FileMetaData*>& files,
1305 : : InternalKey* largest_key) {
1306 [ + - ]: 434 : if (files.empty()) {
1307 : : return false;
1308 : : }
1309 : 434 : *largest_key = files[0]->largest;
1310 [ - + + + ]: 1362 : for (size_t i = 1; i < files.size(); ++i) {
1311 : 928 : FileMetaData* f = files[i];
1312 [ + + ]: 928 : if (icmp.Compare(f->largest, *largest_key) > 0) {
1313 : 461 : *largest_key = f->largest;
1314 : : }
1315 : : }
1316 : : return true;
1317 : : }
1318 : :
1319 : : // Finds minimum file b2=(l2, u2) in level file for which l2 > u1 and
1320 : : // user_key(l2) = user_key(u1)
1321 : 434 : FileMetaData* FindSmallestBoundaryFile(
1322 : : const InternalKeyComparator& icmp,
1323 : : const std::vector<FileMetaData*>& level_files,
1324 : : const InternalKey& largest_key) {
1325 : 434 : const Comparator* user_cmp = icmp.user_comparator();
1326 : 434 : FileMetaData* smallest_boundary_file = nullptr;
1327 [ - + + + ]: 1797 : for (size_t i = 0; i < level_files.size(); ++i) {
1328 : 1363 : FileMetaData* f = level_files[i];
1329 [ - + - - ]: 1363 : if (icmp.Compare(f->smallest, largest_key) > 0 &&
1330 [ # # # # ]: 0 : user_cmp->Compare(f->smallest.user_key(), largest_key.user_key()) ==
1331 : : 0) {
1332 [ # # # # ]: 0 : if (smallest_boundary_file == nullptr ||
1333 : 0 : icmp.Compare(f->smallest, smallest_boundary_file->smallest) < 0) {
1334 : : smallest_boundary_file = f;
1335 : : }
1336 : : }
1337 : : }
1338 : 434 : return smallest_boundary_file;
1339 : : }
1340 : :
1341 : : // Extracts the largest file b1 from |compaction_files| and then searches for a
1342 : : // b2 in |level_files| for which user_key(u1) = user_key(l2). If it finds such a
1343 : : // file b2 (known as a boundary file) it adds it to |compaction_files| and then
1344 : : // searches again using this new upper bound.
1345 : : //
1346 : : // If there are two blocks, b1=(l1, u1) and b2=(l2, u2) and
1347 : : // user_key(u1) = user_key(l2), and if we compact b1 but not b2 then a
1348 : : // subsequent get operation will yield an incorrect result because it will
1349 : : // return the record from b2 in level i rather than from b1 because it searches
1350 : : // level by level for records matching the supplied user key.
1351 : : //
1352 : : // parameters:
1353 : : // in level_files: List of files to search for boundary files.
1354 : : // in/out compaction_files: List of files to extend by adding boundary files.
1355 : 434 : void AddBoundaryInputs(const InternalKeyComparator& icmp,
1356 : : const std::vector<FileMetaData*>& level_files,
1357 : : std::vector<FileMetaData*>* compaction_files) {
1358 [ + - ]: 434 : InternalKey largest_key;
1359 : :
1360 : : // Quick return if compaction_files is empty.
1361 [ + - - + ]: 434 : if (!FindLargestKey(icmp, *compaction_files, &largest_key)) {
1362 : 0 : return;
1363 : : }
1364 : :
1365 : : bool continue_searching = true;
1366 : 868 : while (continue_searching) {
1367 : 434 : FileMetaData* smallest_boundary_file =
1368 : 868 : FindSmallestBoundaryFile(icmp, level_files, largest_key);
1369 : :
1370 : : // If a boundary file was found advance largest_key, otherwise we're done.
1371 [ + - ]: 434 : if (smallest_boundary_file != NULL) {
1372 [ # # ]: 0 : compaction_files->push_back(smallest_boundary_file);
1373 [ - - + - ]: 868 : largest_key = smallest_boundary_file->largest;
1374 : : } else {
1375 : : continue_searching = false;
1376 : : }
1377 : : }
1378 : 434 : }
1379 : :
1380 : 293 : void VersionSet::SetupOtherInputs(Compaction* c) {
1381 [ + - ]: 293 : const int level = c->level();
1382 [ + - ]: 293 : InternalKey smallest, largest;
1383 : :
1384 [ + - ]: 293 : AddBoundaryInputs(icmp_, current_->files_[level], &c->inputs_[0]);
1385 [ + - ]: 293 : GetRange(c->inputs_[0], &smallest, &largest);
1386 : :
1387 [ + - ]: 293 : current_->GetOverlappingInputs(level + 1, &smallest, &largest,
1388 : : &c->inputs_[1]);
1389 : :
1390 : : // Get entire range covered by compaction
1391 [ + - ]: 293 : InternalKey all_start, all_limit;
1392 [ + - ]: 293 : GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);
1393 : :
1394 : : // See if we can grow the number of inputs in "level" without
1395 : : // changing the number of "level+1" files we pick up.
1396 [ + + ]: 293 : if (!c->inputs_[1].empty()) {
1397 : 141 : std::vector<FileMetaData*> expanded0;
1398 [ + - ]: 141 : current_->GetOverlappingInputs(level, &all_start, &all_limit, &expanded0);
1399 [ + - ]: 141 : AddBoundaryInputs(icmp_, current_->files_[level], &expanded0);
1400 : 141 : const int64_t inputs0_size = TotalFileSize(c->inputs_[0]);
1401 : 141 : const int64_t inputs1_size = TotalFileSize(c->inputs_[1]);
1402 : 141 : const int64_t expanded0_size = TotalFileSize(expanded0);
1403 [ - + - + : 141 : if (expanded0.size() > c->inputs_[0].size() &&
- + ]
1404 : 0 : inputs1_size + expanded0_size <
1405 [ # # ]: 0 : ExpandedCompactionByteSizeLimit(options_)) {
1406 [ # # ]: 0 : InternalKey new_start, new_limit;
1407 [ # # ]: 0 : GetRange(expanded0, &new_start, &new_limit);
1408 : 0 : std::vector<FileMetaData*> expanded1;
1409 [ # # ]: 0 : current_->GetOverlappingInputs(level + 1, &new_start, &new_limit,
1410 : : &expanded1);
1411 [ # # # # : 0 : if (expanded1.size() == c->inputs_[1].size()) {
# # ]
1412 [ # # ]: 0 : Log(options_->info_log,
1413 : : "Expanding@%d %d+%d (%ld+%ld bytes) to %d+%d (%ld+%ld bytes)\n",
1414 [ # # ]: 0 : level, int(c->inputs_[0].size()), int(c->inputs_[1].size()),
1415 [ # # ]: 0 : long(inputs0_size), long(inputs1_size), int(expanded0.size()),
1416 [ # # ]: 0 : int(expanded1.size()), long(expanded0_size), long(inputs1_size));
1417 [ # # ]: 0 : smallest = new_start;
1418 [ # # ]: 0 : largest = new_limit;
1419 [ # # ]: 0 : c->inputs_[0] = expanded0;
1420 [ # # ]: 0 : c->inputs_[1] = expanded1;
1421 [ # # ]: 0 : GetRange2(c->inputs_[0], c->inputs_[1], &all_start, &all_limit);
1422 : : }
1423 : 0 : }
1424 : 141 : }
1425 : :
1426 : : // Compute the set of grandparent files that overlap this compaction
1427 : : // (parent == level+1; grandparent == level+2)
1428 [ + - ]: 293 : if (level + 2 < config::kNumLevels) {
1429 [ + - ]: 293 : current_->GetOverlappingInputs(level + 2, &all_start, &all_limit,
1430 : : &c->grandparents_);
1431 : : }
1432 : :
1433 : : // Update the place where we will do the next compaction for this level.
1434 : : // We update this immediately instead of waiting for the VersionEdit
1435 : : // to be applied so that if the compaction fails, we will try a different
1436 : : // key range next time.
1437 [ + - ]: 293 : compact_pointer_[level] = largest.Encode().ToString();
1438 [ + - ]: 293 : c->edit_.SetCompactPointer(level, largest);
1439 : 293 : }
1440 : :
1441 : 0 : Compaction* VersionSet::CompactRange(int level, const InternalKey* begin,
1442 : : const InternalKey* end) {
1443 : 0 : std::vector<FileMetaData*> inputs;
1444 [ # # ]: 0 : current_->GetOverlappingInputs(level, begin, end, &inputs);
1445 [ # # ]: 0 : if (inputs.empty()) {
1446 : : return nullptr;
1447 : : }
1448 : :
1449 : : // Avoid compacting too much in one shot in case the range is large.
1450 : : // But we cannot do this for level-0 since level-0 files can overlap
1451 : : // and we must not pick one file and drop another older file if the
1452 : : // two files overlap.
1453 [ # # ]: 0 : if (level > 0) {
1454 : 0 : const uint64_t limit = MaxFileSizeForLevel(options_, level);
1455 : 0 : uint64_t total = 0;
1456 [ # # # # ]: 0 : for (size_t i = 0; i < inputs.size(); i++) {
1457 [ # # ]: 0 : uint64_t s = inputs[i]->file_size;
1458 : 0 : total += s;
1459 [ # # ]: 0 : if (total >= limit) {
1460 [ # # ]: 0 : inputs.resize(i + 1);
1461 : : break;
1462 : : }
1463 : : }
1464 : : }
1465 : :
1466 [ # # # # ]: 0 : Compaction* c = new Compaction(options_, level);
1467 : 0 : c->input_version_ = current_;
1468 [ # # ]: 0 : c->input_version_->Ref();
1469 [ # # ]: 0 : c->inputs_[0] = inputs;
1470 [ # # ]: 0 : SetupOtherInputs(c);
1471 : : return c;
1472 : 0 : }
1473 : :
1474 : 293 : Compaction::Compaction(const Options* options, int level)
1475 : 293 : : level_(level),
1476 : 293 : max_output_file_size_(MaxFileSizeForLevel(options, level)),
1477 : 293 : input_version_(nullptr),
1478 : 293 : grandparent_index_(0),
1479 : 293 : seen_key_(false),
1480 : 293 : overlapped_bytes_(0) {
1481 [ + + ]: 2344 : for (int i = 0; i < config::kNumLevels; i++) {
1482 : 2051 : level_ptrs_[i] = 0;
1483 : : }
1484 : 293 : }
1485 : :
1486 : 879 : Compaction::~Compaction() {
1487 [ - + ]: 293 : if (input_version_ != nullptr) {
1488 : 0 : input_version_->Unref();
1489 : : }
1490 [ + - + + ]: 1465 : }
1491 : :
1492 : 293 : bool Compaction::IsTrivialMove() const {
1493 : 293 : const VersionSet* vset = input_version_->vset_;
1494 : : // Avoid a move if there is lots of overlapping grandparent data.
1495 : : // Otherwise, the move could create a parent file that will require
1496 : : // a very expensive merge later on.
1497 [ - + + + : 336 : return (num_input_files(0) == 1 && num_input_files(1) == 0 &&
- + ]
1498 : 0 : TotalFileSize(grandparents_) <=
1499 [ # # ]: 0 : MaxGrandParentOverlapBytes(vset->options_));
1500 : : }
1501 : :
1502 : 292 : void Compaction::AddInputDeletions(VersionEdit* edit) {
1503 [ + + ]: 876 : for (int which = 0; which < 2; which++) {
1504 [ - + + + ]: 1675 : for (size_t i = 0; i < inputs_[which].size(); i++) {
1505 : 1091 : edit->DeleteFile(level_ + which, inputs_[which][i]->number);
1506 : : }
1507 : : }
1508 : 292 : }
1509 : :
1510 : 1064 : bool Compaction::IsBaseLevelForKey(const Slice& user_key) {
1511 : : // Maybe use binary search to find right entry instead of linear search?
1512 : 1064 : const Comparator* user_cmp = input_version_->vset_->icmp_.user_comparator();
1513 [ + + ]: 6384 : for (int lvl = level_ + 2; lvl < config::kNumLevels; lvl++) {
1514 : 5320 : const std::vector<FileMetaData*>& files = input_version_->files_[lvl];
1515 [ - + - + ]: 5320 : while (level_ptrs_[lvl] < files.size()) {
1516 [ # # ]: 0 : FileMetaData* f = files[level_ptrs_[lvl]];
1517 [ # # # # ]: 0 : if (user_cmp->Compare(user_key, f->largest.user_key()) <= 0) {
1518 : : // We've advanced far enough
1519 [ # # # # ]: 0 : if (user_cmp->Compare(user_key, f->smallest.user_key()) >= 0) {
1520 : : // Key falls in this file's range, so definitely not base level
1521 : : return false;
1522 : : }
1523 : : break;
1524 : : }
1525 : 0 : level_ptrs_[lvl]++;
1526 : : }
1527 : : }
1528 : : return true;
1529 : : }
1530 : :
1531 : 120023 : bool Compaction::ShouldStopBefore(const Slice& internal_key) {
1532 : 120023 : const VersionSet* vset = input_version_->vset_;
1533 : : // Scan to find earliest grandparent file that contains key.
1534 : 120023 : const InternalKeyComparator* icmp = &vset->icmp_;
1535 [ - + + + : 120243 : while (grandparent_index_ < grandparents_.size() &&
+ + ]
1536 : 219 : icmp->Compare(internal_key,
1537 : 219 : grandparents_[grandparent_index_]->largest.Encode()) >
1538 : : 0) {
1539 [ + - ]: 1 : if (seen_key_) {
1540 : 1 : overlapped_bytes_ += grandparents_[grandparent_index_]->file_size;
1541 : : }
1542 : 1 : grandparent_index_++;
1543 : : }
1544 : 120023 : seen_key_ = true;
1545 : :
1546 [ - + ]: 120023 : if (overlapped_bytes_ > MaxGrandParentOverlapBytes(vset->options_)) {
1547 : : // Too much overlap for current output; start new output
1548 : 0 : overlapped_bytes_ = 0;
1549 : 0 : return true;
1550 : : } else {
1551 : : return false;
1552 : : }
1553 : : }
1554 : :
1555 : 293 : void Compaction::ReleaseInputs() {
1556 [ + - ]: 293 : if (input_version_ != nullptr) {
1557 : 293 : input_version_->Unref();
1558 : 293 : input_version_ = nullptr;
1559 : : }
1560 : 293 : }
1561 : :
1562 : : } // namespace leveldb
|
