[apple/xnu.git] / bsd / hfs / hfscommon / Catalog / CatalogIterators.c

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

        Contains:       Catalog Iterator Implementation

        Version:        HFS Plus 1.0

        Copyright:      © 1997-1998 by Apple Computer, Inc., all rights reserved.

        File Ownership:

                DRI:                            Don Brady

                Other Contact:          Mark Day

                Technology:                     Mac OS File System

        Writers:

                (msd)   Mark Day
                (djb)   Don Brady

        Change History (most recent first):
           <MacOSX>      4/23/98        djb             Re-enable InvalidateCatalogCache (was commented out).
           <MacOSX>       4/6/98        djb             Add locking for cache globals (list) and iterators.
           <MacOSX>       4/2/98        djb             Define gCatalogCacheGlobals here instead of FSVars.
           <MacOSX>      3/31/98        djb             Sync up with final HFSVolumes.h header file.

           <CS3>        11/13/97        djb             Radar #1683572 - Fix for indexed GetFileInfo.
           <CS2>        10/17/97        msd             Bug 1683506. Add support for long Unicode names in
                                                                        CatalogIterators. Added a single global buffer for long Unicode
                                                                        names; it is used by at most one CatalogIterator at a time.
           <CS1>         10/1/97        djb             first checked in
*/


#include "../../hfs_macos_defs.h"
#include "../../hfs.h"
#include "../../hfs_dbg.h"
#include "../../hfs_format.h"

#include        "../headers/FileMgrInternal.h"
#include        "../headers/BTreesInternal.h"
#include        "../headers/CatalogPrivate.h"


#include <sys/param.h>
#include <sys/systm.h>
#include <libkern/libkern.h>
#include <sys/lock.h>

static void     InsertCatalogIteratorAsMRU( CatalogCacheGlobals *cacheGlobals, CatalogIterator *iterator );

static void InsertCatalogIteratorAsLRU( CatalogCacheGlobals *cacheGlobals, CatalogIterator *iterator );

static void PrepareForLongName( CatalogIterator *iterator );


#if TARGET_API_MACOS_X
  CatalogCacheGlobals  *gCatalogCacheGlobals;

  #define GetCatalogCacheGlobals()              (gCatalogCacheGlobals)

  #define CATALOG_ITER_LIST_LOCK(g)             simple_lock(&(g)->simplelock)

  #define CATALOG_ITER_LIST_UNLOCK(g)   simple_unlock(&(g)->simplelock)

  #define CI_LOCK(i)                                    lockmgr(&(i)->iterator_lock, LK_EXCLUSIVE, (simple_lock_t) 0, current_proc())
        
#define CI_UNLOCK(i)                                    lockmgr(&(i)->iterator_lock, LK_RELEASE, (simple_lock_t) 0, current_proc())

#define CI_SLEEPLESS_LOCK(i)                    lockmgr(&(i)->iterator_lock, LK_EXCLUSIVE | LK_NOWAIT, (simple_lock_t) 0, current_proc())       

#define CI_LOCK_FROM_LIST(g,i)          lockmgr(&(i)->iterator_lock, LK_EXCLUSIVE | LK_INTERLOCK, &(g)->simplelock, current_proc())

#else /* TARGET_API_MACOS_X */

  #define GetCatalogCacheGlobals()              ((CatalogCacheGlobals*) ((FSVarsRec*) LMGetFSMVars()->gCatalogCacheGlobals))

  #define CATALOG_ITER_LIST_LOCK(g)

  #define CATALOG_ITER_LIST_UNLOCK(g)

  #define CI_LOCK(i)                                    0
        
  #define CI_UNLOCK(i)                                  0
  
  #define CI_SLEEPLESS_LOCK(i)                  0

  #define CI_LOCK_FROM_LIST(g,i)                0

#endif


