Skip to contentSkip to conversation

histograms: Add query and insert

PATCH Superseded Stevie Alvarez 3 participants 18 messages Aug 8, 2023 – Aug 9, 2023 Kbuild

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 cover histograms: Add query and insert

From: Stevie Alvarez (Google) <[email protected]>

Changes in v3:
* Added traceeval_query() and traceeval_results_release().
* Added traceeval_insert().
* Reordered enum traceeval_data_type for logical numeric use.
* Reordered traceeval_type fields for legibility.
* Removed traceeval_flag's STAT as numerics will aggregate by default.
* Declared traceeval_type before dyn function typedefs.
* Changed dyn_release call's argument to pointer offset for legibility.
* Changed dyn_release signature's argument order for legibility.
* Removed traceeval_iterator since it isn't used.
* Moved type_alloc()'s for-loop's semi-colon to a new line for legibility.
* Made lables less verbose.
* Updated type_alloc's error messages.
* type_alloc() frees allocated data on error instead of traceeval_init().
* Squashed initialize and release patches as init depends on release.
* Capitalized first letter of error messages.
* Added error message for clean_data() if data exists without defs.
* Aligned all function parameters with opening parenthesis.
* Remove compare and testing patches, beyond current scope of project.
---
v2 discussion: https://lore.kernel.org/linux-trace-devel/[email protected]/T/#t

Stevie Alvarez (Google) (6):
histograms: Initial histograms interface
histograms: Add traceeval initialize and release
histograms: Add traceeval compare
histograms: Add traceeval query
histograms: Add traceeval insert
histograms: Initial unit tests

 Makefile                 |   2 +-
 include/traceeval-hist.h | 147 ++++++++
 include/traceeval-test.h |  16 +
 src/Makefile             |   1 +
 src/histograms.c         | 792 +++++++++++++++++++++++++++++++++++++++
 utest/.gitignore         |   1 +
 utest/Makefile           |  35 ++
 utest/eval-test.h        |  13 +
 utest/eval-utest.c       |  28 ++
 utest/traceeval-utest.c  | 290 ++++++++++++++
 10 files changed, 1324 insertions(+), 1 deletion(-)
 create mode 100644 include/traceeval-hist.h
 create mode 100644 include/traceeval-test.h
 create mode 100644 src/histograms.c
 create mode 100644 utest/.gitignore
 create mode 100644 utest/Makefile
 create mode 100644 utest/eval-test.h
 create mode 100644 utest/eval-utest.c
 create mode 100644 utest/traceeval-utest.c
Signature · 1 line
2.41.0
#1 lore raw

PATCH v3 1/6 histograms: Initial histograms interface

From: Stevie Alvarez (Google) <[email protected]>

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

---
 include/traceeval-hist.h | 130 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 130 insertions(+)
 create mode 100644 include/traceeval-hist.h
include/traceeval-hist.h new file +130 -0
new file mode 100644
index 0000000..ebce94e
@@ -0,0 +1,130 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval histogram interface.
+ *
+ * Copyright (C) 2023 Google Inc, Steven Rostedt <[email protected]>
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <[email protected]>
+ */
+#ifndef __LIBTRACEEVAL_HIST_H__
+#define __LIBTRACEEVAL_HIST_H__
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+/* Data definition interfaces */
+
+/* Field name/descriptor for number of hits */
+#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
+
+/* Data type distinguishers */
+enum traceeval_data_type {
+	TRACEEVAL_TYPE_NONE,
+	TRACEEVAL_TYPE_NUMBER_64,
+	TRACEEVAL_TYPE_NUMBER_32,
+	TRACEEVAL_TYPE_NUMBER_16,
+	TRACEEVAL_TYPE_NUMBER_8,
+	TRACEEVAL_TYPE_NUMBER,
+	TRACEEVAL_TYPE_STRING,
+	TRACEEVAL_TYPE_DYNAMIC
+};
+
+/* Statistics specification flags */
+enum traceeval_flags {
+	TRACEEVAL_FL_SIGNED		= (1 << 0),
+	TRACEEVAL_FL_TIMESTAMP		= (1 << 1),
+};
+
+/*
+ * Trace data entry for a traceeval histogram
+ * Constitutes keys and values.
+ */
+union traceeval_data {
+	char				*string;
+	struct traceeval_dynamic	*dyn_data;
+	unsigned long long		number_64;
+	unsigned long			number;
+	unsigned int			number_32;
+	unsigned short			number_16;
+	unsigned char			number_8;
+};
+
+/*
+ * struct traceeval_dynamic - Storage for dynamic traceeval_types
+ * @size: The size of the dynamic type
+ * @data: The pointer to the data of the dynamic type
+ */
+struct traceeval_dynamic {
+	void		*data;
+	size_t		size;
+};
+
+struct traceeval_type;
+
+/* struct traceeval_dynamic release function signature */
+typedef void (*traceeval_dyn_release_fn)(struct traceeval_type *,
+					 struct traceeval_dynamic *);
+
+/* struct traceeval_dynamic compare function signature */
+typedef int (*traceeval_dyn_cmp_fn)(struct traceeval_dynamic *,
+				    struct traceeval_dynamic *,
+				    struct traceeval_type *);
+
+/*
+ * struct traceeval_type - Describes the type of a traceevent_data instance
+ * @type: The enum type that describes the traceeval_data
+ * @name: The string name of the traceeval_data
+ * @flags: flags to describe the traceeval_data
+ * @id: User specified identifier
+ * @dyn_release: For dynamic types called on release (ignored for other types)
+ * @dyn_cmp: A way to compare dynamic types (ignored for other types)
+ *
+ * The traceeval_type structure defines expectations for a corresponding
+ * traceeval_data instance for a traceeval histogram instance. Used to
+ * describe both keys and values.
+ *
+ * The @id field is an optional value in case the user has multiple struct
+ * traceeval_type instances with @type fields set to TRACEEVAL_TYPE_DYNAMIC,
+ * which each relate to distinct user defined struct traceeval_dynamic
+ * 'sub-types'.
+ *
+ * For flexibility, @dyn_cmp() and @dyn_release() take a struct
+ * traceeval_type instance. This allows the user to distinguish between
+ * different sub-types of struct traceeval_dynamic within a single
+ * callback function by examining the @id field. This is not a required
+ * approach, merely one that is accommodated.
+ *
+ * @dyn_cmp() is used to compare two struct traceeval_dynamic instances when a
+ * corresponding struct traceeval_type is reached with its type field set to
+ * TRACEEVAL_TYPE_DYNAMIC. It should return 0 on equality, 1 if the first
+ * argument is greater than the second, -1 for the other way around, and -2 on
+ * error.
+ *
+ * dyn_release() is used during traceeval_release() to release a union
+ * traceeval_data's struct traceeval_dynamic field when the corresponding
+ * traceeval_type type is set to TRACEEVAL_TYPE_DYNAMIC.
+ */
+struct traceeval_type {
+	char				*name;
+	enum traceeval_data_type	type;
+	size_t				flags;
+	size_t				id;
+	traceeval_dyn_release_fn	dyn_release;
+	traceeval_dyn_cmp_fn		dyn_cmp;
+};
+
+/* Statistics about a given entry element */
+struct traceeval_stat {
+	unsigned long long	max;
+	unsigned long long	min;
+	unsigned long long	total;
+	unsigned long long	avg;
+	unsigned long long	std;
+};
+
+/* Iterator over aggregated data */
+struct traceeval_iterator;
+
+struct traceeval;
+
+#endif /* __LIBTRACEEVAL_HIST_H__ */
Signature · 1 line
2.41.0
#2 lore raw

