/*
 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2009, 2013
 *	The President and Fellows of Harvard College.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <err.h>

#include "compat.h"
#include <kern/sfs.h>

#include "disk.h"
#include "utils.h"
#include "ibmacros.h"
#include "sfs.h"
#include "sb.h"
#include "freemap.h"
#include "inode.h"
#include "passes.h"
#include "main.h"

static unsigned long count_dirs=0, count_files=0;

/*
 * State for checking indirect blocks.
 */
struct ibstate {
	uint32_t ino;		/* inode we're doing (constant) */
	uint32_t curfileblock;	/* current block offset in the file */
	uint32_t fileblocks;	/* file size in blocks (constant) */
	uint32_t volblocks;	/* volume size in blocks (constant) */
	unsigned pasteofcount;	/* number of blocks found past eof */
	blockusage_t usagetype;	/* how to call freemap_blockinuse() */
};

/*
 * Traverse an indirect block, recording blocks that are in use,
 * dropping any entries that are past EOF, and clearing any entries
 * that point outside the volume.
 *
 * XXX: this should be extended to be able to recover from crosslinked
 * blocks. Currently it just complains in freemap.c and sets
 * EXIT_UNRECOV.
 *
 * The traversal is recursive; the state is maintained in IBS (as
 * described above). IENTRY is a pointer to the entry in the parent
 * indirect block (or the inode) that names the block we're currently
 * scanning. IECHANGEDP should be set to 1 if *IENTRY is changed.
 * INDIRECTION is the indirection level of this block (1, 2, or 3).
 */
static
void
check_indirect_block(struct ibstate *ibs, uint32_t *ientry, int *iechangedp,
		     int indirection)
{
	uint32_t entries[SFS_DBPERIDB];
	uint32_t i, ct;
	uint32_t coveredblocks;
	int localchanged = 0;
	int j;

	if (*ientry > 0 && *ientry < ibs->volblocks) {
		sfs_readindirect(*ientry, entries);
		freemap_blockinuse(*ientry, B_IBLOCK, ibs->ino);
	}
	else {
		if (*ientry >= ibs->volblocks) {
			setbadness(EXIT_RECOV);
			warnx("Inode %lu: indirect block pointer (level %d) "
			      "for block %lu outside of volume: %lu "
			      "(cleared)\n",
			      (unsigned long)ibs->ino, indirection,
			      (unsigned long)ibs->curfileblock,
			      (unsigned long)*ientry);
			*ientry = 0;
			*iechangedp = 1;
		}
		coveredblocks = 1;
		for (j=0; j<indirection; j++) {
			coveredblocks *= SFS_DBPERIDB;
		}
		ibs->curfileblock += coveredblocks;
		return;
	}

	if (indirection > 1) {
		for (i=0; i<SFS_DBPERIDB; i++) {
			check_indirect_block(ibs, &entries[i], &localchanged,
					     indirection-1);
		}
	}
	else {
		assert(indirection==1);

		for (i=0; i<SFS_DBPERIDB; i++) {
			if (entries[i] >= ibs->volblocks) {
				setbadness(EXIT_RECOV);
				warnx("Inode %lu: direct block pointer for "
				      "block %lu outside of volume: %lu "
				      "(cleared)\n",
				      (unsigned long)ibs->ino,
				      (unsigned long)ibs->curfileblock,
				      (unsigned long)entries[i]);
				entries[i] = 0;
				localchanged = 1;
			}
			else if (entries[i] != 0) {
				if (ibs->curfileblock < ibs->fileblocks) {
					freemap_blockinuse(entries[i],
							  ibs->usagetype,
							  ibs->ino);
				}
				else {
					setbadness(EXIT_RECOV);
					ibs->pasteofcount++;
					freemap_blockfree(entries[i]);
					entries[i] = 0;
					localchanged = 1;
				}
			}
			ibs->curfileblock++;
		}
	}

	ct=0;
	for (i=ct=0; i<SFS_DBPERIDB; i++) {
		if (entries[i]!=0) ct++;
	}
	if (ct==0) {
		if (*ientry != 0) {
			setbadness(EXIT_RECOV);
			/* this is not necessarily correct */
			/*ibs->pasteofcount++;*/
			*iechangedp = 1;
			freemap_blockfree(*ientry);
			*ientry = 0;
		}
	}
	else {
		assert(*ientry != 0);
		if (localchanged) {
			sfs_writeindirect(*ientry, entries);
		}
	}
}

/*
 * Check the blocks belonging to inode INO, whose inode has already
 * been loaded into SFI. ISDIR is a shortcut telling us if the inode
 * is a directory.
 *
 * Returns nonzero if SFI has been modified and needs to be written
 * back.
 */
