[apple/xnu.git] / bsd / hfs / hfs_link.c

/*
 * Copyright (c) 1999-2007 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_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. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * 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_OSREFERENCE_LICENSE_HEADER_END@
 */


#include <sys/systm.h>
#include <sys/kernel.h>
#include <sys/malloc.h>
#include <sys/mount.h>
#include <sys/stat.h>
#include <sys/vnode.h>
#include <vfs/vfs_support.h>
#include <libkern/libkern.h>

#include "hfs.h"
#include "hfs_catalog.h"
#include "hfs_format.h"
#include "hfs_endian.h"


static int cur_link_id = 0;

/*
 * Private directories where hardlink inodes reside.
 */
const char *hfs_private_names[] = {
        HFSPLUSMETADATAFOLDER,      /* FILE HARDLINKS */
        HFSPLUS_DIR_METADATA_FOLDER /* DIRECTORY HARDLINKS */
};


/*
 * Hardlink inodes save the head of their link chain in a
 * private extended attribute.  The following calls are
 * used to access this attribute.
 */
static int  setfirstlink(struct hfsmount * hfsmp, cnid_t fileid, cnid_t firstlink);
static int  getfirstlink(struct hfsmount * hfsmp, cnid_t fileid, cnid_t *firstlink);

/*
 * Create a new catalog link record
 *
 * An indirect link is a reference to an inode (the real
 * file or directory record).
 *
 * All the indirect links for a given inode are chained
 * together in a doubly linked list.
 *
 * Pre-Leopard file hard links do not have kHFSHasLinkChainBit 
 * set and do not have first/prev/next link IDs i.e. the values 
 * are zero.  If a new link is being added to an existing 
 * pre-Leopard file hard link chain, do not set kHFSHasLinkChainBit.
 */
static int
createindirectlink(struct hfsmount *hfsmp, u_int32_t linknum, struct cat_desc *descp,
                   cnid_t nextcnid, cnid_t *linkcnid, int is_inode_linkchain_set)
{
        struct FndrFileInfo *fip;
        struct cat_attr attr;

        if (linknum == 0) {
                printf("createindirectlink: linknum is zero!\n");
                return (EINVAL);
        }

        /* Setup the default attributes */
        bzero(&attr, sizeof(attr));
        
        /* Links are matched to inodes by link ID and to volumes by create date */
        attr.ca_linkref = linknum;
        attr.ca_itime = hfsmp->hfs_itime;
        attr.ca_mode = S_IFREG | S_IRUSR | S_IRGRP | S_IROTH;
        attr.ca_recflags = kHFSHasLinkChainMask | kHFSThreadExistsMask;
        attr.ca_flags = UF_IMMUTABLE;
        fip = (struct FndrFileInfo *)&attr.ca_finderinfo;

        if (descp->cd_flags & CD_ISDIR) {
                fip->fdType    = SWAP_BE32 (kHFSAliasType);
                fip->fdCreator = SWAP_BE32 (kHFSAliasCreator);
                fip->fdFlags   = SWAP_BE16 (kIsAlias);
        } else /* file */ {
                fip->fdType    = SWAP_BE32 (kHardLinkFileType);
                fip->fdCreator = SWAP_BE32 (kHFSPlusCreator);
                fip->fdFlags   = SWAP_BE16 (kHasBeenInited);
                /* If the file inode does not have kHFSHasLinkChainBit set 
                 * and the next link chain ID is zero, assume that this 
                 * is pre-Leopard file inode.  Therefore clear the bit.
                 */
                if ((is_inode_linkchain_set == 0) && (nextcnid == 0)) {
                        attr.ca_recflags &= ~kHFSHasLinkChainMask;
                }
        }
        /* Create the indirect link directly in the catalog */
        return cat_createlink(hfsmp, descp, &attr, nextcnid, linkcnid);
}


/*
 * Make a link to the cnode cp in the directory dp
 * using the name in cnp.
 *
 * The cnodes cp and dcp must be locked.
 */
static int
hfs_makelink(struct hfsmount *hfsmp, struct cnode *cp, struct cnode *dcp,
                struct componentname *cnp)
{
        vfs_context_t ctx = cnp->cn_context;
        struct proc *p = vfs_context_proc(ctx);
        u_int32_t indnodeno = 0;
        char inodename[32]; 
        struct cat_desc to_desc;
        struct cat_desc link_desc;
        int newlink = 0;
        int lockflags;
        int retval = 0;
        cat_cookie_t cookie;
        cnid_t orig_cnid;
        cnid_t linkcnid;
        cnid_t orig_firstlink;
        enum privdirtype type;

        type = S_ISDIR(cp->c_mode) ? DIR_HARDLINKS : FILE_HARDLINKS;

        if (cur_link_id == 0) {
                cur_link_id = ((random() & 0x3fffffff) + 100);
        }
        
        /* We don't allow link nodes in our private system directories. */
        if (dcp->c_fileid == hfsmp->hfs_private_desc[FILE_HARDLINKS].cd_cnid ||
            dcp->c_fileid == hfsmp->hfs_private_desc[DIR_HARDLINKS].cd_cnid) {
                return (EPERM);
        }

        bzero(&cookie, sizeof(cat_cookie_t));
        /* Reserve some space in the Catalog file. */
        if ((retval = cat_preflight(hfsmp, (2 * CAT_CREATE)+ CAT_RENAME, &cookie, p))) {
                return (retval);
        }

        lockflags = SFL_CATALOG | SFL_ATTRIBUTE;
        /* Directory hard links allocate space for a symlink. */
        if (type == DIR_HARDLINKS) {
                lockflags |= SFL_BITMAP;
        }
        lockflags = hfs_systemfile_lock(hfsmp, lockflags, HFS_EXCLUSIVE_LOCK);

        /* Save the current cnid value so we restore it if an error occurs. */
        orig_cnid = cp->c_desc.cd_cnid;

