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