/*
 * Copyright (C) 1996-1998 by the Board of Trustees
 *    of Leland Stanford Junior University.
 * 
 * This file is part of the SimOS distribution. 
 * See LICENSE file for terms of the license. 
 *
 */

/*****************************************************************
 *  File:  BusUma.c 
 *
 *  UMA model with bus contention, snoopy caches, writeback buffers,
 *  out-of-order split transaction bus.
 *
 * Author: $Author: blythe $
 * Date: $Date: 2003/02/23 06:19:58 $
 *****************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include "syslimits.h"
#include "scache.h"
#include "memsys.h"
#include "sim_error.h"
#include "simutil.h"
#include "eventcallback.h"
#include "list.h"
#include "cpu_interface.h"
#include "registry.h"
#include "hw_events.h"

#ifdef SOLO
#include "solo_page.h"
#define DATA_ADDR(_m, _pa) SoloGetMemoryAddr(SoloDecompressAddr(0,_pa))
#else
#define DATA_ADDR(_m, _pa) PHYS_TO_MEMADDR(_m, _pa)
#endif

static int debugMem = 0;
/*#define DEBUG_MEM*/

/*
 * Memory layout 
 * 
 * we require that the memory per mem node and the number of nodes be 
 * power-of-2 size
 */

#ifdef __alpha
#define LLD_SPACE "%ld "
#else
#define LLD_SPACE "%lld "
#endif

#define WB_BUFFER_SIZE		4
#define REQUEST_TABLE_SIZE	8
#define BUSUMA_MAX_MEMORIES	64

static int arbitrationCycles, transferCycles, memoryCycles;
static int dirtyPenalty, readOverhead, upgradeOverhead;
static int maxOverflow;

#define MEMORY_LATENCY		80	/* 80 ns */

/*
 * Interleave on a cache line basis.
 */
#ifdef SOLO
#define BusumaAddrToMemnum(_m,_addr)  SOLO_PA_NODE(SoloDecompressAddr(0,_addr))
#define BusumaAddrToMemline(_m,_addr) (SOLO_PA_OFFSET(SoloDecompressAddr(0,_addr))/SCACHE_LINE_SIZE)
#else
#define BusumaAddrToMemnum(_m,_addr) (FIRST_MEMORY(_m)+(((_addr) >>log2SCACHE_LINE_SIZE) % NUM_MEMORIES(_m)))
#define BusumaAddrToMemline(_m,_addr) ((_addr) / (SCACHE_LINE_SIZE*NUM_MEMORIES(_m)))
#endif

#define BusumaIsLocal(_cpu,_mem) (1)

enum MemReqState { REQ_FREE, WB_OVERFLOW, RT_OVERFLOW,
                   CPU_TO_BUS_OVERHEAD, BUS_ARB_WAIT, BUS_TRANSFER_WAIT, 
                   MEM_CONFLICT_WAIT, MEM_MERGE_WAIT,
                   CACHE_TRANSFER_WAIT, MEM_BUSY_WAIT, MEM_ACTIVE_WAIT,
                   REPLY_BUS_ARB_WAIT, REPLY_BUS_TRANSFER_WAIT};


#define MAX_MREQ (SIM_MAXCPUS*MEMSYS_MAX_OUTSTANDING)

typedef struct MemRequest  {
   EventCallbackHdr hdr;  /* Must be first!! */
   List_Links  link; /* Must be second (after EventCallbackhdr */
#define MREQ_TO_LIST(_m) (&((_m)->link))
#define LIST_TO_MREQ(_l) ((MemRequest *) (((char *)(_l)) - sizeof(EventCallbackHdr)))
   int cmd;
   int transId;
   PA reqAddr;
   PA addr;    /* Address scache aligned */
   unsigned int mode;
   int status;
   int result;   
   enum MemReqState state;
   int rtIndex;
   
   int memnum;
   int machnum;
   int cpunum;
   
   uint starttime;
   uint memQEnter;
   byte* data;  /* data handling - dma, writeback buffer */
   int len;
}  MemRequest;

static MemRequest MemRequestStorage[MAX_MREQ];
/* List of available mreq structures */
static List_Links freeMemReqList;

typedef struct _RequestTable {
   int used;
   PA addr;
   MemRequest *initiator;
   List_Links merge;
   List_Links delay;
} RequestTable;

static RequestTable requestTable[MAX_MACHINES][REQUEST_TABLE_SIZE];
static List_Links requestTableFullQ[MAX_MACHINES];

typedef struct _WB_Buffer {
   List_Links free;
   int numUsed;
   MemRequest entries[WB_BUFFER_SIZE];
   int numOverflowUsed;
   List_Links overflow;
} WB_Buffer;

static WB_Buffer wbBuffers[SIM_MAXCPUS];

static int busBusy[MAX_MACHINES];
static int busIdleStart[MAX_MACHINES];
static EventCallbackHdr arbitrate[MAX_MACHINES];
static List_Links lowPri[MAX_MACHINES], highPri[MAX_MACHINES];
#define WB_QUEUE(_m) (&(lowPri[_m]))


static Result BusUmaCmd(int cpuNum, int cmd, PA paddr, int transId,  PA
                        replacedPaddr, int writeback, byte *data);
static void   BusUmaDumpStats (void);
static void   BusUmaDone (void);
static void BusUmaStatus (void);
static void MemoryDone(int cpuNum, EventCallbackHdr *hdr, void *arg);
static void MemoryArrive(int memnum);
static void CPUArrive(MemRequest *mreq);
static MemRequest * IsInWBBuffer(int cpuNum, PA addr);
static void CacheSnoop(MemRequest *mreq);
static void BusFree(int cpuNum, EventCallbackHdr *hdr, void *arg);
static void ArbitrateCallback(int cpuNum, EventCallbackHdr *hdr, void *arg);
static void Arbitrate(int machine);
static Result BusUmaUncachedRead(int cpuNum, PA addr, byte *data, int len);
static Result BusUmaUncachedWrite(int cpuNum, PA addr, byte *data, int len);
static void BusUmaDrain(void);

#ifndef SOLO
static PA  BusUmaGetNodeAddress(int cpunum);
static void   BusUmaSetRemap(int cpunum, PA mask);
static void   BusUmaControlRemap(int cpunum, int isEnabled);
#endif

/*
 * Stats collected per memory system.
 */
#define STAT_HIST_BUCKETS 100
typedef struct StatsHist {
   unsigned int scaledivisor;
   SimCounter sum;
   SimCounter count;
   SimCounter counts[STAT_HIST_BUCKETS];
} StatsHist;

enum BusUmaCounterTypes {
   /* number of requests that are satisfied by a merge */
   BUC_MERGES,
   /* number of requests delayed due to conflicts */
   BUC_CONFLICTS,
   /* number of writebacks that didn't use the bus */
   BUC_KILLEDWBS,
   /* number of GETs satisfied by writeback buffer */
   BUC_GET_WBBUF,
   /* number of upgrades satisfied by writeback buffer */
   BUC_UPG_WBBUF,
   /* number of cycles bus is busy doing a get request*/
   BUC_BUS_GETRQST,
   /* number of cycles bus is busy doing a get reply*/
   BUC_BUS_GETREPLY,
   /* number of cycles bus is busy doing an upgrade*/
   BUC_BUS_UPG,
   /* number of cycles bus is busy doing a wb*/
   BUC_BUS_WB,
   /* number of cycles bus is busy doing an get which is nak'd b/c no space in request table*/
   BUC_BUS_NAK,
   /* number of cycles bus is busy */
   BUC_BUS_BUSY,
   /* number of cycles bus is idle */
   BUC_BUS_IDLE,
   /* time in memory queue */
   BUC_MEMQUEUE,
   BUC_TOTAL};

typedef struct BusUmaMemStats {
   SimCounter counts[COUNT_TOTAL];
   SimCounter buCounts[BUC_TOTAL];
   StatsHist  reqtime;                  /* latency */
} BusUmaStats;


/*
 * State associated with a memory in the system.
 */

typedef struct MemState  { 
   List_Links memoryQueue;    /* Queue to memory */
   BusUmaStats stats;   
   int busy;
   MemRequest wbHdr;	/* hack needed because we free writebackbuffer at memoryarrive,
                         and we need something to use for eventcallback */
} MemState;


static MemState *memState[BUSUMA_MAX_MEMORIES];

#ifndef SOLO
/*****************************************************************
 * remap region support 
 *****************************************************************/

static PA backmapMask[MAX_MACHINES];
static PA nodeaddrMask[MAX_MACHINES];

