1/* 2 * Copyright (c) 1999 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/* 24 File: BTreeAllocate.c 25 26 Contains: BTree Node Allocation routines for the BTree Module. 27 28 Version: xxx put the technology version here xxx 29 30 Written by: Gordon Sheridan and Bill Bruffey 31 32 Copyright: � 1992-1999 by Apple Computer, Inc., all rights reserved. 33*/ 34 35#include "BTreePrivate.h" 36#include "hfs_endian.h" 37 38///////////////////// Routines Internal To BTreeAllocate.c ////////////////////// 39 40OSStatus GetMapNode (BTreeControlBlockPtr btreePtr, 41 BlockDescriptor *nodePtr, 42 UInt16 **mapPtr, 43 UInt16 *mapSize ); 44 45///////////////////////////////////////////////////////////////////////////////// 46 47/*------------------------------------------------------------------------------- 48 49Routine: AllocateNode - Find Free Node, Mark It Used, and Return Node Number. 50 51Function: Searches the map records for the first free node, marks it "in use" and 52 returns the node number found. This routine should really only be called 53 when we know there are free blocks, otherwise it's just a waste of time. 54 55Note: We have to examine map nodes a word at a time rather than a long word 56 because the External BTree Mgr used map records that were not an integral 57 number of long words. Too bad. In our spare time could develop a more 58 sophisticated algorithm that read map records by long words (and long 59 word aligned) and handled the spare bytes at the beginning and end 60 appropriately. 61 62Input: btreePtr - pointer to control block for BTree file 63 64Output: nodeNum - number of node allocated 65 66 67Result: noErr - success 68 fsBTNoMoreMapNodesErr - no free blocks were found 69 != noErr - failure 70-------------------------------------------------------------------------------*/ 71 72OSStatus AllocateNode (BTreeControlBlockPtr btreePtr, UInt32 *nodeNum) 73{ 74 OSStatus err; 75 BlockDescriptor node; 76 UInt16 *mapPtr, *pos; 77 UInt16 mapSize, size; 78 UInt16 freeWord; 79 UInt16 mask; 80 UInt16 bitOffset; 81 UInt32 nodeNumber; 82 83 84 nodeNumber = 0; // first node number of header map record 85 node.buffer = nil; // clear node.buffer to get header node 86 // - and for ErrorExit 87 88 while (true) 89 { 90 err = GetMapNode (btreePtr, &node, &mapPtr, &mapSize); 91 M_ExitOnError (err); 92 93 //////////////////////// Find Word with Free Bit //////////////////////////// 94 95 pos = mapPtr; 96 size = mapSize; 97 size >>= 1; // convert to number of words 98 //�� assumes mapRecords contain an integral number of words 99 100 while ( size-- ) 101 { 102 if ( *pos++ != 0xFFFF ) // assume test fails, and increment pos 103 break; 104 } 105 106 --pos; // whoa! backup 107 108 if (*pos != 0xFFFF) // hey, we got one! 109 break; 110 111 nodeNumber += mapSize << 3; // covert to number of bits (nodes) 112 } 113 114 ///////////////////////// Find Free Bit in Word ///////////////////////////// 115 116 freeWord = SWAP_BE16 (*pos); 117 bitOffset = 15; 118 mask = 0x8000; 119 120 do { 121 if ( (freeWord & mask) == 0) 122 break; 123 mask >>= 1; 124 } while (--bitOffset); 125 126 ////////////////////// Calculate Free Node Number /////////////////////////// 127 128 nodeNumber += ((pos - mapPtr) << 4) + (15 - bitOffset); // (pos-mapPtr) = # of words! 129 130 131 ///////////////////////// Check for End of Map ////////////////////////////// 132 133 if (nodeNumber >= btreePtr->totalNodes) 134 { 135 err = fsBTFullErr; 136 goto ErrorExit; 137 } 138 139 /////////////////////////// Allocate the Node /////////////////////////////// 140 141 *pos |= SWAP_BE16 (mask); // set the map bit for the node 142 143 err = UpdateNode (btreePtr, &node); 144 M_ExitOnError (err); 145 146 --btreePtr->freeNodes; 147 btreePtr->flags |= kBTHeaderDirty; 148 *nodeNum = nodeNumber; 149 150 return noErr; 151 152////////////////////////////////// Error Exit /////////////////////////////////// 153 154ErrorExit: 155 156 (void) ReleaseNode (btreePtr, &node); 157 *nodeNum = 0; 158 159 return err; 160} 161 162 163 164/*------------------------------------------------------------------------------- 165 166Routine: FreeNode - Clear allocation bit for node. 167 168Function: Finds the bit representing the node specified by nodeNum in the node 169 map and clears the bit. 170 171 172Input: btreePtr - pointer to control block for BTree file 173 nodeNum - number of node to mark free 174 175Output: none 176 177Result: noErr - success 178 fsBTNoMoreMapNodesErr - node number is beyond end of node map 179 != noErr - GetNode or ReleaseNode encountered some difficulty 180-------------------------------------------------------------------------------*/ 181 182OSStatus FreeNode (BTreeControlBlockPtr btreePtr, UInt32 nodeNum) 183{ 184 OSStatus err; 185 BlockDescriptor node; 186 UInt32 nodeIndex; 187 UInt16 mapSize; 188 UInt16 *mapPos; 189 UInt16 bitOffset; 190 191 192 //////////////////////////// Find Map Record //////////////////////////////// 193 nodeIndex = 0; // first node number of header map record 194 node.buffer = nil; // invalidate node.buffer to get header node 195 196 while (nodeNum >= nodeIndex) 197 { 198 err = GetMapNode (btreePtr, &node, &mapPos, &mapSize); 199 M_ExitOnError (err); 200 201 nodeIndex += mapSize << 3; // covert to number of bits (nodes) 202 } 203 204 //////////////////////////// Mark Node Free ///////////////////////////////// 205 206 nodeNum -= (nodeIndex - (mapSize << 3)); // relative to this map record 207 bitOffset = 15 - (nodeNum & 0x0000000F); // last 4 bits are bit offset 208 mapPos += nodeNum >> 4; // point to word containing map bit 209 M_SWAP_BE16_ClearBitNum (*mapPos, bitOffset); // clear it 210 211 err = UpdateNode (btreePtr, &node); 212 M_ExitOnError (err); 213 214 215 ++btreePtr->freeNodes; 216 btreePtr->flags |= kBTHeaderDirty; //�� how about a macro for this 217 218 return noErr; 219 220ErrorExit: 221 222 (void) ReleaseNode (btreePtr, &node); 223 224 return err; 225} 226 227 228 229/*------------------------------------------------------------------------------- 230 231Routine: ExtendBTree - Call FSAgent to extend file, and allocate necessary map nodes. 232 233Function: This routine calls the the FSAgent to extend the end of fork, if necessary, 234 to accomodate the number of nodes requested. It then allocates as many 235 map nodes as are necessary to account for all the nodes in the B*Tree. 236 If newTotalNodes is less than the current number of nodes, no action is 237 taken. 238 239Note: Internal HFS File Manager BTree Module counts on an integral number of 240 long words in map records, although they are not long word aligned. 241 242Input: btreePtr - pointer to control block for BTree file 243 newTotalNodes - total number of nodes the B*Tree is to extended to 244 245Output: none 246 247Result: noErr - success 248 != noErr - failure 249-------------------------------------------------------------------------------*/ 250 251OSStatus ExtendBTree (BTreeControlBlockPtr btreePtr, 252 UInt32 newTotalNodes ) 253{ 254 OSStatus err; 255 SFCB *filePtr; 256 FSSize minEOF, maxEOF; 257 UInt16 nodeSize; 258 UInt32 oldTotalNodes; 259 UInt32 newMapNodes; 260 UInt32 mapBits, totalMapBits; 261 UInt32 recStartBit; 262 UInt32 nodeNum, nextNodeNum; 263 UInt32 firstNewMapNodeNum, lastNewMapNodeNum; 264 BlockDescriptor mapNode, newNode; 265 UInt16 *mapPos; 266 UInt16 *mapStart; 267 UInt16 mapSize; 268 UInt16 mapNodeRecSize; 269 UInt32 bitInWord, bitInRecord; 270 UInt16 mapIndex; 271 272 273 oldTotalNodes = btreePtr->totalNodes; 274 if (newTotalNodes <= oldTotalNodes) // we're done! 275 return noErr; 276 277 nodeSize = btreePtr->nodeSize; 278 filePtr = btreePtr->fcbPtr; 279 280 mapNode.buffer = nil; 281 newNode.buffer = nil; 282 283 mapNodeRecSize = nodeSize - sizeof(BTNodeDescriptor) - 6; // 2 bytes of free space (see note) 284 285 //�� update for proper 64 bit arithmetic!! 286 287 288 //////////////////////// Count Bits In Node Map ///////////////////////////// 289 290 totalMapBits = 0; 291 do { 292 err = GetMapNode (btreePtr, &mapNode, &mapStart, &mapSize); 293 M_ExitOnError (err); 294 295 mapBits = mapSize << 3; // mapSize (in bytes) * 8 296 recStartBit = totalMapBits; // bit number of first bit in map record 297 totalMapBits += mapBits; 298 299 } while ( ((BTNodeDescriptor*)mapNode.buffer)->fLink != 0 ); 300 301 if (DEBUG_BUILD && totalMapBits != CalcMapBits (btreePtr)) 302 Panic ("\pExtendBTree: totalMapBits != CalcMapBits"); 303 304 /////////////////////// Extend LEOF If Necessary //////////////////////////// 305 306 minEOF = (UInt64)newTotalNodes * (UInt64)nodeSize; 307 if ( filePtr->fcbLogicalSize < minEOF ) 308 { 309 maxEOF = 0xFFFFFFFFFFFFFFFFULL; 310 311 err = btreePtr->setEndOfForkProc (btreePtr->fcbPtr, minEOF, maxEOF); 312 M_ExitOnError (err); 313 } 314 315 316 //////////////////// Calc New Total Number Of Nodes ///////////////////////// 317 318 newTotalNodes = filePtr->fcbLogicalSize / nodeSize; //�� hack! 319 //�� do we wish to perform any verification of newTotalNodes at this point? 320 321 btreePtr->totalNodes = newTotalNodes; //�� do we need to update freeNodes here too? 322 323 324 ////////////// Calculate Number Of New Map Nodes Required /////////////////// 325 326 newMapNodes = 0; 327 if (newTotalNodes > totalMapBits) 328 { 329 newMapNodes = (((newTotalNodes - totalMapBits) >> 3) / mapNodeRecSize) + 1; 330 firstNewMapNodeNum = oldTotalNodes; 331 lastNewMapNodeNum = firstNewMapNodeNum + newMapNodes - 1; 332 } 333 else 334 { 335 err = ReleaseNode (btreePtr, &mapNode); 336 M_ExitOnError (err); 337 338 goto Success; 339 } 340 341 342 /////////////////////// Initialize New Map Nodes //////////////////////////// 343 344 ((BTNodeDescriptor*)mapNode.buffer)->fLink = firstNewMapNodeNum; 345 346 nodeNum = firstNewMapNodeNum; 347 while (true) 348 { 349 err = GetNewNode (btreePtr, nodeNum, &newNode); 350 M_ExitOnError (err); 351 352 ((NodeDescPtr)newNode.buffer)->numRecords = 1; 353 ((NodeDescPtr)newNode.buffer)->kind = kBTMapNode; 354 355 // set free space offset 356 *(UInt16 *)((Ptr)newNode.buffer + nodeSize - 4) = nodeSize - 6; 357 358 if (nodeNum++ == lastNewMapNodeNum) 359 break; 360 361 ((BTNodeDescriptor*)newNode.buffer)->fLink = nodeNum; // point to next map node 362 363 err = UpdateNode (btreePtr, &newNode); 364 M_ExitOnError (err); 365 } 366 367 err = UpdateNode (btreePtr, &newNode); 368 M_ExitOnError (err); 369 370 371 ///////////////////// Mark New Map Nodes Allocated ////////////////////////// 372 373 nodeNum = firstNewMapNodeNum; 374 do { 375 bitInRecord = nodeNum - recStartBit; 376 377 while (bitInRecord >= mapBits) 378 { 379 nextNodeNum = ((NodeDescPtr)mapNode.buffer)->fLink; 380 if ( nextNodeNum == 0) 381 { 382 err = fsBTNoMoreMapNodesErr; 383 goto ErrorExit; 384 } 385 386 err = UpdateNode (btreePtr, &mapNode); 387 M_ExitOnError (err); 388 389 err = GetNode (btreePtr, nextNodeNum, &mapNode); 390 M_ExitOnError (err); 391 392 mapIndex = 0; 393 394 mapStart = (UInt16 *) GetRecordAddress (btreePtr, mapNode.buffer, mapIndex); 395 mapSize = GetRecordSize (btreePtr, mapNode.buffer, mapIndex); 396 397 if (DEBUG_BUILD && mapSize != M_MapRecordSize (btreePtr->nodeSize) ) 398 { 399 Panic ("\pExtendBTree: mapSize != M_MapRecordSize"); 400 } 401 402 mapBits = mapSize << 3; // mapSize (in bytes) * 8 403 recStartBit = totalMapBits; // bit number of first bit in map record 404 totalMapBits += mapBits; 405 406 bitInRecord = nodeNum - recStartBit; 407 } 408 409 mapPos = mapStart + ((nodeNum - recStartBit) >> 4); 410 bitInWord = 15 - ((nodeNum - recStartBit) & 0x0000000F); 411 M_SWAP_BE16_SetBitNum (*mapPos, bitInWord); 412 413 ++nodeNum; 414 415 } while (nodeNum <= lastNewMapNodeNum); 416 417 err = UpdateNode (btreePtr, &mapNode); 418 M_ExitOnError (err); 419 420 421 //////////////////////////////// Success //////////////////////////////////// 422 423Success: 424 425 btreePtr->totalNodes = newTotalNodes; 426 btreePtr->freeNodes += (newTotalNodes - oldTotalNodes) - newMapNodes; 427 428 btreePtr->flags |= kBTHeaderDirty; //�� how about a macro for this 429 430 return noErr; 431 432 433 ////////////////////////////// Error Exit /////////////////////////////////// 434 435ErrorExit: 436 437 (void) ReleaseNode (btreePtr, &mapNode); 438 (void) ReleaseNode (btreePtr, &newNode); 439 440 return err; 441} 442 443 444 445/*------------------------------------------------------------------------------- 446 447Routine: GetMapNode - Get the next map node and pointer to the map record. 448 449Function: Given a BlockDescriptor to a map node in nodePtr, GetMapNode releases 450 it and gets the next node. If nodePtr->buffer is nil, then the header 451 node is retrieved. 452 453 454Input: btreePtr - pointer to control block for BTree file 455 nodePtr - pointer to a BlockDescriptor of a map node 456 457Output: nodePtr - pointer to the BlockDescriptor for the next map node 458 mapPtr - pointer to the map record within the map node 459 mapSize - number of bytes in the map record 460 461Result: noErr - success 462 fsBTNoMoreMapNodesErr - we've run out of map nodes 463 fsBTInvalidNodeErr - bad node, or not node type kMapNode 464 != noErr - failure 465-------------------------------------------------------------------------------*/ 466 467OSStatus GetMapNode (BTreeControlBlockPtr btreePtr, 468 BlockDescriptor *nodePtr, 469 UInt16 **mapPtr, 470 UInt16 *mapSize ) 471{ 472 OSStatus err; 473 UInt16 mapIndex; 474 UInt32 nextNodeNum; 475 476 if (nodePtr->buffer != nil) // if iterator is valid... 477 { 478 nextNodeNum = ((NodeDescPtr)nodePtr->buffer)->fLink; 479 if (nextNodeNum == 0) 480 { 481 err = fsBTNoMoreMapNodesErr; 482 goto ErrorExit; 483 } 484 485 err = ReleaseNode (btreePtr, nodePtr); 486 M_ExitOnError (err); 487 488 err = GetNode (btreePtr, nextNodeNum, nodePtr); 489 M_ExitOnError (err); 490 491 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTMapNode) 492 { 493 err = fsBTBadNodeType; 494 goto ErrorExit; 495 } 496 497 ++btreePtr->numMapNodesRead; 498 mapIndex = 0; 499 } else { 500 err = GetNode (btreePtr, kHeaderNodeNum, nodePtr); 501 M_ExitOnError (err); 502 503 if ( ((NodeDescPtr)nodePtr->buffer)->kind != kBTHeaderNode) 504 { 505 err = fsBTInvalidHeaderErr; //�� or fsBTBadNodeType 506 goto ErrorExit; 507 } 508 509 mapIndex = 2; 510 } 511 512 513 *mapPtr = (UInt16 *) GetRecordAddress (btreePtr, nodePtr->buffer, mapIndex); 514 *mapSize = GetRecordSize (btreePtr, nodePtr->buffer, mapIndex); 515 516 return noErr; 517 518 519ErrorExit: 520 521 (void) ReleaseNode (btreePtr, nodePtr); 522 523 *mapPtr = nil; 524 *mapSize = 0; 525 526 return err; 527} 528 529 530 531////////////////////////////////// CalcMapBits ////////////////////////////////// 532 533UInt32 CalcMapBits (BTreeControlBlockPtr btreePtr) 534{ 535 UInt32 mapBits; 536 537 mapBits = M_HeaderMapRecordSize (btreePtr->nodeSize) << 3; 538 539 while (mapBits < btreePtr->totalNodes) 540 mapBits += M_MapRecordSize (btreePtr->nodeSize) << 3; 541 542 return mapBits; 543} 544