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 * lookup the root with the highest offset for a given objectid. The key we do 26 * find is copied into 'key'. If we find something return 0, otherwise 1, < 0 27 * on error. 28 */ 29 int btrfs_find_last_root(struct btrfs_root *root, u64 objectid, 30 struct btrfs_root_item *item, struct btrfs_key *key) 31 { 32 struct btrfs_path *path; 33 struct btrfs_key search_key; 34 struct btrfs_key found_key; 35 struct extent_buffer *l; 36 int ret; 37 int slot; 38 39 search_key.objectid = objectid; 40 search_key.type = BTRFS_ROOT_ITEM_KEY; 41 search_key.offset = (u64)-1; 42 43 path = btrfs_alloc_path(); 44 if (!path) 45 return -ENOMEM; 46 ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0); 47 if (ret < 0) 48 goto out; 49 50 BUG_ON(ret == 0); 51 if (path->slots[0] == 0) { 52 ret = 1; 53 goto out; 54 } 55 l = path->nodes[0]; 56 slot = path->slots[0] - 1; 57 btrfs_item_key_to_cpu(l, &found_key, slot); 58 if (found_key.objectid != objectid || 59 found_key.type != BTRFS_ROOT_ITEM_KEY) { 60 ret = 1; 61 goto out; 62 } 63 if (item) 64 read_extent_buffer(l, item, btrfs_item_ptr_offset(l, slot), 65 sizeof(*item)); 66 if (key) 67 memcpy(key, &found_key, sizeof(found_key)); 68 ret = 0; 69 out: 70 btrfs_free_path(path); 71 return ret; 72 } 73 74 void btrfs_set_root_node(struct btrfs_root_item *item, 75 struct extent_buffer *node) 76 { 77 btrfs_set_root_bytenr(item, node->start); 78 btrfs_set_root_level(item, btrfs_header_level(node)); 79 btrfs_set_root_generation(item, btrfs_header_generation(node)); 80 } 81 82 /* 83 * copy the data in 'item' into the btree 84 */ 85 int btrfs_update_root(struct btrfs_trans_handle *trans, struct btrfs_root 86 *root, struct btrfs_key *key, struct btrfs_root_item 87 *item) 88 { 89 struct btrfs_path *path; 90 struct extent_buffer *l; 91 int ret; 92 int slot; 93 unsigned long ptr; 94 95 path = btrfs_alloc_path(); 96 BUG_ON(!path); 97 ret = btrfs_search_slot(trans, root, key, path, 0, 1); 98 if (ret < 0) 99 goto out; 100 101 if (ret != 0) { 102 btrfs_print_leaf(root, path->nodes[0]); 103 printk(KERN_CRIT "unable to update root key %llu %u %llu\n", 104 (unsigned long long)key->objectid, key->type, 105 (unsigned long long)key->offset); 106 BUG_ON(1); 107 } 108 109 l = path->nodes[0]; 110 slot = path->slots[0]; 111 ptr = btrfs_item_ptr_offset(l, slot); 112 write_extent_buffer(l, item, ptr, sizeof(*item)); 113 btrfs_mark_buffer_dirty(path->nodes[0]); 114 out: 115 btrfs_free_path(path); 116 return ret; 117 } 118 119 int btrfs_insert_root(struct btrfs_trans_handle *trans, struct btrfs_root 120 *root, struct btrfs_key *key, struct btrfs_root_item 121 *item) 122 { 123 int ret; 124 ret = btrfs_insert_item(trans, root, key, item, sizeof(*item)); 125 return ret; 126 } 127 128 /* 129 * at mount time we want to find all the old transaction snapshots that were in 130 * the process of being deleted if we crashed. This is any root item with an 131 * offset lower than the latest root. They need to be queued for deletion to 132 * finish what was happening when we crashed. 133 */ 134 int btrfs_find_dead_roots(struct btrfs_root *root, u64 objectid) 135 { 136 struct btrfs_root *dead_root; 137 struct btrfs_root_item *ri; 138 struct btrfs_key key; 139 struct btrfs_key found_key; 140 struct btrfs_path *path; 141 int ret; 142 u32 nritems; 143 struct extent_buffer *leaf; 144 int slot; 145 146 key.objectid = objectid; 147 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY); 148 key.offset = 0; 149 path = btrfs_alloc_path(); 150 if (!path) 151 return -ENOMEM; 152 153 again: 154 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 155 if (ret < 0) 156 goto err; 157 while (1) { 158 leaf = path->nodes[0]; 159 nritems = btrfs_header_nritems(leaf); 160 slot = path->slots[0]; 161 if (slot >= nritems) { 162 ret = btrfs_next_leaf(root, path); 163 if (ret) 164 break; 165 leaf = path->nodes[0]; 166 nritems = btrfs_header_nritems(leaf); 167 slot = path->slots[0]; 168 } 169 btrfs_item_key_to_cpu(leaf, &key, slot); 170 if (btrfs_key_type(&key) != BTRFS_ROOT_ITEM_KEY) 171 goto next; 172 173 if (key.objectid < objectid) 174 goto next; 175 176 if (key.objectid > objectid) 177 break; 178 179 ri = btrfs_item_ptr(leaf, slot, struct btrfs_root_item); 180 if (btrfs_disk_root_refs(leaf, ri) != 0) 181 goto next; 182 183 memcpy(&found_key, &key, sizeof(key)); 184 key.offset++; 185 btrfs_release_path(path); 186 dead_root = 187 btrfs_read_fs_root_no_radix(root->fs_info->tree_root, 188 &found_key); 189 if (IS_ERR(dead_root)) { 190 ret = PTR_ERR(dead_root); 191 goto err; 192 } 193 194 ret = btrfs_add_dead_root(dead_root); 195 if (ret) 196 goto err; 197 goto again; 198 next: 199 slot++; 200 path->slots[0]++; 201 } 202 ret = 0; 203 err: 204 btrfs_free_path(path); 205 return ret; 206 } 207 208 int btrfs_find_orphan_roots(struct btrfs_root *tree_root) 209 { 210 struct extent_buffer *leaf; 211 struct btrfs_path *path; 212 struct btrfs_key key; 213 struct btrfs_key root_key; 214 struct btrfs_root *root; 215 int err = 0; 216 int ret; 217 218 path = btrfs_alloc_path(); 219 if (!path) 220 return -ENOMEM; 221 222 key.objectid = BTRFS_ORPHAN_OBJECTID; 223 key.type = BTRFS_ORPHAN_ITEM_KEY; 224 key.offset = 0; 225 226 root_key.type = BTRFS_ROOT_ITEM_KEY; 227 root_key.offset = (u64)-1; 228 229 while (1) { 230 ret = btrfs_search_slot(NULL, tree_root, &key, path, 0, 0); 231 if (ret < 0) { 232 err = ret; 233 break; 234 } 235 236 leaf = path->nodes[0]; 237 if (path->slots[0] >= btrfs_header_nritems(leaf)) { 238 ret = btrfs_next_leaf(tree_root, path); 239 if (ret < 0) 240 err = ret; 241 if (ret != 0) 242 break; 243 leaf = path->nodes[0]; 244 } 245 246 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]); 247 btrfs_release_path(path); 248 249 if (key.objectid != BTRFS_ORPHAN_OBJECTID || 250 key.type != BTRFS_ORPHAN_ITEM_KEY) 251 break; 252 253 root_key.objectid = key.offset; 254 key.offset++; 255 256 root = btrfs_read_fs_root_no_name(tree_root->fs_info, 257 &root_key); 258 if (!IS_ERR(root)) 259 continue; 260 261 ret = PTR_ERR(root); 262 if (ret != -ENOENT) { 263 err = ret; 264 break; 265 } 266 267 ret = btrfs_find_dead_roots(tree_root, root_key.objectid); 268 if (ret) { 269 err = ret; 270 break; 271 } 272 } 273 274 btrfs_free_path(path); 275 return err; 276 } 277 278 /* drop the root item for 'key' from 'root' */ 279 int btrfs_del_root(struct btrfs_trans_handle *trans, struct btrfs_root *root, 280 struct btrfs_key *key) 281 { 282 struct btrfs_path *path; 283 int ret; 284 struct btrfs_root_item *ri; 285 struct extent_buffer *leaf; 286 287 path = btrfs_alloc_path(); 288 if (!path) 289 return -ENOMEM; 290 ret = btrfs_search_slot(trans, root, key, path, -1, 1); 291 if (ret < 0) 292 goto out; 293 294 BUG_ON(ret != 0); 295 leaf = path->nodes[0]; 296 ri = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_item); 297 298 ret = btrfs_del_item(trans, root, path); 299 out: 300 btrfs_free_path(path); 301 return ret; 302 } 303 304 int btrfs_del_root_ref(struct btrfs_trans_handle *trans, 305 struct btrfs_root *tree_root, 306 u64 root_id, u64 ref_id, u64 dirid, u64 *sequence, 307 const char *name, int name_len) 308 309 { 310 struct btrfs_path *path; 311 struct btrfs_root_ref *ref; 312 struct extent_buffer *leaf; 313 struct btrfs_key key; 314 unsigned long ptr; 315 int err = 0; 316 int ret; 317 318 path = btrfs_alloc_path(); 319 if (!path) 320 return -ENOMEM; 321 322 key.objectid = root_id; 323 key.type = BTRFS_ROOT_BACKREF_KEY; 324 key.offset = ref_id; 325 again: 326 ret = btrfs_search_slot(trans, tree_root, &key, path, -1, 1); 327 BUG_ON(ret < 0); 328 if (ret == 0) { 329 leaf = path->nodes[0]; 330 ref = btrfs_item_ptr(leaf, path->slots[0], 331 struct btrfs_root_ref); 332 333 WARN_ON(btrfs_root_ref_dirid(leaf, ref) != dirid); 334 WARN_ON(btrfs_root_ref_name_len(leaf, ref) != name_len); 335 ptr = (unsigned long)(ref + 1); 336 WARN_ON(memcmp_extent_buffer(leaf, name, ptr, name_len)); 337 *sequence = btrfs_root_ref_sequence(leaf, ref); 338 339 ret = btrfs_del_item(trans, tree_root, path); 340 if (ret) { 341 err = ret; 342 goto out; 343 } 344 } else 345 err = -ENOENT; 346 347 if (key.type == BTRFS_ROOT_BACKREF_KEY) { 348 btrfs_release_path(path); 349 key.objectid = ref_id; 350 key.type = BTRFS_ROOT_REF_KEY; 351 key.offset = root_id; 352 goto again; 353 } 354 355 out: 356 btrfs_free_path(path); 357 return err; 358 } 359 360 int btrfs_find_root_ref(struct btrfs_root *tree_root, 361 struct btrfs_path *path, 362 u64 root_id, u64 ref_id) 363 { 364 struct btrfs_key key; 365 int ret; 366 367 key.objectid = root_id; 368 key.type = BTRFS_ROOT_REF_KEY; 369 key.offset = ref_id; 370 371 ret = btrfs_search_slot(NULL, tree_root, &key, path, 0, 0); 372 return ret; 373 } 374 375 /* 376 * add a btrfs_root_ref item. type is either BTRFS_ROOT_REF_KEY 377 * or BTRFS_ROOT_BACKREF_KEY. 378 * 379 * The dirid, sequence, name and name_len refer to the directory entry 380 * that is referencing the root. 381 * 382 * For a forward ref, the root_id is the id of the tree referencing 383 * the root and ref_id is the id of the subvol or snapshot. 384 * 385 * For a back ref the root_id is the id of the subvol or snapshot and 386 * ref_id is the id of the tree referencing it. 387 */ 388 int btrfs_add_root_ref(struct btrfs_trans_handle *trans, 389 struct btrfs_root *tree_root, 390 u64 root_id, u64 ref_id, u64 dirid, u64 sequence, 391 const char *name, int name_len) 392 { 393 struct btrfs_key key; 394 int ret; 395 struct btrfs_path *path; 396 struct btrfs_root_ref *ref; 397 struct extent_buffer *leaf; 398 unsigned long ptr; 399 400 path = btrfs_alloc_path(); 401 if (!path) 402 return -ENOMEM; 403 404 key.objectid = root_id; 405 key.type = BTRFS_ROOT_BACKREF_KEY; 406 key.offset = ref_id; 407 again: 408 ret = btrfs_insert_empty_item(trans, tree_root, path, &key, 409 sizeof(*ref) + name_len); 410 BUG_ON(ret); 411 412 leaf = path->nodes[0]; 413 ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_ref); 414 btrfs_set_root_ref_dirid(leaf, ref, dirid); 415 btrfs_set_root_ref_sequence(leaf, ref, sequence); 416 btrfs_set_root_ref_name_len(leaf, ref, name_len); 417 ptr = (unsigned long)(ref + 1); 418 write_extent_buffer(leaf, name, ptr, name_len); 419 btrfs_mark_buffer_dirty(leaf); 420 421 if (key.type == BTRFS_ROOT_BACKREF_KEY) { 422 btrfs_release_path(path); 423 key.objectid = ref_id; 424 key.type = BTRFS_ROOT_REF_KEY; 425 key.offset = root_id; 426 goto again; 427 } 428 429 btrfs_free_path(path); 430 return 0; 431 } 432 433 /* 434 * Old btrfs forgets to init root_item->flags and root_item->byte_limit 435 * for subvolumes. To work around this problem, we steal a bit from 436 * root_item->inode_item->flags, and use it to indicate if those fields 437 * have been properly initialized. 438 */ 439 void btrfs_check_and_init_root_item(struct btrfs_root_item *root_item) 440 { 441 u64 inode_flags = le64_to_cpu(root_item->inode.flags); 442 443 if (!(inode_flags & BTRFS_INODE_ROOT_ITEM_INIT)) { 444 inode_flags |= BTRFS_INODE_ROOT_ITEM_INIT; 445 root_item->inode.flags = cpu_to_le64(inode_flags); 446 root_item->flags = 0; 447 root_item->byte_limit = 0; 448 } 449 } 450