static void
BusUmaUpdateBackmapMask(void)
{
   /* the backmapMask is an optimization that summarizes all the enabled
    * remap masks; it has ones in any bit position which, if set, means
    * this physical address could not be the target of a remap on any
    * CPU.
    *
    * nodeaddrMask masks out the node id bits.
    */

   int i, m;
   for (m=0; m < NUM_MACHINES; m++) {
       backmapMask[m] = nodeaddrMask[m];
       for (i=FIRST_CPU(m); i<=LAST_CPU(m); i++) {
           if (remapVec->RemapEnable[i]) {
               backmapMask[m] &= remapVec->RemapMask[i];
           }
       }
   }
}

static void
BusUmaInitRemap(void)
{
   int i, machine;

   /* We initialize backmapMask to all ones except for the
    * bits that might be set in the node id field
    */

   for (machine=0; machine<NUM_MACHINES; machine++) {
       nodeaddrMask[machine] = ~0;
       for (i=0; i<NUM_CPUS(machine); i++) {
          if (!remapVec->NodeAddrInitialized) {
#ifdef TORNADO
             int m = machine;
             remapVec->NodeAddr[FIRST_CPU(machine)+i] =
                (i*NUM_MEMORIES(m)/NUM_CPUS(m)) *
                (MEM_SIZE(m) / NUM_CPUS(m));
             CPUWarning("busuma: nodeaddr for %d/%d is %lx\n",
                        i, FIRST_CPU(machine)+i,
 			  (unsigned long)(remapVec->NodeAddr[FIRST_CPU(machine)+i]));
#elif defined(SIM_ORIGIN)
             remapVec->NodeAddr[FIRST_CPU(machine)+i] =
                MEMADDR_TO_PHYS(machine, SIM_MEM_ADDR(machine) + 
                                (i/2) * 2 * (MEM_SIZE(machine) / NUM_CPUS(machine)));
#else
             remapVec->NodeAddr[FIRST_CPU(machine)+i] =
                MEMADDR_TO_PHYS(machine, SIM_MEM_ADDR(machine) + 
                                i * (MEM_SIZE(machine) / NUM_CPUS(machine)));
#endif
          }
          nodeaddrMask[machine] &= ~remapVec->NodeAddr[FIRST_CPU(machine)+i];
       }
   }
   remapVec->NodeAddrInitialized = 1;

   /* now zero out the low bits of the backmapmask */
   BusUmaUpdateBackmapMask();
}

static void
BusUmaSetRemap(int cpunum, PA mask)
{
   remapVec->RemapMask[cpunum] = mask;
   BusUmaUpdateBackmapMask();
}

static void
BusUmaControlRemap(int cpunum, int isEnabled)
{
   remapVec->RemapEnable[cpunum] = isEnabled;
   BusUmaUpdateBackmapMask();
}

static PA
BusUmaGetNodeAddress(int cpunum)
{
   return remapVec->NodeAddr[cpunum];
}

static PA
ReverseRemap(PA paddr, int cpunum)
{
   if ((paddr & remapVec->RemapMask[cpunum]) == remapVec->NodeAddr[cpunum]) {
      return paddr - remapVec->NodeAddr[cpunum];
   } else if ((paddr & remapVec->RemapMask[cpunum]) == 0) {
      return paddr + remapVec->NodeAddr[cpunum];
   } else {
      return paddr;
   }
}

#define BACKMAP_PADDR(paddr,cpunum)		                   \
      (((paddr & backmapMask[M_FROM_CPU(cpunum)])                   \
     || !remapVec->RemapEnable[cpunum])                             \
    ? paddr : ReverseRemap(paddr, cpunum))

#endif 
#ifdef SOLO
#define BACKMAP_PADDR(paddr,cpunum)  (paddr)
#endif

/*****************************************************************
 * BusUmaInit
 *****************************************************************/
void 
BusUmaInit(void)
{
   int i, j, m;
   int halfTransXTime;
   
   memsysVec.type = BUSUMA;
   memsysVec.NoMemoryDelay = 0;
   memsysVec.MemsysCmd = BusUmaCmd;
   memsysVec.MemsysDumpStats = BusUmaDumpStats;
   memsysVec.MemsysDone = BusUmaDone;
   memsysVec.MemsysStatus = BusUmaStatus;
   memsysVec.MemsysDrain = BusUmaDrain;

#ifndef SOLO
   memsysVec.MemsysSetRemap = BusUmaSetRemap;
   memsysVec.MemsysControlRemap = BusUmaControlRemap;
   memsysVec.MemsysGetNodeAddress = BusUmaGetNodeAddress;
#endif

   halfTransXTime = NanoSecsToCycles(SCACHE_LINE_SIZE*1000/BUS_BW/2);
   arbitrationCycles = 2*halfTransXTime/5;
   transferCycles = halfTransXTime - arbitrationCycles;
   ASSERT(transferCycles >= 0);
   memoryCycles = NanoSecsToCycles(MEMORY_LATENCY);
   dirtyPenalty = DIRTY_PENALTY;
   readOverhead = MEM_CYCLE_TIME - memoryCycles - 2*halfTransXTime;
   ASSERT(readOverhead >= 0);
   upgradeOverhead = UPGRADE_TIME - halfTransXTime;
   ASSERT(upgradeOverhead >= 0);
   /* maxOverflow = 1; this doesn't work for mxs or with prefetching */
   maxOverflow = 5;

   CPUPrint("MEMSYS: BusUma - arbitrate: %d, transfer: %d, memory: %d\n\n",
            arbitrationCycles, transferCycles, memoryCycles);
   CPUPrint("MEMSYS: BusUma - readOverhead: %d, upgradeOverhead: %d, dirtyPenalty: %d\n",
            readOverhead, upgradeOverhead, dirtyPenalty);

   for (m = 0; m < NUM_MACHINES; m++) {
       if( !NUM_MEMORIES(m) )
           CPUError("BusUma: NumMemories must be >0 (machine %d)\n", m);
       if( MEM_SIZE(m) % NUM_MEMORIES(m) != 0 )
           CPUError("BusUma: the memory size must be a multiple of the number of memories (machine %d)\n",m);
 
       CPUPrint("BusUma with %d memories; cache-line interleaving (machine %d)\n", NUM_MEMORIES(m), m);
       
       busBusy[m] = 0;
       busIdleStart[m] = 1;
       
       bzero((char *)(requestTable[m]),
             sizeof(RequestTable)*REQUEST_TABLE_SIZE);
       for (i = 0; i < REQUEST_TABLE_SIZE; i++) {
           List_Init(&requestTable[m][i].merge);
           List_Init(&requestTable[m][i].delay);
       }
       List_Init(&requestTableFullQ[m]);
   }

   CPUPrint("MEMFields IGETS LLGETS DMAGETS DGETS DMAGETXS GETXS SCUPGRADES UPGRADES WRITEBACKS REPLHINTS UNCACHEDWRITES UNCACHEDACCWRITES UNCACHEDREADS INVALORDNGRADESENT NAKS REMOTEDIRTY EXCLUSIVEONSHARED MEMORYACCESS\n");
   CPUPrint("MEMBUSUMAFields MERGES CONFLICTS KILLEDWBS GET_WBBUF UPG_WBBUF BUS_GETRQST BUS_GETREPLY BUS_UPG BUS_WB BUS_NAK BUS_BUSY BUS_IDLE MEMQUEUE\n");

   /* initialize writeback buffer for each proc */
   for (i = 0; i < SIM_MAXCPUS; i++) {
      List_Init(&wbBuffers[i].free);
      wbBuffers[i].numUsed = 0;
      for (j = 0; j < WB_BUFFER_SIZE; j++) {
         wbBuffers[i].entries[j].cmd = MEMSYS_WRITEBACK;
#ifdef DATA_HANDLING
         wbBuffers[i].entries[j].data = (char *)calloc(1,SCACHE_LINE_SIZE);
#else
         wbBuffers[i].entries[j].data = NULL;
#endif
         wbBuffers[i].entries[j].addr = 0;
         wbBuffers[i].entries[j].state = REQ_FREE;
         List_Insert(MREQ_TO_LIST(&wbBuffers[i].entries[j]), LIST_ATREAR(&wbBuffers[i].free));
      }
      wbBuffers[i].numOverflowUsed = 0;
      List_Init(&wbBuffers[i].overflow);
   }

   for (m = 0; m < NUM_MACHINES; m++) {
       List_Init(&lowPri[m]);
       List_Init(&highPri[m]);
   }

   List_Init(&freeMemReqList);
   
   for (i = 0; i < MAX_MREQ; i++) { 
      MemRequest *mreq = MemRequestStorage + i;
      bzero((char *) (mreq), sizeof(MemRequestStorage[0]));
      List_InitElement(MREQ_TO_LIST(mreq));
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
   }

   for (i = 0; i < TOTAL_MEMORIES; i++) { 
      memState[i] = (MemState *) ZMALLOC(sizeof(MemState), "memState");
      ASSERT(memState[i]);
      List_Init(&memState[i]->memoryQueue);
      bzero((char *) &memState[i]->stats, sizeof(BusUmaStats));
      memState[i]->wbHdr.cmd = MEMSYS_WRITEBACK;
      memState[i]->wbHdr.memnum = i;
   }
#ifndef SOLO
   BusUmaInitRemap();
#endif
}

