1/*
2 * Copyright 2011, Michael Lotz <mmlr@mlotz.ch>.
3 * Distributed under the terms of the MIT License.
4 */
5
6#include "malloc_debug_api.h"
7
8
9#include <malloc.h>
10#include <stdio.h>
11#include <stdlib.h>
12#include <string.h>
13
14#include <signal.h>
15#include <sys/mman.h>
16
17#include <locks.h>
18
19#include <libroot_private.h>
20#include <runtime_loader.h>
21
22#include <TLS.h>
23
24
25// #pragma mark - Debug Helpers
26
27static const size_t kMaxStackTraceDepth = 50;
28
29
30static bool sDebuggerCalls = true;
31static bool sDumpAllocationsOnExit = false;
32static size_t sStackTraceDepth = 0;
33static int32 sStackBaseTLSIndex = -1;
34static int32 sStackEndTLSIndex = -1;
35
36#if __cplusplus >= 201103L
37#include <cstddef>
38using namespace std;
39static size_t sDefaultAlignment = alignof(max_align_t);
40#else
41static size_t sDefaultAlignment = 8;
42#endif
43
44
45static void
46panic(const char* format, ...)
47{
48	char buffer[1024];
49
50	va_list args;
51	va_start(args, format);
52	vsnprintf(buffer, sizeof(buffer), format, args);
53	va_end(args);
54
55	if (sDebuggerCalls)
56		debugger(buffer);
57	else
58		debug_printf(buffer);
59}
60
61
62static void
63print_stdout(const char* format, ...)
64{
65	// To avoid any allocations due to dynamic memory need by printf() we use a
66	// stack buffer and vsnprintf(). Otherwise this does the same as printf().
67	char buffer[1024];
68
69	va_list args;
70	va_start(args, format);
71	vsnprintf(buffer, sizeof(buffer), format, args);
72	va_end(args);
73
74	write(STDOUT_FILENO, buffer, strlen(buffer));
75}
76
77
78// #pragma mark - Linked List
79
80
81#define GET_ITEM(list, item) ((void *)((uint8 *)item - list->offset))
82#define GET_LINK(list, item) ((list_link *)((uint8 *)item + list->offset))
83
84
85struct list_link {
86	list_link*	next;
87	list_link*	prev;
88};
89
90struct list {
91	list_link	link;
92	int32		offset;
93};
94
95
96static inline void
97list_remove_item(struct list* list, void* item)
98{
99	list_link* link = GET_LINK(list, item);
100
101	link->next->prev = link->prev;
102	link->prev->next = link->next;
103}
104
105
106static inline void
107list_add_item(struct list* list, void* item)
108{
109	list_link* link = GET_LINK(list, item);
110
111	link->next = &list->link;
112	link->prev = list->link.prev;
113
114	list->link.prev->next = link;
115	list->link.prev = link;
116}
117
118
119static inline void*
120list_get_next_item(struct list* list, void* item)
121{
122	if (item == NULL) {
123		if (list->link.next == (list_link *)list)
124			return NULL;
125
126		return GET_ITEM(list, list->link.next);
127	}
128
129	list_link* link = GET_LINK(list, item);
130	if (link->next == &list->link)
131		return NULL;
132
133	return GET_ITEM(list, link->next);
134}
135
136
137static inline void
138list_init_etc(struct list* list, int32 offset)
139{
140	list->link.next = list->link.prev = &list->link;
141	list->offset = offset;
142}
143
144
145// #pragma mark - Guarded Heap
146
147
148#define GUARDED_HEAP_PAGE_FLAG_USED			0x01
149#define GUARDED_HEAP_PAGE_FLAG_FIRST		0x02
150#define GUARDED_HEAP_PAGE_FLAG_GUARD		0x04
151#define GUARDED_HEAP_PAGE_FLAG_DEAD			0x08
152#define GUARDED_HEAP_PAGE_FLAG_AREA			0x10
153
154#define GUARDED_HEAP_INITIAL_SIZE			1 * 1024 * 1024
155#define GUARDED_HEAP_GROW_SIZE				2 * 1024 * 1024
156#define GUARDED_HEAP_AREA_USE_THRESHOLD		1 * 1024 * 1024
157
158
159struct guarded_heap;
160
161struct guarded_heap_page {
162	uint8				flags;
163	size_t				allocation_size;
164	void*				allocation_base;
165	size_t				alignment;
166	thread_id			allocating_thread;
167	thread_id			freeing_thread;
168	list_link			free_list_link;
169	size_t				alloc_stack_trace_depth;
170	size_t				free_stack_trace_depth;
171	addr_t				stack_trace[kMaxStackTraceDepth];
172};
173
174struct guarded_heap_area {
175	guarded_heap*		heap;
176	guarded_heap_area*	next;
177	area_id				area;
178	addr_t				base;
179	size_t				size;
180	size_t				page_count;
181	size_t				used_pages;
182	mutex				lock;
183	struct list			free_list;
184	guarded_heap_page	pages[0];
185};
186
187struct guarded_heap {
188	rw_lock				lock;
189	size_t				page_count;
190	size_t				used_pages;
191	uint32				area_creation_counter;
192	bool				reuse_memory;
193	guarded_heap_area*	areas;
194};
195
196
197static guarded_heap sGuardedHeap = {
198	RW_LOCK_INITIALIZER("guarded heap lock"),
199	0, 0, 0, true, NULL
200};
201
202
203static void dump_guarded_heap_page(void* address, bool doPanic = false);
204
205
206static void
207guarded_heap_segfault_handler(int signal, siginfo_t* signalInfo, void* vregs)
208{
209	if (signal != SIGSEGV)
210		return;
211
212	if (signalInfo->si_code != SEGV_ACCERR) {
213		// Not ours.
214		panic("generic segfault");
215		return;
216	}
217
218	dump_guarded_heap_page(signalInfo->si_addr, true);
219
220	exit(-1);
221}
222
223
224static void
225guarded_heap_page_protect(guarded_heap_area& area, size_t pageIndex,
226	uint32 protection)
227{
228	addr_t address = area.base + pageIndex * B_PAGE_SIZE;
229	mprotect((void*)address, B_PAGE_SIZE, protection);
230}
231
232
233static void
234guarded_heap_print_stack_trace(addr_t stackTrace[], size_t depth)
235{
236	char* imageName;
237	char* symbolName;
238	void* location;
239	bool exactMatch;
240
241	for (size_t i = 0; i < depth; i++) {
242		addr_t address = stackTrace[i];
243
244		status_t status = __gRuntimeLoader->get_nearest_symbol_at_address(
245			(void*)address, NULL, NULL, &imageName, &symbolName, NULL,
246			&location, &exactMatch);
247		if (status != B_OK) {
248			print_stdout("\t%#" B_PRIxADDR " (lookup failed: %s)\n", address,
249				strerror(status));
250			continue;
251		}
252
253		print_stdout("\t<%s> %s + %#" B_PRIxADDR "%s\n", imageName, symbolName,
254			address - (addr_t)location, exactMatch ? "" : " (nearest)");
255	}
256}
257
258
259static void
260guarded_heap_print_stack_traces(guarded_heap_page& page)
261{
262	if (page.alloc_stack_trace_depth > 0) {
263		print_stdout("alloc stack trace (%" B_PRIuSIZE "):\n",
264			page.alloc_stack_trace_depth);
265		guarded_heap_print_stack_trace(page.stack_trace,
266			page.alloc_stack_trace_depth);
267	}
268
269	if (page.free_stack_trace_depth > 0) {
270		print_stdout("free stack trace (%" B_PRIuSIZE "):\n",
271			page.free_stack_trace_depth);
272		guarded_heap_print_stack_trace(
273			&page.stack_trace[page.alloc_stack_trace_depth],
274			page.free_stack_trace_depth);
275	}
276}
277
278
279static size_t
280guarded_heap_fill_stack_trace(addr_t stackTrace[], size_t maxDepth,
281	size_t skipFrames)
282{
283	if (maxDepth == 0)
284		return 0;
285
286	void** stackBase = tls_address(sStackBaseTLSIndex);
287	void** stackEnd = tls_address(sStackEndTLSIndex);
288	if (*stackBase == NULL || *stackEnd == NULL) {
289		thread_info threadInfo;
290		status_t result = get_thread_info(find_thread(NULL), &threadInfo);
291		if (result != B_OK)
292			return 0;
293
294		*stackBase = (void*)threadInfo.stack_base;
295		*stackEnd = (void*)threadInfo.stack_end;
296	}
297
298	int32 traceDepth = __arch_get_stack_trace(stackTrace, maxDepth, skipFrames,
299		(addr_t)*stackBase, (addr_t)*stackEnd);
300
301	return traceDepth < 0 ? 0 : traceDepth;
302}
303
304
305static void
306guarded_heap_page_allocate(guarded_heap_area& area, size_t startPageIndex,
307	size_t pagesNeeded, size_t allocationSize, size_t alignment,
308	void* allocationBase)
309{
310	if (pagesNeeded < 2) {
311		panic("need to allocate at least 2 pages, one for guard\n");
312		return;
313	}
314
315	guarded_heap_page* firstPage = NULL;
316	for (size_t i = 0; i < pagesNeeded; i++) {
317		guarded_heap_page& page = area.pages[startPageIndex + i];
318		page.flags = GUARDED_HEAP_PAGE_FLAG_USED;
319		if (i == 0) {
320			page.allocating_thread = find_thread(NULL);
321			page.freeing_thread = -1;
322			page.allocation_size = allocationSize;
323			page.allocation_base = allocationBase;
324			page.alignment = alignment;
325			page.flags |= GUARDED_HEAP_PAGE_FLAG_FIRST;
326			page.alloc_stack_trace_depth = guarded_heap_fill_stack_trace(
327				page.stack_trace, sStackTraceDepth, 2);
328			page.free_stack_trace_depth = 0;
329			firstPage = &page;
330		} else {
331			page.allocating_thread = firstPage->allocating_thread;
332			page.freeing_thread = -1;
333			page.allocation_size = allocationSize;
334			page.allocation_base = allocationBase;
335			page.alignment = alignment;
336			page.alloc_stack_trace_depth = 0;
337			page.free_stack_trace_depth = 0;
338		}
339
340		list_remove_item(&area.free_list, &page);
341
342		if (i == pagesNeeded - 1) {
343			page.flags |= GUARDED_HEAP_PAGE_FLAG_GUARD;
344			guarded_heap_page_protect(area, startPageIndex + i, 0);
345		} else {
346			guarded_heap_page_protect(area, startPageIndex + i,
347				B_READ_AREA | B_WRITE_AREA);
348		}
349	}
350}
351
352
353static void
354guarded_heap_free_page(guarded_heap_area& area, size_t pageIndex,
355	bool force = false)
356{
357	guarded_heap_page& page = area.pages[pageIndex];
358
359	if (area.heap->reuse_memory || force)
360		page.flags = 0;
361	else
362		page.flags |= GUARDED_HEAP_PAGE_FLAG_DEAD;
363
364	page.freeing_thread = find_thread(NULL);
365
366	list_add_item(&area.free_list, &page);
367
368	guarded_heap_page_protect(area, pageIndex, 0);
369}
370
371
372static void
373guarded_heap_pages_allocated(guarded_heap& heap, size_t pagesAllocated)
374{
375	atomic_add((int32*)&heap.used_pages, pagesAllocated);
376}
377
378
379static void*
380guarded_heap_area_allocate(guarded_heap_area& area, size_t pagesNeeded,
381	size_t size, size_t alignment)
382{
383	if (pagesNeeded > area.page_count - area.used_pages)
384		return NULL;
385
386	// We use the free list this way so that the page that has been free for
387	// the longest time is allocated. This keeps immediate re-use (that may
388	// hide bugs) to a minimum.
389	guarded_heap_page* page
390		= (guarded_heap_page*)list_get_next_item(&area.free_list, NULL);
391
392	for (; page != NULL;
393		page = (guarded_heap_page*)list_get_next_item(&area.free_list, page)) {
394
395		if ((page->flags & GUARDED_HEAP_PAGE_FLAG_USED) != 0)
396			continue;
397
398		size_t pageIndex = page - area.pages;
399		if (pageIndex > area.page_count - pagesNeeded)
400			continue;
401
402		// Candidate, check if we have enough pages going forward
403		// (including the guard page).
404		bool candidate = true;
405		for (size_t j = 1; j < pagesNeeded; j++) {
406			if ((area.pages[pageIndex + j].flags & GUARDED_HEAP_PAGE_FLAG_USED)
407					!= 0) {
408				candidate = false;
409				break;
410			}
411		}
412
413		if (!candidate)
414			continue;
415
416		size_t offset = size & (B_PAGE_SIZE - 1);
417		void* result = (void*)((area.base + pageIndex * B_PAGE_SIZE
418			+ (offset > 0 ? B_PAGE_SIZE - offset : 0)) & ~(alignment - 1));
419
420		guarded_heap_page_allocate(area, pageIndex, pagesNeeded, size,
421			alignment, result);
422
423		area.used_pages += pagesNeeded;
424		guarded_heap_pages_allocated(*area.heap, pagesNeeded);
425		return result;
426	}
427
428	return NULL;
429}
430
431
432static bool
433guarded_heap_area_init(guarded_heap& heap, area_id id, void* baseAddress,
434	size_t size)
435{
436	guarded_heap_area* area = (guarded_heap_area*)baseAddress;
437	area->heap = &heap;
438	area->area = id;
439	area->size = size;
440	area->page_count = area->size / B_PAGE_SIZE;
441	area->used_pages = 0;
442
443	size_t pagesNeeded = (sizeof(guarded_heap_area)
444		+ area->page_count * sizeof(guarded_heap_page)
445		+ B_PAGE_SIZE - 1) / B_PAGE_SIZE;
446
447	area->page_count -= pagesNeeded;
448	area->size = area->page_count * B_PAGE_SIZE;
449	area->base = (addr_t)baseAddress + pagesNeeded * B_PAGE_SIZE;
450
451	mutex_init(&area->lock, "guarded_heap_area_lock");
452
453	list_init_etc(&area->free_list,
454		offsetof(guarded_heap_page, free_list_link));
455
456	for (size_t i = 0; i < area->page_count; i++)
457		guarded_heap_free_page(*area, i, true);
458
459	area->next = heap.areas;
460	heap.areas = area;
461	heap.page_count += area->page_count;
462
463	return true;
464}
465
466
467static bool
468guarded_heap_area_create(guarded_heap& heap, size_t size)
469{
470	for (size_t trySize = size; trySize >= 1 * 1024 * 1024;
471		trySize /= 2) {
472
473		void* baseAddress = NULL;
474		area_id id = create_area("guarded_heap_area", &baseAddress,
475			B_ANY_ADDRESS, trySize, B_NO_LOCK, B_READ_AREA | B_WRITE_AREA);
476
477		if (id < 0)
478			continue;
479
480		if (guarded_heap_area_init(heap, id, baseAddress, trySize))
481			return true;
482
483		delete_area(id);
484	}
485
486	panic("failed to allocate a new heap area");
487	return false;
488}
489
490
491static bool
492guarded_heap_add_area(guarded_heap& heap, uint32 counter)
493{
494	WriteLocker areaListWriteLocker(heap.lock);
495	if (heap.area_creation_counter != counter)
496		return false;
497
498	return guarded_heap_area_create(heap, GUARDED_HEAP_GROW_SIZE);
499}
500
501
502static void*
503guarded_heap_allocate_with_area(size_t size, size_t alignment)
504{
505	size_t infoSpace = alignment >= B_PAGE_SIZE ? B_PAGE_SIZE
506		: (sizeof(guarded_heap_page) + alignment - 1) & ~(alignment - 1);
507
508	size_t pagesNeeded = (size + infoSpace + B_PAGE_SIZE - 1) / B_PAGE_SIZE;
509
510	if (alignment > B_PAGE_SIZE)
511		pagesNeeded += alignment / B_PAGE_SIZE - 1;
512
513	void* address = NULL;
514	area_id area = create_area("guarded_heap_huge_allocation", &address,
515		B_ANY_ADDRESS, (pagesNeeded + 1) * B_PAGE_SIZE, B_NO_LOCK,
516		B_READ_AREA | B_WRITE_AREA);
517	if (area < 0) {
518		panic("failed to create area for allocation of %" B_PRIuSIZE " pages",
519			pagesNeeded);
520		return NULL;
521	}
522
523	// We just use a page object
524	guarded_heap_page* page = (guarded_heap_page*)address;
525	page->flags = GUARDED_HEAP_PAGE_FLAG_USED | GUARDED_HEAP_PAGE_FLAG_FIRST
526		| GUARDED_HEAP_PAGE_FLAG_AREA;
527	page->allocation_size = size;
528	page->allocation_base = (void*)(((addr_t)address
529		+ pagesNeeded * B_PAGE_SIZE - size) & ~(alignment - 1));
530	page->alignment = alignment;
531	page->allocating_thread = find_thread(NULL);
532	page->freeing_thread = -1;
533	page->alloc_stack_trace_depth = guarded_heap_fill_stack_trace(
534		page->stack_trace, sStackTraceDepth, 2);
535	page->free_stack_trace_depth = 0;
536
537	if (alignment <= B_PAGE_SIZE) {
538		// Protect just the guard page.
539		mprotect((void*)((addr_t)address + pagesNeeded * B_PAGE_SIZE),
540			B_PAGE_SIZE, 0);
541	} else {
542		// Protect empty pages before the allocation start...
543		addr_t protectedStart = (addr_t)address + B_PAGE_SIZE;
544		size_t protectedSize = (addr_t)page->allocation_base - protectedStart;
545		if (protectedSize > 0)
546			mprotect((void*)protectedStart, protectedSize, 0);
547
548		// ... and after allocation end.
549		size_t allocatedPages = (size + B_PAGE_SIZE - 1) / B_PAGE_SIZE;
550		protectedStart = (addr_t)page->allocation_base
551			+ allocatedPages * B_PAGE_SIZE;
552		protectedSize = (addr_t)address + (pagesNeeded + 1) * B_PAGE_SIZE
553			- protectedStart;
554
555		// There is at least the guard page.
556		mprotect((void*)protectedStart, protectedSize, 0);
557	}
558
559	return page->allocation_base;
560}
561
562
563static void*
564guarded_heap_allocate(guarded_heap& heap, size_t size, size_t alignment)
565{
566	if (alignment == 0)
567		alignment = 1;
568
569	size_t pagesNeeded = (size + B_PAGE_SIZE - 1) / B_PAGE_SIZE + 1;
570	if (alignment > B_PAGE_SIZE
571		|| pagesNeeded * B_PAGE_SIZE >= GUARDED_HEAP_AREA_USE_THRESHOLD) {
572		// Don't bother, use an area directly. Since it will also fault once
573		// it is deleted, that fits our model quite nicely.
574		return guarded_heap_allocate_with_area(size, alignment);
575	}
576
577	void* result = NULL;
578
579	ReadLocker areaListReadLocker(heap.lock);
580	for (guarded_heap_area* area = heap.areas; area != NULL;
581			area = area->next) {
582
583		MutexLocker locker(area->lock);
584		result = guarded_heap_area_allocate(*area, pagesNeeded, size,
585			alignment);
586		if (result != NULL)
587			break;
588	}
589
590	uint32 counter = heap.area_creation_counter;
591	areaListReadLocker.Unlock();
592
593	if (result == NULL) {
594		guarded_heap_add_area(heap, counter);
595		return guarded_heap_allocate(heap, size, alignment);
596	}
597
598	if (result == NULL)
599		panic("ran out of memory");
600
601	return result;
602}
603
604
605static guarded_heap_area*
606guarded_heap_get_locked_area_for(guarded_heap& heap, void* address)
607{
608	ReadLocker areaListReadLocker(heap.lock);
609	for (guarded_heap_area* area = heap.areas; area != NULL;
610			area = area->next) {
611		if ((addr_t)address < area->base)
612			continue;
613
614		if ((addr_t)address >= area->base + area->size)
615			continue;
616
617		mutex_lock(&area->lock);
618		return area;
619	}
620
621	return NULL;
622}
623
624
625static size_t
626guarded_heap_area_page_index_for(guarded_heap_area& area, void* address)
627{
628	size_t pageIndex = ((addr_t)address - area.base) / B_PAGE_SIZE;
629	guarded_heap_page& page = area.pages[pageIndex];
630	if ((page.flags & GUARDED_HEAP_PAGE_FLAG_USED) == 0) {
631		panic("tried to free %p which points at page %" B_PRIuSIZE
632			" which is not marked in use", address, pageIndex);
633		return area.page_count;
634	}
635
636	if ((page.flags & GUARDED_HEAP_PAGE_FLAG_GUARD) != 0) {
637		panic("tried to free %p which points at page %" B_PRIuSIZE
638			" which is a guard page", address, pageIndex);
639		return area.page_count;
640	}
641
642	if ((page.flags & GUARDED_HEAP_PAGE_FLAG_FIRST) == 0) {
643		panic("tried to free %p which points at page %" B_PRIuSIZE
644			" which is not an allocation first page", address, pageIndex);
645		return area.page_count;
646	}
647
648	if ((page.flags & GUARDED_HEAP_PAGE_FLAG_DEAD) != 0) {
649		panic("tried to free %p which points at page %" B_PRIuSIZE
650			" which is a dead page", address, pageIndex);
651		return area.page_count;
652	}
653
654	return pageIndex;
655}
656
657
658static bool
659guarded_heap_area_free(guarded_heap_area& area, void* address)
660{
661	size_t pageIndex = guarded_heap_area_page_index_for(area, address);
662	if (pageIndex >= area.page_count)
663		return false;
664
665	size_t pagesFreed = 0;
666	guarded_heap_page* page = &area.pages[pageIndex];
667	while ((page->flags & GUARDED_HEAP_PAGE_FLAG_GUARD) == 0) {
668		// Mark the allocation page as free.
669		guarded_heap_free_page(area, pageIndex);
670		if (pagesFreed == 0 && sStackTraceDepth > 0) {
671			size_t freeEntries
672				= kMaxStackTraceDepth - page->alloc_stack_trace_depth;
673
674			page->free_stack_trace_depth = guarded_heap_fill_stack_trace(
675				&page->stack_trace[page->alloc_stack_trace_depth],
676				min_c(freeEntries, sStackTraceDepth), 2);
677		}
678
679		pagesFreed++;
680		pageIndex++;
681		page = &area.pages[pageIndex];
682	}
683
684	// Mark the guard page as free as well.
685	guarded_heap_free_page(area, pageIndex);
686	pagesFreed++;
687
688	if (area.heap->reuse_memory) {
689		area.used_pages -= pagesFreed;
690		atomic_add((int32*)&area.heap->used_pages, -pagesFreed);
691	}
692
693	return true;
694}
695
696
697static guarded_heap_page*
698guarded_heap_area_allocation_for(void* address, area_id& allocationArea)
699{
700	allocationArea = area_for(address);
701	if (allocationArea < 0)
702		return NULL;
703
704	area_info areaInfo;
705	if (get_area_info(allocationArea, &areaInfo) != B_OK)
706		return NULL;
707
708	guarded_heap_page* page = (guarded_heap_page*)areaInfo.address;
709	if (page->flags != (GUARDED_HEAP_PAGE_FLAG_USED
710			| GUARDED_HEAP_PAGE_FLAG_FIRST | GUARDED_HEAP_PAGE_FLAG_AREA)) {
711		return NULL;
712	}
713
714	if (page->allocation_base != address)
715		return NULL;
716	if (page->allocation_size >= areaInfo.size)
717		return NULL;
718
719	return page;
720}
721
722
723static bool
724guarded_heap_free_area_allocation(void* address)
725{
726	area_id allocationArea;
727	if (guarded_heap_area_allocation_for(address, allocationArea) == NULL)
728		return false;
729
730	delete_area(allocationArea);
731	return true;
732}
733
734
735static bool
736guarded_heap_free(void* address)
737{
738	if (address == NULL)
739		return true;
740
741	guarded_heap_area* area = guarded_heap_get_locked_area_for(sGuardedHeap,
742		address);
743	if (area == NULL)
744		return guarded_heap_free_area_allocation(address);
745
746	MutexLocker locker(area->lock, true);
747	return guarded_heap_area_free(*area, address);
748}
749
750
751static void*
752guarded_heap_realloc(void* address, size_t newSize)
753{
754	guarded_heap_area* area = guarded_heap_get_locked_area_for(sGuardedHeap,
755		address);
756
757	size_t oldSize;
758	area_id allocationArea = -1;
759	if (area != NULL) {
760		MutexLocker locker(area->lock, true);
761		size_t pageIndex = guarded_heap_area_page_index_for(*area, address);
762		if (pageIndex >= area->page_count)
763			return NULL;
764
765		guarded_heap_page& page = area->pages[pageIndex];
766		oldSize = page.allocation_size;
767		locker.Unlock();
768	} else {
769		guarded_heap_page* page = guarded_heap_area_allocation_for(address,
770			allocationArea);
771		if (page == NULL)
772			return NULL;
773
774		oldSize = page->allocation_size;
775	}
776
777	if (oldSize == newSize)
778		return address;
779
780	void* newBlock = guarded_heap_allocate(sGuardedHeap, newSize,
781		sDefaultAlignment);
782	if (newBlock == NULL)
783		return NULL;
784
785	memcpy(newBlock, address, min_c(oldSize, newSize));
786
787	if (allocationArea >= 0)
788		delete_area(allocationArea);
789	else {
790		MutexLocker locker(area->lock);
791		guarded_heap_area_free(*area, address);
792	}
793
794	return newBlock;
795}
796
797
798// #pragma mark - Debugger commands
799
800
801static void
802dump_guarded_heap_page(guarded_heap_page& page)
803{
804	printf("flags:");
805	if ((page.flags & GUARDED_HEAP_PAGE_FLAG_USED) != 0)
806		printf(" used");
807	if ((page.flags & GUARDED_HEAP_PAGE_FLAG_FIRST) != 0)
808		printf(" first");
809	if ((page.flags & GUARDED_HEAP_PAGE_FLAG_GUARD) != 0)
810		printf(" guard");
811	if ((page.flags & GUARDED_HEAP_PAGE_FLAG_DEAD) != 0)
812		printf(" dead");
813	printf("\n");
814
815	printf("allocation size: %" B_PRIuSIZE "\n", page.allocation_size);
816	printf("allocation base: %p\n", page.allocation_base);
817	printf("alignment: %" B_PRIuSIZE "\n", page.alignment);
818	printf("allocating thread: %" B_PRId32 "\n", page.allocating_thread);
819	printf("freeing thread: %" B_PRId32 "\n", page.freeing_thread);
820}
821
822
823static void
824dump_guarded_heap_page(void* address, bool doPanic)
825{
826	// Find the area that contains this page.
827	guarded_heap_area* area = NULL;
828	for (guarded_heap_area* candidate = sGuardedHeap.areas; candidate != NULL;
829			candidate = candidate->next) {
830
831		if ((addr_t)address < candidate->base)
832			continue;
833		if ((addr_t)address >= candidate->base + candidate->size)
834			continue;
835
836		area = candidate;
837		break;
838	}
839
840	if (area == NULL) {
841		panic("didn't find area for address %p\n", address);
842		return;
843	}
844
845	size_t pageIndex = ((addr_t)address - area->base) / B_PAGE_SIZE;
846	guarded_heap_page& page = area->pages[pageIndex];
847	dump_guarded_heap_page(page);
848
849	// Find the first page and dump the stack traces.
850	for (ssize_t candidateIndex = (ssize_t)pageIndex;
851			sStackTraceDepth > 0 && candidateIndex >= 0; candidateIndex--) {
852		guarded_heap_page& candidate = area->pages[candidateIndex];
853		if ((candidate.flags & GUARDED_HEAP_PAGE_FLAG_FIRST) == 0)
854			continue;
855
856		guarded_heap_print_stack_traces(candidate);
857		break;
858	}
859
860	if (doPanic) {
861		// Note: we do this the complicated way because we absolutely don't
862		// want any character conversion to happen that might provoke other
863		// segfaults in the locale backend. Therefore we avoid using any string
864		// formats, resulting in the mess below.
865
866		#define DO_PANIC(state) \
867			panic("thread %" B_PRId32 " tried accessing address %p which is " \
868				state " (base: 0x%" B_PRIxADDR ", size: %" B_PRIuSIZE \
869				", alignment: %" B_PRIuSIZE ", allocated by thread: %" \
870				B_PRId32 ", freed by thread: %" B_PRId32 ")", \
871				find_thread(NULL), address, page.allocation_base, \
872				page.allocation_size, page.alignment, page.allocating_thread, \
873				page.freeing_thread)
874
875		if ((page.flags & GUARDED_HEAP_PAGE_FLAG_USED) == 0)
876			DO_PANIC("not allocated");
877		else if ((page.flags & GUARDED_HEAP_PAGE_FLAG_GUARD) != 0)
878			DO_PANIC("a guard page");
879		else if ((page.flags & GUARDED_HEAP_PAGE_FLAG_DEAD) != 0)
880			DO_PANIC("a dead page");
881		else
882			DO_PANIC("in an unknown state");
883
884		#undef DO_PANIC
885	}
886}
887
888
889static void
890dump_guarded_heap_area(guarded_heap_area& area)
891{
892	printf("guarded heap area: %p\n", &area);
893	printf("next heap area: %p\n", area.next);
894	printf("guarded heap: %p\n", area.heap);
895	printf("area id: %" B_PRId32 "\n", area.area);
896	printf("base: 0x%" B_PRIxADDR "\n", area.base);
897	printf("size: %" B_PRIuSIZE "\n", area.size);
898	printf("page count: %" B_PRIuSIZE "\n", area.page_count);
899	printf("used pages: %" B_PRIuSIZE "\n", area.used_pages);
900	printf("lock: %p\n", &area.lock);
901
902	size_t freeCount = 0;
903	void* item = list_get_next_item(&area.free_list, NULL);
904	while (item != NULL) {
905		freeCount++;
906
907		if ((((guarded_heap_page*)item)->flags & GUARDED_HEAP_PAGE_FLAG_USED)
908				!= 0) {
909			printf("free list broken, page %p not actually free\n", item);
910		}
911
912		item = list_get_next_item(&area.free_list, item);
913	}
914
915	printf("free_list: %p (%" B_PRIuSIZE " free)\n", &area.free_list,
916		freeCount);
917
918	freeCount = 0;
919	size_t runLength = 0;
920	size_t longestRun = 0;
921	for (size_t i = 0; i <= area.page_count; i++) {
922		guarded_heap_page& page = area.pages[i];
923		if (i == area.page_count
924			|| (page.flags & GUARDED_HEAP_PAGE_FLAG_USED) != 0) {
925			freeCount += runLength;
926			if (runLength > longestRun)
927				longestRun = runLength;
928			runLength = 0;
929			continue;
930		}
931
932		runLength = 1;
933		for (size_t j = 1; j < area.page_count - i; j++) {
934			if ((area.pages[i + j].flags & GUARDED_HEAP_PAGE_FLAG_USED) != 0)
935				break;
936
937			runLength++;
938		}
939
940		i += runLength - 1;
941	}
942
943	printf("longest free run: %" B_PRIuSIZE " (%" B_PRIuSIZE " free)\n",
944		longestRun, freeCount);
945
946	printf("pages: %p\n", area.pages);
947}
948
949
950static void
951dump_guarded_heap(guarded_heap& heap)
952{
953	printf("guarded heap: %p\n", &heap);
954	printf("rw lock: %p\n", &heap.lock);
955	printf("page count: %" B_PRIuSIZE "\n", heap.page_count);
956	printf("used pages: %" B_PRIuSIZE "\n", heap.used_pages);
957	printf("area creation counter: %" B_PRIu32 "\n",
958		heap.area_creation_counter);
959
960	size_t areaCount = 0;
961	guarded_heap_area* area = heap.areas;
962	while (area != NULL) {
963		areaCount++;
964		area = area->next;
965	}
966
967	printf("areas: %p (%" B_PRIuSIZE ")\n", heap.areas, areaCount);
968}
969
970
971static void
972dump_allocations(guarded_heap& heap, bool statsOnly, thread_id thread)
973{
974	WriteLocker heapLocker(heap.lock);
975
976	size_t allocationCount = 0;
977	size_t allocationSize = 0;
978	for (guarded_heap_area* area = heap.areas; area != NULL;
979			area = area->next) {
980
981		MutexLocker areaLocker(area->lock);
982		for (size_t i = 0; i < area->page_count; i++) {
983			guarded_heap_page& page = area->pages[i];
984			if ((page.flags & GUARDED_HEAP_PAGE_FLAG_FIRST) == 0
985				|| (page.flags & GUARDED_HEAP_PAGE_FLAG_DEAD) != 0) {
986				continue;
987			}
988
989			if (thread >= 0 && thread != page.allocating_thread)
990				continue;
991
992			allocationCount++;
993			allocationSize += page.allocation_size;
994
995			if (statsOnly)
996				continue;
997
998			print_stdout("allocation: base: %p; size: %" B_PRIuSIZE
999				"; thread: %" B_PRId32 "; alignment: %" B_PRIuSIZE "\n",
1000				page.allocation_base, page.allocation_size,
1001				page.allocating_thread, page.alignment);
1002
1003			guarded_heap_print_stack_trace(page.stack_trace,
1004				page.alloc_stack_trace_depth);
1005		}
1006	}
1007
1008	print_stdout("total allocations: %" B_PRIuSIZE ", %" B_PRIuSIZE " bytes\n",
1009		allocationCount, allocationSize);
1010}
1011
1012
1013static void
1014dump_allocations_full()
1015{
1016	dump_allocations(sGuardedHeap, false, -1);
1017}
1018
1019
1020// #pragma mark - Heap Debug API
1021
1022
1023static void
1024guarded_heap_set_memory_reuse(bool enabled)
1025{
1026	sGuardedHeap.reuse_memory = enabled;
1027}
1028
1029
1030static void
1031guarded_heap_set_debugger_calls(bool enabled)
1032{
1033	sDebuggerCalls = enabled;
1034}
1035
1036
1037static void
1038guarded_heap_set_default_alignment(size_t defaultAlignment)
1039{
1040	sDefaultAlignment = defaultAlignment;
1041}
1042
1043
1044static void
1045guarded_heap_dump_allocations(bool statsOnly, thread_id thread)
1046{
1047	dump_allocations(sGuardedHeap, statsOnly, thread);
1048}
1049
1050
1051static void
1052guarded_heap_dump_heaps(bool dumpAreas, bool dumpBins)
1053{
1054	WriteLocker heapLocker(sGuardedHeap.lock);
1055	dump_guarded_heap(sGuardedHeap);
1056	if (!dumpAreas)
1057		return;
1058
1059	for (guarded_heap_area* area = sGuardedHeap.areas; area != NULL;
1060			area = area->next) {
1061		MutexLocker areaLocker(area->lock);
1062		dump_guarded_heap_area(*area);
1063
1064		if (!dumpBins)
1065			continue;
1066
1067		for (size_t i = 0; i < area->page_count; i++) {
1068			dump_guarded_heap_page(area->pages[i]);
1069			if ((area->pages[i].flags & GUARDED_HEAP_PAGE_FLAG_FIRST) != 0)
1070				guarded_heap_print_stack_traces(area->pages[i]);
1071		}
1072	}
1073}
1074
1075
1076static status_t
1077guarded_heap_set_dump_allocations_on_exit(bool enabled)
1078{
1079	sDumpAllocationsOnExit = enabled;
1080	return B_OK;
1081}
1082
1083
1084static status_t
1085guarded_heap_set_stack_trace_depth(size_t stackTraceDepth)
1086{
1087	if (stackTraceDepth == 0) {
1088		sStackTraceDepth = 0;
1089		return B_OK;
1090	}
1091
1092	// This is rather wasteful, but these are going to be filled lazily by each
1093	// thread on alloc/free. Therefore we cannot use a dynamic allocation and
1094	// just store a pointer to. Since we only need to store two addresses, we
1095	// use two TLS slots and set them to point at the stack base/end.
1096	if (sStackBaseTLSIndex < 0) {
1097		sStackBaseTLSIndex = tls_allocate();
1098		if (sStackBaseTLSIndex < 0)
1099			return sStackBaseTLSIndex;
1100	}
1101
1102	if (sStackEndTLSIndex < 0) {
1103		sStackEndTLSIndex = tls_allocate();
1104		if (sStackEndTLSIndex < 0)
1105			return sStackEndTLSIndex;
1106	}
1107
1108	sStackTraceDepth = min_c(stackTraceDepth, kMaxStackTraceDepth);
1109	return B_OK;
1110}
1111
1112
1113// #pragma mark - Init
1114
1115
1116static void
1117init_after_fork()
1118{
1119	// The memory has actually been copied (or is in a copy on write state) but
1120	// but the area ids have changed.
1121	for (guarded_heap_area* area = sGuardedHeap.areas; area != NULL;
1122			area = area->next) {
1123		area->area = area_for(area);
1124		if (area->area < 0)
1125			panic("failed to find area for heap area %p after fork", area);
1126	}
1127}
1128
1129
1130static status_t
1131guarded_heap_init(void)
1132{
1133	if (!guarded_heap_area_create(sGuardedHeap, GUARDED_HEAP_INITIAL_SIZE))
1134		return B_ERROR;
1135
1136	// Install a segfault handler so we can print some info before going down.
1137	struct sigaction action;
1138	action.sa_handler = (__sighandler_t)guarded_heap_segfault_handler;
1139	action.sa_flags = SA_SIGINFO;
1140	action.sa_userdata = NULL;
1141	sigemptyset(&action.sa_mask);
1142	sigaction(SIGSEGV, &action, NULL);
1143
1144	atfork(&init_after_fork);
1145		// Note: Needs malloc(). Hence we need to be fully initialized.
1146		// TODO: We should actually also install a hook that is called before
1147		// fork() is being executed. In a multithreaded app it would need to
1148		// acquire *all* allocator locks, so that we don't fork() an
1149		// inconsistent state.
1150
1151	return B_OK;
1152}
1153
1154
1155static void
1156guarded_heap_terminate_after()
1157{
1158	if (sDumpAllocationsOnExit)
1159		dump_allocations_full();
1160}
1161
1162
1163// #pragma mark - Public API
1164
1165
1166static void*
1167heap_memalign(size_t alignment, size_t size)
1168{
1169	if (size == 0)
1170		size = 1;
1171
1172	return guarded_heap_allocate(sGuardedHeap, size, alignment);
1173}
1174
1175
1176static void*
1177heap_malloc(size_t size)
1178{
1179	return heap_memalign(sDefaultAlignment, size);
1180}
1181
1182
1183static void
1184heap_free(void* address)
1185{
1186	if (!guarded_heap_free(address))
1187		panic("free failed for address %p", address);
1188}
1189
1190
1191static void*
1192heap_realloc(void* address, size_t newSize)
1193{
1194	if (newSize == 0) {
1195		free(address);
1196		return NULL;
1197	}
1198
1199	if (address == NULL)
1200		return heap_memalign(sDefaultAlignment, newSize);
1201
1202	return guarded_heap_realloc(address, newSize);
1203}
1204
1205
1206heap_implementation __mallocGuardedHeap = {
1207	guarded_heap_init,
1208	guarded_heap_terminate_after,
1209
1210	heap_memalign,
1211	heap_malloc,
1212	heap_free,
1213	heap_realloc,
1214
1215	NULL,	// calloc
1216	NULL,	// valloc
1217	NULL,	// posix_memalign
1218
1219	NULL,	// start_wall_checking
1220	NULL,	// stop_wall_checking
1221	NULL,	// set_paranoid_validation
1222
1223	guarded_heap_set_memory_reuse,
1224	guarded_heap_set_debugger_calls,
1225	guarded_heap_set_default_alignment,
1226
1227	NULL,	// validate_heaps
1228	NULL,	// validate_walls
1229
1230	guarded_heap_dump_allocations,
1231	guarded_heap_dump_heaps,
1232	heap_malloc,
1233
1234	NULL,	// get_allocation_info
1235
1236	guarded_heap_set_dump_allocations_on_exit,
1237	guarded_heap_set_stack_trace_depth
1238};
1239