/* * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. * * @APPLE_LICENSE_HEADER_START@ * * The contents of this file constitute Original Code as defined in and * are subject to the Apple Public Source License Version 1.1 (the * "License"). You may not use this file except in compliance with the * License. Please obtain a copy of the License at * http://www.apple.com/publicsource and read it before using this file. * * This 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 OR NON-INFRINGEMENT. Please see the * License for the specific language governing rights and limitations * under the License. * * @APPLE_LICENSE_HEADER_END@ */ /* File: BTreeWrapper.c Contains: Interface glue for new B-tree manager. Version: HFS Plus 1.0 Copyright: © 1996-1998 by Apple Computer, Inc., all rights reserved. File Ownership: DRI: Don Brady Other Contact: Mark Day Technology: xxx put technology here xxx Writers: (msd) Mark Day (DSH) Deric Horn (djb) Don Brady Change History (most recent first): 8/10/98 djb Removed all references to btcb global iterator (lastIterator). 04/02/98 djb GetBTreeRecord is only used for MacOS builds. 03/31/98 djb Sync up with final HFSVolumes.h header file. 9/4/97 msd Fix ValidHFSRecord to determine the type of B-tree by FileID, not record size. Add better checking for attribute b-tree keys. 8/22/97 djb Get blockReadFromDisk flag from GetCacheBlock call. 8/14/97 djb Remove reserved field checks in ValidHFSRecord (radar #1649593). Only call if ValidHFSRecord HFS_DIAGNOSTIC is true. 8/11/97 djb Bug 1670441. In SetEndOfForkProc, don't DebugStr if the disk is full. 7/25/97 DSH Pass heuristicHint to BTSearchRecord from SearchBTreeRecord. 7/24/97 djb CallBackProcs now take a file refNum instead of an FCB. GetBlockProc now reports if block came from disk. 7/22/97 djb Move all trace points to BTree.c file. 7/21/97 djb LogEndTime now takes an error code. 7/16/97 DSH FilesInternal.x -> FileMgrInternal.x to avoid name collision 7/15/97 msd Bug #1664103. OpenBTree is not propagating errors from BTOpenPath. 7/9/97 djb Remove maxCNID check from ValidHFSRecord (radar #1649593). 6/13/97 djb In ValidHFSRecord HFSPlus threads names can be > 31 chars. 6/2/97 DSH Also flush AlternateVolumeHeader whenever Attributes or Startup files change size. 5/28/97 msd In ValidHFSRecord, check for attribute keys. 5/19/97 djb Move summary traces from GetBTreeRecord to BTIterateRecord. 5/9/97 djb Get in sync with new FilesInternal.i. 5/7/97 djb Add summary traces to B-tree SPI. 4/24/97 djb first checked in 4/16/97 djb Always use new B-tree code. 4/4/97 djb Remove clumpSize test from ValidHFSRecord. 4/4/97 djb Get in sync with volume format changes. 3/17/97 DSH Casting for SC, BlockProcs are now not static. 3/3/97 djb Call trash block after closing btree! 2/19/97 djb Add support for accessing bigger B-tree nodes. 2/6/97 msd In CheckBTreeKey, remove test and DebugStr for parent ID being too big. 1/23/97 DSH SetEndOfForkProc now calls through to update the Alternate MDB or VolumeHeader. 1/16/97 djb Switched to dynamic lengths for BufferDescriptor length field in SearchBTreeRecord and GetBTreeRecord. Round up to clump size in SetEndOfForkProc. 1/15/97 djb Don't return errors for bad file ids in key. 1/13/97 djb Adding support for getting current record. ValidHFSRecord now supports variable sized thread records. 1/9/97 djb Call CheckBTreeKey before using key length in a BlockMoveData call. 1/6/97 djb Implement SetEndOfForkProc. 1/6/97 djb Added HFS Plus support to CheckBTreeKey and ValidHFSRecord. 1/3/97 djb Added support for large keys. Integrated latest HFSVolumesPriv.h changes. 12/23/96 djb Fixed problem in SearchBTreeRecord (dataSize is an output so it was undefined). Added some debugging code. 12/20/96 msd Fix OpenBTree to use the real data type for the key compare proc pointer (not void *). Fixed problem in SearchBTreeRecord that assigns a pointer to a buffer size field (forgot to dereference the pointer). 12/19/96 djb first checked in */ #include "../headers/BTreesPrivate.h" // B-tree callbacks... #if TARGET_API_MAC_OS8 OSStatus GetBlockProc ( FileReference fileRefNum, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block ); OSStatus ReleaseBlockProc ( FileReference fileRefNum, BlockDescPtr blockPtr, ReleaseBlockOptions options ); OSStatus SetBlockSizeProc ( FileReference fileRefNum, ByteCount blockSize, ItemCount minBlockCount ); #endif // local routines static OSErr CheckBTreeKey(const BTreeKey *key, const BTreeControlBlock *btcb); static Boolean ValidHFSRecord(const void *record, const BTreeControlBlock *btcb, UInt16 recordSize); OSErr SearchBTreeRecord(FileReference refNum, const void* key, UInt32 hint, void* foundKey, void* data, UInt16 *dataSize, UInt32 *newHint) { FSBufferDescriptor btRecord; BTreeIterator searchIterator; FCB *fcb; BTreeControlBlock *btcb; OSStatus result; fcb = GetFileControlBlock(refNum); btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr; btRecord.bufferAddress = data; btRecord.itemCount = 1; if ( btcb->maxKeyLength == kHFSExtentKeyMaximumLength ) btRecord.itemSize = sizeof(HFSExtentRecord); else if ( btcb->maxKeyLength == kHFSPlusExtentKeyMaximumLength ) btRecord.itemSize = sizeof(HFSPlusExtentRecord); else btRecord.itemSize = sizeof(CatalogRecord); searchIterator.hint.writeCount = 0; // clear these out for debugging... searchIterator.hint.reserved1 = 0; searchIterator.hint.reserved2 = 0; searchIterator.hint.nodeNum = hint; searchIterator.hint.index = 0; result = CheckBTreeKey((BTreeKey *) key, btcb); ExitOnError(result); BlockMoveData(key, &searchIterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //€€ should we range check against maxkeylen? // We only optimize for catalog records if( btRecord.itemSize == sizeof(CatalogRecord) ) { UInt32 heuristicHint; UInt32 *cachedHint; Ptr hintCachePtr = FCBTOVCB(fcb)->hintCachePtr; // We pass a 2nd hint/guess into BTSearchRecord. The heuristicHint is a mapping of // dirID and nodeNumber, in hopes that the current search will be in the same node // as the last search with the same parentID. result = GetMRUCacheBlock( ((HFSCatalogKey *)key)->parentID, hintCachePtr, (Ptr *)&cachedHint ); heuristicHint = (result == noErr) ? *cachedHint : kInvalidMRUCacheKey; result = BTSearchRecord( fcb, &searchIterator, heuristicHint, &btRecord, dataSize, &searchIterator ); InsertMRUCacheBlock( hintCachePtr, ((HFSCatalogKey *)key)->parentID, (Ptr) &(searchIterator.hint.nodeNum) ); } else { result = BTSearchRecord( fcb, &searchIterator, kInvalidMRUCacheKey, &btRecord, dataSize, &searchIterator ); } if (result == noErr) { *newHint = searchIterator.hint.nodeNum; result = CheckBTreeKey(&searchIterator.key, btcb); ExitOnError(result); BlockMoveData(&searchIterator.key, foundKey, CalcKeySize(btcb, &searchIterator.key)); //€€ warning, this could overflow user's buffer!!! if ( DEBUG_BUILD && !ValidHFSRecord(data, btcb, *dataSize) ) DebugStr("\pSearchBTreeRecord: bad record?"); } ErrorExit: return result; } OSErr InsertBTreeRecord(FileReference refNum, void* key, void* data, UInt16 dataSize, UInt32 *newHint) { FSBufferDescriptor btRecord; BTreeIterator iterator; FCB *fcb; BTreeControlBlock *btcb; OSStatus result; fcb = GetFileControlBlock(refNum); btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr; btRecord.bufferAddress = data; btRecord.itemSize = dataSize; btRecord.itemCount = 1; iterator.hint.nodeNum = 0; // no hint result = CheckBTreeKey((BTreeKey *) key, btcb); ExitOnError(result); BlockMoveData(key, &iterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //€€ should we range check against maxkeylen? if ( DEBUG_BUILD && !ValidHFSRecord(data, btcb, dataSize) ) DebugStr("\pInsertBTreeRecord: bad record?"); result = BTInsertRecord( fcb, &iterator, &btRecord, dataSize ); *newHint = iterator.hint.nodeNum; ErrorExit: return result; } OSErr DeleteBTreeRecord(FileReference refNum, void* key) { BTreeIterator iterator; FCB *fcb; BTreeControlBlock *btcb; OSStatus result; fcb = GetFileControlBlock(refNum); btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr; iterator.hint.nodeNum = 0; // no hint result = CheckBTreeKey((BTreeKey *) key, btcb); ExitOnError(result); BlockMoveData(key, &iterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //€€ should we range check against maxkeylen? result = BTDeleteRecord( fcb, &iterator ); ErrorExit: return result; } OSErr ReplaceBTreeRecord(FileReference refNum, const void* key, UInt32 hint, void *newData, UInt16 dataSize, UInt32 *newHint) { FSBufferDescriptor btRecord; BTreeIterator iterator; FCB *fcb; BTreeControlBlock *btcb; OSStatus result; fcb = GetFileControlBlock(refNum); btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr; btRecord.bufferAddress = newData; btRecord.itemSize = dataSize; btRecord.itemCount = 1; iterator.hint.nodeNum = hint; result = CheckBTreeKey((BTreeKey *) key, btcb); ExitOnError(result); BlockMoveData(key, &iterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //€€ should we range check against maxkeylen? if ( DEBUG_BUILD && !ValidHFSRecord(newData, btcb, dataSize) ) DebugStr("\pReplaceBTreeRecord: bad record?"); result = BTReplaceRecord( fcb, &iterator, &btRecord, dataSize ); *newHint = iterator.hint.nodeNum; //€€ do we need to invalidate the iterator? ErrorExit: return result; } static OSErr CheckBTreeKey(const BTreeKey *key, const BTreeControlBlock *btcb) { UInt16 keyLen; if ( btcb->attributes & kBTBigKeysMask ) keyLen = key->length16; else keyLen = key->length8; if ( (keyLen < 6) || (keyLen > btcb->maxKeyLength) ) { if ( DEBUG_BUILD ) DebugStr("\pCheckBTreeKey: bad key length!"); return fsBTInvalidKeyLengthErr; } return noErr; } static Boolean ValidHFSRecord(const void *record, const BTreeControlBlock *btcb, UInt16 recordSize) { UInt32 cNodeID; if ( btcb->maxKeyLength == kHFSExtentKeyMaximumLength ) { return ( recordSize == sizeof(HFSExtentRecord) ); } else if (btcb->maxKeyLength == kHFSPlusExtentKeyMaximumLength ) { return ( recordSize == sizeof(HFSPlusExtentRecord) ); } else // Catalog record { CatalogRecord *catalogRecord = (CatalogRecord*) record; switch(catalogRecord->recordType) { case kHFSFolderRecord: { if ( recordSize != sizeof(HFSCatalogFolder) ) return false; if ( catalogRecord->hfsFolder.flags != 0 ) return false; if ( catalogRecord->hfsFolder.valence > 0x7FFF ) return false; cNodeID = catalogRecord->hfsFolder.folderID; if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) ) return false; } break; case kHFSPlusFolderRecord: { if ( recordSize != sizeof(HFSPlusCatalogFolder) ) return false; if ( catalogRecord->hfsPlusFolder.flags != 0 ) return false; if ( catalogRecord->hfsPlusFolder.valence > 0x7FFF ) return false; cNodeID = catalogRecord->hfsPlusFolder.folderID; if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) ) return false; } break; case kHFSFileRecord: { // UInt16 i; HFSExtentDescriptor *dataExtent; HFSExtentDescriptor *rsrcExtent; if ( recordSize != sizeof(HFSCatalogFile) ) return false; if ( (catalogRecord->hfsFile.flags & ~(0x83)) != 0 ) return false; cNodeID = catalogRecord->hfsFile.fileID; if ( cNodeID < 16 ) return false; // make sure 0 ¾ LEOF ¾ PEOF for both forks if ( catalogRecord->hfsFile.dataLogicalSize < 0 ) return false; if ( catalogRecord->hfsFile.dataPhysicalSize < catalogRecord->hfsFile.dataLogicalSize ) return false; if ( catalogRecord->hfsFile.rsrcLogicalSize < 0 ) return false; if ( catalogRecord->hfsFile.rsrcPhysicalSize < catalogRecord->hfsFile.rsrcLogicalSize ) return false; dataExtent = (HFSExtentDescriptor*) &catalogRecord->hfsFile.dataExtents; rsrcExtent = (HFSExtentDescriptor*) &catalogRecord->hfsFile.rsrcExtents; #if 0 for (i = 0; i < kHFSExtentDensity; ++i) { if ( (dataExtent[i].blockCount > 0) && (dataExtent[i].startBlock == 0) ) return false; if ( (rsrcExtent[i].blockCount > 0) && (rsrcExtent[i].startBlock == 0) ) return false; } #endif } break; case kHFSPlusFileRecord: { // UInt16 i; HFSPlusExtentDescriptor *dataExtent; HFSPlusExtentDescriptor *rsrcExtent; if ( recordSize != sizeof(HFSPlusCatalogFile) ) return false; if ( (catalogRecord->hfsPlusFile.flags & ~(0x83)) != 0 ) return false; cNodeID = catalogRecord->hfsPlusFile.fileID; if ( cNodeID < 16 ) return false; // make sure 0 ¾ LEOF ¾ PEOF for both forks dataExtent = (HFSPlusExtentDescriptor*) &catalogRecord->hfsPlusFile.dataFork.extents; rsrcExtent = (HFSPlusExtentDescriptor*) &catalogRecord->hfsPlusFile.resourceFork.extents; #if 0 for (i = 0; i < kHFSPlusExtentDensity; ++i) { if ( (dataExtent[i].blockCount > 0) && (dataExtent[i].startBlock == 0) ) return false; if ( (rsrcExtent[i].blockCount > 0) && (rsrcExtent[i].startBlock == 0) ) return false; } #endif } break; case kHFSFolderThreadRecord: case kHFSFileThreadRecord: { if ( recordSize != sizeof(HFSCatalogThread) ) return false; cNodeID = catalogRecord->hfsThread.parentID; if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) ) return false; if ( (catalogRecord->hfsThread.nodeName[0] == 0) || (catalogRecord->hfsThread.nodeName[0] > 31) ) return false; } break; case kHFSPlusFolderThreadRecord: case kHFSPlusFileThreadRecord: { if ( recordSize > sizeof(HFSPlusCatalogThread) || recordSize < (sizeof(HFSPlusCatalogThread) - sizeof(HFSUniStr255))) return false; cNodeID = catalogRecord->hfsPlusThread.parentID; if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) ) return false; if ( (catalogRecord->hfsPlusThread.nodeName.length == 0) || (catalogRecord->hfsPlusThread.nodeName.length > 255) ) return false; } break; default: return false; } } return true; // record appears to be OK }