sfsck.c

/*
 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2009
 *	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 <sys/types.h>
#include <assert.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <err.h>

#include "support.h"
#include "kern/sfs.h"

#ifdef HOST
#include <netinet/in.h> // for arpa/inet.h
#include <arpa/inet.h>  // for ntohl
#include "hostcompat.h"
#define SWAPL(x) ntohl(x)
#define SWAPS(x) ntohs(x)

#else

#define SWAPL(x) (x)
#define SWAPS(x) (x)
#define NO_REALLOC
#define NO_QSORT

#endif

#include "disk.h"


#define EXIT_USAGE    4
#define EXIT_FATAL    3
#define EXIT_UNRECOV  2
#define EXIT_RECOV    1
#define EXIT_CLEAN    0

static int badness=0;

static
void
setbadness(int code)
{
	if (badness < code) {
		badness = code;
	}
}

////////////////////////////////////////////////////////////

static
void
swapsb(struct sfs_super *sp)
{
	sp->sp_magic = SWAPL(sp->sp_magic);
	sp->sp_nblocks = SWAPL(sp->sp_nblocks);
}

static
void
swapinode(struct sfs_inode *sfi)
{
	int i;

	sfi->sfi_size = SWAPL(sfi->sfi_size);
	sfi->sfi_type = SWAPS(sfi->sfi_type);
	sfi->sfi_linkcount = SWAPS(sfi->sfi_linkcount);

	for (i=0; i<SFS_NDIRECT; i++) {
		sfi->sfi_direct[i] = SWAPL(sfi->sfi_direct[i]);
	}

#ifdef SFS_NIDIRECT
	for (i=0; i<SFS_NIDIRECT; i++) {
		sfi->sfi_indirect[i] = SWAPL(sfi->sfi_indirect[i]);
	}
#else
	sfi->sfi_indirect = SWAPL(sfi->sfi_indirect);
#endif

#ifdef SFS_NDIDIRECT
	for (i=0; i<SFS_NDIDIRECT; i++) {
		sfi->sfi_dindirect[i] = SWAPL(sfi->sfi_dindirect[i]);
	}
#else
#ifdef HAS_DIDIRECT
	sfi->sfi_dindirect = SWAPL(sfi->sfi_dindirect);
#endif
#endif

#ifdef SFS_NTIDIRECT
	for (i=0; i<SFS_NTIDIRECT; i++) {
		sfi->sfi_tindirect[i] = SWAPL(sfi->sfi_tindirect[i]);
	}
#else
#ifdef HAS_TIDIRECT
	sfi->sfi_tindirect = SWAPL(sfi->sfi_tindirect);
#endif
#endif
}

static
void
swapdir(struct sfs_dir *sfd)
{
	sfd->sfd_ino = SWAPL(sfd->sfd_ino);
}

static
void
swapindir(uint32_t *entries)
{
	int i;
	for (i=0; i<SFS_DBPERIDB; i++) {
		entries[i] = SWAPL(entries[i]);
	}
}

static
void
swapbits(uint8_t *bits)
{
	/* nothing to do */
	(void)bits;
}

////////////////////////////////////////////////////////////

static
void *
domalloc(size_t len)
{
	void *x;
	x = malloc(len);
	if (x==NULL) {
		errx(EXIT_FATAL, "Out of memory");
	}
	return x;
}

////////////////////////////////////////////////////////////

typedef enum {
	B_SUPERBLOCK,	/* Block that is the superblock */
	B_BITBLOCK,	/* Block used by free-block bitmap */
	B_INODE,	/* Block that is an inode */
	B_IBLOCK,	/* Indirect (or doubly-indirect etc.) block */
	B_DIRDATA,	/* Data block of a directory */
	B_DATA,		/* Data block */
	B_TOFREE,	/* Block that was used but we are releasing */
	B_PASTEND,	/* Block off the end of the fs */
} blockusage_t;

static uint32_t nblocks, bitblocks;
static uint32_t uniquecounter = 1;

static unsigned long count_blocks=0, count_dirs=0, count_files=0;

////////////////////////////////////////////////////////////

static uint8_t *bitmapdata;
static uint8_t *tofreedata;

static
void
bitmap_init(uint32_t bitblocks)
{
	size_t i, mapsize = bitblocks * SFS_BLOCKSIZE;
	bitmapdata = domalloc(mapsize * sizeof(uint8_t));
	tofreedata = domalloc(mapsize * sizeof(uint8_t));
	for (i=0; i<mapsize; i++) {
		bitmapdata[i] = tofreedata[i] = 0;
	}
}

