[PATCH v2 0/5] histograms: bug fixes and convention compliance

[PATCH v2 0/5] histograms: bug fixes and convention compliance

[Stevie Alvarez]

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

Changes in v2:
 * Renamed interface from histograms.h to traceeval-hist.h.
 * Internal traceeval_type arrays terminated by size rather than type.
 * type_alloc() guarantees traceeval_type name field is a valid pointer.
 * traceeval_release() sets released pointers to NULL.
 * Conditional simplifications and fixes across the board. 
 * Removed function stubs and their interface definitions.
 * Added a timestamp flag.
 * Added typedefs for traceeval_dynamic helper function signatures. 
 * Documentation follows established conventions (kernel docs, line comments).
 * Documentation moved from interface to source code.
 * Internal testing interface.
 * General documentation spell checking.

Since the addition of the traceeval_dynamic function signature typedefs,
warnings pertaining to these function signatures and traceeval_type have
popped up. Steven, Ross, and anyone else, any ideas on why these
warnings are showing up?

Warning from function signatures in include/traceeval-hist.h, line 65 and 69:
	warning: ‘struct traceeval_type’ declared inside parameter list will
	not be visible outside of this definition or declaration

		struct traceeval_type *);

Warning from dyn_release call in src/histograms.c line 258:
	warning: passing argument 2 of
	‘(defs + (sizetype)(i * 48))->dyn_release’ from incompatible
	pointer type

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

	note: expected ‘struct traceeval_type *’ but argument is of type
	‘struct traceeval_type *’

Warning from dyn_cmp call in src/histograms.c line 409:
	warning: passing argument 3 of ‘type->dyn_cmp’ from incompatible
	pointer type

		return type->dyn_cmp(orig->dyn_data, copy->dyn_data, type);

	note: expected ‘struct traceeval_type *’ but argument is of type
	‘struct traceeval_type *’

---
v1 discussion: https://lore.kernel.org/linux-trace-devel/20230731212542.3fb668b1@gandalf.local.home/T/

Stevie Alvarez (Google) (5):
  histograms: Initial histograms interface
  histograms: Add traceeval initialize
  histograms: Add traceeval release
  histograms: Add traceeval compare
  histograms: Initial unit tests

 Makefile                 |   2 +-
 include/traceeval-hist.h | 135 ++++++++++
 include/traceeval-test.h |  15 ++
 src/Makefile             |   1 +
 src/histograms.c         | 522 +++++++++++++++++++++++++++++++++++++++
 utest/.gitignore         |   1 +
 utest/Makefile           |  35 +++
 utest/eval-test.h        |  13 +
 utest/eval-utest.c       |  28 +++
 utest/traceeval-utest.c  | 217 ++++++++++++++++
 10 files changed, 968 insertions(+), 1 deletion(-)
 create mode 100644 include/traceeval-hist.h
 create mode 100644 include/traceeval-test.h
 create mode 100644 src/histograms.c
 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

-- 
2.41.0

[PATCH v2 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/traceeval-hist.h | 128 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 128 insertions(+)
 create mode 100644 include/traceeval-hist.h

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
new file mode 100644
index 0000000..4664974
--- /dev/null
+++ b/include/traceeval-hist.h
@@ -0,0 +1,128 @@
+/* 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 */
+
+/* Field name/descriptor for number of hits */
+#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
+
+/* 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_TIMESTAMP		= (1 << 1),
+	TRACEEVAL_FL_STATS		= (1 << 2)
+};
+
+/*
+ * Trace data entry for a traceeval histogram
+ * Constitutes keys and values.
+ */
+union traceeval_data {
+	char				*string;
+	struct traceeval_dynamic	*dyn_data;
+	unsigned long long		number_64;
+	unsigned long			number;
+	unsigned int			number_32;
+	unsigned short			number_16;
+	unsigned char			number_8;
+};
+
+/*
+ * 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 {
+	void		*data;
+	size_t		size;
+};
+
+/* struct traceeval_dynamic release function signature */
+typedef void (*traceeval_dyn_release_fn)(struct traceeval_dynamic *,
+		struct traceeval_type *);
+
+/* struct traceeval_dynamic compare function signature */
+typedef int (*traceeval_dyn_cmp_fn)(struct traceeval_dynamic *,
+		struct traceeval_dynamic *, struct traceeval_type *);
+
+/*
+ * 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 traceeval_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 traceeval_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
+ * 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 distinguish between
+ * different sub-types of struct traceeval_dynamic within a single
+ * callback function by examining the @id field. This is not a required
+ * approach, merely one that is accommodated.
+ *
+ * @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 other way 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 {
+	char				*name;
+	traceeval_dyn_release_fn	dyn_release;
+	traceeval_dyn_cmp_fn		dyn_cmp;
+	enum traceeval_data_type	type;
+	size_t				flags;
+	size_t				id;
+};
+
+/* Statistics about a given entry element */
+struct traceeval_stat {
+	unsigned long long	max;
+	unsigned long long	min;
+	unsigned long long	total;
+	unsigned long long	avg;
+	unsigned long long	std;
+};
+
+/* Iterator over aggregated data */
+struct traceeval_iterator;
+
+struct traceeval;
+
+#endif /* __LIBTRACEEVAL_HIST_H__ */
-- 
2.41.0

[PATCH v2 2/5] histograms: Add 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 +-
 include/traceeval-hist.h |   5 +
 src/Makefile             |   1 +
 src/histograms.c         | 223 +++++++++++++++++++++++++++++++++++++++
 4 files changed, 230 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/include/traceeval-hist.h b/include/traceeval-hist.h
index 4664974..5bea025 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -125,4 +125,9 @@ struct traceeval_iterator;
 
 struct traceeval;
 
+/* Histogram interfaces */
+
+struct traceeval *traceeval_init(const struct traceeval_type *keys,
+		const struct traceeval_type *vals);
+
 #endif /* __LIBTRACEEVAL_HIST_H__ */
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..be17b89
--- /dev/null
+++ b/src/histograms.c
@@ -0,0 +1,223 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval histogram interface implementation.
+ *
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
+ */
+
+#include <stdbool.h>
+#include <string.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+#include <traceeval-hist.h>
+
+/* 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		*key_types;
+	struct traceeval_type		*val_types;
+	struct hist_table		*hist;
+	size_t				nr_key_types;
+	size_t				nr_val_types;
+};
+
+/* Iterate over results of histogram */
+struct traceeval_iterator {};
+
+/*
+ * print_err() - print an error message
+ * @fmt: String format
+ * @...: (optional) Additional arguments to print in conjunction with @format
+ */
+static void print_err(const char *fmt, ...)
+{
+	va_list ap;
+
+	va_start(ap, fmt);
+	vfprintf(stderr, fmt, ap);
+	va_end(ap);
+	fprintf(stderr, "\n");
+}
+
+/*
+ * type_release() - free a struct traceeval_type array
+ * @defs: The array to release
+ * @len: The length of @defs
+ *
+ * It is assumed that all elements of @defs, within the length of @len, have
+ * name fields initialized to valid pointers.
+ *
+ * This function was designed to be used on an array allocated by type_alloc().
+ * Note that type_alloc() initializes all name fields of elements within the
+ * returned size.
+ */
+static void type_release(struct traceeval_type *defs, size_t len)
+{
+	if (!defs)
+		return;
+
+	for (size_t i = 0; i < len; i++) {
+		free(defs[i].name);
+	}
+
+	free(defs);
+}
+
+/*
+ * type_alloc() - clone a struct traceeval_type array
+ * @defs: The original array
+ * @copy: A pointer to where to place the @defs copy
+ *
+ * Clone traceeval_type array @defs to the heap, and place in @copy.
+ * @defs must be terminated with an instance of type TRACEEVAL_TYPE_NONE.
+ *
+ * The size of the copy pointed to by @copy is returned. It counts all elements
+ * in @defs excluding the terminating TRACEEVAL_TYPE_NONE traceeval_type.
+ * The copy contains everything from @defs excluding the TRACEEVAL_TYPE_NONE
+ * traceeval_type.
+ *
+ * The name field of each element of @defs (except for the terminating
+ * TRACEEVAL_TYPE_NONE) must be a NULL-terminated string. The validity of the
+ * name field is not checked, but errors are returned upon finding unset name
+ * fields and string duplication failures. It is guaranteed that all elements
+ * of the copy within the returned size have valid pointers in their name
+ * fields.
+ *
+ * Returns the size of the array pointed to by @copy, or, if an error occurs,
+ * the negative of the size of what's been allocated so far.
+ * If the return value is negative, the user is responsible for freeing
+ * -1 * return value number of elements from @copy.
+ */
+static size_t type_alloc(const struct traceeval_type *defs,
+		struct traceeval_type **copy)
+{
+	struct traceeval_type *new_defs = NULL;
+	size_t size;
+	size_t i;
+
+	if (!defs) {
+		*copy = NULL;
+		return 0;
+	}
+
+	for (size = 0; defs && defs[size].type != TRACEEVAL_TYPE_NONE; size++);
+
+	if (size) {
+		new_defs = calloc(size, sizeof(*new_defs));
+	} else {
+		*copy = NULL;
+		return 0;
+	}
+
+	for (i = 0; i < size; i++) {
+		/* copy current def data to new_def */
+		new_defs[i] = defs[i];
+
+		/* copy name to heap, ensures name copied */
+		if (!defs[i].name)
+			goto fail_type_name;
+		new_defs[i].name = strdup(defs[i].name);
+
+		if (!new_defs[i].name)
+			goto fail_type_name;
+	}
+
+	*copy = new_defs;
+	return size;
+
+fail_type_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);
+	*copy = new_defs;
+	return i * -1;
+}
+
+/*
+ * traceeval_init - create a traceeval descriptor
+ * @keys: Defines the keys to differentiate traceeval entries
+ * @vals: Defines values attached to entries differentiated by @keys.
+ *
+ * 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 "histogram". Note, both the @keys and @vals array must end with:
+ * { .type = TRACEEVAL_TYPE_NONE }.
+ *
+ * The @keys and @vals passed in are copied for internal use.
+ *
+ * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
+ * the name field must be a null-terminated string. For members of type
+ * TRACEEVAL_TYPE_NONE, the name is ignored.
+ *
+ * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
+ * define the values of the histogram to be empty.
+ * @keys must be populated with at least one element that is not
+ * TRACEEVAL_TYPE_NONE.
+ *
+ * Returns the descriptor on success, or NULL on error.
+ */
+struct traceeval *traceeval_init(const struct traceeval_type *keys,
+				 const struct traceeval_type *vals)
+{
+	struct traceeval *teval;
+	char *err_msg;
+
+	if (!keys)
+		return NULL;
+
+	if (keys->type == TRACEEVAL_TYPE_NONE) {
+		err_msg = "keys cannot start with type TRACEEVAL_TYPE_NONE";
+		goto fail_init_unalloced;
+	}
+
+	/* alloc teval */
+	teval = calloc(1, sizeof(*teval));
+	if (!teval) {
+		err_msg = "failed to allocate memory for traceeval instance";
+		goto fail_init_unalloced;
+	}
+
+	/* alloc key types */
+	teval->nr_key_types = type_alloc(keys, &teval->key_types);
+	if (teval->nr_key_types <= 0) {
+		teval->nr_key_types *= -1;
+		err_msg = "failed to allocate user defined keys";
+		goto fail_init;
+	}
+
+	/* alloc val types */
+	teval->nr_val_types = type_alloc(vals, &teval->val_types);
+	if (teval->nr_val_types < 0) {
+		teval->nr_val_types *= -1;
+		err_msg = "failed to allocate user defined values";
+		goto fail_init;
+	}
+
+	/* alloc hist */
+	teval->hist = calloc(1, sizeof(*teval->hist));
+	if (!teval->hist) {
+		err_msg = "failed to allocate memory for histogram";
+		goto fail_init;
+	}
+
+	return teval;
+
+fail_init:
+	traceeval_release(teval);
+
+fail_init_unalloced:
+	print_err(err_msg);
+	return NULL;
+}
-- 
2.41.0

