misc.c

这是个trace drive的Cache模拟器

}

void
d4init_wback_always (d4cache *c)
{
	c->wbackf = d4wback_always;
	c->name_wback = "always";
}

void
d4init_wback_never (d4cache *c)
{
	c->wbackf = d4wback_never;
	c->name_wback = "never";
}

void
d4init_wback_nofetch (d4cache *c)
{
	c->wbackf = d4wback_nofetch;
	c->name_wback = "nofetch";
}

/* this is for the walloc policy of an icache */
int
d4walloc_impossible (d4cache *c, d4memref m)
{
	fprintf (stderr, "Dinero IV: impossible walloc policy routine called for %s!!!\n",
		 c->name);
	exit (9);
	return 0;	/* can't really get here, but some compilers get upset if we don't have a return value */
}

/* this is for the wback policy of an icache */
int
d4wback_impossible (d4cache *c, d4memref m, int setnumber, d4stacknode *ptr, int walloc)
{
	fprintf (stderr, "Dinero IV: impossible wback policy routine called for %s!!!\n",
		 c->name);
	exit (9);
	return 0;	/* can't really get here, but some compilers get upset if we don't have a return value */
}


#if 0	/* not used normally, but can be useful for debugging */
/*
 * Perform a consistency check on a priority stack
 */
void d4checkstack (d4cache *, int, char *); /* prototype avoids warnings */
void
d4checkstack (d4cache *c, int stacknum, char *msg)
{
	d4stacknode *sp, *top;
	int i, ii;
	static int tentimes = 10;

	top = c->stack[stacknum].top;
	i = 0;
	sp = top;
	do {
		i++;
		sp = sp->down;
	} while (sp != top);
	if (i != c->stack[stacknum].n) {
		if (tentimes-- < 0)
			return;
		fprintf (stderr, "%s: cache %d stack %d actual forward count=%d, shouldbe=%d\n",
			 msg, c->cacheid, stacknum, i, c->stack[stacknum].n);
	}
	ii = 0;
	sp = top;
	do {
		ii++;
		sp = sp->up;
	} while (sp != top);
	if (ii != i) {
		if (tentimes-- < 0)
			return;
		fprintf (stderr, "%s: cache %d stack %d actual forward count=%d, actual reverse count=%d\n",
			 msg, c->cacheid, stacknum, i, ii);
	}
}
#endif


/*
 * Find address in stack.
 */
d4stacknode *
d4_find (d4cache *c, int stacknum, d4addr blockaddr)
{
	d4stacknode *ptr;

	if (c->stack[stacknum].n > D4HASH_THRESH) {
		int buck = D4HASH (blockaddr, stacknum, c->cacheid);
		for (ptr = d4stackhash.table[buck];
		     ptr!=NULL && (ptr->blockaddr!=blockaddr || ptr->cachep!=c || ptr->onstack != stacknum);
		     ptr = ptr->bucket)
			assert (ptr->valid != 0);
		return ptr;
	}

	/*
	 * Don't hash, search the stack linearly.
	 * The search will terminate,
	 * because the last node is guaranteed to have valid==0.
	 */
	for (ptr = c->stack[stacknum].top;
	     ptr->blockaddr != blockaddr && ptr->valid != 0;
	     ptr = ptr->down)
		continue;

	if (ptr->valid != 0)
		return ptr;

	return NULL;	/* not found */
}


/* find the nth element from the top (1 origin) */
d4stacknode *
d4findnth (d4cache *c, int stacknum, int n)
{
	d4stacknode *p;
	int i, stacksize;

	stacksize = c->stack[stacknum].n;
	assert (n <= stacksize);

	/* go in the shortest direction to find node */
	p = c->stack[stacknum].top;
	if (n <= stacksize/2)		/* search from front */
		for (i = 1;  i < n;  i++)
			p = p->down;
	else				/* search from rear */
		for (i = stacksize+1;  i > n;  i--)
			p = p->up;
	return p;
}


/* Move node to top (most recently used position) of stack */
void
d4movetotop (d4cache *c, int stacknum, d4stacknode *ptr)
{
	d4stacknode *top = c->stack[stacknum].top;
	d4stacknode *bot;

	/* nothing to do if node is already at top */
	if (ptr != top) {
		bot = top->up;
		if (bot != ptr)	{	/* general case */
			ptr->down->up = ptr->up;	/* remove */
			ptr->up->down = ptr->down;
			ptr->up = bot;			/* insert between top & bot */
			ptr->down = top;
			bot->down = ptr;
			top->up = ptr;
		}
		c->stack[stacknum].top = ptr;
	}
}


/* Move node to bottom (least recently used, actually spare) position */
void
d4movetobot (d4cache *c, int stacknum, d4stacknode *ptr)
{
	d4stacknode *top = c->stack[stacknum].top;
	d4stacknode *bot = top->up;

	/* nothing to do if node is already at bottom */
	if (ptr != bot) {
		if (top == ptr)		/* common and favorable: move from top to bot */
			c->stack[stacknum].top = top->down;
		else {
			ptr->down->up = ptr->up;	/* remove */
			ptr->up->down = ptr->down;
			ptr->up = bot;			/* insert between top & bot */
			ptr->down = top;
			bot->down = ptr;
			top->up = ptr;
		}
	}
}


/* Insert the indicated node into the hash table */
void
d4hash (d4cache *c, int stacknum, d4stacknode *s)
{
	int buck = D4HASH (s->blockaddr, stacknum, s->cachep->cacheid);

	assert (c->stack[stacknum].n > D4HASH_THRESH);
	s->bucket = d4stackhash.table[buck];
	d4stackhash.table[buck] = s;
}


