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