static void
FreeWBentry(MemRequest *mreq)
{
   if (mreq->state == WB_OVERFLOW) {
      mreq->reqAddr = MEMSYS_NOADDR;
      mreq->len = 0;
      mreq->data = NULL;

      return;
   } else if (mreq->state == CPU_TO_BUS_OVERHEAD) {
      EventCallbackRemove((EventCallbackHdr*)mreq);
      memState[mreq->memnum]->stats.buCounts[BUC_KILLEDWBS]++;
   } else if (mreq->state == BUS_ARB_WAIT) {
      List_Remove(MREQ_TO_LIST(mreq));
      memState[mreq->memnum]->stats.buCounts[BUC_KILLEDWBS]++;
   } else if (mreq->state == BUS_TRANSFER_WAIT) {
      /* this can get called from BusUmaDrain */
      EventCallbackRemove((EventCallbackHdr*)mreq);
      memState[mreq->memnum]->stats.buCounts[BUC_KILLEDWBS]++;
   } else {
      ASSERT(mreq->state == MEM_BUSY_WAIT);
   }
   mreq->state = REQ_FREE;
   List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&wbBuffers[mreq->cpunum].free));
   wbBuffers[mreq->cpunum].numUsed--;
   ASSERT(wbBuffers[mreq->cpunum].numUsed >=0);

   if (!List_IsEmpty(&wbBuffers[mreq->cpunum].overflow)) {
      /* cpu was stalled waiting for space in writeback buffer, so reissue the request */
      Result result;
      List_Links *itemPtr = List_First(&wbBuffers[mreq->cpunum].overflow);
      MemRequest *ovfReq = LIST_TO_MREQ(itemPtr);
      List_Remove(itemPtr);
      wbBuffers[mreq->cpunum].numOverflowUsed--;

      result = BusUmaCmd(mreq->cpunum, ovfReq->cmd,
                         ovfReq->addr, ovfReq->transId,
                         ovfReq->reqAddr, ovfReq->len,
                         ovfReq->data);

      ovfReq->state = REQ_FREE;
      List_Insert(MREQ_TO_LIST(ovfReq), LIST_ATREAR(&freeMemReqList));
      if (result == SUCCESS) {
         ASSERT(CPUVec.Unstall);
         CPUVec.Unstall(mreq->cpunum);
      }
   }
}

/* Check the writeback buffer to see if an entry with the given address is already there
 * If so, and read=1 place the data from in the buffer into argument data
 *        and read=0 place the data from the argument into the buffer (collapse two writebacks into one)
 */
static MemRequest *
IsInWBBuffer(int cpuNum, PA addr)
{
   List_Links *itemPtr, *nextPtr;
   int i;

   if (wbBuffers[cpuNum].numUsed != 0) {
      for (i = 0; i < WB_BUFFER_SIZE; i++) {
         if ((wbBuffers[cpuNum].entries[i].addr == addr) &&
             ((wbBuffers[cpuNum].entries[i].state == CPU_TO_BUS_OVERHEAD) ||
              (wbBuffers[cpuNum].entries[i].state == BUS_ARB_WAIT))) {
            return &wbBuffers[cpuNum].entries[i];
         }
      }
   }

   for (itemPtr = List_First(&wbBuffers[cpuNum].overflow), nextPtr = NULL;
        !List_IsAtEnd(&wbBuffers[cpuNum].overflow, itemPtr);
        itemPtr = nextPtr) {

      nextPtr = List_Next(itemPtr);
      if (LIST_TO_MREQ(itemPtr)->reqAddr == addr)
         return LIST_TO_MREQ(itemPtr);
   }

   return NULL;
}


static void
NakRequest(MemRequest *mreq)
{
   CacheCmdDone(mreq->cpunum, mreq->transId, mreq->mode, MEMSYS_STATUS_NAK,
                mreq->result, mreq->data);
   mreq->state = REQ_FREE;
   List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
   memState[mreq->memnum]->stats.counts[COUNT_NAKS]++;
}

static void
ErrorRequest(MemRequest *mreq)
{
   CacheCmdDone(mreq->cpunum, mreq->transId, mreq->mode, MEMSYS_STATUS_ERROR,
                mreq->result, mreq->data);
   mreq->state = REQ_FREE;
   List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
   memState[mreq->memnum]->stats.counts[COUNT_NAKS]++;
}

static void
RTMerge(MemRequest *mreq, int index)
{
   mreq->state = MEM_MERGE_WAIT;
   mreq->rtIndex = index;
   List_Insert(MREQ_TO_LIST(mreq),
               LIST_ATREAR(&requestTable[mreq->machnum][index].merge));
   if (debugMem)
      CPUPrint("DBGBSU %lld %d merge addr (0x%x)\n",
               CPUVec.CycleCount(0), mreq->cpunum, mreq->addr);
}

static void
RTDelay(MemRequest *mreq, int index)
{
   mreq->state = MEM_CONFLICT_WAIT;
   mreq->rtIndex = index;
   List_Insert(MREQ_TO_LIST(mreq),
               LIST_ATREAR(&requestTable[mreq->machnum][index].delay));
   if (debugMem)
      CPUPrint("DBGBSU %lld %d delay addr (0x%x)\n",
               CPUVec.CycleCount(0), mreq->cpunum, mreq->addr);
}

static void
CheckForMergeDelay(List_Links *list, MemRequest *mreq, int numFree)
{
   List_Links *itemPtr, *nextPtr;

   for (itemPtr = List_First(list), nextPtr = NULL;
        !List_IsAtEnd(list, itemPtr);
        itemPtr = nextPtr) {
         
      MemRequest *req2 = LIST_TO_MREQ(itemPtr);
      nextPtr = List_Next(itemPtr);

      if (req2->addr == mreq->addr) {
         switch (req2->cmd & MEMSYS_CMDMASK) {
         case MEMSYS_GET:
            /* if mode shared, merge, otherwise fall through to GETX/UPGRADE */
            if (mreq->mode == MEMSYS_SHARED) {
               List_Remove(itemPtr);
               RTMerge(req2, mreq->rtIndex);
               break;
            }
         case MEMSYS_GETX:
         case MEMSYS_UPGRADE:
            List_Remove(itemPtr);
            RTDelay(req2, mreq->rtIndex);
            break;
         case MEMSYS_WRITEBACK:
            /* this is OK because the writeback will be killed in cachesnoop */
            break;
         default:
            CPUError("Unknown memsys command (0x%x) in BusUma::RTInsert\n", req2->cmd);
         }
      } else {
         /* if we took the last entry and a get/getx is arbitrating then add it to RTfull queue */
         if ((numFree == 1) && (req2->rtIndex == -1) && (req2->state != RT_OVERFLOW) &&
             (((req2->cmd & MEMSYS_CMDMASK) == MEMSYS_GET) ||
              ((req2->cmd & MEMSYS_CMDMASK) == MEMSYS_GETX))) {
            req2->state = RT_OVERFLOW;
            List_Remove(itemPtr);
            List_Insert(itemPtr,
                        LIST_ATREAR(&requestTableFullQ[mreq->machnum]));
         }
      }
   }
}

static void
RTInsert(MemRequest *mreq) 
{
   int index, numFree = 0;

   for (index = 0; index < REQUEST_TABLE_SIZE; index++) {
       if (!requestTable[mreq->machnum][index].used) {
           if (numFree == 0) {
               requestTable[mreq->machnum][index].used = 1;
               requestTable[mreq->machnum][index].addr = mreq->addr;
               requestTable[mreq->machnum][index].initiator = mreq;
               mreq->rtIndex = index;
               if (debugMem)
                   CPUPrint("DBGBSU %lld %d addr (0x%x) assigned RTindex %d\n",
                            CPUVec.CycleCount(0), mreq->cpunum, mreq->addr, index);
           }
           numFree++;
       }
   }
   
   ASSERT(numFree != 0);
   /* add all pending requests to same addr merge/delay queues 
       also add all get/getx to request delay queue if this request took the last spot */

   CheckForMergeDelay(&highPri[mreq->machnum], mreq, numFree);
   CheckForMergeDelay(&requestTableFullQ[mreq->machnum], mreq, numFree);
}

