/* bfs.c - The Bee File System.  */
/*
 *  GRUB  --  GRand Unified Bootloader
 *  Copyright (C) 2010,2011  Free Software Foundation, Inc.
 *
 *  GRUB 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 3 of the License, or
 *  (at your option) any later version.
 *
 *  GRUB is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with GRUB.  If not, see <http://www.gnu.org/licenses/>.
 */
 /*
   Based on the book "Practical File System Design by Dominic Giampaolo
   with corrections and completitions based on Haiku code.
 */

#include <grub/err.h>
#include <grub/file.h>
#include <grub/mm.h>
#include <grub/misc.h>
#include <grub/disk.h>
#include <grub/types.h>
#include <grub/fshelp.h>

GRUB_MOD_LICENSE("GPLv3+");

#ifdef MODE_AFS
#define BTREE_ALIGN 4
#define SUPERBLOCK  2
#else
#define BTREE_ALIGN 8
#define SUPERBLOCK  1
#endif

#define grub_bfs_to_cpu16 grub_le_to_cpu16
#define grub_bfs_to_cpu32 grub_le_to_cpu32
#define grub_bfs_to_cpu64 grub_le_to_cpu64
#define grub_cpu_to_bfs32_compile_time grub_cpu_to_le32_compile_time

#ifdef MODE_AFS
#define grub_bfs_to_cpu_treehead grub_bfs_to_cpu32
#else
#define grub_bfs_to_cpu_treehead grub_bfs_to_cpu16
#endif

#ifdef MODE_AFS
#define SUPER_BLOCK_MAGIC1 0x41465331
#else
#define SUPER_BLOCK_MAGIC1 0x42465331
#endif
#define SUPER_BLOCK_MAGIC2 0xdd121031
#define SUPER_BLOCK_MAGIC3 0x15b6830e
#define POINTER_INVALID 0xffffffffffffffffULL

#define ATTR_TYPE      0160000
#define ATTR_REG       0100000
#define ATTR_DIR       0040000
#define ATTR_LNK       0120000

#define DOUBLE_INDIRECT_SHIFT 2

