Intrusive SHAMap smart pointers for efficient memory use and lock-free synchronization #5152
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
added 4 commits
October 2, 2024 17:25
This branch has a long history. About two years ago I wrote a patch to remove the mutex from shamap inner nodes (ref: https://github.com/seelabs/rippled/tree/lockfree-tagged-cache). At the time I measured a large memory savings of about 2 gig. Unfortunately, the code required using the `folly` library, and I was hesitant to introduce such a large dependency into rippled (especially one that was so hard to build). This branch resurrects that old work and removes the `folly` dependency. The old branch used a lockless atomic shared pointer. This new branch introduces a intrusive pointer type. Unlike boost's intrusive pointer, this intrusive pointer can handle both strong and weak pointers (needed for the tagged cache). Since this is an intrusive pointer type, in order to support weak pointers, the object is not destroyed when the strong count goes to zero. Instead, it is "partially destroyed" (for example, inner nodes will reset their children). This intrusive pointer takes 16-bits for the strong count and 14-bits for the weak count, and takes one 64-bit pointer to point at the object. This is much smaller than a std::shared_pointer, which needs a control block to hold the strong and weak counts (and potentially other objects), as well as an extra pointer to point at the control block. The intrusive shared pointer can be modified to support for atomic operations (there is a branch that adds this support). These atomic operations can be used instead of the lock when changing inner node pointers in the shamap. Note: The space savings is independent from removing the locks from shamap inner node. Therefor this work is divided into two phases. In the first phase a non-atomic intrusive pointer is introduced and the locks are kept. In a second phases the atomic intrusive pointer could be introduced and the locks will be removed. Some of the code in this patch is written with the upcoming atomic work in mind (for example, using exchange in places). The atomic intrusive pointer also requires the C++ library to support `atomic_ref`. Both gcc and msvc support this, but at the time of this writing clang's library does not. Note: Intrusive pointer will be 12 bytes. The shared_ptr will be around 40 bytes, depending on implementation. When measuring memory usage on a validator, this patch resulted in between a 10 and 15% memory savings.
Codecov ReportAttention: Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## develop #5152 +/- ##
========================================
Coverage 78.1% 78.1%
========================================
Files 790 795 +5
Lines 67988 68447 +459
Branches 8251 8277 +26
========================================
+ Hits 53092 53482 +390
- Misses 14896 14965 +69
... and 3 files with indirect coverage changes 🚀 New features to boost your workflow:
|
Analysis of Reference Count Ranges for Intrusive Smart PointersBackgroundFollowing the conversation in the original PR (Intrusive shamap inner (SHAMapTreeNode memory reduction) by seelabs · Pull Request #4815 · XRPLF/rippled ), it was raised that unlike the standard library
Questions
Code auditStrong referencesFrom analyzing the code: Worst-case scenario:
Theoretical Maximum value: 210 = 2 X (15 / 5) X 35 Weak referencesClass TestsTemporary code changes
Test runs
Test results
The test result of 387 references being observed is much higher than the theoretical maximum. This suggests: Conclusion
|
HowardHinnant
approved these changes
Nov 6, 2024
There was a problem hiding this comment.
The theoretical maximal value for string references is calculated to be 210. Experimental evidence also from the readme detects a value above the theoretical maximum: 387.
I ran a server for about an hour and detected a max of 1908.
These are all well below the limits of 65535, so this limit is probably safe. But it wouldn't hurt to revisit the theoretical maximum and discover why it is incorrect.
I did additional digging following a comment from @HowardHinnant. What I didn't take into account is that
Two of those routines are executed from the Based on those findings, we should update the Theoretical Maximum value.
Giving overall Theoretical Maximum value as: This is still significantly lower than the allocated 65535 range. |
8000
|
Should these flags be defined in the top level
nit: Why check each compiler if they're mutually exclusive (if/if/if)? nit: the |
|
vvysokikh1
reviewed
Mar 18, 2025
include/xrpl/basics/TaggedCache.ipp
Outdated
There was a problem hiding this comment.
Honestly I'm not sold on this separation. Even simplest one liners in this file take 20+ lines of code. It's very hard to review
There was a problem hiding this comment.
I agree that there is no ideal solution here — each approach involves a different type of compromise.
The alternative to separation is to keep everything in a single TaggedCache.h file. While this would save some lines of code, it would reduce the clarity of the TaggedCache interface.
I would vote in favour of future readability, even at the cost of some current complications, and support reviewing the splitting change.
vvysokikh1
approved these changes
Mar 25, 2025
Tapanito
pushed a commit
to Tapanito/rippled
that referenced
this pull request
Mar 27, 2025
…e synchronization (XRPLF#5152) The main goal of this optimisation is memory reduction in SHAMapTreeNodes by introducing intrusive pointers instead of standard std::shared_ptr and std::weak_ptr.
bthomee
added a commit
that referenced
this pull request
May 18, 2025
* refactor: Remove unused and add missing includes (#5293) The codebase is filled with includes that are unused, and which thus can be removed. At the same time, the files often do not include all headers that contain the definitions used in those files. This change uses clang-format and clang-tidy to clean up the includes, with minor manual intervention to ensure the code compiles on all platforms. * refactor: Calculate numFeatures automatically (#5324) Requiring manual updates of numFeatures is an annoying manual process that is easily forgotten, and leads to frequent merge conflicts. This change takes advantage of the `XRPL_FEATURE` and `XRPL_FIX` macros, and adds a new `XRPL_RETIRE` macro to automatically set `numFeatures`. * refactor: Improve ordering of headers with clang-format (#5343) Removes all manual header groupings from source and header files by leveraging clang-format options. * Rename "deadlock" to "stall" in `LoadManager` (#5341) What the LoadManager class does is stall detection, which is not the same as deadlock detection. In the condition of severe CPU starvation, LoadManager will currently intentionally crash rippled reporting `LogicError: Deadlock detected`. This error message is misleading as the condition being detected is not a deadlock. This change fixes and refactors the code in response. * Adds hub.xrpl-commons.org as a new Bootstrap Cluster (#5263) * fix: Error message for ledger_entry rpc (#5344) Changes the error to `malformedAddress` for `permissioned_domain` in the `ledger_entry` rpc, when the account is not a string. This change makes it more clear to a user what is wrong with their request. * fix: Handle invalid marker parameter in grpc call (#5317) The `end_marker` is used to limit the range of ledger entries to fetch. If `end_marker` is less than `marker`, a crash can occur. This change adds an additional check. * fix: trust line RPC no ripple flag (#5345) The Trustline RPC `no_ripple` flag gets set depending on `lsfDefaultRipple` flag, which is not a flag of a trustline but of the account root. The `lsfDefaultRipple` flag does not provide any insight if this particular trust line has `lsfLowNoRipple` or `lsfHighNoRipple` flag set, so it should not be used here at all. This change simplifies the logic. * refactor: Updates Conan dependencies: RocksDB (#5335) Updates RocksDB to version 9.7.3, the latest version supported in Conan 1.x. A patch for 9.7.4 that fixes a memory leak is included. * fix: Remove null pointer deref, just do abort (#5338) This change removes the existing undefined behavior from `LogicError`, so we can be certain that there will be always a stacktrace. De-referencing a null pointer is an old trick to generate `SIGSEGV`, which would typically also create a stacktrace. However it is also an undefined behaviour and compilers can do something else. A more robust way to create a stacktrace while crashing the program is to use `std::abort`, which we have also used in this location for a long time. If we combine the two, we might not get the expected behaviour - namely, the nullpointer deref followed by `std::abort`, as handled in certain compiler versions may not immediately cause a crash. We have observed stacktrace being wiped instead, and thread put in indeterminate state, then stacktrace created without any useful information. * chore: Add PR number to payload (#5310) This PR adds one more payload field to the libXRPL compatibility check workflow - the PR number itself. * chore: Update link to ripple-binary-codec (#5355) The link to ripple-binary-codec's definitions.json appears to be outdated. The updated link is also documented here: https://xrpl.org/docs/references/protocol/binary-format#definitions-file * Prevent consensus from getting stuck in the establish phase (#5277) - Detects if the consensus process is "stalled". If it is, then we can declare a consensus and end successfully even if we do not have 80% agreement on our proposal. - "Stalled" is defined as: - We have a close time consensus - Each disputed transaction is individually stalled: - It has been in the final "stuck" 95% requirement for at least 2 (avMIN_ROUNDS) "inner rounds" of phaseEstablish, - and either all of the other trusted proposers or this validator, if proposing, have had the same vote(s) for at least 4 (avSTALLED_ROUNDS) "inner rounds", and at least 80% of the validators (including this one, if appropriate) agree about the vote (whether yes or no). - If we have been in the establish phase for more than 10x the previous consensus establish phase's time, then consensus is considered "expired", and we will leave the round, which sends a partial validation (indicating that the node is moving on without validating). Two restrictions avoid prematurely exiting, or having an extended exit in extreme situations. - The 10x time is clamped to be within a range of 15s (ledgerMAX_CONSENSUS) to 120s (ledgerABANDON_CONSENSUS). - If consensus has not had an opportunity to walk through all avalanche states (defined as not going through 8 "inner rounds" of phaseEstablish), then ConsensusState::Expired is treated as ConsensusState::No. - When enough nodes leave the round, any remaining nodes will see they've fallen behind, and move on, too, generally before hitting the timeout. Any validations or partial validations sent during this time will help the consensus process bring the nodes back together. * test: enable TxQ unit tests work with variable reference fee (#5118) In preparation for a potential reference fee change we would like to verify that fee change works as expected. The first step is to fix all unit tests to be able to work with different reference fee values. * test: enable unit tests to work with variable reference fee (#5145) Fix remaining unit tests to be able to process reference fee values other than 10. * Intrusive SHAMap smart pointers for efficient memory use and lock-free synchronization (#5152) The main goal of this optimisation is memory reduction in SHAMapTreeNodes by introducing intrusive pointers instead of standard std::shared_ptr and std::weak_ptr. * refactor: Move integration tests from 'examples/' into 'tests/' (#5367) This change moves `examples/example` into `tests/conan` to make it clear it is an integration test, and adjusts the `conan` CI job accordingly * test: enable compile time param to change reference fee value (#5159) Adds an extra CI pipeline to perform unit tests using different values for fees. * Fix undefined uint128_t type on Windows non-unity builds (#5377) As part of import optimization, a transitive include had been removed that defined `BOOST_COMP_MSVC` on Windows. In unity builds, this definition was pulled in, but in non-unity builds it was not - causing a compilation error. An inspection of the Boost code revealed that we can just gate the statements by `_MS_VER` instead. A `#pragma message` is added to verify that the statement is only printed on Windows builds. * fix: uint128 ambiguousness breaking macos unity build (#5386) * Fix to correct memory ordering for compare_exchange_weak and wait in the intrusive reference counting logic (#5381) This change addresses a memory ordering assertion failure observed on one of the Windows test machines during the IntrusiveShared_test suite. * fix: disable `channel_authorize` when `signing_support` is disabled (#5385) * fix: Use the build image from ghcr.io (#5390) The ci pipelines are constantly hitting Docker Hub's public rate limiting since increasing the number of jobs we're running. This change switches over to images hosted in GitHub's registry. * Remove UNREACHABLE from `NetworkOPsImp::processTrustedProposal` (#5387) It’s possible for this to happen legitimately if a set of peers, including a validator, are connected in a cycle, and the latency and message processing time between those peers is significantly less than the latency between the validator and the last peer. It’s unlikely in B820 the real world, but obviously easy to simulate with Antithesis. * Instrument proposal, validation and transaction messages (#5348) Adds metric counters for the following P2P message types: * Untrusted proposal and validation messages * Duplicate proposal, validation and transaction messages * refactor(trivial): reorganize ledger entry tests and helper functions (#5376) This PR splits out `ledger_entry` tests into its own file (`LedgerEntry_test.cpp`) and alphabetizes the helper functions in `LedgerEntry.cpp`. These commits were split out of #5237 to make that PR a little more manageable, since these basic trivial changes are most of the diff. There is no code change, just moving code around. * fix: `fixPayChanV1` (#4717) This change introduces a new fix amendment (`fixPayChanV1`) that prevents the creation of new `PaymentChannelCreate` transaction with a `CancelAfter` time less than the current ledger time. It piggy backs off of fix1571. Once the amendment is activated, creating a new `PaymentChannel` will require that if you specify the `CancelAfter` time/value, that value must be greater than or equal to the current ledger time. Currently users can create a payment channel where the `CancelAfter` time is before the current ledger time. This results in the payment channel being immediately closed on the next PaymentChannel transaction. * Fix: admin RPC webhook queue limit removal and timeout reduction (#5163) When using subscribe at admin RPC port to send webhooks for the transaction stream to a backend, on large(r) ledgers the endpoint receives fewer HTTP POSTs with TX information than the amount of transactions in a ledger. This change removes the hardcoded queue length to avoid dropping TX notifications for the admin-only command. In addition, the per-request TTL for outgoing RPC HTTP calls has been reduced from 10 minutes to 30 seconds. * fix: Adds CTID to RPC tx and updates error (#4738) This change fixes a number of issues involved with CTID: * CTID is not present on all RPC tx transactions. * rpcWRONG_NETWORK is missing in the ErrorCodes.cpp * Temporary disable automatic triggering macOS pipeline (#5397) We temporarily disable running unit tests on macOS on the CI pipeline while we are investigating the delays. * refactor: Clean up test logging to make it easier to search (#5396) This PR replaces the word `failed` with `failure` in any test names and renames some test files to fix MSVC warnings, so that it is easier to search through the test output to find tests that failed. * chore: Run CI on PRs that are Ready or have the "DraftRunCI" label (#5400) - Avoids costly overhead for idle PRs where the CI results don't add any value. * fix: CTID to use correct ledger_index (#5408) * chore: Small clarification to lsfDefaultRipple comment (#5410) * fix: Replaces random endpoint resolution with sequential (#5365) This change addresses an issue where `rippled` attempts to connect to an IPv6 address, even when the local network lacks IPv6 support, resulting in a "Network is unreachable" error. The fix replaces the custom endpoint selection logic with `boost::async_connect`, which sequentially attempts to connect to available endpoints until one succeeds or all fail. * Improve transaction relay logic (#4985) Combines four related changes: 1. "Decrease `shouldRelay` limit to 30s." Pretty self-explanatory. Currently, the limit is 5 minutes, by which point the `HashRouter` entry could have expired, making this transaction look brand new (and thus causing it to be relayed back to peers which have sent it to us recently). 2. "Give a transaction more chances to be retried." Will put a transaction into `LedgerMaster`'s held transactions if the transaction gets a `ter`, `tel`, or `tef` result. Old behavior was just `ter`. * Additionally, to prevent a transaction from being repeatedly held indefinitely, it must meet some extra conditions. (Documented in a comment in the code.) 3. "Pop all transactions with sequential sequences, or tickets." When a transaction is processed successfully, currently, one held transaction for the same account (if any) will be popped out of the held transactions list, and queued up for the next transaction batch. This change pops all transactions for the account, but only if they have sequential sequences (for non-ticket transactions) or use a ticket. This issue was identified from interactions with @mtrippled's #4504, which was merged, but unfortunately reverted later by #4852. When the batches were spaced out, it could potentially take a very long time for a large number of held transactions for an account to get processed through. However, whether batched or not, this change will help get held transactions cleared out, particularly if a missing earlier transaction is what held them up. 4. "Process held transactions through existing NetworkOPs batching." In the current processing, at the end of each consensus round, all held transactions are directly applied to the open ledger, then the held list is reset. This bypasses all of the logic in `NetworkOPs::apply` which, among other things, broadcasts successful transactions to peers. This means that the transaction may not get broadcast to peers for a really long time (5 minutes in the current implementation, or 30 seconds with this first commit). If the node is a bottleneck (either due to network configuration, or because the transaction was submitted locally), the transaction may not be seen by any other nodes or validators before it expires or causes other problems. * Enable passive squelching (#5358) This change updates the squelching logic to accept squelch messages for untrusted validators. As a result, servers will also squelch untrusted validator messages reducing duplicate traffic they generate. In particular: * Updates squelch message handling logic to squelch messages for all validators, not only trusted ones. * Updates the logic to send squelch messages to peers that don't squelch themselves * Increases the threshold for the number of messages that a peer has to deliver to consider it as a candidate for validator messages. * Add PermissionDelegation feature (#5354) This change implements the account permission delegation described in XLS-75d, see XRPLF/XRPL-Standards#257. * Introduces transaction-level and granular permissions that can be delegated to other accounts. * Adds `DelegateSet` transaction to grant specified permissions to another account. * Adds `ltDelegate` ledger object to maintain the permission list for delegating/delegated account pair. * Adds an optional `Delegate` field in common fields, allowing a delegated account to send transactions on behalf of the delegating account within the granted permission scope. The `Account` field remains the delegating account; the `Delegate` field specifies the delegated account. The transaction is signed by the delegated account. * refactor: use east const convention (#5409) This change refactors the codebase to use the "east const convention", and adds a clang-format rule to follow this convention. * fix: enable LedgerStateFix for delegation (#5427) * Configure CODEOWNERS for changes to RPC code (#5266) To ensure changes to any RPC-related code are compatible with other services, such as Clio, the RPC team will be required to review them. * fix: Ensure that coverage file generation is atomic. (#5426) Running unit tests in parallel and multiple threads can write into one file can corrupt output files, and then gcovr won't be able to parse the corrupted file. This change adds -fprofile-update=atomic as instructed by https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68080. * fix: Update validators-example.txt fix xrplf example URL (#5384) * Fix: Resolve slow test on macOS pipeline (#5392) Using std::barrier performs extremely poorly (~1 hour vs ~1 minute to run the test suite) in certain macOS environments. To unblock our macOS CI pipeline, std::barrier has been replaced with a custom mutex-based barrier (Barrier) that significantly improves performance without compromising correctness. * Set version to 2.5.0-b1 --------- Co-authored-by: Bart <bthomee@users.noreply.github.com> Co-authored-by: Ed Hennis <ed@ripple.com> Co-authored-by: Bronek Kozicki <brok@incorrekt.com> Co-authored-by: Darius Tumas <Tokeiito@users.noreply.github.com> Co-authored-by: Sergey Kuznetsov <skuznetsov@ripple.com> Co-authored-by: cyan317 <120398799+cindyyan317@users.noreply.github.com> Co-authored-by: Vlad <129996061+vvysokikh1@users.noreply.github.com> Co-authored-by: Alex Kremer <akremer@ripple.com> Co-authored-by: Valentin Balaschenko <13349202+vlntb@users.noreply.github.com> Co-authored-by: Mayukha Vadari <mvadari@ripple.com> Co-authored-by: Vito Tumas <5780819+Tapanito@users.noreply.github.com> Co-authored-by: Denis Angell <dangell@transia.co> Co-authored-by: Wietse Wind <w.wind@ipublications.net> Co-authored-by: yinyiqian1 <yqian@ripple.com> Co-authored-by: Jingchen <a1q123456@users.noreply.github.com> Co-authored-by: brettmollin <brettmollin@users.noreply.github.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
High Level Overview of Change
This PR finalises the work authored by Scott Determan (https://github.com/seelabs) and is based on the original PR (#4815).
Context of Change
There are two goals:
developbranch.Type of Change
.gitignore, formatting, dropping support for older tooling)