Blame view
fs/btrfs/extent_map.c
11.6 KB
d1310b2e0
|
1 |
#include <linux/err.h> |
d1310b2e0
|
2 |
#include <linux/slab.h> |
a52d9a803
|
3 |
#include <linux/spinlock.h> |
d1310b2e0
|
4 |
#include <linux/hardirq.h> |
261507a02
|
5 |
#include "ctree.h" |
a52d9a803
|
6 |
#include "extent_map.h" |
86479a04e
|
7 |
|
a52d9a803
|
8 |
static struct kmem_cache *extent_map_cache; |
ca6646264
|
9 |
|
2f4cbe644
|
10 |
int __init extent_map_init(void) |
a52d9a803
|
11 |
{ |
837e19728
|
12 |
extent_map_cache = kmem_cache_create("btrfs_extent_map", |
9601e3f63
|
13 14 |
sizeof(struct extent_map), 0, SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL); |
2f4cbe644
|
15 16 |
if (!extent_map_cache) return -ENOMEM; |
2f4cbe644
|
17 |
return 0; |
a52d9a803
|
18 |
} |
17636e03f
|
19 |
void extent_map_exit(void) |
a52d9a803
|
20 |
{ |
a52d9a803
|
21 22 |
if (extent_map_cache) kmem_cache_destroy(extent_map_cache); |
a52d9a803
|
23 |
} |
9d2423c5c
|
24 25 26 |
/** * extent_map_tree_init - initialize extent map tree * @tree: tree to initialize |
9d2423c5c
|
27 28 29 30 |
* * Initialize the extent tree @tree. Should be called for each new inode * or other user of the extent_map interface. */ |
a8067e022
|
31 |
void extent_map_tree_init(struct extent_map_tree *tree) |
a52d9a803
|
32 |
{ |
6bef4d317
|
33 |
tree->map = RB_ROOT; |
5dc562c54
|
34 |
INIT_LIST_HEAD(&tree->modified_extents); |
890871be8
|
35 |
rwlock_init(&tree->lock); |
a52d9a803
|
36 |
} |
a52d9a803
|
37 |
|
9d2423c5c
|
38 39 |
/** * alloc_extent_map - allocate new extent map structure |
9d2423c5c
|
40 41 42 43 44 |
* * Allocate a new extent_map structure. The new structure is * returned with a reference count of one and needs to be * freed using free_extent_map() */ |
172ddd60a
|
45 |
struct extent_map *alloc_extent_map(void) |
a52d9a803
|
46 47 |
{ struct extent_map *em; |
70c8a91ce
|
48 |
em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS); |
c26a92037
|
49 50 |
if (!em) return NULL; |
cbc0e9287
|
51 |
RB_CLEAR_NODE(&em->rb_node); |
d1310b2e0
|
52 |
em->flags = 0; |
261507a02
|
53 |
em->compress_type = BTRFS_COMPRESS_NONE; |
5dc562c54
|
54 |
em->generation = 0; |
a52d9a803
|
55 |
atomic_set(&em->refs, 1); |
5dc562c54
|
56 |
INIT_LIST_HEAD(&em->list); |
a52d9a803
|
57 58 |
return em; } |
a52d9a803
|
59 |
|
9d2423c5c
|
60 61 62 63 64 65 66 |
/** * free_extent_map - drop reference count of an extent_map * @em: extent map beeing releasead * * Drops the reference out on @em by one and free the structure * if the reference count hits zero. */ |
a52d9a803
|
67 68 |
void free_extent_map(struct extent_map *em) { |
2bf5a725a
|
69 70 |
if (!em) return; |
d1310b2e0
|
71 |
WARN_ON(atomic_read(&em->refs) == 0); |
a52d9a803
|
72 |
if (atomic_dec_and_test(&em->refs)) { |
cbc0e9287
|
73 |
WARN_ON(extent_map_in_tree(em)); |
5dc562c54
|
74 |
WARN_ON(!list_empty(&em->list)); |
298a8f9cf
|
75 |
if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) |
95617d693
|
76 |
kfree(em->map_lookup); |
a52d9a803
|
77 78 79 |
kmem_cache_free(extent_map_cache, em); } } |
a52d9a803
|
80 |
|
32193c147
|
81 82 83 84 85 86 87 88 89 |
/* simple helper to do math around the end of an extent, handling wrap */ static u64 range_end(u64 start, u64 len) { if (start + len < start) return (u64)-1; return start + len; } static int tree_insert(struct rb_root *root, struct extent_map *em) |
a52d9a803
|
90 |
{ |
d397712bc
|
91 92 |
struct rb_node **p = &root->rb_node; struct rb_node *parent = NULL; |
32193c147
|
93 94 95 |
struct extent_map *entry = NULL; struct rb_node *orig_parent = NULL; u64 end = range_end(em->start, em->len); |
a52d9a803
|
96 |
|
d397712bc
|
97 |
while (*p) { |
a52d9a803
|
98 |
parent = *p; |
d1310b2e0
|
99 |
entry = rb_entry(parent, struct extent_map, rb_node); |
32193c147
|
100 |
if (em->start < entry->start) |
a52d9a803
|
101 |
p = &(*p)->rb_left; |
32193c147
|
102 |
else if (em->start >= extent_map_end(entry)) |
a52d9a803
|
103 104 |
p = &(*p)->rb_right; else |
32193c147
|
105 |
return -EEXIST; |
a52d9a803
|
106 |
} |
32193c147
|
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
orig_parent = parent; while (parent && em->start >= extent_map_end(entry)) { parent = rb_next(parent); entry = rb_entry(parent, struct extent_map, rb_node); } if (parent) if (end > entry->start && em->start < extent_map_end(entry)) return -EEXIST; parent = orig_parent; entry = rb_entry(parent, struct extent_map, rb_node); while (parent && em->start < entry->start) { parent = rb_prev(parent); entry = rb_entry(parent, struct extent_map, rb_node); } if (parent) if (end > entry->start && em->start < extent_map_end(entry)) return -EEXIST; |
32193c147
|
125 126 127 |
rb_link_node(&em->rb_node, orig_parent, p); rb_insert_color(&em->rb_node, root); return 0; |
a52d9a803
|
128 |
} |
d352ac681
|
129 130 131 132 |
/* * search through the tree for an extent_map with a given offset. If * it can't be found, try to find some neighboring extents */ |
a52d9a803
|
133 |
static struct rb_node *__tree_search(struct rb_root *root, u64 offset, |
5f56406aa
|
134 135 |
struct rb_node **prev_ret, struct rb_node **next_ret) |
a52d9a803
|
136 |
{ |
d397712bc
|
137 |
struct rb_node *n = root->rb_node; |
a52d9a803
|
138 |
struct rb_node *prev = NULL; |
5f56406aa
|
139 |
struct rb_node *orig_prev = NULL; |
d1310b2e0
|
140 141 |
struct extent_map *entry; struct extent_map *prev_entry = NULL; |
a52d9a803
|
142 |
|
d397712bc
|
143 |
while (n) { |
d1310b2e0
|
144 |
entry = rb_entry(n, struct extent_map, rb_node); |
a52d9a803
|
145 146 147 148 149 |
prev = n; prev_entry = entry; if (offset < entry->start) n = n->rb_left; |
d1310b2e0
|
150 |
else if (offset >= extent_map_end(entry)) |
a52d9a803
|
151 152 153 154 |
n = n->rb_right; else return n; } |
5f56406aa
|
155 156 157 |
if (prev_ret) { orig_prev = prev; |
d397712bc
|
158 |
while (prev && offset >= extent_map_end(prev_entry)) { |
5f56406aa
|
159 |
prev = rb_next(prev); |
d1310b2e0
|
160 |
prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406aa
|
161 162 163 164 165 166 |
} *prev_ret = prev; prev = orig_prev; } if (next_ret) { |
d1310b2e0
|
167 |
prev_entry = rb_entry(prev, struct extent_map, rb_node); |
d397712bc
|
168 |
while (prev && offset < prev_entry->start) { |
5f56406aa
|
169 |
prev = rb_prev(prev); |
d1310b2e0
|
170 |
prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406aa
|
171 172 |
} *next_ret = prev; |
a52d9a803
|
173 |
} |
a52d9a803
|
174 175 |
return NULL; } |
d352ac681
|
176 |
/* check to see if two extent_map structs are adjacent and safe to merge */ |
d1310b2e0
|
177 |
static int mergable_maps(struct extent_map *prev, struct extent_map *next) |
a52d9a803
|
178 |
{ |
7f3c74fb8
|
179 180 |
if (test_bit(EXTENT_FLAG_PINNED, &prev->flags)) return 0; |
c8b978188
|
181 182 183 184 185 186 |
/* * don't merge compressed extents, we need to know their * actual size */ if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags)) return 0; |
201a90389
|
187 188 189 |
if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) || test_bit(EXTENT_FLAG_LOGGING, &next->flags)) return 0; |
09a2a8f96
|
190 191 192 193 194 195 196 |
/* * We don't want to merge stuff that hasn't been written to the log yet * since it may not reflect exactly what is on disk, and that would be * bad. */ if (!list_empty(&prev->list) || !list_empty(&next->list)) return 0; |
d1310b2e0
|
197 198 199 200 201 202 203 204 205 206 207 208 209 |
if (extent_map_end(prev) == next->start && prev->flags == next->flags && prev->bdev == next->bdev && ((next->block_start == EXTENT_MAP_HOLE && prev->block_start == EXTENT_MAP_HOLE) || (next->block_start == EXTENT_MAP_INLINE && prev->block_start == EXTENT_MAP_INLINE) || (next->block_start == EXTENT_MAP_DELALLOC && prev->block_start == EXTENT_MAP_DELALLOC) || (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && next->block_start == extent_map_block_end(prev)))) { return 1; } |
a52d9a803
|
210 211 |
return 0; } |
4d2c8f62f
|
212 |
static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) |
a1ed835e1
|
213 |
{ |
a1ed835e1
|
214 215 |
struct extent_map *merge = NULL; struct rb_node *rb; |
a1ed835e1
|
216 217 218 219 220 221 222 |
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)) { em->start = merge->start; |
70c8a91ce
|
223 |
em->orig_start = merge->orig_start; |
a1ed835e1
|
224 225 226 |
em->len += merge->len; em->block_len += merge->block_len; em->block_start = merge->block_start; |
70c8a91ce
|
227 228 229 |
em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start; em->mod_start = merge->mod_start; em->generation = max(em->generation, merge->generation); |
5dc562c54
|
230 |
|
a1ed835e1
|
231 |
rb_erase(&merge->rb_node, &tree->map); |
cbc0e9287
|
232 |
RB_CLEAR_NODE(&merge->rb_node); |
a1ed835e1
|
233 234 235 236 237 238 239 240 241 |
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)) { em->len += merge->len; |
d527afe1e
|
242 |
em->block_len += merge->block_len; |
a1ed835e1
|
243 |
rb_erase(&merge->rb_node, &tree->map); |
cbc0e9287
|
244 |
RB_CLEAR_NODE(&merge->rb_node); |
70c8a91ce
|
245 246 |
em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start; em->generation = max(em->generation, merge->generation); |
a1ed835e1
|
247 248 |
free_extent_map(merge); } |
4d2c8f62f
|
249 |
} |
5dc562c54
|
250 |
/** |
52b1de91e
|
251 |
* unpin_extent_cache - unpin an extent from the cache |
5dc562c54
|
252 253 254 255 |
* @tree: tree to unpin the extent in * @start: logical offset in the file * @len: length of the extent * @gen: generation that this extent has been modified in |
5dc562c54
|
256 257 258 259 260 261 262 |
* * Called after an extent has been written to disk properly. Set the generation * to the generation that actually added the file item to the inode so we know * we need to sync this extent when we call fsync(). */ int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, u64 gen) |
4d2c8f62f
|
263 264 265 |
{ int ret = 0; struct extent_map *em; |
4e2f84e63
|
266 |
bool prealloc = false; |
4d2c8f62f
|
267 268 269 270 271 272 273 274 |
write_lock(&tree->lock); em = lookup_extent_mapping(tree, start, len); WARN_ON(!em || em->start != start); if (!em) goto out; |
5dc562c54
|
275 |
em->generation = gen; |
4d2c8f62f
|
276 |
clear_bit(EXTENT_FLAG_PINNED, &em->flags); |
4e2f84e63
|
277 278 |
em->mod_start = em->start; em->mod_len = em->len; |
b11e234d2
|
279 |
if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) { |
4e2f84e63
|
280 |
prealloc = true; |
b11e234d2
|
281 |
clear_bit(EXTENT_FLAG_FILLING, &em->flags); |
4e2f84e63
|
282 |
} |
4d2c8f62f
|
283 284 |
try_merge_map(tree, em); |
4e2f84e63
|
285 286 287 288 289 |
if (prealloc) { em->mod_start = em->start; em->mod_len = em->len; } |
a1ed835e1
|
290 291 292 293 294 295 |
free_extent_map(em); out: write_unlock(&tree->lock); return ret; } |
201a90389
|
296 297 298 |
void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em) { clear_bit(EXTENT_FLAG_LOGGING, &em->flags); |
cbc0e9287
|
299 |
if (extent_map_in_tree(em)) |
222c81dc3
|
300 |
try_merge_map(tree, em); |
201a90389
|
301 |
} |
176840b3a
|
302 303 304 305 306 307 308 309 310 311 312 313 314 |
static inline void setup_extent_mapping(struct extent_map_tree *tree, struct extent_map *em, int modified) { atomic_inc(&em->refs); em->mod_start = em->start; em->mod_len = em->len; if (modified) list_move(&em->list, &tree->modified_extents); else try_merge_map(tree, em); } |
9d2423c5c
|
315 316 317 318 319 320 321 322 |
/** * add_extent_mapping - add new extent map to the extent tree * @tree: tree to insert new map in * @em: map to insert * * Insert @em into @tree or perform a simple forward/backward merge with * existing mappings. The extent_map struct passed in will be inserted * into the tree directly, with an additional reference taken, or a |
25985edce
|
323 |
* reference dropped if the merge attempt was successful. |
a52d9a803
|
324 325 |
*/ int add_extent_mapping(struct extent_map_tree *tree, |
09a2a8f96
|
326 |
struct extent_map *em, int modified) |
a52d9a803
|
327 328 |
{ int ret = 0; |
a52d9a803
|
329 |
|
32193c147
|
330 331 |
ret = tree_insert(&tree->map, em); if (ret) |
a52d9a803
|
332 |
goto out; |
32193c147
|
333 |
|
176840b3a
|
334 |
setup_extent_mapping(tree, em, modified); |
a52d9a803
|
335 |
out: |
a52d9a803
|
336 337 |
return ret; } |
a52d9a803
|
338 |
|
48a3b6366
|
339 340 341 |
static struct extent_map * __lookup_extent_mapping(struct extent_map_tree *tree, u64 start, u64 len, int strict) |
a52d9a803
|
342 343 344 |
{ struct extent_map *em; struct rb_node *rb_node; |
306929f36
|
345 346 347 |
struct rb_node *prev = NULL; struct rb_node *next = NULL; u64 end = range_end(start, len); |
5f56406aa
|
348 |
rb_node = __tree_search(&tree->map, start, &prev, &next); |
a52d9a803
|
349 |
if (!rb_node) { |
ed64f0665
|
350 351 352 353 354 355 |
if (prev) rb_node = prev; else if (next) rb_node = next; else return NULL; |
a52d9a803
|
356 |
} |
ed64f0665
|
357 |
|
a52d9a803
|
358 |
em = rb_entry(rb_node, struct extent_map, rb_node); |
d1310b2e0
|
359 |
|
ed64f0665
|
360 361 |
if (strict && !(end > em->start && start < extent_map_end(em))) return NULL; |
d1310b2e0
|
362 |
|
a52d9a803
|
363 |
atomic_inc(&em->refs); |
a52d9a803
|
364 365 |
return em; } |
a52d9a803
|
366 |
|
9d2423c5c
|
367 |
/** |
ed64f0665
|
368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 |
* lookup_extent_mapping - lookup extent_map * @tree: tree to lookup in * @start: byte offset to start the search * @len: length of the lookup range * * Find and return the first extent_map struct in @tree that intersects the * [start, len] range. There may be additional objects in the tree that * intersect, so check the object returned carefully to make sure that no * additional lookups are needed. */ struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree, u64 start, u64 len) { return __lookup_extent_mapping(tree, start, len, 1); } /** |
b917b7c3b
|
385 386 387 388 389 390 391 392 393 394 395 396 397 |
* search_extent_mapping - find a nearby extent map * @tree: tree to lookup in * @start: byte offset to start the search * @len: length of the lookup range * * Find and return the first extent_map struct in @tree that intersects the * [start, len] range. * * If one can't be found, any nearby extent may be returned */ struct extent_map *search_extent_mapping(struct extent_map_tree *tree, u64 start, u64 len) { |
ed64f0665
|
398 |
return __lookup_extent_mapping(tree, start, len, 0); |
b917b7c3b
|
399 400 401 |
} /** |
9d2423c5c
|
402 403 404 405 406 407 |
* remove_extent_mapping - removes an extent_map from the extent tree * @tree: extent tree to remove from * @em: extent map beeing removed * * Removes @em from @tree. No reference counts are dropped, and no checks * are done to see if the range is in use |
a52d9a803
|
408 409 410 |
*/ int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) { |
d1310b2e0
|
411 |
int ret = 0; |
a52d9a803
|
412 |
|
7f3c74fb8
|
413 |
WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); |
d1310b2e0
|
414 |
rb_erase(&em->rb_node, &tree->map); |
ff44c6e36
|
415 416 |
if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags)) list_del_init(&em->list); |
cbc0e9287
|
417 |
RB_CLEAR_NODE(&em->rb_node); |
a52d9a803
|
418 419 |
return ret; } |
176840b3a
|
420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 |
void replace_extent_mapping(struct extent_map_tree *tree, struct extent_map *cur, struct extent_map *new, int modified) { WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags)); ASSERT(extent_map_in_tree(cur)); if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags)) list_del_init(&cur->list); rb_replace_node(&cur->rb_node, &new->rb_node, &tree->map); RB_CLEAR_NODE(&cur->rb_node); setup_extent_mapping(tree, new, modified); } |