ex-vi/mapmalloc.c

/*
 * AT&T Unix 7th Edition memory allocation routines.
 *
 * Modified for ex by Gunnar Ritter, Freiburg i. Br., Germany,
 * February 2005.
 *
 * Copyright(C) Caldera International Inc. 2001-2002. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *   Redistributions of source code and documentation must retain the
 *    above copyright notice, this list of conditions and the following
 *    disclaimer.
 *   Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *   All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed or owned by Caldera
 *      International, Inc.
 *   Neither the name of Caldera International, Inc. nor the names of
 *    other contributors may be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA
 * INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE
 * LIABLE FOR ANY DIRECT, INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
 * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *	Sccsid @(#)mapmalloc.c	1.4 (gritter) 2/20/05
 */

#ifdef	VMUNIX

#include <sys/types.h>
#include <unistd.h>
#include <errno.h>
#include <sys/mman.h>

#ifndef	MAP_FAILED
#define	MAP_FAILED	((void *)-1)
#endif	/* !MAP_FAILED */

#ifndef	MAP_ANON
#ifdef	MAP_ANONYMOUS
#define	MAP_ANON	MAP_ANONYMOUS
#else	/* !MAP_ANONYMOUS */
#include <sys/stat.h>
#include <fcntl.h>
#endif	/* !MAP_ANONYMOUS */
#endif	/* !MAP_ANON */

#include "config.h"

/*
 * Since ex makes use of sbrk(), the C library's version of malloc()
 * must be avoided.
 */

/*
#define debug
#define longdebug
*/

#ifdef debug
#define ASSERT(p) if(!(p))botch("p");else
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <inttypes.h>
int 
botch(char *s)
{
	const char msg[] = "assertion botched\n";
	write(2, msg, sizeof msg - 1);
	/*printf("assertion botched: %s\n",s);*/
	abort();
}
static int allock(void *);
#ifdef	debugprint
void dump(const char *msg, uintptr_t t)
{
	const char hex[] = "0123456789ABCDEF";
	int	i;
	write(2, msg, strlen(msg));
	write(2, ": ", 2);
	for (i = sizeof t - 1; i >= 0; i--) {
		write(2, &hex[(t & (0x0f << 8*i+4)) >> 8*i+4], 1);
		write(2, &hex[(t & (0x0f << 8*i)) >> 8*i], 1);
	}
	write(2, "\n", 1);
}
#else
#define	dump(a, b)
#endif
#else
#define ASSERT(p)
#define	dump(a, b)
#endif

/*	avoid break bug */
#ifdef pdp11
#define GRANULE 64
#else
#define GRANULE 0
#endif
/*	C storage allocator
 *	circular first-fit strategy
 *	works with noncontiguous, but monotonically linked, arena
 *	each block is preceded by a ptr to the (pointer of) 
 *	the next following block
 *	blocks are exact number of words long 
 *	aligned to the data type requirements of ALIGN
 *	pointers to blocks must have BUSY bit 0
 *	bit in ptr is 1 for busy, 0 for idle
 *	gaps in arena are merely noted as busy blocks
 *	last block of arena (pointed to by alloct) is empty and
 *	has a pointer to first
 *	idle blocks are coalesced during space search
 *
 *	this variant uses mmap() instead of sbrk()
 *	mmap() is used to allocate pools of increasing size
 *	memory is then allocated from the first possible pool
 *
 *	a different implementation may need to redefine
 *	ALIGN, NALIGN, BLOCK, BUSY, INT
 *	where INT is integer type to which a pointer can be cast
*/
#define	INT		intptr_t
#define	ALIGN		intptr_t
#define	NALIGN		1
#define	WORD		sizeof (union store)
#define	BLOCK		1024	/* a multiple of WORD*/
#define	BUSY		((intptr_t)1)
#ifdef	NULL
#undef	NULL
#endif
#define NULL		 0
#define	testbusy(p)	((INT)(p)&BUSY)
#define	setbusy(p)	(union store *)((INT)(p)|BUSY)
#define	clearbusy(p)	(union store *)((INT)(p)&~BUSY)

