disksim_cachedev.c

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

/*
 * DiskSim Storage Subsystem Simulation Environment (Version 3.0)
 * Revision Authors: John Bucy, Greg Ganger
 * Contributors: John Griffin, Jiri Schindler, Steve Schlosser
 *
 * Copyright (c) of Carnegie Mellon University, 2001, 2002, 2003.
 *
 * This software is being provided by the copyright holders under the
 * following license. By obtaining, using and/or copying this software,
 * you agree that you have read, understood, and will comply with the
 * following terms and conditions:
 *
 * Permission to reproduce, use, and prepare derivative works of this
 * software is granted provided the copyright and "No Warranty" statements
 * are included with all reproductions and derivative works and associated
 * documentation. This software may also be redistributed without charge
 * provided that the copyright and "No Warranty" statements are included
 * in all redistributions.
 *
 * NO WARRANTY. THIS SOFTWARE IS FURNISHED ON AN "AS IS" BASIS.
 * CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED AS TO THE MATTER INCLUDING, BUT NOT LIMITED
 * TO: WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY
 * OF RESULTS OR RESULTS OBTAINED FROM USE OF THIS SOFTWARE. CARNEGIE
 * MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT
 * TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.
 * COPYRIGHT HOLDERS WILL BEAR NO LIABILITY FOR ANY USE OF THIS SOFTWARE
 * OR DOCUMENTATION.
 *
 */


/*
 * DiskSim Storage Subsystem Simulation Environment (Version 2.0)
 * Revision Authors: Greg Ganger
 * Contributors: Ross Cohen, John Griffin, Steve Schlosser
 *
 * Copyright (c) of Carnegie Mellon University, 1999.
 *
 * Permission to reproduce, use, and prepare derivative works of
 * this software for internal use is granted provided the copyright
 * and "No Warranty" statements are included with all reproductions
 * and derivative works. This software may also be redistributed
 * without charge provided that the copyright and "No Warranty"
 * statements are included in all redistributions.
 *
 * NO WARRANTY. THIS SOFTWARE IS FURNISHED ON AN "AS IS" BASIS.
 * CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED AS TO THE MATTER INCLUDING, BUT NOT LIMITED
 * TO: WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY
 * OF RESULTS OR RESULTS OBTAINED FROM USE OF THIS SOFTWARE. CARNEGIE
 * MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT
 * TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.
 */

/*
 * DiskSim Storage Subsystem Simulation Environment
 * Authors: Greg Ganger, Bruce Worthington, Yale Patt
 *
 * Copyright (C) 1993, 1995, 1997 The Regents of the University of Michigan 
 *
 * This software is being provided by the copyright holders under the
 * following license. By obtaining, using and/or copying this software,
 * you agree that you have read, understood, and will comply with the
 * following terms and conditions:
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * and its documentation for any purpose and without fee or royalty is
 * hereby granted, provided that the full text of this NOTICE appears on
 * ALL copies of the software and documentation or portions thereof,
 * including modifications, that you make.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS," AND COPYRIGHT HOLDERS MAKE NO
 * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY OF EXAMPLE,
 * BUT NOT LIMITATION, COPYRIGHT HOLDERS MAKE NO REPRESENTATIONS OR
 * WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR
 * THAT THE USE OF THE SOFTWARE OR DOCUMENTATION WILL NOT INFRINGE ANY
 * THIRD PARTY PATENTS, COPYRIGHTS, TRADEMARKS OR OTHER RIGHTS. COPYRIGHT
 * HOLDERS WILL BEAR NO LIABILITY FOR ANY USE OF THIS SOFTWARE OR
 * DOCUMENTATION.
 *
 *  This software is provided AS IS, WITHOUT REPRESENTATION FROM THE
 * UNIVERSITY OF MICHIGAN AS TO ITS FITNESS FOR ANY PURPOSE, AND
 * WITHOUT WARRANTY BY THE UNIVERSITY OF MICHIGAN OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE REGENTS
 * OF THE UNIVERSITY OF MICHIGAN SHALL NOT BE LIABLE FOR ANY DAMAGES,
 * INCLUDING SPECIAL , INDIRECT, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
 * WITH RESPECT TO ANY CLAIM ARISING OUT OF OR IN CONNECTION WITH THE
 * USE OF OR IN CONNECTION WITH THE USE OF THE SOFTWARE, EVEN IF IT HAS
 * BEEN OR IS HEREAFTER ADVISED OF THE POSSIBILITY OF SUCH DAMAGES
 *
 * The names and trademarks of copyright holders or authors may NOT be
 * used in advertising or publicity pertaining to the software without
 * specific, written prior permission. Title to copyright in this software
 * and any associated documentation will at all times remain with copyright
 * holders.
 */


