<commit_before>// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "db/db_impl.h"

#include <time.h>
#include <algorithm>
#include <errno.h>
#include <set>
#include <string>
#include <stdint.h>
#include <stdio.h>
#include <unistd.h>
#include <vector>
#include "db/builder.h"
#include "db/db_iter.h"
#include "db/dbformat.h"
#include "db/filename.h"
#include "db/log_reader.h"
#include "db/log_writer.h"
#include "db/memtable.h"
#include "db/table_cache.h"
#include "db/version_set.h"
#include "db/write_batch_internal.h"
#include "leveldb/db.h"
#include "leveldb/env.h"
#include "leveldb/status.h"
#include "leveldb/table.h"
#include "leveldb/table_builder.h"
#include "port/port.h"
#include "table/block.h"
#include "table/merger.h"
#include "table/two_level_iterator.h"
#include "util/coding.h"
#include "util/logging.h"
#include "util/mutexlock.h"
#include "util/throttle.h"
#include "leveldb/perf_count.h"

#define __STDC_FORMAT_MACROS
#include <inttypes.h>

namespace leveldb {

// Information kept for every waiting writer
struct DBImpl::Writer {
  Status status;
  WriteBatch* batch;
  bool sync;
  bool done;
  port::CondVar cv;

  explicit Writer(port::Mutex* mu) : cv(mu) { }
};

struct DBImpl::CompactionState {
  Compaction* const compaction;

  // Sequence numbers < smallest_snapshot are not significant since we
  // will never have to service a snapshot below smallest_snapshot.
  // Therefore if we have seen a sequence number S <= smallest_snapshot,
  // we can drop all entries for the same key with sequence numbers < S.
  SequenceNumber smallest_snapshot;

  // Files produced by compaction
  struct Output {
    uint64_t number;
    uint64_t file_size;
    InternalKey smallest, largest;
  };
  std::vector<Output> outputs;

  // State kept for output being generated
  WritableFile* outfile;
  TableBuilder* builder;

  uint64_t total_bytes;
  uint64_t num_entries;

  Output* current_output() { return &outputs[outputs.size()-1]; }

  explicit CompactionState(Compaction* c)
      : compaction(c),
        outfile(NULL),
        builder(NULL),
        total_bytes(0),
        num_entries(0) {
  }
};

Value::~Value() {}

class StringValue : public Value {
 public:
  explicit StringValue(std::string& val) : value_(val) {}
  ~StringValue() {}

  StringValue& assign(const char* data, size_t size) {
    value_.assign(data, size);
    return *this;
  }

 private:
  std::string& value_;
};

// Fix user-supplied options to be reasonable
template <class T,class V>
static void ClipToRange(T* ptr, V minvalue, V maxvalue) {
  if (static_cast<V>(*ptr) > maxvalue) *ptr = maxvalue;
  if (static_cast<V>(*ptr) < minvalue) *ptr = minvalue;
}

Options SanitizeOptions(const std::string& dbname,
                        const InternalKeyComparator* icmp,
                        const InternalFilterPolicy* ipolicy,
                        const Options& src) {
  Options result = src;
  result.comparator = icmp;
  result.filter_policy = (src.filter_policy != NULL) ? ipolicy : NULL;
  ClipToRange(&result.max_open_files,            20,     50000);
  ClipToRange(&result.write_buffer_size,         64<<10, 1<<30);
  ClipToRange(&result.block_size,                1<<10,  4<<20);
  if (result.info_log == NULL) {
    // Open a log file in the same directory as the db
    src.env->CreateDir(dbname);  // In case it does not exist
    src.env->RenameFile(InfoLogFileName(dbname), OldInfoLogFileName(dbname));
    Status s = src.env->NewLogger(InfoLogFileName(dbname), &result.info_log);
    if (!s.ok()) {
      // No place suitable for logging
      result.info_log = NULL;
    }
  }
  if (result.block_cache == NULL) {
    result.block_cache = NewLRUCache(8 << 20);
  }
  return result;
}

DBImpl::DBImpl(const Options& options, const std::string& dbname)
    : env_(options.env),
      internal_comparator_(options.comparator),
      internal_filter_policy_(options.filter_policy),
      options_(SanitizeOptions(
          dbname, &internal_comparator_, &internal_filter_policy_, options)),
      owns_info_log_(options_.info_log != options.info_log),
      owns_cache_(options_.block_cache != options.block_cache),
      dbname_(dbname),
      db_lock_(NULL),
      shutting_down_(NULL),
      bg_cv_(&mutex_),
      mem_(new MemTable(internal_comparator_)),
      imm_(NULL),
      logfile_(NULL),
      logfile_number_(0),
      log_(NULL),
      tmp_batch_(new WriteBatch),
      bg_compaction_scheduled_(false),
      manual_compaction_(NULL),
      level0_good(true)
{
  mem_->Ref();
  has_imm_.Release_Store(NULL);

  // Reserve ten files or so for other uses and give the rest to TableCache.
  const int table_cache_size = options_.max_open_files - 10;
  table_cache_ = new TableCache(dbname_, &options_, table_cache_size);

  versions_ = new VersionSet(dbname_, &options_, table_cache_,
                             &internal_comparator_);

  options_.Dump(options_.info_log);
}

DBImpl::~DBImpl() {
  // Wait for background work to finish
  mutex_.Lock();
  shutting_down_.Release_Store(this);  // Any non-NULL value is ok
  while (bg_compaction_scheduled_) {
    bg_cv_.Wait();
  }
  mutex_.Unlock();

  delete versions_;
  if (mem_ != NULL) mem_->Unref();
  if (imm_ != NULL) imm_->Unref();
  delete tmp_batch_;
  delete log_;
  delete logfile_;
  delete table_cache_;

  if (owns_info_log_) {
    delete options_.info_log;
  }
  if (owns_cache_) {
    delete options_.block_cache;
  }
  if (db_lock_ != NULL) {
    env_->UnlockFile(db_lock_);
  }
}

Status DBImpl::NewDB() {
  VersionEdit new_db;
  new_db.SetComparatorName(user_comparator()->Name());
  new_db.SetLogNumber(0);
  new_db.SetNextFile(2);
  new_db.SetLastSequence(0);

  const std::string manifest = DescriptorFileName(dbname_, 1);
  WritableFile* file;
  Status s = env_->NewWritableFile(manifest, &file);
  if (!s.ok()) {
    return s;
  }
  {
    log::Writer log(file);
    std::string record;
    new_db.EncodeTo(&record);
    s = log.AddRecord(record);
    if (s.ok()) {
      s = file->Close();
    }
  }
  delete file;
  if (s.ok()) {
    // Make "CURRENT" file that points to the new manifest file.
    s = SetCurrentFile(env_, dbname_, 1);
  } else {
    env_->DeleteFile(manifest);
  }

  return s;
}

void DBImpl::MaybeIgnoreError(Status* s) const {
  if (s->ok() || options_.paranoid_checks) {
    // No change needed
  } else {
    Log(options_.info_log, "Ignoring error %s", s->ToString().c_str());
    *s = Status::OK();
  }
}

void DBImpl::DeleteObsoleteFiles() {
  // Make a set of all of the live files
  std::set<uint64_t> live = pending_outputs_;
  versions_->AddLiveFiles(&live);

  // prune the database root directory
  std::vector<std::string> filenames;
  env_->GetChildren(dbname_, &filenames); // Ignoring errors on purpose
  for (size_t i = 0; i < filenames.size(); i++) {
      KeepOrDelete(filenames[i], -1, live);
  }   // for

  // prune the table file directories
  for (int level=0; level<config::kNumLevels; ++level)
  {
      std::string dirname;

      filenames.clear();
      dirname=MakeDirName2(dbname_, level, "sst");
      env_->GetChildren(dirname, &filenames); // Ignoring errors on purpose
      for (size_t i = 0; i < filenames.size(); i++) {
          KeepOrDelete(filenames[i], level, live);
      }   // for
  }   // for
}

void
DBImpl::KeepOrDelete(
    const std::string & Filename,
    int Level,
    const std::set<uint64_t> & Live)
{
  uint64_t number;
  FileType type;
  bool keep = true;

  if (ParseFileName(Filename, &number, &type))
  {
      switch (type)
      {
          case kLogFile:
              keep = ((number >= versions_->LogNumber()) ||
                      (number == versions_->PrevLogNumber()));
              break;

          case kDescriptorFile:
              // Keep my manifest file, and any newer incarnations'
              // (in case there is a race that allows other incarnations)
              keep = (number >= versions_->ManifestFileNumber());
              break;

          case kTableFile:
              keep = (Live.find(number) != Live.end());
              break;

          case kTempFile:
              // Any temp files that are currently being written to must
              // be recorded in pending_outputs_, which is inserted into "Live"
              keep = (Live.find(number) != Live.end());
          break;

          case kCurrentFile:
          case kDBLockFile:
          case kInfoLogFile:
              keep = true;
              break;
      }   // switch

      if (!keep)
      {
          if (type == kTableFile) {
              // temporary hard coding of extra overlapped
              //  levels
              table_cache_->Evict(number, (Level<config::kNumOverlapLevels));
          }
          Log(options_.info_log, "Delete type=%d #%lld\n",
              int(type),
              static_cast<unsigned long long>(number));
          if (-1!=Level)
          {
              std::string file;

              file=TableFileName(dbname_, number, Level);
              env_->DeleteFile(file);
          }   // if
          else
          {
              env_->DeleteFile(dbname_ + "/" + Filename);
          }   // else
      }   // if
  }   // if
} // DBImpl::KeepOrDelete


Status DBImpl::Recover(VersionEdit* edit) {
  mutex_.AssertHeld();

  // Ignore error from CreateDir since the creation of the DB is
  // committed only when the descriptor is created, and this directory
  // may already exist from a previous failed creation attempt.
  env_->CreateDir(dbname_);
  assert(db_lock_ == NULL);
  Status s = env_->LockFile(LockFileName(dbname_), &db_lock_);
  if (!s.ok()) {
    return s;
  }

  if (!env_->FileExists(CurrentFileName(dbname_))) {
    if (options_.create_if_missing) {
      s = NewDB();
      if (!s.ok()) {
        return s;
      }
    } else {
      return Status::InvalidArgument(
          dbname_, "does not exist (create_if_missing is false)");
    }
  } else {
    if (options_.error_if_exists) {
      return Status::InvalidArgument(
          dbname_, "exists (error_if_exists is true)");
    }
  }

  // read manifest
  s = versions_->Recover();

  // Verify Riak 1.3 directory structure created and ready
  if (s.ok() && !TestForLevelDirectories(env_, dbname_, versions_->current()))
  {
      int level;
      std::string old_name, new_name;

      if (options_.create_if_missing)
      {
          // move files from old heirarchy to new
          s=MakeLevelDirectories(env_, dbname_);
          if (s.ok())
          {
              for (level=0; level<config::kNumLevels && s.ok(); ++level)
              {
                  const std::vector<FileMetaData*> & level_files(versions_->current()->GetFileList(level));
                  std::vector<FileMetaData*>::const_iterator it;

                  for (it=level_files.begin(); level_files.end()!=it && s.ok(); ++it)
                  {
                      new_name=TableFileName(dbname_, (*it)->number, level);

                      // test for partial completion
                      if (!env_->FileExists(new_name.c_str()))
                      {
                          old_name=TableFileName(dbname_, (*it)->number, -2);
                          s=env_->RenameFile(old_name, new_name);
                      }   // if
                  }   // for
              }   // for
          }   // if
          else
              return s;
      }   // if
      else
      {
          return Status::InvalidArgument(
              dbname_, "level directories do not exist (create_if_missing is false)");
      }   // else

  }   // if


  if (s.ok()) {
    SequenceNumber max_sequence(0);

    // Recover from all newer log files than the ones named in the
    // descriptor (new log files may have been added by the previous
    // incarnation without registering them in the descriptor).
    //
    // Note that PrevLogNumber() is no longer used, but we pay
    // attention to it in case we are recovering a database
    // produced by an older version of leveldb.
    const uint64_t min_log = versions_->LogNumber();
    const uint64_t prev_log = versions_->PrevLogNumber();
    std::vector<std::string> filenames;
    s = env_->GetChildren(dbname_, &filenames);
    if (!s.ok()) {
      return s;
    }
    uint64_t number;
    FileType type;
    std::vector<uint64_t> logs;
    for (size_t i = 0; i < filenames.size(); i++) {
      if (ParseFileName(filenames[i], &number, &type)
          && type == kLogFile
          && ((number >= min_log) || (number == prev_log))) {
        logs.push_back(number);
      }
    }

    // Recover in the order in which the logs were generated
    std::sort(logs.begin(), logs.end());
    for (size_t i = 0; i < logs.size(); i++) {
      s = RecoverLogFile(logs[i], edit, &max_sequence);

      // The previous incarnation may not have written any MANIFEST
      // records after allocating this log number.  So we manually
      // update the file number allocation counter in VersionSet.
      versions_->MarkFileNumberUsed(logs[i]);
    }

    if (s.ok()) {
      if (versions_->LastSequence() < max_sequence) {
        versions_->SetLastSequence(max_sequence);
      }
    }
  }

  return s;
}


void DBImpl::CheckCompactionState()
{
    mutex_.AssertHeld();
    bool log_flag, need_compaction;

    // Verify Riak 1.4 level sizing, run compactions to fix as necessary
    //  (also recompacts hard repair of all files to level 0)

    log_flag=false;
    need_compaction=false;

    // loop on pending background compactions
    //  reminder: mutex_ is held
    do
    {
        int level;

        // wait out executing compaction (Wait gives mutex to compactions)
        if (bg_compaction_scheduled_)
            bg_cv_.Wait();

        for (level=0, need_compaction=false;
             level<config::kNumLevels && !need_compaction;
             ++level)
        {
            if (versions_->IsLevelOverlapped(level)
                && config::kL0_SlowdownWritesTrigger<=versions_->NumLevelFiles(level))
            {
                need_compaction=true;
                MaybeScheduleCompaction();
                if (!log_flag)
                {
                    log_flag=true;
                    Log(options_.info_log, "Cleanup compactions started ... DB::Open paused");
                }   // if
            }   //if
        }   // for

    } while(bg_compaction_scheduled_ && need_compaction);

    if (log_flag)
        Log(options_.info_log, "Cleanup compactions completed ... DB::Open continuing");

    // prior code only called this function instead of CheckCompactionState
    //  (duplicates original Google functionality)
    else
        MaybeScheduleCompaction();

    return;

}  // DBImpl::CheckCompactionState()


Status DBImpl::RecoverLogFile(uint64_t log_number,
                              VersionEdit* edit,
                              SequenceNumber* max_sequence) {
  struct LogReporter : public log::Reader::Reporter {
    Env* env;
    Logger* info_log;
    const char* fname;
    Status* status;  // NULL if options_.paranoid_checks==false
    virtual void Corruption(size_t bytes, const Status& s) {
      Log(info_log, "%s%s: dropping %d bytes; %s",
          (this->status == NULL ? "(ignoring error) " : ""),
          fname, static_cast<int>(bytes), s.ToString().c_str());
      if (this->status != NULL && this->status->ok()) *this->status = s;
    }
  };

  mutex_.AssertHeld();

  // Open the log file
  std::string fname = LogFileName(dbname_, log_number);
  SequentialFile* file;
  Status status = env_->NewSequentialFile(fname, &file);
  if (!status.ok()) {
    MaybeIgnoreError(&status);
    return status;
  }

  // Create the log reader.
  LogReporter reporter;
  reporter.env = env_;
  reporter.info_log = options_.info_log;
  reporter.fname = fname.c_str();
  reporter.status = (options_.paranoid_checks ? &status : NULL);
  // We intentially make log::Reader do checksumming even if
  // paranoid_checks==false so that corruptions cause entire commits
  // to be skipped instead of propagating bad information (like overly
  // large sequence numbers).
  log::Reader reader(file, &reporter, true/*checksum*/,
                     0/*initial_offset*/);
  Log(options_.info_log, "Recovering log #%llu",
      (unsigned long long) log_number);

  // Read all the records and add to a memtable
  std::string scratch;
  Slice record;
  WriteBatch batch;
  MemTable* mem = NULL;
  while (reader.ReadRecord(&record, &scratch) &&
         status.ok()) {
    if (record.size() < 12) {
      reporter.Corruption(
          record.size(), Status::Corruption("log record too small"));
      continue;
    }
    WriteBatchInternal::SetContents(&batch, record);

    if (mem == NULL) {
      mem = new MemTable(internal_comparator_);
      mem->Ref();
    }
    status = WriteBatchInternal::InsertInto(&batch, mem);
    MaybeIgnoreError(&status);
    if (!status.ok()) {
      break;
    }
    const SequenceNumber last_seq =
        WriteBatchInternal::Sequence(&batch) +
        WriteBatchInternal::Count(&batch) - 1;
    if (last_seq > *max_sequence) {
      *max_sequence = last_seq;
    }

    if (mem->ApproximateMemoryUsage() > options_.write_buffer_size) {
      status = WriteLevel0Table(mem, edit, NULL);
      if (!status.ok()) {
        // Reflect errors immediately so that conditions like full
        // file-systems cause the DB::Open() to fail.
        break;
      }
      mem->Unref();
      mem = NULL;
    }
  }

  if (status.ok() && mem != NULL) {
    status = WriteLevel0Table(mem, edit, NULL);
    // Reflect errors immediately so that conditions like full
    // file-systems cause the DB::Open() to fail.
  }

  if (mem != NULL) mem->Unref();
  delete file;
  return status;
}

Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit,
                                Version* base) {
  mutex_.AssertHeld();
  const uint64_t start_micros = env_->NowMicros();
  FileMetaData meta;
  meta.number = versions_->NewFileNumber();
  meta.level = 0;
  pending_outputs_.insert(meta.number);
  Iterator* iter = mem->NewIterator();
  SequenceNumber smallest_snapshot;
  Log(options_.info_log, "Level-0 table #%llu: started",
      (unsigned long long) meta.number);

  if (snapshots_.empty()) {
    smallest_snapshot = versions_->LastSequence();
  } else {
    smallest_snapshot = snapshots_.oldest()->number_;
  }

  Status s;
  {
    Options local_options;

    mutex_.Unlock();

    // want the data slammed to disk as fast as possible,
    //  no compression for level 0.
    local_options=options_;
    local_options.compression=kNoCompression;
    s = BuildTable(dbname_, env_, local_options, user_comparator(), table_cache_, iter, &meta, smallest_snapshot);

    mutex_.Lock();
  }

  Log(options_.info_log, "Level-0 table #%llu: %llu bytes, %llu keys %s",
      (unsigned long long) meta.number,
      (unsigned long long) meta.file_size,
      (unsigned long long) meta.num_entries,
      s.ToString().c_str());
  delete iter;
  pending_outputs_.erase(meta.number);


  // Note that if file_size is zero, the file has been deleted and
  // should not be added to the manifest.
  int level = 0;
  if (s.ok() && meta.file_size > 0) {
    const Slice min_user_key = meta.smallest.user_key();
    const Slice max_user_key = meta.largest.user_key();
    if (base != NULL) {
        level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);
        if (0!=level)
        {
            std::string old_name, new_name;

            old_name=TableFileName(dbname_, meta.number, 0);
            new_name=TableFileName(dbname_, meta.number, level);
            s=env_->RenameFile(old_name, new_name);
        }   // if
    }

    if (s.ok())
        edit->AddFile(level, meta.number, meta.file_size,
                      meta.smallest, meta.largest);
  }

  CompactionStats stats;
  stats.micros = env_->NowMicros() - start_micros;
  stats.bytes_written = meta.file_size;
  stats_[level].Add(stats);

  if (0!=meta.num_entries && s.ok())
  {
      // This SetWriteRate() call removed because this thread
      //  has priority (others blocked on mutex) and thus created
      //  misleading estimates of disk write speed
      // 2x since mem to disk, not disk to disk
      //      env_->SetWriteRate(2*stats.micros/meta.num_entries);
      // 2x since mem to disk, not disk to disk
      // env_->SetWriteRate(2*stats.micros/meta.num_entries);
  }   // if

  return s;
}