//_______________________________________________________________________________
//      Routine:        InitCatalogCache
//
//      Function:       Allocates cache, and initializes all the cache structures.
//
//_______________________________________________________________________________
OSErr
InitCatalogCache(void)
{
        CatalogCacheGlobals *   cacheGlobals;
        CatalogIterator *               iterator;
        UInt32                                  cacheSize;
        UInt16                                  i;
        UInt16                                  lastIterator;
        OSErr                                   err;


        cacheSize = sizeof(CatalogCacheGlobals) + ( kCatalogIteratorCount * sizeof(CatalogIterator) );
        cacheGlobals = (CatalogCacheGlobals *) NewPtrSysClear( cacheSize );

        cacheGlobals->iteratorCount = kCatalogIteratorCount;

        lastIterator = kCatalogIteratorCount - 1;               //      last iterator number, since they start at 0
        
        //      Initialize the MRU order for the cache
        cacheGlobals->mru = (CatalogIterator *) ( (Ptr)cacheGlobals + sizeof(CatalogCacheGlobals) );

        //      Initialize the LRU order for the cache
        cacheGlobals->lru = (CatalogIterator *) ( (Ptr)(cacheGlobals->mru) + (lastIterator * sizeof(CatalogIterator)) );
        

        //      Traverse iterators, setting initial mru, lru, and default values
        for ( i = 0, iterator = cacheGlobals->mru; i < kCatalogIteratorCount ; i++, iterator = iterator->nextMRU )
        {
                if ( i == lastIterator )
                        iterator->nextMRU = nil;        // terminate the list
                else
                        iterator->nextMRU = (CatalogIterator *) ( (Ptr)iterator + sizeof(CatalogIterator) );

                if ( i == 0 )
                        iterator->nextLRU = nil;        // terminate the list   
                else
                        iterator->nextLRU = (CatalogIterator *) ( (Ptr)iterator - sizeof(CatalogIterator) );

        #if TARGET_API_MACOS_X
                lockinit(&iterator->iterator_lock, PINOD, "hfs_catalog_iterator", 0, 0);
          #endif
        }
        
  #if TARGET_API_MAC_OS8
        (FSVarsRec*) LMGetFSMVars()->gCatalogCacheGlobals = (Ptr) cacheGlobals;
  #endif

  #if TARGET_API_MACOS_X
        gCatalogCacheGlobals = cacheGlobals;
        simple_lock_init(&cacheGlobals->simplelock);
  #endif
        
        return noErr;
}


//_______________________________________________________________________________
//      Routine:        InvalidateCatalogCache
//
//      Function:       Trash any interators matching volume parameter
//
//_______________________________________________________________________________
void PrintCatalogIterator( void );

void
InvalidateCatalogCache( ExtendedVCB *volume )
{
        TrashCatalogIterator( volume, 0 );
}


//_______________________________________________________________________________
//      Routine:        PrintCatalogIterator
//
//      Function:       Prints all interators
//
//_______________________________________________________________________________
#if HFS_DIAGNOSTIC
void
PrintCatalogIterator( void )
{
    CatalogIterator             *iterator;
    CatalogCacheGlobals *cacheGlobals = GetCatalogCacheGlobals();
        int                                     i;

    PRINTIT("CatalogCacheGlobals @ 0x%08lX are:\n", (unsigned long)cacheGlobals);
    PRINTIT("\titeratorCount: %ld \n", cacheGlobals->iteratorCount);
    PRINTIT("\tmru: 0x%08lX \n", (unsigned long)cacheGlobals->mru);
    PRINTIT("\tlru: 0x%08lX \n", (unsigned long)cacheGlobals->lru);

    for ( iterator = cacheGlobals->mru, i=0 ; iterator != nil && i<32  ; iterator = iterator->nextMRU, i++)
      {
        PRINTIT("%d: ", i);
        PRINTIT(" i: 0x%08lX", (unsigned long)iterator);
        PRINTIT(" M: 0x%08lX", (unsigned long)iterator->nextMRU);
        PRINTIT(" L: 0x%08lX", (unsigned long)iterator->nextLRU);
        PRINTIT("\n");
     }
}
#endif

//_______________________________________________________________________________
//      Routine:        TrashCatalogIterator
//
//      Function:       Trash any interators matching volume and folder parameters
//
//_______________________________________________________________________________
void
TrashCatalogIterator( const ExtendedVCB *volume, HFSCatalogNodeID folderID )
{
        CatalogIterator         *iterator;
        CatalogCacheGlobals     *cacheGlobals = GetCatalogCacheGlobals();

        CATALOG_ITER_LIST_LOCK(cacheGlobals);

        for ( iterator = cacheGlobals->mru ; iterator != nil ; iterator = iterator->nextMRU )
        {
                top:

                // first match the volume
                if ( iterator->volume != volume )
                        continue;

                // now match the folder (or all folders if 0)
                if ( (folderID == 0) || (folderID == iterator->folderID) )
                {
                        CatalogIterator *next;

                        iterator->volume = 0;   // trash it
                        iterator->folderID = 0;

                        next = iterator->nextMRU;       // remember the next iterator
                        
                        // if iterator is not already last then make it last
                        if ( next != nil )
                        {
                                InsertCatalogIteratorAsLRU( cacheGlobals, iterator );
                                
                                // iterator->nextMRU will always be zero (since we moved it to the end)
                                // so set up the next iterator manually (we know its not nil)
                                iterator = next;        
                                goto top;                       // process the next iterator
                        }
                }
        }

        CATALOG_ITER_LIST_UNLOCK(cacheGlobals);
}


