On Mon, August 20, 2012 at 22:29 (+0200), Mark Fasheh wrote: > This patch adds basic support for extended inode refs. This includes support > for link and unlink of the refs, which basically gets us support for rename > as well. > > Inode creation does not need changing - extended refs are only added after > the ref array is full. > > Signed-off-by: Mark Fasheh <[email protected]> > --- > fs/btrfs/ctree.h | 52 ++++++++-- > fs/btrfs/hash.h | 10 ++ > fs/btrfs/inode-item.c | 282 > +++++++++++++++++++++++++++++++++++++++++++++++-- > fs/btrfs/inode.c | 23 +++-- > 4 files changed, 340 insertions(+), 27 deletions(-) > > diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h > index fa5c45b..9fa4ebe 100644 > --- a/fs/btrfs/ctree.h > +++ b/fs/btrfs/ctree.h > @@ -151,6 +151,13 @@ struct btrfs_ordered_sum; > */ > #define BTRFS_NAME_LEN 255 > > +/* > + * Theoretical limit is larger, but we keep this down to a sane > + * value. That should limit greatly the possibility of collisions on > + * inode ref items. > + */ > +#define BTRFS_LINK_MAX 65535U > + > /* 32 bytes in various csum fields */ > #define BTRFS_CSUM_SIZE 32 > > @@ -486,6 +493,8 @@ struct btrfs_super_block { > */ > #define BTRFS_FEATURE_INCOMPAT_BIG_METADATA (1ULL << 5) > > +#define BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF (1ULL << 6) > + > #define BTRFS_FEATURE_COMPAT_SUPP 0ULL > #define BTRFS_FEATURE_COMPAT_RO_SUPP 0ULL > #define BTRFS_FEATURE_INCOMPAT_SUPP \ > @@ -493,7 +502,8 @@ struct btrfs_super_block { > BTRFS_FEATURE_INCOMPAT_DEFAULT_SUBVOL | \ > BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS | \ > BTRFS_FEATURE_INCOMPAT_BIG_METADATA | \ > - BTRFS_FEATURE_INCOMPAT_COMPRESS_LZO) > + BTRFS_FEATURE_INCOMPAT_COMPRESS_LZO | \ > + BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) > > /* > * A leaf is full of items. offset and size tell us where to find > @@ -640,6 +650,14 @@ struct btrfs_inode_ref { > /* name goes here */ > } __attribute__ ((__packed__)); > > +struct btrfs_inode_extref { > + __le64 parent_objectid; > + __le64 index; > + __le16 name_len; > + __u8 name[0]; > + /* name goes here */ > +} __attribute__ ((__packed__)); > + > struct btrfs_timespec { > __le64 sec; > __le32 nsec; > @@ -1457,6 +1475,7 @@ struct btrfs_ioctl_defrag_range_args { > */ > #define BTRFS_INODE_ITEM_KEY 1 > #define BTRFS_INODE_REF_KEY 12 > +#define BTRFS_INODE_EXTREF_KEY 13 > #define BTRFS_XATTR_ITEM_KEY 24 > #define BTRFS_ORPHAN_ITEM_KEY 48 > /* reserve 2-15 close to the inode for later flexibility */ > @@ -1778,6 +1797,13 @@ BTRFS_SETGET_STACK_FUNCS(block_group_flags, > BTRFS_SETGET_FUNCS(inode_ref_name_len, struct btrfs_inode_ref, name_len, 16); > BTRFS_SETGET_FUNCS(inode_ref_index, struct btrfs_inode_ref, index, 64); > > +/* struct btrfs_inode_extref */ > +BTRFS_SETGET_FUNCS(inode_extref_parent, struct btrfs_inode_extref, > + parent_objectid, 64); > +BTRFS_SETGET_FUNCS(inode_extref_name_len, struct btrfs_inode_extref, > + name_len, 16); > +BTRFS_SETGET_FUNCS(inode_extref_index, struct btrfs_inode_extref, index, 64); > + > /* struct btrfs_inode_item */ > BTRFS_SETGET_FUNCS(inode_generation, struct btrfs_inode_item, generation, > 64); > BTRFS_SETGET_FUNCS(inode_sequence, struct btrfs_inode_item, sequence, 64); > @@ -2884,12 +2910,12 @@ int btrfs_del_inode_ref(struct btrfs_trans_handle > *trans, > struct btrfs_root *root, > const char *name, int name_len, > u64 inode_objectid, u64 ref_objectid, u64 *index); > -struct btrfs_inode_ref * > -btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans, > - struct btrfs_root *root, > - struct btrfs_path *path, > - const char *name, int name_len, > - u64 inode_objectid, u64 ref_objectid, int mod); > +int btrfs_get_inode_ref_index(struct btrfs_trans_handle *trans, > + struct btrfs_root *root, > + struct btrfs_path *path, > + const char *name, int name_len, > + u64 inode_objectid, u64 ref_objectid, int mod, > + u64 *ret_index); > int btrfs_insert_empty_inode(struct btrfs_trans_handle *trans, > struct btrfs_root *root, > struct btrfs_path *path, u64 objectid); > @@ -2897,6 +2923,18 @@ int btrfs_lookup_inode(struct btrfs_trans_handle > *trans, struct btrfs_root > *root, struct btrfs_path *path, > struct btrfs_key *location, int mod); > > +struct btrfs_inode_extref * > +btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans, > + struct btrfs_root *root, > + struct btrfs_path *path, > + const char *name, int name_len, > + u64 inode_objectid, u64 ref_objectid, int ins_len, > + int cow); > + > +int btrfs_find_name_in_ext_backref(struct btrfs_path *path, const char *name, > + int name_len, > + struct btrfs_inode_extref **extref_ret); > + > /* file-item.c */ > int btrfs_del_csums(struct btrfs_trans_handle *trans, > struct btrfs_root *root, u64 bytenr, u64 len); > diff --git a/fs/btrfs/hash.h b/fs/btrfs/hash.h > index db2ff97..1d98281 100644 > --- a/fs/btrfs/hash.h > +++ b/fs/btrfs/hash.h > @@ -24,4 +24,14 @@ static inline u64 btrfs_name_hash(const char *name, int > len) > { > return crc32c((u32)~1, name, len); > } > + > +/* > + * Figure the key offset of an extended inode ref > + */ > +static inline u64 btrfs_extref_hash(u64 parent_objectid, const char *name, > + int len) > +{ > + return (u64) crc32c(parent_objectid, name, len); > +} > + > #endif > diff --git a/fs/btrfs/inode-item.c b/fs/btrfs/inode-item.c > index a13cf1a..ad11b30 100644 > --- a/fs/btrfs/inode-item.c > +++ b/fs/btrfs/inode-item.c > @@ -18,6 +18,7 @@ > > #include "ctree.h" > #include "disk-io.h" > +#include "hash.h" > #include "transaction.h" > #include "print-tree.h" > > @@ -50,18 +51,56 @@ static int find_name_in_backref(struct btrfs_path *path, > const char *name, > return 0; > } > > -struct btrfs_inode_ref * > +int btrfs_find_name_in_ext_backref(struct btrfs_path *path, const char *name, > + int name_len, > + struct btrfs_inode_extref **extref_ret) > +{ > + struct extent_buffer *leaf; > + struct btrfs_inode_extref *extref; > + unsigned long ptr; > + unsigned long name_ptr; > + u32 item_size; > + u32 cur_offset = 0; > + int ref_name_len; > + > + leaf = path->nodes[0]; > + item_size = btrfs_item_size_nr(leaf, path->slots[0]); > + ptr = btrfs_item_ptr_offset(leaf, path->slots[0]); > + > + /* > + * Search all extended backrefs in this item. We're only > + * looking through any collisions so most of the time this is > + * just going to compare against one buffer. If all is well, > + * we'll return success and the inode ref object. > + */ > + while (cur_offset < item_size) { > + extref = (struct btrfs_inode_extref *) (ptr + cur_offset); > + name_ptr = (unsigned long)(&extref->name); > + ref_name_len = btrfs_inode_extref_name_len(leaf, extref); > + > + if (ref_name_len == name_len > + && (memcmp_extent_buffer(leaf, name, name_ptr, name_len) == > 0)) { > + if (extref_ret) > + *extref_ret = extref; > + return 1; > + } > + > + cur_offset += ref_name_len + sizeof(*extref); > + } > + return 0; > +} > + > +static struct btrfs_inode_ref * > btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans, > - struct btrfs_root *root, > - struct btrfs_path *path, > - const char *name, int name_len, > - u64 inode_objectid, u64 ref_objectid, int mod) > + struct btrfs_root *root, > + struct btrfs_path *path, > + const char *name, int name_len, > + u64 inode_objectid, u64 ref_objectid, int ins_len, > + int cow) > { > + int ret; > struct btrfs_key key; > struct btrfs_inode_ref *ref; > - int ins_len = mod < 0 ? -1 : 0; > - int cow = mod != 0; > - int ret; > > key.objectid = inode_objectid; > key.type = BTRFS_INODE_REF_KEY; > @@ -77,13 +116,149 @@ btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans, > return ref; > } > > -int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, > +/* Returns NULL if no extref found */ > +struct btrfs_inode_extref * > +btrfs_lookup_inode_extref(struct btrfs_trans_handle *trans, > + struct btrfs_root *root, > + struct btrfs_path *path, > + const char *name, int name_len, > + u64 inode_objectid, u64 ref_objectid, int ins_len, > + int cow) > +{ > + int ret; > + struct btrfs_key key; > + struct btrfs_inode_extref *extref; > + > + key.objectid = inode_objectid; > + key.type = BTRFS_INODE_EXTREF_KEY; > + key.offset = btrfs_extref_hash(ref_objectid, name, name_len); > + > + ret = btrfs_search_slot(trans, root, &key, path, ins_len, cow); > + if (ret < 0) > + return ERR_PTR(ret); > + if (ret > 0) > + return NULL; > + if (!btrfs_find_name_in_ext_backref(path, name, name_len, &extref)) > + return NULL; > + return extref; > +} > + > +int btrfs_get_inode_ref_index(struct btrfs_trans_handle *trans, > + struct btrfs_root *root, > + struct btrfs_path *path, > + const char *name, int name_len, > + u64 inode_objectid, u64 ref_objectid, int mod, > + u64 *ret_index) > +{ > + struct btrfs_inode_ref *ref; > + struct btrfs_inode_extref *extref; > + int ins_len = mod < 0 ? -1 : 0; > + int cow = mod != 0; > + > + ref = btrfs_lookup_inode_ref(trans, root, path, name, name_len, > + inode_objectid, ref_objectid, ins_len, > + cow); > + if (IS_ERR(ref)) > + return PTR_ERR(ref); > + > + if (ref != NULL) { > + *ret_index = btrfs_inode_ref_index(path->nodes[0], ref); > + return 0; > + } > + > + btrfs_release_path(path); > + > + extref = btrfs_lookup_inode_extref(trans, root, path, name, > + name_len, inode_objectid, > + ref_objectid, ins_len, cow); > + if (IS_ERR(extref)) > + return PTR_ERR(extref); > + > + if (extref) { > + *ret_index = btrfs_inode_extref_index(path->nodes[0], extref); > + return 0; > + } > + > + return -ENOENT; > +} > + > +int btrfs_del_inode_extref(struct btrfs_trans_handle *trans, > struct btrfs_root *root, > const char *name, int name_len, > u64 inode_objectid, u64 ref_objectid, u64 *index) > { > struct btrfs_path *path; > struct btrfs_key key; > + struct btrfs_inode_extref *extref; > + struct extent_buffer *leaf; > + int ret; > + int del_len = name_len + sizeof(*extref); > + unsigned long ptr; > + unsigned long item_start; > + u32 item_size; > + > + key.objectid = inode_objectid; > + btrfs_set_key_type(&key, BTRFS_INODE_EXTREF_KEY); > + key.offset = btrfs_extref_hash(ref_objectid, name, name_len); > + > + path = btrfs_alloc_path(); > + if (!path) > + return -ENOMEM; > + > + path->leave_spinning = 1; > + > + ret = btrfs_search_slot(trans, root, &key, path, -1, 1); > + if (ret > 0) > + ret = -ENOENT; > + if (ret < 0) > + goto out; > + > + /* > + * Sanity check - did we find the right item for this name? > + * This should always succeed so error here will make the FS > + * readonly. > + */ > + if (!btrfs_find_name_in_ext_backref(path, name, name_len, &extref)) { > + btrfs_std_error(root->fs_info, -ENOENT); > + ret = -EROFS; > + goto out; > + } > + > + leaf = path->nodes[0]; > + item_size = btrfs_item_size_nr(leaf, path->slots[0]); > + if (index) > + *index = btrfs_inode_extref_index(leaf, extref); > + > + if (del_len == item_size) { > + /* > + * Common case only one ref in the item, remove the > + * whole item. > + */ > + ret = btrfs_del_item(trans, root, path); > + goto out; > + } > + > + ptr = (unsigned long)extref; > + item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); > + > + memmove_extent_buffer(leaf, ptr, ptr + del_len, > + item_size - (ptr + del_len - item_start)); > + > + btrfs_truncate_item(trans, root, path, item_size - del_len, 1); > + > +out: > + btrfs_free_path(path); > + > + return ret; > +} > + > +int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, > + struct btrfs_root *root, > + const char *name, int name_len, > + u64 inode_objectid, u64 ref_objectid, u64 *index) > +{ > + struct btrfs_path *path; > + struct btrfs_key key; > struct btrfs_inode_ref *ref; > struct extent_buffer *leaf; > unsigned long ptr; > @@ -91,6 +266,7 @@ int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, > u32 item_size; > u32 sub_item_len; > int ret; > + int search_ext_refs = 0; > int del_len = name_len + sizeof(*ref); > > key.objectid = inode_objectid; > @@ -106,12 +282,14 @@ int btrfs_del_inode_ref(struct btrfs_trans_handle > *trans, > ret = btrfs_search_slot(trans, root, &key, path, -1, 1); > if (ret > 0) { > ret = -ENOENT; > + search_ext_refs = 1; > goto out; > } else if (ret < 0) { > goto out; > } > if (!find_name_in_backref(path, name, name_len, &ref)) { > ret = -ENOENT; > + search_ext_refs = 1; > goto out; > } > leaf = path->nodes[0]; > @@ -129,8 +307,77 @@ int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, > item_start = btrfs_item_ptr_offset(leaf, path->slots[0]); > memmove_extent_buffer(leaf, ptr, ptr + sub_item_len, > item_size - (ptr + sub_item_len - item_start)); > - btrfs_truncate_item(trans, root, path, > - item_size - sub_item_len, 1); > + btrfs_truncate_item(trans, root, path, item_size - sub_item_len, 1); > +out: > + btrfs_free_path(path); > + > + if (search_ext_refs) { > + /* > + * No refs were found, or we could not find the > + * name in our ref array. Find and remove the extended > + * inode ref then. > + */ > + return btrfs_del_inode_extref(trans, root, name, name_len, > + inode_objectid, ref_objectid, > index); > + } > + > + return ret; > +} > + > +/* > + * btrfs_insert_inode_extref() - Inserts an extended inode ref into a tree. > + * > + * The caller must have checked against BTRFS_LINK_MAX already. > + */ > +static int btrfs_insert_inode_extref(struct btrfs_trans_handle *trans, > + struct btrfs_root *root, > + const char *name, int name_len, > + u64 inode_objectid, u64 ref_objectid, u64 > index) > +{ > + struct btrfs_inode_extref *extref; > + int ret; > + int ins_len = name_len + sizeof(*extref); > + unsigned long ptr; > + struct btrfs_path *path; > + struct btrfs_key key; > + struct extent_buffer *leaf; > + struct btrfs_item *item; > + > + key.objectid = inode_objectid; > + key.type = BTRFS_INODE_EXTREF_KEY; > + key.offset = btrfs_extref_hash(ref_objectid, name, name_len); > + > + path = btrfs_alloc_path(); > + if (!path) > + return -ENOMEM; > + > + path->leave_spinning = 1; > + ret = btrfs_insert_empty_item(trans, root, path, &key, > + ins_len); > + if (ret == -EEXIST) { > + if (btrfs_find_name_in_ext_backref(path, name, name_len, NULL)) > + goto out; > + > + btrfs_extend_item(trans, root, path, ins_len); > + ret = 0; > + } > + if (ret < 0) > + goto out; > + > + leaf = path->nodes[0]; > + item = btrfs_item_nr(leaf, path->slots[0]); > + ptr = (unsigned long)btrfs_item_ptr(leaf, path->slots[0], char); > + ptr += btrfs_item_size(leaf, item) - ins_len; > + extref = (struct btrfs_inode_extref *)ptr; > + > + btrfs_set_inode_extref_name_len(path->nodes[0], extref, name_len); > + btrfs_set_inode_extref_index(path->nodes[0], extref, index); > + btrfs_set_inode_extref_parent(path->nodes[0], extref, ref_objectid); > + > + ptr = (unsigned long)&extref->name; > + write_extent_buffer(path->nodes[0], name, ptr, name_len); > + btrfs_mark_buffer_dirty(path->nodes[0]); > + > out: > btrfs_free_path(path); > return ret; > @@ -191,6 +438,19 @@ int btrfs_insert_inode_ref(struct btrfs_trans_handle > *trans, > > out: > btrfs_free_path(path); > + > + if (ret == -EMLINK) { > + struct btrfs_super_block *disk_super = > root->fs_info->super_copy; > + /* We ran out of space in the ref array. Need to > + * add an extended ref. */ > + if (btrfs_super_incompat_flags(disk_super) > + & BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) > + ret = btrfs_insert_inode_extref(trans, root, name, > + name_len, > + inode_objectid, > + ref_objectid, index); > + } > + > return ret; > } > > diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c > index a7d1921..b96f0dc 100644 > --- a/fs/btrfs/inode.c > +++ b/fs/btrfs/inode.c > @@ -2890,7 +2890,6 @@ static struct btrfs_trans_handle > *__unlink_start_trans(struct inode *dir, > struct btrfs_trans_handle *trans; > struct btrfs_root *root = BTRFS_I(dir)->root; > struct btrfs_path *path; > - struct btrfs_inode_ref *ref; > struct btrfs_dir_item *di; > struct inode *inode = dentry->d_inode; > u64 index; > @@ -3004,17 +3003,17 @@ static struct btrfs_trans_handle > *__unlink_start_trans(struct inode *dir, > } > btrfs_release_path(path); > > - ref = btrfs_lookup_inode_ref(trans, root, path, > - dentry->d_name.name, dentry->d_name.len, > - ino, dir_ino, 0); > - if (IS_ERR(ref)) { > - err = PTR_ERR(ref); > + ret = btrfs_get_inode_ref_index(trans, root, path, dentry->d_name.name, > + dentry->d_name.len, ino, dir_ino, 0, > + &index); > + if (ret) { > + err = ret; > goto out; > } > - BUG_ON(!ref); /* Logic error */ > + > if (check_path_shared(root, path)) > goto out; > - index = btrfs_inode_ref_index(path->nodes[0], ref); > + > btrfs_release_path(path); > > /* > @@ -4673,6 +4672,12 @@ static struct inode *btrfs_new_inode(struct > btrfs_trans_handle *trans, > btrfs_set_key_type(&key[0], BTRFS_INODE_ITEM_KEY); > key[0].offset = 0; > > + /* > + * Start new inodes with an inode_ref. This is slightly more > + * efficient for small numbers of hard links since they will > + * be packed into one item. Extended refs will kick in if we > + * add more hard links than can fit in the ref item. > + */ > key[1].objectid = objectid; > btrfs_set_key_type(&key[1], BTRFS_INODE_REF_KEY); > key[1].offset = ref_objectid; > @@ -4975,7 +4980,7 @@ static int btrfs_link(struct dentry *old_dentry, struct > inode *dir, > if (root->objectid != BTRFS_I(inode)->root->objectid) > return -EXDEV; > > - if (inode->i_nlink == ~0U) > + if (inode->i_nlink >= BTRFS_LINK_MAX) > return -EMLINK; > > err = btrfs_set_inode_index(dir, &index);
Reviewed-by: Jan Schmidt <[email protected]> -Jan -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
