boot/loader/heap.cpp

33 	big chunk, the only entry in the free link list (which is a single
35 	When memory is allocated, the smallest free chunk that contains
40 	free chunk available. When a chunk is freed, it will be joint
42 	To ease list handling, the list anchor itself is a free chunk with
118 	FreeChunkKey(const FreeChunk* chunk)
120 		fSize(chunk->Size()),
121 		fChunk(chunk)
125 	int Compare(const FreeChunk* chunk) const
127 		size_t chunkSize = chunk->Size();
131 		if (fChunk == chunk)
133 		return fChunk < chunk ? -1 : 1;
303 	in this chunk.
312 /*!	Splits the upper half at the requested location and returns it. This chunk
320 	FreeChunk* chunk = (FreeChunk*)((addr_t)AllocatedAddress() + splitSize);
321 	size_t newSize = (addr_t)chunk - (addr_t)this;
322 	chunk->fSize = fSize - newSize;
323 	chunk->fNext = NULL;
327 	return chunk;
331 /*!	Checks if the specified chunk touches this chunk, so
335 FreeChunk::IsTouching(FreeChunk* chunk)
337 	return chunk
338 		&& (((uint8*)this + fSize == (uint8*)chunk)
339 			|| (uint8*)chunk + chunk->fSize == (uint8*)this);
343 /*!	Joins the chunk to this chunk and returns the pointer
344 	to the new chunk - which will either be one of the
351 FreeChunk::Join(FreeChunk* chunk)
353 	if (chunk < this) {
354 		chunk->fSize += fSize;
355 		chunk->fNext = fNext;
357 		return chunk;
360 	fSize += chunk->fSize;
361 	fNext = chunk->fNext;
413 	// declare the whole heap as one chunk, and add it
415 	FreeChunk* chunk = (FreeChunk*)base;
416 	chunk->SetTo(sMaxHeapSize);
417 	sFreeChunkTree.Insert(chunk);
419 	sAvailable = chunk->Size();
435 	FreeChunk* chunk = sFreeChunkTree.FindMin();
436 	while (chunk != NULL) {
437 		printf("\t%p: chunk size = %ld, end = %p, next = %p\n", chunk,
438 			chunk->Size(), (uint8*)chunk + chunk->CompleteSize(),
439 			chunk->Next());
440 		chunk = chunk->Next();
472 	FreeChunk* chunk = sFreeChunkTree.FindClosest(FreeChunkKey(size), true,
475 	if (chunk == NULL) {
476 		// could not find a free chunk as large as needed
482 	sFreeChunkTree.Remove(chunk);
483 	sAvailable -= chunk->Size();
485 	void* allocatedAddress = chunk->AllocatedAddress();
487 	// If this chunk is bigger than the requested size and there's enough space
488 	// left over for a new chunk, we split it.
489 	if (chunk->Size() >= size + align(sizeof(FreeChunk))) {
490 		FreeChunk* freeChunk = chunk->Split(size);
579 		panic("freed chunk %p clobbered (%#zx)!\n", freedChunk,
583 		FreeChunk* chunk = sFreeChunkTree.FindMin();
584 		while (chunk) {
585 			if (chunk->Size() > sAvailable || freedChunk == chunk)
586 				panic("invalid chunk in free list (%p (%zu)), or double free\n",
587 					chunk, chunk->Size());
588 			chunk = chunk->Next();
593 	// try to join the new free chunk with an existing one
596 	FreeChunk* chunk = sFreeChunkTree.FindMin();
599 	while (chunk) {
600 		FreeChunk* nextChunk = chunk->Next();
602 		if (chunk->IsTouching(freedChunk)) {
603 			sFreeChunkTree.Remove(chunk);
604 			sAvailable -= chunk->Size();
606 			freedChunk = chunk->Join(freedChunk);
612 		chunk = nextChunk;