Export Create* functions for usage by Impactor.

[hfs.git] / fsck_hfs / dfalib / HardLinkCheck.c

/*
 * Copyright (c) 2000-2002, 2004-2008 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * 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"
#include <sys/stat.h>

#define DEBUG_HARDLINKCHECK 0

/* If set, the node in hash is initialized and has valid inodeID */ 
#define LINKINFO_INIT   0x01
/* If set, verification of corresponding inode is completed successfully */
#define LINKINFO_CHECK  0x02

/* info saved for each indirect link encountered */
struct IndirectLinkInfo {
        /* linkID is link reference number for file hard links, and 
         * inodeID for directory hard links.
         */
        UInt32  linkID; 
        UInt32  linkCount;
        UInt32  flags;
        struct HardLinkList *list;
};

#define VISITED_INODE_ID 1

struct HardLinkInfo {
        UInt32  privDirID;
        SGlobPtr globals;
        uint32_t        priv_dir_itime; /* Creation (initialization) time of metadata folder */
        uint32_t        root_dir_itime; /* Creation (initialization) time of root folder */
        PrimeBuckets    *fileBucket;
};

struct HardLinkList {
        UInt32  prev;
        UInt32  fileID;
        UInt32  next;
};

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  GetRootDir(SGlobPtr gp, CatalogRecord *rec);
static int  RecordOrphanOpenUnlink(SGlobPtr gp, UInt32 parID, unsigned char * filename);
static int  RecordBadHardLinkChainFirst(SGlobPtr, UInt32, UInt32, UInt32);
static int  RecordBadHardLinkNext(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe);
static int  RecordBadHardLinkPrev(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe);
static int  RecordBadLinkCount(SGlobPtr gp, UInt32 inodeID, UInt32 is, UInt32 shouldbe) ;
static int  RecordOrphanLink(SGlobPtr gp, Boolean isdir, UInt32 linkID);
static int  RecordOrphanInode(SGlobPtr gp, Boolean isdir, UInt32 inodeID);
static void hash_insert(UInt32 linkID, int totalSlots, int slotsUsed, struct IndirectLinkInfo *linkInfo);
static struct IndirectLinkInfo * hash_search(UInt32 linkID, int totalSlots, int slotsUsed, struct IndirectLinkInfo *linkInfo);

/*
 * Some functions used when sorting the hard link chain.
 * chain_compare() is used by qsort; find_id is just a linear
 * search to find a specific fileID; and tsort does a
 * topological sort on the linked list.
 */
static int
chain_compare(const void *a1, const void *a2) {
        struct HardLinkList *left = (struct HardLinkList*)a1;
        struct HardLinkList *right = (struct HardLinkList*)a2;

        return (left->prev - right->prev);
}

static int
find_id(struct HardLinkList *list, int nel, int id)
{
        int i;
        for (i = 0; i < nel; i++) {
                if (list[i].fileID == id)
                        return i;
        }
        return 0;
}

static int
tsort(struct HardLinkList *list, int nel)
{
        struct HardLinkList *tmp;
        int cur_indx, tmp_indx = 0;

        int rv = 0;

        tmp = calloc(sizeof(struct HardLinkList), nel);
        if (tmp == NULL) {
                rv = ENOMEM;
                goto done;
        }

        /*
         * Since we only check list.next when doing the sort, we want to
         * start with nodes that have prev == 0 (ones at the top of the
         * graph, in other words).  If there aren't any with a prev of 0,
         * then the chain is broken somehow, and we'll repair it later.
         */
        qsort(list, nel, sizeof(list[0]), chain_compare);

        for (cur_indx = 0; cur_indx < nel; cur_indx++) {
                int i;
                /* Skip nodes we've already come across */
                if (list[cur_indx].fileID == 0)
                        continue;

                /* Copy this node over to the new list */
                tmp[tmp_indx++] = list[cur_indx];
                list[cur_indx].fileID = 0;

                /* ... and then find all its children. */
                for (i = tmp[tmp_indx-1].next; i != 0; ) {
                        // look for the node in list with that fileID
                        int j = find_id(list, nel, i);
                        if (j == 0) {
                                // We couldn't find it
                                // So we're done
                                i = 0;
                        } else {
                                // we add this one to tmp
                                tmp[tmp_indx++] = list[j];
                                list[j].fileID = 0;
                                i = tmp[tmp_indx-1].next;
                        }
                }
        }

        /* Copy the temporary list over, and we're done. */
        memcpy(list, tmp, nel * sizeof(struct HardLinkList));
done:
        if (tmp) {
                free(tmp);
        }

        return rv;
}

/*
 * CheckHardLinkList
 *
 * Verify that the linked list of hard link nodes (the catalog entries, not the indirect
 * node in the private metadata directory) are correct and sane.  If any discrepancies 
 * are detected, create repair order.
 *
 * To do this, we need to topologically sort the list, and then ensure that the prev/next
 * chains are correct.
 *
 */
