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 <mfasheh@xxxxxxx>
> ---
> 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 <list.btrfs@xxxxxxxxxxxxx>
-Jan
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