//_______________________________________________________________________________
//      Routine:        AgeCatalogIterator
//
//      Function:       Move iterator to the end of the list...
//
//_______________________________________________________________________________
void
AgeCatalogIterator ( CatalogIterator *catalogIterator )
{
        CatalogCacheGlobals *   cacheGlobals = GetCatalogCacheGlobals();

        CATALOG_ITER_LIST_LOCK(cacheGlobals);

        //PRINTIT(" AgeCatalogIterator: v=%d, d=%ld, i=%d\n", catalogIterator->volRefNum, catalogIterator->folderID, catalogIterator->currentIndex);

        InsertCatalogIteratorAsLRU( cacheGlobals, catalogIterator );

        CATALOG_ITER_LIST_UNLOCK(cacheGlobals);
}


//_______________________________________________________________________________
//      Routine:        GetCatalogIterator
//
//      Function:       Release interest in Catalog iterator
//
//_______________________________________________________________________________
OSErr
ReleaseCatalogIterator( CatalogIterator* catalogIterator)
{
#if TARGET_API_MACOS_X
        //PRINTIT(" ReleaseCatalogIterator: v=%d, d=%ld, i=%d\n", catalogIterator->volRefNum, catalogIterator->folderID, catalogIterator->currentIndex);
        return CI_UNLOCK(catalogIterator);
#else
        return noErr;
#endif
}


//_______________________________________________________________________________
//      Routine:        GetCatalogIterator
//
//      Function:       Returns an iterator associated with the volume, folderID, index,
//                              and iterationType (kIterateFilesOnly or kIterateAll).
//                              Searches the cache in MRU order.
//                              Inserts the resulting iterator at the head of mru automatically
//
//      Note:           The returned iterator is locked and ReleaseCatalogIterator must
//                              be called to unlock it.
//
//_______________________________________________________________________________

CatalogIterator*
GetCatalogIterator(ExtendedVCB *volume, HFSCatalogNodeID folderID, UInt32 offset)
{
        CatalogCacheGlobals *cacheGlobals = GetCatalogCacheGlobals();
        CatalogIterator *iterator;
        CatalogIterator *bestIterator;

        bestIterator = NULL;

        CATALOG_ITER_LIST_LOCK(cacheGlobals);

        for (iterator = cacheGlobals->mru ; iterator != nil ; iterator = iterator->nextMRU) {

                /* first make sure volume and folder id match */
                if ((iterator->volume != volume) || (iterator->folderID != folderID)) {
                        continue;
                }

                /* ignore busy iterators */
                if ( CI_SLEEPLESS_LOCK(iterator) == EBUSY ) {
                        //PRINTIT(" GetCatalogIterator: busy v=%d, d=%ld, i=%d\n", volume, folderID, iterator->currentIndex);
                        continue;
                }

                /* we matched volume, folder id, now check the offset */
                if ( iterator->currentOffset == offset || iterator->nextOffset == offset) {
                        bestIterator = iterator;        // we scored! - so get out of this loop
                        break;                          // break with iterator locked
                }

                (void) CI_UNLOCK(iterator);     // unlock iterator before moving to the next one
        }

        // check if we didn't get one or if the one we got is too far away...
        if (bestIterator == NULL)
        {
                bestIterator = cacheGlobals->lru;                       // start over with a new iterator

                //PRINTIT(" GetCatalogIterator: recycle v=%d, d=%ld, i=%d\n", bestIterator->volume, bestIterator->folderID, bestIterator->currentIndex);
                (void) CI_LOCK_FROM_LIST(cacheGlobals, bestIterator);   // XXX we should not eat the error!
        
                CATALOG_ITER_LIST_LOCK(cacheGlobals);                   // grab the lock again for MRU Insert below...

                bestIterator->volume = volume;                  // update the iterator's volume
                bestIterator->folderID = folderID;                      // ... and folderID
                bestIterator->currentIndex = 0xFFFFFFFF;                        // ... and offspring index marker
                bestIterator->currentOffset = 0xFFFFFFFF;
                bestIterator->nextOffset = 0xFFFFFFFF;
                
                bestIterator->btreeNodeHint = 0;
                bestIterator->btreeIndexHint = 0;
                bestIterator->parentID = folderID;                      // set key to folderID + empty name
                bestIterator->folderName.unicodeName.length = 0;        // clear pascal/unicode name

                if ( volume->vcbSigWord == kHFSPlusSigWord )
                        bestIterator->nameType = kShortUnicodeName;
                else
                        bestIterator->nameType = kShortPascalName;
        }
        else {
                //PRINTIT(" GetCatalogIterator: found v=%d, d=%ld, i=%d\n", bestIterator->volume, bestIterator->folderID, bestIterator->currentIndex);
        }

        // put this iterator at the front of the list
        InsertCatalogIteratorAsMRU( cacheGlobals, bestIterator );

        CATALOG_ITER_LIST_UNLOCK(cacheGlobals);

        return bestIterator;    // return our best shot

} /* GetCatalogIterator */


