Blame view
fs/btrfs/extent_map.c
17.2 KB
b24413180 License cleanup: ... |
1 |
// SPDX-License-Identifier: GPL-2.0 |
c1d7c514f btrfs: replace GP... |
2 |
|
d1310b2e0 Btrfs: Split the ... |
3 |
#include <linux/err.h> |
d1310b2e0 Btrfs: Split the ... |
4 |
#include <linux/slab.h> |
a52d9a803 Btrfs: Extent bas... |
5 |
#include <linux/spinlock.h> |
261507a02 btrfs: Allow to a... |
6 |
#include "ctree.h" |
1c11b63ef btrfs: replace pe... |
7 |
#include "volumes.h" |
a52d9a803 Btrfs: Extent bas... |
8 |
#include "extent_map.h" |
ebb8765b2 btrfs: move btrfs... |
9 |
#include "compression.h" |
a52d9a803 Btrfs: Extent bas... |
10 |
|
86479a04e Add support for d... |
11 |
|
a52d9a803 Btrfs: Extent bas... |
12 |
static struct kmem_cache *extent_map_cache; |
ca6646264 Btrfs: Add effici... |
13 |
|
2f4cbe644 Btrfs: Return val... |
14 |
int __init extent_map_init(void) |
a52d9a803 Btrfs: Extent bas... |
15 |
{ |
837e19728 btrfs: polish nam... |
16 |
extent_map_cache = kmem_cache_create("btrfs_extent_map", |
9601e3f63 Btrfs: kill btrfs... |
17 |
sizeof(struct extent_map), 0, |
fba4b6977 btrfs: Fix slab a... |
18 |
SLAB_MEM_SPREAD, NULL); |
2f4cbe644 Btrfs: Return val... |
19 20 |
if (!extent_map_cache) return -ENOMEM; |
2f4cbe644 Btrfs: Return val... |
21 |
return 0; |
a52d9a803 Btrfs: Extent bas... |
22 |
} |
e67c718b5 btrfs: add more _... |
23 |
void __cold extent_map_exit(void) |
a52d9a803 Btrfs: Extent bas... |
24 |
{ |
5598e9005 btrfs: drop null ... |
25 |
kmem_cache_destroy(extent_map_cache); |
a52d9a803 Btrfs: Extent bas... |
26 |
} |
9d2423c5c Btrfs: kerneldoc ... |
27 28 29 |
/** * extent_map_tree_init - initialize extent map tree * @tree: tree to initialize |
9d2423c5c Btrfs: kerneldoc ... |
30 31 32 33 |
* * Initialize the extent tree @tree. Should be called for each new inode * or other user of the extent_map interface. */ |
a8067e022 btrfs: drop unuse... |
34 |
void extent_map_tree_init(struct extent_map_tree *tree) |
a52d9a803 Btrfs: Extent bas... |
35 |
{ |
07e1ce096 Btrfs: extent_map... |
36 |
tree->map = RB_ROOT_CACHED; |
5dc562c54 Btrfs: turbo char... |
37 |
INIT_LIST_HEAD(&tree->modified_extents); |
890871be8 Btrfs: switch ext... |
38 |
rwlock_init(&tree->lock); |
a52d9a803 Btrfs: Extent bas... |
39 |
} |
a52d9a803 Btrfs: Extent bas... |
40 |
|
9d2423c5c Btrfs: kerneldoc ... |
41 42 |
/** * alloc_extent_map - allocate new extent map structure |
9d2423c5c Btrfs: kerneldoc ... |
43 44 45 46 47 |
* * 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... |
48 |
struct extent_map *alloc_extent_map(void) |
a52d9a803 Btrfs: Extent bas... |
49 50 |
{ struct extent_map *em; |
70c8a91ce Btrfs: log change... |
51 |
em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS); |
c26a92037 Btrfs: check retu... |
52 53 |
if (!em) return NULL; |
cbc0e9287 Btrfs: remove unn... |
54 |
RB_CLEAR_NODE(&em->rb_node); |
d1310b2e0 Btrfs: Split the ... |
55 |
em->flags = 0; |
261507a02 btrfs: Allow to a... |
56 |
em->compress_type = BTRFS_COMPRESS_NONE; |
5dc562c54 Btrfs: turbo char... |
57 |
em->generation = 0; |
490b54d6f btrfs: convert ex... |
58 |
refcount_set(&em->refs, 1); |
5dc562c54 Btrfs: turbo char... |
59 |
INIT_LIST_HEAD(&em->list); |
a52d9a803 Btrfs: Extent bas... |
60 61 |
return em; } |
a52d9a803 Btrfs: Extent bas... |
62 |
|
9d2423c5c Btrfs: kerneldoc ... |
63 64 |
/** * free_extent_map - drop reference count of an extent_map |
013276101 btrfs: fix string... |
65 |
* @em: extent map being released |
9d2423c5c Btrfs: kerneldoc ... |
66 67 68 69 |
* * Drops the reference out on @em by one and free the structure * if the reference count hits zero. */ |
a52d9a803 Btrfs: Extent bas... |
70 71 |
void free_extent_map(struct extent_map *em) { |
2bf5a725a Btrfs: fsx delall... |
72 73 |
if (!em) return; |
490b54d6f btrfs: convert ex... |
74 75 |
WARN_ON(refcount_read(&em->refs) == 0); if (refcount_dec_and_test(&em->refs)) { |
cbc0e9287 Btrfs: remove unn... |
76 |
WARN_ON(extent_map_in_tree(em)); |
5dc562c54 Btrfs: turbo char... |
77 |
WARN_ON(!list_empty(&em->list)); |
298a8f9cf Btrfs: fix NULL p... |
78 |
if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) |
95617d693 btrfs: cleanup, s... |
79 |
kfree(em->map_lookup); |
a52d9a803 Btrfs: Extent bas... |
80 81 82 |
kmem_cache_free(extent_map_cache, em); } } |
a52d9a803 Btrfs: Extent bas... |
83 |
|
32193c147 Btrfs: faster and... |
84 85 86 87 88 89 90 |
/* simple helper to do math around the end of an extent, handling wrap */ static u64 range_end(u64 start, u64 len) { if (start + len < start) return (u64)-1; return start + len; } |
07e1ce096 Btrfs: extent_map... |
91 |
static int tree_insert(struct rb_root_cached *root, struct extent_map *em) |
a52d9a803 Btrfs: Extent bas... |
92 |
{ |
07e1ce096 Btrfs: extent_map... |
93 |
struct rb_node **p = &root->rb_root.rb_node; |
d397712bc Btrfs: Fix checkp... |
94 |
struct rb_node *parent = NULL; |
32193c147 Btrfs: faster and... |
95 96 97 |
struct extent_map *entry = NULL; struct rb_node *orig_parent = NULL; u64 end = range_end(em->start, em->len); |
07e1ce096 Btrfs: extent_map... |
98 |
bool leftmost = true; |
a52d9a803 Btrfs: Extent bas... |
99 |
|
d397712bc Btrfs: Fix checkp... |
100 |
while (*p) { |
a52d9a803 Btrfs: Extent bas... |
101 |
parent = *p; |
d1310b2e0 Btrfs: Split the ... |
102 |
entry = rb_entry(parent, struct extent_map, rb_node); |
07e1ce096 Btrfs: extent_map... |
103 |
if (em->start < entry->start) { |
a52d9a803 Btrfs: Extent bas... |
104 |
p = &(*p)->rb_left; |
07e1ce096 Btrfs: extent_map... |
105 |
} else if (em->start >= extent_map_end(entry)) { |
a52d9a803 Btrfs: Extent bas... |
106 |
p = &(*p)->rb_right; |
07e1ce096 Btrfs: extent_map... |
107 108 |
leftmost = false; } else { |
32193c147 Btrfs: faster and... |
109 |
return -EEXIST; |
07e1ce096 Btrfs: extent_map... |
110 |
} |
a52d9a803 Btrfs: Extent bas... |
111 |
} |
32193c147 Btrfs: faster and... |
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
orig_parent = parent; while (parent && em->start >= extent_map_end(entry)) { parent = rb_next(parent); entry = rb_entry(parent, struct extent_map, rb_node); } if (parent) if (end > entry->start && em->start < extent_map_end(entry)) return -EEXIST; parent = orig_parent; entry = rb_entry(parent, struct extent_map, rb_node); while (parent && em->start < entry->start) { parent = rb_prev(parent); entry = rb_entry(parent, struct extent_map, rb_node); } if (parent) if (end > entry->start && em->start < extent_map_end(entry)) return -EEXIST; |
32193c147 Btrfs: faster and... |
130 |
rb_link_node(&em->rb_node, orig_parent, p); |
07e1ce096 Btrfs: extent_map... |
131 |
rb_insert_color_cached(&em->rb_node, root, leftmost); |
32193c147 Btrfs: faster and... |
132 |
return 0; |
a52d9a803 Btrfs: Extent bas... |
133 |
} |
d352ac681 Btrfs: add and im... |
134 135 136 137 |
/* * 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... |
138 |
static struct rb_node *__tree_search(struct rb_root *root, u64 offset, |
5f56406aa Btrfs: Fix hole i... |
139 140 |
struct rb_node **prev_ret, struct rb_node **next_ret) |
a52d9a803 Btrfs: Extent bas... |
141 |
{ |
d397712bc Btrfs: Fix checkp... |
142 |
struct rb_node *n = root->rb_node; |
a52d9a803 Btrfs: Extent bas... |
143 |
struct rb_node *prev = NULL; |
5f56406aa Btrfs: Fix hole i... |
144 |
struct rb_node *orig_prev = NULL; |
d1310b2e0 Btrfs: Split the ... |
145 146 |
struct extent_map *entry; struct extent_map *prev_entry = NULL; |
a52d9a803 Btrfs: Extent bas... |
147 |
|
d397712bc Btrfs: Fix checkp... |
148 |
while (n) { |
d1310b2e0 Btrfs: Split the ... |
149 |
entry = rb_entry(n, struct extent_map, rb_node); |
a52d9a803 Btrfs: Extent bas... |
150 151 152 153 154 |
prev = n; prev_entry = entry; if (offset < entry->start) n = n->rb_left; |
d1310b2e0 Btrfs: Split the ... |
155 |
else if (offset >= extent_map_end(entry)) |
a52d9a803 Btrfs: Extent bas... |
156 157 158 159 |
n = n->rb_right; else return n; } |
5f56406aa Btrfs: Fix hole i... |
160 161 162 |
if (prev_ret) { orig_prev = prev; |
d397712bc Btrfs: Fix checkp... |
163 |
while (prev && offset >= extent_map_end(prev_entry)) { |
5f56406aa Btrfs: Fix hole i... |
164 |
prev = rb_next(prev); |
d1310b2e0 Btrfs: Split the ... |
165 |
prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406aa Btrfs: Fix hole i... |
166 167 168 169 170 171 |
} *prev_ret = prev; prev = orig_prev; } if (next_ret) { |
d1310b2e0 Btrfs: Split the ... |
172 |
prev_entry = rb_entry(prev, struct extent_map, rb_node); |
d397712bc Btrfs: Fix checkp... |
173 |
while (prev && offset < prev_entry->start) { |
5f56406aa Btrfs: Fix hole i... |
174 |
prev = rb_prev(prev); |
d1310b2e0 Btrfs: Split the ... |
175 |
prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406aa Btrfs: Fix hole i... |
176 177 |
} *next_ret = prev; |
a52d9a803 Btrfs: Extent bas... |
178 |
} |
a52d9a803 Btrfs: Extent bas... |
179 180 |
return NULL; } |
d352ac681 Btrfs: add and im... |
181 |
/* check to see if two extent_map structs are adjacent and safe to merge */ |
d1310b2e0 Btrfs: Split the ... |
182 |
static int mergable_maps(struct extent_map *prev, struct extent_map *next) |
a52d9a803 Btrfs: Extent bas... |
183 |
{ |
7f3c74fb8 Btrfs: Keep exten... |
184 185 |
if (test_bit(EXTENT_FLAG_PINNED, &prev->flags)) return 0; |
c8b978188 Btrfs: Add zlib c... |
186 187 188 189 190 191 |
/* * don't merge compressed extents, we need to know their * actual size */ if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags)) return 0; |
201a90389 Btrfs: do not all... |
192 193 194 |
if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) || test_bit(EXTENT_FLAG_LOGGING, &next->flags)) return 0; |
09a2a8f96 Btrfs: fix bad ex... |
195 196 197 198 199 200 201 |
/* * We don't want to merge stuff that hasn't been written to the log yet * since it may not reflect exactly what is on disk, and that would be * bad. */ if (!list_empty(&prev->list) || !list_empty(&next->list)) return 0; |
951e05a90 btrfs: Remove imp... |
202 203 |
ASSERT(next->block_start != EXTENT_MAP_DELALLOC && prev->block_start != EXTENT_MAP_DELALLOC); |
c3e14909d btrfs: assert ext... |
204 205 206 |
if (prev->map_lookup || next->map_lookup) ASSERT(test_bit(EXTENT_FLAG_FS_MAPPING, &prev->flags) && test_bit(EXTENT_FLAG_FS_MAPPING, &next->flags)); |
d1310b2e0 Btrfs: Split the ... |
207 208 |
if (extent_map_end(prev) == next->start && prev->flags == next->flags && |
c3e14909d btrfs: assert ext... |
209 |
prev->map_lookup == next->map_lookup && |
d1310b2e0 Btrfs: Split the ... |
210 211 212 213 |
((next->block_start == EXTENT_MAP_HOLE && prev->block_start == EXTENT_MAP_HOLE) || (next->block_start == EXTENT_MAP_INLINE && prev->block_start == EXTENT_MAP_INLINE) || |
d1310b2e0 Btrfs: Split the ... |
214 215 216 217 |
(next->block_start < EXTENT_MAP_LAST_BYTE - 1 && next->block_start == extent_map_block_end(prev)))) { return 1; } |
a52d9a803 Btrfs: Extent bas... |
218 219 |
return 0; } |
4d2c8f62f Btrfs: clean up c... |
220 |
static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) |
a1ed835e1 Btrfs: Fix extent... |
221 |
{ |
a1ed835e1 Btrfs: Fix extent... |
222 223 |
struct extent_map *merge = NULL; struct rb_node *rb; |
a1ed835e1 Btrfs: Fix extent... |
224 |
|
ac05ca913 Btrfs: fix race b... |
225 226 227 228 229 230 231 232 233 234 |
/* * We can't modify an extent map that is in the tree and that is being * used by another task, as it can cause that other task to see it in * inconsistent state during the merging. We always have 1 reference for * the tree and 1 for this task (which is unpinning the extent map or * clearing the logging flag), so anything > 2 means it's being used by * other tasks too. */ if (refcount_read(&em->refs) > 2) return; |
a1ed835e1 Btrfs: Fix extent... |
235 236 237 238 239 240 |
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; |
70c8a91ce Btrfs: log change... |
241 |
em->orig_start = merge->orig_start; |
a1ed835e1 Btrfs: Fix extent... |
242 243 244 |
em->len += merge->len; em->block_len += merge->block_len; em->block_start = merge->block_start; |
70c8a91ce Btrfs: log change... |
245 246 247 |
em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start; em->mod_start = merge->mod_start; em->generation = max(em->generation, merge->generation); |
5dc562c54 Btrfs: turbo char... |
248 |
|
07e1ce096 Btrfs: extent_map... |
249 |
rb_erase_cached(&merge->rb_node, &tree->map); |
cbc0e9287 Btrfs: remove unn... |
250 |
RB_CLEAR_NODE(&merge->rb_node); |
a1ed835e1 Btrfs: Fix extent... |
251 252 253 254 255 256 257 258 259 |
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; |
d527afe1e Btrfs: fix extent... |
260 |
em->block_len += merge->block_len; |
07e1ce096 Btrfs: extent_map... |
261 |
rb_erase_cached(&merge->rb_node, &tree->map); |
cbc0e9287 Btrfs: remove unn... |
262 |
RB_CLEAR_NODE(&merge->rb_node); |
70c8a91ce Btrfs: log change... |
263 264 |
em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start; em->generation = max(em->generation, merge->generation); |
a1ed835e1 Btrfs: Fix extent... |
265 266 |
free_extent_map(merge); } |
4d2c8f62f Btrfs: clean up c... |
267 |
} |
5dc562c54 Btrfs: turbo char... |
268 |
/** |
52b1de91e btrfs: unpin_exte... |
269 |
* unpin_extent_cache - unpin an extent from the cache |
5dc562c54 Btrfs: turbo char... |
270 271 272 273 |
* @tree: tree to unpin the extent in * @start: logical offset in the file * @len: length of the extent * @gen: generation that this extent has been modified in |
5dc562c54 Btrfs: turbo char... |
274 275 276 277 278 279 280 |
* * Called after an extent has been written to disk properly. Set the generation * to the generation that actually added the file item to the inode so we know * we need to sync this extent when we call fsync(). */ int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, u64 gen) |
4d2c8f62f Btrfs: clean up c... |
281 282 283 |
{ int ret = 0; struct extent_map *em; |
4e2f84e63 Btrfs: improve fs... |
284 |
bool prealloc = false; |
4d2c8f62f Btrfs: clean up c... |
285 286 287 288 289 290 291 292 |
write_lock(&tree->lock); em = lookup_extent_mapping(tree, start, len); WARN_ON(!em || em->start != start); if (!em) goto out; |
5dc562c54 Btrfs: turbo char... |
293 |
em->generation = gen; |
4d2c8f62f Btrfs: clean up c... |
294 |
clear_bit(EXTENT_FLAG_PINNED, &em->flags); |
4e2f84e63 Btrfs: improve fs... |
295 296 |
em->mod_start = em->start; em->mod_len = em->len; |
b11e234d2 Btrfs: do not mar... |
297 |
if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) { |
4e2f84e63 Btrfs: improve fs... |
298 |
prealloc = true; |
b11e234d2 Btrfs: do not mar... |
299 |
clear_bit(EXTENT_FLAG_FILLING, &em->flags); |
4e2f84e63 Btrfs: improve fs... |
300 |
} |
4d2c8f62f Btrfs: clean up c... |
301 302 |
try_merge_map(tree, em); |
4e2f84e63 Btrfs: improve fs... |
303 304 305 306 307 |
if (prealloc) { em->mod_start = em->start; em->mod_len = em->len; } |
a1ed835e1 Btrfs: Fix extent... |
308 309 310 311 312 313 |
free_extent_map(em); out: write_unlock(&tree->lock); return ret; } |
201a90389 Btrfs: do not all... |
314 315 316 |
void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em) { clear_bit(EXTENT_FLAG_LOGGING, &em->flags); |
cbc0e9287 Btrfs: remove unn... |
317 |
if (extent_map_in_tree(em)) |
222c81dc3 Btrfs: do not mer... |
318 |
try_merge_map(tree, em); |
201a90389 Btrfs: do not all... |
319 |
} |
176840b3a Btrfs: more effic... |
320 321 322 323 |
static inline void setup_extent_mapping(struct extent_map_tree *tree, struct extent_map *em, int modified) { |
490b54d6f btrfs: convert ex... |
324 |
refcount_inc(&em->refs); |
176840b3a Btrfs: more effic... |
325 326 327 328 329 330 331 332 |
em->mod_start = em->start; em->mod_len = em->len; if (modified) list_move(&em->list, &tree->modified_extents); else try_merge_map(tree, em); } |
1c11b63ef btrfs: replace pe... |
333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 |
static void extent_map_device_set_bits(struct extent_map *em, unsigned bits) { struct map_lookup *map = em->map_lookup; u64 stripe_size = em->orig_block_len; int i; for (i = 0; i < map->num_stripes; i++) { struct btrfs_bio_stripe *stripe = &map->stripes[i]; struct btrfs_device *device = stripe->dev; set_extent_bits_nowait(&device->alloc_state, stripe->physical, stripe->physical + stripe_size - 1, bits); } } static void extent_map_device_clear_bits(struct extent_map *em, unsigned bits) { struct map_lookup *map = em->map_lookup; u64 stripe_size = em->orig_block_len; int i; for (i = 0; i < map->num_stripes; i++) { struct btrfs_bio_stripe *stripe = &map->stripes[i]; struct btrfs_device *device = stripe->dev; __clear_extent_bit(&device->alloc_state, stripe->physical, stripe->physical + stripe_size - 1, bits, 0, 0, NULL, GFP_NOWAIT, NULL); } } |
9d2423c5c Btrfs: kerneldoc ... |
363 364 365 366 367 368 369 370 |
/** * 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... |
371 |
* reference dropped if the merge attempt was successful. |
a52d9a803 Btrfs: Extent bas... |
372 373 |
*/ int add_extent_mapping(struct extent_map_tree *tree, |
09a2a8f96 Btrfs: fix bad ex... |
374 |
struct extent_map *em, int modified) |
a52d9a803 Btrfs: Extent bas... |
375 376 |
{ int ret = 0; |
a52d9a803 Btrfs: Extent bas... |
377 |
|
d23ea3fa7 btrfs: assert ext... |
378 |
lockdep_assert_held_write(&tree->lock); |
32193c147 Btrfs: faster and... |
379 380 |
ret = tree_insert(&tree->map, em); if (ret) |
a52d9a803 Btrfs: Extent bas... |
381 |
goto out; |
32193c147 Btrfs: faster and... |
382 |
|
176840b3a Btrfs: more effic... |
383 |
setup_extent_mapping(tree, em, modified); |
8811133d8 btrfs: Optimize u... |
384 |
if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) { |
1c11b63ef btrfs: replace pe... |
385 |
extent_map_device_set_bits(em, CHUNK_ALLOCATED); |
8811133d8 btrfs: Optimize u... |
386 387 |
extent_map_device_clear_bits(em, CHUNK_TRIMMED); } |
a52d9a803 Btrfs: Extent bas... |
388 |
out: |
a52d9a803 Btrfs: Extent bas... |
389 390 |
return ret; } |
a52d9a803 Btrfs: Extent bas... |
391 |
|
48a3b6366 btrfs: make stati... |
392 393 394 |
static struct extent_map * __lookup_extent_mapping(struct extent_map_tree *tree, u64 start, u64 len, int strict) |
a52d9a803 Btrfs: Extent bas... |
395 396 397 |
{ struct extent_map *em; struct rb_node *rb_node; |
306929f36 btrfs: fix strang... |
398 399 400 |
struct rb_node *prev = NULL; struct rb_node *next = NULL; u64 end = range_end(start, len); |
07e1ce096 Btrfs: extent_map... |
401 |
rb_node = __tree_search(&tree->map.rb_root, start, &prev, &next); |
a52d9a803 Btrfs: Extent bas... |
402 |
if (!rb_node) { |
ed64f0665 Btrfs: clean up c... |
403 404 405 406 407 408 |
if (prev) rb_node = prev; else if (next) rb_node = next; else return NULL; |
a52d9a803 Btrfs: Extent bas... |
409 |
} |
ed64f0665 Btrfs: clean up c... |
410 |
|
a52d9a803 Btrfs: Extent bas... |
411 |
em = rb_entry(rb_node, struct extent_map, rb_node); |
d1310b2e0 Btrfs: Split the ... |
412 |
|
ed64f0665 Btrfs: clean up c... |
413 414 |
if (strict && !(end > em->start && start < extent_map_end(em))) return NULL; |
d1310b2e0 Btrfs: Split the ... |
415 |
|
490b54d6f btrfs: convert ex... |
416 |
refcount_inc(&em->refs); |
a52d9a803 Btrfs: Extent bas... |
417 418 |
return em; } |
a52d9a803 Btrfs: Extent bas... |
419 |
|
9d2423c5c Btrfs: kerneldoc ... |
420 |
/** |
ed64f0665 Btrfs: clean up c... |
421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 |
* 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... |
438 439 440 441 442 443 444 445 446 447 448 449 450 |
* 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... |
451 |
return __lookup_extent_mapping(tree, start, len, 0); |
b917b7c3b Btrfs: search for... |
452 453 454 |
} /** |
9d2423c5c Btrfs: kerneldoc ... |
455 456 |
* remove_extent_mapping - removes an extent_map from the extent tree * @tree: extent tree to remove from |
bb7ab3b92 btrfs: Fix misspe... |
457 |
* @em: extent map being removed |
9d2423c5c Btrfs: kerneldoc ... |
458 459 460 |
* * 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... |
461 |
*/ |
c1766dd78 btrfs: change rem... |
462 |
void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) |
a52d9a803 Btrfs: Extent bas... |
463 |
{ |
7f3c74fb8 Btrfs: Keep exten... |
464 |
WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); |
07e1ce096 Btrfs: extent_map... |
465 |
rb_erase_cached(&em->rb_node, &tree->map); |
ff44c6e36 Btrfs: do not hol... |
466 467 |
if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags)) list_del_init(&em->list); |
1c11b63ef btrfs: replace pe... |
468 469 |
if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) extent_map_device_clear_bits(em, CHUNK_ALLOCATED); |
cbc0e9287 Btrfs: remove unn... |
470 |
RB_CLEAR_NODE(&em->rb_node); |
a52d9a803 Btrfs: Extent bas... |
471 |
} |
176840b3a Btrfs: more effic... |
472 473 474 475 476 477 478 479 480 481 |
void replace_extent_mapping(struct extent_map_tree *tree, struct extent_map *cur, struct extent_map *new, int modified) { WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags)); ASSERT(extent_map_in_tree(cur)); if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags)) list_del_init(&cur->list); |
07e1ce096 Btrfs: extent_map... |
482 |
rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map); |
176840b3a Btrfs: more effic... |
483 484 485 486 |
RB_CLEAR_NODE(&cur->rb_node); setup_extent_mapping(tree, new, modified); } |
c04e61b5e Btrfs: move exten... |
487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 |
static struct extent_map *next_extent_map(struct extent_map *em) { struct rb_node *next; next = rb_next(&em->rb_node); if (!next) return NULL; return container_of(next, struct extent_map, rb_node); } static struct extent_map *prev_extent_map(struct extent_map *em) { struct rb_node *prev; prev = rb_prev(&em->rb_node); if (!prev) return NULL; return container_of(prev, struct extent_map, rb_node); } |
52042d8e8 btrfs: Fix typos ... |
507 508 |
/* * Helper for btrfs_get_extent. Given an existing extent in the tree, |
c04e61b5e Btrfs: move exten... |
509 510 511 512 |
* the existing extent is the nearest extent to map_start, * and an extent that you want to insert, deal with overlap and insert * the best fitted new extent into the tree. */ |
5f4791f4a Btrfs: noinline m... |
513 514 515 516 |
static noinline int merge_extent_mapping(struct extent_map_tree *em_tree, struct extent_map *existing, struct extent_map *em, u64 map_start) |
c04e61b5e Btrfs: move exten... |
517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 |
{ struct extent_map *prev; struct extent_map *next; u64 start; u64 end; u64 start_diff; BUG_ON(map_start < em->start || map_start >= extent_map_end(em)); if (existing->start > map_start) { next = existing; prev = prev_extent_map(next); } else { prev = existing; next = next_extent_map(prev); } start = prev ? extent_map_end(prev) : em->start; start = max_t(u64, start, em->start); end = next ? next->start : extent_map_end(em); end = min_t(u64, end, extent_map_end(em)); start_diff = start - em->start; em->start = start; em->len = end - start; if (em->block_start < EXTENT_MAP_LAST_BYTE && !test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) { em->block_start += start_diff; em->block_len = em->len; } return add_extent_mapping(em_tree, em, 0); } /** * btrfs_add_extent_mapping - add extent mapping into em_tree |
f46b24c94 btrfs: use fs_inf... |
551 |
* @fs_info - used for tracepoint |
c04e61b5e Btrfs: move exten... |
552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 |
* @em_tree - the extent tree into which we want to insert the extent mapping * @em_in - extent we are inserting * @start - start of the logical range btrfs_get_extent() is requesting * @len - length of the logical range btrfs_get_extent() is requesting * * Note that @em_in's range may be different from [start, start+len), * but they must be overlapped. * * Insert @em_in into @em_tree. In case there is an overlapping range, handle * the -EEXIST by either: * a) Returning the existing extent in @em_in if @start is within the * existing em. * b) Merge the existing extent with @em_in passed in. * * Return 0 on success, otherwise -EEXIST. * */ |
f46b24c94 btrfs: use fs_inf... |
569 570 |
int btrfs_add_extent_mapping(struct btrfs_fs_info *fs_info, struct extent_map_tree *em_tree, |
c04e61b5e Btrfs: move exten... |
571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 |
struct extent_map **em_in, u64 start, u64 len) { int ret; struct extent_map *em = *em_in; ret = add_extent_mapping(em_tree, em, 0); /* it is possible that someone inserted the extent into the tree * while we had the lock dropped. It is also possible that * an overlapping map exists in the tree */ if (ret == -EEXIST) { struct extent_map *existing; ret = 0; existing = search_extent_mapping(em_tree, start, len); |
393da9181 Btrfs: add tracep... |
587 |
|
f46b24c94 btrfs: use fs_inf... |
588 |
trace_btrfs_handle_em_exist(fs_info, existing, em, start, len); |
393da9181 Btrfs: add tracep... |
589 |
|
c04e61b5e Btrfs: move exten... |
590 591 592 593 594 595 596 597 598 599 |
/* * existing will always be non-NULL, since there must be * extent causing the -EEXIST. */ if (start >= existing->start && start < extent_map_end(existing)) { free_extent_map(em); *em_in = existing; ret = 0; } else { |
9a7e10e7b Btrfs: add WARN_O... |
600 601 |
u64 orig_start = em->start; u64 orig_len = em->len; |
c04e61b5e Btrfs: move exten... |
602 603 604 605 606 607 |
/* * The existing extent map is the one nearest to * the [start, start + len) range which overlaps */ ret = merge_extent_mapping(em_tree, existing, em, start); |
c04e61b5e Btrfs: move exten... |
608 609 610 |
if (ret) { free_extent_map(em); *em_in = NULL; |
9a7e10e7b Btrfs: add WARN_O... |
611 612 613 614 615 |
WARN_ONCE(ret, "unexpected error %d: merge existing(start %llu len %llu) with em(start %llu len %llu) ", ret, existing->start, existing->len, orig_start, orig_len); |
c04e61b5e Btrfs: move exten... |
616 |
} |
9a7e10e7b Btrfs: add WARN_O... |
617 |
free_extent_map(existing); |
c04e61b5e Btrfs: move exten... |
618 619 620 621 622 623 |
} } ASSERT(ret == 0 || ret == -EEXIST); return ret; } |