inode: API changes for generation number support

Signed-off-by: Anand V. Avati <avati@dev.gluster.com>

BUG: 315 (generation number support)
URL: http://bugs.gluster.com/cgi-bin/bugzilla3/show_bug.cgi?id=315

2 files changed, 196 insertions, 156 deletions

diff --git a/libglusterfs/src/inode.c b/libglusterfs/src/inode.c
index 825ab4c5c..18a5a85db 100644
--- a/libglusterfs/src/inode.c
+++ b/libglusterfs/src/inode.c
@@ -55,6 +55,24 @@ static int
 inode_table_prune (inode_table_t *table);
 
 static int
+hash_dentry (inode_t *parent, const char *name, int mod)
+{
+        int hash = 0;
+        int ret = 0;
+
+        hash = *name;
+        if (hash) {
+                for (name += 1; *name != '\0'; name++) {
+                        hash = (hash << 5) - hash + *name;
+                }
+        }
+        ret = (hash + (unsigned long)parent) % mod;
+
+        return ret;
+}
+
+
+static int
 hash_name (ino_t par, const char *name, int mod)
 {
         int hash = 0;
@@ -90,14 +108,11 @@ __dentry_hash (dentry_t *dentry)
         int              hash = 0;
 
         table = dentry->inode->table;
-        hash = hash_name (dentry->parent->ino, dentry->name,
-                          table->hashsize);
+        hash = hash_dentry (dentry->parent, dentry->name,
+                            table->hashsize);
 
         list_del_init (&dentry->hash);
         list_add (&dentry->hash, &table->name_hash[hash]);
-
-        list_del_init (&dentry->parent_list);
-        list_add (&dentry->parent_list, &dentry->parent->child_list);
 }
 
 
@@ -126,7 +141,6 @@ __dentry_unset (dentry_t *dentry)
                 FREE (dentry->name);
 
         if (dentry->parent) {
-                list_del_init (&dentry->parent_list);
                 __inode_unref (dentry->parent);
                 dentry->parent = NULL;
         }
@@ -138,6 +152,12 @@ __dentry_unset (dentry_t *dentry)
 static void
 __inode_unhash (inode_t *inode)
 {
+        if (!list_empty (&inode->hash)) {
+                if (inode->in_attic)
+                        inode->table->attic_size--;
+                inode->in_attic = 0;
+        }
+
         list_del_init (&inode->hash);
 }
 
@@ -183,6 +203,23 @@ __inode_search (inode_table_t *table, ino_t ino)
 }
 
 
