fs/btrfs/root-tree.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  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 "transaction.h"
  21 #include "disk-io.h"
  22 #include "print-tree.h"
  23
  24 /*
  25  *  search forward for a root, starting with objectid 'search_start'
  26  *  if a root key is found, the objectid we find is filled into 'found_objectid'
  27  *  and 0 is returned.  < 0 is returned on error, 1 if there is nothing
  28  *  left in the tree.
  29  */
  30 int btrfs_search_root(struct btrfs_root *root, u64 search_start,
  31                       u64 *found_objectid)
  32 {
  33         struct btrfs_path *path;
  34         struct btrfs_key search_key;
  35         int ret;
  36
  37         root = root->fs_info->tree_root;
  38         search_key.objectid = search_start;
  39         search_key.type = (u8)-1;
  40         search_key.offset = (u64)-1;
  41
  42         path = btrfs_alloc_path();
  43         BUG_ON(!path);
  44 again:
  45         ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
  46         if (ret < 0)
  47                 goto out;
  48         if (ret == 0) {
  49                 ret = 1;
  50                 goto out;
  51         }
  52         if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
  53                 ret = btrfs_next_leaf(root, path);
  54                 if (ret)
  55                         goto out;
  56         }
  57         btrfs_item_key_to_cpu(path->nodes[0], &search_key, path->slots[0]);
  58         if (search_key.type != BTRFS_ROOT_ITEM_KEY) {
  59                 search_key.offset++;
  60                 btrfs_release_path(root, path);
  61                 goto again;
  62         }
  63         ret = 0;
  64         *found_objectid = search_key.objectid;
  65
  66 out:
  67         btrfs_free_path(path);
  68         return ret;
  69 }
  70
  71 /*
  72  * lookup the root with the highest offset for a given objectid.  The key we do
  73  * find is copied into 'key'.  If we find something return 0, otherwise 1, < 0
  74  * on error.
  75  */
  76 int btrfs_find_last_root(struct btrfs_root *root, u64 objectid,
  77                         struct btrfs_root_item *item, struct btrfs_key *key)
  78 {
  79         struct btrfs_path *path;
  80         struct btrfs_key search_key;
  81         struct btrfs_key found_key;
  82         struct extent_buffer *l;
  83         int ret;
  84         int slot;
  85
  86         search_key.objectid = objectid;
  87         search_key.type = (u8)-1;
  88         search_key.offset = (u64)-1;
  89
  90         path = btrfs_alloc_path();
  91         BUG_ON(!path);
  92         ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
  93         if (ret < 0)
  94                 goto out;
  95
  96         BUG_ON(ret == 0);
  97         l = path->nodes[0];
  98         BUG_ON(path->slots[0] == 0);
  99         slot = path->slots[0] - 1;
 100         btrfs_item_key_to_cpu(l, &found_key, slot);
 101         if (found_key.objectid != objectid) {
 102                 ret = 1;
 103                 goto out;
 104         }
 105         read_extent_buffer(l, item, btrfs_item_ptr_offset(l, slot),
 106                            sizeof(*item));
 107         memcpy(key, &found_key, sizeof(found_key));
 108         ret = 0;
 109 out:
 110         btrfs_free_path(path);
 111         return ret;
 112 }
 113
 114 /*
 115  * copy the data in 'item' into the btree
 116  */
 117 int btrfs_update_root(struct btrfs_trans_handle *trans, struct btrfs_root
 118                       *root, struct btrfs_key *key, struct btrfs_root_item
 119                       *item)
 120 {
 121         struct btrfs_path *path;
 122         struct extent_buffer *l;
 123         int ret;
 124         int slot;
 125         unsigned long ptr;
 126
 127         path = btrfs_alloc_path();
 128         BUG_ON(!path);
 129         ret = btrfs_search_slot(trans, root, key, path, 0, 1);
 130         if (ret < 0)
 131                 goto out;
 132
 133         if (ret != 0) {
 134                 btrfs_print_leaf(root, path->nodes[0]);
 135                 printk("unable to update root key %Lu %u %Lu\n",
 136                        key->objectid, key->type, key->offset);
 137                 BUG_ON(1);
 138         }
 139
 140         l = path->nodes[0];
 141         slot = path->slots[0];
 142         ptr = btrfs_item_ptr_offset(l, slot);
 143         write_extent_buffer(l, item, ptr, sizeof(*item));
 144         btrfs_mark_buffer_dirty(path->nodes[0]);
 145 out:
 146         btrfs_release_path(root, path);
 147         btrfs_free_path(path);
 148         return ret;
 149 }
 150
 151 int btrfs_insert_root(struct btrfs_trans_handle *trans, struct btrfs_root
 152                       *root, struct btrfs_key *key, struct btrfs_root_item
 153                       *item)
 154 {
 155         int ret;
 156         ret = btrfs_insert_item(trans, root, key, item, sizeof(*item));
 157         return ret;
 158 }
 159
 160 /*
 161  * at mount time we want to find all the old transaction snapshots that were in
 162  * the process of being deleted if we crashed.  This is any root item with an offset
 163  * lower than the latest root.  They need to be queued for deletion to finish
 164  * what was happening when we crashed.
 165  */
 166 int btrfs_find_dead_roots(struct btrfs_root *root, u64 objectid,
 167                           struct btrfs_root *latest)
 168 {
 169         struct btrfs_root *dead_root;
 170         struct btrfs_item *item;
 171         struct btrfs_root_item *ri;
 172         struct btrfs_key key;
 173         struct btrfs_key found_key;
 174         struct btrfs_path *path;
 175         int ret;
 176         u32 nritems;
 177         struct extent_buffer *leaf;
 178         int slot;
 179
 180         key.objectid = objectid;
 181         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
 182         key.offset = 0;
 183         path = btrfs_alloc_path();
 184         if (!path)
 185                 return -ENOMEM;
 186
 187 again:
 188         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 189         if (ret < 0)
 190                 goto err;
 191         while(1) {
 192                 leaf = path->nodes[0];
 193                 nritems = btrfs_header_nritems(leaf);
 194                 slot = path->slots[0];
 195                 if (slot >= nritems) {
 196                         ret = btrfs_next_leaf(root, path);
 197                         if (ret)
 198                                 break;
 199                         leaf = path->nodes[0];
 200                         nritems = btrfs_header_nritems(leaf);
 201                         slot = path->slots[0];
 202                 }
 203                 item = btrfs_item_nr(leaf, slot);
 204                 btrfs_item_key_to_cpu(leaf, &key, slot);
 205                 if (btrfs_key_type(&key) != BTRFS_ROOT_ITEM_KEY)
 206                         goto next;
 207
 208                 if (key.objectid < objectid)
 209                         goto next;
 210
 211                 if (key.objectid > objectid)
 212                         break;
 213
 214                 ri = btrfs_item_ptr(leaf, slot, struct btrfs_root_item);
 215                 if (btrfs_disk_root_refs(leaf, ri) != 0)
 216                         goto next;
 217
 218                 memcpy(&found_key, &key, sizeof(key));
 219                 key.offset++;
 220                 btrfs_release_path(root, path);
 221                 dead_root =
 222                         btrfs_read_fs_root_no_radix(root->fs_info->tree_root,
 223                                                     &found_key);
 224                 if (IS_ERR(dead_root)) {
 225                         ret = PTR_ERR(dead_root);
 226                         goto err;
 227                 }
 228
 229                 if (objectid == BTRFS_TREE_RELOC_OBJECTID)
 230                         ret = btrfs_add_dead_reloc_root(dead_root);
 231                 else
 232                         ret = btrfs_add_dead_root(dead_root, latest);
 233                 if (ret)
 234                         goto err;
 235                 goto again;
 236 next:
 237                 slot++;
 238                 path->slots[0]++;
 239         }
 240         ret = 0;
 241 err:
 242         btrfs_free_path(path);
 243         return ret;
 244 }
 245
 246 /* drop the root item for 'key' from 'root' */
 247 int btrfs_del_root(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 248                    struct btrfs_key *key)
 249 {
 250         struct btrfs_path *path;
 251         int ret;
 252         u32 refs;
 253         struct btrfs_root_item *ri;
 254         struct extent_buffer *leaf;
 255
 256         path = btrfs_alloc_path();
 257         BUG_ON(!path);
 258         ret = btrfs_search_slot(trans, root, key, path, -1, 1);
 259         if (ret < 0)
 260                 goto out;
 261         if (ret) {
 262 btrfs_print_leaf(root, path->nodes[0]);
 263 printk("failed to del %Lu %u %Lu\n", key->objectid, key->type, key->offset);
 264
 265         }
 266         BUG_ON(ret != 0);
 267         leaf = path->nodes[0];
 268         ri = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_item);
 269
 270         refs = btrfs_disk_root_refs(leaf, ri);
 271         BUG_ON(refs != 0);
 272         ret = btrfs_del_item(trans, root, path);
 273 out:
 274         btrfs_release_path(root, path);
 275         btrfs_free_path(path);
 276         return ret;
 277 }