Backported malloc and realloc from avr-libc 1.8.0 (without test code)

See #857

4 files changed, 276 insertions, 132 deletions

diff --git a/cores/arduino/malloc.c b/cores/arduino/avr-libc/malloc.c
index 9c56600..3562532 100644
--- a/cores/arduino/malloc.c
+++ b/cores/arduino/avr-libc/malloc.c
@@ -2,9 +2,6 @@
    Copyright (c) 2010  Gerben van den Broeke
    All rights reserved.
 
-       malloc, free, realloc from avr-libc 1.7.0
-       with minor modifications, by Paul Stoffregen
-
    Redistribution and use in source and binary forms, with or without
    modification, are permitted provided that the following conditions are met:
 
@@ -33,20 +30,14 @@
   POSSIBILITY OF SUCH DAMAGE.
 */
  
+ 
+/* $Id: malloc.c 2149 2010-06-09 20:45:37Z joerg_wunsch $ */
 
 #include <stdlib.h>
-#include <inttypes.h>
-#include <string.h>
-#include <avr/io.h>
-
-
-#define __MALLOC_MARGIN__ 120
+#include "sectionname.h"
+#include "stdlib_private.h"
 
-
-struct __freelist {
-	size_t sz;
-	struct __freelist *nx;
-};
+#include <avr/io.h>
 
 /*
  * Exported interface:
@@ -59,13 +50,16 @@ struct __freelist {
  * with the data segment.
  */
  
+/* May be changed by the user only before the first malloc() call.  */
+
+size_t __malloc_margin = 32;
+char *__malloc_heap_start = &__heap_start;
+char *__malloc_heap_end = &__heap_end;
 
-#define STACK_POINTER() ((char *)AVR_STACK_POINTER_REG)
-extern char __heap_start;
-char *__brkval = &__heap_start;	// first location not yet allocated
-struct __freelist *__flp;	// freelist pointer (head of freelist)
-char *__brkval_maximum = 100;
+char *__brkval;
+struct __freelist *__flp;
 
