32  * Initialize the extent tree @tree.  Should be called for each new inode or
35 void extent_map_tree_init(struct extent_map_tree *tree)  in extent_map_tree_init()  argument
37 	tree->map = RB_ROOT_CACHED;  in extent_map_tree_init()
38 	INIT_LIST_HEAD(&tree->modified_extents);  in extent_map_tree_init()
39 	rwlock_init(&tree->lock);  in extent_map_tree_init()
129  * Search through the tree for an extent_map with a given offset.  If it can't
228 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em)  in try_merge_map()  argument
234 	 * We can't modify an extent map that is in the tree and that is being  in try_merge_map()
237 	 * the tree and 1 for this task (which is unpinning the extent map or  in try_merge_map()
262 			rb_erase_cached(&merge->rb_node, &tree->map);  in try_merge_map()
274 		rb_erase_cached(&merge->rb_node, &tree->map);  in try_merge_map()
298 	struct extent_map_tree *tree = &inode->extent_tree;  in unpin_extent_cache()  local
303 	write_lock(&tree->lock);  in unpin_extent_cache()
304 	em = lookup_extent_mapping(tree, start, len);  in unpin_extent_cache()
330 	try_merge_map(tree, em);  in unpin_extent_cache()
339 	write_unlock(&tree->lock);  in unpin_extent_cache()
344 void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em)  in clear_em_logging()  argument
346 	lockdep_assert_held_write(&tree->lock);  in clear_em_logging()
350 		try_merge_map(tree, em);  in clear_em_logging()
353 static inline void setup_extent_mapping(struct extent_map_tree *tree,  in setup_extent_mapping()  argument
364 		list_add(&em->list, &tree->modified_extents);  in setup_extent_mapping()
366 		try_merge_map(tree, em);  in setup_extent_mapping()
370  * Add new extent map to the extent tree
372  * @tree:	tree to insert new map in
377  * Insert @em into @tree or perform a simple forward/backward merge with
379  * into the tree directly, with an additional reference taken, or a
382 static int add_extent_mapping(struct extent_map_tree *tree,  in add_extent_mapping()  argument
387 	lockdep_assert_held_write(&tree->lock);  in add_extent_mapping()
389 	ret = tree_insert(&tree->map, em);  in add_extent_mapping()
393 	setup_extent_mapping(tree, em, modified);  in add_extent_mapping()
399 __lookup_extent_mapping(struct extent_map_tree *tree,  in __lookup_extent_mapping()  argument
407 	rb_node = __tree_search(&tree->map.rb_root, start, &prev_or_next);  in __lookup_extent_mapping()
427  * @tree:	tree to lookup in
431  * Find and return the first extent_map struct in @tree that intersects the
432  * [start, len] range.  There may be additional objects in the tree that
436 struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,  in lookup_extent_mapping()  argument
439 	return __lookup_extent_mapping(tree, start, len, 1);  in lookup_extent_mapping()
445  * @tree:	tree to lookup in
449  * Find and return the first extent_map struct in @tree that intersects the
454 struct extent_map *search_extent_mapping(struct extent_map_tree *tree,  in search_extent_mapping()  argument
457 	return __lookup_extent_mapping(tree, start, len, 0);  in search_extent_mapping()
461  * Remove an extent_map from the extent tree.
463  * @tree:	extent tree to remove from
466  * Remove @em from @tree.  No reference counts are dropped, and no checks
469 void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)  in remove_extent_mapping()  argument
471 	lockdep_assert_held_write(&tree->lock);  in remove_extent_mapping()
474 	rb_erase_cached(&em->rb_node, &tree->map);  in remove_extent_mapping()
480 static void replace_extent_mapping(struct extent_map_tree *tree,  in replace_extent_mapping()  argument
485 	lockdep_assert_held_write(&tree->lock);  in replace_extent_mapping()
491 	rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map);  in replace_extent_mapping()
494 	setup_extent_mapping(tree, new, modified);  in replace_extent_mapping()
518  * Helper for btrfs_get_extent.  Given an existing extent in the tree,
521  * the best fitted new extent into the tree.
563  * @em_tree:  extent tree into which we want to insert the extent mapping
588 	 * Tree-checker should have rejected any inline extent with non-zero  in btrfs_add_extent_mapping()
595 	/* it is possible that someone inserted the extent into the tree  in btrfs_add_extent_mapping()
597 	 * an overlapping map exists in the tree  in btrfs_add_extent_mapping()
642  * Drop all extent maps from a tree in the fastest possible way, rescheduling
643  * if needed. This avoids searching the tree, from the root down to the first
646 static void drop_all_extent_maps_fast(struct extent_map_tree *tree)  in drop_all_extent_maps_fast()  argument
648 	write_lock(&tree->lock);  in drop_all_extent_maps_fast()
649 	while (!RB_EMPTY_ROOT(&tree->map.rb_root)) {  in drop_all_extent_maps_fast()
653 		node = rb_first_cached(&tree->map);  in drop_all_extent_maps_fast()
656 		remove_extent_mapping(tree, em);  in drop_all_extent_maps_fast()
658 		cond_resched_rwlock_write(&tree->lock);  in drop_all_extent_maps_fast()
660 	write_unlock(&tree->lock);  in drop_all_extent_maps_fast()
675  * tree before calling this function.
845 			 * If the extent map is still in the tree it means that  in btrfs_drop_extent_map_range()
858 			 * load it again from the subvolume tree's file extent  in btrfs_drop_extent_map_range()
872 		 * Once for the tree reference (we replaced or removed the  in btrfs_drop_extent_map_range()
873 		 * extent map from the tree).  in btrfs_drop_extent_map_range()
890  * Replace a range in the inode's extent map tree with a new extent map.
893  * @new_em:     The new extent map to add to the inode's extent map tree.
897  * Drops all the extent maps in the inode's extent map tree that intersect the
898  * range of the new extent map and adds the new extent map to the tree.
900  * tree before calling this function.
907 	struct extent_map_tree *tree = &inode->extent_tree;  in btrfs_replace_extent_map_range()  local
914 	 * tree, but getting -EEXIST when adding the new extent map can still  in btrfs_replace_extent_map_range()
922 		write_lock(&tree->lock);  in btrfs_replace_extent_map_range()
923 		ret = add_extent_mapping(tree, new_em, modified);  in btrfs_replace_extent_map_range()
924 		write_unlock(&tree->lock);  in btrfs_replace_extent_map_range()
1008 	/* Once for the tree */  in split_extent_map()