Status DBImpl::CompactMemTable() {
  mutex_.AssertHeld();
  assert(imm_ != NULL);

  // Save the contents of the memtable as a new Table
  VersionEdit edit;
  Version* base = versions_->current();
  base->Ref();
  Status s = WriteLevel0Table(imm_, &edit, base);
  base->Unref();

  if (s.ok() && shutting_down_.Acquire_Load()) {
    s = Status::IOError("Deleting DB during memtable compaction");
  }

  // Replace immutable memtable with the generated Table
  if (s.ok()) {
    edit.SetPrevLogNumber(0);
    edit.SetLogNumber(logfile_number_);  // Earlier logs no longer needed
    s = versions_->LogAndApply(&edit, &mutex_);
  }

  if (s.ok()) {
    // Commit to the new state
    imm_->Unref();
    imm_ = NULL;
    has_imm_.Release_Store(NULL);
    DeleteObsoleteFiles();
  }

  return s;
}

void DBImpl::CompactRange(const Slice* begin, const Slice* end) {
  int max_level_with_files = 1;
  {
    MutexLock l(&mutex_);
    Version* base = versions_->current();
    for (int level = 1; level < config::kNumLevels; level++) {
      if (base->OverlapInLevel(level, begin, end)) {
        max_level_with_files = level;
      }
    }
  }
  TEST_CompactMemTable(); // TODO(sanjay): Skip if memtable does not overlap
  for (int level = 0; level < max_level_with_files; level++) {
    TEST_CompactRange(level, begin, end);
  }
}

void DBImpl::TEST_CompactRange(int level, const Slice* begin,const Slice* end) {
  assert(level >= 0);
  assert(level + 1 < config::kNumLevels);

  InternalKey begin_storage, end_storage;

  ManualCompaction manual;
  manual.level = level;
  manual.done = false;
  if (begin == NULL) {
    manual.begin = NULL;
  } else {
    begin_storage = InternalKey(*begin, kMaxSequenceNumber, kValueTypeForSeek);
    manual.begin = &begin_storage;
  }
  if (end == NULL) {
    manual.end = NULL;
  } else {
    end_storage = InternalKey(*end, 0, static_cast<ValueType>(0));
    manual.end = &end_storage;
  }

  MutexLock l(&mutex_);
  while (!manual.done) {
    while (manual_compaction_ != NULL || bg_compaction_scheduled_) {
      bg_cv_.Wait();
    }
    manual_compaction_ = &manual;
    MaybeScheduleCompaction();
    while (manual_compaction_ == &manual) {
      bg_cv_.Wait();
    }
  }
}

Status DBImpl::TEST_CompactMemTable() {
  // NULL batch means just wait for earlier writes to be done
  Status s = Write(WriteOptions(), NULL);
  if (s.ok()) {
    // Wait until the compaction completes
    MutexLock l(&mutex_);
    while (imm_ != NULL && bg_error_.ok()) {
      bg_cv_.Wait();
    }
    if (imm_ != NULL) {
      s = bg_error_;
    }
  }
  return s;
}

