HardLinkCheck.c   [plain text]

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */

#include "Scavenger.h"

#define DEBUG_HARDLINKCHECK 0

#define kBadLinkID 0xffffffff

/* info saved for each indirect link encountered */
struct IndirectLinkInfo {
	UInt32	linkID;
	UInt32	linkCount;
};

struct HardLinkInfo {
	UInt32	privDirID;
	UInt32	linkSlots;
	UInt32	slotsUsed;
	SGlobPtr globals;
	struct IndirectLinkInfo *linkInfo;
};


HFSPlusCatalogKey gMetaDataDirKey = {
	48,		/* key length */
	2,		/* parent directory ID */
	{
		21,	/* number of unicode characters */
		{
			'\0','\0','\0','\0',
			'H','F','S','+',' ',
			'P','r','i','v','a','t','e',' ',
			'D','a','t','a'
		}
	}
};


/* private local routines */
static int  GetPrivateDir(SGlobPtr gp, CatalogRecord *rec);
static int  RecordOrphanINode(SGlobPtr gp, UInt32 parID, char * filename);
static int  RecordBadLinkCount(SGlobPtr gp, UInt32 parID, char * filename,
                                int badcnt, int goodcnt);
static void hash_insert(UInt32 linkID, int m, int n, struct IndirectLinkInfo *linkInfo);
static struct IndirectLinkInfo * hash_search(UInt32 linkID, int m, int n, struct IndirectLinkInfo *linkInfo);

int average_miss_probe = 0;
int average_hit_probe = 0;

#if DEBUG_HARDLINKCHECK
int hash_search_hits = 0;
int hash_search_misses = 0;
#endif // DEBUG_HARDLINKCHECK

/*
 * HardLinkCheckBegin
 *
 * Get ready to capture indirect link info.
 * Called before iterating over all the catalog leaf nodes.
 */
int
HardLinkCheckBegin(SGlobPtr gp, void** cookie)
{
	struct HardLinkInfo *info;
	CatalogRecord rec;
	UInt32 folderID;
	int entries, slots;

	if (GetPrivateDir(gp, &rec) == 0 && rec.hfsPlusFolder.valence != 0) {
		entries = rec.hfsPlusFolder.valence + 10;
		folderID = rec.hfsPlusFolder.folderID;
	} else {
		entries = 1000;
		folderID = 0;
	}
	
	for (slots = 1; slots <= entries; slots <<= 1)
		continue;
	if (slots < (entries + (entries/3)))
		slots <<= 1;
		
#if DEBUG_HARDLINKCHECK
	printf("hash table size is %d for %d entries\n", slots, entries); 
#endif // DEBUG_HARDLINKCHECK

	info = (struct HardLinkInfo *) malloc(sizeof(struct HardLinkInfo));
	info->linkInfo = (struct IndirectLinkInfo *) calloc(slots, sizeof(struct IndirectLinkInfo));

	info->privDirID = folderID;
	info->linkSlots = slots;
	info->slotsUsed = 0;
	info->globals = gp;
	
	* cookie = info;
	return (0);
}

/*
 * HardLinkCheckEnd
 *
 * Dispose of captured data.
 * Called after calling CheckHardLinks.
 */
void
HardLinkCheckEnd(void * cookie)
{
	if (cookie) {
		struct HardLinkInfo *		infoPtr;
		
		infoPtr = (struct HardLinkInfo *) cookie;
		if (infoPtr->linkInfo) {

#if DEBUG_HARDLINKCHECK
{
	struct IndirectLinkInfo *	linkInfoPtr;
	int		i;
	printf("hash table summary:\n");
	linkInfoPtr = infoPtr->linkInfo;
	for (i = 0; i < infoPtr->linkSlots; ++linkInfoPtr, ++i) {
		printf("%5d --> %d (%d)\n", i, linkInfoPtr->linkID, linkInfoPtr->linkCount);
	}
}
#endif // DEBUG_HARDLINKCHECK

			DisposeMemory(infoPtr->linkInfo);
		}
		DisposeMemory(cookie);
	}
}

/*
 * CaptureHardLink
 *
 * Capture indirect link info.
 * Called for every indirect link in the catalog.
 */
void
CaptureHardLink(void * cookie, UInt32 linkID)
{
	struct HardLinkInfo * info = (struct HardLinkInfo *) cookie;
	struct IndirectLinkInfo *linkInfo;

	if (linkID == 0)
		linkID = kBadLinkID;	/* reported later */
	linkInfo = hash_search(linkID, info->linkSlots, info->slotsUsed, info->linkInfo);
	if (linkInfo)
		++linkInfo->linkCount;
	else
		hash_insert(linkID, info->linkSlots, info->slotsUsed++, info->linkInfo);
}