Re: [PATCH v3 1/6] histograms: Initial histograms interface

Quoted 35 lines · On Tue, 8 Aug 2023 12:11:54 -0400 Stevie Alvarez <[email protected]>…

From: Stevie Alvarez (Google) <[email protected]>

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

---
 include/traceeval-hist.h | 130 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 130 insertions(+)
 create mode 100644 include/traceeval-hist.h
include/traceeval-hist.h new file +17 -0
new file mode 100644
index 0000000..ebce94e
@@ -0,0 +1,130 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval histogram interface.
+ *
+ * Copyright (C) 2023 Google Inc, Steven Rostedt <[email protected]>
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <[email protected]>
+ */
+#ifndef __LIBTRACEEVAL_HIST_H__
+#define __LIBTRACEEVAL_HIST_H__
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+/* Data definition interfaces */
+
+/* Field name/descriptor for number of hits */

include/traceeval-hist.h line 26

Quoted 10 lines
include/traceeval-hist.h new file +9 -0
+#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
+
+/* Data type distinguishers */
+enum traceeval_data_type {
+	TRACEEVAL_TYPE_NONE,
 
+	TRACEEVAL_TYPE_NUMBER_64,
+	TRACEEVAL_TYPE_NUMBER_32,
+	TRACEEVAL_TYPE_NUMBER_16,
+	TRACEEVAL_TYPE_NUMBER_8,

Should be the other way around:

TRACEEVAL_TYPE_NUMBER_8,
TRACEEVAL_TYPE_NUMBER_16,
TRACEEVAL_TYPE_NUMBER_32,
TRACEEVAL_TYPE_NUMBER_64,

So that _8 = 1, _16 = 2, _32 = 3 and _64 = 4

Which would allow for the:

2^(1 * (enum - 1))

algorithm.

Quoted 10 lines
include/traceeval-hist.h new file +10 -0
+	TRACEEVAL_TYPE_NUMBER,
+	TRACEEVAL_TYPE_STRING,
+	TRACEEVAL_TYPE_DYNAMIC
+};
+
+/* Statistics specification flags */
+enum traceeval_flags {
+	TRACEEVAL_FL_SIGNED		= (1 << 0),
+	TRACEEVAL_FL_TIMESTAMP		= (1 << 1),
+};

include/traceeval-hist.h line 46

Quoted 10 lines
include/traceeval-hist.h new file +10 -0
+
+/*
+ * Trace data entry for a traceeval histogram
+ * Constitutes keys and values.
+ */
+union traceeval_data {
+	char				*string;
+	struct traceeval_dynamic	*dyn_data;
+	unsigned long long		number_64;
+	unsigned long			number;

As this is a union, order doesn't matter (for sizes). But for aesthetics, perhaps switch the _64 with the number.

	unsigned long			number;
	unsigned long long		number_64;

To keep all the "number_*" together.

include/traceeval-hist.h line 51

Quoted 5 lines
include/traceeval-hist.h new file +5 -0
+	unsigned int			number_32;
+	unsigned short			number_16;
+	unsigned char			number_8;
+};
+

-- Steve

#3 lore raw

Re: [PATCH v3 1/6] histograms: Initial histograms interface

In reply to Stevie Alvarez

include/traceeval-hist.h line 43

Quoted 6 lines · On Tue, 8 Aug 2023 12:11:54 -0400 Stevie Alvarez <[email protected]>…
include/traceeval-hist.h new file +6 -0
+/*
+ * Trace data entry for a traceeval histogram
+ * Constitutes keys and values.
+ */
+union traceeval_data {
+	char				*string;

We need to also add:

	const char			*cstring;

At least for the user interface, as I'm converting task-eval over to this, and I need to assign const strings to this union.

-- Steve

Quoted 8 lines
include/traceeval-hist.h new file +8 -0
+	struct traceeval_dynamic	*dyn_data;
+	unsigned long long		number_64;
+	unsigned long			number;
+	unsigned int			number_32;
+	unsigned short			number_16;
+	unsigned char			number_8;
+};
+
#4 lore raw

Re: [PATCH v3 1/6] histograms: Initial histograms interface

Quoted 12 lines · Steven Rostedt

include/traceeval-hist.h line 43

Quoted 6 lines · On Tue, 8 Aug 2023 12:11:54 -0400 Stevie Alvarez <[email protected]>…
include/traceeval-hist.h new file +6 -0
+/*
+ * Trace data entry for a traceeval histogram
+ * Constitutes keys and values.
+ */
+union traceeval_data {
+	char				*string;

We need to also add:

Quoted 4 lines
	const char			*cstring;

At least for the user interface, as I'm converting task-eval over to this, and I need to assign const strings to this union.

I assume I should treat cstring the same as string, execept because it's constant, it should not be updated on insertion, correct?

-- Stevie

Quoted 11 lines

-- Steve

Quoted 8 lines
include/traceeval-hist.h new file +8 -0
+	struct traceeval_dynamic	*dyn_data;
+	unsigned long long		number_64;
+	unsigned long			number;
+	unsigned int			number_32;
+	unsigned short			number_16;
+	unsigned char			number_8;
+};
+
#5 lore raw

Re: [PATCH v3 1/6] histograms: Initial histograms interface

Quoted 13 lines · On Tue, 8 Aug 2023 17:51:05 -0400 Stevie Alvarez <[email protected]>…
Quoted 12 lines · Steven Rostedt

include/traceeval-hist.h line 43

