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 : 35486 : static size_t TargetFileSize(const Options* options) {
# 26 : 35486 : return options->max_file_size;
# 27 : 35486 : }
# 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 : 35378 : static int64_t MaxGrandParentOverlapBytes(const Options* options) {
# 32 : 35378 : return 10 * TargetFileSize(options);
# 33 : 35378 : }
# 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 : 0 : }
# 41 : :
# 42 : 22475 : 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 : 22475 : double result = 10. * 1048576.0;
# 48 [ + + ]: 67425 : while (level > 1) {
# 49 : 44950 : result *= 10;
# 50 : 44950 : level--;
# 51 : 44950 : }
# 52 : 22475 : return result;
# 53 : 22475 : }
# 54 : :
# 55 : 108 : static uint64_t MaxFileSizeForLevel(const Options* options, int level) {
# 56 : : // We could vary per level to reduce number of files?
# 57 : 108 : return TargetFileSize(options);
# 58 : 108 : }
# 59 : :
# 60 : 22580 : static int64_t TotalFileSize(const std::vector<FileMetaData*>& files) {
# 61 : 22580 : int64_t sum = 0;
# 62 [ + + ]: 23332 : for (size_t i = 0; i < files.size(); i++) {
# 63 : 752 : sum += files[i]->file_size;
# 64 : 752 : }
# 65 : 22580 : return sum;
# 66 : 22580 : }
# 67 : :
# 68 : 8881 : Version::~Version() {
# 69 : 8881 : assert(refs_ == 0);
# 70 : :
# 71 : : // Remove from linked list
# 72 : 0 : prev_->next_ = next_;
# 73 : 8881 : next_->prev_ = prev_;
# 74 : :
# 75 : : // Drop references to files
# 76 [ + + ]: 71048 : for (int level = 0; level < config::kNumLevels; level++) {
# 77 [ + + ]: 64987 : for (size_t i = 0; i < files_[level].size(); i++) {
# 78 : 2820 : FileMetaData* f = files_[level][i];
# 79 : 2820 : assert(f->refs > 0);
# 80 : 0 : f->refs--;
# 81 [ + + ]: 2820 : if (f->refs <= 0) {
# 82 : 1952 : delete f;
# 83 : 1952 : }
# 84 : 2820 : }
# 85 : 62167 : }
# 86 : 8881 : }
# 87 : :
# 88 : : int FindFile(const InternalKeyComparator& icmp,
# 89 : 3247680 : const std::vector<FileMetaData*>& files, const Slice& key) {
# 90 : 3247680 : uint32_t left = 0;
# 91 : 3247680 : uint32_t right = files.size();
# 92 [ + + ]: 6495354 : while (left < right) {
# 93 : 3247674 : uint32_t mid = (left + right) / 2;
# 94 : 3247674 : const FileMetaData* f = files[mid];
# 95 [ + + ]: 3247674 : 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 : 1685 : left = mid + 1;
# 99 : 3245989 : } else {
# 100 : : // Key at "mid.largest" is >= "target". Therefore all files
# 101 : : // after "mid" are uninteresting.
# 102 : 3245989 : right = mid;
# 103 : 3245989 : }
# 104 : 3247674 : }
# 105 : 3247680 : return right;
# 106 : 3247680 : }
# 107 : :
# 108 : : static bool AfterFile(const Comparator* ucmp, const Slice* user_key,
# 109 : 0 : const FileMetaData* f) {
# 110 : : // null user_key occurs before all keys and is therefore never after *f
# 111 [ # # ]: 0 : return (user_key != nullptr &&
# 112 [ # # ]: 0 : ucmp->Compare(*user_key, f->largest.user_key()) > 0);
# 113 : 0 : }
# 114 : :
# 115 : : static bool BeforeFile(const Comparator* ucmp, const Slice* user_key,
# 116 : 0 : const FileMetaData* f) {
# 117 : : // null user_key occurs after all keys and is therefore never before *f
# 118 [ # # ]: 0 : return (user_key != nullptr &&
# 119 [ # # ]: 0 : ucmp->Compare(*user_key, f->smallest.user_key()) < 0);
# 120 : 0 : }
# 121 : :
# 122 : : bool SomeFileOverlapsRange(const InternalKeyComparator& icmp,
# 123 : : bool disjoint_sorted_files,
# 124 : : const std::vector<FileMetaData*>& files,
# 125 : : const Slice* smallest_user_key,
# 126 : 9 : const Slice* largest_user_key) {
# 127 : 9 : const Comparator* ucmp = icmp.user_comparator();
# 128 [ + + ]: 9 : if (!disjoint_sorted_files) {
# 129 : : // Need to check against all files
# 130 [ - + ]: 3 : for (size_t i = 0; i < files.size(); i++) {
# 131 : 0 : const FileMetaData* f = files[i];
# 132 [ # # ]: 0 : if (AfterFile(ucmp, smallest_user_key, f) ||
# 133 [ # # ]: 0 : BeforeFile(ucmp, largest_user_key, f)) {
# 134 : : // No overlap
# 135 : 0 : } else {
# 136 : 0 : return true; // Overlap
# 137 : 0 : }
# 138 : 0 : }
# 139 : 3 : return false;
# 140 : 3 : }
# 141 : :
# 142 : : // Binary search over file list
# 143 : 6 : uint32_t index = 0;
# 144 [ + - ]: 6 : if (smallest_user_key != nullptr) {
# 145 : : // Find the earliest possible internal key for smallest_user_key
# 146 : 6 : InternalKey small_key(*smallest_user_key, kMaxSequenceNumber,
# 147 : 6 : kValueTypeForSeek);
# 148 : 6 : index = FindFile(icmp, files, small_key.Encode());
# 149 : 6 : }
# 150 : :
# 151 [ + - ]: 6 : if (index >= files.size()) {
# 152 : : // beginning of range is after all files, so no overlap.
# 153 : 6 : return false;
# 154 : 6 : }
# 155 : :
# 156 : 0 : return !BeforeFile(ucmp, largest_user_key, files[index]);
# 157 : 6 : }
# 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 : : LevelFileNumIterator(const InternalKeyComparator& icmp,
# 167 : : const std::vector<FileMetaData*>* flist)
# 168 : 205 : : icmp_(icmp), flist_(flist), index_(flist->size()) { // Marks as invalid
# 169 : 205 : }
# 170 : 724 : bool Valid() const override { return index_ < flist_->size(); }
# 171 : 172 : void Seek(const Slice& target) override {
# 172 : 172 : index_ = FindFile(icmp_, *flist_, target);
# 173 : 172 : }
# 174 : 33 : void SeekToFirst() override { index_ = 0; }
# 175 : 0 : void SeekToLast() override {
# 176 [ # # ]: 0 : index_ = flist_->empty() ? 0 : flist_->size() - 1;
# 177 : 0 : }
# 178 : 39 : void Next() override {
# 179 : 39 : assert(Valid());
# 180 : 0 : index_++;
# 181 : 39 : }
# 182 : 0 : void Prev() override {
# 183 : 0 : assert(Valid());
# 184 [ # # ]: 0 : if (index_ == 0) {
# 185 : 0 : index_ = flist_->size(); // Marks as invalid
# 186 : 0 : } else {
# 187 : 0 : index_--;
# 188 : 0 : }
# 189 : 0 : }
# 190 : 118 : Slice key() const override {
# 191 : 118 : assert(Valid());
# 192 : 0 : return (*flist_)[index_]->largest.Encode();
# 193 : 118 : }
# 194 : 118 : Slice value() const override {
# 195 : 118 : assert(Valid());
# 196 : 0 : EncodeFixed64(value_buf_, (*flist_)[index_]->number);
# 197 : 118 : EncodeFixed64(value_buf_ + 8, (*flist_)[index_]->file_size);
# 198 : 118 : return Slice(value_buf_, sizeof(value_buf_));
# 199 : 118 : }
# 200 : 66 : 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 : : static Iterator* GetFileIterator(void* arg, const ReadOptions& options,
# 212 : 118 : const Slice& file_value) {
# 213 : 118 : TableCache* cache = reinterpret_cast<TableCache*>(arg);
# 214 [ - + ]: 118 : if (file_value.size() != 16) {
# 215 : 0 : return NewErrorIterator(
# 216 : 0 : Status::Corruption("FileReader invoked with unexpected value"));
# 217 : 118 : } else {
# 218 : 118 : return cache->NewIterator(options, DecodeFixed64(file_value.data()),
# 219 : 118 : DecodeFixed64(file_value.data() + 8));
# 220 : 118 : }
# 221 : 118 : }
# 222 : :
# 223 : : Iterator* Version::NewConcatenatingIterator(const ReadOptions& options,
# 224 : 172 : int level) const {
# 225 : 172 : return NewTwoLevelIterator(
# 226 : 172 : new LevelFileNumIterator(vset_->icmp_, &files_[level]), &GetFileIterator,
# 227 : 172 : vset_->table_cache_, options);
# 228 : 172 : }
# 229 : :
# 230 : : void Version::AddIterators(const ReadOptions& options,
# 231 : 3379 : std::vector<Iterator*>* iters) {
# 232 : : // Merge all level zero files together since they may overlap
# 233 [ + + ]: 5033 : for (size_t i = 0; i < files_[0].size(); i++) {
# 234 : 1654 : iters->push_back(vset_->table_cache_->NewIterator(
# 235 : 1654 : options, files_[0][i]->number, files_[0][i]->file_size));
# 236 : 1654 : }
# 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 [ + + ]: 23653 : for (int level = 1; level < config::kNumLevels; level++) {
# 242 [ + + ]: 20274 : if (!files_[level].empty()) {
# 243 : 172 : iters->push_back(NewConcatenatingIterator(options, level));
# 244 : 172 : }
# 245 : 20274 : }
# 246 : 3379 : }
# 247 : :
# 248 : : // Callback from TableCache::Get()
# 249 : : namespace {
# 250 : : enum SaverState {
# 251 : : kNotFound,
# 252 : : kFound,
# 253 : : kDeleted,
# 254 : : kCorrupt,
# 255 : : };
# 256 : : struct Saver {
# 257 : : SaverState state;
# 258 : : const Comparator* ucmp;
# 259 : : Slice user_key;
# 260 : : std::string* value;
# 261 : : };
# 262 : : } // namespace
# 263 : 101279 : static void SaveValue(void* arg, const Slice& ikey, const Slice& v) {
# 264 : 101279 : Saver* s = reinterpret_cast<Saver*>(arg);
# 265 : 101279 : ParsedInternalKey parsed_key;
# 266 [ - + ]: 101279 : if (!ParseInternalKey(ikey, &parsed_key)) {
# 267 : 0 : s->state = kCorrupt;
# 268 : 101279 : } else {
# 269 [ + + ]: 101279 : if (s->ucmp->Compare(parsed_key.user_key, s->user_key) == 0) {
# 270 [ + + ]: 99525 : s->state = (parsed_key.type == kTypeValue) ? kFound : kDeleted;
# 271 [ + + ]: 99525 : if (s->state == kFound) {
# 272 : 37674 : s->value->assign(v.data(), v.size());
# 273 : 37674 : }
# 274 : 99525 : }
# 275 : 101279 : }
# 276 : 101279 : }
# 277 : :
# 278 : 10931 : static bool NewestFirst(FileMetaData* a, FileMetaData* b) {
# 279 : 10931 : return a->number > b->number;
# 280 : 10931 : }
# 281 : :
# 282 : : void Version::ForEachOverlapping(Slice user_key, Slice internal_key, void* arg,
# 283 : 9723489 : bool (*func)(void*, int, FileMetaData*)) {
# 284 : 9723489 : const Comparator* ucmp = vset_->icmp_.user_comparator();
# 285 : :
# 286 : : // Search level-0 in order from newest to oldest.
# 287 : 9723489 : std::vector<FileMetaData*> tmp;
# 288 : 9723489 : tmp.reserve(files_[0].size());
# 289 [ + + ]: 9868202 : for (uint32_t i = 0; i < files_[0].size(); i++) {
# 290 : 144713 : FileMetaData* f = files_[0][i];
# 291 [ + + ][ + + ]: 144713 : if (ucmp->Compare(user_key, f->smallest.user_key()) >= 0 &&
# 292 [ + + ]: 144713 : ucmp->Compare(user_key, f->largest.user_key()) <= 0) {
# 293 : 141195 : tmp.push_back(f);
# 294 : 141195 : }
# 295 : 144713 : }
# 296 [ + + ]: 9723489 : if (!tmp.empty()) {
# 297 : 131588 : std::sort(tmp.begin(), tmp.end(), NewestFirst);
# 298 [ + + ]: 258209 : for (uint32_t i = 0; i < tmp.size(); i++) {
# 299 [ + + ]: 137726 : if (!(*func)(arg, 0, tmp[i])) {
# 300 : 11105 : return;
# 301 : 11105 : }
# 302 : 137726 : }
# 303 : 131588 : }
# 304 : :
# 305 : : // Search other levels.
# 306 [ + + ]: 67540654 : for (int level = 1; level < config::kNumLevels; level++) {
# 307 : 57916751 : size_t num_files = files_[level].size();
# 308 [ + + ]: 57916751 : if (num_files == 0) continue;
# 309 : :
# 310 : : // Binary search to find earliest index whose largest key >= internal_key.
# 311 : 3247502 : uint32_t index = FindFile(vset_->icmp_, files_[level], internal_key);
# 312 [ + + ]: 3247502 : if (index < num_files) {
# 313 : 3245904 : FileMetaData* f = files_[level][index];
# 314 [ + + ]: 3245904 : if (ucmp->Compare(user_key, f->smallest.user_key()) < 0) {
# 315 : : // All of "f" is past any data for user_key
# 316 : 3245624 : } else {
# 317 [ + + ]: 3245624 : if (!(*func)(arg, level, f)) {
# 318 : 88481 : return;
# 319 : 88481 : }
# 320 : 3245624 : }
# 321 : 3245904 : }
# 322 : 3247502 : }
# 323 : 9712384 : }
# 324 : :
# 325 : : Status Version::Get(const ReadOptions& options, const LookupKey& k,
# 326 : 9723156 : std::string* value, GetStats* stats) {
# 327 : 9723156 : stats->seek_file = nullptr;
# 328 : 9723156 : stats->seek_file_level = -1;
# 329 : :
# 330 : 9723156 : struct State {
# 331 : 9723156 : Saver saver;
# 332 : 9723156 : GetStats* stats;
# 333 : 9723156 : const ReadOptions* options;
# 334 : 9723156 : Slice ikey;
# 335 : 9723156 : FileMetaData* last_file_read;
# 336 : 9723156 : int last_file_read_level;
# 337 : :
# 338 : 9723156 : VersionSet* vset;
# 339 : 9723156 : Status s;
# 340 : 9723156 : bool found;
# 341 : :
# 342 : 9723156 : static bool Match(void* arg, int level, FileMetaData* f) {
# 343 : 3382960 : State* state = reinterpret_cast<State*>(arg);
# 344 : :
# 345 [ + + ]: 3382960 : if (state->stats->seek_file == nullptr &&
# 346 [ + + ]: 3382960 : state->last_file_read != nullptr) {
# 347 : : // We have had more than one seek for this read. Charge the 1st file.
# 348 : 5674 : state->stats->seek_file = state->last_file_read;
# 349 : 5674 : state->stats->seek_file_level = state->last_file_read_level;
# 350 : 5674 : }
# 351 : :
# 352 : 3382960 : state->last_file_read = f;
# 353 : 3382960 : state->last_file_read_level = level;
# 354 : :
# 355 : 3382960 : state->s = state->vset->table_cache_->Get(*state->options, f->number,
# 356 : 3382960 : f->file_size, state->ikey,
# 357 : 3382960 : &state->saver, SaveValue);
# 358 [ - + ]: 3382960 : if (!state->s.ok()) {
# 359 : 0 : state->found = true;
# 360 : 0 : return false;
# 361 : 0 : }
# 362 [ - + ]: 3382960 : switch (state->saver.state) {
# 363 [ + + ]: 3283435 : case kNotFound:
# 364 : 3283435 : return true; // Keep searching in other files
# 365 [ + + ]: 37674 : case kFound:
# 366 : 37674 : state->found = true;
# 367 : 37674 : return false;
# 368 [ + + ]: 61851 : case kDeleted:
# 369 : 61851 : 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 : 3382960 : }
# 376 : :
# 377 : : // Not reached. Added to avoid false compilation warnings of
# 378 : : // "control reaches end of non-void function".
# 379 : 0 : return false;
# 380 : 3382960 : }
# 381 : 9723156 : };
# 382 : :
# 383 : 9723156 : State state;
# 384 : 9723156 : state.found = false;
# 385 : 9723156 : state.stats = stats;
# 386 : 9723156 : state.last_file_read = nullptr;
# 387 : 9723156 : state.last_file_read_level = -1;
# 388 : :
# 389 : 9723156 : state.options = &options;
# 390 : 9723156 : state.ikey = k.internal_key();
# 391 : 9723156 : state.vset = vset_;
# 392 : :
# 393 : 9723156 : state.saver.state = kNotFound;
# 394 : 9723156 : state.saver.ucmp = vset_->icmp_.user_comparator();
# 395 : 9723156 : state.saver.user_key = k.user_key();
# 396 : 9723156 : state.saver.value = value;
# 397 : :
# 398 : 9723156 : ForEachOverlapping(state.saver.user_key, state.ikey, &state, &State::Match);
# 399 : :
# 400 [ + + ]: 9723156 : return state.found ? state.s : Status::NotFound(Slice());
# 401 : 9723156 : }
# 402 : :
# 403 : 9723217 : bool Version::UpdateStats(const GetStats& stats) {
# 404 : 9723217 : FileMetaData* f = stats.seek_file;
# 405 [ + + ]: 9723217 : if (f != nullptr) {
# 406 : 5735 : f->allowed_seeks--;
# 407 [ + + ][ + + ]: 5735 : if (f->allowed_seeks <= 0 && file_to_compact_ == nullptr) {
# 408 : 24 : file_to_compact_ = f;
# 409 : 24 : file_to_compact_level_ = stats.seek_file_level;
# 410 : 24 : return true;
# 411 : 24 : }
# 412 : 5735 : }
# 413 : 9723193 : return false;
# 414 : 9723217 : }
# 415 : :
# 416 : 333 : bool Version::RecordReadSample(Slice internal_key) {
# 417 : 333 : ParsedInternalKey ikey;
# 418 [ - + ]: 333 : if (!ParseInternalKey(internal_key, &ikey)) {
# 419 : 0 : return false;
# 420 : 0 : }
# 421 : :
# 422 : 333 : struct State {
# 423 : 333 : GetStats stats; // Holds first matching file
# 424 : 333 : int matches;
# 425 : :
# 426 : 390 : static bool Match(void* arg, int level, FileMetaData* f) {
# 427 : 390 : State* state = reinterpret_cast<State*>(arg);
# 428 : 390 : state->matches++;
# 429 [ + + ]: 390 : if (state->matches == 1) {
# 430 : : // Remember first match.
# 431 : 329 : state->stats.seek_file = f;
# 432 : 329 : state->stats.seek_file_level = level;
# 433 : 329 : }
# 434 : : // We can stop iterating once we have a second match.
# 435 : 390 : return state->matches < 2;
# 436 : 390 : }
# 437 : 333 : };
# 438 : :
# 439 : 333 : State state;
# 440 : 333 : state.matches = 0;
# 441 : 333 : 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 [ + + ]: 333 : if (state.matches >= 2) {
# 448 : : // 1MB cost is about 1 seek (see comment in Builder::Apply).
# 449 : 61 : return UpdateStats(state.stats);
# 450 : 61 : }
# 451 : 272 : return false;
# 452 : 333 : }
# 453 : :
# 454 : 10098633 : void Version::Ref() { ++refs_; }
# 455 : :
# 456 : 10098633 : void Version::Unref() {
# 457 : 10098633 : assert(this != &vset_->dummy_versions_);
# 458 : 0 : assert(refs_ >= 1);
# 459 : 0 : --refs_;
# 460 [ + + ]: 10098633 : if (refs_ == 0) {
# 461 : 6688 : delete this;
# 462 : 6688 : }
# 463 : 10098633 : }
# 464 : :
# 465 : : bool Version::OverlapInLevel(int level, const Slice* smallest_user_key,
# 466 : 9 : const Slice* largest_user_key) {
# 467 : 9 : return SomeFileOverlapsRange(vset_->icmp_, (level > 0), files_[level],
# 468 : 9 : smallest_user_key, largest_user_key);
# 469 : 9 : }
# 470 : :
# 471 : : int Version::PickLevelForMemTableOutput(const Slice& smallest_user_key,
# 472 : 3 : const Slice& largest_user_key) {
# 473 : 3 : int level = 0;
# 474 [ + - ]: 3 : 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 : 3 : InternalKey start(smallest_user_key, kMaxSequenceNumber, kValueTypeForSeek);
# 478 : 3 : InternalKey limit(largest_user_key, 0, static_cast<ValueType>(0));
# 479 : 3 : std::vector<FileMetaData*> overlaps;
# 480 [ + + ]: 9 : while (level < config::kMaxMemCompactLevel) {
# 481 [ - + ]: 6 : if (OverlapInLevel(level + 1, &smallest_user_key, &largest_user_key)) {
# 482 : 0 : break;
# 483 : 0 : }
# 484 [ + - ]: 6 : if (level + 2 < config::kNumLevels) {
# 485 : : // Check that file does not overlap too many grandparent bytes.
# 486 : 6 : GetOverlappingInputs(level + 2, &start, &limit, &overlaps);
# 487 : 6 : const int64_t sum = TotalFileSize(overlaps);
# 488 [ - + ]: 6 : if (sum > MaxGrandParentOverlapBytes(vset_->options_)) {
# 489 : 0 : break;
# 490 : 0 : }
# 491 : 6 : }
# 492 : 6 : level++;
# 493 : 6 : }
# 494 : 3 : }
# 495 : 3 : return level;
# 496 : 3 : }
# 497 : :
# 498 : : // Store in "*inputs" all files in "level" that overlap [begin,end]
# 499 : : void Version::GetOverlappingInputs(int level, const InternalKey* begin,
# 500 : : const InternalKey* end,
# 501 : 363 : std::vector<FileMetaData*>* inputs) {
# 502 : 363 : assert(level >= 0);
# 503 : 0 : assert(level < config::kNumLevels);
# 504 : 0 : inputs->clear();
# 505 : 363 : Slice user_begin, user_end;
# 506 [ + - ]: 363 : if (begin != nullptr) {
# 507 : 363 : user_begin = begin->user_key();
# 508 : 363 : }
# 509 [ + - ]: 363 : if (end != nullptr) {
# 510 : 363 : user_end = end->user_key();
# 511 : 363 : }
# 512 : 363 : const Comparator* user_cmp = vset_->icmp_.user_comparator();
# 513 [ + + ]: 935 : for (size_t i = 0; i < files_[level].size();) {
# 514 : 572 : FileMetaData* f = files_[level][i++];
# 515 : 572 : const Slice file_start = f->smallest.user_key();
# 516 : 572 : const Slice file_limit = f->largest.user_key();
# 517 [ + - ][ - + ]: 572 : if (begin != nullptr && user_cmp->Compare(file_limit, user_begin) < 0) {
# 518 : : // "f" is completely before specified range; skip it
# 519 [ + - ][ - + ]: 572 : } else if (end != nullptr && user_cmp->Compare(file_start, user_end) > 0) {
# 520 : : // "f" is completely after specified range; skip it
# 521 : 572 : } else {
# 522 : 572 : inputs->push_back(f);
# 523 [ + + ]: 572 : 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 [ + - ][ + + ]: 539 : if (begin != nullptr && user_cmp->Compare(file_start, user_begin) < 0) {
# 527 : 19 : user_begin = file_start;
# 528 : 19 : inputs->clear();
# 529 : 19 : i = 0;
# 530 [ + - ]: 520 : } else if (end != nullptr &&
# 531 [ + + ]: 520 : user_cmp->Compare(file_limit, user_end) > 0) {
# 532 : 3 : user_end = file_limit;
# 533 : 3 : inputs->clear();
# 534 : 3 : i = 0;
# 535 : 3 : }
# 536 : 539 : }
# 537 : 572 : }
# 538 : 572 : }
# 539 : 363 : }
# 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 : 0 : 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 : 0 : }
# 563 : 0 : }
# 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 : 1766 : bool operator()(FileMetaData* f1, FileMetaData* f2) const {
# 577 : 1766 : int r = internal_comparator->Compare(f1->smallest, f2->smallest);
# 578 [ + + ]: 1766 : if (r != 0) {
# 579 : 1687 : return (r < 0);
# 580 : 1687 : } else {
# 581 : : // Break ties by file number
# 582 : 79 : return (f1->number < f2->number);
# 583 : 79 : }
# 584 : 1766 : }
# 585 : : };
# 586 : :
# 587 : : typedef std::set<FileMetaData*, BySmallestKey> FileSet;
# 588 : : 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 : 4495 : Builder(VersionSet* vset, Version* base) : vset_(vset), base_(base) {
# 600 : 4495 : base_->Ref();
# 601 : 4495 : BySmallestKey cmp;
# 602 : 4495 : cmp.internal_comparator = &vset_->icmp_;
# 603 [ + + ]: 35960 : for (int level = 0; level < config::kNumLevels; level++) {
# 604 : 31465 : levels_[level].added_files = new FileSet(cmp);
# 605 : 31465 : }
# 606 : 4495 : }
# 607 : :
# 608 : 4495 : ~Builder() {
# 609 [ + + ]: 35960 : for (int level = 0; level < config::kNumLevels; level++) {
# 610 : 31465 : const FileSet* added = levels_[level].added_files;
# 611 : 31465 : std::vector<FileMetaData*> to_unref;
# 612 : 31465 : to_unref.reserve(added->size());
# 613 [ + + ]: 33711 : for (FileSet::const_iterator it = added->begin(); it != added->end();
# 614 : 31465 : ++it) {
# 615 : 2246 : to_unref.push_back(*it);
# 616 : 2246 : }
# 617 : 31465 : delete added;
# 618 [ + + ]: 33711 : for (uint32_t i = 0; i < to_unref.size(); i++) {
# 619 : 2246 : FileMetaData* f = to_unref[i];
# 620 : 2246 : f->refs--;
# 621 [ + + ]: 2246 : if (f->refs <= 0) {
# 622 : 294 : delete f;
# 623 : 294 : }
# 624 : 2246 : }
# 625 : 31465 : }
# 626 : 4495 : base_->Unref();
# 627 : 4495 : }
# 628 : :
# 629 : : // Apply all of the edits in *edit to the current state.
# 630 : 5539 : void Apply(VersionEdit* edit) {
# 631 : : // Update compaction pointers
# 632 [ + + ]: 5859 : for (size_t i = 0; i < edit->compact_pointers_.size(); i++) {
# 633 : 320 : const int level = edit->compact_pointers_[i].first;
# 634 : 320 : vset_->compact_pointer_[level] =
# 635 : 320 : edit->compact_pointers_[i].second.Encode().ToString();
# 636 : 320 : }
# 637 : :
# 638 : : // Delete files
# 639 [ + + ]: 5539 : for (const auto& deleted_file_set_kvp : edit->deleted_files_) {
# 640 : 715 : const int level = deleted_file_set_kvp.first;
# 641 : 715 : const uint64_t number = deleted_file_set_kvp.second;
# 642 : 715 : levels_[level].deleted_files.insert(number);
# 643 : 715 : }
# 644 : :
# 645 : : // Add new files
# 646 [ + + ]: 7785 : for (size_t i = 0; i < edit->new_files_.size(); i++) {
# 647 : 2246 : const int level = edit->new_files_[i].first;
# 648 : 2246 : FileMetaData* f = new FileMetaData(edit->new_files_[i].second);
# 649 : 2246 : 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 : 2246 : f->allowed_seeks = static_cast<int>((f->file_size / 16384U));
# 665 [ + - ]: 2246 : if (f->allowed_seeks < 100) f->allowed_seeks = 100;
# 666 : :
# 667 : 2246 : levels_[level].deleted_files.erase(f->number);
# 668 : 2246 : levels_[level].added_files->insert(f);
# 669 : 2246 : }
# 670 : 5539 : }
# 671 : :
# 672 : : // Save the current state in *v.
# 673 : 4495 : void SaveTo(Version* v) {
# 674 : 4495 : BySmallestKey cmp;
# 675 : 4495 : cmp.internal_comparator = &vset_->icmp_;
# 676 [ + + ]: 35960 : 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 : 31465 : const std::vector<FileMetaData*>& base_files = base_->files_[level];
# 680 : 31465 : std::vector<FileMetaData*>::const_iterator base_iter = base_files.begin();
# 681 : 31465 : std::vector<FileMetaData*>::const_iterator base_end = base_files.end();
# 682 : 31465 : const FileSet* added_files = levels_[level].added_files;
# 683 : 31465 : v->files_[level].reserve(base_files.size() + added_files->size());
# 684 [ + + ]: 31465 : for (const auto& added_file : *added_files) {
# 685 : : // Add all smaller files listed in base_
# 686 : 2246 : for (std::vector<FileMetaData*>::const_iterator bpos =
# 687 : 2246 : std::upper_bound(base_iter, base_end, added_file, cmp);
# 688 [ + + ]: 2599 : base_iter != bpos; ++base_iter) {
# 689 : 353 : MaybeAddFile(v, level, *base_iter);
# 690 : 353 : }
# 691 : :
# 692 : 2246 : MaybeAddFile(v, level, added_file);
# 693 : 2246 : }
# 694 : :
# 695 : : // Add remaining base files
# 696 [ + + ]: 32401 : for (; base_iter != base_end; ++base_iter) {
# 697 : 936 : MaybeAddFile(v, level, *base_iter);
# 698 : 936 : }
# 699 : :
# 700 : 31465 : #ifndef NDEBUG
# 701 : : // Make sure there is no overlap in levels > 0
# 702 [ + + ]: 31465 : if (level > 0) {
# 703 [ - + ]: 26970 : for (uint32_t i = 1; i < v->files_[level].size(); i++) {
# 704 : 0 : const InternalKey& prev_end = v->files_[level][i - 1]->largest;
# 705 : 0 : const InternalKey& this_begin = v->files_[level][i]->smallest;
# 706 [ # # ]: 0 : 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 : 0 : }
# 712 : 0 : }
# 713 : 26970 : }
# 714 : 31465 : #endif
# 715 : 31465 : }
# 716 : 4495 : }
# 717 : :
# 718 : 3535 : void MaybeAddFile(Version* v, int level, FileMetaData* f) {
# 719 [ + + ]: 3535 : if (levels_[level].deleted_files.count(f->number) > 0) {
# 720 : : // File is deleted: do nothing
# 721 : 2820 : } else {
# 722 : 2820 : std::vector<FileMetaData*>* files = &v->files_[level];
# 723 [ + + ][ - + ]: 2820 : if (level > 0 && !files->empty()) {
# 724 : : // Must not overlap
# 725 : 0 : assert(vset_->icmp_.Compare((*files)[files->size() - 1]->largest,
# 726 : 0 : f->smallest) < 0);
# 727 : 0 : }
# 728 : 0 : f->refs++;
# 729 : 2820 : files->push_back(f);
# 730 : 2820 : }
# 731 : 3535 : }
# 732 : : };
# 733 : :
# 734 : : VersionSet::VersionSet(const std::string& dbname, const Options* options,
# 735 : : TableCache* table_cache,
# 736 : : const InternalKeyComparator* cmp)
# 737 : : : env_(options->env),
# 738 : : dbname_(dbname),
# 739 : : options_(options),
# 740 : : table_cache_(table_cache),
# 741 : : icmp_(*cmp),
# 742 : : next_file_number_(2),
# 743 : : manifest_file_number_(0), // Filled by Recover()
# 744 : : last_sequence_(0),
# 745 : : log_number_(0),
# 746 : : prev_log_number_(0),
# 747 : : descriptor_file_(nullptr),
# 748 : : descriptor_log_(nullptr),
# 749 : : dummy_versions_(this),
# 750 : 2193 : current_(nullptr) {
# 751 : 2193 : AppendVersion(new Version(this));
# 752 : 2193 : }
# 753 : :
# 754 : 2193 : VersionSet::~VersionSet() {
# 755 : 2193 : current_->Unref();
# 756 : 2193 : assert(dummy_versions_.next_ == &dummy_versions_); // List must be empty
# 757 : 0 : delete descriptor_log_;
# 758 : 2193 : delete descriptor_file_;
# 759 : 2193 : }
# 760 : :
# 761 : 6688 : void VersionSet::AppendVersion(Version* v) {
# 762 : : // Make "v" current
# 763 : 6688 : assert(v->refs_ == 0);
# 764 : 0 : assert(v != current_);
# 765 [ + + ]: 6688 : if (current_ != nullptr) {
# 766 : 4495 : current_->Unref();
# 767 : 4495 : }
# 768 : 6688 : current_ = v;
# 769 : 6688 : v->Ref();
# 770 : :
# 771 : : // Append to linked list
# 772 : 6688 : v->prev_ = dummy_versions_.prev_;
# 773 : 6688 : v->next_ = &dummy_versions_;
# 774 : 6688 : v->prev_->next_ = v;
# 775 : 6688 : v->next_->prev_ = v;
# 776 : 6688 : }
# 777 : :
# 778 : 2302 : Status VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu) {
# 779 [ + + ]: 2302 : if (edit->has_log_number_) {
# 780 : 2194 : assert(edit->log_number_ >= log_number_);
# 781 : 0 : assert(edit->log_number_ < next_file_number_);
# 782 : 2194 : } else {
# 783 : 108 : edit->SetLogNumber(log_number_);
# 784 : 108 : }
# 785 : :
# 786 [ + + ]: 2302 : if (!edit->has_prev_log_number_) {
# 787 : 108 : edit->SetPrevLogNumber(prev_log_number_);
# 788 : 108 : }
# 789 : :
# 790 : 2302 : edit->SetNextFile(next_file_number_);
# 791 : 2302 : edit->SetLastSequence(last_sequence_);
# 792 : :
# 793 : 2302 : Version* v = new Version(this);
# 794 : 2302 : {
# 795 : 2302 : Builder builder(this, current_);
# 796 : 2302 : builder.Apply(edit);
# 797 : 2302 : builder.SaveTo(v);
# 798 : 2302 : }
# 799 : 2302 : 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 : 2302 : std::string new_manifest_file;
# 804 : 2302 : Status s;
# 805 [ + + ]: 2302 : 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 : 2191 : assert(descriptor_file_ == nullptr);
# 809 : 0 : new_manifest_file = DescriptorFileName(dbname_, manifest_file_number_);
# 810 : 2191 : edit->SetNextFile(next_file_number_);
# 811 : 2191 : s = env_->NewWritableFile(new_manifest_file, &descriptor_file_);
# 812 [ + - ]: 2191 : if (s.ok()) {
# 813 : 2191 : descriptor_log_ = new log::Writer(descriptor_file_);
# 814 : 2191 : s = WriteSnapshot(descriptor_log_);
# 815 : 2191 : }
# 816 : 2191 : }
# 817 : :
# 818 : : // Unlock during expensive MANIFEST log write
# 819 : 0 : {
# 820 : 2302 : mu->Unlock();
# 821 : :
# 822 : : // Write new record to MANIFEST log
# 823 [ + - ]: 2302 : if (s.ok()) {
# 824 : 2302 : std::string record;
# 825 : 2302 : edit->EncodeTo(&record);
# 826 : 2302 : s = descriptor_log_->AddRecord(record);
# 827 [ + - ]: 2302 : if (s.ok()) {
# 828 : 2302 : s = descriptor_file_->Sync();
# 829 : 2302 : }
# 830 [ - + ]: 2302 : if (!s.ok()) {
# 831 : 0 : Log(options_->info_log, "MANIFEST write: %s\n", s.ToString().c_str());
# 832 : 0 : }
# 833 : 2302 : }
# 834 : :
# 835 : : // If we just created a new descriptor file, install it by writing a
# 836 : : // new CURRENT file that points to it.
# 837 [ + + ][ + + ]: 2302 : if (s.ok() && !new_manifest_file.empty()) {
# 838 : 2191 : s = SetCurrentFile(env_, dbname_, manifest_file_number_);
# 839 : 2191 : }
# 840 : :
# 841 : 2302 : mu->Lock();
# 842 : 2302 : }
# 843 : :
# 844 : : // Install the new version
# 845 [ + - ]: 2302 : if (s.ok()) {
# 846 : 2302 : AppendVersion(v);
# 847 : 2302 : log_number_ = edit->log_number_;
# 848 : 2302 : prev_log_number_ = edit->prev_log_number_;
# 849 : 2302 : } 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 : 0 : }
# 858 : 0 : }
# 859 : :
# 860 : 2302 : return s;
# 861 : 2302 : }
# 862 : :
# 863 : 2193 : Status VersionSet::Recover(bool* save_manifest) {
# 864 : 2193 : struct LogReporter : public log::Reader::Reporter {
# 865 : 2193 : Status* status;
# 866 : 2193 : void Corruption(size_t bytes, const Status& s) override {
# 867 [ # # ]: 0 : if (this->status->ok()) *this->status = s;
# 868 : 0 : }
# 869 : 2193 : };
# 870 : :
# 871 : : // Read "CURRENT" file, which contains a pointer to the current manifest file
# 872 : 2193 : std::string current;
# 873 : 2193 : Status s = ReadFileToString(env_, CurrentFileName(dbname_), ¤t);
# 874 [ - + ]: 2193 : if (!s.ok()) {
# 875 : 0 : return s;
# 876 : 0 : }
# 877 [ - + ][ - + ]: 2193 : if (current.empty() || current[current.size() - 1] != '\n') {
# 878 : 0 : return Status::Corruption("CURRENT file does not end with newline");
# 879 : 0 : }
# 880 : 2193 : current.resize(current.size() - 1);
# 881 : :
# 882 : 2193 : std::string dscname = dbname_ + "/" + current;
# 883 : 2193 : SequentialFile* file;
# 884 : 2193 : s = env_->NewSequentialFile(dscname, &file);
# 885 [ - + ]: 2193 : if (!s.ok()) {
# 886 [ # # ]: 0 : if (s.IsNotFound()) {
# 887 : 0 : return Status::Corruption("CURRENT points to a non-existent file",
# 888 : 0 : s.ToString());
# 889 : 0 : }
# 890 : 0 : return s;
# 891 : 0 : }
# 892 : :
# 893 : 2193 : bool have_log_number = false;
# 894 : 2193 : bool have_prev_log_number = false;
# 895 : 2193 : bool have_next_file = false;
# 896 : 2193 : bool have_last_sequence = false;
# 897 : 2193 : uint64_t next_file = 0;
# 898 : 2193 : uint64_t last_sequence = 0;
# 899 : 2193 : uint64_t log_number = 0;
# 900 : 2193 : uint64_t prev_log_number = 0;
# 901 : 2193 : Builder builder(this, current_);
# 902 : :
# 903 : 2193 : {
# 904 : 2193 : LogReporter reporter;
# 905 : 2193 : reporter.status = &s;
# 906 : 2193 : log::Reader reader(file, &reporter, true /*checksum*/,
# 907 : 2193 : 0 /*initial_offset*/);
# 908 : 2193 : Slice record;
# 909 : 2193 : std::string scratch;
# 910 [ + + ][ + - ]: 5430 : while (reader.ReadRecord(&record, &scratch) && s.ok()) {
# 911 : 3237 : VersionEdit edit;
# 912 : 3237 : s = edit.DecodeFrom(record);
# 913 [ + - ]: 3237 : if (s.ok()) {
# 914 [ + + ]: 3237 : if (edit.has_comparator_ &&
# 915 [ - + ]: 3237 : 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 : 0 : }
# 920 : 3237 : }
# 921 : :
# 922 [ + - ]: 3237 : if (s.ok()) {
# 923 : 3237 : builder.Apply(&edit);
# 924 : 3237 : }
# 925 : :
# 926 [ + + ]: 3237 : if (edit.has_log_number_) {
# 927 : 2264 : log_number = edit.log_number_;
# 928 : 2264 : have_log_number = true;
# 929 : 2264 : }
# 930 : :
# 931 [ + + ]: 3237 : if (edit.has_prev_log_number_) {
# 932 : 1044 : prev_log_number = edit.prev_log_number_;
# 933 : 1044 : have_prev_log_number = true;
# 934 : 1044 : }
# 935 : :
# 936 [ + + ]: 3237 : if (edit.has_next_file_number_) {
# 937 : 2264 : next_file = edit.next_file_number_;
# 938 : 2264 : have_next_file = true;
# 939 : 2264 : }
# 940 : :
# 941 [ + + ]: 3237 : if (edit.has_last_sequence_) {
# 942 : 2264 : last_sequence = edit.last_sequence_;
# 943 : 2264 : have_last_sequence = true;
# 944 : 2264 : }
# 945 : 3237 : }
# 946 : 2193 : }
# 947 : 2193 : delete file;
# 948 : 2193 : file = nullptr;
# 949 : :
# 950 [ + - ]: 2193 : if (s.ok()) {
# 951 [ - + ]: 2193 : if (!have_next_file) {
# 952 : 0 : s = Status::Corruption("no meta-nextfile entry in descriptor");
# 953 [ - + ]: 2193 : } else if (!have_log_number) {
# 954 : 0 : s = Status::Corruption("no meta-lognumber entry in descriptor");
# 955 [ - + ]: 2193 : } else if (!have_last_sequence) {
# 956 : 0 : s = Status::Corruption("no last-sequence-number entry in descriptor");
# 957 : 0 : }
# 958 : :
# 959 [ + + ]: 2193 : if (!have_prev_log_number) {
# 960 : 1220 : prev_log_number = 0;
# 961 : 1220 : }
# 962 : :
# 963 : 2193 : MarkFileNumberUsed(prev_log_number);
# 964 : 2193 : MarkFileNumberUsed(log_number);
# 965 : 2193 : }
# 966 : :
# 967 [ + - ]: 2193 : if (s.ok()) {
# 968 : 2193 : Version* v = new Version(this);
# 969 : 2193 : builder.SaveTo(v);
# 970 : : // Install recovered version
# 971 : 2193 : Finalize(v);
# 972 : 2193 : AppendVersion(v);
# 973 : 2193 : manifest_file_number_ = next_file;
# 974 : 2193 : next_file_number_ = next_file + 1;
# 975 : 2193 : last_sequence_ = last_sequence;
# 976 : 2193 : log_number_ = log_number;
# 977 : 2193 : prev_log_number_ = prev_log_number;
# 978 : :
# 979 : : // See if we can reuse the existing MANIFEST file.
# 980 [ - + ]: 2193 : if (ReuseManifest(dscname, current)) {
# 981 : : // No need to save new manifest
# 982 : 2193 : } else {
# 983 : 2193 : *save_manifest = true;
# 984 : 2193 : }
# 985 : 2193 : }
# 986 : :
# 987 : 2193 : return s;
# 988 : 2193 : }
# 989 : :
# 990 : : bool VersionSet::ReuseManifest(const std::string& dscname,
# 991 : 2193 : const std::string& dscbase) {
# 992 [ + - ]: 2193 : if (!options_->reuse_logs) {
# 993 : 2193 : return false;
# 994 : 2193 : }
# 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 : 0 : return false;
# 1004 : 0 : }
# 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 : 0 : return false;
# 1013 : 0 : }
# 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 : 5357 : void VersionSet::MarkFileNumberUsed(uint64_t number) {
# 1022 [ + + ]: 5357 : if (next_file_number_ <= number) {
# 1023 : 973 : next_file_number_ = number + 1;
# 1024 : 973 : }
# 1025 : 5357 : }
# 1026 : :
# 1027 : 4495 : void VersionSet::Finalize(Version* v) {
# 1028 : : // Precomputed best level for next compaction
# 1029 : 4495 : int best_level = -1;
# 1030 : 4495 : double best_score = -1;
# 1031 : :
# 1032 [ + + ]: 31465 : for (int level = 0; level < config::kNumLevels - 1; level++) {
# 1033 : 26970 : double score;
# 1034 [ + + ]: 26970 : 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 : 4495 : score = v->files_[level].size() /
# 1047 : 4495 : static_cast<double>(config::kL0_CompactionTrigger);
# 1048 : 22475 : } else {
# 1049 : : // Compute the ratio of current size to size limit.
# 1050 : 22475 : const uint64_t level_bytes = TotalFileSize(v->files_[level]);
# 1051 : 22475 : score =
# 1052 : 22475 : static_cast<double>(level_bytes) / MaxBytesForLevel(options_, level);
# 1053 : 22475 : }
# 1054 : :
# 1055 [ + + ]: 26970 : if (score > best_score) {
# 1056 : 4679 : best_level = level;
# 1057 : 4679 : best_score = score;
# 1058 : 4679 : }
# 1059 : 26970 : }
# 1060 : :
# 1061 : 4495 : v->compaction_level_ = best_level;
# 1062 : 4495 : v->compaction_score_ = best_score;
# 1063 : 4495 : }
# 1064 : :
# 1065 : 2191 : Status VersionSet::WriteSnapshot(log::Writer* log) {
# 1066 : : // TODO: Break up into multiple records to reduce memory usage on recovery?
# 1067 : :
# 1068 : : // Save metadata
# 1069 : 2191 : VersionEdit edit;
# 1070 : 2191 : edit.SetComparatorName(icmp_.user_comparator()->Name());
# 1071 : :
# 1072 : : // Save compaction pointers
# 1073 [ + + ]: 17528 : for (int level = 0; level < config::kNumLevels; level++) {
# 1074 [ + + ]: 15337 : if (!compact_pointer_[level].empty()) {
# 1075 : 181 : InternalKey key;
# 1076 : 181 : key.DecodeFrom(compact_pointer_[level]);
# 1077 : 181 : edit.SetCompactPointer(level, key);
# 1078 : 181 : }
# 1079 : 15337 : }
# 1080 : :
# 1081 : : // Save files
# 1082 [ + + ]: 17528 : for (int level = 0; level < config::kNumLevels; level++) {
# 1083 : 15337 : const std::vector<FileMetaData*>& files = current_->files_[level];
# 1084 [ + + ]: 16205 : for (size_t i = 0; i < files.size(); i++) {
# 1085 : 868 : const FileMetaData* f = files[i];
# 1086 : 868 : edit.AddFile(level, f->number, f->file_size, f->smallest, f->largest);
# 1087 : 868 : }
# 1088 : 15337 : }
# 1089 : :
# 1090 : 2191 : std::string record;
# 1091 : 2191 : edit.EncodeTo(&record);
# 1092 : 2191 : return log->AddRecord(record);
# 1093 : 2191 : }
# 1094 : :
# 1095 : 13792 : int VersionSet::NumLevelFiles(int level) const {
# 1096 : 13792 : assert(level >= 0);
# 1097 : 0 : assert(level < config::kNumLevels);
# 1098 : 0 : return current_->files_[level].size();
# 1099 : 13792 : }
# 1100 : :
# 1101 : 108 : const char* VersionSet::LevelSummary(LevelSummaryStorage* scratch) const {
# 1102 : : // Update code if kNumLevels changes
# 1103 : 108 : static_assert(config::kNumLevels == 7, "");
# 1104 : 108 : snprintf(scratch->buffer, sizeof(scratch->buffer),
# 1105 : 108 : "files[ %d %d %d %d %d %d %d ]", int(current_->files_[0].size()),
# 1106 : 108 : int(current_->files_[1].size()), int(current_->files_[2].size()),
# 1107 : 108 : int(current_->files_[3].size()), int(current_->files_[4].size()),
# 1108 : 108 : int(current_->files_[5].size()), int(current_->files_[6].size()));
# 1109 : 108 : return scratch->buffer;
# 1110 : 108 : }
# 1111 : :
# 1112 : 54 : uint64_t VersionSet::ApproximateOffsetOf(Version* v, const InternalKey& ikey) {
# 1113 : 54 : uint64_t result = 0;
# 1114 [ + + ]: 432 : for (int level = 0; level < config::kNumLevels; level++) {
# 1115 : 378 : const std::vector<FileMetaData*>& files = v->files_[level];
# 1116 [ + + ]: 400 : for (size_t i = 0; i < files.size(); i++) {
# 1117 [ + + ]: 22 : if (icmp_.Compare(files[i]->largest, ikey) <= 0) {
# 1118 : : // Entire file is before "ikey", so just add the file size
# 1119 : 6 : result += files[i]->file_size;
# 1120 [ - + ]: 16 : } 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 : 0 : break;
# 1127 : 0 : }
# 1128 : 16 : } else {
# 1129 : : // "ikey" falls in the range for this table. Add the
# 1130 : : // approximate offset of "ikey" within the table.
# 1131 : 16 : Table* tableptr;
# 1132 : 16 : Iterator* iter = table_cache_->NewIterator(
# 1133 : 16 : ReadOptions(), files[i]->number, files[i]->file_size, &tableptr);
# 1134 [ + - ]: 16 : if (tableptr != nullptr) {
# 1135 : 16 : result += tableptr->ApproximateOffsetOf(ikey.Encode());
# 1136 : 16 : }
# 1137 : 16 : delete iter;
# 1138 : 16 : }
# 1139 : 22 : }
# 1140 : 378 : }
# 1141 : 54 : return result;
# 1142 : 54 : }
# 1143 : :
# 1144 : 4495 : void VersionSet::AddLiveFiles(std::set<uint64_t>* live) {
# 1145 [ + + ]: 8997 : for (Version* v = dummy_versions_.next_; v != &dummy_versions_;
# 1146 : 4502 : v = v->next_) {
# 1147 [ + + ]: 36016 : for (int level = 0; level < config::kNumLevels; level++) {
# 1148 : 31514 : const std::vector<FileMetaData*>& files = v->files_[level];
# 1149 [ + + ]: 34361 : for (size_t i = 0; i < files.size(); i++) {
# 1150 : 2847 : live->insert(files[i]->number);
# 1151 : 2847 : }
# 1152 : 31514 : }
# 1153 : 4502 : }
# 1154 : 4495 : }
# 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 : 0 : }
# 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 : 0 : &overlaps);
# 1170 : 0 : const int64_t sum = TotalFileSize(overlaps);
# 1171 [ # # ]: 0 : if (sum > result) {
# 1172 : 0 : result = sum;
# 1173 : 0 : }
# 1174 : 0 : }
# 1175 : 0 : }
# 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 : : void VersionSet::GetRange(const std::vector<FileMetaData*>& inputs,
# 1183 : 324 : InternalKey* smallest, InternalKey* largest) {
# 1184 : 324 : assert(!inputs.empty());
# 1185 : 0 : smallest->Clear();
# 1186 : 324 : largest->Clear();
# 1187 [ + + ]: 1241 : for (size_t i = 0; i < inputs.size(); i++) {
# 1188 : 917 : FileMetaData* f = inputs[i];
# 1189 [ + + ]: 917 : if (i == 0) {
# 1190 : 324 : *smallest = f->smallest;
# 1191 : 324 : *largest = f->largest;
# 1192 : 593 : } else {
# 1193 [ + + ]: 593 : if (icmp_.Compare(f->smallest, *smallest) < 0) {
# 1194 : 29 : *smallest = f->smallest;
# 1195 : 29 : }
# 1196 [ + + ]: 593 : if (icmp_.Compare(f->largest, *largest) > 0) {
# 1197 : 191 : *largest = f->largest;
# 1198 : 191 : }
# 1199 : 593 : }
# 1200 : 917 : }
# 1201 : 324 : }
# 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 : : void VersionSet::GetRange2(const std::vector<FileMetaData*>& inputs1,
# 1207 : : const std::vector<FileMetaData*>& inputs2,
# 1208 : 108 : InternalKey* smallest, InternalKey* largest) {
# 1209 : 108 : std::vector<FileMetaData*> all = inputs1;
# 1210 : 108 : all.insert(all.end(), inputs2.begin(), inputs2.end());
# 1211 : 108 : GetRange(all, smallest, largest);
# 1212 : 108 : }
# 1213 : :
# 1214 : 108 : Iterator* VersionSet::MakeInputIterator(Compaction* c) {
# 1215 : 108 : ReadOptions options;
# 1216 : 108 : options.verify_checksums = options_->paranoid_checks;
# 1217 : 108 : 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 [ + - ]: 108 : const int space = (c->level() == 0 ? c->inputs_[0].size() + 1 : 2);
# 1223 : 108 : Iterator** list = new Iterator*[space];
# 1224 : 108 : int num = 0;
# 1225 [ + + ]: 324 : for (int which = 0; which < 2; which++) {
# 1226 [ + + ]: 216 : if (!c->inputs_[which].empty()) {
# 1227 [ + + ]: 141 : if (c->level() + which == 0) {
# 1228 : 108 : const std::vector<FileMetaData*>& files = c->inputs_[which];
# 1229 [ + + ]: 496 : for (size_t i = 0; i < files.size(); i++) {
# 1230 : 388 : list[num++] = table_cache_->NewIterator(options, files[i]->number,
# 1231 : 388 : files[i]->file_size);
# 1232 : 388 : }
# 1233 : 108 : } else {
# 1234 : : // Create concatenating iterator for the files from this level
# 1235 : 33 : list[num++] = NewTwoLevelIterator(
# 1236 : 33 : new Version::LevelFileNumIterator(icmp_, &c->inputs_[which]),
# 1237 : 33 : &GetFileIterator, table_cache_, options);
# 1238 : 33 : }
# 1239 : 141 : }
# 1240 : 216 : }
# 1241 : 108 : assert(num <= space);
# 1242 : 0 : Iterator* result = NewMergingIterator(&icmp_, list, num);
# 1243 : 108 : delete[] list;
# 1244 : 108 : return result;
# 1245 : 108 : }
# 1246 : :
# 1247 : 108 : Compaction* VersionSet::PickCompaction() {
# 1248 : 108 : Compaction* c;
# 1249 : 108 : int level;
# 1250 : :
# 1251 : : // We prefer compactions triggered by too much data in a level over
# 1252 : : // the compactions triggered by seeks.
# 1253 : 108 : const bool size_compaction = (current_->compaction_score_ >= 1);
# 1254 : 108 : const bool seek_compaction = (current_->file_to_compact_ != nullptr);
# 1255 [ + + ]: 108 : if (size_compaction) {
# 1256 : 84 : level = current_->compaction_level_;
# 1257 : 84 : assert(level >= 0);
# 1258 : 0 : assert(level + 1 < config::kNumLevels);
# 1259 : 0 : c = new Compaction(options_, level);
# 1260 : :
# 1261 : : // Pick the first file that comes after compact_pointer_[level]
# 1262 [ + + ]: 192 : for (size_t i = 0; i < current_->files_[level].size(); i++) {
# 1263 : 165 : FileMetaData* f = current_->files_[level][i];
# 1264 [ + + ][ + + ]: 165 : if (compact_pointer_[level].empty() ||
# 1265 [ + + ]: 165 : icmp_.Compare(f->largest.Encode(), compact_pointer_[level]) > 0) {
# 1266 : 57 : c->inputs_[0].push_back(f);
# 1267 : 57 : break;
# 1268 : 57 : }
# 1269 : 165 : }
# 1270 [ + + ]: 84 : if (c->inputs_[0].empty()) {
# 1271 : : // Wrap-around to the beginning of the key space
# 1272 : 27 : c->inputs_[0].push_back(current_->files_[level][0]);
# 1273 : 27 : }
# 1274 [ + - ]: 84 : } else if (seek_compaction) {
# 1275 : 24 : level = current_->file_to_compact_level_;
# 1276 : 24 : c = new Compaction(options_, level);
# 1277 : 24 : c->inputs_[0].push_back(current_->file_to_compact_);
# 1278 : 24 : } else {
# 1279 : 0 : return nullptr;
# 1280 : 0 : }
# 1281 : :
# 1282 : 108 : c->input_version_ = current_;
# 1283 : 108 : c->input_version_->Ref();
# 1284 : :
# 1285 : : // Files in level 0 may overlap each other, so pick up all overlapping ones
# 1286 [ + - ]: 108 : if (level == 0) {
# 1287 : 108 : InternalKey smallest, largest;
# 1288 : 108 : 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 : 108 : current_->GetOverlappingInputs(0, &smallest, &largest, &c->inputs_[0]);
# 1293 : 108 : assert(!c->inputs_[0].empty());
# 1294 : 108 : }
# 1295 : :
# 1296 : 0 : SetupOtherInputs(c);
# 1297 : :
# 1298 : 108 : return c;
# 1299 : 108 : }
# 1300 : :
# 1301 : : // Finds the largest key in a vector of files. Returns true if files it not
# 1302 : : // empty.
# 1303 : : bool FindLargestKey(const InternalKeyComparator& icmp,
# 1304 : : const std::vector<FileMetaData*>& files,
# 1305 : 141 : InternalKey* largest_key) {
# 1306 [ - + ]: 141 : if (files.empty()) {
# 1307 : 0 : return false;
# 1308 : 0 : }
# 1309 : 141 : *largest_key = files[0]->largest;
# 1310 [ + + ]: 510 : for (size_t i = 1; i < files.size(); ++i) {
# 1311 : 369 : FileMetaData* f = files[i];
# 1312 [ + + ]: 369 : if (icmp.Compare(f->largest, *largest_key) > 0) {
# 1313 : 168 : *largest_key = f->largest;
# 1314 : 168 : }
# 1315 : 369 : }
# 1316 : 141 : return true;
# 1317 : 141 : }
# 1318 : :
# 1319 : : // Finds minimum file b2=(l2, u2) in level file for which l2 > u1 and
# 1320 : : // user_key(l2) = user_key(u1)
# 1321 : : FileMetaData* FindSmallestBoundaryFile(
# 1322 : : const InternalKeyComparator& icmp,
# 1323 : : const std::vector<FileMetaData*>& level_files,
# 1324 : 141 : const InternalKey& largest_key) {
# 1325 : 141 : const Comparator* user_cmp = icmp.user_comparator();
# 1326 : 141 : FileMetaData* smallest_boundary_file = nullptr;
# 1327 [ + + ]: 651 : for (size_t i = 0; i < level_files.size(); ++i) {
# 1328 : 510 : FileMetaData* f = level_files[i];
# 1329 [ - + ][ - + ]: 510 : if (icmp.Compare(f->smallest, largest_key) > 0 &&
# 1330 [ # # ]: 510 : user_cmp->Compare(f->smallest.user_key(), largest_key.user_key()) ==
# 1331 : 0 : 0) {
# 1332 [ # # ]: 0 : if (smallest_boundary_file == nullptr ||
# 1333 [ # # ]: 0 : icmp.Compare(f->smallest, smallest_boundary_file->smallest) < 0) {
# 1334 : 0 : smallest_boundary_file = f;
# 1335 : 0 : }
# 1336 : 0 : }
# 1337 : 510 : }
# 1338 : 141 : return smallest_boundary_file;
# 1339 : 141 : }
# 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 : : void AddBoundaryInputs(const InternalKeyComparator& icmp,
# 1356 : : const std::vector<FileMetaData*>& level_files,
# 1357 : 141 : std::vector<FileMetaData*>* compaction_files) {
# 1358 : 141 : InternalKey largest_key;
# 1359 : :
# 1360 : : // Quick return if compaction_files is empty.
# 1361 [ - + ]: 141 : if (!FindLargestKey(icmp, *compaction_files, &largest_key)) {
# 1362 : 0 : return;
# 1363 : 0 : }
# 1364 : :
# 1365 : 141 : bool continue_searching = true;
# 1366 [ + + ]: 282 : while (continue_searching) {
# 1367 : 141 : FileMetaData* smallest_boundary_file =
# 1368 : 141 : FindSmallestBoundaryFile(icmp, level_files, largest_key);
# 1369 : :
# 1370 : : // If a boundary file was found advance largest_key, otherwise we're done.
# 1371 [ - + ]: 141 : if (smallest_boundary_file != NULL) {
# 1372 : 0 : compaction_files->push_back(smallest_boundary_file);
# 1373 : 0 : largest_key = smallest_boundary_file->largest;
# 1374 : 141 : } else {
# 1375 : 141 : continue_searching = false;
# 1376 : 141 : }
# 1377 : 141 : }
# 1378 : 141 : }
# 1379 : :
# 1380 : 108 : void VersionSet::SetupOtherInputs(Compaction* c) {
# 1381 : 108 : const int level = c->level();
# 1382 : 108 : InternalKey smallest, largest;
# 1383 : :
# 1384 : 108 : AddBoundaryInputs(icmp_, current_->files_[level], &c->inputs_[0]);
# 1385 : 108 : GetRange(c->inputs_[0], &smallest, &largest);
# 1386 : :
# 1387 : 108 : current_->GetOverlappingInputs(level + 1, &smallest, &largest,
# 1388 : 108 : &c->inputs_[1]);
# 1389 : :
# 1390 : : // Get entire range covered by compaction
# 1391 : 108 : InternalKey all_start, all_limit;
# 1392 : 108 : 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 [ + + ]: 108 : if (!c->inputs_[1].empty()) {
# 1397 : 33 : std::vector<FileMetaData*> expanded0;
# 1398 : 33 : current_->GetOverlappingInputs(level, &all_start, &all_limit, &expanded0);
# 1399 : 33 : AddBoundaryInputs(icmp_, current_->files_[level], &expanded0);
# 1400 : 33 : const int64_t inputs0_size = TotalFileSize(c->inputs_[0]);
# 1401 : 33 : const int64_t inputs1_size = TotalFileSize(c->inputs_[1]);
# 1402 : 33 : const int64_t expanded0_size = TotalFileSize(expanded0);
# 1403 [ - + ]: 33 : if (expanded0.size() > c->inputs_[0].size() &&
# 1404 [ # # ]: 33 : 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 : 0 : &expanded1);
# 1411 [ # # ]: 0 : if (expanded1.size() == c->inputs_[1].size()) {
# 1412 : 0 : Log(options_->info_log,
# 1413 : 0 : "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 : 0 : }
# 1423 : 0 : }
# 1424 : 33 : }
# 1425 : :
# 1426 : : // Compute the set of grandparent files that overlap this compaction
# 1427 : : // (parent == level+1; grandparent == level+2)
# 1428 [ + - ]: 108 : if (level + 2 < config::kNumLevels) {
# 1429 : 108 : current_->GetOverlappingInputs(level + 2, &all_start, &all_limit,
# 1430 : 108 : &c->grandparents_);
# 1431 : 108 : }
# 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 : 108 : compact_pointer_[level] = largest.Encode().ToString();
# 1438 : 108 : c->edit_.SetCompactPointer(level, largest);
# 1439 : 108 : }
# 1440 : :
# 1441 : : Compaction* VersionSet::CompactRange(int level, const InternalKey* begin,
# 1442 : 0 : const InternalKey* end) {
# 1443 : 0 : std::vector<FileMetaData*> inputs;
# 1444 : 0 : current_->GetOverlappingInputs(level, begin, end, &inputs);
# 1445 [ # # ]: 0 : if (inputs.empty()) {
# 1446 : 0 : return nullptr;
# 1447 : 0 : }
# 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 : 0 : break;
# 1462 : 0 : }
# 1463 : 0 : }
# 1464 : 0 : }
# 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 : 0 : return c;
# 1472 : 0 : }
# 1473 : :
# 1474 : : Compaction::Compaction(const Options* options, int level)
# 1475 : : : level_(level),
# 1476 : : max_output_file_size_(MaxFileSizeForLevel(options, level)),
# 1477 : : input_version_(nullptr),
# 1478 : : grandparent_index_(0),
# 1479 : : seen_key_(false),
# 1480 : 108 : overlapped_bytes_(0) {
# 1481 [ + + ]: 864 : for (int i = 0; i < config::kNumLevels; i++) {
# 1482 : 756 : level_ptrs_[i] = 0;
# 1483 : 756 : }
# 1484 : 108 : }
# 1485 : :
# 1486 : 108 : Compaction::~Compaction() {
# 1487 [ - + ]: 108 : if (input_version_ != nullptr) {
# 1488 : 0 : input_version_->Unref();
# 1489 : 0 : }
# 1490 : 108 : }
# 1491 : :
# 1492 : 108 : bool Compaction::IsTrivialMove() const {
# 1493 : 108 : 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 [ + + ][ - + ]: 108 : return (num_input_files(0) == 1 && num_input_files(1) == 0 &&
# 1498 [ # # ]: 108 : TotalFileSize(grandparents_) <=
# 1499 : 0 : MaxGrandParentOverlapBytes(vset->options_));
# 1500 : 108 : }
# 1501 : :
# 1502 : 108 : void Compaction::AddInputDeletions(VersionEdit* edit) {
# 1503 [ + + ]: 324 : for (int which = 0; which < 2; which++) {
# 1504 [ + + ]: 637 : for (size_t i = 0; i < inputs_[which].size(); i++) {
# 1505 : 421 : edit->DeleteFile(level_ + which, inputs_[which][i]->number);
# 1506 : 421 : }
# 1507 : 216 : }
# 1508 : 108 : }
# 1509 : :
# 1510 : 180 : bool Compaction::IsBaseLevelForKey(const Slice& user_key) {
# 1511 : : // Maybe use binary search to find right entry instead of linear search?
# 1512 : 180 : const Comparator* user_cmp = input_version_->vset_->icmp_.user_comparator();
# 1513 [ + + ]: 1080 : for (int lvl = level_ + 2; lvl < config::kNumLevels; lvl++) {
# 1514 : 900 : const std::vector<FileMetaData*>& files = input_version_->files_[lvl];
# 1515 [ - + ]: 900 : 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 : 0 : return false;
# 1522 : 0 : }
# 1523 : 0 : break;
# 1524 : 0 : }
# 1525 : 0 : level_ptrs_[lvl]++;
# 1526 : 0 : }
# 1527 : 900 : }
# 1528 : 180 : return true;
# 1529 : 180 : }
# 1530 : :
# 1531 : 35372 : bool Compaction::ShouldStopBefore(const Slice& internal_key) {
# 1532 : 35372 : const VersionSet* vset = input_version_->vset_;
# 1533 : : // Scan to find earliest grandparent file that contains key.
# 1534 : 35372 : const InternalKeyComparator* icmp = &vset->icmp_;
# 1535 [ - + ][ - + ]: 35372 : while (grandparent_index_ < grandparents_.size() &&
# 1536 [ # # ]: 35372 : icmp->Compare(internal_key,
# 1537 : 0 : grandparents_[grandparent_index_]->largest.Encode()) >
# 1538 : 0 : 0) {
# 1539 [ # # ]: 0 : if (seen_key_) {
# 1540 : 0 : overlapped_bytes_ += grandparents_[grandparent_index_]->file_size;
# 1541 : 0 : }
# 1542 : 0 : grandparent_index_++;
# 1543 : 0 : }
# 1544 : 35372 : seen_key_ = true;
# 1545 : :
# 1546 [ - + ]: 35372 : 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 : 35372 : } else {
# 1551 : 35372 : return false;
# 1552 : 35372 : }
# 1553 : 35372 : }
# 1554 : :
# 1555 : 108 : void Compaction::ReleaseInputs() {
# 1556 [ + - ]: 108 : if (input_version_ != nullptr) {
# 1557 : 108 : input_version_->Unref();
# 1558 : 108 : input_version_ = nullptr;
# 1559 : 108 : }
# 1560 : 108 : }
# 1561 : :
# 1562 : : } // namespace leveldb
|
