1c1d7c514SDavid Sterba // SPDX-License-Identifier: GPL-2.0 26cbd5570SChris Mason /* 36cbd5570SChris Mason * Copyright (C) 2007 Oracle. All rights reserved. 46cbd5570SChris Mason */ 56cbd5570SChris Mason 61e1d2701SChris Mason #include "ctree.h" 726c2c454SJosef Bacik #include "inode-item.h" 81e1d2701SChris Mason #include "disk-io.h" 9e089f05cSChris Mason #include "transaction.h" 10727011e0SChris Mason #include "print-tree.h" 111e1d2701SChris Mason 129bb8407fSNikolay Borisov struct btrfs_inode_ref *btrfs_find_name_in_backref(struct extent_buffer *leaf, 139bb8407fSNikolay Borisov int slot, const char *name, 149bb8407fSNikolay Borisov int name_len) 153954401fSChris Mason { 163954401fSChris Mason struct btrfs_inode_ref *ref; 173954401fSChris Mason unsigned long ptr; 183954401fSChris Mason unsigned long name_ptr; 193954401fSChris Mason u32 item_size; 203954401fSChris Mason u32 cur_offset = 0; 213954401fSChris Mason int len; 223954401fSChris Mason 233212fa14SJosef Bacik item_size = btrfs_item_size(leaf, slot); 241f250e92SFilipe Manana ptr = btrfs_item_ptr_offset(leaf, slot); 253954401fSChris Mason while (cur_offset < item_size) { 263954401fSChris Mason ref = (struct btrfs_inode_ref *)(ptr + cur_offset); 273954401fSChris Mason len = btrfs_inode_ref_name_len(leaf, ref); 283954401fSChris Mason name_ptr = (unsigned long)(ref + 1); 293954401fSChris Mason cur_offset += len + sizeof(*ref); 303954401fSChris Mason if (len != name_len) 313954401fSChris Mason continue; 329bb8407fSNikolay Borisov if (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) 339bb8407fSNikolay Borisov return ref; 343954401fSChris Mason } 359bb8407fSNikolay Borisov return NULL; 363954401fSChris Mason } 373954401fSChris Mason 386ff49c6aSNikolay Borisov struct btrfs_inode_extref *btrfs_find_name_in_ext_backref( 396ff49c6aSNikolay Borisov struct extent_buffer *leaf, int slot, u64 ref_objectid, 406ff49c6aSNikolay Borisov const char *name, int name_len) 41f186373fSMark Fasheh { 42f186373fSMark Fasheh struct btrfs_inode_extref *extref; 43f186373fSMark Fasheh unsigned long ptr; 44f186373fSMark Fasheh unsigned long name_ptr; 45f186373fSMark Fasheh u32 item_size; 46f186373fSMark Fasheh u32 cur_offset = 0; 47f186373fSMark Fasheh int ref_name_len; 48f186373fSMark Fasheh 493212fa14SJosef Bacik item_size = btrfs_item_size(leaf, slot); 501f250e92SFilipe Manana ptr = btrfs_item_ptr_offset(leaf, slot); 51f186373fSMark Fasheh 52f186373fSMark Fasheh /* 53f186373fSMark Fasheh * Search all extended backrefs in this item. We're only 54f186373fSMark Fasheh * looking through any collisions so most of the time this is 55f186373fSMark Fasheh * just going to compare against one buffer. If all is well, 56f186373fSMark Fasheh * we'll return success and the inode ref object. 57f186373fSMark Fasheh */ 58f186373fSMark Fasheh while (cur_offset < item_size) { 59f186373fSMark Fasheh extref = (struct btrfs_inode_extref *) (ptr + cur_offset); 60f186373fSMark Fasheh name_ptr = (unsigned long)(&extref->name); 61f186373fSMark Fasheh ref_name_len = btrfs_inode_extref_name_len(leaf, extref); 62f186373fSMark Fasheh 63f186373fSMark Fasheh if (ref_name_len == name_len && 64f186373fSMark Fasheh btrfs_inode_extref_parent(leaf, extref) == ref_objectid && 656ff49c6aSNikolay Borisov (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)) 666ff49c6aSNikolay Borisov return extref; 67f186373fSMark Fasheh 68f186373fSMark Fasheh cur_offset += ref_name_len + sizeof(*extref); 69f186373fSMark Fasheh } 706ff49c6aSNikolay Borisov return NULL; 71f186373fSMark Fasheh } 72f186373fSMark Fasheh 73f186373fSMark Fasheh /* Returns NULL if no extref found */ 74f186373fSMark Fasheh struct btrfs_inode_extref * 75f186373fSMark Fasheh btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans, 76f186373fSMark Fasheh struct btrfs_root *root, 77f186373fSMark Fasheh struct btrfs_path *path, 78f186373fSMark Fasheh const char *name, int name_len, 79f186373fSMark Fasheh u64 inode_objectid, u64 ref_objectid, int ins_len, 80f186373fSMark Fasheh int cow) 81f186373fSMark Fasheh { 82f186373fSMark Fasheh int ret; 83f186373fSMark Fasheh struct btrfs_key key; 84f186373fSMark Fasheh 85f186373fSMark Fasheh key.objectid = inode_objectid; 86f186373fSMark Fasheh key.type = BTRFS_INODE_EXTREF_KEY; 87f186373fSMark Fasheh key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 88f186373fSMark Fasheh 89f186373fSMark Fasheh ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 90f186373fSMark Fasheh if (ret < 0) 91f186373fSMark Fasheh return ERR_PTR(ret); 92f186373fSMark Fasheh if (ret > 0) 93f186373fSMark Fasheh return NULL; 946ff49c6aSNikolay Borisov return btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0], 956ff49c6aSNikolay Borisov ref_objectid, name, name_len); 966ff49c6aSNikolay Borisov 97f186373fSMark Fasheh } 98f186373fSMark Fasheh 9948a3b636SEric Sandeen static int btrfs_del_inode_extref(struct btrfs_trans_handle *trans, 100f186373fSMark Fasheh struct btrfs_root *root, 101f186373fSMark Fasheh const char *name, int name_len, 10248a3b636SEric Sandeen u64 inode_objectid, u64 ref_objectid, 10348a3b636SEric Sandeen u64 *index) 104f186373fSMark Fasheh { 105f186373fSMark Fasheh struct btrfs_path *path; 106f186373fSMark Fasheh struct btrfs_key key; 107f186373fSMark Fasheh struct btrfs_inode_extref *extref; 108f186373fSMark Fasheh struct extent_buffer *leaf; 109f186373fSMark Fasheh int ret; 110f186373fSMark Fasheh int del_len = name_len + sizeof(*extref); 111f186373fSMark Fasheh unsigned long ptr; 112f186373fSMark Fasheh unsigned long item_start; 113f186373fSMark Fasheh u32 item_size; 114f186373fSMark Fasheh 115f186373fSMark Fasheh key.objectid = inode_objectid; 116962a298fSDavid Sterba key.type = BTRFS_INODE_EXTREF_KEY; 117f186373fSMark Fasheh key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 118f186373fSMark Fasheh 119f186373fSMark Fasheh path = btrfs_alloc_path(); 120f186373fSMark Fasheh if (!path) 121f186373fSMark Fasheh return -ENOMEM; 122f186373fSMark Fasheh 123f186373fSMark Fasheh ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 124f186373fSMark Fasheh if (ret > 0) 125f186373fSMark Fasheh ret = -ENOENT; 126f186373fSMark Fasheh if (ret < 0) 127f186373fSMark Fasheh goto out; 128f186373fSMark Fasheh 129f186373fSMark Fasheh /* 130f186373fSMark Fasheh * Sanity check - did we find the right item for this name? 131f186373fSMark Fasheh * This should always succeed so error here will make the FS 132f186373fSMark Fasheh * readonly. 133f186373fSMark Fasheh */ 1346ff49c6aSNikolay Borisov extref = btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0], 1356ff49c6aSNikolay Borisov ref_objectid, name, name_len); 1366ff49c6aSNikolay Borisov if (!extref) { 13734d97007SAnand Jain btrfs_handle_fs_error(root->fs_info, -ENOENT, NULL); 138f186373fSMark Fasheh ret = -EROFS; 139f186373fSMark Fasheh goto out; 140f186373fSMark Fasheh } 141f186373fSMark Fasheh 142f186373fSMark Fasheh leaf = path->nodes[0]; 1433212fa14SJosef Bacik item_size = btrfs_item_size(leaf, path->slots[0]); 144f186373fSMark Fasheh if (index) 145f186373fSMark Fasheh *index = btrfs_inode_extref_index(leaf, extref); 146f186373fSMark Fasheh 147f186373fSMark Fasheh if (del_len == item_size) { 148f186373fSMark Fasheh /* 149f186373fSMark Fasheh * Common case only one ref in the item, remove the 150f186373fSMark Fasheh * whole item. 151f186373fSMark Fasheh */ 152f186373fSMark Fasheh ret = btrfs_del_item(trans, root, path); 153f186373fSMark Fasheh goto out; 154f186373fSMark Fasheh } 155f186373fSMark Fasheh 156f186373fSMark Fasheh ptr = (unsigned long)extref; 157f186373fSMark Fasheh item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 158f186373fSMark Fasheh 159f186373fSMark Fasheh memmove_extent_buffer(leaf, ptr, ptr + del_len, 160f186373fSMark Fasheh item_size - (ptr + del_len - item_start)); 161f186373fSMark Fasheh 16278ac4f9eSDavid Sterba btrfs_truncate_item(path, item_size - del_len, 1); 163f186373fSMark Fasheh 164f186373fSMark Fasheh out: 165f186373fSMark Fasheh btrfs_free_path(path); 166f186373fSMark Fasheh 167f186373fSMark Fasheh return ret; 168f186373fSMark Fasheh } 169f186373fSMark Fasheh 1703954401fSChris Mason int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, 1713954401fSChris Mason struct btrfs_root *root, 1723954401fSChris Mason const char *name, int name_len, 173aec7477bSJosef Bacik u64 inode_objectid, u64 ref_objectid, u64 *index) 1743954401fSChris Mason { 1753954401fSChris Mason struct btrfs_path *path; 1763954401fSChris Mason struct btrfs_key key; 1773954401fSChris Mason struct btrfs_inode_ref *ref; 1783954401fSChris Mason struct extent_buffer *leaf; 1793954401fSChris Mason unsigned long ptr; 1803954401fSChris Mason unsigned long item_start; 1813954401fSChris Mason u32 item_size; 1823954401fSChris Mason u32 sub_item_len; 1833954401fSChris Mason int ret; 184f186373fSMark Fasheh int search_ext_refs = 0; 1853954401fSChris Mason int del_len = name_len + sizeof(*ref); 1863954401fSChris Mason 1873954401fSChris Mason key.objectid = inode_objectid; 1883954401fSChris Mason key.offset = ref_objectid; 189962a298fSDavid Sterba key.type = BTRFS_INODE_REF_KEY; 1903954401fSChris Mason 1913954401fSChris Mason path = btrfs_alloc_path(); 1923954401fSChris Mason if (!path) 1933954401fSChris Mason return -ENOMEM; 1943954401fSChris Mason 1953954401fSChris Mason ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 1963954401fSChris Mason if (ret > 0) { 1973954401fSChris Mason ret = -ENOENT; 198f186373fSMark Fasheh search_ext_refs = 1; 1993954401fSChris Mason goto out; 2003954401fSChris Mason } else if (ret < 0) { 2013954401fSChris Mason goto out; 2023954401fSChris Mason } 2039bb8407fSNikolay Borisov 2049bb8407fSNikolay Borisov ref = btrfs_find_name_in_backref(path->nodes[0], path->slots[0], name, 2059bb8407fSNikolay Borisov name_len); 2069bb8407fSNikolay Borisov if (!ref) { 2073954401fSChris Mason ret = -ENOENT; 208f186373fSMark Fasheh search_ext_refs = 1; 2093954401fSChris Mason goto out; 2103954401fSChris Mason } 2113954401fSChris Mason leaf = path->nodes[0]; 2123212fa14SJosef Bacik item_size = btrfs_item_size(leaf, path->slots[0]); 213aec7477bSJosef Bacik 214aec7477bSJosef Bacik if (index) 215aec7477bSJosef Bacik *index = btrfs_inode_ref_index(leaf, ref); 216aec7477bSJosef Bacik 2173954401fSChris Mason if (del_len == item_size) { 2183954401fSChris Mason ret = btrfs_del_item(trans, root, path); 2193954401fSChris Mason goto out; 2203954401fSChris Mason } 2213954401fSChris Mason ptr = (unsigned long)ref; 2223954401fSChris Mason sub_item_len = name_len + sizeof(*ref); 2233954401fSChris Mason item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 2243954401fSChris Mason memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, 2253954401fSChris Mason item_size - (ptr + sub_item_len - item_start)); 22678ac4f9eSDavid Sterba btrfs_truncate_item(path, item_size - sub_item_len, 1); 227f186373fSMark Fasheh out: 228f186373fSMark Fasheh btrfs_free_path(path); 229f186373fSMark Fasheh 230f186373fSMark Fasheh if (search_ext_refs) { 231f186373fSMark Fasheh /* 232f186373fSMark Fasheh * No refs were found, or we could not find the 233f186373fSMark Fasheh * name in our ref array. Find and remove the extended 234f186373fSMark Fasheh * inode ref then. 235f186373fSMark Fasheh */ 236f186373fSMark Fasheh return btrfs_del_inode_extref(trans, root, name, name_len, 237f186373fSMark Fasheh inode_objectid, ref_objectid, index); 238f186373fSMark Fasheh } 239f186373fSMark Fasheh 240f186373fSMark Fasheh return ret; 241f186373fSMark Fasheh } 242f186373fSMark Fasheh 243f186373fSMark Fasheh /* 244f186373fSMark Fasheh * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree. 245f186373fSMark Fasheh * 246f186373fSMark Fasheh * The caller must have checked against BTRFS_LINK_MAX already. 247f186373fSMark Fasheh */ 248f186373fSMark Fasheh static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans, 249f186373fSMark Fasheh struct btrfs_root *root, 250f186373fSMark Fasheh const char *name, int name_len, 251f186373fSMark Fasheh u64 inode_objectid, u64 ref_objectid, u64 index) 252f186373fSMark Fasheh { 253f186373fSMark Fasheh struct btrfs_inode_extref *extref; 254f186373fSMark Fasheh int ret; 255f186373fSMark Fasheh int ins_len = name_len + sizeof(*extref); 256f186373fSMark Fasheh unsigned long ptr; 257f186373fSMark Fasheh struct btrfs_path *path; 258f186373fSMark Fasheh struct btrfs_key key; 259f186373fSMark Fasheh struct extent_buffer *leaf; 260f186373fSMark Fasheh 261f186373fSMark Fasheh key.objectid = inode_objectid; 262f186373fSMark Fasheh key.type = BTRFS_INODE_EXTREF_KEY; 263f186373fSMark Fasheh key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 264f186373fSMark Fasheh 265f186373fSMark Fasheh path = btrfs_alloc_path(); 266f186373fSMark Fasheh if (!path) 267f186373fSMark Fasheh return -ENOMEM; 268f186373fSMark Fasheh 269f186373fSMark Fasheh ret = btrfs_insert_empty_item(trans, root, path, &key, 270f186373fSMark Fasheh ins_len); 271f186373fSMark Fasheh if (ret == -EEXIST) { 2721f250e92SFilipe Manana if (btrfs_find_name_in_ext_backref(path->nodes[0], 2731f250e92SFilipe Manana path->slots[0], 2741f250e92SFilipe Manana ref_objectid, 2756ff49c6aSNikolay Borisov name, name_len)) 276f186373fSMark Fasheh goto out; 277f186373fSMark Fasheh 278c71dd880SDavid Sterba btrfs_extend_item(path, ins_len); 279f186373fSMark Fasheh ret = 0; 280f186373fSMark Fasheh } 281f186373fSMark Fasheh if (ret < 0) 282f186373fSMark Fasheh goto out; 283f186373fSMark Fasheh 284f186373fSMark Fasheh leaf = path->nodes[0]; 285f186373fSMark Fasheh ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char); 2863212fa14SJosef Bacik ptr += btrfs_item_size(leaf, path->slots[0]) - ins_len; 287f186373fSMark Fasheh extref = (struct btrfs_inode_extref *)ptr; 288f186373fSMark Fasheh 289f186373fSMark Fasheh btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len); 290f186373fSMark Fasheh btrfs_set_inode_extref_index(path->nodes[0], extref, index); 291f186373fSMark Fasheh btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid); 292f186373fSMark Fasheh 293f186373fSMark Fasheh ptr = (unsigned long)&extref->name; 294f186373fSMark Fasheh write_extent_buffer(path->nodes[0], name, ptr, name_len); 295f186373fSMark Fasheh btrfs_mark_buffer_dirty(path->nodes[0]); 296f186373fSMark Fasheh 2973954401fSChris Mason out: 2983954401fSChris Mason btrfs_free_path(path); 2993954401fSChris Mason return ret; 3003954401fSChris Mason } 3013954401fSChris Mason 30279787eaaSJeff Mahoney /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */ 3033954401fSChris Mason int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans, 3043954401fSChris Mason struct btrfs_root *root, 3053954401fSChris Mason const char *name, int name_len, 306aec7477bSJosef Bacik u64 inode_objectid, u64 ref_objectid, u64 index) 3073954401fSChris Mason { 3080b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 3093954401fSChris Mason struct btrfs_path *path; 3103954401fSChris Mason struct btrfs_key key; 3113954401fSChris Mason struct btrfs_inode_ref *ref; 3123954401fSChris Mason unsigned long ptr; 3133954401fSChris Mason int ret; 3143954401fSChris Mason int ins_len = name_len + sizeof(*ref); 3153954401fSChris Mason 3163954401fSChris Mason key.objectid = inode_objectid; 3173954401fSChris Mason key.offset = ref_objectid; 318962a298fSDavid Sterba key.type = BTRFS_INODE_REF_KEY; 3193954401fSChris Mason 3203954401fSChris Mason path = btrfs_alloc_path(); 3213954401fSChris Mason if (!path) 3223954401fSChris Mason return -ENOMEM; 3233954401fSChris Mason 324df8d116fSFilipe Manana path->skip_release_on_error = 1; 3253954401fSChris Mason ret = btrfs_insert_empty_item(trans, root, path, &key, 3263954401fSChris Mason ins_len); 3273954401fSChris Mason if (ret == -EEXIST) { 3283954401fSChris Mason u32 old_size; 3299bb8407fSNikolay Borisov ref = btrfs_find_name_in_backref(path->nodes[0], path->slots[0], 3309bb8407fSNikolay Borisov name, name_len); 3319bb8407fSNikolay Borisov if (ref) 3323954401fSChris Mason goto out; 3333954401fSChris Mason 3343212fa14SJosef Bacik old_size = btrfs_item_size(path->nodes[0], path->slots[0]); 335c71dd880SDavid Sterba btrfs_extend_item(path, ins_len); 3363954401fSChris Mason ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 3373954401fSChris Mason struct btrfs_inode_ref); 3383954401fSChris Mason ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size); 3393954401fSChris Mason btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 340aec7477bSJosef Bacik btrfs_set_inode_ref_index(path->nodes[0], ref, index); 3413954401fSChris Mason ptr = (unsigned long)(ref + 1); 3423954401fSChris Mason ret = 0; 3433954401fSChris Mason } else if (ret < 0) { 344df8d116fSFilipe Manana if (ret == -EOVERFLOW) { 3451f250e92SFilipe Manana if (btrfs_find_name_in_backref(path->nodes[0], 3461f250e92SFilipe Manana path->slots[0], 3479bb8407fSNikolay Borisov name, name_len)) 348df8d116fSFilipe Manana ret = -EEXIST; 349df8d116fSFilipe Manana else 350a5719521SYan, Zheng ret = -EMLINK; 351df8d116fSFilipe Manana } 3523954401fSChris Mason goto out; 3533954401fSChris Mason } else { 3543954401fSChris Mason ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 3553954401fSChris Mason struct btrfs_inode_ref); 3563954401fSChris Mason btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 357aec7477bSJosef Bacik btrfs_set_inode_ref_index(path->nodes[0], ref, index); 3583954401fSChris Mason ptr = (unsigned long)(ref + 1); 3593954401fSChris Mason } 3603954401fSChris Mason write_extent_buffer(path->nodes[0], name, ptr, name_len); 3613954401fSChris Mason btrfs_mark_buffer_dirty(path->nodes[0]); 3623954401fSChris Mason 3633954401fSChris Mason out: 3643954401fSChris Mason btrfs_free_path(path); 365f186373fSMark Fasheh 366f186373fSMark Fasheh if (ret == -EMLINK) { 3670b246afaSJeff Mahoney struct btrfs_super_block *disk_super = fs_info->super_copy; 368f186373fSMark Fasheh /* We ran out of space in the ref array. Need to 369f186373fSMark Fasheh * add an extended ref. */ 370f186373fSMark Fasheh if (btrfs_super_incompat_flags(disk_super) 371f186373fSMark Fasheh & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) 372f186373fSMark Fasheh ret = btrfs_insert_inode_extref(trans, root, name, 373f186373fSMark Fasheh name_len, 374f186373fSMark Fasheh inode_objectid, 375f186373fSMark Fasheh ref_objectid, index); 376f186373fSMark Fasheh } 377f186373fSMark Fasheh 3783954401fSChris Mason return ret; 3793954401fSChris Mason } 3803954401fSChris Mason 3815f39d397SChris Mason int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans, 3825f39d397SChris Mason struct btrfs_root *root, 3835f39d397SChris Mason struct btrfs_path *path, u64 objectid) 3841e1d2701SChris Mason { 3851e1d2701SChris Mason struct btrfs_key key; 3861e1d2701SChris Mason int ret; 3871e1d2701SChris Mason key.objectid = objectid; 388962a298fSDavid Sterba key.type = BTRFS_INODE_ITEM_KEY; 3891e1d2701SChris Mason key.offset = 0; 3901e1d2701SChris Mason 3915f39d397SChris Mason ret = btrfs_insert_empty_item(trans, root, path, &key, 3925f39d397SChris Mason sizeof(struct btrfs_inode_item)); 3931e1d2701SChris Mason return ret; 3941e1d2701SChris Mason } 3951e1d2701SChris Mason 396e089f05cSChris Mason int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root 397d6e4a428SChris Mason *root, struct btrfs_path *path, 398d6e4a428SChris Mason struct btrfs_key *location, int mod) 3991e1d2701SChris Mason { 4001e1d2701SChris Mason int ins_len = mod < 0 ? -1 : 0; 4011e1d2701SChris Mason int cow = mod != 0; 402d6e4a428SChris Mason int ret; 403d6e4a428SChris Mason int slot; 4045f39d397SChris Mason struct extent_buffer *leaf; 405d6e4a428SChris Mason struct btrfs_key found_key; 4061e1d2701SChris Mason 407d6e4a428SChris Mason ret = btrfs_search_slot(trans, root, location, path, ins_len, cow); 408962a298fSDavid Sterba if (ret > 0 && location->type == BTRFS_ROOT_ITEM_KEY && 409d6e4a428SChris Mason location->offset == (u64)-1 && path->slots[0] != 0) { 410d6e4a428SChris Mason slot = path->slots[0] - 1; 4115f39d397SChris Mason leaf = path->nodes[0]; 4125f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &found_key, slot); 413d6e4a428SChris Mason if (found_key.objectid == location->objectid && 414962a298fSDavid Sterba found_key.type == location->type) { 415d6e4a428SChris Mason path->slots[0]--; 416d6e4a428SChris Mason return 0; 417d6e4a428SChris Mason } 418d6e4a428SChris Mason } 419d6e4a428SChris Mason return ret; 4201e1d2701SChris Mason } 42154f03ab1SJosef Bacik 42254f03ab1SJosef Bacik /* 42354f03ab1SJosef Bacik * Remove inode items from a given root. 42454f03ab1SJosef Bacik * 42554f03ab1SJosef Bacik * @trans: A transaction handle. 42654f03ab1SJosef Bacik * @root: The root from which to remove items. 42754f03ab1SJosef Bacik * @inode: The inode whose items we want to remove. 428d9ac19c3SJosef Bacik * @control: The btrfs_truncate_control to control how and what we 429d9ac19c3SJosef Bacik * are truncating. 43054f03ab1SJosef Bacik * 43154f03ab1SJosef Bacik * Remove all keys associated with the inode from the given root that have a key 43254f03ab1SJosef Bacik * with a type greater than or equals to @min_type. When @min_type has a value of 43354f03ab1SJosef Bacik * BTRFS_EXTENT_DATA_KEY, only remove file extent items that have an offset value 43454f03ab1SJosef Bacik * greater than or equals to @new_size. If a file extent item that starts before 43554f03ab1SJosef Bacik * @new_size and ends after it is found, its length is adjusted. 43654f03ab1SJosef Bacik * 43754f03ab1SJosef Bacik * Returns: 0 on success, < 0 on error and NEED_TRUNCATE_BLOCK when @min_type is 43854f03ab1SJosef Bacik * BTRFS_EXTENT_DATA_KEY and the caller must truncate the last block. 43954f03ab1SJosef Bacik */ 44054f03ab1SJosef Bacik int btrfs_truncate_inode_items(struct btrfs_trans_handle *trans, 44154f03ab1SJosef Bacik struct btrfs_root *root, 44254f03ab1SJosef Bacik struct btrfs_inode *inode, 443d9ac19c3SJosef Bacik struct btrfs_truncate_control *control) 44454f03ab1SJosef Bacik { 44554f03ab1SJosef Bacik struct btrfs_fs_info *fs_info = root->fs_info; 44654f03ab1SJosef Bacik struct btrfs_path *path; 44754f03ab1SJosef Bacik struct extent_buffer *leaf; 44854f03ab1SJosef Bacik struct btrfs_file_extent_item *fi; 44954f03ab1SJosef Bacik struct btrfs_key key; 45054f03ab1SJosef Bacik struct btrfs_key found_key; 451d9ac19c3SJosef Bacik u64 new_size = control->new_size; 45254f03ab1SJosef Bacik u64 extent_num_bytes = 0; 45354f03ab1SJosef Bacik u64 extent_offset = 0; 45454f03ab1SJosef Bacik u64 item_end = 0; 45554f03ab1SJosef Bacik u32 found_type = (u8)-1; 45654f03ab1SJosef Bacik int del_item; 45754f03ab1SJosef Bacik int pending_del_nr = 0; 45854f03ab1SJosef Bacik int pending_del_slot = 0; 45954f03ab1SJosef Bacik int extent_type = -1; 46054f03ab1SJosef Bacik int ret; 46154f03ab1SJosef Bacik u64 ino = btrfs_ino(inode); 46254f03ab1SJosef Bacik u64 bytes_deleted = 0; 46354f03ab1SJosef Bacik bool be_nice = false; 46454f03ab1SJosef Bacik bool should_throttle = false; 46554f03ab1SJosef Bacik 466d9ac19c3SJosef Bacik BUG_ON(new_size > 0 && control->min_type != BTRFS_EXTENT_DATA_KEY); 46754f03ab1SJosef Bacik 468c2ddb612SJosef Bacik control->last_size = new_size; 469462b728eSJosef Bacik control->sub_bytes = 0; 470c2ddb612SJosef Bacik 47154f03ab1SJosef Bacik /* 472275312a0SJosef Bacik * For shareable roots we want to back off from time to time, this turns 473275312a0SJosef Bacik * out to be subvolume roots, reloc roots, and data reloc roots. 47454f03ab1SJosef Bacik */ 475275312a0SJosef Bacik if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) 47654f03ab1SJosef Bacik be_nice = true; 47754f03ab1SJosef Bacik 47854f03ab1SJosef Bacik path = btrfs_alloc_path(); 47954f03ab1SJosef Bacik if (!path) 48054f03ab1SJosef Bacik return -ENOMEM; 48154f03ab1SJosef Bacik path->reada = READA_BACK; 48254f03ab1SJosef Bacik 48354f03ab1SJosef Bacik key.objectid = ino; 48454f03ab1SJosef Bacik key.offset = (u64)-1; 48554f03ab1SJosef Bacik key.type = (u8)-1; 48654f03ab1SJosef Bacik 48754f03ab1SJosef Bacik search_again: 48854f03ab1SJosef Bacik /* 48954f03ab1SJosef Bacik * With a 16K leaf size and 128MiB extents, you can actually queue up a 49054f03ab1SJosef Bacik * huge file in a single leaf. Most of the time that bytes_deleted is 49154f03ab1SJosef Bacik * > 0, it will be huge by the time we get here 49254f03ab1SJosef Bacik */ 49354f03ab1SJosef Bacik if (be_nice && bytes_deleted > SZ_32M && 49454f03ab1SJosef Bacik btrfs_should_end_transaction(trans)) { 49554f03ab1SJosef Bacik ret = -EAGAIN; 49654f03ab1SJosef Bacik goto out; 49754f03ab1SJosef Bacik } 49854f03ab1SJosef Bacik 49954f03ab1SJosef Bacik ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 50054f03ab1SJosef Bacik if (ret < 0) 50154f03ab1SJosef Bacik goto out; 50254f03ab1SJosef Bacik 50354f03ab1SJosef Bacik if (ret > 0) { 50454f03ab1SJosef Bacik ret = 0; 50554f03ab1SJosef Bacik /* There are no items in the tree for us to truncate, we're done */ 50654f03ab1SJosef Bacik if (path->slots[0] == 0) 50754f03ab1SJosef Bacik goto out; 50854f03ab1SJosef Bacik path->slots[0]--; 50954f03ab1SJosef Bacik } 51054f03ab1SJosef Bacik 51154f03ab1SJosef Bacik while (1) { 5127097a941SJosef Bacik u64 clear_start = 0, clear_len = 0, extent_start = 0; 51354f03ab1SJosef Bacik 51454f03ab1SJosef Bacik fi = NULL; 51554f03ab1SJosef Bacik leaf = path->nodes[0]; 51654f03ab1SJosef Bacik btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 51754f03ab1SJosef Bacik found_type = found_key.type; 51854f03ab1SJosef Bacik 51954f03ab1SJosef Bacik if (found_key.objectid != ino) 52054f03ab1SJosef Bacik break; 52154f03ab1SJosef Bacik 522d9ac19c3SJosef Bacik if (found_type < control->min_type) 52354f03ab1SJosef Bacik break; 52454f03ab1SJosef Bacik 52554f03ab1SJosef Bacik item_end = found_key.offset; 52654f03ab1SJosef Bacik if (found_type == BTRFS_EXTENT_DATA_KEY) { 52754f03ab1SJosef Bacik fi = btrfs_item_ptr(leaf, path->slots[0], 52854f03ab1SJosef Bacik struct btrfs_file_extent_item); 52954f03ab1SJosef Bacik extent_type = btrfs_file_extent_type(leaf, fi); 53054f03ab1SJosef Bacik if (extent_type != BTRFS_FILE_EXTENT_INLINE) { 53154f03ab1SJosef Bacik item_end += 53254f03ab1SJosef Bacik btrfs_file_extent_num_bytes(leaf, fi); 53354f03ab1SJosef Bacik 53454f03ab1SJosef Bacik trace_btrfs_truncate_show_fi_regular( 53554f03ab1SJosef Bacik inode, leaf, fi, found_key.offset); 53654f03ab1SJosef Bacik } else if (extent_type == BTRFS_FILE_EXTENT_INLINE) { 53754f03ab1SJosef Bacik item_end += btrfs_file_extent_ram_bytes(leaf, fi); 53854f03ab1SJosef Bacik 53954f03ab1SJosef Bacik trace_btrfs_truncate_show_fi_inline( 54054f03ab1SJosef Bacik inode, leaf, fi, path->slots[0], 54154f03ab1SJosef Bacik found_key.offset); 54254f03ab1SJosef Bacik } 54354f03ab1SJosef Bacik item_end--; 54454f03ab1SJosef Bacik } 545d9ac19c3SJosef Bacik if (found_type > control->min_type) { 54654f03ab1SJosef Bacik del_item = 1; 54754f03ab1SJosef Bacik } else { 54854f03ab1SJosef Bacik if (item_end < new_size) 54954f03ab1SJosef Bacik break; 55054f03ab1SJosef Bacik if (found_key.offset >= new_size) 55154f03ab1SJosef Bacik del_item = 1; 55254f03ab1SJosef Bacik else 55354f03ab1SJosef Bacik del_item = 0; 55454f03ab1SJosef Bacik } 5557097a941SJosef Bacik 55654f03ab1SJosef Bacik /* FIXME, shrink the extent if the ref count is only 1 */ 55754f03ab1SJosef Bacik if (found_type != BTRFS_EXTENT_DATA_KEY) 55854f03ab1SJosef Bacik goto delete; 55954f03ab1SJosef Bacik 560d9ac19c3SJosef Bacik control->extents_found++; 56154f03ab1SJosef Bacik 56254f03ab1SJosef Bacik if (extent_type != BTRFS_FILE_EXTENT_INLINE) { 56354f03ab1SJosef Bacik u64 num_dec; 56454f03ab1SJosef Bacik 56554f03ab1SJosef Bacik clear_start = found_key.offset; 56654f03ab1SJosef Bacik extent_start = btrfs_file_extent_disk_bytenr(leaf, fi); 56754f03ab1SJosef Bacik if (!del_item) { 56854f03ab1SJosef Bacik u64 orig_num_bytes = 56954f03ab1SJosef Bacik btrfs_file_extent_num_bytes(leaf, fi); 57054f03ab1SJosef Bacik extent_num_bytes = ALIGN(new_size - 57154f03ab1SJosef Bacik found_key.offset, 57254f03ab1SJosef Bacik fs_info->sectorsize); 57354f03ab1SJosef Bacik clear_start = ALIGN(new_size, fs_info->sectorsize); 57454f03ab1SJosef Bacik 57554f03ab1SJosef Bacik btrfs_set_file_extent_num_bytes(leaf, fi, 57654f03ab1SJosef Bacik extent_num_bytes); 57754f03ab1SJosef Bacik num_dec = (orig_num_bytes - extent_num_bytes); 578462b728eSJosef Bacik if (extent_start != 0) 579462b728eSJosef Bacik control->sub_bytes += num_dec; 58054f03ab1SJosef Bacik btrfs_mark_buffer_dirty(leaf); 58154f03ab1SJosef Bacik } else { 58254f03ab1SJosef Bacik extent_num_bytes = 58354f03ab1SJosef Bacik btrfs_file_extent_disk_num_bytes(leaf, fi); 58454f03ab1SJosef Bacik extent_offset = found_key.offset - 58554f03ab1SJosef Bacik btrfs_file_extent_offset(leaf, fi); 58654f03ab1SJosef Bacik 58754f03ab1SJosef Bacik /* FIXME blocksize != 4096 */ 58854f03ab1SJosef Bacik num_dec = btrfs_file_extent_num_bytes(leaf, fi); 589462b728eSJosef Bacik if (extent_start != 0) 590462b728eSJosef Bacik control->sub_bytes += num_dec; 59154f03ab1SJosef Bacik } 59254f03ab1SJosef Bacik clear_len = num_dec; 59354f03ab1SJosef Bacik } else if (extent_type == BTRFS_FILE_EXTENT_INLINE) { 59454f03ab1SJosef Bacik /* 59554f03ab1SJosef Bacik * We can't truncate inline items that have had 59654f03ab1SJosef Bacik * special encodings 59754f03ab1SJosef Bacik */ 59854f03ab1SJosef Bacik if (!del_item && 59954f03ab1SJosef Bacik btrfs_file_extent_encryption(leaf, fi) == 0 && 60054f03ab1SJosef Bacik btrfs_file_extent_other_encoding(leaf, fi) == 0 && 60154f03ab1SJosef Bacik btrfs_file_extent_compression(leaf, fi) == 0) { 60254f03ab1SJosef Bacik u32 size = (u32)(new_size - found_key.offset); 60354f03ab1SJosef Bacik 60454f03ab1SJosef Bacik btrfs_set_file_extent_ram_bytes(leaf, fi, size); 60554f03ab1SJosef Bacik size = btrfs_file_extent_calc_inline_size(size); 60654f03ab1SJosef Bacik btrfs_truncate_item(path, size, 1); 60754f03ab1SJosef Bacik } else if (!del_item) { 60854f03ab1SJosef Bacik /* 60954f03ab1SJosef Bacik * We have to bail so the last_size is set to 61054f03ab1SJosef Bacik * just before this extent. 61154f03ab1SJosef Bacik */ 61254f03ab1SJosef Bacik ret = BTRFS_NEED_TRUNCATE_BLOCK; 61354f03ab1SJosef Bacik break; 61454f03ab1SJosef Bacik } else { 61554f03ab1SJosef Bacik /* 61654f03ab1SJosef Bacik * Inline extents are special, we just treat 61754f03ab1SJosef Bacik * them as a full sector worth in the file 61854f03ab1SJosef Bacik * extent tree just for simplicity sake. 61954f03ab1SJosef Bacik */ 62054f03ab1SJosef Bacik clear_len = fs_info->sectorsize; 62154f03ab1SJosef Bacik } 62254f03ab1SJosef Bacik 623462b728eSJosef Bacik control->sub_bytes += item_end + 1 - new_size; 62454f03ab1SJosef Bacik } 62554f03ab1SJosef Bacik delete: 62654f03ab1SJosef Bacik /* 627*655807b8SJosef Bacik * We only want to clear the file extent range if we're 628*655807b8SJosef Bacik * modifying the actual inode's mapping, which is just the 629*655807b8SJosef Bacik * normal truncate path. 63054f03ab1SJosef Bacik */ 631*655807b8SJosef Bacik if (control->clear_extent_range) { 63254f03ab1SJosef Bacik ret = btrfs_inode_clear_file_extent_range(inode, 63354f03ab1SJosef Bacik clear_start, clear_len); 63454f03ab1SJosef Bacik if (ret) { 63554f03ab1SJosef Bacik btrfs_abort_transaction(trans, ret); 63654f03ab1SJosef Bacik break; 63754f03ab1SJosef Bacik } 63854f03ab1SJosef Bacik } 63954f03ab1SJosef Bacik 64054f03ab1SJosef Bacik if (del_item) 641c2ddb612SJosef Bacik control->last_size = found_key.offset; 64254f03ab1SJosef Bacik else 643c2ddb612SJosef Bacik control->last_size = new_size; 64454f03ab1SJosef Bacik if (del_item) { 64554f03ab1SJosef Bacik if (!pending_del_nr) { 64654f03ab1SJosef Bacik /* No pending yet, add ourselves */ 64754f03ab1SJosef Bacik pending_del_slot = path->slots[0]; 64854f03ab1SJosef Bacik pending_del_nr = 1; 64954f03ab1SJosef Bacik } else if (pending_del_nr && 65054f03ab1SJosef Bacik path->slots[0] + 1 == pending_del_slot) { 65154f03ab1SJosef Bacik /* Hop on the pending chunk */ 65254f03ab1SJosef Bacik pending_del_nr++; 65354f03ab1SJosef Bacik pending_del_slot = path->slots[0]; 65454f03ab1SJosef Bacik } else { 65554f03ab1SJosef Bacik BUG(); 65654f03ab1SJosef Bacik } 65754f03ab1SJosef Bacik } else { 65854f03ab1SJosef Bacik break; 65954f03ab1SJosef Bacik } 66054f03ab1SJosef Bacik should_throttle = false; 66154f03ab1SJosef Bacik 6625caa490eSJosef Bacik if (del_item && extent_start != 0 && !control->skip_ref_updates) { 66354f03ab1SJosef Bacik struct btrfs_ref ref = { 0 }; 66454f03ab1SJosef Bacik 66554f03ab1SJosef Bacik bytes_deleted += extent_num_bytes; 66654f03ab1SJosef Bacik 66754f03ab1SJosef Bacik btrfs_init_generic_ref(&ref, BTRFS_DROP_DELAYED_REF, 66854f03ab1SJosef Bacik extent_start, extent_num_bytes, 0); 66954f03ab1SJosef Bacik btrfs_init_data_ref(&ref, btrfs_header_owner(leaf), 67054f03ab1SJosef Bacik ino, extent_offset, 67154f03ab1SJosef Bacik root->root_key.objectid, false); 67254f03ab1SJosef Bacik ret = btrfs_free_extent(trans, &ref); 67354f03ab1SJosef Bacik if (ret) { 67454f03ab1SJosef Bacik btrfs_abort_transaction(trans, ret); 67554f03ab1SJosef Bacik break; 67654f03ab1SJosef Bacik } 67754f03ab1SJosef Bacik if (be_nice) { 67854f03ab1SJosef Bacik if (btrfs_should_throttle_delayed_refs(trans)) 67954f03ab1SJosef Bacik should_throttle = true; 68054f03ab1SJosef Bacik } 68154f03ab1SJosef Bacik } 68254f03ab1SJosef Bacik 68354f03ab1SJosef Bacik if (found_type == BTRFS_INODE_ITEM_KEY) 68454f03ab1SJosef Bacik break; 68554f03ab1SJosef Bacik 68654f03ab1SJosef Bacik if (path->slots[0] == 0 || 68754f03ab1SJosef Bacik path->slots[0] != pending_del_slot || 68854f03ab1SJosef Bacik should_throttle) { 68954f03ab1SJosef Bacik if (pending_del_nr) { 69054f03ab1SJosef Bacik ret = btrfs_del_items(trans, root, path, 69154f03ab1SJosef Bacik pending_del_slot, 69254f03ab1SJosef Bacik pending_del_nr); 69354f03ab1SJosef Bacik if (ret) { 69454f03ab1SJosef Bacik btrfs_abort_transaction(trans, ret); 69554f03ab1SJosef Bacik break; 69654f03ab1SJosef Bacik } 69754f03ab1SJosef Bacik pending_del_nr = 0; 69854f03ab1SJosef Bacik } 69954f03ab1SJosef Bacik btrfs_release_path(path); 70054f03ab1SJosef Bacik 70154f03ab1SJosef Bacik /* 70254f03ab1SJosef Bacik * We can generate a lot of delayed refs, so we need to 70354f03ab1SJosef Bacik * throttle every once and a while and make sure we're 70454f03ab1SJosef Bacik * adding enough space to keep up with the work we are 70554f03ab1SJosef Bacik * generating. Since we hold a transaction here we 70654f03ab1SJosef Bacik * can't flush, and we don't want to FLUSH_LIMIT because 70754f03ab1SJosef Bacik * we could have generated too many delayed refs to 70854f03ab1SJosef Bacik * actually allocate, so just bail if we're short and 70954f03ab1SJosef Bacik * let the normal reservation dance happen higher up. 71054f03ab1SJosef Bacik */ 71154f03ab1SJosef Bacik if (should_throttle) { 71254f03ab1SJosef Bacik ret = btrfs_delayed_refs_rsv_refill(fs_info, 71354f03ab1SJosef Bacik BTRFS_RESERVE_NO_FLUSH); 71454f03ab1SJosef Bacik if (ret) { 71554f03ab1SJosef Bacik ret = -EAGAIN; 71654f03ab1SJosef Bacik break; 71754f03ab1SJosef Bacik } 71854f03ab1SJosef Bacik } 71954f03ab1SJosef Bacik goto search_again; 72054f03ab1SJosef Bacik } else { 72154f03ab1SJosef Bacik path->slots[0]--; 72254f03ab1SJosef Bacik } 72354f03ab1SJosef Bacik } 72454f03ab1SJosef Bacik out: 72554f03ab1SJosef Bacik if (ret >= 0 && pending_del_nr) { 72654f03ab1SJosef Bacik int err; 72754f03ab1SJosef Bacik 72854f03ab1SJosef Bacik err = btrfs_del_items(trans, root, path, pending_del_slot, 72954f03ab1SJosef Bacik pending_del_nr); 73054f03ab1SJosef Bacik if (err) { 73154f03ab1SJosef Bacik btrfs_abort_transaction(trans, err); 73254f03ab1SJosef Bacik ret = err; 73354f03ab1SJosef Bacik } 73454f03ab1SJosef Bacik } 735c2ddb612SJosef Bacik 736c2ddb612SJosef Bacik ASSERT(control->last_size >= new_size); 737c2ddb612SJosef Bacik if (!ret && control->last_size > new_size) 738c2ddb612SJosef Bacik control->last_size = new_size; 73954f03ab1SJosef Bacik 74054f03ab1SJosef Bacik btrfs_free_path(path); 74154f03ab1SJosef Bacik return ret; 74254f03ab1SJosef Bacik } 743