[PATCH 1/5] histograms: initial histograms interface

[PATCH 1/5] histograms: initial histograms interface

[Stevie Alvarez]

From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>

Initial header file for libtraceeval's histogram API. The interface
provides a simple way of aggregating trace data and reading through said
data.

Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
---
 include/histograms.h | 340 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 340 insertions(+)
 create mode 100644 include/histograms.h

diff --git a/include/histograms.h b/include/histograms.h
new file mode 100644
index 0000000..b8cd53e
--- /dev/null
+++ b/include/histograms.h
@@ -0,0 +1,340 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval histogram interface.
+ *
+ * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
+ */
+#ifndef __LIBTRACEEVAL_HIST_H__
+#define __LIBTRACEEVAL_HIST_H__
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+// Data definition interfaces
+
+/** Data type distinguishers */
+enum traceeval_data_type {
+	TRACEEVAL_TYPE_NONE,
+	TRACEEVAL_TYPE_STRING,
+	TRACEEVAL_TYPE_NUMBER,
+	TRACEEVAL_TYPE_NUMBER_64,
+	TRACEEVAL_TYPE_NUMBER_32,
+	TRACEEVAL_TYPE_NUMBER_16,
+	TRACEEVAL_TYPE_NUMBER_8,
+	TRACEEVAL_TYPE_DYNAMIC
+};
+
+/** Statistics specification flags */
+enum traceeval_flags {
+	TRACEEVAL_FL_SIGNED	= (1 << 0),
+	TRACEEVAL_FL_STATS	= (1 << 1)
+};
+
+/**
+ * Trace data entry for a traceeval histogram
+ * Constitutes keys and values.
+ */
+union traceeval_data {
+	char				*string;
+	struct traceeval_dynamic	*dyn_data;
+	unsigned long			number;
+	unsigned char			number_8;
+	unsigned short			number_16;
+	unsigned int			number_32;
+	unsigned long long		number_64;
+};
+
+/**
+ * Describes a struct traceeval_data instance
+ * Defines expectations for a corresponding traceeval_data instance for a
+ * traceeval histogram instance. Used to describe both keys and values.
+ *
+ * The id field is an optional value in case the user has multiple struct
+ * traceeval_type instances with type fields set to TRACEEVAL_TYPE_DYNAMIC,
+ * which each relate to distinct user defined struct traceeval_dynamic
+ * 'sub-types'.
+ * For flexibility, dyn_cmp() and dyn_release() take a struct traceeval_type
+ * instance. This allows the user to distingush between different sub-types of
+ * struct traceeeval_dynamic within a single callback function by examining the
+ * id field. This is not a required approach, merely one that is accomodated.
+ *
+ * dyn_cmp() is used to compare two struct traceeval_dynamic instances when a
+ * corresponding struct traceeval_type is reached with its type field set to
+ * TRACEEVAL_TYPE_DYNAMIC. It should return 0 on equality, 1 if the first
+ * argument is greater than the second, -1 for the otherway around, and -2 on
+ * error.
+ *
+ * dyn_release() is used during traceeval_release() to release a union
+ * traceeval_data's struct traceeval_dynamic field when the corresponding
+ * traceeval_type type is set to TRACEEVAL_TYPE_DYNAMIC.
+ */
+struct traceeval_type {
+	enum traceeval_data_type	type;
+	char				*name;
+	size_t				flags;
+	size_t				id;
+	void (*dyn_release)(struct traceeval_dynamic *, struct traceeval_type *);
+	int (*dyn_cmp)(struct traceeval_dynamic *, struct traceeval_dynamic *,
+			struct traceeval_type *);
+};
+
+/** Storage for atypical data */
+struct traceeval_dynamic {
+	size_t		size;
+	void		*data;
+};
+
+// Histogram interfaces
+
+/** Histogram */
+struct traceeval;
+
+/**
+ * traceeval_init - create a traceeval descriptor
+ * @keys: Defines the keys of the "histogram"
+ * @vals: Defines the vals of the "histogram"
+ *
+ * The caller still owns @keys and @vals. The caller is responsible for any
+ * necessary clean up of @keys and @vals.
+ * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
+ * the name field must be either a null-terminated string or NULL. For
+ * members of type TRACEEVAL_TYPE_NONE, the name is ignored.
+ * The @keys and @vals define how the traceeval instance will be populated.
+ * The @keys will be used by traceeval_query() to find an instance within
+ * the "historgram". Note, both the @keys and @vals array must end with:
+ * { .type = TRACEEVAL_TYPE_NONE }.
+ *
+ * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
+ * define the values of the histogram to be empty. If @keys is NULL or starts
+ * with { .type = TRACEEVAL_TYPE_NONE }, it is treated as an error to ensure 
+ * the histogram is valid.
+ *
+ * Retruns the descriptor on success, or NULL on error.
+ */
+struct traceeval *traceeval_init(const struct traceeval_type *keys,
+		const struct traceeval_type *vals);
+
+/**
+ * traceeval_release - release a traceeval descriptor
+ * @teval: An instance of traceeval returned by traceeval_init()
+ *
+ * When the caller of traceeval_init() is done with the returned @teval,
+ * it must call traceeval_release().
+ * This does not release any dynamically allocated data inserted by
+ * the user, although it will call any dyn_release() functions provided by
+ * the user from traceeval_init().
+ */
+void traceeval_release(struct traceeval *teval);
+
+/**
+ * traceeval_insert - Insert an item into the traceeval descriptor
+ * @teval: The descriptor to insert into
+ * @keys: The list of keys that defines what is being inserted.
+ * @vals: The list of values that defines what is being inserted.
+ *
+ * Any dynamically allocated data is still owned by the caller; the
+ * responsibility of deallocating it lies on the caller.
+ * For all elements of @keys and @vals that correspond to a struct
+ * traceeval_type of type TRACEEVAL_TYPE_STRING, the string field must be set
+ * to either a null-terminated string or NULL.
+ * The @keys is an array that holds the data in the order of the keys
+ * passed into traceeval_init(). That is, if traceeval_init() had
+ * keys = { { .type = TRACEEVAL_STRING }, { .type = TRACEEVAL_NUMBER_8 },
+ * { .type = TRACEEVAL_NONE } }; then the @keys array passed in must
+ * be a string (char *) followed by a 8 byte number (char). The @keys
+ * and @vals are only examined to where it expects data. That is,
+ * if the traceeval_init() keys had 3 items where the first two was defining
+ * data, and the last one was the TRACEEVAL_TYPE_NONE, then the @keys
+ * here only needs to be an array of 2, inserting the two items defined
+ * by traceeval_init(). The same goes for @vals.
+ *
+ * Returns 0 on success, and -1 on error.
+ */
+int traceeval_insert(struct traceeval *teval,
+		const union traceeval_data *keys,
+		const union traceeval_data *vals);
+
+/**
+ * traceeval_compare - Check equality between two traceeval instances
+ * @orig: The first traceeval instance
+ * @copy: The second traceeval instance
+ *
+ * This compares the values of the key definitions, value definitions, and
+ * inserted data between @orig and @copy in order. It does not compare
+ * by memory address, except for struct traceeval_type's dyn_release() and
+ * dyn_cmp() fields.
+ *
+ * Returns 0 if @orig and @copy are the same, 1 if not, and -1 on error.
+ */
+int traceeval_compare(struct traceeval *orig, struct traceeval *copy);
+
+// interface to queuery traceeval
+
+/**
+ * traceeval_query - Find the last instance defined by the keys
+ * @teval: The descriptor to search from
+ * @keys: A list of data to look for
+ * @results: A pointer to where to place the results (if found)
+ *
+ * This does a lookup for an instance within the traceeval data.
+ * The @keys is an array defined by the keys declared in traceeval_init().
+ * The @keys will return an item that had the same keys when it was
+ * inserted by traceeval_insert(). The @keys here follow the same rules
+ * as the keys for traceeval_insert().
+ *
+ * Note, when the caller is done with @results, it must call
+ * traceeval_results_release() on it.
+ *
+ * Returns 1 if found, 0 if not found, and -1 on error.
+ */
+int traceeval_query(struct traceeval *teval,
+		const union traceeval_data *keys,
+		union traceeval_data * const *results);
+
+/** Field name/descriptor for number of hits */
+#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
+
+/**
+ * traceeval_find_key - find the index of a key
+ * @teval: The descriptor to find the key for
+ * @field: The name of the key to return the index for
+ *
+ * As the order of how keys are defined by traceeval_init(), it
+ * is important to know what index they are for when dealing with
+ * the other functions.
+ *
+ * Returns the index of the key with @field as the name.
+ * Return -1 if not found.
+ */
+int traceeval_find_key(struct traceeval *teval, const char *field);
+
+/**
+ * traceeval_find_val - find the index of a value
+ * @teval: The descriptor to find the value for
+ * @field: The name of the value to return the index for
+ *
+ * As the order of how values are defined by traceeval_init(), it
+ * is important to know what index they are for when dealing with
+ * the results array from traceeval_query(). In order to facilitate
+ * this, traceeval_find_val() will return the index for a given
+ * @field so that the caller does not have to keep track of it.
+ *
+ * Returns the index of the value with @field as the name that can be
+ * used to index the @results array from traceeval_query().
+ * Return -1 if not found.
+ */
+int traceeval_find_val(struct traceeval *teval, const char *field);
+
+/**
+ * traceeval_results_release - Release the results return by traceeval_query()
+ * @teval: The descriptor used in traceeval_query()
+ * @results: The results returned by traceeval_query()
+ *
+ * The @results returned by traceeval_query() is owned by @teval, and
+ * how it manages it is implementation specific. The caller should not
+ * worry about it. When the caller of traceeval_query() is done with
+ * the @results, it must call traceeval_results_release() on it to
+ * allow traceeval to clean up its references.
+ */
+void traceeval_results_release(struct traceeval *teval,
+		const union traceeval_data *results);
+
+// Result iterator/histogram dump interfaces
+
+/** Iterator over aggregated data */
+struct traceeval_iterator;
+
+/**
+ * traceeval_iterator_get - get an iterator to read the data from traceeval
+ * @teval: The descriptor to read from
+ *
+ * This returns a descriptor that can be used to interate through all the
+ * data within @teval.
+ *
+ * Returns the iterator on success, NULL on error.
+ */
+struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval);
+
+/**
+ * traceeval_iterator_sort - Set how the iterator is sorted
+ * @iter: The iterator to set the sorting
+ * @sort_field: The field (defined by traceeval_init) to sort by.
+ * @level: The level of sorting.
+ * @ascending: Set to true to sort ascending order, or false to descending
+ *
+ * Sets how the iterator shall be sorted. @sort_field is the field to sort
+ * by and may be the name of either a key or a value.
+ *
+ * The @level should be zero the first time this is called to define the main sort
+ * field. If secondary sorting is to be done, then this function should be called
+ * again with @level as 1. For more levels of sorting just call this function
+ * for each level incrementing level each time. Note, if a level is missed,
+ * then this will return an error and sorting will not be done for that level.
+ *
+ * Returns 0 on success, -1 or error (including missing a level).
+ */
+int traceeval_iterator_sort(struct traceeval_iterator *iter,
+		const char *sort_field, int level, bool ascending);
+
+/**
+ * traceeval_iterator_next - Iterate through the data of a traceeval descriptor
+ * @iter: The iterator that holds the location and sorting of the data
+ * @keys: The current set of keys of the traceeval the @iter is sorting through
+ *
+ * This will iterate through all the data of the traceeval descriptor held
+ * by @iter in the sort pattern defined by traceeval_iterator_sort().
+ * The @keys return is same as the data used to populate the data passed into
+ * traceveal_insert(). When the caller is done with @keys, it should be passed
+ * into traceeval_keys_release().
+ *
+ * Returns 1 if it returned an item, 0 if there's no more data to return,
+ * and -1 on error.
+ */
+int traceeval_iterator_next(struct traceeval_iterator *iter,
+		const union traceeval_data **keys);
+
+/**
+ * traceeval_keys_release - Release the keys return by traceeval_iterator_next()
+ * @iter: The iterator used in traceeval_iterator_next().
+ * @keys: The results returned by traceeval_iterator_next()
+ *
+ * The @keys returned by traceeval_iterator_next() is owned by @iter, and
+ * how it manages it is implementation specific. The caller should not
+ * worry about it. When the caller of traceeval_iterator_next() is done with
+ * the @keys, it must call traceeval_keys_release() on it to
+ * allow traceeval to clean up its references.
+ */
+void traceeval_keys_release(struct traceeval_iterator *iter,
+		const union traceeval_data *keys);
+
+// Statistic extraction
+
+/** Statistics about a given field */
+struct traceeval_stat {
+	unsigned long long	max;
+	unsigned long long	min;
+	unsigned long long	total;
+	unsigned long long	avg;
+	unsigned long long	std;
+};
+
+/**
+ * traceeval_stat - Extract stats from a field marke a TRACEEVAL_FL_STATS
+ * @teval: The descriptor holding the traceeval information
+ * @keys: The list of keys to find the instance to get the stats on
+ * @field: The field to retreive the stats for
+ * @stats: A structure to place the stats into.
+ *
+ * This returns the stats of the the given @field. Note, if @field was
+ * not marked for recording stats with the TRACEEVAL_FL_STATS flag, or
+ * if no instance is found that has @keys, this will return an error.
+ *
+ * Returns 0 on success, -1 on error.
+ */
+int traceeval_stat(struct traceeval *teval, const union traceeval_data *keys,
+		const char *field, struct traceeval_stat *stat);
+
+#endif /* __LIBTRACEEVAL_HIST_H__ */
+
-- 
2.41.0

[PATCH 2/5] histograms: traceeval initialize

[Stevie Alvarez]

From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>

traceeval_init() creates a new struct traceeval instance with regards
to the struct traceeval_type array arguments keys and vals. These arrays
define the structure of the histogram, with each describing the expected
structure of inserted arrays of union traceeval_data. The keys and vals
arguments are copied on the heap to ensure that the struct traceeval
instance has access to the definition regardless of how the user
initialized keys and vals.

Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
---
 Makefile         |   2 +-
 src/Makefile     |   1 +
 src/histograms.c | 285 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 287 insertions(+), 1 deletion(-)
 create mode 100644 src/histograms.c

diff --git a/Makefile b/Makefile
index 4a24d5a..3ea051c 100644
--- a/Makefile
+++ b/Makefile
@@ -172,7 +172,7 @@ libs: $(LIBRARY_A) $(LIBRARY_SO)
 
 VALGRIND = $(shell which valgrind)
 UTEST_DIR = utest
-UTEST_BINARY = trace-utest
+UTEST_BINARY = eval-utest
 
 test: force $(LIBRARY_STATIC)
 ifneq ($(CUNIT_INSTALLED),1)
diff --git a/src/Makefile b/src/Makefile
index b4b6e52..b32a389 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -4,6 +4,7 @@ include $(src)/scripts/utils.mk
 
 OBJS =
 OBJS += trace-analysis.o
+OBJS += histograms.o
 
 OBJS := $(OBJS:%.o=$(bdir)/%.o)
 
diff --git a/src/histograms.c b/src/histograms.c
new file mode 100644
index 0000000..13830e4
--- /dev/null
+++ b/src/histograms.c
@@ -0,0 +1,285 @@
+
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval histogram interface implementation.
+ *
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
+ */
+
+#include <histograms.h>
+#include <stdio.h>
+#include <stdbool.h>
+#include <string.h>
+#include <stdarg.h>
+
+/**
+ * Iterate over @keys, which should be an array of struct traceeval_type's,
+ * until reaching an instance of type TRACEEVAL_TYPE_NONE.
+ * @i should be a declared integer type.
+ */
+#define for_each_key(i, keys)	\
+	for (i = 0; (keys)[(i)].type != TRACEEVAL_TYPE_NONE; (i)++)
+
+/** A key-value pair */
+struct entry {
+	union traceeval_data	*keys;
+	union traceeval_data	*vals;
+};
+
+/** A table of key-value entries */
+struct hist_table {
+	struct entry	*map;
+	size_t		nr_entries;
+};
+
+/** Histogram */
+struct traceeval {
+	struct traceeval_type		*def_keys;
+	struct traceeval_type		*def_vals;
+	struct hist_table		*hist;
+};
+
+/** Iterate over results of histogram */
+struct traceeval_iterator {};  // TODO
+
+/**
+ * Print error message.
+ * Additional arguments are used with respect to fmt.
+ */
+static void print_err(const char *fmt, ...)
+{
+	va_list ap;
+
+	va_start(ap, fmt);
+	vfprintf(stderr, fmt, ap);
+	va_end(ap);
+	fprintf(stderr, "\n");
+}
+
+// TODO
+int traceeval_compare(struct traceeval *orig, struct traceeval *copy)
+{
+	return -1;
+}
+
+/**
+ * Resize a struct traceeval_type array to a size of @size + 1.
+ *
+ * Returns a pointer to the resized array, or NULL if the provided pointer was
+ * freed to due lack of memory.
+ */
+static struct traceeval_type *type_realloc(struct traceeval_type *defs,
+		size_t size)
+{
+	struct traceeval_type *tmp_defs = NULL;
+	tmp_defs = realloc(defs,
+			(size + 1) * sizeof(struct traceeval_type));
+	if (!tmp_defs)
+		goto fail_type_realloc;
+	return tmp_defs;
+
+fail_type_realloc:
+	for (int i = 0; i < size; i++) {
+		if (defs[i].name)
+			free(defs[i].name);
+	}
+	free(defs);
+	return NULL;
+}
+
+/**
+ * Clone traceeval_type array @defs to the heap. Must be terminated with
+ * an instance of type TRACEEVAL_TYPE_NONE.
+ * Returns NULL if @defs is NULL, or a name is not null terminated.
+ */
+static struct traceeval_type *type_alloc(const struct traceeval_type *defs)
+{
+	struct traceeval_type *new_defs = NULL;
+	char *name;
+	size_t size = 0;
+
+	// Empty def is represented with single TRACEEVAL_TYPE_NONE
+	if (defs == NULL) {
+		if (!(new_defs = calloc(1, sizeof(struct traceeval_type))))
+			goto fail_type_alloc;
+		new_defs->type = TRACEEVAL_TYPE_NONE;
+		return new_defs;
+	}
+
+	for_each_key(size, defs) {
+		// Resize heap defs and clone
+		new_defs = type_realloc(new_defs, size);
+		if (!new_defs)
+			goto fail_type_alloc;
+
+		// copy current def data to new_def
+		new_defs[size] = defs[size];
+		new_defs[size].name = NULL;
+		// copy name to heap if it's not NULL or type NONE
+		if (defs[size].type != TRACEEVAL_TYPE_NONE) {
+			name = NULL;
+			if (!defs[size].name)
+				goto fail_type_alloc_name;
+
+			name = strdup(defs[size].name);
+			if (!name)
+				goto fail_type_alloc_name;
+			new_defs[size].name = name;
+		}
+	}
+
+	// append array terminator
+	new_defs = type_realloc(new_defs, size);
+	if (!new_defs)
+		goto fail_type_alloc;
+	new_defs[size].type = TRACEEVAL_TYPE_NONE;
+
+	return new_defs;
+fail_type_alloc:
+	if (defs[size].name)
+		print_err("failed to allocate memory for traceeval_type %s", defs[size].name);
+	print_err("failed to allocate memory for traceeval_type index %zu", size);
+	return NULL;
+
+fail_type_alloc_name:
+	if (defs[size].name)
+		print_err("failed to allocate name for traceeval_type %s", defs[size].name);
+
+	print_err("failed to allocate name for traceeval_type index %zu", size);
+	return NULL;
+}
+
+/**
+ * Create a new histogram over the given keys and values.
+ */
+struct traceeval *traceeval_init(const struct traceeval_type *keys,
+				 const struct traceeval_type *vals)
+{
+	struct traceeval *teval;
+	char *err_msg;
+	struct traceeval_type type = {
+		.type = TRACEEVAL_TYPE_NONE
+	};
+
+	if (!keys)
+		return NULL;
+
+	if (keys->type == TRACEEVAL_TYPE_NONE) {
+		err_msg = "keys cannot start with type TRACEEVAL_TYPE_NONE";
+		goto fail_eval_init_unalloced;
+	}
+
+	teval = calloc(1, sizeof(struct traceeval));
+	if (!teval) {
+		err_msg = "failed to allocate memory for traceeval instance";
+		goto fail_eval_init_unalloced;
+	}
+
+	teval->def_keys = type_alloc(keys);
+	if (!teval->def_keys) {
+		err_msg = "failed to allocate user defined keys";
+		goto fail_eval_init;
+	}
+
+	// if vals is NULL, alloc single type NONE
+	if (vals)
+		teval->def_vals = type_alloc(vals);
+	else
+		teval->def_vals = type_alloc(&type);
+
+	if (!teval->def_vals) {
+		err_msg = "failed to allocate user defined values";
+		goto fail_eval_init;
+	}
+
+	teval->hist = calloc(1, sizeof(struct hist_table));
+	if (!teval->hist) {
+		err_msg = "failed to allocate memory for histogram";
+		goto fail_eval_init;
+	}
+	teval->hist->nr_entries = 0;
+
+	return teval;
+fail_eval_init:
+	traceeval_release(teval);
+	/* fall-through */
+
+fail_eval_init_unalloced:
+	print_err(err_msg);
+	return NULL;
+}
+
+// TODO
+void traceeval_release(struct traceeval *teval)
+{
+
+}
+
+// TODO
+int traceeval_insert(struct traceeval *teval,
+		     const union traceeval_data *keys,
+		     const union traceeval_data *vals)
+{
+	return -1;
+}
+
+// TODO
+int traceeval_query(struct traceeval *teval,
+		    const union traceeval_data *keys,
+		    union traceeval_data * const *results)
+{
+	return 0;
+}
+
+// TODO
+int traceeval_find_key(struct traceeval *teval, const char *field)
+{
+	return -1;
+}
+
+// TODO
+int traceeval_find_val(struct traceeval *teval, const char *field)
+{
+	return -1;
+}
+
+// TODO
+void traceeval_results_release(struct traceeval *teval,
+			       const union traceeval_data *results)
+{
+
+}
+
+// TODO
+struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval)
+{
+	return NULL;
+}
+
+// TODO
+int traceeval_iterator_sort(struct traceeval_iterator *iter,
+			    const char *sort_field, int level, bool ascending)
+{
+	return -1;
+}
+
+// TODO
+int traceeval_iterator_next(struct traceeval_iterator *iter,
+			    const union traceeval_data **keys)
+{
+	return 0;
+}
+
+// TODO
+void traceeval_keys_release(struct traceeval_iterator *iter,
+			    const union traceeval_data *keys)
+{
+
+}
+
+// TODO
+int traceeval_stat(struct traceeval *teval, const union traceeval_data *keys,
+		   const char *field, struct traceeval_stat *stat)
+{
+	return -1;
+}
-- 
2.41.0

[PATCH 3/5] histograms: traceeval release

[Stevie Alvarez]

From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>

traceeval_release() deconstructs a given struct traceeval instance. It
frees any data allocated to the heap within the union traceeval_data
arrays of entries to the histogram, and the names allocated for the
struct traceeval_type key-value definitions.

Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
---
 src/histograms.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 85 insertions(+), 2 deletions(-)

diff --git a/src/histograms.c b/src/histograms.c
index 13830e4..f46a0e0 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -209,10 +209,93 @@ fail_eval_init_unalloced:
 	return NULL;
 }
 
-// TODO
-void traceeval_release(struct traceeval *teval)
+/**
+ * Deallocate array of traceeval_type's, which must be terminated by
+ * TRACEEVAL_TYPE_NONE.
+ */
+static void type_release(struct traceeval_type *defs)
 {
+	size_t i = 0;
+
+	if (!defs)
+		return;
+
+	for_each_key(i, defs) {
+		if (defs[i].name)
+			free(defs[i].name);
+	}
+
+	free(defs);
+}
+
+/**
+ * Deallocate any specified dynamic data in @data.
+ */
+static void clean_data(union traceeval_data *data, struct traceeval_type *def)
+{
+	size_t i = 0;
+
+	if (!data || !def)
+		return;
+
+	for_each_key(i, def) {
+		switch (def[i].type) {
+		case TRACEEVAL_TYPE_STRING:
+			if (data[i].string)
+				free(data[i].string);
+			break;
+		case TRACEEVAL_TYPE_DYNAMIC:
+			def[i].dyn_release(data[i].dyn_data, &def[i]);
+			break;
+		default:
+			break;
+		}
+	}
+}
 
+/**
+ * Deallocate all possible data stored within the entry.
+ */
+static void clean_entry(struct entry *entry, struct traceeval *teval)
+{
+	if (!entry)
+		return;
+
+	// deallocate dynamic traceeval_data
+	clean_data(entry->keys, teval->def_keys);
+	clean_data(entry->vals, teval->def_vals);
+	free(entry->keys);
+	free(entry->vals);
+}
+
+/**
+ * Deallocate the hist_table allocated to a traceeval instance.
+ */
+static void hist_table_release(struct traceeval *teval)
+{
+	struct hist_table *hist = teval->hist;
+
+	if (!hist)
+		return;
+
+	for (size_t i = 0; i < hist->nr_entries; i++) {
+		clean_entry(&hist->map[i], teval);
+	}
+	free(hist->map);
+	free(hist);
+}
+
+/**
+ * Deallocate a traceeval instance.
+ */
+void traceeval_release(struct traceeval *teval)
+{
+	if (teval) {
+		hist_table_release(teval);
+		type_release(teval->def_keys);
+		type_release(teval->def_vals);
+		free(teval);
+	}
 }
 
 // TODO
