[PATCH v2 00/17] libtraceeval histogram: Updates

[PATCH v2 00/17] 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 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) (17):
  libtraceeval histograms: Fix traceeval_results_release() error message
  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

 Makefile                 |   4 +-
 include/traceeval-hist.h | 110 +++--
 include/traceeval-test.h |  16 -
 samples/Makefile         |  29 ++
 samples/task-eval.c      | 952 +++++++++++++++++++++++++++++++++++++++
 src/Makefile             |   1 +
 src/eval-local.h         | 123 +++++
 src/hash.c               | 123 +++++
 src/histograms.c         | 878 ++++++++++++++++++++++++++----------
 9 files changed, 1952 insertions(+), 284 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 v2 01/17] 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 v2 02/17] 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.

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 v2 03/17] 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 v2 04/17] 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.

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

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index f6c4e8efb2be..22e9029133d5 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -65,13 +65,13 @@ union traceeval_data {
 struct traceeval_type;
 
 /* struct traceeval_dynamic release function signature */
-typedef void (*traceeval_dyn_release_fn)(struct traceeval_type *,
-					 struct traceeval_dynamic);
+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 *);
+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 d22d15238616..09cdf57a8f6a 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 release on type TRACEEVAL_TYPE_DYNAMIC.
  */
 static void data_release(size_t size, union traceeval_data **data,
 				struct traceeval_type *type)
-- 
2.40.1

[PATCH v2 05/17] 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.

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

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 22e9029133d5..412efdbe8681 100644
--- a/include/traceeval-hist.h
+++ b/include/traceeval-hist.h
@@ -63,16 +63,17 @@ union traceeval_data {
 };
 
 struct traceeval_type;
+struct traceeval;
 
 /* struct traceeval_dynamic release function signature */
-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);
 
 /* struct traceeval_dynamic compare function signature */
-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 09cdf57a8f6a..ece1395ac300 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -113,7 +113,8 @@ 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,
+static int compare_traceeval_data(struct traceeval *teval,
+				  union traceeval_data *orig,
 				  const union traceeval_data *copy,
 				  struct traceeval_type *type)
 {
@@ -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,7 +168,8 @@ 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,
+static int compare_traceeval_data_set(struct traceeval *teval,
+				      union traceeval_data *orig,
 				      const union traceeval_data *copy,
 				      struct traceeval_type *defs, size_t size)
 {
@@ -176,7 +178,7 @@ static int compare_traceeval_data_set(union traceeval_data *orig,
 
 	/* 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, orig + i, copy + i, defs + i)))
 			return check == -2 ? -1 : 0;
 	}
 
@@ -192,13 +194,13 @@ static int compare_entries(struct entry *orig, struct entry *copy,
 	int check;
 
 	/* compare keys */
-	check = compare_traceeval_data_set(orig->keys, copy->keys,
+	check = compare_traceeval_data_set(teval, orig->keys, copy->keys,
 			teval->key_types, teval->nr_key_types);
 	if (check < 1)
 		return check;
 
 	/* compare values */
-	check = compare_traceeval_data_set(orig->vals, copy->vals,
+	check = compare_traceeval_data_set(teval, orig->vals, copy->vals,
 			teval->val_types, 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, entry->keys, keys,
+						   teval->key_types, teval->nr_key_types);
 		if (!check)
 			continue;
 		break;
-- 
2.40.1

[PATCH v2 06/17] 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 ece1395ac300..1ae1d793b6a2 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, orig->keys, copy->keys,
-			teval->key_types, teval->nr_key_types);
-	if (check < 1)
-		return check;
-
-	/* compare values */
-	check = compare_traceeval_data_set(teval, orig->vals, copy->vals,
-			teval->val_types, teval->nr_val_types);
-	return check;
-}
-
-/*
- * Compares the hist fields of @orig and @copy for equality.
- *
- * Assumes all other aspects of @orig and @copy are the same.
- *
- * Return 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 v2 07/17] 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         | 172 +++++++++++++++++++++++++++++++++------
 2 files changed, 153 insertions(+), 26 deletions(-)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 412efdbe8681..4baed4237787 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 1ae1d793b6a2..e6995192881e 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) (&(((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,37 @@ do {					\
 	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 hash 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;
 };
 
-/* 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 +322,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 +378,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 +386,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 +406,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 +447,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 +507,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, entry->keys, keys,
 						   teval->key_types, teval->nr_key_types);
-		if (!check)
-			continue;
-		break;
+		if (check)
+			break;
 	}
 
 	if (check > 0)
@@ -536,6 +635,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 copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
 			entry->vals, results);
 }
@@ -563,6 +663,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 +696,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 (copy_traceeval_data_set(teval->nr_key_types, teval->key_types,
@@ -587,13 +708,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 v2 08/17] 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       | 119 ++++++++++++++++++++++++++++++++++++++++++++
 src/histograms.c | 126 +++++++----------------------------------------
 4 files changed, 240 insertions(+), 109 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..820d7ad096e8
--- /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) (&(((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..e4f2a983d39c
--- /dev/null
+++ b/src/hash.c
@@ -0,0 +1,119 @@
+/* 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];
+	}
+	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;
+
+	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];
+		}
+		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 e6995192881e..574bb115ffc0 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -13,61 +13,7 @@
 
 #include <traceeval-hist.h>
 
-#define offset_of(type, field) (&(((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 hash 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;
-};
+#include "eval-local.h"
 
 /*
  * print_err - print an error message
@@ -317,16 +263,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;
 
@@ -390,36 +331,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;
 }
 
@@ -447,18 +378,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)
 {
@@ -487,13 +406,7 @@ 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);
@@ -508,7 +421,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;
 
@@ -517,10 +432,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, entry->keys, keys,
 						   teval->key_types, teval->nr_key_types);
 		if (check)
@@ -667,20 +581,14 @@ 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)
+	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 v2 09/17] 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 4baed4237787..1c02f3039809 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 574bb115ffc0..a1a2daaa2e9b 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -203,6 +203,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
@@ -213,7 +251,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
@@ -227,11 +270,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;
@@ -248,6 +292,16 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
 		goto fail;
 	}
 
+	ret = check_keys(keys);
+	if (ret < 0)
+		goto fail;
+
+	if (vals) {
+		ret = check_vals(vals);
+		if (ret < 0)
+			goto fail;
+	}
+
 	/* alloc key types */
 	teval->nr_key_types = type_alloc(keys, &teval->key_types);
 	if (teval->nr_key_types <= 0) {
-- 
2.40.1

[PATCH v2 10/17] 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 1c02f3039809..d061a4532b06 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 820d7ad096e8..190b19db14d2 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 a1a2daaa2e9b..9a8ec4d85301 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -506,21 +506,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,
-				const union traceeval_data *orig,
-				union traceeval_data *copy)
+			       struct traceeval_stat *stat,
+			       const union traceeval_data *orig,
+			       union traceeval_data *copy)
 {
+	unsigned long long val;
+
 	*copy = *orig;
 
-	if (type->type == TRACEEVAL_TYPE_STRING) {
+	switch(type->type) {
+	case TRACEEVAL_TYPE_NUMBER:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)copy->number;
+		else
+			val = (unsigned long long)copy->number;
+		break;
+
+	case TRACEEVAL_TYPE_NUMBER_64:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)copy->number_64;
+		else
+			val = (unsigned long long)copy->number_64;
+		break;
+
+	case TRACEEVAL_TYPE_NUMBER_32:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)copy->number_32;
+		else
+			val = (unsigned long long)copy->number_32;
+		break;
+
+	case TRACEEVAL_TYPE_NUMBER_16:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)copy->number_16;
+		else
+			val = (unsigned long long)copy->number_16;
+		break;
+
+	case TRACEEVAL_TYPE_NUMBER_8:
+		if (type->flags & TRACEEVAL_FL_SIGNED)
+			val = (long long)copy->number_8;
+		else
+			val = (unsigned long long)copy->number_8;
+		break;
+
+	case TRACEEVAL_TYPE_STRING:
 		copy->string = NULL;
 
 		if (orig->string)
 			copy->string = strdup(orig->string);
-		else
-			return 0;
 
 		if (!copy->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;
@@ -549,6 +613,7 @@ static void data_release(size_t size, union traceeval_data **data,
  */
 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)
 {
 	size_t i;
@@ -562,7 +627,8 @@ 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, stats ? stats + i : NULL,
+					orig + i, (*copy) + i))
 			goto fail;
 	}
 
