[Sheepdog] [PATCH v4] object cache: incorrect lock may lead to update lost

[Yunkai Zhang]

Currently, we use a dirty_rb tree to record which cache object
have been updated.

Two kinds of threads will operate this dirty tree concurrently:
 a. mulitple io-workers: write something to cache objects
 b. one flush-worker: flush all updates to cluster

In the following scenario, update will be lost:

flush-worker                                  one io-worker
[object_cache_push]                         [object_cache_rw]
 |-(1) get a cache object from dirty tree                 |
 |-(2) read the data file of this object                  |
 |                    modify data file of this object (3)-|
 |-(4) forward_write_obj_req()                            |
 |                      add this object to dirty tree (5)-|
 |-(6) rb_erase: remove this object from dirty tree       |

Note: io-worker generate *new update* in step (3), but flush-worker
remove this cache object from dirty tree in step (6).

I use two dirty trees to fix this bug and avoid heavy lock between
flush-worker and io-wroker threads.

There is only one *active* dirty tree for io-workers in any time.
After io-worker modify something, it operate this active dirty tree.

When flush-worker want to flush all updates to cluster, it:
 1. mark another tree as *active* dirty tree.
 2. get update info from *inactive* dirty tree.
 3. if something wrong occur in flushing process,
    merge two dirty trees into active drity tree.

Signed-off-by: Yunkai Zhang <qiushu.zyk at taobao.com>
---
 sheep/object_cache.c |  110 ++++++++++++++++++++++++++++++++++++++++----------
 sheep/sheep_priv.h   |    9 +++-
 2 files changed, 95 insertions(+), 24 deletions(-)

diff --git a/sheep/object_cache.c b/sheep/object_cache.c
index df9ab49..d75f532 100644
--- a/sheep/object_cache.c
+++ b/sheep/object_cache.c
@@ -127,9 +127,16 @@ not_found:
 		cache = xzalloc(sizeof(*cache));
 		cache->vid = vid;
 		create_dir_for(vid);
-		cache->dirty_rb = RB_ROOT;
+
+		cache->dirty_trees[0] = RB_ROOT;
+		cache->dirty_trees[1] = RB_ROOT;
+		cache->active_dirty_tree = &cache->dirty_trees[0];
+
+		INIT_LIST_HEAD(&cache->dirty_lists[0]);
+		INIT_LIST_HEAD(&cache->dirty_lists[1]);
+		cache->active_dirty_list = &cache->dirty_lists[0];
+
 		pthread_mutex_init(&cache->lock, NULL);
-		INIT_LIST_HEAD(&cache->dirty_list);
 		hlist_add_head(&cache->hash, head);
 	} else
 		cache = NULL;
@@ -138,18 +145,61 @@ out:
 	return cache;
 }
 
-static void add_to_dirty_tree_and_list(struct object_cache *oc, uint32_t idx, int create)
+static void add_to_dirty_tree_and_list(struct object_cache *oc, uint32_t idx,
+		struct object_cache_entry *entry, int create)
+{
+	if (!entry) {
+		entry = xzalloc(sizeof(*entry));
+		entry->idx = idx;
+		entry->create = create;
+	}
+	if (!dirty_tree_insert(oc->active_dirty_tree, entry))
+		list_add(&entry->list, oc->active_dirty_list);
+	else
+		free(entry);
+}
+
+static inline void del_from_dirty_tree_and_list(
+		struct object_cache_entry *entry,
+		struct rb_root *dirty_tree)
 {
-	struct object_cache_entry *entry = xzalloc(sizeof(*entry));
+	rb_erase(&entry->rb, dirty_tree);
+	list_del(&entry->list);
+}
 
-	entry->idx = idx;
+static void switch_dirty_tree_and_list(struct object_cache *oc,
+		struct rb_root ** inactive_dirty_tree,
+		struct list_head **inactive_dirty_list)
+{
 	pthread_mutex_lock(&oc->lock);
-	if (!dirty_tree_insert(&oc->dirty_rb, entry)) {
-		if (create)
-			entry->create = 1;
-		list_add(&entry->list, &oc->dirty_list);
-	} else
-		free(entry);
+
+	*inactive_dirty_list = oc->active_dirty_list;
+	*inactive_dirty_tree = oc->active_dirty_tree;
+
+	if (oc->active_dirty_tree == &oc->dirty_trees[0]) {
+		oc->active_dirty_list = &oc->dirty_lists[1];
+		oc->active_dirty_tree = &oc->dirty_trees[1];
+	} else {
+		oc->active_dirty_list = &oc->dirty_lists[0];
+		oc->active_dirty_tree = &oc->dirty_trees[0];
+	}
+
+	pthread_mutex_unlock(&oc->lock);
+}
+
+static void merge_dirty_tree_and_list(struct object_cache *oc,
+		struct rb_root *inactive_dirty_tree,
+		struct list_head *inactive_dirty_list)
+{
+	struct object_cache_entry *entry, *t;
+
+	pthread_mutex_lock(&oc->lock);
+
+	list_for_each_entry_safe(entry, t, inactive_dirty_list, list) {
+		del_from_dirty_tree_and_list(entry, inactive_dirty_tree);
+		add_to_dirty_tree_and_list(oc, entry->idx, entry, 0);
+	}
+
 	pthread_mutex_unlock(&oc->lock);
 }
 
