btrfs: extended inode refs

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@suse.de>

1 files changed, 293 insertions, 52 deletions

diff --git a/fs/btrfs/tree-log.c b/fs/btrfs/tree-log.c
index 15dae589e59f..1d7b34844323 100644
--- a/fs/btrfs/tree-log.c
+++ b/fs/btrfs/tree-log.c
@@ -24,8 +24,10 @@
 #include "disk-io.h"
 #include "locking.h"
 #include "print-tree.h"
+#include "backref.h"
 #include "compat.h"
 #include "tree-log.h"
+#include "hash.h"
 
 /* magic values for the inode_only field in btrfs_log_inode:
  *
@@ -743,6 +745,7 @@ out:
  */
 static noinline int backref_in_log(struct btrfs_root *log,
                                    struct btrfs_key *key,
+                                   u64 ref_objectid,
                                    char *name, int namelen)
 {
         struct btrfs_path *path;
@@ -763,8 +766,17 @@ static noinline int backref_in_log(struct btrfs_root *log,
         if (ret != 0)
                 goto out;
 
-        item_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
         ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
+
+        if (key->type == BTRFS_INODE_EXTREF_KEY) {
+                if (btrfs_find_name_in_ext_backref(path, ref_objectid,
+                                                   name, namelen, NULL))
+                        match = 1;
+
+                goto out;
+        }
+
+        item_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
         ptr_end = ptr + item_size;
         while (ptr < ptr_end) {
                 ref = (struct btrfs_inode_ref *)ptr;
@@ -790,27 +802,36 @@ static inline int __add_inode_ref(struct btrfs_trans_handle *trans,
                                   struct btrfs_path *path,
                                   struct btrfs_root *log_root,
                                   struct inode *dir, struct inode *inode,
-                                  struct btrfs_key *key,
                                   struct extent_buffer *eb,
-                                  struct btrfs_inode_ref *ref,
-                                  char *name, int namelen, int *search_done)
+                                  u64 inode_objectid, u64 parent_objectid,
+                                  u64 ref_index, char *name, int namelen,
+                                  int *search_done)
 {
         int ret;
+        char *victim_name;
+        int victim_name_len;
+        struct extent_buffer *leaf;
         struct btrfs_dir_item *di;
+        struct btrfs_key search_key;
+        struct btrfs_inode_extref *extref;
 
-        ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
+again:
+        /* Search old style refs */
+        search_key.objectid = inode_objectid;
+        search_key.type = BTRFS_INODE_REF_KEY;
+        search_key.offset = parent_objectid;
+        ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
         if (ret == 0) {
-                char *victim_name;
-                int victim_name_len;
                 struct btrfs_inode_ref *victim_ref;
                 unsigned long ptr;
                 unsigned long ptr_end;
-                struct extent_buffer *leaf = path->nodes[0];
+
+                leaf = path->nodes[0];
 
                 /* are we trying to overwrite a back ref for the root directory
                  * if so, just jump out, we're done
                  */
-                if (key->objectid == key->offset)
+                if (search_key.objectid == search_key.offset)
                         return 1;
 
                 /* check all the names in this back reference to see
@@ -830,7 +851,9 @@ static inline int __add_inode_ref(struct btrfs_trans_handle *trans,
                                            (unsigned long)(victim_ref + 1),
                                            victim_name_len);
 
-                        if (!backref_in_log(log_root, key, victim_name,
+                        if (!backref_in_log(log_root, &search_key,
+                                            parent_objectid,
+                                            victim_name,
                                             victim_name_len)) {
                                 btrfs_inc_nlink(inode);
                                 btrfs_release_path(path);
@@ -838,9 +861,14 @@ static inline int __add_inode_ref(struct btrfs_trans_handle *trans,
                                 ret = btrfs_unlink_inode(trans, root, dir,
                                                          inode, victim_name,
                                                          victim_name_len);
+                                BUG_ON(ret);
                                 btrfs_run_delayed_items(trans, root);
+                                kfree(victim_name);
+                                *search_done = 1;
+                                goto again;
                         }
                         kfree(victim_name);
+
                         ptr = (unsigned long)(victim_ref + 1) + victim_name_len;
                 }
                 BUG_ON(ret);
@@ -853,10 +881,74 @@ static inline int __add_inode_ref(struct btrfs_trans_handle *trans,
         }
         btrfs_release_path(path);
 
+        /* Same search but for extended refs */
+        extref = btrfs_lookup_inode_extref(NULL, root, path, name, namelen,
+                                           inode_objectid, parent_objectid, 0,
+                                           0);
+        if (!IS_ERR_OR_NULL(extref)) {
+                u32 item_size;
+                u32 cur_offset = 0;
+                unsigned long base;
+                struct inode *victim_parent;
+
+                leaf = path->nodes[0];
+
+                item_size = btrfs_item_size_nr(leaf, path->slots[0]);
+                base = btrfs_item_ptr_offset(leaf, path->slots[0]);
+
+                while (cur_offset < item_size) {
+                        extref = (struct btrfs_inode_extref *)base + cur_offset;
+
+                        victim_name_len = btrfs_inode_extref_name_len(leaf, extref);
+
+                        if (btrfs_inode_extref_parent(leaf, extref) != parent_objectid)
+                                goto next;
+
+                        victim_name = kmalloc(victim_name_len, GFP_NOFS);
+                        read_extent_buffer(leaf, victim_name, (unsigned long)&extref->name,
+                                           victim_name_len);
+
+                        search_key.objectid = inode_objectid;
+                        search_key.type = BTRFS_INODE_EXTREF_KEY;
+                        search_key.offset = btrfs_extref_hash(parent_objectid,
+                                                              victim_name,
+                                                              victim_name_len);
+                        ret = 0;
+                        if (!backref_in_log(log_root, &search_key,
+                                            parent_objectid, victim_name,
+                                            victim_name_len)) {
+                                ret = -ENOENT;
+                                victim_parent = read_one_inode(root,
+                                                               parent_objectid);
+                                if (victim_parent) {
+                                        btrfs_inc_nlink(inode);
+                                        btrfs_release_path(path);
+
+                                        ret = btrfs_unlink_inode(trans, root,
+                                                                 victim_parent,
+                                                                 inode,
+                                                                 victim_name,
+                                                                 victim_name_len);
+                                        btrfs_run_delayed_items(trans, root);
+                                }
+                                BUG_ON(ret);
+                                iput(victim_parent);
+                                kfree(victim_name);
+                                *search_done = 1;
+                                goto again;
+                        }
+                        kfree(victim_name);
+                        BUG_ON(ret);
+next:
+                        cur_offset += victim_name_len + sizeof(*extref);
+                }
+                *search_done = 1;
+        }
+        btrfs_release_path(path);
+
         /* look for a conflicting sequence number */
         di = btrfs_lookup_dir_index_item(trans, root, path, btrfs_ino(dir),
-                                         btrfs_inode_ref_index(eb, ref),
-                                         name, namelen, 0);
+                                         ref_index, name, namelen, 0);
         if (di && !IS_ERR(di)) {
                 ret = drop_one_dir_item(trans, root, path, dir, di);
                 BUG_ON(ret);
@@ -875,6 +967,48 @@ static inline int __add_inode_ref(struct btrfs_trans_handle *trans,
         return 0;
 }
 
+static int extref_get_fields(struct extent_buffer *eb, unsigned long ref_ptr,
+                             u32 *namelen, char **name, u64 *index,
+                             u64 *parent_objectid)
+{
+        struct btrfs_inode_extref *extref;
+
+        extref = (struct btrfs_inode_extref *)ref_ptr;
+
+        *namelen = btrfs_inode_extref_name_len(eb, extref);
+        *name = kmalloc(*namelen, GFP_NOFS);
+        if (*name == NULL)
+                return -ENOMEM;
+
+        read_extent_buffer(eb, *name, (unsigned long)&extref->name,
+                           *namelen);
+
+        *index = btrfs_inode_extref_index(eb, extref);
+        if (parent_objectid)
+                *parent_objectid = btrfs_inode_extref_parent(eb, extref);
+
+        return 0;
+}
+
+static int ref_get_fields(struct extent_buffer *eb, unsigned long ref_ptr,
+                          u32 *namelen, char **name, u64 *index)
+{
+        struct btrfs_inode_ref *ref;
+
+        ref = (struct btrfs_inode_ref *)ref_ptr;
+
+        *namelen = btrfs_inode_ref_name_len(eb, ref);
+        *name = kmalloc(*namelen, GFP_NOFS);
+        if (*name == NULL)
+                return -ENOMEM;
+
+        read_extent_buffer(eb, *name, (unsigned long)(ref + 1), *namelen);
+
+        *index = btrfs_inode_ref_index(eb, ref);
+
+        return 0;
+}
+
 /*
  * replay one inode back reference item found in the log tree.
  * eb, slot and key refer to the buffer and key found in the log tree.
@@ -888,7 +1022,6 @@ static noinline int add_inode_ref(struct btrfs_trans_handle *trans,
                                   struct extent_buffer *eb, int slot,
                                   struct btrfs_key *key)
 {
-        struct btrfs_inode_ref *ref;
         struct inode *dir;
         struct inode *inode;
         unsigned long ref_ptr;
@@ -897,6 +1030,27 @@ static noinline int add_inode_ref(struct btrfs_trans_handle *trans,
         int namelen;
         int ret;
         int search_done = 0;
+        int log_ref_ver = 0;
+        u64 parent_objectid;
+        u64 inode_objectid;
+        u64 ref_index;
+        int ref_struct_size;
+
+        ref_ptr = btrfs_item_ptr_offset(eb, slot);
+        ref_end = ref_ptr + btrfs_item_size_nr(eb, slot);
+
+        if (key->type == BTRFS_INODE_EXTREF_KEY) {
+                struct btrfs_inode_extref *r;
+
+                ref_struct_size = sizeof(struct btrfs_inode_extref);
+                log_ref_ver = 1;
+                r = (struct btrfs_inode_extref *)ref_ptr;
+                parent_objectid = btrfs_inode_extref_parent(eb, r);
+        } else {
+                ref_struct_size = sizeof(struct btrfs_inode_ref);
+                parent_objectid = key->offset;
+        }
+        inode_objectid = key->objectid;
 
         /*
          * it is possible that we didn't log all the parent directories
@@ -904,32 +1058,38 @@ static noinline int add_inode_ref(struct btrfs_trans_handle *trans,
          * copy the back ref in.  The link count fixup code will take
          * care of the rest
          */
-        dir = read_one_inode(root, key->offset);
+        dir = read_one_inode(root, parent_objectid);
         if (!dir)
                 return -ENOENT;
 
-        inode = read_one_inode(root, key->objectid);
+        inode = read_one_inode(root, inode_objectid);
         if (!inode) {
                 iput(dir);
                 return -EIO;
         }
 
-        ref_ptr = btrfs_item_ptr_offset(eb, slot);
-        ref_end = ref_ptr + btrfs_item_size_nr(eb, slot);
-
         while (ref_ptr < ref_end) {
-                ref = (struct btrfs_inode_ref *)ref_ptr;
-
-                namelen = btrfs_inode_ref_name_len(eb, ref);
-                name = kmalloc(namelen, GFP_NOFS);
-                BUG_ON(!name);
-
-                read_extent_buffer(eb, name, (unsigned long)(ref + 1), namelen);
+                if (log_ref_ver) {
+                        ret = extref_get_fields(eb, ref_ptr, &namelen, &name,
+                                                &ref_index, &parent_objectid);
+                        /*
+                         * parent object can change from one array
+                         * item to another.
+                         */
+                        if (!dir)
+                                dir = read_one_inode(root, parent_objectid);
+                        if (!dir)
+                                return -ENOENT;
+                } else {
+                        ret = ref_get_fields(eb, ref_ptr, &namelen, &name,
+                                             &ref_index);
+                }
+                if (ret)
+                        return ret;
 
                 /* if we already have a perfect match, we're done */
                 if (!inode_in_dir(root, path, btrfs_ino(dir), btrfs_ino(inode),
-                                  btrfs_inode_ref_index(eb, ref),
-                                  name, namelen)) {
+                                  ref_index, name, namelen)) {
                         /*
                          * look for a conflicting back reference in the
                          * metadata. if we find one we have to unlink that name
@@ -940,8 +1100,10 @@ static noinline int add_inode_ref(struct btrfs_trans_handle *trans,
 
                         if (!search_done) {
                                 ret = __add_inode_ref(trans, root, path, log,
-                                                      dir, inode, key, eb, ref,
-                                                      name, namelen,
+                                                      dir, inode, eb,
+                                                      inode_objectid,
+                                                      parent_objectid,
+                                                      ref_index, name, namelen,
                                                       &search_done);
                                 if (ret == 1)
                                         goto out;
@@ -950,14 +1112,18 @@ static noinline int add_inode_ref(struct btrfs_trans_handle *trans,
 
                         /* insert our name */
                         ret = btrfs_add_link(trans, dir, inode, name, namelen,
-                                             0, btrfs_inode_ref_index(eb, ref));
+                                             0, ref_index);
                         BUG_ON(ret);
 
                         btrfs_update_inode(trans, root, inode);
                 }
 
-                ref_ptr = (unsigned long)(ref + 1) + namelen;
+                ref_ptr = (unsigned long)(ref_ptr + ref_struct_size) + namelen;
                 kfree(name);
+                if (log_ref_ver) {
+                        iput(dir);
+                        dir = NULL;
+                }
         }
 
         /* finally write the back reference in the inode */
@@ -981,25 +1147,55 @@ static int insert_orphan_item(struct btrfs_trans_handle *trans,
         return ret;
 }
 
+static int count_inode_extrefs(struct btrfs_root *root,
+                               struct inode *inode, struct btrfs_path *path)
+{
+        int ret = 0;
+        int name_len;
+        unsigned int nlink = 0;
+        u32 item_size;
+        u32 cur_offset = 0;
+        u64 inode_objectid = btrfs_ino(inode);
+        u64 offset = 0;
+        unsigned long ptr;
+        struct btrfs_inode_extref *extref;
+        struct extent_buffer *leaf;
 
-/*
- * There are a few corners where the link count of the file can't
- * be properly maintained during replay.  So, instead of adding
- * lots of complexity to the log code, we just scan the backrefs
- * for any file that has been through replay.
- *
- * The scan will update the link count on the inode to reflect the
- * number of back refs found.  If it goes down to zero, the iput
- * will free the inode.
- */
-static noinline int fixup_inode_link_count(struct btrfs_trans_handle *trans,
-                                           struct btrfs_root *root,
-                                           struct inode *inode)
+        while (1) {
+                ret = btrfs_find_one_extref(root, inode_objectid, offset, path,
+                                            &extref, &offset);
+                if (ret)
+                        break;
+
+                leaf = path->nodes[0];
+                item_size = btrfs_item_size_nr(leaf, path->slots[0]);
+                ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
+
+                while (cur_offset < item_size) {
+                        extref = (struct btrfs_inode_extref *) (ptr + cur_offset);
+                        name_len = btrfs_inode_extref_name_len(leaf, extref);
+
+                        nlink++;
+
+                        cur_offset += name_len + sizeof(*extref);
+                }
+
+                offset++;
+                btrfs_release_path(path);
+        }
+        btrfs_release_path(path);
+
+        if (ret < 0)
+                return ret;
+        return nlink;
+}
+
+static int count_inode_refs(struct btrfs_root *root,
+                               struct inode *inode, struct btrfs_path *path)
 {
-        struct btrfs_path *path;
         int ret;
         struct btrfs_key key;
-        u64 nlink = 0;
+        unsigned int nlink = 0;
         unsigned long ptr;
         unsigned long ptr_end;
         int name_len;
@@ -1009,10 +1205,6 @@ static noinline int fixup_inode_link_count(struct btrfs_trans_handle *trans,
         key.type = BTRFS_INODE_REF_KEY;
         key.offset = (u64)-1;
 
-        path = btrfs_alloc_path();
-        if (!path)
-                return -ENOMEM;
-
         while (1) {
                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
                 if (ret < 0)
@@ -1046,6 +1238,50 @@ static noinline int fixup_inode_link_count(struct btrfs_trans_handle *trans,
                 btrfs_release_path(path);
         }
         btrfs_release_path(path);
+
+        return nlink;
+}
+
+/*
+ * There are a few corners where the link count of the file can't
+ * be properly maintained during replay.  So, instead of adding
+ * lots of complexity to the log code, we just scan the backrefs
+ * for any file that has been through replay.
+ *
+ * The scan will update the link count on the inode to reflect the
+ * number of back refs found.  If it goes down to zero, the iput
+ * will free the inode.
+ */
+static noinline int fixup_inode_link_count(struct btrfs_trans_handle *trans,
+                                           struct btrfs_root *root,
+                                           struct inode *inode)
+{
+        struct btrfs_path *path;
+        int ret;
+        u64 nlink = 0;
+        u64 ino = btrfs_ino(inode);
+
+        path = btrfs_alloc_path();
+        if (!path)
+                return -ENOMEM;
+
+        ret = count_inode_refs(root, inode, path);
+        if (ret < 0)
+                goto out;
+
+        nlink = ret;
+
+        ret = count_inode_extrefs(root, inode, path);
+        if (ret == -ENOENT)
+                ret = 0;
+
+        if (ret < 0)
+                goto out;
+
+        nlink += ret;
+
+        ret = 0;
+
         if (nlink != inode->i_nlink) {
                 set_nlink(inode, nlink);
                 btrfs_update_inode(trans, root, inode);
@@ -1061,9 +1297,10 @@ static noinline int fixup_inode_link_count(struct btrfs_trans_handle *trans,
                 ret = insert_orphan_item(trans, root, ino);
                 BUG_ON(ret);
         }
-        btrfs_free_path(path);
 
-        return 0;
+out:
+        btrfs_free_path(path);
+        return ret;
 }
 
 static noinline int fixup_inode_link_counts(struct btrfs_trans_handle *trans,
@@ -1710,6 +1947,10 @@ static int replay_one_buffer(struct btrfs_root *log, struct extent_buffer *eb,
                         ret = add_inode_ref(wc->trans, root, log, path,
                                             eb, i, &key);
                         BUG_ON(ret && ret != -ENOENT);
+                } else if (key.type == BTRFS_INODE_EXTREF_KEY) {
+                        ret = add_inode_ref(wc->trans, root, log, path,
+                                            eb, i, &key);
+                        BUG_ON(ret && ret != -ENOENT);
                 } else if (key.type == BTRFS_EXTENT_DATA_KEY) {
                         ret = replay_one_extent(wc->trans, root, path,
                                                 eb, i, &key);