xref: /illumos-gate/usr/src/uts/common/fs/zfs/zfs_rlock.c (revision 4d7988d6)
1104e2ed7Sperrin /*
2104e2ed7Sperrin  * CDDL HEADER START
3104e2ed7Sperrin  *
4104e2ed7Sperrin  * The contents of this file are subject to the terms of the
5104e2ed7Sperrin  * Common Development and Distribution License (the "License").
6104e2ed7Sperrin  * You may not use this file except in compliance with the License.
7104e2ed7Sperrin  *
8104e2ed7Sperrin  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9104e2ed7Sperrin  * or http://www.opensolaris.org/os/licensing.
10104e2ed7Sperrin  * See the License for the specific language governing permissions
11104e2ed7Sperrin  * and limitations under the License.
12104e2ed7Sperrin  *
13104e2ed7Sperrin  * When distributing Covered Code, include this CDDL HEADER in each
14104e2ed7Sperrin  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15104e2ed7Sperrin  * If applicable, add the following below this CDDL HEADER, with the
16104e2ed7Sperrin  * fields enclosed by brackets "[]" replaced with your own identifying
17104e2ed7Sperrin  * information: Portions Copyright [yyyy] [name of copyright owner]
18104e2ed7Sperrin  *
19104e2ed7Sperrin  * CDDL HEADER END
20104e2ed7Sperrin  */
21104e2ed7Sperrin /*
220a586ceaSMark Shellenbaum  * Copyright 2010 Sun Microsystems, Inc.  All rights reserved.
23104e2ed7Sperrin  * Use is subject to license terms.
24104e2ed7Sperrin  */
25fb09f5aaSMadhav Suresh /*
2679315247SMatthew Ahrens  * Copyright (c) 2012, 2018 by Delphix. All rights reserved.
27fb09f5aaSMadhav Suresh  */
28104e2ed7Sperrin 
29104e2ed7Sperrin /*
30104e2ed7Sperrin  * This file contains the code to implement file range locking in
31f7170741SWill Andrews  * ZFS, although there isn't much specific to ZFS (all that comes to mind is
32104e2ed7Sperrin  * support for growing the blocksize).
33104e2ed7Sperrin  *
34104e2ed7Sperrin  * Interface
35104e2ed7Sperrin  * ---------
36104e2ed7Sperrin  * Defined in zfs_rlock.h but essentially:
3779315247SMatthew Ahrens  *	lr = rangelock_enter(zp, off, len, lock_type);
3879315247SMatthew Ahrens  *	rangelock_reduce(lr, off, len); // optional
3979315247SMatthew Ahrens  *	rangelock_exit(lr);
40104e2ed7Sperrin  *
41104e2ed7Sperrin  * AVL tree
42104e2ed7Sperrin  * --------
43104e2ed7Sperrin  * An AVL tree is used to maintain the state of the existing ranges
44104e2ed7Sperrin  * that are locked for exclusive (writer) or shared (reader) use.
45104e2ed7Sperrin  * The starting range offset is used for searching and sorting the tree.
46104e2ed7Sperrin  *
47104e2ed7Sperrin  * Common case
48104e2ed7Sperrin  * -----------
4979315247SMatthew Ahrens  * The (hopefully) usual case is of no overlaps or contention for locks. On
5079315247SMatthew Ahrens  * entry to rangelock_enter(), a locked_range_t is allocated; the tree
5179315247SMatthew Ahrens  * searched that finds no overlap, and *this* locked_range_t is placed in the
5279315247SMatthew Ahrens  * tree.
53104e2ed7Sperrin  *
54104e2ed7Sperrin  * Overlaps/Reference counting/Proxy locks
55104e2ed7Sperrin  * ---------------------------------------
56104e2ed7Sperrin  * The avl code only allows one node at a particular offset. Also it's very
57104e2ed7Sperrin  * inefficient to search through all previous entries looking for overlaps
58104e2ed7Sperrin  * (because the very 1st in the ordered list might be at offset 0 but
59104e2ed7Sperrin  * cover the whole file).
60104e2ed7Sperrin  * So this implementation uses reference counts and proxy range locks.
61104e2ed7Sperrin  * Firstly, only reader locks use reference counts and proxy locks,
62104e2ed7Sperrin  * because writer locks are exclusive.
63104e2ed7Sperrin  * When a reader lock overlaps with another then a proxy lock is created
64104e2ed7Sperrin  * for that range and replaces the original lock. If the overlap
65104e2ed7Sperrin  * is exact then the reference count of the proxy is simply incremented.
66104e2ed7Sperrin  * Otherwise, the proxy lock is split into smaller lock ranges and
67104e2ed7Sperrin  * new proxy locks created for non overlapping ranges.
68104e2ed7Sperrin  * The reference counts are adjusted accordingly.
69104e2ed7Sperrin  * Meanwhile, the orginal lock is kept around (this is the callers handle)
70104e2ed7Sperrin  * and its offset and length are used when releasing the lock.
71104e2ed7Sperrin  *
72104e2ed7Sperrin  * Thread coordination
73104e2ed7Sperrin  * -------------------
74104e2ed7Sperrin  * In order to make wakeups efficient and to ensure multiple continuous
75104e2ed7Sperrin  * readers on a range don't starve a writer for the same range lock,
76104e2ed7Sperrin  * two condition variables are allocated in each rl_t.
77104e2ed7Sperrin  * If a writer (or reader) can't get a range it initialises the writer
78104e2ed7Sperrin  * (or reader) cv; sets a flag saying there's a writer (or reader) waiting;
79104e2ed7Sperrin  * and waits on that cv. When a thread unlocks that range it wakes up all
80104e2ed7Sperrin  * writers then all readers before destroying the lock.
81104e2ed7Sperrin  *
82104e2ed7Sperrin  * Append mode writes
83104e2ed7Sperrin  * ------------------
84104e2ed7Sperrin  * Append mode writes need to lock a range at the end of a file.
85104e2ed7Sperrin  * The offset of the end of the file is determined under the
86104e2ed7Sperrin  * range locking mutex, and the lock type converted from RL_APPEND to
87104e2ed7Sperrin  * RL_WRITER and the range locked.
88104e2ed7Sperrin  *
89104e2ed7Sperrin  * Grow block handling
90104e2ed7Sperrin  * -------------------
9179315247SMatthew Ahrens  * ZFS supports multiple block sizes, up to 16MB. The smallest
92104e2ed7Sperrin  * block size is used for the file which is grown as needed. During this
93104e2ed7Sperrin  * growth all other writers and readers must be excluded.
94104e2ed7Sperrin  * So if the block size needs to be grown then the whole file is
95104e2ed7Sperrin  * exclusively locked, then later the caller will reduce the lock
9679315247SMatthew Ahrens  * range to just the range to be written using rangelock_reduce().
97104e2ed7Sperrin  */
98104e2ed7Sperrin 
9979315247SMatthew Ahrens #include <sys/zfs_context.h>
100104e2ed7Sperrin #include <sys/zfs_rlock.h>
101104e2ed7Sperrin 
10279315247SMatthew Ahrens /*
10379315247SMatthew Ahrens  * AVL comparison function used to order range locks
10479315247SMatthew Ahrens  * Locks are ordered on the start offset of the range.
10579315247SMatthew Ahrens  */
10679315247SMatthew Ahrens static int
rangelock_compare(const void * arg1,const void * arg2)10779315247SMatthew Ahrens rangelock_compare(const void *arg1, const void *arg2)
10879315247SMatthew Ahrens {
109c4ab0d3fSGvozden Neskovic 	const locked_range_t *rl1 = (const locked_range_t *)arg1;
110c4ab0d3fSGvozden Neskovic 	const locked_range_t *rl2 = (const locked_range_t *)arg2;
11179315247SMatthew Ahrens 
112*4d7988d6SPaul Dagnelie 	return (TREE_CMP(rl1->lr_offset, rl2->lr_offset));
11379315247SMatthew Ahrens }
11479315247SMatthew Ahrens 
11579315247SMatthew Ahrens /*
11679315247SMatthew Ahrens  * The callback is invoked when acquiring a RL_WRITER or RL_APPEND lock.
11779315247SMatthew Ahrens  * It must convert RL_APPEND to RL_WRITER (starting at the end of the file),
11879315247SMatthew Ahrens  * and may increase the range that's locked for RL_WRITER.
11979315247SMatthew Ahrens  */
12079315247SMatthew Ahrens void
rangelock_init(rangelock_t * rl,rangelock_cb_t * cb,void * arg)12179315247SMatthew Ahrens rangelock_init(rangelock_t *rl, rangelock_cb_t *cb, void *arg)
12279315247SMatthew Ahrens {
12379315247SMatthew Ahrens 	mutex_init(&rl->rl_lock, NULL, MUTEX_DEFAULT, NULL);
12479315247SMatthew Ahrens 	avl_create(&rl->rl_tree, rangelock_compare,
12579315247SMatthew Ahrens 	    sizeof (locked_range_t), offsetof(locked_range_t, lr_node));
12679315247SMatthew Ahrens 	rl->rl_cb = cb;
12779315247SMatthew Ahrens 	rl->rl_arg = arg;
12879315247SMatthew Ahrens }
12979315247SMatthew Ahrens 
13079315247SMatthew Ahrens void
rangelock_fini(rangelock_t * rl)13179315247SMatthew Ahrens rangelock_fini(rangelock_t *rl)
13279315247SMatthew Ahrens {
13379315247SMatthew Ahrens 	mutex_destroy(&rl->rl_lock);
13479315247SMatthew Ahrens 	avl_destroy(&rl->rl_tree);
13579315247SMatthew Ahrens }
13679315247SMatthew Ahrens 
137104e2ed7Sperrin /*
138104e2ed7Sperrin  * Check if a write lock can be grabbed, or wait and recheck until available.
139104e2ed7Sperrin  */
140104e2ed7Sperrin static void
rangelock_enter_writer(rangelock_t * rl,locked_range_t * new)14179315247SMatthew Ahrens rangelock_enter_writer(rangelock_t *rl, locked_range_t *new)
142104e2ed7Sperrin {
14379315247SMatthew Ahrens 	avl_tree_t *tree = &rl->rl_tree;
14479315247SMatthew Ahrens 	locked_range_t *lr;
145104e2ed7Sperrin 	avl_index_t where;
14679315247SMatthew Ahrens 	uint64_t orig_off = new->lr_offset;
14779315247SMatthew Ahrens 	uint64_t orig_len = new->lr_length;
14879315247SMatthew Ahrens 	rangelock_type_t orig_type = new->lr_type;
149104e2ed7Sperrin 
150104e2ed7Sperrin 	for (;;) {
151104e2ed7Sperrin 		/*
15279315247SMatthew Ahrens 		 * Call callback which can modify new->r_off,len,type.
15379315247SMatthew Ahrens 		 * Note, the callback is used by the ZPL to handle appending
15479315247SMatthew Ahrens 		 * and changing blocksizes.  It isn't needed for zvols.
155104e2ed7Sperrin 		 */
15679315247SMatthew Ahrens 		if (rl->rl_cb != NULL) {
15779315247SMatthew Ahrens 			rl->rl_cb(new, rl->rl_arg);
158104e2ed7Sperrin 		}
159104e2ed7Sperrin 
16079315247SMatthew Ahrens 		/*
16179315247SMatthew Ahrens 		 * If the type was APPEND, the callback must convert it to
16279315247SMatthew Ahrens 		 * WRITER.
16379315247SMatthew Ahrens 		 */
16479315247SMatthew Ahrens 		ASSERT3U(new->lr_type, ==, RL_WRITER);
16579315247SMatthew Ahrens 
166104e2ed7Sperrin 		/*
167104e2ed7Sperrin 		 * First check for the usual case of no locks
168104e2ed7Sperrin 		 */
169104e2ed7Sperrin 		if (avl_numnodes(tree) == 0) {
170104e2ed7Sperrin 			avl_add(tree, new);
171104e2ed7Sperrin 			return;
172104e2ed7Sperrin 		}
173104e2ed7Sperrin 
174104e2ed7Sperrin 		/*
175104e2ed7Sperrin 		 * Look for any locks in the range.
176104e2ed7Sperrin 		 */
17779315247SMatthew Ahrens 		lr = avl_find(tree, new, &where);
17879315247SMatthew Ahrens 		if (lr != NULL)
179104e2ed7Sperrin 			goto wait; /* already locked at same offset */
180104e2ed7Sperrin 
18179315247SMatthew Ahrens 		lr = (locked_range_t *)avl_nearest(tree, where, AVL_AFTER);
18279315247SMatthew Ahrens 		if (lr != NULL &&
18379315247SMatthew Ahrens 		    lr->lr_offset < new->lr_offset + new->lr_length)
184104e2ed7Sperrin 			goto wait;
185104e2ed7Sperrin 
18679315247SMatthew Ahrens 		lr = (locked_range_t *)avl_nearest(tree, where, AVL_BEFORE);
18779315247SMatthew Ahrens 		if (lr != NULL &&
18879315247SMatthew Ahrens 		    lr->lr_offset + lr->lr_length > new->lr_offset)
189104e2ed7Sperrin 			goto wait;
190104e2ed7Sperrin 
191104e2ed7Sperrin 		avl_insert(tree, new, where);
192104e2ed7Sperrin 		return;
193104e2ed7Sperrin wait:
19479315247SMatthew Ahrens 		if (!lr->lr_write_wanted) {
19579315247SMatthew Ahrens 			cv_init(&lr->lr_write_cv, NULL, CV_DEFAULT, NULL);
19679315247SMatthew Ahrens 			lr->lr_write_wanted = B_TRUE;
197104e2ed7Sperrin 		}
19879315247SMatthew Ahrens 		cv_wait(&lr->lr_write_cv, &rl->rl_lock);
199104e2ed7Sperrin 
200104e2ed7Sperrin 		/* reset to original */
20179315247SMatthew Ahrens 		new->lr_offset = orig_off;
20279315247SMatthew Ahrens 		new->lr_length = orig_len;
20379315247SMatthew Ahrens 		new->lr_type = orig_type;
204104e2ed7Sperrin 	}
205104e2ed7Sperrin }
206104e2ed7Sperrin 
207104e2ed7Sperrin /*
208104e2ed7Sperrin  * If this is an original (non-proxy) lock then replace it by
209104e2ed7Sperrin  * a proxy and return the proxy.
210104e2ed7Sperrin  */
21179315247SMatthew Ahrens static locked_range_t *
rangelock_proxify(avl_tree_t * tree,locked_range_t * lr)21279315247SMatthew Ahrens rangelock_proxify(avl_tree_t *tree, locked_range_t *lr)
213104e2ed7Sperrin {
21479315247SMatthew Ahrens 	locked_range_t *proxy;
215104e2ed7Sperrin 
21679315247SMatthew Ahrens 	if (lr->lr_proxy)
21779315247SMatthew Ahrens 		return (lr); /* already a proxy */
218104e2ed7Sperrin 
21979315247SMatthew Ahrens 	ASSERT3U(lr->lr_count, ==, 1);
22079315247SMatthew Ahrens 	ASSERT(lr->lr_write_wanted == B_FALSE);
22179315247SMatthew Ahrens 	ASSERT(lr->lr_read_wanted == B_FALSE);
22279315247SMatthew Ahrens 	avl_remove(tree, lr);
22379315247SMatthew Ahrens 	lr->lr_count = 0;
224104e2ed7Sperrin 
225104e2ed7Sperrin 	/* create a proxy range lock */
22679315247SMatthew Ahrens 	proxy = kmem_alloc(sizeof (locked_range_t), KM_SLEEP);
22779315247SMatthew Ahrens 	proxy->lr_offset = lr->lr_offset;
22879315247SMatthew Ahrens 	proxy->lr_length = lr->lr_length;
22979315247SMatthew Ahrens 	proxy->lr_count = 1;
23079315247SMatthew Ahrens 	proxy->lr_type = RL_READER;
23179315247SMatthew Ahrens 	proxy->lr_proxy = B_TRUE;
23279315247SMatthew Ahrens 	proxy->lr_write_wanted = B_FALSE;
23379315247SMatthew Ahrens 	proxy->lr_read_wanted = B_FALSE;
234104e2ed7Sperrin 	avl_add(tree, proxy);
235104e2ed7Sperrin 
236104e2ed7Sperrin 	return (proxy);
237104e2ed7Sperrin }
238104e2ed7Sperrin 
239104e2ed7Sperrin /*
240104e2ed7Sperrin  * Split the range lock at the supplied offset
241104e2ed7Sperrin  * returning the *front* proxy.
242104e2ed7Sperrin  */
24379315247SMatthew Ahrens static locked_range_t *
rangelock_split(avl_tree_t * tree,locked_range_t * lr,uint64_t off)24479315247SMatthew Ahrens rangelock_split(avl_tree_t *tree, locked_range_t *lr, uint64_t off)
245104e2ed7Sperrin {
24679315247SMatthew Ahrens 	ASSERT3U(lr->lr_length, >, 1);
24779315247SMatthew Ahrens 	ASSERT3U(off, >, lr->lr_offset);
24879315247SMatthew Ahrens 	ASSERT3U(off, <, lr->lr_offset + lr->lr_length);
24979315247SMatthew Ahrens 	ASSERT(lr->lr_write_wanted == B_FALSE);
25079315247SMatthew Ahrens 	ASSERT(lr->lr_read_wanted == B_FALSE);
251104e2ed7Sperrin 
252104e2ed7Sperrin 	/* create the rear proxy range lock */
25379315247SMatthew Ahrens 	locked_range_t *rear = kmem_alloc(sizeof (locked_range_t), KM_SLEEP);
25479315247SMatthew Ahrens 	rear->lr_offset = off;
25579315247SMatthew Ahrens 	rear->lr_length = lr->lr_offset + lr->lr_length - off;
25679315247SMatthew Ahrens 	rear->lr_count = lr->lr_count;
25779315247SMatthew Ahrens 	rear->lr_type = RL_READER;
25879315247SMatthew Ahrens 	rear->lr_proxy = B_TRUE;
25979315247SMatthew Ahrens 	rear->lr_write_wanted = B_FALSE;
26079315247SMatthew Ahrens 	rear->lr_read_wanted = B_FALSE;
26179315247SMatthew Ahrens 
26279315247SMatthew Ahrens 	locked_range_t *front = rangelock_proxify(tree, lr);
26379315247SMatthew Ahrens 	front->lr_length = off - lr->lr_offset;
264104e2ed7Sperrin 
265104e2ed7Sperrin 	avl_insert_here(tree, rear, front, AVL_AFTER);
266104e2ed7Sperrin 	return (front);
267104e2ed7Sperrin }
268104e2ed7Sperrin 
269104e2ed7Sperrin /*
270104e2ed7Sperrin  * Create and add a new proxy range lock for the supplied range.
271104e2ed7Sperrin  */
272104e2ed7Sperrin static void
rangelock_new_proxy(avl_tree_t * tree,uint64_t off,uint64_t len)27379315247SMatthew Ahrens rangelock_new_proxy(avl_tree_t *tree, uint64_t off, uint64_t len)
274104e2ed7Sperrin {
27579315247SMatthew Ahrens 	ASSERT(len != 0);
27679315247SMatthew Ahrens 	locked_range_t *lr = kmem_alloc(sizeof (locked_range_t), KM_SLEEP);
27779315247SMatthew Ahrens 	lr->lr_offset = off;
27879315247SMatthew Ahrens 	lr->lr_length = len;
27979315247SMatthew Ahrens 	lr->lr_count = 1;
28079315247SMatthew Ahrens 	lr->lr_type = RL_READER;
28179315247SMatthew Ahrens 	lr->lr_proxy = B_TRUE;
28279315247SMatthew Ahrens 	lr->lr_write_wanted = B_FALSE;
28379315247SMatthew Ahrens 	lr->lr_read_wanted = B_FALSE;
28479315247SMatthew Ahrens 	avl_add(tree, lr);
285104e2ed7Sperrin }
286104e2ed7Sperrin 
287104e2ed7Sperrin static void
rangelock_add_reader(avl_tree_t * tree,locked_range_t * new,locked_range_t * prev,avl_index_t where)28879315247SMatthew Ahrens rangelock_add_reader(avl_tree_t *tree, locked_range_t *new,
28979315247SMatthew Ahrens     locked_range_t *prev, avl_index_t where)
290104e2ed7Sperrin {
29179315247SMatthew Ahrens 	locked_range_t *next;
29279315247SMatthew Ahrens 	uint64_t off = new->lr_offset;
29379315247SMatthew Ahrens 	uint64_t len = new->lr_length;
294104e2ed7Sperrin 
295104e2ed7Sperrin 	/*
296104e2ed7Sperrin 	 * prev arrives either:
297104e2ed7Sperrin 	 * - pointing to an entry at the same offset
298104e2ed7Sperrin 	 * - pointing to the entry with the closest previous offset whose
299104e2ed7Sperrin 	 *   range may overlap with the new range
300104e2ed7Sperrin 	 * - null, if there were no ranges starting before the new one
301104e2ed7Sperrin 	 */
30279315247SMatthew Ahrens 	if (prev != NULL) {
30379315247SMatthew Ahrens 		if (prev->lr_offset + prev->lr_length <= off) {
304104e2ed7Sperrin 			prev = NULL;
30579315247SMatthew Ahrens 		} else if (prev->lr_offset != off) {
306104e2ed7Sperrin 			/*
307104e2ed7Sperrin 			 * convert to proxy if needed then
308104e2ed7Sperrin 			 * split this entry and bump ref count
309104e2ed7Sperrin 			 */
31079315247SMatthew Ahrens 			prev = rangelock_split(tree, prev, off);
311104e2ed7Sperrin 			prev = AVL_NEXT(tree, prev); /* move to rear range */
312104e2ed7Sperrin 		}
313104e2ed7Sperrin 	}
31479315247SMatthew Ahrens 	ASSERT((prev == NULL) || (prev->lr_offset == off));
315104e2ed7Sperrin 
31679315247SMatthew Ahrens 	if (prev != NULL)
317104e2ed7Sperrin 		next = prev;
318104e2ed7Sperrin 	else
31979315247SMatthew Ahrens 		next = avl_nearest(tree, where, AVL_AFTER);
320104e2ed7Sperrin 
32179315247SMatthew Ahrens 	if (next == NULL || off + len <= next->lr_offset) {
322104e2ed7Sperrin 		/* no overlaps, use the original new rl_t in the tree */
323104e2ed7Sperrin 		avl_insert(tree, new, where);
324104e2ed7Sperrin 		return;
325104e2ed7Sperrin 	}
326104e2ed7Sperrin 
32779315247SMatthew Ahrens 	if (off < next->lr_offset) {
328104e2ed7Sperrin 		/* Add a proxy for initial range before the overlap */
32979315247SMatthew Ahrens 		rangelock_new_proxy(tree, off, next->lr_offset - off);
330104e2ed7Sperrin 	}
331104e2ed7Sperrin 
33279315247SMatthew Ahrens 	new->lr_count = 0; /* will use proxies in tree */
333104e2ed7Sperrin 	/*
334104e2ed7Sperrin 	 * We now search forward through the ranges, until we go past the end
335104e2ed7Sperrin 	 * of the new range. For each entry we make it a proxy if it
336104e2ed7Sperrin 	 * isn't already, then bump its reference count. If there's any
337104e2ed7Sperrin 	 * gaps between the ranges then we create a new proxy range.
338104e2ed7Sperrin 	 */
339104e2ed7Sperrin 	for (prev = NULL; next; prev = next, next = AVL_NEXT(tree, next)) {
34079315247SMatthew Ahrens 		if (off + len <= next->lr_offset)
341104e2ed7Sperrin 			break;
34279315247SMatthew Ahrens 		if (prev != NULL && prev->lr_offset + prev->lr_length <
34379315247SMatthew Ahrens 		    next->lr_offset) {
344104e2ed7Sperrin 			/* there's a gap */
34579315247SMatthew Ahrens 			ASSERT3U(next->lr_offset, >,
34679315247SMatthew Ahrens 			    prev->lr_offset + prev->lr_length);
34779315247SMatthew Ahrens 			rangelock_new_proxy(tree,
34879315247SMatthew Ahrens 			    prev->lr_offset + prev->lr_length,
34979315247SMatthew Ahrens 			    next->lr_offset -
35079315247SMatthew Ahrens 			    (prev->lr_offset + prev->lr_length));
351104e2ed7Sperrin 		}
35279315247SMatthew Ahrens 		if (off + len == next->lr_offset + next->lr_length) {
353104e2ed7Sperrin 			/* exact overlap with end */
35479315247SMatthew Ahrens 			next = rangelock_proxify(tree, next);
35579315247SMatthew Ahrens 			next->lr_count++;
356104e2ed7Sperrin 			return;
357104e2ed7Sperrin 		}
35879315247SMatthew Ahrens 		if (off + len < next->lr_offset + next->lr_length) {
359104e2ed7Sperrin 			/* new range ends in the middle of this block */
36079315247SMatthew Ahrens 			next = rangelock_split(tree, next, off + len);
36179315247SMatthew Ahrens 			next->lr_count++;
362104e2ed7Sperrin 			return;
363104e2ed7Sperrin 		}
36479315247SMatthew Ahrens 		ASSERT3U(off + len, >, next->lr_offset + next->lr_length);
36579315247SMatthew Ahrens 		next = rangelock_proxify(tree, next);
36679315247SMatthew Ahrens 		next->lr_count++;
367104e2ed7Sperrin 	}
368104e2ed7Sperrin 
369104e2ed7Sperrin 	/* Add the remaining end range. */
37079315247SMatthew Ahrens 	rangelock_new_proxy(tree, prev->lr_offset + prev->lr_length,
37179315247SMatthew Ahrens 	    (off + len) - (prev->lr_offset + prev->lr_length));
372104e2ed7Sperrin }
373104e2ed7Sperrin 
374104e2ed7Sperrin /*
375104e2ed7Sperrin  * Check if a reader lock can be grabbed, or wait and recheck until available.
376104e2ed7Sperrin  */
377104e2ed7Sperrin static void
rangelock_enter_reader(rangelock_t * rl,locked_range_t * new)37879315247SMatthew Ahrens rangelock_enter_reader(rangelock_t *rl, locked_range_t *new)
379104e2ed7Sperrin {
38079315247SMatthew Ahrens 	avl_tree_t *tree = &rl->rl_tree;
38179315247SMatthew Ahrens 	locked_range_t *prev, *next;
382104e2ed7Sperrin 	avl_index_t where;
38379315247SMatthew Ahrens 	uint64_t off = new->lr_offset;
38479315247SMatthew Ahrens 	uint64_t len = new->lr_length;
385104e2ed7Sperrin 
386104e2ed7Sperrin 	/*
387104e2ed7Sperrin 	 * Look for any writer locks in the range.
388104e2ed7Sperrin 	 */
389104e2ed7Sperrin retry:
390104e2ed7Sperrin 	prev = avl_find(tree, new, &where);
391104e2ed7Sperrin 	if (prev == NULL)
39279315247SMatthew Ahrens 		prev = (locked_range_t *)avl_nearest(tree, where, AVL_BEFORE);
393104e2ed7Sperrin 
394104e2ed7Sperrin 	/*
395104e2ed7Sperrin 	 * Check the previous range for a writer lock overlap.
396104e2ed7Sperrin 	 */
39779315247SMatthew Ahrens 	if (prev && (off < prev->lr_offset + prev->lr_length)) {
39879315247SMatthew Ahrens 		if ((prev->lr_type == RL_WRITER) || (prev->lr_write_wanted)) {
39979315247SMatthew Ahrens 			if (!prev->lr_read_wanted) {
40079315247SMatthew Ahrens 				cv_init(&prev->lr_read_cv,
40179315247SMatthew Ahrens 				    NULL, CV_DEFAULT, NULL);
40279315247SMatthew Ahrens 				prev->lr_read_wanted = B_TRUE;
403104e2ed7Sperrin 			}
40479315247SMatthew Ahrens 			cv_wait(&prev->lr_read_cv, &rl->rl_lock);
405104e2ed7Sperrin 			goto retry;
406104e2ed7Sperrin 		}
40779315247SMatthew Ahrens 		if (off + len < prev->lr_offset + prev->lr_length)
408104e2ed7Sperrin 			goto got_lock;
409104e2ed7Sperrin 	}
410104e2ed7Sperrin 
411104e2ed7Sperrin 	/*
412104e2ed7Sperrin 	 * Search through the following ranges to see if there's
413104e2ed7Sperrin 	 * write lock any overlap.
414104e2ed7Sperrin 	 */
41579315247SMatthew Ahrens 	if (prev != NULL)
416104e2ed7Sperrin 		next = AVL_NEXT(tree, prev);
417104e2ed7Sperrin 	else
41879315247SMatthew Ahrens 		next = (locked_range_t *)avl_nearest(tree, where, AVL_AFTER);
41979315247SMatthew Ahrens 	for (; next != NULL; next = AVL_NEXT(tree, next)) {
42079315247SMatthew Ahrens 		if (off + len <= next->lr_offset)
421104e2ed7Sperrin 			goto got_lock;
42279315247SMatthew Ahrens 		if ((next->lr_type == RL_WRITER) || (next->lr_write_wanted)) {
42379315247SMatthew Ahrens 			if (!next->lr_read_wanted) {
42479315247SMatthew Ahrens 				cv_init(&next->lr_read_cv,
42579315247SMatthew Ahrens 				    NULL, CV_DEFAULT, NULL);
42679315247SMatthew Ahrens 				next->lr_read_wanted = B_TRUE;
427104e2ed7Sperrin 			}
42879315247SMatthew Ahrens 			cv_wait(&next->lr_read_cv, &rl->rl_lock);
429104e2ed7Sperrin 			goto retry;
430104e2ed7Sperrin 		}
43179315247SMatthew Ahrens 		if (off + len <= next->lr_offset + next->lr_length)
432104e2ed7Sperrin 			goto got_lock;
433104e2ed7Sperrin 	}
434104e2ed7Sperrin 
435104e2ed7Sperrin got_lock:
436104e2ed7Sperrin 	/*
437104e2ed7Sperrin 	 * Add the read lock, which may involve splitting existing
43879315247SMatthew Ahrens 	 * locks and bumping ref counts (r_count).
439104e2ed7Sperrin 	 */
44079315247SMatthew Ahrens 	rangelock_add_reader(tree, new, prev, where);
441104e2ed7Sperrin }
442104e2ed7Sperrin 
443104e2ed7Sperrin /*
44479315247SMatthew Ahrens  * Lock a range (offset, length) as either shared (RL_READER) or exclusive
44579315247SMatthew Ahrens  * (RL_WRITER or RL_APPEND).  If RL_APPEND is specified, rl_cb() will convert
44679315247SMatthew Ahrens  * it to a RL_WRITER lock (with the offset at the end of the file).  Returns
44779315247SMatthew Ahrens  * the range lock structure for later unlocking (or reduce range if the
44879315247SMatthew Ahrens  * entire file is locked as RL_WRITER).
449104e2ed7Sperrin  */
45079315247SMatthew Ahrens locked_range_t *
rangelock_enter(rangelock_t * rl,uint64_t off,uint64_t len,rangelock_type_t type)45179315247SMatthew Ahrens rangelock_enter(rangelock_t *rl, uint64_t off, uint64_t len,
45279315247SMatthew Ahrens     rangelock_type_t type)
453104e2ed7Sperrin {
454104e2ed7Sperrin 	ASSERT(type == RL_READER || type == RL_WRITER || type == RL_APPEND);
455104e2ed7Sperrin 
45679315247SMatthew Ahrens 	locked_range_t *new = kmem_alloc(sizeof (locked_range_t), KM_SLEEP);
45779315247SMatthew Ahrens 	new->lr_rangelock = rl;
45879315247SMatthew Ahrens 	new->lr_offset = off;
459ac05c741SMark Maybee 	if (len + off < off)	/* overflow */
460ac05c741SMark Maybee 		len = UINT64_MAX - off;
46179315247SMatthew Ahrens 	new->lr_length = len;
46279315247SMatthew Ahrens 	new->lr_count = 1; /* assume it's going to be in the tree */
46379315247SMatthew Ahrens 	new->lr_type = type;
46479315247SMatthew Ahrens 	new->lr_proxy = B_FALSE;
46579315247SMatthew Ahrens 	new->lr_write_wanted = B_FALSE;
46679315247SMatthew Ahrens 	new->lr_read_wanted = B_FALSE;
46779315247SMatthew Ahrens 
46879315247SMatthew Ahrens 	mutex_enter(&rl->rl_lock);
469104e2ed7Sperrin 	if (type == RL_READER) {
470104e2ed7Sperrin 		/*
471104e2ed7Sperrin 		 * First check for the usual case of no locks
472104e2ed7Sperrin 		 */
47379315247SMatthew Ahrens 		if (avl_numnodes(&rl->rl_tree) == 0)
47479315247SMatthew Ahrens 			avl_add(&rl->rl_tree, new);
475104e2ed7Sperrin 		else
47679315247SMatthew Ahrens 			rangelock_enter_reader(rl, new);
477104e2ed7Sperrin 	} else
47879315247SMatthew Ahrens 		rangelock_enter_writer(rl, new); /* RL_WRITER or RL_APPEND */
47979315247SMatthew Ahrens 	mutex_exit(&rl->rl_lock);
480104e2ed7Sperrin 	return (new);
481104e2ed7Sperrin }
482104e2ed7Sperrin 
483104e2ed7Sperrin /*
484104e2ed7Sperrin  * Unlock a reader lock
485104e2ed7Sperrin  */
486104e2ed7Sperrin static void
rangelock_exit_reader(rangelock_t * rl,locked_range_t * remove)48779315247SMatthew Ahrens rangelock_exit_reader(rangelock_t *rl, locked_range_t *remove)
488104e2ed7Sperrin {
48979315247SMatthew Ahrens 	avl_tree_t *tree = &rl->rl_tree;
490104e2ed7Sperrin 	uint64_t len;
491104e2ed7Sperrin 
492104e2ed7Sperrin 	/*
493104e2ed7Sperrin 	 * The common case is when the remove entry is in the tree
494104e2ed7Sperrin 	 * (cnt == 1) meaning there's been no other reader locks overlapping
495104e2ed7Sperrin 	 * with this one. Otherwise the remove entry will have been
496104e2ed7Sperrin 	 * removed from the tree and replaced by proxies (one or
497104e2ed7Sperrin 	 * more ranges mapping to the entire range).
498104e2ed7Sperrin 	 */
49979315247SMatthew Ahrens 	if (remove->lr_count == 1) {
500104e2ed7Sperrin 		avl_remove(tree, remove);
50179315247SMatthew Ahrens 		if (remove->lr_write_wanted) {
50279315247SMatthew Ahrens 			cv_broadcast(&remove->lr_write_cv);
50379315247SMatthew Ahrens 			cv_destroy(&remove->lr_write_cv);
504c25056deSgw 		}
50579315247SMatthew Ahrens 		if (remove->lr_read_wanted) {
50679315247SMatthew Ahrens 			cv_broadcast(&remove->lr_read_cv);
50779315247SMatthew Ahrens 			cv_destroy(&remove->lr_read_cv);
508c25056deSgw 		}
509104e2ed7Sperrin 	} else {
51079315247SMatthew Ahrens 		ASSERT0(remove->lr_count);
51179315247SMatthew Ahrens 		ASSERT0(remove->lr_write_wanted);
51279315247SMatthew Ahrens 		ASSERT0(remove->lr_read_wanted);
513104e2ed7Sperrin 		/*
514104e2ed7Sperrin 		 * Find start proxy representing this reader lock,
515104e2ed7Sperrin 		 * then decrement ref count on all proxies
516104e2ed7Sperrin 		 * that make up this range, freeing them as needed.
517104e2ed7Sperrin 		 */
51879315247SMatthew Ahrens 		locked_range_t *lr = avl_find(tree, remove, NULL);
51979315247SMatthew Ahrens 		ASSERT3P(lr, !=, NULL);
52079315247SMatthew Ahrens 		ASSERT3U(lr->lr_count, !=, 0);
52179315247SMatthew Ahrens 		ASSERT3U(lr->lr_type, ==, RL_READER);
52279315247SMatthew Ahrens 		locked_range_t *next = NULL;
52379315247SMatthew Ahrens 		for (len = remove->lr_length; len != 0; lr = next) {
52479315247SMatthew Ahrens 			len -= lr->lr_length;
52579315247SMatthew Ahrens 			if (len != 0) {
52679315247SMatthew Ahrens 				next = AVL_NEXT(tree, lr);
52779315247SMatthew Ahrens 				ASSERT3P(next, !=, NULL);
52879315247SMatthew Ahrens 				ASSERT3U(lr->lr_offset + lr->lr_length, ==,
52979315247SMatthew Ahrens 				    next->lr_offset);
53079315247SMatthew Ahrens 				ASSERT3U(next->lr_count, !=, 0);
53179315247SMatthew Ahrens 				ASSERT3U(next->lr_type, ==, RL_READER);
532104e2ed7Sperrin 			}
53379315247SMatthew Ahrens 			lr->lr_count--;
53479315247SMatthew Ahrens 			if (lr->lr_count == 0) {
53579315247SMatthew Ahrens 				avl_remove(tree, lr);
53679315247SMatthew Ahrens 				if (lr->lr_write_wanted) {
53779315247SMatthew Ahrens 					cv_broadcast(&lr->lr_write_cv);
53879315247SMatthew Ahrens 					cv_destroy(&lr->lr_write_cv);
539c25056deSgw 				}
54079315247SMatthew Ahrens 				if (lr->lr_read_wanted) {
54179315247SMatthew Ahrens 					cv_broadcast(&lr->lr_read_cv);
54279315247SMatthew Ahrens 					cv_destroy(&lr->lr_read_cv);
543c25056deSgw 				}
54479315247SMatthew Ahrens 				kmem_free(lr, sizeof (locked_range_t));
545104e2ed7Sperrin 			}
546104e2ed7Sperrin 		}
547104e2ed7Sperrin 	}
54879315247SMatthew Ahrens 	kmem_free(remove, sizeof (locked_range_t));
549104e2ed7Sperrin }
550104e2ed7Sperrin 
551104e2ed7Sperrin /*
552104e2ed7Sperrin  * Unlock range and destroy range lock structure.
553104e2ed7Sperrin  */
554104e2ed7Sperrin void
rangelock_exit(locked_range_t * lr)55579315247SMatthew Ahrens rangelock_exit(locked_range_t *lr)
556104e2ed7Sperrin {
55779315247SMatthew Ahrens 	rangelock_t *rl = lr->lr_rangelock;
558c5c6ffa0Smaybee 
55979315247SMatthew Ahrens 	ASSERT(lr->lr_type == RL_WRITER || lr->lr_type == RL_READER);
56079315247SMatthew Ahrens 	ASSERT(lr->lr_count == 1 || lr->lr_count == 0);
56179315247SMatthew Ahrens 	ASSERT(!lr->lr_proxy);
562104e2ed7Sperrin 
56379315247SMatthew Ahrens 	mutex_enter(&rl->rl_lock);
56479315247SMatthew Ahrens 	if (lr->lr_type == RL_WRITER) {
565104e2ed7Sperrin 		/* writer locks can't be shared or split */
56679315247SMatthew Ahrens 		avl_remove(&rl->rl_tree, lr);
56779315247SMatthew Ahrens 		mutex_exit(&rl->rl_lock);
56879315247SMatthew Ahrens 		if (lr->lr_write_wanted) {
56979315247SMatthew Ahrens 			cv_broadcast(&lr->lr_write_cv);
57079315247SMatthew Ahrens 			cv_destroy(&lr->lr_write_cv);
571c25056deSgw 		}
57279315247SMatthew Ahrens 		if (lr->lr_read_wanted) {
57379315247SMatthew Ahrens 			cv_broadcast(&lr->lr_read_cv);
57479315247SMatthew Ahrens 			cv_destroy(&lr->lr_read_cv);
575c25056deSgw 		}
57679315247SMatthew Ahrens 		kmem_free(lr, sizeof (locked_range_t));
577104e2ed7Sperrin 	} else {
578104e2ed7Sperrin 		/*
57979315247SMatthew Ahrens 		 * lock may be shared, let rangelock_exit_reader()
580104e2ed7Sperrin 		 * release the lock and free the rl_t
581104e2ed7Sperrin 		 */
58279315247SMatthew Ahrens 		rangelock_exit_reader(rl, lr);
58379315247SMatthew Ahrens 		mutex_exit(&rl->rl_lock);
584104e2ed7Sperrin 	}
585104e2ed7Sperrin }
586104e2ed7Sperrin 
587104e2ed7Sperrin /*
588104e2ed7Sperrin  * Reduce range locked as RL_WRITER from whole file to specified range.
58979315247SMatthew Ahrens  * Asserts the whole file is exclusively locked and so there's only one
590104e2ed7Sperrin  * entry in the tree.
591104e2ed7Sperrin  */
592104e2ed7Sperrin void
rangelock_reduce(locked_range_t * lr,uint64_t off,uint64_t len)59379315247SMatthew Ahrens rangelock_reduce(locked_range_t *lr, uint64_t off, uint64_t len)
594104e2ed7Sperrin {
59579315247SMatthew Ahrens 	rangelock_t *rl = lr->lr_rangelock;
596c5c6ffa0Smaybee 
597104e2ed7Sperrin 	/* Ensure there are no other locks */
59879315247SMatthew Ahrens 	ASSERT3U(avl_numnodes(&rl->rl_tree), ==, 1);
59979315247SMatthew Ahrens 	ASSERT3U(lr->lr_offset, ==, 0);
60079315247SMatthew Ahrens 	ASSERT3U(lr->lr_type, ==, RL_WRITER);
60179315247SMatthew Ahrens 	ASSERT(!lr->lr_proxy);
60279315247SMatthew Ahrens 	ASSERT3U(lr->lr_length, ==, UINT64_MAX);
60379315247SMatthew Ahrens 	ASSERT3U(lr->lr_count, ==, 1);
60479315247SMatthew Ahrens 
60579315247SMatthew Ahrens 	mutex_enter(&rl->rl_lock);
60679315247SMatthew Ahrens 	lr->lr_offset = off;
60779315247SMatthew Ahrens 	lr->lr_length = len;
60879315247SMatthew Ahrens 	mutex_exit(&rl->rl_lock);
60979315247SMatthew Ahrens 	if (lr->lr_write_wanted)
61079315247SMatthew Ahrens 		cv_broadcast(&lr->lr_write_cv);
61179315247SMatthew Ahrens 	if (lr->lr_read_wanted)
61279315247SMatthew Ahrens 		cv_broadcast(&lr->lr_read_cv);
613104e2ed7Sperrin }
614