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         else
  57                 add_file(fp, oname);
  58
  59         return fp;
  60 }
  61
  62 static void __insert(struct rb_root *root, long long sectors)
  63 {
  64         struct seek_bkt *sbp;
  65         struct rb_node *parent = NULL;
  66         struct rb_node **p = &root->rb_node;
  67
  68         while (*p) {
  69                 parent = *p;
  70                 sbp = rb_entry(parent, struct seek_bkt, rb_node);
  71                 if (sectors < sbp->sectors)
  72                         p = &(*p)->rb_left;
  73                 else if (sectors > sbp->sectors)
  74                         p = &(*p)->rb_right;
  75                 else {
  76                         sbp->nseeks++;
  77                         return;
  78                 }
  79         }
  80
  81         sbp = malloc(sizeof(struct seek_bkt));
  82         sbp->nseeks = 1;
  83         sbp->sectors = sectors;
  84
  85         rb_link_node(&sbp->rb_node, parent, p);
  86         rb_insert_color(&sbp->rb_node, root);
  87 }
  88
  89 static void __destroy(struct rb_node *n)
  90 {
  91         if (n) {
  92                 struct seek_bkt *sbp = rb_entry(n, struct seek_bkt, rb_node);
  93
  94                 __destroy(n->rb_left);
  95                 __destroy(n->rb_right);
  96                 free(sbp);
  97         }
  98 }
  99
 100 static void sps_emit(struct seeki *sip)
 101 {
 102         double tstamp, s_p_s;
 103         struct sps_bkt *sps = &sip->sps;
 104         double delta = sps->t_last - sps->t_start;
 105
 106         if ((sps->nseeks == 1) || (delta < DBL_EPSILON)) {
 107                 s_p_s = (double)(sps->nseeks);
 108                 tstamp = sps->t_start;
 109         } else {
 110
 111                 s_p_s = (double)(sps->nseeks) / delta;
 112                 tstamp = sps->t_start + (delta / 2);
 113         }
 114
 115         fprintf(sip->sps_fp, "%15.9lf %.2lf\n", sps->t_start, s_p_s);
 116
 117         sps->t_start = 0;
 118         sps->nseeks = 0;
 119 }
 120
 121 static void sps_add(struct seeki *sip, double t)
 122 {
 123         if (sip->sps_fp) {
 124                 struct sps_bkt *sps = &sip->sps;
 125
 126                 if (sps->nseeks != 0 && ((t - sps->t_start) >= 1.0))
 127                         sps_emit(sip);
 128
 129                 sps->t_last = t;
 130                 if (sps->nseeks == 0) {
 131                         sps->t_start = t;
 132                         sps->nseeks = 1;
 133                 } else
 134                         sps->nseeks++;
 135         }
 136 }
 137
 138 static int __median(struct rb_node *n, long long sofar, long long target,
 139                     long long *rvp)
 140 {
 141         struct seek_bkt *sbp;
 142
 143         sbp = rb_entry(n, struct seek_bkt, rb_node);
 144         if ((sofar + sbp->nseeks) >= target) {
 145                 *rvp = sbp->sectors;
 146                 return 1;
 147         }
 148
 149         if (n->rb_left && __median(n->rb_left, sofar, target, rvp))
 150                 return 1;
 151
 152         if (n->rb_right && __median(n->rb_right, sofar, target, rvp))
 153                 return 1;
 154
 155         return 0;
 156
 157 }
 158
 159 static void __mode(struct rb_node *n, struct mode *mp)
 160 {
 161         struct seek_bkt *sbp;
 162
 163         if (n->rb_left)
 164                 __mode(n->rb_left, mp);
 165         if (n->rb_right)
 166                 __mode(n->rb_right, mp);
 167
 168         sbp = rb_entry(n, struct seek_bkt, rb_node);
 169         if (mp->modes == NULL) {
 170                 mp->modes = malloc(sizeof(long long));
 171                 mp->nmds = 0;
 172         } else if (sbp->nseeks > mp->most_seeks)
 173                 mp->nmds = 0;
 174         else if (sbp->nseeks == mp->most_seeks)
 175                 mp->modes = realloc(mp->modes, (mp->nmds + 1) *
 176                                                         sizeof(long long));
 177         else
 178                 return;
 179
 180         mp->most_seeks = sbp->nseeks;
 181         mp->modes[mp->nmds++] = sbp->sectors;
 182 }
 183
 184 long long seek_dist(struct seeki *sip, struct io *iop)
 185 {
 186         long long dist;
 187         long long start = BIT_START(iop), end = BIT_END(iop);
 188
 189         if (seek_absolute)
 190                 dist = start - sip->last_end;
 191         else {
 192                 /* Some overlap means no seek */
 193                 if (((sip->last_start <= start) && (start <= sip->last_end)) ||
 194                     ((sip->last_start <= end) && (end <= sip->last_end)))
 195                         dist = 0;
 196                 else if (start > sip->last_end)
 197                         dist = start - sip->last_end;
 198                 else
 199                         dist = start - sip->last_start;
 200
 201         }
 202
 203         sip->last_start = start;
 204         sip->last_end = end;
 205         return dist;
 206 }
 207
 208 void *seeki_alloc(struct d_info *dip, char *post)
 209 {
 210         char str[256];
 211         struct seeki *sip = malloc(sizeof(struct seeki));
 212
 213         sprintf(str, "%s%s", dip->dip_name, post);
 214         sip->rfp = seek_open(str, 'r');
 215         sip->wfp = seek_open(str, 'w');
 216         sip->cfp = seek_open(str, 'c');
 217         sip->tot_seeks = 0;
 218         sip->total_sectors = 0.0;
 219         sip->last_start = sip->last_end = 0;
 220         memset(&sip->root, 0, sizeof(sip->root));
 221
 222         if (sps_name) {
 223                 char *oname;
 224
 225                 memset(&sip->sps, 0, sizeof(sip->sps));
 226
 227                 oname = malloc(strlen(sps_name) + strlen(dip->dip_name) + 32);
 228                 sprintf(oname, "%s_%s.dat", sps_name, dip->dip_name);
 229                 if ((sip->sps_fp = my_fopen(oname, "w")) == NULL)
 230                         perror(oname);
 231                 else
 232                         add_file(sip->sps_fp, oname);
 233         } else
 234                 sip->sps_fp = NULL;
 235
 236         return sip;
 237 }
 238
 239 void seeki_free(void *param)
 240 {
 241         struct seeki *sip = param;
 242
 243         if (sip->sps_fp && sip->sps.nseeks != 0)
 244                 sps_emit(sip);
 245
 246         /*
 247          * Associated files are cleaned up by seek_clean
 248          */
 249         __destroy(sip->root.rb_node);
 250         free(sip);
 251 }
 252
 253 void seeki_add(void *handle, struct io *iop)
 254 {
 255         struct seeki *sip = handle;
 256         char rw = IOP_READ(iop) ? 'r' : 'w';
 257         long long dist = seek_dist(sip, iop);
 258         double tstamp = BIT_TIME(iop->t.time);
 259         FILE *fp = IOP_READ(iop) ? sip->rfp : sip->wfp;
 260
 261         if (fp)
 262                 fprintf(fp, "%15.9lf %13lld %c\n", tstamp, dist, rw);
 263         if (sip->cfp)
 264                 fprintf(sip->cfp, "%15.9lf %13lld %c\n", tstamp, dist, rw);
 265
 266         dist = llabs(dist);
 267         sip->tot_seeks++;
 268         sip->total_sectors += dist;
 269         __insert(&sip->root, dist);
 270
 271         sps_add(sip, tstamp);
 272 }
 273
 274 long long seeki_nseeks(void *handle)
 275 {
 276         return ((struct seeki *)handle)->tot_seeks;
 277 }
 278
 279 double seeki_mean(void *handle)
 280 {
 281         struct seeki *sip = handle;
 282         return sip->total_sectors / sip->tot_seeks;
 283 }
 284
 285 long long seeki_median(void *handle)
 286 {
 287         long long rval = 0LL;
 288         struct seeki *sip = handle;
 289
 290         if (sip->root.rb_node)
 291                 (void)__median(sip->root.rb_node, 0LL, sip->tot_seeks / 2,
 292                                &rval);
 293
 294         return rval;
 295 }
 296
 297 int seeki_mode(void *handle, struct mode *mp)
 298 {
 299         struct seeki *sip = handle;
 300         struct rb_root *root = &sip->root;
 301
 302         memset(mp, 0, sizeof(struct mode));
 303         if (root->rb_node)
 304                 __mode(root->rb_node, mp);
 305
 306         return mp->nmds;
 307 }