X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=payloads%2Flibpayload%2Flibc%2Fmalloc.c;h=3c5a3fd2a2c7b4b9a29fa4b2051a8926ca10f43b;hb=ccee6256b48ad619d16c4479a25937fa95b93efc;hp=86fb0b13cda6fa6af1451caa3074ba6748c98d1a;hpb=6a441bfb46337ed6b59abed56dad35d94802282c;p=coreboot.git

diff --git a/payloads/libpayload/libc/malloc.c b/payloads/libpayload/libc/malloc.c
index 86fb0b13c..3c5a3fd2a 100644
--- a/payloads/libpayload/libc/malloc.c
+++ b/payloads/libpayload/libc/malloc.c
@@ -2,6 +2,7 @@
  * This file is part of the libpayload project.
  *
  * Copyright (C) 2008 Advanced Micro Devices, Inc.
+ * Copyright (C) 2008-2010 coresystems GmbH
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -28,16 +29,17 @@
  */
 
 /*
- * This is a classically weak malloc() implmentation. We have a relatively
+ * This is a classically weak malloc() implementation. We have a relatively
  * small and static heap, so we take the easy route with an O(N) loop
  * through the tree for every malloc() and free(). Obviously, this doesn't
  * scale past a few hundred KB (if that).
  *
- * We're also susecptable to the usual buffer overun poisoning, though the
+ * We're also susceptible to the usual buffer overrun poisoning, though the
  * risk is within acceptable ranges for this implementation (don't overrun
  * your buffers, kids!).
  */
 
+#define IN_MALLOC_C
 #include <libpayload.h>
 
 extern char _heap, _eheap;	/* Defined in the ldscript. */
@@ -63,18 +65,28 @@ typedef unsigned int hdrtype_t;
 #define IS_FREE(_h) (((_h) & (MAGIC | FLAG_FREE)) == (MAGIC | FLAG_FREE))
 #define HAS_MAGIC(_h) (((_h) & MAGIC) == MAGIC)
 
+static int free_aligned(void* addr);
 void print_malloc_map(void);
 
-static void setup(void)
+#ifdef CONFIG_DEBUG_MALLOC
+static int heap_initialized = 0;
+static int minimal_free = 0;
+#endif
+
+static void setup(hdrtype_t volatile *start, int size)
 {
-	int size = (unsigned int)(_heap - _eheap) - HDRSIZE;
-	*((hdrtype_t *) hstart) = FREE_BLOCK(size);
+	*start = FREE_BLOCK(size);
+
+#ifdef CONFIG_DEBUG_MALLOC
+	heap_initialized = 1;
+	minimal_free  = size;
+#endif
 }
 
 static void *alloc(int len)
 {
 	hdrtype_t header;
-	void *ptr = hstart;
+	hdrtype_t volatile *ptr = (hdrtype_t volatile *) hstart;
 
 	/* Align the size. */
 	len = (len + 3) & ~3;
@@ -83,36 +95,49 @@ static void *alloc(int len)
 		return (void *)NULL;
 
 	/* Make sure the region is setup correctly. */
-	if (!HAS_MAGIC(*((hdrtype_t *) ptr)))
-		setup();
+	if (!HAS_MAGIC(*ptr))
+		setup(ptr, (int)((&_eheap - &_heap) - HDRSIZE));
 
 	/* Find some free space. */
 	do {
-		header = *((hdrtype_t *) ptr);
+		header = *ptr;
 		int size = SIZE(header);
 
+		if (!HAS_MAGIC(header) || size == 0) {
+			printf("memory allocator panic. (%s%s)\n",
+			       !HAS_MAGIC(header) ? " no magic " : "",
+				   size == 0 ? " size=0 " : "");
+			halt();
+		}
+
 		if (header & FLAG_FREE) {
 			if (len <= size) {
-				void *nptr = ptr + HDRSIZE + len;
-				int nsize = size - (len + 8);
-
-				/* Mark the block as used. */
-				*((hdrtype_t *) ptr) = USED_BLOCK(len);
+				hdrtype_t volatile *nptr = (hdrtype_t volatile *)((int)ptr + HDRSIZE + len);
+				int nsize = size - (HDRSIZE + len);
 
 				/* If there is still room in this block,
-				 * then mark it as such.
+				 * then mark it as such otherwise account
+				 * the whole space for that block.
 				 */
-				if (nsize > 0)
-					*((hdrtype_t *) nptr) =
-					    FREE_BLOCK(nsize - 4);
 
-				return (void *)(ptr + HDRSIZE);
+				if (nsize > 0) {
+					/* Mark the block as used. */
+					*ptr = USED_BLOCK(len);
+
+					/* Create a new free block. */
+					*nptr = FREE_BLOCK(nsize);
+				} else {
+					/* Mark the block as used. */
+					*ptr = USED_BLOCK(size);
+				}
+
+				return (void *)((int)ptr + HDRSIZE);
 			}
 		}
 
-		ptr += HDRSIZE + size;
+		ptr = (hdrtype_t volatile *)((int)ptr + HDRSIZE + size);
 
-	} while (ptr < hend);
+	} while (ptr < (hdrtype_t *) hend);
 
 	/* Nothing available. */
 	return (void *)NULL;
