From: Adrian Hunter <adrian.hun...@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.hun...@intel.com> Cc: David Ahern <dsah...@gmail.com> Cc: Frederic Weisbecker <fweis...@gmail.com> Cc: Jiri Olsa <jo...@redhat.com> Cc: Namhyung Kim <namhy...@gmail.com> Cc: Peter Zijlstra <pet...@infradead.org> Cc: Stephane Eranian <eran...@google.com> Link: http://lkml.kernel.org/r/1428594864-29309-13-git-send-email-adrian.hun...@intel.com Signed-off-by: Arnaldo Carvalho de Melo <a...@redhat.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 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
