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 May 24, 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. | |||||
If a writer has started a transaction, this function will spin until the transaction has ended. | |||||
Done Inline Actions"the current sequence number, beginning a read transaction." markj: "the current sequence number, beginning a read transaction." | |||||
.Pp | |||||
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..." | |||||
The | |||||
.Fn seqc_consistent | |||||
function compares the current state of the sequence number. | |||||
markjUnsubmitted Not Done Inline Actions"compares the sequence number with a previously fetched value." markj: "compares the sequence number with a previously fetched value." | |||||
The | |||||
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."… | |||||
.Fa oldseqc | |||||
variable should contain a sequence number from the beginning of read | |||||
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… | |||||
transaction. | |||||
.Pp | |||||
The reader at the end of a transaction checks if the sequence number has changed. | |||||
Done Inline Actionstypo: sequence markj: typo: sequence | |||||
If the sequence number didn't change the object wasn't modified, and fetched | |||||
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… | |||||
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. | |||||
.Sh EXAMPLES | |||||
The following example for a writer change the var1 and var2 variables in the | |||||
markjUnsubmitted 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. | |||||
obj structure: | |||||
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 ." | |||||
.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 | |||||
The following example for a reader read the var1 and var2 variables from the obj | |||||
markjUnsubmitted Not Done Inline ActionsSame comment as above, with read -> reads. markj: Same comment as above, with read -> reads. | |||||
structure. | |||||
In case when the sequence number was changed it restarts the whole process. | |||||
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… | |||||
markjUnsubmitted Not Done Inline Actions"In the case where the..." markj: "In the case where the..." | |||||
.Bd -literal | |||||
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; | |||||
Done Inline ActionsStyle: should be indented by a tab. markj: Style: should be indented by a tab. | |||||
} | |||||
.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. | |||||
This concern may be solved by returning error after a few attempts. | |||||
.Pp | |||||
Theoretically if reading takes a very long time, and when there are many writers | |||||
Done Inline Actions... for readers. markj: ... for readers. | |||||
the counter may overflow and wrap around to the same value. | |||||
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… | |||||
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 | |||||
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. | |||||
reader, it is unlikely to ever happen. | |||||
This can be omitted by extending counter to the 64bits integer. | |||||
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… | |||||
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… | |||||
markjUnsubmitted 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.