void DBImpl::MaybeScheduleCompaction() {
  mutex_.AssertHeld();

  int state, priority;
  bool push;

  // decide which background thread gets the compaction job
  state=0;
  priority=0;
  push=false;

  // writing of memory to disk: high priority
  if (NULL!=imm_)
  {
      push=true;
  }   // if

  // merge level 0s to level 1
  else
  {
      Compaction * c_ptr;
      c_ptr=versions_->PickCompaction();

      // compaction of level 0 files:  high priority
      if (NULL!=c_ptr && c_ptr->level()==0)
      {
          push=true;
          priority=versions_->NumLevelFiles(0);
      }   // if
      else
      {
          priority=versions_->current()->WritePenalty();
      }   // else

      delete c_ptr;
  }   // if

  if (push)
  {
      // is something else already on background work queue
      if (bg_compaction_scheduled_)
          state=2;
      else
          state=1;
  }   // if


  if (bg_compaction_scheduled_ && !push) {
    // Already scheduled
  } else if (shutting_down_.Acquire_Load()) {
    // DB is being deleted; no more background compactions
  } else if (imm_ == NULL &&
             manual_compaction_ == NULL &&
             !versions_->NeedsCompaction()) {
    // No work to be done
  } else {
    bg_compaction_scheduled_ = true;
    env_->Schedule(&DBImpl::BGWork, this, state, (NULL!=imm_), priority);
  }
}

void DBImpl::BGWork(void* db) {
  reinterpret_cast<DBImpl*>(db)->BackgroundCall();
}

void DBImpl::BackgroundCall() {
  MutexLock l(&mutex_);
  assert(bg_compaction_scheduled_);
  if (!shutting_down_.Acquire_Load()) {
    Status s = BackgroundCompaction();
    if (!s.ok()) {
      // Wait a little bit before retrying background compaction in
      // case this is an environmental problem and we do not want to
      // chew up resources for failed compactions for the duration of
      // the problem.
      bg_cv_.SignalAll();  // In case a waiter can proceed despite the error
      Log(options_.info_log, "Waiting after background compaction error: %s",
          s.ToString().c_str());
      mutex_.Unlock();
      env_->SleepForMicroseconds(1000000);
      mutex_.Lock();
    }
  }
  bg_compaction_scheduled_ = false;

  // Previous compaction may have produced too many files in a level,
  // so reschedule another compaction if needed.
  if (!options_.is_repair)
      MaybeScheduleCompaction();
  bg_cv_.SignalAll();
}

Status DBImpl::BackgroundCompaction() {
  Status status;

  mutex_.AssertHeld();

  if (imm_ != NULL) {
    pthread_rwlock_rdlock(&gThreadLock0);
    status=CompactMemTable();
    pthread_rwlock_unlock(&gThreadLock0);
    return status;
  }

  Compaction* c;
  bool is_manual = (manual_compaction_ != NULL);
  InternalKey manual_end;
  if (is_manual) {
    ManualCompaction* m = manual_compaction_;
    c = versions_->CompactRange(m->level, m->begin, m->end);
    m->done = (c == NULL);
    if (c != NULL) {
      manual_end = c->input(0, c->num_input_files(0) - 1)->largest;
    }
    Log(options_.info_log,
        "Manual compaction at level-%d from %s .. %s; will stop at %s\n",
        m->level,
        (m->begin ? m->begin->DebugString().c_str() : "(begin)"),
        (m->end ? m->end->DebugString().c_str() : "(end)"),
        (m->done ? "(end)" : manual_end.DebugString().c_str()));
  } else {
    c = versions_->PickCompaction();
  }


  if (c == NULL) {
    // Nothing to do
  } else if (!is_manual && c->IsTrivialMove()) {
    // Move file to next level
    assert(c->num_input_files(0) == 1);
    std::string old_name, new_name;
    FileMetaData* f = c->input(0, 0);

    old_name=TableFileName(dbname_, f->number, c->level());
    new_name=TableFileName(dbname_, f->number, c->level() +1);
    status=env_->RenameFile(old_name, new_name);

    if (status.ok())
    {
        c->edit()->DeleteFile(c->level(), f->number);
        c->edit()->AddFile(c->level() + 1, f->number, f->file_size,
                           f->smallest, f->largest);
        status = versions_->LogAndApply(c->edit(), &mutex_);

        // if LogAndApply fails, should file be renamed back to original spot?
        VersionSet::LevelSummaryStorage tmp;
        Log(options_.info_log, "Moved #%lld to level-%d %lld bytes %s: %s\n",
            static_cast<unsigned long long>(f->number),
            c->level() + 1,
            static_cast<unsigned long long>(f->file_size),
            status.ToString().c_str(),
            versions_->LevelSummary(&tmp));
    }  // if
  } else {
    CompactionState* compact = new CompactionState(c);
    status = DoCompactionWork(compact);
    CleanupCompaction(compact);
    c->ReleaseInputs();
    DeleteObsoleteFiles();
  }
  delete c;

  if (status.ok()) {
    // Done
  } else if (shutting_down_.Acquire_Load()) {
    // Ignore compaction errors found during shutting down
  } else {
    Log(options_.info_log,
        "Compaction error: %s", status.ToString().c_str());
    if (options_.paranoid_checks && bg_error_.ok()) {
      bg_error_ = status;
    }
  }

  if (is_manual) {
    ManualCompaction* m = manual_compaction_;
    if (!status.ok()) {
      m->done = true;
    }
    if (!m->done) {
      // We only compacted part of the requested range.  Update *m
      // to the range that is left to be compacted.
      m->tmp_storage = manual_end;
      m->begin = &m->tmp_storage;
    }
    manual_compaction_ = NULL;
  }

  return status;
}

void DBImpl::CleanupCompaction(CompactionState* compact) {
  mutex_.AssertHeld();
  if (compact->builder != NULL) {
    // May happen if we get a shutdown call in the middle of compaction
    compact->builder->Abandon();
    delete compact->builder;
  } else {
    assert(compact->outfile == NULL);
  }
  delete compact->outfile;
  for (size_t i = 0; i < compact->outputs.size(); i++) {
    const CompactionState::Output& out = compact->outputs[i];
    pending_outputs_.erase(out.number);
  }
  delete compact;
}

Status DBImpl::OpenCompactionOutputFile(CompactionState* compact) {
  assert(compact != NULL);
  assert(compact->builder == NULL);
  uint64_t file_number;
  {
    mutex_.Lock();
    file_number = versions_->NewFileNumber();
    pending_outputs_.insert(file_number);
    CompactionState::Output out;
    out.number = file_number;
    out.smallest.Clear();
    out.largest.Clear();
    compact->outputs.push_back(out);
    mutex_.Unlock();
  }

  // Make the output file
  std::string fname = TableFileName(dbname_, file_number, compact->compaction->level()+1);
  Status s = env_->NewWritableFile(fname, &compact->outfile);
  if (s.ok()) {
    compact->builder = new TableBuilder(options_, compact->outfile);
  }
  return s;
}

Status DBImpl::FinishCompactionOutputFile(CompactionState* compact,
                                          Iterator* input) {
  assert(compact != NULL);
  assert(compact->outfile != NULL);
  assert(compact->builder != NULL);

  const uint64_t output_number = compact->current_output()->number;
  assert(output_number != 0);

  // Check for iterator errors
  Status s = input->status();
  const uint64_t current_entries = compact->builder->NumEntries();
  if (s.ok()) {
    s = compact->builder->Finish();
  } else {
    compact->builder->Abandon();
  }
  const uint64_t current_bytes = compact->builder->FileSize();
  compact->current_output()->file_size = current_bytes;
  compact->total_bytes += current_bytes;
  compact->num_entries += compact->builder->NumEntries();
  delete compact->builder;
  compact->builder = NULL;

  // Finish and check for file errors
  if (s.ok()) {
    s = compact->outfile->Sync();
  }
  if (s.ok()) {
    s = compact->outfile->Close();
  }
  delete compact->outfile;
  compact->outfile = NULL;

  if (s.ok() && current_entries > 0) {
    // Verify that the table is usable
    Iterator* iter = table_cache_->NewIterator(ReadOptions(),
                                               output_number,
                                               current_bytes,
                                               compact->compaction->level()+1);
    s = iter->status();
    delete iter;
    if (s.ok()) {
      Log(options_.info_log,
          "Generated table #%llu: %lld keys, %lld bytes",
          (unsigned long long) output_number,
          (unsigned long long) current_entries,
          (unsigned long long) current_bytes);
    }
  }
  return s;
}


Status DBImpl::InstallCompactionResults(CompactionState* compact) {
  mutex_.AssertHeld();
  Log(options_.info_log,  "Compacted %d@%d + %d@%d files => %lld bytes",
      compact->compaction->num_input_files(0),
      compact->compaction->level(),
      compact->compaction->num_input_files(1),
      compact->compaction->level() + 1,
      static_cast<long long>(compact->total_bytes));

  // Add compaction outputs
  compact->compaction->AddInputDeletions(compact->compaction->edit());
  const int level = compact->compaction->level();
  for (size_t i = 0; i < compact->outputs.size(); i++) {
    const CompactionState::Output& out = compact->outputs[i];
    compact->compaction->edit()->AddFile(
        level + 1,
        out.number, out.file_size, out.smallest, out.largest);
  }
  return versions_->LogAndApply(compact->compaction->edit(), &mutex_);
}

Status DBImpl::DoCompactionWork(CompactionState* compact) {

  Log(options_.info_log,  "Compacting %d@%d + %d@%d files",
      compact->compaction->num_input_files(0),
      compact->compaction->level(),
      compact->compaction->num_input_files(1),
      compact->compaction->level() + 1);

  assert(versions_->NumLevelFiles(compact->compaction->level()) > 0);
  assert(compact->builder == NULL);
  assert(compact->outfile == NULL);
  if (snapshots_.empty()) {
    compact->smallest_snapshot = versions_->LastSequence();
  } else {
    compact->smallest_snapshot = snapshots_.oldest()->number_;
  }

  // Release mutex while we're actually doing the compaction work
  mutex_.Unlock();

  bool is_level0_compaction=(0 == compact->compaction->level());

  if (is_level0_compaction)
      pthread_rwlock_rdlock(&gThreadLock1);

  const uint64_t start_micros = env_->NowMicros();
  int64_t imm_micros = 0;  // Micros spent doing imm_ compactions


  Iterator* input = versions_->MakeInputIterator(compact->compaction);
  input->SeekToFirst();
  Status status;
  ParsedInternalKey ikey;
  std::string current_user_key;

  KeyRetirement retire(user_comparator(), compact->smallest_snapshot, compact->compaction);

  for (; input->Valid() && !shutting_down_.Acquire_Load(); )
  {
    // Prioritize compaction work ... every 100 keys
    if (NULL==compact->builder
	|| 0==(compact->builder->NumEntries() % 100))
      imm_micros+=PrioritizeWork(is_level0_compaction);

    Slice key = input->key();
    if (compact->builder != NULL
        && compact->compaction->ShouldStopBefore(key, compact->builder->NumEntries())) {

      status = FinishCompactionOutputFile(compact, input);
      if (!status.ok()) {
        break;
      }
    }

    // Handle key/value, add to state, etc.
    bool drop = retire(key);

    if (!drop) {
      // Open output file if necessary
      if (compact->builder == NULL) {
        status = OpenCompactionOutputFile(compact);
        if (!status.ok()) {
          break;
        }
      }
      if (compact->builder->NumEntries() == 0) {
        compact->current_output()->smallest.DecodeFrom(key);
      }
      compact->current_output()->largest.DecodeFrom(key);
      compact->builder->Add(key, input->value());

      // update throttle ... now, end of compaction may be too late
      //   but not too often since NowMicros can be costly
      size_t entry_count;
      entry_count=compact->num_entries + compact->builder->NumEntries();

      // imm_micros intentional NOT removed from time calculation,
      //  gives better measure of overall activity / write overhead
      if (1==(entry_count % 1000) && 1000<entry_count)
      {
          // test for priority change
          if (!is_level0_compaction)
          {
              // raise this compaction's priority if it is blocking a
              //  dire compaction of level 0 files
              if ((int)config::kL0_SlowdownWritesTrigger < versions_->current()->NumFiles(0))
              {
                  pthread_rwlock_rdlock(&gThreadLock1);
                  is_level0_compaction=true;
              }   // if
          }   // if
      }   // if

      // Close output file if it is big enough
      if (compact->builder->FileSize() >=
          compact->compaction->MaxOutputFileSize()) {
        status = FinishCompactionOutputFile(compact, input);
        if (!status.ok()) {
          break;
        }
      }
    }

    input->Next();
  }

  if (status.ok() && shutting_down_.Acquire_Load()) {
    status = Status::IOError("Deleting DB during compaction");
  }
  if (status.ok() && compact->builder != NULL) {
    status = FinishCompactionOutputFile(compact, input);
  }
  if (status.ok()) {
    status = input->status();
  }
  delete input;
  input = NULL;

  CompactionStats stats;
  stats.micros = env_->NowMicros() - start_micros - imm_micros;
  for (int which = 0; which < 2; which++) {
    for (int i = 0; i < compact->compaction->num_input_files(which); i++) {
      stats.bytes_read += compact->compaction->input(which, i)->file_size;
    }
  }
  for (size_t i = 0; i < compact->outputs.size(); i++) {
    stats.bytes_written += compact->outputs[i].file_size;
  }

  if (is_level0_compaction)
      pthread_rwlock_unlock(&gThreadLock1);

  mutex_.Lock();
  stats_[compact->compaction->level() + 1].Add(stats);

  if (status.ok()) {
    // imm_micros intentional NOT removed from time calculation,
    //  gives better measure of overall activity / write overhead
    if (0!=compact->num_entries)
        SetThrottleWriteRate((env_->NowMicros() - start_micros), compact->num_entries,
                            is_level0_compaction, env_->GetBackgroundBacklog());
    status = InstallCompactionResults(compact);
  }
  VersionSet::LevelSummaryStorage tmp;
  Log(options_.info_log,
      "compacted to: %s", versions_->LevelSummary(&tmp));
  return status;
}


