syssim_driver2.c

目前最精确的磁盘模拟器的第3版

/*
 * DiskSim Storage Subsystem Simulation Environment (Version 3.0)
 * Revision Authors: John Bucy, Greg Ganger
 * Contributors: John Griffin, Jiri Schindler, Steve Schlosser
 *
 * Copyright (c) of Carnegie Mellon University, 2001, 2002, 2003.
 *
 * 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.
 *
 */


/*
 * A sample skeleton for a system simulator that calls DiskSim as
 * a slave.
 *
 * Contributed by Eran Gabber of Lucent Technologies - Bell Laboratories
 *
 * Usage:
 *	syssim <parameters file> <output file> <max. block number>
 * Example:
 *	syssim parv.seagate out 2676846
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <math.h>
#include "syssim_driver.h"

#include "disksim_global.h"
#include "disksim_iosim.h"
#include "disksim_iodriver.h"
#include "disksim_disk.h"

#include <sys/param.h>      /* for MIN */
#include <assert.h>

#include <sys/time.h>
#include <unistd.h>
#include <getopt.h>

/* #define DEBUG_SEEK */  
/* #define DEBUG_EXTRA */ 
/* #define DEBUG_EXTRASEEK */
/* #define DEBUG_PHYSREQUESTS */
/* #define DEBUG_COMPLETIONS */
/* #define DEBUG_POSSIBLE */
/* #define DEBUG_NOTBORING */
/* #define DEBUG_SEQPROGRESS */
/* #define DEBUG_ISSUE */
/* #define DEBUG_BLOCKMAP */
/* #define OLD */

#define HAVE_X86

#define MAX_TIME 8000
extern char *optarg;
extern int optind;
extern int opterr;
extern int optopt;

/* algorithm defines */
#define SCHED_INIT 0x1
#define SCHED_OUT_VALID 0x2

#define MIN_ALG 1
#define GREEDY_BW_ALG 1
#define GREEDY_BLOCK_COIN_ALG 2
#define SSTF_ALG 3
#define SEPTF_ALG 4
#define GREEDY_BW_PROB_COIN_ALG 5
#define GREEDY_BW_EDGE_COIN_ALG 6
#define GREEDY_BW_SOURCE_ALG 7
#define GREEDY_BLOCK_ALG 8
#define GREEDY_BW_SOURCE_WEIGHT_ALG 9
#define LEAST_LATENCY_ALG 10
#define GREEDY_BW_MAX_DEST_ALG 11
#define GREEDY_BW_COIN_ALG 12
#define GREEDY_BW_SOURCE_DIST_ALG 13
#define GREEDY_BW_TIME_DIST_ALG 14
#define GREEDY_UNIFORM_RATE_ALG 15
#define GREEDY_BW_TRACK_ALG 16
#define GREEDY_AREA_FIRST_ALG 17
#define GREEDY_BW_TRACK_DIST_ALG 18
#define SEPTF_TRACK_ALG 19
#define SEPTF_FRAGMENT_ALG 20
#define MAX_ALG 20

/* end algorithm defines */

#define	BLOCK	4096
#define	SECTOR	512
#define	BLOCK2SECTOR	(BLOCK/SECTOR)
#define	STRMAX	512

typedef	struct	{
	int n;
	double sum;
	double sqr;
} Stat;

/* globals */
static SysTime now = 0;		/* current time */
static SysTime next_event = 0;	/* next event */
//static int completed = 0;	/* last request was completed */
//static int pending = 0;	        /* number of requests pending */
static Stat st;

//#define MAXDISKS 10
//static double last_issued = 0.0;
static double last_foreground;
static int seq_blkno[MAXDISKS];
static int sourcecyl[MAXDISKS];
static int destcyl[MAXDISKS];
static int inside[MAXDISKS];
static int outside[MAXDISKS];
static int zero[MAXDISKS];
static double last_background[MAXDISKS];
static int background_outstanding[MAXDISKS];

