#ifndef lint
static char sccsid[] = "@(#)qalloc.c 9.10 88/01/19 Copyright 1985 Sun Micro";
#endif

/*
 * Copyright (c) 1985 by Sun Microsystems, Inc. 
 */

/*-
	Quick memory allocation/deallocation

	qalloc.c, Wed Jul 31 09:04:27 1985


 */

#include <stdio.h>
#ifdef REF
#include <sys/types.h>
#include <ref/config.h>
#endif
#include "qalloc.h"

int         QuickAllocs,
            FastAllocs,
            SlowAllocs,
            QuickFrees,
            SlowFrees,
            SpaceAllocated,
            PoolsCreated,
            QVMavail,
            QVMused,
            QLGused,
            VMbreak,
            SpaceLost;

struct QuickFreeblock *QuickBuckets[NBuckets];

double *memory_pad;

/* Low/Out memory detection "constants" */
#define PADSIZE 250000		/* ~ 5"x 4"x 8pixels @ 72 pix/in */
#define	STDERRFD	2
static	char *low_msg = "NeWS: low on memory\n";
#define LOW_MSG_LENGTH	20
static	char *out_msg = "NeWS: out of memory\n";
#define OUT_MSG_LENGTH	20

#if QLOGFLAG
static FILE *qlogfile;
static new_object;
#endif

char *
snoopalloc(fname, nbytes)
int nbytes;
char *fname;
{
	double *retval;
	if (!memory_pad)
		memory_pad = (double *)malloc(PADSIZE);
	retval = (double *)malloc(nbytes);
	if (retval)
		return (char *)retval;
	else {
		if (memory_pad) {
			free(memory_pad);
			memory_pad = 0;
			retval = (double *)malloc(nbytes);
			if (retval) {
    				write(STDERRFD, low_msg, LOW_MSG_LENGTH);
				return (char *)retval;
			} else
				malloc_failure(fname);
		} else
			malloc_failure(fname);
	}
	/* NOT REACHED */
} /* snoopalloc */

char *
snoopcalloc(fname, nelem, elsize)
int nelem, elsize;
char *fname;
{
	double *retval;
	if (!memory_pad)
		memory_pad = (double *)malloc(PADSIZE);
	retval = (double *)calloc(nelem, elsize);
	if (retval)
		return (char *)retval;
	else {
		if (memory_pad) {
			free(memory_pad);
			memory_pad = 0;
			retval = (double *)calloc(nelem, elsize);
			if (retval) {
    				write(STDERRFD, low_msg, LOW_MSG_LENGTH);
				return (char *)retval;
			} else
				malloc_failure(fname);
		} else
			malloc_failure(fname);
	}
	/* NOT REACHED */
} /* snoopcalloc */

char *
softcalloc(fname, nelem, elsize)
int nelem, elsize;
char *fname;
{
	double *retval;
	if (!memory_pad)
		memory_pad = (double *)malloc(PADSIZE);
	retval = (double *)calloc(nelem, elsize);
	if (retval)
		return (char *)retval;
	else {
		if (memory_pad) {
			free(memory_pad);
			memory_pad = 0;
			retval = (double *)calloc(nelem, elsize);
			if (retval) {
    				write(STDERRFD, low_msg, LOW_MSG_LENGTH);
				return (char *)retval;
			} else {
				soft_malloc_failure(fname);
				return 0;
			}
		} else { /* no pad */
			soft_malloc_failure(fname);
			return 0;
		}
	}
	/* NOT REACHED */
} /* softcalloc */

char *
snooprealloc(fname, ptr, nbytes)
double *ptr;	/* longest possible alignment */
int nbytes;
char *fname;
{
	double *retval;
	if (!memory_pad)
		memory_pad = (double *)malloc(PADSIZE);
	retval = (double *)realloc(ptr, nbytes);
	if (retval)
		return (char *)retval;
	else {
		if (memory_pad) {
			free(memory_pad);
			memory_pad = 0;
			retval = (double *)realloc(ptr, nbytes);
			if (retval) {
    				write(STDERRFD, low_msg, LOW_MSG_LENGTH);
				return (char *)retval;
			} else {
				soft_malloc_failure(fname);
				return 0;
			}
		} else /* no pad */
			malloc_failure(fname);
	}
	/* NOT REACHED */
} /* snooprealloc */

