1/* 2 * Copyright (c) 2000-2002, 2004-2011 Apple 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/* Summary for in-memory volume bitmap: 25 * A binary search tree is used to store bitmap segments that are 26 * partially full. If a segment does not exist in the tree, it 27 * can be assumed to be in the following state: 28 * 1. Full if the coresponding segment map bit is set 29 * 2. Empty (implied) 30 */ 31 32#include "Scavenger.h" 33 34#include <sys/disk.h> 35 36#include <bitstring.h> 37 38#define bit_dealloc(p) free(p) 39 40#define _VBC_DEBUG_ 0 41 42enum { 43 kBitsPerByte = 8, 44 kBitsPerWord = 32, 45 kBitsPerSegment = 1024, 46 kBytesPerSegment = kBitsPerSegment / kBitsPerByte, 47 kWordsPerSegment = kBitsPerSegment / kBitsPerWord, 48 49 kBitsWithinWordMask = kBitsPerWord-1, 50 kBitsWithinSegmentMask = kBitsPerSegment-1, 51 52 kBMS_NodesPerPool = 450, 53 kBMS_PoolMax = 2000 54}; 55 56 57#define kAllBitsSetInWord 0xFFFFFFFFu 58#define kMSBBitSetInWord 0x80000000u 59 60enum { 61 kSettingBits = 1, 62 kClearingBits = 2, 63 kTestingBits = 3 64}; 65 66#define kEmptySegment 0 67#define kFullSegment 1 68 69int gBitMapInited = 0; 70 71/* 72 * Bitmap segments that are full are marked in 73 * the gFullSegmentList (a bit string). 74 */ 75bitstr_t* gFullSegmentList; 76UInt32 gBitsMarked; 77UInt32 gTotalBits; 78UInt32 gTotalSegments; 79UInt32* gFullBitmapSegment; /* points to a FULL bitmap segment*/ 80UInt32* gEmptyBitmapSegment; /* points to an EMPTY bitmap segment*/ 81 82/* 83 * Bitmap Segment (BMS) Tree node 84 * Bitmap segments that are partially full are 85 * saved in the BMS Tree. 86 */ 87typedef struct BMS_Node { 88 struct BMS_Node *left; 89 struct BMS_Node *right; 90 UInt32 segment; 91 UInt32 bitmap[kWordsPerSegment]; 92} BMS_Node; 93 94BMS_Node *gBMS_Root; /* root of BMS tree */ 95BMS_Node *gBMS_FreeNodes; /* list of free BMS nodes */ 96BMS_Node *gBMS_PoolList[kBMS_PoolMax]; /* list of BMS node pools */ 97int gBMS_PoolCount; /* count of pools allocated */ 98 99/* Bitmap operations routines */ 100static int FindContigClearedBitmapBits (SVCB *vcb, UInt32 numBlocks, UInt32 *actualStartBlock); 101 102/* Segment Tree routines (binary search tree) */ 103static int BMS_InitTree(void); 104static int BMS_DisposeTree(void); 105static BMS_Node * BMS_Lookup(UInt32 segment); 106static BMS_Node * BMS_Insert(UInt32 segment, int segmentType); 107static BMS_Node * BMS_Delete(UInt32 segment); 108static void BMS_GrowNodePool(void); 109 110#if _VBC_DEBUG_ 111static void BMS_PrintTree(BMS_Node * root); 112static void BMS_MaxDepth(BMS_Node * root, int depth, int *maxdepth); 113#endif 114 115/* 116 * Initialize our volume bitmap data structures 117 */ 118int BitMapCheckBegin(SGlobPtr g) 119{ 120 Boolean isHFSPlus; 121 122 if (gBitMapInited) 123 return (0); 124 125 isHFSPlus = VolumeObjectIsHFSPlus( ); 126 127 gFullBitmapSegment = (UInt32 *)malloc(kBytesPerSegment); 128 memset((void *)gFullBitmapSegment, 0xff, kBytesPerSegment); 129 130 gEmptyBitmapSegment = (UInt32 *)malloc(kBytesPerSegment); 131 memset((void *)gEmptyBitmapSegment, 0x00, kBytesPerSegment); 132 133 gTotalBits = g->calculatedVCB->vcbTotalBlocks; 134 gTotalSegments = (gTotalBits / kBitsPerSegment); 135 if (gTotalBits % kBitsPerSegment) 136 ++gTotalSegments; 137 138 gFullSegmentList = bit_alloc(gTotalSegments); 139 bit_nclear(gFullSegmentList, 0, gTotalSegments - 1); 140 141 BMS_InitTree(); 142 gBitMapInited = 1; 143 gBitsMarked = 0; 144 145 if (isHFSPlus) { 146 UInt16 alignBits; 147 148 /* 149 * Allocate the VolumeHeader in the volume bitmap. 150 * Since the VH is the 3rd sector in we may need to 151 * add some alignment allocation blocks before it. 152 */ 153 if (g->calculatedVCB->vcbBlockSize == 512) 154 alignBits = 2; 155 else if (g->calculatedVCB->vcbBlockSize == 1024) 156 alignBits = 1; 157 else 158 alignBits = 0; 159 160 (void) CaptureBitmapBits(0, 1 + alignBits); 161 162 if (g->calculatedVCB->vcbBlockSize == 512) 163 alignBits = 1; 164 else 165 alignBits = 0; 166 167 (void) CaptureBitmapBits(gTotalBits - 1 - alignBits, 1 + alignBits); 168 } 169 170 return (0); 171} 172 173/* debugging stats */ 174int gFullSegments = 0; 175int gSegmentNodes = 0; 176 177int BitMapCheckEnd(void) 178{ 179 if (gBitMapInited) { 180#if _VBC_DEBUG_ 181 int maxdepth = 0; 182 183 BMS_MaxDepth(gBMS_Root, 0, &maxdepth); 184 plog(" %d full segments, %d segment nodes (max depth was %d nodes)\n", 185 gFullSegments, gSegmentNodes, maxdepth); 186#endif 187 free(gFullBitmapSegment); 188 gFullBitmapSegment = NULL; 189 190 free(gEmptyBitmapSegment); 191 gEmptyBitmapSegment = NULL; 192 193 bit_dealloc(gFullSegmentList); 194 gFullSegmentList = NULL; 195 196 BMS_DisposeTree(); 197 gBitMapInited = 0; 198 } 199 return (0); 200} 201 202/* Function: GetSegmentBitmap 203 * 204 * Description: Return bitmap segment corresponding to given startBit. 205 * 206 * 1. Calculate the segment number for given bit. 207 * 2. If the segment exists in full segment list, 208 * If bitOperation is to clear bits, 209 * a. Remove segment from full segment list. 210 * b. Insert a full segment in the bitmap tree. 211 * Else return pointer to dummy full segment 212 * 3. If segment found in tree, it is partially full. Return it. 213 * 4. If (2) and (3) are not true, it is a empty segment. 214 * If bitOperation is to set bits, 215 * a. Insert empty segment in the bitmap tree. 216 * Else return pointer to dummy empty segment. 217 * 218 * Input: 219 * 1. startBit - bit number (block number) to lookup 220 * 2. buffer - pointer to return pointer to bitmap segment 221 * 3. bitOperation - intent for new segment 222 * kSettingBits - caller wants to set bits 223 * kClearingBits - caller wants to clear bits 224 * kTestingBits - caller wants to test bits. 225 * 226 * Output: 227 * 1. buffer - pointer to desired segment 228 * returns zero on success, -1 on failure. 229 */ 230static int GetSegmentBitmap(UInt32 startBit, UInt32 **buffer, int bitOperation) 231{ 232 UInt32 segment; 233 BMS_Node *segNode = NULL; 234 235 *buffer = NULL; 236 segment = startBit / kBitsPerSegment; 237 238 // for a full seqment... 239 if (bit_test(gFullSegmentList, segment)) { 240 if (bitOperation == kClearingBits) { 241 bit_clear(gFullSegmentList, segment); 242 --gFullSegments; 243 if ((segNode = BMS_Insert(segment, kFullSegment)) != NULL) 244 *buffer = &segNode->bitmap[0]; 245 } else 246 *buffer = gFullBitmapSegment; 247 248 // for a partially full segment.. 249 } else if ((segNode = BMS_Lookup(segment)) != NULL) { 250 *buffer = &segNode->bitmap[0]; 251 252 // for an empty segment... 253 } else { 254 if (bitOperation == kSettingBits) { 255 if ((segNode = BMS_Insert(segment, kEmptySegment)) != NULL) 256 *buffer = &segNode->bitmap[0]; 257 } else 258 *buffer = gEmptyBitmapSegment; 259 } 260 261 if (*buffer == NULL) { 262#if _VBC_DEBUG_ 263 plog("GetSegmentBitmap: couldn't get a node for block %d, segment %d\n", startBit, segment); 264#endif 265 return (-1); /* oops */ 266 } 267 268#if 0 269 if (segNode) { 270 int i; 271 plog(" segment %d: L=0x%08x, R=0x%08x \n< ", 272 (int)segNode->segment, (int)segNode->left, segNode->right); 273 for (i = 0; i < kWordsPerSegment; ++i) { 274 plog("0x%08x ", segNode->bitmap[i]); 275 if ((i & 0x3) == 0x3) 276 plog("\n "); 277 } 278 plog("\n"); 279 } 280 281 if (bitOperation == kSettingBits && *buffer && bcmp(*buffer, gFullBitmapSegment, kBytesPerSegment) == 0) { 282 plog("*** segment %d (start blk %d) is already full!\n", segment, startBit); 283 exit(5); 284 } 285 if (bitOperation == kClearingBits && *buffer && bcmp(*buffer, gEmptyBitmapSegment, kBytesPerSegment) == 0) { 286 plog("*** segment %d (start blk %d) is already empty!\n", segment, startBit); 287 exit(5); 288 } 289#endif 290 291 return (0); 292} 293 294/* Function: TestSegmentBitmap 295 * 296 * Description: Test if the current bitmap segment is a full 297 * segment or empty segment. 298 * If full segment, delete the segment, set corresponding full segment 299 * bit in gFullSegmentList, and update counters. 300 * If empty list, delete the segment from list. Note that we update 301 * the counter only for debugging purposes. 302 * 303 * Input: 304 * startBit - startBit of segment to test 305 * 306 * Output: 307 * nothing (void). 308 */ 309void TestSegmentBitmap(UInt32 startBit) 310{ 311 UInt32 segment; 312 BMS_Node *segNode = NULL; 313 314 segment = startBit / kBitsPerSegment; 315 316 if (bit_test(gFullSegmentList, segment)) 317 return; 318 319 if ((segNode = BMS_Lookup(segment)) != NULL) { 320#if 0 321 int i; 322 plog("> "); 323 for (i = 0; i < kWordsPerSegment; ++i) { 324 plog("0x%08x ", segNode->bitmap[i]); 325 if ((i & 0x3) == 0x3) 326 plog("\n "); 327 } 328 plog("\n"); 329#endif 330 if (segment != 0 && bcmp(&segNode->bitmap[0], gFullBitmapSegment, kBytesPerSegment) == 0) { 331 if (BMS_Delete(segment) != NULL) { 332 bit_set(gFullSegmentList, segment); 333 /* debugging stats */ 334 ++gFullSegments; 335 --gSegmentNodes; 336 } 337 } 338 339 if (segment != 0 && bcmp(&segNode->bitmap[0], gEmptyBitmapSegment, kBytesPerSegment) == 0) { 340 if (BMS_Delete(segment) != NULL) { 341 /* debugging stats */ 342 --gSegmentNodes; 343 } 344 } 345 } 346} 347 348 349/* Function: CaptureBitmapBits 350 * 351 * Description: Set bits in the segmented bitmap from startBit upto 352 * bitCount bits. 353 * 354 * Note: This function is independent of the previous state of the bit 355 * to be set. Therefore single bit can be set multiple times. Setting a 356 * bit multiple times might result in incorrect total number of blocks used 357 * (which can be corrected using UpdateFreeBlockCount function). 358 * 359 * 1. Increment gBitsMarked with bitCount. 360 * 2. If first bit does not start on word boundary, special case it. 361 * 3. Set all whole words. 362 * 4. If not all bits in last word need to be set, special case it. 363 * 5. For 2, 3, and 4, call TestSegmentBitmap after writing one segment or 364 * setting all bits to optimize full and empty segment list. 365 * 366 * Input: 367 * startBit - bit number in segment bitmap to start set operation. 368 * bitCount - total number of bits to set. 369 * 370 * Output: 371 * zero on success, non-zero on failure. 372 * This function also returns E_OvlExt if any overlapping extent is found. 373 */ 374int CaptureBitmapBits(UInt32 startBit, UInt32 bitCount) 375{ 376 Boolean overlap; 377 OSErr err; 378 UInt32 wordsLeft; 379 UInt32 bitMask; 380 UInt32 firstBit; 381 UInt32 numBits; 382 UInt32 *buffer; 383 UInt32 *currentWord; 384 385 overlap = false; 386 if (bitCount == 0) 387 return (0); 388 389 if ((startBit + bitCount) > gTotalBits) { 390 err = vcInvalidExtentErr; 391 goto Exit; 392 } 393 394 /* count allocated bits */ 395 gBitsMarked += bitCount; 396 397 /* 398 * Get the bitmap segment containing the first word to check 399 */ 400 err = GetSegmentBitmap(startBit, &buffer, kSettingBits); 401 if (err != noErr) goto Exit; 402 403 /* Initialize buffer stuff */ 404 { 405 UInt32 wordIndexInSegment; 406 407 wordIndexInSegment = (startBit & kBitsWithinSegmentMask) / kBitsPerWord; 408 currentWord = buffer + wordIndexInSegment; 409 wordsLeft = kWordsPerSegment - wordIndexInSegment; 410 } 411 412 /* 413 * If the first bit to check doesn't start on a word 414 * boundary in the bitmap, then treat that first word 415 * specially. 416 */ 417 firstBit = startBit % kBitsPerWord; 418 if (firstBit != 0) { 419 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit 420 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word 421 if (numBits > bitCount) { 422 numBits = bitCount; // entire allocation is inside this one word 423 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last 424 } 425 426 if (SWAP_BE32(*currentWord) & bitMask) { 427 overlap = true; 428 429 //plog("(1) overlapping file blocks! word: 0x%08x, mask: 0x%08x\n", *currentWord, bitMask); 430 } 431 432 *currentWord |= SWAP_BE32(bitMask); /* set the bits in the bitmap */ 433 434 bitCount -= numBits; 435 ++currentWord; 436 --wordsLeft; 437 if (wordsLeft == 0 || bitCount == 0) 438 TestSegmentBitmap(startBit); 439 } 440 441 /* 442 * Set whole words (32 bits) at a time. 443 */ 444 bitMask = kAllBitsSetInWord; 445 while (bitCount >= kBitsPerWord) { 446 /* See if it's time to move to the next bitmap segment */ 447 if (wordsLeft == 0) { 448 startBit += kBitsPerSegment; // generate a bit in the next bitmap segment 449 450 err = GetSegmentBitmap(startBit, &buffer, kSettingBits); 451 if (err != noErr) goto Exit; 452 453 // Readjust currentWord, wordsLeft 454 currentWord = buffer; 455 wordsLeft = kWordsPerSegment; 456 } 457 458 if (SWAP_BE32(*currentWord) & bitMask) { 459 overlap = true; 460 461 //plog("(2) overlapping file blocks! word: 0x%08x, mask: 0x%08x\n", *currentWord, bitMask); 462 } 463 464 *currentWord |= SWAP_BE32(bitMask); /* set the bits in the bitmap */ 465 466 bitCount -= kBitsPerWord; 467 ++currentWord; 468 --wordsLeft; 469 if (wordsLeft == 0 || bitCount == 0) 470 TestSegmentBitmap(startBit); 471 } 472 473 /* 474 * Check any remaining bits. 475 */ 476 if (bitCount != 0) { 477 bitMask = ~(kAllBitsSetInWord >> bitCount); // set first bitCount bits 478 if (wordsLeft == 0) { 479 startBit += kBitsPerSegment; 480 481 err = GetSegmentBitmap(startBit, &buffer, kSettingBits); 482 if (err != noErr) goto Exit; 483 484 currentWord = buffer; 485 wordsLeft = kWordsPerSegment; 486 } 487 488 if (SWAP_BE32(*currentWord) & bitMask) { 489 overlap = true; 490 491 //plog("(3) overlapping file blocks! word: 0x%08x, mask: 0x%08x\n", *currentWord, bitMask); 492 } 493 494 *currentWord |= SWAP_BE32(bitMask); /* set the bits in the bitmap */ 495 496 TestSegmentBitmap(startBit); 497 } 498Exit: 499 return (overlap ? E_OvlExt : err); 500} 501 502 503/* Function: ReleaseBitMapBits 504 * 505 * Description: Clear bits in the segmented bitmap from startBit upto 506 * bitCount bits. 507 * 508 * Note: This function is independent of the previous state of the bit 509 * to clear. Therefore single bit can be cleared multiple times. Clearing a 510 * bit multiple times might result in incorrect total number of blocks used 511 * (which can be corrected using UpdateFreeBlockCount function). 512 * 513 * 1. Decrement gBitsMarked with bitCount. 514 * 2. If first bit does not start on word boundary, special case it. 515 * 3. Clear all whole words. 516 * 4. If partial bits in last word needs to be cleared, special case it. 517 * 5. For 2, 3, and 4, call TestSegmentBitmap after writing one segment or 518 * clearing all bits to optimize full and empty segment list. 519 * 520 * Input: 521 * startBit - bit number in segment bitmap to start clear operation. 522 * bitCount - total number of bits to clear. 523 * 524 * Output: 525 * zero on success, non-zero on failure. 526 * This function also returns E_OvlExt if any overlapping extent is found. 527 */ 528int ReleaseBitmapBits(UInt32 startBit, UInt32 bitCount) 529{ 530 Boolean overlap; 531 OSErr err; 532 UInt32 wordsLeft; 533 UInt32 bitMask; 534 UInt32 firstBit; 535 UInt32 numBits; 536 UInt32 *buffer; 537 UInt32 *currentWord; 538 539 overlap = false; 540 if (bitCount == 0) 541 return (0); 542 543 if ((startBit + bitCount) > gTotalBits) { 544 err = vcInvalidExtentErr; 545 goto Exit; 546 } 547 548 /* decrment allocated bits */ 549 gBitsMarked -= bitCount; 550 551 /* 552 * Get the bitmap segment containing the first word to check 553 */ 554 err = GetSegmentBitmap(startBit, &buffer, kClearingBits); 555 if (err != noErr) goto Exit; 556 557 /* Initialize buffer stuff */ 558 { 559 UInt32 wordIndexInSegment; 560 561 wordIndexInSegment = (startBit & kBitsWithinSegmentMask) / kBitsPerWord; 562 currentWord = buffer + wordIndexInSegment; 563 wordsLeft = kWordsPerSegment - wordIndexInSegment; 564 } 565 566 /* 567 * If the first bit to check doesn't start on a word 568 * boundary in the bitmap, then treat that first word 569 * specially. 570 */ 571 firstBit = startBit % kBitsPerWord; 572 if (firstBit != 0) { 573 bitMask = kAllBitsSetInWord >> firstBit; // turn off all bits before firstBit 574 numBits = kBitsPerWord - firstBit; // number of remaining bits in this word 575 if (numBits > bitCount) { 576 numBits = bitCount; // entire deallocation is inside this one word 577 bitMask &= ~(kAllBitsSetInWord >> (firstBit + numBits)); // turn off bits after last 578 } 579 580 if ((SWAP_BE32(*currentWord) & bitMask) != bitMask) { 581 overlap = true; 582 583 //plog("(1) overlapping file blocks! word: 0x%08x, mask: 0x%08x\n", *currentWord, bitMask); 584 } 585 586 *currentWord &= SWAP_BE32(~bitMask); /* clear the bits in the bitmap */ 587 588 bitCount -= numBits; 589 ++currentWord; 590 --wordsLeft; 591 if (wordsLeft == 0 || bitCount == 0) 592 TestSegmentBitmap(startBit); 593 } 594 595 /* 596 * Clear whole words (32 bits) at a time. 597 */ 598 bitMask = kAllBitsSetInWord; 599 while (bitCount >= kBitsPerWord) { 600 /* See if it's time to move to the next bitmap segment */ 601 if (wordsLeft == 0) { 602 startBit += kBitsPerSegment; // generate a bit in the next bitmap segment 603 604 err = GetSegmentBitmap(startBit, &buffer, kClearingBits); 605 if (err != noErr) goto Exit; 606 607 // Readjust currentWord, wordsLeft 608 currentWord = buffer; 609 wordsLeft = kWordsPerSegment; 610 } 611 612 if ((SWAP_BE32(*currentWord) & bitMask) != bitMask) { 613 overlap = true; 614 615 //plog("(2) overlapping file blocks! word: 0x%08x, mask: 0x%08x\n", *currentWord, bitMask); 616 } 617 618 *currentWord &= SWAP_BE32(~bitMask); /* clear the bits in the bitmap */ 619 620 bitCount -= kBitsPerWord; 621 ++currentWord; 622 --wordsLeft; 623 if (wordsLeft == 0 || bitCount == 0) 624 TestSegmentBitmap(startBit); 625 } 626 627 /* 628 * Check any remaining bits. 629 */ 630 if (bitCount != 0) { 631 bitMask = ~(kAllBitsSetInWord >> bitCount); // set first bitCount bits 632 if (wordsLeft == 0) { 633 startBit += kBitsPerSegment; 634 635 err = GetSegmentBitmap(startBit, &buffer, kClearingBits); 636 if (err != noErr) goto Exit; 637 638 currentWord = buffer; 639 wordsLeft = kWordsPerSegment; 640 } 641 642 if ((SWAP_BE32(*currentWord) & bitMask) != bitMask) { 643 overlap = true; 644 645 //plog("(3) overlapping file blocks! word: 0x%08x, mask: 0x%08x\n", *currentWord, bitMask); 646 } 647 648 *currentWord &= SWAP_BE32(~bitMask); /* set the bits in the bitmap */ 649 650 TestSegmentBitmap(startBit); 651 } 652Exit: 653 return (overlap ? E_OvlExt : err); 654} 655 656/* Function: CheckVolumeBitMap 657 * 658 * Description: Compares the in-memory volume bitmap with the on-disk 659 * volume bitmap. 660 * If repair is true, update the on-disk bitmap with the in-memory bitmap. 661 * If repair is false and the bitmaps don't match, an error message is 662 * printed and check stops. 663 * 664 * Input: 665 * 1. g - global scavenger structure 666 * 2. repair - indicate if a repair operation is requested or not. 667 * 668 * Output: 669 * zero on success, non-zero on failure. 670 */ 671int CheckVolumeBitMap(SGlobPtr g, Boolean repair) 672{ 673 UInt8 *vbmBlockP; 674 UInt32 *buffer; 675 UInt64 bit; /* 64-bit to avoid wrap around on volumes with 2^32 - 1 blocks */ 676 UInt32 bitsWithinFileBlkMask; 677 UInt32 fileBlk; 678 BlockDescriptor block; 679 ReleaseBlockOptions relOpt; 680 SFCB * fcb; 681 SVCB * vcb; 682 Boolean isHFSPlus; 683 Boolean foundOverAlloc = false; 684 int err = 0; 685 686 vcb = g->calculatedVCB; 687 fcb = g->calculatedAllocationsFCB; 688 isHFSPlus = VolumeObjectIsHFSPlus( ); 689 690 if ( vcb->vcbFreeBlocks != (vcb->vcbTotalBlocks - gBitsMarked) ) { 691 vcb->vcbFreeBlocks = vcb->vcbTotalBlocks - gBitsMarked; 692 MarkVCBDirty(vcb); 693 } 694 695 vbmBlockP = (UInt8 *)NULL; 696 block.buffer = (void *)NULL; 697 relOpt = kReleaseBlock; 698 if ( isHFSPlus ) 699 bitsWithinFileBlkMask = (fcb->fcbBlockSize * 8) - 1; 700 else 701 bitsWithinFileBlkMask = (kHFSBlockSize * 8) - 1; 702 fileBlk = (isHFSPlus ? 0 : vcb->vcbVBMSt); 703 704 /* 705 * Loop through all the bitmap segments and compare 706 * them against the on-disk bitmap. 707 */ 708 for (bit = 0; bit < gTotalBits; bit += kBitsPerSegment) { 709 (void) GetSegmentBitmap(bit, &buffer, kTestingBits); 710 711 /* 712 * When we cross file block boundries read a new block from disk. 713 */ 714 if ((bit & bitsWithinFileBlkMask) == 0) { 715 if (isHFSPlus) { 716 if (block.buffer) { 717 err = ReleaseFileBlock(fcb, &block, relOpt); 718 ReturnIfError(err); 719 } 720 err = GetFileBlock(fcb, fileBlk, kGetBlock, &block); 721 } else /* plain HFS */ { 722 if (block.buffer) { 723 err = ReleaseVolumeBlock(vcb, &block, relOpt | kSkipEndianSwap); 724 ReturnIfError(err); 725 } 726 err = GetVolumeBlock(vcb, fileBlk, kGetBlock | kSkipEndianSwap, &block); 727 } 728 ReturnIfError(err); 729 730 vbmBlockP = (UInt8 *) block.buffer; 731 relOpt = kReleaseBlock; 732 g->TarBlock = fileBlk; 733 ++fileBlk; 734 } 735 if (memcmp(buffer, vbmBlockP + (bit & bitsWithinFileBlkMask)/8, kBytesPerSegment) == 0) 736 continue; 737 738 if (repair) { 739 bcopy(buffer, vbmBlockP + (bit & bitsWithinFileBlkMask)/8, kBytesPerSegment); 740 relOpt = kForceWriteBlock; 741 } else { 742 int underalloc = 0; 743 int indx; 744#if _VBC_DEBUG_ 745 int i, j; 746 UInt32 *disk_buffer; 747 UInt32 dummy, block_num; 748 749 plog(" disk buffer + %d\n", (bit & bitsWithinFileBlkMask)/8); 750 plog("start block number for segment = %qu\n", bit); 751 plog("segment %qd\n", bit / kBitsPerSegment); 752 753 plog("Memory:\n"); 754 for (i = 0; i < kWordsPerSegment; ++i) { 755 plog("0x%08x ", buffer[i]); 756 if ((i & 0x7) == 0x7) 757 plog("\n"); 758 } 759 760 disk_buffer = (UInt32*) (vbmBlockP + (bit & bitsWithinFileBlkMask)/8); 761 plog("Disk:\n"); 762 for (i = 0; i < kWordsPerSegment; ++i) { 763 plog("0x%08x ", disk_buffer[i]); 764 if ((i & 0x7) == 0x7) 765 plog("\n"); 766 } 767 768 plog ("\n"); 769 for (i = 0; i < kWordsPerSegment; ++i) { 770 /* Compare each word in the segment */ 771 if (buffer[i] != disk_buffer[i]) { 772 dummy = 0x80000000; 773 /* If two words are different, compare each bit in the word */ 774 for (j = 0; j < kBitsPerWord; ++j) { 775 /* If two bits are different, calculate allocation block number */ 776 if ((buffer[i] & dummy) != (disk_buffer[i] & dummy)) { 777 block_num = bit + (i * kBitsPerWord) + j; 778 if (buffer[i] & dummy) { 779 plog ("Allocation block %u should be marked used on disk.\n", block_num); 780 } else { 781 plog ("Allocation block %u should be marked free on disk.\n", block_num); 782 } 783 } 784 dummy = dummy >> 1; 785 } 786 } 787 } 788#endif 789 /* 790 * We have at least one difference. If we have over-allocated (that is, the 791 * volume bitmap says a block is allocated, but our counts say it isn't), then 792 * this is a lessor error. If we've under-allocated (that is, the volume bitmap 793 * says a block is available, but our counts say it is in use), then this is a 794 * bigger problem -- it can lead to overlapping extents. 795 * 796 * Once we determine we have under-allocated, we can just stop and print out 797 * the message. 798 */ 799 for (indx = 0; indx < kBytesPerSegment; indx++) { 800 uint8_t *bufp, *diskp; 801 bufp = (uint8_t *)buffer; 802 diskp = vbmBlockP + (bit & bitsWithinFileBlkMask)/8; 803 if (bufp[indx] & ~diskp[indx]) { 804 underalloc++; 805 break; 806 } 807 } 808 g->VIStat = g->VIStat | S_VBM; 809 if (underalloc) { 810 fsckPrint(g->context, E_VBMDamaged); 811 break; /* stop checking after first miss */ 812 } else if (!foundOverAlloc) { 813 /* Only print out a message on the first find */ 814 fsckPrint(g->context, E_VBMDamagedOverAlloc); 815 foundOverAlloc = true; 816 } 817 } 818 ++g->itemsProcessed; 819 } 820 821 if (block.buffer) { 822 if (isHFSPlus) 823 (void) ReleaseFileBlock(fcb, &block, relOpt); 824 else 825 (void) ReleaseVolumeBlock(vcb, &block, relOpt | kSkipEndianSwap); 826 } 827 828 return (0); 829} 830 831/* Function: UpdateFreeBlockCount 832 * 833 * Description: Re-calculate the total bits marked in in-memory bitmap 834 * by traversing the entire bitmap. Update the total number of bits set in 835 * the in-memory volume bitmap and the volume free block count. 836 * 837 * All the bits representing the blocks that are beyond total allocation 838 * blocks of the volume are intialized to zero in the last bitmap segment. 839 * This function checks for bits marked, therefore we do not special case 840 * the last bitmap segment. 841 * 842 * Input: 843 * g - global scavenger structure pointer. 844 * 845 * Output: 846 * nothing (void) 847 */ 848void UpdateFreeBlockCount(SGlobPtr g) 849{ 850 int i; 851 UInt32 newBitsMarked = 0; 852 UInt32 bit; 853 UInt32 *buffer; 854 UInt32 curWord; 855 SVCB * vcb = g->calculatedVCB; 856 857 /* Loop through all the bitmap segments */ 858 for (bit = 0; bit < gTotalBits; bit += kBitsPerSegment) { 859 (void) GetSegmentBitmap(bit, &buffer, kTestingBits); 860 861 /* All bits in segment are set */ 862 if (buffer == gFullBitmapSegment) { 863 newBitsMarked += kBitsPerSegment; 864 continue; 865 } 866 867 /* All bits in segment are clear */ 868 if (buffer == gEmptyBitmapSegment) { 869 continue; 870 } 871 872 /* Segment is partially full */ 873 for (i = 0; i < kWordsPerSegment; i++) { 874 if (buffer[i] == kAllBitsSetInWord) { 875 newBitsMarked += kBitsPerWord; 876 } else { 877 curWord = SWAP_BE32(buffer[i]); 878 while (curWord) { 879 newBitsMarked += curWord & 1; 880 curWord >>= 1; 881 } 882 } 883 } 884 } 885 886 /* Update total bits marked count for in-memory bitmap */ 887 if (gBitsMarked != newBitsMarked) { 888 gBitsMarked = newBitsMarked; 889 } 890 891 /* Update volume free block count */ 892 if (vcb->vcbFreeBlocks != (vcb->vcbTotalBlocks - gBitsMarked)) { 893 vcb->vcbFreeBlocks = vcb->vcbTotalBlocks - gBitsMarked; 894 MarkVCBDirty(vcb); 895 } 896} 897 898/* Function: FindContigClearedBitmapBits 899 * 900 * Description: Find contigous free bitmap bits (allocation blocks) from 901 * the in-memory volume bitmap. If found, the bits are not marked as 902 * used. 903 * 904 * The function traverses the entire in-memory volume bitmap. It keeps 905 * a count of contigous cleared bits and the first cleared bit seen in 906 * the current sequence. 907 * If it sees a set bit, it re-intializes the count to the number of 908 * blocks to be found and first cleared bit as zero. 909 * If it sees a cleared bit, it decrements the count of number of blocks 910 * to be found cleared. If the first cleared bit was set to zero, 911 * it initializes it with the current bit. If the count of number 912 * of blocks becomes zero, the function returns. 913 * 914 * The function takes care if the last bitmap segment is paritally used 915 * to represented the total number of allocation blocks. 916 * 917 * Input: 918 * 1. vcb - pointer to volume information 919 * 2. numBlocks - number of free contigous blocks 920 * 3. actualStartBlock - pointer to return the start block, if contigous 921 * free blocks found. 922 * 923 * Output: 924 * 1. actualStartBlock - pointer to return the start block, if contigous 925 * free blocks found. 926 * On success, returns zero. 927 * On failure, non-zero value 928 * ENOSPC - No contigous free blocks were found of given length 929 */ 930static int FindContigClearedBitmapBits (SVCB *vcb, UInt32 numBlocks, UInt32 *actualStartBlock) 931{ 932 int i, j; 933 int retval = ENOSPC; 934 UInt32 bit; 935 UInt32 *buffer; 936 UInt32 curWord; 937 UInt32 validBitsInSegment; /* valid bits remaining (considering totalBits) in segment */ 938 UInt32 validBitsInWord; /* valid bits remaining (considering totalBits) in word */ 939 UInt32 bitsRemain = numBlocks; /* total free bits more to search */ 940 UInt32 startBlock = 0; /* start bit for free bits sequence */ 941 942 /* For all segments except the last segments, number of valid bits 943 * is always total number of bits represented by the segment 944 */ 945 validBitsInSegment = kBitsPerSegment; 946 947 /* For all words except the last word, the number of valid bits 948 * is always total number of bits represented by the word 949 */ 950 validBitsInWord = kBitsPerWord; 951 952 /* Loop through all the bitmap segments */ 953 for (bit = 0; bit < gTotalBits; bit += kBitsPerSegment) { 954 (void) GetSegmentBitmap(bit, &buffer, kTestingBits); 955 956 /* If this is last segment, calculate valid bits remaining */ 957 if ((gTotalBits - bit) < kBitsPerSegment) { 958 validBitsInSegment = gTotalBits - bit; 959 } 960 961 /* All bits in segment are set */ 962 if (buffer == gFullBitmapSegment) { 963 /* Reset our counters */ 964 startBlock = 0; 965 bitsRemain = numBlocks; 966 continue; 967 } 968 969 /* All bits in segment are clear */ 970 if (buffer == gEmptyBitmapSegment) { 971 /* If startBlock is not initialized, initialize it */ 972 if (bitsRemain == numBlocks) { 973 startBlock = bit; 974 } 975 /* If the total number of required free blocks is greater than 976 * total number of blocks represented in one free segment, include 977 * entire segment in our count 978 * If the total number of required free blocks is less than the 979 * total number of blocks represented in one free segment, include 980 * only the remaining free blocks in the count and break out. 981 */ 982 if (bitsRemain > validBitsInSegment) { 983 bitsRemain -= validBitsInSegment; 984 continue; 985 } else { 986 bitsRemain = 0; 987 break; 988 } 989 } 990 991 /* Segment is partially full */ 992 for (i = 0; i < kWordsPerSegment; i++) { 993 /* All bits in a word are set */ 994 if (buffer[i] == kAllBitsSetInWord) { 995 /* Reset our counters */ 996 startBlock = 0; 997 bitsRemain = numBlocks; 998 } else { 999 /* Not all bits in a word are set */ 1000 1001 /* If this is the last segment, check if the current word 1002 * is the last word containing valid bits. 1003 */ 1004 if (validBitsInSegment != kBitsPerSegment) { 1005 if ((validBitsInSegment - (i * kBitsPerWord)) < kBitsPerWord) { 1006 /* Calculate the total valid bits in last word */ 1007 validBitsInWord = validBitsInSegment - (i * kBitsPerWord); 1008 } 1009 } 1010 1011 curWord = SWAP_BE32(buffer[i]); 1012 /* Check every bit in the word */ 1013 for (j = 0; j < validBitsInWord; j++) { 1014 if (curWord & kMSBBitSetInWord) { 1015 /* The bit is set, reset our counters */ 1016 startBlock = 0; 1017 bitsRemain = numBlocks; 1018 } else { 1019 /* The bit is clear */ 1020 if (bitsRemain == numBlocks) { 1021 startBlock = bit + (i * kBitsPerWord) + j; 1022 } 1023 bitsRemain--; 1024 if (bitsRemain == 0) { 1025 goto out; 1026 } 1027 } 1028 curWord <<= 1; 1029 } /* for - checking bits set in word */ 1030 1031 /* If this is last valid word, stop the search */ 1032 if (validBitsInWord != kBitsPerWord) { 1033 goto out; 1034 } 1035 } /* else - not all bits set in a word */ 1036 } /* for - segment is partially full */ 1037 } /* for - loop over all segments */ 1038 1039out: 1040 if (bitsRemain == 0) { 1041 /* Return the new start block found */ 1042 *actualStartBlock = startBlock; 1043 retval = 0; 1044 } else { 1045 *actualStartBlock = 0; 1046 } 1047 1048 return retval; 1049} 1050 1051/* Function: AllocateContigBitmapBits 1052 * 1053 * Description: Find contigous free bitmap bits (allocation blocks) from 1054 * the in-memory volume bitmap. If found, also mark the bits as used. 1055 * 1056 * Input: 1057 * 1. vcb - pointer to volume information 1058 * 2. numBlocks - number of free contigous blocks 1059 * 3. actualStartBlock - pointer to return the start block, if contigous 1060 * free blocks found. 1061 * 1062 * Output: 1063 * 1. actualStartBlock - pointer to return the start block, if contigous 1064 * free blocks found. 1065 * On success, returns zero. 1066 * On failure, non-zero value 1067 * ENOENT - No contigous free blocks were found of given length 1068 * E_OvlExt - Free blocks found are already allocated (overlapping 1069 * extent found). 1070 */ 1071int AllocateContigBitmapBits (SVCB *vcb, UInt32 numBlocks, UInt32 *actualStartBlock) 1072{ 1073 int error; 1074 1075 error = FindContigClearedBitmapBits (vcb, numBlocks, actualStartBlock); 1076 if (error == noErr) { 1077 error = CaptureBitmapBits (*actualStartBlock, numBlocks); 1078 } 1079 1080 return error; 1081} 1082 1083enum { kMaxTrimExtents = 256 }; 1084dk_extent_t gTrimExtents[kMaxTrimExtents]; 1085dk_unmap_t gTrimData; 1086 1087static void TrimInit(void) 1088{ 1089 bzero(&gTrimData, sizeof(gTrimData)); 1090 gTrimData.extents = gTrimExtents; 1091} 1092 1093static void TrimFlush(void) 1094{ 1095 int err; 1096 1097 if (gTrimData.extentsCount == 0) 1098 { 1099 DPRINTF(d_info|d_trim, "TrimFlush: nothing to flush\n"); 1100 return; 1101 } 1102 1103 err = ioctl(fsreadfd, DKIOCUNMAP, &gTrimData); 1104 if (err == -1) 1105 { 1106 DPRINTF(d_error|d_trim, "TrimFlush: error %d\n", errno); 1107 } 1108 gTrimData.extentsCount = 0; 1109} 1110 1111static void TrimExtent(SGlobPtr g, UInt32 startBlock, UInt32 blockCount) 1112{ 1113 UInt64 offset; 1114 UInt64 length; 1115 1116 DPRINTF(d_info|d_trim, "Trimming: startBlock=%10u, blockCount=%10u\n", startBlock, blockCount); 1117 1118 offset = (UInt64) startBlock * g->calculatedVCB->vcbBlockSize; 1119 if (VolumeObjectIsHFSPlus()) 1120 offset += g->calculatedVCB->vcbEmbeddedOffset; 1121 else 1122 offset += g->calculatedVCB->vcbAlBlSt * 512ULL; 1123 length = (UInt64) blockCount * g->calculatedVCB->vcbBlockSize; 1124 1125 gTrimExtents[gTrimData.extentsCount].offset = offset; 1126 gTrimExtents[gTrimData.extentsCount].length = length; 1127 if (++gTrimData.extentsCount == kMaxTrimExtents) 1128 TrimFlush(); 1129} 1130 1131/* Function: TrimFreeBlocks 1132 * 1133 * Description: Find contiguous ranges of free allocation blocks (cleared bits 1134 * in the bitmap) and issue DKIOCUNMAP requests to tell the underlying device 1135 * that those blocks are not in use. This allows the device to reclaim that 1136 * space. 1137 * 1138 * Input: 1139 * g - global scavenger structure pointer 1140 */ 1141void TrimFreeBlocks(SGlobPtr g) 1142{ 1143 UInt32 *buffer; 1144 UInt32 bit; 1145 UInt32 wordWithinSegment; 1146 UInt32 bitWithinWordMask; 1147 UInt32 currentWord; 1148 UInt32 startBlock; 1149 UInt32 blockCount; 1150 UInt32 totalTrimmed = 0; 1151 1152 TrimInit(); 1153 1154 /* We haven't seen any free blocks yet. */ 1155 startBlock = 0; 1156 blockCount = 0; 1157 1158 /* Loop through bitmap segments */ 1159 for (bit = 0; bit < gTotalBits; /* bit incremented below */) { 1160 assert((bit % kBitsPerSegment) == 0); 1161 1162 (void) GetSegmentBitmap(bit, &buffer, kTestingBits); 1163 1164 if (buffer == gFullBitmapSegment) { 1165 /* 1166 * There are no free blocks in this segment, so trim any previous 1167 * extent (that ended at the end of the previous segment). 1168 */ 1169 if (blockCount != 0) { 1170 TrimExtent(g, startBlock, blockCount); 1171 totalTrimmed += blockCount; 1172 blockCount = 0; 1173 } 1174 bit += kBitsPerSegment; 1175 continue; 1176 } 1177 1178 if (buffer == gEmptyBitmapSegment) { 1179 /* 1180 * This entire segment is free. Add it to a previous extent, or 1181 * start a new one. 1182 */ 1183 if (blockCount == 0) { 1184 startBlock = bit; 1185 } 1186 if (gTotalBits - bit < kBitsPerSegment) { 1187 blockCount += gTotalBits - bit; 1188 } else { 1189 blockCount += kBitsPerSegment; 1190 } 1191 bit += kBitsPerSegment; 1192 continue; 1193 } 1194 1195 /* 1196 * If we get here, the current segment has some free and some used 1197 * blocks, so we have to iterate over them. 1198 */ 1199 for (wordWithinSegment = 0; 1200 wordWithinSegment < kWordsPerSegment && bit < gTotalBits; 1201 ++wordWithinSegment) 1202 { 1203 assert((bit % kBitsPerWord) == 0); 1204 1205 currentWord = SWAP_BE32(buffer[wordWithinSegment]); 1206 1207 /* Iterate over all the bits in the current word. */ 1208 for (bitWithinWordMask = kMSBBitSetInWord; 1209 bitWithinWordMask != 0 && bit < gTotalBits; 1210 ++bit, bitWithinWordMask >>= 1) 1211 { 1212 if (currentWord & bitWithinWordMask) { 1213 /* Found a used block. */ 1214 if (blockCount != 0) { 1215 TrimExtent(g, startBlock, blockCount); 1216 totalTrimmed += blockCount; 1217 blockCount = 0; 1218 } 1219 } else { 1220 /* 1221 * Found an unused block. Add it to the current extent, 1222 * or start a new one. 1223 */ 1224 if (blockCount == 0) { 1225 startBlock = bit; 1226 } 1227 ++blockCount; 1228 } 1229 } 1230 } 1231 } 1232 if (blockCount != 0) { 1233 TrimExtent(g, startBlock, blockCount); 1234 totalTrimmed += blockCount; 1235 blockCount = 0; 1236 } 1237 1238 TrimFlush(); 1239 DPRINTF(d_info|d_trim, "Trimmed %u allocation blocks.\n", totalTrimmed); 1240} 1241 1242/* Function: IsTrimSupported 1243 * 1244 * Description: Determine whether the device we're verifying/repairing suppports 1245 * trimming (i.e., whether it supports DKIOCUNMAP). 1246 * 1247 * Result: 1248 * non-zero Trim supported 1249 * zero Trim not supported 1250 */ 1251int IsTrimSupported(void) 1252{ 1253 int err; 1254 uint32_t features = 0; 1255 1256 err = ioctl(fsreadfd, DKIOCGETFEATURES, &features); 1257 if (err < 0) 1258 { 1259 /* Can't tell if UNMAP is supported. Assume no. */ 1260 return 0; 1261 } 1262 1263 return features & DK_FEATURE_UNMAP; 1264} 1265 1266/* 1267 * BITMAP SEGMENT TREE 1268 * 1269 * A binary search tree is used to store bitmap segments that are 1270 * partially full. If a segment does not exist in the tree, it 1271 * can be assumed to be in the following state: 1272 * 1. Full if the coresponding segment map bit is set 1273 * 2. Empty (implied) 1274 */ 1275 1276static int 1277BMS_InitTree(void) 1278{ 1279 gBMS_PoolCount = 0; 1280 BMS_GrowNodePool(); 1281 1282 gBMS_Root = gBMS_FreeNodes; 1283 gBMS_FreeNodes = gBMS_FreeNodes->right; 1284 gBMS_Root->right = NULL; 1285 1286 return (0); 1287} 1288 1289 1290static int 1291BMS_DisposeTree(void) 1292{ 1293 while(gBMS_PoolCount > 0) 1294 free(gBMS_PoolList[--gBMS_PoolCount]); 1295 1296 gBMS_Root = gBMS_FreeNodes = 0; 1297 return (0); 1298} 1299 1300 1301static BMS_Node * 1302BMS_Lookup(UInt32 segment) 1303{ 1304 BMS_Node *ptree = gBMS_Root; 1305 1306 while (ptree && ptree->segment != segment) { 1307 1308 if (segment > ptree->segment) 1309 ptree = ptree->right; 1310 else 1311 ptree = ptree->left; 1312 } 1313 1314 return ((BMS_Node *)ptree); 1315} 1316 1317 1318static BMS_Node * 1319BMS_InsertTree(BMS_Node *NewEntry) 1320{ 1321 BMS_Node *ptree; 1322 register UInt32 segment; 1323 1324 segment = NewEntry->segment; 1325 ptree = gBMS_Root; 1326 if (ptree == (BMS_Node *)NULL) { 1327 gBMS_Root = NewEntry; 1328 return (NewEntry); 1329 } 1330 1331 while (ptree) { 1332 if (segment > ptree->segment) { /* walk the right sub-tree */ 1333 if (ptree->right) 1334 ptree = ptree->right; 1335 else { 1336 ptree->right = NewEntry; 1337 return (ptree); 1338 } 1339 } 1340 else { /* walk the left sub-tree */ 1341 if (ptree->left) 1342 ptree = ptree->left; 1343 else { 1344 ptree->left = NewEntry; 1345 return (ptree); 1346 } 1347 } 1348 } 1349 1350 return ((BMS_Node *)NULL); 1351} 1352 1353 1354/* insert a new segment into the tree */ 1355static BMS_Node * 1356BMS_Insert(UInt32 segment, int segmentType) 1357{ 1358 BMS_Node *new; 1359 1360 if ((new = gBMS_FreeNodes) == NULL) { 1361 BMS_GrowNodePool(); 1362 if ((new = gBMS_FreeNodes) == NULL) 1363 return ((BMS_Node *)NULL); 1364 } 1365 1366 gBMS_FreeNodes = gBMS_FreeNodes->right; 1367 1368 ++gSegmentNodes; /* debugging stats */ 1369 1370 new->right = NULL; 1371 new->segment = segment; 1372 if (segmentType == kFullSegment) 1373 bcopy(gFullBitmapSegment, new->bitmap, kBytesPerSegment); 1374 else 1375 bzero(new->bitmap, sizeof(new->bitmap)); 1376 1377 if (BMS_InsertTree(new) != NULL) 1378 return (new); 1379 else 1380 return ((BMS_Node *)NULL); 1381} 1382 1383 1384static BMS_Node * 1385BMS_Delete(UInt32 segment) 1386{ 1387 BMS_Node *seg_found, *pprevious, *pnext, *pnextl, *psub; 1388 1389 pprevious = NULL; 1390 seg_found = gBMS_Root; 1391 1392 /* don't allow the root to be deleted! */ 1393 if (seg_found->segment == segment) 1394 return ((BMS_Node *)NULL); 1395 1396 while (seg_found && seg_found->segment != segment) { 1397 pprevious = seg_found; 1398 if (segment > seg_found->segment) 1399 seg_found = seg_found->right; 1400 else 1401 seg_found = seg_found->left; 1402 } 1403 1404 if (seg_found) { 1405 /* 1406 * we found the entry, now reorg the sub-trees 1407 * spanning from our node. 1408 */ 1409 if ((pnext = seg_found->right)) { 1410 /* 1411 * Tree pruning: take the left branch of the 1412 * current node and place it at the lowest 1413 * left branch of the current right branch 1414 */ 1415 psub = pnext; 1416 1417 /* walk the Right/Left sub tree from current node */ 1418 while ((pnextl = psub->left)) 1419 psub = pnextl; 1420 1421 /* plug the old left tree to the new ->Right leftmost node */ 1422 psub->left = seg_found->left; 1423 } else { /* only left sub-tree, simple case */ 1424 pnext = seg_found->left; 1425 } 1426 /* 1427 * Now, plug the current node sub tree to 1428 * the good pointer of our parent node. 1429 */ 1430 if (pprevious->left == seg_found) 1431 pprevious->left = pnext; 1432 else 1433 pprevious->right = pnext; 1434 1435 /* add node back to the free-list */ 1436 bzero(seg_found, sizeof(BMS_Node)); 1437 seg_found->right = gBMS_FreeNodes; 1438 gBMS_FreeNodes = seg_found; 1439 } 1440 1441 return (seg_found); 1442} 1443 1444 1445static void 1446BMS_GrowNodePool(void) 1447{ 1448 BMS_Node *nodePool; 1449 short i; 1450 1451 if (gBMS_PoolCount > kBMS_PoolMax) 1452 return; 1453 1454 nodePool = (BMS_Node *)malloc(sizeof(BMS_Node) * kBMS_NodesPerPool); 1455 if (nodePool != NULL) { 1456 bzero(&nodePool[0], sizeof(BMS_Node) * kBMS_NodesPerPool); 1457 for (i = 1 ; i < kBMS_NodesPerPool ; i++) { 1458 (&nodePool[i-1])->right = &nodePool[i]; 1459 } 1460 1461 gBMS_FreeNodes = &nodePool[0]; 1462 gBMS_PoolList[gBMS_PoolCount++] = nodePool; 1463 } 1464} 1465 1466 1467#if _VBC_DEBUG_ 1468static void 1469BMS_MaxDepth(BMS_Node * root, int depth, int *maxdepth) 1470{ 1471 if (root) { 1472 depth++; 1473 if (depth > *maxdepth) 1474 *maxdepth = depth; 1475 BMS_MaxDepth(root->left, depth, maxdepth); 1476 BMS_MaxDepth(root->right, depth, maxdepth); 1477 } 1478} 1479 1480static void 1481BMS_PrintTree(BMS_Node * root) 1482{ 1483 if (root) { 1484 BMS_PrintTree(root->left); 1485 plog("seg %d\n", root->segment); 1486 BMS_PrintTree(root->right); 1487 } 1488} 1489#endif 1490 1491