Quoted 6 lines · On Tue, 8 Aug 2023 12:11:54 -0400 Stevie Alvarez <[email protected]>…
include/traceeval-hist.h new file +6 -0
+/*
+ * Trace data entry for a traceeval histogram
+ * Constitutes keys and values.
+ */
+union traceeval_data {
+	char				*string;  

We need to also add:

Quoted 7 lines
Quoted 4 lines
	const char			*cstring;

At least for the user interface, as I'm converting task-eval over to this, and I need to assign const strings to this union.

I assume I should treat cstring the same as string, execept because it's constant, it should not be updated on insertion, correct?

On insertion we have:

static int copy_traceeval_data(struct traceeval_type *type,
const union traceeval_data *orig, union traceeval_data *copy)

{
	*copy = *orig;

	switch (type->type) {
	case TRACEEVAL_TYPE_STRING:
		copy->string = NULL;
		if (orig->string)
			copy->string = strdup(orig->string);
		if (!copy->string)
			return -1;
		break;

	default:
		break;
	}

	return 0;
}

So we copy it. That means we really can do whatever we want to it.

-- Steve

#6 lore raw

Re: [PATCH v3 1/6] histograms: Initial histograms interface

In reply to Stevie Alvarez
Quoted 52 lines · On Tue, 8 Aug 2023 12:11:54 -0400 Stevie Alvarez <[email protected]>…

From: Stevie Alvarez (Google) <[email protected]>

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

---
 include/traceeval-hist.h | 130 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 130 insertions(+)
 create mode 100644 include/traceeval-hist.h
include/traceeval-hist.h new file +34 -0
new file mode 100644
index 0000000..ebce94e
@@ -0,0 +1,130 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval histogram interface.
+ *
+ * Copyright (C) 2023 Google Inc, Steven Rostedt <[email protected]>
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <[email protected]>
+ */
+#ifndef __LIBTRACEEVAL_HIST_H__
+#define __LIBTRACEEVAL_HIST_H__
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+/* Data definition interfaces */
+
+/* Field name/descriptor for number of hits */
+#define TRACEEVAL_VAL_HITS ((const char *)(-1UL))
+
+/* Data type distinguishers */
+enum traceeval_data_type {
+	TRACEEVAL_TYPE_NONE,
+	TRACEEVAL_TYPE_NUMBER_64,
+	TRACEEVAL_TYPE_NUMBER_32,
+	TRACEEVAL_TYPE_NUMBER_16,
+	TRACEEVAL_TYPE_NUMBER_8,
+	TRACEEVAL_TYPE_NUMBER,
+	TRACEEVAL_TYPE_STRING,
+	TRACEEVAL_TYPE_DYNAMIC
+};
+
+/* Statistics specification flags */
+enum traceeval_flags {
+	TRACEEVAL_FL_SIGNED		= (1 << 0),

include/traceeval-hist.h line 44

Quoted 10 lines
include/traceeval-hist.h new file +10 -0
+	TRACEEVAL_FL_TIMESTAMP		= (1 << 1),
+};
+
+/*
+ * Trace data entry for a traceeval histogram
+ * Constitutes keys and values.
+ */
+union traceeval_data {
+	char				*string;
+	struct traceeval_dynamic	*dyn_data;

I think the above should be:

	struct traceeval_dynamic	dyn_data;

and not a pointer. Otherwise it really does not give us any benefit having it be anything but a pointer.

That is, keeping it a pointer is as useful as:

	void				*dyn_data;

Which is fine, but we need to do one or the other.

-- Steve

Quoted 7 lines
include/traceeval-hist.h new file +7 -0
+	unsigned long long		number_64;
+	unsigned long			number;
+	unsigned int			number_32;
+	unsigned short			number_16;
+	unsigned char			number_8;
+};
+
#7 lore raw

PATCH v3 2/6 histograms: Add traceeval initialize and release

In reply to Stevie Alvarez

From: Stevie Alvarez (Google) <[email protected]>

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

traceeval_init() uses traceeval_release() and it's helper functions to clean up on error.

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

---
 Makefile                 |   2 +-
 include/traceeval-hist.h |   7 +
 src/Makefile             |   1 +
 src/histograms.c         | 310 +++++++++++++++++++++++++++++++++++++++
 4 files changed, 319 insertions(+), 1 deletion(-)
 create mode 100644 src/histograms.c
Makefile +1 -1
index 4a24d5a..3ea051c 100644
@@ -172,7 +172,7 @@ libs: $(LIBRARY_A) $(LIBRARY_SO)
 
 VALGRIND = $(shell which valgrind)
 UTEST_DIR = utest
-UTEST_BINARY = trace-utest
+UTEST_BINARY = eval-utest
 
 test: force $(LIBRARY_STATIC)
 ifneq ($(CUNIT_INSTALLED),1)
include/traceeval-hist.h +7 -0
index ebce94e..5203520 100644
@@ -127,4 +127,11 @@ struct traceeval_iterator;
 
 struct traceeval;
 
+/* Histogram interfaces */
+
+struct traceeval *traceeval_init(const struct traceeval_type *keys,
+				 const struct traceeval_type *vals);
+
+void traceeval_release(struct traceeval *teval);
+
 #endif /* __LIBTRACEEVAL_HIST_H__ */
src/Makefile +1 -0
index b4b6e52..b32a389 100644
@@ -4,6 +4,7 @@ include $(src)/scripts/utils.mk
 
 OBJS =
 OBJS += trace-analysis.o
+OBJS += histograms.o
 
 OBJS := $(OBJS:%.o=$(bdir)/%.o)
 
src/histograms.c new file +310 -0

310 lines not on this page · raw message

Signature · 1 line
2.41.0
#8 lore raw

Re: [PATCH v3 2/6] histograms: Add traceeval initialize and release

Quoted 33 lines · On Tue, 8 Aug 2023 12:11:55 -0400 Stevie Alvarez <[email protected]>…
src/histograms.c new file +27 -0
new file mode 100644
index 0000000..b85d1a8
@@ -0,0 +1,310 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval histogram interface implementation.
+ *
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <[email protected]>
+ */
+
+#include <stdbool.h>
+#include <string.h>
+#include <stdarg.h>
+#include <stdio.h>
+
+#include <traceeval-hist.h>
+
+/* A key-value pair */
+struct entry {
+	union traceeval_data	*keys;
+	union traceeval_data	*vals;
+};
+
+/* A table of key-value entries */
+struct hist_table {
+	struct entry	*map;
+	size_t		nr_entries;
+};
+
+/* Histogram */

src/histograms.c line 37

Quoted 10 lines
src/histograms.c new file +10 -0
+struct traceeval {
+	struct traceeval_type		*key_types;
+	struct traceeval_type		*val_types;
+	struct hist_table		*hist;
+	size_t				nr_key_types;
+	size_t				nr_val_types;
+};
+
+/*
+ * print_err() - print an error message

Nit, for kerneldoc format, you don't need the parenthesis:

* print_err - print an error message

is the way to write it. Same for the rest.

Quoted 57 lines
src/histograms.c new file +57 -0
+ * @fmt: String format
+ * @...: (optional) Additional arguments to print in conjunction with @format
+ */
+static void print_err(const char *fmt, ...)
+{
+	va_list ap;
+
+	va_start(ap, fmt);
+	vfprintf(stderr, fmt, ap);
+	va_end(ap);
+	fprintf(stderr, "\n");
+}
+
+/*
+ * type_release() - free a struct traceeval_type array
+ * @defs: The array to release
+ * @len: The length of @defs
+ *
+ * It is assumed that all elements of @defs, within the length of @len, have
+ * name fields initialized to valid pointers.
+ *
+ * This function was designed to be used on an array allocated by type_alloc().
+ * Note that type_alloc() initializes all name fields of elements within the
+ * returned size.
+ */
+static void type_release(struct traceeval_type *defs, size_t len)
+{
+	if (!defs)
+		return;
+
+	for (size_t i = 0; i < len; i++) {
+		free(defs[i].name);
+	}
+
+	free(defs);
+}
+
+/*
+ * type_alloc() - clone a struct traceeval_type array
+ * @defs: The original array
+ * @copy: A pointer to where to place the @defs copy
+ *
+ * Clone traceeval_type array @defs to the heap, and place in @copy.
+ * @defs must be terminated with an instance of type TRACEEVAL_TYPE_NONE.
+ *
+ * The size of the copy pointed to by @copy is returned. It counts all elements
+ * in @defs excluding the terminating TRACEEVAL_TYPE_NONE traceeval_type.
+ * The copy contains everything from @defs excluding the TRACEEVAL_TYPE_NONE
+ * traceeval_type.
+ * On error, copy is set to point to NULL.
+ *
+ * The name field of each element of @defs (except for the terminating
+ * TRACEEVAL_TYPE_NONE) must be a NULL-terminated string. The validity of the
+ * name field is not checked, but errors are returned upon finding unset name
+ * fields and string duplication failures. It is guaranteed that all elements
+ * of the copy within the returned size have valid pointers in their name
+ * fields.

src/histograms.c line 104

Quoted 10 lines
src/histograms.c new file +10 -0
+ *
+ * Returns the size of the array pointed to by @copy, or -1 on error.
+ */
+static size_t type_alloc(const struct traceeval_type *defs,
+			 struct traceeval_type **copy)
+{
+	struct traceeval_type *new_defs = NULL;
+	size_t size;
+	size_t i;
+

BTW, for something like this I would just start off with:

	*copy = NULL;

src/histograms.c line 108

Quoted 4 lines
src/histograms.c new file +4 -0
+	if (!defs) {
+		*copy = NULL;
+		return 0;
+	}

And the above can be:

	if (!defs)
		return 0;

src/histograms.c line 118

Quoted 10 lines
src/histograms.c new file +10 -0
+
+	for (size = 0; defs && defs[size].type != TRACEEVAL_TYPE_NONE; size++)
+		;
+
+	if (size) {
+		new_defs = calloc(size, sizeof(*new_defs));
+	} else {
+		*copy = NULL;
+		return 0;
+	}

and the above can be:

	if (!size)
		return 0;

	new_defs = calloc(size, sizeof(*new_defs));
Quoted 18 lines
src/histograms.c new file +18 -0
+
+	for (i = 0; i < size; i++) {
+		/* copy current def data to new_def */
+		new_defs[i] = defs[i];
+
+		/* copy name to heap, ensures name copied */
+		if (!defs[i].name)
+			goto fail;
+		new_defs[i].name = strdup(defs[i].name);
+
+		if (!new_defs[i].name)
+			goto fail;
+	}
+
+	*copy = new_defs;
+	return size;
+
+fail:

src/histograms.c line 145

Quoted 10 lines
src/histograms.c new file +9 -0
+	if (defs[i].name)
+		print_err("Failed to allocate traceeval_type %zu", size);
+	else
+		print_err("traceeval_type list missing a name");
+
+	for (; i >=0; i--)
+		free(new_defs[i].name);
+	free(new_defs);
 
+	*copy = NULL;

And no need for the *copy = NULL; as it was done at the beginning.

src/histograms.c line 148

Quoted 3 lines
src/histograms.c new file +3 -0
+	return -1;
+}
+

-- Steve

#9 lore raw

PATCH v3 3/6 histograms: Add traceeval compare

In reply to Stevie Alvarez

From: Stevie Alvarez (Google) <[email protected]>

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

---
 include/traceeval-test.h |  16 +++
 src/histograms.c         | 213 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 229 insertions(+)
 create mode 100644 include/traceeval-test.h
include/traceeval-test.h new file +16 -0
new file mode 100644
index 0000000..bb8092a
@@ -0,0 +1,16 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval interface for unit testing.
+ *
+ * Copyright (C) 2023 Google Inc, Steven Rostedt <[email protected]>
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <[email protected]>
+ */
+
+#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__ */
src/histograms.c +213 -0

225 lines not on this page · raw message

Signature · 1 line
2.41.0
#10 lore raw

Re: [PATCH v3 3/6] histograms: Add traceeval compare

Quoted 39 lines · On Tue, 8 Aug 2023 12:11:56 -0400 Stevie Alvarez <[email protected]>…

From: Stevie Alvarez (Google) <[email protected]>

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

---
 include/traceeval-test.h |  16 +++
 src/histograms.c         | 213 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 229 insertions(+)
 create mode 100644 include/traceeval-test.h
include/traceeval-test.h new file +16 -0
new file mode 100644
index 0000000..bb8092a
@@ -0,0 +1,16 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * libtraceeval interface for unit testing.
+ *
+ * Copyright (C) 2023 Google Inc, Steven Rostedt <[email protected]>
+ * Copyright (C) 2023 Google Inc, Stevie Alvarez <[email protected]>
+ */
+
+#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__ */
src/histograms.c +0 -0
index b85d1a8..6fac205 100644

src/histograms.c line 14

Quoted 4 lines
src/histograms.c +1 -0
@@ -11,6 +11,20 @@
 #include <stdio.h>
 
 #include <traceeval-hist.h>
+#include <traceeval-test.h>

Note, for anything that is not going to be installed in the system, I prefer to use "" includes. It lets you know that it's local to the repo.

#include <traceeval-hist.h>

#include "traceeval-test.h"

-- Steve

Quoted 20 lines
src/histograms.c +13 -0
+
+/*
+ * Compare two integers of variable length.
+ *
+ * Return 0 if @a and @b are the same, 1 if @a is greater than @b, and -1
+ * if @b is greater than @a.
+ */
+#define compare_numbers_return(a, b)	\
+do {					\
+	if ((a) < (b))			\
+		return -1;		\
+	return (a) != (b);		\
+} while (0)				\
 
 /* A key-value pair */
 struct entry {
@@ -48,6 +62,205 @@ static void print_err(const char *fmt, ...)
 	fprintf(stderr, "\n");
 }
 
#11 lore raw

PATCH v3 4/6 histograms: Add traceeval query

In reply to Stevie Alvarez

From: Stevie Alvarez (Google) <[email protected]>

traceeval_query() fetches the values (aka results) of an entry with keys that match the array of keys provided. The results of a query can be useful for aggregating data between entries/trace events.

traceeval_results_release() frees the results fetched by the query. The user must free the results of a successful query.

---
 include/traceeval-hist.h |   6 ++
 src/histograms.c         | 163 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 169 insertions(+)
include/traceeval-hist.h +6 -0
index 5203520..4923de1 100644
@@ -134,4 +134,10 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
 
 void traceeval_release(struct traceeval *teval);
 
+int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
+		    union traceeval_data **results);
+
+void traceeval_results_release(struct traceeval *teval,
+			       union traceeval_data *results);
+
 #endif /* __LIBTRACEEVAL_HIST_H__ */
