1/*
2 * Copyright 2003-2009, Axel D��rfler, axeld@pinc-software.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include <boot/platform.h>
8#include <boot/heap.h>
9
10#include <stdlib.h>
11#include <stdio.h>
12#include <string.h>
13#include <stdarg.h>
14
15
16extern "C" void* heap_malloc(size_t size);
17extern "C" void* heap_realloc(void* oldBuffer, size_t size);
18extern "C" void heap_free(void* buffer);
19extern void dump_chunks(void);
20extern uint32 heap_available(void);
21
22
23const int32	kHeapSize = 32 * 1024;
24
25int32 gVerbosity = 1;
26
27
28void
29platform_release_heap(struct stage2_args* args, void* base)
30{
31	free(base);
32}
33
34
35status_t
36platform_init_heap(struct stage2_args* args, void** _base, void** _top)
37{
38	void* base = malloc(kHeapSize);
39	if (base == NULL)
40		return B_NO_MEMORY;
41
42	*_base = base;
43	*_top = (void*)((uint8*)base + kHeapSize);
44
45	return B_OK;
46}
47
48
49void
50panic(const char* format, ...)
51{
52	va_list args;
53
54	va_start(args, format);
55	vfprintf(stderr, format, args);
56	va_end(args);
57
58	exit(-1);
59}
60
61
62void
63dprintf(const char* format, ...)
64{
65	va_list args;
66
67	va_start(args, format);
68	vfprintf(stdout, format, args);
69	va_end(args);
70}
71
72
73// #pragma mark -
74
75
76static void
77dump_allocated_chunk(int32 index, void* buffer)
78{
79	if (buffer == NULL || gVerbosity < 3)
80		return;
81
82	size_t* size = (size_t*)((uint8*)buffer - sizeof(uint32));
83	printf("\t%ld. allocation at %p, chunk at %p, size = %ld\n", index, buffer,
84		size, *size);
85
86	if (gVerbosity > 3)
87		dump_chunks();
88}
89
90
91static void*
92test_malloc(size_t bytes)
93{
94	return heap_malloc(bytes);
95}
96
97
98static void*
99test_realloc(void* oldBuffer, size_t size)
100{
101	return heap_realloc(oldBuffer, size);
102}
103
104
105static void
106test_free(void* buffer)
107{
108	if (gVerbosity > 4) {
109		printf("\tfreeing buffer at %p\n", buffer);
110		dump_allocated_chunk(-1, buffer);
111	}
112
113	heap_free(buffer);
114
115	if (gVerbosity > 4) {
116		puts("\t- after:");
117		dump_chunks();
118	}
119}
120
121
122static int32
123random_allocations(void* array[], size_t maxSize)
124{
125	printf("* random allocations (up to %ld bytes)\n", maxSize);
126
127	size_t total = 0;
128	int32 count = 0;
129
130	for (int32 i = 0; i < 100; i++) {
131		size_t size = size_t(rand() * 1. * maxSize / RAND_MAX);
132		array[i] = test_malloc(size);
133		if (array[i] == NULL) {
134			if ((size > heap_available() || size == 0) && gVerbosity < 2)
135				continue;
136
137			printf(	"%ld. allocating %ld bytes failed (%ld bytes total allocated, "
138					"%ld free (%ld))\n",
139					i, size, total, heap_available(), kHeapSize - total);
140		} else {
141			dump_allocated_chunk(i, array[i]);
142
143			total += size;
144			count++;
145		}
146	}
147
148	printf("\t%ld bytes allocated\n", total);
149	if (gVerbosity > 3)
150		dump_chunks();
151
152	return count;
153}
154
155
156int
157main(int argc, char** argv)
158{
159	if (argc > 1)
160		gVerbosity = atoi(argv[1]);
161
162	stage2_args args;
163	memset(&args, 0, sizeof(args));
164	args.heap_size = kHeapSize;
165
166	if (heap_init(&args) < B_OK) {
167		fprintf(stderr, "Could not initialize heap.\n");
168		return -1;
169	}
170
171	printf("heap size == %ld\n", kHeapSize);
172	if (gVerbosity > 2)
173		dump_chunks();
174
175	puts("* simple allocation of 100 * 128 bytes");
176	void* array[100];
177	for (int32 i = 0; i < 100; i++) {
178		array[i] = test_malloc(128);
179		dump_allocated_chunk(i, array[i]);
180	}
181
182	if (gVerbosity > 2)
183		dump_chunks();
184
185	puts("* testing different deleting order");
186	if (gVerbosity > 2)
187		puts("- free 30 from the end (descending):");
188
189	for (int32 i = 100; i-- > 70; ) {
190		test_free(array[i]);
191		array[i] = NULL;
192	}
193
194	if (gVerbosity > 2) {
195		dump_chunks();
196		puts("- free 40 from the middle (ascending):");
197	}
198
199	for (int32 i = 30; i < 70; i++) {
200		test_free(array[i]);
201		array[i] = NULL;
202	}
203
204	if (gVerbosity > 2) {
205		dump_chunks();
206		puts("- free 30 from the start (ascending):");
207	}
208
209	for (int32 i = 0; i < 30; i++) {
210		test_free(array[i]);
211		array[i] = NULL;
212	}
213
214	if (gVerbosity > 2)
215		dump_chunks();
216
217	puts("* allocate until it fails");
218	int32 i = 0;
219	for (i = 0; i < 100; i++) {
220		array[i] = test_malloc(kHeapSize / 64);
221		if (array[i] == NULL) {
222			printf("\tallocation %ld failed - could allocate %ld bytes (64th should fail).\n", i + 1, (kHeapSize / 64) * (i + 1));
223
224			if (gVerbosity > 2)
225				dump_chunks();
226
227			while (i-- > 0) {
228				test_free(array[i]);
229				array[i] = NULL;
230			}
231
232			break;
233		} else
234			dump_allocated_chunk(i, array[i]);
235	}
236	if (i == 100)
237		fprintf(stderr, "could allocate more memory than in heap\n");
238
239	random_allocations(array, 768);
240
241	puts("* free memory again");
242	for (i = 0; i < 100; i++) {
243		test_free(array[i]);
244		array[i] = NULL;
245	}
246
247	for (size_t amount = 32; amount < 1024; amount *= 2) {
248		int32 count = random_allocations(array, amount);
249
250		puts("* random freeing");
251		while (count) {
252			i = int32(rand() * 100. / RAND_MAX);
253			if (array[i] == NULL)
254				continue;
255
256			test_free(array[i]);
257			array[i] = NULL;
258			count--;
259
260			if (gVerbosity > 2) {
261				puts("- freed one");
262				dump_chunks();
263			}
264		}
265	}
266
267	puts("* realloc() test");
268
269	uint8* buffer = (uint8*)test_malloc(1);
270	buffer[0] = 'h';
271
272	uint8* newBuffer = (uint8*)test_realloc(buffer, 2);
273	if (newBuffer != buffer)
274		panic("  could not reuse buffer");
275	newBuffer[1] = 'a';
276	newBuffer = (uint8*)test_realloc(buffer, 3);
277	if (newBuffer != buffer)
278		panic("  could not reuse buffer");
279	newBuffer[2] = 'i';
280	newBuffer = (uint8*)test_realloc(buffer, 4);
281	if (newBuffer != buffer)
282		panic("  could not reuse buffer");
283	newBuffer[3] = 'k';
284	newBuffer = (uint8*)test_realloc(buffer, 5);
285	if (newBuffer == buffer)
286		panic("  could reuse buffer!");
287	newBuffer[4] = 'u';
288	if (memcmp(newBuffer, "haiku", 5))
289		panic("  contents differ!");
290
291	heap_release(&args);
292	return 0;
293}
294
295