static	struct pool *pool0;

union store { union store *ptr;
	      struct pool *pool;
	      ALIGN dummy[NALIGN];
	      INT callocsp;	/*calloc clears an array of integers*/
};

struct pool {
	struct pool *Next;
	union store Allocs[2];	/*initial arena*/
	union store *Allocp;	/*search ptr*/
	union store *Alloct;	/*arena top*/
	union store *Allocx;	/*for benefit of realloc*/
	char *Brk;
	char *End;
	ALIGN Dummy[NALIGN];
};

#define	allocs	(o->Allocs)
#define	allocp	(o->Allocp)
#define	alloct	(o->Alloct)
#define	allocx	(o->Allocx)

static void *
map(void *addr, size_t len)
{
#ifndef	MAP_ANON
	int flags = 0;
	static int fd = -1;

	if (fd==-1 && ((fd=open("/dev/zero",O_RDWR))<0 ||
			fcntl(fd,F_SETFD,FD_CLOEXEC)<0))
		return(MAP_FAILED);
#else	/* MAP_ANON */
	int flags = MAP_ANON;
	int fd = -1;
#endif	/* MAP_ANON */
	flags |= MAP_PRIVATE;
	if (addr)
		flags |= MAP_FIXED;
	return(mmap(addr,len,PROT_READ|PROT_WRITE,flags,fd,0));
}

void *
malloc(size_t nbytes)
{
	register union store *p, *q;
	struct pool *o;
	register int nw;
	static int temp;	/*coroutines assume no auto*/
	static size_t poolblock = 0100000;

	if (nbytes == 0)
		nbytes = 1;
	if(pool0==0 || pool0==MAP_FAILED) {	/*first time*/
		if((pool0=map(NULL, poolblock))==MAP_FAILED) {
			errno = ENOMEM;
			return(NULL);
		}
		pool0->Brk = (char *)pool0->Dummy;
		pool0->End = (char *)pool0+poolblock;
	}
	o = pool0;
first:	if(allocs[0].ptr==0) {	/*first time for this pool*/
		allocs[0].ptr = setbusy(&allocs[1]);
		allocs[1].ptr = setbusy(&allocs[0]);
		alloct = &allocs[1];
		allocp = &allocs[0];
	}
	nw = (nbytes+2*WORD+WORD-1)/WORD;
	ASSERT(allocp>=allocs && allocp<=alloct);
	ASSERT(allock(o));
	for(p=allocp; ; ) {
		for(temp=0; ; ) {
			if(!testbusy(p->ptr)) {
				while(!testbusy((q=p->ptr)->ptr)) {
					int ua = p->ptr==allocp;
					ASSERT(q>p&&q<alloct);
					p->ptr = q->ptr;
					if (ua)
						allocp = p->ptr;
				}
				if(q>=p+nw && p+nw>=p)
					goto found;
			}
			q = p;
			p = clearbusy(p->ptr);
			if(p>q)
				ASSERT(p<=alloct);
			else if(q!=alloct || p!=allocs) {
				ASSERT(q==alloct&&p==allocs);
				errno = ENOMEM;
				return(NULL);
			} else if(++temp>1)
				break;
		}
		temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
		q = (void *)o->Brk;
		if(q+temp+GRANULE < q) {
			errno = ENOMEM;
			return(NULL);
		}
		if(o->Brk+temp*WORD>=o->End) {
			size_t new;
			if(o->Next!=0&&o->Next!=MAP_FAILED) {
				o = o->Next;
				goto first;
			}
			poolblock += poolblock/(poolblock&(poolblock-1) ? 3:2);
			new = (((nw*WORD)+poolblock)/poolblock)*poolblock;
			if ((o->Next=map(0,new))==MAP_FAILED) {
				poolblock /= 4;
				new=(((nw*WORD)+poolblock)/poolblock)*poolblock;
				if ((o->Next=map(0,new))==MAP_FAILED) {
					errno = ENOMEM;
					return(NULL);
				}
			}
			o = o->Next;
			o->Brk = (char *)o->Dummy;
			o->End = (char *)o + new;
			goto first;
		}
		o->Brk += temp*WORD;
		ASSERT(q>alloct);
		alloct->ptr = q;
		if(q!=alloct+1)
			alloct->ptr = setbusy(alloct->ptr);
		alloct = q->ptr = q+temp-1;
		alloct->ptr = setbusy(allocs);
	}
found:
	allocp = p + nw;
	ASSERT(allocp<=alloct);
	if(q>allocp) {
		allocx = allocp->ptr;
		allocp->ptr = p->ptr;
	}
	p->ptr = setbusy(allocp);
	p[1].pool = o;
	dump("malloc", (uintptr_t)(p + 2));
	return(p+2);
}

