[blktrace.git] / btt / seek.c

/*
 * blktrace output analysis: generate a timeline & gather statistics
 *
 * Copyright (C) 2006 Alan D. Brunelle <Alan.Brunelle@hp.com>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 */
#include <float.h>
#include "globals.h"

struct seek_bkt {
	struct rb_node rb_node;
	long long sectors;
	int nseeks;
};

/* Seeks per second */
struct sps_bkt {
	double t_start, t_last;
	unsigned long nseeks;
};

struct seeki {
	FILE *rfp, *wfp, *cfp, *sps_fp;
	struct rb_root root;
	struct sps_bkt sps;
	long long tot_seeks;
	double total_sectors;
	long long last_start, last_end;
};

static FILE *seek_open(char *str, char rw)
{
	FILE *fp;
	char *oname;

	if (seek_name == NULL) return NULL;

	oname = malloc(strlen(seek_name) + strlen(str) + 32);
	sprintf(oname, "%s_%s_%c.dat", seek_name, str, rw);
	if ((fp = my_fopen(oname, "w")) == NULL) {
		perror(oname);
		free(oname);
	} else
		add_file(fp, oname);

	return fp;
}

static void __insert(struct rb_root *root, long long sectors)
{
	struct seek_bkt *sbp;
	struct rb_node *parent = NULL;
	struct rb_node **p = &root->rb_node;

	while (*p) {
		parent = *p;
		sbp = rb_entry(parent, struct seek_bkt, rb_node);
		if (sectors < sbp->sectors)
			p = &(*p)->rb_left;
		else if (sectors > sbp->sectors)
			p = &(*p)->rb_right;
		else {
			sbp->nseeks++;
			return;
		}
	}

	sbp = malloc(sizeof(struct seek_bkt));
	sbp->nseeks = 1;
	sbp->sectors = sectors;

	rb_link_node(&sbp->rb_node, parent, p);
	rb_insert_color(&sbp->rb_node, root);
}

static void __destroy(struct rb_node *n)
{
	if (n) {
		struct seek_bkt *sbp = rb_entry(n, struct seek_bkt, rb_node);

		__destroy(n->rb_left);
		__destroy(n->rb_right);
		free(sbp);
	}
}

static void sps_emit(struct seeki *sip)
{
	double s_p_s;
	struct sps_bkt *sps = &sip->sps;
	double delta = sps->t_last - sps->t_start;

	if ((sps->nseeks == 1) || (delta < DBL_EPSILON))
		s_p_s = (double)(sps->nseeks);
	else
		s_p_s = (double)(sps->nseeks) / delta;

	fprintf(sip->sps_fp, "%15.9lf %.2lf\n", sps->t_start, s_p_s);

	sps->t_start = 0;
	sps->nseeks = 0;
}

static void sps_add(struct seeki *sip, double t)
{
	if (sip->sps_fp) {
		struct sps_bkt *sps = &sip->sps;

		if (sps->nseeks != 0 && ((t - sps->t_start) >= 1.0))
			sps_emit(sip);

		sps->t_last = t;
		if (sps->nseeks == 0) {
			sps->t_start = t;
			sps->nseeks = 1;
		} else
			sps->nseeks++;
	}
}

static int __median(struct rb_node *n, long long sofar, long long target,
		    long long *rvp)
{
	struct seek_bkt *sbp;

	sbp = rb_entry(n, struct seek_bkt, rb_node);
	if ((sofar + sbp->nseeks) >= target) {
		*rvp = sbp->sectors;
		return 1;
	}

	if (n->rb_left && __median(n->rb_left, sofar, target, rvp))
		return 1;

	if (n->rb_right && __median(n->rb_right, sofar, target, rvp))
		return 1;

	return 0;

}

static void __mode(struct rb_node *n, struct mode *mp)
{
	struct seek_bkt *sbp;

	if (n->rb_left)
		__mode(n->rb_left, mp);
	if (n->rb_right)
		__mode(n->rb_right, mp);

	sbp = rb_entry(n, struct seek_bkt, rb_node);
	if (mp->modes == NULL) {
		mp->modes = malloc(sizeof(long long));
		mp->nmds = 0;
	} else if (sbp->nseeks > mp->most_seeks)
		mp->nmds = 0;
	else if (sbp->nseeks == mp->most_seeks)
		mp->modes = realloc(mp->modes, (mp->nmds + 1) *
							sizeof(long long));
	else
		return;

	mp->most_seeks = sbp->nseeks;
	mp->modes[mp->nmds++] = sbp->sectors;
}

long long seek_dist(struct seeki *sip, struct io *iop)
{
	long long dist;
	long long start = BIT_START(iop), end = BIT_END(iop);

	if (seek_absolute)
		dist = start - sip->last_end;
	else {
		/* Some overlap means no seek */
		if (((sip->last_start <= start) && (start <= sip->last_end)) ||
		    ((sip->last_start <= end) && (end <= sip->last_end)))
			dist = 0;
		else if (start > sip->last_end)
			dist = start - sip->last_end;
		else
			dist = start - sip->last_start;

	}

	sip->last_start = start;
	sip->last_end = end;
	return dist;
}

