/* lynxfs.c - Lynx filesystem as used on LOS178 */

/**
 * Overview of LynxFS as used with LynxOS-178.
 *
 * LynxFS is a very simple non-power safe file system.
 * It is similar to ext2 in may important aspects.
 *
 * Inodes:
 * Inodes are 128 bytes each and start in block 2.
 * The first inode is 1, which is the filesystem root directory.
 * The block number and block offset are determined as follows:
 *   rel_off = (inode - 1) * 128
 *   blk_num = 2 + (reloff >> sb->block_bits)
 *   blk_off = reloff & (sb->block_size - 1)
 * Where block bits is the number of bits in the block size.
 * For example, if block_size is 2048, then block_bits is 11.
 * Note that LOS178 can only handle block sizes of 1024 and 2048 bytes.
 * You can create a filesystem with 4096+ byte blocks, but the kernel dies.
 *
 * Blocks:
 * The whole filesystem is addressed in terms of blocks.
 * Block 0 isn't used directly, but contains a shadow copy of the SuperBlock at
 *   offset 512. Only the magic, bsize_magic, and bsize_code should be used
 *   from this pseudo SuperBlock. The other data isn't likely to be accurate.
 * Block 1 contains the real SuperBlock.
 * Block 2 is the start of the inodes.
 * I don't recall what happens if block_size = 512. Don't do that.
 *
 * Inode Block list:
 * The inode block list is very similar to the 32-bit ext2 structure.
 * The blocks are packed as 24 bits in inode->i_blocks.
 * The first 10 entries are directly mapped blocks.
 * Entry 11 is 1-level indirect.
 * Entry 12 is 2-level indirect.
 * Entry 13 is 3-level indirect.
 * Block numbers in the indirect block are 32-bits, although only the lower 24
 * bits may be used.
 *
 * Directory entries:
 * Directory entries are just normal file data and are padded to 4 bytes.
 * The d_reclen field indicates the size of the record.  As a side note, the
 * last record in the block uses the remaining space in the block.
 *
 * Symlink entries:
 * The symlink target is stored in normal file data.
 *
 * Limitations:
 * The use of 24-bit block addresses limits the size of the filesystem to
 * ~(2^24 * block_size) bytes, or ~34 GB for 2048-byte blocks.
 */

 /* Index of first indirect block in inode->i_blocks */
#define INDIRECT_BLOCKS          10

/* 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

#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+");

/* Log2 size of ext2 block in 512 blocks.  */
#define LOG2_512_BLOCK_SIZE(data) \
(data->block_bits - GRUB_DISK_SECTOR_BITS)

/**
 * This is the on-disk super-block structure for LynxFS.
 * The superblock start at offset 512 in the partition.
 *
 * All fields are stored big-endian, so use grub_be_to_cpu32() to access.
 */
struct grub_lynxfs_sblock
{
	grub_uint32_t free_inodes;        /* free inode list */
	grub_uint32_t free_blocks;        /* free block list */
	grub_uint32_t num_inodes;         /* number of inodes on this device */
	grub_uint32_t num_blocks;         /* number of blocks on this device */
	grub_uint32_t root_inode;         /* root of disk file system (?) */
	grub_uint32_t spare1;
	grub_uint32_t free_icount;        /* number of free inodes */
	grub_uint32_t free_bcount;        /* number of free blocks */
	grub_uint32_t spare2;
	grub_uint32_t status;             /* dirty or ok */
	grub_uint32_t magic;              /* magic number */
	grub_uint32_t time;               /* creation time */
	grub_uint32_t bsize_magic;        /* variable block size supported? */
	grub_uint32_t bsize_code;         /* file system block size */
	grub_uint32_t bitmap_magic;       /* bit map free list supported? */
	grub_uint32_t bitmap_blocks;      /* block number of first bitmap block */
	grub_uint32_t bitmap_chunksize;   /* 1st lvl bit is how many 32bit masks*/
	grub_uint32_t spare[5];
	//grub_uint32_t bitmap_map[0];      /* 2 level block bitmap */
};

