Mail Archives: djgpp-workers/2003/09/07/07:58:56.1
Hello.
Below is a patch to switch DJGPP to nmalloc. It's very much
a work in progress. Current problems:
* The hooks from m_hook_kind need prefixing with, say, __malloc
instead of M.
* memalign needs some work. valloc uses memalign, so that's affected too.
* There are various bits of wreakage from the integration
in the headers. Search the diff for "Wreakage". ;)
I'm not going to be able to do any work on DJGPP for two weeks after today,
so if someone gets to look at memalign, that would be useful.
Bye, Rich =]
Index: include/stdlib.h
===================================================================
RCS file: /cvs/djgpp/djgpp/include/stdlib.h,v
retrieving revision 1.17
diff -p -u -3 -r1.17 stdlib.h
--- include/stdlib.h 20 Feb 2003 19:06:14 -0000 1.17
+++ include/stdlib.h 7 Sep 2003 10:37:15 -0000
@@ -187,6 +187,45 @@ int malloc_verify(void);
int malloc_debug(int);
void mallocmap(void);
+/* TODO: FIXME: Wreakage from nmalloc integration is below. */
+
+/* The settable hooks, identifiers */
+/* HKCOUNT is illegal value */
+enum m_hook_kind {malloc_HK, malloc_fail_HK,
+ free_HK, free_null_HK,
+ realloc_HK, realloc_exit_HK,
+ HKCOUNT};
+
+/* Depending on kind, some params may be meaningless */
+typedef void (*M_HOOKFN)(size_t sz, void *bk);
+
+/* returns previous value of the appropriate function */
+typedef M_HOOKFN (*set_m_hook)(enum m_hook_kind which,
+ M_HOOKFN newhook);
+
+/* This allows a clean connection to debugging software */
+/* NOTE: ANY value equivalent to -1 means data not available */
+/* for the unsigned chars this means 0xffh. */
+struct _sysquery {
+ unsigned char data, gdlo, sz, prvf, nxtf, nxt, prv, ohead;
+ void * nilp; /* dummy NULL, &freeptrs[1] */
+ void * anchors; /* of memory chains */
+ set_m_hook hookset; /* how to set a hook */
+};
+
+/* This can return the above values, hopefully in a register */
+/* NONE is used in nextfree, prevfree as the equivalent of NULL */
+/* With the unclean knowledge that nil is actually a pointer to */
+/* freehdrs[1], and that lastsbrk is actually freehdrs[0], the */
+/* entire malloc structure is open to debuggery. */
+struct _sysquery _sysmalloc(void);
+
+/* TODO: FIXME: Get FILE somehow. */
+#include <stdio.h>
+
+FILE *malldbgdumpfile(FILE *fp);
+M_HOOKFN mallsethook(enum m_hook_kind which, M_HOOKFN newhook);
+
#endif /* !_POSIX_SOURCE */
#endif /* !__STRICT_ANSI__ */
#endif /* !__dj_ENFORCE_ANSI_FREESTANDING */
Index: include/libc/malloc.h
===================================================================
RCS file: /cvs/djgpp/djgpp/include/libc/malloc.h,v
retrieving revision 1.3
diff -p -u -3 -r1.3 malloc.h
--- include/libc/malloc.h 4 Feb 2003 20:25:08 -0000 1.3
+++ include/libc/malloc.h 7 Sep 2003 10:37:15 -0000
@@ -18,6 +18,10 @@ extern "C" {
#ifndef _POSIX_SOURCE
+/* TODO: FIXME: Wreakage from nmalloc integration is below. */
+
+#if 0
+
typedef struct BLOCK {
size_t size;
struct BLOCK *next;
@@ -35,6 +39,8 @@ typedef struct BLOCK {
#endif
#define ALIGN 8
#define SMALL (NUMSMALL*ALIGN)
+
+#endif /* 0 */
#endif /* !_POSIX_SOURCE */
#endif /* !__STRICT_ANSI__ */
Index: include/libc/stubs.h
===================================================================
RCS file: /cvs/djgpp/djgpp/include/libc/stubs.h,v
retrieving revision 1.14
diff -p -u -3 -r1.14 stubs.h
--- include/libc/stubs.h 6 Dec 2002 09:32:23 -0000 1.14
+++ include/libc/stubs.h 7 Sep 2003 10:37:20 -0000
@@ -1,3 +1,4 @@
+/* Copyright (C) 2003 DJ Delorie, see COPYING.DJ for details */
/* Copyright (C) 2002 DJ Delorie, see COPYING.DJ for details */
/* Copyright (C) 1997 DJ Delorie, see COPYING.DJ for details */
/* Copyright (C) 1995 DJ Delorie, see COPYING.DJ for details */
@@ -54,6 +55,7 @@ extern "C" {
#define gettimeofday __gettimeofday
#define lfilelength __lfilelength
#define llseek __llseek
+#define memalign __memalign
#define modfl __modfl
#define moncontrol __moncontrol
#define monstartup __monstartup
Index: src/libc/ansi/stdlib/makefile
===================================================================
RCS file: /cvs/djgpp/djgpp/src/libc/ansi/stdlib/makefile,v
retrieving revision 1.6
diff -p -u -3 -r1.6 makefile
--- src/libc/ansi/stdlib/makefile 1 Dec 2002 09:45:26 -0000 1.6
+++ src/libc/ansi/stdlib/makefile 7 Sep 2003 10:37:21 -0000
@@ -1,3 +1,4 @@
+# Copyright (C) 2003 DJ Delorie, see COPYING.DJ for details
# Copyright (C) 2002 DJ Delorie, see COPYING.DJ for details
# Copyright (C) 2001 DJ Delorie, see COPYING.DJ for details
# Copyright (C) 1998 DJ Delorie, see COPYING.DJ for details
@@ -22,8 +23,12 @@ SRC += labs.c
SRC += ldiv.c
SRC += llabs.c
SRC += lldiv.c
-SRC += malloc.c
-SRC += malldbg.c
+# Old malloc
+#SRC += malloc.c
+#SRC += malldbg.c
+# New malloc
+SRC += nmalloc.c
+SRC += nmalldbg.c
SRC += qsort.c
SRC += rand.c
SRC += strtod.c
Index: src/libc/compat/stdlib/makefile
===================================================================
RCS file: /cvs/djgpp/djgpp/src/libc/compat/stdlib/makefile,v
retrieving revision 1.5
diff -p -u -3 -r1.5 makefile
--- src/libc/compat/stdlib/makefile 20 Jan 2001 04:13:25 -0000 1.5
+++ src/libc/compat/stdlib/makefile 7 Sep 2003 10:37:26 -0000
@@ -1,3 +1,4 @@
+# Copyright (C) 2003 DJ Delorie, see COPYING.DJ for details
# Copyright (C) 2001 DJ Delorie, see COPYING.DJ for details
# Copyright (C) 1999 DJ Delorie, see COPYING.DJ for details
# Copyright (C) 1998 DJ Delorie, see COPYING.DJ for details
@@ -23,7 +24,8 @@ SRC += fcvtbuf.c
SRC += fcvt.c
SRC += gcvt.c
SRC += rand48.c
-SRC += memalign.c
+# nmalloc implements memalign.
+#SRC += memalign.c
SRC += valloc.c
include $(TOP)/../makefile.inc
Index: tests/libc/ansi/stdlib/makefile
===================================================================
RCS file: /cvs/djgpp/djgpp/tests/libc/ansi/stdlib/makefile,v
retrieving revision 1.3
diff -p -u -3 -r1.3 makefile
--- tests/libc/ansi/stdlib/makefile 8 Jun 2001 10:03:33 -0000 1.3
+++ tests/libc/ansi/stdlib/makefile 7 Sep 2003 10:37:26 -0000
@@ -1,6 +1,7 @@
TOP=../..
SRC += env.c
+SRC += evilalgo.c
SRC += getenv.c
SRC += shell.c
SRC += strtod.c
Index: src/docs/kb/wc204.txi
===================================================================
RCS file: /cvs/djgpp/djgpp/src/docs/kb/wc204.txi,v
retrieving revision 1.160
diff -p -u -3 -r1.160 wc204.txi
--- src/docs/kb/wc204.txi 3 Sep 2003 17:05:22 -0000 1.160
+++ src/docs/kb/wc204.txi 7 Sep 2003 10:37:36 -0000
@@ -1008,3 +1008,9 @@ into itself, when the current directory
The C99 macro @code{fpclassify} and the supporting functions
@code{__fpclassifyf}, @code{__fpclassifyd} and @code{__fpclassifyld}
were added.
+
+@findex malloc AT r{, New implementation}
+@findex free AT r{, New implementation}
+@findex realloc AT r{, New implementation}
+A new algorithm for allocating memory has been implemented.
+This speeds up memory reallocation considerably.
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ src/libc/ansi/stdlib/nmalloc.c 2003-09-06 16:06:46.000000000 +0000
@@ -0,0 +1,1154 @@
+/* --------- nmalloc.c ----------- */
+
+/* Copyright (c) 2003 by Charles B. Falconer
+ Licensed under the terms of the GNU LIBRARY GENERAL PUBLIC
+ LICENSE and/or the terms of COPYING.DJ, all available at
+ <http://www.delorie.com>.
+
+ Bug reports to <mailto:cbfalconer AT worldnet DOT att DOT net>
+ (html mail will probably be summarily ignored)
+*/
+
+/* 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)
+
+ The system is NOT thread and interrupt safe, although use of a
+ suitable critical section call could make it such. Nothing
+ herein executes for any unusual length of time (with NDEBUG).
+*/
+
+/* Some critical tuning constants. Search for them:
+ MINSBRK controls minimal access to sbrk
+ ALIGN controls alignment of pointers
+ SAVEMEMORY reduces overhead at expense of checkability
+ INT_MAX (system) controls maximum allocation quantum.
+*/
+
+#include <libc/stubs.h>
+
+/* To avoid unexpected problems, the default has been changed
+ so we now require NEWMALLDBG to enable the original action
+*/
+
+#ifndef NEWMALLDBG
+# undef NDEBUG
+# define NDEBUG
+#else
+# undef NDEBUG
+#endif
+
+#ifndef NDEBUG
+ /* diddle these to control areas debugged */
+# define DEBUGM 1 /* malloc */
+# define DEBUGF 1 /* free */
+# define DEBUGR 1 /* realloc */
+#else
+# define DEBUGM 0
+# define DEBUGF 0
+# define DEBUGR 0
+ /* the HOOKABLE variant is only for development */
+ /* It allows some other package to define malloc, */
+ /* free, realloc, and to call this package. */
+# ifndef HOOKABLE
+# define nmalloc malloc
+# define nfree free
+# define nrealloc realloc
+# define nmemalign memalign
+# else
+# define nmalloc _malloc
+# define nfree _free
+# define nrealloc _realloc
+# define nmemalign _memalign
+# endif
+# define fakesbrk sbrk
+#endif
+
+#define SAVEMEMORY 1 /* 0/1 to use/eliminate extra storage */
+
+typedef unsigned char byte;
+typedef unsigned int ulong;
+
+#include <stddef.h> /* offsetof() */
+#include <stdlib.h> /* malloc, free, realloc, exit, EXIT_FAILURE */
+#include <unistd.h> /* sbrk, write */
+#include <signal.h> /* raise, SIGABRT */
+#include <string.h> /* strlen, memmove, memcpy */
+#include <limits.h> /* CHAR_BIT, INT_MAX */
+
+/* TODO: FIXME: #if 0/#endif is wreakage from nmalloc integration. */
+#if 0
+#include "sysquery.h" /* available debugger linkages */
+#endif
+
+/* system dependant magic. Only STDERR used */
+enum {STDIN = 0, STDOUT, STDERR, STDAUX, STDPRN}; /* handles */
+
+/* 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. 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, which does all the above except
+ the inlining. But see NEWMALLDBG above.
+*/
+#ifndef NDEBUG
+# include "nmalloc.h" /* while testing before name changes */
+#else
+# ifdef HOOKABLE
+# include "hookmem.h"
+# endif
+#endif
+
+/* ============================================================
+ Macros and storage for debugging, works before init on DJGPP
+ WARNING - GNU extensions used here!!
+ Note: many messages are designed for easy search with grep
+ and also serve as comments.
+*/
+#if DEBUGM || DEBUGF || DEBUGR
+# include <stdio.h> /* sprintf, for DEBUG only */
+# include "fakesbrk.h" /* repeatable sbrk */
+# define EOL "\n" /* for DEBUG printouts only, allow crlf */
+ 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
+#else
+# define DBGFLUSH
+# define DBGEOLN
+# define DBGPRT(msg, args...)
+# define SHOWBLK(m, id)
+# define DBGPRTM(msg, args...)
+# define SHOWBLKM(m, id)
+# define DBGPRTF(msg, args...)
+# define SHOWBLKF(m, id)
+# define DBGPRTR(msg, args...)
+# define SHOWBLKR(m, id)
+#endif
+
+/* This is intended to allow finding the header area from
+ the address of the immediately adjacent memblocks.
+ 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 or next may be
+ recovered from sz.
+*/
+typedef struct memblock {
+ struct memblock *prev; /* 1st, protect against overrun */
+ struct memblock *next; /* makes this less clobberable */
+ ulong sz; /* of this memblock */
+ /* An allocated block has the next two (1) fields NULL */
+ /* A free block has them both non-NULL */
+ struct memblock *nextfree;
+ struct memblock *prevfree; /* actually data w/SAVEMEMORY */
+#if SAVEMEMORY == 0
+ ulong guardlo; /* may hold size requested */
+#endif
+ /* 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 */
+} memblock, *memblockp;
+
+/* Notice that with SAVEMEMORY the prevfree field only
+ exists for free blocks; it reuses data space. This
+ is why we cannot allow 0 sized blocks.
+*/
+#if SAVEMEMORY
+# define DATAOFFSET (offsetof(memblock, prevfree))
+#else
+# define DATAOFFSET sizeof(memblock)
+#endif
+
+/* 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 + DATAOFFSET)
+
+/* Alternate form of NULL to distinguish free lists
+ This is self protection, because freehdrs[1] is otherwise
+ unused. freehdrs[0] is reserved to hold lastsbrk. In turn
+ this means that ALIGN must be >= 4.
+*/
+#define NONE (memblockp)&freehdrs[1]
+
+/* Magic constants. MINSBRK must be MINSAVE or larger */
+enum {NFLISTS = (int)(CHAR_BIT * sizeof(size_t)), 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 */
+#define lastsbrk freehdrs[0]
+
+/* keep track of the bases of each new sbrk block */
+#define MAXSBRKS 100 /* I have never seen more than 5 needed */
+static int lastsbrkbgn; /* zeroed on load */
+static void *sbrkbgn[MAXSBRKS]; /* NULLS on load */
+
+/* This holds pointers to hooks, initialized to NULLs */
+/* see enum m_hook_kind for actual identifiers in sysquery.h */
+static M_HOOKFN hookptr[HKCOUNT];
+
+/* Forward declaration to allow sysquery init below */
+static M_HOOKFN sethook(enum m_hook_kind which,
+ M_HOOKFN newhook);
+
+/* This allows a clean connection to debugging software */
+static struct _sysquery sysquery = {
+ DATAOFFSET,
+#if SAVEMEMORY
+ 0xff,
+#else
+ offsetof(memblock, guardlo),
+#endif
+ offsetof(memblock, sz),
+ offsetof(memblock, prevfree),
+ offsetof(memblock, nextfree),
+ offsetof(memblock, next),
+ offsetof(memblock, prev),
+ sizeof(memblock),
+ NONE, /* also &freehds[1] */
+ &sbrkbgn, /* anchors field */
+ sethook /* hookset field */
+};
+
+/* 1------------------1 */
+
+/* This can return the above values, hopefully in a register */
+/* The use of NONE in nextfree, prevfree may cause confusion */
+struct _sysquery _sysmalloc(void)
+{
+ return sysquery;
+} /* _sysmalloc */
+
+/* 1------------------1 */
+
+#if DEBUGM || DEBUGF || DEBUGR
+
+/* These two routines are actually available in any user */
+/* application by use of the _sysmalloc call above. They */
+/* are retained here to show the derivation of user code, */
+/* and in case needed during system initialization. */
+
+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 (m->nextfree) {
+ 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("0");
+ }
+ else
+ DBGPRT(" %s NULL", id);
+} /* showblock */
+
+/* 1------------------1 */
+
+/* dump the entire free chain group */
+static 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;
+ }
+ }
+ }
+ DBGEOLN;
+} /* dumpfree */
+#endif
+
+/* 1------------------1 */
+
+/* This is accessible only through the pointer */
+/* returned in the sysquery record by _sysmalloc. */
+/* Only of use in the malldbg package. */
+/* No safeties implemented here - see malldbg */
+static M_HOOKFN sethook(enum m_hook_kind which,
+ M_HOOKFN newhook)
+{
+ M_HOOKFN tmp = NULL;
+
+ if (which < HKCOUNT) {
+ tmp = hookptr[which];
+ hookptr[which] = newhook;
+ }
+ return tmp;
+} /* sethook */
+
+/* 1------------------1 */
+
+/* inserts bases of sbrk chains in sbrkbgn array */
+/* This ensures we can find all controlled memory */
+/* gets called when we find an unexpected sbrk. */
+/* Note that if the sbrk was unaligned bk has now */
+/* been aligned, and we have no record of wastage */
+/* As long as nothing is returned to sbrk this is */
+/* not a problem. This only for the malldbg pkg. */
+static void recordnewsbrk(memblockp bk)
+{
+ int i;
+
+ if (lastsbrkbgn < MAXSBRKS - 1) {
+ /* This check for a previous entry is probably not
+ needed, but it is a rare occurance, so safety */
+ for (i = 0; i < lastsbrkbgn; i++) {
+ if (bk == sbrkbgn[i]) return;
+ }
+ sbrkbgn[lastsbrkbgn++] = bk;
+ }
+/* else we abandon trying to keep track */
+} /* recordnewsbrk */
+
+/* 1------------------1 */
+
+static inline ulong roundup(size_t sz)
+{
+ ulong size;
+
+ size = ((sz + ALIGNMASK) & ~ALIGNMASK) + DATAOFFSET;
+ 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 void badcallabort(const char *msg, int lgh, memblockp m)
+{
+#if DEBUGM || DEBUGF || DEBUGR
+ DBGEOLN;
+#endif
+ write(STDERR, msg, lgh);
+ write(STDERR, ": memory fouled\n", 16);
+#if DEBUGM || DEBUGF || DEBUGR
+ SHOWBLK(m, "");
+ dumpfree();
+#else
+ (void)m; /* anti unused warning */
+#endif
+ raise(SIGABRT);
+} /* badcallabort */
+
+/* 1------------------1 */
+
+#define ISFREE(m) (m && (m != NONE) && m->nextfree && m->prevfree)
+#if SAVEMEMORY
+#define FOULED(m) (!lastsbrk || m->nextfree)
+#else
+#define FOULED(m) (!lastsbrk || (m->guardlo != 0xDEADBEEF))
+#endif
+
+/* 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 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;
+
+ /* mark the block non-free */
+ m->nextfree = m->prevfree = NULL;
+
+ DBGPRTF(EOL " freehdrs %d", b);
+ SHOWBLKF(freehdrs[b], "is blk");
+ }
+} /* extractfree */
+
+/* 1------------------1 */
+
+static inline memblockp combinelo(memblockp m)
+{
+ memblockp m1;
+
+ m1 = m;
+ if (ISFREE(m->prev)) {
+ if (m->prev->next != m) {
+ badcallabort("combinelo", 9, m);
+ exit(EXIT_FAILURE); /* prevent user trapping SIGABRT */
+ }
+ m1 = m->prev;
+ extractfree(m1);
+ if (NULL != (m1->next = m->next))
+ m1->next->prev = m1;
+ m1->sz += m->sz;
+ }
+ return m1;
+} /* combinelo */
+
+/* 1------------------1 */
+
+/* used to combine with lastsbrk, so no ISFREE test */
+/* because lastsbrk is not kept in the free lists */
+static memblockp combinehi(memblockp m)
+{
+ memblockp m1;
+
+ if (m && m->next) {
+ SHOWBLK(m, EOL " combinehi");
+ SHOWBLK(m->next, EOL " with");
+ if (m->next->prev != m) {
+ badcallabort("combinehi", 9, m);
+ exit(EXIT_FAILURE); /* prevent user trapping SIGABRT */
+ }
+ m1 = m->next;
+ if (m1 != lastsbrk) extractfree(m1);
+ if (NULL != (m->next = m->next->next))
+ m->next->prev = m;
+ m->sz += m1->sz;
+ SHOWBLK(m, EOL " giving");
+ }
+ return m;
+} /* combinehi */
+
+/* 1------------------1 */
+
+/* This takes care of marking the block as free */
+static void mv2freelist(memblockp m)
+{
+ int b;
+
+ if (m) {
+ if (ISFREE(m->next)) m = combinehi(m);
+ b = size2bucket(m->sz);
+ DBGPRT(EOL " mv2freelist %d", b); SHOWBLK(m, "blk");
+ if (lastsbrk && (m->next == lastsbrk)) {
+ SHOWBLKF(lastsbrk, EOL " Combine with lastsbrk");
+ lastsbrk = combinehi(m);
+ lastsbrk->nextfree = lastsbrk->prevfree = NULL;
+ SHOWBLKF(lastsbrk, EOL " Resulting in lastsbrk");
+ return;
+ }
+ else 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;
+ DBGPRT(EOL " Exit mv2freelist");
+ }
+} /* mv2freelist */
+
+/* 1------------------1 */
+
+/* this always marks the block as non-free */
+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");
+ badcallabort("rmvfromfree", 11, m);
+ exit(EXIT_FAILURE); /* prevent user trapping SIGABRT */
+ }
+ else {
+ if (NONE == m->nextfree)
+ freehdrs[b] = NULL;
+ else {
+ freehdrs[b] = m->nextfree;
+ freehdrs[b]->prevfree = NONE;
+ }
+#if SAVEMEMORY
+ m->nextfree = NULL;
+#else
+ m->nextfree = m->prevfree = NULL;
+#endif
+ DBGPRTM(EOL " freehdrs %d", b);
+ SHOWBLKM(freehdrs[b], "is blk");
+ }
+ }
+} /* rmvfromfree */
+
+/* 1------------------1 */
+
+static int searchfree(ulong szneed)
+{
+ int b;
+
+ b = size2bucket(szneed);
+ DBGPRT(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)
+ DBGPRT(", using %d", b);
+ else {
+ b = 0;
+ DBGPRT(", none found");
+ }
+ return b;
+} /* searchfree */
+
+/* 1------------------1 */
+
+/* The higher portion is returned in *mp, */
+/* the lower portion via the function return. */
+/* and the lower portion is marked non-free */
+static memblockp split(memblockp *mp, ulong sz)
+{
+ memblockp m1, m;
+
+ m = *mp;
+ m1 = (memblockp)((char *)m + sz);
+ if (m->sz < (sz + DATAOFFSET)) {
+ badcallabort("memblockpsz", 11, m);
+ exit(EXIT_FAILURE); /* prevent user trapping SIGABRT */
+ }
+ memcpy(m1, m, DATAOFFSET);
+ m1->prev = m;
+ m1->sz = m->sz - sz;
+ m->next = m1;
+ m->sz = sz;
+ m->nextfree = NULL;
+#if SAVEMEMORY
+#else
+ m->prevfree = NULL;
+#endif
+ *mp = m1;
+ if (m1->next) {
+ if (m1->next->prev != m) {
+ badcallabort("memblockpnxt", 12, m1);
+ exit(EXIT_FAILURE); /* prevent user trapping SIGABRT */
+ }
+ 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 either
+ lastsbrk can supply the memory szextra, or NULL is returned.
+ A revised lastsbrk block is marked as non-free.
+*/
+static memblockp extendsbrk(ulong szxtra)
+{
+ memblockp m;
+ byte *expected;
+ int alignerr;
+ int aligndelta;
+
+ 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 += (2 * ALIGN + DATAOFFSET);
+ if (szxtra < MINSBRK) szxtra = MINSBRK;
+
+ if (lastsbrk)
+ expected = ((byte*)lastsbrk) + lastsbrk->sz;
+ else expected = NULL;
+
+ if ((aligndelta = (ulong)expected & ALIGNMASK)) {
+ /* lastsbrk end was misaligned, try to align end of this */
+ 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 %d",
+ szxtra, szxtra, expected,
+ lastsbrk, expected - (byte*)lastsbrk);
+ lastsbrk->sz += szxtra;
+ m = lastsbrk;
+ }
+ else {
+ /* Here we have to check & fix alignment */
+ DBGPRTM(EOL "=>sbrk(%4u=0x%05x) got UNEXPECTED %p/%p"
+ " lastsbrk %p sz %d",
+ 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;
+#if SAVEMEMORY
+ m->nextfree = NULL;
+#else
+ m->nextfree = m->prevfree = NULL;
+ m->guardlo = 0xDEADBEEF;
+#endif
+ mv2freelist(lastsbrk);
+ lastsbrk = m;
+ recordnewsbrk(m); /* save in list of chains */
+ }
+ }
+ 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 size)
+{
+ memblockp m = NULL, m1;
+ ulong szneed;
+ int b;
+ void *p = NULL;
+ size_t sz = size; /* preserve arg for hooks */
+
+ /* compute the rounded up size needed */
+ if (!sz) sz++; /* avoid any 0 space allocation */
+ szneed = roundup(sz);
+ DBGPRTM("malloc(%5lu) [%5u]", sz, szneed);
+ SHOWBLKM(lastsbrk, EOL " lastsbrk");
+
+ /* Check for oversize allocation request */
+ if (szneed < ((ulong)(INT_MAX - 65536))) {
+ /* 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 + DATAOFFSET))) {
+ 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(); */
+ /* abject_failure COULD check the first possible freehdrs */
+ /* list as a last chance to find some suitable memory */
+
+ if (m) p = PTR(m);
+ else {
+ DBGPRTM(dbgbp, ", FAILURE");
+ p = NULL;
+ }
+ }
+/* else m and p are NULL for oversize; */
+
+#if DEBUGM
+ DBGPRTM(EOL "returns %p", p);
+ if (m) DBGPRTM("(%lu)", m->sz - DATAOFFSET);
+ DBGEOLN;
+#endif
+
+ if (hookptr[malloc_HK]) hookptr[malloc_HK](size, p);
+ if (!p && hookptr[malloc_fail_HK])
+ hookptr[malloc_fail_HK](size, NULL);
+
+ return p;
+} /* nmalloc */
+
+/* 1------------------1 */
+
+static void dofree(memblockp 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 && (lastsbrk == m->prev) )
+ DBGPRTF(EOL "**Found decreasing sbrk!! FOUL");
+ else mv2freelist(m);
+} /* dofree */
+
+/* 1------------------1 */
+
+void nfree(void *ptr)
+{
+ memblockp m;
+
+ if (hookptr[free_HK]) hookptr[free_HK](0, ptr);
+
+ if (ptr) {
+ m = MEMBLKp(ptr);
+ DBGPRTF("free(%p)", ptr); SHOWBLKF(m, "");
+ if (ISFREE(m) || /* bad, refreeing block */
+ FOULED(m) ) { /* block is fouled */
+ badcallabort("free", 4, m);
+ return; /* he can trap this SIGABRT */
+ }
+ dofree(m);
+#if DEBUGF
+ DBGEOLN;
+#endif
+ }
+ else if (hookptr[free_null_HK])
+ hookptr[free_null_HK](0, NULL);
+} /* nfree */
+
+/* 1------------------1 */
+
+static memblockp mv2lastsbrk(memblockp m, ulong szneed)
+{
+ memblockp m1;
+
+ m1 = split(&lastsbrk, szneed);
+
+ /* Now m1 is the proposed new block, of the right size */
+ /* links are already revised so copy data from m to m2 */
+ memcpy(PTR(m1), PTR(m), m->sz - DATAOFFSET);
+
+ dofree(m);
+ return m1;
+} /* mv2lastsbrk */
+
+/* 1------------------1 */
+
+void *nrealloc(void *ptr, size_t size)
+{
+ memblockp m, m1, m2;
+ void *p;
+ ulong szneed;
+ int b;
+ size_t sz = size;
+
+ if (hookptr[realloc_HK]) hookptr[realloc_HK](sz, ptr);
+
+ if (!ptr) {
+ p = nmalloc(sz);
+ if (hookptr[realloc_exit_HK])
+ hookptr[realloc_exit_HK](size, p);
+ return p;
+ }
+
+ m = m1 = MEMBLKp(ptr);
+ if (!sz) sz++; /* avoid any 0 space allocation */
+ szneed = roundup(sz);
+ DBGPRTR("realloc(%p:%lu[%u])", ptr, sz, szneed);
+ SHOWBLKR(m, EOL " was");
+ if (ISFREE(m) || /* bad, realloc of free block */
+ FOULED(m) ) { /* storage fouled */
+ badcallabort("realloc", 7, m);
+ p = NULL;
+ goto exeunt; /* he can trap this SIGABRT */
+ }
+ SHOWBLKR(lastsbrk, EOL " lastsbrk");
+
+ /* if decreasing simply reduce size and move excess to free */
+ if (szneed <= m->sz) {
+ DBGPRTR(EOL " Realloc is reducing");
+ if ((m->sz - szneed) >= MINSAVE) {
+ m = split(&m1, szneed);
+ mv2freelist(m1);
+ }
+ /* else just return old pointer, i.e. NOP */
+ }
+ else if (szneed > ((ulong)(INT_MAX - 65536))) {
+ /* reject excessive size request */
+ p = NULL; goto exeunt;
+ }
+ else if (ISFREE(m->next) &&
+ (szneed <= (m->sz + m->next->sz)) ) {
+ /* the 'next' block is free and adequate so use it */
+ DBGPRTR(EOL " Realloc is combining, next is free");
+ m = m1 = combinehi(m);
+ /* now split off the excess, if any */
+ if ((m->sz - szneed) >= MINSAVE) {
+ m = split(&m1, szneed);
+ mv2freelist(m1);
+ }
+ /* else m is the oversized return block */
+ }
+ else if ((lastsbrk == m->next) &&
+ ((szneed + MINSAVE) <= (m->sz + lastsbrk->sz)) ) {
+ /* lastsbrk is adequate and adjacent so use it */
+ DBGPRTR(EOL " Realloc is using lastsbrk to extend");
+ m = m1 = combinehi(m1);
+ m = split(&m1, szneed);
+ lastsbrk = m1;
+ }
+ else if (ISFREE(m->prev) &&
+ (szneed <= (m->sz + m->prev->sz)) ) {
+ /* the 'prev' block is free and adequate so use it */
+ DBGPRTR(EOL " Realloc is combining low free, moving data");
+ m1 = m->prev;
+ extractfree(m1);
+ m1->sz += m->sz; /* revise the links */
+ if ((m1->next = m->next)) m1->next->prev = m1;
+ /* we are now done with m links, except sz */
+
+ /* This involves copying the data, overlapping */
+ memmove(PTR(m1), PTR(m), m->sz - DATAOFFSET);
+
+ m = m1; /* done with the old m value */
+ /* Is there something leftover */
+ if ((m->sz - szneed) >= MINSAVE) {
+ m = split(&m1, szneed);
+ mv2freelist(m1);
+ }
+ }
+ else if ((b = searchfree(szneed))) {
+ /* An adequate free block exists, copy over, free old */
+ DBGPRTR(EOL " Realloc is using free block, copying");
+ rmvfromfree(m1 = freehdrs[b]);
+ if (m1->sz < szneed + MINSAVE) {
+ m2 = m1;
+ }
+ else {
+ m2 = split(&m1, szneed);
+ mv2freelist(m1);
+ }
+ /* Now m2 is the proposed new block, of the right size */
+ /* links are already revised so copy data from m to m2 */
+ memcpy(PTR(m2), PTR(m), m->sz - DATAOFFSET);
+
+ dofree(m);
+ m = m2;
+ }
+ else if (lastsbrk &&
+ ((szneed + MINSAVE) <= lastsbrk->sz) ) {
+ DBGPRTR(EOL " Realloc is copying into lastsbrk");
+ m = mv2lastsbrk(m, szneed);
+ }
+ /* else malloc new size, copy data, and free old */
+ else if ((m1 = extendsbrk(szneed))) {
+ if (lastsbrk == m->next) {
+ DBGPRTR(EOL " Realloc is now using lastsbrk extended");
+ /* last chance to avoid copying */
+ m = m1 = combinehi(m);
+ m = split(&m1, szneed);
+ lastsbrk = m1;
+ }
+ else {
+ /* At this point lastsbrk is adequate size */
+ /* split off, copy over, and free old */
+ DBGPRTR(EOL " Realloc is making complete new copy");
+ m = mv2lastsbrk(m, szneed);
+ }
+ }
+ else m = NULL; /* failure */
+
+ if (m) p = PTR(m);
+ else {
+ DBGPRTR(dbgbp, ", FAILURE");
+ p = NULL;
+ }
+
+#if DEBUGR
+ DBGPRTR(EOL "returns %p", p);
+ if (m) DBGPRTR("(%lu)", m->sz - DATAOFFSET);
+ DBGEOLN;
+#endif
+
+exeunt: /* label used on realloc of free block */
+ /* and on trap of oversize request */
+ if (!p && ptr && hookptr[malloc_fail_HK])
+ hookptr[malloc_fail_HK](size, ptr);
+ if (hookptr[realloc_exit_HK])
+ hookptr[realloc_exit_HK](size, p);
+
+ return p;
+} /* nrealloc */
+
+/* 1------------------1 */
+
+/* The remaining code is an attempt to graft on the
+ memalign function. It can do with improvement.
+ The idea is to do this without disturbing the
+ already checked and debugged package.
+*/
+
+/* 1------------------1 */
+
+/* Check alignment is a non-zero power of two <= 65536. */
+/* Return 0 if so, else non-zero */
+static inline int invalid(size_t alignment)
+{
+ if (alignment && (alignment <= 65536))
+ return (alignment & (alignment - 1));
+ else return 1; /* 0 is invalid */
+} /* invalid */
+
+/* 1------------------1 */
+
+/* .---------.------------.------.-----------------.
+ <MINSAVE>|<DATAOFFSET>|<????>|<size-DATAOFFSET>|
+ |<DATAOFFSET>|
+ .--to free list--.--- to used blocks ---------.freelist
+*/
+static ulong suitable(memblockp m, ulong size, ulong alignmask)
+{
+ ulong mb, mlen, mtry;
+
+ mb = (ulong)(char *)m; mlen = m->sz;
+ if (0 == ((mtry = mb + DATAOFFSET) & alignmask))
+ return mb; /* miracles happen, exact fit */
+ mtry = (mtry + MINSAVE + alignmask) & (alignmask+1);
+ mtry = mtry - DATAOFFSET;
+ if ((size + (mtry - mb)) <= mlen) return mtry;
+ else return 0;
+} /* suitable */
+
+/* 1------------------1 */
+
+/* Search one chain of free blocks for a suitable one */
+static ulong searchfreechain(int b, ulong size, ulong alignmsk,
+ memblockp *m1p)
+{
+ memblockp m;
+ ulong mtry;
+
+ m = freehdrs[b]; *m1p = NULL;
+ while ((m = freehdrs[b]) && (m != NONE)) {
+ if ((mtry = suitable(m, size, alignmsk))) {
+ *m1p = m;
+ return mtry;
+ }
+ m = m->nextfree;
+ }
+ return 0;
+} /* searchfreechain */
+
+/* 1------------------1 */
+
+/* exhaustive search of free blocks for a suitable one */
+/* We expect this to be a rare operation, so we will */
+/* search the possibly lengthy chains. */
+/* sz here includes the DATAOFFSET which has to end */
+/* up appearing below the returned pointer. */
+static memblockp searchblock(ulong sz, ulong alignmask,
+ memblockp *m1p)
+{
+ int b;
+ ulong mtry;
+
+ b = size2bucket(sz); /* starting point */
+ while (b && (b < NFLISTS)) {
+ if ((mtry = searchfreechain(b, sz, alignmask, m1p)))
+ return (memblockp)mtry;
+ b++;
+ }
+ /* INTERIM MEASURE - this always fails */
+ return NULL;
+} /* searchblock */
+
+/* 1------------------1 */
+
+/* return memory aligned so that the return value is a */
+/* multiple of alignment. Otherwise similar to malloc */
+/* alignment MUST be a power of two, max 65536. */
+void *nmemalign(size_t size, size_t alignment)
+{
+ ulong szneed;
+ memblockp m, m1;
+ ulong alignmask, sbrkxtra;
+
+ m = NULL;
+ if (size < ((ulong)(INT_MAX - 65536)) &&
+ !invalid(alignment)) {
+ /* parameters seem to be valid */
+ if (alignment <= ALIGN) return nmalloc(size);
+ else {
+ if (!size) size++; /* avoid any zero size allotment */
+ alignmask = alignment - 1;
+ szneed = roundup(size);
+ m = searchblock(szneed, alignmask, &m1);
+ if (m) {
+ /* parcel out m1. m is block to return */
+ /* FAILS for now */
+ }
+ else {
+ /* we have to use lastsbrk etc. */
+ /* assign such a block from lastsbrk that any
+ block will be properly assigned. Free that
+ block. Then make the assignment from lastsbrk.
+ */
+ do {
+ sbrkxtra = ((ulong)lastsbrk + alignmask)
+ & alignmask;
+ if (sbrkxtra < DATAOFFSET)
+ sbrkxtra += alignment;
+ m1 = lastsbrk;
+ m = extendsbrk(sbrkxtra + szneed);
+ } while ((m != m1) && m);
+ /* extendsbrk has put any shards in the free list */
+ /* The loop takes care of unexpected sbrk returns */
+ if (m) {
+ /* m + szbrkxtra - DATAOFFSET will now point to
+ a block sufficient to satisfy memalign. The
+ returned value will be at m + szbrkxtra. The
+ block at m, length szbrkxtra, will be put in
+ the free lists. This call will succeed.
+ */
+ m1 = split(&lastsbrk, sbrkxtra - DATAOFFSET);
+ /* leaving m1 marked non-free, and lastsbrk
+ suitable for the memalign call. We can't
+ just move m to the freelist, because it
+ would immediately recombine with lastsbrk
+ */
+ m = split(&lastsbrk, szneed);
+ dofree(m1); /* now the m block is non-free */
+ } /* success */
+ } /* getting from lastsbrk */
+ } /* alignment > ALIGN */
+ } /* valid parameters */
+ if (m) return PTR(m);
+ else return NULL;
+} /* nmemalign */
+
+/* --------- nmalloc.c ----------- */
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ src/libc/ansi/stdlib/nmalloc.h 2003-06-21 18:59:00.000000000 +0000
@@ -0,0 +1,22 @@
+/* -------- nmalloc.h ----------- */
+
+/* Copyright (c) 2003 by Charles B. Falconer
+ Licensed under the terms of the GNU LIBRARY GENERAL PUBLIC
+ LICENSE and/or the terms of COPYING.DJ, all available at
+ <http://www.delorie.com>.
+
+ Bug reports to <mailto:cbfalconer AT worldnet DOT att DOT net>
+*/
+
+#ifndef nmalloc_h
+#define nmalloc_h
+
+#include <stddef.h>
+
+void *nmalloc(size_t sz);
+void nfree(void *ptr);
+void *nrealloc(void *ptr, size_t sz);
+void *nmemalign(size_t sz, size_t alignment);
+
+#endif
+/* -------- nmalloc.h ----------- */
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ src/libc/ansi/stdlib/nmalldbg.c 2003-09-06 13:49:02.000000000 +0000
@@ -0,0 +1,433 @@
+/* -------- malldbg.c --------- */
+
+/* Copyright (c) 2003 by Charles B. Falconer
+ Licensed under the terms of the GNU LIBRARY GENERAL PUBLIC
+ LICENSE and/or the terms of COPYING.DJ, all available at
+ <http://www.delorie.com>.
+
+ Bug reports to <mailto:cbfalconer AT worldnet DOT att DOT net>
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <signal.h> /* raise, SIGABRT */
+
+/* TODO: FIXME: #if 0/#endif is wreakage from nmalloc integration. */
+#if 0
+#include "malldbg.h" /* and sysquery.h */
+#endif
+
+/* This is to be used in conjunction with a version of
+ nmalloc.c compiled with:
+
+ gcc -DNDEBUG -o malloc.o -c nmalloc.c
+*/
+
+static int dbglevel;
+static FILE *dumpfile;
+static int initialized;
+
+/* array of hook function pointers, for cleaner interface */
+/* This is purely a record of values set by sethook() */
+static M_HOOKFN hookptr[HKCOUNT];
+
+/* Number of free lists in system */
+#define NFLISTS ((int)(CHAR_BIT * sizeof(size_t)))
+
+/* Loaded by initsysinfo() to access nmalloc guts */
+static struct _sysquery sysinfo;
+
+/* freehdrsp is pointer to array[NFLISTS] of void* */
+/* These are the headers of the actual free lists */
+/* also loaded by initsysinfo() call */
+static void *(*freehdrsp)[NFLISTS];
+
+#define NONE sysinfo.nilp
+#define lastsbrk freehdrs[0]
+#define memblockp void*
+typedef unsigned int ulong;
+typedef unsigned char byte;
+
+/* conversion and access macros */
+#define DATAOFFSET sysinfo.data
+
+#define MEMBLKp(p) (memblockp)((byte*)(p) - DATAOFFSET)
+#define PTR(m) (void*)((byte*)(m) + DATAOFFSET)
+
+/* This accesses the list of discrete memory chains */
+/* which are created when sbrk returns unexpected value */
+#define SBRKBGN ((void **)(sysinfo.anchors))
+
+/* field access macros (AFTER sysinfo loaded) */
+/* Examples - replace "m->prv" by "fld(m, prv)" */
+/* replace "m->sz" by "szof(m)" */
+/* where field is prvf, nxtf, prv, nxt */
+#define fld(m, field) *((void**)((char*)m + sysinfo.field))
+#define szof(m) *(ulong*)((char*)m + sysinfo.sz)
+#define freehdrs (*freehdrsp)
+
+/* ----------------- */
+
+/* Set up the access to the nmalloc module */
+static void initsysinfo(void)
+{
+ sysinfo = _sysmalloc();
+ freehdrsp = (void*)((byte*)(sysinfo.nilp)-sizeof(void*));
+ if (!dumpfile) dumpfile = stderr;
+ initialized = 1;
+} /* initsysinfo */
+
+/* 1------------------1 */
+
+/* m is the allocated ptr treated by MEMBLKp */
+/* Fouls if sysinfo has not been initialized */
+/* Display info about a particular memory block */
+static void xshowblock(FILE *f, void *m, const char *id)
+{
+ if (NULL == f) return;
+ if (m) {
+ fprintf(f, " %s %p", id, m);
+ fprintf(f, " sz=%u nxt=%p prv=%p nxtf=",
+ szof(m), fld(m, nxt), fld(m, prv));
+ if (fld(m, nxtf)) {
+ if (NONE == fld(m, nxtf))
+ fprintf(f, "NONE prvf=");
+ else
+ fprintf(f, "%p prvf=", fld(m, nxtf));
+ if (NONE == fld(m, prvf))
+ fprintf(f, "NONE");
+ else
+ fprintf(f, "%p", fld(m, prvf));
+ }
+ else fprintf(f, "0");
+ }
+ else
+ fprintf(f, " %s NULL", id);
+ fflush(f); /* to coexist with internal debuggery */
+} /* xshowblock */
+
+/* 1------------------1 */
+
+/* dump the entire free chain group */
+/* Fouls if sysinfo has not been initialized */
+/* See main for sysinfo initialization sequence */
+static void xdumpfree(FILE *f)
+{
+ int i;
+ memblockp m;
+ ulong totfree;
+
+ if (NULL == f) return;
+ totfree = 0;
+ for (i = 0; i < NFLISTS; i++) {
+ if ((m = freehdrs[i])) {
+ fprintf(f, "\n%2d: ", i);
+ do {
+ fprintf(f, "%p(%u)->", m, szof(m));
+ totfree += szof(m);
+ m = fld(m, nxtf);
+ } while (m && (NONE != m));
+ fprintf(f, "0");
+ m = freehdrs[i];
+ while (m && (NONE !=m )) {
+ xshowblock(f, m, "\n ");
+ m = fld(m, nxtf);
+ }
+ }
+ }
+ fprintf(f, "\nTotal Free = %u\n", totfree);
+ fflush(f); /* to coexist with internal debuggery */
+} /* xdumpfree */
+
+/* ----------------- */
+
+/* show the content of a block, flag it as BAD */
+static void showbad(FILE *f, void * m)
+{
+ void *n;
+
+ if ((dbglevel >= 3) && (NULL == f)) f = dumpfile;
+ if (f) {
+ n = fld(m, nxt);
+ xshowblock(f, m, "\n BAD?:");
+ xshowblock(f, n, "\n BAD?:");
+ putc('\n', f);
+ fflush(f);
+ }
+} /* showbad */
+
+/* ----------------- */
+
+/* scans the complete malloc structures to collect
+ info. If f is non-NULL outputs a detailed listing
+ returns NULL unless a bad block is found.
+ Any bad blocks are displayed on dumpfile */
+static void * mallocscan(FILE *f, struct mallinfo *mi)
+{
+ unsigned long totalmem, totalfree, blks, freeblks;
+ void *m, *n, *badblk;
+ int i, valid;
+
+ valid = 1; badblk = NULL;
+ if (!initialized) initsysinfo();
+ mi->smblks = mi->hblks = mi->hblkhd = mi->usmblks = 0;
+ mi->fsmblks = mi->keepcost = 0;
+
+ /* this initialization accounts for the fact that
+ the lastsbrk field will be counted as used */
+ blks = 0; totalmem = 0;
+ mi->hblkhd = totalfree = szof(freehdrs[0]);
+ freeblks = 1;
+
+ for (i = 0; (m = SBRKBGN[i]); i++) {
+ if (f) fprintf(f, "\n\nGroup %d:", i);
+ do {
+ n = fld(m, nxt);
+ if (f) xshowblock(f, m, "\n ");
+ totalmem += szof(m);
+ blks++;
+ if (dbglevel && n)
+ if (m != fld(n, prv)) {
+ valid = 0; badblk = m;
+ showbad(dumpfile, m);
+ if (dbglevel >= 3) {
+ fflush(dumpfile);
+ raise(SIGABRT);
+ }
+ }
+ if (fld(m, nxtf)) { /* a free block */
+ freeblks++;
+ totalfree += szof(m);
+ }
+ } while ((m = n));
+ }
+ if (f) fprintf(f, "\n");
+
+ /* return the collected info in struct mi */
+ mi->arena = totalmem;
+ mi->ordblks = blks;
+ mi->hblks = freeblks;
+ mi->uordblks = totalmem - totalfree
+ - DATAOFFSET * (blks - freeblks);
+ mi->fordblks = totalfree;
+ mi->keepcost = DATAOFFSET * blks;
+ return badblk;
+} /* mallocscan */
+
+/* ----------------- */
+
+/* Return summary details about the arena */
+struct mallinfo mallinfo(void)
+{
+ struct mallinfo mi;
+ int valid;
+
+ if (!initialized) initsysinfo();
+ valid = (NULL == mallocscan(NULL, &mi));
+ return mi;
+} /* mallinfo */
+
+/* ----------------- */
+
+/* Verify the integrity of the arena */
+int malloc_verify(void)
+{
+ struct mallinfo mi;
+ void *badblk;
+
+ if (!initialized) initsysinfo();
+ badblk = mallocscan(NULL, &mi);
+ if (badblk) showbad(dumpfile, badblk);
+ return (NULL == badblk);
+} /* malloc_verify */
+
+/* ----------------- */
+
+/* dump a complete map of the arena */
+void mallocmap(void)
+{
+ struct mallinfo mi;
+ void *badblk;
+
+ if (!initialized) initsysinfo();
+ fprintf(dumpfile, "\nmallocmap at level %d\n", dbglevel);
+ xdumpfree(dumpfile);
+ badblk = mallocscan(dumpfile, &mi);
+} /* mallocmap */
+
+/* ----------------- */
+
+/* Set the file on which to display results */
+FILE *malldbgdumpfile(FILE *fp)
+{
+ FILE *tmp;
+
+ if (!initialized) initsysinfo();
+ tmp = dumpfile;
+ if (fp) dumpfile = fp;
+ else dumpfile = stderr;
+ return tmp;
+} /* malldbgdumpfile */
+
+/* ----------------- */
+
+/* The following three functions are called by hooks */
+
+/* Do malloc_verify function via hook ptr */
+/* No output unless a bad block found */
+/* This is suitable for setting hooks. */
+static void checkarena(size_t sz, void *bk)
+{
+ struct mallinfo mi;
+ void *badblk;
+
+ if (bk) sz = sz; /* anti warn */
+ if (dbglevel > 1) { /* else ignore, safety */
+ if ((badblk = mallocscan(NULL, &mi)))
+ showbad(dumpfile, badblk);
+ }
+} /* checkarena */
+
+/* ----------------- */
+
+static void freenullalert(size_t sz, void *bk)
+{
+ if (bk) sz = sz; /* anti warn */
+ fputs("\n***Freeing NULL\n", dumpfile);
+} /* freenullalert */
+
+/* ----------------- */
+
+static void mallocfailalert(size_t sz, void *bk)
+{
+ if (bk)
+ fprintf(dumpfile,
+ "\n***realloc failed expanding %p to %lu bytes\n",
+ bk, (unsigned long)sz);
+ else
+ fprintf(dumpfile,
+ "\n***malloc failed allocating %lu bytes\n",
+ (unsigned long)sz);
+} /* mallocfailalert */
+
+/* ----------------- */
+
+/* Check that no hooks are presently in use */
+/* uses the locally stored copy of hooks so */
+/* mistakes are possible. Maybe sysinfo */
+/* should contain a pointer to the real tbl */
+/* Our own hooks are allowable */
+static int somehookinuse(void)
+{
+ enum m_hook_kind hk;
+
+ for (hk = malloc_HK; hk < HKCOUNT; hk++) {
+ /* structured for ease of modification */
+ if (NULL == hookptr[hk]) continue;
+ if (checkarena == hookptr[hk]) continue;
+ if (freenullalert == hookptr[hk]) continue;
+ if (mallocfailalert == hookptr[hk]) continue;
+ return 1;
+ }
+ return 0;
+} /* somehookinuse */
+
+/* ----------------- */
+
+/* sethook, bypassing validity checks */
+static M_HOOKFN sethook(enum m_hook_kind which,
+ M_HOOKFN newhook)
+{
+ M_HOOKFN tmp;
+
+ hookptr[which] = newhook; /* keep local record */
+ tmp = (*sysinfo.hookset)(which, newhook);
+ return tmp;
+} /* sethook */
+
+/* ----------------- */
+
+M_HOOKFN mallsethook(enum m_hook_kind which,
+ M_HOOKFN newhook)
+{
+ if (!initialized) initsysinfo();
+ if (which >= HKCOUNT) return NULL; /* validity check */
+ if (dbglevel != 1) return NULL; /* in use, refuse */
+
+ return sethook(which, newhook);
+} /* mallsethook */
+
+/* ----------------- */
+
+static void releaseallhooks(void)
+{
+ enum m_hook_kind hk;
+
+ for (hk = malloc_HK; hk < HKCOUNT; hk++)
+ sethook(hk, NULL);
+} /* freeallhooks */
+
+/* ----------------- */
+
+static inline void setfreenullhook(void)
+{
+ sethook(free_null_HK, freenullalert);
+} /* setfreenullhook */
+
+/* ----------------- */
+
+static inline void setmallocfailhook(void)
+{
+ sethook(malloc_fail_HK, mallocfailalert);
+} /* setmallocfailhook */
+
+/* ----------------- */
+
+static inline void setverifyhooks(void)
+{
+ sethook(malloc_HK, checkarena);
+ sethook(free_HK, checkarena);
+ sethook(realloc_HK, checkarena);
+} /* setverifyhooks */
+
+/* ----------------- */
+
+/* level action
+ 0 Only passive checks
+ 1 Passive checks, hook setting enabled
+ 2 Checks on each alloc/realloc, no hooks allowed
+ 3 Same, but aborts if fault found, signals malloc_fail
+ 4 Same, but signals on free(NULL)
+
+ A level value outside 0..4 is rejected.
+ Returns current debug_level (before any change).
+*/
+int malloc_debug(int level)
+{
+ int oldlevel;
+
+ if (!initialized) initsysinfo();
+ oldlevel = dbglevel;
+ if ((level >= 0) && (level <= 4) && (level != oldlevel)) {
+ if ((oldlevel < 2) && (level >= 2)) {
+ if (somehookinuse()) { /* refuse */
+ fprintf(dumpfile, "\n***malldbglvl refused\n");
+ return oldlevel;
+ }
+ }
+ /* Either all hooks free or our own, or level < 2 */
+ /* The change is feasible, level is changed and valid */
+ dbglevel = level;
+ releaseallhooks();
+ switch (level) { /* falling through */
+case 4: setfreenullhook();
+case 3: setmallocfailhook();
+case 2: setverifyhooks();
+default: break;
+ } /* switch (level) */
+ } /* valid level change */
+ return oldlevel;
+} /* malloc_debug */
+
+/* -------- malldbg.c ----------- */
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ src/libc/ansi/stdlib/nmalloc.txt 2003-05-01 17:55:50.000000000 +0000
@@ -0,0 +1,56 @@
+This is intended to be prepared via the makefile.
+
+To create a testable debug version, enter "make tnmalloc".
+
+To create an object module for use in actual systems, enter
+"make malloc.o". This will have the normal names, malloc, free,
+realloc.
+
+To create a version for profiling, enter "make tmallocp". The
+module mallocp.o created is generally suitable for profiling,
+and has the usual names.
+
+To create a cross-reference, enter "make xrf" (under DOS boxes
+only)
+
+The various compile time flags are set up appropriately. In
+particular malloc.o should be immediately ready for inclusion
+in a library. It may be desirable to "strip" debugging
+information from the module.
+
+"make all" creates everything, "make clean" wipes them out.
+
+The little test 'evilalgo' can be linked to either the stock
+malloc system, or to the malloc.o generated above. Then time
+execution for an argument of 200000. The original library will
+probably fail where nmalloc will succeed, and nmalloc will do it
+a lot faster.
+
+To create the modules for the malloc_debug system, enter
+"make tmalldbg.exe". Once this is done other systems with the
+debug mechanism can be created by linking malldbg and hookmem
+(.o) ahead of the normal runtime library. The system using it
+must #include malldbg.h.
+
+make zip doesn't work properly.
+
+The integration of the malldbg system is not complete, but
+should function correctly. Future changes are expected to be
+fairly cosmetic, and improve performance slightly. The
+hookmem.h file will disappear and the sysquery action will be
+modified.
+
+2003-05-01
+
+The malldbg system now appears complete. Documentation in
+info source form is included in nmalloc.txh. I find the
+following command useful for creating a viewable or printable
+(but imperfect) .htm doc file:
+
+makeinfo --force --no-split --no-validate --html
+ -o nmalloc.htm nmalloc.txh
+
+(Above is all one line)
+
+
+Bug reports to cbfalconer AT worldnet DOT att DOT net.
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ tests/libc/ansi/stdlib/evilalgo.c 2003-09-06 13:36:40.000000000 +0000
@@ -0,0 +1,44 @@
+/* From djgpp mail list - an evil algorithm */
+/* This shows up the difference between DJGPP2.03 malloc and
+ nmalloc, both in speed and in efficiency of memory use.
+ Snaffled/cleaned up for testing use by C.B. Falconer.
+
+ To use the new malloc, simply link it with the object module.
+*/
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef struct {
+ char af[10];
+ char name[10];
+} record;
+
+record **dt, *d;
+
+int main(int argc, char ** argv)
+{
+#if 0
+ unsigned long n = 1000; /* was 200000L */
+#else
+ /*
+ * <rich AT phekda DOT freeserve DOT co DOT uk>: 1000 was OK; 2000 showed
+ * pathological behaviour with the old malloc on my development box,
+ * which has 640MB of memory.
+ */
+ unsigned long n = 2000;
+#endif
+ unsigned int count;
+ void *v;
+
+ if (argc > 1) n = strtoul(argv[1], NULL, 10);
+
+ dt = NULL;
+ for (count = 0; count < n; count++){
+ if ((v = realloc(dt, (count + 1) * sizeof *dt))) dt = v;
+ else break;
+ if (!(d = dt[count] = calloc(10, sizeof *d))) break;
+ if (!(count & 0xfff)) putc('*', stderr);
+ }
+ printf("\ncount=%d\n", count);
+ return(0);
+} /* evilalgo */
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ tests/libc/ansi/stdlib/tnmalloc/makefile 2003-09-07 10:56:30.000000000 +0000
@@ -0,0 +1,8 @@
+TOP=../../..
+
+SRC += tnmalloc.c
+SRC += tnmaldbg.c
+
+EXTRA_LIBS += cokusmt.o
+
+include $(TOP)/../makefile.inc
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ tests/libc/ansi/stdlib/tnmalloc/cokusmt.c 2002-01-09 10:23:40.000000000 +0000
@@ -0,0 +1,185 @@
+/* FILE cokusmt.c */
+/* This is a miniscule cleanup of the source downloaded from: */
+/* http://www.math.keio.ac.jp/~matumoto/ver980409.html */
+
+/* This is the "Mersenne Twister" random number generator MT19937,
+// which generates pseudorandom integers uniformly distributed in
+// 0..(2^32 - 1) starting from any odd seed in 0..(2^32 - 1). This
+// version is a recode by Shawn Cokus (Cokus AT math DOT washington DOT edu) on
+// March 8, 1998 of a version by Takuji Nishimura (who had suggestions
+// from Topher Cooper and Marc Rieffel in July-August 1997).
+//
+// Effectiveness of the recoding (on Goedel2.math.washington.edu, a
+// DEC Alpha running OSF/1) using GCC -O3 as a compiler: before
+// recoding: 51.6 sec. to generate 300 million random numbers; after
+// recoding: 24.0 sec. for the same (i.e., 46.5% of original time),
+// so speed is now about 12.5 million random number generations per
+// second on this machine.
+//
+// According to URL <http://www.math.keio.ac.jp/~matumoto/emt.html>
+// (and paraphrasing a bit in places), the Mersenne Twister is
+// "designed with consideration of the flaws of various existing
+// generators," has a period of 2^19937 - 1, gives a sequence that
+// is 623-dimensionally equidistributed, and "has passed many
+// stringent tests, including the die-hard test of G. Marsaglia and
+// the load test of P. Hellekalek and S. Wegenkittl." It is efficient
+// in memory usage (typically using 2506 to 5012 bytes of static data,
+// depending on data type sizes, and the code is quite short as well).
+// It generates random numbers in batches of 624 at a time, so the
+// caching and pipelining of modern systems is exploited. It is also
+// divide- and mod-free.
+//
+// This library is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Library General Public License
+// as published by the Free Software Foundation (either version 2 of
+// the License or, at your option, any later version). This library
+// is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY, without even the implied warranty of MERCHANTABILITY or
+// FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General
+// Public License for more details. You should have received a copy
+// of the GNU Library General Public License along with this library;
+// if not, write to the Free Software Foundation, Inc., 59 Temple
+// Place, Suite 330, Boston, MA 02111-1307, USA.
+//
+// The code as Shawn received it included the following notice:
+//
+// Copyright (C) 1997 Makoto Matsumoto and Takuji Nishimura. When
+// you use this, send an e-mail to <matumoto AT math DOT keio DOT ac DOT jp> with
+// an appropriate reference to your work.
+//
+// It would be nice to CC: <Cokus AT math DOT washington DOT edu> when you write.
+*/
+
+/* uint32 must be an unsigned integer type capable of holding at least
+// 32 bits; exactly 32 should be fastest, but 64 is better on an Alpha
+// with GCC at -O3 optimization so try your options and see what's
+// best for you.
+*/
+
+#include "cokusmt.h"
+
+typedef unsigned long uint32;
+
+
+#define N (624) /* length of state vector */
+#define M (397) /* a period parameter */
+#define K (0x9908B0DFU) /* a magic constant */
+#define hiBit(u) ((u) & 0x80000000U) /* mask all but highest */
+ /* bit of u */
+#define loBit(u) ((u) & 0x00000001U) /* mask all but lowest */
+ /* bit of u */
+#define loBits(u) ((u) & 0x7FFFFFFFU) /* mask off the highest */
+ /* bit of u */
+#define mixBits(u, v) (hiBit(u) | loBits(v)) /* move hi bit of u */
+ /* to hi bit of v */
+
+static uint32 state[N+1]; /* state vector+1 to not violate ANSI C */
+static uint32 *next; /* next random value computed from here */
+static int left = -1; /* can *next++ this many times before */
+ /* reloading */
+
+
+/* We initialize state[0..(N-1)] via the generator
+//
+// x_new = (69069 * x_old) mod 2^32
+//
+// from Line 15 of Table 1, p. 106, Sec. 3.3.4 of Knuth's
+// _The Art of Computer Programming_, Volume 2, 3rd ed.
+//
+// Notes (SJC): I do not know what the initial state requirements
+// of the Mersenne Twister are, but it seems this seeding generator
+// could be better. It achieves the maximum period for its modulus
+// (2^30) iff x_initial is odd (p. 20-21, Sec. 3.2.1.2, Knuth); if
+// x_initial can be even, you have sequences like 0, 0, 0, ...;
+// 2^31, 2^31, 2^31, ...; 2^30, 2^30, 2^30, ...; 2^29, 2^29 + 2^31,
+// 2^29, 2^29 + 2^31, ..., etc. so I force seed to be odd below.
+//
+// Even if x_initial is odd, if x_initial is 1 mod 4 then
+//
+// low bit of x is always 1,
+// next-to-low bit of x is always 0,
+// 2nd-from-low bit of x alternates ... 0 1 0 1 0 1 0 1 ... ,
+// 3rd-from-low bit of x 4-cycles ... 0 1 1 0 0 1 1 0 ... ,
+// 4th-from-low bit of x has 8-cycle ... 0 0 0 1 1 1 1 0 ... ,
+// ...
+//
+// and if x_initial is 3 mod 4 then
+//
+// low bit of x is always 1,
+// next-to-low bit of x is always 1,
+// 2nd-from-low bit of x alternates ... 0 1 0 1 0 1 0 1 ... ,
+// 3rd-from-low bit of x 4-cycles ... 0 0 1 1 0 0 1 1 ... ,
+// 4th-from-low bit of x has 8-cycle ... 0 0 1 1 1 1 0 0 ... ,
+// ...
+//
+// The generator's potency (min. s>=0 with (69069-1)^s = 0
+// mod 2^32) is 16, which seems to be alright by p. 25, Sec.
+// 3.2.1.3 of Knuth. It also does well in the dimension 2..5
+// spectral tests, but it could be better in dimension 6
+// (Line 15, Table 1, p. 106, Sec. 3.3.4, Knuth).
+//
+// Note that the random number user does not see the values
+// generated here directly since reloadMT() will always munge
+// them first, so maybe none of all of this matters. In fact,
+// the seed values made here could even be extra-special
+// desirable if the Mersenne Twister theory says so-- that's
+// why the only change I made is to restrict to odd seeds.
+*/
+void seedMT(uint32 seed)
+{
+ register uint32 x = (seed | 1U) & 0xFFFFFFFFU,
+ *s = state;
+ register int j;
+
+ for (left = 0, *s++ = x, j = N;
+ --j;
+ *s++ = (x *= 69069U) & 0xFFFFFFFFU);
+} /* seedMT */
+
+
+static uint32 reloadMT(void)
+{
+ register uint32
+ *p0 = state,
+ *p2 = state + 2,
+ *pM = state + M,
+ s0,
+ s1;
+ register int j;
+
+ if (left < -1) seedMT(4357U); /* Autoseed on first use */
+
+ left = N - 1; next = state + 1;
+ for (s0 = state[0], s1 = state[1], j = N - M + 1;
+ --j;
+ s0 = s1, s1 = *p2++)
+ *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
+
+ for (pM = state, j = M;
+ --j;
+ s0 = s1, s1 = *p2++)
+ *p0++ = *pM++ ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
+
+ s1 = state[0];
+ *p0 = *pM ^ (mixBits(s0, s1) >> 1) ^ (loBit(s1) ? K : 0U);
+ s1 ^= (s1 >> 11);
+ s1 ^= (s1 << 7) & 0x9D2C5680U;
+ s1 ^= (s1 << 15) & 0xEFC60000U;
+ return (s1 ^ (s1 >> 18));
+} /* reloadMT */
+
+
+uint32 randomMT(void)
+{
+ uint32 y;
+
+ if (--left < 0)
+ return(reloadMT());
+
+ y = *next++;
+ y ^= (y >> 11);
+ y ^= (y << 7) & 0x9D2C5680U;
+ y ^= (y << 15) & 0xEFC60000U;
+ return (y ^ (y >> 18));
+} /* randomMT */
+
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ tests/libc/ansi/stdlib/tnmalloc/cokusmt.h 2002-11-07 10:09:54.000000000 +0000
@@ -0,0 +1,17 @@
+/* file cokusMT.h */
+
+#ifndef cokus_h
+#define cokus_h
+
+#include <limits.h>
+
+#if ULONG_MAX != 4294967295UL
+ #error System long word size not suitable for cokusMT
+#endif
+
+#define ranMTMAX ULONG_MAX
+
+void seedMT(unsigned long seed);
+unsigned long randomMT(void);
+
+#endif /* cokus_h */
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ tests/libc/ansi/stdlib/tnmalloc/tnmalloc.c 2003-09-06 14:36:56.000000000 +0000
@@ -0,0 +1,609 @@
+/* ------- tstmalloc -------- */
+
+/* Copyright (c) 2003 by Charles B. Falconer
+ Licensed under the terms of the GNU LIBRARY GENERAL PUBLIC
+ LICENSE and/or the terms of COPYING.DJ, all available at
+ <http://www.delorie.com>.
+
+ Bug reports to <mailto:cbfalconer AT worldnet DOT att DOT net>
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+#include <math.h>
+#include <unistd.h> /* write */
+
+#include "fakesbrk.h"
+#include "cokusMT.h"
+
+/* TODO: FIXME: #if 0/#endif is wreakage from nmalloc integration. */
+#if 0
+#include "sysquery.h"
+#endif
+
+#define NDEBUG
+
+/* NDEBUG allows this to be used for profiling malloc.o */
+#ifndef NDEBUG
+# include "nmalloc.h"
+# define INTERVAL 10 /* for emitting free list dumps */
+#else
+# define nmalloc malloc
+# define nfree free
+# define nrealloc realloc
+# define INTERVAL 1000 /* for emitting free list dumps */
+#endif
+
+void test01(int n);
+void test02(int n);
+void test03(int n);
+void test04(int n);
+void test05(int n);
+void test06(int n);
+void test07(int n);
+void test08(int n);
+void test09(int n);
+void showijk(int i, int j, int k);
+void showsysquery(void);
+void inject(int i);
+double gaussrand(void);
+double gausspos(void);
+
+/* Magic 1500 below must be > MINSBRK in nmalloc.c */
+enum {FAKESIZE = 1234567,
+ HIFAKESZ = 1500,
+ HIFAKE = FAKESIZE - HIFAKESZ,
+ NFLISTS = (int)(CHAR_BIT * sizeof(size_t))
+ };
+
+char fakearea[FAKESIZE];
+
+int notquiet; /* 0 suppresses most output in this module */
+
+/* 1------------------1 */
+
+/* we can fool with this to generate test cases */
+/* If I could only figure a way to peg the addresses */
+/* the test runs would be a good regression test. */
+void *fakesbrk(int delta)
+{
+static char *unused = fakearea;
+static char *hiarea = fakearea + HIFAKE;
+char *next, *p;
+
+ if (hiarea && (delta >= 32) && (delta < HIFAKESZ)) {
+ /* return something above normal use to test
+ action under decreasing sbrk values */
+ p = hiarea;
+ hiarea = 0;
+ return (void *)p;
+ }
+ /* otherwise just act normally */
+ next = unused + delta;
+ if ((unsigned) next > HIFAKE) return (void *)-1;
+ else {
+ p = unused;
+ unused = next;
+ return (void *)p;
+ }
+} /* fakesbrk */
+
+/* =====================================================
+ This portion is an example of using the _sysmalloc()
+ call to access the inner workings of the malloc pkg.
+ Note the exact parallel between these routines and
+ the corresponding ones in nmalloc.c.
+ =====================================================
+*/
+
+/* 1------------------1 */
+
+static struct _sysquery sysinfo;
+void *(*freehdrsp)[NFLISTS];
+
+
+#define NONE sysinfo.nilp
+#define lastsbrk freehdrs[0]
+#define memblockp void*
+typedef unsigned int ulong;
+typedef unsigned char byte;
+
+/* conversion and access macros */
+#define DATAOFFSET sysinfo.data
+
+#define MEMBLKp(p) (memblockp)((byte*)(p) - DATAOFFSET)
+#define PTR(m) (void*)((byte*)(m) + DATAOFFSET)
+
+/* field access macros (AFTER sysinfo loaded) */
+/* Examples - replace "m->prv" by "fld(m, prv)" */
+/* replace "m->sz" by "szof(m)" */
+/* where field is prvf, nxtf, prv, nxt */
+#define fld(m, field) *((void**)((char*)m + sysinfo.field))
+#define szof(m) *(ulong*)((char*)m + sysinfo.sz)
+#define freehdrs (*freehdrsp)
+
+/* 1------------------1 */
+
+/* Fouls if sysinfo has not been initialized */
+/* See main for sysinfo initialization sequence */
+void showsysquery(void)
+{
+ printf("sysinfo is: nil = %p\n"
+ " DATAOFFSET = %d\n"
+ " gdlo offset = %d\n"
+ " sz offset = %d\n"
+ " prvf offset = %d\n"
+ " nxtf offset = %d\n"
+ " nxt offset = %d\n"
+ " prv offset = %d\n"
+ " ohead = %d\n"
+ " &freehdrs = %p\n"
+ " &anchors = %p\n"
+ " &hookset() = %p\n",
+ sysinfo.nilp, sysinfo.data, sysinfo.gdlo,
+ sysinfo.sz, sysinfo.prvf, sysinfo.nxtf,
+ sysinfo.nxt, sysinfo.prv, sysinfo.ohead,
+ freehdrs, sysinfo.anchors, sysinfo.hookset);
+
+} /* showsysquery */
+
+/* 1------------------1 */
+
+/* m is the allocated ptr treated by MEMBLKp */
+/* Fouls if sysinfo has not been initialized */
+/* See main for sysinfo initialization sequence */
+static void xshowblock(void *m, const char *id)
+{
+ if (m) {
+ printf(" %s %p", id, m);
+ printf(" sz=%u nxt=%p prv=%p nxtf=",
+ szof(m), fld(m, nxt), fld(m, prv));
+ if (fld(m, nxtf)) {
+ if (NONE == fld(m, nxtf))
+ printf("NONE prvf=");
+ else
+ printf("%p prvf=", fld(m, nxtf));
+ if (NONE == fld(m, prvf))
+ printf("NONE");
+ else
+ printf("%p", fld(m, prvf));
+ }
+ else printf("0");
+ }
+ else
+ printf(" %s NULL", id);
+ fflush(stdout); /* to coexist with internal debuggery */
+} /* xshowblock */
+
+/* 1------------------1 */
+
+/* dump the entire free chain group */
+/* Fouls if sysinfo has not been initialized */
+/* See main for sysinfo initialization sequence */
+static void xdumpfree(void)
+{
+ int i;
+ memblockp m;
+ ulong totfree;
+
+ totfree = 0;
+ for (i = 0; i < NFLISTS; i++) {
+ if ((m = freehdrs[i])) {
+ printf("\n%2d: ", i);
+ do {
+ printf("%p(%u)->", m, szof(m));
+ totfree += szof(m);
+ m = fld(m, nxtf);
+ } while (m && (NONE != m));
+ printf("0");
+ m = freehdrs[i];
+ while (m && (NONE !=m )) {
+ xshowblock(m, "\n ");
+ m = fld(m, nxtf);
+ }
+ }
+ }
+ printf("\nTotal Free = %u\n", totfree);
+ fflush(stdout); /* to coexist with internal debuggery */
+} /* xdumpfree */
+
+/* ========== End of debuggery examples ============= */
+/* ============== Start of tests ==================== */
+
+/* Just allocate increasing sizes */
+void test01(int n)
+{
+ int i;
+ void *m;
+
+ for (i = 0; i < n; i++) m = nmalloc(65 * i);
+} /* test01 */
+
+/* 1------------------1 */
+
+/* allocate increasing sizes, freeing what was allocated
+ 10 items earlier. Monitor free list every 10th. Free
+ everything at end. Perturb sbrk return values.
+*/
+void test02(int n)
+{
+ int i;
+ void *m[10] = {0};
+
+ for (i = 0; i < n; i++) {
+ nfree(m[i % 10]);
+ m[i % 10] = nmalloc(15 * i);
+ if (0 == (i % 30)) (void)fakesbrk(3);
+ if ( (INTERVAL - 1) == (i % INTERVAL )
+ && notquiet)
+ xdumpfree();
+ }
+ for (i = 0; i < 10; i++) nfree(m[i]);
+ xdumpfree();
+} /* test02 */
+
+/* 1------------------1 */
+
+enum {STDIN = 0, STDOUT, STDERR, STDAUX, STDPRN}; /* handles */
+
+/* made to be compatible with nmalloc internal debugger */
+void inject(int i)
+{
+#ifndef NDEBUG
+ char buf[20];
+
+ sprintf(buf, "%03d: ", i);
+ write(STDOUT, buf, strlen(buf));
+#endif
+} /* inject */
+
+/* 1------------------1 */
+
+/* allocate random sizes, free, finally abort. Perturb sbrk */
+void test03(int n)
+{
+ int i;
+ void *m[10] = {0};
+
+ if (0 == n) n = 10;
+
+ for (i = 0; i < n; i++) {
+ if (m[i % 10]) inject(i);
+ nfree(m[i % 10]);
+ if (notquiet) inject(i);
+ m[i % 10] = nmalloc(randomMT() % 10000);
+
+ if (0 == i) xshowblock(MEMBLKp(m[0]), "\n*testing*");
+
+ if (0 == (i % 30)) (void)fakesbrk(3);
+ if ( (INTERVAL - 1) == (i % INTERVAL )
+ && notquiet)
+ xdumpfree();
+ }
+ for (i = 0; i < 10; i++) {
+ if (m[i] && notquiet) inject(i);
+ nfree(m[i]);
+ }
+ xdumpfree();
+ if (n & 1) {
+ printf("\nDeliberately refreeing pointer, should abort\n\n");
+ fflush(stdout);
+ nfree(m[0]);
+ }
+} /* test03 */
+
+/* 1------------------1 */
+
+/* allocate random sizes, realloc, free. Perturb sbrk */
+void test04(int n)
+{
+ int i;
+ void *m[10] = {0};
+ void *temp;
+
+ for (i = 0; i < n; i++) {
+ if (m[i % 10]) inject(i);
+ nfree(m[i % 10]);
+ if (notquiet) inject(i);
+ m[i % 10] = nmalloc(randomMT() % 10000);
+ if (notquiet) inject(i);
+ temp = nrealloc(m[i % 10], randomMT() % 10000);
+ if (temp) m[i % 10] = temp;
+ if (0 == (i % 30)) (void)fakesbrk(3);
+ if ( (INTERVAL - 1) == (i % INTERVAL)
+ && notquiet)
+ xdumpfree();
+ }
+ for (i = 0; i < 10; i++) {
+ if (m[i] && notquiet) inject(i);
+ nfree(m[i]);
+ }
+ xdumpfree();
+} /* test04 */
+
+/* 1------------------1 */
+
+/* made to be compatible with nmalloc internal debugger */
+void showijk(int i, int j, int k)
+{
+#ifndef NDEBUG
+ char buf[20];
+
+ sprintf(buf, "%03d:%d:%d ", i, j, k);
+ write(STDOUT, buf, strlen(buf));
+#endif
+} /* showijk */
+
+/* 1------------------1 */
+
+/* free 10 items, allocate 10 random sizes, realloc 10 random */
+/* Much like test 4, but a different sequence. No sbrk perturb */
+void test05(int n)
+{
+ int i, j, k, ix;
+ void *m[10] = {0};
+ void *temp;
+
+ for (i = 0; i < n; i++) {
+ j = (i / 10) % 3; /* 0, 1, or 2 */
+ k = (i % 10);
+ ix = k + 10 * (i / 30);
+ if (0 == j) {
+ if (notquiet) showijk(i, j, k);
+ temp = nrealloc(m[k], randomMT() % 10000);
+ if (temp) m[k] = temp;
+ if ( (INTERVAL - 1) == (i % INTERVAL)
+ && notquiet)
+ xdumpfree();
+ }
+ if (1 == j) {
+ if (m[k]) {
+ if (notquiet) showijk(i, j, k);
+ nfree(m[k]);
+ m[k] = NULL;
+ }
+ if ( (INTERVAL - 1) == (i % INTERVAL)
+ && notquiet)
+ xdumpfree();
+ }
+ if (2 == j) {
+ if (notquiet) showijk(i, j, k);
+ m[k] = nmalloc(randomMT() % 10000);
+ if ( (INTERVAL - 1) == (i % INTERVAL)
+ && notquiet)
+ xdumpfree();
+ }
+ if (0 == i) (void)fakesbrk(3); /* make 2 blocks */
+ }
+ for (i = 0; i < 10; i++) {
+ if (m[i]) {
+ if (notquiet) inject(i);
+ nfree(m[i]);
+ }
+ }
+ xdumpfree();
+} /* test05 */
+
+/* 1------------------1 */
+
+/* reallocate random sizes continuously */
+void test06(int n)
+{
+ int i;
+ void *m[10] = {0};
+ void *temp;
+
+ for (i = 0; i < n; i++) {
+ if (notquiet) inject(i);
+ temp = nrealloc(m[i % 10], randomMT() % 10000);
+ if (temp) m[i % 10] = temp;
+ if ( (INTERVAL - 1) == (i % INTERVAL)
+ && notquiet)
+ xdumpfree();
+ }
+ for (i = 0; i < 10; i++) {
+ if (m[i] && notquiet) inject(i);
+ nfree(m[i]);
+ }
+ xdumpfree();
+} /* test06 */
+
+/* 1------------------1 */
+
+/* reallocate random sizes continuously, check data unharmed */
+/* This writes over all allocated memory, so it is a fairly */
+/* good test that nothing is out of place. */
+void test07(int n)
+{
+ int i, j, k;
+ void *m[10] = {0};
+ int sz[10] = {0};
+ int newsz, minsz;
+ unsigned char *p;
+
+ void *temp;
+
+ for (i = 0; i < n; i++) {
+ if (notquiet) inject(i);
+ k = i % 10;
+ minsz = newsz = randomMT() % 10000;
+ if (sz[k] < minsz) minsz = sz[k];
+ if (m[k]) {
+ p = m[k];
+ for (j = 0; j < sz[k]; j++) {
+ /* null loop for initial access */
+ p[j] = j & 0xff;
+ }
+ }
+ temp = nrealloc(m[k], newsz);
+ if (temp) {
+ p = m[k] = temp;
+ sz[k] = newsz;
+ for (j = 0; j < minsz; j++) {
+ /* null loop for initial access */
+ if (p[j] != (j & 0xff)) {
+ printf("Data failure at index %d!!\n", j);
+ printf("is %d should be %d\n",
+ p[j], j & 0xff);
+ fflush(stdout);
+ exit(EXIT_FAILURE);
+ }
+ }
+ }
+ if ( (INTERVAL - 1) == (i % INTERVAL)
+ && notquiet)
+ xdumpfree();
+ }
+ for (i = 0; i < 10; i++) {
+ if (m[i] && notquiet) inject(i);
+ nfree(m[i]);
+ }
+ xdumpfree();
+} /* test07 */
+
+/* 1------------------1 */
+
+/* From the C-FAQ, slightly modified
+ * Most likely value is 0, + or - 5 are rare
+ */
+double gaussrand(void)
+{
+ static double V2, X;
+ static int phase = 0;
+ double Y, U1, U2, V1, S;
+
+ if (phase) Y = V2 * X;
+ else {
+ do {
+ /*
+ * Cast via long to work around a compiler bug. gcc falsely
+ * complains. See: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=6980
+ */
+ U1 = (double)(long)randomMT() / ranMTMAX;
+ U2 = (double)(long)randomMT() / ranMTMAX;
+
+ V1 = 2 * U1 - 1;
+ V2 = 2 * U2 - 1;
+ S = V1 * V1 + V2 * V2;
+ } while (S >= 1 || S == 0);
+
+ Y = V1 * (X = sqrt(-2 * log(S) / S));
+ }
+ phase = 1 - phase;
+ return Y;
+} /* gaussrand */
+
+/* 1------------------1 */
+
+/* maps gaussrand -inf .. 0 into 0..1 and
+ * 0 .. +inf into 1..inf.
+ * Most likely value is slightly less than 1
+ * 5.0 is fairly rare, 120.0 extremely rare
+ */
+double gausspos(void)
+{
+ return exp(gaussrand());
+} /* gausspos */
+
+/* 1------------------1 */
+
+typedef struct node {
+ struct node *next;
+ char *wastage;
+} node, *nodeptr;
+
+/* Under development for long term thrashing */
+void test08(int n)
+{
+ int i;
+ nodeptr root, temp;
+ size_t sz, totalsz;
+
+ printf("Under development\n");
+ root = NULL; totalsz = 0;
+ for (i = 0; i < n; i++) {
+ /* form singly linked list of various sizes */
+ if (!(temp = nmalloc(sizeof *temp))) {
+ fprintf(stderr, "malloc node failed\n");
+ exit(EXIT_FAILURE);
+ }
+ else {
+ sz = (int)(1 + gausspos()) * 32;
+ if (!(temp->wastage = nmalloc(sz))) {
+ fprintf(stderr, "malloc wastage failed\n");
+ exit(EXIT_FAILURE);
+ }
+ else {
+ temp->next = root;
+ root = temp;
+ totalsz += sz;
+ }
+ }
+ } /* for, formed base list */
+} /* test08 */
+
+/* 1------------------1 */
+
+/* Under development for long term thrashing */
+void test09(int n)
+{
+ printf("Under development\n");
+} /* test09 */
+
+/* 1------------------1 */
+
+int main(int argc, char *argv[])
+{
+ unsigned long t = 0, n = 0;
+
+ if (argc > 1) t = strtoul(argv[1], NULL, 10);
+ if (argc > 2) n = strtoul(argv[2], NULL, 10);
+ notquiet = (argc < 4);
+
+ if (0 == n) n = 10;
+
+ printf("test%02lu-%lu\n", t, n);
+ fflush(stdout); /* Needed to coexist with debug pkg */
+
+ sysinfo = _sysmalloc();
+ freehdrsp = (void*)((byte*)(sysinfo.nilp)-sizeof(void*));
+
+ (void) fakesbrk(1); /* start it off on odds */
+ switch (t) {
+case 1: test01(n); break;
+case 2: test02(n); break;
+case 3: test03(n); break;
+case 4: test04(n); break;
+case 5: test05(n); break;
+case 6: test06(n); break;
+case 7: test07(n); break;
+case 8: test08(n); break;
+case 9: test09(n); break;
+default:
+ printf("Usage: tnmalloc [testnumber [quantity [quiet]]]\n");
+ printf("fakearea at %p through %p (was f594)\n",
+ &fakearea, &fakearea[FAKESIZE-1]);
+ printf("CHAR_BIT * sizeof(size_t) = %lu\n",
+ (unsigned long)(CHAR_BIT * sizeof(size_t)));
+ showsysquery();
+ printf(
+ "Test Purpose\n"
+ " 1 malloc only\n"
+ " 2 malloc and free\n"
+ " 3 malloc(random), free, aborts for odd quantity\n"
+ " 4 malloc(random), realloc(random), and free\n"
+ " 5 malloc(10 random), realloc(10 random) and free 10\n"
+ " 6 realloc(random), monitor free lists\n"
+ " 7 realloc(random), check data unharmed\n"
+ " 8 run a long faked sequence, not complete\n"
+ " 9 test memalign operation\n"
+ "Any entry for quiet suppresses free list dumps\n"
+ );
+ break;
+ } /* switch (t) */
+ return 0;
+} /* main */
+
+/* ------- tstmalloc -------- */
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ tests/libc/ansi/stdlib/tnmalloc/tnmaldbg.c 2003-09-06 14:47:32.000000000 +0000
@@ -0,0 +1,432 @@
+/* ------- tmalldbg -------- */
+
+/* Copyright (c) 2003 by Charles B. Falconer
+ Licensed under the terms of the GNU LIBRARY GENERAL PUBLIC
+ LICENSE and/or the terms of COPYING.DJ, all available at
+ <http://www.delorie.com>.
+
+ Bug reports to <mailto:cbfalconer AT worldnet DOT att DOT net>
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+
+/* TODO: FIXME: #if 0/#endif is wreakage from nmalloc integration. */
+#if 0
+#include "malldbg.h"
+#include "sysquery.h"
+#endif
+
+/*#include <string.h>
+#include <math.h>
+#include "cokusMT.h"
+*/
+
+/* Number of free lists in system */
+#define NFLISTS ((int)(CHAR_BIT * sizeof(size_t)))
+
+typedef struct testnode {
+ struct testnode *next;
+ char string[30];
+} testnode;
+
+testnode *root;
+
+int notquiet;
+
+void test01(unsigned long n);
+void test02(unsigned long n);
+void test03(unsigned long n);
+void test04(unsigned long n);
+void test05(unsigned long n);
+void test06(unsigned long n);
+void test07(unsigned long n);
+void test08(unsigned long n);
+void showsysquery(void);
+void printinfo(struct mallinfo *info);
+void foul2ndlast(testnode *node);
+
+/* 1------------------1 */
+
+/* Build something to display the structure of */
+/* a linked list headed by the global var 'root' */
+static testnode *buildlist(int items, testnode *node)
+{
+ testnode *this;
+
+ while (items) {
+ this = malloc(items + sizeof *this);
+ this->next = node;
+ node = this;
+ sprintf(this->string, "item #%d", items);
+ items--;
+ }
+ return node;
+} /* buildlist */
+
+/* 1------------------1 */
+
+/* retains 1 in three of original list,
+ Ex: a -> b -> c -> d ::= a -> d, b & c freed
+ This allows exercizing the free list compaction */
+static void prunelist(testnode *node)
+{
+ testnode *this, *keep;
+
+ while (node) {
+ keep = node;
+ this = node->next;
+ if ((node = this)) {
+ this = node->next;
+ free(node);
+ if ((node = this)) {
+ this = node->next;
+ free(node);
+ node = this;
+ }
+ }
+ keep->next = node;
+ }
+} /* prunelist */
+
+/* 1------------------1 */
+
+static struct _sysquery sysinfo;
+void *(*freehdrsp)[NFLISTS];
+
+
+#define NONE sysinfo.nilp
+#define lastsbrk freehdrs[0]
+#define memblockp void*
+typedef unsigned int ulong;
+typedef unsigned char byte;
+
+/* conversion and access macros */
+#define DATAOFFSET sysinfo.data
+
+#define MEMBLKp(p) (memblockp)((byte*)(p) - DATAOFFSET)
+#define PTR(m) (void*)((byte*)(m) + DATAOFFSET)
+
+/* field access macros (AFTER sysinfo loaded) */
+/* Examples - replace "m->prv" by "fld(m, prv)" */
+/* replace "m->sz" by "szof(m)" */
+/* where field is prvf, nxtf, prv, nxt */
+#define fld(m, field) *((void**)((char*)m + sysinfo.field))
+#define szof(m) *(ulong*)((char*)m + sysinfo.sz)
+#define freehdrs (*freehdrsp)
+
+/* 1------------------1 */
+
+/* Fouls if sysinfo has not been initialized */
+/* See main for sysinfo initialization sequence */
+void showsysquery(void)
+{
+ printf("sysinfo is: NONE = %p\n"
+ " DATAOFFSET = %d\n"
+ " gdlo offset = %d\n"
+ " sz offset = %d\n"
+ " prvf offset = %d\n"
+ " nxtf offset = %d\n"
+ " nxt offset = %d\n"
+ " prv offset = %d\n"
+ " ohead = %d\n"
+ " &freehdrs = %p\n"
+ " &anchors = %p\n"
+ " &hookset() = %p\n",
+ sysinfo.nilp, sysinfo.data, sysinfo.gdlo,
+ sysinfo.sz, sysinfo.prvf, sysinfo.nxtf,
+ sysinfo.nxt, sysinfo.prv, sysinfo.ohead,
+ freehdrs, sysinfo.anchors, sysinfo.hookset);
+
+
+} /* showsysquery */
+
+/* 1------------------1 */
+
+/* m is the allocated ptr treated by MEMBLKp */
+/* Fouls if sysinfo has not been initialized */
+/* See main for sysinfo initialization sequence */
+static void xshowblock(void *m, const char *id)
+{
+ if (m) {
+ printf(" %s %p", id, m);
+ printf(" sz=%u nxt=%p prv=%p nxtf=",
+ szof(m), fld(m, nxt), fld(m, prv));
+ if (fld(m, nxtf)) {
+ if (NONE == fld(m, nxtf))
+ printf("NONE prvf=");
+ else
+ printf("%p prvf=", fld(m, nxtf));
+ if (NONE == fld(m, prvf))
+ printf("NONE");
+ else
+ printf("%p", fld(m, prvf));
+ }
+ else printf("0");
+ }
+ else
+ printf(" %s NULL", id);
+ fflush(stdout); /* to coexist with internal debuggery */
+} /* xshowblock */
+
+/* ========== End of debuggery examples ============= */
+/* ============== Start of tests ==================== */
+
+struct blkspace {
+ unsigned long totspace;
+ unsigned long blkcount;
+};
+
+/* 1------------------1 */
+
+struct blkspace freeblocks(void)
+{
+ struct blkspace blksp;
+ int i;
+ memblockp m;
+
+ blksp.totspace = blksp.blkcount = 0;
+ for (i = 0; i < NFLISTS; i++) {
+ if ((m = freehdrs[i])) {
+ while (m && (NONE !=m )) {
+ blksp.totspace += szof(m);
+ blksp.blkcount++;
+ m = fld(m, nxtf);
+ }
+ }
+ }
+ return blksp;
+} /* freeblocks */
+
+/* 1------------------1 */
+
+void printinfo(struct mallinfo *info)
+{
+ printf(" arena = %d\n", info->arena);
+ printf(" ordblks = %d\n", info->ordblks);
+ printf(" smblks = %d\n", info->smblks);
+ printf(" hblks = %d\n", info->hblks);
+ printf(" hblkhd = %d\n", info->hblkhd);
+ printf(" usmblks = %d\n", info->usmblks);
+ printf(" fsmblks = %d\n", info->fsmblks);
+ printf("uordblks = %d\n", info->uordblks);
+ printf("fordblks = %d\n", info->fordblks); /* free space */
+ printf("keepcost = %d\n", info->keepcost);
+} /* printinfo */
+
+/* 1------------------1 */
+
+void foul2ndlast(testnode *node)
+{
+ testnode *this, *prev;
+ void *m;
+
+ this = prev = NULL;
+ while (node) {
+ prev = this; this = node; node = node->next;
+ }
+ /* Now prev=>this=>NULL */
+ m = MEMBLKp(prev);
+
+ xshowblock(m, "Fouling block: ");
+ puts("");
+
+ /* acts like a write past the previous block */
+ (*(char*)m)--;
+
+ xshowblock(m, " which became: ");
+ puts("\n");
+
+} /* foul2ndlast */
+
+/* 1------------------1 */
+
+void test01(unsigned long n)
+{
+ struct mallinfo info;
+ struct blkspace blkspace;
+ void *m;
+
+ root = buildlist(n, root);
+ m = MEMBLKp(root);
+ xshowblock(m, "\nLAST allocated:");
+ puts("");
+
+ blkspace = freeblocks();
+ info = mallinfo();
+ printinfo(&info);
+
+ printf("\nnfreeblk = %lu\n", blkspace.blkcount);
+ printf(" holding ( %lu )\n", blkspace.totspace);
+} /* test01 */
+
+/* 1------------------1 */
+
+void test02(unsigned long n)
+{
+ root = buildlist(n, root);
+ mallocmap();
+} /* test02 */
+
+/* 1------------------1 */
+
+void test03(unsigned long n)
+{
+ struct mallinfo info;
+
+ root = buildlist(n, root);
+ info = mallinfo();
+ puts("\nBefore pruning:");
+ printinfo(&info);
+ prunelist(root);
+ info = mallinfo();
+ puts("\nAfter pruning:");
+ printinfo(&info);
+ prunelist(root);
+ info = mallinfo();
+ puts("\nAfter repruning:");
+ printinfo(&info);
+ puts("\nComplete map:");
+ mallocmap();
+} /* test03 */
+
+/* 1------------------1 */
+
+void test04(unsigned long n)
+{
+ struct mallinfo info;
+ testnode *this;
+
+ info = mallinfo();
+ puts("\nAt startup:");
+ printinfo(&info);
+ root = buildlist(n, root);
+ info = mallinfo();
+ puts("\nBefore pruning:");
+ printinfo(&info);
+ prunelist(root);
+ info = mallinfo();
+ puts("\nAfter pruning:");
+ printinfo(&info);
+ prunelist(root);
+ info = mallinfo();
+ puts("\nAfter repruning:");
+ printinfo(&info);
+ free(NULL); /* to check the alert */
+ while ((this = root)) {
+ root = root->next;
+ free(this);
+ }
+ info = mallinfo();
+ puts("\nAfter freeing all:");
+ printinfo(&info);
+ puts("\nComplete map:");
+ mallocmap();
+} /* test04 */
+
+/* 1------------------1 */
+
+void test06(unsigned long n)
+{
+ root = buildlist(n, root);
+ printf("malloc_verify() returns %d\n", malloc_verify());
+ mallocmap();
+} /* test06 */
+
+/* 1------------------1 */
+
+void test07(unsigned long n)
+{
+ root = buildlist(n, root);
+ foul2ndlast(root);
+ printf("malloc_verify() returns %d\n", malloc_verify());
+ mallocmap();
+} /* test07 */
+
+/* 1------------------1 */
+
+void test08(unsigned long n)
+{
+ struct mallinfo info;
+ void *p, *p1;
+
+ info = mallinfo();
+ puts("\nAt startup:");
+ printinfo(&info);
+ root = buildlist(n, root);
+ info = mallinfo();
+ puts("\nBefore pruning:");
+ printinfo(&info);
+ prunelist(root);
+ info = mallinfo();
+ puts("\nAfter pruning:");
+ printinfo(&info);
+ prunelist(root);
+ info = mallinfo();
+ puts("\nAfter repruning:");
+ printinfo(&info);
+ puts("\nAfter attempting malloc/realloc(INT_MAX):");
+ p = malloc(INT_MAX);
+ p = malloc(2);
+ if (p && (p1 = realloc(p, INT_MAX))) {
+ p = p1; /* shouldn't happen */
+ puts("\nSomething is wrong");
+ }
+ info = mallinfo();
+ printinfo(&info);
+ puts("\nComplete map:");
+ mallocmap();
+} /* test08 */
+
+/* 1------------------1 */
+
+int main(int argc, char *argv[])
+{
+ unsigned long t = 0, n = 0, dbglvl = 0;
+
+ if (argc > 1) t = strtoul(argv[1], NULL, 10);
+ if (argc > 2) n = strtoul(argv[2], NULL, 10);
+ if (argc > 3) dbglvl = strtoul(argv[3], NULL, 10);
+
+ if (0 == n) n = 10;
+
+ printf("test%02lu-%lu (%lu)\n", t, n, dbglvl);
+
+ sysinfo = _sysmalloc();
+ freehdrsp = (void*)((byte*)(sysinfo.nilp)-sizeof(void*));
+ malloc_debug(dbglvl);
+ if (t != 5) malldbgdumpfile(stdout);
+
+ switch (t) {
+case 1: test01(n); break;
+case 2: test02(n); break;
+case 3: test03(n); break;
+case 4: test04(n); break;
+case 5: test04(n); break; /* see malldbgdumfile call above */
+case 6: test06(n); break;
+case 7: test07(n); break;
+case 8: test08(n); break;
+default:
+ printf("Usage: tmalldbg [testnumber [quantity [level]]]\n");
+ printf("CHAR_BIT * sizeof(size_t) = %lu\n",
+ (unsigned long)(CHAR_BIT * sizeof(size_t)));
+ showsysquery();
+ printf(
+ "\n"
+ "Test Purpose (usually to stdout)\n"
+ " 1 Allocate items, execute/show mallinfo\n"
+ " 2 Allocate items, execute mallocmap\n"
+ " 3 Allocate/prune items, do mallocmap & info\n"
+ " 4 As test 3, but all freed and free(NULL)\n"
+ " 5 As test 4, but dumps to stderr\n"
+ " 6 Allocate items, call malloc_verify / map\n"
+ " 7 As 6, but deliberately foul 2nd last malloc\n"
+ " 8 As 3, but attempt to malloc INT_MAX items\n"
+ );
+ break;
+ } /* switch (t) */
+ return 0;
+} /* main */
+
+/* ------- tmalldbg -------- */
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ tests/libc/compat/stdlib/makefile 2003-09-07 10:56:38.000000000 +0000
@@ -0,0 +1,5 @@
+TOP=../..
+
+SRC += t-memaln.c
+
+include $(TOP)/../makefile.inc
\ No newline at end of file
--- /dev/null 2003-09-07 11:47:01.000000000 +0000
+++ tests/libc/compat/stdlib/t-memaln.c 2003-09-07 11:00:26.000000000 +0000
@@ -0,0 +1,25 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+static const size_t MAX_TEST = 64;
+
+int
+main (void)
+{
+ char *p;
+ size_t i;
+
+ /* boundary must be a power of 2 for memalign with GNU libc 2.1.3. */
+ for (i = 2; i <= MAX_TEST; i *= 2)
+ {
+ p = memalign(i, i);
+ if (!p)
+ printf("memalign(%zd, %zd) failed\n", i, i);
+ else
+ free(p);
+ }
+
+ puts("PASS");
+ return(EXIT_SUCCESS);
+}
- Raw text -