malloc_failure(s)
    char       *s;
{
    register i;
    int	dtfdmax = getdtablesize();

    /*
     * Close all connections in an attempt to terminate the console window
     * (if any).  Wait a bit for the termination to actually take place.
     * Then write the message, which will then go to the default console.
     * Without doing this, the message gets sent to a console that never
     * gets a chance to display it, because it is a window that is going away.
     */
    for (i = 0; i < dtfdmax; i++)
	if (i != STDERRFD)
	    close(i);
    sleep(3);
    write(STDERRFD, out_msg, OUT_MSG_LENGTH);
    abort(0);
    /* NOT REACHED */
}

/* 'soft' failure - just print message and return. */
soft_malloc_failure(s)
    char       *s;
{
    write(STDERRFD, out_msg, OUT_MSG_LENGTH);
}

struct poolblock {
    char       *where;
    int         size;
};

#define poolsize 3
static struct poolblock pool[poolsize];

char       *
qalloc(s)			/* returns a block of size s */
    register    s;
{
    register struct QuickFreeblock **QuickFreeblock;
#if QLOGFLAG
    new_object = 1;
#endif
    if (s > LargestBucketedChunk) {
	register char *ret;
	IFVMSTAT(SlowAllocs++;QLGused+=(s+3)&~3);
#ifdef MallocPreceedsBlockWithSize
	ret = (char *) snoopalloc("qalloc.c", s);
	return ret;
#else
	ret = (char *) snoopalloc("qalloc.c", s + QUICKMINUSOFFSET);
	*(int *)ret = s;
	return ret + QUICKMINUSOFFSET;
#endif
    }
    else if (*(QuickFreeblock = &QuickSlot(s)) == 0) {
	/*
	 * The bucket for this block size is empty, so we need to find a
	 * free space pool that we can grab a virgin one from 
	 */
	register struct poolblock *p;
	register    i;
	if (QAllocStatistics)
	    FastAllocs++;
	if (s == 0) {
#ifdef DEBUG
	    abort(0);	/* Shouldn't happen! */
#endif
	    s++;
	}
	if (s > LargeBucketThreshhold)
	    s = (s + BytesPerLargeBucket - 1) & ~((1 << LogBytesPerLargeBucket) - 1);
	else
	    s = (s + BytesPerBucket - 1) & ~((1 << LogBytesPerBucket) - 1);

	s += QUICKMINUSOFFSET;

	/* find the first pool with enough space */
	for (p = pool, i = poolsize; --i >= 0; p++)
	    if (p->size >= s) {
		register struct QuickFreeblock *ret;
	returnit:		/* we have some space... */
		ret = (struct QuickFreeblock *) p->where;
		p->size -= s;
		p->where += s;

		ret->size = s - QUICKMINUSOFFSET;

		IFVMSTAT(QVMused += ret->size);
		return (char *) &ret->next;
	    }
	/*
	 * no pool has enough space: through away the smallest pool and
	 * allocate some space for it 
	 */
	{
	    register struct poolblock *best = &pool[0];
	    for (p = &pool[1], i = poolsize; --i > 0; p++)
		if (best->size > p->size)
		    best = p;
	    p = best;
#ifdef undef
	    while (p->size >= LargeBucketThreshhold + sizeof(int)) {
		register    rsize = (p->size - sizeof(int)) & ~(BytesPerLargeBucket - 1);
		p->size -= rsize + sizeof(int);
		((struct QuickFreeblock *) p->where)->size = rsize;
		QSFREE(&((struct QuickFreeblock *) p->where)->next, rsize);
		p->where += rsize + sizeof(int);
	    }
	    while (p->size >= BytesPerBucket + sizeof(int)) {
		register    rsize = (p->size - sizeof(int)) & ~(BytesPerBucket - 1);
		p->size -= rsize + sizeof(int);
		((struct QuickFreeblock *) p->where)->size = rsize;
		QSFREE(&((struct QuickFreeblock *) p->where)->next, rsize);
		p->where += rsize + sizeof(int);
	    }
#endif
	    IFVMSTAT(PoolsCreated++; SpaceLost += p->size);
	    p->size = 8 * 1024 + s;
	    p->where = (char *) snoopalloc("qalloc.c", p->size);
#if QLOGFLAG
	    if (qlogfile)
		fprintf(qlogfile, "%10x %12d New pool\n", p->where, p->size);
#endif
	    IFVMSTAT(QVMavail += p->size);
	    goto returnit;
	}
    }
    else {			/* Take the block from a bucket */
	register char *ret;
	ret = (char *) &(*QuickFreeblock)->next;
	IFVMSTAT(QuickAllocs++; QVMused += (*QuickFreeblock)->size);
	*QuickFreeblock = (*QuickFreeblock)->next;
	return ret;
    }
}

