sys/contrib/ck/include/ck_rwcohort.h

   1 /*
   2  * Copyright 2013-2015 Samy Al Bahra.
   3  * Copyright 2013 Brendon Scheinman.
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER 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
  25  * SUCH DAMAGE.
  26  */
  27
  28 #ifndef CK_RWCOHORT_H
  29 #define CK_RWCOHORT_H
  30
  31 /*
  32  * This is an implementation of NUMA-aware reader-writer locks as described in:
  33  *     Calciu, I.; Dice, D.; Lev, Y.; Luchangco, V.; Marathe, V.; and Shavit, N. 2014.
  34  *     NUMA-Aware Reader-Writer Locks
  35  */
  36
  37 #include <ck_cc.h>
  38 #include <ck_pr.h>
  39 #include <ck_stddef.h>
  40 #include <ck_cohort.h>
  41
  42 #define CK_RWCOHORT_WP_NAME(N) ck_rwcohort_wp_##N
  43 #define CK_RWCOHORT_WP_INSTANCE(N) struct CK_RWCOHORT_WP_NAME(N)
  44 #define CK_RWCOHORT_WP_INIT(N, RW, WL) ck_rwcohort_wp_##N##_init(RW, WL)
  45 #define CK_RWCOHORT_WP_READ_LOCK(N, RW, C, GC, LC)      \
  46         ck_rwcohort_wp_##N##_read_lock(RW, C, GC, LC)
  47 #define CK_RWCOHORT_WP_READ_UNLOCK(N, RW, C, GC, LC)    \
  48         ck_rwcohort_wp_##N##_read_unlock(RW)
  49 #define CK_RWCOHORT_WP_WRITE_LOCK(N, RW, C, GC, LC)     \
  50         ck_rwcohort_wp_##N##_write_lock(RW, C, GC, LC)
  51 #define CK_RWCOHORT_WP_WRITE_UNLOCK(N, RW, C, GC, LC)   \
  52         ck_rwcohort_wp_##N##_write_unlock(RW, C, GC, LC)
  53 #define CK_RWCOHORT_WP_DEFAULT_WAIT_LIMIT 1000
  54
  55 #define CK_RWCOHORT_WP_PROTOTYPE(N)                                                     \
  56         CK_RWCOHORT_WP_INSTANCE(N) {                                                    \
  57                 unsigned int read_counter;                                              \
  58                 unsigned int write_barrier;                                             \
  59                 unsigned int wait_limit;                                                \
  60         };                                                                              \
  61         CK_CC_INLINE static void                                                        \
  62         ck_rwcohort_wp_##N##_init(CK_RWCOHORT_WP_INSTANCE(N) *rw_cohort,                \
  63             unsigned int wait_limit)                                                    \
  64         {                                                                               \
  65                                                                                         \
  66                 rw_cohort->read_counter = 0;                                            \
  67                 rw_cohort->write_barrier = 0;                                           \
  68                 rw_cohort->wait_limit = wait_limit;                                     \
  69                 ck_pr_barrier();                                                        \
  70                 return;                                                                 \
  71         }                                                                               \
  72         CK_CC_INLINE static void                                                        \
  73         ck_rwcohort_wp_##N##_write_lock(CK_RWCOHORT_WP_INSTANCE(N) *rw_cohort,          \
  74             CK_COHORT_INSTANCE(N) *cohort, void *global_context,                        \
  75             void *local_context)                                                        \
  76         {                                                                               \
  77                                                                                         \
  78                 while (ck_pr_load_uint(&rw_cohort->write_barrier) > 0)                  \
  79                         ck_pr_stall();                                                  \
  80                                                                                         \
  81                 CK_COHORT_LOCK(N, cohort, global_context, local_context);               \
  82                                                                                         \
  83                 while (ck_pr_load_uint(&rw_cohort->read_counter) > 0)                   \
  84                         ck_pr_stall();                                                  \
  85                                                                                         \
  86                 return;                                                                 \
  87         }                                                                               \
  88         CK_CC_INLINE static void                                                        \
  89         ck_rwcohort_wp_##N##_write_unlock(CK_RWCOHORT_WP_INSTANCE(N) *rw_cohort,        \
  90             CK_COHORT_INSTANCE(N) *cohort, void *global_context,                        \
  91             void *local_context)                                                        \
  92         {                                                                               \
  93                                                                                         \
  94                 (void)rw_cohort;                                                        \
  95                 CK_COHORT_UNLOCK(N, cohort, global_context, local_context);             \
  96                 return;                                                                 \
  97         }                                                                               \
  98         CK_CC_INLINE static void                                                        \
  99         ck_rwcohort_wp_##N##_read_lock(CK_RWCOHORT_WP_INSTANCE(N) *rw_cohort,           \
 100             CK_COHORT_INSTANCE(N) *cohort, void *global_context,                        \
 101             void *local_context)                                                        \
 102         {                                                                               \
 103                 unsigned int wait_count = 0;                                            \
 104                 bool raised = false;                                                    \
 105                                                                                         \
 106                 for (;;) {                                                              \
 107                         ck_pr_inc_uint(&rw_cohort->read_counter);                       \
 108                         ck_pr_fence_atomic_load();                                      \
 109                         if (CK_COHORT_LOCKED(N, cohort, global_context,                 \
 110                             local_context) == false)                                    \
 111                                 break;                                                  \
 112                                                                                         \
 113                         ck_pr_dec_uint(&rw_cohort->read_counter);                       \
 114                         while (CK_COHORT_LOCKED(N, cohort, global_context,              \
 115                             local_context) == true) {                                   \
 116                                 ck_pr_stall();                                          \
 117                                 if (++wait_count > rw_cohort->wait_limit &&             \
 118                                     raised == false) {                                  \
 119                                         ck_pr_inc_uint(&rw_cohort->write_barrier);      \
 120                                         raised = true;                                  \
 121                                 }                                                       \
 122                         }                                                               \
 123                 }                                                                       \
 124                                                                                         \
 125                 if (raised == true)                                                     \
 126                         ck_pr_dec_uint(&rw_cohort->write_barrier);                      \
 127                                                                                         \
 128                 ck_pr_fence_load();                                                     \
 129                 return;                                                                 \
 130         }                                                                               \
 131         CK_CC_INLINE static void                                                        \
 132         ck_rwcohort_wp_##N##_read_unlock(CK_RWCOHORT_WP_INSTANCE(N) *cohort)            \
 133         {                                                                               \
 134                                                                                         \
 135                 ck_pr_fence_load_atomic();                                              \
 136                 ck_pr_dec_uint(&cohort->read_counter);                                  \
 137                 return;                                                                 \
 138         }
 139
 140 #define CK_RWCOHORT_WP_INITIALIZER {                                                    \
 141         .read_counter = 0,                                                              \
 142         .write_barrier = 0,                                                             \
 143         .wait_limit = 0                                                                 \
 144 }
 145
 146 #define CK_RWCOHORT_RP_NAME(N) ck_rwcohort_rp_##N
 147 #define CK_RWCOHORT_RP_INSTANCE(N) struct CK_RWCOHORT_RP_NAME(N)
 148 #define CK_RWCOHORT_RP_INIT(N, RW, WL) ck_rwcohort_rp_##N##_init(RW, WL)
 149 #define CK_RWCOHORT_RP_READ_LOCK(N, RW, C, GC, LC)      \
 150         ck_rwcohort_rp_##N##_read_lock(RW, C, GC, LC)
 151 #define CK_RWCOHORT_RP_READ_UNLOCK(N, RW, C, GC, LC)    \
 152         ck_rwcohort_rp_##N##_read_unlock(RW)
 153 #define CK_RWCOHORT_RP_WRITE_LOCK(N, RW, C, GC, LC)     \
 154         ck_rwcohort_rp_##N##_write_lock(RW, C, GC, LC)
 155 #define CK_RWCOHORT_RP_WRITE_UNLOCK(N, RW, C, GC, LC)   \
 156         ck_rwcohort_rp_##N##_write_unlock(RW, C, GC, LC)
 157 #define CK_RWCOHORT_RP_DEFAULT_WAIT_LIMIT 1000
 158
 159 #define CK_RWCOHORT_RP_PROTOTYPE(N)                                                     \
 160         CK_RWCOHORT_RP_INSTANCE(N) {                                                    \
 161                 unsigned int read_counter;                                              \
 162                 unsigned int read_barrier;                                              \
 163                 unsigned int wait_limit;                                                \
 164         };                                                                              \
 165         CK_CC_INLINE static void                                                        \
 166         ck_rwcohort_rp_##N##_init(CK_RWCOHORT_RP_INSTANCE(N) *rw_cohort,                \
 167             unsigned int wait_limit)                                                    \
 168         {                                                                               \
 169                                                                                         \
 170                 rw_cohort->read_counter = 0;                                            \
 171                 rw_cohort->read_barrier = 0;                                            \
 172                 rw_cohort->wait_limit = wait_limit;                                     \
 173                 ck_pr_barrier();                                                        \
 174                 return;                                                                 \
 175         }                                                                               \
 176         CK_CC_INLINE static void                                                        \
 177         ck_rwcohort_rp_##N##_write_lock(CK_RWCOHORT_RP_INSTANCE(N) *rw_cohort,          \
 178             CK_COHORT_INSTANCE(N) *cohort, void *global_context,                        \
 179             void *local_context)                                                        \
 180         {                                                                               \
 181                 unsigned int wait_count = 0;                                            \
 182                 bool raised = false;                                                    \
 183                                                                                         \
 184                 for (;;) {                                                              \
 185                         CK_COHORT_LOCK(N, cohort, global_context, local_context);       \
 186                         if (ck_pr_load_uint(&rw_cohort->read_counter) == 0)             \
 187                                 break;                                                  \
 188                                                                                         \
 189                         CK_COHORT_UNLOCK(N, cohort, global_context, local_context);     \
 190                         while (ck_pr_load_uint(&rw_cohort->read_counter) > 0) {         \
 191                                 ck_pr_stall();                                          \
 192                                 if (++wait_count > rw_cohort->wait_limit &&             \
 193                                     raised == false) {                                  \
 194                                         ck_pr_inc_uint(&rw_cohort->read_barrier);       \
 195                                         raised = true;                                  \
 196                                 }                                                       \
 197                         }                                                               \
 198                 }                                                                       \
 199                                                                                         \
 200                 if (raised == true)                                                     \
 201                         ck_pr_dec_uint(&rw_cohort->read_barrier);                       \
 202                                                                                         \
 203                 return;                                                                 \
 204         }                                                                               \
 205         CK_CC_INLINE static void                                                        \
 206         ck_rwcohort_rp_##N##_write_unlock(CK_RWCOHORT_RP_INSTANCE(N) *rw_cohort,        \
 207             CK_COHORT_INSTANCE(N) *cohort, void *global_context, void *local_context)   \
 208         {                                                                               \
 209                                                                                         \
 210                 (void)rw_cohort;                                                        \
 211                 CK_COHORT_UNLOCK(N, cohort, global_context, local_context);             \
 212                 return;                                                                 \
 213         }                                                                               \
 214         CK_CC_INLINE static void                                                        \
 215         ck_rwcohort_rp_##N##_read_lock(CK_RWCOHORT_RP_INSTANCE(N) *rw_cohort,           \
 216             CK_COHORT_INSTANCE(N) *cohort, void *global_context,                        \
 217             void *local_context)                                                        \
 218         {                                                                               \
 219                                                                                         \
 220                 while (ck_pr_load_uint(&rw_cohort->read_barrier) > 0)                   \
 221                         ck_pr_stall();                                                  \
 222                                                                                         \
 223                 ck_pr_inc_uint(&rw_cohort->read_counter);                               \
 224                 ck_pr_fence_atomic_load();                                              \
 225                                                                                         \
 226                 while (CK_COHORT_LOCKED(N, cohort, global_context,                      \
 227                     local_context) == true)                                             \
 228                         ck_pr_stall();                                                  \
 229                                                                                         \
 230                 return;                                                                 \
 231         }                                                                               \
 232         CK_CC_INLINE static void                                                        \
 233         ck_rwcohort_rp_##N##_read_unlock(CK_RWCOHORT_RP_INSTANCE(N) *cohort)            \
 234         {                                                                               \
 235                                                                                         \
 236                 ck_pr_fence_load_atomic();                                              \
 237                 ck_pr_dec_uint(&cohort->read_counter);                                  \
 238                 return;                                                                 \
 239         }
 240
 241 #define CK_RWCOHORT_RP_INITIALIZER {                                                    \
 242         .read_counter = 0,                                                              \
 243         .read_barrier = 0,                                                              \
 244         .wait_limit = 0                                                                 \
 245 }
 246
 247 #define CK_RWCOHORT_NEUTRAL_NAME(N) ck_rwcohort_neutral_##N
 248 #define CK_RWCOHORT_NEUTRAL_INSTANCE(N) struct CK_RWCOHORT_NEUTRAL_NAME(N)
 249 #define CK_RWCOHORT_NEUTRAL_INIT(N, RW) ck_rwcohort_neutral_##N##_init(RW)
 250 #define CK_RWCOHORT_NEUTRAL_READ_LOCK(N, RW, C, GC, LC)         \
 251         ck_rwcohort_neutral_##N##_read_lock(RW, C, GC, LC)
 252 #define CK_RWCOHORT_NEUTRAL_READ_UNLOCK(N, RW, C, GC, LC)       \
 253         ck_rwcohort_neutral_##N##_read_unlock(RW)
 254 #define CK_RWCOHORT_NEUTRAL_WRITE_LOCK(N, RW, C, GC, LC)        \
 255         ck_rwcohort_neutral_##N##_write_lock(RW, C, GC, LC)
 256 #define CK_RWCOHORT_NEUTRAL_WRITE_UNLOCK(N, RW, C, GC, LC)      \
 257         ck_rwcohort_neutral_##N##_write_unlock(RW, C, GC, LC)
 258 #define CK_RWCOHORT_NEUTRAL_DEFAULT_WAIT_LIMIT 1000
 259
 260 #define CK_RWCOHORT_NEUTRAL_PROTOTYPE(N)                                                \
 261         CK_RWCOHORT_NEUTRAL_INSTANCE(N) {                                               \
 262                 unsigned int read_counter;                                              \
 263         };                                                                              \
 264         CK_CC_INLINE static void                                                        \
 265         ck_rwcohort_neutral_##N##_init(CK_RWCOHORT_NEUTRAL_INSTANCE(N) *rw_cohort)      \
 266         {                                                                               \
 267                                                                                         \
 268                 rw_cohort->read_counter = 0;                                            \
 269                 ck_pr_barrier();                                                        \
 270                 return;                                                                 \
 271         }                                                                               \
 272         CK_CC_INLINE static void                                                        \
 273         ck_rwcohort_neutral_##N##_write_lock(CK_RWCOHORT_NEUTRAL_INSTANCE(N) *rw_cohort,\
 274             CK_COHORT_INSTANCE(N) *cohort, void *global_context,                        \
 275             void *local_context)                                                        \
 276         {                                                                               \
 277                                                                                         \
 278                 CK_COHORT_LOCK(N, cohort, global_context, local_context);               \
 279                 while (ck_pr_load_uint(&rw_cohort->read_counter) > 0) {                 \
 280                         ck_pr_stall();                                                  \
 281                 }                                                                       \
 282                 return;                                                                 \
 283         }                                                                               \
 284         CK_CC_INLINE static void                                                        \
 285         ck_rwcohort_neutral_##N##_write_unlock(CK_RWCOHORT_NEUTRAL_INSTANCE(N) *rw_cohort,\
 286             CK_COHORT_INSTANCE(N) *cohort, void *global_context, void *local_context)   \
 287         {                                                                               \
 288                                                                                         \
 289                 (void)rw_cohort;                                                        \
 290                 CK_COHORT_UNLOCK(N, cohort, global_context, local_context);             \
 291                 return;                                                                 \
 292         }                                                                               \
 293         CK_CC_INLINE static void                                                        \
 294         ck_rwcohort_neutral_##N##_read_lock(CK_RWCOHORT_NEUTRAL_INSTANCE(N) *rw_cohort, \
 295             CK_COHORT_INSTANCE(N) *cohort, void *global_context,                        \
 296             void *local_context)                                                        \
 297         {                                                                               \
 298                                                                                         \
 299                 CK_COHORT_LOCK(N, cohort, global_context, local_context);               \
 300                 ck_pr_inc_uint(&rw_cohort->read_counter);                               \
 301                 CK_COHORT_UNLOCK(N, cohort, global_context, local_context);             \
 302                 return;                                                                 \
 303         }                                                                               \
 304         CK_CC_INLINE static void                                                        \
 305         ck_rwcohort_neutral_##N##_read_unlock(CK_RWCOHORT_NEUTRAL_INSTANCE(N) *cohort)  \
 306         {                                                                               \
 307                                                                                         \
 308                 ck_pr_fence_load_atomic();                                              \
 309                 ck_pr_dec_uint(&cohort->read_counter);                                  \
 310                 return;                                                                 \
 311         }
 312
 313 #define CK_RWCOHORT_NEUTRAL_INITIALIZER {                                               \
 314         .read_counter = 0,                                                              \
 315 }
 316
 317 #endif /* CK_RWCOHORT_H */