/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright (c) 1999,2000 by Sun Microsystems, Inc.
 * All rights reserved.
 * Copyright (c) 2016 by Delphix. All rights reserved.
 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

/*
 * fsck_pcfs -- routines for manipulating clusters.
 */
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <stdlib.h>
#include <libintl.h>
#include <errno.h>
#include <sys/dktp/fdisk.h>
#include <sys/fs/pc_fs.h>
#include <sys/fs/pc_dir.h>
#include <sys/fs/pc_label.h>
#include "pcfs_common.h"
#include "fsck_pcfs.h"

extern	ClusterContents	TheRootDir;
extern	off64_t		FirstClusterOffset;
extern	off64_t		PartitionOffset;
extern	int32_t		BytesPerCluster;
extern	int32_t		TotalClusters;
extern	int32_t		LastCluster;
extern	int32_t		RootDirSize;
extern	int32_t		FATSize;
extern	bpb_t		TheBIOSParameterBlock;
extern	short		FATEntrySize;
extern	int		RootDirModified;
extern	int		OkayToRelink;
extern	int		ReadOnly;
extern	int		IsFAT32;
extern	int		Verbose;

static	struct pcdir	BlankPCDIR;
static	CachedCluster	*ClusterCache;
static	ClusterInfo	**InUse;
static	int32_t		ReservedClusterCount;
static	int32_t		AllocedClusterCount;
static	int32_t		FreeClusterCount;
static	int32_t		BadClusterCount;

/*
 * Internal statistics
 */
static	int32_t		CachedClusterCount;

int32_t	HiddenClusterCount;
int32_t	FileClusterCount;
int32_t	DirClusterCount;
int32_t	HiddenFileCount;
int32_t	FileCount;
int32_t	DirCount;

static int32_t orphanSizeLookup(int32_t clusterNum);

static void
freeNameInfo(int32_t clusterNum)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return;
	if (InUse[clusterNum - FIRST_CLUSTER]->path != NULL) {
		if (InUse[clusterNum - FIRST_CLUSTER]->path->references > 1) {
			InUse[clusterNum - FIRST_CLUSTER]->path->references--;
		} else {
			free(InUse[clusterNum - FIRST_CLUSTER]->path->fullName);
			free(InUse[clusterNum - FIRST_CLUSTER]->path);
		}
		InUse[clusterNum - FIRST_CLUSTER]->path = NULL;
	}
}

static void
printOrphanPath(int32_t clusterNum)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return;
	if (InUse[clusterNum - FIRST_CLUSTER]->path != NULL) {
		(void) printf(gettext("\nOrphaned allocation units originally "
		    "allocated to:\n"));
		(void) printf("%s\n",
		    InUse[clusterNum - FIRST_CLUSTER]->path->fullName);
		freeNameInfo(clusterNum);
	} else {
		(void) printf(gettext("\nOrphaned allocation units originally "
		    "allocated to an unknown file or directory:\n"));
		(void) printf(gettext("Orphaned chain begins with allocation "
		    "unit %d.\n"), clusterNum);
	}
}

static void
printOrphanSize(int32_t clusterNum)
{
	int32_t size = orphanSizeLookup(clusterNum);

	if (size > 0) {
		(void) printf(gettext("%d bytes in the orphaned chain of "
		    "allocation units.\n"), size);
		if (Verbose) {
			(void) printf(gettext("[Starting at allocation "
			    "unit %d]\n"), clusterNum);
		}
	}
}

static void
printOrphanInfo(int32_t clusterNum)
{
	printOrphanPath(clusterNum);
	printOrphanSize(clusterNum);
}

static int
askAboutFreeing(int32_t clusterNum)
{
	/*
	 * If it is not OkayToRelink, we haven't already printed the size
	 * of the orphaned chain.
	 */
	if (!OkayToRelink)
		printOrphanInfo(clusterNum);
	/*
	 *  If we are in preen mode, preenBail won't return.
	 */
	preenBail("Need user confirmation to free orphaned chain.\n");

	(void) printf(
	    gettext("Free the allocation units in the orphaned chain ? "
	    "(y/n) "));
	return (yes());
}

static int
askAboutRelink(int32_t clusterNum)
{
	/*
	 * Display the size of the chain for the user to consider.
	 */
	printOrphanInfo(clusterNum);
	/*
	 *  If we are in preen mode, preenBail won't return.
	 */
	preenBail("Need user confirmation to re-link orphaned chain.\n");

	(void) printf(gettext("Re-link orphaned chain into file system ? "
	    "(y/n) "));

	return (yes());
}

static int
isHidden(int32_t clusterNum)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return (0);

	if (InUse[clusterNum - FIRST_CLUSTER] == NULL)
		return (0);

	return (InUse[clusterNum - FIRST_CLUSTER]->flags & CLINFO_HIDDEN);
}

static int
isInUse(int32_t clusterNum)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return (0);

	return ((InUse[clusterNum - FIRST_CLUSTER] != NULL) &&
		(InUse[clusterNum - FIRST_CLUSTER]->dirent != NULL));
}

/*
 *  Caller's may request that we cache the data from a readCluster.
 *  The xxxClusterxxxCachexxx routines handle looking for cached data
 *  or initially caching the data.
 *
 *  XXX - facilitate releasing cached data for low memory situations.
 */
static CachedCluster *
findClusterCacheEntry(int32_t clusterNum)
{
	CachedCluster *loop = ClusterCache;

	while (loop != NULL) {
		if (loop->clusterNum == clusterNum)
			return (loop);
		loop = loop->next;
	}
	return (NULL);
}

static uchar_t *
findClusterDataInTheCache(int32_t clusterNum)
{
	CachedCluster *loop = ClusterCache;

	while (loop) {
		if (loop->clusterNum == clusterNum)
			return (loop->clusterData.bytes);
		loop = loop->next;
	}
	return (NULL);
}

