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
24struct seek_bkt {
25	struct rb_node rb_node;
26	long long sectors;
27	int nseeks;
28};
29
30/* Seeks per second */
31struct sps_bkt {
32	double t_start, t_last;
33	unsigned long nseeks;
34};
35
36struct 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
45static 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
62static 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
89static 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
100static 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
121static 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
138static 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
159static 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
184long 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
208void *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
237void 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
251void 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
272long long seeki_nseeks(void *handle)
273{
274	return ((struct seeki *)handle)->tot_seeks;
275}
276
277double seeki_mean(void *handle)
278{
279	struct seeki *sip = handle;
280	return sip->total_sectors / sip->tot_seeks;
281}
282
283long 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
295int 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