static void
MemoryDone(int cpuNum, EventCallbackHdr *hdr, void *arg)
{
   MemRequest *mreq = (MemRequest *)hdr;
   ASSERT(mreq->state == MEM_ACTIVE_WAIT);
   ASSERT(M_FROM_CPU(cpuNum) == mreq->machnum);
   
   switch (mreq->cmd & MEMSYS_CMDMASK) {
   case MEMSYS_GET:
   case MEMSYS_GETX:
      mreq->state = REPLY_BUS_ARB_WAIT;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&highPri[mreq->machnum]));
      Arbitrate(mreq->machnum);
      break;
   case MEMSYS_WRITEBACK:
      break;
   case MEMSYS_SHARING_WRITEBACK:
      /* free the mreq */
      mreq->state = REQ_FREE;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
      break;
   default:
      CPUError("Bad mreq->cmd (0x%x)\n", mreq->cmd);
   }

   /* now check for more requests */
   if (!List_IsEmpty(&memState[mreq->memnum]->memoryQueue))
      MemoryArrive(mreq->memnum);
   else
      memState[mreq->memnum]->busy = 0;
}

/* a request just arrived at this memormy
 * copy data from memory and stall 
 */
static void
MemoryArrive(int memnum)
{
   MemRequest *mreq;

   ASSERT(!List_IsEmpty(&memState[memnum]->memoryQueue));
   mreq = LIST_TO_MREQ(List_First(&memState[memnum]->memoryQueue));
   List_Remove(MREQ_TO_LIST(mreq));
   ASSERT(mreq->state == MEM_BUSY_WAIT);

   memState[memnum]->busy = 1;
   memState[mreq->memnum]->stats.counts[COUNT_MEMORYACCESS]++;
   memState[memnum]->stats.buCounts[BUC_MEMQUEUE] += CPUVec.CycleCount(mreq->cpunum) - mreq->memQEnter;

   switch (mreq->cmd & MEMSYS_CMDMASK) {
   case MEMSYS_GET:
      if (mreq->cmd & MEMSYS_DMAFLAVOR) {
         bcopy(DATA_ADDR(mreq->machnum, mreq->reqAddr), mreq->data, mreq->len);
      } else {
         mreq->data = (byte*)DATA_ADDR(mreq->machnum, mreq->addr);
      }
      if (debugMem)
         CPUPrint("DBGBSU %lld get arrived at memory (0x%x)\n", CPUVec.CycleCount(0), mreq->addr);
      break;
   case MEMSYS_GETX:
      if (mreq->cmd & MEMSYS_DMAFLAVOR) {
         bcopy(mreq->data, DATA_ADDR(mreq->machnum, mreq->reqAddr), mreq->len);
      } else {
         mreq->data = (byte*)DATA_ADDR(mreq->machnum, mreq->addr);
      }
      if (debugMem)
         CPUPrint("DBGBSU %lld getx arrived at memory (0x%x)\n", CPUVec.CycleCount(0), mreq->addr);
      break;
   case MEMSYS_WRITEBACK:
      if (debugMem)
         CPUPrint("DBGBSU %lld wb arrived at memory (0x%x)\n", CPUVec.CycleCount(0), mreq->addr);
#ifdef DATA_HANDLING
      bcopy(mreq->data, DATA_ADDR(mreq->machnum, mreq->addr), SCACHE_LINE_SIZE);
#endif
      FreeWBentry(mreq);
      mreq = &memState[memnum]->wbHdr;
      break;
   case MEMSYS_SHARING_WRITEBACK:
      if (debugMem)
         CPUPrint("DBGBSU %lld sharingWB arrived at memory (0x%x)\n", CPUVec.CycleCount(0), mreq->addr);
      /* don't really need to do anything except make memory busy */
      break;
   default:
      CPUError("Bad mreq->cmd (0x%x)\n", mreq->cmd);
   }
   mreq->state = MEM_ACTIVE_WAIT;
   EventDoCallback(FIRST_CPU(mreq->machnum), MemoryDone, (EventCallbackHdr *)mreq, NULL, memoryCycles);
}

/* request came back from memory
 * free the request table entry if the memory request used it
 */
static void
CPUArrive(MemRequest *mreq)
{
   List_Links *itemPtr, *nextPtr, *mergeHdr, *delayHdr;
   int rtIndex = mreq->rtIndex;

   ASSERT((mreq->state == REPLY_BUS_TRANSFER_WAIT) ||
          ((mreq->state == BUS_TRANSFER_WAIT) &&
           ((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_UPGRADE)));
   CacheCmdDone(mreq->cpunum, mreq->transId, mreq->mode, mreq->status,
                mreq->result, mreq->data);

   if (rtIndex != -1) {
      ASSERT(requestTable[mreq->machnum][rtIndex].initiator == mreq);
      mergeHdr = &requestTable[mreq->machnum][rtIndex].merge;
      delayHdr = &requestTable[mreq->machnum][rtIndex].delay;

      /* if initiator is a GET, handle all the merges */
      if ((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_GET) {
         for (itemPtr = List_First(mergeHdr), nextPtr = NULL;
              !List_IsAtEnd(mergeHdr, itemPtr);
              itemPtr = nextPtr) {

            MemRequest *mergeReq = LIST_TO_MREQ(itemPtr);
            nextPtr = List_Next(itemPtr);

            memState[mreq->memnum]->stats.buCounts[BUC_MERGES]++;
            CacheCmdDone(mergeReq->cpunum, mergeReq->transId, mergeReq->mode, mreq->status,
                         mreq->result, mreq->data);
            if (debugMem)
               CPUPrint("DBGBSU %lld %d merged addr (0x%x)\n",
                        CPUVec.CycleCount(0), mergeReq->cpunum, mergeReq->addr);
            /* free the mreq */
            List_Remove(itemPtr);
            List_Insert(itemPtr, LIST_ATREAR(&freeMemReqList));
            LIST_TO_MREQ(itemPtr)->state = REQ_FREE;
         }
      }

      /* if something on delay queue, make the first entry be the new initiator */
      if (!List_IsEmpty(delayHdr)) {
         MemRequest *delayReq = LIST_TO_MREQ(List_First(delayHdr));

         List_Remove(MREQ_TO_LIST(delayReq));
         requestTable[mreq->machnum][rtIndex].initiator = delayReq;

         /* if the new initiator is a GET, then move all the other GETs in the delay queue
            to the merge queue */
         if ((delayReq->cmd & MEMSYS_CMDMASK) == MEMSYS_GET) {
            
            for (itemPtr = List_First(delayHdr), nextPtr = NULL;
                 !List_IsAtEnd(delayHdr, itemPtr);
                 itemPtr = nextPtr) {

               nextPtr = List_Next(itemPtr);
               
               if ((LIST_TO_MREQ(itemPtr)->cmd & MEMSYS_CMDMASK) == MEMSYS_GET) {
                  List_Remove(itemPtr);
                  List_Insert(itemPtr, LIST_ATREAR(mergeHdr));
                  LIST_TO_MREQ(itemPtr)->state = MEM_MERGE_WAIT;
               }
            }
         }

         memState[mreq->memnum]->stats.buCounts[BUC_CONFLICTS]++;
         if (debugMem)
            CPUPrint("DBGBSU %lld %d issue delayed addr (0x%x)\n",
                     CPUVec.CycleCount(0), delayReq->cpunum, delayReq->addr);
         
         /* Now let the new initiator arbitrate the bus */
         delayReq->state = BUS_ARB_WAIT;
         List_Insert(MREQ_TO_LIST(delayReq), LIST_ATREAR(&highPri[mreq->machnum]));
         Arbitrate(mreq->machnum);
      } else {
         /* free the request table entry, and release the first request in RTfullQ */
         requestTable[mreq->machnum][rtIndex].used = 0;
         if (debugMem)
            CPUPrint("DBGBSU %lld %d freeing RT index %d addr(0x%x)\n",
                     CPUVec.CycleCount(mreq->cpunum), mreq->cpunum, rtIndex, mreq->addr);

         if (!List_IsEmpty(&requestTableFullQ[mreq->machnum])) {
            itemPtr = List_First(&requestTableFullQ[mreq->machnum]);
            List_Remove(itemPtr);
            ASSERT(LIST_TO_MREQ(itemPtr)->state == RT_OVERFLOW);
            LIST_TO_MREQ(itemPtr)->state = BUS_ARB_WAIT;
            List_Insert(itemPtr, LIST_ATREAR(&highPri[mreq->machnum]));
            if (debugMem)
               CPUPrint("DBGBSU %lld %d issuing RTfullQ addr(0x%x)\n",
                        CPUVec.CycleCount(mreq->cpunum), LIST_TO_MREQ(itemPtr)->cpunum,
                        LIST_TO_MREQ(itemPtr)->addr);
         }
      }
   }

   /* sharing writeback also go to memory */
   if (mreq->result & MEMSYS_RESULT_CACHE) {
      mreq->state = MEM_BUSY_WAIT;
      mreq->cmd = MEMSYS_SHARING_WRITEBACK;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&memState[mreq->memnum]->memoryQueue));
      mreq->memQEnter = CPUVec.CycleCount(mreq->cpunum);

      if (!memState[mreq->memnum]->busy)
         MemoryArrive(mreq->memnum);
      
   } else {
      mreq->state = REQ_FREE;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
   }
}


