1#include <linux/err.h>
2#include <linux/gfp.h>
3#include <linux/slab.h>
4#include <linux/module.h>
5#include <linux/spinlock.h>
6#include <linux/hardirq.h>
7#include "extent_map.h"
8
9
10static struct kmem_cache *extent_map_cache;
11
12int __init extent_map_init(void)
13{
14 extent_map_cache = kmem_cache_create("extent_map",
15 sizeof(struct extent_map), 0,
16 SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
17 if (!extent_map_cache)
18 return -ENOMEM;
19 return 0;
20}
21
22void extent_map_exit(void)
23{
24 if (extent_map_cache)
25 kmem_cache_destroy(extent_map_cache);
26}
27
28
29
30
31
32
33
34
35
36void extent_map_tree_init(struct extent_map_tree *tree, gfp_t mask)
37{
38 tree->map.rb_node = NULL;
39 rwlock_init(&tree->lock);
40}
41
42
43
44
45
46
47
48
49
50struct extent_map *alloc_extent_map(gfp_t mask)
51{
52 struct extent_map *em;
53 em = kmem_cache_alloc(extent_map_cache, mask);
54 if (!em || IS_ERR(em))
55 return em;
56 em->in_tree = 0;
57 em->flags = 0;
58 atomic_set(&em->refs, 1);
59 return em;
60}
61
62
63
64
65
66
67
68
69void free_extent_map(struct extent_map *em)
70{
71 if (!em)
72 return;
73 WARN_ON(atomic_read(&em->refs) == 0);
74 if (atomic_dec_and_test(&em->refs)) {
75 WARN_ON(em->in_tree);
76 kmem_cache_free(extent_map_cache, em);
77 }
78}
79
80static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
81 struct rb_node *node)
82{
83 struct rb_node **p = &root->rb_node;
84 struct rb_node *parent = NULL;
85 struct extent_map *entry;
86
87 while (*p) {
88 parent = *p;
89 entry = rb_entry(parent, struct extent_map, rb_node);
90
91 WARN_ON(!entry->in_tree);
92
93 if (offset < entry->start)
94 p = &(*p)->rb_left;
95 else if (offset >= extent_map_end(entry))
96 p = &(*p)->rb_right;
97 else
98 return parent;
99 }
100
101 entry = rb_entry(node, struct extent_map, rb_node);
102 entry->in_tree = 1;
103 rb_link_node(node, parent, p);
104 rb_insert_color(node, root);
105 return NULL;
106}
107
108
109
110
111
112static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
113 struct rb_node **prev_ret,
114 struct rb_node **next_ret)
115{
116 struct rb_node *n = root->rb_node;
117 struct rb_node *prev = NULL;
118 struct rb_node *orig_prev = NULL;
119 struct extent_map *entry;
120 struct extent_map *prev_entry = NULL;
121
122 while (n) {
123 entry = rb_entry(n, struct extent_map, rb_node);
124 prev = n;
125 prev_entry = entry;
126
127 WARN_ON(!entry->in_tree);
128
129 if (offset < entry->start)
130 n = n->rb_left;
131 else if (offset >= extent_map_end(entry))
132 n = n->rb_right;
133 else
134 return n;
135 }
136
137 if (prev_ret) {
138 orig_prev = prev;
139 while (prev && offset >= extent_map_end(prev_entry)) {
140 prev = rb_next(prev);
141 prev_entry = rb_entry(prev, struct extent_map, rb_node);
142 }
143 *prev_ret = prev;
144 prev = orig_prev;
145 }
146
147 if (next_ret) {
148 prev_entry = rb_entry(prev, struct extent_map, rb_node);
149 while (prev && offset < prev_entry->start) {
150 prev = rb_prev(prev);
151 prev_entry = rb_entry(prev, struct extent_map, rb_node);
152 }
153 *next_ret = prev;
154 }
155 return NULL;
156}
157
158
159
160
161
162static inline struct rb_node *tree_search(struct rb_root *root, u64 offset)
163{
164 struct rb_node *prev;
165 struct rb_node *ret;
166 ret = __tree_search(root, offset, &prev, NULL);
167 if (!ret)
168 return prev;
169 return ret;
170}
171
172
173static int mergable_maps(struct extent_map *prev, struct extent_map *next)
174{
175 if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
176 return 0;
177
178
179
180
181
182 if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags))
183 return 0;
184
185 if (extent_map_end(prev) == next->start &&
186 prev->flags == next->flags &&
187 prev->bdev == next->bdev &&
188 ((next->block_start == EXTENT_MAP_HOLE &&
189 prev->block_start == EXTENT_MAP_HOLE) ||
190 (next->block_start == EXTENT_MAP_INLINE &&
191 prev->block_start == EXTENT_MAP_INLINE) ||
192 (next->block_start == EXTENT_MAP_DELALLOC &&
193 prev->block_start == EXTENT_MAP_DELALLOC) ||
194 (next->block_start < EXTENT_MAP_LAST_BYTE - 1 &&
195 next->block_start == extent_map_block_end(prev)))) {
196 return 1;
197 }
198 return 0;
199}
200
201int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len)
202{
203 int ret = 0;
204 struct extent_map *merge = NULL;
205 struct rb_node *rb;
206 struct extent_map *em;
207
208 write_lock(&tree->lock);
209 em = lookup_extent_mapping(tree, start, len);
210
211 WARN_ON(!em || em->start != start);
212
213 if (!em)
214 goto out;
215
216 clear_bit(EXTENT_FLAG_PINNED, &em->flags);
217
218 if (em->start != 0) {
219 rb = rb_prev(&em->rb_node);
220 if (rb)
221 merge = rb_entry(rb, struct extent_map, rb_node);
222 if (rb && mergable_maps(merge, em)) {
223 em->start = merge->start;
224 em->len += merge->len;
225 em->block_len += merge->block_len;
226 em->block_start = merge->block_start;
227 merge->in_tree = 0;
228 rb_erase(&merge->rb_node, &tree->map);
229 free_extent_map(merge);
230 }
231 }
232
233 rb = rb_next(&em->rb_node);
234 if (rb)
235 merge = rb_entry(rb, struct extent_map, rb_node);
236 if (rb && mergable_maps(em, merge)) {
237 em->len += merge->len;
238 em->block_len += merge->len;
239 rb_erase(&merge->rb_node, &tree->map);
240 merge->in_tree = 0;
241 free_extent_map(merge);
242 }
243
244 free_extent_map(em);
245out:
246 write_unlock(&tree->lock);
247 return ret;
248
249}
250
251
252
253
254
255
256
257
258
259
260
261int add_extent_mapping(struct extent_map_tree *tree,
262 struct extent_map *em)
263{
264 int ret = 0;
265 struct extent_map *merge = NULL;
266 struct rb_node *rb;
267 struct extent_map *exist;
268
269 exist = lookup_extent_mapping(tree, em->start, em->len);
270 if (exist) {
271 free_extent_map(exist);
272 ret = -EEXIST;
273 goto out;
274 }
275 rb = tree_insert(&tree->map, em->start, &em->rb_node);
276 if (rb) {
277 ret = -EEXIST;
278 goto out;
279 }
280 atomic_inc(&em->refs);
281 if (em->start != 0) {
282 rb = rb_prev(&em->rb_node);
283 if (rb)
284 merge = rb_entry(rb, struct extent_map, rb_node);
285 if (rb && mergable_maps(merge, em)) {
286 em->start = merge->start;
287 em->len += merge->len;
288 em->block_len += merge->block_len;
289 em->block_start = merge->block_start;
290 merge->in_tree = 0;
291 rb_erase(&merge->rb_node, &tree->map);
292 free_extent_map(merge);
293 }
294 }
295 rb = rb_next(&em->rb_node);
296 if (rb)
297 merge = rb_entry(rb, struct extent_map, rb_node);
298 if (rb && mergable_maps(em, merge)) {
299 em->len += merge->len;
300 em->block_len += merge->len;
301 rb_erase(&merge->rb_node, &tree->map);
302 merge->in_tree = 0;
303 free_extent_map(merge);
304 }
305out:
306 return ret;
307}
308
309
310static u64 range_end(u64 start, u64 len)
311{
312 if (start + len < start)
313 return (u64)-1;
314 return start + len;
315}
316
317
318
319
320
321
322
323
324
325
326
327
328struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
329 u64 start, u64 len)
330{
331 struct extent_map *em;
332 struct rb_node *rb_node;
333 struct rb_node *prev = NULL;
334 struct rb_node *next = NULL;
335 u64 end = range_end(start, len);
336
337 rb_node = __tree_search(&tree->map, start, &prev, &next);
338 if (!rb_node && prev) {
339 em = rb_entry(prev, struct extent_map, rb_node);
340 if (end > em->start && start < extent_map_end(em))
341 goto found;
342 }
343 if (!rb_node && next) {
344 em = rb_entry(next, struct extent_map, rb_node);
345 if (end > em->start && start < extent_map_end(em))
346 goto found;
347 }
348 if (!rb_node) {
349 em = NULL;
350 goto out;
351 }
352 if (IS_ERR(rb_node)) {
353 em = ERR_PTR(PTR_ERR(rb_node));
354 goto out;
355 }
356 em = rb_entry(rb_node, struct extent_map, rb_node);
357 if (end > em->start && start < extent_map_end(em))
358 goto found;
359
360 em = NULL;
361 goto out;
362
363found:
364 atomic_inc(&em->refs);
365out:
366 return em;
367}
368
369
370
371
372
373
374
375
376
377
378
379
380struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
381 u64 start, u64 len)
382{
383 struct extent_map *em;
384 struct rb_node *rb_node;
385 struct rb_node *prev = NULL;
386 struct rb_node *next = NULL;
387
388 rb_node = __tree_search(&tree->map, start, &prev, &next);
389 if (!rb_node && prev) {
390 em = rb_entry(prev, struct extent_map, rb_node);
391 goto found;
392 }
393 if (!rb_node && next) {
394 em = rb_entry(next, struct extent_map, rb_node);
395 goto found;
396 }
397 if (!rb_node) {
398 em = NULL;
399 goto out;
400 }
401 if (IS_ERR(rb_node)) {
402 em = ERR_PTR(PTR_ERR(rb_node));
403 goto out;
404 }
405 em = rb_entry(rb_node, struct extent_map, rb_node);
406 goto found;
407
408 em = NULL;
409 goto out;
410
411found:
412 atomic_inc(&em->refs);
413out:
414 return em;
415}
416
417
418
419
420
421
422
423
424
425int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
426{
427 int ret = 0;
428
429 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
430 rb_erase(&em->rb_node, &tree->map);
431 em->in_tree = 0;
432 return ret;
433}
434