+ATTRIBUTE_CLIB_SECTION
 void *
 malloc(size_t len)
 {
@@ -160,7 +154,11 @@ malloc(size_t len)
 	 * Since we don't have an operating system, just make sure
 	 * that we don't collide with the stack.
 	 */
-	cp = STACK_POINTER() - __MALLOC_MARGIN__;
+	if (__brkval == 0)
+		__brkval = __malloc_heap_start;
+	cp = __malloc_heap_end;
+	if (cp == 0)
+		cp = STACK_POINTER() - __malloc_margin;
 	if (cp <= __brkval)
 	  /*
 	   * Memory exhausted.
@@ -173,7 +171,6 @@ malloc(size_t len)
 	if (avail >= len && avail >= len + sizeof(size_t)) {
 		fp1 = (struct __freelist *)__brkval;
 		__brkval += len + sizeof(size_t);
-		__brkval_maximum = __brkval;
 		fp1->sz = len;
 		return &(fp1->nx);
 	}
@@ -184,6 +181,7 @@ malloc(size_t len)
 }
 
 
+ATTRIBUTE_CLIB_SECTION
 void
 free(void *p)
 {
@@ -267,114 +265,3 @@ free(void *p)
 	}
 }
 
-
-
-void *
-realloc(void *ptr, size_t len)
-{
-	struct __freelist *fp1, *fp2, *fp3, *ofp3;
-	char *cp, *cp1;
-	void *memp;
-	size_t s, incr;
-
-	/* Trivial case, required by C standard. */
-	if (ptr == 0)
-		return malloc(len);
-
-	cp1 = (char *)ptr;
-	cp1 -= sizeof(size_t);
-	fp1 = (struct __freelist *)cp1;
-
-	cp = (char *)ptr + len; /* new next pointer */
-	if (cp < cp1)
-		/* Pointer wrapped across top of RAM, fail. */
-		return 0;
-
-	/*
-	 * See whether we are growing or shrinking.  When shrinking,
-	 * we split off a chunk for the released portion, and call
-	 * free() on it.  Therefore, we can only shrink if the new
-	 * size is at least sizeof(struct __freelist) smaller than the
-	 * previous size.
-	 */
-	if (len <= fp1->sz) {
-		/* The first test catches a possible unsigned int
-		 * rollover condition. */
-		if (fp1->sz <= sizeof(struct __freelist) ||
-		    len > fp1->sz - sizeof(struct __freelist))
-			return ptr;
-		fp2 = (struct __freelist *)cp;
-		fp2->sz = fp1->sz - len - sizeof(size_t);
-		fp1->sz = len;
-		free(&(fp2->nx));
-		return ptr;
-	}
-
-	/*
-	 * If we get here, we are growing.  First, see whether there
-	 * is space in the free list on top of our current chunk.
-	 */
-	incr = len - fp1->sz;
-	cp = (char *)ptr + fp1->sz;
-	fp2 = (struct __freelist *)cp;
-	for (s = 0, ofp3 = 0, fp3 = __flp;
-	     fp3;
-	     ofp3 = fp3, fp3 = fp3->nx) {
-		if (fp3 == fp2 && fp3->sz + sizeof(size_t) >= incr) {
-			/* found something that fits */
-			if (fp3->sz + sizeof(size_t) - incr > sizeof(struct __freelist)) {
-				/* split off a new freelist entry */
-				cp = (char *)ptr + len;
-				fp2 = (struct __freelist *)cp;
-				fp2->nx = fp3->nx;
-				fp2->sz = fp3->sz - incr;
-				fp1->sz = len;
-			} else {
-				/* it just fits, so use it entirely */
-				fp1->sz += fp3->sz + sizeof(size_t);
-				fp2 = fp3->nx;
-			}
-			if (ofp3)
-				ofp3->nx = fp2;
-			else
-				__flp = fp2;
-			return ptr;
-		}
-		/*
-		 * Find the largest chunk on the freelist while
-		 * walking it.
-		 */
-		if (fp3->sz > s)
-			s = fp3->sz;
-	}
-	/*
-	 * If we are the topmost chunk in memory, and there was no
-	 * large enough chunk on the freelist that could be re-used
-	 * (by a call to malloc() below), quickly extend the
-	 * allocation area if possible, without need to copy the old
-	 * data.
-	 */
-	if (__brkval == (char *)ptr + fp1->sz && len > s) {
-		cp = (char *)ptr + len;
-		cp1 = STACK_POINTER() - __MALLOC_MARGIN__;
-		if (cp < cp1) {
-			__brkval = cp;
-			__brkval_maximum = cp;
-			fp1->sz = len;
-			return ptr;
-		}
-		/* If that failed, we are out of luck. */
-		return 0;
-	}
-
-	/*
-	 * Call malloc() for a new chunk, then copy over the data, and
-	 * release the old region.
-	 */
-	if ((memp = malloc(len)) == 0)
-		return 0;
-	memcpy(memp, ptr, fp1->sz);
-	free(ptr);
-	return memp;
-}
-
diff --git a/cores/arduino/avr-libc/realloc.c b/cores/arduino/avr-libc/realloc.c
new file mode 100644
index 0000000..b76ce56
--- /dev/null
+++ b/cores/arduino/avr-libc/realloc.c
@@ -0,0 +1,150 @@
+/* Copyright (c) 2004, 2010 Joerg Wunsch
+   All rights reserved.
+
+   Redistribution and use in source and binary forms, with or without
+   modification, are permitted provided that the following conditions are met:
+
+   * Redistributions of source code must retain the above copyright
+     notice, this list of conditions and the following disclaimer.
+
+   * Redistributions in binary form must reproduce the above copyright
+     notice, this list of conditions and the following disclaimer in
+     the documentation and/or other materials provided with the
+     distribution.
+
+   * Neither the name of the copyright holders nor the names of
+     contributors may be used to endorse or promote products derived
+     from this software without specific prior written permission.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+  POSSIBILITY OF SUCH DAMAGE.
+*/
+/* $Id: realloc.c 2127 2010-06-07 14:49:37Z joerg_wunsch $ */
+
+#include <stdlib.h>
+#include <string.h>
+#include "sectionname.h"
+#include "stdlib_private.h"
+
+#include <avr/io.h>
+
+ATTRIBUTE_CLIB_SECTION
+void *
+realloc(void *ptr, size_t len)
+{
+	struct __freelist *fp1, *fp2, *fp3, *ofp3;
+	char *cp, *cp1;
+	void *memp;
+	size_t s, incr;
+
+	/* Trivial case, required by C standard. */
+	if (ptr == 0)
+		return malloc(len);
+
+	cp1 = (char *)ptr;
+	cp1 -= sizeof(size_t);
+	fp1 = (struct __freelist *)cp1;
+
+	cp = (char *)ptr + len; /* new next pointer */
+	if (cp < cp1)
+		/* Pointer wrapped across top of RAM, fail. */
+		return 0;
+
+	/*
+	 * See whether we are growing or shrinking.  When shrinking,
+	 * we split off a chunk for the released portion, and call
+	 * free() on it.  Therefore, we can only shrink if the new
+	 * size is at least sizeof(struct __freelist) smaller than the
+	 * previous size.
+	 */
+	if (len <= fp1->sz) {
+		/* The first test catches a possible unsigned int
+		 * rollover condition. */
+		if (fp1->sz <= sizeof(struct __freelist) ||
+		    len > fp1->sz - sizeof(struct __freelist))
+			return ptr;
+		fp2 = (struct __freelist *)cp;
+		fp2->sz = fp1->sz - len - sizeof(size_t);
+		fp1->sz = len;
+		free(&(fp2->nx));
+		return ptr;
+	}
+
+	/*
+	 * If we get here, we are growing.  First, see whether there
+	 * is space in the free list on top of our current chunk.
+	 */
+	incr = len - fp1->sz;
+	cp = (char *)ptr + fp1->sz;
+	fp2 = (struct __freelist *)cp;
+	for (s = 0, ofp3 = 0, fp3 = __flp;
+	     fp3;
+	     ofp3 = fp3, fp3 = fp3->nx) {
+		if (fp3 == fp2 && fp3->sz + sizeof(size_t) >= incr) {
+			/* found something that fits */
+			if (fp3->sz + sizeof(size_t) - incr > sizeof(struct __freelist)) {
+				/* split off a new freelist entry */
+				cp = (char *)ptr + len;
+				fp2 = (struct __freelist *)cp;
+				fp2->nx = fp3->nx;
+				fp2->sz = fp3->sz - incr;
+				fp1->sz = len;
+			} else {
+				/* it just fits, so use it entirely */
+				fp1->sz += fp3->sz + sizeof(size_t);
+				fp2 = fp3->nx;
+			}
+			if (ofp3)
+				ofp3->nx = fp2;
+			else
+				__flp = fp2;
+			return ptr;
+		}
+		/*
+		 * Find the largest chunk on the freelist while
+		 * walking it.
+		 */
+		if (fp3->sz > s)
+			s = fp3->sz;
+	}
+	/*
+	 * If we are the topmost chunk in memory, and there was no
+	 * large enough chunk on the freelist that could be re-used
+	 * (by a call to malloc() below), quickly extend the
+	 * allocation area if possible, without need to copy the old
+	 * data.
+	 */
+	if (__brkval == (char *)ptr + fp1->sz && len > s) {
+		cp1 = __malloc_heap_end;
+		cp = (char *)ptr + len;
+		if (cp1 == 0)
+			cp1 = STACK_POINTER() - __malloc_margin;
+		if (cp < cp1) {
+			__brkval = cp;
+			fp1->sz = len;
+			return ptr;
+		}
+		/* If that failed, we are out of luck. */
+		return 0;
+	}
+
+	/*
+	 * Call malloc() for a new chunk, then copy over the data, and
+	 * release the old region.
+	 */
+	if ((memp = malloc(len)) == 0)
+		return 0;
+	memcpy(memp, ptr, fp1->sz);
+	free(ptr);
+	return memp;
+}
+
diff --git a/cores/arduino/avr-libc/sectionname.h b/cores/arduino/avr-libc/sectionname.h
new file mode 100644
index 0000000..8e0f448
--- /dev/null
+++ b/cores/arduino/avr-libc/sectionname.h
@@ -0,0 +1,49 @@
+/* Copyright (c) 2009 Atmel Corporation
+   All rights reserved.
+
+   Redistribution and use in source and binary forms, with or without
+   modification, are permitted provided that the following conditions are met:
+
+   * Redistributions of source code must retain the above copyright
+     notice, this list of conditions and the following disclaimer.
+
+   * Redistributions in binary form must reproduce the above copyright
+     notice, this list of conditions and the following disclaimer in
+     the documentation and/or other materials provided with the
+     distribution.
+
+   * Neither the name of the copyright holders nor the names of
+     contributors may be used to endorse or promote products derived
+     from this software without specific prior written permission.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+  POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef __SECTIONNAME_H__
+#define __SECTIONNAME_H__
+
+/* Put all avr-libc functions in a common, unique sub-section name under .text. */
+
+#define CLIB_SECTION    .text.avr-libc
+#define MLIB_SECTION    .text.avr-libc.fplib
+
+#define STR(x)   _STR(x)
+#define _STR(x)  #x
+
+#define ATTRIBUTE_CLIB_SECTION  __attribute__ ((section (STR(CLIB_SECTION))))
+#define ATTRIBUTE_MLIB_SECTION  __attribute__ ((section (STR(MLIB_SECTION))))
+
+#define ASSEMBLY_CLIB_SECTION   .section CLIB_SECTION, "ax", @progbits
+#define ASSEMBLY_MLIB_SECTION   .section MLIB_SECTION, "ax", @progbits
+
+#endif
diff --git a/cores/arduino/avr-libc/stdlib_private.h b/cores/arduino/avr-libc/stdlib_private.h
new file mode 100644
index 0000000..65c3427
--- /dev/null
+++ b/cores/arduino/avr-libc/stdlib_private.h
@@ -0,0 +1,58 @@
+/* Copyright (c) 2004, Joerg Wunsch
+   All rights reserved.
+
+   Redistribution and use in source and binary forms, with or without
+   modification, are permitted provided that the following conditions are met:
+
+   * Redistributions of source code must retain the above copyright
+     notice, this list of conditions and the following disclaimer.
+   * Redistributions in binary form must reproduce the above copyright
+     notice, this list of conditions and the following disclaimer in
+     the documentation and/or other materials provided with the
+     distribution.
+   * Neither the name of the copyright holders nor the names of
+     contributors may be used to endorse or promote products derived
+     from this software without specific prior written permission.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+  ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
+  LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+  POSSIBILITY OF SUCH DAMAGE.
+*/
+
+/* $Id: stdlib_private.h 1657 2008-03-24 17:11:08Z arcanum $ */
+
+#include <inttypes.h>
+#include <stdlib.h>
+#include <avr/io.h>
+
+#if !defined(__DOXYGEN__)
+
+struct __freelist {
+	size_t sz;
+	struct __freelist *nx;
+};
+
+#endif
+
+extern char *__brkval;		/* first location not yet allocated */
+extern struct __freelist *__flp; /* freelist pointer (head of freelist) */
+extern size_t __malloc_margin;	/* user-changeable before the first malloc() */
+extern char *__malloc_heap_start;
+extern char *__malloc_heap_end;
+
+extern char __heap_start;
+extern char __heap_end;
+
+/* Needed for definition of AVR_STACK_POINTER_REG. */
+#include <avr/io.h>
+
+#define STACK_POINTER() ((char *)AVR_STACK_POINTER_REG)
+