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