static
const char *
blockusagestr(blockusage_t how, uint32_t howdesc)
{
	static char rv[256];
	switch (how) {
	    case B_SUPERBLOCK: return "superblock";
	    case B_BITBLOCK: return "bitmap block";
	    case B_INODE: return "inode";
	    case B_IBLOCK: 
		snprintf(rv, sizeof(rv), "indirect block of inode %lu", 
			 (unsigned long) howdesc);
		break;
	    case B_DIRDATA:
		snprintf(rv, sizeof(rv), "directory data from inode %lu", 
			 (unsigned long) howdesc);
		break;
	    case B_DATA:
		snprintf(rv, sizeof(rv), "file data from inode %lu", 
			 (unsigned long) howdesc);
		break;
	    case B_TOFREE:
		assert(0);
		break;
	    case B_PASTEND:
		return "past the end of the fs";
	}
	return rv;
}

static
void
bitmap_mark(uint32_t block, blockusage_t how, uint32_t howdesc)
{
	unsigned index = block/8;
	uint8_t mask = ((uint8_t)1)<<(block%8);

	if (how == B_TOFREE) {
		if (tofreedata[index] & mask) {
			/* already marked to free once, ignore */
			return;
		}
		if (bitmapdata[index] & mask) {
			/* block is used elsewhere, ignore */
			return;
		}
		tofreedata[index] |= mask;
		return;
	}

	if (tofreedata[index] & mask) {
		/* really using the block, don't free it */
		tofreedata[index] &= ~mask;
	}

	if (bitmapdata[index] & mask) {
		warnx("Block %lu (used as %s) already in use! (NOT FIXED)",
		      (unsigned long) block, blockusagestr(how, howdesc));
		setbadness(EXIT_UNRECOV);
	}

	bitmapdata[index] |= mask;

	if (how != B_PASTEND) {
		count_blocks++;
	}
}

static
int
countbits(uint8_t val)
{
	uint8_t x;
	int ct=0;

	for (x=1; x; x<<=1) {
		if (val & x) ct++;
	}
	return ct;
}

static
void
reportbits(uint32_t bitblock, uint32_t byte, uint8_t val, const char *what)
{
	uint8_t x, y;
	uint32_t blocknum;

	for (x=1, y=0; x; x<<=1, y++) {
		if (val & x) {
			blocknum = bitblock*SFS_BLOCKBITS + byte*CHAR_BIT + y;
			warnx("Block %lu erroneously shown %s in bitmap",
			      (unsigned long) blocknum, what);
		}
	}
}

static
void
check_bitmap(void)
{
	uint8_t bits[SFS_BLOCKSIZE], *found, *tofree, tmp;
	uint32_t alloccount=0, freecount=0, i, j;
	int bchanged;

	for (i=0; i<bitblocks; i++) {
		diskread(bits, SFS_MAP_LOCATION+i);
		swapbits(bits);
		found = bitmapdata + i*SFS_BLOCKSIZE;
		tofree = tofreedata + i*SFS_BLOCKSIZE;
		bchanged = 0;

		for (j=0; j<SFS_BLOCKSIZE; j++) {
			/* we shouldn't have blocks marked both ways */
			assert((found[j] & tofree[j])==0);

			if (bits[j]==found[j]) {
				continue;
			}

			if (bits[j]==(found[j] | tofree[j])) {
				bits[j] = found[j];
				bchanged = 1;
				continue;
			}

			/* free the ones we're freeing */
			bits[j] &= ~tofree[j];

			/* are we short any? */
			if ((bits[j] & found[j]) != found[j]) {
				tmp = found[j] & ~bits[j];
				alloccount += countbits(tmp);
				if (tmp != 0) {
					reportbits(i, j, tmp, "free");
				}
			}

			/* do we have any extra? */
			if ((bits[j] & found[j]) != bits[j]) {
				tmp = bits[j] & ~found[j];
				freecount += countbits(tmp);
				if (tmp != 0) {
					reportbits(i, j, tmp, "allocated");
				}
			}

			bits[j] = found[j];
			bchanged = 1;
		}

		if (bchanged) {
			swapbits(bits);
			diskwrite(bits, SFS_MAP_LOCATION+i);
		}
	}

	if (alloccount > 0) {
		warnx("%lu blocks erroneously shown free in bitmap (fixed)",
		      (unsigned long) alloccount);
		setbadness(EXIT_RECOV);
	}
	if (freecount > 0) {
		warnx("%lu blocks erroneously shown used in bitmap (fixed)",
		      (unsigned long) freecount);
		setbadness(EXIT_RECOV);
	}
}

