performance/io-cache: change data structure used to store page-cache.

- io-cache uses rbtree based hash tables to store page-cache instead of lists.

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

BUG: 335 (Io-cache optimization)
URL: http://bugs.gluster.com/cgi-bin/bugzilla3/show_bug.cgi?id=335

5 files changed, 90 insertions, 69 deletions

diff --git a/xlators/performance/io-cache/src/Makefile.am b/xlators/performance/io-cache/src/Makefile.am
index b1bf5bfbf71..e3d816f1542 100644
--- a/xlators/performance/io-cache/src/Makefile.am
+++ b/xlators/performance/io-cache/src/Makefile.am
@@ -9,6 +9,6 @@ io_cache_la_LIBADD = $(top_builddir)/libglusterfs/src/libglusterfs.la
 noinst_HEADERS = io-cache.h
 
 AM_CFLAGS = -fPIC -D_FILE_OFFSET_BITS=64 -D_GNU_SOURCE -Wall -D$(GF_HOST_OS) \
-	-I$(top_srcdir)/libglusterfs/src -shared -nostartfiles $(GF_CFLAGS)
+	-I$(top_srcdir)/libglusterfs/src -I$(CONTRIBDIR)/rbtree -shared -nostartfiles $(GF_CFLAGS)
 
 CLEANFILES = 
diff --git a/xlators/performance/io-cache/src/io-cache.c b/xlators/performance/io-cache/src/io-cache.c
index 09ea4feb78c..5c1f74db12f 100644
--- a/xlators/performance/io-cache/src/io-cache.c
+++ b/xlators/performance/io-cache/src/io-cache.c
@@ -80,7 +80,7 @@ ioc_inode_need_revalidate (ioc_inode_t *ioc_inode)
 
 	ret = gettimeofday (&tv, NULL);
 
-	if (time_elapsed (&tv, &ioc_inode->tv) >= table->cache_timeout)
+	if (time_elapsed (&tv, &ioc_inode->cache.tv) >= table->cache_timeout)
 		need_revalidate = 1;
 
 	return need_revalidate;
@@ -100,7 +100,8 @@ __ioc_inode_flush (ioc_inode_t *ioc_inode)
 	int32_t    destroy_size = 0;
 	int32_t    ret = 0;
 