@@ -605,7 +671,7 @@ int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 		return check;
 
 	return copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
-			entry->vals, results);
+			entry->vals, NULL, results);
 }
 
 /*
@@ -660,18 +726,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 (copy_traceeval_data_set(teval->nr_key_types, teval->key_types,
-				keys, &new_keys) == -1)
-		return -1;
+				keys, NULL, &new_keys) == -1)
+		goto fail_stats;
 
 	/* copy vals */
 	if (copy_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)
+				vals, entry->val_stats, &new_vals) == -1)
 		goto fail;
 
 	entry->keys = new_keys;
@@ -680,10 +750,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;
 }
 
@@ -700,7 +773,7 @@ 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)
+				vals, entry->val_stats, &new_vals) == -1)
 		return -1;
 
 	clean_data_set(entry->vals, teval->val_types, teval->nr_val_types);
@@ -708,6 +781,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 v2 11/17] 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/hash.c               |   4 +
 src/histograms.c         | 255 ++++++++++++++++++++++++++++++++++++++-
 4 files changed, 276 insertions(+), 1 deletion(-)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index d061a4532b06..2fc81a64e324 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 190b19db14d2..c3ea920ed2e8 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/hash.c b/src/hash.c
index e4f2a983d39c..221145efcbb9 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -67,6 +67,7 @@ __hidden struct hash_iter *hash_iter_start(struct hash_table *hash)
 		if (!hash->hash[i])
 			continue;
 		iter->next_item = hash->hash[i];
+		break;
 	}
 	iter->current_bucket = i;
 	return iter;
@@ -81,6 +82,8 @@ __hidden struct hash_item *hash_iter_next(struct hash_iter *iter)
 		return NULL;
 
 	item = iter->next_item;
+	if (!item)
+		return NULL;
 
 	iter->next_item = item->next;
 	if (!iter->next_item) {
@@ -90,6 +93,7 @@ __hidden struct hash_item *hash_iter_next(struct hash_iter *iter)
 			if (!hash->hash[i])
 				continue;
 			iter->next_item = hash->hash[i];
+			break;
 		}
 		iter->current_bucket = i;
 	}
