g4_skews.c

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

/* 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 4

struct 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 40

enum { GENTRACE, CALIB } mode = CALIB;

void
schedule_callback(disksim_interface_callback_t fn, 
		  double t, 
		  void *ctx) {
  struct dsstuff *ds = (struct dsstuff *)ctx;
  ds->next = t;
}

void
deschedule_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.
double
time_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.
int
trace_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.
double
get_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.
int
adjust_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.com
static double
mean(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 squares
static double
ss(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 double
ssxy(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;
}

// variance
double 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, r
double
linreg(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.0
double
find_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);