directory.c

一个用在mips体系结构中的操作系统

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

/****************************************************************
 * directory.c
 * 
 * $Author: bosch $
 * $Date: 1998/02/10 00:30:27 $
 *****************************************************************/
#include <bstring.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <unistd.h>
#include <stdlib.h>
#include "embra.h"
#include "stats.h"
#include "directory.h"
#include "qc.h"
#include "driver.h"
#include "mem_control.h"
#include "cache.h"
#include "simutil.h"

/* Directory Structure */
/* Bit 31 is the pending bit */
/* Bit 30 is the dirty bit */
/* the remaining 30 bits are allocated  one per processor */
#define DIR_ENT_PENDING(_dir_ent) ((unsigned)(_dir_ent) >> 31)
#define DIR_ENT_EXCL(_dir_ent) ((unsigned)(_dir_ent) & 0x40000000 )
#define DIR_ENT_MAKE_EXCL(_dir_ent) ((unsigned)(_dir_ent) | 0x40000000 )
#define DIR_ENT_CPUS(_dir_ent) (((unsigned)((unsigned)(_dir_ent) <<2))>>2)
#define DIR_ENT_ERASE_PENDING(_dir_ent) ((unsigned)(_dir_ent) & 0x7fffffff)
/* Defining this causes all sorts of check that the directory remains */
/* consistent */ 
/*#define DEBUG_DIR*/
Dir_Entry *directory[MAX_MACHINES];  

/* used for range checking */
Dir_Entry *max_directory[MAX_MACHINES];

/* These are (local) arrays with the values for all processors */
/* This is just an optimization as we could compute the addresses each */
/* time, but that would slow interventions (if our compilier weren't */
/* really good at moving out loop invariant code ) */
/* I don't trust malloc */
volatile unsigned* cc_addr[SIM_MAXCPUS];

/* Local Functions */
static void Do_Intervention( int cpuNum, PA pAddr, VA vAddr, 
                             EmVQCMemState state, Dir_Entry cpu_bits );
static Dir_Entry dir_get( int cpuNum, PA pAddr, VA vAddr,
                          EmVQCMemState state );
static Dir_Entry dir_getx( int cpuNum, PA pAddr, VA vAddr, 
                           EmVQCMemState state );

/* Only for multiprocessors */
void Directory_Init(void)
{
  static int FirstTime = 1;
  int machine;

  if( embra.emode == EMBRA_PAGE ) {
      return;
  }
  if (FirstTime) {
      FirstTime = 0;

      for (machine = 0; machine < NUM_MACHINES; machine++) {
          if (NUM_CPUS(machine) > 1) {
              directory[machine] =
                  (Dir_Entry*) ZALLOC_PERM(DIRECTORY_SIZE(machine),
                                           "EmbraDir");
              max_directory[machine] =
                  (Dir_Entry*)(directory[machine] +
                               DIRECTORY_SIZE(machine));
              CPUPrint("0x%x D Machine %d Directory_BASE 0x%x\n",
                       directory[machine],machine,
                       max_directory[machine] );
          }
      }
  }
}