-- 
2.41.0

[PATCH 4/5] histograms: traceeval compare

[Stevie Alvarez]

From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>

traceeval_compare() compares two struct traceeval instances for
equality. This suite of comparitors was made for testing purposes.

Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
---
 src/histograms.c | 178 ++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 176 insertions(+), 2 deletions(-)

diff --git a/src/histograms.c b/src/histograms.c
index f46a0e0..5f1c7ef 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -20,6 +20,19 @@
 #define for_each_key(i, keys)	\
 	for (i = 0; (keys)[(i)].type != TRACEEVAL_TYPE_NONE; (i)++)
 
+/**
+ * Compare two integers of variable length.
+ *
+ * Return 0 if @a and @b are the same, 1 if @a is greater than @b, and -1
+ * if @b is greater than @a.
+ */
+#define compare_numbers_return(a, b)	\
+do {					\
+	if ((a) < (b))			\
+		return -1;		\
+	return (a) != (b);		\
+} while (0)				\
+
 /** A key-value pair */
 struct entry {
 	union traceeval_data	*keys;
@@ -56,10 +69,171 @@ static void print_err(const char *fmt, ...)
 	fprintf(stderr, "\n");
 }
 
-// TODO
+/**
+ * Return 0 if @orig and @copy are the same, 1 otherwise.
+ */
+static int compare_traceeval_type(struct traceeval_type *orig,
+		struct traceeval_type *copy)
+{
+	int o_name_null;
+	int c_name_null;
+
+	// same memory/null
+	if (orig == copy)
+		return 0;
+
+	size_t i = 0;
+	do {
+		if (orig[i].type != copy[i].type)
+			return 1;
+		if (orig[i].type == TRACEEVAL_TYPE_NONE)
+			return 0;
+		if (orig[i].flags != copy[i].flags)
+			return 1;
+		if (orig[i].id != copy[i].id)
+			return 1;
+		if (orig[i].dyn_release != copy[i].dyn_release)
+			return 1;
+		if (orig[i].dyn_cmp != copy[i].dyn_cmp)
+			return 1;
+
+		// make sure both names are same type
+		o_name_null = !orig[i].name;
+		c_name_null = !copy[i].name;
+		if (o_name_null != c_name_null)
+			return 1;
+		if (o_name_null)
+			continue;
+		if (strcmp(orig[i].name, copy[i].name) != 0)
+			return 1;
+	} while (orig[i++].type != TRACEEVAL_TYPE_NONE);
+
+	return 0;
+}
+
+/**
+ * Return 0 if @orig and @copy are the same, 1 if @orig is greater than @copy,
+ * -1 for the other way around, and -2 on error.
+ */
+static int compare_traceeval_data(union traceeval_data *orig,
+		const union traceeval_data *copy, struct traceeval_type *type)
+{
+	if (!orig || !copy)
+		return 1;
+
+	switch (type->type) {
+	case TRACEEVAL_TYPE_NONE:
+		/* There is no corresponding traceeval_data for TRACEEVAL_TYPE_NONE */
+		return -2;
+
+	case TRACEEVAL_TYPE_STRING:
+		int i = strcmp(orig->string, copy->string);
+		if (!i)
+			return 0;
+		if (i > 0)
+			return 1;
+		return -1;
+
+	case TRACEEVAL_TYPE_NUMBER:
+		compare_numbers_return(orig->number, copy->number);
+
+	case TRACEEVAL_TYPE_NUMBER_64:
+		compare_numbers_return(orig->number_64, copy->number_64);
+
+	case TRACEEVAL_TYPE_NUMBER_32:
+		compare_numbers_return(orig->number_32, copy->number_32);
+
+	case TRACEEVAL_TYPE_NUMBER_16:
+		compare_numbers_return(orig->number_16, copy->number_16);
+
+	case TRACEEVAL_TYPE_NUMBER_8:
+		compare_numbers_return(orig->number_8, copy->number_8);
+
+	case TRACEEVAL_TYPE_DYNAMIC:
+		return type->dyn_cmp(orig->dyn_data, copy->dyn_data, type);
+
+	default:
+		print_err("%d is out of range of enum traceeval_data_type", type->type);
+		return -2;
+	}
+}
+
+/**
+ * Compare arrays fo union traceeval_data's with respect to @def.
+ *
+ * Return 0 if @orig and @copy are the same, 1 if not, and -1 on error.
+ */
+static int compare_traceeval_data_set(union traceeval_data *orig,
+		const union traceeval_data *copy, struct traceeval_type *def)
+{
+	int i = 0;
+	int check;
+
+	// compare data arrays
+	for_each_key(i, def) {
+		if ((check = compare_traceeval_data(&orig[i], &copy[i], &def[i])))
+			goto fail_compare_data_set;
+	}
+
+	return 0;
+fail_compare_data_set:
+	if (check == -2)
+		return -1;
+	return 1;
+}
+
+/**
+ * Return 0 if @orig and @copy are the same, 1 if not, and -1 on error.
+ */
+static int compare_entries(struct entry *orig, struct entry *copy,
+		struct traceeval *teval)
+{
+	int check;
+
+	// compare keys
+	check = compare_traceeval_data_set(orig->keys, copy->keys,
+			teval->def_keys);
+	if (check)
+		return check;
+
+	// compare values
+	check = compare_traceeval_data_set(orig->vals, copy->vals,
+			teval->def_vals);
+	return check;
+}
+
+/**
+ * Return 0 if struct hist_table of @orig and @copy are the same, 1 if not,
+ * and -1 on error.
+ */
+static int compare_hist(struct traceeval *orig, struct traceeval *copy)
+{
+	struct hist_table *o_hist = orig->hist;
+	struct hist_table *c_hist = copy->hist;
+	int cnt = !(o_hist->nr_entries == c_hist->nr_entries);
+	if (cnt)
+		return 1;
+
+	for (size_t i = 0; i < o_hist->nr_entries; i++) {
+		// cmp each entry
+		compare_entries(&o_hist->map[i], &c_hist->map[i], orig);
+	}
+	return 0;	
+}
+
+/**
+ * Return 0 if @orig and @copy are the same, 1 if not, -1 if error.
+ */
 int traceeval_compare(struct traceeval *orig, struct traceeval *copy)
 {
-	return -1;
+	if ((!orig) || (!copy))
+		return -1;
+
+	int keys = compare_traceeval_type(orig->def_keys, copy->def_keys);
+	int vals = compare_traceeval_type(orig->def_vals, copy->def_vals);
+	int hists = compare_hist(orig, copy);
+
+	return (keys || vals || hists);
 }
 
 /**
-- 
2.41.0

[PATCH 5/5] histograms: Add struct traceeval unit tests

[Stevie Alvarez]

From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>

Add unit tests for traceeval_init(), traceeval_release(), and
traceeval_compare() to check edge cases and ensure the interface is
functional.

Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
---
 utest/.gitignore        |   1 +
 utest/Makefile          |  35 +++++++
 utest/eval-test.h       |  10 ++
 utest/eval-utest.c      |  27 +++++
 utest/traceeval-utest.c | 222 ++++++++++++++++++++++++++++++++++++++++
 5 files changed, 295 insertions(+)
 create mode 100644 utest/.gitignore
 create mode 100644 utest/Makefile
 create mode 100644 utest/eval-test.h
 create mode 100644 utest/eval-utest.c
 create mode 100644 utest/traceeval-utest.c

diff --git a/utest/.gitignore b/utest/.gitignore
new file mode 100644
index 0000000..ca0ac10
--- /dev/null
+++ b/utest/.gitignore
@@ -0,0 +1 @@
+eval-utest
diff --git a/utest/Makefile b/utest/Makefile
new file mode 100644
index 0000000..955f91e
--- /dev/null
+++ b/utest/Makefile
@@ -0,0 +1,35 @@
+# SPDX-License-Identifier: MIT
+
+include $(src)/scripts/utils.mk
+
+bdir := $(obj)/utest
+eval_lib := $(obj)/lib/libtraceeval.a
+
+TARGETS = $(bdir)/eval-utest
+
+OBJS := eval-utest.o
+OBJS += traceeval-utest.o
+
+LIBS += -lcunit				\
+	-ldl				\
+	$(eval_lib)
+
+OBJS := $(OBJS:%.o=$(bdir)/%.o)
+
+$(bdir):
+	@mkdir -p $(bdir)
+
+$(OBJS): | $(bdir)
+
+$(bdir)/eval-utest: $(OBJS) $(eval_lib)
+	$(Q)$(do_app_build)
+
+$(bdir)/%.o: %.c
+	$(Q)$(call do_fpic_compile)
+
+-include .*.d
+
+test: $(TARGETS)
+
+clean:
+	$(Q)$(call do_clean,$(TARGETS) $(bdir)/*.o $(bdir)/.*.d)
diff --git a/utest/eval-test.h b/utest/eval-test.h
new file mode 100644
index 0000000..f3372e8
--- /dev/null
+++ b/utest/eval-test.h
@@ -0,0 +1,10 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
+ */
+#ifndef _EVAL_UTEST_H_
+#define _EVAL_UTEST_H_
+
+void test_traceeval_lib(void);
+
+#endif /* _EVAL_UTEST_H_ */
diff --git a/utest/eval-utest.c b/utest/eval-utest.c
new file mode 100644
index 0000000..771a0c4
--- /dev/null
+++ b/utest/eval-utest.c
@@ -0,0 +1,27 @@
+
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
+ */
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <CUnit/CUnit.h>
+#include <CUnit/Basic.h>
+
+#include "eval-test.h"
+
+int main(int argc, char **argv)
+{
+	if (CU_initialize_registry() != CUE_SUCCESS) {
+		printf("Test registry cannot be initialized\n");
+		return EXIT_FAILURE;
+	}
+
+	test_traceeval_lib();
+
+	CU_basic_set_mode(CU_BRM_VERBOSE);
+	CU_basic_run_tests();
+	CU_cleanup_registry();
+	return EXIT_SUCCESS;
+}
diff --git a/utest/traceeval-utest.c b/utest/traceeval-utest.c
new file mode 100644
index 0000000..2bcb4b9
--- /dev/null
+++ b/utest/traceeval-utest.c
@@ -0,0 +1,222 @@
+// SPDX-License-Identifier: MIT
+/*
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
+ */
+
+#include <string.h>
+#include <stdio.h>
+#include <stdbool.h>
+#include <CUnit/CUnit.h>
+#include <CUnit/Basic.h>
+
+#include <histograms.h>
+
+#define TRACEEVAL_SUITE		"traceeval library"
+#define TRACEEVAL_SUCCESS	0
+#define TRACEEVAL_FAILURE	-1
+#define TRACEEVAL_NOT_SAME	1
+
+/**
+ * Test traceeval_init(), traceeval_release(), and traceeval_compare() with
+ * NULL values.
+ */
+void test_eval_null(void)
+{
+	// set up
+	char *name = "test null";
+	enum traceeval_data_type type = TRACEEVAL_TYPE_NONE;
+	const struct traceeval_type test_data[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = name
+		},
+		{
+			.type = type,
+			.name = NULL
+		}
+	};
+
+	// test init
+	struct traceeval *result_null = traceeval_init(NULL, NULL);
+	struct traceeval *result_key = traceeval_init(test_data, NULL);
+	struct traceeval *result_val = traceeval_init(NULL, test_data);
+	
+	// analyze init
+	CU_ASSERT(!result_null);
+	CU_ASSERT(result_key != NULL);
+	CU_ASSERT(!result_val);
+
+	// release
+	traceeval_release(NULL);
+	traceeval_release(result_key);
+}
+
+/**
+ * Use provided data to test traceeval_init(), traceeval_compare(), and
+ * traceeval_release().
+ */
+void test_eval_base(const struct traceeval_type *keys1,
+		const struct traceeval_type *vals1,
+		const struct traceeval_type *keys2,
+		const struct traceeval_type *vals2,
+		bool init_not_null1, bool init_not_null2,
+		int compare_result)
+{
+	struct traceeval *init1;
+	struct traceeval *init2;
+	int result;
+
+	// test init
+	init1 = traceeval_init(keys1, vals1);
+	init2 = traceeval_init(keys2, vals2);
+
+	result = init1 != NULL;
+	if (init_not_null1) {
+		CU_ASSERT(result);
+	} else {
+		CU_ASSERT(!result);
+	}
+
+	result = init2 != NULL;
+	if (init_not_null2) {
+		CU_ASSERT(result);
+	} else {
+		CU_ASSERT(!result);
+	}
+
+	// test compare
+	result = traceeval_compare(init1, init2);
+	
+	// analyze compare
+	CU_ASSERT(result == compare_result);
+	
+	// release
+	traceeval_release(init1);
+	traceeval_release(init2);
+}
+
+/**
+ * Test traceeval_init(), traceeval_release(), and traceeval_compare() with
+ * TRACEEVAL_TYPE_NONE.
+ */
+void test_eval_none(void)
+{
+	// set up
+	char *name = "test none";
+	char *name2 = "test none (some)";
+	const struct traceeval_type test_data_none[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NONE,
+			.name = name
+		}
+	};
+	const struct traceeval_type test_data_some[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = name2
+		},
+		{
+			.type = TRACEEVAL_TYPE_NONE,
+			.name = NULL
+		}
+	};
+
+	test_eval_base(test_data_some, test_data_none, test_data_some,
+			test_data_none, true, true, TRACEEVAL_SUCCESS);
+	test_eval_base(test_data_none, test_data_none, test_data_some,
+			test_data_none, false, true, TRACEEVAL_FAILURE);
+	test_eval_base(test_data_none, test_data_none, test_data_none,
+			test_data_none, false, false, TRACEEVAL_FAILURE);
+}
+
+/**
+ * Test traceeval_init() and traceeval_release() with equivalent values.
+ */
+void test_eval_same(void)
+{
+	// set up
+	char *name = "test data";
+	char *name2 = "test done";
+	const struct traceeval_type test_data[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = name
+		},
+		{
+			.type = TRACEEVAL_TYPE_NONE,
+			.name = name2
+		}
+	};
+	
+	test_eval_base(test_data, test_data, test_data, test_data, true, true,
+			TRACEEVAL_SUCCESS);
+}
+
+/**
+ * Test traceeval_init() and traceeval_release() with non-equivalent values.
+ */
+void test_eval_not_same(void)
+{
+	const struct traceeval_type test_data1[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "test data 1"
+		},
+		{
+			.type = TRACEEVAL_TYPE_NONE,
+			.name = NULL
+		}
+	};
+	const struct traceeval_type test_data2[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "test data 2"
+		},
+		{
+			.type = TRACEEVAL_TYPE_NONE,
+			.name = NULL
+		}
+	};
+
+	// type 1 key diff
+	test_eval_base(test_data2, test_data1, test_data1, test_data1, true,
+			true, TRACEEVAL_NOT_SAME);
+	// type 1 data diff
+	test_eval_base(test_data1, test_data2, test_data1, test_data1, true,
+			true, TRACEEVAL_NOT_SAME);
+	// type 2 key diff
+	test_eval_base(test_data1, test_data1, test_data2, test_data1, true,
+			true, TRACEEVAL_NOT_SAME);
+	// type 2 data diff
+	test_eval_base(test_data1, test_data1, test_data1, test_data2, true,
+			true, TRACEEVAL_NOT_SAME);
+}
+
+/**
+ * Tests the traceeval_init() and traceeval_release() functions.
+ */
+void test_eval(void)
+{
+	test_eval_null();
+	test_eval_none();
+	test_eval_same();
+	test_eval_not_same();
+}
+
+/**
+ * Register tests with CUnit.
+ */
+void test_traceeval_lib(void)
+{
+	CU_pSuite suite = NULL;
+	
+	// set up suite
+	suite = CU_add_suite(TRACEEVAL_SUITE, NULL, NULL);
+	if (suite == NULL) {
+		fprintf(stderr, "Suite %s cannot be created\n", TRACEEVAL_SUITE);
+		return;
+	}
+
+	// add tests to suite
+	CU_add_test(suite, "Test traceeval alloc and release", test_eval);
+}
-- 
2.41.0

Re: [PATCH 1/5] histograms: initial histograms interface

[Steven Rostedt]

Hi Stevie,

Thanks for sending this. Note, you can use "--cover-letter" to "git
send-email" that will add a cover letter "[PATCH 0/5}" that you can use
to explain the patch set. All other patches will be a reply to that
email. It's usually a requirement for most patch series.

On Fri, 28 Jul 2023 15:04:36 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> Initial header file for libtraceeval's histogram API. The interface
> provides a simple way of aggregating trace data and reading through said
> data.
> 
> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  include/histograms.h | 340 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 340 insertions(+)
>  create mode 100644 include/histograms.h
> 
> diff --git a/include/histograms.h b/include/histograms.h

Note, this should be called traceeval.h

If you want to call it this temporarily until we remove the old one
that's fine.

> new file mode 100644
> index 0000000..b8cd53e
> --- /dev/null
> +++ b/include/histograms.h
> @@ -0,0 +1,340 @@
> +/* SPDX-License-Identifier: MIT */
> +/*
> + * libtraceeval histogram interface.
> + *
> + * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +#ifndef __LIBTRACEEVAL_HIST_H__
> +#define __LIBTRACEEVAL_HIST_H__
> +
> +#include <stdlib.h>
> +#include <stddef.h>
> +#include <stdbool.h>
> +
> +// Data definition interfaces
> +
> +/** Data type distinguishers */

So there's a specific comment structure called "kernel doc" that starts
with "/**" and has some rules. This doesn't need that format, so you
only need to use "/* " to not confuse to make it look like kernel doc.

/* Data type distinguishers */

> +enum traceeval_data_type {
> +	TRACEEVAL_TYPE_NONE,
> +	TRACEEVAL_TYPE_STRING,
> +	TRACEEVAL_TYPE_NUMBER,
> +	TRACEEVAL_TYPE_NUMBER_64,
> +	TRACEEVAL_TYPE_NUMBER_32,
> +	TRACEEVAL_TYPE_NUMBER_16,
> +	TRACEEVAL_TYPE_NUMBER_8,
> +	TRACEEVAL_TYPE_DYNAMIC
> +};
> +
> +/** Statistics specification flags */

Same here.

> +enum traceeval_flags {
> +	TRACEEVAL_FL_SIGNED	= (1 << 0),
> +	TRACEEVAL_FL_STATS	= (1 << 1)

As I think about this more, I think we should just do "stats" for all
numbered values. It doesn't really make sense for keys.

But we should still have TRACEEVAL_FL_TIMESTAMP (see traceeval_insert()
below)

> +};
> +
> +/**

And here.

> + * Trace data entry for a traceeval histogram
> + * Constitutes keys and values.
> + */
> +union traceeval_data {
> +	char				*string;
> +	struct traceeval_dynamic	*dyn_data;
> +	unsigned long			number;
> +	unsigned char			number_8;
> +	unsigned short			number_16;
> +	unsigned int			number_32;
> +	unsigned long long		number_64;
> +};
> +
> +/**
> + * Describes a struct traceeval_data instance

So this structure could have a kernel doc comment. Which would look like:

/**
 * struct traceeval_type - Describes the type of a traceevent_data instance
 * @type: The enum type that describes the traceeval_data
 * @name: The string name of the traceveval_data
 * @flags: flags to describe the traceeval_data
 * @id: User specified identifier
 * @dyn_release: For dynamic types called on release (ignored for other types)
 * @dyn_cmp: A way to compare dynamic types (ignored for other types)
 *
 * The typeeval_type structure defines expectations for a corresponding
 * traceeval_data instance for a traceeval histogram instance. Used to
 * describe both keys and values.
 *
 * The @id field is an optional value in case the user has multiple struct
 *
 * The traceeval_type instances with @type fields set to
 * TRACEEVAL_TYPE_DYNAMIC, which each relate to distinct user defined
 * struct traceeval_dynamic 'sub-types'.
 *
 * For flexibility, @dyn_cmp() and @dyn_release() take a struct
 * traceeval_type instance. This allows the user to distingush between
 * different sub-types of struct traceeeval_dynamic within a single
 * callback function by examining the @id field. This is not a required
 * approach, merely one that is accomodated.
 *
 * @dyn_cmp() is used to compare two struct traceeval_dynamic instances when a
 * corresponding struct traceeval_type is reached with its type field set to
 * TRACEEVAL_TYPE_DYNAMIC. It should return 0 on equality, 1 if the first
 * argument is greater than the second, -1 for the otherway around, and -2 on
 * error.
 *
 * dyn_release() is used during traceeval_release() to release a union
 * traceeval_data's struct traceeval_dynamic field when the corresponding
 * traceeval_type type is set to TRACEEVAL_TYPE_DYNAMIC.
 */

> + * Defines expectations for a corresponding traceeval_data instance for a
> + * traceeval histogram instance. Used to describe both keys and values.
> + *
> + * The id field is an optional value in case the user has multiple struct
> + * traceeval_type instances with type fields set to TRACEEVAL_TYPE_DYNAMIC,
> + * which each relate to distinct user defined struct traceeval_dynamic
> + * 'sub-types'.
> + * For flexibility, dyn_cmp() and dyn_release() take a struct traceeval_type
> + * instance. This allows the user to distingush between different sub-types of
> + * struct traceeeval_dynamic within a single callback function by examining the
> + * id field. This is not a required approach, merely one that is accomodated.
> + *
> + * dyn_cmp() is used to compare two struct traceeval_dynamic instances when a
> + * corresponding struct traceeval_type is reached with its type field set to
> + * TRACEEVAL_TYPE_DYNAMIC. It should return 0 on equality, 1 if the first
> + * argument is greater than the second, -1 for the otherway around, and -2 on
> + * error.
> + *
> + * dyn_release() is used during traceeval_release() to release a union
> + * traceeval_data's struct traceeval_dynamic field when the corresponding
> + * traceeval_type type is set to TRACEEVAL_TYPE_DYNAMIC.
> + */
> +struct traceeval_type {
> +	enum traceeval_data_type	type;
> +	char				*name;
> +	size_t				flags;
> +	size_t				id;

> +	void (*dyn_release)(struct traceeval_dynamic *, struct traceeval_type *);
> +	int (*dyn_cmp)(struct traceeval_dynamic *, struct traceeval_dynamic *,
> +			struct traceeval_type *);

You can still index the function pointers:

	void 				(*dyn_release)(struct traceeval_dynamic *,
						 struct traceeval_type *);
	int 				(*dyn_cmp)(struct traceeval_dynamic *, struct traceeval_dynamic *,
						struct traceeval_type *);

Better yet, use typedefs:

typedef void (*traceeval_dyn_release_fn)(struct traceeval_dynamic *, struct traceeval_type *);
typedef void (*traceeval_dyn_cmp_fn)(struct traceeval_dynamic *, struct traceeval_dynamic *,
						struct traceeval_type *);


struct traceeval_type {
	[..]
	traceveal_dyn_release_fn	dyn_release;
	traceeval_dyn_cmp_fn		dyn_cmp;
};

Which looks much better.

> +};
> +
> +/** Storage for atypical data */

This could have kernel doc too:

/**
 * struct traceeval_dynamic - storage for dynamic traceeval_types
 * @size: The size of the dynamic type
 * @data: The pointer to the data of the dynamic type.
 */

> +struct traceeval_dynamic {
> +	size_t		size;
> +	void		*data;
> +};
> +
> +// Histogram interfaces

I don't think we should call it "histograms" as it can create
histograms, but calling it a histogram limits its possibilities.

// traceeval interfaces

> +
> +/** Histogram */

Remove the above comment. The below is fine without a comment.