-	list_for_each_entry_safe (curr, next, &ioc_inode->pages, pages) {
+	list_for_each_entry_safe (curr, next, &ioc_inode->cache.page_lru,
+                                  page_lru) {
 		ret = ioc_page_destroy (curr);
     
 		if (ret != -1) 
@@ -185,7 +186,7 @@ ioc_lookup_cbk (call_frame_t *frame, void *cookie, xlator_t *this,
 		/* update the time-stamp of revalidation */
 		ioc_inode_lock (ioc_inode);
 		{
-			gettimeofday (&ioc_inode->tv, NULL);
+			gettimeofday (&ioc_inode->cache.tv, NULL);
 		}
 		ioc_inode_unlock (ioc_inode);
 		
@@ -271,7 +272,7 @@ ioc_cache_validate_cbk (call_frame_t *frame, void *cookie, xlator_t *this,
 		{
 			destroy_size = __ioc_inode_flush (ioc_inode);
 			if (op_ret >= 0)
-				ioc_inode->mtime = stbuf->st_mtime;
+				ioc_inode->cache.mtime = stbuf->st_mtime;
 		}
 		ioc_inode_unlock (ioc_inode);
 		local_stbuf = NULL;
@@ -290,7 +291,7 @@ ioc_cache_validate_cbk (call_frame_t *frame, void *cookie, xlator_t *this,
   
 	ioc_inode_lock (ioc_inode);
 	{
-		gettimeofday (&ioc_inode->tv, NULL);
+		gettimeofday (&ioc_inode->cache.tv, NULL);
 	}
 	ioc_inode_unlock (ioc_inode);
 
@@ -1117,7 +1118,7 @@ ioc_lk (call_frame_t *frame, xlator_t *this, fd_t *fd, int32_t cmd,
 
 	ioc_inode_lock (ioc_inode);
 	{
-		gettimeofday (&ioc_inode->tv, NULL);
+		gettimeofday (&ioc_inode->cache.tv, NULL);
 	}
 	ioc_inode_unlock (ioc_inode);
 
diff --git a/xlators/performance/io-cache/src/io-cache.h b/xlators/performance/io-cache/src/io-cache.h
index 74a7071472e..49d3d000b4f 100644
--- a/xlators/performance/io-cache/src/io-cache.h
+++ b/xlators/performance/io-cache/src/io-cache.h
@@ -34,11 +34,14 @@
 #include "xlator.h"
 #include "common-utils.h"
 #include "call-stub.h"
+#include "rbthash.h"
+#include "hashfn.h"
 #include <sys/time.h>
 #include <fnmatch.h>
 
 #define IOC_PAGE_SIZE    (1024 * 128)   /* 128KB */
 #define IOC_CACHE_SIZE   (32 * 1024 * 1024)
+#define IOC_PAGE_TABLE_BUCKET_COUNT 4096
 
 struct ioc_table;
 struct ioc_local;
@@ -110,7 +113,6 @@ struct ioc_local {
  *
  */
 struct ioc_page {
-	struct list_head    pages;
 	struct list_head    page_lru;
 	struct ioc_inode    *inode;   /* inode this page belongs to */
 	struct ioc_priority *priority;
@@ -125,28 +127,32 @@ struct ioc_page {
 	pthread_mutex_t     page_lock;
 };
 
+struct ioc_cache {
+        rbthash_table_t  *page_table;
+        struct list_head  page_lru;
+	time_t            mtime;       /*
+                                        * mtime of the server file when last
+                                        * cached
+                                        */
+	struct timeval    tv;          /*
+                                        * time-stamp at last re-validate
+                                        */
+};
+
 struct ioc_inode {
-	struct ioc_table *table;
-	struct list_head pages;      /* list of pages of this inode */
-	struct list_head inode_list; /*
-                                      * list of inodes, maintained by io-cache
-                                      * translator
-                                      */
-	struct list_head inode_lru;
-	struct list_head page_lru;
-	struct ioc_waitq *waitq;
-	pthread_mutex_t  inode_lock;
-	uint32_t         weight;      /*
-                                       * weight of the inode, increases on each
-                                       * read
-                                       */
-	time_t           mtime;       /*
-                                       * mtime of the server file when last
-                                       * cached
-                                       */
-	struct timeval   tv;          /*
-                                       * time-stamp at last re-validate
-                                       */
+	struct ioc_table      *table;
+        struct ioc_cache       cache;        
+	struct list_head       inode_list; /*
+                                            * list of inodes, maintained by
+                                            * io-cache translator
+                                            */
+	struct list_head       inode_lru;
+	struct ioc_waitq      *waitq;
+	pthread_mutex_t        inode_lock;
+	uint32_t               weight;      /*
+                                             * weight of the inode, increases
+                                             * on each read
+                                             */
 };
 
 struct ioc_table {
diff --git a/xlators/performance/io-cache/src/ioc-inode.c b/xlators/performance/io-cache/src/ioc-inode.c
index 23c25be1f36..7260def418e 100644
--- a/xlators/performance/io-cache/src/ioc-inode.c
+++ b/xlators/performance/io-cache/src/ioc-inode.c
@@ -25,6 +25,19 @@
 #include "io-cache.h"
 
 
+inline uint32_t
+ioc_hashfn (void *data, int len)
+{
+        uint32_t        hash = 0;
+        while (len > 0) {
+                hash ^= *(uint32_t *)data;
+                data += sizeof (uint32_t);
+                len -= sizeof (uint32_t);
+        }
+
+        return hash;
+}
+
 /*
  * str_to_ptr - convert a string to pointer
  * @string: string
@@ -163,8 +176,15 @@ ioc_inode_update (ioc_table_t *table, inode_t *inode, uint32_t weight)
 	ioc_inode->table = table;
  
 	/* initialize the list for pages */
-	INIT_LIST_HEAD (&ioc_inode->pages);
-	INIT_LIST_HEAD (&ioc_inode->page_lru);
+        ioc_inode->cache.page_table = rbthash_table_init (IOC_PAGE_TABLE_BUCKET_COUNT,
+                                                          ioc_hashfn, free);
+        if (ioc_inode->cache.page_table == NULL) {
+                FREE (ioc_inode);
+                ioc_inode = NULL;
+                goto out;
+        }
+
+	INIT_LIST_HEAD (&ioc_inode->cache.page_lru);
 
 	ioc_table_lock (table);
 
diff --git a/xlators/performance/io-cache/src/page.c b/xlators/performance/io-cache/src/page.c
index 97cf4ae6c2e..4f9e76cb271 100644
--- a/xlators/performance/io-cache/src/page.c
+++ b/xlators/performance/io-cache/src/page.c
@@ -30,35 +30,28 @@
 #include <assert.h>
 #include <sys/time.h>
 
+char
+ioc_empty (struct ioc_cache *cache)
+{
+        return list_empty (&cache->page_lru);
+}
+
 ioc_page_t *
 ioc_page_get (ioc_inode_t *ioc_inode, off_t offset)
 {
-	int8_t       found = 0;
-	ioc_page_t   *page = NULL;
-	ioc_table_t  *table = NULL;
-	off_t        rounded_offset = 0;
+	ioc_page_t   *page           = NULL;
+	ioc_table_t  *table          = NULL;
+	off_t         rounded_offset = 0;
 
         table = ioc_inode->table;
         rounded_offset = floor (offset, table->page_size);
  
-	if (list_empty (&ioc_inode->pages)) {
-		return NULL;
-	}
-
-	list_for_each_entry (page, &ioc_inode->pages, pages) {
-		if (page->offset == rounded_offset) {
-			found = 1;
-			break;
-		}
-	}
+        page = rbthash_get (ioc_inode->cache.page_table, &rounded_offset,
+                            sizeof (rounded_offset));
 
-	/* was previously returning ioc_inode itself.., 
-	 * 1st of its type and found one more downstairs :O */
-	if (!found){
-		page = NULL;
-	} else {
+        if (page != NULL) {
 		/* push the page to the end of the lru list */
-		list_move_tail (&page->page_lru, &ioc_inode->page_lru);
+		list_move_tail (&page->page_lru, &ioc_inode->cache.page_lru);
 	}
 
 	return page;
@@ -74,7 +67,7 @@ ioc_page_get (ioc_inode_t *ioc_inode, off_t offset)
 int64_t
 ioc_page_destroy (ioc_page_t *page)
 {
-	int64_t page_size = 0;
+	int64_t  page_size = 0;
 
 	page_size = iobref_size (page->iobref);
 
@@ -82,8 +75,8 @@ ioc_page_destroy (ioc_page_t *page)
 		/* frames waiting on this page, do not destroy this page */
 		page_size = -1;
 	} else {
-
-		list_del (&page->pages);
+                rbthash_remove (page->inode->cache.page_table, &page->offset,
+                                sizeof (page->offset));
 		list_del (&page->page_lru);
     
 		gf_log (page->inode->table->xl->name, GF_LOG_TRACE,
@@ -98,7 +91,6 @@ ioc_page_destroy (ioc_page_t *page)
 		}
     
 		page->inode = NULL;
-    
 	}
 
 	if (page_size != -1) {
@@ -140,8 +132,8 @@ ioc_prune (ioc_table_t *table)
 				/* { */
 
 				list_for_each_entry_safe (page, next, 
-							  &curr->page_lru, 
-							  page_lru) {
+							  &curr->cache.page_lru,
+                                                          page_lru) {
 					/* done with all pages, and not 
 					 * reached equilibrium yet??
 					 * continue with next inode in 
@@ -163,7 +155,7 @@ ioc_prune (ioc_table_t *table)
 					if (size_pruned >= size_to_prune)
 						break;
 				} /* list_for_each_entry_safe(page...) */
-				if (list_empty (&curr->pages)) {
+				if (ioc_empty (&curr->cache)) {
 					list_del_init (&curr->inode_lru);
 				}
 
@@ -194,10 +186,10 @@ ioc_prune (ioc_table_t *table)
 ioc_page_t *
 ioc_page_create (ioc_inode_t *ioc_inode, off_t offset)
 {
-	ioc_table_t *table = NULL;
-	ioc_page_t  *page = NULL;
-	off_t       rounded_offset = 0;
-	ioc_page_t  *newpage = NULL;
+	ioc_table_t *table          = NULL;
+	ioc_page_t  *page           = NULL;
+	off_t        rounded_offset = 0;
+	ioc_page_t  *newpage        = NULL;
   
         table = ioc_inode->table;
         rounded_offset = floor (offset, table->page_size);
@@ -219,8 +211,10 @@ ioc_page_create (ioc_inode_t *ioc_inode, off_t offset)
 	newpage->inode = ioc_inode;
 	pthread_mutex_init (&newpage->page_lock, NULL);
 
-	list_add_tail (&newpage->page_lru, &ioc_inode->page_lru);
-	list_add_tail (&newpage->pages, &ioc_inode->pages);
+        rbthash_insert (ioc_inode->cache.page_table, newpage, &rounded_offset,
+                        sizeof (rounded_offset));
+ 
+	list_add_tail (&newpage->page_lru, &ioc_inode->cache.page_lru);
 
 	page = newpage;
 
@@ -293,12 +287,12 @@ ioc_cache_still_valid (ioc_inode_t *ioc_inode, struct stat *stbuf)
 	int8_t cache_still_valid = 1;
   
 #if 0
-	if (!stbuf || (stbuf->st_mtime != ioc_inode->mtime) || 
+	if (!stbuf || (stbuf->st_mtime != ioc_inode->cache.mtime) || 
 	    (stbuf->st_mtim.tv_nsec != ioc_inode->stbuf.st_mtim.tv_nsec))
 		cache_still_valid = 0;
 
 #else
-	if (!stbuf || (stbuf->st_mtime != ioc_inode->mtime))
+	if (!stbuf || (stbuf->st_mtime != ioc_inode->cache.mtime))
 		cache_still_valid = 0;
 
 #endif
@@ -369,9 +363,9 @@ ioc_fault_cbk (call_frame_t *frame, void *cookie, xlator_t *this,
 		} 
     
 		if (op_ret >= 0)
-			ioc_inode->mtime = stbuf->st_mtime;
+			ioc_inode->cache.mtime = stbuf->st_mtime;
     
-		gettimeofday (&ioc_inode->tv, NULL);
+		gettimeofday (&ioc_inode->cache.tv, NULL);
     
 		if (op_ret < 0) {
 			/* error, readv returned -1 */
@@ -571,7 +565,7 @@ ioc_frame_fill (ioc_page_t *page, call_frame_t *frame, off_t offset,
 		frame, offset, size, page->size, local->wait_count);
 
 	/* immediately move this page to the end of the page_lru list */
-	list_move_tail (&page->page_lru, &ioc_inode->page_lru);
+	list_move_tail (&page->page_lru, &ioc_inode->cache.page_lru);
 	/* fill local->pending_size bytes from local->pending_offset */
 	if (local->op_ret != -1 && page->size) {
 		if (offset > page->offset)