conflict-set/ShowMemoryTest.cpp

// Exercises the SHOW_MEMORY instrumentation, which the other tests don't
// compile with (this target passes -DSHOW_MEMORY=1). The instrumentation has
// its own consistency checks, which abort on failure, and asserts are enabled
// by TEST_FLAGS. Only one ConflictSet may exist at a time, since the
// accounting is process-wide.
#include "ConflictSet.h"
#include "Internal.h"

#include <cassert>
#include <cstdint>
#include <string>

using namespace weaselab;

namespace {

void writePoint(ConflictSet &cs, const std::string &key, int64_t writeVersion) {
  ConflictSet::WriteRange w{{(const uint8_t *)key.data(), int(key.size())},
                            {nullptr, 0}};
  cs.addWrites(&w, 1, writeVersion);
}

ConflictSet::Result checkPoint(const ConflictSet &cs, const std::string &key,
                               int64_t readVersion) {
  ConflictSet::ReadRange r{{(const uint8_t *)key.data(), int(key.size())},
                           {nullptr, 0},
                           readVersion};
  ConflictSet::Result result;
  cs.check(&r, &result, 1);
  return result;
}

// Everything a ConflictSet allocated must have been accounted for and released
// by the time it's destroyed.
void checkFullyReleased() {
  assert(nodeBytes == 0);
  assert(partialCapacityBytes == 0);
  assert(totalKeys == 0);
  assert(keyBytes == 0);
  assert(mallocBytes == 0);
}

} // namespace

int main() {
  // Splitting a node replaces it, which defers the release of the old node.
  // Releasing a deferred node must account for its capacity, and the key it
  // held must be accounted for without walking `parent` pointers of nodes that
  // have already been released.
  {
    ConflictSet cs{0};
    writePoint(cs, "a", 1);
    writePoint(cs, "ab", 2);
    assert(checkPoint(cs, "a", 0) == ConflictSet::Conflict);
    assert(checkPoint(cs, "ab", 0) == ConflictSet::Conflict);
    assert(checkPoint(cs, "b", 0) == ConflictSet::Commit);
    assert(nodeBytes > 0);
    assert(keyBytes > 0);
  }
  checkFullyReleased();

  // Exceeding the version window erases the tree mid-workload.
  {
    ConflictSet cs{0};
    writePoint(cs, "abc", 1);
    const int64_t version = int64_t(1) << 40;
    writePoint(cs, "abc", version);
    assert(checkPoint(cs, "abc", 0) == ConflictSet::TooOld);
    assert(checkPoint(cs, "abc", version) == ConflictSet::Commit);
  }
  checkFullyReleased();

  // Erase a tree with many nodes, both mid-workload and at destruction.
  {
    ConflictSet cs{0};
    for (int i = 0; i < 1000; ++i) {
      writePoint(cs, "prefix/" + std::to_string(i), i + 1);
    }
    const int64_t version = int64_t(1) << 40;
    writePoint(cs, "prefix/1", version);
    assert(checkPoint(cs, "prefix/1", version) == ConflictSet::Commit);

    for (int i = 0; i < 1000; ++i) {
      writePoint(cs, "other/" + std::to_string(i), version + i + 1);
    }
    assert(checkPoint(cs, "other/999", version) == ConflictSet::Conflict);
  }
  checkFullyReleased();

  // Grow a node through every node type, so that the accounting for each node
  // type's size is exercised, then erase the entries one at a time so that
  // nodes are released individually rather than as part of a whole tree.
  {
    ConflictSet cs{0};
    std::string key(1, '\0');
    for (int i = 0; i < 256; ++i) {
      key[0] = char(i);
      writePoint(cs, key, i + 1);
    }
    for (int i = 0; i < 256; ++i) {
      key[0] = char(i);
      assert(checkPoint(cs, key, i) == ConflictSet::Conflict);
    }

    // Garbage collection erases entries that can only fail with TooOld anyway.
    // Doing it one version at a time walks the tree, erasing, downsizing and
    // releasing nodes as it goes.
    for (int i = 0; i < 256; ++i) {
      cs.setOldestVersion(i + 1);
    }
    key[0] = '\0';
    assert(checkPoint(cs, key, 0) == ConflictSet::TooOld);
  }
  checkFullyReleased();
}