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 "disk-io.h" 21 #include "hash.h" 22 #include "transaction.h" 23 #include "print-tree.h" 24 25 static int find_name_in_backref(struct btrfs_path *path, const char *name, 26 int name_len, struct btrfs_inode_ref **ref_ret) 27 { 28 struct extent_buffer *leaf; 29 struct btrfs_inode_ref *ref; 30 unsigned long ptr; 31 unsigned long name_ptr; 32 u32 item_size; 33 u32 cur_offset = 0; 34 int len; 35 36 leaf = path->nodes[0]; 37 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 38 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 39 while (cur_offset < item_size) { 40 ref = (struct btrfs_inode_ref *)(ptr + cur_offset); 41 len = btrfs_inode_ref_name_len(leaf, ref); 42 name_ptr = (unsigned long)(ref + 1); 43 cur_offset += len + sizeof(*ref); 44 if (len != name_len) 45 continue; 46 if (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) { 47 *ref_ret = ref; 48 return 1; 49 } 50 } 51 return 0; 52 } 53 54 int btrfs_find_name_in_ext_backref(struct btrfs_path *path, u64 ref_objectid, 55 const char *name, int name_len, 56 struct btrfs_inode_extref **extref_ret) 57 { 58 struct extent_buffer *leaf; 59 struct btrfs_inode_extref *extref; 60 unsigned long ptr; 61 unsigned long name_ptr; 62 u32 item_size; 63 u32 cur_offset = 0; 64 int ref_name_len; 65 66 leaf = path->nodes[0]; 67 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 68 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); 69 70 /* 71 * Search all extended backrefs in this item. We're only 72 * looking through any collisions so most of the time this is 73 * just going to compare against one buffer. If all is well, 74 * we'll return success and the inode ref object. 75 */ 76 while (cur_offset < item_size) { 77 extref = (struct btrfs_inode_extref *) (ptr + cur_offset); 78 name_ptr = (unsigned long)(&extref->name); 79 ref_name_len = btrfs_inode_extref_name_len(leaf, extref); 80 81 if (ref_name_len == name_len && 82 btrfs_inode_extref_parent(leaf, extref) == ref_objectid && 83 (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)) { 84 if (extref_ret) 85 *extref_ret = extref; 86 return 1; 87 } 88 89 cur_offset += ref_name_len + sizeof(*extref); 90 } 91 return 0; 92 } 93 94 static struct btrfs_inode_ref * 95 btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans, 96 struct btrfs_root *root, 97 struct btrfs_path *path, 98 const char *name, int name_len, 99 u64 inode_objectid, u64 ref_objectid, int ins_len, 100 int cow) 101 { 102 int ret; 103 struct btrfs_key key; 104 struct btrfs_inode_ref *ref; 105 106 key.objectid = inode_objectid; 107 key.type = BTRFS_INODE_REF_KEY; 108 key.offset = ref_objectid; 109 110 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 111 if (ret < 0) 112 return ERR_PTR(ret); 113 if (ret > 0) 114 return NULL; 115 if (!find_name_in_backref(path, name, name_len, &ref)) 116 return NULL; 117 return ref; 118 } 119 120 /* Returns NULL if no extref found */ 121 struct btrfs_inode_extref * 122 btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans, 123 struct btrfs_root *root, 124 struct btrfs_path *path, 125 const char *name, int name_len, 126 u64 inode_objectid, u64 ref_objectid, int ins_len, 127 int cow) 128 { 129 int ret; 130 struct btrfs_key key; 131 struct btrfs_inode_extref *extref; 132 133 key.objectid = inode_objectid; 134 key.type = BTRFS_INODE_EXTREF_KEY; 135 key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 136 137 ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 138 if (ret < 0) 139 return ERR_PTR(ret); 140 if (ret > 0) 141 return NULL; 142 if (!btrfs_find_name_in_ext_backref(path, ref_objectid, name, name_len, &extref)) 143 return NULL; 144 return extref; 145 } 146 147 int btrfs_get_inode_ref_index(struct btrfs_trans_handle *trans, 148 struct btrfs_root *root, 149 struct btrfs_path *path, 150 const char *name, int name_len, 151 u64 inode_objectid, u64 ref_objectid, int mod, 152 u64 *ret_index) 153 { 154 struct btrfs_inode_ref *ref; 155 struct btrfs_inode_extref *extref; 156 int ins_len = mod < 0 ? -1 : 0; 157 int cow = mod != 0; 158 159 ref = btrfs_lookup_inode_ref(trans, root, path, name, name_len, 160 inode_objectid, ref_objectid, ins_len, 161 cow); 162 if (IS_ERR(ref)) 163 return PTR_ERR(ref); 164 165 if (ref != NULL) { 166 *ret_index = btrfs_inode_ref_index(path->nodes[0], ref); 167 return 0; 168 } 169 170 btrfs_release_path(path); 171 172 extref = btrfs_lookup_inode_extref(trans, root, path, name, 173 name_len, inode_objectid, 174 ref_objectid, ins_len, cow); 175 if (IS_ERR(extref)) 176 return PTR_ERR(extref); 177 178 if (extref) { 179 *ret_index = btrfs_inode_extref_index(path->nodes[0], extref); 180 return 0; 181 } 182 183 return -ENOENT; 184 } 185 186 static int btrfs_del_inode_extref(struct btrfs_trans_handle *trans, 187 struct btrfs_root *root, 188 const char *name, int name_len, 189 u64 inode_objectid, u64 ref_objectid, 190 u64 *index) 191 { 192 struct btrfs_path *path; 193 struct btrfs_key key; 194 struct btrfs_inode_extref *extref; 195 struct extent_buffer *leaf; 196 int ret; 197 int del_len = name_len + sizeof(*extref); 198 unsigned long ptr; 199 unsigned long item_start; 200 u32 item_size; 201 202 key.objectid = inode_objectid; 203 btrfs_set_key_type(&key, BTRFS_INODE_EXTREF_KEY); 204 key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 205 206 path = btrfs_alloc_path(); 207 if (!path) 208 return -ENOMEM; 209 210 path->leave_spinning = 1; 211 212 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 213 if (ret > 0) 214 ret = -ENOENT; 215 if (ret < 0) 216 goto out; 217 218 /* 219 * Sanity check - did we find the right item for this name? 220 * This should always succeed so error here will make the FS 221 * readonly. 222 */ 223 if (!btrfs_find_name_in_ext_backref(path, ref_objectid, 224 name, name_len, &extref)) { 225 btrfs_std_error(root->fs_info, -ENOENT); 226 ret = -EROFS; 227 goto out; 228 } 229 230 leaf = path->nodes[0]; 231 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 232 if (index) 233 *index = btrfs_inode_extref_index(leaf, extref); 234 235 if (del_len == item_size) { 236 /* 237 * Common case only one ref in the item, remove the 238 * whole item. 239 */ 240 ret = btrfs_del_item(trans, root, path); 241 goto out; 242 } 243 244 ptr = (unsigned long)extref; 245 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 246 247 memmove_extent_buffer(leaf, ptr, ptr + del_len, 248 item_size - (ptr + del_len - item_start)); 249 250 btrfs_truncate_item(root, path, item_size - del_len, 1); 251 252 out: 253 btrfs_free_path(path); 254 255 return ret; 256 } 257 258 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, 259 struct btrfs_root *root, 260 const char *name, int name_len, 261 u64 inode_objectid, u64 ref_objectid, u64 *index) 262 { 263 struct btrfs_path *path; 264 struct btrfs_key key; 265 struct btrfs_inode_ref *ref; 266 struct extent_buffer *leaf; 267 unsigned long ptr; 268 unsigned long item_start; 269 u32 item_size; 270 u32 sub_item_len; 271 int ret; 272 int search_ext_refs = 0; 273 int del_len = name_len + sizeof(*ref); 274 275 key.objectid = inode_objectid; 276 key.offset = ref_objectid; 277 btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY); 278 279 path = btrfs_alloc_path(); 280 if (!path) 281 return -ENOMEM; 282 283 path->leave_spinning = 1; 284 285 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 286 if (ret > 0) { 287 ret = -ENOENT; 288 search_ext_refs = 1; 289 goto out; 290 } else if (ret < 0) { 291 goto out; 292 } 293 if (!find_name_in_backref(path, name, name_len, &ref)) { 294 ret = -ENOENT; 295 search_ext_refs = 1; 296 goto out; 297 } 298 leaf = path->nodes[0]; 299 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 300 301 if (index) 302 *index = btrfs_inode_ref_index(leaf, ref); 303 304 if (del_len == item_size) { 305 ret = btrfs_del_item(trans, root, path); 306 goto out; 307 } 308 ptr = (unsigned long)ref; 309 sub_item_len = name_len + sizeof(*ref); 310 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 311 memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, 312 item_size - (ptr + sub_item_len - item_start)); 313 btrfs_truncate_item(root, path, item_size - sub_item_len, 1); 314 out: 315 btrfs_free_path(path); 316 317 if (search_ext_refs) { 318 /* 319 * No refs were found, or we could not find the 320 * name in our ref array. Find and remove the extended 321 * inode ref then. 322 */ 323 return btrfs_del_inode_extref(trans, root, name, name_len, 324 inode_objectid, ref_objectid, index); 325 } 326 327 return ret; 328 } 329 330 /* 331 * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree. 332 * 333 * The caller must have checked against BTRFS_LINK_MAX already. 334 */ 335 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans, 336 struct btrfs_root *root, 337 const char *name, int name_len, 338 u64 inode_objectid, u64 ref_objectid, u64 index) 339 { 340 struct btrfs_inode_extref *extref; 341 int ret; 342 int ins_len = name_len + sizeof(*extref); 343 unsigned long ptr; 344 struct btrfs_path *path; 345 struct btrfs_key key; 346 struct extent_buffer *leaf; 347 struct btrfs_item *item; 348 349 key.objectid = inode_objectid; 350 key.type = BTRFS_INODE_EXTREF_KEY; 351 key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 352 353 path = btrfs_alloc_path(); 354 if (!path) 355 return -ENOMEM; 356 357 path->leave_spinning = 1; 358 ret = btrfs_insert_empty_item(trans, root, path, &key, 359 ins_len); 360 if (ret == -EEXIST) { 361 if (btrfs_find_name_in_ext_backref(path, ref_objectid, 362 name, name_len, NULL)) 363 goto out; 364 365 btrfs_extend_item(root, path, ins_len); 366 ret = 0; 367 } 368 if (ret < 0) 369 goto out; 370 371 leaf = path->nodes[0]; 372 item = btrfs_item_nr(leaf, path->slots[0]); 373 ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char); 374 ptr += btrfs_item_size(leaf, item) - ins_len; 375 extref = (struct btrfs_inode_extref *)ptr; 376 377 btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len); 378 btrfs_set_inode_extref_index(path->nodes[0], extref, index); 379 btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid); 380 381 ptr = (unsigned long)&extref->name; 382 write_extent_buffer(path->nodes[0], name, ptr, name_len); 383 btrfs_mark_buffer_dirty(path->nodes[0]); 384 385 out: 386 btrfs_free_path(path); 387 return ret; 388 } 389 390 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */ 391 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans, 392 struct btrfs_root *root, 393 const char *name, int name_len, 394 u64 inode_objectid, u64 ref_objectid, u64 index) 395 { 396 struct btrfs_path *path; 397 struct btrfs_key key; 398 struct btrfs_inode_ref *ref; 399 unsigned long ptr; 400 int ret; 401 int ins_len = name_len + sizeof(*ref); 402 403 key.objectid = inode_objectid; 404 key.offset = ref_objectid; 405 btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY); 406 407 path = btrfs_alloc_path(); 408 if (!path) 409 return -ENOMEM; 410 411 path->leave_spinning = 1; 412 ret = btrfs_insert_empty_item(trans, root, path, &key, 413 ins_len); 414 if (ret == -EEXIST) { 415 u32 old_size; 416 417 if (find_name_in_backref(path, name, name_len, &ref)) 418 goto out; 419 420 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]); 421 btrfs_extend_item(root, path, ins_len); 422 ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 423 struct btrfs_inode_ref); 424 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size); 425 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 426 btrfs_set_inode_ref_index(path->nodes[0], ref, index); 427 ptr = (unsigned long)(ref + 1); 428 ret = 0; 429 } else if (ret < 0) { 430 if (ret == -EOVERFLOW) 431 ret = -EMLINK; 432 goto out; 433 } else { 434 ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 435 struct btrfs_inode_ref); 436 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 437 btrfs_set_inode_ref_index(path->nodes[0], ref, index); 438 ptr = (unsigned long)(ref + 1); 439 } 440 write_extent_buffer(path->nodes[0], name, ptr, name_len); 441 btrfs_mark_buffer_dirty(path->nodes[0]); 442 443 out: 444 btrfs_free_path(path); 445 446 if (ret == -EMLINK) { 447 struct btrfs_super_block *disk_super = root->fs_info->super_copy; 448 /* We ran out of space in the ref array. Need to 449 * add an extended ref. */ 450 if (btrfs_super_incompat_flags(disk_super) 451 & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) 452 ret = btrfs_insert_inode_extref(trans, root, name, 453 name_len, 454 inode_objectid, 455 ref_objectid, index); 456 } 457 458 return ret; 459 } 460 461 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans, 462 struct btrfs_root *root, 463 struct btrfs_path *path, u64 objectid) 464 { 465 struct btrfs_key key; 466 int ret; 467 key.objectid = objectid; 468 btrfs_set_key_type(&key, BTRFS_INODE_ITEM_KEY); 469 key.offset = 0; 470 471 ret = btrfs_insert_empty_item(trans, root, path, &key, 472 sizeof(struct btrfs_inode_item)); 473 return ret; 474 } 475 476 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root 477 *root, struct btrfs_path *path, 478 struct btrfs_key *location, int mod) 479 { 480 int ins_len = mod < 0 ? -1 : 0; 481 int cow = mod != 0; 482 int ret; 483 int slot; 484 struct extent_buffer *leaf; 485 struct btrfs_key found_key; 486 487 ret = btrfs_search_slot(trans, root, location, path, ins_len, cow); 488 if (ret > 0 && btrfs_key_type(location) == BTRFS_ROOT_ITEM_KEY && 489 location->offset == (u64)-1 && path->slots[0] != 0) { 490 slot = path->slots[0] - 1; 491 leaf = path->nodes[0]; 492 btrfs_item_key_to_cpu(leaf, &found_key, slot); 493 if (found_key.objectid == location->objectid && 494 btrfs_key_type(&found_key) == btrfs_key_type(location)) { 495 path->slots[0]--; 496 return 0; 497 } 498 } 499 return ret; 500 } 501