static void
CacheTransferDone(int cpuNum, EventCallbackHdr *hdr, void *arg)
{
   MemRequest *mreq = (MemRequest *)hdr;
   ASSERT(M_FROM_CPU(cpuNum) == mreq->machnum);

   if (mreq->cmd & MEMSYS_DMAFLAVOR) {
      if ((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_GET) {
         bcopy(DATA_ADDR(mreq->machnum, mreq->reqAddr), mreq->data, mreq->len);
      } else {
         ASSERT((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_GETX);
         bcopy(mreq->data, DATA_ADDR(mreq->machnum, mreq->reqAddr), mreq->len);
      }
   } else {
      mreq->data = (byte*)DATA_ADDR(mreq->machnum, mreq->addr);
   }
   mreq->state = REPLY_BUS_ARB_WAIT;
   List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&highPri[mreq->machnum]));
   Arbitrate(mreq->machnum);
}

/* Nak all pending upgrades to the same address */
static void
NakUpgrades(MemRequest *mreq)
{
   List_Links *queueHead, *itemPtr, *nextPtr;

   if (mreq->rtIndex == -1) {
      /* there cannot be a request table entry for this addr, so only check highPri queue */
      queueHead = &highPri[mreq->machnum];
   } else {
      /* there cannot be upgrades in highPri queue, so only check requestTable delay queue */
       queueHead = &requestTable[mreq->machnum][mreq->rtIndex].delay;
   }

   for (itemPtr = List_First(queueHead), nextPtr = NULL;
        !List_IsAtEnd(queueHead, itemPtr);
        itemPtr = nextPtr) {
   
      MemRequest *req2 = LIST_TO_MREQ(itemPtr);
      nextPtr = List_Next(itemPtr);

      if ((req2->addr == mreq->addr) &&
          ((req2->cmd & MEMSYS_CMDMASK) == MEMSYS_UPGRADE)) {
         List_Remove(itemPtr);
         NakRequest(req2);
      }
   }
}


/* Check caches and writeback buffers for coherency
 */