static int
CheckHardLinkList(SGlobPtr gp, UInt32 inodeID, struct HardLinkList *list, int calc_link_count, UInt32 firstID)
{
        int retval;
        int indx;

        if (list == NULL) {
                if (fsckGetVerbosity(gp->context) >= kDebugLog) {
                        plog("\tCheckHardLinkList: list=NULL for inodeID = %u\n", inodeID);
                }
                return ENOMEM;
        }
        /*
         * If we have a list, then we sort and verify it.  It's pretty easy, once
         * we're sorted, and tsort() above does the hard work for that.
         */
        if (calc_link_count > 1) {
                retval = tsort(list, calc_link_count);
                if (retval) {
                        goto done;
                }
        }

        /* Previous link of first link should always be zero */
        if (list[0].prev != 0) {
                RecordBadHardLinkPrev(gp, list[0].fileID, list[0].prev, 0);
        }

        /* First ID in the inode should match the ID of the first hard link */
        if (list[0].fileID != firstID) {
                RecordBadHardLinkChainFirst(gp, inodeID, firstID, list[0].fileID);
        }

        /* Check if the previous/next IDs for all nodes except the first node are valid */
        for (indx = 1; indx < calc_link_count; indx++) {
                if (list[indx-1].next != list[indx].fileID) {
                        RecordBadHardLinkNext(gp, list[indx-1].fileID, list[indx-1].next, list[indx].fileID);
                }

                if (list[indx].prev != list[indx-1].fileID) {
                        RecordBadHardLinkPrev(gp, list[indx].fileID, list[indx].prev, list[indx-1].fileID);
                }
        }

        /* Next ID for the last link should always be zero */
        if (list[calc_link_count-1].next != 0) {
                RecordBadHardLinkNext(gp, list[calc_link_count-1].fileID, list[calc_link_count-1].next, 0);
        }

done:
#if DEBUG_HARDLINKCHECK
        /* This is just for debugging -- it's useful to know what the list looks like */
        if (fsckGetVerbosity(gp->context) >= kDebugLog) {
                for (indx = 0; indx < calc_link_count; indx++) {
                        fplog(stderr, "CNID %u: #%u:  <%u, %u, %u>\n", inodeID, indx, list[indx].prev, list[indx].fileID, list[indx].next);
                }
        }
#endif

        return 0;
}

/*
 * 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;
        CatalogRecord rootFolder;
        UInt32 folderID;

        if (GetPrivateDir(gp, &rec) == 0) {
                folderID = rec.hfsPlusFolder.folderID;
        } else {
                folderID = 0;
        }
        
        info = (struct HardLinkInfo *) malloc(sizeof(struct HardLinkInfo));

        if (info == NULL) {
                if (fsckGetVerbosity(gp->context) >= kDebugLog) {
                        plog("hardLinkCheckBegin:  malloc(%zu) failed\n", sizeof(struct HardLinkInfo));
                }
                return 1;
        }

        info->privDirID = folderID;
        info->priv_dir_itime = folderID ? rec.hfsPlusFolder.createDate : 0;
        if (GetRootDir(gp, &rootFolder) == 0) {
                        info->root_dir_itime = rootFolder.hfsPlusFolder.createDate;
        } else {
                        info->root_dir_itime = 0;
        }

        info->globals = gp;
        
        /* We will use the ID of private metadata directory for file hard 
         * links to skip over hard link inode for an alias from directory 
         * hard link checks.
         */
        gp->filelink_priv_dir_id = folderID;


        info->fileBucket = calloc(1, sizeof(PrimeBuckets));
        if (info->fileBucket == NULL) {
                if (fsckGetVerbosity(gp->context) >= kDebugLog) {
                        plog("HardLinkCheckBegin: prime bucket allocation failed\n");
                }
        }

        * 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->fileBucket) {
                        free(infoPtr->fileBucket);
                        infoPtr->fileBucket = NULL;
                }
                DisposeMemory(cookie);
        }

}

/* Structures for file hard link hash used when a 
 * file hard link created in pre-Leopard OS is detected 
 * i.e. the file inode and hard links do not have the 
 * kHFSHasLinkChainBit set, and the first link, the 
 * previous link and the next link IDs are zero.  The 
 * link count for such hard links cannot be verified 
 * using CRT, therefore it is accounted in this hash.
 */
#define FILELINK_HASH_SIZE 257

struct filelink_hash {
        UInt32 link_ref_num;
        UInt32 found_link_count;
        UInt32 calc_link_count;
        struct filelink_hash *next;
};

struct filelink_hash **filelink_head = NULL;
UInt32 filelink_entry_count = 0;

/* Search and return pointer to the entry for given inode ID.
 * If no entry is found, return NULL.
 */
