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