Changeset View
Standalone View
share/man/man9/seqc.9
- This file was added.
.\" | |||||
.\" Copyright (C) 2019 Mariusz Zaborski <oshogbo@FreeBSD.org> | |||||
.\" | |||||
.\" Redistribution and use in source and binary forms, with or without | |||||
.\" modification, are permitted provided that the following conditions | |||||
.\" are met: | |||||
.\" 1. Redistributions of source code must retain the above copyright | |||||
.\" notice(s), this list of conditions and the following disclaimer as | |||||
.\" the first lines of this file unmodified other than the possible | |||||
.\" addition of one or more copyright notices. | |||||
.\" 2. Redistributions in binary form must reproduce the above copyright | |||||
.\" notice(s), this list of conditions and the following disclaimer in the | |||||
.\" documentation and/or other materials provided with the distribution. | |||||
.\" | |||||
.\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER(S) ``AS IS'' AND ANY | |||||
.\" EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED | |||||
.\" WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE | |||||
.\" DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER(S) BE LIABLE FOR ANY | |||||
.\" DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |||||
.\" (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |||||
.\" SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER | |||||
.\" CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |||||
.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |||||
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH | |||||
.\" DAMAGE. | |||||
.\" | |||||
.\" $FreeBSD$ | |||||
.\" | |||||
.Dd June 7, 2019 | |||||
.Dt SEQC 9 | |||||
.Os | |||||
.Sh NAME | |||||
.Nm seqc_consistent , | |||||
.Nm seqc_read , | |||||
.Nm seqc_write_begin , | |||||
.Nm seqc_write_end | |||||
.Nd "lockless read algorithm" | |||||
.Sh SYNOPSIS | |||||
.In sys/seqc.h | |||||
.Ft void | |||||
.Fn seqc_write_begin "seqc_t *seqcp" | |||||
.Ft void | |||||
.Fn seqc_write_end "seqc_t *seqcp" | |||||
.Ft seqc_t | |||||
.Fn seqc_read "seqc_t *seqcp" | |||||
.Ft seqc_t | |||||
.Fn seqc_consistent "const seqc_t *seqcp" "seqc_t oldseqc" | |||||
.Sh DESCRIPTION | |||||
The | |||||
.Nm seqc | |||||
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, | |||||
markj: I think this can be more precise. Something like, seqc allows zero or more readers and zero or… | |||||
but readers may be starved indefinitely by writers. | |||||
.Pp | |||||
Done Inline ActionsThis is mixing the interface with the implementation details. I would separate the two: explain the interface first, and the optionally describe the implementation. markj: This is mixing the interface with the implementation details. I would separate the two: explain… | |||||
Done Inline ActionsI moved it after discribing interface. oshogbo: I moved it after discribing interface. | |||||
The functions | |||||
Done Inline Actionshas changed emaste: has change**d** | |||||
Done Inline ActionsThe sentence, "The writer functions..." is describing the implementation. I would just get rid of it. markj: The sentence, "The writer functions..." is describing the implementation. I would just get rid… | |||||
.Fn seqc_write_begin | |||||
and | |||||
.Fn seqc_write_end | |||||
Done Inline Actionscan drop had here emaste: can drop `had` here | |||||
are used to create a transaction for writer, and notify the readers that the | |||||
object will be modified. | |||||
.Pp | |||||
The | |||||
.Fn seqc_read | |||||
function returns the current sequence number, beginning a read transaction. | |||||
If a writer is executing a transaction, this function will spin until the | |||||
Done Inline Actions"the current sequence number, beginning a read transaction." markj: "the current sequence number, beginning a read transaction." | |||||
transaction has ended. | |||||
Done Inline ActionsThese two sentences aren't really right. They are conflating fences and locking. The point is that seqc(9) always provides the appropriate fencing, but on amd64 (and some other platforms), the implementation does not require any CPU fences at all. Look at atomic_thread_fence_rel() on amd64 for instance. Consumers of the interface must ensure that two writers are not executing at the same time. It is probably worth stating that explicitly. markj: These two sentences aren't really right. They are conflating fences and locking. The point is… | |||||
Done Inline Actions"If a writer is executing a transaction..." markj: "If a writer is executing a transaction..." | |||||
.Pp | |||||
The | |||||
.Fn seqc_consistent | |||||
function compares a sequence number returned by | |||||
Not Done Inline ActionsAMD? emaste: AMD? | |||||
Done Inline ActionsThis is what the comment say in seqc.9 oshogbo: This is what the comment say in seqc.9 | |||||
Done Inline ActionsPresumably amd64? I would not even write "modern" in that case. markj: Presumably amd64? I would not even write "modern" in that case. | |||||
Not Done Inline Actions"... compares a sequence number returned by .Fn seqc_read with the current sequence number." Then the next sentence can be deleted. markj: "... compares a sequence number returned by .Fn seqc_read with the current sequence number."… | |||||
Not Done Inline Actions"compares the sequence number with a previously fetched value." markj: "compares the sequence number with a previously fetched value." | |||||
.Fn seqc_read | |||||
with the current sequence number. | |||||
Done Inline ActionsMaybe, "If a writer has started a transaction, this function will spin until the transaction has ended." markj: Maybe, "If a writer has started a transaction, this function will spin until the transaction… | |||||
.Pp | |||||
At the end of a read transaction, | |||||
.Fn seqc_consistent | |||||
Done Inline Actionstypo: sequence markj: typo: sequence | |||||
should be used to determine whether a writer updated the object. | |||||
Not Done Inline Actions"At the end of a read transaction, .Fn seqc_consistent should be used to determine whether a writer updated the object. If so, the read transaction should be restarted. Otherwise, the read was consistent." markj: "At the end of a read transaction, .Fn seqc_consistent should be used to determine whether a… | |||||
If so, the read transaction should be restarted. | |||||
Otherwise, the read was consistent. | |||||
.Sh EXAMPLES | |||||
In the following example a writer modifies the | |||||
.Va var1 | |||||
and | |||||
.Va | |||||
var2 variables in | |||||
Not Done Inline Actions"In the following example a writer modifies the .Va var1 and .Va var2 fields in .Va obj ." markj: "In the following example a writer modifies the .Va var1 and .Va var2 fields in .Va obj ." | |||||
Not Done Inline Actionschange -> changes "var1", "var2" and "obj" should be annotated with .Va. markj: change -> changes
"var1", "var2" and "obj" should be annotated with .Va. | |||||
.Va obj | |||||
structure: | |||||
.Bd -literal | |||||
lock_exclusive(&obj->lock); | |||||
seqc_write_begin(&obj->seqc); | |||||
obj->var1 = 1; | |||||
obj->var2 = 2; | |||||
seqc_write_end(&obj->seqc); | |||||
unlock_exclusive(&obj->lock); | |||||
.Ed | |||||
Not Done Inline ActionsSame comment as above, with read -> reads. markj: Same comment as above, with read -> reads. | |||||
The following code will obtain a consistent snapshot of | |||||
Not Done Inline ActionsThese are just two parts of the same example. So I would write, "The following code will obtain a consistent snapshot of .Va var1 and .Var var2:" markj: These are just two parts of the same example. So I would write,
"The following code will… | |||||
.Va var1 | |||||
Not Done Inline Actions"In the case where the..." markj: "In the case where the..." | |||||
and | |||||
.Va var2 : | |||||
.Bd -literal | |||||
int var1, var2; | |||||
seqc_t seqc; | |||||
for (;;) { | |||||
seqc = seqc_read(&obj->seqc); | |||||
var1 = obj->var1; | |||||
Done Inline ActionsStyle: should be indented by a tab. markj: Style: should be indented by a tab. | |||||
var2 = obj->var2; | |||||
if (seqc_consistent(&obj->seqc, seqc)) | |||||
break; | |||||
} | |||||
.Ed | |||||
.Sh AUTHORS | |||||
The | |||||
.Nm seqc | |||||
functions was implemented by | |||||
.An Mateusz Guzik Aq Mt mjg@FreeBSD.org . | |||||
This manual page was written by | |||||
.An Mariusz Zaborski Aq Mt oshogbo@FreeBSD.org . | |||||
.Sh CAVEATS | |||||
There is no guarantee of progress for readers. | |||||
In case when there are a lot of writers the reader can be starved. | |||||
Done Inline Actions... for readers. markj: ... for readers. | |||||
mjgUnsubmitted Not Done Inline ActionsIt can be noted that a consumer possibly concerned with this can resort to locking after n failed attempts to read. mjg: It can be noted that a consumer possibly concerned with this can resort to locking after n… | |||||
.Pp | |||||
Theoretically if reading takes a very long time, and when there are many writers | |||||
the counter may overflow. | |||||
Done Inline ActionsThis part is not true, otherwise it would be a serious flaw. The algorithm does not handle multiple concurrent writers. The caller must provide mutual exclusion. markj: This part is not true, otherwise it would be a serious flaw. The algorithm does not handle… | |||||
Done Inline ActionsSorry, I misunderstood. You are right. markj: Sorry, I misunderstood. You are right. | |||||
In that case the reader will not notice that the object was changed. | |||||
mjgUnsubmitted Not Done Inline ActionsThis is inaccurate. The counter overflowing at some point is not a necessarily a problem, in fact it can keep overflowing without causing any issues. The problem is when it wraps back to the original value, as stated in the comment. mjg: This is inaccurate. The counter overflowing at some point is not a necessarily a problem, in… | |||||
Given that this needs 4 billion transactional writes across a single contended | |||||
reader, it is unlikely to ever happen. | |||||
mjgUnsubmitted Not Done Inline ActionsA note can be added that the problem is fixable in practice by extending the counter type to 64 bit. mjg: A note can be added that the problem is fixable in practice by extending the counter type to 64… | |||||
Not Done Inline ActionsThe wording implies that the consumer can use 64-bit integers, but they can't because we use the opaque seqc_t typedef. Maybe, "This could be avoided by extending the interface to allow 64-bit counters." markj: The wording implies that the consumer can use 64-bit integers, but they can't because we use… |
I think this can be more precise. Something like, seqc 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.