static struct filelink_hash *filelink_hash_search(UInt32 link_ref_num) 
{
        struct filelink_hash *cur;

        if (filelink_head == NULL) {
                return NULL;
        }

        cur = filelink_head[link_ref_num % FILELINK_HASH_SIZE];
        while (cur) {
                if (link_ref_num == cur->link_ref_num) {
                        break;
                }
                cur = cur->next;
        }

        return cur;
}

/* Allocate and insert entry for given inode ID in the 
 * hash.  The caller function is responsible for searching 
 * for duplicates before calling this function.  
 * Returns the pointer to the new hash entry.
 */
static struct filelink_hash *filelink_hash_insert(UInt32 link_ref_num) 
{
        struct filelink_hash *cur;

        cur = malloc(sizeof(struct filelink_hash));
        if (!cur) {
                return cur;
        }
        cur->link_ref_num = link_ref_num;
        cur->found_link_count = 0;
        cur->calc_link_count = 0;
        cur->next = filelink_head[link_ref_num % FILELINK_HASH_SIZE];
        filelink_head[link_ref_num % FILELINK_HASH_SIZE] = cur; 
        filelink_entry_count++;
        return cur;
}

/* Update the hash with information about a file hard link 
 * that points to given inode ID.  The calculated link count 
 * for given inode is incremented.
 * Returns zero if the value was successfully updated to hash,
 * and ENOMEM on error.
 */
static int filelink_hash_link(UInt32 link_ref_num)
{
        struct filelink_hash *cur;
        
        /* If no hash exists, allocate the hash */
        if (filelink_head == NULL) {
                filelink_head = calloc(FILELINK_HASH_SIZE, sizeof(struct filelink_hash *));
                if (filelink_head == NULL) {
                        return ENOMEM;
                }
        }

        cur = filelink_hash_search(link_ref_num);
        if (!cur) {
                cur = filelink_hash_insert(link_ref_num);
        }
        if (cur) {
                cur->calc_link_count++;
                return 0;
        }

        return ENOMEM;
}

/* Update the hash with information about given file inode. 
 * The found link count in the hash is updated with the 
 * link count value provided.
 * Returns zero if the value was successfully updated to hash,
 * and ENOMEM on error.
 */ 
int filelink_hash_inode(UInt32 link_ref_num, UInt32 linkCount)
{
        struct filelink_hash *cur;

        /* If no hash exists, allocate the hash */
        if (filelink_head == NULL) {
                filelink_head = calloc(FILELINK_HASH_SIZE, sizeof(struct filelink_hash *));
                if (filelink_head == NULL) {
                        return ENOMEM;
                }
        }

        cur = filelink_hash_search(link_ref_num);
        if (!cur) {
                cur = filelink_hash_insert(link_ref_num);
        }
        if (cur) {
                cur->found_link_count = linkCount;
                return 0;
        } 
        return ENOMEM;
}

/* If the file link hash was used to account for 
 * link count of file hard links created on pre-Leopard
 * OS, destroy the hash by freeing all allocated 
 * memory.
 */
static void filelink_hash_destroy(void) 
{
        int i;
        struct filelink_hash *cur;

        for (i = 0; i < FILELINK_HASH_SIZE; i++) {
                while (filelink_head[i]) {
                        cur = filelink_head[i];
                        filelink_head[i] = cur->next;
                        free (cur);
                }
        }
        free(filelink_head);
        filelink_head = NULL;
        filelink_entry_count = 0;
}

/*
 * CaptureHardLink
 *
 * Capture indirect link info.
 * Called for every indirect link in the catalog.
 */
void
CaptureHardLink(void *cookie, const HFSPlusCatalogFile *file)
{
        struct HardLinkInfo * info = (struct HardLinkInfo *) cookie;

        /* A file hard link created on pre-Leopard OS does not 
         * have kHFSHasLinkChainBit set or prev/next link IDs. 
         * Ignore such file hard links from all check and CRT account 
         * and instead account the information in hash to verify the 
         * link counts later.
         */
        if ((info->fileBucket == NULL) || 
            (((file->flags & kHFSHasLinkChainMask) == 0) && 
             (file->hl_prevLinkID == 0) && 
             (file->hl_nextLinkID == 0))) {
                filelink_hash_link(file->hl_linkReference);
        } else {
                /* For file hard links, add link reference number 
                 * and catalog link ID pair to the prime buckets.
                 */
                hardlink_add_bucket(info->fileBucket, file->hl_linkReference, 
                        file->fileID);

                if ((file->flags & kHFSHasLinkChainMask) == 0) {
                        record_link_badchain(info->globals, false);
                }
        }
        if ((info->priv_dir_itime && file->createDate != info->priv_dir_itime) &&
                (info->root_dir_itime && file->createDate != info->root_dir_itime)) {
                RepairOrderPtr p;
                char str1[12];
                char str2[12];
                uint32_t correct;

                if (debug)
                        plog("Hard Link catalog entry %u has bad time %u (should be %u, or at least %u)\n",
                                file->fileID, file->createDate, info->priv_dir_itime, info->root_dir_itime);
                correct = info->priv_dir_itime;

                p = AllocMinorRepairOrder(info->globals, 0);
                if (p == NULL) {
                        if (debug)
                                plog("Unable to allocate hard link time repair order!");
                        return;
                }

                fsckPrint(info->globals->context, E_BadHardLinkDate);
                snprintf(str1, sizeof(str1), "%u", correct);
                snprintf(str2, sizeof(str2), "%u", file->createDate);
                fsckPrint(info->globals->context, E_BadValue, str1, str2);

                p->type = E_BadHardLinkDate;
                p->parid = file->fileID;
                p->correct = info->priv_dir_itime;
                p->incorrect = file->createDate;
        }

        return;
}

