Mail Archives: djgpp-workers/2002/02/27/16:32:13
Eli Zaretskii wrote:
>
> On Tue, 26 Feb 2002, CBFalconer wrote:
>
> > If the look is that cursory it is not worth-while to me. I posted
> > the basic structure some time ago and got comments on that.
>
> It is still advisable to post code as plain text here, because more
> people will have a look at and comment on it. If it's too large for
> that, you could make the full zip available for download somewhere,
> and post just the main parts, for example.
Ok, here is the main thing, 592 lines. realloc has not yet been
implemented. I think malloc and free are correct. This doesn't
give people the makefile, headers, test routines, etc. It has
always been compiled with "/Dinline= -W -Wall" switches.
The fakesbrk routine in the tester does not return consistent
addresses, so I can't have easy regression tests. Thus this is
primarily for reading.
Pasted as quote to prevent line wrapping.
> /* --------- nmalloc.c ----------- */
>
> /* Copyright (C) 2002 C.B. Falconer, see COPYING.DJ for details */
> /* This is intended to be licensed under the GNU Library license */
> /* with the proviso that the above copyright be retained. */
> /* A re-implementation of malloc and friends for DJGPP 2.03 */
> /* This includes many bits modeled after DJs original scheme. */
> /* This is NOT portable - it builds in knowledge of int size etc. */
> /* i.e. unsigned ints and pointers are both 32 bits (size 4) */
>
> #ifndef NDEBUG
> # define DEBUGM 1 /* malloc */
> # define DEBUGF 1 /* free */
> # define DEBUGR 1 /* realloc */
> #endif
>
> #include <stddef.h> /* offsetof() */
> #include <stdlib.h>
> #include <unistd.h> /* sbrk */
> #include <assert.h> /* goes away with NDEBUG */
>
> /* Incorporation into the system should require deleting the
> following <nmalloc.h>, changing all references to nmalloc
> to malloc, nfree to free, nrealloc to realloc. Change the
> single call to fakesbrk to sbrk. Change the source file
> name from nmalloc.c to malloc.c. Also normally set all
> DEBUGx values above to 0 in place of 1. Later many
> routines will be made inline. For debugging compilations
> are done with "/Dinline= " switch. For production use
> the "/DNDEBUG=1" switch.
> */
> #ifndef NDEBUG
> # include "nmalloc.h" /* while testing before name changes */
> #endif
>
> /* Macros and storage for debugging, works before init on DJGPP */
> /* WARNING - GNU extensions used here!! */
> #if DEBUGM || DEBUGF || DEBUGR
> # include <stdio.h> /* sprintf, write for DEBUG only */
> # include <string.h> /* strlen */
> # include "fakesbrk.h" /* repeatable sbrk */
> # define EOL "\n" /* for DEBUG printouts only, allow crlf */
> enum {STDIN = 0, STDOUT, STDERR, STDAUX, STDPRN}; /* handles */
> static char dbgbuff[1024];
> static char *dbgbp = dbgbuff;
> # define DBGFLUSH do {if (dbgbp != dbgbuff) { \
> /* write it out */ \
> write(STDOUT, dbgbuff, strlen(dbgbuff)); \
> dbgbp = dbgbuff; \
> } \
> } while (0)
> # define DBGEOLN do { \
> DBGPRT(EOL); \
> DBGFLUSH; \
> } while (0)
> # define DBGPRT(msg, args...) do { \
> if ((dbgbp - dbgbuff) > 924) DBGFLUSH; \
> dbgbp +=sprintf(dbgbp, msg , ## args); \
> } while (0)
> # define SHOWBLK(m, id) showblock(m, id)
> # if DEBUGM
> # define DBGPRTM(msg, args...) \
> dbgbp +=sprintf(dbgbp, msg , ## args)
> # define SHOWBLKM(m, id) showblock(m, id)
> # else
> # define DBGPRTM(msg, args...)
> # define SHOWBLKM(m, id)
> # endif
> # if DEBUGF
> # define DBGPRTF(msg, args...) \
> dbgbp +=sprintf(dbgbp, msg , ## args)
> # define SHOWBLKF(m, id) showblock(m, id)
> # else
> # define DBGPRTF(msg, args...)
> # define SHOWBLKF(m, id)
> # endif
> # if DEBUGR
> # define DBGPRTR(msg, args...) \
> dbgbp +=sprintf(dbgbp, msg , ## args)
> # define SHOWBLKR(m, id) showblock(m, id)
> # else
> # define DBGPRTR(msg, args...)
> # define SHOWBLKR(m, id)
> # endif
> #endif
>
> typedef unsigned char byte;
> typedef unsigned int ulong;
>
> /* This is intended to allow finding the header area from
> the address of the immediately adjacent higher memblock.
> The guardxx avoid destruction by an off by one pointer
> and serve no real logical purpose. Note that in some
> cases sz may be recovered from next.
> */
> typedef struct memblock {
> struct memblock *prev;
> struct memblock *next;
> /* An allocated block has the next two fields NULL */
> /* A free block has them both non-NULL */
> struct memblock *nextfree;
> struct memblock *prevfree;
> ulong sz; /* of this memblock */
> ulong guardlo; /* may hold size requested */
> /* here lies the actual assigned storage */
> /* so the following must be addressed by adding offset */
> /* storage must always be a multiple of 8 in size */
> /* thus these items are fictional, i.e. for zero data */
> ulong guardhi[2];
> } memblock, *memblockp;
>
> #define DATAOFFSET (offsetof(memblock, guardhi))
>
> /* conversion and access macros */
> #define MEMBLKp(p) (memblockp)((byte*)(p) - DATAOFFSET)
> #define PTR(m) (void*)((byte*)(m) + DATAOFFSET)
>
> #define ALIGN 8
> #define ALIGNMASK (ALIGN-1)
>
> /* We can never use an allocation smaller than this */
> #define MINSAVE (ALIGN + sizeof(memblock))
>
> /* Alternate form of NULL to distinguish free lists */
> #define NONE (memblockp)&freehdrs
>
> /* Magic constants. MINSBRK must be MINSAVE or larger */
> enum {NFLISTS = 31, MINSBRK = 1024};
>
> /* ============== Globals ============= */
>
> /* Headers of lists holding free blocks of 2**2 thru 2**31 size */
> /* freehdr[n] holds items sized 2**n thru 2**(n+1) - 1 */
> static memblockp freehdrs[NFLISTS]; /* yes, low indices are waste */
> static memblockp lastsbrk;
>
> /* 1------------------1 */
>
> #if DEBUGM || DEBUGF || DEBUGR
> static void showblock(memblockp m, char *id)
> {
> if (m) {
> DBGPRT(" %s %p sz=%u nxt=%p prv=%p nxtf=",
> id, m, m->sz, m->next, m->prev);
> if (NONE == m->nextfree)
> DBGPRT("NONE prvf=");
> else
> DBGPRT("%p prvf=", m->nextfree);
> if (NONE == m->prevfree)
> DBGPRT("NONE");
> else
> DBGPRT("%p", m->prevfree);
> }
> else
> DBGPRT(" %s NULL", id);
> } /* showblock */
>
> /* 1------------------1 */
>
> /* dump the entire free chain group */
> void dumpfree(void)
> {
> int i;
> memblockp m;
>
> for (i = 0; i < NFLISTS; i++) {
> if ((m = freehdrs[i])) {
> DBGPRT(EOL "%2d: ", i);
> do {
> DBGPRT("%p(%u)->", m, m->sz);
> m = m->nextfree;
> } while (m && (NONE != m));
> DBGPRT("0");
> m = freehdrs[i];
> while (m && (NONE !=m )) {
> SHOWBLK(m, EOL " ");
> m = m->nextfree;
> }
> }
> }
> SHOWBLK(lastsbrk, EOL " ");
> DBGEOLN;
> } /* dumpfree */
> #endif
>
> /* 1------------------1 */
>
> static inline ulong roundup(size_t sz)
> {
> ulong size;
>
> size = ((sz + ALIGNMASK) & ~ALIGNMASK) + sizeof(memblock);
> return size;
> } /* roundup */
>
> /* 1------------------1 */
>
> static inline int size2bucket(ulong sz)
> {
> int b;
>
> for (b = 0; sz; sz >>= 1, b++) continue;
> return b;
> } /* size2bucket */
>
> /* 1------------------1 */
>
> static inline void mv2freelist(memblockp m)
> {
> int b;
>
> if (m) {
> b = size2bucket(m->sz);
> DBGPRT(EOL " mv2freelist %d", b); SHOWBLK(m, "blk");
> if (freehdrs[b]) {
> m->nextfree = freehdrs[b];
> freehdrs[b]->prevfree = m;
> }
> else
> m->nextfree = NONE;
> m->prevfree = NONE;
> if (freehdrs[b]) freehdrs[b]->prevfree = m;
> freehdrs[b] = m;
> }
> } /* mv2freelist */
>
> /* 1------------------1 */
>
> static inline void rmvfromfree(memblockp m)
> {
> int b;
>
> if (m) {
> b = size2bucket(m->sz);
> DBGPRTM(EOL " rmvfromfree %d", b); SHOWBLKM(m, "blk");
> if (m != freehdrs[b]) {
> DBGPRTM(" NOT FREE");
> }
> else {
> if (NONE == m->nextfree)
> freehdrs[b] = NULL;
> else {
> freehdrs[b] = m->nextfree;
> freehdrs[b]->prevfree = NONE;
> }
> m->nextfree = m->prevfree = NULL;
> DBGPRTM(EOL " freehdrs %d", b);
> SHOWBLKM(freehdrs[b], "is blk");
> }
> }
> } /* rmvfromfree */
>
> /* 1------------------1 */
>
> static inline int searchfree(ulong szneed)
> {
> int b;
>
> b = size2bucket(szneed);
> DBGPRTM(EOL " freelist search from bucket %d", b);
>
> if (! freehdrs[b] || (freehdrs[b]->sz < szneed)) {
> do {
> b++;
> } while ((b < NFLISTS) && ! freehdrs[b]);
> }
> /* if found we will break off a piece and housekeep */
> if (b < NFLISTS)
> DBGPRTM(", using %d", b);
> else {
> b = 0;
> DBGPRTM(", none found");
> }
> return b;
> } /* searchfree */
>
> /* 1------------------1 */
>
> static inline memblockp split(memblockp *mp, ulong sz)
> {
> memblockp m1, m;
>
> m = *mp;
> m1 = (memblockp)((char *)m + sz);
> assert((m->sz - sz) >= sizeof(memblock));
> memcpy(m1, m, sizeof(memblock));
> m1->prev = m;
> m1->sz = m->sz - sz;
> m->next = m1;
> m->sz = sz;
> m->nextfree = NULL;
> m->prevfree = NULL;
> *mp = m1;
> if (m1->next) {
> assert(m1->next->prev = m);
> m1->next->prev = m1;
> }
> SHOWBLKM(m, EOL " split returns");
> return m;
> } /* split */
>
> /* 1------------------1 */
>
> /* Get the memory, see if it extends the present lastsbrk
> If not, put the old lastsbrk into the appropriate freelist
> and replace lastsbrk by the new, setting the headers up
> else update the size markers in lastsbrk. When done
> lastsbrk either can supply the memory szextra, or is NULL.
> */
> static inline memblockp extendsbrk(ulong szxtra)
> {
> memblockp m;
> byte *expected;
> static int alignerr = 0; /* remember last correction */
> int aligndelta = 0;
>
> DBGPRTM(", extending sbrk");
>
> /* we have to ensure that the new lastsbrk always has */
> /* room to both realign and to leave a header when split */
> szxtra += (ALIGN + sizeof(memblock));
> if (szxtra < MINSBRK) szxtra = MINSBRK;
> szxtra += ALIGN - alignerr;
>
> if (lastsbrk)
> expected = ((byte*)lastsbrk) + lastsbrk->sz;
> else expected = NULL;
>
> if ((aligndelta = (ulong)expected & ALIGNMASK)) {
> /* lastsbrk was misaligned */
> szxtra += ALIGN - aligndelta;
> aligndelta = 0;
> }
>
> m = fakesbrk(szxtra);
> if (-1 == (int)m) return NULL;
> else {
> if ((byte*)m == expected) { /* Extending size of lastsbrk */
> DBGPRTM(EOL " sbrk(%4u=0x%05x) got expected %p"
> " lastsbrk %p sz %lu",
> szxtra, szxtra, expected,
> lastsbrk, expected - (byte*)lastsbrk);
> lastsbrk->sz += szxtra;
> alignerr = 0;
> m = lastsbrk;
> }
> else {
> /* Here we have to check & fix alignment */
> DBGPRTM(EOL "=>sbrk(%4u=0x%05x) got UNEXPECTED %p/%p"
> " lastsbrk %p sz %lu",
> szxtra, szxtra, m, expected,
> lastsbrk, expected - (byte*)lastsbrk);
> if ((alignerr = (ALIGNMASK & (ulong)m))) {
> (byte*)m += (aligndelta = ALIGN - alignerr);
> DBGPRTM(", szerr %d/%d", aligndelta, alignerr);
> }
> m->sz = szxtra - aligndelta; /* discard alignerr bytes */
> m->prev = m->next = NULL;
> m->nextfree = m->prevfree = NULL;
> m->guardlo = 0xDEADBEEF;
> m->guardhi[0] = 0xF00DFEED;
> m->guardhi[1] = 0xBEEFDEAD;
> mv2freelist(lastsbrk);
> lastsbrk = m;
> }
> }
> return m;
> } /* extendsbrk */
>
> /* 1------------------1 */
>
> /* The mechanism:
> All available memory is kept on the free list, and all adjacent
> blocks, assigned or free, are linked by next/prev fields in order
> of address. Freehdrs[n] holds the first of a list of free blocks
> of sizes between 2**n and 2**n+1. A pointer to the free portion
> of the block last acquired via sbrk is held in lastsbrk.
>
> All blocks on the freelist are marked by having a non-NULL value
> in the nextfree or prevfree fields. The special value NONE is
> used to replace NULL to terminate these lists. Because of the
> misalignment possibilities it is necessary to keep accurate byte
> count lengths in the sz component of lastsbrk.
>
> 1. An allocation is made from the first fit freehdrs list. Note
> that there MAY be a usable piece in the next lower freehdr, but
> that is ignored because we do not want to search possibly long
> lists. The block is removed from the freelist, and any excess
> space is broken off (if large enough to be usable) and assigned
> to the appropriate free list.
>
> 2. If no suitable free block is found, allocation is attempted
> from the last block created by an sbrk call. Such a block must
> be large enough to maintain an sbrk pointer after splitting off
> the desired allocation.
>
> 3. If this fails a new block is created (or extended) via an
> sbrk call. If possible, the previous lastsbrk block is extended.
> If extension is not possible the remains of the old block alone
> is placed in the freelist. This (non-extension) case results in
> the prev field of the lastsbrk block being NULL. The next field
> of the lastsbrk block is always NULL. In this case only it is
> necessary to check and correct memory alignment.
>
> Insertion is always done into the start of any given freelist.
> Thus there is no list walking needed. Similarly, any block is
> always removed from the head of the appropriate freelist.
>
> It is assumed that sbrk will never return a lower address than
> did a previous sbrk. I am not sure if this affects anything. I
> believe it does not.
> */
> void *nmalloc(size_t sz)
> {
> memblockp m = NULL, m1;
> ulong szneed;
> int b;
> void *p;
>
> /* compute the rounded up size needed */
> szneed = roundup(sz);
> DBGPRTM("malloc(%5lu) [%5u]", sz, szneed);
> SHOWBLKM(lastsbrk, EOL " lastsbrk");
>
> /* search the free lists for one */
> b = searchfree(szneed);
>
> if (b) {
> rmvfromfree(m1 = freehdrs[b]);
> if (m1->sz < szneed + MINSAVE)
> m = m1;
> else {
> m = split(&m1, szneed);
> mv2freelist(m1);
> }
> }
> else if (lastsbrk &&
> (lastsbrk->sz >= (szneed + sizeof(memblock)))) {
> m = split(&lastsbrk, szneed);
> }
> /* if not found get more from system */
> else if ((m1 = extendsbrk(szneed))) {
> if (m1->sz < szneed + MINSAVE) {
> m = m1;
> DBGPRTM(EOL "**FOULED lastsbrk\a");
> }
> else {
> m = split(&lastsbrk, szneed);
> }
> }
> /* else abject_failure(); */
>
> if (m) p = PTR(m);
> else {
> DBGPRTM(dbgbp, ", FAILURE");
> p = NULL;
> }
>
> #if DEBUGM
> DBGPRTM(EOL "returns %p", p);
> if (m) DBGPRTM("(%lu)", m->sz - sizeof(memblock));
> DBGEOLN;
> #endif
> return p;
> } /* nmalloc */
>
> /* 1------------------1 */
>
> #define ISFREE(m) (m && (m != NONE) && m->nextfree && m->prevfree)
>
> /* 1------------------1 */
>
> /* Unlike rmvfromfree, this extracts a block that */
> /* may be buried deep withing the free list by */
> /* unlinking. m is already known a free block */
> static inline void extractfree(memblockp m)
> {
> int b;
> memblockp mnxtf, mprvf;
>
> if (m) {
> b = size2bucket(m->sz);
> SHOWBLKF(m, EOL " extractfree blk");
>
> /* ease further tests */
> if (NONE == (mnxtf = m->nextfree)) m->nextfree = NULL;
> if (NONE == (mprvf = m->prevfree)) m->prevfree = NULL;
>
> if (m->nextfree) m->nextfree->prevfree = mprvf;
>
> if (m->prevfree) m->prevfree->nextfree = mnxtf;
> else if (m->nextfree) freehdrs[b] = mnxtf;
> else freehdrs[b] = NULL;
>
> DBGPRTF(EOL " freehdrs %d", b);
> SHOWBLKF(freehdrs[b], "is blk");
> }
> } /* extractfree */
>
> /* 1------------------1 */
>
> /* used to combine with lastsbrk, so no ISFREE test */
> /* because lastsbrk is not kept in the free lists */
> static inline memblockp combinehi(memblockp m)
> {
> memblockp m1;
>
> if (m) {
> assert(m->next->prev == m);
> m1 = m->next;
> if (m1 != lastsbrk) extractfree(m1);
> if (NULL != (m->next = m->next->next))
> m->next->prev = m;
> m->sz += m1->sz;
> }
> return m;
> } /* combinehi */
>
> /* 1------------------1 */
>
> static inline memblockp combinelo(memblockp m)
> {
> memblockp m1;
>
> m1 = m;
> if (ISFREE(m->prev)) {
> assert(m->prev->next == m);
> m1 = m->prev;
> extractfree(m1);
> if (NULL != (m1->next = m->next))
> m1->next->prev = m1;
> m1->sz += m->sz;
> }
> return m1;
> } /* combinelo */
>
> /* 1------------------1 */
>
> void nfree(void *ptr)
> {
> memblockp m;
>
> if (ptr) {
> m = MEMBLKp(ptr);
> DBGPRTF("free(%p)", ptr); SHOWBLKF(m, "");
>
> /* mark the block free */
> m->nextfree = m->prevfree = NONE;
>
> /* try to combine with lower or higher blocks in memory */
> if (ISFREE(m->next)) m = combinehi(m);
> if (ISFREE(m->prev)) m = combinelo(m);
>
> if (lastsbrk)
> if (lastsbrk == m->prev)
> DBGPRTF(EOL "**Found decreasing sbrk!! FOUL");
> else if (lastsbrk == m->next) {
> SHOWBLKF(lastsbrk, EOL " Combine with lastsbrk");
> lastsbrk = combinehi(m);
> lastsbrk->nextfree = lastsbrk->prevfree = NULL;
> SHOWBLKF(lastsbrk, EOL " Resulting in lastsbrk");
> }
> else mv2freelist(m);
> else mv2freelist(m);
> #if DEBUGF
> DBGEOLN;
> #endif
> }
> } /* nfree */
>
> /* 1------------------1 */
>
> void *nrealloc(void *ptr, size_t sz)
> {
> memblockp m;
>
> m = MEMBLKp(ptr);
> DBGPRTR("realloc(%p:%u->%lu)", ptr, m->sz, sz);
>
> /* if decreasing simply reduce size and move excess to free */
> /* else if the 'next' block is free and adequate use it */
> /* ( involving a walk of some free list ) */
> /* else malloc new size, copy data, and free old */
>
> #if DEBUGR
> DBGEOLN;
> #endif
> if (m) return PTR(m);
> else return NULL;
> } /* nrealloc */
>
> /* --------- nmalloc.c ----------- */
--
Chuck F (cbfalconer AT yahoo DOT com) (cbfalconer AT XXXXworldnet DOT att DOT net)
Available for consulting/temporary embedded and systems.
(Remove "XXXX" from reply address. yahoo works unmodified)
mailto:uce AT ftc DOT gov (for spambots to harvest)
- Raw text -