From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1030683AbbD1NdX (ORCPT ); Tue, 28 Apr 2015 09:33:23 -0400 Received: from mail.kernel.org ([198.145.29.136]:34235 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1030630AbbD1NdN (ORCPT ); Tue, 28 Apr 2015 09:33:13 -0400 From: Arnaldo Carvalho de Melo To: Ingo Molnar Cc: linux-kernel@vger.kernel.org, Adrian Hunter , David Ahern , Frederic Weisbecker , Jiri Olsa , Namhyung Kim , Peter Zijlstra , Stephane Eranian , Arnaldo Carvalho de Melo Subject: [PATCH 24/64] perf auxtrace: Add a heap for sorting AUX area tracing queues Date: Tue, 28 Apr 2015 10:30:16 -0300 Message-Id: <1430227856-25825-25-git-send-email-acme@kernel.org> X-Mailer: git-send-email 1.9.3 In-Reply-To: <1430227856-25825-1-git-send-email-acme@kernel.org> References: <1430227856-25825-1-git-send-email-acme@kernel.org> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Adrian Hunter 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 Cc: David Ahern Cc: Frederic Weisbecker Cc: Jiri Olsa Cc: Namhyung Kim Cc: Peter Zijlstra Cc: Stephane Eranian Link: http://lkml.kernel.org/r/1428594864-29309-13-git-send-email-adrian.hunter@intel.com Signed-off-by: Arnaldo Carvalho de Melo --- 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 252417ac28e2..e13b1a14c859 100644 --- a/tools/perf/util/auxtrace.c +++ b/tools/perf/util/auxtrace.c @@ -361,6 +361,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 c6b5981384de..c3514f3b7111 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 @@ -297,6 +320,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.3