/*
 * RepairHardLinkChains
 *
 * Cycle through the catalog tree, and generate repair orders for hard 
 * links that may be broken.
 */
int
RepairHardLinkChains(SGlobPtr gp, Boolean isdir)
{
        int result = 0;
        struct IndirectLinkInfo *linkInfo = NULL;
        CatalogRecord   rec;
        HFSPlusCatalogKey       *keyp;
        BTreeIterator   iterator;
        FSBufferDescriptor      btrec;
        UInt16  reclen;
        UInt32  linkID, inodeID;
        UInt32  metadirid;
        SFCB    *fcb;
        size_t  prefixlen;
        int     slotsUsed = 0, slots = 0;
        char *prefixName;
        UInt32 folderID;
        UInt32 link_ref_num;
        int entries;
        UInt32 flags;

        if (isdir) {
                metadirid = gp->dirlink_priv_dir_id;
                prefixlen = strlen(HFS_DIRINODE_PREFIX);
                prefixName = HFS_DIRINODE_PREFIX;
        } else {
                metadirid = gp->filelink_priv_dir_id;
                prefixlen = strlen(HFS_INODE_PREFIX);
                prefixName = HFS_INODE_PREFIX;
        }

        if (metadirid == 0) {
                if (fsckGetVerbosity(gp->context) >= kDebugLog) {
                        if (isdir) {
                                plog ("\tPrivate directory for dirlinks not found.  Stopping repairs.\n");
                        } else {
                                plog ("\tPrivate directory for filelinks not found.  Stopping repairs.\n");
                        }
                } 
                result = ENOENT;
                goto done;
        }

        // Initialize the hash
        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;
        linkInfo = calloc(slots, sizeof(struct IndirectLinkInfo));
        if (linkInfo == NULL) {
                if (fsckGetVerbosity(gp->context) >= kDebugLog) {
                        plog("RepairHardLinkChains:  calloc(%d, %zu) failed\n", slots, sizeof(struct IndirectLinkInfo));
                }
                result = ENOMEM;
                goto done;
        }
        // Done initializing the hash

        // Set up the catalog BTree iterator
        // (start from the root folder, and work our way down)
        fcb = gp->calculatedCatalogFCB;
        ClearMemory(&iterator, sizeof(iterator));
        keyp = (HFSPlusCatalogKey*)&iterator.key;
        BuildCatalogKey(kHFSRootFolderID, NULL, true, (CatalogKey*)keyp);
        btrec.bufferAddress = &rec;
        btrec.itemCount = 1;
        btrec.itemSize = sizeof(rec);

        /* Counter for number of inodes found and verified in the
         * hash.  When an inode is found when checking the hard links,
         * the value is incremented.  When an inode's linked list and 
         * link count are verified, the value is decremented.  If 
         * this value remains non-zero at the end, there are 
         * orphan hard links.
         */
        entries = 0;

        /*
         * This chunk of code iterates through the entire catalog BTree.
         * For each hard link node (that is, the "directory entry" that
         * points to the actual node in the metadata directory), it may
         * add it to the hash (if it doesn't exist yet; it also then increments
         * the link count for that "inode"); it also creates an array
         * of <previous, fileid, next> for the linked list.
         */
        for (result = BTIterateRecord(fcb, kBTreeFirstRecord, &iterator, &btrec, &reclen);
                result == 0;
                result = BTIterateRecord(fcb, kBTreeNextRecord, &iterator, &btrec, &reclen)) {
                HFSPlusCatalogFile *file = &rec.hfsPlusFile;
                Boolean islink = false;

                if (rec.recordType != kHFSPlusFileRecord)
                        continue;

                if (isdir) {
                        /* Assume that this is a directory hard link if 
                         * the atleast one value in finder info corresponds to 
                         * alias, and the alias is not a file inode, and 
                         * either the inode number is greater than 
                         * kHFSFirstUserCatalogNodeID or the flag has 
                         * kHFSHasLinkChainBit set.
                         */
                        if (((file->userInfo.fdType == kHFSAliasType) ||
                             (file->userInfo.fdCreator == kHFSAliasCreator) ||
                             (file->userInfo.fdFlags & kIsAlias)) &&
                            (keyp->parentID != gp->filelink_priv_dir_id) &&
                            ((file->hl_linkReference >= kHFSFirstUserCatalogNodeID) || 
                             (file->flags & kHFSHasLinkChainMask))) {
                                flags = rec.hfsPlusFile.flags;
                                islink = true;
                        }
                } else if (file->userInfo.fdType == kHardLinkFileType &&
                           file->userInfo.fdCreator == kHFSPlusCreator) {
                        flags = rec.hfsPlusFile.flags;
                        islink = true;
                }
                if (islink) {
                        struct IndirectLinkInfo *li = NULL;
                        struct HardLinkList *tlist = NULL;
                        int i;
                        int count;

                        linkID = file->fileID;
                        inodeID = file->bsdInfo.special.iNodeNum;

                        /* Now that we are in repair, all hard links should 
                         * have this bit set because we upgrade all pre-Leopard
                         * file hard links to Leopard hard links on any 
                         * file hard link repairs.
                         */
                        if ((flags & kHFSHasLinkChainMask) == 0) {
                                record_link_badflags(gp, linkID, isdir, flags,
                                        flags | kHFSHasLinkChainMask);
                        }

                        /* For directory hard links, check ownerFlags and 
                         * finderInfo because we could have missed creating 
                         * repair orders in verification.  Verification could 
                         * have stopped before we saw this record because it 
                         * stops as soon as it determines that it needs full 
                         * knowledge of hard links on the disk during repair.
                         */
                        if (isdir) {
                                /* Check if the directory hard link has UF_IMMUTABLE bit set */
                                if ((file->bsdInfo.ownerFlags & UF_IMMUTABLE) == 0) {
                                        record_dirlink_badownerflags(gp, file->fileID, 
                                                file->bsdInfo.ownerFlags, 
                                                file->bsdInfo.ownerFlags | UF_IMMUTABLE, true);
                                }

                                /* Check Finder Info */
                                if ((file->userInfo.fdType != kHFSAliasType) ||
                                    (file->userInfo.fdCreator != kHFSAliasCreator) ||
                                    ((file->userInfo.fdFlags & kIsAlias) == 0)) {
                                        record_link_badfinderinfo(gp, file->fileID, true);
                                }
                        }

                        /* For directory hard links, hash using inodeID.  For 
                         * file hard links, hash using link reference number 
                         * (which is same as inode ID for file hard links 
                         * created post-Tiger).  For each inodeID, add the 
                         * <prev, id, next> triad.
                         */
                        li = hash_search(inodeID, slots, slotsUsed, linkInfo);
                        if (li) {
                                li->linkCount++;
                        } else {
                                entries++;
                                /* hash_insert() initializes linkCount to 1 */
                                hash_insert(inodeID, slots, slotsUsed++, linkInfo);
                                li = hash_search(inodeID, slots, slotsUsed, linkInfo);
                        }
                        if (li == NULL) {
                                /*
                                 * Either the hash passed in should have the entry, or
                                 * the one we just created should (because we just added it);
                                 * either way, if it's not here, we've got something weird
                                 * going on, so let's just abort now.
                                 */
                                result = ENOENT;
                                goto done;
                        }

                        count = li->linkCount - 1;
                        /* Reallocate memory to store information about file/directory hard links */
                        if ((count % 10) == 0) {
                                tlist = realloc(li->list, (count + 10) * sizeof(struct HardLinkList));
                                if (tlist == NULL) {
                                        free(li->list);
                                        li->list = NULL;
                                        result = ENOMEM;
                                        goto done;
                                } else {
                                        li->list = tlist;       // May be the same
                                        for (i = count; i < (count + 10); i++) {
                                                memset(&li->list[i], 0, sizeof(li->list[i]));
                                        }
                                }
                        }

                        /* Store information about this hard link */
                        if (li->list) {
                                li->list[count].fileID = linkID;
                                li->list[count].prev = file->hl_prevLinkID;
                                li->list[count].next = file->hl_nextLinkID;
                        }
                }
        }

        if (result == btNotFound)
                result = 0;     // If we hit the end of the catalog tree, that's okay

        if (result) {
                goto done;
        }

        /*
         * Next, we iterate through the metadata directory, and check the linked list.
         */

        ClearMemory(&iterator, sizeof(iterator));
        keyp = (HFSPlusCatalogKey*)&iterator.key;
        BuildCatalogKey(metadirid, NULL, true, (CatalogKey*)keyp);
        btrec.bufferAddress = &rec;
        btrec.itemCount = 1;
        btrec.itemSize = sizeof(rec);

        for (result = BTSearchRecord(fcb, &iterator, kInvalidMRUCacheKey, &btrec, &reclen, &iterator);
                result == 0;
                result = BTIterateRecord(fcb, kBTreeNextRecord, &iterator, &btrec, &reclen)) {
                unsigned char filename[64];
                size_t len;
                struct IndirectLinkInfo *li = NULL;

                if (rec.recordType == kHFSPlusFolderThreadRecord ||
                    rec.recordType == kHFSPlusFileThreadRecord)
                        continue;
                if (keyp->parentID != metadirid)
                        break;
                if ((isdir && rec.recordType != kHFSPlusFolderRecord) ||
                    (!isdir && rec.recordType != kHFSPlusFileRecord))
                        continue;
                (void)utf_encodestr(keyp->nodeName.unicode,
                                        keyp->nodeName.length * 2,
                                        filename, &len, sizeof(filename));
                filename[len] = 0;
                if (strstr((char*)filename, prefixName) != (char*)filename)
                        continue;

                if (isdir) {
                        inodeID = rec.hfsPlusFolder.folderID;
                        link_ref_num = 0;
                        flags = rec.hfsPlusFolder.flags;
                        li = hash_search(inodeID, slots, slotsUsed, linkInfo);
                } else {
                        inodeID = rec.hfsPlusFile.fileID;
                        link_ref_num = atol((char*)&filename[prefixlen]);
                        flags = rec.hfsPlusFile.flags;
                        li = hash_search(link_ref_num, slots, slotsUsed, linkInfo);
                }

                /* file/directory inode should always have kHFSHasLinkChainBit set */
                if ((flags & kHFSHasLinkChainMask) == 0) {
                        record_inode_badflags(gp, inodeID, isdir, flags,
                                flags | kHFSHasLinkChainMask, true);
                }

                if (li) {
                        UInt32 first_link_id = 0;
                        uint32_t linkCount = 0;

                        result = get_first_link_id(gp, &rec, inodeID, isdir, &first_link_id);
                        if (result != 0) {
                                if (fsckGetVerbosity(gp->context) >= kDebugLog)
                                        plog("\tError getting first link ID for inode = %u (result=%d)\n", inodeID, result);
                        }

                        /* Check and create repairs for doubly linked list */
                        result = CheckHardLinkList(gp, inodeID, li->list, li->linkCount, first_link_id);

                        linkCount = isdir ? rec.hfsPlusFolder.bsdInfo.special.linkCount : rec.hfsPlusFile.bsdInfo.special.linkCount;
                        if (linkCount != li->linkCount) {
                                RecordBadLinkCount(gp, inodeID, linkCount, li->linkCount);
                        }
                
                        li->flags |= LINKINFO_CHECK;
                        entries--;
                } else {
                        /* Not found in hash, this is orphaned file/directory inode */
                        RecordOrphanInode(gp, isdir, inodeID);
                }
        }

        if (result == btNotFound) {
                result = 0;
        }
        if (result) {
                goto done;
        }

        /* Check for orphan hard links */
        if (entries) {
                int i, j;
                for (i = 0; i < slots; i++) {
                        /* If node is initialized but never checked, record orphan link */
                        if ((linkInfo[i].flags & LINKINFO_INIT) && 
                            ((linkInfo[i].flags & LINKINFO_CHECK) == 0)) {
                                for (j = 0; j < linkInfo[i].linkCount; j++) {
                                        RecordOrphanLink(gp, isdir, linkInfo[i].list[j].fileID);
                                }
                        }
                }
        }

done:
        if (linkInfo) {
                int i;
                for (i = 0; i < slots; i++) {
                        if (linkInfo[i].list)
                                free(linkInfo[i].list);
                }
                free(linkInfo);
        }

        return result;
}

