allbery@ncoast.UUCP (06/16/87)
Here is a replacement for the standard malloc, realloc, calloc, free,
sbrk, and brk for Microsoft C 4.0.
It was written to satisfy the need for a 'debugging malloc' in the MSC4.0
environment on the PC.
It can be used in production code with impunity, though it isn't as
efficient space-wise as the standard set of routines.
The core routines have been tested in all memory models - but as noted,
there will need to be some work on the debug code to make it function
properly in other than small code, small data.
-----------------------------CUT HERE----------------------------------------
/*
** Alloc.c - replacement memory allocator for Microsoft C 4.0
**
** malloc, free, calloc, realloc
** Implemented in a totally paranoid fashion - if anyone walks on the
** heap, you know about it immediately.
** If you define TEST, you get some debug code compiled in.
** If you define MALLOCTEST, you get a little malloc debugger.
** If you undefine NOSTDIO, you get standard I/O rather than my oddball
** stuff for i/o.
**
** Alas, the debugging code here assumes small code, small data - though
** the malloc'er itself works fine in larger models. The things that
** would have to change is 1) some of the code in the memtest routine.
** 2) the code for returnaddress. 3) The calls to brkctl.
**
** This is provided with no warranty at all by:
** Kent Williams
** 722 Rundell
** Iowa City, IA 52240
** {...cwruecmp}!ncoast!kent
**
*/
#define NOSTDIO
#define NULL 0
/*
** low level breaker.
** It is documented in Xenix documentation as
** char far *brkctl(command,increment,ptr)
** int command; long increment; char far *ptr;
**
** where command is one of:
** #define BR_ARGSEG 0001 specified segment
** #define BR_NEWSEG 0002 new segment
** #define BR_IMPSEG 0003 implied segment - last data segment
** #define BR_FREESEG 0004 free the specified segment
** #define BR_HUGE 0100 do the specified command in the huge context.
**
** In small model, command should always be BR_ARGSEG, and
** ptr should be the address of something in the data segment.
** In large model, you're on your own, though I think you could probably
** call with BR_ARGSEG and the default data segment the first time, and
** BR_IMPSEG on all subsequent calls.
**
** Returns either a far ptr to allocated memory, or -1 if there's an error.
*/
extern char far *brkctl(int,long,char far *);
/*
** Mystery variable that keeps the library malloc from getting pulled in.
** It SEEMS to be just the offset of the start of the heap ... so that's
** what I set it up to. NOTE : I figured this all out by disassembling the
** dynamic memory allocation routines - If they change the library, all
** bets are off.
*/
char *_asegds = NULL;
/*
** I don't use stdio. If you do, you should undefine NOSTDIO
*/
#ifdef NOSTDIO
extern char *getline(char *);
# define stdin 0
# define stdout 1
# define stderr 2
#else
# include <stdio.h>
# define getline(x) gets(x)
#endif
/* constants */
#define MAGIC_BUSY 0x1234
#define MAGIC_FREE 0x8765
#ifdef TEST
/*
** types used for 'return-stamping' memory allocation blocks.
*/
typedef void (*funcptr)(void);
extern funcptr returnaddress(void);
#endif
/* structures */
typedef struct _qqq
{
struct _qqq *next,*last;
unsigned size;
unsigned magic;
#ifdef TEST
/*
** stamp memory blocks with the address of who created/destroyed them.
*/
funcptr returnadd;
#endif /* TEST */
} mblock;
#ifdef TEST
/*
** If you undef NOSTDIO above, then we assume you're not running in
** my environment, and need the following routine.
*/
#ifdef NOSTDIO
/*
** funky subtrefuge to pick up the return address
** essentialy a replacement for:
public _returnaddress
_returnaddress proc near
mov ax,2[bp]
sub ax,3
ret
_returnaddress endp
**
*/
funcptr returnaddress(x)
unsigned x;
{
register unsigned *xp;
union { unsigned up; funcptr fp; } rval;
/*
** pick up previous frame pointer.
** This only works for small code, small data, though
** it shouldn't be too hard to figure out other models.
*/
xp = &x; /* x is at 4[bp] */
xp -= 2; /* old frame pointer is at 0[bp] */
xp = (unsigned *)(*xp);
xp += 1; /* return address is at 2[oldbp] */
rval.up = *xp - 3;
return rval.fp;
}
#endif /* NOSTDIO */
/*
** mark a block with a return address. Useful when 'envelope'
** functions are used to call the actual allocation routines.
*/
void mark_block(ptr,address)
register mblock *ptr;
funcptr address;
{
(--ptr)->returnadd = address;
}
#endif /* TEST */
/*
** QUANTUM is the minimum size blob requested from brkctl.
*/
#define QUANTUM ((long)((4096+sizeof(mblock)-1)/sizeof(mblock)))
/*
** queueing macros
*/
#define enqueue(q,i) q_insert((q)->last,i)
#define dequeue(q) (q_remove( (q) ->next))
#define q_empty(q) ((q)->next==(q)&&(q)->last==(q))
/*
** externals
*/
#include <ctype.h>
#include <string.h>
/*
** q_insert - insert item in the queue designated by head
** returns : Nothing
*/
static void q_insert(head,item)
register mblock *head,*item;
{
item->last = head;
item->next = head->next;
head->next->last = item;
head->next = item;
}
/*
** q_remove - remove an item from a queue.
** returns NULL if queue is empty
*/
static mblock *q_remove(item)
register mblock *item;
{
if(item->next == item && item->last == item)
return (mblock *)NULL;
item->next->last = item->last;
item->last->next = item->next;
return item;
}
mblock arena = { NULL,NULL,0,0 };
/*
** check_malloc - make sure everything is kosher with a particular
** memory block
*/
int check_malloc(item)
register mblock *item;
{
if(item->next->last != item)
return -1;
if(item->last->next != item)
return -1;
if(item->magic != MAGIC_BUSY && item->magic != MAGIC_FREE)
return -1;
return 0;
}
/*
** free an allocated memory block
*/
int free(item)
register mblock *item;
{
#ifdef TEST
int reason;
static char *reasons[] = {
"Not initialized",
"Bad pointer or chain corrupted",
"Already freed",
};
#endif
/* check for initialization */
if(arena.next == NULL) {
arena.next = arena.last = &arena;
arena.magic = MAGIC_BUSY;
arena.size = 0;
/*
** if there isn't anything allocated, freeing anything is an error.
*/
#ifdef TEST
{
reason = 0;
goto bad_free;
}
#else
return -1;
#endif
}
/* cheat by decrementing the pointer to access the magic block */
--item;
/* if this is a gypsy block, return error */
if(check_malloc(item))
#ifdef TEST
{
reason = 1;
goto bad_free;
}
#else
return -1;
#endif
if(item->magic != MAGIC_BUSY)
#ifdef TEST
{
reason = 2;
bad_free:
fprintf(stderr,"Bad call to free from %04x, reason = %s\n",
returnaddress(),reasons[reason]);
myexit(1);
}
#else
return -1;
#endif
/* if the item being freed isn't an empty list (i.e. not
** linked into the allocation list), then try and merge it
** with contiguous blocks
*/
if(item->next != item) {
/* mark block as free (invariant) */
item->magic = MAGIC_FREE;
/* check to see if next block is free, and contiguous with the
** current block
*/
if((item->next->magic == MAGIC_FREE) &&
(item->next == (item + item->size))) {
/* add in size of next block */
item->size += item->next->size;
/* remove the next block from the queue */
(void)q_remove(item->next);
}
/* check to see if last block is free and contiguous with the current
** block
*/
if((item->last->magic == MAGIC_FREE) &&
(item == (item->last + item->last->size))) {
item->last->size += item->size;
(void)q_remove(item);
}
#ifdef TEST
item->returnadd = returnaddress();
#endif
return 0;
}
/* we are freeing something that's never been allocated */
item->magic = MAGIC_FREE;
enqueue(&arena,item); /* just enqueue the block */
return 0;
}
void *malloc(size)
unsigned size;
{
register mblock *current;
long lmsize;
/* check for initialization */
if(arena.next == NULL) {
arena.next = arena.last = &arena;
arena.magic = MAGIC_BUSY;
arena.size = 0;
}
/* adjust size to be an even number of mblocks
bump to next even mblock round add one */
size = ( (size + (sizeof(mblock) - 1) ) / sizeof(mblock) ) + 1;
/* search down free list to find a block */
for (current = arena.next; current != &arena; current = current->next)
if(current->magic == MAGIC_FREE) {
if(current->size < size)
continue;
malloc_again:
if(current->size == size || current->size == size + 1) {
current->magic = MAGIC_BUSY;
#ifdef TEST
current->returnadd = returnaddress();
#endif
return (void *)(current+1);
}
/* current->size must be > size, split block */
else {
register mblock *new_guy;
/* compute new fragment's address */
new_guy = current + size;
/* compute his size */
new_guy->size = current->size - size;
/* make him free */
new_guy->magic = MAGIC_FREE;
/* insert him in the arena just after current */
q_insert(current,new_guy);
current->magic = MAGIC_BUSY;
current->size = size;
#ifdef TEST
current->returnadd = returnaddress();
#endif
return (void *)(current+1);
}
}
/* we have to malloc up a blob */
if(size+1 < QUANTUM)
lmsize = (long)QUANTUM * (long)sizeof(mblock);
else
lmsize = (long)size * (long)sizeof(mblock);
/*
** call brkctl to get memory.
*/
if((mblock *)-1 ==
(current = (mblock *)brkctl(1,lmsize,((char far *)&arena)))) {
return NULL;
}
/*
** _asegds seems to be a pointer to the first block allocated in
** the heap.
*/
if(_asegds == NULL)
_asegds = (char *)current;
/* make the new block an empty list */
current->next = current->last = current;
current->size = (unsigned)(lmsize/sizeof(mblock));
current->magic = MAGIC_BUSY;
(void)free(current + 1);
goto malloc_again;
/*lint -unreachable */
}
void *calloc(size,num)
unsigned size,num;
{
register char *rval;
long msize = size *num;
if(msize >= 65536L)
return NULL;
if(NULL != (rval = malloc((unsigned)msize)))
memset(rval,0,msize);
return rval;
}
void *realloc(ptr,size)
mblock *ptr; unsigned size;
{
/* save the 'real' size for later */
unsigned bytesize = size;
unsigned freespace; /* size of the new block */
mblock *new_guy; /* pointer to following fragment */
/* check for initialization */
if(arena.next == NULL) {
arena.next = arena.last = &arena;
arena.magic = MAGIC_BUSY;
arena.size = 0;
/*
** if there isn't anything allocated, freeing anything is an error.
*/
return NULL;
}
/* look at the memory block */
--ptr;
/* adjust size to be an even number of mblocks
bump to next even mblock round add one */
size = ( (size + (sizeof(mblock) - 1) ) / sizeof(mblock) ) + 1;
if(check_malloc(ptr)) {
#ifdef TEST
fprintf(stderr,"realloc : bogus pointer %x from %x\n",ptr+1,
returnaddress());
#endif
return NULL;
}
/* none of this reallocing free blocks bullshit. It might work, but
** why encourage people in that kind of behavior?
*/
if(ptr->magic != MAGIC_BUSY)
return NULL;
/* pathological case - realloc of same size */
if(size == ptr->size) {
#ifdef TEST
ptr->returnadd = returnaddress();
#endif
return (void *)(ptr+1);
}
/* are we shrinking ? */
if(ptr->size > size)
goto split_block; /* split the current block into two chunks */
/* try and grow it in place */
if((ptr->next->magic == MAGIC_FREE) && /* is it free ? */
(ptr->next == (ptr + ptr->size)) && /* is it contiguous ? */
((ptr->size + ptr->next->size) >= size)) /* is it big enough ? */ {
/* join with the next block */
freespace = ptr->size + ptr->next->size;
/* get rid of the next block */
(void)q_remove(ptr->next);
ptr->size = freespace; /* put in the new size */
/* if there isn't enough room for a fragment, don't break the chunk */
if(freespace == size || freespace == size+1) {
#ifdef TEST
ptr->returnadd = returnaddress();
#endif
return (void *)(ptr+1);
}
split_block:
/* otherwise, split the block, a la malloc */
new_guy = ptr + size;/* compute new fragment's address */
/* compute his size */
new_guy->size = ptr->size - size;
/* make him free */
new_guy->magic = MAGIC_FREE;
/* insert him in the arena just after ptr */
q_insert(ptr,new_guy);
ptr->size = size;
#ifdef TEST
ptr->returnadd = returnaddress();
#endif
return (void *)(ptr+1);
} else
/* easiest case to implement - malloc new block, copy then free
** the old block
*/ {
++ptr; /* undo the decrement to look at memory block stuff */
if(NULL == (new_guy = (mblock *)malloc(bytesize))) {
#ifdef TEST
fprintf(stderr,"realloc: out of memory\n");
#endif
return NULL;
}
memcpy((char *)new_guy,(char *)ptr,bytesize);
(void)free(ptr);
#ifdef TEST
new_guy[-1].returnadd = returnaddress();
#endif
return (void *)new_guy;
}
}
#ifdef TEST
void free_all()
{
mblock *current;
restart:
for (current = arena.next; current != &arena; current = current->next)
if(current->magic == MAGIC_BUSY) {
if(0 != free(current+1)) {
printf("error freeing %p\n",(char far *)current);
return;
}
goto restart;
}
while (NULL != (current = dequeue(&arena)))
free((char *)current);
}
#endif
/*
** implement a near sbrk on top of brkctl.
*/
char *sbrk(x)
int x;
{
return (char *)brkctl(1,(long)x,((char far *)&arena));
}
/*
** implement a brk on top of brkctl.
*/
int brk(p)
char *p;
{
char *current = sbrk(0);
return (int)brkctl(1,(long)(p-current),((char far *)&arena));
}
#ifdef MALLOCTEST
void print_chain()
{
mblock *current;
for (current = arena.next; current != &arena; current = current->next) {
printf("[%04x] %04x (%04x) : next = %04x last = %04x size = %u %s\n",
current->returnadd,
current,
(¤t[1]),current->next,
current->last,
current->size * sizeof(mblock),
current->magic == MAGIC_FREE ? "FREE" : "BUSY");
}
}
#include <signal.h>
#include <setjmp.h>
static jmp_buf flubber;
static int sig_catcher()
{
signal(SIGINT,sig_catcher);
longjmp(flubber,-1);
}
void memtest()
{
static char buf[256];
unsigned siz;
char *ptr;
signal(SIGINT,sig_catcher);
for(;;) {
setjmp(flubber);
fputs("> ",stdout);
if(NULL == getline(buf))
break;
switch(toupper(buf[0])) {
case 'Q':
return 0;
case 'M':
if(1 == sscanf(buf+1,"%u",&siz))
printf("malloc(%u) = %04x\n",siz,malloc(siz));
else
printf("bad malloc string : %s\n",buf);
continue;
case 'F':
if(1 == sscanf(buf+1,
#ifndef LARGE_DATA
"%x"
#else
"%04x"
#endif
,&ptr))
printf("free(%04x) = %d\n",ptr,free(ptr));
else
printf("bad free string : %s\n",buf);
continue;
case 'P':
print_chain();
continue;
case 'A':
free_all();
continue;
case 'H':
printf("M = malloc <siz>\nF = free <ptr>\n");
printf("P = print malloc chain\nA = free everything\n");
printf("H = help\nQ = quit\nR = realloc <ptr> <size>\n");
printf("S = printf <ptr>\n");
continue;
case 'S':
if(sscanf(buf+1,"%x",&ptr) == 1)
printf("string = %s\n",ptr);
else
printf("bad pointer : %s\n",buf);
continue;
case 'R':
if(2 == sscanf(buf+1,"%x %u",&ptr,&siz))
printf("realloc(%04x,%u) = %04x\n",
ptr,siz,realloc(ptr,siz));
else
printf("bad realloc string : %s\n",buf);
continue;
}
}
}
#endif