qfree(p)
    register char *p;
{
    QFREE(p);
}

PrintQAllocStatistics()
{
    fprintf(stderr, "%10d quick allocs\n%10d fast allocs\n%10d slow allocs\n\
%10d quick frees\n%10d slow frees\n%10d pools created\n%10d space lost\n",
	    QuickAllocs, FastAllocs, SlowAllocs, QuickFrees, SlowFrees, PoolsCreated, SpaceLost);
}

AllocCorruption(n)
{
    fprintf(stderr, "Alloc corruption(%d)\n", n);
    abort(0);
}

qalloc_check()
{
}

#if QLOGFLAG
#if 1
/*-
	Analyse an allocation log for core leaks.

	analyse.c, Wed Feb 26 10:30:44 1986


 */

struct logentry {
    struct logentry *left, *right;
    int         addr;
    int		hash;
    int         size;
    int         line;
    int         sequence;
    int		invisible;
    short       timesused;
    char        file[30];
    char        cast[30];
    char        alloced;
};

static struct logentry *logroot;
static int qal_sequence;

static
unsigned char ReverseBitsInByte[256] =
{
 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0, 0x10, 0x90, 0x50, 0xd0,
 0x30, 0xb0, 0x70, 0xf0, 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8, 0x04, 0x84, 0x44, 0xc4,
 0x24, 0xa4, 0x64, 0xe4, 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec, 0x1c, 0x9c, 0x5c, 0xdc,
 0x3c, 0xbc, 0x7c, 0xfc, 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2, 0x0a, 0x8a, 0x4a, 0xca,
 0x2a, 0xaa, 0x6a, 0xea, 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6, 0x16, 0x96, 0x56, 0xd6,
 0x36, 0xb6, 0x76, 0xf6, 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe, 0x01, 0x81, 0x41, 0xc1,
 0x21, 0xa1, 0x61, 0xe1, 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9, 0x19, 0x99, 0x59, 0xd9,
 0x39, 0xb9, 0x79, 0xf9, 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5, 0x0d, 0x8d, 0x4d, 0xcd,
 0x2d, 0xad, 0x6d, 0xed, 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3, 0x13, 0x93, 0x53, 0xd3,
 0x33, 0xb3, 0x73, 0xf3, 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb, 0x07, 0x87, 0x47, 0xc7,
 0x27, 0xa7, 0x67, 0xe7, 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef, 0x1f, 0x9f, 0x5f, 0xdf,
 0x3f, 0xbf, 0x7f, 0xff,
};

qal_validate_free_entry(fp)
    register struct QuickFreeblock *fp;
{
    while (fp) {
	register struct logentry *p,
	          **pp;
	register    hash = (ReverseBitsInByte[((((int) fp) + 4) >> 2) & 0xFF] << 24) | ((((int) fp) + 4) >> 8);
	pp = &logroot;
	while (p = *pp) {
	    if (p->hash == hash)
		break;
	    if (hash < p->hash)
		pp = &p->left;
	    else
		pp = &p->right;
	}
	if (p) {
	    if (p->alloced == 'A') {
		qal_error("Allocated block in free list", p, stdout);
		fflush(qlogfile);
		abort(0);
	    }
	}
	else {
	    qal_error("non-block in free list", p, stdout);
	    fflush(qlogfile);
	    abort(0);
	}
	fp = fp->next;
    }
}
qal_validate_alloced_entry(fp)
    register struct QuickFreeblock *fp;
{
    if (fp) {
	register struct logentry *p,
	          **pp;
	register    hash = (ReverseBitsInByte[((((int) fp)) >> 2) & 0xFF] << 24) | ((((int) fp)) >> 8);
	pp = &logroot;
	while (p = *pp) {
	    if (p->hash == hash)
		break;
	    if (hash < p->hash)
		pp = &p->left;
	    else
		pp = &p->right;
	}
	if (p) {
	    if (p->alloced == 'F') {
		qal_error("Using free block", p, stdout);
		fflush(qlogfile);
		abort(0);
	    }
	}
	else {
	    qal_error("non-block in use", p, stdout);
	    fflush(qlogfile);
	    abort(0);
	}
    }
}

