[PATCH v4 00/20] libtraceeval histogram: Updates

[PATCH v4 00/20] libtraceeval histogram: Updates

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

This patch set is based on top of:

 https://lore.kernel.org/all/20230809175340.3066-1-stevie.6strings@gmail.com/

I added a sample program task-eval which is one of the tools that will be
using this library. The first patch adds task-eval but that is still using
the old API (defined in trace-analysis.c).

The next patches modify the new API to fit with the use case of task-eval.
One is to use "pointer" as I'm not sure exactly the usecase of the dynamic
structure.

The cmp and release callbacks are changed to be more generic, and they get
called if they simply exist for a given type. I can imagine wanting a
release function for event the most mundane types (like number_32).

The cmp was also updated to pass in the traceeval descriptor, as I found
that I needed access to it while doing a compare (although, I rewrote the
code a bit where that use case isn't in the tool anymore).

Some fixes were made to the query.

I also did a bit of code restructuring and add the hash and iterator logic.

The last patch updates the sample code task-eval.c and has it give pretty
much the same logic as the original.

That sample could be updated to implement the code consolidation that Ross
suggested. I may do that later.

Happy programming!


Changes since v3: https://lore.kernel.org/all/20230817013310.88582-1-rostedt@goodmis.org/

- Added patch to reordered the parameters of copy_traceeval_data() and renamed
  copy to dst and orig to src to match that of memcpy() and strcpy().

- Added patch to rename copy_traceeval_data_set() to dup_traceeval_data_set()
  to not have the parameter order to be confusing with the typical copy order.

- Fixed comment of traceeval_remove() (Ross Zwisler)

Changes since v2: https://lore.kernel.org/all/20230811053940.1408424-1-rostedt@goodmis.org/

  - Fixed comments on traceeval_dyn_release_fn and traceeval_dyn_cmp_fn (Ross Zwisler)

  - Change parameter ordering of compare_traceeval_data (Ross Zwisler)

  - Added (size_t) to offset_of() macro (Ross Zwisler)

  - Fixed iter->current_bucket off by one bug (Ross Zwisler)

  - Removed HASH_MASK() from make_hash()

  - Fixed goto fail_release in traceeval_init() (Ross Zwisler)

  - Free sort and direction in traceeval_iterator_put() (Ross Zwisler)

  - Use num_levels variable instead of (level + 1) (Ross Zwisler)

  - Return 0 on success of update_entry (Ross Zwisler)

  - Fixed the cleanup of old values in update_entry() (Ross Zwisler)

  - Fixed resetting iter->next = 0 in traceeval_iterator_sort_custom() (Ross Zwisler)

  - Added failure checks to task-eval.c sample for all traceeval_query() calls.

  - Added traceeval_remove() to remove an item from traceveal (opposite of traceeval_insert())

Changes since v1: https://lore.kernel.org/all/20230809031313.1298605-1-rostedt@goodmis.org/

 - Lots!

   - Converted to using a hash table

   - Removed the unused compare code. With the other updates, it was
     taking too much time to keep updating them.

   - Added checks and labels to the types to have them know what type
     they are, and index they are at.

   - Added stat logic

   - Added iterator logic

   - Have a working sample with the new code!

Steven Rostedt (Google) (20):
  libtraceeval histograms: Fix traceeval_results_release() error message
  libtraceeval: Reverse params of copy_traceeval_data()
  libtraceeval: Rename copy_traceeval_data_set() to dup_traceeval_data()
  libtraceeval: Add sample task-eval program
  libtraceeval hist: Add pointer and const string types
  libtraceeval histogram: Have cmp and release functions be generic
  libtraceeval histograms: Add traceeval struct to compare function
  libtraceeval histogram: Remove comparing of traceeval and types
  libtraceeval: Convert hist array into a hash table
  libtraceeval histograms: Move hash functions into their own file
  libtraceeval histogram: Label and check keys and values
  libtraceeval histogram: Add updating of stats
  libtraceeval histogram: Add iterator APIs
  libtraceeval histogram: Add data copy callback
  libtraceeval histogram: Do the release on updates
  libtraceeval histogram: Use stack for old copy in update
  libtraceeval histogram: Add traceeval_iterator_sort_custom()
  libtraceeval histogram: Have traceeval_query() just give the pointer
    to results
  libtraceeval samples: Update task-eval to use the histogram logic
  libtraceeval: Add traceeval_remove()

 Makefile                 |   4 +-
 include/traceeval-hist.h | 117 +++--
 include/traceeval-test.h |  16 -
 samples/Makefile         |  29 ++
 samples/task-eval.c      | 966 +++++++++++++++++++++++++++++++++++++++
 src/Makefile             |   1 +
 src/eval-local.h         | 123 +++++
 src/hash.c               | 123 +++++
 src/histograms.c         | 945 ++++++++++++++++++++++++++++----------
 9 files changed, 2023 insertions(+), 301 deletions(-)
 delete mode 100644 include/traceeval-test.h
 create mode 100644 samples/Makefile
 create mode 100644 samples/task-eval.c
 create mode 100644 src/eval-local.h
 create mode 100644 src/hash.c

-- 
2.40.1

[PATCH v4 01/20] libtraceeval histograms: Fix traceeval_results_release() error message

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

The function traceeval_results_release() must have a teval if passed in to
free the accompanying results, but currently the error message is only
displayed if the results is NULL and teval exists. It should be the other
way around.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 src/histograms.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/histograms.c b/src/histograms.c
index a159892e509b..d22d15238616 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -681,7 +681,7 @@ void traceeval_results_release(struct traceeval *teval,
 			       union traceeval_data *results)
 {
 	if (!teval || !results) {
-		if (!results)
+		if (!teval)
 			print_err("Results to be freed without accompanied traceeval instance!");
 		return;
 	}
-- 
2.40.1

[PATCH v4 02/20] libtraceeval: Reverse params of copy_traceeval_data()

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Most C library functions copy data from "dst", "src" order, but
copy_traceeval_data() does it as "src", "dst", and I already made one bug
because of this. Reverse the order of the copy_traceeval_data()
parameters, and also rename them to match standard library names "dst" and
"src".

Link: https://lore.kernel.org/linux-trace-devel/20230817192926.GA73817@google.com/

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 src/histograms.c | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)

diff --git a/src/histograms.c b/src/histograms.c
index d22d15238616..071e30e73768 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -560,25 +560,25 @@ static int get_entry(struct traceeval *teval, const union traceeval_data *keys,
 }
 
 /*
- * Copy @orig to @copy with respect to @type.
+ * Copy @src to @dst with respect to @type.
  *
  * Return 0 on success, -1 on error.
  */
 static int copy_traceeval_data(struct traceeval_type *type,
-				const union traceeval_data *orig,
-				union traceeval_data *copy)
+				union traceeval_data *dst,
+				const union traceeval_data *src)
 {
-	*copy = *orig;
+	*dst = *src;
 
 	if (type->type == TRACEEVAL_TYPE_STRING) {
-		copy->string = NULL;
+		dst->string = NULL;
 
-		if (orig->string)
-			copy->string = strdup(orig->string);
+		if (src->string)
+			dst->string = strdup(src->string);
 		else
 			return 0;
 
-		if (!copy->string)
+		if (!dst->string)
 			return -1;
 	}
 
@@ -621,7 +621,7 @@ static int copy_traceeval_data_set(size_t size, struct traceeval_type *type,
 		return -1;
 
 	for (i = 0; i < size; i++) {
-		if (copy_traceeval_data(type + i, orig + i, (*copy) + i))
+		if (copy_traceeval_data(type + i, (*copy) + i, orig + i))
 			goto fail;
 	}
 
-- 
2.40.1

[PATCH v4 03/20] libtraceeval: Rename copy_traceeval_data_set() to dup_traceeval_data()

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

The name "copy_traceveal_data_set()" is misleading. It's actually
duplicating the data. The difference is that it allocates a new data
element and does not "copy" it. This is considered a "dup" and not a copy.
This makes it more in line of "strdup()".

It also removes the association of the order of the parameters, as when
something is being allocated, it usually comes at the end.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 src/histograms.c | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

diff --git a/src/histograms.c b/src/histograms.c
index 071e30e73768..9b58416ad20c 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -602,13 +602,13 @@ static void data_release(size_t size, union traceeval_data **data,
 }
 
 /*
- * Copy @orig to @copy with respect to @size and @type.
+ * Duplicate a traceeval_data @orig into an newly allocated @copy.
  *
  * Returns 1 on success, -1 on error.
  */
-static int copy_traceeval_data_set(size_t size, struct traceeval_type *type,
-				    const union traceeval_data *orig,
-				    union traceeval_data **copy)
+static int dup_traceeval_data_set(size_t size, struct traceeval_type *type,
+				  const union traceeval_data *orig,
+				  union traceeval_data **copy)
 {
 	size_t i;
 
@@ -662,8 +662,8 @@ int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 	/* find key and copy its corresponding value pair */
 	if ((check = get_entry(teval, keys, &entry)) < 1)
 		return check;
-	return copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
-			entry->vals, results);
+	return dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
+				      entry->vals, results);
 }
 
 /*
@@ -704,13 +704,13 @@ static int create_entry(struct traceeval *teval,
 	struct hist_table *hist = teval->hist;
 
 	/* copy keys */
-	if (copy_traceeval_data_set(teval->nr_key_types, teval->key_types,
-				keys, &new_keys) == -1)
+	if (dup_traceeval_data_set(teval->nr_key_types, teval->key_types,
+				   keys, &new_keys) == -1)
 		return -1;
 
 	/* copy vals */
-	if (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
-				vals, &new_vals) == -1)
+	if (dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
+				   vals, &new_vals) == -1)
 		goto fail_vals;
 
 	/* create new entry */
@@ -743,8 +743,8 @@ static int update_entry(struct traceeval *teval, struct entry *entry,
 {
 	union traceeval_data *new_vals;
 
-	if (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
-				vals, &new_vals) == -1)
+	if (dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
+				   vals, &new_vals) == -1)
 		return -1;
 
 	clean_data_set(entry->vals, teval->val_types, teval->nr_val_types);
-- 
2.40.1

[PATCH v4 04/20] libtraceeval: Add sample task-eval program

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Add a sample task eval program to test the traceeval logic.

This relies on having libtracecmd installed.

This version uses the old API, and will be used to compare when converted
over to the new API.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 Makefile            |   3 +
 samples/Makefile    |  29 ++
 samples/task-eval.c | 859 ++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 891 insertions(+)
 create mode 100644 samples/Makefile
 create mode 100644 samples/task-eval.c

diff --git a/Makefile b/Makefile
index 3ea051cbebf5..62ca9285d7a0 100644
--- a/Makefile
+++ b/Makefile
@@ -348,6 +348,9 @@ $(LIBRARY_STATIC): force
 $(LIBRARY_SHARED): force
 	$(Q)$(call descend,$(src)/src,$(LIBRARY_SO))
 
+samples: $(LIBRARY_STATIC) force
+	$(Q)$(call descend,$(src)/samples,all)
+
 #	$(Q)$(call descend_clean,utest)
 clean:
 	$(Q)$(call descend_clean,src)
