/*
 *  linux/fs/hpfs/hpfs_fs.c
 *  read-only HPFS
 *  version 1.0
 *
 *  Chris Smith 1993
 *
 *  Sources & references:
 *   Duncan, _Design ... of HPFS_, MSJ 4(5)   (C) 1989 Microsoft Corp
 *   linux/fs/minix  Copyright (C) 1991, 1992, 1993  Linus Torvalds
 *   linux/fs/msdos  Written 1992, 1993 by Werner Almesberger
 *   linux/fs/isofs  Copyright (C) 1991  Eric Youngdale
 */

#include <linux/fs.h>
#include <linux/hpfs_fs.h>
#include <linux/errno.h>
#include <linux/malloc.h>
#include <linux/sched.h>
#include <linux/locks.h>
#include <linux/stat.h>
#include <linux/string.h>
#include <asm/bitops.h>
#include <asm/segment.h>

#include "hpfs.h"

/* 
 * HPFS is a mixture of 512-byte blocks and 2048-byte blocks.  The 2k blocks
 * are used for directories and bitmaps.  For bmap to work, we must run the
 * file system with 512-byte blocks.  The 2k blocks are assembled in buffers
 * obtained from kmalloc.
 *
 * For a file's i-number we use the sector number of its fnode, coded.
 * (Directory ino's are even, file ino's are odd, and ino >> 1 is the
 * sector address of the fnode.  This is a hack to allow lookup() to
 * tell read_inode() whether it is necessary to read the fnode.)
 *
 * The map_xxx routines all read something into a buffer and return a
 * pointer somewhere in the buffer.  The caller must do the brelse.
 * The other routines are balanced.
 *
 * For details on the data structures see hpfs.h and the Duncan paper.
 *
 * Overview
 *
 * [ The names of these data structures, except fnode, are not Microsoft's
 * or IBM's.  I don't know what names they use.  The semantics described
 * here are those of this implementation, and any coincidence between it
 * and real HPFS is to be hoped for but not guaranteed by me, and
 * certainly not guaranteed by MS or IBM.  Who know nothing about this. ]
 *
 * [ Also, the following will make little sense if you haven't read the
 * Duncan paper, which is excellent. ]
 *
 * HPFS is a tree.  There are 3 kinds of nodes.  A directory is a tree
 * of dnodes, and a file's allocation info is a tree of sector runs
 * stored in fnodes and anodes.
 *
 * The top pointer is in the super block, it points to the fnode of the
 * root directory.
 *
 * The root directory -- all directories -- gives file names, dates &c,
 * and fnode addresses.  If the directory fits in one dnode, that's it,
 * otherwise the top dnode points to other dnodes, forming a tree.  A
 * dnode tree (one directory) might look like
 *
 *     ((a b c) d (e f g) h (i j) k l (m n o p))
 *
 * The subtrees appear between the files.  Each dir entry contains, along
 * with the name and fnode, a dnode pointer to the subtree that precedes it
 * (if there is one; a flag tells that).  The first entry in every directory
 * is ^A^A, the "." entry for the directory itself.  The last entry in every
 * dnode is \377, a fake entry whose only valid fields are the bit marking
 * it last and the down pointer to the subtree preceding it, if any.
 *
 * The "value" field of directory entries is an fnode address.  The fnode
 * tells where the sectors of the file are.  The fnode for a subdirectory
 * contains one pointer, to the root dnode of the subdirectory.  The fnode
 * for a data file contains, in effect, a tiny anode.  (Most of the space
 * in fnodes is for extended attributes.)
 *
 * anodes and the anode part of fnodes are trees of extents.  An extent
 * is a (length, disk address) pair, labeled with the file address being
 * mapped.  E.g.,
 *
 *     (0: 3@1000  3: 1@2000  4: 2@10)
 *
 * means the file:disk sector map (0:1000 1:1001 2:1002 3:2000 4:10 5:11).
 *
 * There is space for 8 file:len@disk triples in an fnode, or for 40 in an
 * anode.  If this is insufficient, subtrees are used, as in
 *
 *  (6: (0: 3@1000  3: 1@2000  4: 2@10)  12: (6: 3@8000  9: 1@9000  10: 2@20))
 *
 * The label on a subtree is the first address *after* that tree.  The
 * subtrees are always anodes.  The label:subtree pairs require only
 * two words each, so non-leaf subtrees have a different format; there
 * is room for 12 label:subtree pairs in an fnode, or 60 in an anode.
 *
 * Within a directory, each dnode contains a pointer up to its parent
 * dnode.  The root dnode points up to the directory's fnode.
 *
 * Each fnode contains a pointer to the directory that contains it
 * (to the fnode of the directory).  So this pointer in a directory
 * fnode is "..".
 *
 * On the disk, dnodes are all together in the center of the partition,
 * and HPFS even manages to put all the dnodes for a single directory
 * together, generally.  fnodes are out with the data.  anodes are seldom
 * seen -- in fact noncontiguous files are seldom seen.  I think this is
 * partly the open() call that lets programs specify the length of an
 * output file when they know it, and partly because HPFS.IFS really is
 * very good at resisting fragmentation. 
 */

