1/* 2 * Copyright (c) 1996-2002, 2005, 2012 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 * 23 * @(#)BTreeScanner.c 24 */ 25 26 27#include "BTreeScanner.h" 28#include "Scavenger.h" 29#include "../cache.h" 30#include "../fsck_hfs.h" 31 32static int FindNextLeafNode( BTScanState *scanState ); 33static int ReadMultipleNodes( BTScanState *scanState ); 34 35 36//_________________________________________________________________________________ 37// 38// Routine: BTScanNextRecord 39// 40// Purpose: Return the next leaf record in a scan. 41// 42// Inputs: 43// scanState Scanner's current state 44// 45// Outputs: 46// key Key of found record (points into buffer) 47// data Data of found record (points into buffer) 48// dataSize Size of data in found record 49// 50// Result: 51// noErr Found a valid record 52// btNotFound No more records 53// 54// Notes: 55// This routine returns pointers to the found record's key and data. It 56// does not copy the key or data to a caller-supplied buffer (like 57// GetBTreeRecord would). The caller must not modify the key or data. 58//_________________________________________________________________________________ 59 60int BTScanNextRecord( BTScanState * scanState, 61 void * * key, 62 void * * data, 63 u_int32_t * dataSize ) 64{ 65 int err; 66 u_int16_t dataSizeShort; 67 int64_t maxLeafRecs; 68 69 err = noErr; 70 71 // 72 // If this is the first call, there won't be any nodes in the buffer, so go 73 // find the first first leaf node (if any). 74 // 75 if ( scanState->nodesLeftInBuffer <= 0 ) 76 err = FindNextLeafNode( scanState ); 77 78 // btcb->leafRecords may be fragile (the B-Tree header could be damaged) 79 // so in order to do a sanity check on the max number of leaf records we 80 // could have we use the catalog file's physical size divided by the smallest 81 // leaf node record size to get our ceiling. 82 maxLeafRecs = scanState->btcb->fcbPtr->fcbPhysicalSize / sizeof( HFSCatalogThread ); 83 84 while ( err == noErr ) 85 { 86 // See if we have a record in the current node 87 err = GetRecordByIndex( scanState->btcb, scanState->currentNodePtr, 88 scanState->recordNum, (KeyPtr *) key, 89 (UInt8 **) data, &dataSizeShort ); 90 if ( err == noErr ) 91 { 92 ++scanState->recordsFound; 93 ++scanState->recordNum; 94 if (dataSize != NULL) 95 *dataSize = dataSizeShort; 96 return noErr; 97 } 98 99 // We're done with the current node. See if we've returned all the records 100 if ( scanState->recordsFound >= maxLeafRecs ) 101 return btNotFound; 102 103 // Move to the first record of the next leaf node 104 scanState->recordNum = 0; 105 err = FindNextLeafNode( scanState ); 106 } 107 108 // 109 // If we got an EOF error from FindNextLeafNode, then there are no more leaf 110 // records to be found. 111 // 112 if ( err == fsEndOfIterationErr ) 113 err = btNotFound; 114 115 return err; 116 117} /* BTScanNextRecord */ 118 119 120//_________________________________________________________________________________ 121// 122// Routine: FindNextLeafNode 123// 124// Purpose: Point to the next leaf node in the buffer. Read more nodes 125// into the buffer if needed (and allowed). 126// 127// Inputs: 128// scanState Scanner's current state 129// 130// Result: 131// noErr Found a valid record 132// fsEndOfIterationErr No more nodes in file 133//_________________________________________________________________________________ 134 135static int FindNextLeafNode( BTScanState *scanState ) 136{ 137 int err; 138 BlockDescriptor myBlockDescriptor; 139 140 err = noErr; // Assume everything will be OK 141 142 while ( 1 ) 143 { 144 ++scanState->nodeNum; 145 --scanState->nodesLeftInBuffer; 146 if ( scanState->nodesLeftInBuffer <= 0 ) 147 { 148 // read some more nodes into buffer 149 err = ReadMultipleNodes( scanState ); 150 if ( err != noErr ) 151 break; 152 } 153 else 154 { 155 // Adjust to point to the next node in the buffer 156 157 // If we've looked at all nodes in the tree, then we're done 158 if ( scanState->nodeNum >= scanState->btcb->totalNodes ) 159 return fsEndOfIterationErr; 160 161 scanState->currentNodePtr = (BTNodeDescriptor *)((UInt8 *)scanState->currentNodePtr + scanState->btcb->nodeSize); 162 } 163 164 // need to manufacture a BlockDescriptor since hfs_swap_BTNode expects one as input 165 myBlockDescriptor.buffer = (void *) scanState->currentNodePtr; 166 myBlockDescriptor.blockHeader = NULL; 167 myBlockDescriptor.blockNum = scanState->nodeNum; 168 myBlockDescriptor.blockSize = scanState->btcb->nodeSize; 169 myBlockDescriptor.blockReadFromDisk = false; 170 myBlockDescriptor.fragmented = false; 171 err = hfs_swap_BTNode(&myBlockDescriptor, scanState->btcb->fcbPtr, kSwapBTNodeBigToHost); 172 if ( err != noErr ) 173 { 174 err = noErr; 175 continue; 176 } 177 178 // NOTE - todo - add less lame sanity check to allow leaf nodes that 179 // only have damaged kind. 180 if ( scanState->currentNodePtr->kind == kBTLeafNode ) 181 break; 182 } 183 184 return err; 185 186} /* FindNextLeafNode */ 187 188 189//_________________________________________________________________________________ 190// 191// Routine: ReadMultipleNodes 192// 193// Purpose: Read one or more nodes into the buffer. 194// 195// Inputs: 196// theScanStatePtr Scanner's current state 197// 198// Result: 199// noErr One or nodes were read 200// fsEndOfIterationErr No nodes left in file, none in buffer 201//_________________________________________________________________________________ 202 203int CacheRawRead (Cache_t *cache, uint64_t off, uint32_t len, void *buf); 204 205static int ReadMultipleNodes( BTScanState *theScanStatePtr ) 206{ 207 int myErr = noErr; 208 BTreeControlBlockPtr myBTreeCBPtr; 209 UInt64 myPhyBlockNum; 210 SInt64 myPhyOffset; 211 UInt64 mySectorOffset; // offset within file (in 512-byte sectors) 212 UInt32 myContiguousBytes; 213 214 myBTreeCBPtr = theScanStatePtr->btcb; 215 216 // map logical block in catalog btree file to physical block on volume 217 mySectorOffset = 218 (((UInt64)theScanStatePtr->nodeNum * (UInt64)myBTreeCBPtr->fcbPtr->fcbBlockSize) >> kSectorShift); 219 myErr = MapFileBlockC( myBTreeCBPtr->fcbPtr->fcbVolume, myBTreeCBPtr->fcbPtr, 220 theScanStatePtr->bufferSize, mySectorOffset, 221 &myPhyBlockNum, &myContiguousBytes ); 222 if ( myErr != noErr ) 223 { 224 myErr = fsEndOfIterationErr; 225 goto ExitThisRoutine; 226 } 227 228 // now read blocks from the device 229 myPhyOffset = (SInt64) ( ( (UInt64) myPhyBlockNum ) << kSectorShift ); 230 231 // Go through the cache, so we can get any locked-in journal changes 232 Buf_t *tmpbuf = NULL; 233 234 myErr = CacheRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache, 235 myPhyOffset, myContiguousBytes, &tmpbuf ); 236 237 if ( myErr == noErr ) 238 { 239 if (tmpbuf) 240 { 241 if (tmpbuf->Length < myContiguousBytes) 242 abort(); 243 memcpy(theScanStatePtr->bufferPtr, tmpbuf->Buffer, myContiguousBytes); 244 CacheRelease(myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache, tmpbuf, 0); 245 } else 246 abort(); 247#if DEBUG_BTREE 248 /* 249 * This code was written to help debug a cache problem, where CacheRead() 250 * was returning different results than CacheRawRead(). I am leaving it 251 * around because I fear that will happen again, so it can be used for 252 * reference, rather than rewrite it then. 253 */ 254 size_t tempBufferSize = myContiguousBytes; 255 int tempError; 256 unsigned char *tempBuffer = malloc(myContiguousBytes); 257 if (tempBuffer == NULL) 258 abort(); 259 tempError = CacheRawRead( myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache, 260 myPhyOffset, myContiguousBytes, tempBuffer); 261 if (memcmp(tempBuffer, theScanStatePtr->bufferPtr, myContiguousBytes) != 0) 262 { 263 uint8_t *raw, *cached; 264 fprintf(stderr, "CacheRead and CacheRawRead returned different values\n"); 265 fprintf(stderr, "\tmyPhyOffset = %llu, myContiguousBytes = %u\n", myPhyOffset, myContiguousBytes); 266 size_t i = 0; 267 for (i = 0; i < myContiguousBytes; i++) 268 { 269 cached = ((uint8_t*)theScanStatePtr->bufferPtr)[i]; 270 raw = tempBuffer[i]; 271 if (cached != raw) 272 { 273 fprintf(stderr, "\tOffset %zu: cached value = 0x%02x, raw value = 0x%02x\n", i, cached, raw); 274 break; 275 } 276 } 277 extern void dumpCache(void*); 278 dumpCache(myBTreeCBPtr->fcbPtr->fcbVolume->vcbBlockCache); 279 abort(); 280 } 281 free(tempBuffer); 282#endif 283 } 284 285 286 287 if ( myErr != noErr ) 288 { 289 myErr = fsEndOfIterationErr; 290 goto ExitThisRoutine; 291 } 292 293 theScanStatePtr->nodesLeftInBuffer = myContiguousBytes / 294 theScanStatePtr->btcb->nodeSize; 295 theScanStatePtr->currentNodePtr = (BTNodeDescriptor *) theScanStatePtr->bufferPtr; 296 297ExitThisRoutine: 298 return myErr; 299 300} /* ReadMultipleNodes */ 301 302 303//_________________________________________________________________________________ 304// 305// Routine: BTScanInitialize 306// 307// Purpose: Prepare to start a new BTree scan. 308// 309// Inputs: 310// btreeFile The B-Tree's file control block 311// 312// Outputs: 313// scanState Scanner's current state; pass to other scanner calls 314// 315//_________________________________________________________________________________ 316 317int BTScanInitialize( const SFCB * btreeFile, 318 BTScanState * scanState ) 319{ 320 BTreeControlBlock *btcb; 321 u_int32_t bufferSize; 322 323 // 324 // Make sure this is a valid B-Tree file 325 // 326 btcb = (BTreeControlBlock *) btreeFile->fcbBtree; 327 if (btcb == NULL) 328 return R_RdErr; 329 330 // 331 // Make sure buffer size is big enough, and a multiple of the 332 // B-Tree node size 333 // 334 bufferSize = (kCatScanBufferSize / btcb->nodeSize) * btcb->nodeSize; 335 336 // 337 // Set up the scanner's state 338 // 339 scanState->bufferSize = bufferSize; 340 scanState->bufferPtr = (void *) AllocateMemory( bufferSize ); 341 if ( scanState->bufferPtr == NULL ) 342 return( R_NoMem ); 343 344 scanState->btcb = btcb; 345 scanState->nodeNum = 0; 346 scanState->recordNum = 0; 347 scanState->currentNodePtr = NULL; 348 scanState->nodesLeftInBuffer = 0; // no nodes currently in buffer 349 scanState->recordsFound = 0; 350 351 return noErr; 352 353} /* BTScanInitialize */ 354 355 356//_________________________________________________________________________________ 357// 358// Routine: BTScanTerminate 359// 360// Purpose: Return state information about a scan so that it can be resumed 361// later via BTScanInitialize. 362// 363// Inputs: 364// scanState Scanner's current state 365// 366// Outputs: 367// nextNode Node number to resume a scan (pass to BTScanInitialize) 368// nextRecord Record number to resume a scan (pass to BTScanInitialize) 369// recordsFound Valid records seen so far (pass to BTScanInitialize) 370//_________________________________________________________________________________ 371 372int BTScanTerminate( BTScanState * scanState ) 373{ 374 if ( scanState->bufferPtr != NULL ) 375 { 376 DisposeMemory( scanState->bufferPtr ); 377 scanState->bufferPtr = NULL; 378 scanState->currentNodePtr = NULL; 379 } 380 381 return noErr; 382 383} /* BTScanTerminate */ 384 385 386