]>
Commit | Line | Data |
---|---|---|
87d546d8 TG |
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 | void *rn_tag; | |
81 | } rrw_node_t; | |
82 | ||
83 | static rrw_node_t * | |
84 | rrn_find(rrwlock_t *rrl) | |
85 | { | |
86 | rrw_node_t *rn; | |
87 | ||
88 | if (refcount_count(&rrl->rr_linked_rcount) == 0) | |
89 | return (NULL); | |
90 | ||
91 | for (rn = tsd_get(rrw_tsd_key); rn != NULL; rn = rn->rn_next) { | |
92 | if (rn->rn_rrl == rrl) | |
93 | return (rn); | |
94 | } | |
95 | return (NULL); | |
96 | } | |
97 | ||
98 | /* | |
99 | * Add a node to the head of the singly linked list. | |
100 | */ | |
101 | static void | |
102 | rrn_add(rrwlock_t *rrl, void *tag) | |
103 | { | |
104 | rrw_node_t *rn; | |
105 | ||
106 | rn = kmem_alloc(sizeof (*rn), KM_SLEEP); | |
107 | rn->rn_rrl = rrl; | |
108 | rn->rn_next = tsd_get(rrw_tsd_key); | |
109 | rn->rn_tag = tag; | |
110 | VERIFY(tsd_set(rrw_tsd_key, rn) == 0); | |
111 | } | |
112 | ||
113 | /* | |
114 | * If a node is found for 'rrl', then remove the node from this | |
115 | * thread's list and return TRUE; otherwise return FALSE. | |
116 | */ | |
117 | static boolean_t | |
118 | rrn_find_and_remove(rrwlock_t *rrl, void *tag) | |
119 | { | |
120 | rrw_node_t *rn; | |
121 | rrw_node_t *prev = NULL; | |
122 | ||
123 | if (refcount_count(&rrl->rr_linked_rcount) == 0) | |
124 | return (B_FALSE); | |
125 | ||
126 | for (rn = tsd_get(rrw_tsd_key); rn != NULL; rn = rn->rn_next) { | |
127 | if (rn->rn_rrl == rrl && rn->rn_tag == tag) { | |
128 | if (prev) | |
129 | prev->rn_next = rn->rn_next; | |
130 | else | |
131 | VERIFY(tsd_set(rrw_tsd_key, rn->rn_next) == 0); | |
132 | kmem_free(rn, sizeof (*rn)); | |
133 | return (B_TRUE); | |
134 | } | |
135 | prev = rn; | |
136 | } | |
137 | return (B_FALSE); | |
138 | } | |
139 | ||
140 | void | |
141 | rrw_init(rrwlock_t *rrl, boolean_t track_all) | |
142 | { | |
143 | mutex_init(&rrl->rr_lock, NULL, MUTEX_DEFAULT, NULL); | |
144 | cv_init(&rrl->rr_cv, NULL, CV_DEFAULT, NULL); | |
145 | rrl->rr_writer = NULL; | |
146 | refcount_create(&rrl->rr_anon_rcount); | |
147 | refcount_create(&rrl->rr_linked_rcount); | |
148 | rrl->rr_writer_wanted = B_FALSE; | |
149 | rrl->rr_track_all = track_all; | |
150 | } | |
151 | ||
152 | void | |
153 | rrw_destroy(rrwlock_t *rrl) | |
154 | { | |
155 | mutex_destroy(&rrl->rr_lock); | |
156 | cv_destroy(&rrl->rr_cv); | |
157 | ASSERT(rrl->rr_writer == NULL); | |
158 | refcount_destroy(&rrl->rr_anon_rcount); | |
159 | refcount_destroy(&rrl->rr_linked_rcount); | |
160 | } | |
161 | ||
162 | static void | |
163 | rrw_enter_read_impl(rrwlock_t *rrl, boolean_t prio, void *tag) | |
164 | { | |
165 | mutex_enter(&rrl->rr_lock); | |
166 | #if !defined(DEBUG) && defined(_KERNEL) | |
167 | if (rrl->rr_writer == NULL && !rrl->rr_writer_wanted && | |
168 | !rrl->rr_track_all) { | |
169 | rrl->rr_anon_rcount.rc_count++; | |
170 | mutex_exit(&rrl->rr_lock); | |
171 | return; | |
172 | } | |
173 | DTRACE_PROBE(zfs__rrwfastpath__rdmiss); | |
174 | #endif | |
175 | ASSERT(rrl->rr_writer != curthread); | |
176 | ASSERT(refcount_count(&rrl->rr_anon_rcount) >= 0); | |
177 | ||
178 | while (rrl->rr_writer != NULL || (rrl->rr_writer_wanted && | |
179 | refcount_is_zero(&rrl->rr_anon_rcount) && !prio && | |
180 | rrn_find(rrl) == NULL)) | |
181 | cv_wait(&rrl->rr_cv, &rrl->rr_lock); | |
182 | ||
183 | if (rrl->rr_writer_wanted || rrl->rr_track_all) { | |
184 | /* may or may not be a re-entrant enter */ | |
185 | rrn_add(rrl, tag); | |
186 | (void) refcount_add(&rrl->rr_linked_rcount, tag); | |
187 | } else { | |
188 | (void) refcount_add(&rrl->rr_anon_rcount, tag); | |
189 | } | |
190 | ASSERT(rrl->rr_writer == NULL); | |
191 | mutex_exit(&rrl->rr_lock); | |
192 | } | |
193 | ||
194 | void | |
195 | rrw_enter_read(rrwlock_t *rrl, void *tag) | |
196 | { | |
197 | rrw_enter_read_impl(rrl, B_FALSE, tag); | |
198 | } | |
199 | ||
200 | /* | |
201 | * take a read lock even if there are pending write lock requests. if we want | |
202 | * to take a lock reentrantly, but from different threads (that have a | |
203 | * relationship to each other), the normal detection mechanism to overrule | |
204 | * the pending writer does not work, so we have to give an explicit hint here. | |
205 | */ | |
206 | void | |
207 | rrw_enter_read_prio(rrwlock_t *rrl, void *tag) | |
208 | { | |
209 | rrw_enter_read_impl(rrl, B_TRUE, tag); | |
210 | } | |
211 | ||
212 | ||
213 | void | |
214 | rrw_enter_write(rrwlock_t *rrl) | |
215 | { | |
216 | mutex_enter(&rrl->rr_lock); | |
217 | ASSERT(rrl->rr_writer != curthread); | |
218 | ||
219 | while (refcount_count(&rrl->rr_anon_rcount) > 0 || | |
220 | refcount_count(&rrl->rr_linked_rcount) > 0 || | |
221 | rrl->rr_writer != NULL) { | |
222 | rrl->rr_writer_wanted = B_TRUE; | |
223 | cv_wait(&rrl->rr_cv, &rrl->rr_lock); | |
224 | } | |
225 | rrl->rr_writer_wanted = B_FALSE; | |
226 | rrl->rr_writer = curthread; | |
227 | mutex_exit(&rrl->rr_lock); | |
228 | } | |
229 | ||
230 | void | |
231 | rrw_enter(rrwlock_t *rrl, krw_t rw, void *tag) | |
232 | { | |
233 | if (rw == RW_READER) | |
234 | rrw_enter_read(rrl, tag); | |
235 | else | |
236 | rrw_enter_write(rrl); | |
237 | } | |
238 | ||
239 | void | |
240 | rrw_exit(rrwlock_t *rrl, void *tag) | |
241 | { | |
242 | mutex_enter(&rrl->rr_lock); | |
243 | #if !defined(DEBUG) && defined(_KERNEL) | |
244 | if (!rrl->rr_writer && rrl->rr_linked_rcount.rc_count == 0) { | |
245 | rrl->rr_anon_rcount.rc_count--; | |
246 | if (rrl->rr_anon_rcount.rc_count == 0) | |
247 | cv_broadcast(&rrl->rr_cv); | |
248 | mutex_exit(&rrl->rr_lock); | |
249 | return; | |
250 | } | |
251 | DTRACE_PROBE(zfs__rrwfastpath__exitmiss); | |
252 | #endif | |
253 | ASSERT(!refcount_is_zero(&rrl->rr_anon_rcount) || | |
254 | !refcount_is_zero(&rrl->rr_linked_rcount) || | |
255 | rrl->rr_writer != NULL); | |
256 | ||
257 | if (rrl->rr_writer == NULL) { | |
258 | int64_t count; | |
259 | if (rrn_find_and_remove(rrl, tag)) { | |
260 | count = refcount_remove(&rrl->rr_linked_rcount, tag); | |
261 | } else { | |
262 | ASSERT(!rrl->rr_track_all); | |
263 | count = refcount_remove(&rrl->rr_anon_rcount, tag); | |
264 | } | |
265 | if (count == 0) | |
266 | cv_broadcast(&rrl->rr_cv); | |
267 | } else { | |
268 | ASSERT(rrl->rr_writer == curthread); | |
269 | ASSERT(refcount_is_zero(&rrl->rr_anon_rcount) && | |
270 | refcount_is_zero(&rrl->rr_linked_rcount)); | |
271 | rrl->rr_writer = NULL; | |
272 | cv_broadcast(&rrl->rr_cv); | |
273 | } | |
274 | mutex_exit(&rrl->rr_lock); | |
275 | } | |
276 | ||
277 | /* | |
278 | * If the lock was created with track_all, rrw_held(RW_READER) will return | |
279 | * B_TRUE iff the current thread has the lock for reader. Otherwise it may | |
280 | * return B_TRUE if any thread has the lock for reader. | |
281 | */ | |
282 | boolean_t | |
283 | rrw_held(rrwlock_t *rrl, krw_t rw) | |
284 | { | |
285 | boolean_t held; | |
286 | ||
287 | mutex_enter(&rrl->rr_lock); | |
288 | if (rw == RW_WRITER) { | |
289 | held = (rrl->rr_writer == curthread); | |
290 | } else { | |
291 | held = (!refcount_is_zero(&rrl->rr_anon_rcount) || | |
292 | rrn_find(rrl) != NULL); | |
293 | } | |
294 | mutex_exit(&rrl->rr_lock); | |
295 | ||
296 | return (held); | |
297 | } | |
298 | ||
299 | void | |
300 | rrw_tsd_destroy(void *arg) | |
301 | { | |
302 | rrw_node_t *rn = arg; | |
303 | if (rn != NULL) { | |
304 | panic("thread %p terminating with rrw lock %p held", | |
305 | (void *)curthread, (void *)rn->rn_rrl); | |
306 | } | |
307 | } | |
308 | ||
309 | /* | |
310 | * A reader-mostly lock implementation, tuning above reader-writer locks | |
311 | * for hightly parallel read acquisitions, while pessimizing writes. | |
312 | * | |
313 | * The idea is to split single busy lock into array of locks, so that | |
314 | * each reader can lock only one of them for read, depending on result | |
315 | * of simple hash function. That proportionally reduces lock congestion. | |
316 | * Writer same time has to sequentially aquire write on all the locks. | |
317 | * That makes write aquisition proportionally slower, but in places where | |
318 | * it is used (filesystem unmount) performance is not critical. | |
319 | * | |
320 | * All the functions below are direct wrappers around functions above. | |
321 | */ | |
322 | void | |
323 | rrm_init(rrmlock_t *rrl, boolean_t track_all) | |
324 | { | |
325 | int i; | |
326 | ||
327 | for (i = 0; i < RRM_NUM_LOCKS; i++) | |
328 | rrw_init(&rrl->locks[i], track_all); | |
329 | } | |
330 | ||
331 | void | |
332 | rrm_destroy(rrmlock_t *rrl) | |
333 | { | |
334 | int i; | |
335 | ||
336 | for (i = 0; i < RRM_NUM_LOCKS; i++) | |
337 | rrw_destroy(&rrl->locks[i]); | |
338 | } | |
339 | ||
340 | void | |
341 | rrm_enter(rrmlock_t *rrl, krw_t rw, void *tag) | |
342 | { | |
343 | if (rw == RW_READER) | |
344 | rrm_enter_read(rrl, tag); | |
345 | else | |
346 | rrm_enter_write(rrl); | |
347 | } | |
348 | ||
349 | /* | |
350 | * This maps the current thread to a specific lock. Note that the lock | |
351 | * must be released by the same thread that acquired it. We do this | |
352 | * mapping by taking the thread pointer mod a prime number. We examine | |
353 | * only the low 32 bits of the thread pointer, because 32-bit division | |
354 | * is faster than 64-bit division, and the high 32 bits have little | |
355 | * entropy anyway. | |
356 | */ | |
357 | #define RRM_TD_LOCK() (((uint32_t)(uintptr_t)(curthread)) % RRM_NUM_LOCKS) | |
358 | ||
359 | void | |
360 | rrm_enter_read(rrmlock_t *rrl, void *tag) | |
361 | { | |
362 | rrw_enter_read(&rrl->locks[RRM_TD_LOCK()], tag); | |
363 | } | |
364 | ||
365 | void | |
366 | rrm_enter_write(rrmlock_t *rrl) | |
367 | { | |
368 | int i; | |
369 | ||
370 | for (i = 0; i < RRM_NUM_LOCKS; i++) | |
371 | rrw_enter_write(&rrl->locks[i]); | |
372 | } | |
373 | ||
374 | void | |
375 | rrm_exit(rrmlock_t *rrl, void *tag) | |
376 | { | |
377 | int i; | |
378 | ||
379 | if (rrl->locks[0].rr_writer == curthread) { | |
380 | for (i = 0; i < RRM_NUM_LOCKS; i++) | |
381 | rrw_exit(&rrl->locks[i], tag); | |
382 | } else { | |
383 | rrw_exit(&rrl->locks[RRM_TD_LOCK()], tag); | |
384 | } | |
385 | } | |
386 | ||
387 | boolean_t | |
388 | rrm_held(rrmlock_t *rrl, krw_t rw) | |
389 | { | |
390 | if (rw == RW_WRITER) { | |
391 | return (rrw_held(&rrl->locks[0], rw)); | |
392 | } else { | |
393 | return (rrw_held(&rrl->locks[RRM_TD_LOCK()], rw)); | |
394 | } | |
395 | } |