malloc/debug/heap.cpp

/*
 * Copyright 2008-2009, Michael Lotz, mmlr@mlotz.ch.
 * Distributed under the terms of the MIT License.
 *
 * Copyright 2002-2011, Axel Dörfler, axeld@pinc-software.de.
 * Distributed under the terms of the MIT License.
 *
 * Copyright 2001, Travis Geiselbrecht. All rights reserved.
 * Distributed under the terms of the NewOS License.
 */


#include "malloc_debug_api.h"

#include <malloc.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include <errno.h>
#include <sys/mman.h>

#include <errno_private.h>
#include <locks.h>
#include <syscalls.h>

#include <Debug.h>
#include <OS.h>


//#define TRACE_HEAP
#ifdef TRACE_HEAP
#	define INFO(x) debug_printf x
#else
#	define INFO(x) ;
#endif

#undef ASSERT
#define ASSERT(x)	if (!(x)) panic("assert failed: %s", #x);


static void *debug_heap_memalign(size_t alignment, size_t size);


static bool sDebuggerCalls = true;
static bool sReuseMemory = true;
static bool sParanoidValidation = false;
static thread_id sWallCheckThread = -1;
static bool sStopWallChecking = false;
static bool sUseGuardPage = false;

#if __cplusplus >= 201103L
#include <cstddef>
using namespace std;
static size_t sDefaultAlignment = alignof(max_align_t);
#else
static size_t sDefaultAlignment = 8;
#endif


void
panic(const char *format, ...)
{
	char buffer[1024];

	va_list args;
	va_start(args, format);
	vsnprintf(buffer, sizeof(buffer), format, args);
	va_end(args);

	if (sDebuggerCalls)
		debugger(buffer);
	else
		debug_printf("%s", buffer);
}


#define ROUNDUP(x, y)		(((x) + (y) - 1) / (y) * (y))

#define HEAP_INITIAL_SIZE			1 * 1024 * 1024
#define HEAP_GROW_SIZE				2 * 1024 * 1024
#define HEAP_AREA_USE_THRESHOLD		1 * 1024 * 1024

typedef struct heap_leak_check_info_s {
	size_t		size;
	thread_id	thread;
} heap_leak_check_info;

typedef struct heap_page_s heap_page;

typedef struct heap_area_s {
	area_id			area;

	addr_t			base;
	size_t			size;

	uint32			page_count;
	uint32			free_page_count;

	heap_page *		free_pages;
	heap_page *		page_table;

	heap_area_s *	prev;
	heap_area_s *	next;
	heap_area_s *	all_next;
} heap_area;

typedef struct heap_page_s {
	heap_area *		area;
	uint16			index;
	uint16			bin_index : 5;
	uint16			free_count : 10;
	uint16			in_use : 1;
	heap_page_s *	next;
	heap_page_s *	prev;
	union {
		uint16			empty_index;
		uint16			allocation_id; // used for bin == bin_count allocations
	};
	addr_t *		free_list;
} heap_page;

typedef struct heap_bin_s {
	mutex		lock;
	uint32		element_size;
	uint16		max_free_count;
	heap_page *	page_list; // sorted so that the desired page is always first
} heap_bin;

typedef struct heap_allocator_s {
	rw_lock		area_lock;
	mutex		page_lock;

	const char *name;
	uint32		bin_count;
	uint32		page_size;

	uint32		total_pages;
	uint32		total_free_pages;
	uint32		empty_areas;

	heap_bin *	bins;
	heap_area *	areas; // sorted so that the desired area is always first
	heap_area *	all_areas; // all areas including full ones
} heap_allocator;

static const uint32 kAreaAllocationMagic = 'AAMG';
typedef struct area_allocation_info_s {
	area_id		area;
	void *		base;
	uint32		magic;
	size_t		size;
	thread_id	thread;
	size_t		allocation_size;
	size_t		allocation_alignment;
	void *		allocation_base;
} area_allocation_info;

typedef struct heap_class_s {
	const char *name;
	uint32		initial_percentage;
	size_t		max_allocation_size;
	size_t		page_size;
	size_t		min_bin_size;
	size_t		bin_alignment;
	uint32		min_count_per_page;
	size_t		max_waste_per_page;
} heap_class;

// Heap class configuration
#define HEAP_CLASS_COUNT 3
static const heap_class sHeapClasses[HEAP_CLASS_COUNT] = {
	{
		"small",					/* name */
		50,							/* initial percentage */
		B_PAGE_SIZE / 8,			/* max allocation size */
		B_PAGE_SIZE,				/* page size */
		8,							/* min bin size */
		4,							/* bin alignment */
		8,							/* min count per page */
		16							/* max waste per page */
	},
	{
		"medium",					/* name */
		30,							/* initial percentage */
		B_PAGE_SIZE * 2,			/* max allocation size */
		B_PAGE_SIZE * 8,			/* page size */
		B_PAGE_SIZE / 8,			/* min bin size */
		32,							/* bin alignment */
		4,							/* min count per page */
		64							/* max waste per page */
	},
	{
		"large",					/* name */
		20,							/* initial percentage */
		HEAP_AREA_USE_THRESHOLD,	/* max allocation size */
		B_PAGE_SIZE * 16,			/* page size */
		B_PAGE_SIZE * 2,			/* min bin size */
		128,						/* bin alignment */
		1,							/* min count per page */
		256							/* max waste per page */
	}
};

static heap_allocator *sHeaps[HEAP_CLASS_COUNT];


// #pragma mark - Debug functions


static void
dump_page(heap_page *page)
{
	uint32 count = 0;
	for (addr_t *temp = page->free_list; temp != NULL; temp = (addr_t *)*temp)
		count++;

	printf("\t\tpage %p: bin_index: %u; free_count: %u; empty_index: %u; "
		"free_list %p (%" B_PRIu32 " entr%s)\n", page, page->bin_index,
		page->free_count, page->empty_index, page->free_list, count,
		count == 1 ? "y" : "ies");
}


static void
dump_bin(heap_bin *bin)
{
	printf("\telement_size: %" B_PRIu32 "; max_free_count: %u; page_list %p;\n",
		bin->element_size, bin->max_free_count, bin->page_list);

	for (heap_page *temp = bin->page_list; temp != NULL; temp = temp->next)
		dump_page(temp);
}


static void
dump_bin_list(heap_allocator *heap)
{
	for (uint32 i = 0; i < heap->bin_count; i++)
		dump_bin(&heap->bins[i]);
	printf("\n");
}


static void
dump_allocator_areas(heap_allocator *heap)
{
	heap_area *area = heap->all_areas;
	while (area) {
		printf("\tarea %p: area: %" B_PRId32 "; base: 0x%08lx; size: %" B_PRIuSIZE "; "
			"page_count: %" B_PRIu32 "; free_pages: %p (%" B_PRIu32 " entr%s)\n",
			area, area->area, area->base, area->size, area->page_count,
			area->free_pages, area->free_page_count,
			area->free_page_count == 1 ? "y" : "ies");
		area = area->all_next;
	}

	printf("\n");
}


static void
dump_allocator(heap_allocator *heap, bool areas, bool bins)
{
	printf("allocator %p: name: %s; page_size: %" B_PRIu32 "; bin_count: %"
		B_PRIu32 "; pages: %" B_PRIu32 "; free_pages: %" B_PRIu32 "; "
		"empty_areas: %" B_PRIu32 "\n", heap, heap->name, heap->page_size,
		heap->bin_count, heap->total_pages, heap->total_free_pages,
		heap->empty_areas);

	if (areas)
		dump_allocator_areas(heap);
	if (bins)
		dump_bin_list(heap);
}


