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: BTreeAllocate.c 30 31 Contains: BTree Node Allocation routines 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 (djb) Don Brady 50 (ser) Scott Roberts 51 (msd) Mark Day 52 53 Change History (most recent first): 54 55 <MOSXS> 6/1/99 djb Sync up with Mac OS 8.6. 56 <CS3> 11/24/97 djb Remove some debug code (Panic calls). 57 <CS2> 7/24/97 djb CallbackProcs now take refnum instead of an FCB. 58 <CS1> 4/23/97 djb first checked in 59 60 <HFS2> 2/19/97 djb Change E_BadNodeType to fsBTBadNodeType. 61 <HFS1> 12/19/96 djb first checked in 62 63 History applicable to original Scarecrow Design: 64 65 <4> 10/25/96 ser Changing for new VFPI 66 <3> 10/18/96 ser Converting over VFPI changes 67 <2> 1/10/96 msd Change 64-bit math to use real function names from Math64.i. 68 <1> 10/18/95 rst Moved from Scarecrow project. 69 70 <8> 1/12/95 wjk Adopt Model FileSystem changes in D5. 71 <7> 9/30/94 prp Get in sync with D2 interface changes. 72 <6> 7/22/94 wjk Convert to the new set of header files. 73 <5> 8/31/93 prp Use U64SetU instead of S64Set. 74 <4> 5/21/93 gs Fix ExtendBTree bug. 75 <3> 5/10/93 gs Fix pointer arithmetic bug in AllocateNode. 76 <2> 3/23/93 gs finish ExtendBTree routine. 77 <1> 2/8/93 gs first checked in 78 <0> 1/1/93 gs begin AllocateNode and FreeNode 79 80*/ 81 82#include "../../hfs_btreeio.h" 83#include "../../hfs_endian.h" 84#include "../headers/BTreesPrivate.h" 85 86///////////////////// Routines Internal To BTreeAllocate.c ////////////////////// 87 88static OSStatus GetMapNode (BTreeControlBlockPtr btreePtr, 89 BlockDescriptor *nodePtr, 90 u_int16_t **mapPtr, 91 u_int16_t *mapSize ); 92 93///////////////////////////////////////////////////////////////////////////////// 94 95/*------------------------------------------------------------------------------- 96 97Routine: AllocateNode - Find Free Node, Mark It Used, and Return Node Number. 98 99Function: Searches the map records for the first free node, marks it "in use" and 100 returns the node number found. This routine should really only be called 101 when we know there are free blocks, otherwise it's just a waste of time. 102 103Note: We have to examine map nodes a word at a time rather than a long word 104 because the External BTree Mgr used map records that were not an integral 105 number of long words. Too bad. In our spare time could develop a more 106 sophisticated algorithm that read map records by long words (and long 107 word aligned) and handled the spare bytes at the beginning and end 108 appropriately. 109 110Input: btreePtr - pointer to control block for BTree file 111 112Output: nodeNum - number of node allocated 113 114 115Result: noErr - success 116 fsBTNoMoreMapNodesErr - no free blocks were found 117 != noErr - failure 118-------------------------------------------------------------------------------*/ 119 120OSStatus AllocateNode (BTreeControlBlockPtr btreePtr, u_int32_t *nodeNum) 121{ 122 OSStatus err; 123 BlockDescriptor node; 124 u_int16_t *mapPtr, *pos; 125 u_int16_t mapSize, size; 126 u_int16_t freeWord; 127 u_int16_t mask; 128 u_int16_t bitOffset; 129 u_int32_t nodeNumber; 130 131 132 nodeNumber = 0; // first node number of header map record 133 node.buffer = nil; // clear node.buffer to get header node 134 // - and for ErrorExit 135 node.blockHeader = nil; 136 137 while (true) 138 { 139 err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize); 140 M_ExitOnError (err); 141 142 // XXXdbg 143 ModifyBlockStart(btreePtr->fileRefNum, &node); 144 145 //////////////////////// Find Word with Free Bit //////////////////////////// 146 147 pos = mapPtr; 148 size = mapSize; 149 size >>= 1; // convert to number of words 150 //�� assumes mapRecords contain an integral number of words 151 152 while ( size-- ) 153 { 154 if ( *pos++ != 0xFFFF ) // assume test fails, and increment pos 155 break; 156 } 157 158 --pos; // whoa! backup 159 160 if (*pos != 0xFFFF) // hey, we got one! 161 break; 162 163 nodeNumber += mapSize << 3; // covert to number of bits (nodes) 164 } 165 166 ///////////////////////// Find Free Bit in Word ///////////////////////////// 167 168 freeWord = SWAP_BE16 (*pos); 169 bitOffset = 15; 170 mask = 0x8000; 171 172 do { 173 if ( (freeWord & mask) == 0) 174 break; 175 mask >>= 1; 176 } while (--bitOffset); 177 178 ////////////////////// Calculate Free Node Number /////////////////////////// 179 180 nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset); // (pos-mapPtr) = # of words! 181 182 183 ///////////////////////// Check for End of Map ////////////////////////////// 184 185 if (nodeNumber >= btreePtr->totalNodes) 186 { 187 err = fsBTFullErr; 188 goto ErrorExit; 189 } 190 191 /////////////////////////// Allocate the Node /////////////////////////////// 192 193 *pos |= SWAP_BE16 (mask); // set the map bit for the node 194 195 err = UpdateNode (btreePtr, &node, 0, kLockTransaction); 196 M_ExitOnError (err); 197 198 --btreePtr->freeNodes; 199 btreePtr->flags |= kBTHeaderDirty; 200 201 /* Account for allocations from node reserve */ 202 BTUpdateReserve(btreePtr, 1); 203 204 *nodeNum = nodeNumber; 205 206 return noErr; 207 208////////////////////////////////// Error Exit /////////////////////////////////// 209 210ErrorExit: 211 212 (void) ReleaseNode (btreePtr, &node); 213 *nodeNum = 0; 214 215 return err; 216} 217 218 219 220/*------------------------------------------------------------------------------- 221 222Routine: FreeNode - Clear allocation bit for node. 223 224Function: Finds the bit representing the node specified by nodeNum in the node 225 map and clears the bit. 226 227 228Input: btreePtr - pointer to control block for BTree file 229 nodeNum - number of node to mark free 230 231Output: none 232 233Result: noErr - success 234 fsBTNoMoreMapNodesErr - node number is beyond end of node map 235 != noErr - GetNode or ReleaseNode encountered some difficulty 236-------------------------------------------------------------------------------*/ 237 238OSStatus FreeNode (BTreeControlBlockPtr btreePtr, u_int32_t nodeNum) 239{ 240 OSStatus err; 241 BlockDescriptor node; 242 u_int32_t nodeIndex; 243 u_int16_t mapSize; 244 u_int16_t *mapPos; 245 u_int16_t bitOffset; 246 247 248 //////////////////////////// Find Map Record //////////////////////////////// 249 nodeIndex = 0; // first node number of header map record 250 node.buffer = nil; // invalidate node.buffer to get header node 251 node.blockHeader = nil; 252 253 while (nodeNum >= nodeIndex) 254 { 255 err = GetMapNode (btreePtr, &node, &mapPos, &mapSize); 256 M_ExitOnError (err); 257 258 nodeIndex += mapSize << 3; // covert to number of bits (nodes) 259 } 260 261 //////////////////////////// Mark Node Free ///////////////////////////////// 262 263 // XXXdbg 264 ModifyBlockStart(btreePtr->fileRefNum, &node); 265 266 nodeNum -= (nodeIndex - (mapSize << 3)); // relative to this map record 267 bitOffset = 15 - (nodeNum & 0x0000000F); // last 4 bits are bit offset 268 mapPos += nodeNum >> 4; // point to word containing map bit 269 270 M_SWAP_BE16_ClearBitNum (*mapPos, bitOffset); // clear it 271 272 err = UpdateNode (btreePtr, &node, 0, kLockTransaction); 273 M_ExitOnError (err); 274 275 ++btreePtr->freeNodes; 276 btreePtr->flags |= kBTHeaderDirty; // how about a macro for this 277 278 return noErr; 279 280ErrorExit: 281 282 (void) ReleaseNode (btreePtr, &node); 283 284 return err; 285} 286 287 288 289/*------------------------------------------------------------------------------- 290 291Routine: ExtendBTree - Call FSAgent to extend file, and allocate necessary map nodes. 292 293Function: This routine calls the the FSAgent to extend the end of fork, if necessary, 294 to accomodate the number of nodes requested. It then allocates as many 295 map nodes as are necessary to account for all the nodes in the B*Tree. 296 If newTotalNodes is less than the current number of nodes, no action is 297 taken. 298 299Note: Internal HFS File Manager BTree Module counts on an integral number of 300 long words in map records, although they are not long word aligned. 301 302Input: btreePtr - pointer to control block for BTree file 303 newTotalNodes - total number of nodes the B*Tree is to extended to 304 305Output: none 306 307Result: noErr - success 308 != noErr - failure 309-------------------------------------------------------------------------------*/ 310 311OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr, 312 u_int32_t newTotalNodes ) 313{ 314 OSStatus err; 315 FCB *filePtr; 316 FSSize minEOF, maxEOF; 317 u_int16_t nodeSize; 318 u_int32_t oldTotalNodes; 319 u_int32_t newMapNodes; 320 u_int32_t mapBits, totalMapBits; 321 u_int32_t recStartBit; 322 u_int32_t nodeNum, nextNodeNum; 323 u_int32_t firstNewMapNodeNum, lastNewMapNodeNum; 324 BlockDescriptor mapNode, newNode; 325 u_int16_t *mapPos; 326 u_int16_t *mapStart; 327 u_int16_t mapSize; 328 u_int16_t mapNodeRecSize; 329 u_int32_t bitInWord, bitInRecord; 330 u_int16_t mapIndex; 331 332 333 oldTotalNodes = btreePtr->totalNodes; 334 if (newTotalNodes <= oldTotalNodes) // we're done! 335 return noErr; 336 337 nodeSize = btreePtr->nodeSize; 338 filePtr = GetFileControlBlock(btreePtr->fileRefNum); 339 340 mapNode.buffer = nil; 341 mapNode.blockHeader = nil; 342 newNode.buffer = nil; 343 newNode.blockHeader = nil; 344 345 mapNodeRecSize = nodeSize - sizeof(BTNodeDescriptor) - 6; // 2 bytes of free space (see note) 346 347 348 //////////////////////// Count Bits In Node Map ///////////////////////////// 349 350 totalMapBits = 0; 351 do { 352 err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize); 353 M_ExitOnError (err); 354 355 mapBits = mapSize << 3; // mapSize (in bytes) * 8 356 recStartBit = totalMapBits; // bit number of first bit in map record 357 totalMapBits += mapBits; 358 359 } while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 ); 360 361 if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr)) 362 Panic ("\pExtendBTree: totalMapBits != CalcMapBits"); 363 364 /////////////////////// Extend LEOF If Necessary //////////////////////////// 365 366 minEOF = (u_int64_t)newTotalNodes * (u_int64_t)nodeSize; 367 if ( (u_int64_t)filePtr->fcbEOF < minEOF ) 368 { 369 maxEOF = (u_int64_t)0x7fffffffLL * (u_int64_t)nodeSize; 370 371 err = btreePtr->setEndOfForkProc (btreePtr->fileRefNum, minEOF, maxEOF); 372 M_ExitOnError (err); 373 } 374 375 376 //////////////////// Calc New Total Number Of Nodes ///////////////////////// 377 378 newTotalNodes = filePtr->fcbEOF / nodeSize; // hack! 379 // do we wish to perform any verification of newTotalNodes at this point? 380 381 btreePtr->totalNodes = newTotalNodes; // do we need to update freeNodes here too? 382 383 384 ////////////// Calculate Number Of New Map Nodes Required /////////////////// 385 386 newMapNodes = 0; 387 if (newTotalNodes > totalMapBits) 388 { 389 newMapNodes = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1; 390 firstNewMapNodeNum = oldTotalNodes; 391 lastNewMapNodeNum = firstNewMapNodeNum + newMapNodes - 1; 392 } 393 else 394 { 395 err = ReleaseNode (btreePtr, &mapNode); 396 M_ExitOnError (err); 397 398 goto Success; 399 } 400 401 402 /////////////////////// Initialize New Map Nodes //////////////////////////// 403 // XXXdbg - this is the correct place for this: 404 ModifyBlockStart(btreePtr->fileRefNum, &mapNode); 405 406 ((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum; 407 408 nodeNum = firstNewMapNodeNum; 409 while (true) 410 { 411 err = GetNewNode (btreePtr, nodeNum, &newNode); 412 M_ExitOnError (err); 413 414 // XXXdbg 415 ModifyBlockStart(btreePtr->fileRefNum, &newNode); 416 417 ((NodeDescPtr)newNode.buffer)->numRecords = 1; 418 ((NodeDescPtr)newNode.buffer)->kind = kBTMapNode; 419 420 // set free space offset 421 *(u_int16_t *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6; 422 423 if (nodeNum++ == lastNewMapNodeNum) 424 break; 425 426 ((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum; // point to next map node 427 428 err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction); 429 M_ExitOnError (err); 430 } 431 432 err = UpdateNode (btreePtr, &newNode, 0, kLockTransaction); 433 M_ExitOnError (err); 434 435 436 ///////////////////// Mark New Map Nodes Allocated ////////////////////////// 437 438 nodeNum = firstNewMapNodeNum; 439 do { 440 bitInRecord = nodeNum - recStartBit; 441 442 while (bitInRecord >= mapBits) 443 { 444 nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink; 445 if ( nextNodeNum == 0) 446 { 447 err = fsBTNoMoreMapNodesErr; 448 goto ErrorExit; 449 } 450 451 err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction); 452 M_ExitOnError (err); 453 454 err = GetNode (btreePtr, nextNodeNum, 0, &mapNode); 455 M_ExitOnError (err); 456 457 // XXXdbg 458 ModifyBlockStart(btreePtr->fileRefNum, &mapNode); 459 460 mapIndex = 0; 461 462 mapStart = (u_int16_t *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex); 463 mapSize = GetRecordSize (btreePtr, mapNode.buffer, mapIndex); 464 465 if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) ) 466 { 467 Panic ("\pExtendBTree: mapSize != M_MapRecordSize"); 468 } 469 470 mapBits = mapSize << 3; // mapSize (in bytes) * 8 471 recStartBit = totalMapBits; // bit number of first bit in map record 472 totalMapBits += mapBits; 473 474 bitInRecord = nodeNum - recStartBit; 475 } 476 477 mapPos = mapStart + ((nodeNum - recStartBit) >> 4); 478 bitInWord = 15 - ((nodeNum - recStartBit) & 0x0000000F); 479 480 M_SWAP_BE16_SetBitNum (*mapPos, bitInWord); 481 482 ++nodeNum; 483 484 } while (nodeNum <= lastNewMapNodeNum); 485 486 err = UpdateNode (btreePtr, &mapNode, 0, kLockTransaction); 487 M_ExitOnError (err); 488 489 490 //////////////////////////////// Success //////////////////////////////////// 491 492Success: 493 494 btreePtr->totalNodes = newTotalNodes; 495 btreePtr->freeNodes += (newTotalNodes - oldTotalNodes) - newMapNodes; 496 497 btreePtr->flags |= kBTHeaderDirty; //�� how about a macro for this 498 499 /* Force the b-tree header changes to disk */ 500 (void) UpdateHeader (btreePtr, true); 501 502 return noErr; 503 504 505 ////////////////////////////// Error Exit /////////////////////////////////// 506 507ErrorExit: 508 509 (void) ReleaseNode (btreePtr, &mapNode); 510 (void) ReleaseNode (btreePtr, &newNode); 511 512 return err; 513} 514 515 516 517/*------------------------------------------------------------------------------- 518 519Routine: GetMapNode - Get the next map node and pointer to the map record. 520 521Function: Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases 522 it and gets the next node. If nodePtr->buffer is nil, then the header 523 node is retrieved. 524 525 526Input: btreePtr - pointer to control block for BTree file 527 nodePtr - pointer to a BlockDescriptor of a map node 528 529Output: nodePtr - pointer to the BlockDescriptor for the next map node 530 mapPtr - pointer to the map record within the map node 531 mapSize - number of bytes in the map record 532 533Result: noErr - success 534 fsBTNoMoreMapNodesErr - we've run out of map nodes 535 fsBTInvalidNodeErr - bad node, or not node type kMapNode 536 != noErr - failure 537-------------------------------------------------------------------------------*/ 538 539static 540OSStatus GetMapNode (BTreeControlBlockPtr btreePtr, 541 BlockDescriptor *nodePtr, 542 u_int16_t **mapPtr, 543 u_int16_t *mapSize ) 544{ 545 OSStatus err; 546 u_int16_t mapIndex; 547 u_int32_t nextNodeNum; 548 549 if (nodePtr->buffer != nil) // if iterator is valid... 550 { 551 nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink; 552 if (nextNodeNum == 0) 553 { 554 err = fsBTNoMoreMapNodesErr; 555 goto ErrorExit; 556 } 557 558 err = ReleaseNode (btreePtr, nodePtr); 559 M_ExitOnError (err); 560 561 err = GetNode (btreePtr, nextNodeNum, 0, nodePtr); 562 M_ExitOnError (err); 563 564 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode) 565 { 566 err = fsBTBadNodeType; 567 goto ErrorExit; 568 } 569 570 ++btreePtr->numMapNodesRead; 571 mapIndex = 0; 572 } else { 573 err = GetNode (btreePtr, kHeaderNodeNum, 0, nodePtr); 574 M_ExitOnError (err); 575 576 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode) 577 { 578 err = fsBTInvalidHeaderErr; //�� or fsBTBadNodeType 579 goto ErrorExit; 580 } 581 582 mapIndex = 2; 583 } 584 585 586 *mapPtr = (u_int16_t *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex); 587 *mapSize = GetRecordSize (btreePtr, nodePtr->buffer, mapIndex); 588 589 return noErr; 590 591 592ErrorExit: 593 594 (void) ReleaseNode (btreePtr, nodePtr); 595 596 *mapPtr = nil; 597 *mapSize = 0; 598 599 return err; 600} 601 602 603 604////////////////////////////////// CalcMapBits ////////////////////////////////// 605 606u_int32_t CalcMapBits (BTreeControlBlockPtr btreePtr) 607{ 608 u_int32_t mapBits; 609 610 mapBits = M_HeaderMapRecordSize (btreePtr->nodeSize) << 3; 611 612 while (mapBits < btreePtr->totalNodes) 613 mapBits += M_MapRecordSize (btreePtr->nodeSize) << 3; 614 615 return mapBits; 616} 617