#define LOG_EXTENT_SIZE 3
GRUB_PACKED_START
struct grub_bfs_extent
{
	grub_uint32_t ag;
	grub_uint16_t start;
	grub_uint16_t len;
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_bfs_superblock
{
	char label[32];
	grub_uint32_t magic1;
	grub_uint32_t unused1;
	grub_uint32_t bsize;
	grub_uint32_t log2_bsize;
	grub_uint8_t unused[20];
	grub_uint32_t magic2;
	grub_uint32_t unused2;
	grub_uint32_t log2_ag_size;
	grub_uint8_t unused3[32];
	grub_uint32_t magic3;
	struct grub_bfs_extent root_dir;
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_bfs_inode
{
	grub_uint8_t unused[20];
	grub_uint32_t mode;
	grub_uint32_t flags;
#ifdef MODE_AFS
	grub_uint8_t unused2[12];
#else
	grub_uint8_t unused2[8];
#endif
	grub_uint64_t mtime;
	grub_uint8_t unused3[8];
	struct grub_bfs_extent attr;
	grub_uint8_t unused4[12];
	GRUB_PACKED_START
	union
	{
		GRUB_PACKED_START
		struct
		{
			struct grub_bfs_extent direct[12];
			grub_uint64_t max_direct_range;
			struct grub_bfs_extent indirect;
			grub_uint64_t max_indirect_range;
			struct grub_bfs_extent double_indirect;
			grub_uint64_t max_double_indirect_range;
			grub_uint64_t size;
			grub_uint32_t pad[4];
		};
		GRUB_PACKED_END
		char inplace_link[144];
	};
	GRUB_PACKED_END
	grub_uint8_t small_data[0];
};
GRUB_PACKED_END

enum
{
	LONG_SYMLINK = 0x40
};

GRUB_PACKED_START
struct grub_bfs_small_data_element_header
{
	grub_uint32_t type;
	grub_uint16_t name_len;
	grub_uint16_t value_len;
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_bfs_btree_header
{
	grub_uint32_t magic;
#ifdef MODE_AFS
	grub_uint64_t root;
	grub_uint32_t level;
	grub_uint32_t node_size;
	grub_uint32_t unused;
#else
	grub_uint32_t node_size;
	grub_uint32_t level;
	grub_uint32_t unused;
	grub_uint64_t root;
#endif
	grub_uint32_t unused2[2];
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_bfs_btree_node
{
	grub_uint64_t unused;
	grub_uint64_t right;
	grub_uint64_t overflow;
#ifdef MODE_AFS
	grub_uint32_t count_keys;
	grub_uint32_t total_key_len;
#else
	grub_uint16_t count_keys;
	grub_uint16_t total_key_len;
#endif
};
GRUB_PACKED_END

struct grub_bfs_data
{
	struct grub_bfs_superblock sb;
	struct grub_bfs_inode ino;
};

/* Context for grub_bfs_dir.  */
struct grub_bfs_dir_ctx
{
	grub_disk_t disk;
	grub_fs_dir_hook_t hook;
	void* hook_data;
	struct grub_bfs_superblock sb;
};

static grub_err_t
read_extent(grub_disk_t disk,
	const struct grub_bfs_superblock* sb,
	const struct grub_bfs_extent* in,
	grub_off_t off, grub_off_t byteoff, void* buf, grub_size_t len)
{
#ifdef MODE_AFS
	return grub_disk_read(disk, ((grub_bfs_to_cpu32(in->ag)
		<< (grub_bfs_to_cpu32(sb->log2_ag_size)
			- GRUB_DISK_SECTOR_BITS))
		+ ((grub_bfs_to_cpu16(in->start) + off)
			<< (grub_bfs_to_cpu32(sb->log2_bsize)
				- GRUB_DISK_SECTOR_BITS))),
		byteoff, len, buf);
#else
	return grub_disk_read(disk, (((grub_bfs_to_cpu32(in->ag)
		<< grub_bfs_to_cpu32(sb->log2_ag_size))
		+ grub_bfs_to_cpu16(in->start) + off)
		<< (grub_bfs_to_cpu32(sb->log2_bsize)
			- GRUB_DISK_SECTOR_BITS)),
		byteoff, len, buf);
#endif
}

#ifdef MODE_AFS
#define RANGE_SHIFT grub_bfs_to_cpu32 (sb->log2_bsize)
#else
#define RANGE_SHIFT 0
#endif

static grub_err_t
read_bfs_file(grub_disk_t disk,
	const struct grub_bfs_superblock* sb,
	const struct grub_bfs_inode* ino,
	grub_off_t off, void* buf, grub_size_t len,
	grub_disk_read_hook_t read_hook, void* read_hook_data)
{
	if (len == 0)
		return GRUB_ERR_NONE;

	if (off + len > grub_bfs_to_cpu64(ino->size))
		return grub_error(GRUB_ERR_OUT_OF_RANGE,
			N_("attempt to read past the end of file"));

	if (off < (grub_bfs_to_cpu64(ino->max_direct_range) << RANGE_SHIFT))
	{
		unsigned i;
		grub_uint64_t pos = 0;
		for (i = 0; i < ARRAY_SIZE(ino->direct); i++)
		{
			grub_uint64_t newpos;
			newpos = pos + (((grub_uint64_t)grub_bfs_to_cpu16(ino->direct[i].len))
				<< grub_bfs_to_cpu32(sb->log2_bsize));
			if (newpos > off)
			{
				grub_size_t read_size;
				grub_err_t err;
				read_size = newpos - off;
				if (read_size > len)
					read_size = len;
				disk->read_hook = read_hook;
				disk->read_hook_data = read_hook_data;
				err = read_extent(disk, sb, &ino->direct[i], 0, off - pos,
					buf, read_size);
				disk->read_hook = 0;
				if (err)
					return err;
				off += read_size;
				len -= read_size;
				buf = (char*)buf + read_size;
				if (len == 0)
					return GRUB_ERR_NONE;
			}
			pos = newpos;
		}
	}

	if (off < (grub_bfs_to_cpu64(ino->max_direct_range) << RANGE_SHIFT))
		return grub_error(GRUB_ERR_BAD_FS, "incorrect direct blocks");

	if (off < (grub_bfs_to_cpu64(ino->max_indirect_range) << RANGE_SHIFT))
	{
		unsigned i;
		struct grub_bfs_extent* entries;
		grub_size_t nentries;
		grub_err_t err;
		grub_uint64_t pos = (grub_bfs_to_cpu64(ino->max_direct_range)
			<< RANGE_SHIFT);
		nentries = (((grub_size_t)grub_bfs_to_cpu16(ino->indirect.len))
			<< (grub_bfs_to_cpu32(sb->log2_bsize) - LOG_EXTENT_SIZE));
		entries = grub_malloc(nentries << LOG_EXTENT_SIZE);
		if (!entries)
			return grub_errno;
		err = read_extent(disk, sb, &ino->indirect, 0, 0,
			entries, nentries << LOG_EXTENT_SIZE);
		for (i = 0; i < nentries; i++)
		{
			grub_uint64_t newpos;
			newpos = pos + (((grub_uint64_t)grub_bfs_to_cpu16(entries[i].len))
				<< grub_bfs_to_cpu32(sb->log2_bsize));
			if (newpos > off)
			{
				grub_size_t read_size;
				read_size = newpos - off;
				if (read_size > len)
					read_size = len;
				disk->read_hook = read_hook;
				disk->read_hook_data = read_hook_data;
				err = read_extent(disk, sb, &entries[i], 0, off - pos,
					buf, read_size);
				disk->read_hook = 0;
				if (err)
				{
					grub_free(entries);
					return err;
				}
				off += read_size;
				len -= read_size;
				buf = (char*)buf + read_size;
				if (len == 0)
				{
					grub_free(entries);
					return GRUB_ERR_NONE;
				}
			}
			pos = newpos;
		}
		grub_free(entries);
	}

	if (off < (grub_bfs_to_cpu64(ino->max_indirect_range) << RANGE_SHIFT))
		return grub_error(GRUB_ERR_BAD_FS, "incorrect indirect blocks");

	{
		struct grub_bfs_extent* l1_entries, * l2_entries;
		grub_size_t nl1_entries, nl2_entries;
		grub_off_t last_l1n = ~0ULL;
		grub_err_t err;
		nl1_entries = (((grub_uint64_t)grub_bfs_to_cpu16(ino->double_indirect.len))
			<< (grub_bfs_to_cpu32(sb->log2_bsize) - LOG_EXTENT_SIZE));
		l1_entries = grub_malloc(nl1_entries << LOG_EXTENT_SIZE);
		if (!l1_entries)
			return grub_errno;
		nl2_entries = 0;
		l2_entries = grub_malloc(1 << (DOUBLE_INDIRECT_SHIFT
			+ grub_bfs_to_cpu32(sb->log2_bsize)));
		if (!l2_entries)
		{
			grub_free(l1_entries);
			return grub_errno;
		}
		err = read_extent(disk, sb, &ino->double_indirect, 0, 0,
			l1_entries, nl1_entries << LOG_EXTENT_SIZE);
		if (err)
		{
			grub_free(l1_entries);
			grub_free(l2_entries);
			return err;
		}

		while (len > 0)
		{
			grub_off_t boff, l2n, l1n;
			grub_size_t read_size;
			grub_off_t double_indirect_offset;
			double_indirect_offset = off
				- grub_bfs_to_cpu64(ino->max_indirect_range);
			boff = (double_indirect_offset
				& ((1 << (grub_bfs_to_cpu32(sb->log2_bsize)
					+ DOUBLE_INDIRECT_SHIFT)) - 1));
			l2n = ((double_indirect_offset >> (grub_bfs_to_cpu32(sb->log2_bsize)
				+ DOUBLE_INDIRECT_SHIFT))
				& ((1 << (grub_bfs_to_cpu32(sb->log2_bsize) - LOG_EXTENT_SIZE
					+ DOUBLE_INDIRECT_SHIFT)) - 1));
			l1n =
				(double_indirect_offset >>
					(2 * grub_bfs_to_cpu32(sb->log2_bsize) - LOG_EXTENT_SIZE +
						2 * DOUBLE_INDIRECT_SHIFT));
			if (l1n > nl1_entries)
			{
				grub_free(l1_entries);
				grub_free(l2_entries);
				return grub_error(GRUB_ERR_BAD_FS,
					"incorrect double-indirect block");
			}
			if (l1n != last_l1n)
			{
				nl2_entries = (((grub_uint64_t)grub_bfs_to_cpu16(l1_entries[l1n].len))
					<< (grub_bfs_to_cpu32(sb->log2_bsize)
						- LOG_EXTENT_SIZE));
				if (nl2_entries > (1U << (grub_bfs_to_cpu32(sb->log2_bsize)
					- LOG_EXTENT_SIZE
					+ DOUBLE_INDIRECT_SHIFT)))
					nl2_entries = (1 << (grub_bfs_to_cpu32(sb->log2_bsize)
						- LOG_EXTENT_SIZE
						+ DOUBLE_INDIRECT_SHIFT));
				err = read_extent(disk, sb, &l1_entries[l1n], 0, 0,
					l2_entries, nl2_entries << LOG_EXTENT_SIZE);
				if (err)
				{
					grub_free(l1_entries);
					grub_free(l2_entries);
					return err;
				}
				last_l1n = l1n;
			}
			if (l2n > nl2_entries)
			{
				grub_free(l1_entries);
				grub_free(l2_entries);
				return grub_error(GRUB_ERR_BAD_FS,
					"incorrect double-indirect block");
			}

			read_size = (1 << (grub_bfs_to_cpu32(sb->log2_bsize)
				+ DOUBLE_INDIRECT_SHIFT)) - boff;
			if (read_size > len)
				read_size = len;
			disk->read_hook = read_hook;
			disk->read_hook_data = read_hook_data;
			err = read_extent(disk, sb, &l2_entries[l2n], 0, boff,
				buf, read_size);
			disk->read_hook = 0;
			if (err)
			{
				grub_free(l1_entries);
				grub_free(l2_entries);
				return err;
			}
			off += read_size;
			len -= read_size;
			buf = (char*)buf + read_size;
		}
		grub_free(l1_entries);
		grub_free(l2_entries);
		return GRUB_ERR_NONE;
	}
}

static grub_err_t
read_b_node(grub_disk_t disk,
	const struct grub_bfs_superblock* sb,
	const struct grub_bfs_inode* ino,
	grub_uint64_t node_off,
	struct grub_bfs_btree_node** node,
	char** key_data, grub_uint16_t** keylen_idx,
	grub_unaligned_uint64_t** key_values)
{
	void* ret;
	struct grub_bfs_btree_node node_head;
	grub_size_t total_size;
	grub_err_t err;

	*node = NULL;
	*key_data = NULL;
	*keylen_idx = NULL;
	*key_values = NULL;

	err = read_bfs_file(disk, sb, ino, node_off, &node_head, sizeof(node_head),
		0, 0);
	if (err)
		return err;

	total_size = ALIGN_UP(sizeof(node_head) +
		grub_bfs_to_cpu_treehead
		(node_head.total_key_len),
		BTREE_ALIGN) +
		grub_bfs_to_cpu_treehead(node_head.count_keys) *
		sizeof(grub_uint16_t)
		+ grub_bfs_to_cpu_treehead(node_head.count_keys) *
		sizeof(grub_uint64_t);

	ret = grub_malloc(total_size);
	if (!ret)
		return grub_errno;

	err = read_bfs_file(disk, sb, ino, node_off, ret, total_size, 0, 0);
	if (err)
	{
		grub_free(ret);
		return err;
	}

	*node = ret;
	*key_data = (char*)ret + sizeof(node_head);
	*keylen_idx = (grub_uint16_t*)ret
		+ ALIGN_UP(sizeof(node_head) +
			grub_bfs_to_cpu_treehead(node_head.total_key_len),
			BTREE_ALIGN) / 2;
	*key_values = (grub_unaligned_uint64_t*)
		(*keylen_idx +
			grub_bfs_to_cpu_treehead(node_head.count_keys));

	return GRUB_ERR_NONE;
}

static int
iterate_in_b_tree(grub_disk_t disk,
	const struct grub_bfs_superblock* sb,
	const struct grub_bfs_inode* ino,
	int (*hook) (const char* name, grub_uint64_t value,
		struct grub_bfs_dir_ctx* ctx),
	struct grub_bfs_dir_ctx* ctx)
{
	struct grub_bfs_btree_header head;
	grub_err_t err;
	int level;
	grub_uint64_t node_off;

	err = read_bfs_file(disk, sb, ino, 0, &head, sizeof(head), 0, 0);
	if (err)
		return 0;
	node_off = grub_bfs_to_cpu64(head.root);

	level = grub_bfs_to_cpu32(head.level) - 1;
	while (level--)
	{
		struct grub_bfs_btree_node node;
		grub_uint64_t key_value;
		err = read_bfs_file(disk, sb, ino, node_off, &node, sizeof(node),
			0, 0);
		if (err)
			return 0;
		err = read_bfs_file(disk, sb, ino, node_off
			+ ALIGN_UP(sizeof(node) +
				grub_bfs_to_cpu_treehead(node.
					total_key_len),
				BTREE_ALIGN) +
			grub_bfs_to_cpu_treehead(node.count_keys) *
			sizeof(grub_uint16_t), &key_value,
			sizeof(grub_uint64_t), 0, 0);
		if (err)
			return 0;

		node_off = grub_bfs_to_cpu64(key_value);
	}

	while (1)
	{
		struct grub_bfs_btree_node* node;
		char* key_data;
		grub_uint16_t* keylen_idx;
		grub_unaligned_uint64_t* key_values;
		unsigned i;
		grub_uint16_t start = 0, end = 0;

		err = read_b_node(disk, sb, ino,
			node_off,
			&node,
			&key_data,
			&keylen_idx,
			&key_values);

		if (err)
			return 0;

		for (i = 0; i < grub_bfs_to_cpu_treehead(node->count_keys); i++)
		{
			char c;
			start = end;
			end = grub_bfs_to_cpu16(keylen_idx[i]);
			if (grub_bfs_to_cpu_treehead(node->total_key_len) <= end)
				end = grub_bfs_to_cpu_treehead(node->total_key_len);
			c = key_data[end];
			key_data[end] = 0;
			if (hook(key_data + start, grub_bfs_to_cpu64(key_values[i].val),
				ctx))
			{
				grub_free(node);
				return 1;
			}
			key_data[end] = c;
		}
		node_off = grub_bfs_to_cpu64(node->right);
		grub_free(node);
		if (node_off == POINTER_INVALID)
			return 0;
	}
}

static int
bfs_strcmp(const char* a, const char* b, grub_size_t alen)
{
	char ac, bc;
	while (*b && alen)
	{
		if (*a != *b)
			break;

		a++;
		b++;
		alen--;
	}

	ac = alen ? *a : 0;
	bc = *b;

#ifdef MODE_AFS
	return (int)(grub_int8_t)ac - (int)(grub_int8_t)bc;
#else
	return (int)(grub_uint8_t)ac - (int)(grub_uint8_t)bc;
#endif
}

static grub_err_t
find_in_b_tree(grub_disk_t disk,
	const struct grub_bfs_superblock* sb,
	const struct grub_bfs_inode* ino, const char* name,
	grub_uint64_t* res)
{
	struct grub_bfs_btree_header head;
	grub_err_t err;
	int level;
	grub_uint64_t node_off;

	err = read_bfs_file(disk, sb, ino, 0, &head, sizeof(head), 0, 0);
	if (err)
		return err;
	node_off = grub_bfs_to_cpu64(head.root);

	level = grub_bfs_to_cpu32(head.level) - 1;
	while (1)
	{
		struct grub_bfs_btree_node* node;
		char* key_data;
		grub_uint16_t* keylen_idx;
		grub_unaligned_uint64_t* key_values;
		int lg, j;
		unsigned i;

		err = read_b_node(disk, sb, ino, node_off, &node, &key_data, &keylen_idx, &key_values);
		if (err)
			return err;

		if (node->count_keys == 0)
		{
			grub_free(node);
			return grub_error(GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"),
				name);
		}

		for (lg = 0; grub_bfs_to_cpu_treehead(node->count_keys) >> lg; lg++);

		i = 0;

		for (j = lg - 1; j >= 0; j--)
		{
			int cmp;
			grub_uint16_t start = 0, end = 0;
			if ((i | (1 << j)) >= grub_bfs_to_cpu_treehead(node->count_keys))
				continue;
			start = grub_bfs_to_cpu16(keylen_idx[(i | (1 << j)) - 1]);
			end = grub_bfs_to_cpu16(keylen_idx[(i | (1 << j))]);
			if (grub_bfs_to_cpu_treehead(node->total_key_len) <= end)
				end = grub_bfs_to_cpu_treehead(node->total_key_len);
			cmp = bfs_strcmp(key_data + start, name, end - start);
			if (cmp == 0 && level == 0)
			{
				*res = grub_bfs_to_cpu64(key_values[i | (1 << j)].val);
				grub_free(node);
				return GRUB_ERR_NONE;
			}
#ifdef MODE_AFS
			if (cmp <= 0)
#else
			if (cmp < 0)
#endif
				i |= (1 << j);
		}
		if (i == 0)
		{
			grub_uint16_t end = 0;
			int cmp;
			end = grub_bfs_to_cpu16(keylen_idx[0]);
			if (grub_bfs_to_cpu_treehead(node->total_key_len) <= end)
				end = grub_bfs_to_cpu_treehead(node->total_key_len);
			cmp = bfs_strcmp(key_data, name, end);
			if (cmp == 0 && level == 0)
			{
				*res = grub_bfs_to_cpu64(key_values[0].val);
				grub_free(node);
				return GRUB_ERR_NONE;
			}
#ifdef MODE_AFS
			if (cmp > 0 && level != 0)
#else
			if (cmp >= 0 && level != 0)
#endif
			{
				node_off = grub_bfs_to_cpu64(key_values[0].val);
				level--;
				grub_free(node);
				continue;
			}
			else if (level != 0
				&& grub_bfs_to_cpu_treehead(node->count_keys) >= 2)
			{
				node_off = grub_bfs_to_cpu64(key_values[1].val);
				level--;
				grub_free(node);
				continue;
			}
		}
		else if (level != 0
			&& i + 1 < grub_bfs_to_cpu_treehead(node->count_keys))
		{
			node_off = grub_bfs_to_cpu64(key_values[i + 1].val);
			level--;
			grub_free(node);
			continue;
		}
		if (node->overflow != POINTER_INVALID)
		{
			node_off = grub_bfs_to_cpu64(node->overflow);
			/* This level-- isn't specified but is needed.  */
			level--;
			grub_free(node);
			continue;
		}
		grub_free(node);
		return grub_error(GRUB_ERR_FILE_NOT_FOUND, N_("file `%s' not found"),
			name);
	}
}

struct grub_fshelp_node
{
	grub_disk_t disk;
	const struct grub_bfs_superblock* sb;
	struct grub_bfs_inode ino;
};

static grub_err_t
lookup_file(grub_fshelp_node_t dir,
	const char* name,
	grub_fshelp_node_t* foundnode,
	enum grub_fshelp_filetype* foundtype)
{
	grub_err_t err;
	struct grub_bfs_inode* new_ino;
	grub_uint64_t res = 0;

	err = find_in_b_tree(dir->disk, dir->sb, &dir->ino, name, &res);
	if (err)
		return err;

	*foundnode = grub_malloc(sizeof(struct grub_fshelp_node));
	if (!*foundnode)
		return grub_errno;

	(*foundnode)->disk = dir->disk;
	(*foundnode)->sb = dir->sb;
	new_ino = &(*foundnode)->ino;

	if (grub_disk_read(dir->disk, res
		<< (grub_bfs_to_cpu32(dir->sb->log2_bsize)
			- GRUB_DISK_SECTOR_BITS), 0,
		sizeof(*new_ino), (char*)new_ino))
	{
		grub_free(*foundnode);
		return grub_errno;
	}
	switch (grub_bfs_to_cpu32(new_ino->mode) & ATTR_TYPE)
	{
	default:
	case ATTR_REG:
		*foundtype = GRUB_FSHELP_REG;
		break;
	case ATTR_DIR:
		*foundtype = GRUB_FSHELP_DIR;
		break;
	case ATTR_LNK:
		*foundtype = GRUB_FSHELP_SYMLINK;
		break;
	}
	return GRUB_ERR_NONE;
}

static char*
read_symlink(grub_fshelp_node_t node)
{
	char* alloc = NULL;
	grub_err_t err;

#ifndef MODE_AFS
	if (!(grub_bfs_to_cpu32(node->ino.flags) & LONG_SYMLINK))
	{
		alloc = grub_malloc(sizeof(node->ino.inplace_link) + 1);
		if (!alloc)
		{
			return NULL;
		}
		grub_memcpy(alloc, node->ino.inplace_link,
			sizeof(node->ino.inplace_link));
		alloc[sizeof(node->ino.inplace_link)] = 0;
	}
	else
#endif
	{
		grub_size_t symsize = grub_bfs_to_cpu64(node->ino.size);
		alloc = grub_malloc(symsize + 1);
		if (!alloc)
			return NULL;
		err = read_bfs_file(node->disk, node->sb, &node->ino, 0, alloc, symsize, 0, 0);
		if (err)
		{
			grub_free(alloc);
			return NULL;
		}
		alloc[symsize] = 0;
	}

	return alloc;
}

static grub_err_t
find_file(const char* path, grub_disk_t disk,
	const struct grub_bfs_superblock* sb, struct grub_bfs_inode* ino,
	enum grub_fshelp_filetype exptype)
{
	grub_err_t err;
	struct grub_fshelp_node root = {
	  .disk = disk,
	  .sb = sb,
	};
	struct grub_fshelp_node* found;

	err = read_extent(disk, sb, &sb->root_dir, 0, 0, &root.ino,
		sizeof(root.ino));
	if (err)
		return err;
	err = grub_fshelp_find_file_lookup(path, &root, &found, lookup_file, read_symlink, exptype);
	if (!err)
		grub_memcpy(ino, &found->ino, sizeof(*ino));

	if (&root != found)
		grub_free(found);
	return err;
}

static grub_err_t
mount(grub_disk_t disk, struct grub_bfs_superblock* sb)
{
	grub_err_t err;
	err = grub_disk_read(disk, SUPERBLOCK, 0, sizeof(*sb), sb);
	if (err == GRUB_ERR_OUT_OF_RANGE)
		return grub_error(GRUB_ERR_BAD_FS,
#ifdef MODE_AFS
			"not an AFS filesystem"
#else
			"not a BFS filesystem"
#endif
		);
	if (err)
		return err;
	if (sb->magic1 != grub_cpu_to_bfs32_compile_time(SUPER_BLOCK_MAGIC1)
		|| sb->magic2 != grub_cpu_to_bfs32_compile_time(SUPER_BLOCK_MAGIC2)
		|| sb->magic3 != grub_cpu_to_bfs32_compile_time(SUPER_BLOCK_MAGIC3)
		|| sb->bsize == 0
		|| (grub_bfs_to_cpu32(sb->bsize)
			!= (1U << grub_bfs_to_cpu32(sb->log2_bsize)))
		|| grub_bfs_to_cpu32(sb->log2_bsize) < GRUB_DISK_SECTOR_BITS)
		return grub_error(GRUB_ERR_BAD_FS,
#ifdef MODE_AFS
			"not an AFS filesystem"
#else
			"not a BFS filesystem"
#endif
		);
	return GRUB_ERR_NONE;
}

/* Helper for grub_bfs_dir.  */
static int
grub_bfs_dir_iter(const char* name, grub_uint64_t value,
	struct grub_bfs_dir_ctx* ctx)
{
	grub_err_t err2;
	struct grub_bfs_inode ino;
	struct grub_dirhook_info info;

	err2 = grub_disk_read(ctx->disk, value
		<< (grub_bfs_to_cpu32(ctx->sb.log2_bsize)
			- GRUB_DISK_SECTOR_BITS), 0,
		sizeof(ino), (char*)&ino);
	if (err2)
	{
		grub_print_error();
		return 0;
	}

	info.mtimeset = 1;
#ifdef MODE_AFS
	info.mtime =
		grub_divmod64(grub_bfs_to_cpu64(ino.mtime), 1000000, 0);
#else
	info.mtime = grub_bfs_to_cpu64(ino.mtime) >> 16;
#endif
	info.dir = ((grub_bfs_to_cpu32(ino.mode) & ATTR_TYPE) == ATTR_DIR);
	info.symlink = ((grub_bfs_to_cpu32(ino.mode) & ATTR_TYPE) == ATTR_LNK);
	return ctx->hook(name, &info, ctx->hook_data);
}

static grub_err_t
grub_bfs_dir(grub_disk_t disk, const char* path,
	grub_fs_dir_hook_t hook, void* hook_data)
{
	struct grub_bfs_dir_ctx ctx =
	{
	  .disk = disk,
	  .hook = hook,
	  .hook_data = hook_data
	};
	grub_err_t err;

	err = mount(disk, &ctx.sb);
	if (err)
		return err;

	{
		struct grub_bfs_inode ino;
		err = find_file(path, disk, &ctx.sb, &ino, GRUB_FSHELP_DIR);
		if (err)
			return err;
		iterate_in_b_tree(disk, &ctx.sb, &ino, grub_bfs_dir_iter,
			&ctx);
	}

	return grub_errno;
}

static grub_err_t
grub_bfs_open(struct grub_file* file, const char* name)
{
	struct grub_bfs_superblock sb;
	grub_err_t err;

	err = mount(file->disk, &sb);
	if (err)
		return err;

	{
		struct grub_bfs_inode ino;
		struct grub_bfs_data* data;
		err = find_file(name, file->disk, &sb, &ino, GRUB_FSHELP_REG);
		if (err)
			return err;

		data = grub_zalloc(sizeof(struct grub_bfs_data));
		if (!data)
			return grub_errno;
		data->sb = sb;
		grub_memcpy(&data->ino, &ino, sizeof(data->ino));
		file->data = data;
		file->size = grub_bfs_to_cpu64(ino.size);
	}

	return GRUB_ERR_NONE;
}

static grub_err_t
grub_bfs_close(grub_file_t file)
{
	grub_free(file->data);

	return GRUB_ERR_NONE;
}

static grub_ssize_t
grub_bfs_read(grub_file_t file, char* buf, grub_size_t len)
{
	grub_err_t err;
	struct grub_bfs_data* data = file->data;

	err = read_bfs_file(file->disk, &data->sb,
		&data->ino, file->offset, buf, len,
		file->read_hook, file->read_hook_data);
	if (err)
		return -1;
	return len;
}

static grub_err_t
grub_bfs_label(grub_disk_t disk, char** label)
{
	struct grub_bfs_superblock sb;
	grub_err_t err;

	*label = 0;

	err = mount(disk, &sb);
	if (err)
		return err;

	*label = grub_strndup(sb.label, sizeof(sb.label));
	return GRUB_ERR_NONE;
}

#ifndef MODE_AFS
static grub_ssize_t
read_bfs_attr(grub_disk_t disk,
	const struct grub_bfs_superblock* sb,
	struct grub_bfs_inode* ino,
	const char* name, void* buf, grub_size_t len)
{
	grub_uint8_t* ptr = (grub_uint8_t*)ino->small_data;
	grub_uint8_t* end = ((grub_uint8_t*)ino + grub_bfs_to_cpu32(sb->bsize));

	while (ptr + sizeof(struct grub_bfs_small_data_element_header) < end)
	{
		struct grub_bfs_small_data_element_header* el;
		char* el_name;
		grub_uint8_t* data;
		el = (struct grub_bfs_small_data_element_header*)ptr;
		if (el->name_len == 0)
			break;
		el_name = (char*)(el + 1);
		data = (grub_uint8_t*)el_name + grub_bfs_to_cpu16(el->name_len) + 3;
		ptr = data + grub_bfs_to_cpu16(el->value_len) + 1;
		if (grub_memcmp(name, el_name, grub_bfs_to_cpu16(el->name_len)) == 0
			&& name[el->name_len] == 0)
		{
			grub_size_t copy;
			copy = len;
			if (grub_bfs_to_cpu16(el->value_len) > copy)
				copy = grub_bfs_to_cpu16(el->value_len);
			grub_memcpy(buf, data, copy);
			return copy;
		}
	}

	if (ino->attr.len != 0)
	{
		grub_size_t read;
		grub_err_t err;
		grub_uint64_t res;

		err = read_extent(disk, sb, &ino->attr, 0, 0, ino,
			grub_bfs_to_cpu32(sb->bsize));
		if (err)
			return -1;

		err = find_in_b_tree(disk, sb, ino, name, &res);
		if (err)
			return -1;
		grub_disk_read(disk, res
			<< (grub_bfs_to_cpu32(sb->log2_bsize)
				- GRUB_DISK_SECTOR_BITS), 0,
			grub_bfs_to_cpu32(sb->bsize), (char*)ino);
		read = grub_bfs_to_cpu64(ino->size);
		if (read > len)
			read = len;

		err = read_bfs_file(disk, sb, ino, 0, buf, read, 0, 0);
		if (err)
			return -1;
		return read;
	}
	return -1;
}

static grub_err_t
grub_bfs_uuid(grub_disk_t disk, char** uuid)
{
	struct grub_bfs_superblock sb;
	grub_err_t err;
	struct grub_bfs_inode* ino;
	grub_uint64_t vid;

	*uuid = 0;

	err = mount(disk, &sb);
	if (err)
		return err;

	ino = grub_malloc(grub_bfs_to_cpu32(sb.bsize));
	if (!ino)
		return grub_errno;

	err = read_extent(disk, &sb, &sb.root_dir, 0, 0,
		ino, grub_bfs_to_cpu32(sb.bsize));
	if (err)
	{
		grub_free(ino);
		return err;
	}
	if (read_bfs_attr(disk, &sb, ino, "be:volume_id",
		&vid, sizeof(vid)) == sizeof(vid))
		*uuid =
		grub_xasprintf("%016" PRIxGRUB_UINT64_T, grub_bfs_to_cpu64(vid));

	grub_free(ino);

	return GRUB_ERR_NONE;
}
#endif

static struct grub_fs grub_bfs_fs =
{
#ifdef MODE_AFS
	.name = "afs",
#else
	.name = "bfs",
#endif
	.fs_dir = grub_bfs_dir,
	.fs_open = grub_bfs_open,
	.fs_read = grub_bfs_read,
	.fs_close = grub_bfs_close,
	.fs_label = grub_bfs_label,
#ifndef MODE_AFS
	.fs_uuid = grub_bfs_uuid,
#endif
};

#ifdef MODE_AFS
GRUB_MOD_INIT(afs)
#else
GRUB_MOD_INIT(bfs)
#endif
{
	COMPILE_TIME_ASSERT(1 << LOG_EXTENT_SIZE ==
		sizeof(struct grub_bfs_extent));
	grub_fs_register(&grub_bfs_fs);
}

#ifdef MODE_AFS
GRUB_MOD_FINI(afs)
#else
GRUB_MOD_FINI(bfs)
#endif
{
	grub_fs_unregister(&grub_bfs_fs);
}