        /*
         * If this is a new hardlink then we need to create the inode
         * and replace the original file/dir object with a link node.
         */
        if ((cp->c_linkcount == 2) && !(cp->c_flag & C_HARDLINK)) {
                newlink = 1;
                bzero(&to_desc, sizeof(to_desc));
                to_desc.cd_parentcnid = hfsmp->hfs_private_desc[type].cd_cnid;
                to_desc.cd_cnid = cp->c_fileid;
                to_desc.cd_flags = (type == DIR_HARDLINKS) ? CD_ISDIR : 0;

                do {
                        if (type == DIR_HARDLINKS) {
                                /* Directory hardlinks always use the cnid. */
                                indnodeno = cp->c_fileid;
                                MAKE_DIRINODE_NAME(inodename, sizeof(inodename),
                                                        indnodeno);
                        } else {
                                /* Get a unique indirect node number */
                                if (retval == 0) {
                                        indnodeno = cp->c_fileid;
                                } else {
                                        indnodeno = cur_link_id++;
                                }
                                MAKE_INODE_NAME(inodename, sizeof(inodename),
                                                indnodeno);
                        }
                        /* Move original file/dir to data node directory */
                        to_desc.cd_nameptr = (const u_int8_t *)inodename;
                        to_desc.cd_namelen = strlen(inodename);
                
                        retval = cat_rename(hfsmp, &cp->c_desc, &hfsmp->hfs_private_desc[type],
                                        &to_desc, NULL);

                        if (retval != 0 && retval != EEXIST) {
                            printf("hfs_makelink: cat_rename to %s failed (%d). fileid %d\n",
                                inodename, retval, cp->c_fileid);
                        }
                } while ((retval == EEXIST) && (type == FILE_HARDLINKS));
                if (retval)
                        goto out;

                /*
                 * Replace original file/dir with a link record.
                 */
                
                bzero(&link_desc, sizeof(link_desc));
                link_desc.cd_nameptr = cp->c_desc.cd_nameptr;
                link_desc.cd_namelen = cp->c_desc.cd_namelen;
                link_desc.cd_parentcnid = cp->c_parentcnid;
                link_desc.cd_flags = S_ISDIR(cp->c_mode) ? CD_ISDIR : 0;

                retval = createindirectlink(hfsmp, indnodeno, &link_desc, 0, &linkcnid, true);
                if (retval) {
                        int err;

                        /* Restore the cnode's cnid. */
                        cp->c_desc.cd_cnid = orig_cnid;

                        /* Put the original file back. */
                        err = cat_rename(hfsmp, &to_desc, &dcp->c_desc, &cp->c_desc, NULL);
                        if (err && err != EIO && err != ENXIO)
                                panic("hfs_makelink: error %d from cat_rename backout 1", err);
                        goto out;
                }
                cp->c_attr.ca_linkref = indnodeno;
                cp->c_desc.cd_cnid = linkcnid;
                /* Directory hard links store the first link in an attribute. */
                if (type == DIR_HARDLINKS) {
                        if (setfirstlink(hfsmp, cp->c_fileid, linkcnid) == 0)
                                cp->c_attr.ca_recflags |= kHFSHasAttributesMask;
                } else /* FILE_HARDLINKS */ {
                        cp->c_attr.ca_firstlink = linkcnid;
                }
                cp->c_attr.ca_recflags |= kHFSHasLinkChainMask;
        } else {
                indnodeno = cp->c_attr.ca_linkref;
        }

        /*
         * Create a catalog entry for the new link (parentID + name).
         */
        
        bzero(&link_desc, sizeof(link_desc));
        link_desc.cd_nameptr = (const u_int8_t *)cnp->cn_nameptr;
        link_desc.cd_namelen = strlen(cnp->cn_nameptr);
        link_desc.cd_parentcnid = dcp->c_fileid;
        link_desc.cd_flags = S_ISDIR(cp->c_mode) ? CD_ISDIR : 0;

        /* Directory hard links store the first link in an attribute. */
        if (type == DIR_HARDLINKS) {
                retval = getfirstlink(hfsmp, cp->c_fileid, &orig_firstlink);
        } else /* FILE_HARDLINKS */ {
                orig_firstlink = cp->c_attr.ca_firstlink;
        }
        if (retval == 0)
                retval = createindirectlink(hfsmp, indnodeno, &link_desc, 
                                orig_firstlink, &linkcnid, 
                                (cp->c_attr.ca_recflags & kHFSHasLinkChainMask));
        if (retval && newlink) {
                int err;

                /* Get rid of new link */
                (void) cat_delete(hfsmp, &cp->c_desc, &cp->c_attr);
                
                /* Restore the cnode's cnid. */
                cp->c_desc.cd_cnid = orig_cnid;
                
                /* Put the original file back. */
                err = cat_rename(hfsmp, &to_desc, &dcp->c_desc, &cp->c_desc, NULL);
                if (err && err != EIO && err != ENXIO)
                        panic("hfs_makelink: error %d from cat_rename backout 2", err);

                cp->c_attr.ca_linkref = 0;
                goto out;
        } else if (retval == 0) {

            /* Update the original first link to point back to the new first link. */
            if (cp->c_attr.ca_recflags & kHFSHasLinkChainMask) {
                (void) cat_updatelink(hfsmp, orig_firstlink, linkcnid, HFS_IGNORABLE_LINK);

                /* Update the inode's first link value. */
                if (type == DIR_HARDLINKS) {
                    if (setfirstlink(hfsmp, cp->c_fileid, linkcnid) == 0)
                        cp->c_attr.ca_recflags |= kHFSHasAttributesMask;
                } else {
                    cp->c_attr.ca_firstlink = linkcnid;
                }
            }
            /*
             * Finally, if this is a new hardlink then:
             *  - update the private system directory
             *  - mark the cnode as a hard link
             */
            if (newlink) {
                vnode_t vp;
                
                if (retval != 0) {
                    panic("hfs_makelink: retval %d but newlink = 1!\n", retval);
                }

                hfsmp->hfs_private_attr[type].ca_entries++;
                /* From application perspective, directory hard link is a 
                 * normal directory.  Therefore count the new directory 
                 * hard link for folder count calculation.
                 */
                if (type == DIR_HARDLINKS) {
                        INC_FOLDERCOUNT(hfsmp, hfsmp->hfs_private_attr[type]);
                }
                retval = cat_update(hfsmp, &hfsmp->hfs_private_desc[type],
                    &hfsmp->hfs_private_attr[type], NULL, NULL);
                if (retval != 0 && retval != EIO && retval != ENXIO) {
                    panic("hfs_makelink: cat_update of privdir failed! (%d)\n", retval);
                }
                cp->c_flag |= C_HARDLINK;
                if ((vp = cp->c_vp) != NULLVP) {
                    if (vnode_get(vp) == 0) {
                        vnode_setmultipath(vp);
                        vnode_put(vp);
                    }
                }
                if ((vp = cp->c_rsrc_vp) != NULLVP) {
                    if (vnode_get(vp) == 0) {
                        vnode_setmultipath(vp);
                        vnode_put(vp);
                    }
                }
                cp->c_touch_chgtime = TRUE;
                cp->c_flag |= C_FORCEUPDATE;
            }
            dcp->c_flag |= C_FORCEUPDATE;
        }
out:
        hfs_systemfile_unlock(hfsmp, lockflags);