qal_log(addr, size, line, file, alloced, cast)
    char       *file, *cast;
{
    register struct logentry *p, **pp;
    struct logentry in;
    extern      end;
    int qal_leakcheck();
    int qal_invisible();
    static qlogsig;

    /* Install signal handler to invoke qal_leakcheck */
    if (!qlogsig) {
	qlogsig = signal(30/*SIGUSR1*/, qal_leakcheck);
	(void) signal(31/*SIGUSR2*/, qal_invisible);
	printf("PID %D\n", getpid());
    }
    in.addr = addr;
    in.hash = (ReverseBitsInByte[(addr>>2)&0xFF]<<24) | (addr>>8);
    in.size = size;
    in.line = line;
    strncpy(in.file, file, sizeof in.file);
    if (cast)
	strncpy(in.cast, cast, sizeof in.cast);
    else
	in.cast[0] = NULL;
    in.alloced = alloced;
    in.sequence = 0;
    in.invisible = 0;
    pp = &logroot;
    if (qlogfile == 0) {
	qlogfile = fopen("allocation_log", "w");
	if (qlogfile == 0) {
	    fprintf(stderr, "Can't open allocation log\n");
	    exit(0);
	}
    }
    {
	static seq;
	fprintf(qlogfile, "%10x %6d %5d %c %s:%d %s\n",
		addr, ++seq, size, alloced, file, line, cast);
    }
    if (size <= 0) {
	qal_error("Block too small: ", &in, stdout);
	if (qlogfile) fflush(qlogfile);
	abort();
    }
    if (addr < (int) &end || addr > (1 << 25)) {
	qal_error("Bogus address: ", &in, stdout);
	if (qlogfile) fflush(qlogfile);
	abort();
    }
    if (size >= (1 << 15)) {
	qal_error("Block too large: ", &in, stdout);
	if (qlogfile) fflush(qlogfile);
	abort();
    }
    while (p = *pp) {
	if (p->hash == in.hash)
	    break;
	if (in.hash < p->hash)
	    pp = &p->left;
	else
	    pp = &p->right;
    }
    if (p) {
	if (new_object && size < LargestBucketedChunk) {
	    qal_error("New object already in tree: ", p, stdout);
	    if (qlogfile) fflush(qlogfile);
	    abort();
	}
	if (p->alloced == 'F')
	    if (alloced == 'F') {
		qal_error("Freeing freed block: ", &in, stdout);
		qal_error("	previously freed by: ", p, stdout);
		if (qlogfile) fflush(qlogfile);
		abort();
	    }
	    else
		p->timesused++;
	else if (alloced == 'A') {
	    qal_error("Duplicate allocation: ", &in, stdout);
	    qal_error("	previously allocated by: ", p, stdout);
	    if (qlogfile) fflush(qlogfile);
	    abort();
	}
	in.left = p->left;
	in.right = p->right;
	in.timesused = p->timesused;
	if (alloced == 'A')
		in.sequence = qal_sequence++;
	*p = in;
    }
    else {
	if (!new_object) {
	    qal_error("new tree entry for old object: ", p, stdout);
	    if (qlogfile) fflush(qlogfile);
	    abort();
	}
	p = (struct logentry *) snoopalloc("qalloc.c", sizeof(struct logentry));
	in.sequence = qal_sequence++;
	*p = in;
	p->left = 0;
	p->right = 0;
	p->timesused = 1;
	if (p->alloced == 'F') {
	    qal_error("Freeing never allocated block: ", p, stdout);
	    if (qlogfile) fflush(qlogfile);
	    abort();
	}
	*pp = p;
    }
#if QLOGFLAG
    new_object = 0;
#endif
}

static maxused;		/* Max size used */
static qlogcount;	/* Number of nodes counted */
static qlogbytes;	/* Number of bytes counted */
#define	HIST_SIZE	11
static hist[HIST_SIZE];

