g4_skews.c

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

  printf("%s() a = %f, b = %f, r = %f, var = %f\n", __func__, a, b, r, var);

  *aa = a;

  free(err);
  free(x);

  return b;
}

// Make an angle be within [0,1)
double fix_angle(double a) {
  if(a < 0) {
    return a - (int)a + 1;
  } else {
    return a - (int)a;
  }
}


// Time accessing lbn li immediately after accessing lbn l0 and convert the
// time into an angle in [0,1) according to the rotational period of
// the disk.
double 
measure_one_skew(struct dm_disk_if *d,
		 struct dsstuff *ds,
		 struct trace *trace,
		 int l0,
		 int li) {
  double t, tt, a = 0.0;
  double period = dm_time_itod(d->mech->dm_period(d));

  adjust_lbns(d, &l0, &li);

  t = time_second_request(l0, li, ds, trace, d);
  if(mode == CALIB) {
    tt = get_tracetime(trace, l0, li);
    a = fix_angle(-(t - tt) / period);
  }

  return a;
}


// do_idx_ent() does the hard work to measure the skews for a single
// index entry.  We need to determine e->off, the angular offset of
// the first lbn of this instance taking the first lbn of parent as
// the 0 point and e->alen, the angular offset of the i+1st instance
// of e from the ith.
void
do_idx_ent(struct dm_disk_if *d,        // diskmodel
	   struct dm_layout_g4 *l,      // root of g4 layout
	   struct idx_ent *e,           // the entry in question
	   struct idx *parent,          // The index containing e
	   struct idx_ent *parent_e,    // The entry for parent in its parent
	   int parent_off,              // Which entry we are in parent
	   struct dsstuff *ds,          // Disksim instance
	   struct trace *t,             // io trace
	   int lbn) {                   // The first lbn of parent
  int i;
  int l0;
  int dist;

  double yi;

  double *times;
  double *tracetimes;

  // for bootstrapping off and len
  double off0time, len0time;
  int off0lbn[2], len0lbn[2];

  // Work internally in floating-point, then convert back to the
  // integer representation at the end.
  double aoff = dm_angle_itod(e->off);
  double alen =  dm_angle_itod(e->alen);
  
  double period = dm_time_itod(d->mech->dm_period(d));

  // Number of instances of this entry.
  int quot = e->runlen / e->len;

  // times[i] is disksim's prediction of the amount of time to access the 
  // first lbn of the ith instance after accessing the first instance.
  times = calloc(quot, sizeof(double));
  // Actual times from the trace replay against the real disk.
  tracetimes = calloc(quot, sizeof(double));
  // li[i] contains the first lbn of the ith instance of e.
  int *li = calloc(quot, sizeof(*li));

  printf("%s() lbn %d e->lbn %d alen %f off %f quot %d\n", 
	 __func__, lbn, e->lbn, alen, aoff, quot);

  if(e->alen != 0 || e->off != 0) {
    printf("%s() already done, apparently\n", __func__);
    return;
  }

  // Bootstrap offset by measuring the first instance.
  if(e->lbn != 0) {
    aoff = measure_one_skew(d, ds, t, lbn, lbn + e->lbn);
    e->off = dm_angle_dtoi(aoff);
  }

  // Check for the end of the lbn space.
  if(lbn + e->lbn + e->len >= d->dm_sectors) {
    e->alen = dm_angle_dtoi(0.0);
    return;
  }

  // Bootstrap alen by measuring the skew from the first to the second
  // instance.
  alen = measure_one_skew(d, ds, t, lbn + e->lbn, 
			  lbn + e->lbn + e->len);
  e->alen = dm_angle_dtoi(alen);    

  printf("first off %f len %f\n", aoff, alen);

  // Expand out the lbns of all of the instances.  For calibration
  // (second pass), read in the values from the trace.  To generate
  // the trace (first pass), time how long it takes to read the first
  // lbn of the ith instance after reading the last lbn on the first
  // track of the first instance.
  for(i = 1; i < quot; i++) {
    l0 = lbn;
    li[i] = l0 + e->lbn + e->len * i;

    adjust_lbns(d, &l0, &li[i]);

    if(mode == CALIB) {
      tracetimes[i] = get_tracetime(t, l0, li[i]);

      printf("%d (%d,%d) trace %f pred %f\n", i, 
 	     l0, li[i], 
 	     tracetimes[i], times[i]);
    }
    else {
      time_second_request(l0, li[i], ds, t, d);
    }
  }

  if(mode == GENTRACE) {
    return;
  }

  // Now calibrate the value.  We first look at the first 2 instances,
  // then 4, then 8, etc, refining our estimate at each step.
  for(dist = 2; dist < quot ; ) {
    // y = a + bx; r is the correlation coeffecient.
    double a, b;
    for(i = 1; i < dist; i++) {
      times[i] = time_second_request(l0, li[i], ds, t, d);
      printf("%d (%d,%d) trace %f pred %f\n", i, 
	     l0, li[i], 
	     tracetimes[i], times[i]);
    }

    // Do a linear least squares fit of the difference between the
    // predicted and actual service times.  The slope (b) of that line
    // corresponds to the error in our estimate of alen and the y
    // intercept corresponds to the error in our estimate of off.
    b = find_slope(times, tracetimes, dist, &a, period);

    // Adjust the instance-to-instance skew according to the fit.    
    alen = fix_angle(alen - b / period);
    e->alen = dm_angle_dtoi(alen);
    
    // If e is the first instance in its parent index, its offset is
    // defined to be 0.  Otherwise, correct according to the fit.
    if(e->lbn > lbn) {
      printf("fix aoff (%d, %d)\n", lbn, e->lbn);
      aoff = fix_angle(aoff - a / period);
      e->off = dm_angle_dtoi(aoff);
    }

    printf("alen -> %f, off -> %f (dist %d)\n", alen, aoff, dist);

    if(dist == quot) {
      break;
    } else if(dist * 2 >= quot) {
      dist = quot;
    } else {
      dist *= 2;
    }
  }

  free(li);
  free(tracetimes);
  free(times);
  return;
}

