/*
 *  To measure the speed of malloc - based on the algorithm described in
 *  "In Search of a Better Malloc" by David G. Korn and Kiem-Phong Vo,
 *  Usenix 1985. This is a vicious test of memory allocation, but does
 *  suffer from the problem that it asks for a uniform distribution of
 *  sizes - a more accurate distribution is a multi-normal distribution
 *  for all applications I've seen.
 */
/* Mark Moraes, CSRI, University of Toronto */
#ifndef lint
static char rcsid[] = "$Header: /j/moraes/shmem/malloc/malloc/RCS/simumalloc.c,v 1.5 89/10/31 01:52:15 moraes Exp $";
#endif /*lint*/

#include <stdio.h>
#include <string.h>
/* Has MIN and MAX, and MAXHOSTNAMELEN and MAXPATHLEN */
#include <sys/param.h>
/* All sorts of fun numbers like MAXINT, MAXFLOAT etc. */
#include <values.h>
#include "malloc.h"

char *progname;
/* For getopt() */
extern int optind;
extern char *optarg;

extern int fprintf();
extern void exit();
extern int write();
extern int getopt();
extern int sprintf();

int MaxTime, MaxLife, MaxSize, NumAllocs;

typedef union u {
		union u *ptr;
		int size;
} word;

#define MAXTIME 100000
static word *bufs[MAXTIME];

int alloced = 0;
static int maxalloced = 0;

extern long random();
#define rnd(x) (random() % (long) (x))

/*
 *  generally sprintf() to errstring and then call complain rather than
 *  use a varargs routine
 */
char errstring[128];

/*
 *  Should probably have a more fancy version that does perror as well
 *  in a library someplace - like error()
 */
void
complain(s)
char *s;
{
	(void) fprintf(stderr, "%s: %s\n", progname, s);
	exit(-1);
}

void
usage()
{
	(void) fprintf(stderr, "\
Usage: %s [-t MaxTime] [-s MaxSize] [-l MaxLife] [-d]\n", progname);
	exit(-1);
}

int
main(argc, argv)
int argc;
char **argv;
{
	int c;
	register int t;
	char *before, *after;
	extern char *sbrk();
	extern int atoi();
	extern void freeall(), reserve();
	int grew;
	int alloconly = 0;

	if ((progname = strrchr(argv[0], '/')) == NULL)
		progname = argv[0];
	else
		progname++;

	NumAllocs = 1;
	MaxTime = 15000;
	MaxSize = 500;
	MaxLife = 1000;
	while((c = getopt(argc, argv, "n:t:s:l:da")) != EOF) {
		/* optarg has the current argument if the option was followed by ':'*/
		switch (c) {
		case 't':
			MaxTime = atoi(optarg);
			if (MaxTime < 0 || MaxTime > MAXTIME) {
				(void) fprintf(errstring,
				 "%s: MaxTime must be >  0 and < %d\n", progname, MAXTIME);
				exit(-1);
			}
			break;
		case 's':
			MaxSize = atoi(optarg);
			if (MaxSize < 1)
				complain("MaxSize must be > 0");
			break;
		case 'l':
			MaxLife = atoi(optarg);
			if (MaxLife < 0)
				complain("MaxLife must be > 0");
			break;
		case 'n':
			NumAllocs = atoi(optarg);
			if (NumAllocs <= 0)
				complain("NumAllocs must be > 0");
			break;
		case 'd':
			/* Full heap debugging - S-L-O-W */
#ifdef MYMALLOC
			mal_debug(3);
#endif
			break;
		case 'a':
			/* Only allocate -- no free */
			alloconly = 1;
			break;
		case '?':
			usage();
			break;
		}
	}
	/* Any filenames etc. after all the options */
	if (optind < argc) {
		usage();
	}

	for(t = 0; t < MaxTime; t++)
		bufs[t] = 0;
		
	before = sbrk(0);
	for(t = 0; t < MaxTime; t++) {
		register int n;

		for(n = rnd(NumAllocs) + 1; n > 0; n--) {
				int s, l;
				
				s = rnd(MaxSize) + 2;
				l = rnd(MaxLife) + 1;
				reserve(s, t + l);
		}
		if (! alloconly)
			freeall(t);
	}
	after = sbrk(0);
	grew = after - before;
	(void) sprintf(errstring, "Sbrked %d,  MaxAlloced %d, Wastage %.2lf\n",
	 grew, maxalloced * sizeof(word),
	 grew == 0 ? (double) 0.0 : (double) (1.0 -
	 ((double) maxalloced * sizeof(word)) / ((double) grew)));
	(void) write(1, errstring, strlen(errstring));
#ifdef MYMALLOC
	(void) mal_statsdump(stderr);
#endif
	return 0;
}

/*
 *  Mallocs a block s words long, and adds it to the list of blocks to
 *  be freed at time tfree
 */
void
reserve(s, tfree)
int s;
int tfree;
{
		word *wp;

		wp = (word *) malloc(s * sizeof(word));
		if (wp == NULL)
			complain("Out of memory");
		wp[0].ptr = bufs[tfree];
		wp[1].size = s;
		bufs[tfree] = wp;
		alloced += s;
		if (alloced > maxalloced) maxalloced = alloced;
}

/* free all blocks whose lifetime expires at time t */
void
freeall(t)
int t;
{
		word *wp;

		wp = bufs[t];
		while(wp != NULL) {
				word *tmp = wp[0].ptr;
				alloced -= wp[1].size;
				free((char *) wp);
				wp = tmp;
		}
}
