/* 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.   */// The g4 skew analysis works by generating a trace of requests to// issue to the disk, and then analyzing the result of that to derive// the skew values.// The trace follows the structure of the g4 layout search tree for// the disk's layout mapping.  We effectively do a depth-first search// from the top down with a recursive algorithm.  Operating at each// node, we take the lowest LBN in that node as the "zero point" and// measure the angular offset of the first lbn in each entry in the// node from the first entry of the whole node.  Then we recursively// expand the structure of the lbn range of each index entry.// The implementation does both passes in the same code path.#include <libddbg/libddbg.h>#include <libparam/libparam.h>#include <disksim_interface.h>#include "../layout_g4.h"#include <stdio.h>#include <stdlib.h>#include <math.h>#include <string.h>#include <unistd.h>#include <getopt.h>#define MAX_OUT 4struct dsstuff {  struct disksim_interface *iface;  double now;  double next;  // see the completion callback  double compl[MAX_OUT];  int compl_next;};struct trace {  FILE *fp;};// Disksim parameters to disable the disk cache.static char *nocache_over[] = {  "disk0", "Enable caching in buffer", "0",  "disk0", "Fast write level", "0",   "disk0", "Buffer continuous read", "0",   "disk0", "Read any free blocks", "0",   "disk0", "Minimum read-ahead (blks)", "0",   "disk0", "Maximum read-ahead (blks)", "0"};// forward progress -- max times to loop#define FP 40enum { GENTRACE, CALIB } mode = CALIB;voidschedule_callback(disksim_interface_callback_t fn, 		  double t, 		  void *ctx) {  struct dsstuff *ds = (struct dsstuff *)ctx;  ds->next = t;}voiddeschedule_callback(double t, void *ctx) {  struct dsstuff *ds = (struct dsstuff *)ctx;  ds->next = -1;}// Disksim interface request completion callback.void cb(double t, struct disksim_request *r, void *ctx) {  //  double *d = (double *)ctx;  struct dsstuff *ds = (struct dsstuff *)ctx;  // This is a dumb hack to deal with ds iface being wrong -- the  // ctx here *should* be the per-req ctx (->reqctx) but it doesn't  // have the demux code.    ds->compl[ds->compl_next++] = t;}// Read lbns l1 and l2 back-to-back, timing the second request.  In// trace generation mode, we just print out the IOs we would do.  In// calibration mode, we inject both IOs into an instance of disksim.doubletime_second_request(int l1, int l2, struct dsstuff *ds, struct trace *t,		    struct dm_disk_if *d) {  struct disksim_request *r1, *r2;  ddbg_assert(l1 < d->dm_sectors);  ddbg_assert(l2 < d->dm_sectors);  if(mode == GENTRACE) {    fprintf(t->fp, "%f 0 %d 1 1\n", ds->now, l1);    fprintf(t->fp, "%f 0 %d 1 1\n", ds->now + 0.1, l2);    ds->now += 20.0;  } else {    r1 = calloc(1, sizeof(*r1));    r2 = calloc(1, sizeof(*r2));    r1->blkno = l1;    r1->bytecount = 512;    r1->flags |= DISKSIM_READ;    r1->start = ds->now;    //    r1->reqctx = &t1;      r2->blkno = l2;    r2->bytecount = 512;    r2->flags |= DISKSIM_READ;    r2->start = ds->now + 0.001;    //    r2->reqctx = &t2;      disksim_interface_request_arrive(ds->iface, ds->now, r1);    disksim_interface_request_arrive(ds->iface, ds->now, r2);      // pump disksim    do {      ds->now = ds->next;      ds->next = -1;      disksim_interface_internal_event(ds->iface, ds->now, 0);    } while(ds->next != -1);    // roll now forward slightly, some small ~1ms int-arr    ds->now += 1.0;    free(r1);    free(r2);    //    printf("%d -> %d : %f\n", l1, l2, ds->compl[1] - ds->compl[0]);    ds->compl_next = 0;  }  return ds->compl[1] - ds->compl[0]; }// Open the trace file for reading or writing according to the mode.struct trace *setup_trace(char *name) {  struct trace *t = calloc(1, sizeof(*t));  if(mode == GENTRACE) {    t->fp = fopen(name, "w");  } else {    t->fp = fopen(name, "r");  }  return t;}// Parse the next request in the input trace in disksim "validate"// format.inttrace_get_next(struct trace *t, int *lbn, double *result) {  int rv;  rv = fscanf(t->fp, "%*s %*s %d %*d %lf %*f", lbn, result) == 2;  *result /=  1000.0;    return rv;}// Get the timing for accessing lbn2 after lbn1 from the trace.doubleget_tracetime(struct trace *t, int lbn1, int lbn2) {  double result, t1;  int l1, l2;    do { // try to resync    ddbg_assert(trace_get_next(t, &l1, &t1));  } while(l1 != lbn1);  ddbg_assert(trace_get_next(t, &l2, &result));  ddbg_assert(l1 == lbn1);  ddbg_assert(l2 == lbn2);  return result;}// We actually want the last lbn on the source track.  If you use the// first lbn on the source track, some disks will make it every time,// some will make it about half of the time and have a rotation miss// the other half.intadjust_lbns(struct dm_disk_if *d, int *l1, int *l2) {  struct dm_pbn pbn;  int l0, ln;  if(l1) {    d->layout->dm_translate_ltop(d, *l1, MAP_FULL, &pbn, 0);    d->layout->dm_get_track_boundaries(d, &pbn, &l0, &ln, 0);    *l1 = ln;  }  if(l2) {    d->layout->dm_translate_ltop(d, *l2, MAP_FULL, &pbn, 0);    d->layout->dm_get_track_boundaries(d, &pbn, &l0, &ln, 0);    *l2 = l0;  }  return 0;}// The following functions are used to do a linear least-squares fit// following the article at mathworld.wolfram.comstatic doublemean(double *x, int n) {  int i;  double sum = 0.0;  double mean;  for(i = 0; i < n; i++) {    sum += x[i];  }    mean = sum / n;  return mean;}// sum of squaresstatic doubless(double *x, int n) {  int i;  double sum = 0.0;  double res;  for(i = 0; i < n; i++) {    sum += (x[i] * x[i]);  }  res = sum - n * mean(x,n) * mean(x,n);  return res;}static doublessxy(double *x, double *y, int n) {  int i;  double sum = 0.0;  double res;  for(i = 0; i < n; i++) {    sum += (x[i] * y[i]);  }  res = sum - (n * mean(x,n) * mean(y,n));  return res;}// variancedouble vari(double *x, int n) {  double res = ss(x,n) / n;  return res;}double covar(double *x, double *y, int n) {  double res = ssxy(x,y,n) / n;  return res;}// y = a + bx// The data is the collection of pairs (x[i], y[i]) for i in [0,n)// Returns the correlation coeffecient, rdoublelinreg(double *x, double *y, int n, double *a, double *b) {  double r;  *b = ssxy(x,y,n) / ss(x,n);  *a = mean(y,n) - *b * mean(x,n);  r = sqrt(ssxy(x,y,n) * ssxy(x,y,n) / (ss(x,n) * ss(y,n)));  return r;}// Compute the difference between the samples in d1 and d2, returning// the slope of a line through the points, (i, d1[i] - d2[i])// for i in [0,n)// Returns the y intercept in aa.// Return value is the slope of the fitted line.  If it decides we're// done, returns 0.0doublefind_slope(double *d1, double *d2, int n, double *aa,	   double period) {  int i;  double a,b,r;  double yi;  double *err = calloc(n, sizeof(*err));  double *x = calloc(n, sizeof(*x));  double fit_err, tot_err;  double var;  double thresh = period / 2.0;  int addct = 0;  int n2 = 0;    if(n == 1) {    *aa = d1[0] - d2[0];    return 0.0;  }  if(n == 2) {    *aa = 0.0;    return d1[1] - d2[1];  }  for(i = 1; i < n; i++) {    yi = d1[i] - d2[i];    if(-thresh <= yi && yi <= thresh) {      //      printf("%3d\t%f\n", i, yi);      err[n2] = yi;      x[n2] = i;      n2++;    }  }  r = linreg(x, err, n2, &a, &b);  for(i = 0; i < n2; i++) {    printf("%3d\t%f\n", (int)x[i], err[i]);  }  var = vari(err,n);