⟦3ead6b4f0⟧

TextFile

/* malloc.c - Quipu DSA specific memory management */

#ifndef	lint
static char *rcsid = "$Header: /f/osi/quipu/RCS/malloc.c,v 7.0 89/11/23 22:20:55 mrose Rel $";
#endif

/* 
 * $Header: /f/osi/quipu/RCS/malloc.c,v 7.0 89/11/23 22:20:55 mrose Rel $
 *
 *
 * $Log:	malloc.c,v $
 * Revision 7.0  89/11/23  22:20:55  mrose
 * Release 6.0
 * 
 */

/*
 *				  NOTICE
 *
 *    Acquisition, use, and distribution of this module and related
 *    materials are subject to the restrictions of a license agreement.
 *    Consult the Preface in the User's Manual for the full terms of
 *    this agreement.
 *
 */

#include <stdio.h>
#include "quipu/malloc.h"
#include "quipu/util.h"
#include "manifest.h"
#include <sys/types.h>

static int malloc_file = 0;

#ifdef QUIPU_MALLOC

extern LLog * log_dsap;
extern SFD attempt_restart();

#if	defined(DEBUG) && defined(sun3)
#define MALLOCSTACK
#endif

#ifdef MALLOCSTACK
#include <sys/file.h>
off_t lseek();
#ifndef MALLOCTRACE
#define MALLOCTRACE
#endif
#else
#define write_stack(x)
#endif


#define MAXHEAP		100		/* Number of heaps */
#ifndef	BSD42
#define PAGESIZE	0x2000		/* The systems memory page size */
#else
#define	PAGESIZE	pagesize
#endif

#define ALIGN(x)	(((x) + (sizeof(char *) - 1)) & ~(sizeof(char *) - 1))
#define PAGEALIGN(x)	(((x) + (PAGESIZE-1)) & ~(PAGESIZE-1))
#define SMALLMAX	65536	/* largest block a short can reference */


struct header {
	union {
		struct {
			unsigned short 	 control;
			unsigned short   size;
		} small;
		unsigned int big;
	} un;
};

#define bigsize		un.big
#define smallsize	un.small.size
#define use		un.small.control

#define INUSE           0x1000
#define USED(x)         (x->use & INUSE)

/* sizes chosen for anticipated QUIPU behaviour */
#define BUCKETS 11
static unsigned sizes [BUCKETS] = { 0, 12, 16, 24, 48, 64, 128, 256, 512, 8191, 0 };

struct freelist {
	struct header * block;
	unsigned int size;
	struct freelist * next;
	struct freelist * prev;
};

struct freehead {
	struct header	head;
	struct freelist * flist;
};

static struct freelist  heaps[MAXHEAP][BUCKETS];
static struct freelist *heapptr[MAXHEAP];
static struct freelist  bigmem = { 0,0,&bigmem, &bigmem};
static struct freelist  *bigfree = &bigmem;
static struct freelist  freemem = { 0,0,&freemem, &freemem};
static struct freelist  *listfree = &freemem;

static int first_malloc = 1;
static char * top_mem;

#ifdef	BSD42
static int pagesize = 0x2000;
#endif

extern caddr_t sbrk();

#ifdef MALLOCTRACE
static int malloc_started = 0;
static char * malloc_fname = (char *)0;
#endif

#ifndef MALLOCTRACE
/* ARGSUSED */
#endif

#endif

start_malloc_trace(f)
char * f;
{
#ifdef MALLOCTRACE
char * env, *getenv ();

	if (((env = getenv ("TRACE_MEMORY")) == (char *)0) || (*env == 0))
		return;

	if (! malloc_started) {
		if (f == (char *)0)
			malloc_fname = "memory.out";
		else
			malloc_fname = f;
		malloc_file = creat (malloc_fname,0644);
		malloc_started = 1;
	} else {
		malloc_file = open (malloc_fname,1);
		(void) lseek (malloc_file,0l,2);
	}
#else
	malloc_file = 0;
#endif
}

stop_malloc_trace ()
{
#ifdef MALLOCTRACE
	if (malloc_file)
		(void) close (malloc_file);
#endif
	malloc_file = 0;
}

#ifdef QUIPU_MALLOC
#ifdef MALLOCTRACE

static write_string (p)
char *p;
{
register char *q;

	if (!malloc_file)
		return;

	q = p;
	while (*q++)
		;
	(void) write(malloc_file, p, q-p-1);
}

static write_addr(addr)
char *addr; 
{
char buf[20];
static char hex[] = "0123456789abcdef";
char *ptr;
int x;

	if (!malloc_file)
		return;

	x = (int) addr;

	if (x == 0) {
		(void) write(malloc_file, "0 ",2);
		return;
	}

	ptr = buf;
	while (x > 0)
		*ptr++ = hex[x % 16], x /= 16;
	*ptr = 0;
	
	while (ptr != buf)
		(void) write(malloc_file, --ptr,1);

	(void) write (malloc_file," ",1); 
}

