Inside Bitcoin

2001    for (int id = 0; id < kNumThreads; id++) {
2002      thread[id].state = &mt;
2003      thread[id].id = id;
2004      env_->StartThread(MTThreadBody, &thread[id]);
2005    }
2006
2007    // Let them run for a while
2008    DelayMilliseconds(kTestSeconds * 1000);
2009
2010    // Stop the threads and wait for them to finish
2011    mt.stop.store(true, std::memory_order_release);
2012    for (int id = 0; id < kNumThreads; id++) {
2013      while (!mt.thread_done[id].load(std::memory_order_acquire)) {
2014        DelayMilliseconds(100);
2015      }
2016    }
2017  } while (ChangeOptions());
2018}
2019
2020namespace {
2021typedef std::map<std::string, std::string> KVMap;
2022}
2023
2024class ModelDB : public DB {
2025 public:
2026  class ModelSnapshot : public Snapshot {
2027   public:
2028    KVMap map_;
2029  };
2030
2031  explicit ModelDB(const Options& options) : options_(options) {}
2032  ~ModelDB() override = default;
2033  Status Put(const WriteOptions& o, const Slice& k, const Slice& v) override {
2034    return DB::Put(o, k, v);
2035  }
2036  Status Delete(const WriteOptions& o, const Slice& key) override {
2037    return DB::Delete(o, key);
2038  }
2039  Status Get(const ReadOptions& options, const Slice& key,
2040             std::string* value) override {
2041    assert(false);  // Not implemented
2042    return Status::NotFound(key);
2043  }
2044  Iterator* NewIterator(const ReadOptions& options) override {
2045    if (options.snapshot == nullptr) {
2046      KVMap* saved = new KVMap;
2047      *saved = map_;
2048      return new ModelIter(saved, true);
2049    } else {
2050      const KVMap* snapshot_state =
2051          &(reinterpret_cast<const ModelSnapshot*>(options.snapshot)->map_);
2052      return new ModelIter(snapshot_state, false);
2053    }
2054  }
2055  const Snapshot* GetSnapshot() override {
2056    ModelSnapshot* snapshot = new ModelSnapshot;
2057    snapshot->map_ = map_;
2058    return snapshot;
2059  }
2060
2061  void ReleaseSnapshot(const Snapshot* snapshot) override {
2062    delete reinterpret_cast<const ModelSnapshot*>(snapshot);
2063  }
2064  Status Write(const WriteOptions& options, WriteBatch* batch) override {
2065    class Handler : public WriteBatch::Handler {
2066     public:
2067      KVMap* map_;
2068      void Put(const Slice& key, const Slice& value) override {
2069        (*map_)[key.ToString()] = value.ToString();
2070      }
2071      void Delete(const Slice& key) override { map_->erase(key.ToString()); }
2072    };
2073    Handler handler;
2074    handler.map_ = &map_;
2075    return batch->Iterate(&handler);
2076  }
2077
2078  bool GetProperty(const Slice& property, std::string* value) override {
2079    return false;
2080  }
2081  void GetApproximateSizes(const Range* r, int n, uint64_t* sizes) override {
2082    for (int i = 0; i < n; i++) {
2083      sizes[i] = 0;
2084    }
2085  }
2086  void CompactRange(const Slice* start, const Slice* end) override {}
2087
2088 private:
2089  class ModelIter : public Iterator {
2090   public:
2091    ModelIter(const KVMap* map, bool owned)
2092        : map_(map), owned_(owned), iter_(map_->end()) {}
2093    ~ModelIter() override {
2094      if (owned_) delete map_;
2095    }
2096    bool Valid() const override { return iter_ != map_->end(); }
2097    void SeekToFirst() override { iter_ = map_->begin(); }
2098    void SeekToLast() override {
2099      if (map_->empty()) {
2100        iter_ = map_->end();
2101      } else {
2102        iter_ = map_->find(map_->rbegin()->first);
2103      }
2104    }
2105    void Seek(const Slice& k) override {
2106      iter_ = map_->lower_bound(k.ToString());
2107    }
2108    void Next() override { ++iter_; }
2109    void Prev() override { --iter_; }
2110    Slice key() const override { return iter_->first; }
2111    Slice value() const override { return iter_->second; }
2112    Status status() const override { return Status::OK(); }
2113
2114   private:
2115    const KVMap* const map_;
2116    const bool owned_;  // Do we own map_
2117    KVMap::const_iterator iter_;
2118  };
2119  const Options options_;
2120  KVMap map_;
2121};
2122
2123static bool CompareIterators(int step, DB* model, DB* db,
2124                             const Snapshot* model_snap,
2125                             const Snapshot* db_snap) {
2126  ReadOptions options;
2127  options.snapshot = model_snap;
2128  Iterator* miter = model->NewIterator(options);
2129  options.snapshot = db_snap;
2130  Iterator* dbiter = db->NewIterator(options);
2131  bool ok = true;
2132  int count = 0;
2133  for (miter->SeekToFirst(), dbiter->SeekToFirst();
2134       ok && miter->Valid() && dbiter->Valid(); miter->Next(), dbiter->Next()) {
2135    count++;
2136    if (miter->key().compare(dbiter->key()) != 0) {
2137      fprintf(stderr, "step %d: Key mismatch: '%s' vs. '%s'\n", step,
2138              EscapeString(miter->key()).c_str(),
2139              EscapeString(dbiter->key()).c_str());
2140      ok = false;
2141      break;
2142    }
2143
2144    if (miter->value().compare(dbiter->value()) != 0) {
2145      fprintf(stderr, "step %d: Value mismatch for key '%s': '%s' vs. '%s'\n",
2146              step, EscapeString(miter->key()).c_str(),
2147              EscapeString(miter->value()).c_str(),
2148              EscapeString(miter->value()).c_str());
2149      ok = false;
2150    }
2151  }
2152
2153  if (ok) {
2154    if (miter->Valid() != dbiter->Valid()) {
2155      fprintf(stderr, "step %d: Mismatch at end of iterators: %d vs. %d\n",
2156              step, miter->Valid(), dbiter->Valid());
2157      ok = false;
2158    }
2159  }
2160  fprintf(stderr, "%d entries compared: ok=%d\n", count, ok);
2161  delete miter;
2162  delete dbiter;
2163  return ok;
2164}
2165
2166TEST(DBTest, Randomized) {
2167  Random rnd(test::RandomSeed());
2168  do {
2169    ModelDB model(CurrentOptions());
2170    const int N = 10000;
2171    const Snapshot* model_snap = nullptr;
2172    const Snapshot* db_snap = nullptr;
2173    std::string k, v;
2174    for (int step = 0; step < N; step++) {
2175      if (step % 100 == 0) {
2176        fprintf(stderr, "Step %d of %d\n", step, N);
2177      }
2178      // TODO(sanjay): Test Get() works
2179      int p = rnd.Uniform(100);
2180      if (p < 45) {  // Put
2181        k = RandomKey(&rnd);
2182        v = RandomString(
2183            &rnd, rnd.OneIn(20) ? 100 + rnd.Uniform(100) : rnd.Uniform(8));
2184        ASSERT_OK(model.Put(WriteOptions(), k, v));
2185        ASSERT_OK(db_->Put(WriteOptions(), k, v));
2186
2187      } else if (p < 90) {  // Delete
2188        k = RandomKey(&rnd);
2189        ASSERT_OK(model.Delete(WriteOptions(), k));
2190        ASSERT_OK(db_->Delete(WriteOptions(), k));
2191
2192      } else {  // Multi-element batch
2193        WriteBatch b;
2194        const int num = rnd.Uniform(8);
2195        for (int i = 0; i < num; i++) {
2196          if (i == 0 || !rnd.OneIn(10)) {
2197            k = RandomKey(&rnd);
2198          } else {
2199            // Periodically reuse the same key from the previous iter, so
2200            // we have multiple entries in the write batch for the same key
2201          }
2202          if (rnd.OneIn(2)) {
2203            v = RandomString(&rnd, rnd.Uniform(10));
2204            b.Put(k, v);
2205          } else {
2206            b.Delete(k);
2207          }
2208        }
2209        ASSERT_OK(model.Write(WriteOptions(), &b));
2210        ASSERT_OK(db_->Write(WriteOptions(), &b));
2211      }
2212
2213      if ((step % 100) == 0) {
2214        ASSERT_TRUE(CompareIterators(step, &model, db_, nullptr, nullptr));
2215        ASSERT_TRUE(CompareIterators(step, &model, db_, model_snap, db_snap));
2216        // Save a snapshot from each DB this time that we'll use next
2217        // time we compare things, to make sure the current state is
2218        // preserved with the snapshot
2219        if (model_snap != nullptr) model.ReleaseSnapshot(model_snap);
2220        if (db_snap != nullptr) db_->ReleaseSnapshot(db_snap);
2221
2222        Reopen();
2223        ASSERT_TRUE(CompareIterators(step, &model, db_, nullptr, nullptr));
2224
2225        model_snap = model.GetSnapshot();
2226        db_snap = db_->GetSnapshot();
2227      }
2228    }
2229    if (model_snap != nullptr) model.ReleaseSnapshot(model_snap);
2230    if (db_snap != nullptr) db_->ReleaseSnapshot(db_snap);
2231  } while (ChangeOptions());
2232}
2233
2234std::string MakeKey(unsigned int num) {
2235  char buf[30];
2236  snprintf(buf, sizeof(buf), "%016u", num);
2237  return std::string(buf);
2238}
2239
2240void BM_LogAndApply(int iters, int num_base_files) {
2241  std::string dbname = test::TmpDir() + "/leveldb_test_benchmark";
2242  DestroyDB(dbname, Options());
2243
2244  DB* db = nullptr;
2245  Options opts;
2246  opts.create_if_missing = true;
2247  Status s = DB::Open(opts, dbname, &db);
2248  ASSERT_OK(s);
2249  ASSERT_TRUE(db != nullptr);
2250