From 7aa7649e980ff4b335b41eaea34a9a11820c3e2d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Roman=20Smr=C5=BE?= Date: Mon, 8 Aug 2022 22:25:46 +0200 Subject: Generation number of stored objects with caching --- include/erebos/storage.h | 53 ++++++++++++++++++++-------------- src/main.cpp | 47 ++++++++++++++++++++++++++++++ src/storage.cpp | 69 ++++++++++++++++++++++++++++++++++++++++++++ src/storage.h | 3 ++ test/storage.test | 75 ++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 226 insertions(+), 21 deletions(-) create mode 100644 test/storage.test diff --git a/include/erebos/storage.h b/include/erebos/storage.h index 24a59df..e894fee 100644 --- a/include/erebos/storage.h +++ b/include/erebos/storage.h @@ -41,6 +41,8 @@ using std::bind; using std::call_once; using std::make_unique; using std::move; +using std::string; +using std::vector; class PartialStorage { @@ -68,6 +70,10 @@ protected: struct Priv; const std::shared_ptr p; PartialStorage(const std::shared_ptr & p): p(p) {} + +public: + // For test usage + const Priv & priv() const { return *p; } }; class Storage : public PartialStorage @@ -200,6 +206,12 @@ public: const Storage & storage() const; + vector previous() const; + class Generation generation() const; + +private: + class Generation generationLocked() const; + protected: Ref(const std::shared_ptr p): PartialRef(p) {} }; @@ -349,6 +361,19 @@ std::optional> RecordT::Item::as() const return std::nullopt; } +class Generation +{ +public: + Generation(); + static Generation next(const vector &); + + explicit operator string() const; + +private: + Generation(size_t); + size_t gen; +}; + template class Stored { @@ -382,6 +407,8 @@ public: const T & operator*() const { init(); return *p->val; } const T * operator->() const { init(); return p->val.get(); } + Generation generation() const { return p->ref.generation(); } + std::vector> previous() const; bool precedes(const Stored &) const; @@ -448,27 +475,11 @@ Ref Stored::store(const Storage & st) const template std::vector> Stored::previous() const { - auto rec = p->ref->asRecord(); - if (!rec) - return {}; - - auto sdata = rec->item("SDATA").asRef(); - if (sdata) { - auto drec = sdata.value()->asRecord(); - if (!drec) - return {}; - - std::vector> res; - for (const Record::Item & i : drec->items("SPREV")) - if (auto x = i.as()) - res.push_back(*x); - return res; - } - - std::vector> res; - for (const Record::Item & i : rec->items("PREV")) - if (auto x = i.as()) - res.push_back(*x); + auto refs = p->ref.previous(); + vector> res; + res.reserve(refs.size()); + for (const auto & r : refs) + res.push_back(Stored::load(r)); return res; } diff --git a/src/main.cpp b/src/main.cpp index cb9002e..a3facea 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -4,6 +4,8 @@ #include #include +#include "storage.h" + #include #include #include @@ -37,6 +39,7 @@ using std::promise; using std::scoped_lock; using std::string; using std::thread; +using std::to_string; using std::unique_ptr; using std::vector; @@ -104,6 +107,48 @@ struct Command function &)> action; }; +void store(const vector & args) +{ + auto type = args.at(0); + + vector inner, data; + + char * line = nullptr; + size_t size = 0; + + while (getline(&line, &size, stdin) > 0 && strlen(line) > 1) + copy(line, line + strlen(line), std::back_inserter(inner)); + + free(line); + + auto inserter = std::back_inserter(data); + copy(type.begin(), type.end(), inserter); + inserter = ' '; + + auto slen = to_string(inner.size()); + copy(slen.begin(), slen.end(), inserter); + inserter = '\n'; + + copy(inner.begin(), inner.end(), inserter); + + auto digest = st.priv().storeBytes(data); + + ostringstream ss; + ss << "store-done " << string(digest); + printLine(ss.str()); +} + +void storedGeneration(const vector & args) +{ + auto ref = st.ref(Digest(args.at(0))); + if (!ref) + throw invalid_argument("ref " + args.at(0) + " not found"); + + ostringstream ss; + ss << "stored-generation " << string(ref->digest()) << " " << string(ref->generation()); + printLine(ss.str()); +} + void createIdentity(const vector & args) { optional identity; @@ -292,6 +337,8 @@ void attachReject(const vector & params) } vector commands = { + { "store", store }, + { "stored-generation", storedGeneration }, { "create-identity", createIdentity }, { "start-server", startServer }, { "stop-server", stopServer }, diff --git a/src/storage.cpp b/src/storage.cpp index 05b100a..5784309 100644 --- a/src/storage.cpp +++ b/src/storage.cpp @@ -979,6 +979,56 @@ const Storage & Ref::storage() const return *static_cast(p->storage.get()); } +vector Ref::previous() const +{ + auto rec = (**this).asRecord(); + if (!rec) + return {}; + + vector res; + + auto sdata = rec->item("SDATA").asRef(); + if (sdata) { + auto drec = sdata.value()->asRecord(); + if (!drec) + return {}; + + for (const Record::Item & i : drec->items("SPREV")) + if (auto x = i.asRef()) + res.push_back(*x); + return res; + } + + for (const Record::Item & i : rec->items("PREV")) + if (auto x = i.asRef()) + res.push_back(*x); + return res; +} + +Generation Ref::generation() const +{ + scoped_lock lock(p->storage->p->generationCacheLock); + return generationLocked(); +} + +Generation Ref::generationLocked() const +{ + auto it = p->storage->p->generationCache.find(p->digest); + if (it != p->storage->p->generationCache.end()) + return it->second; + + auto prev = previous(); + vector pgen; + pgen.reserve(prev.size()); + for (const auto & r : prev) + pgen.push_back(r.generationLocked()); + + auto gen = Generation::next(pgen); + + p->storage->p->generationCache.emplace(p->digest, gen); + return gen; +} + template RecordT::Item::operator bool() const @@ -1366,6 +1416,25 @@ optional ObjectT::asBlob() const template class erebos::ObjectT; template class erebos::ObjectT; + +Generation::Generation(): Generation(0) {} +Generation::Generation(size_t g): gen(g) {} + +Generation Generation::next(const vector & prev) +{ + Generation ret; + for (const auto g : prev) + if (ret.gen <= g.gen) + ret.gen = g.gen + 1; + return ret; +} + +Generation::operator string() const +{ + return to_string(gen); +} + + vector> erebos::collectStoredObjects(const Stored & from) { unordered_set seen; diff --git a/src/storage.h b/src/storage.h index 0f7c3bf..ef335b8 100644 --- a/src/storage.h +++ b/src/storage.h @@ -164,6 +164,9 @@ struct PartialStorage::Priv optional copy(const typename S::Ref &, vector *) const; template optional copy(const ObjectT &, vector *) const; + + mutable mutex generationCacheLock {}; + mutable unordered_map generationCache {}; }; struct PartialRef::Priv diff --git a/test/storage.test b/test/storage.test new file mode 100644 index 0000000..2ce87d5 --- /dev/null +++ b/test/storage.test @@ -0,0 +1,75 @@ +test: + spawn on node1 as p1 + + # Diamond history + send to p1: + "store rec" + "text:t First root" + "" + expect from p1: + /store-done (blake2#[0-9a-f]*)/ capture r1 + guard r1 == "blake2#c4a8c69fbc8398acf76a2ec1e5a191f339c4d03c3eb425af19d6d7d5efac6b8e" + + send to p1: + "store rec" + "PREV:r $r1" + "" + expect from p1: + /store-done (blake2#[0-9a-f]*)/ capture r2 + + send to p1: + "store rec" + "text:t Second branch" + "PREV:r $r1" + "" + expect from p1: + /store-done (blake2#[0-9a-f]*)/ capture r3 + + send to p1: + "store rec" + "PREV:r $r2" + "PREV:r $r3" + "" + expect from p1: + /store-done (blake2#[0-9a-f]*)/ capture r4 + + send to p1 "stored-generation $r1" + expect from p1 /stored-generation $r1 0/ + + send to p1 "stored-generation $r2" + expect from p1 /stored-generation $r2 1/ + + send to p1 "stored-generation $r3" + expect from p1 /stored-generation $r3 1/ + + send to p1 "stored-generation $r4" + expect from p1 /stored-generation $r4 2/ + + # Attach second root + send to p1: + "store rec" + "text:t Second root" + "" + expect from p1: + /store-done (blake2#[0-9a-f]*)/ capture r2_1 + + send to p1: + "store rec" + "PREV:r $r2_1" + "" + expect from p1: + /store-done (blake2#[0-9a-f]*)/ capture r2_2 + + send to p1: + "store rec" + "PREV:r $r2_2" + "PREV:r $r4" + "" + expect from p1: + /store-done (blake2#[0-9a-f]*)/ capture r2_3 + + send to p1 "stored-generation $r2_3" + expect from p1 /stored-generation $r2_3 3/ + + send to p1 "stored-generation $r2_2" + expect from p1 /stored-generation $r2_2 1/ -- cgit v1.2.3