layout_g1.c

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

/* diskmodel (version 1.0)
 * 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.  
 */



#include "layout_g1.h"
#include "marshall.h"

#define max(x,y) (((x) > (y)) ? (x) : (y))

/*
 * 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"
// #include "disksim_disk.h"


// Compute start + mult*q and add x for the number of times it 
// wraps around 0.  This can probably be optimized.
static inline dm_angle_t 
addmult(dm_angle_t start, int mult, dm_angle_t q, dm_angle_t x) 
{
  int c;
  dm_angle_t result = start;
  long long tmp = (long long)start + mult * (long long)q;
  long long max = (long long)1 << 32;
  


/*    for(c = 0; c < mult; c++) { */
/*      tmp = result + q; */
/*      if(tmp < result) { */
/*        result = tmp + x; */
/*      } */
/*      else { */
/*        result = tmp; */
/*      } */
/*    } */
  
  return result + mult * q + (tmp / max) * x;
}

// optimize these someday (binsearch, maybe)
static struct dm_layout_g1_band *
find_band_lbn(struct dm_layout_g1 *l, int lbn)
{
  struct dm_layout_g1_band *b = &l->bands[0];
  int bandstart = 0;
  int bandno = 0;

  while((lbn >= b->blksinband) || (lbn < 0)) {
    bandstart += b->blksinband;
    lbn -= b->blksinband;
    bandno++;
    b = &l->bands[bandno];
    ddbg_assert(bandno < l->bands_len);
    ddbg_assert(lbn >= 0);
  }
  
  return b;
}

static int 
g1_st_lbn(struct dm_disk_if *d, int lbn) {
  struct dm_layout_g1 *l = (struct dm_layout_g1 *)d->layout;
  struct dm_layout_g1_band *b = find_band_lbn(l, lbn);
  return b->blkspertrack;
}


static struct dm_layout_g1_band *
find_band_pbn(struct dm_layout_g1 *l, struct dm_pbn *p)
{
  int c;
  for(c = 0; c < l->bands_len; c++) {
    if((p->cyl >= l->bands[c].startcyl) &&
       (p->cyl <= l->bands[c].endcyl)) 
      {
	return &l->bands[c];
      }
  }

  ddbg_assert2(0, "band not found!");
  return 0;
}


static int 
g1_st_pbn(struct dm_disk_if *d, struct dm_pbn *p) {
  struct dm_layout_g1 *l = (struct dm_layout_g1 *)d->layout;
  struct dm_layout_g1_band *b = find_band_pbn(l, p);
  return b->blkspertrack;
}




static int g1_surfno_on_cyl(struct dm_layout_g1 *d,
			    struct dm_layout_g1_band *b, 
			    struct dm_pbn *p)
{

  switch(d->mapping) {
  case LAYOUT_CYLSWITCHONSURF1:
    if((p->cyl - b->startcyl) % 2) {
      return (d->disk->dm_surfaces - p->head - 1);
    }  
    break;

  case LAYOUT_CYLSWITCHONSURF2:
    if(p->cyl % 2) {
      return (d->disk->dm_surfaces - p->head - 1);
    }
    break;

  default:
  }
  return p->head;
}


static dm_angle_t
g1_map_pbn_skew(struct dm_disk_if *d, 
		struct dm_pbn *p)
{
  struct dm_layout_g1 *l = (struct dm_layout_g1 *)d->layout;
  struct dm_pbn pbn = *p;
  struct dm_layout_g1_band *b = find_band_pbn(l, p);
  int trackswitches;

  dm_angle_t result = b->firstblkangle;

  int slipoffs = 0;