////////////////////////////////////////////////////////////

struct inodememory {
	uint32_t ino;
	uint32_t linkcount;	/* files only; 0 for dirs */
};

static struct inodememory *inodes = NULL;
static int ninodes=0, maxinodes=0;

static
void
addmemory(uint32_t ino, uint32_t linkcount)
{
	assert(ninodes <= maxinodes);
	if (ninodes == maxinodes) {
#ifdef NO_REALLOC
		int newmax = (maxinodes+1)*2;
		void *p = domalloc(newmax * sizeof(struct inodememory));
		if (inodes) {
			memcpy(p, inodes, ninodes);
			free(inodes);
		}
		inodes = p;
#else
		maxinodes = (maxinodes+1)*2;
		inodes = realloc(inodes, maxinodes * sizeof(uint32_t));
		if (inodes==NULL) {
			errx(EXIT_FATAL, "Out of memory");
		}
#endif
	}
	inodes[ninodes].ino = ino;
	inodes[ninodes].linkcount = linkcount;
}

/* returns nonzero if directory already remembered */
static
int
remember_dir(uint32_t ino, const char *pathsofar)
{
	int i;

	/* don't use this for now */
	(void)pathsofar;

	for (i=0; i<ninodes; i++) {
		if (inodes[i].ino==ino) {
			assert(inodes[i].linkcount==0);
			return 1;
		}
	}

	addmemory(ino, 0);

	return 0;
}

static
void
observe_filelink(uint32_t ino)
{
	int i;
	for (i=0; i<ninodes; i++) {
		if (inodes[i].ino==ino) {
			assert(inodes[i].linkcount>0);
			inodes[i].linkcount++;
			return;
		}
	}
	bitmap_mark(ino, B_INODE, ino);
	addmemory(ino, 1);
}

static
void
adjust_filelinks(void)
{
	struct sfs_inode sfi;
	int i;

	for (i=0; i<ninodes; i++) {
		if (inodes[i].linkcount==0) {
			/* directory */
			continue;
		}
		diskread(&sfi, inodes[i].ino);
		swapinode(&sfi);
		assert(sfi.sfi_type == SFS_TYPE_FILE);
		if (sfi.sfi_linkcount != inodes[i].linkcount) {
			warnx("File %lu link count %lu should be %lu (fixed)",
			      (unsigned long) inodes[i].ino,
			      (unsigned long) sfi.sfi_linkcount,
			      (unsigned long) inodes[i].linkcount);
			sfi.sfi_linkcount = inodes[i].linkcount;
			setbadness(EXIT_RECOV);
			swapinode(&sfi);
			diskwrite(&sfi, inodes[i].ino);
		}
		count_files++;
	}
}

////////////////////////////////////////////////////////////

static
int
checknullstring(char *buf, size_t maxlen)
{
	size_t i;
	for (i=0; i<maxlen; i++) {
		if (buf[i]==0) {
			return 0;
		}
	}
	buf[maxlen-1] = 0;
	return 1;
}

static
int
checkbadstring(char *buf)
{
	size_t i;
	int rv=0;

	for (i=0; buf[i]; i++) {
		if (buf[i]==':' || buf[i]=='/') {
			buf[i] = '_';
			rv = 1;
		}
	}
	return rv;
}

////////////////////////////////////////////////////////////