#define LYNXFS_SB_MAGIC        0x11112222UL /* grub_lynxfs_sblock.magic */
#define LYNXFS_BSIZE_MAGIC     0xcafefecaUL /* grub_lynxfs_sblock.bsize_magic */
#define LYNXFS_BITMAP_MAGIC    0x1fedfaceUL /* grub_lynxfs_sblock.bitmap_magic */

/**
 * This is the on-disk inode structure for LynxFS.
 * Inodes start in block 2. Each inode is 128 bytes.
 * All fields are stored big-endian, including the 24-bit iblock values.
 * NOTES:
 *  o If i_uid == 0xffff then the inode is free.
 *  o On the free inode list, the first 4 bytes are the next free inode
 */
struct grub_lynxfs_inode
{
	grub_int16_t  i_mode;           /* node type and mode */
	grub_int16_t  i_nlink;          /* number of hard links to this file */
	grub_uint32_t i_genid;          /* NFS generation count */
	grub_uint16_t i_uid;            /* user id */
	grub_uint16_t i_guid;           /* group id */
	grub_uint32_t i_size;           /* file size (in bytes) */
	grub_uint32_t i_atime;          /* time when file data was last accessed */
	grub_uint32_t i_mtime;          /* time when file data was last modified */
	grub_uint32_t i_ctime;          /* time when file status was last changed */
	grub_uint32_t i_numblocks;      /* actual number of blocks used in file */
	grub_uint8_t  i_blocks[3 * 13]; /* direct and indirect blocks (24 bits) */
};

/**
 * On-disk directory entry structure.
 * It has a 4-byte alignment
 */
struct lynxfs_dirent
{
	grub_int32_t  d_ino;         /* inode number */
	grub_int16_t  d_reclen;      /* on-disk size, including padding (ignore it) */
	grub_int16_t  d_namlen;      /* length of the name */
#define MAX_NAMELEN        (512 - 9)   // a dir entry must fit in 512 bytes
	grub_uint8_t  d_name[0];     /* variable length name follows */
};

struct grub_fshelp_node
{
	struct grub_lynxfs_data* data;
	struct grub_lynxfs_inode inode;
	int                      ino;        // virtual inode
	int                      inode_read; // whether the inode at ino has been read
};

/* Information about a "mounted" ext2 filesystem.  */
struct grub_lynxfs_data
{
	grub_disk_t               disk;
	struct grub_lynxfs_sblock sblock;
	grub_uint32_t             block_size;
	int block_bits;     /* 2^n = block_size (11 => 2048 bytes) */
	grub_uint32_t             num_inodes;
	grub_uint32_t             root_inode_no;  /* the root inode must be 1 */

	struct grub_lynxfs_inode* inode;
	struct grub_fshelp_node   diropen;
};

/**
 * Extracts the 24-bit block number from inode->i_blocks.
 * No checking of the index is done.
 */
static grub_uint32_t
grub_lynxfs_inode_block_read(struct grub_lynxfs_inode* inode, int idx)
{
	grub_uint8_t* p8 = &inode->i_blocks[idx * 3];
	return (((grub_uint32_t)p8[0] << 16) |
		((grub_uint32_t)p8[1] << 8) |
		(grub_uint32_t)p8[2]);
}

/**
 * Finds the physical block number for the fileblock.
 */
