Blame view
fs/btrfs/extent_map.c
8.68 KB
d1310b2e0 Btrfs: Split the ... |
1 |
#include <linux/err.h> |
d1310b2e0 Btrfs: Split the ... |
2 |
#include <linux/slab.h> |
a52d9a803 Btrfs: Extent bas... |
3 4 |
#include <linux/module.h> #include <linux/spinlock.h> |
d1310b2e0 Btrfs: Split the ... |
5 |
#include <linux/hardirq.h> |
261507a02 btrfs: Allow to a... |
6 |
#include "ctree.h" |
a52d9a803 Btrfs: Extent bas... |
7 |
#include "extent_map.h" |
86479a04e Add support for d... |
8 |
|
a52d9a803 Btrfs: Extent bas... |
9 |
static struct kmem_cache *extent_map_cache; |
ca6646264 Btrfs: Add effici... |
10 |
|
2f4cbe644 Btrfs: Return val... |
11 |
int __init extent_map_init(void) |
a52d9a803 Btrfs: Extent bas... |
12 |
{ |
9601e3f63 Btrfs: kill btrfs... |
13 14 15 |
extent_map_cache = kmem_cache_create("extent_map", sizeof(struct extent_map), 0, SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL); |
2f4cbe644 Btrfs: Return val... |
16 17 |
if (!extent_map_cache) return -ENOMEM; |
2f4cbe644 Btrfs: Return val... |
18 |
return 0; |
a52d9a803 Btrfs: Extent bas... |
19 |
} |
17636e03f Btrfs: section mi... |
20 |
void extent_map_exit(void) |
a52d9a803 Btrfs: Extent bas... |
21 |
{ |
a52d9a803 Btrfs: Extent bas... |
22 23 |
if (extent_map_cache) kmem_cache_destroy(extent_map_cache); |
a52d9a803 Btrfs: Extent bas... |
24 |
} |
9d2423c5c Btrfs: kerneldoc ... |
25 26 27 |
/** * extent_map_tree_init - initialize extent map tree * @tree: tree to initialize |
9d2423c5c Btrfs: kerneldoc ... |
28 29 30 31 |
* * Initialize the extent tree @tree. Should be called for each new inode * or other user of the extent_map interface. */ |
a8067e022 btrfs: drop unuse... |
32 |
void extent_map_tree_init(struct extent_map_tree *tree) |
a52d9a803 Btrfs: Extent bas... |
33 |
{ |
6bef4d317 Btrfs: use RB_ROO... |
34 |
tree->map = RB_ROOT; |
890871be8 Btrfs: switch ext... |
35 |
rwlock_init(&tree->lock); |
a52d9a803 Btrfs: Extent bas... |
36 |
} |
a52d9a803 Btrfs: Extent bas... |
37 |
|
9d2423c5c Btrfs: kerneldoc ... |
38 39 |
/** * alloc_extent_map - allocate new extent map structure |
9d2423c5c Btrfs: kerneldoc ... |
40 41 42 43 44 |
* * Allocate a new extent_map structure. The new structure is * returned with a reference count of one and needs to be * freed using free_extent_map() */ |
172ddd60a btrfs: drop gfp p... |
45 |
struct extent_map *alloc_extent_map(void) |
a52d9a803 Btrfs: Extent bas... |
46 47 |
{ struct extent_map *em; |
172ddd60a btrfs: drop gfp p... |
48 |
em = kmem_cache_alloc(extent_map_cache, GFP_NOFS); |
c26a92037 Btrfs: check retu... |
49 50 |
if (!em) return NULL; |
a52d9a803 Btrfs: Extent bas... |
51 |
em->in_tree = 0; |
d1310b2e0 Btrfs: Split the ... |
52 |
em->flags = 0; |
261507a02 btrfs: Allow to a... |
53 |
em->compress_type = BTRFS_COMPRESS_NONE; |
a52d9a803 Btrfs: Extent bas... |
54 55 56 |
atomic_set(&em->refs, 1); return em; } |
a52d9a803 Btrfs: Extent bas... |
57 |
|
9d2423c5c Btrfs: kerneldoc ... |
58 59 60 61 62 63 64 |
/** * free_extent_map - drop reference count of an extent_map * @em: extent map beeing releasead * * Drops the reference out on @em by one and free the structure * if the reference count hits zero. */ |
a52d9a803 Btrfs: Extent bas... |
65 66 |
void free_extent_map(struct extent_map *em) { |
2bf5a725a Btrfs: fsx delall... |
67 68 |
if (!em) return; |
d1310b2e0 Btrfs: Split the ... |
69 |
WARN_ON(atomic_read(&em->refs) == 0); |
a52d9a803 Btrfs: Extent bas... |
70 71 72 73 74 |
if (atomic_dec_and_test(&em->refs)) { WARN_ON(em->in_tree); kmem_cache_free(extent_map_cache, em); } } |
a52d9a803 Btrfs: Extent bas... |
75 |
|
a52d9a803 Btrfs: Extent bas... |
76 77 78 |
static struct rb_node *tree_insert(struct rb_root *root, u64 offset, struct rb_node *node) { |
d397712bc Btrfs: Fix checkp... |
79 80 |
struct rb_node **p = &root->rb_node; struct rb_node *parent = NULL; |
d1310b2e0 Btrfs: Split the ... |
81 |
struct extent_map *entry; |
a52d9a803 Btrfs: Extent bas... |
82 |
|
d397712bc Btrfs: Fix checkp... |
83 |
while (*p) { |
a52d9a803 Btrfs: Extent bas... |
84 |
parent = *p; |
d1310b2e0 Btrfs: Split the ... |
85 86 87 |
entry = rb_entry(parent, struct extent_map, rb_node); WARN_ON(!entry->in_tree); |
a52d9a803 Btrfs: Extent bas... |
88 89 90 |
if (offset < entry->start) p = &(*p)->rb_left; |
d1310b2e0 Btrfs: Split the ... |
91 |
else if (offset >= extent_map_end(entry)) |
a52d9a803 Btrfs: Extent bas... |
92 93 94 95 |
p = &(*p)->rb_right; else return parent; } |
d1310b2e0 Btrfs: Split the ... |
96 |
entry = rb_entry(node, struct extent_map, rb_node); |
a52d9a803 Btrfs: Extent bas... |
97 98 99 100 101 |
entry->in_tree = 1; rb_link_node(node, parent, p); rb_insert_color(node, root); return NULL; } |
d352ac681 Btrfs: add and im... |
102 103 104 105 |
/* * search through the tree for an extent_map with a given offset. If * it can't be found, try to find some neighboring extents */ |
a52d9a803 Btrfs: Extent bas... |
106 |
static struct rb_node *__tree_search(struct rb_root *root, u64 offset, |
5f56406aa Btrfs: Fix hole i... |
107 108 |
struct rb_node **prev_ret, struct rb_node **next_ret) |
a52d9a803 Btrfs: Extent bas... |
109 |
{ |
d397712bc Btrfs: Fix checkp... |
110 |
struct rb_node *n = root->rb_node; |
a52d9a803 Btrfs: Extent bas... |
111 |
struct rb_node *prev = NULL; |
5f56406aa Btrfs: Fix hole i... |
112 |
struct rb_node *orig_prev = NULL; |
d1310b2e0 Btrfs: Split the ... |
113 114 |
struct extent_map *entry; struct extent_map *prev_entry = NULL; |
a52d9a803 Btrfs: Extent bas... |
115 |
|
d397712bc Btrfs: Fix checkp... |
116 |
while (n) { |
d1310b2e0 Btrfs: Split the ... |
117 |
entry = rb_entry(n, struct extent_map, rb_node); |
a52d9a803 Btrfs: Extent bas... |
118 119 |
prev = n; prev_entry = entry; |
d1310b2e0 Btrfs: Split the ... |
120 |
WARN_ON(!entry->in_tree); |
a52d9a803 Btrfs: Extent bas... |
121 122 |
if (offset < entry->start) n = n->rb_left; |
d1310b2e0 Btrfs: Split the ... |
123 |
else if (offset >= extent_map_end(entry)) |
a52d9a803 Btrfs: Extent bas... |
124 125 126 127 |
n = n->rb_right; else return n; } |
5f56406aa Btrfs: Fix hole i... |
128 129 130 |
if (prev_ret) { orig_prev = prev; |
d397712bc Btrfs: Fix checkp... |
131 |
while (prev && offset >= extent_map_end(prev_entry)) { |
5f56406aa Btrfs: Fix hole i... |
132 |
prev = rb_next(prev); |
d1310b2e0 Btrfs: Split the ... |
133 |
prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406aa Btrfs: Fix hole i... |
134 135 136 137 138 139 |
} *prev_ret = prev; prev = orig_prev; } if (next_ret) { |
d1310b2e0 Btrfs: Split the ... |
140 |
prev_entry = rb_entry(prev, struct extent_map, rb_node); |
d397712bc Btrfs: Fix checkp... |
141 |
while (prev && offset < prev_entry->start) { |
5f56406aa Btrfs: Fix hole i... |
142 |
prev = rb_prev(prev); |
d1310b2e0 Btrfs: Split the ... |
143 |
prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406aa Btrfs: Fix hole i... |
144 145 |
} *next_ret = prev; |
a52d9a803 Btrfs: Extent bas... |
146 |
} |
a52d9a803 Btrfs: Extent bas... |
147 148 |
return NULL; } |
d352ac681 Btrfs: add and im... |
149 |
/* check to see if two extent_map structs are adjacent and safe to merge */ |
d1310b2e0 Btrfs: Split the ... |
150 |
static int mergable_maps(struct extent_map *prev, struct extent_map *next) |
a52d9a803 Btrfs: Extent bas... |
151 |
{ |
7f3c74fb8 Btrfs: Keep exten... |
152 153 |
if (test_bit(EXTENT_FLAG_PINNED, &prev->flags)) return 0; |
c8b978188 Btrfs: Add zlib c... |
154 155 156 157 158 159 |
/* * don't merge compressed extents, we need to know their * actual size */ if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags)) return 0; |
d1310b2e0 Btrfs: Split the ... |
160 161 162 163 164 165 166 167 168 169 170 171 172 |
if (extent_map_end(prev) == next->start && prev->flags == next->flags && prev->bdev == next->bdev && ((next->block_start == EXTENT_MAP_HOLE && prev->block_start == EXTENT_MAP_HOLE) || (next->block_start == EXTENT_MAP_INLINE && prev->block_start == EXTENT_MAP_INLINE) || (next->block_start == EXTENT_MAP_DELALLOC && prev->block_start == EXTENT_MAP_DELALLOC) || (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && next->block_start == extent_map_block_end(prev)))) { return 1; } |
a52d9a803 Btrfs: Extent bas... |
173 174 |
return 0; } |
4d2c8f62f Btrfs: clean up c... |
175 |
static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) |
a1ed835e1 Btrfs: Fix extent... |
176 |
{ |
a1ed835e1 Btrfs: Fix extent... |
177 178 |
struct extent_map *merge = NULL; struct rb_node *rb; |
a1ed835e1 Btrfs: Fix extent... |
179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 |
if (em->start != 0) { rb = rb_prev(&em->rb_node); if (rb) merge = rb_entry(rb, struct extent_map, rb_node); if (rb && mergable_maps(merge, em)) { em->start = merge->start; em->len += merge->len; em->block_len += merge->block_len; em->block_start = merge->block_start; merge->in_tree = 0; rb_erase(&merge->rb_node, &tree->map); free_extent_map(merge); } } rb = rb_next(&em->rb_node); if (rb) merge = rb_entry(rb, struct extent_map, rb_node); if (rb && mergable_maps(em, merge)) { em->len += merge->len; em->block_len += merge->len; rb_erase(&merge->rb_node, &tree->map); merge->in_tree = 0; free_extent_map(merge); } |
4d2c8f62f Btrfs: clean up c... |
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 |
} int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len) { int ret = 0; struct extent_map *em; write_lock(&tree->lock); em = lookup_extent_mapping(tree, start, len); WARN_ON(!em || em->start != start); if (!em) goto out; clear_bit(EXTENT_FLAG_PINNED, &em->flags); try_merge_map(tree, em); |
a1ed835e1 Btrfs: Fix extent... |
223 224 225 226 227 228 229 |
free_extent_map(em); out: write_unlock(&tree->lock); return ret; } |
9d2423c5c Btrfs: kerneldoc ... |
230 231 232 233 234 235 236 237 |
/** * add_extent_mapping - add new extent map to the extent tree * @tree: tree to insert new map in * @em: map to insert * * Insert @em into @tree or perform a simple forward/backward merge with * existing mappings. The extent_map struct passed in will be inserted * into the tree directly, with an additional reference taken, or a |
25985edce Fix common misspe... |
238 |
* reference dropped if the merge attempt was successful. |
a52d9a803 Btrfs: Extent bas... |
239 240 241 242 243 |
*/ int add_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) { int ret = 0; |
a52d9a803 Btrfs: Extent bas... |
244 |
struct rb_node *rb; |
7c2fe32a2 Btrfs: Fix add_ex... |
245 |
struct extent_map *exist; |
a52d9a803 Btrfs: Extent bas... |
246 |
|
7c2fe32a2 Btrfs: Fix add_ex... |
247 248 249 250 251 252 |
exist = lookup_extent_mapping(tree, em->start, em->len); if (exist) { free_extent_map(exist); ret = -EEXIST; goto out; } |
d1310b2e0 Btrfs: Split the ... |
253 |
rb = tree_insert(&tree->map, em->start, &em->rb_node); |
a52d9a803 Btrfs: Extent bas... |
254 |
if (rb) { |
a52d9a803 Btrfs: Extent bas... |
255 256 257 258 |
ret = -EEXIST; goto out; } atomic_inc(&em->refs); |
4d2c8f62f Btrfs: clean up c... |
259 260 |
try_merge_map(tree, em); |
a52d9a803 Btrfs: Extent bas... |
261 |
out: |
a52d9a803 Btrfs: Extent bas... |
262 263 |
return ret; } |
a52d9a803 Btrfs: Extent bas... |
264 |
|
d352ac681 Btrfs: add and im... |
265 |
/* simple helper to do math around the end of an extent, handling wrap */ |
d1310b2e0 Btrfs: Split the ... |
266 267 268 269 270 271 |
static u64 range_end(u64 start, u64 len) { if (start + len < start) return (u64)-1; return start + len; } |
ed64f0665 Btrfs: clean up c... |
272 273 |
struct extent_map *__lookup_extent_mapping(struct extent_map_tree *tree, u64 start, u64 len, int strict) |
a52d9a803 Btrfs: Extent bas... |
274 275 276 |
{ struct extent_map *em; struct rb_node *rb_node; |
306929f36 btrfs: fix strang... |
277 278 279 |
struct rb_node *prev = NULL; struct rb_node *next = NULL; u64 end = range_end(start, len); |
5f56406aa Btrfs: Fix hole i... |
280 |
rb_node = __tree_search(&tree->map, start, &prev, &next); |
a52d9a803 Btrfs: Extent bas... |
281 |
if (!rb_node) { |
ed64f0665 Btrfs: clean up c... |
282 283 284 285 286 287 |
if (prev) rb_node = prev; else if (next) rb_node = next; else return NULL; |
a52d9a803 Btrfs: Extent bas... |
288 |
} |
ed64f0665 Btrfs: clean up c... |
289 |
|
a52d9a803 Btrfs: Extent bas... |
290 |
em = rb_entry(rb_node, struct extent_map, rb_node); |
d1310b2e0 Btrfs: Split the ... |
291 |
|
ed64f0665 Btrfs: clean up c... |
292 293 |
if (strict && !(end > em->start && start < extent_map_end(em))) return NULL; |
d1310b2e0 Btrfs: Split the ... |
294 |
|
a52d9a803 Btrfs: Extent bas... |
295 |
atomic_inc(&em->refs); |
a52d9a803 Btrfs: Extent bas... |
296 297 |
return em; } |
a52d9a803 Btrfs: Extent bas... |
298 |
|
9d2423c5c Btrfs: kerneldoc ... |
299 |
/** |
ed64f0665 Btrfs: clean up c... |
300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 |
* lookup_extent_mapping - lookup extent_map * @tree: tree to lookup in * @start: byte offset to start the search * @len: length of the lookup range * * Find and return the first extent_map struct in @tree that intersects the * [start, len] range. There may be additional objects in the tree that * intersect, so check the object returned carefully to make sure that no * additional lookups are needed. */ struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree, u64 start, u64 len) { return __lookup_extent_mapping(tree, start, len, 1); } /** |
b917b7c3b Btrfs: search for... |
317 318 319 320 321 322 323 324 325 326 327 328 329 |
* search_extent_mapping - find a nearby extent map * @tree: tree to lookup in * @start: byte offset to start the search * @len: length of the lookup range * * Find and return the first extent_map struct in @tree that intersects the * [start, len] range. * * If one can't be found, any nearby extent may be returned */ struct extent_map *search_extent_mapping(struct extent_map_tree *tree, u64 start, u64 len) { |
ed64f0665 Btrfs: clean up c... |
330 |
return __lookup_extent_mapping(tree, start, len, 0); |
b917b7c3b Btrfs: search for... |
331 332 333 |
} /** |
9d2423c5c Btrfs: kerneldoc ... |
334 335 336 337 338 339 |
* remove_extent_mapping - removes an extent_map from the extent tree * @tree: extent tree to remove from * @em: extent map beeing removed * * Removes @em from @tree. No reference counts are dropped, and no checks * are done to see if the range is in use |
a52d9a803 Btrfs: Extent bas... |
340 341 342 |
*/ int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) { |
d1310b2e0 Btrfs: Split the ... |
343 |
int ret = 0; |
a52d9a803 Btrfs: Extent bas... |
344 |
|
7f3c74fb8 Btrfs: Keep exten... |
345 |
WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); |
d1310b2e0 Btrfs: Split the ... |
346 347 |
rb_erase(&em->rb_node, &tree->map); em->in_tree = 0; |
a52d9a803 Btrfs: Extent bas... |
348 349 |
return ret; } |