src/histograms.c +163 -0

166 lines not on this page · raw message

Signature · 1 line
2.41.0
#12 lore raw

Re: [PATCH v3 4/6] histograms: Add traceeval query

Quoted 35 lines · On Tue, 8 Aug 2023 12:11:57 -0400 Stevie Alvarez <[email protected]>…

From: Stevie Alvarez (Google) <[email protected]>

traceeval_query() fetches the values (aka results) of an entry with keys that match the array of keys provided. The results of a query can be useful for aggregating data between entries/trace events.

traceeval_results_release() frees the results fetched by the query. The user must free the results of a successful query.

---
 include/traceeval-hist.h |   6 ++
 src/histograms.c         | 163 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 169 insertions(+)
include/traceeval-hist.h +6 -0
index 5203520..4923de1 100644
@@ -134,4 +134,10 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
 
 void traceeval_release(struct traceeval *teval);
 
+int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
+		    union traceeval_data **results);
+
+void traceeval_results_release(struct traceeval *teval,
+			       union traceeval_data *results);
+
 #endif /* __LIBTRACEEVAL_HIST_H__ */
src/histograms.c +0 -0
index 6fac205..47ff175 100644

src/histograms.c void traceeval_release(struct traceeval *teval) · line 528

Quoted 8 lines
src/histograms.c +5 -0
@@ -521,3 +521,166 @@ void traceeval_release(struct traceeval *teval)
 	teval->val_types = NULL;
 	free(teval);
 }