static void
dump_allocations(bool statsOnly, thread_id thread)
{
	size_t totalSize = 0;
	uint32 totalCount = 0;
	for (uint32 classIndex = 0; classIndex < HEAP_CLASS_COUNT; classIndex++) {
		heap_allocator *heap = sHeaps[classIndex];

		// go through all the pages in all the areas
		heap_area *area = heap->all_areas;
		while (area) {
			heap_leak_check_info *info = NULL;
			for (uint32 i = 0; i < area->page_count; i++) {
				heap_page *page = &area->page_table[i];
				if (!page->in_use)
					continue;

				addr_t base = area->base + i * heap->page_size;
				if (page->bin_index < heap->bin_count) {
					// page is used by a small allocation bin
					uint32 elementCount = page->empty_index;
					size_t elementSize
						= heap->bins[page->bin_index].element_size;
					for (uint32 j = 0; j < elementCount;
							j++, base += elementSize) {
						// walk the free list to see if this element is in use
						bool elementInUse = true;
						for (addr_t *temp = page->free_list; temp != NULL;
								temp = (addr_t *)*temp) {
							if ((addr_t)temp == base) {
								elementInUse = false;
								break;
							}
						}

						if (!elementInUse)
							continue;

						info = (heap_leak_check_info *)(base + elementSize
							- sizeof(heap_leak_check_info));

						if (thread == -1 || info->thread == thread) {
							// interesting...
							if (!statsOnly) {
								printf("thread: % 6" B_PRId32 "; address: "
									"0x%08lx; size: %" B_PRIuSIZE " bytes\n", info->thread,
									base, info->size);
							}

							totalSize += info->size;
							totalCount++;
						}
					}
				} else {
					// page is used by a big allocation, find the page count
					uint32 pageCount = 1;
					while (i + pageCount < area->page_count
						&& area->page_table[i + pageCount].in_use
						&& area->page_table[i + pageCount].bin_index
							== heap->bin_count
						&& area->page_table[i + pageCount].allocation_id
							== page->allocation_id)
						pageCount++;

					info = (heap_leak_check_info *)(base + pageCount
						* heap->page_size - sizeof(heap_leak_check_info));

					if (thread == -1 || info->thread == thread) {
						// interesting...
						if (!statsOnly) {
							printf("thread: % 6" B_PRId32 "; address: 0x%08lx;"
								" size: %" B_PRIuSIZE " bytes\n", info->thread,
								base, info->size);
						}

						totalSize += info->size;
						totalCount++;
					}

					// skip the allocated pages
					i += pageCount - 1;
				}
			}

			area = area->all_next;
		}
	}

	printf("total allocations: %" B_PRIu32 "; total bytes: %" B_PRIuSIZE "\n", totalCount,
		totalSize);
}


static void
heap_validate_walls()
{
	for (uint32 classIndex = 0; classIndex < HEAP_CLASS_COUNT; classIndex++) {
		heap_allocator *heap = sHeaps[classIndex];
		ReadLocker areaReadLocker(heap->area_lock);
		for (uint32 i = 0; i < heap->bin_count; i++)
			mutex_lock(&heap->bins[i].lock);
		MutexLocker pageLocker(heap->page_lock);

		// go through all the pages in all the areas
		heap_area *area = heap->all_areas;
		while (area) {
			heap_leak_check_info *info = NULL;
			for (uint32 i = 0; i < area->page_count; i++) {
				heap_page *page = &area->page_table[i];
				if (!page->in_use)
					continue;

				addr_t base = area->base + i * heap->page_size;
				if (page->bin_index < heap->bin_count) {
					// page is used by a small allocation bin
					uint32 elementCount = page->empty_index;
					size_t elementSize
						= heap->bins[page->bin_index].element_size;
					for (uint32 j = 0; j < elementCount;
							j++, base += elementSize) {
						// walk the free list to see if this element is in use
						bool elementInUse = true;
						for (addr_t *temp = page->free_list; temp != NULL;
								temp = (addr_t *)*temp) {
							if ((addr_t)temp == base) {
								elementInUse = false;
								break;
							}
						}

						if (!elementInUse)
							continue;

						info = (heap_leak_check_info *)(base + elementSize
							- sizeof(heap_leak_check_info));
						if (info->size > elementSize - sizeof(addr_t)
								- sizeof(heap_leak_check_info)) {
							panic("leak check info has invalid size %" B_PRIuSIZE " for"
								" element size %" B_PRIuSIZE "\n", info->size, elementSize);
							continue;
						}

						addr_t wallValue;
						addr_t wallAddress = base + info->size;
						memcpy(&wallValue, (void *)wallAddress, sizeof(addr_t));
						if (wallValue != wallAddress) {
							panic("someone wrote beyond small allocation at"
								" 0x%08lx; size: %" B_PRIuSIZE " bytes;"
								" allocated by %" B_PRId32 ";"
								" value: 0x%08lx\n", base, info->size,
								info->thread, wallValue);
						}
					}
				} else {
					// page is used by a big allocation, find the page count
					uint32 pageCount = 1;
					while (i + pageCount < area->page_count
						&& area->page_table[i + pageCount].in_use
						&& area->page_table[i + pageCount].bin_index
							== heap->bin_count
						&& area->page_table[i + pageCount].allocation_id
							== page->allocation_id)
						pageCount++;

					info = (heap_leak_check_info *)(base + pageCount
						* heap->page_size - sizeof(heap_leak_check_info));

					if (info->size > pageCount * heap->page_size
							- sizeof(addr_t) - sizeof(heap_leak_check_info)) {
						panic("leak check info has invalid size %" B_PRIuSIZE " for"
							" page count %" B_PRIu32 " (%" B_PRIu32 " bytes)\n", info->size,
							pageCount, pageCount * heap->page_size);
						continue;
					}

					addr_t wallValue;
					addr_t wallAddress = base + info->size;
					memcpy(&wallValue, (void *)wallAddress, sizeof(addr_t));
					if (wallValue != wallAddress) {
						panic("someone wrote beyond big allocation at 0x%08lx;"
							" size: %" B_PRIuSIZE " bytes; allocated by %" B_PRId32 ";"
							" value: 0x%08lx\n", base, info->size,
							info->thread, wallValue);
					}

					// skip the allocated pages
					i += pageCount - 1;
				}
			}

			area = area->all_next;
		}

		pageLocker.Unlock();
		for (uint32 i = 0; i < heap->bin_count; i++)
			mutex_unlock(&heap->bins[i].lock);
	}
}