/* notation */

#define little_ushort(x) (*(unsigned short *) &(x))
typedef void nonconst;

/* super block ops */

static void hpfs_read_inode(struct inode *);
static void hpfs_put_super(struct super_block *);
static void hpfs_statfs(struct super_block *, struct statfs *);
static int hpfs_remount_fs(struct super_block *, int *, char *);

static const struct super_operations hpfs_sops =
{
	hpfs_read_inode,		/* read_inode */
	NULL,				/* notify_change */
	NULL,				/* write_inode */
	NULL,				/* put_inode */
	hpfs_put_super,			/* put_super */
	NULL,				/* write_super */
	hpfs_statfs,			/* statfs */
	hpfs_remount_fs,		/* remount_fs */
};

/* file ops */

static int hpfs_file_read(struct inode *, struct file *, char *, int);
static secno hpfs_bmap(struct inode *, unsigned);

static const struct file_operations hpfs_file_ops =
{
	NULL,				/* lseek - default */
	hpfs_file_read,			/* read */
	NULL,				/* write */
	NULL,				/* readdir - bad */
	NULL,				/* select - default */
	NULL,				/* ioctl - default */
	generic_mmap,			/* mmap */
	NULL,				/* no special open is needed */
	NULL,				/* release */
	file_fsync,			/* fsync */
};

static const struct inode_operations hpfs_file_iops =
{
	(nonconst *) & hpfs_file_ops,	/* default file operations */
	NULL,				/* create */
	NULL,				/* lookup */
	NULL,				/* link */
	NULL,				/* unlink */
	NULL,				/* symlink */
	NULL,				/* mkdir */
	NULL,				/* rmdir */
	NULL,				/* mknod */
	NULL,				/* rename */
	NULL,				/* readlink */
	NULL,				/* follow_link */
	(int (*)(struct inode *, int))
	&hpfs_bmap,			/* bmap */
	NULL,				/* truncate */
	NULL,				/* permission */
};

/* directory ops */

static int hpfs_dir_read(struct inode *inode, struct file *filp,
			 char *buf, int count);
static int hpfs_readdir(struct inode *inode, struct file *filp,
			struct dirent *dirent, int count);
static int hpfs_lookup(struct inode *, const char *, int, struct inode **);

static const struct file_operations hpfs_dir_ops =
{
	NULL,				/* lseek - default */
	hpfs_dir_read,			/* read */
	NULL,				/* write - bad */
	hpfs_readdir,			/* readdir */
	NULL,				/* select - default */
	NULL,				/* ioctl - default */
	NULL,				/* mmap */
	NULL,				/* no special open code */
	NULL,				/* no special release code */
	file_fsync,			/* fsync */
};

static const struct inode_operations hpfs_dir_iops =
{
	(nonconst *) & hpfs_dir_ops,	/* default directory file ops */
	NULL,				/* create */
	hpfs_lookup,			/* lookup */
	NULL,				/* link */
	NULL,				/* unlink */
	NULL,				/* symlink */
	NULL,				/* mkdir */
	NULL,				/* rmdir */
	NULL,				/* mknod */
	NULL,				/* rename */
	NULL,				/* readlink */
	NULL,				/* follow_link */
	NULL,				/* bmap */
	NULL,				/* truncate */
	NULL,				/* permission */
};

/* Four 512-byte buffers and the 2k block obtained by concatenating them */

struct quad_buffer_head {
	struct buffer_head *bh[4];
	void *data;
};

/* forwards */

static int parse_opts(char *opts, uid_t *uid, gid_t *gid, umode_t *umask,
		      int *lowercase, int *conv);
static int check_warn(int not_ok,
		      const char *p1, const char *p2, const char *p3);
static int zerop(void *addr, unsigned len);
static void count_dnodes(struct inode *inode, dnode_secno dno,
			 unsigned *n_dnodes, unsigned *n_subdirs);
static unsigned count_bitmap(struct super_block *s);
static unsigned count_one_bitmap(dev_t dev, secno secno);
static secno bplus_lookup(struct inode *inode, struct bplus_header *b,
			  secno file_secno, struct buffer_head **bhp);
static struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno,
				    const unsigned char *name, unsigned len,
				      struct quad_buffer_head *qbh);
static struct hpfs_dirent *map_pos_dirent(struct inode *inode, off_t *posp,
					  struct quad_buffer_head *qbh);
static void write_one_dirent(struct dirent *dirent, const unsigned char *name,
			     unsigned namelen, ino_t ino, int lowercase);
