/*
 * 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:  numa.c 
 *
 * NUMA memory system. 
 *
 * Parameters are:
 * NUMA_BUS_TIME: fixed delay for bus/interconnect between CPU and DC
 * NUMA_PILOCAL_DC_TIME
 * NUMA_PIREMOTE_DC_TIME
 * NUMA_NILOCAL_DC_TIME
 * NUMA_NIREMOTE_DC_TIME
 * NUMA_NET_TIME: fixed delay for network transit
 * NUMA_MEM_TIME: contention based delay for access to DRAM
 * Minimum local miss time is 2*(NUMA_BUS_TIME) + (NUMA_PILOCAL_DC_TIME) + (NUMA_MEM_TIME)
 * Minimum remote miss time is 2*(NUMA_BUS_TIME)
 *              + NUMA_PIREMOTE_DC_TIME
 *              + NUMA_NILOCAL_DC_TIME
 *              + NUMA_NIREMOTE_DC_TIME
 *              + (NUMA_MEM_TIME) + 2*(NUMA_NET_TIME)
 *
 * Author: $Author: blythe $
 * Date:   $Date: 2002/05/29 01:09:11 $
 *****************************************************************/

#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"

/* 
 * Flag for memory system init to prevent repeated mallocs when switching
 */
static uint numaDoneInit = 0;  

#define NUMA_MAX_MEMORIES    64

#define PAGE_NUM(x) (x)/PAGE_SIZE
static uint numaStripeSizePages;
static uint numaStripeSizeBytes;
static uint numaStripeSizeLines;
static uint numaStripeChunk;

/*
 * Numa memsystem version of the counting code in flashlite
 * Counts, at the home, cache misses/CPU (countdown from Trigger) and write misses.
 * Things are done to mirror the flashlite counting implementation closely
 * Count misses in DirContDone for Get and GetX
 * Mark writes in DirContDone for Writeback and InvalCollectAcks for sharing writebacks
 * 
 */
/* # of hot pages pending */
#define MIGREP_PEND 10
/* # of hot pages before interrupt */
#define MIGREP_PEND_INTR migRepPendIntr
int migRepPendIntr = 2;
/* value returned when no pages are left */
#define MIGREP_NULLPAGE 0xffffffff

typedef struct {
   unsigned long sampleCounter;         /* sample count frequency */
   unsigned long pendingPages[MIGREP_PEND];     /* hot pages pending */
   unsigned long pendingPagesCount;     /* number of hot pending pages */
   unsigned char *cmissCounter;         /* cache-miss counter, a byte perc CPU per page */
   unsigned char *writeCounter;         /* write counter, a bit per page */
} MigRepNodeInfo;
MigRepNodeInfo migRepInfo[NUMA_MAX_MEMORIES];   /* One per memory */

/* All variables for resetting counters */
unsigned long counterResetInterval;     /* Cycles between invocations of the reset routine */
unsigned long cmissResetIndex = 0;      /* Next cache-miss counter to reset */
unsigned long writeResetIndex = 0;      /* Next write counter to reset */
unsigned long resetWriteCounters;       /* countdown for resetting write counters */
EventCallbackHdr resetCounterCB;        /* periodic call back for resetting counters */

/* Policy parameters. Will be eventually set through tcl */
/* Sample 1:N */
#define SAMPLE_COUNT migRepSampleCount
int migRepSampleCount = 10;
/* Assuming sampling 1:10 */
int migRepTriggerThreshold = 9;
#define TRIGGER_THRESHOLD migRepTriggerThreshold
/* Reset interval in ms */
int migRepResetInterval = 500;
#define RESET_INTERVAL migRepResetInterval
/* enable counting */
int migRepEnableCounting = 0;
#define ENABLE_COUNT migRepEnableCounting
/* static kern size in pages */
int migRepMaxKern = 0;
#define MAX_KERN migRepMaxKern
/* which node to interrupt */
int migRepIntrHot = 0;
#define INTR_HOT migRepIntrHot
int migRepZeroOnWrite = 0;
#define ZERO_ON_WRITE migRepZeroOnWrite
int migRep4BitCounters = 0;
#define FOUR_BIT_COUNTERS migRep4BitCounters

#ifdef SOLO
#define NumaAddrToMemnum(_addr)  SOLO_PA_NODE(SoloDecompressAddr(0,_addr))
#define NumaAddrToMemline(_addr) (SOLO_PA_OFFSET(SoloDecompressAddr(0,_addr))/SCACHE_LINE_SIZE)
#else
#define NumaAddrToMemnum(_addr) ((_addr/numaStripeSizeBytes)%NUM_MEMORIES(0))
#define NumaAddrToMemline(_addr) (((_addr/numaStripeChunk)*numaStripeSizeLines) \
                                  + ((_addr/SCACHE_LINE_SIZE)%numaStripeSizeLines))

#endif

/*
 * Memory number that is local to this CPU
 * This is the same as the CPU, except if clustering (a la DASH)is used
 */
#define NumaLocalMem(c) ((c)*NUM_MEMORIES(0)/NUM_CPUS(0))
/* Test if cpu c is local to memory m */
#define NumaIsLocal(c, m) ((m) == NumaLocalMem(c))

#define NumaMemFirstCPU(m) ((m)*NUM_CPUS(0)/NUM_MEMORIES(0));
   
/* States for memory and invalidation requests. Helps debugging */
enum MemReqState { REQ_LOCAL_WAIT,      /* Waiting for the local bus */
                   REQ_LOCAL_DC_WAIT,   /* Waiting for the local DC */
                   REQ_NET_WAIT,        /* Sending to the remote DC */
                   REQ_REMOTE_DC_WAIT,  /* Waiting for the remote DC */
                   IN_MEM_DC,           /* In the DC (not really a wait) */
                   INVAL_WAIT,          /* Waiting for invalidates to be done */
                   MEM_WAIT,            /* Waiting to write to DRAM */
                   INVAL_LOCAL_WAIT,    /* Invalidate: waiting for local bus */
                   INVAL_NET_WAIT,      /* Invalidate: Sending to remote DC */
                   INVAL_REMOTE_DC_WAIT,        /* Invalidate: waiting for remote DC */ 
                   INVAL_REMOTE_LOCAL_WAIT,     /* Invalidate: waiting for remote bus */
                   INVAL_ACK_NET_WAIT,  /* Invalidate: Sending Ack to home */
                   INVAL_HOME_DC_WAIT,   /* Invalidate: waiting for home DC */
                   WB_MEM_WAIT,         /* Sharing writeback going to memory */
                   REPLY_NET_WAIT,      /* Sending reply to requesting DC */
                   REPLY_LOCAL_WAIT,    /* Sending reply on bus to requesting processor */
                   REPLY_LOCAL_DC_WAIT, /* Reply waiting for requesting DC */
                   ALL_DONE };

/* A memory request structure */
#define MAX_OUTSTANDING (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)))
   enum MemReqState state;
   uint dc_delay_time;
   /* Fields till here are common with the InvalRequest and should be kept that way */
   int cmd;
   int transId;
   uint reqAddr;
   uint addr;    /* Address scache aligned */
   unsigned int mode;
   PA replacedPaddr;
   int replaceWasDirty;
   int status;
   int result;   
   int memnum;
   int machnum;
   int cpunum;
   int localMemNum;
   struct DirState *dirState;
   uint starttime;
   byte *data;  /* data handling - dma */
   int len;
   int drainNeeded;
}  MemRequest;

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

/*
 * The inval structure must resemble the request structure 
 * for the first few fields, as they are mixed in DC and memory queues
 */
#define MAX_INVALS (MAX_OUTSTANDING*5)
typedef struct InvalRequest  {
   EventCallbackHdr hdr;  /* Must be first!! */
   List_Links  link; /* Must be second (after EventCallbackhdr */
#define INVAL_TO_LIST(_m) (&((_m)->link))
#define LIST_TO_INVAL(_l) ((InvalRequest *) (((char *)(_l)) - sizeof(EventCallbackHdr)))
   enum MemReqState state;
   uint dc_delay_time;
   /* Fields till here are common with the MemRequest and should be kept that way */
   int cpu;             /* CPU to be invalidated */
   MemRequest *mreq;    /* The memory request for this invalidate */
} InvalRequest;

static InvalRequest InvalRequestStorage[MAX_INVALS];
static List_Links freeInvalReqList;  /* List of available inval structures */

/*
 * Directory state for a memory line.
 */
typedef struct DirState {
   unsigned char  numsharers;  /* Number of cpus with line cached. */
   unsigned char  pending:1;   /* 1 if invalidates are pending. */
   unsigned char  dirty:1;     /* Someone has it exclusive */
   unsigned char  bitmap[(SIM_MAXCPUS+7)/8];
   unsigned char  acks;        /* inval acks pending for this directory line */
} DirState;

