RONCC
/
HPC-Tools-for-Quantum-Computing


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173
							<!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="API documentation for the Rust `epoch` mod in crate `crossbeam`."><meta name="keywords" content="rust, rustlang, rust-lang, epoch"><title>crossbeam::epoch - Rust</title><link rel="stylesheet" type="text/css" href="../../normalize.css"><link rel="stylesheet" type="text/css" href="../../rustdoc.css" id="mainThemeStyle"><link rel="stylesheet" type="text/css" href="../../dark.css"><link rel="stylesheet" type="text/css" href="../../light.css" id="themeStyle"><script src="../../storage.js"></script></head><body class="rustdoc mod"><!--[if lte IE 8]><div class="warning">This old browser is unsupported and will most likely display funky things.</div><![endif]--><nav class="sidebar"><div class="sidebar-menu">&#9776;</div><p class='location'>Module epoch</p><div class="sidebar-elems"><div class="block items"><ul><li><a href="#structs">Structs</a></li><li><a href="#functions">Functions</a></li></ul></div><p class='location'><a href='../index.html'>crossbeam</a></p><script>window.sidebarCurrent = {name: 'epoch', ty: 'mod', relpath: '../'};</script><script defer src="../sidebar-items.js"></script></div></nav><div class="theme-picker"><button id="theme-picker" aria-label="Pick another theme!"><img src="../../brush.svg" width="18" alt="Pick another theme!"></button><div id="theme-choices"></div></div><script src="../../theme.js"></script><nav class="sub"><form class="search-form js-only"><div class="search-container"><input class="search-input" name="search" autocomplete="off" placeholder="Click or press ‘S’ to search, ‘?’ for more options…" type="search"><a id="settings-menu" href="../../settings.html"><img src="../../wheel.svg" width="18" alt="Change settings"></a></div></form></nav><section id="main" class="content"><h1 class='fqn'><span class='in-band'>Module <a href='../index.html'>crossbeam</a>::<wbr><a class="mod" href=''>epoch</a></span><span class='out-of-band'><span id='render-detail'><a id="toggle-all-docs" href="javascript:void(0)" title="collapse all docs">[<span class='inner'>&#x2212;</span>]</a></span><a class='srclink' href='../../src/crossbeam/epoch/mod.rs.html#1-265' title='goto source code'>[src]</a></span></h1><div class='docblock'><p>Epoch-based memory management</p>
<p>This module provides fast, easy to use memory management for lock free data
structures. It's inspired by <a href="https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf">Keir Fraser's <em>epoch-based
reclamation</em></a>.</p>
<p>The basic problem this is solving is the fact that when one thread has
removed a node from a data structure, other threads may still have pointers
to that node (in the form of snapshots that will be validated through things
like compare-and-swap), so the memory cannot be immediately freed. Put differently:</p>
<ol>
<li>
<p>There are two sources of reachability at play -- the data structure, and
the snapshots in threads accessing it. Before we delete a node, we need to know
that it cannot be reached in either of these ways.</p>
</li>
<li>
<p>Once a node has been unlinked from the data structure, no <em>new</em> snapshots
reaching it will be created.</p>
</li>
</ol>
<p>Using the epoch scheme is fairly straightforward, and does not require
understanding any of the implementation details:</p>
<ul>
<li>
<p>When operating on a shared data structure, a thread must &quot;pin the current
epoch&quot;, which is done by calling <code>pin()</code>. This function returns a <code>Guard</code>
which unpins the epoch when destroyed.</p>
</li>
<li>
<p>When the thread subsequently reads from a lock-free data structure, the
pointers it extracts act like references with lifetime tied to the
<code>Guard</code>. This allows threads to safely read from snapshotted data, being
guaranteed that the data will remain allocated until they exit the epoch.</p>
</li>
</ul>
<p>To put the <code>Guard</code> to use, Crossbeam provides a set of three pointer types meant to work together:</p>
<ul>
<li>
<p><code>Owned&lt;T&gt;</code>, akin to <code>Box&lt;T&gt;</code>, which points to uniquely-owned data that has
not yet been published in a concurrent data structure.</p>
</li>
<li>
<p><code>Shared&lt;'a, T&gt;</code>, akin to <code>&amp;'a T</code>, which points to shared data that may or may
not be reachable from a data structure, but it guaranteed not to be freed
during lifetime <code>'a</code>.</p>
</li>
<li>
<p><code>Atomic&lt;T&gt;</code>, akin to <code>std::sync::atomic::AtomicPtr</code>, which provides atomic
updates to a pointer using the <code>Owned</code> and <code>Shared</code> types, and connects them
to a <code>Guard</code>.</p>
</li>
</ul>
<p>Each of these types provides further documentation on usage.</p>
<h1 id="example" class="section-header"><a href="#example">Example</a></h1>
<pre class="rust rust-example-rendered">
<span class="kw">use</span> <span class="ident">std</span>::<span class="ident">sync</span>::<span class="ident">atomic</span>::<span class="ident">Ordering</span>::{<span class="ident">Acquire</span>, <span class="ident">Release</span>, <span class="ident">Relaxed</span>};
<span class="kw">use</span> <span class="ident">std</span>::<span class="ident">ptr</span>;

