[sheepdog] [PATCH] add a buffer to object list cache as a second level cache

[levin li]

From: levin li <xingke.lwp at taobao.com>

It's inefficient for get_obj_list() to traverse the object
list rbtree to get the object list every time, so I add a buffer
to cache the list, every time in get_obj_list() if the rbtree
has changed which is detected by the version number, we update
the buffer, then we can just read the buffer by memcpy() if the
object list has not been changed, instead of traverse the full
rbtree.

Signed-off-by: levin li <xingke.lwp at taobao.com>
---
 sheep/object_list_cache.c |   42 ++++++++++++++++++++++++++++++++++--------
 sheep/ops.c               |    4 +++-
 sheep/sheep_priv.h        |    6 +++++-
 3 files changed, 42 insertions(+), 10 deletions(-)

diff --git a/sheep/object_list_cache.c b/sheep/object_list_cache.c
index 28cdbbc..2f3ae3d 100644
--- a/sheep/object_list_cache.c
+++ b/sheep/object_list_cache.c
@@ -16,6 +16,7 @@
 #include <unistd.h>
 #include <sys/types.h>
 #include <pthread.h>
+#include <errno.h>
 
 #include "sheep_priv.h"
 #include "strbuf.h"
@@ -37,6 +38,10 @@ int init_objlist_cache(void)
 	pthread_rwlock_init(&obj_list_cache.lock, NULL);
 	obj_list_cache.root = RB_ROOT;
 	obj_list_cache.cache_size = 0;
+	obj_list_cache.tree_version = 1;
+	obj_list_cache.buf_version = 0;
+	obj_list_cache.buf_size = 0;
+	obj_list_cache.buffer = NULL;
 
 	if (sd_store) {
 		buf = zalloc(1 << 22);
@@ -123,8 +128,10 @@ int check_and_insert_objlist_cache(uint64_t oid)
 	p = objlist_cache_rb_insert(&obj_list_cache.root, entry);
 	if (p)
 		free(entry);
-	else
+	else {
 		obj_list_cache.cache_size++;
+		obj_list_cache.tree_version++;
+	}
 	pthread_rwlock_unlock(&obj_list_cache.lock);
 
 	return 0;
@@ -134,18 +141,37 @@ int get_obj_list(const struct sd_list_req *hdr, struct sd_list_rsp *rsp, void *d
 {
 	uint64_t *list = (uint64_t *)data;
 	int nr = 0;
-	int res = SD_RES_SUCCESS;
 	struct objlist_cache_entry *entry;
 	struct rb_node *p;
 
+	rsp->data_length = obj_list_cache.cache_size * sizeof(uint64_t);
+
 	pthread_rwlock_rdlock(&obj_list_cache.lock);
-	for (p = rb_first(&obj_list_cache.root); p; p = rb_next(p)) {
-		entry = rb_entry(p, struct objlist_cache_entry, node);
-		list[nr++] = entry->oid;
+	if (obj_list_cache.tree_version == obj_list_cache.buf_version)
+		memcpy(list, obj_list_cache.buffer, rsp->data_length);
+	else {
+		for (p = rb_first(&obj_list_cache.root); p; p = rb_next(p)) {
+			entry = rb_entry(p, struct objlist_cache_entry, node);
+			list[nr++] = entry->oid;
+		}
+
+		if (obj_list_cache.buf_size <
+			obj_list_cache.cache_size * sizeof(uint64_t)) {
+			int new_size;
+
+			new_size = obj_list_cache.cache_size * sizeof(uint64_t);
+			obj_list_cache.buffer =
+				realloc(obj_list_cache.buffer, new_size);
+
+			if (ENOMEM != errno) {
+				obj_list_cache.buf_version =
+					obj_list_cache.tree_version;
+				obj_list_cache.buf_size = new_size;
+				memcpy(obj_list_cache.buffer, list, new_size);
+			}
+		}
 	}
 	pthread_rwlock_unlock(&obj_list_cache.lock);
 
-	rsp->data_length = nr * sizeof(uint64_t);
-
-	return res;
+	return SD_RES_SUCCESS;
 }
diff --git a/sheep/ops.c b/sheep/ops.c
index b4df70f..582ed24 100644
--- a/sheep/ops.c
+++ b/sheep/ops.c
@@ -712,8 +712,10 @@ static int store_remove_obj(struct request *req)
 		ret =  SD_RES_EIO;
 	}
 	pthread_rwlock_wrlock(&obj_list_cache.lock);
-	if (!objlist_cache_rb_remove(&obj_list_cache.root, oid))
+	if (!objlist_cache_rb_remove(&obj_list_cache.root, oid)) {
 		obj_list_cache.cache_size--;
+		obj_list_cache.tree_version++;
+	}
 	pthread_rwlock_unlock(&obj_list_cache.lock);
  out:
 	strbuf_release(&buf);
diff --git a/sheep/sheep_priv.h b/sheep/sheep_priv.h
index 21ee282..3c46ca5 100644
--- a/sheep/sheep_priv.h
+++ b/sheep/sheep_priv.h
@@ -203,8 +203,12 @@ static inline struct store_driver *find_store_driver(const char *name)
 }
 
 struct objlist_cache {
-	struct rb_root root;
+	int tree_version;
+	int buf_version;
+	int buf_size;
+	uint64_t *buffer;
 	int cache_size;
+	struct rb_root root;
 	pthread_rwlock_t lock;
 };
 
-- 
1.7.10