X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=extent-cache.c;h=38bed8b5db70d8550f19d5b6dafca8b2f8ad457c;hb=e9db166287b57adc5e7a3ced3b906c7d6de08dd6;hp=3dd6434ee3d76ed6d4a4406a4fa2f9ed587e2ac1;hpb=fcdc0929c6ea051dad59818210df53fd03eaf4b1;p=platform%2Fupstream%2Fbtrfs-progs.git

diff --git a/extent-cache.c b/extent-cache.c
index 3dd6434..38bed8b 100644
--- a/extent-cache.c
+++ b/extent-cache.c
@@ -19,131 +19,226 @@
 #include <stdlib.h>
 #include "kerncompat.h"
 #include "extent-cache.h"
+#include "rbtree-utils.h"
 
-void cache_tree_init(struct cache_tree *tree)
+struct cache_extent_search_range {
+	u64 objectid;
+	u64 start;
+	u64 size;
+};
+
+static int cache_tree_comp_range(struct rb_node *node, void *data)
 {
-	tree->root.rb_node = NULL;
+	struct cache_extent *entry;
+	struct cache_extent_search_range *range;
+
+	range = (struct cache_extent_search_range *)data;
+	entry = rb_entry(node, struct cache_extent, rb_node);
+
+	if (entry->start + entry->size <= range->start)
+		return 1;
+	else if (range->start + range->size <= entry->start)
+		return -1;
+	else
+		return 0;
 }
 
-static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
-				   u64 size, struct rb_node *node)
+static int cache_tree_comp_nodes(struct rb_node *node1, struct rb_node *node2)
 {
-	struct rb_node ** p = &root->rb_node;
-	struct rb_node * parent = NULL;
 	struct cache_extent *entry;
+	struct cache_extent_search_range range;
 
-	while(*p) {
-		parent = *p;
-		entry = rb_entry(parent, struct cache_extent, rb_node);
+	entry = rb_entry(node2, struct cache_extent, rb_node);
+	range.start = entry->start;
+	range.size = entry->size;
 
-		if (offset + size <= entry->start)
-			p = &(*p)->rb_left;
-		else if (offset >= entry->start + entry->size)
-			p = &(*p)->rb_right;
-		else
-			return parent;
-	}
+	return cache_tree_comp_range(node1, (void *)&range);
+}
 
-	entry = rb_entry(parent, struct cache_extent, rb_node);
-	rb_link_node(node, parent, p);
-	rb_insert_color(node, root);
-	return NULL;
+static int cache_tree_comp_range2(struct rb_node *node, void *data)
+{
+	struct cache_extent *entry;
+	struct cache_extent_search_range *range;
+
+	range = (struct cache_extent_search_range *)data;
+	entry = rb_entry(node, struct cache_extent, rb_node);
+
+	if (entry->objectid < range->objectid)
+		return 1;
+	else if (entry->objectid > range->objectid)
+		return -1;
+	else if (entry->start + entry->size <= range->start)
+		return 1;
+	else if (range->start + range->size <= entry->start)
+		return -1;
+	else
+		return 0;
 }
 
-static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
-				     u64 size, struct rb_node **prev_ret)
+static int cache_tree_comp_nodes2(struct rb_node *node1, struct rb_node *node2)
 {
-	struct rb_node * n = root->rb_node;
-	struct rb_node *prev = NULL;
 	struct cache_extent *entry;
-	struct cache_extent *prev_entry = NULL;
-
-	while(n) {
-		entry = rb_entry(n, struct cache_extent, rb_node);
-		prev = n;
-		prev_entry = entry;
-
-		if (offset + size <= entry->start)
-			n = n->rb_left;
-		else if (offset >= entry->start + entry->size)
-			n = n->rb_right;
-		else
-			return n;
-	}
-	if (!prev_ret)
-		return NULL;
+	struct cache_extent_search_range range;
 
-	while(prev && offset >= prev_entry->start + prev_entry->size) {
-		prev = rb_next(prev);
-		prev_entry = rb_entry(prev, struct cache_extent, rb_node);
-	}
-	*prev_ret = prev;
-	return NULL;
+	entry = rb_entry(node2, struct cache_extent, rb_node);
+	range.objectid = entry->objectid;
+	range.start = entry->start;
+	range.size = entry->size;
+
+	return cache_tree_comp_range2(node1, (void *)&range);
+}
+
+void cache_tree_init(struct cache_tree *tree)
+{
+	tree->root = RB_ROOT;
 }
 
