Dan Karron@UCBVAX.BERKELEY.EDU (02/04/91)
Appended below is some code I use for validating pointers. It depends
on knowing the layout of user process memory text, heap and stack boundries.
I am including this with the hope that if you have a technique you use to
debug bad pointers you will send it to me or post it too.
If you want to use the code below in your buggy application, you need to
do two things: 1) include the .h file in your application code, and
2) link in the .o file from the .c file below.
Setting setenv DEBUG_HEAP will produce too much output, but if the
Free detects a bad pointer (which is why I did this) it will turn on
debug output for all succeeding memory allocations calls and make lots of
output.
These bugs are especially pernicious, because the structure of the heap
can be corrupted with no symptoms at all, or for many malloc calls before
you get a error. A bad pointer to free will subtly corrup the heap without
any immediate symptoms.
If you have a a favorite technique you use to track pointer bugs,
I would appreciate hearing how you do it !
Cheers!
dan.
--------------------------MemoryDeBug.h-------------------------------------
#define calloc(a,b) Calloc(a,b,__FILE__,__LINE__)
#define malloc(a) Malloc(a,__FILE__,__LINE__)
#define free(a) Free(a,__FILE__,__LINE__)
#define strdup(a) Strdup(a,__FILE__,__LINE__)
extern void *Calloc(size_t nelem, size_t elsize,char *file,int line);
extern void *Malloc(size_t elsize,char *file,int line);
void Free(void *freeme,char *file,int line);
extern char *Strdup(char *dup_me,char *file,int line);
--------------------------MemoryDeBug.c-------------------------------------
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include "setjmp.h"
#define DEBUG_ENVIRON "DEBUG_HEAP"
#define STACK_POINTER (setjmp(jumped_buffer),(void *)jumped_buffer[JB_SP] )
#define STACK_BASE (void *)0x7ffff000
void *sbrk (int incr); /* stbrk(0) returns the top of the heap */
extern _ftext; /* beginning of text segment */
extern etext; /* one after end of text segment */
extern _fdata; /* beginning of the static initalized data segment */
extern edata; /* one after end of static initalized data */
extern _fbss; /* beginning of uninitalized static data , at edata */
extern end; /* one after end of init data, and beginning of heap */
static int Error_Happened;
void *Calloc(size_t nelem, size_t elsize,char *file,int line)
{
void *ptr;
if(getenv(DEBUG_ENVIRON)||Error_Happened)
printf("Calloc(%d,%d) called at %s,%d ",nelem,elsize,file,line);
ptr=calloc(nelem,elsize);
if(!ptr)
{
fprintf(stderr,"Calloc failed, no memory being returned\n");
Error_Happened=1;
}
if(getenv(DEBUG_ENVIRON)||Error_Happened)
printf(" returning %#x to %#x\n",ptr,(long int)ptr+(nelem*elsize));
return ptr;
}
/***************************************************************************/
void *Malloc(size_t elsize,char *file,int line)
{
void *ptr;
if(getenv(DEBUG_ENVIRON)||Error_Happened)
printf("Calloc(%d) called at %s,%d ",elsize,file,line);
ptr=malloc(elsize);
if(!ptr)
{
fprintf(stderr,"Malloc failed, no memory being returned\n");
Error_Happened=1;
}
if(getenv(DEBUG_ENVIRON)||Error_Happened)
printf(" returning %#x to %#x\n",ptr,(long int)ptr+(elsize));
return ptr;
}
/***************************************************************************/
void *Free(void *ptr,char *file,int line)
{
jmp_buf jumped_buffer;
if(ptr == (void *)0)
{
fprintf(stderr,"ZERO POINTER to Free\n");
Error_Happened=1;
}
else if(ptr< &_ftext)
fprintf(stderr,"BAD POINTER to Free, below beginning of text, %#x < %#x\n",
ptr,&_ftext),Error_Happened=1;
else if(ptr >= &_ftext && ptr < &etext )
fprintf(stderr,"BAD POIINTER to Free, in program text segment, %#x >= %#x < %#x\n",
&_ftext,ptr,&etext),Error_Happened=1;
else if(ptr >= &etext && ptr < &_fdata )
fprintf(stderr,"BAD POINTER to Free, between program text and data, %#x >= %#x < %#x\n",
&etext, ptr, &_fdata),Error_Happened=1;
else if(ptr >= &_fdata && ptr < &_fbss)
fprintf(stderr,"BAD POINTER to Free, in static initalized text area, %#x >= %#x < %#x\n",
&_fdata, ptr, &_fbss),Error_Happened=1;
else if(ptr >= &_fbss && ptr < &end)
fprintf(stderr,"BAD POINTER to Free, in static uninitalized data area, %#x >= %#x < %#x\n",
&_fbss,ptr,&end),Error_Happened=1;
else if( ptr >= &end && ptr < sbrk(0) )
{
if(getenv(DEBUG_ENVIRON)||Error_Happened)
printf("Free(%#x) at %s,%d\n",ptr,file,line);
free(ptr);
}
else if(ptr >= sbrk(0) && ptr < STACK_POINTER )
fprintf(stderr,"BAD POINTER to Free, beyond top of heap, %#x >= %#x\n",
sbrk(0),ptr,STACK_POINTER),Error_Happened=1;
else if(ptr >= STACK_POINTER && ptr < STACK_BASE )
fprintf(stderr,"BAD POINTER to Free, in stack, %#x >= %#x < %#x\n",
STACK_POINTER,ptr,STACK_BASE),Error_Happened=1;
else if(ptr >= STACK_BASE)
fprintf(stderr,"BAD POINTER to Free, beyond top of stack base, %#x >= %#x\n",
ptr, STACK_BASE),Error_Happened=1;
else ;
}
/**************************************************************************/
char *Strdup(char *dup_me,char *file,int line)
{
char *string;
int string_length;
int i;
if(getenv(DEBUG_ENVIRON)||Error_Happened)
printf("Strdup(%s,%d) at %s,%d",dup_me,strlen(dup_me),file,line);
for(i=0;dup_me[i]!=NULL;i++);
string_length = i+1;
string=calloc(string_length,sizeof(char));
for(i=0;i<string_length;i++)
string[i]=dup_me[i];
if(getenv(DEBUG_ENVIRON)||Error_Happened)
printf(" with %#x\n",string);
return string;
}
+-----------------------------------------------------------------------------+
| karron@nyu.edu (E-mail alias that will always find me) |
| Fax: 212 263 7190 * Dan Karron, Research Associate |
| . . . . . . . . . . . . . . * New York University Medical Center |
| 560 First Avenue \*\ Pager <1> (212) 397 9330 |
| New York, New York 10016 \**\ <2> 10896 <3> <your-number-here> |
| (212) 263 5210 \***\_________________________________________ |
| Main machine: karron.med.nyu.edu (128.122.135.3) IRIS 85GT |
+-----------------------------------------------------------------------------+
NOTE PHONE NUMBER CHANGE: The Med Ctr has changed from 340 to 263 exchange.mike@BRL.MIL (Mike Muuss) (02/05/91)
I handle memory corruption and pointer mis-handling in a rather
different manner. I have "wrapper" subroutines called
rt_malloc(), rt_free(), rt_calloc() that take an extra string
argument which indicates the "purpose" of this allocation/free.
Depending on the setting of some global variables, you can
independently enable memory activity logging, and memory
checking. The checking includes adding a "barrier" word at the
end of the allocation, to ensure that the application is not
running off the end. It also maintains a full table of what memory
is being used. This table can be printed at any time, by calling
a subroutine (either from the application, or via a "dbx -P").
One final note is that most of our application's data structures have
been designed with "magic numbers" as their first word, so that
subroutines can validate that they have been given pointers to the
correct kind of object.
These two techniques have been very powerful, and have virtually eliminated
the programming difficulties associated with using very complex
dynamic memory allocation in C.
Best,
-Mike
------
/*
* S T O R A G E . C
*
* Ray Tracing program, storage manager.
*
* Functions -
* rt_malloc Allocate storage, with visibility & checking
* rt_free Similarly, free storage
* rt_realloc Reallocate storage, with visibility & checking
* rt_calloc Allocate zero'ed storage
* rt_prmem When debugging, print memory map
* rt_strdup Duplicate a string in dynamic memory
*
* Author -
* Michael John Muuss
*
* Source -
* SECAD/VLD Computing Consortium, Bldg 394
* The U. S. Army Ballistic Research Laboratory
* Aberdeen Proving Ground, Maryland 21005-5066
*
*/
#ifndef lint
static char RCSstorage[] = "@(#)$Header: /m/cad/librt/RCS/storage.c,v 9.14 91/01/29 10:40:24 cjohnson Exp $";
#endif
#include <stdio.h>
#include "machine.h"
#include "vmath.h"
#include "raytrace.h"
#include "./debug.h"
#ifdef BSD
# include <strings.h>
#else
# include <string.h>
#endif
#define MDB_MAGIC 0x12348969
struct memdebug {
char *mdb_addr;
char *mdb_str;
int mdb_len;
};
static struct memdebug *rt_memdebug;
static int rt_memdebug_len = 0;
#define MEMDEBUG_NULL ((struct memdebug *)0)
/*
* R T _ M E M D E B U G _ A D D
*
* Add another entry to the memory debug table
*/
HIDDEN void
rt_memdebug_add( ptr, cnt, str )
char *ptr;
unsigned int cnt;
char *str;
{
register struct memdebug *mp;
top:
if( rt_g.rtg_parallel ) {
RES_ACQUIRE( &rt_g.res_syscall ); /* lock */
}
if( rt_memdebug ) {
mp = &rt_memdebug[rt_memdebug_len-1];
for( ; mp >= rt_memdebug; mp-- ) {
/* Search for an empty slot */
if( mp->mdb_len > 0 ) continue;
mp->mdb_addr = ptr;
mp->mdb_len = cnt;
mp->mdb_str = str;
if( rt_g.rtg_parallel ) {
RES_RELEASE( &rt_g.res_syscall ); /* unlock */
}
return;
}
}
/* Need to make more slots */
if( rt_memdebug_len <= 0 ) {
rt_memdebug_len = 510;
rt_memdebug = (struct memdebug *)calloc(
rt_memdebug_len, sizeof(struct memdebug) );
} else {
int old_len = rt_memdebug_len;
rt_memdebug_len *= 4;
rt_memdebug = (struct memdebug *)realloc(
(char *)rt_memdebug,
sizeof(struct memdebug) * rt_memdebug_len );
bzero( (char *)&rt_memdebug[old_len],
(rt_memdebug_len-old_len) * sizeof(struct memdebug) );
}
if( rt_g.rtg_parallel ) {
RES_RELEASE( &rt_g.res_syscall ); /* unlock */
}
if( rt_memdebug == (struct memdebug *)0 )
rt_bomb("rt_memdebug_add() malloc failure\n");
goto top;
}
/*
* R T _ M E M D E B U G _ C H E C K
*
* Check an entry against the memory debug table, based upon it's address.
*/
HIDDEN struct memdebug *
rt_memdebug_check( ptr, str )
register char *ptr;
char *str;
{
register struct memdebug *mp = &rt_memdebug[rt_memdebug_len-1];
register long *ip;
if( rt_memdebug == (struct memdebug *)0 ) {
rt_log("rt_memdebug_check(x%x, %s) no memdebug table yet\n",
ptr, str);
return MEMDEBUG_NULL;
}
for( ; mp >= rt_memdebug; mp-- ) {
if( mp->mdb_len <= 0 ) continue;
if( mp->mdb_addr != ptr ) continue;
ip = (long *)(ptr+mp->mdb_len-sizeof(long));
if( *ip != MDB_MAGIC ) {
rt_log("ERROR rt_memdebug_check(x%x, %s) barrier word corrupted!\nbarrier at x%x was=x%x s/b=x%x, len=%d\n",
ptr, str, ip, *ip, MDB_MAGIC, mp->mdb_len);
}
return(mp); /* OK */
}
return MEMDEBUG_NULL;
}
/*
* R T _ M E M D E B U G _ M O V E
*
* realloc() has moved to a new memory block.
* Update our notion as well.
*/
HIDDEN void
rt_memdebug_move( old_ptr, new_ptr, new_cnt, new_str )
char *old_ptr;
char *new_ptr;
int new_cnt;
char *new_str;
{
register struct memdebug *mp = &rt_memdebug[rt_memdebug_len-1];
if( rt_memdebug == (struct memdebug *)0 ) {
rt_log("rt_memdebug_move(x%x, x%x, %d., %s) no memdebug table yet\n",
old_ptr, new_ptr, new_cnt, new_str);
return;
}
for( ; mp >= rt_memdebug; mp-- ) {
if( mp->mdb_len > 0 && (mp->mdb_addr == old_ptr) ) {
mp->mdb_addr = new_ptr;
mp->mdb_len = new_cnt;
mp->mdb_str = new_str;
return;
}
}
rt_log("rt_memdebug_move(): old memdebug entry not found!\n");
rt_log(" old_ptr=x%x, new_ptr=x%x, new_cnt=%d., new_str=%s\n",
old_ptr, new_ptr, new_cnt, new_str );
}
/*
* R T _ M A L L O C
*
* This routine only returns on successful allocation.
* Failure results in rt_bomb() being called.
*/
char *
rt_malloc(cnt, str)
unsigned int cnt;
char *str;
{
register char *ptr;
if( cnt == 0 ) {
rt_log("ERROR: rt_malloc count=0 %s\n", str );
rt_bomb("ERROR: rt_malloc(0)\n");
}
if( rt_g.debug&DEBUG_MEM_FULL ) {
/* Pad, plus full int for magic number */
cnt = (cnt+2*sizeof(long)-1)&(~(sizeof(long)-1));
}
if( rt_g.rtg_parallel ) {
RES_ACQUIRE( &rt_g.res_syscall ); /* lock */
}
ptr = malloc(cnt);
if( rt_g.rtg_parallel ) {
RES_RELEASE( &rt_g.res_syscall ); /* unlock */
}
if( ptr==(char *)0 || rt_g.debug&DEBUG_MEM )
rt_log("%7x malloc%6d %s\n", ptr, cnt, str);
if( ptr==(char *)0 ) {
rt_log("rt_malloc: Insufficient memory available, sbrk(0)=x%x\n", sbrk(0));
rt_bomb("rt_malloc: malloc failure");
}
if( rt_g.debug&DEBUG_MEM_FULL ) {
rt_memdebug_add( ptr, cnt, str );
/* Install a barrier word at the end of the dynamic arena */
/* Correct location depends on 'cnt' being rounded up, above */
*((long *)(ptr+cnt-sizeof(long))) = MDB_MAGIC;
}
return(ptr);
}
/*
* R T _ F R E E
*/
void
rt_free(ptr,str)
char *ptr;
char *str;
{
if(rt_g.debug&DEBUG_MEM) rt_log("%7x free %s\n", ptr, str);
if(ptr == (char *)0) {
rt_log("%7x free ERROR %s\n", ptr, str);
return;
}
if( rt_g.debug&DEBUG_MEM_FULL ) {
struct memdebug *mp;
if( (mp = rt_memdebug_check( ptr, str )) == MEMDEBUG_NULL ) {
rt_log("ERROR rt_free(x%x, %s) pointer bad, or not allocated with rt_malloc!\n",
ptr, str);
} else {
mp->mdb_len = 0; /* successful delete */
}
}
if( rt_g.rtg_parallel ) {
RES_ACQUIRE( &rt_g.res_syscall ); /* lock */
}
*((int *)ptr) = -1; /* zappo! */
free(ptr);
if( rt_g.rtg_parallel ) {
RES_RELEASE( &rt_g.res_syscall ); /* unlock */
}
}
/*
* R T _ R E A L L O C
*/
char *
rt_realloc(ptr, cnt, str)
register char *ptr;
unsigned int cnt;
char *str;
{
char *original_ptr = ptr;
if( rt_g.debug&DEBUG_MEM_FULL ) {
if( rt_memdebug_check( ptr, str ) == MEMDEBUG_NULL ) {
rt_log("%7x realloc%6d %s ** barrier check failure\n",
ptr, cnt, str );
}
/* Pad, plus full int for magic number */
cnt = (cnt+2*sizeof(long)-1)&(~(sizeof(long)-1));
}
if( rt_g.rtg_parallel ) {
RES_ACQUIRE( &rt_g.res_syscall ); /* lock */
}
ptr = realloc(ptr,cnt);
if( rt_g.rtg_parallel ) {
RES_RELEASE( &rt_g.res_syscall ); /* unlock */
}
if( ptr==(char *)0 || rt_g.debug&DEBUG_MEM ) {
rt_log("%7x realloc%6d %s %s\n", ptr, cnt, str,
ptr == original_ptr ? "[grew in place]" : "[moved]" );
}
if( ptr==(char *)0 ) {
rt_log("rt_realloc: Insufficient memory available, sbrk(0)=x%x\n", sbrk(0));
rt_bomb("rt_realloc: malloc failure");
}
if( rt_g.debug&DEBUG_MEM_FULL ) {
/* Even if ptr didn't change, need to update cnt & barrier */
rt_memdebug_move( original_ptr, ptr, cnt, str );
/* Install a barrier word at the end of the dynamic arena */
/* Correct location depends on 'cnt' being rounded up, above */
*((long *)(ptr+cnt-sizeof(long))) = MDB_MAGIC;
}
return(ptr);
}
/*
* R T _ C A L L O C
*/
char *
rt_calloc( nelem, elsize, str )
unsigned int nelem;
unsigned int elsize;
char *str;
{
unsigned len;
char *ret;
ret = rt_malloc( (len = nelem*elsize), str );
#ifdef SYSV
(void)memset( ret, '\0', len );
#else
bzero( ret, len );
#endif
return(ret);
}
/*
* R T _ P R M E M
*
* Print map of memory currently in use.
*/
void
rt_prmem(str)
char *str;
{
register struct memdebug *mp;
register int *ip;
rt_log("\nrt_prmem(): LIBRT memory use (%s)\n", str);
if( (rt_g.debug&DEBUG_MEM_FULL) == 0 ) {
rt_log("\tMemory debugging is now OFF\n");
}
rt_log("\t%d elements in memdebug table\n", rt_memdebug_len);
if( rt_memdebug_len <= 0 ) return;
mp = &rt_memdebug[rt_memdebug_len-1];
for( ; mp >= rt_memdebug; mp-- ) {
if( mp->mdb_len <= 0 ) continue;
ip = (int *)(mp->mdb_addr+mp->mdb_len-sizeof(int));
rt_log("%7x %5x %s %s\n",
mp->mdb_addr, mp->mdb_len, mp->mdb_str,
*ip!=MDB_MAGIC ? "-BAD-" : "" );
if( *ip != MDB_MAGIC )
rt_log("\t%x\t%x\n", *ip, MDB_MAGIC);
}
}
/*
* R T _ S T R D U P
*
* Given a string, allocate enough memory to hold it using rt_malloc(),
* duplicate the strings, returns a pointer to the new string.
*/
char *
rt_strdup( cp )
register char *cp;
{
register char *base;
register int len;
if(rt_g.debug&DEBUG_MEM) rt_log("rt_strdup(%s) x%x\n", cp, cp);
len = strlen( cp )+2;
if( (base = rt_malloc( len, "rt_strdup" )) == (char *)0 )
rt_bomb("rt_strdup: unable to allocate memory");
#ifdef BSD
bcopy( cp, base, len );
#else
memcpy( base, cp, len );
#endif
return(base);
}
/* R T _ C K _ M A L L O C _ P T R
*
* Check the magic number stored with memory allocated with rt_malloc
* when DEBUG_MEM_FULL is set.
*
* return:
* 0 pointer good or DEBUG_MEM_FULL not set
* other memory corrupted.
*/
void
rt_ck_malloc_ptr( ptr, str )
char *ptr;
char *str;
{
register struct memdebug *mp = &rt_memdebug[rt_memdebug_len-1];
register long *ip;
/* if memory debugging isn't turned on, we have no way
* of knowing if the pointer is good or not
*/
if ((rt_g.debug&DEBUG_MEM_FULL) == 0) return;
if (ptr == (char *)NULL) {
rt_log("rt_ck_malloc_ptr(x%x, %s) null pointer\n\n", ptr, str);
rt_bomb("Goodbye");
}
if( rt_memdebug == (struct memdebug *)0 ) {
rt_log("rt_ck_malloc_ptr(x%x, %s) no memdebug table yet\n",
ptr, str);
rt_bomb("Goodbye");
}
for( ; mp >= rt_memdebug; mp-- ) {
if( mp->mdb_len <= 0 || mp->mdb_addr != ptr ) continue;
ip = (long *)(ptr+mp->mdb_len-sizeof(long));
if( *ip != MDB_MAGIC ) {
rt_log("ERROR rt_ck_malloc_ptr(x%x, %s) barrier word corrupted! was=x%x s/b=x%x\n",
ptr, str, *ip, MDB_MAGIC);
rt_bomb("Goodbye");
}
return; /* OK */
}
rt_log("ERROR rt_ck_malloc_ptr(x%x, %s)\n\
pointer not in table of allocated memory.\n", ptr, str);
rt_bomb("Goodbye");
}mike@BRL.MIL (Mike Muuss) (02/05/91)
Dan -
Glad you found the rt_malloc() code interesting.
Let me also share some of the "magic number checking" stuff, as well.
Best,
-Mike
-------
/*
* Macros to check and validate a structure pointer, given that
* the first entry in the structure is a magic number.
*/
#define RT_CKMAG(_ptr, _magic, _str) \
if( !(_ptr) ) { \
rt_log("ERROR: null %s ptr, file %s, line %d\n", \
_str, __FILE__, __LINE__ ); \
rt_bomb("NULL pointer"); \
} else if( *((long *)(_ptr)) != (_magic) ) { \
rt_log("ERROR: bad %s ptr x%x, s/b x%x, was %s(x%x), file %s, line %d\n", \
_str, _ptr, _magic, \
rt_identify_magic( *((long *)(_ptr)) ), \
*((long *)(_ptr)), __FILE__, __LINE__ ); \
rt_bomb("Bad pointer"); \
}
Here is an example use of this:
/*
* R T _ E X T E R N A L
*
* An "opaque" handle for holding onto objects,
* typically in some kind of external form that is not directly
* usable without passing through an "importation" function.
*/
struct rt_external {
long ext_magic;
int ext_nbytes;
genptr_t ext_buf;
};
#define RT_EXTERNAL_MAGIC 0x768dbbd0
#define RT_INIT_EXTERNAL(_p) {(_p)->ext_magic = RT_EXTERNAL_MAGIC; \
(_p)->ext_buf = GENPTR_NULL; (_p)->ext_nbytes = 0;}
#define RT_CK_EXTERNAL(_p) RT_CKMAG(_p, RT_EXTERNAL_MAGIC, "rt_external")
/*
*
* D B _ P U T _ E X T E R N A L
*
* Caller is responsible for freeing memory, using db_free_external().
*/
int
db_put_external( ep, dp, dbip )
struct rt_external *ep;
struct directory *dp;
struct db_i *dbip;
{
if(rt_g.debug&DEBUG_DB) rt_log("db_put_external(%s) ep=x%x, dbip=x%x, dp=x%x\n",
dp->d_namep, ep, dbip, dp );
RT_CK_DBI(dbip);
RT_CK_EXTERNAL(ep);
if( db_put( dbip, dp, (union record *)(ep->ext_buf), 0,
(ep->ext_nbytes+sizeof(union record)-1)/sizeof(union record)
) < 0 )
return(-1);
return(0);
}donl@glass.esd.sgi.com (donl mathis) (02/06/91)
In article <9102041731.aa11984@WOLF.BRL.MIL>, mike@BRL.MIL (Mike Muuss) writes: > I handle memory corruption and pointer mis-handling in a rather > different manner. I have "wrapper" subroutines called > rt_malloc(), rt_free(), rt_calloc() that take an extra string > argument which indicates the "purpose" of this allocation/free. > > Depending on the setting of some global variables, you can > independently enable memory activity logging, and memory > checking. The checking includes adding a "barrier" word at the > end of the allocation, to ensure that the application is not > running off the end. It also maintains a full table of what memory > is being used. This table can be printed at any time, by calling > a subroutine (either from the application, or via a "dbx -P"). > > One final note is that most of our application's data structures have > been designed with "magic numbers" as their first word, so that > subroutines can validate that they have been given pointers to the > correct kind of object. > > These two techniques have been very powerful, and have virtually eliminated > the programming difficulties associated with using very complex > dynamic memory allocation in C. I have a similar package that accomplish much the same thing, but in a somewhat more formal environment. My model for memory use was that a program will enter a logical scope where it will be building a new structure of some kind, allocate many bits and pieces within the structure, and then throw the whole thing away at once. Any number of such scopes may coexist. I abandoned the notion of explicitly freeing individual values, and at least in my applications, have not missed it. A scope is created by opening a "memory group", which has a name and perhaps some tuning parameters. A pointer to struct is returned to the caller, and all allocation requests are made against that handled. Relatively large blocks of memory are added to the group as necessary. Each block has a header that contains a pointer to the current free space within the block. Individual allocation requests are generally satisfied by simply keeping an eye on the free count, and bumping the pointer into the block. "Freeing" the group consists of resetting the block pointers, also quite fast. A group can be destroyed and its blocks returned to the pool. Verification gets easier once you have a structure describing the list of blocks, and block headers that describe the memory that is part of the group. It is a simple matter to verify that a pointer to an object of a known size is completely within a block in the group, and that a group appears to be self-consistent. (One of the routines in my test suite repeatedly fires random bytes into memory and calls the verification routines; it usually, though not always, notices a problem before the program dumps core.) On top of these basic mechanisms, there is a user interface layer designed to make memory easy to get and use. Macros provided typed allocation of the appropriate size, and there is an extension to the basic mechanism for variable-sized arrays that grow as necessary when a reference goes out of the current bounds. Macros also providing scaling by N to allocate arrays without a fuss. I do not know how well this mechanism would fit into C++, nor do i know how much of a pain it would be to adapt it to multiprocessing. The package as it sits is about 1300 lines of C. My last tests indicated a significant performance increase over malloc/free, although they were done some time ago, and i don't know what changes have occured since then. -- - donl mathis at Silicon Graphics Computer Systems, Mountain View, CA donl@sgi.com There is One.
srp@babar.mmwb.ucsf.edu (Scott R. Presnell) (02/06/91)
donl@glass.esd.sgi.com (donl mathis) writes: >In article <9102041731.aa11984@WOLF.BRL.MIL>, mike@BRL.MIL (Mike Muuss) writes: >> I handle memory corruption and pointer mis-handling in a rather >> different manner. I have "wrapper" subroutines called >I have a similar package that accomplish much the same thing, but in a >somewhat more formal environment. My model for memory use was that a [...] With all this talk of pointer validation, wrappers for alloc etc. I thought I'd ask if anyone had been using the C garbage collection scheme posted to comp.sources.unix about a year and a half ago? Having learned Lisp before C I thought garbage collection was a pretty cool idea... I ran the test and tried it out a couple of times on my own small programs without any problems, but I haven't used it in a "production" tool yet. Anyone using it out there? This is the header to the post: = =This is intended to be a general purpose, garbage collecting storage =allocator. The algorithms used are described in: =Boehm, H., and M. Weiser, ="Garbage Collection in an Uncooperative Environment", =Software Practice & Experience, September 1988, pp. 807-820. = =Many of the ideas underlying the collector have previously been explored =by others. (We discovered recently that Doug McIlroy wrote a more or less =similar collector that is part of version 8 UNIX (tm).) However none of =this work appears to have been widely disseminated. = =The tools for detecting storage leaks described in the above paper are not =included here. There is some hope that they might be released by Xerox in =the future. = =Since the collector does not require pointers to be tagged, it does not =attempt to insure that all inaccessible storage is reclaimed. However, =in our experience, it is typically more successful at reclaiming unused =memory than most C programs using explicit deallocation. = Just curious - Scott Presnell (srp@cgl.ucsf.edu) -- Scott Presnell +1 (415) 476-9890 Pharm. Chem., S-926 Internet: srp@cgl.ucsf.edu University of California UUCP: ...ucbvax!ucsfcgl!srp San Francisco, CA. 94143-0446 Bitnet: srp@ucsfcgl.bitnet