> +struct traceeval;
> +
> +/**
> + * traceeval_init - create a traceeval descriptor

Remove all the double asterisks.

 /**
  * traceeval_init
  [..]

Instead of
  * * ...

Also, for header files, functions do not need kernel doc comments. They
should exist in the C files where the function is described.

> + * @keys: Defines the keys of the "histogram"

 * @keys: Defines the keys to differentiate traceeval entries

> + * @vals: Defines the vals of the "histogram"

 * @ vals: Defines values attached to entries differentiated by @keys.

> + *
> + * The caller still owns @keys and @vals. The caller is responsible for any
> + * necessary clean up of @keys and @vals.

I would instead say:

 * The @keys and @vals passed in are copied for internal use.

The "const" in the prototype and the above statement should be good
enough, where the user of this interface should understand the rest.

> + * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
> + * the name field must be either a null-terminated string or NULL. For

The above is incorrect, as it can't be NULL.

> + * members of type TRACEEVAL_TYPE_NONE, the name is ignored.

Note, the below paragraph should come first. You want to describe what
the function does before going into any constraints of the function.

> + * The @keys and @vals define how the traceeval instance will be populated.
> + * The @keys will be used by traceeval_query() to find an instance within
> + * the "historgram". Note, both the @keys and @vals array must end with:
> + * { .type = TRACEEVAL_TYPE_NONE }.
> + *
> + * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
> + * define the values of the histogram to be empty. If @keys is NULL or starts
> + * with { .type = TRACEEVAL_TYPE_NONE }, it is treated as an error to ensure 
> + * the histogram is valid.

The last sentence about @keys should just state:

 * @keys must be populated with at least one element that is not
 * TRACEEVAL_TYPE_NONE.

> + *
> + * Retruns the descriptor on success, or NULL on error.
> + */
> +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> +		const struct traceeval_type *vals);
> +
> +/**
> + * traceeval_release - release a traceeval descriptor

Again, replace all the double asterisks with single ones.

> + * @teval: An instance of traceeval returned by traceeval_init()
> + *
> + * When the caller of traceeval_init() is done with the returned @teval,
> + * it must call traceeval_release().
> + * This does not release any dynamically allocated data inserted by
> + * the user, although it will call any dyn_release() functions provided by
> + * the user from traceeval_init().

The above is contradictory, as it does release user dynamically
allocated data by calling the dyn_release() function.

 * This cleans up all internally allocated data of @teval and will call
 * the corresponding dyn_release() functions that were registered for
 * the TRACEEVAL_TYPE_DYNAMIC type keys and values.


> + */
> +void traceeval_release(struct traceeval *teval);
> +
> +/**
> + * traceeval_insert - Insert an item into the traceeval descriptor
> + * @teval: The descriptor to insert into
> + * @keys: The list of keys that defines what is being inserted.
> + * @vals: The list of values that defines what is being inserted.
> + *

> + * Any dynamically allocated data is still owned by the caller; the
> + * responsibility of deallocating it lies on the caller.

The above can be removed.

> + * For all elements of @keys and @vals that correspond to a struct
> + * traceeval_type of type TRACEEVAL_TYPE_STRING, the string field must be set
> + * to either a null-terminated string or NULL.
> + * The @keys is an array that holds the data in the order of the keys
> + * passed into traceeval_init(). That is, if traceeval_init() had
> + * keys = { { .type = TRACEEVAL_STRING }, { .type = TRACEEVAL_NUMBER_8 },
> + * { .type = TRACEEVAL_NONE } }; then the @keys array passed in must
> + * be a string (char *) followed by a 8 byte number (char). The @keys
> + * and @vals are only examined to where it expects data. That is,
> + * if the traceeval_init() keys had 3 items where the first two was defining
> + * data, and the last one was the TRACEEVAL_TYPE_NONE, then the @keys
> + * here only needs to be an array of 2, inserting the two items defined
> + * by traceeval_init(). The same goes for @vals.

So the above really doesn't explain what the function does.

 * This function will insert an entry defined by @keys and @vals into
 * the traceeval instance. The array of @keys and @vals must match that
 * of what was added to the corresponding parameters of
 * traceeval_init() that created @teval. No checking is performed, if
 * there is a mismatch in array length, it will result in undefined behavior.
 * The types of the @keys and @vals must also match the types used for
 * the corresponding parameters to traceeval_init().
 *
 * If an entry already exists that matches the @keys, then strings and
 * values will be overwritten by the current values and the old values
 * will be discarded. For number values, the max, min, total and count
 * will be recorded. If an entry in @vals has TRACEEVAL_FL_TIMESTAMP
 * set in its corresponding traceeval_type descriptor, then it will be
 * used to timestamp the max and min values.

The description of traceeval_type and traceeval_data mappings as you
did before, can be saved for the man pages.

> + *
> + * Returns 0 on success, and -1 on error.
> + */
> +int traceeval_insert(struct traceeval *teval,
> +		const union traceeval_data *keys,
> +		const union traceeval_data *vals);
> +
> +/**
> + * traceeval_compare - Check equality between two traceeval instances
> + * @orig: The first traceeval instance
> + * @copy: The second traceeval instance
> + *
> + * This compares the values of the key definitions, value definitions, and
> + * inserted data between @orig and @copy in order. It does not compare
> + * by memory address, except for struct traceeval_type's dyn_release() and
> + * dyn_cmp() fields.
> + *
> + * Returns 0 if @orig and @copy are the same, 1 if not, and -1 on error.
> + */
> +int traceeval_compare(struct traceeval *orig, struct traceeval
> *copy); +

I'm not really sure what a traceveal_compare() would be used for
externally. I think we can just remove it? Leave it internally if you
use it for CUTESTs.

> +// interface to queuery traceeval
> +
> +/**
> + * traceeval_query - Find the last instance defined by the keys
> + * @teval: The descriptor to search from
> + * @keys: A list of data to look for
> + * @results: A pointer to where to place the results (if found)
> + *
> + * This does a lookup for an instance within the traceeval data.
> + * The @keys is an array defined by the keys declared in traceeval_init().
> + * The @keys will return an item that had the same keys when it was

 The @results will ... ?

> + * inserted by traceeval_insert(). The @keys here follow the same rules
> + * as the keys for traceeval_insert().

I know that you copied most of this from my document, but I don't even
know what the above means ;-)

Anyway, this patch should be folded piece by piece in the other patches
as you add the functions as you implement them. That is, you should
have 4 patches not 5 (this one should no longer exist, as the changes
will go in the patches that implement each).

-- Steve


> + *
> + * Note, when the caller is done with @results, it must call
> + * traceeval_results_release() on it.
> + *
> + * Returns 1 if found, 0 if not found, and -1 on error.
> + */
> +int traceeval_query(struct traceeval *teval,
> +		const union traceeval_data *keys,
> +		union traceeval_data * const *results);
> +
> +/** Field name/descriptor for number of hits */
> +#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
> +
> +/**
> + * traceeval_find_key - find the index of a key
> + * @teval: The descriptor to find the key for
> + * @field: The name of the key to return the index for
> + *
> + * As the order of how keys are defined by traceeval_init(), it
> + * is important to know what index they are for when dealing with
> + * the other functions.
> + *
> + * Returns the index of the key with @field as the name.
> + * Return -1 if not found.
> + */
> +int traceeval_find_key(struct traceeval *teval, const char *field);
> +
> +/**
> + * traceeval_find_val - find the index of a value
> + * @teval: The descriptor to find the value for
> + * @field: The name of the value to return the index for
> + *
> + * As the order of how values are defined by traceeval_init(), it
> + * is important to know what index they are for when dealing with
> + * the results array from traceeval_query(). In order to facilitate
> + * this, traceeval_find_val() will return the index for a given
> + * @field so that the caller does not have to keep track of it.
> + *
> + * Returns the index of the value with @field as the name that can be
> + * used to index the @results array from traceeval_query().
> + * Return -1 if not found.
> + */
> +int traceeval_find_val(struct traceeval *teval, const char *field);
> +
> +/**
> + * traceeval_results_release - Release the results return by traceeval_query()
> + * @teval: The descriptor used in traceeval_query()
> + * @results: The results returned by traceeval_query()
> + *
> + * The @results returned by traceeval_query() is owned by @teval, and
> + * how it manages it is implementation specific. The caller should not
> + * worry about it. When the caller of traceeval_query() is done with
> + * the @results, it must call traceeval_results_release() on it to
> + * allow traceeval to clean up its references.
> + */
> +void traceeval_results_release(struct traceeval *teval,
> +		const union traceeval_data *results);
> +
> +// Result iterator/histogram dump interfaces
> +
> +/** Iterator over aggregated data */
> +struct traceeval_iterator;
> +
> +/**
> + * traceeval_iterator_get - get an iterator to read the data from traceeval
> + * @teval: The descriptor to read from
> + *
> + * This returns a descriptor that can be used to interate through all the
> + * data within @teval.
> + *
> + * Returns the iterator on success, NULL on error.
> + */
> +struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval);
> +/**
> + * traceeval_iterator_sort - Set how the iterator is sorted
> + * @iter: The iterator to set the sorting
> + * @sort_field: The field (defined by traceeval_init) to sort by.
> + * @level: The level of sorting.
> + * @ascending: Set to true to sort ascending order, or false to descending
> + *
> + * Sets how the iterator shall be sorted. @sort_field is the field to sort
> + * by and may be the name of either a key or a value.
> + *
> + * The @level should be zero the first time this is called to define the main sort
> + * field. If secondary sorting is to be done, then this function should be called
> + * again with @level as 1. For more levels of sorting just call this function
> + * for each level incrementing level each time. Note, if a level is missed,
> + * then this will return an error and sorting will not be done for that level.
> + *
> + * Returns 0 on success, -1 or error (including missing a level).
> + */
> +int traceeval_iterator_sort(struct traceeval_iterator *iter,
> +		const char *sort_field, int level, bool ascending);
> +
> +/**
> + * traceeval_iterator_next - Iterate through the data of a traceeval descriptor
> + * @iter: The iterator that holds the location and sorting of the data
> + * @keys: The current set of keys of the traceeval the @iter is sorting through
> + *
> + * This will iterate through all the data of the traceeval descriptor held
> + * by @iter in the sort pattern defined by traceeval_iterator_sort().
> + * The @keys return is same as the data used to populate the data passed into
> + * traceveal_insert(). When the caller is done with @keys, it should be passed
> + * into traceeval_keys_release().
> + *
> + * Returns 1 if it returned an item, 0 if there's no more data to return,
> + * and -1 on error.
> + */
> +int traceeval_iterator_next(struct traceeval_iterator *iter,
> +		const union traceeval_data **keys);
> +
> +/**
> + * traceeval_keys_release - Release the keys return by
> traceeval_iterator_next()
> + * @iter: The iterator used in traceeval_iterator_next().
> + * @keys: The results returned by traceeval_iterator_next()
> + *
> + * The @keys returned by traceeval_iterator_next() is owned by
> @iter, and
> + * how it manages it is implementation specific. The caller should
> not
> + * worry about it. When the caller of traceeval_iterator_next() is
> done with
> + * the @keys, it must call traceeval_keys_release() on it to
> + * allow traceeval to clean up its references.
> + */
> +void traceeval_keys_release(struct traceeval_iterator *iter,
> +		const union traceeval_data *keys);
> +
> +// Statistic extraction
> +
> +/** Statistics about a given field */
> +struct traceeval_stat {
> +	unsigned long long	max;
> +	unsigned long long	min;
> +	unsigned long long	total;
> +	unsigned long long	avg;
> +	unsigned long long	std;
> +};
> +
> +/**
> + * traceeval_stat - Extract stats from a field marke a
> TRACEEVAL_FL_STATS
> + * @teval: The descriptor holding the traceeval information
> + * @keys: The list of keys to find the instance to get the stats on
> + * @field: The field to retreive the stats for
> + * @stats: A structure to place the stats into.
> + *
> + * This returns the stats of the the given @field. Note, if @field
> was
> + * not marked for recording stats with the TRACEEVAL_FL_STATS flag,
> or
> + * if no instance is found that has @keys, this will return an error.
> + *
> + * Returns 0 on success, -1 on error.
> + */
> +int traceeval_stat(struct traceeval *teval, const union
> traceeval_data *keys,
> +		const char *field, struct traceeval_stat *stat);
> +
> +#endif /* __LIBTRACEEVAL_HIST_H__ */
> +

Re: [PATCH 2/5] histograms: traceeval initialize

[Steven Rostedt]

On Fri, 28 Jul 2023 15:04:37 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> traceeval_init() creates a new struct traceeval instance with regards
> to the struct traceeval_type array arguments keys and vals. These arrays
> define the structure of the histogram, with each describing the expected
> structure of inserted arrays of union traceeval_data. The keys and vals
> arguments are copied on the heap to ensure that the struct traceeval
> instance has access to the definition regardless of how the user
> initialized keys and vals.
> 
> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  Makefile         |   2 +-
>  src/Makefile     |   1 +
>  src/histograms.c | 285 +++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 287 insertions(+), 1 deletion(-)
>  create mode 100644 src/histograms.c
> 
> diff --git a/Makefile b/Makefile
> index 4a24d5a..3ea051c 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -172,7 +172,7 @@ libs: $(LIBRARY_A) $(LIBRARY_SO)
>  
>  VALGRIND = $(shell which valgrind)
>  UTEST_DIR = utest
> -UTEST_BINARY = trace-utest
> +UTEST_BINARY = eval-utest
>  
>  test: force $(LIBRARY_STATIC)
>  ifneq ($(CUNIT_INSTALLED),1)
> diff --git a/src/Makefile b/src/Makefile
> index b4b6e52..b32a389 100644
> --- a/src/Makefile
> +++ b/src/Makefile
> @@ -4,6 +4,7 @@ include $(src)/scripts/utils.mk
>  
>  OBJS =
>  OBJS += trace-analysis.o
> +OBJS += histograms.o
>  
>  OBJS := $(OBJS:%.o=$(bdir)/%.o)
>  
> diff --git a/src/histograms.c b/src/histograms.c
> new file mode 100644
> index 0000000..13830e4
> --- /dev/null
> +++ b/src/histograms.c
> @@ -0,0 +1,285 @@
> +
> +/* SPDX-License-Identifier: MIT */
> +/*
> + * libtraceeval histogram interface implementation.
> + *
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +
> +#include <histograms.h>
> +#include <stdio.h>
> +#include <stdbool.h>
> +#include <string.h>
> +#include <stdarg.h>

Nit, I find it cleaner to have an upside down x-mas tree style of
header includes. This is more of a guideline than anything else.

#include <stdbool.h>
#include <string.h>
#include <strarg.h>
#include <stdio.h>

Just looks cleaner.

Oh, and for the header that is specific for this library, that goes
afterward. Sometimes with a space between it and the other includes.

#include <histograms.h>

And since "histograms" is such a generic term, and there may actually
be a library that has that name, let's make it:

#include <traceeval-hist.h>

for now (it may replace the normal one later).


> +
> +/**
> + * Iterate over @keys, which should be an array of struct traceeval_type's,
> + * until reaching an instance of type TRACEEVAL_TYPE_NONE.
> + * @i should be a declared integer type.
> + */
> +#define for_each_key(i, keys)	\
> +	for (i = 0; (keys)[(i)].type != TRACEEVAL_TYPE_NONE; (i)++)

Nit, the brackets in [(i)] make the parenthesis unneeded. That is, [i]
should always work. But I may be wrong ;-) I just can't think of
something that could make it fail.

> +
> +/** A key-value pair */

Again, just use "/* " and not "/** "

> +struct entry {
> +	union traceeval_data	*keys;
> +	union traceeval_data	*vals;
> +};
> +
> +/** A table of key-value entries */
> +struct hist_table {
> +	struct entry	*map;
> +	size_t		nr_entries;
> +};
> +
> +/** Histogram */
> +struct traceeval {
> +	struct traceeval_type		*def_keys;
> +	struct traceeval_type		*def_vals;

The "def" here keeps making me think it's "default" when it is
"defined". Let's call it "key_types" and "val_types".

That will make it much more obvious to what they are.

Also, I think it's a good idea that we keep track of the size. And then
we don't even need to keep the NONE around.

	size_t				nr_key_types;
	size_t				nr_val_types;

> +	struct hist_table		*hist;
> +};
> +
> +/** Iterate over results of histogram */
> +struct traceeval_iterator {};  // TODO

Looking at this series, it's better to not include these TODOs, and
just add the functions in the later patches.

If a function you add calls one of these function, then you can add the
stub functions. But you don't need to add the stubs if nothing is
referencing them.

> +
> +/**

If you use the kerneldoc comment format, do all the real formatting. That is:

/**
 * function_name - one line desrciption
 * @parameter1: Describe parameter 1
 * @parameter2: Describe parameter 2
 *
 * Description of the body.
 *
 * If it returns a value, say what it returns an the end.
 */

> + * Print error message.
> + * Additional arguments are used with respect to fmt.
> + */
> +static void print_err(const char *fmt, ...)
> +{
> +	va_list ap;
> +
> +	va_start(ap, fmt);
> +	vfprintf(stderr, fmt, ap);
> +	va_end(ap);
> +	fprintf(stderr, "\n");
> +}
> +
> +// TODO
> +int traceeval_compare(struct traceeval *orig, struct traceeval *copy)
> +{
> +	return -1;
> +}
> +
> +/**

Not, static functions do not need to have the kernel doc layout (unless
you want to write one). They can just be a brief description. But then
use "/* " and not "/** ".

> + * Resize a struct traceeval_type array to a size of @size + 1.
> + *
> + * Returns a pointer to the resized array, or NULL if the provided pointer was
> + * freed to due lack of memory.

I would stress that this frees @defs.

 * Returns the pointer to the resized array or NULL if it failed to
 * allocate. On failure, it will free @defs and its contents.

> + */
> +static struct traceeval_type *type_realloc(struct traceeval_type *defs,
> +		size_t size)
> +{
> +	struct traceeval_type *tmp_defs = NULL;

Do not need to initialize it to NULL if you assign it right afterward.

Add a space between the declarations and the code.

> +	tmp_defs = realloc(defs,
> +			(size + 1) * sizeof(struct traceeval_type));
> +	if (!tmp_defs)
> +		goto fail_type_realloc;
> +	return tmp_defs;

Since there's only one error condition and it's right before the
return, remove the label and just do:

	if (tmp_defs)
		return tmp_defs;

	/* Failure, clean up and free defs */

Although, to be safe, I think we should make sure that the newly
allocated memory is zeroed out.

	if (tmp_defs) {
		memset(&tmp_defs[size], 0, sizeof(tmp_defs[size]));
		return tmp_defs;
	}

> +
> +fail_type_realloc:
> +	for (int i = 0; i < size; i++) {

Just FYI, my personal preference is that I always add the "int i" at
the top of the function. But it has recently been declared in the Linux
kernel community that, declaring iterator variables in loops is now
deemed OK to do (as you did above). So I need to start getting use to
this. In other words, keep the above ;-)

> +		if (defs[i].name)
> +			free(defs[i].name);
> +	}
> +	free(defs);
> +	return NULL;
> +}
> +
> +/**
> + * Clone traceeval_type array @defs to the heap. Must be terminated with
> + * an instance of type TRACEEVAL_TYPE_NONE.
> + * Returns NULL if @defs is NULL, or a name is not null terminated.
> + */
> +static struct traceeval_type *type_alloc(const struct traceeval_type *defs)

Let's change this to:

ssize_t type_alloc(const struct traceeval_type *defs, struct traceeval_type **copy)

and return the number of elements and set copy to the copied types.

> +{
> +	struct traceeval_type *new_defs = NULL;
> +	char *name;
> +	size_t size = 0;

Note, use upside-down x-mas tree format for the above too:

	struct traceeval_type *new_defs = NULL;
	size_t size = 0;
	char *name;

I'm thinking we should just scan the array first to get the size. Then
we don't even need the above realloc. We just allocate once after we
know the size.

Again, we should just ignore the NONE type. No need to copy it.

> +
> +	// Empty def is represented with single TRACEEVAL_TYPE_NONE
> +	if (defs == NULL) {
> +		if (!(new_defs = calloc(1, sizeof(struct traceeval_type))))
> +			goto fail_type_alloc;
> +		new_defs->type = TRACEEVAL_TYPE_NONE;
> +		return new_defs;
> +	}

That is, we can do:

	for (size = 0; defs && defs[size].type != TRACEEVAL_TYE_NONE; size++)
		;

	if (size)
		new_defs = calloc(size, sizeof(*new_defs));

Then do the below loop with;

	for (int i; i < size; i++) {


> +
> +	for_each_key(size, defs) {

I just realized if we keep track of the number of keys/vals, we don't
need the for_each_key() macro.

> +		// Resize heap defs and clone
> +		new_defs = type_realloc(new_defs, size);
> +		if (!new_defs)
> +			goto fail_type_alloc;

So we could get rid of the above realloc.

> +
> +		// copy current def data to new_def
> +		new_defs[size] = defs[size];
> +		new_defs[size].name = NULL;
> +		// copy name to heap if it's not NULL or type NONE
> +		if (defs[size].type != TRACEEVAL_TYPE_NONE) {
> +			name = NULL;
> +			if (!defs[size].name)
> +				goto fail_type_alloc_name;
> +
> +			name = strdup(defs[size].name);
> +			if (!name)
> +				goto fail_type_alloc_name;
> +			new_defs[size].name = name;
> +		}
> +	}
> +
> +	// append array terminator
> +	new_defs = type_realloc(new_defs, size);
> +	if (!new_defs)
> +		goto fail_type_alloc;
> +	new_defs[size].type = TRACEEVAL_TYPE_NONE;

And we can get rid of the above too.

> +
> +	return new_defs;

Add a space between returns and failure labels.

> +fail_type_alloc:
> +	if (defs[size].name)
> +		print_err("failed to allocate memory for traceeval_type %s", defs[size].name);
> +	print_err("failed to allocate memory for traceeval_type index %zu", size);
> +	return NULL;
> +
> +fail_type_alloc_name:
> +	if (defs[size].name)
> +		print_err("failed to allocate name for traceeval_type %s", defs[size].name);
> +
> +	print_err("failed to allocate name for traceeval_type index %zu", size);
> +	return NULL;
> +}
> +
> +/**
> + * Create a new histogram over the given keys and values.
> + */
> +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> +				 const struct traceeval_type *vals)
> +{
> +	struct traceeval *teval;
> +	char *err_msg;
> +	struct traceeval_type type = {
> +		.type = TRACEEVAL_TYPE_NONE
> +	};

Note, the above ordering is fine, as the upside-down x-mas tree format
does not apply to arrays that are defined.

Also, let's change the above to:

	struct traceeval_type none_type[] = {
		{ .type = TRACEEVAL_TYPE_NONE }
	};


Both the name change to "none_type" to be more descriptive of what it
is, and also make it an array so we don't need to pass the address
below. But it's really moot if we decide to not add NONE types.

> +
> +	if (!keys)
> +		return NULL;
> +
> +	if (keys->type == TRACEEVAL_TYPE_NONE) {
> +		err_msg = "keys cannot start with type TRACEEVAL_TYPE_NONE";
> +		goto fail_eval_init_unalloced;
> +	}
> +
> +	teval = calloc(1, sizeof(struct traceeval));

My personal preference is to use the variable for the size. I just find
it to be more robust and less error prone, especially if you
accidentally pick the wrong type.

	teval = calloc(1, sizeof(*teval));

> +	if (!teval) {
> +		err_msg = "failed to allocate memory for traceeval instance";
> +		goto fail_eval_init_unalloced;

BTW, you don't need to make the labels so verbose.

		goto fail_nofree;

would be good enough.

> +	}
> +
> +	teval->def_keys = type_alloc(keys);
> +	if (!teval->def_keys) {
> +		err_msg = "failed to allocate user defined keys";
> +		goto fail_eval_init;

and this just:

		goto fail;

> +	}
> +
> +	// if vals is NULL, alloc single type NONE

BTW, since I follow Linux kernel style, // comments are usually looked
down upon. It's better to use

	/* if vals is NULL then just alloc a single NONE type */

> +	if (vals)
> +		teval->def_vals = type_alloc(vals);
> +	else
> +		teval->def_vals = type_alloc(&type);

		teval->def_vals = type_alloc(none_type);

But here we would really just do:

		teval->nr_val_types = 0;

> +
> +	if (!teval->def_vals) {
> +		err_msg = "failed to allocate user defined values";
> +		goto fail_eval_init;
> +	}
> +
> +	teval->hist = calloc(1, sizeof(struct hist_table));
> +	if (!teval->hist) {
> +		err_msg = "failed to allocate memory for histogram";
> +		goto fail_eval_init;
> +	}
> +	teval->hist->nr_entries = 0;

The calloc() above makes the clearing of nr_entries redundant.

> +
> +	return teval;
> +fail_eval_init:
> +	traceeval_release(teval);
> +	/* fall-through */

This isn't a switch statement, no need for the above comment.

> +
> +fail_eval_init_unalloced:
> +	print_err(err_msg);
> +	return NULL;
> +}

Let's nuke all the below functions for this patch and just add the
functions in the later patches.

-- Steve


> +
> +// TODO
> +void traceeval_release(struct traceeval *teval)
> +{
> +
> +}
> +
> +// TODO
> +int traceeval_insert(struct traceeval *teval,
> +		     const union traceeval_data *keys,
> +		     const union traceeval_data *vals)
> +{
> +	return -1;
> +}
> +
> +// TODO
> +int traceeval_query(struct traceeval *teval,
> +		    const union traceeval_data *keys,
> +		    union traceeval_data * const *results)
> +{
> +	return 0;
> +}
> +
> +// TODO
> +int traceeval_find_key(struct traceeval *teval, const char *field)
> +{
> +	return -1;
> +}
> +
> +// TODO
> +int traceeval_find_val(struct traceeval *teval, const char *field)
> +{
> +	return -1;
> +}
> +
> +// TODO
> +void traceeval_results_release(struct traceeval *teval,
> +			       const union traceeval_data *results)
> +{
> +
> +}
> +
> +// TODO
> +struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval)
> +{
> +	return NULL;
> +}
> +
> +// TODO
> +int traceeval_iterator_sort(struct traceeval_iterator *iter,
> +			    const char *sort_field, int level, bool ascending)
> +{
> +	return -1;
> +}
> +
> +// TODO
> +int traceeval_iterator_next(struct traceeval_iterator *iter,
> +			    const union traceeval_data **keys)
> +{
> +	return 0;
> +}
> +
> +// TODO
> +void traceeval_keys_release(struct traceeval_iterator *iter,
> +			    const union traceeval_data *keys)
> +{
> +
> +}
> +
> +// TODO
> +int traceeval_stat(struct traceeval *teval, const union traceeval_data *keys,
> +		   const char *field, struct traceeval_stat *stat)
> +{
> +	return -1;
> +}

Re: [PATCH 3/5] histograms: traceeval release

[Steven Rostedt]

