Return to hfs_vhash.c CVS log

Up to [Apple XNU] / XNU / bsd / hfs

Annotation of XNU/bsd/hfs/hfs_vhash.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
        !             3:  *
        !             4:  * @APPLE_LICENSE_HEADER_START@
        !             5:  * 
        !             6:  * The contents of this file constitute Original Code as defined in and
        !             7:  * are subject to the Apple Public Source License Version 1.1 (the
        !             8:  * "License").  You may not use this file except in compliance with the
        !             9:  * License.  Please obtain a copy of the License at
        !            10:  * http://www.apple.com/publicsource and read it before using this file.
        !            11:  * 
        !            12:  * This Original Code and all software distributed under the License are
        !            13:  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
        !            14:  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
        !            15:  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
        !            16:  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
        !            17:  * License for the specific language governing rights and limitations
        !            18:  * under the License.
        !            19:  * 
        !            20:  * @APPLE_LICENSE_HEADER_END@
        !            21:  */
        !            22: 
        !            23: /* Copyright (c) 1998 Apple Computer, Inc. All Rights Reserved */
        !            24: /*
        !            25:  * Copyright (c) 1982, 1986, 1989, 1991, 1993, 1995
        !            26:  *     The Regents of the University of California.  All rights reserved.
        !            27:  *
        !            28:  * Redistribution and use in source and binary forms, with or without
        !            29:  * modification, are permitted provided that the following conditions
        !            30:  * are met:
        !            31:  * 1. Redistributions of source code must retain the above copyright
        !            32:  *       notice, this list of conditions and the following disclaimer.
        !            33:  * 2. Redistributions in binary form must reproduce the above copyright
        !            34:  *       notice, this list of conditions and the following disclaimer in the
        !            35:  *       documentation and/or other materials provided with the distribution.
        !            36:  * 3. All advertising materials mentioning features or use of this software
        !            37:  *       must display the following acknowledgement:
        !            38:  *     This product includes software developed by the University of
        !            39:  *     California, Berkeley and its contributors.
        !            40:  * 4. Neither the name of the University nor the names of its contributors
        !            41:  *       may be used to endorse or promote products derived from this software
        !            42:  *       without specific prior written permission.
        !            43:  *
        !            44:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
        !            45:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
        !            46:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
        !            47:  * ARE DISCLAIMED.     IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
        !            48:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
        !            49:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
        !            50:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
        !            51:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
        !            52:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
        !            53:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
        !            54:  * SUCH DAMAGE.
        !            55:  *
        !            56:  *     @(#)hfs_vhash.c
        !            57:  *     derived from @(#)ufs_ihash.c    8.7 (Berkeley) 5/17/95
        !            58:  */
        !            59: 
        !            60: #include <sys/param.h>
        !            61: #include <sys/systm.h>
        !            62: #include <sys/vnode.h>
        !            63: #include <sys/malloc.h>
        !            64: #include <sys/proc.h>
        !            65: #include <sys/queue.h>
        !            66: 
        !            67: #include "hfs.h"
        !            68: #include "hfs_dbg.h"
        !            69: 
        !            70: 
        !            71: /*
        !            72:  * Structures associated with hfsnode cacheing.
        !            73:  */
        !            74: LIST_HEAD(vhashhead, hfsnode) *vhashtbl;
        !            75: u_long vhash;          /* size of hash table - 1 */
        !            76: #define HFSNODEHASH(device, nodeID) (&vhashtbl[((device) + (nodeID)) & vhash])
        !            77: struct slock hfs_vhash_slock;
        !            78: 
        !            79: /*
        !            80:  * Initialize hfsnode hash table.
        !            81:  */
        !            82: void
        !            83: hfs_vhashinit()
        !            84: {
        !            85: 
        !            86:        vhashtbl = hashinit(desiredvnodes, M_HFSMNT, &vhash);
        !            87:        simple_lock_init(&hfs_vhash_slock);
        !            88: }
        !            89: 
        !            90: /*
        !            91:  * Use the device/dirID/forkType tuple to find the incore hfsnode, and return a pointer
        !            92:  * to it. If it is in core, but locked, wait for it.
        !            93:  * 
        !            94:  * Acceptable forkTypes are kData, kRsrcFork, kDirectory, or kDefault which translates to either
        !            95:  * kDataFork or kDirectory
        !            96:  *
        !            97:  * While traversing the hash, expext that a hfsnode is in the midst of being allocated, if so, 
        !            98:  * then sleep and try again
        !            99:  */
        !           100: struct vnode *
        !           101: hfs_vhashget(dev, nodeID, forkType)
        !           102:        dev_t dev;
        !           103:        UInt32 nodeID;
        !           104:        UInt8   forkType;
        !           105: {
        !           106:        struct proc *p = current_proc();        /* XXX */
        !           107:        struct hfsnode *hp;
        !           108:        struct vnode *vp;
        !           109: 
        !           110:        DBG_ASSERT(forkType!=kUndefinedFork);
        !           111:        /* 
        !           112:         * Go through the hash list
        !           113:         * If a vnode is in the process of being cleaned out or being
        !           114:         * allocated, wait for it to be finished and then try again
        !           115:         */
        !           116: loop:
        !           117:        simple_lock(&hfs_vhash_slock);
        !           118:        for (hp = HFSNODEHASH(dev, nodeID)->lh_first; hp; hp = hp->h_hash.le_next) {
        !           119:                /* The vnode might be in an incomplete state, so sleep until its ready */
        !           120:                if (hp->h_nodeflags & IN_ALLOCATING) {
        !           121:                        simple_unlock(&hfs_vhash_slock);
        !           122:                        tsleep((caddr_t)hp, PINOD, "hfs_vhashlookup", 0);
        !           123:                        goto loop;
        !           124:                };
        !           125:                        
        !           126:                DBG_ASSERT(hp->h_meta != NULL);
        !           127:                if ((H_FILEID(hp) == nodeID) && (H_DEV(hp) == dev)) {
        !           128:                        /* SER XXX kDefault of meta data (ksysfile) is not assumed here */
        !           129:                        if ((H_FORKTYPE(hp) == forkType) || 
        !           130:                                        (forkType == kAnyFork) ||
        !           131:                                        ((forkType == kDefault) && ((H_FORKTYPE(hp) == kDirectory)
        !           132:                                                        || (H_FORKTYPE(hp) == kDataFork)))) {
        !           133:                                vp = HTOV(hp);
        !           134:                                simple_lock(&vp->v_interlock);
        !           135:                                simple_unlock(&hfs_vhash_slock);
        !           136:                                if (vget(vp, LK_EXCLUSIVE | LK_INTERLOCK, p))
        !           137:                                        goto loop;
        !           138:                                return (vp);
        !           139:                        };
        !           140:                };
        !           141:        };
        !           142:        simple_unlock(&hfs_vhash_slock);
        !           143:        return (NULL);
        !           144: }
        !           145: 
        !           146: 
        !           147: 
        !           148: 
        !           149: /*
        !           150:  * Lock the hfsnode and insert the hfsnode into the hash table, and return it locked.
        !           151:  * Returns the sibling meta data if it exists, elses return NULL
        !           152:  */
        !           153: void
        !           154: hfs_vhashins_sibling(dev, nodeID, hp, fm)
        !           155:        dev_t dev;
        !           156:        UInt32 nodeID;
        !           157:        struct hfsnode *hp;
        !           158:        struct hfsfilemeta **fm;
        !           159: {
        !           160:        struct vhashhead *ipp;
        !           161:        struct hfsnode *thp;
        !           162:        struct hfsfilemeta *tfm;
        !           163: 
        !           164:        DBG_ASSERT(fm != NULL);
        !           165:        DBG_ASSERT(hp != NULL);
        !           166:        DBG_ASSERT(hp->h_meta == NULL);
        !           167:        DBG_ASSERT(H_FORKTYPE(hp)==kDataFork || H_FORKTYPE(hp)==kRsrcFork);
        !           168: 
        !           169:        tfm = NULL;
        !           170:        lockmgr(&hp->h_lock, LK_EXCLUSIVE, (struct slock *)0, current_proc());
        !           171: 
        !           172: 
        !           173:        /* 
        !           174:         * Go through the hash list to see if a sibling exists
        !           175:         * If it does, store it to return
        !           176:         * If a vnode is in the process of being cleaned out or being
        !           177:         * allocated, wait for it to be finished and then try again
        !           178:         */
        !           179: 
        !           180:        ipp = HFSNODEHASH(dev, nodeID);
        !           181: 
        !           182: loop:
        !           183:        simple_lock(&hfs_vhash_slock);
        !           184:        for (thp = ipp->lh_first; thp; thp = thp->h_hash.le_next)       {
        !           185:                if (thp->h_nodeflags & IN_ALLOCATING) {         /* Its in the process of being allocated */
        !           186:                        simple_unlock(&hfs_vhash_slock);
        !           187:                        tsleep((caddr_t)thp, PINOD, "hfs_vhash_ins_meta", 0);
        !           188:                        goto loop;
        !           189:                };
        !           190:                        
        !           191:                DBG_ASSERT(thp->h_meta != NULL);
        !           192:                if ((H_FILEID(thp) == nodeID) && (H_DEV(thp) == dev)) {
        !           193:                        tfm = hp->h_meta = thp->h_meta;
        !           194:                        break;
        !           195:                };
        !           196:        };
        !           197:        
        !           198:        /* Add to sibling list..if it can have them */
        !           199:        if (tfm && (H_FORKTYPE(hp)==kDataFork || H_FORKTYPE(hp)==kRsrcFork)) {
        !           200:                DBG_ASSERT(tfm->h_siblinghead.cqh_first != NULL && tfm->h_siblinghead.cqh_last != NULL);
        !           201:                simple_lock(&tfm->h_siblinglock);
        !           202:                CIRCLEQ_INSERT_HEAD(&tfm->h_siblinghead, hp, h_sibling);
        !           203:                simple_unlock(&tfm->h_siblinglock);
        !           204:        };
        !           205: 
        !           206:        LIST_INSERT_HEAD(ipp, hp, h_hash);
        !           207:        simple_unlock(&hfs_vhash_slock);
        !           208:        *fm = tfm;
        !           209: }
        !           210: 
        !           211: 
        !           212: 
        !           213: /*
        !           214: * Lock the hfsnode and insert the hfsnode into the hash table, and return it locked.
        !           215:  */
        !           216: void
        !           217: hfs_vhashins(dev, nodeID, hp)
        !           218:        dev_t dev;
        !           219:        UInt32 nodeID;
        !           220:      struct hfsnode *hp;
        !           221: {
        !           222:     struct vhashhead *ipp;
        !           223: 
        !           224:     DBG_ASSERT(hp != NULL);
        !           225:     DBG_ASSERT(nodeID != 0);
        !           226: 
        !           227:     lockmgr(&hp->h_lock, LK_EXCLUSIVE, (struct slock *)0, current_proc());
        !           228: 
        !           229:     simple_lock(&hfs_vhash_slock);
        !           230:     ipp = HFSNODEHASH(dev, nodeID);
        !           231:     LIST_INSERT_HEAD(ipp, hp, h_hash);
        !           232:     simple_unlock(&hfs_vhash_slock);
        !           233: }
        !           234: 
        !           235: 
        !           236: /*
        !           237:  * Remove the hfsnode from the hash table and then checks to see if another forks exists.
        !           238:  */
        !           239: void
        !           240: hfs_vhashrem(hp)
        !           241:        struct hfsnode *hp;
        !           242: {
        !           243: 
        !           244:        DBG_ASSERT(hp != NULL);
        !           245:        DBG_ASSERT(hp->h_meta != NULL);
        !           246:        
        !           247:        simple_lock(&hfs_vhash_slock);
        !           248:        
        !           249:        /* Test to see if there are siblings, should only apply to forks */
        !           250:        if (hp->h_meta->h_siblinghead.cqh_first != NULL) {
        !           251:                simple_lock(&hp->h_meta->h_siblinglock);
        !           252:                CIRCLEQ_REMOVE(&hp->h_meta->h_siblinghead, hp, h_sibling);
        !           253:                simple_unlock(&hp->h_meta->h_siblinglock);
        !           254:        };
        !           255:        
        !           256:        LIST_REMOVE(hp, h_hash);
        !           257: 
        !           258: #if HFS_DIAGNOSTIC
        !           259:        hp->h_hash.le_next = NULL;
        !           260:        hp->h_hash.le_prev = NULL;
        !           261: #endif
        !           262: 
        !           263:        
        !           264:        simple_unlock(&hfs_vhash_slock);
        !           265: 
        !           266: 
        !           267: }
        !           268: 
        !           269: 
        !           270: /*
        !           271:  * Moves the entries from one bucket to another
        !           272:  * nodeID is the old bucket id
        !           273:  */
        !           274: void
        !           275: hfs_vhashmove(hp, oldNodeID)
        !           276:        struct hfsnode *hp;
        !           277:        UInt32 oldNodeID;
        !           278: {
        !           279:        struct vhashhead *oldHeadIndex, *newHeadIndex;
        !           280:        struct hfsnode *thp, *nextNode;
        !           281:        UInt32 newNodeID;
        !           282: 
        !           283:        DBG_ASSERT(hp != NULL);
        !           284:        DBG_ASSERT(hp->h_meta != NULL);
        !           285:        
        !           286:     newNodeID = H_FILEID(hp);
        !           287: 
        !           288:     oldHeadIndex = HFSNODEHASH(H_DEV(hp), oldNodeID);
        !           289:     newHeadIndex = HFSNODEHASH(H_DEV(hp), newNodeID);
        !           290:        
        !           291:        /* If it is moving to the same bucket...then we are done */
        !           292:     if (oldHeadIndex == newHeadIndex)
        !           293:                return;
        !           294: 
        !           295: loop:
        !           296:        
        !           297:        /* 
        !           298:         * Go through the old hash list
        !           299:         * If there is a nodeid mismatch, or the nodeid doesnt match the current bucket
        !           300:         * remove it and add it to the right bucket.
        !           301:         * If a vnode is in the process of being cleaned out or being
        !           302:         * allocated, wait for it to be finished and then try again
        !           303:         */
        !           304:        simple_lock(&hfs_vhash_slock);
        !           305:     for (nextNode = oldHeadIndex->lh_first; nextNode; )        {
        !           306:         if (nextNode->h_nodeflags & IN_ALLOCATING) {           /* Its in the process of being allocated */
        !           307:                        simple_unlock(&hfs_vhash_slock);
        !           308:             tsleep((caddr_t)nextNode, PINOD, "hfs_vhashmove", 0);
        !           309:                        goto loop;
        !           310:                        };
        !           311:                        
        !           312:         DBG_ASSERT(nextNode->h_meta != NULL);
        !           313:                thp = nextNode;
        !           314:         nextNode = nextNode->h_hash.le_next;
        !           315:                if (newNodeID == H_FILEID(thp)) {
        !           316:                        LIST_REMOVE(thp, h_hash);
        !           317:             thp->h_hash.le_next = NULL;
        !           318:             thp->h_hash.le_next = NULL;
        !           319:             LIST_INSERT_HEAD(newHeadIndex, thp, h_hash);
        !           320:                        };
        !           321:                };
        !           322:        
        !           323:        simple_unlock(&hfs_vhash_slock);
        !           324: }
        !           325: 
        !           326: #if HFS_DIAGNOSTIC
        !           327: /*
        !           328:  * This will test the hash entry for a given hfsnode
        !           329:  * It will test:
        !           330:  *             1. The uniqei existance of the node
        !           331:  *             2. All other nodes, proper membership to the hash
        !           332:  *             3. Proper termination of the hash
        !           333:  *             4. All members have a non-null h_meta
        !           334:  */
        !           335: void hfs_vhash_dbg(hp)
        !           336:        struct hfsnode *hp;
        !           337: {
        !           338:        struct proc *p = current_proc();        /* XXX */
        !           339:        struct vnode *vp;
        !           340:        struct hfsnode *thp, *tthp;
        !           341:        int                     maxsiblings = 1;
        !           342:        int                     wasFound = false;
        !           343:        struct vhashhead *ipp, *jpp;
        !           344:        dev_t           dev = H_DEV(hp);
        !           345:        UInt32          nodeID = H_FILEID(hp);
        !           346:        UInt8           forkType = H_FORKTYPE(hp);
        !           347:        u_long          forksfound = 0;
        !           348:        
        !           349:        if (forkType==kDataFork || forkType==kRsrcFork)
        !           350:                maxsiblings++;
        !           351:                
        !           352:        if (hp == NULL)
        !           353:        DEBUG_BREAK_MSG(("hash_dgh: Null hfsnode"));
        !           354:        /* 
        !           355:         * Go through the hash list
        !           356:         * If a vnode is in the process of being cleaned out or being
        !           357:         * allocated, wait for it to be finished and then try again
        !           358:         */
        !           359:        ipp = HFSNODEHASH(dev, nodeID);
        !           360: 
        !           361: loop:
        !           362:        simple_lock(&hfs_vhash_slock);
        !           363:        for (thp = ipp->lh_first; thp; thp = thp->h_hash.le_next)       {
        !           364:                if (thp->h_nodeflags & IN_ALLOCATING) {         /* Its in the process of being allocated */
        !           365:                        simple_unlock(&hfs_vhash_slock);
        !           366:                        tsleep((caddr_t)thp, PINOD, "hfs_vhash_ins_meta", 0);
        !           367:                        goto loop;
        !           368:                };
        !           369:                        
        !           370:                if (thp->h_meta == NULL)
        !           371:                DEBUG_BREAK_MSG(("hash_dgh: Null hfs_meta"));
        !           372:            jpp = (HFSNODEHASH(H_DEV(thp), H_FILEID(thp)));
        !           373:            if (ipp != jpp)
        !           374:                DEBUG_BREAK_MSG(("hash_dgh: Member on wrong hash"));
        !           375: 
        !           376:                if ((H_FILEID(thp) == nodeID) && (H_DEV(thp) == dev)) {
        !           377:                        maxsiblings--;
        !           378:                        if (maxsiblings < 0)
        !           379:                        DEBUG_BREAK_MSG(("hash_dgh: Too many siblings"));
        !           380:                    if ((1<<H_FORKTYPE(thp)) & forksfound)
        !           381:                        DEBUG_BREAK_MSG(("hash_dgh: Fork already found"));
        !           382:                    forksfound |= (1<<H_FORKTYPE(thp));
        !           383:                    
        !           384:                    if (H_FORKTYPE(thp) == forkType) {
        !           385:                                if (wasFound == true)
        !           386:                                DEBUG_BREAK_MSG(("hash_dgh: Already found"));
        !           387:                        wasFound = true;
        !           388:                    };
        !           389:                };
        !           390:        };
        !           391:        simple_unlock(&hfs_vhash_slock);
        !           392: 
        !           393:        if (! wasFound)
        !           394:        DEBUG_BREAK_MSG(("hash_dgh: Not found"));
        !           395: 
        !           396: }
        !           397: 
        !           398: #endif /* HFS_DIAGNOSTIC */

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.