LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Adrian Hunter <adrian.hunter@intel.com>
To: Peter Zijlstra <peterz@infradead.org>,
	Arnaldo Carvalho de Melo <acme@kernel.org>
Cc: linux-kernel@vger.kernel.org, David Ahern <dsahern@gmail.com>,
	Frederic Weisbecker <fweisbec@gmail.com>,
	Jiri Olsa <jolsa@redhat.com>, Namhyung Kim <namhyung@gmail.com>,
	Paul Mackerras <paulus@samba.org>,
	Stephane Eranian <eranian@google.com>,
	Alexander Shishkin <alexander.shishkin@linux.intel.com>,
	Andi Kleen <ak@linux.intel.com>
Subject: [PATCH V6 12/25] perf auxtrace: Add a heap for sorting AUX area tracing queues
Date: Mon, 16 Mar 2015 14:41:34 +0200	[thread overview]
Message-ID: <1426509707-24961-13-git-send-email-adrian.hunter@intel.com> (raw)
In-Reply-To: <1426509707-24961-1-git-send-email-adrian.hunter@intel.com>

In order to process AUX area tracing
data in time order, the queue with data
with the lowest timestamp must be
processed first.  Provide a heap to
keep track of which queue that is.

As with the queues, a decoder does not have
to use the heap, but Intel BTS and Intel PT
will use it.

Signed-off-by: Adrian Hunter <adrian.hunter@intel.com>
---
 tools/perf/util/auxtrace.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++
 tools/perf/util/auxtrace.h | 29 ++++++++++++++++
 2 files changed, 114 insertions(+)

diff --git a/tools/perf/util/auxtrace.c b/tools/perf/util/auxtrace.c
index 7e242b8..225bf7e 100644
--- a/tools/perf/util/auxtrace.c
+++ b/tools/perf/util/auxtrace.c
@@ -351,6 +351,91 @@ void auxtrace_queues__free(struct auxtrace_queues *queues)
 	queues->nr_queues = 0;
 }
 
