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