/* Remove the indicated node from the hash table */
void
d4_unhash (d4cache *c, int stacknum, d4stacknode *s)
{
	int buck = D4HASH (s->blockaddr, stacknum, c->cacheid);
	d4stacknode *p = d4stackhash.table[buck];

	assert (c->stack[stacknum].n > D4HASH_THRESH);
	if (p == s)
		d4stackhash.table[buck] = s->bucket;
	else {
		while (p->bucket != s) {
			assert (p->bucket != NULL);
			p = p->bucket;
		}
		p->bucket = s->bucket;
	}
}


/* Allocate a structure describing a pending memory reference */
d4pendstack *
d4get_mref()
{
	d4pendstack *m;

	m = d4pendfree;
	if (m != NULL) {
		d4pendfree = m->next;
		return m;
	}
	m = malloc (sizeof(*m));	/* no need to get too fancy here */
	if (m != NULL)
		return m;
	fprintf (stderr, "DineroIV ***error: no memory for pending mref\n");
	exit (9);
	return NULL;	/* can't really get here, but some compilers get upset if we don't have a return value */
}


/* Deallocate the structure used to describe a pending memory reference */
void
d4put_mref (d4pendstack *m)
{
	m->next = d4pendfree;
	d4pendfree = m;
}


/*
 * Make recursive calls for pending references
 * to own cache or towards memory
 */
void
d4_dopending (d4cache *c, d4pendstack *newm)
{
	do {
		c->pending = newm->next;
		if ((newm->m.accesstype & D4PREFETCH) != 0)
			c->ref (c, newm->m);
		else if ((newm->m.accesstype & D4_MULTIBLOCK) != 0) {
			newm->m.accesstype &= ~D4_MULTIBLOCK;
			c->ref (c, newm->m);
		}
		else {
			switch (D4BASIC_ATYPE(newm->m.accesstype)) {
			default:	fprintf (stderr, "Dinero IV: missing case %d in d4_dopending\n",
						 D4BASIC_ATYPE(newm->m.accesstype));
					exit (9);
			case D4XMISC:
			case D4XREAD:
			case D4XINSTRN:	c->bytes_read += newm->m.size;
					break;
			case D4XWRITE:	c->bytes_written += newm->m.size;
					break;
			case D4XCOPYB:
			case D4XINVAL:	/* don't count these */
					break;
			}
			c->downstream->ref (c->downstream, newm->m);
		}
		d4put_mref(newm);
	} while ((newm = c->pending) != NULL);
}


/*
 * Initiate write back for the dirty parts of a block.
 * Each contiguous bunch of subblocks is written in one operation.
 */
void
d4_wbblock (d4cache *c, d4stacknode *ptr, const int lg2sbsize)
{
	d4addr a;
	unsigned int b, dbits;
	d4pendstack *newm;
	const int sbsize = 1 << lg2sbsize;

	b = 1;
	dbits = ptr->valid & ptr->dirty;
	a = ptr->blockaddr;
	do {
		newm = d4get_mref();
		newm->m.accesstype = D4XWRITE;
		for (;  (dbits&b) == 0;  b<<=1)
			a += sbsize;
		newm->m.address = a;
		for (;  (dbits&b) != 0;  b<<=1) {
			a += sbsize;
			dbits &= ~b;
		}
		newm->m.size = a - newm->m.address;
		newm->next = c->pending;
		c->pending = newm;
	} while (dbits != 0);
	ptr->dirty = 0;
}


/* invalidate and deallocate a block, as indicated by ptr */
void
d4_invblock (d4cache *c, int stacknum, d4stacknode *ptr)
{
	assert (ptr->valid != 0);
	ptr->valid = 0;
	d4movetobot (c, stacknum, ptr);
	if (c->stack[stacknum].n > D4HASH_THRESH)
		d4_unhash (c, stacknum, ptr);
}


/*
 * Copy any dirty stuff from the cache back towards memory.  The operation
 * affects the whole cache or just 1 block, depending on m:
 * if m == NULL or m->size == 0, it affects the whole cache.
 * If prop is true, the same copyback operation will be propagated
 * to other caches towards memory.
 * This function can be invoked directly by the subroutine-calling user,
 * or indirectly by passing a D4XCOPYB access type to d4ref
 * (in which case d4ref passes prop == 1).
 *
 * NOTE: this function does not invalidate!
 */
void
d4copyback (d4cache *c, const d4memref *m, int prop)
{
	int stacknum;
	d4stacknode *ptr;
	d4pendstack *newm;

	if (m != NULL)
		assert (m->accesstype == D4XCOPYB);
	if (prop) {
		newm = d4get_mref();
		if (m != NULL)
			newm->m = *m;
		else {
			newm->m.accesstype = D4XCOPYB;
			newm->m.address = 0;
			newm->m.size = 0;	/* affect the whole cache */
		}
		newm->next = c->pending;
		c->pending = newm;
	}
	if (m != NULL && m->size > 0) {		/* copy back just 1 block */
		ptr = d4_find (c, D4ADDR2SET (c, m->address), D4ADDR2BLOCK (c, m->address));
		if (ptr != NULL && (ptr->dirty & ptr->valid) != 0)
			d4_wbblock (c, ptr, c->lg2subblocksize);
	}
	else for (stacknum=0;  stacknum < c->numsets;  stacknum++) {
		d4stacknode *top = c->stack[stacknum].top;
		assert (top->up->valid == 0); /* this loop skips the bottom node */
		for (ptr = top;  ptr->down != top;  ptr = ptr->down)
			if ((ptr->dirty & ptr->valid) != 0)
				d4_wbblock (c, ptr, c->lg2subblocksize);
	}
	if ((newm = c->pending) != NULL)
		d4_dopending (c, newm);
}