[sheepdog] [PATCH v2 6/9] object cache: schedule the object cache in a lru list

levin li levin108 at gmail.com
Wed Jul 25 14:15:22 CEST 2012


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

We put all the cached object into a global lru list, when
the object cache is referenced(read/write), we move the object
to the head of the lru list, then when cache reaches the max
size we can reclaim it from the end of the lru list.

Signed-off-by: levin li <xingke.lwp at taobao.com>
---
 sheep/object_cache.c |  116 +++++++++++++++++++++++++++-----------------------
 1 file changed, 63 insertions(+), 53 deletions(-)

diff --git a/sheep/object_cache.c b/sheep/object_cache.c
index c4ca2b0..aa5a11f 100644
--- a/sheep/object_cache.c
+++ b/sheep/object_cache.c
@@ -144,10 +144,31 @@ object_cache_insert(struct rb_root *root, struct object_cache_entry *new)
 	return NULL; /* insert successfully */
 }
 
+static struct object_cache_entry *object_tree_search(struct rb_root *root,
+						     uint32_t idx)
+{
+	struct rb_node *n = root->rb_node;
+	struct object_cache_entry *t;
+
+	while (n) {
+		t = rb_entry(n, struct object_cache_entry, node);
+
+		if (idx < t->idx)
+			n = n->rb_left;
+		else if (idx > t->idx)
+			n = n->rb_right;
+		else
+			return t; /* found it */
+	}
+
+	return NULL;
+}
+
 static struct object_cache_entry *
-dirty_tree_insert(struct rb_root *root, struct object_cache_entry *new)
+dirty_tree_insert(struct object_cache *oc, uint32_t idx,
+		  uint64_t bmap, int create)
 {
-	struct rb_node **p = &root->rb_node;
+	struct rb_node **p = &oc->dirty_tree.rb_node;
 	struct rb_node *parent = NULL;
 	struct object_cache_entry *entry;
 
@@ -155,20 +176,28 @@ dirty_tree_insert(struct rb_root *root, struct object_cache_entry *new)
 		parent = *p;
 		entry = rb_entry(parent, struct object_cache_entry, dirty_node);
 
-		if (new->idx < entry->idx)
+		if (idx < entry->idx)
 			p = &(*p)->rb_left;
-		else if (new->idx > entry->idx)
+		else if (idx > entry->idx)
 			p = &(*p)->rb_right;
 		else {
 			/* already has this entry, merge bmap */
-			entry->bmap |= new->bmap;
+			entry->bmap |= bmap;
 			return entry;
 		}
 	}
-	rb_link_node(&new->dirty_node, parent, p);
-	rb_insert_color(&new->dirty_node, root);
 