diff --git a/src/histograms.c b/src/histograms.c
index 9a8ec4d85301..2b823ad5c26d 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -37,7 +37,7 @@ static void print_err(const char *fmt, ...)
  * -1 for the other way around, and -2 on error.
  */
 static int compare_traceeval_data(struct traceeval *teval,
-				  union traceeval_data *orig,
+				  const union traceeval_data *orig,
 				  const union traceeval_data *copy,
 				  struct traceeval_type *type)
 {
@@ -904,3 +904,256 @@ 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->entries);
+	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;
+
+	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 ((level + 1) > iter->nr_sort) {
+		sort = realloc(sort, sizeof(*sort) * (level + 1));
+		if (!sort)
+			return -1;
+
+		iter->sort = sort;
+
+		direction = realloc(direction, sizeof(*direction) * (level + 1));
+		if (!direction)
+			return -1;
+
+		iter->direction = direction;
+
+		/* Make sure the newly allocated contain NULL */
+		for (int i = iter->nr_sort; i < (level + 1); 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, dataA, dataB, type);
+
+		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 v2 12/17] 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 2fc81a64e324..1a24d6117b93 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 *copy,
+				      const union traceeval_data *origin);
+
 /*
  * 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 2b823ad5c26d..f7f72dd3a50b 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -512,6 +512,9 @@ static int copy_traceeval_data(struct traceeval_type *type,
 {
 	unsigned long long val;
 
+	if (type->copy)
+		return type->copy(type, copy, orig);
+
 	*copy = *orig;
 
 	switch(type->type) {
-- 
2.40.1

[PATCH v2 13/17] 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 f7f72dd3a50b..8c73d8cd9f45 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -596,12 +596,16 @@ static int copy_traceeval_data(struct traceeval_type *type,
 /*
  * Free @data with respect to @size and @type.
  *
- * Does not call release on type TRACEEVAL_TYPE_DYNAMIC.
+ * Does not call release() 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 v2 14/17] 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 | 48 ++++++++++++++++++++++++++++++++++--------------
 1 file changed, 34 insertions(+), 14 deletions(-)

diff --git a/src/histograms.c b/src/histograms.c
index 8c73d8cd9f45..643a550422f6 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -598,17 +598,23 @@ static int copy_traceeval_data(struct traceeval_type *type,
  *
  * Does not call release() 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;
 }
@@ -642,7 +648,7 @@ static int copy_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;
 }
 
@@ -701,7 +707,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,
@@ -757,7 +763,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);
@@ -772,20 +778,34 @@ fail_entry:
  *
  * Frees the old vals field of @entry, unless an error occurs.
  *
- * Return 0 on success, -1 on error.
+ * Return 1 on success, -1 on error.
  */
 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 (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
-				vals, entry->val_stats, &new_vals) == -1)
-		return -1;
+	if (!size)
+		return 1;
+
+	for (i = 0; i < size; i++) {
+		old[i] = copy[i];
+
+		if (copy_traceeval_data(types + i, stats + i,
+					vals + i, copy + i))
+			goto fail;
+	}
 
-	clean_data_set(entry->vals, teval->val_types, teval->nr_val_types);
-	entry->vals = new_vals;
 	return 0;
+
+fail:
+	data_release(i, old, types);
+	return -1;
 }
 
 struct traceeval_stat *traceeval_stat(struct traceeval *teval,
-- 
2.40.1

[PATCH v2 15/17] 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         | 34 ++++++++++++++++++++++++++++++++++
 2 files changed, 43 insertions(+)

diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
index 1a24d6117b93..839f63630897 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 *copy,
 				      const union traceeval_data *origin);
 
+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 643a550422f6..33c87644d468 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -1153,6 +1153,40 @@ 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;
+	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 v2 16/17] 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 839f63630897..315b66adb7ee 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 33c87644d468..cd68d4c834af 100644
--- a/src/histograms.c
+++ b/src/histograms.c
@@ -671,7 +671,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;
@@ -683,8 +683,8 @@ int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 	if ((check = get_entry(teval, keys, &entry)) < 1)
 		return check;
 
-	return copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
-			entry->vals, NULL, results);
+	*results = entry->vals;
+	return 1;
 }
 
 /*
@@ -699,15 +699,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 v2 17/17] 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 | 729 +++++++++++++++++++++++++-------------------
 2 files changed, 412 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..e0ef2d0bcb30 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,50 @@ 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)
+			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 +251,162 @@ 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)
+		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 ? */
+
+	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;
+		}
+		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)
+			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)
+			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 +439,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 +487,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 +524,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 +548,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 +558,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 +570,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 +625,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 +712,168 @@ 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 < 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 +882,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 +896,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 +923,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

Re: [PATCH v2 04/17] libtraceeval histogram: Have cmp and release functions be generic

[Ross Zwisler]

On Fri, Aug 11, 2023 at 01:39:27AM -0400, Steven Rostedt wrote:
> 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.
> 
> Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
> ---
>  include/traceeval-hist.h | 46 +++++++++++++++++++++-------------------
>  src/histograms.c         | 28 ++++++++++++------------
>  2 files changed, 38 insertions(+), 36 deletions(-)
> 
> diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> index f6c4e8efb2be..22e9029133d5 100644
> --- a/include/traceeval-hist.h
> +++ b/include/traceeval-hist.h
> @@ -65,13 +65,13 @@ union traceeval_data {
>  struct traceeval_type;
>  
>  /* struct traceeval_dynamic release function signature */

You may want to update the comment here to make it clear that this is now for
both dynamic and pointer types.  Ditto for the compare function signature.

> -typedef void (*traceeval_dyn_release_fn)(struct traceeval_type *,
> -					 struct traceeval_dynamic);
> +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 *);
> +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
<>
> @@ -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 release on type TRACEEVAL_TYPE_DYNAMIC.

or for TRACEEVAL_TYPE_POINTER.

>   */
>  static void data_release(size_t size, union traceeval_data **data,
>  				struct traceeval_type *type)
> -- 
> 2.40.1

Aside from these two comment nits, you can add:

Reviewed-by: Ross Zwisler <zwisler@google.com>

Re: [PATCH v2 05/17] libtraceeval histograms: Add traceeval struct to compare function

[Ross Zwisler]

On Fri, Aug 11, 2023 at 01:39:28AM -0400, Steven Rostedt wrote:
> 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.
> 
> Signed-off-by: Steven Rostedt (Google) <rostedt@goodmis.org>
> ---
>  include/traceeval-hist.h | 13 +++++++------
>  src/histograms.c         | 19 ++++++++++---------
>  2 files changed, 17 insertions(+), 15 deletions(-)
> 
> diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> index 22e9029133d5..412efdbe8681 100644
> --- a/include/traceeval-hist.h
> +++ b/include/traceeval-hist.h
> @@ -63,16 +63,17 @@ union traceeval_data {
>  };
>  
>  struct traceeval_type;
> +struct traceeval;
>  
>  /* struct traceeval_dynamic release function signature */
> -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);
>  
>  /* struct traceeval_dynamic compare function signature */
> -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 09cdf57a8f6a..ece1395ac300 100644
> --- a/src/histograms.c
> +++ b/src/histograms.c
> @@ -113,7 +113,8 @@ 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,
> +static int compare_traceeval_data(struct traceeval *teval,
> +				  union traceeval_data *orig,
>  				  const union traceeval_data *copy,
>  				  struct traceeval_type *type)

Nit: it would be nice if these had the same ordering as the args to
traceeval_data_cmp_fn.