<span class="kw">use</span> <span class="ident">crossbeam</span>::<span class="ident">epoch</span>::{<span class="self">self</span>, <span class="ident">Atomic</span>, <span class="ident">Owned</span>};

<span class="kw">struct</span> <span class="ident">TreiberStack</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
    <span class="ident">head</span>: <span class="ident">Atomic</span><span class="op">&lt;</span><span class="ident">Node</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;&gt;</span>,
}

<span class="kw">struct</span> <span class="ident">Node</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
    <span class="ident">data</span>: <span class="ident">T</span>,
    <span class="ident">next</span>: <span class="ident">Atomic</span><span class="op">&lt;</span><span class="ident">Node</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;&gt;</span>,
}

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> <span class="ident">TreiberStack</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
    <span class="kw">fn</span> <span class="ident">new</span>() <span class="op">-&gt;</span> <span class="ident">TreiberStack</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
        <span class="ident">TreiberStack</span> {
            <span class="ident">head</span>: <span class="ident">Atomic</span>::<span class="ident">null</span>()
        }
    }

    <span class="kw">fn</span> <span class="ident">push</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">t</span>: <span class="ident">T</span>) {
        <span class="comment">// allocate the node via Owned</span>
        <span class="kw">let</span> <span class="kw-2">mut</span> <span class="ident">n</span> <span class="op">=</span> <span class="ident">Owned</span>::<span class="ident">new</span>(<span class="ident">Node</span> {
            <span class="ident">data</span>: <span class="ident">t</span>,
            <span class="ident">next</span>: <span class="ident">Atomic</span>::<span class="ident">null</span>(),
        });

        <span class="comment">// become active</span>
        <span class="kw">let</span> <span class="ident">guard</span> <span class="op">=</span> <span class="ident">epoch</span>::<span class="ident">pin</span>();

        <span class="kw">loop</span> {
            <span class="comment">// snapshot current head</span>
            <span class="kw">let</span> <span class="ident">head</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">head</span>.<span class="ident">load</span>(<span class="ident">Relaxed</span>, <span class="kw-2">&amp;</span><span class="ident">guard</span>);

            <span class="comment">// update `next` pointer with snapshot</span>
            <span class="ident">n</span>.<span class="ident">next</span>.<span class="ident">store_shared</span>(<span class="ident">head</span>, <span class="ident">Relaxed</span>);

            <span class="comment">// if snapshot is still good, link in the new node</span>
            <span class="kw">match</span> <span class="self">self</span>.<span class="ident">head</span>.<span class="ident">cas_and_ref</span>(<span class="ident">head</span>, <span class="ident">n</span>, <span class="ident">Release</span>, <span class="kw-2">&amp;</span><span class="ident">guard</span>) {
                <span class="prelude-val">Ok</span>(<span class="kw">_</span>) <span class="op">=&gt;</span> <span class="kw">return</span>,
                <span class="prelude-val">Err</span>(<span class="ident">owned</span>) <span class="op">=&gt;</span> <span class="ident">n</span> <span class="op">=</span> <span class="ident">owned</span>,
            }
        }
    }

    <span class="kw">fn</span> <span class="ident">pop</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="prelude-ty">Option</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
        <span class="comment">// become active</span>
        <span class="kw">let</span> <span class="ident">guard</span> <span class="op">=</span> <span class="ident">epoch</span>::<span class="ident">pin</span>();

        <span class="kw">loop</span> {
            <span class="comment">// take a snapshot</span>
            <span class="kw">match</span> <span class="self">self</span>.<span class="ident">head</span>.<span class="ident">load</span>(<span class="ident">Acquire</span>, <span class="kw-2">&amp;</span><span class="ident">guard</span>) {
                <span class="comment">// the stack is non-empty</span>
                <span class="prelude-val">Some</span>(<span class="ident">head</span>) <span class="op">=&gt;</span> {
                    <span class="comment">// read through the snapshot, *safely*!</span>
                    <span class="kw">let</span> <span class="ident">next</span> <span class="op">=</span> <span class="ident">head</span>.<span class="ident">next</span>.<span class="ident">load</span>(<span class="ident">Relaxed</span>, <span class="kw-2">&amp;</span><span class="ident">guard</span>);

                    <span class="comment">// if snapshot is still good, update from `head` to `next`</span>
                    <span class="kw">if</span> <span class="self">self</span>.<span class="ident">head</span>.<span class="ident">cas_shared</span>(<span class="prelude-val">Some</span>(<span class="ident">head</span>), <span class="ident">next</span>, <span class="ident">Release</span>) {
                        <span class="kw">unsafe</span> {
                            <span class="comment">// mark the node as unlinked</span>
                            <span class="ident">guard</span>.<span class="ident">unlinked</span>(<span class="ident">head</span>);

                            <span class="comment">// extract out the data from the now-unlinked node</span>
                            <span class="kw">return</span> <span class="prelude-val">Some</span>(<span class="ident">ptr</span>::<span class="ident">read</span>(<span class="kw-2">&amp;</span>(<span class="kw-2">*</span><span class="ident">head</span>).<span class="ident">data</span>))
                        }
                    }
                }

                <span class="comment">// we observed the stack empty</span>
                <span class="prelude-val">None</span> <span class="op">=&gt;</span> <span class="kw">return</span> <span class="prelude-val">None</span>
            }
        }
    }
}</pre>
</div><h2 id='structs' class='section-header'><a href="#structs">Structs</a></h2>
<table>
                       <tr class=' module-item'>
                           <td><a class="struct" href="struct.Atomic.html"
                                  title='struct crossbeam::epoch::Atomic'>Atomic</a></td>
                           <td class='docblock-short'>
                                <p>Like <code>std::sync::atomic::AtomicPtr</code>.</p>

                           </td>
                       </tr>
                       <tr class=' module-item'>
                           <td><a class="struct" href="struct.Guard.html"
                                  title='struct crossbeam::epoch::Guard'>Guard</a></td>
                           <td class='docblock-short'>
                                <p>An RAII-style guard for pinning the current epoch.</p>

                           </td>
                       </tr>
                       <tr class=' module-item'>
                           <td><a class="struct" href="struct.Owned.html"
                                  title='struct crossbeam::epoch::Owned'>Owned</a></td>
                           <td class='docblock-short'>
                                <p>Like <code>Box&lt;T&gt;</code>: an owned, heap-allocated data value of type <code>T</code>.</p>

                           </td>
                       </tr>
                       <tr class=' module-item'>
                           <td><a class="struct" href="struct.Shared.html"
                                  title='struct crossbeam::epoch::Shared'>Shared</a></td>
                           <td class='docblock-short'>
                                <p>Like <code>&amp;'a T</code>: a shared reference valid for lifetime <code>'a</code>.</p>

                           </td>
                       </tr></table><h2 id='functions' class='section-header'><a href="#functions">Functions</a></h2>
