`visitDifferences` had no test coverage: `LedgerMaster::populateFetchPack` is
its only caller, and nothing exercised that path, so the private `hasLeafNode`
and `hasInnerNode` it consults were untested too. Codecov flagged the resulting
gap against an unrelated refactor, since that commit happened to touch a line
inside `hasLeafNode`.
Four cases: a map missing one item reports only the nodes on that item's path,
an identical map reports nothing, a null comparison map reports every node the
plain `visitNodes` walk sees, and a callback returning false stops the walk
where `populateFetchPack` would stop once a pack is full.
The first case uses 64 shared items rather than a couple, so the shared leaves
build inner nodes of their own and the walk has whole matching subtrees to
skip. Verified by mutation: with only two shared items, breaking
`hasInnerNode` to always claim a match left every test passing, since the tree
was too shallow for that branch to be taken. It also asserts that some inner
nodes are reported but not all, which is what distinguishes skipping a subtree
from walking it. Breaking `hasLeafNode` in either direction, or `hasInnerNode`,
now fails the case.
The maps are hashed via `getHash` before being compared, since node hashes are
computed on demand and `visitDifferences` returns early while the root hash is
still zero. Without that the walk visits nothing and every assertion here
would hold vacuously.
Five sites copied the top entry out and then popped it. `SHAMapTreeNodePtr` is
refcounted, so each copy bumped its atomic strong-ref count; `release()` moves
the pointer out instead, a plain pointer swap with no atomic. `SHAMapNodeID`
also derives from `CountedObject`, but `CountedObject` declares no move
constructor, so moving a `SHAMapNodeID` still runs its copy constructor;
`release()` saves nothing on the ID half of the pair. `dirtyUp` and `delItem`
walk up to 64 levels per insert or delete on the ledger write path, so this
removes up to 64 atomic operations per call, not 128. The two sites that read
without popping now bind a reference rather than copying.
`dirtyUp` and `delItem` both drop a `dynamicPointerCast`/null check for a
static cast, on the reasoning that by the time either receives the stack,
`addGiveItem`/`updateGiveItem` have already consumed the terminal leaf entry
via `release()`, so every remaining entry is provably an inner node. That
reasoning holds today, but an `XRPL_ASSERT` is a no-op under `NDEBUG`, so
both get a real `UNREACHABLE`-guarded check instead: a release build that
somehow violated the invariant would otherwise write through a
misinterpreted node via `setChild`, silent memory corruption in place of the
clean crash `dynamicPointerCast` used to produce. `updateGiveItem`'s own
cast needed the same treatment for a different reason: an absent tag leaves
an inner node on top of the stack, and the cast that followed the assertion
there would have reinterpreted an `SHAMapInnerNode` as a `SHAMapLeafNode`.
Replaced with `if (!top->isLeaf()) return false;`, pinned by a regression
test.
The `std::move` these sites previously applied to
`staticPointerCast`/`dynamicPointerCast` was dropped rather than fixed: both
only had a `TT const&` overload, so the move bound to that const ref and
copied anyway, silently defeating the `SHAMapTreeNodePtr` refcount saving
described above. Adds the missing rvalue overload to each, tied to
`SharedIntrusive<TT>&&` rather than a bare `TT&&` so it cannot also bind to
an lvalue in preference to the const-ref overload, and restores `std::move`
at the three call sites that own a soon-to-be-discarded pointer.
The stack asserted its preconditions and then went ahead regardless. Asserts
expand to `assert`, so in a release build every one of those was a no-op in
front of the operation it was guarding: reading or popping an empty
`std::stack` is undefined, `pushChild`'s out-of-range branch check was missing
entirely, and `getChildNodeID` throws `std::logic_error` at leaf depth. None
of these conditions are reachable through any of `SHAMap`'s public entry
points today, but the failure modes if they ever did happen would be
disproportionate: an out-of-range branch would silently corrupt a node ID
instead of failing loudly, and a `logic_error` reaching an unguarded call
chain would abort the process, since nothing in this codebase catches it.
Pushes now return false instead of throwing or silently corrupting the ID, and
reads degrade to a null node rather than undefined behavior. `[[nodiscard]]`
makes an unchecked push a compile error. Each new guard is marked
`UNREACHABLE` rather than left implicitly untested, since no test fixture in
this suite can reach these paths without building a deliberately corrupt map.
`pushRoot` gets the same conversion as every sibling method; it was the one
push still asserting instead of returning false.
`walkTowardsKey`'s two modes (with and without a caller-supplied stack) must
fail at the same node and leave the stack in a state every caller already
knows how to handle; on failure the stack is now cleared via a restored
`clear()`, and a restored `pushCurrent` lambda keeps the loop-entry and
post-loop push-and-clear logic from being duplicated. It also stops deriving
each node ID twice: a caller-supplied stack now reads the ID `pushNode` just
computed off `stack->top().second`, instead of a redundant local copy that
additionally went stale once the loop exited. `belowHelper` and
`peekNextItem` finally get the fallback `top()`'s own docstring promises: both
read `stack.top()` right after an assert-only emptiness check, with no
fallback for release builds, so both now return early on an empty stack
instead of dereferencing a null `SHAMapTreeNodePtr`.
`pushChild`'s hard guard also only checked the parent's depth against
`kLeafDepth`, one level too permissive for an inner child: a parent at 63
passed the check, then pushed an inner child at 64 with only a debug-only
assert catching it, the exact gap this commit exists to close. Tightened to
require depth + 1 below `kLeafDepth` for an inner child, with
`walkTowardsKey`'s no-stack path given the identical tightening so a
malformed map fails at the same node in both modes.
The two functions were near duplicates: walk to the key, then look for the
nearest leaf on one side. Only the scan direction, the comparison deciding a
leaf qualifies, and whether to take the first or last leaf below the subtree
differed, exactly the distinction `BelowDirection` already draws for
`belowHelper`, so the pair collapse into one parameterised walk. Also drops
the stale `// TODO: what to return here?` above `lowerBound`'s `return end()`:
no predecessor is the correct answer for the smallest key, and the tests pin
it.
Existing coverage only exercised `boundHelper`'s inner-node branch, every test
map had at least three items, so the root was always an inner node and the
leaf branch at the top of the function was never reached with a real answer to
give. Adds coverage for a single-item map, where the leaf branch alone decides
the outcome, and an empty map, where the scan must find nothing on every
branch before falling through to `end()`.
Fixes the single-item test's own comment, which claimed `root_` becomes a
leaf, when in fact `root_` stays the inner node it was constructed with for
any map built via `addItem`; only a single-item map synced from a peer
(`addRootNode`) ever replaces `root_` with a leaf directly.
`belowHelper` built each stack entry's `SHAMapNodeID` from `branch`, the branch
used to reach the subtree root, rather than `childBranch`, the branch it had
just descended. The resulting IDs carried a correct depth but named a
different subtree, and nothing rejected them: such an ID has a legal depth and
a legal mask, so only comparing it against an actual leaf key exposes the
mismatch. The affected stacks feed read-only traversals whose consumers use
only the depth, so no ledger state, hash, or peer message was affected, but
any future consumer of `getNodeID()` would have silently received the wrong
position.
Rather than fix the one call, make the mistake unrepresentable.
`NodePathStack` replaces the bare `std::stack` and refuses to accept an ID at
all: every push takes the branch being descended and derives the ID itself, so
a node and its ID cannot disagree. `isPrefixOf` assertions on each push catch a
wrong branch at the point it happens rather than wherever the ID is later
read. Leaf entries now keep the depth they were reached at instead of a
normalized `kLeafDepth`, which is what lets those assertions hold:
`addGiveItem` splits a leaf from the depth it actually sits at.
The new traversal tests fail on the previous code: reverting the branch
derivation trips the leaf-key assertion on the first iteration. Also adds a
`deepFanOutKeysAtLeafDepth` helper and mirrors them against it, since the
existing `deepFanOutKeys`'s fan-out at the 6th nibble keeps its tree only
about 6 levels deep and never exercised the depth-63/64 code these tests are
meant to protect, plus a case that collapses the entire depth-63 chain of
single-child inner nodes into a leaf on the final delete, which the
every-other-key deletion pattern the other new tests use never triggers.
`selectBranch` reads the key byte at `depth / 2`, which is out of bounds for a
32-byte key once the depth reaches 64. Every branch selection in the map
funnels through here, so this is the one place a stray depth can turn into a
bad read. Assert the precondition for callers, then clamp anyway: a wrong
answer for an input that should never occur is better than reading past the
buffer. Verified under ASan that the unclamped form reads one byte past a
32-byte allocation while the clamped form does not.
`depthMask`'s own 65-entry table had the same exposure one level up, reachable
through the public `createID` factory rather than only from inside the map. A
depth past `kLeafDepth` indexed that table out of bounds, confirmed under ASan
as a 4-byte `global-buffer-overflow` immediately after `kMasks`. Both places
that can set a depth now clamp it: the constructor, which is the single point
every `SHAMapNodeID`'s `depth_` passes through, and `createID`, which needs its
own bound because it picks the mask while evaluating the constructor's
argument, before the constructor body could correct anything.
Clamping rather than throwing, which is what `getChildNodeID` does for the
analogous case: `createID` is reached from `getSHAMapNodeID` with a
peer-supplied depth, and two of that function's three callers
(`InboundTransactions::gotData`, `PeerImp::onMessage`) sit on paths with no
handler between them and a thread boundary, so a throw there would end the
process rather than the message. Clamping also has to fix up `id_` alongside
`depth_`, since a node ID whose id and depth disagree fails the invariant every
read of `id_` relies on. Leaving the depth unclamped would additionally let
`getRawString` narrow it to a byte, turning depth 256 into a node claiming to
be the root.
`deserializeSHAMapNodeID` gets the same mask check `isPrefixOf` already
performs, pulled into a shared `isPrefixOfAtDepth` helper, and the masking both
it and `createID` perform is now a named `maskedToDepth` rather than a repeated
bitwise-and.
Tests cover the depth-sensitivity of `isPrefixOf`, the guards that must hold
with asserts stripped, that `deserializeSHAMapNodeID` rejects an out-of-range
depth, and the clamp itself under both build configurations (`EXPECT_DEATH`
in a forked process when the assert is live, and the clamped result compared
against depth 63 when it is not). The clamp test also gates on
`ENABLE_VOIDSTAR`, not just `NDEBUG`: under Antithesis instrumentation
`XRPL_ASSERT` routes to a handler that records the hit but never aborts, so a
Debug build with voidstar enabled has `NDEBUG` undefined yet still hits the
same non-fatal assert as a release build, and without this gate would send
that configuration into the `EXPECT_DEATH` arm, where the forked child never
dies and the test fails, breaking the CI job that runs this suite under
`-Dvoidstar=ON`.
The `visitDifferences` guard said an inner node at leaf depth could be seeded by a peer through an
earlier fetch-pack exchange, while the code marks the branch `UNREACHABLE`, which is documented as a
line that must not be reached in normal use or under fuzzing. Both cannot hold: a peer-reachable
assert is a peer-triggered abort. The code is the correct half. `addKnownNode` marks the map invalid
instead of hooking such a node in, fetch-pack blobs are checked against their content hash in
`LedgerMaster::getFetchPack`, and the parent child-hash slots they attach to chain up to a validated
root, so provoking this needs a preimage rather than a crafted message.
The comment now attributes the branch to a defect or a corrupt store, and records why the node is
still reported into the pack before its children are skipped: the wire form of an inner node carries
only child hashes, so the bad depth is never transmitted, and the recipient hooks blobs in by hash at
positions its own traversal picks. Withholding it would instead surface as a peer that cannot
complete a ledger, with nothing to diagnose locally.
The `hasLeafNode` comment credited its caller with a bound that does not apply. That guard limits the
depth of the caller's own traversal, whereas `hasLeafNode` runs on the map passed in and descends
from that map's root, so the check here is the only thing between a malformed map and the throw in
`getChildNodeID`, not a second line of defense. `hasInnerNode` is the one bounded by its caller.
Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
The check that the terminal leaf of a proof path actually holds the key being proved had no test
covering it, because the substitution it guards against cannot be built by swapping a leaf under a
genuine root: the hash comparison one level up rejects that first.
This test forges the root instead. It puts a genuine leaf from elsewhere in the map at the bottom of
a two-element path and wraps it in an inner node whose branch for the proved key carries that leaf's
hash, so the chain up to the root hash validates even though the leaf belongs to another key. A
control case runs the same forged root over the proved key's own leaf and expects acceptance, which
pins the leaf key comparison as the only reason the substituted path is rejected.
Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com>
A SHAMap has 65 levels, and nibbles run out at level 64: `selectBranch` indexes
the key byte at `depth / 2`, so at depth 64 it reads byte 32 of a 32-byte key.
Only the leaf terminating a path may sit at that depth, but proof path nodes
come off the wire, so a peer could send 65 hash-chained inner nodes and drive
that read past the end of the buffer.
The existing length bound cannot be tightened to catch this: a path for two
keys sharing all 63 leading nibbles legitimately holds 64 inner nodes plus a
leaf, so 65 elements is valid. The claimed node type at the final depth is the
thing to reject, using `>=` rather than `==` to match the convention every
other `kLeafDepth` comparison in this codebase already follows.
Reachable from `TMProofPathResponse` via `LedgerReplayMsgHandler`; confirmed
under ASan with asserts compiled out that the unguarded read lands one byte
past a 32-byte heap allocation. Also closes a second gap: nothing checked the
terminal leaf's own key against `key`, so the hash chain alone let a peer
substitute any leaf whose subtree hashes matched at every level above it.
Pinned by tests: the 65-element path that must verify for both keys sharing
the deep prefix, and the forged all-inner path that must not.
Also guards `visitDifferences` against an inner node claimed at leaf depth:
`hasLeafNode` only checked the comparison map, not the map being walked, so a
corrupt node in the map under `visitDifferences` itself could still throw
uncaught. Skip such a node's children instead.
