source: buchla-68k/orig/GEMDOS/MEMORY.C@ d21fc6f

/*
   =============================================================================
        memory.c - memory allocation functions for GEMDOS
        Version 4 -- 1988-05-03 -- Beckemeyer (original) / Lynxcairne (mods)

        These routines implement the Unix standard C runtime
        library routines malloc(), free(), and realloc(),
        but are NOT compatible with intermixed brk() and sbrk() calls.

        The routines manage "heaps" allocated from the system.
        Each heap is carved up into some number of user memory
        blocks, as requested by malloc() and realloc() calls.

        As blocks are returned with free() calls, they are merged
        with any neighboring blocks that are free. Un-mergable
        blocks are stored on a doubly linked list.

        As heaps become full, new ones are created. The list of
        heaps is a singly linked list.  Heaps are returned to the
        system during garbage collection, which occurs whenever
        the current set of heaps cannot fill a memory request.

        This scheme avoids GEMDOS memory management problems
        and minimizes fragmentation.

        MINSEG below defines the minimum segment size allocated.
        Whenever the remaining portion of a block is smaller than
        this value, the entire block is returned to the caller.

        HEAPSIZE is the smallest system allocation we will ever
        make.  This value can be adjusted to your application.
        If it is small, more GEMDOS Malloc calls will have to
        be performed.  If it is large compared to the amount of
        memory actually aquired at runtime, there will be wasted
        memory.  Since too many GEMDOS Malloc calls may produce
        a crash, it is wise to make HEAPSIZE at least 8K bytes.

   =============================================================================
*/

#define DEBUGIT         1       /* define non-zero to compile debug code */

#include "stdio.h"
#include "osbind.h"
#include "stddefs.h"

/* memory manager definitions */

#define HEAPSIZE        16384L  /* minimum size of each heap */
#define MINSEG          256L    /* minimum size of allocated memory chunk */

#define MAGIC           0x55AA  /* magic number used for validation */

/* the structure controlling the object known as a "heap" */

#define HEAP struct _heap

/* Memory Control Block */

#define MCB struct _mcb

struct _mcb {

        MCB     *fore;          /* forward link */
        MCB     *aft;           /* backward link */
        MCB     *buddy;         /* nearest lower address neighbor */
        long    size;           /* size of this chunk including MCB */
        HEAP    *heap;          /* 0L if free, else owner of this chunk */      
        int     magic;          /* magic number for validation */
};

/* and here is the heap control block */

struct _heap {

        HEAP    *link;          /* pointer to next heap (0 if end) */
        MCB     *avail;         /* pointer to first free block or 0 */
        MCB     *limit;         /* address of the end of this heap */
};

#if     DEBUGIT
short   mal_dbg;                /* set non-zero for malloc debug trace */
#endif

/*
        List of allocated heaps aquired from GEMDOS.
        Start off with no heaps allocated (NULL terminated linked list).
 */

static HEAP heaps = { (HEAP *)0 };

/* 

*/

/*
   =============================================================================
        a_heap() --get another heap from GEMDOS
   =============================================================================
*/

static
HEAP *
a_heap(x)
long x;
{
        MCB *m;
        HEAP *heap;

        /* locate end of the heap list */
        /* (a tail pointer would help here) */

        for (heap = &heaps; heap->link; heap = heap->link)
                ;

        /* adjust the request for the minmum required overhead */

        x = (x + sizeof(HEAP) + sizeof(MCB) + 1) & ~1L;

        /* grab a chunk from GEMDOS */

        if ((heap->link = (HEAP *)Malloc(x)) EQ 0) {

#if     DEBUGIT
        if (mal_dbg) {

                printf("a_heap(%ld):  GEMDOS Malloc() returned 0\n", x);
                printf("      largest block available = %ld\n", Malloc(-1L));
        }
#endif
                return((HEAP *)0);
        }

        /* add the heap to the heap list */

        heap = heap->link;
        heap->link = (HEAP *)0;

        /* first chunk is just after header */

        m = (MCB *)(heap + 1);

        /* set up size and mark it as a free chunk */

        m->size = x - sizeof(HEAP);
        m->heap = 0L;

        /* this is the last (only) chunk on the linked list */

        m->fore = (MCB *)0;
        m->aft = (MCB *)(&heap->avail);

        /* there is no lower addressed neighbor to this chunk */

        m->buddy = (MCB *)0;

        /* mark the heap limit and place chunk on the free list */

        heap->limit = (MCB *)((char *)heap + x); 
        heap->avail = m;

        return(heap);
}

/* 

*/

/*
   =============================================================================
        s_split() -- split a segment into two chunks
   =============================================================================
*/

static
s_split(mcb, x)
MCB *mcb;
long x;
{
        MCB *m;
        HEAP *heap;

        /* check for ownership here */

        if (mcb EQ 0 OR (heap = mcb->heap) EQ 0 OR mcb->magic NE MAGIC) {

#if     DEBUGIT
                if (mal_dbg)
                        printf("s_split($%lx, %ld):  MCB invalid\n", mcb, x);
#endif
                return(FAILURE);
        }

        /* make a new chunk inside this one */

        m = (MCB *)((char *)mcb + x);
        m->size  = mcb->size - x;
        m->buddy = mcb;
        m->heap  = mcb->heap;
        m->magic = MAGIC;

        /* shrink the old chunk */

        mcb->size = x;

        /* establish the forward neighbor's relationship to us */

        mcb = m;

        if ((m = (MCB *)((char *)mcb + mcb->size)) < heap->limit)
                m->buddy = mcb;

        free(++mcb);
        return(SUCCESS);
}

/* 

*/

