bsd/hfs/hfscommon/Misc/BTreeWrapper.c

   1 /*
   2  * Copyright (c) 2000 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         File:           BTreeWrapper.c
  24
  25         Contains:       Interface glue for new B-tree manager.
  26
  27         Version:        HFS Plus 1.0
  28
  29         Copyright:      © 1996-1998 by Apple Computer, Inc., all rights reserved.
  30
  31         File Ownership:
  32
  33                 DRI:                            Don Brady
  34
  35                 Other Contact:          Mark Day
  36
  37                 Technology:                     xxx put technology here xxx
  38
  39         Writers:
  40
  41                 (msd)   Mark Day
  42                 (DSH)   Deric Horn
  43                 (djb)   Don Brady
  44
  45         Change History (most recent first):
  46           <MacOSX>       8/10/98        djb             Removed all references to btcb global iterator (lastIterator).
  47           <MacOSX>      04/02/98        djb             GetBTreeRecord is only used for MacOS builds.
  48           <MacOSX>      03/31/98        djb             Sync up with final HFSVolumes.h header file.
  49           <CS18>          9/4/97        msd             Fix ValidHFSRecord to determine the type of B-tree by FileID,
  50                                                                         not record size. Add better checking for attribute b-tree keys.
  51           <CS17>         8/22/97        djb             Get blockReadFromDisk flag from GetCacheBlock call.
  52           <CS16>         8/14/97        djb             Remove reserved field checks in ValidHFSRecord (radar #1649593).
  53                                                                         Only call if ValidHFSRecord HFS_DIAGNOSTIC is true.
  54           <CS15>         8/11/97        djb             Bug 1670441. In SetEndOfForkProc, don't DebugStr if the disk is
  55                                                                         full.
  56           <CS14>         7/25/97        DSH             Pass heuristicHint to BTSearchRecord from SearchBTreeRecord.
  57           <CS13>         7/24/97        djb             CallBackProcs now take a file refNum instead of an FCB.
  58                                                                         GetBlockProc now reports if block came from disk.
  59           <CS12>         7/22/97        djb             Move all trace points to BTree.c file.
  60           <CS11>         7/21/97        djb             LogEndTime now takes an error code.
  61           <CS10>         7/16/97        DSH             FilesInternal.x -> FileMgrInternal.x to avoid name collision
  62            <CS9>         7/15/97        msd             Bug #1664103.  OpenBTree is not propagating errors from
  63                                                                         BTOpenPath.
  64            <CS8>          7/9/97        djb             Remove maxCNID check from ValidHFSRecord (radar #1649593).
  65            <CS7>         6/13/97        djb             In ValidHFSRecord HFSPlus threads names can be > 31 chars.
  66            <CS6>          6/2/97        DSH             Also flush AlternateVolumeHeader whenever Attributes or Startup
  67                                                                         files change size.
  68            <CS5>         5/28/97        msd             In ValidHFSRecord, check for attribute keys.
  69            <CS4>         5/19/97        djb             Move summary traces from GetBTreeRecord to BTIterateRecord.
  70            <CS3>          5/9/97        djb             Get in sync with new FilesInternal.i.
  71            <CS2>          5/7/97        djb             Add summary traces to B-tree SPI.
  72            <CS1>         4/24/97        djb             first checked in
  73          <HFS18>         4/16/97        djb             Always use new B-tree code.
  74          <HFS17>          4/4/97        djb             Remove clumpSize test from ValidHFSRecord.
  75          <HFS16>          4/4/97        djb             Get in sync with volume format changes.
  76          <HFS15>         3/17/97        DSH             Casting for SC, BlockProcs are now not static.
  77          <HFS14>          3/3/97        djb             Call trash block after closing btree!
  78          <HFS13>         2/19/97        djb             Add support for accessing bigger B-tree nodes.
  79          <HFS12>          2/6/97        msd             In CheckBTreeKey, remove test and DebugStr for parent ID being
  80                                                                         too big.
  81          <HFS11>         1/23/97        DSH             SetEndOfForkProc now calls through to update the Alternate MDB
  82                                                                         or VolumeHeader.
  83          <HFS10>         1/16/97        djb             Switched to dynamic lengths for BufferDescriptor length field in
  84                                                                         SearchBTreeRecord and GetBTreeRecord. Round up to clump size in
  85                                                                         SetEndOfForkProc.
  86           <HFS9>         1/15/97        djb             Don't return errors for bad file ids in key.
  87           <HFS8>         1/13/97        djb             Adding support for getting current record. ValidHFSRecord now
  88                                                                         supports variable sized thread records.
  89           <HFS7>          1/9/97        djb             Call CheckBTreeKey before using key length in a BlockMoveData
  90                                                                         call.
  91           <HFS6>          1/6/97        djb             Implement SetEndOfForkProc.
  92           <HFS5>          1/6/97        djb             Added HFS Plus support to CheckBTreeKey and ValidHFSRecord.
  93           <HFS4>          1/3/97        djb             Added support for large keys. Integrated latest HFSVolumesPriv.h
  94                                                                         changes.
  95           <HFS3>        12/23/96        djb             Fixed problem in SearchBTreeRecord (dataSize is an output so it
  96                                                                         was undefined). Added some debugging code.
  97           <HFS2>        12/20/96        msd             Fix OpenBTree to use the real data type for the key compare proc
  98                                                                         pointer (not void *). Fixed problem in SearchBTreeRecord that
  99                                                                         assigns a pointer to a buffer size field (forgot to dereference
 100                                                                         the pointer).
 101           <HFS1>        12/19/96        djb             first checked in
 102
 103 */
 104
 105 #include "../headers/BTreesPrivate.h"
 106
 107
 108
 109
 110 // B-tree callbacks...
 111 #if TARGET_API_MAC_OS8
 112 OSStatus        GetBlockProc ( FileReference fileRefNum, UInt32 blockNum, GetBlockOptions options, BlockDescriptor *block );
 113 OSStatus        ReleaseBlockProc ( FileReference fileRefNum, BlockDescPtr blockPtr, ReleaseBlockOptions options );
 114 OSStatus        SetBlockSizeProc ( FileReference fileRefNum, ByteCount blockSize, ItemCount minBlockCount );
 115 #endif
 116
 117
 118 // local routines
 119 static OSErr    CheckBTreeKey(const BTreeKey *key, const BTreeControlBlock *btcb);
 120 static Boolean  ValidHFSRecord(const void *record, const BTreeControlBlock *btcb, UInt16 recordSize);
 121
 122
 123
 124
 125 OSErr SearchBTreeRecord(FileReference refNum, const void* key, UInt32 hint, void* foundKey, void* data, UInt16 *dataSize, UInt32 *newHint)
 126 {
 127         FSBufferDescriptor       btRecord;
 128         BTreeIterator            searchIterator;
 129         FCB                                     *fcb;
 130         BTreeControlBlock       *btcb;
 131         OSStatus                         result;
 132
 133
 134         fcb = GetFileControlBlock(refNum);
 135         btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr;
 136
 137         btRecord.bufferAddress = data;
 138         btRecord.itemCount = 1;
 139         if ( btcb->maxKeyLength == kHFSExtentKeyMaximumLength )
 140                 btRecord.itemSize = sizeof(HFSExtentRecord);
 141         else if ( btcb->maxKeyLength == kHFSPlusExtentKeyMaximumLength )
 142                 btRecord.itemSize = sizeof(HFSPlusExtentRecord);
 143         else
 144                 btRecord.itemSize = sizeof(CatalogRecord);
 145
 146         searchIterator.hint.writeCount = 0;     // clear these out for debugging...
 147         searchIterator.hint.reserved1 = 0;
 148         searchIterator.hint.reserved2 = 0;
 149
 150         searchIterator.hint.nodeNum = hint;
 151         searchIterator.hint.index = 0;
 152
 153         result = CheckBTreeKey((BTreeKey *) key, btcb);
 154         ExitOnError(result);
 155
 156         BlockMoveData(key, &searchIterator.key, CalcKeySize(btcb, (BTreeKey *) key));           //\80\80 should we range check against maxkeylen?
 157
 158         //      We only optimize for catalog records
 159         if( btRecord.itemSize == sizeof(CatalogRecord) )
 160         {
 161                 UInt32  heuristicHint;
 162                 UInt32  *cachedHint;
 163                 Ptr             hintCachePtr = FCBTOVCB(fcb)->hintCachePtr;
 164
 165                 //      We pass a 2nd hint/guess into BTSearchRecord.  The heuristicHint is a mapping of
 166                 //      dirID and nodeNumber, in hopes that the current search will be in the same node
 167                 //      as the last search with the same parentID.
 168                 result = GetMRUCacheBlock( ((HFSCatalogKey *)key)->parentID, hintCachePtr, (Ptr *)&cachedHint );
 169                 heuristicHint = (result == noErr) ? *cachedHint : kInvalidMRUCacheKey;
 170
 171                 result = BTSearchRecord( fcb, &searchIterator, heuristicHint, &btRecord, dataSize, &searchIterator );
 172
 173                 InsertMRUCacheBlock( hintCachePtr, ((HFSCatalogKey *)key)->parentID, (Ptr) &(searchIterator.hint.nodeNum) );
 174         }
 175         else
 176         {
 177                 result = BTSearchRecord( fcb, &searchIterator, kInvalidMRUCacheKey, &btRecord, dataSize, &searchIterator );
 178         }
 179
 180         if (result == noErr)
 181         {
 182                 *newHint = searchIterator.hint.nodeNum;
 183
 184                 result = CheckBTreeKey(&searchIterator.key, btcb);
 185                 ExitOnError(result);
 186
 187                 BlockMoveData(&searchIterator.key, foundKey, CalcKeySize(btcb, &searchIterator.key));   //\80\80 warning, this could overflow user's buffer!!!
 188
 189                 if ( DEBUG_BUILD && !ValidHFSRecord(data, btcb, *dataSize) )
 190                         DebugStr("\pSearchBTreeRecord: bad record?");
 191         }
 192
 193 ErrorExit:
 194
 195         return result;
 196 }
 197
 198
 199
 200 OSErr InsertBTreeRecord(FileReference refNum, void* key, void* data, UInt16 dataSize, UInt32 *newHint)
 201 {
 202         FSBufferDescriptor      btRecord;
 203         BTreeIterator           iterator;
 204         FCB                                     *fcb;
 205         BTreeControlBlock       *btcb;
 206         OSStatus                        result;
 207
 208
 209         fcb = GetFileControlBlock(refNum);
 210         btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr;
 211
 212         btRecord.bufferAddress = data;
 213         btRecord.itemSize = dataSize;
 214         btRecord.itemCount = 1;
 215
 216         iterator.hint.nodeNum = 0;                      // no hint
 217
 218         result = CheckBTreeKey((BTreeKey *) key, btcb);
 219         ExitOnError(result);
 220
 221         BlockMoveData(key, &iterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //\80\80 should we range check against maxkeylen?
 222
 223         if ( DEBUG_BUILD && !ValidHFSRecord(data, btcb, dataSize) )
 224                 DebugStr("\pInsertBTreeRecord: bad record?");
 225
 226         result = BTInsertRecord( fcb, &iterator, &btRecord, dataSize );
 227
 228         *newHint = iterator.hint.nodeNum;
 229
 230 ErrorExit:
 231
 232         return result;
 233 }
 234
 235
 236 OSErr DeleteBTreeRecord(FileReference refNum, void* key)
 237 {
 238         BTreeIterator           iterator;
 239         FCB                                     *fcb;
 240         BTreeControlBlock       *btcb;
 241         OSStatus                        result;
 242
 243
 244         fcb = GetFileControlBlock(refNum);
 245         btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr;
 246
 247         iterator.hint.nodeNum = 0;                      // no hint
 248
 249         result = CheckBTreeKey((BTreeKey *) key, btcb);
 250         ExitOnError(result);
 251
 252         BlockMoveData(key, &iterator.key, CalcKeySize(btcb, (BTreeKey *) key)); //\80\80 should we range check against maxkeylen?
 253
 254         result = BTDeleteRecord( fcb, &iterator );
 255
 256 ErrorExit:
 257
 258         return result;
 259 }
 260
 261
 262 OSErr ReplaceBTreeRecord(FileReference refNum, const void* key, UInt32 hint, void *newData, UInt16 dataSize, UInt32 *newHint)
 263 {
 264         FSBufferDescriptor      btRecord;
 265         BTreeIterator           iterator;
 266         FCB                                     *fcb;
 267         BTreeControlBlock       *btcb;
 268         OSStatus                        result;
 269
 270
 271         fcb = GetFileControlBlock(refNum);
 272         btcb = (BTreeControlBlock*) fcb->fcbBTCBPtr;
 273
 274         btRecord.bufferAddress = newData;
 275         btRecord.itemSize = dataSize;
 276         btRecord.itemCount = 1;
 277
 278         iterator.hint.nodeNum = hint;
 279
 280         result = CheckBTreeKey((BTreeKey *) key, btcb);
 281         ExitOnError(result);
 282
 283         BlockMoveData(key, &iterator.key, CalcKeySize(btcb, (BTreeKey *) key));         //\80\80 should we range check against maxkeylen?
 284
 285         if ( DEBUG_BUILD && !ValidHFSRecord(newData, btcb, dataSize) )
 286                 DebugStr("\pReplaceBTreeRecord: bad record?");
 287
 288         result = BTReplaceRecord( fcb, &iterator, &btRecord, dataSize );
 289
 290         *newHint = iterator.hint.nodeNum;
 291
 292         //\80\80 do we need to invalidate the iterator?
 293
 294 ErrorExit:
 295
 296         return result;
 297 }
 298
 299
 300
 301 static OSErr CheckBTreeKey(const BTreeKey *key, const BTreeControlBlock *btcb)
 302 {
 303         UInt16  keyLen;
 304
 305         if ( btcb->attributes & kBTBigKeysMask )
 306                 keyLen = key->length16;
 307         else
 308                 keyLen = key->length8;
 309
 310         if ( (keyLen < 6) || (keyLen > btcb->maxKeyLength) )
 311         {
 312                 if ( DEBUG_BUILD )
 313                         DebugStr("\pCheckBTreeKey: bad key length!");
 314                 return fsBTInvalidKeyLengthErr;
 315         }
 316
 317         return noErr;
 318 }
 319
 320
 321 static Boolean ValidHFSRecord(const void *record, const BTreeControlBlock *btcb, UInt16 recordSize)
 322 {
 323         UInt32                  cNodeID;
 324
 325         if ( btcb->maxKeyLength == kHFSExtentKeyMaximumLength )
 326         {
 327                 return ( recordSize == sizeof(HFSExtentRecord) );
 328         }
 329         else if (btcb->maxKeyLength == kHFSPlusExtentKeyMaximumLength )
 330         {
 331                 return ( recordSize == sizeof(HFSPlusExtentRecord) );
 332         }
 333         else // Catalog record
 334         {
 335                 CatalogRecord *catalogRecord = (CatalogRecord*) record;
 336
 337                 switch(catalogRecord->recordType)
 338                 {
 339                         case kHFSFolderRecord:
 340                         {
 341                                 if ( recordSize != sizeof(HFSCatalogFolder) )
 342                                         return false;
 343                                 if ( catalogRecord->hfsFolder.flags != 0 )
 344                                         return false;
 345                                 if ( catalogRecord->hfsFolder.valence > 0x7FFF )
 346                                         return false;
 347
 348                                 cNodeID = catalogRecord->hfsFolder.folderID;
 349
 350                                 if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) )
 351                                         return false;
 352                         }
 353                         break;
 354
 355                         case kHFSPlusFolderRecord:
 356                         {
 357                                 if ( recordSize != sizeof(HFSPlusCatalogFolder) )
 358                                         return false;
 359                                 if ( catalogRecord->hfsPlusFolder.flags != 0 )
 360                                         return false;
 361                                 if ( catalogRecord->hfsPlusFolder.valence > 0x7FFF )
 362                                         return false;
 363
 364                                 cNodeID = catalogRecord->hfsPlusFolder.folderID;
 365
 366                                 if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) )
 367                                         return false;
 368                         }
 369                         break;
 370
 371                         case kHFSFileRecord:
 372                         {
 373 //                              UInt16                                  i;
 374                                 HFSExtentDescriptor     *dataExtent;
 375                                 HFSExtentDescriptor     *rsrcExtent;
 376
 377                                 if ( recordSize != sizeof(HFSCatalogFile) )
 378                                         return false;
 379                                 if ( (catalogRecord->hfsFile.flags & ~(0x83)) != 0 )
 380                                         return false;
 381
 382                                 cNodeID = catalogRecord->hfsFile.fileID;
 383
 384                                 if ( cNodeID < 16 )
 385                                         return false;
 386
 387                                 // make sure 0 ¾ LEOF ¾ PEOF for both forks
 388
 389                                 if ( catalogRecord->hfsFile.dataLogicalSize < 0 )
 390                                         return false;
 391                                 if ( catalogRecord->hfsFile.dataPhysicalSize < catalogRecord->hfsFile.dataLogicalSize )
 392                                         return false;
 393                                 if ( catalogRecord->hfsFile.rsrcLogicalSize < 0 )
 394                                         return false;
 395                                 if ( catalogRecord->hfsFile.rsrcPhysicalSize < catalogRecord->hfsFile.rsrcLogicalSize )
 396                                         return false;
 397
 398                                 dataExtent = (HFSExtentDescriptor*) &catalogRecord->hfsFile.dataExtents;
 399                                 rsrcExtent = (HFSExtentDescriptor*) &catalogRecord->hfsFile.rsrcExtents;
 400
 401 #if 0
 402                                 for (i = 0; i < kHFSExtentDensity; ++i)
 403                                 {
 404                                         if ( (dataExtent[i].blockCount > 0) && (dataExtent[i].startBlock == 0) )
 405                                                 return false;
 406                                         if ( (rsrcExtent[i].blockCount > 0) && (rsrcExtent[i].startBlock == 0) )
 407                                                 return false;
 408                                 }
 409 #endif
 410                         }
 411                         break;
 412
 413                         case kHFSPlusFileRecord:
 414                         {
 415 //                              UInt16                                  i;
 416                                 HFSPlusExtentDescriptor *dataExtent;
 417                                 HFSPlusExtentDescriptor *rsrcExtent;
 418
 419                                 if ( recordSize != sizeof(HFSPlusCatalogFile) )
 420                                         return false;
 421                                 if ( (catalogRecord->hfsPlusFile.flags & ~(0x83)) != 0 )
 422                                         return false;
 423
 424                                 cNodeID = catalogRecord->hfsPlusFile.fileID;
 425
 426                                 if ( cNodeID < 16 )
 427                                         return false;
 428
 429                                 // make sure 0 ¾ LEOF ¾ PEOF for both forks
 430
 431                                 dataExtent = (HFSPlusExtentDescriptor*) &catalogRecord->hfsPlusFile.dataFork.extents;
 432                                 rsrcExtent = (HFSPlusExtentDescriptor*) &catalogRecord->hfsPlusFile.resourceFork.extents;
 433
 434 #if 0
 435                                 for (i = 0; i < kHFSPlusExtentDensity; ++i)
 436                                 {
 437                                         if ( (dataExtent[i].blockCount > 0) && (dataExtent[i].startBlock == 0) )
 438                                                 return false;
 439                                         if ( (rsrcExtent[i].blockCount > 0) && (rsrcExtent[i].startBlock == 0) )
 440                                                 return false;
 441                                 }
 442 #endif
 443                         }
 444                         break;
 445
 446                         case kHFSFolderThreadRecord:
 447                         case kHFSFileThreadRecord:
 448                         {
 449                                 if ( recordSize != sizeof(HFSCatalogThread) )
 450                                         return false;
 451
 452                                 cNodeID = catalogRecord->hfsThread.parentID;
 453                                 if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) )
 454                                         return false;
 455
 456                                 if ( (catalogRecord->hfsThread.nodeName[0] == 0) ||
 457                                          (catalogRecord->hfsThread.nodeName[0] > 31) )
 458                                         return false;
 459                         }
 460                         break;
 461
 462                         case kHFSPlusFolderThreadRecord:
 463                         case kHFSPlusFileThreadRecord:
 464                         {
 465                                 if ( recordSize > sizeof(HFSPlusCatalogThread) || recordSize < (sizeof(HFSPlusCatalogThread) - sizeof(HFSUniStr255)))
 466                                         return false;
 467
 468                                 cNodeID = catalogRecord->hfsPlusThread.parentID;
 469                                 if ( (cNodeID == 0) || (cNodeID < 16 && cNodeID > 2) )
 470                                         return false;
 471
 472                                 if ( (catalogRecord->hfsPlusThread.nodeName.length == 0) ||
 473                                          (catalogRecord->hfsPlusThread.nodeName.length > 255) )
 474                                         return false;
 475                         }
 476                         break;
 477
 478                         default:
 479                                 return false;
 480                 }
 481         }
 482
 483         return true;    // record appears to be OK
 484 }