-struct cache_extent *alloc_cache_extent(u64 start, u64 size)
+static struct cache_extent *
+alloc_cache_extent(u64 objectid, u64 start, u64 size)
 {
 	struct cache_extent *pe = malloc(sizeof(*pe));
 
 	if (!pe)
 		return pe;
+
+	pe->objectid = objectid;
 	pe->start = start;
 	pe->size = size;
 	return pe;
 }
 
-int insert_existing_cache_extent(struct cache_tree *tree,
-				 struct cache_extent *pe)
+static int __add_cache_extent(struct cache_tree *tree,
+			      u64 objectid, u64 start, u64 size)
 {
-	struct rb_node *found;
-
-	found = tree_insert(&tree->root, pe->start, pe->size, &pe->rb_node);
-	if (found)
-		return -EEXIST;
+	struct cache_extent *pe = alloc_cache_extent(objectid, start, size);
+	int ret;
 
-	return 0;
-}
+	if (!pe) {
+		fprintf(stderr, "memory allocation failed\n");
+		exit(1);
+	}
 
-int insert_cache_extent(struct cache_tree *tree, u64 start, u64 size)
-{
-	struct cache_extent *pe = alloc_cache_extent(start, size);
-	int ret;
-	ret = insert_existing_cache_extent(tree, pe);
+	ret = insert_cache_extent(tree, pe);
 	if (ret)
 		free(pe);
+
 	return ret;
 }
 
-struct cache_extent *find_cache_extent(struct cache_tree *tree,
-					   u64 start, u64 size)
+int add_cache_extent(struct cache_tree *tree, u64 start, u64 size)
+{
+	return __add_cache_extent(tree, 0, start, size);
+}
+
+int add_cache_extent2(struct cache_tree *tree,
+		      u64 objectid, u64 start, u64 size)
+{
+	return __add_cache_extent(tree, objectid, start, size);
+}
+
+int insert_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
+{
+	return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes);
+}
+
+int insert_cache_extent2(struct cache_tree *tree, struct cache_extent *pe)
+{
+	return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes2);
+}
+
+struct cache_extent *lookup_cache_extent(struct cache_tree *tree,
+					 u64 start, u64 size)
+{
+	struct rb_node *node;
+	struct cache_extent *entry;
+	struct cache_extent_search_range range;
+
+	range.start = start;
+	range.size = size;
+	node = rb_search(&tree->root, &range, cache_tree_comp_range, NULL);
+	if (!node)
+		return NULL;
+
+	entry = rb_entry(node, struct cache_extent, rb_node);
+	return entry;
+}
+
+struct cache_extent *lookup_cache_extent2(struct cache_tree *tree,
+					 u64 objectid, u64 start, u64 size)
+{
+	struct rb_node *node;
+	struct cache_extent *entry;
+	struct cache_extent_search_range range;
+
+	range.objectid = objectid;
+	range.start = start;
+	range.size = size;
+	node = rb_search(&tree->root, &range, cache_tree_comp_range2, NULL);
+	if (!node)
+		return NULL;
+
+	entry = rb_entry(node, struct cache_extent, rb_node);
+	return entry;
+}
+
+struct cache_extent *search_cache_extent(struct cache_tree *tree, u64 start)
 {
-	struct rb_node *prev;
-	struct rb_node *ret;
+	struct rb_node *next;
+	struct rb_node *node;
 	struct cache_extent *entry;
-	ret = __tree_search(&tree->root, start, size, &prev);
-	if (!ret)
+	struct cache_extent_search_range range;
+
+	range.start = start;
+	range.size = 1;
+	node = rb_search(&tree->root, &range, cache_tree_comp_range, &next);
+	if (!node)
+		node = next;
+	if (!node)
 		return NULL;
 
-	entry = rb_entry(ret, struct cache_extent, rb_node);
+	entry = rb_entry(node, struct cache_extent, rb_node);
 	return entry;
 }
 
