1/* 2 * Copyright (c) 1996-2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_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. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 * 28 * @(#)BTreeScanner.c 29 */ 30#include <sys/kernel.h> 31#include "../../hfs_endian.h" 32 33#include "../headers/BTreeScanner.h" 34 35static int FindNextLeafNode( BTScanState *scanState, Boolean avoidIO ); 36static int ReadMultipleNodes( BTScanState *scanState ); 37 38 39//_________________________________________________________________________________ 40// 41// Routine: BTScanNextRecord 42// 43// Purpose: Return the next leaf record in a scan. 44// 45// Inputs: 46// scanState Scanner's current state 47// avoidIO If true, don't do any I/O to refill the buffer 48// 49// Outputs: 50// key Key of found record (points into buffer) 51// data Data of found record (points into buffer) 52// dataSize Size of data in found record 53// 54// Result: 55// noErr Found a valid record 56// btNotFound No more records 57// ??? Needed to do I/O to get next node, but avoidIO set 58// 59// Notes: 60// This routine returns pointers to the found record's key and data. It 61// does not copy the key or data to a caller-supplied buffer (like 62// GetBTreeRecord would). The caller must not modify the key or data. 63//_________________________________________________________________________________ 64 65int BTScanNextRecord( BTScanState * scanState, 66 Boolean avoidIO, 67 void * * key, 68 void * * data, 69 u_int32_t * dataSize ) 70{ 71 int err; 72 u_int16_t dataSizeShort; 73 74 err = noErr; 75 76 // 77 // If this is the first call, there won't be any nodes in the buffer, so go 78 // find the first first leaf node (if any). 79 // 80 if ( scanState->nodesLeftInBuffer == 0 ) 81 { 82 err = FindNextLeafNode( scanState, avoidIO ); 83 } 84 85 while ( err == noErr ) 86 { 87 // See if we have a record in the current node 88 err = GetRecordByIndex( scanState->btcb, scanState->currentNodePtr, 89 scanState->recordNum, (KeyPtr *) key, 90 (u_int8_t **) data, &dataSizeShort ); 91 92 if ( err == noErr ) 93 { 94 ++scanState->recordsFound; 95 ++scanState->recordNum; 96 if (dataSize != NULL) 97 *dataSize = dataSizeShort; 98 return noErr; 99 } 100 else if (err > 0) 101 { 102 // We didn't get the node through the cache, so we can't invalidate it. 103 //XXX Should we do something else to avoid seeing the same record again? 104 return err; 105 } 106 107 // We're done with the current node. See if we've returned all the records 108 if ( scanState->recordsFound >= scanState->btcb->leafRecords ) 109 { 110 return btNotFound; 111 } 112 113 // Move to the first record of the next leaf node 114 scanState->recordNum = 0; 115 err = FindNextLeafNode( scanState, avoidIO ); 116 } 117 118 // 119 // If we got an EOF error from FindNextLeafNode, then there are no more leaf 120 // records to be found. 121 // 122 if ( err == fsEndOfIterationErr ) 123 err = btNotFound; 124 125 return err; 126 127} /* BTScanNextRecord */ 128 129 130//_________________________________________________________________________________ 131// 132// Routine: FindNextLeafNode 133// 134// Purpose: Point to the next leaf node in the buffer. Read more nodes 135// into the buffer if needed (and allowed). 136// 137// Inputs: 138// scanState Scanner's current state 139// avoidIO If true, don't do any I/O to refill the buffer 140// 141// Result: 142// noErr Found a valid record 143// fsEndOfIterationErr No more nodes in file 144// ??? Needed to do I/O to get next node, but avoidIO set 145//_________________________________________________________________________________ 146 147static int FindNextLeafNode( BTScanState *scanState, Boolean avoidIO ) 148{ 149 int err; 150 BlockDescriptor block; 151 FileReference fref; 152 153 err = noErr; // Assume everything will be OK 154 155 while ( 1 ) 156 { 157 if ( scanState->nodesLeftInBuffer == 0 ) 158 { 159 // Time to read some more nodes into the buffer 160 if ( avoidIO ) 161 { 162 return fsBTTimeOutErr; 163 } 164 else 165 { 166 // read some more nodes into buffer 167 err = ReadMultipleNodes( scanState ); 168 if ( err != noErr ) 169 break; 170 } 171 } 172 else 173 { 174 // Adjust the node counters and point to the next node in the buffer 175 ++scanState->nodeNum; 176 --scanState->nodesLeftInBuffer; 177 178 // If we've looked at all nodes in the tree, then we're done 179 if ( scanState->nodeNum >= scanState->btcb->totalNodes ) 180 return fsEndOfIterationErr; 181 182 if ( scanState->nodesLeftInBuffer == 0 ) 183 { 184 scanState->recordNum = 0; 185 continue; 186 } 187 188 scanState->currentNodePtr = (BTNodeDescriptor *)(((u_int8_t *)scanState->currentNodePtr) 189 + scanState->btcb->nodeSize); 190 } 191 192 /* Fake a BlockDescriptor */ 193 block.blockHeader = NULL; /* No buffer cache buffer */ 194 block.buffer = scanState->currentNodePtr; 195 block.blockNum = scanState->nodeNum; 196 block.blockSize = scanState->btcb->nodeSize; 197 block.blockReadFromDisk = 1; 198 block.isModified = 0; 199 200 fref = scanState->btcb->fileRefNum; 201 202 /* This node was read from disk, so it must be swapped/checked. 203 * Since we are reading multiple nodes, we might have read an 204 * unused node. Therefore we allow swapping of unused nodes. 205 */ 206 err = hfs_swap_BTNode(&block, fref, kSwapBTNodeBigToHost, true); 207 if ( err != noErr ) { 208 printf("hfs: FindNextLeafNode: Error from hfs_swap_BTNode (node %u)\n", scanState->nodeNum); 209 continue; 210 } 211 212 if ( scanState->currentNodePtr->kind == kBTLeafNode ) 213 break; 214 } 215 216 return err; 217 218} /* FindNextLeafNode */ 219 220 221//_________________________________________________________________________________ 222// 223// Routine: ReadMultipleNodes 224// 225// Purpose: Read one or more nodes into the buffer. 226// 227// Inputs: 228// theScanStatePtr Scanner's current state 229// 230// Result: 231// noErr One or nodes were read 232// fsEndOfIterationErr No nodes left in file, none in buffer 233//_________________________________________________________________________________ 234 235static int ReadMultipleNodes( BTScanState *theScanStatePtr ) 236{ 237 int myErr = E_NONE; 238 BTreeControlBlockPtr myBTreeCBPtr; 239 daddr64_t myPhyBlockNum; 240 u_int32_t myBufferSize; 241 struct vnode * myDevPtr; 242 unsigned int myBlockRun; 243 u_int32_t myBlocksInBufferCount; 244 245 // release old buffer if we have one 246 if ( theScanStatePtr->bufferPtr != NULL ) 247 { 248 buf_markinvalid(theScanStatePtr->bufferPtr); 249 buf_brelse( theScanStatePtr->bufferPtr ); 250 theScanStatePtr->bufferPtr = NULL; 251 theScanStatePtr->currentNodePtr = NULL; 252 } 253 254 myBTreeCBPtr = theScanStatePtr->btcb; 255 256 // map logical block in catalog btree file to physical block on volume 257 myErr = hfs_bmap(myBTreeCBPtr->fileRefNum, theScanStatePtr->nodeNum, 258 &myDevPtr, &myPhyBlockNum, &myBlockRun); 259 if ( myErr != E_NONE ) 260 { 261 goto ExitThisRoutine; 262 } 263 264 // bmap block run gives us the remaining number of valid blocks (number of blocks 265 // minus the first). so if there are 10 valid blocks our run number will be 9. 266 // blocks, in our case is the same as nodes (both are 4K) 267 myBlocksInBufferCount = (theScanStatePtr->bufferSize / myBTreeCBPtr->nodeSize ); 268 myBufferSize = theScanStatePtr->bufferSize; 269 if ( (myBlockRun + 1) < myBlocksInBufferCount ) 270 { 271 myBufferSize = (myBlockRun + 1) * myBTreeCBPtr->nodeSize; 272 } 273 274 // now read blocks from the device 275 myErr = (int)buf_meta_bread(myDevPtr, 276 myPhyBlockNum, 277 myBufferSize, 278 NOCRED, 279 &theScanStatePtr->bufferPtr ); 280 if ( myErr != E_NONE ) 281 { 282 goto ExitThisRoutine; 283 } 284 285 theScanStatePtr->nodesLeftInBuffer = buf_count(theScanStatePtr->bufferPtr) / theScanStatePtr->btcb->nodeSize; 286 theScanStatePtr->currentNodePtr = (BTNodeDescriptor *) buf_dataptr(theScanStatePtr->bufferPtr); 287 288ExitThisRoutine: 289 return myErr; 290 291} /* ReadMultipleNodes */ 292 293 294 295//_________________________________________________________________________________ 296// 297// Routine: BTScanInitialize 298// 299// Purpose: Prepare to start a new BTree scan, or resume a previous one. 300// 301// Inputs: 302// btreeFile The B-Tree's file control block 303// startingNode Initial node number 304// startingRecord Initial record number within node 305// recordsFound Number of valid records found so far 306// bufferSize Size (in bytes) of buffer 307// 308// Outputs: 309// scanState Scanner's current state; pass to other scanner calls 310// 311// Notes: 312// To begin a new scan and see all records in the B-Tree, pass zeroes for 313// startingNode, startingRecord, and recordsFound. 314// 315// To resume a scan from the point of a previous BTScanTerminate, use the 316// values returned by BTScanTerminate as input for startingNode, startingRecord, 317// and recordsFound. 318// 319// When resuming a scan, the caller should check the B-tree's write count. If 320// it is different from the write count when the scan was terminated, then the 321// tree may have changed and the current state may be incorrect. In particular, 322// you may see some records more than once, or never see some records. Also, 323// the scanner may not be able to detect when all leaf records have been seen, 324// and will have to scan through many empty nodes. 325// 326// XXX�Perhaps the write count should be managed by BTScanInitialize and 327// XXX BTScanTerminate? This would avoid the caller having to peek at 328// XXX internal B-Tree structures. 329//_________________________________________________________________________________ 330 331int BTScanInitialize( const FCB * btreeFile, 332 u_int32_t startingNode, 333 u_int32_t startingRecord, 334 u_int32_t recordsFound, 335 u_int32_t bufferSize, 336 BTScanState * scanState ) 337{ 338 BTreeControlBlock *btcb; 339 340 // 341 // Make sure this is a valid B-Tree file 342 // 343 btcb = (BTreeControlBlock *) btreeFile->fcbBTCBPtr; 344 if (btcb == NULL) 345 return fsBTInvalidFileErr; 346 347 // 348 // Make sure buffer size is big enough, and a multiple of the 349 // B-Tree node size 350 // 351 if ( bufferSize < btcb->nodeSize ) 352 return paramErr; 353 bufferSize = (bufferSize / btcb->nodeSize) * btcb->nodeSize; 354 355 // 356 // Set up the scanner's state 357 // 358 scanState->bufferSize = bufferSize; 359 scanState->bufferPtr = NULL; 360 scanState->btcb = btcb; 361 scanState->nodeNum = startingNode; 362 scanState->recordNum = startingRecord; 363 scanState->currentNodePtr = NULL; 364 scanState->nodesLeftInBuffer = 0; // no nodes currently in buffer 365 scanState->recordsFound = recordsFound; 366 microuptime(&scanState->startTime); // initialize our throttle 367 368 return noErr; 369 370} /* BTScanInitialize */ 371 372 373//_________________________________________________________________________________ 374// 375// Routine: BTScanTerminate 376// 377// Purpose: Return state information about a scan so that it can be resumed 378// later via BTScanInitialize. 379// 380// Inputs: 381// scanState Scanner's current state 382// 383// Outputs: 384// nextNode Node number to resume a scan (pass to BTScanInitialize) 385// nextRecord Record number to resume a scan (pass to BTScanInitialize) 386// recordsFound Valid records seen so far (pass to BTScanInitialize) 387//_________________________________________________________________________________ 388 389int BTScanTerminate( BTScanState * scanState, 390 u_int32_t * startingNode, 391 u_int32_t * startingRecord, 392 u_int32_t * recordsFound ) 393{ 394 *startingNode = scanState->nodeNum; 395 *startingRecord = scanState->recordNum; 396 *recordsFound = scanState->recordsFound; 397 398 if ( scanState->bufferPtr != NULL ) 399 { 400 buf_markinvalid(scanState->bufferPtr); 401 buf_brelse( scanState->bufferPtr ); 402 scanState->bufferPtr = NULL; 403 scanState->currentNodePtr = NULL; 404 } 405 406 return noErr; 407 408} /* BTScanTerminate */ 409 410 411