static
int
check_inode_blocks(uint32_t ino, struct sfs_dinode *sfi, int isdir)
{
	struct ibstate ibs;
	uint32_t size, datablock;
	int changed;
	int i;

	size = SFS_ROUNDUP(sfi->sfi_size, SFS_BLOCKSIZE);

	ibs.ino = ino;
	/*ibs.curfileblock = 0;*/
	ibs.fileblocks = size/SFS_BLOCKSIZE;
	ibs.volblocks = sb_totalblocks();
	ibs.pasteofcount = 0;
	ibs.usagetype = isdir ? B_DIRDATA : B_DATA;

	changed = 0;

	for (ibs.curfileblock=0; ibs.curfileblock<NUM_D; ibs.curfileblock++) {
		datablock = GET_D(sfi, ibs.curfileblock);
		if (datablock >= ibs.volblocks) {
			setbadness(EXIT_RECOV);
			warnx("Inode %lu: direct block pointer for "
			      "block %lu outside of volume: %lu "
			      "(cleared)\n",
			      (unsigned long)ibs.ino,
			      (unsigned long)ibs.curfileblock,
			      (unsigned long)datablock);
			SET_D(sfi, ibs.curfileblock) = 0;
			changed = 1;
		}
		else if (datablock > 0) {
			if (ibs.curfileblock < ibs.fileblocks) {
				freemap_blockinuse(datablock, ibs.usagetype,
						   ibs.ino);
			}
			else {
				setbadness(EXIT_RECOV);
				ibs.pasteofcount++;
				changed = 1;
				freemap_blockfree(datablock);
				SET_D(sfi, ibs.curfileblock) = 0;
			}
		}
	}

	for (i=0; i<NUM_I; i++) {
		check_indirect_block(&ibs, &SET_I(sfi, i), &changed, 1);
	}
	for (i=0; i<NUM_II; i++) {
		check_indirect_block(&ibs, &SET_II(sfi, i), &changed, 2);
	}
	for (i=0; i<NUM_III; i++) {
		check_indirect_block(&ibs, &SET_III(sfi, i), &changed, 3);
	}

	if (ibs.pasteofcount > 0) {
		warnx("Inode %lu: %u blocks after EOF (freed)",
		     (unsigned long) ibs.ino, ibs.pasteofcount);
		setbadness(EXIT_RECOV);
	}

	return changed;
}

/*
 * Do the pass1 inode-level checks on inode INO, which has already
 * been loaded into SFI. Note that sfi_type has already been
 * validated.
 *
 * Returns nonzero if SFI has been modified and needs to be written
 * back.
 */
static
int
pass1_inode(uint32_t ino, struct sfs_dinode *sfi, int alreadychanged)
{
	int changed = alreadychanged;
	int isdir = sfi->sfi_type == SFS_TYPE_DIR;

	if (inode_add(ino, sfi->sfi_type)) {
		/* Already been here. */
		assert(changed == 0);
		return 1;
	}

	freemap_blockinuse(ino, B_INODE, ino);

	if (checkzeroed(sfi->sfi_waste, sizeof(sfi->sfi_waste))) {
		warnx("Inode %lu: sfi_waste section not zeroed (fixed)",
		      (unsigned long) ino);
		setbadness(EXIT_RECOV);
		changed = 1;
	}

	if (check_inode_blocks(ino, sfi, isdir)) {
		changed = 1;
	}

	if (changed) {
		sfs_writeinode(ino, sfi);
	}
	return 0;
}

/*
 * Check the directory entry in SFD. INDEX is its offset, and PATH is
 * its name; these are used for printing messages.
 */
static
int
pass1_direntry(const char *path, uint32_t index, struct sfs_direntry *sfd)
{
	int dchanged = 0;
	uint32_t nblocks;

	nblocks = sb_totalblocks();

	if (sfd->sfd_ino == SFS_NOINO) {
		if (sfd->sfd_name[0] != 0) {
			setbadness(EXIT_RECOV);
			warnx("Directory %s entry %lu has name but no file",
			      path, (unsigned long) index);
			sfd->sfd_name[0] = 0;
			dchanged = 1;
		}
	}
	else if (sfd->sfd_ino >= nblocks) {
		setbadness(EXIT_RECOV);
		warnx("Directory %s entry %lu has out of range "
		      "inode (cleared)",
		      path, (unsigned long) index);
		sfd->sfd_ino = SFS_NOINO;
		sfd->sfd_name[0] = 0;
		dchanged = 1;
	}
	else {
		if (sfd->sfd_name[0] == 0) {
			/* XXX: what happens if FSCK.n.m already exists? */
			snprintf(sfd->sfd_name, sizeof(sfd->sfd_name),
				 "FSCK.%lu.%lu",
				 (unsigned long) sfd->sfd_ino,
				 (unsigned long) uniqueid());
			setbadness(EXIT_RECOV);
			warnx("Directory %s entry %lu has file but "
			      "no name (fixed: %s)",
			      path, (unsigned long) index,
			      sfd->sfd_name);
			dchanged = 1;
		}
		if (checknullstring(sfd->sfd_name, sizeof(sfd->sfd_name))) {
			setbadness(EXIT_RECOV);
			warnx("Directory %s entry %lu not "
			      "null-terminated (fixed)",
			      path, (unsigned long) index);
			dchanged = 1;
		}
		if (checkbadstring(sfd->sfd_name)) {
			setbadness(EXIT_RECOV);
			warnx("Directory %s entry %lu contains invalid "
			      "characters (fixed)",
			      path, (unsigned long) index);
			dchanged = 1;
		}
	}
	return dchanged;
}

