1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
<table class="head">
<tr>
<td class="head-ltitle">SEQC(9)</td>
<td class="head-vol">Kernel Developer's Manual</td>
<td class="head-rtitle">SEQC(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">seqc_consistent</code>,
<code class="Nm">seqc_read</code>, <code class="Nm">seqc_write_begin</code>,
<code class="Nm">seqc_write_end</code> — <span class="Nd">lockless
read algorithm</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/seqc.h</a>></code></p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">seqc_write_begin</code>(<var class="Fa" style="white-space: nowrap;">seqc_t
*seqcp</var>);</p>
<p class="Pp"><var class="Ft">void</var>
<br/>
<code class="Fn">seqc_write_end</code>(<var class="Fa" style="white-space: nowrap;">seqc_t
*seqcp</var>);</p>
<p class="Pp"><var class="Ft">seqc_t</var>
<br/>
<code class="Fn">seqc_read</code>(<var class="Fa" style="white-space: nowrap;">seqc_t
*seqcp</var>);</p>
<p class="Pp"><var class="Ft">seqc_t</var>
<br/>
<code class="Fn">seqc_consistent</code>(<var class="Fa" style="white-space: nowrap;">const
seqc_t *seqcp</var>, <var class="Fa" style="white-space: nowrap;">seqc_t
oldseqc</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">seqc</code> allows zero or more readers and
zero or one writer to concurrently access an object, providing a consistent
snapshot of the object for readers. No mutual exclusion between readers and
writers is required, but readers may be starved indefinitely by writers.</p>
<p class="Pp" id="seqc_write_begin">The functions
<a class="permalink" href="#seqc_write_begin"><code class="Fn">seqc_write_begin</code></a>()
and
<a class="permalink" href="#seqc_write_end"><code class="Fn" id="seqc_write_end">seqc_write_end</code></a>()
are used to create a transaction for writer, and notify the readers that the
object will be modified.</p>
<p class="Pp" id="seqc_read">The
<a class="permalink" href="#seqc_read"><code class="Fn">seqc_read</code></a>()
function returns the current sequence number. If a writer has started a
transaction, this function will spin until the transaction has ended.</p>
<p class="Pp" id="seqc_consistent">The
<a class="permalink" href="#seqc_consistent"><code class="Fn">seqc_consistent</code></a>()
function compares the sequence number with a previously fetched value. The
<var class="Fa">oldseqc</var> variable should contain a sequence number from
the beginning of read transaction.</p>
<p class="Pp">The reader at the end of a transaction checks if the sequence
number has changed. If the sequence number didn't change the object wasn't
modified, and fetched variables are valid. If the sequence number changed
the object was modified and the fetch should be repeated. In case when
sequence number is odd the object change is in progress and the reader will
wait until the write will the sequence number will become even.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="EXAMPLES"><a class="permalink" href="#EXAMPLES">EXAMPLES</a></h1>
<p class="Pp">The following example for a writer changes the
<var class="Va">var1</var> and <var class="Va">var2</var> variables in the
<var class="Va">obj</var> structure:</p>
<div class="Bd Pp Li">
<pre>lock_exclusive(&obj->lock);
seqc_write_begin(&obj->seqc);
obj->var1 = 1;
obj->var2 = 2;
seqc_write_end(&obj->seqc);
unlock_exclusive(&obj->lock);</pre>
</div>
<p class="Pp">The following example for a reader reads the
<var class="Va">var1</var> and <var class="Va">var2</var> variables from the
<var class="Va">obj</var> structure. In the case where the sequence number
was changed it restarts the whole process.</p>
<div class="Bd Pp Li">
<pre>int var1, var2;
seqc_t seqc;
for (;;) {
seqc = seqc_read(&obj->seqc);
var1 = obj->var1;
var2 = obj->var2;
if (seqc_consistent(&obj->seqc, seqc))
break;
}</pre>
</div>
</section>
<section class="Sh">
<h1 class="Sh" id="AUTHORS"><a class="permalink" href="#AUTHORS">AUTHORS</a></h1>
<p class="Pp">The <code class="Nm">seqc</code> functions was implemented by
<span class="An">Mateusz Guzik</span>
<<a class="Mt" href="mailto:mjg@FreeBSD.org">mjg@FreeBSD.org</a>>.
This manual page was written by
<br/>
<span class="An">Mariusz Zaborski</span>
<<a class="Mt" href="mailto:oshogbo@FreeBSD.org">oshogbo@FreeBSD.org</a>>.</p>
</section>
<section class="Sh">
<h1 class="Sh" id="CAVEATS"><a class="permalink" href="#CAVEATS">CAVEATS</a></h1>
<p class="Pp">There is no guarantee of progress for readers. In case when there
are a lot of writers the reader can be starved. This concern may be solved
by returning error after a few attempts.</p>
<p class="Pp">Theoretically if reading takes a very long time, and when there
are many writers the counter may overflow and wrap around to the same value.
In that case the reader will not notice that the object was changed. Given
that this needs 4 billion transactional writes across a single contended
reader, it is unlikely to ever happen. This could be avoided by extending
the interface to allow 64-bit counters.</p>
</section>
</div>
<table class="foot">
<tr>
<td class="foot-date">July 29, 2019</td>
<td class="foot-os">FreeBSD 15.0</td>
</tr>
</table>
|