Other than that you can add:

Reviewed-by: Ross Zwisler <zwisler@google.com>

Re: [PATCH v2 07/17] libtraceeval: Convert hist array into a hash table

[Ross Zwisler]

On Fri, Aug 11, 2023 at 01:39:30AM -0400, Steven Rostedt wrote:
> 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         | 172 +++++++++++++++++++++++++++++++++------
>  2 files changed, 153 insertions(+), 26 deletions(-)
> 
> diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> index 412efdbe8681..4baed4237787 100644
> --- a/include/traceeval-hist.h
> +++ b/include/traceeval-hist.h
<>
> @@ -12,6 +13,14 @@
>  
>  #include <traceeval-hist.h>
>  
> +#define offset_of(type, field) (&(((type *)(NULL))->field))

This currently returns a pointer type, but the kernel implementation(s) have
this cast back to a size_t, which makes sense I think.

https://elixir.bootlin.com/linux/latest/source/tools/include/nolibc/types.h#L220

> +#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.
>   *
<>
> @@ -365,16 +406,19 @@ static void clean_entry(struct entry *entry, struct traceeval *teval)
>   */
>  static void hist_table_release(struct traceeval *teval)

This probably wants to be 'hash_table_release()' now since 'hist_table' is
gone.

>  {
> -	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;
>  }

Re: [PATCH v2 04/17] libtraceeval histogram: Have cmp and release functions be generic

[Steven Rostedt]

On Tue, 15 Aug 2023 10:50:28 -0600
Ross Zwisler <zwisler@google.com> wrote:

> > diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> > index f6c4e8efb2be..22e9029133d5 100644
> > --- a/include/traceeval-hist.h
> > +++ b/include/traceeval-hist.h
> > @@ -65,13 +65,13 @@ union traceeval_data {
> >  struct traceeval_type;
> >  
> >  /* struct traceeval_dynamic release function signature */  
> 
> You may want to update the comment here to make it clear that this is now for
> both dynamic and pointer types.  Ditto for the compare function signature.

Agreed, (I was tired and new I was going to miss some spots).

> 
> > -typedef void (*traceeval_dyn_release_fn)(struct traceeval_type *,
> > -					 struct traceeval_dynamic);
> > +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 *);
> > +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  
> <>
> > @@ -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 release on type TRACEEVAL_TYPE_DYNAMIC.  
> 
> or for TRACEEVAL_TYPE_POINTER.

+1

> 
> >   */
> >  static void data_release(size_t size, union traceeval_data **data,
> >  				struct traceeval_type *type)
> > -- 
> > 2.40.1  
> 
> Aside from these two comment nits, you can add:
> 
> Reviewed-by: Ross Zwisler <zwisler@google.com>

Thanks Ross!

-- Steve

Re: [PATCH v2 05/17] libtraceeval histograms: Add traceeval struct to compare function

[Steven Rostedt]

On Tue, 15 Aug 2023 10:55:54 -0600
Ross Zwisler <zwisler@google.com> wrote:

> > --- a/src/histograms.c
> > +++ b/src/histograms.c
> > @@ -113,7 +113,8 @@ 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,
> > +static int compare_traceeval_data(struct traceeval *teval,
> > +				  union traceeval_data *orig,
> >  				  const union traceeval_data *copy,
> >  				  struct traceeval_type *type)  
> 
> Nit: it would be nice if these had the same ordering as the args to
> traceeval_data_cmp_fn.
> 

Yeah, I noticed that to, but figured I can change it later, as it's not API.

I'll update it.

> Other than that you can add:
> 
> Reviewed-by: Ross Zwisler <zwisler@google.com>

Thanks Ross,

-- Steve

Re: [PATCH v2 07/17] libtraceeval: Convert hist array into a hash table

[Steven Rostedt]

On Tue, 15 Aug 2023 12:44:21 -0600
Ross Zwisler <zwisler@google.com> wrote:

> On Fri, Aug 11, 2023 at 01:39:30AM -0400, Steven Rostedt wrote:
> > 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         | 172 +++++++++++++++++++++++++++++++++------
> >  2 files changed, 153 insertions(+), 26 deletions(-)
> > 
> > diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> > index 412efdbe8681..4baed4237787 100644
> > --- a/include/traceeval-hist.h
> > +++ b/include/traceeval-hist.h  
> <>
> > @@ -12,6 +13,14 @@
> >  
> >  #include <traceeval-hist.h>
> >  
> > +#define offset_of(type, field) (&(((type *)(NULL))->field))  
> 
> This currently returns a pointer type, but the kernel implementation(s) have
> this cast back to a size_t, which makes sense I think.
> 
> https://elixir.bootlin.com/linux/latest/source/tools/include/nolibc/types.h#L220

As this is under an MIT license, I created this without looking at the GPL version.

It's really too small and common to be licensed, but still. I'll make the update.


> 
> > +#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.
> >   *  
> <>
> > @@ -365,16 +406,19 @@ static void clean_entry(struct entry *entry, struct traceeval *teval)
> >   */
> >  static void hist_table_release(struct traceeval *teval)  
> 
> This probably wants to be 'hash_table_release()' now since 'hist_table' is
> gone.

I actually purposely kept the "hist" name (teval->hist) for this local file.

Just because that's what Stevie called it ;-)

-- Steve

> 
> >  {
> > -	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;
> >  }  

Re: [PATCH v2 08/17] libtraceeval histograms: Move hash functions into their own file

[Ross Zwisler]

On Fri, Aug 11, 2023 at 01:39:31AM -0400, Steven Rostedt wrote:
> 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       | 119 ++++++++++++++++++++++++++++++++++++++++++++
>  src/histograms.c | 126 +++++++----------------------------------------
>  4 files changed, 240 insertions(+), 109 deletions(-)
>  create mode 100644 src/eval-local.h
>  create mode 100644 src/hash.c

<>