static
void
check_sb(void)
{
	struct sfs_super sp;
	uint32_t i;
	int schanged=0;

	diskread(&sp, SFS_SB_LOCATION);
	swapsb(&sp);
	if (sp.sp_magic != SFS_MAGIC) {
		errx(EXIT_UNRECOV, "Not an sfs filesystem");
	}

	assert(nblocks==0);
	assert(bitblocks==0);
	nblocks = sp.sp_nblocks;
	bitblocks = SFS_BITBLOCKS(nblocks);
	assert(nblocks>0);
	assert(bitblocks>0);

	bitmap_init(bitblocks);
	for (i=nblocks; i<bitblocks*SFS_BLOCKBITS; i++) {
		bitmap_mark(i, B_PASTEND, 0);
	}

	if (checknullstring(sp.sp_volname, sizeof(sp.sp_volname))) {
		warnx("Volume name not null-terminated (fixed)");
		setbadness(EXIT_RECOV);
		schanged = 1;
	}
	if (checkbadstring(sp.sp_volname)) {
		warnx("Volume name contains illegal characters (fixed)");
		setbadness(EXIT_RECOV);
		schanged = 1;
	}

	if (schanged) {
		swapsb(&sp);
		diskwrite(&sp, SFS_SB_LOCATION);
	}

	bitmap_mark(SFS_SB_LOCATION, B_SUPERBLOCK, 0);
	for (i=0; i<bitblocks; i++) {
		bitmap_mark(SFS_MAP_LOCATION+i, B_BITBLOCK, i);
	}
}

////////////////////////////////////////////////////////////

static
void
check_indirect_block(uint32_t ino, uint32_t *ientry, uint32_t *blockp,
		     uint32_t nblocks, uint32_t *badcountp, 
		     int isdir, int indirection)
{
	uint32_t entries[SFS_DBPERIDB];
	uint32_t i, ct;

	if (*ientry !=0) {
		diskread(entries, *ientry);
		swapindir(entries);
		bitmap_mark(*ientry, B_IBLOCK, ino);
	}
	else {
		for (i=0; i<SFS_DBPERIDB; i++) {
			entries[i] = 0;
		}
	}

	if (indirection > 1) {
		for (i=0; i<SFS_DBPERIDB; i++) {
			check_indirect_block(ino, &entries[i], 
					     blockp, nblocks, 
					     badcountp,
					     isdir,
					     indirection-1);
		}
	}
	else {
		assert(indirection==1);

		for (i=0; i<SFS_DBPERIDB; i++) {
			if (*blockp < nblocks) {
				if (entries[i] != 0) {
					bitmap_mark(entries[i],
						    isdir ? B_DIRDATA : B_DATA,
						    ino);
				}
			}
			else {
				if (entries[i] != 0) {
					(*badcountp)++;
					bitmap_mark(entries[i],
						    isdir ? B_DIRDATA : B_DATA,
						    ino);
					entries[i] = 0;
				}
			}
			(*blockp)++;
		}
	}

	ct=0;
	for (i=ct=0; i<SFS_DBPERIDB; i++) {
		if (entries[i]!=0) ct++;
	}
	if (ct==0) {
		if (*ientry != 0) {
			(*badcountp)++;
			bitmap_mark(*ientry, B_TOFREE, 0);
			*ientry = 0;
		}
	}
	else {
		assert(*ientry != 0);
		if (*badcountp > 0) {
			swapindir(entries);
			diskwrite(entries, *ientry);
		}
	}
}

/* returns nonzero if inode modified */
static
int
check_inode_blocks(uint32_t ino, struct sfs_inode *sfi, int isdir)
{
	uint32_t size, block, nblocks, badcount;

	badcount = 0;

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

	for (block=0; block<SFS_NDIRECT; block++) {
		if (block < nblocks) {
			if (sfi->sfi_direct[block] != 0) {
				bitmap_mark(sfi->sfi_direct[block],
					    isdir ? B_DIRDATA : B_DATA, ino);
			}
		}
		else {
			if (sfi->sfi_direct[block] != 0) {
				badcount++;
				bitmap_mark(sfi->sfi_direct[block],
					    B_TOFREE, 0);
			}			
		}
	}

#ifdef SFS_NIDIRECT
	for (i=0; i<SFS_NIDIRECT; i++) {
		check_indirect_block(ino, &sfi->sfi_indirect[i], 
				     &block, nblocks, &badcount, isdir, 1);
	}
#else
	check_indirect_block(ino, &sfi->sfi_indirect, 
			     &block, nblocks, &badcount, isdir, 1);
#endif

#ifdef SFS_NDIDIRECT
	for (i=0; i<SFS_NDIDIRECT; i++) {
		check_indirect_block(ino, &sfi->sfi_dindirect[i], 
				     &block, nblocks, &badcount, isdir, 2);
	}
#else
#ifdef HAS_DIDIRECT
	check_indirect_block(ino, &sfi->sfi_dindirect, 
			     &block, nblocks, &badcount, isdir, 2);
#endif
#endif

#ifdef SFS_NTIDIRECT
	for (i=0; i<SFS_NTIDIRECT; i++) {
		check_indirect_block(ino, &sfi->sfi_tindirect[i], 
				     &block, nblocks, &badcount, isdir, 3);
	}
#else
#ifdef HAS_TIDIRECT
	check_indirect_block(ino, &sfi->sfi_tindirect, 
			     &block, nblocks, &badcount, isdir, 3);
#endif
#endif

	if (badcount > 0) {
		warnx("Inode %lu: %lu blocks after EOF (freed)", 
		     (unsigned long) ino, (unsigned long) badcount);
		setbadness(EXIT_RECOV);
		return 1;
	}

	return 0;
}

