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