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 #include "transaction.h"
  24
  25 static struct btrfs_free_space_info *
  26 search_free_space_info(struct btrfs_trans_handle *trans,
  27                        struct btrfs_fs_info *fs_info,
  28                        struct btrfs_block_group_cache *block_group,
  29                        struct btrfs_path *path, int cow)
  30 {
  31         struct btrfs_root *root = fs_info->free_space_root;
  32         struct btrfs_key key;
  33         int ret;
  34
  35         key.objectid = block_group->key.objectid;
  36         key.type = BTRFS_FREE_SPACE_INFO_KEY;
  37         key.offset = block_group->key.offset;
  38
  39         ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
  40         if (ret < 0)
  41                 return ERR_PTR(ret);
  42         if (ret != 0)
  43                 return ERR_PTR(-ENOENT);
  44
  45         return btrfs_item_ptr(path->nodes[0], path->slots[0],
  46                               struct btrfs_free_space_info);
  47 }
  48
  49 static int free_space_test_bit(struct btrfs_block_group_cache *block_group,
  50                                struct btrfs_path *path, u64 offset,
  51                                u64 sectorsize)
  52 {
  53         struct extent_buffer *leaf;
  54         struct btrfs_key key;
  55         u64 found_start, found_end;
  56         unsigned long ptr, i;
  57
  58         leaf = path->nodes[0];
  59         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  60         ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
  61
  62         found_start = key.objectid;
  63         found_end = key.objectid + key.offset;
  64         ASSERT(offset >= found_start && offset < found_end);
  65
  66         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
  67         i = (offset - found_start) / sectorsize;
  68         return !!extent_buffer_test_bit(leaf, ptr, i);
  69 }
  70
  71 static int clear_free_space_tree(struct btrfs_trans_handle *trans,
  72                                  struct btrfs_root *root)
  73 {
  74         struct btrfs_path *path;
  75         struct btrfs_key key;
  76         int nr;
  77         int ret;
  78
  79         path = btrfs_alloc_path();
  80         if (!path)
  81                 return -ENOMEM;
  82
  83         key.objectid = 0;
  84         key.type = 0;
  85         key.offset = 0;
  86
  87         while (1) {
  88                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
  89                 if (ret < 0)
  90                         goto out;
  91
  92                 nr = btrfs_header_nritems(path->nodes[0]);
  93                 if (!nr)
  94                         break;
  95
  96                 path->slots[0] = 0;
  97                 ret = btrfs_del_items(trans, root, path, 0, nr);
  98                 if (ret)
  99                         goto out;
 100
 101                 btrfs_release_path(path);
 102         }
 103
 104         ret = 0;
 105 out:
 106         btrfs_free_path(path);
 107         return ret;
 108 }
 109
 110 int btrfs_clear_free_space_tree(struct btrfs_fs_info *fs_info)
 111 {
 112         struct btrfs_trans_handle *trans;
 113         struct btrfs_root *tree_root = fs_info->tree_root;
 114         struct btrfs_root *free_space_root = fs_info->free_space_root;
 115         int ret;
 116         u64 features;
 117
 118         trans = btrfs_start_transaction(tree_root, 0);
 119         if (IS_ERR(trans))
 120                 return PTR_ERR(trans);
 121
 122         features = btrfs_super_compat_ro_flags(fs_info->super_copy);
 123         features &= ~(BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE_VALID |
 124                       BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE);
 125         btrfs_set_super_compat_ro_flags(fs_info->super_copy, features);
 126         fs_info->free_space_root = NULL;
 127
 128         ret = clear_free_space_tree(trans, free_space_root);
 129         if (ret)
 130                 goto abort;
 131
 132         ret = btrfs_del_root(trans, tree_root, &free_space_root->root_key);
 133         if (ret)
 134                 goto abort;
 135
 136         list_del(&free_space_root->dirty_list);
 137
 138         ret = clean_tree_block(free_space_root->node);
 139         if (ret)
 140                 goto abort;
 141         ret = btrfs_free_tree_block(trans, free_space_root,
 142                                     free_space_root->node, 0, 1);
 143         if (ret)
 144                 goto abort;
 145
 146         free_extent_buffer(free_space_root->node);
 147         free_extent_buffer(free_space_root->commit_root);
 148         kfree(free_space_root);
 149
 150         ret = btrfs_commit_transaction(trans, tree_root);
 151
 152 abort:
 153         return ret;
 154 }
 155
 156 static int load_free_space_bitmaps(struct btrfs_fs_info *fs_info,
 157                                    struct btrfs_block_group_cache *block_group,
 158                                    struct btrfs_path *path,
 159                                    u32 expected_extent_count,
 160                                    int *errors)
 161 {
 162         struct btrfs_root *root = fs_info->free_space_root;
 163         struct btrfs_key key;
 164         int prev_bit = 0, bit;
 165         u64 extent_start = 0;
 166         u64 start, end, offset;
 167         u32 extent_count = 0;
 168         int ret;
 169
 170         start = block_group->key.objectid;
 171         end = block_group->key.objectid + block_group->key.offset;
 172
 173         while (1) {
 174                 ret = btrfs_next_item(root, path);
 175                 if (ret < 0)
 176                         goto out;
 177                 if (ret)
 178                         break;
 179
 180                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 181
 182                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
 183                         break;
 184
 185                 if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY) {
 186                         fprintf(stderr, "unexpected key of type %u\n", key.type);
 187                         (*errors)++;
 188                         break;
 189                 }
 190                 if (key.objectid >= end) {
 191                         fprintf(stderr,
 192         "free space bitmap starts at %llu, beyond end of block group %llu-%llu\n",
 193                                 key.objectid, start, end);
 194                         (*errors)++;
 195                         break;
 196                 }
 197                 if (key.objectid + key.offset > end) {
 198                         fprintf(stderr,
 199         "free space bitmap ends at %llu, beyond end of block group %llu-%llu\n",
 200                                 key.objectid, start, end);
 201                         (*errors)++;
 202                         break;
 203                 }
 204
 205                 offset = key.objectid;
 206                 while (offset < key.objectid + key.offset) {
 207                         bit = free_space_test_bit(block_group, path, offset,
 208                                                   fs_info->sectorsize);
 209                         if (prev_bit == 0 && bit == 1) {
 210                                 extent_start = offset;
 211                         } else if (prev_bit == 1 && bit == 0) {
 212                                 add_new_free_space(block_group, fs_info, extent_start, offset);
 213                                 extent_count++;
 214                         }
 215                         prev_bit = bit;
 216                         offset += fs_info->sectorsize;
 217                 }
 218         }
 219
 220         if (prev_bit == 1) {
 221                 add_new_free_space(block_group, fs_info, extent_start, end);
 222                 extent_count++;
 223         }
 224
 225         if (extent_count != expected_extent_count) {
 226                 fprintf(stderr, "free space info recorded %u extents, counted %u\n",
 227                         expected_extent_count, extent_count);
 228                 (*errors)++;
 229         }
 230
 231         ret = 0;
 232 out:
 233         return ret;
 234 }
 235
 236 static int load_free_space_extents(struct btrfs_fs_info *fs_info,
 237                                    struct btrfs_block_group_cache *block_group,
 238                                    struct btrfs_path *path,
 239                                    u32 expected_extent_count,
 240                                    int *errors)
 241 {
 242         struct btrfs_root *root = fs_info->free_space_root;
 243         struct btrfs_key key, prev_key;
 244         int have_prev = 0;
 245         u64 start, end;
 246         u32 extent_count = 0;
 247         int ret;
 248
 249         start = block_group->key.objectid;
 250         end = block_group->key.objectid + block_group->key.offset;
 251
 252         while (1) {
 253                 ret = btrfs_next_item(root, path);
 254                 if (ret < 0)
 255                         goto out;
 256                 if (ret)
 257                         break;
 258
 259                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 260
 261                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
 262                         break;
 263
 264                 if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
 265                         fprintf(stderr, "unexpected key of type %u\n", key.type);
 266                         (*errors)++;
 267                         break;
 268                 }
 269                 if (key.objectid >= end) {
 270                         fprintf(stderr,
 271         "free space extent starts at %llu, beyond end of block group %llu-%llu\n",
 272                                 key.objectid, start, end);
 273                         (*errors)++;
 274                         break;
 275                 }
 276                 if (key.objectid + key.offset > end) {
 277                         fprintf(stderr,
 278         "free space extent ends at %llu, beyond end of block group %llu-%llu\n",
 279                                 key.objectid + key.offset, start, end);
 280                         (*errors)++;
 281                         break;
 282                 }
 283
 284                 if (have_prev) {
 285                         u64 cur_start = key.objectid;
 286                         u64 cur_end = cur_start + key.offset;
 287                         u64 prev_start = prev_key.objectid;
 288                         u64 prev_end = prev_start + prev_key.offset;
 289
 290                         if (cur_start < prev_end) {
 291                                 fprintf(stderr,
 292         "free space extent %llu-%llu overlaps with previous %llu-%llu\n",
 293                                         cur_start, cur_end,
 294                                         prev_start, prev_end);
 295                                 (*errors)++;
 296                         } else if (cur_start == prev_end) {
 297                                 fprintf(stderr,
 298         "free space extent %llu-%llu is unmerged with previous %llu-%llu\n",
 299                                         cur_start, cur_end,
 300                                         prev_start, prev_end);
 301                                 (*errors)++;
 302                         }
 303                 }
 304
 305                 add_new_free_space(block_group, fs_info, key.objectid, key.objectid + key.offset);
 306                 extent_count++;
 307
 308                 prev_key = key;
 309                 have_prev = 1;
 310         }
 311
 312         if (extent_count != expected_extent_count) {
 313                 fprintf(stderr, "free space info recorded %u extents, counted %u\n",
 314                         expected_extent_count, extent_count);
 315                 (*errors)++;
 316         }
 317
 318         ret = 0;
 319 out:
 320         return ret;
 321 }
 322
 323 int load_free_space_tree(struct btrfs_fs_info *fs_info,
 324                          struct btrfs_block_group_cache *block_group)
 325 {
 326         struct btrfs_free_space_info *info;
 327         struct btrfs_path *path;
 328         u32 extent_count, flags;
 329         int errors = 0;
 330         int ret;
 331
 332         path = btrfs_alloc_path();
 333         if (!path)
 334                 return -ENOMEM;
 335         path->reada = 1;
 336
 337         info = search_free_space_info(NULL, fs_info, block_group, path, 0);
 338         if (IS_ERR(info)) {
 339                 ret = PTR_ERR(info);
 340                 goto out;
 341         }
 342         extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
 343         flags = btrfs_free_space_flags(path->nodes[0], info);
 344
 345         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
 346                 ret = load_free_space_bitmaps(fs_info, block_group, path,
 347                                               extent_count, &errors);
 348         } else {
 349                 ret = load_free_space_extents(fs_info, block_group, path,
 350                                               extent_count, &errors);
 351         }
 352         if (ret)
 353                 goto out;
 354
 355         ret = 0;
 356 out:
 357         btrfs_free_path(path);
 358         return ret ? ret : errors;
 359 }