static void
CacheSnoop(MemRequest *mreq)
{
   MemRequest *wbReq;
   int i, way=0, wasDirty, cacheToCache=0;
   char *data;
   int machine = M_FROM_CPU(mreq->cpunum);

   ASSERT(mreq->state == BUS_TRANSFER_WAIT);
   /* add gets without request table indexes to request table */
   if ((mreq->rtIndex == -1) && (((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_GET) ||
                                 ((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_GETX))) {
      RTInsert(mreq);
   }

   switch (mreq->cmd & MEMSYS_CMDMASK) {
   case MEMSYS_GET:
      memState[mreq->memnum]->stats.buCounts[BUC_BUS_GETRQST] += arbitrationCycles + transferCycles;
      /* do the sharing writeback if necessary */
      for (i = FIRST_CPU(machine); i <= LAST_CPU(machine); i++) {
         if ((i == mreq->cpunum) && !(mreq->cmd & MEMSYS_DMAFLAVOR)) continue;
         if (IsInSCache(i, BACKMAP_PADDR(mreq->addr,i), MEMSYS_EXCLUSIVE, &data, &way)) {
            CacheWriteback(i, BACKMAP_PADDR(mreq->addr,i), SCACHE_LINE_SIZE, 
                           (byte*)DATA_ADDR(mreq->machnum, mreq->addr));
            cacheToCache=1;
            mreq->result |= MEMSYS_RESULT_DOWNGRADE;
            break;
         }
         wbReq = IsInWBBuffer(i, mreq->addr);
         if (wbReq) {
#ifdef DATA_HANDLING
            bcopy(wbReq->data, DATA_ADDR(mreq->machnum, mreq->addr),
                  SCACHE_LINE_SIZE);
#endif
            /* remove entry from writeback buffer */
            FreeWBentry(wbReq);
            cacheToCache=1;
            mreq->result |= MEMSYS_RESULT_DOWNGRADE;
            break;
         }
      }
      break;
   case MEMSYS_GETX:
      memState[mreq->memnum]->stats.buCounts[BUC_BUS_GETRQST] += arbitrationCycles + transferCycles;
      /* do the sharing writeback and invalidate if necessary */
      for (i = FIRST_CPU(machine); i <= LAST_CPU(machine); i++) {
         if ((i == mreq->cpunum) && !(mreq->cmd & MEMSYS_DMAFLAVOR)) continue;
         if (IsInSCache(i, BACKMAP_PADDR(mreq->addr,i), MEMSYS_EXCLUSIVE, &data, &way)) {
            CacheExtract(i, BACKMAP_PADDR(mreq->addr,i), SCACHE_LINE_SIZE, &wasDirty, 
                         (byte*)DATA_ADDR(mreq->machnum, mreq->addr));
            cacheToCache=1;
            mreq->result |= MEMSYS_RESULT_INVALIDATE;
            break;
         } else if (IsInSCache(i, BACKMAP_PADDR(mreq->addr,i), MEMSYS_SHARED, &data, &way)) {
            CacheInvalidate(i, BACKMAP_PADDR(mreq->addr,i), SCACHE_LINE_SIZE, FALSE, &wasDirty);
            mreq->result |= MEMSYS_RESULT_INVALIDATE;
            memState[mreq->memnum]->stats.counts[COUNT_INVALORDNGRADESENT]++;
            memState[mreq->memnum]->stats.counts[COUNT_EXCLUSIVEONSHARED]++;
         } else {
            CacheFakeInvalidate(i,BACKMAP_PADDR(mreq->addr,i),SCACHE_LINE_SIZE);
         }
                       
         wbReq = IsInWBBuffer(i, mreq->addr);
         if (wbReq) {
#ifdef DATA_HANDLING
            bcopy(wbReq->data, DATA_ADDR(mreq->machnum, mreq->addr),
                  SCACHE_LINE_SIZE);
#endif
            /* remove entry from writeback buffer */
            FreeWBentry(wbReq);
            cacheToCache=1;
            mreq->result |= MEMSYS_RESULT_INVALIDATE;
            break;
         }
      }
      NakUpgrades(mreq);
      break;
   case MEMSYS_UPGRADE:
      memState[mreq->memnum]->stats.buCounts[BUC_BUS_UPG] += arbitrationCycles + transferCycles;
      /* send invalidate if necessary */
      for (i = FIRST_CPU(machine); i <= LAST_CPU(machine); i++) {
         if (i == mreq->cpunum) continue;
         ASSERT(!IsInSCache(i, BACKMAP_PADDR(mreq->addr,i), MEMSYS_EXCLUSIVE, &data, &way));
         if (IsInSCache(i, BACKMAP_PADDR(mreq->addr,i), MEMSYS_SHARED, &data, &way)) {
            CacheInvalidate(i, BACKMAP_PADDR(mreq->addr,i), SCACHE_LINE_SIZE, FALSE, &wasDirty);
            mreq->result |= MEMSYS_RESULT_INVALIDATE;
            memState[mreq->memnum]->stats.counts[COUNT_INVALORDNGRADESENT]++;
            memState[mreq->memnum]->stats.counts[COUNT_EXCLUSIVEONSHARED]++;
         } else { 
            CacheFakeInvalidate(i,BACKMAP_PADDR(mreq->addr,i),SCACHE_LINE_SIZE);
         }
         ASSERT(!IsInWBBuffer(i, mreq->addr));
      }
      NakUpgrades(mreq);
      break;
   case MEMSYS_WRITEBACK:
      memState[mreq->memnum]->stats.buCounts[BUC_BUS_WB] += arbitrationCycles + transferCycles;
      /* just some sanity checks */
      for (i = FIRST_CPU(machine); i < LAST_CPU(machine); i++) {
         if (i == mreq->cpunum) continue;
         ASSERT(!IsInSCache(i, BACKMAP_PADDR(mreq->addr,i), MEMSYS_EXCLUSIVE, &data, &way));
         ASSERT(!IsInSCache(i, BACKMAP_PADDR(mreq->addr,i), MEMSYS_SHARED, &data, &way));
         ASSERT(!IsInWBBuffer(i, mreq->addr));
      }
      break;
   default:
      CPUError("Bad mreq->cmd (0x%x)\n", mreq->cmd);
   }

   if (cacheToCache) {
      if (debugMem)
         CPUPrint("DBGBSU %lld %d cacheToCache addr(0x%x)\n",
                  CPUVec.CycleCount(0), mreq->cpunum, mreq->addr);
      mreq->state = CACHE_TRANSFER_WAIT;
      mreq->result |= MEMSYS_RESULT_CACHE|MEMSYS_RESULT_DOWNGRADE;
      memState[mreq->memnum]->stats.counts[COUNT_REMOTEDIRTY]++;
      memState[mreq->memnum]->stats.counts[COUNT_INVALORDNGRADESENT]++;
      EventDoCallback(FIRST_CPU(mreq->machnum), CacheTransferDone, (EventCallbackHdr *) mreq, NULL, memoryCycles + dirtyPenalty);
   } else if ((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_UPGRADE) {
      mreq->result |= MEMSYS_RESULT_MEMORY;	/* doesn't really make sense to set this for upgrades,
                                                   but scache wants it set */
      CPUArrive(mreq);
   } else {
      mreq->state = MEM_BUSY_WAIT;
      mreq->result |= MEMSYS_RESULT_MEMORY;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&memState[mreq->memnum]->memoryQueue));
      mreq->memQEnter = CPUVec.CycleCount(mreq->cpunum);

      if (!memState[mreq->memnum]->busy)
         MemoryArrive(mreq->memnum);
   }
}

/* Bus transfer has finished, so send request to proper place (CPU or memory),
 * and setup the next arbitration if there's something in the queues
 */
static void
BusFree(int cpuNum, EventCallbackHdr *hdr, void *arg)
{
   MemRequest *mreq = (MemRequest *)hdr;
   ASSERT(M_FROM_CPU(cpuNum) == mreq->machnum);
   
   /* Send request to proper place */
   if (mreq->state == BUS_TRANSFER_WAIT) {
      CacheSnoop(mreq);
   } else {
      ASSERT(mreq->state == REPLY_BUS_TRANSFER_WAIT);
      CPUArrive(mreq);
   }

   if (busIdleStart[mreq->machnum]) {
      memState[FIRST_MEMORY(mreq->machnum)]->stats.buCounts[BUC_BUS_IDLE] +=
          CPUVec.CycleCount(0) - busIdleStart[mreq->machnum] -
          (arbitrationCycles + transferCycles);
      busIdleStart[mreq->machnum] = 0;
   }

   /* Setup next arbitration */
   if (!List_IsEmpty(&highPri[mreq->machnum]) ||
       !List_IsEmpty(&lowPri[mreq->machnum])) {
      EventDoCallback(FIRST_CPU(mreq->machnum), ArbitrateCallback, (EventCallbackHdr *) &arbitrate[mreq->machnum], NULL, arbitrationCycles);
   } else {
      busBusy[mreq->machnum] = 0;
      busIdleStart[mreq->machnum] = CPUVec.CycleCount(0);
   }
}

/* Arbitration cycles are finished, now decide the winner by first checking
 * the high priority queue, and then the low priority queue.
 */
static void
ArbitrateCallback(int cpuNum, EventCallbackHdr *hdr, void *arg)
{
   List_Links *itemPtr;
   MemRequest *mreq;
   int machine = M_FROM_CPU(cpuNum);

   if (!List_IsEmpty(&highPri[machine])) {
      itemPtr = List_First(&highPri[machine]);
   } else if (!List_IsEmpty(&lowPri[machine])) {
      itemPtr = List_First(&lowPri[machine]);
   } else {
      /* this could happen if a CPU miss is satisfied from it's
	 own writeback buffer */
      /* Kinshuk, DT: BUT, this happens very often if you do a flush
       * followed by a prefetch exclusive (as in the SIPS code).
       * So this gets commented out for now.
       */
      /*
	CPUWarning("ArbitrateCallback called with nothing to do (time: %lld)\n",
	           CPUVec.CycleCount(cpuNum));
       */

      busBusy[machine] = 0;
      return;
   }
   List_Remove(itemPtr);

   /* now occupy the bus for the correct number of cycles */
   mreq = LIST_TO_MREQ(itemPtr);
   if (mreq->state == BUS_ARB_WAIT) {
      mreq->state = BUS_TRANSFER_WAIT;
   } else {
      ASSERT(mreq->state == REPLY_BUS_ARB_WAIT);
      mreq->state = REPLY_BUS_TRANSFER_WAIT;
      memState[mreq->memnum]->stats.buCounts[BUC_BUS_GETREPLY] += arbitrationCycles + transferCycles;
   }

   memState[mreq->memnum]->stats.buCounts[BUC_BUS_BUSY] += arbitrationCycles + transferCycles;
   EventDoCallback(FIRST_CPU(mreq->machnum), BusFree, (EventCallbackHdr *)mreq, NULL, transferCycles);
}

static void
Arbitrate(int machine)
{
   /* if arbitration callback is already set or will be once bus is free, just return */
   if (busBusy[machine])
      return;
   busBusy[machine] = 1;
   EventDoCallback(FIRST_CPU(machine), ArbitrateCallback, (EventCallbackHdr *) &arbitrate[machine], NULL, arbitrationCycles);
}

/* Request just arrived from CPU to Bus interface (time to go through caches, etc) */
static void
BusArrive(int cpuNum, EventCallbackHdr *hdr, void *arg)
{
   MemRequest *mreq = (MemRequest *)hdr;
   MemRequest *wbReq;
   char *data;
   int i, way=0, requestTableFull;

   ASSERT(M_FROM_CPU(cpuNum) == mreq->machnum);
   ASSERT(mreq->state == CPU_TO_BUS_OVERHEAD);

   /* if this request is for a bogus address, bus error it immediately */
   if (!IS_VALID_PA(M_FROM_CPU(cpuNum), mreq->addr)) {
      ErrorRequest(mreq);
      return;
   }

#ifndef SOLO
   /* if firewall is on and cpu is trying to write, check the firewall */
   if (CPUVec.CheckFirewall) {
      int c = mreq->cmd & MEMSYS_CMDMASK;
      if ((c == MEMSYS_GETX) || (c == MEMSYS_UPGRADE)) {
         if (!CPUVec.CheckFirewall(cpuNum, mreq->addr)) {
            ErrorRequest(mreq);
            return;
         }
      }
   }
#endif 

   /* check the writeback buffer first */
   switch (mreq->cmd & MEMSYS_CMDMASK) {
   case MEMSYS_GET:
      wbReq = IsInWBBuffer(cpuNum, mreq->addr);
      if (wbReq) {
         memState[mreq->memnum]->stats.buCounts[BUC_GET_WBBUF]++;
	 /*
         CPUPrint("DBGBSU %lld GET hit in wbBuffer (0x%x)\n", CPUVec.CycleCount(0), mreq->addr);
	 */
#ifdef DATA_HANDLING
         bcopy(wbReq->data, DATA_ADDR(mreq->machnum, mreq->addr),
               SCACHE_LINE_SIZE);
#endif
	 CacheCmdDone(cpuNum, mreq->transId, mreq->mode, mreq->status,
		      MEMSYS_RESULT_MEMORY|MEMSYS_RESULT_NOTRANSITION,
		      (byte*)DATA_ADDR(mreq->machnum, mreq->addr));
         /* free req */
         mreq->state = REQ_FREE;
         List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
         return;
      }
      break;
   case MEMSYS_GETX:
      wbReq = IsInWBBuffer(cpuNum, mreq->addr);
      if (wbReq) {
         memState[mreq->memnum]->stats.buCounts[BUC_GET_WBBUF]++;
	 /*
         CPUPrint("DBGBSU %lld GETX hit in wbBuffer (0x%x)\n", CPUVec.CycleCount(0), mreq->addr);
	 */
#ifdef DATA_HANDLING
         bcopy(wbReq->data, DATA_ADDR(mreq->machnum, mreq->addr),
               SCACHE_LINE_SIZE);
#endif
         /* remove writeback entry because cache now has the most-recent data */
         FreeWBentry(wbReq);
	 CacheCmdDone(cpuNum, mreq->transId, mreq->mode, mreq->status,
		      MEMSYS_RESULT_MEMORY|MEMSYS_RESULT_NOTRANSITION,
		      (byte*)DATA_ADDR(mreq->machnum, mreq->addr));
         /* free req */
         mreq->state = REQ_FREE;
         List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
         return;
      }
      break;
   case MEMSYS_UPGRADE:
      wbReq = IsInWBBuffer(cpuNum, mreq->addr);
      if (wbReq) { 
         memState[mreq->memnum]->stats.buCounts[BUC_UPG_WBBUF]++;
         CPUPrint("DBGBSU %lld UPGRADE hit in wbBuffer (0x%x)\n", CPUVec.CycleCount(0), mreq->addr);
         /* remove writeback entry because cache now has the most-recent data */
         FreeWBentry(wbReq);
	 CacheCmdDone(cpuNum, mreq->transId, mreq->mode, mreq->status,
		      MEMSYS_RESULT_MEMORY|MEMSYS_RESULT_NOTRANSITION,
		      (byte*)DATA_ADDR(mreq->machnum, mreq->addr));

         /* free req */
         mreq->state = REQ_FREE;
         List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
         return;
      }

      /* Upgrades need to check wether that cache line is still in cache,
         It could've been invalidated by now */
      if (!IsInSCache(mreq->cpunum, BACKMAP_PADDR(mreq->addr, mreq->cpunum), MEMSYS_SHARED, &data, &way)) {
         NakRequest(mreq);
         return;
      }
      break;
   case MEMSYS_WRITEBACK:
      /* for writebacks, add to low priority queue */
      mreq->state = BUS_ARB_WAIT;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(WB_QUEUE(mreq->machnum)));
      Arbitrate(mreq->machnum);
      return;
   default:
      CPUError("Unknown memsys command (0x%x) in BusUma::BusArrive\n", mreq->cmd);
   }

   /* look for matching requests from other CPUS and merge if both CPUs issued a SHARED mode request,
      otherwise add this one to delay queue */
   requestTableFull = 1;
   for (i = 0; i < REQUEST_TABLE_SIZE; i++) {
      if (requestTable[mreq->machnum][i].used) {
         if (requestTable[mreq->machnum][i].addr == mreq->addr) {
            if ((requestTable[mreq->machnum][i].initiator->mode == MEMSYS_SHARED) &&
                (mreq->mode == MEMSYS_SHARED)) {
               RTMerge(mreq, i);
            } else if (((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_UPGRADE) &&
                       (requestTable[mreq->machnum][i].initiator->mode == MEMSYS_EXCLUSIVE)) {
               /* by the time this upgrade gets to bus, cache will have been invalidated,
                  so NAK this request */
               NakRequest(mreq);
            } else {
               RTDelay(mreq, i);
            }
            return;
         }
      } else {
         requestTableFull = 0;
      }
   }
   
   /* if request table is full and this is a get or getx, this request will end up getting
      nak'ed when it tries to insert itself in request table, so put it on queue */
   if (requestTableFull && (((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_GET) ||
                            ((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_GETX))) {
      mreq->state = RT_OVERFLOW;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&requestTableFullQ[mreq->machnum]));
      return;
   }
   mreq->state = BUS_ARB_WAIT;
   List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&highPri[mreq->machnum]));
   Arbitrate(mreq->machnum);
   return;
}


