1 /*
2 *
3 * Copyright (C) 2008 Advanced Micro Devices, Inc.
4 * Copyright (C) 2008-2010 coresystems GmbH
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 /*
31 * This is a classically weak malloc() implementation. We have a relatively
32 * small and static heap, so we take the easy route with an O(N) loop
33 * through the tree for every malloc() and free(). Obviously, this doesn't
34 * scale past a few hundred KB (if that).
35 *
36 * We're also susceptible to the usual buffer overrun poisoning, though the
37 * risk is within acceptable ranges for this implementation (don't overrun
38 * your buffers, kids!).
39 */
40
41 #define IN_MALLOC_C
42 #include <libpayload.h>
43 #include <stdint.h>
44
45 struct memory_type {
46 void *start;
47 void *end;
48 struct align_region_t* align_regions;
49 #if CONFIG(LP_DEBUG_MALLOC)
50 int magic_initialized;
51 size_t minimal_free;
52 const char *name;
53 #endif
54 };
55
56 extern char _heap, _eheap; /* Defined in the ldscript. */
57
58 static struct memory_type default_type =
59 { (void *)&_heap, (void *)&_eheap, NULL
60 #if CONFIG(LP_DEBUG_MALLOC)
61 , 0, 0, "HEAP"
62 #endif
63 };
64 static struct memory_type *const heap = &default_type;
65 static struct memory_type *dma = &default_type;
66
67 typedef u64 hdrtype_t;
68 #define HDRSIZE (sizeof(hdrtype_t))
69
70 #define SIZE_BITS ((HDRSIZE << 3) - 7)
71 #define MAGIC (((hdrtype_t)0x2a) << (SIZE_BITS + 1))
72 #define FLAG_FREE (((hdrtype_t)0x01) << (SIZE_BITS + 0))
73 #define MAX_SIZE ((((hdrtype_t)0x01) << SIZE_BITS) - 1)
74
75 #define SIZE(_h) ((_h) & MAX_SIZE)
76
77 #define _HEADER(_s, _f) ((hdrtype_t) (MAGIC | (_f) | ((_s) & MAX_SIZE)))
78
79 #define FREE_BLOCK(_s) _HEADER(_s, FLAG_FREE)
80 #define USED_BLOCK(_s) _HEADER(_s, 0)
81
82 #define IS_FREE(_h) (((_h) & (MAGIC | FLAG_FREE)) == (MAGIC | FLAG_FREE))
83 #define HAS_MAGIC(_h) (((_h) & MAGIC) == MAGIC)
84
85 static int free_aligned(void* addr, struct memory_type *type);
86 void print_malloc_map(void);
87
init_dma_memory(void * start,u32 size)88 void init_dma_memory(void *start, u32 size)
89 {
90 if (dma_initialized()) {
91 printf("ERROR: %s called twice!\n", __func__);
92 return;
93 }
94
95 /*
96 * DMA memory might not be zeroed by coreboot on stage loading, so make
97 * sure we clear the magic cookie from last boot.
98 */
99 *(hdrtype_t *)start = 0;
100
101 dma = malloc(sizeof(*dma));
102 dma->start = start;
103 dma->end = start + size;
104 dma->align_regions = NULL;
105
106 #if CONFIG(LP_DEBUG_MALLOC)
107 dma->minimal_free = 0;
108 dma->magic_initialized = 0;
109 dma->name = "DMA";
110
111 printf("Initialized cache-coherent DMA memory at [%p:%p]\n", start, start + size);
112 #endif
113 }
114
dma_initialized(void)115 int dma_initialized(void)
116 {
117 return dma != heap;
118 }
119
120 /* For boards that don't initialize DMA we assume all locations are coherent */
dma_coherent(const void * ptr)121 int dma_coherent(const void *ptr)
122 {
123 return !dma_initialized() || (dma->start <= ptr && dma->end > ptr);
124 }
125
126 /* Get the range of memory that can be allocated by the dma allocator. */
dma_allocator_range(void ** start_out,size_t * size_out)127 void dma_allocator_range(void **start_out, size_t *size_out)
128 {
129 if (dma_initialized()) {
130 *start_out = dma->start;
131 *size_out = dma->end - dma->start;
132 } else {
133 *start_out = NULL;
134 *size_out = 0;
135 }
136 }
137
138 /* Find free block of size >= len */
find_free_block(int len,struct memory_type * type)139 static hdrtype_t volatile *find_free_block(int len, struct memory_type *type)
140 {
141 hdrtype_t header;
142 hdrtype_t volatile *ptr = (hdrtype_t volatile *)type->start;
143
144 /* Align the size. */
145 len = ALIGN_UP(len, HDRSIZE);
146
147 if (!len || len > MAX_SIZE)
148 return (void *)NULL;
149
150 /* Make sure the region is setup correctly. */
151 if (!HAS_MAGIC(*ptr)) {
152 size_t size = (type->end - type->start) - HDRSIZE;
153 *ptr = FREE_BLOCK(size);
154 #if CONFIG(LP_DEBUG_MALLOC)
155 type->magic_initialized = 1;
156 type->minimal_free = size;
157 #endif
158 }
159
160 /* Find some free space. */
161 do {
162 header = *ptr;
163 int size = SIZE(header);
164
165 if (!HAS_MAGIC(header) || size == 0) {
166 printf("memory allocator panic. (%s%s)\n",
167 !HAS_MAGIC(header) ? " no magic " : "",
168 size == 0 ? " size=0 " : "");
169 halt();
170 }
171
172 if ((header & FLAG_FREE) && len <= size)
173 return ptr;
174
175 ptr = (hdrtype_t volatile *)((uintptr_t)ptr + HDRSIZE + size);
176
177 } while (ptr < (hdrtype_t *) type->end);
178
179 /* Nothing available. */
180 return NULL;
181 }
182
183 /* Mark the block with length 'len' as used */
use_block(hdrtype_t volatile * ptr,int len)184 static void use_block(hdrtype_t volatile *ptr, int len)
185 {
186 /* Align the size. */
187 len = ALIGN_UP(len, HDRSIZE);
188
189 hdrtype_t volatile *nptr = (hdrtype_t volatile *)
190 ((uintptr_t)ptr + HDRSIZE + len);
191 int size = SIZE(*ptr);
192 int nsize = size - (HDRSIZE + len);
193
194 /*
195 * If there is still room in this block, then mark it as such otherwise
196 * account the whole space for that block.
197 */
198 if (nsize > 0) {
199 /* Mark the block as used. */
200 *ptr = USED_BLOCK(len);
201
202 /* Create a new free block. */
203 *nptr = FREE_BLOCK(nsize);
204 } else {
205 /* Mark the block as used. */
206 *ptr = USED_BLOCK(size);
207 }
208 }
209
alloc(int len,struct memory_type * type)210 static void *alloc(int len, struct memory_type *type)
211 {
212 hdrtype_t volatile *ptr = find_free_block(len, type);
213
214 if (ptr == NULL)
215 return NULL;
216
217 use_block(ptr, len);
218 return (void *)((uintptr_t)ptr + HDRSIZE);
219 }
220
_consolidate(struct memory_type * type)221 static void _consolidate(struct memory_type *type)
222 {
223 void *ptr = type->start;
224
225 while (ptr < type->end) {
226 void *nptr;
227 hdrtype_t hdr = *((hdrtype_t *) ptr);
228 unsigned int size = 0;
229
230 if (!IS_FREE(hdr)) {
231 ptr += HDRSIZE + SIZE(hdr);
232 continue;
233 }
234
235 size = SIZE(hdr);
236 nptr = ptr + HDRSIZE + SIZE(hdr);
237
238 while (nptr < type->end) {
239 hdrtype_t nhdr = *((hdrtype_t *) nptr);
240
241 if (!(IS_FREE(nhdr)))
242 break;
243
244 size += SIZE(nhdr) + HDRSIZE;
245
246 *((hdrtype_t *) nptr) = 0;
247
248 nptr += (HDRSIZE + SIZE(nhdr));
249 }
250
251 *((hdrtype_t *) ptr) = FREE_BLOCK(size);
252 ptr = nptr;
253 }
254 }
255
free(void * ptr)256 void free(void *ptr)
257 {
258 hdrtype_t hdr;
259 struct memory_type *type = heap;
260
261 /* No action occurs on NULL. */
262 if (ptr == NULL)
263 return;
264
265 /* Sanity check. */
266 if (ptr < type->start || ptr >= type->end) {
267 type = dma;
268 if (ptr < type->start || ptr >= type->end)
269 return;
270 }
271
272 if (free_aligned(ptr, type)) return;
273
274 ptr -= HDRSIZE;
275 hdr = *((hdrtype_t *) ptr);
276
277 /* Not our header (we're probably poisoned). */
278 if (!HAS_MAGIC(hdr))
279 return;
280
281 /* Double free. */
282 if (hdr & FLAG_FREE)
283 return;
284
285 *((hdrtype_t *) ptr) = FREE_BLOCK(SIZE(hdr));
286 _consolidate(type);
287 }
288
malloc(size_t size)289 void *malloc(size_t size)
290 {
291 return alloc(size, heap);
292 }
293
dma_malloc(size_t size)294 void *dma_malloc(size_t size)
295 {
296 return alloc(size, dma);
297 }
298
calloc(size_t nmemb,size_t size)299 void *calloc(size_t nmemb, size_t size)
300 {
301 size_t total = nmemb * size;
302 void *ptr = alloc(total, heap);
303
304 if (ptr)
305 memset(ptr, 0, total);
306
307 return ptr;
308 }
309
realloc(void * ptr,size_t size)310 void *realloc(void *ptr, size_t size)
311 {
312 void *ret, *pptr;
313 hdrtype_t volatile *block;
314 unsigned int osize;
315 struct memory_type *type = heap;
316
317 if (ptr == NULL)
318 return alloc(size, type);
319
320 pptr = ptr - HDRSIZE;
321
322 if (!HAS_MAGIC(*((hdrtype_t *) pptr)))
323 return NULL;
324
325 if (ptr < type->start || ptr >= type->end)
326 type = dma;
327
328 /* Get the original size of the block. */
329 osize = SIZE(*((hdrtype_t *) pptr));
330
331 /*
332 * Free the memory to update the tables - this won't touch the actual
333 * memory, so we can still use it for the copy after we have
334 * reallocated the new space.
335 */
336 free(ptr);
337
338 block = find_free_block(size, type);
339 if (block == NULL)
340 return NULL;
341
342 ret = (void *)((uintptr_t)block + HDRSIZE);
343
344 /*
345 * If ret == ptr, then no copy is needed. Otherwise, move the memory to
346 * the new location, which might be before the old one and overlap since
347 * the free() above includes a _consolidate().
348 */
349 if (ret != ptr)
350 memmove(ret, ptr, osize > size ? size : osize);
351
352 /* Mark the block as used. */
353 use_block(block, size);
354
355 return ret;
356 }
357
358 struct align_region_t
359 {
360 /* If alignment is 0 then the region represents a large region which
361 * has no metadata for tracking subelements. */
362 int alignment;
363 /* start in memory, and size in bytes */
364 void* start;
365 int size;
366 /* layout within a region:
367 - num_elements bytes, 0: free, 1: used, 2: used, combines with next
368 - padding to alignment
369 - data section
370 - waste space
371
372 start_data points to the start of the data section
373 */
374 void* start_data;
375 /* number of free blocks sized "alignment" */
376 int free;
377 struct align_region_t *next;
378 };
379
region_is_large(const struct align_region_t * r)380 static inline int region_is_large(const struct align_region_t *r)
381 {
382 return r->alignment == 0;
383 }
384
addr_in_region(const struct align_region_t * r,void * addr)385 static inline int addr_in_region(const struct align_region_t *r, void *addr)
386 {
387 return ((addr >= r->start_data) && (addr < r->start_data + r->size));
388 }
389
390 /* num_elements == 0 indicates a large aligned region instead of a smaller
391 * region comprised of alignment-sized chunks. */
allocate_region(int alignment,int num_elements,size_t size,struct memory_type * type)392 static struct align_region_t *allocate_region(int alignment, int num_elements,
393 size_t size, struct memory_type *type)
394 {
395 struct align_region_t *r;
396 size_t extra_space;
397
398 #if CONFIG(LP_DEBUG_MALLOC)
399 printf("%s(old align_regions=%p, alignment=%u, num_elements=%u, size=%zu)\n",
400 __func__, type->align_regions, alignment, num_elements, size);
401 #endif
402
403 r = malloc(sizeof(*r));
404
405 if (r == NULL)
406 return NULL;
407
408 memset(r, 0, sizeof(*r));
409
410 if (num_elements != 0) {
411 r->alignment = alignment;
412 r->size = num_elements * alignment;
413 r->free = num_elements;
414 /* Allocate enough memory for alignment requirements and
415 * metadata for each chunk. */
416 extra_space = num_elements;
417 } else {
418 /* Large aligned allocation. Set alignment = 0. */
419 r->alignment = 0;
420 r->size = size;
421 extra_space = 0;
422 }
423
424 r->start = alloc(r->size + alignment + extra_space, type);
425
426 if (r->start == NULL) {
427 free(r);
428 return NULL;
429 }
430
431 r->start_data = (void *)ALIGN_UP((uintptr_t)r->start + extra_space,
432 alignment);
433
434 /* Clear any (if requested) metadata. */
435 memset(r->start, 0, extra_space);
436
437 /* Link the region with the rest. */
438 r->next = type->align_regions;
439 type->align_regions = r;
440
441 return r;
442 }
443
try_free_region(struct align_region_t ** prev_link)444 static void try_free_region(struct align_region_t **prev_link)
445 {
446 struct align_region_t *r = *prev_link;
447
448 /* All large regions are immediately free-able. Non-large regions
449 * need to be checked for the fully freed state. */
450 if (!region_is_large(r)) {
451 if (r->free != r->size / r->alignment)
452 return;
453 }
454
455 /* Unlink region from link list. */
456 *prev_link = r->next;
457
458 /* Free the data and metadata. */
459 free(r->start);
460 free(r);
461 }
462
free_aligned(void * addr,struct memory_type * type)463 static int free_aligned(void* addr, struct memory_type *type)
464 {
465 struct align_region_t **prev_link = &type->align_regions;
466
467 while (*prev_link != NULL)
468 {
469 if (!addr_in_region(*prev_link, addr)) {
470 prev_link = &((*prev_link)->next);
471 continue;
472 }
473
474 if (region_is_large(*prev_link)) {
475 try_free_region(prev_link);
476 return 1;
477 }
478
479 int i = (addr-(*prev_link)->start_data)/(*prev_link)->alignment;
480 u8 *meta = (*prev_link)->start;
481 while (meta[i] == 2)
482 {
483 meta[i++] = 0;
484 (*prev_link)->free++;
485 }
486 meta[i] = 0;
487 (*prev_link)->free++;
488 try_free_region(prev_link);
489 return 1;
490 }
491 return 0;
492 }
493
alloc_aligned(size_t align,size_t size,struct memory_type * type)494 static void *alloc_aligned(size_t align, size_t size, struct memory_type *type)
495 {
496 /* Define a large request to be 1024 bytes for either alignment or
497 * size of allocation. */
498 const size_t large_request = 1024;
499
500 if (size == 0) return 0;
501 if (type->align_regions == 0) {
502 type->align_regions = malloc(sizeof(struct align_region_t));
503 if (type->align_regions == NULL)
504 return NULL;
505 memset(type->align_regions, 0, sizeof(struct align_region_t));
506 }
507 struct align_region_t *reg = type->align_regions;
508
509 if (size >= large_request || align >= large_request) {
510 reg = allocate_region(align, 0, size, type);
511 if (reg == NULL)
512 return NULL;
513 return reg->start_data;
514 }
515
516 look_further:
517 while (reg != 0)
518 {
519 if ((reg->alignment == align) && (reg->free >= (size + align - 1)/align))
520 {
521 #if CONFIG(LP_DEBUG_MALLOC)
522 printf(" found memalign region. %u free, %zu required\n", reg->free, (size + align - 1)/align);
523 #endif
524 break;
525 }
526 reg = reg->next;
527 }
528 if (reg == 0)
529 {
530 #if CONFIG(LP_DEBUG_MALLOC)
531 printf(" need to allocate a new memalign region\n");
532 #endif
533 /* get align regions */
534 reg = allocate_region(align, large_request/align, size, type);
535 #if CONFIG(LP_DEBUG_MALLOC)
536 printf(" ... returned %p\n", reg);
537 #endif
538 }
539 if (reg == 0) {
540 /* Nothing available. */
541 return (void *)NULL;
542 }
543
544 int i, count = 0, target = (size+align-1)/align;
545 for (i = 0; i < (reg->size/align); i++)
546 {
547 if (((u8*)reg->start)[i] == 0)
548 {
549 count++;
550 if (count == target) {
551 count = i+1-count;
552 for (i=0; i<target-1; i++)
553 {
554 ((u8*)reg->start)[count+i]=2;
555 }
556 ((u8*)reg->start)[count+target-1]=1;
557 reg->free -= target;
558 return reg->start_data+(align*count);
559 }
560 } else {
561 count = 0;
562 }
563 }
564 /* The free space in this region is fragmented,
565 so we will move on and try the next one: */
566 reg = reg->next;
567 goto look_further; // end condition is once a new region is allocated - it always has enough space
568 }
569
memalign(size_t align,size_t size)570 void *memalign(size_t align, size_t size)
571 {
572 return alloc_aligned(align, size, heap);
573 }
574
dma_memalign(size_t align,size_t size)575 void *dma_memalign(size_t align, size_t size)
576 {
577 return alloc_aligned(align, size, dma);
578 }
579
580 /* This is for debugging purposes. */
581 #if CONFIG(LP_DEBUG_MALLOC)
print_malloc_map(void)582 void print_malloc_map(void)
583 {
584 struct memory_type *type = heap;
585 void *ptr;
586 int free_memory;
587
588 again:
589 ptr = type->start;
590 free_memory = 0;
591
592 while (ptr < type->end) {
593 hdrtype_t hdr = *((hdrtype_t *) ptr);
594
595 if (!HAS_MAGIC(hdr)) {
596 if (type->magic_initialized)
597 printf("%s: Poisoned magic - we're toast\n", type->name);
598 else
599 printf("%s: No magic yet - going to initialize\n", type->name);
600 break;
601 }
602
603 /* FIXME: Verify the size of the block. */
604
605 printf("%s %x: %s (%llx bytes)\n", type->name,
606 (unsigned int)(ptr - type->start),
607 hdr & FLAG_FREE ? "FREE" : "USED", SIZE(hdr));
608
609 if (hdr & FLAG_FREE)
610 free_memory += SIZE(hdr);
611
612 ptr += HDRSIZE + SIZE(hdr);
613 }
614
615 if (free_memory && (type->minimal_free > free_memory))
616 type->minimal_free = free_memory;
617 printf("%s: Maximum memory consumption: %zu bytes\n", type->name,
618 (type->end - type->start) - HDRSIZE - type->minimal_free);
619
620 if (type != dma) {
621 type = dma;
622 goto again;
623 }
624 }
625 #endif
626