static uchar_t *
addToCache(int32_t clusterNum, uchar_t *buf, int32_t *datasize)
{
	CachedCluster *new;
	uchar_t *cp;

	if ((new = (CachedCluster *)malloc(sizeof (CachedCluster))) == NULL) {
		perror(gettext("No memory for cached cluster info"));
		return (buf);
	}
	new->clusterNum = clusterNum;
	new->modified = 0;

	if ((cp = (uchar_t *)calloc(1, BytesPerCluster)) == NULL) {
		perror(gettext("No memory for cached copy of cluster"));
		free(new);
		return (buf);
	}
	(void) memcpy(cp, buf, *datasize);
	new->clusterData.bytes = cp;

	if (Verbose) {
		(void) fprintf(stderr,
		    gettext("Allocation unit %d cached.\n"), clusterNum);
	}
	if (ClusterCache == NULL) {
		ClusterCache = new;
		new->next = NULL;
	} else if (new->clusterNum < ClusterCache->clusterNum) {
		new->next = ClusterCache;
		ClusterCache = new;
	} else {
		CachedCluster *loop = ClusterCache;
		CachedCluster *trailer = NULL;

		while (loop && new->clusterNum > loop->clusterNum) {
			trailer = loop;
			loop = loop->next;
		}
		trailer->next = new;
		if (loop) {
			new->next = loop;
		} else {
			new->next = NULL;
		}
	}
	CachedClusterCount++;
	return (new->clusterData.bytes);
}

static int
seekCluster(int fd, int32_t clusterNum)
{
	off64_t seekto;
	int saveError;

	seekto = FirstClusterOffset +
	    ((off64_t)clusterNum - FIRST_CLUSTER) * BytesPerCluster;
	if (lseek64(fd, seekto, SEEK_SET) != seekto) {
		saveError = errno;
		(void) fprintf(stderr,
		    gettext("Seek to Allocation unit #%d failed: "),
		    clusterNum);
		(void) fprintf(stderr, strerror(saveError));
		(void) fprintf(stderr, "\n");
		return (0);
	}
	return (1);
}

/*
 *  getcluster
 *	Get cluster bytes off the disk.  We always read those bytes into
 *	the same static buffer.  If the caller wants its own copy of the
 *	data it'll have to make its own copy.  We'll return all the data
 *	read, even if it's short of a full cluster.  This is for future use
 *	when we might want to relocate any salvagable data from bad clusters.
 */
static int
getCluster(int fd, int32_t clusterNum, uchar_t **data, int32_t *datasize)
{
	static uchar_t *clusterBuffer = NULL;
	int saveError;
	int try;

	*datasize = 0;
	*data = NULL;

	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return (RDCLUST_BADINPUT);

	if (clusterBuffer == NULL &&
	    (clusterBuffer = (uchar_t *)malloc(BytesPerCluster)) == NULL) {
		perror(gettext("No memory for a cluster data buffer"));
		return (RDCLUST_MEMERR);
	}

	for (try = 0; try < RDCLUST_MAX_RETRY; try++) {
		if (!seekCluster(fd, clusterNum))
			return (RDCLUST_FAIL);
		if ((*datasize = read(fd, clusterBuffer, BytesPerCluster)) ==
		    BytesPerCluster) {
			*data = clusterBuffer;
			return (RDCLUST_GOOD);
		}
	}
	if (*datasize >= 0) {
		*data = clusterBuffer;
		(void) fprintf(stderr,
		    gettext("Short read of allocation unit #%d\n"), clusterNum);
	} else {
		saveError = errno;
		(void) fprintf(stderr, "Allocation unit %d:", clusterNum);
		(void) fprintf(stderr, strerror(saveError));
		(void) fprintf(stderr, "\n");
	}
	return (RDCLUST_FAIL);
}

static void
writeCachedCluster(int fd, CachedCluster *clustInfo)
{
	ssize_t bytesWritten;

	if (ReadOnly)
		return;

	if (Verbose)
		(void) fprintf(stderr,
		    gettext("Allocation unit %d modified.\n"),
		    clustInfo->clusterNum);

	if (seekCluster(fd, clustInfo->clusterNum) == NULL)
		return;

	if ((bytesWritten = write(fd, clustInfo->clusterData.bytes,
	    BytesPerCluster)) != BytesPerCluster) {
		if (bytesWritten < 0) {
			perror(gettext("Failed to write modified "
			    "allocation unit"));
		} else {
			(void) fprintf(stderr,
			    gettext("Short write of allocation unit %d\n"),
			    clustInfo->clusterNum);
		}
		(void) close(fd);
		exit(13);
	}
}

/*
 * It's cheaper to allocate a lot at a time; malloc overhead pushes
 * you over the brink much more quickly if you don't.
 * This numbers seems to be a fair trade-off between reduced malloc overhead
 * and additional overhead by over-allocating.
 */

#define	CHUNKSIZE	1024

static ClusterInfo *pool;

static ClusterInfo *
newClusterInfo(void)
{

	ClusterInfo *ret;

	if (pool == NULL) {
		int i;

		pool = (ClusterInfo *)malloc(sizeof (ClusterInfo) * CHUNKSIZE);

		if (pool == NULL) {
			perror(
			    gettext("Out of memory for cluster information"));
			exit(9);
		}

		for (i = 0; i < CHUNKSIZE - 1; i++)
			pool[i].nextfree = &pool[i+1];

		pool[CHUNKSIZE-1].nextfree = NULL;
	}
	ret = pool;
	pool = pool->nextfree;

	memset(ret, 0, sizeof (*ret));

	return (ret);
}

/* Should be called with verified arguments */

static ClusterInfo *
cloneClusterInfo(int32_t clusterNum)
{
	ClusterInfo *cl = InUse[clusterNum - FIRST_CLUSTER];

	if (cl->refcnt > 1) {
		ClusterInfo *newCl = newClusterInfo();
		cl->refcnt--;
		*newCl = *cl;
		newCl->refcnt = 1;
		if (newCl->path)
			newCl->path->references++;
		InUse[clusterNum - FIRST_CLUSTER] = newCl;
	}
	return (InUse[clusterNum - FIRST_CLUSTER]);
}

