disksim_redun.c

来自「disksim是一个非常优秀的磁盘仿真工具」· C语言 代码 · 共 1,296 行 · 第 1/3 页

/*
 * DiskSim Storage Subsystem Simulation Environment (Version 4.0)
 * Revision Authors: John Bucy, Greg Ganger
 * Contributors: John Griffin, Jiri Schindler, Steve Schlosser
 *
 * Copyright (c) of Carnegie Mellon University, 2001-2008.
 *
 * 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_stat.h"
#include "disksim_iosim.h"
#include "disksim_orgface.h"
#include "disksim_logorg.h"
#include "disksim_ioqueue.h"


static int logorg_modulus_update (int inc, int val, int maxval)
{
   int ret;

   ret = val + inc;
   if (ret < 0) {
      ret += maxval;
   } else if (ret >= maxval) {
      ret -= maxval;
   }
   return(ret);
}


int logorg_tabular_rottype (int maptype, int reduntype, int rottype, int stripeunit)
{
   if (reduntype != PARITY_ROTATED) {
      return(FALSE);
   }
   if (maptype != STRIPED) {
      return(FALSE);
   }
   if (stripeunit == 0) {
      return(FALSE);
   }
   switch (rottype) {
      case PARITY_LEFT_SYM:
      case PARITY_LEFT_ASYM:
      case PARITY_RIGHT_SYM:
      case PARITY_RIGHT_ASYM:
      return(TRUE);
   }
   return(FALSE);
}


static void logorg_parity_rotate_ideal (logorg *currlogorg, ioreq_event *curr)
{
   if (curr->flags & READ) {
      return;
   }
   curr->next = ioreq_copy(curr);
   curr->next->devno = currlogorg->idealno;
   currlogorg->idealno = (currlogorg->idealno + 1) % currlogorg->numdisks;
}


static void logorg_parity_rotate_random (logorg *currlogorg, ioreq_event *curr)
{
   if (curr->flags & READ) {
      return;
   }
   curr->next = ioreq_copy(curr);
   while (curr->next->devno == curr->devno) {
      curr->next->devno = (int)((double)currlogorg->numdisks * DISKSIM_drand48());
   }
}


static int logorg_shadowed_get_short_dist (logorg *currlogorg, ioreq_event *curr, int numtocheck, int *checklist)
{
   int i, j;
   int dist;
   int shortdev = -1;
   int shortdist = 999999999;
   int ties[MAXCOPIES];
   int no;

   j = -1;
   for (i = 0; i < numtocheck; i++) {
      no = checklist[i];
      dist = ioqueue_get_dist(currlogorg->devs[(curr->devno + (no * currlogorg->numdisks))].queue, (curr->blkno + currlogorg->devs[(curr->devno + (no * currlogorg->numdisks))].startblkno));
      if (dist >= 999999999) {
	 fprintf(stderr, "Haven't allowed for large enough 'dist's in logorg_shadowed_get_short_dist - %d\n", dist);
	 exit(1);
      }
      if (dist == shortdist) {
	 j++;
	 if (j >= MAXCOPIES) {
	    fprintf(stderr, "Haven't allowed for enough ties in logorg_shadowed_get_short_dist - %d\n", j);
	    exit(1);
	 }
	 ties[j] = no;
      }
      if (dist < shortdist) {
	 shortdist = dist;
	 shortdev = no;
	 j = -1;
      }
   }
   if (shortdev == -1) {
      fprintf(stderr, "Illegal condition in logorg_shadowed_get_short_dist\n");
      exit(1);
   } else if (j != -1) {
      i = (int) (DISKSIM_drand48() * (double) (j+2));
      if (i != 0) {
	 shortdev = ties[(i-1)];
      }
   }
   return(shortdev);
}


static int logorg_shadowed_get_short_queue (logorg *currlogorg, ioreq_event *curr, int def)
{
   int i, j;
   int len;
   int shortdev = -1;
   int shortlen = 999999999;
   int ties[MAXCOPIES];

   j = -1;
   for (i = 0; i < currlogorg->copies; i++) {
      len = ioqueue_get_number_in_queue(currlogorg->devs[(curr->devno + (i * currlogorg->numdisks))].queue);
      if (len >= 999999999) {
	 fprintf(stderr, "Haven't allowed for large enough 'dist's in logorg_shadowed_get_short_queue - %d\n", len);
	 exit(1);
      }
      if (len == shortlen) {
	 j++;
	 if (j >= MAXCOPIES) {
	    fprintf(stderr, "Haven't allowed for enough ties in logorg_shadowed_get_short_queue - %d\n", j);
	    exit(1);
	 }
	 ties[j] = i;
      }
      if (len < shortlen) {
	 shortlen = len;
	 shortdev = i;
	 j = -1;
      }
   }
   if (shortdev == -1) {
      fprintf(stderr, "Illegal condition in logorg_shadowed_get_short_queue\n");
      exit(1);
   } else if (j != -1) {
      if (def == 1) {
         i = (int) (DISKSIM_drand48() * (double) (j+2));
         if (i != 0) {
	    shortdev = ties[(i-1)];
         }
      } else if (def == 2) {
	 j++;
	 ties[j] = shortdev;
	 shortdev = logorg_shadowed_get_short_dist(currlogorg, curr, (j+1), ties);
      } else {
	 fprintf(stderr, "Unknown default tie breaker in logorg_shadowed_get_short_queue - %d\n", def);
	 exit(1);
      }
   }
   return(shortdev);
}


int logorg_shadowed (logorg *currlogorg, ioreq_event *curr, int numreqs)
{
   int i, j;
   ioreq_event *temp;
   ioreq_event *newreq;
   int checklist[MAXCOPIES];

   temp = curr;
   if (curr->flags & READ) {
      for (i = 0; i < numreqs; i++) {
	 switch (currlogorg->copychoice) {
	    case SHADOW_PRIMARY:
/* May want to move head on secondary device */
			  break;
	    case SHADOW_RANDOM:
			  temp->devno += currlogorg->numdisks * (int) (DISKSIM_drand48() * (double) currlogorg->copies);
			  break;
	    case SHADOW_ROUNDROBIN:
			  temp->devno += currlogorg->numdisks * currlogorg->reduntoggle;
			  currlogorg->reduntoggle++;
			  currlogorg->reduntoggle %= currlogorg->copies;
			  break;
	    case SHADOW_SHORTDIST:
			  for (j = 0; j < currlogorg->copies; j++)
			     checklist[j] = j;
			  temp->devno += currlogorg->numdisks * logorg_shadowed_get_short_dist(currlogorg, temp, currlogorg->copies, checklist);
			  break;
	    case SHADOW_SHORTQUEUE:
			  temp->devno += currlogorg->numdisks * logorg_shadowed_get_short_queue(currlogorg, temp, 1);
			  break;
	    case SHADOW_SHORTQUEUE2:
			  temp->devno += currlogorg->numdisks * logorg_shadowed_get_short_queue(currlogorg, temp, 2);
			  break;
	    default:
		    fprintf(stderr, "Unknown shadow choice type at logorg_shadowed\n");
		    exit(1);
	 }
	 temp = temp->next;
      }
      return(numreqs);
   } else {
      for (i = 0; i < numreqs; i++) {
         for (j = 1; j < currlogorg->copies; j++) {
            newreq = ioreq_copy(temp);
            temp->next = newreq;
            newreq->devno += currlogorg->numdisks;
            temp = newreq;
         }
	 temp = temp->next;
      }
      return(currlogorg->copies * numreqs);
   }
}


