| <!DOCTYPE html><html lang="en"><head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="generator" content="rustdoc"><meta name="description" content="Internal details."><meta name="keywords" content="rust, rustlang, rust-lang, internal"><title>arc_swap::docs::internal - Rust</title><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceSerif4-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../FiraSans-Regular.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../FiraSans-Medium.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceCodePro-Regular.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceSerif4-Bold.ttf.woff2"><link rel="preload" as="font" type="font/woff2" crossorigin href="../../../SourceCodePro-Semibold.ttf.woff2"><link rel="stylesheet" href="../../../normalize.css"><link rel="stylesheet" href="../../../rustdoc.css" id="mainThemeStyle"><link rel="stylesheet" href="../../../ayu.css" disabled><link rel="stylesheet" href="../../../dark.css" disabled><link rel="stylesheet" href="../../../light.css" id="themeStyle"><script id="default-settings" ></script><script src="../../../storage.js"></script><script defer src="../../../main.js"></script><noscript><link rel="stylesheet" href="../../../noscript.css"></noscript><link rel="alternate icon" type="image/png" href="../../../favicon-16x16.png"><link rel="alternate icon" type="image/png" href="../../../favicon-32x32.png"><link rel="icon" type="image/svg+xml" href="../../../favicon.svg"></head><body class="rustdoc mod"><!--[if lte IE 11]><div class="warning">This old browser is unsupported and will most likely display funky things.</div><![endif]--><nav class="mobile-topbar"><button class="sidebar-menu-toggle">☰</button><a class="sidebar-logo" href="../../../arc_swap/index.html"><div class="logo-container"><img class="rust-logo" src="../../../rust-logo.svg" alt="logo"></div></a><h2></h2></nav><nav class="sidebar"><a class="sidebar-logo" href="../../../arc_swap/index.html"><div class="logo-container"><img class="rust-logo" src="../../../rust-logo.svg" alt="logo"></div></a><h2 class="location"><a href="#">Module internal</a></h2><div class="sidebar-elems"></div></nav><main><div class="width-limiter"><nav class="sub"><form class="search-form"><div class="search-container"><span></span><input class="search-input" name="search" autocomplete="off" spellcheck="false" placeholder="Click or press ‘S’ to search, ‘?’ for more options…" type="search"><div id="help-button" title="help" tabindex="-1"><a href="../../../help.html">?</a></div><div id="settings-menu" tabindex="-1"><a href="../../../settings.html" title="settings"><img width="22" height="22" alt="Change settings" src="../../../wheel.svg"></a></div></div></form></nav><section id="main-content" class="content"><div class="main-heading"><h1 class="fqn">Module <a href="../../index.html">arc_swap</a>::<wbr><a href="../index.html">docs</a>::<wbr><a class="mod" href="#">internal</a><button id="copy-path" onclick="copy_path(this)" title="Copy item path to clipboard"><img src="../../../clipboard.svg" width="19" height="18" alt="Copy item path"></button></h1><span class="out-of-band"><a class="srclink" href="../../../src/arc_swap/docs/internal.rs.html#1-106">source</a> · <a id="toggle-all-docs" href="javascript:void(0)" title="collapse all docs">[<span class="inner">−</span>]</a></span></div><details class="rustdoc-toggle top-doc" open><summary class="hideme"><span>Expand description</span></summary><div class="docblock"><p>Internal details.</p> |
| <p>While the other parts of documentation are useful to users of the crate, this part is probably |
| helpful only if you want to look into the code or are curious about how it works internally.</p> |
| <p>Also note that any of these details may change in future versions and are not part of the |
| stability guarantees. Don’t rely on anything here.</p> |
| <h2 id="storing-the-arc"><a href="#storing-the-arc">Storing the <code>Arc</code>.</a></h2> |
| <p>The <a href="std::sync::Arc"><code>Arc</code></a> can be turned into a raw pointer and back. This is abstracted by the <a href="../../trait.RefCnt.html"><code>RefCnt</code></a> |
| trait and it is technically possible to implement it for custom types (this crate also |
| implements it for <a href="std::rc::Rc"><code>Rc</code></a> and <a href="std::sync::Weak"><code>Weak</code></a>, though the actual usefulness of these is a bit |
| questionable).</p> |
| <p>The raw pointer is stored inside an <a href="std::sync::atomic::AtomicPtr"><code>AtomicPtr</code></a>.</p> |
| <h2 id="protection-of-reference-counts"><a href="#protection-of-reference-counts">Protection of reference counts</a></h2> |
| <p>The first idea would be to just use <a href="std::sync::atomic::AtomicPtr"><code>AtomicPtr</code></a> with whatever the <a href="std::sync::Arc::into_raw"><code>Arc::into_raw</code></a> returns. |
| Then replacing it would be fine (there’s no need to update ref counts). The load needs to |
| increment the reference count ‒ one still stays inside and another is returned to the caller. |
| This is done by re-creating the Arc from the raw pointer and then cloning it, throwing one |
| instance away (without destroying it).</p> |
| <p>This approach has a problem. There’s a short time between we read the raw pointer and increment |
| the count. If some other thread replaces the stored Arc and throws it away, the ref count could |
| drop to 0, get destroyed and we would be trying to bump ref counts in a ghost, which would be |
| totally broken.</p> |
| <p>To prevent this, we actually use two approaches in a hybrid manner.</p> |
| <p>The first one is based on hazard pointers idea, but slightly modified. There’s a global |
| repository of pointers that owe a reference. When someone swaps a pointer, it walks this list |
| and pays all the debts (and takes them out of the repository).</p> |
| <p>For simplicity and performance, storing into the repository is fallible. If storing into the |
| repository fails (because the thread used up all its own slots, or because the pointer got |
| replaced in just the wrong moment and it can’t confirm the reservation), unlike the full |
| hazard-pointers approach, we don’t retry, but fall back onto secondary strategy.</p> |
| <p>The secondary strategy is similar, but a bit more complex (and therefore slower, that’s why it |
| is only a fallback). We first publish an intent to read a pointer (and where we are reading it |
| from). Then we actually do so and publish the debt, like previously.</p> |
| <p>The writer pays the debts as usual. But also, if it sees the intent to read the value, it helps |
| along, reads it, bumps the reference and passes it to the reader. Therefore, if the reader |
| fails to do the protection itself, because it got interrupted by a writer, it finds a |
| ready-made replacement value it can just use and doesn’t have to retry. Also, the writer |
| doesn’t have to wait for the reader in any way, because it can just solve its problem and move |
| on.</p> |
| <h2 id="unsafety"><a href="#unsafety">Unsafety</a></h2> |
| <p>All the uses of the unsafe keyword is just to turn the raw pointer back to Arc. It originated |
| from an Arc in the first place, so the only thing to ensure is it is still valid. That means its |
| ref count never dropped to 0.</p> |
| <p>At the beginning, there’s ref count of 1 stored in the raw pointer (and maybe some others |
| elsewhere, but we can’t rely on these). This 1 stays there for the whole time the pointer is |
| stored there. When the arc is replaced, this 1 is returned to the caller, so we just have to |
| make sure no more readers access it by that time.</p> |
| <h2 id="leases-and-debts"><a href="#leases-and-debts">Leases and debts</a></h2> |
| <p>Instead of incrementing the reference count, the pointer reference can be owed. In such case, it |
| is recorded into a global storage. As each thread has its own storage (the global storage is |
| composed of multiple thread storages), the readers don’t contend. When the pointer is no longer |
| in use, the debt is erased.</p> |
| <p>The writer pays all the existing debts, therefore the reader have the full Arc with ref count at |
| that time. The reader is made aware the debt was paid and decrements the reference count.</p> |
| <h2 id="memory-orders"><a href="#memory-orders">Memory orders</a></h2><h3 id="synchronizing-the-data-pointed-to-by-the-pointer"><a href="#synchronizing-the-data-pointed-to-by-the-pointer">Synchronizing the data pointed to by the pointer.</a></h3> |
| <p>We have AcqRel (well, SeqCst, but that’s included) on the swap and Acquire on the loads. In case |
| of the double read around the debt allocation, we do that on the <em>second</em>, because of ABA. |
| That’s also why that SeqCst on the allocation of debt itself is not enough. |
| the <em>latest</em> decrement. By making both the increment and decrement AcqRel, we effectively chain |
| the edges together.</p> |
| <h2 id="memory-orders-around-debts"><a href="#memory-orders-around-debts">Memory orders around debts</a></h2> |
| <p>The linked list of debt nodes only grows. The shape of the list (existence of nodes) is |
| synchronized through Release on creation and Acquire on load on the head pointer.</p> |
| <p>The debts work similar to locks ‒ Acquire and Release make all the pointer manipulation at the |
| interval where it is written down. However, we use the SeqCst on the allocation of the debt |
| because when we see an empty slot, we need to make sure that it happened after we have |
| overwritten the pointer.</p> |
| <p>In case the writer pays the debt, it sees the new enough data (for the same reasons the stale |
| empties are not seen). The reference count on the Arc is AcqRel and makes sure it is not |
| destroyed too soon. The writer traverses all the slots, therefore they don’t need to synchronize |
| with each other.</p> |
| <p>Further details are inside the internal <code>debt</code> module.</p> |
| </div></details></section></div></main><div id="rustdoc-vars" data-root-path="../../../" data-current-crate="arc_swap" data-themes="ayu,dark,light" data-resource-suffix="" data-rustdoc-version="1.66.0-nightly (5c8bff74b 2022-10-21)" ></div></body></html> |
