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