int logorg_parity_disk (logorg *currlogorg, ioreq_event *curr, int numreqs)
{
   depends *depend;

   if (curr->flags & READ) {
      return(numreqs);
   }
   if ((currlogorg->maptype == STRIPED) && (currlogorg->stripeunit == 0)) {
      curr->next = ioreq_copy(curr);
      curr->next->devno = currlogorg->numdisks;
      return(numreqs+1);
   }
   if (numreqs != 1) {
      fprintf(stderr, "Too many reqs at logorg_parity_disk - %d\n", numreqs);
      exit(1);
   }
   depend = (depends *) getfromextraq();
   depend->blkno = curr->blkno;
   depend->devno = curr->devno;
   depend->numdeps = 2;
   depend->deps[0] = ioreq_copy(curr);
   depend->deps[1] = ioreq_copy(curr);
   depend->deps[0]->opid = 2;
   depend->deps[0]->devno = currlogorg->numdisks;
   depend->next = (depends *) getfromextraq();
   depend->next->next = NULL;
   depend->next->blkno = curr->blkno;
   depend->next->devno = currlogorg->numdisks;
   depend->next->deps[0] = depend->deps[0];
   depend->next->deps[1] = depend->deps[1];
   if (currlogorg->writesync == TRUE) {
      depend->deps[1]->opid = 2;
      depend->next->numdeps = 2;
   } else {
      depend->deps[1]->opid = 1;
      depend->next->numdeps = 1;
   }
   curr->flags |= READ;
   curr->next = ioreq_copy(curr);
   curr->next->devno = currlogorg->numdisks;
   curr->prev = (ioreq_event *) depend;
   return(4);
}


