This is needed for BTRFS.

Signed-off-by: Marek Behun marek.behun@nic.cz

create mode 100644 lib/crc32c.c

diff --git a/include/u-boot/crc.h b/include/u-boot/crc.h index 6764d58bab..6d08f5df98 100644 --- a/include/u-boot/crc.h +++ b/include/u-boot/crc.h @@ -28,4 +28,8 @@ uint32_t crc32_no_comp (uint32_t, const unsigned char *, uint); void crc32_wd_buf(const unsigned char *input, uint ilen, unsigned char *output, uint chunk_sz);

+/* lib/crc32c.c */ +void crc32c_init(uint32_t *, uint32_t); +uint32_t crc32c_cal(uint32_t, const char *, int, uint32_t *); + #endif /* _UBOOT_CRC_H */ diff --git a/lib/Kconfig b/lib/Kconfig index fe337acaeb..29e55dbe1d 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -146,6 +146,9 @@ config SHA_PROG_HW_ACCEL config MD5 bool

+config CRC32C + bool + endmenu

menu "Compression Support" diff --git a/lib/Makefile b/lib/Makefile index 2eef1eb80e..a58ce0f815 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -67,6 +67,7 @@ obj-y += display_options.o CFLAGS_display_options.o := $(if $(BUILD_TAG),-DBUILD_TAG='"$(BUILD_TAG)"') obj-$(CONFIG_BCH) += bch.o obj-y += crc32.o +obj-$(CONFIG_CRC32C) += crc32c.o obj-y += ctype.o obj-y += div64.o obj-y += hang.o diff --git a/lib/crc32c.c b/lib/crc32c.c new file mode 100644 index 0000000000..322c08ff5d --- /dev/null +++ b/lib/crc32c.c @@ -0,0 +1,38 @@ +/* + * Copied from Linux kernel crypto/crc32c.c + * Copyright (c) 2004 Cisco Systems, Inc. + * Copyright (c) 2008 Herbert Xu herbert@gondor.apana.org.au + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include <common.h> +#include <compiler.h> + +uint32_t crc32c_cal(uint32_t crc, const char *data, int length, + uint32_t *crc32c_table) +{ + while (length--) + crc = crc32c_table[(u8)(crc ^ *data++)] ^ (crc >> 8); + + return crc; +} + +void crc32c_init(uint32_t *crc32c_table, uint32_t pol) +{ + int i, j; + uint32_t v; + const uint32_t poly = pol; /* Bit-reflected CRC32C polynomial */ + + for (i = 0; i < 256; i++) { + v = i; + for (j = 0; j < 8; j++) + v = (v >> 1) ^ ((v & 1) ? poly : 0); + + crc32c_table[i] = v; + } +}

The ext4, reiserfs and zfs filesystems all have their own implementation of the same function, *_devread. Generalize this function into fs_devread and put the code into fs/fs_internal.c.

Signed-off-by: Marek Behun marek.behun@nic.cz

create mode 100644 fs/fs_internal.c create mode 100644 include/fs_internal.h

diff --git a/fs/Makefile b/fs/Makefile index 5770f41c0b..e5bf0df26f 100644 --- a/fs/Makefile +++ b/fs/Makefile @@ -10,7 +10,7 @@ ifdef CONFIG_SPL_BUILD obj-$(CONFIG_SPL_FAT_SUPPORT) += fat/ obj-$(CONFIG_SPL_EXT_SUPPORT) += ext4/ else -obj-y += fs.o +obj-y += fs.o fs_internal.o

obj-$(CONFIG_FS_CBFS) += cbfs/ obj-$(CONFIG_CMD_CRAMFS) += cramfs/ diff --git a/fs/ext4/dev.c b/fs/ext4/dev.c index ae2ba6a901..f04fa08f64 100644 --- a/fs/ext4/dev.c +++ b/fs/ext4/dev.c @@ -26,7 +26,7 @@ #include <common.h> #include <blk.h> #include <config.h> -#include <memalign.h> +#include <fs_internal.h> #include <ext4fs.h> #include <ext_common.h> #include "ext4_common.h" @@ -47,85 +47,11 @@ void ext4fs_set_blk_dev(struct blk_desc *rbdd, disk_partition_t *info) get_fs()->dev_desc->log2blksz; }

-int ext4fs_devread(lbaint_t sector, int byte_offset, int byte_len, char *buf) +int ext4fs_devread(lbaint_t sector, int byte_offset, int byte_len, + char *buffer) { - unsigned block_len; - int log2blksz = ext4fs_blk_desc->log2blksz; - ALLOC_CACHE_ALIGN_BUFFER(char, sec_buf, (ext4fs_blk_desc ? - ext4fs_blk_desc->blksz : - 0)); - if (ext4fs_blk_desc == NULL) { - printf("** Invalid Block Device Descriptor (NULL)\n"); - return 0; - } - - /* Check partition boundaries */ - if ((sector + ((byte_offset + byte_len - 1) >> log2blksz)) - >= part_info->size) { - printf("%s read outside partition " LBAFU "\n", __func__, - sector); - return 0; - } - - /* Get the read to the beginning of a partition */ - sector += byte_offset >> log2blksz; - byte_offset &= ext4fs_blk_desc->blksz - 1; - - debug(" <" LBAFU ", %d, %d>\n", sector, byte_offset, byte_len); - - if (byte_offset != 0) { - int readlen; - /* read first part which isn't aligned with start of sector */ - if (blk_dread(ext4fs_blk_desc, part_info->start + sector, 1, - (void *)sec_buf) != 1) { - printf(" ** ext2fs_devread() read error **\n"); - return 0; - } - readlen = min((int)ext4fs_blk_desc->blksz - byte_offset, - byte_len); - memcpy(buf, sec_buf + byte_offset, readlen); - buf += readlen; - byte_len -= readlen; - sector++; - } - - if (byte_len == 0) - return 1; - - /* read sector aligned part */ - block_len = byte_len & ~(ext4fs_blk_desc->blksz - 1); - - if (block_len == 0) { - ALLOC_CACHE_ALIGN_BUFFER(u8, p, ext4fs_blk_desc->blksz); - - block_len = ext4fs_blk_desc->blksz; - blk_dread(ext4fs_blk_desc, part_info->start + sector, 1, - (void *)p); - memcpy(buf, p, byte_len); - return 1; - } - - if (blk_dread(ext4fs_blk_desc, part_info->start + sector, - block_len >> log2blksz, (void *)buf) != - block_len >> log2blksz) { - printf(" ** %s read error - block\n", __func__); - return 0; - } - block_len = byte_len & ~(ext4fs_blk_desc->blksz - 1); - buf += block_len; - byte_len -= block_len; - sector += block_len / ext4fs_blk_desc->blksz; - - if (byte_len != 0) { - /* read rest of data which are not in whole sector */ - if (blk_dread(ext4fs_blk_desc, part_info->start + sector, 1, - (void *)sec_buf) != 1) { - printf("* %s read error - last part\n", __func__); - return 0; - } - memcpy(buf, sec_buf, byte_len); - } - return 1; + return fs_devread(get_fs()->dev_desc, part_info, sector, byte_offset, + byte_len, buffer); }

int ext4_read_superblock(char *buffer) diff --git a/fs/fs_internal.c b/fs/fs_internal.c new file mode 100644 index 0000000000..58b441030c --- /dev/null +++ b/fs/fs_internal.c @@ -0,0 +1,92 @@ +/* + * 2017 by Marek Behun marek.behun@nic.cz + * + * Derived from code in ext4/dev.c, which was based on reiserfs/dev.c + * + * SPDX-License-Identifier: GPL-2.0 + */ + +#include <common.h> +#include <compiler.h> +#include <part.h> +#include <memalign.h> + +int fs_devread(struct blk_desc *blk, disk_partition_t *partition, + lbaint_t sector, int byte_offset, int byte_len, char *buf) +{ + unsigned block_len; + int log2blksz = blk->log2blksz; + ALLOC_CACHE_ALIGN_BUFFER(char, sec_buf, (blk ? blk->blksz : 0)); + if (blk == NULL) { + printf("** Invalid Block Device Descriptor (NULL)\n"); + return 0; + } + + /* Check partition boundaries */ + if ((sector + ((byte_offset + byte_len - 1) >> log2blksz)) + >= partition->size) { + printf("%s read outside partition " LBAFU "\n", __func__, + sector); + return 0; + } + + /* Get the read to the beginning of a partition */ + sector += byte_offset >> log2blksz; + byte_offset &= blk->blksz - 1; + + debug(" <" LBAFU ", %d, %d>\n", sector, byte_offset, byte_len); + + if (byte_offset != 0) { + int readlen; + /* read first part which isn't aligned with start of sector */ + if (blk_dread(blk, partition->start + sector, 1, + (void *)sec_buf) != 1) { + printf(" ** %s read error **\n", __func__); + return 0; + } + readlen = min((int)blk->blksz - byte_offset, + byte_len); + memcpy(buf, sec_buf + byte_offset, readlen); + buf += readlen; + byte_len -= readlen; + sector++; + } + + if (byte_len == 0) + return 1; + + /* read sector aligned part */ + block_len = byte_len & ~(blk->blksz - 1); + + if (block_len == 0) { + ALLOC_CACHE_ALIGN_BUFFER(u8, p, blk->blksz); + + block_len = blk->blksz; + blk_dread(blk, partition->start + sector, 1, + (void *)p); + memcpy(buf, p, byte_len); + return 1; + } + + if (blk_dread(blk, partition->start + sector, + block_len >> log2blksz, (void *)buf) != + block_len >> log2blksz) { + printf(" ** %s read error - block\n", __func__); + return 0; + } + block_len = byte_len & ~(blk->blksz - 1); + buf += block_len; + byte_len -= block_len; + sector += block_len / blk->blksz; + + if (byte_len != 0) { + /* read rest of data which are not in whole sector */ + if (blk_dread(blk, partition->start + sector, 1, + (void *)sec_buf) != 1) { + printf("* %s read error - last part\n", __func__); + return 0; + } + memcpy(buf, sec_buf, byte_len); + } + return 1; +} diff --git a/fs/reiserfs/dev.c b/fs/reiserfs/dev.c index 5a1ab0a364..7b786e4ed3 100644 --- a/fs/reiserfs/dev.c +++ b/fs/reiserfs/dev.c @@ -9,7 +9,7 @@ #include <common.h> #include <config.h> #include <reiserfs.h> - +#include <fs_internal.h> #include "reiserfs_private.h"

static struct blk_desc *reiserfs_blk_desc; @@ -22,78 +22,8 @@ void reiserfs_set_blk_dev(struct blk_desc *rbdd, disk_partition_t *info) part_info = info; }