> diff --git a/src/hash.c b/src/hash.c
> new file mode 100644
> index 000000000000..e4f2a983d39c
> --- /dev/null
> +++ b/src/hash.c
> @@ -0,0 +1,119 @@
> +/* 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);

key should already be masked to HASH_MASK(hash->bits) via make_hash().  If
those bits are set, we have a bug somewhere.

I think it's better to check to see if those bits are set and bail out loudly
with an error.

> +
> +	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];

I think we need to break here after we've found a populated bucket and set
iter->next_item.  Right now this works only if we have a single populated
bucket, because we'll set iter->next_item once and then keep iterating until
i == HASH_SIZE(hash->bits).

This will mean that iter->current_bucket will always == HASH_SIZE(hash->bits),
but we have a bug in hash_iter_next() that meant we weren't returning early
with NULL when we hit this condition.

> +	}
> +	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))

	if (iter->current_bucket >= HASH_SIZE(hash->bits))

Right now we're missing the exit case where
iter->current_bucket == HASH_SIZE(hash->bits), which means we've run out of
buckets with entries.

> +		return NULL;
> +
> +	item = iter->next_item;
> +
> +	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];

As in hash_iter_start(), we need to break when we find the next non-empty
bucket and set iter->next_item.  This will let us set iter->current_bucket
correctly as well.

> +		}
> +		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);

As with hash_add(), 'key' should already be masked and I think it'd be better
to error out loudly if upper bits in 'key' are unexpectedly set.

> +
> +	iter->current_bucket = key;
> +	iter->next_item = hash->hash[key];
> +
> +	return iter;
> +}
> +

Re: [PATCH v2 09/17] libtraceeval histogram: Label and check keys and values

[Ross Zwisler]

On Fri, Aug 11, 2023 at 01:39:32AM -0400, Steven Rostedt wrote:
> 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 4baed4237787..1c02f3039809 100644
> --- a/include/traceeval-hist.h
> +++ b/include/traceeval-hist.h
<>
> @@ -248,6 +292,16 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
>  		goto fail;
>  	}
>  
> +	ret = check_keys(keys);
> +	if (ret < 0)
> +		goto fail;
> +
> +	if (vals) {
> +		ret = check_vals(vals);
> +		if (ret < 0)
> +			goto fail;

These two goto statements should both be to fail_release so we clean up
'teval', else we could do this check above the alloc.

> +	}
> +
>  	/* alloc key types */
>  	teval->nr_key_types = type_alloc(keys, &teval->key_types);
>  	if (teval->nr_key_types <= 0) {
> -- 
> 2.40.1
> 

Re: [PATCH v2 08/17] libtraceeval histograms: Move hash functions into their own file

[Steven Rostedt]

On Tue, 15 Aug 2023 13:31:56 -0600
Ross Zwisler <zwisler@google.com> wrote:

> 
> > diff --git a/src/hash.c b/src/hash.c
> > new file mode 100644
> > index 000000000000..e4f2a983d39c
> > --- /dev/null
> > +++ b/src/hash.c
> > @@ -0,0 +1,119 @@
> > +/* 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);  
> 
> key should already be masked to HASH_MASK(hash->bits) via make_hash().  If
> those bits are set, we have a bug somewhere.
> 
> I think it's better to check to see if those bits are set and bail out loudly
> with an error.

I debated a bit about where to do the mask. I didn't want to put a
dependency that the bits were already masked, so I just did it twice. It's
a very fast operation.

I also don't want to make the dependency that key can only come from
mask_hash(). As it's critical that key is masked here (or we have a array
overflow), I just kept it in both places.

I can comment that here.

> 
> > +
> > +	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];  
> 
> I think we need to break here after we've found a populated bucket and set
> iter->next_item.  Right now this works only if we have a single populated
> bucket, because we'll set iter->next_item once and then keep iterating until
> i == HASH_SIZE(hash->bits).
> 
> This will mean that iter->current_bucket will always == HASH_SIZE(hash->bits),
> but we have a bug in hash_iter_next() that meant we weren't returning early
> with NULL when we hit this condition.

Nice catch, but I found this bug during my tests but fixed it in patch 11. :-p

I'll move that change here, as that's the proper place it belongs.

> 
> > +	}
> > +	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))  
> 
> 	if (iter->current_bucket >= HASH_SIZE(hash->bits))
> 
> Right now we're missing the exit case where
> iter->current_bucket == HASH_SIZE(hash->bits), which means we've run out
> of buckets with entries.

You are correct that it should be fixed, but it just happens that the rest
of the logic will still end up returning NULL when this happens. But the
above was suppose to be a "shortcut" that never gets hit (or why I fixed it
in patch 11)!

> 
> > +		return NULL;
> > +
> > +	item = iter->next_item;

In patch 11, I added:

	if (!item)
		return NULL;

That should be here too (along with the above off by one fix).

> > +
> > +	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];  
> 
> As in hash_iter_start(), we need to break when we find the next non-empty
> bucket and set iter->next_item.  This will let us set iter->current_bucket
> correctly as well.

And this too was fixed in patch 11.

> 
> > +		}
> > +		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);  
> 
> As with hash_add(), 'key' should already be masked and I think it'd be
> better to error out loudly if upper bits in 'key' are unexpectedly set.

Again, I don't want to add a dependency of where key was created. It may be
used for other purposes (and the upper bits may hold info later).  I think
it's just more robust to keep the extra masks. Again, they are very fast
operations.

Thanks Ross,

-- Steve

> 
> > +
> > +	iter->current_bucket = key;
> > +	iter->next_item = hash->hash[key];
> > +
> > +	return iter;
> > +}
> > +  

Re: [PATCH v2 09/17] libtraceeval histogram: Label and check keys and values

[Steven Rostedt]

On Tue, 15 Aug 2023 13:48:09 -0600
Ross Zwisler <zwisler@google.com> wrote:

> On Fri, Aug 11, 2023 at 01:39:32AM -0400, Steven Rostedt wrote:
> > 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 4baed4237787..1c02f3039809 100644
> > --- a/include/traceeval-hist.h
> > +++ b/include/traceeval-hist.h  
> <>
> > @@ -248,6 +292,16 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
> >  		goto fail;
> >  	}
> >  
> > +	ret = check_keys(keys);
> > +	if (ret < 0)
> > +		goto fail;
> > +
> > +	if (vals) {
> > +		ret = check_vals(vals);
> > +		if (ret < 0)
> > +			goto fail;  
> 
> These two goto statements should both be to fail_release so we clean up
> 'teval', else we could do this check above the alloc.

Nice catch. Will fix.

-- Steve

> 
> > +	}
> > +
> >  	/* alloc key types */
> >  	teval->nr_key_types = type_alloc(keys, &teval->key_types);
> >  	if (teval->nr_key_types <= 0) {
> > -- 
> > 2.40.1
> >   

Re: [PATCH v2 10/17] libtraceeval histogram: Add updating of stats

[Ross Zwisler]

On Fri, Aug 11, 2023 at 01:39:33AM -0400, Steven Rostedt wrote:
> 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 1c02f3039809..d061a4532b06 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 820d7ad096e8..190b19db14d2 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;

I'm confused about why 'val_stats' is in 'struct entry', instead of in
'struct traceeval'?

I would think that we'd want to keep our stats on a per-histogram basis, where
we have an array of 'struct traceeval_stat' structs with the same size as our
'val_types' array, so that for a given compound value, say 

{ TRACEVAL_TYPE_NUMBER_64, TRACEEVAL_TYPE_NUMBER_16, TRACEEVAL_NUMBER_8}

we'd have stats for each of these entries, like min, max, average, etc.?

With the stats associated with each entry, I don't see how we keep all the
stats for all the entries up to date as we do insertions & removals.

Re: [PATCH v2 10/17] libtraceeval histogram: Add updating of stats

[Steven Rostedt]

On Tue, 15 Aug 2023 14:25:54 -0600
Ross Zwisler <zwisler@google.com> wrote:

> On Fri, Aug 11, 2023 at 01:39:33AM -0400, Steven Rostedt wrote:
> > 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 1c02f3039809..d061a4532b06 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 820d7ad096e8..190b19db14d2 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;  
> 
> I'm confused about why 'val_stats' is in 'struct entry', instead of in
> 'struct traceeval'?
> 
> I would think that we'd want to keep our stats on a per-histogram basis, where
> we have an array of 'struct traceeval_stat' structs with the same size as our
> 'val_types' array, so that for a given compound value, say 
> 
> { TRACEVAL_TYPE_NUMBER_64, TRACEEVAL_TYPE_NUMBER_16, TRACEEVAL_NUMBER_8}
> 
> we'd have stats for each of these entries, like min, max, average, etc.?
> 
> With the stats associated with each entry, I don't see how we keep all the
> stats for all the entries up to date as we do insertions & removals.

Because the stats are for each key, not the total of the traceeval. If you
look at the code in task-eval, I want to know the max,min,total,count,avg
of the sleep time for a task when it is blocked, when it is sleeping, when
it is running, etc:

Task: migrate
      Total run time (us):       4645364
      Total blocked time (us):         0
      Total preempt time (us):     98540
      Total sleep time (us):      115559

    thread id: 1884
      Total run time (us):           808

    thread id: 1885
      Total run time (us):       2920763
      Total preempt time (us):    245570
      Total sleep time (us):   224289277

    thread id: 1886
      Total run time (us):       3601375
      Total preempt time (us):   1308185
      Total sleep time (us):    12692630

    thread id: 1887
      Total run time (us):       3740300
      Total preempt time (us):   2620102
      Total sleep time (us):     4806722

That "Task: migrate" is just one entry in the traceeval, the threads are
entries in the nested traceeval that is saved per task.

Actually, task-eval is only looking at the total time, but I could easily
add the max/min/avg times too. If I were to write a latency program, and
was tracing the wake up latency of a task, you probably want these stats
for each key, so I can see the max latency per task, and not just the total
for all tasks.

-- Steve

Re: [PATCH v2 08/17] libtraceeval histograms: Move hash functions into their own file

[Steven Rostedt]

On Tue, 15 Aug 2023 16:23:33 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> > > +__hidden void hash_add(struct hash_table *hash, struct hash_item *item, unsigned key)
> > > +{
> > > +	key &= HASH_MASK(hash->bits);    
> > 
> > key should already be masked to HASH_MASK(hash->bits) via make_hash().  If
> > those bits are set, we have a bug somewhere.
> > 
> > I think it's better to check to see if those bits are set and bail out loudly
> > with an error.  
> 
> I debated a bit about where to do the mask. I didn't want to put a
> dependency that the bits were already masked, so I just did it twice. It's
> a very fast operation.
> 
> I also don't want to make the dependency that key can only come from
> mask_hash(). As it's critical that key is masked here (or we have a array
> overflow), I just kept it in both places.
> 
> I can comment that here.

Thinking about this more, I'm not even sure I want HASH_MASK() in
make_hash(). In fact, I think I'm going to remove it. The hash size is
really internal to the hash code, and to maintain a proper abstraction,
other code should not assume how big the bucket array is.

-- Steve

Re: [PATCH v2 11/17] libtraceeval histogram: Add iterator APIs

[Ross Zwisler]

On Fri, Aug 11, 2023 at 01:39:34AM -0400, Steven Rostedt wrote:
> 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/hash.c               |   4 +
>  src/histograms.c         | 255 ++++++++++++++++++++++++++++++++++++++-
>  4 files changed, 276 insertions(+), 1 deletion(-)
> 
<>
> diff --git a/src/histograms.c b/src/histograms.c
> index 9a8ec4d85301..2b823ad5c26d 100644
> --- a/src/histograms.c
> +++ b/src/histograms.c
> @@ -37,7 +37,7 @@ static void print_err(const char *fmt, ...)
>   * -1 for the other way around, and -2 on error.
>   */
>  static int compare_traceeval_data(struct traceeval *teval,
> -				  union traceeval_data *orig,
> +				  const union traceeval_data *orig,
>  				  const union traceeval_data *copy,
>  				  struct traceeval_type *type)
>  {
> @@ -904,3 +904,256 @@ 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->entries);

I think we also need to free **sort and *direction, which are both allocated
in traceeval_iterator_sort().    Probably need to update the function comment
as well to include allocs from that function.

> +	free(iter);
> +}
<>
> +/**
> + * 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;
> +
> +	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;
> +	}
> +

nit: It'd probably help with readability to have:

  int num_levels = level + 1;

and use that instead of (level + 1).

> +	if ((level + 1) > iter->nr_sort) {
> +		sort = realloc(sort, sizeof(*sort) * (level + 1));
> +		if (!sort)
> +			return -1;
> +
> +		iter->sort = sort;
> +
> +		direction = realloc(direction, sizeof(*direction) * (level + 1));
> +		if (!direction)
> +			return -1;
> +
> +		iter->direction = direction;
> +
> +		/* Make sure the newly allocated contain NULL */
> +		for (int i = iter->nr_sort; i < (level + 1); i++)
> +			sort[i] = NULL;
> +
> +		iter->nr_sort = level + 1;
> +	}
> +
> +	sort[level] = type;
> +	direction[level] = ascending;
> +	iter->needs_sort = true;
> +	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;