[PATCH v2 3/5] histograms: Add 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 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>
---
 include/traceeval-hist.h |  2 +
 src/histograms.c         | 84 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 86 insertions(+)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 5bea025..cd74d3e 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -130,4 +130,6 @@ struct traceeval;
 struct traceeval *traceeval_init(const struct traceeval_type *keys,
 		const struct traceeval_type *vals);
 
+void traceeval_release(struct traceeval *teval);
+
 #endif /* __LIBTRACEEVAL_HIST_H__ */
diff --git a/src/histograms.c b/src/histograms.c
index be17b89..95243b0 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -221,3 +221,87 @@ fail_init_unalloced:
 	print_err(err_msg);
 	return NULL;
 }
+
+/*
+ * Free any specified dynamic data in @data.
+ */
+static void clean_data(union traceeval_data *data, struct traceeval_type *defs,
+		size_t size)
+{
+	size_t i;
+
+	if (!data || !defs)
+		return;
+
+	for (i = 0; i < size; i++) {
+		switch (defs[i].type) {
+		case TRACEEVAL_TYPE_STRING:
+			free(data[i].string);
+			break;
+		case TRACEEVAL_TYPE_DYNAMIC:
+			if (defs[i].dyn_release)
+				defs[i].dyn_release(data[i].dyn_data, &defs[i]);
+			break;
+		default:
+			break;
+		}
+	}
+}
+
+/*
+ * Free all possible data stored within the entry.
+ */
+static void clean_entry(struct entry *entry, struct traceeval *teval)
+{
+	if (!entry)
+		return;
+
+	/* free dynamic traceeval_data */
+	clean_data(entry->keys, teval->key_types, teval->nr_key_types);
+	clean_data(entry->vals, teval->val_types, teval->nr_val_types);
+	free(entry->keys);
+	free(entry->vals);
+}
+
+/*
+ * Free 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);
+	teval->hist = NULL;
+}
+
+/*
+ * 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 frees all internally allocated data of @teval and will call the
+ * corresponding dyn_release() functions registered for keys and values of
+ * type TRACEEVAL_TYPE_DYNAMIC.
+ */
+void traceeval_release(struct traceeval *teval)
+{
+	if (!teval)
+		return;
+
+	hist_table_release(teval);
+	type_release(teval->key_types, teval->nr_key_types);
+	type_release(teval->val_types, teval->nr_val_types);
+	teval->key_types = NULL;
+	teval->val_types = NULL;
+	free(teval);
+}
-- 
2.41.0

[PATCH v2 4/5] histograms: Add 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>
---
 include/traceeval-test.h |  16 +++
 src/histograms.c         | 221 ++++++++++++++++++++++++++++++++++++++-
 2 files changed, 234 insertions(+), 3 deletions(-)
 create mode 100644 include/traceeval-test.h

diff --git a/include/traceeval-test.h b/include/traceeval-test.h
new file mode 100644
index 0000000..bb8092a
--- /dev/null
+++ b/include/traceeval-test.h
@@ -0,0 +1,16 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval interface for unit testing.
+ *
+ * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
+ */
+
+#ifndef __LIBTRACEEVAL_TEST_H__
+#define __LIBTRACEEVAL_TEST_H__
+
+#include <traceeval-hist.h>
+
+int traceeval_compare(struct traceeval *orig, struct traceeval *copy);
+
+#endif /* __LIBTRACEEVAL_TEST_H__ */
diff --git a/src/histograms.c b/src/histograms.c
index 95243b0..8094678 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -11,6 +11,20 @@
 #include <stdio.h>
 
 #include <traceeval-hist.h>
