From david%bdt%hoptoad%lll-crg%ames.uucp@mailrus.cc.umich.edu Thu Sep 22 01:15:09 1988
Received: from mailrus.cc.umich.edu by polymnia.math.lsa.umich.edu (5.59/umix-1.1)
	id AA08618; Thu, 22 Sep 88 01:15:00 EDT
Received: from ames.arc.nasa.gov by mailrus.cc.umich.edu (5.59/1.0)
	id AA15150; Thu, 22 Sep 88 01:17:30 EDT
From: david%bdt%hoptoad%lll-crg%ames.uucp@mailrus.cc.umich.edu
Received: Wed, 21 Sep 88 22:16:15 PDT by ames.arc.nasa.gov (5.59/1.2)
Received: by lll-crg.llnl.gov (5.54/1.14)
	id AA16660; Wed, 21 Sep 88 22:05:15 PDT
Received: from bdt.UUCP by hop.toad.com id AA13716; Wed, 21 Sep 88 18:02:34 PDT
Message-Id: <8809220102.AA13716@hop.toad.com>
To: dyer%math.lsa.umich.edu%mailrus%ames%lll-crg%hoptoad.uucp@mailrus.cc.umich.edu
Date: Wed, 21 Sep 88 9:10:22 PDT
Subject: Re: Memory Allocator - who wants it?
In-Reply-To: Message from "math.lsa.umich.edu!dyer" of Sep 17, 88 at 11:16 pm
X-Mailer: Elm [version 1.5]
Status: R

OK.  Here's the malloc I use with Alcyon C.

I am not doing a lot of new Atari ST product development, btu we are
continuing to market and support all of our products, including new
improvements and enhancements.   We will probably begin a new ST
marketing effort this month.   Our Retail Software is becoming
popular in the Mega ST configuration, I guess for price considerations.

	- David Beckemeyer

------- CUT HERE ------

/************************************************************************/
/*									*/
/*	(c) Copyright 1986						*/
/*	David Beckemeyer						*/
/*	All Rights Reserved 						*/
/*									*/
/*	memory.c - memory allocation module				*/
/*									*/
/*	This is an implementation of the Unix standard C runtime	*/
/*	library routines malloc(), free(), and realloc().		*/
/*									*/
/*	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.		*/
/*									*/
/************************************************************************/

#include <stdio.h>
#include <osbind.h>


/* memory manager definitions */
#define MAGIC 0x55aa		/* magic number used for validation */
#define HEAPSIZE 16384L		/* minimum size of each heap */
#define MINSEG 256L		/* minimum size of allocated memory chunk */

/* the structure controlling the object known as heap */
#define HEAP struct _heap

/* Memory Control Block */
#define MCB struct _mcb
struct _mcb {
	MCB *fore;		/* forward link */
	MCB *aft;		/* backward link */
	MCB *neighbor;		/* 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 *freelist;		/* pointer to first free block or 0 */
	MCB *limit;		/* address of the end of this heap */
};

/* List of allocated heaps aquired from GEMDOS.
 * Start off with no heaps allocated (NULL terminated linked list).
 */
static HEAP heaplist = { (HEAP *)0 };

	
/* get another heap from GEMDOS */

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

	/* locate end of the heaplist (a tail pointer might help here) */
	for (heap = &heaplist; 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)) == 0)
		return((HEAP *)0);

	/* add the heap to the heaplist */
	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->freelist);

	/* there is no lower addressed neighbor to this chunk */
	m->neighbor = (MCB *)0;

	/* mark the heap limit and place chunk on freelist */
	heap->limit = (MCB *)((char *)heap + x); 
	heap->freelist = m;
	return(heap);
}


/* split a segment into two chunks */

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

	/* check for ownership here */
	if (mcb == 0 || (heap = mcb->heap) == 0 || mcb->magic != MAGIC) {
		return(-40);
	}

	/* make a new chunk inside this one */
	m = (MCB *)((char *)mcb + x);
	m->size = mcb->size - x;
	m->neighbor = 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->neighbor = mcb;
	free(++mcb);
	return(0);
}



