Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/misc/volume1/8706/25

Text File | 1993-09-02 | 15.4 KB | 643 lines

Article 62 of comp.sources.misc:
Relay-Version: version B 2.10.3 alpha 5/22/85; site osu-eddie.UUCP
Path: osu-eddie!cbosgd!ucbvax!ucbcad!ames!oliveb!pyramid!uccba!hal!ncoast!allbery
From: [e-mail] (Kent Williams)
Newsgroups: comp.sources.misc
Subject: Replacement malloc for Microsoft C 4.0
Message-ID: <[e-mail]>
Date: 16 Jun 87 20:04:49 GMT
Date-Received: 17 Jun 87 12:33:52 GMT
Sender: [e-mail]
Distribution: comp
Organization: Cleveland Public Access UN*X, Cleveland, OH
Lines: 623
Keywords: malloc MSC
Approved: [e-mail]
X-Archive: comp.sources.misc/8706/25

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