Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/unix/volume6/malloc

Text File | 1986-11-30 | 26KB | 1,033 lines

Subject: v06i054:  A "smarter" malloc (malloc)
Newsgroups: mod.sources
Approved: [e-mail]

Submitted by: cca!astrovax!wls (William L. Sebok)
Mod.sources: Volume 6, Issue 54
Archive-name: malloc

--------Cut Here----------
# This is a shell archive.  Remove anything before this line,
# then unpack it by saving it in a file and typing "sh file".
#
# Wrapped by astrovax!wls on Thu Jul  3 13:20:20 EDT 1986
# Contents:  README malloc.3 forget.3 malloc.h malloc.c free.c realloc.c
#    forget.c tstmalloc.c asm.sed malloc.adb

echo x - README
sed 's/^@//' > "README" <<'@//E*O*F README//'
This is the malloc()/free()/realloc()/forget() package used at astrovax.

It does not have the property of the 4.2 BSD malloc of allocating huge amounts
of excess memory.  Image processing is done here and large malloc requests
are not rare.  It is quite undesirable when one asks for 4.1 megabytes of memory
to have it try to return 8 megabytes and to fail because the process goes over
quota or there is not enough swap space.

Also this malloc does not have the property of the 4.1 BSD malloc that a search
for free memory traverses a linked list that covers all previous allocations,
causing thrashing by touching them and thus paging them back into memory.

Hopefully this malloc covers the best of both worlds.  There is a fair attempt
at storage compaction, merging freed areas with adjacent free areas and
optionally returning freed areas adjacent to the break back to the system,
thereby shrinking the size of the process.

It is also allowable and compatible with this package to obtain memory by the
use of the sbrk() system call.  This memory can be reclaimed and returned to
the malloc arena by the use of the provided forget() function.  This function
is intended to provide the functionality of the Forth FORGET primitive in
an environment that also includes malloc and free.

The main disadvantage of this package is a larger storage overhead of 24 bytes
per memory area, due to the fact that each area is linked into two
bi-directional chains.

Non-vax users should edit the commented system-dependent parts of Makefile and
malloc.h for the requirements of one's own computer.

Bill Sebok            Princeton University, Astrophysics
{allegra,akgua,cbosgd,decvax,ihnp4,noao,philabs,princeton,vax135}!astrovax!wls
@//E*O*F README//
chmod u=rw,g=r,o=r README