/* disk, workload parameters */
static double interarrival = 65.12;
static double readfraction = 2.0 / 3.0;
//static int max_sectors = 4400000;
static int ave_sectors = 10;
static int seq_sectors = 16;
static int servtime = 0;
static int onlyfourpass = 0;
static float servicetime = 0.0;
static int min_sector_pickup = 1;

static double off_cyl_mult = 1.0;

static double threshold = 1.0;

static double conservative = 0.0;

/* inputs */
//static int nsectors;
static int do_background = 0;
static int algorithm = 0;
static int amount_background = 1000;
static int multi_programming = 2;
static double sim_length = 20000.0;
static int pickup_demand_blocks = 0;
static double hot_fraction = 0.0;
static int do_input_trace=0;
static int active_requests=0;
static int done10=0;
static int done20=0;
static int done30=0;
static int done40=0;
static int done50=0;
static int done60=0;
static int done70=0;
static int done80=0;
static int done90=0;
static int done95=0;
static int done100=0;

/* trace file */

static FILE *tracefile;
static FILE *free_block_rate;

static statgen *total_latency_stat;
static statgen *search_count_stat;
static statgen *total_seek_stat;
static statgen *total_transfer_stat;
static statgen *free_bandwidth_stat;
static statgen *extra_seek_stat;
static statgen *total_latency_stat_inst;
static statgen *free_bandwidth_stat_inst;
static statgen *extra_seek_stat_inst;
static statgen **latency_stat;
static statgen **seek_dist_stat;
static statgen **free_count_stat;
static statgen **free_demand_count_stat;
static statgen **take_free_time_stat;
static statgen **free_pop_stat;
static statgen **free_cyl_pop_stat;
static statgen **free_cyl_stat;

static int req_count=0;
static float free_bandwidth;
static int max_band_count=0;
static double max_cyl_prob=0.0;

static float cyl_mean;
static long cyl_dist_count=0;
static long total_seeks=0;

/* weight for algorithm GREEDY_BW_SOURCE_WEIGHT_ALG */
static float FB_weight=1;

static long alg_count=0;

static int area_firstcyl=1;
static int area_lastcyl=2;

/* bucket sizes */

//#define CYL_ENTRIES 1
#define MAX_REQ 3
#define PERIOD 500.0
#define MICROMULT 1000000
#define ANGLE_ENTRIES 360
#define MAX_ANGLE 360
#define MAX_SECTORS 256
//#define MAXSURFACES 4
#define TRACEBATCHSIZE 25
#define SEARCH_COUNT_STAT "Search count"
#define EXTRA_SEEK_STAT "Extra seek time"
#define FREE_BANDWIDTH_STAT "Free bandwidth"
#define LATENCY_STAT "Rotational latency"
#define TRANSFER_STAT "Transfer time"
#define SEEK_STAT "Seek time"
#define SEEK_DIST_STAT "Seek distance"
#define FREE_COUNT_STAT "Free count"
#define FREE_DEMAND_COUNT_STAT "Free demand count"
#define TAKE_FREE_TIME_STAT "Free time"
#define FREE_POP_STAT "Free population"
#define FREE_CYL_POP_STAT "Free cylinder population"
#define FREE_CYL_STAT "Free cylinder"
#define STAT_FILENAME "free.statsdef"
#define LATENCY_WEIGHT "ioqueue_latency_weight"
#define MAX_COUNT_WEIGHT 1.0
#define CYL_DIST_MEAN 1000

#define numiodrivers            (disksim->iodriver_info->numiodrivers)
#define iodrivers               (disksim->iodriver_info->iodrivers)

extern double remote_disk_seek_time(int distnace, int headswitch, int read);
extern event* iotrace_get_ioreq_event(FILE* iotracefile,int traceformat, ioreq_event* new);

/* added disksim variable */

long total_timer;
long free_time;