+#include <traceeval-test.h>
+
+/*
+ * 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 {
@@ -158,12 +172,13 @@ fail_type_name:
  * The @keys and @vals passed in are copied for internal use.
  *
  * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
- * the name field must be a null-terminated string. For members of type
- * TRACEEVAL_TYPE_NONE, the name is ignored.
+ * the name field must be a null-terminated string. Members of type
+ * TRACEEVAL_TYPE_NONE are used to terminate the array, therefore their other
+ * fields are ignored.
  *
  * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
  * define the values of the histogram to be empty.
- * @keys must be populated with at least one element that is not
+ * @keys must be populated with at least one element that is not of type
  * TRACEEVAL_TYPE_NONE.
  *
  * Returns the descriptor on success, or NULL on error.
@@ -305,3 +320,203 @@ void traceeval_release(struct traceeval *teval)
 	teval->val_types = NULL;
 	free(teval);
 }
+
+/*
+ * Compare traceeval_type instances for equality.
+ *
+ * Return 0 if @orig and @copy are the same, 1 otherwise.
+ */
+static int compare_traceeval_type(struct traceeval_type *orig,
+		struct traceeval_type *copy, size_t orig_size, size_t copy_size)
+{
+	size_t i;
+
+	/* same memory/NULL */
+	if (orig == copy)
+		return 0;
+	if (!!orig != !!copy)
+		return 1;
+
+	if (orig_size != copy_size)
+		return 1;
+
+	for (i = 0; i < orig_size; i++) {
+		if (orig[i].type != copy[i].type)
+			return 1;
+		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
+		if (!!orig[i].name != !!copy[i].name)
+			return 1;
+		if (!orig[i].name)
+			continue;
+		if (strcmp(orig[i].name, copy[i].name) != 0)
+			return 1;
+	}
+
+	return 0;
+}
+
+/*
+ * Compare traceeval_data instances.
+ *
+ * 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)
+{
+	int i;
+
+	if (orig == copy)
+		return 0;
+
+	if (!orig)
+		return -1;
+
+	if (!copy)
+		return 1;
+
+	switch (type->type) {
+	case TRACEEVAL_TYPE_STRING:
+		i = strcmp(orig->string, copy->string);
+		compare_numbers_return(i, 0);
+
+	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:
+		if (type->dyn_cmp)
+			return type->dyn_cmp(orig->dyn_data, copy->dyn_data, type);
+		return 0;
+
+	default:
+		print_err("%d is an invalid enum traceeval_data_type member",
+				type->type);
+		return -2;
+	}
+}
+
+/*
+ * Compare arrays of 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 *defs,
+		size_t size)
+{
+	int check;
+	size_t i;
+
+	/* compare data arrays */
+	for (i = 0; i < size; i++) {
+		if ((check = compare_traceeval_data(&orig[i], &copy[i], &defs[i])))
+			goto fail_c_set;
+	}
+
+	return 0;
+
+fail_c_set:
+	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->key_types, teval->nr_key_types);
+	if (check)
+		return check;
+
+	/* compare values */
+	check = compare_traceeval_data_set(orig->vals, copy->vals,
+			teval->val_types, teval->nr_val_types);
+	return check;
+}
+
+/*
+ * Compares the hist fields of @orig and @copy for equality.
+ *
+ * Assumes all other aspects of @orig and @copy are the same.
+ *
+ * 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;
+	struct hist_table *c_hist;
+	int c;
+
+	o_hist = orig->hist;
+	c_hist = copy->hist;
+
+	if (o_hist->nr_entries != c_hist->nr_entries)
+		return 1;
+
+	for (size_t i = 0; i < o_hist->nr_entries; i++) {
+		if ((c = compare_entries(&o_hist->map[i], &c_hist->map[i], orig)))
+			return c;
+	}
+
+	return 0;
+}
+
+/*
+ * 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)
+{
+	int keys;
+	int vals;
+	int hists;
+
+	if (!orig || !copy)
+		return -1;
+
+	keys = compare_traceeval_type(orig->key_types, copy->key_types,
+			orig->nr_key_types, copy->nr_key_types);
+	vals = compare_traceeval_type(orig->val_types, copy->val_types,
+			orig->nr_val_types, copy->nr_val_types);
+	hists = compare_hist(orig, copy);
+
+	if (hists == -1)
+		return -1;
+
+	return keys || vals || hists;
+}
-- 
2.41.0

[PATCH v2 5/5] histograms: Initial 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>
---
 include/traceeval-test.h |   1 -
 utest/.gitignore         |   1 +
 utest/Makefile           |  35 +++++++
 utest/eval-test.h        |  13 +++
 utest/eval-utest.c       |  28 +++++
 utest/traceeval-utest.c  | 217 +++++++++++++++++++++++++++++++++++++++
 6 files changed, 294 insertions(+), 1 deletion(-)
 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/include/traceeval-test.h b/include/traceeval-test.h
index bb8092a..45cf13b 100644
--- a/include/traceeval-test.h
+++ b/include/traceeval-test.h
@@ -2,7 +2,6 @@
 /*
  * libtraceeval interface for unit testing.
  *
- * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
  * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
  */
 
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..f6e594e
--- /dev/null
+++ b/utest/eval-test.h
@@ -0,0 +1,13 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval cunit interface.
+ *
+ * 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..94d04c6
--- /dev/null
+++ b/utest/eval-utest.c
@@ -0,0 +1,28 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval cunit handler.
+ *
+ * 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..de23821
--- /dev/null
+++ b/utest/traceeval-utest.c
@@ -0,0 +1,217 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
+ */
+
+#include <CUnit/CUnit.h>
+#include <CUnit/Basic.h>
+#include <stdbool.h>
+#include <string.h>
+#include <stdio.h>
+
+#include <traceeval-hist.h>
+#include <traceeval-test.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.
+ */
+static void test_eval_null(void)
+{
+	/* set up */
+	const struct traceeval_type test_data[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "test null"
+		},
+		{
+			.type = TRACEEVAL_TYPE_NONE,
+			.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().
+ */
+static 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.
+ */
+static void test_eval_none(void)
+{
+	/* set up */
+	const struct traceeval_type test_data_none[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NONE,
+			.name = "test none"
+		}
+	};
+	const struct traceeval_type test_data_some[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "test none (some)"
+		},
+		{
+			.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.
+ */
+static void test_eval_same(void)
+{
+	/* set up */
+	const struct traceeval_type test_data[] =  {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "test data"
+		},
+		{
+			.type = TRACEEVAL_TYPE_NONE,
+			.name = NULL
+		}
+	};
+
+	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.
+ */
+static 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.
+ */
+static 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 v2 0/5] histograms: bug fixes and convention compliance

[Steven Rostedt]

On Thu,  3 Aug 2023 18:53:58 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> From: "Stevie Alvarez (Google)" <stevie.6strings@gmail.com>
> 
> Changes in v2:
>  * Renamed interface from histograms.h to traceeval-hist.h.
>  * Internal traceeval_type arrays terminated by size rather than type.
>  * type_alloc() guarantees traceeval_type name field is a valid pointer.
>  * traceeval_release() sets released pointers to NULL.
>  * Conditional simplifications and fixes across the board. 
>  * Removed function stubs and their interface definitions.
>  * Added a timestamp flag.
>  * Added typedefs for traceeval_dynamic helper function signatures. 
>  * Documentation follows established conventions (kernel docs, line comments).
>  * Documentation moved from interface to source code.
>  * Internal testing interface.
>  * General documentation spell checking.
> 
> Since the addition of the traceeval_dynamic function signature typedefs,
> warnings pertaining to these function signatures and traceeval_type have
> popped up. Steven, Ross, and anyone else, any ideas on why these
> warnings are showing up?
> 
> Warning from function signatures in include/traceeval-hist.h, line 65 and 69:
> 	warning: ‘struct traceeval_type’ declared inside parameter list will
> 	not be visible outside of this definition or declaration
> 
> 		struct traceeval_type *);

This is because the typedef is before the declaration. Just add:

struct traceeval_type;

above it.

> 
> Warning from dyn_release call in src/histograms.c line 258:
> 	warning: passing argument 2 of
> 	‘(defs + (sizetype)(i * 48))->dyn_release’ from incompatible
> 	pointer type
> 
> 		defs[i].dyn_release(data[i].dyn_data, &defs[i]);

Try passing in: defs + i

I'll review these later today.

-- Steve

> 
> 	note: expected ‘struct traceeval_type *’ but argument is of type
> 	‘struct traceeval_type *’
> 
> Warning from dyn_cmp call in src/histograms.c line 409:
> 	warning: passing argument 3 of ‘type->dyn_cmp’ from incompatible
> 	pointer type
> 
> 		return type->dyn_cmp(orig->dyn_data, copy->dyn_data, type);
> 
> 	note: expected ‘struct traceeval_type *’ but argument is of type
> 	‘struct traceeval_type *’
> 
> ---
> v1 discussion: https://lore.kernel.org/linux-trace-devel/20230731212542.3fb668b1@gandalf.local.home/T/
> 
> Stevie Alvarez (Google) (5):
>   histograms: Initial histograms interface
>   histograms: Add traceeval initialize
>   histograms: Add traceeval release
>   histograms: Add traceeval compare
>   histograms: Initial unit tests
> 
>  Makefile                 |   2 +-
>  include/traceeval-hist.h | 135 ++++++++++
>  include/traceeval-test.h |  15 ++
>  src/Makefile             |   1 +
>  src/histograms.c         | 522 +++++++++++++++++++++++++++++++++++++++
>  utest/.gitignore         |   1 +
>  utest/Makefile           |  35 +++
>  utest/eval-test.h        |  13 +
>  utest/eval-utest.c       |  28 +++
>  utest/traceeval-utest.c  | 217 ++++++++++++++++
>  10 files changed, 968 insertions(+), 1 deletion(-)
>  create mode 100644 include/traceeval-hist.h
>  create mode 100644 include/traceeval-test.h
>  create mode 100644 src/histograms.c
>  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
> 

Re: [PATCH v2 1/5] histograms: Initial histograms interface

[Steven Rostedt]

On Thu,  3 Aug 2023 18:53:59 -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/traceeval-hist.h | 128 +++++++++++++++++++++++++++++++++++++++
>  1 file changed, 128 insertions(+)
>  create mode 100644 include/traceeval-hist.h
> 
> diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> new file mode 100644
> index 0000000..4664974
> --- /dev/null
> +++ b/include/traceeval-hist.h
> @@ -0,0 +1,128 @@
> +/* 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 */
> +
> +/* Field name/descriptor for number of hits */
> +#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
> +
> +/* 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,

Hmm, I'm thinking it would be nice to rearrange this a bit to:

enum traceeval_data_type {
	TRACEEVAL_TYPE_NONE,
	TRACEEVAL_TYPE_NUMBER_8,
	TRACEEVAL_TYPE_NUMBER_16,
	TRACEEVAL_TYPE_NUMBER_32,
	TRACEEVAL_TYPE_NUMBER_64,
	TRACEEVAL_TYPE_NUMBER,
	TRACEEVAL_TYPE_STRING,

That way NUMBER_8 will be 1, NUMBER_16 is 2, NUMBER_32 is 3 and NUMBER_64
is 4. If we ever wanted to do a trick, we can get the byte size from:

  2^(1 * (enum - 1))

  2^(1 * (NUMBER_8 - 1))  = 2^(1 * 0) = 1
  2^(1 * (NUMBER_16 - 1)) = 2^(1 * 1) = 2
  2^(1 * (NUMBER_32 - 1)) = 2^(1 * 2) = 4
  2^(1 * (NUMBER_64 - 1)) = 2^(1 * 3) = 8

I love hacks!


> +	TRACEEVAL_TYPE_DYNAMIC
> +};
> +
> +/* Statistics specification flags */
> +enum traceeval_flags {
> +	TRACEEVAL_FL_SIGNED		= (1 << 0),
> +	TRACEEVAL_FL_TIMESTAMP		= (1 << 1),
> +	TRACEEVAL_FL_STATS		= (1 << 2)

We may as well remove STATS until we decided to use it.

Maybe even get rid of this enum until we decide to use it.

Remember, once it's exposed, it is API.

> +};
> +
> +/*
> + * Trace data entry for a traceeval histogram
> + * Constitutes keys and values.
> + */
> +union traceeval_data {
> +	char				*string;
> +	struct traceeval_dynamic	*dyn_data;
> +	unsigned long long		number_64;
> +	unsigned long			number;
> +	unsigned int			number_32;
> +	unsigned short			number_16;
> +	unsigned char			number_8;
> +};
> +
> +/*
> + * 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 {
> +	void		*data;
> +	size_t		size;
> +};
> +

As I replied to the cover letter, you need to add:

struct traceeval_type;

to get rid of the warning.

> +/* struct traceeval_dynamic release function signature */
> +typedef void (*traceeval_dyn_release_fn)(struct traceeval_dynamic *,
> +		struct traceeval_type *);
> +
> +/* struct traceeval_dynamic compare function signature */
> +typedef int (*traceeval_dyn_cmp_fn)(struct traceeval_dynamic *,
> +		struct traceeval_dynamic *, struct traceeval_type *);
> +
> +/*
> + * 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 traceeval_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 traceeval_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
> + * 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 distinguish between
> + * different sub-types of struct traceeval_dynamic within a single
> + * callback function by examining the @id field. This is not a required
> + * approach, merely one that is accommodated.
> + *
> + * @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 other way 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 {
> +	char				*name;
> +	traceeval_dyn_release_fn	dyn_release;
> +	traceeval_dyn_cmp_fn		dyn_cmp;
> +	enum traceeval_data_type	type;
> +	size_t				flags;
> +	size_t				id;

Let's reorder this a little. Normally function pointers come at the end of
a structure. That's more of a guideline than a rule, but let's have it here.

struct traceeval_type {
	char				*name;
	enum traceeval_data_type	type;
	size_t				flags;
	size_t				id;
	traceeval_dyn_release_fn	dyn_release;
	traceeval_dyn_cmp_fn		dyn_cmp;
};

Especially since dynamic types are going to be rare, we don't want it in
the hot cache.

-- Steve


> +};
> +
> +/* Statistics about a given entry element */
> +struct traceeval_stat {
> +	unsigned long long	max;
> +	unsigned long long	min;
> +	unsigned long long	total;
> +	unsigned long long	avg;
> +	unsigned long long	std;
> +};
> +
> +/* Iterator over aggregated data */
> +struct traceeval_iterator;
> +
> +struct traceeval;
> +
> +#endif /* __LIBTRACEEVAL_HIST_H__ */

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

[Steven Rostedt]

On Thu,  3 Aug 2023 18:54:00 -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 +-
>  include/traceeval-hist.h |   5 +
>  src/Makefile             |   1 +
>  src/histograms.c         | 223 +++++++++++++++++++++++++++++++++++++++
>  4 files changed, 230 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

This seems like it doesn't belong in this patch.

>  
>  test: force $(LIBRARY_STATIC)
>  ifneq ($(CUNIT_INSTALLED),1)
> diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> index 4664974..5bea025 100644
> --- a/include/traceeval-hist.h
> +++ b/include/traceeval-hist.h
> @@ -125,4 +125,9 @@ struct traceeval_iterator;
>  
>  struct traceeval;
>  
> +/* Histogram interfaces */
> +
> +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> +		const struct traceeval_type *vals);
> +
>  #endif /* __LIBTRACEEVAL_HIST_H__ */
> 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..be17b89
> --- /dev/null
> +++ b/src/histograms.c
> @@ -0,0 +1,223 @@
> +/* SPDX-License-Identifier: MIT */
> +/*
> + * libtraceeval histogram interface implementation.
> + *
> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +
> +#include <stdbool.h>
> +#include <string.h>
> +#include <stdarg.h>
> +#include <stdio.h>
> +
> +#include <traceeval-hist.h>
> +
> +/* 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		*key_types;
> +	struct traceeval_type		*val_types;
> +	struct hist_table		*hist;
> +	size_t				nr_key_types;
> +	size_t				nr_val_types;
> +};
> +
> +/* Iterate over results of histogram */
> +struct traceeval_iterator {};