/***************************************************************************
  This is a fairly simple module for managing a device that is being used
  as a cache for another device.  It does not have many functionalities
  that a real device-caching-device would have, such as
	1. No actual "cache"-iness.  That is, it simply maps given locations
	   to the same locations on the cache device.  This limits the max
	   amount of real device space that can be cached, and misses
	   opportunities for creating cache-device locality where none
	   exists in the original workload.
	2. No prefetching.
	3. No optimization.  For example, see #1.  Also, no grouping of
	   writes to cache-device.  Also, no going to original device when
	   cache-device is busy.
	4. No locking.  Specifically, requests for the same space can be in
	   progress in parallel.  This could cause inconsistencies, with
	   unfortunate sequencing.
	5. No buffer space limitations.  Specifically, there is no limit on
	   the amount of buffer space used at once for managing the cache
	   and real devices.
***************************************************************************/

/* shouln't we be able to #include disksim_cache.h here?? */
#define CACHE_DEVICE    2

#include "disksim_global.h"
#include "disksim_iosim.h"
#include "disksim_ioqueue.h"
#include "disksim_cachedev.h"
#include "config.h"


/* cache event types */

#define CACHE_EVENT_IOREQ               0
#define CACHE_EVENT_READ                1
#define CACHE_EVENT_POPULATE_ONLY       2
#define CACHE_EVENT_POPULATE_ALSO       3
#define CACHE_EVENT_WRITE               4
#define CACHE_EVENT_FLUSH               5
#define CACHE_EVENT_IDLEFLUSH_READ      6
#define CACHE_EVENT_IDLEFLUSH_FLUSH     7

/* cache write schemes */

#define CACHE_WRITE_MIN         1
#define CACHE_WRITE_SYNCONLY    1
#define CACHE_WRITE_THRU        2
#define CACHE_WRITE_BACK        3
#define CACHE_WRITE_MAX         3

/* cache background flush types */

#define CACHE_FLUSH_MIN         0
#define CACHE_FLUSH_DEMANDONLY  0
#define CACHE_FLUSH_PERIODIC    1
#define CACHE_FLUSH_MAX         1


typedef struct cacheevent {
   double time;
   int type;
   struct cacheevent *next;
   struct cacheevent *prev;
   void (**donefunc)(void *,ioreq_event *);	/* Function to call when complete */
   void *doneparam;		/* parameter for donefunc */
   int flags;
   ioreq_event *req;
   struct cacheevent *waitees;
   int validpoint;
} cache_event;

typedef struct {
   int reads;
   int readblocks;
   int readhitsfull;
   int readmisses;
   int popwrites;
   int popwriteblocks;
   int writes;
   int writeblocks;
   int writehitsfull;
   int writemisses;
   int destagereads;
   int destagereadblocks;
   int destagewrites;
   int destagewriteblocks;
   int maxbufferspace;
} cache_stats;


typedef struct cache_def {
   int cachetype;       /* all caches must start with an integer type */
   void (**issuefunc)(void *,ioreq_event *);	/* to issue a disk access    */
   void *issueparam;				/* first param for issuefunc */
   struct ioq * (**queuefind)(void *,int);	/* to get ioqueue ptr for dev*/
   void *queuefindparam;			/* first param for queuefind */
   void (**wakeupfunc)(void *,struct cacheevent *);	/* to re-activate slept proc */
   void *wakeupparam;				/* first param for wakeupfunc */
   int size;					/* in 512B blks  */
   int cache_devno;				/* device used for cache */
   int real_devno;				/* device for which cache is used */
   int maxreqsize;
   int writescheme;
   int flush_policy;
   double flush_period;
   double flush_idledelay;
   int bufferspace;
   cache_event *ongoing_requests;
   bitstr_t *validmap;
   bitstr_t *dirtymap;
   cache_stats stat;
   char *name;
} cache_def;


int cachedev_get_cachetype (cache_def *cache)
{  
   ASSERT (cache != NULL);
   return(cache->cachetype);
}


int cachedev_get_maxreqsize (cache_def *cache)
{
   if (cache) {
      return(cache->maxreqsize);
   }
   return(0);
}


static void cachedev_empty_donefunc (void *doneparam, ioreq_event *req)
{
   addtoextraq((event *) req);
}


static void cachedev_add_ongoing_request (cache_def *cache, cache_event *cachereq)
{
   cachereq->next = cache->ongoing_requests;
   cachereq->prev = NULL;
   if (cachereq->next) {
      cachereq->next->prev = cachereq;
   }
   cache->ongoing_requests = cachereq;
}


