2 * This file is part of the libpayload project.
4 * Copyright (C) 2008 Advanced Micro Devices, Inc.
5 * Copyright (C) 2008-2010 coresystems GmbH
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. The name of the author may not be used to endorse or promote products
16 * derived from this software without specific prior written permission.
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * This is a classically weak malloc() implementation. We have a relatively
33 * small and static heap, so we take the easy route with an O(N) loop
34 * through the tree for every malloc() and free(). Obviously, this doesn't
35 * scale past a few hundred KB (if that).
37 * We're also susceptible to the usual buffer overrun poisoning, though the
38 * risk is within acceptable ranges for this implementation (don't overrun
39 * your buffers, kids!).
43 #include <libpayload.h>
45 extern char _heap, _eheap; /* Defined in the ldscript. */
47 static void *hstart = (void *)&_heap;
48 static void *hend = (void *)&_eheap;
50 typedef unsigned int hdrtype_t;
52 #define MAGIC (0x2a << 26)
53 #define FLAG_FREE (1 << 25)
54 #define FLAG_USED (1 << 24)
56 #define SIZE(_h) ((_h) & 0xFFFFFF)
58 #define _HEADER(_s, _f) ((hdrtype_t) (MAGIC | (_f) | ((_s) & 0xFFFFFF)))
60 #define FREE_BLOCK(_s) _HEADER(_s, FLAG_FREE)
61 #define USED_BLOCK(_s) _HEADER(_s, FLAG_USED)
63 #define HDRSIZE (sizeof(hdrtype_t))
65 #define IS_FREE(_h) (((_h) & (MAGIC | FLAG_FREE)) == (MAGIC | FLAG_FREE))
66 #define HAS_MAGIC(_h) (((_h) & MAGIC) == MAGIC)
68 static int free_aligned(void* addr);
69 void print_malloc_map(void);
71 #ifdef CONFIG_DEBUG_MALLOC
72 static int heap_initialized = 0;
73 static int minimal_free = 0;
76 static void setup(hdrtype_t volatile *start, int size)
78 *start = FREE_BLOCK(size);
80 #ifdef CONFIG_DEBUG_MALLOC
86 static void *alloc(int len)
89 hdrtype_t volatile *ptr = (hdrtype_t volatile *) hstart;
94 if (!len || len > 0xffffff)
97 /* Make sure the region is setup correctly. */
101 /* Find some free space. */
104 int size = SIZE(header);
106 if (!HAS_MAGIC(header) || size == 0) {
107 printf("memory allocator panic. (%s%s)\n",
108 !HAS_MAGIC(header) ? " no magic " : "",
109 size == 0 ? " size=0 " : "");
113 if (header & FLAG_FREE) {
115 hdrtype_t volatile *nptr = ptr + (HDRSIZE + len);
116 int nsize = size - (HDRSIZE + len);
118 /* If there is still room in this block,
119 * then mark it as such otherwise account
120 * the whole space for that block.
124 /* Mark the block as used. */
125 *ptr = USED_BLOCK(len);
127 /* Create a new free block. */
128 *nptr = FREE_BLOCK(nsize);
130 /* Mark the block as used. */
131 *ptr = USED_BLOCK(size);
134 return (void *)(ptr + HDRSIZE);
138 ptr += HDRSIZE + size;
140 } while (ptr < (hdrtype_t *) hend);
142 /* Nothing available. */
146 static void _consolidate(void)
152 hdrtype_t hdr = *((hdrtype_t *) ptr);
153 unsigned int size = 0;
156 ptr += HDRSIZE + SIZE(hdr);
161 nptr = ptr + HDRSIZE + SIZE(hdr);
163 while (nptr < hend) {
164 hdrtype_t nhdr = *((hdrtype_t *) nptr);
166 if (!(IS_FREE(nhdr)))
169 size += SIZE(nhdr) + HDRSIZE;
171 *((hdrtype_t *) nptr) = 0;
173 nptr += (HDRSIZE + SIZE(nhdr));
176 *((hdrtype_t *) ptr) = FREE_BLOCK(size);
185 if (free_aligned(ptr)) return;
190 if (ptr < hstart || ptr >= hend)
193 hdr = *((hdrtype_t *) ptr);
195 /* Not our header (we're probably poisoned). */
203 *((hdrtype_t *) ptr) = FREE_BLOCK(SIZE(hdr));
207 void *malloc(size_t size)
212 void *calloc(size_t nmemb, size_t size)
214 size_t total = nmemb * size;
215 void *ptr = alloc(total);
218 memset(ptr, 0, total);
223 void *realloc(void *ptr, size_t size)
231 pptr = ptr - HDRSIZE;
233 if (!HAS_MAGIC(*((hdrtype_t *) pptr)))
236 /* Get the original size of the block. */
237 osize = SIZE(*((hdrtype_t *) pptr));
240 * Free the memory to update the tables - this won't touch the actual
241 * memory, so we can still use it for the copy after we have
242 * reallocated the new space.
248 * if ret == NULL, then doh - failure.
249 * if ret == ptr then woo-hoo! no copy needed.
251 if (ret == NULL || ret == ptr)
254 /* Copy the memory to the new location. */
255 memcpy(ret, ptr, osize > size ? size : osize);
260 struct align_region_t
263 /* start in memory, and size in bytes */
266 /* layout within a region:
267 - num_elements bytes, 0: free, 1: used, 2: used, combines with next
268 - padding to alignment
272 start_data points to the start of the data section
275 /* number of free blocks sized "alignment" */
277 struct align_region_t *next;
280 static struct align_region_t* align_regions = 0;
282 static struct align_region_t *allocate_region(int alignment, int num_elements)
284 struct align_region_t *new_region;
285 #ifdef CONFIG_DEBUG_MALLOC
286 printf("%s(old align_regions=%p, alignment=%u, num_elements=%u)\n",
287 __func__, align_regions, alignment, num_elements);
290 new_region = malloc(sizeof(struct align_region_t));
294 new_region->alignment = alignment;
295 new_region->start = malloc((num_elements+1) * alignment + num_elements);
296 if (!new_region->start) {
300 new_region->start_data = (void*)((u32)(new_region->start + num_elements + alignment - 1) & (~(alignment-1)));
301 new_region->size = num_elements * alignment;
302 new_region->free = num_elements;
303 new_region->next = align_regions;
304 memset(new_region->start, 0, num_elements);
305 align_regions = new_region;
310 static int free_aligned(void* addr)
312 struct align_region_t *reg = align_regions;
315 if ((addr >= reg->start_data) && (addr < reg->start_data + reg->size))
317 int i = (addr-reg->start_data)/reg->alignment;
318 while (((u8*)reg->start)[i]==2)
320 ((u8*)reg->start)[i++]=0;
323 ((u8*)reg->start)[i]=0;
332 void *memalign(size_t align, size_t size)
334 if (size == 0) return 0;
335 if (align_regions == 0) {
336 align_regions = malloc(sizeof(struct align_region_t));
337 if (align_regions == NULL)
339 memset(align_regions, 0, sizeof(struct align_region_t));
341 struct align_region_t *reg = align_regions;
345 if ((reg->alignment == align) && (reg->free >= (size + align - 1)/align))
347 #ifdef CONFIG_DEBUG_MALLOC
348 printf(" found memalign region. %x free, %x required\n", reg->free, (size + align - 1)/align);
356 #ifdef CONFIG_DEBUG_MALLOC
357 printf(" need to allocate a new memalign region\n");
359 /* get align regions */
360 reg = allocate_region(align, (size<1024)?(1024/align):(((size-1)/align)+1));
361 #ifdef CONFIG_DEBUG_MALLOC
362 printf(" ... returned %p\n", align_regions);
366 /* Nothing available. */
370 int i, count = 0, target = (size+align-1)/align;
371 for (i = 0; i < (reg->size/align); i++)
373 if (((u8*)reg->start)[i] == 0)
376 if (count == target) {
378 for (i=0; i<target-1; i++)
380 ((u8*)reg->start)[count+i]=2;
382 ((u8*)reg->start)[count+target-1]=1;
384 return reg->start_data+(align*count);
390 goto look_further; // end condition is once a new region is allocated - it always has enough space
393 /* This is for debugging purposes. */
394 #ifdef CONFIG_DEBUG_MALLOC
395 void print_malloc_map(void)
401 hdrtype_t hdr = *((hdrtype_t *) ptr);
403 if (!HAS_MAGIC(hdr)) {
404 if (heap_initialized)
405 printf("Poisoned magic - we're toast\n");
407 printf("No magic yet - going to initialize\n");
411 /* FIXME: Verify the size of the block. */
413 printf("%x: %s (%x bytes)\n",
414 (unsigned int)(ptr - hstart),
415 hdr & FLAG_FREE ? "FREE" : "USED", SIZE(hdr));
418 free_memory += SIZE(hdr);
420 ptr += HDRSIZE + SIZE(hdr);
423 if (free_memory && (minimal_free > free_memory))
424 minimal_free = free_memory;
425 printf("Maximum memory consumption: %d bytes",
426 (unsigned int)(&_eheap - &_heap) - HDRSIZE - minimal_free);