From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from brockman.in8.de ([85.214.220.56]:55109 "EHLO mail.in8.de" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752801Ab2GFO4m (ORCPT ); Fri, 6 Jul 2012 10:56:42 -0400 Message-ID: <4FF6FCA8.2060100@jan-o-sch.net> Date: Fri, 06 Jul 2012 16:56:40 +0200 From: Jan Schmidt MIME-Version: 1.0 To: Mark Fasheh CC: linux-btrfs@vger.kernel.org, Chris Mason , Mark Fasheh Subject: Re: [PATCH 1/3] btrfs: extended inode refs References: <1337636781-12575-1-git-send-email-mfasheh@suse.de> <1337636781-12575-2-git-send-email-mfasheh@suse.de> In-Reply-To: <1337636781-12575-2-git-send-email-mfasheh@suse.de> Content-Type: text/plain; charset=ISO-8859-1 Sender: linux-btrfs-owner@vger.kernel.org List-ID: Hi Mark, Sorry, I'm a bit late with my feedback. On Mon, May 21, 2012 at 23:46 (+0200), Mark Fasheh wrote: > From: Mark Fasheh Where does this From line come from? Git shouldn't add them unless its different from the sender's name. Shouldn't be in the patch. > 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 > --- > fs/btrfs/ctree.h | 52 ++++++++-- > fs/btrfs/hash.h | 10 ++ > fs/btrfs/inode-item.c | 279 +++++++++++++++++++++++++++++++++++++++++++++++-- > fs/btrfs/inode.c | 23 +++-- > 4 files changed, 338 insertions(+), 26 deletions(-) > > diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h > index 80b6486..3882813 100644 > --- a/fs/btrfs/ctree.h > +++ b/fs/btrfs/ctree.h > @@ -143,6 +143,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 > > @@ -462,13 +469,16 @@ struct btrfs_super_block { > #define BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS (1ULL << 2) > #define BTRFS_FEATURE_INCOMPAT_COMPRESS_LZO (1ULL << 3) > > +#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 \ > (BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF | \ > BTRFS_FEATURE_INCOMPAT_DEFAULT_SUBVOL | \ > BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS | \ > - 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 > @@ -615,6 +625,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; > @@ -1400,6 +1418,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 */ > @@ -1701,6 +1720,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); > @@ -2791,12 +2817,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); > @@ -2804,6 +2830,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 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 baa74f3..496fb1c 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" > > static int find_name_in_backref(struct btrfs_path *path, const char *name, > @@ -49,18 +50,56 @@ static int find_name_in_backref(struct btrfs_path *path, const char *name, > return 0; > } > > -struct btrfs_inode_ref * > +int find_name_in_ext_backref(struct btrfs_path *path, const char *name, > + int name_len, > + struct btrfs_inode_extref **extref_ret) Exported functions should be prefixed "btrfs_". What about btrfs_find_extref_name? > +{ > + 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; For consistency, I'd like to switch return 0 and 1. > +} > + > +static struct btrfs_inode_ref * > btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans, static functions should not be prefixed "btrfs_". > - 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; > @@ -76,20 +115,156 @@ btrfs_lookup_inode_ref(struct btrfs_trans_handle *trans, > return ref; > } > > -int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, > +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) Please add a comment on the return value above this function. It is important to note that it returns NULL instead of an ENOENT error pointer (which is okay and consistent with btrfs_inode_ref_index). > +{ > + 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 (!find_name_in_ext_backref(path, name, name_len, &extref)) Maybe easier to read if written with "ret" in two lines. Not sure. > + 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 *ref1; "ref1" seems to be a left over from when "extref" was called "ref2". We should rather just say "ref" here. > + struct btrfs_inode_extref *extref; > + int ins_len = mod < 0 ? -1 : 0; > + int cow = mod != 0; > + > + ref1 = btrfs_lookup_inode_ref(trans, root, path, name, name_len, > + inode_objectid, ref_objectid, ins_len, > + cow); > + if (IS_ERR(ref1)) > + return PTR_ERR(ref1); > + > + if (ref1 != NULL) { > + *ret_index = btrfs_inode_ref_index(path->nodes[0], ref1); > + 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 (!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)); > + > + ret = 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; > unsigned long item_start; > u32 item_size; > u32 sub_item_len; > - int ret; > + int ret, search_ext_refs = 0; No comma declarations according to style guide (as mentioned in May ;-) ) > int del_len = name_len + sizeof(*ref); > > key.objectid = inode_objectid; > @@ -105,12 +280,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]; > @@ -132,6 +309,75 @@ int btrfs_del_inode_ref(struct btrfs_trans_handle *trans, > 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 (find_name_in_ext_backref(path, name, name_len, NULL)) > + goto out; > + > + ret = btrfs_extend_item(trans, root, path, ins_len); > + } > + 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; > } > > @@ -189,6 +435,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) Uhm. Good place to check here. But please help me to find the place where this is added to the super block's flags in the first place. > + 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 892b347..5ce89e4 100644 > --- a/fs/btrfs/inode.c > +++ b/fs/btrfs/inode.c > @@ -2689,7 +2689,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; > @@ -2803,17 +2802,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); > + > if (check_path_shared(root, path)) > goto out; > - index = btrfs_inode_ref_index(path->nodes[0], ref); > + > btrfs_release_path(path); > > /* > @@ -4484,6 +4483,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; > @@ -4777,7 +4782,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); That's all for this one, -Jan