/* 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 intslipcount_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.voidg4_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_tltop(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_tptol(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 intg4_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;}intg4_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);  }}intg4_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_tg4_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_tg4_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_tg4_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_tg4_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_tg4_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 layoutint g4_get_numzones(struct dm_disk_if *d) {  struct dm_layout_g4 *l = (struct dm_layout_g4 *)d->layout;  return l->root->ents_len;}intg4_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 };