static void
heap_validate_heap(heap_allocator *heap)
{
	ReadLocker areaReadLocker(heap->area_lock);
	for (uint32 i = 0; i < heap->bin_count; i++)
		mutex_lock(&heap->bins[i].lock);
	MutexLocker pageLocker(heap->page_lock);

	uint32 totalPageCount = 0;
	uint32 totalFreePageCount = 0;
	heap_area *area = heap->all_areas;
	while (area != NULL) {
		// validate the free pages list
		uint32 freePageCount = 0;
		heap_page *lastPage = NULL;
		heap_page *page = area->free_pages;
		while (page) {
			if ((addr_t)page < (addr_t)&area->page_table[0]
				|| (addr_t)page >= (addr_t)&area->page_table[area->page_count])
				panic("free page is not part of the page table\n");

			if (page->index >= area->page_count)
				panic("free page has invalid index\n");

			if ((addr_t)&area->page_table[page->index] != (addr_t)page)
				panic("free page index does not lead to target page\n");

			if (page->prev != lastPage)
				panic("free page entry has invalid prev link\n");

			if (page->in_use)
				panic("free page marked as in use\n");

			lastPage = page;
			page = page->next;
			freePageCount++;
		}

		totalPageCount += freePageCount;
		totalFreePageCount += freePageCount;
		if (area->free_page_count != freePageCount) {
			panic("free page count %" B_PRIu32 " doesn't match free page list %" B_PRIu32 "\n",
				area->free_page_count, freePageCount);
		}

		// validate the page table
		uint32 usedPageCount = 0;
		for (uint32 i = 0; i < area->page_count; i++) {
			if (area->page_table[i].in_use)
				usedPageCount++;
		}

		totalPageCount += usedPageCount;
		if (freePageCount + usedPageCount != area->page_count) {
			panic("free pages and used pages do not add up "
				"(%" B_PRIu32 " + %" B_PRIu32 " != %" B_PRIu32 ")\n",
				freePageCount, usedPageCount, area->page_count);
		}

		area = area->all_next;
	}

	// validate the areas
	area = heap->areas;
	heap_area *lastArea = NULL;
	uint32 lastFreeCount = 0;
	while (area != NULL) {
		if (area->free_page_count < lastFreeCount)
			panic("size ordering of area list broken\n");

		if (area->prev != lastArea)
			panic("area list entry has invalid prev link\n");

		lastArea = area;
		lastFreeCount = area->free_page_count;
		area = area->next;
	}

	lastArea = NULL;
	area = heap->all_areas;
	while (area != NULL) {
		if (lastArea != NULL && lastArea->base < area->base)
			panic("base ordering of all_areas list broken\n");

		lastArea = area;
		area = area->all_next;
	}

	// validate the bins
	for (uint32 i = 0; i < heap->bin_count; i++) {
		heap_bin *bin = &heap->bins[i];
		heap_page *lastPage = NULL;
		heap_page *page = bin->page_list;
		lastFreeCount = 0;
		while (page) {
			area = heap->all_areas;
			while (area) {
				if (area == page->area)
					break;
				area = area->all_next;
			}

			if (area == NULL) {
				panic("page area not present in area list\n");
				page = page->next;
				continue;
			}

			if ((addr_t)page < (addr_t)&area->page_table[0]
				|| (addr_t)page >= (addr_t)&area->page_table[area->page_count])
				panic("used page is not part of the page table\n");

			if (page->index >= area->page_count)
				panic("used page has invalid index %" B_PRIu16 "\n", page->index);

			if ((addr_t)&area->page_table[page->index] != (addr_t)page) {
				panic("used page index does not lead to target page"
					" (%p vs. %p)\n", &area->page_table[page->index],
					page);
			}

			if (page->prev != lastPage) {
				panic("used page entry has invalid prev link (%p vs %p bin "
					"%" B_PRIu32 ")\n", page->prev, lastPage, i);
			}

			if (!page->in_use)
				panic("used page %p marked as not in use\n", page);

			if (page->bin_index != i) {
				panic("used page with bin index %" B_PRIu16 " in page list of bin %" B_PRIu32 "\n",
					page->bin_index, i);
			}

			if (page->free_count < lastFreeCount)
				panic("ordering of bin page list broken\n");

			// validate the free list
			uint32 freeSlotsCount = 0;
			addr_t *element = page->free_list;
			addr_t pageBase = area->base + page->index * heap->page_size;
			while (element) {
				if ((addr_t)element < pageBase
					|| (addr_t)element >= pageBase + heap->page_size)
					panic("free list entry out of page range %p\n", element);

				if (((addr_t)element - pageBase) % bin->element_size != 0)
					panic("free list entry not on a element boundary\n");

				element = (addr_t *)*element;
				freeSlotsCount++;
			}

			uint32 slotCount = bin->max_free_count;
			if (page->empty_index > slotCount) {
				panic("empty index beyond slot count (%" B_PRIu16 " with %" B_PRIu32 " slots)\n",
					page->empty_index, slotCount);
			}

			freeSlotsCount += (slotCount - page->empty_index);
			if (freeSlotsCount > slotCount)
				panic("more free slots than fit into the page\n");

			lastPage = page;
			lastFreeCount = page->free_count;
			page = page->next;
		}
	}

	pageLocker.Unlock();
	for (uint32 i = 0; i < heap->bin_count; i++)
		mutex_unlock(&heap->bins[i].lock);
}


// #pragma mark - Heap functions


static void
heap_add_area(heap_allocator *heap, area_id areaID, addr_t base, size_t size)
{
	heap_area *area = (heap_area *)base;
	area->area = areaID;

	base += sizeof(heap_area);
	size -= sizeof(heap_area);

	uint32 pageCount = size / heap->page_size;
	size_t pageTableSize = pageCount * sizeof(heap_page);
	area->page_table = (heap_page *)base;
	base += pageTableSize;
	size -= pageTableSize;

	// the rest is now actually usable memory (rounded to the next page)
	area->base = ROUNDUP(base, B_PAGE_SIZE);
	area->size = size & ~(B_PAGE_SIZE - 1);

	// now we know the real page count
	pageCount = area->size / heap->page_size;
	area->page_count = pageCount;

	// zero out the page table and fill in page indexes
	memset((void *)area->page_table, 0, pageTableSize);
	for (uint32 i = 0; i < pageCount; i++) {
		area->page_table[i].area = area;
		area->page_table[i].index = i;
	}

	// add all pages up into the free pages list
	for (uint32 i = 1; i < pageCount; i++) {
		area->page_table[i - 1].next = &area->page_table[i];
		area->page_table[i].prev = &area->page_table[i - 1];
	}
	area->free_pages = &area->page_table[0];
	area->free_page_count = pageCount;
	area->page_table[0].prev = NULL;
	area->next = NULL;

	WriteLocker areaWriteLocker(heap->area_lock);
	MutexLocker pageLocker(heap->page_lock);
	if (heap->areas == NULL) {
		// it's the only (empty) area in that heap
		area->prev = NULL;
		heap->areas = area;
	} else {
		// link in this area as the last one as it is completely empty
		heap_area *lastArea = heap->areas;
		while (lastArea->next != NULL)
			lastArea = lastArea->next;

		lastArea->next = area;
		area->prev = lastArea;
	}

	// insert this area in the all_areas list so it stays ordered by base
	if (heap->all_areas == NULL || heap->all_areas->base < area->base) {
		area->all_next = heap->all_areas;
		heap->all_areas = area;
	} else {
		heap_area *insert = heap->all_areas;
		while (insert->all_next && insert->all_next->base > area->base)
			insert = insert->all_next;

		area->all_next = insert->all_next;
		insert->all_next = area;
	}

	heap->total_pages += area->page_count;
	heap->total_free_pages += area->free_page_count;

	if (areaID >= 0) {
		// this later on deletable area is yet empty - the empty count will be
		// decremented as soon as this area is used for the first time
		heap->empty_areas++;
	}

	pageLocker.Unlock();
	areaWriteLocker.Unlock();
}


static status_t
heap_remove_area(heap_allocator *heap, heap_area *area)
{
	if (area->free_page_count != area->page_count) {
		panic("tried removing heap area that has still pages in use");
		return B_ERROR;
	}

	if (area->prev == NULL && area->next == NULL) {
		panic("tried removing the last non-full heap area");
		return B_ERROR;
	}

	if (heap->areas == area)
		heap->areas = area->next;
	if (area->prev != NULL)
		area->prev->next = area->next;
	if (area->next != NULL)
		area->next->prev = area->prev;

	if (heap->all_areas == area)
		heap->all_areas = area->all_next;
	else {
		heap_area *previous = heap->all_areas;
		while (previous) {
			if (previous->all_next == area) {
				previous->all_next = area->all_next;
				break;
			}

			previous = previous->all_next;
		}

		if (previous == NULL)
			panic("removing heap area that is not in all list");
	}

	heap->total_pages -= area->page_count;
	heap->total_free_pages -= area->free_page_count;
	return B_OK;
}