//_______________________________________________________________________________
//      Routine:        UpdateBtreeIterator
//
//      Function:       Fills in a BTreeIterator from a CatalogIterator
//
//      Assumes:        catalogIterator->nameType is correctly initialized!
//                              catalogIterator is locked (MacOS X)
//_______________________________________________________________________________
void
UpdateBtreeIterator(const CatalogIterator *catalogIterator, BTreeIterator *btreeIterator)
{
        CatalogName *   nodeName;
        Boolean                 isHFSPlus;


        btreeIterator->hint.writeCount  = 0;
        btreeIterator->hint.nodeNum     = catalogIterator->btreeNodeHint;
        btreeIterator->hint.index               = catalogIterator->btreeIndexHint;

        switch (catalogIterator->nameType)
        {
                case kShortPascalName:
                        if ( catalogIterator->folderName.pascalName[0] > 0 )
                                nodeName  = (CatalogName *) catalogIterator->folderName.pascalName;
                        else
                                nodeName = NULL;

                        isHFSPlus = false;
                        break;

                case kShortUnicodeName:
                        if ( catalogIterator->folderName.unicodeName.length > 0 )
                                nodeName  = (CatalogName *) &catalogIterator->folderName.unicodeName;
                        else
                                nodeName = NULL;

                        isHFSPlus = true;
                        break;

                case kLongUnicodeName:
                        if ( catalogIterator->folderName.longNamePtr->length > 0 )
                                nodeName  = (CatalogName *) catalogIterator->folderName.longNamePtr;
                        else
                                nodeName = NULL;

                        isHFSPlus = true;
                        break;

                default:
                        return;
        }

        BuildCatalogKey(catalogIterator->parentID, nodeName, isHFSPlus, (CatalogKey*) &btreeIterator->key);
}


//_______________________________________________________________________________
//      Routine:        UpdateCatalogIterator
//
//      Function:       Updates a CatalogIterator from a BTreeIterator
//
//      Assumes:        catalogIterator->nameType is correctly initialized!
//                              catalogIterator is locked (MacOS X)
//_______________________________________________________________________________
void
UpdateCatalogIterator (const BTreeIterator *btreeIterator, CatalogIterator *catalogIterator)
{
        void *                  srcName;
        void *                  dstName;
        UInt16                  nameSize;
        CatalogKey *    catalogKey;


        catalogIterator->btreeNodeHint  = btreeIterator->hint.nodeNum;
        catalogIterator->btreeIndexHint = btreeIterator->hint.index;

        catalogKey = (CatalogKey*) &btreeIterator->key;

        switch (catalogIterator->nameType)
        {
                case kShortPascalName:
                        catalogIterator->parentID = catalogKey->hfs.parentID;

                        dstName  = catalogIterator->folderName.pascalName;
                        srcName  = catalogKey->hfs.nodeName;
                        nameSize = catalogKey->hfs.nodeName[0] + sizeof(UInt8);
                        break;

                case kShortUnicodeName:
                        catalogIterator->parentID = catalogKey->hfsPlus.parentID;

                        dstName  = &catalogIterator->folderName.unicodeName;
                        srcName  = &catalogKey->hfsPlus.nodeName;
                        nameSize = (catalogKey->hfsPlus.nodeName.length + 1) * sizeof(UInt16);

                        //      See if we need to make this iterator use long names
                        if ( nameSize > sizeof(catalogIterator->folderName.unicodeName) )
                        {
                                PrepareForLongName(catalogIterator);            //      Find a long name buffer to use
                                dstName  = catalogIterator->folderName.longNamePtr;
                        }
                        break;

                case kLongUnicodeName:
                        catalogIterator->parentID = catalogKey->hfsPlus.parentID;

                        dstName  = catalogIterator->folderName.longNamePtr;
                        srcName  = &catalogKey->hfsPlus.nodeName;
                        nameSize = (catalogKey->hfsPlus.nodeName.length + 1) * sizeof(UInt16);
                        break;

                default:
                        return;
        }

        if (catalogIterator->parentID != catalogIterator->folderID)
                catalogIterator->nextOffset = 0xFFFFFFFF;

        BlockMoveData(srcName, dstName, nameSize);

} // end UpdateCatalogIterator