This is already done in sort_iter().

> +	}
> +
> +	if (iter->next >= iter->nr_entries)
> +		return 0;
> +
> +	entry = iter->entries[iter->next++];
> +	*keys = entry->keys;
> +	return 1;
> +}
> -- 
> 2.40.1
> 

Re: [PATCH v2 11/17] libtraceeval histogram: Add iterator APIs

[Steven Rostedt]

On Wed, 16 Aug 2023 15:34:49 -0600
Ross Zwisler <zwisler@google.com> wrote:

> > +
> > +/**
> > + * 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->entries);  
> 
> I think we also need to free **sort and *direction, which are both allocated
> in traceeval_iterator_sort().    Probably need to update the function comment
> as well to include allocs from that function.

Yes, thanks.

> 
> > +	free(iter);
> > +}  
> <>
> > +/**
> > + * 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;
> > +
> > +	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;
> > +	}
> > +  
> 
> nit: It'd probably help with readability to have:
> 
>   int num_levels = level + 1;
> 
> and use that instead of (level + 1).

Sure, I'm just so use to the (level + 1), that it comes natural for me now.
But I do agree, from a readability standpoint, having a "num_levels" would
be better.

> 
> > +	if ((level + 1) > iter->nr_sort) {
> > +		sort = realloc(sort, sizeof(*sort) * (level + 1));
> > +		if (!sort)
> > +			return -1;
> > +
> > +		iter->sort = sort;
> > +
> > +		direction = realloc(direction, sizeof(*direction) * (level + 1));
> > +		if (!direction)
> > +			return -1;
> > +
> > +		iter->direction = direction;
> > +
> > +		/* Make sure the newly allocated contain NULL */
> > +		for (int i = iter->nr_sort; i < (level + 1); i++)
> > +			sort[i] = NULL;
> > +
> > +		iter->nr_sort = level + 1;
> > +	}
> > +
> > +	sort[level] = type;
> > +	direction[level] = ascending;
> > +	iter->needs_sort = true;
> > +	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;  
> 
> This is already done in sort_iter().