static void
updateFlags(int32_t clusterNum, int newflags)
{
	ClusterInfo *cl = InUse[clusterNum - FIRST_CLUSTER];

	if (cl->flags != newflags && cl->refcnt > 1)
		cl = cloneClusterInfo(clusterNum);

	cl->flags = newflags;
}

static void
freeClusterInfo(ClusterInfo *old)
{
	if (--old->refcnt <= 0) {
		if (old->path && --old->path->references <= 0) {
			free(old->path->fullName);
			free(old->path);
		}
		old->nextfree = pool;
		pool = old;
	}
}

/*
 * Allocate entries in our sparse array of cluster information.
 * Returns non-zero if the structure already has been allocated
 * (for those keeping score at home).
 *
 * The template parameter, if non-NULL, is used to facilitate sharing
 * the ClusterInfo nodes for the clusters belonging to the same file.
 * The first call to allocInUse for a new file should have *template
 * set to 0; on return, *template then points to the newly allocated
 * ClusterInfo.  Second and further calls keep the same value
 * in *template and that ClusterInfo ndoe is then used for all
 * entries in the file.  Code that modifies the ClusterInfo nodes
 * should take care proper sharing semantics are maintained (i.e.,
 * copy-on-write using cloneClusterInfo())
 *
 * The ClusterInfo used in the template is guaranted to be in use in
 * at least one other cluster as we never return a value if we didn't
 * set it first.  So we can overwrite it without the possibility of a leak.
 */
static int
allocInUse(int32_t clusterNum, ClusterInfo **template)
{
	ClusterInfo *newCl;

	if (InUse[clusterNum - FIRST_CLUSTER] != NULL)
		return (CLINFO_PREVIOUSLY_ALLOCED);

	if (template != NULL && *template != NULL)
		newCl = *template;
	else {
		newCl = newClusterInfo();
		if (template)
			*template = newCl;
	}

	InUse[clusterNum - FIRST_CLUSTER] = newCl;
	newCl->refcnt++;

	return (CLINFO_NEWLY_ALLOCED);
}

static void
markFree(int32_t clusterNum)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return;

	if (InUse[clusterNum - FIRST_CLUSTER]) {
		if (InUse[clusterNum - FIRST_CLUSTER]->saved)
			free(InUse[clusterNum - FIRST_CLUSTER]->saved);
		freeClusterInfo(InUse[clusterNum - FIRST_CLUSTER]);
		InUse[clusterNum - FIRST_CLUSTER] = NULL;
	}
}

static void
markOrphan(int fd, int32_t clusterNum, struct pcdir *dp)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return;

	(void) markInUse(fd, clusterNum, dp, NULL, 0, VISIBLE, NULL);
	if (InUse[clusterNum - FIRST_CLUSTER] != NULL)
		updateFlags(clusterNum,
		    InUse[clusterNum - FIRST_CLUSTER]->flags | CLINFO_ORPHAN);
}

static void
markBad(int32_t clusterNum, uchar_t *recovered, int32_t recoveredLen)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return;

	(void) allocInUse(clusterNum, NULL);

	if (recoveredLen) {
		(void) cloneClusterInfo(clusterNum);
		InUse[clusterNum - FIRST_CLUSTER]->saved = recovered;
	}
	updateFlags(clusterNum,
	    InUse[clusterNum - FIRST_CLUSTER]->flags | CLINFO_BAD);

	BadClusterCount++;
	if (Verbose)
		(void) fprintf(stderr,
		    gettext("Allocation unit %d marked bad.\n"), clusterNum);
}

static void
clearOrphan(int32_t c)
{
	/* silent failure for bogus clusters */
	if (c < FIRST_CLUSTER || c > LastCluster)
		return;
	if (InUse[c - FIRST_CLUSTER] != NULL)
		updateFlags(c,
		    InUse[c - FIRST_CLUSTER]->flags & ~CLINFO_ORPHAN);
}

static void
clearInUse(int32_t c)
{
	ClusterInfo **clp;

	/* silent failure for bogus clusters */
	if (c < FIRST_CLUSTER || c > LastCluster)
		return;

	clp = &InUse[c - FIRST_CLUSTER];
	if (*clp != NULL) {
		freeClusterInfo(*clp);
		*clp = NULL;
	}
}

static void
clearAllClusters_InUse()
{
	int32_t cc;
	for (cc = FIRST_CLUSTER; cc < LastCluster; cc++) {
		clearInUse(cc);
	}
}

static void
makeUseTable(void)
{
	if (InUse != NULL) {
		clearAllClusters_InUse();
		return;
	}
	if ((InUse = (ClusterInfo **)
	    calloc(TotalClusters, sizeof (ClusterInfo *))) == NULL) {
		perror(gettext("No memory for internal table"));
		exit(9);
	}
}

static void
countClusters(void)
{
	int32_t c;

	BadClusterCount = HiddenClusterCount =
	    AllocedClusterCount = FreeClusterCount = 0;

	for (c = FIRST_CLUSTER; c < LastCluster; c++) {
		if (badInFAT(c)) {
			BadClusterCount++;
		} else if (isMarkedBad(c)) {
			/*
			 * This catches the bad sectors found
			 * during thorough verify that have never been
			 * allocated to a file.  Without this check, we
			 * count these guys as free.
			 */
			BadClusterCount++;
			markBadInFAT(c);
		} else if (isHidden(c)) {
			HiddenClusterCount++;
		} else if (isInUse(c)) {
			AllocedClusterCount++;
		} else {
			FreeClusterCount++;
		}
	}
}

/*
 * summarizeFAT
 *	Mark orphans without directory entries as allocated.
 *	XXX - these chains should be reclaimed!
 *	XXX - merge this routine with countClusters (same loop, duh.)
 */
static void
summarizeFAT(int fd)
{
	int32_t c;
	ClusterInfo *tmpl = NULL;

	for (c = FIRST_CLUSTER; c < LastCluster; c++) {
		if (!freeInFAT(c) && !badInFAT(c) && !reservedInFAT(c) &&
		    !isInUse(c)) {
			(void) markInUse(fd, c, &BlankPCDIR, NULL, 0, VISIBLE,
				&tmpl);
		}
	}
}