        cat_postflight(hfsmp, &cookie, p);
        
        if (retval == 0 && newlink) {
                hfs_volupdate(hfsmp, VOL_MKFILE, 0);
        }
        return (retval);
}


/*
 * link vnode operation
 *
 *  IN vnode_t  a_vp;
 *  IN vnode_t  a_tdvp;
 *  IN struct componentname  *a_cnp;
 *  IN vfs_context_t  a_context;
 */
__private_extern__
int
hfs_vnop_link(struct vnop_link_args *ap)
{
        struct hfsmount *hfsmp;
        struct vnode *vp = ap->a_vp;
        struct vnode *tdvp = ap->a_tdvp;
        struct vnode *fdvp = NULLVP;
        struct componentname *cnp = ap->a_cnp;
        struct cnode *cp;
        struct cnode *tdcp;
        struct cnode *fdcp = NULL;
        struct cat_desc todesc;
        int lockflags = 0;
        int intrans = 0;
        enum vtype v_type;
        int error, ret;

        hfsmp = VTOHFS(vp);
        v_type = vnode_vtype(vp);

        /* No hard links in HFS standard file systems. */
        if (hfsmp->hfs_flags & HFS_STANDARD) {
                return (ENOTSUP);
        }
        /* Linking to a special file is not permitted. */
        if (v_type == VBLK || v_type == VCHR) {
                return (EPERM);  
        }
        if (v_type == VDIR) {
                /* Make sure our private directory exists. */
                if (hfsmp->hfs_private_desc[DIR_HARDLINKS].cd_cnid == 0) {
                        return (EPERM);
                }
                /*
                 * Directory hardlinks (ADLs) have only been qualified on
                 * journaled HFS+.  If/when they are tested on non-journaled
                 * file systems then this test can be removed.
                 */
                if (hfsmp->jnl == NULL) {
                        return (EPERM);
                }
                /* Directory hardlinks also need the parent of the original directory. */
                if ((error = hfs_vget(hfsmp, hfs_currentparent(VTOC(vp)), &fdvp, 1))) {
                        return (error);
                }
        } else {
                /* Make sure our private directory exists. */
                if (hfsmp->hfs_private_desc[FILE_HARDLINKS].cd_cnid == 0) {
                        return (ENOTSUP);
                }
        }
        if (hfs_freeblks(hfsmp, 0) == 0) {
                if (fdvp) {
                        vnode_put(fdvp);
                }
                return (ENOSPC);
        }
        /* Lock the cnodes. */
        if (fdvp) {
                if ((error = hfs_lockfour(VTOC(tdvp), VTOC(vp), VTOC(fdvp), NULL, HFS_EXCLUSIVE_LOCK))) {
                        if (fdvp) {
                                vnode_put(fdvp);
                        }
                        return (error);
                }
                fdcp = VTOC(fdvp);
        } else {
                if ((error = hfs_lockpair(VTOC(tdvp), VTOC(vp), HFS_EXCLUSIVE_LOCK))) {
                        return (error);
                }
        }
        tdcp = VTOC(tdvp);
        cp = VTOC(vp);
        if (cp->c_linkcount >= HFS_LINK_MAX) {
                error = EMLINK;
                goto out;
        }
        if (cp->c_flags & (IMMUTABLE | APPEND)) {
                error = EPERM;
                goto out;
        }
        if (cp->c_flag & (C_NOEXISTS | C_DELETED)) {
                error = ENOENT;
                goto out;
        }

        tdcp->c_flag |= C_DIR_MODIFICATION;

        if (hfs_start_transaction(hfsmp) != 0) {
                error = EINVAL;
                goto out;
        }
        intrans = 1;

        todesc.cd_flags = (v_type == VDIR) ? CD_ISDIR : 0;
        todesc.cd_encoding = 0;
        todesc.cd_nameptr = (const u_int8_t *)cnp->cn_nameptr;
        todesc.cd_namelen = cnp->cn_namelen;
        todesc.cd_parentcnid = tdcp->c_fileid;
        todesc.cd_hint = 0;
        todesc.cd_cnid = 0;

        lockflags = hfs_systemfile_lock(hfsmp, SFL_CATALOG, HFS_SHARED_LOCK);

        /* If destination exists then we lost a race with create. */
        if (cat_lookup(hfsmp, &todesc, 0, NULL, NULL, NULL, NULL) == 0) {
                error = EEXIST;
                goto out;
        }
        if (cp->c_flag & C_HARDLINK) {
                struct cat_attr cattr;

                /* If inode is missing then we lost a race with unlink. */
                if ((cat_idlookup(hfsmp, cp->c_fileid, 0, NULL, &cattr, NULL) != 0) ||
                    (cattr.ca_fileid != cp->c_fileid)) {
                        error = ENOENT;
                        goto out;
                }
        } else {
                cnid_t fileid;

                /* If source is missing then we lost a race with unlink. */
                if ((cat_lookup(hfsmp, &cp->c_desc, 0, NULL, NULL, NULL, &fileid) != 0) ||
                    (fileid != cp->c_fileid)) {
                        error = ENOENT;
                        goto out;
                }
        }
        /* 
         * All directory links must reside in an non-ARCHIVED hierarchy.
         */
        if (v_type == VDIR) {
                /*
                 * - Source parent and destination parent cannot match
                 * - A link is not permitted in the root directory
                 * - Parent of 'pointed at' directory is not the root directory
                 * - The 'pointed at' directory (source) is not an ancestor
                 *   of the new directory hard link (destination).
                 * - No ancestor of the new directory hard link (destination) 
                 *   is a directory hard link.
                 */
                if ((cp->c_parentcnid == tdcp->c_fileid) ||
                    (tdcp->c_fileid == kHFSRootFolderID) ||
                    (cp->c_parentcnid == kHFSRootFolderID) ||
                    cat_check_link_ancestry(hfsmp, tdcp->c_fileid, cp->c_fileid)) {
                        error = EPERM;  /* abide by the rules, you did not */
                        goto out;
                }
        }
        hfs_systemfile_unlock(hfsmp, lockflags);
        lockflags = 0;

        cp->c_linkcount++;
        cp->c_touch_chgtime = TRUE;
        error = hfs_makelink(hfsmp, cp, tdcp, cnp);
        if (error) {
                cp->c_linkcount--;
                hfs_volupdate(hfsmp, VOL_UPDATE, 0);
        } else {
                /* Invalidate negative cache entries in the destination directory */
                if (tdcp->c_flag & C_NEG_ENTRIES) {
                        cache_purge_negatives(tdvp);
                        tdcp->c_flag &= ~C_NEG_ENTRIES;
                }

                /* Update the target directory and volume stats */
                tdcp->c_entries++;
                if (v_type == VDIR) {
                        INC_FOLDERCOUNT(hfsmp, tdcp->c_attr);
                        tdcp->c_attr.ca_recflags |= kHFSHasChildLinkMask;

                        /* Set kHFSHasChildLinkBit in the destination hierarchy */
                        error = cat_set_childlinkbit(hfsmp, tdcp->c_parentcnid);
                        if (error) {
                                printf ("hfs_vnop_link: error updating destination parent chain for %u\n", tdcp->c_cnid);
                                error = 0;
                        }
                }
                tdcp->c_dirchangecnt++;
                tdcp->c_touch_chgtime = TRUE;
                tdcp->c_touch_modtime = TRUE;
                tdcp->c_flag |= C_FORCEUPDATE;

                error = hfs_update(tdvp, 0);
                if (error && error != EIO && error != ENXIO) {
                        panic("hfs_vnop_link: error updating tdvp %p\n", tdvp);
                }
                
                if ((v_type == VDIR) && 
                    (fdcp != NULL) && 
                    ((fdcp->c_attr.ca_recflags & kHFSHasChildLinkMask) == 0)) {

                        fdcp->c_attr.ca_recflags |= kHFSHasChildLinkMask;
                        fdcp->c_touch_chgtime = TRUE;
                        fdcp->c_flag |= C_FORCEUPDATE;
                        error = hfs_update(fdvp, 0);
                        if (error && error != EIO && error != ENXIO) {
                                panic("hfs_vnop_link: error updating fdvp %p\n", fdvp);
                        }

                        /* Set kHFSHasChildLinkBit in the source hierarchy */
                        error = cat_set_childlinkbit(hfsmp, fdcp->c_parentcnid);
                        if (error) {
                                printf ("hfs_vnop_link: error updating source parent chain for %u\n", fdcp->c_cnid);
                                error = 0;
                        }
                }
                hfs_volupdate(hfsmp, VOL_MKFILE,
                        (tdcp->c_cnid == kHFSRootFolderID));
        }
        /* Make sure update occurs inside transaction */
        cp->c_flag |= C_FORCEUPDATE;  

        if ((error == 0) && (ret = hfs_update(vp, TRUE)) != 0 && ret != EIO && ret != ENXIO) {
                panic("hfs_vnop_link: error %d updating vp @ %p\n", ret, vp);
        }

        HFS_KNOTE(vp, NOTE_LINK);
        HFS_KNOTE(tdvp, NOTE_WRITE);
out:
        if (lockflags) {
                hfs_systemfile_unlock(hfsmp, lockflags);
        }
        if (intrans) {
                hfs_end_transaction(hfsmp);
        }

        tdcp->c_flag &= ~C_DIR_MODIFICATION;
        wakeup((caddr_t)&tdcp->c_flag);

        if (fdcp) {
                hfs_unlockfour(tdcp, cp, fdcp, NULL);
        } else {
                hfs_unlockpair(tdcp, cp);
        }
        if (fdvp) {
                vnode_put(fdvp);
        }
        return (error);
}


