[RFC v2 78/83] GC: Thorough garbage collection.

[Andiry Xu]

From: Andiry Xu 

After fast gc, if the valid log entries still account for less
than the half of the log size, NOVA starts thorough garbage collection,
allocates a new log, copies the live log entries to it, and switches
to the new log atomically. The radix tree needs to be updated to point
to the new log.

Example:
I = Invalid, V = Valid

VIIV ->  -> VVII

 ||
 ||  fast gc
 \/

VIIV -> VVII

 ||
 ||  thorough gc
 \/



Signed-off-by: Andiry Xu 
---
 fs/nova/gc.c | 273 +++
 1 file changed, 273 insertions(+)

diff --git a/fs/nova/gc.c b/fs/nova/gc.c
index 1634c04..d74286e 100644
--- a/fs/nova/gc.c
+++ b/fs/nova/gc.c
@@ -18,6 +18,62 @@
 #include "nova.h"
 #include "inode.h"
 
+static bool curr_log_entry_invalid(struct super_block *sb,
+   struct nova_inode *pi, struct nova_inode_info_header *sih,
+   u64 curr_p, size_t *length)
+{
+   struct nova_file_write_entry *entry;
+   struct nova_dentry *dentry;
+   struct nova_setattr_logentry *setattr_entry;
+   struct nova_link_change_entry *linkc_entry;
+   void *entryc;
+   u8 type;
+   bool ret = true;
+
+   entryc = (void *)nova_get_block(sb, curr_p);
+   type = nova_get_entry_type(entryc);
+
+   switch (type) {
+   case SET_ATTR:
+   setattr_entry = (struct nova_setattr_logentry *) entryc;
+   if (setattr_entry->invalid == 0)
+   ret = false;
+   *length = sizeof(struct nova_setattr_logentry);
+   break;
+   case LINK_CHANGE:
+   linkc_entry = (struct nova_link_change_entry *) entryc;
+   if (linkc_entry->invalid == 0)
+   ret = false;
+   *length = sizeof(struct nova_link_change_entry);
+   break;
+   case FILE_WRITE:
+   entry = (struct nova_file_write_entry *) entryc;
+   if (entry->num_pages != entry->invalid_pages)
+   ret = false;
+   *length = sizeof(struct nova_file_write_entry);
+   break;
+   case DIR_LOG:
+   dentry = (struct nova_dentry *) entryc;
+   if (dentry->invalid == 0)
+   ret = false;
+   if (sih->last_dentry == curr_p)
+   ret = false;
+   *length = le16_to_cpu(dentry->de_len);
+   break;
+   case NEXT_PAGE:
+   /* No more entries in this page */
+   *length = PAGE_SIZE - ENTRY_LOC(curr_p);
+   break;
+   default:
+   nova_dbg("%s: unknown type %d, 0x%llx\n",
+   __func__, type, curr_p);
+   NOVA_ASSERT(0);
+   *length = PAGE_SIZE - ENTRY_LOC(curr_p);
+   break;
+   }
+
+   return ret;
+}
 
 static bool curr_page_invalid(struct super_block *sb,
struct nova_inode *pi, struct nova_inode_info_header *sih,
@@ -68,6 +124,210 @@ static void free_curr_page(struct super_block *sb,
nova_get_blocknr(sb, curr_head, btype), 1);
 }
 
