From f499e40fd97698a1c48d188279647009b21905fe Mon Sep 17 00:00:00 2001 From: Wang Shilong Date: Fri, 10 Jan 2014 21:25:46 +0800 Subject: Btrfs: optimize to remove unnecessary removal with ulist reallocation Here we are not going to free memory, no need to remove every node one by one, just init root node here is ok. Cc: Liu Bo Signed-off-by: Wang Shilong Signed-off-by: Josef Bacik Signed-off-by: Chris Mason --- fs/btrfs/ulist.c | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'fs/btrfs/ulist.c') diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c index b0a523b2c60e..35f5de9dd498 100644 --- a/fs/btrfs/ulist.c +++ b/fs/btrfs/ulist.c @@ -207,9 +207,6 @@ int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, void *old = NULL; int i; - for (i = 0; i < ulist->nnodes; i++) - rb_erase(&ulist->nodes[i].rb_node, &ulist->root); - /* * if nodes_alloced == ULIST_SIZE no memory has been allocated * yet, so pass NULL to krealloc @@ -234,6 +231,7 @@ int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, * pointers, so we have to do it ourselves. Otherwise we may * be bitten by crashes. */ + ulist->root = RB_ROOT; for (i = 0; i < ulist->nnodes; i++) { ret = ulist_rbtree_insert(ulist, &ulist->nodes[i]); if (ret < 0) -- cgit v1.2.3 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.c | 105 +++++++++++++++++++++++-------------------------------- 1 file changed, 44 insertions(+), 61 deletions(-) (limited to 'fs/btrfs/ulist.c') diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c index 35f5de9dd498..8dd0e8dfdaf4 100644 --- a/fs/btrfs/ulist.c +++ b/fs/btrfs/ulist.c @@ -7,6 +7,7 @@ #include #include #include "ulist.h" +#include "ctree.h" /* * ulist is a generic data structure to hold a collection of unique u64 @@ -14,10 +15,6 @@ * 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. - * * A sample usage for ulists is the enumeration of directed graphs without * visiting a node twice. The pseudo-code could look like this: * @@ -50,10 +47,9 @@ */ void ulist_init(struct ulist *ulist) { - ulist->nnodes = 0; - ulist->nodes = ulist->int_nodes; - ulist->nodes_alloced = ULIST_SIZE; + INIT_LIST_HEAD(&ulist->nodes); ulist->root = RB_ROOT; + ulist->nnodes = 0; } EXPORT_SYMBOL(ulist_init); @@ -66,14 +62,14 @@ EXPORT_SYMBOL(ulist_init); */ void ulist_fini(struct ulist *ulist) { - /* - * The first ULIST_SIZE elements are stored inline in struct ulist. - * Only if more elements are alocated they need to be freed. - */ - if (ulist->nodes_alloced > ULIST_SIZE) - kfree(ulist->nodes); - ulist->nodes_alloced = 0; /* in case ulist_fini is called twice */ + struct ulist_node *node; + struct ulist_node *next; + + list_for_each_entry_safe(node, next, &ulist->nodes, list) { + kfree(node); + } ulist->root = RB_ROOT; + INIT_LIST_HEAD(&ulist->nodes); } EXPORT_SYMBOL(ulist_fini); @@ -192,57 +188,29 @@ int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask) int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, u64 *old_aux, gfp_t gfp_mask) { - int ret = 0; - struct ulist_node *node = NULL; + int ret; + struct ulist_node *node; + node = ulist_rbtree_search(ulist, val); if (node) { if (old_aux) *old_aux = node->aux; return 0; } + node = kmalloc(sizeof(*node), gfp_mask); + if (!node) + return -ENOMEM; - if (ulist->nnodes >= ulist->nodes_alloced) { - u64 new_alloced = ulist->nodes_alloced + 128; - struct ulist_node *new_nodes; - void *old = NULL; - int i; - - /* - * if nodes_alloced == ULIST_SIZE no memory has been allocated - * yet, so pass NULL to krealloc - */ - if (ulist->nodes_alloced > ULIST_SIZE) - old = ulist->nodes; + node->val = val; + node->aux = aux; +#ifdef CONFIG_BTRFS_DEBUG + node->seqnum = ulist->nnodes; +#endif - new_nodes = krealloc(old, sizeof(*new_nodes) * new_alloced, - gfp_mask); - if (!new_nodes) - return -ENOMEM; - - if (!old) - memcpy(new_nodes, ulist->int_nodes, - sizeof(ulist->int_nodes)); - - ulist->nodes = new_nodes; - ulist->nodes_alloced = new_alloced; - - /* - * krealloc actually uses memcpy, which does not copy rb_node - * pointers, so we have to do it ourselves. Otherwise we may - * be bitten by crashes. - */ - ulist->root = RB_ROOT; - for (i = 0; i < ulist->nnodes; i++) { - ret = ulist_rbtree_insert(ulist, &ulist->nodes[i]); - if (ret < 0) - return ret; - } - } - ulist->nodes[ulist->nnodes].val = val; - ulist->nodes[ulist->nnodes].aux = aux; - ret = ulist_rbtree_insert(ulist, &ulist->nodes[ulist->nnodes]); - BUG_ON(ret); - ++ulist->nnodes; + ret = ulist_rbtree_insert(ulist, node); + ASSERT(!ret); + list_add_tail(&node->list, &ulist->nodes); + ulist->nnodes++; return 1; } @@ -266,11 +234,26 @@ EXPORT_SYMBOL(ulist_add); */ struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter) { - if (ulist->nnodes == 0) + struct ulist_node *node; + + if (list_empty(&ulist->nodes)) return NULL; - if (uiter->i < 0 || uiter->i >= ulist->nnodes) + if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes) return NULL; - - return &ulist->nodes[uiter->i++]; + if (uiter->cur_list) { + uiter->cur_list = uiter->cur_list->next; + } else { + uiter->cur_list = ulist->nodes.next; +#ifdef CONFIG_BTRFS_DEBUG + uiter->i = 0; +#endif + } + node = list_entry(uiter->cur_list, struct ulist_node, list); +#ifdef CONFIG_BTRFS_DEBUG + ASSERT(node->seqnum == uiter->i); + ASSERT(uiter->i >= 0 && uiter->i < ulist->nnodes); + uiter->i++; +#endif + return node; } EXPORT_SYMBOL(ulist_next); -- cgit v1.2.3 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 +--------- 1 file changed, 1 insertion(+), 9 deletions(-) (limited to 'fs/btrfs/ulist.c') diff --git a/fs/btrfs/ulist.c b/fs/btrfs/ulist.c index 8dd0e8dfdaf4..840a38b2778a 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); -- cgit v1.2.3