9  * or https://opensource.org/licenses/CDDL-1.0.
35  * ---------
42  * --------------------
45  *    freed etc and zp_size reset. zp_size must be set within range lock.
50  *    to ensure the file size is at least the offset last written.
56  * --------
59  * The starting range offset is used for searching and sorting the tree.
62  * -----------
69  * ---------------------------------------
70  * The avl code only allows one node at a particular offset. Also it's very
72  * (because the very 1st in the ordered list might be at offset 0 but
77  * When a reader lock overlaps with another then a proxy lock is created
78  * for that range and replaces the original lock. If the overlap
80  * Otherwise, the proxy lock is split into smaller lock ranges and
83  * Meanwhile, the original lock is kept around (this is the callers handle)
84  * and its offset and length are used when releasing the lock.
87  * -------------------
89  * readers on a range don't starve a writer for the same range lock,
94  * writers then all readers before destroying the lock.
97  * ------------------
98  * Append mode writes need to lock a range at the end of a file.
99  * The offset of the end of the file is determined under the
100  * range locking mutex, and the lock type converted from RL_APPEND to
104  * -------------------
109  * exclusively locked, then later the caller will reduce the lock
119  * Locks are ordered on the start offset of the range.
127 	return (TREE_CMP(rl1->lr_offset, rl2->lr_offset));  in zfs_rangelock_compare()
131  * The callback is invoked when acquiring a RL_WRITER or RL_APPEND lock.
138 	mutex_init(&rl->rl_lock, NULL, MUTEX_DEFAULT, NULL);  in zfs_rangelock_init()
139 	avl_create(&rl->rl_tree, zfs_rangelock_compare,  in zfs_rangelock_init()
141 	rl->rl_cb = cb;  in zfs_rangelock_init()
142 	rl->rl_arg = arg;  in zfs_rangelock_init()
148 	mutex_destroy(&rl->rl_lock);  in zfs_rangelock_fini()
149 	avl_destroy(&rl->rl_tree);  in zfs_rangelock_fini()
153  * Check if a write lock can be grabbed.  If not, fail immediately or sleep and
160 	avl_tree_t *tree = &rl->rl_tree;  in zfs_rangelock_enter_writer()
163 	uint64_t orig_off = new->lr_offset;  in zfs_rangelock_enter_writer()
164 	uint64_t orig_len = new->lr_length;  in zfs_rangelock_enter_writer()
165 	zfs_rangelock_type_t orig_type = new->lr_type;  in zfs_rangelock_enter_writer()
169 		 * Call callback which can modify new->r_off,len,type.  in zfs_rangelock_enter_writer()
173 		if (rl->rl_cb != NULL) {  in zfs_rangelock_enter_writer()
174 			rl->rl_cb(new, rl->rl_arg);  in zfs_rangelock_enter_writer()
181 		ASSERT3U(new->lr_type, ==, RL_WRITER);  in zfs_rangelock_enter_writer()
196 			goto wait; /* already locked at same offset */  in zfs_rangelock_enter_writer()
200 		    lr->lr_offset < new->lr_offset + new->lr_length)  in zfs_rangelock_enter_writer()
205 		    lr->lr_offset + lr->lr_length > new->lr_offset)  in zfs_rangelock_enter_writer()
213 		if (!lr->lr_write_wanted) {  in zfs_rangelock_enter_writer()
214 			cv_init(&lr->lr_write_cv, NULL, CV_DEFAULT, NULL);  in zfs_rangelock_enter_writer()
215 			lr->lr_write_wanted = B_TRUE;  in zfs_rangelock_enter_writer()
217 		cv_wait(&lr->lr_write_cv, &rl->rl_lock);  in zfs_rangelock_enter_writer()
220 		new->lr_offset = orig_off;  in zfs_rangelock_enter_writer()
221 		new->lr_length = orig_len;  in zfs_rangelock_enter_writer()
222 		new->lr_type = orig_type;  in zfs_rangelock_enter_writer()
227  * If this is an original (non-proxy) lock then replace it by
235 	if (lr->lr_proxy)  in zfs_rangelock_proxify()
238 	ASSERT3U(lr->lr_count, ==, 1);  in zfs_rangelock_proxify()
239 	ASSERT(lr->lr_write_wanted == B_FALSE);  in zfs_rangelock_proxify()
240 	ASSERT(lr->lr_read_wanted == B_FALSE);  in zfs_rangelock_proxify()
242 	lr->lr_count = 0;  in zfs_rangelock_proxify()
244 	/* create a proxy range lock */  in zfs_rangelock_proxify()
246 	proxy->lr_offset = lr->lr_offset;  in zfs_rangelock_proxify()
247 	proxy->lr_length = lr->lr_length;  in zfs_rangelock_proxify()
248 	proxy->lr_count = 1;  in zfs_rangelock_proxify()
249 	proxy->lr_type = RL_READER;  in zfs_rangelock_proxify()
250 	proxy->lr_proxy = B_TRUE;  in zfs_rangelock_proxify()
251 	proxy->lr_write_wanted = B_FALSE;  in zfs_rangelock_proxify()
252 	proxy->lr_read_wanted = B_FALSE;  in zfs_rangelock_proxify()
259  * Split the range lock at the supplied offset
267 	ASSERT3U(lr->lr_length, >, 1);  in zfs_rangelock_split()
268 	ASSERT3U(off, >, lr->lr_offset);  in zfs_rangelock_split()
269 	ASSERT3U(off, <, lr->lr_offset + lr->lr_length);  in zfs_rangelock_split()
270 	ASSERT(lr->lr_write_wanted == B_FALSE);  in zfs_rangelock_split()
271 	ASSERT(lr->lr_read_wanted == B_FALSE);  in zfs_rangelock_split()
273 	/* create the rear proxy range lock */  in zfs_rangelock_split()
275 	rear->lr_offset = off;  in zfs_rangelock_split()
276 	rear->lr_length = lr->lr_offset + lr->lr_length - off;  in zfs_rangelock_split()
277 	rear->lr_count = lr->lr_count;  in zfs_rangelock_split()
278 	rear->lr_type = RL_READER;  in zfs_rangelock_split()
279 	rear->lr_proxy = B_TRUE;  in zfs_rangelock_split()
280 	rear->lr_write_wanted = B_FALSE;  in zfs_rangelock_split()
281 	rear->lr_read_wanted = B_FALSE;  in zfs_rangelock_split()
284 	front->lr_length = off - lr->lr_offset;  in zfs_rangelock_split()
291  * Create and add a new proxy range lock for the supplied range.
300 	lr->lr_offset = off;  in zfs_rangelock_new_proxy()
301 	lr->lr_length = len;  in zfs_rangelock_new_proxy()
302 	lr->lr_count = 1;  in zfs_rangelock_new_proxy()
303 	lr->lr_type = RL_READER;  in zfs_rangelock_new_proxy()
304 	lr->lr_proxy = B_TRUE;  in zfs_rangelock_new_proxy()
305 	lr->lr_write_wanted = B_FALSE;  in zfs_rangelock_new_proxy()
306 	lr->lr_read_wanted = B_FALSE;  in zfs_rangelock_new_proxy()
315 	uint64_t off = new->lr_offset;  in zfs_rangelock_add_reader()
316 	uint64_t len = new->lr_length;  in zfs_rangelock_add_reader()
320 	 * - pointing to an entry at the same offset  in zfs_rangelock_add_reader()
321 	 * - pointing to the entry with the closest previous offset whose  in zfs_rangelock_add_reader()
323 	 * - null, if there were no ranges starting before the new one  in zfs_rangelock_add_reader()
326 		if (prev->lr_offset + prev->lr_length <= off) {  in zfs_rangelock_add_reader()
328 		} else if (prev->lr_offset != off) {  in zfs_rangelock_add_reader()
337 	ASSERT((prev == NULL) || (prev->lr_offset == off));  in zfs_rangelock_add_reader()
344 	if (next == NULL || off + len <= next->lr_offset) {  in zfs_rangelock_add_reader()
350 	if (off < next->lr_offset) {  in zfs_rangelock_add_reader()
352 		zfs_rangelock_new_proxy(tree, off, next->lr_offset - off);  in zfs_rangelock_add_reader()
355 	new->lr_count = 0; /* will use proxies in tree */  in zfs_rangelock_add_reader()
363 		if (off + len <= next->lr_offset)  in zfs_rangelock_add_reader()
365 		if (prev != NULL && prev->lr_offset + prev->lr_length <  in zfs_rangelock_add_reader()
366 		    next->lr_offset) {  in zfs_rangelock_add_reader()
368 			ASSERT3U(next->lr_offset, >,  in zfs_rangelock_add_reader()
369 			    prev->lr_offset + prev->lr_length);  in zfs_rangelock_add_reader()
371 			    prev->lr_offset + prev->lr_length,  in zfs_rangelock_add_reader()
372 			    next->lr_offset -  in zfs_rangelock_add_reader()
373 			    (prev->lr_offset + prev->lr_length));  in zfs_rangelock_add_reader()
375 		if (off + len == next->lr_offset + next->lr_length) {  in zfs_rangelock_add_reader()
378 			next->lr_count++;  in zfs_rangelock_add_reader()
381 		if (off + len < next->lr_offset + next->lr_length) {  in zfs_rangelock_add_reader()
384 			next->lr_count++;  in zfs_rangelock_add_reader()
387 		ASSERT3U(off + len, >, next->lr_offset + next->lr_length);  in zfs_rangelock_add_reader()
389 		next->lr_count++;  in zfs_rangelock_add_reader()
393 	zfs_rangelock_new_proxy(tree, prev->lr_offset + prev->lr_length,  in zfs_rangelock_add_reader()
394 	    (off + len) - (prev->lr_offset + prev->lr_length));  in zfs_rangelock_add_reader()
398  * Check if a reader lock can be grabbed.  If not, fail immediately or sleep and
405 	avl_tree_t *tree = &rl->rl_tree;  in zfs_rangelock_enter_reader()
408 	uint64_t off = new->lr_offset;  in zfs_rangelock_enter_reader()
409 	uint64_t len = new->lr_length;  in zfs_rangelock_enter_reader()
420 	 * Check the previous range for a writer lock overlap.  in zfs_rangelock_enter_reader()
422 	if (prev && (off < prev->lr_offset + prev->lr_length)) {  in zfs_rangelock_enter_reader()
423 		if ((prev->lr_type == RL_WRITER) || (prev->lr_write_wanted)) {  in zfs_rangelock_enter_reader()
426 			if (!prev->lr_read_wanted) {  in zfs_rangelock_enter_reader()
427 				cv_init(&prev->lr_read_cv,  in zfs_rangelock_enter_reader()
429 				prev->lr_read_wanted = B_TRUE;  in zfs_rangelock_enter_reader()
431 			cv_wait(&prev->lr_read_cv, &rl->rl_lock);  in zfs_rangelock_enter_reader()
434 		if (off + len < prev->lr_offset + prev->lr_length)  in zfs_rangelock_enter_reader()
440 	 * write lock any overlap.  in zfs_rangelock_enter_reader()
447 		if (off + len <= next->lr_offset)  in zfs_rangelock_enter_reader()
449 		if ((next->lr_type == RL_WRITER) || (next->lr_write_wanted)) {  in zfs_rangelock_enter_reader()
452 			if (!next->lr_read_wanted) {  in zfs_rangelock_enter_reader()
453 				cv_init(&next->lr_read_cv,  in zfs_rangelock_enter_reader()
455 				next->lr_read_wanted = B_TRUE;  in zfs_rangelock_enter_reader()
457 			cv_wait(&next->lr_read_cv, &rl->rl_lock);  in zfs_rangelock_enter_reader()
460 		if (off + len <= next->lr_offset + next->lr_length)  in zfs_rangelock_enter_reader()
466 	 * Add the read lock, which may involve splitting existing  in zfs_rangelock_enter_reader()
474  * Lock a range (offset, length) as either shared (RL_READER) or exclusive
476  * it to a RL_WRITER lock (with the offset at the end of the file).  Returns
477  * the range lock structure for later unlocking (or reduce range if the
479  * lock could not be acquired immediately.
490 	new->lr_rangelock = rl;  in zfs_rangelock_enter_impl()
491 	new->lr_offset = off;  in zfs_rangelock_enter_impl()
493 		len = UINT64_MAX - off;  in zfs_rangelock_enter_impl()
494 	new->lr_length = len;  in zfs_rangelock_enter_impl()
495 	new->lr_count = 1; /* assume it's going to be in the tree */  in zfs_rangelock_enter_impl()
496 	new->lr_type = type;  in zfs_rangelock_enter_impl()
497 	new->lr_proxy = B_FALSE;  in zfs_rangelock_enter_impl()
498 	new->lr_write_wanted = B_FALSE;  in zfs_rangelock_enter_impl()
499 	new->lr_read_wanted = B_FALSE;  in zfs_rangelock_enter_impl()
501 	mutex_enter(&rl->rl_lock);  in zfs_rangelock_enter_impl()
506 		if (avl_numnodes(&rl->rl_tree) == 0) {  in zfs_rangelock_enter_impl()
507 			avl_add(&rl->rl_tree, new);  in zfs_rangelock_enter_impl()
516 	mutex_exit(&rl->rl_lock);  in zfs_rangelock_enter_impl()
540 	if (lr->lr_write_wanted)  in zfs_rangelock_free()
541 		cv_destroy(&lr->lr_write_cv);  in zfs_rangelock_free()
543 	if (lr->lr_read_wanted)  in zfs_rangelock_free()
544 		cv_destroy(&lr->lr_read_cv);  in zfs_rangelock_free()
550  * Unlock a reader lock
556 	avl_tree_t *tree = &rl->rl_tree;  in zfs_rangelock_exit_reader()
566 	if (remove->lr_count == 1) {  in zfs_rangelock_exit_reader()
568 		if (remove->lr_write_wanted)  in zfs_rangelock_exit_reader()
569 			cv_broadcast(&remove->lr_write_cv);  in zfs_rangelock_exit_reader()
570 		if (remove->lr_read_wanted)  in zfs_rangelock_exit_reader()
571 			cv_broadcast(&remove->lr_read_cv);  in zfs_rangelock_exit_reader()
574 		ASSERT0(remove->lr_count);  in zfs_rangelock_exit_reader()
575 		ASSERT0(remove->lr_write_wanted);  in zfs_rangelock_exit_reader()
576 		ASSERT0(remove->lr_read_wanted);  in zfs_rangelock_exit_reader()
578 		 * Find start proxy representing this reader lock,  in zfs_rangelock_exit_reader()
584 		ASSERT3U(lr->lr_count, !=, 0);  in zfs_rangelock_exit_reader()
585 		ASSERT3U(lr->lr_type, ==, RL_READER);  in zfs_rangelock_exit_reader()
587 		for (len = remove->lr_length; len != 0; lr = next) {  in zfs_rangelock_exit_reader()
588 			len -= lr->lr_length;  in zfs_rangelock_exit_reader()
592 				ASSERT3U(lr->lr_offset + lr->lr_length, ==,  in zfs_rangelock_exit_reader()
593 				    next->lr_offset);  in zfs_rangelock_exit_reader()
594 				ASSERT3U(next->lr_count, !=, 0);  in zfs_rangelock_exit_reader()
595 				ASSERT3U(next->lr_type, ==, RL_READER);  in zfs_rangelock_exit_reader()
597 			lr->lr_count--;  in zfs_rangelock_exit_reader()
598 			if (lr->lr_count == 0) {  in zfs_rangelock_exit_reader()
600 				if (lr->lr_write_wanted)  in zfs_rangelock_exit_reader()
601 					cv_broadcast(&lr->lr_write_cv);  in zfs_rangelock_exit_reader()
602 				if (lr->lr_read_wanted)  in zfs_rangelock_exit_reader()
603 					cv_broadcast(&lr->lr_read_cv);  in zfs_rangelock_exit_reader()
612  * Unlock range and destroy range lock structure.
617 	zfs_rangelock_t *rl = lr->lr_rangelock;  in zfs_rangelock_exit()
621 	ASSERT(lr->lr_type == RL_WRITER || lr->lr_type == RL_READER);  in zfs_rangelock_exit()
622 	ASSERT(lr->lr_count == 1 || lr->lr_count == 0);  in zfs_rangelock_exit()
623 	ASSERT(!lr->lr_proxy);  in zfs_rangelock_exit()
632 	mutex_enter(&rl->rl_lock);  in zfs_rangelock_exit()
633 	if (lr->lr_type == RL_WRITER) {  in zfs_rangelock_exit()
635 		avl_remove(&rl->rl_tree, lr);  in zfs_rangelock_exit()
636 		if (lr->lr_write_wanted)  in zfs_rangelock_exit()
637 			cv_broadcast(&lr->lr_write_cv);  in zfs_rangelock_exit()
638 		if (lr->lr_read_wanted)  in zfs_rangelock_exit()
639 			cv_broadcast(&lr->lr_read_cv);  in zfs_rangelock_exit()
643 		 * lock may be shared, let rangelock_exit_reader()  in zfs_rangelock_exit()
644 		 * release the lock and free the zfs_locked_range_t.  in zfs_rangelock_exit()
648 	mutex_exit(&rl->rl_lock);  in zfs_rangelock_exit()
664 	zfs_rangelock_t *rl = lr->lr_rangelock;  in zfs_rangelock_reduce()
667 	ASSERT3U(avl_numnodes(&rl->rl_tree), ==, 1);  in zfs_rangelock_reduce()
668 	ASSERT3U(lr->lr_offset, ==, 0);  in zfs_rangelock_reduce()
669 	ASSERT3U(lr->lr_type, ==, RL_WRITER);  in zfs_rangelock_reduce()
670 	ASSERT(!lr->lr_proxy);  in zfs_rangelock_reduce()
671 	ASSERT3U(lr->lr_length, ==, UINT64_MAX);  in zfs_rangelock_reduce()
672 	ASSERT3U(lr->lr_count, ==, 1);  in zfs_rangelock_reduce()
674 	mutex_enter(&rl->rl_lock);  in zfs_rangelock_reduce()
675 	lr->lr_offset = off;  in zfs_rangelock_reduce()
676 	lr->lr_length = len;  in zfs_rangelock_reduce()
677 	mutex_exit(&rl->rl_lock);  in zfs_rangelock_reduce()
678 	if (lr->lr_write_wanted)  in zfs_rangelock_reduce()
679 		cv_broadcast(&lr->lr_write_cv);  in zfs_rangelock_reduce()
680 	if (lr->lr_read_wanted)  in zfs_rangelock_reduce()
681 		cv_broadcast(&lr->lr_read_cv);  in zfs_rangelock_reduce()