Add the traceeval_iterator struct when it is used.

It's not relevant to this patch.

> +
> +/*
> + * print_err() - print an error message
> + * @fmt: String format
> + * @...: (optional) Additional arguments to print in conjunction with @format
> + */
> +static void print_err(const char *fmt, ...)
> +{
> +	va_list ap;
> +
> +	va_start(ap, fmt);
> +	vfprintf(stderr, fmt, ap);
> +	va_end(ap);
> +	fprintf(stderr, "\n");
> +}
> +
> +/*
> + * type_release() - free a struct traceeval_type array
> + * @defs: The array to release
> + * @len: The length of @defs
> + *
> + * It is assumed that all elements of @defs, within the length of @len, have
> + * name fields initialized to valid pointers.
> + *
> + * This function was designed to be used on an array allocated by type_alloc().
> + * Note that type_alloc() initializes all name fields of elements within the
> + * returned size.
> + */
> +static void type_release(struct traceeval_type *defs, size_t len)

You added this but did not add traceeval_release().

traceeval_release() should be added in this patch to clean up everything
that traceeval_init() creates.

> +{
> +	if (!defs)
> +		return;
> +
> +	for (size_t i = 0; i < len; i++) {
> +		free(defs[i].name);
> +	}
> +
> +	free(defs);
> +}
> +
> +/*
> + * type_alloc() - clone a struct traceeval_type array
> + * @defs: The original array
> + * @copy: A pointer to where to place the @defs copy
> + *
> + * Clone traceeval_type array @defs to the heap, and place in @copy.
> + * @defs must be terminated with an instance of type TRACEEVAL_TYPE_NONE.
> + *
> + * The size of the copy pointed to by @copy is returned. It counts all elements
> + * in @defs excluding the terminating TRACEEVAL_TYPE_NONE traceeval_type.
> + * The copy contains everything from @defs excluding the TRACEEVAL_TYPE_NONE
> + * traceeval_type.
> + *
> + * The name field of each element of @defs (except for the terminating
> + * TRACEEVAL_TYPE_NONE) must be a NULL-terminated string. The validity of the
> + * name field is not checked, but errors are returned upon finding unset name
> + * fields and string duplication failures. It is guaranteed that all elements
> + * of the copy within the returned size have valid pointers in their name
> + * fields.
> + *
> + * Returns the size of the array pointed to by @copy, or, if an error occurs,
> + * the negative of the size of what's been allocated so far.
> + * If the return value is negative, the user is responsible for freeing
> + * -1 * return value number of elements from @copy.
> + */
> +static size_t type_alloc(const struct traceeval_type *defs,
> +		struct traceeval_type **copy)
> +{
> +	struct traceeval_type *new_defs = NULL;
> +	size_t size;
> +	size_t i;
> +
> +	if (!defs) {
> +		*copy = NULL;
> +		return 0;
> +	}
> +
> +	for (size = 0; defs && defs[size].type != TRACEEVAL_TYPE_NONE; size++);

For loops like the above, please do:

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

This makes it obvious that it's an empty loop and we don't think it's
looping over the line below it.

> +
> +	if (size) {
> +		new_defs = calloc(size, sizeof(*new_defs));
> +	} else {
> +		*copy = NULL;
> +		return 0;
> +	}
> +
> +	for (i = 0; i < size; i++) {
> +		/* copy current def data to new_def */
> +		new_defs[i] = defs[i];
> +
> +		/* copy name to heap, ensures name copied */
> +		if (!defs[i].name)
> +			goto fail_type_name;

No need to be so verbose in the labels.

			goto fail;

is good enough ;-)

> +		new_defs[i].name = strdup(defs[i].name);
> +
> +		if (!new_defs[i].name)
> +			goto fail_type_name;
> +	}
> +
> +	*copy = new_defs;
> +	return size;
> +
> +fail_type_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);

I would change the above to:

	if (defs[i].name)
		print_err("Failed to allocate traceveal_type %zu", size);
	else
		print_err("traceeval_type list missing a name");

> +	*copy = new_defs;
> +	return i * -1;

Also, we need to clean up here and not pass that info back to the caller.

// need to make i: ssize_t i;

	for (; i >= 0; i--)
		free(new_defs[i].name);
	free(new_defs);
	*copy = NULL;
	return -1;