echo x - malloc.3
sed 's/^@//' > "malloc.3" <<'@//E*O*F malloc.3//'
@.TH MALLOC 3  "30 June 1986"
@.SH NAME
malloc, free, realloc \- memory allocator
@.SH SYNOPSIS
@.nf
@.B char *malloc(size)
@.B Size size;
@.PP
@.B void free(ptr)
@.B char *ptr;
@.PP
@.B char *realloc(ptr, size)
@.B char *ptr;
@.B Size size;
@.PP
@.B extern char endfree
@.PP
@.B extern void (*mlabort)()
@.fi
@.PP
Where
@.I Size
is an integer large enough to hold a char pointer.
@.SH DESCRIPTION
@.I Malloc
and
@.I free
provide a simple general-purpose memory allocation package.
@.I Malloc
returns a pointer to a block of at least
@.I size
bytes beginning on the boundary of the most stringent alignment required
by the architecture.
@.PP
The argument to
@.I free
is a pointer to a block previously allocated by
@.IR malloc ;
this space is made available for further allocation,
but its contents are left undisturbed.
@.PP
Needless to say, grave disorder will result if the space assigned by
@.I malloc
is overrun or if some random number is handed to
@.IR free .
@.PP
@.I Malloc
maintains multiple lists of free blocks according to size,
allocating space from the appropriate list.
It calls
@.I brk
(see
@.IR brk (2))
to get more memory from the system when there is no
suitable space already free.
@.PP
@.I Free
makes an attempt to merge newly freed memory with adjacent free areas.
If the result of this merging is an area that touches the system break
(the current location of the highest valid address of the data segment of the
process) and if
@.I
endfree
has a non-zero value,  then break is moved back, contracting the process
size and releasing the memory back to the system.
@.PP
By default
@.I endfree
has a value of 0, which disables the release of memory back to the system.
@.PP
It is valid to also allocate memory by the use of
@.I sbrk(3)
or by moving up the break with
@.I brk(3).
This memory may be reclaimed and returned to
the \fImalloc\fP/\fIfree\fP arena by the use of
@.I forget
(see \fIforget\fP(3)).
@.PP
@.I Realloc
changes the size of the block pointed to by
@.I ptr
to
@.I size
bytes and returns a pointer to the (possibly moved) block.
The contents will be unchanged up to the lesser of the new and old sizes.
@.PP
In order to be compatible with older versions,
if
@.I endfree
is 0, then
@.I realloc
also works if
@.I ptr
points to a block freed since the last call of
@.I malloc
or
@.I realloc.
Sequences of
@.I free, malloc
and
@.I realloc
were previously used to attempt storage compaction.
This procedure is no longer recommended.
In this implementation
@.I Realloc,
@.I malloc
and
@.I free
do a fair amount of their own storage compaction anyway.
@.SH DIAGNOSTICS
@.I Malloc, realloc
return a null pointer (0) if there is no available memory or if the arena
has been detectably corrupted by storing outside the bounds of a block.
@.I Realloc
makes an attempt to detect and return a null pointer when the break has been
moved so that the requested address is no longer valid.
@.I Malloc
may be recompiled to check the arena very stringently on every transaction;
those sites with a source code license may do this by recompiling the source
with  -Ddebug .
@.PP
On detection of corruption of the malloc arena the normal response is an
abort with a core dump.  This response can be changed by placing a pointer to
a function with the desired response into the extern pointer
@.I mlabort.
@.SH ALGORITHM
@.I Malloc
returns a block of size equal to the size requested plus an overhead (24
bytes for a 32 bit machine).
Freed memory is linked into a chain selected by the size of the freed area
(currently, memory size of items in a chain is between two adjacent powers of
2).
The search for memory starts with the chain whose length index is at least
equal to the size of the request and proceeds if unsuccessful to larger
memory size chains.  If there is any surplus memory left after the filling
of a request it is returned to the appropriate free list chain.
@.SH BUGS
When
@.I realloc
returns 0, the block pointed to by
@.I ptr
may have been destroyed.
@//E*O*F malloc.3//
chmod u=rw,g=r,o=r malloc.3

echo x - forget.3
sed 's/^@//' > "forget.3" <<'@//E*O*F forget.3//'
@.TH FORGET 3  "30 June 1986"
@.SH NAME
forget \- reclaim sbrk'ed memory into malloc arena
@.SH SYNOPSIS
@.nf
@.B void forget(ptr)
@.B char *ptr;
@.PP
@.B extern char endfree
@.SH DESCRIPTION
@.I Forget
provides a way of reclaiming memory obtained by
@.I sbrk(3)
and returning it to the malloc arena.  All such memory above
@.I ptr
(the "forget point") is marked free and merged if possible with adjacent
free areas.  If
@.I endfree
is non-zero any such memory adjacent to the "break" (the highest valid
data address for the process) is released to the system by moving back
the break.
@.PP
This function was written to provide the functionality of the Forth
FORGET primitive in an environment where
a dictionary is grown by
@.I sbrk
and
@.I malloc
and
@.I free
are also present.
@.SH BUGS
When the specified forget point is below the initial end of the program,
disaster can result.
@//E*O*F forget.3//
chmod u=rw,g=r,o=r forget.3

