Page MenuHomeFreeBSD
Files F143477114

D16744.id58370.diff
No OneTemporary
Actions

D16744.id58370.diff
View Options

Index: share/man/man9/Makefile
===================================================================
--- share/man/man9/Makefile
+++ share/man/man9/Makefile
@@ -292,6 +292,7 @@
securelevel_gt.9 \
selrecord.9 \
sema.9 \
+ seqc.9 \
sf_buf.9 \
sglist.9 \
shm_map.9 \
@@ -1817,6 +1818,10 @@
sema.9 sema_trywait.9 \
sema.9 sema_value.9 \
sema.9 sema_wait.9
+MLINKS+=seqc.9 seqc_consistent.9 \
+ seqc.9 seqc_read.9 \
+ seqc.9 seqc_write_begin.9 \
+ seqc.9 seqc_write_end.9
MLINKS+=sf_buf.9 sf_buf_alloc.9 \
sf_buf.9 sf_buf_free.9 \
sf_buf.9 sf_buf_kva.9 \
Index: share/man/man9/seqc.9
===================================================================
--- /dev/null
+++ share/man/man9/seqc.9
@@ -0,0 +1,127 @@
+.\"
+.\" 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,
+but readers may be starved indefinitely by writers.
+.Pp
+The functions
+.Fn seqc_write_begin
+and
+.Fn seqc_write_end
+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
+transaction has ended.
+.Pp
+The
+.Fn seqc_consistent
+function compares a sequence number returned by
+.Fn seqc_read
+with the current sequence number.
+.Pp
+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.
+.Sh EXAMPLES
+In the following example a writer modifies the
+.Va var1
+and
+.Va
+var2 variables in
+.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
+The following code will obtain a consistent snapshot of
+.Va var1
+and
+.Va var2 :
+.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;
+}
+.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.
+.Pp
+Theoretically if reading takes a very long time, and when there are many writers
+the counter may overflow.
+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.
Index: sys/sys/seqc.h
===================================================================
--- sys/sys/seqc.h
+++ sys/sys/seqc.h
@@ -40,55 +40,6 @@
#ifdef _KERNEL
-/*
- * seqc allows readers and writers to work with a consistent snapshot. Modifying
- * operations must be enclosed within a transaction delineated by
- * seqc_write_beg/seqc_write_end. The trick works by having the writer increment
- * the sequence number twice, at the beginning and end of the transaction.
- * The reader detects that the sequence number has not changed between its start
- * and end, and that the sequence number is even, to validate consistency.
- *
- * Some fencing (both hard fencing and compiler barriers) may be needed,
- * depending on the cpu. Modern AMD cpus provide strong enough guarantees to not
- * require any fencing by the reader or writer.
- *
- * Example usage:
- *
- * writers:
- * lock_exclusive(&obj->lock);
- * seqc_write_begin(&obj->seqc);
- * obj->var1 = ...;
- * obj->var2 = ...;
- * seqc_write_end(&obj->seqc);
- * unlock_exclusive(&obj->lock);
- *
- * readers:
- * 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;
- * }
- * .....
- *
- * Writers may not block or sleep in any way.
- *
- * There are 2 minor caveats in this implementation:
- *
- * 1. There is no guarantee of progress. That is, a large number of writers can
- * interfere with the execution of the readers and cause the code to live-lock
- * in a loop trying to acquire a consistent snapshot.
- *
- * 2. If the reader loops long enough, the counter may overflow and eventually
- * wrap back to its initial value, fooling the reader into accepting the
- * snapshot. Given that this needs 4 billion transactional writes across a
- * single contended reader, it is unlikely to ever happen.
- */
-
/* A hack to get MPASS macro */
#include <sys/lock.h>

File Metadata

Mime Type
text/plain
Expires
Sat, Jan 31, 5:20 PM (3 h, 46 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
28138093
Default Alt Text
D16744.id58370.diff (6 KB)

Event Timeline