X-Authentication-Warning: delorie.com: mailnull set sender to djgpp-workers-bounces using -f Message-ID: <3C7D4C39.2B68622E@yahoo.com> Date: Wed, 27 Feb 2002 16:14:33 -0500 From: CBFalconer Organization: Ched Research X-Mailer: Mozilla 4.75 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: djgpp-workers AT delorie DOT com Subject: Re: Malloc/free DJGPP code References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Reply-To: djgpp-workers AT delorie DOT com 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 /* offsetof() */ > #include > #include /* sbrk */ > #include /* goes away with NDEBUG */ > > /* Incorporation into the system should require deleting the > following , 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 /* sprintf, write for DEBUG only */ > # include /* 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)