/*
 * CheckHardLinks
 *
 * Check indirect node link counts aginst the indirect
 * links that were found. There are 4 possible problems
 * that can occur.
 *  1. orphaned indirect node (i.e. no links found)
 *  2. orphaned indirect link (i.e. indirect node missing)
 *  3. incorrect link count
 *  4. indirect link id was 0 (i.e. link id wasn't preserved)
 */
int
CheckHardLinks(void *cookie)
{
	struct HardLinkInfo *info = (struct HardLinkInfo *)cookie;
	SGlobPtr gp;
	UInt32              folderID;
	UInt32 linkID;
	SFCB              * fcb;
	CatalogRecord       rec;
	HFSPlusCatalogKey * keyp;
	BTreeIterator       iterator;
	FSBufferDescriptor  btrec;
	UInt16              reclen;
	size_t              len;
	int linkCount;
	int prefixlen;
	int result;
	struct IndirectLinkInfo * linkInfo;
	char filename[64];

	/* All done if no hard links exist. */
	if (info == NULL || (info->privDirID == 0 && info->slotsUsed == 0))
		return (0);

	gp = info->globals;
	PrintStatus(gp, M_MultiLinkChk, 0);

	folderID = info->privDirID;
	linkInfo = info->linkInfo;

#if DEBUG_HARDLINKCHECK
	printf("hashtable: %d entries inserted, %d search hits, %d search misses\n",
			info->slotsUsed, hash_search_hits, hash_search_misses);
	printf("average_miss_probe = %d, average_hit_probe = %d\n",
			average_miss_probe/hash_search_misses, average_hit_probe/hash_search_hits);
#endif // DEBUG_HARDLINKCHECK

	fcb = gp->calculatedCatalogFCB;
	prefixlen = strlen(HFS_INODE_PREFIX);
	ClearMemory(&iterator, sizeof(iterator));
	keyp = (HFSPlusCatalogKey*)&iterator.key;
	btrec.bufferAddress = &rec;
	btrec.itemCount = 1;
	btrec.itemSize = sizeof(rec);
	/*
	 * position iterator at folder thread record
	 * (i.e. one record before first child)
	 */
	ClearMemory(&iterator, sizeof(iterator));
	BuildCatalogKey(folderID, NULL, true, (CatalogKey *)keyp);
	result = BTSearchRecord(fcb, &iterator, kInvalidMRUCacheKey, &btrec,
				&reclen, &iterator);
	if (result) goto exit;

	/* Visit all the children in private directory. */
	for (;;) {
		result = BTIterateRecord(fcb, kBTreeNextRecord, &iterator,
					&btrec, &reclen);
		if (result || keyp->parentID != folderID)
			break;
		if (rec.recordType != kHFSPlusFileRecord)
			continue;

		(void) utf_encodestr(keyp->nodeName.unicode,
					keyp->nodeName.length * 2,
					filename, &len);
		filename[len] = '\0';
		
		if ( 	(strstr(filename, HFS_DELETE_PREFIX) == filename) &&
				(gp->calculatedVCB->vcbDriverWriteRef != -1) ) {
				
			RecordOrphanINode(gp, folderID, filename);
			continue;		
		}
				
		if (strstr(filename, HFS_INODE_PREFIX) != filename)
			continue;
		
		linkID = atol(&filename[prefixlen]);
		linkCount = rec.hfsPlusFile.bsdInfo.special.linkCount;
		linkInfo = hash_search(linkID, info->linkSlots, info->slotsUsed, info->linkInfo);
		if (linkInfo) {
			if (linkCount != linkInfo->linkCount)
				RecordBadLinkCount(gp, folderID, filename,
						   linkCount, linkInfo->linkCount);
		} else {
			/* no match means this is an orphan indirect node */
			RecordOrphanINode(gp, folderID, filename);
		}
		filename[0] = '\0';
	}

	/*
	 * Any remaining indirect links are orphans.
	 *
	 * TBD: what to do with them...
	 */
#if 0
	if (gp->logLevel >= kDebugLog) {
	    for (i = 0; i < info->slotsUsed; ++i) {
		if (linkInfo[i].linkID == kBadLinkID) {
		    printf("missing link number (copied under Mac OS 9 ?)\n");
		    /*
		     * To do: loop through each file ID and report
		     */
		} else if (linkInfo[i].linkID != 0) {
		    printf("\torphaned link (indirect node %d missing)\n", linkInfo[i].linkID);
		}
	}
#endif

exit:
	return (result);
}

/*
 * GetPrivateDir
 *
 * Get catalog entry for the "HFS+ Private Data" directory.
 * The indirect nodes are stored in this directory.
 */
static int
GetPrivateDir(SGlobPtr gp, CatalogRecord * rec)
{
	HFSPlusCatalogKey * keyp;
	BTreeIterator       iterator;
	FSBufferDescriptor  btrec;
	UInt16              reclen;
	int                 result;
	Boolean 			isHFSPlus;

	isHFSPlus = VolumeObjectIsHFSPlus( );
	if (!isHFSPlus)
		return (-1);

	ClearMemory(&iterator, sizeof(iterator));
	keyp = (HFSPlusCatalogKey*)&iterator.key;

	btrec.bufferAddress = rec;
	btrec.itemCount = 1;
	btrec.itemSize = sizeof(CatalogRecord);

	/* look up record for HFS+ private folder */
	ClearMemory(&iterator, sizeof(iterator));
	CopyMemory(&gMetaDataDirKey, keyp, sizeof(gMetaDataDirKey));
	result = BTSearchRecord(gp->calculatedCatalogFCB, &iterator,
	                        kInvalidMRUCacheKey, &btrec, &reclen, &iterator);

	return (result);
}

/*
 * RecordOrphanINode
 *
 * Record a repair to delete an orphaned indirect node.
 */
static int
RecordOrphanINode(SGlobPtr gp, UInt32 parID, char* filename)
{
	RepairOrderPtr p;
	int n;
	
	PrintError(gp, E_UnlinkedFile, 1, filename);
	
	n = strlen(filename);
	p = AllocMinorRepairOrder(gp, n + 1);
	if (p == NULL)
		return (R_NoMem);

	p->type = E_UnlinkedFile;
	p->correct = 0;
	p->incorrect = 0;
	p->hint = 0;
	p->parid = parID;
	p->name[0] = n;  /* pascal string */
	CopyMemory(filename, &p->name[1], n);

	gp->CatStat |= S_UnlinkedFile;
	return (noErr);
}


/* 
 * RecordBadLinkCount
 *
 * Record a repair to adjust an indirect node's link count.
 */
static int
RecordBadLinkCount(SGlobPtr gp, UInt32 parID, char * filename,
                   int badcnt, int goodcnt)
{
	RepairOrderPtr p;
	char goodstr[16];
	char badstr[16];
	int n;
	
	PrintError(gp, E_InvalidLinkCount, 1, filename);
	sprintf(goodstr, "%d", goodcnt);
	sprintf(badstr, "%d", badcnt);
	PrintError(gp, E_BadValue, 2, goodstr, badstr);

	n = strlen(filename);
	p = AllocMinorRepairOrder(gp, n + 1);
	if (p == NULL)
		return (R_NoMem);

	p->type = E_InvalidLinkCount;
	p->incorrect = badcnt;
	p->correct = goodcnt;
	p->hint = 0;
	p->parid = parID;
	p->name[0] = n;  /* pascal string */
	CopyMemory(filename, &p->name[1], n);

	gp->CatStat |= S_LinkCount;
	return (0);
}


static void
hash_insert(UInt32 linkID, int m, int n, struct IndirectLinkInfo *linkInfo)
{
	int i, last;
	
	i = linkID & (m - 1);
	
	last = (i + (m-1)) % m;
	while ((i != last) && (linkInfo[i].linkID != 0) && (linkInfo[i].linkID != linkID))
		i = (i + 1) % m;
	
	if (linkInfo[i].linkID == 0) {
		linkInfo[i].linkID = linkID;
		linkInfo[i].linkCount = 1;
	} else if (linkInfo[i].linkID == linkID) {
		printf("hash: duplicate insert! (%d)\n", linkID);
		exit(13);
	} else {
		printf("hash table full (%d entries) \n", n);
		exit(14);
	}
}


static struct IndirectLinkInfo *
hash_search(UInt32 linkID, int m, int n, struct IndirectLinkInfo *linkInfo)
{
	int i, last;
	int p = 1;

	
	i = linkID & (m - 1);

	last = (i + (n-1)) % m;
	while ((i != last) && linkInfo[i].linkID && (linkInfo[i].linkID != linkID)) {
		i = (i + 1) % m;
		++p;
	}
	
	if (linkInfo[i].linkID == linkID) {
#if DEBUG_HARDLINKCHECK
		++hash_search_hits;
#endif // DEBUG_HARDLINKCHECK
		average_hit_probe += p;
		return (&linkInfo[i]);
	} else {
#if DEBUG_HARDLINKCHECK
		++hash_search_misses;
#endif // DEBUG_HARDLINKCHECK
		average_miss_probe += p;
		return (NULL);
	}
}