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 2010 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
26 * Copyright (c) 2012 by Delphix. All rights reserved.
30 * This file contains the code to implement file range locking in
31 * ZFS, although there isn't much specific to ZFS (all that comes to mind is
32 * support for growing the blocksize).
36 * Defined in zfs_rlock.h but essentially:
37 * rl = zfs_range_lock(zp, off, len, lock_type);
38 * zfs_range_unlock(rl);
39 * zfs_range_reduce(rl, off, len);
43 * An AVL tree is used to maintain the state of the existing ranges
44 * that are locked for exclusive (writer) or shared (reader) use.
45 * The starting range offset is used for searching and sorting the tree.
49 * The (hopefully) usual case is of no overlaps or contention for
50 * locks. On entry to zfs_lock_range() a rl_t is allocated; the tree
51 * searched that finds no overlap, and *this* rl_t is placed in the tree.
53 * Overlaps/Reference counting/Proxy locks
54 * ---------------------------------------
55 * The avl code only allows one node at a particular offset. Also it's very
56 * inefficient to search through all previous entries looking for overlaps
57 * (because the very 1st in the ordered list might be at offset 0 but
58 * cover the whole file).
59 * So this implementation uses reference counts and proxy range locks.
60 * Firstly, only reader locks use reference counts and proxy locks,
61 * because writer locks are exclusive.
62 * When a reader lock overlaps with another then a proxy lock is created
63 * for that range and replaces the original lock. If the overlap
64 * is exact then the reference count of the proxy is simply incremented.
65 * Otherwise, the proxy lock is split into smaller lock ranges and
66 * new proxy locks created for non overlapping ranges.
67 * The reference counts are adjusted accordingly.
68 * Meanwhile, the original lock is kept around (this is the callers handle)
69 * and its offset and length are used when releasing the lock.
73 * In order to make wakeups efficient and to ensure multiple continuous
74 * readers on a range don't starve a writer for the same range lock,
75 * two condition variables are allocated in each rl_t.
76 * If a writer (or reader) can't get a range it initialises the writer
77 * (or reader) cv; sets a flag saying there's a writer (or reader) waiting;
78 * and waits on that cv. When a thread unlocks that range it wakes up all
79 * writers then all readers before destroying the lock.
83 * Append mode writes need to lock a range at the end of a file.
84 * The offset of the end of the file is determined under the
85 * range locking mutex, and the lock type converted from RL_APPEND to
86 * RL_WRITER and the range locked.
90 * ZFS supports multiple block sizes currently up to 128K. The smallest
91 * block size is used for the file which is grown as needed. During this
92 * growth all other writers and readers must be excluded.
93 * So if the block size needs to be grown then the whole file is
94 * exclusively locked, then later the caller will reduce the lock
95 * range to just the range to be written using zfs_reduce_range.
98 #include <sys/zfs_rlock.h>
99 #include <sys/sysmacros.h>
102 * Check if a write lock can be grabbed, or wait and recheck until available.
105 zfs_range_lock_writer(zfs_rlock_t *zrl, rl_t *new)
107 avl_tree_t *tree = &zrl->zr_avl;
111 uint64_t off = new->r_off;
112 uint64_t len = new->r_len;
116 * Range locking is also used by zvol. However, for zvol, we
117 * don't need to append or grow blocksize, so skip that
120 * Yes, this is ugly, and would be solved by not handling
121 * grow or append in range lock code. If that was done then
122 * we could make the range locking code generically available
123 * to other non-zfs consumers.
125 if (zrl->zr_size) { /* caller is ZPL */
127 * If in append mode pick up the current end of file.
128 * This is done under z_range_lock to avoid races.
130 if (new->r_type == RL_APPEND)
131 new->r_off = *zrl->zr_size;
134 * If we need to grow the block size then grab the whole
135 * file range. This is also done under z_range_lock to
138 end_size = MAX(*zrl->zr_size, new->r_off + len);
139 if (end_size > *zrl->zr_blksz &&
140 (!ISP2(*zrl->zr_blksz) ||
141 *zrl->zr_blksz < *zrl->zr_max_blksz)) {
143 new->r_len = UINT64_MAX;
148 * First check for the usual case of no locks
150 if (avl_numnodes(tree) == 0) {
151 new->r_type = RL_WRITER; /* convert to writer */
157 * Look for any locks in the range.
159 rl = avl_find(tree, new, &where);
161 goto wait; /* already locked at same offset */
163 rl = (rl_t *)avl_nearest(tree, where, AVL_AFTER);
164 if (rl && (rl->r_off < new->r_off + new->r_len))
167 rl = (rl_t *)avl_nearest(tree, where, AVL_BEFORE);
168 if (rl && rl->r_off + rl->r_len > new->r_off)
171 new->r_type = RL_WRITER; /* convert possible RL_APPEND */
172 avl_insert(tree, new, where);
175 if (!rl->r_write_wanted) {
176 cv_init(&rl->r_wr_cv, NULL, CV_DEFAULT, NULL);
177 rl->r_write_wanted = B_TRUE;
179 cv_wait(&rl->r_wr_cv, &zrl->zr_mutex);
181 /* reset to original */
188 * If this is an original (non-proxy) lock then replace it by
189 * a proxy and return the proxy.
192 zfs_range_proxify(avl_tree_t *tree, rl_t *rl)
197 return (rl); /* already a proxy */
199 ASSERT3U(rl->r_cnt, ==, 1);
200 ASSERT(rl->r_write_wanted == B_FALSE);
201 ASSERT(rl->r_read_wanted == B_FALSE);
202 avl_remove(tree, rl);
205 /* create a proxy range lock */
206 proxy = kmem_alloc(sizeof (rl_t), KM_SLEEP);
207 proxy->r_off = rl->r_off;
208 proxy->r_len = rl->r_len;
210 proxy->r_type = RL_READER;
211 proxy->r_proxy = B_TRUE;
212 proxy->r_write_wanted = B_FALSE;
213 proxy->r_read_wanted = B_FALSE;
214 avl_add(tree, proxy);
220 * Split the range lock at the supplied offset
221 * returning the *front* proxy.
224 zfs_range_split(avl_tree_t *tree, rl_t *rl, uint64_t off)
228 ASSERT3U(rl->r_len, >, 1);
229 ASSERT3U(off, >, rl->r_off);
230 ASSERT3U(off, <, rl->r_off + rl->r_len);
231 ASSERT(rl->r_write_wanted == B_FALSE);
232 ASSERT(rl->r_read_wanted == B_FALSE);
234 /* create the rear proxy range lock */
235 rear = kmem_alloc(sizeof (rl_t), KM_SLEEP);
237 rear->r_len = rl->r_off + rl->r_len - off;
238 rear->r_cnt = rl->r_cnt;
239 rear->r_type = RL_READER;
240 rear->r_proxy = B_TRUE;
241 rear->r_write_wanted = B_FALSE;
242 rear->r_read_wanted = B_FALSE;
244 front = zfs_range_proxify(tree, rl);
245 front->r_len = off - rl->r_off;
247 avl_insert_here(tree, rear, front, AVL_AFTER);
252 * Create and add a new proxy range lock for the supplied range.
255 zfs_range_new_proxy(avl_tree_t *tree, uint64_t off, uint64_t len)
260 rl = kmem_alloc(sizeof (rl_t), KM_SLEEP);
264 rl->r_type = RL_READER;
265 rl->r_proxy = B_TRUE;
266 rl->r_write_wanted = B_FALSE;
267 rl->r_read_wanted = B_FALSE;
272 zfs_range_add_reader(avl_tree_t *tree, rl_t *new, rl_t *prev, avl_index_t where)
275 uint64_t off = new->r_off;
276 uint64_t len = new->r_len;
279 * prev arrives either:
280 * - pointing to an entry at the same offset
281 * - pointing to the entry with the closest previous offset whose
282 * range may overlap with the new range
283 * - null, if there were no ranges starting before the new one
286 if (prev->r_off + prev->r_len <= off) {
288 } else if (prev->r_off != off) {
290 * convert to proxy if needed then
291 * split this entry and bump ref count
293 prev = zfs_range_split(tree, prev, off);
294 prev = AVL_NEXT(tree, prev); /* move to rear range */
297 ASSERT((prev == NULL) || (prev->r_off == off));
302 next = (rl_t *)avl_nearest(tree, where, AVL_AFTER);
304 if (next == NULL || off + len <= next->r_off) {
305 /* no overlaps, use the original new rl_t in the tree */
306 avl_insert(tree, new, where);
310 if (off < next->r_off) {
311 /* Add a proxy for initial range before the overlap */
312 zfs_range_new_proxy(tree, off, next->r_off - off);
315 new->r_cnt = 0; /* will use proxies in tree */
317 * We now search forward through the ranges, until we go past the end
318 * of the new range. For each entry we make it a proxy if it
319 * isn't already, then bump its reference count. If there's any
320 * gaps between the ranges then we create a new proxy range.
322 for (prev = NULL; next; prev = next, next = AVL_NEXT(tree, next)) {
323 if (off + len <= next->r_off)
325 if (prev && prev->r_off + prev->r_len < next->r_off) {
327 ASSERT3U(next->r_off, >, prev->r_off + prev->r_len);
328 zfs_range_new_proxy(tree, prev->r_off + prev->r_len,
329 next->r_off - (prev->r_off + prev->r_len));
331 if (off + len == next->r_off + next->r_len) {
332 /* exact overlap with end */
333 next = zfs_range_proxify(tree, next);
337 if (off + len < next->r_off + next->r_len) {
338 /* new range ends in the middle of this block */
339 next = zfs_range_split(tree, next, off + len);
343 ASSERT3U(off + len, >, next->r_off + next->r_len);
344 next = zfs_range_proxify(tree, next);
348 /* Add the remaining end range. */
349 zfs_range_new_proxy(tree, prev->r_off + prev->r_len,
350 (off + len) - (prev->r_off + prev->r_len));
354 * Check if a reader lock can be grabbed, or wait and recheck until available.
357 zfs_range_lock_reader(zfs_rlock_t *zrl, rl_t *new)
359 avl_tree_t *tree = &zrl->zr_avl;
362 uint64_t off = new->r_off;
363 uint64_t len = new->r_len;
366 * Look for any writer locks in the range.
369 prev = avl_find(tree, new, &where);
371 prev = (rl_t *)avl_nearest(tree, where, AVL_BEFORE);
374 * Check the previous range for a writer lock overlap.
376 if (prev && (off < prev->r_off + prev->r_len)) {
377 if ((prev->r_type == RL_WRITER) || (prev->r_write_wanted)) {
378 if (!prev->r_read_wanted) {
379 cv_init(&prev->r_rd_cv, NULL, CV_DEFAULT, NULL);
380 prev->r_read_wanted = B_TRUE;
382 cv_wait(&prev->r_rd_cv, &zrl->zr_mutex);
385 if (off + len < prev->r_off + prev->r_len)
390 * Search through the following ranges to see if there's
391 * write lock any overlap.
394 next = AVL_NEXT(tree, prev);
396 next = (rl_t *)avl_nearest(tree, where, AVL_AFTER);
397 for (; next; next = AVL_NEXT(tree, next)) {
398 if (off + len <= next->r_off)
400 if ((next->r_type == RL_WRITER) || (next->r_write_wanted)) {
401 if (!next->r_read_wanted) {
402 cv_init(&next->r_rd_cv, NULL, CV_DEFAULT, NULL);
403 next->r_read_wanted = B_TRUE;
405 cv_wait(&next->r_rd_cv, &zrl->zr_mutex);
408 if (off + len <= next->r_off + next->r_len)
414 * Add the read lock, which may involve splitting existing
415 * locks and bumping ref counts (r_cnt).
417 zfs_range_add_reader(tree, new, prev, where);
421 * Lock a range (offset, length) as either shared (RL_READER)
422 * or exclusive (RL_WRITER). Returns the range lock structure
423 * for later unlocking or reduce range (if entire file
424 * previously locked as RL_WRITER).
427 zfs_range_lock(zfs_rlock_t *zrl, uint64_t off, uint64_t len, rl_type_t type)
431 ASSERT(type == RL_READER || type == RL_WRITER || type == RL_APPEND);
433 new = kmem_alloc(sizeof (rl_t), KM_SLEEP);
436 if (len + off < off) /* overflow */
437 len = UINT64_MAX - off;
439 new->r_cnt = 1; /* assume it's going to be in the tree */
441 new->r_proxy = B_FALSE;
442 new->r_write_wanted = B_FALSE;
443 new->r_read_wanted = B_FALSE;
445 mutex_enter(&zrl->zr_mutex);
446 if (type == RL_READER) {
448 * First check for the usual case of no locks
450 if (avl_numnodes(&zrl->zr_avl) == 0)
451 avl_add(&zrl->zr_avl, new);
453 zfs_range_lock_reader(zrl, new);
454 } else /* RL_WRITER or RL_APPEND */
455 zfs_range_lock_writer(zrl, new);
456 mutex_exit(&zrl->zr_mutex);
461 zfs_range_free(void *arg)
465 if (rl->r_write_wanted)
466 cv_destroy(&rl->r_wr_cv);
468 if (rl->r_read_wanted)
469 cv_destroy(&rl->r_rd_cv);
471 kmem_free(rl, sizeof (rl_t));
475 * Unlock a reader lock
478 zfs_range_unlock_reader(zfs_rlock_t *zrl, rl_t *remove, list_t *free_list)
480 avl_tree_t *tree = &zrl->zr_avl;
481 rl_t *rl, *next = NULL;
485 * The common case is when the remove entry is in the tree
486 * (cnt == 1) meaning there's been no other reader locks overlapping
487 * with this one. Otherwise the remove entry will have been
488 * removed from the tree and replaced by proxies (one or
489 * more ranges mapping to the entire range).
491 if (remove->r_cnt == 1) {
492 avl_remove(tree, remove);
494 if (remove->r_write_wanted)
495 cv_broadcast(&remove->r_wr_cv);
497 if (remove->r_read_wanted)
498 cv_broadcast(&remove->r_rd_cv);
500 list_insert_tail(free_list, remove);
502 ASSERT0(remove->r_cnt);
503 ASSERT0(remove->r_write_wanted);
504 ASSERT0(remove->r_read_wanted);
506 * Find start proxy representing this reader lock,
507 * then decrement ref count on all proxies
508 * that make up this range, freeing them as needed.
510 rl = avl_find(tree, remove, NULL);
513 ASSERT(rl->r_type == RL_READER);
514 for (len = remove->r_len; len != 0; rl = next) {
517 next = AVL_NEXT(tree, rl);
519 ASSERT(rl->r_off + rl->r_len == next->r_off);
521 ASSERT(next->r_type == RL_READER);
524 if (rl->r_cnt == 0) {
525 avl_remove(tree, rl);
527 if (rl->r_write_wanted)
528 cv_broadcast(&rl->r_wr_cv);
530 if (rl->r_read_wanted)
531 cv_broadcast(&rl->r_rd_cv);
533 list_insert_tail(free_list, rl);
537 kmem_free(remove, sizeof (rl_t));
542 * Unlock range and destroy range lock structure.
545 zfs_range_unlock(rl_t *rl)
547 zfs_rlock_t *zrl = rl->r_zrl;
551 ASSERT(rl->r_type == RL_WRITER || rl->r_type == RL_READER);
552 ASSERT(rl->r_cnt == 1 || rl->r_cnt == 0);
553 ASSERT(!rl->r_proxy);
554 list_create(&free_list, sizeof (rl_t), offsetof(rl_t, rl_node));
556 mutex_enter(&zrl->zr_mutex);
557 if (rl->r_type == RL_WRITER) {
558 /* writer locks can't be shared or split */
559 avl_remove(&zrl->zr_avl, rl);
560 if (rl->r_write_wanted)
561 cv_broadcast(&rl->r_wr_cv);
563 if (rl->r_read_wanted)
564 cv_broadcast(&rl->r_rd_cv);
566 list_insert_tail(&free_list, rl);
569 * lock may be shared, let zfs_range_unlock_reader()
570 * release the zp->z_range_lock lock and free the rl_t
572 zfs_range_unlock_reader(zrl, rl, &free_list);
574 mutex_exit(&zrl->zr_mutex);
576 while ((free_rl = list_head(&free_list)) != NULL) {
577 list_remove(&free_list, free_rl);
578 zfs_range_free(free_rl);
581 list_destroy(&free_list);
585 * Reduce range locked as RL_WRITER from whole file to specified range.
586 * Asserts the whole file is exclusivly locked and so there's only one
590 zfs_range_reduce(rl_t *rl, uint64_t off, uint64_t len)
592 zfs_rlock_t *zrl = rl->r_zrl;
594 /* Ensure there are no other locks */
595 ASSERT(avl_numnodes(&zrl->zr_avl) == 1);
596 ASSERT(rl->r_off == 0);
597 ASSERT(rl->r_type == RL_WRITER);
598 ASSERT(!rl->r_proxy);
599 ASSERT3U(rl->r_len, ==, UINT64_MAX);
600 ASSERT3U(rl->r_cnt, ==, 1);
602 mutex_enter(&zrl->zr_mutex);
606 if (rl->r_write_wanted)
607 cv_broadcast(&rl->r_wr_cv);
608 if (rl->r_read_wanted)
609 cv_broadcast(&rl->r_rd_cv);
611 mutex_exit(&zrl->zr_mutex);
615 * AVL comparison function used to order range locks
616 * Locks are ordered on the start offset of the range.
619 zfs_range_compare(const void *arg1, const void *arg2)
621 const rl_t *rl1 = (const rl_t *)arg1;
622 const rl_t *rl2 = (const rl_t *)arg2;
624 return (AVL_CMP(rl1->r_off, rl2->r_off));
628 EXPORT_SYMBOL(zfs_range_lock);
629 EXPORT_SYMBOL(zfs_range_unlock);
630 EXPORT_SYMBOL(zfs_range_reduce);
631 EXPORT_SYMBOL(zfs_range_compare);