16f0994d4SAxel Dörfler/*
228d3c8caSMichael Lotz * Copyright 2003-2013, Axel D��rfler, axeld@pinc-software.de.
36f0994d4SAxel Dörfler * Distributed under the terms of the MIT License.
46f0994d4SAxel Dörfler */
56f0994d4SAxel Dörfler
66f0994d4SAxel Dörfler
76f0994d4SAxel Dörfler#include "runtime_loader_private.h"
86f0994d4SAxel Dörfler
96f0994d4SAxel Dörfler#include <syscalls.h>
106f0994d4SAxel Dörfler
1128d3c8caSMichael Lotz#ifdef HEAP_TEST
1228d3c8caSMichael Lotz#	include <stdio.h>
1328d3c8caSMichael Lotz#endif
146f0994d4SAxel Dörfler#include <stdlib.h>
156f0994d4SAxel Dörfler#include <string.h>
166f0994d4SAxel Dörfler
1728d3c8caSMichael Lotz#include <algorithm>
1828d3c8caSMichael Lotz
1928d3c8caSMichael Lotz#include <util/SplayTree.h>
2028d3c8caSMichael Lotz
21df3de479SAugustin Cavalier#include <locks.h>
22df3de479SAugustin Cavalier
2328d3c8caSMichael Lotz
2428d3c8caSMichael Lotz/*!	This is a very simple malloc()/free() implementation - it only
2528d3c8caSMichael Lotz	manages a free list.
2628d3c8caSMichael Lotz	After heap_init() is called, all free memory is contained in one
2728d3c8caSMichael Lotz	big chunk, the only entry in the free link list (which is a single
2828d3c8caSMichael Lotz	linked list).
2928d3c8caSMichael Lotz	When memory is allocated, the smallest free chunk that contains
3028d3c8caSMichael Lotz	the requested size is split (or taken as a whole if it can't be
3128d3c8caSMichael Lotz	splitted anymore), and it's lower half will be removed from the
3228d3c8caSMichael Lotz	free list.
3328d3c8caSMichael Lotz	The free list is ordered by size, starting with the smallest
3428d3c8caSMichael Lotz	free chunk available. When a chunk is freed, it will be joint
3528d3c8caSMichael Lotz	with its predecessor or successor, if possible.
3628d3c8caSMichael Lotz	To ease list handling, the list anchor itself is a free chunk with
3728d3c8caSMichael Lotz	size 0 that can't be allocated.
3828d3c8caSMichael Lotz*/
3928d3c8caSMichael Lotzconst static size_t kAlignment = 8;
4028d3c8caSMichael Lotz	// all memory chunks will be a multiple of this
4128d3c8caSMichael Lotz
4228d3c8caSMichael Lotzconst static size_t kInitialHeapSize = 64 * 1024;
4328d3c8caSMichael Lotzconst static size_t kHeapGrowthAlignment = 32 * 1024;
4428d3c8caSMichael Lotz
45df3de479SAugustin Cavalierstatic const char* const kLockName = "runtime_loader heap";
46df3de479SAugustin Cavalierstatic recursive_lock sLock = RECURSIVE_LOCK_INITIALIZER(kLockName);
47df3de479SAugustin Cavalier
4828d3c8caSMichael Lotz
4928d3c8caSMichael Lotzclass Chunk {
5028d3c8caSMichael Lotzpublic:
5128d3c8caSMichael Lotz	size_t CompleteSize() const
5228d3c8caSMichael Lotz	{
5328d3c8caSMichael Lotz		return fSize;
5428d3c8caSMichael Lotz	}
556f0994d4SAxel Dörfler
5628d3c8caSMichael Lotzprotected:
5728d3c8caSMichael Lotz	union {
5828d3c8caSMichael Lotz		size_t	fSize;
5928d3c8caSMichael Lotz		char	fAlignment[kAlignment];
6028d3c8caSMichael Lotz	};
6128d3c8caSMichael Lotz};
626f0994d4SAxel Dörfler
636f0994d4SAxel Dörfler
6428d3c8caSMichael Lotzclass FreeChunk;
6528d3c8caSMichael Lotz
666f0994d4SAxel Dörfler
6728d3c8caSMichael Lotzstruct FreeChunkData : SplayTreeLink<FreeChunk> {
686f0994d4SAxel Dörfler
6928d3c8caSMichael Lotz	FreeChunk* Next() const
7028d3c8caSMichael Lotz	{
7128d3c8caSMichael Lotz		return fNext;
7228d3c8caSMichael Lotz	}
736f0994d4SAxel Dörfler
7428d3c8caSMichael Lotz	FreeChunk** NextLink()
7528d3c8caSMichael Lotz	{
7628d3c8caSMichael Lotz		return &fNext;
7728d3c8caSMichael Lotz	}
786f0994d4SAxel Dörfler
7928d3c8caSMichael Lotzprotected:
8028d3c8caSMichael Lotz	FreeChunk*	fNext;
816f0994d4SAxel Dörfler};
826f0994d4SAxel Dörfler
836f0994d4SAxel Dörfler
8428d3c8caSMichael Lotzclass FreeChunk : public Chunk, public FreeChunkData {
8528d3c8caSMichael Lotzpublic:
8628d3c8caSMichael Lotz			void				SetTo(size_t size);
876f0994d4SAxel Dörfler
8828d3c8caSMichael Lotz			size_t				Size() const;
896f0994d4SAxel Dörfler
9028d3c8caSMichael Lotz			FreeChunk*			Split(size_t splitSize);
9128d3c8caSMichael Lotz			bool				IsTouching(FreeChunk* link);
9228d3c8caSMichael Lotz			FreeChunk*			Join(FreeChunk* link);
936f0994d4SAxel Dörfler
9428d3c8caSMichael Lotz			void*				AllocatedAddress() const;
9528d3c8caSMichael Lotz	static	FreeChunk*			SetToAllocated(void* allocated);
9628d3c8caSMichael Lotz};
976f0994d4SAxel Dörfler
986f0994d4SAxel Dörfler
9928d3c8caSMichael Lotzstruct FreeChunkKey {
10028d3c8caSMichael Lotz	FreeChunkKey(size_t size)
10128d3c8caSMichael Lotz		:
10228d3c8caSMichael Lotz		fSize(size),
10328d3c8caSMichael Lotz		fChunk(NULL)
10428d3c8caSMichael Lotz	{
10528d3c8caSMichael Lotz	}
1066f0994d4SAxel Dörfler
10728d3c8caSMichael Lotz	FreeChunkKey(const FreeChunk* chunk)
10828d3c8caSMichael Lotz		:
10928d3c8caSMichael Lotz		fSize(chunk->Size()),
11028d3c8caSMichael Lotz		fChunk(chunk)
11128d3c8caSMichael Lotz	{
11228d3c8caSMichael Lotz	}
1136f0994d4SAxel Dörfler
11428d3c8caSMichael Lotz	int Compare(const FreeChunk* chunk) const
11528d3c8caSMichael Lotz	{
11628d3c8caSMichael Lotz		size_t chunkSize = chunk->Size();
11728d3c8caSMichael Lotz		if (chunkSize != fSize)
11828d3c8caSMichael Lotz			return fSize < chunkSize ? -1 : 1;
1196f0994d4SAxel Dörfler
12028d3c8caSMichael Lotz		if (fChunk == chunk)
12128d3c8caSMichael Lotz			return 0;
12228d3c8caSMichael Lotz		return fChunk < chunk ? -1 : 1;
12328d3c8caSMichael Lotz	}
1246f0994d4SAxel Dörfler
12528d3c8caSMichael Lotzprivate:
12628d3c8caSMichael Lotz	size_t				fSize;
12728d3c8caSMichael Lotz	const FreeChunk*	fChunk;
12828d3c8caSMichael Lotz};
1296f0994d4SAxel Dörfler
1306f0994d4SAxel Dörfler
13128d3c8caSMichael Lotzstruct FreeChunkTreeDefinition {
13228d3c8caSMichael Lotz	typedef FreeChunkKey	KeyType;
13328d3c8caSMichael Lotz	typedef FreeChunk		NodeType;
1346f0994d4SAxel Dörfler
13528d3c8caSMichael Lotz	static FreeChunkKey GetKey(const FreeChunk* node)
13628d3c8caSMichael Lotz	{
13728d3c8caSMichael Lotz		return FreeChunkKey(node);
13828d3c8caSMichael Lotz	}
1396f0994d4SAxel Dörfler
14028d3c8caSMichael Lotz	static SplayTreeLink<FreeChunk>* GetLink(FreeChunk* node)
14128d3c8caSMichael Lotz	{
14228d3c8caSMichael Lotz		return node;
14328d3c8caSMichael Lotz	}
1446f0994d4SAxel Dörfler
14528d3c8caSMichael Lotz	static int Compare(const FreeChunkKey& key, const FreeChunk* node)
14628d3c8caSMichael Lotz	{
14728d3c8caSMichael Lotz		return key.Compare(node);
14828d3c8caSMichael Lotz	}
1496f0994d4SAxel Dörfler
15028d3c8caSMichael Lotz	static FreeChunk** GetListLink(FreeChunk* node)
15128d3c8caSMichael Lotz	{
15228d3c8caSMichael Lotz		return node->NextLink();
1536f0994d4SAxel Dörfler	}
15428d3c8caSMichael Lotz};
1556f0994d4SAxel Dörfler
1566f0994d4SAxel Dörfler
15728d3c8caSMichael Lotztypedef IteratableSplayTree<FreeChunkTreeDefinition> FreeChunkTree;
15828d3c8caSMichael Lotz
15928d3c8caSMichael Lotz
16028d3c8caSMichael Lotzstatic size_t sAvailable;
16128d3c8caSMichael Lotzstatic FreeChunkTree sFreeChunkTree;
16228d3c8caSMichael Lotz
16328d3c8caSMichael Lotz
16428d3c8caSMichael Lotzstatic inline size_t
16528d3c8caSMichael Lotzalign(size_t size, size_t alignment = kAlignment)
16628d3c8caSMichael Lotz{
16728d3c8caSMichael Lotz	return (size + alignment - 1) & ~(alignment - 1);
1686f0994d4SAxel Dörfler}
1696f0994d4SAxel Dörfler
1706f0994d4SAxel Dörfler
171f68fa9d3SIngo Weinholdvoid
17228d3c8caSMichael LotzFreeChunk::SetTo(size_t size)
1736f0994d4SAxel Dörfler{
17428d3c8caSMichael Lotz	fSize = size;
17528d3c8caSMichael Lotz	fNext = NULL;
17628d3c8caSMichael Lotz}
1776f0994d4SAxel Dörfler
1786f0994d4SAxel Dörfler
17928d3c8caSMichael Lotz/*!	Returns the amount of bytes that can be allocated
18028d3c8caSMichael Lotz	in this chunk.
18128d3c8caSMichael Lotz*/
18228d3c8caSMichael Lotzsize_t
18328d3c8caSMichael LotzFreeChunk::Size() const
18428d3c8caSMichael Lotz{
18528d3c8caSMichael Lotz	return (addr_t)this + fSize - (addr_t)AllocatedAddress();
18628d3c8caSMichael Lotz}
18728d3c8caSMichael Lotz
18828d3c8caSMichael Lotz
18928d3c8caSMichael Lotz/*!	Splits the upper half at the requested location and returns it. This chunk
19028d3c8caSMichael Lotz	will no longer be a valid FreeChunk object; only its fSize will be valid.
19128d3c8caSMichael Lotz */
19228d3c8caSMichael LotzFreeChunk*
19328d3c8caSMichael LotzFreeChunk::Split(size_t splitSize)
19428d3c8caSMichael Lotz{
19528d3c8caSMichael Lotz	splitSize = align(splitSize);
19628d3c8caSMichael Lotz
19728d3c8caSMichael Lotz	FreeChunk* chunk = (FreeChunk*)((addr_t)AllocatedAddress() + splitSize);
19828d3c8caSMichael Lotz	size_t newSize = (addr_t)chunk - (addr_t)this;
19928d3c8caSMichael Lotz	chunk->fSize = fSize - newSize;
20028d3c8caSMichael Lotz	chunk->fNext = NULL;
20128d3c8caSMichael Lotz
20228d3c8caSMichael Lotz	fSize = newSize;
2036f0994d4SAxel Dörfler
20428d3c8caSMichael Lotz	return chunk;
2056f0994d4SAxel Dörfler}
2066f0994d4SAxel Dörfler
2076f0994d4SAxel Dörfler
20828d3c8caSMichael Lotz/*!	Checks if the specified chunk touches this chunk, so
20928d3c8caSMichael Lotz	that they could be joined.
21028d3c8caSMichael Lotz*/
21128d3c8caSMichael Lotzbool
21228d3c8caSMichael LotzFreeChunk::IsTouching(FreeChunk* chunk)
21328d3c8caSMichael Lotz{
21428d3c8caSMichael Lotz	return chunk
21528d3c8caSMichael Lotz		&& (((uint8*)this + fSize == (uint8*)chunk)
21628d3c8caSMichael Lotz			|| (uint8*)chunk + chunk->fSize == (uint8*)this);
21728d3c8caSMichael Lotz}
21828d3c8caSMichael Lotz
21928d3c8caSMichael Lotz
22028d3c8caSMichael Lotz/*!	Joins the chunk to this chunk and returns the pointer
22128d3c8caSMichael Lotz	to the new chunk - which will either be one of the
22228d3c8caSMichael Lotz	two chunks.
22328d3c8caSMichael Lotz	Note, the chunks must be joinable, or else this method
22428d3c8caSMichael Lotz	doesn't work correctly. Use FreeChunk::IsTouching()
22528d3c8caSMichael Lotz	to check if this method can be applied.
22628d3c8caSMichael Lotz*/
22728d3c8caSMichael LotzFreeChunk*
22828d3c8caSMichael LotzFreeChunk::Join(FreeChunk* chunk)
2296f0994d4SAxel Dörfler{
23028d3c8caSMichael Lotz	if (chunk < this) {
23128d3c8caSMichael Lotz		chunk->fSize += fSize;
23228d3c8caSMichael Lotz		chunk->fNext = fNext;
23328d3c8caSMichael Lotz
23428d3c8caSMichael Lotz		return chunk;
2356f0994d4SAxel Dörfler	}
2366f0994d4SAxel Dörfler
23728d3c8caSMichael Lotz	fSize += chunk->fSize;
23828d3c8caSMichael Lotz	fNext = chunk->fNext;
23928d3c8caSMichael Lotz
24028d3c8caSMichael Lotz	return this;
2416f0994d4SAxel Dörfler}
2426f0994d4SAxel Dörfler
2436f0994d4SAxel Dörfler
24428d3c8caSMichael Lotzvoid*
24528d3c8caSMichael LotzFreeChunk::AllocatedAddress() const
2466f0994d4SAxel Dörfler{
24728d3c8caSMichael Lotz	return (void*)static_cast<const FreeChunkData*>(this);
2486f0994d4SAxel Dörfler}
2496f0994d4SAxel Dörfler
2506f0994d4SAxel Dörfler
25128d3c8caSMichael LotzFreeChunk*
25228d3c8caSMichael LotzFreeChunk::SetToAllocated(void* allocated)
2536f0994d4SAxel Dörfler{
25428d3c8caSMichael Lotz	return static_cast<FreeChunk*>((FreeChunkData*)allocated);
2556f0994d4SAxel Dörfler}
2566f0994d4SAxel Dörfler
2576f0994d4SAxel Dörfler
25828d3c8caSMichael Lotz//	#pragma mark -
2596f0994d4SAxel Dörfler
2606f0994d4SAxel Dörfler
2615cfd3a15SAxel Dörflerstatic status_t
2625cfd3a15SAxel Dörfleradd_area(size_t size)
2636f0994d4SAxel Dörfler{
26428d3c8caSMichael Lotz	void* base;
2659f3bd497SPawel Dziepak	area_id area = _kern_create_area("rld heap", &base,
26728d3c8caSMichael Lotz	if (area < 0)
2686f0994d4SAxel Dörfler		return area;
2696f0994d4SAxel Dörfler
27028d3c8caSMichael Lotz	// declare the whole area as one chunk, and add it to the free tree
27128d3c8caSMichael Lotz	FreeChunk* chunk = (FreeChunk*)base;
27228d3c8caSMichael Lotz	chunk->SetTo(size);
27328d3c8caSMichael Lotz	sFreeChunkTree.Insert(chunk);
2746f0994d4SAxel Dörfler
27528d3c8caSMichael Lotz	sAvailable += chunk->Size();
2766f0994d4SAxel Dörfler	return B_OK;
2776f0994d4SAxel Dörfler}
2786f0994d4SAxel Dörfler
2796f0994d4SAxel Dörfler
2805cfd3a15SAxel Dörflerstatic status_t
28112b3e8a8SAlex Smithgrow_heap(size_t bytes)
2826f0994d4SAxel Dörfler{
28328d3c8caSMichael Lotz	return add_area(align(align(sizeof(Chunk)) + bytes, kHeapGrowthAlignment));
2845cfd3a15SAxel Dörfler}
2856f0994d4SAxel Dörfler
2866f0994d4SAxel Dörfler
28728d3c8caSMichael Lotz//	#pragma mark -
2886f0994d4SAxel Dörfler
2895cfd3a15SAxel Dörfler
2905cfd3a15SAxel Dörflerstatus_t
29132560010SAugustin Cavalierheap_init()
2925cfd3a15SAxel Dörfler{
29328d3c8caSMichael Lotz	return add_area(kInitialHeapSize);
2946f0994d4SAxel Dörfler}
2955cfd3a15SAxel Dörfler
2966f0994d4SAxel Dörfler
29732560010SAugustin Cavalierstatus_t
29832560010SAugustin Cavalierheap_reinit_after_fork()
29932560010SAugustin Cavalier{
30032560010SAugustin Cavalier	recursive_lock_init(&sLock, kLockName);
30132560010SAugustin Cavalier	return B_OK;
30232560010SAugustin Cavalier}
30332560010SAugustin Cavalier
30432560010SAugustin Cavalier
3056f0994d4SAxel Dörfler#ifdef HEAP_TEST
3066f0994d4SAxel Dörflervoid
3076f0994d4SAxel Dörflerdump_chunks(void)
3086f0994d4SAxel Dörfler{
30928d3c8caSMichael Lotz	FreeChunk* chunk = sFreeChunkTree.FindMin();
3106f0994d4SAxel Dörfler	while (chunk != NULL) {
31128d3c8caSMichael Lotz		printf("\t%p: chunk size = %ld, end = %p, next = %p\n", chunk,
31228d3c8caSMichael Lotz			chunk->Size(), (uint8*)chunk + chunk->CompleteSize(),
31328d3c8caSMichael Lotz			chunk->Next());
31428d3c8caSMichael Lotz		chunk = chunk->Next();
3156f0994d4SAxel Dörfler	}
3166f0994d4SAxel Dörfler}
3176f0994d4SAxel Dörfler#endif
3186f0994d4SAxel Dörfler
3196f0994d4SAxel Dörfler
32028d3c8caSMichael Lotzvoid*
3216f0994d4SAxel Dörflermalloc(size_t size)
3226f0994d4SAxel Dörfler{
3235cfd3a15SAxel Dörfler	if (size == 0)
3246f0994d4SAxel Dörfler		return NULL;
3256f0994d4SAxel Dörfler
326df3de479SAugustin Cavalier	RecursiveLocker _(sLock);
327df3de479SAugustin Cavalier
32828d3c8caSMichael Lotz	// align the size requirement to a kAlignment bytes boundary
32928d3c8caSMichael Lotz	if (size < sizeof(FreeChunkData))
33028d3c8caSMichael Lotz		size = sizeof(FreeChunkData);
33128d3c8caSMichael Lotz	size = align(size);
3326f0994d4SAxel Dörfler
3335cfd3a15SAxel Dörfler	if (size > sAvailable) {
3345cfd3a15SAxel Dörfler		// try to enlarge heap
33528d3c8caSMichael Lotz		if (grow_heap(size) != B_OK)
3365cfd3a15SAxel Dörfler			return NULL;
3375cfd3a15SAxel Dörfler	}
3386f0994d4SAxel Dörfler
33928d3c8caSMichael Lotz	FreeChunkKey key(size);
34028d3c8caSMichael Lotz	FreeChunk* chunk = sFreeChunkTree.FindClosest(key, true, true);
3416f0994d4SAxel Dörfler	if (chunk == NULL) {
3426f0994d4SAxel Dörfler		// could not find a free chunk as large as needed
34328d3c8caSMichael Lotz		if (grow_heap(size) != B_OK)
3445cfd3a15SAxel Dörfler			return NULL;
3455cfd3a15SAxel Dörfler
34628d3c8caSMichael Lotz		chunk = sFreeChunkTree.FindClosest(key, true, true);
34728d3c8caSMichael Lotz		if (chunk == NULL) {
34828d3c8caSMichael Lotz			TRACE(("no allocation chunk found after growing the heap\n"));
34928d3c8caSMichael Lotz			return NULL;
35028d3c8caSMichael Lotz		}
3516f0994d4SAxel Dörfler	}
3526f0994d4SAxel Dörfler
35328d3c8caSMichael Lotz	sFreeChunkTree.Remove(chunk);
35428d3c8caSMichael Lotz	sAvailable -= chunk->Size();
3556f0994d4SAxel Dörfler
35628d3c8caSMichael Lotz	void* allocatedAddress = chunk->AllocatedAddress();
35728d3c8caSMichael Lotz
35828d3c8caSMichael Lotz	// If this chunk is bigger than the requested size and there's enough space
35928d3c8caSMichael Lotz	// left over for a new chunk, we split it.
36028d3c8caSMichael Lotz	if (chunk->Size() >= size + align(sizeof(FreeChunk))) {
36128d3c8caSMichael Lotz		FreeChunk* freeChunk = chunk->Split(size);
36228d3c8caSMichael Lotz		sFreeChunkTree.Insert(freeChunk);
36328d3c8caSMichael Lotz		sAvailable += freeChunk->Size();
36428d3c8caSMichael Lotz	}
36528d3c8caSMichael Lotz
36628d3c8caSMichael Lotz	TRACE(("malloc(%lu) -> %p\n", size, allocatedAddress));
36728d3c8caSMichael Lotz	return allocatedAddress;
36828d3c8caSMichael Lotz}
3696f0994d4SAxel Dörfler
3706f0994d4SAxel Dörfler
37128d3c8caSMichael Lotzvoid*
37228d3c8caSMichael Lotzrealloc(void* oldBuffer, size_t newSize)
37328d3c8caSMichael Lotz{
37428d3c8caSMichael Lotz	if (newSize == 0) {
37528d3c8caSMichael Lotz		TRACE(("realloc(%p, %lu) -> NULL\n", oldBuffer, newSize));
37628d3c8caSMichael Lotz		free(oldBuffer);
37728d3c8caSMichael Lotz		return NULL;
3786f0994d4SAxel Dörfler	}
3796f0994d4SAxel Dörfler
380df3de479SAugustin Cavalier	RecursiveLocker _(sLock);
381df3de479SAugustin Cavalier
38228d3c8caSMichael Lotz	size_t oldSize = 0;
38328d3c8caSMichael Lotz	if (oldBuffer != NULL) {
38428d3c8caSMichael Lotz		FreeChunk* oldChunk = FreeChunk::SetToAllocated(oldBuffer);
38528d3c8caSMichael Lotz		oldSize = oldChunk->Size();
38628d3c8caSMichael Lotz
38728d3c8caSMichael Lotz		// Check if the old buffer still fits, and if it makes sense to keep it.
38828d3c8caSMichael Lotz		if (oldSize >= newSize
38928d3c8caSMichael Lotz			&& (oldSize < 128 || newSize > oldSize / 3)) {
39028d3c8caSMichael Lotz			TRACE(("realloc(%p, %lu) old buffer is large enough\n",
39128d3c8caSMichael Lotz				oldBuffer, newSize));
39228d3c8caSMichael Lotz			return oldBuffer;
39328d3c8caSMichael Lotz		}
39428d3c8caSMichael Lotz	}
39528d3c8caSMichael Lotz
39628d3c8caSMichael Lotz	void* newBuffer = malloc(newSize);
39728d3c8caSMichael Lotz	if (newBuffer == NULL)
39828d3c8caSMichael Lotz		return NULL;
3996f0994d4SAxel Dörfler
40028d3c8caSMichael Lotz	if (oldBuffer != NULL) {
40128d3c8caSMichael Lotz		memcpy(newBuffer, oldBuffer, std::min(oldSize, newSize));
40228d3c8caSMichael Lotz		free(oldBuffer);
40328d3c8caSMichael Lotz	}
40428d3c8caSMichael Lotz
40528d3c8caSMichael Lotz	TRACE(("realloc(%p, %lu) -> %p\n", oldBuffer, newSize, newBuffer));
40628d3c8caSMichael Lotz	return newBuffer;
4076f0994d4SAxel Dörfler}
4086f0994d4SAxel Dörfler
4096f0994d4SAxel Dörfler
4106f0994d4SAxel Dörflervoid
41128d3c8caSMichael Lotzfree(void* allocated)
4126f0994d4SAxel Dörfler{
4136f0994d4SAxel Dörfler	if (allocated == NULL)
4146f0994d4SAxel Dörfler		return;
4156f0994d4SAxel Dörfler
416df3de479SAugustin Cavalier	RecursiveLocker _(sLock);
417df3de479SAugustin Cavalier
41828d3c8caSMichael Lotz	TRACE(("free(%p)\n", allocated));
41928d3c8caSMichael Lotz
42028d3c8caSMichael Lotz
42128d3c8caSMichael Lotz	FreeChunk* freedChunk = FreeChunk::SetToAllocated(allocated);
4226f0994d4SAxel Dörfler
4236f0994d4SAxel Dörfler	// try to join the new free chunk with an existing one
4246f0994d4SAxel Dörfler	// it may be joined with up to two chunks
4256f0994d4SAxel Dörfler
42628d3c8caSMichael Lotz	FreeChunk* chunk = sFreeChunkTree.FindMin();
4276f0994d4SAxel Dörfler	int32 joinCount = 0;
4286f0994d4SAxel Dörfler
4296f0994d4SAxel Dörfler	while (chunk) {
43028d3c8caSMichael Lotz		FreeChunk* nextChunk = chunk->Next();
43128d3c8caSMichael Lotz
4326f0994d4SAxel Dörfler		if (chunk->IsTouching(freedChunk)) {
43328d3c8caSMichael Lotz			sFreeChunkTree.Remove(chunk);
43428d3c8caSMichael Lotz			sAvailable -= chunk->Size();
4356f0994d4SAxel Dörfler
43628d3c8caSMichael Lotz			freedChunk = chunk->Join(freedChunk);
437f68fa9d3SIngo Weinhold
4386f0994d4SAxel Dörfler			if (++joinCount == 2)
4396f0994d4SAxel Dörfler				break;
4406f0994d4SAxel Dörfler		}
4416f0994d4SAxel Dörfler
44228d3c8caSMichael Lotz		chunk = nextChunk;
4436f0994d4SAxel Dörfler	}
4446f0994d4SAxel Dörfler
44528d3c8caSMichael Lotz	sFreeChunkTree.Insert(freedChunk);
44628d3c8caSMichael Lotz	sAvailable += freedChunk->Size();
4476f0994d4SAxel Dörfler}