Combine all outstanding patches into one /big patch/

o  Added seek absolute option -- allows one to specify whether they want
   seek distances to be calculated based upon nearness to previous IO or
   from start to start.

o  Added block number dumping

o  Updated btt documentation for above.

o  Significant clean up of memory used and files opened. All allocated
   memory and opened files are cleaned up prior to normal program exit.

o  Fixed problem where Q & M traces were not being freed properly.

o  Fixed problem where bilink structures were not being freed properly.

o  Fixed omission -- output combined seeks in addition to read and
   write seeks.

Signed-off-by: Alan D. Brunelle <Alan.Brunelle@hp.com>
Signed-off-by: Jens Axboe <jens.axboe@oracle.com>

14 files changed, 492 insertions, 123 deletions

diff --git a/btt/Makefile b/btt/Makefile
index 5c825eb..920c70c 100644
--- a/btt/Makefile
+++ b/btt/Makefile
@@ -1,38 +1,39 @@
-CC	= gcc
-
-ECFLAGS	= 
-# ECFLAGS	= -DCOUNT_IOS
+#
+# OCFLAGS:
+# 	COUNT_IOS	- Counts struct io's left at end
+# 	DEBUG		- Various and sundy debug asserts
+# 	NDEBUG		- Defined: no asserts, Undefined: asserts
+#
 
-CFLAGS	= -Wall -O2 -W -g $(ECFLAGS)
-# CFLAGS	= -Wall -g -W -UDO_INLINE -DDEBUG $(ECFLAGS)
+CC	= gcc
+INCS	= -I. -I..
+OCFLAGS	= -UCOUNT_IOS -UDEBUG -DNDEBUG
+XCFLAGS	= -Wall -W -g -D_GNU_SOURCE -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64
+CFLAGS	= $(INCS) -O2 $(XCFLAGS) $(OCFLAGS)
 
-ALL_CFLAGS = $(CFLAGS) -I.. -D_GNU_SOURCE -D_LARGEFILE_SOURCE \
-		-D_FILE_OFFSET_BITS=64
 PROGS	= btt
-#ELIBS	= -lefence
-#PLIBS	= -lpthread
 LIBS	= $(PLIBS) $(ELIBS)
 OBJS	= args.o bt_timeline.o devmap.o devs.o dip_rb.o iostat.o latency.o \
 	  misc.o output.o proc.o seek.o trace.o trace_complete.o trace_im.o \
 	  trace_issue.o trace_queue.o trace_remap.o trace_requeue.o rbtree.o \
-	  mmap.o trace_plug.o
+	  mmap.o trace_plug.o bno_dump.o
 
 all: depend $(PROGS)
 
 rbtree.o: ../rbtree.c
-	$(CC) -o $*.o -c $(ALL_CFLAGS) $<
+	$(CC) -o $*.o -c $(CFLAGS) $<
 
 depend:
-	@$(CC) -MM $(ALL_CFLAGS) -I.. *.c 1> .depend
+	@$(CC) -MM $(CFLAGS) -I.. *.c 1> .depend
 
 clean: docsclean
 	-rm -f *.o $(PROGS) .depend
 
 %.o: %.c
-	$(CC) -o $*.o -c $(ALL_CFLAGS) $<
+	$(CC) -o $*.o -c $(CFLAGS) $<
 
 btt: $(OBJS)
-	$(CC) $(ALL_CFLAGS) -o $@ $(filter %.o,$^) $(LIBS)
+	$(CC) $(CFLAGS) -o $@ $(filter %.o,$^) $(LIBS)
 
 docs:
 	$(MAKE) -C doc all
diff --git a/btt/args.c b/btt/args.c
index 7fa087e..7a4a5fd 100644
--- a/btt/args.c
+++ b/btt/args.c
@@ -27,15 +27,29 @@
 #include <fcntl.h>
 #include "globals.h"
 