> +}
> +
> +/*
> + * traceeval_init - create a traceeval descriptor
> + * @keys: Defines the keys to differentiate traceeval entries
> + * @vals: Defines values attached to entries differentiated by @keys.
> + *
> + * 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 "histogram". Note, both the @keys and @vals array must end with:
> + * { .type = TRACEEVAL_TYPE_NONE }.
> + *
> + * The @keys and @vals passed in are copied for internal use.
> + *
> + * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
> + * the name field must be a null-terminated string. For members of type
> + * TRACEEVAL_TYPE_NONE, the name is ignored.
> + *
> + * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
> + * define the values of the histogram to be empty.
> + * @keys must be populated with at least one element that is not
> + * TRACEEVAL_TYPE_NONE.
> + *
> + * Returns the descriptor on success, or NULL on error.
> + */
> +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> +				 const struct traceeval_type *vals)
> +{
> +	struct traceeval *teval;
> +	char *err_msg;
> +
> +	if (!keys)
> +		return NULL;
> +
> +	if (keys->type == TRACEEVAL_TYPE_NONE) {
> +		err_msg = "keys cannot start with type TRACEEVAL_TYPE_NONE";

BTW, all the error messages should start with a capital letter.

			"Keys cannot .."

> +		goto fail_init_unalloced;

Just make this: goto fail;

> +	}
> +
> +	/* alloc teval */
> +	teval = calloc(1, sizeof(*teval));
> +	if (!teval) {
> +		err_msg = "failed to allocate memory for traceeval instance";
> +		goto fail_init_unalloced;
> +	}
> +
> +	/* alloc key types */
> +	teval->nr_key_types = type_alloc(keys, &teval->key_types);
> +	if (teval->nr_key_types <= 0) {
> +		teval->nr_key_types *= -1;

Get rid of the above setting.

> +		err_msg = "failed to allocate user defined keys";
> +		goto fail_init;

and this: goto fail_release;

> +	}
> +
> +	/* alloc val types */
> +	teval->nr_val_types = type_alloc(vals, &teval->val_types);
> +	if (teval->nr_val_types < 0) {
> +		teval->nr_val_types *= -1;

And git rid of the above too.

> +		err_msg = "failed to allocate user defined values";
> +		goto fail_init;
> +	}
> +
> +	/* alloc hist */
> +	teval->hist = calloc(1, sizeof(*teval->hist));
> +	if (!teval->hist) {
> +		err_msg = "failed to allocate memory for histogram";
> +		goto fail_init;
> +	}
> +
> +	return teval;
> +
> +fail_init:
> +	traceeval_release(teval);

The above isn't defined. If you reference a function in a patch, it must be
at least defined.

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

-- Steve

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

[Steven Rostedt]

On Thu,  3 Aug 2023 18:54:01 -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 entries to the histogram,
> and the names allocated for the struct traceeval_type key-value
> definitions.
> 

As this is referenced in the first patch, please fold this patch into the
first one. It's fine to add both the init and the releaese (alloc and free)
functions in one patch. In fact, they should be together because those
functions are tightly coupled.


The idea is that every patch should do "one thing", but an alloc should
always be accompanied by a free. As a whole, it's "one thing", and OK to be
in one patch/commit.

It also makes it easier to review. When they are separate patches, I can't
go and look to see if something allocated was later freed. Having them as
two patches makes it more likely to introduce an error.

> Signed-off-by: Stevie Alvarez (Google) <stevie.6strings@gmail.com>
> ---
>  include/traceeval-hist.h |  2 +
>  src/histograms.c         | 84 ++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 86 insertions(+)
> 
> diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> index 5bea025..cd74d3e 100644
> --- a/include/traceeval-hist.h
> +++ b/include/traceeval-hist.h
> @@ -130,4 +130,6 @@ struct traceeval;
>  struct traceeval *traceeval_init(const struct traceeval_type *keys,
>  		const struct traceeval_type *vals);
>  
> +void traceeval_release(struct traceeval *teval);
> +
>  #endif /* __LIBTRACEEVAL_HIST_H__ */
> diff --git a/src/histograms.c b/src/histograms.c
> index be17b89..95243b0 100644
> --- a/src/histograms.c
> +++ b/src/histograms.c
> @@ -221,3 +221,87 @@ fail_init_unalloced:
>  	print_err(err_msg);
>  	return NULL;
>  }
> +
> +/*
> + * Free any specified dynamic data in @data.
> + */
> +static void clean_data(union traceeval_data *data, struct traceeval_type *defs,
> +		size_t size)
> +{
> +	size_t i;
> +
> +	if (!data || !defs)
> +		return;

Perhaps the above should have:

	if (!data || !defs) {
		if (data)
			print_err("Data to be freed without accompanied types!");
	}


> +
> +	for (i = 0; i < size; i++) {
> +		switch (defs[i].type) {
> +		case TRACEEVAL_TYPE_STRING:
> +			free(data[i].string);
> +			break;
> +		case TRACEEVAL_TYPE_DYNAMIC:
> +			if (defs[i].dyn_release)
> +				defs[i].dyn_release(data[i].dyn_data, &defs[i]);

I just realized, you should make the release function define as:

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

As the function is really a method of the struct typeeval_type. And the
usually way is to have the "this" pointer as the first parameter of the
method function. The traceeval_type is the "this" in this case.

Also, for all functions, the parameters should line up with the open
parenthesis.

Instead of:

static size_t type_alloc(const struct traceeval_type *defs,
		struct traceeval_type **copy)

It should always be:

static size_t type_alloc(const struct traceeval_type *defs,
			 struct traceeval_type **copy)


See how easier it is to read the function name, and differentiate it from
the parameters.

Same for the typedef (notice how I lined it up above?). It makes it easier
to see what the name of the function type is.

-- Steve




> +			break;
> +		default:
> +			break;
> +		}
> +	}
> +}
> +
> +/*
> + * Free all possible data stored within the entry.
> + */
> +static void clean_entry(struct entry *entry, struct traceeval *teval)
> +{
> +	if (!entry)
> +		return;
> +
> +	/* free dynamic traceeval_data */
> +	clean_data(entry->keys, teval->key_types, teval->nr_key_types);
> +	clean_data(entry->vals, teval->val_types, teval->nr_val_types);
> +	free(entry->keys);
> +	free(entry->vals);
> +}
> +
> +/*
> + * Free 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);
> +	teval->hist = NULL;
> +}
> +
> +/*
> + * 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 frees all internally allocated data of @teval and will call the
> + * corresponding dyn_release() functions registered for keys and values of
> + * type TRACEEVAL_TYPE_DYNAMIC.
> + */
> +void traceeval_release(struct traceeval *teval)
> +{
> +	if (!teval)
> +		return;
> +
> +	hist_table_release(teval);
> +	type_release(teval->key_types, teval->nr_key_types);
> +	type_release(teval->val_types, teval->nr_val_types);
> +	teval->key_types = NULL;
> +	teval->val_types = NULL;
> +	free(teval);
> +}

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

[Steven Rostedt]