/*
 * Remove a link to a hardlink file/dir.
 *
 * Note: dvp and vp cnodes are already locked.
 */
__private_extern__
int
hfs_unlink(struct hfsmount *hfsmp, struct vnode *dvp, struct vnode *vp, struct componentname *cnp, int skip_reserve)
{
        struct cnode *cp;
        struct cnode *dcp;
        struct cat_desc cndesc;
        struct timeval tv;
        char inodename[32];
        cnid_t  prevlinkid;
        cnid_t  nextlinkid;
        int lockflags = 0;
        int started_tr;
        int rm_priv_file = 0;
        int error;
        
        if (hfsmp->hfs_flags & HFS_STANDARD) {
                return (EPERM);
        }
        cp = VTOC(vp);
        dcp = VTOC(dvp);

        dcp->c_flag |= C_DIR_MODIFICATION;
        
        /* Remove the entry from the namei cache: */
        cache_purge(vp);

        if ((error = hfs_start_transaction(hfsmp)) != 0) {
                started_tr = 0;
                goto out;
        }
        started_tr = 1;

        /* 
         * Protect against a race with rename by using the component
         * name passed in and parent id from dvp (instead of using 
         * the cp->c_desc which may have changed).  
         *
         * Re-lookup the component name so we get the correct cnid
         * for the name (as opposed to the c_cnid in the cnode which
         * could have changed before the cnode was locked).
         */
        cndesc.cd_flags = vnode_isdir(vp) ? CD_ISDIR : 0;
        cndesc.cd_encoding = cp->c_desc.cd_encoding;
        cndesc.cd_nameptr = (const u_int8_t *)cnp->cn_nameptr;
        cndesc.cd_namelen = cnp->cn_namelen;
        cndesc.cd_parentcnid = dcp->c_fileid;
        cndesc.cd_hint = dcp->c_childhint;

        lockflags = SFL_CATALOG | SFL_ATTRIBUTE;
        if (cndesc.cd_flags & CD_ISDIR) {
                /* We'll be removing the alias resource allocation blocks. */
                lockflags |= SFL_BITMAP;
        }
        lockflags = hfs_systemfile_lock(hfsmp, lockflags, HFS_EXCLUSIVE_LOCK);

        if ((error = cat_lookuplink(hfsmp, &cndesc, &cndesc.cd_cnid, &prevlinkid, &nextlinkid))) {
                goto out;
        }

        /* Reserve some space in the catalog file. */
        if (!skip_reserve && (error = cat_preflight(hfsmp, 2 * CAT_DELETE, NULL, 0))) {
                goto out;
        }

        /* Purge any cached origin entries for a directory or file hard link. */
        hfs_relorigin(cp, dcp->c_fileid);
        if (dcp->c_fileid != dcp->c_cnid) {
                hfs_relorigin(cp, dcp->c_cnid);
        }

        /* Delete the link record. */
        if ((error = cat_deletelink(hfsmp, &cndesc))) {
                goto out;
        }

        /* Update the parent directory. */
        if (dcp->c_entries > 0) {
                dcp->c_entries--;
        }
        if (cndesc.cd_flags & CD_ISDIR) {
                DEC_FOLDERCOUNT(hfsmp, dcp->c_attr);
        }
        dcp->c_dirchangecnt++;
        microtime(&tv);
        dcp->c_ctime = tv.tv_sec;
        dcp->c_mtime = tv.tv_sec;
        (void ) cat_update(hfsmp, &dcp->c_desc, &dcp->c_attr, NULL, NULL);

        /*
         * If this is the last link then we need to process the inode.
         * Otherwise we need to fix up the link chain.
         */
        --cp->c_linkcount;
        if (cp->c_linkcount < 1) {
                char delname[32];
                struct cat_desc to_desc;
                struct cat_desc from_desc;

                /*
                 * If a file inode or directory inode is being deleted, rename 
                 * it to an open deleted file.  This ensures that deletion 
                 * of inode and its corresponding extended attributes does 
                 * not overflow the journal.  This inode will be deleted 
                 * either in hfs_vnop_inactive() or in hfs_remove_orphans(). 
                 * Note: a rename failure here is not fatal.
                 */     
                bzero(&from_desc, sizeof(from_desc));
                bzero(&to_desc, sizeof(to_desc));
                if (vnode_isdir(vp)) {
                        if (cp->c_entries != 0) {
                                panic("hfs_unlink: dir not empty (id %d, %d entries)", cp->c_fileid, cp->c_entries);
                        }
                        MAKE_DIRINODE_NAME(inodename, sizeof(inodename),
                                                cp->c_attr.ca_linkref);
                        from_desc.cd_parentcnid = hfsmp->hfs_private_desc[DIR_HARDLINKS].cd_cnid;
                        from_desc.cd_flags = CD_ISDIR;
                        to_desc.cd_flags = CD_ISDIR;
                } else { 
                        MAKE_INODE_NAME(inodename, sizeof(inodename),
                                        cp->c_attr.ca_linkref);
                        from_desc.cd_parentcnid = hfsmp->hfs_private_desc[FILE_HARDLINKS].cd_cnid;
                        from_desc.cd_flags = 0;
                        to_desc.cd_flags = 0;
                }
                from_desc.cd_nameptr = (const u_int8_t *)inodename;
                from_desc.cd_namelen = strlen(inodename);
                from_desc.cd_cnid = cp->c_fileid;

                MAKE_DELETED_NAME(delname, sizeof(delname), cp->c_fileid);
                to_desc.cd_nameptr = (const u_int8_t *)delname;
                to_desc.cd_namelen = strlen(delname);
                to_desc.cd_parentcnid = hfsmp->hfs_private_desc[FILE_HARDLINKS].cd_cnid;
                to_desc.cd_cnid = cp->c_fileid;

                error = cat_rename(hfsmp, &from_desc, &hfsmp->hfs_private_desc[FILE_HARDLINKS],
                                   &to_desc, (struct cat_desc *)NULL);
                if (error == 0) {
                        cp->c_flag |= C_DELETED;
                        cp->c_attr.ca_recflags &= ~kHFSHasLinkChainMask;
                        cp->c_attr.ca_firstlink = 0;
                        if (vnode_isdir(vp)) {
                                hfsmp->hfs_private_attr[DIR_HARDLINKS].ca_entries--;
                                DEC_FOLDERCOUNT(hfsmp, hfsmp->hfs_private_attr[DIR_HARDLINKS]);

                                hfsmp->hfs_private_attr[FILE_HARDLINKS].ca_entries++;
                                INC_FOLDERCOUNT(hfsmp, hfsmp->hfs_private_attr[FILE_HARDLINKS]);

                                (void)cat_update(hfsmp, &hfsmp->hfs_private_desc[DIR_HARDLINKS],
                                        &hfsmp->hfs_private_attr[DIR_HARDLINKS], NULL, NULL);
                                (void)cat_update(hfsmp, &hfsmp->hfs_private_desc[FILE_HARDLINKS],
                                        &hfsmp->hfs_private_attr[FILE_HARDLINKS], NULL, NULL);
                        }
                } else {
                        error = 0;  /* rename failure here is not fatal */
                }
        } else /* Still some links left */ {
                cnid_t firstlink;

                /*
                 * Update the start of the link chain.
                 * Note: Directory hard links store the first link in an attribute.
                 */
                if (vnode_isdir(vp) &&
                    getfirstlink(hfsmp, cp->c_fileid, &firstlink) == 0 &&
                    firstlink == cndesc.cd_cnid) {
                        if (setfirstlink(hfsmp, cp->c_fileid, nextlinkid) == 0)
                                cp->c_attr.ca_recflags |= kHFSHasAttributesMask;
                } else if (vnode_isreg(vp) && cp->c_attr.ca_firstlink == cndesc.cd_cnid) {
                        cp->c_attr.ca_firstlink = nextlinkid;
                }
                /* Update previous link. */
                if (prevlinkid) {
                        (void) cat_updatelink(hfsmp, prevlinkid, HFS_IGNORABLE_LINK, nextlinkid);
                }
                /* Update next link. */
                if (nextlinkid) {
                        (void) cat_updatelink(hfsmp, nextlinkid, prevlinkid, HFS_IGNORABLE_LINK);
                }
        }

        /* Push new link count to disk. */
        cp->c_ctime = tv.tv_sec;        
        (void) cat_update(hfsmp, &cp->c_desc, &cp->c_attr, NULL, NULL);

        /* All done with the system files. */
        hfs_systemfile_unlock(hfsmp, lockflags);
        lockflags = 0;

        /* Update file system stats. */
        hfs_volupdate(hfsmp, VOL_RMFILE, (dcp->c_cnid == kHFSRootFolderID));
        /* The last link of a directory removed the inode. */
        if (rm_priv_file) {
                hfs_volupdate(hfsmp, VOL_RMFILE, 0);
        }
        /*
         * All done with this cnode's descriptor...
         *
         * Note: all future catalog calls for this cnode may be
         * by fileid only.  This is OK for HFS (which doesn't have
         * file thread records) since HFS doesn't support hard links.
         */
        cat_releasedesc(&cp->c_desc);

        HFS_KNOTE(dvp, NOTE_WRITE);
        HFS_KNOTE(vp, NOTE_DELETE);
out:
        if (lockflags) {
                hfs_systemfile_unlock(hfsmp, lockflags);
        }
        if (started_tr) {
                hfs_end_transaction(hfsmp);
        }

        dcp->c_flag &= ~C_DIR_MODIFICATION;
        wakeup((caddr_t)&dcp->c_flag);

        return (error);
}