+
+/*
+ * Find the entry that @keys corresponds to within @teval.
+ *
+ * Returns 0 on success, 1 if no match found, -1 on error.

Ideally, it would be 1 if found, 0 if not found and -1 on error.

But I guess you did it this way to short circuit the check below, but that doesn't match either.

src/histograms.c void traceeval_release(struct traceeval *teval) · line 535

Quoted 7 lines
src/histograms.c +7 -0
+ */
+static int get_entry(struct traceeval *teval, const union traceeval_data *keys,
+		     struct entry **result)
+{
+	struct hist_table *hist;
+	int i;
+	int check;

Upside-down x-mas tree format :-)

	struct hist_table *hist;
	struct entry;
	int check = 0;
	int i;

There's a reason I set check to zero.

src/histograms.c void traceeval_release(struct traceeval *teval) · line 542

Quoted 9 lines
src/histograms.c +7 -0
+
+	if (!teval || !keys)
+		return -1;
+
+	hist = teval->hist;
 
 
+	i = 0;
+	for (struct entry *entry = hist->map; i < hist->nr_entries;

Do not declare complex variables in for loops. Makes them much harder to read.

	for (i = 0, entry = hist->map; i < hist->nr_entries; entry = &hist->map[++i])

src/histograms.c void traceeval_release(struct traceeval *teval) · line 543

Quoted 1 line
src/histograms.c +1 -0
+			entry = &hist->map[++i]) {

Probably want to optimize this with a hash anyway, especially since the code will likely have hundreds of keys and do thousands of lookups.

src/histograms.c void traceeval_release(struct traceeval *teval) · line 544

Quoted 1 line
src/histograms.c +1 -0
+		check = compare_traceeval_data_set(entry->keys, keys,

compare_traceeval_data_set() should return 1 on found, zero on not found and -1 on error.

src/histograms.c

Quoted 2 lines
src/histograms.c +2 -0
+				teval->key_types, teval->nr_key_types);
+

We can then have:

		if (!check)
			continue;

		break;

src/histograms.c void traceeval_release(struct traceeval *teval) · line 556

Quoted 10 lines
src/histograms.c +10 -0
+		/* return entry if keys match */
+		if (!check) {
+			*result = entry;
+			return 0;
+		} else if (check == 1) {
+			continue;
+		} else {
+			return check;
+		}
+	}
	if (check > 0)
		*result = entry;

	return check;
Quoted 81 lines
src/histograms.c +81 -0
+
+	return 1;
+}
+
+/*
+ * Copy @orig to @copy with respect to @type.
+ *
+ * Return 0 on success, -1 on error.
+ */
+static int copy_traceeval_data(struct traceeval_type *type,
+				const union traceeval_data *orig,
+				union traceeval_data *copy)
+{
+	*copy = *orig;
+
+	switch (type->type) {
+	case TRACEEVAL_TYPE_STRING:
+		copy->string = NULL;
+		if (orig->string)
+			copy->string = strdup(orig->string);
+		if (!copy->string)
+			return -1;
+		break;
+
+	default:
+		break;
+	}
+
+	return 0;
+}
+
+/*
+ * Free @data with respect to @size and @type.
+ *
+ * Does not call dyn_release on type TRACEEVAL_TYPE_DYNAMIC.
+ */
+static void data_release(size_t size, union traceeval_data **data,
+				struct traceeval_type *type)
+{
+	for (size_t i = 0; i < size; i++) {
+		if (type[i].type == TRACEEVAL_TYPE_STRING)
+			free((*data)[i].string);
+	}
+	free(*data);
+	*data = NULL;
+}
+
+/*
+ * Copy @orig to @copy with respect to @size and @type.
+ *
+ * Returns 1 on success, -1 on error.
+ */
+static int copy_traceeval_data_set(size_t size, struct traceeval_type *type,
+				    const union traceeval_data *orig,
+				    union traceeval_data **copy)
+{
+	size_t i;
+
+	*copy = calloc(size, sizeof(**copy));
+	if (!*copy)
+		return -1;
+
+	for (i = 0; i < size; i++) {
+		if (copy_traceeval_data(type + i, orig + i, (*copy) + i))
+			goto fail;
+	}
+
+	return 1;
+
+fail:
+	data_release(i, copy, type);
+	return -1;
+}
+
+
+/*
+ * traceeval_query - find the last instance defined by the keys
+ * @teval: The descriptor to search from
+ * @keys: A list of data to look for
+ * @results: A pointer to where to place the results (if found)
+ *

src/histograms.c void traceeval_release(struct traceeval *teval) · line 647

Quoted 10 lines
src/histograms.c +10 -0
+ * This does a lookup for an instance within the traceeval data.
+ * The @keys is an array defined by the keys declared in traceeval_init().
+ * The @keys will return an item that had the same keys when it was
+ * inserted by traceeval_insert(). The @keys here follow the same rules
+ * as the keys for traceeval_insert().
+ *
+ * Note, when the caller is done with @results, it must call
+ * traceeval_results_release() on it.
+ *
+ * Returns 1 if found, 0 if not found, and -1 on error.

The above is what I would agree on, but does not follow below.

src/histograms.c void traceeval_release(struct traceeval *teval) · line 659

Quoted 12 lines

+ */

