Page MenuHomeFreeBSD
Files F132996324

D16744.id57593.diff
No OneTemporary
Actions

D16744.id57593.diff
View Options

Index: share/man/man9/Makefile
===================================================================
--- share/man/man9/Makefile
+++ share/man/man9/Makefile
@@ -291,6 +291,7 @@
securelevel_gt.9 \
selrecord.9 \
sema.9 \
+ seqc.9 \
sf_buf.9 \
sglist.9 \
shm_map.9 \
@@ -1811,6 +1812,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) 2018 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 August 16, 2018
+.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
+interface allows readers and writers to work with a consistent snapshot
+using a object sequence number instead of using heavy locks.
+The writer functions increment the sequence number twice, at the beginning and
+end of the transaction.
+The reader at the end of a transaction checks if the sequence number has change.
+If the sequence number didn't change the object wasn't modified, and fetched
+variables are valid.
+If the sequence number had 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.
+.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.
+Some additional locking may be needed, depending on the CPU.
+Modern AMD CPUs provide strong enough guarantees to not require any fencing by
+the reader or writer.
+.Pp
+The
+.Fn seqc_read
+function returns the current sequance number.
+In case when the writing is in progress this function will spin until the
+process will end.
+.Pp
+The
+.Fn seqc_consistent
+function compares the current state of the sequence number.
+The
+.Fa oldseqc
+variable should contain a sequence number from the beginning of read
+transaction.
+.Sh EXAMPLES
+The following example for a writer change the var1 and var2 variables in the
+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 example for a reader read the var1 and var2 variables from the obj
+structure.
+In case when the sequence number was changed it restarts the whole process.
+.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.
+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 seqcuence number twice, at the beginning and end of the transaction.
- * The reader detects that the seqcuence number has not changed between its start
- * and end, and that the seqcuence 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
Wed, Oct 22, 10:21 PM (10 h, 21 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
24070525
Default Alt Text
D16744.id57593.diff (7 KB)

Event Timeline