btt/seek.c

   1 /*
   2  * blktrace output analysis: generate a timeline & gather statistics
   3  *
   4  * Copyright (C) 2006 Alan D. Brunelle <Alan.Brunelle@hp.com>
   5  *
   6  *  This program is free software; you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation; either version 2 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program; if not, write to the Free Software
  18  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *
  20  */
  21 #include <float.h>
  22 #include "globals.h"
  23
  24 struct seek_bkt {
  25         struct rb_node rb_node;
  26         long long sectors;
  27         int nseeks;
  28 };
  29
  30 /* Seeks per second */
  31 struct sps_bkt {
  32         double t_start, t_last;
  33         unsigned long nseeks;
  34 };
  35
  36 struct seeki {
  37         FILE *rfp, *wfp, *cfp, *sps_fp;
  38         struct rb_root root;
  39         struct sps_bkt sps;
  40         long long tot_seeks;
  41         double total_sectors;
  42         long long last_start, last_end;
  43 };
  44
  45 static FILE *seek_open(char *str, char rw)
  46 {
  47         FILE *fp;
  48         char *oname;
  49
  50         if (seek_name == NULL) return NULL;
  51
  52         oname = malloc(strlen(seek_name) + strlen(str) + 32);
  53         sprintf(oname, "%s_%s_%c.dat", seek_name, str, rw);
  54         if ((fp = my_fopen(oname, "w")) == NULL) {
  55                 perror(oname);
  56                 free(oname);
  57         } else
  58                 add_file(fp, oname);
  59
  60         return fp;
  61 }
  62
  63 static void __insert(struct rb_root *root, long long sectors)
  64 {
  65         struct seek_bkt *sbp;
  66         struct rb_node *parent = NULL;
  67         struct rb_node **p = &root->rb_node;
  68
  69         while (*p) {
  70                 parent = *p;
  71                 sbp = rb_entry(parent, struct seek_bkt, rb_node);
  72                 if (sectors < sbp->sectors)
  73                         p = &(*p)->rb_left;
  74                 else if (sectors > sbp->sectors)
  75                         p = &(*p)->rb_right;
  76                 else {
  77                         sbp->nseeks++;
  78                         return;
  79                 }
  80         }
  81
  82         sbp = malloc(sizeof(struct seek_bkt));
  83         sbp->nseeks = 1;
  84         sbp->sectors = sectors;
  85
  86         rb_link_node(&sbp->rb_node, parent, p);
  87         rb_insert_color(&sbp->rb_node, root);
  88 }
  89
  90 static void __destroy(struct rb_node *n)
  91 {
  92         if (n) {
  93                 struct seek_bkt *sbp = rb_entry(n, struct seek_bkt, rb_node);
  94
  95                 __destroy(n->rb_left);
  96                 __destroy(n->rb_right);
  97                 free(sbp);
  98         }
  99 }
 100
 101 static void sps_emit(struct seeki *sip)
 102 {
 103         double s_p_s;
 104         struct sps_bkt *sps = &sip->sps;
 105         double delta = sps->t_last - sps->t_start;
 106
 107         if ((sps->nseeks == 1) || (delta < DBL_EPSILON))
 108                 s_p_s = (double)(sps->nseeks);
 109         else
 110                 s_p_s = (double)(sps->nseeks) / delta;
 111
 112         fprintf(sip->sps_fp, "%15.9lf %.2lf\n", sps->t_start, s_p_s);
 113
 114         sps->t_start = 0;
 115         sps->nseeks = 0;
 116 }
 117
 118 static void sps_add(struct seeki *sip, double t)
 119 {
 120         if (sip->sps_fp) {
 121                 struct sps_bkt *sps = &sip->sps;
 122
 123                 if (sps->nseeks != 0 && ((t - sps->t_start) >= 1.0))
 124                         sps_emit(sip);
 125
 126                 sps->t_last = t;
 127                 if (sps->nseeks == 0) {
 128                         sps->t_start = t;
 129                         sps->nseeks = 1;
 130                 } else
 131                         sps->nseeks++;
 132         }
 133 }
 134
 135 static int __median(struct rb_node *n, long long sofar, long long target,
 136                     long long *rvp)
 137 {
 138         struct seek_bkt *sbp;
 139
 140         sbp = rb_entry(n, struct seek_bkt, rb_node);
 141         if ((sofar + sbp->nseeks) >= target) {
 142                 *rvp = sbp->sectors;
 143                 return 1;
 144         }
 145
 146         if (n->rb_left && __median(n->rb_left, sofar, target, rvp))
 147                 return 1;
 148
 149         if (n->rb_right && __median(n->rb_right, sofar, target, rvp))
 150                 return 1;
 151
 152         return 0;
 153
 154 }
 155
 156 static void __mode(struct rb_node *n, struct mode *mp)
 157 {
 158         struct seek_bkt *sbp;
 159
 160         if (n->rb_left)
 161                 __mode(n->rb_left, mp);
 162         if (n->rb_right)
 163                 __mode(n->rb_right, mp);
 164
 165         sbp = rb_entry(n, struct seek_bkt, rb_node);
 166         if (mp->modes == NULL) {
 167                 mp->modes = malloc(sizeof(long long));
 168                 mp->nmds = 0;
 169         } else if (sbp->nseeks > mp->most_seeks)
 170                 mp->nmds = 0;
 171         else if (sbp->nseeks == mp->most_seeks)
 172                 mp->modes = realloc(mp->modes, (mp->nmds + 1) *
 173                                                         sizeof(long long));
 174         else
 175                 return;
 176
 177         mp->most_seeks = sbp->nseeks;
 178         mp->modes[mp->nmds++] = sbp->sectors;
 179 }
 180
 181 long long seek_dist(struct seeki *sip, struct io *iop)
 182 {
 183         long long dist;
 184         long long start = BIT_START(iop), end = BIT_END(iop);
 185
 186         if (seek_absolute)
 187                 dist = start - sip->last_end;
 188         else {
 189                 /* Some overlap means no seek */
 190                 if (((sip->last_start <= start) && (start <= sip->last_end)) ||
 191                     ((sip->last_start <= end) && (end <= sip->last_end)))
 192                         dist = 0;
 193                 else if (start > sip->last_end)
 194                         dist = start - sip->last_end;
 195                 else
 196                         dist = start - sip->last_start;
 197
 198         }
 199
 200         sip->last_start = start;
 201         sip->last_end = end;
 202         return dist;
 203 }
 204
 205 void *seeki_alloc(struct d_info *dip, char *post)
 206 {
 207         char str[256];
 208         struct seeki *sip = malloc(sizeof(struct seeki));
 209
 210         sprintf(str, "%s%s", dip->dip_name, post);
 211         sip->rfp = seek_open(str, 'r');
 212         sip->wfp = seek_open(str, 'w');
 213         sip->cfp = seek_open(str, 'c');
 214         sip->tot_seeks = 0;
 215         sip->total_sectors = 0.0;
 216         sip->last_start = sip->last_end = 0;
 217         memset(&sip->root, 0, sizeof(sip->root));
 218
 219         if (sps_name) {
 220                 char *oname;
 221
 222                 memset(&sip->sps, 0, sizeof(sip->sps));
 223
 224                 oname = malloc(strlen(sps_name) + strlen(dip->dip_name) + 32);
 225                 sprintf(oname, "%s_%s.dat", sps_name, dip->dip_name);
 226                 if ((sip->sps_fp = my_fopen(oname, "w")) == NULL) {
 227                         perror(oname);
 228                         free(oname);
 229                 } else
 230                         add_file(sip->sps_fp, oname);
 231         } else
 232                 sip->sps_fp = NULL;
 233
 234         return sip;
 235 }
 236
 237 void seeki_free(void *param)
 238 {
 239         struct seeki *sip = param;
 240
 241         if (sip->sps_fp && sip->sps.nseeks != 0)
 242                 sps_emit(sip);
 243
 244         /*
 245          * Associated files are cleaned up by seek_clean
 246          */
 247         __destroy(sip->root.rb_node);
 248         free(sip);
 249 }
 250
 251 void seeki_add(void *handle, struct io *iop)
 252 {
 253         struct seeki *sip = handle;
 254         char rw = IOP_READ(iop) ? 'r' : 'w';
 255         long long dist = seek_dist(sip, iop);
 256         double tstamp = BIT_TIME(iop->t.time);
 257         FILE *fp = IOP_READ(iop) ? sip->rfp : sip->wfp;
 258
 259         if (fp)
 260                 fprintf(fp, "%15.9lf %13lld %c\n", tstamp, dist, rw);
 261         if (sip->cfp)
 262                 fprintf(sip->cfp, "%15.9lf %13lld %c\n", tstamp, dist, rw);
 263
 264         dist = llabs(dist);
 265         sip->tot_seeks++;
 266         sip->total_sectors += dist;
 267         __insert(&sip->root, dist);
 268
 269         sps_add(sip, tstamp);
 270 }
 271
 272 long long seeki_nseeks(void *handle)
 273 {
 274         return ((struct seeki *)handle)->tot_seeks;
 275 }
 276
 277 double seeki_mean(void *handle)
 278 {
 279         struct seeki *sip = handle;
 280         return sip->total_sectors / sip->tot_seeks;
 281 }
 282
 283 long long seeki_median(void *handle)
 284 {
 285         long long rval = 0LL;
 286         struct seeki *sip = handle;
 287
 288         if (sip->root.rb_node)
 289                 (void)__median(sip->root.rb_node, 0LL, sip->tot_seeks / 2,
 290                                &rval);
 291
 292         return rval;
 293 }
 294
 295 int seeki_mode(void *handle, struct mode *mp)
 296 {
 297         struct seeki *sip = handle;
 298         struct rb_root *root = &sip->root;
 299
 300         memset(mp, 0, sizeof(struct mode));
 301         if (root->rb_node)
 302                 __mode(root->rb_node, mp);
 303
 304         return mp->nmds;
 305 }