1/* 2 * Copyright (c) 2000-2003, 2005-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/* 29 File: BTreeMiscOps.c 30 31 Contains: Miscellaneous operations for the BTree Module. 32 33 Version: xxx put the technology version here xxx 34 35 Written by: Gordon Sheridan and Bill Bruffey 36 37 Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved. 38 39 File Ownership: 40 41 DRI: Don Brady 42 43 Other Contact: Mark Day 44 45 Technology: File Systems 46 47 Writers: 48 49 (DSH) Deric Horn 50 (msd) Mark Day 51 (djb) Don Brady 52 53 Change History (most recent first): 54 55 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6. 56 <CS2> 9/4/97 djb Optimize TrySimpleReplace for the case where record size is not 57 changing. 58 <CS1> 4/23/97 djb first checked in 59 60 <HFS7> 3/31/97 djb Move ClearMemory to Utilities.c. 61 <HFS6> 3/17/97 DSH Casting for DFA 62 <HFS5> 2/27/97 msd Remove temporary fix from last revision. BTree EOF's should be 63 correct now, so check for strict equality. 64 <HFS4> 2/26/97 msd Fix a casting problem in ClearMemory. TEMPORARY FIX: Made 65 VerifyHeader more lenient, allowing the EOF to be greater than 66 the amount actually used by nodes; this should really be fixed 67 in the formatting code (which needs to compute the real BTree 68 sizes before writing the volume header). 69 <HFS3> 2/19/97 djb Added ClearMemory. Changed CalcKeyLength to KeyLength. 70 <HFS2> 1/3/97 djb Added support for large keys. 71 <HFS1> 12/19/96 djb first checked in 72 73 History applicable to original Scarecrow Design: 74 75 <9> 10/25/96 ser Changing for new VFPI 76 <8> 10/18/96 ser Converting over VFPI changes 77 <7> 9/17/96 dkh More BTree statistics. Change IsItAHint to not always check to 78 see if the hint node is allocated. 79 <6> 9/16/96 dkh Revised BTree statistics. 80 <5> 6/20/96 dkh Radar #1358740. Change from using Pools to debug MemAllocators. 81 <4> 1/22/96 dkh Change Pools.i inclusion to PoolsPriv.i 82 <3> 1/10/96 msd Change 64-bit math to use real function names from Math64.i. 83 <2> 12/7/95 dkh D10E2 build. Changed usage of Ref data type to LogicalAddress. 84 <1> 10/18/95 rst Moved from Scarecrow project. 85 86 <19> 4/26/95 prp In UpdateHeader, clear the dirty flag after the BTree is updated. 87 <18> 1/12/95 wjk Adopt Model FileSystem changes in D5. 88 <17> 11/16/94 prp Add IsItAHint routine and use it whenever hint's node number was 89 used for testing. 90 <16> 10/5/94 bk add pools.h include file 91 <15> 9/30/94 prp Get in sync with D2 interface changes. 92 <14> 7/22/94 wjk Convert to the new set of header files. 93 <13> 12/2/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and 94 NRCmds environments. 95 <12> 11/30/93 wjk Move from Makefiles to BuildFiles. Fit into the ModernOS and 96 NRCmds environments. 97 <11> 11/23/93 wjk Changes required to compile on the RS6000. 98 <10> 8/31/93 prp Use U64SetU instead of S64Set. 99 <9> 6/2/93 gs Update for changes to FSErrors.h and add some comments. 100 <8> 5/21/93 gs Modify UpdateHeader to write out attributes. Remove 101 Get/UpdateNode from TrySimpleReplace. 102 <7> 5/10/93 gs Add TrySimpleReplace routine. 103 <6> 3/23/93 gs Change MoveData to take void * instead of Ptr. Add UpdateHeader 104 and ClearBytes routines. 105 <5> 2/8/93 gs Add FindIteratorPosition. 106 <4> 12/10/92 gs Implement CheckKeyDescriptor and the KeyDescriptor interpreter. 107 <3> 12/8/92 gs Add GetKeyDescriptor, VerifyHeader, and Alloc/Dealloc memory 108 routines. 109 <2> 12/2/92 gs Add CompareKeys routine. 110 <1> 11/15/92 gs first checked in 111 112*/ 113 114#include "../headers/BTreesPrivate.h" 115#include "../../hfs_btreeio.h" 116 117 118////////////////////////////// Routine Definitions ////////////////////////////// 119 120/*------------------------------------------------------------------------------- 121Routine: CalcKeyRecordSize - Return size of combined key/record structure. 122 123Function: Rounds keySize and recSize so they will end on word boundaries. 124 Does NOT add size of offset. 125 126Input: keySize - length of key (including length field) 127 recSize - length of record data 128 129Output: none 130 131Result: u_int16_t - size of combined key/record that will be inserted in btree 132-------------------------------------------------------------------------------*/ 133 134u_int16_t CalcKeyRecordSize (u_int16_t keySize, 135 u_int16_t recSize ) 136{ 137 if ( M_IsOdd (keySize) ) keySize += 1; // pad byte 138 139 if (M_IsOdd (recSize) ) recSize += 1; // pad byte 140 141 return (keySize + recSize); 142} 143 144 145 146/*------------------------------------------------------------------------------- 147Routine: VerifyHeader - Validate fields of the BTree header record. 148 149Function: Examines the fields of the BTree header record to determine if the 150 fork appears to contain a valid BTree. 151 152Input: forkPtr - pointer to fork control block 153 header - pointer to BTree header 154 155 156Result: noErr - success 157 != noErr - failure 158-------------------------------------------------------------------------------*/ 159 160OSStatus VerifyHeader (FCB *filePtr, 161 BTHeaderRec *header ) 162{ 163 u_int64_t forkSize; 164 u_int32_t totalNodes; 165 166 167 switch (header->nodeSize) // node size == 512*2^n 168 { 169 case 512: 170 case 1024: 171 case 2048: 172 case 4096: 173 case 8192: 174 case 16384: 175 case 32768: break; 176 default: return fsBTInvalidHeaderErr; //�� E_BadNodeType 177 } 178 179 totalNodes = header->totalNodes; 180 181 forkSize = (u_int64_t)totalNodes * (u_int64_t)header->nodeSize; 182 183 if ( forkSize > (u_int64_t)filePtr->fcbEOF ) 184 return fsBTInvalidHeaderErr; 185 186 if ( header->freeNodes >= totalNodes ) 187 return fsBTInvalidHeaderErr; 188 189 if ( header->rootNode >= totalNodes ) 190 return fsBTInvalidHeaderErr; 191 192 if ( header->firstLeafNode >= totalNodes ) 193 return fsBTInvalidHeaderErr; 194 195 if ( header->lastLeafNode >= totalNodes ) 196 return fsBTInvalidHeaderErr; 197 198 if ( header->treeDepth > kMaxTreeDepth ) 199 return fsBTInvalidHeaderErr; 200 201 202 /////////////////////////// Check BTree Type //////////////////////////////// 203 204 switch (header->btreeType) 205 { 206 case 0: // HFS Type - no Key Descriptor 207 case kUserBTreeType: // with Key Descriptors etc. 208 case kReservedBTreeType: // Desktop Mgr BTree ? 209 break; 210 211 default: return fsBTUnknownVersionErr; 212 } 213 214 return noErr; 215} 216 217 218 219__private_extern__ 220OSStatus TreeIsDirty(BTreeControlBlockPtr btreePtr) 221{ 222 return (btreePtr->flags & kBTHeaderDirty); 223} 224 225 226 227/*------------------------------------------------------------------------------- 228Routine: UpdateHeader - Write BTreeInfoRec fields to Header node. 229 230Function: Checks the kBTHeaderDirty flag in the BTreeInfoRec and updates the 231 header node if necessary. 232 233Input: btreePtr - pointer to BTreeInfoRec 234 235 236Result: noErr - success 237 != noErr - failure 238-------------------------------------------------------------------------------*/ 239 240OSStatus UpdateHeader(BTreeControlBlockPtr btreePtr, Boolean forceWrite) 241{ 242 OSStatus err; 243 BlockDescriptor node; 244 BTHeaderRec *header; 245 u_int32_t options; 246 247 if ((btreePtr->flags & kBTHeaderDirty) == 0) // btree info already flushed 248 return noErr; 249 250 251 err = GetNode (btreePtr, kHeaderNodeNum, 0, &node ); 252 if (err != noErr) { 253 return err; 254 } 255 256 // XXXdbg 257 ModifyBlockStart(btreePtr->fileRefNum, &node); 258 259 header = (BTHeaderRec*) ((char *)node.buffer + sizeof(BTNodeDescriptor)); 260 261 header->treeDepth = btreePtr->treeDepth; 262 header->rootNode = btreePtr->rootNode; 263 header->leafRecords = btreePtr->leafRecords; 264 header->firstLeafNode = btreePtr->firstLeafNode; 265 header->lastLeafNode = btreePtr->lastLeafNode; 266 header->nodeSize = btreePtr->nodeSize; //�� this shouldn't change 267 header->maxKeyLength = btreePtr->maxKeyLength; //�� neither should this 268 header->totalNodes = btreePtr->totalNodes; 269 header->freeNodes = btreePtr->freeNodes; 270 header->btreeType = btreePtr->btreeType; 271 272 // ignore header->clumpSize; //�� rename this field? 273 274 if (forceWrite) 275 options = kForceWriteBlock; 276 else 277 options = kLockTransaction; 278 279 err = UpdateNode (btreePtr, &node, 0, options); 280 281 btreePtr->flags &= (~kBTHeaderDirty); 282 283 return err; 284} 285 286 287 288/*------------------------------------------------------------------------------- 289Routine: FindIteratorPosition - One_line_description. 290 291Function: Brief_description_of_the_function_and_any_side_effects 292 293Algorithm: see FSC.BT.BTIterateRecord.PICT 294 295Note: //�� document side-effects of bad node hints 296 297Input: btreePtr - description 298 iterator - description 299 300 301Output: iterator - description 302 left - description 303 middle - description 304 right - description 305 nodeNum - description 306 returnIndex - description 307 foundRecord - description 308 309 310Result: noErr - success 311 != noErr - failure 312-------------------------------------------------------------------------------*/ 313 314OSStatus FindIteratorPosition (BTreeControlBlockPtr btreePtr, 315 BTreeIteratorPtr iterator, 316 BlockDescriptor *left, 317 BlockDescriptor *middle, 318 BlockDescriptor *right, 319 u_int32_t *returnNodeNum, 320 u_int16_t *returnIndex, 321 Boolean *foundRecord ) 322{ 323 OSStatus err; 324 Boolean foundIt; 325 u_int32_t nodeNum; 326 u_int16_t leftIndex, index, rightIndex; 327 Boolean validHint; 328 329 // assume btreePtr valid 330 // assume left, middle, right point to BlockDescriptors 331 // assume nodeNum points to u_int32_t 332 // assume index points to u_int16_t 333 // assume foundRecord points to Boolean 334 335 left->buffer = nil; 336 left->blockHeader = nil; 337 middle->buffer = nil; 338 middle->blockHeader = nil; 339 right->buffer = nil; 340 right->blockHeader = nil; 341 342 foundIt = false; 343 344 if (iterator == nil) // do we have an iterator? 345 { 346 err = fsBTInvalidIteratorErr; 347 goto ErrorExit; 348 } 349 350 err = IsItAHint (btreePtr, iterator, &validHint); 351 M_ExitOnError (err); 352 353 nodeNum = iterator->hint.nodeNum; 354 if (! validHint) // does the hint appear to be valid? 355 { 356 goto SearchTheTree; 357 } 358 359 err = GetNode (btreePtr, nodeNum, kGetNodeHint, middle); 360 if( err == fsBTInvalidNodeErr ) // returned if nodeNum is out of range 361 goto SearchTheTree; 362 363 M_ExitOnError (err); 364 365 if ( ((NodeDescPtr) middle->buffer)->kind != kBTLeafNode || 366 ((NodeDescPtr) middle->buffer)->numRecords <= 0 ) 367 { 368 goto SearchTheTree; 369 } 370 371 foundIt = SearchNode (btreePtr, middle->buffer, &iterator->key, &index); 372 if (foundIt == true) 373 { 374 ++btreePtr->numValidHints; 375 goto SuccessfulExit; 376 } 377 iterator->hint.nodeNum = 0; 378 379 if (index == 0) 380 { 381 if (((NodeDescPtr) middle->buffer)->bLink == 0) // before 1st btree record 382 { 383 goto SuccessfulExit; 384 } 385 386 nodeNum = ((NodeDescPtr) middle->buffer)->bLink; 387 388 // BTree nodes are always grabbed in left to right order. 389 // Therefore release the current node before looking up the 390 // left node. 391 err = ReleaseNode(btreePtr, middle); 392 M_ExitOnError(err); 393 394 // Look up the left node 395 err = GetNode (btreePtr, nodeNum, 0, left); 396 M_ExitOnError (err); 397 398 // Look up the current node again 399 err = GetRightSiblingNode (btreePtr, left->buffer, middle); 400 M_ExitOnError (err); 401 402 if ( ((NodeDescPtr) left->buffer)->kind != kBTLeafNode || 403 ((NodeDescPtr) left->buffer)->numRecords <= 0 ) 404 { 405 goto SearchTheTree; 406 } 407 408 foundIt = SearchNode (btreePtr, left->buffer, &iterator->key, &leftIndex); 409 if (foundIt == true) 410 { 411 *right = *middle; 412 *middle = *left; 413 left->buffer = nil; 414 index = leftIndex; 415 416 goto SuccessfulExit; 417 } 418 419 if (leftIndex == 0) // we're lost! 420 { 421 goto SearchTheTree; 422 } 423 else if (leftIndex >= ((NodeDescPtr) left->buffer)->numRecords) 424 { 425 nodeNum = ((NodeDescPtr) left->buffer)->fLink; 426 427 PanicIf (index != 0, "FindIteratorPosition: index != 0"); //�� just checking... 428 goto SuccessfulExit; 429 } 430 else 431 { 432 *right = *middle; 433 *middle = *left; 434 left->buffer = nil; 435 index = leftIndex; 436 437 goto SuccessfulExit; 438 } 439 } 440 else if (index >= ((NodeDescPtr) middle->buffer)->numRecords) 441 { 442 if (((NodeDescPtr) middle->buffer)->fLink == 0) // beyond last record 443 { 444 goto SuccessfulExit; 445 } 446 447 nodeNum = ((NodeDescPtr) middle->buffer)->fLink; 448 449 err = GetRightSiblingNode (btreePtr, middle->buffer, right); 450 M_ExitOnError (err); 451 452 if ( ((NodeDescPtr) right->buffer)->kind != kBTLeafNode || 453 ((NodeDescPtr) right->buffer)->numRecords <= 0 ) 454 { 455 goto SearchTheTree; 456 } 457 458 foundIt = SearchNode (btreePtr, right->buffer, &iterator->key, &rightIndex); 459 if (rightIndex >= ((NodeDescPtr) right->buffer)->numRecords) // we're lost 460 { 461 goto SearchTheTree; 462 } 463 else // we found it, or rightIndex==0, or rightIndex<numRecs 464 { 465 *left = *middle; 466 *middle = *right; 467 right->buffer = nil; 468 index = rightIndex; 469 470 goto SuccessfulExit; 471 } 472 } 473 474 475 //////////////////////////// Search The Tree //////////////////////////////// 476 477SearchTheTree: 478 { 479 TreePathTable treePathTable; // so we only use stack space if we need to 480 481 err = ReleaseNode (btreePtr, left); M_ExitOnError (err); 482 err = ReleaseNode (btreePtr, middle); M_ExitOnError (err); 483 err = ReleaseNode (btreePtr, right); M_ExitOnError (err); 484 485 err = SearchTree ( btreePtr, &iterator->key, treePathTable, &nodeNum, middle, &index); 486 switch (err) //�� separate find condition from exceptions 487 { 488 case noErr: foundIt = true; break; 489 case fsBTRecordNotFoundErr: break; 490 default: goto ErrorExit; 491 } 492 } 493 494 /////////////////////////////// Success! //////////////////////////////////// 495 496SuccessfulExit: 497 498 *returnNodeNum = nodeNum; 499 *returnIndex = index; 500 *foundRecord = foundIt; 501 502 return noErr; 503 504 505 ////////////////////////////// Error Exit /////////////////////////////////// 506 507ErrorExit: 508 509 (void) ReleaseNode (btreePtr, left); 510 (void) ReleaseNode (btreePtr, middle); 511 (void) ReleaseNode (btreePtr, right); 512 513 *returnNodeNum = 0; 514 *returnIndex = 0; 515 *foundRecord = false; 516 517 return err; 518} 519 520 521 522/////////////////////////////// CheckInsertParams /////////////////////////////// 523 524OSStatus CheckInsertParams (FCB *filePtr, 525 BTreeIterator *iterator, 526 FSBufferDescriptor *record, 527 u_int16_t recordLen ) 528{ 529 BTreeControlBlockPtr btreePtr; 530 531 if (filePtr == nil) return paramErr; 532 533 btreePtr = (BTreeControlBlockPtr) filePtr->fcbBTCBPtr; 534 if (btreePtr == nil) return fsBTInvalidFileErr; 535 if (iterator == nil) return paramErr; 536 if (record == nil) return paramErr; 537 538 // check total key/record size limit 539 if ( CalcKeyRecordSize (CalcKeySize(btreePtr, &iterator->key), recordLen) > (btreePtr->nodeSize >> 1)) 540 return fsBTRecordTooLargeErr; 541 542 return noErr; 543} 544 545 546 547/*------------------------------------------------------------------------------- 548Routine: TrySimpleReplace - Attempts a simple insert, set, or replace. 549 550Function: If a hint exitst for the iterator, attempt to find the key in the hint 551 node. If the key is found, an insert operation fails. If the is not 552 found, a replace operation fails. If the key was not found, and the 553 insert position is greater than 0 and less than numRecords, the record 554 is inserted, provided there is enough freeSpace. If the key was found, 555 and there is more freeSpace than the difference between the new record 556 and the old record, the old record is deleted and the new record is 557 inserted. 558 559Assumptions: iterator key has already been checked by CheckKey 560 561 562Input: btreePtr - description 563 iterator - description 564 record - description 565 recordLen - description 566 operation - description 567 568 569Output: recordInserted - description 570 571 572Result: noErr - success 573 E_RecordExits - insert operation failure 574 != noErr - GetNode, ReleaseNode, UpdateNode returned an error 575-------------------------------------------------------------------------------*/ 576 577OSStatus TrySimpleReplace (BTreeControlBlockPtr btreePtr, 578 NodeDescPtr nodePtr, 579 BTreeIterator *iterator, 580 FSBufferDescriptor *record, 581 u_int16_t recordLen, 582 Boolean *recordInserted ) 583{ 584 u_int32_t oldSpace; 585 u_int32_t spaceNeeded; 586 u_int16_t index; 587 u_int16_t keySize; 588 Boolean foundIt; 589 Boolean didItFit; 590 591 592 *recordInserted = false; // we'll assume this won't work... 593 594 if ( nodePtr->kind != kBTLeafNode ) 595 return noErr; // we're in the weeds! 596 597 foundIt = SearchNode (btreePtr, nodePtr, &iterator->key, &index); 598 599 if ( foundIt == false ) 600 return noErr; // we might be lost... 601 602 keySize = CalcKeySize(btreePtr, &iterator->key); // includes length field 603 604 spaceNeeded = CalcKeyRecordSize (keySize, recordLen); 605 606 oldSpace = GetRecordSize (btreePtr, nodePtr, index); 607 608 if ( spaceNeeded == oldSpace ) 609 { 610 u_int8_t * dst; 611 612 dst = GetRecordAddress (btreePtr, nodePtr, index); 613 614 if ( M_IsOdd (keySize) ) 615 ++keySize; // add pad byte 616 617 dst += keySize; // skip over key to point at record 618 619 BlockMoveData(record->bufferAddress, dst, recordLen); // blast away... 620 621 *recordInserted = true; 622 } 623 else if ( (GetNodeFreeSize(btreePtr, nodePtr) + oldSpace) >= spaceNeeded) 624 { 625 DeleteRecord (btreePtr, nodePtr, index); 626 627 didItFit = InsertKeyRecord (btreePtr, nodePtr, index, 628 &iterator->key, KeyLength(btreePtr, &iterator->key), 629 record->bufferAddress, recordLen); 630 PanicIf (didItFit == false, "TrySimpleInsert: InsertKeyRecord returned false!"); 631 632 *recordInserted = true; 633 } 634 // else not enough space... 635 636 return noErr; 637} 638 639 640/*------------------------------------------------------------------------------- 641Routine: IsItAHint - checks the hint within a BTreeInterator. 642 643Function: checks the hint within a BTreeInterator. If it is non-zero, it may 644 possibly be valid. 645 646Input: btreePtr - pointer to control block for BTree file 647 iterator - pointer to BTreeIterator 648 649Output: answer - true if the hint looks reasonable 650 - false if the hint is 0 651 652Result: noErr - success 653-------------------------------------------------------------------------------*/ 654 655 656OSStatus IsItAHint (BTreeControlBlockPtr btreePtr, BTreeIterator *iterator, Boolean *answer) 657{ 658 ++btreePtr->numHintChecks; 659 660#if DEBUG_BUILD 661 if (iterator->hint.nodeNum >= btreePtr->totalNodes) 662 { 663 *answer = false; 664 } else 665 666#endif 667 if (iterator->hint.nodeNum == 0) 668 { 669 *answer = false; 670 } 671 else 672 { 673 *answer = true; 674 ++btreePtr->numPossibleHints; 675 } 676 677 return noErr; 678} 679