lib/fat-rwlock.c

   1 /*
   2  * Copyright (c) 2013, 2014 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18
  19 #include "fat-rwlock.h"
  20
  21 #include <errno.h>
  22
  23 #include "hmap.h"
  24 #include "list.h"
  25 #include "ovs-thread.h"
  26 #include "random.h"
  27
  28 /* This system's cache line size, in bytes.
  29  * Being wrong hurts performance but not correctness. */
  30 #define CACHE_LINE_SIZE 64      /* Correct for most CPUs. */
  31 BUILD_ASSERT_DECL(IS_POW2(CACHE_LINE_SIZE));
  32
  33 struct fat_rwlock_slot {
  34     /* Membership in rwlock's list of "struct fat_rwlock_slot"s.
  35      *
  36      * fat_rwlock_destroy() sets 'rwlock' to NULL to indicate that this
  37      * slot may be destroyed. */
  38     struct list list_node;      /* In struct rwlock's 'threads' list. */
  39     struct fat_rwlock *rwlock;  /* Owner. */
  40
  41     /* Mutex.
  42      *
  43      * A thread holding the read-lock holds its own mutex.
  44      *
  45      * A thread holding the write-lock holds every thread's mutex, plus
  46      * 'rwlock->mutex'. */
  47     struct ovs_mutex mutex;
  48
  49     /* This thread's locking status for 'rwlock':
  50      *
  51      *     - 0: This thread does not have any lock on 'rwlock'.  This thread
  52      *       does not have 'mutex' locked.
  53      *
  54      *     - 1: This thread has a read-lock on 'rwlock' and holds 'mutex'.
  55      *
  56      *     - 2...UINT_MAX-1: This thread has recursively taken the read-lock on
  57      *       'rwlock' to the level of 'depth'.  This thread holds 'mutex'.
  58      *
  59      *     - UINT_MAX: This thread has the write-lock on 'rwlock' and holds
  60      *       'mutex' (plus the 'mutex' of all of 'rwlock''s other slots).
  61      *
  62      * Accessed only by the slot's own thread, so no synchronization is
  63      * needed. */
  64     unsigned int depth;
  65
  66     /* To prevent two of these structures from accidentally occupying the same
  67      * cache line (causing "false sharing"), we cache-align each of these data
  68      * structures.  That requires malloc()ing extra space and throwing away
  69      * some space at the beginning, which means that the pointer to this struct
  70      * isn't necessarily the pointer to the beginning of the block, and so we
  71      * need to retain the original pointer to free later.
  72      *
  73      * Accessed only by a single thread, so no synchronization is needed. */
  74     void *base;                /* Pointer to pass to free() for this block.  */
  75 };
  76
  77 static void
  78 free_slot(struct fat_rwlock_slot *slot)
  79 {
  80     if (slot->depth) {
  81         abort();
  82     }
  83
  84     list_remove(&slot->list_node);
  85     free(slot->base);
  86 }
  87
  88 static void
  89 slot_destructor(void *slot_)
  90 {
  91     struct fat_rwlock_slot *slot = slot_;
  92     struct fat_rwlock *rwlock = slot->rwlock;
  93
  94     ovs_mutex_lock(&rwlock->mutex);
  95     free_slot(slot);
  96     ovs_mutex_unlock(&rwlock->mutex);
  97 }
  98
  99 /* Initialize 'rwlock' as a new fat_rwlock. */
 100 void
 101 fat_rwlock_init(struct fat_rwlock *rwlock)
 102 {
 103     ovsthread_key_create(&rwlock->key, slot_destructor);
 104     ovs_mutex_init(&rwlock->mutex);
 105     ovs_mutex_lock(&rwlock->mutex);
 106     list_init(&rwlock->threads);
 107     ovs_mutex_unlock(&rwlock->mutex);
 108 }
 109
 110 /* Destroys 'rwlock', which must not be locked or otherwise in use by any
 111  * thread. */
 112 void
 113 fat_rwlock_destroy(struct fat_rwlock *rwlock)
 114 {
 115     struct fat_rwlock_slot *slot, *next;
 116
 117     /* Order is important here.  By destroying the thread-specific data first,
 118      * before we destroy the slots, we ensure that the thread-specific
 119      * data destructor can't race with our loop below. */
 120     ovsthread_key_delete(rwlock->key);
 121
 122     LIST_FOR_EACH_SAFE (slot, next, list_node, &rwlock->threads) {
 123         free_slot(slot);
 124     }
 125 }
 126
 127 static struct fat_rwlock_slot *
 128 fat_rwlock_get_slot__(struct fat_rwlock *rwlock)
 129 {
 130     struct fat_rwlock_slot *slot;
 131     void *base;
 132
 133     /* Fast path. */
 134     slot = ovsthread_getspecific(rwlock->key);
 135     if (slot) {
 136         return slot;
 137     }
 138
 139     /* Slow path: create a new slot for 'rwlock' in this thread. */
 140
 141     /* Allocate room for:
 142      *
 143      *     - Up to CACHE_LINE_SIZE - 1 bytes before the per-thread, so that
 144      *       the start of the slot doesn't potentially share a cache line.
 145      *
 146      *     - The slot itself.
 147      *
 148      *     - Space following the slot up to the end of the cache line, so
 149      *       that the end of the slot doesn't potentially share a cache
 150      *       line. */
 151     base = xmalloc((CACHE_LINE_SIZE - 1)
 152                    + ROUND_UP(sizeof *slot, CACHE_LINE_SIZE));
 153     slot = (void *) ROUND_UP((uintptr_t) base, CACHE_LINE_SIZE);
 154
 155     slot->base = base;
 156     slot->rwlock = rwlock;
 157     ovs_mutex_init(&slot->mutex);
 158     slot->depth = 0;
 159
 160     ovs_mutex_lock(&rwlock->mutex);
 161     list_push_back(&rwlock->threads, &slot->list_node);
 162     ovs_mutex_unlock(&rwlock->mutex);
 163
 164     ovsthread_setspecific(rwlock->key, slot);
 165
 166     return slot;
 167 }
 168
 169 /* Locks 'rwlock' for reading.  The read-lock is recursive: it may be acquired
 170  * any number of times by a single thread (which must then release it the same
 171  * number of times for it to truly be released). */
 172 void
 173 fat_rwlock_rdlock(const struct fat_rwlock *rwlock_)
 174     OVS_ACQ_RDLOCK(rwlock_)
 175     OVS_NO_THREAD_SAFETY_ANALYSIS
 176 {
 177     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 178     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 179
 180     switch (this->depth) {
 181     case UINT_MAX:
 182         /* This thread already holds the write-lock. */
 183         abort();
 184
 185     case 0:
 186         ovs_mutex_lock(&this->mutex);
 187         /* fall through */
 188     default:
 189         this->depth++;
 190         break;
 191     }
 192 }
 193
 194 /* Tries to lock 'rwlock' for reading.  If successful, returns 0.  If taking
 195  * the lock would require blocking, returns EBUSY (without blocking). */
 196 int
 197 fat_rwlock_tryrdlock(const struct fat_rwlock *rwlock_)
 198     OVS_TRY_RDLOCK(0, rwlock_)
 199     OVS_NO_THREAD_SAFETY_ANALYSIS
 200 {
 201     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 202     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 203     int error;
 204
 205     switch (this->depth) {
 206     case UINT_MAX:
 207         return EBUSY;
 208
 209     case 0:
 210         error = ovs_mutex_trylock(&this->mutex);
 211         if (error) {
 212             return error;
 213         }
 214         /* fall through */
 215     default:
 216         this->depth++;
 217         break;
 218     }
 219
 220     return 0;
 221 }
 222
 223 /* Locks 'rwlock' for writing.
 224  *
 225  * The write lock is not recursive. */
 226 void
 227 fat_rwlock_wrlock(const struct fat_rwlock *rwlock_)
 228     OVS_ACQ_WRLOCK(rwlock_)
 229     OVS_NO_THREAD_SAFETY_ANALYSIS
 230 {
 231     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 232     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 233     struct fat_rwlock_slot *slot;
 234
 235     ovs_assert(!this->depth);
 236     this->depth = UINT_MAX;
 237
 238     ovs_mutex_lock(&rwlock->mutex);
 239     LIST_FOR_EACH (slot, list_node, &rwlock->threads) {
 240         ovs_mutex_lock(&slot->mutex);
 241     }
 242 }
 243
 244 /* Unlocks 'rwlock', which the current thread must have locked for reading or
 245  * for writing.  If the read lock has been taken recursively, it must be
 246  * released the same number of times to be truly released. */
 247 void
 248 fat_rwlock_unlock(const struct fat_rwlock *rwlock_)
 249     OVS_RELEASES(rwlock_)
 250     OVS_NO_THREAD_SAFETY_ANALYSIS
 251 {
 252     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 253     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 254     struct fat_rwlock_slot *slot;
 255
 256     switch (this->depth) {
 257     case UINT_MAX:
 258         LIST_FOR_EACH (slot, list_node, &rwlock->threads) {
 259             ovs_mutex_unlock(&slot->mutex);
 260         }
 261         ovs_mutex_unlock(&rwlock->mutex);
 262         this->depth = 0;
 263         break;
 264
 265     case 0:
 266         /* This thread doesn't hold any lock. */
 267         abort();
 268
 269     case 1:
 270         ovs_mutex_unlock(&this->mutex);
 271     default:
 272         this->depth--;
 273         break;
 274     }
 275 }