On Fri, 28 Jul 2023 15:04:38 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> traceeval_release() deconstructs a given struct traceeval instance. It
> frees any data allocated to the heap within the union traceeval_data
> arrays of entries to the histogram, and the names allocated for the
> struct traceeval_type key-value definitions.
> 
> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  src/histograms.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 85 insertions(+), 2 deletions(-)
> 
> diff --git a/src/histograms.c b/src/histograms.c
> index 13830e4..f46a0e0 100644
> --- a/src/histograms.c
> +++ b/src/histograms.c
> @@ -209,10 +209,93 @@ fail_eval_init_unalloced:
>  	return NULL;
>  }
>  
> -// TODO
> -void traceeval_release(struct traceeval *teval)
> +/**
> + * Deallocate array of traceeval_type's, which must be terminated by
> + * TRACEEVAL_TYPE_NONE.
> + */
> +static void type_release(struct traceeval_type *defs)

So if we keep track of the number of defs, we should just pass in the
size. And ignore the NONE.

>  {
> +	size_t i = 0;
> +
> +	if (!defs)
> +		return;
> +
> +	for_each_key(i, defs) {
> +		if (defs[i].name)
> +			free(defs[i].name);
> +	}
> +
> +	free(defs);
> +}
> +
> +/**
> + * Deallocate any specified dynamic data in @data.
> + */
> +static void clean_data(union traceeval_data *data, struct traceeval_type *def) +{
> +	size_t i = 0;
> +
> +	if (!data || !def)
> +		return;
> +
> +	for_each_key(i, def) {
> +		switch (def[i].type) {
> +		case TRACEEVAL_TYPE_STRING:
> +			if (data[i].string)
> +				free(data[i].string);
> +			break;
> +		case TRACEEVAL_TYPE_DYNAMIC:
> +			def[i].dyn_release(data[i].dyn_data, &def[i]);

Note, it should be OK if the dynamic event does not have a release
function. This should be:

			if (def[i].dyn_release)
				def[i].dyn_release(data[i].dyn_data, &def[i]);

> +			break;
> +		default:
> +			break;
> +		}
> +	}
> +}
>  
> +/**
> + * Deallocate all possible data stored within the entry.

Use the word "Free" and not "Deallocate". This goes for all other
places.

-- Steve

> + */
> +static void clean_entry(struct entry *entry, struct traceeval *teval)
> +{
> +	if (!entry)
> +		return;
> +
> +	// deallocate dynamic traceeval_data
> +	clean_data(entry->keys, teval->def_keys);
> +	clean_data(entry->vals, teval->def_vals);
> +	free(entry->keys);
> +	free(entry->vals);
> +}
> +
> +/**
> + * Deallocate the hist_table allocated to a traceeval instance.
> + */
> +static void hist_table_release(struct traceeval *teval)
> +{
> +	struct hist_table *hist = teval->hist;
> +
> +	if (!hist)
> +		return;
> +
> +	for (size_t i = 0; i < hist->nr_entries; i++) {
> +		clean_entry(&hist->map[i], teval);
> +	}
> +	free(hist->map);
> +	free(hist);
> +}
> +
> +/**
> + * Deallocate a traceeval instance.
> + */
> +void traceeval_release(struct traceeval *teval)
> +{
> +	if (teval) {
> +		hist_table_release(teval);
> +		type_release(teval->def_keys);
> +		type_release(teval->def_vals);
> +		free(teval);
> +	}
>  }
>  
>  // TODO

Re: [PATCH 4/5] histograms: traceeval compare

[Steven Rostedt]

On Fri, 28 Jul 2023 15:04:39 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:
> +/**
> + * Return 0 if @orig and @copy are the same, 1 otherwise.
> + */
> +static int compare_traceeval_type(struct traceeval_type *orig,
> +		struct traceeval_type *copy)
> +{
> +	int o_name_null;
> +	int c_name_null;
> +
> +	// same memory/null
> +	if (orig == copy)
> +		return 0;

You say memory/null, so I'm assuming one can be NULL. Then you need to add;

	if (!!orig != !!copy)
		return 1;

Little C trick above ;-)

> +
> +	size_t i = 0;
> +	do {
> +		if (orig[i].type != copy[i].type)
> +			return 1;
> +		if (orig[i].type == TRACEEVAL_TYPE_NONE)
> +			return 0;
> +		if (orig[i].flags != copy[i].flags)
> +			return 1;
> +		if (orig[i].id != copy[i].id)
> +			return 1;
> +		if (orig[i].dyn_release != copy[i].dyn_release)
> +			return 1;
> +		if (orig[i].dyn_cmp != copy[i].dyn_cmp)
> +			return 1;
> +
> +		// make sure both names are same type
> +		o_name_null = !orig[i].name;
> +		c_name_null = !copy[i].name;
> +		if (o_name_null != c_name_null)
> +			return 1;
> +		if (o_name_null)
> +			continue;

You can replace the above with:

		if (!!orig[i].name != !!copy[i].name)
			return 1;
		if (!orig[i].name)
			continue;

And get rid of the o_name_null and c_name_null variables.

> +		if (strcmp(orig[i].name, copy[i].name) != 0)
> +			return 1;
> +	} while (orig[i++].type != TRACEEVAL_TYPE_NONE);
> +
> +	return 0;
> +}
> +
> +/**
> + * Return 0 if @orig and @copy are the same, 1 if @orig is greater than @copy,
> + * -1 for the other way around, and -2 on error.
> + */
> +static int compare_traceeval_data(union traceeval_data *orig,
> +		const union traceeval_data *copy, struct traceeval_type *type)
> +{
> +	if (!orig || !copy)
> +		return 1;

So if either is NULL then you return 1?

> +
> +	switch (type->type) {
> +	case TRACEEVAL_TYPE_NONE:
> +		/* There is no corresponding traceeval_data for TRACEEVAL_TYPE_NONE */
> +		return -2;
> +
> +	case TRACEEVAL_TYPE_STRING:
> +		int i = strcmp(orig->string, copy->string);

I do prefer the "int i" above for this case.


> +		if (!i)
> +			return 0;
> +		if (i > 0)
> +			return 1;
> +		return -1;

Again, the above can be replaced with:

		if (i < 0)
			return -1;

		return i > 0;
or even:
		return !!i;


> +
> +	case TRACEEVAL_TYPE_NUMBER:
> +		compare_numbers_return(orig->number, copy->number);
> +
> +	case TRACEEVAL_TYPE_NUMBER_64:
> +		compare_numbers_return(orig->number_64, copy->number_64);
> +
> +	case TRACEEVAL_TYPE_NUMBER_32:
> +		compare_numbers_return(orig->number_32, copy->number_32);
> +
> +	case TRACEEVAL_TYPE_NUMBER_16:
> +		compare_numbers_return(orig->number_16, copy->number_16);
> +
> +	case TRACEEVAL_TYPE_NUMBER_8:
> +		compare_numbers_return(orig->number_8, copy->number_8);
> +
> +	case TRACEEVAL_TYPE_DYNAMIC:
> +		return type->dyn_cmp(orig->dyn_data, copy->dyn_data, type);
> +
> +	default:
> +		print_err("%d is out of range of enum traceeval_data_type", type->type);
> +		return -2;
> +	}
> +}
> +
> +/**
> + * Compare arrays fo union traceeval_data's with respect to @def.

   "fo"?

> + *
> + * Return 0 if @orig and @copy are the same, 1 if not, and -1 on error.
> + */
> +static int compare_traceeval_data_set(union traceeval_data *orig,
> +		const union traceeval_data *copy, struct traceeval_type *def)
> +{
> +	int i = 0;
> +	int check;
> +
> +	// compare data arrays
> +	for_each_key(i, def) {
> +		if ((check = compare_traceeval_data(&orig[i], &copy[i], &def[i])))
> +			goto fail_compare_data_set;

Let's make the labels less verbose.

> +	}
> +
> +	return 0;
> +fail_compare_data_set:
> +	if (check == -2)
> +		return -1;
> +	return 1;

	return check == -2 ? -1; 1;

> +}
> +
> +/**
> + * Return 0 if @orig and @copy are the same, 1 if not, and -1 on error.
> + */
> +static int compare_entries(struct entry *orig, struct entry *copy,
> +		struct traceeval *teval)
> +{
> +	int check;
> +
> +	// compare keys
> +	check = compare_traceeval_data_set(orig->keys, copy->keys,
> +			teval->def_keys);
> +	if (check)
> +		return check;
> +
> +	// compare values
> +	check = compare_traceeval_data_set(orig->vals, copy->vals,
> +			teval->def_vals);
> +	return check;
> +}
> +
> +/**
> + * Return 0 if struct hist_table of @orig and @copy are the same, 1 if not,
> + * and -1 on error.
> + */
> +static int compare_hist(struct traceeval *orig, struct traceeval *copy)
> +{
> +	struct hist_table *o_hist = orig->hist;
> +	struct hist_table *c_hist = copy->hist;
> +	int cnt = !(o_hist->nr_entries == c_hist->nr_entries);

Add space between declarations and code.

> +	if (cnt)
> +		return 1;

Why the cnt variable?

	if (o_hist->nr_entries != c_hist->nr_entries)
		return 1;

> +
> +	for (size_t i = 0; i < o_hist->nr_entries; i++) {
> +		// cmp each entry

The above comment is as useful as: /* add one to x */ x++;

No need for it.

> +		compare_entries(&o_hist->map[i], &c_hist->map[i], orig);
> +	}
> +	return 0;	

White space attached to the end of the above line.

If you do a git show of each of your commits, it should show you white
space errors like that with a block red color.

> +}
> +
> +/**
> + * Return 0 if @orig and @copy are the same, 1 if not, -1 if error.
> + */
>  int traceeval_compare(struct traceeval *orig, struct traceeval *copy)
>  {
> -	return -1;
> +	if ((!orig) || (!copy))
> +		return -1;
> +
> +	int keys = compare_traceeval_type(orig->def_keys, copy->def_keys);
> +	int vals = compare_traceeval_type(orig->def_vals, copy->def_vals);
> +	int hists = compare_hist(orig, copy);

First, you need to add the above as declarations. Following Linux
kernel styling, only variables for "for" loops may be declared locally
like that. Otherwise, we prefer old style C.

Also, can't any of the above return an error? The below doesn't catch
that.

	if (keys < 0 || vals < 0 || hists < 0)
		return -1;

 ?

> +
> +	return (keys || vals || hists);

return is not a function. No need for the parenthesis.

	return keys || vals || hists;

>  }
>  
>  /**

-- Steve

Re: [PATCH 5/5] histograms: Add struct traceeval unit tests

[Steven Rostedt]

On Fri, 28 Jul 2023 15:04:40 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> Add unit tests for traceeval_init(), traceeval_release(), and
> traceeval_compare() to check edge cases and ensure the interface is
> functional.

Just nits about extra white space that git showed me.

> 
> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  utest/.gitignore        |   1 +
>  utest/Makefile          |  35 +++++++
>  utest/eval-test.h       |  10 ++
>  utest/eval-utest.c      |  27 +++++
>  utest/traceeval-utest.c | 222 ++++++++++++++++++++++++++++++++++++++++
>  5 files changed, 295 insertions(+)
>  create mode 100644 utest/.gitignore
>  create mode 100644 utest/Makefile
>  create mode 100644 utest/eval-test.h
>  create mode 100644 utest/eval-utest.c
>  create mode 100644 utest/traceeval-utest.c
> 
> diff --git a/utest/.gitignore b/utest/.gitignore
> new file mode 100644
> index 0000000..ca0ac10
> --- /dev/null
> +++ b/utest/.gitignore
> @@ -0,0 +1 @@
> +eval-utest
> diff --git a/utest/Makefile b/utest/Makefile
> new file mode 100644
> index 0000000..955f91e
> --- /dev/null
> +++ b/utest/Makefile
> @@ -0,0 +1,35 @@
> +# SPDX-License-Identifier: MIT
> +
> +include $(src)/scripts/utils.mk
> +
> +bdir := $(obj)/utest
> +eval_lib := $(obj)/lib/libtraceeval.a
> +
> +TARGETS = $(bdir)/eval-utest
> +
> +OBJS := eval-utest.o
> +OBJS += traceeval-utest.o
> +
> +LIBS += -lcunit				\
> +	-ldl				\
> +	$(eval_lib)
> +
> +OBJS := $(OBJS:%.o=$(bdir)/%.o)
> +
> +$(bdir):
> +	@mkdir -p $(bdir)
> +
> +$(OBJS): | $(bdir)
> +
> +$(bdir)/eval-utest: $(OBJS) $(eval_lib)
> +	$(Q)$(do_app_build)
> +
> +$(bdir)/%.o: %.c
> +	$(Q)$(call do_fpic_compile)
> +
> +-include .*.d
> +
> +test: $(TARGETS)
> +
> +clean:
> +	$(Q)$(call do_clean,$(TARGETS) $(bdir)/*.o $(bdir)/.*.d)
> diff --git a/utest/eval-test.h b/utest/eval-test.h
> new file mode 100644
> index 0000000..f3372e8
> --- /dev/null
> +++ b/utest/eval-test.h
> @@ -0,0 +1,10 @@
> +/* SPDX-License-Identifier: MIT */
> +/*
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +#ifndef _EVAL_UTEST_H_
> +#define _EVAL_UTEST_H_
> +
> +void test_traceeval_lib(void);
> +
> +#endif /* _EVAL_UTEST_H_ */
> diff --git a/utest/eval-utest.c b/utest/eval-utest.c
> new file mode 100644
> index 0000000..771a0c4
> --- /dev/null
> +++ b/utest/eval-utest.c
> @@ -0,0 +1,27 @@
> +
> +// SPDX-License-Identifier: MIT
> +/*
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +#include <stdio.h>
> +#include <stdlib.h>
> +
> +#include <CUnit/CUnit.h>
> +#include <CUnit/Basic.h>
> +
> +#include "eval-test.h"
> +
> +int main(int argc, char **argv)
> +{
> +	if (CU_initialize_registry() != CUE_SUCCESS) {
> +		printf("Test registry cannot be initialized\n");
> +		return EXIT_FAILURE;
> +	}
> +
> +	test_traceeval_lib();
> +
> +	CU_basic_set_mode(CU_BRM_VERBOSE);
> +	CU_basic_run_tests();
> +	CU_cleanup_registry();
> +	return EXIT_SUCCESS;
> +}
> diff --git a/utest/traceeval-utest.c b/utest/traceeval-utest.c
> new file mode 100644
> index 0000000..2bcb4b9
> --- /dev/null
> +++ b/utest/traceeval-utest.c
> @@ -0,0 +1,222 @@
> +// SPDX-License-Identifier: MIT
> +/*
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +
> +#include <string.h>
> +#include <stdio.h>
> +#include <stdbool.h>
> +#include <CUnit/CUnit.h>
> +#include <CUnit/Basic.h>
> +
> +#include <histograms.h>
> +
> +#define TRACEEVAL_SUITE		"traceeval library"
> +#define TRACEEVAL_SUCCESS	0
> +#define TRACEEVAL_FAILURE	-1
> +#define TRACEEVAL_NOT_SAME	1
> +
> +/**
> + * Test traceeval_init(), traceeval_release(), and traceeval_compare() with
> + * NULL values.
> + */
> +void test_eval_null(void)
> +{
> +	// set up
> +	char *name = "test null";
> +	enum traceeval_data_type type = TRACEEVAL_TYPE_NONE;
> +	const struct traceeval_type test_data[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = name
> +		},
> +		{
> +			.type = type,
> +			.name = NULL
> +		}
> +	};
> +
> +	// test init
> +	struct traceeval *result_null = traceeval_init(NULL, NULL);
> +	struct traceeval *result_key = traceeval_init(test_data, NULL);
> +	struct traceeval *result_val = traceeval_init(NULL, test_data);
> +	

Extra space at the end of the above.
> +	// analyze init
> +	CU_ASSERT(!result_null);
> +	CU_ASSERT(result_key != NULL);
> +	CU_ASSERT(!result_val);
> +
> +	// release
> +	traceeval_release(NULL);
> +	traceeval_release(result_key);
> +}
> +
> +/**
> + * Use provided data to test traceeval_init(), traceeval_compare(), and
> + * traceeval_release().
> + */
> +void test_eval_base(const struct traceeval_type *keys1,
> +		const struct traceeval_type *vals1,
> +		const struct traceeval_type *keys2,
> +		const struct traceeval_type *vals2,
> +		bool init_not_null1, bool init_not_null2,
> +		int compare_result)
> +{
> +	struct traceeval *init1;
> +	struct traceeval *init2;
> +	int result;
> +
> +	// test init
> +	init1 = traceeval_init(keys1, vals1);
> +	init2 = traceeval_init(keys2, vals2);
> +
> +	result = init1 != NULL;
> +	if (init_not_null1) {
> +		CU_ASSERT(result);
> +	} else {
> +		CU_ASSERT(!result);
> +	}
> +
> +	result = init2 != NULL;
> +	if (init_not_null2) {
> +		CU_ASSERT(result);
> +	} else {
> +		CU_ASSERT(!result);
> +	}
> +
> +	// test compare
> +	result = traceeval_compare(init1, init2);
> +	
> +	// analyze compare
> +	CU_ASSERT(result == compare_result);
> +	

Extra space above.

> +	// release
> +	traceeval_release(init1);
> +	traceeval_release(init2);
> +}
> +
> +/**
> + * Test traceeval_init(), traceeval_release(), and traceeval_compare() with
> + * TRACEEVAL_TYPE_NONE.
> + */
> +void test_eval_none(void)
> +{
> +	// set up
> +	char *name = "test none";
> +	char *name2 = "test none (some)";
> +	const struct traceeval_type test_data_none[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = name
> +		}
> +	};
> +	const struct traceeval_type test_data_some[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = name2
> +		},
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = NULL
> +		}
> +	};
> +
> +	test_eval_base(test_data_some, test_data_none, test_data_some,
> +			test_data_none, true, true, TRACEEVAL_SUCCESS);
> +	test_eval_base(test_data_none, test_data_none, test_data_some,
> +			test_data_none, false, true, TRACEEVAL_FAILURE);
> +	test_eval_base(test_data_none, test_data_none, test_data_none,
> +			test_data_none, false, false, TRACEEVAL_FAILURE);
> +}
> +
> +/**
> + * Test traceeval_init() and traceeval_release() with equivalent values.
> + */
> +void test_eval_same(void)
> +{
> +	// set up
> +	char *name = "test data";
> +	char *name2 = "test done";
> +	const struct traceeval_type test_data[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = name
> +		},
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = name2
> +		}
> +	};
> +	

EXtra space above.

> +	test_eval_base(test_data, test_data, test_data, test_data, true, true,
> +			TRACEEVAL_SUCCESS);
> +}
> +
> +/**
> + * Test traceeval_init() and traceeval_release() with non-equivalent values.
> + */
> +void test_eval_not_same(void)
> +{
> +	const struct traceeval_type test_data1[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = "test data 1"
> +		},
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = NULL
> +		}
> +	};
> +	const struct traceeval_type test_data2[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = "test data 2"
> +		},
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = NULL
> +		}
> +	};
> +
> +	// type 1 key diff
> +	test_eval_base(test_data2, test_data1, test_data1, test_data1, true,
> +			true, TRACEEVAL_NOT_SAME);
> +	// type 1 data diff
> +	test_eval_base(test_data1, test_data2, test_data1, test_data1, true,
> +			true, TRACEEVAL_NOT_SAME);
> +	// type 2 key diff
> +	test_eval_base(test_data1, test_data1, test_data2, test_data1, true,
> +			true, TRACEEVAL_NOT_SAME);
> +	// type 2 data diff
> +	test_eval_base(test_data1, test_data1, test_data1, test_data2, true,
> +			true, TRACEEVAL_NOT_SAME);
> +}
> +
> +/**
> + * Tests the traceeval_init() and traceeval_release() functions.
> + */
> +void test_eval(void)
> +{
> +	test_eval_null();
> +	test_eval_none();
> +	test_eval_same();
> +	test_eval_not_same();
> +}
> +
> +/**
> + * Register tests with CUnit.
> + */
> +void test_traceeval_lib(void)
> +{
> +	CU_pSuite suite = NULL;
> +	

Extra space above.

> +	// set up suite
> +	suite = CU_add_suite(TRACEEVAL_SUITE, NULL, NULL);
> +	if (suite == NULL) {
> +		fprintf(stderr, "Suite %s cannot be created\n", TRACEEVAL_SUITE);
> +		return;
> +	}
> +
> +	// add tests to suite
> +	CU_add_test(suite, "Test traceeval alloc and release", test_eval);
> +}

-- Steve

Re: [PATCH 1/5] histograms: initial histograms interface

[Stevie Alvarez]