static write_int(x)
unsigned x;
{
char buf[20];
static char dec[] = "0123456789";
char *ptr;

	if (!malloc_file)
		return;

	if (x == 0) {
		(void) write(malloc_file, "0 ",2);
		return;
	}

	ptr = buf;
	while (x > 0)
		*ptr++ = dec[x % 10], x /= 10;

	while (ptr != buf)
		(void) write(malloc_file, --ptr,1);

	(void) write (malloc_file," ",1); 
}

static char * log_realloc (oldlen,newlen,bsize,addr)
unsigned oldlen,newlen,bsize;
char * addr;
{
	write_string ("realloc of "); write_int (oldlen); 
	write_string ("at "); write_addr (addr);
	write_string ("\n");
	write_stack("x");

	write_string ("realloc-to of "); write_int (newlen); 
	write_string ("gets "); write_int (bsize);
	write_string ("at "); write_addr (addr);
	write_string ("\n");
	write_stack("x");
}

static print_free_list (heap)
unsigned heap;
{
int i;
struct freelist * top;
struct freelist * ptr;

	write_string ("free list for heap ");write_int(heap);write_string(":\n");
	for (i=0; i<BUCKETS; i++) {
	   top = &heaps[heap][i];
	   write_int (sizes[i]); write_string (": ");
	   for (ptr = top->next ; ptr != top; ptr=ptr->next) 
		write_int (ptr->size);
	   write_string ("\n");
	}
}

#ifdef MALLOCSTACK

/* ever so slightly machine dependant !!! */

static write_stack (x)
char * x;
{

struct	stackframe {
	struct stackframe	*next;
	char			*addr;
} * frame;

	for (frame = ((struct stackframe *)(&x-2))->next ; frame; frame = frame->next) {
		write_string ("C ");
		write_addr ((char *)frame->addr);
		write_string ("\n");
	}
	write_string ("\n");

}
#endif 
#endif 


static return_freelist (next)
struct freelist *next;
{
	next->next = listfree->next;
	next->prev = listfree;
	listfree->next->prev = next;
	listfree->next = next;
}

static struct freelist * new_freelist ()
{
struct freelist * flist;

	flist = listfree->next;

	if (flist == listfree) {
		int i;
		struct freelist * next;
		/* go and get some more */
		if ((flist = (struct freelist *) sbrk (PAGESIZE)) == (struct freelist *)0) {
			/* there are 100s of places where Quipu would choke on a naff malloc */
			attempt_restart (-2);
			return ((struct freelist *)0);
		}
		top_mem = (char *)flist + PAGESIZE;
		next = (struct freelist *)flist;
		next++;
		for (i=sizeof (struct freelist); i< PAGESIZE ; i+=sizeof (struct freelist)) 
			return_freelist (next++);
	} else {
		flist->prev->next = flist->next;
		flist->next->prev = flist->prev;
	}

	return (flist);
}


static char * big_malloc (realsize)
			/* used for mallocs of > MAXSMALL */
unsigned realsize;
{
unsigned blocksize;
struct freelist * flist;
struct header * head = (struct header *)0;
char * mem;

	for (flist = bigfree->next; flist != bigfree; flist=flist->next) {
		if (flist->size >= realsize) {
			head = flist->block;
			flist->prev->next = flist->next;
			flist->next->prev = flist->prev;
			return_freelist (flist);
			break;
		}
	}

	if (head == (struct header *)0) {
		/* go and get on then !!! */
		blocksize = PAGEALIGN(realsize);
		if ((head = (struct header *) sbrk ((int)blocksize)) == (struct header *)0) {
			/* there are 100s of places where Quipu would choke on a naff malloc */
			attempt_restart (-2);
			return ((char *)0);
		}
		top_mem = (char *)head + blocksize;
		head->bigsize = blocksize | 0x01;
	} else
		head->bigsize |= 0x01;

	mem = (char *) head + ALIGN(sizeof (struct header));

#ifdef MALLOCTRACE
	write_string ("gets "); write_int (head->bigsize);
	write_string ("at "); write_addr (mem);
	write_string ("\n");
	write_stack("x");
#endif

	return (mem);

}

static big_free (ptr)
struct header *ptr;
{
struct freelist *next;
struct freehead *x;

	if ((next = new_freelist ()) == (struct freelist *)0)
		return;
	next->size=ptr->bigsize;
	next->block = ptr;
	ptr->bigsize &= ~1;
	next->next = bigfree->next;
	next->prev = bigfree;
	bigfree->next->prev = next;
	bigfree->next = next;