-#define S_OPTS	"Ad:D:e:hi:I:l:M:o:p:q:s:S:t:T:Vv"
+#define SETBUFFER_SIZE	(64 * 1024)
+
+#define S_OPTS	"aAB:d:D:e:hi:I:l:M:o:p:q:s:S:t:T:Vv"
 static struct option l_opts[] = {
 	{
+		.name = "seek-absolute",
+		.has_arg = no_argument,
+		.flag = NULL,
+		.val = 'a'
+	},
+	{
 		.name = "all-data",
 		.has_arg = no_argument,
 		.flag = NULL,
 		.val = 'A'
 	},
 	{
+		.name = "dump-blocknos",
+		.has_arg = required_argument,
+		.flag = NULL,
+		.val = 'B'
+	},
+	{
 		.name = "range-delta",
 		.has_arg = required_argument,
 		.flag = NULL,
@@ -143,7 +157,9 @@ static struct option l_opts[] = {
 };
 
 static char usage_str[] = \
-	"\n[ -A               | --all-data ]\n" \
+	"\n[ -a               | --seek-absolute ]\n" \
+	"[ -A               | --all-data ]\n" \
+	"[ -B <output name> | --dump-blocknos=<output name> ]\n" \
 	"[ -d <seconds>     | --range-delta=<seconds> ]\n" \
 	"[ -D <dev;...>     | --devices=<dev;...> ]\n" \
 	"[ -e <exe,...>     | --exes=<exe,...>  ]\n" \
@@ -162,21 +178,57 @@ static char usage_str[] = \
 	"[ -V               | --version ]\n" \
 	"[ -v               | --verbose ]\n\n";
 
+static struct file_info *arg_files = NULL;
+
 static void usage(char *prog)
 {
 	fprintf(stderr, "Usage: %s %s %s", prog, bt_timeline_version,
 		usage_str);
 }
 
+static FILE *setup_ofile(char *fname)
+{
+	if (fname) {
+		char *buf;
+		FILE *ofp = fopen(fname, "w");
+
+		if (!ofp) {
+			perror(fname);
+			exit(1);
+		}
+
+		buf = malloc(SETBUFFER_SIZE);
+		assert(buf);
+
+		setbuffer(ofp, buf, SETBUFFER_SIZE);
+		add_file(&arg_files, ofp, fname);
+		add_buf(buf);
+		return ofp;
+	}
+
+	return NULL;
+}
+
+void clean_args(void)
+{
+	clean_files(&arg_files);
+}
+
 void handle_args(int argc, char *argv[])
 {
 	int c;
 
 	while ((c = getopt_long(argc, argv, S_OPTS, l_opts, NULL)) != -1) {
 		switch (c) {
+		case 'a':
+			seek_absolute = 1;
+			break;
 		case 'A':
 			output_all_data = 1;
 			break;
+		case 'B':
+			bno_dump_name = strdup(optarg);
+			break;
 		case 'd':
 			sscanf(optarg, "%lf", &range_delta);
 			break;
@@ -273,21 +325,6 @@ void handle_args(int argc, char *argv[])
 		free(fname);
 	}
 
-	if (iostat_name != NULL) {
-		iostat_ofp = fopen(iostat_name, "w");
-		if (iostat_ofp == NULL) {
-			perror(iostat_name);
-			exit(1);
-		}
-		setbuffer(iostat_ofp, malloc(64 * 1024), 64 * 1024);
-	}
-
-	if (per_io_name != NULL) {
-		per_io_ofp = fopen(per_io_name, "w");
-		if (per_io_ofp == NULL) {
-			perror(per_io_name);
-			exit(1);
-		}
-		setbuffer(per_io_ofp, malloc(64 * 1024), 64 * 1024);
-	}
+	iostat_ofp = setup_ofile(iostat_name);
+	per_io_ofp = setup_ofile(per_io_name);
 }
diff --git a/btt/bno_dump.c b/btt/bno_dump.c
new file mode 100644
index 0000000..d1bc6ab
--- /dev/null
+++ b/btt/bno_dump.c
@@ -0,0 +1,92 @@
+/*
+ * 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 "globals.h"
+
+struct bno_dump {
+	FILE *rfp, *wfp, *cfp;
+};
+
+static struct file_info *bno_dump_files = NULL;
+
+static FILE *bno_dump_open(__u32 device, char rwc)
+{
+	FILE *fp;
+	char *oname;
+	int mjr, mnr;
+
+	mjr = device >> MINORBITS;
+	mnr = device & ((1 << MINORBITS) - 1);
+
+	oname = malloc(strlen(bno_dump_name) + 32);
+	sprintf(oname, "%s_%03d,%03d_%c.dat", bno_dump_name, mjr, mnr, rwc);
+	if ((fp = fopen(oname, "w")) == NULL)
+		perror(oname);
+	else
+		add_file(&bno_dump_files, fp, oname);
+	return fp;
+}
+
+void *bno_dump_init(__u32 device)
+{
+	struct bno_dump *bdp;
+
+	if (bno_dump_name == NULL) return NULL;
+
+	bdp = malloc(sizeof(*bdp));
+	bdp->rfp = bno_dump_open(device, 'r');
+	bdp->wfp = bno_dump_open(device, 'w');
+	bdp->cfp = bno_dump_open(device, 'c');
+
+	return bdp;
+}
+
+void bno_dump_exit(void *param)
+{
+	/*
+	 * Associated files will be auto-cleaned by bno_dump_clean
+	 */
+	free(param);
+}
+
+static inline void bno_dump_write(FILE *fp, struct io *iop)
+{
+	fprintf(fp, "%15.9lf %lld %lld\n",
+	        BIT_TIME(iop->t.time), 
+		(long long)BIT_START(iop), (long long)BIT_END(iop));
+}
+
+void bno_dump_add(void *handle, struct io *iop)
+{
+#	define RW_FP(bdp, iop)	(IOP_READ(iop) ? bdp->rfp : bdp->wfp)
+	struct bno_dump *bdp = handle;
+
+	if (bdp) {
+		if (RW_FP(bdp, iop))
+			bno_dump_write(RW_FP(bdp, iop), iop);
+		if (bdp->cfp)
+			bno_dump_write(bdp->cfp, iop);
+	}
+}
+
+void bno_dump_clean(void)
+{
+	clean_files(&bno_dump_files);
+}
diff --git a/btt/bt_timeline.c b/btt/bt_timeline.c
index e9407e0..76676a3 100644
--- a/btt/bt_timeline.c
+++ b/btt/bt_timeline.c
@@ -27,10 +27,10 @@
 
 char bt_timeline_version[] = "0.99.1";
 
-char *devices, *exes, *input_name, *output_name, *seek_name;
+char *devices, *exes, *input_name, *output_name, *seek_name, *bno_dump_name;
 char *d2c_name, *q2c_name, *per_io_name;
 FILE *ranges_ofp, *avgs_ofp, *per_io_ofp;
-int verbose, done, time_bounded, output_all_data;
+int verbose, done, time_bounded, output_all_data, seek_absolute;
 double t_astart, t_aend;
 unsigned long n_traces;
 struct avgs_info all_avgs;
@@ -39,6 +39,7 @@ time_t genesis, last_vtrace;
 LIST_HEAD(all_devs);
 LIST_HEAD(all_procs);
 LIST_HEAD(free_ios);
+LIST_HEAD(free_bilinks);
 LIST_HEAD(rmhd);
 LIST_HEAD(retries);
 __u64 q_histo[N_HIST_BKTS], d_histo[N_HIST_BKTS];
@@ -50,8 +51,6 @@ __u64 next_retry_check = 0;
 struct region_info all_regions = {
 	.qranges = LIST_HEAD_INIT(all_regions.qranges),
 	.cranges = LIST_HEAD_INIT(all_regions.cranges),
-	.qr_cur = NULL,
-	.cr_cur = NULL
 };
 
 #if defined(DEBUG)
@@ -74,6 +73,31 @@ int main(int argc, char *argv[])
 	if (process() || output_avgs(avgs_ofp) || output_ranges(ranges_ofp))
 		return 1;
 
+	if (iostat_ofp) {
+		fprintf(iostat_ofp, "\n");
+		iostat_dump_stats(iostat_last_stamp, 1);
+	}
+
+	if (ranges_ofp != stdout) 
+		fclose(ranges_ofp);
+	if (avgs_ofp != stdout) 
+		fclose(avgs_ofp);
+
+	seek_clean();
+	latency_clean();
+	bno_dump_clean();
+	dev_map_exit();
+	dip_exit();
+	pip_exit();
+	io_free_all();
+	bilink_free_all();
+	region_exit(&all_regions);
+
+	free(input_name);
+	if (output_name) free(output_name);
+
+	clean_bufs();
+
 	return 0;
 }
 
@@ -86,7 +110,7 @@ int process(void)
 {
 	int ret = 0;
 	struct io *iop = io_alloc();
-	struct timeval tvs, tvi, tve;
+	struct timeval tvs, tve;
 
 	genesis = last_vtrace = time(NULL);
 	gettimeofday(&tvs, NULL);
@@ -97,26 +121,17 @@ int process(void)
 
 	io_release(iop);
 	do_retries(0);
-
-	gettimeofday(&tvi, NULL);
-
-	if (iostat_ofp) {
-		fprintf(iostat_ofp, "\n");
-		iostat_dump_stats(iostat_last_stamp, 1);
-	}
-
-	seek_clean();
-	latency_clean();
 	gettimeofday(&tve, NULL);
 
 	if (verbose) {
-		double tps, dt_input = tv2dbl(&tvi) - tv2dbl(&tvs);
+		double tps, dt_input = tv2dbl(&tve) - tv2dbl(&tvs);
 		
 		tps = (double)n_traces / dt_input;
-		printf("%10lu traces @ %.1lf Ktps\t%.6lf+%.6lf=%.6lf\n", 
+		printf("\r                                        "
+		       "                                        \r");
+		printf("%10lu traces @ %.1lf Ktps in %.6lf seconds\n",
 			n_traces, tps/1000.0,
-			dt_input, tv2dbl(&tve) - tv2dbl(&tvi),
-			tv2dbl(&tve) - tv2dbl(&tvs));
+			dt_input);
 
 #		if defined(DEBUG)
 			printf("\ttree = |%d|\n", rb_tree_size);
diff --git a/btt/devmap.c b/btt/devmap.c
index 2b6366c..a74f224 100644
--- a/btt/devmap.c
+++ b/btt/devmap.c
@@ -23,6 +23,16 @@
 
 struct devmap *all_devmaps = NULL;
 
+void dev_map_exit(void)
+{
+	struct devmap *dmp;
+
+	while ((dmp = all_devmaps) != NULL) {
+		all_devmaps = dmp->next;
+		free(dmp);
+	}
+}
+
 void dev_map_add(struct devmap *dmp)
 {
 	struct devmap *this = malloc(sizeof(struct devmap));
diff --git a/btt/devs.c b/btt/devs.c
index 4aca9dd..9eece81 100644
--- a/btt/devs.c
+++ b/btt/devs.c
@@ -25,6 +25,33 @@
 #define DEV_HASH(dev)	((MAJOR(dev) ^ MINOR(dev)) & (N_DEV_HASH - 1))
 struct list_head	dev_heads[N_DEV_HASH];
 
+static inline void *dip_rb_mkhds(void)
+{
+	size_t len = N_IOP_TYPES * sizeof(struct rb_root);
+	return memset(malloc(len), 0, len);
+}
+
+static void __destroy(struct rb_node *n)
+{
+	if (n) {
+		struct io *iop = rb_entry(n, struct io, rb_node);
+
+		__destroy(n->rb_left);
+		__destroy(n->rb_right);
+		io_release(iop);
+	}
+}
+
+static void __destroy_heads(struct rb_root *roots)
+{
+	int i;
+
+	for (i = 0; i < N_IOP_TYPES; i++)
+		__destroy(roots[i].rb_node);
+
+	free(roots);
+}
+
 #if defined(DEBUG)
 void __dump_rb_node(struct rb_node *n)
 {
@@ -95,6 +122,22 @@ struct d_info *__dip_find(__u32 device)
 	return NULL;
 }
 
+void dip_exit(void)
+{
+	struct d_info *dip;
+	struct list_head *p, *q;
+
+	list_for_each_safe(p, q, &all_devs) {
+		dip = list_entry(p, struct d_info, all_head);
+
+		__destroy_heads(dip->heads);
+		region_exit(&dip->regions);
+		seeki_exit(dip->seek_handle);
+		bno_dump_exit(dip->bno_dump_handle);
+		free(dip);
+	}
+}
+
 struct d_info *dip_add(__u32 device, struct io *iop)
 {
 	struct d_info *dip = __dip_find(device);
@@ -103,11 +146,12 @@ struct d_info *dip_add(__u32 device, struct io *iop)
 		dip = malloc(sizeof(struct d_info));
 		memset(dip, 0, sizeof(*dip));
 		dip->heads = dip_rb_mkhds();
-		init_region(&dip->regions);
+		region_init(&dip->regions);
 		dip->device = device;
 		dip->last_q = (__u64)-1;
 		dip->map = dev_map_find(device);
 		dip->seek_handle = seeki_init(device);
+		dip->bno_dump_handle = bno_dump_init(device);
 		latency_init(dip);
 		list_add_tail(&dip->hash_head, &dev_heads[DEV_HASH(device)]);
 		list_add_tail(&dip->all_head, &all_devs);
diff --git a/btt/doc/btt.tex b/btt/doc/btt.tex
index af585c5..26cba36 100644
--- a/btt/doc/btt.tex
+++ b/btt/doc/btt.tex
@@ -1,5 +1,5 @@
 \documentclass{article}
-\usepackage{epsfig}
+\usepackage{epsfig,placeins}
 
 %
 % Copyright (C) 2007 Alan D. Brunelle <Alan.Brunelle@hp.com>
@@ -22,7 +22,7 @@
 
 \title{\texttt{btt} User Guide}
 \author{Alan D. Brunelle (Alan.Brunelle@hp.com)}
-\date{1 March 2007}
+\date{10 April 2007}
 
 \begin{document}
 \maketitle
@@ -591,12 +591,29 @@ Device:       rrqm/s   wrqm/s     r/s     w/s    rsec/s    wsec/s
   \epsfig{file=seek.eps,width=4.5in}
   \caption{\label{fig:seek}Seek Chart}
   \end{figure}
+  \FloatBarrier
+
+  The seek difference is calculated in one of two ways:
+
+  \begin{description}
+    \item[default] By default, the seek distance is calculated as the
+    \emph{closest} distance between the previous IO and this IO. The
+    concept of \emph{closeness} means that it could either be the
+    \emph{end} of the previous IO and the beginning of the next, or the
+    end of this IO and the start of the next.
+
+    \item[\texttt{-a}] If the \texttt{-a} or \texttt{--seek-absolute}
+    option is specified, then the seek distance is simply the difference
+    between the end of the previous IO and the start of this IO.
+  \end{description}
 
 \newpage\section{\label{sec:cmd-line}Command Line}
 
 \begin{verbatim}
 Usage: \texttt{btt} 0.99.1 
+[ -a               | --seek-absolute ]
 [ -A               | --all-data ]
+[ -B <output name> | --dump-blocknos=<output name> ]
 [ -d <seconds>     | --range-delta=<seconds> ]
 [ -D <dev;...>     | --devices=<dev;...> ]
 [ -e <exe,...>     | --exes=<exe,...>  ]
@@ -616,6 +633,14 @@ Usage: \texttt{btt} 0.99.1
 [ -v               | --verbose ]
 \end{verbatim}
 
+\subsection{\label{sec:o-a}\texttt{--seek-absolute}/\texttt{-a}}
+
+  When specified on the command line, this directs btt to calculate
+  seek distances based solely upon the ending block address of one IO,
+  and the start of the next.  By default \texttt{btt} uses the concept
+  of the closeness to either the beginning or end of the previous IO. See
+  section~\ref{sec:seek} for more details about seek distances.
+
 \subsection{\label{sec:o-A}\texttt{--all-data}/\texttt{-A}}
 
   Normally \texttt{btt} will not print out verbose information
@@ -623,6 +648,25 @@ Usage: \texttt{btt} 0.99.1
   section~\ref{sec:detailed-data}). If you desire that level of 
   detail you can specify this option.
 
+\subsection{\label{sec:o-B}\texttt{--dump-blocknos}/\texttt{-B}}
+
+  This option will output absolute block numbers to three files prefixed
+  by the specified output name:
+
+  \begin{description}
+    \item[\emph{prefix}\_\emph{device}\_r.dat] All read block numbers are
+    output, first column is time (seconds), second is the block number,
+    and the third column is the ending block number.
+
+    \item[\emph{prefix}\_\emph{device}\_w.dat] All write block numbers are
+    output, first column is time (seconds), second is the block number,
+    and the third column is the ending block number.
+
+    \item[\emph{prefix}\_\emph{device}\_c.dat] All block numbers (read
+    and write) are output, first column is time (seconds), second is
+    the block number, and the third column is the ending block number.
+  \end{description}
+
 \subsection{\label{sec:o-d}\texttt{--range-delta}/\texttt{-d}}
 
   Section~\ref{sec:activity} discussed how \texttt{btt} outputs a file
diff --git a/btt/globals.h b/btt/globals.h
index 9564817..ad50917 100644
--- a/btt/globals.h
+++ b/btt/globals.h
@@ -84,7 +84,7 @@ enum iop_type {
 struct file_info {
 	struct file_info *next;
 	FILE *ofp;
-	char oname[1];
+	char *oname;
 };
 
 struct mode {
@@ -124,7 +124,6 @@ struct range_info {
 struct region_info {
 	struct list_head qranges;
 	struct list_head cranges;
-	struct range_info *qr_cur, *cr_cur;
 };
 
 struct p_info {
@@ -132,7 +131,7 @@ struct p_info {
 	struct avgs_info avgs;
 	__u64 last_q;
 	__u32 pid;
-	char name[1];
+	char *name;
 };
 
 struct devmap {
@@ -159,7 +158,7 @@ struct d_info {
 	void *heads;
 	struct region_info regions;
 	struct devmap *map;
-	void *seek_handle;
+	void *seek_handle, *bno_dump_handle;
 	FILE *d2c_ofp, *q2c_ofp;
 	struct avgs_info avgs;
 	struct stats stats, all_stats;
@@ -191,21 +190,23 @@ struct bilink {
 	struct list_head down_head, up_head;
 	struct io *diop, *uiop;
 };
+#define bilink_free_head	down_head
 
 /* bt_timeline.c */
 
 extern char bt_timeline_version[], *devices, *exes, *input_name, *output_name;
 extern char *seek_name, *iostat_name, *d2c_name, *q2c_name, *per_io_name;
+extern char *bno_dump_name;
 extern double range_delta;
-extern FILE *ranges_ofp, *avgs_ofp, *iostat_ofp, *per_io_ofp;;
-extern int verbose, done, time_bounded, output_all_data;
+extern FILE *ranges_ofp, *avgs_ofp, *iostat_ofp, *per_io_ofp;
+extern int verbose, done, time_bounded, output_all_data, seek_absolute;
 extern unsigned int n_devs;
 extern unsigned long n_traces;
 extern struct list_head all_devs, all_procs, retries, rmhd;
 extern struct avgs_info all_avgs;
 extern __u64 last_q, next_retry_check;
 extern struct region_info all_regions;
-extern struct list_head free_ios;
+extern struct list_head free_ios, free_bilinks;
 extern __u64 iostat_interval, iostat_last_stamp;
 extern time_t genesis, last_vtrace;
 extern double t_astart, t_aend;
@@ -221,9 +222,10 @@ extern struct list_head cios;
 /* args.c */
 void handle_args(int argc, char *argv[]);
 
-/* dev_map.c */
+/* devmap.c */
 int dev_map_read(char *fname);
 struct devmap *dev_map_find(__u32 device);
+void dev_map_exit(void);
 
 /* devs.c */
 #if defined(DEBUG)
@@ -240,6 +242,7 @@ struct io *dip_find_sec(struct d_info *dip, enum iop_type type, __u64 sec);
 void dip_foreach_out(void (*func)(struct d_info *, void *), void *arg);
 void dip_plug(__u32 dev, double cur_time);
 void dip_unplug(__u32 dev, double cur_time, int is_timer);
+void dip_exit(void);
 
 /* dip_rb.c */
 int rb_insert(struct rb_root *root, struct io *iop);
@@ -268,6 +271,8 @@ void latency_q2c(struct d_info *dip, __u64 tstamp, __u64 latency);
 int in_devices(struct blk_io_trace *t);
 void add_file(struct file_info **fipp, FILE *fp, char *oname);
 void clean_files(struct file_info **fipp);
+void add_buf(void *buf);
+void clean_bufs(void);
 void dbg_ping(void);
 
 /* mmap.c */
@@ -285,9 +290,17 @@ void add_process(__u32 pid, char *name);
 struct p_info *find_process(__u32 pid, char *name);
 void pip_update_q(struct io *iop);
 void pip_foreach_out(void (*f)(struct p_info *, void *), void *arg);
+void pip_exit(void);
+
+/* bno_dump.c */
+void *bno_dump_init(__u32 device);
+void bno_dump_exit(void *param);
+void bno_dump_add(void *handle, struct io *iop);
+void bno_dump_clean(void);
 
 /* seek.c */
 void *seeki_init(__u32 device);
+void seeki_exit(void *param);
 void seek_clean(void);
 void seeki_add(void *handle, struct io *iop);
 double seeki_mean(void *handle);
diff --git a/btt/inlines.h b/btt/inlines.h
index 38ac5ef..25e5b21 100644
--- a/btt/inlines.h
+++ b/btt/inlines.h
@@ -19,46 +19,58 @@
  *
  */
 
-static inline struct range_info *new_cur(__u64 time)
+static inline void region_init(struct region_info *reg)
 {
-	struct range_info *cur = malloc(sizeof(struct range_info));
-
-	INIT_LIST_HEAD(&cur->head);
-	cur->start = time;
-	return cur;
+	INIT_LIST_HEAD(&reg->qranges);
+	INIT_LIST_HEAD(&reg->cranges);
 }
 
-static inline void update_range(struct list_head *head_p,
-				struct range_info **cur_p, __u64 time)
+static inline void __region_exit(struct list_head *range_head)
 {
-	if (*cur_p == NULL)
-		*cur_p = new_cur(time);
-	else {
-		__u64 my_delta = (time > (*cur_p)->end) ? time - (*cur_p)->end : 1;
-		if (BIT_TIME(my_delta) >= range_delta) {
-			list_add_tail(&(*cur_p)->head, head_p);
-			*cur_p = new_cur(time);
-		}
+	struct list_head *p, *q;
+	struct range_info *rip;
+
+	list_for_each_safe(p, q, range_head) {
+		rip = list_entry(p, struct range_info, head);
+		free(rip);
 	}
+}
 
-	(*cur_p)->end = time;
+static inline void region_exit(struct region_info *reg)
+{
+	__region_exit(&reg->qranges);
+	__region_exit(&reg->cranges);
 }
 
-static inline void init_region(struct region_info *reg)
+static inline void update_range(struct list_head *head_p, __u64 time)
 {
-	INIT_LIST_HEAD(&reg->qranges);
-	INIT_LIST_HEAD(&reg->cranges);
-	reg->qr_cur = reg->cr_cur = NULL;
+	struct range_info *rip;
+
+	if (!list_empty(head_p)) {
+		rip = list_entry(head_p->prev, struct range_info, head);
+
+		if (time < rip->end)
+			return;
+
+		if (BIT_TIME(time - rip->end) < range_delta) {
+			rip->end = time;
+			return;
+		}
+	}
+
+	rip = malloc(sizeof(*rip));
+	rip->start = rip->end = time;
+	list_add_tail(&rip->head, head_p);
 }
 
 static inline void update_qregion(struct region_info *reg, __u64 time)
 {
-	update_range(&reg->qranges, &reg->qr_cur, time);
+	update_range(&reg->qranges, time);
 }
 
 static inline void update_cregion(struct region_info *reg, __u64 time)
 {
-	update_range(&reg->cranges, &reg->cr_cur, time);
+	update_range(&reg->cranges, time);
 }
 
 static inline void avg_update(struct avg_info *ap, __u64 t)
@@ -115,7 +127,7 @@ static inline struct io *io_alloc(void)
 	struct io *iop;
 
 	if (!list_empty(&free_ios)) {
-		iop = list_entry(free_ios.next, struct io, f_head);
+		iop = list_entry(free_ios.prev, struct io, f_head);
 		LIST_DEL(&iop->f_head);
 
 #		if defined(COUNT_IOS)
@@ -161,6 +173,17 @@ static inline void io_free(struct io *iop)
 	list_add_tail(&iop->f_head, &free_ios);
 }
 
+static inline void io_free_all(void)
+{
+	struct io *iop;
+	struct list_head *p, *q;
+
+	list_for_each_safe(p, q, &free_ios) {
+		iop = list_entry(p, struct io, f_head);
+		free(iop);
+	}
+}
+
 static inline int io_setup(struct io *iop, enum iop_type type)
 {
 	iop->type = type;
@@ -282,12 +305,6 @@ static inline struct rb_root *__get_root(struct d_info *dip, enum iop_type type)
 	return &roots[type];
 }
 
-static inline void *dip_rb_mkhds(void)
-{
-	size_t len = N_IOP_TYPES * sizeof(struct rb_root);
-	return memset(malloc(len), 0, len);
-}
-
 static inline int dip_rb_ins(struct d_info *dip, struct io *iop)
 {
 	return rb_insert(__get_root(dip, iop->type), iop);
@@ -389,12 +406,31 @@ static inline int type2c(enum iop_type type)
 
 static inline void bilink_free(struct bilink *blp)
 {
-	free(blp);
+	list_add_tail(&blp->bilink_free_head, &free_bilinks);
+}
+
+static inline void bilink_free_all(void)
+{
+	struct bilink *blp;
+	struct list_head *p, *q;
+
+	list_for_each_safe(p, q, &free_bilinks) {
+		blp = list_entry(p, struct bilink, bilink_free_head);
+		free(blp);
+	}
 }
 
 static inline struct bilink *bilink_alloc(struct io *diop, struct io *uiop)
 {
-	struct bilink *blp = malloc(sizeof(*blp));
+	struct bilink *blp;
+
+	if (!list_empty(&free_bilinks)) {
+		blp = list_entry(free_bilinks.prev, struct bilink, 
+							bilink_free_head);
+		LIST_DEL(&blp->bilink_free_head);
+	}
+	else
+		blp = malloc(sizeof(*blp));
 
 	blp->diop = diop;
 	blp->uiop = uiop;
diff --git a/btt/misc.c b/btt/misc.c
index 022cef5..24ade81 100644
--- a/btt/misc.c
+++ b/btt/misc.c
@@ -53,15 +53,12 @@ int in_devices(struct blk_io_trace *t)
 
 void add_file(struct file_info **fipp, FILE *fp, char *oname)
 {
-	struct file_info *fip;
-	
-	fip = malloc(sizeof(struct file_info) + strlen(oname) + 1);
+	struct file_info *fip = malloc(sizeof(*fip));
 
+	fip->ofp = fp;
+	fip->oname = oname;
 	fip->next = *fipp;
 	*fipp = fip;
-
-	fip->ofp = fp;
-	strcpy(fip->oname, oname);
 }
 
 void clean_files(struct file_info **fipp)
@@ -75,8 +72,34 @@ void clean_files(struct file_info **fipp)
 		fclose(fip->ofp);
 		if (!stat(fip->oname, &buf) && (buf.st_size == 0))
 			unlink(fip->oname);
+
+		free(fip->oname);
 		free(fip);
 	}
 }
 
+struct buf_info {
+	struct buf_info *next;
+	void *buf;
+} *all_bufs;
+void add_buf(void *buf)
+{
+	struct buf_info *bip = malloc(sizeof(*bip));
+
+	bip->buf = buf;
+	bip->next = all_bufs;
+	all_bufs = bip;
+}
+
+void clean_bufs(void)
+{
+	struct buf_info *bip;
+
+	while ((bip = all_bufs) != NULL) {
+		all_bufs = bip->next;
+		free(bip->buf);
+		free(bip);
+	}
+}
+	
 void dbg_ping(void) {}
diff --git a/btt/output.c b/btt/output.c
index 1278434..18d1d53 100644
--- a/btt/output.c
+++ b/btt/output.c
@@ -321,6 +321,7 @@ void output_seek_mode_info(FILE *ofp, struct o_seek_info *sip)
 		free(p);
 	}
 }
+
 void add_seek_mode_info(struct o_seek_info *sip, struct mode *mp)
 {
 	int i;
@@ -342,6 +343,8 @@ void add_seek_mode_info(struct o_seek_info *sip, struct mode *mp)
 			sip->head = new;
 			new->mode = lp[i];
 			new->nseeks = mp->most_seeks;
+
+			add_buf(new);
 		}
 	}
 }
@@ -373,6 +376,7 @@ void __output_dip_seek_info(struct d_info *dip, void *arg)
 		seek_info.mean += (nseeks * mean);
 		seek_info.median += (nseeks * median);
 		add_seek_mode_info(&seek_info, &m);
+		free(m.modes);
 	}
 }
 
@@ -466,8 +470,8 @@ void __dip_output_plug_all(FILE *ofp, struct plug_info *p)
 {
 	fprintf(ofp, "---------- | ---------- ----------  | ----------------\n");
 	fprintf(ofp, "%10s | %10s %10s  | %s\n", 
-	        "DEV", "# Plugs", "# Timer Us", "% Time Q Plugged");
-	fprintf(ofp, "%10s | %10ld(%10ld) | %13.9lf%%\n", "OVERALL",
+	        "Overall", "# Plugs", "# Timer Us", "% Time Q Plugged");
+	fprintf(ofp, "%10s | %10ld(%10ld) | %13.9lf%%\n", "Average",
 	        p->n_plugs / n_plugs, p->n_timer_unplugs / n_plugs, 
 		p->t_percent / n_plugs);
 
@@ -598,11 +602,6 @@ void __output_ranges(FILE *ofp, struct list_head *head_p, float base)
 int output_regions(FILE *ofp, char *header, struct region_info *reg, 
 			  float base)
 {
-	if (reg->qr_cur != NULL)
-		list_add_tail(&reg->qr_cur->head, &reg->qranges);
-	if (reg->cr_cur != NULL)
-		list_add_tail(&reg->cr_cur->head, &reg->cranges);
-
 	if (list_len(&reg->qranges) == 0 && list_len(&reg->cranges) == 0)
 		return 0;
 
diff --git a/btt/proc.c b/btt/proc.c
index 8e6c5ff..e24948f 100644
--- a/btt/proc.c
+++ b/btt/proc.c
@@ -33,6 +33,24 @@ struct pn_info {
 
 struct rb_root root_pid, root_name;
 
+static void __destroy(struct rb_node *n, int free_name, int free_pip)
+{
+	if (n) {
+		struct pn_info *pnp = rb_entry(n, struct pn_info, rb_node);
+
+		__destroy(n->rb_left, free_name, free_pip);
+		__destroy(n->rb_right, free_name, free_pip);
+
+		if (free_name) free(pnp->u.name);
+		if (free_pip) {
+			free(pnp->pip->name);
+			region_exit(&pnp->pip->regions);
+			free(pnp->pip);
+		}
+		free(pnp);
+	}
+}
+
 struct p_info * __find_process_pid(__u32 pid)
 {
 	struct pn_info *this;
@@ -151,13 +169,11 @@ void add_process(__u32 pid, char *name)
 	struct p_info *pip = find_process(pid, name);
 
 	if (pip == NULL) {
-		size_t len = sizeof(struct p_info) + strlen(name) + 1;
-
-		pip = memset(malloc(len), 0, len);
+		pip = memset(malloc(sizeof(*pip)), 0, sizeof(*pip));
 		pip->pid = pid;
-		init_region(&pip->regions);
+		region_init(&pip->regions);
 		pip->last_q = (__u64)-1;
-		strcpy(pip->name, name);
+		pip->name = strdup(name);
 
 		insert(pip);
 	}
@@ -204,3 +220,9 @@ void pip_foreach_out(void (*f)(struct p_info *, void *), void *arg)
 		}
 	}
 }
+
+void pip_exit(void)
+{
+	__destroy(root_pid.rb_node, 0, 0);
+	__destroy(root_name.rb_node, 1, 1);
+}
diff --git a/btt/seek.c b/btt/seek.c
index f5f3851..8738698 100644
--- a/btt/seek.c
+++ b/btt/seek.c
@@ -29,7 +29,7 @@ struct seek_bkt {
 };
 
 struct seeki {
-	FILE *rfp, *wfp;
+	FILE *rfp, *wfp, *cfp;
 	struct rb_root root;
 	long long tot_seeks;
 	double total_sectors;
@@ -84,6 +84,17 @@ static void __insert(struct rb_root *root, long long sectors)
 	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);
+	}
+}
+
 void seek_clean(void)
 {
 	clean_files(&seek_files);
@@ -94,14 +105,19 @@ long long seek_dist(struct seeki *sip, struct io *iop)
 	long long dist;
 	long long start = BIT_START(iop), end = BIT_END(iop);
 
-	/* 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)
+	if (seek_absolute)
 		dist = start - sip->last_end;
-	else
-		dist = start - sip->last_start;
+	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;
@@ -114,6 +130,7 @@ void *seeki_init(__u32 device)
 
 	sip->rfp = seek_open(device, 'r');
 	sip->wfp = seek_open(device, 'w');
+	sip->cfp = seek_open(device, 'c');
 	sip->tot_seeks = 0;
 	sip->total_sectors = 0.0;
 	sip->last_start = sip->last_end = 0;
@@ -122,14 +139,29 @@ void *seeki_init(__u32 device)
 	return sip;
 }
 
+void seeki_exit(void *param)
+{
+	struct seeki *sip = param;
+
+	/*
+	 * 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\n", BIT_TIME(iop->t.time), dist);
+		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++;
diff --git a/btt/trace_issue.c b/btt/trace_issue.c
index b19ddd6..d2b0832 100644
--- a/btt/trace_issue.c
+++ b/btt/trace_issue.c
@@ -78,6 +78,7 @@ void trace_issue(struct io *d_iop)
 {
 	if (io_setup(d_iop, IOP_D)) {
 		seeki_add(d_iop->dip->seek_handle, d_iop);
+		bno_dump_add(d_iop->dip->bno_dump_handle, d_iop);
 		iostat_issue(d_iop);
 		d_iop->dip->n_ds++;
 		if (!remapper_dev(d_iop->t.device))