/*
 * CheckHardLinks
 *
 * Check indirect node link counts against 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;
        SFCB              * fcb;
        CatalogRecord       rec;
        HFSPlusCatalogKey * keyp;
        BTreeIterator       iterator;
        FSBufferDescriptor  btrec;
        UInt16              reclen;
        size_t len;
        size_t prefixlen;
        int result;
        unsigned char filename[64];
        PrimeBuckets *catBucket;

        /* All done if no hard links exist. */
        if (info == NULL)
                return (0);

        gp = info->globals;
        fsckPrint(gp->context, hfsHardLinkCheck);

        folderID = info->privDirID;

        catBucket = calloc(1, sizeof(PrimeBuckets));
        if (catBucket == NULL) {
                if (fsckGetVerbosity(gp->context) >= kDebugLog) {
                        plog("CheckHardLinks:  calloc(1, %zu) failed\n", sizeof(PrimeBuckets));
                }
                result = ENOMEM;
                goto exit;
        }
                

        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 != 0) && (result != btNotFound)) { 
                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, sizeof(filename));
                filename[len] = '\0';
                
                /* Report Orphaned nodes only in debug mode */
                if ((strstr((char *)filename, HFS_DELETE_PREFIX) == (char *)filename) &&
                        (fsckGetVerbosity(gp->context) == kDebugLog)) {
                        RecordOrphanOpenUnlink(gp, folderID, filename);
                        continue;               
                }
                                
                if (strstr((char *)filename, HFS_INODE_PREFIX) != (char *)filename)
                        continue;
                
                result = inode_check(gp, catBucket, (CatalogRecord*)&rec, (CatalogKey*)keyp, false);
                if (result) {
                        break;
                }
                filename[0] = '\0';
        }

        if (result == btNotFound) {
                result = 0;
        }

        /*
         * If we've reached this point, and result is clean,
         * then we need to compare the two hard link
         * buckets:  if they don't match, then we have a hard link chain error, and
         * need to either repair it, or just mark the error.
         */
        if ((result == 0) && (info->fileBucket != NULL)) {
                result = compare_prime_buckets(catBucket, info->fileBucket);
                if (result) {
                        record_link_badchain(gp, false);
                        if (fsckGetVerbosity(gp->context) >= kDebugLog) {
                                plog("\tfilelink prime buckets do not match\n");
                        }
                        goto exit;
                }
        }

        /* If hard links created in pre-Leopard OS were detected, they were 
         * added to the hash for checking link counts later.  Check the 
         * link counts from the hash.  Note that the hard links created in 
         * pre-Leopard OS do not have kHFSHasLinkChainBit set in the inode 
         * and the hard links, and the first/prev/next ID is zero --- and 
         * hence they were ignored from CRT check and added to hash.
         */
        if (filelink_entry_count) {
                int i;
                struct filelink_hash *cur;

                /* Since pre-Leopard OS hard links were detected, they 
                 * should be updated to new version.  This is however 
                 * an opportunistic repair and no corruption will be 
                 * reported.  This will be performed only if any other 
                 * file hard link repairs are performed.
                 */
                if (fsckGetVerbosity(gp->context) >= kDebugLog) {
                        plog("\tCheckHardLinks: found %u pre-Leopard file inodes.\n", filelink_entry_count);
                }

                for (i = 0; i < FILELINK_HASH_SIZE; i++) {
                        cur = filelink_head[i];
                        while (cur) {
                                if ((cur->found_link_count == 0) || 
                                    (cur->calc_link_count == 0) ||
                                    (cur->found_link_count != cur->calc_link_count)) {
                                        record_link_badchain(gp, false);
                                        goto exit;
                                }
                                cur = cur->next;
                        }
                }
        }