long time_scale = 550000;

#define BITMAP_CHECK(DEVNO,CYL,SURF,SECT)       ((bitmap[DEVNO][SURF][CYL][SECT >> 5] & (0x1 << (SECT & 0x001F))) >> (SECT & 0x001F)) 
#define BITMAP_SET(DEVNO,CYL,SURF,SECT)       (bitmap[DEVNO][SURF][CYL][SECT >> 5] |= (0x1 << (SECT & 0x001F)))
#define BITMAP_CLEAR(DEVNO,CYL,SURF,SECT)       (bitmap[DEVNO][SURF][CYL][SECT >> 5] &= ((0xFFFFFFFE << (SECT & 0x001F)) | (0xFFFFFFFE >> (0x001F - ((SECT-1) & 0x001F)))))


void panic(const char *s)
{
  perror(s);
  exit(1);
}

void add_statistics(Stat *s, double x)
{
  s->n++;
  s->sum += x;
  s->sqr += x*x;
}

void print_statistics(Stat *s, const char *title)
{
  double avg, std;
  
  avg = s->sum/s->n;
  std = sqrt((s->sqr - 2*avg*s->sum + s->n*avg*avg) / s->n);
  fprintf(stderr,"%s: n=%d average=%f std. deviation=%f\n", title, s->n, avg, std);
}

/* 
 *   For free block figuring
 *
 *
 */

static int nrequests[MAXDISKS];

typedef struct cyl_node_s {
  unsigned short cylinder;
  unsigned char possible_seek;
  unsigned char nsectors;
  float source_seektime;
  float dest_seektime;
  float extra_time;
} cyl_node_t;

typedef struct node_s {
  unsigned short sectors_rotate;
  unsigned char sector;
  unsigned char possible_rotate;
  unsigned char possible;
  unsigned char cumulative_possible;
  unsigned char desired;
  unsigned char completed;
  float source_rotate;
} node_t;

typedef struct bucket_s {
  float angle;
  unsigned short cylinder;
  struct bucket_s *next;
} bucket_t;

/*typedef struct bitmap_s {
  unsigned int bit : 1;
  } bitmap_t;*/


typedef struct touchmap_s {
  float touch;
  float squared;
  float max;
} touchmap_t;

typedef struct entry_s {
  unsigned int *free_block_count;
} entry_t;

typedef struct block_s {
  unsigned short cylinder;
  unsigned char sector;
} block_t;

static int min_fragment_size=1;
static int numcyls;
static int numsurfaces;
static int numblocks;
static int *sectorspercyl;
static int *cylsperzone;
static double *probpercyl;
static float oneRotation;
static int ndrives = 1;
static float extra_settle_angle = 0.0;
static float **sector_angle;
static unsigned short **min_sectors;
static float *seek_angle;
static float *seek_min;
//static bitmap_t ****bitmap;
static unsigned int ****bitmap;
static touchmap_t ***touchmap;
static int *free_blocks;
static int *cyl_order;
static int **free_count;
static unsigned short ***free_count_track;
void free_block_request(unsigned short cyl, unsigned short sector, float angle, unsigned short surface, int devno);


void map_blocknum(int diskno, int blocknum, unsigned short *cyl, unsigned short *sector, unsigned short *surface)
{
  int temp_cyl;
  int temp_sector;
  int temp_surface;
  
#ifdef DEBUG_BLOCKMAP
  fprintf(stderr,"input block %d to",blocknum);
#endif /* DEBUG_BLOCKMAP */
  disk_get_mapping (MAP_FULL, diskno, blocknum, &temp_cyl, &temp_surface, &temp_sector);
  //  *cyl = blockmap[blocknum / surfaces].cylinder;
  //*sector = blockmap[blocknum / surfaces].sector;
#ifdef DEBUG_BLOCKMAP
  fprintf(stderr," (%d,%d,%d)\n",temp_cyl,temp_sector,temp_surface);
#endif /* DEBUG_BLOCKMAP */

  *cyl = (short)temp_cyl;
  *sector = (short)temp_sector;
  *surface = (short)temp_surface;
  
}

