3 #include <linux/slab.h>
4 #include <linux/module.h>
5 #include <linux/spinlock.h>
6 #include <linux/version.h>
7 #include <linux/hardirq.h>
8 #include "extent_map.h"
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
*,
16 static struct kmem_cache
*extent_map_cache
;
18 int __init
extent_map_init(void)
20 extent_map_cache
= btrfs_cache_create("extent_map",
21 sizeof(struct extent_map
), 0,
23 if (!extent_map_cache
)
28 void extent_map_exit(void)
31 kmem_cache_destroy(extent_map_cache
);
35 * extent_map_tree_init - initialize extent map tree
36 * @tree: tree to initialize
37 * @mask: flags for memory allocations during tree operations
39 * Initialize the extent tree @tree. Should be called for each new inode
40 * or other user of the extent_map interface.
42 void extent_map_tree_init(struct extent_map_tree
*tree
, gfp_t mask
)
44 tree
->map
.rb_node
= NULL
;
45 spin_lock_init(&tree
->lock
);
47 EXPORT_SYMBOL(extent_map_tree_init
);
50 * alloc_extent_map - allocate new extent map structure
51 * @mask: memory allocation flags
53 * Allocate a new extent_map structure. The new structure is
54 * returned with a reference count of one and needs to be
55 * freed using free_extent_map()
57 struct extent_map
*alloc_extent_map(gfp_t mask
)
59 struct extent_map
*em
;
60 em
= kmem_cache_alloc(extent_map_cache
, mask
);
61 if (!em
|| IS_ERR(em
))
65 atomic_set(&em
->refs
, 1);
68 EXPORT_SYMBOL(alloc_extent_map
);
71 * free_extent_map - drop reference count of an extent_map
72 * @em: extent map beeing releasead
74 * Drops the reference out on @em by one and free the structure
75 * if the reference count hits zero.
77 void free_extent_map(struct extent_map
*em
)
81 WARN_ON(atomic_read(&em
->refs
) == 0);
82 if (atomic_dec_and_test(&em
->refs
)) {
84 kmem_cache_free(extent_map_cache
, em
);
87 EXPORT_SYMBOL(free_extent_map
);
89 static struct rb_node
*tree_insert(struct rb_root
*root
, u64 offset
,
92 struct rb_node
** p
= &root
->rb_node
;
93 struct rb_node
* parent
= NULL
;
94 struct extent_map
*entry
;
98 entry
= rb_entry(parent
, struct extent_map
, rb_node
);
100 WARN_ON(!entry
->in_tree
);
102 if (offset
< entry
->start
)
104 else if (offset
>= extent_map_end(entry
))
110 entry
= rb_entry(node
, struct extent_map
, rb_node
);
112 rb_link_node(node
, parent
, p
);
113 rb_insert_color(node
, root
);
118 * search through the tree for an extent_map with a given offset. If
119 * it can't be found, try to find some neighboring extents
121 static struct rb_node
*__tree_search(struct rb_root
*root
, u64 offset
,
122 struct rb_node
**prev_ret
,
123 struct rb_node
**next_ret
)
125 struct rb_node
* n
= root
->rb_node
;
126 struct rb_node
*prev
= NULL
;
127 struct rb_node
*orig_prev
= NULL
;
128 struct extent_map
*entry
;
129 struct extent_map
*prev_entry
= NULL
;
132 entry
= rb_entry(n
, struct extent_map
, rb_node
);
136 WARN_ON(!entry
->in_tree
);
138 if (offset
< entry
->start
)
140 else if (offset
>= extent_map_end(entry
))
148 while(prev
&& offset
>= extent_map_end(prev_entry
)) {
149 prev
= rb_next(prev
);
150 prev_entry
= rb_entry(prev
, struct extent_map
, rb_node
);
157 prev_entry
= rb_entry(prev
, struct extent_map
, rb_node
);
158 while(prev
&& offset
< prev_entry
->start
) {
159 prev
= rb_prev(prev
);
160 prev_entry
= rb_entry(prev
, struct extent_map
, rb_node
);
168 * look for an offset in the tree, and if it can't be found, return
169 * the first offset we can find smaller than 'offset'.
171 static inline struct rb_node
*tree_search(struct rb_root
*root
, u64 offset
)
173 struct rb_node
*prev
;
175 ret
= __tree_search(root
, offset
, &prev
, NULL
);
181 /* check to see if two extent_map structs are adjacent and safe to merge */
182 static int mergable_maps(struct extent_map
*prev
, struct extent_map
*next
)
184 if (test_bit(EXTENT_FLAG_PINNED
, &prev
->flags
))
188 * don't merge compressed extents, we need to know their
191 if (test_bit(EXTENT_FLAG_COMPRESSED
, &prev
->flags
))
194 if (extent_map_end(prev
) == next
->start
&&
195 prev
->flags
== next
->flags
&&
196 prev
->bdev
== next
->bdev
&&
197 ((next
->block_start
== EXTENT_MAP_HOLE
&&
198 prev
->block_start
== EXTENT_MAP_HOLE
) ||
199 (next
->block_start
== EXTENT_MAP_INLINE
&&
200 prev
->block_start
== EXTENT_MAP_INLINE
) ||
201 (next
->block_start
== EXTENT_MAP_DELALLOC
&&
202 prev
->block_start
== EXTENT_MAP_DELALLOC
) ||
203 (next
->block_start
< EXTENT_MAP_LAST_BYTE
- 1 &&
204 next
->block_start
== extent_map_block_end(prev
)))) {
211 * add_extent_mapping - add new extent map to the extent tree
212 * @tree: tree to insert new map in
215 * Insert @em into @tree or perform a simple forward/backward merge with
216 * existing mappings. The extent_map struct passed in will be inserted
217 * into the tree directly, with an additional reference taken, or a
218 * reference dropped if the merge attempt was sucessfull.
220 int add_extent_mapping(struct extent_map_tree
*tree
,
221 struct extent_map
*em
)
224 struct extent_map
*merge
= NULL
;
226 struct extent_map
*exist
;
228 exist
= lookup_extent_mapping(tree
, em
->start
, em
->len
);
230 free_extent_map(exist
);
234 assert_spin_locked(&tree
->lock
);
235 rb
= tree_insert(&tree
->map
, em
->start
, &em
->rb_node
);
238 free_extent_map(merge
);
241 atomic_inc(&em
->refs
);
242 if (em
->start
!= 0) {
243 rb
= rb_prev(&em
->rb_node
);
245 merge
= rb_entry(rb
, struct extent_map
, rb_node
);
246 if (rb
&& mergable_maps(merge
, em
)) {
247 em
->start
= merge
->start
;
248 em
->len
+= merge
->len
;
249 em
->block_len
+= merge
->block_len
;
250 em
->block_start
= merge
->block_start
;
252 rb_erase(&merge
->rb_node
, &tree
->map
);
253 free_extent_map(merge
);
256 rb
= rb_next(&em
->rb_node
);
258 merge
= rb_entry(rb
, struct extent_map
, rb_node
);
259 if (rb
&& mergable_maps(em
, merge
)) {
260 em
->len
+= merge
->len
;
261 em
->block_len
+= merge
->len
;
262 rb_erase(&merge
->rb_node
, &tree
->map
);
264 free_extent_map(merge
);
269 EXPORT_SYMBOL(add_extent_mapping
);
271 /* simple helper to do math around the end of an extent, handling wrap */
272 static u64
range_end(u64 start
, u64 len
)
274 if (start
+ len
< start
)
280 * lookup_extent_mapping - lookup extent_map
281 * @tree: tree to lookup in
282 * @start: byte offset to start the search
283 * @len: length of the lookup range
285 * Find and return the first extent_map struct in @tree that intersects the
286 * [start, len] range. There may be additional objects in the tree that
287 * intersect, so check the object returned carefully to make sure that no
288 * additional lookups are needed.
290 struct extent_map
*lookup_extent_mapping(struct extent_map_tree
*tree
,
293 struct extent_map
*em
;
294 struct rb_node
*rb_node
;
295 struct rb_node
*prev
= NULL
;
296 struct rb_node
*next
= NULL
;
297 u64 end
= range_end(start
, len
);
299 assert_spin_locked(&tree
->lock
);
300 rb_node
= __tree_search(&tree
->map
, start
, &prev
, &next
);
301 if (!rb_node
&& prev
) {
302 em
= rb_entry(prev
, struct extent_map
, rb_node
);
303 if (end
> em
->start
&& start
< extent_map_end(em
))
306 if (!rb_node
&& next
) {
307 em
= rb_entry(next
, struct extent_map
, rb_node
);
308 if (end
> em
->start
&& start
< extent_map_end(em
))
315 if (IS_ERR(rb_node
)) {
316 em
= ERR_PTR(PTR_ERR(rb_node
));
319 em
= rb_entry(rb_node
, struct extent_map
, rb_node
);
320 if (end
> em
->start
&& start
< extent_map_end(em
))
327 atomic_inc(&em
->refs
);
331 EXPORT_SYMBOL(lookup_extent_mapping
);
334 * remove_extent_mapping - removes an extent_map from the extent tree
335 * @tree: extent tree to remove from
336 * @em: extent map beeing removed
338 * Removes @em from @tree. No reference counts are dropped, and no checks
339 * are done to see if the range is in use
341 int remove_extent_mapping(struct extent_map_tree
*tree
, struct extent_map
*em
)
345 WARN_ON(test_bit(EXTENT_FLAG_PINNED
, &em
->flags
));
346 assert_spin_locked(&tree
->lock
);
347 rb_erase(&em
->rb_node
, &tree
->map
);
351 EXPORT_SYMBOL(remove_extent_mapping
);
This page took 0.054907 seconds and 6 git commands to generate.