share/man/man9/seqc.9

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