On Thu,  3 Aug 2023 18:54:02 -0400
Stevie Alvarez <stevie.6strings@gmail.com> 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>
> ---
>  include/traceeval-test.h |  16 +++
>  src/histograms.c         | 221 ++++++++++++++++++++++++++++++++++++++-
>  2 files changed, 234 insertions(+), 3 deletions(-)
>  create mode 100644 include/traceeval-test.h
> 
> diff --git a/include/traceeval-test.h b/include/traceeval-test.h
> new file mode 100644
> index 0000000..bb8092a
> --- /dev/null
> +++ b/include/traceeval-test.h
> @@ -0,0 +1,16 @@
> +/* SPDX-License-Identifier: MIT */
> +/*
> + * libtraceeval interface for unit testing.
> + *
> + * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>

I noticed that you deleted the above line in the next patch, it just
shouldn't be added in this one.

Also, it shouldn't be in the include/ directory, as we don't want to add
this to the system on install.

This is just for testing, let's keep the function in the utest/ directory,
as well as the header file.

Feel free to add a file there to store this.

-- Steve



> + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> + */
> +
> +#ifndef __LIBTRACEEVAL_TEST_H__
> +#define __LIBTRACEEVAL_TEST_H__
> +
> +#include <traceeval-hist.h>
> +
> +int traceeval_compare(struct traceeval *orig, struct traceeval *copy);
> +
> +#endif /* __LIBTRACEEVAL_TEST_H__ */
> diff --git a/src/histograms.c b/src/histograms.c
> index 95243b0..8094678 100644
> --- a/src/histograms.c
> +++ b/src/histograms.c
> @@ -11,6 +11,20 @@
>  #include <stdio.h>
>  
>  #include <traceeval-hist.h>
> +#include <traceeval-test.h>
> +
> +/*
> + * 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 {
> @@ -158,12 +172,13 @@ fail_type_name:
>   * The @keys and @vals passed in are copied for internal use.
>   *
>   * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
> - * the name field must be a null-terminated string. For members of type
> - * TRACEEVAL_TYPE_NONE, the name is ignored.
> + * the name field must be a null-terminated string. Members of type
> + * TRACEEVAL_TYPE_NONE are used to terminate the array, therefore their other
> + * fields are ignored.
>   *
>   * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
>   * define the values of the histogram to be empty.
> - * @keys must be populated with at least one element that is not
> + * @keys must be populated with at least one element that is not of type
>   * TRACEEVAL_TYPE_NONE.
>   *
>   * Returns the descriptor on success, or NULL on error.
> @@ -305,3 +320,203 @@ void traceeval_release(struct traceeval *teval)
>  	teval->val_types = NULL;
>  	free(teval);
>  }
> +
> +/*
> + * Compare traceeval_type instances for equality.
> + *
> + * Return 0 if @orig and @copy are the same, 1 otherwise.
> + */
> +static int compare_traceeval_type(struct traceeval_type *orig,
> +		struct traceeval_type *copy, size_t orig_size, size_t copy_size)
> +{
> +	size_t i;
> +
> +	/* same memory/NULL */
> +	if (orig == copy)
> +		return 0;
> +	if (!!orig != !!copy)
> +		return 1;
> +
> +	if (orig_size != copy_size)
> +		return 1;
> +
> +	for (i = 0; i < orig_size; i++) {
> +		if (orig[i].type != copy[i].type)
> +			return 1;
> +		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
> +		if (!!orig[i].name != !!copy[i].name)
> +			return 1;
> +		if (!orig[i].name)
> +			continue;
> +		if (strcmp(orig[i].name, copy[i].name) != 0)
> +			return 1;
> +	}
> +
> +	return 0;
> +}
> +
> +/*
> + * Compare traceeval_data instances.
> + *
> + * 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)
> +{
> +	int i;
> +
> +	if (orig == copy)
> +		return 0;
> +
> +	if (!orig)
> +		return -1;
> +
> +	if (!copy)
> +		return 1;
> +
> +	switch (type->type) {
> +	case TRACEEVAL_TYPE_STRING:
> +		i = strcmp(orig->string, copy->string);
> +		compare_numbers_return(i, 0);
> +
> +	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:
> +		if (type->dyn_cmp)
> +			return type->dyn_cmp(orig->dyn_data, copy->dyn_data, type);
> +		return 0;
> +
> +	default:
> +		print_err("%d is an invalid enum traceeval_data_type member",
> +				type->type);
> +		return -2;
> +	}
> +}
> +
> +/*
> + * Compare arrays of 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 *defs,
> +		size_t size)
> +{
> +	int check;
> +	size_t i;
> +
> +	/* compare data arrays */
> +	for (i = 0; i < size; i++) {
> +		if ((check = compare_traceeval_data(&orig[i], &copy[i], &defs[i])))
> +			goto fail_c_set;
> +	}
> +
> +	return 0;
> +
> +fail_c_set:
> +	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->key_types, teval->nr_key_types);
> +	if (check)
> +		return check;
> +
> +	/* compare values */
> +	check = compare_traceeval_data_set(orig->vals, copy->vals,
> +			teval->val_types, teval->nr_val_types);
> +	return check;
> +}
> +
> +/*
> + * Compares the hist fields of @orig and @copy for equality.
> + *
> + * Assumes all other aspects of @orig and @copy are the same.
> + *
> + * 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;
> +	struct hist_table *c_hist;
> +	int c;
> +
> +	o_hist = orig->hist;
> +	c_hist = copy->hist;
> +
> +	if (o_hist->nr_entries != c_hist->nr_entries)
> +		return 1;
> +
> +	for (size_t i = 0; i < o_hist->nr_entries; i++) {
> +		if ((c = compare_entries(&o_hist->map[i], &c_hist->map[i], orig)))
> +			return c;
> +	}
> +
> +	return 0;
> +}
> +
> +/*
> + * 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)
> +{
> +	int keys;
> +	int vals;
> +	int hists;
> +
> +	if (!orig || !copy)
> +		return -1;
> +
> +	keys = compare_traceeval_type(orig->key_types, copy->key_types,
> +			orig->nr_key_types, copy->nr_key_types);
> +	vals = compare_traceeval_type(orig->val_types, copy->val_types,
> +			orig->nr_val_types, copy->nr_val_types);
> +	hists = compare_hist(orig, copy);
> +
> +	if (hists == -1)
> +		return -1;
> +
> +	return keys || vals || hists;
> +}

Re: [PATCH v2 1/5] histograms: Initial histograms interface

[Stevie Alvarez]

On Fri, Aug 04, 2023 at 09:50:58AM -0400, Steven Rostedt wrote:
> On Thu,  3 Aug 2023 18:53:59 -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/traceeval-hist.h | 128 +++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 128 insertions(+)
> >  create mode 100644 include/traceeval-hist.h
> > 
> > diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> > new file mode 100644
> > index 0000000..4664974
> > --- /dev/null
> > +++ b/include/traceeval-hist.h
> > @@ -0,0 +1,128 @@
> > +/* 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 */
> > +
> > +/* Field name/descriptor for number of hits */
> > +#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
> > +
> > +/* 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,
> 
> Hmm, I'm thinking it would be nice to rearrange this a bit to:
> 
> enum traceeval_data_type {
> 	TRACEEVAL_TYPE_NONE,
> 	TRACEEVAL_TYPE_NUMBER_8,
> 	TRACEEVAL_TYPE_NUMBER_16,
> 	TRACEEVAL_TYPE_NUMBER_32,
> 	TRACEEVAL_TYPE_NUMBER_64,
> 	TRACEEVAL_TYPE_NUMBER,
> 	TRACEEVAL_TYPE_STRING,
> 
> That way NUMBER_8 will be 1, NUMBER_16 is 2, NUMBER_32 is 3 and NUMBER_64
> is 4. If we ever wanted to do a trick, we can get the byte size from:
> 
>   2^(1 * (enum - 1))
> 
>   2^(1 * (NUMBER_8 - 1))  = 2^(1 * 0) = 1
>   2^(1 * (NUMBER_16 - 1)) = 2^(1 * 1) = 2
>   2^(1 * (NUMBER_32 - 1)) = 2^(1 * 2) = 4
>   2^(1 * (NUMBER_64 - 1)) = 2^(1 * 3) = 8
> 
> I love hacks!
> 
> 
> > +	TRACEEVAL_TYPE_DYNAMIC
> > +};
> > +
> > +/* Statistics specification flags */
> > +enum traceeval_flags {
> > +	TRACEEVAL_FL_SIGNED		= (1 << 0),
> > +	TRACEEVAL_FL_TIMESTAMP		= (1 << 1),
> > +	TRACEEVAL_FL_STATS		= (1 << 2)
> 
> We may as well remove STATS until we decided to use it.
> 
> Maybe even get rid of this enum until we decide to use it.
> 
> Remember, once it's exposed, it is API.
> 
> > +};
> > +
> > +/*
> > + * Trace data entry for a traceeval histogram
> > + * Constitutes keys and values.
> > + */
> > +union traceeval_data {
> > +	char				*string;
> > +	struct traceeval_dynamic	*dyn_data;
> > +	unsigned long long		number_64;
> > +	unsigned long			number;
> > +	unsigned int			number_32;
> > +	unsigned short			number_16;
> > +	unsigned char			number_8;
> > +};
> > +
> > +/*
> > + * 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 {
> > +	void		*data;
> > +	size_t		size;
> > +};
> > +
> 
> As I replied to the cover letter, you need to add:
> 
> struct traceeval_type;
> 
> to get rid of the warning.
> 
> > +/* struct traceeval_dynamic release function signature */
> > +typedef void (*traceeval_dyn_release_fn)(struct traceeval_dynamic *,
> > +		struct traceeval_type *);
> > +
> > +/* struct traceeval_dynamic compare function signature */
> > +typedef int (*traceeval_dyn_cmp_fn)(struct traceeval_dynamic *,
> > +		struct traceeval_dynamic *, struct traceeval_type *);
> > +
> > +/*
> > + * 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 traceeval_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 traceeval_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
> > + * 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 distinguish between
> > + * different sub-types of struct traceeval_dynamic within a single
> > + * callback function by examining the @id field. This is not a required
> > + * approach, merely one that is accommodated.
> > + *
> > + * @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 other way 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 {
> > +	char				*name;
> > +	traceeval_dyn_release_fn	dyn_release;
> > +	traceeval_dyn_cmp_fn		dyn_cmp;
> > +	enum traceeval_data_type	type;
> > +	size_t				flags;
> > +	size_t				id;
> 
> Let's reorder this a little. Normally function pointers come at the end of
> a structure. That's more of a guideline than a rule, but let's have it here.
> 
> struct traceeval_type {
> 	char				*name;
> 	enum traceeval_data_type	type;
> 	size_t				flags;
> 	size_t				id;
> 	traceeval_dyn_release_fn	dyn_release;
> 	traceeval_dyn_cmp_fn		dyn_cmp;
> };
> 
> Especially since dynamic types are going to be rare, we don't want it in
> the hot cache.

Does the order of the fields in a struct definition not matter? I
thought word-boundaries applied to struct definitions? Or does the
compiler take care of this?

-- Stevie

> 
> -- Steve
> 
> 
> > +};
> > +
> > +/* Statistics about a given entry element */
> > +struct traceeval_stat {
> > +	unsigned long long	max;
> > +	unsigned long long	min;
> > +	unsigned long long	total;
> > +	unsigned long long	avg;
> > +	unsigned long long	std;
> > +};
> > +
> > +/* Iterator over aggregated data */
> > +struct traceeval_iterator;
> > +
> > +struct traceeval;
> > +
> > +#endif /* __LIBTRACEEVAL_HIST_H__ */
> 

Re: [PATCH v2 1/5] histograms: Initial histograms interface

[Steven Rostedt]

