cache.c

这个是LINUX下的GDB调度工具的源码

/* Requeu the given request from the last of the given pipeline.  */
static void
pipeline_requeue_request (FRV_CACHE_PIPELINE *p)
{
  FRV_CACHE_STAGE *stage = & p->stages[LAST_STAGE];
  FRV_CACHE_REQUEST *req = stage->request;
  stage->request = NULL;
  pipeline_add_request (p, req);
}

/* Return the priority lower than the lowest one in this cache pipeline.
   0 is the highest priority.  */
static int
next_priority (FRV_CACHE *cache, FRV_CACHE_PIPELINE *pipeline)
{
  int i, j;
  int pipe;
  int lowest = 0;
  FRV_CACHE_REQUEST *req;

  /* Check the priorities of any queued items.  */
  for (req = pipeline->requests; req != NULL; req = req->next)
    if (req->priority > lowest)
      lowest = req->priority;

  /* Check the priorities of items in the pipeline stages.  */
  for (i = FIRST_STAGE; i < FRV_CACHE_STAGES; ++i)
    {
      FRV_CACHE_STAGE *stage = & pipeline->stages[i];
      if (stage->request != NULL && stage->request->priority > lowest)
        lowest = stage->request->priority;
    }

  /* Check the priorities of load requests waiting in WAR.  These are one
     higher than the request that spawned them.  */
  for (i = 0; i < NUM_WARS; ++i)
    {
      FRV_CACHE_WAR *war = & pipeline->WAR[i];
      if (war->valid && war->priority > lowest)
	lowest = war->priority + 1;
    }

  /* Check the priorities of any BARS or NARS associated with this pipeline.
     These are one higher than the request that spawned them.  */
  pipe = pipeline - cache->pipeline;
  if (cache->BARS.valid && cache->BARS.pipe == pipe 
      && cache->BARS.priority > lowest)
    lowest = cache->BARS.priority + 1;
  if (cache->NARS.valid && cache->NARS.pipe == pipe 
      && cache->NARS.priority > lowest)
    lowest = cache->NARS.priority + 1;

  /* Return a priority 2 lower than the lowest found.  This allows a WAR
     request to be generated with a priority greater than this but less than
     the next higher priority request.  */
  return lowest + 2;
}

static void
add_WAR_request (FRV_CACHE_PIPELINE* pipeline, FRV_CACHE_WAR *war)
{
  /* Add the load request to the indexed pipeline.  */
  FRV_CACHE_REQUEST *req = new_cache_request ();
  req->kind = req_WAR;
  req->reqno = war->reqno;
  req->priority = war->priority;
  req->address = war->address;
  req->u.WAR.preload = war->preload;
  req->u.WAR.lock = war->lock;
  pipeline_add_request (pipeline, req);
}

/* Remove the next request from the given pipeline and return it.  */
static FRV_CACHE_REQUEST *
pipeline_next_request (FRV_CACHE_PIPELINE *p)
{
  FRV_CACHE_REQUEST *first = p->requests;
  if (first != NULL)
    pipeline_remove_request (p, first);
  return first;
}

/* Return the request which is at the given stage of the given pipeline.  */
static FRV_CACHE_REQUEST *
pipeline_stage_request (FRV_CACHE_PIPELINE *p, int stage)
{
  return p->stages[stage].request;
}

static void
advance_pipelines (FRV_CACHE *cache)
{
  int stage;
  int pipe;
  FRV_CACHE_PIPELINE *pipelines = cache->pipeline;

  /* Free the final stage requests.  */
  for (pipe = 0; pipe < FRV_CACHE_PIPELINES; ++pipe)
    {
      FRV_CACHE_REQUEST *req = pipelines[pipe].stages[LAST_STAGE].request;
      if (req != NULL)
	free_cache_request (req);
    }

  /* Shuffle the requests along the pipeline.  */
  for (stage = LAST_STAGE; stage > FIRST_STAGE; --stage)
    {
      for (pipe = 0; pipe < FRV_CACHE_PIPELINES; ++pipe)
	pipelines[pipe].stages[stage] = pipelines[pipe].stages[stage - 1];
    }

  /* Add a new request to the pipeline.  */
  for (pipe = 0; pipe < FRV_CACHE_PIPELINES; ++pipe)
    pipelines[pipe].stages[FIRST_STAGE].request
      = pipeline_next_request (& pipelines[pipe]);
}

