From 4c7a6f74ceeafd738b55d1c57349327f7ea8e895 Mon Sep 17 00:00:00 2001 From: Wang Shilong Date: Wed, 29 Jan 2014 00:25:34 +0800 Subject: Btrfs: rework ulist with list+rb_tree We are really suffering from now ulist's implementation, some developers gave their try, and i just gave some of my ideas for things: 1. use list+rb_tree instead of arrary+rb_tree 2. add cur_list to iterator rather than ulist structure. 3. add seqnum into every node when they are added, this is used to do selfcheck when iterating node. I noticed Zach Brown's comments before, long term is to kick off ulist implementation, however, for now, we need at least avoid arrary from ulist. Cc: Liu Bo Cc: Josef Bacik Cc: Zach Brown Signed-off-by: Wang Shilong Signed-off-by: Josef Bacik Signed-off-by: Chris Mason --- fs/btrfs/ulist.h | 38 +++++++++++--------------------------- 1 file changed, 11 insertions(+), 27 deletions(-) (limited to 'fs/btrfs/ulist.h') diff --git a/fs/btrfs/ulist.h b/fs/btrfs/ulist.h index fb36731074b..2be7102d807 100644 --- a/fs/btrfs/ulist.h +++ b/fs/btrfs/ulist.h @@ -17,18 +17,12 @@ * enumerating it. * It is possible to store an auxiliary value along with the key. * - * The implementation is preliminary and can probably be sped up - * significantly. A first step would be to store the values in an rbtree - * as soon as ULIST_SIZE is exceeded. */ - -/* - * number of elements statically allocated inside struct ulist - */ -#define ULIST_SIZE 16 - struct ulist_iterator { +#ifdef CONFIG_BTRFS_DEBUG int i; +#endif + struct list_head *cur_list; /* hint to start search */ }; /* @@ -37,6 +31,12 @@ struct ulist_iterator { struct ulist_node { u64 val; /* value to store */ u64 aux; /* auxiliary value saved along with the val */ + +#ifdef CONFIG_BTRFS_DEBUG + int seqnum; /* sequence number this node is added */ +#endif + + struct list_head list; /* used to link node */ struct rb_node rb_node; /* used to speed up search */ }; @@ -46,24 +46,8 @@ struct ulist { */ unsigned long nnodes; - /* - * number of nodes we already have room for - */ - unsigned long nodes_alloced; - - /* - * pointer to the array storing the elements. The first ULIST_SIZE - * elements are stored inline. In this case the it points to int_nodes. - * After exceeding ULIST_SIZE, dynamic memory is allocated. - */ - struct ulist_node *nodes; - + struct list_head nodes; struct rb_root root; - - /* - * inline storage space for the first ULIST_SIZE entries - */ - struct ulist_node int_nodes[ULIST_SIZE]; }; void ulist_init(struct ulist *ulist); @@ -77,6 +61,6 @@ int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter); -#define ULIST_ITER_INIT(uiter) ((uiter)->i = 0) +#define ULIST_ITER_INIT(uiter) ((uiter)->cur_list = NULL) #endif -- cgit v1.2.3-70-g09d2 From 49fc647a2c558862145357f3a25892248042f6fe Mon Sep 17 00:00:00 2001 From: Wang Shilong Date: Wed, 29 Jan 2014 00:25:35 +0800 Subject: Btrfs: do not export ulist functions There are not any users that use ulist except Btrfs,don't export them. Signed-off-by: Wang Shilong Reviewed-by: David Sterba Signed-off-by: Josef Bacik Signed-off-by: Chris Mason --- fs/btrfs/ulist.c | 10 +--------- fs/btrfs/ulist.h | 1 - 2 files changed, 1 insertion(+), 10 deletions(-) (limited to 'fs/btrfs/ulist.h') diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c index 8dd0e8dfdaf..840a38b2778 100644 --- a/fs/btrfs/ulist.c +++ b/fs/btrfs/ulist.c @@ -5,7 +5,6 @@ */ #include -#include #include "ulist.h" #include "ctree.h" @@ -51,7 +50,6 @@ void ulist_init(struct ulist *ulist) ulist->root = RB_ROOT; ulist->nnodes = 0; } -EXPORT_SYMBOL(ulist_init); /** * ulist_fini - free up additionally allocated memory for the ulist @@ -60,7 +58,7 @@ EXPORT_SYMBOL(ulist_init); * This is useful in cases where the base 'struct ulist' has been statically * allocated. */ -void ulist_fini(struct ulist *ulist) +static void ulist_fini(struct ulist *ulist) { struct ulist_node *node; struct ulist_node *next; @@ -71,7 +69,6 @@ void ulist_fini(struct ulist *ulist) ulist->root = RB_ROOT; INIT_LIST_HEAD(&ulist->nodes); } -EXPORT_SYMBOL(ulist_fini); /** * ulist_reinit - prepare a ulist for reuse @@ -85,7 +82,6 @@ void ulist_reinit(struct ulist *ulist) ulist_fini(ulist); ulist_init(ulist); } -EXPORT_SYMBOL(ulist_reinit); /** * ulist_alloc - dynamically allocate a ulist @@ -104,7 +100,6 @@ struct ulist *ulist_alloc(gfp_t gfp_mask) return ulist; } -EXPORT_SYMBOL(ulist_alloc); /** * ulist_free - free dynamically allocated ulist @@ -119,7 +114,6 @@ void ulist_free(struct ulist *ulist) ulist_fini(ulist); kfree(ulist); } -EXPORT_SYMBOL(ulist_free); static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val) { @@ -214,7 +208,6 @@ int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, return 1; } -EXPORT_SYMBOL(ulist_add); /** * ulist_next - iterate ulist @@ -256,4 +249,3 @@ struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter) #endif return node; } -EXPORT_SYMBOL(ulist_next); diff --git a/fs/btrfs/ulist.h b/fs/btrfs/ulist.h index 2be7102d807..7f78cbf5cf4 100644 --- a/fs/btrfs/ulist.h +++ b/fs/btrfs/ulist.h @@ -51,7 +51,6 @@ struct ulist { }; void ulist_init(struct ulist *ulist); -void ulist_fini(struct ulist *ulist); void ulist_reinit(struct ulist *ulist); struct ulist *ulist_alloc(gfp_t gfp_mask); void ulist_free(struct ulist *ulist); -- cgit v1.2.3-70-g09d2