2004-07-23 Joerg Wunsch * doc/api/malloc.dox: Document realloc() internals. * include/stdlib.h: include realloc(). * libc/stdlib/Makefile.am: include realloc.c. * libc/stdlib/malloc.c: move out shared parts to stdlib_private.h. * libc/stdlib/stdlib_private.h: [new] shared file for malloc()/realloc(). * libc/stdlib/realloc.c: [new] implementation of realloc(). Index: doc/api/malloc.dox =================================================================== RCS file: /cvsroot/avr-libc/avr-libc/doc/api/malloc.dox,v retrieving revision 1.9 diff -u -r1.9 malloc.dox --- doc/api/malloc.dox 16 Nov 2002 21:05:17 -0000 1.9 +++ doc/api/malloc.dox 23 Jul 2004 11:28:40 -0000 @@ -209,4 +209,30 @@ allocations. That way, the potential for heap fragmentation is hopefully reduced. +A call to realloc() first determines whether the operation is about to +grow or shrink the current allocation. When shrinking, the case is +easy: the existing chunk is split, and the tail of the region that is +no longer to be used is passed to the standard free() function for +insertion into the freelist. Checks are first made whether the tail +chunk is large enough to hold a chunk of its own at all, otherwise +realloc() will simply do nothing, and return the original region. + +When growing the region, it is first checked whether the existing +allocation can be extended in-place. If so, this is done, and the +original pointer is returned without copying any data contents. As a +side-effect, this check will also record the size of the largest chunk +on the freelist. + +If the region cannot be extended in-place, but the old chunk is at the +top of heap, and the above freelist walk did not reveal a large enough +chunk on the freelist to satisfy the new request, an attempt is made +to quickly extend this topmost chunk (and thus the heap), so no need +arises to copy over the existing data. If there's no more space +available in the heap (same check is done as in malloc()), the entire +request will fail. + +Otherwise, malloc() will be called with the new request size, the +existing data will be copied over, and free() will be called on the +old region. + */ Index: include/stdlib.h =================================================================== RCS file: /cvsroot/avr-libc/avr-libc/include/stdlib.h,v retrieving revision 1.17 diff -u -r1.17 stdlib.h --- include/stdlib.h 5 Mar 2004 22:17:46 -0000 1.17 +++ include/stdlib.h 23 Jul 2004 11:28:41 -0000 @@ -1,4 +1,5 @@ /* Copyright (c) 2002, Marek Michalkiewicz + Copyright (c) 2004, Joerg Wunsch Portions of documentation Copyright (c) 1990, 1991, 1993, 1994 The Regents of the University of California. @@ -326,6 +327,25 @@ extern void *calloc(size_t __nele, size_t __size) __ATTR_MALLOC__; /** + The realloc() function tries to change the size of the region + allocated at \c ptr to the new \c size value. It returns a + pointer to the new region. The returned pointer might be the + same as the old pointer, or a pointer to a completely different + region. + + The contents of the returned region up to either the old or the new + size value (whatever is less) will be identical to the contents of + the old region, even in case a new region had to be allocated. + + It is acceptable to pass \c ptr as NULL, in which case realloc() + will behave identical to malloc(). + + If the new memory cannot be allocated, realloc() returns NULL, and + the region at \c ptr will not be changed. +*/ +extern void *realloc(void *__ptr, size_t __size) __ATTR_MALLOC__; + +/** The strtod() function converts the initial portion of the string pointed to by \c nptr to double representation. Index: libc/stdlib/Makefile.am =================================================================== RCS file: /cvsroot/avr-libc/avr-libc/libc/stdlib/Makefile.am,v retrieving revision 1.3 diff -u -r1.3 Makefile.am --- libc/stdlib/Makefile.am 17 Oct 2002 09:16:56 -0000 1.3 +++ libc/stdlib/Makefile.am 23 Jul 2004 11:28:41 -0000 @@ -40,6 +40,7 @@ qsort.c \ rand.c \ random.c \ + realloc.c \ strtol.c \ strtoul.c Index: libc/stdlib/malloc.c =================================================================== RCS file: /cvsroot/avr-libc/avr-libc/libc/stdlib/malloc.c,v retrieving revision 1.8 diff -u -r1.8 malloc.c --- libc/stdlib/malloc.c 15 Feb 2004 19:44:45 -0000 1.8 +++ libc/stdlib/malloc.c 23 Jul 2004 11:28:41 -0000 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2002 Joerg Wunsch + * Copyright (c) 2002, 2004 Joerg Wunsch * * All rights reserved. * @@ -28,53 +28,12 @@ #include -#include - -#ifndef __AVR__ - -/* - * When compiling this file natively on a host machine, it will - * include a main() that performs a regression test. This is meant as - * a debugging aid, where a normal source-level debugger will help to - * verify that the various allocator structures have the desired - * appearance at each stage. - * - * When cross-compiling with avr-gcc, it will compile into just the - * library functions malloc() and free(). - */ -#define MALLOC_TEST - -#endif /* !__AVR__ */ - -#if !defined(DOXYGEN) - -struct freelist { - size_t sz; - struct freelist *nx; -}; - -#endif /* not DOXYGEN */ - -static char *brkval; -static struct freelist *flp; +#include "stdlib_private.h" #ifdef MALLOC_TEST - -#define malloc mymalloc -#define free myfree -#define __heap_start mymem -#define __heap_end ((char *)0) - char mymem[256]; -#define STACK_POINTER() (mymem + 256) - -#else /* !MALLOC_TEST */ - -extern char __heap_start; -extern char __heap_end; - -#define STACK_POINTER() ((char *)SP) - +#else +#include #endif /* MALLOC_TEST */ /* @@ -94,10 +53,13 @@ char *__malloc_heap_start = &__heap_start; char *__malloc_heap_end = &__heap_end; +char *__brkval; +struct __freelist *__flp; + void * malloc(size_t len) { - struct freelist *fp1, *fp2; + struct __freelist *fp1, *fp2; char *cp; size_t s, avail; @@ -107,8 +69,8 @@ * this), otherwise we could not possibly fit a freelist entry * into the chunk later. */ - if (len < sizeof(struct freelist) - sizeof(size_t)) - len = sizeof(struct freelist) - sizeof(size_t); + if (len < sizeof(struct __freelist) - sizeof(size_t)) + len = sizeof(struct __freelist) - sizeof(size_t); /* * First, walk the free list and try finding a chunk that @@ -117,7 +79,7 @@ * that would still fit the request -- we need it for step 2. * */ - for (s = 0, fp1 = flp, fp2 = 0; + for (s = 0, fp1 = __flp, fp2 = 0; fp1; fp2 = fp1, fp1 = fp1->nx) { if (fp1->sz == len) { @@ -128,7 +90,7 @@ if (fp2) fp2->nx = fp1->nx; else - flp = fp1->nx; + __flp = fp1->nx; return &(fp1->nx); } if (fp1->sz > len) { @@ -147,9 +109,9 @@ * and use the entire chunk. */ if (s) { - if (s - len < sizeof(struct freelist)) + if (s - len < sizeof(struct __freelist)) len = s; - for (fp1 = flp, fp2 = 0; + for (fp1 = __flp, fp2 = 0; fp1; fp2 = fp1, fp1 = fp1->nx) { if (fp1->sz == s) { @@ -161,7 +123,7 @@ if (fp2) fp2->nx = fp1->nx; else - flp = fp1->nx; + __flp = fp1->nx; return &(fp1->nx); } /* @@ -179,7 +141,7 @@ cp = (char *)fp1; s -= len; cp += s; - fp2 = (struct freelist *)cp; + fp2 = (struct __freelist *)cp; fp2->sz = len; fp1->sz = s - sizeof(size_t); return &(fp2->nx); @@ -196,18 +158,18 @@ * Since we don't have an operating system, just make sure * that we don't collide with the stack. */ - if (brkval == 0) - brkval = __malloc_heap_start; + if (__brkval == 0) + __brkval = __malloc_heap_start; cp = __malloc_heap_end; if (cp == 0) cp = STACK_POINTER() - __malloc_margin; - avail = cp - brkval; + avail = cp - __brkval; /* * Both tests below are needed to catch the case len >= 0xfffe. */ if (avail >= len && avail >= len + sizeof(size_t)) { - fp1 = (struct freelist *)brkval; - brkval += len + sizeof(size_t); + fp1 = (struct freelist *)__brkval; + __brkval += len + sizeof(size_t); fp1->sz = len; return &(fp1->nx); } @@ -220,7 +182,7 @@ void free(void *p) { - struct freelist *fp1, *fp2, *fpnew; + struct __freelist *fp1, *fp2, *fpnew; char *cp1, *cp2, *cpnew; /* ISO C says free(NULL) must be a no-op */ @@ -229,15 +191,15 @@ cpnew = p; cpnew -= sizeof(size_t); - fpnew = (struct freelist *)cpnew; + fpnew = (struct __freelist *)cpnew; fpnew->nx = 0; /* * Trivial case first: if there's no freelist yet, our entry * will be the only one on it. */ - if (flp == 0) { - flp = fpnew; + if (__flp == 0) { + __flp = fpnew; return; } @@ -246,7 +208,7 @@ * freelist. Try to aggregate the chunk with adjacent chunks * if possible. */ - for (fp1 = flp, fp2 = 0; + for (fp1 = __flp, fp2 = 0; fp1; fp2 = fp1, fp1 = fp1->nx) { if (fp1 < fpnew) @@ -260,7 +222,7 @@ } if (fp2 == 0) { /* new head of freelist */ - flp = fpnew; + __flp = fpnew; return; } break; @@ -283,6 +245,7 @@ #ifdef MALLOC_TEST #include +#include #include #include @@ -304,15 +267,15 @@ void printfreelist(void) { - struct freelist *fp1; + struct __freelist *fp1; int i; - if (!flp) { + if (!__flp) { printf("no free list\n"); return; } - for (i = 0, fp1 = flp; fp1; i++, fp1 = fp1->nx) { + for (i = 0, fp1 = __flp; fp1; i++, fp1 = fp1->nx) { printf("entry %d @ %u: size %u, next ", i, (char *)fp1 - mymem, fp1->sz); if (fp1->nx) @@ -331,10 +294,11 @@ void printalloc(void) { - int i, j, k; + int j, k; + size_t i; size_t sum, sum2; void *sortedhandles[32]; - struct freelist *fp; + struct __freelist *fp; char *cp; for (i = j = k = sum = sum2 = 0; @@ -350,13 +314,13 @@ } printf("brkval: %d, %d request%s => sum %u bytes " "(actually %d reqs => %u bytes)\n", - (char *)brkval - mymem, j, j == 1? "": "s", sum, k, sum2); + (char *)__brkval - mymem, j, j == 1? "": "s", sum, k, sum2); memcpy(sortedhandles, handles, sizeof sortedhandles); qsort(sortedhandles, 32, sizeof(void *), compare); for (i = j = 0; i < sizeof sortedhandles / sizeof (void *); i++) if ((cp = sortedhandles[i])) { cp -= sizeof(size_t); - fp = (struct freelist *)cp; + fp = (struct __freelist *)cp; printf("block %d @ %u: %u bytes\n", j, (char *)&fp->nx - mymem, fp->sz); j++; @@ -389,7 +353,7 @@ for (i = s = 0; i < j; i++) if (handles[i]) s++; - if (s == j) + if (s == (unsigned)j) break; if (m / om > 10) { --- /dev/null Fri Jul 23 13:33:00 2004 +++ libc/stdlib/stdlib_private.h Wed Jan 7 13:44:57 2004 @@ -0,0 +1,88 @@ +/* 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$ */ + +#include +#include + +#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; + +#ifndef __AVR__ + +/* + * When compiling malloc.c/realloc.c natively on a host machine, it will + * include a main() that performs a regression test. This is meant as + * a debugging aid, where a normal source-level debugger will help to + * verify that the various allocator structures have the desired + * appearance at each stage. + * + * When cross-compiling with avr-gcc, it will compile into just the + * library functions malloc() and free(). + */ +#define MALLOC_TEST + +#endif /* !__AVR__ */ + +#ifdef MALLOC_TEST + +extern void *mymalloc(size_t); +extern void myfree(void *); +extern void *myrealloc(void *, size_t); + +#define malloc mymalloc +#define free myfree +#define realloc myrealloc + +#define __heap_start mymem[0] +#define __heap_end mymem[256] +extern char mymem[]; +#define STACK_POINTER() (mymem + 256) + +#else /* !MALLOC_TEST */ + +extern char __heap_start; +extern char __heap_end; + +#define STACK_POINTER() ((char *)SP) + +#endif /* MALLOC_TEST */ --- /dev/null Fri Jul 23 13:33:00 2004 +++ libc/stdlib/realloc.c Wed Jan 7 14:09:17 2004 @@ -0,0 +1,149 @@ +/* + * 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: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. 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. + * + * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``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 DEVELOPERS 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$ + */ + +#include +#include + +#include "stdlib_private.h" + +#ifndef MALLOC_TEST +#include +#endif + +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); + + cp = (char *)ptr; + cp -= sizeof(size_t); + fp1 = (struct __freelist *)cp; + + cp = (char *)ptr + len; /* new next pointer */ + fp2 = (struct __freelist *)cp; + + /* + * 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->sz = fp1->sz - len - sizeof(size_t); + fp2->nx = fp1->nx; + fp1->sz = len; + fp1->nx = fp2; + 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 - sizeof(size_t); + 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 >= incr) { + /* found something that fits */ + if (incr <= fp3->sz && + incr > fp3->sz - sizeof(struct __freelist)) { + /* it just fits, so use it entirely */ + fp1->sz += fp3->sz + sizeof(size_t); + if (ofp3) + ofp3->nx = fp3->nx; + else + __flp = fp3->nx; + return ptr; + } + /* split off a new freelist entry */ + cp = (char *)ptr + len; + fp2 = (struct __freelist *)cp; + fp2->nx = fp3->nx; + fp2->sz = fp3->sz - incr - sizeof(size_t); + if (ofp3) + ofp3->nx = fp2; + else + __flp = fp2; + fp1->sz = len; + 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; + 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; +} +