On Fri, Jul 28, 2023 at 04:25:00PM -0400, Steven Rostedt wrote:
> 
> Hi Stevie,
> 
> Thanks for sending this. Note, you can use "--cover-letter" to "git
> send-email" that will add a cover letter "[PATCH 0/5}" that you can use
> to explain the patch set. All other patches will be a reply to that
> email. It's usually a requirement for most patch series.
> 
> On Fri, 28 Jul 2023 15:04:36 -0400
> Stevie Alvarez <stevie.6strings@gmail.com> wrote:
> 
> > From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> > 
> > Initial header file for libtraceeval's histogram API. The interface
> > provides a simple way of aggregating trace data and reading through said
> > data.
> > 
> > Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> > ---
> >  include/histograms.h | 340 +++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 340 insertions(+)
> >  create mode 100644 include/histograms.h
> > 
> > diff --git a/include/histograms.h b/include/histograms.h
> 
> Note, this should be called traceeval.h
> 
> If you want to call it this temporarily until we remove the old one
> that's fine.
> 
> > new file mode 100644
> > index 0000000..b8cd53e
> > --- /dev/null
> > +++ b/include/histograms.h
> > @@ -0,0 +1,340 @@
> > +/* SPDX-License-Identifier: MIT */
> > +/*
> > + * libtraceeval histogram interface.
> > + *
> > + * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
> > + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> > + */
> > +#ifndef __LIBTRACEEVAL_HIST_H__
> > +#define __LIBTRACEEVAL_HIST_H__
> > +
> > +#include <stdlib.h>
> > +#include <stddef.h>
> > +#include <stdbool.h>
> > +
> > +// Data definition interfaces
> > +
> > +/** Data type distinguishers */
> 
> So there's a specific comment structure called "kernel doc" that starts
> with "/**" and has some rules. This doesn't need that format, so you
> only need to use "/* " to not confuse to make it look like kernel doc.
> 
> /* Data type distinguishers */
> 
> > +enum traceeval_data_type {
> > +	TRACEEVAL_TYPE_NONE,
> > +	TRACEEVAL_TYPE_STRING,
> > +	TRACEEVAL_TYPE_NUMBER,
> > +	TRACEEVAL_TYPE_NUMBER_64,
> > +	TRACEEVAL_TYPE_NUMBER_32,
> > +	TRACEEVAL_TYPE_NUMBER_16,
> > +	TRACEEVAL_TYPE_NUMBER_8,
> > +	TRACEEVAL_TYPE_DYNAMIC
> > +};
> > +
> > +/** Statistics specification flags */
> 
> Same here.
> 
> > +enum traceeval_flags {
> > +	TRACEEVAL_FL_SIGNED	= (1 << 0),
> > +	TRACEEVAL_FL_STATS	= (1 << 1)
> 
> As I think about this more, I think we should just do "stats" for all
> numbered values. It doesn't really make sense for keys.

So get rid of the "stats" flag altogether and do it by default for numbered
values? And what do you mean when you say it doesn't make sense for keys? A
key could be a numeric value too, but you might be meaning something else; I'm
not quite following.

> 
> But we should still have TRACEEVAL_FL_TIMESTAMP (see traceeval_insert()
> below)
> 
> > +};
> > +
> > +/**
> 
> And here.
> 
> > + * Trace data entry for a traceeval histogram
> > + * Constitutes keys and values.
> > + */
> > +union traceeval_data {
> > +	char				*string;
> > +	struct traceeval_dynamic	*dyn_data;
> > +	unsigned long			number;
> > +	unsigned char			number_8;
> > +	unsigned short			number_16;
> > +	unsigned int			number_32;
> > +	unsigned long long		number_64;
> > +};
> > +
> > +/**
> > + * Describes a struct traceeval_data instance
> 
> So this structure could have a kernel doc comment. Which would look like:
> 
> /**
>  * struct traceeval_type - Describes the type of a traceevent_data instance
>  * @type: The enum type that describes the traceeval_data
>  * @name: The string name of the traceveval_data
>  * @flags: flags to describe the traceeval_data
>  * @id: User specified identifier
>  * @dyn_release: For dynamic types called on release (ignored for other types)
>  * @dyn_cmp: A way to compare dynamic types (ignored for other types)
>  *
>  * The typeeval_type structure defines expectations for a corresponding
>  * traceeval_data instance for a traceeval histogram instance. Used to
>  * describe both keys and values.
>  *
>  * The @id field is an optional value in case the user has multiple struct
>  *
>  * The traceeval_type instances with @type fields set to
>  * TRACEEVAL_TYPE_DYNAMIC, which each relate to distinct user defined
>  * struct traceeval_dynamic 'sub-types'.
>  *
>  * For flexibility, @dyn_cmp() and @dyn_release() take a struct
>  * traceeval_type instance. This allows the user to distingush between
>  * different sub-types of struct traceeeval_dynamic within a single
>  * callback function by examining the @id field. This is not a required
>  * approach, merely one that is accomodated.
>  *
>  * @dyn_cmp() is used to compare two struct traceeval_dynamic instances when a
>  * corresponding struct traceeval_type is reached with its type field set to
>  * TRACEEVAL_TYPE_DYNAMIC. It should return 0 on equality, 1 if the first
>  * argument is greater than the second, -1 for the otherway around, and -2 on
>  * error.
>  *
>  * dyn_release() is used during traceeval_release() to release a union
>  * traceeval_data's struct traceeval_dynamic field when the corresponding
>  * traceeval_type type is set to TRACEEVAL_TYPE_DYNAMIC.
>  */
> 
> > + * Defines expectations for a corresponding traceeval_data instance for a
> > + * traceeval histogram instance. Used to describe both keys and values.
> > + *
> > + * The id field is an optional value in case the user has multiple struct
> > + * traceeval_type instances with type fields set to TRACEEVAL_TYPE_DYNAMIC,
> > + * which each relate to distinct user defined struct traceeval_dynamic
> > + * 'sub-types'.
> > + * For flexibility, dyn_cmp() and dyn_release() take a struct traceeval_type
> > + * instance. This allows the user to distingush between different sub-types of
> > + * struct traceeeval_dynamic within a single callback function by examining the
> > + * id field. This is not a required approach, merely one that is accomodated.
> > + *
> > + * dyn_cmp() is used to compare two struct traceeval_dynamic instances when a
> > + * corresponding struct traceeval_type is reached with its type field set to
> > + * TRACEEVAL_TYPE_DYNAMIC. It should return 0 on equality, 1 if the first
> > + * argument is greater than the second, -1 for the otherway around, and -2 on
> > + * error.
> > + *
> > + * dyn_release() is used during traceeval_release() to release a union
> > + * traceeval_data's struct traceeval_dynamic field when the corresponding
> > + * traceeval_type type is set to TRACEEVAL_TYPE_DYNAMIC.
> > + */
> > +struct traceeval_type {
> > +	enum traceeval_data_type	type;
> > +	char				*name;
> > +	size_t				flags;
> > +	size_t				id;
> 
> > +	void (*dyn_release)(struct traceeval_dynamic *, struct traceeval_type *);
> > +	int (*dyn_cmp)(struct traceeval_dynamic *, struct traceeval_dynamic *,
> > +			struct traceeval_type *);
> 
> You can still index the function pointers:
> 
> 	void 				(*dyn_release)(struct traceeval_dynamic *,
> 						 struct traceeval_type *);
> 	int 				(*dyn_cmp)(struct traceeval_dynamic *, struct traceeval_dynamic *,
> 						struct traceeval_type *);
> 
> Better yet, use typedefs:
> 
> typedef void (*traceeval_dyn_release_fn)(struct traceeval_dynamic *, struct traceeval_type *);
> typedef void (*traceeval_dyn_cmp_fn)(struct traceeval_dynamic *, struct traceeval_dynamic *,
> 						struct traceeval_type *);
> 
> 
> struct traceeval_type {
> 	[..]
> 	traceveal_dyn_release_fn	dyn_release;
> 	traceeval_dyn_cmp_fn		dyn_cmp;
> };
> 
> Which looks much better.
> 
> > +};
> > +
> > +/** Storage for atypical data */
> 
> This could have kernel doc too:
> 
> /**
>  * struct traceeval_dynamic - storage for dynamic traceeval_types
>  * @size: The size of the dynamic type
>  * @data: The pointer to the data of the dynamic type.
>  */
> 
> > +struct traceeval_dynamic {
> > +	size_t		size;
> > +	void		*data;
> > +};
> > +
> > +// Histogram interfaces
> 
> I don't think we should call it "histograms" as it can create
> histograms, but calling it a histogram limits its possibilities.
> 
> // traceeval interfaces
> 
> > +
> > +/** Histogram */
> 
> Remove the above comment. The below is fine without a comment.
> 
> > +struct traceeval;
> > +
> > +/**
> > + * traceeval_init - create a traceeval descriptor
> 
> Remove all the double asterisks.
> 
>  /**
>   * traceeval_init
>   [..]
> 
> Instead of
>   * * ...
> 
> Also, for header files, functions do not need kernel doc comments. They
> should exist in the C files where the function is described.
> 
> > + * @keys: Defines the keys of the "histogram"
> 
>  * @keys: Defines the keys to differentiate traceeval entries
> 
> > + * @vals: Defines the vals of the "histogram"
> 
>  * @ vals: Defines values attached to entries differentiated by @keys.
> 
> > + *
> > + * The caller still owns @keys and @vals. The caller is responsible for any
> > + * necessary clean up of @keys and @vals.
> 
> I would instead say:
> 
>  * The @keys and @vals passed in are copied for internal use.
> 
> The "const" in the prototype and the above statement should be good
> enough, where the user of this interface should understand the rest.
> 
> > + * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
> > + * the name field must be either a null-terminated string or NULL. For
> 
> The above is incorrect, as it can't be NULL.
> 
> > + * members of type TRACEEVAL_TYPE_NONE, the name is ignored.
> 
> Note, the below paragraph should come first. You want to describe what
> the function does before going into any constraints of the function.
> 
> > + * The @keys and @vals define how the traceeval instance will be populated.
> > + * The @keys will be used by traceeval_query() to find an instance within
> > + * the "historgram". Note, both the @keys and @vals array must end with:
> > + * { .type = TRACEEVAL_TYPE_NONE }.
> > + *
> > + * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
> > + * define the values of the histogram to be empty. If @keys is NULL or starts
> > + * with { .type = TRACEEVAL_TYPE_NONE }, it is treated as an error to ensure 
> > + * the histogram is valid.
> 
> The last sentence about @keys should just state:
> 
>  * @keys must be populated with at least one element that is not
>  * TRACEEVAL_TYPE_NONE.
> 
> > + *
> > + * Retruns the descriptor on success, or NULL on error.
> > + */
> > +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> > +		const struct traceeval_type *vals);
> > +
> > +/**
> > + * traceeval_release - release a traceeval descriptor
> 
> Again, replace all the double asterisks with single ones.
> 
> > + * @teval: An instance of traceeval returned by traceeval_init()
> > + *
> > + * When the caller of traceeval_init() is done with the returned @teval,
> > + * it must call traceeval_release().
> > + * This does not release any dynamically allocated data inserted by
> > + * the user, although it will call any dyn_release() functions provided by
> > + * the user from traceeval_init().
> 
> The above is contradictory, as it does release user dynamically
> allocated data by calling the dyn_release() function.
> 
>  * This cleans up all internally allocated data of @teval and will call
>  * the corresponding dyn_release() functions that were registered for
>  * the TRACEEVAL_TYPE_DYNAMIC type keys and values.
> 
> 
> > + */
> > +void traceeval_release(struct traceeval *teval);
> > +
> > +/**
> > + * traceeval_insert - Insert an item into the traceeval descriptor
> > + * @teval: The descriptor to insert into
> > + * @keys: The list of keys that defines what is being inserted.
> > + * @vals: The list of values that defines what is being inserted.
> > + *
> 
> > + * Any dynamically allocated data is still owned by the caller; the
> > + * responsibility of deallocating it lies on the caller.
> 
> The above can be removed.
> 
> > + * For all elements of @keys and @vals that correspond to a struct
> > + * traceeval_type of type TRACEEVAL_TYPE_STRING, the string field must be set
> > + * to either a null-terminated string or NULL.
> > + * The @keys is an array that holds the data in the order of the keys
> > + * passed into traceeval_init(). That is, if traceeval_init() had
> > + * keys = { { .type = TRACEEVAL_STRING }, { .type = TRACEEVAL_NUMBER_8 },
> > + * { .type = TRACEEVAL_NONE } }; then the @keys array passed in must
> > + * be a string (char *) followed by a 8 byte number (char). The @keys
> > + * and @vals are only examined to where it expects data. That is,
> > + * if the traceeval_init() keys had 3 items where the first two was defining
> > + * data, and the last one was the TRACEEVAL_TYPE_NONE, then the @keys
> > + * here only needs to be an array of 2, inserting the two items defined
> > + * by traceeval_init(). The same goes for @vals.
> 
> So the above really doesn't explain what the function does.
> 
>  * This function will insert an entry defined by @keys and @vals into
>  * the traceeval instance. The array of @keys and @vals must match that
>  * of what was added to the corresponding parameters of
>  * traceeval_init() that created @teval. No checking is performed, if
>  * there is a mismatch in array length, it will result in undefined behavior.
>  * The types of the @keys and @vals must also match the types used for
>  * the corresponding parameters to traceeval_init().
>  *
>  * If an entry already exists that matches the @keys, then strings and
>  * values will be overwritten by the current values and the old values
>  * will be discarded. For number values, the max, min, total and count
>  * will be recorded. If an entry in @vals has TRACEEVAL_FL_TIMESTAMP
>  * set in its corresponding traceeval_type descriptor, then it will be
>  * used to timestamp the max and min values.

So only values can be a timestamp? Or at least timestamp metrics can
only be gathered for values? This goes back to my comment above about
the flags.

-- Stevie

> 
> The description of traceeval_type and traceeval_data mappings as you
> did before, can be saved for the man pages.
> 
> > + *
> > + * Returns 0 on success, and -1 on error.
> > + */
> > +int traceeval_insert(struct traceeval *teval,
> > +		const union traceeval_data *keys,
> > +		const union traceeval_data *vals);
> > +
> > +/**
> > + * traceeval_compare - Check equality between two traceeval instances
> > + * @orig: The first traceeval instance
> > + * @copy: The second traceeval instance
> > + *
> > + * This compares the values of the key definitions, value definitions, and
> > + * inserted data between @orig and @copy in order. It does not compare
> > + * by memory address, except for struct traceeval_type's dyn_release() and
> > + * dyn_cmp() fields.
> > + *
> > + * Returns 0 if @orig and @copy are the same, 1 if not, and -1 on error.
> > + */
> > +int traceeval_compare(struct traceeval *orig, struct traceeval
> > *copy); +
> 
> I'm not really sure what a traceveal_compare() would be used for
> externally. I think we can just remove it? Leave it internally if you
> use it for CUTESTs.
> 
> > +// interface to queuery traceeval
> > +
> > +/**
> > + * traceeval_query - Find the last instance defined by the keys
> > + * @teval: The descriptor to search from
> > + * @keys: A list of data to look for
> > + * @results: A pointer to where to place the results (if found)
> > + *
> > + * This does a lookup for an instance within the traceeval data.
> > + * The @keys is an array defined by the keys declared in traceeval_init().
> > + * The @keys will return an item that had the same keys when it was
> 
>  The @results will ... ?
> 
> > + * inserted by traceeval_insert(). The @keys here follow the same rules
> > + * as the keys for traceeval_insert().
> 
> I know that you copied most of this from my document, but I don't even
> know what the above means ;-)
> 
> Anyway, this patch should be folded piece by piece in the other patches
> as you add the functions as you implement them. That is, you should
> have 4 patches not 5 (this one should no longer exist, as the changes
> will go in the patches that implement each).
> 
> -- Steve
> 
> 
> > + *
> > + * Note, when the caller is done with @results, it must call
> > + * traceeval_results_release() on it.
> > + *
> > + * Returns 1 if found, 0 if not found, and -1 on error.
> > + */
> > +int traceeval_query(struct traceeval *teval,
> > +		const union traceeval_data *keys,
> > +		union traceeval_data * const *results);
> > +
> > +/** Field name/descriptor for number of hits */
> > +#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
> > +
> > +/**
> > + * traceeval_find_key - find the index of a key
> > + * @teval: The descriptor to find the key for
> > + * @field: The name of the key to return the index for
> > + *
> > + * As the order of how keys are defined by traceeval_init(), it
> > + * is important to know what index they are for when dealing with
> > + * the other functions.
> > + *
> > + * Returns the index of the key with @field as the name.
> > + * Return -1 if not found.
> > + */
> > +int traceeval_find_key(struct traceeval *teval, const char *field);
> > +
> > +/**
> > + * traceeval_find_val - find the index of a value
> > + * @teval: The descriptor to find the value for
> > + * @field: The name of the value to return the index for
> > + *
> > + * As the order of how values are defined by traceeval_init(), it
> > + * is important to know what index they are for when dealing with
> > + * the results array from traceeval_query(). In order to facilitate
> > + * this, traceeval_find_val() will return the index for a given
> > + * @field so that the caller does not have to keep track of it.
> > + *
> > + * Returns the index of the value with @field as the name that can be
> > + * used to index the @results array from traceeval_query().
> > + * Return -1 if not found.
> > + */
> > +int traceeval_find_val(struct traceeval *teval, const char *field);
> > +
> > +/**
> > + * traceeval_results_release - Release the results return by traceeval_query()
> > + * @teval: The descriptor used in traceeval_query()
> > + * @results: The results returned by traceeval_query()
> > + *
> > + * The @results returned by traceeval_query() is owned by @teval, and
> > + * how it manages it is implementation specific. The caller should not
> > + * worry about it. When the caller of traceeval_query() is done with
> > + * the @results, it must call traceeval_results_release() on it to
> > + * allow traceeval to clean up its references.
> > + */
> > +void traceeval_results_release(struct traceeval *teval,
> > +		const union traceeval_data *results);
> > +
> > +// Result iterator/histogram dump interfaces
> > +
> > +/** Iterator over aggregated data */
> > +struct traceeval_iterator;
> > +
> > +/**
> > + * traceeval_iterator_get - get an iterator to read the data from traceeval
> > + * @teval: The descriptor to read from
> > + *
> > + * This returns a descriptor that can be used to interate through all the
> > + * data within @teval.
> > + *
> > + * Returns the iterator on success, NULL on error.
> > + */
> > +struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval);
> > +/**
> > + * traceeval_iterator_sort - Set how the iterator is sorted
> > + * @iter: The iterator to set the sorting
> > + * @sort_field: The field (defined by traceeval_init) to sort by.
> > + * @level: The level of sorting.
> > + * @ascending: Set to true to sort ascending order, or false to descending
> > + *
> > + * Sets how the iterator shall be sorted. @sort_field is the field to sort
> > + * by and may be the name of either a key or a value.
> > + *
> > + * The @level should be zero the first time this is called to define the main sort
> > + * field. If secondary sorting is to be done, then this function should be called
> > + * again with @level as 1. For more levels of sorting just call this function
> > + * for each level incrementing level each time. Note, if a level is missed,
> > + * then this will return an error and sorting will not be done for that level.
> > + *
> > + * Returns 0 on success, -1 or error (including missing a level).
> > + */
> > +int traceeval_iterator_sort(struct traceeval_iterator *iter,
> > +		const char *sort_field, int level, bool ascending);
> > +
> > +/**
> > + * traceeval_iterator_next - Iterate through the data of a traceeval descriptor
> > + * @iter: The iterator that holds the location and sorting of the data
> > + * @keys: The current set of keys of the traceeval the @iter is sorting through
> > + *
> > + * This will iterate through all the data of the traceeval descriptor held
> > + * by @iter in the sort pattern defined by traceeval_iterator_sort().
> > + * The @keys return is same as the data used to populate the data passed into
> > + * traceveal_insert(). When the caller is done with @keys, it should be passed
> > + * into traceeval_keys_release().
> > + *
> > + * Returns 1 if it returned an item, 0 if there's no more data to return,
> > + * and -1 on error.
> > + */
> > +int traceeval_iterator_next(struct traceeval_iterator *iter,
> > +		const union traceeval_data **keys);
> > +
> > +/**
> > + * traceeval_keys_release - Release the keys return by
> > traceeval_iterator_next()
> > + * @iter: The iterator used in traceeval_iterator_next().
> > + * @keys: The results returned by traceeval_iterator_next()
> > + *
> > + * The @keys returned by traceeval_iterator_next() is owned by
> > @iter, and
> > + * how it manages it is implementation specific. The caller should
> > not
> > + * worry about it. When the caller of traceeval_iterator_next() is
> > done with
> > + * the @keys, it must call traceeval_keys_release() on it to
> > + * allow traceeval to clean up its references.
> > + */
> > +void traceeval_keys_release(struct traceeval_iterator *iter,
> > +		const union traceeval_data *keys);
> > +
> > +// Statistic extraction
> > +
> > +/** Statistics about a given field */
> > +struct traceeval_stat {
> > +	unsigned long long	max;
> > +	unsigned long long	min;
> > +	unsigned long long	total;
> > +	unsigned long long	avg;
> > +	unsigned long long	std;
> > +};
> > +
> > +/**
> > + * traceeval_stat - Extract stats from a field marke a
> > TRACEEVAL_FL_STATS
> > + * @teval: The descriptor holding the traceeval information
> > + * @keys: The list of keys to find the instance to get the stats on
> > + * @field: The field to retreive the stats for
> > + * @stats: A structure to place the stats into.
> > + *
> > + * This returns the stats of the the given @field. Note, if @field
> > was
> > + * not marked for recording stats with the TRACEEVAL_FL_STATS flag,
> > or
> > + * if no instance is found that has @keys, this will return an error.
> > + *
> > + * Returns 0 on success, -1 on error.
> > + */
> > +int traceeval_stat(struct traceeval *teval, const union
> > traceeval_data *keys,
> > +		const char *field, struct traceeval_stat *stat);
> > +
> > +#endif /* __LIBTRACEEVAL_HIST_H__ */
> > +
> 

Re: [PATCH 1/5] histograms: initial histograms interface

[Steven Rostedt]

On Mon, 31 Jul 2023 16:53:53 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> >   
> > > +enum traceeval_flags {
> > > +	TRACEEVAL_FL_SIGNED	= (1 << 0),
> > > +	TRACEEVAL_FL_STATS	= (1 << 1)  
> > 
> > As I think about this more, I think we should just do "stats" for all
> > numbered values. It doesn't really make sense for keys.  
> 
> So get rid of the "stats" flag altogether and do it by default for numbered
> values? And what do you mean when you say it doesn't make sense for keys? A
> key could be a numeric value too, but you might be meaning something else; I'm
> not quite following.

We don't need to keep the stats (max, min, total, count) for keys because
they are unique instances. Each instance should be the same. That is, the
stats are being kept for an instance of the histogram. And an instance is
defined by a unique key. If we keep stats on keys, the max and min will be
the same, and the total will just be max * hitcount.

I would also not keep stats if something is marked as a TIMESTAMP, as a
TIMESTAMP is just a place in time and not something that we need to keep
max min on. Hmm, I guess we could do it, and that would give us the time of
the first and last hit of that particular instance. Yeah, let's keep the
stats even on TIMESTAMPS. Doesn't hurt (even if total doesn't make sense).

> 
> > 
> > But we should still have TRACEEVAL_FL_TIMESTAMP (see traceeval_insert()
> > below)
> >   
> > > +};
> > > +
> > > +/**  
> > 

[..]

> >  * This function will insert an entry defined by @keys and @vals into
> >  * the traceeval instance. The array of @keys and @vals must match that
> >  * of what was added to the corresponding parameters of
> >  * traceeval_init() that created @teval. No checking is performed, if
> >  * there is a mismatch in array length, it will result in undefined behavior.
> >  * The types of the @keys and @vals must also match the types used for
> >  * the corresponding parameters to traceeval_init().
> >  *
> >  * If an entry already exists that matches the @keys, then strings and
> >  * values will be overwritten by the current values and the old values
> >  * will be discarded. For number values, the max, min, total and count
> >  * will be recorded. If an entry in @vals has TRACEEVAL_FL_TIMESTAMP
> >  * set in its corresponding traceeval_type descriptor, then it will be
> >  * used to timestamp the max and min values.  
> 
> So only values can be a timestamp? Or at least timestamp metrics can
> only be gathered for values? This goes back to my comment above about
> the flags.

Yeah, I think it only makes sense for a timestamp to be a value. As keys
are all shown, and we only keep track of a bit of a value. A timestamp is
used to know when a particular key was hit, so it doesn't make sense to be
a key.

-- Steve

Re: [PATCH 1/5] histograms: initial histograms interface

[Ross Zwisler]

On Fri, Jul 28, 2023 at 03:04:36PM -0400, Stevie Alvarez wrote:
> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> Initial header file for libtraceeval's histogram API. The interface
> provides a simple way of aggregating trace data and reading through said
> data.
> 
> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  include/histograms.h | 340 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 340 insertions(+)
>  create mode 100644 include/histograms.h
> 
> diff --git a/include/histograms.h b/include/histograms.h
> new file mode 100644
> index 0000000..b8cd53e
> --- /dev/null
> +++ b/include/histograms.h
> @@ -0,0 +1,340 @@
> +/* SPDX-License-Identifier: MIT */
> +/*
> + * libtraceeval histogram interface.
> + *
> + * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +#ifndef __LIBTRACEEVAL_HIST_H__
> +#define __LIBTRACEEVAL_HIST_H__
> +
> +#include <stdlib.h>
> +#include <stddef.h>
> +#include <stdbool.h>
> +
> +// Data definition interfaces
> +
> +/** Data type distinguishers */
> +enum traceeval_data_type {
> +	TRACEEVAL_TYPE_NONE,
> +	TRACEEVAL_TYPE_STRING,
> +	TRACEEVAL_TYPE_NUMBER,
> +	TRACEEVAL_TYPE_NUMBER_64,
> +	TRACEEVAL_TYPE_NUMBER_32,
> +	TRACEEVAL_TYPE_NUMBER_16,
> +	TRACEEVAL_TYPE_NUMBER_8,
> +	TRACEEVAL_TYPE_DYNAMIC
> +};
> +
> +/** Statistics specification flags */
> +enum traceeval_flags {
> +	TRACEEVAL_FL_SIGNED	= (1 << 0),
> +	TRACEEVAL_FL_STATS	= (1 << 1)
> +};
> +
> +/**
> + * Trace data entry for a traceeval histogram
> + * Constitutes keys and values.
> + */
> +union traceeval_data {
> +	char				*string;
> +	struct traceeval_dynamic	*dyn_data;
> +	unsigned long			number;
> +	unsigned char			number_8;
> +	unsigned short			number_16;
> +	unsigned int			number_32;
> +	unsigned long long		number_64;
> +};
> +
> +/**
> + * Describes a struct traceeval_data instance
> + * Defines expectations for a corresponding traceeval_data instance for a
> + * traceeval histogram instance. Used to describe both keys and values.
> + *
> + * The id field is an optional value in case the user has multiple struct
> + * traceeval_type instances with type fields set to TRACEEVAL_TYPE_DYNAMIC,
> + * which each relate to distinct user defined struct traceeval_dynamic
> + * 'sub-types'.
> + * For flexibility, dyn_cmp() and dyn_release() take a struct traceeval_type
> + * instance. This allows the user to distingush between different sub-types of
                                        distinguish

Lots of small spelling errors in comments, I'll leave the rest to you. :)
Check out ":help spell" in vim/neovim for a spell checker that works on
text in comments.

> + * struct traceeeval_dynamic within a single callback function by examining the
> + * id field. This is not a required approach, merely one that is accomodated.
> + *
> + * dyn_cmp() is used to compare two struct traceeval_dynamic instances when a
> + * corresponding struct traceeval_type is reached with its type field set to
> + * TRACEEVAL_TYPE_DYNAMIC. It should return 0 on equality, 1 if the first
> + * argument is greater than the second, -1 for the otherway around, and -2 on
> + * error.
> + *
> + * dyn_release() is used during traceeval_release() to release a union
> + * traceeval_data's struct traceeval_dynamic field when the corresponding
> + * traceeval_type type is set to TRACEEVAL_TYPE_DYNAMIC.
> + */
> +struct traceeval_type {
> +	enum traceeval_data_type	type;
> +	char				*name;
> +	size_t				flags;
> +	size_t				id;
> +	void (*dyn_release)(struct traceeval_dynamic *, struct traceeval_type *);
> +	int (*dyn_cmp)(struct traceeval_dynamic *, struct traceeval_dynamic *,
> +			struct traceeval_type *);
> +};
> +
> +/** Storage for atypical data */
> +struct traceeval_dynamic {
> +	size_t		size;
> +	void		*data;
> +};

I think this should be up higher in the header, above it's first use in
traceeval_data?