static heap_allocator *
heap_create_allocator(const char *name, addr_t base, size_t size,
	const heap_class *heapClass)
{
	heap_allocator *heap = (heap_allocator *)base;
	base += sizeof(heap_allocator);
	size -= sizeof(heap_allocator);

	heap->name = name;
	heap->page_size = heapClass->page_size;
	heap->total_pages = heap->total_free_pages = heap->empty_areas = 0;
	heap->areas = heap->all_areas = NULL;
	heap->bins = (heap_bin *)base;

	heap->bin_count = 0;
	size_t binSize = 0, lastSize = 0;
	uint32 count = heap->page_size / heapClass->min_bin_size;
	for (; count >= heapClass->min_count_per_page; count--, lastSize = binSize) {
		if (heap->bin_count >= 32)
			panic("heap configuration invalid - max bin count reached\n");

		binSize = (heap->page_size / count) & ~(heapClass->bin_alignment - 1);
		if (binSize == lastSize)
			continue;
		if (heap->page_size - count * binSize > heapClass->max_waste_per_page)
			continue;

		heap_bin *bin = &heap->bins[heap->bin_count];
		mutex_init(&bin->lock, "heap bin lock");
		bin->element_size = binSize;
		bin->max_free_count = heap->page_size / binSize;
		bin->page_list = NULL;
		heap->bin_count++;
	};

	base += heap->bin_count * sizeof(heap_bin);
	size -= heap->bin_count * sizeof(heap_bin);

	rw_lock_init(&heap->area_lock, "heap area lock");
	mutex_init(&heap->page_lock, "heap page lock");

	heap_add_area(heap, -1, base, size);
	return heap;
}


static inline void
heap_free_pages_added(heap_allocator *heap, heap_area *area, uint32 pageCount)
{
	area->free_page_count += pageCount;
	heap->total_free_pages += pageCount;

	if (area->free_page_count == pageCount) {
		// we need to add ourselfs to the area list of the heap
		area->prev = NULL;
		area->next = heap->areas;
		if (area->next)
			area->next->prev = area;
		heap->areas = area;
	} else {
		// we might need to move back in the area list
		if (area->next && area->next->free_page_count < area->free_page_count) {
			// move ourselfs so the list stays ordered
			heap_area *insert = area->next;
			while (insert->next
				&& insert->next->free_page_count < area->free_page_count)
				insert = insert->next;

			if (area->prev)
				area->prev->next = area->next;
			if (area->next)
				area->next->prev = area->prev;
			if (heap->areas == area)
				heap->areas = area->next;

			area->prev = insert;
			area->next = insert->next;
			if (area->next)
				area->next->prev = area;
			insert->next = area;
		}
	}

	if (area->free_page_count == area->page_count && area->area >= 0)
		heap->empty_areas++;
}


static inline void
heap_free_pages_removed(heap_allocator *heap, heap_area *area, uint32 pageCount)
{
	if (area->free_page_count == area->page_count && area->area >= 0) {
		// this area was completely empty
		heap->empty_areas--;
	}

	area->free_page_count -= pageCount;
	heap->total_free_pages -= pageCount;

	if (area->free_page_count == 0) {
		// the area is now full so we remove it from the area list
		if (area->prev)
			area->prev->next = area->next;
		if (area->next)
			area->next->prev = area->prev;
		if (heap->areas == area)
			heap->areas = area->next;
		area->next = area->prev = NULL;
	} else {
		// we might need to move forward in the area list
		if (area->prev && area->prev->free_page_count > area->free_page_count) {
			// move ourselfs so the list stays ordered
			heap_area *insert = area->prev;
			while (insert->prev
				&& insert->prev->free_page_count > area->free_page_count)
				insert = insert->prev;

			if (area->prev)
				area->prev->next = area->next;
			if (area->next)
				area->next->prev = area->prev;

			area->prev = insert->prev;
			area->next = insert;
			if (area->prev)
				area->prev->next = area;
			if (heap->areas == insert)
				heap->areas = area;
			insert->prev = area;
		}
	}
}


static inline void
heap_link_page(heap_page *page, heap_page **list)
{
	page->prev = NULL;
	page->next = *list;
	if (page->next)
		page->next->prev = page;
	*list = page;
}


static inline void
heap_unlink_page(heap_page *page, heap_page **list)
{
	if (page->prev)
		page->prev->next = page->next;
	if (page->next)
		page->next->prev = page->prev;
	if (list && *list == page) {
		*list = page->next;
		if (page->next)
			page->next->prev = NULL;
	}
}


static heap_page *
heap_allocate_contiguous_pages(heap_allocator *heap, uint32 pageCount,
	size_t alignment)
{
	heap_area *area = heap->areas;
	while (area) {
		if (area->free_page_count < pageCount) {
			area = area->next;
			continue;
		}

		uint32 step = 1;
		uint32 firstValid = 0;
		const uint32 lastValid = area->page_count - pageCount + 1;

		if (alignment > heap->page_size) {
			firstValid = (ROUNDUP(area->base, alignment) - area->base)
				/ heap->page_size;
			step = alignment / heap->page_size;
		}

		int32 first = -1;
		for (uint32 i = firstValid; i < lastValid; i += step) {
			if (area->page_table[i].in_use)
				continue;

			first = i;

			for (uint32 j = 1; j < pageCount; j++) {
				if (area->page_table[i + j].in_use) {
					first = -1;
					i += j / step * step;
					break;
				}
			}

			if (first >= 0)
				break;
		}

		if (first < 0) {
			area = area->next;
			continue;
		}

		for (uint32 i = first; i < first + pageCount; i++) {
			heap_page *page = &area->page_table[i];
			page->in_use = 1;
			page->bin_index = heap->bin_count;

			heap_unlink_page(page, &area->free_pages);

			page->next = page->prev = NULL;
			page->free_list = NULL;
			page->allocation_id = (uint16)first;
		}

		heap_free_pages_removed(heap, area, pageCount);
		return &area->page_table[first];
	}

	return NULL;
}


static void
heap_add_leak_check_info(addr_t address, size_t allocated, size_t size)
{
	size -= sizeof(addr_t) + sizeof(heap_leak_check_info);
	heap_leak_check_info *info = (heap_leak_check_info *)(address + allocated
		- sizeof(heap_leak_check_info));
	info->thread = find_thread(NULL);
	info->size = size;

	addr_t wallAddress = address + size;
	memcpy((void *)wallAddress, &wallAddress, sizeof(addr_t));
}


static void *
heap_raw_alloc(heap_allocator *heap, size_t size, size_t alignment)
{
	INFO(("heap %p: allocate %" B_PRIuSIZE " bytes from raw pages with"
		" alignment %" B_PRIuSIZE "\n", heap, size, alignment));

	uint32 pageCount = (size + heap->page_size - 1) / heap->page_size;

	MutexLocker pageLocker(heap->page_lock);
	heap_page *firstPage = heap_allocate_contiguous_pages(heap, pageCount,
		alignment);
	if (firstPage == NULL) {
		INFO(("heap %p: found no contiguous pages to allocate %" B_PRIuSIZE " bytes\n",
			heap, size));
		return NULL;
	}

	addr_t address = firstPage->area->base + firstPage->index * heap->page_size;
	heap_add_leak_check_info(address, pageCount * heap->page_size, size);
	return (void *)address;
}


