Messages in this thread Patch in this message |  | | From | Alexander Shishkin <> | Subject | [PATCH v0 51/71] perf itrace: Add a heap for sorting Instruction Tracing queues | Date | Wed, 11 Dec 2013 14:37:03 +0200 |
| |
From: Adrian Hunter <adrian.hunter@intel.com>
In order to process Instruction 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.
Signed-off-by: Adrian Hunter <adrian.hunter@intel.com> --- tools/perf/util/itrace.c | 86 ++++++++++++++++++++++++++++++++++++++++++++++++ tools/perf/util/itrace.h | 29 ++++++++++++++++ 2 files changed, 115 insertions(+)
diff --git a/tools/perf/util/itrace.c b/tools/perf/util/itrace.c index f26d6cd..44214bc 100644 --- a/tools/perf/util/itrace.c +++ b/tools/perf/util/itrace.c @@ -344,6 +344,92 @@ void itrace_queues__free(struct itrace_queues *queues) queues->nr_queues = 0; } +static void itrace_heapify(struct itrace_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 itrace_heap__add(struct itrace_heap *heap, unsigned int queue_nr, + u64 ordinal) +{ + struct itrace_heap_item *heap_array; + + if (queue_nr >= heap->heap_sz) { + unsigned int heap_sz = ITRACE_INIT_NR_QUEUES; + + while (heap_sz <= queue_nr) + heap_sz <<= 1; + heap_array = realloc(heap->heap_array, + heap_sz * sizeof(struct itrace_heap_item)); + if (!heap_array) + return -ENOMEM; + heap->heap_array = heap_array; + heap->heap_sz = heap_sz; + } + + itrace_heapify(heap->heap_array, heap->heap_cnt++, queue_nr, ordinal); + + return 0; +} + +void itrace_heap__free(struct itrace_heap *heap) +{ + free(heap->heap_array); + heap->heap_array = NULL; + heap->heap_cnt = 0; + heap->heap_sz = 0; +} + +void itrace_heap__pop(struct itrace_heap *heap) +{ + unsigned int pos, last, heap_cnt = heap->heap_cnt; + struct itrace_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; + itrace_heapify(heap_array, pos, heap_array[last].queue_nr, + heap_array[last].ordinal); +} + size_t itrace_record__info_priv_size(struct itrace_record *itr) { if (itr) diff --git a/tools/perf/util/itrace.h b/tools/perf/util/itrace.h index b4aca53..304d377 100644 --- a/tools/perf/util/itrace.h +++ b/tools/perf/util/itrace.h @@ -150,6 +150,29 @@ struct itrace_queues { }; /** + * struct itrace_heap_item - element of struct itrace_heap. + * @queue_nr: queue number + * @ordinal: value used for sorting (lowest ordinal is top of the heap) expected + * to be a timestamp + */ +struct itrace_heap_item { + unsigned int queue_nr; + u64 ordinal; +}; + +/** + * struct itrace_heap - a heap suitable for sorting Instruction 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 itrace_heap { + struct itrace_heap_item *heap_array; + unsigned int heap_cnt; + unsigned int heap_sz; +}; + +/** * struct itrace_mmap - records an mmap at PERF_EVENT_ITRACE_OFFSET. * @base: address of mapped area * @mask: %0 if @len is not a power of two, otherwise (@len - %1) @@ -266,6 +289,12 @@ struct itrace_buffer *itrace_buffer__next(struct itrace_queue *queue, struct itrace_buffer *buffer); void *itrace_buffer__get_data(struct itrace_buffer *buffer, int fd); void itrace_buffer__put_data(struct itrace_buffer *buffer); + +int itrace_heap__add(struct itrace_heap *heap, unsigned int queue_nr, + u64 ordinal); +void itrace_heap__pop(struct itrace_heap *heap); +void itrace_heap__free(struct itrace_heap *heap); + struct itrace_record *itrace_record__init(int *err); int itrace_record__options(struct itrace_record *itr, -- 1.8.5.1
|  |