////////////////////////////////////////////////////////////

static
uint32_t
ibmap(uint32_t iblock, uint32_t offset, uint32_t entrysize)
{
	uint32_t entries[SFS_DBPERIDB];

	if (iblock == 0) {
		return 0;
	}

	diskread(entries, iblock);
	swapindir(entries);

	if (entrysize > 1) {
		uint32_t index = offset / entrysize;
		offset %= entrysize;
		return ibmap(entries[index], offset, entrysize/SFS_DBPERIDB);
	}
	else {
		assert(offset < SFS_DBPERIDB);
		return entries[offset];
	}
}

#define BMAP_ND   		SFS_NDIRECT
#define BMAP_D(sfi, x)		((sfi)->sfi_direct[(x)])

#ifdef SFS_NIDIRECT
#define BMAP_NI			SFS_NIDIRECT
#define BMAP_I(sfi, x)		((sfi)->sfi_indirect[(x)])
#else
#define BMAP_NI			1
#define BMAP_I(sfi, x)		((void)(x), (sfi)->sfi_indirect)
#endif

#ifdef SFS_NDIDIRECT
#define BMAP_NII		SFS_NDIDIRECT
#define BMAP_II(sfi, x)		((sfi)->sfi_dindirect[(x)])
#else
#ifdef HAS_DIDIRECT
#define BMAP_NII		1
#define BMAP_II(sfi, x)		((void)(x), (sfi)->sfi_dindirect)
#else
#define BMAP_NII		0
#define BMAP_II(sfi, x)		((void)(x), (void)(sfi), 0)
#endif
#endif

#ifdef SFS_NTIDIRECT
#define BMAP_NIII		SFS_NTIDIRECT
#define BMAP_III(sfi, x)	((sfi)->sfi_tindirect[(x)])
#else
#ifdef HAS_TIDIRECT
#define BMAP_NIII		1
#define BMAP_III(sfi, x)	((void)(x), (sfi)->sfi_tindirect)
#else
#define BMAP_NIII		0
#define BMAP_III(sfi, x)	((void)(x), (void)(sfi), 0)
#endif
#endif

#define BMAP_DMAX   BMAP_ND
#define BMAP_IMAX   (BMAP_DMAX+SFS_DBPERIDB*BMAP_NI)
#define BMAP_IIMAX  (BMAP_IMAX+SFS_DBPERIDB*BMAP_NII)
#define BMAP_IIIMAX (BMAP_IIMAX+SFS_DBPERIDB*BMAP_NIII)

#define BMAP_DSIZE	1
#define BMAP_ISIZE	(BMAP_DSIZE*SFS_DBPERIDB)
#define BMAP_IISIZE	(BMAP_ISIZE*SFS_DBPERIDB)
#define BMAP_IIISIZE	(BMAP_IISIZE*SFS_DBPERIDB)

static
uint32_t
dobmap(const struct sfs_inode *sfi, uint32_t fileblock)
{
	uint32_t iblock, offset;

	if (fileblock < BMAP_DMAX) {
		return BMAP_D(sfi, fileblock);
	}
	else if (fileblock < BMAP_IMAX) {
		iblock = (fileblock - BMAP_DMAX)/BMAP_ISIZE;
		offset = (fileblock - BMAP_DMAX)%BMAP_ISIZE;
		return ibmap(BMAP_I(sfi, iblock), offset, BMAP_DSIZE);
	}
	else if (fileblock < BMAP_IIMAX) {
		iblock = (fileblock - BMAP_IMAX)/BMAP_IISIZE;
		offset = (fileblock - BMAP_IMAX)%BMAP_IISIZE;
		return ibmap(BMAP_II(sfi, iblock), offset, BMAP_ISIZE);
	}
	else if (fileblock < BMAP_IIIMAX) {
		iblock = (fileblock - BMAP_IIMAX)/BMAP_IIISIZE;
		offset = (fileblock - BMAP_IIMAX)%BMAP_IIISIZE;
		return ibmap(BMAP_III(sfi, iblock), offset, BMAP_IISIZE);
	}
	return 0;
}

