disksim_cachemem.c

目前最精确的磁盘模拟器的第3版

   cache_atom *tmp = cache->hash[(lbn & CACHE_HASHMASK)];
/*
fprintf (outputfile, "Entered cache_find_atom: devno %d, lbn %d, CACHE_HASHMASK %x, setno %d\n", devno, lbn, CACHE_HASHMASK, (lbn & CACHE_HASHMASK));
*/
   while ((tmp) && ((tmp->lbn != lbn) || (tmp->devno != devno))) {
      tmp = tmp->hash_next;
   }
   return(tmp);
}


#if 0
static void cache_remove_lbn_from_hash (cache_def *cache, int devno, int lbn)
{
   cache_atom *tmp;

   if ((tmp = cache_find_atom(cache, devno, lbn))) {
      cache_remove_entry_from_hash(cache, tmp);
   }
}
#endif


#if 0
static void cache_check_for_residence (cache_def *cache, int devno, int lbn, int size, int *miss)
{
   cache_atom *line = NULL;
   int i;

   for (i=0; i<size; i++) {
      if (line == NULL) {
         line = cache_find_atom(cache, devno, (lbn + i));
      }
      if ((line == NULL) || ((line->state & CACHE_VALID) == 0)) {
         miss[(i & INV_BITS_PER_INT_MASK)] |= 1 << (i & BITS_PER_INT_MASK);
      }
      if (line) {
         line = line->line_next;
      }
   }
}
#endif


#if 0
/* Use for setting VALID, LOCKDOWN, DIRTY and other atom state bits */

static void cache_set_state (cache_def *cache, int devno, int lbn, int size, int mask)
{
   cache_atom *line = NULL;
   int i;

   for (i=0; i<size; i++) {
      if (line == NULL) {
         line = cache_find_atom(cache, devno, (lbn + i));
      }
	       /* Can't change state of unallocated cache atoms */
      ASSERT(line != NULL);

      line->state |= mask;
      line = line->line_next;
   }
}
#endif


#if 0
/* Use for clearing VALID, LOCKDOWN, DIRTY and other atom state bits */

static void cache_reset_state (cache_def *cache, int devno, int lbn, int size, int mask)
{
   cache_atom *line = NULL;
   int i;

   for (i=0; i<size; i++) {
      if (line == NULL) {
         line = cache_find_atom(cache, devno, (lbn + i));
      }
	       /* Can't change state of unallocated cache atoms */
      ASSERT(line != NULL);

      line->state &= ~mask;
      line = line->line_next;
   }
}
#endif


static void cache_add_to_lrulist (cache_mapentry *map, 
				  cache_atom *line, 
				  int segnum)
{
   cache_atom **head;

   if (segnum == CACHE_SEGNUM) {
      head = &map->freelist;
   } else {
      head = &map->lru[segnum];
      map->numactive[segnum]++;
   }
   line->state |= segnum;
   if (*head) {
      line->lru_next = *head;
      line->lru_prev = (*head)->lru_prev;
      (*head)->lru_prev = line;
      line->lru_prev->lru_next = line;
   } else {
      line->lru_next = line;
      line->lru_prev = line;
      *head = line;
   }
}


static void cache_remove_from_lrulist (cache_mapentry *map, cache_atom *line, int segnum)
{
   cache_atom **head;

   if (segnum == CACHE_SEGNUM) {
      head = &map->freelist;
   } else {
      head = &map->lru[segnum];
      map->numactive[segnum]--;
   }
   if (line->lru_next != line) {
      line->lru_prev->lru_next = line->lru_next;
      line->lru_next->lru_prev = line->lru_prev;
      if (*head == line) {
         *head = line->lru_next;
      }
   } else {
      *head = NULL;
   }
   line->state &= ~CACHE_SEGNUM;
   line->lru_next = NULL;
   line->lru_prev = NULL;
}


/* Reset state of LRU list given access to line */

