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 101.Pp 102The following example for a reader reads the 103.Va var1 104and 105.Va var2 106variables from the 107.Va obj 108structure. 109In the case where the sequence number was changed it restarts the whole process. 110.Bd -literal 111int var1, var2; 112seqc_t seqc; 113 114for (;;) { 115 seqc = seqc_read(&obj->seqc); 116 var1 = obj->var1; 117 var2 = obj->var2; 118 if (seqc_consistent(&obj->seqc, seqc)) 119 break; 120} 121.Ed 122.Sh AUTHORS 123The 124.Nm seqc 125functions was implemented by 126.An Mateusz Guzik Aq Mt mjg@FreeBSD.org . 127This manual page was written by 128.An Mariusz Zaborski Aq Mt oshogbo@FreeBSD.org . 129.Sh CAVEATS 130There is no guarantee of progress for readers. 131In case when there are a lot of writers the reader can be starved. 132This concern may be solved by returning error after a few attempts. 133.Pp 134Theoretically if reading takes a very long time, and when there are many writers 135the counter may overflow and wrap around to the same value. 136In that case the reader will not notice that the object was changed. 137Given that this needs 4 billion transactional writes across a single contended 138reader, it is unlikely to ever happen. 139This could be avoided by extending the interface to allow 64-bit counters. 140