exit:
        if (filelink_entry_count) {
                filelink_hash_destroy();
        }

        if (catBucket)
                free(catBucket);

        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);
}

/*
 * GetRootDir
 *
 * Get catalog entry for the Root Folder.
 */
static int
GetRootDir(SGlobPtr gp, CatalogRecord * rec)
{
        CatalogKey      key;
        uint16_t        recSize;
        int                 result;
        Boolean                         isHFSPlus;

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

        result = GetCatalogRecordByID(gp, kHFSRootFolderID, isHFSPlus, &key, rec, &recSize);

        return (result);
}

/*
 * RecordOrphanLink
 *
 * Record a repair to delete an orphaned hard links, i.e. hard links 
 * that do not have any corresponding inode.
 */
static int
RecordOrphanLink(SGlobPtr gp, Boolean isdir, UInt32 linkID)
{
        RepairOrderPtr p;
        
        fsckPrint(gp->context, isdir ? E_OrphanDirLink : E_OrphanFileLink, linkID);

        p = AllocMinorRepairOrder(gp, 0);
        if (p == NULL)
                return ENOMEM;

        p->type = isdir ? E_OrphanDirLink : E_OrphanFileLink;
        p->parid = linkID;

        gp->CatStat |= S_LinkErrRepair;

        return 0;
}