> +
> +// Histogram interfaces
> +
> +/** Histogram */
> +struct traceeval;
> +
> +/**
> + * traceeval_init - create a traceeval descriptor
> + * @keys: Defines the keys of the "histogram"
> + * @vals: Defines the vals of the "histogram"
> + *
> + * The caller still owns @keys and @vals. The caller is responsible for any
> + * necessary clean up of @keys and @vals.
> + * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
> + * the name field must be either a null-terminated string or NULL. For
> + * members of type TRACEEVAL_TYPE_NONE, the name is ignored.
> + * The @keys and @vals define how the traceeval instance will be populated.
> + * The @keys will be used by traceeval_query() to find an instance within
> + * the "historgram". Note, both the @keys and @vals array must end with:
> + * { .type = TRACEEVAL_TYPE_NONE }.
> + *
> + * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
> + * define the values of the histogram to be empty. If @keys is NULL or starts
> + * with { .type = TRACEEVAL_TYPE_NONE }, it is treated as an error to ensure 
> + * the histogram is valid.
> + *
> + * Retruns the descriptor on success, or NULL on error.
> + */
> +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> +		const struct traceeval_type *vals);
> +
> +/**
> + * traceeval_release - release a traceeval descriptor
> + * @teval: An instance of traceeval returned by traceeval_init()
> + *
> + * When the caller of traceeval_init() is done with the returned @teval,
> + * it must call traceeval_release().
> + * This does not release any dynamically allocated data inserted by
> + * the user, although it will call any dyn_release() functions provided by
> + * the user from traceeval_init().
> + */
> +void traceeval_release(struct traceeval *teval);
> +
> +/**
> + * traceeval_insert - Insert an item into the traceeval descriptor
> + * @teval: The descriptor to insert into
> + * @keys: The list of keys that defines what is being inserted.
> + * @vals: The list of values that defines what is being inserted.
> + *
> + * Any dynamically allocated data is still owned by the caller; the
> + * responsibility of deallocating it lies on the caller.
> + * For all elements of @keys and @vals that correspond to a struct
> + * traceeval_type of type TRACEEVAL_TYPE_STRING, the string field must be set
> + * to either a null-terminated string or NULL.
> + * The @keys is an array that holds the data in the order of the keys
> + * passed into traceeval_init(). That is, if traceeval_init() had
> + * keys = { { .type = TRACEEVAL_STRING }, { .type = TRACEEVAL_NUMBER_8 },
> + * { .type = TRACEEVAL_NONE } }; then the @keys array passed in must
> + * be a string (char *) followed by a 8 byte number (char). The @keys
> + * and @vals are only examined to where it expects data. That is,
> + * if the traceeval_init() keys had 3 items where the first two was defining
> + * data, and the last one was the TRACEEVAL_TYPE_NONE, then the @keys
> + * here only needs to be an array of 2, inserting the two items defined
> + * by traceeval_init(). The same goes for @vals.
> + *
> + * Returns 0 on success, and -1 on error.
> + */
> +int traceeval_insert(struct traceeval *teval,
> +		const union traceeval_data *keys,
> +		const union traceeval_data *vals);
> +
> +/**
> + * traceeval_compare - Check equality between two traceeval instances
> + * @orig: The first traceeval instance
> + * @copy: The second traceeval instance
> + *
> + * This compares the values of the key definitions, value definitions, and
> + * inserted data between @orig and @copy in order. It does not compare
> + * by memory address, except for struct traceeval_type's dyn_release() and
> + * dyn_cmp() fields.
> + *
> + * Returns 0 if @orig and @copy are the same, 1 if not, and -1 on error.
> + */
> +int traceeval_compare(struct traceeval *orig, struct traceeval *copy);
> +
> +// interface to queuery traceeval
> +
> +/**
> + * traceeval_query - Find the last instance defined by the keys
> + * @teval: The descriptor to search from
> + * @keys: A list of data to look for
> + * @results: A pointer to where to place the results (if found)
> + *
> + * This does a lookup for an instance within the traceeval data.
> + * The @keys is an array defined by the keys declared in traceeval_init().
> + * The @keys will return an item that had the same keys when it was
> + * inserted by traceeval_insert(). The @keys here follow the same rules
> + * as the keys for traceeval_insert().
> + *
> + * Note, when the caller is done with @results, it must call
> + * traceeval_results_release() on it.
> + *
> + * Returns 1 if found, 0 if not found, and -1 on error.
> + */
> +int traceeval_query(struct traceeval *teval,
> +		const union traceeval_data *keys,
> +		union traceeval_data * const *results);

I don't think this 'union traceeval_data * const *results' will give you what
you want.  This will pass in an immutable pointer to 'results', and you need
to modify the 'results' pointer.

I think you actually want 'const union traceeval_data **results' because you
want a mutable pointer (results) to immutable results data.  This is similar
to the 'const union traceeval_data **keys' arg given to

> int traceeval_iterator_next(struct traceeval_iterator *iter,
> 		const union traceeval_data **keys);

and will match the const placement on the 'results' argument to 

> void traceeval_results_release(struct traceeval *teval,
> 		const union traceeval_data *results);

With the current code there is no way to get results back out of this
function, because 'results' is const and you won't be able to set the pointer.

Here is a quick example I made to make sure I understood the various
placements of const in this arg list. :)

--- >8 ---
#include <stdio.h>
#include <stdlib.h>
#include <histogram.h>

int traceeval_query(struct traceeval *teval,
		const union traceeval_data *keys,
		const union traceeval_data **results)
{
	union traceeval_data *r = malloc(sizeof r);
	*results = r;
	r->string = "foo";
}

void main()
{
	const union traceeval_data *results;

	traceeval_query(NULL, NULL, &results);
	printf("results->name:'%s'\n", results->string);

        // This next line would fail because the results data itself is
        // read-only.
//	results->name = "bar";
}
--- >8 ---

> +
> +/** Field name/descriptor for number of hits */
> +#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
> +
> +/**
> + * traceeval_find_key - find the index of a key
> + * @teval: The descriptor to find the key for
> + * @field: The name of the key to return the index for
> + *
> + * As the order of how keys are defined by traceeval_init(), it
> + * is important to know what index they are for when dealing with
> + * the other functions.
> + *
> + * Returns the index of the key with @field as the name.
> + * Return -1 if not found.
> + */
> +int traceeval_find_key(struct traceeval *teval, const char *field);
> +
> +/**
> + * traceeval_find_val - find the index of a value
> + * @teval: The descriptor to find the value for
> + * @field: The name of the value to return the index for
> + *
> + * As the order of how values are defined by traceeval_init(), it
> + * is important to know what index they are for when dealing with
> + * the results array from traceeval_query(). In order to facilitate
> + * this, traceeval_find_val() will return the index for a given
> + * @field so that the caller does not have to keep track of it.
> + *
> + * Returns the index of the value with @field as the name that can be
> + * used to index the @results array from traceeval_query().
> + * Return -1 if not found.
> + */
> +int traceeval_find_val(struct traceeval *teval, const char *field);
> +
> +/**
> + * traceeval_results_release - Release the results return by traceeval_query()
> + * @teval: The descriptor used in traceeval_query()
> + * @results: The results returned by traceeval_query()
> + *
> + * The @results returned by traceeval_query() is owned by @teval, and
> + * how it manages it is implementation specific. The caller should not
> + * worry about it. When the caller of traceeval_query() is done with
> + * the @results, it must call traceeval_results_release() on it to
> + * allow traceeval to clean up its references.
> + */
> +void traceeval_results_release(struct traceeval *teval,
> +		const union traceeval_data *results);
> +
> +// Result iterator/histogram dump interfaces
> +
> +/** Iterator over aggregated data */
> +struct traceeval_iterator;
> +
> +/**
> + * traceeval_iterator_get - get an iterator to read the data from traceeval
> + * @teval: The descriptor to read from
> + *
> + * This returns a descriptor that can be used to interate through all the
> + * data within @teval.
> + *
> + * Returns the iterator on success, NULL on error.
> + */
> +struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval);
> +
> +/**
> + * traceeval_iterator_sort - Set how the iterator is sorted
> + * @iter: The iterator to set the sorting
> + * @sort_field: The field (defined by traceeval_init) to sort by.
> + * @level: The level of sorting.
> + * @ascending: Set to true to sort ascending order, or false to descending
> + *
> + * Sets how the iterator shall be sorted. @sort_field is the field to sort
> + * by and may be the name of either a key or a value.
> + *
> + * The @level should be zero the first time this is called to define the main sort
> + * field. If secondary sorting is to be done, then this function should be called
> + * again with @level as 1. For more levels of sorting just call this function
> + * for each level incrementing level each time. Note, if a level is missed,
> + * then this will return an error and sorting will not be done for that level.
> + *
> + * Returns 0 on success, -1 or error (including missing a level).
> + */
> +int traceeval_iterator_sort(struct traceeval_iterator *iter,
> +		const char *sort_field, int level, bool ascending);
> +
> +/**
> + * traceeval_iterator_next - Iterate through the data of a traceeval descriptor
> + * @iter: The iterator that holds the location and sorting of the data
> + * @keys: The current set of keys of the traceeval the @iter is sorting through
> + *
> + * This will iterate through all the data of the traceeval descriptor held
> + * by @iter in the sort pattern defined by traceeval_iterator_sort().
> + * The @keys return is same as the data used to populate the data passed into
> + * traceveal_insert(). When the caller is done with @keys, it should be passed
> + * into traceeval_keys_release().
> + *
> + * Returns 1 if it returned an item, 0 if there's no more data to return,
> + * and -1 on error.
> + */
> +int traceeval_iterator_next(struct traceeval_iterator *iter,
> +		const union traceeval_data **keys);
> +
> +/**
> + * traceeval_keys_release - Release the keys return by traceeval_iterator_next()
> + * @iter: The iterator used in traceeval_iterator_next().
> + * @keys: The results returned by traceeval_iterator_next()
> + *
> + * The @keys returned by traceeval_iterator_next() is owned by @iter, and
> + * how it manages it is implementation specific. The caller should not
> + * worry about it. When the caller of traceeval_iterator_next() is done with
> + * the @keys, it must call traceeval_keys_release() on it to
> + * allow traceeval to clean up its references.
> + */
> +void traceeval_keys_release(struct traceeval_iterator *iter,
> +		const union traceeval_data *keys);
> +
> +// Statistic extraction
> +
> +/** Statistics about a given field */
> +struct traceeval_stat {
> +	unsigned long long	max;
> +	unsigned long long	min;
> +	unsigned long long	total;
> +	unsigned long long	avg;
> +	unsigned long long	std;
> +};
> +
> +/**
> + * traceeval_stat - Extract stats from a field marke a TRACEEVAL_FL_STATS
> + * @teval: The descriptor holding the traceeval information
> + * @keys: The list of keys to find the instance to get the stats on
> + * @field: The field to retreive the stats for
> + * @stats: A structure to place the stats into.
> + *
> + * This returns the stats of the the given @field. Note, if @field was
> + * not marked for recording stats with the TRACEEVAL_FL_STATS flag, or
> + * if no instance is found that has @keys, this will return an error.
> + *
> + * Returns 0 on success, -1 on error.
> + */
> +int traceeval_stat(struct traceeval *teval, const union traceeval_data *keys,
> +		const char *field, struct traceeval_stat *stat);
> +
> +#endif /* __LIBTRACEEVAL_HIST_H__ */
> +
> -- 
> 2.41.0
> 

Re: [PATCH 1/5] histograms: initial histograms interface

[Steven Rostedt]

On Mon, 31 Jul 2023 18:36:24 -0600
Ross Zwisler <zwisler@google.com> wrote:

> On Fri, Jul 28, 2023 at 03:04:36PM -0400, Stevie Alvarez wrote:

> > +/**
> > + * traceeval_query - Find the last instance defined by the keys
> > + * @teval: The descriptor to search from
> > + * @keys: A list of data to look for
> > + * @results: A pointer to where to place the results (if found)
> > + *
> > + * This does a lookup for an instance within the traceeval data.
> > + * The @keys is an array defined by the keys declared in traceeval_init().
> > + * The @keys will return an item that had the same keys when it was
> > + * inserted by traceeval_insert(). The @keys here follow the same rules
> > + * as the keys for traceeval_insert().
> > + *
> > + * Note, when the caller is done with @results, it must call
> > + * traceeval_results_release() on it.
> > + *
> > + * Returns 1 if found, 0 if not found, and -1 on error.
> > + */
> > +int traceeval_query(struct traceeval *teval,
> > +		const union traceeval_data *keys,
> > +		union traceeval_data * const *results);  
> 
> I don't think this 'union traceeval_data * const *results' will give you what
> you want.  This will pass in an immutable pointer to 'results', and you need
> to modify the 'results' pointer.

That's my fault. I had it it that way in the code I had him base this off
of. In fact, in Boulder I said I need to check that because it may be
wrong. It was ;-)

Yes, Ross is right, it should be "const union traceeval_data **results".

Thanks Ross.

> 
> I think you actually want 'const union traceeval_data **results' because you
> want a mutable pointer (results) to immutable results data.  This is similar
> to the 'const union traceeval_data **keys' arg given to
> 
> > int traceeval_iterator_next(struct traceeval_iterator *iter,
> > 		const union traceeval_data **keys);  
> 
> and will match the const placement on the 'results' argument to 
> 
> > void traceeval_results_release(struct traceeval *teval,
> > 		const union traceeval_data *results);  
> 
> With the current code there is no way to get results back out of this
> function, because 'results' is const and you won't be able to set the pointer.
> 
> Here is a quick example I made to make sure I understood the various
> placements of const in this arg list. :)

I was going to do this too while in Boulder, but we got distracted :-p

-- Steve


> 
> --- >8 ---  
> #include <stdio.h>
> #include <stdlib.h>
> #include <histogram.h>
> 
> int traceeval_query(struct traceeval *teval,
> 		const union traceeval_data *keys,
> 		const union traceeval_data **results)
> {
> 	union traceeval_data *r = malloc(sizeof r);
> 	*results = r;
> 	r->string = "foo";
> }
> 
> void main()
> {
> 	const union traceeval_data *results;
> 
> 	traceeval_query(NULL, NULL, &results);
> 	printf("results->name:'%s'\n", results->string);
> 
>         // This next line would fail because the results data itself is
>         // read-only.
> //	results->name = "bar";
> }
> --- >8 ---  
> 
> > +
> > +/** Field name/descriptor for number of hits */
> > +#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
> > +
> > +/**
> > + * traceeval_find_key - find the index of a key
> > + * @teval: The descriptor to find the key for
> > + * @field: The name of the key to return the index for
> > + *
> > + * As the order of how keys are defined by traceeval_init(), it
> > + * is important to know what index they are for when dealing with
> > + * the other functions.
> > + *
> > + * Returns the index of the key with @field as the name.
> > + * Return -1 if not found.
> > + */
> > +int traceeval_find_key(struct traceeval *teval, const char *field);
> > +
> > +/**
> > + * traceeval_find_val - find the index of a value
> > + * @teval: The descriptor to find the value for
> > + * @field: The name of the value to return the index for
> > + *
> > + * As the order of how values are defined by traceeval_init(), it
> > + * is important to know what index they are for when dealing with
> > + * the results array from traceeval_query(). In order to facilitate
> > + * this, traceeval_find_val() will return the index for a given
> > + * @field so that the caller does not have to keep track of it.
> > + *
> > + * Returns the index of the value with @field as the name that can be
> > + * used to index the @results array from traceeval_query().
> > + * Return -1 if not found.
> > + */
> > +int traceeval_find_val(struct traceeval *teval, const char *field);
> > +
> > +/**
> > + * traceeval_results_release - Release the results return by traceeval_query()
> > + * @teval: The descriptor used in traceeval_query()
> > + * @results: The results returned by traceeval_query()
> > + *
> > + * The @results returned by traceeval_query() is owned by @teval, and
> > + * how it manages it is implementation specific. The caller should not
> > + * worry about it. When the caller of traceeval_query() is done with
> > + * the @results, it must call traceeval_results_release() on it to
> > + * allow traceeval to clean up its references.
> > + */
> > +void traceeval_results_release(struct traceeval *teval,
> > +		const union traceeval_data *results);
> > +
> > +// Result iterator/histogram dump interfaces
> > +
> > +/** Iterator over aggregated data */
> > +struct traceeval_iterator;
> > +
> > +/**
> > + * traceeval_iterator_get - get an iterator to read the data from traceeval
> > + * @teval: The descriptor to read from
> > + *
> > + * This returns a descriptor that can be used to interate through all the
> > + * data within @teval.
> > + *
> > + * Returns the iterator on success, NULL on error.
> > + */
> > +struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval);
> > +
> > +/**
> > + * traceeval_iterator_sort - Set how the iterator is sorted
> > + * @iter: The iterator to set the sorting
> > + * @sort_field: The field (defined by traceeval_init) to sort by.
> > + * @level: The level of sorting.
> > + * @ascending: Set to true to sort ascending order, or false to descending
> > + *
> > + * Sets how the iterator shall be sorted. @sort_field is the field to sort
> > + * by and may be the name of either a key or a value.
> > + *
> > + * The @level should be zero the first time this is called to define the main sort
> > + * field. If secondary sorting is to be done, then this function should be called
> > + * again with @level as 1. For more levels of sorting just call this function
> > + * for each level incrementing level each time. Note, if a level is missed,
> > + * then this will return an error and sorting will not be done for that level.
> > + *
> > + * Returns 0 on success, -1 or error (including missing a level).
> > + */
> > +int traceeval_iterator_sort(struct traceeval_iterator *iter,
> > +		const char *sort_field, int level, bool ascending);
> > +
> > +/**
> > + * traceeval_iterator_next - Iterate through the data of a traceeval descriptor
> > + * @iter: The iterator that holds the location and sorting of the data
> > + * @keys: The current set of keys of the traceeval the @iter is sorting through
> > + *
> > + * This will iterate through all the data of the traceeval descriptor held
> > + * by @iter in the sort pattern defined by traceeval_iterator_sort().
> > + * The @keys return is same as the data used to populate the data passed into
> > + * traceveal_insert(). When the caller is done with @keys, it should be passed
> > + * into traceeval_keys_release().
> > + *
> > + * Returns 1 if it returned an item, 0 if there's no more data to return,
> > + * and -1 on error.
> > + */
> > +int traceeval_iterator_next(struct traceeval_iterator *iter,
> > +		const union traceeval_data **keys);
> > +
> > +/**
> > + * traceeval_keys_release - Release the keys return by traceeval_iterator_next()
> > + * @iter: The iterator used in traceeval_iterator_next().
> > + * @keys: The results returned by traceeval_iterator_next()
> > + *
> > + * The @keys returned by traceeval_iterator_next() is owned by @iter, and
> > + * how it manages it is implementation specific. The caller should not
> > + * worry about it. When the caller of traceeval_iterator_next() is done with
> > + * the @keys, it must call traceeval_keys_release() on it to
> > + * allow traceeval to clean up its references.
> > + */
> > +void traceeval_keys_release(struct traceeval_iterator *iter,
> > +		const union traceeval_data *keys);
> > +
> > +// Statistic extraction
> > +
> > +/** Statistics about a given field */
> > +struct traceeval_stat {
> > +	unsigned long long	max;
> > +	unsigned long long	min;
> > +	unsigned long long	total;
> > +	unsigned long long	avg;
> > +	unsigned long long	std;
> > +};
> > +
> > +/**
> > + * traceeval_stat - Extract stats from a field marke a TRACEEVAL_FL_STATS
> > + * @teval: The descriptor holding the traceeval information
> > + * @keys: The list of keys to find the instance to get the stats on
> > + * @field: The field to retreive the stats for
> > + * @stats: A structure to place the stats into.
> > + *
> > + * This returns the stats of the the given @field. Note, if @field was
> > + * not marked for recording stats with the TRACEEVAL_FL_STATS flag, or
> > + * if no instance is found that has @keys, this will return an error.
> > + *
> > + * Returns 0 on success, -1 on error.
> > + */
> > +int traceeval_stat(struct traceeval *teval, const union traceeval_data *keys,
> > +		const char *field, struct traceeval_stat *stat);
> > +
> > +#endif /* __LIBTRACEEVAL_HIST_H__ */
> > +
> > -- 
> > 2.41.0
> >   

Re: [PATCH 1/5] histograms: initial histograms interface

[Stevie Alvarez]

