Commit | Line | Data |
---|---|---|
5225e788 AB |
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 | ||
6eb42155 | 23 | static struct file_info *seek_files = NULL; |
b2ecdd0f | 24 | |
5225e788 | 25 | struct seek_bkt { |
6eb42155 | 26 | struct rb_node rb_node; |
5225e788 AB |
27 | long long sectors; |
28 | int nseeks; | |
29 | }; | |
30 | ||
ccf6d55e AB |
31 | /* Seeks per second */ |
32 | struct sps_bkt { | |
33 | double t_start, t_last; | |
34 | unsigned long nseeks; | |
35 | }; | |
36 | ||
5225e788 | 37 | struct seeki { |
ccf6d55e | 38 | FILE *rfp, *wfp, *cfp, *sps_fp; |
6eb42155 | 39 | struct rb_root root; |
ccf6d55e | 40 | struct sps_bkt sps; |
6eb42155 | 41 | long long tot_seeks; |
5225e788 AB |
42 | double total_sectors; |
43 | long long last_start, last_end; | |
44 | }; | |
45 | ||
4c48f14e | 46 | static FILE *seek_open(char *str, char rw) |
5225e788 AB |
47 | { |
48 | FILE *fp; | |
49 | char *oname; | |
5225e788 AB |
50 | |
51 | if (seek_name == NULL) return NULL; | |
52 | ||
4c48f14e AB |
53 | oname = malloc(strlen(seek_name) + strlen(str) + 32); |
54 | sprintf(oname, "%s_%s_%c.dat", seek_name, str, rw); | |
5225e788 AB |
55 | if ((fp = fopen(oname, "w")) == NULL) |
56 | perror(oname); | |
b2ecdd0f | 57 | else |
6eb42155 | 58 | add_file(&seek_files, fp, oname); |
5225e788 AB |
59 | |
60 | return fp; | |
61 | } | |
62 | ||
6eb42155 ADB |
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 | ||
69040794 AB |
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 | ||
ccf6d55e AB |
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 | ||
b2ecdd0f ADB |
141 | void seek_clean(void) |
142 | { | |
6eb42155 | 143 | clean_files(&seek_files); |
b2ecdd0f ADB |
144 | } |
145 | ||
5225e788 AB |
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 | ||
69040794 | 151 | if (seek_absolute) |
5225e788 | 152 | dist = start - sip->last_end; |
69040794 AB |
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 | } | |
5225e788 AB |
164 | |
165 | sip->last_start = start; | |
166 | sip->last_end = end; | |
167 | return dist; | |
168 | } | |
169 | ||
4c48f14e | 170 | void *seeki_init(char *str) |
5225e788 AB |
171 | { |
172 | struct seeki *sip = malloc(sizeof(struct seeki)); | |
173 | ||
4c48f14e AB |
174 | sip->rfp = seek_open(str, 'r'); |
175 | sip->wfp = seek_open(str, 'w'); | |
176 | sip->cfp = seek_open(str, 'c'); | |
6eb42155 | 177 | sip->tot_seeks = 0; |
5225e788 AB |
178 | sip->total_sectors = 0.0; |
179 | sip->last_start = sip->last_end = 0; | |
6eb42155 | 180 | memset(&sip->root, 0, sizeof(sip->root)); |
5225e788 | 181 | |
ccf6d55e AB |
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 | ||
5225e788 AB |
197 | return sip; |
198 | } | |
199 | ||
69040794 AB |
200 | void seeki_exit(void *param) |
201 | { | |
202 | struct seeki *sip = param; | |
203 | ||
ccf6d55e AB |
204 | if (sip->sps_fp && sip->sps.nseeks != 0) |
205 | sps_emit(sip); | |
206 | ||
69040794 AB |
207 | /* |
208 | * Associated files are cleaned up by seek_clean | |
209 | */ | |
210 | __destroy(sip->root.rb_node); | |
211 | free(sip); | |
212 | } | |
213 | ||
5225e788 AB |
214 | void seeki_add(void *handle, struct io *iop) |
215 | { | |
5225e788 | 216 | struct seeki *sip = handle; |
69040794 | 217 | char rw = IOP_READ(iop) ? 'r' : 'w'; |
5225e788 | 218 | long long dist = seek_dist(sip, iop); |
69040794 | 219 | double tstamp = BIT_TIME(iop->t.time); |
5225e788 AB |
220 | FILE *fp = IOP_READ(iop) ? sip->rfp : sip->wfp; |
221 | ||
222 | if (fp) | |
69040794 AB |
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); | |
5225e788 AB |
226 | |
227 | dist = llabs(dist); | |
6eb42155 | 228 | sip->tot_seeks++; |
5225e788 | 229 | sip->total_sectors += dist; |
6eb42155 | 230 | __insert(&sip->root, dist); |
ccf6d55e AB |
231 | |
232 | sps_add(sip, tstamp); | |
5225e788 AB |
233 | } |
234 | ||
235 | long long seeki_nseeks(void *handle) | |
236 | { | |
6eb42155 | 237 | return ((struct seeki *)handle)->tot_seeks; |
5225e788 AB |
238 | } |
239 | ||
240 | double seeki_mean(void *handle) | |
241 | { | |
242 | struct seeki *sip = handle; | |
6eb42155 ADB |
243 | return sip->total_sectors / sip->tot_seeks; |
244 | } | |
245 | ||
8b10aae0 | 246 | int __median(struct rb_node *n, long long sofar, long long target, long |
6eb42155 ADB |
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 | ||
5225e788 AB |
265 | } |
266 | ||
267 | long long seeki_median(void *handle) | |
268 | { | |
6eb42155 | 269 | long long rval = 0LL; |
5225e788 | 270 | struct seeki *sip = handle; |
5225e788 | 271 | |
6eb42155 | 272 | if (sip->root.rb_node) |
8b10aae0 | 273 | (void)__median(sip->root.rb_node, 0LL, sip->tot_seeks / 2, |
6eb42155 | 274 | &rval); |
5225e788 | 275 | |
6eb42155 | 276 | return rval; |
5225e788 AB |
277 | } |
278 | ||
6eb42155 ADB |
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) | |
8b10aae0 | 294 | mp->modes = realloc(mp->modes, (mp->nmds + 1) * |
6eb42155 ADB |
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) | |
5225e788 | 304 | { |
5225e788 | 305 | struct seeki *sip = handle; |
6eb42155 ADB |
306 | struct rb_root *root = &sip->root; |
307 | ||
308 | memset(mp, 0, sizeof(struct mode)); | |
8b10aae0 | 309 | if (root->rb_node) |
6eb42155 | 310 | __mode(root->rb_node, mp); |
5225e788 | 311 | |
6eb42155 | 312 | return mp->nmds; |
5225e788 | 313 | } |