src/histograms.c +11 -0
+int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
+		    union traceeval_data **results)
+{
+	struct entry *entry;
+	int check;
+
+	if (!teval || !keys || !results)
+		return -1;
+
+	/* find key and copy its corresponding value pair */
+	if ((check = get_entry(teval, keys, &entry)))

If get_entry() returns 1 on match and 0 if not, and -1 on error, I think we want this to be:

if ((check = get_entry(teval, keys, &entry) < 1)

src/histograms.c

Quoted 1 line
src/histograms.c +1 -0
+		return check;

Right now it returns 1 on not found.

-- Steve

Quoted 26 lines
src/histograms.c +26 -0
+	return copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
+			entry->vals, results);
+}
+
+/*
+ * traceeval_results_release - release the results return by traceeval_query()
+ * @teval: The descriptor used in traceeval_query()
+ * @results: The results returned by traceeval_query()
+ *
+ * The @results returned by traceeval_query() is owned by @teval, and
+ * how it manages it is implementation specific. The caller should not
+ * worry about it. When the caller of traceeval_query() is done with
+ * the @results, it must call traceeval_results_release() on it to
+ * allow traceeval to clean up its references.
+ */
+void traceeval_results_release(struct traceeval *teval,
+			       union traceeval_data *results)
+{
+	if (!teval || !results) {
+		if (!results)
+			print_err("Results to be freed without accompanied traceeval instance!");
+		return;
+	}
+
+	data_release(teval->nr_val_types, &results, teval->val_types);
+}
#13 lore raw

PATCH v3 5/6 histograms: Add traceeval insert

In reply to Stevie Alvarez

From: Stevie Alvarez (Google) <[email protected]>

traceeval_insert() updates the provided struct traceeval's histogram. If an entry that exists with a keys field that match the keys argument, the entries vals field are updated with a copy of the vals argument. If such an entry does not exist, a new entry is added to the histogram, with respect to the keys and vals arguments.

---
 include/traceeval-hist.h |   4 ++
 src/histograms.c         | 106 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 110 insertions(+)
include/traceeval-hist.h +4 -0
index 4923de1..e713c70 100644
@@ -134,6 +134,10 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
 
 void traceeval_release(struct traceeval *teval);
 
+int traceeval_insert(struct traceeval *teval,
+		     const union traceeval_data *keys,
+		     const union traceeval_data *vals);
+
 int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 		    union traceeval_data **results);
 
src/histograms.c +106 -0

109 lines not on this page · raw message

Signature · 1 line
2.41.0
#14 lore raw

Re: [PATCH v3 5/6] histograms: Add traceeval insert

Quoted 85 lines · Stevie Alvarez

From: Stevie Alvarez (Google) <[email protected]>

traceeval_insert() updates the provided struct traceeval's histogram. If an entry that exists with a keys field that match the keys argument, the entries vals field are updated with a copy of the vals argument. If such an entry does not exist, a new entry is added to the histogram, with respect to the keys and vals arguments.

---
 include/traceeval-hist.h |   4 ++
 src/histograms.c         | 106 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 110 insertions(+)
include/traceeval-hist.h +4 -0
index 4923de1..e713c70 100644
@@ -134,6 +134,10 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
 
 void traceeval_release(struct traceeval *teval);
 
+int traceeval_insert(struct traceeval *teval,
+		     const union traceeval_data *keys,
+		     const union traceeval_data *vals);
+
 int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 		    union traceeval_data **results);
 
src/histograms.c +48 -0
index 47ff175..a59542a 100644
@@ -684,3 +684,109 @@ void traceeval_results_release(struct traceeval *teval,
 
 	data_release(teval->nr_val_types, &results, teval->val_types);
 }
+
+/*
+ * Create a new entry in @teval with respect to @keys and @vals.
+ *
+ * Returns 0 on success, -1 on error.
+ */
+static int create_entry(struct traceeval *teval,
+			const union traceeval_data *keys,
+			const union traceeval_data *vals)
+{
+	union traceeval_data *new_keys;
+	union traceeval_data *new_vals;
+	struct entry *tmp_map;
+	struct hist_table *hist = teval->hist;
+
+	/* copy keys */
+	if (copy_traceeval_data_set(teval->nr_key_types, teval->key_types,
+				keys, &new_keys) == -1)
+		return -1;
+
+	/* copy vals */
+	if (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
+				vals, &new_vals) == -1)
+		goto fail_vals;
+
+	/* create new entry */
+	tmp_map = realloc(hist->map, ++hist->nr_entries * sizeof(*tmp_map));
+	if (!tmp_map)
+		goto fail;
+	tmp_map->keys = new_keys;
+	tmp_map->vals = new_vals;
+	hist->map = tmp_map;
+
+	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);
+	return -1;
+}
+
+/*
+ * Update @entry's vals field with a copy of @vals, with respect to @teval.
+ *
+ * Return 0 on success, -1 on error.
+ */

src/histograms.c void traceeval_results_release(struct traceeval *teval, · line 744

Quoted 10 lines
src/histograms.c +10 -0
+static int update_entry(struct traceeval *teval, struct entry *entry,
+			const union traceeval_data *vals)
+{
+	union traceeval_data *new_vals;
+
+	if (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
+				vals, &new_vals) == -1)
+		return -1;
+
+	entry->vals = new_vals;

Are we leaking the old 'entry->vals', as we never free that memory anywhere?

Should we just update in-place, instead of allocating a new one & freeing the old? The vals arrays should each be the same size because they have a common 'teval->val_types'.

I know 'vals' is owned by the caller, but we allocated and own 'entry->vals' via a previous call to create_entry().

We'll have to free existing strings & allocate new ones (and do something similar for dynamic types when they're supported), but the rest of 'entry->vals' should be reusable I think.