On Fri, 4 Aug 2023 13:41:59 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> > > +struct traceeval_type {
> > > +	char				*name;
> > > +	traceeval_dyn_release_fn	dyn_release;
> > > +	traceeval_dyn_cmp_fn		dyn_cmp;
> > > +	enum traceeval_data_type	type;
> > > +	size_t				flags;
> > > +	size_t				id;  
> > 
> > Let's reorder this a little. Normally function pointers come at the end of
> > a structure. That's more of a guideline than a rule, but let's have it here.
> > 
> > struct traceeval_type {
> > 	char				*name;
> > 	enum traceeval_data_type	type;
> > 	size_t				flags;
> > 	size_t				id;
> > 	traceeval_dyn_release_fn	dyn_release;
> > 	traceeval_dyn_cmp_fn		dyn_cmp;
> > };
> > 
> > Especially since dynamic types are going to be rare, we don't want it in
> > the hot cache.  
> 
> Does the order of the fields in a struct definition not matter? I
> thought word-boundaries applied to struct definitions? Or does the
> compiler take care of this?

They do matter. Word bounders are important, but the compiler will just
make "holes" if needed. For example, let's say on 64 bit, everything above
is 64 bits but the type. I would have created a "hole". But because the
type is more important than the id, I kept it at the top.

struct traceeval_type {
	char				*name;			// offset 0
 	enum traceeval_data_type	type;			// offset 8

[ compiler adds 4 byte "hole" or "padding" ]

 	size_t				flags;			// offset 16
 	size_t				id;			// offset 24
 	traceeval_dyn_release_fn	dyn_release;		// offset 32
 	traceeval_dyn_cmp_fn		dyn_cmp;		// offset 40
};

If a cache line is 32 bytes (most is usually 128, but let's say on an older
architecture) I don't care if the the dyn_release and dyn_cmp are in the
same cache line as name.

-- Steve

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

[Stevie Alvarez]

On Fri, Aug 04, 2023 at 10:40:39AM -0400, Steven Rostedt wrote:
> On Thu,  3 Aug 2023 18:54:00 -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 +-
> >  include/traceeval-hist.h |   5 +
> >  src/Makefile             |   1 +
> >  src/histograms.c         | 223 +++++++++++++++++++++++++++++++++++++++
> >  4 files changed, 230 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
> 
> This seems like it doesn't belong in this patch.
> 
> >  
> >  test: force $(LIBRARY_STATIC)
> >  ifneq ($(CUNIT_INSTALLED),1)
> > diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> > index 4664974..5bea025 100644
> > --- a/include/traceeval-hist.h
> > +++ b/include/traceeval-hist.h
> > @@ -125,4 +125,9 @@ struct traceeval_iterator;
> >  
> >  struct traceeval;
> >  
> > +/* Histogram interfaces */
> > +
> > +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> > +		const struct traceeval_type *vals);
> > +
> >  #endif /* __LIBTRACEEVAL_HIST_H__ */
> > 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..be17b89
> > --- /dev/null
> > +++ b/src/histograms.c
> > @@ -0,0 +1,223 @@
> > +/* SPDX-License-Identifier: MIT */
> > +/*
> > + * libtraceeval histogram interface implementation.
> > + *
> > + * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
> > + */
> > +
> > +#include <stdbool.h>
> > +#include <string.h>
> > +#include <stdarg.h>
> > +#include <stdio.h>
> > +
> > +#include <traceeval-hist.h>
> > +
> > +/* 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		*key_types;
> > +	struct traceeval_type		*val_types;
> > +	struct hist_table		*hist;
> > +	size_t				nr_key_types;
> > +	size_t				nr_val_types;
> > +};
> > +
> > +/* Iterate over results of histogram */
> > +struct traceeval_iterator {};
> 
> Add the traceeval_iterator struct when it is used.
> 
> It's not relevant to this patch.
> 
> > +
> > +/*
> > + * print_err() - print an error message
> > + * @fmt: String format
> > + * @...: (optional) Additional arguments to print in conjunction with @format
> > + */
> > +static void print_err(const char *fmt, ...)
> > +{
> > +	va_list ap;
> > +
> > +	va_start(ap, fmt);
> > +	vfprintf(stderr, fmt, ap);
> > +	va_end(ap);
> > +	fprintf(stderr, "\n");
> > +}
> > +
> > +/*
> > + * type_release() - free a struct traceeval_type array
> > + * @defs: The array to release
> > + * @len: The length of @defs
> > + *
> > + * It is assumed that all elements of @defs, within the length of @len, have
> > + * name fields initialized to valid pointers.
> > + *
> > + * This function was designed to be used on an array allocated by type_alloc().
> > + * Note that type_alloc() initializes all name fields of elements within the
> > + * returned size.
> > + */
> > +static void type_release(struct traceeval_type *defs, size_t len)
> 
> You added this but did not add traceeval_release().
> 
> traceeval_release() should be added in this patch to clean up everything
> that traceeval_init() creates.
> 
> > +{
> > +	if (!defs)
> > +		return;
> > +
> > +	for (size_t i = 0; i < len; i++) {
> > +		free(defs[i].name);
> > +	}
> > +
> > +	free(defs);
> > +}
> > +
> > +/*
> > + * type_alloc() - clone a struct traceeval_type array
> > + * @defs: The original array
> > + * @copy: A pointer to where to place the @defs copy
> > + *
> > + * Clone traceeval_type array @defs to the heap, and place in @copy.
> > + * @defs must be terminated with an instance of type TRACEEVAL_TYPE_NONE.
> > + *
> > + * The size of the copy pointed to by @copy is returned. It counts all elements
> > + * in @defs excluding the terminating TRACEEVAL_TYPE_NONE traceeval_type.
> > + * The copy contains everything from @defs excluding the TRACEEVAL_TYPE_NONE
> > + * traceeval_type.
> > + *
> > + * The name field of each element of @defs (except for the terminating
> > + * TRACEEVAL_TYPE_NONE) must be a NULL-terminated string. The validity of the
> > + * name field is not checked, but errors are returned upon finding unset name
> > + * fields and string duplication failures. It is guaranteed that all elements
> > + * of the copy within the returned size have valid pointers in their name
> > + * fields.
> > + *
> > + * Returns the size of the array pointed to by @copy, or, if an error occurs,
> > + * the negative of the size of what's been allocated so far.
> > + * If the return value is negative, the user is responsible for freeing
> > + * -1 * return value number of elements from @copy.
> > + */
> > +static size_t type_alloc(const struct traceeval_type *defs,
> > +		struct traceeval_type **copy)
> > +{
> > +	struct traceeval_type *new_defs = NULL;
> > +	size_t size;
> > +	size_t i;
> > +
> > +	if (!defs) {
> > +		*copy = NULL;
> > +		return 0;
> > +	}
> > +
> > +	for (size = 0; defs && defs[size].type != TRACEEVAL_TYPE_NONE; size++);
> 
> For loops like the above, please do:
> 
> 	for (size = 0; defs && defs[size].type != TRACEEVAL_TYPE_NONE; size++)
> 		;
> 
> This makes it obvious that it's an empty loop and we don't think it's
> looping over the line below it.
> 
> > +
> > +	if (size) {
> > +		new_defs = calloc(size, sizeof(*new_defs));
> > +	} else {
> > +		*copy = NULL;
> > +		return 0;
> > +	}
> > +
> > +	for (i = 0; i < size; i++) {
> > +		/* copy current def data to new_def */
> > +		new_defs[i] = defs[i];
> > +
> > +		/* copy name to heap, ensures name copied */
> > +		if (!defs[i].name)
> > +			goto fail_type_name;
> 
> No need to be so verbose in the labels.
> 
> 			goto fail;
> 
> is good enough ;-)
> 
> > +		new_defs[i].name = strdup(defs[i].name);
> > +
> > +		if (!new_defs[i].name)
> > +			goto fail_type_name;
> > +	}
> > +
> > +	*copy = new_defs;
> > +	return size;
> > +
> > +fail_type_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);
> 
> I would change the above to:
> 
> 	if (defs[i].name)
> 		print_err("Failed to allocate traceveal_type %zu", size);
> 	else
> 		print_err("traceeval_type list missing a name");
> 
> > +	*copy = new_defs;
> > +	return i * -1;
> 
> Also, we need to clean up here and not pass that info back to the caller.
> 
> // need to make i: ssize_t i;
> 
> 	for (; i >= 0; i--)
> 		free(new_defs[i].name);
> 	free(new_defs);
> 	*copy = NULL;
> 	return -1;
> 
> 
> > +}
> > +
> > +/*
> > + * traceeval_init - create a traceeval descriptor
> > + * @keys: Defines the keys to differentiate traceeval entries
> > + * @vals: Defines values attached to entries differentiated by @keys.
> > + *
> > + * 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 "histogram". Note, both the @keys and @vals array must end with:
> > + * { .type = TRACEEVAL_TYPE_NONE }.
> > + *
> > + * The @keys and @vals passed in are copied for internal use.
> > + *
> > + * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
> > + * the name field must be a null-terminated string. For members of type
> > + * TRACEEVAL_TYPE_NONE, the name is ignored.
> > + *
> > + * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
> > + * define the values of the histogram to be empty.
> > + * @keys must be populated with at least one element that is not
> > + * TRACEEVAL_TYPE_NONE.
> > + *
> > + * Returns the descriptor on success, or NULL on error.
> > + */
> > +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> > +				 const struct traceeval_type *vals)
> > +{
> > +	struct traceeval *teval;
> > +	char *err_msg;
> > +
> > +	if (!keys)
> > +		return NULL;
> > +
> > +	if (keys->type == TRACEEVAL_TYPE_NONE) {
> > +		err_msg = "keys cannot start with type TRACEEVAL_TYPE_NONE";
> 
> BTW, all the error messages should start with a capital letter.
> 
> 			"Keys cannot .."
> 
> > +		goto fail_init_unalloced;
> 
> Just make this: goto fail;

Having multiple of the same label segfaults my tests. I'm relatively new
to using C labels, is that behavior expected? And if so is it acceptable
for me to distingush the two fail labels by a single character?

-- Stevie

> 
> > +	}
> > +
> > +	/* alloc teval */
> > +	teval = calloc(1, sizeof(*teval));
> > +	if (!teval) {
> > +		err_msg = "failed to allocate memory for traceeval instance";
> > +		goto fail_init_unalloced;
> > +	}
> > +
> > +	/* alloc key types */
> > +	teval->nr_key_types = type_alloc(keys, &teval->key_types);
> > +	if (teval->nr_key_types <= 0) {
> > +		teval->nr_key_types *= -1;
> 
> Get rid of the above setting.
> 
> > +		err_msg = "failed to allocate user defined keys";
> > +		goto fail_init;
> 
> and this: goto fail_release;
> 
> > +	}
> > +
> > +	/* alloc val types */
> > +	teval->nr_val_types = type_alloc(vals, &teval->val_types);
> > +	if (teval->nr_val_types < 0) {
> > +		teval->nr_val_types *= -1;
> 
> And git rid of the above too.
> 
> > +		err_msg = "failed to allocate user defined values";
> > +		goto fail_init;
> > +	}
> > +
> > +	/* alloc hist */
> > +	teval->hist = calloc(1, sizeof(*teval->hist));
> > +	if (!teval->hist) {
> > +		err_msg = "failed to allocate memory for histogram";
> > +		goto fail_init;
> > +	}
> > +
> > +	return teval;
> > +
> > +fail_init:
> > +	traceeval_release(teval);
> 
> The above isn't defined. If you reference a function in a patch, it must be
> at least defined.
> 
> > +
> > +fail_init_unalloced:
> > +	print_err(err_msg);
> > +	return NULL;
> > +}
> 
> -- Steve

Re: [PATCH v2 1/5] histograms: Initial histograms interface

[Stevie Alvarez]

