fs: btrfs: Add single-device read-only BTRFS implementation
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/ctree.c b/fs/btrfs/ctree.c
new file mode 100644
index 0000000..b13ecb9
--- /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;
+}