static void cachedev_remove_ongoing_request (cache_def *cache, cache_event *cachereq)
{
   if (cachereq->next) {
      cachereq->next->prev = cachereq->prev;
   }
   if (cachereq->prev) {
      cachereq->prev->next = cachereq->next;
   }
   if (cache->ongoing_requests == cachereq) {
      cache->ongoing_requests = cachereq->next;
   }
}


static cache_event * cachedev_find_ongoing_request (cache_def *cache, ioreq_event *req)
{
   cache_event *tmp = cache->ongoing_requests;

   /* Is this enough to ensure equivalence?? */
   while ((tmp != NULL) && ((req->opid != tmp->req->opid) || (req->blkno != tmp->req->blkno) || (req->bcount != tmp->req->bcount) || (req->buf != tmp->req->buf))) {
      tmp = tmp->next;
   }

   return (tmp);
}


/* Return a count of how many dirty blocks are on the cachedev. */
static int cachedev_count_dirty_blocks (cache_def *cache)
{
   int dirtyblocks = 0;
   int i;

   for (i=0; i<cache->size; i++) {
      if (bit_test(cache->dirtymap,i)) {
         dirtyblocks++;
      }
   }
   return (dirtyblocks);
}


static void cachedev_setbits (bitstr_t *bitmap, ioreq_event *req)
{
   bit_nset (bitmap, req->blkno, (req->blkno+req->bcount-1));
}


static void cachedev_clearbits (bitstr_t *bitmap, ioreq_event *req)
{
   bit_nclear (bitmap, req->blkno, (req->blkno+req->bcount-1));
}


static int cachedev_isreadhit (cache_def *cache, ioreq_event *req)
{
   int lastblk = req->blkno + req->bcount;
   int i;

   if (lastblk >= cache->size) {
      return (0);
   }

   for (i=req->blkno; i<lastblk; i++) {
      if (bit_test(cache->validmap,i) == 0) {
         return (0);
      }
   }

   return (1);
}


static int cachedev_iswritehit (cache_def *cache, ioreq_event *req)
{
   if ((req->blkno+req->bcount) >= cache->size) {
      return (0);
   }
   return (1);
}


static int cachedev_find_dirty_cache_blocks (cache_def *cache, int *blknoPtr, int *bcountPtr)
{
   int blkno;

   bit_ffs (cache->dirtymap, cache->size, blknoPtr);
   if (*blknoPtr == -1) {
      return (0);
   }

   blkno = *blknoPtr;
   while (bit_test (cache->dirtymap, blkno) != 0) {
      blkno++;
   }
   *bcountPtr = blkno - *blknoPtr;

   return (1);
}


static void cachedev_periodic_callback (timer_event *timereq)
{
   fprintf (stderr, "cachedev_periodic_callback not yet supported\n");
   ASSERT (0);
   exit (0);
}


static void cachedev_idlework_callback (void *idleworkparam, int idledevno)
{
   cache_def *cache = idleworkparam;
   cache_event *flushdesc;
   ioreq_event *flushreq;
   int blkno, bcount;
   struct ioq *queue;

   ASSERT (idledevno == cache->real_devno);

   queue = (*cache->queuefind)(cache->queuefindparam, cache->real_devno);
   if (ioqueue_get_number_in_queue (queue) != 0) {
      return;
   }

   queue = (*cache->queuefind)(cache->queuefindparam, cache->cache_devno);
   if (ioqueue_get_number_in_queue (queue) != 0) {
      return;
   }

   if (cachedev_find_dirty_cache_blocks (cache, &blkno, &bcount) == 0) {
      return;
   }

   /* Just assume that bufferspace is available */
   cache->bufferspace += bcount;
   if (cache->bufferspace > cache->stat.maxbufferspace) {
      cache->stat.maxbufferspace = cache->bufferspace;
   }

   flushdesc = (cache_event *) getfromextraq();
   flushdesc->type = CACHE_EVENT_IDLEFLUSH_READ;
   flushreq = (ioreq_event *) getfromextraq();
   flushreq->buf = flushdesc;
   flushreq->devno = cache->cache_devno;
   flushreq->blkno = blkno;
   flushreq->bcount = bcount;
   flushreq->type = IO_ACCESS_ARRIVE;
   flushreq->flags = READ;
   (*cache->issuefunc)(cache->issueparam, flushreq);
   cache->stat.destagereads++;
   cache->stat.destagereadblocks += bcount;
}


/* Gets the appropriate block, locked and ready to be accessed read or write */

int cachedev_get_block (cache_def *cache, ioreq_event *req, void (**donefunc)(void *, ioreq_event *), void *doneparam)
{
   cache_event *rwdesc = (cache_event *) getfromextraq();