static void *
heap_allocate_from_bin(heap_allocator *heap, uint32 binIndex, size_t size)
{
	heap_bin *bin = &heap->bins[binIndex];
	INFO(("heap %p: allocate %" B_PRIuSIZE " bytes from bin %" B_PRIu32
		" with element_size %" B_PRIu32 "\n",
		heap, size, binIndex, bin->element_size));

	MutexLocker binLocker(bin->lock);
	heap_page *page = bin->page_list;
	if (page == NULL) {
		MutexLocker pageLocker(heap->page_lock);
		heap_area *area = heap->areas;
		if (area == NULL) {
			INFO(("heap %p: no free pages to allocate %" B_PRIuSIZE " bytes\n", heap,
				size));
			return NULL;
		}

		// by design there are only areas in the list that still have
		// free pages available
		page = area->free_pages;
		area->free_pages = page->next;
		if (page->next)
			page->next->prev = NULL;

		heap_free_pages_removed(heap, area, 1);

		if (page->in_use)
			panic("got an in use page from the free pages list\n");
		page->in_use = 1;

		pageLocker.Unlock();

		page->bin_index = binIndex;
		page->free_count = bin->max_free_count;
		page->empty_index = 0;
		page->free_list = NULL;
		page->next = page->prev = NULL;
		bin->page_list = page;
	}

	// we have a page where we have a free slot
	void *address = NULL;
	if (page->free_list) {
		// there's a previously freed entry we can use
		address = page->free_list;
		page->free_list = (addr_t *)*page->free_list;
	} else {
		// the page hasn't been fully allocated so use the next empty_index
		address = (void *)(page->area->base + page->index * heap->page_size
			+ page->empty_index * bin->element_size);
		page->empty_index++;
	}

	page->free_count--;
	if (page->free_count == 0) {
		// the page is now full so we remove it from the page_list
		bin->page_list = page->next;
		if (page->next)
			page->next->prev = NULL;
		page->next = page->prev = NULL;
	}

	heap_add_leak_check_info((addr_t)address, bin->element_size, size);
	return address;
}


static void *
heap_memalign(heap_allocator *heap, size_t alignment, size_t size)
{
	INFO(("memalign(alignment = %" B_PRIuSIZE ", size = %" B_PRIuSIZE ")\n",
		alignment, size));

	if (!is_valid_alignment(alignment)) {
		panic("memalign() with an alignment which is not a power of 2 (%" B_PRIuSIZE ")\n",
			alignment);
	}

	size += sizeof(addr_t) + sizeof(heap_leak_check_info);

	void *address = NULL;
	if (alignment < B_PAGE_SIZE) {
		if (alignment != 0) {
			// TODO: The alignment is done by ensuring that the element size
			// of the target bin is aligned with the requested alignment. This
			// has the problem that it wastes space because a better (smaller)
			// bin could possibly be selected. We should pick the best bin and
			// check if there is an aligned block in the free list or if a new
			// (page aligned) page has to be allocated anyway.
			size = ROUNDUP(size, alignment);
			for (uint32 i = 0; i < heap->bin_count; i++) {
				if (size <= heap->bins[i].element_size
					&& is_valid_alignment(heap->bins[i].element_size)) {
					address = heap_allocate_from_bin(heap, i, size);
					break;
				}
			}
		} else {
			for (uint32 i = 0; i < heap->bin_count; i++) {
				if (size <= heap->bins[i].element_size) {
					address = heap_allocate_from_bin(heap, i, size);
					break;
				}
			}
		}
	}

	if (address == NULL)
		address = heap_raw_alloc(heap, size, alignment);

	size -= sizeof(addr_t) + sizeof(heap_leak_check_info);

	INFO(("memalign(): asked to allocate %" B_PRIuSIZE " bytes, returning pointer %p\n",
		size, address));

	if (address == NULL)
		return address;

	memset(address, 0xcc, size);

	// make sure 0xdeadbeef is cleared if we do not overwrite the memory
	// and the user does not clear it
	if (((uint32 *)address)[1] == 0xdeadbeef)
		((uint32 *)address)[1] = 0xcccccccc;

	return address;
}


static status_t
heap_free(heap_allocator *heap, void *address)
{
	if (address == NULL)
		return B_OK;

	ReadLocker areaReadLocker(heap->area_lock);
	heap_area *area = heap->all_areas;
	while (area) {
		// since the all_areas list is ordered by base with the biggest
		// base at the top, we need only find the first area with a base
		// smaller than our address to become our only candidate for freeing
		if (area->base <= (addr_t)address) {
			if ((addr_t)address >= area->base + area->size) {
				// none of the other areas can contain the address as the list
				// is ordered
				return B_ENTRY_NOT_FOUND;
			}

			// this area contains the allocation, we're done searching
			break;
		}

		area = area->all_next;
	}

	if (area == NULL) {
		// this address does not belong to us
		return B_ENTRY_NOT_FOUND;
	}

	INFO(("free(): asked to free pointer %p\n", address));

	heap_page *page = &area->page_table[((addr_t)address - area->base)
		/ heap->page_size];

	INFO(("free(): page %p: bin_index %d, free_count %d\n", page,
		page->bin_index, page->free_count));

	if (page->bin_index > heap->bin_count) {
		panic("free(): page %p: invalid bin_index %d\n", page,
			page->bin_index);
		return B_ERROR;
	}

	addr_t pageBase = area->base + page->index * heap->page_size;
	if (page->bin_index < heap->bin_count) {
		// small allocation
		heap_bin *bin = &heap->bins[page->bin_index];
		if (((addr_t)address - pageBase) % bin->element_size != 0) {
			panic("free(): address %p does not fall on allocation boundary"
				" for page base %p and element size %" B_PRIu32 "\n", address,
				(void *)pageBase, bin->element_size);
			return B_ERROR;
		}

		MutexLocker binLocker(bin->lock);

		if (((uint32 *)address)[1] == 0xdeadbeef) {
			// This block looks like it was freed already, walk the free list
			// on this page to make sure this address doesn't exist.
			for (addr_t *temp = page->free_list; temp != NULL;
					temp = (addr_t *)*temp) {
				if (temp == address) {
					panic("free(): address %p already exists in page free"
						" list (double free)\n", address);
					return B_ERROR;
				}
			}
		}

		heap_leak_check_info *info = (heap_leak_check_info *)((addr_t)address
			+ bin->element_size - sizeof(heap_leak_check_info));
		if (info->size > bin->element_size - sizeof(addr_t)
				- sizeof(heap_leak_check_info)) {
			panic("leak check info has invalid size %" B_PRIuSIZE
				" for element size %" B_PRIu32 ","
				" probably memory has been overwritten past allocation size\n",
				info->size, bin->element_size);
		}

		addr_t wallValue;
		addr_t wallAddress = (addr_t)address + info->size;
		memcpy(&wallValue, (void *)wallAddress, sizeof(addr_t));
		if (wallValue != wallAddress) {
			panic("someone wrote beyond small allocation at %p;"
				" size: %" B_PRIuSIZE " bytes; allocated by %" B_PRId32 ";"
				" value: 0x%08lx\n",
				address, info->size, info->thread, wallValue);
		}

		// the first 4 bytes are overwritten with the next free list pointer
		// later
		uint32 *dead = (uint32 *)address;
		for (uint32 i = 0; i < bin->element_size / sizeof(uint32); i++)
			dead[i] = 0xdeadbeef;

		if (sReuseMemory) {
			// add the address to the page free list
			*(addr_t *)address = (addr_t)page->free_list;
			page->free_list = (addr_t *)address;
			page->free_count++;

			if (page->free_count == bin->max_free_count) {
				// we are now empty, remove the page from the bin list
				MutexLocker pageLocker(heap->page_lock);
				heap_unlink_page(page, &bin->page_list);
				page->in_use = 0;
				heap_link_page(page, &area->free_pages);
				heap_free_pages_added(heap, area, 1);
			} else if (page->free_count == 1) {
				// we need to add ourselfs to the page list of the bin
				heap_link_page(page, &bin->page_list);
			} else {
				// we might need to move back in the free pages list
				if (page->next && page->next->free_count < page->free_count) {
					// move ourselfs so the list stays ordered
					heap_page *insert = page->next;
					while (insert->next
						&& insert->next->free_count < page->free_count)
						insert = insert->next;

					heap_unlink_page(page, &bin->page_list);

					page->prev = insert;
					page->next = insert->next;
					if (page->next)
						page->next->prev = page;
					insert->next = page;
				}
			}
		}
	} else {
		if ((addr_t)address != pageBase) {
			panic("free(): large allocation address %p not on page base %p\n",
				address, (void *)pageBase);
			return B_ERROR;
		}

		// large allocation, just return the pages to the page free list
		uint32 allocationID = page->allocation_id;
		uint32 maxPages = area->page_count - page->index;
		uint32 pageCount = 0;

		MutexLocker pageLocker(heap->page_lock);
		for (uint32 i = 0; i < maxPages; i++) {
			// loop until we find the end of this allocation
			if (!page[i].in_use || page[i].bin_index != heap->bin_count
				|| page[i].allocation_id != allocationID)
				break;

			// this page still belongs to the same allocation
			if (sReuseMemory) {
				page[i].in_use = 0;
				page[i].allocation_id = 0;

				// return it to the free list
				heap_link_page(&page[i], &area->free_pages);
			}

			pageCount++;
		}

		size_t allocationSize = pageCount * heap->page_size;
		heap_leak_check_info *info = (heap_leak_check_info *)((addr_t)address
			+ allocationSize - sizeof(heap_leak_check_info));
		if (info->size > allocationSize - sizeof(addr_t)
				- sizeof(heap_leak_check_info)) {
			panic("leak check info has invalid size %" B_PRIuSIZE
				" for allocation of %" B_PRIuSIZE ","
				" probably memory has been overwritten past allocation size\n",
				info->size, allocationSize);
		}

		addr_t wallValue;
		addr_t wallAddress = (addr_t)address + info->size;
		memcpy(&wallValue, (void *)wallAddress, sizeof(addr_t));
		if (wallValue != wallAddress) {
			panic("someone wrote beyond big allocation at %p;"
				" size: %" B_PRIuSIZE " bytes; allocated by %" B_PRId32 "; value: 0x%08lx\n",
				address, info->size, info->thread, wallValue);
		}

		uint32 *dead = (uint32 *)address;
		for (uint32 i = 0; i < allocationSize / sizeof(uint32); i++)
			dead[i] = 0xdeadbeef;

		if (sReuseMemory)
			heap_free_pages_added(heap, area, pageCount);
	}

	areaReadLocker.Unlock();

	if (heap->empty_areas > 1) {
		WriteLocker areaWriteLocker(heap->area_lock);
		MutexLocker pageLocker(heap->page_lock);

		area = heap->areas;
		while (area != NULL && heap->empty_areas > 1) {
			heap_area *next = area->next;
			if (area->area >= 0
				&& area->free_page_count == area->page_count
				&& heap_remove_area(heap, area) == B_OK) {
				delete_area(area->area);
				heap->empty_areas--;
			}

			area = next;
		}
	}

	return B_OK;
}


