]>
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> | |
0a2118df | 6 | #include <linux/version.h> |
d1310b2e | 7 | #include <linux/hardirq.h> |
a52d9a80 CM |
8 | #include "extent_map.h" |
9 | ||
86479a04 CM |
10 | /* temporary define until extent_map moves out of btrfs */ |
11 | struct kmem_cache *btrfs_cache_create(const char *name, size_t size, | |
12 | unsigned long extra_flags, | |
13 | void (*ctor)(void *, struct kmem_cache *, | |
14 | unsigned long)); | |
15 | ||
a52d9a80 | 16 | static struct kmem_cache *extent_map_cache; |
ca664626 | 17 | |
2f4cbe64 | 18 | int __init extent_map_init(void) |
a52d9a80 | 19 | { |
86479a04 | 20 | extent_map_cache = btrfs_cache_create("extent_map", |
6d36dcd4 | 21 | sizeof(struct extent_map), 0, |
a52d9a80 | 22 | NULL); |
2f4cbe64 WB |
23 | if (!extent_map_cache) |
24 | return -ENOMEM; | |
2f4cbe64 | 25 | return 0; |
a52d9a80 CM |
26 | } |
27 | ||
17636e03 | 28 | void extent_map_exit(void) |
a52d9a80 | 29 | { |
a52d9a80 CM |
30 | if (extent_map_cache) |
31 | kmem_cache_destroy(extent_map_cache); | |
a52d9a80 CM |
32 | } |
33 | ||
d1310b2e | 34 | void extent_map_tree_init(struct extent_map_tree *tree, gfp_t mask) |
a52d9a80 CM |
35 | { |
36 | tree->map.rb_node = NULL; | |
d1310b2e CM |
37 | tree->last = NULL; |
38 | spin_lock_init(&tree->lock); | |
a52d9a80 CM |
39 | } |
40 | EXPORT_SYMBOL(extent_map_tree_init); | |
41 | ||
42 | struct extent_map *alloc_extent_map(gfp_t mask) | |
43 | { | |
44 | struct extent_map *em; | |
45 | em = kmem_cache_alloc(extent_map_cache, mask); | |
46 | if (!em || IS_ERR(em)) | |
47 | return em; | |
48 | em->in_tree = 0; | |
d1310b2e | 49 | em->flags = 0; |
a52d9a80 CM |
50 | atomic_set(&em->refs, 1); |
51 | return em; | |
52 | } | |
53 | EXPORT_SYMBOL(alloc_extent_map); | |
54 | ||
55 | void free_extent_map(struct extent_map *em) | |
56 | { | |
2bf5a725 CM |
57 | if (!em) |
58 | return; | |
d1310b2e | 59 | WARN_ON(atomic_read(&em->refs) == 0); |
a52d9a80 CM |
60 | if (atomic_dec_and_test(&em->refs)) { |
61 | WARN_ON(em->in_tree); | |
62 | kmem_cache_free(extent_map_cache, em); | |
63 | } | |
64 | } | |
65 | EXPORT_SYMBOL(free_extent_map); | |
66 | ||
a52d9a80 CM |
67 | static struct rb_node *tree_insert(struct rb_root *root, u64 offset, |
68 | struct rb_node *node) | |
69 | { | |
70 | struct rb_node ** p = &root->rb_node; | |
71 | struct rb_node * parent = NULL; | |
d1310b2e | 72 | struct extent_map *entry; |
a52d9a80 CM |
73 | |
74 | while(*p) { | |
75 | parent = *p; | |
d1310b2e CM |
76 | entry = rb_entry(parent, struct extent_map, rb_node); |
77 | ||
78 | WARN_ON(!entry->in_tree); | |
a52d9a80 CM |
79 | |
80 | if (offset < entry->start) | |
81 | p = &(*p)->rb_left; | |
d1310b2e | 82 | else if (offset >= extent_map_end(entry)) |
a52d9a80 CM |
83 | p = &(*p)->rb_right; |
84 | else | |
85 | return parent; | |
86 | } | |
87 | ||
d1310b2e | 88 | entry = rb_entry(node, struct extent_map, rb_node); |
a52d9a80 CM |
89 | entry->in_tree = 1; |
90 | rb_link_node(node, parent, p); | |
91 | rb_insert_color(node, root); | |
92 | return NULL; | |
93 | } | |
94 | ||
95 | static struct rb_node *__tree_search(struct rb_root *root, u64 offset, | |
5f56406a CM |
96 | struct rb_node **prev_ret, |
97 | struct rb_node **next_ret) | |
a52d9a80 CM |
98 | { |
99 | struct rb_node * n = root->rb_node; | |
100 | struct rb_node *prev = NULL; | |
5f56406a | 101 | struct rb_node *orig_prev = NULL; |
d1310b2e CM |
102 | struct extent_map *entry; |
103 | struct extent_map *prev_entry = NULL; | |
a52d9a80 CM |
104 | |
105 | while(n) { | |
d1310b2e | 106 | entry = rb_entry(n, struct extent_map, rb_node); |
a52d9a80 CM |
107 | prev = n; |
108 | prev_entry = entry; | |
109 | ||
d1310b2e CM |
110 | WARN_ON(!entry->in_tree); |
111 | ||
a52d9a80 CM |
112 | if (offset < entry->start) |
113 | n = n->rb_left; | |
d1310b2e | 114 | else if (offset >= extent_map_end(entry)) |
a52d9a80 CM |
115 | n = n->rb_right; |
116 | else | |
117 | return n; | |
118 | } | |
5f56406a CM |
119 | |
120 | if (prev_ret) { | |
121 | orig_prev = prev; | |
d1310b2e | 122 | while(prev && offset >= extent_map_end(prev_entry)) { |
5f56406a | 123 | prev = rb_next(prev); |
d1310b2e | 124 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406a CM |
125 | } |
126 | *prev_ret = prev; | |
127 | prev = orig_prev; | |
128 | } | |
129 | ||
130 | if (next_ret) { | |
d1310b2e | 131 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406a CM |
132 | while(prev && offset < prev_entry->start) { |
133 | prev = rb_prev(prev); | |
d1310b2e | 134 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406a CM |
135 | } |
136 | *next_ret = prev; | |
a52d9a80 | 137 | } |
a52d9a80 CM |
138 | return NULL; |
139 | } | |
140 | ||
141 | static inline struct rb_node *tree_search(struct rb_root *root, u64 offset) | |
142 | { | |
143 | struct rb_node *prev; | |
144 | struct rb_node *ret; | |
5f56406a | 145 | ret = __tree_search(root, offset, &prev, NULL); |
a52d9a80 CM |
146 | if (!ret) |
147 | return prev; | |
148 | return ret; | |
149 | } | |
150 | ||
d1310b2e | 151 | static int mergable_maps(struct extent_map *prev, struct extent_map *next) |
a52d9a80 | 152 | { |
d1310b2e CM |
153 | if (extent_map_end(prev) == next->start && |
154 | prev->flags == next->flags && | |
155 | prev->bdev == next->bdev && | |
156 | ((next->block_start == EXTENT_MAP_HOLE && | |
157 | prev->block_start == EXTENT_MAP_HOLE) || | |
158 | (next->block_start == EXTENT_MAP_INLINE && | |
159 | prev->block_start == EXTENT_MAP_INLINE) || | |
160 | (next->block_start == EXTENT_MAP_DELALLOC && | |
161 | prev->block_start == EXTENT_MAP_DELALLOC) || | |
162 | (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && | |
163 | next->block_start == extent_map_block_end(prev)))) { | |
164 | return 1; | |
165 | } | |
a52d9a80 CM |
166 | return 0; |
167 | } | |
168 | ||
169 | /* | |
d1310b2e | 170 | * add_extent_mapping tries a simple forward/backward merge with existing |
a52d9a80 CM |
171 | * mappings. The extent_map struct passed in will be inserted into |
172 | * the tree directly (no copies made, just a reference taken). | |
173 | */ | |
174 | int add_extent_mapping(struct extent_map_tree *tree, | |
175 | struct extent_map *em) | |
176 | { | |
177 | int ret = 0; | |
d1310b2e | 178 | struct extent_map *merge = NULL; |
a52d9a80 CM |
179 | struct rb_node *rb; |
180 | ||
d1310b2e | 181 | rb = tree_insert(&tree->map, em->start, &em->rb_node); |
a52d9a80 | 182 | if (rb) { |
d1310b2e | 183 | merge = rb_entry(rb, struct extent_map, rb_node); |
a52d9a80 CM |
184 | ret = -EEXIST; |
185 | goto out; | |
186 | } | |
187 | atomic_inc(&em->refs); | |
188 | if (em->start != 0) { | |
189 | rb = rb_prev(&em->rb_node); | |
190 | if (rb) | |
d1310b2e CM |
191 | merge = rb_entry(rb, struct extent_map, rb_node); |
192 | if (rb && mergable_maps(merge, em)) { | |
193 | em->start = merge->start; | |
194 | em->len += merge->len; | |
195 | em->block_start = merge->block_start; | |
196 | merge->in_tree = 0; | |
197 | rb_erase(&merge->rb_node, &tree->map); | |
198 | free_extent_map(merge); | |
a52d9a80 CM |
199 | } |
200 | } | |
d1310b2e CM |
201 | rb = rb_next(&em->rb_node); |
202 | if (rb) | |
203 | merge = rb_entry(rb, struct extent_map, rb_node); | |
204 | if (rb && mergable_maps(em, merge)) { | |
205 | em->len += merge->len; | |
206 | rb_erase(&merge->rb_node, &tree->map); | |
207 | merge->in_tree = 0; | |
208 | free_extent_map(merge); | |
209 | } | |
210 | tree->last = em; | |
a52d9a80 | 211 | out: |
a52d9a80 CM |
212 | return ret; |
213 | } | |
214 | EXPORT_SYMBOL(add_extent_mapping); | |
215 | ||
d1310b2e CM |
216 | static u64 range_end(u64 start, u64 len) |
217 | { | |
218 | if (start + len < start) | |
219 | return (u64)-1; | |
220 | return start + len; | |
221 | } | |
222 | ||
a52d9a80 CM |
223 | /* |
224 | * lookup_extent_mapping returns the first extent_map struct in the | |
d1310b2e | 225 | * tree that intersects the [start, len] range. There may |
a52d9a80 CM |
226 | * be additional objects in the tree that intersect, so check the object |
227 | * returned carefully to make sure you don't need additional lookups. | |
228 | */ | |
229 | struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree, | |
d1310b2e | 230 | u64 start, u64 len) |
a52d9a80 CM |
231 | { |
232 | struct extent_map *em; | |
233 | struct rb_node *rb_node; | |
d1310b2e | 234 | struct rb_node *prev = NULL; struct rb_node *next = NULL; u64 end = range_end(start, len); em = tree->last; if (em && end > em->start && start < extent_map_end(em)) goto found; |
a52d9a80 | 235 | |
5f56406a CM |
236 | rb_node = __tree_search(&tree->map, start, &prev, &next); |
237 | if (!rb_node && prev) { | |
238 | em = rb_entry(prev, struct extent_map, rb_node); | |
d1310b2e | 239 | if (end > em->start && start < extent_map_end(em)) |
5f56406a CM |
240 | goto found; |
241 | } | |
242 | if (!rb_node && next) { | |
243 | em = rb_entry(next, struct extent_map, rb_node); | |
d1310b2e | 244 | if (end > em->start && start < extent_map_end(em)) |
5f56406a CM |
245 | goto found; |
246 | } | |
a52d9a80 CM |
247 | if (!rb_node) { |
248 | em = NULL; | |
249 | goto out; | |
250 | } | |
251 | if (IS_ERR(rb_node)) { | |
252 | em = ERR_PTR(PTR_ERR(rb_node)); | |
253 | goto out; | |
254 | } | |
255 | em = rb_entry(rb_node, struct extent_map, rb_node); | |
d1310b2e CM |
256 | if (end > em->start && start < extent_map_end(em)) |
257 | goto found; | |
258 | ||
259 | em = NULL; | |
260 | goto out; | |
261 | ||
5f56406a | 262 | found: |
a52d9a80 | 263 | atomic_inc(&em->refs); |
d1310b2e | 264 | tree->last = em; |
a52d9a80 | 265 | out: |
a52d9a80 CM |
266 | return em; |
267 | } | |
268 | EXPORT_SYMBOL(lookup_extent_mapping); | |
269 | ||
270 | /* | |
271 | * removes an extent_map struct from the tree. No reference counts are | |
272 | * dropped, and no checks are done to see if the range is in use | |
273 | */ | |
274 | int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) | |
275 | { | |
d1310b2e | 276 | int ret = 0; |
a52d9a80 | 277 | |
d1310b2e CM |
278 | rb_erase(&em->rb_node, &tree->map); |
279 | em->in_tree = 0; | |
280 | if (tree->last == em) | |
281 | tree->last = NULL; | |
a52d9a80 CM |
282 | return ret; |
283 | } | |
284 | EXPORT_SYMBOL(remove_extent_mapping); |