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.
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.
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]
22 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
26 * Copyright (c) 2012 by Delphix. All rights reserved.
29 #include <sys/refcount.h>
30 #include <sys/rrwlock.h>
31 #include <sys/trace_rrwlock.h>
34 * This file contains the implementation of a re-entrant read
35 * reader/writer lock (aka "rrwlock").
37 * This is a normal reader/writer lock with the additional feature
38 * of allowing threads who have already obtained a read lock to
39 * re-enter another read lock (re-entrant read) - even if there are
42 * Callers who have not obtained a read lock give waiting writers priority.
44 * The rrwlock_t lock does not allow re-entrant writers, nor does it
45 * allow a re-entrant mix of reads and writes (that is, it does not
46 * allow a caller who has already obtained a read lock to be able to
47 * then grab a write lock without first dropping all read locks, and
50 * The rrwlock_t uses tsd (thread specific data) to keep a list of
51 * nodes (rrw_node_t), where each node keeps track of which specific
52 * lock (rrw_node_t::rn_rrl) the thread has grabbed. Since re-entering
53 * should be rare, a thread that grabs multiple reads on the same rrwlock_t
54 * will store multiple rrw_node_ts of the same 'rrn_rrl'. Nodes on the
55 * tsd list can represent a different rrwlock_t. This allows a thread
56 * to enter multiple and unique rrwlock_ts for read locks at the same time.
58 * Since using tsd exposes some overhead, the rrwlock_t only needs to
59 * keep tsd data when writers are waiting. If no writers are waiting, then
60 * a reader just bumps the anonymous read count (rr_anon_rcount) - no tsd
61 * is needed. Once a writer attempts to grab the lock, readers then
62 * keep tsd data and bump the linked readers count (rr_linked_rcount).
64 * If there are waiting writers and there are anonymous readers, then a
65 * reader doesn't know if it is a re-entrant lock. But since it may be one,
66 * we allow the read to proceed (otherwise it could deadlock). Since once
67 * waiting writers are active, readers no longer bump the anonymous count,
68 * the anonymous readers will eventually flush themselves out. At this point,
69 * readers will be able to tell if they are a re-entrant lock (have a
70 * rrw_node_t entry for the lock) or not. If they are a re-entrant lock, then
71 * we must let the proceed. If they are not, then the reader blocks for the
72 * waiting writers. Hence, we do not starve writers.
75 /* global key for TSD */
78 typedef struct rrw_node
{
79 struct rrw_node
*rn_next
;
85 rrn_find(rrwlock_t
*rrl
)
89 if (zfs_refcount_count(&rrl
->rr_linked_rcount
) == 0)
92 for (rn
= tsd_get(rrw_tsd_key
); rn
!= NULL
; rn
= rn
->rn_next
) {
93 if (rn
->rn_rrl
== rrl
)
100 * Add a node to the head of the singly linked list.
103 rrn_add(rrwlock_t
*rrl
, void *tag
)
107 rn
= kmem_alloc(sizeof (*rn
), KM_SLEEP
);
109 rn
->rn_next
= tsd_get(rrw_tsd_key
);
111 VERIFY(tsd_set(rrw_tsd_key
, rn
) == 0);
115 * If a node is found for 'rrl', then remove the node from this
116 * thread's list and return TRUE; otherwise return FALSE.
119 rrn_find_and_remove(rrwlock_t
*rrl
, void *tag
)
122 rrw_node_t
*prev
= NULL
;
124 if (zfs_refcount_count(&rrl
->rr_linked_rcount
) == 0)
127 for (rn
= tsd_get(rrw_tsd_key
); rn
!= NULL
; rn
= rn
->rn_next
) {
128 if (rn
->rn_rrl
== rrl
&& rn
->rn_tag
== tag
) {
130 prev
->rn_next
= rn
->rn_next
;
132 VERIFY(tsd_set(rrw_tsd_key
, rn
->rn_next
) == 0);
133 kmem_free(rn
, sizeof (*rn
));
142 rrw_init(rrwlock_t
*rrl
, boolean_t track_all
)
144 mutex_init(&rrl
->rr_lock
, NULL
, MUTEX_DEFAULT
, NULL
);
145 cv_init(&rrl
->rr_cv
, NULL
, CV_DEFAULT
, NULL
);
146 rrl
->rr_writer
= NULL
;
147 zfs_refcount_create(&rrl
->rr_anon_rcount
);
148 zfs_refcount_create(&rrl
->rr_linked_rcount
);
149 rrl
->rr_writer_wanted
= B_FALSE
;
150 rrl
->rr_track_all
= track_all
;
154 rrw_destroy(rrwlock_t
*rrl
)
156 mutex_destroy(&rrl
->rr_lock
);
157 cv_destroy(&rrl
->rr_cv
);
158 ASSERT(rrl
->rr_writer
== NULL
);
159 zfs_refcount_destroy(&rrl
->rr_anon_rcount
);
160 zfs_refcount_destroy(&rrl
->rr_linked_rcount
);
164 rrw_enter_read_impl(rrwlock_t
*rrl
, boolean_t prio
, void *tag
)
166 mutex_enter(&rrl
->rr_lock
);
167 #if !defined(DEBUG) && defined(_KERNEL)
168 if (rrl
->rr_writer
== NULL
&& !rrl
->rr_writer_wanted
&&
169 !rrl
->rr_track_all
) {
170 rrl
->rr_anon_rcount
.rc_count
++;
171 mutex_exit(&rrl
->rr_lock
);
174 DTRACE_PROBE(zfs__rrwfastpath__rdmiss
);
176 ASSERT(rrl
->rr_writer
!= curthread
);
177 ASSERT(zfs_refcount_count(&rrl
->rr_anon_rcount
) >= 0);
179 while (rrl
->rr_writer
!= NULL
|| (rrl
->rr_writer_wanted
&&
180 zfs_refcount_is_zero(&rrl
->rr_anon_rcount
) && !prio
&&
181 rrn_find(rrl
) == NULL
))
182 cv_wait(&rrl
->rr_cv
, &rrl
->rr_lock
);
184 if (rrl
->rr_writer_wanted
|| rrl
->rr_track_all
) {
185 /* may or may not be a re-entrant enter */
187 (void) zfs_refcount_add(&rrl
->rr_linked_rcount
, tag
);
189 (void) zfs_refcount_add(&rrl
->rr_anon_rcount
, tag
);
191 ASSERT(rrl
->rr_writer
== NULL
);
192 mutex_exit(&rrl
->rr_lock
);
196 rrw_enter_read(rrwlock_t
*rrl
, void *tag
)
198 rrw_enter_read_impl(rrl
, B_FALSE
, tag
);
202 * take a read lock even if there are pending write lock requests. if we want
203 * to take a lock reentrantly, but from different threads (that have a
204 * relationship to each other), the normal detection mechanism to overrule
205 * the pending writer does not work, so we have to give an explicit hint here.
208 rrw_enter_read_prio(rrwlock_t
*rrl
, void *tag
)
210 rrw_enter_read_impl(rrl
, B_TRUE
, tag
);
215 rrw_enter_write(rrwlock_t
*rrl
)
217 mutex_enter(&rrl
->rr_lock
);
218 ASSERT(rrl
->rr_writer
!= curthread
);
220 while (zfs_refcount_count(&rrl
->rr_anon_rcount
) > 0 ||
221 zfs_refcount_count(&rrl
->rr_linked_rcount
) > 0 ||
222 rrl
->rr_writer
!= NULL
) {
223 rrl
->rr_writer_wanted
= B_TRUE
;
224 cv_wait(&rrl
->rr_cv
, &rrl
->rr_lock
);
226 rrl
->rr_writer_wanted
= B_FALSE
;
227 rrl
->rr_writer
= curthread
;
228 mutex_exit(&rrl
->rr_lock
);
232 rrw_enter(rrwlock_t
*rrl
, krw_t rw
, void *tag
)
235 rrw_enter_read(rrl
, tag
);
237 rrw_enter_write(rrl
);
241 rrw_exit(rrwlock_t
*rrl
, void *tag
)
243 mutex_enter(&rrl
->rr_lock
);
244 #if !defined(DEBUG) && defined(_KERNEL)
245 if (!rrl
->rr_writer
&& rrl
->rr_linked_rcount
.rc_count
== 0) {
246 rrl
->rr_anon_rcount
.rc_count
--;
247 if (rrl
->rr_anon_rcount
.rc_count
== 0)
248 cv_broadcast(&rrl
->rr_cv
);
249 mutex_exit(&rrl
->rr_lock
);
252 DTRACE_PROBE(zfs__rrwfastpath__exitmiss
);
254 ASSERT(!zfs_refcount_is_zero(&rrl
->rr_anon_rcount
) ||
255 !zfs_refcount_is_zero(&rrl
->rr_linked_rcount
) ||
256 rrl
->rr_writer
!= NULL
);
258 if (rrl
->rr_writer
== NULL
) {
260 if (rrn_find_and_remove(rrl
, tag
)) {
261 count
= zfs_refcount_remove(
262 &rrl
->rr_linked_rcount
, tag
);
264 ASSERT(!rrl
->rr_track_all
);
265 count
= zfs_refcount_remove(&rrl
->rr_anon_rcount
, tag
);
268 cv_broadcast(&rrl
->rr_cv
);
270 ASSERT(rrl
->rr_writer
== curthread
);
271 ASSERT(zfs_refcount_is_zero(&rrl
->rr_anon_rcount
) &&
272 zfs_refcount_is_zero(&rrl
->rr_linked_rcount
));
273 rrl
->rr_writer
= NULL
;
274 cv_broadcast(&rrl
->rr_cv
);
276 mutex_exit(&rrl
->rr_lock
);
280 * If the lock was created with track_all, rrw_held(RW_READER) will return
281 * B_TRUE iff the current thread has the lock for reader. Otherwise it may
282 * return B_TRUE if any thread has the lock for reader.
285 rrw_held(rrwlock_t
*rrl
, krw_t rw
)
289 mutex_enter(&rrl
->rr_lock
);
290 if (rw
== RW_WRITER
) {
291 held
= (rrl
->rr_writer
== curthread
);
293 held
= (!zfs_refcount_is_zero(&rrl
->rr_anon_rcount
) ||
294 rrn_find(rrl
) != NULL
);
296 mutex_exit(&rrl
->rr_lock
);
302 rrw_tsd_destroy(void *arg
)
304 rrw_node_t
*rn
= arg
;
306 panic("thread %p terminating with rrw lock %p held",
307 (void *)curthread
, (void *)rn
->rn_rrl
);
312 * A reader-mostly lock implementation, tuning above reader-writer locks
313 * for hightly parallel read acquisitions, while pessimizing writes.
315 * The idea is to split single busy lock into array of locks, so that
316 * each reader can lock only one of them for read, depending on result
317 * of simple hash function. That proportionally reduces lock congestion.
318 * Writer at the same time has to sequentially acquire write on all the locks.
319 * That makes write acquisition proportionally slower, but in places where
320 * it is used (filesystem unmount) performance is not critical.
322 * All the functions below are direct wrappers around functions above.
325 rrm_init(rrmlock_t
*rrl
, boolean_t track_all
)
329 for (i
= 0; i
< RRM_NUM_LOCKS
; i
++)
330 rrw_init(&rrl
->locks
[i
], track_all
);
334 rrm_destroy(rrmlock_t
*rrl
)
338 for (i
= 0; i
< RRM_NUM_LOCKS
; i
++)
339 rrw_destroy(&rrl
->locks
[i
]);
343 rrm_enter(rrmlock_t
*rrl
, krw_t rw
, void *tag
)
346 rrm_enter_read(rrl
, tag
);
348 rrm_enter_write(rrl
);
352 * This maps the current thread to a specific lock. Note that the lock
353 * must be released by the same thread that acquired it. We do this
354 * mapping by taking the thread pointer mod a prime number. We examine
355 * only the low 32 bits of the thread pointer, because 32-bit division
356 * is faster than 64-bit division, and the high 32 bits have little
359 #define RRM_TD_LOCK() (((uint32_t)(uintptr_t)(curthread)) % RRM_NUM_LOCKS)
362 rrm_enter_read(rrmlock_t
*rrl
, void *tag
)
364 rrw_enter_read(&rrl
->locks
[RRM_TD_LOCK()], tag
);
368 rrm_enter_write(rrmlock_t
*rrl
)
372 for (i
= 0; i
< RRM_NUM_LOCKS
; i
++)
373 rrw_enter_write(&rrl
->locks
[i
]);
377 rrm_exit(rrmlock_t
*rrl
, void *tag
)
381 if (rrl
->locks
[0].rr_writer
== curthread
) {
382 for (i
= 0; i
< RRM_NUM_LOCKS
; i
++)
383 rrw_exit(&rrl
->locks
[i
], tag
);
385 rrw_exit(&rrl
->locks
[RRM_TD_LOCK()], tag
);
390 rrm_held(rrmlock_t
*rrl
, krw_t rw
)
392 if (rw
== RW_WRITER
) {
393 return (rrw_held(&rrl
->locks
[0], rw
));
395 return (rrw_held(&rrl
->locks
[RRM_TD_LOCK()], rw
));