/*
 * Initialize the HFS+ private system directories.
 *
 * These directories are used to hold the inodes
 * for file and directory hardlinks as well as
 * open-unlinked files.
 *
 * If they don't yet exist they will get created.
 *
 * This call is assumed to be made during mount.
 */
__private_extern__
void
hfs_privatedir_init(struct hfsmount * hfsmp, enum privdirtype type)
{
        struct vnode * dvp = NULLVP;
        struct cnode * dcp = NULL;
        struct cat_desc *priv_descp;
        struct cat_attr *priv_attrp;
        struct FndrDirInfo * fndrinfo;
        struct timeval tv;
        int lockflags;
        int trans = 0;
        int error;
        
        if (hfsmp->hfs_flags & HFS_STANDARD) {
                return;
        }

        priv_descp = &hfsmp->hfs_private_desc[type];
        priv_attrp = &hfsmp->hfs_private_attr[type];

        /* Check if directory already exists. */
        if (priv_descp->cd_cnid != 0) {
                return;
        }

        priv_descp->cd_parentcnid = kRootDirID;
        priv_descp->cd_nameptr = (const u_int8_t *)hfs_private_names[type];
        priv_descp->cd_namelen = strlen((const char *)priv_descp->cd_nameptr);
        priv_descp->cd_flags = CD_ISDIR | CD_DECOMPOSED;

        lockflags = hfs_systemfile_lock(hfsmp, SFL_CATALOG, HFS_SHARED_LOCK);
        error = cat_lookup(hfsmp, priv_descp, 0, NULL, priv_attrp, NULL, NULL);
        hfs_systemfile_unlock(hfsmp, lockflags);

        if (error == 0) {
                if (type == FILE_HARDLINKS) {
                        hfsmp->hfs_metadata_createdate = priv_attrp->ca_itime;
                }
                priv_descp->cd_cnid = priv_attrp->ca_fileid;
                goto exit;
        }

        /* Directory is missing, if this is read-only then we're done. */
        if (hfsmp->hfs_flags & HFS_READ_ONLY) {
                goto exit;
        }

        /* Grab the root directory so we can update it later. */
        if (hfs_vget(hfsmp, kRootDirID, &dvp, 0) != 0) {
                goto exit;
        }
        dcp = VTOC(dvp);

        /* Setup the default attributes */
        bzero(priv_attrp, sizeof(struct cat_attr));
        priv_attrp->ca_flags = UF_IMMUTABLE | UF_HIDDEN;
        priv_attrp->ca_mode = S_IFDIR;
        if (type == DIR_HARDLINKS) {
                priv_attrp->ca_mode |= S_ISVTX | S_IRUSR | S_IXUSR | S_IRGRP |
                                       S_IXGRP | S_IROTH | S_IXOTH;
        }
        priv_attrp->ca_linkcount = 1;
        priv_attrp->ca_itime = hfsmp->hfs_itime;
        priv_attrp->ca_recflags = kHFSHasFolderCountMask;
        
        fndrinfo = (struct FndrDirInfo *)&priv_attrp->ca_finderinfo;
        fndrinfo->frLocation.v = SWAP_BE16(16384);
        fndrinfo->frLocation.h = SWAP_BE16(16384);
        fndrinfo->frFlags = SWAP_BE16(kIsInvisible + kNameLocked);              

        if (hfs_start_transaction(hfsmp) != 0) {
                goto exit;
        }
        trans = 1;

        lockflags = hfs_systemfile_lock(hfsmp, SFL_CATALOG, HFS_EXCLUSIVE_LOCK);

        /* Make sure there's space in the Catalog file. */
        if (cat_preflight(hfsmp, CAT_CREATE, NULL, 0) != 0) {
                hfs_systemfile_unlock(hfsmp, lockflags);
                goto exit;
        }

        /* Create the private directory on disk. */
        error = cat_create(hfsmp, priv_descp, priv_attrp, NULL);
        if (error == 0) {
                priv_descp->cd_cnid = priv_attrp->ca_fileid;

                /* Update the parent directory */
                dcp->c_entries++;
                INC_FOLDERCOUNT(hfsmp, dcp->c_attr);
                dcp->c_dirchangecnt++;
                microtime(&tv);
                dcp->c_ctime = tv.tv_sec;
                dcp->c_mtime = tv.tv_sec;
                (void) cat_update(hfsmp, &dcp->c_desc, &dcp->c_attr, NULL, NULL);
        }

        hfs_systemfile_unlock(hfsmp, lockflags);
        
        if (error) {
                goto exit;
        }
        if (type == FILE_HARDLINKS) {
                hfsmp->hfs_metadata_createdate = hfsmp->hfs_itime;
        }
        hfs_volupdate(hfsmp, VOL_MKDIR, 1);
exit:
        if (trans) {
                hfs_end_transaction(hfsmp);
        }
        if (dvp) {
                hfs_unlock(dcp);
                vnode_put(dvp);
        }
        if ((error == 0) && (type == DIR_HARDLINKS)) {
                hfs_xattr_init(hfsmp);
        }
}