  switch (l->mapping) {
  case LAYOUT_NORMAL:
  case LAYOUT_CYLSWITCHONSURF1:
  case LAYOUT_CYLSWITCHONSURF2:
    {
      int c;
      // relative to the start of the zone...
      int cylno = p->cyl - b->startcyl;
      pbn.cyl -= b->startcyl;
      pbn.head = g1_surfno_on_cyl(l, b, p);
      
      trackswitches = pbn.head + (d->dm_surfaces - 1) * pbn.cyl;

      result = addmult(result, trackswitches, b->trackskew, b->trkspace);
      result = addmult(result, pbn.cyl, b->cylskew, b->trkspace);

      /* The following assumes that slips also push skew forward in
       * some schemes 
       */
      if ((issectpercyl(l)) 
	  || (l->sparescheme == SECTPERTRACK_SPARING)) {
	
	int tracks = cylno * d->dm_surfaces;
	int cutoff;
	int i;
	
	if (l->sparescheme == SECTPERTRACK_SPARING) {
	  tracks += p->head;
	}
	cutoff = tracks * b->blkspertrack;
	for (i = 0; i < b->numslips; i++) {
	  if (b->slip[i] < cutoff) {
	    slipoffs++;
	  }
	}
      }
      result = addmult(result, slipoffs, b->sector_width, b->trkspace);
      
    }
    break;


  default:
    ddbg_assert(0);
  }

  result = addmult(result, pbn.sector, b->sector_width, b->trkspace);

  return result;
}
		     

dm_angle_t g1_get_track_0l(struct dm_disk_if *d, 
			   struct dm_mech_state *track)
{
  struct dm_layout_g1 *l = (struct dm_layout_g1 *)d->layout;
  struct dm_pbn pbn;
  struct dm_layout_g1_band *b;
  int trackswitches;
  dm_angle_t result;
  int slipoffs = 0;
  
  pbn.head = track->head;
  pbn.cyl = track->cyl;
  pbn.sector = 0;

  return d->layout->dm_pbn_skew(d, &pbn);
}




void
g1_convert_ptoa(struct dm_disk_if *d, 
		struct dm_pbn *p,
		dm_angle_t *angle,
		dm_angle_t *width)
{
  struct dm_layout_g1 *l = (struct dm_layout_g1 *)d->layout;
  struct dm_pbn pbn = *p;
  struct dm_layout_g1_band *b = find_band_pbn(l, p);

  dm_angle_t result = b->firstblkangle;

  int slipoffs = 0;

  p = &pbn;

  switch (l->mapping) {
  case LAYOUT_NORMAL:
  case LAYOUT_CYLSWITCHONSURF1:
  case LAYOUT_CYLSWITCHONSURF2:
    p->cyl -= b->startcyl;

    /* The following assumes that slips also push skew forward in
     * some schemes 
     */
    if ((issectpercyl(l)) 
	|| (l->sparescheme == SECTPERTRACK_SPARING)) {

      int tracks = p->cyl * d->dm_surfaces;
      int cutoff;
      int i;
 
      if (l->sparescheme == SECTPERTRACK_SPARING) {
	tracks += p->head;
      }
      cutoff = tracks * b->blkspertrack;
      for (i = 0; i < b->numslips; i++) {
	if (b->slip[i] < cutoff) {
	  slipoffs++;
	}
      }
    }
    result = addmult(result, slipoffs, b->sector_width, b->trkspace);
    break;


  default:
    ddbg_assert(0);
  }

  result = addmult(result, pbn.sector, b->sector_width, b->trkspace);
  

  if(angle) *angle = result;
  ddbg_assert2(width == 0, "unimplemented");
}

dm_ptol_result_t
g1_convert_atop(struct dm_disk_if *d,
		struct dm_mech_state *a,
		struct dm_pbn *result)
{
  int trackswitches;
  struct dm_pbn track;
  struct dm_layout_g1_band *b;
  dm_angle_t angle;

  int slipoffs = 0;
  struct dm_layout_g1 *l = (struct dm_layout_g1 *)d->layout;


  track.cyl = a->cyl;
  track.head = a->head;

  b = find_band_pbn(l, &track);

  angle = a->theta - b->firstblkangle;

