1 // SPDX-License-Identifier: GPL-2.0+
3 * BTRFS filesystem implementation for U-Boot
5 * 2017 Marek BehĂșn, CZ.NIC, kabel@kernel.org
8 #include <linux/kernel.h>
16 * Read the content of symlink inode @ino of @root, into @target.
17 * NOTE: @target will not be \0 termiated, caller should handle it properly.
19 * Return the number of read data.
20 * Return <0 for error.
22 int btrfs_readlink(struct btrfs_root
*root
, u64 ino
, char *target
)
24 struct btrfs_path path
;
26 struct btrfs_file_extent_item
*fi
;
30 key
.type
= BTRFS_EXTENT_DATA_KEY
;
32 btrfs_init_path(&path
);
34 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
41 fi
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
42 struct btrfs_file_extent_item
);
43 if (btrfs_file_extent_type(path
.nodes
[0], fi
) !=
44 BTRFS_FILE_EXTENT_INLINE
) {
46 error("Extent for symlink %llu must be INLINE type!", ino
);
49 if (btrfs_file_extent_compression(path
.nodes
[0], fi
) !=
50 BTRFS_COMPRESS_NONE
) {
52 error("Extent for symlink %llu must not be compressed!", ino
);
55 if (btrfs_file_extent_ram_bytes(path
.nodes
[0], fi
) >=
56 root
->fs_info
->sectorsize
) {
58 error("Symlink %llu extent data too large (%llu)!\n",
59 ino
, btrfs_file_extent_ram_bytes(path
.nodes
[0], fi
));
62 read_extent_buffer(path
.nodes
[0], target
,
63 btrfs_file_extent_inline_start(fi
),
64 btrfs_file_extent_ram_bytes(path
.nodes
[0], fi
));
65 ret
= btrfs_file_extent_ram_bytes(path
.nodes
[0], fi
);
67 btrfs_release_path(&path
);
71 static int lookup_root_ref(struct btrfs_fs_info
*fs_info
,
72 u64 rootid
, u64
*root_ret
, u64
*dir_ret
)
74 struct btrfs_root
*root
= fs_info
->tree_root
;
75 struct btrfs_root_ref
*root_ref
;
76 struct btrfs_path path
;
80 btrfs_init_path(&path
);
81 key
.objectid
= rootid
;
82 key
.type
= BTRFS_ROOT_BACKREF_KEY
;
85 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
88 /* Should not happen */
93 ret
= btrfs_previous_item(root
, &path
, rootid
, BTRFS_ROOT_BACKREF_KEY
);
100 btrfs_item_key_to_cpu(path
.nodes
[0], &key
, path
.slots
[0]);
101 root_ref
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
102 struct btrfs_root_ref
);
103 *root_ret
= key
.offset
;
104 *dir_ret
= btrfs_root_ref_dirid(path
.nodes
[0], root_ref
);
106 btrfs_release_path(&path
);
111 * To get the parent inode of @ino of @root.
113 * @root_ret and @ino_ret will be filled.
115 * NOTE: This function is not reliable. It can only get one parent inode.
116 * The get the proper parent inode, we need a full VFS inodes stack to
119 static int get_parent_inode(struct btrfs_root
*root
, u64 ino
,
120 struct btrfs_root
**root_ret
, u64
*ino_ret
)
122 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
123 struct btrfs_path path
;
124 struct btrfs_key key
;
127 if (ino
== BTRFS_FIRST_FREE_OBJECTID
) {
128 u64 parent_root
= -1;
130 /* It's top level already, no more parent */
131 if (root
->root_key
.objectid
== BTRFS_FS_TREE_OBJECTID
) {
132 *root_ret
= fs_info
->fs_root
;
133 *ino_ret
= BTRFS_FIRST_FREE_OBJECTID
;
137 ret
= lookup_root_ref(fs_info
, root
->root_key
.objectid
,
138 &parent_root
, ino_ret
);
142 key
.objectid
= parent_root
;
143 key
.type
= BTRFS_ROOT_ITEM_KEY
;
144 key
.offset
= (u64
)-1;
145 *root_ret
= btrfs_read_fs_root(fs_info
, &key
);
146 if (IS_ERR(*root_ret
))
147 return PTR_ERR(*root_ret
);
152 btrfs_init_path(&path
);
154 key
.type
= BTRFS_INODE_REF_KEY
;
155 key
.offset
= (u64
)-1;
157 ret
= btrfs_search_slot(NULL
, root
, &key
, &path
, 0, 0);
160 /* Should not happen */
165 ret
= btrfs_previous_item(root
, &path
, ino
, BTRFS_INODE_REF_KEY
);
172 btrfs_item_key_to_cpu(path
.nodes
[0], &key
, path
.slots
[0]);
174 *ino_ret
= key
.offset
;
176 btrfs_release_path(&path
);
180 static inline int next_length(const char *path
)
183 while (*path
!= '\0' && *path
!= '/') {
186 if (res
> BTRFS_NAME_LEN
)
192 static inline const char *skip_current_directories(const char *cur
)
197 else if (cur
[0] == '.' && cur
[1] == '/')
207 * Resolve one filename of @ino of @root.
209 * key_ret: The child key (either INODE_ITEM or ROOT_ITEM type)
210 * type_ret: BTRFS_FT_* of the child inode.
212 * Return 0 with above members filled.
213 * Return <0 for error.
215 static int resolve_one_filename(struct btrfs_root
*root
, u64 ino
,
216 const char *name
, int namelen
,
217 struct btrfs_key
*key_ret
, u8
*type_ret
)
219 struct btrfs_dir_item
*dir_item
;
220 struct btrfs_path path
;
223 btrfs_init_path(&path
);
225 dir_item
= btrfs_lookup_dir_item(NULL
, root
, &path
, ino
, name
,
227 if (IS_ERR(dir_item
)) {
228 ret
= PTR_ERR(dir_item
);
232 btrfs_dir_item_key_to_cpu(path
.nodes
[0], dir_item
, key_ret
);
233 *type_ret
= btrfs_dir_type(path
.nodes
[0], dir_item
);
235 btrfs_release_path(&path
);
240 * Resolve a full path @filename. The start point is @ino of @root.
242 * The result will be filled into @root_ret, @ino_ret and @type_ret.
244 int btrfs_lookup_path(struct btrfs_root
*root
, u64 ino
, const char *filename
,
245 struct btrfs_root
**root_ret
, u64
*ino_ret
,
246 u8
*type_ret
, int symlink_limit
)
248 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
249 struct btrfs_root
*next_root
;
250 struct btrfs_key key
;
251 const char *cur
= filename
;
254 u8 type
= BTRFS_FT_UNKNOWN
;
258 /* If the path is absolute path, also search from fs root */
260 root
= fs_info
->fs_root
;
261 ino
= btrfs_root_dirid(&root
->root_item
);
265 while (*cur
!= '\0') {
266 cur
= skip_current_directories(cur
);
268 len
= next_length(cur
);
269 if (len
> BTRFS_NAME_LEN
) {
270 error("%s: Name too long at \"%.*s\"", __func__
,
271 BTRFS_NAME_LEN
, cur
);
272 return -ENAMETOOLONG
;
275 if (len
== 1 && cur
[0] == '.')
278 if (len
== 2 && cur
[0] == '.' && cur
[1] == '.') {
279 /* Go one level up */
280 ret
= get_parent_inode(root
, ino
, &next_root
, &next_ino
);
291 ret
= resolve_one_filename(root
, ino
, cur
, len
, &key
, &type
);
295 if (key
.type
== BTRFS_ROOT_ITEM_KEY
) {
296 /* Child inode is a subvolume */
298 next_root
= btrfs_read_fs_root(fs_info
, &key
);
299 if (IS_ERR(next_root
))
300 return PTR_ERR(next_root
);
302 ino
= btrfs_root_dirid(&root
->root_item
);
303 } else if (type
== BTRFS_FT_SYMLINK
&& symlink_limit
>= 0) {
304 /* Child inode is a symlink */
308 if (symlink_limit
== 0) {
309 error("%s: Too much symlinks!", __func__
);
312 target
= malloc(fs_info
->sectorsize
);
315 ret
= btrfs_readlink(root
, key
.objectid
, target
);
322 ret
= btrfs_lookup_path(root
, ino
, target
, &next_root
,
323 &next_ino
, &next_type
,
331 /* Child inode is an inode */
338 /* We haven't found anything, but still get no error? */
339 if (type
== BTRFS_FT_UNKNOWN
&& !ret
)
352 * Read out inline extent.
354 * Since inline extent should only exist for offset 0, no need for extra
356 * Truncating should be handled by the caller.
358 * Return the number of bytes read.
359 * Return <0 for error.
361 int btrfs_read_extent_inline(struct btrfs_path
*path
,
362 struct btrfs_file_extent_item
*fi
, char *dest
)
364 struct extent_buffer
*leaf
= path
->nodes
[0];
365 int slot
= path
->slots
[0];
372 csize
= btrfs_file_extent_inline_item_len(leaf
, btrfs_item_nr(slot
));
373 if (btrfs_file_extent_compression(leaf
, fi
) == BTRFS_COMPRESS_NONE
) {
374 /* Uncompressed, just read it out */
375 read_extent_buffer(leaf
, dest
,
376 btrfs_file_extent_inline_start(fi
),
381 /* Compressed extent, prepare the compressed and data buffer */
382 dsize
= btrfs_file_extent_ram_bytes(leaf
, fi
);
383 cbuf
= malloc(csize
);
384 dbuf
= malloc(dsize
);
385 if (!cbuf
|| !dbuf
) {
389 read_extent_buffer(leaf
, cbuf
, btrfs_file_extent_inline_start(fi
),
391 ret
= btrfs_decompress(btrfs_file_extent_compression(leaf
, fi
),
392 cbuf
, csize
, dbuf
, dsize
);
393 if (ret
== (u32
)-1) {
398 * The compressed part ends before sector boundary, the remaining needs
402 memset(dbuf
+ ret
, 0, dsize
- ret
);
403 memcpy(dest
, dbuf
, dsize
);
412 * Read out regular extent.
414 * Truncating should be handled by the caller.
416 * @offset and @len should not cross the extent boundary.
417 * Return the number of bytes read.
418 * Return <0 for error.
420 int btrfs_read_extent_reg(struct btrfs_path
*path
,
421 struct btrfs_file_extent_item
*fi
, u64 offset
,
424 struct extent_buffer
*leaf
= path
->nodes
[0];
425 struct btrfs_fs_info
*fs_info
= leaf
->fs_info
;
426 struct btrfs_key key
;
427 u64 extent_num_bytes
;
434 bool finished
= false;
437 int slot
= path
->slots
[0];
440 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
441 extent_num_bytes
= btrfs_file_extent_num_bytes(leaf
, fi
);
442 ASSERT(IS_ALIGNED(offset
, fs_info
->sectorsize
) &&
443 IS_ALIGNED(len
, fs_info
->sectorsize
));
444 ASSERT(offset
>= key
.offset
&&
445 offset
+ len
<= key
.offset
+ extent_num_bytes
);
447 /* Preallocated or hole , fill @dest with zero */
448 if (btrfs_file_extent_type(leaf
, fi
) == BTRFS_FILE_EXTENT_PREALLOC
||
449 btrfs_file_extent_disk_bytenr(leaf
, fi
) == 0) {
450 memset(dest
, 0, len
);
454 if (btrfs_file_extent_compression(leaf
, fi
) == BTRFS_COMPRESS_NONE
) {
457 logical
= btrfs_file_extent_disk_bytenr(leaf
, fi
) +
458 btrfs_file_extent_offset(leaf
, fi
) +
462 num_copies
= btrfs_num_copies(fs_info
, logical
, len
);
463 for (i
= 1; i
<= num_copies
; i
++) {
464 ret
= read_extent_data(fs_info
, dest
, logical
, &read
, i
);
465 if (ret
< 0 || read
!= len
)
475 csize
= btrfs_file_extent_disk_num_bytes(leaf
, fi
);
476 dsize
= btrfs_file_extent_ram_bytes(leaf
, fi
);
477 disk_bytenr
= btrfs_file_extent_disk_bytenr(leaf
, fi
);
478 num_copies
= btrfs_num_copies(fs_info
, disk_bytenr
, csize
);
480 cbuf
= malloc_cache_aligned(csize
);
481 dbuf
= malloc_cache_aligned(dsize
);
482 if (!cbuf
|| !dbuf
) {
486 /* For compressed extent, we must read the whole on-disk extent */
487 for (i
= 1; i
<= num_copies
; i
++) {
489 ret
= read_extent_data(fs_info
, cbuf
, disk_bytenr
,
491 if (ret
< 0 || read
!= csize
)
501 ret
= btrfs_decompress(btrfs_file_extent_compression(leaf
, fi
), cbuf
,
503 if (ret
== (u32
)-1) {
508 * The compressed part ends before sector boundary, the remaining needs
512 memset(dbuf
+ ret
, 0, dsize
- ret
);
513 /* Then copy the needed part */
514 memcpy(dest
, dbuf
+ btrfs_file_extent_offset(leaf
, fi
), len
);
523 * Get the first file extent that covers bytenr @file_offset.
525 * @file_offset must be aligned to sectorsize.
527 * return 0 for found, and path points to the file extent.
528 * return >0 for not found, and fill @next_offset.
529 * @next_offset can be 0 if there is no next file extent.
530 * return <0 for error.
532 static int lookup_data_extent(struct btrfs_root
*root
, struct btrfs_path
*path
,
533 u64 ino
, u64 file_offset
, u64
*next_offset
)
535 struct btrfs_key key
;
536 struct btrfs_file_extent_item
*fi
;
540 ASSERT(IS_ALIGNED(file_offset
, root
->fs_info
->sectorsize
));
542 key
.type
= BTRFS_EXTENT_DATA_KEY
;
543 key
.offset
= file_offset
;
545 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
546 /* Error or we're already at the file extent */
549 /* Check previous file extent */
550 ret
= btrfs_previous_item(root
, path
, ino
, BTRFS_EXTENT_DATA_KEY
);
555 /* Now the key.offset must be smaller than @file_offset */
556 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
557 if (key
.objectid
!= ino
||
558 key
.type
!= BTRFS_EXTENT_DATA_KEY
)
561 fi
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
562 struct btrfs_file_extent_item
);
563 extent_type
= btrfs_file_extent_type(path
->nodes
[0], fi
);
564 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
) {
565 if (file_offset
== 0)
567 /* Inline extent should be the only extent, no next extent. */
572 /* This file extent covers @file_offset */
573 if (key
.offset
<= file_offset
&& key
.offset
+
574 btrfs_file_extent_num_bytes(path
->nodes
[0], fi
) > file_offset
)
577 ret
= btrfs_next_item(root
, path
);
585 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
586 fi
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
587 struct btrfs_file_extent_item
);
588 /* Next next data extent */
589 if (key
.objectid
!= ino
||
590 key
.type
!= BTRFS_EXTENT_DATA_KEY
) {
594 /* Current file extent already beyond @file_offset */
595 if (key
.offset
> file_offset
) {
596 *next_offset
= key
.offset
;
599 /* This file extent covers @file_offset */
600 if (key
.offset
<= file_offset
&& key
.offset
+
601 btrfs_file_extent_num_bytes(path
->nodes
[0], fi
) > file_offset
)
603 /* This file extent ends before @file_offset, check next */
604 ret
= btrfs_next_item(root
, path
);
611 btrfs_item_key_to_cpu(path
->nodes
[0], &key
, path
->slots
[0]);
612 if (key
.type
!= BTRFS_EXTENT_DATA_KEY
|| key
.objectid
!= ino
) {
616 *next_offset
= key
.offset
;
620 static int read_and_truncate_page(struct btrfs_path
*path
,
621 struct btrfs_file_extent_item
*fi
,
622 int start
, int len
, char *dest
)
624 struct extent_buffer
*leaf
= path
->nodes
[0];
625 struct btrfs_fs_info
*fs_info
= leaf
->fs_info
;
626 u64 aligned_start
= round_down(start
, fs_info
->sectorsize
);
629 int page_off
= start
- aligned_start
;
630 int page_len
= fs_info
->sectorsize
- page_off
;
633 ASSERT(start
+ len
<= aligned_start
+ fs_info
->sectorsize
);
634 buf
= malloc_cache_aligned(fs_info
->sectorsize
);
638 extent_type
= btrfs_file_extent_type(leaf
, fi
);
639 if (extent_type
== BTRFS_FILE_EXTENT_INLINE
) {
640 ret
= btrfs_read_extent_inline(path
, fi
, buf
);
641 memcpy(dest
, buf
+ page_off
, min(page_len
, ret
));
646 ret
= btrfs_read_extent_reg(path
, fi
,
647 round_down(start
, fs_info
->sectorsize
),
648 fs_info
->sectorsize
, buf
);
653 memcpy(dest
, buf
+ page_off
, page_len
);
658 int btrfs_file_read(struct btrfs_root
*root
, u64 ino
, u64 file_offset
, u64 len
,
661 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
662 struct btrfs_file_extent_item
*fi
;
663 struct btrfs_path path
;
664 struct btrfs_key key
;
665 u64 aligned_start
= round_down(file_offset
, fs_info
->sectorsize
);
666 u64 aligned_end
= round_down(file_offset
+ len
, fs_info
->sectorsize
);
668 u64 cur
= aligned_start
;
671 btrfs_init_path(&path
);
673 /* Set the whole dest all zero, so we won't need to bother holes */
674 memset(dest
, 0, len
);
676 /* Read out the leading unaligned part */
677 if (aligned_start
!= file_offset
) {
678 ret
= lookup_data_extent(root
, &path
, ino
, aligned_start
,
683 /* Read the unaligned part out*/
684 fi
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
685 struct btrfs_file_extent_item
);
686 ret
= read_and_truncate_page(&path
, fi
, file_offset
,
687 round_up(file_offset
, fs_info
->sectorsize
) -
691 cur
+= fs_info
->sectorsize
;
693 /* The whole file is a hole */
695 memset(dest
, 0, len
);
702 /* Read the aligned part */
703 while (cur
< aligned_end
) {
704 u64 extent_num_bytes
;
707 btrfs_release_path(&path
);
708 ret
= lookup_data_extent(root
, &path
, ino
, cur
, &next_offset
);
712 /* No next, direct exit */
718 * Find a extent gap, mostly caused by NO_HOLE feature.
719 * Just to next offset directly.
721 if (next_offset
> cur
) {
726 fi
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
727 struct btrfs_file_extent_item
);
728 btrfs_item_key_to_cpu(path
.nodes
[0], &key
, path
.slots
[0]);
729 type
= btrfs_file_extent_type(path
.nodes
[0], fi
);
730 if (type
== BTRFS_FILE_EXTENT_INLINE
) {
731 ret
= btrfs_read_extent_inline(&path
, fi
, dest
);
734 /* Skip holes, as we have zeroed the dest */
735 if (type
== BTRFS_FILE_EXTENT_PREALLOC
||
736 btrfs_file_extent_disk_bytenr(path
.nodes
[0], fi
) == 0) {
737 cur
= key
.offset
+ btrfs_file_extent_num_bytes(
742 /* Read the remaining part of the extent */
743 extent_num_bytes
= btrfs_file_extent_num_bytes(path
.nodes
[0],
745 ret
= btrfs_read_extent_reg(&path
, fi
, cur
,
746 min(extent_num_bytes
, aligned_end
- cur
),
747 dest
+ cur
- file_offset
);
750 cur
+= min(extent_num_bytes
, aligned_end
- cur
);
753 /* Read the tailing unaligned part*/
754 if (file_offset
+ len
!= aligned_end
) {
755 btrfs_release_path(&path
);
756 ret
= lookup_data_extent(root
, &path
, ino
, aligned_end
,
758 /* <0 is error, >0 means no extent */
761 fi
= btrfs_item_ptr(path
.nodes
[0], path
.slots
[0],
762 struct btrfs_file_extent_item
);
763 ret
= read_and_truncate_page(&path
, fi
, aligned_end
,
764 file_offset
+ len
- aligned_end
,
765 dest
+ aligned_end
- file_offset
);
768 btrfs_release_path(&path
);