int64_t
DBImpl::PrioritizeWork(
    bool IsLevel0)
{
    int64_t start_time;
    bool again;
    int ret_val;
    struct timespec timeout;

    start_time=env_->NowMicros();

    // loop while on hold due to higher priority stuff,
    //  but keep polling for need to handle imm_
    do
    {
        again=false;

        if (has_imm_.NoBarrier_Load() != NULL) {
            mutex_.Lock();
            if (imm_ != NULL) {
                if (IsLevel0)
                    pthread_rwlock_unlock(&gThreadLock1);
                pthread_rwlock_rdlock(&gThreadLock0);
                CompactMemTable();
                pthread_rwlock_unlock(&gThreadLock0);
                if (IsLevel0)
                    pthread_rwlock_rdlock(&gThreadLock1);
                bg_cv_.SignalAll();  // Wakeup MakeRoomForWrite() if necessary
            }   // if
            mutex_.Unlock();
        }   // if

        // pause to potentially hand off disk to
        //  memtable threads
#if defined(_POSIX_TIMEOUTS) && (_POSIX_TIMEOUTS - 200112L) >= 0L
        clock_gettime(CLOCK_REALTIME, &timeout);
        timeout.tv_sec+=1;
        ret_val=pthread_rwlock_timedwrlock(&gThreadLock0, &timeout);
#else
        // ugly spin lock
        ret_val=pthread_rwlock_trywrlock(&gThreadLock0);
        if (EBUSY==ret_val)
        {
            ret_val=ETIMEDOUT;
            env_->SleepForMicroseconds(10000);  // 10milliseconds
        }   // if
#endif
        if (0==ret_val)
            pthread_rwlock_unlock(&gThreadLock0);
        again=(ETIMEDOUT==ret_val);

        // Give priorities to level 0 compactions, unless
        //  this compaction is blocking a level 0 in this database
        if (!IsLevel0 && level0_good && !again)
        {
#if defined(_POSIX_TIMEOUTS) && (_POSIX_TIMEOUTS - 200112L) >= 0L
            clock_gettime(CLOCK_REALTIME, &timeout);
            timeout.tv_sec+=1;
            ret_val=pthread_rwlock_timedwrlock(&gThreadLock1, &timeout);
#else
            // ugly spin lock
            ret_val=pthread_rwlock_trywrlock(&gThreadLock1);
            if (EBUSY==ret_val)
            {
                ret_val=ETIMEDOUT;
                env_->SleepForMicroseconds(10000);  // 10milliseconds
            }   // if
#endif

            if (0==ret_val)
                pthread_rwlock_unlock(&gThreadLock1);
            again=again || (ETIMEDOUT==ret_val);
        }   // if
    } while(again);

    // let caller know how long was spent waiting.
    return(env_->NowMicros() - start_time);

}  // PrioritizeWork



namespace {
struct IterState {
  port::Mutex* mu;
  Version* version;
  MemTable* mem;
  MemTable* imm;
};

static void CleanupIteratorState(void* arg1, void* arg2) {
  IterState* state = reinterpret_cast<IterState*>(arg1);
  state->mu->Lock();
  state->mem->Unref();
  if (state->imm != NULL) state->imm->Unref();
  state->version->Unref();
  state->mu->Unlock();
  delete state;
}
}  // namespace

Iterator* DBImpl::NewInternalIterator(const ReadOptions& options,
                                      SequenceNumber* latest_snapshot) {
  IterState* cleanup = new IterState;
  mutex_.Lock();
  *latest_snapshot = versions_->LastSequence();

  // Collect together all needed child iterators
  std::vector<Iterator*> list;
  list.push_back(mem_->NewIterator());
  mem_->Ref();
  if (imm_ != NULL) {
    list.push_back(imm_->NewIterator());
    imm_->Ref();
  }
  versions_->current()->AddIterators(options, &list);
  Iterator* internal_iter =
      NewMergingIterator(&internal_comparator_, &list[0], list.size());
  versions_->current()->Ref();

  cleanup->mu = &mutex_;
  cleanup->mem = mem_;
  cleanup->imm = imm_;
  cleanup->version = versions_->current();
  internal_iter->RegisterCleanup(CleanupIteratorState, cleanup, NULL);

  mutex_.Unlock();
  return internal_iter;
}

Iterator* DBImpl::TEST_NewInternalIterator() {
  SequenceNumber ignored;
  return NewInternalIterator(ReadOptions(), &ignored);
}

int64_t DBImpl::TEST_MaxNextLevelOverlappingBytes() {
  MutexLock l(&mutex_);
  return versions_->MaxNextLevelOverlappingBytes();
}

Status DBImpl::Get(const ReadOptions& options,
                   const Slice& key,
                   std::string* value) {
  StringValue stringvalue(*value);
  return DBImpl::Get(options, key, &stringvalue);
}

Status DBImpl::Get(const ReadOptions& options,
                   const Slice& key,
                   Value* value) {
  Status s;
  MutexLock l(&mutex_);
  SequenceNumber snapshot;
  if (options.snapshot != NULL) {
    snapshot = reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_;
  } else {
    snapshot = versions_->LastSequence();
  }

  MemTable* mem = mem_;
  MemTable* imm = imm_;
  Version* current = versions_->current();
  mem->Ref();
  if (imm != NULL) imm->Ref();
  current->Ref();

  bool have_stat_update = false;
  Version::GetStats stats;

  // Unlock while reading from files and memtables
  {
    mutex_.Unlock();
    // First look in the memtable, then in the immutable memtable (if any).
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {
      // Done
        gPerfCounters->Inc(ePerfGetMem);
    } else if (imm != NULL && imm->Get(lkey, value, &s)) {
      // Done
        gPerfCounters->Inc(ePerfGetImm);
    } else {
      s = current->Get(options, lkey, value, &stats);
      have_stat_update = true;
      gPerfCounters->Inc(ePerfGetVersion);
    }
    mutex_.Lock();
  }

  if (have_stat_update && current->UpdateStats(stats)) {
      // no compactions initiated by reads, takes too long
      // MaybeScheduleCompaction();
  }
  mem->Unref();
  if (imm != NULL) imm->Unref();
  current->Unref();

  gPerfCounters->Inc(ePerfApiGet);

  return s;
}

Iterator* DBImpl::NewIterator(const ReadOptions& options) {
  SequenceNumber latest_snapshot;
  Iterator* internal_iter = NewInternalIterator(options, &latest_snapshot);
  gPerfCounters->Inc(ePerfIterNew);
  return NewDBIterator(
      &dbname_, env_, user_comparator(), internal_iter,
      (options.snapshot != NULL
       ? reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_
       : latest_snapshot));
}

const Snapshot* DBImpl::GetSnapshot() {
  MutexLock l(&mutex_);
  return snapshots_.New(versions_->LastSequence());
}

void DBImpl::ReleaseSnapshot(const Snapshot* s) {
  MutexLock l(&mutex_);
  snapshots_.Delete(reinterpret_cast<const SnapshotImpl*>(s));
}

// Convenience methods
Status DBImpl::Put(const WriteOptions& o, const Slice& key, const Slice& val) {
  return DB::Put(o, key, val);
}

Status DBImpl::Delete(const WriteOptions& options, const Slice& key) {
  return DB::Delete(options, key);
}