/*
 * Check a directory. INO is the inode number; PATHSOFAR is the path
 * to this directory. This traverses the volume directory tree
 * recursively.
 */
static
void
pass1_dir(uint32_t ino, const char *pathsofar)
{
	struct sfs_dinode sfi;
	struct sfs_direntry *direntries;
	uint32_t ndirentries, i;
	int ichanged=0, dchanged=0;

	sfs_readinode(ino, &sfi);

	if (sfi.sfi_size % sizeof(struct sfs_direntry) != 0) {
		setbadness(EXIT_RECOV);
		warnx("Directory %s has illegal size %lu (fixed)",
		      pathsofar, (unsigned long) sfi.sfi_size);
		sfi.sfi_size = SFS_ROUNDUP(sfi.sfi_size,
					   sizeof(struct sfs_direntry));
		ichanged = 1;
	}
	count_dirs++;

	if (pass1_inode(ino, &sfi, ichanged)) {
		/* been here before; crosslinked dir, sort it out in pass 2 */
		return;
	}

	ndirentries = sfi.sfi_size/sizeof(struct sfs_direntry);
	direntries = domalloc(sfi.sfi_size);

	sfs_readdir(&sfi, direntries, ndirentries);

	for (i=0; i<ndirentries; i++) {
		if (pass1_direntry(pathsofar, i, &direntries[i])) {
			dchanged = 1;
		}
	}

	for (i=0; i<ndirentries; i++) {
		if (direntries[i].sfd_ino == SFS_NOINO) {
			/* nothing */
		}
		else if (!strcmp(direntries[i].sfd_name, ".")) {
			/* nothing */
		}
		else if (!strcmp(direntries[i].sfd_name, "..")) {
			/* nothing */
		}
		else {
			char path[strlen(pathsofar)+SFS_NAMELEN+1];
			struct sfs_dinode subsfi;
			uint32_t subino;

			subino = direntries[i].sfd_ino;
			sfs_readinode(subino, &subsfi);
			snprintf(path, sizeof(path), "%s/%s",
				 pathsofar, direntries[i].sfd_name);

			switch (subsfi.sfi_type) {
			    case SFS_TYPE_FILE:
				if (pass1_inode(subino, &subsfi, 0)) {
					/* been here before */
					break;
				}
				count_files++;
				break;
			    case SFS_TYPE_DIR:
				pass1_dir(subino, path);
				break;
			    default:
				setbadness(EXIT_RECOV);
				warnx("Object %s: Invalid inode type "
				      "(removed)", path);
				direntries[i].sfd_ino = SFS_NOINO;
				direntries[i].sfd_name[0] = 0;
				dchanged = 1;
				break;
			}
		}
	}

	if (dchanged) {
		sfs_writedir(&sfi, direntries, ndirentries);
	}

	free(direntries);
}

/*
 * Check the root directory, and implicitly everything under it.
 */
static
void
pass1_rootdir(void)
{
	struct sfs_dinode sfi;
	char path[SFS_VOLNAME_SIZE + 2];

	sfs_readinode(SFS_ROOTDIR_INO, &sfi);

	switch (sfi.sfi_type) {
	    case SFS_TYPE_DIR:
		break;
	    case SFS_TYPE_FILE:
		warnx("Root directory inode is a regular file (fixed)");
		goto fix;
	    default:
		warnx("Root directory inode has invalid type %lu (fixed)",
		      (unsigned long) sfi.sfi_type);
	    fix:
		setbadness(EXIT_RECOV);
		sfi.sfi_type = SFS_TYPE_DIR;
		sfs_writeinode(SFS_ROOTDIR_INO, &sfi);
		break;
	}

	snprintf(path, sizeof(path), "%s:", sb_volname());
	pass1_dir(SFS_ROOTDIR_INO, path);
}

////////////////////////////////////////////////////////////
// public interface

void
pass1(void)
{
	pass1_rootdir();
}

unsigned long
pass1_founddirs(void)
{
	return count_dirs;
}

unsigned long
pass1_foundfiles(void)
{
	return count_files;
}