fs/zfs/zfs_rlock.c

38  * AVL tree
40  * An AVL tree is used to maintain the state of the existing ranges
42  * The starting range offset is used for searching and sorting the tree.
47  * locks. On entry to zfs_lock_range() a rl_t is allocated; the tree
48  * searched that finds no overlap, and *this* rl_t is placed in the tree.
103 	avl_tree_t *tree = &zp->z_range_avl;
146 		if (avl_numnodes(tree) == 0) {
148 			avl_add(tree, new);
155 		rl = avl_find(tree, new, &where);
159 		rl = (rl_t *)avl_nearest(tree, where, AVL_AFTER);
163 		rl = (rl_t *)avl_nearest(tree, where, AVL_BEFORE);
168 		avl_insert(tree, new, where);
188 zfs_range_proxify(avl_tree_t *tree, rl_t *rl)
198 	avl_remove(tree, rl);
210 	avl_add(tree, proxy);
220 zfs_range_split(avl_tree_t *tree, rl_t *rl, uint64_t off)
240 	front = zfs_range_proxify(tree, rl);
243 	avl_insert_here(tree, rear, front, AVL_AFTER);
251 zfs_range_new_proxy(avl_tree_t *tree, uint64_t off, uint64_t len)
264 	avl_add(tree, rl);
268 zfs_range_add_reader(avl_tree_t *tree, rl_t *new, rl_t *prev, avl_index_t where)
289 			prev = zfs_range_split(tree, prev, off);
290 			prev = AVL_NEXT(tree, prev); /* move to rear range */
298 		next = (rl_t *)avl_nearest(tree, where, AVL_AFTER);
301 		/* no overlaps, use the original new rl_t in the tree */
302 		avl_insert(tree, new, where);
308 		zfs_range_new_proxy(tree, off, next->r_off - off);
311 	new->r_cnt = 0; /* will use proxies in tree */
318 	for (prev = NULL; next; prev = next, next = AVL_NEXT(tree, next)) {
324 			zfs_range_new_proxy(tree, prev->r_off + prev->r_len,
329 			next = zfs_range_proxify(tree, next);
335 			next = zfs_range_split(tree, next, off + len);
340 		next = zfs_range_proxify(tree, next);
345 	zfs_range_new_proxy(tree, prev->r_off + prev->r_len,
355 	avl_tree_t *tree = &zp->z_range_avl;
365 	prev = avl_find(tree, new, &where);
367 		prev = (rl_t *)avl_nearest(tree, where, AVL_BEFORE);
390 		next = AVL_NEXT(tree, prev);
392 		next = (rl_t *)avl_nearest(tree, where, AVL_AFTER);
393 	for (; next; next = AVL_NEXT(tree, next)) {
413 	zfs_range_add_reader(tree, new, prev, where);
435 	new->r_cnt = 1; /* assume it's going to be in the tree */
462 	avl_tree_t *tree = &zp->z_range_avl;
467 	 * The common case is when the remove entry is in the tree
470 	 * removed from the tree and replaced by proxies (one or
474 		avl_remove(tree, remove);
492 		rl = avl_find(tree, remove, NULL);
499 				next = AVL_NEXT(tree, rl);
507 				avl_remove(tree, rl);
562  * entry in the tree.