static
void
dirread(struct sfs_inode *sfi, struct sfs_dir *d, unsigned nd)
{
	const unsigned atonce = SFS_BLOCKSIZE/sizeof(struct sfs_dir);
	unsigned nblocks = SFS_ROUNDUP(nd, atonce) / atonce;
	unsigned i, j;

	for (i=0; i<nblocks; i++) {
		uint32_t block = dobmap(sfi, i);
		if (block!=0) {
			diskread(d + i*atonce, block);
			for (j=0; j<atonce; j++) {
				swapdir(&d[i*atonce+j]);
			}
		}
		else {
			warnx("Warning: sparse directory found");
			bzero(d + i*atonce, SFS_BLOCKSIZE);
		}
	}
}

static
void
dirwrite(const struct sfs_inode *sfi, struct sfs_dir *d, int nd)
{
	const unsigned atonce = SFS_BLOCKSIZE/sizeof(struct sfs_dir);
	unsigned nblocks = SFS_ROUNDUP(nd, atonce) / atonce;
	unsigned i, j, bad;

	for (i=0; i<nblocks; i++) {
		uint32_t block = dobmap(sfi, i);
		if (block!=0) {
			for (j=0; j<atonce; j++) {
				swapdir(&d[i*atonce+j]);
			}
			diskwrite(d + i*atonce, block);
		}
		else {
			for (j=bad=0; j<atonce; j++) {
				if (d[i*atonce+j].sfd_ino != SFS_NOINO ||
				    d[i*atonce+j].sfd_name[0] != 0) {
					bad = 1;
				}
			}
			if (bad) {
				warnx("Cannot write to missing block in "
				      "sparse directory (ERROR)");
				setbadness(EXIT_UNRECOV);
			}
		}
	}
}

////////////////////////////////////////////////////////////

static struct sfs_dir *global_sortdirs;
static
int
dirsortfunc(const void *aa, const void *bb)
{
	const int *a = (const int *)aa;
	const int *b = (const int *)bb;
	const struct sfs_dir *ad = &global_sortdirs[*a];
	const struct sfs_dir *bd = &global_sortdirs[*b];
	return strcmp(ad->sfd_name, bd->sfd_name);
}

#ifdef NO_QSORT
static
void
qsort(int *data, int num, size_t size, int (*f)(const void *, const void *))
{
	int i, j;
	(void)size;

	/* because I'm lazy, bubble sort */
	for (i=0; i<num-1; i++) {
		for (j=i+1; j<num; j++) {
			if (f(&data[i], &data[j]) < 0) {
				int tmp = data[i];
				data[i] = data[j];
				data[j] = tmp;
			}
		}
	}
}
#endif

static
void
sortdir(int *vector, struct sfs_dir *d, int nd)
{
	global_sortdirs = d;
	qsort(vector, nd, sizeof(int), dirsortfunc);
}

/* tries to add a directory entry; returns 0 on success */
static
int
dir_tryadd(struct sfs_dir *d, int nd, const char *name, uint32_t ino)
{
	int i;
	for (i=0; i<nd; i++) {
		if (d[i].sfd_ino==SFS_NOINO) {
			d[i].sfd_ino = ino;
			assert(strlen(name) < sizeof(d[i].sfd_name));
			strcpy(d[i].sfd_name, name);
			return 0;
		}
	}
	return -1;
}

static
int
check_dir_entry(const char *pathsofar, uint32_t index, struct sfs_dir *sfd)
{
	int dchanged = 0;

	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",
			      pathsofar, (unsigned long) index);
			sfd->sfd_name[0] = 0;
			dchanged = 1;
		}
	}
	else {
		if (sfd->sfd_name[0] == 0) {
			snprintf(sfd->sfd_name, sizeof(sfd->sfd_name),
				 "FSCK.%lu.%lu",
				 (unsigned long) sfd->sfd_ino,
				 (unsigned long) uniquecounter++);
			setbadness(EXIT_RECOV);
			warnx("Directory /%s entry %lu has file but "
			      "no name (fixed: %s)",
			      pathsofar, (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)",
			      pathsofar, (unsigned long) index);
			dchanged = 1;
		}
		if (checkbadstring(sfd->sfd_name)) {
			setbadness(EXIT_RECOV);
			warnx("Directory /%s entry %lu contains invalid "
			      "characters (fixed)",
			      pathsofar, (unsigned long) index);
			dchanged = 1;
		}
	}
	return dchanged;
}

