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
  62 static void
  63 free_slot(struct fat_rwlock_slot *slot)
  64 {
  65     if (slot->depth) {
  66         abort();
  67     }
  68
  69     list_remove(&slot->list_node);
  70     free_cacheline(slot);
  71 }
  72
  73 static void
  74 slot_destructor(void *slot_)
  75 {
  76     struct fat_rwlock_slot *slot = slot_;
  77     struct fat_rwlock *rwlock = slot->rwlock;
  78
  79     ovs_mutex_lock(&rwlock->mutex);
  80     free_slot(slot);
  81     ovs_mutex_unlock(&rwlock->mutex);
  82 }
  83
  84 /* Initialize 'rwlock' as a new fat_rwlock. */
  85 void
  86 fat_rwlock_init(struct fat_rwlock *rwlock)
  87 {
  88     ovsthread_key_create(&rwlock->key, slot_destructor);
  89     ovs_mutex_init(&rwlock->mutex);
  90     ovs_mutex_lock(&rwlock->mutex);
  91     list_init(&rwlock->threads);
  92     ovs_mutex_unlock(&rwlock->mutex);
  93 }
  94
  95 /* Destroys 'rwlock', which must not be locked or otherwise in use by any
  96  * thread. */
  97 void
  98 fat_rwlock_destroy(struct fat_rwlock *rwlock)
  99 {
 100     struct fat_rwlock_slot *slot, *next;
 101
 102     /* Order is important here.  By destroying the thread-specific data first,
 103      * before we destroy the slots, we ensure that the thread-specific
 104      * data destructor can't race with our loop below. */
 105     ovsthread_key_delete(rwlock->key);
 106
 107     LIST_FOR_EACH_SAFE (slot, next, list_node, &rwlock->threads) {
 108         free_slot(slot);
 109     }
 110     ovs_mutex_destroy(&rwlock->mutex);
 111 }
 112
 113 static struct fat_rwlock_slot *
 114 fat_rwlock_get_slot__(struct fat_rwlock *rwlock)
 115 {
 116     struct fat_rwlock_slot *slot;
 117
 118     /* Fast path. */
 119     slot = ovsthread_getspecific(rwlock->key);
 120     if (slot) {
 121         return slot;
 122     }
 123
 124     /* Slow path: create a new slot for 'rwlock' in this thread. */
 125
 126     slot = xmalloc_cacheline(sizeof *slot);
 127     slot->rwlock = rwlock;
 128     ovs_mutex_init(&slot->mutex);
 129     slot->depth = 0;
 130
 131     ovs_mutex_lock(&rwlock->mutex);
 132     list_push_back(&rwlock->threads, &slot->list_node);
 133     ovs_mutex_unlock(&rwlock->mutex);
 134
 135     ovsthread_setspecific(rwlock->key, slot);
 136
 137     return slot;
 138 }
 139
 140 /* Locks 'rwlock' for reading.  The read-lock is recursive: it may be acquired
 141  * any number of times by a single thread (which must then release it the same
 142  * number of times for it to truly be released). */
 143 void
 144 fat_rwlock_rdlock(const struct fat_rwlock *rwlock_)
 145     OVS_ACQ_RDLOCK(rwlock_)
 146     OVS_NO_THREAD_SAFETY_ANALYSIS
 147 {
 148     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 149     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 150
 151     switch (this->depth) {
 152     case UINT_MAX:
 153         /* This thread already holds the write-lock. */
 154         abort();
 155
 156     case 0:
 157         ovs_mutex_lock(&this->mutex);
 158         /* fall through */
 159     default:
 160         this->depth++;
 161         break;
 162     }
 163 }
 164
 165 /* Tries to lock 'rwlock' for reading.  If successful, returns 0.  If taking
 166  * the lock would require blocking, returns EBUSY (without blocking). */
 167 int
 168 fat_rwlock_tryrdlock(const struct fat_rwlock *rwlock_)
 169     OVS_TRY_RDLOCK(0, rwlock_)
 170     OVS_NO_THREAD_SAFETY_ANALYSIS
 171 {
 172     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 173     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 174     int error;
 175
 176     switch (this->depth) {
 177     case UINT_MAX:
 178         return EBUSY;
 179
 180     case 0:
 181         error = ovs_mutex_trylock(&this->mutex);
 182         if (error) {
 183             return error;
 184         }
 185         /* fall through */
 186     default:
 187         this->depth++;
 188         break;
 189     }
 190
 191     return 0;
 192 }
 193
 194 /* Locks 'rwlock' for writing.
 195  *
 196  * The write lock is not recursive. */
 197 void
 198 fat_rwlock_wrlock(const struct fat_rwlock *rwlock_)
 199     OVS_ACQ_WRLOCK(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     struct fat_rwlock_slot *slot;
 205
 206     ovs_assert(!this->depth);
 207     this->depth = UINT_MAX;
 208
 209     ovs_mutex_lock(&rwlock->mutex);
 210     LIST_FOR_EACH (slot, list_node, &rwlock->threads) {
 211         ovs_mutex_lock(&slot->mutex);
 212     }
 213 }
 214
 215 /* Unlocks 'rwlock', which the current thread must have locked for reading or
 216  * for writing.  If the read lock has been taken recursively, it must be
 217  * released the same number of times to be truly released. */
 218 void
 219 fat_rwlock_unlock(const struct fat_rwlock *rwlock_)
 220     OVS_RELEASES(rwlock_)
 221     OVS_NO_THREAD_SAFETY_ANALYSIS
 222 {
 223     struct fat_rwlock *rwlock = CONST_CAST(struct fat_rwlock *, rwlock_);
 224     struct fat_rwlock_slot *this = fat_rwlock_get_slot__(rwlock);
 225     struct fat_rwlock_slot *slot;
 226
 227     switch (this->depth) {
 228     case UINT_MAX:
 229         LIST_FOR_EACH (slot, list_node, &rwlock->threads) {
 230             ovs_mutex_unlock(&slot->mutex);
 231         }
 232         ovs_mutex_unlock(&rwlock->mutex);
 233         this->depth = 0;
 234         break;
 235
 236     case 0:
 237         /* This thread doesn't hold any lock. */
 238         abort();
 239
 240     case 1:
 241         ovs_mutex_unlock(&this->mutex);
 242     default:
 243         this->depth--;
 244         break;
 245     }
 246 }