Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 1 | #include <linux/err.h> |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 2 | #include <linux/gfp.h> |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 3 | #include <linux/slab.h> |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 4 | #include <linux/module.h> |
| 5 | #include <linux/spinlock.h> |
Jens Axboe | 0a2118d | 2007-10-19 09:23:05 -0400 | [diff] [blame] | 6 | #include <linux/version.h> |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 7 | #include <linux/hardirq.h> |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 8 | #include "extent_map.h" |
| 9 | |
Chris Mason | 86479a0 | 2007-09-10 19:58:16 -0400 | [diff] [blame] | 10 | /* temporary define until extent_map moves out of btrfs */ |
| 11 | struct kmem_cache *btrfs_cache_create(const char *name, size_t size, |
| 12 | unsigned long extra_flags, |
| 13 | void (*ctor)(void *, struct kmem_cache *, |
| 14 | unsigned long)); |
| 15 | |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 16 | static struct kmem_cache *extent_map_cache; |
Chris Mason | ca66462 | 2007-11-27 11:16:35 -0500 | [diff] [blame] | 17 | |
Wyatt Banks | 2f4cbe6 | 2007-11-19 10:22:33 -0500 | [diff] [blame] | 18 | int __init extent_map_init(void) |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 19 | { |
Chris Mason | 86479a0 | 2007-09-10 19:58:16 -0400 | [diff] [blame] | 20 | extent_map_cache = btrfs_cache_create("extent_map", |
Chris Mason | 6d36dcd | 2007-10-15 16:14:37 -0400 | [diff] [blame] | 21 | sizeof(struct extent_map), 0, |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 22 | NULL); |
Wyatt Banks | 2f4cbe6 | 2007-11-19 10:22:33 -0500 | [diff] [blame] | 23 | if (!extent_map_cache) |
| 24 | return -ENOMEM; |
Wyatt Banks | 2f4cbe6 | 2007-11-19 10:22:33 -0500 | [diff] [blame] | 25 | return 0; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 26 | } |
| 27 | |
Christian Hesse | 17636e0 | 2007-12-11 09:25:06 -0500 | [diff] [blame] | 28 | void extent_map_exit(void) |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 29 | { |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 30 | if (extent_map_cache) |
| 31 | kmem_cache_destroy(extent_map_cache); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 32 | } |
| 33 | |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 34 | void extent_map_tree_init(struct extent_map_tree *tree, gfp_t mask) |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 35 | { |
| 36 | tree->map.rb_node = NULL; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 37 | tree->last = NULL; |
| 38 | spin_lock_init(&tree->lock); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 39 | } |
| 40 | EXPORT_SYMBOL(extent_map_tree_init); |
| 41 | |
| 42 | struct extent_map *alloc_extent_map(gfp_t mask) |
| 43 | { |
| 44 | struct extent_map *em; |
| 45 | em = kmem_cache_alloc(extent_map_cache, mask); |
| 46 | if (!em || IS_ERR(em)) |
| 47 | return em; |
| 48 | em->in_tree = 0; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 49 | em->flags = 0; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 50 | atomic_set(&em->refs, 1); |
| 51 | return em; |
| 52 | } |
| 53 | EXPORT_SYMBOL(alloc_extent_map); |
| 54 | |
| 55 | void free_extent_map(struct extent_map *em) |
| 56 | { |
Chris Mason | 2bf5a72 | 2007-08-30 11:54:02 -0400 | [diff] [blame] | 57 | if (!em) |
| 58 | return; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 59 | WARN_ON(atomic_read(&em->refs) == 0); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 60 | if (atomic_dec_and_test(&em->refs)) { |
| 61 | WARN_ON(em->in_tree); |
| 62 | kmem_cache_free(extent_map_cache, em); |
| 63 | } |
| 64 | } |
| 65 | EXPORT_SYMBOL(free_extent_map); |
| 66 | |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 67 | static struct rb_node *tree_insert(struct rb_root *root, u64 offset, |
| 68 | struct rb_node *node) |
| 69 | { |
| 70 | struct rb_node ** p = &root->rb_node; |
| 71 | struct rb_node * parent = NULL; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 72 | struct extent_map *entry; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 73 | |
| 74 | while(*p) { |
| 75 | parent = *p; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 76 | entry = rb_entry(parent, struct extent_map, rb_node); |
| 77 | |
| 78 | WARN_ON(!entry->in_tree); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 79 | |
| 80 | if (offset < entry->start) |
| 81 | p = &(*p)->rb_left; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 82 | else if (offset >= extent_map_end(entry)) |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 83 | p = &(*p)->rb_right; |
| 84 | else |
| 85 | return parent; |
| 86 | } |
| 87 | |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 88 | entry = rb_entry(node, struct extent_map, rb_node); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 89 | entry->in_tree = 1; |
| 90 | rb_link_node(node, parent, p); |
| 91 | rb_insert_color(node, root); |
| 92 | return NULL; |
| 93 | } |
| 94 | |
| 95 | static struct rb_node *__tree_search(struct rb_root *root, u64 offset, |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 96 | struct rb_node **prev_ret, |
| 97 | struct rb_node **next_ret) |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 98 | { |
| 99 | struct rb_node * n = root->rb_node; |
| 100 | struct rb_node *prev = NULL; |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 101 | struct rb_node *orig_prev = NULL; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 102 | struct extent_map *entry; |
| 103 | struct extent_map *prev_entry = NULL; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 104 | |
| 105 | while(n) { |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 106 | entry = rb_entry(n, struct extent_map, rb_node); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 107 | prev = n; |
| 108 | prev_entry = entry; |
| 109 | |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 110 | WARN_ON(!entry->in_tree); |
| 111 | |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 112 | if (offset < entry->start) |
| 113 | n = n->rb_left; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 114 | else if (offset >= extent_map_end(entry)) |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 115 | n = n->rb_right; |
| 116 | else |
| 117 | return n; |
| 118 | } |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 119 | |
| 120 | if (prev_ret) { |
| 121 | orig_prev = prev; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 122 | while(prev && offset >= extent_map_end(prev_entry)) { |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 123 | prev = rb_next(prev); |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 124 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 125 | } |
| 126 | *prev_ret = prev; |
| 127 | prev = orig_prev; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 128 | } |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 129 | |
| 130 | if (next_ret) { |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 131 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 132 | while(prev && offset < prev_entry->start) { |
| 133 | prev = rb_prev(prev); |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 134 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 135 | } |
| 136 | *next_ret = prev; |
| 137 | } |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 138 | return NULL; |
| 139 | } |
| 140 | |
| 141 | static inline struct rb_node *tree_search(struct rb_root *root, u64 offset) |
| 142 | { |
| 143 | struct rb_node *prev; |
| 144 | struct rb_node *ret; |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 145 | ret = __tree_search(root, offset, &prev, NULL); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 146 | if (!ret) |
| 147 | return prev; |
| 148 | return ret; |
| 149 | } |
| 150 | |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 151 | static int mergable_maps(struct extent_map *prev, struct extent_map *next) |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 152 | { |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 153 | if (extent_map_end(prev) == next->start && |
| 154 | prev->flags == next->flags && |
| 155 | prev->bdev == next->bdev && |
| 156 | ((next->block_start == EXTENT_MAP_HOLE && |
| 157 | prev->block_start == EXTENT_MAP_HOLE) || |
| 158 | (next->block_start == EXTENT_MAP_INLINE && |
| 159 | prev->block_start == EXTENT_MAP_INLINE) || |
| 160 | (next->block_start == EXTENT_MAP_DELALLOC && |
| 161 | prev->block_start == EXTENT_MAP_DELALLOC) || |
| 162 | (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && |
| 163 | next->block_start == extent_map_block_end(prev)))) { |
| 164 | return 1; |
| 165 | } |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 166 | return 0; |
| 167 | } |
| 168 | |
| 169 | /* |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 170 | * add_extent_mapping tries a simple forward/backward merge with existing |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 171 | * mappings. The extent_map struct passed in will be inserted into |
| 172 | * the tree directly (no copies made, just a reference taken). |
| 173 | */ |
| 174 | int add_extent_mapping(struct extent_map_tree *tree, |
| 175 | struct extent_map *em) |
| 176 | { |
| 177 | int ret = 0; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 178 | struct extent_map *merge = NULL; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 179 | struct rb_node *rb; |
| 180 | |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 181 | rb = tree_insert(&tree->map, em->start, &em->rb_node); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 182 | if (rb) { |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 183 | merge = rb_entry(rb, struct extent_map, rb_node); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 184 | ret = -EEXIST; |
| 185 | goto out; |
| 186 | } |
| 187 | atomic_inc(&em->refs); |
| 188 | if (em->start != 0) { |
| 189 | rb = rb_prev(&em->rb_node); |
| 190 | if (rb) |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 191 | merge = rb_entry(rb, struct extent_map, rb_node); |
| 192 | if (rb && mergable_maps(merge, em)) { |
| 193 | em->start = merge->start; |
| 194 | em->len += merge->len; |
| 195 | em->block_start = merge->block_start; |
| 196 | merge->in_tree = 0; |
| 197 | rb_erase(&merge->rb_node, &tree->map); |
| 198 | free_extent_map(merge); |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 199 | } |
| 200 | } |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 201 | rb = rb_next(&em->rb_node); |
| 202 | if (rb) |
| 203 | merge = rb_entry(rb, struct extent_map, rb_node); |
| 204 | if (rb && mergable_maps(em, merge)) { |
| 205 | em->len += merge->len; |
| 206 | rb_erase(&merge->rb_node, &tree->map); |
| 207 | merge->in_tree = 0; |
| 208 | free_extent_map(merge); |
| 209 | } |
| 210 | tree->last = em; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 211 | out: |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 212 | return ret; |
| 213 | } |
| 214 | EXPORT_SYMBOL(add_extent_mapping); |
| 215 | |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 216 | static u64 range_end(u64 start, u64 len) |
| 217 | { |
| 218 | if (start + len < start) |
| 219 | return (u64)-1; |
| 220 | return start + len; |
| 221 | } |
| 222 | |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 223 | /* |
| 224 | * lookup_extent_mapping returns the first extent_map struct in the |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 225 | * tree that intersects the [start, len] range. There may |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 226 | * be additional objects in the tree that intersect, so check the object |
| 227 | * returned carefully to make sure you don't need additional lookups. |
| 228 | */ |
| 229 | struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree, |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 230 | u64 start, u64 len) |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 231 | { |
| 232 | struct extent_map *em; |
| 233 | struct rb_node *rb_node; |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 234 | struct rb_node *prev = NULL; struct rb_node *next = NULL; u64 end = range_end(start, len); em = tree->last; if (em && end > em->start && start < extent_map_end(em)) goto found; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 235 | |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 236 | rb_node = __tree_search(&tree->map, start, &prev, &next); |
| 237 | if (!rb_node && prev) { |
| 238 | em = rb_entry(prev, struct extent_map, rb_node); |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 239 | if (end > em->start && start < extent_map_end(em)) |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 240 | goto found; |
| 241 | } |
| 242 | if (!rb_node && next) { |
| 243 | em = rb_entry(next, struct extent_map, rb_node); |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 244 | if (end > em->start && start < extent_map_end(em)) |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 245 | goto found; |
| 246 | } |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 247 | if (!rb_node) { |
| 248 | em = NULL; |
| 249 | goto out; |
| 250 | } |
| 251 | if (IS_ERR(rb_node)) { |
| 252 | em = ERR_PTR(PTR_ERR(rb_node)); |
| 253 | goto out; |
| 254 | } |
| 255 | em = rb_entry(rb_node, struct extent_map, rb_node); |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 256 | if (end > em->start && start < extent_map_end(em)) |
| 257 | goto found; |
| 258 | |
| 259 | em = NULL; |
| 260 | goto out; |
| 261 | |
Chris Mason | 5f56406 | 2008-01-22 16:47:59 -0500 | [diff] [blame] | 262 | found: |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 263 | atomic_inc(&em->refs); |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 264 | tree->last = em; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 265 | out: |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 266 | return em; |
| 267 | } |
| 268 | EXPORT_SYMBOL(lookup_extent_mapping); |
| 269 | |
| 270 | /* |
| 271 | * removes an extent_map struct from the tree. No reference counts are |
| 272 | * dropped, and no checks are done to see if the range is in use |
| 273 | */ |
| 274 | int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) |
| 275 | { |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 276 | int ret = 0; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 277 | |
Chris Mason | d1310b2 | 2008-01-24 16:13:08 -0500 | [diff] [blame] | 278 | rb_erase(&em->rb_node, &tree->map); |
| 279 | em->in_tree = 0; |
| 280 | if (tree->last == em) |
| 281 | tree->last = NULL; |
Chris Mason | a52d9a8 | 2007-08-27 16:49:44 -0400 | [diff] [blame] | 282 | return ret; |
| 283 | } |
| 284 | EXPORT_SYMBOL(remove_extent_mapping); |