1/*
2 * Copyright 2002-2007, Haiku Inc.
3 * Distributed under the terms of the MIT License.
4 */
5
6/* Hoard: A Fast, Scalable, and Memory-Efficient Allocator
7 * 		for Shared-Memory Multiprocessors
8 * Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery
9 *
10 * Copyright (c) 1998-2000, The University of Texas at Austin.
11 *
12 * This library is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation, http://www.fsf.org.
15 *
16 * This library is distributed in the hope that it will be useful, but
17 * WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19 * Library General Public License for more details.
20 */
21
22#include "config.h"
23#include "threadheap.h"
24#include "processheap.h"
25#include "arch-specific.h"
26
27#include <image.h>
28
29#include <errno.h>
30#include <string.h>
31
32#include <errno_private.h>
33#include <user_thread.h>
34
35#include "tracing_config.h"
36
37using namespace BPrivate;
38
39
40#if USER_MALLOC_TRACING
41#	define KTRACE(format...)	ktrace_printf(format)
42#else
43#	define KTRACE(format...)	do {} while (false)
44#endif
45
46
47#if HEAP_LEAK_CHECK
48static block* sUsedList = NULL;
49static hoardLockType sUsedLock = MUTEX_INITIALIZER("");
50
51
52/*!
53	Finds the closest symbol that comes before the given address.
54*/
55static status_t
56get_symbol_for_address(void* address, char *imageBuffer, size_t imageBufferSize,
57	char* buffer, size_t bufferSize, int32& offset)
58{
59	offset = -1;
60
61	image_info info;
62	int32 cookie = 0;
63	while (get_next_image_info(0, &cookie, &info) == B_OK) {
64		if (((addr_t)info.text > (addr_t)address
65				|| (addr_t)info.text + info.text_size < (addr_t)address)
66			&& ((addr_t)info.data > (addr_t)address
67				|| (addr_t)info.data + info.data_size < (addr_t)address))
68			continue;
69
70		char name[256];
71		int32 index = 0;
72		int32 nameLength = sizeof(name);
73		int32 symbolType;
74		void* location;
75		while (get_nth_image_symbol(info.id, index, name, &nameLength,
76				&symbolType, &location) == B_OK) {
77			if ((addr_t)address >= (addr_t)location) {
78				// see if this is better than what we have
79				int32 newOffset = (addr_t)address - (addr_t)location;
80
81				if (offset == -1 || offset > newOffset) {
82					const char* imageName = strrchr(info.name, '/');
83					if (imageName != NULL)
84						strlcpy(imageBuffer, imageName + 1, imageBufferSize);
85					else
86						strlcpy(imageBuffer, info.name, imageBufferSize);
87
88					strlcpy(buffer, name, bufferSize);
89					offset = newOffset;
90				}
91			}
92
93			nameLength = sizeof(name);
94			index++;
95		}
96	}
97
98	return offset != -1 ? B_OK : B_ENTRY_NOT_FOUND;
99}
100
101
102static void
103dump_block(block* b)
104{
105	printf("  %p, %ld bytes: call stack", b + 1, b->getAllocatedSize());
106
107	for (int i = 0; i < HEAP_CALL_STACK_SIZE; i++) {
108		if (b->getCallStack(i) != NULL) {
109			char image[256];
110			char name[256];
111			int32 offset;
112			if (get_symbol_for_address(b->getCallStack(i), image, sizeof(image),
113					name, sizeof(name), offset) != B_OK) {
114				strcpy(name, "???");
115				offset = 0;
116			}
117
118			printf(": %p (%s:%s+0x%lx)", b->getCallStack(i), image, name, offset);
119		}
120	}
121	putchar('\n');
122}
123
124
125extern "C" void __dump_allocated(void);
126
127extern "C" void
128__dump_allocated(void)
129{
130	hoardLock(sUsedLock);
131
132	puts("allocated:\n");
133
134	block* b = sUsedList;
135	while (b != NULL) {
136		dump_block(b);
137
138		b = b->getNext();
139	}
140
141	hoardUnlock(sUsedLock);
142}
143
144
145static void
146add_address(void* address, size_t size)
147{
148	block *b = (block *)address - 1;
149
150#ifdef __i386__
151	// set call stack
152	struct stack_frame {
153		struct stack_frame*	previous;
154		void*				return_address;
155	};
156
157	stack_frame* frame = (stack_frame*)get_stack_frame();
158
159	for (int i = 0; i < HEAP_CALL_STACK_SIZE; i++) {
160		if (frame != NULL) {
161			b->setCallStack(i, frame->return_address);
162			frame = frame->previous;
163		} else
164			b->setCallStack(i, NULL);
165	}
166
167	b->setAllocatedSize(size);
168#endif
169
170	hoardLock(sUsedLock);
171
172	b->setNext(sUsedList);
173	sUsedList = b;
174
175	hoardUnlock(sUsedLock);
176}
177
178
179static void
180remove_address(void* address)
181{
182	block* b = (block *)address - 1;
183	hoardLock(sUsedLock);
184
185	if (sUsedList == b) {
186		// we're lucky, it's the first block in the list
187		sUsedList = b->getNext();
188	} else {
189		// search for block in the used list (very slow!)
190		block* last = sUsedList;
191		while (last != NULL && last->getNext() != b) {
192			last = last->getNext();
193		}
194
195		if (last == NULL) {
196			printf("freed block not in used list!\n");
197			dump_block(b);
198		} else
199			last->setNext(b->getNext());
200	}
201
202	hoardUnlock(sUsedLock);
203}
204
205#endif	// HEAP_LEAK_CHECK
206
207#if HEAP_WALL
208
209static void*
210set_wall(void* addr, size_t size)
211{
212	size_t *start = (size_t*)addr;
213
214	start[0] = size;
215	memset(start + 1, 0x88, HEAP_WALL_SIZE - sizeof(size_t));
216	memset((uint8*)addr + size - HEAP_WALL_SIZE, 0x66, HEAP_WALL_SIZE);
217
218	return (uint8*)addr + HEAP_WALL_SIZE;
219}
220
221
222static void*
223check_wall(uint8* buffer)
224{
225	buffer -= HEAP_WALL_SIZE;
226	size_t size = *(size_t*)buffer;
227
228	if (threadHeap::objectSize(buffer) < size)
229		debugger("invalid size");
230
231	for (size_t i = 0; i < HEAP_WALL_SIZE; i++) {
232		if (i >= sizeof(size_t) && buffer[i] != 0x88) {
233			debug_printf("allocation %p, size %ld front wall clobbered at byte %ld.\n",
234				buffer + HEAP_WALL_SIZE, size - 2 * HEAP_WALL_SIZE, i);
235			debugger("front wall clobbered");
236		}
237		if (buffer[i + size - HEAP_WALL_SIZE] != 0x66) {
238			debug_printf("allocation %p, size %ld back wall clobbered at byte %ld.\n",
239				buffer + HEAP_WALL_SIZE, size - 2 * HEAP_WALL_SIZE, i);
240			debugger("back wall clobbered");
241		}
242	}
243
244	return buffer;
245}
246
247#endif	// HEAP_WALL
248
249inline static processHeap *
250getAllocator(void)
251{
252	static char *buffer = (char *)hoardSbrk(sizeof(processHeap));
253	static processHeap *theAllocator = new (buffer) processHeap();
254
255	return theAllocator;
256}
257
258
259extern "C" void
260__heap_before_fork(void)
261{
262	static processHeap *pHeap = getAllocator();
263	for (int i = 0; i < pHeap->getMaxThreadHeaps(); i++)
264		pHeap->getHeap(i).lock();
265
266	static_cast<hoardHeap*>(pHeap)->lock();
267}
268
269void __init_after_fork(void);
270
271extern "C" void
272__heap_after_fork_child(void)
273{
274	__init_after_fork();
275	static processHeap *pHeap = getAllocator();
276	for (int i = 0; i < pHeap->getMaxThreadHeaps(); i++)
277		pHeap->getHeap(i).initLock();
278
279	pHeap->initLock();
280}
281
282
283extern "C" void
284__heap_after_fork_parent(void)
285{
286	static processHeap *pHeap = getAllocator();
287	for (int i = 0; i < pHeap->getMaxThreadHeaps(); i++)
288		pHeap->getHeap(i).unlock();
289
290	static_cast<hoardHeap*>(pHeap)->unlock();
291}
292
293
294extern "C" void
295__heap_thread_init(void)
296{
297}
298
299
300extern "C" void
301__heap_thread_exit(void)
302{
303}
304
305
306//	#pragma mark - public functions
307
308
309extern "C" void *
310malloc(size_t size)
311{
312	static processHeap *pHeap = getAllocator();
313
314#if HEAP_WALL
315	size += 2 * HEAP_WALL_SIZE;
316#endif
317
318	defer_signals();
319
320	void *addr = pHeap->getHeap(pHeap->getHeapIndex()).malloc(size);
321	if (addr == NULL) {
322		undefer_signals();
323		__set_errno(B_NO_MEMORY);
324		KTRACE("malloc(%lu) -> NULL", size);
325		return NULL;
326	}
327
328#if HEAP_LEAK_CHECK
329	add_address(addr, size);
330#endif
331
332	undefer_signals();
333
334#if HEAP_WALL
335	addr = set_wall(addr, size);
336#endif
337
338	KTRACE("malloc(%lu) -> %p", size, addr);
339
340	return addr;
341}
342
343
344extern "C" void *
345calloc(size_t nelem, size_t elsize)
346{
347	static processHeap *pHeap = getAllocator();
348	size_t size = nelem * elsize;
349	void *ptr = NULL;
350
351	if ((nelem > 0) && ((size/nelem) != elsize))
352		goto nomem;
353
354#if HEAP_WALL
355	size += 2 * HEAP_WALL_SIZE;
356
357	if (nelem == 0 || elsize == 0)
358		goto ok;
359	if (size < (nelem * size)&& size < (elsize * size))
360		goto nomem;
361
362ok:
363#endif
364
365	defer_signals();
366
367	ptr = pHeap->getHeap(pHeap->getHeapIndex()).malloc(size);
368	if (ptr == NULL) {
369		undefer_signals();
370	nomem:
371		__set_errno(B_NO_MEMORY);
372		KTRACE("calloc(%lu, %lu) -> NULL", nelem, elsize);
373		return NULL;
374	}
375
376#if HEAP_LEAK_CHECK
377	add_address(ptr, size);
378#endif
379
380	undefer_signals();
381
382#if HEAP_WALL
383	ptr = set_wall(ptr, size);
384	size -= 2 * HEAP_WALL_SIZE;
385#endif
386
387	// Zero out the malloc'd block.
388	memset(ptr, 0, size);
389	KTRACE("calloc(%lu, %lu) -> %p", nelem, elsize, ptr);
390	return ptr;
391}
392
393
394extern "C" void
395free(void *ptr)
396{
397	static processHeap *pHeap = getAllocator();
398
399#if HEAP_WALL
400	if (ptr == NULL)
401		return;
402	KTRACE("free(%p)", ptr);
403	ptr = check_wall((uint8*)ptr);
404#else
405	KTRACE("free(%p)", ptr);
406#endif
407
408	defer_signals();
409
410#if HEAP_LEAK_CHECK
411	if (ptr != NULL)
412		remove_address(ptr);
413#endif
414	pHeap->free(ptr);
415
416	undefer_signals();
417}
418
419
420extern "C" void *
421memalign(size_t alignment, size_t size)
422{
423	static processHeap *pHeap = getAllocator();
424
425#if HEAP_WALL
426	debug_printf("memalign() is not yet supported by the wall code.\n");
427	return NULL;
428#endif
429
430	defer_signals();
431
432	void *addr = pHeap->getHeap(pHeap->getHeapIndex()).memalign(alignment,
433		size);
434	if (addr == NULL) {
435		undefer_signals();
436		__set_errno(B_NO_MEMORY);
437		KTRACE("memalign(%lu, %lu) -> NULL", alignment, size);
438		return NULL;
439	}
440
441#if HEAP_LEAK_CHECK
442	add_address(addr, size);
443#endif
444
445	undefer_signals();
446
447	KTRACE("memalign(%lu, %lu) -> %p", alignment, size, addr);
448	return addr;
449}
450
451
452extern "C" void *
453aligned_alloc(size_t alignment, size_t size)
454{
455	if (size % alignment != 0) {
456		__set_errno(B_BAD_VALUE);
457		return NULL;
458	}
459	return memalign(alignment, size);
460}
461
462
463extern "C" int
464posix_memalign(void **_pointer, size_t alignment, size_t size)
465{
466	if ((alignment & (sizeof(void *) - 1)) != 0 || _pointer == NULL)
467		return B_BAD_VALUE;
468
469#if HEAP_WALL
470	debug_printf("posix_memalign() is not yet supported by the wall code.\n");
471	return -1;
472#endif
473	static processHeap *pHeap = getAllocator();
474	defer_signals();
475	void *pointer = pHeap->getHeap(pHeap->getHeapIndex()).memalign(alignment,
476		size);
477	if (pointer == NULL) {
478		undefer_signals();
479		KTRACE("posix_memalign(%p, %lu, %lu) -> NULL", _pointer, alignment,
480			size);
481		return B_NO_MEMORY;
482	}
483
484#if HEAP_LEAK_CHECK
485	add_address(pointer, size);
486#endif
487
488	undefer_signals();
489
490	*_pointer = pointer;
491	KTRACE("posix_memalign(%p, %lu, %lu) -> %p", _pointer, alignment, size,
492		pointer);
493	return 0;
494}
495
496
497extern "C" void *
498valloc(size_t size)
499{
500	return memalign(B_PAGE_SIZE, size);
501}
502
503
504extern "C" void *
505realloc(void *ptr, size_t size)
506{
507	if (ptr == NULL)
508		return malloc(size);
509
510	if (size == 0) {
511		free(ptr);
512		return NULL;
513	}
514
515	// If the existing object can hold the new size,
516	// just return it.
517
518#if HEAP_WALL
519	size += 2 * HEAP_WALL_SIZE;
520	ptr = (uint8*)ptr - HEAP_WALL_SIZE;
521#endif
522
523	size_t objSize = threadHeap::objectSize(ptr);
524	if (objSize >= size) {
525#if HEAP_WALL
526		check_wall((uint8*)ptr + HEAP_WALL_SIZE);
527		ptr = set_wall(ptr, size);
528#endif
529		KTRACE("realloc(%p, %lu) -> %p", ptr, size, ptr);
530		return ptr;
531	}
532
533#if HEAP_WALL
534	size -= 2 * HEAP_WALL_SIZE;
535	objSize -= 2 * HEAP_WALL_SIZE;
536	ptr = (uint8*)ptr + HEAP_WALL_SIZE;
537#endif
538
539	// Allocate a new block of size sz.
540	void *buffer = malloc(size);
541	if (buffer == NULL) {
542		// Allocation failed, leave old block and return
543		__set_errno(B_NO_MEMORY);
544		KTRACE("realloc(%p, %lu) -> NULL", ptr, size);
545		return NULL;
546	}
547
548	// Copy the contents of the original object
549	// up to the size of the new block.
550
551	size_t minSize = (objSize < size) ? objSize : size;
552	memcpy(buffer, ptr, minSize);
553
554	// Free the old block.
555	free(ptr);
556
557	// Return a pointer to the new one.
558	KTRACE("realloc(%p, %lu) -> %p", ptr, size, buffer);
559	return buffer;
560}
561
562
563extern "C" size_t
564malloc_usable_size(void *ptr)
565{
566	if (ptr == NULL)
567		return 0;
568	return threadHeap::objectSize(ptr);
569}
570
571
572//	#pragma mark - BeOS specific extensions
573
574
575struct mstats {
576	size_t bytes_total;
577	size_t chunks_used;
578	size_t bytes_used;
579	size_t chunks_free;
580	size_t bytes_free;
581};
582
583
584extern "C" struct mstats mstats(void);
585
586extern "C" struct mstats
587mstats(void)
588{
589	// Note, the stats structure is not thread-safe, but it doesn't
590	// matter that much either
591	processHeap *heap = getAllocator();
592	static struct mstats stats;
593
594	int allocated = 0;
595	int used = 0;
596	int chunks = 0;
597
598	for (int i = 0; i < hoardHeap::SIZE_CLASSES; i++) {
599		int classUsed, classAllocated;
600		heap->getStats(i, classUsed, classAllocated);
601
602		if (classUsed > 0)
603			chunks++;
604
605		allocated += classAllocated;
606		used += classUsed;
607	}
608
609	stats.bytes_total = allocated;
610	stats.chunks_used = chunks;
611	stats.bytes_used = used;
612	stats.chunks_free = hoardHeap::SIZE_CLASSES - chunks;
613	stats.bytes_free = allocated - used;
614
615	return stats;
616}
617
618