/*
 * RecordOrphanInode
 *
 * Record a repair for orphan inode i.e. inodes that do not have 
 * any corresponding hard links.
 */
static int
RecordOrphanInode(SGlobPtr gp, Boolean isdir, UInt32 inodeID)
{
        RepairOrderPtr p;
        
        fsckPrint(gp->context, isdir ? E_OrphanDirInode : E_OrphanFileInode, inodeID);

        p = AllocMinorRepairOrder(gp, 0);
        if (p == NULL)
                return ENOMEM;

        p->type = isdir ? E_OrphanDirInode : E_OrphanFileInode;
        p->parid = inodeID;

        gp->CatStat |= S_LinkErrRepair;

        return 0;
}

/*
 * RecordOrphanOpenUnlink
 *
 * This is only called when debugging is turned on.  Don't
 * record an actual error, just print out a message.
 */
static int
RecordOrphanOpenUnlink(SGlobPtr gp, UInt32 parID, unsigned char* filename)
{
        fsckPrint(gp->context, E_UnlinkedFile, filename);
        
        return (noErr);
}


static int
RecordBadHardLinkChainFirst(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe)
{
        RepairOrderPtr p;
        char goodstr[16], badstr[16];

        fsckPrint(gp->context, E_InvalidLinkChainFirst, fileID);
        sprintf(goodstr, "%u", shouldbe);
        sprintf(badstr, "%u", is);
        fsckPrint(gp->context, E_BadValue, goodstr, badstr);

        p = AllocMinorRepairOrder(gp, 0);

        if (p == NULL) {
                return (ENOMEM);
        }

        p->type = E_InvalidLinkChainFirst;
        p->incorrect = is;
        p->correct = shouldbe;
        p->hint = 0;
        p->parid = fileID;      // *Not* the parent ID!
        gp->CatStat |= S_LinkErrRepair;

        return (0);
}


