pygrub: XFS support for pygrub

Signed-off-by: Marco Nenciarini <marco.nenciarini@devise.it>
Committed-by: Ian Jackson <ian.jackson@eu.citrix.com>

4 files changed, 1194 insertions, 1 deletions

diff --git a/tools/libfsimage/Makefile b/tools/libfsimage/Makefile
index 2075a192ab..2deb830f5f 100644
--- a/tools/libfsimage/Makefile
+++ b/tools/libfsimage/Makefile
@@ -1,7 +1,7 @@
 XEN_ROOT = $(CURDIR)/../..
 include $(XEN_ROOT)/tools/Rules.mk
 
-SUBDIRS-y = common ufs reiserfs iso9660 fat zfs
+SUBDIRS-y = common ufs reiserfs iso9660 fat zfs xfs
 SUBDIRS-y += $(shell env CC="$(CC)" ./check-libext2fs)
 
 .PHONY: all clean install
diff --git a/tools/libfsimage/xfs/Makefile b/tools/libfsimage/xfs/Makefile
new file mode 100644
index 0000000000..99ed1ba0db
--- /dev/null
+++ b/tools/libfsimage/xfs/Makefile
@@ -0,0 +1,13 @@
+XEN_ROOT = ../../..
+
+LIB_SRCS-y = fsys_xfs.c
+
+FS = xfs
+
+.PHONY: all
+all: fs-all
+
+.PHONY: install
+install: fs-install
+
+include $(XEN_ROOT)/tools/libfsimage/Rules.mk
diff --git a/tools/libfsimage/xfs/fsys_xfs.c b/tools/libfsimage/xfs/fsys_xfs.c
new file mode 100644
index 0000000000..6366d16d0d
--- /dev/null
+++ b/tools/libfsimage/xfs/fsys_xfs.c
@@ -0,0 +1,636 @@
+/* fsys_xfs.c - an implementation for the SGI XFS file system */
+/*  
+ *  GRUB  --  GRand Unified Bootloader
+ *  Copyright (C) 2001,2002,2004  Free Software Foundation, Inc.
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program 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 this program; if not, write to the Free Software
+ *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include <fsimage_grub.h>
+#include "xfs.h"
+
+#define MAX_LINK_COUNT	8
+
+typedef struct xad {
+	xfs_fileoff_t offset;
+	xfs_fsblock_t start;
+	xfs_filblks_t len;
+} xad_t;
+
+struct xfs_info {
+	int bsize;
+	int dirbsize;
+	int isize;
+	unsigned int agblocks;
+	int bdlog;
+	int blklog;
+	int inopblog;
+	int agblklog;
+	int agnolog;
+	unsigned int nextents;
+	xfs_daddr_t next;
+	xfs_daddr_t daddr;
+	xfs_dablk_t forw;
+	xfs_dablk_t dablk;
+	xfs_bmbt_rec_32_t *xt;
+	xfs_bmbt_ptr_t ptr0;
+	int btnode_ptr0_off;
+	int i8param;
+	int dirpos;
+	int dirmax;
+	int blkoff;
+	int fpos;
+	xfs_ino_t rootino;
+};
+
+static struct xfs_info xfs;
+
+#define dirbuf		((char *)FSYS_BUF)
+#define filebuf		((char *)FSYS_BUF + 4096)
+#define inode		((xfs_dinode_t *)((char *)FSYS_BUF + 8192))
+#define icore		(inode->di_core)
+
+#define	mask32lo(n)	(((xfs_uint32_t)1 << (n)) - 1)
+
+#define	XFS_INO_MASK(k)		((xfs_uint32_t)((1ULL << (k)) - 1))
+#define	XFS_INO_OFFSET_BITS	xfs.inopblog
+#define	XFS_INO_AGBNO_BITS	xfs.agblklog
+#define	XFS_INO_AGINO_BITS	(xfs.agblklog + xfs.inopblog)
+#define	XFS_INO_AGNO_BITS	xfs.agnolog
+
+static inline xfs_agblock_t
+agino2agbno (xfs_agino_t agino)
+{
+	return agino >> XFS_INO_OFFSET_BITS;
+}
+
+static inline xfs_agnumber_t
+ino2agno (xfs_ino_t ino)
+{
+	return ino >> XFS_INO_AGINO_BITS;
+}
+
+static inline xfs_agino_t
+ino2agino (xfs_ino_t ino)
+{
+	return ino & XFS_INO_MASK(XFS_INO_AGINO_BITS);
+}
+
+static inline int
+ino2offset (xfs_ino_t ino)
+{
+	return ino & XFS_INO_MASK(XFS_INO_OFFSET_BITS);
+}
+
+static inline xfs_uint16_t
+le16 (xfs_uint16_t x)
+{
+	__asm__("xchgb %b0,%h0"	\
+		: "=Q" (x) \
+		:  "0" (x)); \
+		return x;
+}
+
+static inline xfs_uint32_t
+le32 (xfs_uint32_t x)
+{
+#if 0
+        /* 386 doesn't have bswap.  */
+	__asm__("bswap %0" : "=r" (x) : "0" (x));
+#else
+	/* This is slower but this works on all x86 architectures.  */
+	__asm__("xchgb %b0, %h0" \
+		"\n\troll $16, %0" \
+		"\n\txchgb %b0, %h0" \
+		: "=Q" (x) : "0" (x));
+#endif
+	return x;
+}
+
+static inline xfs_uint64_t
+le64 (xfs_uint64_t x)
+{
+	xfs_uint32_t h = x >> 32;
+        xfs_uint32_t l = x & ((1ULL<<32)-1);
+        return (((xfs_uint64_t)le32(l)) << 32) | ((xfs_uint64_t)(le32(h)));
+}
+
+
+static xfs_fsblock_t
+xt_start (xfs_bmbt_rec_32_t *r)
+{
+	return (((xfs_fsblock_t)(le32 (r->l1) & mask32lo(9))) << 43) | 
+	       (((xfs_fsblock_t)le32 (r->l2)) << 11) |
+	       (((xfs_fsblock_t)le32 (r->l3)) >> 21);
+}
+
+static xfs_fileoff_t
+xt_offset (xfs_bmbt_rec_32_t *r)
+{
+	return (((xfs_fileoff_t)le32 (r->l0) &
+		mask32lo(31)) << 23) |
+		(((xfs_fileoff_t)le32 (r->l1)) >> 9);
+}
+
+static xfs_filblks_t
+xt_len (xfs_bmbt_rec_32_t *r)
+{
+	return le32(r->l3) & mask32lo(21);
+}
+
+static inline int
+xfs_highbit32(xfs_uint32_t v)
+{
+	int i;
+
+	if (--v) {
+		for (i = 0; i < 31; i++, v >>= 1) {
+			if (v == 0)
+				return i;
+		}
+	}
+	return 0;
+}
+
+static int
+isinxt (xfs_fileoff_t key, xfs_fileoff_t offset, xfs_filblks_t len)
+{
+	return (key >= offset) ? (key < offset + len ? 1 : 0) : 0;
+}
+
+static xfs_daddr_t
+agb2daddr (xfs_agnumber_t agno, xfs_agblock_t agbno)
+{
+	return ((xfs_fsblock_t)agno*xfs.agblocks + agbno) << xfs.bdlog;
+}
+
+static xfs_daddr_t
+fsb2daddr (xfs_fsblock_t fsbno)
+{
+	return agb2daddr ((xfs_agnumber_t)(fsbno >> xfs.agblklog),
+			 (xfs_agblock_t)(fsbno & mask32lo(xfs.agblklog)));
+}
+
+#undef offsetof
+#define offsetof(t,m)	((size_t)&(((t *)0)->m))
+
+static inline int
+btroot_maxrecs (fsi_file_t *ffi)
+{
+	int tmp = icore.di_forkoff ? (icore.di_forkoff << 3) : xfs.isize;
+
+	return (tmp - sizeof(xfs_bmdr_block_t) - offsetof(xfs_dinode_t, di_u)) /
+		(sizeof (xfs_bmbt_key_t) + sizeof (xfs_bmbt_ptr_t));
+}
+
+static int
+di_read (fsi_file_t *ffi, xfs_ino_t ino)
+{
+	xfs_agino_t agino;
+	xfs_agnumber_t agno;
+	xfs_agblock_t agbno;
+	xfs_daddr_t daddr;
+	int offset;
+
+	agno = ino2agno (ino);
+	agino = ino2agino (ino);
+	agbno = agino2agbno (agino);
+	offset = ino2offset (ino);
+	daddr = agb2daddr (agno, agbno);
+
+	devread (ffi, daddr, offset*xfs.isize, xfs.isize, (char *)inode);
+
+	xfs.ptr0 = *(xfs_bmbt_ptr_t *)
+		    (inode->di_u.di_c + sizeof(xfs_bmdr_block_t)
+		    + btroot_maxrecs (ffi)*sizeof(xfs_bmbt_key_t));
+
+	return 1;
+}
+
+static void
+init_extents (fsi_file_t *ffi)
+{
+	xfs_bmbt_ptr_t ptr0;
+	xfs_btree_lblock_t h;
+
+	switch (icore.di_format) {
+	case XFS_DINODE_FMT_EXTENTS:
+		xfs.xt = inode->di_u.di_bmx;
+		xfs.nextents = le32 (icore.di_nextents);
+		break;
+	case XFS_DINODE_FMT_BTREE:
+		ptr0 = xfs.ptr0;
+		for (;;) {
+			xfs.daddr = fsb2daddr (le64(ptr0));
+			devread (ffi, xfs.daddr, 0,
+				 sizeof(xfs_btree_lblock_t), (char *)&h);
+			if (!h.bb_level) {
+				xfs.nextents = le16(h.bb_numrecs);
+				xfs.next = fsb2daddr (le64(h.bb_rightsib));
+				xfs.fpos = sizeof(xfs_btree_block_t);
+				return;
+			}
+			devread (ffi, xfs.daddr, xfs.btnode_ptr0_off,
+				 sizeof(xfs_bmbt_ptr_t), (char *)&ptr0);
+		}
+	}
+}
+
+static xad_t *
+next_extent (fsi_file_t *ffi)
+{
+	static xad_t xad;
+
+	switch (icore.di_format) {
+	case XFS_DINODE_FMT_EXTENTS:
+		if (xfs.nextents == 0)
+			return NULL;
+		break;
+	case XFS_DINODE_FMT_BTREE:
+		if (xfs.nextents == 0) {
+			xfs_btree_lblock_t h;
+			if (xfs.next == 0)
+				return NULL;
+			xfs.daddr = xfs.next;
+			devread (ffi, xfs.daddr, 0, sizeof(xfs_btree_lblock_t), (char *)&h);
+			xfs.nextents = le16(h.bb_numrecs);
+			xfs.next = fsb2daddr (le64(h.bb_rightsib));
+			xfs.fpos = sizeof(xfs_btree_block_t);
+		}
+		/* Yeah, I know that's slow, but I really don't care */
+		devread (ffi, xfs.daddr, xfs.fpos, sizeof(xfs_bmbt_rec_t), filebuf);
+		xfs.xt = (xfs_bmbt_rec_32_t *)filebuf;
+		xfs.fpos += sizeof(xfs_bmbt_rec_32_t);
+	}
+	xad.offset = xt_offset (xfs.xt);
+	xad.start = xt_start (xfs.xt);
+	xad.len = xt_len (xfs.xt);
+	++xfs.xt;
+	--xfs.nextents;
+
+	return &xad;
+}
+
+/*
+ * Name lies - the function reads only first 100 bytes
+ */
+static void
+xfs_dabread (fsi_file_t *ffi)
+{
+	xad_t *xad;
+	xfs_fileoff_t offset;;
+
+	init_extents (ffi);
+	while ((xad = next_extent (ffi))) {
+		offset = xad->offset;
+		if (isinxt (xfs.dablk, offset, xad->len)) {
+			devread (ffi, fsb2daddr (xad->start + xfs.dablk - offset),
+				 0, 100, dirbuf);
+			break;
+		}
+	}
+}
+
+static inline xfs_ino_t
+sf_ino (char *sfe, int namelen)
+{
+	void *p = sfe + namelen + 3;
+
+	return (xfs.i8param == 0)
+		? le64(*(xfs_ino_t *)p) : le32(*(xfs_uint32_t *)p);
+}
+
+static inline xfs_ino_t
+sf_parent_ino (fsi_file_t *ffi)
+{
+	return (xfs.i8param == 0)
+		? le64(*(xfs_ino_t *)(&inode->di_u.di_dir2sf.hdr.parent))
+		: le32(*(xfs_uint32_t *)(&inode->di_u.di_dir2sf.hdr.parent));
+}
+
+static inline int
+roundup8 (int n)
+{
+	return ((n+7)&~7);
+}
+
+static int
+xfs_read (fsi_file_t *ffi, char *buf, int len);
+
+static char *
+next_dentry (fsi_file_t *ffi, xfs_ino_t *ino)
+{
+	int namelen = 1;
+	int toread;
+	static char usual[2][3] = {".", ".."};
+	static xfs_dir2_sf_entry_t *sfe;
+	char *name = usual[0];
+
+	if (xfs.dirpos >= xfs.dirmax) {
+		if (xfs.forw == 0)
+			return NULL;
+		xfs.dablk = xfs.forw;
+		xfs_dabread (ffi);
+#define h	((xfs_dir2_leaf_hdr_t *)dirbuf)
+		xfs.dirmax = le16 (h->count) - le16 (h->stale);
+		xfs.forw = le32 (h->info.forw);
+#undef h
+		xfs.dirpos = 0;
+	}
+
+	switch (icore.di_format) {
+	case XFS_DINODE_FMT_LOCAL:
+		switch (xfs.dirpos) {
+		case -2:
+			*ino = 0;
+			break;
+		case -1:
+			*ino = sf_parent_ino (ffi);
+			++name;
+			++namelen;
+			sfe = (xfs_dir2_sf_entry_t *)
+				(inode->di_u.di_c 
+				 + sizeof(xfs_dir2_sf_hdr_t)
+				 - xfs.i8param);
+			break;
+		default:
+			namelen = sfe->namelen;
+			*ino = sf_ino ((char *)sfe, namelen);
+			name = (char *)sfe->name;
+			sfe = (xfs_dir2_sf_entry_t *)
+				  ((char *)sfe + namelen + 11 - xfs.i8param);
+		}
+		break;
+	case XFS_DINODE_FMT_BTREE:
+	case XFS_DINODE_FMT_EXTENTS:
+#define dau	((xfs_dir2_data_union_t *)dirbuf)
+		for (;;) {
+			if (xfs.blkoff >= xfs.dirbsize) {
+				xfs.blkoff = sizeof(xfs_dir2_data_hdr_t);
+				filepos &= ~(xfs.dirbsize - 1);
+				filepos |= xfs.blkoff;
+			}
+			xfs_read (ffi, dirbuf, 4);
+			xfs.blkoff += 4;
+			if (dau->unused.freetag == XFS_DIR2_DATA_FREE_TAG) {
+				toread = roundup8 (le16(dau->unused.length)) - 4;
+				xfs.blkoff += toread;
+				filepos += toread;
+				continue;
+			}
+			break;
+		}
+		xfs_read (ffi, (char *)dirbuf + 4, 5);
+		*ino = le64 (dau->entry.inumber);
+		namelen = dau->entry.namelen;
+#undef dau
+		toread = roundup8 (namelen + 11) - 9;
+		xfs_read (ffi, dirbuf, toread);
+		name = (char *)dirbuf;
+		xfs.blkoff += toread + 5;
+	}
+	++xfs.dirpos;
+	name[namelen] = 0;
+
+	return name;
+}
+
+static char *
+first_dentry (fsi_file_t *ffi, xfs_ino_t *ino)
+{
+	xfs.forw = 0;
+	switch (icore.di_format) {
+	case XFS_DINODE_FMT_LOCAL:
+		xfs.dirmax = inode->di_u.di_dir2sf.hdr.count;
+		xfs.i8param = inode->di_u.di_dir2sf.hdr.i8count ? 0 : 4;
+		xfs.dirpos = -2;
+		break;
+	case XFS_DINODE_FMT_EXTENTS:
+	case XFS_DINODE_FMT_BTREE:
+		filepos = 0;
+		xfs_read (ffi, dirbuf, sizeof(xfs_dir2_data_hdr_t));
+		if (((xfs_dir2_data_hdr_t *)dirbuf)->magic == le32(XFS_DIR2_BLOCK_MAGIC)) {
+#define tail		((xfs_dir2_block_tail_t *)dirbuf)
+			filepos = xfs.dirbsize - sizeof(*tail);
+			xfs_read (ffi, dirbuf, sizeof(*tail));
+			xfs.dirmax = le32 (tail->count) - le32 (tail->stale);
+#undef tail
+		} else {
+			xfs.dablk = (1ULL << 35) >> xfs.blklog;
+#define h		((xfs_dir2_leaf_hdr_t *)dirbuf)
+#define n		((xfs_da_intnode_t *)dirbuf)
+			for (;;) {
+				xfs_dabread (ffi);
+				if ((n->hdr.info.magic == le16(XFS_DIR2_LEAFN_MAGIC))
+				    || (n->hdr.info.magic == le16(XFS_DIR2_LEAF1_MAGIC))) {
+					xfs.dirmax = le16 (h->count) - le16 (h->stale);
+					xfs.forw = le32 (h->info.forw);
+					break;
+				}
+				xfs.dablk = le32 (n->btree[0].before);
+			}
+#undef n
+#undef h
+		}
+		xfs.blkoff = sizeof(xfs_dir2_data_hdr_t);
+		filepos = xfs.blkoff;
+		xfs.dirpos = 0;
+	}
+	return next_dentry (ffi, ino);
+}
+
+static int
+xfs_mount (fsi_file_t *ffi, const char *options)
+{
+	xfs_sb_t super;
+
+	if (!devread (ffi, 0, 0, sizeof(super), (char *)&super)
+	    || (le32(super.sb_magicnum) != XFS_SB_MAGIC)
+	    || ((le16(super.sb_versionnum) 
+		& XFS_SB_VERSION_NUMBITS) != XFS_SB_VERSION_4) ) {
+		return 0;
+	}
+
+	xfs.bsize = le32 (super.sb_blocksize);
+	xfs.blklog = super.sb_blocklog;
+	xfs.bdlog = xfs.blklog - SECTOR_BITS;
+	xfs.rootino = le64 (super.sb_rootino);
+	xfs.isize = le16 (super.sb_inodesize);
+	xfs.agblocks = le32 (super.sb_agblocks);
+	xfs.dirbsize = xfs.bsize << super.sb_dirblklog;
+
+	xfs.inopblog = super.sb_inopblog;
+	xfs.agblklog = super.sb_agblklog;
+	xfs.agnolog = xfs_highbit32 (le32(super.sb_agcount));
+
+	xfs.btnode_ptr0_off =
+		((xfs.bsize - sizeof(xfs_btree_block_t)) /
+		(sizeof (xfs_bmbt_key_t) + sizeof (xfs_bmbt_ptr_t)))
+		 * sizeof(xfs_bmbt_key_t) + sizeof(xfs_btree_block_t);
+
+	return 1;
+}
+
+static int
+xfs_read (fsi_file_t *ffi, char *buf, int len)
+{
+	xad_t *xad;
+	xfs_fileoff_t endofprev, endofcur, offset;
+	xfs_filblks_t xadlen;
+	int toread, startpos, endpos;
+
+	if (icore.di_format == XFS_DINODE_FMT_LOCAL) {
+		grub_memmove (buf, inode->di_u.di_c + filepos, len);
+		filepos += len;
+		return len;
+	}
+
+	startpos = filepos;
+	endpos = filepos + len;
+	endofprev = (xfs_fileoff_t)-1;
+	init_extents (ffi);
+	while (len > 0 && (xad = next_extent (ffi))) {
+		offset = xad->offset;
+		xadlen = xad->len;
+		if (isinxt (filepos >> xfs.blklog, offset, xadlen)) {
+			endofcur = (offset + xadlen) << xfs.blklog; 
+			toread = (endofcur >= endpos)
+				  ? len : (endofcur - filepos);
+
+			disk_read_func = disk_read_hook;
+			devread (ffi, fsb2daddr (xad->start),
+				 filepos - (offset << xfs.blklog), toread, buf);
+			disk_read_func = NULL;
+
+			buf += toread;
+			len -= toread;
+			filepos += toread;
+		} else if (offset > endofprev) {
+			toread = ((offset << xfs.blklog) >= endpos)
+				  ? len : ((offset - endofprev) << xfs.blklog);
+			len -= toread;
+			filepos += toread;
+			for (; toread; toread--) {
+				*buf++ = 0;
+			}
+			continue;
+		}
+		endofprev = offset + xadlen; 
+	}
+
+	return filepos - startpos;
+}
+
+static int
+xfs_dir (fsi_file_t *ffi, char *dirname)
+{
+	xfs_ino_t ino, parent_ino, new_ino;
+	xfs_fsize_t di_size;
+	int di_mode;
+	int cmp, n, link_count;
+	char linkbuf[xfs.bsize];
+	char *rest, *name, ch;
+
+	parent_ino = ino = xfs.rootino;
+	link_count = 0;
+	for (;;) {
+		di_read (ffi, ino);
+		di_size = le64 (icore.di_size);
+		di_mode = le16 (icore.di_mode);
+
+		if ((di_mode & IFMT) == IFLNK) {
+			if (++link_count > MAX_LINK_COUNT) {
+				errnum = ERR_SYMLINK_LOOP;
+				return 0;
+			}
+			if (di_size < xfs.bsize - 1) {
+				filepos = 0;
+				filemax = di_size;
+				n = xfs_read (ffi, linkbuf, filemax);
+			} else {
+				errnum = ERR_FILELENGTH;
+				return 0;
+			}
+
+			ino = (linkbuf[0] == '/') ? xfs.rootino : parent_ino;
+			while (n < (xfs.bsize - 1) && (linkbuf[n++] = *dirname++));
+			linkbuf[n] = 0;
+			dirname = linkbuf;
+			continue;
+		}
+
+		if (!*dirname || isspace (*dirname)) {
+			if ((di_mode & IFMT) != IFREG) {
+				errnum = ERR_BAD_FILETYPE;
+				return 0;
+			}
+			filepos = 0;
+			filemax = di_size;
+			return 1;
+		}
+
+		if ((di_mode & IFMT) != IFDIR) {
+			errnum = ERR_BAD_FILETYPE;
+			return 0;
+		}
+
+		for (; *dirname == '/'; dirname++);
+
+		for (rest = dirname; (ch = *rest) && !isspace (ch) && ch != '/'; rest++);
+		*rest = 0;
+
+		name = first_dentry (ffi, &new_ino);
+		for (;;) {
+			cmp = (!*dirname) ? -1 : substring (dirname, name);
+#ifndef STAGE1_5
+			if (print_possibilities && ch != '/' && cmp <= 0) {
+				if (print_possibilities > 0)
+					print_possibilities = -print_possibilities;
+				print_a_completion (name);
+			} else
+#endif
+			if (cmp == 0) {
+				parent_ino = ino;
+				if (new_ino)
+					ino = new_ino;
+		        	*(dirname = rest) = ch;
+				break;
+			}
+			name = next_dentry (ffi, &new_ino);
+			if (name == NULL) {
+				if (print_possibilities < 0)
+					return 1;
+
+				errnum = ERR_FILE_NOT_FOUND;
+				*rest = ch;
+				return 0;
+			}
+		}
+	}
+}
+
+fsi_plugin_ops_t *
+fsi_init_plugin(int version, fsi_plugin_t *fp, const char **name)
+{
+	static fsig_plugin_ops_t ops = {
+		FSIMAGE_PLUGIN_VERSION,
+		.fpo_mount = xfs_mount,
+		.fpo_dir = xfs_dir,
+		.fpo_read = xfs_read
+	};
+
+	*name = "xfs";
+	return (fsig_init(fp, &ops));
+}
diff --git a/tools/libfsimage/xfs/xfs.h b/tools/libfsimage/xfs/xfs.h
new file mode 100644
index 0000000000..02f8dcd1a2
--- /dev/null
+++ b/tools/libfsimage/xfs/xfs.h
@@ -0,0 +1,544 @@
+/* xfs.h - an extraction from xfsprogs-1.3.5/include/xfs* into one file */
+/* 
+ *  GRUB  --  GRand Unified Bootloader
+ *  Copyright (C) 2000  Silicon Graphics, Inc.  All Rights Reserved.
+ *  Copyright (C) 2001,2004  Free Software Foundation, Inc.
+ * 
+ *  This program is free software; you can redistribute it and/or modify it
+ *  under the terms of version 2 of the GNU General Public License as
+ *  published by the Free Software Foundation.
+ * 
+ *  This program is distributed in the hope that it would be useful, but
+ *  WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * 
+ *  Further, this software is distributed without any warranty that it is
+ *  free of the rightful claim of any third person regarding infringement
+ *  or the like.  Any license provided herein, whether implied or
+ *  otherwise, applies only to this software file.  Patent licenses, if
+ *  any, provided herein do not apply to combinations of this program with
+ *  other software, or any other product whatsoever.
+ * 
+ *  You should have received a copy of the GNU General Public License along
+ *  with this program; if not, write the Free Software Foundation, Inc., 59
+ *  Temple Place - Suite 330, Boston MA 02111-1307, USA.
+ * 
+ *  Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
+ *  Mountain View, CA  94043, or:
+ * 
+ *  http://www.sgi.com 
+ * 
+ *  For further information regarding this notice, see: 
+ * 
+ *  http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
+ */
+
+typedef signed char	xfs_int8_t;
+typedef unsigned char	xfs_uint8_t;
+typedef short		xfs_int16_t;
+typedef unsigned short	xfs_uint16_t;
+typedef int		xfs_int32_t;
+typedef unsigned int	xfs_uint32_t;
+typedef long long	xfs_int64_t;
+typedef unsigned long long xfs_uint64_t;
+
+typedef xfs_uint64_t	xfs_ino_t;
+typedef	xfs_uint32_t	xfs_agino_t;
+typedef xfs_int64_t	xfs_daddr_t;
+typedef xfs_int64_t	xfs_off_t;
+typedef xfs_uint8_t	uuid_t[16];
+
+
+/* those are from xfs_types.h */
+
+typedef xfs_uint32_t	xfs_agblock_t;	/* blockno in alloc. group */
+typedef	xfs_uint32_t	xfs_extlen_t;	/* extent length in blocks */
+typedef	xfs_uint32_t	xfs_agnumber_t;	/* allocation group number */
+typedef xfs_int32_t	xfs_extnum_t;	/* # of extents in a file */
+typedef xfs_int16_t	xfs_aextnum_t;	/* # extents in an attribute fork */
+typedef	xfs_int64_t	xfs_fsize_t;	/* bytes in a file */
+
+typedef	xfs_uint32_t	xfs_dablk_t;	/* dir/attr block number (in file) */
+typedef	xfs_uint32_t	xfs_dahash_t;	/* dir/attr hash value */
+
+/*
+ * Disk based types:
+ */
+typedef xfs_uint64_t	xfs_dfsbno_t;	/* blockno in filesystem (agno|agbno) */
+typedef xfs_uint64_t	xfs_drfsbno_t;	/* blockno in filesystem (raw) */
+typedef	xfs_uint64_t	xfs_drtbno_t;	/* extent (block) in realtime area */
+typedef	xfs_uint64_t	xfs_dfiloff_t;	/* block number in a file */
+
+typedef	xfs_uint64_t	xfs_fsblock_t;	/* blockno in filesystem (agno|agbno) */
+typedef	xfs_uint64_t	xfs_fileoff_t;	/* block number in a file */
+typedef	xfs_uint64_t	xfs_filblks_t;	/* number of blocks in a file */
+
+
+/* those are from xfs_sb.h */
+
+#define	XFS_SB_MAGIC		0x58465342	/* 'XFSB'*/
+#define	XFS_SB_VERSION_4	4		/* 6.2+ - bitmask version */
+#define	XFS_SB_VERSION_NUMBITS	0x000f
+
+typedef struct xfs_sb
+{
+	xfs_uint32_t	sb_magicnum;	/* magic number == XFS_SB_MAGIC */
+	xfs_uint32_t	sb_blocksize;	/* logical block size, bytes */
+	xfs_drfsbno_t	sb_dblocks;	/* number of data blocks */
+	xfs_drfsbno_t	sb_rblocks;	/* number of realtime blocks */
+	xfs_drtbno_t	sb_rextents;	/* number of realtime extents */
+	uuid_t		sb_uuid;	/* file system unique id */
+	xfs_dfsbno_t	sb_logstart;	/* starting block of log if internal */
+	xfs_ino_t	sb_rootino;	/* root inode number */
+	xfs_ino_t	sb_rbmino;	/* bitmap inode for realtime extents */
+	xfs_ino_t	sb_rsumino;	/* summary inode for rt bitmap */
+	xfs_agblock_t	sb_rextsize;	/* realtime extent size, blocks */
+	xfs_agblock_t	sb_agblocks;	/* size of an allocation group */
+	xfs_agnumber_t	sb_agcount;	/* number of allocation groups */
+	xfs_extlen_t	sb_rbmblocks;	/* number of rt bitmap blocks */
+	xfs_extlen_t	sb_logblocks;	/* number of log blocks */
+	xfs_uint16_t	sb_versionnum;	/* header version == XFS_SB_VERSION */
+	xfs_uint16_t	sb_sectsize;	/* volume sector size, bytes */
+	xfs_uint16_t	sb_inodesize;	/* inode size, bytes */
+	xfs_uint16_t	sb_inopblock;	/* inodes per block */
+	char		sb_fname[12];	/* file system name */
+	xfs_uint8_t	sb_blocklog;	/* log2 of sb_blocksize */
+	xfs_uint8_t	sb_sectlog;	/* log2 of sb_sectsize */
+	xfs_uint8_t	sb_inodelog;	/* log2 of sb_inodesize */
+	xfs_uint8_t	sb_inopblog;	/* log2 of sb_inopblock */
+	xfs_uint8_t	sb_agblklog;	/* log2 of sb_agblocks (rounded up) */
+	xfs_uint8_t	sb_rextslog;	/* log2 of sb_rextents */
+	xfs_uint8_t	sb_inprogress;	/* mkfs is in progress, don't mount */
+	xfs_uint8_t	sb_imax_pct;	/* max % of fs for inode space */
+					/* statistics */
+	/*
+	 * These fields must remain contiguous.  If you really
+	 * want to change their layout, make sure you fix the
+	 * code in xfs_trans_apply_sb_deltas().
+	 */
+	xfs_uint64_t	sb_icount;	/* allocated inodes */
+	xfs_uint64_t	sb_ifree;	/* free inodes */
+	xfs_uint64_t	sb_fdblocks;	/* free data blocks */
+	xfs_uint64_t	sb_frextents;	/* free realtime extents */
+	/*
+	 * End contiguous fields.
+	 */
+	xfs_ino_t	sb_uquotino;	/* user quota inode */
+	xfs_ino_t	sb_gquotino;	/* group quota inode */
+	xfs_uint16_t	sb_qflags;	/* quota flags */
+	xfs_uint8_t	sb_flags;	/* misc. flags */
+	xfs_uint8_t	sb_shared_vn;	/* shared version number */
+	xfs_extlen_t	sb_inoalignmt;	/* inode chunk alignment, fsblocks */
+	xfs_uint32_t	sb_unit;	/* stripe or raid unit */
+	xfs_uint32_t	sb_width;	/* stripe or raid width */	
+	xfs_uint8_t	sb_dirblklog;	/* log2 of dir block size (fsbs) */
+        xfs_uint8_t       sb_dummy[7];    /* padding */
+} xfs_sb_t;
+
+
+/* those are from xfs_btree.h */
+
+/*
+ * Long form header: bmap btrees.
+ */
+typedef struct xfs_btree_lblock
+{
+	xfs_uint32_t	bb_magic;	/* magic number for block type */
+	xfs_uint16_t	bb_level;	/* 0 is a leaf */
+	xfs_uint16_t	bb_numrecs;	/* current # of data records */
+	xfs_dfsbno_t	bb_leftsib;	/* left sibling block or NULLDFSBNO */
+	xfs_dfsbno_t	bb_rightsib;	/* right sibling block or NULLDFSBNO */
+} xfs_btree_lblock_t;
+
+/*
+ * Combined header and structure, used by common code.
+ */
+typedef struct xfs_btree_hdr
+{
+	xfs_uint32_t	bb_magic;	/* magic number for block type */
+	xfs_uint16_t	bb_level;	/* 0 is a leaf */
+	xfs_uint16_t	bb_numrecs;	/* current # of data records */
+} xfs_btree_hdr_t;
+
+typedef struct xfs_btree_block
+{
+	xfs_btree_hdr_t	bb_h;		/* header */
+	union		{
+		struct	{
+			xfs_agblock_t	bb_leftsib;
+			xfs_agblock_t	bb_rightsib;
+		}	s;		/* short form pointers */
+		struct	{
+			xfs_dfsbno_t	bb_leftsib;
+			xfs_dfsbno_t	bb_rightsib;
+		}	l;		/* long form pointers */
+	}		bb_u;		/* rest */
+} xfs_btree_block_t;
+
+/* those are from xfs_bmap_btree.h */
+
+/*
+ * Bmap root header, on-disk form only.
+ */
+typedef struct xfs_bmdr_block
+{
+	xfs_uint16_t	bb_level;	/* 0 is a leaf */
+	xfs_uint16_t	bb_numrecs;	/* current # of data records */
+} xfs_bmdr_block_t;
+
+/*
+ * Bmap btree record and extent descriptor.
+ * For 32-bit kernels,
+ *  l0:31 is an extent flag (value 1 indicates non-normal).
+ *  l0:0-30 and l1:9-31 are startoff.
+ *  l1:0-8, l2:0-31, and l3:21-31 are startblock.
+ *  l3:0-20 are blockcount.
+ * For 64-bit kernels,
+ *  l0:63 is an extent flag (value 1 indicates non-normal).
+ *  l0:9-62 are startoff.
+ *  l0:0-8 and l1:21-63 are startblock.
+ *  l1:0-20 are blockcount.
+ */
+
+#define	BMBT_USE_64	1
+
+typedef struct xfs_bmbt_rec_32
+{
+	xfs_uint32_t		l0, l1, l2, l3;
+} xfs_bmbt_rec_32_t;
+typedef struct xfs_bmbt_rec_64
+{
+	xfs_uint64_t		l0, l1;
+} xfs_bmbt_rec_64_t;
+
+#if BMBT_USE_64
+typedef	xfs_uint64_t	xfs_bmbt_rec_base_t;	/* use this for casts */
+typedef xfs_bmbt_rec_64_t xfs_bmbt_rec_t, xfs_bmdr_rec_t;
+#else	/* !BMBT_USE_64 */
+typedef	xfs_uint32_t	xfs_bmbt_rec_base_t;	/* use this for casts */
+typedef xfs_bmbt_rec_32_t xfs_bmbt_rec_t, xfs_bmdr_rec_t;
+#endif	/* BMBT_USE_64 */
+
+/*
+ * Key structure for non-leaf levels of the tree.
+ */
+typedef struct xfs_bmbt_key
+{
+	xfs_dfiloff_t	br_startoff;	/* starting file offset */
+} xfs_bmbt_key_t, xfs_bmdr_key_t;
+
+typedef xfs_dfsbno_t xfs_bmbt_ptr_t, xfs_bmdr_ptr_t;	/* btree pointer type */
+					/* btree block header type */
+typedef	struct xfs_btree_lblock xfs_bmbt_block_t;
+
+
+/* those are from xfs_dir2.h */
+/*
+ * Directory version 2.
+ * There are 4 possible formats:
+ *	shortform
+ *	single block - data with embedded leaf at the end
+ *	multiple data blocks, single leaf+freeindex block
+ *	data blocks, node&leaf blocks (btree), freeindex blocks
+ *
+ *	The shortform format is in xfs_dir2_sf.h.
+ *	The single block format is in xfs_dir2_block.h.
+ *	The data block format is in xfs_dir2_data.h.
+ *	The leaf and freeindex block formats are in xfs_dir2_leaf.h.
+ *	Node blocks are the same as the other version, in xfs_da_btree.h.
+ */
+
+/*
+ * Byte offset in data block and shortform entry.
+ */
+typedef	xfs_uint16_t	xfs_dir2_data_off_t;
+
+/*
+ * Byte offset in a directory.
+ */
+typedef	xfs_off_t		xfs_dir2_off_t;
+
+/* those are from xfs_da_btree.h */
+/*========================================================================
+ * Directory Structure when greater than XFS_LBSIZE(mp) bytes.
+ *========================================================================*/
+
+/*
+ * This structure is common to both leaf nodes and non-leaf nodes in the Btree.
+ *
+ * Is is used to manage a doubly linked list of all blocks at the same
+ * level in the Btree, and to identify which type of block this is.
+ */
+#define	XFS_DIR2_LEAF1_MAGIC	0xd2f1	/* magic number: v2 dirlf single blks */
+#define	XFS_DIR2_LEAFN_MAGIC	0xd2ff	/* magic number: v2 dirlf multi blks */
+
+typedef struct xfs_da_blkinfo {
+	xfs_dablk_t forw;			/* previous block in list */
+	xfs_dablk_t back;			/* following block in list */
+	xfs_uint16_t magic;			/* validity check on block */
+	xfs_uint16_t pad;				/* unused */
+} xfs_da_blkinfo_t;
+
+/*
+ * This is the structure of the root and intermediate nodes in the Btree.
+ * The leaf nodes are defined above.
+ *
+ * Entries are not packed.
+ *
+ * Since we have duplicate keys, use a binary search but always follow
+ * all match in the block, not just the first match found.
+ */
+
+typedef struct xfs_da_intnode {
+	struct xfs_da_node_hdr {	/* constant-structure header block */
+		xfs_da_blkinfo_t info;	/* block type, links, etc. */
+		xfs_uint16_t count;	/* count of active entries */
+		xfs_uint16_t level;	/* level above leaves (leaf == 0) */
+	} hdr;
+	struct xfs_da_node_entry {
+		xfs_dahash_t hashval;	/* hash value for this descendant */
+		xfs_dablk_t before;	/* Btree block before this key */
+	} btree[1];			/* variable sized array of keys */
+} xfs_da_intnode_t;
+
+
+/* those are from xfs_dir2_data.h */
+/*
+ * Directory format 2, data block structures.
+ */
+
+/*
+ * Constants.
+ */
+#define	XFS_DIR2_DATA_FREE_TAG	0xffff
+#define	XFS_DIR2_DATA_FD_COUNT	3
+
+/*
+ * Structures.
+ */
+
+/*
+ * Describe a free area in the data block.
+ * The freespace will be formatted as a xfs_dir2_data_unused_t.
+ */
+typedef struct xfs_dir2_data_free {
+	xfs_dir2_data_off_t	offset;		/* start of freespace */
+	xfs_dir2_data_off_t	length;		/* length of freespace */
+} xfs_dir2_data_free_t;
+
+/*
+ * Header for the data blocks.
+ * Always at the beginning of a directory-sized block.
+ * The code knows that XFS_DIR2_DATA_FD_COUNT is 3.
+ */
+typedef struct xfs_dir2_data_hdr {
+	xfs_uint32_t		magic;		/* XFS_DIR2_DATA_MAGIC */
+						/* or XFS_DIR2_BLOCK_MAGIC */
+	xfs_dir2_data_free_t	bestfree[XFS_DIR2_DATA_FD_COUNT];
+} xfs_dir2_data_hdr_t;
+
+/*
+ * Active entry in a data block.  Aligned to 8 bytes.
+ * Tag appears as the last 2 bytes.
+ */
+typedef struct xfs_dir2_data_entry {
+	xfs_ino_t		inumber;	/* inode number */
+	xfs_uint8_t		namelen;	/* name length */
+	xfs_uint8_t		name[1];	/* name bytes, no null */
+						/* variable offset */
+	xfs_dir2_data_off_t	tag;		/* starting offset of us */
+} xfs_dir2_data_entry_t;
+
+/*
+ * Unused entry in a data block.  Aligned to 8 bytes.
+ * Tag appears as the last 2 bytes.
+ */
+typedef struct xfs_dir2_data_unused {
+	xfs_uint16_t		freetag;	/* XFS_DIR2_DATA_FREE_TAG */
+	xfs_dir2_data_off_t	length;		/* total free length */
+						/* variable offset */
+	xfs_dir2_data_off_t	tag;		/* starting offset of us */
+} xfs_dir2_data_unused_t;
+
+typedef union {
+	xfs_dir2_data_entry_t	entry;
+	xfs_dir2_data_unused_t	unused;
+} xfs_dir2_data_union_t;
+
+
+/* those are from xfs_dir2_leaf.h */
+/*
+ * Directory version 2, leaf block structures.
+ */
+
+/*
+ * Leaf block header.
+ */
+typedef struct xfs_dir2_leaf_hdr {
+	xfs_da_blkinfo_t	info;		/* header for da routines */
+	xfs_uint16_t		count;		/* count of entries */
+	xfs_uint16_t		stale;		/* count of stale entries */
+} xfs_dir2_leaf_hdr_t;
+
+
+/* those are from xfs_dir2_block.h */
+/*
+ * xfs_dir2_block.h
+ * Directory version 2, single block format structures
+ */
+
+/*
+ * The single block format is as follows:
+ * xfs_dir2_data_hdr_t structure
+ * xfs_dir2_data_entry_t and xfs_dir2_data_unused_t structures
+ * xfs_dir2_leaf_entry_t structures
+ * xfs_dir2_block_tail_t structure
+ */
+
+#define	XFS_DIR2_BLOCK_MAGIC	0x58443242	/* XD2B: for one block dirs */
+
+typedef struct xfs_dir2_block_tail {
+	xfs_uint32_t	count;			/* count of leaf entries */
+	xfs_uint32_t	stale;			/* count of stale lf entries */
+} xfs_dir2_block_tail_t;
+
+
+/* those are from xfs_dir2_sf.h */
+
+/*
+ * Directory layout when stored internal to an inode.
+ *
+ * Small directories are packed as tightly as possible so as to
+ * fit into the literal area of the inode.
+ */
+
+/*
+ * Inode number stored as 8 8-bit values.
+ */
+typedef	struct { xfs_uint8_t i[8]; } xfs_dir2_ino8_t;
+
+/*
+ * Inode number stored as 4 8-bit values.
+ * Works a lot of the time, when all the inode numbers in a directory
+ * fit in 32 bits.
+ */
+typedef struct { xfs_uint8_t i[4]; } xfs_dir2_ino4_t;
+
+typedef union {
+	xfs_dir2_ino8_t	i8;
+	xfs_dir2_ino4_t	i4;
+} xfs_dir2_inou_t;
+
+/*
+ * Normalized offset (in a data block) of the entry, really xfs_dir2_data_off_t.
+ * Only need 16 bits, this is the byte offset into the single block form.
+ */
+typedef struct { xfs_uint8_t i[2]; } xfs_dir2_sf_off_t;
+
+/*
+ * The parent directory has a dedicated field, and the self-pointer must
+ * be calculated on the fly.
+ *
+ * Entries are packed toward the top as tightly as possible.  The header
+ * and the elements must be bcopy()'d out into a work area to get correct
+ * alignment for the inode number fields.
+ */
+typedef struct xfs_dir2_sf_hdr {
+	xfs_uint8_t		count;		/* count of entries */
+	xfs_uint8_t		i8count;	/* count of 8-byte inode #s */
+	xfs_dir2_inou_t		parent;		/* parent dir inode number */
+} xfs_dir2_sf_hdr_t;
+
+typedef struct xfs_dir2_sf_entry {
+	xfs_uint8_t		namelen;	/* actual name length */
+	xfs_dir2_sf_off_t	offset;		/* saved offset */
+	xfs_uint8_t		name[1];	/* name, variable size */
+	xfs_dir2_inou_t		inumber;	/* inode number, var. offset */
+} xfs_dir2_sf_entry_t;
+
+typedef struct xfs_dir2_sf {
+	xfs_dir2_sf_hdr_t	hdr;		/* shortform header */
+	xfs_dir2_sf_entry_t	list[1];	/* shortform entries */
+} xfs_dir2_sf_t;
+
+/* those are from xfs_dinode.h */
+
+#define	XFS_DINODE_VERSION_1	1
+#define	XFS_DINODE_VERSION_2	2
+#define	XFS_DINODE_MAGIC	0x494e	/* 'IN' */
+
+/*
+ * Disk inode structure.
+ * This is just the header; the inode is expanded to fill a variable size
+ * with the last field expanding.  It is split into the core and "other"
+ * because we only need the core part in the in-core inode.
+ */
+typedef struct xfs_timestamp {
+	xfs_int32_t	t_sec;		/* timestamp seconds */
+	xfs_int32_t	t_nsec;		/* timestamp nanoseconds */
+} xfs_timestamp_t;
+
+/*
+ * Note: Coordinate changes to this structure with the XFS_DI_* #defines
+ * below and the offsets table in xfs_ialloc_log_di().
+ */
+typedef struct xfs_dinode_core
+{
+	xfs_uint16_t	di_magic;	/* inode magic # = XFS_DINODE_MAGIC */
+	xfs_uint16_t	di_mode;	/* mode and type of file */
+	xfs_int8_t	di_version;	/* inode version */
+	xfs_int8_t	di_format;	/* format of di_c data */
+	xfs_uint16_t	di_onlink;	/* old number of links to file */
+	xfs_uint32_t	di_uid;		/* owner's user id */
+	xfs_uint32_t	di_gid;		/* owner's group id */
+	xfs_uint32_t	di_nlink;	/* number of links to file */
+	xfs_uint16_t	di_projid;	/* owner's project id */
+	xfs_uint8_t	di_pad[10];	/* unused, zeroed space */
+	xfs_timestamp_t	di_atime;	/* time last accessed */
+	xfs_timestamp_t	di_mtime;	/* time last modified */
+	xfs_timestamp_t	di_ctime;	/* time created/inode modified */
+	xfs_fsize_t	di_size;	/* number of bytes in file */
+	xfs_drfsbno_t	di_nblocks;	/* # of direct & btree blocks used */
+	xfs_extlen_t	di_extsize;	/* basic/minimum extent size for file */
+	xfs_extnum_t	di_nextents;	/* number of extents in data fork */
+	xfs_aextnum_t	di_anextents;	/* number of extents in attribute fork*/
+	xfs_uint8_t	di_forkoff;	/* attr fork offs, <<3 for 64b align */
+	xfs_int8_t	di_aformat;	/* format of attr fork's data */
+	xfs_uint32_t	di_dmevmask;	/* DMIG event mask */
+	xfs_uint16_t	di_dmstate;	/* DMIG state info */
+	xfs_uint16_t	di_flags;	/* random flags, XFS_DIFLAG_... */
+	xfs_uint32_t	di_gen;		/* generation number */
+} xfs_dinode_core_t;
+
+typedef struct xfs_dinode
+{
+	xfs_dinode_core_t	di_core;
+	xfs_agino_t		di_next_unlinked;/* agi unlinked list ptr */
+	union {
+		xfs_bmdr_block_t di_bmbt;	/* btree root block */
+		xfs_bmbt_rec_32_t di_bmx[1];	/* extent list */
+		xfs_dir2_sf_t	di_dir2sf;	/* shortform directory v2 */
+		char		di_c[1];	/* local contents */
+	} di_u;
+} xfs_dinode_t;
+
+/*
+ * Values for di_format
+ */
+typedef enum xfs_dinode_fmt
+{
+	XFS_DINODE_FMT_DEV,		/* CHR, BLK: di_dev */
+	XFS_DINODE_FMT_LOCAL,		/* DIR, REG: di_c */
+					/* LNK: di_symlink */
+	XFS_DINODE_FMT_EXTENTS,		/* DIR, REG, LNK: di_bmx */
+	XFS_DINODE_FMT_BTREE,		/* DIR, REG, LNK: di_bmbt */
+	XFS_DINODE_FMT_UUID 		/* MNT: di_uuid */
+} xfs_dinode_fmt_t;
+
+/*
+ * File types (mode field)
+ */
+#define	IFMT		0170000		/* type of file */
+#define	IFDIR		0040000		/* directory */
+#define	IFREG		0100000		/* regular */
+#define	IFLNK		0120000		/* symbolic link */