+static void auxtrace_heapify(struct auxtrace_heap_item *heap_array,
+			     unsigned int pos, unsigned int queue_nr,
+			     u64 ordinal)
+{
+	unsigned int parent;
+
+	while (pos) {
+		parent = (pos - 1) >> 1;
+		if (heap_array[parent].ordinal <= ordinal)
+			break;
+		heap_array[pos] = heap_array[parent];
+		pos = parent;
+	}
+	heap_array[pos].queue_nr = queue_nr;
+	heap_array[pos].ordinal = ordinal;
+}
+
+int auxtrace_heap__add(struct auxtrace_heap *heap, unsigned int queue_nr,
+		       u64 ordinal)
+{
+	struct auxtrace_heap_item *heap_array;
+
+	if (queue_nr >= heap->heap_sz) {
+		unsigned int heap_sz = AUXTRACE_INIT_NR_QUEUES;
+
+		while (heap_sz <= queue_nr)
+			heap_sz <<= 1;
+		heap_array = realloc(heap->heap_array,
+				     heap_sz * sizeof(struct auxtrace_heap_item));
+		if (!heap_array)
+			return -ENOMEM;
+		heap->heap_array = heap_array;
+		heap->heap_sz = heap_sz;
+	}
+
+	auxtrace_heapify(heap->heap_array, heap->heap_cnt++, queue_nr, ordinal);
+
+	return 0;
+}
+
+void auxtrace_heap__free(struct auxtrace_heap *heap)
+{
+	zfree(&heap->heap_array);
+	heap->heap_cnt = 0;
+	heap->heap_sz = 0;
+}
+
+void auxtrace_heap__pop(struct auxtrace_heap *heap)
+{
+	unsigned int pos, last, heap_cnt = heap->heap_cnt;
+	struct auxtrace_heap_item *heap_array;
+
+	if (!heap_cnt)
+		return;
+
+	heap->heap_cnt -= 1;
+
+	heap_array = heap->heap_array;
+
+	pos = 0;
+	while (1) {
+		unsigned int left, right;
+
+		left = (pos << 1) + 1;
+		if (left >= heap_cnt)
+			break;
+		right = left + 1;
+		if (right >= heap_cnt) {
+			heap_array[pos] = heap_array[left];
+			return;
+		}
+		if (heap_array[left].ordinal < heap_array[right].ordinal) {
+			heap_array[pos] = heap_array[left];
+			pos = left;
+		} else {
+			heap_array[pos] = heap_array[right];
+			pos = right;
+		}
+	}
+
+	last = heap_cnt - 1;
+	auxtrace_heapify(heap_array, pos, heap_array[last].queue_nr,
+			 heap_array[last].ordinal);
+}
+
 size_t auxtrace_record__info_priv_size(struct auxtrace_record *itr)
 {
 	if (itr)
diff --git a/tools/perf/util/auxtrace.h b/tools/perf/util/auxtrace.h
index 3a093f7..984ce57 100644
--- a/tools/perf/util/auxtrace.h
+++ b/tools/perf/util/auxtrace.h
@@ -168,6 +168,29 @@ struct auxtrace_queues {
 };
 
 /**
+ * struct auxtrace_heap_item - element of struct auxtrace_heap.
+ * @queue_nr: queue number
+ * @ordinal: value used for sorting (lowest ordinal is top of the heap) expected
+ *           to be a timestamp
+ */
+struct auxtrace_heap_item {
+	unsigned int		queue_nr;
+	u64			ordinal;
+};
+
+/**
+ * struct auxtrace_heap - a heap suitable for sorting AUX area tracing queues.
+ * @heap_array: the heap
+ * @heap_cnt: the number of elements in the heap
+ * @heap_sz: maximum number of elements (grows as needed)
+ */
+struct auxtrace_heap {
+	struct auxtrace_heap_item	*heap_array;
+	unsigned int		heap_cnt;
+	unsigned int		heap_sz;
+};
+
+/**
  * struct auxtrace_mmap - records an mmap of the auxtrace buffer.
  * @base: address of mapped area
  * @userpg: pointer to buffer's perf_event_mmap_page
@@ -277,6 +300,12 @@ void *auxtrace_buffer__get_data(struct auxtrace_buffer *buffer, int fd);
 void auxtrace_buffer__put_data(struct auxtrace_buffer *buffer);
 void auxtrace_buffer__drop_data(struct auxtrace_buffer *buffer);
 void auxtrace_buffer__free(struct auxtrace_buffer *buffer);
+
+int auxtrace_heap__add(struct auxtrace_heap *heap, unsigned int queue_nr,
+		       u64 ordinal);
+void auxtrace_heap__pop(struct auxtrace_heap *heap);
+void auxtrace_heap__free(struct auxtrace_heap *heap);
+
 struct auxtrace_record *auxtrace_record__init(struct perf_evlist *evlist,
 					      int *err);
 
-- 
1.9.1


  parent reply	other threads:[~2015-03-16 12:44 UTC|newest]

Thread overview: 33+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2015-03-16 12:41 [PATCH V6 00/25] perf tools: Introduce an abstraction for AUX Area and Instruction Tracing Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 01/25] perf header: Add AUX area tracing feature Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 02/25] perf evlist: Add initial support for mmapping an AUX area buffer Adrian Hunter
2015-03-24 11:07   ` Jiri Olsa
2015-03-31  9:09     ` Adrian Hunter
2015-03-24 11:07   ` Jiri Olsa
2015-03-16 12:41 ` [PATCH V6 03/25] perf tools: Add user events for AUX area tracing Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 04/25] perf tools: Add support for AUX area recording Adrian Hunter
2015-03-24 11:07   ` Jiri Olsa
2015-03-24 11:07   ` Jiri Olsa
2015-03-16 12:41 ` [PATCH V6 05/25] perf record: Add basic AUX area tracing support Adrian Hunter
2015-03-24 11:07   ` Jiri Olsa
2015-03-16 12:41 ` [PATCH V6 06/25] perf record: Extend -m option for AUX area tracing mmap pages Adrian Hunter
2015-03-24 11:08   ` Jiri Olsa
2015-03-16 12:41 ` [PATCH V6 07/25] perf tools: Add a user event for AUX area tracing errors Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 08/25] perf session: Add hooks to allow transparent decoding of AUX area tracing data Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 09/25] perf session: Add instruction tracing options Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 10/25] perf auxtrace: Add helpers for AUX area tracing errors Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 11/25] perf auxtrace: Add helpers for queuing AUX area tracing data Adrian Hunter
2015-03-16 12:41 ` Adrian Hunter [this message]
2015-03-16 12:41 ` [PATCH V6 13/25] perf auxtrace: Add processing for AUX area tracing events Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 14/25] perf auxtrace: Add a hashtable for caching Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 15/25] perf tools: Add member to struct dso for an instruction cache Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 16/25] perf script: Add Instruction Tracing support Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 17/25] perf script: Always allow fields 'addr' and 'cpu' for auxtrace Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 18/25] perf report: Add Instruction Tracing support Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 19/25] perf inject: Re-pipe AUX area tracing events Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 20/25] perf inject: Add Instruction Tracing support Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 21/25] perf tools: Add AUX area tracing index Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 22/25] perf tools: Hit all build ids when AUX area tracing Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 23/25] perf tools: Add build option NO_AUXTRACE to exclude " Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 24/25] perf auxtrace: Add option to synthesize events for transactions Adrian Hunter
2015-03-16 12:41 ` [PATCH V6 25/25] perf script: Add field option 'flags' to print sample flags Adrian Hunter

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1426509707-24961-13-git-send-email-adrian.hunter@intel.com \
    --to=adrian.hunter@intel.com \
    --cc=acme@kernel.org \
    --cc=ak@linux.intel.com \
    --cc=alexander.shishkin@linux.intel.com \
    --cc=dsahern@gmail.com \
    --cc=eranian@google.com \
    --cc=fweisbec@gmail.com \
    --cc=jolsa@redhat.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=namhyung@gmail.com \
    --cc=paulus@samba.org \
    --cc=peterz@infradead.org \
    --subject='Re: [PATCH V6 12/25] perf auxtrace: Add a heap for sorting AUX area tracing queues' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).