static void cache_access (cache_def *cache, cache_atom *line)
{
   int set;
   int segnum = 0;

   if (cache->replacepolicy != CACHE_REPLACE_SLRU) {
      return;
   }
   while (line->line_prev) {
      line = line->line_prev;
   }
   set = (cache->mapmask) ? (line->lbn % cache->mapmask) : 0;
   if (line->lru_next) {
      segnum = line->state & CACHE_SEGNUM;
      cache_remove_from_lrulist(&cache->map[set], line, segnum);
      if (segnum != (cache->numsegs-1)) {
         segnum = (segnum + 1) & CACHE_SEGNUM;
      }
   }
   cache_add_to_lrulist(&cache->map[set], line, segnum);
   while ((segnum) && 
	  (cache->map[set].numactive[segnum] == 
	   cache->map[set].maxactive[segnum])) 
     {
       line = cache->map[set].lru[segnum];
       cache_remove_from_lrulist(&cache->map[set], line, segnum);
       segnum--;
       cache_add_to_lrulist(&cache->map[set], line, segnum);
     }
}


static void cache_replace_waitforline (cache_def *cache, cache_event *allocdesc)
{
   // fprintf (outputfile, "entered cache_replace_waitforline: linelocked %d\n", (allocdesc->flags & CACHE_FLAG_LINELOCKED_ALLOCATE));

   if (cache->linewaiters) {
      allocdesc->next = cache->linewaiters->next;
      cache->linewaiters->next = allocdesc;
      if (!(allocdesc->flags & CACHE_FLAG_LINELOCKED_ALLOCATE)) {
         cache->linewaiters = allocdesc;
      }
   } else {
      allocdesc->next = allocdesc;
      cache->linewaiters = allocdesc;
   }
   allocdesc->flags |= CACHE_FLAG_LINELOCKED_ALLOCATE;
}


static cache_atom *cache_get_replace_startpoint (cache_def *cache, int set)
{
   cache_atom *line = cache->map[set].lru[0];

   if (line) {
      if (cache->replacepolicy == CACHE_REPLACE_RANDOM) {
         int choice = cache->map[set].numactive[0] * DISKSIM_drand48();
         int i;
         for (i=0; i<choice; i++) {
            line = line->lru_prev;
         }
      } else if (cache->replacepolicy == CACHE_REPLACE_LIFO) {
         line = line->lru_prev;
      } else if ((cache->replacepolicy != CACHE_REPLACE_FIFO) && (cache->replacepolicy != CACHE_REPLACE_SLRU)) {
         fprintf(stderr, "Unknown replacement policy at cache_get_replace_startpoint: %d\n", cache->replacepolicy);
         exit(1);
      }
   }
   return(line);
}


/* Add identifier to lockstruct only if not already present */

static void cache_add_to_lockstruct (struct cachelockw **head, void *identifier)
{
   struct cachelockw *tmp = *head;
   int start = FALSE;
   int i;

   if (tmp == NULL) {
      tmp = (struct cachelockw *) getfromextraq();
	  memset((char *)tmp, 0, sizeof(struct cachelockw));
      /* bzero ((char *)tmp, sizeof(struct cachelockw)); */
      tmp->entry[0] = identifier;
      *head = tmp;
   } else {
      while (tmp->next) {
         for (i=0; i<CACHE_LOCKSPERSTRUCT; i++) {
            if (tmp->entry[i] == identifier) {
               return;
            }
         }
         tmp = tmp->next;
      }
      for (i=0; i<CACHE_LOCKSPERSTRUCT; i++) {
         if (tmp->entry[i] == identifier) {
            return;
         } else if (tmp->entry[i]) {
            start = TRUE;
         } else if (start) {
            tmp->entry[i] = identifier;
            return;
         }
      }
      tmp->next = (struct cachelockw *) getfromextraq();
      tmp = tmp->next;
	  memset ((char *)tmp, 0, sizeof(struct cachelockw));
      /* bzero ((char *)tmp, sizeof(struct cachelockw)); */
      tmp->entry[0] = identifier;
   }
}


/* Does anyone have a write lock on the atom?? */

static int cache_atom_iswritelocked (cache_def *cache, cache_atom *target)
{
   while (target->lbn % cache->lockgran) {
      target = target->line_prev;
   }
   return(target->writelock != NULL);
}


/* Does anyone have any lock on the atom?? */

static int cache_atom_islocked (cache_def *cache, cache_atom *target)
{
   while (target->lbn % cache->lockgran) {
      target = target->line_prev;
   }
   return(target->readlocks || target->writelock);
}


#if 0
/* should change this code so that newly enabled "I-streams" do not */
/* necessarily preempt the "I-stream" that freed the lock...        */

