sys/cddl/contrib/opensolaris/uts/common/fs/zfs/rrwlock.c

   1 /*
   2  * CDDL HEADER START
   3  *
   4  * The contents of this file are subject to the terms of the
   5  * Common Development and Distribution License (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25 /*
  26  * Copyright (c) 2012 by Delphix. All rights reserved.
  27  */
  28
  29 #include <sys/refcount.h>
  30 #include <sys/rrwlock.h>
  31
  32 /*
  33  * This file contains the implementation of a re-entrant read
  34  * reader/writer lock (aka "rrwlock").
  35  *
  36  * This is a normal reader/writer lock with the additional feature
  37  * of allowing threads who have already obtained a read lock to
  38  * re-enter another read lock (re-entrant read) - even if there are
  39  * waiting writers.
  40  *
  41  * Callers who have not obtained a read lock give waiting writers priority.
  42  *
  43  * The rrwlock_t lock does not allow re-entrant writers, nor does it
  44  * allow a re-entrant mix of reads and writes (that is, it does not
  45  * allow a caller who has already obtained a read lock to be able to
  46  * then grab a write lock without first dropping all read locks, and
  47  * vice versa).
  48  *
  49  * The rrwlock_t uses tsd (thread specific data) to keep a list of
  50  * nodes (rrw_node_t), where each node keeps track of which specific
  51  * lock (rrw_node_t::rn_rrl) the thread has grabbed.  Since re-entering
  52  * should be rare, a thread that grabs multiple reads on the same rrwlock_t
  53  * will store multiple rrw_node_ts of the same 'rrn_rrl'. Nodes on the
  54  * tsd list can represent a different rrwlock_t.  This allows a thread
  55  * to enter multiple and unique rrwlock_ts for read locks at the same time.
  56  *
  57  * Since using tsd exposes some overhead, the rrwlock_t only needs to
  58  * keep tsd data when writers are waiting.  If no writers are waiting, then
  59  * a reader just bumps the anonymous read count (rr_anon_rcount) - no tsd
  60  * is needed.  Once a writer attempts to grab the lock, readers then
  61  * keep tsd data and bump the linked readers count (rr_linked_rcount).
  62  *
  63  * If there are waiting writers and there are anonymous readers, then a
  64  * reader doesn't know if it is a re-entrant lock. But since it may be one,
  65  * we allow the read to proceed (otherwise it could deadlock).  Since once
  66  * waiting writers are active, readers no longer bump the anonymous count,
  67  * the anonymous readers will eventually flush themselves out.  At this point,
  68  * readers will be able to tell if they are a re-entrant lock (have a
  69  * rrw_node_t entry for the lock) or not. If they are a re-entrant lock, then
  70  * we must let the proceed.  If they are not, then the reader blocks for the
  71  * waiting writers.  Hence, we do not starve writers.
  72  */
  73
  74 /* global key for TSD */
  75 uint_t rrw_tsd_key;
  76
  77 typedef struct rrw_node {
  78         struct rrw_node *rn_next;
  79         rrwlock_t       *rn_rrl;
  80 } rrw_node_t;
  81
  82 static rrw_node_t *
  83 rrn_find(rrwlock_t *rrl)
  84 {
  85         rrw_node_t *rn;
  86
  87         if (refcount_count(&rrl->rr_linked_rcount) == 0)
  88                 return (NULL);
  89
  90         for (rn = tsd_get(rrw_tsd_key); rn != NULL; rn = rn->rn_next) {
  91                 if (rn->rn_rrl == rrl)
  92                         return (rn);
  93         }
  94         return (NULL);
  95 }
  96
  97 /*
  98  * Add a node to the head of the singly linked list.
  99  */
 100 static void
 101 rrn_add(rrwlock_t *rrl)
 102 {
 103         rrw_node_t *rn;
 104
 105         rn = kmem_alloc(sizeof (*rn), KM_SLEEP);
 106         rn->rn_rrl = rrl;
 107         rn->rn_next = tsd_get(rrw_tsd_key);
 108         VERIFY(tsd_set(rrw_tsd_key, rn) == 0);
 109 }
 110
 111 /*
 112  * If a node is found for 'rrl', then remove the node from this
 113  * thread's list and return TRUE; otherwise return FALSE.
 114  */
 115 static boolean_t
 116 rrn_find_and_remove(rrwlock_t *rrl)
 117 {
 118         rrw_node_t *rn;
 119         rrw_node_t *prev = NULL;
 120
 121         if (refcount_count(&rrl->rr_linked_rcount) == 0)
 122                 return (B_FALSE);
 123
 124         for (rn = tsd_get(rrw_tsd_key); rn != NULL; rn = rn->rn_next) {
 125                 if (rn->rn_rrl == rrl) {
 126                         if (prev)
 127                                 prev->rn_next = rn->rn_next;
 128                         else
 129                                 VERIFY(tsd_set(rrw_tsd_key, rn->rn_next) == 0);
 130                         kmem_free(rn, sizeof (*rn));
 131                         return (B_TRUE);
 132                 }
 133                 prev = rn;
 134         }
 135         return (B_FALSE);
 136 }
 137
 138 void
 139 rrw_init(rrwlock_t *rrl)
 140 {
 141         mutex_init(&rrl->rr_lock, NULL, MUTEX_DEFAULT, NULL);
 142         cv_init(&rrl->rr_cv, NULL, CV_DEFAULT, NULL);
 143         rrl->rr_writer = NULL;
 144         refcount_create(&rrl->rr_anon_rcount);
 145         refcount_create(&rrl->rr_linked_rcount);
 146         rrl->rr_writer_wanted = B_FALSE;
 147 }
 148
 149 void
 150 rrw_destroy(rrwlock_t *rrl)
 151 {
 152         mutex_destroy(&rrl->rr_lock);
 153         cv_destroy(&rrl->rr_cv);
 154         ASSERT(rrl->rr_writer == NULL);
 155         refcount_destroy(&rrl->rr_anon_rcount);
 156         refcount_destroy(&rrl->rr_linked_rcount);
 157 }
 158
 159 static void
 160 rrw_enter_read(rrwlock_t *rrl, void *tag)
 161 {
 162         mutex_enter(&rrl->rr_lock);
 163 #if !defined(DEBUG) && defined(_KERNEL)
 164         if (!rrl->rr_writer && !rrl->rr_writer_wanted) {
 165                 rrl->rr_anon_rcount.rc_count++;
 166                 mutex_exit(&rrl->rr_lock);
 167                 return;
 168         }
 169         DTRACE_PROBE(zfs__rrwfastpath__rdmiss);
 170 #endif
 171         ASSERT(rrl->rr_writer != curthread);
 172         ASSERT(refcount_count(&rrl->rr_anon_rcount) >= 0);
 173
 174         while (rrl->rr_writer || (rrl->rr_writer_wanted &&
 175             refcount_is_zero(&rrl->rr_anon_rcount) &&
 176             rrn_find(rrl) == NULL))
 177                 cv_wait(&rrl->rr_cv, &rrl->rr_lock);
 178
 179         if (rrl->rr_writer_wanted) {
 180                 /* may or may not be a re-entrant enter */
 181                 rrn_add(rrl);
 182                 (void) refcount_add(&rrl->rr_linked_rcount, tag);
 183         } else {
 184                 (void) refcount_add(&rrl->rr_anon_rcount, tag);
 185         }
 186         ASSERT(rrl->rr_writer == NULL);
 187         mutex_exit(&rrl->rr_lock);
 188 }
 189
 190 static void
 191 rrw_enter_write(rrwlock_t *rrl)
 192 {
 193         mutex_enter(&rrl->rr_lock);
 194         ASSERT(rrl->rr_writer != curthread);
 195
 196         while (refcount_count(&rrl->rr_anon_rcount) > 0 ||
 197             refcount_count(&rrl->rr_linked_rcount) > 0 ||
 198             rrl->rr_writer != NULL) {
 199                 rrl->rr_writer_wanted = B_TRUE;
 200                 cv_wait(&rrl->rr_cv, &rrl->rr_lock);
 201         }
 202         rrl->rr_writer_wanted = B_FALSE;
 203         rrl->rr_writer = curthread;
 204         mutex_exit(&rrl->rr_lock);
 205 }
 206
 207 void
 208 rrw_enter(rrwlock_t *rrl, krw_t rw, void *tag)
 209 {
 210         if (rw == RW_READER)
 211                 rrw_enter_read(rrl, tag);
 212         else
 213                 rrw_enter_write(rrl);
 214 }
 215
 216 void
 217 rrw_exit(rrwlock_t *rrl, void *tag)
 218 {
 219         mutex_enter(&rrl->rr_lock);
 220 #if !defined(DEBUG) && defined(_KERNEL)
 221         if (!rrl->rr_writer && rrl->rr_linked_rcount.rc_count == 0) {
 222                 rrl->rr_anon_rcount.rc_count--;
 223                 if (rrl->rr_anon_rcount.rc_count == 0)
 224                         cv_broadcast(&rrl->rr_cv);
 225                 mutex_exit(&rrl->rr_lock);
 226                 return;
 227         }
 228         DTRACE_PROBE(zfs__rrwfastpath__exitmiss);
 229 #endif
 230         ASSERT(!refcount_is_zero(&rrl->rr_anon_rcount) ||
 231             !refcount_is_zero(&rrl->rr_linked_rcount) ||
 232             rrl->rr_writer != NULL);
 233
 234         if (rrl->rr_writer == NULL) {
 235                 int64_t count;
 236                 if (rrn_find_and_remove(rrl))
 237                         count = refcount_remove(&rrl->rr_linked_rcount, tag);
 238                 else
 239                         count = refcount_remove(&rrl->rr_anon_rcount, tag);
 240                 if (count == 0)
 241                         cv_broadcast(&rrl->rr_cv);
 242         } else {
 243                 ASSERT(rrl->rr_writer == curthread);
 244                 ASSERT(refcount_is_zero(&rrl->rr_anon_rcount) &&
 245                     refcount_is_zero(&rrl->rr_linked_rcount));
 246                 rrl->rr_writer = NULL;
 247                 cv_broadcast(&rrl->rr_cv);
 248         }
 249         mutex_exit(&rrl->rr_lock);
 250 }
 251
 252 boolean_t
 253 rrw_held(rrwlock_t *rrl, krw_t rw)
 254 {
 255         boolean_t held;
 256
 257         mutex_enter(&rrl->rr_lock);
 258         if (rw == RW_WRITER) {
 259                 held = (rrl->rr_writer == curthread);
 260         } else {
 261                 held = (!refcount_is_zero(&rrl->rr_anon_rcount) ||
 262                     !refcount_is_zero(&rrl->rr_linked_rcount));
 263         }
 264         mutex_exit(&rrl->rr_lock);
 265
 266         return (held);
 267 }
 268
 269 void
 270 rrw_tsd_destroy(void *arg)
 271 {
 272         rrw_node_t *rn = arg;
 273         if (rn != NULL) {
 274                 panic("thread %p terminating with rrw lock %p held",
 275                     (void *)curthread, (void *)rn->rn_rrl);
 276         }
 277 }