RONCC
/
HPC-Tools-for-Quantum-Computing


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299
							<!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="../../main.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">
            </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="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>
            </div>
        </div>
    </aside>

    

    <script>
        window.rootPath = "../../";
        window.currentCrate = "crossbeam";
    </script>
    <script src="../../main.js"></script>
    <script defer src="../../search-index.js"></script>
</body>
</html>