#include "Scavenger.h"
#include "SRuntime.h"
#include <sys/stat.h>
#include <ctype.h>
OSErr GetCatalogRecordByID(SGlobPtr GPtr, UInt32 file_id, Boolean isHFSPlus, CatalogKey *key, CatalogRecord *rec, uint16_t *recsize)
{
int retval = 0;
SFCB *fcb;
BTreeControlBlock *btcb;
FSBufferDescriptor buf_desc;
BTreeIterator search_iterator;
BTreeIterator result_iterator;
fcb = GPtr->calculatedCatalogFCB;
btcb = (BTreeControlBlock *)fcb->fcbBtree;
bzero(&buf_desc, sizeof(buf_desc));
bzero(&search_iterator, sizeof(search_iterator));
buf_desc.bufferAddress = rec;
buf_desc.itemCount = 1;
buf_desc.itemSize = sizeof(CatalogRecord);
BuildCatalogKey(file_id, NULL, isHFSPlus, (CatalogKey *)&(search_iterator.key));
retval = BTSearchRecord(fcb, &search_iterator, kInvalidMRUCacheKey,
&buf_desc, recsize, &result_iterator);
if (retval) {
goto out;
}
if (isHFSPlus) {
if ((rec->recordType != kHFSPlusFolderThreadRecord) &&
(rec->recordType != kHFSPlusFileThreadRecord)) {
retval = ENOENT;
goto out;
}
} else {
if ((rec->recordType != kHFSFolderThreadRecord) &&
(rec->recordType != kHFSFileThreadRecord)) {
retval = ENOENT;
goto out;
}
}
bzero(&buf_desc, sizeof(buf_desc));
bzero(&search_iterator, sizeof(search_iterator));
buf_desc.bufferAddress = rec;
buf_desc.itemCount = 1;
buf_desc.itemSize = sizeof(CatalogRecord);
if (isHFSPlus) {
BuildCatalogKey(rec->hfsPlusThread.parentID,
(CatalogName *)&(rec->hfsPlusThread.nodeName),
isHFSPlus, (CatalogKey *)&(search_iterator.key));
} else {
BuildCatalogKey(rec->hfsThread.parentID,
(CatalogName *)&(rec->hfsThread.nodeName),
isHFSPlus, (CatalogKey *)&(search_iterator.key));
}
retval = BTSearchRecord(fcb, &search_iterator, kInvalidMRUCacheKey,
&buf_desc, recsize, &result_iterator);
if (retval) {
goto out;
}
bcopy(&(result_iterator.key), key, CalcKeySize(btcb, &(result_iterator.key)));
out:
return retval;
}
static int record_privdir_bad_perm(SGlobPtr gptr, uint32_t cnid)
{
RepairOrderPtr p;
RcdError (gptr, E_BadPermPrivDir);
p = AllocMinorRepairOrder(gptr, 0);
if (p == NULL) {
return ENOMEM;
}
p->type = E_BadPermPrivDir;
p->parid = cnid;
gptr->CatStat |= S_LinkErrRepair;
return 0;
}
int record_link_badflags(SGlobPtr gptr, uint32_t link_id, Boolean isdir,
uint32_t incorrect, uint32_t correct)
{
RepairOrderPtr p;
char str1[12];
char str2[12];
fsckPrint(gptr->context, isdir? E_DirLinkBadFlags : E_FileLinkBadFlags, link_id);
snprintf(str1, sizeof(str1), "0x%x", correct);
snprintf(str2, sizeof(str2), "0x%x", incorrect);
fsckPrint(gptr->context, E_BadValue, str1, str2);
p = AllocMinorRepairOrder(gptr, 0);
if (p == NULL) {
return ENOMEM;
}
p->type = isdir ? E_DirLinkBadFlags : E_FileLinkBadFlags;
p->correct = correct;
p->incorrect = incorrect;
p->parid = link_id;
gptr->CatStat |= S_LinkErrRepair;
return 0;
}
int record_inode_badflags(SGlobPtr gptr, uint32_t inode_id, Boolean isdir,
uint32_t incorrect, uint32_t correct, Boolean check_duplicates)
{
RepairOrderPtr p;
char str1[12];
char str2[12];
p = AllocMinorRepairOrder(gptr, 0);
if (p == NULL) {
return ENOMEM;
}
p->type = isdir ? E_DirInodeBadFlags : E_FileInodeBadFlags;
p->correct = correct;
p->incorrect = incorrect;
p->parid = inode_id;
gptr->CatStat |= S_LinkErrRepair;
if ((check_duplicates != 0) &&
(IsDuplicateRepairOrder(gptr, p) == 1)) {
DeleteRepairOrder(gptr, p);
} else {
fsckPrint(gptr->context, isdir? E_DirInodeBadFlags : E_FileInodeBadFlags, inode_id);
snprintf(str1, sizeof(str1), "0x%x", correct);
snprintf(str2, sizeof(str2), "0x%x", incorrect);
fsckPrint(gptr->context, E_BadValue, str1, str2);
}
return 0;
}
static int record_inode_badparent(SGlobPtr gptr, uint32_t inode_id, Boolean isdir,
uint32_t incorrect, uint32_t correct)
{
char str1[12];
char str2[12];
fsckPrint(gptr->context, isdir? E_DirInodeBadParent : E_FileInodeBadParent, inode_id);
snprintf(str1, sizeof(str1), "%u", correct);
snprintf(str2, sizeof(str2), "%u", incorrect);
fsckPrint(gptr->context, E_BadValue, str1, str2);
gptr->CatStat |= S_LinkErrNoRepair;
return 0;
}
static int record_inode_badname(SGlobPtr gptr, uint32_t inode_id,
char *incorrect, char *correct)
{
fsckPrint(gptr->context, E_DirInodeBadName, inode_id);
fsckPrint(gptr->context, E_BadValue, correct, incorrect);
gptr->CatStat |= S_LinkErrNoRepair;
return 0;
}
void record_link_badchain(SGlobPtr gptr, Boolean isdir)
{
int fval = (isdir ? S_DirHardLinkChain : S_FileHardLinkChain);
int err = (isdir ? E_DirHardLinkChain : E_FileHardLinkChain);
if ((gptr->CatStat & fval) == 0) {
fsckPrint(gptr->context, err);
gptr->CatStat |= fval;
}
}
int record_dirlink_badownerflags(SGlobPtr gptr, uint32_t file_id,
uint8_t incorrect, uint8_t correct, int check_duplicates)
{
RepairOrderPtr p;
char str1[12];
char str2[12];
p = AllocMinorRepairOrder(gptr, 0);
if (p == NULL) {
return ENOMEM;
}
p->type = E_DirHardLinkOwnerFlags;
p->correct = correct;
p->incorrect = incorrect;
p->parid = file_id;
gptr->CatStat |= S_LinkErrRepair;
if ((check_duplicates != 0) &&
(IsDuplicateRepairOrder(gptr, p) == 1)) {
DeleteRepairOrder(gptr, p);
} else {
fsckPrint(gptr->context, E_DirHardLinkOwnerFlags, file_id);
snprintf(str1, sizeof(str1), "0x%x", correct);
snprintf(str2, sizeof(str2), "0x%x", incorrect);
fsckPrint(gptr->context, E_BadValue, str1, str2);
}
return 0;
}
int record_link_badfinderinfo(SGlobPtr gptr, uint32_t file_id, Boolean isdir)
{
RepairOrderPtr p;
p = AllocMinorRepairOrder(gptr, 0);
if (p == NULL) {
return ENOMEM;
}
p->type = isdir ? E_DirHardLinkFinderInfo : E_FileHardLinkFinderInfo;
p->parid = file_id;
gptr->CatStat |= (isdir ? S_DirHardLinkChain : S_FileHardLinkChain);
if (IsDuplicateRepairOrder(gptr, p) == 1) {
DeleteRepairOrder(gptr, p);
} else {
fsckPrint(gptr->context, p->type, file_id);
}
return 0;
}
static int record_parent_badflags(SGlobPtr gptr, uint32_t dir_id,
uint32_t incorrect, uint32_t correct)
{
RepairOrderPtr p;
char str1[12];
char str2[12];
p = AllocMinorRepairOrder(gptr, 0);
if (p == NULL) {
return ENOMEM;
}
p->type = E_DirLinkAncestorFlags;
p->correct = correct;
p->incorrect = incorrect;
p->parid = dir_id;
gptr->CatStat |= S_LinkErrRepair;
if (IsDuplicateRepairOrder(gptr, p) == 1) {
DeleteRepairOrder(gptr, p);
} else {
fsckPrint(gptr->context, E_DirLinkAncestorFlags, dir_id);
snprintf(str1, sizeof(str1), "0x%x", correct);
snprintf(str2, sizeof(str2), "0x%x", incorrect);
fsckPrint(gptr->context, E_BadValue, str1, str2);
}
return 0;
}
static int priv_dir_lookup(SGlobPtr gptr, CatalogKey *key, CatalogRecord *rec)
{
int i;
int retval;
char *dirname = HFSPLUS_DIR_METADATA_FOLDER;
CatalogName cat_dirname;
uint16_t recsize;
uint32_t hint;
cat_dirname.ustr.length = strlen(dirname);
for (i = 0; i < cat_dirname.ustr.length; i++) {
cat_dirname.ustr.unicode[i] = (u_int16_t) dirname[i];
}
BuildCatalogKey(kHFSRootFolderID, &cat_dirname, true, key);
retval = SearchBTreeRecord (gptr->calculatedCatalogFCB, key, kNoHint,
NULL, rec, &recsize, &hint);
return retval;
}
int dirhardlink_init(SGlobPtr gptr)
{
int retval = 0;
CatalogRecord rec;
CatalogKey key;
if (VolumeObjectIsHFSPlus() == false) {
goto out;
}
retval = priv_dir_lookup(gptr, &key, &rec);
if (retval == 0) {
gptr->dirlink_priv_dir_id = rec.hfsPlusFolder.folderID;
gptr->dirlink_priv_dir_valence = rec.hfsPlusFolder.valence;
} else {
gptr->dirlink_priv_dir_id = 0;
gptr->dirlink_priv_dir_valence = 0;
}
retval = 0;
out:
return retval;
}
static void dirlink_priv_dir_check(SGlobPtr gptr, HFSPlusCatalogFolder *rec,
HFSPlusCatalogKey *key)
{
if (((rec->bsdInfo.ownerFlags & UF_IMMUTABLE) == 0) ||
((rec->bsdInfo.fileMode & S_ISVTX) == 0)) {
record_privdir_bad_perm(gptr, rec->folderID);
}
}
int get_first_link_id(SGlobPtr gptr, CatalogRecord *inode_rec, uint32_t inode_id,
Boolean isdir, uint32_t *first_link_id)
{
int retval = 0;
int i;
BTreeIterator iterator;
FSBufferDescriptor bt_data;
HFSPlusAttrData *rec;
HFSPlusAttrKey *key;
u_int8_t attrdata[FIRST_LINK_XATTR_REC_SIZE];
size_t unicode_bytes = 0;
bzero(&iterator, sizeof(iterator));
if (isdir) {
key = (HFSPlusAttrKey *)&iterator.key;
utf_decodestr((unsigned char *)FIRST_LINK_XATTR_NAME,
strlen(FIRST_LINK_XATTR_NAME), key->attrName,
&unicode_bytes, sizeof(key->attrName));
key->attrNameLen = unicode_bytes / sizeof(UniChar);
key->keyLength = kHFSPlusAttrKeyMinimumLength + unicode_bytes;
key->pad = 0;
key->fileID = inode_id;
key->startBlock = 0;
rec = (HFSPlusAttrData *)&attrdata[0];
bt_data.bufferAddress = rec;
bt_data.itemSize = sizeof(attrdata);
bt_data.itemCount = 1;
retval = BTSearchRecord(gptr->calculatedAttributesFCB, &iterator, kNoHint,
&bt_data, NULL, NULL);
if (retval == 0) {
if (rec->recordType != kHFSPlusAttrInlineData) {
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tfirst link EA is not inline for dirinode=%u (found=0x%x)\n", inode_id, rec->recordType);
}
retval = ENOENT;
goto out;
}
if (rec->attrData[rec->attrSize-1] != '\0') {
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tfirst link EA attrData is not NULL terminated for dirinode=%u\n", inode_id);
}
retval = ENOENT;
goto out;
}
for (i = 0; i < rec->attrSize-1; i++) {
if (isdigit(rec->attrData[i]) == 0) {
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tfirst link EA attrData contains non-digit 0x%x for dirinode=%u\n", rec->attrData[i], inode_id);
}
retval = ENOENT;
goto out;
}
}
*first_link_id = strtoul((char *)&rec->attrData[0], NULL, 10);
if (*first_link_id < kHFSFirstUserCatalogNodeID) {
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tfirst link ID=%u is < 16 for dirinode=%u\n", *first_link_id, inode_id);
}
*first_link_id = 0;
retval = ENOENT;
goto out;
}
}
} else {
*first_link_id = 0;
if ((inode_rec != NULL) &&
(inode_rec->recordType == kHFSPlusFileRecord)) {
*first_link_id = inode_rec->hfsPlusFile.hl_firstLinkID;
if (*first_link_id < kHFSFirstUserCatalogNodeID) {
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog("\tfirst link ID=%u is < 16 for fileinode=%u\n", *first_link_id, inode_id);
}
*first_link_id = 0;
retval = ENOENT;
goto out;
}
} else {
CatalogRecord rec;
CatalogKey key;
uint16_t recsize;
retval = GetCatalogRecordByID(gptr, inode_id, true, &key, &rec, &recsize);
if (retval == 0) {
*first_link_id = rec.hfsPlusFile.hl_firstLinkID;
if (rec.recordType != kHFSPlusFileRecord ||
*first_link_id < kHFSFirstUserCatalogNodeID) {
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog("\tfirst link ID=%u is < 16 for fileinode=%u\n", *first_link_id, inode_id);
}
*first_link_id = 0;
retval = ENOENT;
}
} else {
*first_link_id = 0;
retval = ENOENT;
}
}
}
out:
return retval;
}
void hardlink_add_bucket(PrimeBuckets *bucket, uint32_t inode_id,
uint32_t cur_link_id)
{
uint64_t num;
num = ((uint64_t)inode_id << 32) | cur_link_id;
add_prime_bucket_uint64(bucket, num);
}
struct link_list {
uint32_t link_id;
struct link_list *next;
};
int inode_check(SGlobPtr gptr, PrimeBuckets *bucket,
CatalogRecord *rec, CatalogKey *key, Boolean isdir)
{
int retval = 0;
uint32_t inode_id;
uint32_t cur_link_id;
uint32_t prev_link_id;
uint32_t count;
uint32_t linkCount;
char calc_name[32];
char found_name[NAME_MAX];
size_t calc_len;
size_t found_len;
CatalogKey linkkey;
CatalogRecord linkrec;
uint16_t recsize;
int flags;
uint32_t parentid;
uint32_t link_ref_num = 0;
struct link_list *head = NULL;
struct link_list *cur;
(void) utf_encodestr(key->hfsPlus.nodeName.unicode, key->hfsPlus.nodeName.length * 2,
(unsigned char *)found_name, &found_len, NAME_MAX);
found_name[found_len] = '\0';
if (isdir) {
inode_id = rec->hfsPlusFolder.folderID;
flags = rec->hfsPlusFolder.flags;
linkCount = rec->hfsPlusFolder.bsdInfo.special.linkCount;
parentid = gptr->dirlink_priv_dir_id;
} else {
inode_id = rec->hfsPlusFile.fileID;
flags = rec->hfsPlusFile.flags;
linkCount = rec->hfsPlusFile.bsdInfo.special.linkCount;
parentid = gptr->filelink_priv_dir_id;
link_ref_num = strtoul(&found_name[strlen(HFS_INODE_PREFIX)], NULL, 10);
}
if ((parentid != 0) && (key->hfsPlus.parentID != parentid)) {
(void) record_inode_badparent(gptr, inode_id, isdir, key->hfsPlus.parentID, parentid);
}
if (isdir) {
(void) snprintf(calc_name, sizeof(calc_name), "%s%u", HFS_DIRINODE_PREFIX, inode_id);
calc_len = strlen(calc_name);
if ((found_len != calc_len) ||
(strncmp(calc_name, found_name, calc_len) != 0)) {
(void) record_inode_badname(gptr, inode_id, found_name,
calc_name);
}
}
if (linkCount == 0) {
record_link_badchain(gptr, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tlinkCount=0 for dirinode=%u\n", inode_id);
}
retval = 1;
goto out;
}
if ((flags & kHFSHasLinkChainMask) == 0) {
if ((isdir) || (!isdir && (rec->hfsPlusFile.hl_firstLinkID != 0))) {
(void) record_inode_badflags(gptr, inode_id, isdir,
flags, flags | kHFSHasLinkChainMask, false);
} else {
filelink_hash_inode(link_ref_num, linkCount);
retval = 0;
goto out;
}
}
retval = get_first_link_id(gptr, rec, inode_id, isdir, &cur_link_id);
if (retval) {
record_link_badchain(gptr, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tError getting first link ID for inode=%u\n", inode_id);
}
goto out;
}
prev_link_id = 0;
count = 0;
while (cur_link_id != 0) {
retval = GetCatalogRecordByID(gptr, cur_link_id, true,
&linkkey, &linkrec, &recsize);
if (retval) {
record_link_badchain(gptr, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tError getting link=%u for inode=%u\n", cur_link_id, inode_id);
}
goto out;
}
if (linkrec.recordType != kHFSPlusFileRecord) {
record_link_badchain(gptr, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tIncorrect record type for link=%u for inode=%u (expected=2, found=%u)\n", cur_link_id, inode_id, linkrec.recordType);
}
retval = 1;
goto out;
}
if ((linkrec.hfsPlusFile.flags & kHFSHasLinkChainMask) == 0) {
(void) record_link_badchain(gptr, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tIncorrect flag for link=%u for inode=%u (found=0x%x)\n", cur_link_id, inode_id, linkrec.hfsPlusFile.flags);
}
retval = 1;
goto out;
}
if (isdir) {
if ((linkrec.hfsPlusFile.userInfo.fdType != kHFSAliasType) ||
(linkrec.hfsPlusFile.userInfo.fdCreator != kHFSAliasCreator) ||
((linkrec.hfsPlusFile.userInfo.fdFlags & kIsAlias) == 0)) {
record_link_badfinderinfo(gptr, linkrec.hfsPlusFile.fileID, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog("\tdirlink: fdType = 0x%08lx, fdCreator = 0x%08lx\n",
(unsigned long)linkrec.hfsPlusFile.userInfo.fdType,
(unsigned long)linkrec.hfsPlusFile.userInfo.fdCreator);
}
}
if (linkrec.hfsPlusFile.hl_linkReference != inode_id) {
record_link_badchain(gptr, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tIncorrect dirinode ID for dirlink=%u (expected=%u, found=%u)\n", cur_link_id, inode_id, linkrec.hfsPlusFile.hl_linkReference);
}
retval = 1;
goto out;
}
} else {
if ((linkrec.hfsPlusFile.userInfo.fdType != kHardLinkFileType) ||
(linkrec.hfsPlusFile.userInfo.fdCreator != kHFSPlusCreator)) {
record_link_badfinderinfo(gptr, linkrec.hfsPlusFile.fileID, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog("\tfilelink: fdType = 0x%08lx, fdCreator = 0x%08lx\n",
(unsigned long)linkrec.hfsPlusFile.userInfo.fdType,
(unsigned long)linkrec.hfsPlusFile.userInfo.fdCreator);
}
}
if (linkrec.hfsPlusFile.hl_linkReference != link_ref_num) {
record_link_badchain(gptr, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tIncorrect link reference number for filelink=%u (expected=%u, found=%u)\n", cur_link_id, inode_id, linkrec.hfsPlusFile.hl_linkReference);
}
retval = 1;
goto out;
}
}
if (isdir) {
hardlink_add_bucket(bucket, inode_id, cur_link_id);
} else {
hardlink_add_bucket(bucket, link_ref_num, cur_link_id);
}
if (prev_link_id != linkrec.hfsPlusFile.hl_prevLinkID) {
record_link_badchain(gptr, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tIncorrect prevLinkID for link=%u for inode=%u (expected=%u, found=%u)\n", cur_link_id, inode_id, prev_link_id, linkrec.hfsPlusFile.hl_prevLinkID);
}
retval = 1;
goto out;
}
cur = head;
while (cur) {
if (cur->link_id == cur_link_id) {
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tDuplicate link=%u found in list for inode=%u\n", cur_link_id, inode_id);
}
record_link_badchain(gptr, isdir);
retval = 1;
goto out;
}
cur = cur->next;
}
cur = malloc(sizeof(struct link_list));
if (!cur) {
retval = ENOMEM;
goto out;
}
cur->link_id = cur_link_id;
cur->next = head;
head = cur;
count++;
prev_link_id = cur_link_id;
cur_link_id = linkrec.hfsPlusFile.hl_nextLinkID;
}
if (linkCount != count) {
record_link_badchain(gptr, isdir);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tIncorrect linkCount for inode=%u (expected=%u, found=%u)\n", inode_id, count, linkCount);
}
retval = 1;
goto out;
}
out:
while(head) {
cur = head;
head = head->next;
free(cur);
}
return retval;
}
static void check_dirlink_ancestors(SGlobPtr gptr, uint32_t dir_id)
{
int retval = 0;
CatalogRecord rec;
CatalogKey key;
uint16_t recsize;
while ((dir_id != kHFSRootFolderID) && (dir_id != gptr->dirlink_priv_dir_id)) {
retval = GetCatalogRecordByID(gptr, dir_id, true, &key, &rec, &recsize);
if (retval != 0) {
break;
}
if (rec.recordType != kHFSPlusFolderRecord) {
break;
}
if ((rec.hfsPlusFolder.flags & kHFSHasChildLinkMask) == 0) {
(void) record_parent_badflags(gptr, dir_id,
rec.hfsPlusFolder.flags,
rec.hfsPlusFolder.flags | kHFSHasChildLinkMask);
}
dir_id = key.hfsPlus.parentID;
}
if ((dir_id != kHFSRootFolderID) && (dir_id != gptr->dirlink_priv_dir_id)) {
fsckPrint(gptr->context, E_BadParentHierarchy, dir_id);
gptr->CBTStat |= S_Orphan;
}
return;
}
static void dirlink_check(SGlobPtr gptr, PrimeBuckets *bucket,
HFSPlusCatalogFile *rec, HFSPlusCatalogKey *key, Boolean isdir)
{
#if DEBUG_HARDLINKCHECK
if (fsckGetVerbosity(gptr->context) >= kDebugLog)
plog("link_check: adding <%u, %u>\n", rec->hl_linkReference, rec->fileID);
#endif
hardlink_add_bucket(bucket, rec->hl_linkReference, rec->fileID);
if ((rec->bsdInfo.ownerFlags & UF_IMMUTABLE) == 0) {
record_dirlink_badownerflags(gptr, rec->fileID,
rec->bsdInfo.ownerFlags,
rec->bsdInfo.ownerFlags | UF_IMMUTABLE, false);
}
if ((rec->userInfo.fdType != kHFSAliasType) ||
(rec->userInfo.fdCreator != kHFSAliasCreator) ||
((rec->userInfo.fdFlags & kIsAlias) == 0)) {
record_link_badfinderinfo(gptr, rec->fileID, isdir);
}
check_dirlink_ancestors(gptr, key->parentID);
}
static int find_next_child_dir(SGlobPtr gptr, uint32_t parent_id,
uint32_t cur_child_catalog_id, uint32_t *child_inode_id,
uint32_t *child_catalog_id, uint32_t *is_dirinode)
{
int retval;
SFCB *fcb;
int return_next_rec = true;
BTreeIterator iterator;
FSBufferDescriptor buf_desc;
uint16_t recsize;
CatalogRecord rec;
CatalogKey *key;
*child_inode_id = 0;
*child_catalog_id = 0;
*is_dirinode = false;
fcb = gptr->calculatedCatalogFCB;
key = (CatalogKey *)&iterator.key;
if (cur_child_catalog_id == 0) {
iterate_parent:
bzero(&iterator, sizeof(iterator));
bzero(&buf_desc, sizeof(buf_desc));
buf_desc.bufferAddress = &rec;
buf_desc.itemCount = 1;
buf_desc.itemSize = sizeof(rec);
BuildCatalogKey(parent_id, NULL, true, key);
retval = BTSearchRecord(fcb, &iterator, kNoHint, &buf_desc, &recsize,
&iterator);
if ((retval != 0) && (retval != btNotFound)) {
goto out;
}
} else {
bzero(&iterator, sizeof(iterator));
bzero(&buf_desc, sizeof(buf_desc));
buf_desc.bufferAddress = &rec;
buf_desc.itemCount = 1;
buf_desc.itemSize = sizeof(rec);
BuildCatalogKey(cur_child_catalog_id, NULL, true, key);
retval = BTSearchRecord(fcb, &iterator, kNoHint, &buf_desc,
&recsize, &iterator);
if (retval) {
return_next_rec = false;
goto iterate_parent;
}
if ((rec.recordType != kHFSPlusFolderThreadRecord) &&
(rec.recordType != kHFSPlusFileThreadRecord)) {
return_next_rec = false;
goto iterate_parent;
}
bzero(&iterator, sizeof(iterator));
bzero(&buf_desc, sizeof(buf_desc));
buf_desc.bufferAddress = &rec;
buf_desc.itemCount = 1;
buf_desc.itemSize = sizeof(rec);
BuildCatalogKey(rec.hfsPlusThread.parentID,
(CatalogName *)&(rec.hfsPlusThread.nodeName),
true, (CatalogKey *)&(iterator.key));
retval = BTSearchRecord(fcb, &iterator, kInvalidMRUCacheKey,
&buf_desc, &recsize, &iterator);
if (retval) {
return_next_rec = false;
goto iterate_parent;
}
}
retval = BTIterateRecord(fcb, kBTreeNextRecord, &iterator, &buf_desc,
&recsize);
while (retval == 0) {
if (key->hfsPlus.parentID != parent_id) {
break;
}
if (rec.recordType == kHFSPlusFolderRecord) {
if (return_next_rec) {
if (rec.hfsPlusFolder.flags & kHFSHasLinkChainMask) {
*is_dirinode = true;
}
*child_inode_id = rec.hfsPlusFolder.folderID;
*child_catalog_id = rec.hfsPlusFolder.folderID;
break;
}
if (rec.hfsPlusFolder.folderID == cur_child_catalog_id) {
return_next_rec = true;
}
} else if (rec.recordType == kHFSPlusFileRecord) {
if ((rec.hfsPlusFile.flags & kHFSHasLinkChainMask) &&
(rec.hfsPlusFile.userInfo.fdType == kHFSAliasType) &&
(rec.hfsPlusFile.userInfo.fdCreator == kHFSAliasCreator) &&
(key->hfsPlus.parentID != gptr->filelink_priv_dir_id)) {
if (return_next_rec) {
*child_inode_id = rec.hfsPlusFile.hl_linkReference;
*child_catalog_id = rec.hfsPlusFile.fileID;
*is_dirinode = true;
break;
}
if (rec.hfsPlusFile.fileID == cur_child_catalog_id) {
return_next_rec = true;
}
}
}
retval = BTIterateRecord(fcb, kBTreeNextRecord, &iterator,
&buf_desc, &recsize);
}
if (retval == btNotFound) {
retval = 0;
}
out:
return retval;
}
struct dfs_id {
uint32_t inode_id;
uint32_t catalog_id;
};
struct dfs_stack {
uint32_t depth;
struct dfs_id *idptr;
};
#define DIRLINK_DFS_MAX_DEPTH PATH_MAX/2
static int check_loops(struct dfs_stack *dfs, struct dfs_id id)
{
int retval = 0;
int i;
for (i = 0; i < dfs->depth; i++) {
if (dfs->idptr[i].inode_id == id.inode_id) {
retval = 1;
break;
}
}
return retval;
}
static void print_dfs(struct dfs_stack *dfs)
{
int i;
plog ("\t");
for (i = 0; i < dfs->depth; i++) {
plog ("(%u,%u) ", dfs->idptr[i].inode_id, dfs->idptr[i].catalog_id);
}
plog ("\n");
}
struct visited_dirinode {
uint32_t *list;
uint32_t size;
uint32_t offset;
uint32_t wrapped;
};
static void mark_dirinode_visited(uint32_t dirinode_id, struct visited_dirinode *visited)
{
if (visited->list == NULL) {
return;
}
if (visited->offset >= visited->size) {
visited->offset = 0;
visited->wrapped = true;
}
visited->list[visited->offset] = dirinode_id;
visited->offset++;
}
static int is_dirinode_visited(uint32_t dirinode_id, struct visited_dirinode *visited)
{
int is_visited = false;
uint32_t end_offset;
uint32_t off;
if (visited->list == NULL) {
return is_visited;
}
if (visited->wrapped == true) {
end_offset = visited->size;
} else {
end_offset = visited->offset;
}
for (off = 0; off < end_offset; off++) {
if (visited->list[off] == dirinode_id) {
is_visited = true;
break;
}
}
return is_visited;
}
static int check_hierarchy_loops(SGlobPtr gptr)
{
int retval = 0;
struct dfs_stack dfs;
struct dfs_id unknown_child;
struct dfs_id child;
struct dfs_id parent;
struct visited_dirinode visited;
uint32_t is_dirinode;
#define DFS_PUSH(dfs_id) \
{ \
dfs.idptr[dfs.depth].inode_id = dfs_id.inode_id; \
dfs.idptr[dfs.depth].catalog_id = dfs_id.catalog_id; \
dfs.depth++; \
}
#define DFS_POP(dfs_id) \
{ \
dfs.depth--; \
dfs_id.inode_id = dfs.idptr[dfs.depth].inode_id; \
dfs_id.catalog_id = dfs.idptr[dfs.depth].catalog_id; \
}
#define DFS_PEEK(dfs_id) \
{ \
dfs_id.inode_id = dfs.idptr[dfs.depth-1].inode_id; \
dfs_id.catalog_id = dfs.idptr[dfs.depth-1].catalog_id; \
}
dfs.idptr = malloc(DIRLINK_DFS_MAX_DEPTH * sizeof(struct dfs_id));
if (!dfs.idptr) {
return ENOMEM;
}
dfs.depth = 0;
unknown_child.inode_id = unknown_child.catalog_id = 0;
if (gptr->calculated_dirinodes) {
visited.size = gptr->calculated_dirinodes;
} else {
visited.size = 1024;
}
visited.list = malloc(visited.size * sizeof(uint32_t));
if (visited.list == NULL) {
visited.size = 0;
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tcheck_loops: Allocation failed for visited list\n");
}
}
visited.offset = 0;
visited.wrapped = false;
if (gptr->dirlink_priv_dir_id) {
parent.inode_id = parent.catalog_id = gptr->dirlink_priv_dir_id;
} else {
parent.inode_id = parent.catalog_id = kHFSRootFolderID;
}
DFS_PUSH(parent);
DFS_PUSH(unknown_child);
while ((dfs.depth > 1) && (dfs.depth < DIRLINK_DFS_MAX_DEPTH)) {
DFS_POP(child);
DFS_PEEK(parent);
retval = find_next_child_dir(gptr, parent.inode_id,
child.catalog_id, &(child.inode_id),
&(child.catalog_id), &is_dirinode);
if (retval) {
break;
}
if (child.inode_id) {
retval = check_loops(&dfs, child);
if (retval) {
fsckPrint(gptr->context, E_DirLoop);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tDetected when adding (%u,%u) to following traversal stack -\n", child.inode_id, child.catalog_id);
print_dfs(&dfs);
}
gptr->CatStat |= S_LinkErrNoRepair;
retval = E_DirLoop;
break;
}
DFS_PUSH(child);
if (is_dirinode == true) {
if (is_dirinode_visited(child.inode_id, &visited)) {
continue;
} else {
mark_dirinode_visited(child.inode_id, &visited);
}
}
DFS_PUSH(unknown_child);
}
}
if (dfs.depth >= DIRLINK_DFS_MAX_DEPTH) {
fsckPrint(gptr->context, E_DirHardLinkNesting);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
print_dfs(&dfs);
}
gptr->CatStat |= S_LinkErrNoRepair;
retval = E_DirHardLinkNesting;
}
if (dfs.idptr) {
free(dfs.idptr);
}
if (visited.list) {
free(visited.list);
}
return retval;
}
int dirhardlink_check(SGlobPtr gptr)
{
int retval = 0;
uint16_t selcode;
uint32_t hint;
CatalogRecord catrec;
CatalogKey catkey;
uint16_t recsize;
PrimeBuckets *inode_view = NULL;
PrimeBuckets *dirlink_view = NULL;
if (VolumeObjectIsHFSPlus() == false) {
goto out;
}
if ((gptr->dirlink_priv_dir_valence == 0) &&
(gptr->calculated_dirlinks == 0) &&
(gptr->calculated_dirinodes == 0)) {
goto out;
}
fsckPrint(gptr->context, hfsMultiLinkDirCheck);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tprivdir_valence=%u, calc_dirlinks=%u, calc_dirinode=%u\n", gptr->dirlink_priv_dir_valence, gptr->calculated_dirlinks, gptr->calculated_dirinodes);
}
if (gptr->dirlink_priv_dir_id == 0) {
fsckPrint(gptr->context, E_MissingPrivDir);
gptr->CatStat |= S_LinkErrNoRepair;
}
inode_view = (PrimeBuckets *)calloc(1, sizeof(PrimeBuckets));
if (!inode_view) {
retval = ENOMEM;
goto out;
}
dirlink_view = (PrimeBuckets *)calloc(1, sizeof(PrimeBuckets));
if (!dirlink_view) {
retval = ENOMEM;
goto out;
}
selcode = 0x8001;
retval = GetBTreeRecord(gptr->calculatedCatalogFCB, selcode, &catkey,
&catrec, &recsize, &hint);
if (retval != 0) {
goto out;
}
selcode = 1;
do {
if (catrec.hfsPlusFolder.recordType == kHFSPlusFolderRecord) {
if (catrec.hfsPlusFolder.folderID == gptr->dirlink_priv_dir_id) {
dirlink_priv_dir_check(gptr,
&(catrec.hfsPlusFolder), &(catkey.hfsPlus));
}
if ((catrec.hfsPlusFolder.flags & kHFSHasLinkChainMask) ||
(catkey.hfsPlus.parentID == gptr->dirlink_priv_dir_id)) {
retval = inode_check(gptr, inode_view,
&catrec,
&catkey,
true);
if (retval) {
retval = 0;
break;
}
}
} else
if (catrec.recordType == kHFSPlusFileRecord) {
if ((catrec.hfsPlusFile.flags & kHFSHasLinkChainMask) &&
(catrec.hfsPlusFile.userInfo.fdType == kHFSAliasType) &&
(catrec.hfsPlusFile.userInfo.fdCreator == kHFSAliasCreator) &&
(catkey.hfsPlus.parentID != gptr->filelink_priv_dir_id)) {
dirlink_check(gptr, dirlink_view,
&(catrec.hfsPlusFile), &(catkey.hfsPlus), true);
}
}
retval = GetBTreeRecord(gptr->calculatedCatalogFCB, 1,
&catkey, &catrec, &recsize, &hint);
} while (retval == noErr);
if (retval == btNotFound) {
retval = 0;
} else if (retval != 0) {
goto out;
}
if ((gptr->CatStat & S_DirHardLinkChain) == 0) {
retval = compare_prime_buckets(inode_view, dirlink_view);
if (retval) {
record_link_badchain(gptr, true);
if (fsckGetVerbosity(gptr->context) >= kDebugLog) {
plog ("\tdirlink prime buckets do not match\n");
}
retval = 0;
}
}
retval = check_hierarchy_loops(gptr);
if (retval) {
retval = 0;
goto out;
}
out:
if (inode_view) {
free (inode_view);
}
if (dirlink_view) {
free (dirlink_view);
}
return retval;
}