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