diff options
Diffstat (limited to 'static/netbsd/man9/pslist.9 3.html')
| -rw-r--r-- | static/netbsd/man9/pslist.9 3.html | 386 |
1 files changed, 0 insertions, 386 deletions
diff --git a/static/netbsd/man9/pslist.9 3.html b/static/netbsd/man9/pslist.9 3.html deleted file mode 100644 index 9aa95f84..00000000 --- a/static/netbsd/man9/pslist.9 3.html +++ /dev/null @@ -1,386 +0,0 @@ -<table class="head"> - <tr> - <td class="head-ltitle">PSLIST(9)</td> - <td class="head-vol">Kernel Developer's Manual</td> - <td class="head-rtitle">PSLIST(9)</td> - </tr> -</table> -<div class="manual-text"> -<section class="Sh"> -<h1 class="Sh" id="NAME"><a class="permalink" href="#NAME">NAME</a></h1> -<p class="Pp"><code class="Nm">pslist</code> — - <span class="Nd">pserialize-safe linked lists</span></p> -</section> -<section class="Sh"> -<h1 class="Sh" id="SYNOPSIS"><a class="permalink" href="#SYNOPSIS">SYNOPSIS</a></h1> -<p class="Pp"><code class="In">#include - <<a class="In">sys/pslist.h</a>></code></p> -<p class="Pp"><var class="Vt">struct pslist_head head <span class="No">=</span> - <code class="Dv">PSLIST_INITIALIZER</code></var>; - <br/> - <var class="Vt">struct pslist_entry entry <span class="No">=</span> - <code class="Dv">PSLIST_ENTRY_INITIALIZER</code></var>;</p> -<p class="Pp"><var class="Ft">void</var> - <br/> - <code class="Fn">PSLIST_INIT</code>(<var class="Fa" style="white-space: nowrap;">struct - pslist_head *head</var>);</p> -<p class="Pp"><var class="Ft">void</var> - <br/> - <code class="Fn">PSLIST_DESTROY</code>(<var class="Fa" style="white-space: nowrap;">struct - pslist_head *head</var>);</p> -<p class="Pp"><var class="Ft">void</var> - <br/> - <code class="Fn">PSLIST_ENTRY_INIT</code>(<var class="Fa" style="white-space: nowrap;">TYPE - *element</var>, <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY - NAME</var>);</p> -<p class="Pp"><var class="Ft">void</var> - <br/> - <code class="Fn">PSLIST_ENTRY_DESTROY</code>(<var class="Fa" style="white-space: nowrap;">TYPE - *element</var>, <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY - NAME</var>);</p> -<p class="Pp"><var class="Ft">void</var> - <br/> - <code class="Fn">PSLIST_WRITER_INSERT_HEAD</code>(<var class="Fa" style="white-space: nowrap;">struct - pslist_head *head</var>, <var class="Fa" style="white-space: nowrap;">TYPE - *new</var>, <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY - NAME</var>);</p> -<p class="Pp"><var class="Ft">void</var> - <br/> - <code class="Fn">PSLIST_WRITER_INSERT_BEFORE</code>(<var class="Fa" style="white-space: nowrap;">TYPE - *element</var>, <var class="Fa" style="white-space: nowrap;">TYPE - *new</var>, <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY - NAME</var>);</p> -<p class="Pp"><var class="Ft">void</var> - <br/> - <code class="Fn">PSLIST_WRITER_INSERT_AFTER</code>(<var class="Fa" style="white-space: nowrap;">TYPE - *element</var>, <var class="Fa" style="white-space: nowrap;">TYPE - *new</var>, <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY - NAME</var>);</p> -<p class="Pp"><var class="Ft">void</var> - <br/> - <code class="Fn">PSLIST_WRITER_REMOVE</code>(<var class="Fa" style="white-space: nowrap;">TYPE - *element</var>, <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY - NAME</var>);</p> -<p class="Pp"><var class="Ft">TYPE *</var> - <br/> - <code class="Fn">PSLIST_WRITER_FIRST</code>(<var class="Fa" style="white-space: nowrap;">const - struct pslist *head</var>, - <var class="Fa" style="white-space: nowrap;">TYPE</var>, - <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY NAME</var>);</p> -<p class="Pp"><var class="Ft">TYPE *</var> - <br/> - <code class="Fn">PSLIST_WRITER_NEXT</code>(<var class="Fa" style="white-space: nowrap;">const - TYPE *element</var>, - <var class="Fa" style="white-space: nowrap;">TYPE</var>, - <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY NAME</var>);</p> -<p class="Pp"><code class="Fn">PSLIST_WRITER_FOREACH</code>(<var class="Fa" style="white-space: nowrap;">const - TYPE *element</var>, <var class="Fa" style="white-space: nowrap;">const - struct pslist_head *head</var>, - <var class="Fa" style="white-space: nowrap;">TYPE</var>, - <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY NAME</var>);</p> -<p class="Pp"><var class="Ft">TYPE *</var> - <br/> - <code class="Fn">PSLIST_READER_FIRST</code>(<var class="Fa" style="white-space: nowrap;">const - struct pslist *head</var>, - <var class="Fa" style="white-space: nowrap;">TYPE</var>, - <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY NAME</var>);</p> -<p class="Pp"><var class="Ft">TYPE *</var> - <br/> - <code class="Fn">PSLIST_READER_NEXT</code>(<var class="Fa" style="white-space: nowrap;">const - TYPE *element</var>, - <var class="Fa" style="white-space: nowrap;">TYPE</var>, - <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY NAME</var>);</p> -<p class="Pp"><code class="Fn">PSLIST_READER_FOREACH</code>(<var class="Fa" style="white-space: nowrap;">const - TYPE *element</var>, <var class="Fa" style="white-space: nowrap;">const - struct pslist_head *head</var>, - <var class="Fa" style="white-space: nowrap;">TYPE</var>, - <var class="Fa" style="white-space: nowrap;">PSLIST_ENTRY NAME</var>);</p> -</section> -<section class="Sh"> -<h1 class="Sh" id="DESCRIPTION"><a class="permalink" href="#DESCRIPTION">DESCRIPTION</a></h1> -<p class="Pp">The <code class="Nm">pslist</code> data structure is a linked list - like <code class="Nm">list</code> in <a class="Xr">queue(3)</a>. It is - augmented with memory barriers so that any number of readers can safely run - in parallel with at most one writer, without needing any interprocessor - synchronization such as locks or atomics on the reader side.</p> -<p class="Pp" id="PSLIST_INIT">The head of a linked list is represented by a - <var class="Vt">struct pslist_head</var> object allocated by the caller, - e.g. by embedding it in another struct, which should be otherwise treated as - opaque. A linked list head must be initialized with - <code class="Dv">PSLIST_INITIALIZER</code> or - <a class="permalink" href="#PSLIST_INIT"><code class="Fn">PSLIST_INIT</code></a>() - before it may be used. When initialized, a list head represents an empty - list. A list should be empty and destroyed with - <a class="permalink" href="#PSLIST_DESTROY"><code class="Fn" id="PSLIST_DESTROY">PSLIST_DESTROY</code></a>() - before the <var class="Vt">struct pslist_head</var> object's memory is - reused.</p> -<p class="Pp" id="element">Each entry in a linked list is represented by a - <var class="Vt">struct pslist_entry</var> object, also opaque, and embedded - as a member in a caller-allocated structure called an - <a class="permalink" href="#element"><i class="Em">element</i></a>. A - <var class="Vt">struct pslist_entry</var> object must be initialized with - <code class="Dv">PSLIST_ENTRY_INITIALIZER</code> or - <a class="permalink" href="#PSLIST_ENTRY_INIT"><code class="Fn" id="PSLIST_ENTRY_INIT">PSLIST_ENTRY_INIT</code></a>() - before it may be used.</p> -<p class="Pp" id="PSLIST_ENTRY_DESTROY">When initialized, a list entry is - unassociated. Inserting an entry associates it with a particular list. - Removing it partially disassociates it from that list and prevents new - readers from finding it in the list, but allows extant parallel readers to - continue reading the next entry. The caller must then wait, e.g. with - <a class="Xr">pserialize_perform(9)</a>, for all extant parallel readers to - finish, before destroying the list entry with - <a class="permalink" href="#PSLIST_ENTRY_DESTROY"><code class="Fn">PSLIST_ENTRY_DESTROY</code></a>() - and then freeing or reusing its memory.</p> -</section> -<section class="Sh"> -<h1 class="Sh" id="EXCLUSIVE_OPERATIONS"><a class="permalink" href="#EXCLUSIVE_OPERATIONS">EXCLUSIVE - OPERATIONS</a></h1> -<p class="Pp">The following operations may be performed on list heads and - entries when the caller has exclusive access to them — no parallel - writers or readers may have access to the same objects.</p> -<dl class="Bl-tag"> - <dt id="PSLIST_INITIALIZER"><a class="permalink" href="#PSLIST_INITIALIZER"><code class="Dv">PSLIST_INITIALIZER</code></a></dt> - <dd>Constant initializer for a <var class="Vt">struct pslist_head</var> - object.</dd> - <dt><code class="Fn">PSLIST_INIT</code>(<var class="Fa">head</var>)</dt> - <dd>Initialize the list headed by <var class="Fa">head</var> to be empty.</dd> - <dt><code class="Fn">PSLIST_DESTROY</code>(<var class="Fa">head</var>)</dt> - <dd>Destroy the list headed by <var class="Fa">head</var>, which must be - empty. - <p class="Pp">This has an effect only with the - <code class="Dv">DIAGNOSTIC</code> option, so it is not strictly - necessary, but it can help to detect bugs early; see - <a class="Xr">KASSERT(9)</a>.</p> - </dd> - <dt id="PSLIST_ENTRY_INITIALIZER"><a class="permalink" href="#PSLIST_ENTRY_INITIALIZER"><code class="Dv">PSLIST_ENTRY_INITIALIZER</code></a></dt> - <dd>Constant initializer for an unassociated <var class="Vt">struct - pslist_entry</var> object.</dd> - <dt id="PSLIST_ENTRY_INIT~2"><a class="permalink" href="#PSLIST_ENTRY_INIT~2"><code class="Fn">PSLIST_ENTRY_INIT</code></a>(<var class="Fa">element</var>, - <var class="Fa">NAME</var>)</dt> - <dd>Initialize the <var class="Vt">struct pslist_entry</var> object - <var class="Fa">element</var><code class="Li">-></code><var class="Fa">NAME</var>.</dd> - <dt><code class="Fn">PSLIST_ENTRY_DESTROY</code>(<var class="Fa">element</var>, - <var class="Fa">NAME</var>)</dt> - <dd>Destroy the <var class="Vt">struct pslist_entry</var> object - <var class="Fa">element</var><code class="Li">-></code><var class="Fa">NAME</var>. - Either <var class="Fa">element</var> must never have been inserted into a - list, or it must have been inserted and removed, and the caller must have - waited for all parallel readers to finish reading it first.</dd> -</dl> -</section> -<section class="Sh"> -<h1 class="Sh" id="WRITER_OPERATIONS"><a class="permalink" href="#WRITER_OPERATIONS">WRITER - OPERATIONS</a></h1> -<p class="Pp">The following operations may be performed on list heads and - entries when the caller has exclusive - <a class="permalink" href="#write"><i class="Em" id="write">write</i></a> - access to them — parallel readers for the same objects are allowed, - but no parallel writers.</p> -<dl class="Bl-tag"> - <dt id="PSLIST_WRITER_INSERT_HEAD"><a class="permalink" href="#PSLIST_WRITER_INSERT_HEAD"><code class="Fn">PSLIST_WRITER_INSERT_HEAD</code></a>(<var class="Fa">head</var>, - <var class="Fa">element</var>, <var class="Fa">NAME</var>)</dt> - <dd>Insert the element <var class="Fa">element</var> at the beginning of the - list headed by <var class="Fa">head</var>, before any existing elements in - the list. - <p class="Pp">The object - <var class="Fa">element</var><code class="Li">-></code><var class="Fa">NAME</var> - must be a <var class="Vt">struct pslist_entry</var> object which has - been initialized but not inserted.</p> - </dd> - <dt id="PSLIST_WRITER_INSERT_BEFORE"><a class="permalink" href="#PSLIST_WRITER_INSERT_BEFORE"><code class="Fn">PSLIST_WRITER_INSERT_BEFORE</code></a>(<var class="Fa">element</var>, - <var class="Fa">new</var>, <var class="Fa">NAME</var>)</dt> - <dd>Insert the element <var class="Fa">new</var> into a list before the - element <var class="Fa">element</var>. - <p class="Pp">The object - <var class="Fa">element</var><code class="Li">-></code><var class="Fa">NAME</var> - must be a <var class="Vt">struct pslist_entry</var> object which has - been inserted into a list. The object - <var class="Fa">new</var><code class="Li">-></code><var class="Fa">NAME</var> - must be a <var class="Vt">struct pslist_entry</var></p> - </dd> - <dt id="PSLIST_WRITER_INSERT_AFTER"><a class="permalink" href="#PSLIST_WRITER_INSERT_AFTER"><code class="Fn">PSLIST_WRITER_INSERT_AFTER</code></a>(<var class="Fa">element</var>, - <var class="Fa">new</var>, <var class="Fa">NAME</var>)</dt> - <dd>Insert the element <var class="Fa">new</var> into a list after the element - <var class="Fa">element</var>. - <p class="Pp">The object - <var class="Fa">element</var><code class="Li">-></code><var class="Fa">NAME</var> - must be a <var class="Vt">struct pslist_entry</var> object which has - been inserted into a list. The object - <var class="Fa">new</var><code class="Li">-></code><var class="Fa">NAME</var> - must be a <var class="Vt">struct pslist_entry</var></p> - </dd> - <dt id="PSLIST_WRITER_REMOVE"><a class="permalink" href="#PSLIST_WRITER_REMOVE"><code class="Fn">PSLIST_WRITER_REMOVE</code></a>(<var class="Fa">element</var>, - <var class="Fa">NAME</var>)</dt> - <dd>Remove the element <var class="Fa">element</var> from the list into which - it has been inserted. - <p class="Pp">The object - <var class="Fa">element</var><code class="Li">-></code><var class="Fa">NAME</var> - must be a <var class="Vt">struct pslist_entry</var> object which has - been inserted into a list.</p> - </dd> - <dt id="PSLIST_WRITER_FIRST"><a class="permalink" href="#PSLIST_WRITER_FIRST"><code class="Fn">PSLIST_WRITER_FIRST</code></a>(<var class="Fa">head</var>, - <var class="Fa">type</var>, <var class="Fa">NAME</var>)</dt> - <dd>Return a pointer to the first element <var class="Fa">o</var> of type - <var class="Fa">type</var> with a <var class="Vt">struct - pslist_entry</var> member - <var class="Fa">o</var><code class="Li">-></code><var class="Fa">NAME</var>, - or <code class="Dv">NULL</code> if the list is empty.</dd> - <dt id="PSLIST_WRITER_NEXT"><a class="permalink" href="#PSLIST_WRITER_NEXT"><code class="Fn">PSLIST_WRITER_NEXT</code></a>(<var class="Fa">element</var>, - <var class="Fa">type</var>, <var class="Fa">NAME</var>)</dt> - <dd>Return a pointer to the next element <var class="Fa">o</var> of type - <var class="Fa">type</var> with a <var class="Vt">struct - pslist_entry</var> member - <var class="Fa">o</var><code class="Li">-></code><var class="Fa">NAME</var> - after <var class="Fa">element</var> in a list, or - <code class="Dv">NULL</code> if there are no elements after - <var class="Fa">element</var>.</dd> - <dt id="PSLIST_WRITER_FOREACH"><a class="permalink" href="#PSLIST_WRITER_FOREACH"><code class="Fn">PSLIST_WRITER_FOREACH</code></a>(<var class="Fa">element</var>, - <var class="Fa">head</var>, <var class="Fa">type</var>, - <var class="Fa">NAME</var>)</dt> - <dd>Loop header for iterating over each element <var class="Fa">element</var> - of type <var class="Fa">type</var> with <var class="Vt">struct - pslist_entry</var> member - <var class="Fa">element</var><code class="Li">-></code><var class="Fa">NAME</var> - starting at the list head <var class="Fa">head</var>. - <p class="Pp">The caller must not modify the list while iterating over - it.</p> - </dd> -</dl> -</section> -<section class="Sh"> -<h1 class="Sh" id="READER_OPERATIONS"><a class="permalink" href="#READER_OPERATIONS">READER - OPERATIONS</a></h1> -<p class="Pp">The following operations may be performed on list heads and - entries when the caller is in a passively serialized read section — - see <a class="Xr">pserialize(9)</a>.</p> -<dl class="Bl-tag"> - <dt id="PSLIST_READER_FIRST"><a class="permalink" href="#PSLIST_READER_FIRST"><code class="Fn">PSLIST_READER_FIRST</code></a>(<var class="Fa">head</var>, - <var class="Fa">type</var>, <var class="Fa">NAME</var>)</dt> - <dd>Return a pointer to the first element <var class="Fa">o</var> of type - <var class="Fa">type</var> with a <var class="Vt">struct - pslist_entry</var> member - <var class="Fa">o</var><code class="Li">-></code><var class="Fa">NAME</var>, - or <code class="Dv">NULL</code> if the list is empty.</dd> - <dt id="PSLIST_READER_NEXT"><a class="permalink" href="#PSLIST_READER_NEXT"><code class="Fn">PSLIST_READER_NEXT</code></a>(<var class="Fa">element</var>, - <var class="Fa">type</var>, <var class="Fa">NAME</var>)</dt> - <dd>Return a pointer to the next element <var class="Fa">o</var> of type - <var class="Fa">type</var> with a <var class="Vt">struct - pslist_entry</var> member - <var class="Fa">o</var><code class="Li">-></code><var class="Fa">NAME</var> - after <var class="Fa">element</var> in a list, or - <code class="Dv">NULL</code> if there are no elements after - <var class="Fa">element</var>.</dd> - <dt id="PSLIST_READER_FOREACH"><a class="permalink" href="#PSLIST_READER_FOREACH"><code class="Fn">PSLIST_READER_FOREACH</code></a>(<var class="Fa">element</var>, - <var class="Fa">head</var>, <var class="Fa">type</var>, - <var class="Fa">NAME</var>)</dt> - <dd>Loop header for iterating over each element <var class="Fa">element</var> - of type <var class="Fa">type</var> with <var class="Vt">struct - pslist_entry</var> member - <var class="Fa">element</var><code class="Li">-></code><var class="Fa">NAME</var> - starting at the list head <var class="Fa">head</var>.</dd> -</dl> -</section> -<section class="Sh"> -<h1 class="Sh" id="EXAMPLES"><a class="permalink" href="#EXAMPLES">EXAMPLES</a></h1> -<p class="Pp">Example frotz structure and global state:</p> -<div class="Bd Pp Li"> -<pre> struct frotz { - uint64_t f_key; - uint64_t f_datum; - struct pslist_entry f_entry; - }; - - static struct { - kmutex_t lock; - pserialize_t psz; - struct pslist_head list; - struct pool pool; - } frobnitzem __cacheline_aligned;</pre> -</div> -<p class="Pp">Initialize the global state:</p> -<div class="Bd Pp Li"> -<pre> mutex_init(&frobnitzem.lock, MUTEX_DEFAULT, IPL_NONE); - frobnitzem.psz = pserialize_create(); - PSLIST_INIT(&frobnitzem.list); - pool_init(&frobnitzem.pool, sizeof(struct frotz), ...);</pre> -</div> -<p class="Pp">Create and publish a frotz:</p> -<div class="Bd Pp Li"> -<pre> uint64_t key = ...; - uint64_t datum = ...; - - struct frotz *f = pool_get(&frobnitzem.pool, PR_WAITOK); - - /* Initialize f. */ - f->f_key = key; - f->f_datum = datum; - PSLIST_ENTRY_INIT(f, f_entry); - - /* Publish it. */ - mutex_enter(&frobnitzem.lock); - PSLIST_WRITER_INSERT_HEAD(&frobnitzem.list, f, f_entry); - mutex_exit(&frobnitzem.lock);</pre> -</div> -<p class="Pp">Look up a frotz and return its associated datum:</p> -<div class="Bd Pp Li"> -<pre> uint64_t key = ...; - struct frotz *f; - int error = ENOENT; - int s; - - s = pserialize_read_enter(); - PSLIST_READER_FOREACH(f, &frobnitzem.list, struct frotz, f_entry) { - if (f->f_key == key) { - *datump = f->f_datum; - error = 0; - break; - } - } - pserialize_read_exit(s); - return error;</pre> -</div> -<p class="Pp">Remove a frotz and wait for readers to finish using it before - reusing the memory allocated for it:</p> -<div class="Bd Pp Li"> -<pre> struct frotz *f = ...; - - mutex_enter(&frobnitzem.lock); - PSLIST_WRITER_REMOVE(f, f_entry); - mutex_exit(&frobnitzem.lock); - - pserialize_perform(&frobnitzem.psz); - - PSLIST_ENTRY_DESTROY(f, f_entry); - pool_put(&frobnitzem.pool, f);</pre> -</div> -</section> -<section class="Sh"> -<h1 class="Sh" id="CODE_REFERENCES"><a class="permalink" href="#CODE_REFERENCES">CODE - REFERENCES</a></h1> -<p class="Pp">The <code class="Nm">pslist</code> data structure is implemented - by static inlines and macros in - <span class="Pa">sys/sys/pslist.h</span>.</p> -</section> -<section class="Sh"> -<h1 class="Sh" id="SEE_ALSO"><a class="permalink" href="#SEE_ALSO">SEE - ALSO</a></h1> -<p class="Pp"><a class="Xr">queue(3)</a>, <a class="Xr">pserialize(9)</a>, - <a class="Xr">psref(9)</a></p> -</section> -<section class="Sh"> -<h1 class="Sh" id="HISTORY"><a class="permalink" href="#HISTORY">HISTORY</a></h1> -<p class="Pp">The <code class="Nm">pslist</code> data structure first appeared - in <span class="Ux">NetBSD 8.0</span>.</p> -</section> -<section class="Sh"> -<h1 class="Sh" id="AUTHORS"><a class="permalink" href="#AUTHORS">AUTHORS</a></h1> -<p class="Pp"><span class="An">Taylor R Campbell</span> - <<a class="Mt" href="mailto:riastradh@NetBSD.org">riastradh@NetBSD.org</a>></p> -</section> -</div> -<table class="foot"> - <tr> - <td class="foot-date">July 7, 2016</td> - <td class="foot-os">NetBSD 10.1</td> - </tr> -</table> |