/*****************************************************************
 * MemsysCmd
 * 
 * Main interface from secondary cache into here
 * For DMA opeartions, the writeback parameter holds the
 * length of the DMA transfer and is NOT a boolean.
 *****************************************************************/
/*  xxxxx  things to do:
    make uncached operations contend for bus
    sync??
    */
Result
BusUmaCmd(int cpuNum, int cmd, PA addr, int transId, 
          PA replacedPaddr, int writeback, byte *data)
{
   MemRequest *mreq;
   List_Links *itemPtr;
   int memnum, overhead;
   int machine = M_FROM_CPU(cpuNum);

#ifndef SOLO
   addr = REMAP_PADDR(addr, cpuNum);
   replacedPaddr = REMAP_PADDR(replacedPaddr, cpuNum);
#endif 

   if (debugMem)
      CPUPrint("DBGBSU %lld CPU %d 0x%x addr 0x%x 0x%x repl 0x%x %d PC 0x%x\n",
               CPUVec.CycleCount(0), cpuNum, cmd, addr, transId, replacedPaddr, writeback,
               CPUVec.CurrentPC(cpuNum));
   if (cmd == MEMSYS_SYNC) {
      return SUCCESS;
   } 
   memnum = BusumaAddrToMemnum(machine, addr);
   
   /* for a writeback, add it to writebuffer for this CPU.
      If all the writebuffers are full, stall CPU until all the writes are flushed
      This CPU will be removed from sharer list after the writeback has been issued
      */
   if (writeback && (replacedPaddr != MEMSYS_NOADDR)) {
      int rmemnum = BusumaAddrToMemnum(machine, replacedPaddr);

      ASSERT(!(cmd & MEMSYS_DMAFLAVOR));

      if (IsInWBBuffer(cpuNum, replacedPaddr)) {
         CPUError("DBGBSU %lld WB hit in wbBuffer (0x%x)\nThe GetX or upgrade in between should've removed the first wb.\n",
                  CPUVec.CycleCount(0), replacedPaddr);
      } else if (wbBuffers[cpuNum].numUsed == WB_BUFFER_SIZE) {
         /* we just got a writeback and all writeback buffers are full,
            so store the necessary parameters in overflow buffer,
            and move one of the writebacks to high priority queue,
            and stall until an entry is free */
         List_Links *itemPtr, *nextPtr;
         MemRequest *ovfReq;

         ASSERT(List_IsEmpty(&wbBuffers[cpuNum].free));
         ASSERT(wbBuffers[cpuNum].numOverflowUsed != maxOverflow);
         itemPtr = List_First(&freeMemReqList);
         ASSERT(itemPtr);
         List_Remove(itemPtr);
         ovfReq = LIST_TO_MREQ(itemPtr);

         ovfReq->state = WB_OVERFLOW;
         ovfReq->cmd = cmd;
         ovfReq->addr = addr;
         ovfReq->transId = transId;
         /* i really shoulnd't put replacedPaddr in reqAddr, and writeback in len,
            but MemRequest is already big enough, and those two fields are wasted in overflow MemRequest */
         ovfReq->reqAddr = replacedPaddr;
         ovfReq->len = writeback;
         ovfReq->data = data;

         List_Insert(itemPtr, LIST_ATREAR(&wbBuffers[cpuNum].overflow));
         wbBuffers[cpuNum].numOverflowUsed++;

    	 if (debugMem)
            CPUPrint("DBGBSU %lld Writeback buffer full on CPU %d.\n", 
                    CPUVec.CycleCount(cpuNum), cpuNum);

         /* stall => move the first entry from lowPri to highPri */
         for (itemPtr = List_First(WB_QUEUE(machine)), nextPtr = NULL;
              !List_IsAtEnd(WB_QUEUE(machine), itemPtr);
              itemPtr = nextPtr) {
            MemRequest *mreq = LIST_TO_MREQ(itemPtr);
            nextPtr = List_Next(itemPtr);
            if (mreq->cpunum == cpuNum) {
               List_Remove(itemPtr);
               List_Insert(itemPtr, LIST_ATREAR(&highPri[machine]));
               break;
            }
         }

         return STALL;
      } else {
         MemRequest *wbEntry;
         List_Links *itemPtr;
         ASSERT(!List_IsEmpty(&wbBuffers[cpuNum].free));

         itemPtr = List_First(&wbBuffers[cpuNum].free);
         List_Remove(itemPtr);
         wbBuffers[cpuNum].numUsed++;

         memState[rmemnum]->stats.counts[COUNT_WRITEBACKS]++;
         wbEntry = LIST_TO_MREQ(itemPtr);
         wbEntry->state = CPU_TO_BUS_OVERHEAD;
         wbEntry->memnum = rmemnum;
         wbEntry->machnum = machine;
         wbEntry->cpunum = cpuNum;
         wbEntry->starttime = CPUVec.CycleCount(cpuNum);
#ifdef DATA_HANDLING
         bcopy(data, wbEntry->data, SCACHE_LINE_SIZE);
#endif
         wbEntry->addr = replacedPaddr;
         EventDoCallback(cpuNum, BusArrive, (EventCallbackHdr *)wbEntry, NULL, readOverhead);
      }
   }

   /* Handle special case: a GET with transId -1 indicates
    * a writeback or repl hint without the associated GET (due
    * to a CACHE instruction executed in the processor)
    */
   if (((cmd & MEMSYS_CMDMASK) == MEMSYS_GET) && (transId == -1) &&
       !(cmd & MEMSYS_DMAFLAVOR)) {
      return SUCCESS;
   }

   
   /*
    * Got a request. Fill allocate and fill in a memrequest and
    * model the workload wait time for where it is going;
    */
   itemPtr = List_First(&freeMemReqList);
   ASSERT(itemPtr);
   List_Remove(itemPtr);
   mreq = LIST_TO_MREQ(itemPtr);

   mreq->cmd = cmd;
   mreq->transId = transId;
   mreq->reqAddr = addr;
   mreq->addr =  addr & ~(SCACHE_LINE_SIZE-1);
   mreq->memnum = memnum;
   mreq->machnum = machine;
   mreq->cpunum = cpuNum;
   mreq->starttime = CPUVec.CycleCount(cpuNum);
   mreq->rtIndex = -1;
   if( cmd & MEMSYS_DMAFLAVOR ) {
      ASSERT( transId < 0 );
      ASSERT( data );
      mreq->data = data;
      mreq->len = writeback;
   } else {
      ASSERT( transId >= 0);
      mreq->data = NULL;
   }

   switch (cmd & MEMSYS_CMDMASK) {
   case MEMSYS_GET:
      mreq->mode = MEMSYS_SHARED;
      overhead = readOverhead;
      if (cmd & MEMSYS_IFFLAVOR) {
         memState[memnum]->stats.counts[COUNT_IGETS]++;
      } else if (cmd & MEMSYS_LLFLAVOR) {
         memState[memnum]->stats.counts[COUNT_LLGETS]++;
      } else if (cmd & MEMSYS_DMAFLAVOR) {
         memState[memnum]->stats.counts[COUNT_DMAGETS]++;
      } else {         
         memState[memnum]->stats.counts[COUNT_DGETS]++;
      }
      break;
   case MEMSYS_GETX:
      mreq->mode = MEMSYS_EXCLUSIVE;
      overhead = readOverhead;
      if (cmd & MEMSYS_DMAFLAVOR) {
         memState[memnum]->stats.counts[COUNT_DMAGETXS]++;
      } else {         
         memState[memnum]->stats.counts[COUNT_GETXS]++;
      }
      break;
   case MEMSYS_UPGRADE:
      mreq->mode = MEMSYS_EXCLUSIVE;
      overhead = upgradeOverhead;
      if (cmd & MEMSYS_SCFLAVOR) {
         memState[memnum]->stats.counts[COUNT_SCUPGRADES]++;
      } else {
         memState[memnum]->stats.counts[COUNT_UPGRADES]++;
      }
      break;
   case MEMSYS_UNCWRITE: {
      Result rval;
      memState[memnum]->stats.counts[COUNT_UNCACHEDWRITES]++;
      rval = BusUmaUncachedWrite(cpuNum, addr, data, writeback);
      /* free mreq becuase it's not used */
      mreq->state = REQ_FREE;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
      return rval;
			 }
   case MEMSYS_UNCWRITE_ACCELERATED:
      memState[memnum]->stats.counts[COUNT_UNCACHEDACCWRITES]++;
      BusUmaUncachedWrite(cpuNum, addr, data, writeback);
      /* free mreq becuase it's not used */
      mreq->state = REQ_FREE;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
      return SUCCESS;
   case MEMSYS_UNCREAD: {
      Result rval;
      memState[memnum]->stats.counts[COUNT_UNCACHEDREADS]++;
      rval = BusUmaUncachedRead(cpuNum, addr, data, writeback);
      /* free mreq becuase it's not used */
      mreq->state = REQ_FREE;
      List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
      return rval;
      }
   default:
      CPUError("Unknown memsys command (0x%x) in BusUmaCmd\n", cmd);
      overhead = 0; /* Quite compiler warning message. */
   }

   /*
    * compute a bunch of values to make future routines happier.
    */
   mreq->state = CPU_TO_BUS_OVERHEAD;
   mreq->status = MEMSYS_STATUS_SUCCESS;
   mreq->result = 0;

   EventDoCallback(cpuNum, BusArrive, (EventCallbackHdr *)mreq, NULL, overhead);
   return STALL;
}

