disksim_cachemem.c

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

}


/* Return number of writeouts (dirty block flushes) to be waited for.      */
/* Also fill pointer to block allocated.  Null indicates that blocks must  */
/* be written out but no specific one has yet been allocated.              */

static int cache_get_free_atom (cache_def *cache, int lbn, cache_atom **ret, cache_event *allocdesc)
{
   int writeouts = 0;
   int set = (cache->mapmask) ? (lbn % cache->mapmask) : 0;

   // fprintf (outputfile, "Entered cache_get_free_atom: lbn %d, set %d, freelist %p\n", lbn, set, cache->map[set].freelist);

   if (cache->map[set].freelist == NULL) {
      writeouts = cache_replace(cache, set, allocdesc);
   }
   if ((*ret = cache->map[set].freelist)) {
      cache_remove_from_lrulist(&cache->map[set], *ret, CACHE_SEGNUM);
   }
   return(writeouts);
}


/* Still need to add check for outstanding allocations by other people, to
avoid allocation replication */

static cache_event *cache_allocate_space_continue (cache_def *cache, cache_event *allocdesc)
{
   int numwrites = 0;
   cache_atom *new;
/*
   cache_atom *toclean = NULL;
   cache_atom *tocleanlast;
   int flushstart = -1;
*/

   int devno = allocdesc->req->devno;
   int lbn = allocdesc->lockstop;
   int stop = allocdesc->allocstop;
   cache_atom *cleaned = allocdesc->cleaned;
   cache_atom *lineprev = allocdesc->lineprev;
   int linesize = (cache->linesize) ? cache->linesize : 1;

   // fprintf (outputfile, "Entered allocate_space_continue: lbn %d, stop %d\n", lbn, stop);

   if (allocdesc->waitees) {
      cache_event *rwdesc = allocdesc->waitees;
      if (rwdesc->type == CACHE_EVENT_READ) {
         cache_read_continue(cache, rwdesc);
      } else {
         cache_write_continue(cache, rwdesc);
      }
      addtoextraq((event *) allocdesc);
      return(NULL);
   }
   while (lbn < stop) {
      if ((new = cleaned) == NULL) {
         numwrites += cache_get_free_atom(cache, lbn, &new, allocdesc);
      }
      if (numwrites == 0) {
	 ASSERT(new != NULL);
         do {
            new->devno = devno;
            new->lbn = lbn;
		 /* Re-allocated cache atom must not still be locked */
	    ASSERT((!new->writelock) && (!new->readlocks));
/*
            new->writelock = allocdesc->prev->req;
*/
            new->state = CACHE_LOCKDOWN;
            cache_insert_new_into_hash(cache, new);
            lbn++;
            new = (lbn % linesize) ? new->line_next : new;
         } while (lbn % linesize);
         if (cache->linesize == 0) {
            new->line_next = NULL;
            new->line_prev = lineprev;
            if (lineprev) {
               lineprev->line_next = new;
            }
            lineprev =  ((cache->linesize == -1) || (lbn % linesize)) ? new : NULL;
         }
/*
      } else if (cache->startallflushes) {
         if (flushstart == -1) {
            flushstart = i;
         }
         if (new) {
            if (toclean) {
               tocleanlast->line_next = new;
               tocleanlast = new;
            } else {
               toclean = new;
               tocleanlast = new;
            }
            while (tocleanlast->line_next) {
               tocleanlast = tocleanlast->line_next;
            }
         }
*/
      } else {
         allocdesc->lockstop = lbn;
         allocdesc->cleaned = new;
         allocdesc->lineprev = lineprev;
         /* This needs fixing! */
/*
         cache_waitfor_IO(cache, numwrites, allocdesc, NULL);
*/
         return(allocdesc);
      }
   }
/*
   if (numwrites) {
      allocdesc->lockstop = flushstart;
      allocdesc->cleaned = toclean;
      allocdesc->lineprev = lineprev;
      cache_wait(cache, numwrites, allocdesc);
      return(allocdesc);
   }
*/
   addtoextraq((event *) allocdesc);
   return(NULL);
}


static cache_event * cache_allocate_space (cache_def *cache, int lbn, int size, cache_event *rwdesc)
{
   cache_event *allocdesc = (cache_event *) getfromextraq();
   int linesize = max(1, cache->linesize);

   // fprintf (outputfile, "Entered cache_allocate_space: lbn %d, size %d, linesize %d\n", lbn, size, cache->linesize);

   allocdesc->type = CACHE_EVENT_ALLOCATE;
   allocdesc->req = rwdesc->req;
   allocdesc->flags = rwdesc->flags & CACHE_FLAG_LINELOCKED_ALLOCATE;
   allocdesc->lockstop = lbn - (lbn % linesize);
   allocdesc->allocstop =  lbn + size + (linesize - 1 - ((lbn + size - 1) % linesize));
   allocdesc->cleaned = NULL;
   allocdesc->lineprev = NULL;
   allocdesc->prev = rwdesc;
   allocdesc->waitees = NULL;
   if ((allocdesc = cache_allocate_space_continue(cache, allocdesc))) {
      allocdesc->waitees = rwdesc;
      rwdesc->flags |= allocdesc->flags & CACHE_FLAG_LINELOCKED_ALLOCATE;
   }
   return(allocdesc);
}