static void
getReadyToSearch(int fd)
{
	getFAT(fd);
	if (!IsFAT32)
		getRootDirectory(fd);
}


static char PathName[MAXPATHLEN];

static void
summarize(int fd, int includeFAT)
{
	struct pcdir *ignorep1, *ignorep2 = NULL;
	int32_t ignore32;
	char ignore;
	int pathlen;

	ReservedClusterCount = 0;
	AllocedClusterCount = 0;
	HiddenClusterCount = 0;
	FileClusterCount = 0;
	FreeClusterCount = 0;
	DirClusterCount = 0;
	BadClusterCount = 0;
	HiddenFileCount = 0;
	FileCount = 0;
	DirCount = 0;
	ignorep1 = ignorep2 = NULL;
	ignore = '\0';

	PathName[0] = '\0';
	pathlen = 0;

	getReadyToSearch(fd);
	/*
	 *  Traverse the full meta-data tree to talley what clusters
	 * are in use.  The root directory is an area outside of the
	 * file space on FAT12 and FAT16 file systems.  On FAT32 file
	 * systems, the root directory is in a file area cluster just
	 * like any other directory.
	 */
	if (!IsFAT32) {
		traverseFromRoot(fd, 0, PCFS_VISIT_SUBDIRS, PCFS_TRAVERSE_ALL,
		    ignore, &ignorep1, &ignore32, &ignorep2, PathName,
		    &pathlen);
	} else {
		DirCount++;
		traverseDir(fd, TheBIOSParameterBlock.bpb32.root_dir_clust,
		    0, PCFS_VISIT_SUBDIRS, PCFS_TRAVERSE_ALL, ignore,
		    &ignorep1, &ignore32, &ignorep2, PathName, &pathlen);
	}

	if (includeFAT)
		summarizeFAT(fd);
	countClusters();
}

int
isMarkedBad(int32_t clusterNum)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return (0);

	if (InUse[clusterNum - FIRST_CLUSTER] == NULL)
		return (0);

	return (InUse[clusterNum - FIRST_CLUSTER]->flags & CLINFO_BAD);
}

static int
isMarkedOrphan(int32_t clusterNum)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return (0);

	if (InUse[clusterNum - FIRST_CLUSTER] == NULL)
		return (0);

	return (InUse[clusterNum - FIRST_CLUSTER]->flags & CLINFO_ORPHAN);
}

static void
orphanChain(int fd, int32_t c, struct pcdir *ndp)
{
	ClusterInfo *tmpl = NULL;

	/* silent failure for bogus clusters */
	if (c < FIRST_CLUSTER || c > LastCluster)
		return;
	clearInUse(c);
	markOrphan(fd, c, ndp);
	c = nextInChain(c);
	while (c != 0) {
		clearInUse(c);
		clearOrphan(c);
		(void) markInUse(fd, c, ndp, NULL, 0, VISIBLE, &tmpl);
		c = nextInChain(c);
	}
}

static int32_t
findAFreeCluster(int32_t startAt)
{
	int32_t look = startAt;

	for (;;) {
		if (freeInFAT(look)) {
			break;
		}
		if (look == LastCluster)
			look = FIRST_CLUSTER;
		else
			look++;
		if (look == startAt)
			break;
	}
	if (look != startAt)
		return (look);
	else
		return (0);
}

static void
setEndOfDirectory(struct pcdir *dp)
{
	dp->pcd_filename[0] = PCD_UNUSED;
}

static void
emergencyEndOfDirectory(int fd, int32_t secondToLast)
{
	ClusterContents dirdata;
	int32_t dirdatasize = 0;

	if (readCluster(fd, secondToLast, &(dirdata.bytes), &dirdatasize,
	    RDCLUST_DO_CACHE) != RDCLUST_GOOD) {
		(void) fprintf(stderr,
		    gettext("Unable to read allocation unit %d.\n"),
		    secondToLast);
		(void) fprintf(stderr,
		    gettext("Cannot allocate a new allocation unit to hold an"
		    " end-of-directory marker.\nCannot access allocation unit"
		    " to overwrite existing directory entry with\nthe marker."
		    "  Needed directory truncation has failed.  Giving up.\n"));
		(void) close(fd);
		exit(11);
	}
	setEndOfDirectory(dirdata.dirp);
	markClusterModified(secondToLast);
}

static void
makeNewEndOfDirectory(struct pcdir *entry, int32_t secondToLast,
    int32_t newCluster, ClusterContents *newData)
{
	setEndOfDirectory(newData->dirp);
	markClusterModified(newCluster);
	/*
	 *  There are two scenarios.  One is that we truncated the
	 *  directory in the very beginning.  The other is that we
	 *  truncated it in the middle or at the end.  In the first
	 *  scenario, the secondToLast argument is not a valid cluster
	 *  (it's zero), and so we actually need to change the start
	 *  cluster for the directory to this new start cluster.  In
	 *  the second scenario, the secondToLast cluster we received
	 *  as an argument needs to be pointed at the new end of
	 *  directory.
	 */
	if (secondToLast == 0) {
		updateDirEnt_Start(entry, newCluster);
	} else {
		writeFATEntry(secondToLast, newCluster);
	}
	markLastInFAT(newCluster);
}

