Commit | Line | Data |
---|---|---|
d1310b2e | 1 | #include <linux/err.h> |
a52d9a80 | 2 | #include <linux/gfp.h> |
d1310b2e | 3 | #include <linux/slab.h> |
a52d9a80 CM |
4 | #include <linux/module.h> |
5 | #include <linux/spinlock.h> | |
d1310b2e | 6 | #include <linux/hardirq.h> |
a52d9a80 CM |
7 | #include "extent_map.h" |
8 | ||
86479a04 CM |
9 | /* temporary define until extent_map moves out of btrfs */ |
10 | struct kmem_cache *btrfs_cache_create(const char *name, size_t size, | |
11 | unsigned long extra_flags, | |
12 | void (*ctor)(void *, struct kmem_cache *, | |
13 | unsigned long)); | |
14 | ||
a52d9a80 | 15 | static struct kmem_cache *extent_map_cache; |
ca664626 | 16 | |
2f4cbe64 | 17 | int __init extent_map_init(void) |
a52d9a80 | 18 | { |
86479a04 | 19 | extent_map_cache = btrfs_cache_create("extent_map", |
6d36dcd4 | 20 | sizeof(struct extent_map), 0, |
a52d9a80 | 21 | NULL); |
2f4cbe64 WB |
22 | if (!extent_map_cache) |
23 | return -ENOMEM; | |
2f4cbe64 | 24 | return 0; |
a52d9a80 CM |
25 | } |
26 | ||
17636e03 | 27 | void extent_map_exit(void) |
a52d9a80 | 28 | { |
a52d9a80 CM |
29 | if (extent_map_cache) |
30 | kmem_cache_destroy(extent_map_cache); | |
a52d9a80 CM |
31 | } |
32 | ||
9d2423c5 CH |
33 | /** |
34 | * extent_map_tree_init - initialize extent map tree | |
35 | * @tree: tree to initialize | |
36 | * @mask: flags for memory allocations during tree operations | |
37 | * | |
38 | * Initialize the extent tree @tree. Should be called for each new inode | |
39 | * or other user of the extent_map interface. | |
40 | */ | |
d1310b2e | 41 | void extent_map_tree_init(struct extent_map_tree *tree, gfp_t mask) |
a52d9a80 CM |
42 | { |
43 | tree->map.rb_node = NULL; | |
d1310b2e | 44 | spin_lock_init(&tree->lock); |
a52d9a80 CM |
45 | } |
46 | EXPORT_SYMBOL(extent_map_tree_init); | |
47 | ||
9d2423c5 CH |
48 | /** |
49 | * alloc_extent_map - allocate new extent map structure | |
50 | * @mask: memory allocation flags | |
51 | * | |
52 | * Allocate a new extent_map structure. The new structure is | |
53 | * returned with a reference count of one and needs to be | |
54 | * freed using free_extent_map() | |
55 | */ | |
a52d9a80 CM |
56 | struct extent_map *alloc_extent_map(gfp_t mask) |
57 | { | |
58 | struct extent_map *em; | |
59 | em = kmem_cache_alloc(extent_map_cache, mask); | |
60 | if (!em || IS_ERR(em)) | |
61 | return em; | |
62 | em->in_tree = 0; | |
d1310b2e | 63 | em->flags = 0; |
a52d9a80 CM |
64 | atomic_set(&em->refs, 1); |
65 | return em; | |
66 | } | |
67 | EXPORT_SYMBOL(alloc_extent_map); | |
68 | ||
9d2423c5 CH |
69 | /** |
70 | * free_extent_map - drop reference count of an extent_map | |
71 | * @em: extent map beeing releasead | |
72 | * | |
73 | * Drops the reference out on @em by one and free the structure | |
74 | * if the reference count hits zero. | |
75 | */ | |
a52d9a80 CM |
76 | void free_extent_map(struct extent_map *em) |
77 | { | |
2bf5a725 CM |
78 | if (!em) |
79 | return; | |
d1310b2e | 80 | WARN_ON(atomic_read(&em->refs) == 0); |
a52d9a80 CM |
81 | if (atomic_dec_and_test(&em->refs)) { |
82 | WARN_ON(em->in_tree); | |
83 | kmem_cache_free(extent_map_cache, em); | |
84 | } | |
85 | } | |
86 | EXPORT_SYMBOL(free_extent_map); | |
87 | ||
a52d9a80 CM |
88 | static struct rb_node *tree_insert(struct rb_root *root, u64 offset, |
89 | struct rb_node *node) | |
90 | { | |
d397712b CM |
91 | struct rb_node **p = &root->rb_node; |
92 | struct rb_node *parent = NULL; | |
d1310b2e | 93 | struct extent_map *entry; |
a52d9a80 | 94 | |
d397712b | 95 | while (*p) { |
a52d9a80 | 96 | parent = *p; |
d1310b2e CM |
97 | entry = rb_entry(parent, struct extent_map, rb_node); |
98 | ||
99 | WARN_ON(!entry->in_tree); | |
a52d9a80 CM |
100 | |
101 | if (offset < entry->start) | |
102 | p = &(*p)->rb_left; | |
d1310b2e | 103 | else if (offset >= extent_map_end(entry)) |
a52d9a80 CM |
104 | p = &(*p)->rb_right; |
105 | else | |
106 | return parent; | |
107 | } | |
108 | ||
d1310b2e | 109 | entry = rb_entry(node, struct extent_map, rb_node); |
a52d9a80 CM |
110 | entry->in_tree = 1; |
111 | rb_link_node(node, parent, p); | |
112 | rb_insert_color(node, root); | |
113 | return NULL; | |
114 | } | |
115 | ||
d352ac68 CM |
116 | /* |
117 | * search through the tree for an extent_map with a given offset. If | |
118 | * it can't be found, try to find some neighboring extents | |
119 | */ | |
a52d9a80 | 120 | static struct rb_node *__tree_search(struct rb_root *root, u64 offset, |
5f56406a CM |
121 | struct rb_node **prev_ret, |
122 | struct rb_node **next_ret) | |
a52d9a80 | 123 | { |
d397712b | 124 | struct rb_node *n = root->rb_node; |
a52d9a80 | 125 | struct rb_node *prev = NULL; |
5f56406a | 126 | struct rb_node *orig_prev = NULL; |
d1310b2e CM |
127 | struct extent_map *entry; |
128 | struct extent_map *prev_entry = NULL; | |
a52d9a80 | 129 | |
d397712b | 130 | while (n) { |
d1310b2e | 131 | entry = rb_entry(n, struct extent_map, rb_node); |
a52d9a80 CM |
132 | prev = n; |
133 | prev_entry = entry; | |
134 | ||
d1310b2e CM |
135 | WARN_ON(!entry->in_tree); |
136 | ||
a52d9a80 CM |
137 | if (offset < entry->start) |
138 | n = n->rb_left; | |
d1310b2e | 139 | else if (offset >= extent_map_end(entry)) |
a52d9a80 CM |
140 | n = n->rb_right; |
141 | else | |
142 | return n; | |
143 | } | |
5f56406a CM |
144 | |
145 | if (prev_ret) { | |
146 | orig_prev = prev; | |
d397712b | 147 | while (prev && offset >= extent_map_end(prev_entry)) { |
5f56406a | 148 | prev = rb_next(prev); |
d1310b2e | 149 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406a CM |
150 | } |
151 | *prev_ret = prev; | |
152 | prev = orig_prev; | |
153 | } | |
154 | ||
155 | if (next_ret) { | |
d1310b2e | 156 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
d397712b | 157 | while (prev && offset < prev_entry->start) { |
5f56406a | 158 | prev = rb_prev(prev); |
d1310b2e | 159 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406a CM |
160 | } |
161 | *next_ret = prev; | |
a52d9a80 | 162 | } |
a52d9a80 CM |
163 | return NULL; |
164 | } | |
165 | ||
d352ac68 CM |
166 | /* |
167 | * look for an offset in the tree, and if it can't be found, return | |
168 | * the first offset we can find smaller than 'offset'. | |
169 | */ | |
a52d9a80 CM |
170 | static inline struct rb_node *tree_search(struct rb_root *root, u64 offset) |
171 | { | |
172 | struct rb_node *prev; | |
173 | struct rb_node *ret; | |
5f56406a | 174 | ret = __tree_search(root, offset, &prev, NULL); |
a52d9a80 CM |
175 | if (!ret) |
176 | return prev; | |
177 | return ret; | |
178 | } | |
179 | ||
d352ac68 | 180 | /* check to see if two extent_map structs are adjacent and safe to merge */ |
d1310b2e | 181 | static int mergable_maps(struct extent_map *prev, struct extent_map *next) |
a52d9a80 | 182 | { |
7f3c74fb CM |
183 | if (test_bit(EXTENT_FLAG_PINNED, &prev->flags)) |
184 | return 0; | |
185 | ||
c8b97818 CM |
186 | /* |
187 | * don't merge compressed extents, we need to know their | |
188 | * actual size | |
189 | */ | |
190 | if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags)) | |
191 | return 0; | |
192 | ||
d1310b2e CM |
193 | if (extent_map_end(prev) == next->start && |
194 | prev->flags == next->flags && | |
195 | prev->bdev == next->bdev && | |
196 | ((next->block_start == EXTENT_MAP_HOLE && | |
197 | prev->block_start == EXTENT_MAP_HOLE) || | |
198 | (next->block_start == EXTENT_MAP_INLINE && | |
199 | prev->block_start == EXTENT_MAP_INLINE) || | |
200 | (next->block_start == EXTENT_MAP_DELALLOC && | |
201 | prev->block_start == EXTENT_MAP_DELALLOC) || | |
202 | (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && | |
203 | next->block_start == extent_map_block_end(prev)))) { | |
204 | return 1; | |
205 | } | |
a52d9a80 CM |
206 | return 0; |
207 | } | |
208 | ||
9d2423c5 CH |
209 | /** |
210 | * add_extent_mapping - add new extent map to the extent tree | |
211 | * @tree: tree to insert new map in | |
212 | * @em: map to insert | |
213 | * | |
214 | * Insert @em into @tree or perform a simple forward/backward merge with | |
215 | * existing mappings. The extent_map struct passed in will be inserted | |
216 | * into the tree directly, with an additional reference taken, or a | |
217 | * reference dropped if the merge attempt was sucessfull. | |
a52d9a80 CM |
218 | */ |
219 | int add_extent_mapping(struct extent_map_tree *tree, | |
220 | struct extent_map *em) | |
221 | { | |
222 | int ret = 0; | |
d1310b2e | 223 | struct extent_map *merge = NULL; |
a52d9a80 | 224 | struct rb_node *rb; |
7c2fe32a | 225 | struct extent_map *exist; |
a52d9a80 | 226 | |
7c2fe32a CM |
227 | exist = lookup_extent_mapping(tree, em->start, em->len); |
228 | if (exist) { | |
229 | free_extent_map(exist); | |
230 | ret = -EEXIST; | |
231 | goto out; | |
232 | } | |
64f26f74 | 233 | assert_spin_locked(&tree->lock); |
d1310b2e | 234 | rb = tree_insert(&tree->map, em->start, &em->rb_node); |
a52d9a80 | 235 | if (rb) { |
a52d9a80 | 236 | ret = -EEXIST; |
e6dcd2dc | 237 | free_extent_map(merge); |
a52d9a80 CM |
238 | goto out; |
239 | } | |
240 | atomic_inc(&em->refs); | |
241 | if (em->start != 0) { | |
242 | rb = rb_prev(&em->rb_node); | |
243 | if (rb) | |
d1310b2e CM |
244 | merge = rb_entry(rb, struct extent_map, rb_node); |
245 | if (rb && mergable_maps(merge, em)) { | |
246 | em->start = merge->start; | |
247 | em->len += merge->len; | |
c8b97818 | 248 | em->block_len += merge->block_len; |
d1310b2e CM |
249 | em->block_start = merge->block_start; |
250 | merge->in_tree = 0; | |
251 | rb_erase(&merge->rb_node, &tree->map); | |
252 | free_extent_map(merge); | |
a52d9a80 CM |
253 | } |
254 | } | |
d1310b2e CM |
255 | rb = rb_next(&em->rb_node); |
256 | if (rb) | |
257 | merge = rb_entry(rb, struct extent_map, rb_node); | |
258 | if (rb && mergable_maps(em, merge)) { | |
259 | em->len += merge->len; | |
c8b97818 | 260 | em->block_len += merge->len; |
d1310b2e CM |
261 | rb_erase(&merge->rb_node, &tree->map); |
262 | merge->in_tree = 0; | |
263 | free_extent_map(merge); | |
264 | } | |
a52d9a80 | 265 | out: |
a52d9a80 CM |
266 | return ret; |
267 | } | |
268 | EXPORT_SYMBOL(add_extent_mapping); | |
269 | ||
d352ac68 | 270 | /* simple helper to do math around the end of an extent, handling wrap */ |
d1310b2e CM |
271 | static u64 range_end(u64 start, u64 len) |
272 | { | |
273 | if (start + len < start) | |
274 | return (u64)-1; | |
275 | return start + len; | |
276 | } | |
277 | ||
9d2423c5 CH |
278 | /** |
279 | * lookup_extent_mapping - lookup extent_map | |
280 | * @tree: tree to lookup in | |
281 | * @start: byte offset to start the search | |
282 | * @len: length of the lookup range | |
283 | * | |
284 | * Find and return the first extent_map struct in @tree that intersects the | |
285 | * [start, len] range. There may be additional objects in the tree that | |
286 | * intersect, so check the object returned carefully to make sure that no | |
287 | * additional lookups are needed. | |
a52d9a80 CM |
288 | */ |
289 | struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree, | |
d1310b2e | 290 | u64 start, u64 len) |
a52d9a80 CM |
291 | { |
292 | struct extent_map *em; | |
293 | struct rb_node *rb_node; | |
306929f3 CH |
294 | struct rb_node *prev = NULL; |
295 | struct rb_node *next = NULL; | |
296 | u64 end = range_end(start, len); | |
297 | ||
64f26f74 | 298 | assert_spin_locked(&tree->lock); |
5f56406a CM |
299 | rb_node = __tree_search(&tree->map, start, &prev, &next); |
300 | if (!rb_node && prev) { | |
301 | em = rb_entry(prev, struct extent_map, rb_node); | |
d1310b2e | 302 | if (end > em->start && start < extent_map_end(em)) |
5f56406a CM |
303 | goto found; |
304 | } | |
305 | if (!rb_node && next) { | |
306 | em = rb_entry(next, struct extent_map, rb_node); | |
d1310b2e | 307 | if (end > em->start && start < extent_map_end(em)) |
5f56406a CM |
308 | goto found; |
309 | } | |
a52d9a80 CM |
310 | if (!rb_node) { |
311 | em = NULL; | |
312 | goto out; | |
313 | } | |
314 | if (IS_ERR(rb_node)) { | |
315 | em = ERR_PTR(PTR_ERR(rb_node)); | |
316 | goto out; | |
317 | } | |
318 | em = rb_entry(rb_node, struct extent_map, rb_node); | |
d1310b2e CM |
319 | if (end > em->start && start < extent_map_end(em)) |
320 | goto found; | |
321 | ||
322 | em = NULL; | |
323 | goto out; | |
324 | ||
5f56406a | 325 | found: |
a52d9a80 CM |
326 | atomic_inc(&em->refs); |
327 | out: | |
a52d9a80 CM |
328 | return em; |
329 | } | |
330 | EXPORT_SYMBOL(lookup_extent_mapping); | |
331 | ||
9d2423c5 CH |
332 | /** |
333 | * remove_extent_mapping - removes an extent_map from the extent tree | |
334 | * @tree: extent tree to remove from | |
335 | * @em: extent map beeing removed | |
336 | * | |
337 | * Removes @em from @tree. No reference counts are dropped, and no checks | |
338 | * are done to see if the range is in use | |
a52d9a80 CM |
339 | */ |
340 | int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) | |
341 | { | |
d1310b2e | 342 | int ret = 0; |
a52d9a80 | 343 | |
7f3c74fb | 344 | WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); |
64f26f74 | 345 | assert_spin_locked(&tree->lock); |
d1310b2e CM |
346 | rb_erase(&em->rb_node, &tree->map); |
347 | em->in_tree = 0; | |
a52d9a80 CM |
348 | return ret; |
349 | } | |
350 | EXPORT_SYMBOL(remove_extent_mapping); |