static int cache_get_rw_lock (cache_def *cache, int locktype, cache_event *rwdesc, cache_atom *line, int i, int stop)
{
   int lockgran;
   cache_atom *tmp = line;
   int j = 0;

   int lbn = rwdesc->req->blkno;
   int devno = rwdesc->req->devno;

   // fprintf (outputfile, "Entered cache_get_rw_lock: lbn %d, i %d, stop %d, locktype %d\n", line->lbn, i, stop, locktype);

   while (j < stop) {
      if (locktype == 1) {
         lockgran = cache_get_read_lock(cache, tmp, rwdesc);
      } else {
         if (locktype == 3) {
            cache_free_read_lock(cache, tmp, rwdesc->req);
         }
         lockgran = cache_get_write_lock(cache, tmp, rwdesc);
      }

   // fprintf (outputfile, "got lock: lockgran %d, lbn %d\n", lockgran, tmp->lbn);

      if (lockgran == 0) {
         return(1);
      } else {
         if ((line->lbn != (lbn + i)) || (line->devno != devno)) {

            /* NOTE: this precaution only covers us when FIRST atom of line */
            /* changes identity.  Otherwise, must have other support.       */

            if (locktype == 1) {
               cache_free_read_lock(cache, tmp, rwdesc->req);
            } else {
               cache_free_write_lock(cache, tmp, rwdesc->req);
            }
            return(2);
         }
         j++;
         tmp = tmp->line_next;
         while ((tmp) && (tmp->lbn % lockgran)) {
            j++;
            tmp = tmp->line_next;
         }
      }
   }
   return(0);
}


static int cache_issue_fillreq (cache_def *cache, int start, int end, cache_event *rwdesc, int prefetchtype)
{
   ioreq_event *fillreq;
   int linesize = max(cache->linesize, 1);

   // fprintf (outputfile, "Entered cache_issue_fillreq: start %d, end %d, prefetchtype %d\n", start, end, prefetchtype);

   if (prefetchtype & CACHE_PREFETCH_FRONTOFLINE) {
      cache_atom *line = cache_find_atom(cache, rwdesc->req->devno, start);
      int validstart = -1;
      int lockgran = cache->lockgran;
      while (start % linesize) {
         line = line->line_prev;
         if (line->state & CACHE_VALID) {
/*
fprintf (outputfile, "already valid backwards: lbn %d\n", line->lbn);
*/
            break;
/*
            if (line->state & CACHE_DIRTY) {
               break;
            }
            if (validstart == -1) {
               validstart = line->lbn;
            }
*/
         } else {
            validstart = -1;
         }
         if ((line->lbn % lockgran) == (lockgran-1)) {
            if ((!cache->prefetch_waitfor_locks) && (cache_atom_islocked(cache, line))) {
               break;
            }
            if ((lockgran = cache_get_write_lock(cache, line, rwdesc)) == 0) {
               return(0);
            }
         }
         start--;
         line->state |= CACHE_VALID;
      }
/* Need to free some locks if do this...
      if (validstart != -1) {
         start = validstart;
      }
*/
   }
   if (prefetchtype & CACHE_PREFETCH_RESTOFLINE) {
      cache_atom *line = cache_find_atom(cache, rwdesc->req->devno, end);
      int validend = -1;
      int lockgran = cache->lockgran;
      while ((end+1) % linesize) {
         line = line->line_next;
         if (line->state & CACHE_VALID) {
/*
fprintf (outputfile, "already valid forwards: lbn %d\n", line->lbn);
*/
            break;
/*
            if (line->state & CACHE_DIRTY) {
               break;
            }
            if (validend == -1) {
               validend = line->lbn;
            }
*/
         } else {
            validend = -1;
         }
         if ((line->lbn % lockgran) == 0) {
            if ((!cache->prefetch_waitfor_locks) && (cache_atom_islocked(cache, line))) {
               break;
            }
            if ((lockgran = cache_get_write_lock(cache, line, rwdesc)) == 0) {
               return(0);
            }
         }
         end++;
         line->state |= CACHE_VALID;
      }
/* Need to free some locks if do this...
      if (validend != -1) {
         end = validend;
      }
*/
   }

   fillreq  = ioreq_copy(rwdesc->req);
   fillreq->blkno = start;
   fillreq->bcount = end - start + 1;
   fillreq->type = IO_ACCESS_ARRIVE;
   fillreq->flags |= READ;
   rwdesc->req->tempint1 = start;
   rwdesc->req->tempint2 = end;
   rwdesc->type = (rwdesc->type == CACHE_EVENT_READ) ? CACHE_EVENT_READEXTRA : CACHE_EVENT_WRITEFILLEXTRA;
   cache_waitfor_IO(cache, 1, rwdesc, fillreq);

   // fprintf (outputfile, "%f: Issueing line fill request: blkno %d, bcount %d\n", simtime, fillreq->blkno, fillreq->bcount);

   (*cache->issuefunc)(cache->issueparam, fillreq);
   return(end - start + 1);
}