#define STAT_HIST_BUCKETS 100
#define DEFAULT_HIST_BUCKET_SCALE 30

typedef struct StatsHist {
   unsigned int scaledivisor;
   SimCounter sum;
   SimCounter count;
   SimCounter counts[STAT_HIST_BUCKETS];
} StatsHist;

/*
 * Stats collected per memory system.
 */
typedef struct NumaMemStats {
   SimCounter counts[COUNT_TOTAL];
   StatsHist  reqtime;                  /* latency */
} NumaStats;

/* Global Info about misses, local and remote home */
static NumaStats globalStats[2];

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

typedef struct MemState  { 
   List_Links localQueue;   /* Queue for the Directory Controller */
   List_Links memoryQueue;    /* Queue to memory */
   NumaStats stats;   
   DirState dirState[1]; /* really NUMA_MAX_BYTES_PER_MEMORY/SCACHE_LINE_SIZE */
} MemState;

static MemState *memState[NUMA_MAX_MEMORIES];

#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 void DoDCDelay(int num, MemRequest *mreq) ;
static void RequestLocal(int cpuNum, EventCallbackHdr *hdr, void *v);
static void RequestLocalDC(int num, EventCallbackHdr *hdr, void *v) ;
static void RequestNet(int cpuNum, EventCallbackHdr *hdr, void *v) ;
static void RequestRemoteDC(int num, EventCallbackHdr *hdr, void *v) ;
static void DirContEnter(int num, MemRequest *mreq) ;
static void MemContDelay(int num, MemRequest *mreq) ;
static void MemContDone(int num, EventCallbackHdr *hdr, void *v) ;
static void SharingWBDelay(int num, InvalRequest *lreq);
static void SharingWBDone(int num, EventCallbackHdr *hdr, void *v); 
static void DoInvalidates(MemRequest *mreq) ;
static void InvalRequestNet(int num, EventCallbackHdr *hdr, void *v) ;
static void InvalRemoteDC(int num, EventCallbackHdr *hdr, void *v) ;
static void InvalAckNet(int num, EventCallbackHdr *hdr, void *v) ;
static void InvalHomeDC(int num, EventCallbackHdr *hdr, void *v) ;
static void InvalCollectAcks(int num, EventCallbackHdr *hdr, void *v) ;
static void InvalRemoteAckDone(int num, EventCallbackHdr *hdr, void *v); 
static void DirContDone(int num, MemRequest *mreq) ;
static void ReplyNet(int num, EventCallbackHdr *hdr, void *v);
static void ReplyDC(int num, EventCallbackHdr *hdr, void *v);
static void SendReplyToCPU(int cpuNum, EventCallbackHdr *hdr, void *v);

static void MigRepNumaInit(void);
static void MigRepDoWriteCounter(unsigned long addr, int memnum);
static void MigRepDoCmissCounter(MemRequest *mreq);
static void migRepHotPage(unsigned long localPageNum, int cpunum, int memnum, int localmemnum);
uint64 MigRepGetHotPage(int memnum);
uint64 MigRepGetInfo(unsigned long addr, int memnum, 
                                 unsigned long countType, unsigned long countAddr );
void MigRepSetInfo(unsigned long addr, int memnum, uint64 val,
                   unsigned long countType, unsigned long countAddr );
static void MigRepPeriodic(int cpuNum, EventCallbackHdr *hdr, void *v);

void NumaInit(void);
Result NumaCmd(int cpuNum, int cmd, PA addr, 
               int transId, PA replacedPaddr, int writeback, byte *data);
void NumaDone(void);
void NumaDumpStats(void);
void NumaStatus(void);
void NumaDrain(void);


/* Increment a histogram structure */
static void 
StatsIncHist(StatsHist *s, uint value)
{
   uint bucket;
   if (s->scaledivisor == 0) {
      bucket = value / DEFAULT_HIST_BUCKET_SCALE;
   } else { 
      bucket = value / s->scaledivisor;
   }
   if (bucket > STAT_HIST_BUCKETS-1) {
      bucket = STAT_HIST_BUCKETS-1;
   }
   s->counts[bucket]++;
   s->sum += value;
   s->count++;
}


/* increment a stat bucket in the memory and local/remote home structures */
static void
StatsInc(int bucket, MemRequest *mreq, int i)
{
   MemState *mState = memState[mreq->memnum];
   int isLocal = NumaIsLocal(mreq->cpunum, mreq->memnum) ? 1 : 0;

   mState->stats.counts[bucket] += i;
   globalStats[isLocal].counts[bucket] += i;
}



#ifndef SOLO

/*****************************************************************
 * remap region support 
 *****************************************************************/

static PA backmapMask;
static PA nodeaddrMask;

static void
NumaUpdateBackmapMask(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;
   backmapMask = nodeaddrMask;
   for (i=0; i<TOTAL_CPUS; i++) {
      if (remapVec->RemapEnable[i]) {
	 backmapMask &= remapVec->RemapMask[i];
      }
   }
}

static void
NumaInitRemap(void)
{
   int i;

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

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

      }
      nodeaddrMask &= ~remapVec->NodeAddr[i];
   }
   remapVec->NodeAddrInitialized = 1;

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

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

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

static PA
NumaGetNodeAddress(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)			                   \
     || !remapVec->RemapEnable[cpunum])                             \
    ? paddr : ReverseRemap(paddr, cpunum))

#endif

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


/*****************************************************************
 * DirIsASharer
 * Check if the cpunum is a sharer
 *****************************************************************/
static int
DirIsASharer(DirState *dirState, int cpunum)
{
   return (dirState->bitmap[cpunum/8] & (1 << (cpunum % 8)));
}

/*****************************************************************
 * DirSetASharer
 *
 * Add a cpu to the list of processors sharing a cache line
 *****************************************************************/
static void
DirSetASharer(DirState *dirState, int cpunum, int exclusive)
{
   if (!DirIsASharer(dirState, cpunum)) { 
      dirState->numsharers++;
      dirState->bitmap[cpunum/8] |= (1 << (cpunum % 8));
   }
   dirState->dirty = exclusive;
   if (exclusive && (dirState->numsharers != 1)) {
      CPUError("Directory protocol screwup\n");
   }
}


/*****************************************************************
 * DirClearASharer
 *
 * Remove a processor from the list of cache line sharers
 *****************************************************************/
static void
DirClearASharer(DirState *dirState, int cpunum)
{
   if (!DirIsASharer(dirState, cpunum))
      return;
   dirState->numsharers--;
   dirState->bitmap[cpunum/8] &= ~(1 << (cpunum % 8));
   if (dirState->numsharers == 0) 
      dirState->dirty = 0;
}



/********  NUMA STATE MACHINE ROUTINES **********/

/*
 * Queue up for the memory controller
 */ 
static void
DoDCDelay(int num, MemRequest *mreq) 
{
   MemState  *mState = memState[num];

   ASSERT((mreq->dc_delay_time == NUMA_PILOCAL_DC_TIME)
          || (mreq->dc_delay_time == NUMA_PIREMOTE_DC_TIME)
          || (mreq->dc_delay_time == NUMA_NILOCAL_DC_TIME)
          || (mreq->dc_delay_time == NUMA_NIREMOTE_DC_TIME));
   
   if(List_IsEmpty(&mState->localQueue)) {
      EventDoCallback(num, mreq->hdr.rout, 
                      (EventCallbackHdr *) mreq, 
                      0, mreq->dc_delay_time);
   }
   List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&mState->localQueue));
}


/* 
 * Called after the fixed local delay for a request
 * Will queue for the local directory controller
 */
static void
RequestLocal(int cpuNum, EventCallbackHdr *hdr, void *v) 
{
   MemRequest *mreq = (MemRequest *)hdr;

   mreq->state = REQ_LOCAL_DC_WAIT;
   mreq->hdr.rout = RequestLocalDC;

   if (mreq->memnum == mreq->localMemNum) {
      mreq->dc_delay_time = NUMA_PILOCAL_DC_TIME;
   } else {
      mreq->dc_delay_time = NUMA_PIREMOTE_DC_TIME;
   }
   
   DoDCDelay(mreq->localMemNum, mreq);
}


/* 
 * Called after the queued local DC delay for a request is done
 * Will check if the request needs to go remote 
 * and send to the appropriate  directory controller
 */
