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