Lines Matching defs:tree
11 * Ext4 extents status tree core functions.
22 * will introduce a new structure called io tree to track all extent
25 * Delay extent tree is the first step to achieve this goal. It is
27 * extent tree, whose goal is only track delayed extents in memory to
30 * delay extent tree at the first commit. But for better understand
31 * what it does, it has been rename to extent status tree.
35 * tracked in the tree. It maintains the delayed extent when a delayed
41 * status tree and future works.
44 * In this step all extent status are tracked by extent status tree.
45 * Thus, we can first try to lookup a block mapping in this tree before
46 * finding it in extent tree. Hence, single extent cache can be removed
47 * because extent status tree can do a better job. Extents in status
48 * tree are loaded on-demand. Therefore, the extent status tree may not
50 * to reclaim memory from extent status tree because fragmented extent
51 * tree will make status tree cost too much memory. written/unwritten/-
52 * hole extents in the tree will be reclaimed by this shrinker when we
58 * Extent status tree implementation for ext4.
62 * Extent status tree tracks all extent status.
64 * 1. Why we need to implement extent status tree?
66 * Without extent status tree, ext4 identifies a delayed extent by looking
73 * Let us have a look at how they do without extent status tree.
90 * With extent status tree implementation, FIEMAP, SEEK_HOLE/DATA,
93 * not by searching the extent tree.
97 * 2. Ext4 extent status tree impelmentation
101 * physically. Unlike extent in extent tree, this extent in ext4 is
106 * -- extent status tree
107 * Every inode has an extent status tree and all allocation blocks
108 * are added to the tree with different status. The extent in the
109 * tree are ordered by logical block no.
111 * -- operations on a extent status tree
112 * There are three important operations on a delayed extent tree: find
115 * -- race on a extent status tree
116 * Extent status tree is protected by inode->i_es_lock.
119 * Fragmented extent tree will make extent status tree cost too much
121 * the tree under a heavy memory pressure.
172 void ext4_es_init_tree(struct ext4_es_tree *tree)
174 tree->root = RB_ROOT;
175 tree->cache_es = NULL;
181 struct ext4_es_tree *tree;
185 tree = &EXT4_I(inode)->i_es_tree;
186 node = rb_first(&tree->root);
208 * search through the tree for an delayed extent with a given offset. If
242 * extents status tree
251 * in the extents status tree that satisfies @matching_fn. If a match
262 struct ext4_es_tree *tree = NULL;
269 tree = &EXT4_I(inode)->i_es_tree;
273 es1 = READ_ONCE(tree->cache_es);
281 es1 = __es_tree_search(&tree->root, lblk);
297 WRITE_ONCE(tree->cache_es, es1);
327 * in extents status tree
348 return false; /* no matching extent in the tree */
378 * extents status tree
569 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
582 rb_erase(&es->rb_node, &tree->root);
593 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
606 rb_erase(node, &tree->root);
711 * access direct/indirect tree from outside. It is too dirty to define
788 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
789 struct rb_node **p = &tree->root.rb_node;
836 rb_insert_color(&es->rb_node, &tree->root);
839 tree->cache_es = es;
845 * status tree.
863 es_debug("add [%u/%u) %llu %x to extent status tree of inode %lu\n",
941 * tree if and only if there isn't information about the range in
974 * ext4_es_lookup_extent() looks up an extent in extent status tree.
984 struct ext4_es_tree *tree;
996 tree = &EXT4_I(inode)->i_es_tree;
1001 es1 = READ_ONCE(tree->cache_es);
1009 node = tree->root.rb_node;
1063 * in file from extent status tree
1189 * @root - root of pending reservation tree
1223 * released when removing a block range from the extent status tree
1243 struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;
1310 * extents status tree.
1335 pr = __pr_tree_search(&tree->root, first_lclu);
1339 rb_erase(&pr->rb_node, &tree->root);
1353 * __es_remove_extent - removes block range from extent status tree
1370 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
1383 es = __es_tree_search(&tree->root, lblk);
1390 tree->cache_es = NULL;
1454 rb_erase(&es->rb_node, &tree->root);
1486 * ext4_es_remove_extent - removes block range from extent status tree
1507 es_debug("remove [%u/%u) from extent status tree of inode %lu\n",
1762 * Return 0 if we hit end of tree / interval, 1 if we exhausted nr_to_scan.
1770 struct ext4_es_tree *tree = &ei->i_es_tree;
1774 es = __es_tree_search(&tree->root, ei->i_es_shrink_lblk);
1794 rb_erase(&es->rb_node, &tree->root);
1841 struct ext4_es_tree *tree;
1845 tree = &EXT4_I(inode)->i_es_tree;
1846 tree->cache_es = NULL;
1847 node = rb_first(&tree->root);
1852 rb_erase(&es->rb_node, &tree->root);
1863 struct ext4_pending_tree *tree;
1868 tree = &EXT4_I(inode)->i_pending_tree;
1869 node = rb_first(&tree->root);
1894 void ext4_init_pending_tree(struct ext4_pending_tree *tree)
1896 tree->root = RB_ROOT;
1911 struct ext4_pending_tree *tree;
1915 tree = &EXT4_I(inode)->i_pending_tree;
1916 node = (&tree->root)->rb_node;
1945 struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;
1946 struct rb_node **p = &tree->root.rb_node;
1981 rb_insert_color(&pr->rb_node, &tree->root);
2000 struct ext4_pending_tree *tree;
2004 tree = &EXT4_I(inode)->i_pending_tree;
2005 rb_erase(&pr->rb_node, &tree->root);
2053 * tree, adding a pending reservation where
2073 es_debug("add [%u/1) delayed to extent status tree of inode %lu\n",
2147 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
2158 es = __es_tree_search(&tree->root, start);
2231 * Used after a newly allocated extent is added to the extents status tree.
2258 * inserted in the extents status tree due to ENOSPC.