static void cache_give_lock_to_waiter (cache_def *cache, cache_atom *target, cache_event *rwdesc)
{
   switch (rwdesc->type) {

      case CACHE_EVENT_READ:
                               cache_read_continue(cache, rwdesc);
                               break;

      case CACHE_EVENT_WRITE:
                               cache_write_continue(cache, rwdesc);
                               break;

      default:
       fprintf(stderr, "Unknown type at cache_give_lock_to_waiter: %d\n", rwdesc->type);
       exit(1);
   }
}
#endif


static void cache_lock_free (cache_def *cache, cache_atom *target)
{
   cache_lockwaiters *tmp;
   int writelocked = FALSE;

	      /* Can't give away a line that is writelock'd */
   ASSERT(!target->writelock);

   if ((tmp = target->lockwaiters)) {
      int i = 0;
      while ((tmp) && (!writelocked) && (!target->writelock)) {
         cache_event *waiter = NULL;
         if (tmp->entry[i]) {
            writelocked = (cache->sharedreadlocks == 0) || tmp->entry[i]->locktype;
            if ((!writelocked) || (target->readlocks == NULL)) {
               waiter = tmp->entry[i];
               tmp->entry[i] = NULL;
            }
         }
         i++;
         if (i == CACHE_LOCKSPERSTRUCT) {
            target->lockwaiters = tmp->next;
            addtoextraq((event *) tmp);
            tmp = target->lockwaiters;
            i = 0;
         }
         if (waiter) {
	    (*cache->wakeupfunc)(cache->wakeupparam, waiter);
         }
      }
   } else if (cache->linewaiters) {
      int linesize = max(cache->linesize, 1);
      cache_event *allocdesc;
      while (target->lbn % linesize) {
         target = target->line_prev;
      }
      while (target) {
         if ((target->writelock) || (target->readlocks)) {
            return;
         }
         target = target->line_next;
      }
      allocdesc = cache->linewaiters->next;
      if (allocdesc->next == allocdesc) {
         cache->linewaiters = NULL;
      } else {
         cache->linewaiters->next = allocdesc->next;
      }
      allocdesc->next = NULL;
      // fprintf (outputfile, "allocation continuing: line finally freed\n");
      (*cache->wakeupfunc)(cache->wakeupparam, allocdesc);
   }
}


/* gransize is assumed to be a factor of linesize */

static int cache_get_write_lock (cache_def *cache, cache_atom *target, cache_event *rwdesc)
{
   //fprintf (outputfile, "Entered cache_get_write_lock: target %p, lbn %d, lockgran %d\n", target, target->lbn, cache->lockgran);

   while (target->lbn % cache->lockgran) {
      target = target->line_prev;
   }

   // fprintf (outputfile, "doing cache_get_write_lock: target %p, lbn %d, lockgran %d\n", target, target->lbn, cache->lockgran);

   if (target->writelock == rwdesc->req) {
      return(cache->lockgran);
   } else if ((target->writelock) || (target->readlocks)) {
      rwdesc->locktype = 1;
      cache_add_to_lockstruct(&target->lockwaiters, rwdesc);
      return(0);
   } else {
      target->writelock = rwdesc->req;
      return(cache->lockgran);
   }
}


static int cache_free_write_lock (cache_def *cache, cache_atom *target, ioreq_event *owner)
{

   // fprintf (outputfile, "Entered cache_free_write_lock: target %p, lbn %d, lockgran %d\n", target, target->lbn, cache->lockgran);

   while (target->lbn % cache->lockgran) {
      target = target->line_prev;
   }

   // fprintf (outputfile, "doing cache_free_write_lock: target %p, lbn %d, lockgran %d\n", target, target->lbn, cache->lockgran);

   if (owner == target->writelock) {
      target->writelock = NULL;
      cache_lock_free(cache, target);
      return(cache->lockgran);
   } else {
      return(0);
   }
}


static int cache_get_read_lock (cache_def *cache, cache_atom *target, cache_event *rwdesc)
{
   // fprintf (outputfile, "Entered cache_get_read_lock: target %p, lbn %d, lockgran %d\n", target, target->lbn, cache->lockgran);

   if (!cache->sharedreadlocks) {
      return(cache_get_write_lock(cache, target, rwdesc));
   }
   while (target->lbn % cache->lockgran) {
      target = target->line_prev;
   }