static void cache_unlock_attached_prefetch (cache_def *cache, cache_event *rwdesc)
{
   int fillstart = rwdesc->req->tempint1;
   int fillend = rwdesc->req->tempint2 + 1;  /* one beyond, actually */
   int reqstart = rwdesc->req->blkno;
   int reqend = reqstart + rwdesc->req->bcount;  /* one beyond, actually */

   // fprintf (outputfile, "Entered cache_unlock_attached_prefetch: fillstart %d, fillend %d, reqstart %d, reqend %d\n", fillstart, fillend, reqstart, reqend);

   if (fillstart < reqstart) {
      int lockgran = cache->lockgran;
      while (reqstart % cache->lockgran) {
         reqstart--;
      }

      reqstart--;
      if (fillstart <= reqstart) {
         cache_atom *line = cache_find_atom(cache, rwdesc->req->devno, reqstart);
         do {
            if ((line->lbn % lockgran) == (lockgran-1)) {
               lockgran = cache_free_write_lock(cache, line, rwdesc->req);
                    /* Can't free lock if not held */
               ASSERT(lockgran != 0);
            }
            line = line->line_prev;
            reqstart--;
         } while (fillstart <= reqstart);
      }
   }
   if (fillend > reqend) {
      int lockgran = cache->lockgran;
         while (reqend % cache->lockgran) {
            reqend++;
         }
/*
      if ((fillend / cache->lockgran) == (reqend / cache->lockgran)) {
      } else {
         reqend++;
      }
*/
      if (fillend > reqend) {
         cache_atom *line = cache_find_atom(cache, rwdesc->req->devno, reqend);
         do {
            if ((line->lbn % lockgran) == 0) {
               lockgran = cache_free_write_lock(cache, line, rwdesc->req);
                    /* Can't free lock if not held */
               ASSERT(lockgran != 0);
            }
            line = line->line_next;
            reqend++;
         } while (fillend > reqend);
      }
   }
}


static int cache_read_continue (cache_def *cache, cache_event *readdesc)
{
   cache_atom *line = NULL;
   cache_atom *tmp;
   int i, j;
   cache_event *waitee;
   int stop = 0;
   int curlock;
   int lockgran;
   int ret;

   int linesize = max(1, cache->linesize);
   int devno = readdesc->req->devno;
   int lbn = readdesc->req->blkno;
   int size = readdesc->req->bcount;
   int validpoint = readdesc->validpoint;

   if (cache->size == 0) {
      cache_waitfor_IO(cache, 1, readdesc, readdesc->req);
      cache->stat.readmisses++;
      cache->stat.fillreads++;
      cache->stat.fillreadatoms += readdesc->req->bcount;
      readdesc->req->type = IO_ACCESS_ARRIVE;
      (*cache->issuefunc)(cache->issueparam, ioreq_copy(readdesc->req));
      return(1);
   }
   i = readdesc->lockstop;

   // fprintf (outputfile, "Entered cache_read_continue: lbn %d, size %d, i %d\n", lbn, size, i);

read_cont_loop:
   while (i < size) {
      line = cache_find_atom(cache, devno, (lbn + i));
      waitee = NULL;
      if (line == NULL) {
         if ((waitee = cache_allocate_space(cache, (lbn + i), 1, readdesc))) {
            readdesc->lockstop = i;
            return(1);
         } else {
            continue;
         }
      }
      stop = min(rounduptomult((size - i), cache->atomsperbit), (linesize - ((lbn + i) % linesize)));

      // fprintf (outputfile, "stop %d, lbn %d, atomsperbit %d, i %d, size %d, linesize %d\n", stop, lbn, cache->atomsperbit, i, size, linesize);
      // fprintf (outputfile, "validpoint %d, i %d\n", validpoint, i);

      j = 0;
      tmp = line;
      curlock = 2;
      lockgran = 0;
      while (j < stop) {
         int locktype = (tmp->state & CACHE_VALID) ? 1 : 2;