/* Handle a request for a load from the given address.  */
void
frv_cache_request_load (FRV_CACHE *cache, unsigned reqno, SI address, int slot)
{
  FRV_CACHE_REQUEST *req;

  /* slot is a UNIT_*.  Convert it to a cache pipeline index.  */
  int pipe = convert_slot_to_index (slot);
  FRV_CACHE_PIPELINE *pipeline = & cache->pipeline[pipe];

  /* Add the load request to the indexed pipeline.  */
  req = new_cache_request ();
  req->kind = req_load;
  req->reqno = reqno;
  req->priority = next_priority (cache, pipeline);
  req->address = address;

  pipeline_add_request (pipeline, req);
}

void
frv_cache_request_store (FRV_CACHE *cache, SI address,
			 int slot, char *data, unsigned length)
{
  FRV_CACHE_REQUEST *req;

  /* slot is a UNIT_*.  Convert it to a cache pipeline index.  */
  int pipe = convert_slot_to_index (slot);
  FRV_CACHE_PIPELINE *pipeline = & cache->pipeline[pipe];

  /* Add the load request to the indexed pipeline.  */
  req = new_store_request (length);
  req->kind = req_store;
  req->reqno = NO_REQNO;
  req->priority = next_priority (cache, pipeline);
  req->address = address;
  req->u.store.length = length;
  memcpy (req->u.store.data, data, length);

  pipeline_add_request (pipeline, req);
  invalidate_return_buffer (cache, address);
}

/* Handle a request to invalidate the cache line containing the given address.
   Flush the data if requested.  */
void
frv_cache_request_invalidate (FRV_CACHE *cache, unsigned reqno, SI address,
			      int slot, int all, int flush)
{
  FRV_CACHE_REQUEST *req;

  /* slot is a UNIT_*.  Convert it to a cache pipeline index.  */
  int pipe = convert_slot_to_index (slot);
  FRV_CACHE_PIPELINE *pipeline = & cache->pipeline[pipe];

  /* Add the load request to the indexed pipeline.  */
  req = new_cache_request ();
  req->kind = req_invalidate;
  req->reqno = reqno;
  req->priority = next_priority (cache, pipeline);
  req->address = address;
  req->u.invalidate.all = all;
  req->u.invalidate.flush = flush;

  pipeline_add_request (pipeline, req);
}

/* Handle a request to preload the cache line containing the given address.  */
void
frv_cache_request_preload (FRV_CACHE *cache, SI address,
			   int slot, int length, int lock)
{
  FRV_CACHE_REQUEST *req;

  /* slot is a UNIT_*.  Convert it to a cache pipeline index.  */
  int pipe = convert_slot_to_index (slot);
  FRV_CACHE_PIPELINE *pipeline = & cache->pipeline[pipe];

  /* Add the load request to the indexed pipeline.  */
  req = new_cache_request ();
  req->kind = req_preload;
  req->reqno = NO_REQNO;
  req->priority = next_priority (cache, pipeline);
  req->address = address;
  req->u.preload.length = length;
  req->u.preload.lock = lock;

  pipeline_add_request (pipeline, req);
  invalidate_return_buffer (cache, address);
}

/* Handle a request to unlock the cache line containing the given address.  */
void
frv_cache_request_unlock (FRV_CACHE *cache, SI address, int slot)
{
  FRV_CACHE_REQUEST *req;

  /* slot is a UNIT_*.  Convert it to a cache pipeline index.  */
  int pipe = convert_slot_to_index (slot);
  FRV_CACHE_PIPELINE *pipeline = & cache->pipeline[pipe];

  /* Add the load request to the indexed pipeline.  */
  req = new_cache_request ();
  req->kind = req_unlock;
  req->reqno = NO_REQNO;
  req->priority = next_priority (cache, pipeline);
  req->address = address;

  pipeline_add_request (pipeline, req);
}

/* Check whether this address interferes with a pending request of
   higher priority.  */
