misc.c

这是个trace drive的Cache模拟器

/*
 * Miscellaneous functions for Dinero IV.
 * Written by Jan Edler and Mark D. Hill
 * 
 * Copyright (C) 1997 NEC Research Institute, Inc. and Mark D. Hill.
 * All rights reserved.
 * Copyright (C) 1985, 1989 Mark D. Hill.  All rights reserved.
 * 
 * Permission to use, copy, modify, and distribute this software and
 * its associated documentation for non-commercial purposes is hereby
 * granted (for commercial purposes see below), provided that the above
 * copyright notice appears in all copies, derivative works or modified
 * versions of the software and any portions thereof, and that both the
 * copyright notice and this permission notice appear in the documentation.
 * NEC Research Institute Inc. and Mark D. Hill shall be given a copy of
 * any such derivative work or modified version of the software and NEC
 * Research Institute Inc.  and any of its affiliated companies (collectively
 * referred to as NECI) and Mark D. Hill shall be granted permission to use,
 * copy, modify, and distribute the software for internal use and research.
 * The name of NEC Research Institute Inc. and its affiliated companies
 * shall not be used in advertising or publicity related to the distribution
 * of the software, without the prior written consent of NECI.  All copies,
 * derivative works, or modified versions of the software shall be exported
 * or reexported in accordance with applicable laws and regulations relating
 * to export control.  This software is experimental.  NECI and Mark D. Hill
 * make no representations regarding the suitability of this software for
 * any purpose and neither NECI nor Mark D. Hill will support the software.
 * 
 * Use of this software for commercial purposes is also possible, but only
 * if, in addition to the above requirements for non-commercial use, written
 * permission for such use is obtained by the commercial user from NECI or
 * Mark D. Hill prior to the fabrication and distribution of the software.
 * 
 * THE SOFTWARE IS PROVIDED AS IS.  NECI AND MARK D. HILL DO NOT MAKE
 * ANY WARRANTEES EITHER EXPRESS OR IMPLIED WITH REGARD TO THE SOFTWARE.
 * NECI AND MARK D. HILL ALSO DISCLAIM ANY WARRANTY THAT THE SOFTWARE IS
 * FREE OF INFRINGEMENT OF ANY INTELLECTUAL PROPERTY RIGHTS OF OTHERS.
 * NO OTHER LICENSE EXPRESS OR IMPLIED IS HEREBY GRANTED.  NECI AND MARK
 * D. HILL SHALL NOT BE LIABLE FOR ANY DAMAGES, INCLUDING GENERAL, SPECIAL,
 * INCIDENTAL, OR CONSEQUENTIAL DAMAGES, ARISING OUT OF THE USE OR INABILITY
 * TO USE THE SOFTWARE.
 *
 * $Header: /home/edler/dinero/d4/RCS/misc.c,v 1.7 1997/12/11 08:07:58 edler Exp $
 */

#include <stddef.h>
#include <stdlib.h>
#include <limits.h>
#include <stdio.h>
#include <assert.h>
#include "d4.h"


/*
 * Global variable definitions
 */
struct d4_stackhash_struct d4stackhash;
d4stacknode d4freelist;
int d4nnodes;
d4pendstack *d4pendfree;
d4cache *d4_allcaches;


/*
 * Private prototypes for this file
 */
extern void d4_invblock (d4cache *, int stacknum, d4stacknode *);
extern void d4_invinfcache (d4cache *, const d4memref *);


/*
 * Create a new cache
 * The new cache sits "above" the indicated larger cache in the
 * memory hierarchy, with memory at the bottom and processors at the top.
 */
d4cache *
d4new (d4cache *larger)
{
	static int nextcacheid = 1;
	d4cache *c = calloc (1, sizeof(d4cache));

	if (c == NULL)
		return NULL;
	c->cacheid = nextcacheid++;
	c->downstream = larger;
	c->ref = d4ref;	/* may get altered for custom version */
	if (larger == NULL) {	/* simulated memory */
		c->flags = D4F_MEM;
		c->assoc = 1;	/* not used, but helps avoid compiler warnings */
	}
	c->link = d4_allcaches;
	d4_allcaches = c;	/* d4customize depends on this LIFO order */
	return c;
}


/*
 * Check all caches, set up internal data structures.
 * Must be called exactly once, after all calls to d4new
 * and all necessary direct initialization of d4cache structures.
 * The call to d4setup must occur before any calls to d4ref.
 * The return value is zero for success.
 */
