1.\" 2.\" Copyright (C) 2019 Mariusz Zaborski <oshogbo@FreeBSD.org> 3.\" 4.\" Redistribution and use in source and binary forms, with or without 5.\" modification, are permitted provided that the following conditions 6.\" are met: 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. 14.\" 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 25.\" DAMAGE. 26.\" 27.\" $FreeBSD$ 28.\" 29.Dd July 29, 2019 30.Dt SEQC 9 31.Os 32.Sh NAME 33.Nm seqc_consistent , 34.Nm seqc_read , 35.Nm seqc_write_begin , 36.Nm seqc_write_end 37.Nd "lockless read algorithm" 38.Sh SYNOPSIS 39.In sys/seqc.h 40.Ft void 41.Fn seqc_write_begin "seqc_t *seqcp" 42.Ft void 43.Fn seqc_write_end "seqc_t *seqcp" 44.Ft seqc_t 45.Fn seqc_read "seqc_t *seqcp" 46.Ft seqc_t 47.Fn seqc_consistent "const seqc_t *seqcp" "seqc_t oldseqc" 48.Sh DESCRIPTION 49The 50.Nm seqc 51allows zero or more readers and zero or one writer to concurrently access 52an object, providing a consistent snapshot of the object for readers. 53No mutual exclusion between readers and writers is required, 54but readers may be starved indefinitely by writers. 55.Pp 56The functions 57.Fn seqc_write_begin 58and 59.Fn seqc_write_end 60are used to create a transaction for writer, and notify the readers that the 61object will be modified. 62.Pp 63The 64.Fn seqc_read 65function returns the current sequence number. 66If a writer has started a transaction, this function will spin until the 67transaction has ended. 68.Pp 69The 70.Fn seqc_consistent 71function compares the sequence number with a previously fetched value. 72The 73.Fa oldseqc 74variable should contain a sequence number from the beginning of read 75transaction. 76.Pp 77The reader at the end of a transaction checks if the sequence number has 78changed. 79If the sequence number didn't change the object wasn't modified, and fetched 80variables are valid. 81If the sequence number changed the object was modified and the fetch should be 82repeated. 83In case when sequence number is odd the object change is in progress and the 84reader will wait until the write will the sequence number will become even. 85.Sh EXAMPLES 86The following example for a writer changees the 87.Va var1 88and 89.Va var2 90variables in the 91.Va obj 92structure: 93.Bd -literal 94lock_exclusive(&obj->lock); 95seqc_write_begin(&obj->seqc); 96obj->var1 = 1; 97obj->var2 = 2; 98seqc_write_end(&obj->seqc); 99unlock_exclusive(&obj->lock); 100.Ed 101The following example for a reader reads the 102.Va var1 103and 104.Va var2 105variables from the 106.Va obj 107structure. 108In the case where the sequence number was changed it restarts the whole process. 109.Bd -literal 110int var1, var2; 111seqc_t seqc; 112 113for (;;) { 114 seqc = seqc_read(&obj->seqc); 115 var1 = obj->var1; 116 var2 = obj->var2; 117 if (seqc_consistent(&obj->seqc, seqc)) 118 break; 119} 120.Ed 121.Sh AUTHORS 122The 123.Nm seqc 124functions was implemented by 125.An Mateusz Guzik Aq Mt mjg@FreeBSD.org . 126This manual page was written by 127.An Mariusz Zaborski Aq Mt oshogbo@FreeBSD.org . 128.Sh CAVEATS 129There is no guarantee of progress for readers. 130In case when there are a lot of writers the reader can be starved. 131This concern may be solved by returning error after a few attempts. 132.Pp 133Theoretically if reading takes a very long time, and when there are many writers 134the counter may overflow and wrap around to the same value. 135In that case the reader will not notice that the object was changed. 136Given that this needs 4 billion transactional writes across a single contended 137reader, it is unlikely to ever happen. 138This could be avoided by extending the interface to allow 64-bit counters. 139