static  unsigned cc_counts[SIM_MAXCPUS];
/* Note this procedure and the directory stucture limit us to 30 CPUs */
static void Do_Intervention( int cpuNum, PA pAddr, VA vAddr, 
                             EmVQCMemState state, Dir_Entry cpu_bits )
{
  static int count;
  register int i;
  int machine = M_FROM_CPU(cpuNum);

  /* Eliminate us from the cpu_bits */
  /* We could be in it if we have a read shared copy and we are upgrading */
  cpu_bits &= ~(EMP[cpuNum].myBit);

  /*Clobber the other guy's quick check, forcing synchronization at */
  /*the directory, then clobber his cache tags */
  Cache_Clobber( machine, cpuNum, pAddr, cpu_bits, state);

  if( !embra.MPinUP ) {
     /* Confirm that every other CPU is not in a race condition */
     /* Initial pass notes if other procs are out of TC , or if not, then */
     /* it notes their CC */ 
     for( i = FIRST_CPU(machine); i <= LAST_CPU(machine); i++ )
        {
           if( i != EMP[cpuNum].myNum )
              {
                 if( EMP[i].outTC || !EMP[i].outOfSlaveLoop )
                    cpu_bits &= (~(1<<i));
                 else
                    cc_counts[i] = EMP[i].cycleCountdown;
              }
        }
     i = FIRST_CPU(machine);
     while( cpu_bits )
        {
           if( i++ == LAST_CPU(machine) )
              i = 0;
           if( (cpu_bits>>i) & 0x1 )
              {
                 if( EMP[i].outTC )
                    cpu_bits &= (~(1<<i));
                 else
                    if( cc_counts[i] != EMP[i].cycleCountdown )
                       cpu_bits &= (~(1<<i));                  
              }
        }
  }
}


static Dir_Entry dir_get( int cpuNum, PA pAddr, VA vAddr, EmVQCMemState state )
{
  int machine = M_FROM_CPU(cpuNum);
  unsigned dir_entry = directory[machine][ADDR2SLINE(pAddr)];
  ASSERT( &directory[machine][ADDR2SLINE(pAddr)] < max_directory[machine] );
  if( !embra.MPinUP ) {
     ASSERT( DIR_ENT_PENDING(dir_entry) );
  }
  /* If I am in directory then either I own line exclusive (in which */
  /* case this action will downgrade me), or I have a read shared */
  /* copy, which in this case won't change anything */
#ifdef DEBUG_DIR
  if( DIR_ENT_CPUS(dir_entry) == EMP[cpuNum].myBit )
	 {
		qc_insure_other_qc_invalid(pAddr);
		return EMP[cpuNum].myBit;
	 }
#else
  if( dir_entry & EMP[cpuNum].myBit )
	 return DIR_ENT_CPUS(dir_entry);
#endif

#ifdef DEBUG_DIR
  if( !DIR_ENT_EXCL( dir_entry ) )
	 qc_insure_other_qc_invalid_or_read(pAddr);
#endif
  /* Owned exclusively by someone else --intervene*/
  if( DIR_ENT_EXCL( dir_entry ) ) {
	 Do_Intervention( cpuNum, pAddr, vAddr, state,
                      DIR_ENT_CPUS(dir_entry) );
  }
  /* else this is a read shared line, and we just want to enter the list*/

  return (DIR_ENT_CPUS(dir_entry) | EMP[cpuNum].myBit); /* new dir entry */
}

static Dir_Entry dir_getx( int cpuNum, PA pAddr, VA vAddr, 
                           EmVQCMemState state )
{
   int machine = M_FROM_CPU(cpuNum);
   Dir_Entry dir_entry = directory[machine][ADDR2SLINE(pAddr)];

   ASSERT( &directory[machine][ADDR2SLINE(pAddr)] < max_directory[machine] );
   if( !embra.MPinUP ) {
      ASSERT( DIR_ENT_PENDING(dir_entry) );
   }

   /* Someone else has dibs (excl or read shared) on the line, so intervene */
   if( DIR_ENT_CPUS(dir_entry) != EMP[cpuNum].myBit ) {
      Do_Intervention( cpuNum, pAddr, vAddr, state, 
                       DIR_ENT_CPUS(dir_entry) );
   }
#ifdef DEBUG_DIR
  /* We are the only users for the line, either exclusive (and we forgot) */
  /* or read shared (in which case this is an upgrade) */
	 qc_insure_other_qc_invalid(pAddr);
#endif
   return  DIR_ENT_MAKE_EXCL(EMP[cpuNum].myBit);
}

