layout_g4.c

disksim是一个非常优秀的磁盘仿真工具

/* diskmodel (version 1.1)
 * Authors: John Bucy, Greg Ganger
 * Contributors: John Griffin, Jiri Schindler, Steve Schlosser
 *
 * Copyright (c) of Carnegie Mellon University, 2003-2005
 *
 * 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 "dm.h"

#include "layout_g4.h"
#include "layout_g4_private.h"

static inline int min(int x, int y) {
  return x < y ? x : y;
}


// slipcount(0 and slipcount_rev() are identical except that the former
// slides the lbn forward while the latter does not.

// optimization: keep track of the points at which the running total
// of the slip/spare list is 0.  Have a fast index of those and 
// start at the highest one <= lbn.

// Or:  keep running total and binsearch.

// XXX give a succinct explanation as to why ltop() wants the one
// and ptol() the other!

// This also needs to indicate when lbn coincides with a slip, i.e.
// in sequential access, you skip a sector.

// Returns the highest entry in the slip list <= lbn??

static int
slipcount_bins(struct dm_layout_g4 *l,
	       int lbn,
	       int low,
	       int high)
{
  ddbg_assert(low <= high);
  ddbg_assert(0 <= low);
  ddbg_assert(high <= l->slips_len);

  if(high == low+1 || high == low) {
    return low;
  }
  else {
    int midpt = low + ((high - low) / 2);
    if(l->slips[midpt].off > lbn) {
      high = midpt;
    }
    else {  // off <= lbn
      low = midpt;
    }
    return slipcount_bins(l,lbn,low,high);
  }
}

static int 
slipcount(struct dm_layout_g4 *l,
	  int lbn)
{
  int i;
  int ct;
  int l2 = lbn;

  // the upper limit of l->slips_len is not in error
  i = slipcount_bins(l, lbn, 0, l->slips_len);
  ddbg_assert(0 <= i);
  ddbg_assert(i < l->slips_len);

  ct = l->slips[i].count;

  while(i < l->slips_len && l->slips[i].off <= l2) {
    ct = l->slips[i].count;
    l2 = lbn + ct;
    i++;
  }

  return ct;
}

static int 
slipcount_rev(struct dm_layout_g4 *l,
	      int lbn,
	      int *slip_len) 
{
  int i = 0;

  // the upper limit of l->slips_len is not in error
  i = slipcount_bins(l, lbn, 0, l->slips_len); 
  ddbg_assert(0 <= i);
  ddbg_assert(i < l->slips_len);

  if(l->slips[i].off <= lbn 
     && (i > 0 
	 && lbn < l->slips[i].off 
	 + (l->slips[i].count - l->slips[i-1].count))) 
  {
    if(slip_len) {
      ddbg_assert(0);      // XXX fixme
    }

    return -1;
  }
  else {
    return l->slips[i].count;
  }
}


struct remap *
remap_lbn(struct dm_layout_g4 *l,
	  int lbn)
{
  int i;
  struct remap *r, *result = 0;

  for(i = 0, r = &l->remaps[i]; i < l->remaps_len; i++, r++) {
    if(r->off <= lbn && lbn < (r->off + r->count)) {
      result = r;
      break;
    }
  }

  return result;
}

// is p the destination of a remap?
struct remap *
remap_pbn(struct dm_layout_g4 *l,
	  struct dm_pbn *p)
{
  int i;
  struct remap *r, *result = 0;
  for(i = 0, r = &l->remaps[i]; i < l->remaps_len; i++, r++) {
    if(r->dest.cyl == p->cyl 
       && r->dest.head == p->head
       && r->dest.sector <= p->sector 
       && p->sector < (r->dest.sector + r->count))
    {
      result = r;
      break;
    }
  }

  return result;
}


// Maybe refactor into a single set
// of "recurse" routines that take exactly one of a
// lbn or pbn and build the path to the tp containing it.

void
g4_path_append(struct g4_path *p, 
	       union g4_node n, 
	       g4_node_t t, 
	       int i,
	       int quot,
	       int resid) 
{
  ddbg_assert(p->length < G4_ALLOC_PATH);
  struct g4_path_node *pp = &p->path[p->length];
  
  pp->n = n;
  pp->type = t;
  pp->i = i;

  pp->quot = quot;
  pp->resid = resid;

  ++p->length;
}


// For ptol, have to keep track of the size of the enclosing thing so
// we don't map past the end of it.
struct g4_path *
g4_r(struct dm_layout_g4 *l, 
     union g4_node *n,
     g4_node_t t,
     int *lbn,
     int max,
     struct dm_pbn *p,
     struct g4_path *acc) // accumlator
{
  int i;
  union g4_node *nn; // where we're going to recurse
  g4_node_t tt;

  int quot = 0;
  int resid = 1;

  ddbg_assert(lbn || p);

  switch(t) {
  case TRACK:
    if(lbn) {
      if(n->t->low <= *lbn && *lbn <= n->t->high) {

	// ?
	resid = *lbn - n->t->low;

	nn = 0;
	goto out;
      }
      else {
	goto out_err;
      }
    }
    else {
      if(n->t->low <= p->sector && p->sector <= n->t->high) {
	if(p->sector > max) {
	  goto out_err;
	}

	// quot/resid?
	resid = p->sector - n->t->low;
	 
	nn = 0;
	goto out;
      }
      else {
	goto out_err;
      }
    }
    break;

  case IDX:
  {
    struct idx_ent *e;
    for(i = 0, e = &n->i->ents[0]; i < n->i->ents_len; i++, e++) 
    {
      if(lbn) {
	if(e->lbn <= *lbn && *lbn < (e->lbn + e->runlen)) {
	  *lbn -= e->lbn;

	  quot = *lbn / e->len;
	  // XXX
	  quot = e->cylrunlen < 0 ? -quot : quot;
	  resid = *lbn % e->len;

	  nn = &e->child;
	  tt = e->childtype;

	  *lbn = resid;
	  goto out;
	}	
      }
      else {
	int low = e->cylrunlen > 0 ? e->cyl : e->cyl + e->cylrunlen + 1;
	int high = e->cylrunlen < 0 ? e->cyl : e->cyl + e->cylrunlen - 1;
	if(low <= p->cyl && p->cyl <= high
	   && (e->childtype != TRACK || p->head == e->head))

	{ 
	  p->cyl -= e->cyl;

	  quot = p->cyl / e->cyllen;
	  resid = p->cyl % e->cyllen;

	  max = min(max, e->lbn + e->runlen - 1);
	  max -= e->lbn;

	  // cut down again for RLE
	  quot = p->cyl / e->cyllen;
	  // XXX
	  quot = e->cylrunlen < 0 ? -quot : quot;
	  max = min(max, (quot+1) * e->len - 1);
	  max -= quot * e->len;

	  resid = p->cyl % e->cyllen;
	  
	  p->cyl = resid;
	 
	  nn = &e->child;
	  tt = e->childtype;
	  goto out;
	}
      }
    }
    goto out_err;
  } break;
  default:
    ddbg_assert(0);
    break;
  }

 out:
  g4_path_append(acc, *n, t, i, quot, resid);
  if(nn) {
    return g4_r(l, nn, tt, lbn, max, p, acc);
  }
  else {
    return acc;
  }

 out_err:
  free(acc);
  return 0;
}

struct g4_path *
g4_recurse(struct dm_layout_g4 *l, int *lbn, struct dm_pbn *p) 
{
  int lbncopy;
  struct dm_pbn pbncopy;
  struct g4_path *acc = calloc(1, sizeof(*acc));
  union g4_node n;
  int max;

  if(lbn) {
    lbncopy = *lbn;
    lbn = &lbncopy;
  }

  if(p) {
    pbncopy = *p;
    p = &pbncopy;
  }
  
  n.i = l->root;
  g4_path_append(acc, n, IDX, 
		 0,  // i
		 0,  // quot
		 1); // resid

  max = l->parent->dm_sectors-1;
  max += slipcount_rev(l, max, 0);
  return g4_r(l, &n, IDX, lbn, max, p, acc);
}


dm_ptol_result_t
ltop(struct dm_disk_if *d,
     int lbn, 
     dm_layout_maptype junk,
     struct dm_pbn *result,
     int *remapsector)
{
  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;
  struct remap *r;

  if(lbn < 0 || d->dm_sectors <= lbn) {
    return DM_NX;
  }

  if((r = remap_lbn(l, lbn))) {
    *result = r->dest;
    result->sector += (lbn - r->off);
    return DM_OK;
    // not always -- spare remaps
    // return DM_REMAPPED;
  }
  else {
    int i;
    struct g4_path *p;
    struct g4_path_node *n;

    // fiddle lbn according to slips/spares
    lbn += slipcount(l, lbn);
    
    p = g4_recurse(l, &lbn, 0);
    if(!p) {
      return DM_NX;
    }

    for(i = 0; i < p->length; ++i) {
      n = &p->path[i];
      switch(n->type) {
      case TRACK:
	result->sector = n->n.t->low + lbn;
	break;
	
      case IDX:
      {
	struct idx_ent *e = &n->n.i->ents[n->i];
	lbn -= e->lbn;

	if(i > 0) {
	  result->cyl += e->cyl + (n->quot * e->cyllen);
	}
	else {
	  result->cyl = e->cyl + (n->quot * e->cyllen);
	}

	if(e->childtype == TRACK) {
	  result->head = e->head;
	}

	lbn = n->resid;
      } break;

      default: ddbg_assert(0); break;
      }
    }
    free(p);
  }

  return DM_OK;
}


dm_ptol_result_t
ptol(struct dm_disk_if *d,
     struct dm_pbn *pbn,
     int *remapsector)
{
  int result = 0;
  struct dm_pbn pbncopy = *pbn; // we modify this
  struct remap *r;

  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;

  pbn = &pbncopy;

  if((r = remap_pbn(l, pbn))) {
    return r->off + pbn->sector - r->dest.sector;
  }
  else {
    int rv = 0;
    int i;
    struct g4_path *path;
    struct g4_path_node *n;

    path = g4_recurse(l, 0, pbn);

    if(!path) {
      return DM_NX;
    }

    for(i = 0; i < path->length; ++i) {
      n = &path->path[i];
      switch(n->type) {
      case TRACK:
	result += (pbn->sector - n->n.t->low);
	break;
      case IDX:
	{
	  struct idx_ent *e = &n->n.i->ents[n->i];

	  pbn->cyl -= e->cyl;
	
	  if(i > 0) {
	    result += e->lbn + (n->quot * e->len);
	  }
	  else {
	    result = e->lbn + (n->quot * e->len);
	  }
	
	  pbn->cyl = n->resid;
	  
	} break;

      default: ddbg_assert(0); break;
      }
    }

    // if result coincides with an entry in the slip list...

    rv = slipcount_rev(l, result, NULL); // &slipct
    if(rv == -1) {
      result = DM_NX;
    }
    else {
      result -= rv;
    }

    free(path);
  }

  return result;
}


static int
g4_spt(struct dm_layout_g4 *l,
       int *lbn,
       struct dm_pbn *pbn)
{
  struct g4_path *p;
  struct g4_path_node *n;
  int rv;

  p = g4_recurse(l, lbn, pbn);

  if(p) {
    n = &p->path[p->length - 1];
    ddbg_assert(n->type == TRACK);
    rv = n->n.t->spt;
    free(p);
  }
  else {
    rv = -1;
  }  

  return rv;
}

int
g4_spt_lbn(struct dm_disk_if *d,
	   int lbn)
{
  int result;
  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;
  struct remap *r;

  lbn += slipcount(l,lbn);
  r = remap_lbn(l, lbn);

  if(r) {
    return r->spt;
  }
  else {
    return g4_spt(l, &lbn, 0);
  }
}


int
g4_spt_pbn(struct dm_disk_if *d,
	   struct dm_pbn *p)
{
  int result;
  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;
  struct remap *r;
  if((r = remap_pbn(l, p))) {
    return r->spt;
  }
  else {
    return g4_spt(l, 0, p);
  }
}


// I'm punting on what this means for non-whole-track layouts right
// now.

// This assumes that li ... li+k => (c,h,0) ... (c,h,k-1)
dm_ptol_result_t
g4_track_bound(struct dm_disk_if *d,
	       struct dm_pbn *pbn,
	       int *l0,
	       int *ln,
	       int *remapsector)
{
  int lbn;
  struct remap *r;
  struct dm_pbn pi;
  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;

  int spt = g4_spt_pbn(d, pbn);

  lbn = ptol(d, pbn, 0);
  if(lbn < 0) {
    return lbn;
  }

  if(l0) {
    pi = *pbn;
    pi.sector = 0;

    while((*l0 = ptol(d, &pi, 0)) < 0) {
      pi.sector++;
    }

    ddbg_assert(*l0 < d->dm_sectors);
  }
  
  if(ln) {
    pi = *pbn;
    pi.sector = spt-1;
    
    while((*ln = ptol(d, &pi, 0)) < 0) {
      pi.sector--;
      ddbg_assert(pi.sector >= 0);
    }

    ddbg_assert(*ln < d->dm_sectors);
  }

  if (l0 && ln) {
    ddbg_assert(*l0 <= *ln);
  }

  return DM_OK;
}


dm_angle_t
g4_sector_width(struct dm_disk_if *d,
		struct dm_pbn *track,
		int num)
{
  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;
  // int spt = g4_spt_pbn(d, track);
  dm_angle_t result;
  struct remap *r;
  
  if((r = remap_pbn(l, track))) {
    result = r->sw;
  }
  else {
    struct g4_path *p;
    struct g4_path_node *n;
    p = g4_recurse(l, 0, track);

    if(!p) {
      // DM_NX
      result = 0;
    }
    else {
      n = &p->path[p->length - 1];
      ddbg_assert(n->type == TRACK);
      result = n->n.t->sw;
      free(p);
    }
  }

  return result;
}


// Compute the starting offset of a pbn relative to 0. 
dm_angle_t
g4_skew(struct dm_disk_if *d,
	struct dm_pbn *pbn)
{
  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;
  struct g4_path *p;
  struct g4_path_node *n;
  int i;
  dm_angle_t result;

  p = g4_recurse(l, 0, pbn);
  if(!p) { 
    // DM_NX
    return 0; 
  }

  for(i = 0; i < p->length; ++i) {
    n = &p->path[i];
    switch(n->type) {
    case TRACK:
      result += n->resid * n->n.t->sw;
      break;

    case IDX:
    {
      struct idx_ent *e = &n->n.i->ents[n->i];

      if(i > 0) {
	result += e->off;
      }
      else {
	result = e->off;
      }

      result += n->quot * e->alen;

    } break;
      
    default: ddbg_assert(0); break;
    }
  }

  free(p);
  return result;
}


// convert from an angle to a pbn
// returns a ptol_result since provided angle could be in slipped
// space, etc.  Rounds angle down to a sector starting offset
// Takes the angle in 0l.
dm_ptol_result_t
g4_atop(struct dm_disk_if *d,
	struct dm_mech_state *m,
	struct dm_pbn *p)
{
 
  dm_angle_t sw;
  p->cyl = m->cyl;
  p->head = m->head;
  p->sector = 0; // XXX

  sw = g4_sector_width(d, p, 1);
  p->sector = m->theta / sw;

  // p may be in unmapped space
  return d->layout->dm_translate_ptol(d, p, 0);
}

dm_ptol_result_t
g4_defect_count(struct dm_disk_if *d, 
		struct dm_pbn *track,
		int *result)
{
  // XXX
  *result = 0;
  return 0;
}


// XXX These zone apis are totally fake!  We're going to map zones to
// root ents.

// returns the number of zones for the layout
int 
g4_get_numzones(struct dm_disk_if *d) 
{
  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;
  return l->root->ents_len;
}


int
g4_get_zone(struct dm_disk_if *d, int n, struct dm_layout_zone *z)
{
  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;
  struct idx_ent *e;


  if(n >= l->root->ents_len) {
    return -1;
  }

  e = &l->root->ents[n];

  z->spt = g4_spt_lbn(d, e->lbn);
  z->lbn_low = e->lbn;
  z->lbn_high = min(d->dm_sectors, e->lbn + e->runlen);
  z->cyl_low = e->cyl;
  z->cyl_high = min(d->dm_cyls, e->cyl + e->cylrunlen);


  return 0;
}


struct dm_layout_if layout_g4 = {
  .dm_translate_ltop = ltop,
  .dm_translate_ptol = ptol,

  .dm_get_sectors_lbn = g4_spt_lbn,
  .dm_get_sectors_pbn = g4_spt_pbn,

  .dm_get_track_boundaries = g4_track_bound, 

  .dm_pbn_skew = g4_skew,

  .dm_convert_atop = g4_atop,
  .dm_get_sector_width = g4_sector_width, 

  .dm_defect_count = g4_defect_count,
  .dm_get_numzones = g4_get_numzones,
  .dm_get_zone = g4_get_zone
 
};