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 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 123 if (ret > 0) 124 ret = -ENOENT; 125 if (ret < 0) 126 goto out; 127 128 /* 129 * Sanity check - did we find the right item for this name? 130 * This should always succeed so error here will make the FS 131 * readonly. 132 */ 133 extref = btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0], 134 ref_objectid, name, name_len); 135 if (!extref) { 136 btrfs_handle_fs_error(root->fs_info, -ENOENT, NULL); 137 ret = -EROFS; 138 goto out; 139 } 140 141 leaf = path->nodes[0]; 142 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 143 if (index) 144 *index = btrfs_inode_extref_index(leaf, extref); 145 146 if (del_len == item_size) { 147 /* 148 * Common case only one ref in the item, remove the 149 * whole item. 150 */ 151 ret = btrfs_del_item(trans, root, path); 152 goto out; 153 } 154 155 ptr = (unsigned long)extref; 156 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 157 158 memmove_extent_buffer(leaf, ptr, ptr + del_len, 159 item_size - (ptr + del_len - item_start)); 160 161 btrfs_truncate_item(path, item_size - del_len, 1); 162 163 out: 164 btrfs_free_path(path); 165 166 return ret; 167 } 168 169 int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, 170 struct btrfs_root *root, 171 const char *name, int name_len, 172 u64 inode_objectid, u64 ref_objectid, u64 *index) 173 { 174 struct btrfs_path *path; 175 struct btrfs_key key; 176 struct btrfs_inode_ref *ref; 177 struct extent_buffer *leaf; 178 unsigned long ptr; 179 unsigned long item_start; 180 u32 item_size; 181 u32 sub_item_len; 182 int ret; 183 int search_ext_refs = 0; 184 int del_len = name_len + sizeof(*ref); 185 186 key.objectid = inode_objectid; 187 key.offset = ref_objectid; 188 key.type = BTRFS_INODE_REF_KEY; 189 190 path = btrfs_alloc_path(); 191 if (!path) 192 return -ENOMEM; 193 194 ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 195 if (ret > 0) { 196 ret = -ENOENT; 197 search_ext_refs = 1; 198 goto out; 199 } else if (ret < 0) { 200 goto out; 201 } 202 203 ref = btrfs_find_name_in_backref(path->nodes[0], path->slots[0], name, 204 name_len); 205 if (!ref) { 206 ret = -ENOENT; 207 search_ext_refs = 1; 208 goto out; 209 } 210 leaf = path->nodes[0]; 211 item_size = btrfs_item_size_nr(leaf, path->slots[0]); 212 213 if (index) 214 *index = btrfs_inode_ref_index(leaf, ref); 215 216 if (del_len == item_size) { 217 ret = btrfs_del_item(trans, root, path); 218 goto out; 219 } 220 ptr = (unsigned long)ref; 221 sub_item_len = name_len + sizeof(*ref); 222 item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 223 memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, 224 item_size - (ptr + sub_item_len - item_start)); 225 btrfs_truncate_item(path, item_size - sub_item_len, 1); 226 out: 227 btrfs_free_path(path); 228 229 if (search_ext_refs) { 230 /* 231 * No refs were found, or we could not find the 232 * name in our ref array. Find and remove the extended 233 * inode ref then. 234 */ 235 return btrfs_del_inode_extref(trans, root, name, name_len, 236 inode_objectid, ref_objectid, index); 237 } 238 239 return ret; 240 } 241 242 /* 243 * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree. 244 * 245 * The caller must have checked against BTRFS_LINK_MAX already. 246 */ 247 static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans, 248 struct btrfs_root *root, 249 const char *name, int name_len, 250 u64 inode_objectid, u64 ref_objectid, u64 index) 251 { 252 struct btrfs_inode_extref *extref; 253 int ret; 254 int ins_len = name_len + sizeof(*extref); 255 unsigned long ptr; 256 struct btrfs_path *path; 257 struct btrfs_key key; 258 struct extent_buffer *leaf; 259 struct btrfs_item *item; 260 261 key.objectid = inode_objectid; 262 key.type = BTRFS_INODE_EXTREF_KEY; 263 key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 264 265 path = btrfs_alloc_path(); 266 if (!path) 267 return -ENOMEM; 268 269 ret = btrfs_insert_empty_item(trans, root, path, &key, 270 ins_len); 271 if (ret == -EEXIST) { 272 if (btrfs_find_name_in_ext_backref(path->nodes[0], 273 path->slots[0], 274 ref_objectid, 275 name, name_len)) 276 goto out; 277 278 btrfs_extend_item(path, ins_len); 279 ret = 0; 280 } 281 if (ret < 0) 282 goto out; 283 284 leaf = path->nodes[0]; 285 item = btrfs_item_nr(path->slots[0]); 286 ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char); 287 ptr += btrfs_item_size(leaf, item) - ins_len; 288 extref = (struct btrfs_inode_extref *)ptr; 289 290 btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len); 291 btrfs_set_inode_extref_index(path->nodes[0], extref, index); 292 btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid); 293 294 ptr = (unsigned long)&extref->name; 295 write_extent_buffer(path->nodes[0], name, ptr, name_len); 296 btrfs_mark_buffer_dirty(path->nodes[0]); 297 298 out: 299 btrfs_free_path(path); 300 return ret; 301 } 302 303 /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */ 304 int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans, 305 struct btrfs_root *root, 306 const char *name, int name_len, 307 u64 inode_objectid, u64 ref_objectid, u64 index) 308 { 309 struct btrfs_fs_info *fs_info = root->fs_info; 310 struct btrfs_path *path; 311 struct btrfs_key key; 312 struct btrfs_inode_ref *ref; 313 unsigned long ptr; 314 int ret; 315 int ins_len = name_len + sizeof(*ref); 316 317 key.objectid = inode_objectid; 318 key.offset = ref_objectid; 319 key.type = BTRFS_INODE_REF_KEY; 320 321 path = btrfs_alloc_path(); 322 if (!path) 323 return -ENOMEM; 324 325 path->skip_release_on_error = 1; 326 ret = btrfs_insert_empty_item(trans, root, path, &key, 327 ins_len); 328 if (ret == -EEXIST) { 329 u32 old_size; 330 ref = btrfs_find_name_in_backref(path->nodes[0], path->slots[0], 331 name, name_len); 332 if (ref) 333 goto out; 334 335 old_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]); 336 btrfs_extend_item(path, ins_len); 337 ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 338 struct btrfs_inode_ref); 339 ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size); 340 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 341 btrfs_set_inode_ref_index(path->nodes[0], ref, index); 342 ptr = (unsigned long)(ref + 1); 343 ret = 0; 344 } else if (ret < 0) { 345 if (ret == -EOVERFLOW) { 346 if (btrfs_find_name_in_backref(path->nodes[0], 347 path->slots[0], 348 name, name_len)) 349 ret = -EEXIST; 350 else 351 ret = -EMLINK; 352 } 353 goto out; 354 } else { 355 ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 356 struct btrfs_inode_ref); 357 btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 358 btrfs_set_inode_ref_index(path->nodes[0], ref, index); 359 ptr = (unsigned long)(ref + 1); 360 } 361 write_extent_buffer(path->nodes[0], name, ptr, name_len); 362 btrfs_mark_buffer_dirty(path->nodes[0]); 363 364 out: 365 btrfs_free_path(path); 366 367 if (ret == -EMLINK) { 368 struct btrfs_super_block *disk_super = fs_info->super_copy; 369 /* We ran out of space in the ref array. Need to 370 * add an extended ref. */ 371 if (btrfs_super_incompat_flags(disk_super) 372 & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) 373 ret = btrfs_insert_inode_extref(trans, root, name, 374 name_len, 375 inode_objectid, 376 ref_objectid, index); 377 } 378 379 return ret; 380 } 381 382 int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans, 383 struct btrfs_root *root, 384 struct btrfs_path *path, u64 objectid) 385 { 386 struct btrfs_key key; 387 int ret; 388 key.objectid = objectid; 389 key.type = BTRFS_INODE_ITEM_KEY; 390 key.offset = 0; 391 392 ret = btrfs_insert_empty_item(trans, root, path, &key, 393 sizeof(struct btrfs_inode_item)); 394 return ret; 395 } 396 397 int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root 398 *root, struct btrfs_path *path, 399 struct btrfs_key *location, int mod) 400 { 401 int ins_len = mod < 0 ? -1 : 0; 402 int cow = mod != 0; 403 int ret; 404 int slot; 405 struct extent_buffer *leaf; 406 struct btrfs_key found_key; 407 408 ret = btrfs_search_slot(trans, root, location, path, ins_len, cow); 409 if (ret > 0 && location->type == BTRFS_ROOT_ITEM_KEY && 410 location->offset == (u64)-1 && path->slots[0] != 0) { 411 slot = path->slots[0] - 1; 412 leaf = path->nodes[0]; 413 btrfs_item_key_to_cpu(leaf, &found_key, slot); 414 if (found_key.objectid == location->objectid && 415 found_key.type == location->type) { 416 path->slots[0]--; 417 return 0; 418 } 419 } 420 return ret; 421 } 422