-struct cache_extent *find_first_cache_extent(struct cache_tree *tree,
-						 u64 start)
+struct cache_extent *search_cache_extent2(struct cache_tree *tree,
+					 u64 objectid, u64 start)
 {
-	struct rb_node *prev;
-	struct rb_node *ret;
+	struct rb_node *next;
+	struct rb_node *node;
 	struct cache_extent *entry;
+	struct cache_extent_search_range range;
 
-	ret = __tree_search(&tree->root, start, 1, &prev);
-	if (!ret)
-		ret = prev;
-	if (!ret)
+	range.objectid = objectid;
+	range.start = start;
+	range.size = 1;
+	node = rb_search(&tree->root, &range, cache_tree_comp_range2, &next);
+	if (!node)
+		node = next;
+	if (!node)
 		return NULL;
-	entry = rb_entry(ret, struct cache_extent, rb_node);
+
+	entry = rb_entry(node, struct cache_extent, rb_node);
 	return entry;
 }
 
+struct cache_extent *first_cache_extent(struct cache_tree *tree)
+{
+	struct rb_node *node = rb_first(&tree->root);
+
+	if (!node)
+		return NULL;
+	return rb_entry(node, struct cache_extent, rb_node);
+}
+
+struct cache_extent *last_cache_extent(struct cache_tree *tree)
+{
+	struct rb_node *node = rb_last(&tree->root);
+
+	if (!node)
+		return NULL;
+	return rb_entry(node, struct cache_extent, rb_node);
+}
+
 struct cache_extent *prev_cache_extent(struct cache_extent *pe)
 {
 	struct rb_node *node = rb_prev(&pe->rb_node);
@@ -162,9 +257,85 @@ struct cache_extent *next_cache_extent(struct cache_extent *pe)
 	return rb_entry(node, struct cache_extent, rb_node);
 }
 
-void remove_cache_extent(struct cache_tree *tree,
-				 struct cache_extent *pe)
+void remove_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
 {
 	rb_erase(&pe->rb_node, &tree->root);
 }
 
+void cache_tree_free_extents(struct cache_tree *tree,
+			     free_cache_extent free_func)
+{
+	struct cache_extent *ce;
+
+	while ((ce = first_cache_extent(tree))) {
+		remove_cache_extent(tree, ce);
+		free_func(ce);
+	}
+}
+
+static void free_extent_cache(struct cache_extent *pe)
+{
+	free(pe);
+}
+
+void free_extent_cache_tree(struct cache_tree *tree)
+{
+	cache_tree_free_extents(tree, free_extent_cache);
+}
+
+int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size)
+{
+	struct cache_extent *cache;
+	struct cache_extent *next = NULL;
+	struct cache_extent *prev = NULL;
+	int next_merged = 0;
+	int prev_merged = 0;
+	int ret = 0;
+
+	if (cache_tree_empty(tree))
+		goto insert;
+
+	cache = search_cache_extent(tree, start);
+	if (!cache) {
+		/*
+		 * Either the tree is completely empty, or the no range after
+		 * start.
+		 * Either way, the last cache_extent should be prev.
+		 */
+		prev = last_cache_extent(tree);
+	} else if (start <= cache->start) {
+		next = cache;
+		prev = prev_cache_extent(cache);
+	} else {
+		prev = cache;
+		next = next_cache_extent(cache);
+	}
+
+	/*
+	 * Ensure the range to be inserted won't cover with existings
+	 * Or we will need extra loop to do merge
+	 */
+	BUG_ON(next && start + size > next->start);
+	BUG_ON(prev && prev->start + prev->size > start);
+
+	if (next && start + size == next->start) {
+		next_merged = 1;
+		next->size = next->start + next->size - start;
+		next->start = start;
+	}
+	if (prev && prev->start + prev->size == start) {
+		prev_merged = 1;
+		if (next_merged) {
+			next->size = next->start + next->size - prev->start;
+			next->start = prev->start;
+			remove_cache_extent(tree, prev);
+			free(prev);
+		} else {
+			prev->size = start + size - prev->start;
+		}
+	}
+insert:
+	if (!prev_merged && !next_merged)
+		ret = add_cache_extent(tree, start, size);
+	return ret;
+}