-	return NULL; /* insert successfully */
+	entry = object_tree_search(&oc->object_tree, idx);
+	if (!entry)
+		return NULL;
+
+	entry->bmap |= bmap;
+	entry->flags |= ENTRY_CREATE_BIT;
+	rb_link_node(&entry->dirty_node, parent, p);
+	rb_insert_color(&entry->dirty_node, &oc->dirty_tree);
+	list_add(&entry->list, &oc->dirty_list);
+
+	return entry;
 }
 
 static struct object_cache_entry *dirty_tree_search(struct rb_root *root,
@@ -191,26 +220,6 @@ static struct object_cache_entry *dirty_tree_search(struct rb_root *root,
 	return NULL;
 }
 
-static struct object_cache_entry *object_tree_search(struct rb_root *root,
-						     uint32_t idx)
-{
-	struct rb_node *n = root->rb_node;
-	struct object_cache_entry *t;
-
-	while (n) {
-		t = rb_entry(n, struct object_cache_entry, node);
-
-		if (idx < t->idx)
-			n = n->rb_left;
-		else if (idx > t->idx)
-			n = n->rb_right;
-		else
-			return t; /* found it */
-	}
-
-	return NULL;
-}
-
 static int create_dir_for(uint32_t vid)
 {
 	int ret = 0;
@@ -272,36 +281,28 @@ del_from_dirty_tree_and_list(struct object_cache_entry *entry,
 
 /* Caller should hold the oc->lock */
 static inline void
-add_to_dirty_tree_and_list(struct object_cache *oc,
-			   struct object_cache_entry *entry)
+add_to_dirty_tree_and_list(struct object_cache *oc, uint32_t idx,
+			   uint64_t bmap, int create)
 {
-	if (!dirty_tree_insert(&oc->dirty_tree, entry))
-		list_add(&entry->list, &oc->dirty_list);
-	else
-		free(entry);
-}
-
-static inline struct object_cache_entry *
-alloc_cache_entry(uint32_t idx, uint64_t bmap, int create)
-{
-	struct object_cache_entry *entry = xzalloc(sizeof(*entry));
-
-	entry->idx = idx;
-	entry->bmap = bmap;
-	entry->flags |= ENTRY_CREATE_BIT;
+	struct object_cache_entry *entry;
+	entry = dirty_tree_insert(oc, idx, bmap, create);
+	if (!entry)
+		panic("Can not find object entry %" PRIx32 "\n", idx);
 
-	return entry;
+	/* If cache isn't in reclaiming, move it
+	 * to the head of lru list */
+	cds_list_del_rcu(&entry->lru_list);
+	cds_list_add_rcu(&entry->lru_list,
+			 &sys_cache.cache_lru_list);
 }
 
 static void update_cache_entry(struct object_cache *oc, uint32_t idx,
 		size_t datalen, off_t offset)
 {
-	struct object_cache_entry *entry;
-
-	entry = alloc_cache_entry(idx, calc_object_bmap(datalen, offset), 0);
+	uint64_t bmap = calc_object_bmap(datalen, offset);
 
 	pthread_rwlock_wrlock(&oc->lock);
-	add_to_dirty_tree_and_list(oc, entry);
+	add_to_dirty_tree_and_list(oc, idx, bmap, 0);
 	pthread_rwlock_unlock(&oc->lock);
 }
 
@@ -352,7 +353,6 @@ static int object_cache_lookup(struct object_cache *oc, uint32_t idx,
 	}
 
 	if (create) {
-		struct object_cache_entry *entry;
 		unsigned data_length;
 
 		if (idx_has_vdi_bit(idx))
@@ -368,9 +368,8 @@ static int object_cache_lookup(struct object_cache *oc, uint32_t idx,
 
 			add_to_object_cache(oc, idx);
 
-			entry = alloc_cache_entry(idx, bmap, 1);
 			pthread_rwlock_wrlock(&oc->lock);
-			add_to_dirty_tree_and_list(oc, entry);
+			add_to_dirty_tree_and_list(oc, idx, bmap, 1);
 			pthread_rwlock_unlock(&oc->lock);
 		}
 	}
@@ -801,6 +800,7 @@ int object_cache_handle_request(struct request *req)
 	uint32_t vid = oid_to_vid(oid);
 	uint32_t idx = object_cache_oid_to_idx(oid);
 	struct object_cache *cache;
+	struct object_cache_entry *entry;
 	int ret, create = 0;
 
 	dprintf("%08"PRIx32", len %"PRIu32", off %"PRIu64"\n", idx,
@@ -817,19 +817,29 @@ int object_cache_handle_request(struct request *req)
 			return ret;
 	}
 
+	pthread_rwlock_rdlock(&cache->lock);
+	entry = object_tree_search(&cache->object_tree, idx);
+	pthread_rwlock_unlock(&cache->lock);
+
 	if (hdr->flags & SD_FLAG_CMD_WRITE) {
 		ret = write_cache_object(cache->vid, idx, req->data,
 					 hdr->data_length, hdr->obj.offset);
 		if (ret != SD_RES_SUCCESS)
 			goto out;
 		update_cache_entry(cache, idx, hdr->data_length,
-				hdr->obj.offset);
+				   hdr->obj.offset);
 	} else {
 		ret = read_cache_object(cache->vid, idx, req->data,
 					hdr->data_length, hdr->obj.offset);
 		if (ret != SD_RES_SUCCESS)
 			goto out;
 		req->rp.data_length = hdr->data_length;
+
+		if (entry) {
+			cds_list_del_rcu(&entry->lru_list);
+			cds_list_add_rcu(&entry->lru_list,
+					 &sys_cache.cache_lru_list);
+		}
 	}
 out:
 	return ret;
-- 
1.7.10




More information about the sheepdog mailing list