static void
RequestLocalDC(int num, EventCallbackHdr *hdr, void *v) 
{
   MemRequest *mreq = (MemRequest *)hdr;
   MemState  *mState = memState[num];

   /* 
    * Remove request from list and schedule next callback
    */
  List_Remove(MREQ_TO_LIST(mreq));
   if (!List_IsEmpty(&mState->localQueue)) {
      MemRequest *newReq;
      /*
       * Start the next memory request. 
       */
      newReq = LIST_TO_MREQ(List_First(&(mState->localQueue)));
      EventDoCallback(num, newReq->hdr.rout, (EventCallbackHdr *) newReq, 0,
                      newReq->dc_delay_time);
   } 

   /* Send to the directory controller, with net delay if remote */
   if (mreq->memnum == mreq->localMemNum) {
      DirContEnter(mreq->memnum, mreq);
   } else {
      mreq->state = REQ_NET_WAIT;
      EventDoCallback(mreq->cpunum, RequestNet, 
                      (EventCallbackHdr *) mreq, 
                      0, NUMA_NET_TIME);
   }
}




/* 
 * Called after the fixed net delay for a request is done
 * Now queue for the destination (remote) DC
 */
static void
RequestNet(int cpuNum, EventCallbackHdr *hdr, void *v) 
{
   MemRequest *mreq = (MemRequest *)hdr;

   mreq->state = REQ_REMOTE_DC_WAIT;
   mreq->hdr.rout = RequestRemoteDC;
   mreq->dc_delay_time = NUMA_NILOCAL_DC_TIME;
   
   DoDCDelay(mreq->memnum, mreq);

}



/* 
 * Called after the queued remote DC delay for a request
 * Will send to the  directory controller
 */
static void
RequestRemoteDC(int num, EventCallbackHdr *hdr, void *v) 
{
   MemRequest *mreq = (MemRequest *)hdr;
   MemState  *mState = memState[num];

   /* 
    * Remove request from list and schedule next callback
    */
  List_Remove(MREQ_TO_LIST(mreq));
   if (!List_IsEmpty(&mState->localQueue)) {
      MemRequest *newReq;
      /*
       * Start the next memory request. 
       */
      newReq = LIST_TO_MREQ(List_First(&(mState->localQueue)));
      EventDoCallback(num, newReq->hdr.rout, (EventCallbackHdr *) newReq, 0,
                      newReq->dc_delay_time);
   } 

   /* Send to the directory controller */
   DirContEnter(mreq->memnum, mreq);
}


/*
 * Make the decision on where to get the data from or NAK
 * If uncached op, next step memory
 * If Pending set, this request will be NAKed
 * If !pending and clean with not cached, next step memory
 * If !pending and shared and GET, next step memory
 * If !pending and shared and GETX,next step invalidate 
 *    (memory access overlaps, and is not modelled)
 * If !pending and dirty and GET, next step downgrade
 * If !pending and dirty and GETX, next step invalidate
 */
static void
DirContEnter(int num, MemRequest *mreq) 
{
   DirState *dirState = mreq->dirState;
   int nextop;
#define NEXTOP_MEM 1
#define NEXTOP_INV 2
#define NEXTOP_NAK 3
#define NEXTOP_NONE 4

   mreq->state = IN_MEM_DC;

   /* Decide the next operation based on request type and state of
      the directory, and change the result status if necessary */
   switch (mreq->cmd & MEMSYS_CMDMASK) {
   case MEMSYS_GET:
      if (dirState->pending) {
         nextop = NEXTOP_NAK;
      } else if (dirState->dirty) {
         StatsInc(COUNT_REMOTEDIRTY, mreq, 1);
         nextop = NEXTOP_INV;
         mreq->result = MEMSYS_RESULT_CACHE|MEMSYS_RESULT_DOWNGRADE;
         ASSERT(!dirState->pending);
         dirState->pending = 1;
      } else {
         nextop = NEXTOP_MEM;
         ASSERT(!dirState->pending);
         dirState->pending = 1;
      }
      break;

   case MEMSYS_GETX:
      if (dirState->pending) {
         nextop = NEXTOP_NAK;
      } else if (dirState->numsharers > 0){
         nextop = NEXTOP_INV;
         if (dirState->dirty) {
            StatsInc(COUNT_REMOTEDIRTY, mreq, 1);
            mreq->result = MEMSYS_RESULT_INVALIDATE|MEMSYS_RESULT_CACHE;
         } else {
            StatsInc(COUNT_EXCLUSIVEONSHARED, mreq, 1);
            mreq->result = MEMSYS_RESULT_INVALIDATE|MEMSYS_RESULT_MEMORY;
         }
         ASSERT(!dirState->pending);
         dirState->pending = 1;
      } else {
         nextop = NEXTOP_MEM;
         ASSERT(!dirState->pending);
         dirState->pending = 1;
      }
      break;

   case MEMSYS_UPGRADE:
      if (dirState->pending) {
         nextop = NEXTOP_NAK;
      } else if (!DirIsASharer(dirState, mreq->cpunum)) {
         /* 
          * this is required because inval acks have no delay 
          * therfore the directory can remove the sharer from the list
          * after the upgrade is issued. NAK will cause retry as GETX.
          */
         nextop = NEXTOP_NAK;
      } else if (dirState->numsharers > 1){
         StatsInc(COUNT_EXCLUSIVEONSHARED, mreq, 1);
         nextop = NEXTOP_INV;
         mreq->result = MEMSYS_RESULT_INVALIDATE|MEMSYS_RESULT_MEMORY;
         ASSERT(!dirState->pending);
         dirState->pending = 1;
      } else {
         nextop = NEXTOP_NONE;
      }
      break;

   case MEMSYS_UNCWRITE:
   case MEMSYS_UNCWRITE_ACCELERATED:
   case MEMSYS_UNCREAD:
      nextop = NEXTOP_MEM;
      break;

   case MEMSYS_WRITEBACK:
      nextop = NEXTOP_MEM;
      break;
         
   case MEMSYS_REPLACEMENT_HINT:
      nextop = NEXTOP_NONE;
      break;
         
   default:
      CPUError("Unknown memsys command (0x%x) in UmaCmd\n", mreq->cmd);
      nextop = NEXTOP_NONE; /* Quite compiler warning message */
   }

   /* Forward the request based on the next operation */
   switch (nextop) {
   case NEXTOP_NAK:
      mreq->status = MEMSYS_STATUS_NAK;
      StatsInc(COUNT_NAKS, mreq, 1);
      DirContDone(mreq->memnum, mreq);
      break;

   case NEXTOP_MEM:
      StatsInc(COUNT_MEMORYACCESS, mreq, 1);
      mreq->hdr.rout = MemContDone;
      MemContDelay(mreq->memnum, mreq);
      break;

   case NEXTOP_INV:
      DoInvalidates(mreq);
      break;

   case NEXTOP_NONE:
      DirContDone(mreq->memnum, mreq);
      break;

   }

   return;
}


/* Queue up for the memory controller */
static void
MemContDelay(int num, MemRequest *mreq) 
{
   MemState  *mState = memState[num];

   mreq->state = MEM_WAIT;
   if(List_IsEmpty(&mState->memoryQueue)) {
      EventDoCallback(num, mreq->hdr.rout, 
                      (EventCallbackHdr *) mreq, 
                      0, NUMA_MEM_TIME);
   }
   List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&mState->memoryQueue));

}


/* Memory controller delay done */
static void
MemContDone(int num, EventCallbackHdr *hdr, void *v) 
{
   MemRequest *mreq = (MemRequest *)hdr;
   MemState  *mState = memState[num];

   /* 
    * Remove request from list and schedule next callback
    */
   List_Remove(MREQ_TO_LIST(mreq));
   if (!List_IsEmpty(&mState->memoryQueue)) {
      MemRequest *newReq;
      /*
       * Start the next memory request. 
       */
      newReq = LIST_TO_MREQ(List_First(&(mState->memoryQueue)));
      EventDoCallback(num, newReq->hdr.rout, (EventCallbackHdr *) newReq, 0,
                      NUMA_MEM_TIME);
   }

   DirContDone(mreq->memnum, mreq);
   
}



/* Sharing writebacks queue up for the memory controller */
static void
SharingWBDelay(int num, InvalRequest *lreq) 
{
   MemState  *mState = memState[num];

   lreq->state = WB_MEM_WAIT;
   if(List_IsEmpty(&mState->memoryQueue)) {
      EventDoCallback(num, lreq->hdr.rout, 
                      (EventCallbackHdr *) lreq, 
                      0, NUMA_MEM_TIME);
   }
   List_Insert(INVAL_TO_LIST(lreq), LIST_ATREAR(&mState->memoryQueue));

}


/* Memory controller delay done for sharing writebacks */
static void
SharingWBDone(int num, EventCallbackHdr *hdr, void *v) 
{
   InvalRequest *lreq = (InvalRequest *)hdr;
   MemState  *mState = memState[num];

   /* 
    * Remove request from list and schedule next callback
    */
   List_Remove(INVAL_TO_LIST(lreq));
   if (!List_IsEmpty(&mState->memoryQueue)) {
      InvalRequest *newReq;
      /*
       * Start the next memory request. 
       */
      newReq = LIST_TO_INVAL(List_First(&(mState->memoryQueue)));
      EventDoCallback(num, newReq->hdr.rout, (EventCallbackHdr *) newReq, 0,
                      NUMA_MEM_TIME);
   }

   /* Sharing writeback done. Release the structure at this point */
   lreq->state = ALL_DONE;
   List_Insert(INVAL_TO_LIST(lreq), LIST_ATREAR(&freeInvalReqList));
}



