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

#include "disksim_global.h"
#include "disksim_iosim.h"
#include "disksim_stat.h"
#include "disksim_disk.h"


/* This variable is now in the diskinfo structure, but the real question */
/* is why it exists at all...                                            */
//int LRU_at_seg_list_head = 0;


#if 0
static int disk_buffer_segment_wrap_needed (segment *seg, int endblkno)
{
   return(seg->startblkno < (endblkno - seg->size));
}
#endif


void disk_buffer_segment_wrap (segment *seg, int endblkno)
{
   seg->startblkno = max(seg->startblkno, (endblkno - seg->size));
}


/* Determines whether the iorequest passed in overlaps in any way with the given
 * segment in the cache -rcohen
 */

int disk_buffer_overlap (segment *seg, ioreq_event *curr)
{
   int tmp;

   if ((curr->blkno >= seg->startblkno) && (curr->blkno < seg->endblkno)) {
      return(TRUE);
   }

   tmp = curr->blkno + curr->bcount;
   if ((tmp > seg->startblkno) && (tmp <= seg->endblkno)) {
      return(TRUE);
   }

   if ((curr->blkno <= seg->startblkno) && (tmp >= seg->endblkno)) {
      return(TRUE);
   }

   return(FALSE);
}


void disk_buffer_remove_from_seg (diskreq *currdiskreq)
{
   segment *seg = currdiskreq->seg;

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "%12.6f  %8p  Entering disk_buffer_remove_from_seg\n",simtime,currdiskreq);
fflush(outputfile);
}

   ASSERT(seg != NULL);

   if (seg->diskreqlist == currdiskreq) {
      seg->diskreqlist = currdiskreq->seg_next;
   } else {
      diskreq *tmpdiskreq = seg->diskreqlist;

      while (tmpdiskreq) {
	 if (tmpdiskreq->seg_next == currdiskreq) {
	    tmpdiskreq->seg_next = currdiskreq->seg_next;
	    break;
	 }
	 tmpdiskreq = tmpdiskreq->seg_next;
      }
      ASSERT(tmpdiskreq != NULL);
   }
   currdiskreq->seg = NULL;

   ASSERT1((seg->diskreqlist || seg->state != BUFFER_DIRTY),"seg->state",seg->state);
}


/* return real or effective owner of segment or NULL.  For effective, a 
   READ segment OWNER may be overridden by a READ with an outblkno that 
   is less than the (effective) OWNER's outblkno
*/

diskreq* disk_buffer_seg_owner (segment *seg, int effective)
{
   diskreq *seg_owner = seg->diskreqlist;
   diskreq *tmpdiskreq = seg->diskreqlist;

   while (seg_owner) {
      if (seg_owner->flags & SEG_OWNED) {
	 break;
      }
      seg_owner = seg_owner->seg_next;
   }

   if (effective && seg->access && (seg->access->flags & READ)) {
      while (tmpdiskreq) {
	 if ((seg->recyclereq != tmpdiskreq) &&
	     (!tmpdiskreq->ioreqlist || 
	      (tmpdiskreq->ioreqlist->flags & READ))) {
	    if (!seg_owner || tmpdiskreq->outblkno < seg_owner->outblkno) {
	       seg_owner = tmpdiskreq;
/*
	       fprintf(stderr,"%.6f  effective seg_owner found\n",simtime);fflush(stderr);
*/
	    }
	 }
	 tmpdiskreq = tmpdiskreq->seg_next;
      }
   }

   return(seg_owner);
}


/* A recyclable/reusable segment has a single diskreq.  That diskreq must be a 
   read which has all of its remaining data in the segment or a write which 
   only needs to send completion up the line.
*/

int disk_buffer_reusable_segment_check (disk *currdisk, segment *currseg)
{
   diskreq *currdiskreq = currseg->diskreqlist;
   ioreq_event *currioreq;

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "%12.6f            Entering disk_buffer_reusable_segment_check\n",simtime);
fflush(outputfile);
}

   if (currdisk->acctime < 0.0 && !currseg->recyclereq && currdiskreq && 
       !currdiskreq->seg_next && currdiskreq->ioreqlist && 
       !(currdiskreq->flags & COMPLETION_RECEIVED)) {
      if (currdiskreq->ioreqlist->flags & READ) {
         currioreq = currdiskreq->ioreqlist;
         while (currioreq->next) {
            currioreq = currioreq->next;
         }
         if ((currdiskreq->outblkno >= currseg->startblkno) &&
             (currdiskreq->outblkno <  currseg->endblkno) &&
             ((currioreq->blkno + currioreq->bcount) > currseg->startblkno) &&
             ((currioreq->blkno + currioreq->bcount) <= currseg->endblkno)) {
            if (!(currdiskreq->flags & SEG_OWNED)) {
               disk_buffer_attempt_seg_ownership(currdisk,currdiskreq);
            }

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "                        segment %8p is reusable\n",currseg);
fflush(outputfile);
}

            return(TRUE);
         }
      } else {			/* WRITE */
         currioreq = currdiskreq->ioreqlist;
         while (currioreq->next) {
            currioreq = currioreq->next;
         }
         if (currdiskreq->inblkno >= (currioreq->blkno + currioreq->bcount)) {
            if (!(currdiskreq->flags & SEG_OWNED)) {
               disk_buffer_attempt_seg_ownership(currdisk,currdiskreq);
            }

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "                        segment %8p is reusable\n",currseg);
fflush(outputfile);
}

            return(TRUE);
         }
      }
   }

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "                        segment %8p is NOT reusable\n",currseg);
fflush(outputfile);
}

   return(FALSE);
}


