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