Yep, I know. But I love redundancy ;-)

I actually added it to both at the same time because I didn't know which
one was better to have it. I compromised, and just said "OK do it in both!"

-- Steve

> 
> > +	}
> > +
> > +	if (iter->next >= iter->nr_entries)
> > +		return 0;
> > +
> > +	entry = iter->entries[iter->next++];
> > +	*keys = entry->keys;
> > +	return 1;
> > +}
> > -- 
> > 2.40.1
> >   

Re: [PATCH v2 14/17] libtraceeval histogram: Use stack for old copy in update

[Ross Zwisler]

On Fri, Aug 11, 2023 at 01:39:37AM -0400, Steven Rostedt wrote:
> 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 | 48 ++++++++++++++++++++++++++++++++++--------------
>  1 file changed, 34 insertions(+), 14 deletions(-)
> 
<>
> @@ -772,20 +778,34 @@ fail_entry:
>   *
>   * Frees the old vals field of @entry, unless an error occurs.
>   *
> - * Return 0 on success, -1 on error.
> + * Return 1 on success, -1 on error.

The code is now returning 1, 0 and -1 in different cases, and all three of
these return values are percolating up to be returned by traceeval_insert(),
which is only supposed to return 0 or 1.

>   */
>  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 (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
> -				vals, entry->val_stats, &new_vals) == -1)
> -		return -1;
> +	if (!size)
> +		return 1;

If we try and copy a 0 length val, is it okay to just return 0 here and call
it success?

> +
> +	for (i = 0; i < size; i++) {
> +		old[i] = copy[i];
> +
> +		if (copy_traceeval_data(types + i, stats + i,
> +					vals + i, copy + i))
> +			goto fail;
> +	}

I think we still need to rip through old[] and free strings, and also call
.release on types that define it, probably via data_release().

I don't understand why data_release() only calls .release if a .copy function
isn't defined?  Are we saying that .copy() must also release the old data?  If
so that needs to be explicit, but I think we still need to free strings at a
minimum.

>  
> -	clean_data_set(entry->vals, teval->val_types, teval->nr_val_types);
> -	entry->vals = new_vals;
>  	return 0;
> +
> +fail:
> +	data_release(i, old, types);
> +	return -1;
>  }
>  
>  struct traceeval_stat *traceeval_stat(struct traceeval *teval,
> -- 
> 2.40.1
> 

Re: [PATCH v2 15/17] libtraceeval histogram: Add traceeval_iterator_sort_custom()

[Ross Zwisler]

On Fri, Aug 11, 2023 at 01:39:38AM -0400, Steven Rostedt wrote:
> 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         | 34 ++++++++++++++++++++++++++++++++++
>  2 files changed, 43 insertions(+)
> 
> diff --git a/include/traceeval-hist.h b/include/traceeval-hist.h
> index 1a24d6117b93..839f63630897 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 *copy,
>  				      const union traceeval_data *origin);
>  
> +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 643a550422f6..33c87644d468 100644
> --- a/src/histograms.c
> +++ b/src/histograms.c
> @@ -1153,6 +1153,40 @@ 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);