/*	freeing strategy tuned for LIFO allocation
*/
void 
free(register void *ap)
{
	register union store *p = ap;
	struct pool *o;

	dump("  free", (uintptr_t)ap);
	if (ap == NULL)
		return;
	o = p[-1].pool;
	ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
	ASSERT(allock(o));
	allocp = p -= 2;
	ASSERT(testbusy(p->ptr));
	p->ptr = clearbusy(p->ptr);
	ASSERT(p->ptr > allocp && p->ptr <= alloct);
}

/*	realloc(p, nbytes) reallocates a block obtained from malloc()
 *	and freed since last call of malloc()
 *	to have new size nbytes, and old content
 *	returns new location, or 0 on failure
*/

void *
realloc(void *ap, size_t nbytes)
{
	register union store *p = ap;
	register union store *q;
	struct pool *o;
	union store *s, *t;
	register size_t nw;
	size_t onw;

	if (p==NULL)
		return(malloc(nbytes));
	if (nbytes==0) {
		free(p);
		return NULL;
	}
	if(testbusy(p[-2].ptr))
		free(p);
	onw = p[-2].ptr - p;
	o = p[-1].pool;
	q = malloc(nbytes);
	if(q==NULL || q==p)
		return(q);
	s = p;
	t = q;
	nw = (nbytes+WORD-1)/WORD;
	if(nw<onw)
		onw = nw;
	while(onw--!=0)
		*t++ = *s++;
	if(q<p && q+nw>=p && p[-1].pool==q[-1].pool)
		(q+(q+nw-p))->ptr = allocx;
	return(q);
}

#ifdef debug
int 
allock(void *ao)
{
#ifdef longdebug
	struct pool *o = ao;
	register union store *p;
	int x;
	x = 0;
	for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
		if(p==allocp)
			x++;
	}
	ASSERT(p==alloct);
	ASSERT(x==1|p==allocp);
#endif
	return(1);
}
#endif

/*	calloc - allocate and clear memory block
*/
#define CHARPERINT (sizeof(INT)/sizeof(char))

void *
calloc(size_t num, size_t size)
{
	register char *mp;
	register INT *q;
	register int m;

	num *= size;
	mp = malloc(num);
	if(mp==NULL)
		return(NULL);
	q = (INT *) mp;
	m = (num+CHARPERINT-1)/CHARPERINT;
	while(--m >= 0)
		*q++ = 0;
	return(mp);
}

#ifdef	notdef
/*ARGSUSED*/
void 
cfree(char *p, size_t num, size_t size)
{
	free(p);
}

/*
 * Just in case ...
 */
char *
memalign(size_t alignment, size_t size)
{
	return NULL;
}

char *
valloc(size_t size)
{
	return NULL;
}

char *
mallinfo(void)
{
	return NULL;
}

int 
mallopt(void)
{
	return -1;
}
#endif	/* notdef */

char *poolsbrk(intptr_t val) { return NULL; }

#endif	/* VMUNIX */