1/*
2 * Copyright 2008-2009, Michael Lotz, mmlr@mlotz.ch.
3 * Distributed under the terms of the MIT License.
4 *
5 * Copyright 2002-2011, Axel Dörfler, axeld@pinc-software.de.
6 * Distributed under the terms of the MIT License.
7 *
8 * Copyright 2001, Travis Geiselbrecht. All rights reserved.
9 * Distributed under the terms of the NewOS License.
10 */
11
12
13#include "malloc_debug_api.h"
14
15#include <malloc.h>
16#include <stdio.h>
17#include <string.h>
18#include <stdlib.h>
19
20#include <errno.h>
21#include <sys/mman.h>
22
23#include <errno_private.h>
24#include <locks.h>
25#include <syscalls.h>
26
27#include <Debug.h>
28#include <OS.h>
29
30
31//#define TRACE_HEAP
32#ifdef TRACE_HEAP
33#	define INFO(x) debug_printf x
34#else
35#	define INFO(x) ;
36#endif
37
38#undef ASSERT
39#define ASSERT(x)	if (!(x)) panic("assert failed: %s", #x);
40
41
42static void *debug_heap_memalign(size_t alignment, size_t size);
43
44
45static bool sDebuggerCalls = true;
46static bool sReuseMemory = true;
47static bool sParanoidValidation = false;
48static thread_id sWallCheckThread = -1;
49static bool sStopWallChecking = false;
50static bool sUseGuardPage = false;
51
52#if __cplusplus >= 201103L
53#include <cstddef>
54using namespace std;
55static size_t sDefaultAlignment = alignof(max_align_t);
56#else
57static size_t sDefaultAlignment = 8;
58#endif
59
60
61void
62panic(const char *format, ...)
63{
64	char buffer[1024];
65
66	va_list args;
67	va_start(args, format);
68	vsnprintf(buffer, sizeof(buffer), format, args);
69	va_end(args);
70
71	if (sDebuggerCalls)
72		debugger(buffer);
73	else
74		debug_printf(buffer);
75}
76
77
78#define ROUNDUP(x, y)		(((x) + (y) - 1) / (y) * (y))
79
80#define HEAP_INITIAL_SIZE			1 * 1024 * 1024
81#define HEAP_GROW_SIZE				2 * 1024 * 1024
82#define HEAP_AREA_USE_THRESHOLD		1 * 1024 * 1024
83
84typedef struct heap_leak_check_info_s {
85	size_t		size;
86	thread_id	thread;
87} heap_leak_check_info;
88
89typedef struct heap_page_s heap_page;
90
91typedef struct heap_area_s {
92	area_id			area;
93
94	addr_t			base;
95	size_t			size;
96
97	uint32			page_count;
98	uint32			free_page_count;
99
100	heap_page *		free_pages;
101	heap_page *		page_table;
102
103	heap_area_s *	prev;
104	heap_area_s *	next;
105	heap_area_s *	all_next;
106} heap_area;
107
108typedef struct heap_page_s {
109	heap_area *		area;
110	uint16			index;
111	uint16			bin_index : 5;
112	uint16			free_count : 10;
113	uint16			in_use : 1;
114	heap_page_s *	next;
115	heap_page_s *	prev;
116	union {
117		uint16			empty_index;
118		uint16			allocation_id; // used for bin == bin_count allocations
119	};
120	addr_t *		free_list;
121} heap_page;
122
123typedef struct heap_bin_s {
124	mutex		lock;
125	uint32		element_size;
126	uint16		max_free_count;
127	heap_page *	page_list; // sorted so that the desired page is always first
128} heap_bin;
129
130typedef struct heap_allocator_s {
131	rw_lock		area_lock;
132	mutex		page_lock;
133
134	const char *name;
135	uint32		bin_count;
136	uint32		page_size;
137
138	uint32		total_pages;
139	uint32		total_free_pages;
140	uint32		empty_areas;
141
142	heap_bin *	bins;
143	heap_area *	areas; // sorted so that the desired area is always first
144	heap_area *	all_areas; // all areas including full ones
145} heap_allocator;
146
147static const uint32 kAreaAllocationMagic = 'AAMG';
148typedef struct area_allocation_info_s {
149	area_id		area;
150	void *		base;
151	uint32		magic;
152	size_t		size;
153	thread_id	thread;
154	size_t		allocation_size;
155	size_t		allocation_alignment;
156	void *		allocation_base;
157} area_allocation_info;
158
159typedef struct heap_class_s {
160	const char *name;
161	uint32		initial_percentage;
162	size_t		max_allocation_size;
163	size_t		page_size;
164	size_t		min_bin_size;
165	size_t		bin_alignment;
166	uint32		min_count_per_page;
167	size_t		max_waste_per_page;
168} heap_class;
169
170// Heap class configuration
171#define HEAP_CLASS_COUNT 3
172static const heap_class sHeapClasses[HEAP_CLASS_COUNT] = {
173	{
174		"small",					/* name */
175		50,							/* initial percentage */
176		B_PAGE_SIZE / 8,			/* max allocation size */
177		B_PAGE_SIZE,				/* page size */
178		8,							/* min bin size */
179		4,							/* bin alignment */
180		8,							/* min count per page */
181		16							/* max waste per page */
182	},
183	{
184		"medium",					/* name */
185		30,							/* initial percentage */
186		B_PAGE_SIZE * 2,			/* max allocation size */
187		B_PAGE_SIZE * 8,			/* page size */
188		B_PAGE_SIZE / 8,			/* min bin size */
189		32,							/* bin alignment */
190		4,							/* min count per page */
191		64							/* max waste per page */
192	},
193	{
194		"large",					/* name */
195		20,							/* initial percentage */
196		HEAP_AREA_USE_THRESHOLD,	/* max allocation size */
197		B_PAGE_SIZE * 16,			/* page size */
198		B_PAGE_SIZE * 2,			/* min bin size */
199		128,						/* bin alignment */
200		1,							/* min count per page */
201		256							/* max waste per page */
202	}
203};
204
205static heap_allocator *sHeaps[HEAP_CLASS_COUNT];
206
207
208// #pragma mark - Debug functions
209
210
211static void
212dump_page(heap_page *page)
213{
214	uint32 count = 0;
215	for (addr_t *temp = page->free_list; temp != NULL; temp = (addr_t *)*temp)
216		count++;
217
218	printf("\t\tpage %p: bin_index: %u; free_count: %u; empty_index: %u; "
219		"free_list %p (%" B_PRIu32 " entr%s)\n", page, page->bin_index,
220		page->free_count, page->empty_index, page->free_list, count,
221		count == 1 ? "y" : "ies");
222}
223
224
225static void
226dump_bin(heap_bin *bin)
227{
228	printf("\telement_size: %" B_PRIu32 "; max_free_count: %u; page_list %p;\n",
229		bin->element_size, bin->max_free_count, bin->page_list);
230
231	for (heap_page *temp = bin->page_list; temp != NULL; temp = temp->next)
232		dump_page(temp);
233}
234
235
236static void
237dump_bin_list(heap_allocator *heap)
238{
239	for (uint32 i = 0; i < heap->bin_count; i++)
240		dump_bin(&heap->bins[i]);
241	printf("\n");
242}
243
244
245static void
246dump_allocator_areas(heap_allocator *heap)
247{
248	heap_area *area = heap->all_areas;
249	while (area) {
250		printf("\tarea %p: area: %" B_PRId32 "; base: 0x%08lx; size: %lu; "
251			"page_count: %" B_PRIu32 "; free_pages: %p (%" B_PRIu32 " entr%s)\n",
252			area, area->area, area->base, area->size, area->page_count,
253			area->free_pages, area->free_page_count,
254			area->free_page_count == 1 ? "y" : "ies");
255		area = area->all_next;
256	}
257
258	printf("\n");
259}
260
261
262static void
263dump_allocator(heap_allocator *heap, bool areas, bool bins)
264{
265	printf("allocator %p: name: %s; page_size: %" B_PRIu32 "; bin_count: %"
266		B_PRIu32 "; pages: %" B_PRIu32 "; free_pages: %" B_PRIu32 "; "
267		"empty_areas: %" B_PRIu32 "\n", heap, heap->name, heap->page_size,
268		heap->bin_count, heap->total_pages, heap->total_free_pages,
269		heap->empty_areas);
270
271	if (areas)
272		dump_allocator_areas(heap);
273	if (bins)
274		dump_bin_list(heap);
275}
276
277
278static void
279dump_allocations(bool statsOnly, thread_id thread)
280{
281	size_t totalSize = 0;
282	uint32 totalCount = 0;
283	for (uint32 classIndex = 0; classIndex < HEAP_CLASS_COUNT; classIndex++) {
284		heap_allocator *heap = sHeaps[classIndex];
285
286		// go through all the pages in all the areas
287		heap_area *area = heap->all_areas;
288		while (area) {
289			heap_leak_check_info *info = NULL;
290			for (uint32 i = 0; i < area->page_count; i++) {
291				heap_page *page = &area->page_table[i];
292				if (!page->in_use)
293					continue;
294
295				addr_t base = area->base + i * heap->page_size;
296				if (page->bin_index < heap->bin_count) {
297					// page is used by a small allocation bin
298					uint32 elementCount = page->empty_index;
299					size_t elementSize
300						= heap->bins[page->bin_index].element_size;
301					for (uint32 j = 0; j < elementCount;
302							j++, base += elementSize) {
303						// walk the free list to see if this element is in use
304						bool elementInUse = true;
305						for (addr_t *temp = page->free_list; temp != NULL;
306								temp = (addr_t *)*temp) {
307							if ((addr_t)temp == base) {
308								elementInUse = false;
309								break;
310							}
311						}
312
313						if (!elementInUse)
314							continue;
315
316						info = (heap_leak_check_info *)(base + elementSize
317							- sizeof(heap_leak_check_info));
318
319						if (thread == -1 || info->thread == thread) {
320							// interesting...
321							if (!statsOnly) {
322								printf("thread: % 6" B_PRId32 "; address: "
323									"0x%08lx; size: %lu bytes\n", info->thread,
324									base, info->size);
325							}
326
327							totalSize += info->size;
328							totalCount++;
329						}
330					}
331				} else {
332					// page is used by a big allocation, find the page count
333					uint32 pageCount = 1;
334					while (i + pageCount < area->page_count
335						&& area->page_table[i + pageCount].in_use
336						&& area->page_table[i + pageCount].bin_index
337							== heap->bin_count
338						&& area->page_table[i + pageCount].allocation_id
339							== page->allocation_id)
340						pageCount++;
341
342					info = (heap_leak_check_info *)(base + pageCount
343						* heap->page_size - sizeof(heap_leak_check_info));
344
345					if (thread == -1 || info->thread == thread) {
346						// interesting...
347						if (!statsOnly) {
348							printf("thread: % 6" B_PRId32 "; address: 0x%08lx;"
349								" size: %lu bytes\n", info->thread,
350								base, info->size);
351						}
352
353						totalSize += info->size;
354						totalCount++;
355					}
356
357					// skip the allocated pages
358					i += pageCount - 1;
359				}
360			}
361
362			area = area->all_next;
363		}
364	}
365
366	printf("total allocations: %" B_PRIu32 "; total bytes: %lu\n", totalCount,
367		totalSize);
368}
369
370
371static void
372heap_validate_walls()
373{
374	for (uint32 classIndex = 0; classIndex < HEAP_CLASS_COUNT; classIndex++) {
375		heap_allocator *heap = sHeaps[classIndex];
376		ReadLocker areaReadLocker(heap->area_lock);
377		for (uint32 i = 0; i < heap->bin_count; i++)
378			mutex_lock(&heap->bins[i].lock);
379		MutexLocker pageLocker(heap->page_lock);
380
381		// go through all the pages in all the areas
382		heap_area *area = heap->all_areas;
383		while (area) {
384			heap_leak_check_info *info = NULL;
385			for (uint32 i = 0; i < area->page_count; i++) {
386				heap_page *page = &area->page_table[i];
387				if (!page->in_use)
388					continue;
389
390				addr_t base = area->base + i * heap->page_size;
391				if (page->bin_index < heap->bin_count) {
392					// page is used by a small allocation bin
393					uint32 elementCount = page->empty_index;
394					size_t elementSize
395						= heap->bins[page->bin_index].element_size;
396					for (uint32 j = 0; j < elementCount;
397							j++, base += elementSize) {
398						// walk the free list to see if this element is in use
399						bool elementInUse = true;
400						for (addr_t *temp = page->free_list; temp != NULL;
401								temp = (addr_t *)*temp) {
402							if ((addr_t)temp == base) {
403								elementInUse = false;
404								break;
405							}
406						}
407
408						if (!elementInUse)
409							continue;
410
411						info = (heap_leak_check_info *)(base + elementSize
412							- sizeof(heap_leak_check_info));
413						if (info->size > elementSize - sizeof(addr_t)
414								- sizeof(heap_leak_check_info)) {
415							panic("leak check info has invalid size %lu for"
416								" element size %lu\n", info->size, elementSize);
417							continue;
418						}
419
420						addr_t wallValue;
421						addr_t wallAddress = base + info->size;
422						memcpy(&wallValue, (void *)wallAddress, sizeof(addr_t));
423						if (wallValue != wallAddress) {
424							panic("someone wrote beyond small allocation at"
425								" 0x%08lx; size: %lu bytes; allocated by %ld;"
426								" value: 0x%08lx\n", base, info->size,
427								info->thread, wallValue);
428						}
429					}
430				} else {
431					// page is used by a big allocation, find the page count
432					uint32 pageCount = 1;
433					while (i + pageCount < area->page_count
434						&& area->page_table[i + pageCount].in_use
435						&& area->page_table[i + pageCount].bin_index
436							== heap->bin_count
437						&& area->page_table[i + pageCount].allocation_id
438							== page->allocation_id)
439						pageCount++;
440
441					info = (heap_leak_check_info *)(base + pageCount
442						* heap->page_size - sizeof(heap_leak_check_info));
443
444					if (info->size > pageCount * heap->page_size
445							- sizeof(addr_t) - sizeof(heap_leak_check_info)) {
446						panic("leak check info has invalid size %lu for"
447							" page count %lu (%lu bytes)\n", info->size,
448							pageCount, pageCount * heap->page_size);
449						continue;
450					}
451
452					addr_t wallValue;
453					addr_t wallAddress = base + info->size;
454					memcpy(&wallValue, (void *)wallAddress, sizeof(addr_t));
455					if (wallValue != wallAddress) {
456						panic("someone wrote beyond big allocation at 0x%08lx;"
457							" size: %lu bytes; allocated by %ld;"
458							" value: 0x%08lx\n", base, info->size,
459							info->thread, wallValue);
460					}
461
462					// skip the allocated pages
463					i += pageCount - 1;
464				}
465			}
466
467			area = area->all_next;
468		}
469
470		pageLocker.Unlock();
471		for (uint32 i = 0; i < heap->bin_count; i++)
472			mutex_unlock(&heap->bins[i].lock);
473	}
474}
475
476
477static void
478heap_validate_heap(heap_allocator *heap)
479{
480	ReadLocker areaReadLocker(heap->area_lock);
481	for (uint32 i = 0; i < heap->bin_count; i++)
482		mutex_lock(&heap->bins[i].lock);
483	MutexLocker pageLocker(heap->page_lock);
484
485	uint32 totalPageCount = 0;
486	uint32 totalFreePageCount = 0;
487	heap_area *area = heap->all_areas;
488	while (area != NULL) {
489		// validate the free pages list
490		uint32 freePageCount = 0;
491		heap_page *lastPage = NULL;
492		heap_page *page = area->free_pages;
493		while (page) {
494			if ((addr_t)page < (addr_t)&area->page_table[0]
495				|| (addr_t)page >= (addr_t)&area->page_table[area->page_count])
496				panic("free page is not part of the page table\n");
497
498			if (page->index >= area->page_count)
499				panic("free page has invalid index\n");
500
501			if ((addr_t)&area->page_table[page->index] != (addr_t)page)
502				panic("free page index does not lead to target page\n");
503
504			if (page->prev != lastPage)
505				panic("free page entry has invalid prev link\n");
506
507			if (page->in_use)
508				panic("free page marked as in use\n");
509
510			lastPage = page;
511			page = page->next;
512			freePageCount++;
513		}
514
515		totalPageCount += freePageCount;
516		totalFreePageCount += freePageCount;
517		if (area->free_page_count != freePageCount) {
518			panic("free page count %ld doesn't match free page list %ld\n",
519				area->free_page_count, freePageCount);
520		}
521
522		// validate the page table
523		uint32 usedPageCount = 0;
524		for (uint32 i = 0; i < area->page_count; i++) {
525			if (area->page_table[i].in_use)
526				usedPageCount++;
527		}
528
529		totalPageCount += usedPageCount;
530		if (freePageCount + usedPageCount != area->page_count) {
531			panic("free pages and used pages do not add up (%lu + %lu != %lu)\n",
532				freePageCount, usedPageCount, area->page_count);
533		}
534
535		area = area->all_next;
536	}
537
538	// validate the areas
539	area = heap->areas;
540	heap_area *lastArea = NULL;
541	uint32 lastFreeCount = 0;
542	while (area != NULL) {
543		if (area->free_page_count < lastFreeCount)
544			panic("size ordering of area list broken\n");
545
546		if (area->prev != lastArea)
547			panic("area list entry has invalid prev link\n");
548
549		lastArea = area;
550		lastFreeCount = area->free_page_count;
551		area = area->next;
552	}
553
554	lastArea = NULL;
555	area = heap->all_areas;
556	while (area != NULL) {
557		if (lastArea != NULL && lastArea->base < area->base)
558			panic("base ordering of all_areas list broken\n");
559
560		lastArea = area;
561		area = area->all_next;
562	}
563
564	// validate the bins
565	for (uint32 i = 0; i < heap->bin_count; i++) {
566		heap_bin *bin = &heap->bins[i];
567		heap_page *lastPage = NULL;
568		heap_page *page = bin->page_list;
569		lastFreeCount = 0;
570		while (page) {
571			area = heap->all_areas;
572			while (area) {
573				if (area == page->area)
574					break;
575				area = area->all_next;
576			}
577
578			if (area == NULL) {
579				panic("page area not present in area list\n");
580				page = page->next;
581				continue;
582			}
583
584			if ((addr_t)page < (addr_t)&area->page_table[0]
585				|| (addr_t)page >= (addr_t)&area->page_table[area->page_count])
586				panic("used page is not part of the page table\n");
587
588			if (page->index >= area->page_count)
589				panic("used page has invalid index %lu\n", page->index);
590
591			if ((addr_t)&area->page_table[page->index] != (addr_t)page) {
592				panic("used page index does not lead to target page"
593					" (%lu vs. %lu)\n", (addr_t)&area->page_table[page->index],
594					page);
595			}
596
597			if (page->prev != lastPage) {
598				panic("used page entry has invalid prev link (%p vs %p bin "
599					"%lu)\n", page->prev, lastPage, i);
600			}
601
602			if (!page->in_use)
603				panic("used page %p marked as not in use\n", page);
604
605			if (page->bin_index != i) {
606				panic("used page with bin index %u in page list of bin %lu\n",
607					page->bin_index, i);
608			}
609
610			if (page->free_count < lastFreeCount)
611				panic("ordering of bin page list broken\n");
612
613			// validate the free list
614			uint32 freeSlotsCount = 0;
615			addr_t *element = page->free_list;
616			addr_t pageBase = area->base + page->index * heap->page_size;
617			while (element) {
618				if ((addr_t)element < pageBase
619					|| (addr_t)element >= pageBase + heap->page_size)
620					panic("free list entry out of page range %p\n", element);
621
622				if (((addr_t)element - pageBase) % bin->element_size != 0)
623					panic("free list entry not on a element boundary\n");
624
625				element = (addr_t *)*element;
626				freeSlotsCount++;
627			}
628
629			uint32 slotCount = bin->max_free_count;
630			if (page->empty_index > slotCount) {
631				panic("empty index beyond slot count (%u with %lu slots)\n",
632					page->empty_index, slotCount);
633			}
634
635			freeSlotsCount += (slotCount - page->empty_index);
636			if (freeSlotsCount > slotCount)
637				panic("more free slots than fit into the page\n");
638
639			lastPage = page;
640			lastFreeCount = page->free_count;
641			page = page->next;
642		}
643	}
644
645	pageLocker.Unlock();
646	for (uint32 i = 0; i < heap->bin_count; i++)
647		mutex_unlock(&heap->bins[i].lock);
648}
649
650
651// #pragma mark - Heap functions
652
653
654static void
655heap_add_area(heap_allocator *heap, area_id areaID, addr_t base, size_t size)
656{
657	heap_area *area = (heap_area *)base;
658	area->area = areaID;
659
660	base += sizeof(heap_area);
661	size -= sizeof(heap_area);
662
663	uint32 pageCount = size / heap->page_size;
664	size_t pageTableSize = pageCount * sizeof(heap_page);
665	area->page_table = (heap_page *)base;
666	base += pageTableSize;
667	size -= pageTableSize;
668
669	// the rest is now actually usable memory (rounded to the next page)
670	area->base = ROUNDUP(base, B_PAGE_SIZE);
671	area->size = size & ~(B_PAGE_SIZE - 1);
672
673	// now we know the real page count
674	pageCount = area->size / heap->page_size;
675	area->page_count = pageCount;
676
677	// zero out the page table and fill in page indexes
678	memset((void *)area->page_table, 0, pageTableSize);
679	for (uint32 i = 0; i < pageCount; i++) {
680		area->page_table[i].area = area;
681		area->page_table[i].index = i;
682	}
683
684	// add all pages up into the free pages list
685	for (uint32 i = 1; i < pageCount; i++) {
686		area->page_table[i - 1].next = &area->page_table[i];
687		area->page_table[i].prev = &area->page_table[i - 1];
688	}
689	area->free_pages = &area->page_table[0];
690	area->free_page_count = pageCount;
691	area->page_table[0].prev = NULL;
692	area->next = NULL;
693
694	WriteLocker areaWriteLocker(heap->area_lock);
695	MutexLocker pageLocker(heap->page_lock);
696	if (heap->areas == NULL) {
697		// it's the only (empty) area in that heap
698		area->prev = NULL;
699		heap->areas = area;
700	} else {
701		// link in this area as the last one as it is completely empty
702		heap_area *lastArea = heap->areas;
703		while (lastArea->next != NULL)
704			lastArea = lastArea->next;
705
706		lastArea->next = area;
707		area->prev = lastArea;
708	}
709
710	// insert this area in the all_areas list so it stays ordered by base
711	if (heap->all_areas == NULL || heap->all_areas->base < area->base) {
712		area->all_next = heap->all_areas;
713		heap->all_areas = area;
714	} else {
715		heap_area *insert = heap->all_areas;
716		while (insert->all_next && insert->all_next->base > area->base)
717			insert = insert->all_next;
718
719		area->all_next = insert->all_next;
720		insert->all_next = area;
721	}
722
723	heap->total_pages += area->page_count;
724	heap->total_free_pages += area->free_page_count;
725
726	if (areaID >= 0) {
727		// this later on deletable area is yet empty - the empty count will be
728		// decremented as soon as this area is used for the first time
729		heap->empty_areas++;
730	}
731
732	pageLocker.Unlock();
733	areaWriteLocker.Unlock();
734}
735
736
737static status_t
738heap_remove_area(heap_allocator *heap, heap_area *area)
739{
740	if (area->free_page_count != area->page_count) {
741		panic("tried removing heap area that has still pages in use");
742		return B_ERROR;
743	}
744
745	if (area->prev == NULL && area->next == NULL) {
746		panic("tried removing the last non-full heap area");
747		return B_ERROR;
748	}
749
750	if (heap->areas == area)
751		heap->areas = area->next;
752	if (area->prev != NULL)
753		area->prev->next = area->next;
754	if (area->next != NULL)
755		area->next->prev = area->prev;
756
757	if (heap->all_areas == area)
758		heap->all_areas = area->all_next;
759	else {
760		heap_area *previous = heap->all_areas;
761		while (previous) {
762			if (previous->all_next == area) {
763				previous->all_next = area->all_next;
764				break;
765			}
766
767			previous = previous->all_next;
768		}
769
770		if (previous == NULL)
771			panic("removing heap area that is not in all list");
772	}
773
774	heap->total_pages -= area->page_count;
775	heap->total_free_pages -= area->free_page_count;
776	return B_OK;
777}
778
779
780static heap_allocator *
781heap_create_allocator(const char *name, addr_t base, size_t size,
782	const heap_class *heapClass)
783{
784	heap_allocator *heap = (heap_allocator *)base;
785	base += sizeof(heap_allocator);
786	size -= sizeof(heap_allocator);
787
788	heap->name = name;
789	heap->page_size = heapClass->page_size;
790	heap->total_pages = heap->total_free_pages = heap->empty_areas = 0;
791	heap->areas = heap->all_areas = NULL;
792	heap->bins = (heap_bin *)base;
793
794	heap->bin_count = 0;
795	size_t binSize = 0, lastSize = 0;
796	uint32 count = heap->page_size / heapClass->min_bin_size;
797	for (; count >= heapClass->min_count_per_page; count--, lastSize = binSize) {
798		if (heap->bin_count >= 32)
799			panic("heap configuration invalid - max bin count reached\n");
800
801		binSize = (heap->page_size / count) & ~(heapClass->bin_alignment - 1);
802		if (binSize == lastSize)
803			continue;
804		if (heap->page_size - count * binSize > heapClass->max_waste_per_page)
805			continue;
806
807		heap_bin *bin = &heap->bins[heap->bin_count];
808		mutex_init(&bin->lock, "heap bin lock");
809		bin->element_size = binSize;
810		bin->max_free_count = heap->page_size / binSize;
811		bin->page_list = NULL;
812		heap->bin_count++;
813	};
814
815	base += heap->bin_count * sizeof(heap_bin);
816	size -= heap->bin_count * sizeof(heap_bin);
817
818	rw_lock_init(&heap->area_lock, "heap area lock");
819	mutex_init(&heap->page_lock, "heap page lock");
820
821	heap_add_area(heap, -1, base, size);
822	return heap;
823}
824
825
826static inline void
827heap_free_pages_added(heap_allocator *heap, heap_area *area, uint32 pageCount)
828{
829	area->free_page_count += pageCount;
830	heap->total_free_pages += pageCount;
831
832	if (area->free_page_count == pageCount) {
833		// we need to add ourselfs to the area list of the heap
834		area->prev = NULL;
835		area->next = heap->areas;
836		if (area->next)
837			area->next->prev = area;
838		heap->areas = area;
839	} else {
840		// we might need to move back in the area list
841		if (area->next && area->next->free_page_count < area->free_page_count) {
842			// move ourselfs so the list stays ordered
843			heap_area *insert = area->next;
844			while (insert->next
845				&& insert->next->free_page_count < area->free_page_count)
846				insert = insert->next;
847
848			if (area->prev)
849				area->prev->next = area->next;
850			if (area->next)
851				area->next->prev = area->prev;
852			if (heap->areas == area)
853				heap->areas = area->next;
854
855			area->prev = insert;
856			area->next = insert->next;
857			if (area->next)
858				area->next->prev = area;
859			insert->next = area;
860		}
861	}
862
863	if (area->free_page_count == area->page_count && area->area >= 0)
864		heap->empty_areas++;
865}
866
867
868static inline void
869heap_free_pages_removed(heap_allocator *heap, heap_area *area, uint32 pageCount)
870{
871	if (area->free_page_count == area->page_count && area->area >= 0) {
872		// this area was completely empty
873		heap->empty_areas--;
874	}
875
876	area->free_page_count -= pageCount;
877	heap->total_free_pages -= pageCount;
878
879	if (area->free_page_count == 0) {
880		// the area is now full so we remove it from the area list
881		if (area->prev)
882			area->prev->next = area->next;
883		if (area->next)
884			area->next->prev = area->prev;
885		if (heap->areas == area)
886			heap->areas = area->next;
887		area->next = area->prev = NULL;
888	} else {
889		// we might need to move forward in the area list
890		if (area->prev && area->prev->free_page_count > area->free_page_count) {
891			// move ourselfs so the list stays ordered
892			heap_area *insert = area->prev;
893			while (insert->prev
894				&& insert->prev->free_page_count > area->free_page_count)
895				insert = insert->prev;
896
897			if (area->prev)
898				area->prev->next = area->next;
899			if (area->next)
900				area->next->prev = area->prev;
901
902			area->prev = insert->prev;
903			area->next = insert;
904			if (area->prev)
905				area->prev->next = area;
906			if (heap->areas == insert)
907				heap->areas = area;
908			insert->prev = area;
909		}
910	}
911}
912
913
914static inline void
915heap_link_page(heap_page *page, heap_page **list)
916{
917	page->prev = NULL;
918	page->next = *list;
919	if (page->next)
920		page->next->prev = page;
921	*list = page;
922}
923
924
925static inline void
926heap_unlink_page(heap_page *page, heap_page **list)
927{
928	if (page->prev)
929		page->prev->next = page->next;
930	if (page->next)
931		page->next->prev = page->prev;
932	if (list && *list == page) {
933		*list = page->next;
934		if (page->next)
935			page->next->prev = NULL;
936	}
937}
938
939
940static heap_page *
941heap_allocate_contiguous_pages(heap_allocator *heap, uint32 pageCount,
942	size_t alignment)
943{
944	heap_area *area = heap->areas;
945	while (area) {
946		if (area->free_page_count < pageCount) {
947			area = area->next;
948			continue;
949		}
950
951		uint32 step = 1;
952		uint32 firstValid = 0;
953		const uint32 lastValid = area->page_count - pageCount + 1;
954
955		if (alignment > heap->page_size) {
956			firstValid = (ROUNDUP(area->base, alignment) - area->base)
957				/ heap->page_size;
958			step = alignment / heap->page_size;
959		}
960
961		int32 first = -1;
962		for (uint32 i = firstValid; i < lastValid; i += step) {
963			if (area->page_table[i].in_use)
964				continue;
965
966			first = i;
967
968			for (uint32 j = 1; j < pageCount; j++) {
969				if (area->page_table[i + j].in_use) {
970					first = -1;
971					i += j / step * step;
972					break;
973				}
974			}
975
976			if (first >= 0)
977				break;
978		}
979
980		if (first < 0) {
981			area = area->next;
982			continue;
983		}
984
985		for (uint32 i = first; i < first + pageCount; i++) {
986			heap_page *page = &area->page_table[i];
987			page->in_use = 1;
988			page->bin_index = heap->bin_count;
989
990			heap_unlink_page(page, &area->free_pages);
991
992			page->next = page->prev = NULL;
993			page->free_list = NULL;
994			page->allocation_id = (uint16)first;
995		}
996
997		heap_free_pages_removed(heap, area, pageCount);
998		return &area->page_table[first];
999	}
1000
1001	return NULL;
1002}
1003
1004
1005static void
1006heap_add_leak_check_info(addr_t address, size_t allocated, size_t size)
1007{
1008	size -= sizeof(addr_t) + sizeof(heap_leak_check_info);
1009	heap_leak_check_info *info = (heap_leak_check_info *)(address + allocated
1010		- sizeof(heap_leak_check_info));
1011	info->thread = find_thread(NULL);
1012	info->size = size;
1013
1014	addr_t wallAddress = address + size;
1015	memcpy((void *)wallAddress, &wallAddress, sizeof(addr_t));
1016}
1017
1018
1019static void *
1020heap_raw_alloc(heap_allocator *heap, size_t size, size_t alignment)
1021{
1022	INFO(("heap %p: allocate %lu bytes from raw pages with alignment %lu\n",
1023		heap, size, alignment));
1024
1025	uint32 pageCount = (size + heap->page_size - 1) / heap->page_size;
1026
1027	MutexLocker pageLocker(heap->page_lock);
1028	heap_page *firstPage = heap_allocate_contiguous_pages(heap, pageCount,
1029		alignment);
1030	if (firstPage == NULL) {
1031		INFO(("heap %p: found no contiguous pages to allocate %ld bytes\n",
1032			heap, size));
1033		return NULL;
1034	}
1035
1036	addr_t address = firstPage->area->base + firstPage->index * heap->page_size;
1037	heap_add_leak_check_info(address, pageCount * heap->page_size, size);
1038	return (void *)address;
1039}
1040
1041
1042static void *
1043heap_allocate_from_bin(heap_allocator *heap, uint32 binIndex, size_t size)
1044{
1045	heap_bin *bin = &heap->bins[binIndex];
1046	INFO(("heap %p: allocate %lu bytes from bin %lu with element_size %lu\n",
1047		heap, size, binIndex, bin->element_size));
1048
1049	MutexLocker binLocker(bin->lock);
1050	heap_page *page = bin->page_list;
1051	if (page == NULL) {
1052		MutexLocker pageLocker(heap->page_lock);
1053		heap_area *area = heap->areas;
1054		if (area == NULL) {
1055			INFO(("heap %p: no free pages to allocate %lu bytes\n", heap,
1056				size));
1057			return NULL;
1058		}
1059
1060		// by design there are only areas in the list that still have
1061		// free pages available
1062		page = area->free_pages;
1063		area->free_pages = page->next;
1064		if (page->next)
1065			page->next->prev = NULL;
1066
1067		heap_free_pages_removed(heap, area, 1);
1068
1069		if (page->in_use)
1070			panic("got an in use page from the free pages list\n");
1071		page->in_use = 1;
1072
1073		pageLocker.Unlock();
1074
1075		page->bin_index = binIndex;
1076		page->free_count = bin->max_free_count;
1077		page->empty_index = 0;
1078		page->free_list = NULL;
1079		page->next = page->prev = NULL;
1080		bin->page_list = page;
1081	}
1082
1083	// we have a page where we have a free slot
1084	void *address = NULL;
1085	if (page->free_list) {
1086		// there's a previously freed entry we can use
1087		address = page->free_list;
1088		page->free_list = (addr_t *)*page->free_list;
1089	} else {
1090		// the page hasn't been fully allocated so use the next empty_index
1091		address = (void *)(page->area->base + page->index * heap->page_size
1092			+ page->empty_index * bin->element_size);
1093		page->empty_index++;
1094	}
1095
1096	page->free_count--;
1097	if (page->free_count == 0) {
1098		// the page is now full so we remove it from the page_list
1099		bin->page_list = page->next;
1100		if (page->next)
1101			page->next->prev = NULL;
1102		page->next = page->prev = NULL;
1103	}
1104
1105	heap_add_leak_check_info((addr_t)address, bin->element_size, size);
1106	return address;
1107}
1108
1109
1110static void *
1111heap_memalign(heap_allocator *heap, size_t alignment, size_t size)
1112{
1113	INFO(("memalign(alignment = %lu, size = %lu)\n", alignment, size));
1114
1115	if (!is_valid_alignment(alignment)) {
1116		panic("memalign() with an alignment which is not a power of 2 (%lu)\n",
1117			alignment);
1118	}
1119
1120	size += sizeof(addr_t) + sizeof(heap_leak_check_info);
1121
1122	void *address = NULL;
1123	if (alignment < B_PAGE_SIZE) {
1124		if (alignment != 0) {
1125			// TODO: The alignment is done by ensuring that the element size
1126			// of the target bin is aligned with the requested alignment. This
1127			// has the problem that it wastes space because a better (smaller)
1128			// bin could possibly be selected. We should pick the best bin and
1129			// check if there is an aligned block in the free list or if a new
1130			// (page aligned) page has to be allocated anyway.
1131			size = ROUNDUP(size, alignment);
1132			for (uint32 i = 0; i < heap->bin_count; i++) {
1133				if (size <= heap->bins[i].element_size
1134					&& is_valid_alignment(heap->bins[i].element_size)) {
1135					address = heap_allocate_from_bin(heap, i, size);
1136					break;
1137				}
1138			}
1139		} else {
1140			for (uint32 i = 0; i < heap->bin_count; i++) {
1141				if (size <= heap->bins[i].element_size) {
1142					address = heap_allocate_from_bin(heap, i, size);
1143					break;
1144				}
1145			}
1146		}
1147	}
1148
1149	if (address == NULL)
1150		address = heap_raw_alloc(heap, size, alignment);
1151
1152	size -= sizeof(addr_t) + sizeof(heap_leak_check_info);
1153
1154	INFO(("memalign(): asked to allocate %lu bytes, returning pointer %p\n",
1155		size, address));
1156
1157	if (address == NULL)
1158		return address;
1159
1160	memset(address, 0xcc, size);
1161
1162	// make sure 0xdeadbeef is cleared if we do not overwrite the memory
1163	// and the user does not clear it
1164	if (((uint32 *)address)[1] == 0xdeadbeef)
1165		((uint32 *)address)[1] = 0xcccccccc;
1166
1167	return address;
1168}
1169
1170
1171static status_t
1172heap_free(heap_allocator *heap, void *address)
1173{
1174	if (address == NULL)
1175		return B_OK;
1176
1177	ReadLocker areaReadLocker(heap->area_lock);
1178	heap_area *area = heap->all_areas;
1179	while (area) {
1180		// since the all_areas list is ordered by base with the biggest
1181		// base at the top, we need only find the first area with a base
1182		// smaller than our address to become our only candidate for freeing
1183		if (area->base <= (addr_t)address) {
1184			if ((addr_t)address >= area->base + area->size) {
1185				// none of the other areas can contain the address as the list
1186				// is ordered
1187				return B_ENTRY_NOT_FOUND;
1188			}
1189
1190			// this area contains the allocation, we're done searching
1191			break;
1192		}
1193
1194		area = area->all_next;
1195	}
1196
1197	if (area == NULL) {
1198		// this address does not belong to us
1199		return B_ENTRY_NOT_FOUND;
1200	}
1201
1202	INFO(("free(): asked to free pointer %p\n", address));
1203
1204	heap_page *page = &area->page_table[((addr_t)address - area->base)
1205		/ heap->page_size];
1206
1207	INFO(("free(): page %p: bin_index %d, free_count %d\n", page,
1208		page->bin_index, page->free_count));
1209
1210	if (page->bin_index > heap->bin_count) {
1211		panic("free(): page %p: invalid bin_index %d\n", page,
1212			page->bin_index);
1213		return B_ERROR;
1214	}
1215
1216	addr_t pageBase = area->base + page->index * heap->page_size;
1217	if (page->bin_index < heap->bin_count) {
1218		// small allocation
1219		heap_bin *bin = &heap->bins[page->bin_index];
1220		if (((addr_t)address - pageBase) % bin->element_size != 0) {
1221			panic("free(): address %p does not fall on allocation boundary"
1222				" for page base %p and element size %lu\n", address,
1223				(void *)pageBase, bin->element_size);
1224			return B_ERROR;
1225		}
1226
1227		MutexLocker binLocker(bin->lock);
1228
1229		if (((uint32 *)address)[1] == 0xdeadbeef) {
1230			// This block looks like it was freed already, walk the free list
1231			// on this page to make sure this address doesn't exist.
1232			for (addr_t *temp = page->free_list; temp != NULL;
1233					temp = (addr_t *)*temp) {
1234				if (temp == address) {
1235					panic("free(): address %p already exists in page free"
1236						" list (double free)\n", address);
1237					return B_ERROR;
1238				}
1239			}
1240		}
1241
1242		heap_leak_check_info *info = (heap_leak_check_info *)((addr_t)address
1243			+ bin->element_size - sizeof(heap_leak_check_info));
1244		if (info->size > bin->element_size - sizeof(addr_t)
1245				- sizeof(heap_leak_check_info)) {
1246			panic("leak check info has invalid size %lu for element size %lu,"
1247				" probably memory has been overwritten past allocation size\n",
1248				info->size, bin->element_size);
1249		}
1250
1251		addr_t wallValue;
1252		addr_t wallAddress = (addr_t)address + info->size;
1253		memcpy(&wallValue, (void *)wallAddress, sizeof(addr_t));
1254		if (wallValue != wallAddress) {
1255			panic("someone wrote beyond small allocation at %p;"
1256				" size: %lu bytes; allocated by %ld; value: 0x%08lx\n",
1257				address, info->size, info->thread, wallValue);
1258		}
1259
1260		// the first 4 bytes are overwritten with the next free list pointer
1261		// later
1262		uint32 *dead = (uint32 *)address;
1263		for (uint32 i = 0; i < bin->element_size / sizeof(uint32); i++)
1264			dead[i] = 0xdeadbeef;
1265
1266		if (sReuseMemory) {
1267			// add the address to the page free list
1268			*(addr_t *)address = (addr_t)page->free_list;
1269			page->free_list = (addr_t *)address;
1270			page->free_count++;
1271
1272			if (page->free_count == bin->max_free_count) {
1273				// we are now empty, remove the page from the bin list
1274				MutexLocker pageLocker(heap->page_lock);
1275				heap_unlink_page(page, &bin->page_list);
1276				page->in_use = 0;
1277				heap_link_page(page, &area->free_pages);
1278				heap_free_pages_added(heap, area, 1);
1279			} else if (page->free_count == 1) {
1280				// we need to add ourselfs to the page list of the bin
1281				heap_link_page(page, &bin->page_list);
1282			} else {
1283				// we might need to move back in the free pages list
1284				if (page->next && page->next->free_count < page->free_count) {
1285					// move ourselfs so the list stays ordered
1286					heap_page *insert = page->next;
1287					while (insert->next
1288						&& insert->next->free_count < page->free_count)
1289						insert = insert->next;
1290
1291					heap_unlink_page(page, &bin->page_list);
1292
1293					page->prev = insert;
1294					page->next = insert->next;
1295					if (page->next)
1296						page->next->prev = page;
1297					insert->next = page;
1298				}
1299			}
1300		}
1301	} else {
1302		if ((addr_t)address != pageBase) {
1303			panic("free(): large allocation address %p not on page base %p\n",
1304				address, (void *)pageBase);
1305			return B_ERROR;
1306		}
1307
1308		// large allocation, just return the pages to the page free list
1309		uint32 allocationID = page->allocation_id;
1310		uint32 maxPages = area->page_count - page->index;
1311		uint32 pageCount = 0;
1312
1313		MutexLocker pageLocker(heap->page_lock);
1314		for (uint32 i = 0; i < maxPages; i++) {
1315			// loop until we find the end of this allocation
1316			if (!page[i].in_use || page[i].bin_index != heap->bin_count
1317				|| page[i].allocation_id != allocationID)
1318				break;
1319
1320			// this page still belongs to the same allocation
1321			if (sReuseMemory) {
1322				page[i].in_use = 0;
1323				page[i].allocation_id = 0;
1324
1325				// return it to the free list
1326				heap_link_page(&page[i], &area->free_pages);
1327			}
1328
1329			pageCount++;
1330		}
1331
1332		size_t allocationSize = pageCount * heap->page_size;
1333		heap_leak_check_info *info = (heap_leak_check_info *)((addr_t)address
1334			+ allocationSize - sizeof(heap_leak_check_info));
1335		if (info->size > allocationSize - sizeof(addr_t)
1336				- sizeof(heap_leak_check_info)) {
1337			panic("leak check info has invalid size %lu for allocation of %lu,"
1338				" probably memory has been overwritten past allocation size\n",
1339				info->size, allocationSize);
1340		}
1341
1342		addr_t wallValue;
1343		addr_t wallAddress = (addr_t)address + info->size;
1344		memcpy(&wallValue, (void *)wallAddress, sizeof(addr_t));
1345		if (wallValue != wallAddress) {
1346			panic("someone wrote beyond big allocation at %p;"
1347				" size: %lu bytes; allocated by %ld; value: 0x%08lx\n",
1348				address, info->size, info->thread, wallValue);
1349		}
1350
1351		uint32 *dead = (uint32 *)address;
1352		for (uint32 i = 0; i < allocationSize / sizeof(uint32); i++)
1353			dead[i] = 0xdeadbeef;
1354
1355		if (sReuseMemory)
1356			heap_free_pages_added(heap, area, pageCount);
1357	}
1358
1359	areaReadLocker.Unlock();
1360
1361	if (heap->empty_areas > 1) {
1362		WriteLocker areaWriteLocker(heap->area_lock);
1363		MutexLocker pageLocker(heap->page_lock);
1364
1365		area = heap->areas;
1366		while (area != NULL && heap->empty_areas > 1) {
1367			heap_area *next = area->next;
1368			if (area->area >= 0
1369				&& area->free_page_count == area->page_count
1370				&& heap_remove_area(heap, area) == B_OK) {
1371				delete_area(area->area);
1372				heap->empty_areas--;
1373			}
1374
1375			area = next;
1376		}
1377	}
1378
1379	return B_OK;
1380}
1381
1382
1383static status_t
1384heap_realloc(heap_allocator *heap, void *address, void **newAddress,
1385	size_t newSize)
1386{
1387	ReadLocker areaReadLocker(heap->area_lock);
1388	heap_area *area = heap->all_areas;
1389	while (area) {
1390		// since the all_areas list is ordered by base with the biggest
1391		// base at the top, we need only find the first area with a base
1392		// smaller than our address to become our only candidate for
1393		// reallocating
1394		if (area->base <= (addr_t)address) {
1395			if ((addr_t)address >= area->base + area->size) {
1396				// none of the other areas can contain the address as the list
1397				// is ordered
1398				return B_ENTRY_NOT_FOUND;
1399			}
1400
1401			// this area contains the allocation, we're done searching
1402			break;
1403		}
1404
1405		area = area->all_next;
1406	}
1407
1408	if (area == NULL) {
1409		// this address does not belong to us
1410		return B_ENTRY_NOT_FOUND;
1411	}
1412
1413	INFO(("realloc(address = %p, newSize = %lu)\n", address, newSize));
1414
1415	heap_page *page = &area->page_table[((addr_t)address - area->base)
1416		/ heap->page_size];
1417	if (page->bin_index > heap->bin_count) {
1418		panic("realloc(): page %p: invalid bin_index %d\n", page,
1419			page->bin_index);
1420		return B_ERROR;
1421	}
1422
1423	// find out the size of the old allocation first
1424	size_t minSize = 0;
1425	size_t maxSize = 0;
1426	if (page->bin_index < heap->bin_count) {
1427		// this was a small allocation
1428		heap_bin *bin = &heap->bins[page->bin_index];
1429		maxSize = bin->element_size;
1430		if (page->bin_index > 0)
1431			minSize = heap->bins[page->bin_index - 1].element_size + 1;
1432	} else {
1433		// this was a large allocation
1434		uint32 allocationID = page->allocation_id;
1435		uint32 maxPages = area->page_count - page->index;
1436		maxSize = heap->page_size;
1437
1438		MutexLocker pageLocker(heap->page_lock);
1439		for (uint32 i = 1; i < maxPages; i++) {
1440			if (!page[i].in_use || page[i].bin_index != heap->bin_count
1441				|| page[i].allocation_id != allocationID)
1442				break;
1443
1444			minSize += heap->page_size;
1445			maxSize += heap->page_size;
1446		}
1447	}
1448
1449	newSize += sizeof(addr_t) + sizeof(heap_leak_check_info);
1450
1451	// does the new allocation simply fit in the old allocation?
1452	if (newSize > minSize && newSize <= maxSize) {
1453		// update the size info (the info is at the end so stays where it is)
1454		heap_leak_check_info *info = (heap_leak_check_info *)((addr_t)address
1455			+ maxSize - sizeof(heap_leak_check_info));
1456		newSize -= sizeof(addr_t) + sizeof(heap_leak_check_info);
1457		*newAddress = address;
1458
1459		MutexLocker pageLocker(heap->page_lock);
1460		info->size = newSize;
1461		addr_t wallAddress = (addr_t)address + newSize;
1462		memcpy((void *)wallAddress, &wallAddress, sizeof(addr_t));
1463		return B_OK;
1464	}
1465
1466	areaReadLocker.Unlock();
1467
1468	// new leak check info will be created with the malloc below
1469	newSize -= sizeof(addr_t) + sizeof(heap_leak_check_info);
1470
1471	// if not, allocate a new chunk of memory
1472	*newAddress = debug_heap_memalign(sDefaultAlignment, newSize);
1473	if (*newAddress == NULL) {
1474		// we tried but it didn't work out, but still the operation is done
1475		return B_OK;
1476	}
1477
1478	// copy the old data and free the old allocation
1479	memcpy(*newAddress, address, min_c(maxSize, newSize));
1480	heap_free(heap, address);
1481	return B_OK;
1482}
1483
1484
1485inline uint32
1486heap_class_for(size_t size)
1487{
1488	// take the extra info size into account
1489	size += sizeof(addr_t) + sizeof(heap_leak_check_info);
1490
1491	uint32 index = 0;
1492	for (; index < HEAP_CLASS_COUNT - 1; index++) {
1493		if (size <= sHeapClasses[index].max_allocation_size)
1494			return index;
1495	}
1496
1497	return index;
1498}
1499
1500
1501static status_t
1502heap_get_allocation_info(heap_allocator *heap, void *address, size_t *size,
1503	thread_id *thread)
1504{
1505	ReadLocker areaReadLocker(heap->area_lock);
1506	heap_area *area = heap->all_areas;
1507	while (area) {
1508		// since the all_areas list is ordered by base with the biggest
1509		// base at the top, we need only find the first area with a base
1510		// smaller than our address to become our only candidate for freeing
1511		if (area->base <= (addr_t)address) {
1512			if ((addr_t)address >= area->base + area->size) {
1513				// none of the other areas can contain the address as the list
1514				// is ordered
1515				return B_ENTRY_NOT_FOUND;
1516			}
1517
1518			// this area contains the allocation, we're done searching
1519			break;
1520		}
1521
1522		area = area->all_next;
1523	}
1524
1525	if (area == NULL) {
1526		// this address does not belong to us
1527		return B_ENTRY_NOT_FOUND;
1528	}
1529
1530	heap_page *page = &area->page_table[((addr_t)address - area->base)
1531		/ heap->page_size];
1532
1533	if (page->bin_index > heap->bin_count) {
1534		panic("get_allocation_info(): page %p: invalid bin_index %d\n", page,
1535			page->bin_index);
1536		return B_ERROR;
1537	}
1538
1539	heap_leak_check_info *info = NULL;
1540	addr_t pageBase = area->base + page->index * heap->page_size;
1541	if (page->bin_index < heap->bin_count) {
1542		// small allocation
1543		heap_bin *bin = &heap->bins[page->bin_index];
1544		if (((addr_t)address - pageBase) % bin->element_size != 0) {
1545			panic("get_allocation_info(): address %p does not fall on"
1546				" allocation boundary for page base %p and element size %lu\n",
1547				address, (void *)pageBase, bin->element_size);
1548			return B_ERROR;
1549		}
1550
1551		MutexLocker binLocker(bin->lock);
1552
1553		info = (heap_leak_check_info *)((addr_t)address + bin->element_size
1554			- sizeof(heap_leak_check_info));
1555		if (info->size > bin->element_size - sizeof(addr_t)
1556				- sizeof(heap_leak_check_info)) {
1557			panic("leak check info has invalid size %lu for element size %lu,"
1558				" probably memory has been overwritten past allocation size\n",
1559				info->size, bin->element_size);
1560			return B_ERROR;
1561		}
1562	} else {
1563		if ((addr_t)address != pageBase) {
1564			panic("get_allocation_info(): large allocation address %p not on"
1565				" page base %p\n", address, (void *)pageBase);
1566			return B_ERROR;
1567		}
1568
1569		uint32 allocationID = page->allocation_id;
1570		uint32 maxPages = area->page_count - page->index;
1571		uint32 pageCount = 0;
1572
1573		MutexLocker pageLocker(heap->page_lock);
1574		for (uint32 i = 0; i < maxPages; i++) {
1575			// loop until we find the end of this allocation
1576			if (!page[i].in_use || page[i].bin_index != heap->bin_count
1577				|| page[i].allocation_id != allocationID)
1578				break;
1579
1580			pageCount++;
1581		}
1582
1583		size_t allocationSize = pageCount * heap->page_size;
1584		info = (heap_leak_check_info *)((addr_t)address + allocationSize
1585			- sizeof(heap_leak_check_info));
1586		if (info->size > allocationSize - sizeof(addr_t)
1587				- sizeof(heap_leak_check_info)) {
1588			panic("leak check info has invalid size %lu for allocation of %lu,"
1589				" probably memory has been overwritten past allocation size\n",
1590				info->size, allocationSize);
1591			return B_ERROR;
1592		}
1593	}
1594
1595	if (size != NULL)
1596		*size = info->size;
1597	if (thread != NULL)
1598		*thread = info->thread;
1599
1600	return B_OK;
1601}
1602
1603
1604//	#pragma mark -
1605
1606
1607static status_t
1608heap_create_new_heap_area(heap_allocator *heap, const char *name, size_t size)
1609{
1610	void *address = NULL;
1611	area_id heapArea = create_area(name, &address, B_ANY_ADDRESS, size,
1612		B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
1613	if (heapArea < B_OK) {
1614		INFO(("heap: couldn't allocate heap area \"%s\"\n", name));
1615		return heapArea;
1616	}
1617
1618	heap_add_area(heap, heapArea, (addr_t)address, size);
1619	if (sParanoidValidation)
1620		heap_validate_heap(heap);
1621
1622	return B_OK;
1623}
1624
1625
1626static int32
1627heap_wall_checker(void *data)
1628{
1629	int msInterval = (addr_t)data;
1630	while (!sStopWallChecking) {
1631		heap_validate_walls();
1632		snooze(msInterval * 1000);
1633	}
1634
1635	return 0;
1636}
1637
1638
1639//	#pragma mark - Heap Debug API
1640
1641
1642static status_t
1643debug_heap_start_wall_checking(int msInterval)
1644{
1645	if (sWallCheckThread < 0) {
1646		sWallCheckThread = spawn_thread(heap_wall_checker, "heap wall checker",
1647			B_LOW_PRIORITY, (void *)(addr_t)msInterval);
1648	}
1649
1650	if (sWallCheckThread < 0)
1651		return sWallCheckThread;
1652
1653	sStopWallChecking = false;
1654	return resume_thread(sWallCheckThread);
1655}
1656
1657
1658static status_t
1659debug_heap_stop_wall_checking()
1660{
1661	int32 result;
1662	sStopWallChecking = true;
1663	return wait_for_thread(sWallCheckThread, &result);
1664}
1665
1666
1667static void
1668debug_heap_set_paranoid_validation(bool enabled)
1669{
1670	sParanoidValidation = enabled;
1671}
1672
1673
1674static void
1675debug_heap_set_memory_reuse(bool enabled)
1676{
1677	sReuseMemory = enabled;
1678}
1679
1680
1681static void
1682debug_heap_set_debugger_calls(bool enabled)
1683{
1684	sDebuggerCalls = enabled;
1685}
1686
1687
1688static void
1689debug_heap_set_default_alignment(size_t defaultAlignment)
1690{
1691	sDefaultAlignment = defaultAlignment;
1692}
1693
1694
1695static void
1696debug_heap_validate_heaps()
1697{
1698	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++)
1699		heap_validate_heap(sHeaps[i]);
1700}
1701
1702
1703static void
1704debug_heap_dump_heaps(bool dumpAreas, bool dumpBins)
1705{
1706	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++)
1707		dump_allocator(sHeaps[i], dumpAreas, dumpBins);
1708}
1709
1710
1711static void *
1712debug_heap_malloc_with_guard_page(size_t size)
1713{
1714	size_t areaSize = ROUNDUP(size + sizeof(area_allocation_info) + B_PAGE_SIZE,
1715		B_PAGE_SIZE);
1716	if (areaSize < size) {
1717		// the size overflowed
1718		return NULL;
1719	}
1720
1721	void *address = NULL;
1722	area_id allocationArea = create_area("guarded area", &address,
1723		B_ANY_ADDRESS, areaSize, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
1724	if (allocationArea < B_OK) {
1725		panic("heap: failed to create area for guarded allocation of %lu"
1726			" bytes\n", size);
1727		return NULL;
1728	}
1729
1730	if (mprotect((void *)((addr_t)address + areaSize - B_PAGE_SIZE),
1731			B_PAGE_SIZE, PROT_NONE) != 0) {
1732		panic("heap: failed to protect guard page: %s\n", strerror(errno));
1733		delete_area(allocationArea);
1734		return NULL;
1735	}
1736
1737	area_allocation_info *info = (area_allocation_info *)address;
1738	info->magic = kAreaAllocationMagic;
1739	info->area = allocationArea;
1740	info->base = address;
1741	info->size = areaSize;
1742	info->thread = find_thread(NULL);
1743	info->allocation_size = size;
1744	info->allocation_alignment = 0;
1745
1746	// the address is calculated so that the end of the allocation
1747	// is at the end of the usable space of the requested area
1748	address = (void *)((addr_t)address + areaSize - B_PAGE_SIZE - size);
1749
1750	INFO(("heap: allocated area %ld for guarded allocation of %lu bytes\n",
1751		allocationArea, size));
1752
1753	info->allocation_base = address;
1754
1755	memset(address, 0xcc, size);
1756	return address;
1757}
1758
1759
1760static status_t
1761debug_heap_get_allocation_info(void *address, size_t *size,
1762	thread_id *thread)
1763{
1764	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++) {
1765		heap_allocator *heap = sHeaps[i];
1766		if (heap_get_allocation_info(heap, address, size, thread) == B_OK)
1767			return B_OK;
1768	}
1769
1770	// or maybe it was a huge allocation using an area
1771	area_info areaInfo;
1772	area_id area = area_for(address);
1773	if (area >= B_OK && get_area_info(area, &areaInfo) == B_OK) {
1774		area_allocation_info *info = (area_allocation_info *)areaInfo.address;
1775
1776		// just make extra sure it was allocated by us
1777		if (info->magic == kAreaAllocationMagic && info->area == area
1778			&& info->size == areaInfo.size && info->base == areaInfo.address
1779			&& info->allocation_size < areaInfo.size) {
1780			if (size)
1781				*size = info->allocation_size;
1782			if (thread)
1783				*thread = info->thread;
1784			return B_OK;
1785		}
1786	}
1787
1788	return B_ENTRY_NOT_FOUND;
1789}
1790
1791
1792//	#pragma mark - Init
1793
1794
1795static status_t
1796debug_heap_init(void)
1797{
1798	// This will locate the heap base at 384 MB and reserve the next 1152 MB
1799	// for it. They may get reclaimed by other areas, though, but the maximum
1800	// size of the heap is guaranteed until the space is really needed.
1801	void *heapBase = (void *)0x18000000;
1802	status_t status = _kern_reserve_address_range((addr_t *)&heapBase,
1803		B_EXACT_ADDRESS, 0x48000000);
1804
1805	area_id heapArea = create_area("heap", (void **)&heapBase,
1806		status == B_OK ? B_EXACT_ADDRESS : B_BASE_ADDRESS,
1807		HEAP_INITIAL_SIZE, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
1808	if (heapArea < B_OK)
1809		return heapArea;
1810
1811	addr_t base = (addr_t)heapBase;
1812	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++) {
1813		size_t partSize = HEAP_INITIAL_SIZE
1814			* sHeapClasses[i].initial_percentage / 100;
1815		sHeaps[i] = heap_create_allocator(sHeapClasses[i].name, base, partSize,
1816			&sHeapClasses[i]);
1817		base += partSize;
1818	}
1819
1820	return B_OK;
1821}
1822
1823
1824//	#pragma mark - Public API
1825
1826
1827static void *
1828debug_heap_memalign(size_t alignment, size_t size)
1829{
1830	size_t alignedSize = size + sizeof(addr_t) + sizeof(heap_leak_check_info);
1831	if (alignment != 0 && alignment < B_PAGE_SIZE)
1832		alignedSize = ROUNDUP(alignedSize, alignment);
1833
1834	if (alignedSize >= HEAP_AREA_USE_THRESHOLD) {
1835		// don't even attempt such a huge allocation - use areas instead
1836		size_t areaSize = ROUNDUP(size + sizeof(area_allocation_info)
1837			+ alignment, B_PAGE_SIZE);
1838		if (areaSize < size) {
1839			// the size overflowed
1840			return NULL;
1841		}
1842
1843		void *address = NULL;
1844		area_id allocationArea = create_area("memalign area", &address,
1845			B_ANY_ADDRESS, areaSize, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
1846		if (allocationArea < B_OK) {
1847			panic("heap: failed to create area for huge allocation of %lu"
1848				" bytes\n", size);
1849			return NULL;
1850		}
1851
1852		area_allocation_info *info = (area_allocation_info *)address;
1853		info->magic = kAreaAllocationMagic;
1854		info->area = allocationArea;
1855		info->base = address;
1856		info->size = areaSize;
1857		info->thread = find_thread(NULL);
1858		info->allocation_size = size;
1859		info->allocation_alignment = alignment;
1860
1861		address = (void *)((addr_t)address + sizeof(area_allocation_info));
1862		if (alignment != 0) {
1863			address = (void *)ROUNDUP((addr_t)address, alignment);
1864			ASSERT((addr_t)address % alignment == 0);
1865			ASSERT((addr_t)address + size - 1 < (addr_t)info + areaSize - 1);
1866		}
1867
1868		INFO(("heap: allocated area %ld for huge allocation of %lu bytes\n",
1869			allocationArea, size));
1870
1871		info->allocation_base = address;
1872
1873		memset(address, 0xcc, size);
1874		return address;
1875	}
1876
1877	uint32 heapClass = alignment < B_PAGE_SIZE
1878		? heap_class_for(alignedSize) : 0;
1879
1880	heap_allocator *heap = sHeaps[heapClass];
1881	void *result = heap_memalign(heap, alignment, size);
1882	if (result == NULL) {
1883		// add new area and try again
1884		heap_create_new_heap_area(heap, "additional heap area", HEAP_GROW_SIZE);
1885		result = heap_memalign(heap, alignment, size);
1886	}
1887
1888	if (sParanoidValidation)
1889		heap_validate_heap(heap);
1890
1891	if (result == NULL) {
1892		panic("heap: heap has run out of memory trying to allocate %lu bytes\n",
1893			size);
1894	}
1895
1896	if (alignment != 0)
1897		ASSERT((addr_t)result % alignment == 0);
1898
1899	return result;
1900}
1901
1902
1903static void *
1904debug_heap_malloc(size_t size)
1905{
1906	if (sUseGuardPage)
1907		return debug_heap_malloc_with_guard_page(size);
1908
1909	return debug_heap_memalign(sDefaultAlignment, size);
1910}
1911
1912
1913static void
1914debug_heap_free(void *address)
1915{
1916	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++) {
1917		heap_allocator *heap = sHeaps[i];
1918		if (heap_free(heap, address) == B_OK) {
1919			if (sParanoidValidation)
1920				heap_validate_heap(heap);
1921			return;
1922		}
1923	}
1924
1925	// or maybe it was a huge allocation using an area
1926	area_info areaInfo;
1927	area_id area = area_for(address);
1928	if (area >= B_OK && get_area_info(area, &areaInfo) == B_OK) {
1929		area_allocation_info *info = (area_allocation_info *)areaInfo.address;
1930
1931		// just make extra sure it was allocated by us
1932		if (info->magic == kAreaAllocationMagic && info->area == area
1933			&& info->size == areaInfo.size && info->base == areaInfo.address
1934			&& info->allocation_size < areaInfo.size) {
1935			delete_area(area);
1936			INFO(("free(): freed huge allocation by deleting area %ld\n",
1937				area));
1938			return;
1939		}
1940	}
1941
1942	panic("free(): free failed for address %p\n", address);
1943}
1944
1945
1946static void *
1947debug_heap_realloc(void *address, size_t newSize)
1948{
1949	if (address == NULL)
1950		return debug_heap_memalign(sDefaultAlignment, newSize);
1951
1952	if (newSize == 0) {
1953		free(address);
1954		return NULL;
1955	}
1956
1957	void *newAddress = NULL;
1958	for (uint32 i = 0; i < HEAP_CLASS_COUNT; i++) {
1959		heap_allocator *heap = sHeaps[i];
1960		if (heap_realloc(heap, address, &newAddress, newSize) == B_OK) {
1961			if (sParanoidValidation)
1962				heap_validate_heap(heap);
1963			return newAddress;
1964		}
1965	}
1966
1967	// or maybe it was a huge allocation using an area
1968	area_info areaInfo;
1969	area_id area = area_for(address);
1970	if (area >= B_OK && get_area_info(area, &areaInfo) == B_OK) {
1971		area_allocation_info *info = (area_allocation_info *)areaInfo.address;
1972
1973		// just make extra sure it was allocated by us
1974		if (info->magic == kAreaAllocationMagic && info->area == area
1975			&& info->size == areaInfo.size && info->base == areaInfo.address
1976			&& info->allocation_size < areaInfo.size) {
1977			if (sUseGuardPage) {
1978				size_t available = info->size - B_PAGE_SIZE
1979					- sizeof(area_allocation_info);
1980
1981				if (available >= newSize) {
1982					// there is enough room available for the newSize
1983					newAddress = (void*)((addr_t)info->allocation_base
1984						+ info->allocation_size - newSize);
1985					INFO(("realloc(): new size %ld fits in old area %ld with "
1986						"%ld available -> new address: %p\n", newSize, area,
1987						available, newAddress));
1988					memmove(newAddress, info->allocation_base,
1989						min_c(newSize, info->allocation_size));
1990					info->allocation_base = newAddress;
1991					info->allocation_size = newSize;
1992					return newAddress;
1993				}
1994			} else {
1995				size_t available = info->size - ((addr_t)info->allocation_base
1996					- (addr_t)info->base);
1997
1998				if (available >= newSize) {
1999					// there is enough room available for the newSize
2000					INFO(("realloc(): new size %ld fits in old area %ld with "
2001						"%ld available\n", newSize, area, available));
2002					info->allocation_size = newSize;
2003					return address;
2004				}
2005			}
2006
2007			// have to allocate/copy/free - TODO maybe resize the area instead?
2008			newAddress = debug_heap_memalign(sDefaultAlignment, newSize);
2009			if (newAddress == NULL) {
2010				panic("realloc(): failed to allocate new block of %ld"
2011					" bytes\n", newSize);
2012				return NULL;
2013			}
2014
2015			memcpy(newAddress, address, min_c(newSize, info->allocation_size));
2016			delete_area(area);
2017			INFO(("realloc(): allocated new block %p for size %ld and deleted "
2018				"old area %ld\n", newAddress, newSize, area));
2019			return newAddress;
2020		}
2021	}
2022
2023	panic("realloc(): failed to realloc address %p to size %lu\n", address,
2024		newSize);
2025	return NULL;
2026}
2027
2028
2029heap_implementation __mallocDebugHeap = {
2030	debug_heap_init,
2031	NULL,	// terminate_after
2032
2033	debug_heap_memalign,
2034	debug_heap_malloc,
2035	debug_heap_free,
2036	debug_heap_realloc,
2037
2038	NULL,	// calloc
2039	NULL,	// valloc
2040	NULL,	// posix_memalign
2041
2042	debug_heap_start_wall_checking,
2043	debug_heap_stop_wall_checking,
2044	debug_heap_set_paranoid_validation,
2045	debug_heap_set_memory_reuse,
2046	debug_heap_set_debugger_calls,
2047	debug_heap_set_default_alignment,
2048	debug_heap_validate_heaps,
2049	heap_validate_walls,
2050	dump_allocations,
2051	debug_heap_dump_heaps,
2052	debug_heap_malloc_with_guard_page,
2053	debug_heap_get_allocation_info,
2054
2055	NULL,	// set_dump_allocations_on_exit
2056	NULL	// set_stack_trace_depth
2057};
2058