diff --git a/samples/Makefile b/samples/Makefile
new file mode 100644
index 000000000000..012301ec5542
--- /dev/null
+++ b/samples/Makefile
@@ -0,0 +1,29 @@
+# SPDX-License-Identifier: LGPL-2.1
+
+include $(src)/scripts/utils.mk
+
+TARGETS :=
+TARGETS += task-eval
+
+sdir := $(obj)/bin
+
+CFLAGS += `pkg-config --cflags libtracecmd`
+LIBRARY_LIBS += `pkg-config --libs libtracecmd`
+
+TARGETS := $(patsubst %,$(sdir)/%,$(TARGETS))
+
+all: $(TARGETS)
+
+$(sdir):
+	@mkdir -p $(sdir)
+
+$(TARGETS): $(sdir) $(LIBTRACEEVAL_STATIC)
+
+$(sdir)/%: $(bdir)/%.o
+	$(call do_sample_build,$@,$<)
+
+$(bdir)/%.o: $(bdir)/%.c
+	$(Q)$(CC) -o $@ -c $< $(CFLAGS) $(INCLUDES)
+
+clean:
+	$(Q)$(call do_clean,$(sdir)/*)
diff --git a/samples/task-eval.c b/samples/task-eval.c
new file mode 100644
index 000000000000..9214777ee2e1
--- /dev/null
+++ b/samples/task-eval.c
@@ -0,0 +1,859 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdarg.h>
+#include <getopt.h>
+#include <errno.h>
+#include <trace-cmd.h>
+#include <traceeval.h>
+
+static char *argv0;
+
+static char *get_this_name(void)
+{
+	static char *this_name;
+	char *arg;
+	char *p;
+
+	if (this_name)
+		return this_name;
+
+	arg = argv0;
+	p = arg+strlen(arg);
+
+	while (p >= arg && *p != '/')
+		p--;
+	p++;
+
+	this_name = p;
+	return p;
+}
+
+static void usage(void)
+{
+	char *p = get_this_name();
+
+	printf("usage: %s [-c comm] trace.dat\n"
+	       "\n"
+	       "  Run this after running: trace-cmd record -e sched\n"
+	       "\n"
+	       "  Do some work and then hit Ctrl^C to stop the recording.\n"
+	       "  Run this on the resulting trace.dat file\n"
+	       "\n"
+	       "-c comm - to look at only a specific process called 'comm'\n"
+	       "\n",p);
+	exit(-1);
+}
+
+static void __vdie(const char *fmt, va_list ap, int err)
+{
+	int ret = errno;
+	char *p = get_this_name();
+
+	if (err && errno)
+		perror(p);
+	else
+		ret = -1;
+
+	fprintf(stderr, "  ");
+	vfprintf(stderr, fmt, ap);
+
+	fprintf(stderr, "\n");
+	exit(ret);
+}
+
+void die(const char *fmt, ...)
+{
+	va_list ap;
+
+	va_start(ap, fmt);
+	__vdie(fmt, ap, 0);
+	va_end(ap);
+}
+
+void pdie(const char *fmt, ...)
+{
+	va_list ap;
+
+	va_start(ap, fmt);
+	__vdie(fmt, ap, 1);
+	va_end(ap);
+}
+
+enum sched_state {
+	RUNNING,
+	BLOCKED,
+	PREEMPT,
+	SLEEP,
+	IDLE,
+	OTHER
+};
+
+struct process_data {
+	struct traceeval	*teval_cpus;
+	struct traceeval	*teval_threads;
+	char			*comm;
+	int			state;
+};
+
+struct task_data {
+	struct traceeval	*teval_cpus;
+	struct traceeval	*teval_processes;
+	char			*comm;
+};
+
+enum command {
+	START,
+	STOP
+};
+
+static void update_process(struct task_data *tdata, const char *comm,
+			   enum sched_state state, enum command cmd,
+			   unsigned long long ts)
+{
+	struct traceeval_key keys[] = {
+		{
+			.type = TRACEEVAL_TYPE_STRING,
+			.string = comm,
+		},
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.number = state,
+		}
+	};
+	int ret;
+
+	switch (cmd) {
+	case START:
+		ret = traceeval_n_start(tdata->teval_processes, keys, ts);
+		if (ret < 0)
+			pdie("Could not start process");
+		return;
+	case STOP:
+		ret = traceeval_n_stop(tdata->teval_processes, keys, ts);
+		if (ret < 0)
+			pdie("Could not stop process");
+		return;
+	}
+}
+
+static void start_process(struct task_data *tdata, const char *comm,
+			   enum sched_state state, unsigned long long ts)
+{
+	update_process(tdata, comm, state, START, ts);
+}
+
+static void stop_process(struct task_data *tdata, const char *comm,
+			   enum sched_state state, unsigned long long ts)
+{
+	update_process(tdata, comm, state, STOP, ts);
+}
+
+static struct process_data *
+get_process_data(struct task_data *tdata, const char *comm)
+{
+	struct traceeval_key keys[] = {
+		{
+			.type = TRACEEVAL_TYPE_STRING,
+			.string = comm,
+		},
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.number = RUNNING,
+		}
+	};
+
+	return traceeval_n_get_private(tdata->teval_processes, keys);
+}
+
+void set_process_data(struct task_data *tdata, const char *comm, void *data)
+{
+	struct traceeval_key keys[] = {
+		{
+			.type = TRACEEVAL_TYPE_STRING,
+			.string = comm,
+		},
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.number = RUNNING,
+		}
+	};
+	int ret;
+
+	ret = traceeval_n_set_private(tdata->teval_processes, keys, data);
+	if (ret < 0)
+		pdie("Failed to set process data");
+}
+
+static void update_cpu(struct traceeval *teval, int cpu,
+		       enum sched_state state, enum command cmd,
+		       unsigned long long ts)
+{
+	struct traceeval_key keys[] = {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.number = cpu,
+		},
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.number = state,
+		}
+	};
+	int ret;
+
+	switch (cmd) {
+	case START:
+		ret = traceeval_n_continue(teval, keys, ts);
+		if (ret < 0)
+			pdie("Could not start CPU");
+		return;
+	case STOP:
+		ret = traceeval_n_stop(teval, keys, ts);
+		if (ret < 0)
+			pdie("Could not stop CPU");
+		return;
+	}
+}
+
+static void start_cpu(struct traceeval *teval, int cpu,
+		      enum sched_state state,  unsigned long long ts)
+{
+	update_cpu(teval, cpu, state, START, ts);
+}
+
+static void stop_cpu(struct traceeval *teval, int cpu,
+		     enum sched_state state, unsigned long long ts)
+{
+	update_cpu(teval, cpu, state, STOP, ts);
+}
+
+static void update_thread(struct process_data *pdata, int tid,
+			  enum sched_state state, enum command cmd,
+			  unsigned long long ts)
+{
+	struct traceeval_key keys[] = {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.number = tid,
+		},
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.number = state,
+		}
+	};
+	int ret;
+
+	switch (cmd) {
+	case START:
+		ret = traceeval_n_start(pdata->teval_threads, keys, ts);
+		if (ret < 0)
+			pdie("Could not start thread");
+		return;
+	case STOP:
+		ret = traceeval_n_stop(pdata->teval_threads, keys, ts);
+		if (ret < 0)
+			pdie("Could not stop thread");
+		return;
+	}
+}
+
+static void start_thread(struct process_data *pdata, int tid,
+			   enum sched_state state, unsigned long long ts)
+{
+	update_thread(pdata, tid, state, START, ts);
+}
+
+static void stop_thread(struct process_data *pdata, int tid,
+			enum sched_state state, unsigned long long ts)
+{
+	update_thread(pdata, tid, state, STOP, ts);
+}
+
+static struct tep_format_field *get_field(struct tep_event *event, const char *name)
+{
+	static struct tep_format_field *field;
+
+	field = tep_find_field(event, name);
+	if (!field)
+		die("Could not find field %s for %s",
+		    name, event->name);
+
+	return field;
+}
+
+static void init_process_data(struct process_data *pdata)
+{
+	struct traceeval_key_info cpu_info[] = {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "CPU",
+		},
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "Schedule state",
+		}
+	};
+	struct traceeval_key_info thread_info[] = {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "TID",
+		},
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "Schedule state",
+		}
+	};
+
+	pdata->teval_cpus = traceeval_2_alloc("CPUs", cpu_info);
+	if (!pdata->teval_cpus)
+		pdie("Creating trace eval");
+
+	pdata->teval_threads = traceeval_2_alloc("Threads", thread_info);
+	if (!pdata->teval_threads)
+		pdie("Creating trace eval");
+}
+
+static struct process_data *alloc_pdata(struct task_data *tdata, const char *comm)
+{
+	struct process_data *pdata;
+
+	pdata = calloc(1, sizeof(*pdata));
+	if (!pdata)
+		pdie("Allocating process data");
+	init_process_data(pdata);
+	set_process_data(tdata, comm, pdata);
+
+	return pdata;
+}
+
+static void sched_out(struct task_data *tdata, const char *comm,
+		      struct tep_event *event,
+		      struct tep_record *record, struct tep_format_field *prev_pid,
+		      struct tep_format_field *prev_state)
+{
+	struct process_data *pdata;
+	unsigned long long val;
+	int pid;
+	int ret;
+
+	ret = tep_read_number_field(prev_pid, record->data, &val);
+	if (ret < 0)
+		die("Could not read sched_switch next_pid for record");
+
+	/* Ignore the idle task */
+	pid = val;
+	if (!pid) {
+		/* Record the runtime for the process CPUs */
+		stop_cpu(tdata->teval_cpus, record->cpu, IDLE, record->ts);
+		return;
+	}
+
+	/* The process is scheduling out. Stop the run time. */
+	update_process(tdata, comm, RUNNING, STOP, record->ts);
+
+	/* Get the process data from the process running state */
+	pdata = get_process_data(tdata, comm);
+	if (!pdata)
+		pdata = alloc_pdata(tdata, comm);
+
+	ret = tep_read_number_field(prev_state, record->data, &val);
+	if (ret < 0)
+		die("Could not read sched_switch next_pid for record");
+	val &= 3;
+	/*
+	 * Save the state the process is exiting with. Will need this
+	 * when scheduled back in.
+	 */
+	if (!val)
+		pdata->state = PREEMPT;
+	else if (val & 1)
+		pdata->state = SLEEP;
+	else if (val & 2)
+		pdata->state = BLOCKED;
+
+	/* Record the state timings for the process */
+	start_process(tdata, comm, pdata->state, record->ts);
+
+	/* Record the state timings for the individual thread */
+	stop_thread(pdata, pid, RUNNING, record->ts);
+
+	/* Record the state timings for the individual thread */
+	start_thread(pdata, pid, pdata->state, record->ts);
+
+	/* Record the runtime for the process CPUs */
+	stop_cpu(pdata->teval_cpus, record->cpu, RUNNING, record->ts);
+
+	/* Record the runtime for the all CPUs */
+	stop_cpu(tdata->teval_cpus, record->cpu, RUNNING, record->ts);
+}
+
+static void sched_in(struct task_data *tdata, const char *comm,
+		     struct tep_event *event,
+		     struct tep_record *record, struct tep_format_field *next_pid)
+{
+	struct process_data *pdata;
+	unsigned long long val;
+	bool is_new = false;
+	int ret;
+	int pid;
+
+	ret = tep_read_number_field(next_pid, record->data, &val);
+	if (ret < 0)
+		die("Could not read sched_switch next_pid for record");
+	pid = val;
+
+	/* Ignore the idle task */
+	if (!pid) {
+		/* Record the runtime for the process CPUs */
+		start_cpu(tdata->teval_cpus, record->cpu, IDLE, record->ts);
+		return;
+	}
+
+	/* Start recording the running time of this process */
+	start_process(tdata, comm, RUNNING, record->ts);
+
+	pdata = get_process_data(tdata, comm);
+
+	/* Start recording the running time of process CPUs */
+	start_cpu(tdata->teval_cpus, record->cpu, RUNNING, record->ts);
+
+	/* If there was no pdata, then this process did not go through sched out */
+	if (!pdata) {
+		pdata = alloc_pdata(tdata, comm);
+		is_new = true;
+	}
+
+	/* Record the state timings for the individual thread */
+	start_thread(pdata, pid, RUNNING, record->ts);
+
+	/* Start recording the running time of process CPUs */
+	start_cpu(pdata->teval_cpus, record->cpu, RUNNING, record->ts);
+
+	/* If it was just created, there's nothing to stop */
+	if (is_new)
+		return;
+
+	/* Stop recording the thread time for its scheduled out state */
+	stop_thread(pdata, val, pdata->state, record->ts);
+
+	/* Stop recording the process time for its scheduled out state */
+	stop_process(tdata, comm, pdata->state, record->ts);
+}
+
+static int switch_func(struct tracecmd_input *handle, struct tep_event *event,
+		       struct tep_record *record, int cpu, void *data)
+{
+	static struct tep_format_field *prev_comm;
+	static struct tep_format_field *prev_pid;
+	static struct tep_format_field *prev_state;
+	static struct tep_format_field *next_comm;
+	static struct tep_format_field *next_pid;
+	struct task_data *tdata = data;
+	const char *comm;
+
+	if (!next_comm) {
+		prev_comm = get_field(event, "prev_comm");
+		prev_pid = get_field(event, "prev_pid");
+		prev_state = get_field(event, "prev_state");
+
+		next_comm = get_field(event, "next_comm");
+		next_pid = get_field(event, "next_pid");
+	}
+
+	comm = record->data + prev_comm->offset;
+	if (!tdata->comm || strcmp(comm, tdata->comm) == 0)
+		sched_out(tdata, comm, event, record, prev_pid, prev_state);
+
+	comm = record->data + next_comm->offset;
+	if (!tdata->comm || strcmp(comm, tdata->comm) == 0)
+		sched_in(tdata, comm, event, record, next_pid);
+
+	return 0;
+}
+
+static void print_microseconds(int idx, unsigned long long nsecs)
+{
+	unsigned long long usecs;
+
+	usecs = nsecs / 1000;
+	if (!nsecs || usecs)
+		printf("%*lld\n", idx, usecs);
+	else
+		printf("%*d.%03lld\n", idx, 0, nsecs);
+}
+
+static void display_cpus(struct traceeval *teval)
+{
+	struct traceeval_key_array *karray;
+	const struct traceeval_key *ckey;
+	const struct traceeval_key *skey;
+	int last_cpu = -1;
+	int i, nr;
+
+	printf("\n");
+
+	nr = traceeval_result_nr(teval);
+	if (!nr)
+		die("No result for CPUs\n");
+
+	for (i = 0; i < nr; i++) {
+		karray = traceeval_result_indx_key_array(teval, i);
+		if (!karray)
+			die("No cpu key for result %d\n", i);
+		ckey = traceeval_key_array_indx(karray, 0);
+		skey = traceeval_key_array_indx(karray, 1);
+
+
+		if (last_cpu != ckey->number)
+			printf("    CPU [%d]:\n", (int)ckey->number);
+
+		switch (skey->number) {
+		case RUNNING:
+			printf("       Running: ");
+			break;
+		case IDLE:
+			printf("          Idle: ");
+			break;
+		case BLOCKED:
+		case PREEMPT:
+		case SLEEP:
+		case OTHER:
+			printf("         \?\?(%ld): ", skey->number);
+			break;
+		}
+		printf(" time (us):");
+		print_microseconds(12, traceeval_result_indx_total(teval, i));
+
+		last_cpu = ckey->number;
+	}
+}
+
+static void display_thread(struct traceeval *teval, int tid)
+{
+	struct traceeval_key keys[2] =
+		{
+			{
+				.type = TRACEEVAL_TYPE_NUMBER,
+				.number = tid,
+			},
+			{
+				.type = TRACEEVAL_TYPE_NUMBER,
+				.number = RUNNING,
+			}
+		};
+	ssize_t ret;
+
+	printf("\n    thread id: %d\n", tid);
+
+	printf("      Total run time (us):");
+	print_microseconds(14, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
+
+	keys[1].number = PREEMPT;
+	printf("      Total preempt time (us):");
+	print_microseconds(10, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
+
+	keys[1].number = BLOCKED;
+	printf("      Total blocked time (us):");
+	print_microseconds(10, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
+
+	keys[1].number = SLEEP;
+	printf("      Total sleep time (us):");
+	print_microseconds(12, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
+};
+
+static void display_threads(struct traceeval *teval)
+{
+	struct traceeval_key_array *karray;
+	const struct traceeval_key *tkey;
+	struct traceeval_key keys[2];
+	int last_tid = -1;
+	int i, nr;
+
+	nr = traceeval_result_nr(teval);
+	if (!nr)
+		die("No result for threads\n");
+
+	memset(keys, 0, sizeof(keys));
+	keys[1].type = TRACEEVAL_TYPE_NUMBER;
+
+	for (i = 0; i < nr; i++) {
+		karray = traceeval_result_indx_key_array(teval, i);
+		if (!karray)
+			die("No thread key for result %d\n", i);
+		tkey = traceeval_key_array_indx(karray, 0);
+		if (!tkey)
+			die("No thread keys for result?");
+
+		/*
+		 * All the TIDS should be together in the results,
+		 * as the results are sorted by the first key, which
+		 * is the comm.
+		 */
+		if (last_tid == tkey->number)
+			continue;
+
+		last_tid = tkey->number;
+
+		display_thread(teval, tkey->number);
+	}
+}
+
+static void display_process(struct traceeval *teval, struct process_data *pdata,
+			    const char *comm)
+{
+	struct traceeval_key keys[2] =
+		{
+			{
+				.type = TRACEEVAL_TYPE_STRING,
+				.string = comm,
+			},
+			{
+				.type = TRACEEVAL_TYPE_NUMBER,
+				.number = RUNNING,
+			}
+		};
+	ssize_t ret;
+
+	printf("Task: %s\n", comm);
+
+	printf("  Total run time (us):");
+	print_microseconds(18, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
+
+	keys[1].number = PREEMPT;
+	printf("  Total preempt time (us):");
+	print_microseconds(14, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
+
+	keys[1].number = BLOCKED;
+	printf("  Total blocked time (us):");
+	print_microseconds(14, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
+
+	keys[1].number = SLEEP;
+	printf("  Total sleep time (us):");
+	print_microseconds(16, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
+
+	display_threads(pdata->teval_threads);
+	display_cpus(pdata->teval_cpus);
+	printf("\n");
+}
+
+static int compare_pdata(struct traceeval *teval,
+			 const struct traceeval_key_array *A,
+			 const struct traceeval_key_array *B,
+			 void *data)
+{
+	struct traceeval_key akeys[2];
+	struct traceeval_key bkeys[2];
+	const struct traceeval_key *akey;
+	const struct traceeval_key *bkey;
+	long long aval;
+	long long bval;
+	int ret;
+
+	/* Get the RUNNING values for this process */
+
+	akey = traceeval_key_array_indx(A, 0);
+	akeys[0] = *akey;
+	akeys[1].type = TRACEEVAL_TYPE_NUMBER;
+	akeys[1].number = RUNNING;
+
+	bkey = traceeval_key_array_indx(B, 0);
+	bkeys[0] = *bkey;
+	bkeys[1].type = TRACEEVAL_TYPE_NUMBER;
+	bkeys[1].number = RUNNING;
+
+	aval = traceeval_result_keys_total(teval, akey);
+	bval = traceeval_result_keys_total(teval, bkeys);
+
+	if (aval < 0)
+		return -1;
+	if (bval < 0)
+		return -1;
+
+	if (bval < aval)
+		return -1;
+	if (bval > aval)
+		return 1;
+
+	ret = strcmp(bkeys[0].string, akeys[0].string);
+
+	/* If two different processes have the same runtime, sort by name */
+	if (ret)
+		return ret;
+
+	/* Same process, sort by state */
+
+	akey = traceeval_key_array_indx(A, 1);
+	bkey = traceeval_key_array_indx(B, 1);
+
+	if (bkey->number < akey->number)
+		return -1;
+
+	return bkey->number > akey->number;
+}
+
+static void display_processes(struct traceeval *teval)
+{
+	struct traceeval_key_array *karray;
+	const struct traceeval_key *tkey;
+	struct traceeval_key keys[2];
+	struct process_data *pdata;
+	const char *last_comm = NULL;
+	int i, nr;
+
+	nr = traceeval_result_nr(teval);
+	if (!nr)
+		die("No result for processes\n");
+
+	memset(keys, 0, sizeof(keys));
+	keys[1].type = TRACEEVAL_TYPE_NUMBER;
+
+	for (i = 0; i < nr; i++) {
+		karray = traceeval_result_indx_key_array(teval, i);
+		if (!karray)
+			die("No process key for result %d\n", i);
+		tkey = traceeval_key_array_indx(karray, 0);
+		if (!tkey)
+			die("No process keys for result?");
+
+		/*
+		 * All the comms should be together in the results,
+		 * as the results are sorted by the first key, which
+		 * is the comm.
+		 */
+		if (last_comm && strcmp(tkey->string, last_comm) == 0)
+			continue;
+
+		last_comm = tkey->string;
+
+		keys[0] = *tkey;
+		keys[1].number = RUNNING;
+
+		/* All processes should have a running state */
+		pdata = traceeval_n_get_private(teval, keys);
+		if (pdata)
+			display_process(teval, pdata, keys[0].string);
+	}
+}
+
+static void display(struct task_data *tdata)
+{
+	unsigned long long total_time = 0;
+	unsigned long long idle_time = 0;
+	struct traceeval_key_array *karray;
+	const struct traceeval_key *tkey;
+	unsigned long long val;
+	int i, nr;
+
+	if (tdata->comm)
+		return display_processes(tdata->teval_processes);
+
+	printf("Total:\n");
+
+	nr = traceeval_result_nr(tdata->teval_cpus);
+	for (i = 0; i < nr; i++) {
+		karray = traceeval_result_indx_key_array(tdata->teval_cpus, i);
+		if (!karray)
+			die("No CPU keys for result %d\n", i);
+		tkey = traceeval_key_array_indx(karray, 1);
+		if (!tkey)
+			die("No state keys for CPU result %d?", i);
+
+		val = traceeval_result_indx_total(tdata->teval_cpus, i);
+		switch (tkey->number) {
+		case RUNNING:
+			total_time += val;
+			break;
+		case IDLE:
+			idle_time += val;
+			break;
+		default:
+			die("Invalid CPU state: %d\n", tkey->number);
+		}
+	}
+
+	printf("  Total  run time (us):");
+	print_microseconds(16, total_time);
+	printf("  Total idle time (us):");
+	print_microseconds(16, idle_time);
+
+	display_cpus(tdata->teval_cpus);
+
+	traceeval_sort_custom(tdata->teval_processes, compare_pdata, NULL);
+
+	printf("\n");
+	display_processes(tdata->teval_processes);
+}
+
+static void free_tdata(struct task_data *tdata)
+{
+}
+
+int main (int argc, char **argv)
+{
+	struct tracecmd_input *handle;
+	struct task_data data;
+	struct traceeval_key_info cpu_tinfo[2] = {
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "CPU"
+		},
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "Schedule state"
+		}
+	};
+	struct traceeval_key_info process_tinfo[2] = {
+		{
+			.type = TRACEEVAL_TYPE_STRING,
+			.name = "COMM"
+		},
+		{
+			.type = TRACEEVAL_TYPE_NUMBER,
+			.name = "Schedule state"
+		}
+	};
+	int c;
+
+	memset(&data, 0, sizeof(data));
+
+	argv0 = argv[0];
+
+	while ((c = getopt(argc, argv, "c:h")) >= 0) {
+		switch (c) {
+		case 'c':
+			data.comm = optarg;
+			break;
+		case 'h':
+		default:
+			usage();
+		}
+	}
+
+	argc -= optind;
+	argv += optind;
+
+	if (argc < 1)
+		usage();
+
+	handle = tracecmd_open(argv[0], TRACECMD_FL_LOAD_NO_PLUGINS);
+	if (!handle)
+		pdie("Error opening %s", argv[0]);
+
+	data.teval_processes = traceeval_2_alloc("Processes", process_tinfo);
+	if (!data.teval_processes)
+		pdie("Creating trace eval");
+
+	data.teval_cpus = traceeval_2_alloc("CPUs", cpu_tinfo);
+	if (!data.teval_cpus)
+		pdie("Creating trace eval");
+
+	tracecmd_follow_event(handle, "sched", "sched_switch", switch_func, &data);
+
+	tracecmd_iterate_events(handle, NULL, 0, NULL, NULL);
+
+	display(&data);
+
+	free_tdata(&data);
+
+	return 0;
+}
-- 
2.40.1

[PATCH v4 05/20] libtraceeval hist: Add pointer and const string types

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Add a pointer type to traceeval_data, as this can be used as a generic
pointer type. This may even obsolete the dynamic type.

Also, add a const char * "cstring" type. There's times where the key and
value data needs to be assigned to a const char *string, and without
having an option of that type, the compiler complains about losing the
const.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 08e0696f2d83..f6c4e8efb2be 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -25,6 +25,7 @@ enum traceeval_data_type {
 	TRACEEVAL_TYPE_NUMBER_32,
 	TRACEEVAL_TYPE_NUMBER_64,
 	TRACEEVAL_TYPE_NUMBER,
+	TRACEEVAL_TYPE_POINTER,
 	TRACEEVAL_TYPE_STRING,
 	TRACEEVAL_TYPE_DYNAMIC
 };
@@ -52,6 +53,8 @@ struct traceeval_dynamic {
 union traceeval_data {
 	struct traceeval_dynamic	dyn_data;
 	char				*string;
+	const char			*cstring;
+	void				*pointer;
 	unsigned long			number;
 	unsigned long long		number_64;
 	unsigned int			number_32;
-- 
2.40.1

[PATCH v4 06/20] libtraceeval histogram: Have cmp and release functions be generic

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Having the ability to override the compare function for a given type can
be very advantageous. There's also no reason that any type could ask for a
release callback to be called when the type is being released. It could be
used for information as well as for freeing.

Rename traceeval_dyn_cmp_fn to traceeval_data_cmp_fn and
 traceeval_dyn_release_fn to traceeval_data_release_fn and have
them take the union traceeval_type instead of struct traceeval_dynamic.

Also this changes the compare to pass a pointer to union traceeval_data
instead of passing in the structure of the dyn_data type.

In the structure, rename dyn_cmp to just cmp, and dyn_release to just
release.

Reviewed-by: Ross Zwisler <zwisler@google.com>
Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h | 50 +++++++++++++++++++++-------------------
 src/histograms.c         | 28 +++++++++++-----------
 2 files changed, 40 insertions(+), 38 deletions(-)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index f6c4e8efb2be..4c42c82ea045 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -64,14 +64,14 @@ union traceeval_data {
 
 struct traceeval_type;
 
-/* struct traceeval_dynamic release function signature */
-typedef void (*traceeval_dyn_release_fn)(struct traceeval_type *,
-					 struct traceeval_dynamic);
+/* release function callback on traceeval_data */
+typedef void (*traceeval_data_release_fn)(struct traceeval_type *,
+					  union traceeval_data *);
 
-/* struct traceeval_dynamic compare function signature */
-typedef int (*traceeval_dyn_cmp_fn)(struct traceeval_dynamic,
-				    struct traceeval_dynamic,
-				    struct traceeval_type *);
+/* compare function callback to compare traceeval_data */
+typedef int (*traceeval_data_cmp_fn)(const union traceeval_data *,
+				     const union traceeval_data *,
+				     struct traceeval_type *);
 
 /*
  * struct traceeval_type - Describes the type of a traceevent_data instance
@@ -79,8 +79,8 @@ typedef int (*traceeval_dyn_cmp_fn)(struct traceeval_dynamic,
  * @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)
+ * @release: An optional callback for when the data is being released
+ * @cmp: An optional callback to specify a way to compare the type
  *
  * The traceeval_type structure defines expectations for a corresponding
  * traceeval_data instance for a traceeval histogram instance. Used to
@@ -91,29 +91,31 @@ typedef int (*traceeval_dyn_cmp_fn)(struct traceeval_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.
+ * For flexibility, @cmp() and @release() take a struct traceeval_type
+ * instance. This allows the user to handle dyn_data and pointer types.
+ * It may also be used for other types if the default cmp() or release()
+ * need to be overridden. Note for string types, even if the release()
+ * is called, the string freeing is still taken care of by the traceeval
+ * infrastructure.
  *
- * @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.
+ * The @id field is a user specified field that may allow the same callback
+ * to be used by multiple types and not needing to do a strcmp() against the
+ * name (could be used for switch statements).
  *
- * 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.
+ * @cmp() is used to override the default compare of a type. This is
+ * required to compare dyn_data and pointer types. 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.
+ *
+ * @release() is called when a data element is being released (or freed).
  */
 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;
+	traceeval_data_release_fn	release;
+	traceeval_data_cmp_fn		cmp;
 };
 
 /* Statistics about a given entry element */
diff --git a/src/histograms.c b/src/histograms.c
index 9b58416ad20c..030e417105d4 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -90,9 +90,9 @@ static int compare_traceeval_type(struct traceeval_type *orig,
 			return 0;
 		if (orig[i].id != copy[i].id)
 			return 0;
-		if (orig[i].dyn_release != copy[i].dyn_release)
+		if (orig[i].release != copy[i].release)
 			return 0;
-		if (orig[i].dyn_cmp != copy[i].dyn_cmp)
+		if (orig[i].cmp != copy[i].cmp)
 			return 0;
 
 		// make sure both names are same type
@@ -128,6 +128,9 @@ static int compare_traceeval_data(union traceeval_data *orig,
 	if (!copy)
 		return 1;
 
+	if (type->cmp)
+		return type->cmp(orig, copy, type);
+
 	switch (type->type) {
 	case TRACEEVAL_TYPE_STRING:
 		i = strcmp(orig->string, copy->string);
@@ -149,8 +152,7 @@ static int compare_traceeval_data(union traceeval_data *orig,
 		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);
+		/* If it didn't specify a cmp function, then punt */
 		return 0;
 
 	default:
@@ -236,8 +238,8 @@ static int compare_hist(struct traceeval *orig, struct traceeval *copy)
  *
  * 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.
+ * by memory address, except for struct traceeval_type's release() and
+ * cmp() fields.
  *
  * Returns 1 if @orig and @copy are the same, 0 if not, and -1 on error.
  */
@@ -438,14 +440,13 @@ fail:
  */
 static void clean_data(union traceeval_data *data, struct traceeval_type *type)
 {
+		if (type->release)
+			type->release(type, data);
+
 		switch (type->type) {
 		case TRACEEVAL_TYPE_STRING:
 			free(data->string);
 			break;
-		case TRACEEVAL_TYPE_DYNAMIC:
-			if (type->dyn_release)
-				type->dyn_release(type, data->dyn_data);
-			break;
 		default:
 			break;
 		}
@@ -465,9 +466,8 @@ static void clean_data_set(union traceeval_data *data, struct traceeval_type *de
 		return;
 	}
 
-	for (i = 0; i < size; i++) {
+	for (i = 0; i < size; i++)
 		clean_data(data + i, defs + i);
-	}
 
 	free(data);
 }
@@ -512,7 +512,7 @@ static void hist_table_release(struct traceeval *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
+ * corresponding release() functions registered for keys and values of
  * type TRACEEVAL_TYPE_DYNAMIC.
  */
 void traceeval_release(struct traceeval *teval)
@@ -588,7 +588,7 @@ static int copy_traceeval_data(struct traceeval_type *type,
 /*
  * Free @data with respect to @size and @type.
  *
- * Does not call dyn_release on type TRACEEVAL_TYPE_DYNAMIC.
+ * Does not call the release callback on the data.
  */
 static void data_release(size_t size, union traceeval_data **data,
 				struct traceeval_type *type)
-- 
2.40.1

[PATCH v4 07/20] libtraceeval histograms: Add traceeval struct to compare function

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

When looking at how this code would be implemented, I found that I needed
access to the traceeval structure within the compare callbacks. Pass that
in too.

Also, rearrange the parameters a little. The traceeval and type should go
first as they describe the "object", and the data should go last as they are
the values of the function.

Reviewed-by: Ross Zwisler <zwisler@google.com>
Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h | 13 +++++++------
 src/histograms.c         | 31 ++++++++++++++++---------------
 2 files changed, 23 insertions(+), 21 deletions(-)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 4c42c82ea045..d7ffe42f3231 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -63,16 +63,17 @@ union traceeval_data {
 };
 
 struct traceeval_type;
+struct traceeval;
 
 /* release function callback on traceeval_data */
-typedef void (*traceeval_data_release_fn)(struct traceeval_type *,
-					  union traceeval_data *);
+typedef void (*traceeval_data_release_fn)(const struct traceeval_type *type,
+					  union traceeval_data *data);
 
 /* compare function callback to compare traceeval_data */
-typedef int (*traceeval_data_cmp_fn)(const union traceeval_data *,
-				     const union traceeval_data *,
-				     struct traceeval_type *);
-
+typedef int (*traceeval_data_cmp_fn)(struct traceeval *teval,
+				     const struct traceeval_type *type,
+				     const union traceeval_data *A,
+				     const union traceeval_data *B);
 /*
  * struct traceeval_type - Describes the type of a traceevent_data instance
  * @type: The enum type that describes the traceeval_data
diff --git a/src/histograms.c b/src/histograms.c
index 030e417105d4..1ed677ac0e14 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -113,9 +113,10 @@ static int compare_traceeval_type(struct traceeval_type *orig,
  * 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)
+static int compare_traceeval_data(struct traceeval *teval,
+				  struct traceeval_type *type,
+				  union traceeval_data *orig,
+				  const union traceeval_data *copy)
 {
 	int i;
 
@@ -129,7 +130,7 @@ static int compare_traceeval_data(union traceeval_data *orig,
 		return 1;
 
 	if (type->cmp)
-		return type->cmp(orig, copy, type);
+		return type->cmp(teval, type, orig, copy);
 
 	switch (type->type) {
 	case TRACEEVAL_TYPE_STRING:
@@ -167,16 +168,17 @@ static int compare_traceeval_data(union traceeval_data *orig,
  *
  * Return 1 if @orig and @copy are the same, 0 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)
+static int compare_traceeval_data_set(struct traceeval *teval,
+				      struct traceeval_type *defs,
+				      union traceeval_data *orig,
+				      const union traceeval_data *copy, 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)))
+		if ((check = compare_traceeval_data(teval, defs + i, orig + i, copy + i)))
 			return check == -2 ? -1 : 0;
 	}
 
@@ -192,14 +194,14 @@ static int compare_entries(struct entry *orig, struct entry *copy,
 	int check;
 
 	/* compare keys */
-	check = compare_traceeval_data_set(orig->keys, copy->keys,
-			teval->key_types, teval->nr_key_types);
+	check = compare_traceeval_data_set(teval, teval->key_types,
+					   orig->keys, copy->keys, teval->nr_key_types);
 	if (check < 1)
 		return check;
 
 	/* compare values */
-	check = compare_traceeval_data_set(orig->vals, copy->vals,
-			teval->val_types, teval->nr_val_types);
+	check = compare_traceeval_data_set(teval, teval->val_types,
+					   orig->vals, copy->vals, teval->nr_val_types);
 	return check;
 }
 
@@ -546,9 +548,8 @@ static int get_entry(struct traceeval *teval, const union traceeval_data *keys,
 
 	hist = teval->hist;
 	for (i = 0, entry = hist->map; i < hist->nr_entries; entry = &hist->map[++i]) {
-		check = compare_traceeval_data_set(entry->keys, keys,
-				teval->key_types, teval->nr_key_types);
-
+		check = compare_traceeval_data_set(teval, teval->key_types,
+						   entry->keys, keys, teval->nr_key_types);
 		if (!check)
 			continue;
 		break;
-- 
2.40.1

[PATCH v4 08/20] libtraceeval histogram: Remove comparing of traceeval and types

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

The compare functions for traceeval and types were created for testing. But
because the tests have not yet been pulled in, remove these functions as
they are currently unused and cause an unnecessary burden of making sure
they are updated when other code they use is updated.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 Makefile                 |   1 -
 include/traceeval-test.h |  16 -----
 src/histograms.c         | 127 ---------------------------------------
 3 files changed, 144 deletions(-)
 delete mode 100644 include/traceeval-test.h

diff --git a/Makefile b/Makefile
index 62ca9285d7a0..d8c57ef4e356 100644
--- a/Makefile
+++ b/Makefile
@@ -172,7 +172,6 @@ libs: $(LIBRARY_A) $(LIBRARY_SO)
 
 VALGRIND = $(shell which valgrind)
 UTEST_DIR = utest
-UTEST_BINARY = eval-utest
 
 test: force $(LIBRARY_STATIC)
 ifneq ($(CUNIT_INSTALLED),1)
diff --git a/include/traceeval-test.h b/include/traceeval-test.h
deleted file mode 100644
index bb8092ac2e50..000000000000
--- a/include/traceeval-test.h
+++ /dev/null
@@ -1,16 +0,0 @@
-/* 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 1ed677ac0e14..a40bfedc3cb4 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -12,8 +12,6 @@
 
 #include <traceeval-hist.h>
 
-#include "traceeval-test.h"
-
 /*
  * Compare two integers of variable length.
  *
@@ -63,50 +61,6 @@ static void print_err(const char *fmt, ...)
 	fprintf(stderr, "\n");
 }
 
-/*
- * Compare traceeval_type instances for equality.
- *
- * Return 1 if @orig and @copy are the same, 0 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 1;
-	if (!!orig != !!copy)
-		return 0;
-
-	if (orig_size != copy_size)
-		return 0;
-
-	for (i = 0; i < orig_size; i++) {
-		if (orig[i].type != copy[i].type)
-			return 0;
-		if (orig[i].flags != copy[i].flags)
-			return 0;
-		if (orig[i].id != copy[i].id)
-			return 0;
-		if (orig[i].release != copy[i].release)
-			return 0;
-		if (orig[i].cmp != copy[i].cmp)
-			return 0;
-
-		// make sure both names are same type
-		if (!!orig[i].name != !!copy[i].name)
-			return 0;
-		if (!orig[i].name)
-			continue;
-		if (strcmp(orig[i].name, copy[i].name) != 0)
-			return 0;
-	}
-
-	return 1;
-}
-
 /*
  * Compare traceeval_data instances.
  *
@@ -185,87 +139,6 @@ static int compare_traceeval_data_set(struct traceeval *teval,
 	return 1;
 }
 
-/*
- * Return 1 if @orig and @copy are the same, 0 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(teval, teval->key_types,
-					   orig->keys, copy->keys, teval->nr_key_types);
-	if (check < 1)
-		return check;
-
-	/* compare values */
-	check = compare_traceeval_data_set(teval, teval->val_types,
-					   orig->vals, copy->vals, 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 1 if struct hist_table of @orig and @copy are the same, 0 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 0;
-
-	for (size_t i = 0; i < o_hist->nr_entries; i++) {
-		if ((c = compare_entries(o_hist->map + i, c_hist->map + i, orig)) < 1)
-			return c;
-	}
-
-	return 1;
-}
-
-/*
- * 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 release() and
- * cmp() fields.
- *
- * Returns 1 if @orig and @copy are the same, 0 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;
-}
-
 /*
  * type_release - free a struct traceeval_type array
  * @defs: The array to release
-- 
2.40.1

[PATCH v4 09/20] libtraceeval: Convert hist array into a hash table

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

The lookups need to be extremely fast. Instead of doing a linear search
across all entries (which could be thousands), do a hash lookup instead.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h |   7 ++
 src/histograms.c         | 166 +++++++++++++++++++++++++++++++++------
 2 files changed, 147 insertions(+), 26 deletions(-)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index d7ffe42f3231..1edda56a712f 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -74,6 +74,12 @@ typedef int (*traceeval_data_cmp_fn)(struct traceeval *teval,
 				     const struct traceeval_type *type,
 				     const union traceeval_data *A,
 				     const union traceeval_data *B);
+
+/* make a unique value */
+typedef int (*traceeval_data_hash_fn)(struct traceeval *teval,
+				      const struct traceeval_type *type,
+				      const union traceeval_data *data);
+
 /*
  * struct traceeval_type - Describes the type of a traceevent_data instance
  * @type: The enum type that describes the traceeval_data
@@ -117,6 +123,7 @@ struct traceeval_type {
 	size_t				id;
 	traceeval_data_release_fn	release;
 	traceeval_data_cmp_fn		cmp;
+	traceeval_data_hash_fn		hash;
 };
 
 /* Statistics about a given entry element */
diff --git a/src/histograms.c b/src/histograms.c
index a40bfedc3cb4..54d156791193 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -3,6 +3,7 @@
  * libtraceeval histogram interface implementation.
  *
  * Copyright (C) 2023 Google Inc, Stevie Alvarez <stevie.6strings@gmail.com>
+ * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
  */
 
 #include <stdbool.h>
@@ -12,6 +13,14 @@
 
 #include <traceeval-hist.h>
 
+#define offset_of(type, field) ((size_t)(&(((type *)(NULL))->field)))
+#define container_of(ptr, type, field) \
+	(type *)((void *)(ptr) - (void *)offset_of(type, field))
+
+#define HASH_BITS 10	/* Start with 1K of buckets */
+#define HASH_SIZE(bits)	(1 << (bits))
+#define HASH_MASK(bits)	(HASH_SIZE(bits) - 1)
+
 /*
  * Compare two integers of variable length.
  *
@@ -25,23 +34,31 @@ do {					\
 	return (a) != (b);		\
 } while (0)				\
 
+
+struct hash_item {
+	struct hash_item	*next;
+	unsigned		key;
+};
+
+/* A hash of key-value entries */
+struct hash_table {
+	struct hash_item	**hash;
+	unsigned		bits;
+	size_t			nr_items;
+};
+
 /* A key-value pair */
 struct entry {
+	struct hash_item	hash;
 	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;
+	struct hash_table		*hist;
 	size_t				nr_key_types;
 	size_t				nr_val_types;
 };
@@ -299,6 +316,11 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
 		err_msg = "Failed to allocate memory for histogram";
 		goto fail_release;
 	}
+	teval->hist->bits = HASH_BITS;
+	teval->hist->hash = calloc(HASH_SIZE(teval->hist->bits),
+				   sizeof(*teval->hist->hash));
+	if (!teval->hist->hash)
+		goto fail_release;
 
 	return teval;
 
@@ -350,7 +372,7 @@ static void clean_data_set(union traceeval_data *data, struct traceeval_type *de
 /*
  * Free all possible data stored within the entry.
  */
-static void clean_entry(struct entry *entry, struct traceeval *teval)
+static void free_entry(struct traceeval *teval, struct entry *entry)
 {
 	if (!entry)
 		return;
@@ -358,6 +380,19 @@ static void clean_entry(struct entry *entry, struct traceeval *teval)
 	/* free dynamic traceeval_data */
 	clean_data_set(entry->keys, teval->key_types, teval->nr_key_types);
 	clean_data_set(entry->vals, teval->val_types, teval->nr_val_types);
+
+	free(entry);
+}
+
+static void free_entries(struct traceeval *teval, struct hash_item *item)
+{
+	struct entry *entry;
+
+	while (item) {
+		entry = container_of(item, struct entry, hash);
+		item = item->next;
+		free_entry(teval, entry);
+	}
 }
 
 /*
@@ -365,16 +400,19 @@ static void clean_entry(struct entry *entry, struct traceeval *teval)
  */
 static void hist_table_release(struct traceeval *teval)
 {
-	struct hist_table *hist = teval->hist;
+	struct hash_table *hist = teval->hist;
 
 	if (!hist)
 		return;
 
-	for (size_t i = 0; i < hist->nr_entries; i++) {
-		clean_entry(hist->map + i, teval);
+	for (size_t i = 0; i < HASH_SIZE(hist->bits); i++) {
+		if (!hist->hash[i])
+			continue;
+
+		free_entries(teval, hist->hash[i]);
 	}
 
-	free(hist->map);
+	free(hist->hash);
 	free(hist);
 	teval->hist = NULL;
 }
@@ -403,6 +441,58 @@ void traceeval_release(struct traceeval *teval)
 	free(teval);
 }
 
+static unsigned long long hash_string(const char *str)
+{
+	unsigned long long key = 0;
+	int len = strlen(str);
+	int i;
+
+	for (i = 0; i < len; i++)
+		key += (unsigned long long)str[i] << ((i & 7) * 8);
+
+	return key;
+}
+
+static unsigned make_hash(struct traceeval *teval, const union traceeval_data *keys,
+			  int bits)
+{
+	const struct traceeval_type *types = teval->key_types;
+	unsigned long long val;
+	unsigned key = 0;
+	int nr = teval->nr_key_types;
+
+	for (int i = 0; i < nr; i++) {
+		if (types[i].hash) {
+			key += types[i].hash(teval, &types[i], &keys[i]);
+			continue;
+		}
+
+		switch (types[i].type) {
+		case TRACEEVAL_TYPE_NUMBER_8:
+		case TRACEEVAL_TYPE_NUMBER_16:
+		case TRACEEVAL_TYPE_NUMBER_32:
+		case TRACEEVAL_TYPE_NUMBER_64:
+		case TRACEEVAL_TYPE_NUMBER:
+			val = keys[i].number_64;
+			break;
+		case TRACEEVAL_TYPE_STRING:
+			val = hash_string(keys[i].cstring);
+			break;
+		default:
+			val = 0;
+		}
+ /*
+ * This is a quick hashing function adapted from Donald E. Knuth's 32
+ * bit multiplicative hash. See The Art of Computer Programming (TAOCP).
+ * Multiplication by the Prime number, closest to the golden ratio of
+ * 2^32.
+ */
+		key += val * 2654435761;
+	}
+
+	return key & HASH_MASK(bits);
+}
+
 /*
  * Find the entry that @keys corresponds to within @teval.
  *
@@ -411,21 +501,24 @@ void traceeval_release(struct traceeval *teval)
 static int get_entry(struct traceeval *teval, const union traceeval_data *keys,
 		     struct entry **result)
 {
-	struct hist_table *hist;
+	struct hash_table *hist = teval->hist;
 	struct entry *entry;
+	unsigned key;
 	int check = 0;
-	int i;
 
 	if (!teval || !keys)
 		return -1;
 
+	key = make_hash(teval, keys, hist->bits);
+
 	hist = teval->hist;
-	for (i = 0, entry = hist->map; i < hist->nr_entries; entry = &hist->map[++i]) {
+
+	for (struct hash_item *item = hist->hash[key]; item; item = item->next) {
+		entry = container_of(item, struct entry, hash);
 		check = compare_traceeval_data_set(teval, teval->key_types,
 						   entry->keys, keys, teval->nr_key_types);
-		if (!check)
-			continue;
-		break;
+		if (check)
+			break;
 	}
 
 	if (check > 0)
@@ -536,6 +629,7 @@ int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 	/* find key and copy its corresponding value pair */
 	if ((check = get_entry(teval, keys, &entry)) < 1)
 		return check;
+
 	return dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
 				      entry->vals, results);
 }
@@ -563,6 +657,28 @@ void traceeval_results_release(struct traceeval *teval,
 	data_release(teval->nr_val_types, &results, teval->val_types);
 }
 
+static struct entry *create_hist_entry(struct traceeval *teval,
+				       const union traceeval_data *keys)
+{
+	struct hash_table *hist = teval->hist;
+	struct hash_item *item;
+	unsigned key = make_hash(teval, keys, hist->bits);
+	struct entry *entry;
+
+	entry = calloc(1, sizeof(*entry));
+	if (!entry)
+		return NULL;
+
+	item = &entry->hash;
+	item->next = hist->hash[key];
+	hist->hash[key] = item;
+	item->key = key;
+
+	hist->nr_items++;
+
+	return entry;
+}
+
 /*
  * Create a new entry in @teval with respect to @keys and @vals.
  *
@@ -574,8 +690,7 @@ static int create_entry(struct traceeval *teval,
 {
 	union traceeval_data *new_keys;
 	union traceeval_data *new_vals;
-	struct entry *tmp_map;
-	struct hist_table *hist = teval->hist;
+	struct entry *entry;
 
 	/* copy keys */
 	if (dup_traceeval_data_set(teval->nr_key_types, teval->key_types,
@@ -587,13 +702,12 @@ static int create_entry(struct traceeval *teval,
 				   vals, &new_vals) == -1)
 		goto fail_vals;
 
-	/* create new entry */
-	tmp_map = realloc(hist->map, ++hist->nr_entries * sizeof(*tmp_map));
-	if (!tmp_map)
+	entry = create_hist_entry(teval, keys);
+	if (!entry)
 		goto fail;
-	tmp_map->keys = new_keys;
-	tmp_map->vals = new_vals;
-	hist->map = tmp_map;
+
+	entry->keys = new_keys;
+	entry->vals = new_vals;
 
 	return 0;
 
-- 
2.40.1

[PATCH v4 10/20] libtraceeval histograms: Move hash functions into their own file

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Move the hash functions into their own file so that it does not clutter
the histogram.c file. Functionality should be the same, but some code
restructuring was done.

To keep the hash abstract, helper functions were introduced:

  hash_iter_start() - to start iterating over all items in the hash
  hash_iter_next() - to get the next item in the hash

  hash_iter_bucket() - to start iterating over a single bucket in the hash
  hash_iter_bucket_next() - to get the next item in the bucket

  hash_nr_items() - to get the number of items in the hash

Also implemented hash_remove() to remove an item from the hash.

Also created a eval-local.h header file to store the prototypes of the
local functions as well as moved the structures there too.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 src/Makefile     |   1 +
 src/eval-local.h | 103 +++++++++++++++++++++++++++++++++++++++
 src/hash.c       | 123 +++++++++++++++++++++++++++++++++++++++++++++++
 src/histograms.c | 121 +++++++---------------------------------------
 4 files changed, 244 insertions(+), 104 deletions(-)
 create mode 100644 src/eval-local.h
 create mode 100644 src/hash.c

diff --git a/src/Makefile b/src/Makefile
index b32a3891333d..4b7b3051a8b2 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -5,6 +5,7 @@ include $(src)/scripts/utils.mk
 OBJS =
 OBJS += trace-analysis.o
 OBJS += histograms.o
+OBJS += hash.o
 
 OBJS := $(OBJS:%.o=$(bdir)/%.o)
 
diff --git a/src/eval-local.h b/src/eval-local.h
new file mode 100644
index 000000000000..007fdb146b96
--- /dev/null
+++ b/src/eval-local.h
@@ -0,0 +1,103 @@
+/* SPDX-License-Identifier: MIT */
+#ifndef __EVAL_LOCAL_H
+#define __EVAL_LOCAL_H
+
+#include <string.h>
+
+#define __hidden __attribute__((visibility ("hidden")))
+
+#define offset_of(type, field) ((size_t)(&(((type *)(NULL))->field)))
+#define container_of(ptr, type, field) \
+	(type *)((void *)(ptr) - (void *)offset_of(type, field))
+
+#define HASH_BITS 10	/* Start with 1K of buckets */
+#define HASH_SIZE(bits)	(1 << (bits))
+#define HASH_MASK(bits)	(HASH_SIZE(bits) - 1)
+
+/*
+ * 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)				\
+
+struct hash_item {
+	struct hash_item	*next;
+	unsigned		key;
+};
+
+struct hash_iter {
+	struct hash_item	*next_item;
+	size_t			current_bucket;
+};
+
+/* A table of key-value entries */
+struct hash_table {
+	struct hash_item	**hash;
+	unsigned		bits;
+	size_t			nr_items;
+	struct hash_iter	iter;
+};
+
+/* A key-value pair */
+struct entry {
+	struct hash_item	hash;
+	union traceeval_data	*keys;
+	union traceeval_data	*vals;
+};
+
+/* Histogram */
+struct traceeval {
+	struct traceeval_type		*key_types;
+	struct traceeval_type		*val_types;
+	struct hash_table		*hist;
+	size_t				nr_key_types;
+	size_t				nr_val_types;
+};
+
+extern struct hash_table *hash_alloc(void);
+extern void hash_free(struct hash_table *hash);
+extern void hash_add(struct hash_table *hash, struct hash_item *item, unsigned key);
+extern int hash_remove(struct hash_table *hash, struct hash_item *item);
+
+extern struct hash_iter *hash_iter_start(struct hash_table *hash);
+extern struct hash_item *hash_iter_next(struct hash_iter *iter);
+
+extern struct hash_iter *hash_iter_bucket(struct hash_table *hash, unsigned key);
+extern struct hash_item *hash_iter_bucket_next(struct hash_iter *iter);
+
+static inline size_t hash_nr_items(struct hash_table *hash)
+{
+	return hash->nr_items;
+}
+
+static inline unsigned long long hash_string(const char *str)
+{
+	unsigned long long key = 0;
+	int len = strlen(str);
+	int i;
+
+	for (i = 0; i < len; i++)
+		key += (unsigned long long)str[i] << ((i & 7) * 8);
+
+	return key;
+}
+
+ /*
+ * This is a quick hashing function adapted from Donald E. Knuth's 32
+ * bit multiplicative hash. See The Art of Computer Programming (TAOCP).
+ * Multiplication by the Prime number, closest to the golden ratio of
+ * 2^32.
+ */
+static inline unsigned long long hash_number(unsigned long long val)
+{
+		return val * 2654435761ULL;
+}
+
+#endif
diff --git a/src/hash.c b/src/hash.c
new file mode 100644
index 000000000000..82962fbba8d8
--- /dev/null
+++ b/src/hash.c
@@ -0,0 +1,123 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval hashtable interface implementation.
+ *
+ * Copyright (C) 2023 Google Inc, Steven Rostedt <rostedt@goodmis.org>
+ */
+
+#include <traceeval-hist.h>
+
+#include "eval-local.h"
+
+__hidden struct hash_table *hash_alloc(void)
+{
+	struct hash_table *hash;
+
+	hash = calloc(1, sizeof(*hash));
+	if (!hash)
+		return NULL;
+
+	hash->bits = HASH_BITS;
+	hash->hash = calloc(HASH_SIZE(hash->bits), sizeof(*hash->hash));
+	if (!hash->hash) {
+		free(hash);
+		hash = NULL;
+	}
+
+	return hash;
+}
+
+__hidden void hash_free(struct hash_table *hash)
+{
+	free(hash->hash);
+	free(hash);
+}
+
+__hidden void hash_add(struct hash_table *hash, struct hash_item *item, unsigned key)
+{
+	key &= HASH_MASK(hash->bits);
+
+	item->next = hash->hash[key];
+	hash->hash[key] = item;
+	item->key = key;
+
+	hash->nr_items++;
+}
+
+__hidden int hash_remove(struct hash_table *hash, struct hash_item *item)
+{
+	struct hash_item **parent;
+
+	for (parent = &hash->hash[item->key]; *parent; parent = &(*parent)->next) {
+		if (*parent == item) {
+			*parent = item->next;
+			hash->nr_items--;
+			return 1;
+		}
+	}
+	return 0;
+}
+
+__hidden struct hash_iter *hash_iter_start(struct hash_table *hash)
+{
+	struct hash_iter *iter = &hash->iter;
+	size_t i;
+
+	for (i = 0; i < HASH_SIZE(hash->bits); i++) {
+		if (!hash->hash[i])
+			continue;
+		iter->next_item = hash->hash[i];
+		break;
+	}
+	iter->current_bucket = i;
+	return iter;
+}
+
+__hidden struct hash_item *hash_iter_next(struct hash_iter *iter)
+{
+	struct hash_table *hash = container_of(iter, struct hash_table, iter);
+	struct hash_item *item;
+
+	if (iter->current_bucket >= HASH_SIZE(hash->bits))
+		return NULL;
+
+	item = iter->next_item;
+	if (!item)
+		return NULL;
+
+	iter->next_item = item->next;
+	if (!iter->next_item) {
+		size_t i;
+
+		for (i = iter->current_bucket + 1; i < HASH_SIZE(hash->bits); i++) {
+			if (!hash->hash[i])
+				continue;
+			iter->next_item = hash->hash[i];
+			break;
+		}
+		iter->current_bucket = i;
+	}
+	return item;
+}
+
+__hidden struct hash_iter *hash_iter_bucket(struct hash_table *hash, unsigned key)
+{
+	struct hash_iter *iter = &hash->iter;
+
+	key &= HASH_MASK(hash->bits);
+
+	iter->current_bucket = key;
+	iter->next_item = hash->hash[key];
+
+	return iter;
+}
+
+__hidden struct hash_item *hash_iter_bucket_next(struct hash_iter *iter)
+{
+	struct hash_item *item = iter->next_item;
+
+	if (item)
+		iter->next_item = item->next;
+
+	return item;
+}
diff --git a/src/histograms.c b/src/histograms.c
index 54d156791193..b1c6bb4fc990 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -12,56 +12,7 @@
 #include <stdio.h>
 
 #include <traceeval-hist.h>
-
-#define offset_of(type, field) ((size_t)(&(((type *)(NULL))->field)))
-#define container_of(ptr, type, field) \
-	(type *)((void *)(ptr) - (void *)offset_of(type, field))
-
-#define HASH_BITS 10	/* Start with 1K of buckets */
-#define HASH_SIZE(bits)	(1 << (bits))
-#define HASH_MASK(bits)	(HASH_SIZE(bits) - 1)
-
-/*
- * 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)				\
-
-
-struct hash_item {
-	struct hash_item	*next;
-	unsigned		key;
-};
-
-/* A hash of key-value entries */
-struct hash_table {
-	struct hash_item	**hash;
-	unsigned		bits;
-	size_t			nr_items;
-};
-
-/* A key-value pair */
-struct entry {
-	struct hash_item	hash;
-	union traceeval_data	*keys;
-	union traceeval_data	*vals;
-};
-
-/* Histogram */
-struct traceeval {
-	struct traceeval_type		*key_types;
-	struct traceeval_type		*val_types;
-	struct hash_table		*hist;
-	size_t				nr_key_types;
-	size_t				nr_val_types;
-};
+#include "eval-local.h"
 
 /*
  * print_err - print an error message
@@ -311,16 +262,11 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
 	}
 
 	/* alloc hist */
-	teval->hist = calloc(1, sizeof(*teval->hist));
+	teval->hist = hash_alloc();
 	if (!teval->hist) {
 		err_msg = "Failed to allocate memory for histogram";
 		goto fail_release;
 	}
-	teval->hist->bits = HASH_BITS;
-	teval->hist->hash = calloc(HASH_SIZE(teval->hist->bits),
-				   sizeof(*teval->hist->hash));
-	if (!teval->hist->hash)
-		goto fail_release;
 
 	return teval;
 
@@ -384,36 +330,26 @@ static void free_entry(struct traceeval *teval, struct entry *entry)
 	free(entry);
 }
 
-static void free_entries(struct traceeval *teval, struct hash_item *item)
-{
-	struct entry *entry;
-
-	while (item) {
-		entry = container_of(item, struct entry, hash);
-		item = item->next;
-		free_entry(teval, entry);
-	}
-}
-
 /*
  * Free the hist_table allocated to a traceeval instance.
  */
 static void hist_table_release(struct traceeval *teval)
 {
 	struct hash_table *hist = teval->hist;
+	struct hash_iter *iter;
+	struct hash_item *item;
 
 	if (!hist)
 		return;
 
-	for (size_t i = 0; i < HASH_SIZE(hist->bits); i++) {
-		if (!hist->hash[i])
-			continue;
+	for (iter = hash_iter_start(hist); (item = hash_iter_next(iter)); ) {
+		struct entry *entry = container_of(item, struct entry, hash);
 
-		free_entries(teval, hist->hash[i]);
+		hash_remove(hist, &entry->hash);
+		free_entry(teval, entry);
 	}
 
-	free(hist->hash);
-	free(hist);
+	hash_free(hist);
 	teval->hist = NULL;
 }
 
@@ -441,18 +377,6 @@ void traceeval_release(struct traceeval *teval)
 	free(teval);
 }
 
-static unsigned long long hash_string(const char *str)
-{
-	unsigned long long key = 0;
-	int len = strlen(str);
-	int i;
-
-	for (i = 0; i < len; i++)
-		key += (unsigned long long)str[i] << ((i & 7) * 8);
-
-	return key;
-}
-
 static unsigned make_hash(struct traceeval *teval, const union traceeval_data *keys,
 			  int bits)
 {
@@ -481,16 +405,10 @@ static unsigned make_hash(struct traceeval *teval, const union traceeval_data *k
 		default:
 			val = 0;
 		}
- /*
- * This is a quick hashing function adapted from Donald E. Knuth's 32
- * bit multiplicative hash. See The Art of Computer Programming (TAOCP).
- * Multiplication by the Prime number, closest to the golden ratio of
- * 2^32.
- */
-		key += val * 2654435761;
+		key += hash_number(val);
 	}
 
-	return key & HASH_MASK(bits);
+	return key;
 }
 
 /*
@@ -502,7 +420,9 @@ static int get_entry(struct traceeval *teval, const union traceeval_data *keys,
 		     struct entry **result)
 {
 	struct hash_table *hist = teval->hist;
-	struct entry *entry;
+	struct entry *entry = NULL;
+	struct hash_iter *iter;
+	struct hash_item *item;
 	unsigned key;
 	int check = 0;
 
@@ -511,10 +431,9 @@ static int get_entry(struct traceeval *teval, const union traceeval_data *keys,
 
 	key = make_hash(teval, keys, hist->bits);
 
-	hist = teval->hist;
-
-	for (struct hash_item *item = hist->hash[key]; item; item = item->next) {
+	for (iter = hash_iter_bucket(hist, key); (item = hash_iter_bucket_next(iter)); ) {
 		entry = container_of(item, struct entry, hash);
+
 		check = compare_traceeval_data_set(teval, teval->key_types,
 						   entry->keys, keys, teval->nr_key_types);
 		if (check)
@@ -661,7 +580,6 @@ static struct entry *create_hist_entry(struct traceeval *teval,
 				       const union traceeval_data *keys)
 {
 	struct hash_table *hist = teval->hist;
-	struct hash_item *item;
 	unsigned key = make_hash(teval, keys, hist->bits);
 	struct entry *entry;
 
@@ -669,12 +587,7 @@ static struct entry *create_hist_entry(struct traceeval *teval,
 	if (!entry)
 		return NULL;
 
-	item = &entry->hash;
-	item->next = hist->hash[key];
-	hist->hash[key] = item;
-	item->key = key;
-
-	hist->nr_items++;
+	hash_add(hist, &entry->hash, key);
 
 	return entry;
 }
-- 
2.40.1

[PATCH v4 11/20] libtraceeval histogram: Label and check keys and values

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

When initializing the traceeval descriptor, mark each key and value as
their type via the flags (keys get TRACEEVAL_FL_KEY and values get
TRACEEVAL_FL_VALUE) as well as adding the index of that key/value type of
the key/value data it represents. This will be used by the iterators for
sorting. The iterator will point to the key/value type and use that
information to know which key/value data to sort with.

The keys and values passed in will also be updated to have their flags
match the proper key/value type as well as the index. This will be useful
for traceeval_stat() that will take the type as a parameter, and use it to
figure out fast where the data is that is to be looked up.

All pointer and dynamic types in keys must have both a cmp and hash
function defined, otherwise they cannot be indexed or hashed. Add a check
to make sure all key types of pointer and dynamic have those functions.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h | 11 +++++---
 src/histograms.c         | 60 ++++++++++++++++++++++++++++++++++++++--
 2 files changed, 64 insertions(+), 7 deletions(-)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 1edda56a712f..f80d039baa61 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -32,8 +32,10 @@ enum traceeval_data_type {
 
 /* Statistics specification flags */
 enum traceeval_flags {
-	TRACEEVAL_FL_SIGNED		= (1 << 0),
-	TRACEEVAL_FL_TIMESTAMP		= (1 << 1),
+	TRACEEVAL_FL_KEY		= (1 << 0),
+	TRACEEVAL_FL_VALUE		= (1 << 1),
+	TRACEEVAL_FL_SIGNED		= (1 << 2),
+	TRACEEVAL_FL_TIMESTAMP		= (1 << 3),
 };
 
 /*
@@ -120,6 +122,7 @@ struct traceeval_type {
 	char				*name;
 	enum traceeval_data_type	type;
 	size_t				flags;
+	size_t				index;
 	size_t				id;
 	traceeval_data_release_fn	release;
 	traceeval_data_cmp_fn		cmp;
@@ -142,8 +145,8 @@ struct traceeval;
 
 /* Histogram interfaces */
 
-struct traceeval *traceeval_init(const struct traceeval_type *keys,
-				 const struct traceeval_type *vals);
+struct traceeval *traceeval_init(struct traceeval_type *keys,
+				 struct traceeval_type *vals);
 
 void traceeval_release(struct traceeval *teval);
 
diff --git a/src/histograms.c b/src/histograms.c
index b1c6bb4fc990..4b4b559964d1 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -202,6 +202,44 @@ fail:
 	return -1;
 }
 
+static int check_keys(struct traceeval_type *keys)
+{
+	for (int i = 0; keys[i].type != TRACEEVAL_TYPE_NONE; i++) {
+		/* Define this as a key */
+		keys[i].flags |= TRACEEVAL_FL_KEY;
+		keys[i].flags &= ~TRACEEVAL_FL_VALUE;
+
+		keys[i].index = i;
+
+		switch (keys[i].type) {
+		case TRACEEVAL_TYPE_POINTER:
+		case TRACEEVAL_TYPE_DYNAMIC:
+			/*
+			 * Key pointers and dynamic types must have a
+			 * cmp and hash function
+			 */
+			if (!keys[i].cmp || !keys[i].hash)
+				return -1;
+			break;
+		default:
+			break;
+		}
+	}
+	return 0;
+}
+
+static int check_vals(struct traceeval_type *vals)
+{
+	for (int i = 0; vals[i].type != TRACEEVAL_TYPE_NONE; i++) {
+		/* Define this as a value */
+		vals[i].flags |= TRACEEVAL_FL_VALUE;
+		vals[i].flags &= ~TRACEEVAL_FL_KEY;
+
+		vals[i].index = i;
+	}
+	return 0;
+}
+
 /*
  * traceeval_init - create a traceeval descriptor
  * @keys: Defines the keys to differentiate traceeval entries
@@ -212,7 +250,12 @@ fail:
  * 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.
+ * The @keys and @vals passed in are copied for internal use, but they are
+ * still modified to add the flags to denote their type (key or value) as
+ * well as the index into the keys or vals array respectively. This is
+ * to help speed up other operations that may need to know the index of
+ * the given type, and remove the burden from the user to make sure they
+ * are added.
  *
  * For any member of @keys or @vals that isn't of type TRACEEVAL_TYPE_NONE,
  * the name field must be a null-terminated string. Members of type
@@ -226,11 +269,12 @@ fail:
  *
  * 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 *traceeval_init(struct traceeval_type *keys,
+				 struct traceeval_type *vals)
 {
 	struct traceeval *teval;
 	char *err_msg;
+	int ret;
 
 	if (!keys)
 		return NULL;
@@ -247,6 +291,16 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
 		goto fail;
 	}
 
+	ret = check_keys(keys);
+	if (ret < 0)
+		goto fail_release;
+
+	if (vals) {
+		ret = check_vals(vals);
+		if (ret < 0)
+			goto fail_release;
+	}
+
 	/* alloc key types */
 	teval->nr_key_types = type_alloc(keys, &teval->key_types);
 	if (teval->nr_key_types <= 0) {
-- 
2.40.1

[PATCH v4 12/20] libtraceeval histogram: Add updating of stats

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Whenever an entry is added that already exists (overwriting the values)
keep track of the stats for the number values (max, min, total, count).

Also move the stat structure out of the public view. We may want to modify
this structure in the future, and so it should not become an API.

Add accessor functions to get to the stat values.

Add traceeval_stat() to acquire a stat handle from a specific key for a
specific value.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h |  17 ++--
 src/eval-local.h         |   9 ++
 src/histograms.c         | 182 +++++++++++++++++++++++++++++++++++----
 3 files changed, 183 insertions(+), 25 deletions(-)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index f80d039baa61..164d34c0fa81 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -130,13 +130,7 @@ struct traceeval_type {
 };
 
 /* 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;
-};
+struct traceeval_stat;
 
 /* Iterator over aggregated data */
 struct traceeval_iterator;
@@ -160,4 +154,13 @@ int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 void traceeval_results_release(struct traceeval *teval,
 			       union traceeval_data *results);
 
+struct traceeval_stat *traceeval_stat(struct traceeval *teval,
+				      const union traceeval_data *keys,
+				      struct traceeval_type *type);
+
+unsigned long long traceeval_stat_max(struct traceeval_stat *stat);
+unsigned long long traceeval_stat_min(struct traceeval_stat *stat);
+unsigned long long traceeval_stat_total(struct traceeval_stat *stat);
+unsigned long long traceeval_stat_count(struct traceeval_stat *stat);
+
 #endif /* __LIBTRACEEVAL_HIST_H__ */
diff --git a/src/eval-local.h b/src/eval-local.h
index 007fdb146b96..ed2e8abc9b63 100644
--- a/src/eval-local.h
+++ b/src/eval-local.h
@@ -45,11 +45,20 @@ struct hash_table {
 	struct hash_iter	iter;
 };
 
+struct traceeval_stat {
+	unsigned long long	max;
+	unsigned long long	min;
+	unsigned long long	total;
+	unsigned long long	std;
+	size_t			count;
+};
+
 /* A key-value pair */
 struct entry {
 	struct hash_item	hash;
 	union traceeval_data	*keys;
 	union traceeval_data	*vals;
+	struct traceeval_stat	*val_stats;
 };
 
 /* Histogram */
diff --git a/src/histograms.c b/src/histograms.c
index 4b4b559964d1..592e9c5f78a4 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -505,21 +505,85 @@ static int get_entry(struct traceeval *teval, const union traceeval_data *keys,
  * Return 0 on success, -1 on error.
  */
 static int copy_traceeval_data(struct traceeval_type *type,
-				union traceeval_data *dst,
-				const union traceeval_data *src)
+			       struct traceeval_stat *stat,
+			       union traceeval_data *dst,
+			       const union traceeval_data *src)
 {
+	unsigned long long val;
+
 	*dst = *src;
 
-	if (type->type == TRACEEVAL_TYPE_STRING) {
+	switch(type->type) {
+	case TRACEEVAL_TYPE_NUMBER:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)dst->number;
+		else
+			val = (unsigned long long)dst->number;
+		break;
+
+	case TRACEEVAL_TYPE_NUMBER_64:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)dst->number_64;
+		else
+			val = (unsigned long long)dst->number_64;
+		break;
+
+	case TRACEEVAL_TYPE_NUMBER_32:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)dst->number_32;
+		else
+			val = (unsigned long long)dst->number_32;
+		break;
+
+	case TRACEEVAL_TYPE_NUMBER_16:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)dst->number_16;
+		else
+			val = (unsigned long long)dst->number_16;
+		break;
+
+	case TRACEEVAL_TYPE_NUMBER_8:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)dst->number_8;
+		else
+			val = (unsigned long long)dst->number_8;
+		break;
+
+	case TRACEEVAL_TYPE_STRING:
 		dst->string = NULL;
 
 		if (src->string)
 			dst->string = strdup(src->string);
-		else
-			return 0;
 
 		if (!dst->string)
 			return -1;
+		return 0;
+	default:
+		return 0;
+	}
+
+	if (!stat)
+		return 0;
+
+	if (!stat->count++) {
+		stat->max = val;
+		stat->min = val;
+		stat->total = val;
+		return 0;
+	}
+
+	if (type->flags & TRACEEVAL_FL_SIGNED) {
+		if ((long long)stat->max < (long long)val)
+			stat->max = val;
+		if ((long long)stat->min > (long long)val)
+			stat->min = val;
+		stat->total += (long long)val;
+	} else {
+		if (stat->max < val)
+			stat->max = val;
+		if (stat->min > val)
+			stat->min = val;
+		stat->total += val;
 	}
 
 	return 0;
@@ -547,6 +611,7 @@ static void data_release(size_t size, union traceeval_data **data,
  * Returns 1 on success, -1 on error.
  */
 static int dup_traceeval_data_set(size_t size, struct traceeval_type *type,
+				  struct traceeval_stat *stats,
 				  const union traceeval_data *orig,
 				  union traceeval_data **copy)
 {
@@ -561,7 +626,8 @@ static int dup_traceeval_data_set(size_t size, struct traceeval_type *type,
 		return -1;
 
 	for (i = 0; i < size; i++) {
-		if (copy_traceeval_data(type + i, (*copy) + i, orig + i))
+		if (copy_traceeval_data(type + i, stats ? stats + i : NULL,
+					 (*copy) + i, orig + i))
 			goto fail;
 	}
 
@@ -604,7 +670,7 @@ int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 		return check;
 
 	return dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
-				      entry->vals, results);
+				      NULL, entry->vals, results);
 }
 
 /*
@@ -659,18 +725,22 @@ static int create_entry(struct traceeval *teval,
 	union traceeval_data *new_vals;
 	struct entry *entry;
 
+	entry = create_hist_entry(teval, keys);
+	if (!entry)
+		return -1;
+
+	entry->val_stats = calloc(teval->nr_key_types, sizeof(*entry->val_stats));
+	if (!entry->val_stats)
+		goto fail_entry;
+
 	/* copy keys */
 	if (dup_traceeval_data_set(teval->nr_key_types, teval->key_types,
-				   keys, &new_keys) == -1)
-		return -1;
+				   NULL, keys, &new_keys) == -1)
+		goto fail_stats;
 
 	/* copy vals */
 	if (dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
-				   vals, &new_vals) == -1)
-		goto fail_vals;
-
-	entry = create_hist_entry(teval, keys);
-	if (!entry)
+				   entry->val_stats, vals, &new_vals) == -1)
 		goto fail;
 
 	entry->keys = new_keys;
@@ -679,10 +749,13 @@ static int create_entry(struct traceeval *teval,
 	return 0;
 
 fail:
-	data_release(teval->nr_val_types, &new_vals, teval->val_types);
-
-fail_vals:
 	data_release(teval->nr_key_types, &new_keys, teval->key_types);
+
+fail_stats:
+	free(entry->val_stats);
+
+fail_entry:
+	free(entry);
 	return -1;
 }
 
@@ -699,7 +772,7 @@ static int update_entry(struct traceeval *teval, struct entry *entry,
 	union traceeval_data *new_vals;
 
 	if (dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
-				   vals, &new_vals) == -1)
+				   entry->val_stats, vals, &new_vals) == -1)
 		return -1;
 
 	clean_data_set(entry->vals, teval->val_types, teval->nr_val_types);
@@ -707,6 +780,79 @@ static int update_entry(struct traceeval *teval, struct entry *entry,
 	return 0;
 }
 
+struct traceeval_stat *traceeval_stat(struct traceeval *teval,
+				      const union traceeval_data *keys,
+				      struct traceeval_type *type)
+{
+	struct entry *entry;
+	int ret;
+
+	/* Only value numbers have stats */
+	if (!(type->flags & TRACEEVAL_FL_VALUE))
+		return NULL;
+
+	switch (type->type) {
+	case TRACEEVAL_TYPE_NUMBER:
+	case TRACEEVAL_TYPE_NUMBER_64:
+	case TRACEEVAL_TYPE_NUMBER_32:
+	case TRACEEVAL_TYPE_NUMBER_16:
+	case TRACEEVAL_TYPE_NUMBER_8:
+		break;
+	default:
+		return NULL;
+	}
+
+	ret = get_entry(teval, keys, &entry);
+	if (ret <= 0)
+		return NULL;
+
+	return &entry->val_stats[type->index];
+}
+
+/**
+ * traceeval_stat_max - return max value of stat
+ * @stat: The stat structure that holds the stats
+ *
+ * Returns the max value within @stat.
+ */
+unsigned long long traceeval_stat_max(struct traceeval_stat *stat)
+{
+	return stat->max;
+}
+
+/**
+ * traceeval_stat_min - return min value of stat
+ * @stat: The stat structure that holds the stats
+ *
+ * Returns the min value within @stat.
+ */
+unsigned long long traceeval_stat_min(struct traceeval_stat *stat)
+{
+	return stat->min;
+}
+
+/**
+ * traceeval_stat_total - return total value of stat
+ * @stat: The stat structure that holds the stats
+ *
+ * Returns the total value within @stat.
+ */
+unsigned long long traceeval_stat_total(struct traceeval_stat *stat)
+{
+	return stat->total;
+}
+
+/**
+ * traceeval_stat_count - return count value of stat
+ * @stat: The stat structure that holds the stats
+ *
+ * Returns the count value within @stat.
+ */
+unsigned long long traceeval_stat_count(struct traceeval_stat *stat)
+{
+	return stat->count;
+}
+
 /*
  * traceeval_insert - insert an item into the traceeval descriptor
  * @teval: The descriptor to insert into
-- 
2.40.1

[PATCH v4 13/20] libtraceeval histogram: Add iterator APIs

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Provide an interface for the application to iterate over all the entries
in the traceeval histogram.

 traceeval_iterator_get() - acquire an iterator for the given traceeval
 traceveal_iterator_put() - release the iterator
 traceeval_iterator_sort() - sort the iterator for a given key/value
 traceeval_iterator_next() - return the keys of the next entry in the
                             traceeval

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h |   7 ++
 src/eval-local.h         |  11 ++
 src/histograms.c         | 258 ++++++++++++++++++++++++++++++++++++++-
 3 files changed, 275 insertions(+), 1 deletion(-)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 164d34c0fa81..e8a7981ac2c0 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -163,4 +163,11 @@ unsigned long long traceeval_stat_min(struct traceeval_stat *stat);
 unsigned long long traceeval_stat_total(struct traceeval_stat *stat);
 unsigned long long traceeval_stat_count(struct traceeval_stat *stat);
 
+struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval);
+void traceeval_iterator_put(struct traceeval_iterator *iter);
+int traceeval_iterator_sort(struct traceeval_iterator *iter, const char *sort_field,
+			    int level, bool ascending);
+int traceeval_iterator_next(struct traceeval_iterator *iter,
+			    const union traceeval_data **keys);
+
 #endif /* __LIBTRACEEVAL_HIST_H__ */
diff --git a/src/eval-local.h b/src/eval-local.h
index ed2e8abc9b63..5c3918f17cc1 100644
--- a/src/eval-local.h
+++ b/src/eval-local.h
@@ -70,6 +70,17 @@ struct traceeval {
 	size_t				nr_val_types;
 };
 
+struct traceeval_iterator {
+	struct traceeval		*teval;
+	struct entry			**entries;
+	struct traceeval_type		**sort;
+	bool				*direction;
+	size_t				nr_entries;
+	size_t				nr_sort;
+	size_t				next;
+	bool				needs_sort;
+};
+
 extern struct hash_table *hash_alloc(void);
 extern void hash_free(struct hash_table *hash);
 extern void hash_add(struct hash_table *hash, struct hash_item *item, unsigned key);
diff --git a/src/histograms.c b/src/histograms.c
index 592e9c5f78a4..c4ff632b4f87 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -37,7 +37,7 @@ static void print_err(const char *fmt, ...)
  */
 static int compare_traceeval_data(struct traceeval *teval,
 				  struct traceeval_type *type,
-				  union traceeval_data *orig,
+				  const union traceeval_data *orig,
 				  const union traceeval_data *copy)
 {
 	int i;
@@ -903,3 +903,259 @@ int traceeval_insert(struct traceeval *teval,
 	else
 		return update_entry(teval, entry, vals);
 }
+
+/**
+ * traceeval_iterator_put - release a given iterator
+ * @iter: The iterartor to release
+ *
+ * Frees the resources of an @iter that was created by
+ * traceeval_iterator_get().
+ */
+void traceeval_iterator_put(struct traceeval_iterator *iter)
+{
+	if (!iter)
+		return;
+
+	free(iter->direction);
+	free(iter->entries);
+	free(iter->sort);
+	free(iter);
+}
+
+/**
+ * traceeval_iterator_get - get a handle to iterate over a given traceeval
+ * @teval: The traceeval handle to iterate over
+ *
+ * Returns a handle to iterate over the given @teval. Must be freed with
+ * traceeval_iterator_put(). It can be used with traceeval_iterator_next()
+ * to retrieve the keys of the next entry in @teval.
+ *
+ * Use traceeval_iterator_sort() to specify the order of the entries
+ * returned by traceeval_iterator_next().
+ *
+ * Returns an allocated iterator on success, and NULL on failure.
+ */
+struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval)
+{
+	struct traceeval_iterator *iter;
+	struct hash_table *hist = teval->hist;
+	struct hash_iter *hiter;
+	struct hash_item *item;
+	int i;
+
+	iter = calloc(1, sizeof(*iter));
+	if (!iter)
+		return NULL;
+
+	iter->teval = teval;
+	iter->nr_entries = hash_nr_items(hist);
+	iter->entries = calloc(iter->nr_entries, sizeof(*iter->entries));
+	if (!iter->entries) {
+		free(iter);
+		return NULL;
+	}
+
+	for (i = 0, hiter = hash_iter_start(hist); (item = hash_iter_next(hiter)); i++) {
+		struct entry *entry = container_of(item, struct entry, hash);
+
+		iter->entries[i] = entry;
+	}
+
+	/* Loop must match entries */
+	if (i != iter->nr_entries) {
+		traceeval_iterator_put(iter);
+		return NULL;
+	}
+
+	return iter;
+}
+
+static struct traceeval_type *find_sort_type(struct traceeval *teval,
+					     const char *name)
+{
+	struct traceeval_type *type;
+	int i;
+
+	/* Check values first, and then keys */
+	for (i = 0; i < teval->nr_val_types; i++) {
+		type = &teval->val_types[i];
+
+		if (strcmp(type->name, name) == 0)
+			return type;
+	}
+
+	for (i = 0; i < teval->nr_key_types; i++) {
+		type = &teval->key_types[i];
+
+		if (strcmp(type->name, name) == 0)
+			return type;
+	}
+
+	return NULL;
+}
+
+/**
+ * traceeval_iterator_sort - sort the entries that an iterator will return
+ * @iter: The iterator to specify the sort order of the entries
+ * @sort_field: The name of the key or value to sort with.
+ * @level: The level of sorting (0 for first order, 1 for second, ...)
+ * @ascending: If the sort should go forward or backward.
+ *
+ * The iterator has a list of entries to produce with traceeval_iterator_next().
+ * This function specifies what the order of the output of that function will
+ * be. Note, whenever this function is called, it resets the @iter so that
+ * the traceveal_iterator_next() will start from the beginning again.
+ *
+ * In other words, be very careful to ever call this function in a middle
+ * of a loop that is using traceeval_iterator_next(), otherwise you may end
+ * up in an infinite loop!
+ *
+ * The @level specifies the level of sorting. That is, for @level = 0,
+ * it will decide the main sorting of the @iter. For @level = 1, it will
+ * be the tie breaker for two entries that are equal for the @level = 0
+ * sort. @level = 2, will be the tie breaker for @level = 1, and so on.
+ *
+ * Note, if traceeval_iterator_next() is called, and there's a missing @level,
+ * it will fail. That is, if this function is called once with @level = 0 and
+ * againg with @level = 2, but never with @level = 1, the call to
+ * traceeval_iterator_next() will fail.
+ *
+ * If this function is called multiple times with the same @level, then the
+ * last call will define the what that @level will do.
+ *
+ * The @ascending will determine if "smaller" items go first if true, and
+ * "larger" items go first if false.
+ *
+ * Return 0 on success and -1 on failure.
+ */
+int traceeval_iterator_sort(struct traceeval_iterator *iter, const char *sort_field,
+			    int level, bool ascending)
+{
+	bool *direction = iter->direction;
+	struct traceeval_type **sort = iter->sort;
+	struct traceeval_type *type;
+	int num_levels = level + 1;
+
+	type = find_sort_type(iter->teval, sort_field);
+	if (!type)
+		return -1;
+
+	/* pointer and dynamic types must have a cmp function */
+	switch (type->type) {
+	case TRACEEVAL_TYPE_POINTER:
+	case TRACEEVAL_TYPE_DYNAMIC:
+		if (!type->cmp)
+			return -1;
+		break;
+	default:
+		break;
+	}
+
+	if (num_levels > iter->nr_sort) {
+		sort = realloc(sort, sizeof(*sort) * num_levels);
+		if (!sort)
+			return -1;
+
+		iter->sort = sort;
+
+		direction = realloc(direction, sizeof(*direction) * num_levels);
+		if (!direction)
+			return -1;
+
+		iter->direction = direction;
+
+		/* Make sure the newly allocated contain NULL */
+		for (int i = iter->nr_sort; i < num_levels; i++)
+			sort[i] = NULL;
+
+		iter->nr_sort = level + 1;
+	}
+
+	sort[level] = type;
+	direction[level] = ascending;
+	iter->needs_sort = true;
+	return 0;
+}
+
+static int iter_cmp(const void *A, const void *B, void *data)
+{
+	struct traceeval_iterator *iter = data;
+	struct traceeval *teval = iter->teval;
+	const struct entry *a = *((const struct entry **)A);
+	const struct entry *b = *((const struct entry **)B);
+	int ret;
+
+	for (int i = 0; i < iter->nr_sort; i++) {
+		struct traceeval_type *type;
+		union traceeval_data *dataA;
+		union traceeval_data *dataB;
+
+		type = iter->sort[i];
+
+		if (type->flags & TRACEEVAL_FL_KEY) {
+			dataA = &a->keys[type->index];
+			dataB = &b->keys[type->index];
+		} else {
+			dataA = &a->vals[type->index];
+			dataB = &b->vals[type->index];
+		}
+
+		ret = compare_traceeval_data(teval, type, dataA, dataB);
+
+		if (ret)
+			return iter->direction[i] ? ret : ret * -1;
+	}
+
+	return 0;
+}
+
+static int sort_iter(struct traceeval_iterator *iter)
+{
+	int i;
+
+	/* Make sure all levels are filled */
+	for (i = 0; i < iter->nr_sort; i++) {
+		if (!iter->sort[i])
+			return -1;
+	}
+
+	qsort_r(iter->entries, iter->nr_entries, sizeof(*iter->entries),
+		iter_cmp, iter);
+
+	iter->needs_sort = false;
+	iter->next = 0;
+
+	return 0;
+}
+
+/**
+ * traceeval_iterator_next - retrieve the next entry from an iterator
+ * @iter: The iterator to retrieve the next entry from
+ * @keys: The returned keys of the next entry (if exists)
+ *
+ * This returns the keys for the next entry in the traceeval being
+ * iterated over by @iter. If there are no more entries, 0 is returned
+ * and @keys are untouched.
+ *
+ * Returns 1 if another entry is returned, or 0 if not (or negative on error)
+ */
+int traceeval_iterator_next(struct traceeval_iterator *iter,
+			    const union traceeval_data **keys)
+{
+	struct entry *entry;
+	int ret;
+
+	if (iter->needs_sort) {
+		ret = sort_iter(iter);
+		if (ret < 0)
+			return ret;
+		iter->next = 0;
+	}
+
+	if (iter->next >= iter->nr_entries)
+		return 0;
+
+	entry = iter->entries[iter->next++];
+	*keys = entry->keys;
+	return 1;
+}
-- 
2.40.1

[PATCH v4 14/20] libtraceeval histogram: Add data copy callback

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Add a callback "copy" to the type that gets called when a copy is done.
This is can be used to copy dynamic types. Otherwise the old one is just
going to be released.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h | 5 +++++
 src/histograms.c         | 3 +++
 2 files changed, 8 insertions(+)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index e8a7981ac2c0..a87f39afc050 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -82,6 +82,10 @@ typedef int (*traceeval_data_hash_fn)(struct traceeval *teval,
 				      const struct traceeval_type *type,
 				      const union traceeval_data *data);
 
+typedef int (*traceeval_data_copy_fn)(const struct traceeval_type *type,
+				      union traceeval_data *dst,
+				      const union traceeval_data *src);
+
 /*
  * struct traceeval_type - Describes the type of a traceevent_data instance
  * @type: The enum type that describes the traceeval_data
@@ -126,6 +130,7 @@ struct traceeval_type {
 	size_t				id;
 	traceeval_data_release_fn	release;
 	traceeval_data_cmp_fn		cmp;
+	traceeval_data_copy_fn		copy;
 	traceeval_data_hash_fn		hash;
 };
 
diff --git a/src/histograms.c b/src/histograms.c
index c4ff632b4f87..08d711239284 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -511,6 +511,9 @@ static int copy_traceeval_data(struct traceeval_type *type,
 {
 	unsigned long long val;
 
+	if (type->copy)
+		return type->copy(type, dst, src);
+
 	*dst = *src;
 
 	switch(type->type) {
-- 
2.40.1

[PATCH v4 15/20] libtraceeval histogram: Do the release on updates

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

If no copy() function exists for a type but a release() function does,
then do the release on the old copy.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 src/histograms.c | 6 +++++-
 1 file changed, 5 insertions(+), 1 deletion(-)

diff --git a/src/histograms.c b/src/histograms.c
index 08d711239284..185480cabad2 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -595,12 +595,16 @@ static int copy_traceeval_data(struct traceeval_type *type,
 /*
  * Free @data with respect to @size and @type.
  *
- * Does not call the release callback on the data.
+ * Does not call the release() callback if a copy() exists.
  */
 static void data_release(size_t size, union traceeval_data **data,
 				struct traceeval_type *type)
 {
 	for (size_t i = 0; i < size; i++) {
+		/* A copy should handle releases */
+		if (type[i].release && !type[i].copy)
+			type[i].release(&type[i], &(*data)[i]);
+
 		if (type[i].type == TRACEEVAL_TYPE_STRING)
 			free((*data)[i].string);
 	}
-- 
2.40.1

[PATCH v4 16/20] libtraceeval histogram: Use stack for old copy in update

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

In the update, instead of using the heap, use the stack to save the old
values. This should save time where it does not need to allocate and then
free the value list to do an update.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 src/histograms.c | 51 ++++++++++++++++++++++++++++++++++++------------
 1 file changed, 38 insertions(+), 13 deletions(-)

diff --git a/src/histograms.c b/src/histograms.c
index 185480cabad2..e6a15a25bba0 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -597,17 +597,23 @@ static int copy_traceeval_data(struct traceeval_type *type,
  *
  * Does not call the release() callback if a copy() exists.
  */
-static void data_release(size_t size, union traceeval_data **data,
-				struct traceeval_type *type)
+static void data_release(size_t size, union traceeval_data *data,
+			 struct traceeval_type *type)
 {
 	for (size_t i = 0; i < size; i++) {
 		/* A copy should handle releases */
 		if (type[i].release && !type[i].copy)
-			type[i].release(&type[i], &(*data)[i]);
+			type[i].release(&type[i], &data[i]);
 
 		if (type[i].type == TRACEEVAL_TYPE_STRING)
-			free((*data)[i].string);
+			free(data[i].string);
 	}
+}
+
+static void data_release_and_free(size_t size, union traceeval_data **data,
+				struct traceeval_type *type)
+{
+	data_release(size, *data, type);
 	free(*data);
 	*data = NULL;
 }
@@ -641,7 +647,7 @@ static int dup_traceeval_data_set(size_t size, struct traceeval_type *type,
 	return 1;
 
 fail:
-	data_release(i, copy, type);
+	data_release_and_free(i, copy, type);
 	return -1;
 }
 
@@ -700,7 +706,7 @@ void traceeval_results_release(struct traceeval *teval,
 		return;
 	}
 
-	data_release(teval->nr_val_types, &results, teval->val_types);
+	data_release_and_free(teval->nr_val_types, &results, teval->val_types);
 }
 
 static struct entry *create_hist_entry(struct traceeval *teval,
@@ -756,7 +762,7 @@ static int create_entry(struct traceeval *teval,
 	return 0;
 
 fail:
-	data_release(teval->nr_key_types, &new_keys, teval->key_types);
+	data_release_and_free(teval->nr_key_types, &new_keys, teval->key_types);
 
 fail_stats:
 	free(entry->val_stats);
@@ -776,15 +782,34 @@ fail_entry:
 static int update_entry(struct traceeval *teval, struct entry *entry,
 			const union traceeval_data *vals)
 {
-	union traceeval_data *new_vals;
+	struct traceeval_stat *stats = entry->val_stats;
+	struct traceeval_type *types = teval->val_types;
+	union traceeval_data *copy = entry->vals;
+	union traceeval_data old[teval->nr_val_types];
+	size_t size = teval->nr_val_types;
+	size_t i;
 
-	if (dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
-				   entry->val_stats, vals, &new_vals) == -1)
-		return -1;
+	if (!size)
+		return 0;
 
-	clean_data_set(entry->vals, teval->val_types, teval->nr_val_types);
-	entry->vals = new_vals;
+	for (i = 0; i < size; i++) {
+		old[i] = copy[i];
+
+		if (copy_traceeval_data(types + i, stats + i,
+					copy + i, vals + i))
+			goto fail;
+	}
+	data_release(size, old, types);
 	return 0;
+ fail:
+	/* Free the new values that were added */
+	data_release(i, copy, types);
+	/* Put back the old values */
+	for (i--; i >= 0; i--) {
+		copy_traceeval_data(types + i, NULL,
+				    copy + i, old + i);
+	}
+	return -1;
 }
 
 struct traceeval_stat *traceeval_stat(struct traceeval *teval,
-- 
2.40.1

[PATCH v4 17/20] libtraceeval histogram: Add traceeval_iterator_sort_custom()

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Add an iterator where the application can supply the sort algorithm where
it gets the teval descriptor along with the keys and values of both of the
entries to compare against. Also, allow it to submit its own data to the
compare function:

int traceeval_iterator_sort_custom(struct traceeval_iterator *iter,
				   traceeval_cmp_fn sort_fn, void *data);

with

typedef int (*traceeval_cmp_fn)(struct traceeval *teval,
				const union traceeval_data *Akeys,
				const union traceeval_data *Avals,
				const union traceeval_data *Bkeys,
				const union traceeval_data *Bvals,
				void *data);

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h |  9 +++++++++
 src/histograms.c         | 35 +++++++++++++++++++++++++++++++++++
 2 files changed, 44 insertions(+)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index a87f39afc050..490cfd2a51a2 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -86,6 +86,13 @@ typedef int (*traceeval_data_copy_fn)(const struct traceeval_type *type,
 				      union traceeval_data *dst,
 				      const union traceeval_data *src);
 
+typedef int (*traceeval_cmp_fn)(struct traceeval *teval,
+				const union traceeval_data *Akeys,
+				const union traceeval_data *Avals,
+				const union traceeval_data *Bkeys,
+				const union traceeval_data *Bvals,
+				void *data);
+
 /*
  * struct traceeval_type - Describes the type of a traceevent_data instance
  * @type: The enum type that describes the traceeval_data
@@ -172,6 +179,8 @@ struct traceeval_iterator *traceeval_iterator_get(struct traceeval *teval);
 void traceeval_iterator_put(struct traceeval_iterator *iter);
 int traceeval_iterator_sort(struct traceeval_iterator *iter, const char *sort_field,
 			    int level, bool ascending);
+int traceeval_iterator_sort_custom(struct traceeval_iterator *iter,
+				   traceeval_cmp_fn sort_fn, void *data);
 int traceeval_iterator_next(struct traceeval_iterator *iter,
 			    const union traceeval_data **keys);
 
diff --git a/src/histograms.c b/src/histograms.c
index e6a15a25bba0..f9c52684b7dc 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -1160,6 +1160,41 @@ static int sort_iter(struct traceeval_iterator *iter)
 	return 0;
 }
 
+struct iter_custom_data {
+	struct traceeval_iterator *iter;
+	traceeval_cmp_fn sort_fn;
+	void *data;
+};
+
+static int iter_custom_cmp(const void *A, const void *B, void *data)
+{
+	struct iter_custom_data *cust_data = data;
+	struct traceeval_iterator *iter = cust_data->iter;
+	struct traceeval *teval = iter->teval;
+	const struct entry *a = *((const struct entry **)A);
+	const struct entry *b = *((const struct entry **)B);
+
+	return cust_data->sort_fn(teval, a->keys, a->vals, b->keys, b->vals,
+				  cust_data->data);
+}
+
+int traceeval_iterator_sort_custom(struct traceeval_iterator *iter,
+				   traceeval_cmp_fn sort_fn, void *data)
+{
+	struct iter_custom_data cust_data = {
+		.iter = iter,
+		.sort_fn = sort_fn,
+		.data = data
+	};
+
+	qsort_r(iter->entries, iter->nr_entries, sizeof(*iter->entries),
+		iter_custom_cmp, &cust_data);
+
+	iter->needs_sort = false;
+	iter->next = 0;
+	return 0;
+}
+
 /**
  * traceeval_iterator_next - retrieve the next entry from an iterator
  * @iter: The iterator to retrieve the next entry from
-- 
2.40.1

[PATCH v4 18/20] libtraceeval histogram: Have traceeval_query() just give the pointer to results

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Instead of wasting allocation to return the results for queries,
especially since the query is likely not to modify the results, just give
a direct pointer to the entry->vals.

Mark it as const so (hopefully) nobody modifies it.

We still require the traceeval_results_release() to be called on it, as we
may in the future add a ref count to it and perhaps do a copy-on-write if
an update happens while something still has a hold on it.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h |  4 ++--
 src/histograms.c         | 10 ++++------
 2 files changed, 6 insertions(+), 8 deletions(-)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 490cfd2a51a2..4e0e9c057045 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -161,10 +161,10 @@ int traceeval_insert(struct traceeval *teval,
 		     const union traceeval_data *vals);
 
 int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
-		    union traceeval_data **results);
+		    const union traceeval_data **results);
 
 void traceeval_results_release(struct traceeval *teval,
-			       union traceeval_data *results);
+			       const union traceeval_data *results);
 
 struct traceeval_stat *traceeval_stat(struct traceeval *teval,
 				      const union traceeval_data *keys,
diff --git a/src/histograms.c b/src/histograms.c
index f9c52684b7dc..c008694b41b7 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -670,7 +670,7 @@ fail:
  * Returns 1 if found, 0 if not found, and -1 on error.
  */
 int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
-		    union traceeval_data **results)
+		    const union traceeval_data **results)
 {
 	struct entry *entry;
 	int check;
@@ -682,8 +682,8 @@ int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 	if ((check = get_entry(teval, keys, &entry)) < 1)
 		return check;
 
-	return dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
-				      NULL, entry->vals, results);
+	*results = entry->vals;
+	return 1;
 }
 
 /*
@@ -698,15 +698,13 @@ int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
  * allow traceeval to clean up its references.
  */
 void traceeval_results_release(struct traceeval *teval,
-			       union traceeval_data *results)
+			       const union traceeval_data *results)
 {
 	if (!teval || !results) {
 		if (!teval)
 			print_err("Results to be freed without accompanied traceeval instance!");
 		return;
 	}
-
-	data_release_and_free(teval->nr_val_types, &results, teval->val_types);
 }
 
 static struct entry *create_hist_entry(struct traceeval *teval,
-- 
2.40.1

[PATCH v4 19/20] libtraceeval samples: Update task-eval to use the histogram logic

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Convert task-eval over to the new API.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 samples/Makefile    |   2 +-
 samples/task-eval.c | 743 +++++++++++++++++++++++++-------------------
 2 files changed, 426 insertions(+), 319 deletions(-)

diff --git a/samples/Makefile b/samples/Makefile
index 012301ec5542..eb14411189f6 100644
--- a/samples/Makefile
+++ b/samples/Makefile
@@ -19,7 +19,7 @@ $(sdir):
 
 $(TARGETS): $(sdir) $(LIBTRACEEVAL_STATIC)
 
-$(sdir)/%: $(bdir)/%.o
+$(sdir)/%: $(LIBTRACEEVAL_STATIC) $(bdir)/%.o
 	$(call do_sample_build,$@,$<)
 
 $(bdir)/%.o: $(bdir)/%.c
diff --git a/samples/task-eval.c b/samples/task-eval.c
index 9214777ee2e1..66d0c40dc0c8 100644
--- a/samples/task-eval.c
+++ b/samples/task-eval.c
@@ -5,7 +5,7 @@
 #include <getopt.h>
 #include <errno.h>
 #include <trace-cmd.h>
-#include <traceeval.h>
+#include <traceeval-hist.h>
 
 static char *argv0;
 
@@ -80,6 +80,79 @@ void pdie(const char *fmt, ...)
 	va_end(ap);
 }
 
