1// BlockAllocator.cpp 2 3// debugging 4#define BA_DEFINE_INLINES 1 5 6#include <new> 7 8#include "AllocationInfo.h" 9#include "BlockAllocator.h" 10#include "BlockAllocatorArea.h" 11#include "BlockAllocatorAreaBucket.h" 12#include "Debug.h" 13 14 15// BlockAllocator 16 17// constructor 18BlockAllocator::BlockAllocator(size_t areaSize) 19 : fReferenceManager(), 20 fBuckets(NULL), 21 fBucketCount(0), 22 fAreaSize(areaSize), 23 fAreaCount(0), 24 fFreeBytes(0) 25{ 26 // create and init buckets 27 fBucketCount = bucket_containing_size(areaSize) + 1; 28 fBuckets = new(std::nothrow) AreaBucket[fBucketCount]; 29 size_t minSize = 0; 30 for (int32 i = 0; i < fBucketCount; i++) { 31 size_t maxSize = (1 << i) * kMinNetBlockSize; 32 fBuckets[i].SetIndex(i); 33 fBuckets[i].SetSizeLimits(minSize, maxSize); 34 minSize = maxSize; 35 } 36} 37 38// destructor 39BlockAllocator::~BlockAllocator() 40{ 41 if (fBuckets) 42 delete[] fBuckets; 43} 44 45// InitCheck 46status_t 47BlockAllocator::InitCheck() const 48{ 49 RETURN_ERROR(fBuckets ? B_OK : B_NO_MEMORY); 50} 51 52// AllocateBlock 53BlockReference * 54BlockAllocator::AllocateBlock(size_t usableSize) 55{ 56#if ENABLE_BA_PANIC 57if (fPanic) 58 return NULL; 59#endif 60//PRINT(("BlockAllocator::AllocateBlock(%lu)\n", usableSize)); 61 Block *block = NULL; 62 if (usableSize > 0 && usableSize <= Area::GetMaxFreeBytesFor(fAreaSize)) { 63 // get a block reference 64 BlockReference *reference = fReferenceManager.AllocateReference(); 65 if (reference) { 66 block = _AllocateBlock(usableSize); 67 // set reference / cleanup on failure 68 if (block) 69 block->SetReference(reference); 70 else 71 fReferenceManager.FreeReference(reference); 72 } 73 D(SanityCheck(false)); 74 } 75//PRINT(("BlockAllocator::AllocateBlock() done: %p\n", block)); 76 return (block ? block->GetReference() : NULL); 77} 78 79// FreeBlock 80void 81BlockAllocator::FreeBlock(BlockReference *blockReference) 82{ 83#if ENABLE_BA_PANIC 84if (fPanic) 85 return; 86#endif 87D(if (!CheckBlock(blockReference)) return;); 88 Block *block = (blockReference ? blockReference->GetBlock() : NULL); 89//PRINT(("BlockAllocator::FreeBlock(%p)\n", block)); 90 Area *area = NULL; 91 if (block && !block->IsFree() && (area = _AreaForBlock(block)) != NULL) { 92 _FreeBlock(area, block, true); 93 D(SanityCheck(false)); 94 if (_DefragmentingRecommended()) 95 _Defragment(); 96 } 97//PRINT(("BlockAllocator::FreeBlock() done\n")); 98} 99 100// ResizeBlock 101BlockReference * 102BlockAllocator::ResizeBlock(BlockReference *blockReference, size_t usableSize) 103{ 104#if ENABLE_BA_PANIC 105if (fPanic) 106 return NULL; 107#endif 108D(if (!CheckBlock(blockReference)) return NULL;); 109//PRINT(("BlockAllocator::ResizeBlock(%p, %lu)\n", blockReference, usableSize)); 110 Block *block = (blockReference ? blockReference->GetBlock() : NULL); 111 Block *resultBlock = NULL; 112 Area *area = NULL; 113 if (block && !block->IsFree() && (area = _AreaForBlock(block)) != NULL) { 114//PRINT(("BlockAllocator::ResizeBlock(%p, %lu)\n", block, usableSize)); 115 if (usableSize) { 116 // try to let the area resize the block 117 size_t blockSize = block->GetSize(); 118 size_t areaFreeBytes = area->GetFreeBytes(); 119 bool needsDefragmenting = area->NeedsDefragmenting(); 120//PRINT((" block reference: %p / %p\n", blockReference, block->GetReference())); 121 resultBlock = area->ResizeBlock(block, usableSize); 122 block = blockReference->GetBlock(); 123 if (resultBlock) { 124//PRINT((" area succeeded in resizing the block\n")); 125//PRINT((" block reference now: %p\n", resultBlock->GetReference())); 126 // the area was able to resize the block 127 _RethinkAreaBucket(area, area->GetBucket(), 128 needsDefragmenting); 129 fFreeBytes = fFreeBytes + area->GetFreeBytes() - areaFreeBytes; 130 // Defragment only, if the area was able to resize the block, 131 // the new block is smaller than the old one and defragmenting 132 // is recommended. 133 if (blockSize > resultBlock->GetSize() 134 && _DefragmentingRecommended()) { 135 _Defragment(); 136 } 137 } else { 138//PRINT((" area failed to resize the block\n")); 139 // the area failed: allocate a new block, copy the data, and 140 // free the old one 141 resultBlock = _AllocateBlock(usableSize); 142 block = blockReference->GetBlock(); 143 if (resultBlock) { 144 memcpy(resultBlock->GetData(), block->GetData(), 145 block->GetUsableSize()); 146 resultBlock->SetReference(block->GetReference()); 147 _FreeBlock(area, block, false); 148 } 149 } 150 } else 151 FreeBlock(blockReference); 152 D(SanityCheck(false)); 153//PRINT(("BlockAllocator::ResizeBlock() done: %p\n", resultBlock)); 154 } 155 return (resultBlock ? resultBlock->GetReference() : NULL); 156} 157 158// SanityCheck 159bool 160BlockAllocator::SanityCheck(bool deep) const 161{ 162 // iterate through all areas of all buckets 163 int32 areaCount = 0; 164 size_t freeBytes = 0; 165 for (int32 i = 0; i < fBucketCount; i++) { 166 AreaBucket *bucket = fBuckets + i; 167 if (deep) { 168 if (!bucket->SanityCheck(deep)) 169 return false; 170 } 171 for (Area *area = bucket->GetFirstArea(); 172 area; 173 area = bucket->GetNextArea(area)) { 174 areaCount++; 175 freeBytes += area->GetFreeBytes(); 176 } 177 } 178 // area count 179 if (areaCount != fAreaCount) { 180 FATAL(("fAreaCount is %ld, but should be %ld\n", fAreaCount, 181 areaCount)); 182 BA_PANIC("BlockAllocator: Bad free bytes."); 183 return false; 184 } 185 // free bytes 186 if (fFreeBytes != freeBytes) { 187 FATAL(("fFreeBytes is %lu, but should be %lu\n", fFreeBytes, 188 freeBytes)); 189 BA_PANIC("BlockAllocator: Bad free bytes."); 190 return false; 191 } 192 return true; 193} 194 195// CheckArea 196bool 197BlockAllocator::CheckArea(Area *checkArea) 198{ 199 for (int32 i = 0; i < fBucketCount; i++) { 200 AreaBucket *bucket = fBuckets + i; 201 for (Area *area = bucket->GetFirstArea(); 202 area; 203 area = bucket->GetNextArea(area)) { 204 if (area == checkArea) 205 return true; 206 } 207 } 208 FATAL(("Area %p is not a valid Area!\n", checkArea)); 209 BA_PANIC("Invalid Area."); 210 return false; 211} 212 213// CheckBlock 214bool 215BlockAllocator::CheckBlock(Block *block, size_t minSize) 216{ 217 Area *area = _AreaForBlock(block); 218 return (area/* && CheckArea(area)*/ && area->CheckBlock(block, minSize)); 219} 220 221// CheckBlock 222bool 223BlockAllocator::CheckBlock(BlockReference *reference, size_t minSize) 224{ 225 return (fReferenceManager.CheckReference(reference) 226 && CheckBlock(reference->GetBlock(), minSize)); 227} 228 229// GetAllocationInfo 230void 231BlockAllocator::GetAllocationInfo(AllocationInfo &info) 232{ 233 fReferenceManager.GetAllocationInfo(info); 234 info.AddOtherAllocation(sizeof(AreaBucket), fBucketCount); 235 info.AddAreaAllocation(fAreaSize, fAreaCount); 236} 237 238// _AreaForBlock 239inline 240BlockAllocator::Area * 241BlockAllocator::_AreaForBlock(Block *block) 242{ 243 Area *area = NULL; 244 area_id id = area_for(block); 245 area_info info; 246 if (id >= 0 && get_area_info(id, &info) == B_OK) 247 area = (Area*)info.address; 248D(if (!CheckArea(area)) return NULL;); 249 return area; 250} 251 252// _AllocateBlock 253Block * 254BlockAllocator::_AllocateBlock(size_t usableSize, bool dontCreateArea) 255{ 256 Block *block = NULL; 257 // Get the last area (the one with the most free space) and try 258 // to let it allocate a block. If that fails, allocate a new area. 259 // find a bucket for the allocation 260// TODO: optimize 261 AreaBucket *bucket = NULL; 262 int32 index = bucket_containing_min_size(usableSize); 263 for (; index < fBucketCount; index++) { 264 if (!fBuckets[index].IsEmpty()) { 265 bucket = fBuckets + index; 266 break; 267 } 268 } 269 // get an area: if we have one, from the bucket, else create a new 270 // area 271 Area *area = NULL; 272 if (bucket) 273 area = bucket->GetFirstArea(); 274 else if (!dontCreateArea) { 275 area = Area::Create(fAreaSize); 276 if (area) { 277 fAreaCount++; 278 fFreeBytes += area->GetFreeBytes(); 279 bucket = fBuckets + area->GetBucketIndex(); 280 bucket->AddArea(area); 281PRINT(("New area allocated. area count now: %ld, free bytes: %lu\n", 282fAreaCount, fFreeBytes)); 283 } 284 } 285 // allocate a block 286 if (area) { 287 size_t areaFreeBytes = area->GetFreeBytes(); 288 bool needsDefragmenting = area->NeedsDefragmenting(); 289 block = area->AllocateBlock(usableSize); 290 // move the area into another bucket, if necessary 291 if (block) { 292 _RethinkAreaBucket(area, bucket, needsDefragmenting); 293 fFreeBytes = fFreeBytes + area->GetFreeBytes() - areaFreeBytes; 294 } 295#if ENABLE_BA_PANIC 296else if (!fPanic) { 297FATAL(("Block allocation failed unexpectedly.\n")); 298PRINT((" usableSize: %lu, areaFreeBytes: %lu\n", usableSize, areaFreeBytes)); 299BA_PANIC("Block allocation failed unexpectedly."); 300//block = area->AllocateBlock(usableSize); 301} 302#endif 303 } 304 return block; 305} 306 307// _FreeBlock 308void 309BlockAllocator::_FreeBlock(Area *area, Block *block, bool freeReference) 310{ 311 size_t areaFreeBytes = area->GetFreeBytes(); 312 AreaBucket *bucket = area->GetBucket(); 313 bool needsDefragmenting = area->NeedsDefragmenting(); 314 // free the block and the block reference 315 BlockReference *reference = block->GetReference(); 316 area->FreeBlock(block); 317 if (reference && freeReference) 318 fReferenceManager.FreeReference(reference); 319 // move the area into another bucket, if necessary 320 _RethinkAreaBucket(area, bucket, needsDefragmenting); 321 fFreeBytes = fFreeBytes + area->GetFreeBytes() - areaFreeBytes; 322} 323 324// _RethinkAreaBucket 325inline 326void 327BlockAllocator::_RethinkAreaBucket(Area *area, AreaBucket *bucket, 328 bool needsDefragmenting) 329{ 330 AreaBucket *newBucket = fBuckets + area->GetBucketIndex(); 331 if (newBucket != bucket 332 || needsDefragmenting != area->NeedsDefragmenting()) { 333 bucket->RemoveArea(area); 334 newBucket->AddArea(area); 335 } 336} 337 338// _DefragmentingRecommended 339inline 340bool 341BlockAllocator::_DefragmentingRecommended() 342{ 343 // Don't know, whether this makes much sense: We don't try to defragment, 344 // when not at least a complete area could be deleted, and some tolerance 345 // being left (a fixed value plus 1/32 of the used bytes). 346 size_t usedBytes = fAreaCount * Area::GetMaxFreeBytesFor(fAreaSize) 347 - fFreeBytes; 348 return (fFreeBytes > fAreaSize + kDefragmentingTolerance + usedBytes / 32); 349} 350 351// _Defragment 352bool 353BlockAllocator::_Defragment() 354{ 355 bool success = false; 356 // We try to empty the least populated area by moving its blocks to other 357 // areas. 358 if (fFreeBytes > fAreaSize) { 359 // find the least populated area 360 // find the bucket with the least populated areas 361 AreaBucket *bucket = NULL; 362 for (int32 i = fBucketCount - 1; i >= 0; i--) { 363 if (!fBuckets[i].IsEmpty()) { 364 bucket = fBuckets + i; 365 break; 366 } 367 } 368 // find the area in the bucket 369 Area *area = NULL; 370 if (bucket) { 371 area = bucket->GetFirstArea(); 372 Area *bucketArea = area; 373 while ((bucketArea = bucket->GetNextArea(bucketArea)) != NULL) { 374 if (bucketArea->GetFreeBytes() > area->GetFreeBytes()) 375 area = bucketArea; 376 } 377 } 378 if (area) { 379 // remove the area from the bucket 380 bucket->RemoveArea(area); 381 fFreeBytes -= area->GetFreeBytes(); 382 // iterate through the blocks in the area and try to find a new 383 // home for them 384 success = true; 385 while (Block *block = area->GetFirstUsedBlock()) { 386 Block *newBlock = _AllocateBlock(block->GetUsableSize(), true); 387 if (newBlock) { 388 // got a new block: copy the data to it and free the old 389 // one 390 memcpy(newBlock->GetData(), block->GetData(), 391 block->GetUsableSize()); 392 newBlock->SetReference(block->GetReference()); 393 block->SetReference(NULL); 394 area->FreeBlock(block, true); 395#if ENABLE_BA_PANIC 396 if (fPanic) { 397 PRINT(("Panicked while trying to free block %p\n", 398 block)); 399 success = false; 400 break; 401 } 402#endif 403 } else { 404 success = false; 405 break; 406 } 407 } 408 // delete the area 409 if (success && area->IsEmpty()) { 410 area->Delete(); 411 fAreaCount--; 412PRINT(("defragmenting: area deleted\n")); 413 } else { 414PRINT(("defragmenting: failed to empty area\n")); 415 // failed: re-add the area 416 fFreeBytes += area->GetFreeBytes(); 417 AreaBucket *newBucket = fBuckets + area->GetBucketIndex(); 418 newBucket->AddArea(area); 419 } 420 } 421 D(SanityCheck(false)); 422 } 423 return success; 424} 425 426#if ENABLE_BA_PANIC 427bool BlockAllocator::fPanic = false; 428#endif 429