static grub_disk_addr_t
grub_lynxfs_read_block(grub_fshelp_node_t node, grub_disk_addr_t fileblock)
{
	struct grub_lynxfs_data* data = node->data;
	struct grub_lynxfs_inode* inode = &node->inode;
	unsigned int             blksz = data->block_size;
	grub_disk_addr_t         blksz_quarter = blksz / 4;
	int                      log2_blksz = LOG2_512_BLOCK_SIZE(data);
	int                      log_perblock = log2_blksz + 9 - 2;
	grub_uint32_t            indir; // big-endian
	int                      shift;

	/* Direct blocks.  */
	if (fileblock < INDIRECT_BLOCKS)
		return grub_lynxfs_inode_block_read(inode, fileblock);
	fileblock -= INDIRECT_BLOCKS;

	/* Indirect.  */
	if (fileblock < blksz_quarter)
	{
		indir = grub_cpu_to_be32(grub_lynxfs_inode_block_read(inode, 10));
		shift = 0;
		goto indirect;
	}
	fileblock -= blksz_quarter;

	/* Double indirect.  */
	if (fileblock < blksz_quarter * blksz_quarter)
	{
		indir = grub_cpu_to_be32(grub_lynxfs_inode_block_read(inode, 11));
		shift = 1;
		goto indirect;
	}
	fileblock -= blksz_quarter * blksz_quarter;

	/* Triple indirect.  */
	if (fileblock < blksz_quarter * blksz_quarter * (blksz_quarter + 1))
	{
		indir = grub_cpu_to_be32(grub_lynxfs_inode_block_read(inode, 12));
		shift = 2;
		goto indirect;
	}
	grub_error(GRUB_ERR_BAD_FS,
		"lynxfs doesn't support quadruple indirect blocks");
	return -1;

indirect:
	do
	{
		/* If the indirect block is zero, all child blocks are absent
		 *       (i.e. filled with zeros.) */
		if (indir == 0)
			return 0;
		if (grub_disk_read(data->disk,
			((grub_disk_addr_t)grub_be_to_cpu32(indir)) << log2_blksz,
			((fileblock >> (log_perblock * shift)) & ((1 << log_perblock) - 1)) * sizeof(
				indir),
			sizeof(indir), &indir))
			return -1;
	} while (shift--);

	return grub_be_to_cpu32(indir);
}

/* 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_lynxfs_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)
{
	return grub_fshelp_read_file(node->data->disk, node,
		read_hook, read_hook_data,
		pos, len, buf,
		grub_lynxfs_read_block,
		grub_be_to_cpu32(node->inode.i_size),
		LOG2_512_BLOCK_SIZE(node->data), 0);
}

/* Read the inode INO for the file described by DATA into INODE.  */
static grub_err_t
grub_lynxfs_read_inode(struct grub_lynxfs_data* data,
	grub_uint32_t ino, struct grub_lynxfs_inode* inode)
{
	int blk_num, blk_off;
	int reloff;

	/* Make sure the inode is valid */
	if ((ino < 1) || (ino > data->num_inodes))
		return GRUB_ERR_FILE_NOT_FOUND;
	reloff = ((ino - 1) * 128); /* relative offset in inode area */
	blk_num = (2 + (reloff >> data->block_bits)) << (data->block_bits - 9);
	blk_off = reloff & (data->block_size - 1);

	if (grub_disk_read(data->disk, blk_num, blk_off, sizeof(*inode), inode))
		return grub_errno;
	return 0;
}

static struct grub_lynxfs_data*
grub_lynxfs_mount(grub_disk_t disk)
{
	struct grub_lynxfs_data* data;
	struct grub_lynxfs_sblock* sb;

	data = grub_malloc(sizeof(*data));
	if (!data)
		return 0;
	sb = &data->sblock;

	/* Read the root superblock, which starts at ofset 512 */
	grub_disk_read(disk, 1, 0, sizeof(*sb), sb);
	if (grub_errno)
		goto fail;

	/* check the magic codes to see if this is a LynxFS partition */
	if ((sb->magic != grub_cpu_to_be32_compile_time(LYNXFS_SB_MAGIC)) ||
		(sb->bsize_magic != grub_cpu_to_be32_compile_time(LYNXFS_BSIZE_MAGIC)))
	{
		grub_error(GRUB_ERR_BAD_FS, "not an lynxfs filesystem");
		goto fail;
	}

	/* Grab the block size and calculate the number of bits */
	data->block_size = grub_be_to_cpu32(sb->bsize_code);
	data->block_bits = 0;
	{
		int tmp = data->block_size;
		while ((tmp >>= 1) > 0)
			data->block_bits++;
	}

	/* Now read the REAL superblock from block 1 */
	grub_disk_read(disk, data->block_size / 512, 0, sizeof(*sb), sb);
	if (grub_errno)
		goto fail;

	/* Sanity check */
	if ((sb->magic != grub_cpu_to_be32_compile_time(LYNXFS_SB_MAGIC)) ||
		(sb->bsize_magic != grub_cpu_to_be32_compile_time(LYNXFS_BSIZE_MAGIC)) ||
		(sb->bitmap_magic != grub_cpu_to_be32_compile_time(LYNXFS_BITMAP_MAGIC)))
	{
		grub_error(GRUB_ERR_BAD_FS, "not an lynxfs filesystem");
		goto fail;
	}

	/* Extract static (fixed) SuperBlock data */
	data->root_inode_no = grub_be_to_cpu32(sb->root_inode);
	data->num_inodes = grub_be_to_cpu32(sb->num_inodes);

	data->disk = disk;

	// open the root inode
	data->diropen.data = data;
	data->diropen.ino = data->root_inode_no;
	data->diropen.inode_read = 1;
	data->inode = &data->diropen.inode;

	grub_lynxfs_read_inode(data, data->root_inode_no, data->inode);
	if (grub_errno)
		goto fail;
	return data;

fail:
	if (grub_errno == GRUB_ERR_OUT_OF_RANGE)
		grub_error(GRUB_ERR_BAD_FS, "not an lynxfs filesystem");
	grub_free(data);
	return NULL;
}

