lkml.org 
[lkml]   [2015]   [Mar]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH V5 12/25] perf itrace: Add a heap for sorting Instruction Tracing queues
    Date
    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.

    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/itrace.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++++
    tools/perf/util/itrace.h | 29 +++++++++++++++++
    2 files changed, 114 insertions(+)

    diff --git a/tools/perf/util/itrace.c b/tools/perf/util/itrace.c
    index 6c9f32c..90913fe 100644
    --- a/tools/perf/util/itrace.c
    +++ b/tools/perf/util/itrace.c
    @@ -349,6 +349,91 @@ 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)
    +{
    + zfree(&heap->heap_array);
    + 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 0403b32..3b9b7fb 100644
    --- a/tools/perf/util/itrace.h
    +++ b/tools/perf/util/itrace.h
    @@ -170,6 +170,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 of the itrace buffer.
    * @base: address of mapped area
    * @userpg: pointer to buffer's perf_event_mmap_page
    @@ -278,6 +301,12 @@ void *itrace_buffer__get_data(struct itrace_buffer *buffer, int fd);
    void itrace_buffer__put_data(struct itrace_buffer *buffer);
    void itrace_buffer__drop_data(struct itrace_buffer *buffer);
    void itrace_buffer__free(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(struct perf_evlist *evlist, int *err);

    int itrace_record__options(struct itrace_record *itr,
    --
    1.9.1


    \
     
     \ /
      Last update: 2015-03-07 22:21    [W:3.907 / U:0.056 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site