free-space-tree.c

   1 /*
   2  * Copyright (C) 2015 Facebook.  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 #include "ctree.h"
  20 #include "disk-io.h"
  21 #include "free-space-cache.h"
  22 #include "free-space-tree.h"
  23
  24 static struct btrfs_free_space_info *
  25 search_free_space_info(struct btrfs_trans_handle *trans,
  26                        struct btrfs_fs_info *fs_info,
  27                        struct btrfs_block_group_cache *block_group,
  28                        struct btrfs_path *path, int cow)
  29 {
  30         struct btrfs_root *root = fs_info->free_space_root;
  31         struct btrfs_key key;
  32         int ret;
  33
  34         key.objectid = block_group->key.objectid;
  35         key.type = BTRFS_FREE_SPACE_INFO_KEY;
  36         key.offset = block_group->key.offset;
  37
  38         ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
  39         if (ret < 0)
  40                 return ERR_PTR(ret);
  41         if (ret != 0)
  42                 return ERR_PTR(-ENOENT);
  43
  44         return btrfs_item_ptr(path->nodes[0], path->slots[0],
  45                               struct btrfs_free_space_info);
  46 }
  47
  48 static int free_space_test_bit(struct btrfs_block_group_cache *block_group,
  49                                struct btrfs_path *path, u64 offset,
  50                                u64 sectorsize)
  51 {
  52         struct extent_buffer *leaf;
  53         struct btrfs_key key;
  54         u64 found_start, found_end;
  55         unsigned long ptr, i;
  56
  57         leaf = path->nodes[0];
  58         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  59         ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
  60
  61         found_start = key.objectid;
  62         found_end = key.objectid + key.offset;
  63         ASSERT(offset >= found_start && offset < found_end);
  64
  65         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
  66         i = (offset - found_start) / sectorsize;
  67         return !!extent_buffer_test_bit(leaf, ptr, i);
  68 }
  69
  70 static int load_free_space_bitmaps(struct btrfs_fs_info *fs_info,
  71                                    struct btrfs_block_group_cache *block_group,
  72                                    struct btrfs_path *path,
  73                                    u32 expected_extent_count,
  74                                    int *errors)
  75 {
  76         struct btrfs_root *root = fs_info->free_space_root;
  77         struct btrfs_key key;
  78         int prev_bit = 0, bit;
  79         u64 extent_start = 0;
  80         u64 start, end, offset;
  81         u32 extent_count = 0;
  82         int ret;
  83
  84         start = block_group->key.objectid;
  85         end = block_group->key.objectid + block_group->key.offset;
  86
  87         while (1) {
  88                 ret = btrfs_next_item(root, path);
  89                 if (ret < 0)
  90                         goto out;
  91                 if (ret)
  92                         break;
  93
  94                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
  95
  96                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
  97                         break;
  98
  99                 if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY) {
 100                         fprintf(stderr, "unexpected key of type %u\n", key.type);
 101                         (*errors)++;
 102                         break;
 103                 }
 104                 if (key.objectid >= end) {
 105                         fprintf(stderr, "free space bitmap starts at %Lu, beyond end of block group %Lu-%Lu\n",
 106                                 key.objectid, start, end);
 107                         (*errors)++;
 108                         break;
 109                 }
 110                 if (key.objectid + key.offset > end) {
 111                         fprintf(stderr, "free space bitmap ends at %Lu, beyond end of block group %Lu-%Lu\n",
 112                                 key.objectid, start, end);
 113                         (*errors)++;
 114                         break;
 115                 }
 116
 117                 offset = key.objectid;
 118                 while (offset < key.objectid + key.offset) {
 119                         bit = free_space_test_bit(block_group, path, offset,
 120                                                   root->sectorsize);
 121                         if (prev_bit == 0 && bit == 1) {
 122                                 extent_start = offset;
 123                         } else if (prev_bit == 1 && bit == 0) {
 124                                 add_new_free_space(block_group, fs_info, extent_start, offset);
 125                                 extent_count++;
 126                         }
 127                         prev_bit = bit;
 128                         offset += root->sectorsize;
 129                 }
 130         }
 131
 132         if (prev_bit == 1) {
 133                 add_new_free_space(block_group, fs_info, extent_start, end);
 134                 extent_count++;
 135         }
 136
 137         if (extent_count != expected_extent_count) {
 138                 fprintf(stderr, "free space info recorded %u extents, counted %u\n",
 139                         expected_extent_count, extent_count);
 140                 (*errors)++;
 141         }
 142
 143         ret = 0;
 144 out:
 145         return ret;
 146 }
 147
 148 static int load_free_space_extents(struct btrfs_fs_info *fs_info,
 149                                    struct btrfs_block_group_cache *block_group,
 150                                    struct btrfs_path *path,
 151                                    u32 expected_extent_count,
 152                                    int *errors)
 153 {
 154         struct btrfs_root *root = fs_info->free_space_root;
 155         struct btrfs_key key, prev_key;
 156         int have_prev = 0;
 157         u64 start, end;
 158         u32 extent_count = 0;
 159         int ret;
 160
 161         start = block_group->key.objectid;
 162         end = block_group->key.objectid + block_group->key.offset;
 163
 164         while (1) {
 165                 ret = btrfs_next_item(root, path);
 166                 if (ret < 0)
 167                         goto out;
 168                 if (ret)
 169                         break;
 170
 171                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 172
 173                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
 174                         break;
 175
 176                 if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
 177                         fprintf(stderr, "unexpected key of type %u\n", key.type);
 178                         (*errors)++;
 179                         break;
 180                 }
 181                 if (key.objectid >= end) {
 182                         fprintf(stderr, "free space extent starts at %Lu, beyond end of block group %Lu-%Lu\n",
 183                                 key.objectid, start, end);
 184                         (*errors)++;
 185                         break;
 186                 }
 187                 if (key.objectid + key.offset > end) {
 188                         fprintf(stderr, "free space extent ends at %Lu, beyond end of block group %Lu-%Lu\n",
 189                                 key.objectid, start, end);
 190                         (*errors)++;
 191                         break;
 192                 }
 193
 194                 if (have_prev) {
 195                         u64 cur_start = key.objectid;
 196                         u64 cur_end = cur_start + key.offset;
 197                         u64 prev_start = prev_key.objectid;
 198                         u64 prev_end = prev_start + prev_key.offset;
 199
 200                         if (cur_start < prev_end) {
 201                                 fprintf(stderr, "free space extent %Lu-%Lu overlaps with previous %Lu-%Lu\n",
 202                                         cur_start, cur_end,
 203                                         prev_start, prev_end);
 204                                 (*errors)++;
 205                         } else if (cur_start == prev_end) {
 206                                 fprintf(stderr, "free space extent %Lu-%Lu is unmerged with previous %Lu-%Lu\n",
 207                                         cur_start, cur_end,
 208                                         prev_start, prev_end);
 209                                 (*errors)++;
 210                         }
 211                 }
 212
 213                 add_new_free_space(block_group, fs_info, key.objectid, key.objectid + key.offset);
 214                 extent_count++;
 215
 216                 prev_key = key;
 217                 have_prev = 1;
 218         }
 219
 220         if (extent_count != expected_extent_count) {
 221                 fprintf(stderr, "free space info recorded %u extents, counted %u\n",
 222                         expected_extent_count, extent_count);
 223                 (*errors)++;
 224         }
 225
 226         ret = 0;
 227 out:
 228         return ret;
 229 }
 230
 231 int load_free_space_tree(struct btrfs_fs_info *fs_info,
 232                          struct btrfs_block_group_cache *block_group)
 233 {
 234         struct btrfs_free_space_info *info;
 235         struct btrfs_path *path;
 236         u32 extent_count, flags;
 237         int errors = 0;
 238         int ret;
 239
 240         path = btrfs_alloc_path();
 241         if (!path)
 242                 return -ENOMEM;
 243         path->reada = 1;
 244
 245         info = search_free_space_info(NULL, fs_info, block_group, path, 0);
 246         if (IS_ERR(info)) {
 247                 ret = PTR_ERR(info);
 248                 goto out;
 249         }
 250         extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
 251         flags = btrfs_free_space_flags(path->nodes[0], info);
 252
 253         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
 254                 ret = load_free_space_bitmaps(fs_info, block_group, path,
 255                                               extent_count, &errors);
 256         } else {
 257                 ret = load_free_space_extents(fs_info, block_group, path,
 258                                               extent_count, &errors);
 259         }
 260         if (ret)
 261                 goto out;
 262
 263         ret = 0;
 264 out:
 265         btrfs_free_path(path);
 266         return ret ? ret : errors;
 267 }