/*
   =============================================================================
        aloc_s() -- allocate a chunk out of a heap
   =============================================================================
*/

static
MCB *
aloc_s(x, heap)
long x;
HEAP *heap;
{
        MCB *mcb;

        /* use first fit algorithm to find chunk to use */

        for (mcb = heap->avail; mcb; mcb = mcb->fore)
                if (mcb->size GE x + sizeof(MCB))
                        break;

        if (mcb) {

                /* remove it from the free list */

                unfree(mcb);

                /* set up owner */

                mcb->heap = heap;
                mcb->magic = MAGIC;

                /* if it's bigger than we need and splitable, split it */

                if (mcb->size - x > MINSEG)
                        if (s_split(mcb, x + sizeof(MCB)))
                                return((MCB *)0);

                /* return start of data area to caller */

                mcb++;
        }

        return(mcb);
}

/* 

*/

/*
   =============================================================================
        unfree() -- remove (unlink) a chunk from the free list
   =============================================================================
*/

static
unfree(mcb)
MCB *mcb;
{
        if ((mcb->aft->fore = mcb->fore) NE 0)
                mcb->fore->aft = mcb->aft;
}



/*
   =============================================================================
        collect() -- GEMDOS garbage collection, return TRUE if anything changes
   =============================================================================
*/

static
collect()
{
        HEAP *heap, *h;
        MCB *mcb;
        int flag;

#if     DEBUGIT
        if (mal_dbg)
                printf("collect():  collecting garbage ...\n");
#endif
        
        for (flag = 0, heap = &heaps; (h = heap->link) NE 0; ) {

                if ((mcb = h->avail) NE 0 AND
                     NOT mcb->buddy AND ((char *)mcb + mcb->size) EQ h->limit) {

                        heap->link = h->link;
                        Mfree(h);
                        flag++;
                        
                } else
                        heap = h;
        }

        return(flag);
}

/* 

*/

/*
   =============================================================================

        Unix standard C runtime library routines
        malloc(), free(), and realloc() follow.

        The three calls work as described in K & R,
        except that they don't use brk() or sbrk(),
        so BEWARE.

        This implementation uses a first fit algorithm
        and does occasional garbage collection to
        minimize system memory fragmentation.

   =============================================================================
*/


/*
   =============================================================================
        malloc() -- allocate 'n' bytes of memory
   =============================================================================
*/


char *
malloc(n)
unsigned n;
{
        register HEAP *heap;
        register long x;
        char *p;

        x = (long)(n + 1) & ~1L;

        /* first check all current heaps */

        for (heap = heaps.link; heap; heap = heap->link)
                if ((p = aloc_s(x, heap)) NE 0)
                        return(p);

        /* not enough room on heap list, try garbage collection */

        collect();

        /* now allocate a new heap */

        if ((heap = a_heap(max(x, HEAPSIZE))) NE 0)
                if ((p = aloc_s(x, heap)) NE 0)
                        return(p);

        /* couldn't get a chunk big enough */

#if     DEBUGIT
        if (mal_dbg)
                printf("malloc(%u):  unable to find a large enough chunk\n", n);
#endif

        return((char *)0);
}

/* 

*/


/*
   =============================================================================
        free() -- return a block 'mcb' of memory to the storage pool
   =============================================================================
*/


free(mcb)
MCB *mcb;
{
        MCB *m;
        HEAP *heap;

        /* address header */

        mcb--;

        /* check for ownership here */

        if (mcb EQ 0 OR (heap = mcb->heap) EQ 0 OR mcb->magic NE MAGIC) {

#if     DEBUGIT
        printf("free($%lx):  MCB invalid\n", mcb);
#endif

                return(-40);
        }
                
        /* connect to chunks behind this one */

        while (mcb->buddy) {

                if (mcb->buddy->heap)
                        break;

                mcb->buddy->size += mcb->size;
                mcb = mcb->buddy;
                unfree(mcb);
        }

        /* now connect to chunks after this one */

        while ((m = (MCB *)((char *)mcb + mcb->size)) < heap->limit) {

                m->buddy = mcb;

                if (m->heap)
                        break;

                mcb->size += m->size;
                unfree(m);
        }

        /* place the resultant chunk on the free list */

        for (m = (MCB *)(&heap->avail); m->fore; m = m->fore)
                ;

        m->fore = mcb;
        mcb->fore = (MCB *)0;
        mcb->aft = m;
        mcb->heap = 0L;
        return(0);
}

/* 

*/


/*
   =============================================================================
        realloc() -- reallocate a block of memory
   =============================================================================
*/


char *
realloc(mcb, n)
MCB *mcb;
unsigned n;
{
        long x;
        char *t, *s, *p;

        /* address header */

        --mcb;

        /* check for ownership here */

        if (mcb EQ 0 OR mcb->magic NE MAGIC) {

#if     DEBUGIT
        printf("realloc($%lx, %u):  MCB invalid\n", mcb, n);
#endif

                return((char *)0);
        }

        /* round up the request and add overhead */

        x = (long)(n + 1 + sizeof(MCB)) & ~1L;

        /* if less than current size, just shrink it */

        if (mcb->size > x) {

                if (s_split(mcb, x))
                        return((char *)0);
                else
                        return((char *)(++mcb));
        }

        /* it's bigger - allocate new block, copy data, and free old one */

        if ((p = malloc(n)) NE 0) {

                x = mcb->size - sizeof(MCB);
                s = ++mcb;
                t = p;

                while (x--)
                        *t++ = *s++;

                free(mcb);
                return(p);
        }

#if     DEBUGIT
        printf("realloc($%lx, %u):  unable to reallocate\n", mcb, n);
#endif
        return((char *)0);
}