On Thu, 7 Jan 2021 18:15:43 +0200
"Yordan Karadzhov (VMware)" <y.karadz@xxxxxxxxx> wrote:
> We add an infrastructure for recording the data from a particular trace
> event field during data loading. The goal is to avoid the use of the
> expensive "read_event_field" operation in the case when the value of the
> field is needed during the visualization processing (in plugins for
> example).
>
> Signed-off-by: Yordan Karadzhov (VMware) <y.karadz@xxxxxxxxx>
> ---
> src/libkshark.c | 147 ++++++++++++++++++++++++++++++++++++++
> src/libkshark.h | 43 +++++++++++
> tests/libkshark-tests.cpp | 37 ++++++++++
> 3 files changed, 227 insertions(+)
>
> diff --git a/src/libkshark.c b/src/libkshark.c
> index 0e2ce7a..f73e1da 100644
> --- a/src/libkshark.c
> +++ b/src/libkshark.c
> @@ -2110,3 +2110,150 @@ kshark_merge_data_matrices(struct kshark_matrix_data_set *buffers, int n_buffers
> end:
> return merged_data;
> }
> +
> +/** @brief Allocate memory for kshark_data_container. */
> +struct kshark_data_container *kshark_init_data_container()
> +{
> + struct kshark_data_container *container;
> +
> + container = calloc(1, sizeof(*container));
> + if (!container)
> + goto fail;
> +
> + container->data = calloc(KS_CONTAINER_DEFAULT_SIZE,
> + sizeof(*container->data));
> +
> + if (!container->data)
> + goto fail;
> +
> + container->capacity = KS_CONTAINER_DEFAULT_SIZE;
> + container->sorted = false;
> +
> + return container;
> +
> + fail:
> + fprintf(stderr, "Failed to allocate memory for data container.\n");
> + kshark_free_data_container(container);
> + return NULL;
> +}
> +
> +/**
> + * @brief Free the memory allocated for a kshark_data_container
> + * @param container: Intput location for the kshark_data_container object.
"Input"
> + */
> +void kshark_free_data_container(struct kshark_data_container *container)
> +{
> + if (!container)
> + return;
> +
> + for (ssize_t i = 0; i < container->size; ++i)
> + free(container->data[i]);
> +
> + free(container->data);
> + free(container);
> +}
> +
> +/**
> + * @brief Append data field value to a kshark_data_container
> + * @param container: Input location for the kshark_data_container object.
> + * @param entry: The entry that needs addition data field value.
> + * @param field: The value of data field to be added.
> + *
> + * @returns The size of the container after the addition.
> + */
> +ssize_t kshark_data_container_append(struct kshark_data_container *container,
> + struct kshark_entry *entry, int64_t field)
> +{
> + struct kshark_data_field_int64 *data_field;
> +
> + if (container->capacity == container->size) {
> + if (!KS_DOUBLE_SIZE(container->data,
> + container->capacity))
> + return -ENOMEM;
> + }
> +
> + data_field = malloc(sizeof(*data_field));
> + data_field->entry = entry;
> + data_field->field = field;
> + container->data[container->size++] = data_field;
> +
> + return container->size;
> +}
> +
> +static int compare_time_dc(const void* a, const void* b)
> +{
> + const struct kshark_data_field_int64 *field_a, *field_b;
> +
> + field_a = *(const struct kshark_data_field_int64 **) a;
> + field_b = *(const struct kshark_data_field_int64 **) b;
> +
> + if (field_a->entry->ts > field_b->entry->ts)
> + return 1;
> +
> + if (field_a->entry->ts < field_b->entry->ts)
> + return -1;
> +
> + return 0;
> +}
> +
> +/**
> + * @brief Sort in time the records in kshark_data_container. The container is
> + * resized in order to free the unused memory capacity.
> + *
> + * @param container: Intput location for the kshark_data_container object.
"Input"
-- Steve
> + */
> +void kshark_data_container_sort(struct kshark_data_container *container)
> +{
> + struct kshark_data_field_int64 **data_tmp;
> +
> + qsort(container->data, container->size,
> + sizeof(struct kshark_data_field_int64 *),
> + compare_time_dc);
> +
> + container->sorted = true;
> +
> + data_tmp = realloc(container->data,
> + container->size * sizeof(*container->data));
> +
> + if (!data_tmp)
> + return;
> +
> + container->data = data_tmp;
> + container->capacity = container->size;
> +}
> +
> +/**
> + * @brief Binary search inside a time-sorted array of kshark_data_field_int64.
> + *
> + * @param time: The value of time to search for.
> + * @param data: Input location for the data.
> + * @param l: Array index specifying the lower edge of the range to search in.
> + * @param h: Array index specifying the upper edge of the range to search in.
> + *
> + * @returns On success, the index of the first kshark_data_field_int64 inside
> + * the range, having a timestamp equal or bigger than "time".
> + * If all fields inside the range have timestamps greater than "time"
> + * the function returns BSEARCH_ALL_GREATER (negative value).
> + * If all fields inside the range have timestamps smaller than "time"
> + * the function returns BSEARCH_ALL_SMALLER (negative value).
> + */
> +ssize_t kshark_find_entry_field_by_time(int64_t time,
> + struct kshark_data_field_int64 **data,
> + size_t l, size_t h)
> +{
> + size_t mid;
> +
> + if (data[l]->entry->ts > time)
> + return BSEARCH_ALL_GREATER;
> +
> + if (data[h]->entry->ts < time)
> + return BSEARCH_ALL_SMALLER;
> +
> + /*
> + * After executing the BSEARCH macro, "l" will be the index of the last
> + * entry having timestamp < time and "h" will be the index of the first
> + * entry having timestamp >= time.
> + */
> + BSEARCH(h, l, data[mid]->entry->ts < time);
> + return h;
> +}
> diff --git a/src/libkshark.h b/src/libkshark.h
> index dd4f2b7..aa4b3ca 100644
> --- a/src/libkshark.h
> +++ b/src/libkshark.h
> @@ -1105,6 +1105,49 @@ struct kshark_matrix_data_set
> kshark_merge_data_matrices(struct kshark_matrix_data_set *buffers,
> int n_buffers);
>
> +/**
> + * Structure used to store the data of a kshark_entry plus one additional
> + * 64 bit integer data field.
> + */
> +struct kshark_data_field_int64 {
> + /** The entry object holding the basic data of the trace record. */
> + struct kshark_entry *entry;
> +
> + /** Additional 64 bit integer data field. */
> + int64_t field;
> +};
> +
> +/** The capacity of the kshark_data_container object after initialization. */
> +#define KS_CONTAINER_DEFAULT_SIZE 1024
> +
> +/** Structure used to store an array of entries and data fields. */
> +struct kshark_data_container {
> + /** An array of kshark_data_field_int64 objects. */
> + struct kshark_data_field_int64 **data;
> +
> + /** The total number of kshark_data_field_int64 objects stored. */
> + ssize_t size;
> +
> + /** The memory capacity of the container. */
> + ssize_t capacity;
> +
> + /** Is sorted in time. */
> + bool sorted;
> +};
> +
> +struct kshark_data_container *kshark_init_data_container();
> +
> +void kshark_free_data_container(struct kshark_data_container *container);
> +
> +ssize_t kshark_data_container_append(struct kshark_data_container *container,
> + struct kshark_entry *entry, int64_t field);
> +
> +void kshark_data_container_sort(struct kshark_data_container *container);
> +
> +ssize_t kshark_find_entry_field_by_time(int64_t time,
> + struct kshark_data_field_int64 **data,
> + size_t l, size_t h);
> +
> #ifdef __cplusplus
> }
> #endif
> diff --git a/tests/libkshark-tests.cpp b/tests/libkshark-tests.cpp
> index d0a3594..8a5dcf1 100644
> --- a/tests/libkshark-tests.cpp
> +++ b/tests/libkshark-tests.cpp
> @@ -66,3 +66,40 @@ BOOST_AUTO_TEST_CASE(doule_size_macro)
> for (; i < n; ++i)
> BOOST_CHECK_EQUAL(arr[i], 0);
> }
> +
> +#define N_VALUES 2 * KS_CONTAINER_DEFAULT_SIZE + 1
> +#define MAX_TS 100000
> +BOOST_AUTO_TEST_CASE(fill_data_container)
> +{
> + struct kshark_data_container *data = kshark_init_data_container();
> + struct kshark_entry entries[N_VALUES];
> + int64_t i, ts_last(0);
> +
> + BOOST_CHECK_EQUAL(data->capacity, KS_CONTAINER_DEFAULT_SIZE);
> +
> + for (i = 0; i < N_VALUES; ++i) {
> + entries[i].ts = rand() % MAX_TS;
> + kshark_data_container_append(data, &entries[i], 10 - entries[i].ts);
> + }
> +
> + BOOST_CHECK_EQUAL(data->size, N_VALUES);
> + BOOST_CHECK_EQUAL(data->capacity, 4 * KS_CONTAINER_DEFAULT_SIZE);
> +
> + kshark_data_container_sort(data);
> + BOOST_CHECK_EQUAL(data->capacity, N_VALUES);
> + for (i = 0; i < N_VALUES; ++i) {
> + BOOST_REQUIRE(data->data[i]->entry->ts >= ts_last);
> + BOOST_CHECK_EQUAL(data->data[i]->entry->ts,
> + 10 - data->data[i]->field);
> +
> + ts_last = data->data[i]->entry->ts;
> + }
> +
> + i = kshark_find_entry_field_by_time(MAX_TS / 2, data->data,
> + 0, N_VALUES - 1);
> +
> + BOOST_REQUIRE(data->data[i - 1]->entry->ts < MAX_TS / 2);
> + BOOST_REQUIRE(data->data[i]->entry->ts >= MAX_TS / 2);
> +
> + kshark_free_data_container(data);
> +}
|