src/add-ons/kernel/file_systems/ramfs/BlockAllocatorArea.cpp

   1 // BlockAllocatorArea.cpp
   2
   3 #include "BlockAllocatorArea.h"
   4 #include "Debug.h"
   5
   6 // constructor
   7 BlockAllocator::Area::Area(area_id id, size_t size)
   8         : fBucket(NULL),
   9           fID(id),
  10           fSize(size),
  11           fFreeBytes(0),
  12           fFreeBlockCount(1),
  13           fUsedBlockCount(0),
  14           fFirstBlock(NULL),
  15           fLastBlock(NULL),
  16           fFirstFree(NULL),
  17           fLastFree(NULL)
  18 {
  19         size_t headerSize = block_align_ceil(sizeof(Area));
  20         fFirstFree = (TFreeBlock*)((char*)this + headerSize);
  21         fFirstFree->SetTo(NULL, block_align_floor(fSize - headerSize), false, NULL,
  22                                           NULL);
  23         fFirstBlock = fLastBlock = fLastFree = fFirstFree;
  24         fFreeBytes = fFirstFree->GetUsableSize();
  25 }
  26
  27 // Create
  28 BlockAllocator::Area *
  29 BlockAllocator::Area::Create(size_t size)
  30 {
  31         Area *area = NULL;
  32         void *base = NULL;
  33 #if USER
  34         area_id id = create_area("block alloc", &base, B_ANY_ADDRESS,
  35                                                          size, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
  36 #else
  37         area_id id = create_area("block alloc", &base, B_ANY_KERNEL_ADDRESS,
  38                                                          size, B_FULL_LOCK, B_READ_AREA | B_WRITE_AREA);
  39 #endif
  40         if (id >= 0) {
  41                 area = new(base) Area(id, size);
  42         } else {
  43                 ERROR(("BlockAllocator::Area::Create(%lu): Failed to create area: %s\n",
  44                         size, strerror(id)));
  45         }
  46         return area;
  47 }
  48
  49 // Delete
  50 void
  51 BlockAllocator::Area::Delete()
  52 {
  53         delete_area(fID);
  54 }
  55
  56 // AllocateBlock
  57 Block *
  58 BlockAllocator::Area::AllocateBlock(size_t usableSize, bool dontDefragment)
  59 {
  60 if (kMinBlockSize != block_align_ceil(sizeof(TFreeBlock))) {
  61 FATAL(("kMinBlockSize is not correctly initialized! Is %lu, but should be: "
  62 "%lu\n", kMinBlockSize, block_align_ceil(sizeof(TFreeBlock))));
  63 BA_PANIC("kMinBlockSize not correctly initialized.");
  64 return NULL;
  65 }
  66         if (usableSize == 0)
  67                 return NULL;
  68         Block *newBlock = NULL;
  69         size_t size = max(usableSize + sizeof(BlockHeader), kMinBlockSize);
  70         size = block_align_ceil(size);
  71         if (size <= _GetBlockFreeBytes()) {
  72                 // find first fit
  73                 TFreeBlock *block = _FindFreeBlock(size);
  74                 if (!block && !dontDefragment) {
  75                         // defragmenting is necessary
  76                         _Defragment();
  77                         block = _FindFreeBlock(size);
  78                         if (!block) {
  79                                 // no free block
  80                                 // Our data structures seem to be corrupted, since
  81                                 // _GetBlockFreeBytes() promised that we would have enough
  82                                 // free space.
  83                                 FATAL(("Couldn't find free block of min size %lu after "
  84                                            "defragmenting, although we should have %lu usable free "
  85                                            "bytes!\n", size, _GetBlockFreeBytes()));
  86                                 BA_PANIC("Bad area free bytes.");
  87                         }
  88                 }
  89                 if (block) {
  90                         // found a free block
  91                         size_t remainder = block->GetSize() - size;
  92                         if (remainder >= kMinBlockSize) {
  93                                 // enough space left for a free block
  94                                 Block *freePrev = block->GetPreviousBlock();
  95 //                              TFreeBlock *prevFree = block->GetPreviousFreeBlock();
  96 //                              TFreeBlock *nextFree = block->GetNextFreeBlock();
  97 //                              newBlock = block;
  98                                 _MoveResizeFreeBlock(block, size, remainder);
  99                                 // setup the new block
 100 //                              newBlock->SetSize(size, true);
 101 //                              newBlock->SetFree(false);
 102                                 newBlock = _MakeUsedBlock(block, 0, freePrev, size, true);
 103                         } else {
 104                                 // not enough space left: take the free block over completely
 105                                 // remove the block from the free list
 106                                 _RemoveFreeBlock(block);
 107                                 newBlock = block;
 108                                 newBlock->SetFree(false);
 109                         }
 110                         if (fFreeBlockCount)
 111                                 fFreeBytes -= newBlock->GetSize();
 112                         else
 113                                 fFreeBytes = 0;
 114                         fUsedBlockCount++;
 115                 }
 116         }
 117         D(SanityCheck());
 118         return newBlock;
 119 }
 120
 121 // FreeBlock
 122 void
 123 BlockAllocator::Area::FreeBlock(Block *block, bool dontDefragment)
 124 {
 125         if (block) {
 126                 // mark the block free and insert it into the free list
 127                 block->SetFree(true);
 128                 TFreeBlock *freeBlock = (TFreeBlock*)block;
 129                 _InsertFreeBlock(freeBlock);
 130                 fUsedBlockCount--;
 131                 if (fFreeBlockCount == 1)
 132                         fFreeBytes += freeBlock->GetUsableSize();
 133                 else
 134                         fFreeBytes += freeBlock->GetSize();
 135                 // try coalescing with the next and the previous free block
 136 D(SanityCheck());
 137                 _CoalesceWithNext(freeBlock);
 138 D(SanityCheck());
 139                 _CoalesceWithNext(freeBlock->GetPreviousFreeBlock());
 140                 // defragment, if sensible
 141                 if (!dontDefragment && _DefragmentingRecommended())
 142                         _Defragment();
 143                 D(SanityCheck());
 144         }
 145 }
 146
 147 // ResizeBlock
 148 Block *
 149 BlockAllocator::Area::ResizeBlock(Block *block, size_t newUsableSize,
 150                                                                   bool dontDefragment)
 151 {
 152 //PRINT(("Area::ResizeBlock(%p, %lu)\n", block, newUsableSize));
 153 // newUsableSize must be >0 !
 154         if (newUsableSize == 0)
 155                 return NULL;
 156         Block *resultBlock = NULL;
 157         if (block) {
 158                 size_t size = block->GetSize();
 159                 size_t newSize = max(newUsableSize + sizeof(BlockHeader),
 160                                                          kMinBlockSize);
 161                 newSize = block_align_ceil(newSize);
 162                 if (newSize == size) {
 163                         // size doesn't change: nothing to do
 164                         resultBlock = block;
 165                 } else if (newSize < size) {
 166                         // shrink the block
 167                         size_t sizeDiff = size - newSize;
 168                         Block *nextBlock = block->GetNextBlock();
 169                         if (nextBlock && nextBlock->IsFree()) {
 170                                 // join the space with the adjoining free block
 171                                 TFreeBlock *freeBlock = nextBlock->ToFreeBlock();
 172                                 _MoveResizeFreeBlock(freeBlock, -sizeDiff,
 173                                                                          freeBlock->GetSize() + sizeDiff);
 174                                 // resize the block and we're done
 175                                 block->SetSize(newSize, true);
 176                                 fFreeBytes += sizeDiff;
 177                         } else if (sizeDiff >= sizeof(TFreeBlock)) {
 178                                 // the freed space is large enough for a free block
 179                                 TFreeBlock *newFree = _MakeFreeBlock(block, newSize, block,
 180                                         sizeDiff, nextBlock, NULL, NULL);
 181                                 _InsertFreeBlock(newFree);
 182                                 block->SetSize(newSize, true);
 183                                 if (fFreeBlockCount == 1)
 184                                         fFreeBytes += newFree->GetUsableSize();
 185                                 else
 186                                         fFreeBytes += newFree->GetSize();
 187                                 if (!dontDefragment && _DefragmentingRecommended())
 188                                         _Defragment();
 189                         }       // else: insufficient space for a free block: no changes
 190                         resultBlock = block;
 191                 } else {
 192 //PRINT(("  grow...\n"));
 193                         // grow the block
 194                         size_t sizeDiff = newSize - size;
 195                         Block *nextBlock = block->GetNextBlock();
 196                         if (nextBlock && nextBlock->IsFree()
 197                                 && nextBlock->GetSize() >= sizeDiff) {
 198 //PRINT(("  adjoining free block\n"));
 199                                 // there is a adjoining free block and it is large enough
 200                                 TFreeBlock *freeBlock = nextBlock->ToFreeBlock();
 201                                 size_t freeSize = freeBlock->GetSize();
 202                                 if (freeSize - sizeDiff >= sizeof(TFreeBlock)) {
 203                                         // the remaining space is still large enough for a free
 204                                         // block
 205                                         _MoveResizeFreeBlock(freeBlock, sizeDiff,
 206                                                                                  freeSize - sizeDiff);
 207                                         block->SetSize(newSize, true);
 208                                         fFreeBytes -= sizeDiff;
 209                                 } else {
 210                                         // the remaining free space wouldn't be large enough for
 211                                         // a free block: consume the free block completely
 212                                         Block *freeNext = freeBlock->GetNextBlock();
 213                                         _RemoveFreeBlock(freeBlock);
 214                                         block->SetSize(size + freeSize, freeNext);
 215                                         _FixBlockList(block, block->GetPreviousBlock(), freeNext);
 216                                         if (fFreeBlockCount == 0)
 217                                                 fFreeBytes = 0;
 218                                         else
 219                                                 fFreeBytes -= freeSize;
 220                                 }
 221                                 resultBlock = block;
 222                         } else {
 223 //PRINT(("  no adjoining free block\n"));
 224                                 // no (large enough) adjoining free block: allocate
 225                                 // a new block and copy the data to it
 226                                 BlockReference *reference = block->GetReference();
 227                                 resultBlock = AllocateBlock(newUsableSize, dontDefragment);
 228                                 block = reference->GetBlock();
 229                                 if (resultBlock) {
 230                                         resultBlock->SetReference(reference);
 231                                         memcpy(resultBlock->GetData(), block->GetData(),
 232                                                    block->GetUsableSize());
 233                                         FreeBlock(block, dontDefragment);
 234                                         resultBlock = reference->GetBlock();
 235                                 }
 236                         }
 237                 }
 238         }
 239         D(SanityCheck());
 240 //PRINT(("Area::ResizeBlock() done: %p\n", resultBlock));
 241         return resultBlock;
 242 }
 243
 244 // SanityCheck
 245 bool
 246 BlockAllocator::Area::SanityCheck() const
 247 {
 248         // area ID
 249         if (fID < 0) {
 250                 FATAL(("Area ID < 0: %lx\n", fID));
 251                 BA_PANIC("Bad area ID.");
 252                 return false;
 253         }
 254         // size
 255         size_t areaHeaderSize = block_align_ceil(sizeof(Area));
 256         if (fSize < areaHeaderSize + sizeof(TFreeBlock)) {
 257                 FATAL(("Area too small to contain area header and at least one free "
 258                            "block: %lu bytes\n", fSize));
 259                 BA_PANIC("Bad area size.");
 260                 return false;
 261         }
 262         // free bytes
 263         if (fFreeBytes > fSize) {
 264                 FATAL(("Free size greater than area size: %lu vs %lu\n", fFreeBytes,
 265                            fSize));
 266                 BA_PANIC("Bad area free bytes.");
 267                 return false;
 268         }
 269         // block count
 270         if (fFreeBlockCount + fUsedBlockCount == 0) {
 271                 FATAL(("Area contains no blocks at all.\n"));
 272                 BA_PANIC("Bad area block count.");
 273                 return false;
 274         }
 275         // block list
 276         uint32 usedBlockCount = 0;
 277         uint32 freeBlockCount = 0;
 278         size_t freeBytes = 0;
 279         if (!fFirstBlock || !fLastBlock) {
 280                 FATAL(("Invalid block list: first or last block NULL: first: %p, "
 281                            "last: %p\n", fFirstBlock, fLastBlock));
 282                 BA_PANIC("Bad area block list.");
 283                 return false;
 284         } else {
 285                 // iterate through block list and also check free list
 286                 int32 blockCount = fFreeBlockCount + fUsedBlockCount;
 287                 Block *block = fFirstBlock;
 288                 Block *prevBlock = NULL;
 289                 Block *prevFree = NULL;
 290                 Block *nextFree = fFirstFree;
 291                 bool blockListOK = true;
 292                 for (int32 i = 0; i < blockCount; i++) {
 293                         blockListOK = false;
 294                         if (!block) {
 295                                 FATAL(("Encountered NULL in block list at index %ld, although "
 296                                            "list should have %ld blocks\n", i, blockCount));
 297                                 BA_PANIC("Bad area block list.");
 298                                 return false;
 299                         }
 300                         uint64 address = (uint32)block;
 301                         // block within area?
 302                         if (address < (uint32)this + areaHeaderSize
 303                                 || address + sizeof(TFreeBlock) > (uint32)this + fSize) {
 304                                 FATAL(("Utterly mislocated block: %p, area: %p, "
 305                                            "size: %lu\n", block, this, fSize));
 306                                 BA_PANIC("Bad area block.");
 307                                 return false;
 308                         }
 309                         // block too large for area?
 310                         size_t blockSize = block->GetSize();
 311                         if (blockSize < sizeof(TFreeBlock)
 312                                 || address + blockSize > (uint32)this + fSize) {
 313                                 FATAL(("Mislocated block: %p, size: %lu, area: %p, "
 314                                            "size: %lu\n", block, blockSize, this, fSize));
 315                                 BA_PANIC("Bad area block.");
 316                                 return false;
 317                         }
 318                         // alignment
 319                         if (block_align_floor(address) != address
 320                                 || block_align_floor(blockSize) != blockSize) {
 321                                 FATAL(("Block %ld not properly aligned: %p, size: %lu\n",
 322                                            i, block, blockSize));
 323                                 BA_PANIC("Bad area block.");
 324                                 return false;
 325                         }
 326                         // previous block
 327                         if (block->GetPreviousBlock() != prevBlock) {
 328                                 FATAL(("Previous block of block %ld was not the previous "
 329                                            "block in list: %p vs %p\n", i,
 330                                            block->GetPreviousBlock(), prevBlock));
 331                                 BA_PANIC("Bad area block list.");
 332                                 return false;
 333                         }
 334                         // additional checks for free block list
 335                         if (block->IsFree()) {
 336                                 freeBlockCount++;
 337                                 TFreeBlock *freeBlock = block->ToFreeBlock();
 338                                 if (prevFree)
 339                                         freeBytes += freeBlock->GetSize();
 340                                 else
 341                                         freeBytes += freeBlock->GetUsableSize();
 342                                 // block == next free block of previous free block
 343                                 if (freeBlock != nextFree) {
 344                                         FATAL(("Free block %ld is not the next block in free "
 345                                                    "list: %p vs %p\n", i, freeBlock, nextFree));
 346                                         BA_PANIC("Bad area free list.");
 347                                         return false;
 348                                 }
 349                                 // previous free block
 350                                 if (freeBlock->GetPreviousFreeBlock() != prevFree) {
 351                                         FATAL(("Previous free block of block %ld was not the "
 352                                                    " previous block in free list: %p vs %p\n", i,
 353                                                    freeBlock->GetPreviousFreeBlock(), prevFree));
 354                                         BA_PANIC("Bad area free list.");
 355                                         return false;
 356                                 }
 357                                 prevFree = freeBlock;
 358                                 nextFree = freeBlock->GetNextFreeBlock();
 359                         } else
 360                                 usedBlockCount++;
 361                         prevBlock = block;
 362                         block = block->GetNextBlock();
 363                         blockListOK = true;
 364                 }
 365                 // final checks on block list
 366                 if (blockListOK) {
 367                         if (block) {
 368                                 FATAL(("More blocks in block list than expected\n"));
 369                                 BA_PANIC("Bad area block count.");
 370                                 return false;
 371                         } else if (fLastBlock != prevBlock) {
 372                                 FATAL(("last block in block list was %p, but should be "
 373                                            "%p\n", fLastBlock, prevBlock));
 374                                 BA_PANIC("Bad area last block.");
 375                                 return false;
 376                         } else if (prevFree != fLastFree) {
 377                                 FATAL(("last block in free list was %p, but should be %p\n",
 378                                            fLastFree, prevFree));
 379                                 BA_PANIC("Bad area last free block.");
 380                                 return false;
 381                         }
 382                         // block counts (a bit reduntant)
 383                         if (freeBlockCount != fFreeBlockCount) {
 384                                 FATAL(("Free block count is %ld, but should be %ld\n",
 385                                            fFreeBlockCount, freeBlockCount));
 386                                 BA_PANIC("Bad area free block count.");
 387                                 return false;
 388                         }
 389                         if (usedBlockCount != fUsedBlockCount) {
 390                                 FATAL(("Used block count is %ld, but should be %ld\n",
 391                                            fUsedBlockCount, usedBlockCount));
 392                                 BA_PANIC("Bad area used block count.");
 393                                 return false;
 394                         }
 395                         // free bytes
 396                         if (fFreeBytes != freeBytes) {
 397                                 FATAL(("Free bytes is %lu, but should be %lu\n",
 398                                            fFreeBytes, freeBytes));
 399                                 BA_PANIC("Bad area free bytes.");
 400                                 return false;
 401                         }
 402                 }
 403         }
 404         return true;
 405 }
 406
 407 // CheckBlock
 408 bool
 409 BlockAllocator::Area::CheckBlock(Block *checkBlock, size_t minSize)
 410 {
 411         for (Block *block = fFirstBlock; block; block = block->GetNextBlock()) {
 412                 if (block == checkBlock)
 413                         return (block->GetUsableSize() >= minSize);
 414         }
 415         FATAL(("Block %p is not in area %p!\n", checkBlock, this));
 416         BA_PANIC("Invalid Block.");
 417         return false;
 418 }
 419
 420 // _FindFreeBlock
 421 TFreeBlock *
 422 BlockAllocator::Area::_FindFreeBlock(size_t minSize)
 423 {
 424         // first fit
 425         for (TFreeBlock *block = GetFirstFreeBlock();
 426                  block;
 427                  block = block->GetNextFreeBlock()) {
 428                 if (block->GetSize() >= minSize)
 429                         return block;
 430         }
 431         return NULL;
 432 }
 433
 434 // _InsertFreeBlock
 435 void
 436 BlockAllocator::Area::_InsertFreeBlock(TFreeBlock *block)
 437 {
 438         if (block) {
 439                 // find the free block before which this one has to be inserted
 440                 TFreeBlock *nextFree = NULL;
 441                 for (nextFree = GetFirstFreeBlock();
 442                          nextFree;
 443                          nextFree = nextFree->GetNextFreeBlock()) {
 444                         if ((uint32)nextFree > (uint32)block)
 445                                 break;
 446                 }
 447                 // get the previous block and insert the block between the two
 448                 TFreeBlock *prevFree
 449                         = (nextFree ? nextFree->GetPreviousFreeBlock() : fLastFree);
 450                 _FixFreeList(block, prevFree, nextFree);
 451                 fFreeBlockCount++;
 452         }
 453 }
 454
 455 // _RemoveFreeBlock
 456 void
 457 BlockAllocator::Area::_RemoveFreeBlock(TFreeBlock *block)
 458 {
 459         if (block) {
 460                 TFreeBlock *prevFree = block->GetPreviousFreeBlock();
 461                 TFreeBlock *nextFree = block->GetNextFreeBlock();
 462                 if (prevFree)
 463                         prevFree->SetNextFreeBlock(nextFree);
 464                 else
 465                         fFirstFree = nextFree;
 466                 if (nextFree)
 467                         nextFree->SetPreviousFreeBlock(prevFree);
 468                 else
 469                         fLastFree = prevFree;
 470         }
 471         fFreeBlockCount--;
 472 }
 473
 474 // _MoveResizeFreeBlock
 475 TFreeBlock *
 476 BlockAllocator::Area::_MoveResizeFreeBlock(TFreeBlock *freeBlock,
 477                                                                                    ssize_t offset, size_t newSize)
 478 {
 479         TFreeBlock *movedFree = NULL;
 480         if (freeBlock && offset) {
 481                 // move the header of the free block
 482                 Block *freePrev = freeBlock->GetPreviousBlock();
 483                 TFreeBlock *prevFree = freeBlock->GetPreviousFreeBlock();
 484                 TFreeBlock *nextFree = freeBlock->GetNextFreeBlock();
 485                 movedFree = _MakeFreeBlock(freeBlock, offset, freePrev, newSize,
 486                         freeBlock->HasNextBlock(), prevFree, nextFree);
 487                 // update the free list
 488                 _FixFreeList(movedFree, prevFree, nextFree);
 489         }
 490         return movedFree;
 491 }
 492
 493 // _MakeFreeBlock
 494 inline
 495 TFreeBlock *
 496 BlockAllocator::Area::_MakeFreeBlock(void *address, ssize_t offset,
 497                                                                          Block *previous, size_t size,
 498                                                                          bool hasNext, TFreeBlock *previousFree,
 499                                                                          TFreeBlock *nextFree)
 500 {
 501         TFreeBlock *block = (TFreeBlock*)((char*)address + offset);
 502         block->SetTo(previous, size, hasNext, previousFree, nextFree);
 503         if (hasNext)
 504                 block->GetNextBlock()->SetPreviousBlock(block);
 505         else
 506                 fLastBlock = block;
 507         return block;
 508 }
 509
 510 // _CoalesceWithNext
 511 bool
 512 BlockAllocator::Area::_CoalesceWithNext(TFreeBlock *block)
 513 {
 514         bool result = false;
 515         TFreeBlock *nextFree = NULL;
 516         if (block && (nextFree = block->GetNextFreeBlock()) != NULL
 517                 && block->GetNextBlock() == nextFree) {
 518                 _RemoveFreeBlock(nextFree);
 519                 Block *nextBlock = nextFree->GetNextBlock();
 520                 block->SetSize(block->GetSize() + nextFree->GetSize(), nextBlock);
 521                 if (nextBlock)
 522                         nextBlock->SetPreviousBlock(block);
 523                 else
 524                         fLastBlock = block;
 525                 result = true;
 526         }
 527         return result;
 528 }
 529
 530 // _MakeUsedBlock
 531 inline
 532 Block *
 533 BlockAllocator::Area::_MakeUsedBlock(void *address, ssize_t offset,
 534                                                                          Block *previous, size_t size,
 535                                                                          bool hasNext)
 536 {
 537         Block *block = (Block*)((char*)address + offset);
 538         block->SetTo(previous, size, false, hasNext, NULL);
 539         if (hasNext)
 540                 block->GetNextBlock()->SetPreviousBlock(block);
 541         else
 542                 fLastBlock = block;
 543         return block;
 544 }
 545
 546 // _Defragment
 547 void
 548 BlockAllocator::Area::_Defragment()
 549 {
 550 D(SanityCheck());
 551 //PRINT(("BlockAllocator::Area::_Defragment()\n"));
 552         // A trivial strategy for now: Keep the last free block and move the
 553         // others so that they can be joined with it. This is done iteratively
 554         // by moving the first free block to adjoin to the second one and
 555         // coalescing them. A free block is moved by moving the data blocks in
 556         // between.
 557         TFreeBlock *nextFree = NULL;
 558         while (fFirstFree && (nextFree = fFirstFree->GetNextFreeBlock()) != NULL) {
 559                 Block *prevBlock = fFirstFree->GetPreviousBlock();
 560                 Block *nextBlock = fFirstFree->GetNextBlock();
 561                 size_t size = fFirstFree->GetSize();
 562                 // Used blocks are relatively position independed. We can move them
 563                 // en bloc and only need to adjust the previous pointer of the first
 564                 // one.
 565                 if (!nextBlock->IsFree()) {
 566                         // move the used blocks
 567                         size_t chunkSize = (char*)nextFree - (char*)nextBlock;
 568                         Block *nextFreePrev = nextFree->GetPreviousBlock();
 569                         Block *movedBlock = fFirstFree;
 570                         memmove(movedBlock, nextBlock, chunkSize);
 571                         movedBlock->SetPreviousBlock(prevBlock);
 572                         // init the first free block
 573                         Block *movedNextFreePrev = (Block*)((char*)nextFreePrev - size);
 574                         fFirstFree = _MakeFreeBlock(movedBlock, chunkSize,
 575                                 movedNextFreePrev, size, true, NULL, nextFree);
 576                         nextFree->SetPreviousFreeBlock(fFirstFree);
 577                         // fix the references of the moved blocks
 578                         for (Block *block = movedBlock;
 579                                  block != fFirstFree;
 580                                  block = block->GetNextBlock()) {
 581                                 block->FixReference();
 582                         }
 583                 } else {
 584                         // uncoalesced adjoining free block: That should never happen,
 585                         // since we always coalesce as early as possible.
 586                         INFORM(("Warning: Found uncoalesced adjoining free blocks!\n"));
 587                 }
 588                 // coalesce the first two blocks
 589 D(SanityCheck());
 590                 _CoalesceWithNext(fFirstFree);
 591 D(SanityCheck());
 592         }
 593 //D(SanityCheck());
 594 //PRINT(("BlockAllocator::Area::_Defragment() done\n"));
 595 }
 596