On Fri, Aug 04, 2023 at 01:57:18PM -0400, Steven Rostedt wrote:
> On Fri, 4 Aug 2023 13:41:59 -0400
> Stevie Alvarez <stevie.6strings@gmail.com> wrote:
> 
> > > > +struct traceeval_type {
> > > > +	char				*name;
> > > > +	traceeval_dyn_release_fn	dyn_release;
> > > > +	traceeval_dyn_cmp_fn		dyn_cmp;
> > > > +	enum traceeval_data_type	type;
> > > > +	size_t				flags;
> > > > +	size_t				id;  
> > > 
> > > Let's reorder this a little. Normally function pointers come at the end of
> > > a structure. That's more of a guideline than a rule, but let's have it here.
> > > 
> > > struct traceeval_type {
> > > 	char				*name;
> > > 	enum traceeval_data_type	type;
> > > 	size_t				flags;
> > > 	size_t				id;
> > > 	traceeval_dyn_release_fn	dyn_release;
> > > 	traceeval_dyn_cmp_fn		dyn_cmp;
> > > };
> > > 
> > > Especially since dynamic types are going to be rare, we don't want it in
> > > the hot cache.  
> > 
> > Does the order of the fields in a struct definition not matter? I
> > thought word-boundaries applied to struct definitions? Or does the
> > compiler take care of this?
> 
> They do matter. Word bounders are important, but the compiler will just
> make "holes" if needed. For example, let's say on 64 bit, everything above
> is 64 bits but the type. I would have created a "hole". But because the
> type is more important than the id, I kept it at the top.
> 
> struct traceeval_type {
> 	char				*name;			// offset 0
>  	enum traceeval_data_type	type;			// offset 8
> 
> [ compiler adds 4 byte "hole" or "padding" ]
> 
>  	size_t				flags;			// offset 16
>  	size_t				id;			// offset 24
>  	traceeval_dyn_release_fn	dyn_release;		// offset 32
>  	traceeval_dyn_cmp_fn		dyn_cmp;		// offset 40
> };
> 
> If a cache line is 32 bytes (most is usually 128, but let's say on an older
> architecture) I don't care if the the dyn_release and dyn_cmp are in the
> same cache line as name.
> 
> -- Steve

This makes sense, I appreciate the explination! I was treating size_t as
an int in my head by accident.... oops!

-- Stevie

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

[Steven Rostedt]

On Fri, 4 Aug 2023 14:23:11 -0400
Stevie Alvarez <stevie.6strings@gmail.com> wrote:

> > > + * traceeval_init - create a traceeval descriptor
> > > + * @keys: Defines the keys to differentiate traceeval entries
> > > + * @vals: Defines values attached to entries differentiated by @keys.
> > > + *
> > > + * 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 "histogram". Note, both the @keys and @vals array must end with:
> > > + * { .type = TRACEEVAL_TYPE_NONE }.
> > > + *
> > > + * The @keys and @vals passed in are copied for internal use.
> > > + *
> > > + * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
> > > + * the name field must be a null-terminated string. For members of type
> > > + * TRACEEVAL_TYPE_NONE, the name is ignored.
> > > + *
> > > + * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
> > > + * define the values of the histogram to be empty.
> > > + * @keys must be populated with at least one element that is not
> > > + * TRACEEVAL_TYPE_NONE.
> > > + *
> > > + * Returns the descriptor on success, or NULL on error.
> > > + */
> > > +struct traceeval *traceeval_init(const struct traceeval_type *keys,
> > > +				 const struct traceeval_type *vals)
> > > +{
> > > +	struct traceeval *teval;
> > > +	char *err_msg;
> > > +
> > > +	if (!keys)
> > > +		return NULL;
> > > +
> > > +	if (keys->type == TRACEEVAL_TYPE_NONE) {
> > > +		err_msg = "keys cannot start with type TRACEEVAL_TYPE_NONE";  
> > 
> > BTW, all the error messages should start with a capital letter.
> > 
> > 			"Keys cannot .."
> >   
> > > +		goto fail_init_unalloced;  
> > 
> > Just make this: goto fail;  
> 
> Having multiple of the same label segfaults my tests. I'm relatively new
> to using C labels, is that behavior expected? And if so is it acceptable
> for me to distingush the two fail labels by a single character?

labels must be unique per function. But I constantly use  the same label
multiple times per C file.

As I stated in the email, convert one to "fail:" and the other one to "fail_release:"

> 
> -- Stevie
> 
> >   
> > > +	}
> > > +
> > > +	/* alloc teval */
> > > +	teval = calloc(1, sizeof(*teval));
> > > +	if (!teval) {
> > > +		err_msg = "failed to allocate memory for traceeval instance";
> > > +		goto fail_init_unalloced;
> > > +	}
> > > +
> > > +	/* alloc key types */
> > > +	teval->nr_key_types = type_alloc(keys, &teval->key_types);
> > > +	if (teval->nr_key_types <= 0) {
> > > +		teval->nr_key_types *= -1;  
> > 
> > Get rid of the above setting.
> >   
> > > +		err_msg = "failed to allocate user defined keys";
> > > +		goto fail_init;  
> > 
> > and this: goto fail_release;
> >   
> > > +	}
> > > +
> > > +	/* alloc val types */
> > > +	teval->nr_val_types = type_alloc(vals, &teval->val_types);
> > > +	if (teval->nr_val_types < 0) {
> > > +		teval->nr_val_types *= -1;  
> > 
> > And git rid of the above too.
> >   
> > > +		err_msg = "failed to allocate user defined values";
> > > +		goto fail_init;
> > > +	}
> > > +
> > > +	/* alloc hist */
> > > +	teval->hist = calloc(1, sizeof(*teval->hist));
> > > +	if (!teval->hist) {
> > > +		err_msg = "failed to allocate memory for histogram";
> > > +		goto fail_init;
> > > +	}
> > > +
> > > +	return teval;
> > > +
> > > +fail_init:

This would be

 fail_release:

as it releases the teval.

> > > +	traceeval_release(teval);  
> > 
> > The above isn't defined. If you reference a function in a patch, it must be
> > at least defined.
> >   
> > > +
> > > +fail_init_unalloced:

and this one be

 fail:

As it is part of the fail path for both.

-- Steve


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

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

[Ross Zwisler]

On Thu, Aug 03, 2023 at 06:54:02PM -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>
> ---
>  include/traceeval-test.h |  16 +++
>  src/histograms.c         | 221 ++++++++++++++++++++++++++++++++++++++-
>  2 files changed, 234 insertions(+), 3 deletions(-)
>  create mode 100644 include/traceeval-test.h
> 
> diff --git a/include/traceeval-test.h b/include/traceeval-test.h
> new file mode 100644
> index 0000000..bb8092a
> --- /dev/null
> +++ b/include/traceeval-test.h
<>
> @@ -158,12 +172,13 @@ fail_type_name:
>   * The @keys and @vals passed in are copied for internal use.
>   *
>   * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
> - * the name field must be a null-terminated string. For members of type
> - * TRACEEVAL_TYPE_NONE, the name is ignored.
> + * the name field must be a null-terminated string. Members of type
> + * TRACEEVAL_TYPE_NONE are used to terminate the array, therefore their other
> + * fields are ignored.
>   *
>   * @vals can be NULL or start with its type field as TRACEEVAL_TYPE_NONE to
>   * define the values of the histogram to be empty.
> - * @keys must be populated with at least one element that is not
> + * @keys must be populated with at least one element that is not of type

These two comment updates seem accidental, and can be just folded into the
initial patch that creates them.

>   * TRACEEVAL_TYPE_NONE.
>   *
>   * Returns the descriptor on success, or NULL on error.
> @@ -305,3 +320,203 @@ void traceeval_release(struct traceeval *teval)
>  	teval->val_types = NULL;
>  	free(teval);
>  }
> +
> +/*
> + * Compare traceeval_type instances for equality.
> + *
> + * Return 0 if @orig and @copy are the same, 1 otherwise.
> + */
> +static int compare_traceeval_type(struct traceeval_type *orig,
> +		struct traceeval_type *copy, size_t orig_size, size_t copy_size)
> +{
> +	size_t i;
> +
> +	/* same memory/NULL */
> +	if (orig == copy)
> +		return 0;
> +	if (!!orig != !!copy)
> +		return 1;
> +
> +	if (orig_size != copy_size)
> +		return 1;
> +
> +	for (i = 0; i < orig_size; i++) {
> +		if (orig[i].type != copy[i].type)
> +			return 1;
> +		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
> +		if (!!orig[i].name != !!copy[i].name)
> +			return 1;
> +		if (!orig[i].name)
> +			continue;
> +		if (strcmp(orig[i].name, copy[i].name) != 0)
> +			return 1;
> +	}
> +
> +	return 0;
> +}
> +
> +/*
> + * Compare traceeval_data instances.
> + *
> + * 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,

For both this and compare_traceeval_data_set(), both 'orig' and 'copy' can be
const.   Same with 'type', since compare functions shouldn't be modifying any
data.  This applies to most or all of the pointer params to your compare
functions.

> +		const union traceeval_data *copy, struct traceeval_type *type)
> +{
> +	int i;
> +
> +	if (orig == copy)
> +		return 0;
> +
> +	if (!orig)
> +		return -1;
> +
> +	if (!copy)
> +		return 1;
> +
> +	switch (type->type) {
> +	case TRACEEVAL_TYPE_STRING:
> +		i = strcmp(orig->string, copy->string);
> +		compare_numbers_return(i, 0);
> +
> +	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:
> +		if (type->dyn_cmp)
> +			return type->dyn_cmp(orig->dyn_data, copy->dyn_data, type);
> +		return 0;
> +
> +	default:
> +		print_err("%d is an invalid enum traceeval_data_type member",
> +				type->type);
> +		return -2;
> +	}
> +}
> +
> +/*
> + * Compare arrays of 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 *defs,
> +		size_t size)