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