/* allocate a chunk out of a heap */

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

	/* use first fit algorithm to find chunk to use */
	for (mcb = heap->freelist; mcb; mcb = mcb->fore)
		if (mcb->size >= x + sizeof(MCB))
			break;
	if (mcb) {
		/* remove it from the freelist */
		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)
			split_seg(mcb, x + sizeof(MCB));
		/* return start of data area to caller */
		mcb++;
	}
	return(mcb);
}



/* remove (unlink) a chunk from the freelist */

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



/* GEMDOS garbage collection, return TRUE if anything changes */

static collect()
{
	HEAP *heap, *h;
	MCB *mcb;
	int flag;
	
	for (flag = 0, heap = &heaplist; (h = heap->link) != 0; ) {
		if ((mcb = h->freelist) != 0 &&
		 !mcb->neighbor && ((char *)mcb + mcb->size) == 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.
 *
 *	This implementation uses a first fit algorithm
 *	and does occasional garbage collection to
 *	minimize system memory fragmentation.
 *
 *****************************************************

/****************/
/*		*/
/*    malloc	*/
/*		*/
/****************/

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

	/* malloc is supposed to accept all 16 bits so fix it up here */
	if (n < 0)
		x = 65537L + (long)n & ~1L;
	else
		x = (long)(n + 1) & ~1L;

	/* first check all current heaps */
	for (heap = heaplist.link; heap; heap = heap->link)
		if ((p = alloc_seg(x, heap)) != 0)
			return(p);

	/* not enough room on heaps, try garbage collection */
	collect();

	/* now allocate a new heap */
	if ((heap = alloc_heap(max(x, HEAPSIZE))) != 0)
		if ((p = alloc_seg(x, heap)) != 0)
			return(p);

	/* couldn't get a chunk big enough */
	return((char *)0);
}


/****************/
/*		*/
/*     free	*/
/*		*/
/****************/

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

	/* address header */
	mcb--;

	/* check for ownership here */
	if (mcb == 0 || (heap = mcb->heap) == 0 || mcb->magic != MAGIC) {
		return(-40);
	}
		
	/* connect to chunks behind this one */
	while (mcb->neighbor) {
		if (mcb->neighbor->heap)
			break;
		mcb->neighbor->size += mcb->size;
		mcb = mcb->neighbor;
		unfree(mcb);
	}

	/* now connect to chunks after this one */
	while ((m = (MCB *)((char *)mcb + mcb->size)) < heap->limit) {
		m->neighbor = mcb;
		if (m->heap)
			break;
		mcb->size += m->size;
		unfree(m);
	}
	/* place the resultant chunk on the free list */
	for (m = (MCB *)(&heap->freelist); m->fore; m = m->fore)
		;
	m->fore = mcb;
	mcb->fore = (MCB *)0;
	mcb->aft = m;
	mcb->heap = 0L;
	return(0);
}



/****************/
/*		*/
/*   realloc	*/
/*		*/
/****************/

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

	/* address header */
	--mcb;

	/* check for ownership here */
	if (mcb == 0 || mcb->magic != MAGIC) {
		return((char *)0);
	}

	/* malloc is supposed to accept all 16 bits so fix it up here */
	if (n < 0)
		x = (65537L + (long)n + sizeof(MCB)) & ~1L;
	else
		x = (long)(n + 1 + sizeof(MCB)) & ~1L;

	/* if less than current size, just shrink it */
	if (mcb->size > x) {
		split_seg(mcb, x);
		return((char *)(++mcb));
	}

	/* it's bigger - allocate new block, copy data, and free old one */
	if ((p = malloc(n)) != 0) {
		x = mcb->size - sizeof(MCB);
		s = ++mcb;
		t = p;
		while (x--)
			*t++ = *s++;
		free(mcb);
		return(p);
	}
	return((char *)0);
}