/*
 * Lookup a hardlink link (from chain)
 */
__private_extern__
int
hfs_lookuplink(struct hfsmount *hfsmp, cnid_t linkfileid, cnid_t *prevlinkid,  cnid_t *nextlinkid)
{
        int lockflags;
        int error;

        *prevlinkid = 0;
        *nextlinkid = 0;

        lockflags = hfs_systemfile_lock(hfsmp, SFL_CATALOG, HFS_SHARED_LOCK);

        error = cat_lookuplinkbyid(hfsmp, linkfileid, prevlinkid, nextlinkid);
        if (error == ENOLINK) {
                hfs_systemfile_unlock(hfsmp, lockflags);
                lockflags = hfs_systemfile_lock(hfsmp, SFL_ATTRIBUTE, HFS_SHARED_LOCK);

                error = getfirstlink(hfsmp, linkfileid, nextlinkid);
        }
        hfs_systemfile_unlock(hfsmp, lockflags);

        return (error);
}

/*
 * Cache the origin of a directory or file hard link
 *
 * cnode must be lock on entry
 */
__private_extern__
void
hfs_savelinkorigin(cnode_t *cp, cnid_t parentcnid)
{
        linkorigin_t *origin = NULL;
        void * thread = current_thread();
        int count = 0;
        int maxorigins = (S_ISDIR(cp->c_mode)) ? MAX_CACHED_ORIGINS : MAX_CACHED_FILE_ORIGINS;

        /*
         *  Look for an existing origin first.  If not found, create/steal one.
         */
        TAILQ_FOREACH(origin, &cp->c_originlist, lo_link) {
                ++count;
                if (origin->lo_thread == thread) {
                        TAILQ_REMOVE(&cp->c_originlist, origin, lo_link);
                        break;
                }
        }
        if (origin == NULL) {
                /* Recycle the last (i.e., the oldest) if we have too many. */
                if (count > maxorigins) {
                        origin = TAILQ_LAST(&cp->c_originlist, hfs_originhead);
                        TAILQ_REMOVE(&cp->c_originlist, origin, lo_link);
                } else {
                        MALLOC(origin, linkorigin_t *, sizeof(linkorigin_t), M_TEMP, M_WAITOK);
                }
                origin->lo_thread = thread;
        }
        origin->lo_cnid = cp->c_cnid;
        origin->lo_parentcnid = parentcnid;
        TAILQ_INSERT_HEAD(&cp->c_originlist, origin, lo_link);
}