static char*
grub_lynxfs_read_symlink(grub_fshelp_node_t node)
{
	char* symlink;
	struct grub_fshelp_node* diro = node;

	if (!diro->inode_read)
	{
		grub_lynxfs_read_inode(diro->data, diro->ino, &diro->inode);
		if (grub_errno)
			return 0;
	}
	grub_uint32_t i_size = grub_be_to_cpu32(diro->inode.i_size);

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

	grub_lynxfs_read_file(diro, 0, 0, 0, i_size, symlink);
	if (grub_errno)
	{
		grub_free(symlink);
		return 0;
	}
	symlink[i_size] = '\0';
	return symlink;
}

static int
grub_lynxfs_iterate_dir(grub_fshelp_node_t dir,
	grub_fshelp_iterate_dir_hook_t hook, void* hook_data)
{
	unsigned int fpos = 0;
	struct grub_fshelp_node* diro = (struct grub_fshelp_node*)dir;

	if (!diro->inode_read)
	{
		grub_lynxfs_read_inode(diro->data, diro->ino, &diro->inode);
		if (grub_errno)
			return 0;
	}
	grub_uint32_t i_size = grub_be_to_cpu32(diro->inode.i_size);

	/* Search the file.  */
	while (fpos < i_size)
	{
		struct lynxfs_dirent dirent;

		grub_lynxfs_read_file(diro, 0, 0, fpos, sizeof(dirent), (char*)&dirent);
		if (grub_errno)
			return 0;

		grub_uint32_t d_ino = grub_be_to_cpu32(dirent.d_ino);
		grub_int16_t  d_namlen = grub_be_to_cpu16(dirent.d_namlen);
		grub_int16_t  d_reclen = grub_be_to_cpu16(dirent.d_reclen);

		/* a reclen of 0 would cause issues, as we cannot continue the loop */
		if (d_reclen == 0)
			return 0;

		if (d_ino != 0 && d_namlen != 0 && d_namlen <= MAX_NAMELEN)
		{
			char filename[MAX_NAMELEN + 1];
			struct grub_fshelp_node* fdiro;
			enum grub_fshelp_filetype type = GRUB_FSHELP_UNKNOWN;

			grub_lynxfs_read_file(diro, 0, 0, fpos + sizeof(struct lynxfs_dirent),
				d_namlen, filename);
			if (grub_errno)
				return 0;
			filename[d_namlen] = '\0';

			fdiro = grub_malloc(sizeof(*fdiro));
			if (!fdiro)
				return 0;

			fdiro->data = diro->data;
			fdiro->ino = d_ino;

			grub_lynxfs_read_inode(diro->data, d_ino, &fdiro->inode);
			if (grub_errno)
			{
				grub_free(fdiro);
				return 0;
			}
			fdiro->inode_read = 1;

			grub_uint16_t i_mode = grub_be_to_cpu16(fdiro->inode.i_mode);
			if ((i_mode & FILETYPE_INO_MASK) == FILETYPE_INO_DIRECTORY)
				type = GRUB_FSHELP_DIR;
			else if ((i_mode & FILETYPE_INO_MASK) == FILETYPE_INO_SYMLINK)
				type = GRUB_FSHELP_SYMLINK;
			else if ((i_mode & FILETYPE_INO_MASK) == FILETYPE_INO_REG)
				type = GRUB_FSHELP_REG;

			if (hook(filename, type, fdiro, hook_data))
				return 1;
		}
		fpos += d_reclen;
	}

	return 0;
}

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

	data = grub_lynxfs_mount(file->disk);
	if (!data)
	{
		err = grub_errno;
		goto fail;
	}

	err = grub_fshelp_find_file(name, &data->diropen, &fdiro,
		grub_lynxfs_iterate_dir,
		grub_lynxfs_read_symlink,
		GRUB_FSHELP_REG);
	if (err)
		goto fail;

	if (!fdiro->inode_read)
	{
		err = grub_lynxfs_read_inode(data, fdiro->ino, &fdiro->inode);
		if (err)
			goto fail;
	}

	grub_memcpy(data->inode, &fdiro->inode, sizeof(*data->inode));
	data->diropen.ino = fdiro->ino;
	grub_free(fdiro);

	file->size = grub_be_to_cpu32(data->inode->i_size);
	file->data = data;
	file->offset = 0;

	return 0;

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