echo x - malloc.h
sed 's/^@//' > "malloc.h" <<'@//E*O*F malloc.h//'
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * A  "smarter" malloc                William L. Sebok
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *    Algorithm:
 *     Assign to each area an index "n". This is currently proportional to
 *    the log 2 of size of the area rounded down to the nearest integer.
 *    Then all free areas of storage whose length have the same index n are
 *    organized into a chain with other free areas of index n (the "bucket"
 *    chain). A request for allocation of storage first searches the list of
 *    free memory.  The search starts at the bucket chain of index equal to
 *    that of the storage request, continuing to higher index bucket chains
 *    if the first attempt fails.
 *    If the search fails then new memory is allocated.  Only the amount of
 *    new memory needed is allocated.  Any old free memory left after an
 *    allocation is returned to the free list.
 *
 *      All memory areas (free or busy) handled by malloc are also chained
 *    sequentially by increasing address (the adjacency chain).  When memory
 *    is freed it is merged with adjacent free areas, if any.  If a free area
 *    of memory ends at the end of memory (i.e. at the break), and if the
 *    variable "endfree" is non-zero, then the break is contracted, freeing
 *    the memory back to the system.
 *
 *    Notes:
 *        ov_length field includes sizeof(struct overhead)
 *        adjacency chain includes all memory, allocated plus free.
 */

/* the following items may need to be configured for a particular machine */

/* alignment requirement for machine (in bytes) */
#define NALIGN    4

/* size of an integer large enough to hold a character pointer */
typedef    long    Size;

/*
 * CURBRK returns the value of the current system break, i.e., the system's
 * idea of the highest legal address in the data area.  It is defined as
 * a macro for the benefit of systems that have provided an easier way to
 * obtain this number (such as in an external variable)
 */

#ifndef CURBRK
#define CURBRK    sbrk(0)
extern char *sbrk();
#else  CURBRK
#    if    CURBRK == curbrk
extern Size curbrk;
#    endif
#endif CURBRK

/*
 * note that it is assumed that CURBRK remembers the last requested break to
 * the nearest byte (or at least the nearest word) rather than the nearest page
 * boundary.  If this is not true then the following BRK macro should be
 * replaced with one that remembers the break to within word-size accuracy.
 */

#ifndef BRK
#define BRK(x)    brk(x)
extern char *brk();
#endif  BRK

/* END of machine dependent portion */

#define    MAGIC_FREE    0x548a934c
#define    MAGIC_BUSY    0xc139569a

#define NBUCKETS    18

struct qelem {
    struct qelem *q_forw;
    struct qelem *q_back;
};

struct overhead {
    struct qelem    ov_adj;        /* adjacency chain pointers */
    struct qelem    ov_buk;        /* bucket chain pointers */
    long        ov_magic;
    Size        ov_length;
};

/*
 * The following macros depend on the order of the elements in struct overhead
 */
#define TOADJ(p)    ((struct qelem *)(p))
#define FROMADJ(p)    ((struct overhead *)(p))
#define FROMBUK(p)    ((struct overhead *)( (char *)p - sizeof(struct qelem)))
#define TOBUK(p)    ((struct qelem *)( (char *)p + sizeof(struct qelem)))

#ifdef MALLOC
/*
 * return to the system memory freed adjacent to the break
 * default is Off
 */
char endfree = 0;

/* sizes of buckets currently proportional to log 2() */
Size mlsizes[] = {0, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768,
    65536, 131072, 262144, 524288, 1048576, 2097152, 4194304};

/* head of adjacency chain */
struct qelem adjhead = { &adjhead, &adjhead };

/* head of bucket chains */
struct qelem buckets[NBUCKETS] = {
    &buckets[0],  &buckets[0],    &buckets[1],  &buckets[1],
    &buckets[2],  &buckets[2],    &buckets[3],  &buckets[3],
    &buckets[4],  &buckets[4],    &buckets[5],  &buckets[5],
    &buckets[6],  &buckets[6],    &buckets[7],  &buckets[7],
    &buckets[8],  &buckets[8],    &buckets[9],  &buckets[9],
    &buckets[10], &buckets[10],    &buckets[11], &buckets[11],
    &buckets[12], &buckets[12],    &buckets[13], &buckets[13],
    &buckets[14], &buckets[14],    &buckets[15], &buckets[15],
    &buckets[16], &buckets[16],    &buckets[17], &buckets[17]
};

