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 struct seeki {
  32         FILE *rfp, *wfp, *cfp;
  33         struct rb_root root;
  34         long long tot_seeks;
  35         double total_sectors;
  36         long long last_start, last_end;
  37 };
  38
  39 static FILE *seek_open(char *str, char rw)
  40 {
  41         FILE *fp;
  42         char *oname;
  43
  44         if (seek_name == NULL) return NULL;
  45
  46         oname = malloc(strlen(seek_name) + strlen(str) + 32);
  47         sprintf(oname, "%s_%s_%c.dat", seek_name, str, rw);
  48         if ((fp = fopen(oname, "w")) == NULL)
  49                 perror(oname);
  50         else
  51                 add_file(&seek_files, fp, oname);
  52
  53         return fp;
  54 }
  55
  56 static void __insert(struct rb_root *root, long long sectors)
  57 {
  58         struct seek_bkt *sbp;
  59         struct rb_node *parent = NULL;
  60         struct rb_node **p = &root->rb_node;
  61
  62         while (*p) {
  63                 parent = *p;
  64                 sbp = rb_entry(parent, struct seek_bkt, rb_node);
  65                 if (sectors < sbp->sectors)
  66                         p = &(*p)->rb_left;
  67                 else if (sectors > sbp->sectors)
  68                         p = &(*p)->rb_right;
  69                 else {
  70                         sbp->nseeks++;
  71                         return;
  72                 }
  73         }
  74
  75         sbp = malloc(sizeof(struct seek_bkt));
  76         sbp->nseeks = 1;
  77         sbp->sectors = sectors;
  78
  79         rb_link_node(&sbp->rb_node, parent, p);
  80         rb_insert_color(&sbp->rb_node, root);
  81 }
  82
  83 static void __destroy(struct rb_node *n)
  84 {
  85         if (n) {
  86                 struct seek_bkt *sbp = rb_entry(n, struct seek_bkt, rb_node);
  87
  88                 __destroy(n->rb_left);
  89                 __destroy(n->rb_right);
  90                 free(sbp);
  91         }
  92 }
  93
  94 void seek_clean(void)
  95 {
  96         clean_files(&seek_files);
  97 }
  98
  99 long long seek_dist(struct seeki *sip, struct io *iop)
 100 {
 101         long long dist;
 102         long long start = BIT_START(iop), end = BIT_END(iop);
 103
 104         if (seek_absolute)
 105                 dist = start - sip->last_end;
 106         else {
 107                 /* Some overlap means no seek */
 108                 if (((sip->last_start <= start) && (start <= sip->last_end)) ||
 109                     ((sip->last_start <= end) && (end <= sip->last_end)))
 110                         dist = 0;
 111                 else if (start > sip->last_end)
 112                         dist = start - sip->last_end;
 113                 else
 114                         dist = start - sip->last_start;
 115
 116         }
 117
 118         sip->last_start = start;
 119         sip->last_end = end;
 120         return dist;
 121 }
 122
 123 void *seeki_init(char *str)
 124 {
 125         struct seeki *sip = malloc(sizeof(struct seeki));
 126
 127         sip->rfp = seek_open(str, 'r');
 128         sip->wfp = seek_open(str, 'w');
 129         sip->cfp = seek_open(str, 'c');
 130         sip->tot_seeks = 0;
 131         sip->total_sectors = 0.0;
 132         sip->last_start = sip->last_end = 0;
 133         memset(&sip->root, 0, sizeof(sip->root));
 134
 135         return sip;
 136 }
 137
 138 void seeki_exit(void *param)
 139 {
 140         struct seeki *sip = param;
 141
 142         /*
 143          * Associated files are cleaned up by seek_clean
 144          */
 145         __destroy(sip->root.rb_node);
 146         free(sip);
 147 }
 148
 149 void seeki_add(void *handle, struct io *iop)
 150 {
 151         struct seeki *sip = handle;
 152         char rw = IOP_READ(iop) ? 'r' : 'w';
 153         long long dist = seek_dist(sip, iop);
 154         double tstamp = BIT_TIME(iop->t.time);
 155         FILE *fp = IOP_READ(iop) ? sip->rfp : sip->wfp;
 156
 157         if (fp)
 158                 fprintf(fp, "%15.9lf %13lld %c\n", tstamp, dist, rw);
 159         if (sip->cfp)
 160                 fprintf(sip->cfp, "%15.9lf %13lld %c\n", tstamp, dist, rw);
 161
 162         dist = llabs(dist);
 163         sip->tot_seeks++;
 164         sip->total_sectors += dist;
 165         __insert(&sip->root, dist);
 166 }
 167
 168 long long seeki_nseeks(void *handle)
 169 {
 170         return ((struct seeki *)handle)->tot_seeks;
 171 }
 172
 173 double seeki_mean(void *handle)
 174 {
 175         struct seeki *sip = handle;
 176         return sip->total_sectors / sip->tot_seeks;
 177 }
 178
 179 int __median(struct rb_node *n, long long sofar, long long target, long
 180                    long *rvp)
 181 {
 182         struct seek_bkt *sbp;
 183
 184         sbp = rb_entry(n, struct seek_bkt, rb_node);
 185         if ((sofar + sbp->nseeks) >= target) {
 186                 *rvp = sbp->sectors;
 187                 return 1;
 188         }
 189
 190         if (n->rb_left && __median(n->rb_left, sofar, target, rvp))
 191                 return 1;
 192
 193         if (n->rb_right && __median(n->rb_right, sofar, target, rvp))
 194                 return 1;
 195
 196         return 0;
 197
 198 }
 199
 200 long long seeki_median(void *handle)
 201 {
 202         long long rval = 0LL;
 203         struct seeki *sip = handle;
 204
 205         if (sip->root.rb_node)
 206                 (void)__median(sip->root.rb_node, 0LL, sip->tot_seeks / 2,
 207                                &rval);
 208
 209         return rval;
 210 }
 211
 212 void __mode(struct rb_node *n, struct mode *mp)
 213 {
 214         struct seek_bkt *sbp;
 215
 216         if (n->rb_left) __mode(n->rb_left, mp);
 217         if (n->rb_right) __mode(n->rb_right, mp);
 218
 219         sbp = rb_entry(n, struct seek_bkt, rb_node);
 220         if (mp->modes == NULL) {
 221                 mp->modes = malloc(sizeof(long long));
 222                 mp->nmds = 0;
 223         }
 224         else if (sbp->nseeks > mp->most_seeks)
 225                 mp->nmds = 0;
 226         else if (sbp->nseeks == mp->most_seeks)
 227                 mp->modes = realloc(mp->modes, (mp->nmds + 1) *
 228                                                         sizeof(long long));
 229         else
 230                 return;
 231
 232         mp->most_seeks = sbp->nseeks;
 233         mp->modes[mp->nmds++] = sbp->sectors;
 234 }
 235
 236 int seeki_mode(void *handle, struct mode *mp)
 237 {
 238         struct seeki *sip = handle;
 239         struct rb_root *root = &sip->root;
 240
 241         memset(mp, 0, sizeof(struct mode));
 242         if (root->rb_node)
 243                 __mode(root->rb_node, mp);
 244
 245         return mp->nmds;
 246 }