	x = (struct freehead *) ptr;
	x->flist = next;
}

static which_list (size)
register unsigned size;
{
register unsigned * p;

	p = sizes;
	p [BUCKETS -1] = size;		/* force stop to while loop */
	
	while ( size > *p++ )
		;

	return ( (p-1) - sizes);
}

static add_free (x)
struct header * x;
{
struct freelist *next, *c;
struct freehead *ptr;

	x->use &= ~INUSE;

	if ((c = heapptr[x->use]) == (struct freelist *) 0)
		c = heapptr[x->use] = heaps[x->use];

	c = &c[which_list(x->smallsize)];

	if ((next = new_freelist ()) == (struct freelist *)0)
		return;
	next->size=x->smallsize;
	next->block = x;
	next->next = c->next;
	next->prev = c;
	c->next->prev = next;
	c->next = next;

	ptr = (struct freehead *) x;
	ptr->flist = next;
}

static remove_free (a)
register struct freelist * a;
{
	a->block->use |= INUSE;
	a->prev->next = a->next;
	a->next->prev = a->prev;
	return_freelist(a);
}

static struct header * next_free_block (ptr)
register struct header * ptr;
{
register struct header * next;

	next = (struct header *)((char *)ptr + ptr->smallsize);
	if (PAGEALIGN((int)ptr) != PAGEALIGN((int)next + 1))
		return (struct header *)0;
	if (((char *)next < top_mem) && (next->use == (ptr->use & ~INUSE)))
		return (next);

	return (struct header *)0;

}

static struct header * find_block (size)
unsigned size;
{
register struct freelist * top;
register struct freelist * ptr;
register int i;
#ifdef BESTFIT
struct freelist * best = (struct freelist *)0;
#endif

	if ((top = heapptr[mem_heap]) == (struct freelist *)0)
		return ((struct header *) 0);

	top = &top[i = which_list (size)];

	for (; i < BUCKETS ; i++,top++ ) {
	   for (ptr = top->next ; ptr != top; ptr=ptr->next) {
		if (ptr->size >= size) {
#ifdef BESTFIT
			if (ptr->size == size) {
				remove_free (ptr);
				return (&(ptr->block));
			}
			if ( (best == (struct freelist *)0) 
				|| (ptr->size < best->size)) 
					best = ptr;
			
#else
			remove_free (ptr);
			return (ptr->block);
#endif
		}
	   }

#ifdef BESTFIT
	   if (best != (struct freelist *)0) {
		remove_free (best);
		return (&(best->block));
	   }
#endif
	}
	return (struct header *)0;
}

static use_block (ptr,size)
register struct header *ptr;
register unsigned size;
{
register struct header *next;

	if ((ptr->smallsize == size) || (ptr->smallsize < size + sizeof (struct freehead)))
		return;  /* don't split it -> left with block too small for use */	

	next = (struct header *)((char *)ptr + size);
	next->smallsize = ptr->smallsize - size;
	next->use = ptr->use & ~INUSE;

	ptr->smallsize = size;
	ptr->use |= INUSE;

	add_free (next);
}

char * malloc (size)
register unsigned size;
{
char * mem;
struct header *head;
register unsigned realsize, blocksize;

#ifdef	BSD42
	if (first_malloc)
	    pagesize = getpagesize ();
#endif

	if (mem_heap >= MAXHEAP)
		mem_heap = MAXHEAP - 1;

	if (size < sizeof (struct freelist *))	/* memory will be used when freed for freelist !!! */
		realsize = ALIGN (sizeof (struct freehead));
	else
		realsize = ALIGN (size) + ALIGN (sizeof (struct header));

	if (realsize >= SMALLMAX) {
#ifdef MALLOCTRACE
		write_string ("malloc of "); write_int (size); 
#endif
		return (big_malloc (realsize));
	}

	if (first_malloc) {
		/* set up freelist */
		unsigned x;
		int i,j;

		for (i = 0; i < MAXHEAP; i++) {
				heapptr[i] = (struct freelist *) 0;
			for (j = 0 ; j<BUCKETS; j++) {
				heaps[i][j].prev = &heaps[i][j];
				heaps[i][j].next = &heaps[i][j];
				heaps[i][j].size = 0;
			}
		}

		/* align first sbrk to page boundary */
		x = (unsigned)sbrk(0);
		x = PAGEALIGN (x) - x;
		blocksize = PAGEALIGN(realsize) + x;
		if ((head = (struct header *) sbrk ((int)blocksize)) == (struct header *)0) {
			/* there are 100s of places where Quipu would choke on a naff malloc */
			attempt_restart (-2);
			return ((char *)0);
		}
		head->smallsize = blocksize;
		top_mem = (char *)head + blocksize;
		first_malloc = 0;
		head->use = INUSE | mem_heap;
		use_block (head,realsize);
		
	} else if ((head = find_block (realsize)) == (struct header *)0) {
		blocksize = PAGEALIGN(realsize);
		if ((head = (struct header *) sbrk ((int)blocksize)) == (struct header *)0) {
			/* there are 100s of places where Quipu would choke on a naff malloc */
			attempt_restart (-2);
			return ((char *)0);
		}
		head->smallsize = blocksize;
		top_mem = (char *)head + blocksize;
		head->use = INUSE | mem_heap;
		use_block (head,realsize);
	} else
		use_block (head,realsize);

	mem = (char *) head + ALIGN(sizeof (struct header));

#ifdef MALLOCTRACE
	write_string ("malloc of "); write_int (size); 
	write_string ("gets "); write_int (head->smallsize);
	write_string ("at "); write_addr (mem);
	write_string ("heap ");write_int (mem_heap); 
	write_string ("\n");
	write_stack("x");
#endif

	return (mem);
}