+static int nova_gc_assign_file_entry(struct super_block *sb,
+   struct nova_inode_info_header *sih,
+   struct nova_file_write_entry *old_entry,
+   struct nova_file_write_entry *new_entry)
+{
+   struct nova_file_write_entry *temp;
+   void **pentry;
+   unsigned long start_pgoff = old_entry->pgoff;
+   unsigned int num = old_entry->num_pages;
+   unsigned long curr_pgoff;
+   int i;
+   int ret = 0;
+
+   for (i = 0; i < num; i++) {
+   curr_pgoff = start_pgoff + i;
+
+   pentry = radix_tree_lookup_slot(>tree, curr_pgoff);
+   if (pentry) {
+   temp = radix_tree_deref_slot(pentry);
+   if (temp == old_entry)
+   radix_tree_replace_slot(>tree, pentry,
+   new_entry);
+   }
+   }
+
+   return ret;
+}
+
+static int nova_gc_assign_dentry(struct super_block *sb,
+   struct nova_inode_info_header *sih, struct nova_dentry *old_dentry,
+   struct nova_dentry *new_dentry)
+{
+   struct nova_dentry *temp;
+   void **pentry;
+   unsigned long hash;
+   int ret = 0;
+
+   hash = BKDRHash(old_dentry->name, old_dentry->name_len);
+   nova_dbgv("%s: assign %s hash %lu\n", __func__,
+   old_dentry->name, hash);
+
+   /* FIXME: hash collision ignored here */
+   pentry = radix_tree_lookup_slot(>tree, hash);
+   if (pentry) {
+   temp = radix_tree_deref_slot(pentry);
+   if (temp == old_dentry)
+   radix_tree_replace_slot(>tree, pentry, new_dentry);
+   }
+
+   return ret;
+}
+
+static int nova_gc_assign_new_entry(struct super_block *sb,
+   

[RFC v2 78/83] GC: Thorough garbage collection.

[Andiry Xu]

From: Andiry Xu 

After fast gc, if the valid log entries still account for less
than the half of the log size, NOVA starts thorough garbage collection,
allocates a new log, copies the live log entries to it, and switches
to the new log atomically. The radix tree needs to be updated to point
to the new log.

Example:
I = Invalid, V = Valid

VIIV ->  -> VVII

 ||
 ||  fast gc
 \/

VIIV -> VVII

 ||
 ||  thorough gc
 \/



Signed-off-by: Andiry Xu 
---
 fs/nova/gc.c | 273 +++
 1 file changed, 273 insertions(+)

diff --git a/fs/nova/gc.c b/fs/nova/gc.c
index 1634c04..d74286e 100644
--- a/fs/nova/gc.c
+++ b/fs/nova/gc.c
@@ -18,6 +18,62 @@
 #include "nova.h"
 #include "inode.h"
 
+static bool curr_log_entry_invalid(struct super_block *sb,
+   struct nova_inode *pi, struct nova_inode_info_header *sih,
+   u64 curr_p, size_t *length)
+{
+   struct nova_file_write_entry *entry;
+   struct nova_dentry *dentry;
+   struct nova_setattr_logentry *setattr_entry;
+   struct nova_link_change_entry *linkc_entry;
+   void *entryc;
+   u8 type;
+   bool ret = true;
+
+   entryc = (void *)nova_get_block(sb, curr_p);
+   type = nova_get_entry_type(entryc);
+
+   switch (type) {
+   case SET_ATTR:
+   setattr_entry = (struct nova_setattr_logentry *) entryc;
+   if (setattr_entry->invalid == 0)
+   ret = false;
+   *length = sizeof(struct nova_setattr_logentry);
+   break;
+   case LINK_CHANGE:
+   linkc_entry = (struct nova_link_change_entry *) entryc;
+   if (linkc_entry->invalid == 0)
+   ret = false;
+   *length = sizeof(struct nova_link_change_entry);
+   break;
+   case FILE_WRITE:
+   entry = (struct nova_file_write_entry *) entryc;
+   if (entry->num_pages != entry->invalid_pages)
+   ret = false;
+   *length = sizeof(struct nova_file_write_entry);
+   break;
+   case DIR_LOG:
+   dentry = (struct nova_dentry *) entryc;
+   if (dentry->invalid == 0)
+   ret = false;
+   if (sih->last_dentry == curr_p)
+   ret = false;
+   *length = le16_to_cpu(dentry->de_len);
+   break;
+   case NEXT_PAGE:
+   /* No more entries in this page */
+   *length = PAGE_SIZE - ENTRY_LOC(curr_p);
+   break;
+   default:
+   nova_dbg("%s: unknown type %d, 0x%llx\n",
+   __func__, type, curr_p);
+   NOVA_ASSERT(0);
+   *length = PAGE_SIZE - ENTRY_LOC(curr_p);
+   break;
+   }
+
+   return ret;
+}
 
 static bool curr_page_invalid(struct super_block *sb,
struct nova_inode *pi, struct nova_inode_info_header *sih,
@@ -68,6 +124,210 @@ static void free_curr_page(struct super_block *sb,
nova_get_blocknr(sb, curr_head, btype), 1);
 }
 
+static int nova_gc_assign_file_entry(struct super_block *sb,
+   struct nova_inode_info_header *sih,
+   struct nova_file_write_entry *old_entry,
+   struct nova_file_write_entry *new_entry)
+{
+   struct nova_file_write_entry *temp;
+   void **pentry;
+   unsigned long start_pgoff = old_entry->pgoff;
+   unsigned int num = old_entry->num_pages;
+   unsigned long curr_pgoff;
+   int i;
+   int ret = 0;
+
+   for (i = 0; i < num; i++) {
+   curr_pgoff = start_pgoff + i;
+
+   pentry = radix_tree_lookup_slot(>tree, curr_pgoff);
+   if (pentry) {
+   temp = radix_tree_deref_slot(pentry);
+   if (temp == old_entry)
+   radix_tree_replace_slot(>tree, pentry,
+   new_entry);
+   }
+   }
+
+   return ret;
+}
+
+static int nova_gc_assign_dentry(struct super_block *sb,
+   struct nova_inode_info_header *sih, struct nova_dentry *old_dentry,
+   struct nova_dentry *new_dentry)
+{
+   struct nova_dentry *temp;
+   void **pentry;
+   unsigned long hash;
+   int ret = 0;
+
+   hash = BKDRHash(old_dentry->name, old_dentry->name_len);
+   nova_dbgv("%s: assign %s hash %lu\n", __func__,
+   old_dentry->name, hash);
+
+   /* FIXME: hash collision ignored here */
+   pentry = radix_tree_lookup_slot(>tree, hash);
+   if (pentry) {
+   temp = radix_tree_deref_slot(pentry);
+   if (temp == old_dentry)
+   radix_tree_replace_slot(>tree, pentry, new_dentry);
+   }
+
+   return ret;
+}
+
+static int nova_gc_assign_new_entry(struct super_block *sb,
+   struct nova_inode *pi, struct