/* 
 * Send the required invalidates or downgrades 
 * Local invalidates have only a local delay
 * Remote invalidates have a net + dc + local delay
 */
static void
DoInvalidates(MemRequest *mreq) 
{
   DirState *dirState = mreq->dirState;
   int i;
   List_Links *itemPtr;
   InvalRequest *lreq;

   dirState->acks = 0;
   mreq->state = INVAL_WAIT;
   
   for (i = 0; i < TOTAL_CPUS; i++) {
      if (i == mreq->cpunum && mreq->transId>=0) {
         /* Requesting CPU */
         dirState->acks++;
      } else if (!DirIsASharer(dirState, i)) {
         /* 
          * Not a sharer
          * MemStat must still know of invalidations
          */
         CacheFakeInvalidate(i, BACKMAP_PADDR(mreq->addr, i), SCACHE_LINE_SIZE);
         dirState->acks++;
      } else {
         itemPtr = List_First(&freeInvalReqList);
         ASSERT(itemPtr != &freeInvalReqList);
         List_Remove(itemPtr);
         lreq = LIST_TO_INVAL(itemPtr);
         lreq->cpu = i;
         lreq->mreq = mreq;

         if (NumaLocalMem(i) != mreq->memnum) {
            /* CPU to be invalidated is remote */
            lreq->state = INVAL_NET_WAIT;
            EventDoCallback(mreq->cpunum, InvalRequestNet, (EventCallbackHdr *) lreq, 0,
                            NUMA_NET_TIME);
         } else {
            /* CPU to be invalidated is local */
            lreq->state = INVAL_LOCAL_WAIT;
            EventDoCallback(mreq->cpunum, InvalCollectAcks, (EventCallbackHdr *) lreq, 0,
                            NUMA_BUS_TIME);
         }
      }
   }
   StatsInc(COUNT_INVALORDNGRADESENT, mreq, (TOTAL_CPUS - dirState->acks));

   /* Make sure that there is at least 1 outstanding inval */
   ASSERT(dirState->acks != TOTAL_CPUS);
}
   
 
/* 
 * net delay done for invalidations that go remote
 * next step is the DC delay
 */
static void
InvalRequestNet(int num, EventCallbackHdr *hdr, void *v) 
{
   InvalRequest *lreq = (InvalRequest *)hdr;
   int memnum = NumaLocalMem(lreq->cpu);
   MemState  *mState = memState[memnum];

   lreq->hdr.rout = InvalRemoteDC;
   lreq->state = INVAL_REMOTE_DC_WAIT;
   lreq->dc_delay_time = NUMA_NILOCAL_DC_TIME;
   if(List_IsEmpty(&mState->localQueue)) {
      EventDoCallback(memnum, lreq->hdr.rout, 
                      (EventCallbackHdr *) lreq, 
                      0, lreq->dc_delay_time);
   }
   List_Insert(INVAL_TO_LIST(lreq), LIST_ATREAR(&mState->localQueue));
}
   

/* 
 * DC delay done for remote invals
 * Next do a local delay
 */
static void
InvalRemoteDC(int num, EventCallbackHdr *hdr, void *v) 
{
   InvalRequest *lreq = (InvalRequest *)hdr;
   int memnum = NumaLocalMem(lreq->cpu);
   MemState  *mState = memState[memnum];

   /* 
    * Remove request from list and schedule next callback
    */
   List_Remove(INVAL_TO_LIST(lreq));
   if (!List_IsEmpty(&mState->localQueue)) {
      InvalRequest *newReq;
      /*
       * Start the next memory request. 
       */
      newReq = LIST_TO_INVAL(List_First(&(mState->localQueue)));
      EventDoCallback(num, newReq->hdr.rout, (EventCallbackHdr *) newReq, 0,
                      lreq->dc_delay_time);
   }


   lreq->state = INVAL_REMOTE_LOCAL_WAIT;
   EventDoCallback(num, InvalAckNet, (EventCallbackHdr *) lreq, 0,
                      NUMA_BUS_TIME);
  
}

/*
 * Cache has been invalidated. Now send the ack to home
 */
static void
InvalAckNet(int num, EventCallbackHdr *hdr, void *v) 
{
   InvalRequest *lreq = (InvalRequest *)hdr;

   lreq->state = INVAL_ACK_NET_WAIT;
   EventDoCallback(num, InvalHomeDC, (EventCallbackHdr *) lreq, 0,
                      NUMA_NET_TIME);
}


/*
 * Do a DC delay for the inval acks returning to the home DC
 */
static void
InvalHomeDC(int num, EventCallbackHdr *hdr, void *v) 
{
   InvalRequest *lreq = (InvalRequest *)hdr;
   int memnum = lreq->mreq->memnum;
   MemState  *mState = memState[memnum];

   lreq->hdr.rout = InvalRemoteAckDone;
   lreq->state = INVAL_HOME_DC_WAIT;
   lreq->dc_delay_time = NUMA_NIREMOTE_DC_TIME;
   if(List_IsEmpty(&mState->localQueue)) {
      EventDoCallback(memnum, lreq->hdr.rout, 
                      (EventCallbackHdr *) lreq, 
                      0, lreq->dc_delay_time);
   }
   List_Insert(INVAL_TO_LIST(lreq), LIST_ATREAR(&mState->localQueue));
}



/* 
 * Remote ack received. Schedule next callback in DC queue
 * and pass this one on to InvalCollectAcks
 */
static void
InvalRemoteAckDone(int num, EventCallbackHdr *hdr, void *v) 
{

   InvalRequest *lreq = (InvalRequest *)hdr;
   int memnum = lreq->mreq->memnum;
   MemState  *mState = memState[memnum];

   /* 
    * Remove request from list and schedule next callback
    */
   List_Remove(INVAL_TO_LIST(lreq));
   if (!List_IsEmpty(&mState->localQueue)) {
      InvalRequest *newReq;
      /*
       * Start the next memory request. 
       */
      newReq = LIST_TO_INVAL(List_First(&(mState->localQueue)));
      EventDoCallback(num, newReq->hdr.rout, (EventCallbackHdr *) newReq, 0,
                      newReq->dc_delay_time);
   }

   InvalCollectAcks(memnum, (EventCallbackHdr *)lreq, 0);

}

/*
 * Invalidation acks for a cache line are counted here
 * When they are all received, we move on.
 * The invals could have crossed writebacks along the way.
 * If this happens, the request is NAKed.
 */
static void
InvalCollectAcks(int num, EventCallbackHdr *hdr, void *v) 
{
   InvalRequest *lreq = (InvalRequest *)hdr;
   int invalCpu = lreq->cpu;
   MemRequest *mreq = lreq->mreq;
   DirState *dirState = mreq->dirState;
   byte *data;
   unsigned wbNeeded = dirState->dirty;
   int wasDirty;

   
   data = (byte*) DATA_ADDR(mreq->machnum, mreq->addr);
   /* 
    * The following check should actually be done at the remote DC, 
    * But since we have the pending flag on the directory controller,
    * it should not matter. This does increase the window for the Inval
    * to cross the writeback.
    */

   if (mreq->mode == MEMSYS_EXCLUSIVE) { 
      if (CacheExtract(invalCpu, 
                       BACKMAP_PADDR(mreq->addr, invalCpu), 
                       SCACHE_LINE_SIZE, &wasDirty, data)) {
         /* Clear only if successful */
         DirClearASharer(dirState,invalCpu); 
      } else {
         wbNeeded = 0;
         /* Writeback or replacement hint in flight, NAK this request */
         mreq->status = MEMSYS_STATUS_NAK;
         StatsInc(COUNT_NAKS, mreq, 1);
      }
   } else {
      if (CacheWriteback(invalCpu, 
                         BACKMAP_PADDR(mreq->addr, invalCpu), 
                         SCACHE_LINE_SIZE, data)) {
         /* 
          * This line could have been replaced while we were waiting for the ack
          * Set it to be a sharer only if the return values says so
          */
         DirSetASharer(dirState,invalCpu,0); 
      } else {
          wbNeeded = 0;
          /* Writeback in flight, NAK this request */
          mreq->status = MEMSYS_STATUS_NAK;
          StatsInc(COUNT_NAKS, mreq, 1);
      }
   }

   if (wbNeeded) {
      /* need a sharing writeback to memory. Use the current Inval structure */
      lreq->hdr.rout = SharingWBDone;
      SharingWBDelay(mreq->memnum, lreq);
      if (ENABLE_COUNT)
         MigRepDoWriteCounter(mreq->reqAddr, mreq->memnum);
   } else {
      /* Put this inval structure back */
      lreq->state = ALL_DONE;
      List_Insert(INVAL_TO_LIST(lreq), LIST_ATREAR(&freeInvalReqList));
   }

   if (++(dirState->acks) == TOTAL_CPUS) {
      /* all acks are in, go to the next step */
      mreq->state = IN_MEM_DC;
      if (mreq->status == MEMSYS_STATUS_NAK) {
         /* this one got NAKed during inval, turn off the pending bit */
         mreq->dirState->pending = 0;
      }
      DirContDone(mreq->memnum, mreq);
   }
}