////////////////////////////////////////////////////////////

static
int
check_dir(uint32_t ino, uint32_t parentino, const char *pathsofar)
{
	struct sfs_inode sfi;
	struct sfs_dir *direntries;
	int *sortvector;
	uint32_t dirsize, ndirentries, maxdirentries, subdircount, i;
	int ichanged=0, dchanged=0, dotseen=0, dotdotseen=0;

	diskread(&sfi, ino);
	swapinode(&sfi);

	if (remember_dir(ino, pathsofar)) {
		/* crosslinked dir */
		return 1;
	}

	bitmap_mark(ino, B_INODE, ino);
	count_dirs++;

	if (sfi.sfi_size % sizeof(struct sfs_dir) != 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_dir));
		ichanged = 1;
	}

	if (check_inode_blocks(ino, &sfi, 1)) {
		ichanged = 1;
	}

	ndirentries = sfi.sfi_size/sizeof(struct sfs_dir);
	maxdirentries = SFS_ROUNDUP(ndirentries, 
				    SFS_BLOCKSIZE/sizeof(struct sfs_dir));
	dirsize = maxdirentries * sizeof(struct sfs_dir);
	direntries = domalloc(dirsize);
	sortvector = domalloc(ndirentries * sizeof(int));

	dirread(&sfi, direntries, ndirentries);
	for (i=ndirentries; i<maxdirentries; i++) {
		direntries[i].sfd_ino = SFS_NOINO;
		bzero(direntries[i].sfd_name, sizeof(direntries[i].sfd_name));
	}

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

	sortdir(sortvector, direntries, ndirentries);

	/* don't use ndirentries-1 here in case ndirentries == 0 */
	for (i=0; i+1<ndirentries; i++) {
		struct sfs_dir *d1 = &direntries[sortvector[i]];
		struct sfs_dir *d2 = &direntries[sortvector[i+1]];
		assert(d1 != d2);

		if (d1->sfd_ino == SFS_NOINO) {
			continue;
		}

		if (!strcmp(d1->sfd_name, d2->sfd_name)) {
			if (d1->sfd_ino == d2->sfd_ino) {
				setbadness(EXIT_RECOV);
				warnx("Directory /%s: Duplicate entries for "
				      "%s (merged)",
				      pathsofar, d1->sfd_name);
				d1->sfd_ino = SFS_NOINO;
				d1->sfd_name[0] = 0;
			}
			else {
				snprintf(d1->sfd_name, sizeof(d1->sfd_name),
					 "FSCK.%lu.%lu",
					 (unsigned long) d1->sfd_ino,
					 (unsigned long) uniquecounter++);
				setbadness(EXIT_RECOV);
				warnx("Directory /%s: Duplicate names %s "
				      "(one renamed: %s)",
				      pathsofar, d2->sfd_name, d1->sfd_name);
			}
			dchanged = 1;
		}
	}

	for (i=0; i<ndirentries; i++) {
		if (!strcmp(direntries[i].sfd_name, ".")) {
			if (direntries[i].sfd_ino != ino) {
				setbadness(EXIT_RECOV);
				warnx("Directory /%s: Incorrect `.' entry "
				      "(fixed)", pathsofar);
				direntries[i].sfd_ino = ino;
				dchanged = 1;
			}
			assert(dotseen==0); /* due to duplicate checking */
			dotseen = 1;
		}
		else if (!strcmp(direntries[i].sfd_name, "..")) {
			if (direntries[i].sfd_ino != parentino) {
				setbadness(EXIT_RECOV);
				warnx("Directory /%s: Incorrect `..' entry "
				      "(fixed)", pathsofar);
				direntries[i].sfd_ino = parentino;
				dchanged = 1;
			}
			assert(dotdotseen==0); /* due to duplicate checking */
			dotdotseen = 1;
		}
	}

	if (!dotseen) {
		if (dir_tryadd(direntries, ndirentries, ".", ino)==0) {
			setbadness(EXIT_RECOV);
			warnx("Directory /%s: No `.' entry (added)",
			      pathsofar);
			dchanged = 1;
		}
		else if (dir_tryadd(direntries, maxdirentries, ".", ino)==0) {
			setbadness(EXIT_RECOV);
			warnx("Directory /%s: No `.' entry (added)",
			      pathsofar);
			ndirentries++;
			dchanged = 1;
			sfi.sfi_size += sizeof(struct sfs_dir);
			ichanged = 1;
		}
		else {
			setbadness(EXIT_UNRECOV);
			warnx("Directory /%s: No `.' entry (NOT FIXED)",
			      pathsofar);
		}
	}

	if (!dotdotseen) {
		if (dir_tryadd(direntries, ndirentries, "..", parentino)==0) {
			setbadness(EXIT_RECOV);
			warnx("Directory /%s: No `..' entry (added)",
			      pathsofar);
			dchanged = 1;
		}
		else if (dir_tryadd(direntries, maxdirentries, "..", 
				    parentino)==0) {
			setbadness(EXIT_RECOV);
			warnx("Directory /%s: No `..' entry (added)",
			      pathsofar);
			ndirentries++;
			dchanged = 1;
			sfi.sfi_size += sizeof(struct sfs_dir);
			ichanged = 1;
		}
		else {
			setbadness(EXIT_UNRECOV);
			warnx("Directory /%s: No `..' entry (NOT FIXED)",
			      pathsofar);
		}
	}

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

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

			switch (subsfi.sfi_type) {
			    case SFS_TYPE_FILE:
				if (check_inode_blocks(direntries[i].sfd_ino,
						       &subsfi, 0)) {
					swapinode(&subsfi);
					diskwrite(&subsfi, 
						  direntries[i].sfd_ino);
				}
				observe_filelink(direntries[i].sfd_ino);
				break;
			    case SFS_TYPE_DIR:
				if (check_dir(direntries[i].sfd_ino,
					      ino,
					      path)) {
					setbadness(EXIT_RECOV);
					warnx("Directory /%s: Crosslink to "
					      "other directory (removed)",
					      path);
					direntries[i].sfd_ino = SFS_NOINO;
					direntries[i].sfd_name[0] = 0;
					dchanged = 1;
				}
				else {
					subdircount++;
				}
				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 (sfi.sfi_linkcount != subdircount+2) {
		setbadness(EXIT_RECOV);
		warnx("Directory /%s: Link count %lu should be %lu (fixed)",
		      pathsofar, (unsigned long) sfi.sfi_linkcount,
		      (unsigned long) subdircount+2);
		sfi.sfi_linkcount = subdircount+2;
		ichanged = 1;
	}

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

	if (ichanged) {
		swapinode(&sfi);
		diskwrite(&sfi, ino);
	}

	free(direntries);
	free(sortvector);

	return 0;
}


