Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0
2 :
3 : #include <linux/slab.h>
4 : #include <trace/events/btrfs.h>
5 : #include "messages.h"
6 : #include "ctree.h"
7 : #include "extent-io-tree.h"
8 : #include "btrfs_inode.h"
9 : #include "misc.h"
10 :
11 : static struct kmem_cache *extent_state_cache;
12 :
13 : static inline bool extent_state_in_tree(const struct extent_state *state)
14 : {
15 665085829 : return !RB_EMPTY_NODE(&state->rb_node);
16 : }
17 :
18 : #ifdef CONFIG_BTRFS_DEBUG
19 : static LIST_HEAD(states);
20 : static DEFINE_SPINLOCK(leak_lock);
21 :
22 : static inline void btrfs_leak_debug_add_state(struct extent_state *state)
23 : {
24 : unsigned long flags;
25 :
26 : spin_lock_irqsave(&leak_lock, flags);
27 : list_add(&state->leak_list, &states);
28 : spin_unlock_irqrestore(&leak_lock, flags);
29 : }
30 :
31 : static inline void btrfs_leak_debug_del_state(struct extent_state *state)
32 : {
33 : unsigned long flags;
34 :
35 : spin_lock_irqsave(&leak_lock, flags);
36 : list_del(&state->leak_list);
37 : spin_unlock_irqrestore(&leak_lock, flags);
38 : }
39 :
40 : static inline void btrfs_extent_state_leak_debug_check(void)
41 : {
42 : struct extent_state *state;
43 :
44 : while (!list_empty(&states)) {
45 : state = list_entry(states.next, struct extent_state, leak_list);
46 : pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n",
47 : state->start, state->end, state->state,
48 : extent_state_in_tree(state),
49 : refcount_read(&state->refs));
50 : list_del(&state->leak_list);
51 : kmem_cache_free(extent_state_cache, state);
52 : }
53 : }
54 :
55 : #define btrfs_debug_check_extent_io_range(tree, start, end) \
56 : __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
57 : static inline void __btrfs_debug_check_extent_io_range(const char *caller,
58 : struct extent_io_tree *tree,
59 : u64 start, u64 end)
60 : {
61 : struct btrfs_inode *inode = tree->inode;
62 : u64 isize;
63 :
64 : if (!inode)
65 : return;
66 :
67 : isize = i_size_read(&inode->vfs_inode);
68 : if (end >= PAGE_SIZE && (end % 2) == 0 && end != isize - 1) {
69 : btrfs_debug_rl(inode->root->fs_info,
70 : "%s: ino %llu isize %llu odd range [%llu,%llu]",
71 : caller, btrfs_ino(inode), isize, start, end);
72 : }
73 : }
74 : #else
75 : #define btrfs_leak_debug_add_state(state) do {} while (0)
76 : #define btrfs_leak_debug_del_state(state) do {} while (0)
77 : #define btrfs_extent_state_leak_debug_check() do {} while (0)
78 : #define btrfs_debug_check_extent_io_range(c, s, e) do {} while (0)
79 : #endif
80 :
81 : /*
82 : * For the file_extent_tree, we want to hold the inode lock when we lookup and
83 : * update the disk_i_size, but lockdep will complain because our io_tree we hold
84 : * the tree lock and get the inode lock when setting delalloc. These two things
85 : * are unrelated, so make a class for the file_extent_tree so we don't get the
86 : * two locking patterns mixed up.
87 : */
88 : static struct lock_class_key file_extent_tree_class;
89 :
90 : struct tree_entry {
91 : u64 start;
92 : u64 end;
93 : struct rb_node rb_node;
94 : };
95 :
96 8261269 : void extent_io_tree_init(struct btrfs_fs_info *fs_info,
97 : struct extent_io_tree *tree, unsigned int owner)
98 : {
99 8261269 : tree->fs_info = fs_info;
100 8261269 : tree->state = RB_ROOT;
101 8261269 : spin_lock_init(&tree->lock);
102 8256715 : tree->inode = NULL;
103 8256715 : tree->owner = owner;
104 8256715 : if (owner == IO_TREE_INODE_FILE_EXTENT)
105 8256715 : lockdep_set_class(&tree->lock, &file_extent_tree_class);
106 8256715 : }
107 :
108 1221648 : void extent_io_tree_release(struct extent_io_tree *tree)
109 : {
110 1221648 : spin_lock(&tree->lock);
111 : /*
112 : * Do a single barrier for the waitqueue_active check here, the state
113 : * of the waitqueue should not change once extent_io_tree_release is
114 : * called.
115 : */
116 1221648 : smp_mb();
117 1221679 : while (!RB_EMPTY_ROOT(&tree->state)) {
118 31 : struct rb_node *node;
119 31 : struct extent_state *state;
120 :
121 31 : node = rb_first(&tree->state);
122 31 : state = rb_entry(node, struct extent_state, rb_node);
123 31 : rb_erase(&state->rb_node, &tree->state);
124 31 : RB_CLEAR_NODE(&state->rb_node);
125 : /*
126 : * btree io trees aren't supposed to have tasks waiting for
127 : * changes in the flags of extent states ever.
128 : */
129 62 : ASSERT(!waitqueue_active(&state->wq));
130 31 : free_extent_state(state);
131 :
132 31 : cond_resched_lock(&tree->lock);
133 : }
134 1221648 : spin_unlock(&tree->lock);
135 1221648 : }
136 :
137 408821427 : static struct extent_state *alloc_extent_state(gfp_t mask)
138 : {
139 408821427 : struct extent_state *state;
140 :
141 : /*
142 : * The given mask might be not appropriate for the slab allocator,
143 : * drop the unsupported bits
144 : */
145 408821427 : mask &= ~(__GFP_DMA32|__GFP_HIGHMEM);
146 408821427 : state = kmem_cache_alloc(extent_state_cache, mask);
147 408914300 : if (!state)
148 : return state;
149 408914300 : state->state = 0;
150 408914300 : RB_CLEAR_NODE(&state->rb_node);
151 408914300 : btrfs_leak_debug_add_state(state);
152 408914300 : refcount_set(&state->refs, 1);
153 408914300 : init_waitqueue_head(&state->wq);
154 408881141 : trace_alloc_extent_state(state, mask, _RET_IP_);
155 409034742 : return state;
156 : }
157 :
158 : static struct extent_state *alloc_extent_state_atomic(struct extent_state *prealloc)
159 : {
160 157447210 : if (!prealloc)
161 2987 : prealloc = alloc_extent_state(GFP_ATOMIC);
162 :
163 157447210 : return prealloc;
164 : }
165 :
166 484680308 : void free_extent_state(struct extent_state *state)
167 : {
168 484680308 : if (!state)
169 : return;
170 429065690 : if (refcount_dec_and_test(&state->refs)) {
171 409378784 : WARN_ON(extent_state_in_tree(state));
172 409378784 : btrfs_leak_debug_del_state(state);
173 409378784 : trace_free_extent_state(state, _RET_IP_);
174 409319560 : kmem_cache_free(extent_state_cache, state);
175 : }
176 : }
177 :
178 326174372 : static int add_extent_changeset(struct extent_state *state, u32 bits,
179 : struct extent_changeset *changeset,
180 : int set)
181 : {
182 326174372 : int ret;
183 :
184 326174372 : if (!changeset)
185 : return 0;
186 2727799 : if (set && (state->state & bits) == bits)
187 : return 0;
188 2727643 : if (!set && (state->state & bits) == 0)
189 : return 0;
190 2727643 : changeset->bytes_changed += state->end - state->start + 1;
191 2727643 : ret = ulist_add(&changeset->range_changed, state->start, state->end,
192 : GFP_ATOMIC);
193 2727643 : return ret;
194 : }
195 :
196 : static inline struct extent_state *next_state(struct extent_state *state)
197 : {
198 385414393 : struct rb_node *next = rb_next(&state->rb_node);
199 :
200 385427660 : if (next)
201 91514653 : return rb_entry(next, struct extent_state, rb_node);
202 : else
203 : return NULL;
204 : }
205 :
206 : static inline struct extent_state *prev_state(struct extent_state *state)
207 : {
208 69450393 : struct rb_node *next = rb_prev(&state->rb_node);
209 :
210 69366152 : if (next)
211 2 : return rb_entry(next, struct extent_state, rb_node);
212 : else
213 : return NULL;
214 : }
215 :
216 : /*
217 : * Search @tree for an entry that contains @offset. Such entry would have
218 : * entry->start <= offset && entry->end >= offset.
219 : *
220 : * @tree: the tree to search
221 : * @offset: offset that should fall within an entry in @tree
222 : * @node_ret: pointer where new node should be anchored (used when inserting an
223 : * entry in the tree)
224 : * @parent_ret: points to entry which would have been the parent of the entry,
225 : * containing @offset
226 : *
227 : * Return a pointer to the entry that contains @offset byte address and don't change
228 : * @node_ret and @parent_ret.
229 : *
230 : * If no such entry exists, return pointer to entry that ends before @offset
231 : * and fill parameters @node_ret and @parent_ret, ie. does not return NULL.
232 : */
233 372346661 : static inline struct extent_state *tree_search_for_insert(struct extent_io_tree *tree,
234 : u64 offset,
235 : struct rb_node ***node_ret,
236 : struct rb_node **parent_ret)
237 : {
238 372346661 : struct rb_root *root = &tree->state;
239 372346661 : struct rb_node **node = &root->rb_node;
240 372346661 : struct rb_node *prev = NULL;
241 372346661 : struct extent_state *entry = NULL;
242 :
243 775883826 : while (*node) {
244 520118057 : prev = *node;
245 520118057 : entry = rb_entry(prev, struct extent_state, rb_node);
246 :
247 520118057 : if (offset < entry->start)
248 129231581 : node = &(*node)->rb_left;
249 390886476 : else if (offset > entry->end)
250 274305584 : node = &(*node)->rb_right;
251 : else
252 116580892 : return entry;
253 : }
254 :
255 255765769 : if (node_ret)
256 108163768 : *node_ret = node;
257 255765769 : if (parent_ret)
258 108164937 : *parent_ret = prev;
259 :
260 : /* Search neighbors until we find the first one past the end */
261 268215633 : while (entry && offset > entry->end)
262 85787854 : entry = next_state(entry);
263 :
264 : return entry;
265 : }
266 :
267 : /*
268 : * Search offset in the tree or fill neighbor rbtree node pointers.
269 : *
270 : * @tree: the tree to search
271 : * @offset: offset that should fall within an entry in @tree
272 : * @next_ret: pointer to the first entry whose range ends after @offset
273 : * @prev_ret: pointer to the first entry whose range begins before @offset
274 : *
275 : * Return a pointer to the entry that contains @offset byte address. If no
276 : * such entry exists, then return NULL and fill @prev_ret and @next_ret.
277 : * Otherwise return the found entry and other pointers are left untouched.
278 : */
279 5373 : static struct extent_state *tree_search_prev_next(struct extent_io_tree *tree,
280 : u64 offset,
281 : struct extent_state **prev_ret,
282 : struct extent_state **next_ret)
283 : {
284 5373 : struct rb_root *root = &tree->state;
285 5373 : struct rb_node **node = &root->rb_node;
286 5373 : struct extent_state *orig_prev;
287 5373 : struct extent_state *entry = NULL;
288 :
289 5373 : ASSERT(prev_ret);
290 5373 : ASSERT(next_ret);
291 :
292 12310 : while (*node) {
293 11296 : entry = rb_entry(*node, struct extent_state, rb_node);
294 :
295 11296 : if (offset < entry->start)
296 2916 : node = &(*node)->rb_left;
297 8380 : else if (offset > entry->end)
298 4021 : node = &(*node)->rb_right;
299 : else
300 4359 : return entry;
301 : }
302 :
303 : orig_prev = entry;
304 1017 : while (entry && offset > entry->end)
305 1000 : entry = next_state(entry);
306 1014 : *next_ret = entry;
307 1014 : entry = orig_prev;
308 :
309 1016 : while (entry && offset < entry->start)
310 14 : entry = prev_state(entry);
311 1014 : *prev_ret = entry;
312 :
313 1014 : return NULL;
314 : }
315 :
316 : /*
317 : * Inexact rb-tree search, return the next entry if @offset is not found
318 : */
319 : static inline struct extent_state *tree_search(struct extent_io_tree *tree, u64 offset)
320 : {
321 236619895 : return tree_search_for_insert(tree, offset, NULL, NULL);
322 : }
323 :
324 0 : static void extent_io_tree_panic(struct extent_io_tree *tree, int err)
325 : {
326 0 : btrfs_panic(tree->fs_info, err,
327 : "locking error: extent tree was modified by another thread while locked");
328 : }
329 :
330 : /*
331 : * Utility function to look for merge candidates inside a given range. Any
332 : * extents with matching state are merged together into a single extent in the
333 : * tree. Extents with EXTENT_IO in their state field are not merged because
334 : * the end_io handlers need to be able to do operations on them without
335 : * sleeping (or doing allocations/splits).
336 : *
337 : * This should be called with the tree lock held.
338 : */
339 226552070 : static void merge_state(struct extent_io_tree *tree, struct extent_state *state)
340 : {
341 226552070 : struct extent_state *other;
342 :
343 226552070 : if (state->state & (EXTENT_LOCKED | EXTENT_BOUNDARY))
344 : return;
345 :
346 69449558 : other = prev_state(state);
347 62205745 : if (other && other->end == state->start - 1 &&
348 53874831 : other->state == state->state) {
349 51660344 : if (tree->inode)
350 35759753 : btrfs_merge_delalloc_extent(tree->inode, state, other);
351 51754074 : state->start = other->start;
352 51754074 : rb_erase(&other->rb_node, &tree->state);
353 51748302 : RB_CLEAR_NODE(&other->rb_node);
354 51748302 : free_extent_state(other);
355 : }
356 69464743 : other = next_state(state);
357 20453128 : if (other && other->start == state->end + 1 &&
358 9685004 : other->state == state->state) {
359 8184786 : if (tree->inode)
360 7705625 : btrfs_merge_delalloc_extent(tree->inode, state, other);
361 8184786 : state->end = other->end;
362 8184786 : rb_erase(&other->rb_node, &tree->state);
363 8184785 : RB_CLEAR_NODE(&other->rb_node);
364 8184785 : free_extent_state(other);
365 : }
366 : }
367 :
368 179859926 : static void set_state_bits(struct extent_io_tree *tree,
369 : struct extent_state *state,
370 : u32 bits, struct extent_changeset *changeset)
371 : {
372 179859926 : u32 bits_to_set = bits & ~EXTENT_CTLBITS;
373 179859926 : int ret;
374 :
375 179859926 : if (tree->inode)
376 154007903 : btrfs_set_delalloc_extent(tree->inode, state, bits);
377 :
378 179898847 : ret = add_extent_changeset(state, bits_to_set, changeset, 1);
379 179862884 : BUG_ON(ret < 0);
380 179862884 : state->state |= bits_to_set;
381 179862884 : }
382 :
383 : /*
384 : * Insert an extent_state struct into the tree. 'bits' are set on the
385 : * struct before it is inserted.
386 : *
387 : * This may return -EEXIST if the extent is already there, in which case the
388 : * state struct is freed.
389 : *
390 : * The tree lock is not taken internally. This is a utility function and
391 : * probably isn't what you want to call (see set/clear_extent_bit).
392 : */
393 18555305 : static int insert_state(struct extent_io_tree *tree,
394 : struct extent_state *state,
395 : u32 bits, struct extent_changeset *changeset)
396 : {
397 18555305 : struct rb_node **node;
398 18555305 : struct rb_node *parent = NULL;
399 18555305 : const u64 end = state->end;
400 :
401 18555305 : set_state_bits(tree, state, bits, changeset);
402 :
403 18555333 : node = &tree->state.rb_node;
404 107498197 : while (*node) {
405 88942864 : struct extent_state *entry;
406 :
407 88942864 : parent = *node;
408 88942864 : entry = rb_entry(parent, struct extent_state, rb_node);
409 :
410 88942864 : if (end < entry->start) {
411 36236370 : node = &(*node)->rb_left;
412 52706494 : } else if (end > entry->end) {
413 52706494 : node = &(*node)->rb_right;
414 : } else {
415 0 : btrfs_err(tree->fs_info,
416 : "found node %llu %llu on insert of %llu %llu",
417 : entry->start, entry->end, state->start, end);
418 0 : return -EEXIST;
419 : }
420 : }
421 :
422 18555333 : rb_link_node(&state->rb_node, parent, node);
423 18555333 : rb_insert_color(&state->rb_node, &tree->state);
424 :
425 18555342 : merge_state(tree, state);
426 18555342 : return 0;
427 : }
428 :
429 : /*
430 : * Insert state to @tree to the location given by @node and @parent.
431 : */
432 89582842 : static void insert_state_fast(struct extent_io_tree *tree,
433 : struct extent_state *state, struct rb_node **node,
434 : struct rb_node *parent, unsigned bits,
435 : struct extent_changeset *changeset)
436 : {
437 89582842 : set_state_bits(tree, state, bits, changeset);
438 89551369 : rb_link_node(&state->rb_node, parent, node);
439 89551369 : rb_insert_color(&state->rb_node, &tree->state);
440 89560370 : merge_state(tree, state);
441 89541930 : }
442 :
443 : /*
444 : * Split a given extent state struct in two, inserting the preallocated
445 : * struct 'prealloc' as the newly created second half. 'split' indicates an
446 : * offset inside 'orig' where it should be split.
447 : *
448 : * Before calling,
449 : * the tree has 'orig' at [orig->start, orig->end]. After calling, there
450 : * are two extent state structs in the tree:
451 : * prealloc: [orig->start, split - 1]
452 : * orig: [ split, orig->end ]
453 : *
454 : * The tree locks are not taken by this function. They need to be held
455 : * by the caller.
456 : */
457 49209244 : static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
458 : struct extent_state *prealloc, u64 split)
459 : {
460 49209244 : struct rb_node *parent = NULL;
461 49209244 : struct rb_node **node;
462 :
463 49209244 : if (tree->inode)
464 49149995 : btrfs_split_delalloc_extent(tree->inode, orig, split);
465 :
466 49234101 : prealloc->start = orig->start;
467 49234101 : prealloc->end = split - 1;
468 49234101 : prealloc->state = orig->state;
469 49234101 : orig->start = split;
470 :
471 49234101 : parent = &orig->rb_node;
472 49234101 : node = &parent;
473 113535166 : while (*node) {
474 64301065 : struct extent_state *entry;
475 :
476 64301065 : parent = *node;
477 64301065 : entry = rb_entry(parent, struct extent_state, rb_node);
478 :
479 64301065 : if (prealloc->end < entry->start) {
480 49253735 : node = &(*node)->rb_left;
481 15047330 : } else if (prealloc->end > entry->end) {
482 15047330 : node = &(*node)->rb_right;
483 : } else {
484 0 : free_extent_state(prealloc);
485 0 : return -EEXIST;
486 : }
487 : }
488 :
489 49234101 : rb_link_node(&prealloc->rb_node, parent, node);
490 49234101 : rb_insert_color(&prealloc->rb_node, &tree->state);
491 :
492 49234101 : return 0;
493 : }
494 :
495 : /*
496 : * Utility function to clear some bits in an extent state struct. It will
497 : * optionally wake up anyone waiting on this state (wake == 1).
498 : *
499 : * If no bits are set on the state struct after clearing things, the
500 : * struct is freed and removed from the tree
501 : */
502 146438484 : static struct extent_state *clear_state_bit(struct extent_io_tree *tree,
503 : struct extent_state *state,
504 : u32 bits, int wake,
505 : struct extent_changeset *changeset)
506 : {
507 146438484 : struct extent_state *next;
508 146438484 : u32 bits_to_clear = bits & ~EXTENT_CTLBITS;
509 146438484 : int ret;
510 :
511 146438484 : if (tree->inode)
512 136938759 : btrfs_clear_delalloc_extent(tree->inode, state, bits);
513 :
514 146387885 : ret = add_extent_changeset(state, bits_to_clear, changeset, 0);
515 146395537 : BUG_ON(ret < 0);
516 146395537 : state->state &= ~bits_to_clear;
517 146395537 : if (wake)
518 120486234 : wake_up(&state->wq);
519 146432065 : if (state->state == 0) {
520 97495151 : next = next_state(state);
521 97491233 : if (extent_state_in_tree(state)) {
522 97491233 : rb_erase(&state->rb_node, &tree->state);
523 97501966 : RB_CLEAR_NODE(&state->rb_node);
524 97501966 : free_extent_state(state);
525 : } else {
526 0 : WARN_ON(1);
527 : }
528 : } else {
529 48936914 : merge_state(tree, state);
530 48988397 : next = next_state(state);
531 : }
532 146495226 : return next;
533 : }
534 :
535 : /*
536 : * Detect if extent bits request NOWAIT semantics and set the gfp mask accordingly,
537 : * unset the EXTENT_NOWAIT bit.
538 : */
539 : static void set_gfp_mask_from_bits(u32 *bits, gfp_t *mask)
540 : {
541 399752986 : *mask = (*bits & EXTENT_NOWAIT ? GFP_NOWAIT : GFP_NOFS);
542 399752986 : *bits &= EXTENT_NOWAIT - 1;
543 : }
544 :
545 : /*
546 : * Clear some bits on a range in the tree. This may require splitting or
547 : * inserting elements in the tree, so the gfp mask is used to indicate which
548 : * allocations or sleeping are allowed.
549 : *
550 : * Pass 'wake' == 1 to kick any sleepers, and 'delete' == 1 to remove the given
551 : * range from the tree regardless of state (ie for truncate).
552 : *
553 : * The range [start, end] is inclusive.
554 : *
555 : * This takes the tree lock, and returns 0 on success and < 0 on error.
556 : */
557 222928497 : int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
558 : u32 bits, struct extent_state **cached_state,
559 : struct extent_changeset *changeset)
560 : {
561 222928497 : struct extent_state *state;
562 222928497 : struct extent_state *cached;
563 222928497 : struct extent_state *prealloc = NULL;
564 222928497 : u64 last_end;
565 222928497 : int err;
566 222928497 : int clear = 0;
567 222928497 : int wake;
568 222928497 : int delete = (bits & EXTENT_CLEAR_ALL_BITS);
569 222928497 : gfp_t mask;
570 :
571 222928497 : set_gfp_mask_from_bits(&bits, &mask);
572 222928497 : btrfs_debug_check_extent_io_range(tree, start, end);
573 222928497 : trace_btrfs_clear_extent_bit(tree, start, end - start + 1, bits);
574 :
575 222747999 : if (delete)
576 32067439 : bits |= ~EXTENT_CTLBITS;
577 :
578 222747999 : if (bits & EXTENT_DELALLOC)
579 127899513 : bits |= EXTENT_NORESERVE;
580 :
581 222747999 : wake = (bits & EXTENT_LOCKED) ? 1 : 0;
582 222747999 : if (bits & (EXTENT_LOCKED | EXTENT_BOUNDARY))
583 169435441 : clear = 1;
584 222747999 : again:
585 222904996 : if (!prealloc) {
586 : /*
587 : * Don't care for allocation failure here because we might end
588 : * up not needing the pre-allocated extent state at all, which
589 : * is the case if we only have in the tree extent states that
590 : * cover our input range and don't cover too any other range.
591 : * If we end up needing a new extent state we allocate it later.
592 : */
593 222897197 : prealloc = alloc_extent_state(mask);
594 : }
595 :
596 223107355 : spin_lock(&tree->lock);
597 223297243 : if (cached_state) {
598 118362842 : cached = *cached_state;
599 :
600 118362842 : if (clear) {
601 71928728 : *cached_state = NULL;
602 71928728 : cached_state = NULL;
603 : }
604 :
605 118362842 : if (cached && extent_state_in_tree(cached) &&
606 103714397 : cached->start <= start && cached->end > start) {
607 103565000 : if (clear)
608 69995557 : refcount_dec(&cached->refs);
609 103595063 : state = cached;
610 103595063 : goto hit_next;
611 : }
612 14797842 : if (clear)
613 1895322 : free_extent_state(cached);
614 : }
615 :
616 : /* This search will find the extents that end after our range starts. */
617 119732201 : state = tree_search(tree, start);
618 119676609 : if (!state)
619 59357565 : goto out;
620 163914107 : hit_next:
621 165701206 : if (state->start > end)
622 7942890 : goto out;
623 157758316 : WARN_ON(state->end < start);
624 157758316 : last_end = state->end;
625 :
626 : /* The state doesn't have the wanted bits, go ahead. */
627 157758316 : if (!(state->state & bits)) {
628 13373992 : state = next_state(state);
629 13368194 : goto next;
630 : }
631 :
632 : /*
633 : * | ---- desired range ---- |
634 : * | state | or
635 : * | ------------- state -------------- |
636 : *
637 : * We need to split the extent we found, and may flip bits on second
638 : * half.
639 : *
640 : * If the extent we found extends past our range, we just split and
641 : * search again. It'll get split again the next time though.
642 : *
643 : * If the extent we found is inside our range, we clear the desired bit
644 : * on it.
645 : */
646 :
647 144384324 : if (state->start < start) {
648 500455 : prealloc = alloc_extent_state_atomic(prealloc);
649 500455 : if (!prealloc)
650 0 : goto search_again;
651 500455 : err = split_state(tree, state, prealloc, start);
652 500240 : if (err)
653 0 : extent_io_tree_panic(tree, err);
654 :
655 500240 : prealloc = NULL;
656 500240 : if (err)
657 : goto out;
658 500240 : if (state->end <= end) {
659 354540 : state = clear_state_bit(tree, state, bits, wake, changeset);
660 354406 : goto next;
661 : }
662 145700 : goto search_again;
663 : }
664 : /*
665 : * | ---- desired range ---- |
666 : * | state |
667 : * We need to split the extent, and clear the bit on the first half.
668 : */
669 143883869 : if (state->start <= end && state->end > end) {
670 25399380 : prealloc = alloc_extent_state_atomic(prealloc);
671 25399380 : if (!prealloc)
672 0 : goto search_again;
673 25399380 : err = split_state(tree, state, prealloc, end + 1);
674 25397596 : if (err)
675 0 : extent_io_tree_panic(tree, err);
676 :
677 25397596 : if (wake)
678 24580609 : wake_up(&state->wq);
679 :
680 25400439 : clear_state_bit(tree, prealloc, bits, wake, changeset);
681 :
682 25400860 : prealloc = NULL;
683 25400860 : goto out;
684 : }
685 :
686 118484489 : state = clear_state_bit(tree, state, bits, wake, changeset);
687 132113673 : next:
688 132113673 : if (last_end == (u64)-1)
689 269719 : goto out;
690 131843954 : start = last_end + 1;
691 131843954 : if (start <= end && state && !need_resched())
692 1787099 : goto hit_next;
693 :
694 130056855 : search_again:
695 130202555 : if (start > end)
696 130015759 : goto out;
697 186796 : spin_unlock(&tree->lock);
698 156997 : if (gfpflags_allow_blocking(mask))
699 155587 : cond_resched();
700 156997 : goto again;
701 :
702 222986793 : out:
703 222986793 : spin_unlock(&tree->lock);
704 223174818 : if (prealloc)
705 197420322 : free_extent_state(prealloc);
706 :
707 223143027 : return 0;
708 :
709 : }
710 :
711 393534 : static void wait_on_state(struct extent_io_tree *tree,
712 : struct extent_state *state)
713 : __releases(tree->lock)
714 : __acquires(tree->lock)
715 : {
716 393534 : DEFINE_WAIT(wait);
717 393534 : prepare_to_wait(&state->wq, &wait, TASK_UNINTERRUPTIBLE);
718 393534 : spin_unlock(&tree->lock);
719 393532 : schedule();
720 392722 : spin_lock(&tree->lock);
721 393534 : finish_wait(&state->wq, &wait);
722 393534 : }
723 :
724 : /*
725 : * Wait for one or more bits to clear on a range in the state tree.
726 : * The range [start, end] is inclusive.
727 : * The tree lock is taken by this function
728 : */
729 90950 : void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
730 : struct extent_state **cached_state)
731 : {
732 90950 : struct extent_state *state;
733 :
734 90950 : btrfs_debug_check_extent_io_range(tree, start, end);
735 :
736 90950 : spin_lock(&tree->lock);
737 484611 : again:
738 : /*
739 : * Maintain cached_state, as we may not remove it from the tree if there
740 : * are more bits than the bits we're waiting on set on this state.
741 : */
742 484611 : if (cached_state && *cached_state) {
743 484611 : state = *cached_state;
744 484611 : if (extent_state_in_tree(state) &&
745 91165 : state->start <= start && start < state->end)
746 90682 : goto process_node;
747 : }
748 393937 : while (1) {
749 : /*
750 : * This search will find all the extents that end after our
751 : * range starts.
752 : */
753 393937 : state = tree_search(tree, start);
754 : process_node:
755 484627 : if (!state)
756 : break;
757 463767 : if (state->start > end)
758 66192 : goto out;
759 :
760 397575 : if (state->state & bits) {
761 393534 : start = state->start;
762 393534 : refcount_inc(&state->refs);
763 393534 : wait_on_state(tree, state);
764 393534 : free_extent_state(state);
765 393534 : goto again;
766 : }
767 4041 : start = state->end + 1;
768 :
769 4041 : if (start > end)
770 : break;
771 :
772 20 : if (!cond_resched_lock(&tree->lock)) {
773 12 : state = next_state(state);
774 12 : goto process_node;
775 : }
776 : }
777 24881 : out:
778 : /* This state is no longer useful, clear it and free it up. */
779 91077 : if (cached_state && *cached_state) {
780 91077 : state = *cached_state;
781 91077 : *cached_state = NULL;
782 91077 : free_extent_state(state);
783 : }
784 91077 : spin_unlock(&tree->lock);
785 91077 : }
786 :
787 189070036 : static void cache_state_if_flags(struct extent_state *state,
788 : struct extent_state **cached_ptr,
789 : unsigned flags)
790 : {
791 189070036 : if (cached_ptr && !(*cached_ptr)) {
792 109218822 : if (!flags || (state->state & flags)) {
793 96270565 : *cached_ptr = state;
794 96270565 : refcount_inc(&state->refs);
795 : }
796 : }
797 189166449 : }
798 :
799 : static void cache_state(struct extent_state *state,
800 : struct extent_state **cached_ptr)
801 : {
802 180026741 : return cache_state_if_flags(state, cached_ptr,
803 : EXTENT_LOCKED | EXTENT_BOUNDARY);
804 : }
805 :
806 : /*
807 : * Find the first state struct with 'bits' set after 'start', and return it.
808 : * tree->lock must be held. NULL will returned if nothing was found after
809 : * 'start'.
810 : */
811 11975995 : static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree,
812 : u64 start, u32 bits)
813 : {
814 11975995 : struct extent_state *state;
815 :
816 : /*
817 : * This search will find all the extents that end after our range
818 : * starts.
819 : */
820 11975995 : state = tree_search(tree, start);
821 11976138 : while (state) {
822 9111717 : if (state->end >= start && (state->state & bits))
823 9109930 : return state;
824 1787 : state = next_state(state);
825 : }
826 : return NULL;
827 : }
828 :
829 : /*
830 : * Find the first offset in the io tree with one or more @bits set.
831 : *
832 : * Note: If there are multiple bits set in @bits, any of them will match.
833 : *
834 : * Return 0 if we find something, and update @start_ret and @end_ret.
835 : * Return 1 if we found nothing.
836 : */
837 11975570 : int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
838 : u64 *start_ret, u64 *end_ret, u32 bits,
839 : struct extent_state **cached_state)
840 : {
841 11975570 : struct extent_state *state;
842 11975570 : int ret = 1;
843 :
844 11975570 : spin_lock(&tree->lock);
845 11975602 : if (cached_state && *cached_state) {
846 0 : state = *cached_state;
847 0 : if (state->end == start - 1 && extent_state_in_tree(state)) {
848 0 : while ((state = next_state(state)) != NULL) {
849 0 : if (state->state & bits)
850 0 : goto got_it;
851 : }
852 0 : free_extent_state(*cached_state);
853 0 : *cached_state = NULL;
854 0 : goto out;
855 : }
856 0 : free_extent_state(*cached_state);
857 0 : *cached_state = NULL;
858 : }
859 :
860 11975602 : state = find_first_extent_bit_state(tree, start, bits);
861 11975548 : got_it:
862 11975548 : if (state) {
863 9109539 : cache_state_if_flags(state, cached_state, 0);
864 9109591 : *start_ret = state->start;
865 9109591 : *end_ret = state->end;
866 9109591 : ret = 0;
867 : }
868 2866009 : out:
869 11975600 : spin_unlock(&tree->lock);
870 11975601 : return ret;
871 : }
872 :
873 : /*
874 : * Find a contiguous area of bits
875 : *
876 : * @tree: io tree to check
877 : * @start: offset to start the search from
878 : * @start_ret: the first offset we found with the bits set
879 : * @end_ret: the final contiguous range of the bits that were set
880 : * @bits: bits to look for
881 : *
882 : * set_extent_bit and clear_extent_bit can temporarily split contiguous ranges
883 : * to set bits appropriately, and then merge them again. During this time it
884 : * will drop the tree->lock, so use this helper if you want to find the actual
885 : * contiguous area for given bits. We will search to the first bit we find, and
886 : * then walk down the tree until we find a non-contiguous area. The area
887 : * returned will be the full contiguous area with the bits set.
888 : */
889 400 : int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
890 : u64 *start_ret, u64 *end_ret, u32 bits)
891 : {
892 400 : struct extent_state *state;
893 400 : int ret = 1;
894 :
895 400 : spin_lock(&tree->lock);
896 400 : state = find_first_extent_bit_state(tree, start, bits);
897 400 : if (state) {
898 395 : *start_ret = state->start;
899 395 : *end_ret = state->end;
900 495 : while ((state = next_state(state)) != NULL) {
901 100 : if (state->start > (*end_ret + 1))
902 : break;
903 0 : *end_ret = state->end;
904 : }
905 : ret = 0;
906 : }
907 400 : spin_unlock(&tree->lock);
908 400 : return ret;
909 : }
910 :
911 : /*
912 : * Find a contiguous range of bytes in the file marked as delalloc, not more
913 : * than 'max_bytes'. start and end are used to return the range,
914 : *
915 : * True is returned if we find something, false if nothing was in the tree.
916 : */
917 51310610 : bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
918 : u64 *end, u64 max_bytes,
919 : struct extent_state **cached_state)
920 : {
921 51310610 : struct extent_state *state;
922 51310610 : u64 cur_start = *start;
923 51310610 : bool found = false;
924 51310610 : u64 total_bytes = 0;
925 :
926 51310610 : spin_lock(&tree->lock);
927 :
928 : /*
929 : * This search will find all the extents that end after our range
930 : * starts.
931 : */
932 51310462 : state = tree_search(tree, cur_start);
933 51306724 : if (!state) {
934 9204192 : *end = (u64)-1;
935 9204192 : goto out;
936 : }
937 :
938 49305831 : while (state) {
939 45767016 : if (found && (state->start != cur_start ||
940 2805901 : (state->state & EXTENT_BOUNDARY))) {
941 2059644 : goto out;
942 : }
943 43707372 : if (!(state->state & EXTENT_DELALLOC)) {
944 31557513 : if (!found)
945 31550607 : *end = state->end;
946 31557513 : goto out;
947 : }
948 12149859 : if (!found) {
949 10553170 : *start = state->start;
950 10553170 : *cached_state = state;
951 10553170 : refcount_inc(&state->refs);
952 : }
953 12150120 : found = true;
954 12150120 : *end = state->end;
955 12150120 : cur_start = state->end + 1;
956 12150120 : total_bytes += state->end - state->start + 1;
957 12150120 : if (total_bytes >= max_bytes)
958 : break;
959 7202154 : state = next_state(state);
960 : }
961 8486781 : out:
962 51308130 : spin_unlock(&tree->lock);
963 51309856 : return found;
964 : }
965 :
966 : /*
967 : * Set some bits on a range in the tree. This may require allocations or
968 : * sleeping. By default all allocations use GFP_NOFS, use EXTENT_NOWAIT for
969 : * GFP_NOWAIT.
970 : *
971 : * If any of the exclusive bits are set, this will fail with -EEXIST if some
972 : * part of the range already has the desired bits set. The extent_state of the
973 : * existing range is returned in failed_state in this case, and the start of the
974 : * existing range is returned in failed_start. failed_state is used as an
975 : * optimization for wait_extent_bit, failed_start must be used as the source of
976 : * truth as failed_state may have changed since we returned.
977 : *
978 : * [start, end] is inclusive This takes the tree lock.
979 : */
980 176824489 : static int __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
981 : u32 bits, u64 *failed_start,
982 : struct extent_state **failed_state,
983 : struct extent_state **cached_state,
984 : struct extent_changeset *changeset)
985 : {
986 176824489 : struct extent_state *state;
987 176824489 : struct extent_state *prealloc = NULL;
988 176824489 : struct rb_node **p = NULL;
989 176824489 : struct rb_node *parent = NULL;
990 176824489 : int err = 0;
991 176824489 : u64 last_start;
992 176824489 : u64 last_end;
993 176824489 : u32 exclusive_bits = (bits & EXTENT_LOCKED);
994 176824489 : gfp_t mask;
995 :
996 176824489 : set_gfp_mask_from_bits(&bits, &mask);
997 176824489 : btrfs_debug_check_extent_io_range(tree, start, end);
998 176824489 : trace_btrfs_set_extent_bit(tree, start, end - start + 1, bits);
999 :
1000 176824489 : if (exclusive_bits)
1001 : ASSERT(failed_start);
1002 : else
1003 : ASSERT(failed_start == NULL && failed_state == NULL);
1004 : again:
1005 183749059 : if (!prealloc) {
1006 : /*
1007 : * Don't care for allocation failure here because we might end
1008 : * up not needing the pre-allocated extent state at all, which
1009 : * is the case if we only have in the tree extent states that
1010 : * cover our input range and don't cover too any other range.
1011 : * If we end up needing a new extent state we allocate it later.
1012 : */
1013 183580144 : prealloc = alloc_extent_state(mask);
1014 : }
1015 :
1016 183881072 : spin_lock(&tree->lock);
1017 184086779 : if (cached_state && *cached_state) {
1018 48801553 : state = *cached_state;
1019 48801553 : if (state->start <= start && state->end > start &&
1020 : extent_state_in_tree(state))
1021 48262140 : goto hit_next;
1022 : }
1023 : /*
1024 : * This search will find all the extents that end after our range
1025 : * starts.
1026 : */
1027 135824639 : state = tree_search_for_insert(tree, start, &p, &parent);
1028 135728524 : if (!state) {
1029 89587195 : prealloc = alloc_extent_state_atomic(prealloc);
1030 89587195 : if (!prealloc)
1031 0 : goto search_again;
1032 89587195 : prealloc->start = start;
1033 89587195 : prealloc->end = end;
1034 89587195 : insert_state_fast(tree, prealloc, p, parent, bits, changeset);
1035 89554419 : cache_state(prealloc, cached_state);
1036 89600005 : prealloc = NULL;
1037 89600005 : goto out;
1038 : }
1039 46141329 : hit_next:
1040 95041744 : last_start = state->start;
1041 95041744 : last_end = state->end;
1042 :
1043 : /*
1044 : * | ---- desired range ---- |
1045 : * | state |
1046 : *
1047 : * Just lock what we found and keep going
1048 : */
1049 95041744 : if (state->start == start && state->end <= end) {
1050 53052045 : if (state->state & exclusive_bits) {
1051 86731 : *failed_start = state->start;
1052 86731 : cache_state(state, failed_state);
1053 86731 : err = -EEXIST;
1054 86731 : goto out;
1055 : }
1056 :
1057 52965314 : set_state_bits(tree, state, bits, changeset);
1058 52935426 : cache_state(state, cached_state);
1059 52918417 : merge_state(tree, state);
1060 52918831 : if (last_end == (u64)-1)
1061 0 : goto out;
1062 52918831 : start = last_end + 1;
1063 52918831 : state = next_state(state);
1064 52946930 : if (start < end && state && state->start == start &&
1065 : !need_resched())
1066 632184 : goto hit_next;
1067 52314746 : goto search_again;
1068 : }
1069 :
1070 : /*
1071 : * | ---- desired range ---- |
1072 : * | state |
1073 : * or
1074 : * | ------------- state -------------- |
1075 : *
1076 : * We need to split the extent we found, and may flip bits on second
1077 : * half.
1078 : *
1079 : * If the extent we found extends past our range, we just split and
1080 : * search again. It'll get split again the next time though.
1081 : *
1082 : * If the extent we found is inside our range, we set the desired bit
1083 : * on it.
1084 : */
1085 41989699 : if (state->start < start) {
1086 15335401 : if (state->state & exclusive_bits) {
1087 2303 : *failed_start = start;
1088 2303 : cache_state(state, failed_state);
1089 2303 : err = -EEXIST;
1090 2303 : goto out;
1091 : }
1092 :
1093 : /*
1094 : * If this extent already has all the bits we want set, then
1095 : * skip it, not necessary to split it or do anything with it.
1096 : */
1097 15333098 : if ((state->state & bits) == bits) {
1098 25183 : start = state->end + 1;
1099 25183 : cache_state(state, cached_state);
1100 25183 : goto search_again;
1101 : }
1102 :
1103 15307915 : prealloc = alloc_extent_state_atomic(prealloc);
1104 15307915 : if (!prealloc)
1105 0 : goto search_again;
1106 15307915 : err = split_state(tree, state, prealloc, start);
1107 15192029 : if (err)
1108 0 : extent_io_tree_panic(tree, err);
1109 :
1110 15192029 : prealloc = NULL;
1111 15192029 : if (err)
1112 : goto out;
1113 15192029 : if (state->end <= end) {
1114 8502634 : set_state_bits(tree, state, bits, changeset);
1115 8508829 : cache_state(state, cached_state);
1116 8542860 : merge_state(tree, state);
1117 8542531 : if (last_end == (u64)-1)
1118 0 : goto out;
1119 8542531 : start = last_end + 1;
1120 8542531 : state = next_state(state);
1121 8530972 : if (start < end && state && state->start == start &&
1122 : !need_resched())
1123 6091 : goto hit_next;
1124 : }
1125 15214276 : goto search_again;
1126 : }
1127 : /*
1128 : * | ---- desired range ---- |
1129 : * | state | or | state |
1130 : *
1131 : * There's a hole, we need to insert something in it and ignore the
1132 : * extent we found.
1133 : */
1134 26654298 : if (state->start > start) {
1135 18555317 : u64 this_end;
1136 18555317 : if (end < last_start)
1137 : this_end = end;
1138 : else
1139 146130 : this_end = last_start - 1;
1140 :
1141 18555317 : prealloc = alloc_extent_state_atomic(prealloc);
1142 18555317 : if (!prealloc)
1143 0 : goto search_again;
1144 :
1145 : /*
1146 : * Avoid to free 'prealloc' if it can be merged with the later
1147 : * extent.
1148 : */
1149 18555317 : prealloc->start = start;
1150 18555317 : prealloc->end = this_end;
1151 18555317 : err = insert_state(tree, prealloc, bits, changeset);
1152 18555311 : if (err)
1153 0 : extent_io_tree_panic(tree, err);
1154 :
1155 18555311 : cache_state(prealloc, cached_state);
1156 18555360 : prealloc = NULL;
1157 18555360 : start = this_end + 1;
1158 18555360 : goto search_again;
1159 : }
1160 : /*
1161 : * | ---- desired range ---- |
1162 : * | state |
1163 : *
1164 : * We need to split the extent, and set the bit on the first half
1165 : */
1166 8098981 : if (state->start <= end && state->end > end) {
1167 8098981 : if (state->state & exclusive_bits) {
1168 2048 : *failed_start = start;
1169 2048 : cache_state(state, failed_state);
1170 2048 : err = -EEXIST;
1171 2048 : goto out;
1172 : }
1173 :
1174 8096933 : prealloc = alloc_extent_state_atomic(prealloc);
1175 8096933 : if (!prealloc)
1176 0 : goto search_again;
1177 8096959 : err = split_state(tree, state, prealloc, end + 1);
1178 8096081 : if (err)
1179 0 : extent_io_tree_panic(tree, err);
1180 :
1181 8096081 : set_state_bits(tree, prealloc, bits, changeset);
1182 8096270 : cache_state(prealloc, cached_state);
1183 8097024 : merge_state(tree, prealloc);
1184 8096971 : prealloc = NULL;
1185 8096971 : goto out;
1186 : }
1187 :
1188 0 : search_again:
1189 86109539 : if (start > end)
1190 79022356 : goto out;
1191 7087183 : spin_unlock(&tree->lock);
1192 7066776 : if (gfpflags_allow_blocking(mask))
1193 7066775 : cond_resched();
1194 7066775 : goto again;
1195 :
1196 176810414 : out:
1197 176810414 : spin_unlock(&tree->lock);
1198 177012813 : if (prealloc)
1199 52401649 : free_extent_state(prealloc);
1200 :
1201 177001383 : return err;
1202 :
1203 : }
1204 :
1205 80405666 : int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1206 : u32 bits, struct extent_state **cached_state)
1207 : {
1208 80405666 : return __set_extent_bit(tree, start, end, bits, NULL, NULL,
1209 : cached_state, NULL);
1210 : }
1211 :
1212 : /*
1213 : * Convert all bits in a given range from one bit to another
1214 : *
1215 : * @tree: the io tree to search
1216 : * @start: the start offset in bytes
1217 : * @end: the end offset in bytes (inclusive)
1218 : * @bits: the bits to set in this range
1219 : * @clear_bits: the bits to clear in this range
1220 : * @cached_state: state that we're going to cache
1221 : *
1222 : * This will go through and set bits for the given range. If any states exist
1223 : * already in this range they are set with the given bit and cleared of the
1224 : * clear_bits. This is only meant to be used by things that are mergeable, ie.
1225 : * converting from say DELALLOC to DIRTY. This is not meant to be used with
1226 : * boundary bits like LOCK.
1227 : *
1228 : * All allocations are done with GFP_NOFS.
1229 : */
1230 2260243 : int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1231 : u32 bits, u32 clear_bits,
1232 : struct extent_state **cached_state)
1233 : {
1234 2260243 : struct extent_state *state;
1235 2260243 : struct extent_state *prealloc = NULL;
1236 2260243 : struct rb_node **p = NULL;
1237 2260243 : struct rb_node *parent = NULL;
1238 2260243 : int err = 0;
1239 2260243 : u64 last_start;
1240 2260243 : u64 last_end;
1241 2260243 : bool first_iteration = true;
1242 :
1243 2260243 : btrfs_debug_check_extent_io_range(tree, start, end);
1244 2260243 : trace_btrfs_convert_extent_bit(tree, start, end - start + 1, bits,
1245 : clear_bits);
1246 :
1247 2260208 : again:
1248 2260208 : if (!prealloc) {
1249 : /*
1250 : * Best effort, don't worry if extent state allocation fails
1251 : * here for the first iteration. We might have a cached state
1252 : * that matches exactly the target range, in which case no
1253 : * extent state allocations are needed. We'll only know this
1254 : * after locking the tree.
1255 : */
1256 2260201 : prealloc = alloc_extent_state(GFP_NOFS);
1257 2260215 : if (!prealloc && !first_iteration)
1258 : return -ENOMEM;
1259 : }
1260 :
1261 2260222 : spin_lock(&tree->lock);
1262 2260277 : if (cached_state && *cached_state) {
1263 2260277 : state = *cached_state;
1264 2260277 : if (state->start <= start && state->end > start &&
1265 : extent_state_in_tree(state))
1266 2260253 : goto hit_next;
1267 : }
1268 :
1269 : /*
1270 : * This search will find all the extents that end after our range
1271 : * starts.
1272 : */
1273 24 : state = tree_search_for_insert(tree, start, &p, &parent);
1274 0 : if (!state) {
1275 0 : prealloc = alloc_extent_state_atomic(prealloc);
1276 0 : if (!prealloc) {
1277 0 : err = -ENOMEM;
1278 0 : goto out;
1279 : }
1280 0 : prealloc->start = start;
1281 0 : prealloc->end = end;
1282 0 : insert_state_fast(tree, prealloc, p, parent, bits, NULL);
1283 0 : cache_state(prealloc, cached_state);
1284 0 : prealloc = NULL;
1285 0 : goto out;
1286 : }
1287 0 : hit_next:
1288 2260253 : last_start = state->start;
1289 2260253 : last_end = state->end;
1290 :
1291 : /*
1292 : * | ---- desired range ---- |
1293 : * | state |
1294 : *
1295 : * Just lock what we found and keep going.
1296 : */
1297 2260253 : if (state->start == start && state->end <= end) {
1298 2260238 : set_state_bits(tree, state, bits, NULL);
1299 2260221 : cache_state(state, cached_state);
1300 2260221 : state = clear_state_bit(tree, state, clear_bits, 0, NULL);
1301 2260188 : if (last_end == (u64)-1)
1302 0 : goto out;
1303 2260188 : start = last_end + 1;
1304 2260188 : if (start < end && state && state->start == start &&
1305 : !need_resched())
1306 0 : goto hit_next;
1307 2260188 : goto search_again;
1308 : }
1309 :
1310 : /*
1311 : * | ---- desired range ---- |
1312 : * | state |
1313 : * or
1314 : * | ------------- state -------------- |
1315 : *
1316 : * We need to split the extent we found, and may flip bits on second
1317 : * half.
1318 : *
1319 : * If the extent we found extends past our range, we just split and
1320 : * search again. It'll get split again the next time though.
1321 : *
1322 : * If the extent we found is inside our range, we set the desired bit
1323 : * on it.
1324 : */
1325 15 : if (state->start < start) {
1326 15 : prealloc = alloc_extent_state_atomic(prealloc);
1327 15 : if (!prealloc) {
1328 0 : err = -ENOMEM;
1329 0 : goto out;
1330 : }
1331 15 : err = split_state(tree, state, prealloc, start);
1332 0 : if (err)
1333 0 : extent_io_tree_panic(tree, err);
1334 0 : prealloc = NULL;
1335 0 : if (err)
1336 : goto out;
1337 0 : if (state->end <= end) {
1338 0 : set_state_bits(tree, state, bits, NULL);
1339 0 : cache_state(state, cached_state);
1340 0 : state = clear_state_bit(tree, state, clear_bits, 0, NULL);
1341 0 : if (last_end == (u64)-1)
1342 0 : goto out;
1343 0 : start = last_end + 1;
1344 0 : if (start < end && state && state->start == start &&
1345 : !need_resched())
1346 0 : goto hit_next;
1347 : }
1348 0 : goto search_again;
1349 : }
1350 : /*
1351 : * | ---- desired range ---- |
1352 : * | state | or | state |
1353 : *
1354 : * There's a hole, we need to insert something in it and ignore the
1355 : * extent we found.
1356 : */
1357 0 : if (state->start > start) {
1358 0 : u64 this_end;
1359 0 : if (end < last_start)
1360 : this_end = end;
1361 : else
1362 0 : this_end = last_start - 1;
1363 :
1364 0 : prealloc = alloc_extent_state_atomic(prealloc);
1365 0 : if (!prealloc) {
1366 0 : err = -ENOMEM;
1367 0 : goto out;
1368 : }
1369 :
1370 : /*
1371 : * Avoid to free 'prealloc' if it can be merged with the later
1372 : * extent.
1373 : */
1374 0 : prealloc->start = start;
1375 0 : prealloc->end = this_end;
1376 0 : err = insert_state(tree, prealloc, bits, NULL);
1377 0 : if (err)
1378 0 : extent_io_tree_panic(tree, err);
1379 0 : cache_state(prealloc, cached_state);
1380 0 : prealloc = NULL;
1381 0 : start = this_end + 1;
1382 0 : goto search_again;
1383 : }
1384 : /*
1385 : * | ---- desired range ---- |
1386 : * | state |
1387 : *
1388 : * We need to split the extent, and set the bit on the first half.
1389 : */
1390 0 : if (state->start <= end && state->end > end) {
1391 0 : prealloc = alloc_extent_state_atomic(prealloc);
1392 0 : if (!prealloc) {
1393 0 : err = -ENOMEM;
1394 0 : goto out;
1395 : }
1396 :
1397 0 : err = split_state(tree, state, prealloc, end + 1);
1398 0 : if (err)
1399 0 : extent_io_tree_panic(tree, err);
1400 :
1401 0 : set_state_bits(tree, prealloc, bits, NULL);
1402 0 : cache_state(prealloc, cached_state);
1403 0 : clear_state_bit(tree, prealloc, clear_bits, 0, NULL);
1404 0 : prealloc = NULL;
1405 0 : goto out;
1406 : }
1407 :
1408 0 : search_again:
1409 2260188 : if (start > end)
1410 2260232 : goto out;
1411 0 : spin_unlock(&tree->lock);
1412 0 : cond_resched();
1413 0 : first_iteration = false;
1414 0 : goto again;
1415 :
1416 2260232 : out:
1417 2260232 : spin_unlock(&tree->lock);
1418 2260268 : if (prealloc)
1419 2260268 : free_extent_state(prealloc);
1420 :
1421 : return err;
1422 : }
1423 :
1424 : /*
1425 : * Find the first range that has @bits not set. This range could start before
1426 : * @start.
1427 : *
1428 : * @tree: the tree to search
1429 : * @start: offset at/after which the found extent should start
1430 : * @start_ret: records the beginning of the range
1431 : * @end_ret: records the end of the range (inclusive)
1432 : * @bits: the set of bits which must be unset
1433 : *
1434 : * Since unallocated range is also considered one which doesn't have the bits
1435 : * set it's possible that @end_ret contains -1, this happens in case the range
1436 : * spans (last_range_end, end of device]. In this case it's up to the caller to
1437 : * trim @end_ret to the appropriate size.
1438 : */
1439 1014 : void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
1440 : u64 *start_ret, u64 *end_ret, u32 bits)
1441 : {
1442 1014 : struct extent_state *state;
1443 1014 : struct extent_state *prev = NULL, *next = NULL;
1444 :
1445 1014 : spin_lock(&tree->lock);
1446 :
1447 : /* Find first extent with bits cleared */
1448 5373 : while (1) {
1449 5373 : state = tree_search_prev_next(tree, start, &prev, &next);
1450 5373 : if (!state && !next && !prev) {
1451 : /*
1452 : * Tree is completely empty, send full range and let
1453 : * caller deal with it
1454 : */
1455 0 : *start_ret = 0;
1456 0 : *end_ret = -1;
1457 0 : goto out;
1458 5373 : } else if (!state && !next) {
1459 : /*
1460 : * We are past the last allocated chunk, set start at
1461 : * the end of the last extent.
1462 : */
1463 997 : *start_ret = prev->end + 1;
1464 997 : *end_ret = -1;
1465 997 : goto out;
1466 4376 : } else if (!state) {
1467 17 : state = next;
1468 : }
1469 :
1470 : /*
1471 : * At this point 'state' either contains 'start' or start is
1472 : * before 'state'
1473 : */
1474 4376 : if (in_range(start, state->start, state->end - state->start + 1)) {
1475 4359 : if (state->state & bits) {
1476 : /*
1477 : * |--range with bits sets--|
1478 : * |
1479 : * start
1480 : */
1481 : start = state->end + 1;
1482 : } else {
1483 : /*
1484 : * 'start' falls within a range that doesn't
1485 : * have the bits set, so take its start as the
1486 : * beginning of the desired range
1487 : *
1488 : * |--range with bits cleared----|
1489 : * |
1490 : * start
1491 : */
1492 0 : *start_ret = state->start;
1493 0 : break;
1494 : }
1495 : } else {
1496 : /*
1497 : * |---prev range---|---hole/unset---|---node range---|
1498 : * |
1499 : * start
1500 : *
1501 : * or
1502 : *
1503 : * |---hole/unset--||--first node--|
1504 : * 0 |
1505 : * start
1506 : */
1507 17 : if (prev)
1508 5 : *start_ret = prev->end + 1;
1509 : else
1510 12 : *start_ret = 0;
1511 : break;
1512 : }
1513 : }
1514 :
1515 : /*
1516 : * Find the longest stretch from start until an entry which has the
1517 : * bits set
1518 : */
1519 17 : while (state) {
1520 17 : if (state->end >= start && !(state->state & bits)) {
1521 0 : *end_ret = state->end;
1522 : } else {
1523 17 : *end_ret = state->start - 1;
1524 17 : break;
1525 : }
1526 0 : state = next_state(state);
1527 : }
1528 0 : out:
1529 1014 : spin_unlock(&tree->lock);
1530 1014 : }
1531 :
1532 : /*
1533 : * Count the number of bytes in the tree that have a given bit(s) set for a
1534 : * given range.
1535 : *
1536 : * @tree: The io tree to search.
1537 : * @start: The start offset of the range. This value is updated to the
1538 : * offset of the first byte found with the given bit(s), so it
1539 : * can end up being bigger than the initial value.
1540 : * @search_end: The end offset (inclusive value) of the search range.
1541 : * @max_bytes: The maximum byte count we are interested. The search stops
1542 : * once it reaches this count.
1543 : * @bits: The bits the range must have in order to be accounted for.
1544 : * If multiple bits are set, then only subranges that have all
1545 : * the bits set are accounted for.
1546 : * @contig: Indicate if we should ignore holes in the range or not. If
1547 : * this is true, then stop once we find a hole.
1548 : * @cached_state: A cached state to be used across multiple calls to this
1549 : * function in order to speedup searches. Use NULL if this is
1550 : * called only once or if each call does not start where the
1551 : * previous one ended.
1552 : *
1553 : * Returns the total number of bytes found within the given range that have
1554 : * all given bits set. If the returned number of bytes is greater than zero
1555 : * then @start is updated with the offset of the first byte with the bits set.
1556 : */
1557 1130632 : u64 count_range_bits(struct extent_io_tree *tree,
1558 : u64 *start, u64 search_end, u64 max_bytes,
1559 : u32 bits, int contig,
1560 : struct extent_state **cached_state)
1561 : {
1562 1130632 : struct extent_state *state = NULL;
1563 1130632 : struct extent_state *cached;
1564 1130632 : u64 cur_start = *start;
1565 1130632 : u64 total_bytes = 0;
1566 1130632 : u64 last = 0;
1567 1130632 : int found = 0;
1568 :
1569 1130632 : if (WARN_ON(search_end < cur_start))
1570 : return 0;
1571 :
1572 1130632 : spin_lock(&tree->lock);
1573 :
1574 1130638 : if (!cached_state || !*cached_state)
1575 1109374 : goto search;
1576 :
1577 21264 : cached = *cached_state;
1578 :
1579 21264 : if (!extent_state_in_tree(cached))
1580 222 : goto search;
1581 :
1582 21042 : if (cached->start <= cur_start && cur_start <= cached->end) {
1583 : state = cached;
1584 911 : } else if (cached->start > cur_start) {
1585 821 : struct extent_state *prev;
1586 :
1587 : /*
1588 : * The cached state starts after our search range's start. Check
1589 : * if the previous state record starts at or before the range we
1590 : * are looking for, and if so, use it - this is a common case
1591 : * when there are holes between records in the tree. If there is
1592 : * no previous state record, we can start from our cached state.
1593 : */
1594 821 : prev = prev_state(cached);
1595 821 : if (!prev)
1596 : state = cached;
1597 821 : else if (prev->start <= cur_start && cur_start <= prev->end)
1598 : state = prev;
1599 : }
1600 :
1601 : /*
1602 : * This search will find all the extents that end after our range
1603 : * starts.
1604 : */
1605 114 : search:
1606 1130524 : if (!state)
1607 1109710 : state = tree_search(tree, cur_start);
1608 :
1609 2480215 : while (state) {
1610 1676270 : if (state->start > search_end)
1611 : break;
1612 1369873 : if (contig && found && state->start > last + 1)
1613 : break;
1614 1369873 : if (state->end >= cur_start && (state->state & bits) == bits) {
1615 20458 : total_bytes += min(search_end, state->end) + 1 -
1616 20458 : max(cur_start, state->start);
1617 20458 : if (total_bytes >= max_bytes)
1618 : break;
1619 1578 : if (!found) {
1620 1578 : *start = max(cur_start, state->start);
1621 1578 : found = 1;
1622 : }
1623 1578 : last = state->end;
1624 1349415 : } else if (contig && found) {
1625 : break;
1626 : }
1627 1349602 : state = next_state(state);
1628 : }
1629 :
1630 1130613 : if (cached_state) {
1631 45033 : free_extent_state(*cached_state);
1632 45033 : *cached_state = state;
1633 45033 : if (state)
1634 21273 : refcount_inc(&state->refs);
1635 : }
1636 :
1637 1130613 : spin_unlock(&tree->lock);
1638 :
1639 1130613 : return total_bytes;
1640 : }
1641 :
1642 : /*
1643 : * Search a range in the state tree for a given mask. If 'filled' == 1, this
1644 : * returns 1 only if every extent in the tree has the bits set. Otherwise, 1
1645 : * is returned if any bit in the range is found set.
1646 : */
1647 55566258 : int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
1648 : u32 bits, int filled, struct extent_state *cached)
1649 : {
1650 55566258 : struct extent_state *state = NULL;
1651 55566258 : int bitset = 0;
1652 :
1653 55566258 : spin_lock(&tree->lock);
1654 55568441 : if (cached && extent_state_in_tree(cached) && cached->start <= start &&
1655 3470851 : cached->end > start)
1656 : state = cached;
1657 : else
1658 52097590 : state = tree_search(tree, start);
1659 55854464 : while (state && start <= end) {
1660 13394151 : if (filled && state->start > start) {
1661 : bitset = 0;
1662 : break;
1663 : }
1664 :
1665 13388519 : if (state->start > end)
1666 : break;
1667 :
1668 5452031 : if (state->state & bits) {
1669 4090533 : bitset = 1;
1670 4090533 : if (!filled)
1671 : break;
1672 1361498 : } else if (filled) {
1673 : bitset = 0;
1674 : break;
1675 : }
1676 :
1677 4176207 : if (state->end == (u64)-1)
1678 : break;
1679 :
1680 4176207 : start = state->end + 1;
1681 4176207 : if (start > end)
1682 : break;
1683 287944 : state = next_state(state);
1684 : }
1685 :
1686 : /* We ran out of states and were still inside of our range. */
1687 55566520 : if (filled && !state)
1688 439 : bitset = 0;
1689 55566520 : spin_unlock(&tree->lock);
1690 55567400 : return bitset;
1691 : }
1692 :
1693 : /* Wrappers around set/clear extent bit */
1694 1911660 : int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1695 : u32 bits, struct extent_changeset *changeset)
1696 : {
1697 : /*
1698 : * We don't support EXTENT_LOCKED yet, as current changeset will
1699 : * record any bits changed, so for EXTENT_LOCKED case, it will
1700 : * either fail with -EEXIST or changeset will record the whole
1701 : * range.
1702 : */
1703 1911660 : ASSERT(!(bits & EXTENT_LOCKED));
1704 :
1705 1911660 : return __set_extent_bit(tree, start, end, bits, NULL, NULL, NULL, changeset);
1706 : }
1707 :
1708 6818450 : int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1709 : u32 bits, struct extent_changeset *changeset)
1710 : {
1711 : /*
1712 : * Don't support EXTENT_LOCKED case, same reason as
1713 : * set_record_extent_bits().
1714 : */
1715 6818450 : ASSERT(!(bits & EXTENT_LOCKED));
1716 :
1717 6818450 : return __clear_extent_bit(tree, start, end, bits, NULL, changeset);
1718 : }
1719 :
1720 3266 : int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
1721 : struct extent_state **cached)
1722 : {
1723 3266 : int err;
1724 3266 : u64 failed_start;
1725 :
1726 3266 : err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start,
1727 : NULL, cached, NULL);
1728 3266 : if (err == -EEXIST) {
1729 5 : if (failed_start > start)
1730 4 : clear_extent_bit(tree, start, failed_start - 1,
1731 : EXTENT_LOCKED, cached);
1732 5 : return 0;
1733 : }
1734 : return 1;
1735 : }
1736 :
1737 : /*
1738 : * Either insert or lock state struct between start and end use mask to tell
1739 : * us if waiting is desired.
1740 : */
1741 94494217 : int lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
1742 : struct extent_state **cached_state)
1743 : {
1744 94494217 : struct extent_state *failed_state = NULL;
1745 94494217 : int err;
1746 94494217 : u64 failed_start;
1747 :
1748 94494217 : err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start,
1749 : &failed_state, cached_state, NULL);
1750 94468760 : while (err == -EEXIST) {
1751 90996 : if (failed_start != start)
1752 4413 : clear_extent_bit(tree, start, failed_start - 1,
1753 : EXTENT_LOCKED, cached_state);
1754 :
1755 90996 : wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED,
1756 : &failed_state);
1757 91077 : err = __set_extent_bit(tree, start, end, EXTENT_LOCKED,
1758 : &failed_start, &failed_state,
1759 : cached_state, NULL);
1760 : }
1761 94336810 : return err;
1762 : }
1763 :
1764 0 : void __cold extent_state_free_cachep(void)
1765 : {
1766 0 : btrfs_extent_state_leak_debug_check();
1767 0 : kmem_cache_destroy(extent_state_cache);
1768 0 : }
1769 :
1770 11 : int __init extent_state_init_cachep(void)
1771 : {
1772 11 : extent_state_cache = kmem_cache_create("btrfs_extent_state",
1773 : sizeof(struct extent_state), 0,
1774 : SLAB_MEM_SPREAD, NULL);
1775 11 : if (!extent_state_cache)
1776 0 : return -ENOMEM;
1777 :
1778 : return 0;
1779 : }
|