void 
BusUmaStatus(void) 
{
    char buf[1024];
    char tmpBuf[32];
    int i, memNum;

    for (memNum = 0; memNum < TOTAL_MEMORIES; memNum++) {
       sprintf(buf, "MEM %d ", memNum);
       for (i = 0; i < COUNT_TOTAL; i++) {
          sprintf(tmpBuf, LLD_SPACE, memState[memNum]->stats.counts[i]);
          strcat(buf, tmpBuf);
       }
       CPUPrint("%s\n", buf);

       sprintf(buf, "MEMBUSUMA %d ", memNum);
       for (i = 0; i < BUC_TOTAL; i++) {
          sprintf(tmpBuf, LLD_SPACE, memState[memNum]->stats.buCounts[i]);
          strcat(buf, tmpBuf);
       }
       CPUPrint("%s\n", buf);
    }
}

void 
BusUmaDone(void)
{
   CPUPrint("Exiting the BusUma memory system\n");
}


void
BusUmaDumpStats(void)
{
   BusUmaStatus();
}

static Result
BusUmaUncachedWrite(int cpuNum, PA addr, byte *data, int len)
{

#ifdef HWBCOPY
   /* For now, if the given address is a valid physical address,
    * assume that we are doing an access to the MSG space.
    * These writes are only needed in Flashlite -- punt here
    */
   if (!IS_VALID_PA(M_FROM_CPU(cpuNum), addr))
#endif
      {

#ifndef SOLO
         /* should check firewall here because flashlite also
          * checks it before calling doPio, and doPio can't
          * check because cpuNum == dest node when called from
          * flashlite.
          *
          * However things are complicated by the need to determine
          * which node addr points at, perhaps firewall writes go
          * through here (which means they should be allowed).
          * Ignore for now.
          */
         Result ret;
         ASSERT(CPUVec.UncachedPIO);
         ret = CPUVec.UncachedPIO(cpuNum, addr, 0, len, data);
         if (ret != SUCCESS) { 
            CPUError("SimMagic_DoPIO failed: cpu=%d addr=%#llx pc=%#llx \n",
                     cpuNum,addr,CPUVec.CurrentPC(cpuNum));
	    return ret;
         }
         ASSERT(ret == SUCCESS);
#endif
#ifdef SOLO
         bcopy(data, (char *)addr, len); 
#endif
#ifdef DEBUG_MEM
         {
            int foo;
            bcopy(data, &foo, 4);
            CPUPrint("Uncached write (%d bytes) to 0x%x of 0x%x\n", 
                     len, addr, foo);
         }
#endif /* DEBUG_MEM */
      }
      return SUCCESS;
}

static Result
BusUmaUncachedRead(int cpuNum, PA addr, byte *data, int len)
{
#ifdef SOLO
         bcopy(data, (char *)addr, len); 
#else
         Result ret;
         ASSERT(CPUVec.UncachedPIO);
         ret = CPUVec.UncachedPIO(cpuNum, addr, 1, len, data);
         if (ret != SUCCESS) { 
            CPUWarning("SimMagic_DoPIO failed: cpu=%d addr=%#llx pc=%#llx \n",
                     cpuNum,addr,CPUVec.CurrentPC(cpuNum));
	    return BUSERROR;
         }
         ASSERT(ret == SUCCESS);
#endif

#ifdef DEBUG_MEM
   {  
      int foo;
      bcopy(data, &foo, 4);
      CPUPrint("Uncached read (%d bytes) to 0x%x of 0x%x\n", len, addr, foo);
   }
#endif /* DEBUG_MEM */
   return SUCCESS;
}

/* if running with data handling, need to drain writebacks */
static void
BusUmaDrain(void)
{
#ifdef DATA_HANDLING
   int i, cpu;
   MemRequest *mreq;

   for (cpu = 0; cpu < TOTAL_CPUS; cpu++) {
      ASSERT(List_IsEmpty(&wbBuffers[cpu].overflow));
      if (wbBuffers[cpu].numUsed != 0) {
         for (i = 0; i < WB_BUFFER_SIZE; i++) {
            mreq = &wbBuffers[cpu].entries[i];
            switch (mreq->state) {
            case REQ_FREE:
               continue;
               break;
            case MEM_BUSY_WAIT:
               List_Remove(MREQ_TO_LIST(mreq)); /* from memoryQueue */
               /* fall through */
            case CPU_TO_BUS_OVERHEAD:
            case BUS_ARB_WAIT:
            case BUS_TRANSFER_WAIT:
               bcopy(mreq->data, DATA_ADDR(mreq->machnum, mreq->addr),
                     SCACHE_LINE_SIZE);
               FreeWBentry(mreq);
               break;
            default:
               CPUError("State %d not handled.\n", mreq->state);
            }
         }
      }
   }
#endif  /* DATA_HANDLING */
}