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.
174 void ext4_es_init_tree(struct ext4_es_tree *tree)
176 tree->root = RB_ROOT;
177 tree->cache_es = NULL;
183 struct ext4_es_tree *tree;
187 tree = &EXT4_I(inode)->i_es_tree;
188 node = rb_first(&tree->root);
210 * search through the tree for an delayed extent with a given offset. If
244 * extents status tree
253 * in the extents status tree that satisfies @matching_fn. If a match
264 struct ext4_es_tree *tree = NULL;
271 tree = &EXT4_I(inode)->i_es_tree;
275 es1 = READ_ONCE(tree->cache_es);
283 es1 = __es_tree_search(&tree->root, lblk);
299 WRITE_ONCE(tree->cache_es, es1);
331 * in extents status tree
352 return false; /* no matching extent in the tree */
382 * extents status tree
573 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
586 rb_erase(&es->rb_node, &tree->root);
597 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
610 rb_erase(node, &tree->root);
716 * access direct/indirect tree from outside. It is too dirty to define
793 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
794 struct rb_node **p = &tree->root.rb_node;
841 rb_insert_color(&es->rb_node, &tree->root);
844 tree->cache_es = es;
850 * status tree.
870 es_debug("add [%u/%u) %llu %x to extent status tree of inode %lu\n",
948 * tree if and only if there isn't information about the range in
981 * ext4_es_lookup_extent() looks up an extent in extent status tree.
991 struct ext4_es_tree *tree;
1003 tree = &EXT4_I(inode)->i_es_tree;
1008 es1 = READ_ONCE(tree->cache_es);
1016 node = tree->root.rb_node;
1070 * in file from extent status tree
1196 * @root - root of pending reservation tree
1230 * released when removing a block range from the extent status tree
1250 struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;
1317 * extents status tree.
1342 pr = __pr_tree_search(&tree->root, first_lclu);
1346 rb_erase(&pr->rb_node, &tree->root);
1360 * __es_remove_extent - removes block range from extent status tree
1377 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
1390 es = __es_tree_search(&tree->root, lblk);
1397 tree->cache_es = NULL;
1461 rb_erase(&es->rb_node, &tree->root);
1493 * ext4_es_remove_extent - removes block range from extent status tree
1514 es_debug("remove [%u/%u) from extent status tree of inode %lu\n",
1768 * Return 0 if we hit end of tree / interval, 1 if we exhausted nr_to_scan.
1776 struct ext4_es_tree *tree = &ei->i_es_tree;
1780 es = __es_tree_search(&tree->root, ei->i_es_shrink_lblk);
1800 rb_erase(&es->rb_node, &tree->root);
1847 struct ext4_es_tree *tree;
1851 tree = &EXT4_I(inode)->i_es_tree;
1852 tree->cache_es = NULL;
1853 node = rb_first(&tree->root);
1858 rb_erase(&es->rb_node, &tree->root);
1869 struct ext4_pending_tree *tree;
1874 tree = &EXT4_I(inode)->i_pending_tree;
1875 node = rb_first(&tree->root);
1902 void ext4_init_pending_tree(struct ext4_pending_tree *tree)
1904 tree->root = RB_ROOT;
1919 struct ext4_pending_tree *tree;
1923 tree = &EXT4_I(inode)->i_pending_tree;
1924 node = (&tree->root)->rb_node;
1953 struct ext4_pending_tree *tree = &EXT4_I(inode)->i_pending_tree;
1954 struct rb_node **p = &tree->root.rb_node;
1989 rb_insert_color(&pr->rb_node, &tree->root);
2008 struct ext4_pending_tree *tree;
2012 tree = &EXT4_I(inode)->i_pending_tree;
2013 rb_erase(&pr->rb_node, &tree->root);
2061 * tree, adding a pending reservation where
2083 es_debug("add [%u/1) delayed to extent status tree of inode %lu\n",
2157 struct ext4_es_tree *tree = &EXT4_I(inode)->i_es_tree;
2168 es = __es_tree_search(&tree->root, start);
2241 * Used after a newly allocated extent is added to the extents status tree.
2268 * inserted in the extents status tree due to ENOSPC.