1 /* 2 * blktrace output analysis: generate a timeline & gather statistics 3 * 4 * Copyright (C) 2006 Alan D. Brunelle <Alan.Brunelle (at) 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(char *str) 209 { 210 struct seeki *sip = malloc(sizeof(struct seeki)); 211 212 sip->rfp = seek_open(str, 'r'); 213 sip->wfp = seek_open(str, 'w'); 214 sip->cfp = seek_open(str, 'c'); 215 sip->tot_seeks = 0; 216 sip->total_sectors = 0.0; 217 sip->last_start = sip->last_end = 0; 218 memset(&sip->root, 0, sizeof(sip->root)); 219 220 if (sps_name) { 221 char *oname; 222 223 memset(&sip->sps, 0, sizeof(sip->sps)); 224 225 oname = malloc(strlen(sps_name) + strlen(str) + 32); 226 sprintf(oname, "%s_%s.dat", sps_name, str); 227 if ((sip->sps_fp = my_fopen(oname, "w")) == NULL) 228 perror(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 } 306