int
d4setup()
{
	int i, nnodes;
	int r = 0;
	d4cache *c, *cc;
	d4stacknode *nodes = NULL, *ptr;

	for (c = d4_allcaches;  c != NULL;  c = c->link) {

		/* Check some stuff the user shouldn't muck with */
		if (c->stack != NULL || c->pending != NULL ||
		    c->cacheid < 1 ||
		    (c->link == NULL && c->cacheid != 1) ||
		    (c->flags != D4F_MEM && c->downstream == NULL) ||
		    c->numsets != 0 ||
		    c->ranges != NULL || c->nranges != 0 || c->maxranges != 0)
			goto fail1;

		/*
		 * If customization has been done,
		 * check that the same values have been set in the d4cache structure.
		 * NOTE: The order of the checks here
		 * must match the code in d4customize.
		 */
		if (d4custom) {
			int problem = 0;
			if (c->cacheid > d4_ncustom)
				problem |= 0x1;
			else {
				if (d4_cust_vals[c->cacheid][0] != c->flags)
					problem |= 0x2;
				if (d4_cust_vals[c->cacheid][1] != c->lg2blocksize)
					problem |= 0x4;
				if (d4_cust_vals[c->cacheid][2] != c->lg2subblocksize)
					problem |= 0x8;
				if (d4_cust_vals[c->cacheid][3] != c->lg2size)
					problem |= 0x10;
				if (d4_cust_vals[c->cacheid][4] != c->assoc)
					problem |= 0x20;
				if (d4_cust_vals[c->cacheid][5] != c->prefetch_abortpercent)
					problem |= 0x40;
				if (d4_cust_vals[c->cacheid][6] != ((c->replacementf==d4rep_lru)?'l':
							    (c->replacementf==d4rep_fifo)?'f':
							    (c->replacementf==d4rep_random)?'r':0))
					problem |= 0x80;
				if (d4_cust_vals[c->cacheid][7] != ((c->prefetchf==d4prefetch_none)?'n':
							    (c->prefetchf==d4prefetch_always)?'a':
							    (c->prefetchf==d4prefetch_loadforw)?'l':
							    (c->prefetchf==d4prefetch_subblock)?'s':
							    (c->prefetchf==d4prefetch_miss)?'m':
							    (c->prefetchf==d4prefetch_tagged)?'t':0))
					problem |= 0x100;
				if (d4_cust_vals[c->cacheid][8] != ((c->wallocf==d4walloc_always)?'a':
							    (c->wallocf==d4walloc_never)?'n':
							    (c->wallocf==d4walloc_nofetch)?'f':0))
					problem |= 0x200;
				if (d4_cust_vals[c->cacheid][9] != ((c->wbackf==d4wback_always)?'a':
							    (c->wbackf==d4wback_never)?'n':
							    (c->wbackf==d4wback_nofetch)?'f':0))
					problem |= 0x400;
			}
			if (problem) {
				fprintf (stderr, "Dinero IV: custom values "
					 "are inconsistent, problem=0x%x\n",
					 problem);
				exit (9);
			}
		}

		if ((c->flags & D4F_MEM) != 0)
			c->numsets = 1;	/* not used, but helps avoid compiler warnings */
		else {
			/* check the things the user should have set */
			if (c->lg2blocksize < 0)
				goto fail2;
			if (c->lg2subblocksize < 0 || c->lg2subblocksize > c->lg2blocksize)
				goto fail3;
			if (c->lg2size < c->lg2blocksize)
				goto fail4;
			if (c->assoc <= 0)
				goto fail5;
			if (c->replacementf == NULL || c->name_replacement == NULL)
				goto fail6;
			if (c->prefetchf == NULL || c->name_prefetch == NULL)
				goto fail7;
			if (c->wallocf == NULL || c->name_walloc == NULL)
				goto fail8;
			if (c->wbackf == NULL || c->name_wback == NULL)
				goto fail9;

			/* we don't try to check per-policy cache state */

			/* it looks ok, now initialize */
			c->numsets = (1<<c->lg2size) / ((1<<c->lg2blocksize) * c->assoc);

			c->stack = calloc (c->numsets+((c->flags&D4F_CCC)!=0),
					   sizeof(d4stackhead));
			if (c->stack == NULL)
				goto fail10;
			nnodes = c->numsets * (1 + c->assoc) +
				 (c->numsets * c->assoc + 1) * ((c->flags&D4F_CCC)!=0);
			nodes = calloc (nnodes, sizeof(d4stacknode));
			if (nodes == NULL)
				goto fail11;
			for (i = 0;  i < nnodes;  i++)
				nodes[i].cachep = c;
			ptr = nodes;
			/* set up circular list for each stack */
			for (i = 0;  i < c->numsets+((c->flags&D4F_CCC)!=0);  i++) {
				int j, n;
				n = 1 + c->assoc * ((i < c->numsets) ? 1 : c->numsets);
				c->stack[i].top = ptr;
				c->stack[i].n = n;
				for (j = 1;  j < n-1;  j++) {
					ptr[j].onstack = i;
					ptr[j].down = &ptr[j+1];
					ptr[j].up = &ptr[j-1];
				}
				ptr[0].onstack = i;
				ptr[0].down = &ptr[1];
				ptr[0].up = &ptr[n-1];
				ptr[n-1].onstack = i;
				ptr[n-1].down = &ptr[0];
				ptr[n-1].up = &ptr[n-2];
				ptr += n;
			}
			assert (ptr - nodes == nnodes);
#if D4_HASHSIZE == 0
			d4stackhash.size += c->numsets * c->assoc;
#endif
			d4nnodes += nnodes;
		}

		/* make a printable name if the user didn't pick one */
		if (c->name == NULL) {
			c->name = malloc (30);
			if (c->name == NULL)
				goto fail12;
			sprintf (c->name, "%s%d",
				 (c->flags&D4F_MEM)!=0 ? "memory" : "cache", c->cacheid);
		}
	}
#if D4_HASHSIZE > 0
	d4stackhash.size = D4_HASHSIZE;
#endif
	d4stackhash.table = calloc (d4stackhash.size, sizeof(d4stacknode*));
	if (d4stackhash.table == NULL)
		goto fail13;
	return 0;

	/* Try to undo stuff so (in principle) the user could try again */
fail13: r++;
	/* don't bother trying to deallocate c->name */
fail12:	r++;
	free (nodes);
fail11:	r++;
	free (c->stack);
fail10:	r++;
fail9:	r++;
fail8:	r++;
fail7:	r++;
fail6:	r++;
fail5:	r++;
fail4:	r++;
fail3:	r++;
fail2:	r++;
fail1:	r++;

	for (cc = d4_allcaches;  cc != c;  cc = cc->link) {
		/* don't bother trying to deallocate c->name */
		free (c->stack[0].top);
		free (c->stack);
		c->stack = NULL;
		c->numsets = 0;
	}
	d4nnodes = 0;
	return r;
}