static void
createNewEndOfDirectory(int fd, struct pcdir *entry, int32_t secondToLast)
{
	ClusterContents dirdata;
	int32_t dirdatasize = 0;
	int32_t freeCluster;

	if (((freeCluster = findAFreeCluster(secondToLast)) != 0)) {
		if (readCluster(fd, freeCluster, &(dirdata.bytes),
		    &dirdatasize, RDCLUST_DO_CACHE) == RDCLUST_GOOD) {
			if (Verbose) {
				(void) fprintf(stderr,
				    gettext("Grabbed allocation unit #%d "
				    "for truncated\ndirectory's new end "
				    "of directory.\n"), freeCluster);
			}
			makeNewEndOfDirectory(entry, secondToLast,
			    freeCluster, &dirdata);
			return;
		}
	}
	if (secondToLast == 0) {
		if (freeCluster == 0) {
			(void) fprintf(stderr, gettext("File system full.\n"));
		} else {
			(void) fprintf(stderr,
			    gettext("Unable to read allocation unit %d.\n"),
			    freeCluster);
		}
		(void) fprintf(stderr,
		    gettext("Cannot allocate a new allocation unit to hold "
		    "an end-of-directory marker.\nNo existing directory "
		    "entries can be overwritten with the marker,\n"
		    "the only unit allocated to the directory is "
		    "inaccessible.\nNeeded directory truncation has failed.  "
		    "Giving up.\n"));
		(void) close(fd);
		exit(11);
	}
	emergencyEndOfDirectory(fd, secondToLast);
}

/*
 * truncAtCluster
 *	Given a directory entry and a cluster number, search through
 *	the cluster chain for the entry and make the cluster previous
 *	to the given cluster in the chain the last cluster in the file.
 *	The number of orphaned bytes is returned.  For a chain that's
 *	a directory we need to do some special handling, since we'll be
 *	getting rid of the end of directory notice by truncating.
 */
static int64_t
truncAtCluster(int fd, struct pcdir *entry, int32_t cluster)
{
	uint32_t oldSize, newSize;
	int32_t prev, count, follow;
	int dir = (entry->pcd_attr & PCA_DIR);

	prev = 0; count = 0;
	follow = extractStartCluster(entry);
	while (follow != cluster && follow >= FIRST_CLUSTER &&
	    follow <= LastCluster) {
		prev = follow;
		count++;
		follow = nextInChain(follow);
	}
	if (follow != cluster) {
		/*
		 *  We didn't find the cluster they wanted to trunc at
		 *  anywhere in the entry's chain.  So we'll leave the
		 *  entry alone, and return a negative value so they
		 *  can know something is wrong.
		 */
		return (-1);
	}
	if (Verbose) {
		(void) fprintf(stderr,
		    gettext("Chain truncation at unit #%d\n"), cluster);
	}
	if (!dir) {
		oldSize = extractSize(entry);
		newSize = count *
		    TheBIOSParameterBlock.bpb.sectors_per_cluster *
		    TheBIOSParameterBlock.bpb.bytes_per_sector;
		if (newSize == 0)
			updateDirEnt_Start(entry, 0);
	} else {
		newSize = 0;
	}
	updateDirEnt_Size(entry, newSize);
	if (dir) {
		createNewEndOfDirectory(fd, entry, prev);
	} else if (prev != 0) {
		markLastInFAT(prev);
	}
	if (dir) {
		/*
		 * We don't really know what the size of a directory is
		 * but it is important for us to know if this truncation
		 * results in an orphan with any size.  The value we
		 * return from this routine for a normal file is the
		 * number of bytes left in the chain.  For a directory
		 * we can't be exact, and the caller doesn't really
		 * expect us to be.  For a directory the caller only
		 * cares if there are zero bytes left or more than
		 * zero bytes left.  We'll return 1 to indicate
		 * more than zero.
		 */
		if ((follow = nextInChain(follow)) != 0)
			return (1);
		else
			return (0);
	}
	/*
	 * newSize should always be smaller than the old one, since
	 * we are decreasing the number of clusters allocated to the file.
	 */
	return ((int64_t)oldSize - (int64_t)newSize);
}

static struct pcdir *
updateOrphanedChainMetadata(int fd, struct pcdir *dp, int32_t endCluster,
    int isBad)
{
	struct pcdir *ndp = NULL;
	int64_t remainder;
	char *newName = NULL;
	int chosenName;
	int dir = (dp->pcd_attr & PCA_DIR);

	/*
	 *  If the truncation fails, (which ought not to happen),
	 *  there's no need to go any further, we just return
	 *  a null value for the new directory entry pointer.
	 */
	remainder = truncAtCluster(fd, dp, endCluster);
	if (remainder < 0)
		return (ndp);
	if (!dir && isBad) {
		/*
		 *  Subtract out the bad cluster from the remaining size
		 *  We always assume the cluster being deleted from the
		 *  file is full size, but that might not be the case
		 *  for the last cluster of the file, so that is why
		 *  we check for negative remainder value.
		 */
		remainder -= TheBIOSParameterBlock.bpb.sectors_per_cluster *
		    TheBIOSParameterBlock.bpb.bytes_per_sector;
		if (remainder < 0)
			remainder = 0;
	}
	/*
	 * Build a new directory entry for the rest of the chain.
	 * Later, if the user okays it, we'll link this entry into the
	 * root directory.  The new entry will start out as a
	 * copy of the truncated entry.
	 */
	if ((remainder != 0) &&
	    ((newName = nextAvailableCHKName(&chosenName)) != NULL) &&
	    ((ndp = newDirEnt(dp)) != NULL)) {
		if (Verbose) {
			if (dir)
				(void) fprintf(stderr,
				    gettext("Orphaned directory chain.\n"));
			else
				(void) fprintf(stderr,
				    gettext("Orphaned chain, %u bytes.\n"),
				    (uint32_t)remainder);
		}
		if (!dir)
			updateDirEnt_Size(ndp, (uint32_t)remainder);
		if (isBad)
			updateDirEnt_Start(ndp, nextInChain(endCluster));
		else
			updateDirEnt_Start(ndp, endCluster);
		updateDirEnt_Name(ndp, newName);
		addEntryToCHKList(chosenName);
	}
	return (ndp);
}

/*
 *  splitChain()
 *
 *	split a cluster allocation chain into two cluster chains
 *	around a given cluster (problemCluster).  This results in two
 *	separate directory entries; the original (dp), and one we hope
 *	to create and return a pointer to to the caller (*newdp).
 *	This second entry is the orphan chain, and it may end up in
 *	the root directory as a FILEnnnn.CHK file.  We also return the
 *	starting cluster of the orphan chain to the caller (*orphanStart).
 */