+static inode_t *
+__inode_search_attic (inode_table_t *table, ino_t ino, uint64_t gen)
+{
+        inode_t  *inode = NULL;
+        inode_t  *tmp = NULL;
+
+        list_for_each_entry (tmp, &table->attic, hash) {
+                if (tmp->ino == ino && tmp->generation == gen) {
+                        inode = tmp;
+                        break;
+                }
+        }
+
+        return inode;
+}
+
+
 static dentry_t *
 __dentry_search_for_inode (inode_t *inode, ino_t par, const char *name)
 {
@@ -299,7 +336,6 @@ __inode_retire (inode_t *inode)
         inode->table->purge_size++;
 
         __inode_unhash (inode);
-        assert (list_empty (&inode->child_list));
 
         list_for_each_entry_safe (dentry, t, &inode->dentry_list, inode_list) {
                 __dentry_unset (dentry);
@@ -320,7 +356,7 @@ __inode_unref (inode_t *inode)
         if (!inode->ref) {
                 inode->table->active_size--;
 
-                if (inode->nlookup && __is_inode_hashed (inode))
+                if (inode->nlookup)
                         __inode_passivate (inode);
                 else
                         __inode_retire (inode);
@@ -387,11 +423,10 @@ __dentry_create (inode_t *inode, inode_t *parent, const char *name)
         newd = (void *) CALLOC (1, sizeof (*newd));
 
         INIT_LIST_HEAD (&newd->inode_list);
-        INIT_LIST_HEAD (&newd->parent_list);
         INIT_LIST_HEAD (&newd->hash);
 
-        list_add (&newd->parent_list, &parent->child_list);
-        newd->parent = __inode_ref (parent);
+        if (parent)
+                newd->parent = __inode_ref (parent);
         newd->name = strdup (name);
 
         list_add (&newd->inode_list, &inode->dentry_list);
@@ -418,7 +453,6 @@ __inode_create (inode_table_t *table)
         INIT_LIST_HEAD (&newi->list);
         INIT_LIST_HEAD (&newi->hash);
         INIT_LIST_HEAD (&newi->dentry_list);
-        INIT_LIST_HEAD (&newi->child_list);
 
 
         list_add (&newi->list, &table->lru);
@@ -496,67 +530,101 @@ inode_search (inode_table_t *table, ino_t ino, const char *name)
 }
 
 
-static void
-__copy_dentries (inode_t *oldi, inode_t *newi)
+dentry_t *
+__dentry_grep (inode_table_t *table, inode_t *parent, const char *name)
 {
+        int       hash = 0;
         dentry_t *dentry = NULL;
-        dentry_t *newd = NULL;
         dentry_t *tmp = NULL;
 
-        list_for_each_entry (dentry, &oldi->dentry_list, inode_list) {
-                tmp = __dentry_search_for_inode (newi, dentry->parent->ino,
-                                                 dentry->name);
+        hash = hash_dentry (parent, name, table->hashsize);
 
-                if (!tmp) {
-                        newd = __dentry_create (newi, dentry->parent,
-                                                dentry->name);
-                } else {
-                        newd = tmp;
+        list_for_each_entry (tmp, &table->name_hash[hash], hash) {
+                if (tmp->parent == parent && !strcmp (tmp->name, name)) {
+                        dentry = tmp;
+                        break;
                 }
+        }
+
+        return dentry;
+}
+
+
+inode_t *
+inode_grep (inode_table_t *table, inode_t *parent, const char *name)
+{
+        inode_t   *inode = NULL;
+        dentry_t  *dentry = NULL;
+
+        pthread_mutex_lock (&table->lock);
+        {
+                dentry = __dentry_grep (table, parent, name);
+
+                if (dentry)
+                        inode = dentry->inode;
+
+                if (inode)
+                        __inode_ref (inode);
+        }
+        pthread_mutex_unlock (&table->lock);
+
+        return inode;
+}
+
 
-                if (__is_dentry_hashed (dentry)) {
-                        __dentry_unhash (dentry);
-                        __dentry_hash (newd);
+inode_t *
+__inode_get (inode_table_t *table, ino_t ino, uint64_t gen)
+{
+        inode_t   *inode = NULL;
+
+        inode = __inode_search (table, ino);
+
+        if (gen) {
+                if (!inode || inode->generation != gen) {
+                        inode = __inode_search_attic (table, ino, gen);
                 }
         }
+
+        return inode;
 }
 
 
-static void
-__adopt_children (inode_t *oldi, inode_t *newi)
+inode_t *
+inode_get (inode_table_t *table, ino_t ino, uint64_t gen)
 {
-        dentry_t *dentry = NULL;
+        inode_t   *inode = NULL;
 
-        list_for_each_entry (dentry, &oldi->child_list, parent_list) {
-                assert (dentry->parent == oldi);
-                __inode_unref (dentry->parent);
-                dentry->parent = __inode_ref (newi);
+        pthread_mutex_lock (&table->lock);
+        {
+                inode = __inode_get (table, ino, gen);
         }
+        pthread_mutex_unlock (&table->lock);
 
-        list_splice_init (&oldi->child_list, &newi->child_list);
+        return inode;
 }
 
 
-static void
-__inode_replace (inode_t *oldi, inode_t *newi)
+static int
+__inode_atticize (inode_t *inode)
 {
-        gf_log (oldi->table->name, GF_LOG_DEBUG,
-                "inode(%"PRId64") replaced (%"PRId64"",
-                oldi->ino, newi->ino);
+        inode_table_t *table = NULL;
 
-        __copy_dentries (oldi, newi);
-        __adopt_children (oldi, newi);
+        table = inode->table;
 
-        newi->nlookup    = oldi->nlookup;
-        newi->generation = oldi->generation;
+        __inode_unhash (inode);
+
+        list_add (&inode->hash, &table->attic);
+        inode->in_attic = 1;
+        table->attic_size++;
 
-        oldi->nlookup    = 0;
-        oldi->generation = 0;
+        return 0;
+}
 
-        __inode_unhash (oldi);
 
-        if (newi->ino == 1)
-                newi->table->root = newi;
+uint64_t
+inode_gen_from_stat (struct stat *stbuf)
+{
+        return (uint64_t) stbuf->st_dev;
 }
 
 
@@ -568,62 +636,68 @@ __inode_link (inode_t *inode, inode_t *parent, const char *name,
         dentry_t      *old_dentry = NULL;
         inode_t       *old_inode = NULL;
         inode_table_t *table = NULL;
+        inode_t       *link_inode = NULL;
 
         table = inode->table;
 
-        if (inode->ino)
-                assert (inode->ino == stbuf->st_ino);
+        link_inode = inode;
 
-        inode->ino     = stbuf->st_ino;
-        inode->st_mode = stbuf->st_mode;
+        if (!__is_inode_hashed (inode)) {
+                inode->ino        = stbuf->st_ino;
+                inode->st_mode    = stbuf->st_mode;
+                inode->generation = inode_gen_from_stat (stbuf);
 
-        old_inode = __inode_search (table, stbuf->st_ino);
+                old_inode = __inode_search (table, inode->ino);
 
-        if (old_inode && old_inode != inode) {
-                __inode_ref (old_inode);
-                __inode_replace (old_inode, inode);
-                __inode_unref (old_inode);
+                if (old_inode) {
+                        if (old_inode->generation < inode->generation) {
+                                __inode_atticize (old_inode);
+                                __inode_hash (inode);
+                        } else {
+                                link_inode = old_inode;
+                        }
+                }
         }
-        __inode_hash (inode);
 
-        if (parent) {
-                dentry = __dentry_search_for_inode (inode, parent->ino, name);
-                if (!dentry) {
-                        dentry = __dentry_create (inode, parent, name);
-                }
+        /* use only link_inode beyond this point */
+        if (name) {
+                old_dentry = __dentry_grep (table, parent, name);
 
-                old_dentry = __dentry_search (table, parent->ino, name);
                 if (old_dentry) {
-                        __dentry_unhash (old_dentry);
+                        if (old_dentry->inode != link_inode)
+                                __dentry_unset (old_dentry);
+                } else {
+                        dentry = __dentry_create (link_inode, parent, name);
+                        dentry->inode = link_inode;
+                        __dentry_hash (dentry);
                 }
-
-                __dentry_hash (dentry);
-        } else if (inode->ino != 1) {
-                gf_log (table->name, GF_LOG_DEBUG,
-                        "child (%"PRId64") without a parent!", inode->ino);
         }
-        
-        return inode;
+
+        return link_inode;
 }
 
 
-int
+inode_t *
 inode_link (inode_t *inode, inode_t *parent, const char *name,
             struct stat *stbuf)
 {
         inode_table_t *table = NULL;
+        inode_t       *linked_inode = NULL;
 
         table = inode->table;
 
         pthread_mutex_lock (&table->lock);
         {
-                inode = __inode_link (inode, parent, name, stbuf);
+                linked_inode = __inode_link (inode, parent, name, stbuf);
+
+                if (linked_inode)
+                        __inode_ref (linked_inode);
         }
         pthread_mutex_unlock (&table->lock);
 
         inode_table_prune (table);
 
-        return 0;
+        return linked_inode;
 }
 
 
@@ -631,20 +705,12 @@ int
 inode_lookup (inode_t *inode)
 {
         inode_table_t *table = NULL;
-        inode_t       *lookup_inode = NULL;
 
         table = inode->table;
-        lookup_inode = inode;
 
         pthread_mutex_lock (&table->lock);
         {
-                if (!__is_inode_hashed (inode)) {
-                        lookup_inode = __inode_search (table, inode->ino);
-                        if (lookup_inode == NULL)
-                                lookup_inode = inode;
-                }
-
-                __inode_lookup (lookup_inode);
+                __inode_lookup (inode);
         }
         pthread_mutex_unlock (&table->lock);
 
@@ -656,20 +722,12 @@ int
 inode_forget (inode_t *inode, uint64_t nlookup)
 {
         inode_table_t *table = NULL;
-        inode_t       *forget_inode = NULL;
 
         table = inode->table;
-        forget_inode = inode;
 
         pthread_mutex_lock (&table->lock);
         {
-                if (!__is_inode_hashed (inode)) {
-                        forget_inode = __inode_search (table, inode->ino);
-                        if (forget_inode == NULL)
-                                forget_inode = inode;
-                }
-
-                __inode_forget (forget_inode, nlookup);
+                __inode_forget (inode, nlookup);
         }
         pthread_mutex_unlock (&table->lock);
 
@@ -696,20 +754,15 @@ void
 inode_unlink (inode_t *inode, inode_t *parent, const char *name)
 {
         inode_table_t *table = NULL;
-        inode_t       *unlink_inode = NULL;
+
+        if (!inode)
+                return;
 
         table = inode->table;
-        unlink_inode = inode;
 
         pthread_mutex_lock (&table->lock);
         {
-                if (!__is_inode_hashed (inode)) {
-                        unlink_inode = __inode_search (table, inode->ino);
-                        if (unlink_inode == NULL)
-                                unlink_inode = inode;
-                }
-
-                __inode_unlink (unlink_inode, parent, name);
+                __inode_unlink (inode, parent, name);
         }
         pthread_mutex_unlock (&table->lock);
 
@@ -722,25 +775,12 @@ inode_rename (inode_table_t *table, inode_t *srcdir, const char *srcname,
               inode_t *dstdir, const char *dstname, inode_t *inode,
               struct stat *stbuf)
 {
-        dentry_t      *old_dst = NULL;
-        inode_t       *rename_inode = NULL;
-
-        rename_inode = inode;
+        table = inode->table;
 
         pthread_mutex_lock (&table->lock);
         {
-                if (!__is_inode_hashed (inode)) {
-                        rename_inode = __inode_search (table, inode->ino);
-                        if (rename_inode == NULL)
-                                rename_inode = inode;
-                }
-
-                old_dst = __dentry_search (table, dstdir->ino, dstname);
-                if (old_dst)
-                        __dentry_unset (old_dst);
-
-                __inode_unlink (rename_inode, srcdir, srcname);
-                __inode_link (rename_inode, dstdir, dstname, stbuf);
+                __inode_link (inode, dstdir, dstname, stbuf);
+                __inode_unlink (inode, srcdir, srcname);
         }
         pthread_mutex_unlock (&table->lock);
 
@@ -792,7 +832,10 @@ inode_parent (inode_t *inode, ino_t par, const char *name)
                 }
 
                 if (dentry)
-                        parent = __inode_ref (dentry->parent);
+                        parent = dentry->parent;
+
+                if (parent)
+                        __inode_ref (parent);
         }
         pthread_mutex_unlock (&table->lock);
 
diff --git a/libglusterfs/src/inode.h b/libglusterfs/src/inode.h
index a64573b98..d1486ca31 100644
--- a/libglusterfs/src/inode.h
+++ b/libglusterfs/src/inode.h
@@ -57,13 +57,17 @@ struct _inode_table {
         uint32_t           lru_size;    /* count of inodes in lru list  */
         struct list_head   purge;       /* list of inodes to be purged soon */
         uint32_t           purge_size;  /* count of inodes in purge list */
+
+        struct list_head   attic;       /* list of inodes which do not have the latest generation
+                                           number. inode_t's @hash is linked with @attic. It is
+                                           otherwise linked with @inode_hash */
+        uint32_t           attic_size;
 };
 
 
 struct _dentry {
         struct list_head   inode_list;   /* list of dentries of inode */
         struct list_head   hash;         /* hash table pointers */
-        struct list_head   parent_list;  /* list of dentries under the parent  */
         inode_t           *inode;        /* inode of this directory entry */
         char              *name;         /* name of the directory entry */
         inode_t           *parent;       /* directory of the entry */
@@ -77,20 +81,20 @@ struct _inode_ctx {
 };
 
 struct _inode {
-        inode_table_t    *table;         /* the table this inode belongs to */
-        gf_lock_t         lock;
-        uint64_t          nlookup;
-        uint64_t          generation;
-        uint32_t          ref;           /* reference count on this inode */
-        ino_t             ino;           /* inode number in the storage (persistent) */
-        mode_t            st_mode;       /* what kind of file */
-        struct list_head  fd_list;       /* list of open files on this inode */
-        struct list_head  dentry_list;   /* list of directory entries for this inode */
-        struct list_head  child_list;    /* list of directory entries under this inode */
-        struct list_head  hash;          /* hash table pointers */
-        struct list_head  list;          /* active/lru/purge */
-
-	struct _inode_ctx *_ctx;    /* replacement for dict_t *(inode->ctx) */
+        inode_table_t       *table;         /* the table this inode belongs to */
+        gf_lock_t            lock;
+        uint64_t             nlookup;
+        uint64_t             generation;
+        uint32_t             in_attic;      /* whether @hash is linked with @inode_hash or @attic */
+        uint32_t             ref;           /* reference count on this inode */
+        ino_t                ino;           /* inode number in the storage (persistent) */
+        mode_t               st_mode;       /* what kind of file */
+        struct list_head     fd_list;       /* list of open files on this inode */
+        struct list_head     dentry_list;   /* list of directory entries for this inode */
+        struct list_head     hash;          /* hash table pointers */
+        struct list_head     list;          /* active/lru/purge */
+
+	struct _inode_ctx   *_ctx;    /* replacement for dict_t *(inode->ctx) */
 };
 
 
@@ -103,14 +107,12 @@ inode_new (inode_table_t *table);
 inode_t *
 inode_search (inode_table_t *table, ino_t ino, const char *name);
 
-int
+inode_t *
 inode_link (inode_t *inode, inode_t *parent,
             const char *name, struct stat *stbuf);
 
 void
-inode_unlink (inode_t *inode,
-              inode_t *parent,
-              const char *name);
+inode_unlink (inode_t *inode, inode_t *parent, const char *name);
 
 inode_t *
 inode_parent (inode_t *inode, ino_t par, const char *name);
@@ -125,32 +127,27 @@ int
 inode_lookup (inode_t *inode);
 
 int
-inode_forget (inode_t *inode,
-	      uint64_t nlookup);
+inode_forget (inode_t *inode, uint64_t nlookup);
 
 int
-inode_rename (inode_table_t *table,
-	      inode_t *olddir,
-	      const char *oldname,
-	      inode_t *newdir,
-	      const char *newname,
-	      inode_t *inode,
-	      struct stat *stbuf);
+inode_rename (inode_table_t *table, inode_t *olddir, const char *oldname,
+	      inode_t *newdir, const char *newname,
+	      inode_t *inode, struct stat *stbuf);
 
+inode_t *
+inode_grep (inode_table_t *table, inode_t *parent, const char *name);
 
-int32_t
-inode_path (inode_t *inode,
-	    const char *name,
-	    char **bufp);
+inode_t *
+inode_get (inode_table_t *table, ino_t ino, uint64_t gen);
+
+int
+inode_path (inode_t *inode, const char *name, char **bufp);
 
 inode_t *
-inode_from_path (inode_table_t *table,
-		 const char *path);
+inode_from_path (inode_table_t *table, const char *path);
 
 dentry_t *
-dentry_search_for_inode (inode_t *inode,
-                         ino_t par,
-                         const char *name);
+dentry_search_for_inode (inode_t *inode, ino_t par, const char *name);
 
 int
 __inode_ctx_put (inode_t *inode, xlator_t *xlator, uint64_t value);