static int
RecordBadHardLinkPrev(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe)
{
        RepairOrderPtr p;
        char goodstr[16], badstr[16];

        fsckPrint(gp->context, E_InvalidLinkChainPrev, fileID);
        sprintf(goodstr, "%u", shouldbe);
        sprintf(badstr, "%u", is);
        fsckPrint(gp->context, E_BadValue, goodstr, badstr);

        p = AllocMinorRepairOrder(gp, 0);
        if (p == NULL)
                return (R_NoMem);

        p->type = E_InvalidLinkChainPrev;
        p->incorrect = is;
        p->correct = shouldbe;
        p->hint = 0;
        p->parid = fileID;      // *Not* the parent ID
        gp->CatStat |= S_LinkCount;
        return (0);
}

static int
RecordBadHardLinkNext(SGlobPtr gp, UInt32 fileID, UInt32 is, UInt32 shouldbe)
{
        RepairOrderPtr p;
        char goodstr[16], badstr[16];

        fsckPrint(gp->context, E_InvalidLinkChainNext, fileID);

        sprintf(goodstr, "%u", shouldbe);
        sprintf(badstr, "%u", is);
        fsckPrint(gp->context, E_BadValue, goodstr, badstr);

        p = AllocMinorRepairOrder(gp, 0);
        if (p == NULL)
                return (R_NoMem);

        p->type = E_InvalidLinkChainNext;
        p->incorrect = is;
        p->correct = shouldbe;
        p->hint = 0;
        p->parid = fileID;      // *Not* the parent ID
        gp->CatStat |= S_LinkCount;
        return (0);
}

static int 
RecordBadLinkCount(SGlobPtr gp, UInt32 inodeID, UInt32 is, UInt32 shouldbe) 
{
        RepairOrderPtr p;
        char goodstr[16], badstr[16];
        fsckPrint(gp->context, E_InvalidLinkCount, inodeID);

        sprintf(goodstr, "%u", shouldbe);
        sprintf(badstr, "%u", is);
        fsckPrint(gp->context, E_BadValue, goodstr, badstr);

        p = AllocMinorRepairOrder(gp, 0);
        if (p == NULL)
                return (R_NoMem);

        p->type = E_InvalidLinkCount;
        p->incorrect = is;
        p->correct = shouldbe;
        p->hint = 0;
        p->parid = inodeID;     // *Not* the parent ID
        return (0);
}


static void
hash_insert(UInt32 linkID, int totalSlots, int slotsUsed, struct IndirectLinkInfo *linkInfo)
{
        int i, last;
        
        i = linkID & (totalSlots - 1);
        
        last = (i + (totalSlots-1)) % totalSlots;
        while ((i != last) && 
               (linkInfo[i].flags & LINKINFO_INIT) &&
               (linkInfo[i].linkID != linkID)) {
                i = (i + 1) % totalSlots;
        }

        if ((linkInfo[i].flags & LINKINFO_INIT) == 0) {
                if (linkInfo[i].list) {
                        plog ("hash: overwriting data! (old:%u, new:%u)\n", linkInfo[i].linkID, linkID);
                        exit(13);
                }
                linkInfo[i].flags |= LINKINFO_INIT;
                linkInfo[i].linkID = linkID;
                linkInfo[i].linkCount = 1;
        } else if (linkInfo[i].linkID == linkID) {
                plog("hash: duplicate insert! (%d)\n", linkID);
                exit(13);
        } else {
                plog("hash table full (%d entries) \n", slotsUsed);
                exit(14);
        }
}


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

        
        i = linkID & (totalSlots - 1);

        last = (i + (slotsUsed-1)) % totalSlots;
        while ((i != last) && 
               (linkInfo[i].flags & LINKINFO_INIT) &&
               (linkInfo[i].linkID != linkID)) {
                i = (i + 1) % totalSlots;
                ++p;
        }
        
        if ((linkInfo[i].flags & LINKINFO_INIT) && 
            (linkInfo[i].linkID == linkID)) {
                return (&linkInfo[i]);
        } else {
                return (NULL);
        }
}