Status DBImpl::Write(const WriteOptions& options, WriteBatch* my_batch) {
  Status status;
  int throttle(0);

  Writer w(&mutex_);
  w.batch = my_batch;
  w.sync = options.sync;
  w.done = false;

  {  // place mutex_ within a block
     //  not changing tabs to ease compare to Google sources
  MutexLock l(&mutex_);
  writers_.push_back(&w);
  while (!w.done && &w != writers_.front()) {
    w.cv.Wait();
  }
  if (w.done) {
    return w.status;  // skips throttle ... maintenance unfriendly coding, bastards
  }

  // May temporarily unlock and wait.
  status = MakeRoomForWrite(my_batch == NULL);
  uint64_t last_sequence = versions_->LastSequence();
  Writer* last_writer = &w;
  if (status.ok() && my_batch != NULL) {  // NULL batch is for compactions
    WriteBatch* updates = BuildBatchGroup(&last_writer);
    WriteBatchInternal::SetSequence(updates, last_sequence + 1);
    last_sequence += WriteBatchInternal::Count(updates);

    // Add to log and apply to memtable.  We can release the lock
    // during this phase since &w is currently responsible for logging
    // and protects against concurrent loggers and concurrent writes
    // into mem_.
    {
      mutex_.Unlock();
      status = log_->AddRecord(WriteBatchInternal::Contents(updates));
      if (status.ok() && options.sync) {
        status = logfile_->Sync();
      }
      if (status.ok()) {
        status = WriteBatchInternal::InsertInto(updates, mem_);
      }
      mutex_.Lock();
    }
    if (updates == tmp_batch_) tmp_batch_->Clear();

    versions_->SetLastSequence(last_sequence);
  }

  while (true) {
    Writer* ready = writers_.front();
    writers_.pop_front();
    if (ready != &w) {
      ready->status = status;
      ready->done = true;
      ready->cv.Signal();
    }
    if (ready == last_writer) break;
  }

  // Notify new head of write queue
  if (!writers_.empty()) {
    writers_.front()->cv.Signal();
  }

  gPerfCounters->Inc(ePerfApiWrite);

  // protect use of versions_ ... still within scope of mutex_ lock
  throttle=versions_->WriteThrottleUsec(bg_compaction_scheduled_);
  }  // release  MutexLock l(&mutex_)

  // throttle on exit to reduce possible reordering
  if (0!=throttle)
  {
      /// slowing each call down sequentially
      MutexLock l(&throttle_mutex_);

      // throttle is per key write, how many in batch?
      //  (batch multiplier killed AAE, removed)
      env_->SleepForMicroseconds(throttle /* * WriteBatchInternal::Count(my_batch)*/);
      gPerfCounters->Add(ePerfDebug0, throttle);<commit_msg>two one-line changes (throttle related):  remove 1.3 hack to not count keys in write batch for throttle (AAE no longer needs and 2i suffers with it), and remove imm_micros from SetThrottleRate() since everything is overthrottling at this point (was needed to help 1.3)<commit_after>// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "db/db_impl.h"

#include <time.h>
#include <algorithm>
#include <errno.h>
#include <set>
#include <string>
#include <stdint.h>
#include <stdio.h>
#include <unistd.h>
#include <vector>
#include "db/builder.h"
#include "db/db_iter.h"
#include "db/dbformat.h"
#include "db/filename.h"
#include "db/log_reader.h"
#include "db/log_writer.h"
#include "db/memtable.h"
#include "db/table_cache.h"
#include "db/version_set.h"
#include "db/write_batch_internal.h"
#include "leveldb/db.h"
#include "leveldb/env.h"
#include "leveldb/status.h"
#include "leveldb/table.h"
#include "leveldb/table_builder.h"
#include "port/port.h"
#include "table/block.h"
#include "table/merger.h"
#include "table/two_level_iterator.h"
#include "util/coding.h"
#include "util/logging.h"
#include "util/mutexlock.h"
#include "util/throttle.h"
#include "leveldb/perf_count.h"

#define __STDC_FORMAT_MACROS
#include <inttypes.h>

namespace leveldb {

// Information kept for every waiting writer
struct DBImpl::Writer {
  Status status;
  WriteBatch* batch;
  bool sync;
  bool done;
  port::CondVar cv;

  explicit Writer(port::Mutex* mu) : cv(mu) { }
};

struct DBImpl::CompactionState {
  Compaction* const compaction;

  // Sequence numbers < smallest_snapshot are not significant since we
  // will never have to service a snapshot below smallest_snapshot.
  // Therefore if we have seen a sequence number S <= smallest_snapshot,
  // we can drop all entries for the same key with sequence numbers < S.
  SequenceNumber smallest_snapshot;

  // Files produced by compaction
  struct Output {
    uint64_t number;
    uint64_t file_size;
    InternalKey smallest, largest;
  };
  std::vector<Output> outputs;

  // State kept for output being generated
  WritableFile* outfile;
  TableBuilder* builder;

  uint64_t total_bytes;
  uint64_t num_entries;

  Output* current_output() { return &outputs[outputs.size()-1]; }

  explicit CompactionState(Compaction* c)
      : compaction(c),
        outfile(NULL),
        builder(NULL),
        total_bytes(0),
        num_entries(0) {
  }
};

Value::~Value() {}

class StringValue : public Value {
 public:
  explicit StringValue(std::string& val) : value_(val) {}
  ~StringValue() {}

  StringValue& assign(const char* data, size_t size) {
    value_.assign(data, size);
    return *this;
  }

 private:
  std::string& value_;
};

// Fix user-supplied options to be reasonable
template <class T,class V>
static void ClipToRange(T* ptr, V minvalue, V maxvalue) {
  if (static_cast<V>(*ptr) > maxvalue) *ptr = maxvalue;
  if (static_cast<V>(*ptr) < minvalue) *ptr = minvalue;
}

Options SanitizeOptions(const std::string& dbname,
                        const InternalKeyComparator* icmp,
                        const InternalFilterPolicy* ipolicy,
                        const Options& src) {
  Options result = src;
  result.comparator = icmp;
  result.filter_policy = (src.filter_policy != NULL) ? ipolicy : NULL;
  ClipToRange(&result.max_open_files,            20,     50000);
  ClipToRange(&result.write_buffer_size,         64<<10, 1<<30);
  ClipToRange(&result.block_size,                1<<10,  4<<20);
  if (result.info_log == NULL) {
    // Open a log file in the same directory as the db
    src.env->CreateDir(dbname);  // In case it does not exist
    src.env->RenameFile(InfoLogFileName(dbname), OldInfoLogFileName(dbname));
    Status s = src.env->NewLogger(InfoLogFileName(dbname), &result.info_log);
    if (!s.ok()) {
      // No place suitable for logging
      result.info_log = NULL;
    }
  }
  if (result.block_cache == NULL) {
    result.block_cache = NewLRUCache(8 << 20);
  }
  return result;
}

DBImpl::DBImpl(const Options& options, const std::string& dbname)
    : env_(options.env),
      internal_comparator_(options.comparator),
      internal_filter_policy_(options.filter_policy),
      options_(SanitizeOptions(
          dbname, &internal_comparator_, &internal_filter_policy_, options)),
      owns_info_log_(options_.info_log != options.info_log),
      owns_cache_(options_.block_cache != options.block_cache),
      dbname_(dbname),
      db_lock_(NULL),
      shutting_down_(NULL),
      bg_cv_(&mutex_),
      mem_(new MemTable(internal_comparator_)),
      imm_(NULL),
      logfile_(NULL),
      logfile_number_(0),
      log_(NULL),
      tmp_batch_(new WriteBatch),
      bg_compaction_scheduled_(false),
      manual_compaction_(NULL),
      level0_good(true)
{
  mem_->Ref();
  has_imm_.Release_Store(NULL);

  // Reserve ten files or so for other uses and give the rest to TableCache.
  const int table_cache_size = options_.max_open_files - 10;
  table_cache_ = new TableCache(dbname_, &options_, table_cache_size);

  versions_ = new VersionSet(dbname_, &options_, table_cache_,
                             &internal_comparator_);

  options_.Dump(options_.info_log);
}

DBImpl::~DBImpl() {
  // Wait for background work to finish
  mutex_.Lock();
  shutting_down_.Release_Store(this);  // Any non-NULL value is ok
  while (bg_compaction_scheduled_) {
    bg_cv_.Wait();
  }
  mutex_.Unlock();

  delete versions_;
  if (mem_ != NULL) mem_->Unref();
  if (imm_ != NULL) imm_->Unref();
  delete tmp_batch_;
  delete log_;
  delete logfile_;
  delete table_cache_;

  if (owns_info_log_) {
    delete options_.info_log;
  }
  if (owns_cache_) {
    delete options_.block_cache;
  }
  if (db_lock_ != NULL) {
    env_->UnlockFile(db_lock_);
  }
}

Status DBImpl::NewDB() {
  VersionEdit new_db;
  new_db.SetComparatorName(user_comparator()->Name());
  new_db.SetLogNumber(0);
  new_db.SetNextFile(2);
  new_db.SetLastSequence(0);

  const std::string manifest = DescriptorFileName(dbname_, 1);
  WritableFile* file;
  Status s = env_->NewWritableFile(manifest, &file);
  if (!s.ok()) {
    return s;
  }
  {
    log::Writer log(file);
    std::string record;
    new_db.EncodeTo(&record);
    s = log.AddRecord(record);
    if (s.ok()) {
      s = file->Close();
    }
  }
  delete file;
  if (s.ok()) {
    // Make "CURRENT" file that points to the new manifest file.
    s = SetCurrentFile(env_, dbname_, 1);
  } else {
    env_->DeleteFile(manifest);
  }

  return s;
}

void DBImpl::MaybeIgnoreError(Status* s) const {
  if (s->ok() || options_.paranoid_checks) {
    // No change needed
  } else {
    Log(options_.info_log, "Ignoring error %s", s->ToString().c_str());
    *s = Status::OK();
  }
}

void DBImpl::DeleteObsoleteFiles() {
  // Make a set of all of the live files
  std::set<uint64_t> live = pending_outputs_;
  versions_->AddLiveFiles(&live);

  // prune the database root directory
  std::vector<std::string> filenames;
  env_->GetChildren(dbname_, &filenames); // Ignoring errors on purpose
  for (size_t i = 0; i < filenames.size(); i++) {
      KeepOrDelete(filenames[i], -1, live);
  }   // for

  // prune the table file directories
  for (int level=0; level<config::kNumLevels; ++level)
  {
      std::string dirname;

      filenames.clear();
      dirname=MakeDirName2(dbname_, level, "sst");
      env_->GetChildren(dirname, &filenames); // Ignoring errors on purpose
      for (size_t i = 0; i < filenames.size(); i++) {
          KeepOrDelete(filenames[i], level, live);
      }   // for
  }   // for
}

void
DBImpl::KeepOrDelete(
    const std::string & Filename,
    int Level,
    const std::set<uint64_t> & Live)
{
  uint64_t number;
  FileType type;
  bool keep = true;

  if (ParseFileName(Filename, &number, &type))
  {
      switch (type)
      {
          case kLogFile:
              keep = ((number >= versions_->LogNumber()) ||
                      (number == versions_->PrevLogNumber()));
              break;

          case kDescriptorFile:
              // Keep my manifest file, and any newer incarnations'
              // (in case there is a race that allows other incarnations)
              keep = (number >= versions_->ManifestFileNumber());
              break;

          case kTableFile:
              keep = (Live.find(number) != Live.end());
              break;

          case kTempFile:
              // Any temp files that are currently being written to must
              // be recorded in pending_outputs_, which is inserted into "Live"
              keep = (Live.find(number) != Live.end());
          break;

          case kCurrentFile:
          case kDBLockFile:
          case kInfoLogFile:
              keep = true;
              break;
      }   // switch

      if (!keep)
      {
          if (type == kTableFile) {
              // temporary hard coding of extra overlapped
              //  levels
              table_cache_->Evict(number, (Level<config::kNumOverlapLevels));
          }
          Log(options_.info_log, "Delete type=%d #%lld\n",
              int(type),
              static_cast<unsigned long long>(number));
          if (-1!=Level)
          {
              std::string file;

              file=TableFileName(dbname_, number, Level);
              env_->DeleteFile(file);
          }   // if
          else
          {
              env_->DeleteFile(dbname_ + "/" + Filename);
          }   // else
      }   // if
  }   // if
} // DBImpl::KeepOrDelete


Status DBImpl::Recover(VersionEdit* edit) {
  mutex_.AssertHeld();

  // Ignore error from CreateDir since the creation of the DB is
  // committed only when the descriptor is created, and this directory
  // may already exist from a previous failed creation attempt.
  env_->CreateDir(dbname_);
  assert(db_lock_ == NULL);
  Status s = env_->LockFile(LockFileName(dbname_), &db_lock_);
  if (!s.ok()) {
    return s;
  }

  if (!env_->FileExists(CurrentFileName(dbname_))) {
    if (options_.create_if_missing) {
      s = NewDB();
      if (!s.ok()) {
        return s;
      }
    } else {
      return Status::InvalidArgument(
          dbname_, "does not exist (create_if_missing is false)");
    }
  } else {
    if (options_.error_if_exists) {
      return Status::InvalidArgument(
          dbname_, "exists (error_if_exists is true)");
    }
  }

  // read manifest
  s = versions_->Recover();

  // Verify Riak 1.3 directory structure created and ready
  if (s.ok() && !TestForLevelDirectories(env_, dbname_, versions_->current()))
  {
      int level;
      std::string old_name, new_name;

      if (options_.create_if_missing)
      {
          // move files from old heirarchy to new
          s=MakeLevelDirectories(env_, dbname_);
          if (s.ok())
          {
              for (level=0; level<config::kNumLevels && s.ok(); ++level)
              {
                  const std::vector<FileMetaData*> & level_files(versions_->current()->GetFileList(level));
                  std::vector<FileMetaData*>::const_iterator it;

                  for (it=level_files.begin(); level_files.end()!=it && s.ok(); ++it)
                  {
                      new_name=TableFileName(dbname_, (*it)->number, level);

                      // test for partial completion
                      if (!env_->FileExists(new_name.c_str()))
                      {
                          old_name=TableFileName(dbname_, (*it)->number, -2);
                          s=env_->RenameFile(old_name, new_name);
                      }   // if
                  }   // for
              }   // for
          }   // if
          else
              return s;
      }   // if
      else
      {
          return Status::InvalidArgument(
              dbname_, "level directories do not exist (create_if_missing is false)");
      }   // else

  }   // if


  if (s.ok()) {
    SequenceNumber max_sequence(0);

    // Recover from all newer log files than the ones named in the
    // descriptor (new log files may have been added by the previous
    // incarnation without registering them in the descriptor).
    //
    // Note that PrevLogNumber() is no longer used, but we pay
    // attention to it in case we are recovering a database
    // produced by an older version of leveldb.
    const uint64_t min_log = versions_->LogNumber();
    const uint64_t prev_log = versions_->PrevLogNumber();
    std::vector<std::string> filenames;
    s = env_->GetChildren(dbname_, &filenames);
    if (!s.ok()) {
      return s;
    }
    uint64_t number;
    FileType type;
    std::vector<uint64_t> logs;
    for (size_t i = 0; i < filenames.size(); i++) {
      if (ParseFileName(filenames[i], &number, &type)
          && type == kLogFile
          && ((number >= min_log) || (number == prev_log))) {
        logs.push_back(number);
      }
    }

    // Recover in the order in which the logs were generated
    std::sort(logs.begin(), logs.end());
    for (size_t i = 0; i < logs.size(); i++) {
      s = RecoverLogFile(logs[i], edit, &max_sequence);

      // The previous incarnation may not have written any MANIFEST
      // records after allocating this log number.  So we manually
      // update the file number allocation counter in VersionSet.
      versions_->MarkFileNumberUsed(logs[i]);
    }

    if (s.ok()) {
      if (versions_->LastSequence() < max_sequence) {
        versions_->SetLastSequence(max_sequence);
      }
    }
  }

  return s;
}


void DBImpl::CheckCompactionState()
{
    mutex_.AssertHeld();
    bool log_flag, need_compaction;

    // Verify Riak 1.4 level sizing, run compactions to fix as necessary
    //  (also recompacts hard repair of all files to level 0)

    log_flag=false;
    need_compaction=false;

    // loop on pending background compactions
    //  reminder: mutex_ is held
    do
    {
        int level;

        // wait out executing compaction (Wait gives mutex to compactions)
        if (bg_compaction_scheduled_)
            bg_cv_.Wait();

        for (level=0, need_compaction=false;
             level<config::kNumLevels && !need_compaction;
             ++level)
        {
            if (versions_->IsLevelOverlapped(level)
                && config::kL0_SlowdownWritesTrigger<=versions_->NumLevelFiles(level))
            {
                need_compaction=true;
                MaybeScheduleCompaction();
                if (!log_flag)
                {
                    log_flag=true;
                    Log(options_.info_log, "Cleanup compactions started ... DB::Open paused");
                }   // if
            }   //if
        }   // for

    } while(bg_compaction_scheduled_ && need_compaction);

    if (log_flag)
        Log(options_.info_log, "Cleanup compactions completed ... DB::Open continuing");

    // prior code only called this function instead of CheckCompactionState
    //  (duplicates original Google functionality)
    else
        MaybeScheduleCompaction();

    return;

}  // DBImpl::CheckCompactionState()


Status DBImpl::RecoverLogFile(uint64_t log_number,
                              VersionEdit* edit,
                              SequenceNumber* max_sequence) {
  struct LogReporter : public log::Reader::Reporter {
    Env* env;
    Logger* info_log;
    const char* fname;
    Status* status;  // NULL if options_.paranoid_checks==false
    virtual void Corruption(size_t bytes, const Status& s) {
      Log(info_log, "%s%s: dropping %d bytes; %s",
          (this->status == NULL ? "(ignoring error) " : ""),
          fname, static_cast<int>(bytes), s.ToString().c_str());
      if (this->status != NULL && this->status->ok()) *this->status = s;
    }
  };

  mutex_.AssertHeld();

  // Open the log file
  std::string fname = LogFileName(dbname_, log_number);
  SequentialFile* file;
  Status status = env_->NewSequentialFile(fname, &file);
  if (!status.ok()) {
    MaybeIgnoreError(&status);
    return status;
  }

  // Create the log reader.
  LogReporter reporter;
  reporter.env = env_;
  reporter.info_log = options_.info_log;
  reporter.fname = fname.c_str();
  reporter.status = (options_.paranoid_checks ? &status : NULL);
  // We intentially make log::Reader do checksumming even if
  // paranoid_checks==false so that corruptions cause entire commits
  // to be skipped instead of propagating bad information (like overly
  // large sequence numbers).
  log::Reader reader(file, &reporter, true/*checksum*/,
                     0/*initial_offset*/);
  Log(options_.info_log, "Recovering log #%llu",
      (unsigned long long) log_number);

  // Read all the records and add to a memtable
  std::string scratch;
  Slice record;
  WriteBatch batch;
  MemTable* mem = NULL;
  while (reader.ReadRecord(&record, &scratch) &&
         status.ok()) {
    if (record.size() < 12) {
      reporter.Corruption(
          record.size(), Status::Corruption("log record too small"));
      continue;
    }
    WriteBatchInternal::SetContents(&batch, record);

    if (mem == NULL) {
      mem = new MemTable(internal_comparator_);
      mem->Ref();
    }
    status = WriteBatchInternal::InsertInto(&batch, mem);
    MaybeIgnoreError(&status);
    if (!status.ok()) {
      break;
    }
    const SequenceNumber last_seq =
        WriteBatchInternal::Sequence(&batch) +
        WriteBatchInternal::Count(&batch) - 1;
    if (last_seq > *max_sequence) {
      *max_sequence = last_seq;
    }

    if (mem->ApproximateMemoryUsage() > options_.write_buffer_size) {
      status = WriteLevel0Table(mem, edit, NULL);
      if (!status.ok()) {
        // Reflect errors immediately so that conditions like full
        // file-systems cause the DB::Open() to fail.
        break;
      }
      mem->Unref();
      mem = NULL;
    }
  }

  if (status.ok() && mem != NULL) {
    status = WriteLevel0Table(mem, edit, NULL);
    // Reflect errors immediately so that conditions like full
    // file-systems cause the DB::Open() to fail.
  }

  if (mem != NULL) mem->Unref();
  delete file;
  return status;
}

Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit,
                                Version* base) {
  mutex_.AssertHeld();
  const uint64_t start_micros = env_->NowMicros();
  FileMetaData meta;
  meta.number = versions_->NewFileNumber();
  meta.level = 0;
  pending_outputs_.insert(meta.number);
  Iterator* iter = mem->NewIterator();
  SequenceNumber smallest_snapshot;
  Log(options_.info_log, "Level-0 table #%llu: started",
      (unsigned long long) meta.number);

  if (snapshots_.empty()) {
    smallest_snapshot = versions_->LastSequence();
  } else {
    smallest_snapshot = snapshots_.oldest()->number_;
  }

  Status s;
  {
    Options local_options;

    mutex_.Unlock();

    // want the data slammed to disk as fast as possible,
    //  no compression for level 0.
    local_options=options_;
    local_options.compression=kNoCompression;
    s = BuildTable(dbname_, env_, local_options, user_comparator(), table_cache_, iter, &meta, smallest_snapshot);

    mutex_.Lock();
  }

  Log(options_.info_log, "Level-0 table #%llu: %llu bytes, %llu keys %s",
      (unsigned long long) meta.number,
      (unsigned long long) meta.file_size,
      (unsigned long long) meta.num_entries,
      s.ToString().c_str());
  delete iter;
  pending_outputs_.erase(meta.number);


  // Note that if file_size is zero, the file has been deleted and
  // should not be added to the manifest.
  int level = 0;
  if (s.ok() && meta.file_size > 0) {
    const Slice min_user_key = meta.smallest.user_key();
    const Slice max_user_key = meta.largest.user_key();
    if (base != NULL) {
        level = base->PickLevelForMemTableOutput(min_user_key, max_user_key);
        if (0!=level)
        {
            std::string old_name, new_name;

            old_name=TableFileName(dbname_, meta.number, 0);
            new_name=TableFileName(dbname_, meta.number, level);
            s=env_->RenameFile(old_name, new_name);
        }   // if
    }

    if (s.ok())
        edit->AddFile(level, meta.number, meta.file_size,
                      meta.smallest, meta.largest);
  }

  CompactionStats stats;
  stats.micros = env_->NowMicros() - start_micros;
  stats.bytes_written = meta.file_size;
  stats_[level].Add(stats);

  if (0!=meta.num_entries && s.ok())
  {
      // This SetWriteRate() call removed because this thread
      //  has priority (others blocked on mutex) and thus created
      //  misleading estimates of disk write speed
      // 2x since mem to disk, not disk to disk
      //      env_->SetWriteRate(2*stats.micros/meta.num_entries);
      // 2x since mem to disk, not disk to disk
      // env_->SetWriteRate(2*stats.micros/meta.num_entries);
  }   // if

  return s;
}

Status DBImpl::CompactMemTable() {
  mutex_.AssertHeld();
  assert(imm_ != NULL);

  // Save the contents of the memtable as a new Table
  VersionEdit edit;
  Version* base = versions_->current();
  base->Ref();
  Status s = WriteLevel0Table(imm_, &edit, base);
  base->Unref();

  if (s.ok() && shutting_down_.Acquire_Load()) {
    s = Status::IOError("Deleting DB during memtable compaction");
  }

  // Replace immutable memtable with the generated Table
  if (s.ok()) {
    edit.SetPrevLogNumber(0);
    edit.SetLogNumber(logfile_number_);  // Earlier logs no longer needed
    s = versions_->LogAndApply(&edit, &mutex_);
  }

  if (s.ok()) {
    // Commit to the new state
    imm_->Unref();
    imm_ = NULL;
    has_imm_.Release_Store(NULL);
    DeleteObsoleteFiles();
  }

  return s;
}

void DBImpl::CompactRange(const Slice* begin, const Slice* end) {
  int max_level_with_files = 1;
  {
    MutexLock l(&mutex_);
    Version* base = versions_->current();
    for (int level = 1; level < config::kNumLevels; level++) {
      if (base->OverlapInLevel(level, begin, end)) {
        max_level_with_files = level;
      }
    }
  }
  TEST_CompactMemTable(); // TODO(sanjay): Skip if memtable does not overlap
  for (int level = 0; level < max_level_with_files; level++) {
    TEST_CompactRange(level, begin, end);
  }
}

void DBImpl::TEST_CompactRange(int level, const Slice* begin,const Slice* end) {
  assert(level >= 0);
  assert(level + 1 < config::kNumLevels);

  InternalKey begin_storage, end_storage;

  ManualCompaction manual;
  manual.level = level;
  manual.done = false;
  if (begin == NULL) {
    manual.begin = NULL;
  } else {
    begin_storage = InternalKey(*begin, kMaxSequenceNumber, kValueTypeForSeek);
    manual.begin = &begin_storage;
  }
  if (end == NULL) {
    manual.end = NULL;
  } else {
    end_storage = InternalKey(*end, 0, static_cast<ValueType>(0));
    manual.end = &end_storage;
  }

  MutexLock l(&mutex_);
  while (!manual.done) {
    while (manual_compaction_ != NULL || bg_compaction_scheduled_) {
      bg_cv_.Wait();
    }
    manual_compaction_ = &manual;
    MaybeScheduleCompaction();
    while (manual_compaction_ == &manual) {
      bg_cv_.Wait();
    }
  }
}

Status DBImpl::TEST_CompactMemTable() {
  // NULL batch means just wait for earlier writes to be done
  Status s = Write(WriteOptions(), NULL);
  if (s.ok()) {
    // Wait until the compaction completes
    MutexLock l(&mutex_);
    while (imm_ != NULL && bg_error_.ok()) {
      bg_cv_.Wait();
    }
    if (imm_ != NULL) {
      s = bg_error_;
    }
  }
  return s;
}

void DBImpl::MaybeScheduleCompaction() {
  mutex_.AssertHeld();

  int state, priority;
  bool push;

  // decide which background thread gets the compaction job
  state=0;
  priority=0;
  push=false;

  // writing of memory to disk: high priority
  if (NULL!=imm_)
  {
      push=true;
  }   // if

  // merge level 0s to level 1
  else
  {
      Compaction * c_ptr;
      c_ptr=versions_->PickCompaction();

      // compaction of level 0 files:  high priority
      if (NULL!=c_ptr && c_ptr->level()==0)
      {
          push=true;
          priority=versions_->NumLevelFiles(0);
      }   // if
      else
      {
          priority=versions_->current()->WritePenalty();
      }   // else

      delete c_ptr;
  }   // if

  if (push)
  {
      // is something else already on background work queue
      if (bg_compaction_scheduled_)
          state=2;
      else
          state=1;
  }   // if


  if (bg_compaction_scheduled_ && !push) {
    // Already scheduled
  } else if (shutting_down_.Acquire_Load()) {
    // DB is being deleted; no more background compactions
  } else if (imm_ == NULL &&
             manual_compaction_ == NULL &&
             !versions_->NeedsCompaction()) {
    // No work to be done
  } else {
    bg_compaction_scheduled_ = true;
    env_->Schedule(&DBImpl::BGWork, this, state, (NULL!=imm_), priority);
  }
}

void DBImpl::BGWork(void* db) {
  reinterpret_cast<DBImpl*>(db)->BackgroundCall();
}

void DBImpl::BackgroundCall() {
  MutexLock l(&mutex_);
  assert(bg_compaction_scheduled_);
  if (!shutting_down_.Acquire_Load()) {
    Status s = BackgroundCompaction();
    if (!s.ok()) {
      // Wait a little bit before retrying background compaction in
      // case this is an environmental problem and we do not want to
      // chew up resources for failed compactions for the duration of
      // the problem.
      bg_cv_.SignalAll();  // In case a waiter can proceed despite the error
      Log(options_.info_log, "Waiting after background compaction error: %s",
          s.ToString().c_str());
      mutex_.Unlock();
      env_->SleepForMicroseconds(1000000);
      mutex_.Lock();
    }
  }
  bg_compaction_scheduled_ = false;

  // Previous compaction may have produced too many files in a level,
  // so reschedule another compaction if needed.
  if (!options_.is_repair)
      MaybeScheduleCompaction();
  bg_cv_.SignalAll();
}

Status DBImpl::BackgroundCompaction() {
  Status status;

  mutex_.AssertHeld();

  if (imm_ != NULL) {
    pthread_rwlock_rdlock(&gThreadLock0);
    status=CompactMemTable();
    pthread_rwlock_unlock(&gThreadLock0);
    return status;
  }

  Compaction* c;
  bool is_manual = (manual_compaction_ != NULL);
  InternalKey manual_end;
  if (is_manual) {
    ManualCompaction* m = manual_compaction_;
    c = versions_->CompactRange(m->level, m->begin, m->end);
    m->done = (c == NULL);
    if (c != NULL) {
      manual_end = c->input(0, c->num_input_files(0) - 1)->largest;
    }
    Log(options_.info_log,
        "Manual compaction at level-%d from %s .. %s; will stop at %s\n",
        m->level,
        (m->begin ? m->begin->DebugString().c_str() : "(begin)"),
        (m->end ? m->end->DebugString().c_str() : "(end)"),
        (m->done ? "(end)" : manual_end.DebugString().c_str()));
  } else {
    c = versions_->PickCompaction();
  }


  if (c == NULL) {
    // Nothing to do
  } else if (!is_manual && c->IsTrivialMove()) {
    // Move file to next level
    assert(c->num_input_files(0) == 1);
    std::string old_name, new_name;
    FileMetaData* f = c->input(0, 0);

    old_name=TableFileName(dbname_, f->number, c->level());
    new_name=TableFileName(dbname_, f->number, c->level() +1);
    status=env_->RenameFile(old_name, new_name);

    if (status.ok())
    {
        c->edit()->DeleteFile(c->level(), f->number);
        c->edit()->AddFile(c->level() + 1, f->number, f->file_size,
                           f->smallest, f->largest);
        status = versions_->LogAndApply(c->edit(), &mutex_);

        // if LogAndApply fails, should file be renamed back to original spot?
        VersionSet::LevelSummaryStorage tmp;
        Log(options_.info_log, "Moved #%lld to level-%d %lld bytes %s: %s\n",
            static_cast<unsigned long long>(f->number),
            c->level() + 1,
            static_cast<unsigned long long>(f->file_size),
            status.ToString().c_str(),
            versions_->LevelSummary(&tmp));
    }  // if
  } else {
    CompactionState* compact = new CompactionState(c);
    status = DoCompactionWork(compact);
    CleanupCompaction(compact);
    c->ReleaseInputs();
    DeleteObsoleteFiles();
  }
  delete c;

  if (status.ok()) {
    // Done
  } else if (shutting_down_.Acquire_Load()) {
    // Ignore compaction errors found during shutting down
  } else {
    Log(options_.info_log,
        "Compaction error: %s", status.ToString().c_str());
    if (options_.paranoid_checks && bg_error_.ok()) {
      bg_error_ = status;
    }
  }

  if (is_manual) {
    ManualCompaction* m = manual_compaction_;
    if (!status.ok()) {
      m->done = true;
    }
    if (!m->done) {
      // We only compacted part of the requested range.  Update *m
      // to the range that is left to be compacted.
      m->tmp_storage = manual_end;
      m->begin = &m->tmp_storage;
    }
    manual_compaction_ = NULL;
  }

  return status;
}

void DBImpl::CleanupCompaction(CompactionState* compact) {
  mutex_.AssertHeld();
  if (compact->builder != NULL) {
    // May happen if we get a shutdown call in the middle of compaction
    compact->builder->Abandon();
    delete compact->builder;
  } else {
    assert(compact->outfile == NULL);
  }
  delete compact->outfile;
  for (size_t i = 0; i < compact->outputs.size(); i++) {
    const CompactionState::Output& out = compact->outputs[i];
    pending_outputs_.erase(out.number);
  }
  delete compact;
}

Status DBImpl::OpenCompactionOutputFile(CompactionState* compact) {
  assert(compact != NULL);
  assert(compact->builder == NULL);
  uint64_t file_number;
  {
    mutex_.Lock();
    file_number = versions_->NewFileNumber();
    pending_outputs_.insert(file_number);
    CompactionState::Output out;
    out.number = file_number;
    out.smallest.Clear();
    out.largest.Clear();
    compact->outputs.push_back(out);
    mutex_.Unlock();
  }

  // Make the output file
  std::string fname = TableFileName(dbname_, file_number, compact->compaction->level()+1);
  Status s = env_->NewWritableFile(fname, &compact->outfile);
  if (s.ok()) {
    compact->builder = new TableBuilder(options_, compact->outfile);
  }
  return s;
}

Status DBImpl::FinishCompactionOutputFile(CompactionState* compact,
                                          Iterator* input) {
  assert(compact != NULL);
  assert(compact->outfile != NULL);
  assert(compact->builder != NULL);

  const uint64_t output_number = compact->current_output()->number;
  assert(output_number != 0);

  // Check for iterator errors
  Status s = input->status();
  const uint64_t current_entries = compact->builder->NumEntries();
  if (s.ok()) {
    s = compact->builder->Finish();
  } else {
    compact->builder->Abandon();
  }
  const uint64_t current_bytes = compact->builder->FileSize();
  compact->current_output()->file_size = current_bytes;
  compact->total_bytes += current_bytes;
  compact->num_entries += compact->builder->NumEntries();
  delete compact->builder;
  compact->builder = NULL;

  // Finish and check for file errors
  if (s.ok()) {
    s = compact->outfile->Sync();
  }
  if (s.ok()) {
    s = compact->outfile->Close();
  }
  delete compact->outfile;
  compact->outfile = NULL;

  if (s.ok() && current_entries > 0) {
    // Verify that the table is usable
    Iterator* iter = table_cache_->NewIterator(ReadOptions(),
                                               output_number,
                                               current_bytes,
                                               compact->compaction->level()+1);
    s = iter->status();
    delete iter;
    if (s.ok()) {
      Log(options_.info_log,
          "Generated table #%llu: %lld keys, %lld bytes",
          (unsigned long long) output_number,
          (unsigned long long) current_entries,
          (unsigned long long) current_bytes);
    }
  }
  return s;
}


Status DBImpl::InstallCompactionResults(CompactionState* compact) {
  mutex_.AssertHeld();
  Log(options_.info_log,  "Compacted %d@%d + %d@%d files => %lld bytes",
      compact->compaction->num_input_files(0),
      compact->compaction->level(),
      compact->compaction->num_input_files(1),
      compact->compaction->level() + 1,
      static_cast<long long>(compact->total_bytes));

  // Add compaction outputs
  compact->compaction->AddInputDeletions(compact->compaction->edit());
  const int level = compact->compaction->level();
  for (size_t i = 0; i < compact->outputs.size(); i++) {
    const CompactionState::Output& out = compact->outputs[i];
    compact->compaction->edit()->AddFile(
        level + 1,
        out.number, out.file_size, out.smallest, out.largest);
  }
  return versions_->LogAndApply(compact->compaction->edit(), &mutex_);
}

Status DBImpl::DoCompactionWork(CompactionState* compact) {

  Log(options_.info_log,  "Compacting %d@%d + %d@%d files",
      compact->compaction->num_input_files(0),
      compact->compaction->level(),
      compact->compaction->num_input_files(1),
      compact->compaction->level() + 1);

  assert(versions_->NumLevelFiles(compact->compaction->level()) > 0);
  assert(compact->builder == NULL);
  assert(compact->outfile == NULL);
  if (snapshots_.empty()) {
    compact->smallest_snapshot = versions_->LastSequence();
  } else {
    compact->smallest_snapshot = snapshots_.oldest()->number_;
  }

  // Release mutex while we're actually doing the compaction work
  mutex_.Unlock();

  bool is_level0_compaction=(0 == compact->compaction->level());

  if (is_level0_compaction)
      pthread_rwlock_rdlock(&gThreadLock1);

  const uint64_t start_micros = env_->NowMicros();
  int64_t imm_micros = 0;  // Micros spent doing imm_ compactions


  Iterator* input = versions_->MakeInputIterator(compact->compaction);
  input->SeekToFirst();
  Status status;
  ParsedInternalKey ikey;
  std::string current_user_key;

  KeyRetirement retire(user_comparator(), compact->smallest_snapshot, compact->compaction);

  for (; input->Valid() && !shutting_down_.Acquire_Load(); )
  {
    // Prioritize compaction work ... every 100 keys
    if (NULL==compact->builder
	|| 0==(compact->builder->NumEntries() % 100))
      imm_micros+=PrioritizeWork(is_level0_compaction);

    Slice key = input->key();
    if (compact->builder != NULL
        && compact->compaction->ShouldStopBefore(key, compact->builder->NumEntries())) {

      status = FinishCompactionOutputFile(compact, input);
      if (!status.ok()) {
        break;
      }
    }

    // Handle key/value, add to state, etc.
    bool drop = retire(key);

    if (!drop) {
      // Open output file if necessary
      if (compact->builder == NULL) {
        status = OpenCompactionOutputFile(compact);
        if (!status.ok()) {
          break;
        }
      }
      if (compact->builder->NumEntries() == 0) {
        compact->current_output()->smallest.DecodeFrom(key);
      }
      compact->current_output()->largest.DecodeFrom(key);
      compact->builder->Add(key, input->value());

      // update throttle ... now, end of compaction may be too late
      //   but not too often since NowMicros can be costly
      size_t entry_count;
      entry_count=compact->num_entries + compact->builder->NumEntries();

      // imm_micros intentional NOT removed from time calculation,
      //  gives better measure of overall activity / write overhead
      if (1==(entry_count % 1000) && 1000<entry_count)
      {
          // test for priority change
          if (!is_level0_compaction)
          {
              // raise this compaction's priority if it is blocking a
              //  dire compaction of level 0 files
              if ((int)config::kL0_SlowdownWritesTrigger < versions_->current()->NumFiles(0))
              {
                  pthread_rwlock_rdlock(&gThreadLock1);
                  is_level0_compaction=true;
              }   // if
          }   // if
      }   // if

      // Close output file if it is big enough
      if (compact->builder->FileSize() >=
          compact->compaction->MaxOutputFileSize()) {
        status = FinishCompactionOutputFile(compact, input);
        if (!status.ok()) {
          break;
        }
      }
    }

    input->Next();
  }

  if (status.ok() && shutting_down_.Acquire_Load()) {
    status = Status::IOError("Deleting DB during compaction");
  }
  if (status.ok() && compact->builder != NULL) {
    status = FinishCompactionOutputFile(compact, input);
  }
  if (status.ok()) {
    status = input->status();
  }
  delete input;
  input = NULL;

  CompactionStats stats;
  stats.micros = env_->NowMicros() - start_micros - imm_micros;
  for (int which = 0; which < 2; which++) {
    for (int i = 0; i < compact->compaction->num_input_files(which); i++) {
      stats.bytes_read += compact->compaction->input(which, i)->file_size;
    }
  }
  for (size_t i = 0; i < compact->outputs.size(); i++) {
    stats.bytes_written += compact->outputs[i].file_size;
  }

  if (is_level0_compaction)
      pthread_rwlock_unlock(&gThreadLock1);

  mutex_.Lock();
  stats_[compact->compaction->level() + 1].Add(stats);

  if (status.ok()) {
    if (0!=compact->num_entries)
        SetThrottleWriteRate((env_->NowMicros() - start_micros - imm_micros), compact->num_entries,
                            is_level0_compaction, env_->GetBackgroundBacklog());
    status = InstallCompactionResults(compact);
  }
  VersionSet::LevelSummaryStorage tmp;
  Log(options_.info_log,
      "compacted to: %s", versions_->LevelSummary(&tmp));
  return status;
}


int64_t
DBImpl::PrioritizeWork(
    bool IsLevel0)
{
    int64_t start_time;
    bool again;
    int ret_val;
    struct timespec timeout;

    start_time=env_->NowMicros();

    // loop while on hold due to higher priority stuff,
    //  but keep polling for need to handle imm_
    do
    {
        again=false;

        if (has_imm_.NoBarrier_Load() != NULL) {
            mutex_.Lock();
            if (imm_ != NULL) {
                if (IsLevel0)
                    pthread_rwlock_unlock(&gThreadLock1);
                pthread_rwlock_rdlock(&gThreadLock0);
                CompactMemTable();
                pthread_rwlock_unlock(&gThreadLock0);
                if (IsLevel0)
                    pthread_rwlock_rdlock(&gThreadLock1);
                bg_cv_.SignalAll();  // Wakeup MakeRoomForWrite() if necessary
            }   // if
            mutex_.Unlock();
        }   // if

        // pause to potentially hand off disk to
        //  memtable threads
#if defined(_POSIX_TIMEOUTS) && (_POSIX_TIMEOUTS - 200112L) >= 0L
        clock_gettime(CLOCK_REALTIME, &timeout);
        timeout.tv_sec+=1;
        ret_val=pthread_rwlock_timedwrlock(&gThreadLock0, &timeout);
#else
        // ugly spin lock
        ret_val=pthread_rwlock_trywrlock(&gThreadLock0);
        if (EBUSY==ret_val)
        {
            ret_val=ETIMEDOUT;
            env_->SleepForMicroseconds(10000);  // 10milliseconds
        }   // if
#endif
        if (0==ret_val)
            pthread_rwlock_unlock(&gThreadLock0);
        again=(ETIMEDOUT==ret_val);

        // Give priorities to level 0 compactions, unless
        //  this compaction is blocking a level 0 in this database
        if (!IsLevel0 && level0_good && !again)
        {
#if defined(_POSIX_TIMEOUTS) && (_POSIX_TIMEOUTS - 200112L) >= 0L
            clock_gettime(CLOCK_REALTIME, &timeout);
            timeout.tv_sec+=1;
            ret_val=pthread_rwlock_timedwrlock(&gThreadLock1, &timeout);
#else
            // ugly spin lock
            ret_val=pthread_rwlock_trywrlock(&gThreadLock1);
            if (EBUSY==ret_val)
            {
                ret_val=ETIMEDOUT;
                env_->SleepForMicroseconds(10000);  // 10milliseconds
            }   // if
#endif

            if (0==ret_val)
                pthread_rwlock_unlock(&gThreadLock1);
            again=again || (ETIMEDOUT==ret_val);
        }   // if
    } while(again);

    // let caller know how long was spent waiting.
    return(env_->NowMicros() - start_time);

}  // PrioritizeWork



namespace {
struct IterState {
  port::Mutex* mu;
  Version* version;
  MemTable* mem;
  MemTable* imm;
};

static void CleanupIteratorState(void* arg1, void* arg2) {
  IterState* state = reinterpret_cast<IterState*>(arg1);
  state->mu->Lock();
  state->mem->Unref();
  if (state->imm != NULL) state->imm->Unref();
  state->version->Unref();
  state->mu->Unlock();
  delete state;
}
}  // namespace

Iterator* DBImpl::NewInternalIterator(const ReadOptions& options,
                                      SequenceNumber* latest_snapshot) {
  IterState* cleanup = new IterState;
  mutex_.Lock();
  *latest_snapshot = versions_->LastSequence();

  // Collect together all needed child iterators
  std::vector<Iterator*> list;
  list.push_back(mem_->NewIterator());
  mem_->Ref();
  if (imm_ != NULL) {
    list.push_back(imm_->NewIterator());
    imm_->Ref();
  }
  versions_->current()->AddIterators(options, &list);
  Iterator* internal_iter =
      NewMergingIterator(&internal_comparator_, &list[0], list.size());
  versions_->current()->Ref();

  cleanup->mu = &mutex_;
  cleanup->mem = mem_;
  cleanup->imm = imm_;
  cleanup->version = versions_->current();
  internal_iter->RegisterCleanup(CleanupIteratorState, cleanup, NULL);

  mutex_.Unlock();
  return internal_iter;
}

Iterator* DBImpl::TEST_NewInternalIterator() {
  SequenceNumber ignored;
  return NewInternalIterator(ReadOptions(), &ignored);
}

int64_t DBImpl::TEST_MaxNextLevelOverlappingBytes() {
  MutexLock l(&mutex_);
  return versions_->MaxNextLevelOverlappingBytes();
}

Status DBImpl::Get(const ReadOptions& options,
                   const Slice& key,
                   std::string* value) {
  StringValue stringvalue(*value);
  return DBImpl::Get(options, key, &stringvalue);
}

Status DBImpl::Get(const ReadOptions& options,
                   const Slice& key,
                   Value* value) {
  Status s;
  MutexLock l(&mutex_);
  SequenceNumber snapshot;
  if (options.snapshot != NULL) {
    snapshot = reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_;
  } else {
    snapshot = versions_->LastSequence();
  }

  MemTable* mem = mem_;
  MemTable* imm = imm_;
  Version* current = versions_->current();
  mem->Ref();
  if (imm != NULL) imm->Ref();
  current->Ref();

  bool have_stat_update = false;
  Version::GetStats stats;

  // Unlock while reading from files and memtables
  {
    mutex_.Unlock();
    // First look in the memtable, then in the immutable memtable (if any).
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {
      // Done
        gPerfCounters->Inc(ePerfGetMem);
    } else if (imm != NULL && imm->Get(lkey, value, &s)) {
      // Done
        gPerfCounters->Inc(ePerfGetImm);
    } else {
      s = current->Get(options, lkey, value, &stats);
      have_stat_update = true;
      gPerfCounters->Inc(ePerfGetVersion);
    }
    mutex_.Lock();
  }

  if (have_stat_update && current->UpdateStats(stats)) {
      // no compactions initiated by reads, takes too long
      // MaybeScheduleCompaction();
  }
  mem->Unref();
  if (imm != NULL) imm->Unref();
  current->Unref();

  gPerfCounters->Inc(ePerfApiGet);

  return s;
}

Iterator* DBImpl::NewIterator(const ReadOptions& options) {
  SequenceNumber latest_snapshot;
  Iterator* internal_iter = NewInternalIterator(options, &latest_snapshot);
  gPerfCounters->Inc(ePerfIterNew);
  return NewDBIterator(
      &dbname_, env_, user_comparator(), internal_iter,
      (options.snapshot != NULL
       ? reinterpret_cast<const SnapshotImpl*>(options.snapshot)->number_
       : latest_snapshot));
}

const Snapshot* DBImpl::GetSnapshot() {
  MutexLock l(&mutex_);
  return snapshots_.New(versions_->LastSequence());
}

void DBImpl::ReleaseSnapshot(const Snapshot* s) {
  MutexLock l(&mutex_);
  snapshots_.Delete(reinterpret_cast<const SnapshotImpl*>(s));
}

// Convenience methods
Status DBImpl::Put(const WriteOptions& o, const Slice& key, const Slice& val) {
  return DB::Put(o, key, val);
}

Status DBImpl::Delete(const WriteOptions& options, const Slice& key) {
  return DB::Delete(options, key);
}

Status DBImpl::Write(const WriteOptions& options, WriteBatch* my_batch) {
  Status status;
  int throttle(0);

  Writer w(&mutex_);
  w.batch = my_batch;
  w.sync = options.sync;
  w.done = false;

  {  // place mutex_ within a block
     //  not changing tabs to ease compare to Google sources
  MutexLock l(&mutex_);
  writers_.push_back(&w);
  while (!w.done && &w != writers_.front()) {
    w.cv.Wait();
  }
  if (w.done) {
    return w.status;  // skips throttle ... maintenance unfriendly coding, bastards
  }

  // May temporarily unlock and wait.
  status = MakeRoomForWrite(my_batch == NULL);
  uint64_t last_sequence = versions_->LastSequence();
  Writer* last_writer = &w;
  if (status.ok() && my_batch != NULL) {  // NULL batch is for compactions
    WriteBatch* updates = BuildBatchGroup(&last_writer);
    WriteBatchInternal::SetSequence(updates, last_sequence + 1);
    last_sequence += WriteBatchInternal::Count(updates);

    // Add to log and apply to memtable.  We can release the lock
    // during this phase since &w is currently responsible for logging
    // and protects against concurrent loggers and concurrent writes
    // into mem_.
    {
      mutex_.Unlock();
      status = log_->AddRecord(WriteBatchInternal::Contents(updates));
      if (status.ok() && options.sync) {
        status = logfile_->Sync();
      }
      if (status.ok()) {
        status = WriteBatchInternal::InsertInto(updates, mem_);
      }
      mutex_.Lock();
    }
    if (updates == tmp_batch_) tmp_batch_->Clear();

    versions_->SetLastSequence(last_sequence);
  }

  while (true) {
    Writer* ready = writers_.front();
    writers_.pop_front();
    if (ready != &w) {
      ready->status = status;
      ready->done = true;
      ready->cv.Signal();
    }
    if (ready == last_writer) break;
  }

  // Notify new head of write queue
  if (!writers_.empty()) {
    writers_.front()->cv.Signal();
  }

  gPerfCounters->Inc(ePerfApiWrite);

  // protect use of versions_ ... still within scope of mutex_ lock
  throttle=versions_->WriteThrottleUsec(bg_compaction_scheduled_);
  }  // release  MutexLock l(&mutex_)

  // throttle on exit to reduce possible reordering
  if (0!=throttle)
  {
      /// slowing each call down sequentially
      MutexLock l(&throttle_mutex_);

      // throttle is per key write, how many in batch?
      env_->SleepForMicroseconds(throttle * WriteBatchInternal::Count(my_batch));
      gPerfCounters->Add(ePerfDebug0, throttle);
{'fraction_non_alphanumeric': 0.13005122674575356, 'fraction_numerical': 0.005856025882987328, 'mean_word_length': 2.7218431404029864, 'pattern_counts': {'":': 0, '<': 139, '<?xml version=': 0, '>': 763, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5343680', 'n_tokens_mistral': 29539, 'n_tokens_neox': 28577, 'n_words': 6942}