extent_map applies a "read more" senario, since we want to build a RCU-skiplist later, we build a new version extent_map based on skiplist firstly.
Signed-off-by: Liu Bo <[email protected]> --- fs/btrfs/extent_map.c | 258 ++++++++++++++++++++++++++++++++----------------- fs/btrfs/extent_map.h | 14 +++- fs/btrfs/volumes.c | 22 ++-- 3 files changed, 190 insertions(+), 104 deletions(-) diff --git a/fs/btrfs/extent_map.c b/fs/btrfs/extent_map.c index 7c97b33..e0a7881 100644 --- a/fs/btrfs/extent_map.c +++ b/fs/btrfs/extent_map.c @@ -9,6 +9,13 @@ static struct kmem_cache *extent_map_cache; +static LIST_HEAD(maps); + +#define MAP_LEAK_DEBUG 1 +#if MAP_LEAK_DEBUG +static DEFINE_SPINLOCK(map_leak_lock); +#endif + int __init extent_map_init(void) { extent_map_cache = kmem_cache_create("extent_map", @@ -21,6 +28,30 @@ int __init extent_map_init(void) void extent_map_exit(void) { + struct extent_map *em; + +#if MAP_LEAK_DEBUG + struct list_head *tmp; + int count = 0; + + list_for_each(tmp, &maps) + count++; + + printk(KERN_INFO "%d em is left to free\n", count); + + while (!list_empty(&maps)) { + cond_resched(); + em = list_entry(maps.next, struct extent_map, leak_list); + printk(KERN_ERR "btrfs extent map: start %llu, len %llu " + "refs %d block_start %llu, block_len %llu, in_tree %u\n", + em->start, em->len, atomic_read(&em->refs), + em->block_start, em->block_len, em->in_tree); + WARN_ON(1); + list_del(&em->leak_list); + kmem_cache_free(extent_map_cache, em); + } +#endif + if (extent_map_cache) kmem_cache_destroy(extent_map_cache); } @@ -34,7 +65,8 @@ void extent_map_exit(void) */ void extent_map_tree_init(struct extent_map_tree *tree) { - tree->map = RB_ROOT; + tree->head.start = (-1ULL); + sl_init_list(&tree->map, &tree->head.sl_node); rwlock_init(&tree->lock); } @@ -48,16 +80,41 @@ void extent_map_tree_init(struct extent_map_tree *tree) struct extent_map *alloc_extent_map(void) { struct extent_map *em; +#if MAP_LEAK_DEBUG + unsigned long flags; +#endif + em = kmem_cache_alloc(extent_map_cache, GFP_NOFS); if (!em) return NULL; em->in_tree = 0; em->flags = 0; em->compress_type = BTRFS_COMPRESS_NONE; + sl_init_node(&em->sl_node); atomic_set(&em->refs, 1); +#if MAP_LEAK_DEBUG + spin_lock_irqsave(&map_leak_lock, flags); + list_add(&em->leak_list, &maps); + spin_unlock_irqrestore(&map_leak_lock, flags); +#endif return em; } +static inline void __free_extent_map(struct extent_map *em) +{ +#if MAP_LEAK_DEBUG + unsigned long flags; + + spin_lock_irqsave(&map_leak_lock, flags); + list_del(&em->leak_list); + spin_unlock_irqrestore(&map_leak_lock, flags); +#endif + + WARN_ON(em->in_tree); + sl_free_node(&em->sl_node); + kmem_cache_free(extent_map_cache, em); +} + /** * free_extent_map - drop reference count of an extent_map * @em: extent map beeing releasead @@ -69,91 +126,113 @@ void free_extent_map(struct extent_map *em) { if (!em) return; + WARN_ON(atomic_read(&em->refs) == 0); - if (atomic_dec_and_test(&em->refs)) { - WARN_ON(em->in_tree); - kmem_cache_free(extent_map_cache, em); - } + if (atomic_dec_and_test(&em->refs)) + __free_extent_map(em); } -static struct rb_node *tree_insert(struct rb_root *root, u64 offset, - struct rb_node *node) +static inline int in_entry(struct sl_node *node, u64 offset) { - struct rb_node **p = &root->rb_node; - struct rb_node *parent = NULL; struct extent_map *entry; - while (*p) { - parent = *p; - entry = rb_entry(parent, struct extent_map, rb_node); + entry = sl_entry(node, struct extent_map, sl_node); + if (!node->head && + entry->start <= offset && extent_map_end(entry) - 1 >= offset) + return 1; + return 0; +} - WARN_ON(!entry->in_tree); +static inline struct extent_map *next_entry(struct sl_node *p, int l, + struct sl_node **q) +{ + struct extent_map *ret; + struct sl_node *next; - if (offset < entry->start) - p = &(*p)->rb_left; - else if (offset >= extent_map_end(entry)) - p = &(*p)->rb_right; - else - return parent; - } + next = __sl_next_with_level(p, l); + ret = sl_entry(next, struct extent_map, sl_node); + BUG_ON(!ret); + *q = next; - entry = rb_entry(node, struct extent_map, rb_node); - entry->in_tree = 1; - rb_link_node(node, parent, p); - rb_insert_color(node, root); - return NULL; + return ret; } -/* - * search through the tree for an extent_map with a given offset. If - * it can't be found, try to find some neighboring extents - */ -static struct rb_node *__tree_search(struct rb_root *root, u64 offset, - struct rb_node **prev_ret, - struct rb_node **next_ret) +static struct sl_node *sl_search(struct sl_list *list, u64 offset, + struct sl_node **next_ret) { - struct rb_node *n = root->rb_node; - struct rb_node *prev = NULL; - struct rb_node *orig_prev = NULL; struct extent_map *entry; - struct extent_map *prev_entry = NULL; + struct sl_node *p, *q; + int level; - while (n) { - entry = rb_entry(n, struct extent_map, rb_node); - prev = n; - prev_entry = entry; + BUG_ON(!list); + level = list->level; + p = list->head; + BUG_ON(!p); - WARN_ON(!entry->in_tree); + if (sl_empty(p)) + return NULL; + do { + while (entry = next_entry(p, level, &q), entry->start <= offset) + p = q; - if (offset < entry->start) - n = n->rb_left; - else if (offset >= extent_map_end(entry)) - n = n->rb_right; - else - return n; - } + if (in_entry(p, offset)) + return p; + if (in_entry(q, offset)) + return q; - if (prev_ret) { - orig_prev = prev; - while (prev && offset >= extent_map_end(prev_entry)) { - prev = rb_next(prev); - prev_entry = rb_entry(prev, struct extent_map, rb_node); - } - *prev_ret = prev; - prev = orig_prev; - } + level--; + } while (level >= 0); - if (next_ret) { - prev_entry = rb_entry(prev, struct extent_map, rb_node); - while (prev && offset < prev_entry->start) { - prev = rb_prev(prev); - prev_entry = rb_entry(prev, struct extent_map, rb_node); - } - *next_ret = prev; + if (next_ret) + *next_ret = sl_next(p); + return NULL; +} + +static struct sl_node * +sl_insert_node(struct sl_list *list, u64 offset, struct sl_node *node) +{ + struct extent_map *entry; + struct sl_node *backlook[MAXLEVEL]; + struct sl_node *p; + struct sl_node *q; + int level; + u64 randseed; + + /* step1: build backlook node, find insert place */ + level = list->level; + p = list->head; + do { + while (entry = next_entry(p, level, &q), entry->start <= offset) + p = q; + + /* -EEXIST */ + if (in_entry(p, offset)) + return p; + if (in_entry(q, offset)) + return q; + + backlook[level] = p; + level--; + } while (level >= 0); + + /* step2: get random level */ + get_random_bytes(&randseed, sizeof(u64)); + level = generate_node_level(randseed); + if (level > list->level) { + list->level++; + level = list->level; + backlook[level] = list->head; } + + /* step3: insert the node */ + entry = sl_entry(node, struct extent_map, sl_node); + entry->in_tree = 1; + sl_fill_node(node, level, GFP_ATOMIC); + sl_link_node(node, backlook, level); return NULL; } + /* check to see if two extent_map structs are adjacent and safe to merge */ static int mergable_maps(struct extent_map *prev, struct extent_map *next) { @@ -186,31 +265,31 @@ static int mergable_maps(struct extent_map *prev, struct extent_map *next) static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) { struct extent_map *merge = NULL; - struct rb_node *rb; + struct sl_node *sl; if (em->start != 0) { - rb = rb_prev(&em->rb_node); - if (rb) - merge = rb_entry(rb, struct extent_map, rb_node); - if (rb && mergable_maps(merge, em)) { + sl = sl_prev(&em->sl_node); + if (sl) + merge = sl_entry(sl, struct extent_map, sl_node); + if (sl && mergable_maps(merge, em)) { em->start = merge->start; em->len += merge->len; em->block_len += merge->block_len; em->block_start = merge->block_start; merge->in_tree = 0; - rb_erase(&merge->rb_node, &tree->map); + sl_erase(&merge->sl_node, &tree->map); free_extent_map(merge); } } - rb = rb_next(&em->rb_node); - if (rb) - merge = rb_entry(rb, struct extent_map, rb_node); - if (rb && mergable_maps(em, merge)) { + sl = sl_next(&em->sl_node); + if (sl) + merge = sl_entry(sl, struct extent_map, sl_node); + if (sl && mergable_maps(em, merge)) { em->len += merge->len; em->block_len += merge->len; - rb_erase(&merge->rb_node, &tree->map); merge->in_tree = 0; + sl_erase(&merge->sl_node, &tree->map); free_extent_map(merge); } } @@ -224,7 +303,6 @@ int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len) em = lookup_extent_mapping(tree, start, len); WARN_ON(!em || em->start != start); - if (!em) goto out; @@ -236,7 +314,6 @@ int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len) out: write_unlock(&tree->lock); return ret; - } /** @@ -253,7 +330,7 @@ int add_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) { int ret = 0; - struct rb_node *rb; + struct sl_node *sl_node; struct extent_map *exist; exist = lookup_extent_mapping(tree, em->start, em->len); @@ -262,11 +339,12 @@ int add_extent_mapping(struct extent_map_tree *tree, ret = -EEXIST; goto out; } - rb = tree_insert(&tree->map, em->start, &em->rb_node); - if (rb) { + sl_node = sl_insert_node(&tree->map, em->start, &em->sl_node); + if (sl_node) { ret = -EEXIST; goto out; } + atomic_inc(&em->refs); try_merge_map(tree, em); @@ -286,22 +364,20 @@ struct extent_map *__lookup_extent_mapping(struct extent_map_tree *tree, u64 start, u64 len, int strict) { struct extent_map *em; - struct rb_node *rb_node; - struct rb_node *prev = NULL; - struct rb_node *next = NULL; + struct sl_node *sl_node; + struct sl_node *next = NULL; u64 end = range_end(start, len); - rb_node = __tree_search(&tree->map, start, &prev, &next); - if (!rb_node) { - if (prev) - rb_node = prev; - else if (next) - rb_node = next; + sl_node = sl_search(&tree->map, start, &next); + if (!sl_node) { + if (next) + sl_node = next; else return NULL; } - em = rb_entry(rb_node, struct extent_map, rb_node); + em = sl_entry(sl_node, struct extent_map, sl_node); + BUG_ON(!em); if (strict && !(end > em->start && start < extent_map_end(em))) return NULL; @@ -357,7 +433,7 @@ int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) int ret = 0; WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); - rb_erase(&em->rb_node, &tree->map); + sl_erase(&em->sl_node, &tree->map); em->in_tree = 0; return ret; } diff --git a/fs/btrfs/extent_map.h b/fs/btrfs/extent_map.h index 33a7890..6d2c247 100644 --- a/fs/btrfs/extent_map.h +++ b/fs/btrfs/extent_map.h @@ -2,6 +2,7 @@ #define __EXTENTMAP__ #include <linux/rbtree.h> +#include "skiplist.h" #define EXTENT_MAP_LAST_BYTE (u64)-4 #define EXTENT_MAP_HOLE (u64)-3 @@ -15,7 +16,7 @@ #define EXTENT_FLAG_PREALLOC 3 /* pre-allocated extent */ struct extent_map { - struct rb_node rb_node; + struct sl_node sl_node; /* all of these are in bytes */ u64 start; @@ -28,11 +29,20 @@ struct extent_map { atomic_t refs; unsigned int in_tree:1; unsigned int compress_type:4; + + struct list_head leak_list; +}; + +struct map_head { + struct sl_node sl_node; + u64 start; + u64 len; }; struct extent_map_tree { - struct rb_root map; + struct sl_list map; rwlock_t lock; + struct map_head head; }; static inline u64 extent_map_end(struct extent_map *em) diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c index f4b839f..adaac9e 100644 --- a/fs/btrfs/volumes.c +++ b/fs/btrfs/volumes.c @@ -2830,20 +2830,20 @@ void btrfs_mapping_init(struct btrfs_mapping_tree *tree) void btrfs_mapping_tree_free(struct btrfs_mapping_tree *tree) { struct extent_map *em; + struct sl_node *head, *node; + + /* At the end of the whole filesystem, so no lock is needed. */ + head = tree->map_tree.map.head; + while (!sl_empty(head)) { + node = head->next[0]; + em = sl_entry(node, struct extent_map, sl_node); + + remove_extent_mapping(&tree->map_tree, em); - while (1) { - write_lock(&tree->map_tree.lock); - em = lookup_extent_mapping(&tree->map_tree, 0, (u64)-1); - if (em) - remove_extent_mapping(&tree->map_tree, em); - write_unlock(&tree->map_tree.lock); - if (!em) - break; kfree(em->bdev); - /* once for us */ - free_extent_map(em); - /* once for the tree */ free_extent_map(em); + + cond_resched(); } } -- 1.6.5.2 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html