void
splitChain(int fd, struct pcdir *dp, int32_t problemCluster,
    struct pcdir **newdp, int32_t *orphanStart)
{
	struct pcdir *ndp = NULL;
	int isBad = isMarkedBad(problemCluster);

	ndp = updateOrphanedChainMetadata(fd, dp, problemCluster, isBad);
	*newdp = ndp;
	clearInUse(problemCluster);
	if (isBad) {
		clearOrphan(problemCluster);
		*orphanStart = nextInChain(problemCluster);
		orphanChain(fd, *orphanStart, ndp);
		markBadInFAT(problemCluster);
	} else {
		*orphanStart = problemCluster;
		orphanChain(fd, problemCluster, ndp);
	}
}

/*
 *  freeOrphan
 *
 *  User has requested that an orphaned cluster chain be freed back
 *  into the file area.
 */
static void
freeOrphan(int32_t c)
{
	int32_t n;

	/*
	 * Free the directory entry we explicitly created for
	 * the orphaned clusters.
	 */
	if (InUse[c - FIRST_CLUSTER]->dirent != NULL)
		free(InUse[c - FIRST_CLUSTER]->dirent);
	/*
	 * Then mark the clusters themselves as available.
	 */
	do {
		n = nextInChain(c);
		markFreeInFAT(c);
		markFree(c);
		c = n;
	} while (c != 0);
}

/*
 *  Rewrite the InUse field for a cluster chain.  Can be used on a partial
 *  chain if provided with a stopAtCluster.
 */
static void
redoInUse(int fd, int32_t c, struct pcdir *ndp, int32_t stopAtCluster)
{
	while (c && c != stopAtCluster) {
		clearInUse(c);
		(void) markInUse(fd, c, ndp, NULL, 0, VISIBLE, NULL);
		c = nextInChain(c);
	}
}

static struct pcdir *
orphanDirEntLookup(int32_t clusterNum)
{
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return (NULL);

	if (isInUse(clusterNum)) {
		return (InUse[clusterNum - FIRST_CLUSTER]->dirent);
	} else {
		return (NULL);
	}
}

static int32_t
orphanSizeLookup(int32_t clusterNum)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return (-1);

	if (isInUse(clusterNum)) {
		return (extractSize(InUse[clusterNum - FIRST_CLUSTER]->dirent));
	} else {
		return (-1);
	}
}

/*
 *  linkOrphan
 *
 *  User has requested that an orphaned cluster chain be brought back
 *  into the file system.  So we have to make a new directory entry
 *  in the root directory and point it at the cluster chain.
 */
static void
linkOrphan(int fd, int32_t start)
{
	struct pcdir *newEnt = NULL;
	struct pcdir *dp;

	if ((dp = orphanDirEntLookup(start)) != NULL) {
		newEnt = addRootDirEnt(fd, dp);
	} else {
		(void) printf(gettext("Re-link of orphaned chain failed."
		    "  Allocation units will remain orphaned.\n"));
	}
	/*
	 *  A cluster isn't really InUse() unless it is referenced,
	 *  so if newEnt is NULL here, we are in effect using markInUse()
	 *  to note that the cluster is NOT in use.
	 */
	redoInUse(fd, start, newEnt, 0);
}

/*
 *  relinkCreatedOrphans
 *
 *  While marking clusters as bad, we can create orphan cluster
 *  chains.  Since we were the ones doing the marking, we were able to
 *  keep track of the orphans we created.  Now we want to go through
 *  all those chains and either get them back into the file system or
 *  free them depending on the user's input.
 */
static void
relinkCreatedOrphans(int fd)
{
	int32_t c;

	for (c = FIRST_CLUSTER; c < LastCluster; c++) {
		if (isMarkedOrphan(c)) {
			if (OkayToRelink && askAboutRelink(c)) {
				linkOrphan(fd, c);
			} else if (askAboutFreeing(c)) {
				freeOrphan(c);
			}
			clearOrphan(c);
		}
	}
}

/*
 *  relinkFATOrphans
 *
 *  We want to find orphans not represented in the meta-data.
 *  These are chains marked in the FAT as being in use but
 *  not referenced anywhere by any directory entries.
 *  We'll go through the whole FAT and mark the first cluster
 *  in any such chain as an orphan.  Then we can just use
 *  the relinkCreatedOrphans routine to get them back into the
 *  file system or free'ed depending on the user's input.
 */
static void
relinkFATOrphans(int fd)
{
	struct pcdir *ndp = NULL;
	int32_t cc, c, n;
	int32_t bpc, newSize;
	char *newName;
	int chosenName;

	for (c = FIRST_CLUSTER; c < LastCluster; c++) {
		if (freeInFAT(c) || badInFAT(c) ||
		    reservedInFAT(c) || isInUse(c))
			continue;
		cc = 1;
		n = c;
		while (n = nextInChain(n))
			cc++;
		bpc = TheBIOSParameterBlock.bpb.sectors_per_cluster *
		    TheBIOSParameterBlock.bpb.bytes_per_sector;
		newSize = cc * bpc;
		if (((newName = nextAvailableCHKName(&chosenName)) != NULL) &&
		    ((ndp = newDirEnt(NULL)) != NULL)) {
			updateDirEnt_Size(ndp, newSize);
			updateDirEnt_Start(ndp, c);
			updateDirEnt_Name(ndp, newName);
			addEntryToCHKList(chosenName);
		}
		orphanChain(fd, c, ndp);
	}
	relinkCreatedOrphans(fd);
}

static void
relinkOrphans(int fd)
{
	relinkCreatedOrphans(fd);
	relinkFATOrphans(fd);
}

static void
checkForFATLoop(int32_t clusterNum)
{
	int32_t prev = clusterNum;
	int32_t follow;

	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return;

	follow = nextInChain(clusterNum);
	while (follow != clusterNum && follow >= FIRST_CLUSTER &&
	    follow <= LastCluster) {
		prev = follow;
		follow = nextInChain(follow);
	}
	if (follow == clusterNum) {
		/*
		 * We found a loop.  Eradicate it by changing
		 * the last cluster in the loop to be last
		 * in the chain instead instead of pointing
		 * back to the first cluster.
		 */
		markLastInFAT(prev);
	}
}

