From patchwork Sun Sep 3 15:00:28 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Marek_Beh=C3=BAn?= X-Patchwork-Id: 809315 X-Patchwork-Delegate: trini@ti.com Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=lists.denx.de (client-ip=81.169.180.215; helo=lists.denx.de; envelope-from=u-boot-bounces@lists.denx.de; receiver=) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; secure) header.d=nic.cz header.i=@nic.cz header.b="fj1SgFm1"; dkim-atps=neutral Received: from lists.denx.de (dione.denx.de [81.169.180.215]) by ozlabs.org (Postfix) with ESMTP id 3xlbtX3L2rz9t2y for ; Mon, 4 Sep 2017 01:07:16 +1000 (AEST) Received: by lists.denx.de (Postfix, from userid 105) id 2D03CC21EF6; Sun, 3 Sep 2017 15:05:30 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on lists.denx.de X-Spam-Level: X-Spam-Status: No, score=-5.0 required=5.0 tests=RCVD_IN_DNSWL_HI, T_DKIM_INVALID autolearn=unavailable autolearn_force=no version=3.4.0 Received: from lists.denx.de (localhost [IPv6:::1]) by lists.denx.de (Postfix) with ESMTP id 9F8DFC21F67; Sun, 3 Sep 2017 15:01:43 +0000 (UTC) Received: by lists.denx.de (Postfix, from userid 105) id 9D026C21D65; Sun, 3 Sep 2017 15:01:34 +0000 (UTC) Received: from mail.nic.cz (mail.nic.cz [217.31.204.67]) by lists.denx.de (Postfix) with ESMTPS id 9A012C21DAA for ; Sun, 3 Sep 2017 15:01:33 +0000 (UTC) Received: from dellmb.labs.office.nic.cz (unknown [IPv6:2001:1488:fffe:6:8982:ed8c:62b1:c0c8]) by mail.nic.cz (Postfix) with ESMTP id 49A0362401; Sun, 3 Sep 2017 17:01:33 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=nic.cz; s=default; t=1504450893; bh=vw9A0DZnhEbYR2A/Ez59q/gMP4zjtTC3YWjL3sHOK9g=; h=From:To:Date; b=fj1SgFm1At5zx3f8utgeMj97yu3UYNcz5s2jI3sk0majCl/waBOn3ONIoRCh1UFUA 4ACvoiORPSyUV7KOuRlruJtcLXC+xi8c5q4yhFCsEJ0XSzKS1FTvUdX/OkvJCtb8do LSCXGL9AFMktAYbJIckaKVCJ/btbGZc+ayWBXqdI= From: =?utf-8?q?Marek_Beh=C3=BAn?= To: u-boot@lists.denx.de Date: Sun, 3 Sep 2017 17:00:28 +0200 Message-Id: <20170903150031.18179-7-marek.behun@nic.cz> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20170903150031.18179-1-marek.behun@nic.cz> References: <20170903150031.18179-1-marek.behun@nic.cz> X-Virus-Scanned: clamav-milter 0.99.2 at mail X-Virus-Status: Clean Cc: Tomas Hlavacek , Stefan Roese , =?utf-8?q?Andreas_F=C3=A4rber?= Subject: [U-Boot] [PATCH 6/9] fs: btrfs: Add single-device read-only BTRFS implementation X-BeenThere: u-boot@lists.denx.de X-Mailman-Version: 2.1.18 Precedence: list List-Id: U-Boot discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: u-boot-bounces@lists.denx.de Sender: "U-Boot" 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 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 +#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 + +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 +#include + +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 + +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 +#include +#include + +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 + +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 + +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 + +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 + +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; +}