void (*mlabort)() = {0};

#else
extern char endfree;
extern struct qelem adjhead, buckets[NBUCKETS];
extern Size mlsizes[NBUCKETS];
extern void (*mlabort)();
#endif

extern void insque(), remque();
extern void free(), mllcerr();
extern char *malloc(), *realloc();

#ifdef debug
# define ASSERT(p,q)    if (!(p)) mllcerr(q)
#else
# define ASSERT(p,q)
#endif
@//E*O*F malloc.h//
chmod u=rw,g=r,o=r malloc.h

echo x - malloc.c
sed 's/^@//' > "malloc.c" <<'@//E*O*F malloc.c//'
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * A  "smarter" malloc v1.0            William L. Sebok
 *                    Sept. 24, 1984 rev. June 30,1986
 *
 *    malloc allocates and returns a pointer to a piece of memory nbytes
 *    in size.
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#define MALLOC
#include "malloc.h"

#define NULL    0

char *
malloc(nbytes)
    Size nbytes;
{
    register struct overhead *p, *q;
    register struct qelem *bucket;
    register Size surplus;
    Size mlindx();

    nbytes = ((nbytes + (NALIGN-1)) & ~(NALIGN-1))
        + sizeof(struct overhead);

    for (
        bucket = &buckets[mlindx(nbytes)];
        bucket < &buckets[NBUCKETS];
        bucket++
    ) {
        register struct qelem *b;
        for(b = bucket->q_forw; b != bucket; b = b->q_forw) {
            p = FROMBUK(b);
            ASSERT(p->ov_magic == MAGIC_FREE,
"\nmalloc: Entry not marked FREE found on Free List!\n");
            if (p->ov_length >= nbytes) {
                remque(b);
                surplus = p->ov_length - nbytes;
                goto foundit;
            }
        }
    }

    /* obtain additional memory from system */
    {
        register Size i;
        p = (struct overhead *)CURBRK;

        i = ((Size)p)&(NALIGN-1);
        if (i != 0)
            p = (struct overhead *)((char *)p + NALIGN - i);

        if (BRK((char *)p + nbytes))
            return(NULL);

        p->ov_length = nbytes;
        surplus = 0;

        /* add to end of adjacency chain */
        ASSERT((FROMADJ(adjhead.q_back)) < p,
"\nmalloc: Entry in adjacency chain found with address lower than Chain head!\n"
            );
        insque(TOADJ(p),adjhead.q_back);
    }

foundit:
    /* mark surplus memory free */
    if (surplus > sizeof(struct overhead)) {
        /* if big enough, split it up */
        q = (struct overhead *)((char *)p + nbytes);

        q->ov_length = surplus;
        p->ov_length = nbytes;
        q->ov_magic = MAGIC_FREE;

        /* add surplus into adjacency chain */
        insque(TOADJ(q),TOADJ(p));

        /* add surplus into bucket chain */
        insque(TOBUK(q),&buckets[mlindx(surplus)]);
    }

    p->ov_magic = MAGIC_BUSY;
    return((char*)p + sizeof(struct overhead));
}

/*
 * select the proper size bucket
 */
Size
mlindx(n)
register Size n;
{
    register Size *p, *q, *r;
    p = &mlsizes[0];
    r = &mlsizes[NBUCKETS];
    /* binary search */
    while ((q = (p + (r-p)/2)) > p) {
        if (n < *q)
            r = q;
        else
            p = q;
    }
    return(q - &mlsizes[0]);
}

