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" 7ec8eb376SJosef Bacik #include "fs.h" 8ec8eb376SJosef Bacik #include "messages.h" 926c2c454SJosef Bacik #include "inode-item.h" 101e1d2701SChris Mason #include "disk-io.h" 11e089f05cSChris Mason #include "transaction.h" 12727011e0SChris Mason #include "print-tree.h" 13f1e5c618SJosef Bacik #include "space-info.h" 14*07e81dc9SJosef Bacik #include "accessors.h" 151e1d2701SChris Mason 169bb8407fSNikolay Borisov struct btrfs_inode_ref *btrfs_find_name_in_backref(struct extent_buffer *leaf, 179bb8407fSNikolay Borisov int slot, const char *name, 189bb8407fSNikolay Borisov int name_len) 193954401fSChris Mason { 203954401fSChris Mason struct btrfs_inode_ref *ref; 213954401fSChris Mason unsigned long ptr; 223954401fSChris Mason unsigned long name_ptr; 233954401fSChris Mason u32 item_size; 243954401fSChris Mason u32 cur_offset = 0; 253954401fSChris Mason int len; 263954401fSChris Mason 273212fa14SJosef Bacik item_size = btrfs_item_size(leaf, slot); 281f250e92SFilipe Manana ptr = btrfs_item_ptr_offset(leaf, slot); 293954401fSChris Mason while (cur_offset < item_size) { 303954401fSChris Mason ref = (struct btrfs_inode_ref *)(ptr + cur_offset); 313954401fSChris Mason len = btrfs_inode_ref_name_len(leaf, ref); 323954401fSChris Mason name_ptr = (unsigned long)(ref + 1); 333954401fSChris Mason cur_offset += len + sizeof(*ref); 343954401fSChris Mason if (len != name_len) 353954401fSChris Mason continue; 369bb8407fSNikolay Borisov if (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0) 379bb8407fSNikolay Borisov return ref; 383954401fSChris Mason } 399bb8407fSNikolay Borisov return NULL; 403954401fSChris Mason } 413954401fSChris Mason 426ff49c6aSNikolay Borisov struct btrfs_inode_extref *btrfs_find_name_in_ext_backref( 436ff49c6aSNikolay Borisov struct extent_buffer *leaf, int slot, u64 ref_objectid, 446ff49c6aSNikolay Borisov const char *name, int name_len) 45f186373fSMark Fasheh { 46f186373fSMark Fasheh struct btrfs_inode_extref *extref; 47f186373fSMark Fasheh unsigned long ptr; 48f186373fSMark Fasheh unsigned long name_ptr; 49f186373fSMark Fasheh u32 item_size; 50f186373fSMark Fasheh u32 cur_offset = 0; 51f186373fSMark Fasheh int ref_name_len; 52f186373fSMark Fasheh 533212fa14SJosef Bacik item_size = btrfs_item_size(leaf, slot); 541f250e92SFilipe Manana ptr = btrfs_item_ptr_offset(leaf, slot); 55f186373fSMark Fasheh 56f186373fSMark Fasheh /* 57f186373fSMark Fasheh * Search all extended backrefs in this item. We're only 58f186373fSMark Fasheh * looking through any collisions so most of the time this is 59f186373fSMark Fasheh * just going to compare against one buffer. If all is well, 60f186373fSMark Fasheh * we'll return success and the inode ref object. 61f186373fSMark Fasheh */ 62f186373fSMark Fasheh while (cur_offset < item_size) { 63f186373fSMark Fasheh extref = (struct btrfs_inode_extref *) (ptr + cur_offset); 64f186373fSMark Fasheh name_ptr = (unsigned long)(&extref->name); 65f186373fSMark Fasheh ref_name_len = btrfs_inode_extref_name_len(leaf, extref); 66f186373fSMark Fasheh 67f186373fSMark Fasheh if (ref_name_len == name_len && 68f186373fSMark Fasheh btrfs_inode_extref_parent(leaf, extref) == ref_objectid && 696ff49c6aSNikolay Borisov (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == 0)) 706ff49c6aSNikolay Borisov return extref; 71f186373fSMark Fasheh 72f186373fSMark Fasheh cur_offset += ref_name_len + sizeof(*extref); 73f186373fSMark Fasheh } 746ff49c6aSNikolay Borisov return NULL; 75f186373fSMark Fasheh } 76f186373fSMark Fasheh 77f186373fSMark Fasheh /* Returns NULL if no extref found */ 78f186373fSMark Fasheh struct btrfs_inode_extref * 79f186373fSMark Fasheh btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans, 80f186373fSMark Fasheh struct btrfs_root *root, 81f186373fSMark Fasheh struct btrfs_path *path, 82f186373fSMark Fasheh const char *name, int name_len, 83f186373fSMark Fasheh u64 inode_objectid, u64 ref_objectid, int ins_len, 84f186373fSMark Fasheh int cow) 85f186373fSMark Fasheh { 86f186373fSMark Fasheh int ret; 87f186373fSMark Fasheh struct btrfs_key key; 88f186373fSMark Fasheh 89f186373fSMark Fasheh key.objectid = inode_objectid; 90f186373fSMark Fasheh key.type = BTRFS_INODE_EXTREF_KEY; 91f186373fSMark Fasheh key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 92f186373fSMark Fasheh 93f186373fSMark Fasheh ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); 94f186373fSMark Fasheh if (ret < 0) 95f186373fSMark Fasheh return ERR_PTR(ret); 96f186373fSMark Fasheh if (ret > 0) 97f186373fSMark Fasheh return NULL; 986ff49c6aSNikolay Borisov return btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0], 996ff49c6aSNikolay Borisov ref_objectid, name, name_len); 1006ff49c6aSNikolay Borisov 101f186373fSMark Fasheh } 102f186373fSMark Fasheh 10348a3b636SEric Sandeen static int btrfs_del_inode_extref(struct btrfs_trans_handle *trans, 104f186373fSMark Fasheh struct btrfs_root *root, 105f186373fSMark Fasheh const char *name, int name_len, 10648a3b636SEric Sandeen u64 inode_objectid, u64 ref_objectid, 10748a3b636SEric Sandeen u64 *index) 108f186373fSMark Fasheh { 109f186373fSMark Fasheh struct btrfs_path *path; 110f186373fSMark Fasheh struct btrfs_key key; 111f186373fSMark Fasheh struct btrfs_inode_extref *extref; 112f186373fSMark Fasheh struct extent_buffer *leaf; 113f186373fSMark Fasheh int ret; 114f186373fSMark Fasheh int del_len = name_len + sizeof(*extref); 115f186373fSMark Fasheh unsigned long ptr; 116f186373fSMark Fasheh unsigned long item_start; 117f186373fSMark Fasheh u32 item_size; 118f186373fSMark Fasheh 119f186373fSMark Fasheh key.objectid = inode_objectid; 120962a298fSDavid Sterba key.type = BTRFS_INODE_EXTREF_KEY; 121f186373fSMark Fasheh key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 122f186373fSMark Fasheh 123f186373fSMark Fasheh path = btrfs_alloc_path(); 124f186373fSMark Fasheh if (!path) 125f186373fSMark Fasheh return -ENOMEM; 126f186373fSMark Fasheh 127f186373fSMark Fasheh ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 128f186373fSMark Fasheh if (ret > 0) 129f186373fSMark Fasheh ret = -ENOENT; 130f186373fSMark Fasheh if (ret < 0) 131f186373fSMark Fasheh goto out; 132f186373fSMark Fasheh 133f186373fSMark Fasheh /* 134f186373fSMark Fasheh * Sanity check - did we find the right item for this name? 135f186373fSMark Fasheh * This should always succeed so error here will make the FS 136f186373fSMark Fasheh * readonly. 137f186373fSMark Fasheh */ 1386ff49c6aSNikolay Borisov extref = btrfs_find_name_in_ext_backref(path->nodes[0], path->slots[0], 1396ff49c6aSNikolay Borisov ref_objectid, name, name_len); 1406ff49c6aSNikolay Borisov if (!extref) { 14134d97007SAnand Jain btrfs_handle_fs_error(root->fs_info, -ENOENT, NULL); 142f186373fSMark Fasheh ret = -EROFS; 143f186373fSMark Fasheh goto out; 144f186373fSMark Fasheh } 145f186373fSMark Fasheh 146f186373fSMark Fasheh leaf = path->nodes[0]; 1473212fa14SJosef Bacik item_size = btrfs_item_size(leaf, path->slots[0]); 148f186373fSMark Fasheh if (index) 149f186373fSMark Fasheh *index = btrfs_inode_extref_index(leaf, extref); 150f186373fSMark Fasheh 151f186373fSMark Fasheh if (del_len == item_size) { 152f186373fSMark Fasheh /* 153f186373fSMark Fasheh * Common case only one ref in the item, remove the 154f186373fSMark Fasheh * whole item. 155f186373fSMark Fasheh */ 156f186373fSMark Fasheh ret = btrfs_del_item(trans, root, path); 157f186373fSMark Fasheh goto out; 158f186373fSMark Fasheh } 159f186373fSMark Fasheh 160f186373fSMark Fasheh ptr = (unsigned long)extref; 161f186373fSMark Fasheh item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 162f186373fSMark Fasheh 163f186373fSMark Fasheh memmove_extent_buffer(leaf, ptr, ptr + del_len, 164f186373fSMark Fasheh item_size - (ptr + del_len - item_start)); 165f186373fSMark Fasheh 16678ac4f9eSDavid Sterba btrfs_truncate_item(path, item_size - del_len, 1); 167f186373fSMark Fasheh 168f186373fSMark Fasheh out: 169f186373fSMark Fasheh btrfs_free_path(path); 170f186373fSMark Fasheh 171f186373fSMark Fasheh return ret; 172f186373fSMark Fasheh } 173f186373fSMark Fasheh 1743954401fSChris Mason int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, 1753954401fSChris Mason struct btrfs_root *root, 1763954401fSChris Mason const char *name, int name_len, 177aec7477bSJosef Bacik u64 inode_objectid, u64 ref_objectid, u64 *index) 1783954401fSChris Mason { 1793954401fSChris Mason struct btrfs_path *path; 1803954401fSChris Mason struct btrfs_key key; 1813954401fSChris Mason struct btrfs_inode_ref *ref; 1823954401fSChris Mason struct extent_buffer *leaf; 1833954401fSChris Mason unsigned long ptr; 1843954401fSChris Mason unsigned long item_start; 1853954401fSChris Mason u32 item_size; 1863954401fSChris Mason u32 sub_item_len; 1873954401fSChris Mason int ret; 188f186373fSMark Fasheh int search_ext_refs = 0; 1893954401fSChris Mason int del_len = name_len + sizeof(*ref); 1903954401fSChris Mason 1913954401fSChris Mason key.objectid = inode_objectid; 1923954401fSChris Mason key.offset = ref_objectid; 193962a298fSDavid Sterba key.type = BTRFS_INODE_REF_KEY; 1943954401fSChris Mason 1953954401fSChris Mason path = btrfs_alloc_path(); 1963954401fSChris Mason if (!path) 1973954401fSChris Mason return -ENOMEM; 1983954401fSChris Mason 1993954401fSChris Mason ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 2003954401fSChris Mason if (ret > 0) { 2013954401fSChris Mason ret = -ENOENT; 202f186373fSMark Fasheh search_ext_refs = 1; 2033954401fSChris Mason goto out; 2043954401fSChris Mason } else if (ret < 0) { 2053954401fSChris Mason goto out; 2063954401fSChris Mason } 2079bb8407fSNikolay Borisov 2089bb8407fSNikolay Borisov ref = btrfs_find_name_in_backref(path->nodes[0], path->slots[0], name, 2099bb8407fSNikolay Borisov name_len); 2109bb8407fSNikolay Borisov if (!ref) { 2113954401fSChris Mason ret = -ENOENT; 212f186373fSMark Fasheh search_ext_refs = 1; 2133954401fSChris Mason goto out; 2143954401fSChris Mason } 2153954401fSChris Mason leaf = path->nodes[0]; 2163212fa14SJosef Bacik item_size = btrfs_item_size(leaf, path->slots[0]); 217aec7477bSJosef Bacik 218aec7477bSJosef Bacik if (index) 219aec7477bSJosef Bacik *index = btrfs_inode_ref_index(leaf, ref); 220aec7477bSJosef Bacik 2213954401fSChris Mason if (del_len == item_size) { 2223954401fSChris Mason ret = btrfs_del_item(trans, root, path); 2233954401fSChris Mason goto out; 2243954401fSChris Mason } 2253954401fSChris Mason ptr = (unsigned long)ref; 2263954401fSChris Mason sub_item_len = name_len + sizeof(*ref); 2273954401fSChris Mason item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); 2283954401fSChris Mason memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, 2293954401fSChris Mason item_size - (ptr + sub_item_len - item_start)); 23078ac4f9eSDavid Sterba btrfs_truncate_item(path, item_size - sub_item_len, 1); 231f186373fSMark Fasheh out: 232f186373fSMark Fasheh btrfs_free_path(path); 233f186373fSMark Fasheh 234f186373fSMark Fasheh if (search_ext_refs) { 235f186373fSMark Fasheh /* 236f186373fSMark Fasheh * No refs were found, or we could not find the 237f186373fSMark Fasheh * name in our ref array. Find and remove the extended 238f186373fSMark Fasheh * inode ref then. 239f186373fSMark Fasheh */ 240f186373fSMark Fasheh return btrfs_del_inode_extref(trans, root, name, name_len, 241f186373fSMark Fasheh inode_objectid, ref_objectid, index); 242f186373fSMark Fasheh } 243f186373fSMark Fasheh 244f186373fSMark Fasheh return ret; 245f186373fSMark Fasheh } 246f186373fSMark Fasheh 247f186373fSMark Fasheh /* 248f186373fSMark Fasheh * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree. 249f186373fSMark Fasheh * 250f186373fSMark Fasheh * The caller must have checked against BTRFS_LINK_MAX already. 251f186373fSMark Fasheh */ 252f186373fSMark Fasheh static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans, 253f186373fSMark Fasheh struct btrfs_root *root, 254f186373fSMark Fasheh const char *name, int name_len, 255f186373fSMark Fasheh u64 inode_objectid, u64 ref_objectid, u64 index) 256f186373fSMark Fasheh { 257f186373fSMark Fasheh struct btrfs_inode_extref *extref; 258f186373fSMark Fasheh int ret; 259f186373fSMark Fasheh int ins_len = name_len + sizeof(*extref); 260f186373fSMark Fasheh unsigned long ptr; 261f186373fSMark Fasheh struct btrfs_path *path; 262f186373fSMark Fasheh struct btrfs_key key; 263f186373fSMark Fasheh struct extent_buffer *leaf; 264f186373fSMark Fasheh 265f186373fSMark Fasheh key.objectid = inode_objectid; 266f186373fSMark Fasheh key.type = BTRFS_INODE_EXTREF_KEY; 267f186373fSMark Fasheh key.offset = btrfs_extref_hash(ref_objectid, name, name_len); 268f186373fSMark Fasheh 269f186373fSMark Fasheh path = btrfs_alloc_path(); 270f186373fSMark Fasheh if (!path) 271f186373fSMark Fasheh return -ENOMEM; 272f186373fSMark Fasheh 273f186373fSMark Fasheh ret = btrfs_insert_empty_item(trans, root, path, &key, 274f186373fSMark Fasheh ins_len); 275f186373fSMark Fasheh if (ret == -EEXIST) { 2761f250e92SFilipe Manana if (btrfs_find_name_in_ext_backref(path->nodes[0], 2771f250e92SFilipe Manana path->slots[0], 2781f250e92SFilipe Manana ref_objectid, 2796ff49c6aSNikolay Borisov name, name_len)) 280f186373fSMark Fasheh goto out; 281f186373fSMark Fasheh 282c71dd880SDavid Sterba btrfs_extend_item(path, ins_len); 283f186373fSMark Fasheh ret = 0; 284f186373fSMark Fasheh } 285f186373fSMark Fasheh if (ret < 0) 286f186373fSMark Fasheh goto out; 287f186373fSMark Fasheh 288f186373fSMark Fasheh leaf = path->nodes[0]; 289f186373fSMark Fasheh ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char); 2903212fa14SJosef Bacik ptr += btrfs_item_size(leaf, path->slots[0]) - ins_len; 291f186373fSMark Fasheh extref = (struct btrfs_inode_extref *)ptr; 292f186373fSMark Fasheh 293f186373fSMark Fasheh btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len); 294f186373fSMark Fasheh btrfs_set_inode_extref_index(path->nodes[0], extref, index); 295f186373fSMark Fasheh btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid); 296f186373fSMark Fasheh 297f186373fSMark Fasheh ptr = (unsigned long)&extref->name; 298f186373fSMark Fasheh write_extent_buffer(path->nodes[0], name, ptr, name_len); 299f186373fSMark Fasheh btrfs_mark_buffer_dirty(path->nodes[0]); 300f186373fSMark Fasheh 3013954401fSChris Mason out: 3023954401fSChris Mason btrfs_free_path(path); 3033954401fSChris Mason return ret; 3043954401fSChris Mason } 3053954401fSChris Mason 30679787eaaSJeff Mahoney /* Will return 0, -ENOMEM, -EMLINK, or -EEXIST or anything from the CoW path */ 3073954401fSChris Mason int btrfs_insert_inode_ref(struct btrfs_trans_handle *trans, 3083954401fSChris Mason struct btrfs_root *root, 3093954401fSChris Mason const char *name, int name_len, 310aec7477bSJosef Bacik u64 inode_objectid, u64 ref_objectid, u64 index) 3113954401fSChris Mason { 3120b246afaSJeff Mahoney struct btrfs_fs_info *fs_info = root->fs_info; 3133954401fSChris Mason struct btrfs_path *path; 3143954401fSChris Mason struct btrfs_key key; 3153954401fSChris Mason struct btrfs_inode_ref *ref; 3163954401fSChris Mason unsigned long ptr; 3173954401fSChris Mason int ret; 3183954401fSChris Mason int ins_len = name_len + sizeof(*ref); 3193954401fSChris Mason 3203954401fSChris Mason key.objectid = inode_objectid; 3213954401fSChris Mason key.offset = ref_objectid; 322962a298fSDavid Sterba key.type = BTRFS_INODE_REF_KEY; 3233954401fSChris Mason 3243954401fSChris Mason path = btrfs_alloc_path(); 3253954401fSChris Mason if (!path) 3263954401fSChris Mason return -ENOMEM; 3273954401fSChris Mason 328df8d116fSFilipe Manana path->skip_release_on_error = 1; 3293954401fSChris Mason ret = btrfs_insert_empty_item(trans, root, path, &key, 3303954401fSChris Mason ins_len); 3313954401fSChris Mason if (ret == -EEXIST) { 3323954401fSChris Mason u32 old_size; 3339bb8407fSNikolay Borisov ref = btrfs_find_name_in_backref(path->nodes[0], path->slots[0], 3349bb8407fSNikolay Borisov name, name_len); 3359bb8407fSNikolay Borisov if (ref) 3363954401fSChris Mason goto out; 3373954401fSChris Mason 3383212fa14SJosef Bacik old_size = btrfs_item_size(path->nodes[0], path->slots[0]); 339c71dd880SDavid Sterba btrfs_extend_item(path, ins_len); 3403954401fSChris Mason ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 3413954401fSChris Mason struct btrfs_inode_ref); 3423954401fSChris Mason ref = (struct btrfs_inode_ref *)((unsigned long)ref + old_size); 3433954401fSChris Mason btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 344aec7477bSJosef Bacik btrfs_set_inode_ref_index(path->nodes[0], ref, index); 3453954401fSChris Mason ptr = (unsigned long)(ref + 1); 3463954401fSChris Mason ret = 0; 3473954401fSChris Mason } else if (ret < 0) { 348df8d116fSFilipe Manana if (ret == -EOVERFLOW) { 3491f250e92SFilipe Manana if (btrfs_find_name_in_backref(path->nodes[0], 3501f250e92SFilipe Manana path->slots[0], 3519bb8407fSNikolay Borisov name, name_len)) 352df8d116fSFilipe Manana ret = -EEXIST; 353df8d116fSFilipe Manana else 354a5719521SYan, Zheng ret = -EMLINK; 355df8d116fSFilipe Manana } 3563954401fSChris Mason goto out; 3573954401fSChris Mason } else { 3583954401fSChris Mason ref = btrfs_item_ptr(path->nodes[0], path->slots[0], 3593954401fSChris Mason struct btrfs_inode_ref); 3603954401fSChris Mason btrfs_set_inode_ref_name_len(path->nodes[0], ref, name_len); 361aec7477bSJosef Bacik btrfs_set_inode_ref_index(path->nodes[0], ref, index); 3623954401fSChris Mason ptr = (unsigned long)(ref + 1); 3633954401fSChris Mason } 3643954401fSChris Mason write_extent_buffer(path->nodes[0], name, ptr, name_len); 3653954401fSChris Mason btrfs_mark_buffer_dirty(path->nodes[0]); 3663954401fSChris Mason 3673954401fSChris Mason out: 3683954401fSChris Mason btrfs_free_path(path); 369f186373fSMark Fasheh 370f186373fSMark Fasheh if (ret == -EMLINK) { 3710b246afaSJeff Mahoney struct btrfs_super_block *disk_super = fs_info->super_copy; 372f186373fSMark Fasheh /* We ran out of space in the ref array. Need to 373f186373fSMark Fasheh * add an extended ref. */ 374f186373fSMark Fasheh if (btrfs_super_incompat_flags(disk_super) 375f186373fSMark Fasheh & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) 376f186373fSMark Fasheh ret = btrfs_insert_inode_extref(trans, root, name, 377f186373fSMark Fasheh name_len, 378f186373fSMark Fasheh inode_objectid, 379f186373fSMark Fasheh ref_objectid, index); 380f186373fSMark Fasheh } 381f186373fSMark Fasheh 3823954401fSChris Mason return ret; 3833954401fSChris Mason } 3843954401fSChris Mason 3855f39d397SChris Mason int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans, 3865f39d397SChris Mason struct btrfs_root *root, 3875f39d397SChris Mason struct btrfs_path *path, u64 objectid) 3881e1d2701SChris Mason { 3891e1d2701SChris Mason struct btrfs_key key; 3901e1d2701SChris Mason int ret; 3911e1d2701SChris Mason key.objectid = objectid; 392962a298fSDavid Sterba key.type = BTRFS_INODE_ITEM_KEY; 3931e1d2701SChris Mason key.offset = 0; 3941e1d2701SChris Mason 3955f39d397SChris Mason ret = btrfs_insert_empty_item(trans, root, path, &key, 3965f39d397SChris Mason sizeof(struct btrfs_inode_item)); 3971e1d2701SChris Mason return ret; 3981e1d2701SChris Mason } 3991e1d2701SChris Mason 400e089f05cSChris Mason int btrfs_lookup_inode(struct btrfs_trans_handle *trans, struct btrfs_root 401d6e4a428SChris Mason *root, struct btrfs_path *path, 402d6e4a428SChris Mason struct btrfs_key *location, int mod) 4031e1d2701SChris Mason { 4041e1d2701SChris Mason int ins_len = mod < 0 ? -1 : 0; 4051e1d2701SChris Mason int cow = mod != 0; 406d6e4a428SChris Mason int ret; 407d6e4a428SChris Mason int slot; 4085f39d397SChris Mason struct extent_buffer *leaf; 409d6e4a428SChris Mason struct btrfs_key found_key; 4101e1d2701SChris Mason 411d6e4a428SChris Mason ret = btrfs_search_slot(trans, root, location, path, ins_len, cow); 412962a298fSDavid Sterba if (ret > 0 && location->type == BTRFS_ROOT_ITEM_KEY && 413d6e4a428SChris Mason location->offset == (u64)-1 && path->slots[0] != 0) { 414d6e4a428SChris Mason slot = path->slots[0] - 1; 4155f39d397SChris Mason leaf = path->nodes[0]; 4165f39d397SChris Mason btrfs_item_key_to_cpu(leaf, &found_key, slot); 417d6e4a428SChris Mason if (found_key.objectid == location->objectid && 418962a298fSDavid Sterba found_key.type == location->type) { 419d6e4a428SChris Mason path->slots[0]--; 420d6e4a428SChris Mason return 0; 421d6e4a428SChris Mason } 422d6e4a428SChris Mason } 423d6e4a428SChris Mason return ret; 4241e1d2701SChris Mason } 42554f03ab1SJosef Bacik 42671d18b53SJosef Bacik static inline void btrfs_trace_truncate(struct btrfs_inode *inode, 42771d18b53SJosef Bacik struct extent_buffer *leaf, 42871d18b53SJosef Bacik struct btrfs_file_extent_item *fi, 42971d18b53SJosef Bacik u64 offset, int extent_type, int slot) 43071d18b53SJosef Bacik { 43171d18b53SJosef Bacik if (!inode) 43271d18b53SJosef Bacik return; 43371d18b53SJosef Bacik if (extent_type == BTRFS_FILE_EXTENT_INLINE) 43471d18b53SJosef Bacik trace_btrfs_truncate_show_fi_inline(inode, leaf, fi, slot, 43571d18b53SJosef Bacik offset); 43671d18b53SJosef Bacik else 43771d18b53SJosef Bacik trace_btrfs_truncate_show_fi_regular(inode, leaf, fi, offset); 43871d18b53SJosef Bacik } 43971d18b53SJosef Bacik 44054f03ab1SJosef Bacik /* 44154f03ab1SJosef Bacik * Remove inode items from a given root. 44254f03ab1SJosef Bacik * 44354f03ab1SJosef Bacik * @trans: A transaction handle. 44454f03ab1SJosef Bacik * @root: The root from which to remove items. 44554f03ab1SJosef Bacik * @inode: The inode whose items we want to remove. 446d9ac19c3SJosef Bacik * @control: The btrfs_truncate_control to control how and what we 447d9ac19c3SJosef Bacik * are truncating. 44854f03ab1SJosef Bacik * 44954f03ab1SJosef Bacik * Remove all keys associated with the inode from the given root that have a key 45054f03ab1SJosef Bacik * with a type greater than or equals to @min_type. When @min_type has a value of 45154f03ab1SJosef Bacik * BTRFS_EXTENT_DATA_KEY, only remove file extent items that have an offset value 45254f03ab1SJosef Bacik * greater than or equals to @new_size. If a file extent item that starts before 45354f03ab1SJosef Bacik * @new_size and ends after it is found, its length is adjusted. 45454f03ab1SJosef Bacik * 45554f03ab1SJosef Bacik * Returns: 0 on success, < 0 on error and NEED_TRUNCATE_BLOCK when @min_type is 45654f03ab1SJosef Bacik * BTRFS_EXTENT_DATA_KEY and the caller must truncate the last block. 45754f03ab1SJosef Bacik */ 45854f03ab1SJosef Bacik int btrfs_truncate_inode_items(struct btrfs_trans_handle *trans, 45954f03ab1SJosef Bacik struct btrfs_root *root, 460d9ac19c3SJosef Bacik struct btrfs_truncate_control *control) 46154f03ab1SJosef Bacik { 46254f03ab1SJosef Bacik struct btrfs_fs_info *fs_info = root->fs_info; 46354f03ab1SJosef Bacik struct btrfs_path *path; 46454f03ab1SJosef Bacik struct extent_buffer *leaf; 46554f03ab1SJosef Bacik struct btrfs_file_extent_item *fi; 46654f03ab1SJosef Bacik struct btrfs_key key; 46754f03ab1SJosef Bacik struct btrfs_key found_key; 468d9ac19c3SJosef Bacik u64 new_size = control->new_size; 46954f03ab1SJosef Bacik u64 extent_num_bytes = 0; 47054f03ab1SJosef Bacik u64 extent_offset = 0; 47154f03ab1SJosef Bacik u64 item_end = 0; 47254f03ab1SJosef Bacik u32 found_type = (u8)-1; 47354f03ab1SJosef Bacik int del_item; 47454f03ab1SJosef Bacik int pending_del_nr = 0; 47554f03ab1SJosef Bacik int pending_del_slot = 0; 47654f03ab1SJosef Bacik int extent_type = -1; 47754f03ab1SJosef Bacik int ret; 47854f03ab1SJosef Bacik u64 bytes_deleted = 0; 47954f03ab1SJosef Bacik bool be_nice = false; 48054f03ab1SJosef Bacik 48171d18b53SJosef Bacik ASSERT(control->inode || !control->clear_extent_range); 48256e1edb0SJosef Bacik ASSERT(new_size == 0 || control->min_type == BTRFS_EXTENT_DATA_KEY); 48354f03ab1SJosef Bacik 484c2ddb612SJosef Bacik control->last_size = new_size; 485462b728eSJosef Bacik control->sub_bytes = 0; 486c2ddb612SJosef Bacik 48754f03ab1SJosef Bacik /* 488275312a0SJosef Bacik * For shareable roots we want to back off from time to time, this turns 489275312a0SJosef Bacik * out to be subvolume roots, reloc roots, and data reloc roots. 49054f03ab1SJosef Bacik */ 491275312a0SJosef Bacik if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) 49254f03ab1SJosef Bacik be_nice = true; 49354f03ab1SJosef Bacik 49454f03ab1SJosef Bacik path = btrfs_alloc_path(); 49554f03ab1SJosef Bacik if (!path) 49654f03ab1SJosef Bacik return -ENOMEM; 49754f03ab1SJosef Bacik path->reada = READA_BACK; 49854f03ab1SJosef Bacik 499487e81d2SJosef Bacik key.objectid = control->ino; 50054f03ab1SJosef Bacik key.offset = (u64)-1; 50154f03ab1SJosef Bacik key.type = (u8)-1; 50254f03ab1SJosef Bacik 50354f03ab1SJosef Bacik search_again: 50454f03ab1SJosef Bacik /* 50554f03ab1SJosef Bacik * With a 16K leaf size and 128MiB extents, you can actually queue up a 50654f03ab1SJosef Bacik * huge file in a single leaf. Most of the time that bytes_deleted is 50754f03ab1SJosef Bacik * > 0, it will be huge by the time we get here 50854f03ab1SJosef Bacik */ 50954f03ab1SJosef Bacik if (be_nice && bytes_deleted > SZ_32M && 51054f03ab1SJosef Bacik btrfs_should_end_transaction(trans)) { 51154f03ab1SJosef Bacik ret = -EAGAIN; 51254f03ab1SJosef Bacik goto out; 51354f03ab1SJosef Bacik } 51454f03ab1SJosef Bacik 51554f03ab1SJosef Bacik ret = btrfs_search_slot(trans, root, &key, path, -1, 1); 51654f03ab1SJosef Bacik if (ret < 0) 51754f03ab1SJosef Bacik goto out; 51854f03ab1SJosef Bacik 51954f03ab1SJosef Bacik if (ret > 0) { 52054f03ab1SJosef Bacik ret = 0; 52154f03ab1SJosef Bacik /* There are no items in the tree for us to truncate, we're done */ 52254f03ab1SJosef Bacik if (path->slots[0] == 0) 52354f03ab1SJosef Bacik goto out; 52454f03ab1SJosef Bacik path->slots[0]--; 52554f03ab1SJosef Bacik } 52654f03ab1SJosef Bacik 52754f03ab1SJosef Bacik while (1) { 5287097a941SJosef Bacik u64 clear_start = 0, clear_len = 0, extent_start = 0; 529e48dac7fSJosef Bacik bool should_throttle = false; 53054f03ab1SJosef Bacik 53154f03ab1SJosef Bacik fi = NULL; 53254f03ab1SJosef Bacik leaf = path->nodes[0]; 53354f03ab1SJosef Bacik btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 53454f03ab1SJosef Bacik found_type = found_key.type; 53554f03ab1SJosef Bacik 536487e81d2SJosef Bacik if (found_key.objectid != control->ino) 53754f03ab1SJosef Bacik break; 53854f03ab1SJosef Bacik 539d9ac19c3SJosef Bacik if (found_type < control->min_type) 54054f03ab1SJosef Bacik break; 54154f03ab1SJosef Bacik 54254f03ab1SJosef Bacik item_end = found_key.offset; 54354f03ab1SJosef Bacik if (found_type == BTRFS_EXTENT_DATA_KEY) { 54454f03ab1SJosef Bacik fi = btrfs_item_ptr(leaf, path->slots[0], 54554f03ab1SJosef Bacik struct btrfs_file_extent_item); 54654f03ab1SJosef Bacik extent_type = btrfs_file_extent_type(leaf, fi); 54771d18b53SJosef Bacik if (extent_type != BTRFS_FILE_EXTENT_INLINE) 54854f03ab1SJosef Bacik item_end += 54954f03ab1SJosef Bacik btrfs_file_extent_num_bytes(leaf, fi); 55071d18b53SJosef Bacik else if (extent_type == BTRFS_FILE_EXTENT_INLINE) 55154f03ab1SJosef Bacik item_end += btrfs_file_extent_ram_bytes(leaf, fi); 55254f03ab1SJosef Bacik 55371d18b53SJosef Bacik btrfs_trace_truncate(control->inode, leaf, fi, 55471d18b53SJosef Bacik found_key.offset, extent_type, 55571d18b53SJosef Bacik path->slots[0]); 55654f03ab1SJosef Bacik item_end--; 55754f03ab1SJosef Bacik } 558d9ac19c3SJosef Bacik if (found_type > control->min_type) { 55954f03ab1SJosef Bacik del_item = 1; 56054f03ab1SJosef Bacik } else { 56154f03ab1SJosef Bacik if (item_end < new_size) 56254f03ab1SJosef Bacik break; 56354f03ab1SJosef Bacik if (found_key.offset >= new_size) 56454f03ab1SJosef Bacik del_item = 1; 56554f03ab1SJosef Bacik else 56654f03ab1SJosef Bacik del_item = 0; 56754f03ab1SJosef Bacik } 5687097a941SJosef Bacik 56954f03ab1SJosef Bacik /* FIXME, shrink the extent if the ref count is only 1 */ 57054f03ab1SJosef Bacik if (found_type != BTRFS_EXTENT_DATA_KEY) 57154f03ab1SJosef Bacik goto delete; 57254f03ab1SJosef Bacik 573d9ac19c3SJosef Bacik control->extents_found++; 57454f03ab1SJosef Bacik 57554f03ab1SJosef Bacik if (extent_type != BTRFS_FILE_EXTENT_INLINE) { 57654f03ab1SJosef Bacik u64 num_dec; 57754f03ab1SJosef Bacik 57854f03ab1SJosef Bacik clear_start = found_key.offset; 57954f03ab1SJosef Bacik extent_start = btrfs_file_extent_disk_bytenr(leaf, fi); 58054f03ab1SJosef Bacik if (!del_item) { 58154f03ab1SJosef Bacik u64 orig_num_bytes = 58254f03ab1SJosef Bacik btrfs_file_extent_num_bytes(leaf, fi); 58354f03ab1SJosef Bacik extent_num_bytes = ALIGN(new_size - 58454f03ab1SJosef Bacik found_key.offset, 58554f03ab1SJosef Bacik fs_info->sectorsize); 58654f03ab1SJosef Bacik clear_start = ALIGN(new_size, fs_info->sectorsize); 58754f03ab1SJosef Bacik 58854f03ab1SJosef Bacik btrfs_set_file_extent_num_bytes(leaf, fi, 58954f03ab1SJosef Bacik extent_num_bytes); 59054f03ab1SJosef Bacik num_dec = (orig_num_bytes - extent_num_bytes); 591462b728eSJosef Bacik if (extent_start != 0) 592462b728eSJosef Bacik control->sub_bytes += num_dec; 59354f03ab1SJosef Bacik btrfs_mark_buffer_dirty(leaf); 59454f03ab1SJosef Bacik } else { 59554f03ab1SJosef Bacik extent_num_bytes = 59654f03ab1SJosef Bacik btrfs_file_extent_disk_num_bytes(leaf, fi); 59754f03ab1SJosef Bacik extent_offset = found_key.offset - 59854f03ab1SJosef Bacik btrfs_file_extent_offset(leaf, fi); 59954f03ab1SJosef Bacik 60054f03ab1SJosef Bacik /* FIXME blocksize != 4096 */ 60154f03ab1SJosef Bacik num_dec = btrfs_file_extent_num_bytes(leaf, fi); 602462b728eSJosef Bacik if (extent_start != 0) 603462b728eSJosef Bacik control->sub_bytes += num_dec; 60454f03ab1SJosef Bacik } 60554f03ab1SJosef Bacik clear_len = num_dec; 60654f03ab1SJosef Bacik } else if (extent_type == BTRFS_FILE_EXTENT_INLINE) { 60754f03ab1SJosef Bacik /* 60854f03ab1SJosef Bacik * We can't truncate inline items that have had 60954f03ab1SJosef Bacik * special encodings 61054f03ab1SJosef Bacik */ 61154f03ab1SJosef Bacik if (!del_item && 61254f03ab1SJosef Bacik btrfs_file_extent_encryption(leaf, fi) == 0 && 61354f03ab1SJosef Bacik btrfs_file_extent_other_encoding(leaf, fi) == 0 && 61454f03ab1SJosef Bacik btrfs_file_extent_compression(leaf, fi) == 0) { 61554f03ab1SJosef Bacik u32 size = (u32)(new_size - found_key.offset); 61654f03ab1SJosef Bacik 61754f03ab1SJosef Bacik btrfs_set_file_extent_ram_bytes(leaf, fi, size); 61854f03ab1SJosef Bacik size = btrfs_file_extent_calc_inline_size(size); 61954f03ab1SJosef Bacik btrfs_truncate_item(path, size, 1); 62054f03ab1SJosef Bacik } else if (!del_item) { 62154f03ab1SJosef Bacik /* 62254f03ab1SJosef Bacik * We have to bail so the last_size is set to 62354f03ab1SJosef Bacik * just before this extent. 62454f03ab1SJosef Bacik */ 62554f03ab1SJosef Bacik ret = BTRFS_NEED_TRUNCATE_BLOCK; 62654f03ab1SJosef Bacik break; 62754f03ab1SJosef Bacik } else { 62854f03ab1SJosef Bacik /* 62954f03ab1SJosef Bacik * Inline extents are special, we just treat 63054f03ab1SJosef Bacik * them as a full sector worth in the file 63154f03ab1SJosef Bacik * extent tree just for simplicity sake. 63254f03ab1SJosef Bacik */ 63354f03ab1SJosef Bacik clear_len = fs_info->sectorsize; 63454f03ab1SJosef Bacik } 63554f03ab1SJosef Bacik 636462b728eSJosef Bacik control->sub_bytes += item_end + 1 - new_size; 63754f03ab1SJosef Bacik } 63854f03ab1SJosef Bacik delete: 63954f03ab1SJosef Bacik /* 640655807b8SJosef Bacik * We only want to clear the file extent range if we're 641655807b8SJosef Bacik * modifying the actual inode's mapping, which is just the 642655807b8SJosef Bacik * normal truncate path. 64354f03ab1SJosef Bacik */ 644655807b8SJosef Bacik if (control->clear_extent_range) { 64571d18b53SJosef Bacik ret = btrfs_inode_clear_file_extent_range(control->inode, 64654f03ab1SJosef Bacik clear_start, clear_len); 64754f03ab1SJosef Bacik if (ret) { 64854f03ab1SJosef Bacik btrfs_abort_transaction(trans, ret); 64954f03ab1SJosef Bacik break; 65054f03ab1SJosef Bacik } 65154f03ab1SJosef Bacik } 65254f03ab1SJosef Bacik 65354f03ab1SJosef Bacik if (del_item) { 654376b91d5SJosef Bacik ASSERT(!pending_del_nr || 655376b91d5SJosef Bacik ((path->slots[0] + 1) == pending_del_slot)); 656376b91d5SJosef Bacik 6570adbc619SJosef Bacik control->last_size = found_key.offset; 65854f03ab1SJosef Bacik if (!pending_del_nr) { 65954f03ab1SJosef Bacik /* No pending yet, add ourselves */ 66054f03ab1SJosef Bacik pending_del_slot = path->slots[0]; 66154f03ab1SJosef Bacik pending_del_nr = 1; 66254f03ab1SJosef Bacik } else if (pending_del_nr && 66354f03ab1SJosef Bacik path->slots[0] + 1 == pending_del_slot) { 66454f03ab1SJosef Bacik /* Hop on the pending chunk */ 66554f03ab1SJosef Bacik pending_del_nr++; 66654f03ab1SJosef Bacik pending_del_slot = path->slots[0]; 66754f03ab1SJosef Bacik } 66854f03ab1SJosef Bacik } else { 6690adbc619SJosef Bacik control->last_size = new_size; 67054f03ab1SJosef Bacik break; 67154f03ab1SJosef Bacik } 67254f03ab1SJosef Bacik 6735caa490eSJosef Bacik if (del_item && extent_start != 0 && !control->skip_ref_updates) { 67454f03ab1SJosef Bacik struct btrfs_ref ref = { 0 }; 67554f03ab1SJosef Bacik 67654f03ab1SJosef Bacik bytes_deleted += extent_num_bytes; 67754f03ab1SJosef Bacik 67854f03ab1SJosef Bacik btrfs_init_generic_ref(&ref, BTRFS_DROP_DELAYED_REF, 67954f03ab1SJosef Bacik extent_start, extent_num_bytes, 0); 68054f03ab1SJosef Bacik btrfs_init_data_ref(&ref, btrfs_header_owner(leaf), 681487e81d2SJosef Bacik control->ino, extent_offset, 68254f03ab1SJosef Bacik root->root_key.objectid, false); 68354f03ab1SJosef Bacik ret = btrfs_free_extent(trans, &ref); 68454f03ab1SJosef Bacik if (ret) { 68554f03ab1SJosef Bacik btrfs_abort_transaction(trans, ret); 68654f03ab1SJosef Bacik break; 68754f03ab1SJosef Bacik } 68854f03ab1SJosef Bacik if (be_nice) { 68954f03ab1SJosef Bacik if (btrfs_should_throttle_delayed_refs(trans)) 69054f03ab1SJosef Bacik should_throttle = true; 69154f03ab1SJosef Bacik } 69254f03ab1SJosef Bacik } 69354f03ab1SJosef Bacik 69454f03ab1SJosef Bacik if (found_type == BTRFS_INODE_ITEM_KEY) 69554f03ab1SJosef Bacik break; 69654f03ab1SJosef Bacik 69754f03ab1SJosef Bacik if (path->slots[0] == 0 || 69854f03ab1SJosef Bacik path->slots[0] != pending_del_slot || 69954f03ab1SJosef Bacik should_throttle) { 70054f03ab1SJosef Bacik if (pending_del_nr) { 70154f03ab1SJosef Bacik ret = btrfs_del_items(trans, root, path, 70254f03ab1SJosef Bacik pending_del_slot, 70354f03ab1SJosef Bacik pending_del_nr); 70454f03ab1SJosef Bacik if (ret) { 70554f03ab1SJosef Bacik btrfs_abort_transaction(trans, ret); 70654f03ab1SJosef Bacik break; 70754f03ab1SJosef Bacik } 70854f03ab1SJosef Bacik pending_del_nr = 0; 70954f03ab1SJosef Bacik } 71054f03ab1SJosef Bacik btrfs_release_path(path); 71154f03ab1SJosef Bacik 71254f03ab1SJosef Bacik /* 71354f03ab1SJosef Bacik * We can generate a lot of delayed refs, so we need to 71454f03ab1SJosef Bacik * throttle every once and a while and make sure we're 71554f03ab1SJosef Bacik * adding enough space to keep up with the work we are 71654f03ab1SJosef Bacik * generating. Since we hold a transaction here we 71754f03ab1SJosef Bacik * can't flush, and we don't want to FLUSH_LIMIT because 71854f03ab1SJosef Bacik * we could have generated too many delayed refs to 71954f03ab1SJosef Bacik * actually allocate, so just bail if we're short and 72054f03ab1SJosef Bacik * let the normal reservation dance happen higher up. 72154f03ab1SJosef Bacik */ 72254f03ab1SJosef Bacik if (should_throttle) { 72354f03ab1SJosef Bacik ret = btrfs_delayed_refs_rsv_refill(fs_info, 72454f03ab1SJosef Bacik BTRFS_RESERVE_NO_FLUSH); 72554f03ab1SJosef Bacik if (ret) { 72654f03ab1SJosef Bacik ret = -EAGAIN; 72754f03ab1SJosef Bacik break; 72854f03ab1SJosef Bacik } 72954f03ab1SJosef Bacik } 73054f03ab1SJosef Bacik goto search_again; 73154f03ab1SJosef Bacik } else { 73254f03ab1SJosef Bacik path->slots[0]--; 73354f03ab1SJosef Bacik } 73454f03ab1SJosef Bacik } 73554f03ab1SJosef Bacik out: 73654f03ab1SJosef Bacik if (ret >= 0 && pending_del_nr) { 73754f03ab1SJosef Bacik int err; 73854f03ab1SJosef Bacik 73954f03ab1SJosef Bacik err = btrfs_del_items(trans, root, path, pending_del_slot, 74054f03ab1SJosef Bacik pending_del_nr); 74154f03ab1SJosef Bacik if (err) { 74254f03ab1SJosef Bacik btrfs_abort_transaction(trans, err); 74354f03ab1SJosef Bacik ret = err; 74454f03ab1SJosef Bacik } 74554f03ab1SJosef Bacik } 746c2ddb612SJosef Bacik 747c2ddb612SJosef Bacik ASSERT(control->last_size >= new_size); 748c2ddb612SJosef Bacik if (!ret && control->last_size > new_size) 749c2ddb612SJosef Bacik control->last_size = new_size; 75054f03ab1SJosef Bacik 75154f03ab1SJosef Bacik btrfs_free_path(path); 75254f03ab1SJosef Bacik return ret; 75354f03ab1SJosef Bacik } 754