@@ -181,8 +231,11 @@ int object_cache_lookup(struct object_cache *oc, uint32_t idx, int create)
 		ret = prealloc(fd, data_length);
 		if (ret != SD_RES_SUCCESS)
 			ret = -1;
-		else
-			add_to_dirty_tree_and_list(oc, idx, 1);
+		else {
+			pthread_mutex_lock(&oc->lock);
+			add_to_dirty_tree_and_list(oc, idx, NULL, 1);
+			pthread_mutex_unlock(&oc->lock);
+		}
 	}
 	close(fd);
 out:
@@ -268,7 +321,9 @@ int object_cache_rw(struct object_cache *oc, uint32_t idx, struct request *req)
 		ret = write_cache_object(oc->vid, idx, req->data, hdr->data_length, hdr->offset);
 		if (ret != SD_RES_SUCCESS)
 			goto out;
-		add_to_dirty_tree_and_list(oc, idx, 0);
+		pthread_mutex_lock(&oc->lock);
+		add_to_dirty_tree_and_list(oc, idx, NULL, 0);
+		pthread_mutex_unlock(&oc->lock);
 	} else {
 		ret = read_cache_object(oc->vid, idx, req->data, hdr->data_length, hdr->offset);
 		if (ret != SD_RES_SUCCESS)
@@ -464,23 +519,34 @@ out:
 int object_cache_push(struct object_cache *oc)
 {
 	struct object_cache_entry *entry, *t;
+	struct rb_root *inactive_dirty_tree;
+	struct list_head *inactive_dirty_list;
 	int ret = SD_RES_SUCCESS;
 
 	if (node_in_recovery())
 		/* We don't do flushing in recovery */
 		return SD_RES_SUCCESS;
 
-	list_for_each_entry_safe(entry, t, &oc->dirty_list, list) {
+	switch_dirty_tree_and_list(oc,
+			&inactive_dirty_tree,
+			&inactive_dirty_list);
+
+	/* 1. for async flush, there is only one worker
+	 * 2. for sync flush, Guest assure us of that only one sync
+	 * request is issued in one of gateway worker threads
+	 * So we need not to protect inactive dirty tree and list */
+	list_for_each_entry_safe(entry, t, inactive_dirty_list, list) {
 		ret = push_cache_object(oc->vid, entry->idx, entry->create);
 		if (ret != SD_RES_SUCCESS)
-			goto out;
-		pthread_mutex_lock(&oc->lock);
-		rb_erase(&entry->rb, &oc->dirty_rb);
-		list_del(&entry->list);
-		pthread_mutex_unlock(&oc->lock);
+			goto push_failed;
+		del_from_dirty_tree_and_list(entry, inactive_dirty_tree);
 		free(entry);
 	}
-out:
+	return ret;
+push_failed:
+	merge_dirty_tree_and_list(oc,
+			inactive_dirty_tree,
+			inactive_dirty_list);
 	return ret;
 }
 
@@ -518,7 +584,7 @@ void object_cache_delete(uint32_t vid)
 		hlist_del(&cache->hash);
 		pthread_mutex_unlock(&hashtable_lock[h]);
 
-		list_for_each_entry_safe(entry, t, &cache->dirty_list, list) {
+		list_for_each_entry_safe(entry, t, cache->active_dirty_list, list) {
 			free(entry);
 		}
 		free(cache);
diff --git a/sheep/sheep_priv.h b/sheep/sheep_priv.h
index a9e8440..8e982cf 100644
--- a/sheep/sheep_priv.h
+++ b/sheep/sheep_priv.h
@@ -410,9 +410,14 @@ static inline int sys_can_halt(void)
 
 struct object_cache {
 	uint32_t vid;
-	struct list_head dirty_list;
 	struct hlist_node hash;
-	struct rb_root dirty_rb;
+
+	struct list_head dirty_lists[2];
+	struct list_head *active_dirty_list;
+
+	struct rb_root dirty_trees[2];
+	struct rb_root *active_dirty_tree;
+
 	pthread_mutex_t lock;
 };
 
-- 
1.7.7.6