void
mllcerr(p)
char *p;
{
    register char *q;
    q = p;
    while (*q++);    /* find end of string */
    (void)write(2,p,q-p-1);
    if (mlabort)
        (*mlabort)();
#ifdef debug
    else
        abort();
#endif debug
}

#ifndef vax
/*
 * The vax has wondrous instructions for inserting and removing items into
 * doubly linked queues.  On the vax the assembler output of the C compiler is
 * massaged by an sed script to turn these function calls into invocations of
 * the insque and remque machine instructions.
 */

void
insque(item,queu)
register struct qelem *item, *queu;
/* insert "item" after "queu" */
{
    register struct qelem *pueu;
    pueu = queu->q_forw;
    item->q_forw = pueu;
    item->q_back = queu;
    queu->q_forw = item;
    pueu->q_back = item;
}

void
remque(item)
register struct qelem *item;
/* remove "item" */
{
    register struct qelem *queu, *pueu;
    pueu = item->q_forw;
    queu = item->q_back;
    queu->q_forw = pueu;
    pueu->q_back = queu;
}
#endif
@//E*O*F malloc.c//
chmod u=rw,g=r,o=r malloc.c

echo x - free.c
sed 's/^@//' > "free.c" <<'@//E*O*F free.c//'
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *  free                    William L. Sebok
 * A "smarter" malloc v1.0        Sept. 24, 1984 rev. June 30,1986
 *
 *     free takes a previously malloc-allocated area at mem and frees it.
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */


#include "malloc.h"

#define NULL    0

void
free(mem)
register char *mem;
{
    register struct overhead *p, *q;
    void mlfree_end();

    if (mem == NULL)
        return;

    p = (struct overhead *)(mem - sizeof(struct overhead));

    /* not advised but allowed */
    if (p->ov_magic == MAGIC_FREE)
        return;

    if (p->ov_magic != MAGIC_BUSY)
        mllcerr("attempt to free memory not allocated with malloc!\n");

    /* try to merge with previous free area */
    q = FROMADJ((TOADJ(p))->q_back);

    if (q != FROMADJ(&adjhead)) {
        ASSERT(q < p,
"\nfree: While trying to merge a free area with a lower adjacent free area,\n\
 addresses were found out of order!\n");
        /* If lower segment can be merged */
        if (   q->ov_magic == MAGIC_FREE
           && (char *)q + q->ov_length == (char *)p
        ) {
            /* remove lower address area from bucket chain */
            remque(TOBUK(q));

            /* remove upper address area from adjacency chain */
            remque(TOADJ(p));

            q->ov_length += p->ov_length;
            p->ov_magic = NULL;    /* decommission */
            p = q;
        }
    }

    /* try to merge with next higher free area */
    q = FROMADJ((TOADJ(p))->q_forw);

    if (q != FROMADJ(&adjhead)) {
        /* upper segment can be merged */
        ASSERT(q > p,
"\nfree: While trying to merge a free area with a higher adjacent free area,\n\
 addresses were found out of order!\n");
        if (     q->ov_magic == MAGIC_FREE
           &&    (char *)p + p->ov_length == (char *)q
        ) {
            /* remove upper from bucket chain */
            remque(TOBUK(q));

            /* remove upper from adjacency chain */
            remque(TOADJ(q));

            p->ov_length += q->ov_length;
            q->ov_magic = NULL;    /* decommission */
        }
    }

    p->ov_magic = MAGIC_FREE;

    /* place in bucket chain */
    insque(TOBUK(p),&buckets[mlindx(p->ov_length)]);

    if (endfree)
        mlfree_end();

    return;
}

void
mlfree_end()
{
    register struct overhead *p;

    p = FROMADJ(adjhead.q_back);
    if (    /* area is free and at end of memory */
            p->ov_magic == MAGIC_FREE
        &&    (char*)p + p->ov_length == (char *)CURBRK
    ) {
        p->ov_magic = NULL;    /* decommission (just in case) */

        /* remove from end of adjacency chain */
        remque(TOADJ(p));

        /* remove from bucket chain */
        remque(TOBUK(p));

        /* release memory to system */
        (void)BRK((char *)p);
    }
    return;
}
@//E*O*F free.c//
chmod u=rw,g=r,o=r free.c

