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 "globals.h"
  22
  23 static struct file_info *seek_files = NULL;
  24
  25 struct seek_bkt {
  26         struct rb_node rb_node;
  27         long long sectors;
  28         int nseeks;
  29 };
  30
  31 /* Seeks per second */
  32 struct sps_bkt {
  33         double t_start, t_last;
  34         unsigned long nseeks;
  35 };
  36
  37 struct seeki {
  38         FILE *rfp, *wfp, *cfp, *sps_fp;
  39         struct rb_root root;
  40         struct sps_bkt sps;
  41         long long tot_seeks;
  42         double total_sectors;
  43         long long last_start, last_end;
  44 };
  45
  46 static FILE *seek_open(char *str, char rw)
  47 {
  48         FILE *fp;
  49         char *oname;
  50
  51         if (seek_name == NULL) return NULL;
  52
  53         oname = malloc(strlen(seek_name) + strlen(str) + 32);
  54         sprintf(oname, "%s_%s_%c.dat", seek_name, str, rw);
  55         if ((fp = fopen(oname, "w")) == NULL)
  56                 perror(oname);
  57         else
  58                 add_file(&seek_files, 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 tstamp, s_p_s;
 104         struct sps_bkt *sps = &sip->sps;
 105
 106         if (sps->nseeks == 1) {
 107                 s_p_s = 1.0;
 108                 tstamp = sps->t_start;
 109         }
 110         else {
 111                 double delta = sps->t_last - sps->t_start;
 112
 113                 s_p_s = (double)(sps->nseeks) / delta;
 114                 tstamp = sps->t_start + (delta / 2);
 115         }
 116
 117         fprintf(sip->sps_fp, "%15.9lf %.2lf\n", sps->t_start, s_p_s);
 118
 119         sps->t_start = 0;
 120         sps->nseeks = 0;
 121 }
 122
 123 static void sps_add(struct seeki *sip, double t)
 124 {
 125         if (sip->sps_fp) {
 126                 struct sps_bkt *sps = &sip->sps;
 127
 128                 if (sps->nseeks != 0 && ((t - sps->t_start) >= 1.0))
 129                         sps_emit(sip);
 130
 131                 sps->t_last = t;
 132                 if (sps->nseeks == 0) {
 133                         sps->t_start = t;
 134                         sps->nseeks = 1;
 135                 }
 136                 else
 137                         sps->nseeks++;
 138         }
 139 }
 140
 141 void seek_clean(void)
 142 {
 143         clean_files(&seek_files);
 144 }
 145
 146 long long seek_dist(struct seeki *sip, struct io *iop)
 147 {
 148         long long dist;
 149         long long start = BIT_START(iop), end = BIT_END(iop);
 150
 151         if (seek_absolute)
 152                 dist = start - sip->last_end;
 153         else {
 154                 /* Some overlap means no seek */
 155                 if (((sip->last_start <= start) && (start <= sip->last_end)) ||
 156                     ((sip->last_start <= end) && (end <= sip->last_end)))
 157                         dist = 0;
 158                 else if (start > sip->last_end)
 159                         dist = start - sip->last_end;
 160                 else
 161                         dist = start - sip->last_start;
 162
 163         }
 164
 165         sip->last_start = start;
 166         sip->last_end = end;
 167         return dist;
 168 }
 169
 170 void *seeki_init(char *str)
 171 {
 172         struct seeki *sip = malloc(sizeof(struct seeki));
 173
 174         sip->rfp = seek_open(str, 'r');
 175         sip->wfp = seek_open(str, 'w');
 176         sip->cfp = seek_open(str, 'c');
 177         sip->tot_seeks = 0;
 178         sip->total_sectors = 0.0;
 179         sip->last_start = sip->last_end = 0;
 180         memset(&sip->root, 0, sizeof(sip->root));
 181
 182         if (sps_name) {
 183                 char *oname;
 184
 185                 memset(&sip->sps, 0, sizeof(sip->sps));
 186
 187                 oname = malloc(strlen(sps_name) + strlen(str) + 32);
 188                 sprintf(oname, "%s_%s.dat", sps_name, str);
 189                 if ((sip->sps_fp = fopen(oname, "w")) == NULL)
 190                         perror(oname);
 191                 else
 192                         add_file(&seek_files, sip->sps_fp, oname);
 193         }
 194         else
 195                 sip->sps_fp = NULL;
 196
 197         return sip;
 198 }
 199
 200 void seeki_exit(void *param)
 201 {
 202         struct seeki *sip = param;
 203
 204         if (sip->sps_fp && sip->sps.nseeks != 0)
 205                 sps_emit(sip);
 206
 207         /*
 208          * Associated files are cleaned up by seek_clean
 209          */
 210         __destroy(sip->root.rb_node);
 211         free(sip);
 212 }
 213
 214 void seeki_add(void *handle, struct io *iop)
 215 {
 216         struct seeki *sip = handle;
 217         char rw = IOP_READ(iop) ? 'r' : 'w';
 218         long long dist = seek_dist(sip, iop);
 219         double tstamp = BIT_TIME(iop->t.time);
 220         FILE *fp = IOP_READ(iop) ? sip->rfp : sip->wfp;
 221
 222         if (fp)
 223                 fprintf(fp, "%15.9lf %13lld %c\n", tstamp, dist, rw);
 224         if (sip->cfp)
 225                 fprintf(sip->cfp, "%15.9lf %13lld %c\n", tstamp, dist, rw);
 226
 227         dist = llabs(dist);
 228         sip->tot_seeks++;
 229         sip->total_sectors += dist;
 230         __insert(&sip->root, dist);
 231
 232         sps_add(sip, tstamp);
 233 }
 234
 235 long long seeki_nseeks(void *handle)
 236 {
 237         return ((struct seeki *)handle)->tot_seeks;
 238 }
 239
 240 double seeki_mean(void *handle)
 241 {
 242         struct seeki *sip = handle;
 243         return sip->total_sectors / sip->tot_seeks;
 244 }
 245
 246 int __median(struct rb_node *n, long long sofar, long long target, long
 247                    long *rvp)
 248 {
 249         struct seek_bkt *sbp;
 250
 251         sbp = rb_entry(n, struct seek_bkt, rb_node);
 252         if ((sofar + sbp->nseeks) >= target) {
 253                 *rvp = sbp->sectors;
 254                 return 1;
 255         }
 256
 257         if (n->rb_left && __median(n->rb_left, sofar, target, rvp))
 258                 return 1;
 259
 260         if (n->rb_right && __median(n->rb_right, sofar, target, rvp))
 261                 return 1;
 262
 263         return 0;
 264
 265 }
 266
 267 long long seeki_median(void *handle)
 268 {
 269         long long rval = 0LL;
 270         struct seeki *sip = handle;
 271
 272         if (sip->root.rb_node)
 273                 (void)__median(sip->root.rb_node, 0LL, sip->tot_seeks / 2,
 274                                &rval);
 275
 276         return rval;
 277 }
 278
 279 void __mode(struct rb_node *n, struct mode *mp)
 280 {
 281         struct seek_bkt *sbp;
 282
 283         if (n->rb_left) __mode(n->rb_left, mp);
 284         if (n->rb_right) __mode(n->rb_right, mp);
 285
 286         sbp = rb_entry(n, struct seek_bkt, rb_node);
 287         if (mp->modes == NULL) {
 288                 mp->modes = malloc(sizeof(long long));
 289                 mp->nmds = 0;
 290         }
 291         else if (sbp->nseeks > mp->most_seeks)
 292                 mp->nmds = 0;
 293         else if (sbp->nseeks == mp->most_seeks)
 294                 mp->modes = realloc(mp->modes, (mp->nmds + 1) *
 295                                                         sizeof(long long));
 296         else
 297                 return;
 298
 299         mp->most_seeks = sbp->nseeks;
 300         mp->modes[mp->nmds++] = sbp->sectors;
 301 }
 302
 303 int seeki_mode(void *handle, struct mode *mp)
 304 {
 305         struct seeki *sip = handle;
 306         struct rb_root *root = &sip->root;
 307
 308         memset(mp, 0, sizeof(struct mode));
 309         if (root->rb_node)
 310                 __mode(root->rb_node, mp);
 311
 312         return mp->nmds;
 313 }