// do_idx() is the main recursive function which measures the skews
// for all of the entries of a given index node.  Each entry has 2
// parameters to measure: the offset of the first instance of that
// entry from the beginning of the index containing it and the
// "length" of each instance, i.e. the offset of the i+1st instance
// relative to the ith.  For each index entry, it first measures the
// offset of the entry relative to the start of the index
// (do_idx_ent()) and then recurses into the structure of that entry.
int do_idx(struct dm_disk_if *d,    // diskmodel
	   struct idx_ent *ie,      // The entry for idx in its parent
	   struct idx *idx,         // The index node in question
	   struct dm_layout_g4 *l,  // g4 layout
	   struct dsstuff *ds,      // disksim instance
	   struct trace *t,         // io trace
	   int lbn) {               // First lbn of idx
  int i;
  struct idx_ent *e;

  fprintf(stderr, "%s(lbn %d)\n", __func__, lbn);

  for(i = 0, e = &idx->ents[0]; i < idx->ents_len; i++, e++) {
    // Measure the angular offset of this entry from the beginning of
    // the index node.
    do_idx_ent(d, l, &idx->ents[i], idx, ie, i, ds, t, lbn);

    // Recursively expand the structure of this entry.
    if(e->childtype == IDX) {
      do_idx(d, e, e->child.i, l, ds, t, lbn + e->lbn);
    }
  }

  for(i = 0, e = &idx->ents[0]; i < idx->ents_len; i++, e++) {
    printf("%s() off %f alen %f\n", __func__, 
	   dm_angle_itod(idx->ents[i].off),
	   dm_angle_itod(idx->ents[i].alen));
  }

  return 0;
}
	 

int main(int argc, char **argv) {
  int c;
  static struct option opts[] = {
    { "parv", 1, 0, 0 },    { "outv", 1, 0, 0 },
    { "model", 1, 0, 0 },
    { "mode", 1, 0, 0 },
    { "trace", 1, 0, 0 },
    {0,0,0,0}
  };

  enum optt { 
    PARV = 0,
    OUTV = 1,
    MODEL = 2,
    MODE = 3,
    TRACE = 4
  };

  struct dm_disk_if *d;
  struct dm_layout_g4 *l;

  struct trace *t;
  struct dsstuff *ds = calloc(1, sizeof(*ds));

  struct lp_block *unm;

  setlinebuf(stdout);
  FILE *outfile;
  int optind;

  char *parv = 0;
  char *outv = 0;
  char *model = 0;
  char *trace = 0;

  while((c = getopt_long(argc, argv, "q", opts, &optind)) != -1) {
    switch(c) {
    case -1:
      break;
    case 0:
      switch(optind) {
      case PARV:
	parv = strdup(optarg);
	break;
      case OUTV:
	outv = strdup(optarg);
	break;
      case MODEL:
	model = strdup(optarg);
	break;
      case MODE:
	if(!strcmp(optarg, "calib")) {
	  mode = CALIB;
	}
	else if(!strcmp(optarg, "gentrace")) {
	  mode = GENTRACE;
	}
	else {
	  fprintf(stderr, "*** bad mode %s\n", optarg);
	  exit(1);
	}
	break;

      case TRACE:
	trace = strdup(optarg);
	break;

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

  t = setup_trace(trace);
  if(mode == CALIB) {
    outfile = fopen(model, "w");
    ddbg_assert(outfile);
  }

  ds->iface = disksim_interface_initialize(parv, 
					   outv,
					   cb,
					   schedule_callback,
					   deschedule_callback,
					   ds,
					   18,  // argc
					   nocache_over);

  d = disksim_getdiskmodel(ds->iface, 0);
  l = (struct dm_layout_g4 *)d->layout;

  do_idx(d, 0, l->root, l, ds, t, 0);

  extern struct lp_block* marshal_layout_g4(struct dm_layout_g4 *);

  if(mode == CALIB) {
    unm = marshal_layout_g4(l);
    unparse_block(unm, outfile);
    fclose(outfile);
  }

  free(ds);

  fclose(t->fp);
  free(t);

  return 0;
}