From 1847b4437363398e4d53b192161375212d9ef90b Mon Sep 17 00:00:00 2001 From: Alan Cox Date: Fri, 17 Jun 2016 12:56:07 +0100 Subject: [PATCH] libc: replace malloc() with a classic K&R style malloc algorithm Shorter, simpler and neater. Hopefully correct (or it'll be fun debugging all the app crashes ;-)). realloc would benefit from being smart about using the adjacent buffers to grow rather than the dumb free/alloc approach. Alan --- Library/libs/calloc.c | 31 ++-- Library/libs/error.c | 5 +- Library/libs/free.c | 182 ++++----------------- Library/libs/malloc-l.h | 65 -------- Library/libs/malloc.c | 342 ++++++++-------------------------------- Library/libs/realloc.c | 72 ++++++--- 6 files changed, 172 insertions(+), 525 deletions(-) delete mode 100644 Library/libs/malloc-l.h diff --git a/Library/libs/calloc.c b/Library/libs/calloc.c index 05bc1bad..9d4d2910 100644 --- a/Library/libs/calloc.c +++ b/Library/libs/calloc.c @@ -1,19 +1,20 @@ -/* Copyright (C) 1995,1996 Robert de Bath - * This file is part of the Linux-8086 C library and is distributed - * under the GNU Library General Public License. - * - * This is a combined alloca/malloc package. It uses a classic algorithm - * and so may be seen to be quite slow compared to more modern routines - * with 'nasty' distributions. - */ - -#include "malloc-l.h" - -void *calloc(size_t elm, size_t sz) +/* Copyright (C) 1995,1996 Robert de Bath + * This file is part of the Linux-8086 C library and is distributed + * under the GNU Library General Public License. + * + * Kept from the old malloc package. + */ + +#include +#include +#include + +void *calloc(size_t elm, size_t sz) { - register size_t v = elm * sz; - register void *ptr = malloc(v); - + /* FIXME: a modern calloc should probably trap overflows and NULL */ + size_t v = elm * sz; + void *ptr = malloc(v); + if (ptr) memset(ptr, 0, v); return ptr; diff --git a/Library/libs/error.c b/Library/libs/error.c index e3281f3f..a71a25a7 100644 --- a/Library/libs/error.c +++ b/Library/libs/error.c @@ -11,13 +11,16 @@ #include #include #include -#include "malloc-l.h" static uint8_t *__sys_errlist; static uint16_t *__sys_errptr; static int __sys_nerr; static char retbuf[80]; +#define ALIGNMENT 16 + +#define ALIGNUP(s) (((s) + ALIGNMENT - 1) & ~(ALIGNMENT - 1)) + static void _load_errlist(void) { struct stat st; diff --git a/Library/libs/free.c b/Library/libs/free.c index 021868a5..51b7e805 100644 --- a/Library/libs/free.c +++ b/Library/libs/free.c @@ -1,155 +1,41 @@ -/* Copyright (C) 1995,1996 Robert de Bath - * This file is part of the Linux-8086 C library and is distributed - * under the GNU Library General Public License. - * - * This is a combined alloca/malloc package. It uses a classic algorithm - * and so may be seen to be quite slow compared to more modern routines - * with 'nasty' distributions. +/* + * This is an ANSI C version of the classic K & R memory allocator. The only + * real difference here is that we handle large allocations and signs correctly + * which the original didn't do portably. Specifically we + * - correctly handle signed sbrk when the largest allocation allowed is + * unsigned + * - catch the case of a malloc close to the full size_t overflowing in the + * nblock computation. */ -#include "malloc-l.h" - -/* Start the alloca with just the dumb version of malloc */ -void *(*__alloca_alloc) __P((size_t)) = __mini_malloc; - -/* the free list is a single list of free blocks. __freed_list points to - the highest block (highest address) and each block points to the lower - block (lower address). last block points to 0 (initial value of - _freed_list) -*/ -mem *__freed_list = 0; - -#ifdef VERBOSE -/* NB: Careful here, stdio may use malloc - so we can't */ -#include #include -#include -static void pstr __P((char *)); -static void phex __P((unsigned)); -static void noise __P((char *, mem *)); -static void pstr(char *str) -{ - write(2, str, strlen(str)); -} static void phex(unsigned val) -{ - char buf[8]; - strcpy(buf, "000"); - ltoa((long) val, buf + 3, 16); - pstr(buf + strlen(buf + 4)); -} void __noise(char *y, mem * x) -{ - pstr("Malloc "); - phex((unsigned) x); - pstr(" sz "); - phex(x ? (unsigned) m_size(x) : 0); - pstr(" nxt "); - phex(x ? (unsigned) m_next(x) : 0); - pstr(" is "); - pstr(y); - pstr("\n"); -} -#endif /* */ -void free(void *ptr) -{ - register mem *top, *chk = (mem *) ptr; - if (chk == 0) - return; /* free(NULL) - be nice */ - chk--; - try_this:; - top = (mem *) sbrk(0); - if (m_add(chk, m_size(chk)) >= top) { - noise("FREE brk", chk); - brk((void *) ((uchar *) top - m_size(chk))); - - /* Adding this code allow free to release blocks in any order; - * they can still only be allocated from the top of the heap - * tho. - */ -#ifdef __MINI_MALLOC__ - /* FIXME: void * cast appears to be a cc65 bug */ - if (__alloca_alloc == (void *)__mini_malloc && __freed_list) { - chk = __freed_list; - __freed_list = m_next(__freed_list); - goto try_this; - } -#endif /* */ - } - - else { /* Nope, not sure where this goes, leave it for malloc to deal with */ - -#ifdef __MINI_MALLOC__ - /* check if block is already on free list. - if it is, return without doing nothing */ - top = __freed_list; - while (top) { - if (top == chk) - return; - top = m_next(top); - } - - /* else add it to free list */ - if (!__freed_list || chk > __freed_list) { - - /* null free list or block above free list */ - m_next(chk) = __freed_list; - __freed_list = chk; - } - - else { - - /* insert block in free list, ordered by address */ - register mem *prev = __freed_list; - top = __freed_list; - while (top && top > chk) { - prev = top; - top = m_next(top); - } - m_next(chk) = top; - m_next(prev) = chk; - } - -#else /* */ - m_next(chk) = __freed_list; - __freed_list = chk; - -#endif /* */ - noise("ADD LIST", chk); - } -} +#include +#include +#include "malloc.h" -void *__mini_malloc(size_t size) +void free(void *ptr) { - register mem *ptr; - register unsigned int sz; - - /* First time round this _might_ be odd, But we won't do that! */ -#if 0 - sz = (unsigned int) sbrk(0); - if (sz & (sizeof(struct mem_cell) - 1)) { - if (sbrk - (sizeof(struct mem_cell) - - (sz & (sizeof(struct mem_cell) - 1))) < 0) - goto nomem; - } -#endif /* */ - if (size == 0) - return 0; - - /* Ensure size is aligned, otherwise our memory nodes become unaligned - * and we get hard-to-debug errors on platforms which require - * aligned accesses. */ - size = ALIGNUP(size + sizeof(struct mem_cell)); - - /* Minor oops here, sbrk has a signed argument */ - if (size > (((unsigned) -1) >> 1) - sizeof(struct mem_cell) * 2) { - nomem:errno = ENOMEM; - return 0; + struct memh *mh = MH(ptr), *p; + + if (ptr == NULL) + return; + + /* Find the free list block that is just before us */ + for (p = __mfreeptr; !(p < mh && mh < p->next); p = p->next) + if (p >= p->next && (p < mh || mh < p->next)) + break; + /* Fix up and if we can merge forward */ + if (mh + mh->size == p->next) { + mh->size += p->next->size; + mh->next = p->next->next; + } else + mh->next = p->next; + /* Ditto backwards */ + if (p + p->size == mh) { + p->size += mh->size; + p->next = mh->next; + } else { + p->next = mh; } - size += sizeof(struct mem_cell); /* Round up and leave space for size field */ - ptr = (mem *) sbrk(size); - if ((int) ptr == -1) - return 0; - m_size(ptr) = size; - noise("CREATE", ptr); - return ptr + 1; + __mfreeptr = p; } diff --git a/Library/libs/malloc-l.h b/Library/libs/malloc-l.h deleted file mode 100644 index b8af5131..00000000 --- a/Library/libs/malloc-l.h +++ /dev/null @@ -1,65 +0,0 @@ -/* Copyright (C) 1995,1996 Robert de Bath - * This file is part of the Linux-8086 C library and is distributed - * under the GNU Library General Public License. - * - * This is a combined alloca/malloc package. It uses a classic algorithm - * and so may be seen to be quite slow compared to more modern routines - * with 'nasty' distributions. - */ -#include -#include -#include -#include -#include - -#define __MINI_MALLOC__ - -union maximally_aligned { - uint8_t b; - uint16_t s; - uint32_t i; - #if !defined(NO_64BIT) - uint64_t l; - #endif - float f; - double d; -}; - -struct malloc_alignment_tester -{ - char b; - union maximally_aligned u; -}; - -#define ALIGNMENT ((int)&(((struct malloc_alignment_tester*)NULL)->u)) -#define ALIGNUP(s) (((s) + ALIGNMENT - 1) & ~(ALIGNMENT - 1)) - -#define MCHUNK 512 /* Allocation unit in 'mem' elements */ -#undef LAZY_FREE /* If set frees can be infinitly defered */ -#undef MINALLOC /* 32 */ /* Smallest chunk to alloc in 'mem's */ -#undef VERBOSE /* Lots of noise, debuging ? */ - -#undef malloc -#define MAX_INT ((int)(((unsigned)-1)>>1)) - -#ifdef VERBOSE -#define noise __noise -#else -#define noise(y,x) -#endif - -typedef struct mem_cell { - struct mem_cell *next; /* A pointer to the next mem */ - unsigned int size; /* An int >= sizeof pointer */ - char *depth; /* For the alloca hack */ - union maximally_aligned padding[0]; /* Ensures alignment of payload */ -} mem; - -#define m_size(p) ((p)[0].size) /* For malloc */ -#define m_next(p) ((p)[0].next) /* For malloc and alloca */ -#define m_deep(p) ((p)[0].depth) /* For alloca */ -#define m_add(x,y) (mem *)((uchar *)x + y) /* Sum mem* with y bytes */ - -extern void *__mini_malloc __P((size_t)); -extern void *(*__alloca_alloc) __P((size_t)); -extern mem *__freed_list; diff --git a/Library/libs/malloc.c b/Library/libs/malloc.c index 72b6a7d9..abe00a49 100644 --- a/Library/libs/malloc.c +++ b/Library/libs/malloc.c @@ -1,285 +1,83 @@ -/* Copyright (C) 1995,1996 Robert de Bath - * This file is part of the Linux-8086 C library and is distributed - * under the GNU Library General Public License. - * - * This is a combined alloca/malloc package. It uses a classic algorithm - * and so may be seen to be quite slow compared to more modern routines - * with 'nasty' distributions. +/* + * This is an ANSI C version of the classic K & R memory allocator. The only + * real difference here is that we handle large allocations and signs correctly + * which the original didn't do portably. Specifically we + * - correctly handle signed sbrk when the largest allocation allowed is + * unsigned + * - catch the case of a malloc close to the full size_t overflowing in the + * nblock computation. */ -#include "malloc-l.h" +#include +#include +#include +#include "malloc.h" -/* The chunk_list pointer is either NULL or points to a chunk in a - * circular list of all the free blocks in memory - */ - -#define Static static -static mem *chunk_list = 0; -Static mem *__search_chunk __P((unsigned)); -Static void __insert_chunk __P((mem *)); -void *malloc(size_t size) -{ - register unsigned sz; - register mem *ptr = 0; - if (size == 0) - return 0; /* ANSI STD */ - - /* Ensure the size is aligned, otherwise our memory nodes become unaligned - * and we get hard-to-debug errors on platforms which require aligned - * accesses. */ - sz = ALIGNUP(size + sizeof(struct mem_cell)); - -#ifdef MINALLOC - if (sz < MINALLOC) - sz = MINALLOC; - -#endif /* */ -#ifdef VERBOSE - { - static mem arr[2]; - m_size(arr) = sz; - noise("WANTED", arr); - } -#endif /* */ - __alloca_alloc = malloc; /* We'll be messing with the heap now TVM */ +struct memh __mroot = { &__mroot, 0 }; -#ifdef LAZY_FREE - ptr = __search_chunk(sz); - if (ptr == 0) { - -#endif /* */ - /* First deal with the freed list */ - if (__freed_list) { - while (__freed_list) { - ptr = __freed_list; - __freed_list = m_next(__freed_list); - if (m_size(ptr) == sz) { - - /* Oh! Well that's lucky ain't it :-) */ - noise("LUCKY MALLOC", ptr); - return ptr + 1; - } - __insert_chunk(ptr); - } - ptr = m_next(chunk_list); - if (ptr + m_size(ptr) >= (void *) sbrk(0)) { - - /* Time to free for real */ - m_next(chunk_list) = m_next(ptr); - if (ptr == m_next(ptr)) - chunk_list = 0; - free(ptr + 1); - } -#ifdef LAZY_FREE - ptr = __search_chunk(sz); - -#endif /* */ - } -#ifndef LAZY_FREE - ptr = __search_chunk(sz); +struct memh *__mfreeptr = &__mroot; -#endif /* */ - if (ptr == 0) { - -#ifdef MCHUNK - unsigned int alloc = - (MCHUNK * ((sz + MCHUNK - 1) / MCHUNK) - 1); - if ((ptr = __mini_malloc(alloc)) != NULL) - __insert_chunk(ptr - 1); - - else { /* Oooo, near end of RAM */ - unsigned int needed = alloc; - alloc /= 2; - while (alloc > 256 && needed) { - ptr = __mini_malloc(alloc); - if (ptr) { - if (alloc > needed) - needed = 0; - - else - needed -= alloc; - __insert_chunk(ptr - 1); - } - - else - alloc /= 2; - } - } - ptr = __search_chunk(sz); - if (ptr == 0) -#endif /* */ - { - -#ifndef MCHUNK - ptr = __mini_malloc(size); - -#endif /* */ -#ifdef VERBOSE - if (ptr == 0) - noise("MALLOC FAIL", 0); - - else - noise("MALLOC NOW", ptr - 1); - -#endif /* */ - return ptr; - } - } -#ifdef LAZY_FREE - } -#endif /* */ -#ifdef VERBOSE - ptr[1].size = 0x5555; - -#endif /* */ - noise("MALLOC RET\n", ptr); - return ptr + 1; +static struct memh *brkmore(size_t nb) +{ + struct memh *p; + + if (nb < BRKSIZE) + nb = BRKSIZE; + + /* Here be dragons: sbrk takes a signed value. We can however in C malloc + a size_t: We also assume nobody else misaligns the brk boundary, we won't + fix it if so - maybe we should ? */ + + /* Current end of memory */ + p = sbrk(0); + if (p == (struct memh *) -1) + return NULL; + /* Overflow catch */ + if (p + nb < p) + return NULL; + /* Move our break point. Using brk this way avoids the sign problems */ + if (brk(p + nb)) + return NULL; + /* Fake it as a used block and free it into the free list */ + p->size = nb; + free(p + 1); + return __mfreeptr; } - -/* This function takes a pointer to a block of memory and inserts it into - * the chain of memory chunks - */ -Static void __insert_chunk(mem * mem_chunk) +void *malloc(size_t size) { - register mem *p1, *p2; - if (chunk_list == 0) { /* Simple case first */ - m_next(mem_chunk) = chunk_list = mem_chunk; - noise("FIRST CHUNK", mem_chunk); - return; - } - p1 = mem_chunk; - p2 = chunk_list; - - do { - if (p1 > p2) { - - /* We're at the top of the chain, p1 is higher */ - if (m_next(p2) <= p2) { - if (m_add(p2, m_size(p2)) == p1) { - - /* Good, stick 'em together */ - noise("INSERT CHUNK", mem_chunk); - m_size(p2) += m_size(p1); - noise("JOIN 1", p2); - } - - else { - m_next(p1) = m_next(p2); - m_next(p2) = p1; - noise("INSERT CHUNK", mem_chunk); - noise("FROM", p2); - } - return; - } - if (m_next(p2) > p1) { - - /* In chain, p1 between p2 and next */ - m_next(p1) = m_next(p2); - m_next(p2) = p1; - noise("INSERT CHUNK", mem_chunk); - noise("FROM", p2); - - /* Try to join above */ - if (m_add(p1, m_size(p1)) == m_next(p1)) { - m_size(p1) += m_size(m_next(p1)); - m_next(p1) = m_next(m_next(p1)); - noise("JOIN 2", p1); - } - - /* Try to join below */ - if (m_add(p2, m_size(p2)) == p1) { - m_size(p2) += m_size(p1); - m_next(p2) = m_next(p1); - noise("JOIN 3", p2); - } - chunk_list = p2; /* Make sure it's valid */ - return; + struct memh *p, *prev; + size_t nblocks; + + nblocks = size + sizeof(struct memh) + sizeof(struct memh) - 1; + /* Cheap way to catch overflow */ + if (nblocks < size) + return NULL; + nblocks /= sizeof(struct memh); + + prev = __mfreeptr; + + for (p = prev->next;; prev = p, p = p->next) { + if (p->size >= nblocks) { + if (p->size == nblocks) + /* We found a hole the right size so unlink it */ + prev->next = p->next; + else { + /* Split a hole */ + p->size -= nblocks; + /* Move down the block and hand the end of it to the user, to avoid + having to move the links. Our realloc depends upon this */ + p += p->size; + p->size = nblocks; } + /* Ensure its a valid start point and optimal for malloc(x)/free(x) */ + __mfreeptr = prev; + return (void *) (p + 1); } - - else if (p1 < p2) { - if (m_next(p2) <= p2 && p1 < m_next(p2)) { - - /* At top of chain, next is bottom of chain, - * p1 is below next - */ - m_next(p1) = m_next(p2); - m_next(p2) = p1; - noise("INSERT CHUNK", mem_chunk); - noise("FROM", p2); - chunk_list = p2; - if (m_add(p1, m_size(p1)) == m_next(p1)) { - if (p2 == m_next(p1)) - chunk_list = p1; - m_size(p1) += m_size(m_next(p1)); - m_next(p1) = m_next(m_next(p1)); - noise("JOIN 4", p1); - } - return; - } + /* We've done one orbit.. */ + if (p == __mfreeptr) { + if ((p = brkmore(nblocks)) == NULL) + return NULL; } - chunk_list = p2; /* Save for search */ - p2 = m_next(p2); - } while (p2 != chunk_list); - - /* If we get here we have a problem, ignore it, maybe it'll go away */ - noise("DROPPED CHUNK", mem_chunk); -} - - -/* This function will search for a chunk in memory of at least 'mem_size' - * when found, if the chunk is too big it'll be split, and pointer to the - * chunk returned. If none is found NULL is returned. - */ -Static mem *__search_chunk(unsigned mem_size) -{ - register mem *p1, *p2; - if (chunk_list == 0) /* Simple case first */ - return 0; - - /* Search for a block >= the size we want */ - p1 = m_next(chunk_list); - p2 = chunk_list; - - do { - noise("CHECKED", p1); - if (m_size(p1) >= mem_size) - break; - p2 = p1; - p1 = m_next(p1); - } while (p2 != chunk_list); - - /* None found, exit */ - if (m_size(p1) < mem_size) - return 0; - - /* If it's exactly right remove it */ - if (m_size(p1) < mem_size + 2) { - noise("FOUND RIGHT", p1); - chunk_list = m_next(p2) = m_next(p1); - if (chunk_list == p1) - chunk_list = 0; - return p1; } - noise("SPLIT", p1); - - /* Otherwise split it */ - m_next(p2) = m_add(p1, mem_size); - chunk_list = p2; - p2 = m_next(p2); - m_size(p2) = m_size(p1) - mem_size; - m_next(p2) = m_next(p1); - m_size(p1) = mem_size; - if (chunk_list == p1) - chunk_list = p2; - -#ifdef VERBOSE - p1[1].size = 0xAAAA; - -#endif /* */ - noise("INSERT CHUNK", p2); - noise("FOUND CHUNK", p1); - noise("LIST IS", chunk_list); - return p1; } diff --git a/Library/libs/realloc.c b/Library/libs/realloc.c index f9f0a973..ae97dd06 100644 --- a/Library/libs/realloc.c +++ b/Library/libs/realloc.c @@ -1,29 +1,53 @@ -/* Copyright (C) 1995,1996 Robert de Bath - * This file is part of the Linux-8086 C library and is distributed - * under the GNU Library General Public License. - * - * This is a combined alloca/malloc package. It uses a classic algorithm - * and so may be seen to be quite slow compared to more modern routines - * with 'nasty' distributions. - */ - -#include "malloc-l.h" - -void *realloc(void *ptr, size_t size) +/* + * This is an ANSI C version of the classic K & R memory allocator. The only + * real difference here is that we handle large allocations and signs correctly + * which the original didn't do portably. Specifically we + * - correctly handle signed sbrk when the largest allocation allowed is + * unsigned + * - catch the case of a malloc close to the full size_t overflowing in the + * nblock computation. + */ + +#include +#include +#include +#include +#include "malloc.h" + +/* + * We cannot just free/malloc because there is a pathalogical case when we free + * a block which is merged with the block before and then we allocate some of the + * combined block. In that case we will a new header into the middle of the user + * bytes. + */ +void *realloc(void *ptr, size_t size) { - void *nptr; - unsigned int osize; - if (ptr == 0) + struct memh *mh = MH(ptr); + void *np; + size_t nblocks; + + if (size == 0) { + free(ptr); + return NULL; + } + + if (ptr == NULL) return malloc(size); - - /* ??? what if I really want to free rest of block ? */ - if (size <= (osize = (m_size(((mem *) ptr) - 1) - 1) * sizeof(mem))) + + nblocks = + (size + sizeof(struct memh) + sizeof(struct memh) - + 1) / sizeof(struct memh); + + /* If size in mem blocks is sufficiently similar (make this fuzzier ?) */ + if (nblocks == mh->size) + return ptr; + + if (nblocks < mh->size) return ptr; - if ((nptr = malloc(size)) == NULL) - return 0; - memcpy(nptr, ptr, osize); + np = malloc(size); + if (np == NULL) + return ptr; + memcpy(np, ptr, mh->size * sizeof(struct memh)); free(ptr); - return nptr; + return np; } - - -- 2.34.1