Quoted 51 lines
src/histograms.c +48 -0
+	return 0;
+}
+
+/*
+ * traceeval_insert - insert an item into the traceeval descriptor
+ * @teval: The descriptor to insert into
+ * @keys: The list of keys that defines what is being inserted.
+ * @vals: The list of values that defines what is being inserted.
+ *
+ * The @keys is an array that holds the data in the order of the keys
+ * passed into traceeval_init(). That is, if traceeval_init() had
+ * keys = { { .type = TRACEEVAL_STRING }, { .type = TRACEEVAL_NUMBER_8 },
+ * { .type = TRACEEVAL_NONE } }; then the @keys array passed in must
+ * be a string (char *) followed by a 8 byte number (char).
+ *
+ * The @keys and @vals are only examined to where it expects data. That is,
+ * if the traceeval_init() keys had 3 items where the first two was defining
+ * data, and the last one was the TRACEEVAL_TYPE_NONE, then the @keys
+ * here only needs to be an array of 2, inserting the two items defined
+ * by traceeval_init(). The same goes for @vals.
+ *
+ * For all elements of @keys and @vals that correspond to a struct
+ * traceeval_type of type TRACEEVAL_TYPE_STRING, the string field must be set
+ * a valid pointer or NULL.
+ *
+ * On error, @teval is left unchanged.
+ *
+ * Returns 0 on success, and -1 on error.
+ */
+int traceeval_insert(struct traceeval *teval,
+		     const union traceeval_data *keys,
+		     const union traceeval_data *vals)
+{
+	struct entry *entry;
+	int check;
+
+	entry = NULL;
+	check = get_entry(teval, keys, &entry);
+
+	if (check == -1)
+		return check;
+
+	/* insert key-value pair */
+	if (check)
+		return create_entry(teval, keys, vals);
+	else
+		return update_entry(teval, entry, vals);
+}
Signature · 1 line
2.41.0
#15 lore raw

Re: [PATCH v3 5/6] histograms: Add traceeval insert

Quoted 90 lines · Ross Zwisler
Quoted 89 lines · Stevie Alvarez

From: Stevie Alvarez (Google) <[email protected]>

traceeval_insert() updates the provided struct traceeval's histogram. If an entry that exists with a keys field that match the keys argument, the entries vals field are updated with a copy of the vals argument. If such an entry does not exist, a new entry is added to the histogram, with respect to the keys and vals arguments.

---
 include/traceeval-hist.h |   4 ++
 src/histograms.c         | 106 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 110 insertions(+)
include/traceeval-hist.h +4 -0
index 4923de1..e713c70 100644
@@ -134,6 +134,10 @@ struct traceeval *traceeval_init(const struct traceeval_type *keys,
 
 void traceeval_release(struct traceeval *teval);
 
+int traceeval_insert(struct traceeval *teval,
+		     const union traceeval_data *keys,
+		     const union traceeval_data *vals);
+
 int traceeval_query(struct traceeval *teval, const union traceeval_data *keys,
 		    union traceeval_data **results);
 
src/histograms.c +52 -0
index 47ff175..a59542a 100644
@@ -684,3 +684,109 @@ void traceeval_results_release(struct traceeval *teval,
 
 	data_release(teval->nr_val_types, &results, teval->val_types);
 }
+
+/*
+ * Create a new entry in @teval with respect to @keys and @vals.
+ *
+ * Returns 0 on success, -1 on error.
+ */
+static int create_entry(struct traceeval *teval,
+			const union traceeval_data *keys,
+			const union traceeval_data *vals)
+{
+	union traceeval_data *new_keys;
+	union traceeval_data *new_vals;
+	struct entry *tmp_map;
+	struct hist_table *hist = teval->hist;
+
+	/* copy keys */
+	if (copy_traceeval_data_set(teval->nr_key_types, teval->key_types,
+				keys, &new_keys) == -1)
+		return -1;
+
+	/* copy vals */
+	if (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
+				vals, &new_vals) == -1)
+		goto fail_vals;
+
+	/* create new entry */
+	tmp_map = realloc(hist->map, ++hist->nr_entries * sizeof(*tmp_map));
+	if (!tmp_map)
+		goto fail;
+	tmp_map->keys = new_keys;
+	tmp_map->vals = new_vals;
+	hist->map = tmp_map;
+
+	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);
+	return -1;
+}
+
+/*
+ * Update @entry's vals field with a copy of @vals, with respect to @teval.
+ *
+ * Return 0 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;
Quoted 8 lines

src/histograms.c void traceeval_results_release(struct traceeval *teval, · line 744

Quoted 6 lines
src/histograms.c +6 -0
+
+	if (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
+				vals, &new_vals) == -1)
+		return -1;
+
+	entry->vals = new_vals;

Are we leaking the old 'entry->vals', as we never free that memory anywhere?

Thanks for catching this!

Quoted 11 lines

Should we just update in-place, instead of allocating a new one & freeing the old? The vals arrays should each be the same size because they have a common 'teval->val_types'.

I know 'vals' is owned by the caller, but we allocated and own 'entry->vals' via a previous call to create_entry().

We'll have to free existing strings & allocate new ones (and do something similar for dynamic types when they're supported), but the rest of 'entry->vals' should be reusable I think.

My worry about doing this in place is we can't guarantee the operation to be atomic if an error occurs when trying to copy a string. Take the following traceeval instance for example...

	teval->val_types = {
		{ .type = TRACEEVAL_TYPE_STRING },
		{ .type = TRACEEVAL_TYPE_STRING },
		{ .type = TRACEEVAL_TYPE_NONE }
	}

Say an entry is being updated, and we've freed the first string and placed a copy of the new string in its place. We then move on to the second string; we attempt to make a copy of the new string, but it fails, leaving the state changed.
Of course, we can keep track of all the original strings and free them at the very end. Is that more efficient than copying the new vals, freeing entry->vals via clean_data(), and then assigning the new vals to entry->vals? My immediate response is that the in place approach is just as good as the later, but I could be thinking about this the wrong way. Is my logic here sound? Thoughts?

-- Stevie

Quoted 52 lines
Quoted 52 lines
src/histograms.c +48 -0
+	return 0;
+}
+
+/*
+ * traceeval_insert - insert an item into the traceeval descriptor
+ * @teval: The descriptor to insert into
+ * @keys: The list of keys that defines what is being inserted.
+ * @vals: The list of values that defines what is being inserted.
+ *
+ * The @keys is an array that holds the data in the order of the keys
+ * passed into traceeval_init(). That is, if traceeval_init() had
+ * keys = { { .type = TRACEEVAL_STRING }, { .type = TRACEEVAL_NUMBER_8 },
+ * { .type = TRACEEVAL_NONE } }; then the @keys array passed in must
+ * be a string (char *) followed by a 8 byte number (char).
+ *
+ * The @keys and @vals are only examined to where it expects data. That is,
+ * if the traceeval_init() keys had 3 items where the first two was defining
+ * data, and the last one was the TRACEEVAL_TYPE_NONE, then the @keys
+ * here only needs to be an array of 2, inserting the two items defined
+ * by traceeval_init(). The same goes for @vals.
+ *
+ * For all elements of @keys and @vals that correspond to a struct
+ * traceeval_type of type TRACEEVAL_TYPE_STRING, the string field must be set
+ * a valid pointer or NULL.
+ *
+ * On error, @teval is left unchanged.
+ *
+ * Returns 0 on success, and -1 on error.
+ */
+int traceeval_insert(struct traceeval *teval,
+		     const union traceeval_data *keys,
+		     const union traceeval_data *vals)
+{
+	struct entry *entry;
+	int check;
+
+	entry = NULL;
+	check = get_entry(teval, keys, &entry);
+
+	if (check == -1)
+		return check;
+
+	/* insert key-value pair */
+	if (check)
+		return create_entry(teval, keys, vals);
+	else
+		return update_entry(teval, entry, vals);
+}
Signature · 1 line
2.41.0
#16 lore raw