//_______________________________________________________________________________
//      Routine:        InsertCatalogIteratorAsMRU
//
//      Function:       Moves catalog iterator to head of mru order in double linked list
//
//                              Assumes list simple lock is held
//_______________________________________________________________________________
static void
InsertCatalogIteratorAsMRU ( CatalogCacheGlobals *cacheGlobals, CatalogIterator *iterator )
{
        CatalogIterator *swapIterator;

        if ( cacheGlobals->mru != iterator )                                    //      if it's not already the mru iterator
        {
                swapIterator = cacheGlobals->mru;                                               //      put it in the front of the double queue
                cacheGlobals->mru = iterator;
                iterator->nextLRU->nextMRU = iterator->nextMRU;
                if ( iterator->nextMRU != nil )
                        iterator->nextMRU->nextLRU = iterator->nextLRU;
                else
                        cacheGlobals->lru= iterator->nextLRU;
                iterator->nextMRU       = swapIterator;
                iterator->nextLRU       = nil;
                swapIterator->nextLRU   = iterator;
        }
}


//________________________________________________________________________________
//      Routine:        InsertCatalogIteratorAsLRU
//
//      Function:       Moves catalog iterator to head of lru order in double linked list
//
//                              Assumes list simple lock is held
//_______________________________________________________________________________
static void
InsertCatalogIteratorAsLRU ( CatalogCacheGlobals *cacheGlobals, CatalogIterator *iterator )
{
        CatalogIterator *swapIterator;

        if ( cacheGlobals->lru != iterator )
        {
                swapIterator = cacheGlobals->lru;
                cacheGlobals->lru = iterator;
                iterator->nextMRU->nextLRU = iterator->nextLRU;
                if ( iterator->nextLRU != nil )
                        iterator->nextLRU->nextMRU = iterator->nextMRU;
                else
                        cacheGlobals->mru= iterator->nextMRU;
                iterator->nextLRU       = swapIterator;
                iterator->nextMRU       = nil;
                swapIterator->nextMRU   = iterator;
        }
}



//_______________________________________________________________________________
//      Routine:        PrepareForLongName
//
//      Function:       Takes a CatalogIterator whose nameType is kShortUnicodeName, and
//                              changes the nameType to kLongUnicodeName.
//
//  Since long Unicode names aren't stored in the CatalogIterator itself, we have
//      to point to an HFSUniStr255 for storage.  In the current implementation, we have
//      just one such global buffer in the cache globals.  We'll set the iterator to
//      point to the global buffer and invalidate the iterator that was using it
//      (i.e. the iterator whose nameType is kLongUnicodeName).
//
//      Eventually, we might want to have a list of long name buffers which we recycle
//      using an LRU algorithm.  Or perhaps, some other way....
//
//      Assumes:        catalogIterator is locked (MacOS X)
//_______________________________________________________________________________
static void
PrepareForLongName ( CatalogIterator *iterator )
{
        CatalogCacheGlobals     *cacheGlobals = GetCatalogCacheGlobals();
        CatalogIterator         *iter;
        
        if (DEBUG_BUILD && iterator->nameType != kShortUnicodeName)
                DebugStr("\p PrepareForLongName: nameType is wrong!");
        
        //
        //      Walk through all the iterators.  The first iterator whose nameType
        //      is kLongUnicodeName is invalidated (because it is using the global
        //      long name buffer).
        //
        
        CATALOG_ITER_LIST_LOCK(cacheGlobals);

        for ( iter = cacheGlobals->mru ; iter != nil ; iter = iter->nextMRU )
        {
                if (iter->nameType == kLongUnicodeName)
                {
                        // if iterator is not already last then make it last
                        if ( iter->nextMRU != nil )
                                InsertCatalogIteratorAsLRU( cacheGlobals, iter );
                        
                        (void) CI_LOCK_FROM_LIST(cacheGlobals,iter);
                        iter->volume = 0;       // trash it
                        iter->folderID = 0;
                        (void) CI_UNLOCK(iter);

            #if TARGET_API_MACOS_X
                        break;
                  #endif
                }
        }

        /*
         * if iter is nil then none of the iterators was using the LongUnicodeName buffer
         */
        if (iter == nil)
                CATALOG_ITER_LIST_UNLOCK(cacheGlobals);
        
        //
        //      Change the nameType of this iterator and point to the global
        //      long name buffer. Note - this iterator is already locked
        //
        iterator->nameType = kLongUnicodeName;
        iterator->folderName.longNamePtr = &cacheGlobals->longName;
}