/*
 * All directory processing is over at this point
 * Send reply, local or remote
 */
static void
DirContDone(int num, MemRequest *mreq) 
{
   DirState *dirState = mreq->dirState;

   /*
    * DMA Data handling
    */
   if( mreq->cmd&MEMSYS_DMAFLAVOR ) { 
      byte *memAddr = (byte*)DATA_ADDR(mreq->machnum, mreq->reqAddr);
      if( mreq->cmd&MEMSYS_GETX ) {
         bcopy(mreq->data,memAddr,mreq->len);
      } else { 
         bcopy(memAddr,mreq->data,mreq->len);
      }
   }
   
   /* Update directory state */
   if (mreq->status != MEMSYS_STATUS_NAK) { 
      switch (mreq->cmd & MEMSYS_CMDMASK) {
      case MEMSYS_GET:
         dirState->pending = 0;
         if (!(mreq->cmd&MEMSYS_DMAFLAVOR)) {
            DirSetASharer(dirState, mreq->cpunum, 0);
         }
         if (ENABLE_COUNT)
            MigRepDoCmissCounter(mreq);
         break;

      case MEMSYS_GETX:
      case MEMSYS_UPGRADE:
         dirState->pending = 0;
         if (!(mreq->cmd&MEMSYS_DMAFLAVOR)) {
            DirSetASharer(dirState, mreq->cpunum, 1);
         }
         if (ENABLE_COUNT)
            MigRepDoCmissCounter(mreq);
         break;

      case MEMSYS_UNCWRITE:
      case MEMSYS_UNCWRITE_ACCELERATED:
      case MEMSYS_UNCREAD:
         break;

      case MEMSYS_WRITEBACK:
         /*
          * End of the road
          * update memory if data handling
          */
         if (mreq->data) { 
            byte *memAddr = (byte*)DATA_ADDR(mreq->machnum, mreq->replacedPaddr);
            bcopy(mreq->data, memAddr, SCACHE_LINE_SIZE);
            free(mreq->data);
         }
         DirClearASharer(dirState, mreq->cpunum);
         List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
         mreq->drainNeeded = 0;
#ifdef MIG_REP_WBACK
         if (ENABLE_COUNT)
            MigRepDoWriteCounter(mreq->replacedPaddr, mreq->memnum);
#endif         
         return;

      case MEMSYS_REPLACEMENT_HINT:
         /*
          * End of the road
          */
         DirClearASharer(dirState, mreq->cpunum);
         List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));
         mreq->drainNeeded = 0;
         return;

      default:
         CPUError("Unknown memsys command (0x%x) in UmaCmd\n", mreq->cmd);
      }
   }

   /* Send this one on its way */
   if (mreq->memnum == mreq->localMemNum) {
      mreq->state = REPLY_LOCAL_WAIT;
      EventDoCallback(mreq->cpunum, SendReplyToCPU, 
                      (EventCallbackHdr *) mreq, 
                      0, NUMA_BUS_TIME);
   } else {
      mreq->state = REPLY_NET_WAIT;
      EventDoCallback(mreq->cpunum, ReplyNet, 
                      (EventCallbackHdr *) mreq, 
                      0, NUMA_NET_TIME);
   }
}

/*
 * Network delay done for the reply
 * Send it to the requesting DC
 */
static void
ReplyNet(int num, EventCallbackHdr *hdr, void *v)
{
   MemRequest *mreq = (MemRequest *)hdr;

   mreq->hdr.rout = ReplyDC;
   mreq->state = REPLY_LOCAL_DC_WAIT;
   mreq->dc_delay_time = NUMA_NIREMOTE_DC_TIME;

   DoDCDelay(mreq->localMemNum, mreq);
}


/*
 * Requesting DC is done
 * Do a local delay
 */ 
static void
ReplyDC(int num, EventCallbackHdr *hdr, void *v)
{
   MemRequest *mreq = (MemRequest *)hdr;
   MemState  *mState = memState[mreq->localMemNum];

   /* 
    * Remove request from list and schedule next callback
    */
   List_Remove(MREQ_TO_LIST(mreq));
   if (!List_IsEmpty(&mState->localQueue)) {
      MemRequest *newReq;
      /*
       * Start the next memory request. 
       */
      newReq = LIST_TO_MREQ(List_First(&(mState->localQueue)));
      EventDoCallback(num, newReq->hdr.rout, (EventCallbackHdr *) newReq, 0,
                      newReq->dc_delay_time);
   } 

   mreq->state = REPLY_LOCAL_WAIT;
   EventDoCallback(mreq->cpunum, SendReplyToCPU, (EventCallbackHdr *) mreq, 0,
                      NUMA_BUS_TIME);
 
}


/* 
 * All done. update the caches
 */
