find-root.h

   1 /*
   2  * Copyright (C) 2015 Fujitsu.  All rights reserved.
   3  *
   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.
   7  *
   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.
  12  *
  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.
  17  */
  18
  19 #ifndef __BTRFS_FIND_ROOT_H__
  20 #define __BTRFS_FIND_ROOT_H__
  21
  22 #include "kerncompat.h"
  23
  24 #include "ctree.h"
  25 #include "list.h"
  26 #include "extent-cache.h"
  27
  28 /*
  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.
  33  *
  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
  39  *
  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.
  45  */
  46
  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;
  51 };
  52
  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;
  62         /*
  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.
  66          */
  67 };
  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)
  73 {
  74         struct btrfs_find_root_gen_cache *gen_cache;
  75         struct cache_extent *cache;
  76
  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);
  85         }
  86 }
  87 #endif