static dnode_secno dir_subdno(struct inode *inode, unsigned pos);
static struct hpfs_dirent *map_nth_dirent(dev_t dev, dnode_secno dno,
					  int n,
					  struct quad_buffer_head *qbh);
static unsigned choose_conv(unsigned char *p, unsigned len);
static unsigned convcpy_tofs(unsigned char *out, unsigned char *in,
			     unsigned len);
static dnode_secno fnode_dno(dev_t dev, ino_t ino);
static struct fnode *map_fnode(dev_t dev, ino_t ino,
			       struct buffer_head **bhp);
static struct anode *map_anode(dev_t dev, unsigned secno,
			       struct buffer_head **bhp);
static struct dnode *map_dnode(dev_t dev, unsigned secno,
			       struct quad_buffer_head *qbh);
static void *map_sector(dev_t dev, unsigned secno, struct buffer_head **bhp);
static void *map_4sectors(dev_t dev, unsigned secno,
			  struct quad_buffer_head *qbh);
static void brelse4(struct quad_buffer_head *qbh);

/*
 * make inode number for a file
 */

static inline ino_t file_ino(fnode_secno secno)
{
	return secno << 1 | 1;
}

/*
 * make inode number for a directory
 */

static inline ino_t dir_ino(fnode_secno secno)
{
	return secno << 1;
}

/*
 * get fnode address from an inode number
 */

static inline fnode_secno ino_secno(ino_t ino)
{
	return ino >> 1;
}

/*
 * test for directory's inode number 
 */

static inline int ino_is_dir(ino_t ino)
{
	return (ino & 1) == 0;
}

/*
 * conv= options
 */

#define CONV_BINARY 0			/* no conversion */
#define CONV_TEXT 1			/* crlf->newline */
#define CONV_AUTO 2			/* decide based on file contents */

/*
 * local time (HPFS) to GMT (Unix)
 */

static inline time_t local_to_gmt(time_t t)
{
	extern struct timezone sys_tz;
	return t + sys_tz.tz_minuteswest * 60;
}

/* super block ops */

/*
 * mount.  This gets one thing, the root directory inode.  It does a
 * bunch of guessed-at consistency checks.
 */