static void
sharedChainError(int fd, int32_t clusterNum, struct pcdir *badEntry)
{
	/*
	 * If we have shared clusters, it is either because the
	 * cluster somehow got assigned to multiple files and/or
	 * because of a loop in the cluster chain.  In either
	 * case we want to truncate the offending file at the
	 * cluster of contention.  Then, we will want to run
	 * through the remainder of the chain. If we find ourselves
	 * back at the top, we will know there is a loop in the
	 * FAT we need to remove.
	 */
	if (Verbose)
		(void) fprintf(stderr,
		    gettext("Truncating chain due to duplicate allocation of "
		    "unit %d.\n"), clusterNum);
	/*
	 * Note that we don't orphan anything here, because the duplicate
	 * part of the chain may be part of another valid chain.
	 */
	(void) truncAtCluster(fd, badEntry, clusterNum);
	checkForFATLoop(clusterNum);
}

void
truncChainWithBadCluster(int fd, struct pcdir *dp, int32_t startCluster)
{
	struct pcdir *orphanEntry;
	int32_t orphanStartCluster;
	int32_t c = startCluster;

	while (c != 0) {
		if (isMarkedBad(c)) {
			/*
			 *  splitChain() truncates the current guy and
			 *  then makes an orphan chain out of the remaining
			 *  clusters.  When we come back from the split
			 *  we'll want to continue looking for bad clusters
			 *  in the orphan chain.
			 */
			splitChain(fd, dp, c,
			    &orphanEntry, &orphanStartCluster);
			/*
			 *  There is a chance that we weren't able or weren't
			 *  required to make a directory entry for the
			 *  remaining clusters.  In that case we won't go
			 *  on, because we couldn't make any more splits
			 *  anyway.
			 */
			if (orphanEntry == NULL)
				break;
			c = orphanStartCluster;
			dp = orphanEntry;
			continue;
		}
		c = nextInChain(c);
	}
}

int32_t
nextInChain(int32_t currentCluster)
{
	int32_t nextCluster;

	/* silent failure for bogus clusters */
	if (currentCluster < FIRST_CLUSTER || currentCluster > LastCluster)
		return (0);

	/*
	 * Look up FAT entry of next link in cluster chain,
	 * if this one is the last one return 0 as the next link.
	 */
	nextCluster = readFATEntry(currentCluster);
	if (nextCluster < FIRST_CLUSTER || nextCluster > LastCluster)
		return (0);

	return (nextCluster);
}

/*
 * findImpactedCluster
 *
 *	Called when someone modifies what they believe might be a cached
 *	cluster entry, but when	they only have a directory entry pointer
 *	and not the cluster number.  We have to go dig up what cluster
 *	they are modifying.
 */
int32_t
findImpactedCluster(struct pcdir *modified)
{
	CachedCluster *loop;
	/*
	 * Check to see if it's in the root directory first
	 */
	if (!IsFAT32 && ((uchar_t *)modified >= TheRootDir.bytes) &&
	    ((uchar_t *)modified < TheRootDir.bytes + RootDirSize))
		return (FAKE_ROOTDIR_CLUST);

	loop = ClusterCache;
	while (loop) {
		if (((uchar_t *)modified >= loop->clusterData.bytes) &&
		    ((uchar_t *)modified <
		    (loop->clusterData.bytes + BytesPerCluster))) {
			return (loop->clusterNum);
		}
		loop = loop->next;
	}
	/*
	 *  Guess it wasn't cached after all...
	 */
	return (0);
}

void
writeClusterMods(int fd)
{
	CachedCluster *loop = ClusterCache;

	while (loop) {
		if (loop->modified)
			writeCachedCluster(fd, loop);
		loop = loop->next;
	}
}

void
squirrelPath(struct nameinfo *pathInfo, int32_t clusterNum)
{
	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return;
	if (InUse[clusterNum - FIRST_CLUSTER] == NULL)
		return;
	InUse[clusterNum - FIRST_CLUSTER]->path = pathInfo;
}

int
markInUse(int fd, int32_t clusterNum, struct pcdir *referencer, struct
    pcdir *longRef, int32_t longStartCluster, int isHiddenFile,
    ClusterInfo **template)
{
	int alreadyMarked;
	ClusterInfo *cl;

	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return (CLINFO_NEWLY_ALLOCED);

	alreadyMarked = allocInUse(clusterNum, template);
	if ((alreadyMarked == CLINFO_PREVIOUSLY_ALLOCED) &&
	    (isInUse(clusterNum))) {
		sharedChainError(fd, clusterNum, referencer);
		return (CLINFO_PREVIOUSLY_ALLOCED);
	}
	cl = InUse[clusterNum - FIRST_CLUSTER];
	/*
	 * If Cl is newly allocated (refcnt <= 1) we must fill in the fields.
	 * If Cl has different fields, we must clone it.
	 */

	if (cl->refcnt <= 1 || cl->dirent != referencer ||
	    cl->longent != longRef ||
	    cl->longEntStartClust != longStartCluster) {
		if (cl->refcnt > 1)
			cl = cloneClusterInfo(clusterNum);
		cl->dirent = referencer;
		cl->longent = longRef;
		cl->longEntStartClust = longStartCluster;
		if (isHiddenFile)
			cl->flags |= CLINFO_HIDDEN;

		/*
		 * Return cl as the template to use for other clusters in
		 * this file
		 */
		if (template)
			*template = cl;
	}
	return (CLINFO_NEWLY_ALLOCED);
}

void
markClusterModified(int32_t clusterNum)
{
	CachedCluster *c;

	if (clusterNum == FAKE_ROOTDIR_CLUST) {
		RootDirModified = 1;
		return;
	}

	/* silent failure for bogus clusters */
	if (clusterNum < FIRST_CLUSTER || clusterNum > LastCluster)
		return;

	if (c = findClusterCacheEntry(clusterNum)) {
		c->modified = 1;
	} else {
		(void) fprintf(stderr,
		    gettext("Unexpected internal error: "
		    "Missing cache entry [%d]\n"), clusterNum);
		exit(10);
	}
}

