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