On Fri, Jul 28, 2023 at 04:25:00PM -0400, Steven Rostedt wrote:
> 
> Hi Stevie,
> 
> Thanks for sending this. Note, you can use "--cover-letter" to "git
> send-email" that will add a cover letter "[PATCH 0/5}" that you can use
> to explain the patch set. All other patches will be a reply to that
> email. It's usually a requirement for most patch series.
> 
> On Fri, 28 Jul 2023 15:04:36 -0400
> Stevie Alvarez <stevie.6strings@gmail.com> wrote:
> 
> > From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> > 
> > Initial header file for libtraceeval's histogram API. The interface
> > provides a simple way of aggregating trace data and reading through said
> > data.
> > 
> > Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> > ---
> >  include/histograms.h | 340 +++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 340 insertions(+)
> >  create mode 100644 include/histograms.h
> > 
> > diff --git a/include/histograms.h b/include/histograms.h
> 
> Note, this should be called traceeval.h
> 
> If you want to call it this temporarily until we remove the old one
> that's fine.
> 
> > new file mode 100644
> > index 0000000..b8cd53e
> > --- /dev/null
> > +++ b/include/histograms.h
> > @@ -0,0 +1,340 @@
> > +/* SPDX-License-Identifier: MIT */
> > +/*
> > + * libtraceeval histogram interface.
> > + *
> > + * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
> > + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> > + */
> > +#ifndef __LIBTRACEEVAL_HIST_H__
> > +#define __LIBTRACEEVAL_HIST_H__
> > +
> > +#include <stdlib.h>
> > +#include <stddef.h>
> > +#include <stdbool.h>
> > +
> > +// Data definition interfaces
> > +
> > +/** Data type distinguishers */
> 
> So there's a specific comment structure called "kernel doc" that starts
> with "/**" and has some rules. This doesn't need that format, so you
> only need to use "/* " to not confuse to make it look like kernel doc.
> 
> /* Data type distinguishers */
> 
> > +enum traceeval_data_type {
> > +	TRACEEVAL_TYPE_NONE,
> > +	TRACEEVAL_TYPE_STRING,
> > +	TRACEEVAL_TYPE_NUMBER,
> > +	TRACEEVAL_TYPE_NUMBER_64,
> > +	TRACEEVAL_TYPE_NUMBER_32,
> > +	TRACEEVAL_TYPE_NUMBER_16,
> > +	TRACEEVAL_TYPE_NUMBER_8,
> > +	TRACEEVAL_TYPE_DYNAMIC
> > +};
> > +
> > +/** Statistics specification flags */
> 
> Same here.
> 
> > +enum traceeval_flags {
> > +	TRACEEVAL_FL_SIGNED	= (1 << 0),
> > +	TRACEEVAL_FL_STATS	= (1 << 1)
> 
> As I think about this more, I think we should just do "stats" for all
> numbered values. It doesn't really make sense for keys.
> 
> But we should still have TRACEEVAL_FL_TIMESTAMP (see traceeval_insert()
> below)
> 
> > +};
> > +
> > +/**
> 
> And here.
> 
> > + * Trace data entry for a traceeval histogram
> > + * Constitutes keys and values.
> > + */
> > +union traceeval_data {
> > +	char				*string;
> > +	struct traceeval_dynamic	*dyn_data;
> > +	unsigned long			number;
> > +	unsigned char			number_8;
> > +	unsigned short			number_16;
> > +	unsigned int			number_32;
> > +	unsigned long long		number_64;
> > +};
> > +
> > +/**
> > + * Describes a struct traceeval_data instance
> 
> So this structure could have a kernel doc comment. Which would look like:
> 
> /**
>  * struct traceeval_type - Describes the type of a traceevent_data instance
>  * @type: The enum type that describes the traceeval_data
>  * @name: The string name of the traceveval_data
>  * @flags: flags to describe the traceeval_data
>  * @id: User specified identifier
>  * @dyn_release: For dynamic types called on release (ignored for other types)
>  * @dyn_cmp: A way to compare dynamic types (ignored for other types)
>  *
>  * The typeeval_type structure defines expectations for a corresponding
>  * traceeval_data instance for a traceeval histogram instance. Used to
>  * describe both keys and values.
>  *
>  * The @id field is an optional value in case the user has multiple struct
>  *
>  * The traceeval_type instances with @type fields set to
>  * TRACEEVAL_TYPE_DYNAMIC, which each relate to distinct user defined
>  * struct traceeval_dynamic 'sub-types'.
>  *
>  * For flexibility, @dyn_cmp() and @dyn_release() take a struct
>  * traceeval_type instance. This allows the user to distingush between
>  * different sub-types of struct traceeeval_dynamic within a single
>  * callback function by examining the @id field. This is not a required
>  * approach, merely one that is accomodated.
>  *
>  * @dyn_cmp() is used to compare two struct traceeval_dynamic instances when a
>  * corresponding struct traceeval_type is reached with its type field set to
>  * TRACEEVAL_TYPE_DYNAMIC. It should return 0 on equality, 1 if the first
>  * argument is greater than the second, -1 for the otherway around, and -2 on
>  * error.
>  *
>  * dyn_release() is used during traceeval_release() to release a union
>  * traceeval_data's struct traceeval_dynamic field when the corresponding
>  * traceeval_type type is set to TRACEEVAL_TYPE_DYNAMIC.
>  */
> 
> > + * Defines expectations for a corresponding traceeval_data instance for a
> > + * traceeval histogram instance. Used to describe both keys and values.
> > + *
> > + * The id field is an optional value in case the user has multiple struct
> > + * traceeval_type instances with type fields set to TRACEEVAL_TYPE_DYNAMIC,
> > + * which each relate to distinct user defined struct traceeval_dynamic
> > + * 'sub-types'.
> > + * For flexibility, dyn_cmp() and dyn_release() take a struct traceeval_type
> > + * instance. This allows the user to distingush between different sub-types of
> > + * struct traceeeval_dynamic within a single callback function by examining the
> > + * id field. This is not a required approach, merely one that is accomodated.
> > + *
> > + * dyn_cmp() is used to compare two struct traceeval_dynamic instances when a
> > + * corresponding struct traceeval_type is reached with its type field set to
> > + * TRACEEVAL_TYPE_DYNAMIC. It should return 0 on equality, 1 if the first
> > + * argument is greater than the second, -1 for the otherway around, and -2 on
> > + * error.
> > + *
> > + * dyn_release() is used during traceeval_release() to release a union
> > + * traceeval_data's struct traceeval_dynamic field when the corresponding
> > + * traceeval_type type is set to TRACEEVAL_TYPE_DYNAMIC.
> > + */
> > +struct traceeval_type {
> > +	enum traceeval_data_type	type;
> > +	char				*name;
> > +	size_t				flags;
> > +	size_t				id;
> 
> > +	void (*dyn_release)(struct traceeval_dynamic *, struct traceeval_type *);
> > +	int (*dyn_cmp)(struct traceeval_dynamic *, struct traceeval_dynamic *,
> > +			struct traceeval_type *);
> 
> You can still index the function pointers:
> 
> 	void 				(*dyn_release)(struct traceeval_dynamic *,
> 						 struct traceeval_type *);
> 	int 				(*dyn_cmp)(struct traceeval_dynamic *, struct traceeval_dynamic *,
> 						struct traceeval_type *);
> 
> Better yet, use typedefs:
> 
> typedef void (*traceeval_dyn_release_fn)(struct traceeval_dynamic *, struct traceeval_type *);
> typedef void (*traceeval_dyn_cmp_fn)(struct traceeval_dynamic *, struct traceeval_dynamic *,
> 						struct traceeval_type *);
> 
> 
> struct traceeval_type {
> 	[..]
> 	traceveal_dyn_release_fn	dyn_release;
> 	traceeval_dyn_cmp_fn		dyn_cmp;
> };
> 
> Which looks much better.
> 
> > +};
> > +
> > +/** Storage for atypical data */
> 
> This could have kernel doc too:
> 
> /**
>  * struct traceeval_dynamic - storage for dynamic traceeval_types
>  * @size: The size of the dynamic type
>  * @data: The pointer to the data of the dynamic type.
>  */
> 
> > +struct traceeval_dynamic {
> > +	size_t		size;
> > +	void		*data;
> > +};
> > +
> > +// Histogram interfaces
> 
> I don't think we should call it "histograms" as it can create
> histograms, but calling it a histogram limits its possibilities.
> 
> // traceeval interfaces
> 
> > +
> > +/** Histogram */
> 
> Remove the above comment. The below is fine without a comment.
> 
> > +struct traceeval;
> > +
> > +/**
> > + * traceeval_init - create a traceeval descriptor
> 
> Remove all the double asterisks.
> 
>  /**
>   * traceeval_init
>   [..]
> 
> Instead of
>   * * ...
> 
> Also, for header files, functions do not need kernel doc comments. They
> should exist in the C files where the function is described.

As I've been updating the documentation, I keep thinking about this. Is
there a particular reason why the documentation should reside within the
C file rather than the header?
When I think about using libraries, my immediate thought is to look at the
interface/header file to see what functions are avaiable and what they do,
not the source. I'd think that the code would jumble up my view and make
it more cumbersome and distracting to read.
All that said, I'm not sure sure if that's not the standard way of doing
things here.

-- Stevie

> 
> > + * @keys: Defines the keys of the "histogram"
> 
>  * @keys: Defines the keys to differentiate traceeval entries
> 
> > + * @vals: Defines the vals of the "histogram"
> 
>  * @ vals: Defines values attached to entries differentiated by @keys.
> 
> > + *
> > + * The caller still owns @keys and @vals. The caller is responsible for any
> > + * necessary clean up of @keys and @vals.
> 
> I would instead say:
> 
>  * The @keys and @vals passed in are copied for internal use.
> 
> The "const" in the prototype and the above statement should be good
> enough, where the user of this interface should understand the rest.
> 
> > + * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
> > + * the name field must be either a null-terminated string or NULL. For
> 
> The above is incorrect, as it can't be NULL.
> 
> > + * members of type TRACEEVAL_TYPE_NONE, the name is ignored.
> 
> Note, the below paragraph should come first. You want to describe what
> the function does before going into any constraints of the function.
> 
> > + * The @keys and @vals define how the traceeval instance will be populated.
> > + * The @keys will be used by traceeval_query() to find an instance within
> > + * the "historgram". Note, both the @keys and @vals array must end with:
> > + * { .type = TRACEEVAL_TYPE_NONE }.
> > + *
> > + * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
> > + * define the values of the histogram to be empty. If @keys is NULL or starts
> > + * with { .type = TRACEEVAL_TYPE_NONE }, it is treated as an error to ensure 
> > + * the histogram is valid.
> 
> The last sentence about @keys should just state:
> 
>  * @keys must be populated with at least one element that is not
>  * TRACEEVAL_TYPE_NONE.
> 
> > + *
> > + * Retruns the descriptor on success, or NULL on error.
> > + */
> > +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> > +		const struct traceeval_type *vals);
> > +
> > +/**
> > + * traceeval_release - release a traceeval descriptor
> 
> Again, replace all the double asterisks with single ones.
> 
> > + * @teval: An instance of traceeval returned by traceeval_init()
> > + *
> > + * When the caller of traceeval_init() is done with the returned @teval,
> > + * it must call traceeval_release().
> > + * This does not release any dynamically allocated data inserted by
> > + * the user, although it will call any dyn_release() functions provided by
> > + * the user from traceeval_init().
> 
> The above is contradictory, as it does release user dynamically
> allocated data by calling the dyn_release() function.
> 
>  * This cleans up all internally allocated data of @teval and will call
>  * the corresponding dyn_release() functions that were registered for
>  * the TRACEEVAL_TYPE_DYNAMIC type keys and values.
> 
> 
> > + */
> > +void traceeval_release(struct traceeval *teval);
> > +
> > +/**
> > + * traceeval_insert - Insert an item into the traceeval descriptor
> > + * @teval: The descriptor to insert into
> > + * @keys: The list of keys that defines what is being inserted.
> > + * @vals: The list of values that defines what is being inserted.
> > + *
> 
> > + * Any dynamically allocated data is still owned by the caller; the
> > + * responsibility of deallocating it lies on the caller.
> 
> The above can be removed.
> 
> > + * For all elements of @keys and @vals that correspond to a struct
> > + * traceeval_type of type TRACEEVAL_TYPE_STRING, the string field must be set
> > + * to either a null-terminated string or NULL.
> > + * The @keys is an array that holds the data in the order of the keys
> > + * passed into traceeval_init(). That is, if traceeval_init() had
> > + * keys = { { .type = TRACEEVAL_STRING }, { .type = TRACEEVAL_NUMBER_8 },
> > + * { .type = TRACEEVAL_NONE } }; then the @keys array passed in must
> > + * be a string (char *) followed by a 8 byte number (char). The @keys
> > + * and @vals are only examined to where it expects data. That is,
> > + * if the traceeval_init() keys had 3 items where the first two was defining
> > + * data, and the last one was the TRACEEVAL_TYPE_NONE, then the @keys
> > + * here only needs to be an array of 2, inserting the two items defined
> > + * by traceeval_init(). The same goes for @vals.
> 
> So the above really doesn't explain what the function does.
> 
>  * This function will insert an entry defined by @keys and @vals into
>  * the traceeval instance. The array of @keys and @vals must match that
>  * of what was added to the corresponding parameters of
>  * traceeval_init() that created @teval. No checking is performed, if
>  * there is a mismatch in array length, it will result in undefined behavior.
>  * The types of the @keys and @vals must also match the types used for
>  * the corresponding parameters to traceeval_init().
>  *
>  * If an entry already exists that matches the @keys, then strings and
>  * values will be overwritten by the current values and the old values
>  * will be discarded. For number values, the max, min, total and count
>  * will be recorded. If an entry in @vals has TRACEEVAL_FL_TIMESTAMP
>  * set in its corresponding traceeval_type descriptor, then it will be
>  * used to timestamp the max and min values.
> 
> The description of traceeval_type and traceeval_data mappings as you
> did before, can be saved for the man pages.
> 
> > + *
> > + * Returns 0 on success, and -1 on error.
> > + */
> > +int traceeval_insert(struct traceeval *teval,
> > +		const union traceeval_data *keys,
> > +		const union traceeval_data *vals);
> > +
> > +/**
> > + * traceeval_compare - Check equality between two traceeval instances
> > + * @orig: The first traceeval instance
> > + * @copy: The second traceeval instance
> > + *
> > + * This compares the values of the key definitions, value definitions, and
> > + * inserted data between @orig and @copy in order. It does not compare
> > + * by memory address, except for struct traceeval_type's dyn_release() and
> > + * dyn_cmp() fields.
> > + *
> > + * Returns 0 if @orig and @copy are the same, 1 if not, and -1 on error.
> > + */
> > +int traceeval_compare(struct traceeval *orig, struct traceeval
> > *copy); +
> 
> I'm not really sure what a traceveal_compare() would be used for
> externally. I think we can just remove it? Leave it internally if you
> use it for CUTESTs.
> 
> > +// interface to queuery traceeval
> > +
> > +/**
> > + * traceeval_query - Find the last instance defined by the keys
> > + * @teval: The descriptor to search from
> > + * @keys: A list of data to look for
> > + * @results: A pointer to where to place the results (if found)
> > + *
> > + * This does a lookup for an instance within the traceeval data.
> > + * The @keys is an array defined by the keys declared in traceeval_init().
> > + * The @keys will return an item that had the same keys when it was
> 
>  The @results will ... ?
> 
> > + * inserted by traceeval_insert(). The @keys here follow the same rules
> > + * as the keys for traceeval_insert().
> 
> I know that you copied most of this from my document, but I don't even
> know what the above means ;-)
> 
> Anyway, this patch should be folded piece by piece in the other patches
> as you add the functions as you implement them. That is, you should
> have 4 patches not 5 (this one should no longer exist, as the changes
> will go in the patches that implement each).
> 
> -- Steve
> 
> 
> > + *
> > + * Note, when the caller is done with @results, it must call
> > + * traceeval_results_release() on it.
> > + *
> > + * Returns 1 if found, 0 if not found, and -1 on error.
> > + */
> > +int traceeval_query(struct traceeval *teval,
> > +		const union traceeval_data *keys,
> > +		union traceeval_data * const *results);
> > +
> > +/** Field name/descriptor for number of hits */
> > +#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
> > +
> > +/**
> > + * traceeval_find_key - find the index of a key
> > + * @teval: The descriptor to find the key for
> > + * @field: The name of the key to return the index for
> > + *
> > + * As the order of how keys are defined by traceeval_init(), it
> > + * is important to know what index they are for when dealing with
> > + * the other functions.
> > + *
> > + * Returns the index of the key with @field as the name.
> > + * Return -1 if not found.
> > + */
> > +int traceeval_find_key(struct traceeval *teval, const char *field);
> > +
> > +/**
> > + * traceeval_find_val - find the index of a value
> > + * @teval: The descriptor to find the value for
> > + * @field: The name of the value to return the index for
> > + *
> > + * As the order of how values are defined by traceeval_init(), it
> > + * is important to know what index they are for when dealing with
> > + * the results array from traceeval_query(). In order to facilitate
> > + * this, traceeval_find_val() will return the index for a given
> > + * @field so that the caller does not have to keep track of it.
> > + *
> > + * Returns the index of the value with @field as the name that can be
> > + * used to index the @results array from traceeval_query().
> > + * Return -1 if not found.
> > + */
> > +int traceeval_find_val(struct traceeval *teval, const char *field);
> > +
> > +/**
> > + * traceeval_results_release - Release the results return by traceeval_query()
> > + * @teval: The descriptor used in traceeval_query()
> > + * @results: The results returned by traceeval_query()
> > + *
> > + * The @results returned by traceeval_query() is owned by @teval, and
> > + * how it manages it is implementation specific. The caller should not
> > + * worry about it. When the caller of traceeval_query() is done with
> > + * the @results, it must call traceeval_results_release() on it to
> > + * allow traceeval to clean up its references.
> > + */
> > +void traceeval_results_release(struct traceeval *teval,
> > +		const union traceeval_data *results);
> > +
> > +// Result iterator/histogram dump interfaces
> > +
> > +/** Iterator over aggregated data */
> > +struct traceeval_iterator;
> > +
> > +/**
> > + * traceeval_iterator_get - get an iterator to read the data from traceeval
> > + * @teval: The descriptor to read from
> > + *
> > + * This returns a descriptor that can be used to interate through all the
> > + * data within @teval.
> > + *
> > + * Returns the iterator on success, NULL on error.
> > + */
> > +struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval);
> > +/**
> > + * traceeval_iterator_sort - Set how the iterator is sorted
> > + * @iter: The iterator to set the sorting
> > + * @sort_field: The field (defined by traceeval_init) to sort by.
> > + * @level: The level of sorting.
> > + * @ascending: Set to true to sort ascending order, or false to descending
> > + *
> > + * Sets how the iterator shall be sorted. @sort_field is the field to sort
> > + * by and may be the name of either a key or a value.
> > + *
> > + * The @level should be zero the first time this is called to define the main sort
> > + * field. If secondary sorting is to be done, then this function should be called
> > + * again with @level as 1. For more levels of sorting just call this function
> > + * for each level incrementing level each time. Note, if a level is missed,
> > + * then this will return an error and sorting will not be done for that level.
> > + *
> > + * Returns 0 on success, -1 or error (including missing a level).
> > + */
> > +int traceeval_iterator_sort(struct traceeval_iterator *iter,
> > +		const char *sort_field, int level, bool ascending);
> > +
> > +/**
> > + * traceeval_iterator_next - Iterate through the data of a traceeval descriptor
> > + * @iter: The iterator that holds the location and sorting of the data
> > + * @keys: The current set of keys of the traceeval the @iter is sorting through
> > + *
> > + * This will iterate through all the data of the traceeval descriptor held
> > + * by @iter in the sort pattern defined by traceeval_iterator_sort().
> > + * The @keys return is same as the data used to populate the data passed into
> > + * traceveal_insert(). When the caller is done with @keys, it should be passed
> > + * into traceeval_keys_release().
> > + *
> > + * Returns 1 if it returned an item, 0 if there's no more data to return,
> > + * and -1 on error.
> > + */
> > +int traceeval_iterator_next(struct traceeval_iterator *iter,
> > +		const union traceeval_data **keys);
> > +
> > +/**
> > + * traceeval_keys_release - Release the keys return by
> > traceeval_iterator_next()
> > + * @iter: The iterator used in traceeval_iterator_next().
> > + * @keys: The results returned by traceeval_iterator_next()
> > + *
> > + * The @keys returned by traceeval_iterator_next() is owned by
> > @iter, and
> > + * how it manages it is implementation specific. The caller should
> > not
> > + * worry about it. When the caller of traceeval_iterator_next() is
> > done with
> > + * the @keys, it must call traceeval_keys_release() on it to
> > + * allow traceeval to clean up its references.
> > + */
> > +void traceeval_keys_release(struct traceeval_iterator *iter,
> > +		const union traceeval_data *keys);
> > +
> > +// Statistic extraction
> > +
> > +/** Statistics about a given field */
> > +struct traceeval_stat {
> > +	unsigned long long	max;
> > +	unsigned long long	min;
> > +	unsigned long long	total;
> > +	unsigned long long	avg;
> > +	unsigned long long	std;
> > +};
> > +
> > +/**
> > + * traceeval_stat - Extract stats from a field marke a
> > TRACEEVAL_FL_STATS
> > + * @teval: The descriptor holding the traceeval information
> > + * @keys: The list of keys to find the instance to get the stats on
> > + * @field: The field to retreive the stats for
> > + * @stats: A structure to place the stats into.
> > + *
> > + * This returns the stats of the the given @field. Note, if @field
> > was
> > + * not marked for recording stats with the TRACEEVAL_FL_STATS flag,
> > or
> > + * if no instance is found that has @keys, this will return an error.
> > + *
> > + * Returns 0 on success, -1 on error.
> > + */
> > +int traceeval_stat(struct traceeval *teval, const union
> > traceeval_data *keys,
> > +		const char *field, struct traceeval_stat *stat);
> > +
> > +#endif /* __LIBTRACEEVAL_HIST_H__ */
> > +
> 

Re: [PATCH 1/5] histograms: initial histograms interface

[Steven Rostedt]

On Tue, 1 Aug 2023 15:08:56 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> > Also, for header files, functions do not need kernel doc comments. They
> > should exist in the C files where the function is described.  
> 
> As I've been updating the documentation, I keep thinking about this. Is
> there a particular reason why the documentation should reside within the
> C file rather than the header?
> When I think about using libraries, my immediate thought is to look at the
> interface/header file to see what functions are avaiable and what they do,
> not the source. I'd think that the code would jumble up my view and make
> it more cumbersome and distracting to read.
> All that said, I'm not sure sure if that's not the standard way of doing
> things here.

The reason is that users should be using the man pages that we create. But
the comment around the code is to remind us (the code developers) what the
code is for while we are developing. When I work on a function, I like to
read the comment for that function to make sure I'm not breaking anything.

In other words, users of the code should not need to be looking at the
header files (I seldom do, unless there's missing man pages). If we put the
comment by the prototype, then really nobody will be seeing it.

We will have man pages before this is fully released.

-- Steve

Re: [PATCH 2/5] histograms: traceeval initialize

[Ross Zwisler]

On Fri, Jul 28, 2023 at 03:04:37PM -0400, Stevie Alvarez wrote:
> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> traceeval_init() creates a new struct traceeval instance with regards
> to the struct traceeval_type array arguments keys and vals. These arrays
> define the structure of the histogram, with each describing the expected
> structure of inserted arrays of union traceeval_data. The keys and vals
> arguments are copied on the heap to ensure that the struct traceeval
> instance has access to the definition regardless of how the user
> initialized keys and vals.
> 
> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  Makefile         |   2 +-
>  src/Makefile     |   1 +
>  src/histograms.c | 285 +++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 287 insertions(+), 1 deletion(-)
>  create mode 100644 src/histograms.c
> 
> diff --git a/Makefile b/Makefile
> index 4a24d5a..3ea051c 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -172,7 +172,7 @@ libs: $(LIBRARY_A) $(LIBRARY_SO)
>  
>  VALGRIND = $(shell which valgrind)
>  UTEST_DIR = utest
> -UTEST_BINARY = trace-utest
> +UTEST_BINARY = eval-utest
>  
>  test: force $(LIBRARY_STATIC)
>  ifneq ($(CUNIT_INSTALLED),1)
> diff --git a/src/Makefile b/src/Makefile
> index b4b6e52..b32a389 100644
> --- a/src/Makefile
> +++ b/src/Makefile
> @@ -4,6 +4,7 @@ include $(src)/scripts/utils.mk
>  
>  OBJS =
>  OBJS += trace-analysis.o
> +OBJS += histograms.o
>  
>  OBJS := $(OBJS:%.o=$(bdir)/%.o)
>  
> diff --git a/src/histograms.c b/src/histograms.c
> new file mode 100644
> index 0000000..13830e4
> --- /dev/null
> +++ b/src/histograms.c
> @@ -0,0 +1,285 @@
> +
> +/* SPDX-License-Identifier: MIT */
> +/*
> + * libtraceeval histogram interface implementation.
> + *
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +
> +#include <histograms.h>
> +#include <stdio.h>
> +#include <stdbool.h>
> +#include <string.h>
> +#include <stdarg.h>
> +
> +/**
> + * Iterate over @keys, which should be an array of struct traceeval_type's,
> + * until reaching an instance of type TRACEEVAL_TYPE_NONE.
> + * @i should be a declared integer type.
> + */
> +#define for_each_key(i, keys)	\
> +	for (i = 0; (keys)[(i)].type != TRACEEVAL_TYPE_NONE; (i)++)
> +
> +/** A key-value pair */
> +struct entry {
> +	union traceeval_data	*keys;
> +	union traceeval_data	*vals;
> +};
> +
> +/** A table of key-value entries */
> +struct hist_table {
> +	struct entry	*map;
> +	size_t		nr_entries;
> +};
> +
> +/** Histogram */
> +struct traceeval {
> +	struct traceeval_type		*def_keys;
> +	struct traceeval_type		*def_vals;
> +	struct hist_table		*hist;
> +};

Should this be called something else?  'struct traceeval' is already defined
in src/trace-analysis.c in this same codebase, and the other def is used all
over the place in include/traceeval.h.

> +
> +/** Iterate over results of histogram */
> +struct traceeval_iterator {};  // TODO
> +
> +/**
> + * Print error message.
> + * Additional arguments are used with respect to fmt.
> + */
> +static void print_err(const char *fmt, ...)
> +{
> +	va_list ap;
> +
> +	va_start(ap, fmt);
> +	vfprintf(stderr, fmt, ap);
> +	va_end(ap);
> +	fprintf(stderr, "\n");
> +}
> +
> +// TODO
> +int traceeval_compare(struct traceeval *orig, struct traceeval *copy)
> +{
> +	return -1;
> +}
> +
> +/**
> + * Resize a struct traceeval_type array to a size of @size + 1.
> + *
> + * Returns a pointer to the resized array, or NULL if the provided pointer was
> + * freed to due lack of memory.
> + */
> +static struct traceeval_type *type_realloc(struct traceeval_type *defs,

Probably should have been feedback for patch 1, but 'traceeval_type' also has
a collision.  'struct traceeval_type' is defined in include/histograms.h, and
'enum traceeval_type' is defined in include/libtraceeval.h.

IMO even if the compiler lets us do this, we shouldn't because it'll confuse
cscope/LSMs/grep and people reading the code.

> +		size_t size)
> +{
> +	struct traceeval_type *tmp_defs = NULL;
> +	tmp_defs = realloc(defs,
> +			(size + 1) * sizeof(struct traceeval_type));
> +	if (!tmp_defs)
> +		goto fail_type_realloc;
> +	return tmp_defs;
> +
> +fail_type_realloc:
> +	for (int i = 0; i < size; i++) {
> +		if (defs[i].name)
> +			free(defs[i].name);

Because the extra entries returned by realloc() are uninitialized, I think you
risk trying to free 'name' values that are non-NULL but not real pointers.

Should you instead try to iterate from 0 until you find an entry with type
TRACEEVAL_TYPE_NONE?  Or do you guarantee elsewhere that all 'name' pointers
are either valid or NULL?  If so, it might be good to do that initialization
in this function so the free path makes sense in the same context and so new
users of this function don't violate that assumption.

> +	}
> +	free(defs);
> +	return NULL;
> +}
> +
> +/**
> + * Clone traceeval_type array @defs to the heap. Must be terminated with
> + * an instance of type TRACEEVAL_TYPE_NONE.
> + * Returns NULL if @defs is NULL, or a name is not null terminated.

It actually returns an single entry TRACEEVAL_TYPE_NONE list if @defs is NULL

> + */
> +static struct traceeval_type *type_alloc(const struct traceeval_type *defs)
> +{
> +	struct traceeval_type *new_defs = NULL;
> +	char *name;
> +	size_t size = 0;
> +
> +	// Empty def is represented with single TRACEEVAL_TYPE_NONE
> +	if (defs == NULL) {
> +		if (!(new_defs = calloc(1, sizeof(struct traceeval_type))))
> +			goto fail_type_alloc;
> +		new_defs->type = TRACEEVAL_TYPE_NONE;
> +		return new_defs;
> +	}
> +
> +	for_each_key(size, defs) {
> +		// Resize heap defs and clone
> +		new_defs = type_realloc(new_defs, size);
> +		if (!new_defs)
> +			goto fail_type_alloc;
> +
> +		// copy current def data to new_def
> +		new_defs[size] = defs[size];
> +		new_defs[size].name = NULL;
> +		// copy name to heap if it's not NULL or type NONE
> +		if (defs[size].type != TRACEEVAL_TYPE_NONE) {
> +			name = NULL;
> +			if (!defs[size].name)
> +				goto fail_type_alloc_name;
> +
> +			name = strdup(defs[size].name);
> +			if (!name)
> +				goto fail_type_alloc_name;
> +			new_defs[size].name = name;
> +		}
> +	}
> +
> +	// append array terminator
> +	new_defs = type_realloc(new_defs, size);
> +	if (!new_defs)
> +		goto fail_type_alloc;
> +	new_defs[size].type = TRACEEVAL_TYPE_NONE;
> +
> +	return new_defs;
> +fail_type_alloc:
> +	if (defs[size].name)
> +		print_err("failed to allocate memory for traceeval_type %s", defs[size].name);
> +	print_err("failed to allocate memory for traceeval_type index %zu", size);
> +	return NULL;
> +
> +fail_type_alloc_name:
> +	if (defs[size].name)
> +		print_err("failed to allocate name for traceeval_type %s", defs[size].name);
> +
> +	print_err("failed to allocate name for traceeval_type index %zu", size);
> +	return NULL;

These two error paths do the same actions (no extra frees or anything) and
just differ in text, so they can probably be collapsed into one.

> +}
> +
> +/**
> + * Create a new histogram over the given keys and values.
> + */
> +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> +				 const struct traceeval_type *vals)
> +{
> +	struct traceeval *teval;
> +	char *err_msg;
> +	struct traceeval_type type = {
> +		.type = TRACEEVAL_TYPE_NONE
> +	};
> +
> +	if (!keys)
> +		return NULL;
> +
> +	if (keys->type == TRACEEVAL_TYPE_NONE) {
> +		err_msg = "keys cannot start with type TRACEEVAL_TYPE_NONE";
> +		goto fail_eval_init_unalloced;
> +	}
> +
> +	teval = calloc(1, sizeof(struct traceeval));
> +	if (!teval) {
> +		err_msg = "failed to allocate memory for traceeval instance";
> +		goto fail_eval_init_unalloced;
> +	}
> +
> +	teval->def_keys = type_alloc(keys);
> +	if (!teval->def_keys) {
> +		err_msg = "failed to allocate user defined keys";
> +		goto fail_eval_init;
> +	}
> +
> +	// if vals is NULL, alloc single type NONE
> +	if (vals)
> +		teval->def_vals = type_alloc(vals);
> +	else
> +		teval->def_vals = type_alloc(&type);

Because type_alloc(NULL) returns a single TRACEEVAL_TYPE_NONE entry, you can
collapse these two cases into just 

  teval->def_vals = type_alloc(vals);

and get rid of the 'type' local variable.

> +
> +	if (!teval->def_vals) {
> +		err_msg = "failed to allocate user defined values";
> +		goto fail_eval_init;
> +	}
> +
> +	teval->hist = calloc(1, sizeof(struct hist_table));

nit: Steven mentioned this too, but I think it's better to say
"sizeof(*teval->hist)".  This prevents the types from getting out of sync, say
if for example we changed the type of teval->hist.

You can see examples of this in the kernel:
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/kernel/params.c#n639
I think this applies to all the places you are doing sizeof(struct X).

> +	if (!teval->hist) {
> +		err_msg = "failed to allocate memory for histogram";
> +		goto fail_eval_init;
> +	}
> +	teval->hist->nr_entries = 0;
> +
> +	return teval;
> +fail_eval_init:
> +	traceeval_release(teval);
> +	/* fall-through */
> +
> +fail_eval_init_unalloced:
> +	print_err(err_msg);
> +	return NULL;
> +}