static int disk_buffer_recyclable_segment_check (disk *currdisk, segment *currseg, int isread)
{
   diskreq *currdiskreq = currseg->diskreqlist;
   ioreq_event *currioreq;

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "%12.6f            Entering disk_buffer_recyclable_segment_check\n",simtime);
fflush(outputfile);
}

   if (currdisk->acctime < 0.0 && !currseg->recyclereq && currdiskreq && 
       !currdiskreq->seg_next && currdiskreq->ioreqlist && 
       !(currdiskreq->flags & COMPLETION_RECEIVED)) {
      if (currdiskreq->ioreqlist->flags & READ) {
         if (isread || 
	     (!currdisk->dedicatedwriteseg && 
	      (currdisk->numdirty < currdisk->numwritesegs))) {
            currioreq = currdiskreq->ioreqlist;
            while (currioreq->next) {
               currioreq = currioreq->next;
            }
            if ((currdiskreq->outblkno >= currseg->startblkno) &&
                (currdiskreq->outblkno <  currseg->endblkno) &&
                ((currioreq->blkno + currioreq->bcount) > currseg->startblkno) &&
                ((currioreq->blkno + currioreq->bcount) <= currseg->endblkno)) {
               if (!(currdiskreq->flags & SEG_OWNED)) {
                  disk_buffer_attempt_seg_ownership(currdisk,currdiskreq);
               }

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "                        segment %8p is recyclable\n",currseg);
fflush(outputfile);
}

               return(TRUE);
	    }
         }
      } else {			/* WRITE */
	 if (!isread || !currdisk->dedicatedwriteseg) {
            currioreq = currdiskreq->ioreqlist;
	    while (currioreq->next) {
	       currioreq = currioreq->next;
	    }
	    if (currdiskreq->inblkno >= (currioreq->blkno + currioreq->bcount)) {
               if (!(currdiskreq->flags & SEG_OWNED)) {
	          disk_buffer_attempt_seg_ownership(currdisk,currdiskreq);
	       }

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "                        segment %8p is recyclable\n",currseg);
fflush(outputfile);
}

               return(TRUE);
	    }
	 }
      }
   }

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "                        segment %8p is NOT recyclable\n",currseg);
fflush(outputfile);
}

   return(FALSE);
}


segment* disk_buffer_recyclable_segment (disk *currdisk, int isread)
{
   segment *currseg = currdisk->seglist;

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "%12.6f            Entering disk_buffer_recyclable_segment\n",simtime);
fprintf (outputfile, "                        numdirty = %d\n", currdisk->numdirty);
fflush(outputfile);
}

   if (currdisk->acctime >= 0.0) {
      return(NULL);
   }

   while (currseg) {
      if (disk_buffer_recyclable_segment_check(currdisk, currseg, isread)) {

if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf (outputfile, "                        recyclable segment found\n");
fflush(outputfile);
}

	 return(currseg);
      }
      currseg = currseg->next;
   }


if (disk_printhack && (simtime >= disk_printhacktime)) {
fprintf(outputfile, "                        No recyclable segment found\n");
fflush(outputfile);
}

   return(NULL);
}


/* if BUFFER_READING, checks to see if cache can and should "fit in" blkno.
   if BUFFER_WRITING, checks to see if blkno is in the cache and can be
     written to media.
*/

int disk_buffer_block_available (disk *currdisk, segment *seg, int blkno)
{
   diskreq *seg_owner;

   if (blkno < 0) {
      return(FALSE);
   }
   if (seg->state == BUFFER_READING) {
      if ((blkno < seg->endblkno) && (blkno >= seg->startblkno)) {
	 return(FALSE);
      }
      if ((blkno < seg->startblkno) && 
	  ((!currdisk->readanyfreeblocks) ||
	   (seg->endblkno != seg->startblkno))) {
         return(FALSE);
      }
      seg_owner = disk_buffer_seg_owner(seg,TRUE);
      if (seg_owner && !(seg_owner->flags & COMPLETION_SENT) && 
	  ((blkno - seg_owner->outblkno) >= seg->size)) {
         return(FALSE);
      }
   } else if (seg->state == BUFFER_WRITING) {
      if ((blkno < currdisk->effectivehda->inblkno) || 
	  (blkno >= seg->endblkno)) {
	 return(FALSE);
      }
      if ((currdisk->effectivehda->ioreqlist) && 
	  (currdisk->extra_write_disconnect)) {
	 if (currdisk->effectivehda->ioreqlist->bcount < 45) {
	    if ((seg->endblkno - seg->startblkno) <