/*
 * Initialization routines for built-in policies
 * These exist for convenience of use only.
 */
void
d4init_rep_lru (d4cache *c)
{
	c->replacementf = d4rep_lru;
	c->name_replacement = "LRU";
}

void
d4init_rep_fifo (d4cache *c)
{
	c->replacementf = d4rep_fifo;
	c->name_replacement = "FIFO";
}

void
d4init_rep_random (d4cache *c)
{
	c->replacementf = d4rep_random;
	c->name_replacement = "random";
}

void
d4init_prefetch_none (d4cache *c)
{
	c->prefetchf = d4prefetch_none;
	c->name_prefetch = "none";
}

void
d4init_prefetch_always (d4cache *c, int dist, int abortpct)
{
	c->prefetchf = d4prefetch_always;
	c->name_prefetch = "always";
	c->prefetch_distance = dist;
	c->prefetch_abortpercent = abortpct;
}

void
d4init_prefetch_loadforw (d4cache *c, int dist, int abortpct)
{
	c->prefetchf = d4prefetch_loadforw;
	c->name_prefetch = "load-forward";
	c->prefetch_distance = dist;
	c->prefetch_abortpercent = abortpct;
}

void
d4init_prefetch_subblock (d4cache *c, int dist, int abortpct)
{
	c->prefetchf = d4prefetch_subblock;
	c->name_prefetch = "subblock";
	c->prefetch_distance = dist;
	c->prefetch_abortpercent = abortpct;
}

void
d4init_prefetch_miss (d4cache *c, int dist, int abortpct)
{
	c->prefetchf = d4prefetch_miss;
	c->name_prefetch = "miss";
	c->prefetch_distance = dist;
	c->prefetch_abortpercent = abortpct;
}

void
d4init_prefetch_tagged (d4cache *c, int dist, int abortpct)
{
	c->prefetchf = d4prefetch_tagged;
	c->name_prefetch = "tagged";
	c->prefetch_distance = dist;
	c->prefetch_abortpercent = abortpct;
}

void
d4init_walloc_always (d4cache *c)
{
	c->wallocf = d4walloc_always;
	c->name_walloc = "always";
}

void
d4init_walloc_never (d4cache *c)
{
	c->wallocf = d4walloc_never;
	c->name_walloc = "never";
}

void
d4init_walloc_nofetch (d4cache *c)
{
	c->wallocf = d4walloc_nofetch;
	c->name_walloc = "nofetch";