static status_t
heap_realloc(heap_allocator *heap, void *address, void **newAddress,
	size_t newSize)
{
	ReadLocker areaReadLocker(heap->area_lock);
	heap_area *area = heap->all_areas;
	while (area) {
		// since the all_areas list is ordered by base with the biggest
		// base at the top, we need only find the first area with a base
		// smaller than our address to become our only candidate for
		// reallocating
		if (area->base <= (addr_t)address) {
			if ((addr_t)address >= area->base + area->size) {
				// none of the other areas can contain the address as the list
				// is ordered
				return B_ENTRY_NOT_FOUND;
			}

			// this area contains the allocation, we're done searching
			break;
		}

		area = area->all_next;
	}

	if (area == NULL) {
		// this address does not belong to us
		return B_ENTRY_NOT_FOUND;
	}

	INFO(("realloc(address = %p, newSize = %" B_PRIuSIZE ")\n", address, newSize));

	heap_page *page = &area->page_table[((addr_t)address - area->base)
		/ heap->page_size];
	if (page->bin_index > heap->bin_count) {
		panic("realloc(): page %p: invalid bin_index %d\n", page,
			page->bin_index);
		return B_ERROR;
	}

	// find out the size of the old allocation first
	size_t minSize = 0;
	size_t maxSize = 0;
	if (page->bin_index < heap->bin_count) {
		// this was a small allocation
		heap_bin *bin = &heap->bins[page->bin_index];
		maxSize = bin->element_size;
		if (page->bin_index > 0)
			minSize = heap->bins[page->bin_index - 1].element_size + 1;
	} else {
		// this was a large allocation
		uint32 allocationID = page->allocation_id;
		uint32 maxPages = area->page_count - page->index;
		maxSize = heap->page_size;

		MutexLocker pageLocker(heap->page_lock);
		for (uint32 i = 1; i < maxPages; i++) {
			if (!page[i].in_use || page[i].bin_index != heap->bin_count
				|| page[i].allocation_id != allocationID)
				break;

			minSize += heap->page_size;
			maxSize += heap->page_size;
		}
	}

	newSize += sizeof(addr_t) + sizeof(heap_leak_check_info);

	// does the new allocation simply fit in the old allocation?
	if (newSize > minSize && newSize <= maxSize) {
		// update the size info (the info is at the end so stays where it is)
		heap_leak_check_info *info = (heap_leak_check_info *)((addr_t)address
			+ maxSize - sizeof(heap_leak_check_info));
		newSize -= sizeof(addr_t) + sizeof(heap_leak_check_info);
		*newAddress = address;

		MutexLocker pageLocker(heap->page_lock);
		info->size = newSize;
		addr_t wallAddress = (addr_t)address + newSize;
		memcpy((void *)wallAddress, &wallAddress, sizeof(addr_t));
		return B_OK;
	}

	areaReadLocker.Unlock();

	// new leak check info will be created with the malloc below
	newSize -= sizeof(addr_t) + sizeof(heap_leak_check_info);

	// if not, allocate a new chunk of memory
	*newAddress = debug_heap_memalign(sDefaultAlignment, newSize);
	if (*newAddress == NULL) {
		// we tried but it didn't work out, but still the operation is done
		return B_OK;
	}

	// copy the old data and free the old allocation
	memcpy(*newAddress, address, min_c(maxSize, newSize));
	heap_free(heap, address);
	return B_OK;
}


inline uint32
heap_class_for(size_t size)
{
	// take the extra info size into account
	size += sizeof(addr_t) + sizeof(heap_leak_check_info);

	uint32 index = 0;
	for (; index < HEAP_CLASS_COUNT - 1; index++) {
		if (size <= sHeapClasses[index].max_allocation_size)
			return index;
	}

	return index;
}