/*
 * Release any cached origins for a directory or file hard link
 *
 * cnode must be lock on entry
 */
__private_extern__
void
hfs_relorigins(struct cnode *cp)
{
        linkorigin_t *origin, *prev;

        TAILQ_FOREACH_SAFE(origin, &cp->c_originlist, lo_link, prev) {
                FREE(origin, M_TEMP);
        }
        TAILQ_INIT(&cp->c_originlist);
}

/*
 * Release a specific origin for a directory or file hard link
 *
 * cnode must be lock on entry
 */
__private_extern__
void
hfs_relorigin(struct cnode *cp, cnid_t parentcnid)
{
        linkorigin_t *origin, *prev;
        void * thread = current_thread();

        TAILQ_FOREACH_SAFE(origin, &cp->c_originlist, lo_link, prev) {
                if ((origin->lo_thread == thread) ||
                    (origin->lo_parentcnid == parentcnid)) {
                        TAILQ_REMOVE(&cp->c_originlist, origin, lo_link);
                        FREE(origin, M_TEMP);
                        break;
                }
        }
}

/*
 * Test if a directory or file hard link has a cached origin
 *
 * cnode must be lock on entry
 */
__private_extern__
int
hfs_haslinkorigin(cnode_t *cp)
{
        if (cp->c_flag & C_HARDLINK) {
                linkorigin_t *origin;
                void * thread = current_thread();
        
                TAILQ_FOREACH(origin, &cp->c_originlist, lo_link) {
                        if (origin->lo_thread == thread) {
                                return (1);
                        }
                }
        }
        return (0);
}