static int logorg_parity_rotate_updates (logorg *currlogorg, ioreq_event *curr, int inc)
{
   int reqs = 2;
   int parityno;
   int blksleft;
   int bcount;
   ioreq_event *newreq;
   int parityunit;
   int numdisks;
   int devno;
   int parityblock;

   parityunit = currlogorg->parityunit;
   numdisks = currlogorg->numdisks;

   parityblock = curr->blkno / (parityunit * (numdisks - 1));
   parityno = (curr->blkno % (parityunit * (numdisks - 1))) / parityunit;
   curr->blkno += parityblock * parityunit;
   if (inc == -1) {
      devno = numdisks - (parityno % numdisks) - 1;
   } else {
      devno = parityno % numdisks;
   }
   if (((inc == 1) && (curr->devno <= devno)) || ((inc == -1) && (curr->devno >=devno))) {
      curr->blkno += parityunit;
      devno = logorg_modulus_update(inc, devno, numdisks);
      parityno++;
   }
   blksleft = parityunit - (curr->blkno % currlogorg->parityunit);
   bcount = curr->bcount;
   if ((parityunit != currlogorg->parityunit) && ((bcount > blksleft) || (parityunit > currlogorg->parityunit))) {
      fprintf(stderr, "Failed integrity check in logorg_parity_rotate_left\n");
      exit(1);
   }
   while (bcount > blksleft) {
      if (!(curr->flags & READ)) {
         newreq = ioreq_copy(curr);
         newreq->devno = devno;
         newreq->bcount = blksleft;
         newreq->blkno = curr->blkno + curr->bcount - bcount;
         newreq->next = curr->next;
         curr->next = newreq;
         reqs++;
      }
      bcount -= blksleft;
      devno = logorg_modulus_update(inc, devno, numdisks);
      if (devno == curr->devno) {
	 curr->bcount += parityunit;
         devno = logorg_modulus_update(inc, devno, numdisks);
	 parityno++;
      }
      parityno++;
      blksleft = parityunit;
   }
   if (curr->flags & READ) {
      return(1);
   }
   newreq = ioreq_copy(curr);
   newreq->devno = devno;
   newreq->blkno = curr->blkno + curr->bcount - bcount;
   newreq->bcount = bcount;
   newreq->next = curr->next;
   curr->next = newreq;
   if (parityno > currlogorg->numfull) {
      fprintf(stderr, "Integrity check failure in logorg_parity_rotate_left\n");
      exit(1);
   }
   return(reqs);
}