/*
 *  readCluster
 *	caller wants to read cluster clusterNum.  We should return
 *	a pointer to the read data in "data", and fill in the number
 *	of bytes read in "datasize".  If shouldCache is non-zero
 *	we should allocate cache space to the cluster, otherwise we
 *	just return a pointer to a buffer we re-use whenever cacheing
 *	is not requested.
 */
int
readCluster(int fd, int32_t clusterNum, uchar_t **data, int32_t *datasize,
    int shouldCache)
{
	uchar_t *newBuf;
	int rv;

	*data = NULL;
	if ((*data = findClusterDataInTheCache(clusterNum)) != NULL) {
		*datasize = BytesPerCluster;
		return (RDCLUST_GOOD);
	}

	rv = getCluster(fd, clusterNum, &newBuf, datasize);
	if (rv != RDCLUST_GOOD)
		return (rv);

	/*
	 * Caller requested we NOT cache the data from this read.
	 * So, we just return a pointer to the common data buffer.
	 */
	if (shouldCache == 0) {
		*data = newBuf;
		return (rv);
	}

	/*
	 * Caller requested we cache the data from this read.
	 * So, if we have some data, add it to the cache by
	 * copying it out of the common buffer into new storage.
	 */
	if (*datasize > 0)
		*data = addToCache(clusterNum, newBuf, datasize);
	return (rv);
}

void
findBadClusters(int fd)
{
	int32_t clusterCount;
	int32_t datasize;
	uchar_t *data;

	BadClusterCount = 0;
	makeUseTable();
	(void) printf(gettext("** Scanning allocation units\n"));
	for (clusterCount = FIRST_CLUSTER;
	    clusterCount < LastCluster; clusterCount++) {
		if (readCluster(fd, clusterCount,
		    &data, &datasize, RDCLUST_DONT_CACHE) < 0) {
			if (Verbose)
			    (void) fprintf(stderr,
				gettext("\nUnreadable allocation unit %d.\n"),
				clusterCount);
			markBad(clusterCount, data, datasize);
		}
		/*
		 *  Progress meter, display a '.' for every 1000 clusters
		 *  processed.  We don't want to display this when
		 *  we are in verbose mode; verbose mode progress is
		 *  shown by displaying each file name as it is found.
		 */
		if (!Verbose && clusterCount % 1000 == 0)
			(void) printf(".");
	}
	(void) printf(gettext("..done\n"));
}

void
scanAndFixMetadata(int fd)
{
	/*
	 * First we initialize a few things.
	 */
	makeUseTable();
	getReadyToSearch(fd);
	createCHKNameList(fd);

	/*
	 * Make initial scan, taking into account any effect that
	 * the bad clusters we may have already discovered have
	 * on meta-data.  We may break up some cluster chains
	 * during this period.  The relinkCreatedOrphans() call
	 * will then give the user the chance to recover stuff
	 * we've created.
	 */
	(void) printf(gettext("** Scanning file system meta-data\n"));
	summarize(fd, NO_FAT_IN_SUMMARY);
	if (Verbose)
		printSummary(stderr);
	(void) printf(gettext("** Correcting any meta-data discrepancies\n"));
	relinkCreatedOrphans(fd);

	/*
	 * Clear our usage table and go back over everything, this
	 * time including looking for clusters floating free in the FAT.
	 * This may include clusters the user chose to free during the
	 * relink phase.
	 */
	makeUseTable();
	summarize(fd, INCLUDE_FAT_IN_SUMMARY);
	relinkOrphans(fd);
}

void
printSummary(FILE *outDest)
{
	(void) fprintf(outDest,
	    gettext("%llu bytes.\n"),
	    (uint64_t)
	    TotalClusters * TheBIOSParameterBlock.bpb.sectors_per_cluster *
	    TheBIOSParameterBlock.bpb.bytes_per_sector);
	(void) fprintf(outDest,
	    gettext("%llu bytes in bad sectors.\n"),
	    (uint64_t)
	    BadClusterCount * TheBIOSParameterBlock.bpb.sectors_per_cluster *
	    TheBIOSParameterBlock.bpb.bytes_per_sector);
	(void) fprintf(outDest,
	    gettext("%llu bytes in %d directories.\n"),
	    (uint64_t)
	    DirClusterCount * TheBIOSParameterBlock.bpb.sectors_per_cluster *
	    TheBIOSParameterBlock.bpb.bytes_per_sector, DirCount);
	if (HiddenClusterCount) {
		(void) fprintf(outDest,
		    gettext("%llu bytes in %d hidden files.\n"),
		    (uint64_t)HiddenClusterCount *
		    TheBIOSParameterBlock.bpb.sectors_per_cluster *
		    TheBIOSParameterBlock.bpb.bytes_per_sector,
		    HiddenFileCount);
	}
	(void) fprintf(outDest,
	    gettext("%llu bytes in %d files.\n"),
	    (uint64_t)
	    FileClusterCount * TheBIOSParameterBlock.bpb.sectors_per_cluster *
	    TheBIOSParameterBlock.bpb.bytes_per_sector, FileCount);
	(void) fprintf(outDest,
	    gettext("%llu bytes free.\n"), (uint64_t)FreeClusterCount *
	    TheBIOSParameterBlock.bpb.sectors_per_cluster *
	    TheBIOSParameterBlock.bpb.bytes_per_sector);
	(void) fprintf(outDest,
	    gettext("%d bytes per allocation unit.\n"),
	    TheBIOSParameterBlock.bpb.sectors_per_cluster *
	    TheBIOSParameterBlock.bpb.bytes_per_sector);
	(void) fprintf(outDest,
	    gettext("%d total allocation units.\n"), TotalClusters);
	if (ReservedClusterCount)
	    (void) fprintf(outDest, gettext("%d reserved allocation units.\n"),
		ReservedClusterCount);
	(void) fprintf(outDest,
	    gettext("%d available allocation units.\n"), FreeClusterCount);
}