2 .\" Copyright (C) 2019 Mariusz Zaborski <oshogbo@FreeBSD.org>
4 .\" Redistribution and use in source and binary forms, with or without
5 .\" modification, are permitted provided that the following conditions
7 .\" 1. Redistributions of source code must retain the above copyright
8 .\" notice(s), this list of conditions and the following disclaimer as
9 .\" the first lines of this file unmodified other than the possible
10 .\" addition of one or more copyright notices.
11 .\" 2. Redistributions in binary form must reproduce the above copyright
12 .\" notice(s), this list of conditions and the following disclaimer in the
13 .\" documentation and/or other materials provided with the distribution.
15 .\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY
16 .\" EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17 .\" WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18 .\" DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE LIABLE FOR ANY
19 .\" DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20 .\" (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21 .\" SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
22 .\" CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
35 .Nm seqc_write_begin ,
37 .Nd "lockless read algorithm"
41 .Fn seqc_write_begin "seqc_t *seqcp"
43 .Fn seqc_write_end "seqc_t *seqcp"
45 .Fn seqc_read "seqc_t *seqcp"
47 .Fn seqc_consistent "const seqc_t *seqcp" "seqc_t oldseqc"
51 allows zero or more readers and zero or one writer to concurrently access
52 an object, providing a consistent snapshot of the object for readers.
53 No mutual exclusion between readers and writers is required,
54 but readers may be starved indefinitely by writers.
60 are used to create a transaction for writer, and notify the readers that the
61 object will be modified.
65 function returns the current sequence number.
66 If a writer has started a transaction, this function will spin until the
67 transaction has ended.
71 function compares the sequence number with a previously fetched value.
74 variable should contain a sequence number from the beginning of read
77 The reader at the end of a transaction checks if the sequence number has
79 If the sequence number didn't change the object wasn't modified, and fetched
81 If the sequence number changed the object was modified and the fetch should be
83 In case when sequence number is odd the object change is in progress and the
84 reader will wait until the write will the sequence number will become even.
86 The following example for a writer changees the
94 lock_exclusive(&obj->lock);
95 seqc_write_begin(&obj->seqc);
98 seqc_write_end(&obj->seqc);
99 unlock_exclusive(&obj->lock);
101 The following example for a reader reads the
108 In the case where the sequence number was changed it restarts the whole process.
114 seqc = seqc_read(&obj->seqc);
117 if (seqc_consistent(&obj->seqc, seqc))
124 functions was implemented by
125 .An Mateusz Guzik Aq Mt mjg@FreeBSD.org .
126 This manual page was written by
127 .An Mariusz Zaborski Aq Mt oshogbo@FreeBSD.org .
129 There is no guarantee of progress for readers.
130 In case when there are a lot of writers the reader can be starved.
131 This concern may be solved by returning error after a few attempts.
133 Theoretically if reading takes a very long time, and when there are many writers
134 the counter may overflow and wrap around to the same value.
135 In that case the reader will not notice that the object was changed.
136 Given that this needs 4 billion transactional writes across a single contended
137 reader, it is unlikely to ever happen.
138 This could be avoided by extending the interface to allow 64-bit counters.