static int
address_interference (FRV_CACHE *cache, SI address, FRV_CACHE_REQUEST *req,
		      int pipe)
{
  int i, j;
  int line_mask = ~(cache->line_size - 1);
  int other_pipe;
  int priority = req->priority;
  FRV_CACHE_REQUEST *other_req;
  SI other_address;
  SI all_address;

  address &= line_mask;
  all_address = -1 & line_mask;

  /* Check for collisions in the queue for this pipeline.  */
  for (other_req = cache->pipeline[pipe].requests;
       other_req != NULL;
       other_req = other_req->next)
    {
      other_address = other_req->address & line_mask;
      if ((address == other_address || address == all_address)
	  && priority > other_req->priority)
	return 1;
    }

  /* Check for a collision in the the other pipeline.  */
  other_pipe = pipe ^ 1;
  other_req = cache->pipeline[other_pipe].stages[LAST_STAGE].request;
  if (other_req != NULL)
    {
      other_address = other_req->address & line_mask;
      if (address == other_address || address == all_address)
	return 1;
    }

  /* Check for a collision with load requests waiting in WAR.  */
  for (i = LS; i < FRV_CACHE_PIPELINES; ++i)
    {
      for (j = 0; j < NUM_WARS; ++j)
	{
	  FRV_CACHE_WAR *war = & cache->pipeline[i].WAR[j];
	  if (war->valid
	      && (address == (war->address & line_mask) 
		  || address == all_address)
	      && priority > war->priority)
	    return 1;
	}
      /* If this is not a WAR request, then yield to any WAR requests in
	 either pipeline or to a higher priority request in the same pipeline.
      */
      if (req->kind != req_WAR)
	{
	  for (j = FIRST_STAGE; j < FRV_CACHE_STAGES; ++j)
	    {
	      other_req = cache->pipeline[i].stages[j].request;
	      if (other_req != NULL)
		{
		  if (other_req->kind == req_WAR)
		    return 1;
		  if (i == pipe
		      && (address == (other_req->address & line_mask) 
			  || address == all_address)
		      && priority > other_req->priority)
		    return 1;
		}
	    }
	}
    }

  /* Check for a collision with load requests waiting in ARS.  */
  if (cache->BARS.valid
      && (address == (cache->BARS.address & line_mask)
	  || address == all_address)
      && priority > cache->BARS.priority)
    return 1;
  if (cache->NARS.valid
      && (address == (cache->NARS.address & line_mask)
	  || address == all_address)
      && priority > cache->NARS.priority)
    return 1;

  return 0;
}

/* Wait for a free WAR register in BARS or NARS.  */
static void
wait_for_WAR (FRV_CACHE* cache, int pipe, FRV_CACHE_REQUEST *req)
{
  FRV_CACHE_WAR war;
  FRV_CACHE_PIPELINE *pipeline = & cache->pipeline[pipe];

  if (! cache->BARS.valid)
    {
      cache->BARS.pipe = pipe;
      cache->BARS.reqno = req->reqno;
      cache->BARS.address = req->address;
      cache->BARS.priority = req->priority - 1;
      switch (req->kind)
	{
	case req_load:
	  cache->BARS.preload = 0;
	  cache->BARS.lock = 0;
	  break;
	case req_store:
	  cache->BARS.preload = 1;
	  cache->BARS.lock = 0;
	  break;
	case req_preload:
	  cache->BARS.preload = 1;
	  cache->BARS.lock = req->u.preload.lock;
	  break;
	}
      cache->BARS.valid = 1;
      return;
    }
  if (! cache->NARS.valid)
    {
      cache->NARS.pipe = pipe;
      cache->NARS.reqno = req->reqno;
      cache->NARS.address = req->address;
      cache->NARS.priority = req->priority - 1;
      switch (req->kind)
	{
	case req_load:
	  cache->NARS.preload = 0;
	  cache->NARS.lock = 0;
	  break;
	case req_store:
	  cache->NARS.preload = 1;
	  cache->NARS.lock = 0;
	  break;
	case req_preload:
	  cache->NARS.preload = 1;
	  cache->NARS.lock = req->u.preload.lock;
	  break;
	}
      cache->NARS.valid = 1;
      return;
    }
  /* All wait registers are busy, so resubmit this request.  */
  pipeline_requeue_request (pipeline);
}

/* Find a free WAR register and wait for memory to fetch the data.  */
static void
wait_in_WAR (FRV_CACHE* cache, int pipe, FRV_CACHE_REQUEST *req)
{
  int war;
  FRV_CACHE_PIPELINE *pipeline = & cache->pipeline[pipe];

  /* Find a valid WAR to  hold this request.  */
  for (war = 0; war < NUM_WARS; ++war)
    if (! pipeline->WAR[war].valid)
      break;
  if (war >= NUM_WARS)
    {
      wait_for_WAR (cache, pipe, req);
      return;
    }

  pipeline->WAR[war].address = req->address;
  pipeline->WAR[war].reqno = req->reqno;
  pipeline->WAR[war].priority = req->priority - 1;
  pipeline->WAR[war].latency = cache->memory_latency + 1;
  switch (req->kind)
    {
    case req_load:
      pipeline->WAR[war].preload = 0;
      pipeline->WAR[war].lock = 0;
      break;
    case req_store:
      pipeline->WAR[war].preload = 1;
      pipeline->WAR[war].lock = 0;
      break;
    case req_preload:
      pipeline->WAR[war].preload = 1;
      pipeline->WAR[war].lock = req->u.preload.lock;
      break;
    }
  pipeline->WAR[war].valid = 1;
}

static void
handle_req_load (FRV_CACHE *cache, int pipe, FRV_CACHE_REQUEST *req)
{
  FRV_CACHE_TAG *tag;