]>
git.ipfire.org Git - thirdparty/u-boot.git/blob - fs/btrfs/extent-io.c
1 // SPDX-License-Identifier: GPL-2.0+
3 * BTRFS filesystem implementation for U-Boot
5 * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz
8 #include <linux/kernel.h>
14 #include "extent-io.h"
17 void extent_io_tree_init(struct extent_io_tree
*tree
)
19 cache_tree_init(&tree
->state
);
20 cache_tree_init(&tree
->cache
);
24 static struct extent_state
*alloc_extent_state(void)
26 struct extent_state
*state
;
28 state
= malloc(sizeof(*state
));
31 state
->cache_node
.objectid
= 0;
38 static void btrfs_free_extent_state(struct extent_state
*state
)
41 BUG_ON(state
->refs
< 0);
46 static void free_extent_state_func(struct cache_extent
*cache
)
48 struct extent_state
*es
;
50 es
= container_of(cache
, struct extent_state
, cache_node
);
51 btrfs_free_extent_state(es
);
54 static void free_extent_buffer_final(struct extent_buffer
*eb
);
55 void extent_io_tree_cleanup(struct extent_io_tree
*tree
)
57 cache_tree_free_extents(&tree
->state
, free_extent_state_func
);
60 static inline void update_extent_state(struct extent_state
*state
)
62 state
->cache_node
.start
= state
->start
;
63 state
->cache_node
.size
= state
->end
+ 1 - state
->start
;
67 * Utility function to look for merge candidates inside a given range.
68 * Any extents with matching state are merged together into a single
69 * extent in the tree. Extents with EXTENT_IO in their state field are
72 static int merge_state(struct extent_io_tree
*tree
,
73 struct extent_state
*state
)
75 struct extent_state
*other
;
76 struct cache_extent
*other_node
;
78 if (state
->state
& EXTENT_IOBITS
)
81 other_node
= prev_cache_extent(&state
->cache_node
);
83 other
= container_of(other_node
, struct extent_state
,
85 if (other
->end
== state
->start
- 1 &&
86 other
->state
== state
->state
) {
87 state
->start
= other
->start
;
88 update_extent_state(state
);
89 remove_cache_extent(&tree
->state
, &other
->cache_node
);
90 btrfs_free_extent_state(other
);
93 other_node
= next_cache_extent(&state
->cache_node
);
95 other
= container_of(other_node
, struct extent_state
,
97 if (other
->start
== state
->end
+ 1 &&
98 other
->state
== state
->state
) {
99 other
->start
= state
->start
;
100 update_extent_state(other
);
101 remove_cache_extent(&tree
->state
, &state
->cache_node
);
102 btrfs_free_extent_state(state
);
109 * insert an extent_state struct into the tree. 'bits' are set on the
110 * struct before it is inserted.
112 static int insert_state(struct extent_io_tree
*tree
,
113 struct extent_state
*state
, u64 start
, u64 end
,
119 state
->state
|= bits
;
120 state
->start
= start
;
122 update_extent_state(state
);
123 ret
= insert_cache_extent(&tree
->state
, &state
->cache_node
);
125 merge_state(tree
, state
);
130 * split a given extent state struct in two, inserting the preallocated
131 * struct 'prealloc' as the newly created second half. 'split' indicates an
132 * offset inside 'orig' where it should be split.
134 static int split_state(struct extent_io_tree
*tree
, struct extent_state
*orig
,
135 struct extent_state
*prealloc
, u64 split
)
138 prealloc
->start
= orig
->start
;
139 prealloc
->end
= split
- 1;
140 prealloc
->state
= orig
->state
;
141 update_extent_state(prealloc
);
143 update_extent_state(orig
);
144 ret
= insert_cache_extent(&tree
->state
, &prealloc
->cache_node
);
150 * clear some bits on a range in the tree.
152 static int clear_state_bit(struct extent_io_tree
*tree
,
153 struct extent_state
*state
, int bits
)
155 int ret
= state
->state
& bits
;
157 state
->state
&= ~bits
;
158 if (state
->state
== 0) {
159 remove_cache_extent(&tree
->state
, &state
->cache_node
);
160 btrfs_free_extent_state(state
);
162 merge_state(tree
, state
);
168 * extent_buffer_bitmap_set - set an area of a bitmap
169 * @eb: the extent buffer
170 * @start: offset of the bitmap item in the extent buffer
171 * @pos: bit number of the first bit
172 * @len: number of bits to set
174 void extent_buffer_bitmap_set(struct extent_buffer
*eb
, unsigned long start
,
175 unsigned long pos
, unsigned long len
)
177 u8
*p
= (u8
*)eb
->data
+ start
+ BIT_BYTE(pos
);
178 const unsigned int size
= pos
+ len
;
179 int bits_to_set
= BITS_PER_BYTE
- (pos
% BITS_PER_BYTE
);
180 u8 mask_to_set
= BITMAP_FIRST_BYTE_MASK(pos
);
182 while (len
>= bits_to_set
) {
185 bits_to_set
= BITS_PER_BYTE
;
190 mask_to_set
&= BITMAP_LAST_BYTE_MASK(size
);
196 * extent_buffer_bitmap_clear - clear an area of a bitmap
197 * @eb: the extent buffer
198 * @start: offset of the bitmap item in the extent buffer
199 * @pos: bit number of the first bit
200 * @len: number of bits to clear
202 void extent_buffer_bitmap_clear(struct extent_buffer
*eb
, unsigned long start
,
203 unsigned long pos
, unsigned long len
)
205 u8
*p
= (u8
*)eb
->data
+ start
+ BIT_BYTE(pos
);
206 const unsigned int size
= pos
+ len
;
207 int bits_to_clear
= BITS_PER_BYTE
- (pos
% BITS_PER_BYTE
);
208 u8 mask_to_clear
= BITMAP_FIRST_BYTE_MASK(pos
);
210 while (len
>= bits_to_clear
) {
211 *p
&= ~mask_to_clear
;
212 len
-= bits_to_clear
;
213 bits_to_clear
= BITS_PER_BYTE
;
218 mask_to_clear
&= BITMAP_LAST_BYTE_MASK(size
);
219 *p
&= ~mask_to_clear
;
224 * clear some bits on a range in the tree.
226 int clear_extent_bits(struct extent_io_tree
*tree
, u64 start
, u64 end
, int bits
)
228 struct extent_state
*state
;
229 struct extent_state
*prealloc
= NULL
;
230 struct cache_extent
*node
;
237 prealloc
= alloc_extent_state();
243 * this search will find the extents that end after
246 node
= search_cache_extent(&tree
->state
, start
);
249 state
= container_of(node
, struct extent_state
, cache_node
);
250 if (state
->start
> end
)
252 last_end
= state
->end
;
255 * | ---- desired range ---- |
257 * | ------------- state -------------- |
259 * We need to split the extent we found, and may flip
260 * bits on second half.
262 * If the extent we found extends past our range, we
263 * just split and search again. It'll get split again
264 * the next time though.
266 * If the extent we found is inside our range, we clear
267 * the desired bit on it.
269 if (state
->start
< start
) {
270 err
= split_state(tree
, state
, prealloc
, start
);
271 BUG_ON(err
== -EEXIST
);
275 if (state
->end
<= end
) {
276 set
|= clear_state_bit(tree
, state
, bits
);
277 if (last_end
== (u64
)-1)
279 start
= last_end
+ 1;
281 start
= state
->start
;
286 * | ---- desired range ---- |
288 * We need to split the extent, and clear the bit
291 if (state
->start
<= end
&& state
->end
> end
) {
292 err
= split_state(tree
, state
, prealloc
, end
+ 1);
293 BUG_ON(err
== -EEXIST
);
295 set
|= clear_state_bit(tree
, prealloc
, bits
);
300 start
= state
->end
+ 1;
301 set
|= clear_state_bit(tree
, state
, bits
);
302 if (last_end
== (u64
)-1)
304 start
= last_end
+ 1;
308 btrfs_free_extent_state(prealloc
);
318 * set some bits on a range in the tree.
320 int set_extent_bits(struct extent_io_tree
*tree
, u64 start
, u64 end
, int bits
)
322 struct extent_state
*state
;
323 struct extent_state
*prealloc
= NULL
;
324 struct cache_extent
*node
;
330 prealloc
= alloc_extent_state();
336 * this search will find the extents that end after
339 node
= search_cache_extent(&tree
->state
, start
);
341 err
= insert_state(tree
, prealloc
, start
, end
, bits
);
342 BUG_ON(err
== -EEXIST
);
347 state
= container_of(node
, struct extent_state
, cache_node
);
348 last_start
= state
->start
;
349 last_end
= state
->end
;
352 * | ---- desired range ---- |
355 * Just lock what we found and keep going
357 if (state
->start
== start
&& state
->end
<= end
) {
358 state
->state
|= bits
;
359 merge_state(tree
, state
);
360 if (last_end
== (u64
)-1)
362 start
= last_end
+ 1;
366 * | ---- desired range ---- |
369 * | ------------- state -------------- |
371 * We need to split the extent we found, and may flip bits on
374 * If the extent we found extends past our
375 * range, we just split and search again. It'll get split
376 * again the next time though.
378 * If the extent we found is inside our range, we set the
381 if (state
->start
< start
) {
382 err
= split_state(tree
, state
, prealloc
, start
);
383 BUG_ON(err
== -EEXIST
);
387 if (state
->end
<= end
) {
388 state
->state
|= bits
;
389 start
= state
->end
+ 1;
390 merge_state(tree
, state
);
391 if (last_end
== (u64
)-1)
393 start
= last_end
+ 1;
395 start
= state
->start
;
400 * | ---- desired range ---- |
401 * | state | or | state |
403 * There's a hole, we need to insert something in it and
404 * ignore the extent we found.
406 if (state
->start
> start
) {
408 if (end
< last_start
)
411 this_end
= last_start
-1;
412 err
= insert_state(tree
, prealloc
, start
, this_end
,
414 BUG_ON(err
== -EEXIST
);
418 start
= this_end
+ 1;
422 * | ---- desired range ---- |
423 * | ---------- state ---------- |
424 * We need to split the extent, and set the bit
427 err
= split_state(tree
, state
, prealloc
, end
+ 1);
428 BUG_ON(err
== -EEXIST
);
430 state
->state
|= bits
;
431 merge_state(tree
, prealloc
);
435 btrfs_free_extent_state(prealloc
);
443 int set_extent_dirty(struct extent_io_tree
*tree
, u64 start
, u64 end
)
445 return set_extent_bits(tree
, start
, end
, EXTENT_DIRTY
);
448 int clear_extent_dirty(struct extent_io_tree
*tree
, u64 start
, u64 end
)
450 return clear_extent_bits(tree
, start
, end
, EXTENT_DIRTY
);
453 int find_first_extent_bit(struct extent_io_tree
*tree
, u64 start
,
454 u64
*start_ret
, u64
*end_ret
, int bits
)
456 struct cache_extent
*node
;
457 struct extent_state
*state
;
461 * this search will find all the extents that end after
464 node
= search_cache_extent(&tree
->state
, start
);
469 state
= container_of(node
, struct extent_state
, cache_node
);
470 if (state
->end
>= start
&& (state
->state
& bits
)) {
471 *start_ret
= state
->start
;
472 *end_ret
= state
->end
;
476 node
= next_cache_extent(node
);
484 int test_range_bit(struct extent_io_tree
*tree
, u64 start
, u64 end
,
485 int bits
, int filled
)
487 struct extent_state
*state
= NULL
;
488 struct cache_extent
*node
;
491 node
= search_cache_extent(&tree
->state
, start
);
492 while (node
&& start
<= end
) {
493 state
= container_of(node
, struct extent_state
, cache_node
);
495 if (filled
&& state
->start
> start
) {
499 if (state
->start
> end
)
501 if (state
->state
& bits
) {
509 start
= state
->end
+ 1;
512 node
= next_cache_extent(node
);
522 int set_state_private(struct extent_io_tree
*tree
, u64 start
, u64
private)
524 struct cache_extent
*node
;
525 struct extent_state
*state
;
528 node
= search_cache_extent(&tree
->state
, start
);
533 state
= container_of(node
, struct extent_state
, cache_node
);
534 if (state
->start
!= start
) {
538 state
->xprivate
= private;
543 int get_state_private(struct extent_io_tree
*tree
, u64 start
, u64
*private)
545 struct cache_extent
*node
;
546 struct extent_state
*state
;
549 node
= search_cache_extent(&tree
->state
, start
);
554 state
= container_of(node
, struct extent_state
, cache_node
);
555 if (state
->start
!= start
) {
559 *private = state
->xprivate
;
564 static struct extent_buffer
*__alloc_extent_buffer(struct btrfs_fs_info
*info
,
565 u64 bytenr
, u32 blocksize
)
567 struct extent_buffer
*eb
;
569 eb
= calloc(1, sizeof(struct extent_buffer
));
572 eb
->data
= malloc_cache_aligned(blocksize
);
582 eb
->cache_node
.start
= bytenr
;
583 eb
->cache_node
.size
= blocksize
;
585 memset_extent_buffer(eb
, 0, 0, blocksize
);
590 struct extent_buffer
*btrfs_clone_extent_buffer(struct extent_buffer
*src
)
592 struct extent_buffer
*new;
594 new = __alloc_extent_buffer(src
->fs_info
, src
->start
, src
->len
);
598 copy_extent_buffer(new, src
, 0, 0, src
->len
);
599 new->flags
|= EXTENT_BUFFER_DUMMY
;
604 static void free_extent_buffer_final(struct extent_buffer
*eb
)
607 if (!(eb
->flags
& EXTENT_BUFFER_DUMMY
)) {
608 struct extent_io_tree
*tree
= &eb
->fs_info
->extent_cache
;
610 remove_cache_extent(&tree
->cache
, &eb
->cache_node
);
611 BUG_ON(tree
->cache_size
< eb
->len
);
612 tree
->cache_size
-= eb
->len
;
618 static void free_extent_buffer_internal(struct extent_buffer
*eb
, bool free_now
)
620 if (!eb
|| IS_ERR(eb
))
624 BUG_ON(eb
->refs
< 0);
626 if (eb
->flags
& EXTENT_DIRTY
) {
628 "dirty eb leak (aborted trans): start %llu len %u",
631 if (eb
->flags
& EXTENT_BUFFER_DUMMY
|| free_now
)
632 free_extent_buffer_final(eb
);
636 void free_extent_buffer(struct extent_buffer
*eb
)
638 free_extent_buffer_internal(eb
, 1);
641 struct extent_buffer
*find_extent_buffer(struct extent_io_tree
*tree
,
642 u64 bytenr
, u32 blocksize
)
644 struct extent_buffer
*eb
= NULL
;
645 struct cache_extent
*cache
;
647 cache
= lookup_cache_extent(&tree
->cache
, bytenr
, blocksize
);
648 if (cache
&& cache
->start
== bytenr
&&
649 cache
->size
== blocksize
) {
650 eb
= container_of(cache
, struct extent_buffer
, cache_node
);
656 struct extent_buffer
*find_first_extent_buffer(struct extent_io_tree
*tree
,
659 struct extent_buffer
*eb
= NULL
;
660 struct cache_extent
*cache
;
662 cache
= search_cache_extent(&tree
->cache
, start
);
664 eb
= container_of(cache
, struct extent_buffer
, cache_node
);
670 struct extent_buffer
*alloc_extent_buffer(struct btrfs_fs_info
*fs_info
,
671 u64 bytenr
, u32 blocksize
)
673 struct extent_buffer
*eb
;
674 struct extent_io_tree
*tree
= &fs_info
->extent_cache
;
675 struct cache_extent
*cache
;
677 cache
= lookup_cache_extent(&tree
->cache
, bytenr
, blocksize
);
678 if (cache
&& cache
->start
== bytenr
&&
679 cache
->size
== blocksize
) {
680 eb
= container_of(cache
, struct extent_buffer
, cache_node
);
686 eb
= container_of(cache
, struct extent_buffer
,
688 free_extent_buffer(eb
);
690 eb
= __alloc_extent_buffer(fs_info
, bytenr
, blocksize
);
693 ret
= insert_cache_extent(&tree
->cache
, &eb
->cache_node
);
698 tree
->cache_size
+= blocksize
;
704 * Allocate a dummy extent buffer which won't be inserted into extent buffer
707 * This mostly allows super block read write using existing eb infrastructure
708 * without pulluting the eb cache.
710 * This is especially important to avoid injecting eb->start == SZ_64K, as
711 * fuzzed image could have invalid tree bytenr covers super block range,
712 * and cause ref count underflow.
714 struct extent_buffer
*alloc_dummy_extent_buffer(struct btrfs_fs_info
*fs_info
,
715 u64 bytenr
, u32 blocksize
)
717 struct extent_buffer
*ret
;
719 ret
= __alloc_extent_buffer(fs_info
, bytenr
, blocksize
);
723 ret
->flags
|= EXTENT_BUFFER_DUMMY
;
728 int read_extent_from_disk(struct blk_desc
*desc
, struct disk_partition
*part
,
729 u64 physical
, struct extent_buffer
*eb
,
730 unsigned long offset
, unsigned long len
)
734 ret
= __btrfs_devread(desc
, part
, eb
->data
+ offset
, len
, physical
);
746 int memcmp_extent_buffer(const struct extent_buffer
*eb
, const void *ptrv
,
747 unsigned long start
, unsigned long len
)
749 return memcmp(eb
->data
+ start
, ptrv
, len
);
752 void read_extent_buffer(const struct extent_buffer
*eb
, void *dst
,
753 unsigned long start
, unsigned long len
)
755 memcpy(dst
, eb
->data
+ start
, len
);
758 void write_extent_buffer(struct extent_buffer
*eb
, const void *src
,
759 unsigned long start
, unsigned long len
)
761 memcpy(eb
->data
+ start
, src
, len
);
764 void copy_extent_buffer(struct extent_buffer
*dst
, struct extent_buffer
*src
,
765 unsigned long dst_offset
, unsigned long src_offset
,
768 memcpy(dst
->data
+ dst_offset
, src
->data
+ src_offset
, len
);
771 void memmove_extent_buffer(struct extent_buffer
*dst
, unsigned long dst_offset
,
772 unsigned long src_offset
, unsigned long len
)
774 memmove(dst
->data
+ dst_offset
, dst
->data
+ src_offset
, len
);
777 void memset_extent_buffer(struct extent_buffer
*eb
, char c
,
778 unsigned long start
, unsigned long len
)
780 memset(eb
->data
+ start
, c
, len
);
783 int extent_buffer_test_bit(struct extent_buffer
*eb
, unsigned long start
,
786 return le_test_bit(nr
, (u8
*)eb
->data
+ start
);
789 int set_extent_buffer_dirty(struct extent_buffer
*eb
)
791 struct extent_io_tree
*tree
= &eb
->fs_info
->extent_cache
;
792 if (!(eb
->flags
& EXTENT_DIRTY
)) {
793 eb
->flags
|= EXTENT_DIRTY
;
794 set_extent_dirty(tree
, eb
->start
, eb
->start
+ eb
->len
- 1);
795 extent_buffer_get(eb
);
800 int clear_extent_buffer_dirty(struct extent_buffer
*eb
)
802 struct extent_io_tree
*tree
= &eb
->fs_info
->extent_cache
;
803 if (eb
->flags
& EXTENT_DIRTY
) {
804 eb
->flags
&= ~EXTENT_DIRTY
;
805 clear_extent_dirty(tree
, eb
->start
, eb
->start
+ eb
->len
- 1);
806 free_extent_buffer(eb
);