struct super_block *hpfs_read_super(struct super_block *s,
				    void *options, int silent)
{
	struct hpfs_boot_block *bootblock;
	struct hpfs_super_block *superblock;
	struct hpfs_spare_block *spareblock;
	struct hpfs_dirent *de;
	struct buffer_head *bh0, *bh1, *bh2;
	struct quad_buffer_head qbh;
	dnode_secno root_dno;
	dev_t dev;
	uid_t uid;
	gid_t gid;
	umode_t umask;
	int lowercase;
	int conv;
	int dubious;

	/*
	 * Get the mount options
	 */

	if (!parse_opts(options, &uid, &gid, &umask, &lowercase, &conv)) {
		printk("HPFS: syntax error in mount options.  Not mounted.\n");
		s->s_dev = 0;
		return 0;
	}

	/*
	 * Fill in the super block struct
	 */

	lock_super(s);
	dev = s->s_dev;
	set_blocksize(dev, 512);

	/*
	 * fetch sectors 0, 16, 17
	 */

	bootblock = map_sector(dev, 0, &bh0);
	if (!bootblock)
		goto bail;

	superblock = map_sector(dev, 16, &bh1);
	if (!superblock)
		goto bail0;

	spareblock = map_sector(dev, 17, &bh2);
	if (!spareblock)
		goto bail1;

	/*
	 * Check that this fs looks enough like a known one that we can find
	 * and read the root directory.
	 */

	if (bootblock->magic != 0xaa55
	    || superblock->magic != SB_MAGIC
	    || spareblock->magic != SP_MAGIC
	    || bootblock->sig_28h != 0x28
	    || memcmp(&bootblock->sig_hpfs, "HPFS    ", 8)
	    || little_ushort(bootblock->bytes_per_sector) != 512) {
		printk("HPFS: hpfs_read_super: Not HPFS\n");
		goto bail2;
	}

	/*
	 * Check for inconsistencies -- possibly wrong guesses here, possibly
	 * filesystem problems.
	 */

	dubious = 0;

	dubious |= check_warn(spareblock->dirty != 0,
		       "`Improperly stopped'", "flag is set", "run CHKDSK");
	dubious |= check_warn(spareblock->n_spares_used != 0,
			      "Spare blocks", "may be in use", "run CHKDSK");

	/*
	 * Above errors mean we could get wrong answers if we proceed,
	 * so don't
	 */

	if (dubious)
		goto bail2;

	dubious |= check_warn((spareblock->n_dnode_spares !=
			       spareblock->n_dnode_spares_free),
			      "Spare dnodes", "may be in use", "run CHKDSK");
	dubious |= check_warn(superblock->zero1 != 0,
			      "#1", "unknown word nonzero", "investigate");
	dubious |= check_warn(superblock->zero3 != 0,
			      "#3", "unknown word nonzero", "investigate");
	dubious |= check_warn(superblock->zero4 != 0,
			      "#4", "unknown word nonzero", "investigate");
	dubious |= check_warn(!zerop(superblock->zero5,
				     sizeof superblock->zero5),
			      "#5", "unknown word nonzero", "investigate");
	dubious |= check_warn(!zerop(superblock->zero6,
				     sizeof superblock->zero6),
			      "#6", "unknown word nonzero", "investigate");

	if (dubious)
		printk("HPFS: Proceeding, but operation may be unreliable\n");

	/*
	 * set fs read only
	 */

	s->s_flags |= MS_RDONLY;

	/*
	 * fill in standard stuff
	 */

	s->s_magic = HPFS_SUPER_MAGIC;
	s->s_blocksize = 512;
	s->s_blocksize_bits = 9;
	s->s_op = (struct super_operations *) &hpfs_sops;

	/*
	 * fill in hpfs stuff
	 */

	s->s_hpfs_root = dir_ino(superblock->root);
	s->s_hpfs_fs_size = superblock->n_sectors;
	s->s_hpfs_dirband_size = superblock->n_dir_band / 4;
	s->s_hpfs_dmap = superblock->dir_band_bitmap;
	s->s_hpfs_bitmaps = superblock->bitmaps;
	s->s_hpfs_uid = uid;
	s->s_hpfs_gid = gid;
	s->s_hpfs_mode = 0777 & ~umask;
	s->s_hpfs_n_free = -1;
	s->s_hpfs_n_free_dnodes = -1;
	s->s_hpfs_lowercase = lowercase;
	s->s_hpfs_conv = conv;

	/*
	 * done with the low blocks
	 */

	brelse(bh2);
	brelse(bh1);
	brelse(bh0);

	/*
	 * all set.  try it out.
	 */

	s->s_mounted = iget(s, s->s_hpfs_root);
	unlock_super(s);

	if (!s->s_mounted) {
		printk("HPFS: hpfs_read_super: inode get failed\n");
		s->s_dev = 0;
		return 0;
	}

	/*
	 * find the root directory's . pointer & finish filling in the inode
	 */

	root_dno = fnode_dno(dev, s->s_hpfs_root);
	if (root_dno)
		de = map_dirent(s->s_mounted, root_dno, "\001\001", 2, &qbh);
	if (!root_dno || !de) {
		printk("HPFS: "
		       "hpfs_read_super: root dir isn't in the root dir\n");
		s->s_dev = 0;
		return 0;
	}

	s->s_mounted->i_atime = local_to_gmt(de->read_date);
	s->s_mounted->i_mtime = local_to_gmt(de->write_date);
	s->s_mounted->i_ctime = local_to_gmt(de->creation_date);

	brelse4(&qbh);
	return s;

 bail2:
	brelse(bh2);
 bail1:
	brelse(bh1);
 bail0:
	brelse(bh0);
 bail:
	s->s_dev = 0;
	unlock_super(s);
	return 0;
}

static int check_warn(int not_ok,
		      const char *p1, const char *p2, const char *p3)
{
	if (not_ok)
		printk("HPFS: %s %s. Please %s\n", p1, p2, p3);
	return not_ok;
}

static int zerop(void *addr, unsigned len)
{
	unsigned char *p = addr;
	return p[0] == 0 && memcmp(p, p + 1, len - 1) == 0;
}

/*
 * A tiny parser for option strings, stolen from dosfs.
 */

static int parse_opts(char *opts, uid_t *uid, gid_t *gid, umode_t *umask,
		      int *lowercase, int *conv)
{
	char *p, *rhs;

	*uid = current->uid;
	*gid = current->gid;
	*umask = current->umask;
	*lowercase = 1;
	*conv = CONV_BINARY;

	if (!opts)
		return 1;

	for (p = strtok(opts, ","); p != 0; p = strtok(0, ",")) {
		if ((rhs = strchr(p, '=')) != 0)
			*rhs++ = '\0';
		if (!strcmp(p, "uid")) {
			if (!rhs || !*rhs)
				return 0;
			*uid = simple_strtoul(rhs, &rhs, 0);
			if (*rhs)
				return 0;
		}
		else if (!strcmp(p, "gid")) {
			if (!rhs || !*rhs)
				return 0;
			*gid = simple_strtoul(rhs, &rhs, 0);
			if (*rhs)
				return 0;
		}
		else if (!strcmp(p, "umask")) {
			if (!rhs || !*rhs)
				return 0;
			*umask = simple_strtoul(rhs, &rhs, 8);
			if (*rhs)
				return 0;
		}