static void
SendReplyToCPU(int cpuNum, EventCallbackHdr *hdr, void *v)
{
   MemRequest *mreq = (MemRequest *)hdr;
   MemState  *mState = memState[mreq->memnum];
   StatsHist *hist;
   int isLocal = NumaIsLocal(mreq->cpunum, mreq->memnum) ? 1 : 0;
   byte* data;
   uint difftime = CPUVec.CycleCount(mreq->cpunum) - mreq->starttime;

   /* 
    * DMA requests are not necessarily aligned!!!
    */
   if( mreq->cmd & MEMSYS_DMAFLAVOR ) {
      data = (byte*)DATA_ADDR(mreq->machnum, mreq->reqAddr);
   } else { 
      data = (byte*)DATA_ADDR(mreq->machnum, mreq->addr);
   }

   hist = &(mState->stats.reqtime);
   StatsIncHist(hist, difftime);
   hist = &(globalStats[isLocal].reqtime);
   StatsIncHist(hist, difftime);
   if (mreq->memnum != mreq->localMemNum) {
      mreq->result |= MEMSYS_RESULT_REMOTE_HOME;
   }

   if (mreq->mode == MEMSYS_UNCACHED) {
      if ((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_UNCREAD) {
         void *from = (void*)DATA_ADDR(mreq->machnum, (uint)mreq->reqAddr);
         bcopy(from, mreq->data, mreq->len);
         /* Unstall the processor */
         ASSERT(CPUVec.ReissueUncachedOp);
         CPUVec.ReissueUncachedOp(mreq->cpunum);
      } else {
         void *to = (void*)DATA_ADDR(mreq->machnum, (uint)mreq->reqAddr);
         bcopy(mreq->data, to, mreq->len);
      }         

   } else {
      CacheCmdDone(mreq->cpunum, mreq->transId, mreq->mode, mreq->status, 
                   mreq->result, data);
   }

   mreq->state = ALL_DONE;
   List_Insert(MREQ_TO_LIST(mreq), LIST_ATREAR(&freeMemReqList));

}


/* Update the stats on a new request */
static void
UpdateRequestStats(MemRequest *mreq)
{

   switch (mreq->cmd & MEMSYS_CMDMASK) {
   case MEMSYS_GET:
      if (mreq->cmd & MEMSYS_DMAFLAVOR) {
         StatsInc(COUNT_DMAGETS, mreq, 1);
      } else {
         if (mreq->cmd & MEMSYS_IFFLAVOR) {
            StatsInc(COUNT_IGETS, mreq, 1);
         } else if (mreq->cmd & MEMSYS_LLFLAVOR) {
            StatsInc(COUNT_LLGETS, mreq, 1);
         } else {
            StatsInc(COUNT_DGETS, mreq, 1);
         }

         if (mreq->replacedPaddr != MEMSYS_NOADDR) {
            if (mreq->replaceWasDirty) {
               StatsInc(COUNT_WRITEBACKS, mreq, 1);
            } else {
               StatsInc(COUNT_REPLHINTS, mreq, 1);
            }
         }
      }
      break;

   case MEMSYS_GETX:
      if (mreq->cmd & MEMSYS_DMAFLAVOR) {
         StatsInc(COUNT_DMAGETXS, mreq, 1);
      } else {
         StatsInc(COUNT_GETXS, mreq, 1);

         if (mreq->replacedPaddr != MEMSYS_NOADDR) {
            if (mreq->replaceWasDirty) {
               StatsInc(COUNT_WRITEBACKS, mreq, 1);
            } else {
               StatsInc(COUNT_REPLHINTS, mreq, 1);
            }
         }
      }
      break;

   case MEMSYS_UPGRADE:
      if (mreq->cmd & MEMSYS_SCFLAVOR) {
         StatsInc(COUNT_SCUPGRADES, mreq, 1);
      } else {
         StatsInc(COUNT_UPGRADES, mreq, 1);
      }
      break;

   case MEMSYS_UNCWRITE:
      StatsInc(COUNT_UNCACHEDWRITES, mreq, 1);
      break;

   case MEMSYS_UNCWRITE_ACCELERATED:
      StatsInc(COUNT_UNCACHEDACCWRITES, mreq, 1);
      break;
         
   case MEMSYS_UNCREAD:
      StatsInc(COUNT_UNCACHEDREADS, mreq, 1);
      break;
   
   case MEMSYS_REPLACEMENT_HINT:
      StatsInc(COUNT_REPLHINTS, mreq, 1);
      break;

   case MEMSYS_WRITEBACK:
      StatsInc(COUNT_WRITEBACKS, mreq, 1);
      break;

   default:
      CPUError("Unknown memsys command (0x%x) in UmaCmd\n", mreq->cmd);
   }
}



/*****************************************************************
 * MemsysInit
 *****************************************************************/
void 
NumaInit(void)
{
   int i;
   u_long lines_per_mem, size;

   /* 
    * Initialize the pointers to functions and delay parameters
    */
   memsysVec.type = NUMA;
   memsysVec.NoMemoryDelay = 0;
   memsysVec.MemsysCmd = NumaCmd;
   memsysVec.MemsysDumpStats = NumaDumpStats;
   memsysVec.MemsysDone = NumaDone;
   memsysVec.MemsysStatus = NumaStatus;
#ifndef SOLO
   memsysVec.MemsysDrain = NumaDrain;
   memsysVec.MemsysSetRemap = NumaSetRemap;
   memsysVec.MemsysControlRemap = NumaControlRemap;
   memsysVec.MemsysGetNodeAddress = NumaGetNodeAddress;
#endif
 
   CPUPrint("MEM num igets llgets dmagets dgets dmagetxs getxs scupgrades upgrades writebacks replhints uncachedwrites uncachedaccwrites uncachedreads invalordngradesent naks remotedirty exclusiveonshared memoryaccess misscount totlatency\n");
   /* 
    * Initialize the list of request structures
    */
   List_Init(&freeMemReqList);
   
   for (i = 0; i < MAX_OUTSTANDING; 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));
   }

   /* 
    * Initialize the list of Invalidate structures
    */
   List_Init(&freeInvalReqList);
   
   for (i = 0; i < MAX_INVALS; i++) { 
      InvalRequest *lreq = InvalRequestStorage + i;
      bzero((char *) (lreq), sizeof(InvalRequestStorage[0]));
      List_InitElement(INVAL_TO_LIST(lreq));
      List_Insert(INVAL_TO_LIST(lreq), LIST_ATREAR(&freeInvalReqList));
   }

   /*
    * Allocate and initialize the directory state for each memory,
    * the stats per memory and the overall stats.
    */
   lines_per_mem = MEM_SIZE(0) / SCACHE_LINE_SIZE;
   size = sizeof(MemState)+ (sizeof(DirState)*lines_per_mem);   

   for (i = 0; i < NUM_MEMORIES(0); i++) { 
      if (!numaDoneInit) {
         memState[i] = (MemState *) ZMALLOC(size, "memState");
      }
      ASSERT(memState[i]);
      List_Init(&memState[i]->memoryQueue);
      List_Init(&memState[i]->localQueue);
      bzero((char *) &memState[i]->dirState, sizeof(DirState)*lines_per_mem);
      bzero((char *) &memState[i]->stats, sizeof(NumaStats));      
   }
   bzero((char *) globalStats, 2*sizeof(NumaStats));
#ifndef SOLO
   NumaInitRemap();

   if (NUMA_STRIPE_SIZE < 0) {
      numaStripeSizePages = MEM_SIZE(0)/PAGE_SIZE/NUM_MEMORIES(0);
   } else {
      numaStripeSizePages = NUMA_STRIPE_SIZE;
   }
   numaStripeSizeBytes = numaStripeSizePages*PAGE_SIZE;
   numaStripeSizeLines = numaStripeSizeBytes/SCACHE_LINE_SIZE;
   numaStripeChunk = numaStripeSizeBytes*NUM_MEMORIES(0);

   ASSERT(NUMA_STRIPE_SIZE < 0);
   if (ENABLE_COUNT)
      MigRepNumaInit();
#endif
   numaDoneInit = 1;
}

/*****************************************************************
 * 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.
 *****************************************************************/

