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