void *seeki_alloc(struct d_info *dip, char *post)
{
	char str[256];
	struct seeki *sip = malloc(sizeof(struct seeki));

	sprintf(str, "%s%s", dip->dip_name, post);
	sip->rfp = seek_open(str, 'r');
	sip->wfp = seek_open(str, 'w');
	sip->cfp = seek_open(str, 'c');
	sip->tot_seeks = 0;
	sip->total_sectors = 0.0;
	sip->last_start = sip->last_end = 0;
	memset(&sip->root, 0, sizeof(sip->root));

	if (sps_name) {
		char *oname;

		memset(&sip->sps, 0, sizeof(sip->sps));

		oname = malloc(strlen(sps_name) + strlen(dip->dip_name) + 32);
		sprintf(oname, "%s_%s.dat", sps_name, dip->dip_name);
		if ((sip->sps_fp = my_fopen(oname, "w")) == NULL) {
			perror(oname);
			free(oname);
		} else
			add_file(sip->sps_fp, oname);
	} else
		sip->sps_fp = NULL;

	return sip;
}

void seeki_free(void *param)
{
	struct seeki *sip = param;

	if (sip->sps_fp && sip->sps.nseeks != 0)
		sps_emit(sip);

	/*
	 * Associated files are cleaned up by seek_clean
	 */
	__destroy(sip->root.rb_node);
	free(sip);
}

void seeki_add(void *handle, struct io *iop)
{
	struct seeki *sip = handle;
	char rw = IOP_READ(iop) ? 'r' : 'w';
	long long dist = seek_dist(sip, iop);
	double tstamp = BIT_TIME(iop->t.time);
	FILE *fp = IOP_READ(iop) ? sip->rfp : sip->wfp;

	if (fp)
		fprintf(fp, "%15.9lf %13lld %c\n", tstamp, dist, rw);
	if (sip->cfp)
		fprintf(sip->cfp, "%15.9lf %13lld %c\n", tstamp, dist, rw);

	dist = llabs(dist);
	sip->tot_seeks++;
	sip->total_sectors += dist;
	__insert(&sip->root, dist);

	sps_add(sip, tstamp);
}

long long seeki_nseeks(void *handle)
{
	return ((struct seeki *)handle)->tot_seeks;
}

double seeki_mean(void *handle)
{
	struct seeki *sip = handle;
	return sip->total_sectors / sip->tot_seeks;
}

long long seeki_median(void *handle)
{
	long long rval = 0LL;
	struct seeki *sip = handle;

	if (sip->root.rb_node)
		(void)__median(sip->root.rb_node, 0LL, sip->tot_seeks / 2,
			       &rval);

	return rval;
}

int seeki_mode(void *handle, struct mode *mp)
{
	struct seeki *sip = handle;
	struct rb_root *root = &sip->root;

	memset(mp, 0, sizeof(struct mode));
	if (root->rb_node)
		__mode(root->rb_node, mp);

	return mp->nmds;
}
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	*/
5bebfd16	21	#include <float.h>
5225e788 AB	22	#include "globals.h"
	23
	24	struct seek_bkt {
6eb42155	25	struct rb_node rb_node;
5225e788 AB	26	long long sectors;
	27	int nseeks;
	28	};
	29
ccf6d55e AB	30	/* Seeks per second */
	31	struct sps_bkt {
	32	double t_start, t_last;
	33	unsigned long nseeks;
	34	};
	35
5225e788	36	struct seeki {
ccf6d55e	37	FILE rfp, wfp, cfp, sps_fp;
6eb42155	38	struct rb_root root;
ccf6d55e	39	struct sps_bkt sps;
6eb42155	40	long long tot_seeks;
5225e788 AB	41	double total_sectors;
	42	long long last_start, last_end;
	43	};
	44
4c48f14e	45	static FILE seek_open(char str, char rw)
5225e788 AB	46	{
	47	FILE *fp;
	48	char *oname;
5225e788 AB	49
	50	if (seek_name == NULL) return NULL;
	51
4c48f14e AB	52	oname = malloc(strlen(seek_name) + strlen(str) + 32);
4c48f14e AB	53	sprintf(oname, "%s_%s_%c.dat", seek_name, str, rw);
84b321fa	54	if ((fp = my_fopen(oname, "w")) == NULL) {
5225e788	55	perror(oname);
84b321fa ES	56	free(oname);
84b321fa ES	57	} else
c053af42	58	add_file(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)
ccf6d55e AB	102	{
f6d38abd	103	double s_p_s;
ccf6d55e	104	struct sps_bkt *sps = &sip->sps;
5bebfd16	105	double delta = sps->t_last - sps->t_start;
ccf6d55e	106
f6d38abd	107	if ((sps->nseeks == 1) \|\| (delta < DBL_EPSILON))
5bebfd16	108	s_p_s = (double)(sps->nseeks);
f6d38abd	109	else
ccf6d55e	110	s_p_s = (double)(sps->nseeks) / delta;
ccf6d55e AB	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
	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;
c053af42	130	} else
ccf6d55e AB	131	sps->nseeks++;
	132	}
	133	}
	134