Result
NumaCmd(int cpuNum, int cmd, PA addr, int transId, 
	PA replacedPaddr, int writeback, byte *data)
{
   MemState  *mState;
   MemRequest *mreq = NULL;
   List_Links *itemPtr;
   int memnum;
   int stall = 1;

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

   if (cmd == MEMSYS_SYNC) {
      return SUCCESS;
   } 

   if ((cmd == MEMSYS_GET) && (transId == -1)) {
      /* 
       * Ugly hack for Cache instructions. Note the DMAFLAVOR also 
       * uses negative transids too. However it sets MEMSYS_DMAFLAVOR
       * Should be fixed by having MIPSY use the cmds MEMSYS_WRITEBACK/REPLHINT
       * Original comment attached:
       * 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 (writeback) {
         cmd = MEMSYS_WRITEBACK;
      } else {
         cmd = MEMSYS_REPLACEMENT_HINT;
      }
   }
  

   /* A number of cases do not need an mreq allocated */
   switch (cmd & MEMSYS_CMDMASK) {
   case MEMSYS_GET:
   case MEMSYS_GETX:
   case MEMSYS_UPGRADE:
   memnum = NumaAddrToMemnum(addr);
   mState = memState[memnum];
   /*
    * Got a request. Allocate and fill in a memrequest
    */
   itemPtr = List_First(&freeMemReqList);
   ASSERT(itemPtr != &freeMemReqList);
   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->data = data;
   mreq->len = writeback;
   if( cmd & MEMSYS_DMAFLAVOR ) {
      ASSERT( transId < 0 );
      ASSERT( data );
      mreq->replaceWasDirty  = 0;
   } else {
      mreq->replaceWasDirty = writeback;
   }
   mreq->replacedPaddr = replacedPaddr;
   mreq->status = MEMSYS_STATUS_SUCCESS;
   mreq->memnum = memnum;
   mreq->machnum = M_FROM_CPU(cpuNum);
   mreq->cpunum = cpuNum;
   mreq->localMemNum = NumaLocalMem(cpuNum);
   mreq->dirState = &mState->dirState[NumaAddrToMemline(addr)];
   mreq->result = MEMSYS_RESULT_MEMORY|MEMSYS_RESULT_NOTRANSITION;

   UpdateRequestStats(mreq);
      break;
   default:
      break;
   }

   switch (cmd & MEMSYS_CMDMASK) {
   case MEMSYS_GET:
      
      mreq->mode = MEMSYS_SHARED;
      break;

   case MEMSYS_GETX:
      mreq->mode = MEMSYS_EXCLUSIVE;
      break;

   case MEMSYS_UPGRADE:
      mreq->mode = MEMSYS_EXCLUSIVE;
      break;

   case MEMSYS_UNCWRITE:
   case MEMSYS_UNCWRITE_ACCELERATED:
      /* Currently uncached write return with no delay,
       */
      globalStats[1].counts[MEMSYS_UNCWRITE]++;
#ifndef SOLO
      {
         Result ret;
         ASSERT(CPUVec.UncachedPIO);
         ret = CPUVec.UncachedPIO(cpuNum, addr, 0, writeback, data);
         ASSERT(ret == SUCCESS);
         return SUCCESS;
      }
      
#else
      stall = 0;
      break;
#endif
   
   case MEMSYS_UNCREAD:
      /* Data handling is done in SendReplyToCPU for non-KSEG1 */
      globalStats[1].counts[MEMSYS_UNCREAD]++;
#ifndef SOLO
      {
         Result ret;
         ASSERT(CPUVec.UncachedPIO);
         ret = CPUVec.UncachedPIO(cpuNum, addr, 1, writeback, data);
         ASSERT(ret == SUCCESS);
         return SUCCESS;
      }
#else
      break;
#endif  
   case MEMSYS_WRITEBACK:
   case MEMSYS_REPLACEMENT_HINT:
      stall = 0;
      break;

   default:
      CPUError("Unknown memsys command (0x%x) for memsys Numa\n", cmd);
   }

   /*
    * Handle replacement hints and writebacks here.
    */
   if (replacedPaddr != MEMSYS_NOADDR) {
      int rmemnum = NumaAddrToMemnum(replacedPaddr);
      DirState *dir = &memState[rmemnum]->dirState[NumaAddrToMemline(replacedPaddr)];
      MemRequest *wreq;
      /*
       * Allocate and fill in a memrequest for the writeback
       */
      itemPtr = List_First(&freeMemReqList);
      ASSERT(itemPtr != &freeMemReqList);
      List_Remove(itemPtr);
      wreq = LIST_TO_MREQ(itemPtr);

      wreq->data = 0;
      if (writeback) {
         wreq->cmd = MEMSYS_WRITEBACK;
         if (data) {
            wreq->data = malloc(SCACHE_LINE_SIZE);
            bcopy(data, wreq->data, SCACHE_LINE_SIZE);
         }
      } else {
         wreq->cmd = MEMSYS_REPLACEMENT_HINT;
      }

      wreq->transId = transId;
      wreq->reqAddr = 0;
      wreq->addr =  0;
      wreq->len = 0;
      wreq->replaceWasDirty = writeback;
      wreq->replacedPaddr = replacedPaddr;
      wreq->status = MEMSYS_STATUS_SUCCESS;
      wreq->memnum = rmemnum;
      wreq->machnum = M_FROM_CPU(cpuNum);
      wreq->cpunum = cpuNum;
      wreq->localMemNum = NumaLocalMem(cpuNum);
      wreq->dirState = dir;
      wreq->result = MEMSYS_RESULT_MEMORY|MEMSYS_RESULT_NOTRANSITION;
      wreq->drainNeeded = 1;
      UpdateRequestStats(wreq);

      /* 
       * add 1 cycle to this to ensure that it does not get ahead of the original
       * request through the DC queue 
       */
      EventDoCallback(wreq->cpunum, RequestLocal, (EventCallbackHdr *) wreq, 0,
                      NUMA_BUS_TIME + 1);
   }

   if (stall) {
      /*
       * Queue us for the Local delay
       */
      mreq->starttime = CPUVec.CycleCount(mreq->cpunum);
      mreq->hdr.rout = RequestLocal;
      mreq->state = REQ_LOCAL_WAIT;
      EventDoCallback(mreq->cpunum, RequestLocal, (EventCallbackHdr *) mreq, 0,
                      NUMA_BUS_TIME);
      return STALL; 
   } else {
      return SUCCESS;
   }
}

void 
NumaDone(void)
{
   CPUPrint("Exiting the NUMA memory system\n");
}

/* Dump stats about the memory system */
void
NumaDumpStats(void)
{

   int i, j, isLocal;

   for (i = 0; i < NUM_MEMORIES(0); i++) {
      CPUPrint("MEM %d", i);
      for (j=0; j< COUNT_TOTAL; j++) {
         CPUPrint(" %lld", memState[i]->stats.counts[j]);
      }
      CPUPrint(" %lld %lld\n", memState[i]->stats.reqtime.count, memState[i]->stats.reqtime.sum);
   }

   isLocal = 1;
   CPUPrint("MEM LOCAL");
   for (j=0; j< COUNT_TOTAL; j++) {
      CPUPrint(" %lld", globalStats[isLocal].counts[j]);
   }
   CPUPrint(" %lld %lld\n", globalStats[isLocal].reqtime.count, globalStats[isLocal].reqtime.sum);
   
   isLocal = 0;
   CPUPrint("MEM REMOTE");
   for (j=0; j< COUNT_TOTAL; j++) {
      CPUPrint(" %lld", globalStats[isLocal].counts[j]);
   }
   CPUPrint(" %lld %lld\n", globalStats[isLocal].reqtime.count, globalStats[isLocal].reqtime.sum);
}


void
NumaStatus(void) 
{
   NumaDumpStats();
}


/*
 * Currently only writebacks and replacement hints need to
 * be drained. The others will cause processors to be stalled
 * and the clock will be run forward till all processors are unstalled.
 * For writebacks with data handling, the data needs to be written back.
 */
void
NumaDrain(void)
{
   int i;

   for (i = 0; i < MAX_OUTSTANDING; i++) { 
      MemRequest *mreq = MemRequestStorage + i;
      
      if (mreq->drainNeeded) {
         EventCallbackRemove((EventCallbackHdr*)mreq);
      
         if ((mreq->cmd & MEMSYS_CMDMASK) == MEMSYS_WRITEBACK) {
            if (mreq->data) { 
               byte *memAddr = (byte*)DATA_ADDR(mreq->machnum, mreq->replacedPaddr);
               bcopy(mreq->data, memAddr, SCACHE_LINE_SIZE);
               free(mreq->data);
            }
         }
      }
   }
}

/* Cache miss counting code for migration/replication */

/* 
 * Resets a cache line worth of counters every time
 * Mirrors Flashlite implementation and cache-line size (128)
 */
#define CMISS_COUNTERS_PER_CACHELINE (128/NUM_CPUS(0))
#define WRITE_COUNTERS_PER_CACHELINE (128*8)

#define MIGREP_LOCAL_PAGENUM(_a) (((_a)/PAGE_SIZE)%numaStripeSizePages)

/* Init all the structures for counting cache misses */
static void
MigRepNumaInit(void)
{
   int i, j;
   unsigned long size;

   ASSERT(NUMA_STRIPE_SIZE < 0);
   
   for(i=0; i<NUM_MEMORIES(0);i++) {
      migRepInfo[i].sampleCounter = SAMPLE_COUNT;
      for (j=0; j<MIGREP_PEND; j++) {
         migRepInfo[i].pendingPages[j] = MIGREP_NULLPAGE;
      }
      migRepInfo[i].pendingPagesCount = 0;

      if (!numaDoneInit) {
         size = numaStripeSizePages*NUM_MEMORIES(0);
         migRepInfo[i].cmissCounter = (unsigned char *) MALLOC(size, "migRep");
         size = numaStripeSizePages/8;
         migRepInfo[i].writeCounter = (unsigned char *) ZMALLOC(size, "migRep");
      }

      size = numaStripeSizePages/8;
      bzero((char *) migRepInfo[i].writeCounter, size);
      size = numaStripeSizePages*NUM_MEMORIES(0);
      for (j=0; j<size; j++) {
         migRepInfo[i].cmissCounter[j] = TRIGGER_THRESHOLD;
      }
   }

   /* calculate the period for calling the counter reset routine */
   counterResetInterval = (unsigned long)
      NanoSecsToCycles(RESET_INTERVAL*1000*1000)
      / (numaStripeSizePages/CMISS_COUNTERS_PER_CACHELINE);

   /* Init the write counter countdown variable, i.e. 1 in
      resetWriteCounters invocations */

   resetWriteCounters = WRITE_COUNTERS_PER_CACHELINE
      / CMISS_COUNTERS_PER_CACHELINE;
   /* Set up the first callback */
   bzero((char *) (&resetCounterCB), sizeof(EventCallbackHdr));
   EventDoCallback(0, MigRepPeriodic, &resetCounterCB, 0, counterResetInterval);
}


/* mark the page as written */
static void
MigRepDoWriteCounter(unsigned long addr, int memnum)
{
   unsigned long localPageNum = MIGREP_LOCAL_PAGENUM(addr);
   unsigned long cindex = localPageNum/8;
   unsigned long cbit = localPageNum % 8;

   migRepInfo[memnum].writeCounter[cindex] |= (1<<cbit);
}



/* Increment cache miss count for the page on a sampled basis */
static void
MigRepDoCmissCounter(MemRequest *mreq)
{
   int memnum = mreq->memnum;
   int cpunum = mreq->cpunum;
   int localmemnum = mreq->localMemNum;
   
   if (!(--migRepInfo[memnum].sampleCounter)) {
      unsigned long localPageNum = MIGREP_LOCAL_PAGENUM(mreq->reqAddr);
      unsigned long cindex = localPageNum*NUM_CPUS(0) + localmemnum;

      /* If GETX or UPGRADE mark it as a write */
      if ((mreq->cmd == MEMSYS_GETX) || (mreq->cmd == MEMSYS_UPGRADE)) {
         MigRepDoWriteCounter(mreq->reqAddr, memnum);
         if (ZERO_ON_WRITE) {
            int i;
            unsigned long ci;
            ASSERT(NUM_MEMORIES(0) <= 16);
            for(i=0; i<NUM_MEMORIES(0); i++) {
               if (i != localmemnum) {
                  ci = localPageNum*NUM_CPUS(0) + i;
                  migRepInfo[memnum].cmissCounter[ci] = TRIGGER_THRESHOLD;
               }
            }
         }
      }

      /* Only decrement if it has not hit the trigger */
      if(migRepInfo[memnum].cmissCounter[cindex]) {
         if(!(--migRepInfo[memnum].cmissCounter[cindex])) {
            /* This page is officially hot */
            if ((PAGE_NUM(mreq->reqAddr) > MAX_KERN) && (localmemnum != memnum)) {
               /* 
                * Interrupt only if it is not a static kernel page
                * and it is not a local page
                */
               migRepHotPage(localPageNum, cpunum, memnum, localmemnum);
            }
         }
      }

      migRepInfo[memnum].sampleCounter = SAMPLE_COUNT;
   }
}



/* Add hot page to list of pending pages and potentially interrupt the CPU */
static void
migRepHotPage(unsigned long localPageNum, int cpunum, int memnum, int localmemnum)
{
   int i, cputointr;
   unsigned long page;
   int qnode;
   
   if (INTR_HOT) {
      cputointr = cpunum;
      qnode = localmemnum;
      page = localPageNum + numaStripeSizePages*memnum;
   } else {
      cputointr = NumaMemFirstCPU(memnum);
      qnode = memnum;
      page = localPageNum;
   }
    
   for (i=0; i<MIGREP_PEND; i++) {
      if (migRepInfo[qnode].pendingPages[i] == MIGREP_NULLPAGE) {
         migRepInfo[qnode].pendingPages[i] = page;
         if (++migRepInfo[qnode].pendingPagesCount >= MIGREP_PEND_INTR) {
            /* Interrupt the CPU, enough pending pages */
            CPUVec.MigRepStart(cputointr);
         }
         break;
      } else if (migRepInfo[qnode].pendingPages[i] == page) {
         /* page already there as hot. Ignore! */
         break;
      }
   }
   if (i == MIGREP_PEND)
      CPUWarning("NUMA WARNING: pending page count exceeded on %d\n", qnode);
/*   ASSERT(i != MIGREP_PEND); */
}


/*
 * Called from the kernel through simmagic.
 * Returns a pending page or 0 if no pages
 * Resets the interrupt when all pages are gone
 */
uint64
MigRepGetHotPage(int cpunum)
{
   int i, localmemnum;
   unsigned long page;
   
   localmemnum = NumaLocalMem(cpunum);

   page = MIGREP_NULLPAGE;
   for (i=0; i<MIGREP_PEND; i++) {
      if (migRepInfo[localmemnum].pendingPages[i] != MIGREP_NULLPAGE) {
         page = migRepInfo[localmemnum].pendingPages[i];
         migRepInfo[localmemnum].pendingPages[i] = MIGREP_NULLPAGE;
         migRepInfo[localmemnum].pendingPagesCount--;
         break;
      }
   }

   if (!migRepInfo[localmemnum].pendingPagesCount) {
      /* All pages done, reset the interrupt */
      CPUVec.MigRepEnd(cpunum);
   }

   return ((uint64)page);
}


/*
 * Called from the kernel through simmagic.
 * Returns the requested counter value as int64
 * This is because flashlite does it this way as a int64
 * Bit 19 of the address (20 active bits) is used to demux cache and write counters
 * Bottom 3 bits cannot be used.
 */
uint64
MigRepGetInfo(unsigned long addr, int memnum, unsigned long countType, 
              unsigned long countAddr)
{
   int i;
   uint64 counterVal = 0;
   unsigned long bitVal;
   uint64 dummy;
   unsigned long cindex, cbit;
   unsigned char *counter;

   if (!(ENABLE_COUNT)) {
      return ((uint64) 0);
   }

   if (countType) {
      /* Write counter */
      cindex = countAddr/8;
      cbit = countAddr%8;
      bitVal = (migRepInfo[memnum].writeCounter[cindex])&(1<<cbit);
      if (bitVal) {
         cbit = countAddr%64;
         counterVal = ((uint64) 1) << cbit;
      }
   } else {
      /* cache miss counter */
      cindex = countAddr*NUM_MEMORIES(0);
      counter = &(migRepInfo[memnum].cmissCounter[cindex]);
      if (FOUR_BIT_COUNTERS) {
         ASSERT(NUM_MEMORIES(0) <= 16);
         ASSERT(NUM_MACHINES == 1);
         for(i=0; i<NUM_MEMORIES(0); i++) {
            dummy =  counter[i];
            ASSERT(dummy < 16);
            counterVal |= ((dummy & 0xf) << (i*4));
         }
      } else {
         ASSERT(NUM_MEMORIES(0) <= 8);
         ASSERT(NUM_MACHINES == 1);
         for(i=0; i<NUM_MEMORIES(0); i++) {
            dummy =  counter[i];
            ASSERT(dummy < 256);
            counterVal |= ((dummy & 0xff) << (i*8));
         }
      }
   }
   return (counterVal);
}



/*
 * Called from the kernel through simmagic.
 * Sets the requested counter value as int64
 * This is because flashlite does it this way as a int64
 * Bit 19 of the address (20 active bits) is used to demux cache and write counters
 * Bottom 3 bits cannot be used.
 */
void
MigRepSetInfo(unsigned long addr, int memnum, uint64 val, 
              unsigned long countType, unsigned long countAddr)
{
   int i;
   unsigned long cindex, cbit, bitVal;
   unsigned char *counter;

   if (!(ENABLE_COUNT)) {
      return ;
   }

   if (countType) {
      /* Write counter */
      cindex = countAddr/8;
      cbit = countAddr%8;
      bitVal = 1 << cbit;
      if (val) {
         migRepInfo[memnum].writeCounter[cindex] |= bitVal;
      } else {
         migRepInfo[memnum].writeCounter[cindex] &= ~(bitVal);
      }
   } else {
      /* cache miss counter */
      cindex = countAddr*NUM_MEMORIES(0);
      counter = &(migRepInfo[memnum].cmissCounter[cindex]);
      if (FOUR_BIT_COUNTERS) {
         ASSERT(NUM_MEMORIES(0) <= 16);
         ASSERT(NUM_MACHINES == 1);
         for(i=0; i<NUM_MEMORIES(0); i++) {
            counter[i] = (char) ((val >> (i*4)) & 0xf);
            /* counter[i] = (char) ((val >> (i*8)) & 0x0ff); */
         }
      } else {
         ASSERT(NUM_MEMORIES(0) <= 8);
         ASSERT(NUM_MACHINES == 1);
         for(i=0; i<NUM_MEMORIES(0); i++) {
            counter[i] = (char) ((val >> (i*8)) & 0x0ff);
         }
      }
   }

}


/*
 * Called periodically to reset some miss counters
 * Each time through a MAGIC cache line (128 bytes) of cache-miss counters are reset
 * When resetWriteCounters goes to zero 128 bytes of write counters are reset.
 * Uses the callback mechanism
 */
static void
MigRepPeriodic(int cpuNum, EventCallbackHdr *hdr, void *v)
{
   int i, j, k;
   unsigned long nextResetIndex = cmissResetIndex + CMISS_COUNTERS_PER_CACHELINE;
   unsigned long countersToReset = CMISS_COUNTERS_PER_CACHELINE;
   unsigned char *counter;

   if (nextResetIndex >= numaStripeSizePages) {
      countersToReset = CMISS_COUNTERS_PER_CACHELINE - (nextResetIndex - numaStripeSizePages);
      nextResetIndex = 0;
   }

   for (k=0; k<NUM_MEMORIES(0); k++) {
      counter = &(migRepInfo[k].cmissCounter[cmissResetIndex]);
      for (i=0; i<countersToReset; i++) {
         for (j=0; j<TOTAL_CPUS; j++, counter++) {
            *counter = TRIGGER_THRESHOLD;
         }
      }
   }
   cmissResetIndex = nextResetIndex;

   if (!(--resetWriteCounters)) {
      resetWriteCounters = WRITE_COUNTERS_PER_CACHELINE/CMISS_COUNTERS_PER_CACHELINE;

      nextResetIndex = writeResetIndex + WRITE_COUNTERS_PER_CACHELINE;
      countersToReset = WRITE_COUNTERS_PER_CACHELINE;

      if (nextResetIndex >= numaStripeSizePages) {
         countersToReset = WRITE_COUNTERS_PER_CACHELINE - (nextResetIndex - numaStripeSizePages);
         nextResetIndex = 0;
      }

      for (k=0; k<NUM_MEMORIES(0); k++) {
         counter = &(migRepInfo[k].writeCounter[writeResetIndex/8]);
         for (i=0; i<(countersToReset/8); i++, counter++) {
               *counter = 0;
         }
      }
      writeResetIndex = nextResetIndex;
   }

   EventDoCallback(0, MigRepPeriodic, &resetCounterCB, 0, counterResetInterval);

}