static
void
check_root_dir(void)
{
	struct sfs_inode sfi;
	diskread(&sfi, SFS_ROOT_LOCATION);
	swapinode(&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;
		swapinode(&sfi);
		diskwrite(&sfi, SFS_ROOT_LOCATION);
		break;
	}

	check_dir(SFS_ROOT_LOCATION, SFS_ROOT_LOCATION, "");
}

////////////////////////////////////////////////////////////

int
main(int argc, char **argv)
{
#ifdef HOST
	hostcompat_init(argc, argv);
#endif

	if (argc!=2) {
		errx(EXIT_USAGE, "Usage: sfsck device/diskfile");
	}

	assert(sizeof(struct sfs_super)==SFS_BLOCKSIZE);
	assert(sizeof(struct sfs_inode)==SFS_BLOCKSIZE);
	assert(SFS_BLOCKSIZE % sizeof(struct sfs_dir) == 0);

	opendisk(argv[1]);

	check_sb();
	check_root_dir();
	check_bitmap();
	adjust_filelinks();

	closedisk();

	warnx("%lu blocks used (of %lu); %lu directories; %lu files",
	      count_blocks, (unsigned long) nblocks, count_dirs, count_files);

	switch (badness) {
	    case EXIT_USAGE:
	    case EXIT_FATAL:
	    default:
		/* not supposed to happen here */
		assert(0);
		break;
	    case EXIT_UNRECOV:
		warnx("WARNING - unrecoverable errors. Maybe try again?");
		break;
	    case EXIT_RECOV:
		warnx("Caution - filesystem modified. Run again for luck.");
		break;
	    case EXIT_CLEAN:
		break;
	}

	return badness;
}