- -int reiserfs_devread (int sector, int byte_offset, int byte_len, char *buf) +int reiserfs_devread(int sector, int byte_offset, int byte_len, char *buf) { - char sec_buf[SECTOR_SIZE]; - unsigned block_len; -/* - unsigned len = byte_len; - u8 *start = buf; -*/ - /* - * Check partition boundaries - */ - if (sector < 0 - || ((sector + ((byte_offset + byte_len - 1) >> SECTOR_BITS)) - >= part_info->size)) { -/* errnum = ERR_OUTSIDE_PART; */ - printf (" ** reiserfs_devread() read outside partition\n"); - return 0; - } - - /* - * Get the read to the beginning of a partition. - */ - sector += byte_offset >> SECTOR_BITS; - byte_offset &= SECTOR_SIZE - 1; - -#if defined(DEBUG) - printf (" <%d, %d, %d> ", sector, byte_offset, byte_len); -#endif - - - if (reiserfs_blk_desc == NULL) - return 0; - - - if (byte_offset != 0) { - /* read first part which isn't aligned with start of sector */ - if (reiserfs_blk_desc->block_read(reiserfs_blk_desc, - part_info->start + sector, - 1, (void *)sec_buf) != 1) { - printf (" ** reiserfs_devread() read error\n"); - return 0; - } - memcpy(buf, sec_buf+byte_offset, min(SECTOR_SIZE-byte_offset, byte_len)); - buf+=min(SECTOR_SIZE-byte_offset, byte_len); - byte_len-=min(SECTOR_SIZE-byte_offset, byte_len); - sector++; - } - - /* read sector aligned part */ - block_len = byte_len & ~(SECTOR_SIZE-1); - if (reiserfs_blk_desc->block_read(reiserfs_blk_desc, - part_info->start + sector, - block_len / SECTOR_SIZE, (void *)buf) - != block_len/SECTOR_SIZE) { - printf (" ** reiserfs_devread() read error - block\n"); - return 0; - } - buf+=block_len; - byte_len-=block_len; - sector+= block_len/SECTOR_SIZE; - - if ( byte_len != 0 ) { - /* read rest of data which are not in whole sector */ - if (reiserfs_blk_desc->block_read(reiserfs_blk_desc, - part_info->start + sector, - 1, (void *)sec_buf) != 1) { - printf (" ** reiserfs_devread() read error - last part\n"); - return 0; - } - memcpy(buf, sec_buf, byte_len); - } - - return 1; + return fs_devread(reiserfs_blk_desc, part_info, sector, byte_offset, + byte_len, buf); } diff --git a/fs/zfs/dev.c b/fs/zfs/dev.c index 2f409e66cd..7dda42b48b 100644 --- a/fs/zfs/dev.c +++ b/fs/zfs/dev.c @@ -11,6 +11,7 @@

#include <common.h> #include <config.h> +#include <fs_internal.h> #include <zfs_common.h>

static struct blk_desc *zfs_blk_desc; @@ -25,87 +26,6 @@ void zfs_set_blk_dev(struct blk_desc *rbdd, disk_partition_t *info) /* err */ int zfs_devread(int sector, int byte_offset, int byte_len, char *buf) { - short sec_buffer[SECTOR_SIZE/sizeof(short)]; - char *sec_buf = (char *)sec_buffer; - unsigned block_len; - - /* - * Check partition boundaries - */ - if ((sector < 0) || - ((sector + ((byte_offset + byte_len - 1) >> SECTOR_BITS)) >= - part_info->size)) { - /* errnum = ERR_OUTSIDE_PART; */ - printf(" ** zfs_devread() read outside partition sector %d\n", sector); - return 1; - } - - /* - * Get the read to the beginning of a partition. - */ - sector += byte_offset >> SECTOR_BITS; - byte_offset &= SECTOR_SIZE - 1; - - debug(" <%d, %d, %d>\n", sector, byte_offset, byte_len); - - if (zfs_blk_desc == NULL) { - printf("** Invalid Block Device Descriptor (NULL)\n"); - return 1; - } - - if (byte_offset != 0) { - /* read first part which isn't aligned with start of sector */ - if (zfs_blk_desc->block_read(zfs_blk_desc, - part_info->start + sector, 1, - (void *)sec_buf) != 1) { - printf(" ** zfs_devread() read error **\n"); - return 1; - } - memcpy(buf, sec_buf + byte_offset, - min(SECTOR_SIZE - byte_offset, byte_len)); - buf += min(SECTOR_SIZE - byte_offset, byte_len); - byte_len -= min(SECTOR_SIZE - byte_offset, byte_len); - sector++; - } - - if (byte_len == 0) - return 0; - - /* read sector aligned part */ - block_len = byte_len & ~(SECTOR_SIZE - 1); - - if (block_len == 0) { - u8 p[SECTOR_SIZE]; - - block_len = SECTOR_SIZE; - zfs_blk_desc->block_read(zfs_blk_desc, - part_info->start + sector, - 1, (void *)p); - memcpy(buf, p, byte_len); - return 0; - } - - if (zfs_blk_desc->block_read(zfs_blk_desc, part_info->start + sector, - block_len / SECTOR_SIZE, - (void *)buf) != block_len / SECTOR_SIZE) { - printf(" ** zfs_devread() read error - block\n"); - return 1; - } - - block_len = byte_len & ~(SECTOR_SIZE - 1); - buf += block_len; - byte_len -= block_len; - sector += block_len / SECTOR_SIZE; - - if (byte_len != 0) { - /* read rest of data which are not in whole sector */ - if (zfs_blk_desc->block_read(zfs_blk_desc, - part_info->start + sector, - 1, (void *)sec_buf) != 1) { - printf(" ** zfs_devread() read error - last part\n"); - return 1; - } - memcpy(buf, sec_buf, byte_len); - } - return 0; + return fs_devread(zfs_blk_desc, part_info, sector, byte_offset, + byte_len, buf); } diff --git a/include/fs_internal.h b/include/fs_internal.h new file mode 100644 index 0000000000..9d6dddd841 --- /dev/null +++ b/include/fs_internal.h @@ -0,0 +1,17 @@ +/* + * 2017 by Marek Behun marek.behun@nic.cz + * + * Derived from code in ext4/dev.c, which was based on reiserfs/dev.c + * + * SPDX-License-Identifier: GPL-2.0 + */ + +#ifndef __U_BOOT_FS_INTERNAL_H__ +#define __U_BOOT_FS_INTERNAL_H__ + +#include <part.h> + +int fs_devread(struct blk_desc *, disk_partition_t *, lbaint_t, int, int, + char *); + +#endif /* __U_BOOT_FS_INTERNAL_H__ */

Add a header variadic-macro.h which defines the CALL_MACRO_FOR_EACH marco.

This macro can be used as follows: #define TEST(x) CALL_MACRO_FOR_EACH(TEST, a, b, c, d)

This will expand to TEST(a) TEST(b) TEST(c) TEST(d)

The nice thing is that CALL_MACRO_FOR_EACH is a variadic macro, thus the number of arguments can vary (although it has an upper limit - in this implementation 32 arguments).

Signed-off-by: Marek Behun marek.behun@nic.cz

create mode 100644 include/u-boot/variadic-macro.h

diff --git a/include/u-boot/variadic-macro.h b/include/u-boot/variadic-macro.h new file mode 100644 index 0000000000..922beafcea --- /dev/null +++ b/include/u-boot/variadic-macro.h @@ -0,0 +1,59 @@ +/* + * Helper for work with variadic macros + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#ifndef __VARIADIC_MACRO_H__ +#define __VARIADIC_MACRO_H__ + +#define _VM_GET_NTH_ARG(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, \ + _14, _15, _16, _17, _18, _19, _20, _21, _22, _23, _24, _25, _26, _27, \ + _28, _29, _30, _31, _32, N, ...) N + +#define _VM_HELP_0(_call, ...) +#define _VM_HELP_1(_call, x, ...) _call(x) +#define _VM_HELP_2(_call, x, ...) _call(x) _VM_HELP_1(_call, __VA_ARGS__) +#define _VM_HELP_3(_call, x, ...) _call(x) _VM_HELP_2(_call, __VA_ARGS__) +#define _VM_HELP_4(_call, x, ...) _call(x) _VM_HELP_3(_call, __VA_ARGS__) +#define _VM_HELP_5(_call, x, ...) _call(x) _VM_HELP_4(_call, __VA_ARGS__) +#define _VM_HELP_6(_call, x, ...) _call(x) _VM_HELP_5(_call, __VA_ARGS__) +#define _VM_HELP_7(_call, x, ...) _call(x) _VM_HELP_6(_call, __VA_ARGS__) +#define _VM_HELP_8(_call, x, ...) _call(x) _VM_HELP_7(_call, __VA_ARGS__) +#define _VM_HELP_9(_call, x, ...) _call(x) _VM_HELP_8(_call, __VA_ARGS__) +#define _VM_HELP_10(_call, x, ...) _call(x) _VM_HELP_9(_call, __VA_ARGS__) +#define _VM_HELP_11(_call, x, ...) _call(x) _VM_HELP_10(_call, __VA_ARGS__) +#define _VM_HELP_12(_call, x, ...) _call(x) _VM_HELP_11(_call, __VA_ARGS__) +#define _VM_HELP_13(_call, x, ...) _call(x) _VM_HELP_12(_call, __VA_ARGS__) +#define _VM_HELP_14(_call, x, ...) _call(x) _VM_HELP_13(_call, __VA_ARGS__) +#define _VM_HELP_15(_call, x, ...) _call(x) _VM_HELP_14(_call, __VA_ARGS__) +#define _VM_HELP_16(_call, x, ...) _call(x) _VM_HELP_15(_call, __VA_ARGS__) +#define _VM_HELP_17(_call, x, ...) _call(x) _VM_HELP_16(_call, __VA_ARGS__) +#define _VM_HELP_18(_call, x, ...) _call(x) _VM_HELP_17(_call, __VA_ARGS__) +#define _VM_HELP_19(_call, x, ...) _call(x) _VM_HELP_18(_call, __VA_ARGS__) +#define _VM_HELP_20(_call, x, ...) _call(x) _VM_HELP_19(_call, __VA_ARGS__) +#define _VM_HELP_21(_call, x, ...) _call(x) _VM_HELP_20(_call, __VA_ARGS__) +#define _VM_HELP_22(_call, x, ...) _call(x) _VM_HELP_21(_call, __VA_ARGS__) +#define _VM_HELP_23(_call, x, ...) _call(x) _VM_HELP_22(_call, __VA_ARGS__) +#define _VM_HELP_24(_call, x, ...) _call(x) _VM_HELP_23(_call, __VA_ARGS__) +#define _VM_HELP_25(_call, x, ...) _call(x) _VM_HELP_24(_call, __VA_ARGS__) +#define _VM_HELP_26(_call, x, ...) _call(x) _VM_HELP_25(_call, __VA_ARGS__) +#define _VM_HELP_27(_call, x, ...) _call(x) _VM_HELP_26(_call, __VA_ARGS__) +#define _VM_HELP_28(_call, x, ...) _call(x) _VM_HELP_27(_call, __VA_ARGS__) +#define _VM_HELP_29(_call, x, ...) _call(x) _VM_HELP_28(_call, __VA_ARGS__) +#define _VM_HELP_30(_call, x, ...) _call(x) _VM_HELP_29(_call, __VA_ARGS__) +#define _VM_HELP_31(_call, x, ...) _call(x) _VM_HELP_30(_call, __VA_ARGS__) + +#define CALL_MACRO_FOR_EACH(x, ...) \ + _VM_GET_NTH_ARG("", ##__VA_ARGS__, _VM_HELP_31, _VM_HELP_30, \ + _VM_HELP_29, _VM_HELP_28, _VM_HELP_27, _VM_HELP_26, _VM_HELP_25, \ + _VM_HELP_24, _VM_HELP_23, _VM_HELP_22, _VM_HELP_21, _VM_HELP_20, \ + _VM_HELP_19, _VM_HELP_18, _VM_HELP_17, _VM_HELP_16, _VM_HELP_15, \ + _VM_HELP_14, _VM_HELP_13, _VM_HELP_12, _VM_HELP_11, _VM_HELP_10, \ + _VM_HELP_9, _VM_HELP_8, _VM_HELP_7, _VM_HELP_6, _VM_HELP_5, \ + _VM_HELP_4, _VM_HELP_3, _VM_HELP_2, _VM_HELP_1, \ + _VM_HELP_0)(x, __VA_ARGS__) + +#endif /* __VARIADIC_MACRO_H__ */

Add btrfs_tree.h and ctree.h from Linux which contains constants and structures for the BTRFS filesystem.

Signed-off-by: Marek Behun marek.behun@nic.cz

create mode 100644 fs/btrfs/btrfs_tree.h create mode 100644 fs/btrfs/ctree.h

diff --git a/fs/btrfs/btrfs_tree.h b/fs/btrfs/btrfs_tree.h new file mode 100644 index 0000000000..f171b24288 --- /dev/null +++ b/fs/btrfs/btrfs_tree.h @@ -0,0 +1,766 @@ +/* + * From linux/include/uapi/linux/btrfs_tree.h + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#ifndef __BTRFS_BTRFS_TREE_H__ +#define __BTRFS_BTRFS_TREE_H__ + +#include <common.h> + +#define BTRFS_VOL_NAME_MAX 255 +#define BTRFS_NAME_MAX 255 +#define BTRFS_LABEL_SIZE 256 +#define BTRFS_FSID_SIZE 16 +#define BTRFS_UUID_SIZE 16 + +/* + * This header contains the structure definitions and constants used + * by file system objects that can be retrieved using + * the BTRFS_IOC_SEARCH_TREE ioctl. That means basically anything that + * is needed to describe a leaf node's key or item contents. + */ + +/* holds pointers to all of the tree roots */ +#define BTRFS_ROOT_TREE_OBJECTID 1ULL + +/* stores information about which extents are in use, and reference counts */ +#define BTRFS_EXTENT_TREE_OBJECTID 2ULL + +/* + * chunk tree stores translations from logical -> physical block numbering + * the super block points to the chunk tree + */ +#define BTRFS_CHUNK_TREE_OBJECTID 3ULL + +/* + * stores information about which areas of a given device are in use. + * one per device. The tree of tree roots points to the device tree + */ +#define BTRFS_DEV_TREE_OBJECTID 4ULL + +/* one per subvolume, storing files and directories */ +#define BTRFS_FS_TREE_OBJECTID 5ULL + +/* directory objectid inside the root tree */ +#define BTRFS_ROOT_TREE_DIR_OBJECTID 6ULL + +/* holds checksums of all the data extents */ +#define BTRFS_CSUM_TREE_OBJECTID 7ULL + +/* holds quota configuration and tracking */ +#define BTRFS_QUOTA_TREE_OBJECTID 8ULL + +/* for storing items that use the BTRFS_UUID_KEY* types */ +#define BTRFS_UUID_TREE_OBJECTID 9ULL + +/* tracks free space in block groups. */ +#define BTRFS_FREE_SPACE_TREE_OBJECTID 10ULL + +/* device stats in the device tree */ +#define BTRFS_DEV_STATS_OBJECTID 0ULL + +/* for storing balance parameters in the root tree */ +#define BTRFS_BALANCE_OBJECTID -4ULL + +/* orhpan objectid for tracking unlinked/truncated files */ +#define BTRFS_ORPHAN_OBJECTID -5ULL + +/* does write ahead logging to speed up fsyncs */ +#define BTRFS_TREE_LOG_OBJECTID -6ULL +#define BTRFS_TREE_LOG_FIXUP_OBJECTID -7ULL + +/* for space balancing */ +#define BTRFS_TREE_RELOC_OBJECTID -8ULL +#define BTRFS_DATA_RELOC_TREE_OBJECTID -9ULL + +/* + * extent checksums all have this objectid + * this allows them to share the logging tree + * for fsyncs + */ +#define BTRFS_EXTENT_CSUM_OBJECTID -10ULL + +/* For storing free space cache */ +#define BTRFS_FREE_SPACE_OBJECTID -11ULL + +/* + * The inode number assigned to the special inode for storing + * free ino cache + */ +#define BTRFS_FREE_INO_OBJECTID -12ULL + +/* dummy objectid represents multiple objectids */ +#define BTRFS_MULTIPLE_OBJECTIDS -255ULL + +/* + * All files have objectids in this range. + */ +#define BTRFS_FIRST_FREE_OBJECTID 256ULL +#define BTRFS_LAST_FREE_OBJECTID -256ULL +#define BTRFS_FIRST_CHUNK_TREE_OBJECTID 256ULL + + +/* + * the device items go into the chunk tree. The key is in the form + * [ 1 BTRFS_DEV_ITEM_KEY device_id ] + */ +#define BTRFS_DEV_ITEMS_OBJECTID 1ULL + +#define BTRFS_BTREE_INODE_OBJECTID 1 + +#define BTRFS_EMPTY_SUBVOL_DIR_OBJECTID 2 + +#define BTRFS_DEV_REPLACE_DEVID 0ULL + +/* + * inode items have the data typically returned from stat and store other + * info about object characteristics. There is one for every file and dir in + * the FS + */ +#define BTRFS_INODE_ITEM_KEY 1 +#define BTRFS_INODE_REF_KEY 12 +#define BTRFS_INODE_EXTREF_KEY 13 +#define BTRFS_XATTR_ITEM_KEY 24 +#define BTRFS_ORPHAN_ITEM_KEY 48 +/* reserve 2-15 close to the inode for later flexibility */ + +/* + * dir items are the name -> inode pointers in a directory. There is one + * for every name in a directory. + */ +#define BTRFS_DIR_LOG_ITEM_KEY 60 +#define BTRFS_DIR_LOG_INDEX_KEY 72 +#define BTRFS_DIR_ITEM_KEY 84 +#define BTRFS_DIR_INDEX_KEY 96 +/* + * extent data is for file data + */ +#define BTRFS_EXTENT_DATA_KEY 108 + +/* + * extent csums are stored in a separate tree and hold csums for + * an entire extent on disk. + */ +#define BTRFS_EXTENT_CSUM_KEY 128 + +/* + * root items point to tree roots. They are typically in the root + * tree used by the super block to find all the other trees + */ +#define BTRFS_ROOT_ITEM_KEY 132 + +/* + * root backrefs tie subvols and snapshots to the directory entries that + * reference them + */ +#define BTRFS_ROOT_BACKREF_KEY 144 + +/* + * root refs make a fast index for listing all of the snapshots and + * subvolumes referenced by a given root. They point directly to the + * directory item in the root that references the subvol + */ +#define BTRFS_ROOT_REF_KEY 156 + +/* + * extent items are in the extent map tree. These record which blocks + * are used, and how many references there are to each block + */ +#define BTRFS_EXTENT_ITEM_KEY 168 + +/* + * The same as the BTRFS_EXTENT_ITEM_KEY, except it's metadata we already know + * the length, so we save the level in key->offset instead of the length. + */ +#define BTRFS_METADATA_ITEM_KEY 169 + +#define BTRFS_TREE_BLOCK_REF_KEY 176 + +#define BTRFS_EXTENT_DATA_REF_KEY 178 + +#define BTRFS_EXTENT_REF_V0_KEY 180 + +#define BTRFS_SHARED_BLOCK_REF_KEY 182 + +#define BTRFS_SHARED_DATA_REF_KEY 184 + +/* + * block groups give us hints into the extent allocation trees. Which + * blocks are free etc etc + */ +#define BTRFS_BLOCK_GROUP_ITEM_KEY 192 + +/* + * Every block group is represented in the free space tree by a free space info + * item, which stores some accounting information. It is keyed on + * (block_group_start, FREE_SPACE_INFO, block_group_length). + */ +#define BTRFS_FREE_SPACE_INFO_KEY 198 + +/* + * A free space extent tracks an extent of space that is free in a block group. + * It is keyed on (start, FREE_SPACE_EXTENT, length). + */ +#define BTRFS_FREE_SPACE_EXTENT_KEY 199 + +/* + * When a block group becomes very fragmented, we convert it to use bitmaps + * instead of extents. A free space bitmap is keyed on + * (start, FREE_SPACE_BITMAP, length); the corresponding item is a bitmap with + * (length / sectorsize) bits. + */ +#define BTRFS_FREE_SPACE_BITMAP_KEY 200 + +#define BTRFS_DEV_EXTENT_KEY 204 +#define BTRFS_DEV_ITEM_KEY 216 +#define BTRFS_CHUNK_ITEM_KEY 228 + +/* + * Records the overall state of the qgroups. + * There's only one instance of this key present, + * (0, BTRFS_QGROUP_STATUS_KEY, 0) + */ +#define BTRFS_QGROUP_STATUS_KEY 240 +/* + * Records the currently used space of the qgroup. + * One key per qgroup, (0, BTRFS_QGROUP_INFO_KEY, qgroupid). + */ +#define BTRFS_QGROUP_INFO_KEY 242 +/* + * Contains the user configured limits for the qgroup. + * One key per qgroup, (0, BTRFS_QGROUP_LIMIT_KEY, qgroupid). + */ +#define BTRFS_QGROUP_LIMIT_KEY 244 +/* + * Records the child-parent relationship of qgroups. For + * each relation, 2 keys are present: + * (childid, BTRFS_QGROUP_RELATION_KEY, parentid) + * (parentid, BTRFS_QGROUP_RELATION_KEY, childid) + */ +#define BTRFS_QGROUP_RELATION_KEY 246 + +/* + * Obsolete name, see BTRFS_TEMPORARY_ITEM_KEY. + */ +#define BTRFS_BALANCE_ITEM_KEY 248 + +/* + * The key type for tree items that are stored persistently, but do not need to + * exist for extended period of time. The items can exist in any tree. + * + * [subtype, BTRFS_TEMPORARY_ITEM_KEY, data] + * + * Existing items: + * + * - balance status item + * (BTRFS_BALANCE_OBJECTID, BTRFS_TEMPORARY_ITEM_KEY, 0) + */ +#define BTRFS_TEMPORARY_ITEM_KEY 248 + +/* + * Obsolete name, see BTRFS_PERSISTENT_ITEM_KEY + */ +#define BTRFS_DEV_STATS_KEY 249 + +/* + * The key type for tree items that are stored persistently and usually exist + * for a long period, eg. filesystem lifetime. The item kinds can be status + * information, stats or preference values. The item can exist in any tree. + * + * [subtype, BTRFS_PERSISTENT_ITEM_KEY, data] + * + * Existing items: + * + * - device statistics, store IO stats in the device tree, one key for all + * stats + * (BTRFS_DEV_STATS_OBJECTID, BTRFS_DEV_STATS_KEY, 0) + */ +#define BTRFS_PERSISTENT_ITEM_KEY 249 + +/* + * Persistantly stores the device replace state in the device tree. + * The key is built like this: (0, BTRFS_DEV_REPLACE_KEY, 0). + */ +#define BTRFS_DEV_REPLACE_KEY 250 + +/* + * Stores items that allow to quickly map UUIDs to something else. + * These items are part of the filesystem UUID tree. + * The key is built like this: + * (UUID_upper_64_bits, BTRFS_UUID_KEY*, UUID_lower_64_bits). + */ +#if BTRFS_UUID_SIZE != 16 +#error "UUID items require BTRFS_UUID_SIZE == 16!" +#endif +#define BTRFS_UUID_KEY_SUBVOL 251 /* for UUIDs assigned to subvols */ +#define BTRFS_UUID_KEY_RECEIVED_SUBVOL 252 /* for UUIDs assigned to + * received subvols */ + +/* + * string items are for debugging. They just store a short string of + * data in the FS + */ +#define BTRFS_STRING_ITEM_KEY 253 + + + +/* 32 bytes in various csum fields */ +#define BTRFS_CSUM_SIZE 32 + +/* csum types */ +#define BTRFS_CSUM_TYPE_CRC32 0 + +/* + * flags definitions for directory entry item type + * + * Used by: + * struct btrfs_dir_item.type + */ +#define BTRFS_FT_UNKNOWN 0 +#define BTRFS_FT_REG_FILE 1 +#define BTRFS_FT_DIR 2 +#define BTRFS_FT_CHRDEV 3 +#define BTRFS_FT_BLKDEV 4 +#define BTRFS_FT_FIFO 5 +#define BTRFS_FT_SOCK 6 +#define BTRFS_FT_SYMLINK 7 +#define BTRFS_FT_XATTR 8 +#define BTRFS_FT_MAX 9 + +/* + * The key defines the order in the tree, and so it also defines (optimal) + * block layout. + * + * objectid corresponds to the inode number. + * + * type tells us things about the object, and is a kind of stream selector. + * so for a given inode, keys with type of 1 might refer to the inode data, + * type of 2 may point to file data in the btree and type == 3 may point to + * extents. + * + * offset is the starting byte offset for this key in the stream. + */ + +struct btrfs_key { + __u64 objectid; + __u8 type; + __u64 offset; +} __attribute__ ((__packed__)); + +struct btrfs_dev_item { + /* the internal btrfs device id */ + __u64 devid; + + /* size of the device */ + __u64 total_bytes; + + /* bytes used */ + __u64 bytes_used; + + /* optimal io alignment for this device */ + __u32 io_align; + + /* optimal io width for this device */ + __u32 io_width; + + /* minimal io size for this device */ + __u32 sector_size; + + /* type and info about this device */ + __u64 type; + + /* expected generation for this device */ + __u64 generation; + + /* + * starting byte of this partition on the device, + * to allow for stripe alignment in the future + */ + __u64 start_offset; + + /* grouping information for allocation decisions */ + __u32 dev_group; + + /* seek speed 0-100 where 100 is fastest */ + __u8 seek_speed; + + /* bandwidth 0-100 where 100 is fastest */ + __u8 bandwidth; + + /* btrfs generated uuid for this device */ + __u8 uuid[BTRFS_UUID_SIZE]; + + /* uuid of FS who owns this device */ + __u8 fsid[BTRFS_UUID_SIZE]; +} __attribute__ ((__packed__)); + +struct btrfs_stripe { + __u64 devid; + __u64 offset; + __u8 dev_uuid[BTRFS_UUID_SIZE]; +} __attribute__ ((__packed__)); + +struct btrfs_chunk { + /* size of this chunk in bytes */ + __u64 length; + + /* objectid of the root referencing this chunk */ + __u64 owner; + + __u64 stripe_len; + __u64 type; + + /* optimal io alignment for this chunk */ + __u32 io_align; + + /* optimal io width for this chunk */ + __u32 io_width; + + /* minimal io size for this chunk */ + __u32 sector_size; + + /* 2^16 stripes is quite a lot, a second limit is the size of a single + * item in the btree + */ + __u16 num_stripes; + + /* sub stripes only matter for raid10 */ + __u16 sub_stripes; + struct btrfs_stripe stripe; + /* additional stripes go here */ +} __attribute__ ((__packed__)); + +#define BTRFS_FREE_SPACE_EXTENT 1 +#define BTRFS_FREE_SPACE_BITMAP 2 + +struct btrfs_free_space_entry { + __u64 offset; + __u64 bytes; + __u8 type; +} __attribute__ ((__packed__)); + +struct btrfs_free_space_header { + struct btrfs_key location; + __u64 generation; + __u64 num_entries; + __u64 num_bitmaps; +} __attribute__ ((__packed__)); + +#define BTRFS_HEADER_FLAG_WRITTEN (1ULL << 0) +#define BTRFS_HEADER_FLAG_RELOC (1ULL << 1) + +/* Super block flags */ +/* Errors detected */ +#define BTRFS_SUPER_FLAG_ERROR (1ULL << 2) + +#define BTRFS_SUPER_FLAG_SEEDING (1ULL << 32) +#define BTRFS_SUPER_FLAG_METADUMP (1ULL << 33) + + +/* + * items in the extent btree are used to record the objectid of the + * owner of the block and the number of references + */ + +struct btrfs_extent_item { + __u64 refs; + __u64 generation; + __u64 flags; +} __attribute__ ((__packed__)); + + +#define BTRFS_EXTENT_FLAG_DATA (1ULL << 0) +#define BTRFS_EXTENT_FLAG_TREE_BLOCK (1ULL << 1) + +/* following flags only apply to tree blocks */ + +/* use full backrefs for extent pointers in the block */ +#define BTRFS_BLOCK_FLAG_FULL_BACKREF (1ULL << 8) + +/* + * this flag is only used internally by scrub and may be changed at any time + * it is only declared here to avoid collisions + */ +#define BTRFS_EXTENT_FLAG_SUPER (1ULL << 48) + +struct btrfs_tree_block_info { + struct btrfs_key key; + __u8 level; +} __attribute__ ((__packed__)); + +struct btrfs_extent_data_ref { + __u64 root; + __u64 objectid; + __u64 offset; + __u32 count; +} __attribute__ ((__packed__)); + +struct btrfs_shared_data_ref { + __u32 count; +} __attribute__ ((__packed__)); + +struct btrfs_extent_inline_ref { + __u8 type; + __u64 offset; +} __attribute__ ((__packed__)); + +/* dev extents record free space on individual devices. The owner + * field points back to the chunk allocation mapping tree that allocated + * the extent. The chunk tree uuid field is a way to double check the owner + */ +struct btrfs_dev_extent { + __u64 chunk_tree; + __u64 chunk_objectid; + __u64 chunk_offset; + __u64 length; + __u8 chunk_tree_uuid[BTRFS_UUID_SIZE]; +} __attribute__ ((__packed__)); + +struct btrfs_inode_ref { + __u64 index; + __u16 name_len; + /* name goes here */ +} __attribute__ ((__packed__)); + +struct btrfs_inode_extref { + __u64 parent_objectid; + __u64 index; + __u16 name_len; + __u8 name[0]; + /* name goes here */ +} __attribute__ ((__packed__)); + +struct btrfs_timespec { + __u64 sec; + __u32 nsec; +} __attribute__ ((__packed__)); + +struct btrfs_inode_item { + /* nfs style generation number */ + __u64 generation; + /* transid that last touched this inode */ + __u64 transid; + __u64 size; + __u64 nbytes; + __u64 block_group; + __u32 nlink; + __u32 uid; + __u32 gid; + __u32 mode; + __u64 rdev; + __u64 flags; + + /* modification sequence number for NFS */ + __u64 sequence; + + /* + * a little future expansion, for more than this we can + * just grow the inode item and version it + */ + __u64 reserved[4]; + struct btrfs_timespec atime; + struct btrfs_timespec ctime; + struct btrfs_timespec mtime; + struct btrfs_timespec otime; +} __attribute__ ((__packed__)); + +struct btrfs_dir_log_item { + __u64 end; +} __attribute__ ((__packed__)); + +struct btrfs_dir_item { + struct btrfs_key location; + __u64 transid; + __u16 data_len; + __u16 name_len; + __u8 type; +} __attribute__ ((__packed__)); + +#define BTRFS_ROOT_SUBVOL_RDONLY (1ULL << 0) + +/* + * Internal in-memory flag that a subvolume has been marked for deletion but + * still visible as a directory + */ +#define BTRFS_ROOT_SUBVOL_DEAD (1ULL << 48) + +struct btrfs_root_item { + struct btrfs_inode_item inode; + __u64 generation; + __u64 root_dirid; + __u64 bytenr; + __u64 byte_limit; + __u64 bytes_used; + __u64 last_snapshot; + __u64 flags; + __u32 refs; + struct btrfs_key drop_progress; + __u8 drop_level; + __u8 level; + + /* + * The following fields appear after subvol_uuids+subvol_times + * were introduced. + */ + + /* + * This generation number is used to test if the new fields are valid + * and up to date while reading the root item. Every time the root item + * is written out, the "generation" field is copied into this field. If + * anyone ever mounted the fs with an older kernel, we will have + * mismatching generation values here and thus must invalidate the + * new fields. See btrfs_update_root and btrfs_find_last_root for + * details. + * the offset of generation_v2 is also used as the start for the memset + * when invalidating the fields. + */ + __u64 generation_v2; + __u8 uuid[BTRFS_UUID_SIZE]; + __u8 parent_uuid[BTRFS_UUID_SIZE]; + __u8 received_uuid[BTRFS_UUID_SIZE]; + __u64 ctransid; /* updated when an inode changes */ + __u64 otransid; /* trans when created */ + __u64 stransid; /* trans when sent. non-zero for received subvol */ + __u64 rtransid; /* trans when received. non-zero for received subvol */ + struct btrfs_timespec ctime; + struct btrfs_timespec otime; + struct btrfs_timespec stime; + struct btrfs_timespec rtime; + __u64 reserved[8]; /* for future */ +} __attribute__ ((__packed__)); + +/* + * this is used for both forward and backward root refs + */ +struct btrfs_root_ref { + __u64 dirid; + __u64 sequence; + __u16 name_len; +} __attribute__ ((__packed__)); + +#define BTRFS_FILE_EXTENT_INLINE 0 +#define BTRFS_FILE_EXTENT_REG 1 +#define BTRFS_FILE_EXTENT_PREALLOC 2 + +enum btrfs_compression_type { + BTRFS_COMPRESS_NONE = 0, + BTRFS_COMPRESS_ZLIB = 1, + BTRFS_COMPRESS_LZO = 2, + BTRFS_COMPRESS_TYPES = 2, + BTRFS_COMPRESS_LAST = 3, +}; + +struct btrfs_file_extent_item { + /* + * transaction id that created this extent + */ + __u64 generation; + /* + * max number of bytes to hold this extent in ram + * when we split a compressed extent we can't know how big + * each of the resulting pieces will be. So, this is + * an upper limit on the size of the extent in ram instead of + * an exact limit. + */ + __u64 ram_bytes; + + /* + * 32 bits for the various ways we might encode the data, + * including compression and encryption. If any of these + * are set to something a given disk format doesn't understand + * it is treated like an incompat flag for reading and writing, + * but not for stat. + */ + __u8 compression; + __u8 encryption; + __u16 other_encoding; /* spare for later use */ + + /* are we inline data or a real extent? */ + __u8 type; + + /* + * disk space consumed by the extent, checksum blocks are included + * in these numbers + * + * At this offset in the structure, the inline extent data start. + */ + __u64 disk_bytenr; + __u64 disk_num_bytes; + /* + * the logical offset in file blocks (no csums) + * this extent record is for. This allows a file extent to point + * into the middle of an existing extent on disk, sharing it + * between two snapshots (useful if some bytes in the middle of the + * extent have changed + */ + __u64 offset; + /* + * the logical number of file blocks (no csums included). This + * always reflects the size uncompressed and without encoding. + */ + __u64 num_bytes; + +} __attribute__ ((__packed__)); + +struct btrfs_csum_item { + __u8 csum; +} __attribute__ ((__packed__)); + +/* different types of block groups (and chunks) */ +#define BTRFS_BLOCK_GROUP_DATA (1ULL << 0) +#define BTRFS_BLOCK_GROUP_SYSTEM (1ULL << 1) +#define BTRFS_BLOCK_GROUP_METADATA (1ULL << 2) +#define BTRFS_BLOCK_GROUP_RAID0 (1ULL << 3) +#define BTRFS_BLOCK_GROUP_RAID1 (1ULL << 4) +#define BTRFS_BLOCK_GROUP_DUP (1ULL << 5) +#define BTRFS_BLOCK_GROUP_RAID10 (1ULL << 6) +#define BTRFS_BLOCK_GROUP_RAID5 (1ULL << 7) +#define BTRFS_BLOCK_GROUP_RAID6 (1ULL << 8) +#define BTRFS_BLOCK_GROUP_RESERVED (BTRFS_AVAIL_ALLOC_BIT_SINGLE | \ + BTRFS_SPACE_INFO_GLOBAL_RSV) + +enum btrfs_raid_types { + BTRFS_RAID_RAID10, + BTRFS_RAID_RAID1, + BTRFS_RAID_DUP, + BTRFS_RAID_RAID0, + BTRFS_RAID_SINGLE, + BTRFS_RAID_RAID5, + BTRFS_RAID_RAID6, + BTRFS_NR_RAID_TYPES +}; + +#define BTRFS_BLOCK_GROUP_TYPE_MASK (BTRFS_BLOCK_GROUP_DATA | \ + BTRFS_BLOCK_GROUP_SYSTEM | \ + BTRFS_BLOCK_GROUP_METADATA) + +#define BTRFS_BLOCK_GROUP_PROFILE_MASK (BTRFS_BLOCK_GROUP_RAID0 | \ + BTRFS_BLOCK_GROUP_RAID1 | \ + BTRFS_BLOCK_GROUP_RAID5 | \ + BTRFS_BLOCK_GROUP_RAID6 | \ + BTRFS_BLOCK_GROUP_DUP | \ + BTRFS_BLOCK_GROUP_RAID10) +#define BTRFS_BLOCK_GROUP_RAID56_MASK (BTRFS_BLOCK_GROUP_RAID5 | \ + BTRFS_BLOCK_GROUP_RAID6) + +/* + * We need a bit for restriper to be able to tell when chunks of type + * SINGLE are available. This "extended" profile format is used in + * fs_info->avail_*_alloc_bits (in-memory) and balance item fields + * (on-disk). The corresponding on-disk bit in chunk.type is reserved + * to avoid remappings between two formats in future. + */ +#define BTRFS_AVAIL_ALLOC_BIT_SINGLE (1ULL << 48) + +/* + * A fake block group type that is used to communicate global block reserve + * size to userspace via the SPACE_INFO ioctl. + */ +#define BTRFS_SPACE_INFO_GLOBAL_RSV (1ULL << 49) + +#define BTRFS_EXTENDED_PROFILE_MASK (BTRFS_BLOCK_GROUP_PROFILE_MASK | \ + BTRFS_AVAIL_ALLOC_BIT_SINGLE) + +#endif /* __BTRFS_BTRFS_TREE_H__ */ diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h new file mode 100644 index 0000000000..39f4473ae5 --- /dev/null +++ b/fs/btrfs/ctree.h @@ -0,0 +1,334 @@ +/* + * From linux/fs/btrfs/ctree.h + * Copyright (C) 2007,2008 Oracle. All rights reserved. + * + * Modified in 2017 by Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#ifndef __BTRFS_CTREE_H__ +#define __BTRFS_CTREE_H__ + +#include <common.h> +#include <compiler.h> +#include "btrfs_tree.h" + +#define BTRFS_MAGIC 0x4D5F53665248425FULL /* ascii _BHRfS_M, no null */ + +#define BTRFS_MAX_MIRRORS 3 + +#define BTRFS_MAX_LEVEL 8 + +#define BTRFS_COMPAT_EXTENT_TREE_V0 + +/* + * the max metadata block size. This limit is somewhat artificial, + * but the memmove costs go through the roof for larger blocks. + */ +#define BTRFS_MAX_METADATA_BLOCKSIZE 65536 + +/* + * we can actually store much bigger names, but lets not confuse the rest + * of linux + */ +#define BTRFS_NAME_LEN 255 + +/* + * Theoretical limit is larger, but we keep this down to a sane + * value. That should limit greatly the possibility of collisions on + * inode ref items. + */ +#define BTRFS_LINK_MAX 65535U + +static const int btrfs_csum_sizes[] = { 4 }; + +/* four bytes for CRC32 */ +#define BTRFS_EMPTY_DIR_SIZE 0 + +/* ioprio of readahead is set to idle */ +#define BTRFS_IOPRIO_READA (IOPRIO_PRIO_VALUE(IOPRIO_CLASS_IDLE, 0)) + +#define BTRFS_DIRTY_METADATA_THRESH SZ_32M + +#define BTRFS_MAX_EXTENT_SIZE SZ_128M + +/* + * File system states + */ +#define BTRFS_FS_STATE_ERROR 0 +#define BTRFS_FS_STATE_REMOUNTING 1 +#define BTRFS_FS_STATE_TRANS_ABORTED 2 +#define BTRFS_FS_STATE_DEV_REPLACING 3 +#define BTRFS_FS_STATE_DUMMY_FS_INFO 4 + +#define BTRFS_BACKREF_REV_MAX 256 +#define BTRFS_BACKREF_REV_SHIFT 56 +#define BTRFS_BACKREF_REV_MASK (((u64)BTRFS_BACKREF_REV_MAX - 1) << \ + BTRFS_BACKREF_REV_SHIFT) + +#define BTRFS_OLD_BACKREF_REV 0 +#define BTRFS_MIXED_BACKREF_REV 1 + +/* + * every tree block (leaf or node) starts with this header. + */ +struct btrfs_header { + /* these first four must match the super block */ + __u8 csum[BTRFS_CSUM_SIZE]; + __u8 fsid[BTRFS_FSID_SIZE]; /* FS specific uuid */ + __u64 bytenr; /* which block this node is supposed to live in */ + __u64 flags; + + /* allowed to be different from the super from here on down */ + __u8 chunk_tree_uuid[BTRFS_UUID_SIZE]; + __u64 generation; + __u64 owner; + __u32 nritems; + __u8 level; +} __attribute__ ((__packed__)); + +/* + * this is a very generous portion of the super block, giving us + * room to translate 14 chunks with 3 stripes each. + */ +#define BTRFS_SYSTEM_CHUNK_ARRAY_SIZE 2048 + +/* + * just in case we somehow lose the roots and are not able to mount, + * we store an array of the roots from previous transactions + * in the super. + */ +#define BTRFS_NUM_BACKUP_ROOTS 4 +struct btrfs_root_backup { + __u64 tree_root; + __u64 tree_root_gen; + + __u64 chunk_root; + __u64 chunk_root_gen; + + __u64 extent_root; + __u64 extent_root_gen; + + __u64 fs_root; + __u64 fs_root_gen; + + __u64 dev_root; + __u64 dev_root_gen; + + __u64 csum_root; + __u64 csum_root_gen; + + __u64 total_bytes; + __u64 bytes_used; + __u64 num_devices; + /* future */ + __u64 unused_64[4]; + + __u8 tree_root_level; + __u8 chunk_root_level; + __u8 extent_root_level; + __u8 fs_root_level; + __u8 dev_root_level; + __u8 csum_root_level; + /* future and to align */ + __u8 unused_8[10]; +} __attribute__ ((__packed__)); + +/* + * the super block basically lists the main trees of the FS + * it currently lacks any block count etc etc + */ +struct btrfs_super_block { + __u8 csum[BTRFS_CSUM_SIZE]; + /* the first 4 fields must match struct btrfs_header */ + __u8 fsid[BTRFS_FSID_SIZE]; /* FS specific uuid */ + __u64 bytenr; /* this block number */ + __u64 flags; + + /* allowed to be different from the btrfs_header from here own down */ + __u64 magic; + __u64 generation; + __u64 root; + __u64 chunk_root; + __u64 log_root; + + /* this will help find the new super based on the log root */ + __u64 log_root_transid; + __u64 total_bytes; + __u64 bytes_used; + __u64 root_dir_objectid; + __u64 num_devices; + __u32 sectorsize; + __u32 nodesize; + __u32 __unused_leafsize; + __u32 stripesize; + __u32 sys_chunk_array_size; + __u64 chunk_root_generation; + __u64 compat_flags; + __u64 compat_ro_flags; + __u64 incompat_flags; + __u16 csum_type; + __u8 root_level; + __u8 chunk_root_level; + __u8 log_root_level; + struct btrfs_dev_item dev_item; + + char label[BTRFS_LABEL_SIZE]; + + __u64 cache_generation; + __u64 uuid_tree_generation; + + /* future expansion */ + __u64 reserved[30]; + __u8 sys_chunk_array[BTRFS_SYSTEM_CHUNK_ARRAY_SIZE]; + struct btrfs_root_backup super_roots[BTRFS_NUM_BACKUP_ROOTS]; +} __attribute__ ((__packed__)); + +/* + * Compat flags that we support. If any incompat flags are set other than the + * ones specified below then we will fail to mount + */ +#define BTRFS_FEATURE_COMPAT_SUPP 0ULL +#define BTRFS_FEATURE_COMPAT_SAFE_SET 0ULL +#define BTRFS_FEATURE_COMPAT_SAFE_CLEAR 0ULL + +#define BTRFS_FEATURE_COMPAT_RO_SUPP \ + (BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE | \ + BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE_VALID) + +#define BTRFS_FEATURE_COMPAT_RO_SAFE_SET 0ULL +#define BTRFS_FEATURE_COMPAT_RO_SAFE_CLEAR 0ULL + +#define BTRFS_FEATURE_INCOMPAT_SUPP \ + (BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF | \ + BTRFS_FEATURE_INCOMPAT_DEFAULT_SUBVOL | \ + BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS | \ + BTRFS_FEATURE_INCOMPAT_BIG_METADATA | \ + BTRFS_FEATURE_INCOMPAT_COMPRESS_LZO | \ + BTRFS_FEATURE_INCOMPAT_RAID56 | \ + BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF | \ + BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA | \ + BTRFS_FEATURE_INCOMPAT_NO_HOLES) + +#define BTRFS_FEATURE_INCOMPAT_SAFE_SET \ + (BTRFS_FEATURE_INCOMPAT_EXTENDED_IREF) +#define BTRFS_FEATURE_INCOMPAT_SAFE_CLEAR 0ULL + +/* + * A leaf is full of items. offset and size tell us where to find + * the item in the leaf (relative to the start of the data area) + */ +struct btrfs_item { + struct btrfs_key key; + __u32 offset; + __u32 size; +} __attribute__ ((__packed__)); + +/* + * leaves have an item area and a data area: + * [item0, item1....itemN] [free space] [dataN...data1, data0] + * + * The data is separate from the items to get the keys closer together + * during searches. + */ +struct btrfs_leaf { + struct btrfs_header header; + struct btrfs_item items[]; +} __attribute__ ((__packed__)); + +/* + * all non-leaf blocks are nodes, they hold only keys and pointers to + * other blocks + */ +struct btrfs_key_ptr { + struct btrfs_key key; + __u64 blockptr; + __u64 generation; +} __attribute__ ((__packed__)); + +struct btrfs_node { + struct btrfs_header header; + struct btrfs_key_ptr ptrs[]; +} __attribute__ ((__packed__)); + +union btrfs_tree_node { + struct btrfs_header header; + struct btrfs_leaf leaf; + struct btrfs_node node; +}; + +typedef __u8 u8; +typedef __u16 u16; +typedef __u32 u32; +typedef __u64 u64; + +struct btrfs_path { + union btrfs_tree_node *nodes[BTRFS_MAX_LEVEL]; + u32 slots[BTRFS_MAX_LEVEL]; +}; + +struct btrfs_root { + u64 objectid; + u64 bytenr; + u64 root_dirid; +}; + +int btrfs_comp_keys(struct btrfs_key *, struct btrfs_key *); +int btrfs_comp_keys_type(struct btrfs_key *, struct btrfs_key *); +int btrfs_bin_search(union btrfs_tree_node *, struct btrfs_key *, int *); +void btrfs_free_path(struct btrfs_path *); +int btrfs_search_tree(const struct btrfs_root *, struct btrfs_key *, + struct btrfs_path *); +int btrfs_prev_slot(struct btrfs_path *); +int btrfs_next_slot(struct btrfs_path *); + +static inline struct btrfs_key *btrfs_path_leaf_key(struct btrfs_path *p) { + return &p->nodes[0]->leaf.items[p->slots[0]].key; +} + +static inline struct btrfs_key * +btrfs_search_tree_key_type(const struct btrfs_root *root, u64 objectid, + u8 type, struct btrfs_path *path) +{ + struct btrfs_key key, *res; + + key.objectid = objectid; + key.type = type; + key.offset = 0; + + if (btrfs_search_tree(root, &key, path)) + return NULL; + + res = btrfs_path_leaf_key(path); + if (btrfs_comp_keys_type(&key, res)) { + btrfs_free_path(path); + return NULL; + } + + return res; +} + +static inline u32 btrfs_path_item_size(struct btrfs_path *p) +{ + return p->nodes[0]->leaf.items[p->slots[0]].size; +} + +static inline void *btrfs_leaf_data(struct btrfs_leaf *leaf, u32 slot) +{ + return ((u8 *) leaf) + sizeof(struct btrfs_header) + + leaf->items[slot].offset; +} + +static inline void *btrfs_path_leaf_data(struct btrfs_path *p) +{ + return btrfs_leaf_data(&p->nodes[0]->leaf, p->slots[0]); +} + +#define btrfs_item_ptr(l,s,t) \ + ((t *) btrfs_leaf_data((l),(s))) + +#define btrfs_path_item_ptr(p,t) \ + ((t *) btrfs_path_leaf_data((p))) + +#endif /* __BTRFS_CTREE_H__ */

BTRFS on disk structures are stored in Little Endian. Add functions to convert this structures to cpu and to disk format.

On Little Endian hosts, these functions do nothing.

On Big Endian the CALL_MACRO_FROM_EACH from variadic-macro.h is used to define all the members for each structure on which cpu_to_le* or le*_to_cpu is to be called.

Signed-off-by: Marek Behun marek.behun@nic.cz

create mode 100644 fs/btrfs/conv-funcs.h

diff --git a/fs/btrfs/conv-funcs.h b/fs/btrfs/conv-funcs.h new file mode 100644 index 0000000000..f2e7944e4e --- /dev/null +++ b/fs/btrfs/conv-funcs.h @@ -0,0 +1,176 @@ +/* + * Functions to convert BTRFS structures from disk to CPU endianness and back. + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#ifndef __BTRFS_CONV_FUNCS_H__ +#define __BTRFS_CONV_FUNCS_H__ + +#include "ctree.h" +#include <u-boot/variadic-macro.h> +#include <asm/byteorder.h> + +/* We are using variadic macros and C11 _Generic to achieve compact code. + + We want to define macro DEFINE_CONV(x, ...), where the first argument is the + name of the structure for which it shall define conversion functions (the + names of the functions shall be x_to_cpu and x_to_disk), and the other + arguments are names of the members on which the functions shall do + endianness conversion. */ + +#if defined(__LITTLE_ENDIAN) + +/* If the target machine is little endian, the conversion functions do + nothing, since the on disk format is little endian. */ + +# define DEFINE_CONV(n,...) \ + static inline struct n *n##_to_disk(struct n * r) \ + { \ + return r; \ + } \ + static inline struct n *n##_to_cpu(struct n * r) \ + { \ + return r; \ + } + +# define DEFINE_CONV_ALT(n,a,...) \ + static inline struct n *n##_to_disk_##a(struct n * r) \ + { \ + return r; \ + } \ + static inline struct n *n##_to_cpu_##a(struct n * r) \ + { \ + return r; \ + } + +#else /* !defined(__LITTLE_ENDIAN) */ + +/* Some structures contain not only scalar members, but compound types as well + (for example, struct btrfs_inode_item contains members of type struct + btrfs_timespec. + + For these members we want to call the conversion function recursively, so + first we declare the functions taking pointers to this types (these function + will be defined later by the DEFINE_CONV macro) and then we define + correspond functions taking non-pointers, so that they can be used in the + expansion of the _Generic. */ +# define DEFINE_CONV_FOR_STRUCT(n) \ + static inline struct n * n##_to_disk(struct n *); \ + static inline struct n * n##_to_cpu(struct n *); \ + static inline struct n n##_to_disk_v(struct n x) { \ + return *n##_to_disk(&x); \ + } \ + static inline struct n n##_to_cpu_v(struct n x) { \ + return *n##_to_cpu(&x); \ + } + +DEFINE_CONV_FOR_STRUCT(btrfs_key) +DEFINE_CONV_FOR_STRUCT(btrfs_stripe) +DEFINE_CONV_FOR_STRUCT(btrfs_timespec) +DEFINE_CONV_FOR_STRUCT(btrfs_inode_item) +DEFINE_CONV_FOR_STRUCT(btrfs_root_backup) +DEFINE_CONV_FOR_STRUCT(btrfs_dev_item) + +/* Now define the _Generic for both CPU to LE and LE to CPU */ +# define DEFINE_CONV_CPU_TO_LE(x) \ + (d->x) = _Generic((d->x), \ + __u16: cpu_to_le16, \ + __u32: cpu_to_le32, \ + __u64: cpu_to_le64, \ + struct btrfs_key: btrfs_key_to_disk_v, \ + struct btrfs_stripe: btrfs_stripe_to_disk_v, \ + struct btrfs_timespec: btrfs_timespec_to_disk_v, \ + struct btrfs_inode_item: btrfs_inode_item_to_disk_v, \ + struct btrfs_root_backup: btrfs_root_backup_to_disk_v, \ + struct btrfs_dev_item: btrfs_dev_item_to_disk_v \ + )((d->x)); + +# define DEFINE_CONV_LE_TO_CPU(x) \ + (d->x) = _Generic((d->x), \ + __u16: le16_to_cpu, \ + __u32: le32_to_cpu, \ + __u64: le64_to_cpu, \ + struct btrfs_key: btrfs_key_to_cpu_v, \ + struct btrfs_stripe: btrfs_stripe_to_cpu_v, \ + struct btrfs_timespec: btrfs_timespec_to_cpu_v, \ + struct btrfs_inode_item: btrfs_inode_item_to_cpu_v, \ + struct btrfs_root_backup: btrfs_root_backup_to_cpu_v, \ + struct btrfs_dev_item: btrfs_dev_item_to_cpu_v \ + )((d->x)); + +# define DEFINE_CONV_ONE(t,n,m,...) \ + static inline struct t * n(struct t * d) { \ + CALL_MACRO_FOR_EACH(m, ##__VA_ARGS__) \ + return d; \ + } + +/* Finally define the DEFINE_CONV macro */ +# define DEFINE_CONV(n,...) \ + DEFINE_CONV_ONE(n,n##_to_disk,DEFINE_CONV_CPU_TO_LE,##__VA_ARGS__) \ + DEFINE_CONV_ONE(n,n##_to_cpu,DEFINE_CONV_LE_TO_CPU,##__VA_ARGS__) + +# define DEFINE_CONV_ALT(n,a,...) \ + DEFINE_CONV_ONE(n,n##_to_disk_##a,DEFINE_CONV_CPU_TO_LE, \ + ##__VA_ARGS__) \ + DEFINE_CONV_ONE(n,n##_to_cpu_##a,DEFINE_CONV_LE_TO_CPU,##__VA_ARGS__) + +#endif /* !defined(__LITTLE_ENDIAN) */ + +DEFINE_CONV(btrfs_key, objectid, offset) +DEFINE_CONV(btrfs_dev_item, devid, total_bytes, bytes_used, io_align, io_width, + sector_size, type, generation, start_offset, dev_group) +DEFINE_CONV(btrfs_stripe, devid, offset) +DEFINE_CONV(btrfs_chunk, length, owner, stripe_len, type, io_align, io_width, + sector_size, num_stripes, sub_stripes) +DEFINE_CONV(btrfs_free_space_entry, offset, bytes) +DEFINE_CONV(btrfs_free_space_header, location, generation, num_entries, + num_bitmaps) +DEFINE_CONV(btrfs_extent_item, refs, generation, flags) +DEFINE_CONV(btrfs_tree_block_info, key) +DEFINE_CONV(btrfs_extent_data_ref, root, objectid, offset, count) +DEFINE_CONV(btrfs_shared_data_ref, count) +DEFINE_CONV(btrfs_extent_inline_ref, offset) +DEFINE_CONV(btrfs_dev_extent, chunk_tree, chunk_objectid, chunk_offset, length) +DEFINE_CONV(btrfs_inode_ref, index, name_len) +DEFINE_CONV(btrfs_inode_extref, parent_objectid, index, name_len) +DEFINE_CONV(btrfs_timespec, sec, nsec) +DEFINE_CONV(btrfs_inode_item, generation, transid, size, nbytes, block_group, + nlink, uid, gid, mode, rdev, flags, sequence, atime, ctime, mtime, + otime) +DEFINE_CONV(btrfs_dir_log_item, end) +DEFINE_CONV(btrfs_dir_item, location, transid, data_len, name_len) +DEFINE_CONV(btrfs_root_item, inode, generation, root_dirid, bytenr, byte_limit, + bytes_used, last_snapshot, flags, refs, drop_progress, + generation_v2, ctransid, otransid, stransid, rtransid, ctime, + otime, stime, rtime) +DEFINE_CONV(btrfs_root_ref, dirid, sequence, name_len) +DEFINE_CONV(btrfs_file_extent_item, generation, ram_bytes, other_encoding, + disk_bytenr, disk_num_bytes, offset, num_bytes) +DEFINE_CONV_ALT(btrfs_file_extent_item, inl, generation, ram_bytes, + other_encoding) +DEFINE_CONV(btrfs_dev_replace_item, src_devid, cursor_left, cursor_right, + cont_reading_from_srcdev_mode, replace_state, time_started, + time_stopped, num_write_errors, num_uncorrectable_read_errors) +DEFINE_CONV(btrfs_block_group_item, used, chunk_objectid, flags) +DEFINE_CONV(btrfs_free_space_info, extent_count, flags) + +DEFINE_CONV(btrfs_header, bytenr, flags, generation, owner, nritems) +DEFINE_CONV(btrfs_root_backup, tree_root, tree_root_gen, chunk_root, + chunk_root_gen, extent_root, extent_root_gen, fs_root, fs_root_gen, + dev_root, dev_root_gen, csum_root, csum_root_gen, total_bytes, + bytes_used, num_devices) +DEFINE_CONV(btrfs_super_block, bytenr, flags, magic, generation, root, + chunk_root, log_root, log_root_transid, total_bytes, bytes_used, + root_dir_objectid, num_devices, sectorsize, nodesize, + __unused_leafsize, stripesize, sys_chunk_array_size, + chunk_root_generation, compat_flags, compat_ro_flags, + incompat_flags, csum_type, dev_item, cache_generation, + uuid_tree_generation, super_roots[0], super_roots[1], + super_roots[2], super_roots[3]) +DEFINE_CONV(btrfs_item, key, offset, size) +DEFINE_CONV(btrfs_key_ptr, key, blockptr, generation) + +#endif /* __BTRFS_CONV_FUNCS_H__ */

This adds the proper implementation for the BTRFS filesystem. The implementation currently supports only read-only mode and the filesystem can be only on a single device.

Checksums of data chunks is unimplemented.

Compression is implemented (ZLIB + LZO).

Signed-off-by: Marek Behun marek.behun@nic.cz

create mode 100644 fs/btrfs/btrfs.h create mode 100644 fs/btrfs/chunk-map.c create mode 100644 fs/btrfs/compression.c create mode 100644 fs/btrfs/ctree.c create mode 100644 fs/btrfs/dev.c create mode 100644 fs/btrfs/dir-item.c create mode 100644 fs/btrfs/extent-io.c create mode 100644 fs/btrfs/hash.c create mode 100644 fs/btrfs/inode.c create mode 100644 fs/btrfs/root.c create mode 100644 fs/btrfs/subvolume.c create mode 100644 fs/btrfs/super.c

diff --git a/fs/btrfs/btrfs.h b/fs/btrfs/btrfs.h new file mode 100644 index 0000000000..4247cbbb09 --- /dev/null +++ b/fs/btrfs/btrfs.h @@ -0,0 +1,89 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#ifndef __BTRFS_BTRFS_H__ +#define __BTRFS_BTRFS_H__ + +#include <linux/rbtree.h> +#include "conv-funcs.h" + +struct btrfs_info { + struct btrfs_super_block sb; + struct btrfs_root_backup *root_backup; + + struct btrfs_root tree_root; + struct btrfs_root fs_root; + struct btrfs_root chunk_root; + + struct rb_root chunks_root; +}; + +extern struct btrfs_info btrfs_info; + +/* hash.c */ +void btrfs_hash_init(void); +u32 btrfs_crc32c(u32, const void *, size_t); +u32 btrfs_csum_data(char *, u32, size_t); +void btrfs_csum_final(u32, void *); + +static inline u64 btrfs_name_hash(const char *name, int len) +{ + return btrfs_crc32c((u32) ~1, name, len); +} + +/* dev.c */ +extern struct blk_desc *btrfs_blk_desc; +extern disk_partition_t *btrfs_part_info; + +int btrfs_devread(u64, int, void *); + +/* chunk-map.c */ +u64 btrfs_map_logical_to_physical(u64); +int btrfs_chunk_map_init(void); +void btrfs_chunk_map_exit(void); +int btrfs_read_chunk_tree(void); + +/* compression.c */ +u32 btrfs_decompress(u8 type, const char *, u32, char *, u32); + +/* super.c */ +int btrfs_read_superblock(void); + +/* dir-item.c */ +typedef int (*btrfs_readdir_callback_t)(const struct btrfs_root *, + struct btrfs_dir_item *); + +int btrfs_lookup_dir_item(const struct btrfs_root *, u64, const char *, int, + struct btrfs_dir_item *); +int btrfs_readdir(const struct btrfs_root *, u64, btrfs_readdir_callback_t); + +/* root.c */ +int btrfs_find_root(u64, struct btrfs_root *, struct btrfs_root_item *); +u64 btrfs_lookup_root_ref(u64, struct btrfs_root_ref *, char *); + +/* inode.c */ +u64 btrfs_lookup_inode_ref(struct btrfs_root *, u64, struct btrfs_inode_ref *, + char *); +int btrfs_lookup_inode(const struct btrfs_root *, struct btrfs_key *, + struct btrfs_inode_item *, struct btrfs_root *); +int btrfs_readlink(const struct btrfs_root *, u64, char *); +u64 btrfs_lookup_path(struct btrfs_root *, u64, const char *, u8 *, + struct btrfs_inode_item *, int); +u64 btrfs_file_read(const struct btrfs_root *, u64, u64, u64, char *); + +/* subvolume.c */ +u64 btrfs_get_default_subvol_objectid(void); + +/* extent-io.c */ +u64 btrfs_read_extent_inline(struct btrfs_path *, + struct btrfs_file_extent_item *, u64, u64, + char *); +u64 btrfs_read_extent_reg(struct btrfs_path *, struct btrfs_file_extent_item *, + u64, u64, char *); + +#endif /* !__BTRFS_BTRFS_H__ */ diff --git a/fs/btrfs/chunk-map.c b/fs/btrfs/chunk-map.c new file mode 100644 index 0000000000..48407f3331 --- /dev/null +++ b/fs/btrfs/chunk-map.c @@ -0,0 +1,178 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" +#include <malloc.h> + +struct chunk_map_item { + struct rb_node node; + u64 logical; + u64 length; + u64 physical; +}; + +static int add_chunk_mapping(struct btrfs_key *key, struct btrfs_chunk *chunk) +{ + struct btrfs_stripe *stripe; + u64 block_profile = chunk->type & BTRFS_BLOCK_GROUP_PROFILE_MASK; + struct rb_node **new = &(btrfs_info.chunks_root.rb_node), *prnt = NULL; + struct chunk_map_item *map_item; + + if (block_profile && block_profile != BTRFS_BLOCK_GROUP_DUP) { + printf("%s: unsupported chunk profile %llu\n", __func__, + block_profile); + return -1; + } else if (!chunk->length) { + printf("%s: zero length chunk\n", __func__); + return -1; + } + + stripe = &chunk->stripe; + btrfs_stripe_to_cpu(stripe); + + while (*new) { + struct chunk_map_item *this; + + this = rb_entry(*new, struct chunk_map_item, node); + + prnt = *new; + if (key->offset < this->logical) { + new = &((*new)->rb_left); + } else if (key->offset > this->logical) { + new = &((*new)->rb_right); + } else { + debug("%s: Logical address %llu already in map!\n", + __func__, key->offset); + return 0; + } + } + + map_item = malloc(sizeof(struct chunk_map_item)); + if (!map_item) + return -1; + + map_item->logical = key->offset; + map_item->length = chunk->length; + map_item->physical = le64_to_cpu(chunk->stripe.offset); + rb_link_node(&map_item->node, prnt, new); + rb_insert_color(&map_item->node, &btrfs_info.chunks_root); + + debug("%s: Mapping %llu to %llu\n", __func__, map_item->logical, + map_item->physical); + + return 0; +} + +u64 btrfs_map_logical_to_physical(u64 logical) +{ + struct rb_node *node = btrfs_info.chunks_root.rb_node; + + while (node) { + struct chunk_map_item *item; + + item = rb_entry(node, struct chunk_map_item, node); + + if (item->logical > logical) + node = node->rb_left; + else if (logical > item->logical + item->length) + node = node->rb_right; + else + return item->physical + logical - item->logical; + } + + printf("%s: Cannot map logical address %llu to physical\n", __func__, + logical); + + return -1ULL; +} + +void btrfs_chunk_map_exit(void) +{ + struct rb_node *now, *next; + struct chunk_map_item *item; + + for (now = rb_first_postorder(&btrfs_info.chunks_root); now; now = next) + { + item = rb_entry(now, struct chunk_map_item, node); + next = rb_next_postorder(now); + free(item); + } +} + +int btrfs_chunk_map_init(void) +{ + u8 sys_chunk_array_copy[sizeof(btrfs_info.sb.sys_chunk_array)]; + u8 * const start = sys_chunk_array_copy; + u8 * const end = start + btrfs_info.sb.sys_chunk_array_size; + u8 *cur; + struct btrfs_key *key; + struct btrfs_chunk *chunk; + + btrfs_info.chunks_root = RB_ROOT; + + memcpy(sys_chunk_array_copy, btrfs_info.sb.sys_chunk_array, + sizeof(sys_chunk_array_copy)); + + for (cur = start; cur < end;) { + key = (struct btrfs_key *) cur; + cur += sizeof(struct btrfs_key); + chunk = (struct btrfs_chunk *) cur; + + btrfs_key_to_cpu(key); + btrfs_chunk_to_cpu(chunk); + + if (key->type != BTRFS_CHUNK_ITEM_KEY) { + printf("%s: invalid key type %u\n", __func__, + key->type); + return -1; + } + + if (add_chunk_mapping(key, chunk)) + return -1; + + cur += sizeof(struct btrfs_chunk); + cur += sizeof(struct btrfs_stripe) * (chunk->num_stripes - 1); + } + + return 0; +} + +int btrfs_read_chunk_tree(void) +{ + struct btrfs_path path; + struct btrfs_key key, *found_key; + struct btrfs_chunk *chunk; + int res; + + key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID; + key.type = BTRFS_CHUNK_ITEM_KEY; + key.offset = 0; + + if (btrfs_search_tree(&btrfs_info.chunk_root, &key, &path)) + return -1; + + do { + found_key = btrfs_path_leaf_key(&path); + if (btrfs_comp_keys_type(&key, found_key)) + break; + + chunk = btrfs_path_item_ptr(&path, struct btrfs_chunk); + btrfs_chunk_to_cpu(chunk); + if (add_chunk_mapping(found_key, chunk)) { + res = -1; + break; + } + } while (!(res = btrfs_next_slot(&path))); + + btrfs_free_path(&path); + + if (res < 0) + return -1; + + return 0; +} diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c new file mode 100644 index 0000000000..a59ff5a8bb --- /dev/null +++ b/fs/btrfs/compression.c @@ -0,0 +1,134 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" +#include <linux/lzo.h> +#include <u-boot/zlib.h> + +static u32 decompress_lzo(const u8 *cbuf, u32 clen, u8 *dbuf, u32 dlen) +{ + u32 tot_len, in_len, res; + size_t out_len; + int ret; + + if (clen < 4) + return -1; + + tot_len = le32_to_cpu(*(u32 *) cbuf); + cbuf += 4; + clen -= 4; + tot_len -= 4; + + if (tot_len == 0 && dlen) + return -1; + if (tot_len < 4) + return -1; + + res = 0; + + while (tot_len > 4) { + in_len = le32_to_cpu(*(u32 *) cbuf); + cbuf += 4; + clen -= 4; + + if (in_len > clen || tot_len < 4 + in_len) + return -1; + + tot_len -= 4 + in_len; + + out_len = dlen; + ret = lzo1x_decompress_safe(cbuf, in_len, dbuf, &out_len); + if (ret != LZO_E_OK) + return -1; + + cbuf += in_len; + clen -= in_len; + dbuf += out_len; + dlen -= out_len; + + res += out_len; + } + + return res; +} + +/* from zutil.h */ +#define PRESET_DICT 0x20 + +static u32 decompress_zlib(const u8 *_cbuf, u32 clen, u8 *dbuf, u32 dlen) +{ + int wbits = MAX_WBITS, ret = -1; + z_stream stream; + u8 *cbuf; + u32 res; + + memset(&stream, 0, sizeof(stream)); + + cbuf = (u8 *) _cbuf; + + stream.total_in = 0; + + stream.next_out = dbuf; + stream.avail_out = dlen; + stream.total_out = 0; + + /* skip adler32 check if deflate and no dictionary */ + if (clen > 2 && !(cbuf[1] & PRESET_DICT) && + ((cbuf[0] & 0x0f) == Z_DEFLATED) && + !(((cbuf[0] << 8) + cbuf[1]) % 31)) { + wbits = -((cbuf[0] >> 4) + 8); + cbuf += 2; + clen -= 2; + } + + if (Z_OK != inflateInit2(&stream, wbits)) + return -1; + + while (stream.total_in < clen) { + stream.next_in = cbuf + stream.total_in; + stream.avail_in = min((u32) (clen - stream.total_in), + (u32) btrfs_info.sb.sectorsize); + + ret = inflate(&stream, Z_NO_FLUSH); + if (ret != Z_OK) + break; + } + + res = stream.total_out; + inflateEnd(&stream); + + if (ret != Z_STREAM_END) + return -1; + + return res; +} + +u32 btrfs_decompress(u8 type, const char *c, u32 clen, char *d, u32 dlen) +{ + u32 res; + const u8 *cbuf; + u8 *dbuf; + + cbuf = (const u8 *) c; + dbuf = (u8 *) d; + + switch (type) { + case BTRFS_COMPRESS_NONE: + res = dlen < clen ? dlen : clen; + memcpy(dbuf, cbuf, res); + return res; + case BTRFS_COMPRESS_ZLIB: + return decompress_zlib(cbuf, clen, dbuf, dlen); + case BTRFS_COMPRESS_LZO: + return decompress_lzo(cbuf, clen, dbuf, dlen); + default: + printf("%s: Unsupported compression in extent: %i\n", __func__, + type); + return -1; + } +} diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c new file mode 100644 index 0000000000..b13ecb9376 --- /dev/null +++ b/fs/btrfs/ctree.c @@ -0,0 +1,289 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" +#include <malloc.h> + +int btrfs_comp_keys(struct btrfs_key *a, struct btrfs_key *b) +{ + if (a->objectid > b->objectid) + return 1; + if (a->objectid < b->objectid) + return -1; + if (a->type > b->type) + return 1; + if (a->type < b->type) + return -1; + if (a->offset > b->offset) + return 1; + if (a->offset < b->offset) + return -1; + return 0; +} + +int btrfs_comp_keys_type(struct btrfs_key *a, struct btrfs_key *b) +{ + if (a->objectid > b->objectid) + return 1; + if (a->objectid < b->objectid) + return -1; + if (a->type > b->type) + return 1; + if (a->type < b->type) + return -1; + return 0; +} + +static int generic_bin_search(void *addr, int item_size, struct btrfs_key *key, + int max, int *slot) +{ + int low = 0, high = max, mid, ret; + struct btrfs_key *tmp; + + if (0) { + int i; + printf("\tsearching %llu %i\n", key->objectid, key->type); + for (i = 0; i < max; ++i) { + tmp = (struct btrfs_key *) ((u8 *) addr + i*item_size); + printf("\t\t%llu %i\n", tmp->objectid, tmp->type); + } + printf("\n"); + } + + while (low < high) { + mid = (low + high) / 2; + + tmp = (struct btrfs_key *) ((u8 *) addr + mid*item_size); + ret = btrfs_comp_keys(tmp, key); + + if (ret < 0) { + low = mid + 1; + } else if (ret > 0) { + high = mid; + } else { + *slot = mid; + return 0; + } + } + + *slot = low; + return 1; +} + +int btrfs_bin_search(union btrfs_tree_node *p, struct btrfs_key *key, + int *slot) +{ + void *addr; + unsigned long size; + + if (p->header.level) { + addr = p->node.ptrs; + size = sizeof(struct btrfs_key_ptr); + } else { + addr = p->leaf.items; + size = sizeof(struct btrfs_item); + } + + return generic_bin_search(addr, size, key, p->header.nritems, slot); +} + +static void clear_path(struct btrfs_path *p) +{ + int i; + + for (i = 0; i < BTRFS_MAX_LEVEL; ++i) { + p->nodes[i] = NULL; + p->slots[i] = 0; + } +} + +void btrfs_free_path(struct btrfs_path *p) +{ + int i; + + for (i = 0; i < BTRFS_MAX_LEVEL; ++i) { + if (p->nodes[i]) + free(p->nodes[i]); + } + + clear_path(p); +} + +static int read_tree_node(u64 physical, union btrfs_tree_node **buf) +{ + struct btrfs_header hdr; + unsigned long size, offset = sizeof(hdr); + union btrfs_tree_node *res; + u32 i; + + if (!btrfs_devread(physical, sizeof(hdr), &hdr)) + return -1; + + btrfs_header_to_cpu(&hdr); + + if (hdr.level) + size = sizeof(struct btrfs_node) + + hdr.nritems * sizeof(struct btrfs_key_ptr); + else + size = btrfs_info.sb.nodesize; + + res = malloc(size); + if (!res) { + debug("%s: malloc failed\n", __func__); + return -1; + } + + if (!btrfs_devread(physical + offset, size - offset, + ((u8 *) res) + offset)) { + free(res); + return -1; + } + + res->header = hdr; + if (hdr.level) + for (i = 0; i < hdr.nritems; ++i) + btrfs_key_ptr_to_cpu(&res->node.ptrs[i]); + else + for (i = 0; i < hdr.nritems; ++i) + btrfs_item_to_cpu(&res->leaf.items[i]); + + *buf = res; + + return 0; +} + +int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key, + struct btrfs_path *p) +{ + u8 lvl, prev_lvl; + int i, slot, ret; + u64 logical, physical; + union btrfs_tree_node *buf; + + clear_path(p); + + logical = root->bytenr; + + for (i = 0; i < BTRFS_MAX_LEVEL; ++i) { + physical = btrfs_map_logical_to_physical(logical); + if (physical == -1ULL) + goto err; + + if (read_tree_node(physical, &buf)) + goto err; + + lvl = buf->header.level; + if (i && prev_lvl != lvl + 1) { + printf("%s: invalid level in header at %llu\n", + __func__, logical); + goto err; + } + prev_lvl = lvl; + + ret = btrfs_bin_search(buf, key, &slot); + if (ret < 0) + goto err; + if (ret && slot > 0 && lvl) + slot -= 1; + + p->slots[lvl] = slot; + p->nodes[lvl] = buf; + + if (lvl) + logical = buf->node.ptrs[slot].blockptr; + else + break; + } + + return 0; +err: + btrfs_free_path(p); + return -1; +} + +static int jump_leaf(struct btrfs_path *path, int dir) +{ + struct btrfs_path p; + u32 slot; + int level = 1, from_level, i; + + dir = dir >= 0 ? 1 : -1; + + p = *path; + + while (level < BTRFS_MAX_LEVEL) { + if (!p.nodes[level]) + return 1; + + slot = p.slots[level]; + if ((dir > 0 && slot + dir >= p.nodes[level]->header.nritems) + || (dir < 0 && !slot)) + level++; + else + break; + } + + if (level == BTRFS_MAX_LEVEL) + return 1; + + p.slots[level] = slot + dir; + level--; + from_level = level; + + while (level >= 0) { + u64 logical, physical; + + slot = p.slots[level + 1]; + logical = p.nodes[level + 1]->node.ptrs[slot].blockptr; + physical = btrfs_map_logical_to_physical(logical); + if (physical == -1ULL) + goto err; + + if (read_tree_node(physical, &p.nodes[level])) + goto err; + + if (dir > 0) + p.slots[level] = 0; + else + p.slots[level] = p.nodes[level]->header.nritems - 1; + level--; + } + + /* Free rewritten nodes in path */ + for (i = 0; i <= from_level; ++i) + free(path->nodes[i]); + + *path = p; + return 0; + +err: + /* Free rewritten nodes in p */ + for (i = level + 1; i <= from_level; ++i) + free(p.nodes[i]); + return -1; +} + +int btrfs_prev_slot(struct btrfs_path *p) +{ + if (!p->slots[0]) + return jump_leaf(p, -1); + + p->slots[0]--; + return 0; +} + +int btrfs_next_slot(struct btrfs_path *p) +{ + struct btrfs_leaf *leaf = &p->nodes[0]->leaf; + + if (p->slots[0] >= leaf->header.nritems) + return jump_leaf(p, 1); + + p->slots[0]++; + return 0; +} diff --git a/fs/btrfs/dev.c b/fs/btrfs/dev.c new file mode 100644 index 0000000000..fd2e9b6127 --- /dev/null +++ b/fs/btrfs/dev.c @@ -0,0 +1,26 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include <common.h> +#include <compiler.h> +#include <fs_internal.h> + +struct blk_desc *btrfs_blk_desc; +disk_partition_t *btrfs_part_info; + +int btrfs_devread(u64 address, int byte_len, void *buf) +{ + lbaint_t sector; + int byte_offset; + + sector = address >> btrfs_blk_desc->log2blksz; + byte_offset = address % btrfs_blk_desc->blksz; + + return fs_devread(btrfs_blk_desc, btrfs_part_info, sector, byte_offset, + byte_len, buf); +} diff --git a/fs/btrfs/dir-item.c b/fs/btrfs/dir-item.c new file mode 100644 index 0000000000..decf86eb53 --- /dev/null +++ b/fs/btrfs/dir-item.c @@ -0,0 +1,125 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" + +static int verify_dir_item(struct btrfs_dir_item *item, u32 start, u32 total) +{ + u16 max_len = BTRFS_NAME_LEN; + u32 end; + + if (item->type >= BTRFS_FT_MAX) { + printf("%s: invalid dir item type: %i\n", __func__, item->type); + return 1; + } + + if (item->type == BTRFS_FT_XATTR) + max_len = 255; /* XATTR_NAME_MAX */ + + end = start + sizeof(*item) + item->name_len; + if (item->name_len > max_len || end > total) { + printf("%s: invalid dir item name len: %u\n", __func__, + item->name_len); + return 1; + } + + return 0; +} + +static struct btrfs_dir_item * +btrfs_match_dir_item_name(struct btrfs_path *path, const char *name, + int name_len) +{ + struct btrfs_dir_item *item; + u32 total_len, cur = 0, this_len; + const char *name_ptr; + + item = btrfs_path_item_ptr(path, struct btrfs_dir_item); + + total_len = btrfs_path_item_size(path); + + while (cur < total_len) { + btrfs_dir_item_to_cpu(item); + this_len = sizeof(*item) + item->name_len + item->data_len; + name_ptr = (const char *) (item + 1); + + if (verify_dir_item(item, cur, total_len)) + return NULL; + if (item->name_len == name_len && !memcmp(name_ptr, name, + name_len)) + return item; + + cur += this_len; + item = (struct btrfs_dir_item *) ((u8 *) item + this_len); + } + + return NULL; +} + +int btrfs_lookup_dir_item(const struct btrfs_root *root, u64 dir, + const char *name, int name_len, + struct btrfs_dir_item *item) +{ + struct btrfs_path path; + struct btrfs_key key; + struct btrfs_dir_item *res = NULL; + + key.objectid = dir; + key.type = BTRFS_DIR_ITEM_KEY; + key.offset = btrfs_name_hash(name, name_len); + + if (btrfs_search_tree(root, &key, &path)) + return -1; + + if (btrfs_comp_keys_type(&key, btrfs_path_leaf_key(&path))) + goto out; + + res = btrfs_match_dir_item_name(&path, name, name_len); + if (res) + *item = *res; +out: + btrfs_free_path(&path); + return res ? 0 : -1; +} + +int btrfs_readdir(const struct btrfs_root *root, u64 dir, + btrfs_readdir_callback_t callback) +{ + struct btrfs_path path; + struct btrfs_key key, *found_key; + struct btrfs_dir_item *item; + int res; + + key.objectid = dir; + key.type = BTRFS_DIR_INDEX_KEY; + key.offset = 0; + + if (btrfs_search_tree(root, &key, &path)) + return -1; + + do { + found_key = btrfs_path_leaf_key(&path); + if (btrfs_comp_keys_type(&key, found_key)) + break; + + item = btrfs_path_item_ptr(&path, struct btrfs_dir_item); + btrfs_dir_item_to_cpu(item); + + if (verify_dir_item(item, 0, sizeof(*item) + item->name_len)) + continue; + if (item->type == BTRFS_FT_XATTR) + continue; + + if (callback(root, item)) + break; + } while (!(res = btrfs_next_slot(&path))); + + btrfs_free_path(&path); + + return res < 0 ? -1 : 0; +} diff --git a/fs/btrfs/extent-io.c b/fs/btrfs/extent-io.c new file mode 100644 index 0000000000..feb91432e9 --- /dev/null +++ b/fs/btrfs/extent-io.c @@ -0,0 +1,120 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" +#include <malloc.h> + +u64 btrfs_read_extent_inline(struct btrfs_path *path, + struct btrfs_file_extent_item *extent, u64 offset, + u64 size, char *out) +{ + u32 clen, dlen, orig_size = size, res; + const char *cbuf; + char *dbuf; + const int data_off = offsetof(struct btrfs_file_extent_item, + disk_bytenr); + + clen = btrfs_path_item_size(path) - data_off; + cbuf = (const char *) extent + data_off; + dlen = extent->ram_bytes; + + if (offset > dlen) + return -1ULL; + + if (size > dlen - offset) + size = dlen - offset; + + if (extent->compression == BTRFS_COMPRESS_NONE) { + memcpy(out, cbuf + offset, size); + return size; + } + + if (dlen > orig_size) { + dbuf = malloc(dlen); + if (!dbuf) + return -1ULL; + } else { + dbuf = out; + } + + res = btrfs_decompress(extent->compression, cbuf, clen, dbuf, dlen); + if (res == -1 || res != dlen) + goto err; + + if (dlen > orig_size) { + memcpy(out, dbuf + offset, size); + free(dbuf); + } else if (offset) { + memmove(out, dbuf + offset, size); + } + + return size; + +err: + if (dlen > orig_size) + free(dbuf); + return -1ULL; +} + +u64 btrfs_read_extent_reg(struct btrfs_path *path, + struct btrfs_file_extent_item *extent, u64 offset, + u64 size, char *out) +{ + u64 physical, clen, dlen, orig_size = size; + u32 res; + char *cbuf, *dbuf; + + clen = extent->disk_num_bytes; + dlen = extent->num_bytes; + + if (offset > dlen) + return -1ULL; + + if (size > dlen - offset) + size = dlen - offset; + + physical = btrfs_map_logical_to_physical(extent->disk_bytenr); + if (physical == -1ULL) + return -1ULL; + + if (extent->compression == BTRFS_COMPRESS_NONE) { + physical += extent->offset + offset; + if (!btrfs_devread(physical, size, out)) + return -1ULL; + + return size; + } + + cbuf = malloc(dlen > size ? clen + dlen : clen); + if (!cbuf) + return -1ULL; + + if (dlen > orig_size) + dbuf = cbuf + clen; + else + dbuf = out; + + if (!btrfs_devread(physical, clen, cbuf)) + goto err; + + res = btrfs_decompress(extent->compression, cbuf, clen, dbuf, dlen); + if (res == -1) + goto err; + + if (dlen > orig_size) + memcpy(out, dbuf + offset, size); + else + memmove(out, dbuf + offset, size); + + free(cbuf); + return res; + +err: + free(cbuf); + return -1ULL; +} diff --git a/fs/btrfs/hash.c b/fs/btrfs/hash.c new file mode 100644 index 0000000000..f8a50e532a --- /dev/null +++ b/fs/btrfs/hash.c @@ -0,0 +1,38 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" +#include <u-boot/crc.h> + +static u32 btrfs_crc32c_table[256]; + +void btrfs_hash_init(void) +{ + static int inited = 0; + + if (!inited) { + crc32c_init(btrfs_crc32c_table, 0x82F63B78); + inited = 1; + } +} + +u32 btrfs_crc32c(u32 crc, const void *data, size_t length) +{ + return crc32c_cal(crc, (const char *) data, length, + btrfs_crc32c_table); +} + +u32 btrfs_csum_data(char *data, u32 seed, size_t len) +{ + return btrfs_crc32c(seed, data, len); +} + +void btrfs_csum_final(u32 crc, void *result) +{ + *((u32 *) result) = cpu_to_le32(~crc); +} diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c new file mode 100644 index 0000000000..0d3da28296 --- /dev/null +++ b/fs/btrfs/inode.c @@ -0,0 +1,385 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" +#include <malloc.h> + +u64 btrfs_lookup_inode_ref(struct btrfs_root *root, u64 inr, + struct btrfs_inode_ref *refp, char *name) +{ + struct btrfs_path path; + struct btrfs_key *key; + struct btrfs_inode_ref *ref; + u64 res = -1ULL; + + key = btrfs_search_tree_key_type(root, inr, BTRFS_INODE_REF_KEY, + &path); + + if (!key) + return -1ULL; + + ref = btrfs_path_item_ptr(&path, struct btrfs_inode_ref); + btrfs_inode_ref_to_cpu(ref); + + if (refp) + *refp = *ref; + + if (name) { + if (ref->name_len > BTRFS_NAME_MAX) { + printf("%s: inode name too long: %u\n", __func__, + ref->name_len); + goto out; + } + + memcpy(name, ref + 1, ref->name_len); + } + + res = key->offset; +out: + btrfs_free_path(&path); + return res; +} + +int btrfs_lookup_inode(const struct btrfs_root *root, + struct btrfs_key *location, + struct btrfs_inode_item *item, + struct btrfs_root *new_root) +{ + struct btrfs_root tmp_root = *root; + struct btrfs_path path; + int res = -1; + + if (location->type == BTRFS_ROOT_ITEM_KEY) { + if (btrfs_find_root(location->objectid, &tmp_root, NULL)) + return -1; + + location->objectid = tmp_root.root_dirid; + location->type = BTRFS_INODE_ITEM_KEY; + location->offset = 0; + } + + if (btrfs_search_tree(&tmp_root, location, &path)) + return res; + + if (btrfs_comp_keys(location, btrfs_path_leaf_key(&path))) + goto out; + + if (item) { + *item = *btrfs_path_item_ptr(&path, struct btrfs_inode_item); + btrfs_inode_item_to_cpu(item); + } + + if (new_root) + *new_root = tmp_root; + + res = 0; + +out: + btrfs_free_path(&path); + return res; +} + +int btrfs_readlink(const struct btrfs_root *root, u64 inr, char *target) +{ + struct btrfs_path path; + struct btrfs_key key; + struct btrfs_file_extent_item *extent; + const char *data_ptr; + int res = -1; + + key.objectid = inr; + key.type = BTRFS_EXTENT_DATA_KEY; + key.offset = 0; + + if (btrfs_search_tree(root, &key, &path)) + return -1; + + if (btrfs_comp_keys(&key, btrfs_path_leaf_key(&path))) + goto out; + + extent = btrfs_path_item_ptr(&path, struct btrfs_file_extent_item); + if (extent->type != BTRFS_FILE_EXTENT_INLINE) { + printf("%s: Extent for symlink %llu not of INLINE type\n", + __func__, inr); + goto out; + } + + btrfs_file_extent_item_to_cpu_inl(extent); + + if (extent->compression != BTRFS_COMPRESS_NONE) { + printf("%s: Symlink %llu extent data compressed!\n", __func__, + inr); + goto out; + } else if (extent->encryption != 0) { + printf("%s: Symlink %llu extent data encrypted!\n", __func__, + inr); + goto out; + } else if (extent->ram_bytes >= btrfs_info.sb.sectorsize) { + printf("%s: Symlink %llu extent data too long (%llu)!\n", + __func__, inr, extent->ram_bytes); + goto out; + } + + data_ptr = (const char *) extent + + offsetof(struct btrfs_file_extent_item, disk_bytenr); + + memcpy(target, data_ptr, extent->ram_bytes); + target[extent->ram_bytes] = '\0'; + res = 0; +out: + btrfs_free_path(&path); + return res; +} + +/* inr must be a directory (for regular files with multiple hard links this + function returns only one of the parents of the file) */ +static u64 get_parent_inode(struct btrfs_root *root, u64 inr, + struct btrfs_inode_item *inode_item) +{ + struct btrfs_key key; + u64 res; + + if (inr == BTRFS_FIRST_FREE_OBJECTID) { + if (root->objectid != btrfs_info.fs_root.objectid) { + u64 parent; + struct btrfs_root_ref ref; + + parent = btrfs_lookup_root_ref(root->objectid, &ref, + NULL); + if (parent == -1ULL) + return -1ULL; + + if (btrfs_find_root(parent, root, NULL)) + return -1ULL; + + inr = ref.dirid; + } + + if (inode_item) { + key.objectid = inr; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + if (btrfs_lookup_inode(root, &key, inode_item, NULL)) + return -1ULL; + } + + return inr; + } + + res = btrfs_lookup_inode_ref(root, inr, NULL, NULL); + if (res == -1ULL) + return -1ULL; + + if (inode_item) { + key.objectid = res; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + if (btrfs_lookup_inode(root, &key, inode_item, NULL)) + return -1ULL; + } + + return res; +} + +static inline int next_length(const char *path) +{ + int res = 0; + while (*path != '\0' && *path != '/' && res <= BTRFS_NAME_LEN) + ++res, ++path; + return res; +} + +static inline const char *skip_current_directories(const char *cur) +{ + while (1) { + if (cur[0] == '/') + ++cur; + else if (cur[0] == '.' && cur[1] == '/') + cur += 2; + else + break; + } + + return cur; +} + +/* inode.c, musi vratit aj root stromu kde sa inoda najde */ +u64 btrfs_lookup_path(struct btrfs_root *root, u64 inr, const char *path, + u8 *type_p, struct btrfs_inode_item *inode_item_p, + int symlink_limit) +{ + struct btrfs_dir_item item; + struct btrfs_inode_item inode_item; + u8 type = BTRFS_FT_DIR; + int len, have_inode = 0; + const char *cur = path; + + if (*cur == '/') { + ++cur; + inr = root->root_dirid; + } + + do { + cur = skip_current_directories(cur); + + len = next_length(cur); + if (len > BTRFS_NAME_LEN) { + printf("%s: Name too long at "%.*s"\n", __func__, + BTRFS_NAME_LEN, cur); + return -1ULL; + } + + if (len == 1 && cur[0] == '.') + break; + + if (len == 2 && cur[0] == '.' && cur[1] == '.') { + cur += 2; + inr = get_parent_inode(root, inr, &inode_item); + if (inr == -1ULL) + return -1ULL; + + type = BTRFS_FT_DIR; + continue; + } + + if (!*cur) + break; + + if (btrfs_lookup_dir_item(root, inr, cur, len, &item)) + return -1ULL; + + type = item.type; + have_inode = 1; + if (btrfs_lookup_inode(root, &item.location, &inode_item, root)) + return -1ULL; + + if (item.type == BTRFS_FT_SYMLINK && symlink_limit >= 0) { + char *target; + + if (!symlink_limit) { + printf("%s: Too much symlinks!\n", __func__); + return -1ULL; + } + + target = malloc(min(inode_item.size + 1, + (u64) btrfs_info.sb.sectorsize)); + if (!target) + return -1ULL; + + if (btrfs_readlink(root, item.location.objectid, + target)) { + free(target); + return -1ULL; + } + + inr = btrfs_lookup_path(root, inr, target, &type, + &inode_item, symlink_limit - 1); + + free(target); + + if (inr == -1ULL) + return -1ULL; + } else if (item.type != BTRFS_FT_DIR && cur[len]) { + printf("%s: "%.*s" not a directory\n", __func__, + (int) (cur - path + len), path); + return -1ULL; + } else { + inr = item.location.objectid; + } + + cur += len; + } while (*cur); + + if (type_p) + *type_p = type; + + if (inode_item_p) { + if (!have_inode) { + struct btrfs_key key; + + key.objectid = inr; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + if (btrfs_lookup_inode(root, &key, &inode_item, NULL)) + return -1ULL; + } + + *inode_item_p = inode_item; + } + + return inr; +} + +u64 btrfs_file_read(const struct btrfs_root *root, u64 inr, u64 offset, + u64 size, char *buf) +{ + struct btrfs_path path; + struct btrfs_key key; + struct btrfs_file_extent_item *extent; + int res; + u64 rd, rd_all = -1ULL; + + key.objectid = inr; + key.type = BTRFS_EXTENT_DATA_KEY; + key.offset = offset; + + if (btrfs_search_tree(root, &key, &path)) + return -1ULL; + + if (btrfs_comp_keys(&key, btrfs_path_leaf_key(&path)) < 0) { + if (btrfs_prev_slot(&path)) + goto out; + + if (btrfs_comp_keys_type(&key, btrfs_path_leaf_key(&path))) + goto out; + } + + rd_all = 0; + + do { + if (btrfs_comp_keys_type(&key, btrfs_path_leaf_key(&path))) + break; + + extent = btrfs_path_item_ptr(&path, + struct btrfs_file_extent_item); + + if (extent->type == BTRFS_FILE_EXTENT_INLINE) { + btrfs_file_extent_item_to_cpu_inl(extent); + rd = btrfs_read_extent_inline(&path, extent, offset, + size, buf); + } else { + btrfs_file_extent_item_to_cpu(extent); + rd = btrfs_read_extent_reg(&path, extent, offset, size, + buf); + } + + if (rd == -1ULL) { + printf("%s: Error reading extent\n", __func__); + rd_all = -1; + goto out; + } + + offset = 0; + buf += rd; + rd_all += rd; + size -= rd; + + if (!size) + break; + } while (!(res = btrfs_next_slot(&path))); + + if (res) + return -1ULL; + +out: + btrfs_free_path(&path); + return rd_all; +} diff --git a/fs/btrfs/root.c b/fs/btrfs/root.c new file mode 100644 index 0000000000..c405813b69 --- /dev/null +++ b/fs/btrfs/root.c @@ -0,0 +1,93 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" + +static void read_root_item(struct btrfs_path *p, struct btrfs_root_item *item) +{ + u32 len; + int reset = 0; + + len = btrfs_path_item_size(p); + memcpy(item, btrfs_path_item_ptr(p, struct btrfs_root_item), len); + btrfs_root_item_to_cpu(item); + + if (len < sizeof(*item)) + reset = 1; + if (!reset && item->generation != item->generation_v2) { + if (item->generation_v2 != 0) + printf("%s: generation != generation_v2 in root item", + __func__); + reset = 1; + } + if (reset) { + memset(&item->generation_v2, 0, + sizeof(*item) - offsetof(struct btrfs_root_item, + generation_v2)); + } +} + +int btrfs_find_root(u64 objectid, struct btrfs_root *root, + struct btrfs_root_item *root_item) +{ + struct btrfs_path path; + struct btrfs_root_item my_root_item; + + if (!btrfs_search_tree_key_type(&btrfs_info.tree_root, objectid, + BTRFS_ROOT_ITEM_KEY, &path)) + return -1; + + if (!root_item) + root_item = &my_root_item; + read_root_item(&path, root_item); + + if (root) { + root->objectid = objectid; + root->bytenr = root_item->bytenr; + root->root_dirid = root_item->root_dirid; + } + + btrfs_free_path(&path); + return 0; +} + +u64 btrfs_lookup_root_ref(u64 subvolid, struct btrfs_root_ref *refp, char *name) +{ + struct btrfs_path path; + struct btrfs_key *key; + struct btrfs_root_ref *ref; + u64 res = -1ULL; + + key = btrfs_search_tree_key_type(&btrfs_info.tree_root, subvolid, + BTRFS_ROOT_BACKREF_KEY, &path); + + if (!key) + return -1ULL; + + ref = btrfs_path_item_ptr(&path, struct btrfs_root_ref); + btrfs_root_ref_to_cpu(ref); + + if (refp) + *refp = *ref; + + if (name) { + if (ref->name_len > BTRFS_VOL_NAME_MAX) { + printf("%s: volume name too long: %u\n", __func__, + ref->name_len); + goto out; + } + + memcpy(name, ref + 1, ref->name_len); + } + + res = key->offset; +out: + btrfs_free_path(&path); + return res; +} + diff --git a/fs/btrfs/subvolume.c b/fs/btrfs/subvolume.c new file mode 100644 index 0000000000..54e0ab4546 --- /dev/null +++ b/fs/btrfs/subvolume.c @@ -0,0 +1,131 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" +#include <malloc.h> + +static int get_subvol_name(u64 subvolid, char *name, int max_len) +{ + struct btrfs_root_ref rref; + struct btrfs_inode_ref iref; + struct btrfs_root root; + u64 dir; + char tmp[max(BTRFS_VOL_NAME_MAX, BTRFS_NAME_MAX)]; + char *ptr; + + ptr = name + max_len - 1; + *ptr = '\0'; + + while (subvolid != BTRFS_FS_TREE_OBJECTID) { + subvolid = btrfs_lookup_root_ref(subvolid, &rref, tmp); + + if (subvolid == -1ULL) + return -1; + + ptr -= rref.name_len + 1; + if (ptr < name) + goto too_long; + + memcpy(ptr + 1, tmp, rref.name_len); + *ptr = '/'; + + if (btrfs_find_root(subvolid, &root, NULL)) + return -1; + + dir = rref.dirid; + + while (dir != BTRFS_FIRST_FREE_OBJECTID) { + dir = btrfs_lookup_inode_ref(&root, dir, &iref, tmp); + + if (dir == -1ULL) + return -1; + + ptr -= iref.name_len + 1; + if (ptr < name) + goto too_long; + + memcpy(ptr + 1, tmp, iref.name_len); + *ptr = '/'; + } + } + + if (ptr == name + max_len - 1) { + name[0] = '/'; + name[1] = '\0'; + } else { + memmove(name, ptr, name + max_len - ptr); + } + + return 0; + +too_long: + printf("%s: subvolume name too long\n", __func__); + return -1; +} + +u64 btrfs_get_default_subvol_objectid(void) +{ + struct btrfs_dir_item item; + + if (btrfs_lookup_dir_item(&btrfs_info.tree_root, + btrfs_info.sb.root_dir_objectid, "default", 7, + &item)) + return BTRFS_FS_TREE_OBJECTID; + return item.location.objectid; +} + +static void list_subvols(u64 tree, char *nameptr, int max_name_len, int level) +{ + struct btrfs_key key, *found_key; + struct btrfs_path path; + struct btrfs_root_ref *ref; + int res; + + key.objectid = tree; + key.type = BTRFS_ROOT_REF_KEY; + key.offset = 0; + + if (btrfs_search_tree(&btrfs_info.tree_root, &key, &path)) + return; + + do { + found_key = btrfs_path_leaf_key(&path); + if (btrfs_comp_keys_type(&key, found_key)) + break; + + ref = btrfs_path_item_ptr(&path, struct btrfs_root_ref); + btrfs_root_ref_to_cpu(ref); + + printf("ID %llu parent %llu name ", found_key->offset, tree); + if (nameptr && !get_subvol_name(found_key->offset, nameptr, + max_name_len)) + printf("%s\n", nameptr); + else + printf("%.*s\n", (int) ref->name_len, + (const char *) (ref + 1)); + + if (level > 0) + list_subvols(found_key->offset, nameptr, max_name_len, + level - 1); + else + printf("%s: Too much recursion, maybe skipping some " + "subvolumes\n", __func__); + } while (!(res = btrfs_next_slot(&path))); + + btrfs_free_path(&path); +} + +void btrfs_list_subvols(void) +{ + char *nameptr = malloc(4096); + + list_subvols(BTRFS_FS_TREE_OBJECTID, nameptr, nameptr ? 4096 : 0, 40); + + if (nameptr) + free(nameptr); +} diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c new file mode 100644 index 0000000000..706286ee2d --- /dev/null +++ b/fs/btrfs/super.c @@ -0,0 +1,233 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" + +#define BTRFS_SUPER_FLAG_SUPP (BTRFS_HEADER_FLAG_WRITTEN \ + | BTRFS_HEADER_FLAG_RELOC \ + | BTRFS_SUPER_FLAG_ERROR \ + | BTRFS_SUPER_FLAG_SEEDING \ + | BTRFS_SUPER_FLAG_METADUMP) + +#define BTRFS_SUPER_INFO_SIZE 4096 + +static int btrfs_newest_root_backup(struct btrfs_super_block *sb) +{ + struct btrfs_root_backup *root_backup; + int i, newest = -1; + + for (i = 0; i < BTRFS_NUM_BACKUP_ROOTS; ++i) { + root_backup = sb->super_roots + i; + if (root_backup->tree_root_gen == sb->generation) + newest = i; + } + + return newest; +} + +static inline int is_power_of_2(u64 x) +{ + return !(x & (x - 1)); +} + +static int btrfs_check_super_csum(char *raw_disk_sb) +{ + struct btrfs_super_block *disk_sb = + (struct btrfs_super_block *) raw_disk_sb; + u16 csum_type = le16_to_cpu(disk_sb->csum_type); + + if (csum_type == BTRFS_CSUM_TYPE_CRC32) { + u32 crc = ~(u32) 0; + const int csum_size = sizeof(crc); + char result[csum_size]; + + crc = btrfs_csum_data(raw_disk_sb + BTRFS_CSUM_SIZE, crc, + BTRFS_SUPER_INFO_SIZE - BTRFS_CSUM_SIZE); + btrfs_csum_final(crc, result); + + if (memcmp(raw_disk_sb, result, csum_size)) + return -1; + } else { + return -1; + } + + return 0; +} + +static int btrfs_check_super(struct btrfs_super_block *sb) +{ + int ret = 0; + + if (sb->flags & ~BTRFS_SUPER_FLAG_SUPP) { + printf("%s: Unsupported flags: %llu\n", __func__, + sb->flags & ~BTRFS_SUPER_FLAG_SUPP); + } + + if (sb->root_level > BTRFS_MAX_LEVEL) { + printf("%s: tree_root level too big: %d >= %d\n", __func__, + sb->root_level, BTRFS_MAX_LEVEL); + ret = -1; + } + + if (sb->chunk_root_level > BTRFS_MAX_LEVEL) { + printf("%s: chunk_root level too big: %d >= %d\n", __func__, + sb->chunk_root_level, BTRFS_MAX_LEVEL); + ret = -1; + } + + if (sb->log_root_level > BTRFS_MAX_LEVEL) { + printf("%s: log_root level too big: %d >= %d\n", __func__, + sb->log_root_level, BTRFS_MAX_LEVEL); + ret = -1; + } + + if (!is_power_of_2(sb->sectorsize) || sb->sectorsize < 4096 || + sb->sectorsize > BTRFS_MAX_METADATA_BLOCKSIZE) { + printf("%s: invalid sectorsize %u\n", __func__, + sb->sectorsize); + ret = -1; + } + + if (!is_power_of_2(sb->nodesize) || sb->nodesize < sb->sectorsize || + sb->nodesize > BTRFS_MAX_METADATA_BLOCKSIZE) { + printf("%s: invalid nodesize %u\n", __func__, sb->nodesize); + ret = -1; + } + + if (sb->nodesize != sb->__unused_leafsize) { + printf("%s: invalid leafsize %u, should be %u\n", __func__, + sb->__unused_leafsize, sb->nodesize); + ret = -1; + } + + if (!IS_ALIGNED(sb->root, sb->sectorsize)) { + printf("%s: tree_root block unaligned: %llu\n", __func__, + sb->root); + ret = -1; + } + + if (!IS_ALIGNED(sb->chunk_root, sb->sectorsize)) { + printf("%s: chunk_root block unaligned: %llu\n", __func__, + sb->chunk_root); + ret = -1; + } + + if (!IS_ALIGNED(sb->log_root, sb->sectorsize)) { + printf("%s: log_root block unaligned: %llu\n", __func__, + sb->log_root); + ret = -1; + } + + if (memcmp(sb->fsid, sb->dev_item.fsid, BTRFS_UUID_SIZE) != 0) { + printf("%s: dev_item UUID does not match fsid\n", __func__); + ret = -1; + } + + if (sb->bytes_used < 6*sb->nodesize) { + printf("%s: bytes_used is too small %llu\n", __func__, + sb->bytes_used); + ret = -1; + } + + if (!is_power_of_2(sb->stripesize)) { + printf("%s: invalid stripesize %u\n", __func__, sb->stripesize); + ret = -1; + } + + if (sb->sys_chunk_array_size > BTRFS_SYSTEM_CHUNK_ARRAY_SIZE) { + printf("%s: system chunk array too big %u > %u\n", __func__, + sb->sys_chunk_array_size, BTRFS_SYSTEM_CHUNK_ARRAY_SIZE); + ret = -1; + } + + if (sb->sys_chunk_array_size < sizeof(struct btrfs_key) + + sizeof(struct btrfs_chunk)) { + printf("%s: system chunk array too small %u < %u\n", __func__, + sb->sys_chunk_array_size, (u32) sizeof(struct btrfs_key) + + sizeof(struct btrfs_chunk)); + ret = -1; + } + + return ret; +} + +int btrfs_read_superblock(void) +{ + const u64 superblock_offsets[4] = { + 0x10000ull, + 0x4000000ull, + 0x4000000000ull, + 0x4000000000000ull + }; + char raw_sb[BTRFS_SUPER_INFO_SIZE]; + struct btrfs_super_block *sb = (struct btrfs_super_block *) raw_sb; + u64 dev_total_bytes; + int i, root_backup_idx; + + dev_total_bytes = (u64) btrfs_part_info->size * btrfs_part_info->blksz; + + btrfs_info.sb.generation = 0; + + for (i = 0; i < 4; ++i) { + if (superblock_offsets[i] + sizeof(sb) > dev_total_bytes) + break; + + if (!btrfs_devread(superblock_offsets[i], BTRFS_SUPER_INFO_SIZE, + raw_sb)) + break; + + if (btrfs_check_super_csum(raw_sb)) { + printf("%s: invalid checksum at superblock mirror %i\n", + __func__, i); + continue; + } + + btrfs_super_block_to_cpu(sb); + + if (sb->magic != BTRFS_MAGIC) { + printf("%s: invalid BTRFS magic 0x%016llX at " + "superblock mirror %i\n", __func__, sb->magic, + i); + } else if (sb->bytenr != superblock_offsets[i]) { + printf("%s: invalid bytenr 0x%016llX (expected " + "0x%016llX) at superblock mirror %i\n", + __func__, sb->bytenr, superblock_offsets[i], i); + } else if (btrfs_check_super(sb)) { + printf("%s: Checking superblock mirror %i failed\n", + __func__, i); + } else if (sb->generation > btrfs_info.sb.generation) { + memcpy(&btrfs_info.sb, sb, sizeof(*sb)); + } else { + /* Nothing */ + } + } + + if (!btrfs_info.sb.generation) { + printf("%s: No valid BTRFS superblock found!\n", __func__); + return -1; + } + + root_backup_idx = btrfs_newest_root_backup(&btrfs_info.sb); + if (root_backup_idx < 0) { + printf("%s: No valid root_backup found!\n", __func__); + return -1; + } + btrfs_info.root_backup = btrfs_info.sb.super_roots + root_backup_idx; + + if (btrfs_info.root_backup->num_devices != 1) { + printf("%s: Unsupported number of devices (%lli). This driver " + "only supports filesystem on one device.\n", __func__, + btrfs_info.root_backup->num_devices); + return -1; + } + + debug("Chosen superblock with generation = %llu\n", + btrfs_info.sb.generation); + + return 0; +}

Signed-off-by: Marek Behun marek.behun@nic.cz

create mode 100644 fs/btrfs/Kconfig create mode 100644 fs/btrfs/Makefile create mode 100644 fs/btrfs/btrfs.c create mode 100644 include/btrfs.h

diff --git a/fs/Kconfig b/fs/Kconfig index e6803ac8cb..1cb9831be8 100644 --- a/fs/Kconfig +++ b/fs/Kconfig @@ -4,6 +4,8 @@

menu "File systems"

+source "fs/btrfs/Kconfig" + source "fs/cbfs/Kconfig"

source "fs/ext4/Kconfig" diff --git a/fs/Makefile b/fs/Makefile index e5bf0df26f..84d1d30f09 100644 --- a/fs/Makefile +++ b/fs/Makefile @@ -12,6 +12,7 @@ obj-$(CONFIG_SPL_EXT_SUPPORT) += ext4/ else obj-y += fs.o fs_internal.o

+obj-$(CONFIG_FS_BTRFS) += btrfs/ obj-$(CONFIG_FS_CBFS) += cbfs/ obj-$(CONFIG_CMD_CRAMFS) += cramfs/ obj-$(CONFIG_FS_EXT4) += ext4/ diff --git a/fs/btrfs/Kconfig b/fs/btrfs/Kconfig new file mode 100644 index 0000000000..22909d9fcc --- /dev/null +++ b/fs/btrfs/Kconfig @@ -0,0 +1,9 @@ +config FS_BTRFS + bool "Enable BTRFS filesystem support" + select CRC32C + select LZO + select RBTREE + help + This provides a single-device read-only BTRFS support. BTRFS is a + next-generation Linux file system based on the copy-on-write + principle. diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile new file mode 100644 index 0000000000..01731557e6 --- /dev/null +++ b/fs/btrfs/Makefile @@ -0,0 +1,8 @@ +# +# 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz +# +# SPDX-License-Identifier: GPL-2.0+ +# + +obj-y := btrfs.o chunk-map.o compression.o ctree.o dev.o dir-item.o \ + extent-io.o hash.o inode.o root.o subvolume.o super.o diff --git a/fs/btrfs/btrfs.c b/fs/btrfs/btrfs.c new file mode 100644 index 0000000000..4140e2bc20 --- /dev/null +++ b/fs/btrfs/btrfs.c @@ -0,0 +1,227 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include "btrfs.h" +#include <config.h> +#include <malloc.h> +#include <linux/time.h> + +struct btrfs_info btrfs_info; + +static int readdir_callback(const struct btrfs_root *root, + struct btrfs_dir_item *item) +{ + static const char typestr[BTRFS_FT_MAX][4] = { + [BTRFS_FT_UNKNOWN] = " ? ", + [BTRFS_FT_REG_FILE] = " ", + [BTRFS_FT_DIR] = "DIR", + [BTRFS_FT_CHRDEV] = "CHR", + [BTRFS_FT_BLKDEV] = "BLK", + [BTRFS_FT_FIFO] = "FIF", + [BTRFS_FT_SOCK] = "SCK", + [BTRFS_FT_SYMLINK] = "SYM", + [BTRFS_FT_XATTR] = " ? ", + }; + struct btrfs_inode_item inode; + const char *name = (const char *) (item + 1); + char filetime[32], *target = NULL; + time_t mtime; + + if (btrfs_lookup_inode(root, &item->location, &inode, NULL)) { + printf("%s: Cannot find inode item for directory entry %.*s!\n", + __func__, item->name_len, name); + return 0; + } + + mtime = inode.mtime.sec; + ctime_r(&mtime, filetime); + + if (item->type == BTRFS_FT_SYMLINK) { + target = malloc(min(inode.size + 1, + (u64) btrfs_info.sb.sectorsize)); + + if (target && btrfs_readlink(root, item->location.objectid, + target)) { + free(target); + target = NULL; + } + + if (!target) + printf("%s: Cannot read symlink target!\n", __func__); + } + + printf("<%s> ", typestr[item->type]); + if (item->type == BTRFS_FT_CHRDEV || item->type == BTRFS_FT_BLKDEV) + printf("%4u,%5u ", (unsigned int) (inode.rdev >> 20), + (unsigned int) (inode.rdev & 0xfffff)); + else + printf("%10llu ", inode.size); + + printf("%24.24s %.*s", filetime, item->name_len, name); + + if (item->type == BTRFS_FT_SYMLINK) { + printf(" -> %s", target ? target : "?"); + if (target) + free(target); + } + + printf("\n"); + + return 0; +} + +int btrfs_probe(struct blk_desc *fs_dev_desc, disk_partition_t *fs_partition) +{ + btrfs_blk_desc = fs_dev_desc; + btrfs_part_info = fs_partition; + + memset(&btrfs_info, 0, sizeof(btrfs_info)); + + btrfs_hash_init(); + if (btrfs_read_superblock()) + return -1; + + if (btrfs_chunk_map_init()) { + printf("%s: failed to init chunk map\n", __func__); + return -1; + } + + btrfs_info.tree_root.objectid = 0; + btrfs_info.tree_root.bytenr = btrfs_info.sb.root; + btrfs_info.chunk_root.objectid = 0; + btrfs_info.chunk_root.bytenr = btrfs_info.sb.chunk_root; + + if (btrfs_read_chunk_tree()) { + printf("%s: failed to read chunk tree\n", __func__); + return -1; + } + + if (btrfs_find_root(btrfs_get_default_subvol_objectid(), + &btrfs_info.fs_root, NULL)) { + printf("%s: failed to find default subvolume\n", __func__); + return -1; + } + + return 0; +} + +int btrfs_ls(const char *path) +{ + struct btrfs_root root = btrfs_info.fs_root; + u64 inr; + u8 type; + + inr = btrfs_lookup_path(&root, root.root_dirid, path, &type, NULL, 40); + + if (inr == -1ULL) { + printf("Cannot lookup path %s\n", path); + return 1; + } + + if (type != BTRFS_FT_DIR) { + printf("Not a directory: %s\n", path); + return 1; + } + + if (btrfs_readdir(&root, inr, readdir_callback)) { + printf("An error occured while listing directory %s\n", path); + return 1; + } + + return 0; +} + +int btrfs_exists(const char *file) +{ + struct btrfs_root root = btrfs_info.fs_root; + u64 inr; + u8 type; + + inr = btrfs_lookup_path(&root, root.root_dirid, file, &type, NULL, 40); + + return (inr != -1ULL && type == BTRFS_FT_REG_FILE); +} + +int btrfs_size(const char *file, loff_t *size) +{ + struct btrfs_root root = btrfs_info.fs_root; + struct btrfs_inode_item inode; + u64 inr; + u8 type; + + inr = btrfs_lookup_path(&root, root.root_dirid, file, &type, &inode, + 40); + + if (inr == -1ULL) { + printf("Cannot lookup file %s\n", file); + return 1; + } + + if (type != BTRFS_FT_REG_FILE) { + printf("Not a regular file: %s\n", file); + return 1; + } + + *size = inode.size; + return 0; +} + +int btrfs_read(const char *file, void *buf, loff_t offset, loff_t len, + loff_t *actread) +{ + struct btrfs_root root = btrfs_info.fs_root; + struct btrfs_inode_item inode; + u64 inr, rd; + u8 type; + + inr = btrfs_lookup_path(&root, root.root_dirid, file, &type, &inode, + 40); + + if (inr == -1ULL) { + printf("Cannot lookup file %s\n", file); + return 1; + } + + if (type != BTRFS_FT_REG_FILE) { + printf("Not a regular file: %s\n", file); + return 1; + } + + if (!len) + len = inode.size; + + if (len > inode.size - offset) + len = inode.size - offset; + + rd = btrfs_file_read(&root, inr, offset, len, buf); + if (rd == -1ULL) { + printf("An error occured while reading file %s\n", file); + return 1; + } + + *actread = rd; + return 0; +} + +void btrfs_close(void) +{ + btrfs_chunk_map_exit(); +} + +int btrfs_uuid(char *uuid_str) +{ +#ifdef CONFIG_LIB_UUID + uuid_bin_to_str(btrfs_info.sb.fsid, uuid_str, UUID_STR_FORMAT_STD); + return 0; +#endif + return -ENOSYS; +} + +/* + btrfs_list_subvols(); +*/ diff --git a/fs/fs.c b/fs/fs.c index 13cd3626c6..6bb2531450 100644 --- a/fs/fs.c +++ b/fs/fs.c @@ -14,6 +14,7 @@ #include <fs.h> #include <sandboxfs.h> #include <ubifs_uboot.h> +#include <btrfs.h> #include <asm/io.h> #include <div64.h> #include <linux/math64.h> @@ -163,6 +164,21 @@ static struct fstype_info fstypes[] = { .uuid = fs_uuid_unsupported, }, #endif +#ifdef CONFIG_FS_BTRFS + { + .fstype = FS_TYPE_BTRFS, + .name = "btrfs", + .null_dev_desc_ok = false, + .probe = btrfs_probe, + .close = btrfs_close, + .ls = btrfs_ls, + .exists = btrfs_exists, + .size = btrfs_size, + .read = btrfs_read, + .write = fs_write_unsupported, + .uuid = btrfs_uuid, + }, +#endif { .fstype = FS_TYPE_ANY, .name = "unsupported", diff --git a/include/btrfs.h b/include/btrfs.h new file mode 100644 index 0000000000..7390975ea7 --- /dev/null +++ b/include/btrfs.h @@ -0,0 +1,21 @@ +/* + * BTRFS filesystem implementation for U-Boot + * + * 2017 Marek Behun, CZ.NIC, marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#ifndef __U_BOOT_BTRFS_H__ +#define __U_BOOT_BTRFS_H__ + +int btrfs_probe(struct blk_desc *, disk_partition_t *); +int btrfs_ls(const char *); +int btrfs_exists(const char *); +int btrfs_size(const char *, loff_t *); +int btrfs_read(const char *, void *, loff_t, loff_t, loff_t *); +void btrfs_close(void); +int btrfs_uuid(char *); +void btrfs_list_subvols(void); + +#endif /* __U_BOOT_BTRFS_H__ */ diff --git a/include/fs.h b/include/fs.h index 2f2aca8378..2e1b9a13ed 100644 --- a/include/fs.h +++ b/include/fs.h @@ -13,6 +13,7 @@ #define FS_TYPE_EXT 2 #define FS_TYPE_SANDBOX 3 #define FS_TYPE_UBIFS 4 +#define FS_TYPE_BTRFS 5

/* * Tell the fs layer which block device an partition to use for future

Signed-off-by: Marek Behun marek.behun@nic.cz

create mode 100644 cmd/btrfs.c

diff --git a/cmd/Kconfig b/cmd/Kconfig index d6d130edfa..77623052c4 100644 --- a/cmd/Kconfig +++ b/cmd/Kconfig @@ -1311,6 +1311,16 @@ config CMD_CROS_EC endmenu

menu "Filesystem commands" +config CMD_BTRFS + bool "Enable the 'btrsubvol' command" + select FS_BTRFS + help + This enables the 'btrsubvol' command to list subvolumes + of a BTRFS filesystem. There are no special commands for + listing BTRFS directories or loading BTRFS files - this + can be done by the generic 'fs' commands (see CMD_FS_GENERIC) + when BTRFS is enabled (see FS_BTRFS). + config CMD_CBFS bool "Enable the 'cbfs' command" depends on FS_CBFS diff --git a/cmd/Makefile b/cmd/Makefile index 2a5b8ce825..2b0444d5b7 100644 --- a/cmd/Makefile +++ b/cmd/Makefile @@ -27,6 +27,7 @@ obj-$(CONFIG_CMD_BOOTMENU) += bootmenu.o obj-$(CONFIG_CMD_BOOTSTAGE) += bootstage.o obj-$(CONFIG_CMD_BOOTZ) += bootz.o obj-$(CONFIG_CMD_BOOTI) += booti.o +obj-$(CONFIG_CMD_BTRFS) += btrfs.o obj-$(CONFIG_CMD_CACHE) += cache.o obj-$(CONFIG_CMD_CBFS) += cbfs.o obj-$(CONFIG_CMD_CLK) += clk.o diff --git a/cmd/btrfs.c b/cmd/btrfs.c new file mode 100644 index 0000000000..3f4f1b782b --- /dev/null +++ b/cmd/btrfs.c @@ -0,0 +1,28 @@ +/* + * 2017 by Marek Behun marek.behun@nic.cz + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include <common.h> +#include <command.h> +#include <btrfs.h> +#include <fs.h> + +int do_btrsubvol(cmd_tbl_t *cmdtp, int flag, int argc, char *const argv[]) +{ + if (argc != 3) + return CMD_RET_USAGE; + + if (fs_set_blk_dev(argv[1], argv[2], FS_TYPE_BTRFS)) + return 1; + + btrfs_list_subvols(); + return 0; +} + +U_BOOT_CMD(btrsubvol, 3, 1, do_btrsubvol, + "list subvolumes of a BTRFS filesystem", + "<interface> <dev[:part]>\n" + " - List subvolumes of a BTRFS filesystem." +)

Signed-off-by: Marek Behun marek.behun@nic.cz

diff --git a/configs/turris_omnia_defconfig b/configs/turris_omnia_defconfig index a3834acb96..9a456e67aa 100644 --- a/configs/turris_omnia_defconfig +++ b/configs/turris_omnia_defconfig @@ -26,6 +26,7 @@ CONFIG_CMD_USB=y CONFIG_CMD_TFTPPUT=y CONFIG_CMD_CACHE=y CONFIG_CMD_TIME=y +CONFIG_CMD_BTRFS=y # CONFIG_SPL_PARTITION_UUIDS is not set CONFIG_ENV_IS_IN_SPI_FLASH=y CONFIG_SPL_OF_TRANSLATE=y