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     ovs_mutex_destroy(&rwlock->mutex);
 126 }
 127
 128 static struct fat_rwlock_slot *
 129 fat_rwlock_get_slot__(struct fat_rwlock *rwlock)
 130 {
 131     struct fat_rwlock_slot *slot;
 132     void *base;
 133
 134     /* Fast path. */
 135     slot = ovsthread_getspecific(rwlock->key);
 136     if (slot) {
 137         return slot;
 138     }
 139
 140     /* Slow path: create a new slot for 'rwlock' in this thread. */
 141
 142     /* Allocate room for:
 143      *
 144      *     - Up to CACHE_LINE_SIZE - 1 bytes before the per-thread, so that
 145      *       the start of the slot doesn't potentially share a cache line.
 146      *
 147      *     - The slot itself.
 148      *
 149      *     - Space following the slot up to the end of the cache line, so
 150      *       that the end of the slot doesn't potentially share a cache
 151      *       line. */
 152     base = xmalloc((CACHE_LINE_SIZE - 1)
 153                    + ROUND_UP(sizeof *slot, CACHE_LINE_SIZE));
 154     slot = (void *) ROUND_UP((uintptr_t) base, CACHE_LINE_SIZE);
 155
 156     slot->base = base;
 157     slot->rwlock = rwlock;
 158     ovs_mutex_init(&slot->mutex);
 159     slot->depth = 0;
 160
 161     ovs_mutex_lock(&rwlock->mutex);
 162     list_push_back(&rwlock->threads, &slot->list_node);
 163     ovs_mutex_unlock(&rwlock->mutex);
 164
 165     ovsthread_setspecific(rwlock->key, slot);
 166
 167     return slot;
 168 }
 169
 170 /* Locks 'rwlock' for reading.  The read-lock is recursive: it may be acquired
 171  * any number of times by a single thread (which must then release it the same
 172  * number of times for it to truly be released). */
 173 void
 174 fat_rwlock_rdlock(const struct fat_rwlock *rwlock_)
 175     OVS_ACQ_RDLOCK(rwlock_)
 176     OVS_NO_THREAD_SAFETY_ANALYSIS
 177 {
 178     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 179     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 180
 181     switch (this->depth) {
 182     case UINT_MAX:
 183         /* This thread already holds the write-lock. */
 184         abort();
 185
 186     case 0:
 187         ovs_mutex_lock(&this->mutex);
 188         /* fall through */
 189     default:
 190         this->depth++;
 191         break;
 192     }
 193 }
 194
 195 /* Tries to lock 'rwlock' for reading.  If successful, returns 0.  If taking
 196  * the lock would require blocking, returns EBUSY (without blocking). */
 197 int
 198 fat_rwlock_tryrdlock(const struct fat_rwlock *rwlock_)
 199     OVS_TRY_RDLOCK(0, rwlock_)
 200     OVS_NO_THREAD_SAFETY_ANALYSIS
 201 {
 202     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 203     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 204     int error;
 205
 206     switch (this->depth) {
 207     case UINT_MAX:
 208         return EBUSY;
 209
 210     case 0:
 211         error = ovs_mutex_trylock(&this->mutex);
 212         if (error) {
 213             return error;
 214         }
 215         /* fall through */
 216     default:
 217         this->depth++;
 218         break;
 219     }
 220
 221     return 0;
 222 }
 223
 224 /* Locks 'rwlock' for writing.
 225  *
 226  * The write lock is not recursive. */
 227 void
 228 fat_rwlock_wrlock(const struct fat_rwlock *rwlock_)
 229     OVS_ACQ_WRLOCK(rwlock_)
 230     OVS_NO_THREAD_SAFETY_ANALYSIS
 231 {
 232     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 233     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 234     struct fat_rwlock_slot *slot;
 235
 236     ovs_assert(!this->depth);
 237     this->depth = UINT_MAX;
 238
 239     ovs_mutex_lock(&rwlock->mutex);
 240     LIST_FOR_EACH (slot, list_node, &rwlock->threads) {
 241         ovs_mutex_lock(&slot->mutex);
 242     }
 243 }
 244
 245 /* Unlocks 'rwlock', which the current thread must have locked for reading or
 246  * for writing.  If the read lock has been taken recursively, it must be
 247  * released the same number of times to be truly released. */
 248 void
 249 fat_rwlock_unlock(const struct fat_rwlock *rwlock_)
 250     OVS_RELEASES(rwlock_)
 251     OVS_NO_THREAD_SAFETY_ANALYSIS
 252 {
 253     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 254     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 255     struct fat_rwlock_slot *slot;
 256
 257     switch (this->depth) {
 258     case UINT_MAX:
 259         LIST_FOR_EACH (slot, list_node, &rwlock->threads) {
 260             ovs_mutex_unlock(&slot->mutex);
 261         }
 262         ovs_mutex_unlock(&rwlock->mutex);
 263         this->depth = 0;
 264         break;
 265
 266     case 0:
 267         /* This thread doesn't hold any lock. */
 268         abort();
 269
 270     case 1:
 271         ovs_mutex_unlock(&this->mutex);
 272     default:
 273         this->depth--;
 274         break;
 275     }
 276 }