Re: [PATCH v3 5/6] histograms: Add traceeval insert

Quoted 16 lines · Stevie Alvarez
Quoted 15 lines · Ross Zwisler
Quoted 14 lines · Stevie Alvarez

From: Stevie Alvarez (Google) <[email protected]>

traceeval_insert() updates the provided struct traceeval's histogram. If an entry that exists with a keys field that match the keys argument, the entries vals field are updated with a copy of the vals argument. If such an entry does not exist, a new entry is added to the histogram, with respect to the keys and vals arguments.

---
 include/traceeval-hist.h |   4 ++
 src/histograms.c         | 106 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 110 insertions(+)
Quoted 4 lines
Quoted 4 lines

include/traceeval-hist.h

Quoted 4 lines
include/traceeval-hist.h +0 -0
index 4923de1..e713c70 100644

<>

Quoted 41 lines
Quoted 9 lines
Quoted 9 lines
include/traceeval-hist.h +9 -0
+/*
+ * Update @entry's vals field with a copy of @vals, with respect to @teval.
+ *
+ * Return 0 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;
Quoted 8 lines

include/traceeval-hist.h

Quoted 6 lines
include/traceeval-hist.h +6 -0
+
+	if (copy_traceeval_data_set(teval->nr_val_types, teval->val_types,
+				vals, &new_vals) == -1)
+		return -1;
+
+	entry->vals = new_vals;

Are we leaking the old 'entry->vals', as we never free that memory anywhere?

Thanks for catching this!

Quoted 11 lines

Should we just update in-place, instead of allocating a new one & freeing the old? The vals arrays should each be the same size because they have a common 'teval->val_types'.

I know 'vals' is owned by the caller, but we allocated and own 'entry->vals' via a previous call to create_entry().

We'll have to free existing strings & allocate new ones (and do something similar for dynamic types when they're supported), but the rest of 'entry->vals' should be reusable I think.

My worry about doing this in place is we can't guarantee the operation to be atomic if an error occurs when trying to copy a string. Take the following traceeval instance for example...

	teval->val_types = {
		{ .type = TRACEEVAL_TYPE_STRING },
		{ .type = TRACEEVAL_TYPE_STRING },
		{ .type = TRACEEVAL_TYPE_NONE }
	}
Quoted 10 lines

Say an entry is being updated, and we've freed the first string and placed a copy of the new string in its place. We then move on to the second string; we attempt to make a copy of the new string, but it fails, leaving the state changed.
Of course, we can keep track of all the original strings and free them at the very end. Is that more efficient than copying the new vals, freeing entry->vals via clean_data(), and then assigning the new vals to entry->vals? My immediate response is that the in place approach is just as good as the later, but I could be thinking about this the wrong way. Is my logic here sound? Thoughts?

Sure, that concern makes sense to me. Keeping track of all the original vals seems complex, and I agree that just making a new 'vals' from scratch and then freeing the old is fine. This will let us re-use the free path we already have in 'clean_data()' which is preferable to having 2 separate cleanup paths.

#17 lore raw
In reply to Stevie Alvarez
Quoted 24 lines · Stevie Alvarez

From: Stevie Alvarez (Google) <[email protected]>

Changes in v3:
* Added traceeval_query() and traceeval_results_release().
* Added traceeval_insert().
* Reordered enum traceeval_data_type for logical numeric use.
* Reordered traceeval_type fields for legibility.
* Removed traceeval_flag's STAT as numerics will aggregate by default.
* Declared traceeval_type before dyn function typedefs.
* Changed dyn_release call's argument to pointer offset for legibility.
* Changed dyn_release signature's argument order for legibility.
* Removed traceeval_iterator since it isn't used.
* Moved type_alloc()'s for-loop's semi-colon to a new line for legibility.
* Made lables less verbose.
* Updated type_alloc's error messages.
* type_alloc() frees allocated data on error instead of traceeval_init().
* Squashed initialize and release patches as init depends on release.
* Capitalized first letter of error messages.
* Added error message for clean_data() if data exists without defs.
* Aligned all function parameters with opening parenthesis.
* Remove compare and testing patches, beyond current scope of project.
---
v2 discussion: https://lore.kernel.org/linux-trace-devel/[email protected]/T/#t

Quoted 7 lines

Stevie Alvarez (Google) (6):
histograms: Initial histograms interface
histograms: Add traceeval initialize and release
histograms: Add traceeval compare
histograms: Add traceeval query
histograms: Add traceeval insert
histograms: Initial unit tests

The patch series counts six patches total, but you may notice that only five were sent. The last patch, 'Initial unit tests,' was purposefully not included, since it's beyond the current scope of the project. My apologies for the confusion.

-- Stevie

Quoted 24 lines
 Makefile                 |   2 +-
 include/traceeval-hist.h | 147 ++++++++
 include/traceeval-test.h |  16 +
 src/Makefile             |   1 +
 src/histograms.c         | 792 +++++++++++++++++++++++++++++++++++++++
 utest/.gitignore         |   1 +
 utest/Makefile           |  35 ++
 utest/eval-test.h        |  13 +
 utest/eval-utest.c       |  28 ++
 utest/traceeval-utest.c  | 290 ++++++++++++++
 10 files changed, 1324 insertions(+), 1 deletion(-)
 create mode 100644 include/traceeval-hist.h
 create mode 100644 include/traceeval-test.h
 create mode 100644 src/histograms.c
 create mode 100644 utest/.gitignore
 create mode 100644 utest/Makefile
 create mode 100644 utest/eval-test.h
 create mode 100644 utest/eval-utest.c
 create mode 100644 utest/traceeval-utest.c
Signature · 1 line
2.41.0