echo x - realloc.c
sed 's/^@//' > "realloc.c" <<'@//E*O*F realloc.c//'
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *  realloc                William L. Sebok
 * A  "smarter" malloc v1.0        Sept. 24, 1984 rev. June 30,1986
 *
 *    realloc takes previously malloc-allocated area at mem, and tries
 *     to change its size to nbytes bytes, moving it and copying its
 *     contents if necessary.
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include "malloc.h"

#ifndef    NULL
#define NULL    0
#endif

char *
realloc(mem,nbytes)
register char *mem; unsigned nbytes;
{
    register char *newmem;
    register struct overhead *p, *q;
    Size surplus, length;
    char oendfree;

    if (mem == NULL)
        return(malloc(nbytes));

    /* if beyond current arena it has to be bad */
    if(mem > (char*)FROMADJ(adjhead.q_back) + sizeof(struct overhead))
        return(NULL);

    p = (struct overhead *)(mem - sizeof(struct overhead));

    if (p->ov_magic != MAGIC_BUSY && p->ov_magic != MAGIC_FREE)
        return(NULL);    /* already gone */

    length = p->ov_length;

    nbytes = (nbytes + (NALIGN-1)) & (~(NALIGN-1));

    if (p->ov_magic == MAGIC_BUSY) {
        oendfree = endfree;    endfree = 0;
        free(mem);    /* free it but don't let it contract break */
        endfree = oendfree;
    }

    if(  p->ov_magic == MAGIC_FREE
     && (surplus = length - nbytes - sizeof(struct overhead)) >= 0
    ) {
        /* shrink area in place */
        if (surplus > sizeof(struct overhead)) {
            q = (struct overhead *)( (char *)p + nbytes
                + sizeof(struct overhead));
            q->ov_length = surplus;
            q->ov_magic = MAGIC_FREE;
            insque(TOADJ(q),TOADJ(p));
            insque(TOBUK(q),&buckets[mlindx(surplus)]);
            p->ov_length -= surplus;
        }
        /* declare it to be busy */
        remque(TOBUK(p));
        p->ov_magic = MAGIC_BUSY;

        if (endfree)
            mlfree_end();
        return(mem);
    }

    /* if at break, grow in place */
    if (p->ov_magic == MAGIC_FREE && ((char *)p + p->ov_length) == CURBRK) {
        nbytes += sizeof(struct overhead);
        BRK((char *)p + nbytes);
        p->ov_length = nbytes;
        return(mem);
    }

    newmem = malloc(nbytes);

    if (newmem != mem && newmem != NULL) {
        register Size n;
        n = length - sizeof(struct overhead);
        nbytes = (nbytes < n) ? nbytes: n;
        (void)bcopy(mem,newmem,nbytes);
        /* note:
         * it is assumed that bcopy does the right thing on overlapping
         * extents (true on the vax)
         */
    }

    if (endfree)
        mlfree_end();

    return(newmem);
}
@//E*O*F realloc.c//
chmod u=rw,g=r,o=r realloc.c

echo x - forget.c
sed 's/^@//' > "forget.c" <<'@//E*O*F forget.c//'
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 *  forget                William L. Sebok
 * A "smarter" malloc v1.0        Sept. 24, 1984 rev. June 30,1986
 *
 *    forget returns to the malloc arena all memory allocated by sbrk()
 *     above "bpnt".
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include "malloc.h"

#define    NULL    0