I guess I don't yet see what this gives us over the existing sorting and
iterators?  Does this do the same thing, we just pass in the sort function
instead of calling traceeval_iterator_sort() one or more times?

> +
> +	iter->needs_sort = false;

Also probably need to set
  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
> 

Re: [PATCH v2 14/17] libtraceeval histogram: Use stack for old copy in update

[Steven Rostedt]

On Wed, 16 Aug 2023 16:37:54 -0600
Ross Zwisler <zwisler@google.com> wrote:

> On Fri, Aug 11, 2023 at 01:39:37AM -0400, Steven Rostedt wrote:
> > 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 | 48 ++++++++++++++++++++++++++++++++++--------------
> >  1 file changed, 34 insertions(+), 14 deletions(-)
> >   
> <>
> > @@ -772,20 +778,34 @@ fail_entry:
> >   *
> >   * Frees the old vals field of @entry, unless an error occurs.
> >   *
> > - * Return 0 on success, -1 on error.
> > + * Return 1 on success, -1 on error.  
> 
> The code is now returning 1, 0 and -1 in different cases, and all three of
> these return values are percolating up to be returned by traceeval_insert(),
> which is only supposed to return 0 or 1.
> 

I didn't update the comments well. The idea is, return 1 if the element
already existed, 0 if it did not, and -1 on error. I need to fix this.

> >   */
> >  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 (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
> > -				vals, entry->val_stats, &new_vals) == -1)
> > -		return -1;
> > +	if (!size)
> > +		return 1;  
> 
> If we try and copy a 0 length val, is it okay to just return 0 here and call
> it success?
> 
> > +
> > +	for (i = 0; i < size; i++) {
> > +		old[i] = copy[i];
> > +
> > +		if (copy_traceeval_data(types + i, stats + i,
> > +					vals + i, copy + i))
> > +			goto fail;
> > +	}  
> 
> I think we still need to rip through old[] and free strings, and also call

Yes, I forgot to add that :-p 

> .release on types that define it, probably via data_release().
> 
> I don't understand why data_release() only calls .release if a .copy function
> isn't defined?  Are we saying that .copy() must also release the old data?  If
> so that needs to be explicit, but I think we still need to free strings at a
> minimum.

So the idea is that the release function is called to release (free) the
old data. But the copy may not need to allocate or free, it could use the
existing data. This will be explicitly stated in the man pages (when I get
around to writing them).

-- Steve


> 
> >  
> > -	clean_data_set(entry->vals, teval->val_types, teval->nr_val_types);
> > -	entry->vals = new_vals;
> >  	return 0;
> > +
> > +fail:
> > +	data_release(i, old, types);
> > +	return -1;
> >  }
> >  
> >  struct traceeval_stat *traceeval_stat(struct traceeval *teval,
> > -- 
> > 2.40.1
> >   

Re: [PATCH v2 15/17] libtraceeval histogram: Add traceeval_iterator_sort_custom()

[Steven Rostedt]

On Wed, 16 Aug 2023 16:57:16 -0600
Ross Zwisler <zwisler@google.com> wrote:

> > +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);  
> 
> I guess I don't yet see what this gives us over the existing sorting and
> iterators?  Does this do the same thing, we just pass in the sort function
> instead of calling traceeval_iterator_sort() one or more times?

This should be used in replace of the other sorting. It allows the user to
make a complex sort. If you look at the last patch, the sample uses this:

+/*
+ * 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);
+}


> 
> > +
> > +	iter->needs_sort = false;  
> 
> Also probably need to set
>   iter->next = 0;

So much for redundancy!

Thanks,

-- Steve

> 
> > +	return 0;
> > +}
> > +

Re: [PATCH v2 14/17] libtraceeval histogram: Use stack for old copy in update

[Steven Rostedt]

On Wed, 16 Aug 2023 19:12:25 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> On Wed, 16 Aug 2023 16:37:54 -0600
> Ross Zwisler <zwisler@google.com> wrote:
> 
> > On Fri, Aug 11, 2023 at 01:39:37AM -0400, Steven Rostedt wrote:  
> > > 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 | 48 ++++++++++++++++++++++++++++++++++--------------
> > >  1 file changed, 34 insertions(+), 14 deletions(-)
> > >     
> > <>  
> > > @@ -772,20 +778,34 @@ fail_entry:
> > >   *
> > >   * Frees the old vals field of @entry, unless an error occurs.
> > >   *
> > > - * Return 0 on success, -1 on error.
> > > + * Return 1 on success, -1 on error.    
> > 
> > The code is now returning 1, 0 and -1 in different cases, and all three of
> > these return values are percolating up to be returned by traceeval_insert(),
> > which is only supposed to return 0 or 1.
> >   
> 
> I didn't update the comments well. The idea is, return 1 if the element
> already existed, 0 if it did not, and -1 on error. I need to fix this.

Anyway, it this does not belong in this patch. The return value of
traceeval_insert() change should be a separate patch. One that I will add
in another series after this one.

-- Steve

Re: [PATCH v2 14/17] libtraceeval histogram: Use stack for old copy in update

[Steven Rostedt]

On Wed, 16 Aug 2023 19:12:25 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> > > +
> > > +	for (i = 0; i < size; i++) {
> > > +		old[i] = copy[i];
> > > +
> > > +		if (copy_traceeval_data(types + i, stats + i,
> > > +					vals + i, copy + i))
> > > +			goto fail;
> > > +	}    
> > 
> > I think we still need to rip through old[] and free strings, and also call  
> 
> Yes, I forgot to add that :-p 
> 
> > .release on types that define it, probably via data_release().
> > 

I realized I actually had this kind of backwards. On failure, we want to put
back old and remove the data added to vals (aka copy).

Here's what I'm doing:

	for (i = 0; i < size; i++) {
		old[i] = copy[i];

		if (copy_traceeval_data(types + i, stats + i,
					vals + i, copy + 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;

-- Steve