+static struct traceeval_type cpu_keys[] = {
+	{
+		.type = TRACEEVAL_TYPE_NUMBER,
+		.name = "CPU",
+	},
+	{
+		.type = TRACEEVAL_TYPE_NUMBER,
+		.name = "Schedule state",
+	},
+	{
+		.type = TRACEEVAL_TYPE_NONE
+	}
+};
+
+static struct traceeval_type process_keys[] = {
+	{
+		.type = TRACEEVAL_TYPE_STRING,
+		.name = "COMM"
+	},
+	{
+		.type = TRACEEVAL_TYPE_NUMBER,
+		.name = "Schedule state"
+	},
+	{
+		.type	= TRACEEVAL_TYPE_NONE,
+	}
+};
+
+static struct traceeval_type process_data_vals[] = {
+	{
+		.type = TRACEEVAL_TYPE_POINTER,
+		.name = "data",
+	},
+	{
+		.type = TRACEEVAL_TYPE_NONE
+	}
+};
+
+static struct traceeval_type thread_keys[] = {
+	{
+		.type = TRACEEVAL_TYPE_NUMBER,
+		.name = "TID",
+	},
+	{
+		.type = TRACEEVAL_TYPE_NUMBER,
+		.name = "Schedule state",
+	},
+	{
+		.type = TRACEEVAL_TYPE_NONE,
+	}
+};
+
+static struct traceeval_type timestamp_vals[] = {
+	{
+		.type = TRACEEVAL_TYPE_NUMBER_64,
+		.name = "Timestamp",
+		.flags = TRACEEVAL_FL_TIMESTAMP,
+	},
+	{
+		.type = TRACEEVAL_TYPE_NONE
+	}
+};
+
+static struct traceeval_type delta_vals[] = {
+	{
+		.type	= TRACEEVAL_TYPE_NUMBER_64,
+		.name	= "delta",
+	},
+	{
+		.type	= TRACEEVAL_TYPE_NONE,
+	},
+};
+
 enum sched_state {
 	RUNNING,
 	BLOCKED,
@@ -89,16 +162,22 @@ enum sched_state {
 	OTHER
 };
 
+struct teval_pair {
+	struct traceeval	*start;
+	struct traceeval	*stop;
+};
+
 struct process_data {
-	struct traceeval	*teval_cpus;
-	struct traceeval	*teval_threads;
+	struct teval_pair	teval_cpus;
+	struct teval_pair	teval_threads;
 	char			*comm;
 	int			state;
 };
 
 struct task_data {
-	struct traceeval	*teval_cpus;
-	struct traceeval	*teval_processes;
+	struct teval_pair	teval_cpus;
+	struct teval_pair	teval_processes;
+	struct traceeval	*teval_processes_data;
 	char			*comm;
 };
 
@@ -111,30 +190,52 @@ static void update_process(struct task_data *tdata, const char *comm,
 			   enum sched_state state, enum command cmd,
 			   unsigned long long ts)
 {
-	struct traceeval_key keys[] = {
+	union traceeval_data keys[] = {
 		{
-			.type = TRACEEVAL_TYPE_STRING,
-			.string = comm,
+			.cstring	= comm,
 		},
 		{
-			.type = TRACEEVAL_TYPE_NUMBER,
-			.number = state,
-		}
+			.number		= state,
+		},
 	};
+	union traceeval_data vals[] = {
+		{
+			.number_64	= ts,
+		},
+	};
+	union traceeval_data new_vals[1] = { };
+	const union traceeval_data *results;
 	int ret;
 
 	switch (cmd) {
 	case START:
-		ret = traceeval_n_start(tdata->teval_processes, keys, ts);
+		ret = traceeval_insert(tdata->teval_processes.start, keys, vals);
 		if (ret < 0)
 			pdie("Could not start process");
 		return;
 	case STOP:
-		ret = traceeval_n_stop(tdata->teval_processes, keys, ts);
+		ret = traceeval_query(tdata->teval_processes.start, keys, &results);
+		if (ret < 0)
+			pdie("Could not query start process");
+		if (ret == 0)
+			return;
+		if (!results[0].number_64)
+			break;
+
+		new_vals[0].number_64 = ts - results[0].number_64;
+
+		ret = traceeval_insert(tdata->teval_processes.stop, keys, new_vals);
 		if (ret < 0)
 			pdie("Could not stop process");
-		return;
+
+		/* Reset the start */
+		new_vals[0].number_64 = 0;
+		ret = traceeval_insert(tdata->teval_processes.start, keys, new_vals);
+		if (ret < 0)
+			pdie("Could not start CPU");
+		break;
 	}
+	traceeval_results_release(tdata->teval_processes.start, results);
 }
 
 static void start_process(struct task_data *tdata, const char *comm,
@@ -152,105 +253,172 @@ static void stop_process(struct task_data *tdata, const char *comm,
 static struct process_data *
 get_process_data(struct task_data *tdata, const char *comm)
 {
-	struct traceeval_key keys[] = {
+	union traceeval_data keys[] = {
 		{
-			.type = TRACEEVAL_TYPE_STRING,
-			.string = comm,
+			.cstring = comm,
 		},
 		{
-			.type = TRACEEVAL_TYPE_NUMBER,
 			.number = RUNNING,
 		}
 	};
+	const union traceeval_data *results;
+	void *data;
+	int ret;
+
+	ret = traceeval_query(tdata->teval_processes_data, keys, &results);
+	if (ret < 0)
+		pdie("Could not query process data");
+	if (ret == 0)
+		return NULL;
 
-	return traceeval_n_get_private(tdata->teval_processes, keys);
+	data = results[0].pointer;
+	traceeval_results_release(tdata->teval_processes_data, results);
+	return data;
 }
 
 void set_process_data(struct task_data *tdata, const char *comm, void *data)
 {
-	struct traceeval_key keys[] = {
+	union traceeval_data keys[] = {
 		{
-			.type = TRACEEVAL_TYPE_STRING,
-			.string = comm,
+			.cstring = comm,
 		},
 		{
-			.type = TRACEEVAL_TYPE_NUMBER,
 			.number = RUNNING,
 		}
 	};
+	union traceeval_data new_vals[1] = { };
+	const union traceeval_data *results;
 	int ret;
 
-	ret = traceeval_n_set_private(tdata->teval_processes, keys, data);
+	ret = traceeval_query(tdata->teval_processes_data, keys, &results);
+	if (ret > 0)
+		goto out; /* It already exists ? */
+	if (ret < 0)
+		pdie("Could not query process data");
+
+	new_vals[0].pointer = data;
+	ret = traceeval_insert(tdata->teval_processes_data, keys, new_vals);
 	if (ret < 0)
 		pdie("Failed to set process data");
+
+ out:
+	traceeval_results_release(tdata->teval_processes_data, results);
 }
 
-static void update_cpu(struct traceeval *teval, int cpu,
+static void update_cpu(struct teval_pair *teval_pair, int cpu,
 		       enum sched_state state, enum command cmd,
 		       unsigned long long ts)
 {
-	struct traceeval_key keys[] = {
+	const union traceeval_data *results;
+	union traceeval_data keys[] = {
 		{
-			.type = TRACEEVAL_TYPE_NUMBER,
 			.number = cpu,
 		},
 		{
-			.type = TRACEEVAL_TYPE_NUMBER,
 			.number = state,
 		}
 	};
+	union traceeval_data vals[] = {
+		{
+			.number_64	= ts,
+		},
+	};
+	union traceeval_data new_vals[1] = { };
 	int ret;
 
 	switch (cmd) {
 	case START:
-		ret = traceeval_n_continue(teval, keys, ts);
+		/* Only set if the timestamp is zero (or doesn't exist) */
+		ret = traceeval_query(teval_pair->start, keys, &results);
+		if (ret > 0) {
+			if (results[0].number_64)
+				break;
+		}
+		if (ret < 0)
+			pdie("Could not query cpu start data");
+		ret = traceeval_insert(teval_pair->start, keys, vals);
 		if (ret < 0)
 			pdie("Could not start CPU");
-		return;
+		break;
 	case STOP:
-		ret = traceeval_n_stop(teval, keys, ts);
+		ret = traceeval_query(teval_pair->start, keys, &results);
+		if (ret < 0)
+			pdie("Could not query cpu stop data");
+		if (ret == 0)
+			return;
+
+		if (!results[0].number_64)
+			break;
+
+		new_vals[0].number_64 = ts - results[0].number_64;
+
+		ret = traceeval_insert(teval_pair->stop, keys, new_vals);
 		if (ret < 0)
 			pdie("Could not stop CPU");
-		return;
+
+		/* Reset the start */
+		new_vals[0].number_64 = 0;
+		ret = traceeval_insert(teval_pair->start, keys, new_vals);
+		if (ret < 0)
+			pdie("Could not start CPU");
+
+		break;
+		default:
+			return;
 	}
+	traceeval_results_release(teval_pair->start, results);
 }
 
-static void start_cpu(struct traceeval *teval, int cpu,
+static void start_cpu(struct teval_pair *teval_pair, int cpu,
 		      enum sched_state state,  unsigned long long ts)
 {
-	update_cpu(teval, cpu, state, START, ts);
+	update_cpu(teval_pair, cpu, state, START, ts);
 }
 
-static void stop_cpu(struct traceeval *teval, int cpu,
+static void stop_cpu(struct teval_pair *teval_pair, int cpu,
 		     enum sched_state state, unsigned long long ts)
 {
-	update_cpu(teval, cpu, state, STOP, ts);
+	update_cpu(teval_pair, cpu, state, STOP, ts);
 }
 
 static void update_thread(struct process_data *pdata, int tid,
 			  enum sched_state state, enum command cmd,
 			  unsigned long long ts)
 {
-	struct traceeval_key keys[] = {
+	const union traceeval_data *results;
+	union traceeval_data keys[] = {
 		{
-			.type = TRACEEVAL_TYPE_NUMBER,
 			.number = tid,
 		},
 		{
-			.type = TRACEEVAL_TYPE_NUMBER,
 			.number = state,
 		}
 	};
+	union traceeval_data vals[] = {
+		{
+			.number_64	= ts,
+		},
+	};
+	union traceeval_data new_vals[1] = { };
 	int ret;
 
 	switch (cmd) {
 	case START:
-		ret = traceeval_n_start(pdata->teval_threads, keys, ts);
+		ret = traceeval_insert(pdata->teval_threads.start, keys, vals);
 		if (ret < 0)
 			pdie("Could not start thread");
 		return;
 	case STOP:
-		ret = traceeval_n_stop(pdata->teval_threads, keys, ts);
+		ret = traceeval_query(pdata->teval_threads.start, keys, &results);
+		if (ret < 0)
+			pdie("Could not query thread start");
+		if (ret == 0)
+			return;
+
+		new_vals[0].number_64 = ts - results[0].number_64;
+
+		ret = traceeval_insert(pdata->teval_threads.stop, keys, new_vals);
+		traceeval_results_release(pdata->teval_threads.start, results);
 		if (ret < 0)
 			pdie("Could not stop thread");
 		return;
@@ -283,34 +451,21 @@ static struct tep_format_field *get_field(struct tep_event *event, const char *n
 
 static void init_process_data(struct process_data *pdata)
 {
-	struct traceeval_key_info cpu_info[] = {
-		{
-			.type = TRACEEVAL_TYPE_NUMBER,
-			.name = "CPU",
-		},
-		{
-			.type = TRACEEVAL_TYPE_NUMBER,
-			.name = "Schedule state",
-		}
-	};
-	struct traceeval_key_info thread_info[] = {
-		{
-			.type = TRACEEVAL_TYPE_NUMBER,
-			.name = "TID",
-		},
-		{
-			.type = TRACEEVAL_TYPE_NUMBER,
-			.name = "Schedule state",
-		}
-	};
 
-	pdata->teval_cpus = traceeval_2_alloc("CPUs", cpu_info);
-	if (!pdata->teval_cpus)
-		pdie("Creating trace eval");
+	pdata->teval_cpus.start = traceeval_init(cpu_keys, timestamp_vals);
+	if (!pdata->teval_cpus.start)
+		pdie("Creating trace eval cpus start");
+	pdata->teval_cpus.stop = traceeval_init(cpu_keys, delta_vals);
+	if (!pdata->teval_cpus.stop)
+		pdie("Creating trace eval cpus");
 
-	pdata->teval_threads = traceeval_2_alloc("Threads", thread_info);
-	if (!pdata->teval_threads)
-		pdie("Creating trace eval");
+	pdata->teval_threads.start = traceeval_init(thread_keys, timestamp_vals);
+	if (!pdata->teval_threads.start)
+		pdie("Creating trace eval threads start");
+
+	pdata->teval_threads.stop = traceeval_init(thread_keys, delta_vals);
+	if (!pdata->teval_threads.stop)
+		pdie("Creating trace eval threads");
 }
 
 static struct process_data *alloc_pdata(struct task_data *tdata, const char *comm)
@@ -344,7 +499,7 @@ static void sched_out(struct task_data *tdata, const char *comm,
 	pid = val;
 	if (!pid) {
 		/* Record the runtime for the process CPUs */
-		stop_cpu(tdata->teval_cpus, record->cpu, IDLE, record->ts);
+		stop_cpu(&tdata->teval_cpus, record->cpu, IDLE, record->ts);
 		return;
 	}
 
@@ -381,10 +536,10 @@ static void sched_out(struct task_data *tdata, const char *comm,
 	start_thread(pdata, pid, pdata->state, record->ts);
 
 	/* Record the runtime for the process CPUs */
-	stop_cpu(pdata->teval_cpus, record->cpu, RUNNING, record->ts);
+	stop_cpu(&pdata->teval_cpus, record->cpu, RUNNING, record->ts);
 
 	/* Record the runtime for the all CPUs */
-	stop_cpu(tdata->teval_cpus, record->cpu, RUNNING, record->ts);
+	stop_cpu(&tdata->teval_cpus, record->cpu, RUNNING, record->ts);
 }
 
 static void sched_in(struct task_data *tdata, const char *comm,
@@ -405,7 +560,7 @@ static void sched_in(struct task_data *tdata, const char *comm,
 	/* Ignore the idle task */
 	if (!pid) {
 		/* Record the runtime for the process CPUs */
-		start_cpu(tdata->teval_cpus, record->cpu, IDLE, record->ts);
+		start_cpu(&tdata->teval_cpus, record->cpu, IDLE, record->ts);
 		return;
 	}
 
@@ -415,7 +570,7 @@ static void sched_in(struct task_data *tdata, const char *comm,
 	pdata = get_process_data(tdata, comm);
 
 	/* Start recording the running time of process CPUs */
-	start_cpu(tdata->teval_cpus, record->cpu, RUNNING, record->ts);
+	start_cpu(&tdata->teval_cpus, record->cpu, RUNNING, record->ts);
 
 	/* If there was no pdata, then this process did not go through sched out */
 	if (!pdata) {
@@ -427,7 +582,7 @@ static void sched_in(struct task_data *tdata, const char *comm,
 	start_thread(pdata, pid, RUNNING, record->ts);
 
 	/* Start recording the running time of process CPUs */
-	start_cpu(pdata->teval_cpus, record->cpu, RUNNING, record->ts);
+	start_cpu(&pdata->teval_cpus, record->cpu, RUNNING, record->ts);
 
 	/* If it was just created, there's nothing to stop */
 	if (is_new)
@@ -482,32 +637,83 @@ static void print_microseconds(int idx, unsigned long long nsecs)
 		printf("%*d.%03lld\n", idx, 0, nsecs);
 }
 
+/*
+ * Sort all the processes by the RUNNING state.
+ *  If A and B have the same COMM, then sort by state.
+ *  else
+ *    Find the RUNNNIG state for A and B
+ *    If the RUNNING state does not exist, it's considered -1
+ *  If RUNNING is equal, then sort by COMM.
+ */
+static int compare_pdata(struct traceeval *teval_data,
+				const union traceeval_data *Akeys,
+				const union traceeval_data *Avals,
+				const union traceeval_data *Bkeys,
+				const union traceeval_data *Bvals,
+				void *data)
+{
+	struct traceeval *teval = data; /* The deltas are here */
+	union traceeval_data keysA[] = {
+		{ .cstring = Akeys[0].cstring }, { .number = RUNNING } };
+	union traceeval_data keysB[] = {
+		{ .cstring = Bkeys[0].cstring }, { .number = RUNNING } };
+	struct traceeval_stat *statA;
+	struct traceeval_stat *statB;
+	unsigned long long totalA = -1;
+	unsigned long long totalB = -1;
+
+	/* First check if we are on the same task */
+	if (strcmp(Akeys[0].cstring, Bkeys[0].cstring) == 0) {
+		/* Sort decending */
+		if (Bkeys[1].number > Akeys[1].number)
+			return -1;
+		return Bkeys[1].number != Akeys[1].number;
+	}
+
+	/* Get the RUNNING values for both processes */
+	statA = traceeval_stat(teval, keysA, &delta_vals[0]);
+	if (statA)
+		totalA = traceeval_stat_total(statA);
+
+	statB = traceeval_stat(teval, keysB, &delta_vals[0]);
+	if (statB)
+		totalB = traceeval_stat_total(statB);
+
+	if (totalB < totalA)
+		return -1;
+	if (totalB > totalA)
+		return 1;
+
+	return strcmp(Bkeys[0].cstring, Akeys[0].cstring);
+}
+
 static void display_cpus(struct traceeval *teval)
 {
-	struct traceeval_key_array *karray;
-	const struct traceeval_key *ckey;
-	const struct traceeval_key *skey;
+	struct traceeval_iterator *iter = traceeval_iterator_get(teval);
+	const union traceeval_data *keys;
+	struct traceeval_stat *stat;
 	int last_cpu = -1;
-	int i, nr;
+
+	if (!iter)
+		pdie("Could not get iterator?");
 
 	printf("\n");
 
-	nr = traceeval_result_nr(teval);
-	if (!nr)
-		die("No result for CPUs\n");
+	traceeval_iterator_sort(iter, cpu_keys[0].name, 0, true);
+	traceeval_iterator_sort(iter, cpu_keys[1].name, 1, true);
 
-	for (i = 0; i < nr; i++) {
-		karray = traceeval_result_indx_key_array(teval, i);
-		if (!karray)
-			die("No cpu key for result %d\n", i);
-		ckey = traceeval_key_array_indx(karray, 0);
-		skey = traceeval_key_array_indx(karray, 1);
+	while (traceeval_iterator_next(iter, &keys) > 0) {
+		int state = keys[1].number;
+		int cpu = keys[0].number;
 
+		stat = traceeval_stat(teval, keys, &delta_vals[0]);
+		if (!stat)
+			continue; // die?
 
-		if (last_cpu != ckey->number)
-			printf("    CPU [%d]:\n", (int)ckey->number);
+		if (last_cpu != cpu)
+			printf("    CPU [%d]:\n", cpu);
 
-		switch (skey->number) {
+		switch (state) {
 		case RUNNING:
 			printf("       Running: ");
 			break;
@@ -518,256 +724,170 @@ static void display_cpus(struct traceeval *teval)
 		case PREEMPT:
 		case SLEEP:
 		case OTHER:
-			printf("         \?\?(%ld): ", skey->number);
+			printf("         \?\?(%d): ", state);
 			break;
 		}
 		printf(" time (us):");
-		print_microseconds(12, traceeval_result_indx_total(teval, i));
+		print_microseconds(12, traceeval_stat_total(stat));
 
-		last_cpu = ckey->number;
+		last_cpu = cpu;
 	}
+
+	if (last_cpu < 0)
+		die("No result for CPUs\n");
+
 }
 
-static void display_thread(struct traceeval *teval, int tid)
-{
-	struct traceeval_key keys[2] =
-		{
-			{
-				.type = TRACEEVAL_TYPE_NUMBER,
-				.number = tid,
-			},
-			{
-				.type = TRACEEVAL_TYPE_NUMBER,
-				.number = RUNNING,
-			}
-		};
-	ssize_t ret;
-
-	printf("\n    thread id: %d\n", tid);
-
-	printf("      Total run time (us):");
-	print_microseconds(14, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
-
-	keys[1].number = PREEMPT;
-	printf("      Total preempt time (us):");
-	print_microseconds(10, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
-
-	keys[1].number = BLOCKED;
-	printf("      Total blocked time (us):");
-	print_microseconds(10, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
-
-	keys[1].number = SLEEP;
-	printf("      Total sleep time (us):");
-	print_microseconds(12, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
-};
+static void display_state_times(int state, unsigned long long total)
+{
+	switch (state) {
+	case RUNNING:
+		printf("      Total run time (us):");
+		print_microseconds(14, total);
+		break;
+	case BLOCKED:
+		printf("      Total blocked time (us):");
+		print_microseconds(10, total);
+		break;
+	case PREEMPT:
+		printf("      Total preempt time (us):");
+		print_microseconds(10, total);
+		break;
+	case SLEEP:
+		printf("      Total sleep time (us):");
+		print_microseconds(12, total);
+	}
+}
 
 static void display_threads(struct traceeval *teval)
 {
-	struct traceeval_key_array *karray;
-	const struct traceeval_key *tkey;
-	struct traceeval_key keys[2];
+	struct traceeval_iterator *iter = traceeval_iterator_get(teval);
+	const union traceeval_data *keys;
+	struct traceeval_stat *stat;
 	int last_tid = -1;
-	int i, nr;
 
-	nr = traceeval_result_nr(teval);
-	if (!nr)
-		die("No result for threads\n");
+	traceeval_iterator_sort(iter, thread_keys[0].name, 0, true);
+	traceeval_iterator_sort(iter, thread_keys[1].name, 1, true);
 
-	memset(keys, 0, sizeof(keys));
-	keys[1].type = TRACEEVAL_TYPE_NUMBER;
-
-	for (i = 0; i < nr; i++) {
-		karray = traceeval_result_indx_key_array(teval, i);
-		if (!karray)
-			die("No thread key for result %d\n", i);
-		tkey = traceeval_key_array_indx(karray, 0);
-		if (!tkey)
-			die("No thread keys for result?");
-
-		/*
-		 * All the TIDS should be together in the results,
-		 * as the results are sorted by the first key, which
-		 * is the comm.
-		 */
-		if (last_tid == tkey->number)
-			continue;
+	while (traceeval_iterator_next(iter, &keys) > 0) {
+		int state = keys[1].number;
+		int tid = keys[0].number;
+
+		stat = traceeval_stat(teval, keys, &delta_vals[0]);
+		if (!stat)
+			continue; // die?
+
+		if (last_tid != keys[0].number)
+			printf("\n    thread id: %d\n", tid);
 
-		last_tid = tkey->number;
+		last_tid = tid;
 
-		display_thread(teval, tkey->number);
+		display_state_times(state, traceeval_stat_total(stat));
 	}
+
+	if (last_tid < 0)
+		die("No result for threads\n");
+
 }
 
-static void display_process(struct traceeval *teval, struct process_data *pdata,
-			    const char *comm)
+static void display_process(struct process_data *pdata)
 {
-	struct traceeval_key keys[2] =
-		{
-			{
-				.type = TRACEEVAL_TYPE_STRING,
-				.string = comm,
-			},
-			{
-				.type = TRACEEVAL_TYPE_NUMBER,
-				.number = RUNNING,
-			}
-		};
-	ssize_t ret;
-
-	printf("Task: %s\n", comm);
-
-	printf("  Total run time (us):");
-	print_microseconds(18, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
-
-	keys[1].number = PREEMPT;
-	printf("  Total preempt time (us):");
-	print_microseconds(14, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
-
-	keys[1].number = BLOCKED;
-	printf("  Total blocked time (us):");
-	print_microseconds(14, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
-
-	keys[1].number = SLEEP;
-	printf("  Total sleep time (us):");
-	print_microseconds(16, (ret = traceeval_result_keys_total(teval, keys)) < 0 ? 0 : ret);
-
-	display_threads(pdata->teval_threads);
-	display_cpus(pdata->teval_cpus);
+	display_threads(pdata->teval_threads.stop);
+	display_cpus(pdata->teval_cpus.stop);
 	printf("\n");
 }
 
-static int compare_pdata(struct traceeval *teval,
-			 const struct traceeval_key_array *A,
-			 const struct traceeval_key_array *B,
-			 void *data)
+static void display_process_stats(struct traceeval *teval,
+				  struct process_data *pdata, const char *comm)
 {
-	struct traceeval_key akeys[2];
-	struct traceeval_key bkeys[2];
-	const struct traceeval_key *akey;
-	const struct traceeval_key *bkey;
-	long long aval;
-	long long bval;
-	int ret;
-
-	/* Get the RUNNING values for this process */
-
-	akey = traceeval_key_array_indx(A, 0);
-	akeys[0] = *akey;
-	akeys[1].type = TRACEEVAL_TYPE_NUMBER;
-	akeys[1].number = RUNNING;
-
-	bkey = traceeval_key_array_indx(B, 0);
-	bkeys[0] = *bkey;
-	bkeys[1].type = TRACEEVAL_TYPE_NUMBER;
-	bkeys[1].number = RUNNING;
-
-	aval = traceeval_result_keys_total(teval, akey);
-	bval = traceeval_result_keys_total(teval, bkeys);
-
-	if (aval < 0)
-		return -1;
-	if (bval < 0)
-		return -1;
-
-	if (bval < aval)
-		return -1;
-	if (bval > aval)
-		return 1;
-
-	ret = strcmp(bkeys[0].string, akeys[0].string);
+	struct traceeval_stat *stat;
+	unsigned long long delta;
+	union traceeval_data keys[] = {
+		{
+			.cstring = comm,
+		},
+		{
+			.number = RUNNING,
+		}
+	};
 
-	/* If two different processes have the same runtime, sort by name */
-	if (ret)
-		return ret;
+	for (int i = 0; i < OTHER; i++) {
+		keys[1].number = i;
 
-	/* Same process, sort by state */
+		delta = 0;
+		stat = traceeval_stat(teval, keys, &delta_vals[0]);
+		if (stat)
+			delta = traceeval_stat_total(stat);
+		display_state_times(i, delta);
+	}
+}
 
-	akey = traceeval_key_array_indx(A, 1);
-	bkey = traceeval_key_array_indx(B, 1);
+static void display_processes(struct traceeval *teval,
+			      struct traceeval *teval_data)
+{
+	struct traceeval_iterator *iter = traceeval_iterator_get(teval_data);
+	const union traceeval_data *keys;
+	int ret;
 
-	if (bkey->number < akey->number)
-		return -1;
+	traceeval_iterator_sort_custom(iter, compare_pdata, teval);
 
-	return bkey->number > akey->number;
-}
+	while (traceeval_iterator_next(iter, &keys) > 0) {
+		const union traceeval_data *results;
+		struct process_data *pdata = NULL;
+		const char *comm = keys[0].cstring;
 
-static void display_processes(struct traceeval *teval)
-{
-	struct traceeval_key_array *karray;
-	const struct traceeval_key *tkey;
-	struct traceeval_key keys[2];
-	struct process_data *pdata;
-	const char *last_comm = NULL;
-	int i, nr;
-
-	nr = traceeval_result_nr(teval);
-	if (!nr)
-		die("No result for processes\n");
-
-	memset(keys, 0, sizeof(keys));
-	keys[1].type = TRACEEVAL_TYPE_NUMBER;
-
-	for (i = 0; i < nr; i++) {
-		karray = traceeval_result_indx_key_array(teval, i);
-		if (!karray)
-			die("No process key for result %d\n", i);
-		tkey = traceeval_key_array_indx(karray, 0);
-		if (!tkey)
-			die("No process keys for result?");
-
-		/*
-		 * All the comms should be together in the results,
-		 * as the results are sorted by the first key, which
-		 * is the comm.
-		 */
-		if (last_comm && strcmp(tkey->string, last_comm) == 0)
-			continue;
+		ret = traceeval_query(teval_data, keys, &results);
+		if (ret < 0)
+			pdie("Could not query iterator");
+		if (ret < 1)
+			continue; /* ?? */
 
-		last_comm = tkey->string;
+		pdata = results[0].pointer;
+		traceeval_results_release(teval_data, results);
 
-		keys[0] = *tkey;
-		keys[1].number = RUNNING;
+		printf("Task: %s\n", comm);
 
-		/* All processes should have a running state */
-		pdata = traceeval_n_get_private(teval, keys);
+		display_process_stats(teval, pdata, comm);
 		if (pdata)
-			display_process(teval, pdata, keys[0].string);
+			display_process(pdata);
 	}
 }
 
 static void display(struct task_data *tdata)
 {
+	struct traceeval *teval = tdata->teval_cpus.stop;
+	struct traceeval_iterator *iter = traceeval_iterator_get(teval);
+	const union traceeval_data *keys;
+	struct traceeval_stat *stat;
 	unsigned long long total_time = 0;
 	unsigned long long idle_time = 0;
-	struct traceeval_key_array *karray;
-	const struct traceeval_key *tkey;
-	unsigned long long val;
-	int i, nr;
 
-	if (tdata->comm)
-		return display_processes(tdata->teval_processes);
+	if (tdata->comm) {
+		return display_processes(tdata->teval_processes.stop,
+					 tdata->teval_processes_data);
+	}
 
 	printf("Total:\n");
 
-	nr = traceeval_result_nr(tdata->teval_cpus);
-	for (i = 0; i < nr; i++) {
-		karray = traceeval_result_indx_key_array(tdata->teval_cpus, i);
-		if (!karray)
-			die("No CPU keys for result %d\n", i);
-		tkey = traceeval_key_array_indx(karray, 1);
-		if (!tkey)
-			die("No state keys for CPU result %d?", i);
-
-		val = traceeval_result_indx_total(tdata->teval_cpus, i);
-		switch (tkey->number) {
+	if (!iter)
+		pdie("No cpus?");
+
+	while (traceeval_iterator_next(iter, &keys) > 0) {
+		int state = keys[1].number;
+
+		stat = traceeval_stat(teval, keys, &delta_vals[0]);
+		if (!stat)
+			continue;
+
+		switch (state) {
 		case RUNNING:
-			total_time += val;
+			total_time += traceeval_stat_total(stat);
 			break;
 		case IDLE:
-			idle_time += val;
+			idle_time += traceeval_stat_total(stat);
 			break;
 		default:
-			die("Invalid CPU state: %d\n", tkey->number);
+			die("Invalid CPU state: %d\n", state);
 		}
 	}
 
@@ -776,12 +896,10 @@ static void display(struct task_data *tdata)
 	printf("  Total idle time (us):");
 	print_microseconds(16, idle_time);
 
-	display_cpus(tdata->teval_cpus);
-
-	traceeval_sort_custom(tdata->teval_processes, compare_pdata, NULL);
+	display_cpus(tdata->teval_cpus.stop);
 
 	printf("\n");
-	display_processes(tdata->teval_processes);
+	display_processes(tdata->teval_processes.stop, tdata->teval_processes_data);
 }
 
 static void free_tdata(struct task_data *tdata)
@@ -792,26 +910,6 @@ int main (int argc, char **argv)
 {
 	struct tracecmd_input *handle;
 	struct task_data data;
-	struct traceeval_key_info cpu_tinfo[2] = {
-		{
-			.type = TRACEEVAL_TYPE_NUMBER,
-			.name = "CPU"
-		},
-		{
-			.type = TRACEEVAL_TYPE_NUMBER,
-			.name = "Schedule state"
-		}
-	};
-	struct traceeval_key_info process_tinfo[2] = {
-		{
-			.type = TRACEEVAL_TYPE_STRING,
-			.name = "COMM"
-		},
-		{
-			.type = TRACEEVAL_TYPE_NUMBER,
-			.name = "Schedule state"
-		}
-	};
 	int c;
 
 	memset(&data, 0, sizeof(data));
@@ -839,12 +937,21 @@ int main (int argc, char **argv)
 	if (!handle)
 		pdie("Error opening %s", argv[0]);
 
-	data.teval_processes = traceeval_2_alloc("Processes", process_tinfo);
-	if (!data.teval_processes)
+	data.teval_processes.start = traceeval_init(process_keys, timestamp_vals);
+	if (!data.teval_processes.start)
+		pdie("Creating trace eval start");
+	data.teval_processes_data = traceeval_init(process_keys, process_data_vals);
+	if (!data.teval_processes_data)
+		pdie("Creating trace eval data");
+	data.teval_processes.stop = traceeval_init(process_keys, delta_vals);
+	if (!data.teval_processes.stop)
 		pdie("Creating trace eval");
 
-	data.teval_cpus = traceeval_2_alloc("CPUs", cpu_tinfo);
-	if (!data.teval_cpus)
+	data.teval_cpus.start = traceeval_init(cpu_keys, timestamp_vals);
+	if (!data.teval_cpus.start)
+		pdie("Creating trace eval");
+	data.teval_cpus.stop = traceeval_init(cpu_keys, delta_vals);
+	if (!data.teval_cpus.stop)
 		pdie("Creating trace eval");
 
 	tracecmd_follow_event(handle, "sched", "sched_switch", switch_func, &data);
-- 
2.40.1

[PATCH v4 20/20] libtraceeval: Add traceeval_remove()

[Steven Rostedt]

From: "Steven Rostedt (Google)" <rostedt@goodmis.org>

Add a way to remove an entry that's in the traceeval. Currently there's
only ways to add entries, but there also needs to be a way to remove them
too.

Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
---
 include/traceeval-hist.h |  3 +++
 src/histograms.c         | 29 +++++++++++++++++++++++++++++
 2 files changed, 32 insertions(+)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 4e0e9c057045..0cee9bcbeb83 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -160,6 +160,9 @@ int traceeval_insert(struct traceeval *teval,
 		     const union traceeval_data *keys,
 		     const union traceeval_data *vals);
 
+int traceeval_remove(struct traceeval *teval,
+		     const union traceeval_data *keys);
+
 int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 		    const union traceeval_data **results);
 
diff --git a/src/histograms.c b/src/histograms.c
index c008694b41b7..96f0926f062c 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -934,6 +934,35 @@ int traceeval_insert(struct traceeval *teval,
 		return update_entry(teval, entry, vals);
 }
 
+/**
+ * traceeval_remove - remove an item from the traceeval descriptor
+ * @teval: The descriptor to removed from
+ * @keys: The list of keys that defines what is being removed
+ *
+ * This is the opposite of traceeval_insert(). Instead of inserting
+ * an item into the traceeval historgram, it removes it.
+ *
+ * Returns 1 if it found and removed an item,
+ *         0 if it did not find an time matching @keys
+ *        -1 if there was an error.
+ */
+int traceeval_remove(struct traceeval *teval,
+		     const union traceeval_data *keys)
+{
+	struct hash_table *hist = teval->hist;
+	struct entry *entry;
+	int check;
+
+	entry = NULL;
+	check = get_entry(teval, keys, &entry);
+
+	if (check < 1)
+		return check;
+
+	hash_remove(hist, &entry->hash);
+	return 1;
+}
+
 /**
  * traceeval_iterator_put - release a given iterator
  * @iter: The iterartor to release
-- 
2.40.1

Re: [PATCH v4 00/20] libtraceeval histogram: Updates

[Steven Rostedt]

On Thu, 17 Aug 2023 16:45:08 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> Changes since v3: https://lore.kernel.org/all/20230817013310.88582-1-rostedt@goodmis.org/

The diff between this version and the last version:

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 8e5a6451f399..0cee9bcbeb83 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -83,8 +83,8 @@ typedef int (*traceeval_data_hash_fn)(struct traceeval *teval,
 				      const union traceeval_data *data);
 
 typedef int (*traceeval_data_copy_fn)(const struct traceeval_type *type,
-				      union traceeval_data *copy,
-				      const union traceeval_data *origin);
+				      union traceeval_data *dst,
+				      const union traceeval_data *src);
 
 typedef int (*traceeval_cmp_fn)(struct traceeval *teval,
 				const union traceeval_data *Akeys,
diff --git a/src/histograms.c b/src/histograms.c
index f35d1b2e583d..96f0926f062c 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -500,65 +500,65 @@ static int get_entry(struct traceeval *teval, const union traceeval_data *keys,
 }
 
 /*
- * Copy @orig to @copy with respect to @type.
+ * Copy @src to @dst with respect to @type.
  *
  * Return 0 on success, -1 on error.
  */
 static int copy_traceeval_data(struct traceeval_type *type,
 			       struct traceeval_stat *stat,
-			       const union traceeval_data *orig,
-			       union traceeval_data *copy)
+			       union traceeval_data *dst,
+			       const union traceeval_data *src)
 {
 	unsigned long long val;
 
 	if (type->copy)
-		return type->copy(type, copy, orig);
+		return type->copy(type, dst, src);
 
-	*copy = *orig;
+	*dst = *src;
 
 	switch(type->type) {
 	case TRACEEVAL_TYPE_NUMBER:
 		if (type->flags & TRACEEVAL_FL_SIGNED)
-			val = (long long)copy->number;
+			val = (long long)dst->number;
 		else
-			val = (unsigned long long)copy->number;
+			val = (unsigned long long)dst->number;
 		break;
 
 	case TRACEEVAL_TYPE_NUMBER_64:
 		if (type->flags & TRACEEVAL_FL_SIGNED)
-			val = (long long)copy->number_64;
+			val = (long long)dst->number_64;
 		else
-			val = (unsigned long long)copy->number_64;
+			val = (unsigned long long)dst->number_64;
 		break;
 
 	case TRACEEVAL_TYPE_NUMBER_32:
 		if (type->flags & TRACEEVAL_FL_SIGNED)
-			val = (long long)copy->number_32;
+			val = (long long)dst->number_32;
 		else
-			val = (unsigned long long)copy->number_32;
+			val = (unsigned long long)dst->number_32;
 		break;
 
 	case TRACEEVAL_TYPE_NUMBER_16:
 		if (type->flags & TRACEEVAL_FL_SIGNED)
-			val = (long long)copy->number_16;
+			val = (long long)dst->number_16;
 		else
-			val = (unsigned long long)copy->number_16;
+			val = (unsigned long long)dst->number_16;
 		break;
 
 	case TRACEEVAL_TYPE_NUMBER_8:
 		if (type->flags & TRACEEVAL_FL_SIGNED)
-			val = (long long)copy->number_8;
+			val = (long long)dst->number_8;
 		else
-			val = (unsigned long long)copy->number_8;
+			val = (unsigned long long)dst->number_8;
 		break;
 
 	case TRACEEVAL_TYPE_STRING:
-		copy->string = NULL;
+		dst->string = NULL;
 
-		if (orig->string)
-			copy->string = strdup(orig->string);
+		if (src->string)
+			dst->string = strdup(src->string);
 
-		if (!copy->string)
+		if (!dst->string)
 			return -1;
 		return 0;
 	default:
@@ -619,14 +619,14 @@ static void data_release_and_free(size_t size, union traceeval_data **data,
 }
 
 /*
- * Copy @orig to @copy with respect to @size and @type.
+ * Duplicate a traceeval_data @orig into an newly allocated @copy.
  *
  * Returns 1 on success, -1 on error.
  */
-static int copy_traceeval_data_set(size_t size, struct traceeval_type *type,
-				    const union traceeval_data *orig,
-				    struct traceeval_stat *stats,
-				    union traceeval_data **copy)
+static int dup_traceeval_data_set(size_t size, struct traceeval_type *type,
+				  struct traceeval_stat *stats,
+				  const union traceeval_data *orig,
+				  union traceeval_data **copy)
 {
 	size_t i;
 
@@ -640,7 +640,7 @@ static int copy_traceeval_data_set(size_t size, struct traceeval_type *type,
 
 	for (i = 0; i < size; i++) {
 		if (copy_traceeval_data(type + i, stats ? stats + i : NULL,
-					orig + i, (*copy) + i))
+					 (*copy) + i, orig + i))
 			goto fail;
 	}
 
@@ -745,13 +745,13 @@ static int create_entry(struct traceeval *teval,
 		goto fail_entry;
 
 	/* copy keys */
-	if (copy_traceeval_data_set(teval->nr_key_types, teval->key_types,
-				keys, NULL, &new_keys) == -1)
+	if (dup_traceeval_data_set(teval->nr_key_types, teval->key_types,
+				   NULL, keys, &new_keys) == -1)
 		goto fail_stats;
 
 	/* copy vals */
-	if (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
-				vals, entry->val_stats, &new_vals) == -1)
+	if (dup_traceeval_data_set(teval->nr_val_types, teval->val_types,
+				   entry->val_stats, vals, &new_vals) == -1)
 		goto fail;
 
 	entry->keys = new_keys;
@@ -794,7 +794,7 @@ static int update_entry(struct traceeval *teval, struct entry *entry,
 		old[i] = copy[i];
 
 		if (copy_traceeval_data(types + i, stats + i,
-					vals + i, copy + i))
+					copy + i, vals + i))
 			goto fail;
 	}
 	data_release(size, old, types);
@@ -936,7 +936,7 @@ int traceeval_insert(struct traceeval *teval,
 
 /**
  * traceeval_remove - remove an item from the traceeval descriptor
- * @teval: The descriptor to insert into
+ * @teval: The descriptor to removed from
  * @keys: The list of keys that defines what is being removed
  *
  * This is the opposite of traceeval_insert(). Instead of inserting


-- Steve

Re: [PATCH v4 00/20] libtraceeval histogram: Updates

[Ross Zwisler]

On Thu, Aug 17, 2023 at 04:45:08PM -0400, Steven Rostedt wrote:
> From: "Steven Rostedt (Google)" <rostedt@goodmis.org>
> 
> This patch set is based on top of:
> 
>  https://lore.kernel.org/all/20230809175340.3066-1-stevie.6strings@gmail.com/
> 
> I added a sample program task-eval which is one of the tools that will be
> using this library. The first patch adds task-eval but that is still using
> the old API (defined in trace-analysis.c).
> 
> The next patches modify the new API to fit with the use case of task-eval.
> One is to use "pointer" as I'm not sure exactly the usecase of the dynamic
> structure.
> 
> The cmp and release callbacks are changed to be more generic, and they get
> called if they simply exist for a given type. I can imagine wanting a
> release function for event the most mundane types (like number_32).
> 
> The cmp was also updated to pass in the traceeval descriptor, as I found
> that I needed access to it while doing a compare (although, I rewrote the
> code a bit where that use case isn't in the tool anymore).
> 
> Some fixes were made to the query.
> 
> I also did a bit of code restructuring and add the hash and iterator logic.
> 
> The last patch updates the sample code task-eval.c and has it give pretty
> much the same logic as the original.
> 
> That sample could be updated to implement the code consolidation that Ross
> suggested. I may do that later.
> 
> Happy programming!

Looks good, you can add:

Reviewed-by: Ross Zwisler <zwisler@google.com>
> 
> Changes since v3: https://lore.kernel.org/all/20230817013310.88582-1-rostedt@goodmis.org/
> 
> - Added patch to reordered the parameters of copy_traceeval_data() and renamed
>   copy to dst and orig to src to match that of memcpy() and strcpy().
> 
> - Added patch to rename copy_traceeval_data_set() to dup_traceeval_data_set()
>   to not have the parameter order to be confusing with the typical copy order.
> 
> - Fixed comment of traceeval_remove() (Ross Zwisler)
> 
> Changes since v2: https://lore.kernel.org/all/20230811053940.1408424-1-rostedt@goodmis.org/
> 
>   - Fixed comments on traceeval_dyn_release_fn and traceeval_dyn_cmp_fn (Ross Zwisler)
> 
>   - Change parameter ordering of compare_traceeval_data (Ross Zwisler)
> 
>   - Added (size_t) to offset_of() macro (Ross Zwisler)
> 
>   - Fixed iter->current_bucket off by one bug (Ross Zwisler)
> 
>   - Removed HASH_MASK() from make_hash()
> 
>   - Fixed goto fail_release in traceeval_init() (Ross Zwisler)
> 
>   - Free sort and direction in traceeval_iterator_put() (Ross Zwisler)
> 
>   - Use num_levels variable instead of (level + 1) (Ross Zwisler)
> 
>   - Return 0 on success of update_entry (Ross Zwisler)
> 
>   - Fixed the cleanup of old values in update_entry() (Ross Zwisler)
> 
>   - Fixed resetting iter->next = 0 in traceeval_iterator_sort_custom() (Ross Zwisler)
> 
>   - Added failure checks to task-eval.c sample for all traceeval_query() calls.
> 
>   - Added traceeval_remove() to remove an item from traceveal (opposite of traceeval_insert())
> 
> Changes since v1: https://lore.kernel.org/all/20230809031313.1298605-1-rostedt@goodmis.org/
> 
>  - Lots!
> 
>    - Converted to using a hash table
> 
>    - Removed the unused compare code. With the other updates, it was
>      taking too much time to keep updating them.
> 
>    - Added checks and labels to the types to have them know what type
>      they are, and index they are at.
> 
>    - Added stat logic
> 
>    - Added iterator logic
> 
>    - Have a working sample with the new code!
> 
> Steven Rostedt (Google) (20):
>   libtraceeval histograms: Fix traceeval_results_release() error message
>   libtraceeval: Reverse params of copy_traceeval_data()
>   libtraceeval: Rename copy_traceeval_data_set() to dup_traceeval_data()
>   libtraceeval: Add sample task-eval program
>   libtraceeval hist: Add pointer and const string types
>   libtraceeval histogram: Have cmp and release functions be generic
>   libtraceeval histograms: Add traceeval struct to compare function
>   libtraceeval histogram: Remove comparing of traceeval and types
>   libtraceeval: Convert hist array into a hash table
>   libtraceeval histograms: Move hash functions into their own file
>   libtraceeval histogram: Label and check keys and values
>   libtraceeval histogram: Add updating of stats
>   libtraceeval histogram: Add iterator APIs
>   libtraceeval histogram: Add data copy callback
>   libtraceeval histogram: Do the release on updates
>   libtraceeval histogram: Use stack for old copy in update
>   libtraceeval histogram: Add traceeval_iterator_sort_custom()
>   libtraceeval histogram: Have traceeval_query() just give the pointer
>     to results
>   libtraceeval samples: Update task-eval to use the histogram logic
>   libtraceeval: Add traceeval_remove()
> 
>  Makefile                 |   4 +-
>  include/traceeval-hist.h | 117 +++--
>  include/traceeval-test.h |  16 -
>  samples/Makefile         |  29 ++
>  samples/task-eval.c      | 966 +++++++++++++++++++++++++++++++++++++++
>  src/Makefile             |   1 +
>  src/eval-local.h         | 123 +++++
>  src/hash.c               | 123 +++++
>  src/histograms.c         | 945 ++++++++++++++++++++++++++++----------
>  9 files changed, 2023 insertions(+), 301 deletions(-)
>  delete mode 100644 include/traceeval-test.h
>  create mode 100644 samples/Makefile
>  create mode 100644 samples/task-eval.c
>  create mode 100644 src/eval-local.h
>  create mode 100644 src/hash.c
> 
> -- 
> 2.40.1
>