<table>
                       <tr class=' module-item'>
                           <td><a class="fn" href="fn.pin.html"
                                  title='fn crossbeam::epoch::pin'>pin</a></td>
                           <td class='docblock-short'>
                                <p>Pin the current epoch.</p>

                           </td>
                       </tr></table></section><section id="search" class="content hidden"></section><section class="footer"></section><aside id="help" class="hidden"><div><h1 class="hidden">Help</h1><div class="shortcuts"><h2>Keyboard Shortcuts</h2><dl><dt><kbd>?</kbd></dt><dd>Show this help dialog</dd><dt><kbd>S</kbd></dt><dd>Focus the search field</dd><dt><kbd>↑</kbd></dt><dd>Move up in search results</dd><dt><kbd>↓</kbd></dt><dd>Move down in search results</dd><dt><kbd>↹</kbd></dt><dd>Switch tab</dd><dt><kbd>&#9166;</kbd></dt><dd>Go to active search result</dd><dt><kbd>+</kbd></dt><dd>Expand all sections</dd><dt><kbd>-</kbd></dt><dd>Collapse all sections</dd></dl></div><div class="infos"><h2>Search Tricks</h2><p>Prefix searches with a type followed by a colon (e.g. <code>fn:</code>) to restrict the search to a given type.</p><p>Accepted types are: <code>fn</code>, <code>mod</code>, <code>struct</code>, <code>enum</code>, <code>trait</code>, <code>type</code>, <code>macro</code>, and <code>const</code>.</p><p>Search functions by type signature (e.g. <code>vec -> usize</code> or <code>* -> vec</code>)</p><p>Search multiple things at once by splitting your query with comma (e.g. <code>str,u8</code> or <code>String,struct:Vec,test</code>)</p></div></div></aside><script>window.rootPath = "../../";window.currentCrate = "crossbeam";</script><script src="../../aliases.js"></script><script src="../../main.js"></script><script defer src="../../search-index.js"></script></body></html>