/* * Memory reference handling 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/ref.c,v 1.8 1997/12/11 07:56:19 edler Exp $ *//* * This file contains the primary functions * for handling memory references in Dinero IV. * *	Replacement policy functions * 	Prefetch policy functions *	Write allocate and back/through policy functions *	Other support functions *	Primary user-callable function: d4ref * * These functions are grouped together to allow customization * on a per-cache basis to be performed, * with macros such as D4CUSTOM, D4_CACHE_*, and D4_OPTS_*. * In such a case, this file is #include'd into some other file * multiple times (see d4customize in misc.c). * The first time, we do only some stuff that must be done just one time. * Each additional time, we define all the customized functions for one cache. * * If you add new policy functions to this file, you also need to add * some code to d4customize in misc.c! *//* * The first group of stuff in this file is only done once * if we are customizing */#if !D4CUSTOM || D4_REF_ONCE==0#include <stddef.h>#include <stdlib.h>#include <limits.h>#include <stdio.h>#include <string.h>#include <assert.h>#include "d4.h"/* some systems don't provide a proper declaration for random() */#ifdef D4_RANDOM_DEFextern D4_RANDOM_DEF random(void);#endif/* some silly macros to cope with ## wierdness */#define D4_OPT__(cacheid,spec)	D4_OPTS_ ## cacheid ## _ ## spec#define D4_OPT_(cacheid,spec)	D4_OPT__(cacheid,spec)#define D4_OPT(spec)		D4_OPT_(D4_CACHEID,spec)#if !D4CUSTOM /* these are just dummies to avoid unresolved references */int d4_ncustom = 0;long *d4_cust_vals[1] = { NULL };#endif/* This is a general mechanism by which you can tell if we are customized */const int d4custom = D4CUSTOM;/* * We need some non-customized policy functions even in the customized * case.  These dummy functions aren't for actually calling, but * are needed to resolve references, e.g., when the user sets * the function pointers in d4cache before calling d4setup. * They also allow comparison to be done in obscure cases, e.g., to * see if a particular policy is in effect. */#if D4CUSTOMstatic void d4dummy_crash (char *name)	{ fprintf (stderr, "Dinero IV: someone called dummy function %s!\n", name);	  exit(9);	}d4stacknode *d4rep_lru (d4cache *c, int stacknum, d4memref m, d4stacknode *ptr)	{ d4dummy_crash("d4rep_lru"); return NULL; }d4stacknode *d4rep_fifo (d4cache *c, int stacknum, d4memref m, d4stacknode *ptr)	{ d4dummy_crash("d4rep_fifo"); return NULL; }d4stacknode *d4rep_random (d4cache *c, int stacknum, d4memref m, d4stacknode *ptr)	{ d4dummy_crash("d4rep_random"); return NULL; }d4pendstack *d4prefetch_none (d4cache *c, d4memref m, int miss, d4stacknode *stackptr)	{ d4dummy_crash("d4prefetch_none"); return NULL; }d4pendstack *d4prefetch_always (d4cache *c, d4memref m, int miss, d4stacknode *stackptr)	{ d4dummy_crash("d4prefetch_always"); return NULL; }d4pendstack *d4prefetch_loadforw (d4cache *c, d4memref m, int miss, d4stacknode *stackptr)	{ d4dummy_crash("d4prefetch_loadforw"); return NULL; }d4pendstack *d4prefetch_subblock (d4cache *c, d4memref m, int miss, d4stacknode *stackptr)	{ d4dummy_crash("d4prefetch_subblock"); return NULL; }d4pendstack *d4prefetch_miss (d4cache *c, d4memref m, int miss, d4stacknode *stackptr)	{ d4dummy_crash("d4prefetch_miss"); return NULL; }d4pendstack *d4prefetch_tagged (d4cache *c, d4memref m, int miss, d4stacknode *stackptr)	{ d4dummy_crash("d4prefetch_tagged"); return NULL; }int d4walloc_always (d4cache *c, d4memref m)	{ d4dummy_crash("d4walloc_always"); return 0; }int d4walloc_never (d4cache *c, d4memref m)	{ d4dummy_crash("d4walloc_never"); return 0; }int d4walloc_nofetch (d4cache *c, d4memref m)	{ d4dummy_crash("d4walloc_nofetch"); return 0; }int d4wback_always (d4cache *c, d4memref m, int setnumber, d4stacknode *ptr, int walloc)	{ d4dummy_crash("d4wback_always"); return 0; }int d4wback_never (d4cache *c, d4memref m, int setnumber, d4stacknode *ptr, int walloc)	{ d4dummy_crash("d4wback_never"); return 0; }int d4wback_nofetch (d4cache *c, d4memref m, int setnumber, d4stacknode *ptr, int walloc)	{ d4dummy_crash("d4wback_nofetch"); return 0; }#endif#if D4CUSTOM/* * Dynamic stub for d4ref in customized case. * This routine will normally be called at most 1 time for each cache. * Remember, if D4CUSTOM is 1, the "real" d4ref, later in this file, * will appear multiple times, renamed to something else each time. */#undef d4ref /* defeat the macro from d4.h, which users normally invoke */extern void d4ref (d4cache *, d4memref); /* prototype to avoid compiler warnings */voidd4ref (d4cache *c, d4memref m){	extern int d4_ncustom;	extern void (*d4_custom[]) (d4cache *, d4memref);	if (c->cacheid <= 0 || c->cacheid > d4_ncustom) {		/* "can't happen" */		fprintf (stderr, "Dinero IV: d4_custom is messed up "			 "(d4_ncustom %d, cacheid %d)\n", d4_ncustom, c->cacheid);		exit (9);	}	c->ref = d4_custom[c->cacheid-1];	c->ref (c, m);}#endif#define D4_REF_ONCE 1	/* don't do it again */#endif	/* !D4CUSTOM || D4_REF_ONCE==0 *//* * Everything else in this file may be done multiple times * if we're customizing. */#if !D4CUSTOM || D4_REF_ONCE>1	/* applies everything else except the last line */#if !D4CUSTOM || D4_OPT (rep_lru)/* * LRU replacement policy * With D4CUSTOM!=0 and inlining, this is also good for direct-mapped caches */D4_INLINEd4stacknode *d4rep_lru (d4cache *c, int stacknum, d4memref m, d4stacknode *ptr){	if (ptr != NULL) {	/* hits */		if ((!D4CUSTOM || D4VAL (c, assoc) > 1 || (D4VAL (c, flags) & D4F_CCC) != 0) &&		    ptr != c->stack[stacknum].top)			d4movetotop (c, stacknum, ptr);	}	else {			/* misses */		ptr = c->stack[stacknum].top->up;		assert (ptr->valid == 0);		ptr->blockaddr = D4ADDR2BLOCK (c, m.address);		if ((!D4CUSTOM || D4VAL(c,assoc) >= D4HASH_THRESH || (D4VAL(c,flags)&D4F_CCC)!=0) &&		    c->stack[stacknum].n > D4HASH_THRESH)			d4hash (c, stacknum, ptr);		c->stack[stacknum].top = ptr;	/* quicker than d4movetotop */	}	return ptr;}#endif	/* !D4CUSTOM || D4_OPT (rep_lru) */#if !D4CUSTOM || D4_OPT (rep_fifo)/* * FIFO replacement policy */D4_INLINEd4stacknode *d4rep_fifo (d4cache *c, int stacknum, d4memref m, d4stacknode *ptr){	if (ptr == NULL) {	/* misses */		ptr = c->stack[stacknum].top->up;		assert (ptr->valid == 0);		ptr->blockaddr = D4ADDR2BLOCK (c, m.address);		if (c->stack[stacknum].n > D4HASH_THRESH)			d4hash (c, stacknum, ptr);		c->stack[stacknum].top = ptr;	/* quicker than d4movetotop */	}	return ptr;}#endif	/* !D4CUSTOM || D4_OPT (rep_fifo) */#if !D4CUSTOM || D4_OPT (rep_random)/* * Random replacement policy. */D4_INLINEd4stacknode *d4rep_random (d4cache *c, int stacknum, d4memref m, d4stacknode *ptr){	if (ptr == NULL) {	/* misses */		int setsize = c->stack[stacknum].n - 1;		ptr = c->stack[stacknum].top->up;		assert (ptr->valid == 0);		ptr->blockaddr = D4ADDR2BLOCK (c, m.address);		if (setsize >= D4HASH_THRESH)			d4hash (c, stacknum, ptr);		c->stack[stacknum].top = ptr;	/* quicker than d4movetotop */		if (ptr->up->valid != 0)	/* set is full */			d4movetobot (c, stacknum, d4findnth (c, stacknum, 2 + (random() % setsize)));	}	return ptr;}#endif	/* !D4CUSTOM || D4_OPT (rep_random) */#if !D4CUSTOM || D4_OPT (prefetch_none)/* * Demand fetch only policy, no prefetching */D4_INLINEd4pendstack *d4prefetch_none (d4cache *c, d4memref m, int miss, d4stacknode *stackptr){	/* no prefetch, nothing to do */	return NULL;}#endif	/* !D4CUSTOM || D4_OPT (prefetch_none) */#if !D4CUSTOM || D4_OPT (prefetch_always)/* * Always prefetch policy */D4_INLINEd4pendstack *d4prefetch_always (d4cache *c, d4memref m, int miss, d4stacknode *stackptr){	d4pendstack *pf;	pf = d4get_mref();	pf->m.address = D4ADDR2SUBBLOCK (c, m.address + c->prefetch_distance);	pf->m.accesstype = m.accesstype | D4PREFETCH;	pf->m.size = 1<<D4VAL(c,lg2subblocksize);	return pf;}#endif	/* !D4CUSTOM || D4_OPT (prefetch_always) */#if !D4CUSTOM || D4_OPT (prefetch_loadforw)/* * Load forward prefetch policy * Don't prefetch into next block. */D4_INLINEd4pendstack *d4prefetch_loadforw (d4cache *c, d4memref m, int miss, d4stacknode *stackptr){	d4pendstack *pf;	if (D4ADDR2BLOCK(c,m.address+c->prefetch_distance) != D4ADDR2BLOCK(c,m.address))		return NULL;	pf = d4get_mref();	pf->m.address = D4ADDR2SUBBLOCK (c, m.address + c->prefetch_distance);	pf->m.accesstype = m.accesstype | D4PREFETCH;	pf->m.size = 1<<D4VAL(c,lg2subblocksize);	return pf;}#endif	/* !D4CUSTOM || D4_OPT (prefetch_loadforw) */#if !D4CUSTOM || D4_OPT (prefetch_subblock)/* * Subblock prefetch policy * Don't prefetch into next block; wrap around within block instead. */D4_INLINEd4pendstack *d4prefetch_subblock (d4cache *c, d4memref m, int miss, d4stacknode *stackptr){	d4pendstack *pf;	pf = d4get_mref();	pf->m.address = D4ADDR2SUBBLOCK (c, m.address + c->prefetch_distance);	pf->m.accesstype = m.accesstype | D4PREFETCH;	pf->m.size = 1<<D4VAL(c,lg2subblocksize);	if (D4ADDR2BLOCK(c,pf->m.address) != D4ADDR2BLOCK(c,m.address))		pf->m.address -= 1<<D4VAL(c,lg2blocksize);	return pf;}#endif	/* !D4CUSTOM || D4_OPT (prefetch_subblock) */#if !D4CUSTOM || D4_OPT (prefetch_miss)/* * Miss prefetch policy * Prefetch only on misses */D4_INLINEd4pendstack *d4prefetch_miss (d4cache *c, d4memref m, int miss, d4stacknode *stackptr){	d4pendstack *pf;	if (!miss)		return NULL;	pf = d4get_mref();	pf->m.address = D4ADDR2SUBBLOCK (c, m.address + c->prefetch_distance);	pf->m.accesstype = m.accesstype | D4PREFETCH;	pf->m.size = 1<<D4VAL(c,lg2subblocksize);	return pf;}#endif	/* !D4CUSTOM || D4_OPT (prefetch_miss) */#if !D4CUSTOM || D4_OPT (prefetch_tagged)/*  * Tagged prefetch (see Smith, "cache Memories," ~p.20) initiates  * a prefetch on the first demand reference to a (sub)-block.  Thus,  * a prefetch is initiated on a demand miss or the first demand  * reference to a (sub)-block that was brought into the cache by a  * prefetch.  * * Tagged prefetching is implemented using demand reference bits * in the cache entry.  A prefetch is started on a demand miss and * on a refernce to a (sub)-block whose reference bit was not previously set. */D4_INLINEd4pendstack *d4prefetch_tagged (d4cache *c, d4memref m, int miss, d4stacknode *stackptr){	d4pendstack *pf;	int sbbits;	sbbits = D4ADDR2SBMASK(c,m);	if (!miss && (sbbits & stackptr->referenced) != 0)		return NULL;	pf = d4get_mref();	pf->m.address = D4ADDR2SUBBLOCK (c, m.address + c->prefetch_distance);	pf->m.accesstype = m.accesstype | D4PREFETCH;	pf->m.size = 1<<D4VAL(c,lg2subblocksize);	return pf;}#endif	/* !D4CUSTOM || D4_OPT (prefetch_tagged) */#if !D4CUSTOM || D4_OPT (walloc_always)/* * Always write allocate */D4_INLINEintd4walloc_always (d4cache *c, d4memref m){	return 1;}#endif	/* !D4CUSTOM || D4_OPT (walloc_always) */#if !D4CUSTOM || D4_OPT (walloc_never)/* * Never write allocate */D4_INLINEintd4walloc_never (d4cache *c, d4memref m){	return 0;