qal_leakcheck()
{   register i;
    FILE *log_temp;
    static log_seq;
    char log_name[50];

    /* Open new log file */
    log_temp = qlogfile;
    sprintf(log_name, "allocation_log%d", log_seq++);
    qlogfile = fopen(log_name, "w");
    if (qlogfile == 0) {
        fprintf(stderr, "Can't open %s\n", log_name);
        exit(0);
    }
    /* Reset statistics */
    maxused = 0;
    qlogcount = 0;
    qlogbytes = 0;
    for (i = 0; i<HIST_SIZE; i++)
	hist[i] = 0;
    /* Collect data */
    do_leakcheck(logroot);
    do_maxused(logroot);
    do_buildhist(logroot);
    /* Display statistics */
    for (i = 0; i<HIST_SIZE; i++)
	printf("%7d",hist[i]);
    printf("   HIST\n");
    for (i = 0; i<HIST_SIZE; i++)
	printf("%7d",i*maxused/10);
    printf("   qlogcount=%D, qlogbytes=%D BOUND\n", qlogcount, qlogbytes);
    PrintQAllocStatistics();
    /* Reset log file */
    fflush(qlogfile);
    fclose(qlogfile);
    qlogfile = NULL;
}

qal_invisible()
{
    do_invisible(logroot, 1);
    return;
}

static
do_invisible(p, invisible)
    register struct logentry *p;
{
    if (p == 0)
	return;
    do_invisible(p->left, invisible);
    p->invisible = invisible;
    do_invisible(p->right, invisible);
    return;
}

static
do_leakcheck(p)
    register struct logentry *p;
{
    if (p == 0)
	return;
    do_leakcheck(p->left);
    if (!p->invisible && p->alloced == 'A')
	qal_error("", p, qlogfile);
    do_leakcheck(p->right);
}


static
do_maxused(p)
    register struct logentry *p;
{
    register a, b;
    if (p == 0) return 0;
    do_maxused(p->left);
    do_maxused(p->right);
    if (!p->invisible) {
	if (p->timesused>maxused) maxused = p->timesused;
	if (p->alloced == 'A') {
	    qlogcount++;
	    qlogbytes += p->size;
	}
    }
}


static
do_buildhist(p)
    register struct logentry *p;
{
    if (p == 0) return 0;
    if (!p->invisible)
	hist[p->timesused*10/maxused]++;
    do_buildhist(p->left);
    do_buildhist(p->right);
}

qal_error(s, p, file)
    char       *s;
    register struct logentry *p;
    FILE *file;
{
    if (p == 0)
	fprintf(file, "%s BOGUS ENTRY\n", s);
    else
	fprintf(file, "%s%10x %6d %5d %c %s:%d %s\n",
		s, p->addr, p->sequence, p->size, p->alloced,
		p->file, p->line, p->cast);
    qal_break();
}

qal_break() {}

qlog_chain_check() {
    qal_validate_free_entry(QuickSlot(82));
}
#else

/* int qlog_bucket = 1; */

qal_log(addr, size, line, file, op, cast)
    char *addr, *file, *cast;
{
    extern char end;
    static seq;
    if (qlogfile == 0) {
	qlogfile = fopen("allocation_log", "w");
	if (qlogfile == 0) {
	    fprintf(stderr, "Can't open allocation log\n");
	    exit(0);
	}
    }
    fprintf(qlogfile, "%10x %6d %5d %c %s:%d %s\n",
	    addr, ++seq, size, op, file, line, cast);
/* XXX Changed size<4 to size<0. Currently doesnt roundup to word boundaries */
    if (op == 'A' || op == 'F')
    if (addr < &end || addr > (char *) (4*1024*1024) || size<0 || size>200*1024)
    {   
	fprintf(stderr, "Allocation screwup in %s@%d\n", file, line);
	fflush(qlogfile);
	abort(0);
    }
    qlog_chain_check();
}

qlog_chain_check() {
    register qlog_bucket;
    for (qlog_bucket = 1; qlog_bucket<25; qlog_bucket++) {
	register struct QuickFreeblock *p = QuickBuckets[qlog_bucket];
	register struct QuickFreeblock *prev = 0;
	register n = 0;
	while (p) {
	    if ((int) p < (int) &end
		|| (int)p>(4*1024*1024)
		|| p->size != qlog_bucket*BytesPerBucket) {
		    fprintf(stderr, "chain screwup at item %d of slot %d; prev=%d\n",
			    n, qlog_bucket, prev);
		    fflush(qlogfile);
		    abort(0);
		}
	    prev = p;
	    p = p->next;
	}
    }
}
#endif
#endif