c053af42 AB	135	static int __median(struct rb_node *n, long long sofar, long long target,
c053af42 AB	136	long long *rvp)
b2ecdd0f	137	{
c053af42 AB	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
	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;
b2ecdd0f ADB	179	}
b2ecdd0f ADB	180
5225e788 AB	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
69040794	186	if (seek_absolute)
5225e788	187	dist = start - sip->last_end;
69040794 AB	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	}
5225e788 AB	199
	200	sip->last_start = start;
	201	sip->last_end = end;
	202	return dist;
	203	}
	204
a155ab98	205	void seeki_alloc(struct d_info dip, char *post)
5225e788	206	{
a155ab98	207	char str[256];
5225e788 AB	208	struct seeki *sip = malloc(sizeof(struct seeki));
5225e788 AB	209
a155ab98	210	sprintf(str, "%s%s", dip->dip_name, post);
4c48f14e AB	211	sip->rfp = seek_open(str, 'r');
	212	sip->wfp = seek_open(str, 'w');
	213	sip->cfp = seek_open(str, 'c');
6eb42155	214	sip->tot_seeks = 0;
5225e788 AB	215	sip->total_sectors = 0.0;
5225e788 AB	216	sip->last_start = sip->last_end = 0;
6eb42155	217	memset(&sip->root, 0, sizeof(sip->root));
5225e788	218
ccf6d55e AB	219	if (sps_name) {
	220	char *oname;
	221
	222	memset(&sip->sps, 0, sizeof(sip->sps));
	223
a155ab98 AB	224	oname = malloc(strlen(sps_name) + strlen(dip->dip_name) + 32);
a155ab98 AB	225	sprintf(oname, "%s_%s.dat", sps_name, dip->dip_name);
84b321fa	226	if ((sip->sps_fp = my_fopen(oname, "w")) == NULL) {
ccf6d55e	227	perror(oname);
84b321fa ES	228	free(oname);
84b321fa ES	229	} else
c053af42 AB	230	add_file(sip->sps_fp, oname);
c053af42 AB	231	} else
ccf6d55e AB	232	sip->sps_fp = NULL;
ccf6d55e AB	233
5225e788 AB	234	return sip;
	235	}
	236
c053af42	237	void seeki_free(void *param)
69040794 AB	238	{
	239	struct seeki *sip = param;
	240
ccf6d55e AB	241	if (sip->sps_fp && sip->sps.nseeks != 0)
	242	sps_emit(sip);
	243
69040794 AB	244	/*
	245	* Associated files are cleaned up by seek_clean
	246	*/
	247	__destroy(sip->root.rb_node);
	248	free(sip);
	249	}
	250
5225e788 AB	251	void seeki_add(void handle, struct io iop)
5225e788 AB	252	{
5225e788	253	struct seeki *sip = handle;
69040794	254	char rw = IOP_READ(iop) ? 'r' : 'w';
5225e788	255	long long dist = seek_dist(sip, iop);
69040794	256	double tstamp = BIT_TIME(iop->t.time);
5225e788 AB	257	FILE *fp = IOP_READ(iop) ? sip->rfp : sip->wfp;
	258
	259	if (fp)
69040794 AB	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);
5225e788 AB	263
5225e788 AB	264	dist = llabs(dist);
6eb42155	265	sip->tot_seeks++;
5225e788	266	sip->total_sectors += dist;
6eb42155	267	__insert(&sip->root, dist);
ccf6d55e AB	268
ccf6d55e AB	269	sps_add(sip, tstamp);
5225e788 AB	270	}
	271
	272	long long seeki_nseeks(void *handle)
	273	{
6eb42155	274	return ((struct seeki *)handle)->tot_seeks;
5225e788 AB	275	}
	276
	277	double seeki_mean(void *handle)
	278	{
	279	struct seeki *sip = handle;
6eb42155 ADB	280	return sip->total_sectors / sip->tot_seeks;
	281	}
	282
5225e788 AB	283	long long seeki_median(void *handle)
5225e788 AB	284	{
6eb42155	285	long long rval = 0LL;
5225e788	286	struct seeki *sip = handle;
5225e788	287
6eb42155	288	if (sip->root.rb_node)
8b10aae0	289	(void)__median(sip->root.rb_node, 0LL, sip->tot_seeks / 2,
6eb42155	290	&rval);
5225e788	291
6eb42155	292	return rval;
5225e788 AB	293	}
5225e788 AB	294
6eb42155	295	int seeki_mode(void handle, struct mode mp)
5225e788	296	{
5225e788	297	struct seeki *sip = handle;
6eb42155 ADB	298	struct rb_root *root = &sip->root;
	299
	300	memset(mp, 0, sizeof(struct mode));
8b10aae0	301	if (root->rb_node)
6eb42155	302	__mode(root->rb_node, mp);
5225e788	303
6eb42155	304	return mp->nmds;
5225e788	305	}