free(s)
char *s;
{
struct header * ptr;
struct header * next;

	ptr = (struct header *) (s - ALIGN (sizeof (struct header)));

	if (ptr->smallsize & 1) {
#ifdef MALLOCTRACE
		write_string ("free of "); write_int (ptr->bigsize); 
		write_string ("at "); write_addr (s); 
		write_string ("heap (big)\n"); 
		write_stack("x");
#endif
		big_free (ptr);
		return;
	}

#ifdef MALLOCTRACE
	write_string ("free of "); write_int (ptr->smallsize); 
	write_string ("at "); write_addr (s); 
	write_string ("heap "); write_int (ptr->use & ~INUSE);
	write_string ("\n");
	write_stack("x");
#endif

	if (! USED(ptr)) {
		LLOG (log_dsap,LLOG_EXCEPTIONS,("freeing problem"));
		return;		/* already freed !!! */
	}
		
	/* join forward free block in loop to catch previous back blocks ! */
	while ((next = next_free_block(ptr)) != (struct header *) 0) {
		ptr->smallsize += next->smallsize;
		remove_free (((struct freehead *)next)->flist);
	}
	add_free (ptr);

	return;

}


char *realloc(s, n)
char *s;
register unsigned n;
{
char * mem;
register unsigned realsize;
struct header * ptr;
struct header * next;

	ptr = (struct header *) (s - ALIGN (sizeof (struct header)));

	if (ptr->smallsize & 1) {
		DLOG (log_dsap,LLOG_DEBUG,("re-alloc of big block"));
#ifdef MALLOCTRACE
		write_stack ("x");
#endif
		goto out;
	}

	if (! USED(ptr)) {
		LLOG (log_dsap,LLOG_EXCEPTIONS,("re-alloc problem"));
#ifdef MALLOCTRACE
		write_stack ("x");
#endif
		goto out;
	}

	realsize = ALIGN (n) + ALIGN (sizeof (struct header));
	if (ptr->smallsize >= realsize) {
#ifdef MALLOCTRACE
		log_realloc (ptr->smallsize,realsize,ptr->smallsize,s);
#endif
		return (s);
	}

	/* see if next block is free */
	if ((next = next_free_block(ptr)) != (struct header *) 0) {
		struct header * top;

		top = next;
		/* join with other free blocks */
		while ((next = next_free_block(top)) != (struct header *) 0) {
			top->smallsize += next->smallsize;
			remove_free (((struct freehead *)next)->flist);
		}
		remove_free (((struct freehead *)top)->flist);

		/* is it big enough ? */
		if (ptr->smallsize + top->smallsize >= realsize) {
#ifdef MALLOCTRACE
			unsigned savesize;
			savesize = ptr->smallsize;
#endif

			ptr->smallsize += top->smallsize;
			use_block (ptr,realsize);
#ifdef MALLOCTRACE
			log_realloc (savesize,realsize,ptr->smallsize,s);
#endif
			return (s);
		} else 
			/* return to free list */
			add_free (top);
	}

out:;
	if ((mem = malloc (n)) == (char *)0)
		return ((char *)0);
	bcopy (s,mem,(int)n);
	free (s);

	return (mem);
}

char *calloc(n, size)
unsigned n, size;
{
char * mem;
unsigned x;

	x= n*size;
	if ((mem = malloc (x)) == (char *)0)
		return ((char *)0);
        bzero (mem,(int)x);
        return (mem);
}

void
cfree(mem)
char *  mem;
{
        free(mem);
}

#endif
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦3ead6b4f0⟧ TextFile

Derivation

TextFile