void
forget(bpnt)
char *bpnt;
{
    register struct overhead *p, *q, *r, *b;
    register Size l;
    struct overhead *crbrk;
    char pinvalid, oendfree;

    /*
     * b = forget point
     * p = beginning of entry
     * q = end of entry, beginning of gap
     * r = end of gap, beginning of next entry (or the break)
     * pinvalid = true when groveling at forget point
     */

    pinvalid = 0;
    oendfree = endfree;    endfree = 0;
    b = (struct overhead *)bpnt;
    p = FROMADJ(adjhead.q_back);
    r = crbrk = (struct overhead *)CURBRK;

    for (;pinvalid == 0 && b < r; p = FROMADJ(TOADJ(r = p)->q_back)) {
        if ( p == FROMADJ(&adjhead)
         || (q = (struct overhead *)((char *)p + p->ov_length)) < b
        ) {
            pinvalid = 1;
            q = b;
        }

        if (q == r)
            continue;

        ASSERT(q < r,
"\nforget: addresses in adjacency chain are out of order!\n");

        /* end of gap is at break */
        if (oendfree && r == crbrk) {
            (void)BRK((char *)q);    /* free it yourself */
            crbrk = r = q;
            continue;
        }

        if (pinvalid)
            q = (struct overhead *) /* align q pointer */
                (((long)q + (NALIGN-1)) & (~(NALIGN-1)));

        l = (char *)r - (char *)q;
        /*
         * note: unless something is screwy: (l%NALIGN) == 0
         * as r should be aligned by this point
         */

        if (l >= sizeof(struct overhead)) {
            /* construct busy entry and free it */
            q->ov_magic = MAGIC_BUSY;
            q->ov_length = l;
            insque(TOADJ(q),TOADJ(p));
            free((char *)q + sizeof(struct overhead));
        } else if (pinvalid == 0) {
            /* append it to previous entry */
            p->ov_length += l;
            if (p->ov_magic == MAGIC_FREE) {
                remque(TOBUK(p));
                insque(TOBUK(p),&buckets[mlindx(p->ov_length)]);
            }
        }
    }
    endfree = oendfree;
    if (endfree)
        mlfree_end();
    return;
}
@//E*O*F forget.c//
chmod u=rw,g=r,o=r forget.c

echo x - tstmalloc.c
sed 's/^@//' > "tstmalloc.c" <<'@//E*O*F tstmalloc.c//'
/*
 * tstmalloc    this routine tests and exercizes the malloc/free package
 */
#include <stdio.h>
#include <setjmp.h>
#include "malloc.h"

jmp_buf env;

