sys/contrib/ck/include/ck_sequence.h

   1 /*
   2  * Copyright 2010-2015 Samy Al Bahra.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  */
  26
  27 #ifndef CK_SEQUENCE_H
  28 #define CK_SEQUENCE_H
  29
  30 #include <ck_cc.h>
  31 #include <ck_pr.h>
  32 #include <ck_stdbool.h>
  33
  34 struct ck_sequence {
  35         unsigned int sequence;
  36 };
  37 typedef struct ck_sequence ck_sequence_t;
  38
  39 #define CK_SEQUENCE_INITIALIZER { .sequence = 0 }
  40
  41 CK_CC_INLINE static void
  42 ck_sequence_init(struct ck_sequence *sq)
  43 {
  44
  45         ck_pr_store_uint(&sq->sequence, 0);
  46         return;
  47 }
  48
  49 CK_CC_INLINE static unsigned int
  50 ck_sequence_read_begin(const struct ck_sequence *sq)
  51 {
  52         unsigned int version;
  53
  54         for (;;) {
  55                 version = ck_pr_load_uint(&sq->sequence);
  56
  57                 /*
  58                  * If a sequence is even then associated data may be in a
  59                  * consistent state.
  60                  */
  61                 if (CK_CC_LIKELY((version & 1) == 0))
  62                         break;
  63
  64                 /*
  65                  * If a sequence is odd then a thread is in the middle of an
  66                  * update. Retry the read to avoid operating on inconsistent
  67                  * data.
  68                  */
  69                 ck_pr_stall();
  70         }
  71
  72         ck_pr_fence_load();
  73         return version;
  74 }
  75
  76 CK_CC_INLINE static bool
  77 ck_sequence_read_retry(const struct ck_sequence *sq, unsigned int version)
  78 {
  79
  80         /*
  81          * If the sequence number was updated then a read should be
  82          * re-attempted.
  83          */
  84         ck_pr_fence_load();
  85         return ck_pr_load_uint(&sq->sequence) != version;
  86 }
  87
  88 #define CK_SEQUENCE_READ(seqlock, version)                                              \
  89         for (*(version) = 1;                                                            \
  90             (*(version) != 0) && (*(version) = ck_sequence_read_begin(seqlock), 1);     \
  91             *(version) = ck_sequence_read_retry(seqlock, *(version)))
  92
  93 /*
  94  * This must be called after a successful mutex acquisition.
  95  */
  96 CK_CC_INLINE static void
  97 ck_sequence_write_begin(struct ck_sequence *sq)
  98 {
  99
 100         /*
 101          * Increment the sequence to an odd number to indicate
 102          * the beginning of a write update.
 103          */
 104         ck_pr_store_uint(&sq->sequence, sq->sequence + 1);
 105         ck_pr_fence_store();
 106         return;
 107 }
 108
 109 /*
 110  * This must be called before mutex ownership is relinquished.
 111  */
 112 CK_CC_INLINE static void
 113 ck_sequence_write_end(struct ck_sequence *sq)
 114 {
 115
 116         /*
 117          * Increment the sequence to an even number to indicate
 118          * completion of a write update.
 119          */
 120         ck_pr_fence_store();
 121         ck_pr_store_uint(&sq->sequence, sq->sequence + 1);
 122         return;
 123 }
 124
 125 #endif /* CK_SEQUENCE_H */