diff options
| -rw-r--r-- | Makefile.in | 2 | ||||
| -rw-r--r-- | find-root.c | 139 | ||||
| -rw-r--r-- | find-root.h | 87 |
3 files changed, 227 insertions, 1 deletions
diff --git a/Makefile.in b/Makefile.in index 3a603983..ad4c56f0 100644 --- a/Makefile.in +++ b/Makefile.in @@ -35,7 +35,7 @@ objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \ extent-cache.o extent_io.o volumes.o utils.o repair.o \ qgroup.o raid6.o free-space-cache.o list_sort.o props.o \ ulist.o qgroup-verify.o backref.o string-table.o task-utils.o \ - inode.o file.o + inode.o file.o find-root.o cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \ cmds-inspect.o cmds-balance.o cmds-send.o cmds-receive.o \ cmds-quota.o cmds-qgroup.o cmds-replace.o cmds-check.o \ diff --git a/find-root.c b/find-root.c new file mode 100644 index 00000000..1af37b54 --- /dev/null +++ b/find-root.c @@ -0,0 +1,139 @@ +/* + * Copyright (C) 2015 Fujitsu. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this program; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 021110-1307, USA. + */ + +#include "kerncompat.h" + +#include <stdio.h> +#include <stdlib.h> +#include "ctree.h" +#include "utils.h" +#include "find-root.h" +#include "volumes.h" +#include "disk-io.h" +#include "extent-cache.h" + +/* Return value is the same as btrfs_find_root_search(). */ +static int add_eb_to_result(struct extent_buffer *eb, + struct cache_tree *result, + u32 leafsize, + struct btrfs_find_root_filter *filter, + struct cache_extent **match) +{ + u64 generation = btrfs_header_generation(eb); + u64 level = btrfs_header_level(eb); + u64 owner = btrfs_header_owner(eb); + u64 start = eb->start; + struct cache_extent *cache; + struct btrfs_find_root_gen_cache *gen_cache = NULL; + int ret = 0; + + if (owner != filter->objectid || level < filter->level || + generation < filter->generation) + return ret; + + /* Get the generation cache or create one */ + cache = search_cache_extent(result, generation); + if (!cache) { + gen_cache = malloc(sizeof(*gen_cache)); + BUG_ON(!gen_cache); + cache = &gen_cache->cache; + cache->start = generation; + cache->size = 1; + cache->objectid = 0; + gen_cache->highest_level = 0; + cache_tree_init(&gen_cache->eb_tree); + + ret = insert_cache_extent(result, cache); + if (ret < 0) + return ret; + } + gen_cache = container_of(cache, struct btrfs_find_root_gen_cache, + cache); + + /* Higher level, clean tree and insert the new one */ + if (level > gen_cache->highest_level) { + free_extent_cache_tree(&gen_cache->eb_tree); + gen_cache->highest_level = level; + /* Fall into the insert routine */ + } + + /* Same level, insert it into the eb_tree */ + if (level == gen_cache->highest_level) { + ret = add_cache_extent(&gen_cache->eb_tree, + start, leafsize); + if (ret < 0 && ret != -EEXIST) + return ret; + ret = 0; + } + if (generation == filter->match_gen && + level == filter->match_level && + !filter->search_all) { + ret = 1; + if (match) + *match = search_cache_extent(&gen_cache->eb_tree, + start); + } + return ret; +} + +/* + * Return 0 if iterating all the metadata extents. + * Return 1 if found root with given gen/level and set *match to it. + * Return <0 if error happens + */ +int btrfs_find_root_search(struct btrfs_root *chunk_root, + struct btrfs_find_root_filter *filter, + struct cache_tree *result, + struct cache_extent **match) +{ + struct btrfs_fs_info *fs_info = chunk_root->fs_info; + struct extent_buffer *eb; + u64 metadata_offset = 0; + u64 metadata_size = 0; + u64 offset = 0; + u32 leafsize = chunk_root->leafsize; + int suppress_errors = 0; + int ret = 0; + + suppress_errors = fs_info->suppress_check_block_errors; + fs_info->suppress_check_block_errors = 1; + while (1) { + ret = btrfs_next_metadata(&fs_info->mapping_tree, + &metadata_offset, &metadata_size); + if (ret) { + if (ret == -ENOENT) + ret = 0; + break; + } + for (offset = metadata_offset; + offset < metadata_offset + metadata_size; + offset += chunk_root->leafsize) { + eb = read_tree_block(chunk_root, offset, leafsize, 0); + if (!eb || IS_ERR(eb)) + continue; + ret = add_eb_to_result(eb, result, leafsize, filter, + match); + free_extent_buffer(eb); + if (ret) + goto out; + } + } +out: + fs_info->suppress_check_block_errors = suppress_errors; + return ret; +} diff --git a/find-root.h b/find-root.h new file mode 100644 index 00000000..1c67ebcc --- /dev/null +++ b/find-root.h @@ -0,0 +1,87 @@ +/* + * Copyright (C) 2015 Fujitsu. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this program; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 021110-1307, USA. + */ + +#ifndef __BTRFS_FIND_ROOT_H__ +#define __BTRFS_FIND_ROOT_H__ + +#include "kerncompat.h" + +#include "ctree.h" +#include "list.h" +#include "extent-cache.h" + +/* + * Find-root will restore the search result in a 2-level trees. + * Search result is a cache_tree consisted of generation_cache. + * Each generation cache records the highest level of this generation + * and all the tree blocks with this generation. + * + * <result> + * cache_tree ----> generation_cache: gen:1 level: 2 eb_tree ----> eb1 + * | |-> eb2 + * | ...... + * |-> generation_cache: gen:2 level: 3 eb_tree ---> eb3 + * + * In the above example, generation 1's highest level is 2, but have multiple + * eb with same generation, so the root of generation 1 must be missing, + * possibly has already been overwritten. + * On the other hand, generation 2's highest level is 3 and we find only one + * eb for it, so it may be the root of generation 2. + */ + +struct btrfs_find_root_gen_cache { + struct cache_extent cache; /* cache->start is generation */ + u64 highest_level; + struct cache_tree eb_tree; +}; + +struct btrfs_find_root_filter { + u64 objectid; /* Only search tree with this objectid */ + u64 generation; /* Only record tree block with higher or + equal generation */ + u8 level; /* Only record tree block with higher or + equal level */ + u8 match_level; + u64 match_gen; + int search_all; + /* + * If set search_all, even the tree block matches match_gen + * and match_level and objectid, still continue searching + * This *WILL* take *TONS* of extra time. + */ +}; +int btrfs_find_root_search(struct btrfs_root *chunk_root, + struct btrfs_find_root_filter *filter, + struct cache_tree *result, + struct cache_extent **match); +static inline void btrfs_find_root_free(struct cache_tree *result) +{ + struct btrfs_find_root_gen_cache *gen_cache; + struct cache_extent *cache; + + cache = first_cache_extent(result); + while (cache) { + gen_cache = container_of(cache, + struct btrfs_find_root_gen_cache, cache); + free_extent_cache_tree(&gen_cache->eb_tree); + remove_cache_extent(result, cache); + free(gen_cache); + cache = first_cache_extent(result); + } +} +#endif |