static status_t
heap_get_allocation_info(heap_allocator *heap, void *address, size_t *size,
	thread_id *thread)
{
	ReadLocker areaReadLocker(heap->area_lock);
	heap_area *area = heap->all_areas;
	while (area) {
		// since the all_areas list is ordered by base with the biggest
		// base at the top, we need only find the first area with a base
		// smaller than our address to become our only candidate for freeing
		if (area->base <= (addr_t)address) {
			if ((addr_t)address >= area->base + area->size) {
				// none of the other areas can contain the address as the list
				// is ordered
				return B_ENTRY_NOT_FOUND;
			}

			// this area contains the allocation, we're done searching
			break;
		}

		area = area->all_next;
	}

	if (area == NULL) {
		// this address does not belong to us
		return B_ENTRY_NOT_FOUND;
	}

	heap_page *page = &area->page_table[((addr_t)address - area->base)
		/ heap->page_size];

	if (page->bin_index > heap->bin_count) {
		panic("get_allocation_info(): page %p: invalid bin_index %d\n", page,
			page->bin_index);
		return B_ERROR;
	}

	heap_leak_check_info *info = NULL;
	addr_t pageBase = area->base + page->index * heap->page_size;
	if (page->bin_index < heap->bin_count) {
		// small allocation
		heap_bin *bin = &heap->bins[page->bin_index];
		if (((addr_t)address - pageBase) % bin->element_size != 0) {
			panic("get_allocation_info(): address %p does not fall on"
				" allocation boundary for page base %p and element size %" B_PRIu32 "\n",
				address, (void *)pageBase, bin->element_size);
			return B_ERROR;
		}

		MutexLocker binLocker(bin->lock);

		info = (heap_leak_check_info *)((addr_t)address + bin->element_size
			- sizeof(heap_leak_check_info));
		if (info->size > bin->element_size - sizeof(addr_t)
				- sizeof(heap_leak_check_info)) {
			panic("leak check info has invalid size %" B_PRIuSIZE
				" for element size %" B_PRIu32 ","
				" probably memory has been overwritten past allocation size\n",
				info->size, bin->element_size);
			return B_ERROR;
		}
	} else {
		if ((addr_t)address != pageBase) {
			panic("get_allocation_info(): large allocation address %p not on"
				" page base %p\n", address, (void *)pageBase);
			return B_ERROR;
		}

		uint32 allocationID = page->allocation_id;
		uint32 maxPages = area->page_count - page->index;
		uint32 pageCount = 0;

		MutexLocker pageLocker(heap->page_lock);
		for (uint32 i = 0; i < maxPages; i++) {
			// loop until we find the end of this allocation
			if (!page[i].in_use || page[i].bin_index != heap->bin_count
				|| page[i].allocation_id != allocationID)
				break;

			pageCount++;
		}

		size_t allocationSize = pageCount * heap->page_size;
		info = (heap_leak_check_info *)((addr_t)address + allocationSize
			- sizeof(heap_leak_check_info));
		if (info->size > allocationSize - sizeof(addr_t)
				- sizeof(heap_leak_check_info)) {
			panic("leak check info has invalid size %" B_PRIuSIZE
				" for allocation of %" B_PRIuSIZE ","
				" probably memory has been overwritten past allocation size\n",
				info->size, allocationSize);
			return B_ERROR;
		}
	}

	if (size != NULL)
		*size = info->size;
	if (thread != NULL)
		*thread = info->thread;

	return B_OK;
}


//	#pragma mark -


static status_t
heap_create_new_heap_area(heap_allocator *heap, const char *name, size_t size)
{
	void *address = NULL;
	area_id heapArea = create_area(name, &address, B_ANY_ADDRESS, size,
		B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
	if (heapArea < B_OK) {
		INFO(("heap: couldn't allocate heap area \"%s\"\n", name));
		return heapArea;
	}

	heap_add_area(heap, heapArea, (addr_t)address, size);
	if (sParanoidValidation)
		heap_validate_heap(heap);

	return B_OK;
}


static int32
heap_wall_checker(void *data)
{
	int msInterval = (addr_t)data;
	while (!sStopWallChecking) {
		heap_validate_walls();
		snooze(msInterval * 1000);
	}

	return 0;
}


//	#pragma mark - Heap Debug API


static status_t
debug_heap_start_wall_checking(int msInterval)
{
	if (sWallCheckThread < 0) {
		sWallCheckThread = spawn_thread(heap_wall_checker, "heap wall checker",
			B_LOW_PRIORITY, (void *)(addr_t)msInterval);
	}

	if (sWallCheckThread < 0)
		return sWallCheckThread;

	sStopWallChecking = false;
	return resume_thread(sWallCheckThread);
}


static status_t
debug_heap_stop_wall_checking()
{
	int32 result;
	sStopWallChecking = true;
	return wait_for_thread(sWallCheckThread, &result);
}


static void
debug_heap_set_paranoid_validation(bool enabled)
{
	sParanoidValidation = enabled;
}


static void
debug_heap_set_memory_reuse(bool enabled)
{
	sReuseMemory = enabled;
}


static void
debug_heap_set_debugger_calls(bool enabled)
{
	sDebuggerCalls = enabled;
}


static void
debug_heap_set_default_alignment(size_t defaultAlignment)
{
	sDefaultAlignment = defaultAlignment;
}


static void
debug_heap_validate_heaps()
{
	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++)
		heap_validate_heap(sHeaps[i]);
}


static void
debug_heap_dump_heaps(bool dumpAreas, bool dumpBins)
{
	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++)
		dump_allocator(sHeaps[i], dumpAreas, dumpBins);
}


static void *
debug_heap_malloc_with_guard_page(size_t size)
{
	size_t areaSize = ROUNDUP(size + sizeof(area_allocation_info) + B_PAGE_SIZE,
		B_PAGE_SIZE);
	if (areaSize < size) {
		// the size overflowed
		return NULL;
	}

	void *address = NULL;
	area_id allocationArea = create_area("guarded area", &address,
		B_ANY_ADDRESS, areaSize, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
	if (allocationArea < B_OK) {
		panic("heap: failed to create area for guarded allocation of %" B_PRIuSIZE
			" bytes\n", size);
		return NULL;
	}

	if (mprotect((void *)((addr_t)address + areaSize - B_PAGE_SIZE),
			B_PAGE_SIZE, PROT_NONE) != 0) {
		panic("heap: failed to protect guard page: %s\n", strerror(errno));
		delete_area(allocationArea);
		return NULL;
	}

	area_allocation_info *info = (area_allocation_info *)address;
	info->magic = kAreaAllocationMagic;
	info->area = allocationArea;
	info->base = address;
	info->size = areaSize;
	info->thread = find_thread(NULL);
	info->allocation_size = size;
	info->allocation_alignment = 0;

	// the address is calculated so that the end of the allocation
	// is at the end of the usable space of the requested area
	address = (void *)((addr_t)address + areaSize - B_PAGE_SIZE - size);

	INFO(("heap: allocated area %" B_PRId32 " for guarded allocation of %" B_PRIuSIZE " bytes\n",
		allocationArea, size));

	info->allocation_base = address;

	memset(address, 0xcc, size);
	return address;
}


static status_t
debug_heap_get_allocation_info(void *address, size_t *size,
	thread_id *thread)
{
	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++) {
		heap_allocator *heap = sHeaps[i];
		if (heap_get_allocation_info(heap, address, size, thread) == B_OK)
			return B_OK;
	}

	// or maybe it was a huge allocation using an area
	area_info areaInfo;
	area_id area = area_for(address);
	if (area >= B_OK && get_area_info(area, &areaInfo) == B_OK) {
		area_allocation_info *info = (area_allocation_info *)areaInfo.address;

		// just make extra sure it was allocated by us
		if (info->magic == kAreaAllocationMagic && info->area == area
			&& info->size == areaInfo.size && info->base == areaInfo.address
			&& info->allocation_size < areaInfo.size) {
			if (size)
				*size = info->allocation_size;
			if (thread)
				*thread = info->thread;
			return B_OK;
		}
	}

	return B_ENTRY_NOT_FOUND;
}


//	#pragma mark - Init


static status_t
debug_heap_init(void)
{
	// This will locate the heap base at 384 MB and reserve the next 1152 MB
	// for it. They may get reclaimed by other areas, though, but the maximum
	// size of the heap is guaranteed until the space is really needed.
	void *heapBase = (void *)0x18000000;
	status_t status = _kern_reserve_address_range((addr_t *)&heapBase,
		B_EXACT_ADDRESS, 0x48000000);

	area_id heapArea = create_area("heap", (void **)&heapBase,
		status == B_OK ? B_EXACT_ADDRESS : B_BASE_ADDRESS,
		HEAP_INITIAL_SIZE, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
	if (heapArea < B_OK)
		return heapArea;

	addr_t base = (addr_t)heapBase;
	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++) {
		size_t partSize = HEAP_INITIAL_SIZE
			* sHeapClasses[i].initial_percentage / 100;
		sHeaps[i] = heap_create_allocator(sHeapClasses[i].name, base, partSize,
			&sHeapClasses[i]);
		base += partSize;
	}

	return B_OK;
}