@@ -157,6 +182,8 @@ void free(void *ptr)
 {
 	hdrtype_t hdr;
 
+	if (free_aligned(ptr)) return;
+
 	ptr -= HDRSIZE;
 
 	/* Sanity check. */
@@ -184,8 +211,8 @@ void *malloc(size_t size)
 
 void *calloc(size_t nmemb, size_t size)
 {
-	unsigned int total = (nmemb * size);
-	void *ptr = alloc(size);
+	size_t total = nmemb * size;
+	void *ptr = alloc(total);
 
 	if (ptr)
 		memset(ptr, 0, total);
@@ -230,17 +257,154 @@ void *realloc(void *ptr, size_t size)
 	return ret;
 }
 
+struct align_region_t
+{
+	int alignment;
+	/* start in memory, and size in bytes */
+	void* start;
+	int size;
+	/* layout within a region:
+	  - num_elements bytes, 0: free, 1: used, 2: used, combines with next
+	  - padding to alignment
+	  - data section
+	  - waste space
+
+	  start_data points to the start of the data section
+	*/
+	void* start_data;
+	/* number of free blocks sized "alignment" */
+	int free;
+	struct align_region_t *next;
+};
+
+static struct align_region_t* align_regions = 0;
+
+static struct align_region_t *allocate_region(int alignment, int num_elements)
+{
+	struct align_region_t *new_region;
+#ifdef CONFIG_DEBUG_MALLOC
+	printf("%s(old align_regions=%p, alignment=%u, num_elements=%u)\n",
+			__func__, align_regions, alignment, num_elements);
+#endif
+
+	new_region = malloc(sizeof(struct align_region_t));
+
+	if (!new_region)
+		return NULL;
+	new_region->alignment = alignment;
+	new_region->start = malloc((num_elements+1) * alignment + num_elements);
+	if (!new_region->start) {
+		free(new_region);
+		return NULL;
+	}
+	new_region->start_data = (void*)((u32)(new_region->start + num_elements + alignment - 1) & (~(alignment-1)));
+	new_region->size = num_elements * alignment;
+	new_region->free = num_elements;
+	new_region->next = align_regions;
+	memset(new_region->start, 0, num_elements);
+	align_regions = new_region;
+	return new_region;
+}
+
+
+static int free_aligned(void* addr)
+{
+	struct align_region_t *reg = align_regions;
+	while (reg != 0)
+	{
+		if ((addr >= reg->start_data) && (addr < reg->start_data + reg->size))
+		{
+			int i = (addr-reg->start_data)/reg->alignment;
+			while (((u8*)reg->start)[i]==2)
+			{
+				((u8*)reg->start)[i++]=0;
+				reg->free++;
+			}
+			((u8*)reg->start)[i]=0;
+			reg->free++;
+			return 1;
+		}
+		reg = reg->next;
+	}
+	return 0;
+}
+
+void *memalign(size_t align, size_t size)
+{
+	if (size == 0) return 0;
+	if (align_regions == 0) {
+		align_regions = malloc(sizeof(struct align_region_t));
+		if (align_regions == NULL)
+			return NULL;
+		memset(align_regions, 0, sizeof(struct align_region_t));
+	}
+	struct align_region_t *reg = align_regions;
+look_further:
+	while (reg != 0)
+	{
+		if ((reg->alignment == align) && (reg->free >= (size + align - 1)/align))
+		{
+#ifdef CONFIG_DEBUG_MALLOC
+			printf("  found memalign region. %x free, %x required\n", reg->free, (size + align - 1)/align);
+#endif
+			break;
+		}
+		reg = reg->next;
+	}
+	if (reg == 0)
+	{
+#ifdef CONFIG_DEBUG_MALLOC
+		printf("  need to allocate a new memalign region\n");
+#endif
+		/* get align regions */
+		reg = allocate_region(align, (size<1024)?(1024/align):(((size-1)/align)+1));
+#ifdef CONFIG_DEBUG_MALLOC
+		printf("  ... returned %p\n", align_regions);
+#endif
+	}
+	if (reg == 0) {
+		/* Nothing available. */
+		return (void *)NULL;
+	}
+
+	int i, count = 0, target = (size+align-1)/align;
+	for (i = 0; i < (reg->size/align); i++)
+	{
+		if (((u8*)reg->start)[i] == 0)
+		{
+			count++;
+			if (count == target) {
+				count = i+1-count;
+				for (i=0; i<target-1; i++)
+				{
+					((u8*)reg->start)[count+i]=2;
+				}
+				((u8*)reg->start)[count+target-1]=1;
+				reg->free -= target;
+				return reg->start_data+(align*count);
+			}
+		} else {
+			count = 0;
+		}
+	}
+	goto look_further; // end condition is once a new region is allocated - it always has enough space
+}
+
 /* This is for debugging purposes. */
-#ifdef TEST
+#ifdef CONFIG_DEBUG_MALLOC
 void print_malloc_map(void)
 {
 	void *ptr = hstart;
+	int free_memory = 0;
 
 	while (ptr < hend) {
 		hdrtype_t hdr = *((hdrtype_t *) ptr);
 
 		if (!HAS_MAGIC(hdr)) {
-			printf("Poisoned magic - we're toast\n");
+			if (heap_initialized)
+				printf("Poisoned magic - we're toast\n");
+			else
+				printf("No magic yet - going to initialize\n");
 			break;
 		}
 
@@ -250,7 +414,15 @@ void print_malloc_map(void)
 		       (unsigned int)(ptr - hstart),
 		       hdr & FLAG_FREE ? "FREE" : "USED", SIZE(hdr));
 
+		if (hdr & FLAG_FREE)
+			free_memory += SIZE(hdr);
+
 		ptr += HDRSIZE + SIZE(hdr);
 	}
+
+	if (free_memory && (minimal_free > free_memory))
+		minimal_free = free_memory;
+	printf("Maximum memory consumption: %d bytes\n",
+		(unsigned int)(&_eheap - &_heap) - HDRSIZE - minimal_free);
 }
 #endif