void Directory_NoLock_Modify( int cpuNum, PA pAddr, VA vAddr, int state )
{
   Dir_Entry dir_ent;
   int machine = M_FROM_CPU(cpuNum);
   ASSERT( NUM_CPUS(machine) > 1 );

   switch( state ) {
   case MEM_D_EXCLUSIVE:
   case MEM_I_EXCLUSIVE:
	  dir_ent = dir_getx( cpuNum, pAddr, vAddr, (EmVQCMemState)state );
	  break;
   case MEM_D_SHARED:
   case MEM_I_SHARED:
	  dir_ent = dir_get( cpuNum, pAddr, vAddr, (EmVQCMemState)state );
	  break;
   default:
      ASSERT(0);
   }
   ASSERT( !DIR_ENT_PENDING(dir_ent) );
   directory[machine][ADDR2SLINE(pAddr)] = dir_ent;
}

Dir_Entry Directory_Lock( int cpuNum, PA pAddr, VA vAddr, int state)
{
   int machine = M_FROM_CPU(cpuNum);
   ASSERT( NUM_CPUS(machine) > 1 );

   switch( state ) {
   case MEM_D_EXCLUSIVE:
   case MEM_I_EXCLUSIVE:
      Dir_Lock_Line( &directory[machine][ADDR2SLINE(pAddr)] );
	  return dir_getx( cpuNum, pAddr, vAddr, (EmVQCMemState)state );
   case MEM_D_SHARED:
   case MEM_I_SHARED:
      Dir_Lock_Line( &directory[machine][ADDR2SLINE(pAddr)] );
	  return dir_get( cpuNum, pAddr, vAddr, (EmVQCMemState)state );
   default:
      ASSERT(0);
   }
   return 0;
}  

void Directory_Free( int cpuNum, PA pAddr, Dir_Entry dir_ent )
{
   int machine = M_FROM_CPU(cpuNum);
   ASSERT( NUM_CPUS(machine) > 1 );

   ASSERT( dir_ent && !DIR_ENT_PENDING(dir_ent) );
   directory[machine][ADDR2SLINE(pAddr)] = dir_ent;
}

/* AKA replacement hint */
void Directory_Eliminate( int cpuNum, PLN pline, unsigned cpu_bit )
{
  unsigned dir_entry;
  int machine = M_FROM_CPU(cpuNum);

  /* If the tag is invalid, don't bother to affect the directory */
  /* NOTE: this check is now done in cache.c */
  /* Replacement hints not necessary for uniprocessor */
  /*if( pline == INVALID_TAG || NUM_CPUS(machine) == 1 )*/
  if( NUM_CPUS(machine) == 1 )
     return;

  dir_entry = Dir_Lock_Line( &directory[machine][pline] );
  ASSERT( DIR_ENT_PENDING(dir_entry) );
  /* We want to assert that our interventions are actually knocking */
  /* out the correct line, but because we do the replacement hint */
  /* outside of the directory lock (to avoid deadlock) we can be in a */
  /* state where we are issuing a replacement hint to a line which has */
  /* been stolen.  Therefore we can not assert this */
#ifdef COMMENTOUT
  {
	 extern PLN* pline_tag; /* cache.c */
	 if( !(dir_entry & cpu_bit) &&
		 pline_tag[pline%LINES_PER_CACHE] != INVALID_TAG ) {
		CPUPut("%d: pline 0x%x, tag 0x%x, direntry 0x%x cpu_bit 0x%x\n", 
			   EMP[cpuNum].myNum, pline, pline_tag[pline%LINES_PER_CACHE], dir_entry, cpu_bit);
	 }
	 ASSERT( (dir_entry & cpu_bit) || 
			 pline_tag[pline%LINES_PER_CACHE] == INVALID_TAG )
  }
#endif

  /* If I am the only user, clear the entry */
  if( DIR_ENT_CPUS(dir_entry) == cpu_bit ) {
	 directory[machine][pline] = 0;
	 return;
  }

  directory[machine][pline] = DIR_ENT_ERASE_PENDING(dir_entry & (~cpu_bit) );
}