#define CYCLES_PER_MS 550000

inline long long get_time(){

  static unsigned low;
  static unsigned high;
  long long returnval;

  __asm__(".byte 0x0f,0x31" :"=a" (low), "=d" (high)); /* RDTSC */
  
  returnval = high;
  returnval = returnval << 32;
  returnval += low;
  
  return(returnval);
}

/*void calibrate_timer(){
  }*/

void init_free_blocks()
{
  int i,j,k;

  FILE *statfile;

  unsigned short cyl = 0;
  unsigned short sector = 0;
  unsigned short surface = 0;
  
  /*
   *   data space
   */
  
  statfile = fopen(STAT_FILENAME,"r");
  if(statfile == NULL){
    fprintf(stderr,"ERROR:  Statsdef file %s could not be opened for reading\n",STAT_FILENAME);
    exit(-1);
  }

  latency_stat = (statgen **)calloc((int)ceil(sim_length/(float)PERIOD),sizeof(statgen));
  if(latency_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for latency_stat\n");
    exit(-1);
  }

  seek_dist_stat = (statgen **)calloc((int)ceil(sim_length/(float)PERIOD),sizeof(statgen));
  if(seek_dist_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for seek_disk_stat\n");
    exit(-1);
  }

  free_pop_stat = (statgen **)calloc((int)ceil(sim_length/(float)PERIOD),sizeof(statgen));
  if(free_pop_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for free_pop_stat\n");
    exit(-1);
  }
  
  free_cyl_pop_stat = (statgen **)calloc((int)ceil(sim_length/(float)PERIOD),sizeof(statgen));
  if(free_cyl_pop_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for free_cyl_pop_stat\n");
    exit(-1);
  }

  free_cyl_stat = (statgen **)calloc((int)ceil(sim_length/(float)PERIOD),sizeof(statgen));
  if(free_cyl_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for free_cyl_stat\n");
    exit(-1);
  }
  
  free_count_stat = (statgen **)calloc((int)ceil(sim_length/(float)PERIOD),sizeof(statgen));
  if(free_count_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for free_count_stat\n");
    exit(-1);
  }
  
  free_demand_count_stat = (statgen **)calloc((int)ceil(sim_length/(float)PERIOD),sizeof(statgen));
  if(free_count_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for free_demand_count_stat\n");
    exit(-1);
  }
  
  take_free_time_stat = (statgen **)calloc((int)ceil(sim_length/(float)PERIOD),sizeof(statgen));
  if(take_free_time_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for take_free_time_stat\n");
    exit(-1);
  }
  
  total_latency_stat = (statgen *)malloc(sizeof(statgen));
  if(total_latency_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for total_latency_stat\n");
    exit(-1);
  }

  stat_initialize(statfile, LATENCY_STAT, total_latency_stat);

  search_count_stat = (statgen *)malloc(sizeof(statgen));
  if(search_count_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for search_count_stat\n");
    exit(-1);
  }

  stat_initialize(statfile, SEARCH_COUNT_STAT, search_count_stat);

  total_transfer_stat = (statgen *)malloc(sizeof(statgen));
  if(total_transfer_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for total_transfer_stat\n");
    exit(-1);
  }

  stat_initialize(statfile, TRANSFER_STAT, total_transfer_stat);

  total_seek_stat = (statgen *)malloc(sizeof(statgen));
  if(total_seek_stat == NULL){
    fprintf(stderr,"ERROR:  Could not malloc memory for total_seek_stat\n");
    exit(-1);
  }

  stat_initialize(statfile, SEEK_STAT, total_seek_stat);

  free_bandwidth_stat = (statgen *)malloc(sizeof(statgen));
  if(free_bandwidth_stat == NULL){