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
seek_open(char * str,char rw)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
__insert(struct rb_root * root,long long sectors)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
__destroy(struct rb_node * n)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
sps_emit(struct seeki * sip)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
sps_add(struct seeki * sip,double t)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
__median(struct rb_node * n,long long sofar,long long target,long long * rvp)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
__mode(struct rb_node * n,struct mode * mp)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
seek_dist(struct seeki * sip,struct io * iop)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
seeki_alloc(struct d_info * dip,char * post)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
seeki_free(void * param)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
seeki_add(void * handle,struct io * iop)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
seeki_nseeks(void * handle)272 long long seeki_nseeks(void *handle)
273 {
274 return ((struct seeki *)handle)->tot_seeks;
275 }
276
seeki_mean(void * handle)277 double seeki_mean(void *handle)
278 {
279 struct seeki *sip = handle;
280 return sip->total_sectors / sip->tot_seeks;
281 }
282
seeki_median(void * handle)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
seeki_mode(void * handle,struct mode * mp)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