/* xfs.c - XFS.  */
/*
 *  GRUB  --  GRand Unified Bootloader
 *  Copyright (C) 2005,2006,2007,2008,2009  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/>.
 */

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

GRUB_MOD_LICENSE("GPLv3+");

#define	XFS_INODE_EXTENTS	9

#define XFS_INODE_FORMAT_INO	1
#define XFS_INODE_FORMAT_EXT	2
#define XFS_INODE_FORMAT_BTREE	3

/* Superblock version field flags */
#define XFS_SB_VERSION_NUMBITS		0x000f
#define	XFS_SB_VERSION_ATTRBIT		0x0010
#define	XFS_SB_VERSION_NLINKBIT		0x0020
#define	XFS_SB_VERSION_QUOTABIT		0x0040
#define	XFS_SB_VERSION_ALIGNBIT		0x0080
#define	XFS_SB_VERSION_DALIGNBIT	0x0100
#define	XFS_SB_VERSION_LOGV2BIT		0x0400
#define	XFS_SB_VERSION_SECTORBIT	0x0800
#define	XFS_SB_VERSION_EXTFLGBIT	0x1000
#define	XFS_SB_VERSION_DIRV2BIT		0x2000
#define XFS_SB_VERSION_MOREBITSBIT	0x8000
#define XFS_SB_VERSION_BITS_SUPPORTED \
	(XFS_SB_VERSION_NUMBITS | \
	 XFS_SB_VERSION_ATTRBIT | \
	 XFS_SB_VERSION_NLINKBIT | \
	 XFS_SB_VERSION_QUOTABIT | \
	 XFS_SB_VERSION_ALIGNBIT | \
	 XFS_SB_VERSION_DALIGNBIT | \
	 XFS_SB_VERSION_LOGV2BIT | \
	 XFS_SB_VERSION_SECTORBIT | \
	 XFS_SB_VERSION_EXTFLGBIT | \
	 XFS_SB_VERSION_DIRV2BIT | \
	 XFS_SB_VERSION_MOREBITSBIT)

/* Recognized xfs format versions */
#define XFS_SB_VERSION_4		4	/* Good old XFS filesystem */
#define XFS_SB_VERSION_5		5	/* CRC enabled filesystem */

/* features2 field flags */
#define XFS_SB_VERSION2_LAZYSBCOUNTBIT	0x00000002	/* Superblk counters */
#define XFS_SB_VERSION2_ATTR2BIT	0x00000008	/* Inline attr rework */
#define XFS_SB_VERSION2_PROJID32BIT	0x00000080	/* 32-bit project ids */
#define XFS_SB_VERSION2_FTYPE		0x00000200	/* inode type in dir */
#define XFS_SB_VERSION2_BITS_SUPPORTED \
	(XFS_SB_VERSION2_LAZYSBCOUNTBIT | \
	 XFS_SB_VERSION2_ATTR2BIT | \
	 XFS_SB_VERSION2_PROJID32BIT | \
	 XFS_SB_VERSION2_FTYPE)

/* Inode flags2 flags */
#define XFS_DIFLAG2_BIGTIME_BIT	3
#define XFS_DIFLAG2_BIGTIME		(1 << XFS_DIFLAG2_BIGTIME_BIT)
#define XFS_DIFLAG2_NREXT64_BIT	4
#define XFS_DIFLAG2_NREXT64		(1 << XFS_DIFLAG2_NREXT64_BIT)

/* incompat feature flags */
#define XFS_SB_FEAT_INCOMPAT_FTYPE      (1 << 0)        /* filetype in dirent */
#define XFS_SB_FEAT_INCOMPAT_SPINODES   (1 << 1)        /* sparse inode chunks */
#define XFS_SB_FEAT_INCOMPAT_META_UUID  (1 << 2)        /* metadata UUID */
#define XFS_SB_FEAT_INCOMPAT_BIGTIME    (1 << 3)        /* large timestamps */
#define XFS_SB_FEAT_INCOMPAT_NEEDSREPAIR (1 << 4)       /* needs xfs_repair */
#define XFS_SB_FEAT_INCOMPAT_NREXT64 (1 << 5)           /* large extent counters */

/*
 * Directory entries with ftype are explicitly handled by GRUB code.
 *
 * We do not currently read the inode btrees, so it is safe to read filesystems
 * with the XFS_SB_FEAT_INCOMPAT_SPINODES feature.
 *
 * We do not currently verify metadata UUID, so it is safe to read filesystems
 * with the XFS_SB_FEAT_INCOMPAT_META_UUID feature.
 */
#define XFS_SB_FEAT_INCOMPAT_SUPPORTED \
	(XFS_SB_FEAT_INCOMPAT_FTYPE | \
	 XFS_SB_FEAT_INCOMPAT_SPINODES | \
	 XFS_SB_FEAT_INCOMPAT_META_UUID | \
	 XFS_SB_FEAT_INCOMPAT_BIGTIME | \
	 XFS_SB_FEAT_INCOMPAT_NEEDSREPAIR | \
	 XFS_SB_FEAT_INCOMPAT_NREXT64)