/*
 * Obtain the current parent cnid of a directory or file hard link
 *
 * cnode must be lock on entry
 */
__private_extern__
cnid_t
hfs_currentparent(cnode_t *cp)
{
        if (cp->c_flag & C_HARDLINK) {
                linkorigin_t *origin;
                void * thread = current_thread();
        
                TAILQ_FOREACH(origin, &cp->c_originlist, lo_link) {
                        if (origin->lo_thread == thread) {
                                return (origin->lo_parentcnid);
                        }
                }
        }
        return (cp->c_parentcnid);
}

/*
 * Obtain the current cnid of a directory or file hard link
 *
 * cnode must be lock on entry
 */
__private_extern__
cnid_t
hfs_currentcnid(cnode_t *cp)
{
        if (cp->c_flag & C_HARDLINK) {
                linkorigin_t *origin;
                void * thread = current_thread();
        
                TAILQ_FOREACH(origin, &cp->c_originlist, lo_link) {
                        if (origin->lo_thread == thread) {
                                return (origin->lo_cnid);
                        }
                }
        }
        return (cp->c_cnid);
}


/*
 * Set the first link attribute for a given file id.
 *
 * The attributes b-tree must already be locked.
 * If journaling is enabled, a transaction must already be started.
 */
static int
setfirstlink(struct hfsmount * hfsmp, cnid_t fileid, cnid_t firstlink)
{
        FCB * btfile;
        BTreeIterator * iterator;
        FSBufferDescriptor btdata;
        u_int8_t attrdata[FIRST_LINK_XATTR_REC_SIZE];
        HFSPlusAttrData *dataptr;
        int result;
        u_int16_t datasize;

        if (hfsmp->hfs_attribute_cp == NULL) {
                return (EPERM);
        }
        MALLOC(iterator, BTreeIterator *, sizeof(*iterator), M_TEMP, M_WAITOK);
        bzero(iterator, sizeof(*iterator));

        result = hfs_buildattrkey(fileid, FIRST_LINK_XATTR_NAME, (HFSPlusAttrKey *)&iterator->key);
        if (result) {
                goto out;
        }
        dataptr = (HFSPlusAttrData *)&attrdata[0];
        dataptr->recordType = kHFSPlusAttrInlineData;
        dataptr->reserved[0] = 0;
        dataptr->reserved[1] = 0;

        /*
         * Since attrData is variable length, we calculate the size of
         * attrData by subtracting the size of all other members of
         * structure HFSPlusAttData from the size of attrdata.
         */
        (void)snprintf((char *)&dataptr->attrData[0],
                        sizeof(dataptr) - (4 * sizeof(uint32_t)),
                        "%lu", (unsigned long)firstlink);
        dataptr->attrSize = 1 + strlen((char *)&dataptr->attrData[0]);

        /* Calculate size of record rounded up to multiple of 2 bytes. */
        datasize = sizeof(HFSPlusAttrData) - 2 + dataptr->attrSize + ((dataptr->attrSize & 1) ? 1 : 0);

        btdata.bufferAddress = dataptr;
        btdata.itemSize = datasize;
        btdata.itemCount = 1;

        btfile = hfsmp->hfs_attribute_cp->c_datafork;

        /* Insert the attribute. */
        result = BTInsertRecord(btfile, iterator, &btdata, datasize);
        if (result == btExists) {
                result = BTReplaceRecord(btfile, iterator, &btdata, datasize);
        }
        (void) BTFlushPath(btfile);
out:
        FREE(iterator, M_TEMP);

        return MacToVFSError(result);
}

/*
 * Get the first link attribute for a given file id.
 *
 * The attributes b-tree must already be locked.
 */
static int
getfirstlink(struct hfsmount * hfsmp, cnid_t fileid, cnid_t *firstlink)
{
        FCB * btfile;
        BTreeIterator * iterator;
        FSBufferDescriptor btdata;
        u_int8_t attrdata[FIRST_LINK_XATTR_REC_SIZE];
        HFSPlusAttrData *dataptr;
        int result;
        u_int16_t datasize;

        if (hfsmp->hfs_attribute_cp == NULL) {
                return (EPERM);
        }
        MALLOC(iterator, BTreeIterator *, sizeof(*iterator), M_TEMP, M_WAITOK);
        bzero(iterator, sizeof(*iterator));

        result = hfs_buildattrkey(fileid, FIRST_LINK_XATTR_NAME, (HFSPlusAttrKey *)&iterator->key);
        if (result)
                goto out;

        dataptr = (HFSPlusAttrData *)&attrdata[0];
        datasize = sizeof(attrdata);

        btdata.bufferAddress = dataptr;
        btdata.itemSize = sizeof(attrdata);
        btdata.itemCount = 1;

        btfile = hfsmp->hfs_attribute_cp->c_datafork;

        result = BTSearchRecord(btfile, iterator, &btdata, NULL, NULL);
        if (result)
                goto out;

        if (dataptr->attrSize < 3) {
                result = ENOENT;
                goto out;
        }
        *firstlink = strtoul((char*)&dataptr->attrData[0], NULL, 10);
out:
        FREE(iterator, M_TEMP);

        return MacToVFSError(result);
}