Re: [PATCH 2/5] histograms: traceeval initialize

[Steven Rostedt]

On Wed, 2 Aug 2023 15:07:21 -0600
Ross Zwisler <zwisler@google.com> wrote:

> > diff --git a/src/histograms.c b/src/histograms.c
> > new file mode 100644
> > index 0000000..13830e4
> > --- /dev/null
> > +++ b/src/histograms.c
> > @@ -0,0 +1,285 @@
> > +
> > +/* SPDX-License-Identifier: MIT */
> > +/*
> > + * libtraceeval histogram interface implementation.
> > + *
> > + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> > + */
> > +
> > +#include <histograms.h>
> > +#include <stdio.h>
> > +#include <stdbool.h>
> > +#include <string.h>
> > +#include <stdarg.h>
> > +
> > +/**
> > + * Iterate over @keys, which should be an array of struct traceeval_type's,
> > + * until reaching an instance of type TRACEEVAL_TYPE_NONE.
> > + * @i should be a declared integer type.
> > + */
> > +#define for_each_key(i, keys)	\
> > +	for (i = 0; (keys)[(i)].type != TRACEEVAL_TYPE_NONE; (i)++)
> > +
> > +/** A key-value pair */
> > +struct entry {
> > +	union traceeval_data	*keys;
> > +	union traceeval_data	*vals;
> > +};
> > +
> > +/** A table of key-value entries */
> > +struct hist_table {
> > +	struct entry	*map;
> > +	size_t		nr_entries;
> > +};
> > +
> > +/** Histogram */
> > +struct traceeval {
> > +	struct traceeval_type		*def_keys;
> > +	struct traceeval_type		*def_vals;
> > +	struct hist_table		*hist;
> > +};  
> 
> Should this be called something else?  'struct traceeval' is already defined
> in src/trace-analysis.c in this same codebase, and the other def is used all
> over the place in include/traceeval.h.

Yeah, we could call it something slightly different for now, but the goal
is that it will supersede the struct traceeval in trace-analysis.c, and the
code there will be removed.

We haven't hit version 1.0 yet because I hated the old API and until 1.0 is
reached, the API is allowed to change.

> 
> > +
> > +/** Iterate over results of histogram */
> > +struct traceeval_iterator {};  // TODO
> > +
> > +/**
> > + * Print error message.
> > + * Additional arguments are used with respect to fmt.
> > + */
> > +static void print_err(const char *fmt, ...)
> > +{
> > +	va_list ap;
> > +
> > +	va_start(ap, fmt);
> > +	vfprintf(stderr, fmt, ap);
> > +	va_end(ap);
> > +	fprintf(stderr, "\n");
> > +}
> > +
> > +// TODO
> > +int traceeval_compare(struct traceeval *orig, struct traceeval *copy)
> > +{
> > +	return -1;
> > +}
> > +
> > +/**
> > + * Resize a struct traceeval_type array to a size of @size + 1.
> > + *
> > + * Returns a pointer to the resized array, or NULL if the provided pointer was
> > + * freed to due lack of memory.
> > + */
> > +static struct traceeval_type *type_realloc(struct traceeval_type *defs,  
> 
> Probably should have been feedback for patch 1, but 'traceeval_type' also has
> a collision.  'struct traceeval_type' is defined in include/histograms.h, and
> 'enum traceeval_type' is defined in include/libtraceeval.h.
> 
> IMO even if the compiler lets us do this, we shouldn't because it'll confuse
> cscope/LSMs/grep and people reading the code.

Again, I think it may be fine, as we will eventually remove the old code.


> 
> > +		size_t size)
> > +{
> > +	struct traceeval_type *tmp_defs = NULL;
> > +	tmp_defs = realloc(defs,
> > +			(size + 1) * sizeof(struct traceeval_type));
> > +	if (!tmp_defs)
> > +		goto fail_type_realloc;
> > +	return tmp_defs;
> > +
> > +fail_type_realloc:
> > +	for (int i = 0; i < size; i++) {
> > +		if (defs[i].name)
> > +			free(defs[i].name);  
> 
> Because the extra entries returned by realloc() are uninitialized, I think you
> risk trying to free 'name' values that are non-NULL but not real pointers.
> 
> Should you instead try to iterate from 0 until you find an entry with type
> TRACEEVAL_TYPE_NONE?  Or do you guarantee elsewhere that all 'name' pointers
> are either valid or NULL?  If so, it might be good to do that initialization
> in this function so the free path makes sense in the same context and so new
> users of this function don't violate that assumption.

I believe I mentioned the same thing (or similar) in my reply.

-- Steve

> 
> > +	}
> > +	free(defs);
> > +	return NULL;
> > +}
> > +
> > +/**
> > + * Clone traceeval_type array @defs to the heap. Must be terminated with
> > + * an instance of type TRACEEVAL_TYPE_NONE.
> > + * Returns NULL if @defs is NULL, or a name is not null terminated.  
>

Re: [PATCH 3/5] histograms: traceeval release

[Ross Zwisler]

On Fri, Jul 28, 2023 at 03:04:38PM -0400, Stevie Alvarez wrote:
> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> traceeval_release() deconstructs a given struct traceeval instance. It
> frees any data allocated to the heap within the union traceeval_data
> arrays of entries to the histogram, and the names allocated for the
> struct traceeval_type key-value definitions.
> 
> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  src/histograms.c | 87 ++++++++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 85 insertions(+), 2 deletions(-)
> 
> diff --git a/src/histograms.c b/src/histograms.c
> index 13830e4..f46a0e0 100644
> --- a/src/histograms.c
> +++ b/src/histograms.c
> @@ -209,10 +209,93 @@ fail_eval_init_unalloced:
>  	return NULL;
>  }
>  
> -// TODO
> -void traceeval_release(struct traceeval *teval)
> +/**
> + * Deallocate array of traceeval_type's, which must be terminated by
> + * TRACEEVAL_TYPE_NONE.
> + */
> +static void type_release(struct traceeval_type *defs)
>  {
> +	size_t i = 0;
> +
> +	if (!defs)
> +		return;
> +
> +	for_each_key(i, defs) {
> +		if (defs[i].name)
> +			free(defs[i].name);
> +	}
> +
> +	free(defs);
> +}
> +
> +/**
> + * Deallocate any specified dynamic data in @data.
> + */
> +static void clean_data(union traceeval_data *data, struct traceeval_type *def)
> +{
> +	size_t i = 0;
> +
> +	if (!data || !def)
> +		return;
> +
> +	for_each_key(i, def) {
> +		switch (def[i].type) {
> +		case TRACEEVAL_TYPE_STRING:
> +			if (data[i].string)
> +				free(data[i].string);
> +			break;
> +		case TRACEEVAL_TYPE_DYNAMIC:
> +			def[i].dyn_release(data[i].dyn_data, &def[i]);
> +			break;
> +		default:
> +			break;
> +		}
> +	}
> +}
>  
> +/**
> + * Deallocate all possible data stored within the entry.
> + */
> +static void clean_entry(struct entry *entry, struct traceeval *teval)
> +{
> +	if (!entry) 

Should we check for NULL 'teval' as well?

> +		return;
> +
> +	// deallocate dynamic traceeval_data
> +	clean_data(entry->keys, teval->def_keys);
> +	clean_data(entry->vals, teval->def_vals);
> +	free(entry->keys);
> +	free(entry->vals);
> +}
> +
> +/**
> + * Deallocate the hist_table allocated to a traceeval instance.
> + */
> +static void hist_table_release(struct traceeval *teval)
> +{
> +	struct hist_table *hist = teval->hist;
> +
> +	if (!hist)
> +		return;
> +
> +	for (size_t i = 0; i < hist->nr_entries; i++) {
> +		clean_entry(&hist->map[i], teval);
> +	}
> +	free(hist->map);
> +	free(hist);

Probably good to set 'teval->hist = NULL' just for good hygiene.  This keeps
later users from accidentally having a use-after-free.

Re: [PATCH 3/5] histograms: traceeval release

[Steven Rostedt]

On Wed, 2 Aug 2023 15:54:03 -0600
Ross Zwisler <zwisler@google.com> wrote:

> > +/**
> > + * Deallocate all possible data stored within the entry.
> > + */
> > +static void clean_entry(struct entry *entry, struct traceeval *teval)
> > +{
> > +	if (!entry)   
> 
> Should we check for NULL 'teval' as well?

No, because teval can't be NULL here. As to get here, we need to go through
traceeval_release() which does the check for !teval.

-- Steve
> 
> > +		return;
> > +
> > +	// deallocate dynamic traceeval_data
> > +	clean_data(entry->keys, teval->def_keys);
> > +	clean_data(entry->vals, teval->def_vals);
> > +	free(entry->keys);
> > +	free(entry->vals);
> > +}

Re: [PATCH 3/5] histograms: traceeval release

[Steven Rostedt]

On Fri, 28 Jul 2023 15:04:38 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> +/**
> + * Deallocate a traceeval instance.
> + */
> +void traceeval_release(struct traceeval *teval)
> +{
> +	if (teval) {
> +		hist_table_release(teval);
> +		type_release(teval->def_keys);
> +		type_release(teval->def_vals);
> +		free(teval);
> +	}
>  }

Nit, but it is usually cleaner to just have:

void traceeval_release(struct traceeval *teval)
{
	if (!teval)
		return;

	hist_table_release(teval);
	type_release(teval->def_keys);
	type_release(teval->def_vals);
	free(teval);
}


Less indents ;-)

-- Steve

Re: [PATCH 4/5] histograms: traceeval compare

[Ross Zwisler]

On Fri, Jul 28, 2023 at 03:04:39PM -0400, Stevie Alvarez wrote:
> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> traceeval_compare() compares two struct traceeval instances for
> equality. This suite of comparitors was made for testing purposes.
> 
> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  src/histograms.c | 178 ++++++++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 176 insertions(+), 2 deletions(-)
> 
> diff --git a/src/histograms.c b/src/histograms.c
> index f46a0e0..5f1c7ef 100644
> --- a/src/histograms.c
> +++ b/src/histograms.c
> @@ -20,6 +20,19 @@
>  #define for_each_key(i, keys)	\
>  	for (i = 0; (keys)[(i)].type != TRACEEVAL_TYPE_NONE; (i)++)
>  
> +/**
> + * Compare two integers of variable length.
> + *
> + * Return 0 if @a and @b are the same, 1 if @a is greater than @b, and -1
> + * if @b is greater than @a.
> + */
> +#define compare_numbers_return(a, b)	\
> +do {					\
> +	if ((a) < (b))			\
> +		return -1;		\
> +	return (a) != (b);		\
> +} while (0)				\
> +
>  /** A key-value pair */
>  struct entry {
>  	union traceeval_data	*keys;
> @@ -56,10 +69,171 @@ static void print_err(const char *fmt, ...)
>  	fprintf(stderr, "\n");
>  }
>  
> -// TODO
> +/**
> + * Return 0 if @orig and @copy are the same, 1 otherwise.
> + */
> +static int compare_traceeval_type(struct traceeval_type *orig,
> +		struct traceeval_type *copy)
> +{
> +	int o_name_null;
> +	int c_name_null;
> +
> +	// same memory/null
> +	if (orig == copy)
> +		return 0;
> +
> +	size_t i = 0;

Best practice is to put all the variable definitions at the top of the
function.

> +	do {
> +		if (orig[i].type != copy[i].type)
> +			return 1;
> +		if (orig[i].type == TRACEEVAL_TYPE_NONE)
> +			return 0;
> +		if (orig[i].flags != copy[i].flags)
> +			return 1;
> +		if (orig[i].id != copy[i].id)
> +			return 1;
> +		if (orig[i].dyn_release != copy[i].dyn_release)
> +			return 1;
> +		if (orig[i].dyn_cmp != copy[i].dyn_cmp)
> +			return 1;
> +
> +		// make sure both names are same type
> +		o_name_null = !orig[i].name;
> +		c_name_null = !copy[i].name;
> +		if (o_name_null != c_name_null)
> +			return 1;
> +		if (o_name_null)
> +			continue;
> +		if (strcmp(orig[i].name, copy[i].name) != 0)
> +			return 1;
> +	} while (orig[i++].type != TRACEEVAL_TYPE_NONE);
> +
> +	return 0;
> +}

<snip>

> +/**
> + * Return 0 if struct hist_table of @orig and @copy are the same, 1 if not,
> + * and -1 on error.
> + */
> +static int compare_hist(struct traceeval *orig, struct traceeval *copy)
> +{
> +	struct hist_table *o_hist = orig->hist;
> +	struct hist_table *c_hist = copy->hist;
> +	int cnt = !(o_hist->nr_entries == c_hist->nr_entries);
> +	if (cnt)
> +		return 1;
> +
> +	for (size_t i = 0; i < o_hist->nr_entries; i++) {
> +		// cmp each entry
> +		compare_entries(&o_hist->map[i], &c_hist->map[i], orig);

Need to check the return value of 'compare_entries()' and return it if it's
nonzero.

> +	}
> +	return 0;	
> +}
> +
> +/**
> + * Return 0 if @orig and @copy are the same, 1 if not, -1 if error.
> + */
>  int traceeval_compare(struct traceeval *orig, struct traceeval *copy)
>  {
> -	return -1;
> +	if ((!orig) || (!copy))

No need for parens, this can just be:

  if (!orig || !copy)
    return -1;

> +		return -1;
> +
> +	int keys = compare_traceeval_type(orig->def_keys, copy->def_keys);
> +	int vals = compare_traceeval_type(orig->def_vals, copy->def_vals);
> +	int hists = compare_hist(orig, copy);
> +
> +	return (keys || vals || hists);
>  }
>  
>  /**
> -- 
> 2.41.0
> 

Re: [PATCH 5/5] histograms: Add struct traceeval unit tests

[Ross Zwisler]

On Fri, Jul 28, 2023 at 03:04:40PM -0400, Stevie Alvarez wrote:
> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> Add unit tests for traceeval_init(), traceeval_release(), and
> traceeval_compare() to check edge cases and ensure the interface is
> functional.
> 
> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  utest/.gitignore        |   1 +
>  utest/Makefile          |  35 +++++++
>  utest/eval-test.h       |  10 ++
>  utest/eval-utest.c      |  27 +++++
>  utest/traceeval-utest.c | 222 ++++++++++++++++++++++++++++++++++++++++
>  5 files changed, 295 insertions(+)
>  create mode 100644 utest/.gitignore
>  create mode 100644 utest/Makefile
>  create mode 100644 utest/eval-test.h
>  create mode 100644 utest/eval-utest.c
>  create mode 100644 utest/traceeval-utest.c
> 
> diff --git a/utest/.gitignore b/utest/.gitignore
> new file mode 100644
> index 0000000..ca0ac10
> --- /dev/null
> +++ b/utest/.gitignore
> @@ -0,0 +1 @@
> +eval-utest
> diff --git a/utest/Makefile b/utest/Makefile
> new file mode 100644
> index 0000000..955f91e
> --- /dev/null
> +++ b/utest/Makefile
> @@ -0,0 +1,35 @@
> +# SPDX-License-Identifier: MIT
> +
> +include $(src)/scripts/utils.mk
> +
> +bdir := $(obj)/utest
> +eval_lib := $(obj)/lib/libtraceeval.a
> +
> +TARGETS = $(bdir)/eval-utest
> +
> +OBJS := eval-utest.o
> +OBJS += traceeval-utest.o
> +
> +LIBS += -lcunit				\
> +	-ldl				\
> +	$(eval_lib)
> +
> +OBJS := $(OBJS:%.o=$(bdir)/%.o)
> +
> +$(bdir):
> +	@mkdir -p $(bdir)
> +
> +$(OBJS): | $(bdir)
> +
> +$(bdir)/eval-utest: $(OBJS) $(eval_lib)
> +	$(Q)$(do_app_build)
> +
> +$(bdir)/%.o: %.c
> +	$(Q)$(call do_fpic_compile)
> +
> +-include .*.d
> +
> +test: $(TARGETS)
> +
> +clean:
> +	$(Q)$(call do_clean,$(TARGETS) $(bdir)/*.o $(bdir)/.*.d)
> diff --git a/utest/eval-test.h b/utest/eval-test.h
> new file mode 100644
> index 0000000..f3372e8
> --- /dev/null
> +++ b/utest/eval-test.h
> @@ -0,0 +1,10 @@
> +/* SPDX-License-Identifier: MIT */
> +/*
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +#ifndef _EVAL_UTEST_H_
> +#define _EVAL_UTEST_H_
> +
> +void test_traceeval_lib(void);
> +
> +#endif /* _EVAL_UTEST_H_ */
> diff --git a/utest/eval-utest.c b/utest/eval-utest.c
> new file mode 100644
> index 0000000..771a0c4
> --- /dev/null
> +++ b/utest/eval-utest.c
> @@ -0,0 +1,27 @@
> +
> +// SPDX-License-Identifier: MIT
> +/*
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +#include <stdio.h>
> +#include <stdlib.h>
> +
> +#include <CUnit/CUnit.h>
> +#include <CUnit/Basic.h>
> +
> +#include "eval-test.h"
> +
> +int main(int argc, char **argv)
> +{
> +	if (CU_initialize_registry() != CUE_SUCCESS) {
> +		printf("Test registry cannot be initialized\n");
> +		return EXIT_FAILURE;
> +	}
> +
> +	test_traceeval_lib();
> +
> +	CU_basic_set_mode(CU_BRM_VERBOSE);
> +	CU_basic_run_tests();
> +	CU_cleanup_registry();
> +	return EXIT_SUCCESS;
> +}
> diff --git a/utest/traceeval-utest.c b/utest/traceeval-utest.c
> new file mode 100644
> index 0000000..2bcb4b9
> --- /dev/null
> +++ b/utest/traceeval-utest.c
> @@ -0,0 +1,222 @@
> +// SPDX-License-Identifier: MIT
> +/*
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +
> +#include <string.h>
> +#include <stdio.h>
> +#include <stdbool.h>
> +#include <CUnit/CUnit.h>
> +#include <CUnit/Basic.h>
> +
> +#include <histograms.h>
> +
> +#define TRACEEVAL_SUITE		"traceeval library"
> +#define TRACEEVAL_SUCCESS	0
> +#define TRACEEVAL_FAILURE	-1
> +#define TRACEEVAL_NOT_SAME	1
> +
> +/**
> + * Test traceeval_init(), traceeval_release(), and traceeval_compare() with
> + * NULL values.
> + */
> +void test_eval_null(void)

All functions except test_traceeval_lib() should be static.

> +{
> +	// set up
> +	char *name = "test null";
> +	enum traceeval_data_type type = TRACEEVAL_TYPE_NONE;
> +	const struct traceeval_type test_data[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = name
> +		},
> +		{
> +			.type = type,
			.type = TRACEEVAL_TYPE_NONE,

and you can get rid of the 'type' variable.

> +			.name = NULL
> +		}
> +	};
> +
> +	// test init
> +	struct traceeval *result_null = traceeval_init(NULL, NULL);
> +	struct traceeval *result_key = traceeval_init(test_data, NULL);
> +	struct traceeval *result_val = traceeval_init(NULL, test_data);
> +	
> +	// analyze init
> +	CU_ASSERT(!result_null);
> +	CU_ASSERT(result_key != NULL);
> +	CU_ASSERT(!result_val);
> +
> +	// release
> +	traceeval_release(NULL);
> +	traceeval_release(result_key);
> +}
> +
> +/**
> + * Use provided data to test traceeval_init(), traceeval_compare(), and
> + * traceeval_release().
> + */
> +void test_eval_base(const struct traceeval_type *keys1,
> +		const struct traceeval_type *vals1,
> +		const struct traceeval_type *keys2,
> +		const struct traceeval_type *vals2,
> +		bool init_not_null1, bool init_not_null2,
> +		int compare_result)
> +{
> +	struct traceeval *init1;
> +	struct traceeval *init2;
> +	int result;
> +
> +	// test init
> +	init1 = traceeval_init(keys1, vals1);
> +	init2 = traceeval_init(keys2, vals2);
> +
> +	result = init1 != NULL;
> +	if (init_not_null1) {
> +		CU_ASSERT(result);
> +	} else {
> +		CU_ASSERT(!result);
> +	}
> +
> +	result = init2 != NULL;
> +	if (init_not_null2) {
> +		CU_ASSERT(result);
> +	} else {
> +		CU_ASSERT(!result);
> +	}
> +
> +	// test compare
> +	result = traceeval_compare(init1, init2);
> +	
> +	// analyze compare
> +	CU_ASSERT(result == compare_result);
> +	
> +	// release
> +	traceeval_release(init1);
> +	traceeval_release(init2);
> +}
> +
> +/**
> + * Test traceeval_init(), traceeval_release(), and traceeval_compare() with
> + * TRACEEVAL_TYPE_NONE.
> + */
> +void test_eval_none(void)
> +{
> +	// set up
> +	char *name = "test none";
> +	char *name2 = "test none (some)";
> +	const struct traceeval_type test_data_none[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = name
> +		}
> +	};
> +	const struct traceeval_type test_data_some[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = name2
> +		},
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = NULL
> +		}
> +	};
> +
> +	test_eval_base(test_data_some, test_data_none, test_data_some,
> +			test_data_none, true, true, TRACEEVAL_SUCCESS);
> +	test_eval_base(test_data_none, test_data_none, test_data_some,
> +			test_data_none, false, true, TRACEEVAL_FAILURE);
> +	test_eval_base(test_data_none, test_data_none, test_data_none,
> +			test_data_none, false, false, TRACEEVAL_FAILURE);
> +}
> +
> +/**
> + * Test traceeval_init() and traceeval_release() with equivalent values.
> + */
> +void test_eval_same(void)
> +{
> +	// set up
> +	char *name = "test data";
> +	char *name2 = "test done";

        char *name2 = "test none";
        ?

> +	const struct traceeval_type test_data[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = name
> +		},
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = name2
> +		}
> +	};
> +	
> +	test_eval_base(test_data, test_data, test_data, test_data, true, true,
> +			TRACEEVAL_SUCCESS);
> +}
> +
> +/**
> + * Test traceeval_init() and traceeval_release() with non-equivalent values.
> + */
> +void test_eval_not_same(void)
> +{
> +	const struct traceeval_type test_data1[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = "test data 1"

nit: maybe just inline all the names in other test functions, like you have in
this one?  Saves some variables & is more readable.

> +		},
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = NULL
> +		}
> +	};
> +	const struct traceeval_type test_data2[] =  {
> +		{
> +			.type = TRACEEVAL_TYPE_NUMBER,
> +			.name = "test data 2"
> +		},
> +		{
> +			.type = TRACEEVAL_TYPE_NONE,
> +			.name = NULL
> +		}
> +	};
> +
> +	// type 1 key diff
> +	test_eval_base(test_data2, test_data1, test_data1, test_data1, true,
> +			true, TRACEEVAL_NOT_SAME);
> +	// type 1 data diff
> +	test_eval_base(test_data1, test_data2, test_data1, test_data1, true,
> +			true, TRACEEVAL_NOT_SAME);
> +	// type 2 key diff
> +	test_eval_base(test_data1, test_data1, test_data2, test_data1, true,
> +			true, TRACEEVAL_NOT_SAME);
> +	// type 2 data diff
> +	test_eval_base(test_data1, test_data1, test_data1, test_data2, true,
> +			true, TRACEEVAL_NOT_SAME);
> +}
> +
> +/**
> + * Tests the traceeval_init() and traceeval_release() functions.
> + */
> +void test_eval(void)
> +{
> +	test_eval_null();
> +	test_eval_none();
> +	test_eval_same();
> +	test_eval_not_same();
> +}
> +
> +/**
> + * Register tests with CUnit.
> + */
> +void test_traceeval_lib(void)
> +{
> +	CU_pSuite suite = NULL;
> +	
> +	// set up suite
> +	suite = CU_add_suite(TRACEEVAL_SUITE, NULL, NULL);
> +	if (suite == NULL) {
> +		fprintf(stderr, "Suite %s cannot be created\n", TRACEEVAL_SUITE);
> +		return;
> +	}
> +
> +	// add tests to suite
> +	CU_add_test(suite, "Test traceeval alloc and release", test_eval);
> +}
> -- 
> 2.41.0
>