GRUB_PACKED_START
struct grub_xfs_sblock
{
	grub_uint8_t magic[4];
	grub_uint32_t bsize;
	grub_uint8_t unused1[24];
	grub_uint16_t uuid[8];
	grub_uint8_t unused2[8];
	grub_uint64_t rootino;
	grub_uint8_t unused3[20];
	grub_uint32_t agsize;
	grub_uint8_t unused4[12];
	grub_uint16_t version;
	grub_uint8_t unused5[6];
	grub_uint8_t label[12];
	grub_uint8_t log2_bsize;
	grub_uint8_t log2_sect;
	grub_uint8_t log2_inode;
	grub_uint8_t log2_inop;
	grub_uint8_t log2_agblk;
	grub_uint8_t unused6[67];
	grub_uint8_t log2_dirblk;
	grub_uint8_t unused7[7];
	grub_uint32_t features2;
	grub_uint8_t unused8[4];
	grub_uint32_t sb_features_compat;
	grub_uint32_t sb_features_ro_compat;
	grub_uint32_t sb_features_incompat;
	grub_uint32_t sb_features_log_incompat;
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_xfs_dir_header
{
	grub_uint8_t count;
	grub_uint8_t largeino;
	union
	{
		grub_uint32_t i4;
		grub_uint64_t i8;
	} parent;
};
GRUB_PACKED_END

/* Structure for directory entry inlined in the inode */
GRUB_PACKED_START
struct grub_xfs_dir_entry
{
	grub_uint8_t len;
	grub_uint16_t offset;
	char name[1];
	/* Inode number follows, 32 / 64 bits.  */
};
GRUB_PACKED_END

/* Structure for directory entry in a block */
GRUB_PACKED_START
struct grub_xfs_dir2_entry
{
	grub_uint64_t inode;
	grub_uint8_t len;
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_xfs_extent
{
	/* This should be a bitfield but bietfields are unportable, so just have
	   a raw array and functions extracting useful info from it.
	 */
	grub_uint32_t raw[4];
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_xfs_btree_node
{
	grub_uint8_t magic[4];
	grub_uint16_t level;
	grub_uint16_t numrecs;
	grub_uint64_t left;
	grub_uint64_t right;
	/* In V5 here follow crc, uuid, etc. */
	/* Then follow keys and block pointers */
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_xfs_btree_root
{
	grub_uint16_t level;
	grub_uint16_t numrecs;
	grub_uint64_t keys[1];
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_xfs_time_legacy
{
	grub_uint32_t sec;
	grub_uint32_t nanosec;
};
GRUB_PACKED_END

/*
 * The struct grub_xfs_inode layout was taken from the
 * struct xfs_dinode_core which is described here:
 * https://mirrors.edge.kernel.org/pub/linux/utils/fs/xfs/docs/xfs_filesystem_structure.pdf
 */
GRUB_PACKED_START
struct grub_xfs_inode
{
	grub_uint8_t magic[2];
	grub_uint16_t mode;
	grub_uint8_t version;
	grub_uint8_t format;
	grub_uint8_t unused2[18];
	grub_uint64_t nextents_big;
	grub_uint64_t atime;
	grub_uint64_t mtime;
	grub_uint64_t ctime;
	grub_uint64_t size;
	grub_uint64_t nblocks;
	grub_uint32_t extsize;
	grub_uint32_t nextents;
	grub_uint16_t unused3;
	grub_uint8_t fork_offset;
	grub_uint8_t unused4[17]; /* Last member of inode v2. */
	grub_uint8_t unused5[20]; /* First member of inode v3. */
	grub_uint64_t flags2;
	grub_uint8_t unused6[48]; /* Last member of inode v3. */
};
GRUB_PACKED_END

#define XFS_V3_INODE_SIZE	sizeof(struct grub_xfs_inode)
/* Size of struct grub_xfs_inode v2, up to unused4 member included. */
#define XFS_V2_INODE_SIZE	(XFS_V3_INODE_SIZE - 76)

GRUB_PACKED_START
struct grub_xfs_dir_leaf_entry
{
	grub_uint32_t hashval;
	grub_uint32_t address;
};
GRUB_PACKED_END

GRUB_PACKED_START
struct grub_xfs_dirblock_tail
{
	grub_uint32_t leaf_count;
	grub_uint32_t leaf_stale;
};
GRUB_PACKED_END

struct grub_fshelp_node
{
	struct grub_xfs_data* data;
	grub_uint64_t ino;
	int inode_read;
	struct grub_xfs_inode inode;
};

struct grub_xfs_data
{
	grub_size_t data_size;
	struct grub_xfs_sblock sblock;
	grub_disk_t disk;
	int pos;
	int bsize;
	grub_uint32_t agsize;
	unsigned int hasftype : 1;
	unsigned int hascrc : 1;
	struct grub_fshelp_node diropen;
};

static int grub_xfs_sb_hascrc(struct grub_xfs_data* data)
{
	return (data->sblock.version & grub_cpu_to_be16_compile_time(XFS_SB_VERSION_NUMBITS)) ==
		grub_cpu_to_be16_compile_time(XFS_SB_VERSION_5);
}

static int grub_xfs_sb_hasftype(struct grub_xfs_data* data)
{
	if ((data->sblock.version & grub_cpu_to_be16_compile_time(XFS_SB_VERSION_NUMBITS)) ==
		grub_cpu_to_be16_compile_time(XFS_SB_VERSION_5) &&
		data->sblock.sb_features_incompat & grub_cpu_to_be32_compile_time(XFS_SB_FEAT_INCOMPAT_FTYPE))
		return 1;
	if (data->sblock.version & grub_cpu_to_be16_compile_time(XFS_SB_VERSION_MOREBITSBIT) &&
		data->sblock.features2 & grub_cpu_to_be32_compile_time(XFS_SB_VERSION2_FTYPE))
		return 1;
	return 0;
}

static int grub_xfs_sb_valid(struct grub_xfs_data* data)
{
	grub_dprintf("xfs", "Validating superblock\n");
	if (grub_strncmp((char*)(data->sblock.magic), "XFSB", 4)
		|| data->sblock.log2_bsize < GRUB_DISK_SECTOR_BITS
		|| ((int)data->sblock.log2_bsize
			+ (int)data->sblock.log2_dirblk) >= 27)
	{
		grub_error(GRUB_ERR_BAD_FS, "not a XFS filesystem");
		return 0;
	}
	if ((data->sblock.version & grub_cpu_to_be16_compile_time(XFS_SB_VERSION_NUMBITS)) ==
		grub_cpu_to_be16_compile_time(XFS_SB_VERSION_5))
	{
		grub_dprintf("xfs", "XFS v5 superblock detected\n");
		if (data->sblock.sb_features_incompat &
			grub_cpu_to_be32_compile_time(~XFS_SB_FEAT_INCOMPAT_SUPPORTED))
		{
			grub_error(GRUB_ERR_BAD_FS, "XFS filesystem has unsupported "
				"incompatible features");
			return 0;
		}
		return 1;
	}
	else if ((data->sblock.version & grub_cpu_to_be16_compile_time(XFS_SB_VERSION_NUMBITS)) ==
		grub_cpu_to_be16_compile_time(XFS_SB_VERSION_4))
	{
		grub_dprintf("xfs", "XFS v4 superblock detected\n");
		if (!(data->sblock.version & grub_cpu_to_be16_compile_time(XFS_SB_VERSION_DIRV2BIT)))
		{
			grub_error(GRUB_ERR_BAD_FS, "XFS filesystem without V2 directories "
				"is unsupported");
			return 0;
		}
		if (data->sblock.version & grub_cpu_to_be16_compile_time(~XFS_SB_VERSION_BITS_SUPPORTED) ||
			(data->sblock.version & grub_cpu_to_be16_compile_time(XFS_SB_VERSION_MOREBITSBIT) &&
				data->sblock.features2 & grub_cpu_to_be16_compile_time(~XFS_SB_VERSION2_BITS_SUPPORTED)))
		{
			grub_error(GRUB_ERR_BAD_FS, "XFS filesystem has unsupported version "
				"bits");
			return 0;
		}
		return 1;
	}
	return 0;
}

static int
grub_xfs_sb_needs_repair(struct grub_xfs_data* data)
{
	return ((data->sblock.version &
		grub_cpu_to_be16_compile_time(XFS_SB_VERSION_NUMBITS)) ==
		grub_cpu_to_be16_compile_time(XFS_SB_VERSION_5) &&
		(data->sblock.sb_features_incompat &
			grub_cpu_to_be32_compile_time(XFS_SB_FEAT_INCOMPAT_NEEDSREPAIR)));
}

/* Filetype information as used in inodes.  */
#define FILETYPE_INO_MASK	0170000
#define FILETYPE_INO_REG	0100000
#define FILETYPE_INO_DIRECTORY	0040000
#define FILETYPE_INO_SYMLINK	0120000

static inline int
GRUB_XFS_INO_AGBITS(struct grub_xfs_data* data)
{
	return ((data)->sblock.log2_agblk + (data)->sblock.log2_inop);
}

static inline grub_uint64_t
GRUB_XFS_INO_INOINAG(struct grub_xfs_data* data,
	grub_uint64_t ino)
{
	return (ino & ((1LL << GRUB_XFS_INO_AGBITS(data)) - 1));
}

static inline grub_uint64_t
GRUB_XFS_INO_AG(struct grub_xfs_data* data,
	grub_uint64_t ino)
{
	return (ino >> GRUB_XFS_INO_AGBITS(data));
}

static inline grub_disk_addr_t
GRUB_XFS_FSB_TO_BLOCK(struct grub_xfs_data* data, grub_disk_addr_t fsb)
{
	return ((fsb >> data->sblock.log2_agblk) * data->agsize
		+ (fsb & ((1LL << data->sblock.log2_agblk) - 1)));
}

static inline grub_uint64_t
GRUB_XFS_EXTENT_OFFSET(struct grub_xfs_extent* exts, int ex)
{
	return ((grub_be_to_cpu32(exts[ex].raw[0]) & ~(1 << 31)) << 23
		| grub_be_to_cpu32(exts[ex].raw[1]) >> 9);
}

static inline grub_uint64_t
GRUB_XFS_EXTENT_BLOCK(struct grub_xfs_extent* exts, int ex)
{
	return ((grub_uint64_t)(grub_be_to_cpu32(exts[ex].raw[1])
		& (0x1ff)) << 43
		| (grub_uint64_t)grub_be_to_cpu32(exts[ex].raw[2]) << 11
		| grub_be_to_cpu32(exts[ex].raw[3]) >> 21);
}

static inline grub_uint64_t
GRUB_XFS_EXTENT_SIZE(struct grub_xfs_extent* exts, int ex)
{
	return (grub_be_to_cpu32(exts[ex].raw[3]) & ((1 << 21) - 1));
}


static inline grub_uint64_t
grub_xfs_inode_block(struct grub_xfs_data* data,
	grub_uint64_t ino)
{
	long long int inoinag = GRUB_XFS_INO_INOINAG(data, ino);
	long long ag = GRUB_XFS_INO_AG(data, ino);
	long long block;

	block = (inoinag >> data->sblock.log2_inop) + ag * data->agsize;
	block <<= (data->sblock.log2_bsize - GRUB_DISK_SECTOR_BITS);
	return block;
}


static inline int
grub_xfs_inode_offset(struct grub_xfs_data* data,
	grub_uint64_t ino)
{
	int inoag = GRUB_XFS_INO_INOINAG(data, ino);
	return ((inoag & ((1 << data->sblock.log2_inop) - 1)) <<
		data->sblock.log2_inode);
}

static inline grub_size_t
grub_xfs_inode_size(struct grub_xfs_data* data)
{
	return (grub_size_t)1 << data->sblock.log2_inode;
}

/*
 * Returns size occupied by XFS inode stored in memory - we store struct
 * grub_fshelp_node there but on disk inode size may be actually larger than
 * struct grub_xfs_inode so we need to account for that so that we can read
 * from disk directly into in-memory structure.
 */
static inline grub_size_t
grub_xfs_fshelp_size(struct grub_xfs_data* data)
{
	return sizeof(struct grub_fshelp_node) - sizeof(struct grub_xfs_inode)
		+ grub_xfs_inode_size(data);
}

/* This should return void * but XFS code is error-prone with alignment, so
   return char to retain cast-align.
 */
static char*
grub_xfs_inode_data(struct grub_xfs_inode* inode)
{
	if (inode->version <= 2)
		return ((char*)inode) + XFS_V2_INODE_SIZE;
	return ((char*)inode) + XFS_V3_INODE_SIZE;
}

static struct grub_xfs_dir_entry*
grub_xfs_inline_de(struct grub_xfs_dir_header* head)
{
	/*
	  With small inode numbers the header is 4 bytes smaller because of
	  smaller parent pointer
	*/
	return (struct grub_xfs_dir_entry*)
		(((char*)head) + sizeof(struct grub_xfs_dir_header) -
			(head->largeino ? 0 : sizeof(grub_uint32_t)));
}

static grub_uint8_t*
grub_xfs_inline_de_inopos(struct grub_xfs_data* data,
	struct grub_xfs_dir_entry* de)
{
	return ((grub_uint8_t*)(de + 1)) + de->len - 1 + (data->hasftype ? 1 : 0);
}

static struct grub_xfs_dir_entry*
grub_xfs_inline_next_de(struct grub_xfs_data* data,
	struct grub_xfs_dir_header* head,
	struct grub_xfs_dir_entry* de)
{
	char* p = (char*)de + sizeof(struct grub_xfs_dir_entry) - 1 + de->len;

	p += head->largeino ? sizeof(grub_uint64_t) : sizeof(grub_uint32_t);
	if (data->hasftype)
		p++;

	return (struct grub_xfs_dir_entry*)p;
}

static struct grub_xfs_dirblock_tail*
grub_xfs_dir_tail(struct grub_xfs_data* data, void* dirblock)
{
	int dirblksize = 1 << (data->sblock.log2_bsize + data->sblock.log2_dirblk);

	return (struct grub_xfs_dirblock_tail*)
		((char*)dirblock + dirblksize - sizeof(struct grub_xfs_dirblock_tail));
}

static struct grub_xfs_dir2_entry*
grub_xfs_first_de(struct grub_xfs_data* data, void* dirblock)
{
	if (data->hascrc)
		return (struct grub_xfs_dir2_entry*)((char*)dirblock + 64);
	return (struct grub_xfs_dir2_entry*)((char*)dirblock + 16);
}

static struct grub_xfs_dir2_entry*
grub_xfs_next_de(struct grub_xfs_data* data, struct grub_xfs_dir2_entry* de)
{
	int size = sizeof(struct grub_xfs_dir2_entry) + de->len + 2 /* Tag */;

	if (data->hasftype)
		size++;		/* File type */
	return (struct grub_xfs_dir2_entry*)(((char*)de) + ALIGN_UP(size, 8));
}

/* This should return void * but XFS code is error-prone with alignment, so
   return char to retain cast-align.
 */
static char*
grub_xfs_btree_keys(struct grub_xfs_data* data,
	struct grub_xfs_btree_node* leaf)
{
	char* keys = (char*)(leaf + 1);

	if (data->hascrc)
		keys += 48;	/* skip crc, uuid, ... */
	return keys;
}

static grub_err_t
grub_xfs_read_inode(struct grub_xfs_data* data, grub_uint64_t ino,
	struct grub_xfs_inode* inode)
{
	grub_uint64_t block = grub_xfs_inode_block(data, ino);
	int offset = grub_xfs_inode_offset(data, ino);

	grub_dprintf("xfs", "Reading inode (%" PRIuGRUB_UINT64_T ") - %" PRIuGRUB_UINT64_T ", %d\n",
		ino, block, offset);
	/* Read the inode.  */
	if (grub_disk_read(data->disk, block, offset, grub_xfs_inode_size(data),
		inode))
		return grub_errno;

	if (grub_strncmp((char*)inode->magic, "IN", 2))
		return grub_error(GRUB_ERR_BAD_FS, "not a correct XFS inode");

	return 0;
}

static grub_uint64_t
get_fsb(const void* keys, int idx)
{
	const char* p = (const char*)keys + sizeof(grub_uint64_t) * idx;
	return grub_be_to_cpu64(grub_get_unaligned64(p));
}

static int
grub_xfs_inode_has_large_extent_counts(const struct grub_xfs_inode* inode)
{
	return inode->version >= 3 &&
		(inode->flags2 & grub_cpu_to_be64_compile_time(XFS_DIFLAG2_NREXT64));
}

static grub_uint64_t
grub_xfs_get_inode_nextents(struct grub_xfs_inode* inode)
{
	return (grub_xfs_inode_has_large_extent_counts(inode)) ?
		grub_be_to_cpu64(inode->nextents_big) :
		grub_be_to_cpu32(inode->nextents);
}

static grub_disk_addr_t
grub_xfs_read_block(grub_fshelp_node_t node, grub_disk_addr_t fileblock)
{
	struct grub_xfs_btree_node* leaf = 0;
	grub_uint64_t ex, nrec;
	struct grub_xfs_extent* exts;
	grub_uint64_t ret = 0;

	if (node->inode.format == XFS_INODE_FORMAT_BTREE)
	{
		struct grub_xfs_btree_root* root;
		const char* keys;
		int recoffset;

		leaf = grub_malloc(node->data->bsize);
		if (leaf == 0)
			return 0;

		root = (struct grub_xfs_btree_root*)grub_xfs_inode_data(&node->inode);
		nrec = grub_be_to_cpu16(root->numrecs);
		keys = (char*)&root->keys[0];
		if (node->inode.fork_offset)
			recoffset = (node->inode.fork_offset - 1) / 2;
		else
			recoffset = (grub_xfs_inode_size(node->data)
				- ((char*)keys - (char*)&node->inode))
			/ (2 * sizeof(grub_uint64_t));
		do
		{
			grub_uint64_t i;

			for (i = 0; i < nrec; i++)
			{
				if (fileblock < get_fsb(keys, i))
					break;
			}

			/* Sparse block.  */
			if (i == 0)
			{
				grub_free(leaf);
				return 0;
			}

			if (grub_disk_read(node->data->disk,
				GRUB_XFS_FSB_TO_BLOCK(node->data, get_fsb(keys, i - 1 + recoffset)) << (node->data->sblock.log2_bsize - GRUB_DISK_SECTOR_BITS),
				0, node->data->bsize, leaf))
			{
				grub_free(leaf);
				return 0;
			}

			if ((!node->data->hascrc &&
				grub_strncmp((char*)leaf->magic, "BMAP", 4)) ||
				(node->data->hascrc &&
					grub_strncmp((char*)leaf->magic, "BMA3", 4)))
			{
				grub_free(leaf);
				grub_error(GRUB_ERR_BAD_FS, "not a correct XFS BMAP node");
				return 0;
			}

			nrec = grub_be_to_cpu16(leaf->numrecs);
			keys = grub_xfs_btree_keys(node->data, leaf);
			recoffset = ((node->data->bsize - ((char*)keys
				- (char*)leaf))
				/ (2 * sizeof(grub_uint64_t)));
		} while (leaf->level);
		exts = (struct grub_xfs_extent*)keys;
	}
	else if (node->inode.format == XFS_INODE_FORMAT_EXT)
	{
		grub_addr_t exts_end = 0;
		grub_addr_t data_end = 0;

		nrec = grub_xfs_get_inode_nextents(&node->inode);
		exts = (struct grub_xfs_extent*)grub_xfs_inode_data(&node->inode);

		if (grub_mul(sizeof(struct grub_xfs_extent), nrec, &exts_end) ||
			grub_add((grub_addr_t)node->data, exts_end, &exts_end) ||
			grub_add((grub_addr_t)node->data, node->data->data_size, &data_end) ||
			exts_end > data_end)
		{
			grub_error(GRUB_ERR_BAD_FS, "invalid number of XFS extents");
			return 0;
		}
	}
	else
	{
		grub_error(GRUB_ERR_NOT_IMPLEMENTED_YET,
			"XFS does not support inode format %d yet",
			node->inode.format);
		return 0;
	}

	/* Iterate over each extent to figure out which extent has
	   the block we are looking for.  */
	for (ex = 0; ex < nrec; ex++)
	{
		grub_uint64_t start = GRUB_XFS_EXTENT_BLOCK(exts, ex);
		grub_uint64_t offset = GRUB_XFS_EXTENT_OFFSET(exts, ex);
		grub_uint64_t size = GRUB_XFS_EXTENT_SIZE(exts, ex);

		/* Sparse block.  */
		if (fileblock < offset)
			break;
		else if (fileblock < offset + size)
		{
			ret = (fileblock - offset + start);
			break;
		}
	}

	grub_free(leaf);

	return GRUB_XFS_FSB_TO_BLOCK(node->data, ret);
}


/* Read LEN bytes from the file described by DATA starting with byte
   POS.  Return the amount of read bytes in READ.  */
static grub_ssize_t
grub_xfs_read_file(grub_fshelp_node_t node,
	grub_disk_read_hook_t read_hook, void* read_hook_data,
	grub_off_t pos, grub_size_t len, char* buf, grub_uint32_t header_size)
{
	return grub_fshelp_read_file(node->data->disk, node,
		read_hook, read_hook_data,
		pos, len, buf, grub_xfs_read_block,
		grub_be_to_cpu64(node->inode.size) + header_size,
		node->data->sblock.log2_bsize
		- GRUB_DISK_SECTOR_BITS, 0);
}


static char*
grub_xfs_read_symlink(grub_fshelp_node_t node)
{
	grub_ssize_t size = grub_be_to_cpu64(node->inode.size);

	if (size < 0)
	{
		grub_error(GRUB_ERR_BAD_FS, "invalid symlink");
		return 0;
	}

	switch (node->inode.format)
	{
	case XFS_INODE_FORMAT_INO:
		return grub_strndup(grub_xfs_inode_data(&node->inode), size);

	case XFS_INODE_FORMAT_EXT:
	{
		char* symlink;
		grub_ssize_t numread;
		int off = 0;

		if (node->data->hascrc)
			off = 56;

		symlink = grub_malloc(size + 1);
		if (!symlink)
			return 0;

		node->inode.size = grub_be_to_cpu64(size + off);
		numread = grub_xfs_read_file(node, 0, 0, off, size, symlink, off);
		if (numread != size)
		{
			grub_free(symlink);
			return 0;
		}
		symlink[size] = '\0';
		return symlink;
	}
	}

	return 0;
}


static enum grub_fshelp_filetype
grub_xfs_mode_to_filetype(grub_uint16_t mode)
{
	if ((grub_be_to_cpu16(mode)
		& FILETYPE_INO_MASK) == FILETYPE_INO_DIRECTORY)
		return GRUB_FSHELP_DIR;
	else if ((grub_be_to_cpu16(mode)
		& FILETYPE_INO_MASK) == FILETYPE_INO_SYMLINK)
		return GRUB_FSHELP_SYMLINK;
	else if ((grub_be_to_cpu16(mode)
		& FILETYPE_INO_MASK) == FILETYPE_INO_REG)
		return GRUB_FSHELP_REG;
	return GRUB_FSHELP_UNKNOWN;
}


/* Context for grub_xfs_iterate_dir.  */
struct grub_xfs_iterate_dir_ctx
{
	grub_fshelp_iterate_dir_hook_t hook;
	void* hook_data;
	struct grub_fshelp_node* diro;
};

/* Helper for grub_xfs_iterate_dir.  */
static int iterate_dir_call_hook(grub_uint64_t ino, const char* filename,
	struct grub_xfs_iterate_dir_ctx* ctx)
{
	struct grub_fshelp_node* fdiro;
	grub_err_t err;

	fdiro = grub_malloc(grub_xfs_fshelp_size(ctx->diro->data) + 1);
	if (!fdiro)
	{
		grub_print_error();
		return 0;
	}

	/* The inode should be read, otherwise the filetype can
	   not be determined.  */
	fdiro->ino = ino;
	fdiro->inode_read = 1;
	fdiro->data = ctx->diro->data;
	err = grub_xfs_read_inode(ctx->diro->data, ino, &fdiro->inode);
	if (err)
	{
		grub_print_error();
		grub_free(fdiro);
		return 0;
	}

	return ctx->hook(filename, grub_xfs_mode_to_filetype(fdiro->inode.mode),
		fdiro, ctx->hook_data);
}

static int
grub_xfs_iterate_dir(grub_fshelp_node_t dir,
	grub_fshelp_iterate_dir_hook_t hook, void* hook_data)
{
	struct grub_fshelp_node* diro = (struct grub_fshelp_node*)dir;
	struct grub_xfs_iterate_dir_ctx ctx = {
	  .hook = hook,
	  .hook_data = hook_data,
	  .diro = diro
	};

	switch (diro->inode.format)
	{
	case XFS_INODE_FORMAT_INO:
	{
		struct grub_xfs_dir_header* head = (struct grub_xfs_dir_header*)grub_xfs_inode_data(&diro->inode);
		struct grub_xfs_dir_entry* de = grub_xfs_inline_de(head);
		int smallino = !head->largeino;
		int i;
		grub_uint64_t parent;

		/* If small inode numbers are used to pack the direntry, the
		   parent inode number is small too.  */
		if (smallino)
			parent = grub_be_to_cpu32(head->parent.i4);
		else
			parent = grub_be_to_cpu64(head->parent.i8);

		/* Synthesize the direntries for `.' and `..'.  */
		if (iterate_dir_call_hook(diro->ino, ".", &ctx))
			return 1;

		if (iterate_dir_call_hook(parent, "..", &ctx))
			return 1;

		for (i = 0; i < head->count &&
			(grub_uint8_t*)de < ((grub_uint8_t*)dir + grub_xfs_fshelp_size(dir->data)); i++)
		{
			grub_uint64_t ino;
			grub_uint8_t* inopos = grub_xfs_inline_de_inopos(dir->data, de);
			grub_uint8_t c;

			if ((inopos + (smallino ? 4 : 8)) > (grub_uint8_t*) dir + grub_xfs_fshelp_size(dir->data))
				return grub_error(GRUB_ERR_BAD_FS, "not a correct XFS inode");

			/* inopos might be unaligned.  */
			if (smallino)
				ino = (((grub_uint32_t)inopos[0]) << 24)
				| (((grub_uint32_t)inopos[1]) << 16)
				| (((grub_uint32_t)inopos[2]) << 8)
				| (((grub_uint32_t)inopos[3]) << 0);
			else
				ino = (((grub_uint64_t)inopos[0]) << 56)
				| (((grub_uint64_t)inopos[1]) << 48)
				| (((grub_uint64_t)inopos[2]) << 40)
				| (((grub_uint64_t)inopos[3]) << 32)
				| (((grub_uint64_t)inopos[4]) << 24)
				| (((grub_uint64_t)inopos[5]) << 16)
				| (((grub_uint64_t)inopos[6]) << 8)
				| (((grub_uint64_t)inopos[7]) << 0);

			c = de->name[de->len];
			de->name[de->len] = '\0';
			if (iterate_dir_call_hook(ino, de->name, &ctx))
			{
				de->name[de->len] = c;
				return 1;
			}
			de->name[de->len] = c;

			de = grub_xfs_inline_next_de(dir->data, head, de);
		}
		break;
	}

	case XFS_INODE_FORMAT_BTREE:
	case XFS_INODE_FORMAT_EXT:
	{
		grub_ssize_t numread;
		char* dirblock;
		grub_uint64_t blk;
		int dirblk_size, dirblk_log2;

		dirblk_log2 = (dir->data->sblock.log2_bsize
			+ dir->data->sblock.log2_dirblk);
		dirblk_size = 1 << dirblk_log2;

		dirblock = grub_malloc(dirblk_size);
		if (!dirblock)
			return 0;

		/* Iterate over every block the directory has.  */
		for (blk = 0;
			blk < (grub_be_to_cpu64(dir->inode.size)
				>> dirblk_log2);
			blk++)
		{
			struct grub_xfs_dir2_entry* direntry =
				grub_xfs_first_de(dir->data, dirblock);
			int entries = -1;
			char* end = dirblock + dirblk_size;
			grub_uint32_t magic;

			numread = grub_xfs_read_file(dir, 0, 0,
				blk << dirblk_log2,
				dirblk_size, dirblock, 0);
			if (numread != dirblk_size)
			{
				grub_free(dirblock);
				return 0;
			}

			/*
			 * If this data block isn't actually part of the extent list then
			 * grub_xfs_read_file() returns a block of zeros. So, if the magic
			 * number field is all zeros then this block should be skipped.
			 */
			magic = *(grub_uint32_t*)(void*)dirblock;
			if (!magic)
				continue;

			/*
			 * Leaf and tail information are only in the data block if the number
			 * of extents is 1.
			 */
			if (dir->inode.nextents == grub_cpu_to_be32_compile_time(1))
			{
				struct grub_xfs_dirblock_tail* tail = grub_xfs_dir_tail(dir->data, dirblock);

				end = (char*)tail;

				/* Subtract the space used by leaf nodes. */
				end -= grub_be_to_cpu32(tail->leaf_count) * sizeof(struct grub_xfs_dir_leaf_entry);

				entries = grub_be_to_cpu32(tail->leaf_count) - grub_be_to_cpu32(tail->leaf_stale);

				if (!entries)
					continue;
			}

			/* Iterate over all entries within this block.  */
			while ((char*)direntry < (char*)end)
			{
				grub_uint8_t* freetag;
				char* filename;

				freetag = (grub_uint8_t*)direntry;

				if (grub_get_unaligned16(freetag) == 0XFFFF)
				{
					grub_uint8_t* skip = (freetag + sizeof(grub_uint16_t));

					/* This entry is not used, go to the next one.  */
					direntry = (struct grub_xfs_dir2_entry*)
						(((char*)direntry) +
							grub_be_to_cpu16(grub_get_unaligned16(skip)));

					continue;
				}

				filename = (char*)(direntry + 1);
				if (filename + direntry->len + 1 > (char*)end)
					return grub_error(GRUB_ERR_BAD_FS, "invalid XFS directory entry");

				/* The byte after the filename is for the filetype, padding, or
				   tag, which is not used by GRUB.  So it can be overwritten. */
				filename[direntry->len] = '\0';

				if (iterate_dir_call_hook(grub_be_to_cpu64(direntry->inode),
					filename, &ctx))
				{
					grub_free(dirblock);
					return 1;
				}

				/*
				 * The expected number of directory entries is only tracked for the
				 * single extent case.
				 */
				if (dir->inode.nextents == grub_cpu_to_be32_compile_time(1))
				{
					/* Check if last direntry in this block is reached. */
					entries--;
					if (!entries)
						break;
				}

				/* Select the next directory entry.  */
				direntry = grub_xfs_next_de(dir->data, direntry);
			}
		}
		grub_free(dirblock);
		break;
	}

	default:
		grub_error(GRUB_ERR_NOT_IMPLEMENTED_YET,
			"XFS does not support inode format %d yet",
			diro->inode.format);
	}
	return 0;
}


static struct grub_xfs_data*
grub_xfs_mount(grub_disk_t disk)
{
	struct grub_xfs_data* data = 0;
	grub_size_t sz;

	data = grub_zalloc(sizeof(struct grub_xfs_data));
	if (!data)
		return 0;

	data->data_size = sizeof(struct grub_xfs_data);

	grub_dprintf("xfs", "Reading sb\n");
	/* Read the superblock.  */
	if (grub_disk_read(disk, 0, 0,
		sizeof(struct grub_xfs_sblock), &data->sblock))
		goto fail;

	if (!grub_xfs_sb_valid(data))
		goto fail;

	if (grub_xfs_sb_needs_repair(data))
		grub_dprintf("xfs", "XFS filesystem needs repair, boot may fail\n");

	if (grub_add(grub_xfs_inode_size(data),
		sizeof(struct grub_xfs_data) - sizeof(struct grub_xfs_inode) + 1, &sz))
		goto fail;

	data = grub_realloc(data, sz);

	if (!data)
		goto fail;

	data->data_size = sz;
	data->diropen.data = data;
	data->diropen.ino = grub_be_to_cpu64(data->sblock.rootino);
	data->diropen.inode_read = 1;
	data->bsize = grub_be_to_cpu32(data->sblock.bsize);
	data->agsize = grub_be_to_cpu32(data->sblock.agsize);
	data->hasftype = grub_xfs_sb_hasftype(data);
	data->hascrc = grub_xfs_sb_hascrc(data);

	data->disk = disk;
	data->pos = 0;
	grub_dprintf("xfs", "Reading root ino %" PRIuGRUB_UINT64_T "\n",
		grub_cpu_to_be64(data->sblock.rootino));

	grub_xfs_read_inode(data, data->diropen.ino, &data->diropen.inode);

	return data;
fail:

	if (grub_errno == GRUB_ERR_OUT_OF_RANGE)
		grub_error(GRUB_ERR_BAD_FS, "not an XFS filesystem");

	grub_free(data);

	return 0;
}


/* Context for grub_xfs_dir.  */
struct grub_xfs_dir_ctx
{
	grub_fs_dir_hook_t hook;
	void* hook_data;
};

/* Bigtime inodes helpers. */
#define XFS_BIGTIME_EPOCH_OFFSET	(-(grub_int64_t) GRUB_INT32_MIN)

static int grub_xfs_inode_has_bigtime(const struct grub_xfs_inode* inode)
{
	return inode->version >= 3 &&
		(inode->flags2 & grub_cpu_to_be64_compile_time(XFS_DIFLAG2_BIGTIME));
}

static grub_int64_t
grub_xfs_get_inode_time(struct grub_xfs_inode* inode)
{
	struct grub_xfs_time_legacy* lts;

	if (grub_xfs_inode_has_bigtime(inode))
		return grub_divmod64(grub_be_to_cpu64(inode->mtime), NSEC_PER_SEC, NULL) - XFS_BIGTIME_EPOCH_OFFSET;

	lts = (struct grub_xfs_time_legacy*)&inode->mtime;
	return grub_be_to_cpu32(lts->sec);
}

/* Helper for grub_xfs_dir.  */
static int
grub_xfs_dir_iter(const char* filename, enum grub_fshelp_filetype filetype,
	grub_fshelp_node_t node, void* data)
{
	struct grub_xfs_dir_ctx* ctx = data;
	struct grub_dirhook_info info;

	grub_memset(&info, 0, sizeof(info));
	if (node->inode_read)
	{
		info.mtimeset = 1;
		info.mtime = grub_xfs_get_inode_time(&node->inode);
	}
	info.dir = ((filetype & GRUB_FSHELP_TYPE_MASK) == GRUB_FSHELP_DIR);
	info.symlink = ((filetype & GRUB_FSHELP_TYPE_MASK) == GRUB_FSHELP_SYMLINK);
	grub_free(node);
	return ctx->hook(filename, &info, ctx->hook_data);
}

static grub_err_t
grub_xfs_dir(grub_disk_t disk, const char* path,
	grub_fs_dir_hook_t hook, void* hook_data)
{
	struct grub_xfs_dir_ctx ctx = { hook, hook_data };
	struct grub_xfs_data* data = 0;
	struct grub_fshelp_node* fdiro = 0;

	data = grub_xfs_mount(disk);
	if (!data)
		goto mount_fail;

	grub_fshelp_find_file(path, &data->diropen, &fdiro, grub_xfs_iterate_dir,
		grub_xfs_read_symlink, GRUB_FSHELP_DIR);
	if (grub_errno)
		goto fail;

	grub_xfs_iterate_dir(fdiro, grub_xfs_dir_iter, &ctx);

fail:
	if (fdiro != &data->diropen)
		grub_free(fdiro);
	grub_free(data);

mount_fail:
	return grub_errno;
}


/* Open a file named NAME and initialize FILE.  */
static grub_err_t
grub_xfs_open(struct grub_file* file, const char* name)
{
	struct grub_xfs_data* data;
	struct grub_fshelp_node* fdiro = 0;

	data = grub_xfs_mount(file->disk);
	if (!data)
		goto mount_fail;

	grub_fshelp_find_file(name, &data->diropen, &fdiro, grub_xfs_iterate_dir,
		grub_xfs_read_symlink, GRUB_FSHELP_REG);
	if (grub_errno)
		goto fail;

	if (!fdiro->inode_read)
	{
		grub_xfs_read_inode(data, fdiro->ino, &fdiro->inode);
		if (grub_errno)
			goto fail;
	}

	if (fdiro != &data->diropen)
	{
		grub_memcpy(&data->diropen, fdiro, grub_xfs_fshelp_size(data));
		grub_free(fdiro);
	}

	file->size = grub_be_to_cpu64(data->diropen.inode.size);
	file->data = data;
	file->offset = 0;

	return 0;

fail:
	if (fdiro != &data->diropen)
		grub_free(fdiro);
	grub_free(data);

mount_fail:
	return grub_errno;
}


static grub_ssize_t
grub_xfs_read(grub_file_t file, char* buf, grub_size_t len)
{
	struct grub_xfs_data* data =
		(struct grub_xfs_data*)file->data;

	return grub_xfs_read_file(&data->diropen,
		file->read_hook, file->read_hook_data,
		file->offset, len, buf, 0);
}


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

	return GRUB_ERR_NONE;
}


static grub_err_t
grub_xfs_label(grub_disk_t disk, char** label)
{
	struct grub_xfs_data* data;

	data = grub_xfs_mount(disk);
	if (data)
		*label = grub_strndup((char*)(data->sblock.label), 12);
	else
		*label = 0;

	grub_free(data);

	return grub_errno;
}

static grub_err_t
grub_xfs_uuid(grub_disk_t disk, char** uuid)
{
	struct grub_xfs_data* data;

	data = grub_xfs_mount(disk);
	if (data)
	{
		*uuid = grub_xasprintf("%04x%04x-%04x-%04x-%04x-%04x%04x%04x",
			grub_be_to_cpu16(data->sblock.uuid[0]),
			grub_be_to_cpu16(data->sblock.uuid[1]),
			grub_be_to_cpu16(data->sblock.uuid[2]),
			grub_be_to_cpu16(data->sblock.uuid[3]),
			grub_be_to_cpu16(data->sblock.uuid[4]),
			grub_be_to_cpu16(data->sblock.uuid[5]),
			grub_be_to_cpu16(data->sblock.uuid[6]),
			grub_be_to_cpu16(data->sblock.uuid[7]));
	}
	else
		*uuid = NULL;

	grub_free(data);

	return grub_errno;
}

static struct grub_fs grub_xfs_fs =
{
	.name = "xfs",
	.fs_dir = grub_xfs_dir,
	.fs_open = grub_xfs_open,
	.fs_read = grub_xfs_read,
	.fs_close = grub_xfs_close,
	.fs_label = grub_xfs_label,
	.fs_uuid = grub_xfs_uuid,
	.next = 0
};

GRUB_MOD_INIT(xfs)
{
	grub_fs_register(&grub_xfs_fs);
}

GRUB_MOD_FINI(xfs)
{
	grub_fs_unregister(&grub_xfs_fs);
}