main(argc,argv)
int argc; char *argv[];
{
    char lin[100], arg1[20], arg2[20], arg3[20];
    char *res, *malloc(), *realloc();
    register struct overhead *p, *q;
    register struct qelem *qp;
    int arg, nargs, argn;
    int l;
    void malerror();

    mlabort = &malerror;
    setjmp(env);

    for (;;) {
        printf("*  ");
        if (fgets(lin,sizeof lin, stdin)== NULL)
            exit(0);
        nargs = sscanf(lin,"%s%s%s",arg1,arg2,arg3);
        switch (arg1[0]) {

        case 'b':
            if (nargs == 2) {
                arg = atoi(arg2);
                if (arg<0 ||  arg>=NBUCKETS)
                    goto bad;

                qp = &buckets[arg];
                printf("Bucket %2d\t\t\t  buk=%08lx %08lx\n",
                    arg, qp->q_forw,qp->q_back);
                qp = qp->q_forw;
                for (; qp != &buckets[arg]; qp = qp->q_forw) {
                    p = FROMBUK(qp);
                    if (dump(p))
                        break;
                }
            } else {
                printf("Buckets:");
                for (qp=buckets; qp<&buckets[NBUCKETS];qp++){
                    if (qp->q_forw != qp)
                        printf(" %d", qp-buckets);
                }
                printf("\n");
            }
            break;
        case 'e':
            endfree = 1;
            break;
        case 'E':
            endfree = 0;
            break;
        case 'f':
            if (nargs != 2) goto bad;
            sscanf(arg2,"%lx",&arg);
            printf("free(%x)\n",arg);
            free(arg);
            break;
        case 'F':
            if (nargs != 2) goto bad;
            sscanf(arg2,"%lx",&arg);
            printf("forget(%x)\n",arg);
            forget(arg);
            break;
        case 'h':
            printf("\
b    print bucket chains that aren't empty\n\
b [n]    trace through bucket chains\n\
e    turn on freeing of end of memory\n\
E    turn off freeing of end of memory\n\
f addr        free addr\n\
F addr        forget below addr\n\
h    print this help file\n\
m bytes        malloc bytes\n\
q    quit\n\
r addr bytes    realloc\n\
s    print break addr\n\
S    sbrk count\n\
t    trace through adjacency chain\n\
");
            break;
        case 'm':
            if (nargs != 2) goto bad;
            arg = atoi(arg2);
            res = malloc(arg);
            printf("malloc(%d) = %lx\n",arg, res);
            break;
        case 'r':
            if (nargs != 3) goto bad;
            sscanf(arg2,"%lx",&arg);
            argn = atoi(arg3);
            res = realloc(arg,argn);
            printf("realloc(%lx,%d) = %lx\n",arg,argn,res);
            break;
        case 'q':
            exit(0);
            break;
        case 's':
            printf("brk = %08x\n",sbrk(0));
            break;
        case 'S':
            if (nargs != 2) goto bad;
            sscanf(arg2,"%ld",&arg);
            printf("sbrk(%d)\n",arg);
            sbrk(arg);
            break;
        case 't':
            printf("\t\t\t\t\t\thead    adj=%08lx %08lx\n",
                adjhead.q_forw,adjhead.q_back);
            for (qp = adjhead.q_forw; qp!=&adjhead; qp=qp->q_forw) {
                p = FROMADJ(qp);
                if (dump(p))
                    break;
                q = FROMADJ(qp->q_forw);
                if (q==FROMADJ(&adjhead))
                    q = (struct overhead *)sbrk(0);
                l = (char *)q - (char *)p - p->ov_length;
                if (l>0)
                    printf("%08x free space  len=%8d\n",
                        (char *)p + p->ov_length, l);
            }
            break;
        default:
    bad:        printf("Bad command\n");
        }
    }
}

dump(p)
register struct overhead *p;
{
    register char *s;
    int stat = 0;

    if (p->ov_magic == MAGIC_FREE)
        s = "MAGIC_FREE ";
    else if (p->ov_magic == MAGIC_BUSY)
        s = "MAGIC_BUSY ";
    else {
        s = "BAD MAGIC  ";
        stat = 1;
    }

    printf( "%08x %s len=%8d buk=%08x %08x adj=%08x %08x\n",
        (&p[1]),s,p->ov_length,p->ov_buk.q_forw,p->ov_buk.q_back,
        p->ov_adj.q_forw,p->ov_adj.q_back
    );
    return(stat);
}

void
malerror()
{
    write(2,"malloc error\n",13);
    longjmp(env,1);
}
@//E*O*F tstmalloc.c//
chmod u=rw,g=r,o=r tstmalloc.c

echo x - asm.sed
sed 's/^@//' > "asm.sed" <<'@//E*O*F asm.sed//'
s/calls    $2,_insque/insque    *(sp)+,*(sp)+/
s/calls    $1,_remque/remque    *(sp)+,r0/
@//E*O*F asm.sed//
chmod u=rw,g=r,o=r asm.sed

echo x - malloc.adb
sed 's/^@//' > "malloc.adb" <<'@//E*O*F malloc.adb//'
@.>7
@./"adj "XX"buk "XX"MAG "X"len "Dn
(*(<7))
@//E*O*F malloc.adb//
chmod u=rw,g=r,o=r malloc.adb

exit 0
--------Cut Here----------