//	#pragma mark - Public API


static void *
debug_heap_memalign(size_t alignment, size_t size)
{
	size_t alignedSize = size + sizeof(addr_t) + sizeof(heap_leak_check_info);
	if (alignment != 0 && alignment < B_PAGE_SIZE)
		alignedSize = ROUNDUP(alignedSize, alignment);

	if (alignedSize >= HEAP_AREA_USE_THRESHOLD) {
		// don't even attempt such a huge allocation - use areas instead
		size_t areaSize = ROUNDUP(size + sizeof(area_allocation_info)
			+ alignment, B_PAGE_SIZE);
		if (areaSize < size) {
			// the size overflowed
			return NULL;
		}

		void *address = NULL;
		area_id allocationArea = create_area("memalign area", &address,
			B_ANY_ADDRESS, areaSize, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
		if (allocationArea < B_OK) {
			panic("heap: failed to create area for huge allocation of %" B_PRIuSIZE
				" bytes\n", size);
			return NULL;
		}

		area_allocation_info *info = (area_allocation_info *)address;
		info->magic = kAreaAllocationMagic;
		info->area = allocationArea;
		info->base = address;
		info->size = areaSize;
		info->thread = find_thread(NULL);
		info->allocation_size = size;
		info->allocation_alignment = alignment;

		address = (void *)((addr_t)address + sizeof(area_allocation_info));
		if (alignment != 0) {
			address = (void *)ROUNDUP((addr_t)address, alignment);
			ASSERT((addr_t)address % alignment == 0);
			ASSERT((addr_t)address + size - 1 < (addr_t)info + areaSize - 1);
		}

		INFO(("heap: allocated area %" B_PRId32 " for huge allocation of %" B_PRIuSIZE " bytes\n",
			allocationArea, size));

		info->allocation_base = address;

		memset(address, 0xcc, size);
		return address;
	}

	uint32 heapClass = alignment < B_PAGE_SIZE
		? heap_class_for(alignedSize) : 0;

	heap_allocator *heap = sHeaps[heapClass];
	void *result = heap_memalign(heap, alignment, size);
	if (result == NULL) {
		// add new area and try again
		heap_create_new_heap_area(heap, "additional heap area", HEAP_GROW_SIZE);
		result = heap_memalign(heap, alignment, size);
	}

	if (sParanoidValidation)
		heap_validate_heap(heap);

	if (result == NULL) {
		panic("heap: heap has run out of memory trying to allocate %" B_PRIuSIZE " bytes\n",
			size);
	}

	if (alignment != 0)
		ASSERT((addr_t)result % alignment == 0);

	return result;
}


static void *
debug_heap_malloc(size_t size)
{
	if (sUseGuardPage)
		return debug_heap_malloc_with_guard_page(size);

	return debug_heap_memalign(sDefaultAlignment, size);
}


static void
debug_heap_free(void *address)
{
	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++) {
		heap_allocator *heap = sHeaps[i];
		if (heap_free(heap, address) == B_OK) {
			if (sParanoidValidation)
				heap_validate_heap(heap);
			return;
		}
	}

	// or maybe it was a huge allocation using an area
	area_info areaInfo;
	area_id area = area_for(address);
	if (area >= B_OK && get_area_info(area, &areaInfo) == B_OK) {
		area_allocation_info *info = (area_allocation_info *)areaInfo.address;

		// just make extra sure it was allocated by us
		if (info->magic == kAreaAllocationMagic && info->area == area
			&& info->size == areaInfo.size && info->base == areaInfo.address
			&& info->allocation_size < areaInfo.size) {
			delete_area(area);
			INFO(("free(): freed huge allocation by deleting area %" B_PRId32 "\n",
				area));
			return;
		}
	}

	panic("free(): free failed for address %p\n", address);
}


static void *
debug_heap_realloc(void *address, size_t newSize)
{
	if (address == NULL)
		return debug_heap_memalign(sDefaultAlignment, newSize);

	if (newSize == 0) {
		free(address);
		return NULL;
	}

	void *newAddress = NULL;
	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++) {
		heap_allocator *heap = sHeaps[i];
		if (heap_realloc(heap, address, &newAddress, newSize) == B_OK) {
			if (sParanoidValidation)
				heap_validate_heap(heap);
			return newAddress;
		}
	}

	// or maybe it was a huge allocation using an area
	area_info areaInfo;
	area_id area = area_for(address);
	if (area >= B_OK && get_area_info(area, &areaInfo) == B_OK) {
		area_allocation_info *info = (area_allocation_info *)areaInfo.address;

		// just make extra sure it was allocated by us
		if (info->magic == kAreaAllocationMagic && info->area == area
			&& info->size == areaInfo.size && info->base == areaInfo.address
			&& info->allocation_size < areaInfo.size) {
			if (sUseGuardPage) {
				size_t available = info->size - B_PAGE_SIZE
					- sizeof(area_allocation_info);

				if (available >= newSize) {
					// there is enough room available for the newSize
					newAddress = (void*)((addr_t)info->allocation_base
						+ info->allocation_size - newSize);
					INFO(("realloc(): new size %" B_PRIuSIZE
						" fits in old area %" B_PRId32 " with "
						"%" B_PRIuSIZE " available -> new address: %p\n",
						newSize, area, available, newAddress));
					memmove(newAddress, info->allocation_base,
						min_c(newSize, info->allocation_size));
					info->allocation_base = newAddress;
					info->allocation_size = newSize;
					return newAddress;
				}
			} else {
				size_t available = info->size - ((addr_t)info->allocation_base
					- (addr_t)info->base);

				if (available >= newSize) {
					// there is enough room available for the newSize
					INFO(("realloc(): new size %" B_PRIuSIZE
						" fits in old area %" B_PRId32 " with "
						"%" B_PRIuSIZE " available\n",
						newSize, area, available));
					info->allocation_size = newSize;
					return address;
				}
			}

			// have to allocate/copy/free - TODO maybe resize the area instead?
			newAddress = debug_heap_memalign(sDefaultAlignment, newSize);
			if (newAddress == NULL) {
				panic("realloc(): failed to allocate new block of %" B_PRIuSIZE
					" bytes\n", newSize);
				return NULL;
			}

			memcpy(newAddress, address, min_c(newSize, info->allocation_size));
			delete_area(area);
			INFO(("realloc(): allocated new block %p for size %" B_PRIuSIZE
				" and deleted old area %" B_PRId32 "\n",
				newAddress, newSize, area));
			return newAddress;
		}
	}

	panic("realloc(): failed to realloc address %p to size %" B_PRIuSIZE "\n", address,
		newSize);
	return NULL;
}


heap_implementation __mallocDebugHeap = {
	debug_heap_init,
	NULL,	// terminate_after

	debug_heap_memalign,
	debug_heap_malloc,
	debug_heap_free,
	debug_heap_realloc,

	NULL,	// calloc
	NULL,	// valloc
	NULL,	// posix_memalign

	debug_heap_start_wall_checking,
	debug_heap_stop_wall_checking,
	debug_heap_set_paranoid_validation,
	debug_heap_set_memory_reuse,
	debug_heap_set_debugger_calls,
	debug_heap_set_default_alignment,
	debug_heap_validate_heaps,
	heap_validate_walls,
	dump_allocations,
	debug_heap_dump_heaps,
	debug_heap_malloc_with_guard_page,
	debug_heap_get_allocation_info,

	NULL,	// set_dump_allocations_on_exit
	NULL	// set_stack_trace_depth
};