system/runtime_loader/heap.cpp

27 	big chunk, the only entry in the free link list (which is a single
29 	When memory is allocated, the smallest free chunk that contains
34 	free chunk available. When a chunk is freed, it will be joint
36 	To ease list handling, the list anchor itself is a free chunk with
112 	FreeChunkKey(const FreeChunk* chunk)
114 		fSize(chunk->Size()),
115 		fChunk(chunk)
119 	int Compare(const FreeChunk* chunk) const
121 		size_t chunkSize = chunk->Size();
125 		if (fChunk == chunk)
127 		return fChunk < chunk ? -1 : 1;
185 	in this chunk.
194 /*!	Splits the upper half at the requested location and returns it. This chunk
202 	FreeChunk* chunk = (FreeChunk*)((addr_t)AllocatedAddress() + splitSize);
203 	size_t newSize = (addr_t)chunk - (addr_t)this;
204 	chunk->fSize = fSize - newSize;
205 	chunk->fNext = NULL;
209 	return chunk;
213 /*!	Checks if the specified chunk touches this chunk, so
217 FreeChunk::IsTouching(FreeChunk* chunk)
219 	return chunk
220 		&& (((uint8*)this + fSize == (uint8*)chunk)
221 			|| (uint8*)chunk + chunk->fSize == (uint8*)this);
225 /*!	Joins the chunk to this chunk and returns the pointer
226 	to the new chunk - which will either be one of the
233 FreeChunk::Join(FreeChunk* chunk)
235 	if (chunk < this) {
236 		chunk->fSize += fSize;
237 		chunk->fNext = fNext;
239 		return chunk;
242 	fSize += chunk->fSize;
243 	fNext = chunk->fNext;
275 	// declare the whole area as one chunk, and add it to the free tree
276 	FreeChunk* chunk = (FreeChunk*)base;
277 	chunk->SetTo(size);
278 	sFreeChunkTree.Insert(chunk);
280 	sAvailable += chunk->Size();
314 	FreeChunk* chunk = sFreeChunkTree.FindMin();
315 	while (chunk != NULL) {
316 		printf("\t%p: chunk size = %ld, end = %p, next = %p\n", chunk,
317 			chunk->Size(), (uint8*)chunk + chunk->CompleteSize(),
318 			chunk->Next());
319 		chunk = chunk->Next();
345 	FreeChunk* chunk = sFreeChunkTree.FindClosest(key, true, true);
346 	if (chunk == NULL) {
347 		// could not find a free chunk as large as needed
351 		chunk = sFreeChunkTree.FindClosest(key, true, true);
352 		if (chunk == NULL) {
353 			TRACE(("no allocation chunk found after growing the heap\n"));
358 	sFreeChunkTree.Remove(chunk);
359 	sAvailable -= chunk->Size();
361 	void* allocatedAddress = chunk->AllocatedAddress();
363 	// If this chunk is bigger than the requested size and there's enough space
364 	// left over for a new chunk, we split it.
365 	if (chunk->Size() >= size + align(sizeof(FreeChunk))) {
366 		FreeChunk* freeChunk = chunk->Split(size);
428 	// try to join the new free chunk with an existing one
431 	FreeChunk* chunk = sFreeChunkTree.FindMin();
434 	while (chunk) {
435 		FreeChunk* nextChunk = chunk->Next();
437 		if (chunk->IsTouching(freedChunk)) {
438 			sFreeChunkTree.Remove(chunk);
439 			sAvailable -= chunk->Size();
441 			freedChunk = chunk->Join(freedChunk);
447 		chunk = nextChunk;