From 93290e83d330653f090b3780e59ea5d2bf1e3bca Mon Sep 17 00:00:00 2001
From: Jonathan Herman <hermanjl@cs.unc.edu>
Date: Fri, 5 Oct 2012 17:14:37 -0400
Subject: Rewrote set_cpu_to_rts() and iterate() for increased performance and
 accuracy.

Container job information functions, like displaying the job in the server's boxes
or the currently running task in pop-ups, rewritten to take advantage of these
changes.
---
 rt-plot-container.c | 114 +++++++++++++++++++++++----------
 rt-plot-vcpu.c      |  28 ++++-----
 rt-plot.c           | 178 +++++++++++++++++++++-------------------------------
 rt-plot.h           |   2 +-
 trace-dialog.c      |   2 -
 trace-graph.c       |  38 +++++------
 6 files changed, 188 insertions(+), 174 deletions(-)

diff --git a/rt-plot-container.c b/rt-plot-container.c
index 94f78ee..6c647fc 100644
--- a/rt-plot-container.c
+++ b/rt-plot-container.c
@@ -22,6 +22,80 @@ int rt_plot_get_containers(struct graph_info *ginfo, gint **conts,
 	return count;
 }
 
+struct record *
+rt_read_next_data(struct graph_info *ginfo, struct tracecmd_input *handle, int *rec_cpu)
+{
+	unsigned long long ts;
+	struct record *record;
+	int next;
+	int cpu;
+
+	if (rec_cpu)
+		*rec_cpu = -1;
+
+	next = -1;
+	ts = 0;
+
+	for (cpu = 0; cpu < ginfo->cpus; cpu++) {
+		record = tracecmd_peek_data(handle, cpu);
+		if (record && (!ts || get_rts(ginfo, record) < ts)) {
+			ts = get_rts(ginfo, record);
+			next = cpu;
+		}
+	}
+
+	if (next >= 0) {
+		if (rec_cpu)
+			*rec_cpu = next;
+		return tracecmd_read_data(handle, next);
+	}
+
+	return NULL;
+}
+
+struct server_iter_args {
+	unsigned long long goal;
+	int match_sid;
+
+	int *out_job;
+	int *out_tid;
+	int *out_tjob;
+	int is_running;
+};
+
+static int server_iterator(struct graph_info *ginfo, struct record *record, void *data)
+{
+	int sid, job, tid, tjob, match;
+	struct server_iter_args *args = data;
+	unsigned long long when, time = get_rts(ginfo, record);
+
+	if (time > args->goal + max_rt_search(ginfo))
+		return 0;
+	if (time < args->goal)
+		return 1;
+
+#define ARGS ginfo, record, &sid, &job, &tid, &tjob, &when
+	match = rt_graph_check_server_switch_away(ARGS);
+	if (match && sid == args->match_sid) {
+		(*args->out_tid)  = tid;
+		(*args->out_tjob) = tjob;
+		(*args->out_job)  = job;
+		args->is_running = 1;
+		return 0;
+
+	}
+
+	match = rt_graph_check_server_switch_to(ARGS);
+	if (match && sid == args->match_sid) {
+		/* We must not have been running anything */
+		(*args->out_job) = job;
+		return 0;
+	}
+
+#undef  ARGS
+	return 1;
+}
+
 int get_server_info(struct graph_info *ginfo, struct rt_plot_common *rt,
 		    int match_sid, unsigned long long time,
 		    unsigned long long *out_release,
@@ -29,47 +103,19 @@ int get_server_info(struct graph_info *ginfo, struct rt_plot_common *rt,
 		    int *out_job, int *out_tid, int *out_tjob,
 		    struct record **out_record)
 {
-	struct record *record;
-	int sid, job, tid, tjob, match, next_cpu, is_running = 0;
-	unsigned long long when, max_ts;
+	struct server_iter_args args = {time, match_sid,
+					out_job, out_tid, out_tjob, 0};
 
 	*out_record = find_rt_record(ginfo, rt, time);
-	if (!(*out_record))
+	if (!*out_record)
 		return 0;
 
 	*out_release = *out_deadline = *out_job = *out_tid = 0;
 
-	/* Get current job info for server task */
-	get_previous_release(ginfo, rt, sid, time,
-			     out_job, out_release, out_deadline);
-
-	/* Need to reset back to current location */
-	record = find_rt_record(ginfo, rt, time);
-	if (!record)
-		goto out;
-
-	/* TODO: read backwards too */
-	max_ts = time + max_rt_search(ginfo);
-	do {
-		if (get_rts(ginfo, record) > max_ts)
-			break;
-
-		match = rt_graph_check_server_switch_away(ginfo, record,
-							  &sid, &job, &tid, &tjob,
-							  &when);
-		if (match && sid == match_sid) {
-			*out_tid = tid;
-			*out_tjob = tjob;
-			is_running = 1;
-			break;
-		}
-		free_record(record);
-	} while ((record = tracecmd_read_next_data(ginfo->handle, &next_cpu)));
+	set_cpus_to_rts(ginfo, time);
+	iterate(ginfo, 0, server_iterator, &args);
 
-	if (record && record != *out_record)
-		free_record(record);
- out:
-	return is_running;
+	return args.is_running;
 }
 
 void rt_plot_container(struct graph_info *ginfo, int cid)
diff --git a/rt-plot-vcpu.c b/rt-plot-vcpu.c
index 8f850b9..e39ae19 100644
--- a/rt-plot-vcpu.c
+++ b/rt-plot-vcpu.c
@@ -13,12 +13,12 @@
 #define dprintf(l, x...)	do { if (0) printf(x); } while (0)
 #endif
 
-static void update_tid(struct vcpu_info *info, int tid)
+static void update_label(struct vcpu_info *info, int tid, int tjob)
 {
 	info->fresh = FALSE;
 	if (tid != info->run_tid) {
 		info->run_tid = tid;
-		snprintf(info->label, LLABEL, "%d", tid);
+		snprintf(info->label, LLABEL, "%d:%d", tid, tjob);
 	}
 }
 
@@ -33,7 +33,7 @@ try_server_switch_away(struct graph_info *ginfo, struct vcpu_info *vcpu_info,
 						  &sid, &job,
 						  &tid, &tjob, &ts);
 	if (match && sid == vcpu_info->sid) {
-		update_tid(vcpu_info, tid);
+		update_label(vcpu_info, tid, tjob);
 
 		if (vcpu_info->run_time && vcpu_info->run_time < ts) {
 			info->box = TRUE;
@@ -66,7 +66,7 @@ static int try_server_switch_to(struct graph_info *ginfo, struct vcpu_info *vcpu
 	match = rt_graph_check_server_switch_to(ginfo, record,
 						&sid, &job, &tid, &tjob, &ts);
 	if (match && sid == vcpu_info->sid) {
-		update_tid(vcpu_info, tid);
+		update_label(vcpu_info, tid, tjob);
 		vcpu_info->run_time = ts;
 		vcpu_info->run_cpu = record->cpu;
 		vcpu_info->run_tid = tid;
@@ -151,7 +151,7 @@ static void do_plot_end(struct graph_info *ginfo, struct vcpu_info *vcpu_info,
 					     &release, &deadline,
 					     &job, &tid, &tjob, &record);
 		if (is_running) {
-			update_tid(vcpu_info, tid);
+			update_label(vcpu_info, tid, tjob);
 			info->box = TRUE;
 			info->bcolor = hash_pid(vcpu_info->run_tid);
 			info->bfill = is_task_running(ginfo, ginfo->view_end_time, tid);
@@ -251,7 +251,7 @@ void rt_vcpu_plot_start(struct graph_info *ginfo, struct graph_plot *plot,
 	vcpu_info->fresh = TRUE;
 	vcpu_info->running = FALSE;
 	vcpu_info->last_job = -1;
-	update_tid(vcpu_info, 0);
+	update_label(vcpu_info, 0, 0);
 }
 
 /**
@@ -276,15 +276,15 @@ int rt_vcpu_plot_record_matches(struct rt_plot_common *rt,
 	int dint, sid, match;
 	unsigned long long dull;
 
-#define ARG ginfo, record, &sid
-	match = rt_graph_check_server_switch_to(ARG, &dint, &dint, &dint, &dull)   ||
-		rt_graph_check_server_switch_away(ARG, &dint, &dint, &dint, &dull);
-		/* rt_graph_check_server_completion(ARG, &dint, &dull)  || */
-		/* rt_graph_check_server_release(ARG, &dint, &dull, &dull); */
-		/* rt_graph_check_server_block(ARG, &dull)		    || */
-		/* rt_graph_check_server_resume(ARG, &dull); */
+#define ARG ginfo, record, &sid, &dint
+	match = rt_graph_check_server_switch_to(ARG, &dint, &dint, &dull)   ||
+		rt_graph_check_server_switch_away(ARG,&dint, &dint, &dull);
+		rt_graph_check_server_completion(ARG, &dull)  ||
+		rt_graph_check_server_release(ARG, &dull, &dull);
+		rt_graph_check_server_block(ARG, &dull)		    ||
+		rt_graph_check_server_resume(ARG, &dull);
 #undef ARG
-	return (sid == vcpu_info->sid);
+	return (match && sid == vcpu_info->sid);
 }
 
 /**
diff --git a/rt-plot.c b/rt-plot.c
index a86b7df..e47343a 100644
--- a/rt-plot.c
+++ b/rt-plot.c
@@ -28,15 +28,15 @@ void insert_record(struct graph_info *ginfo, struct record_list *list,
 
 	while (pos->next) {
 		unsigned long long next_rts = get_rts(ginfo, pos->next->record);
-		if (( reverse && !next_rts > get_rts(ginfo, record)) ||
-		    (!reverse &&  next_rts < get_rts(ginfo, record))){
+		if (( reverse &&  next_rts < get_rts(ginfo, record)) ||
+		    (!reverse &&  next_rts > get_rts(ginfo, record))){
 			break;
 		}
 		pos = pos->next;
 	}
 
 	node->next = pos->next;
-	pos->next = node;	
+	pos->next = node;
 }
 
 
@@ -53,7 +53,7 @@ int pop_record(struct graph_info *ginfo, struct record_list *list,
 	list->next = list->next->next;
 	(*node)->next = 0;
 
-	return 1;	
+	return 1;
 }
 
 
@@ -91,7 +91,7 @@ prev_release_iterator(struct graph_info *ginfo, struct record *rec, void *data)
 		*(args->out_job) = job;
 		*(args->out_release) = release;
 		*(args->out_deadline) = deadline;
-		
+
 		/* Cache to minimize work later */
 		args->common->last_job.no = job;
 		args->common->last_job.release = release;
@@ -122,14 +122,14 @@ prev_display_iterator(struct graph_info *ginfo, struct record *record, void *dat
 	if (get_rts(ginfo, record) < args->min_ts) {
 		return 0;
 	}
-		
+
 	eid = pevent_data_type(ginfo->pevent, record);
 	ignored = (eid == ginfo->event_sched_switch_id);
 
 	if (!ignored) {
 		ignored = args->common->is_drawn(ginfo, eid);
 	}
-	
+
 	if (!ignored && args->common->record_matches(args->common, ginfo, record)) {
 		args->result = record;
 		++record->ref_count;
@@ -147,8 +147,6 @@ static struct record*
 find_prev_display_record(struct graph_info *ginfo, struct rt_plot_common *rt_info,
 		 unsigned long long time, unsigned long long range)
 {
-	int eid, ignored, match, cpu;
-	struct record *prev, *next, *res = NULL;
 	struct prev_display_args args = {rt_info, NULL, 0};
 
 	if (range) {
@@ -342,98 +340,64 @@ rt_plot_match_time(struct graph_info *ginfo, struct graph_plot *plot,
 	return ret;
 }
 
-
-
 /**
- * next_rts - find a real-time timestamp AROUND an FTRACE time
- * @ginfo: Current state of the graph
- * @cpu: CPU to search
- * @ft_target: FTRACE time to seek towards
- *
- * Returns the RT time of a record CLOSELY BEFORE @ft_time.
- */
-unsigned long long
-next_rts(struct graph_info *ginfo, int cpu, unsigned long long ft_target)
-{
-	struct record *record;
-	unsigned long long ts = 0ULL;
-	tracecmd_set_cpu_to_timestamp(ginfo->handle, cpu, ft_target);
-	record = tracecmd_read_data(ginfo->handle, cpu);
-	if (record) {
-		ts = get_rts(ginfo, record);
-		free_record(record);
-		return ts;
-	} else
-		return 0;
-}
-
-/**
- * set_cpu_to_rts - seek CPU to a time closely preceding a real-time timestamp
- * @ginfo: Current state o the graph
+ * set_cpu_to_rts - seek CPU to a time closely preceding a real-time timestamp.
  * @cpu: The CPU to seek
  * @rt_target: RT time to seek towards
  *
  * This seeks to a real-time timestamp, not the default ftrace timestamps.
- * The @cpu seek location will be placed before the given time, but will
- * not necessarily be placed _right_ before the time.
+ * The @cpu seek location will be placed on the last record whose timestamp
+ * is less than @rt_target.
  */
-unsigned long long
-set_cpu_to_rts(struct graph_info *ginfo, unsigned long long rt_target, int cpu)
+long long correction = 0;
+unsigned long long set_cpu_to_rts(struct graph_info *ginfo,
+		    unsigned long long rt_target, int cpu)
 {
-	struct record *record;
-	unsigned long long last_rts, rts, seek_time, last_seek;
-	long long diff;
-
-	rts = next_rts(ginfo, cpu, rt_target);
-	diff = rt_target - rts;
-
-	/* "Guess" a new target based on difference */
-	seek_time = rt_target + diff;
-	rts = next_rts(ginfo, cpu, seek_time);
-	diff = rt_target - rts;
-
-	/* Zero in in 1.5x the difference increments */
-	if (rts && diff > 0) {
-		/*   rts      rt_target  | real-time time
-		 *   seek        ?       | trace-cmd time
-		 * ---|---->>----|--------
-		 */
-		do {
-			last_seek = seek_time;
-			last_rts = rts;
-			seek_time = seek_time + 1.5 * (rt_target - rts);
-			rts = next_rts(ginfo, cpu, seek_time);
-		} while (rts < rt_target && last_rts != rts);
-		tracecmd_set_cpu_to_timestamp(ginfo->handle, cpu, last_seek);
-		seek_time = last_seek;
-	} else if (rts && diff < 0) {
-		/* rt_target    rts      | real-time time
-		 *    ?         seek     | trace-cmd time
-		 * ---|----<<----|--------
-		 */
-		do {
-			seek_time = seek_time - 1.5 * (rts - rt_target);
-			last_rts = rts;
-			rts = next_rts(ginfo, cpu, seek_time);
-		} while (rts > rt_target && rts != last_rts);
+	struct record *record, *last_record;
+	unsigned long long rts, seek_time;
+	long long next_diff;
+
+	seek_time = rt_target + correction;
+	tracecmd_set_cpu_to_timestamp(ginfo->handle, cpu, seek_time);
+
+	last_record = tracecmd_read_data(ginfo->handle, cpu);
+	rts = get_rts(ginfo, last_record);
+	if (rts < rt_target) {
+		while ((record = tracecmd_read_data(ginfo->handle, cpu))) {
+			if (get_rts(ginfo, record) >= rt_target) {
+				free_record(record);
+					break;
+			}
+			free_record(last_record);
+			last_record = record;
+		}
+	} else if (rts > rt_target) {
+		while ((record = tracecmd_read_prev(ginfo->handle, last_record))) {
+			if (get_rts(ginfo, record) <= rt_target) {
+				free_record(last_record);
+				last_record = record;
+				break;
+			}
+			free_record(last_record);
+			last_record = record;
+		}
 	}
 
-	/* Get to first record at or after time */
-	while ((record = tracecmd_read_data(ginfo->handle, cpu))) {
-		if (get_rts(ginfo, record) >= rt_target)
-			break;
-		free_record(record);
+	if (last_record) {
+		next_diff = (last_record->ts - rt_target);
+		if (correction)
+			correction = correction *3/ 4 + (next_diff) / 4;
+		else
+			correction = next_diff;
+		tracecmd_set_cursor(ginfo->handle, cpu, last_record->offset);
+		free_record(last_record);
 	}
-	if (record) {
-		tracecmd_set_cursor(ginfo->handle, cpu, record->offset);
-		free_record(record);
-	} else
-		tracecmd_set_cpu_to_timestamp(ginfo->handle, cpu, seek_time);
+
 	return rts;
 }
 
 /**
- * set_cpus_to_time - seek all cpus to real-time @rt_target
+ * set_cpus_to_time - seek all cpus to real-time @rt_target.
  */
 unsigned long long set_cpus_to_rts(struct graph_info *ginfo, unsigned long long rt_target)
 {
@@ -491,6 +455,9 @@ int is_task_running(struct graph_info *ginfo,
 	return running;
 }
 
+/**
+ * iterate - pass records in real-time timestamp order to @cb.
+ */
 void iterate(struct graph_info *ginfo, int reverse, iterate_cb cb, void *data)
 {
 	int proceed, cpu;
@@ -502,47 +469,48 @@ void iterate(struct graph_info *ginfo, int reverse, iterate_cb cb, void *data)
 	memset(nodes, 0, sizeof(*nodes) * ginfo->cpus);
 	memset(&list, 0, sizeof(list));
 
-	/* Maintains a list of the next record on each cpu, sorted by
-	 * timestamp. Start with the first record on each cpu.
-	 */
+	/* Start with the first record on each CPU */
 	for (cpu = 0; cpu < ginfo->cpus; cpu++) {
 		next = tracecmd_peek_data(ginfo->handle, cpu);
 		if (next) {
 			if (reverse) {
+				/* Reading backwards is clumsy...*/
 				prev = next;
-				next = tracecmd_read_prev(ginfo->handle, prev);
-				if (prev != next && prev->data) {
-					free_record(prev);
-				}
+			 	next = tracecmd_read_prev(ginfo->handle, prev);
+			 	if (prev != next && prev->data)
+			 		free_record(prev);
+			} else {
+				next = tracecmd_read_data(ginfo->handle, cpu);
 			}
 			insert_record(ginfo, &list, next, &nodes[cpu], reverse);
 		}
 	}
 
-	/* Read sequentially from all cpus */
+	/* Read record with the next timestamp until the callback is finished
+	 * consuming data
+	 */
 	while (pop_record(ginfo, &list, &node)) {
 		next = node->record;
 
+		/* Pass records into callback */
 		proceed = cb(ginfo, next, data);
-
 		if (!proceed) {
 			free_record(next);
 			break;
-		} 
+		}
 
+		/* Replace this record with the next record from the same CPU */
 		prev = next;
-
-		if (!reverse) {
+		if (!reverse)
 			next = tracecmd_read_data(ginfo->handle, next->cpu);
-		} else {
+		else
 			next = tracecmd_read_prev(ginfo->handle, next);
-		}
-
 		free_record(prev);
-
-		insert_record(ginfo, &list, next, node, reverse);
+		if (prev != next)
+			insert_record(ginfo, &list, next, node, reverse);
 	}
 
+	/* Free unused records */
 	while (pop_record(ginfo, &list, &node)) {
 		free_record(node->record);
 	}
@@ -550,7 +518,7 @@ void iterate(struct graph_info *ginfo, int reverse, iterate_cb cb, void *data)
 
 
 /**
- * Find the information for the last release of @match_tid on @cpu before @time.
+ * get_previous_release - return stats for the latest release of @match_tid
  *
  * This method will NOT re-seek the CPUs near time. The caller must have placed
  * the CPUs near the the CPUs themselves.
diff --git a/rt-plot.h b/rt-plot.h
index a1cf98e..924ae72 100644
--- a/rt-plot.h
+++ b/rt-plot.h
@@ -68,7 +68,7 @@ find_rt_display_record(struct graph_info *ginfo,
 	return __find_rt_record(ginfo, rt, time, 1, 0);
 }
 
-unsigned long long next_rts(struct graph_info *ginfo, int cpu,
+long long next_rts(struct graph_info *ginfo, int cpu,
 			    unsigned long long ft_target);
 unsigned long long set_cpu_to_rts(struct graph_info *ginfo,
 		    unsigned long long rt_target, int cpu);
diff --git a/trace-dialog.c b/trace-dialog.c
index 4e1d6e2..00ab269 100644
--- a/trace-dialog.c
+++ b/trace-dialog.c
@@ -183,7 +183,6 @@ void warning(const char *fmt, ...)
 {
 	GString *str;
 	va_list ap;
-	int err;
 
 	if (alt_warning) {
 		va_start(ap, fmt);
@@ -199,7 +198,6 @@ void warning(const char *fmt, ...)
 		return;
 	}
 
-	err = errno;
 	errno = 0;
 
 	str = g_string_new("");
diff --git a/trace-graph.c b/trace-graph.c
index 69f5069..0aa8137 100644
--- a/trace-graph.c
+++ b/trace-graph.c
@@ -1852,14 +1852,16 @@ static void draw_plot(struct graph_info *ginfo, struct graph_plot *plot,
 }
 
 /*
- * TODO: this method needs refactoring and splitting
+ * TODO: this method needs refactoring and splitting.
+ * Containers currently aren't using hashing, which can significantly affect
+ * performance if enough containers are being rendered.
  */
 static void draw_hashed_plots(struct graph_info *ginfo)
 {
 	gint cpu, pid, clean;
 	struct record *record;
-	struct plot_hash *hash;
 	struct plot_list *list;
+	struct plot_hash *hash;
 	unsigned long long max_time, min_time;
 	gdouble start, duration;
 
@@ -1940,19 +1942,19 @@ static void draw_hashed_plots(struct graph_info *ginfo)
 		}
 
 
-		/* hash = trace_graph_plot_find_cpu(ginfo, cpu); */
-		/* if (hash) { */
-		/* 	for (list = hash->plots; list; list = list->next) { */
-		/* 		draw_plot(ginfo, list->plot, record); */
-		/* 	} */
-		/* } */
-		/* pid = pevent_data_pid(ginfo->pevent, record); */
-		/* hash = trace_graph_plot_find_task(ginfo, pid); */
-		/* if (hash) { */
-		/* 	for (list = hash->plots; list; list = list->next) { */
-		/* 		draw_plot(ginfo, list->plot, record); */
-		/* 	} */
-		/* } */
+		hash = trace_graph_plot_find_cpu(ginfo, cpu);
+		if (hash) {
+			for (list = hash->plots; list; list = list->next) {
+				draw_plot(ginfo, list->plot, record);
+			}
+		}
+		pid = pevent_data_pid(ginfo->pevent, record);
+		hash = trace_graph_plot_find_task(ginfo, pid);
+		if (hash) {
+			for (list = hash->plots; list; list = list->next) {
+				draw_plot(ginfo, list->plot, record);
+			}
+		}
 		for (list = ginfo->all_recs; list; list = list->next) {
 			/* TODO: hacky assumption that everything else can be
 			 * reached via previous hashes
@@ -1960,10 +1962,10 @@ static void draw_hashed_plots(struct graph_info *ginfo)
 			 * added with arbitrary numbers, and a pevent_other_id
 			 * which uses id ranges x < . < y to parse cids or lids
 			 */
-			/* if (list->plot->type == PLOT_TYPE_SERVER_TASK || */
-			/*     list->plot->type == PLOT_TYPE_SERVER_CPU) { */
+			if (list->plot->type == PLOT_TYPE_SERVER_TASK ||
+			    list->plot->type == PLOT_TYPE_SERVER_CPU) {
 				draw_plot(ginfo, list->plot, record);
-			/* } */
+			}
 		}
 		free_record(record);
 	}
-- 
cgit v1.2.2