static grub_err_t
grub_lynxfs_close(grub_file_t file)
{
	grub_free(file->data);
	return GRUB_ERR_NONE;
}

/* Read LEN bytes data from FILE into BUF.  */
static grub_ssize_t
grub_lynxfs_read(grub_file_t file, char* buf, grub_size_t len)
{
	struct grub_lynxfs_data* data = (struct grub_lynxfs_data*)file->data;

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

/* Context for grub_lynxfs_dir.  */
struct grub_lynxfs_dir_ctx
{
	grub_fs_dir_hook_t      hook;
	void* hook_data;
	struct grub_lynxfs_data* data;
};

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

	grub_memset(&info, 0, sizeof(info));
	if (!node->inode_read)
	{
		grub_lynxfs_read_inode(ctx->data, node->ino, &node->inode);
		if (!grub_errno)
			node->inode_read = 1;
		grub_errno = GRUB_ERR_NONE;
	}
	if (node->inode_read)
	{
		info.mtimeset = 1;
		info.mtime = grub_be_to_cpu32(node->inode.i_mtime);
	}

	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_lynxfs_dir(grub_disk_t disk, const char* path, grub_fs_dir_hook_t hook,
	void* hook_data)
{
	struct grub_lynxfs_dir_ctx ctx =
	{
		.hook = hook,
		.hook_data = hook_data
	};
	struct grub_fshelp_node* fdiro = 0;

	ctx.data = grub_lynxfs_mount(disk);
	if (!ctx.data)
		goto fail;

	grub_fshelp_find_file(path, &ctx.data->diropen, &fdiro,
		grub_lynxfs_iterate_dir, grub_lynxfs_read_symlink,
		GRUB_FSHELP_DIR);
	if (grub_errno)
		goto fail;

	grub_lynxfs_iterate_dir(fdiro, grub_lynxfs_dir_iter, &ctx);

fail:
	if (fdiro != &ctx.data->diropen)
		grub_free(fdiro);
	grub_free(ctx.data);
	return grub_errno;
}

static struct grub_fs grub_lynxfs_fs =
{
	.name = "lynxfs",
	.fs_dir = grub_lynxfs_dir,
	.fs_open = grub_lynxfs_open,
	.fs_read = grub_lynxfs_read,
	.fs_close = grub_lynxfs_close,
	.next = 0
};

GRUB_MOD_INIT(lynxfs)
{
	grub_fs_register(&grub_lynxfs_fs);
}

GRUB_MOD_FINI(lynxfs)
{
	grub_fs_unregister(&grub_lynxfs_fs);
}
