From af8759a9c1d965a3220024d1857aea219d62d898 Mon Sep 17 00:00:00 2001 From: Marcos Magueta Date: Mon, 18 May 2026 12:50:25 -0300 Subject: Branching and object registry rework (#11) --- include/CursorManager.h | 49 +++++++++- include/HandlerManager.h | 5 +- include/LifecycleManager.h | 75 +++++++++++++-- include/Merkle.h | 162 +++++++++++++++++++------------ include/MultigroupCodec.h | 89 +++++++++++++++++ include/NamespaceReferenceManager.h | 70 +++++++++++--- include/ObjectManager.h | 145 +++++++++++++++++++++++++--- include/PermissionsManager.h | 11 ++- include/RNT_C_API.h | 185 ++++++++++++++++++++++++++---------- include/Types.h | 73 ++++++++++---- 10 files changed, 693 insertions(+), 171 deletions(-) create mode 100644 include/MultigroupCodec.h (limited to 'include') diff --git a/include/CursorManager.h b/include/CursorManager.h index 839bf5e..c2606c3 100644 --- a/include/CursorManager.h +++ b/include/CursorManager.h @@ -3,6 +3,8 @@ #include "Api.h" #include "HandlerManager.h" #include "IStorageBackend.h" +#include "LifecycleManager.h" +#include "ObjectManager.h" #include "Types.h" #include @@ -37,8 +39,19 @@ namespace nt public: static constexpr std::size_t PAGE_SIZE = 1; - /** @brief Constructs a CursorManager that reads from the given backend. */ - explicit CursorManager(IStorageBackend& backend); + /** + * @brief Constructs a CursorManager. + * + * The @p lifecycles and @p objects references are optional: when + * left null the cursor performs no snapshot pinning (this matches the + * test fixtures, which register relations at synthetic paths with no + * /system/snapshots ancestor). When both are provided, Open finds the + * resolved snapshot for the handle's relation and Pins it for the + * cursor's lifetime, releasing the pin in Close. + */ + explicit CursorManager(IStorageBackend& backend, + LifecycleManager* lifecycles = nullptr, + ObjectManager* objects = nullptr); /** * @brief Active scan state for a single relation. @@ -53,9 +66,15 @@ namespace nt * merkle_root is seeded from ObjectManager::Relation::merkle_root at * open time and does not change during iteration; the cursor reads the * snapshot captured when it was opened. + * + * Notably the cursor does NOT keep a pointer to the HandlerManager + * handle it was opened from. Everything Next() needs — the relation + * type, the merkle_root, and the ephemeral generator function — is + * captured at Open time, so closing the handle before the cursor is + * exhausted is safe (the API contract still says to close the cursor + * first, but a violation no longer dereferences a freed handle). */ struct cursor { - HandlerManager::handle* handle = nullptr; /** * Hex hash of the relation's Merkle B-tree root node. * Empty string means the relation contains no tuples. @@ -71,6 +90,26 @@ namespace nt std::size_t page_position = 0; std::size_t fetch_offset = 0; // next Merkle::Page() call starts here bool exhausted = false; + /** + * True for EPHEMERAL_RELATION cursors; selects the generator-driven + * page fetch path instead of Merkle B-tree paging. + */ + bool is_ephemeral = false; + /** + * Generator function for ephemeral cursors. Copied from the + * ephemeral_object_type at Open time, so the cursor remains valid + * even if the source registry entry is later torn down (the + * snapshot pin held in pinned_snapshot prevents that today, but + * the copy makes the cursor independent regardless). + */ + ObjectManager::ephemeral_object_type::Generator generator; + /** + * Borrowed pointer to the snapshot the cursor is pinning. + * Non-null only when a /system/snapshots// + * ancestor was found at Open time and LifecycleManager was + * available. Close unpins it. + */ + ObjectManager::registry* pinned_snapshot = nullptr; }; /** @@ -103,7 +142,9 @@ namespace nt void Close(cursor* cursor); private: - IStorageBackend& backend_; + IStorageBackend& backend_; + LifecycleManager* lifecycles_ = nullptr; + ObjectManager* objects_ = nullptr; /** * Fetches a page of hashes via Merkle::Page, resolves each from the diff --git a/include/HandlerManager.h b/include/HandlerManager.h index f3d504e..06ed362 100644 --- a/include/HandlerManager.h +++ b/include/HandlerManager.h @@ -17,6 +17,7 @@ namespace nt { class IdentityManager; class LifecycleManager; + class NamespaceReferenceManager; class PermissionsManager; /** @brief Opens and closes authorized handles to registry objects. */ @@ -33,7 +34,8 @@ namespace nt HandlerManager(ObjectManager& objects, PermissionsManager& permissions, IdentityManager& identities, - LifecycleManager& lifecycles); + LifecycleManager& lifecycles, + NamespaceReferenceManager& references); /** * @brief Represents authorized access to an object in the registry. @@ -93,5 +95,6 @@ namespace nt PermissionsManager& permissions_; IdentityManager& identities_; LifecycleManager& lifecycles_; + NamespaceReferenceManager& references_; }; } diff --git a/include/LifecycleManager.h b/include/LifecycleManager.h index 8126820..5508bc6 100644 --- a/include/LifecycleManager.h +++ b/include/LifecycleManager.h @@ -1,6 +1,7 @@ #pragma once #include "Api.h" +#include "IStorageBackend.h" #include "ObjectManager.h" /** @@ -15,9 +16,9 @@ namespace nt * * Object lifetime is governed by two independent counters in registry_head: * `handle_count` (sessions holding an open handle) and `reference_count` - * (structural dependencies such as cursors pinned to a snapshot or views - * referencing base relations). An object is eligible for GC only when both - * reach zero. + * (structural dependencies such as cursors pinned to a snapshot or + * ephemeral relations referencing their base relations). An object is + * eligible for GC only when both reach zero. * * Monitor / Unmonitor manage `handle_count`. Pin / Unpin manage * `reference_count`. See docs/reactos-ob-comparison.md §1. @@ -25,6 +26,18 @@ namespace nt class NT_API LifecycleManager { public: + /** + * @brief Constructs a LifecycleManager bound to a registry and store. + * + * Needs the registry to perform GC: Unmonitor and Unpin call + * ObjectManager::Unregister once both counters reach zero. Type-specific + * cleanup (e.g. cascading a Multigroup's pin to its child Relations, + * or a BranchTree's pin to its child Multigroups) runs inside the + * lifecycle manager before the entry is spliced out. The storage + * backend is needed by CascadeBranchTree to page the merkle nodes. + */ + LifecycleManager(ObjectManager& objects, IStorageBackend& storage); + /** * @brief Starts monitoring an object's lifecycle. * @@ -53,9 +66,9 @@ namespace nt * @brief Increments the structural dependency count on an object. * * Call when one object takes a dependency on another — for example when - * a cursor pins an immutable snapshot version, or when a view is - * registered against its base relations. Prevents GC of the target object - * while the dependency is live. + * a cursor pins an immutable snapshot version, or when an ephemeral + * relation is registered against its base relations. Prevents GC of the + * target object while the dependency is live. * * @todo Implement. See docs/reactos-ob-comparison.md §1. * @@ -75,6 +88,15 @@ namespace nt */ void Unpin(ObjectManager::registry* object); + /** + * @brief Returns true when the object is GC-eligible right now. + * + * Eligibility is the joint condition handle_count == 0 && + * reference_count == 0. Decrement callers (Unmonitor / Unpin) consult + * this and, when true, run type-specific cleanup before unregistering. + */ + bool IsEligibleForGC(ObjectManager::registry* object) const; + /** * @brief Serializes contention for changes to mutable reference states. * @@ -97,5 +119,46 @@ namespace nt * @return True when the operation may proceed. */ const bool Contention(ObjectManager::registry* object); + + private: + /** + * @brief Joint-counters check + type-specific cascade + Unregister. + * + * Called by Unmonitor and Unpin after their decrement. No-op when the + * object is still referenced. When eligible: + * - MULTIGROUP entries first unpin every Relation registered as a + * direct child of their /system/snapshots/H subtree. + * - BRANCH_TREE entries first unpin every Multigroup their + * content-addressed tree references. + * - The entry is then removed from the registry; its IObject and + * registry_head are freed. + * + * Inline GC for now; the reaper-queue deferred-deletion pattern from + * docs/reactos-ob-comparison.md §7 is a later optimisation. + */ + void TryCollect(ObjectManager::registry* object); + + /** + * @brief Releases pins held by a MULTIGROUP entry on its child Relations. + * + * Iterates the registry once, collects every /system/snapshots// + * direct child, and calls Unpin on each. Triggered exclusively from + * TryCollect at the moment the parent snapshot becomes eligible for GC. + */ + void CascadeMultigroup(ObjectManager::registry* multigroup); + + /** + * @brief Releases pins held by a BRANCH_TREE entry on its child mgs. + * + * Pages the Merkle tree at the BranchTree's merkle_root, + * resolves each (mg_name, mg_hash) entry to its + * /system/snapshots/ Multigroup, and calls Unpin on it. + * Triggered exclusively from TryCollect at the moment the BranchTree + * itself becomes eligible for GC. + */ + void CascadeBranchTree(ObjectManager::registry* branch_tree); + + ObjectManager& objects_; + IStorageBackend& storage_; }; } diff --git a/include/Merkle.h b/include/Merkle.h index 8380093..ba8018a 100644 --- a/include/Merkle.h +++ b/include/Merkle.h @@ -5,105 +5,143 @@ #include #include #include +#include #include #include /** * @file Merkle.h - * @brief Sorted content-addressed B-tree over SHA-256 tuple hash hex strings. + * @brief Generic sorted content-addressed B-tree over a templated key type. * - * Each node is stored as an immutable blob in IStorageBackend via Put/Get. - * All three operations load only the nodes on the path from root to the target - * leaf — O(log_B(n)) nodes in memory at once, never the whole tree. + * Maps `Key → Hash32 payload` with `Key` totally ordered. Each tree node is + * stored as an immutable blob in IStorageBackend via Put/Get. All operations + * load only the nodes on the path from root to the target leaf — O(log_B(n)) + * nodes in memory at once, never the whole tree. * - * **Branching factor B = 64**: leaves hold up to 64 hashes; internal nodes hold - * up to 64 child entries. At B=64 and 1 billion tuples the tree is at most - * 5 levels deep (~20 KB peak working set). + * Instantiated three times in RNT: + * + * | Level | Key | Payload (Hash32) | + * |---------------|----------------|-------------------------| + * | Branch tree | `std::string` | multigroup snapshot hash| + * | Multigroup | `std::string` | relation merkle root | + * | Relation | `nt::Hash32` | tuple hash (key=payload)| + * + * **Branching factor B = 64**. At 64 children per node and a billion leaves the + * tree is at most 5 levels deep (~20 KB peak working set). * * **Immutability**: nodes are never overwritten once written (content-addressed). - * Insert and Remove produce new nodes only along the modified path; old nodes + * Insert / Remove produce new nodes only along the modified path; old nodes * remain valid for any snapshot that still holds their root hash. * - * **Internal node entry layout** (leaf_count | min_hash | child_hash): + * **Leaf node** stores a sorted-by-key list of `(Key, Hash32 payload)` pairs, + * length ≤ B. For the relation level the key and payload happen to carry the + * same value (the tuple hash); callers pass it twice. Storing both keeps the + * tree shape uniform across the three levels. + * + * **Internal node entry** layout (`leaf_count | min_key | child_hash`): * - `leaf_count` enables O(log_B(n) + limit) offset navigation for Page() * without loading sibling subtrees. - * - `min_hash` (smallest tuple hash in the subtree) is the routing key. + * - `min_key` is the smallest key in the subtree — the routing key. * - `child_hash` is the content-addressed hash of the child node blob. * * **Invariants** (asserted in debug builds): * - No leaf or internal node is ever empty. - * - Internal node entries are sorted ascending by min_hash. - * - All public entry points that accept a hex hash throw `std::invalid_argument` - * when the string is not exactly 64 lowercase hex characters. + * - Leaf entries are sorted ascending by key. + * - Internal entries are sorted ascending by min_key. * - * @todo Add bounds checking in decode_leaf / decode_internal: validate that the - * reported entry count does not exceed the actual blob size before reading. - * Currently a truncated or corrupt blob causes out-of-bounds reads. + * **Wire format**: tagged 1-byte node kind ('L' or 'I'), then big-endian u32 + * count, then count repetitions of either a leaf entry or a child entry. + * Key encoding is per-specialisation: `Hash32` is 32 raw bytes; `std::string` + * is `u32_be length | bytes`. Wire format is content-addressed — any change + * here invalidates every existing stored snapshot. */ namespace nt { +/** @brief 32-byte hash, the universal payload type for all merkle levels. */ +using Hash32 = std::array; + +/** @brief Decode a 64-character lowercase-hex SHA256 string into raw bytes. + * Throws std::invalid_argument when the string is not exactly 64 hex chars. */ +Hash32 hex_to_bin(const std::string& hex); + +/** @brief Encode raw 32 bytes back into a 64-character lowercase-hex string. */ +std::string bin_to_hex(const Hash32& bin); + +template class Merkle { public: static constexpr size_t B = 64; /** - * @brief Insert a tuple hash into the tree. - * @param store KV backend for node serialization. + * @brief Insert or overwrite a `(key, payload)` mapping. + * @param store KV backend for node serialisation. * @param root_hex Current root hash (empty string = empty tree). - * @param hash_hex 64-char hex SHA-256 of the tuple to insert. - * @return New root hash. Equal to root_hex when the hash was already present. + * @param key Routing/identity key. + * @param payload Hash this key maps to (child root one level down, or + * the key itself at the relation level). + * @return New root hash. Equal to root_hex when an insertion of an + * identical (key, payload) pair would be a no-op. */ static std::string Insert(IStorageBackend& store, - const std::string& root_hex, - const std::string& hash_hex); + const std::string& root_hex, + const Key& key, + const Hash32& payload); /** - * @brief Remove a tuple hash from the tree. - * @param store KV backend. - * @param root_hex Current root hash. - * @param hash_hex 64-char hex SHA-256 of the tuple to remove. - * @return New root hash. Empty string when the tree becomes empty. + * @brief Remove a key from the tree. + * @return New root hash. Empty string when the tree becomes empty. + * Equal to root_hex when the key is absent. */ static std::string Remove(IStorageBackend& store, - const std::string& root_hex, - const std::string& hash_hex); + const std::string& root_hex, + const Key& key); + + /** + * @brief Look up the payload for a key. + * @return The payload when present, std::nullopt when absent. + */ + static std::optional Get(IStorageBackend& store, + const std::string& root_hex, + const Key& key); + + /** @brief One (key, payload) pair returned by Page(). */ + struct Entry { + Key key; + Hash32 payload; + }; /** - * @brief Page through tuple hashes in sorted order. + * @brief Page through entries in key-sorted order. * * Descends to the leaf at logical position @p offset using cumulative * leaf_counts stored in internal nodes, then walks forward collecting at - * most @p limit hashes. Only the nodes on the active path are loaded; + * most @p limit entries. Only the nodes on the active path are loaded; * sibling subtrees are never touched. - * - * @param store KV backend. - * @param root_hex Current root hash. - * @param offset Zero-based logical tuple offset. - * @param limit Maximum number of hashes to return. - * @return Hex hash strings in sorted order. Empty when past the end. */ - static std::vector Page(IStorageBackend& store, - const std::string& root_hex, - size_t offset, - size_t limit); + static std::vector Page(IStorageBackend& store, + const std::string& root_hex, + size_t offset, + size_t limit); private: - using Hash32 = std::array; + struct LeafEntry { + Key key; + Hash32 payload; + }; struct LeafNode { - std::vector hashes; // sorted ascending, len ≤ B + std::vector entries; }; - // Wire: 8-byte leaf_count | 32-byte min_hash | 32-byte child_hash struct ChildEntry { - uint64_t leaf_count; // number of tuple hashes in this subtree - Hash32 min_hash; // smallest tuple hash in the subtree - Hash32 child_hash; // content-addressed hash of the child node + uint64_t leaf_count; + Key min_key; + Hash32 child_hash; }; struct InternalNode { - std::vector entries; // sorted by min_hash, len ≤ B + std::vector entries; }; // Wire format @@ -113,34 +151,32 @@ private: static InternalNode decode_internal(const std::vector& bytes); static bool is_leaf_bytes(const std::vector& bytes); - // Hex / binary - static Hash32 hex_to_bin(const std::string& hex); - static std::string bin_to_hex(const Hash32& bin); - // Storage helpers static std::vector load_node(IStorageBackend& store, const std::string& hash_hex); static std::string store_leaf(IStorageBackend& store, const LeafNode& n); static std::string store_internal(IStorageBackend& store, const InternalNode& n); - // Returns the minimum hash of the subtree rooted at node_hex. - static Hash32 subtree_min(IStorageBackend& store, const std::string& node_hex); + /** @brief Returns the smallest key in the subtree rooted at @p node_hex. */ + static Key subtree_min_key(IStorageBackend& store, const std::string& node_hex); + + /** @brief Routes a key to the rightmost child whose min_key ≤ target. */ + static size_t route(const InternalNode& node, const Key& target); - // Recursive insert result: new node hash, subtree leaf count, optional split. struct InsertResult { std::string new_hash; uint64_t leaf_count = 0; bool did_split = false; uint64_t split_leaf_count = 0; - Hash32 split_min_hash = {}; + Key split_min_key{}; std::string split_hash; }; static InsertResult insert_into(IStorageBackend& store, const std::string& node_hex, - const Hash32& tuple_hash); + const Key& key, + const Hash32& payload); - // Recursive remove result: new node hash (empty = node gone), leaf count. struct RemoveResult { std::string new_hash; uint64_t leaf_count = 0; @@ -148,17 +184,17 @@ private: static RemoveResult remove_from(IStorageBackend& store, const std::string& node_hex, - const Hash32& tuple_hash); + const Key& key); - // Page collection — offset consumed as we descend. static void page_from(IStorageBackend& store, const std::string& node_hex, size_t& offset, size_t limit, - std::vector& out); + std::vector& out); - // Find which child to route into (rightmost whose min_hash ≤ target). - static size_t route(const InternalNode& node, const Hash32& target); + static std::optional get_from(IStorageBackend& store, + const std::string& node_hex, + const Key& key); }; } // namespace nt diff --git a/include/MultigroupCodec.h b/include/MultigroupCodec.h new file mode 100644 index 0000000..50f7bb8 --- /dev/null +++ b/include/MultigroupCodec.h @@ -0,0 +1,89 @@ +#pragma once + +#include "IStorageBackend.h" + +#include +#include +#include + +/** + * @file MultigroupCodec.h + * @brief Thin facade over Merkle for multigroup snapshots. + * + * A multigroup snapshot is a `Merkle` B-tree mapping each + * relation name to that relation's merkle root. The snapshot identifier is + * the hex hash of the tree's root node — the same path-localised content + * addressing used at the tuple level inside each relation. + * + * Stored relations and ephemeral relations are represented uniformly: only + * the relation's name and its current merkle_root participate in the tree, + * regardless of how that root was derived. + * + * The codec used to be a flat `SHA256(sorted [(name, root)])` over a single + * blob. That collapsed all relations into one rehash on any mutation. With + * the merkle B-tree, a single relation update touches `O(log_B(n_rels))` + * nodes on the way to the new root — sibling subtrees stay byte-identical. + * + * `RelationEntry` is `(relation_name, relation_root_hex)`. Both forms are + * hex strings on the wire; the codec hex-decodes internally before handing + * payloads to `Merkle`. + */ + +namespace nt::MultigroupCodec +{ + /** @brief One entry in a multigroup snapshot: (relation_name, root_hex). */ + using RelationEntry = std::pair; + + /** + * @brief Build a multigroup tree from a list of (name, root) entries. + * + * Each `Insert` advances the root through `O(log_B)` nodes. The final + * root hash is the snapshot identifier. The list need not be pre-sorted — + * the merkle B-tree imposes order intrinsically. + * + * @param store KV backend; receives all node blobs. + * @param relations Entries to load. Duplicates collapse to the last value. + * @return Root node hash (empty string when `relations` is empty). + */ + std::string Build(IStorageBackend& store, + const std::vector& relations); + + /** + * @brief Enumerate all (name, root_hex) pairs at a multigroup root. + * + * Pages the entire tree (offset 0, no limit). Returned entries are in + * key-sorted order. Empty input root yields an empty list. + */ + std::vector List(IStorageBackend& store, + const std::string& root_hex); + + /** + * @brief Insert or overwrite one (relation_name → root_hex) entry. + * + * Equivalent to `Merkle::Insert` after hex-decoding the + * payload. The caller threads the returned root hash through subsequent + * mutations. Pass an empty `root_hex` for the prior-state argument to + * start from an empty tree. + */ + std::string InsertOne(IStorageBackend& store, + const std::string& root_hex, + const std::string& relation_name, + const std::string& relation_root_hex); + + /** + * @brief Remove one relation entry from the multigroup tree. + * + * Returns the new root hash; empty when the tree becomes empty. + */ + std::string RemoveOne(IStorageBackend& store, + const std::string& root_hex, + const std::string& relation_name); + + /** + * @brief Look up one relation's root hex by name. + * @return Hex root, or empty string when the name is absent. + */ + std::string Lookup(IStorageBackend& store, + const std::string& root_hex, + const std::string& relation_name); +} diff --git a/include/NamespaceReferenceManager.h b/include/NamespaceReferenceManager.h index 0bf00bc..dd91297 100644 --- a/include/NamespaceReferenceManager.h +++ b/include/NamespaceReferenceManager.h @@ -1,6 +1,11 @@ #pragma once #include "Api.h" +#include "IStorageBackend.h" +#include "ObjectManager.h" + +#include +#include /** * @file NamespaceReferenceManager.h @@ -16,8 +21,9 @@ namespace nt * This manager is the reparse layer of the namespace. Its design mirrors the * ReactOS ParseProcedure / STATUS_REPARSE mechanism: a namespace entry whose * type carries a ParseProcedure can redirect name resolution to a different - * path, allowing branch references and views to appear as first-class objects - * in the namespace without exposing their physical storage paths directly. + * path, allowing branch references and ephemeral relations to appear as + * first-class objects in the namespace without exposing their physical + * storage paths directly. * * **Branch references.** * A path such as `/refs/branch/main` is a namespace entry backed by a @@ -27,13 +33,15 @@ namespace nt * object itself with WRITE access, which is the sole contention point for that * branch. * - * **View resolution.** - * A view is an ephemeral RELATION whose ParseProcedure reparses to its base - * relations internally on behalf of the runtime. The caller's handle and access - * mask remain bound to the view. The base relations are accessed only via the - * view's own type callbacks; the caller never receives a handle on them and - * does not need explicit permission on them. Capability security is enforced at - * the view boundary, not the base relation boundary. + * **Ephemeral relation resolution.** + * An ephemeral relation produces tuples through a generator function rather + * than physical storage; the generator may query base relations on behalf + * of the runtime to materialise its output. The caller's handle and access + * mask remain bound to the ephemeral relation. Base relations are accessed + * only via the ephemeral relation's own type callbacks; the caller never + * receives a handle on them and does not need explicit permission on them. + * Capability security is enforced at the ephemeral-relation boundary, not + * the base relation boundary. * * **Atomic multi-reference updates.** * Updating multiple references simultaneously (e.g. advancing both `main` and @@ -43,9 +51,10 @@ namespace nt * the batch is aborted. This preserves audit consistency. * * **Cycle guard.** - * View definitions may reference other views, and branch aliases may chain. - * Name resolution must track reparse depth and return an error after a bounded - * number of iterations to prevent infinite cycles. + * Ephemeral relation definitions may reference other ephemeral relations, + * and branch aliases may chain. Name resolution must track reparse depth + * and return an error after a bounded number of iterations to prevent + * infinite cycles. * * **Audit branch.** * Audit requires global access dissociated from any data branch. It should be @@ -60,5 +69,42 @@ namespace nt */ class NT_API NamespaceReferenceManager { + public: + /** + * @brief Constructs a NamespaceReferenceManager bound to a registry. + * @param objects Registry used to look up reference objects (branches, + * sessions) during reparse. + * @param storage KV backend; required to read the branch-tree merkle + * nodes when resolving `/system/branches///...` + * paths through to their snapshot. + */ + NamespaceReferenceManager(ObjectManager& objects, + IStorageBackend& storage); + + /** + * @brief Rewrites a logical path through reference reparse rules. + * + * Currently handles branch references: + * /system/branches//... → /system/snapshots//... + * where target_hash is the value stored on the named Branch object. When + * the branch is unborn (target_hash empty) or the rest of the path is + * empty (caller is opening the branch object itself, not something + * under it), the path is returned unchanged. + * + * Session paths (/system/sessions//branches//...) will be + * added when SESSION objects exist; for now they are returned as-is. + * + * A 30-iteration cycle guard mirrors the ReactOS reparse cap. If the + * guard trips the returned path is empty, signaling failure to the + * caller (Find will subsequently miss). + * + * @param path Input logical path components. + * @return Resolved path components, or empty vector on cycle/failure. + */ + std::vector Resolve(std::vector path) const; + + private: + ObjectManager& objects_; + IStorageBackend& storage_; }; } diff --git a/include/ObjectManager.h b/include/ObjectManager.h index e30ff1b..7531079 100644 --- a/include/ObjectManager.h +++ b/include/ObjectManager.h @@ -5,6 +5,7 @@ #include #include +#include #include #include #include @@ -33,8 +34,27 @@ namespace nt virtual ~IObject() = default; }; - /** @brief Abstract registry object representing a multigroup. */ - class Multigroup : public IObject {}; + /** + * @brief Registry object representing a multigroup snapshot. + * + * `merkle_root` is the hex hash of the Merkle root node + * that maps relation_name → relation_merkle_root for this snapshot. + * Updates are path-localised: inserting one tuple advances the root + * through O(log_B) node rewrites, leaving sibling subtrees byte- + * identical. + * + * Every commit produces a new Multigroup entry under + * /system/snapshots/ with one child Relation per leaf at + * /system/snapshots//relations/. Snapshots are + * immutable (disposable=false, exclusive=false); the rest of the + * system refers to them by hash. A Multigroup is eligible for GC + * only when its reference_count drops to zero (no BRANCH_TREE still + * pins it, no pinned cursor still references it). + */ + class Multigroup : public IObject { + public: + std::string merkle_root; + }; /** * @brief Registry object representing a stored relation. * @@ -46,21 +66,107 @@ namespace nt public: std::string merkle_root; }; + /** + * @brief Registry object representing an ephemeral relation. + * + * Ephemeral relations have no tuple storage of their own; tuples are + * produced on demand by the generator function declared in the + * ephemeral_object_type descriptor. They compose into a multigroup's + * tree on equal footing with stored relations — only `merkle_root` + * participates in the Merkle entry for this relation, + * regardless of how that root was derived. + * + * `merkle_root` is the SHA256 hex digest derived from the generator's + * identity, the current schema, and the merkle_roots of the declared + * base relations. Any mutation to structure or rebinding of a base + * produces a new merkle_root, which then propagates into a new + * multigroup snapshot exactly like a tuple insertion in a stored + * relation. + * + * `dependencies` lists the logical paths of base relations this + * ephemeral relation is defined atop of. The lifecycle manager Pins + * each entry while this object is alive, preventing GC of a stored + * relation that still backs an ephemeral one. The dependency list is + * also the foundation for attribute-level provenance tracking added + * later. + * + * @todo Define the merkle_root composition function (hashes the + * generator identity + schema + sorted base merkle_roots). + * Until ephemeral relations are registered through a writer + * path this remains a documentation-only contract. + */ + class EphemeralRelation : public IObject { + public: + std::string merkle_root; + std::vector dependencies; + }; /** @brief Abstract registry object representing a transaction. */ class Transaction : public IObject {}; /** - * @brief A named mutable reference to a multigroup state. + * @brief Registry object representing an active connection's session. * - * The payload field carries the serialized multigroup bytes in whatever - * format the caller registered them with. The C API returns these bytes - * verbatim when a handle to the branch is opened; Sakura is responsible - * for deserializing them into a Multigroup object. + * `connection_context` carries whatever auth/connection metadata the + * caller passed to rnt_session_open. The runtime treats it as an + * opaque pointer; ownership of the pointee is the caller's concern. + * + * `branch_overrides` maps a branch name to the BRANCH_TREE root this + * session should see for that branch, instead of the global HEAD. + * NamespaceReferenceManager::Resolve consults the override first when + * a path of the form /system/sessions//branches//... + * is requested, falling back to the global /system/branches/ + * lookup when no override is present. + * + * The session→branch reference direction is intentional: global + * branches do not track viewing sessions, which keeps the hot path + * cheap. GC of a stale snapshot must walk all sessions' override + * maps to discover live references — amortised cost only paid at GC + * time. A reverse index can be added later if session counts make + * the walk hot. + */ + class Session : public IObject { + public: + void* connection_context = nullptr; + std::map branch_overrides; + }; + + /** + * @brief A named mutable reference to a branch-tree root. + * + * `target_hash` is the merkle_root of a BRANCH_TREE — a + * `Merkle` root mapping `mg_name -> mg_hash`. Path + * resolution walks the branch tree to translate + * `/system/branches//multigroups//relations/` into the + * right `/system/snapshots//relations/`. Empty string + * means the branch has no commits yet (unborn). + * + * Branches are the sole mutable pointer in the system; concurrent + * writers serialize through LifecycleManager::Contention because the + * BRANCH object_type carries exclusive=true. Readers never contend — + * they resolve the branch through its tree to the immutable + * Multigroups and operate on those. */ class Branch : public IObject { public: std::string name; - std::vector payload; + std::string target_hash; + }; + + /** + * @brief Registry object for a branch-tree blob. + * + * `merkle_root` is the Merkle root hash of the (mg_name, + * mg_hash) tree this entry indexes. The same blob is referenced by + * every BRANCH and session override sharing this tip. Lifecycles: + * + * - Pinned once per referencing BRANCH or session override. + * - When its reference count drops to zero, + * LifecycleManager::CascadeBranchTree pages the tree and unpins + * each multigroup it references before unregistering the entry. + */ + class BranchTree : public IObject { + public: + std::string merkle_root; }; /** @@ -145,8 +251,9 @@ namespace nt * * - `handle_count` — open sessions holding a cursor or handle on this object. * Managed exclusively by LifecycleManager::Monitor / Unmonitor. - * - `reference_count` — structural dependencies such as a view referencing its - * base relations, or a cursor pinned to an immutable snapshot version. + * - `reference_count` — structural dependencies such as an ephemeral relation + * referencing its base relations, or a cursor pinned to an immutable snapshot + * version. * Managed by LifecycleManager::Pin / Unpin (not yet implemented). * * All snapshot versions are immutable. An insertion or deletion produces a new @@ -166,8 +273,8 @@ namespace nt struct registry_head { /** * Structural dependency count. Non-zero while another registry object - * references this one (e.g. a view depending on a base relation, or a - * cursor pinned to a snapshot version). + * references this one (e.g. an ephemeral relation depending on a base + * relation, or a cursor pinned to a snapshot version). * @todo Implement via LifecycleManager::Pin / Unpin. */ uint32_t reference_count = 0; @@ -216,5 +323,19 @@ namespace nt * @return Borrowed pointer to the matching entry, or nullptr when not found. */ registry* Find(const std::vector object_path); + + /** + * @brief Removes the entry registered at @p object_path, if any. + * + * Splices the matching node out of the registry list and frees its + * owned object and head. No reference-count checks are performed — + * the caller is responsible for releasing handles and pins before + * calling this. Intended for disposable objects (sessions today, + * other disposables once GC lands in step 6). + * + * @param object_path Logical path of the entry to remove. + * @return True when an entry was removed, false when nothing matched. + */ + bool Unregister(const std::vector& object_path); }; } diff --git a/include/PermissionsManager.h b/include/PermissionsManager.h index 2db1784..6718f9f 100644 --- a/include/PermissionsManager.h +++ b/include/PermissionsManager.h @@ -58,10 +58,10 @@ namespace nt * hold of an object, since that might produce significant overhead. * * Note that the permissions systems also rely on objects with capabilities, - * so imagining the case a view (ephemeral relation) is created based on - * 3 other stored relations, while you can access the view, you cannot directly - * access the other 3 relations. You need explicit permission to create a handle - * on the others. + * so imagining the case an ephemeral relation is created based on + * 3 other stored relations, while you can access the ephemeral relation, + * you cannot directly access the other 3 relations. You need explicit + * permission to create a handle on the others. * * Here's an example tree: * /system @@ -79,7 +79,8 @@ namespace nt * /permissions * /multigroups/coffee_shop/relations/user {descriptor : [write, read]} * - * Meaning that `peter` has access to read the `user_and_order` ephemeral relation, but cannot open a handle on `user` and `order`. + * Meaning that `peter` has access to read the `user_and_order` ephemeral + * relation, but cannot open a handle on `user` and `order`. * * @param object Object being accessed. * @param connection_context Connection metadata for the caller. diff --git a/include/RNT_C_API.h b/include/RNT_C_API.h index ddf6a97..e6455ba 100644 --- a/include/RNT_C_API.h +++ b/include/RNT_C_API.h @@ -46,15 +46,15 @@ typedef void* rnt_handle_t; typedef void* rnt_cursor_t; /* ------------------------------------------------------------------ */ -/* Runtime lifecycle */ +/* Runtime lifecycle */ /* ------------------------------------------------------------------ */ /** - * @brief Initialises the RNT runtime with the selected storage backend. + * @brief Initializes the RNT runtime with the selected storage backend. * * Must be called before any other API function. Once the runtime is - * successfully initialised, subsequent calls are no-ops and return 0. - * If initialisation fails (returns negative), the call may be retried + * successfully initialized, subsequent calls are no-ops and return 0. + * If initialization fails (returns negative), the call may be retried * with corrected parameters — the runtime is left in a clean state. * * @param driver Storage driver to use: "sqlite" or "memory". @@ -82,6 +82,59 @@ int rnt_init(const char* driver, const char* storage_path); */ int rnt_firewall(const char* auth_method, char** claims_out); +/* ------------------------------------------------------------------ */ +/* Session lifecycle */ +/* ------------------------------------------------------------------ */ + +/** + * @brief Opens a session and registers it at /system/sessions/. + * + * The runtime mints a random 256-bit hex hash for the session; the caller + * has no influence over the value. The returned string is the opaque + * identifier required by every other rnt_session_* call. + * + * @param connection_context Caller-owned pointer carried on the session. + * The runtime treats it as opaque; ownership of + * the pointee remains with the caller. + * @param session_hash_out Set to a heap-allocated 64-char hex string. + * Release with rnt_free_string(). + * @return 0 on success, negative on error. + */ +int rnt_session_open(void* connection_context, char** session_hash_out); + +/** + * @brief Closes a session, unregistering it from /system/sessions/. + * + * After this call the session hash is invalid; subsequent rnt_session_* or + * resolver lookups against it will fail. Branch overrides held by the + * session are dropped. + * + * @param session_hash Hash returned by rnt_session_open. + * @return 0 on success, negative when the hash does not match an active session. + */ +int rnt_session_close(const char* session_hash); + +/** + * @brief Sets a per-session override for a branch. + * + * While the override is in effect, paths resolved through + * /system/sessions//branches//... point at + * /system/snapshots//... regardless of where the global branch + * HEAD currently sits. Pass an empty string for @p target_hash to remove + * the override and resume falling back to the global branch. + * + * Non-empty target hashes must correspond to an existing + * /system/snapshots/ entry; otherwise the call fails. + * + * @param session_hash Session identifier. + * @param branch_name Branch the override applies to (e.g. "main"). + * @param target_hash Snapshot hash to bind, or "" to clear. + * @return 0 on success, negative on error. + */ +int rnt_session_set_branch(const char* session_hash, + const char* branch_name, + const char* target_hash); + /* ------------------------------------------------------------------ */ /* Handle lifecycle */ /* ------------------------------------------------------------------ */ @@ -107,41 +160,41 @@ rnt_handle_t rnt_open_handle(const char* path, const char* claims); int rnt_close_handle(rnt_handle_t handle); /** - * @brief Reads the raw payload bytes stored in a BRANCH object. + * @brief Reads the current branch-tree root hash from a BRANCH object. * - * Only valid for handles opened on BRANCH objects. The caller uses the bytes - * to reconstruct the in-memory multigroup (e.g. via Sakura's deserializer). + * Only valid for handles opened on BRANCH objects. The returned string is + * the merkle_root of the BRANCH_TREE this branch currently points at — a + * `Merkle` root mapping mg_name → mg_hash. An empty string + * indicates an unborn branch with no commits yet. * - * @param handle Handle to a BRANCH object. - * @param payload_out Set to a heap-allocated copy of the payload bytes. - * Release with rnt_free_bytes(). - * @param len_out Set to the number of bytes in payload_out. + * @param handle Handle to a BRANCH object. + * @param target_hash_out Set to a heap-allocated copy of the target hash + * (possibly empty). Release with rnt_free_string(). * @return 0 on success, negative when the handle is not a BRANCH. */ -int rnt_branch_payload(rnt_handle_t handle, - uint8_t** payload_out, - size_t* len_out); +int rnt_branch_target(rnt_handle_t handle, char** target_hash_out); /** - * @brief Writes new payload bytes into the BRANCH object referenced by handle. + * @brief Atomically advances a branch to point at a new branch-tree root. * - * Updates the in-memory branch object. Callers are responsible for persisting - * the multigroup state to the storage backend separately via tuple link - * operations. + * The new hash must already exist as a content-addressed blob in the KV + * store — branch-tree roots are produced by mutating calls (rnt_link_tuple, + * rnt_register_relation, …) and cannot be invented externally. Pass an + * empty string to reset the branch to unborn. * * Write exclusion is structural: BRANCH objects carry @c exclusive=true in * their object_type, so LifecycleManager::Contention prevents a second handle * from being opened while a writer holds the branch. AUTH_CLAIM::WRITE is not * checked at the C API boundary. * - * @param handle Open BRANCH handle. - * @param payload New serialized multigroup bytes. - * @param len Number of bytes in payload. - * @return 0 on success, negative on error. + * @param branch_path Slash-separated branch path, e.g. "/system/branches/main". + * @param new_hash Branch-tree root to advance to (64-char lowercase hex), + * or "" to reset to unborn. + * @return 0 on success, negative when the branch is not found, the type is + * not BRANCH, or @p new_hash is non-empty but no matching blob + * exists in the KV store. */ -int rnt_branch_set_payload(rnt_handle_t handle, - const uint8_t* payload, - size_t len); +int rnt_branch_advance(const char* branch_path, const char* new_hash); /* ------------------------------------------------------------------ */ /* Object registration */ @@ -153,24 +206,71 @@ int rnt_branch_set_payload(rnt_handle_t handle, * Idempotent: if an object already exists at the path, the call succeeds * without re-registering. * - * @param path Slash-separated path, e.g. "/system/branches/main/relations/foo". + * @param path Slash-separated path of the form + * "/system/branches//multigroups//relations/". * @return 0 on success, negative on error. */ int rnt_register_relation(const char* path); /** - * @brief Registers a BRANCH object at the given path with an initial payload. + * @brief Registers a BRANCH object at the given path pointing at a branch-tree root. * * If a BRANCH already exists at this path, returns 0 without modifying it. - * - * @param path Slash-separated path, e.g. "/system/branches/main". - * @param payload Initial serialized multigroup bytes (may be NULL for empty). - * @param payload_len Byte count of payload. + * When @p target_hash is non-NULL and non-empty it must already exist as a + * content-addressed blob in the KV store (produced by an earlier mutation + * through the same runtime); otherwise the call fails. Pass NULL or "" to + * register an unborn branch. + * + * @param path Slash-separated path, e.g. "/system/branches/main". + * @param target_hash Branch-tree root this branch points at (may be NULL + * or "" for unborn). * @return 0 on success, negative on error. */ -int rnt_register_branch(const char* path, - const uint8_t* payload, - size_t payload_len); +int rnt_register_branch(const char* path, const char* target_hash); + +/** + * @brief Lists all relations of a specific multigroup under a branch. + * + * Returns a newline-delimited string of "name\troot_hash" pairs, one per + * relation in the named multigroup at the branch's current tree. An unborn + * branch or an mg absent from the branch tree yields an empty string. The + * caller must release the string with rnt_free_string(). + * + * @param branch_mg_path Slash-separated path of the form + * "/system/branches//multigroups/". + * @param out Set to a heap-allocated "name\troot\n" string. + * Release with rnt_free_string(). NULL on error. + * @return 0 on success, negative when the path shape is wrong or the branch + * is not found. + */ +int rnt_list_relations(const char* branch_mg_path, char** out); + +/** + * @brief Lists all multigroups bound to a branch. + * + * Reads the branch-tree root from `/system/branches/` and pages each + * (mg_name, mg_hash) entry. Returns "name\thash\n" lines. Unborn branches + * yield an empty string. + * + * @param branch_path Slash-separated branch path, e.g. "/system/branches/main". + * @param out Heap-allocated string; release with rnt_free_string(). + * @return 0 on success, negative when the branch is not found. + */ +int rnt_list_branch_multigroups(const char* branch_path, char** out); + +/** + * @brief Lists all relations stored in a specific snapshot. + * + * Reads the multigroup codec directly from the snapshot at + * /system/snapshots/ without following any branch HEAD. + * Use this when the desired snapshot hash is already known (e.g. detached + * checkout). Returns the same "name\troot_hash\n" format as rnt_list_relations. + * + * @param snapshot_hash 64-char hex hash of the snapshot. + * @param out Set to heap-allocated string. Release with rnt_free_string(). + * @return 0 on success, negative when the snapshot is not registered. + */ +int rnt_list_snapshot_relations(const char* snapshot_hash, char** out); /* ------------------------------------------------------------------ */ /* Tuple storage */ @@ -235,21 +335,6 @@ int rnt_clear_relation(const char* relation_path); */ int rnt_relation_root(const char* relation_path, char** root_hash_out); -/** - * @brief Writes a Merkle root hash into a relation's ObjectManager entry. - * - * Called by Sakura's open_branch during multigroup reconstruction: after - * deserializing the branch payload, OCaml calls this function once per - * relation to restore the persisted Merkle root into the in-memory - * ObjectManager so that subsequent cursors see the correct tuple set. - * - * @param relation_path Slash-separated relation path. - * @param root_hash 64-character hex Merkle root, or empty string to mark - * the relation as empty. - * @return 0 on success, negative when the relation is not found. - */ -int rnt_set_relation_root(const char* relation_path, const char* root_hash); - /* ------------------------------------------------------------------ */ /* Cursor and VM */ /* ------------------------------------------------------------------ */ @@ -300,7 +385,7 @@ typedef void* rnt_plan_t; * plan and released when the resulting VM cursor is closed. * * @param relation_path Absolute slash-separated path to the relation, e.g. - * "/system/branches/main/relations/public:users". + * "/system/branches/main/multigroups/warehouse/relations/public:users". * @return Plan node, or NULL when the relation does not exist or cannot be opened. */ rnt_plan_t rnt_plan_scan(const char* relation_path); diff --git a/include/Types.h b/include/Types.h index f7eadff..edf4297 100644 --- a/include/Types.h +++ b/include/Types.h @@ -20,37 +20,74 @@ enum OBJECT_TYPE { TRANSACTION, /** * A relation whose tuples are produced on demand by a generator function - * rather than read from physical storage. Cardinality may be finite (e.g. - * a projected stored relation) or AlephZero (e.g. the eq builtin). The - * object_type for this label must be an ephemeral_object_type. + * rather than read from physical storage. Behaves like a RELATION in every + * other respect: owns a `merkle_root`, has mutable schema, composes into its + * multigroup's hash, and may be opened, scanned, and pinned through the + * same handle pipeline. + * + * The generator receives unsigned-int paginators (offset, limit) plus any + * bound argument values written by an upstream JOIN, and yields tuples. + * Cardinality may be finite (e.g. a projection over a stored relation) or + * AlephZero (e.g. the eq builtin). The object_type for this label must be + * an ephemeral_object_type. + * + * Tracked as a distinct label — rather than collapsed into RELATION — + * for three reasons: + * 1. Sakura distinguishes generated relations as a separate subclass at + * the wire layer, even though the runtime treats them uniformly. + * 2. They have no physical tuple-storage backend; reads always go + * through the generator. + * 3. They carry a dependency list of base relation paths they are + * defined atop of. This drives structural reference counting (a + * base relation cannot be GC'd while an ephemeral relation depends + * on it) and is the foundation for attribute-level provenance + * tracking added later. */ EPHEMERAL_RELATION, /** - * A named mutable reference to a multigroup state, analogous to a git - * branch. A BRANCH object carries an opaque payload (serialized multigroup - * bytes) that the caller — in practice Sakura — deserializes on open. + * A named mutable reference to a multigroup snapshot, analogous to a git + * branch. A BRANCH object carries a `target_hash` — the merkle_root of + * the snapshot it currently points at — and nothing else. * * Branch objects are the entry point for database connections: a client - * opens a handle to /system/branches/, reads the payload bytes to - * reconstruct the multigroup in memory, and holds the handle for the - * duration of the session. + * opens a handle to /system/branches/, reads target_hash, and uses + * that hash to open the snapshot at /system/snapshots/. Multigroup + * state is reconstructed by walking the content-addressed graph from + * that snapshot, not by deserializing bytes attached to the branch. * * The `exclusive` flag on the object_type should be set to true so that * LifecycleManager::Contention serializes concurrent writers. */ BRANCH, /** - * A named query plan stored in the object registry. A VIEW object carries - * the serialized plan definition and the multigroup hash at definition time. - * No handles to physical storage are kept open in the VIEW object itself. - * Each time the view is opened, fresh relation handles and cursors are - * created for the duration of that execution, then released on close. + * A per-connection runtime context. SESSION objects own the + * connection_context pointer (auth metadata, etc.) and a map of per-session + * branch overrides: `branch_name -> target_hash`. Overrides let one + * connection observe a different snapshot for a branch than the global + * HEAD without affecting other sessions. + * + * Sessions are identified by random 256-bit hex hashes minted at + * rnt_session_open. The hash is opaque to the caller and is the only + * handle for subsequent rnt_session_* calls. SESSION objects live at + * /system/sessions/; the resolver consults + * /system/sessions//branches/ first and falls back to the global + * /system/branches/ when there is no override. + */ + SESSION, + /** + * The content-addressed Merkle root of a branch's multigroup map. + * A BRANCH points at a BRANCH_TREE via target_hash; the tree maps + * `mg_name -> mg_hash` and is paged at resolve time to translate + * `/system/branches///` into `/system/snapshots//`. * - * @todo Implement ObjectManager::View, rnt_register_view, and the - * open-view path in HandlerManager. Views are reserved in the type - * system but have no runtime support yet. + * BRANCH_TREE objects live at `/system/branch_trees/`. They are + * immutable (disposable=false, exclusive=false) and pinned by the BRANCH + * objects that reference them; the mgs they reference are in turn pinned + * by the BRANCH_TREE via LifecycleManager::CascadeBranchTree at GC time. + * The same blob is reused across all branches and session overrides + * that share a tip. */ - VIEW + BRANCH_TREE }; /** @brief Operations that may be supported by an object type. */ -- cgit v1.2.3