Btrfs progs v4.17.1
[btrfs-progs-unstable/devel.git] / find-root.h
blob60d1111dca2ef8a1b05581c70afecd4cd99acc1e
1 /*
2 * Copyright (C) 2015 Fujitsu. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
19 #ifndef __BTRFS_FIND_ROOT_H__
20 #define __BTRFS_FIND_ROOT_H__
22 #include "kerncompat.h"
24 #include "ctree.h"
25 #include "list.h"
26 #include "extent-cache.h"
29 * Find-root will restore the search result in a 2-level trees.
30 * Search result is a cache_tree consisted of generation_cache.
31 * Each generation cache records the highest level of this generation
32 * and all the tree blocks with this generation.
34 * <result>
35 * cache_tree ----> generation_cache: gen:1 level: 2 eb_tree ----> eb1
36 * | |-> eb2
37 * | ......
38 * |-> generation_cache: gen:2 level: 3 eb_tree ---> eb3
40 * In the above example, generation 1's highest level is 2, but have multiple
41 * eb with same generation, so the root of generation 1 must be missing,
42 * possibly has already been overwritten.
43 * On the other hand, generation 2's highest level is 3 and we find only one
44 * eb for it, so it may be the root of generation 2.
47 struct btrfs_find_root_gen_cache {
48 struct cache_extent cache; /* cache->start is generation */
49 u64 highest_level;
50 struct cache_tree eb_tree;
53 struct btrfs_find_root_filter {
54 u64 objectid; /* Only search tree with this objectid */
55 u64 generation; /* Only record tree block with higher or
56 equal generation */
57 u8 level; /* Only record tree block with higher or
58 equal level */
59 u8 match_level;
60 u64 match_gen;
61 int search_all;
63 * If set search_all, even the tree block matches match_gen
64 * and match_level and objectid, still continue searching
65 * This *WILL* take *TONS* of extra time.
68 int btrfs_find_root_search(struct btrfs_fs_info *fs_info,
69 struct btrfs_find_root_filter *filter,
70 struct cache_tree *result,
71 struct cache_extent **match);
72 static inline void btrfs_find_root_free(struct cache_tree *result)
74 struct btrfs_find_root_gen_cache *gen_cache;
75 struct cache_extent *cache;
77 cache = first_cache_extent(result);
78 while (cache) {
79 gen_cache = container_of(cache,
80 struct btrfs_find_root_gen_cache, cache);
81 free_extent_cache_tree(&gen_cache->eb_tree);
82 remove_cache_extent(result, cache);
83 free(gen_cache);
84 cache = first_cache_extent(result);
87 #endif