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 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, u64 *index) 190 { 191 struct btrfs_path *path; 192 struct btrfs_key key; 193 struct btrfs_inode_extref *extref; 194 struct extent_buffer *leaf; 195 int ret; 196 int del_len = name_len + sizeof(*extref); 197 unsigned long ptr; 198 unsigned long item_start; 199 u32 item_size; 200 201 key.objectid = inode_objectid; 202 btrfs_set_key_type(&key, BTRFS_INODE_EXTREF_KEY); 203 key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 204 205 path = btrfs_alloc_path(); 206 if (!path) 207 return -ENOMEM; 208 209 path->leave_spinning = 1; 210 211 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 212 if (ret > 0) 213 ret = -ENOENT; 214 if (ret < 0) 215 goto out; 216 217 /* 218 * Sanity check - did we find the right item for this name? 219 * This should always succeed so error here will make the FS 220 * readonly. 221 */ 222 if (!btrfs_find_name_in_ext_backref(path, ref_objectid, 223 name, name_len, &extref)) { 224 btrfs_std_error(root->fs_info, -ENOENT); 225 ret = -EROFS; 226 goto out; 227 } 228 229 leaf = path->nodes[0]; 230 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 231 if (index) 232 *index = btrfs_inode_extref_index(leaf, extref); 233 234 if (del_len == item_size) { 235 /* 236 * Common case only one ref in the item, remove the 237 * whole item. 238 */ 239 ret = btrfs_del_item(trans, root, path); 240 goto out; 241 } 242 243 ptr = (unsigned long)extref; 244 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 245 246 memmove_extent_buffer(leaf, ptr, ptr + del_len, 247 item_size - (ptr + del_len - item_start)); 248 249 btrfs_truncate_item(trans, root, path, item_size - del_len, 1); 250 251 out: 252 btrfs_free_path(path); 253 254 return ret; 255 } 256 257 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, 258 struct btrfs_root *root, 259 const char *name, int name_len, 260 u64 inode_objectid, u64 ref_objectid, u64 *index) 261 { 262 struct btrfs_path *path; 263 struct btrfs_key key; 264 struct btrfs_inode_ref *ref; 265 struct extent_buffer *leaf; 266 unsigned long ptr; 267 unsigned long item_start; 268 u32 item_size; 269 u32 sub_item_len; 270 int ret; 271 int search_ext_refs = 0; 272 int del_len = name_len + sizeof(*ref); 273 274 key.objectid = inode_objectid; 275 key.offset = ref_objectid; 276 btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY); 277 278 path = btrfs_alloc_path(); 279 if (!path) 280 return -ENOMEM; 281 282 path->leave_spinning = 1; 283 284 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 285 if (ret > 0) { 286 ret = -ENOENT; 287 search_ext_refs = 1; 288 goto out; 289 } else if (ret < 0) { 290 goto out; 291 } 292 if (!find_name_in_backref(path, name, name_len, &ref)) { 293 ret = -ENOENT; 294 search_ext_refs = 1; 295 goto out; 296 } 297 leaf = path->nodes[0]; 298 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 299 300 if (index) 301 *index = btrfs_inode_ref_index(leaf, ref); 302 303 if (del_len == item_size) { 304 ret = btrfs_del_item(trans, root, path); 305 goto out; 306 } 307 ptr = (unsigned long)ref; 308 sub_item_len = name_len + sizeof(*ref); 309 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 310 memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, 311 item_size - (ptr + sub_item_len - item_start)); 312 btrfs_truncate_item(trans, root, path, item_size - sub_item_len, 1); 313 out: 314 btrfs_free_path(path); 315 316 if (search_ext_refs) { 317 /* 318 * No refs were found, or we could not find the 319 * name in our ref array. Find and remove the extended 320 * inode ref then. 321 */ 322 return btrfs_del_inode_extref(trans, root, name, name_len, 323 inode_objectid, ref_objectid, index); 324 } 325 326 return ret; 327 } 328 329 /* 330 * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree. 331 * 332 * The caller must have checked against BTRFS_LINK_MAX already. 333 */ 334 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans, 335 struct btrfs_root *root, 336 const char *name, int name_len, 337 u64 inode_objectid, u64 ref_objectid, u64 index) 338 { 339 struct btrfs_inode_extref *extref; 340 int ret; 341 int ins_len = name_len + sizeof(*extref); 342 unsigned long ptr; 343 struct btrfs_path *path; 344 struct btrfs_key key; 345 struct extent_buffer *leaf; 346 struct btrfs_item *item; 347 348 key.objectid = inode_objectid; 349 key.type = BTRFS_INODE_EXTREF_KEY; 350 key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 351 352 path = btrfs_alloc_path(); 353 if (!path) 354 return -ENOMEM; 355 356 path->leave_spinning = 1; 357 ret = btrfs_insert_empty_item(trans, root, path, &key, 358 ins_len); 359 if (ret == -EEXIST) { 360 if (btrfs_find_name_in_ext_backref(path, ref_objectid, 361 name, name_len, NULL)) 362 goto out; 363 364 btrfs_extend_item(trans, root, path, ins_len); 365 ret = 0; 366 } 367 if (ret < 0) 368 goto out; 369 370 leaf = path->nodes[0]; 371 item = btrfs_item_nr(leaf, path->slots[0]); 372 ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char); 373 ptr += btrfs_item_size(leaf, item) - ins_len; 374 extref = (struct btrfs_inode_extref *)ptr; 375 376 btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len); 377 btrfs_set_inode_extref_index(path->nodes[0], extref, index); 378 btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid); 379 380 ptr = (unsigned long)&extref->name; 381 write_extent_buffer(path->nodes[0], name, ptr, name_len); 382 btrfs_mark_buffer_dirty(path->nodes[0]); 383 384 out: 385 btrfs_free_path(path); 386 return ret; 387 } 388 389 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */ 390 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans, 391 struct btrfs_root *root, 392 const char *name, int name_len, 393 u64 inode_objectid, u64 ref_objectid, u64 index) 394 { 395 struct btrfs_path *path; 396 struct btrfs_key key; 397 struct btrfs_inode_ref *ref; 398 unsigned long ptr; 399 int ret; 400 int ins_len = name_len + sizeof(*ref); 401 402 key.objectid = inode_objectid; 403 key.offset = ref_objectid; 404 btrfs_set_key_type(&key, BTRFS_INODE_REF_KEY); 405 406 path = btrfs_alloc_path(); 407 if (!path) 408 return -ENOMEM; 409 410 path->leave_spinning = 1; 411 ret = btrfs_insert_empty_item(trans, root, path, &key, 412 ins_len); 413 if (ret == -EEXIST) { 414 u32 old_size; 415 416 if (find_name_in_backref(path, name, name_len, &ref)) 417 goto out; 418 419 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]); 420 btrfs_extend_item(trans, root, path, ins_len); 421 ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 422 struct btrfs_inode_ref); 423 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size); 424 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 425 btrfs_set_inode_ref_index(path->nodes[0], ref, index); 426 ptr = (unsigned long)(ref + 1); 427 ret = 0; 428 } else if (ret < 0) { 429 if (ret == -EOVERFLOW) 430 ret = -EMLINK; 431 goto out; 432 } else { 433 ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 434 struct btrfs_inode_ref); 435 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 436 btrfs_set_inode_ref_index(path->nodes[0], ref, index); 437 ptr = (unsigned long)(ref + 1); 438 } 439 write_extent_buffer(path->nodes[0], name, ptr, name_len); 440 btrfs_mark_buffer_dirty(path->nodes[0]); 441 442 out: 443 btrfs_free_path(path); 444 445 if (ret == -EMLINK) { 446 struct btrfs_super_block *disk_super = root->fs_info->super_copy; 447 /* We ran out of space in the ref array. Need to 448 * add an extended ref. */ 449 if (btrfs_super_incompat_flags(disk_super) 450 & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) 451 ret = btrfs_insert_inode_extref(trans, root, name, 452 name_len, 453 inode_objectid, 454 ref_objectid, index); 455 } 456 457 return ret; 458 } 459 460 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans, 461 struct btrfs_root *root, 462 struct btrfs_path *path, u64 objectid) 463 { 464 struct btrfs_key key; 465 int ret; 466 key.objectid = objectid; 467 btrfs_set_key_type(&key, BTRFS_INODE_ITEM_KEY); 468 key.offset = 0; 469 470 ret = btrfs_insert_empty_item(trans, root, path, &key, 471 sizeof(struct btrfs_inode_item)); 472 return ret; 473 } 474 475 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root 476 *root, struct btrfs_path *path, 477 struct btrfs_key *location, int mod) 478 { 479 int ins_len = mod < 0 ? -1 : 0; 480 int cow = mod != 0; 481 int ret; 482 int slot; 483 struct extent_buffer *leaf; 484 struct btrfs_key found_key; 485 486 ret = btrfs_search_slot(trans, root, location, path, ins_len, cow); 487 if (ret > 0 && btrfs_key_type(location) == BTRFS_ROOT_ITEM_KEY && 488 location->offset == (u64)-1 && path->slots[0] != 0) { 489 slot = path->slots[0] - 1; 490 leaf = path->nodes[0]; 491 btrfs_item_key_to_cpu(leaf, &found_key, slot); 492 if (found_key.objectid == location->objectid && 493 btrfs_key_type(&found_key) == btrfs_key_type(location)) { 494 path->slots[0]--; 495 return 0; 496 } 497 } 498 return ret; 499 } 500