  switch (l->mapping) {
  case LAYOUT_NORMAL:
  case LAYOUT_CYLSWITCHONSURF1:
  case LAYOUT_CYLSWITCHONSURF2:

    /* The following assumes that slips also push skew forward in
     * some schemes 
     */
    if ((issectpercyl(l)) 
	|| (l->sparescheme == SECTPERTRACK_SPARING)) {

      int tracks = track.cyl * d->dm_surfaces;
      int cutoff;
      int i;
 
      if (l->sparescheme == SECTPERTRACK_SPARING) {
	tracks -= track.head;
      }
      // count the slips
      cutoff = tracks * b->blkspertrack;
      for (i = 0; i < b->numslips; i++) {
	if (b->slip[i] < cutoff) {
	  slipoffs++;
	}
      }
    }
    // subtract out the slips
    angle -= addmult(0, slipoffs, b->sector_width, b->trkspace);
    break;


  default:
    ddbg_assert(0);
  }

  result->cyl = a->cyl;
  result->head = a->head;
  // rounds angle down to lower sector boundary
  result->sector = (angle / (b->sector_width) % b->blkspertrack);


  // XXX ... check that angle isn't a defect
  return DM_OK;
}



static dm_ptol_result_t
g1_ptol_0t(struct dm_disk_if *d, 
	   struct dm_pbn *p,
	   int *remapsector)
{
  dm_angle_t zerol;
  long long max = ((long long)1 << 32);

  struct dm_mech_state a;
  struct dm_pbn p2;
    
  struct dm_layout_g1 *l = (struct dm_layout_g1 *)d->layout;
  struct dm_layout_g1_band *b = find_band_pbn(l, p);

  a.theta = p->sector * b->sector_width;
  zerol = d->layout->dm_get_track_zerol(d, (struct dm_mech_state *)p);

  if(zerol > a.theta) {
    //    a.theta -= b->trkspace;
  }
  a.theta -= zerol;

  a.head = p->head;
  a.cyl = p->cyl;

  d->layout->dm_convert_atop(d, &a, &p2);

  return d->layout->dm_translate_ptol(d, &p2, remapsector);
}

/*
 * The next several functions compute the lbn stored in a physical
 * media sector <cyl, surf, blk>, for different sparing/mapping
 * schemes.  The returned value is a proper lbn, or DM_REMAPPED if the
 * sector is a remapped defect, or DM_SLIPPED if the sector is a
 * slipped defect or an unused spare.
 */

static dm_ptol_result_t
g1_ptol_nosparing(struct dm_disk_if *d, 
		  struct dm_pbn *p,
		  int *remapsector)

{
  struct dm_layout_g1 *l = (struct dm_layout_g1 *)d->layout;
  struct dm_layout_g1_band *b = find_band_pbn(l, p);
  int lbn = l->band_blknos[b->num];
  struct dm_pbn pbn = *p;

  p = &pbn;


  ddbg_assert(b);
  ddbg_assert(p->cyl >= 0);
  ddbg_assert(p->cyl >= b->startcyl);
  ddbg_assert(p->cyl < d->dm_cyls);
  ddbg_assert(p->head >= 0);
  ddbg_assert(p->head < d->dm_surfaces);
  ddbg_assert(p->sector >= 0);
  ddbg_assert(p->sector < b->blkspertrack);


  p->head = g1_surfno_on_cyl(l, b, p);
  
  lbn += (((p->cyl - b->startcyl) * d->dm_surfaces) + p->head) * b->blkspertrack;
  lbn += p->sector - b->deadspace;

  if(lbn < 0) {
    return DM_SLIPPED;
  }
  else {
    return lbn;
  }
}



static dm_ptol_result_t
g1_ptol_sectpertrackspare(struct dm_disk_if *d, 
			  struct dm_pbn *p,
			  int *remapsector)
{
  int i;
  int lbnspercyl;
  int firstblkoncyl;
  struct dm_layout_g1 *l = (struct dm_layout_g1 *)d->layout;
  struct dm_layout_g1_band *b = find_band_pbn(l, p);
  int lbn = l->band_blknos[b->num];
  struct dm_pbn pbn = *p;