| <!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="Source of the Rust file `/root/.cargo/registry/src/github.com-1ecc6299db9ec823/arc-swap-1.6.0/src/docs/internal.rs`."><meta name="keywords" content="rust, rustlang, rust-lang"><title>internal.rs - source</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="../../../source-script.js"></script><script defer src="../../../source-files.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 source"><!--[if lte IE 11]><div class="warning">This old browser is unsupported and will most likely display funky things.</div><![endif]--><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></nav><main><div class="width-limiter"><nav class="sub"><a class="sub-logo-container" href="../../../arc_swap/index.html"><img class="rust-logo" src="../../../rust-logo.svg" alt="logo"></a><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="example-wrap"><pre class="src-line-numbers"><span id="1">1</span> |
| <span id="2">2</span> |
| <span id="3">3</span> |
| <span id="4">4</span> |
| <span id="5">5</span> |
| <span id="6">6</span> |
| <span id="7">7</span> |
| <span id="8">8</span> |
| <span id="9">9</span> |
| <span id="10">10</span> |
| <span id="11">11</span> |
| <span id="12">12</span> |
| <span id="13">13</span> |
| <span id="14">14</span> |
| <span id="15">15</span> |
| <span id="16">16</span> |
| <span id="17">17</span> |
| <span id="18">18</span> |
| <span id="19">19</span> |
| <span id="20">20</span> |
| <span id="21">21</span> |
| <span id="22">22</span> |
| <span id="23">23</span> |
| <span id="24">24</span> |
| <span id="25">25</span> |
| <span id="26">26</span> |
| <span id="27">27</span> |
| <span id="28">28</span> |
| <span id="29">29</span> |
| <span id="30">30</span> |
| <span id="31">31</span> |
| <span id="32">32</span> |
| <span id="33">33</span> |
| <span id="34">34</span> |
| <span id="35">35</span> |
| <span id="36">36</span> |
| <span id="37">37</span> |
| <span id="38">38</span> |
| <span id="39">39</span> |
| <span id="40">40</span> |
| <span id="41">41</span> |
| <span id="42">42</span> |
| <span id="43">43</span> |
| <span id="44">44</span> |
| <span id="45">45</span> |
| <span id="46">46</span> |
| <span id="47">47</span> |
| <span id="48">48</span> |
| <span id="49">49</span> |
| <span id="50">50</span> |
| <span id="51">51</span> |
| <span id="52">52</span> |
| <span id="53">53</span> |
| <span id="54">54</span> |
| <span id="55">55</span> |
| <span id="56">56</span> |
| <span id="57">57</span> |
| <span id="58">58</span> |
| <span id="59">59</span> |
| <span id="60">60</span> |
| <span id="61">61</span> |
| <span id="62">62</span> |
| <span id="63">63</span> |
| <span id="64">64</span> |
| <span id="65">65</span> |
| <span id="66">66</span> |
| <span id="67">67</span> |
| <span id="68">68</span> |
| <span id="69">69</span> |
| <span id="70">70</span> |
| <span id="71">71</span> |
| <span id="72">72</span> |
| <span id="73">73</span> |
| <span id="74">74</span> |
| <span id="75">75</span> |
| <span id="76">76</span> |
| <span id="77">77</span> |
| <span id="78">78</span> |
| <span id="79">79</span> |
| <span id="80">80</span> |
| <span id="81">81</span> |
| <span id="82">82</span> |
| <span id="83">83</span> |
| <span id="84">84</span> |
| <span id="85">85</span> |
| <span id="86">86</span> |
| <span id="87">87</span> |
| <span id="88">88</span> |
| <span id="89">89</span> |
| <span id="90">90</span> |
| <span id="91">91</span> |
| <span id="92">92</span> |
| <span id="93">93</span> |
| <span id="94">94</span> |
| <span id="95">95</span> |
| <span id="96">96</span> |
| <span id="97">97</span> |
| <span id="98">98</span> |
| <span id="99">99</span> |
| <span id="100">100</span> |
| <span id="101">101</span> |
| <span id="102">102</span> |
| <span id="103">103</span> |
| <span id="104">104</span> |
| <span id="105">105</span> |
| <span id="106">106</span> |
| </pre><pre class="rust"><code><span class="doccomment">//! Internal details. |
| //! |
| //! 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. |
| //! |
| //! 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. |
| //! |
| //! # Storing the [`Arc`]. |
| //! |
| //! The [`Arc`] can be turned into a raw pointer and back. This is abstracted by the [`RefCnt`] |
| //! trait and it is technically possible to implement it for custom types (this crate also |
| //! implements it for [`Rc`] and [`Weak`], though the actual usefulness of these is a bit |
| //! questionable). |
| //! |
| //! The raw pointer is stored inside an [`AtomicPtr`]. |
| //! |
| //! # Protection of reference counts |
| //! |
| //! The first idea would be to just use [`AtomicPtr`] with whatever the [`Arc::into_raw`] 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). |
| //! |
| //! 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. |
| //! |
| //! To prevent this, we actually use two approaches in a hybrid manner. |
| //! |
| //! 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). |
| //! |
| //! 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. |
| //! |
| //! 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. |
| //! |
| //! 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. |
| //! |
| //! # Unsafety |
| //! |
| //! 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. |
| //! |
| //! 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. |
| //! |
| //! # Leases and debts |
| //! |
| //! 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. |
| //! |
| //! 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. |
| //! |
| //! # Memory orders |
| //! |
| //! ## Synchronizing the data pointed to by the pointer. |
| //! |
| //! 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 *second*, because of ABA. |
| //! That's also why that SeqCst on the allocation of debt itself is not enough. |
| //! the *latest* decrement. By making both the increment and decrement AcqRel, we effectively chain |
| //! the edges together. |
| //! |
| //! # Memory orders around debts |
| //! |
| //! 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. |
| //! |
| //! 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. |
| //! |
| //! 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. |
| //! |
| //! Further details are inside the internal `debt` module. |
| //! |
| //! [`RefCnt`]: crate::RefCnt |
| //! [`Arc`]: std::sync::Arc |
| //! [`Arc::into_raw`]: std::sync::Arc::into_raw |
| //! [`Rc`]: std::rc::Rc |
| //! [`Weak`]: std::sync::Weak |
| //! [`AtomicPtr`]: std::sync::atomic::AtomicPtr |
| </span></code></pre></div> |
| </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> |
