Skip to contentSkip to conversation

trace-filter: Change the naming convention used in trace-filter-hash

PATCH In review Yordan Karadzhov (VMware) 2 participants 7 messages Jun 19, 2018 – Jun 20, 2018

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/2 trace-filter: Change the naming convention used in trace-filter-hash

The trace-filter-hash code implements a set of hashing utilities for filtering the trace data. Currently, only tasks are filtered with this utility via its pid. To use this tool for filtering other items such as events, a name change is required for the structures and functions used. Instead of using the term "task", use the term "id", which is more generic, and will be less confusing when using the trace-filter-hash for filtering events and such.

---
 kernel-shark/include/kernel-shark.h      |   4 +-
 kernel-shark/include/trace-filter-hash.h |  31 +++--
 kernel-shark/include/trace-filter.h      |  12 +-
 kernel-shark/include/trace-graph.h       |  16 +--
 kernel-shark/include/trace-view-store.h  |  12 +-
 kernel-shark/include/trace-view.h        |   4 +-
 kernel-shark/kernel-shark.c              | 100 ++++++++--------
 kernel-shark/trace-filter-hash.c         | 143 ++++++++++++-----------
 kernel-shark/trace-filter.c              |  18 +--
 kernel-shark/trace-graph.c               |  48 ++++----
 kernel-shark/trace-view-main.c           |  22 ++--
 kernel-shark/trace-view-store.c          |  30 ++---
 kernel-shark/trace-view.c                |   4 +-
 13 files changed, 222 insertions(+), 222 deletions(-)
kernel-shark/include/kernel-shark.h +2 -2
index a673dbd..1934583 100644
@@ -48,8 +48,8 @@ struct shark_info {
 	gboolean			graph_follows;
 	gboolean			sync_task_filters;
 	gboolean			sync_event_filters;
-	struct filter_task		*list_task_filter;
-	struct filter_task		*list_hide_tasks;
+	struct filter_id		*list_task_filter;
+	struct filter_id		*list_hide_tasks;
 
 	/* Save capture state. */
 	gboolean			cap_all_events;
kernel-shark/include/trace-filter-hash.h +15 -16
index ceb4ad9..5cc39dc 100644
@@ -22,28 +22,27 @@
 
 #include "trace-hash-local.h"
 
-struct filter_task_item {
-	struct filter_task_item	*next;
-	int			pid;
+struct filter_id_item {
+	struct filter_id_item	*next;
+	int			id;
 };
 
-struct filter_task {
-	struct filter_task_item **hash;
+struct filter_id {
+	struct filter_id_item **hash;
 	int			count;
 };
 
-struct filter_task_item *
-filter_task_find_pid(struct filter_task *hash, int pid);
-void filter_task_add_pid(struct filter_task *hash, int pid);
-void filter_task_remove_pid(struct filter_task *hash, int pid);
-void filter_task_clear(struct filter_task *hash);
-struct filter_task *filter_task_hash_alloc(void);
-void filter_task_hash_free(struct filter_task *hash);
-struct filter_task *filter_task_hash_copy(struct filter_task *hash);
-int *filter_task_pids(struct filter_task *hash);
-int filter_task_compare(struct filter_task *hash1, struct filter_task *hash2);
+struct filter_id_item *filter_id_find(struct filter_id *hash, int id);
+void filter_id_add(struct filter_id *hash, int id);
+void filter_id_remove(struct filter_id *hash, int id);
+void filter_id_clear(struct filter_id *hash);
+struct filter_id *filter_id_hash_alloc(void);
+void filter_id_hash_free(struct filter_id *hash);
+struct filter_id *filter_id_hash_copy(struct filter_id *hash);
+int *filter_ids(struct filter_id *hash);
+int filter_id_compare(struct filter_id *hash1, struct filter_id *hash2);
 
-static inline int filter_task_count(struct filter_task *hash)
+static inline int filter_task_count(struct filter_id *hash)
 {
 	return hash->count;
 }
kernel-shark/include/trace-filter.h +6 -6
index d547095..4ddbd22 100644
@@ -146,21 +146,21 @@ void trace_array_add(gint **array, gint *count, gint val);
 int trace_filter_save_events(struct tracecmd_xml_handle *handle,
 			     struct event_filter *filter);
 int trace_filter_save_tasks(struct tracecmd_xml_handle *handle,
-			    struct filter_task *filter);
+			    struct filter_id *filter);
 int trace_filter_load_events(struct event_filter *event_filter,
 			     struct tracecmd_xml_handle *handle,
 			     struct tracecmd_xml_system_node *node);
-int trace_filter_load_task_filter(struct filter_task *filter,
+int trace_filter_load_task_filter(struct filter_id *filter,
 				  struct tracecmd_xml_handle *handle,
 				  struct tracecmd_xml_system_node *node);
 int trace_filter_load_filters(struct tracecmd_xml_handle *handle,
 			      const char *system_name,
-			      struct filter_task *task_filter,
-			      struct filter_task *hide_tasks);
+			      struct filter_id *task_filter,
+			      struct filter_id *hide_tasks);
 int trace_filter_save_filters(struct tracecmd_xml_handle *handle,
 			      const char *system_name,
-			      struct filter_task *task_filter,
-			      struct filter_task *hide_tasks);
+			      struct filter_id *task_filter,
+			      struct filter_id *hide_tasks);
 
 GtkWidget *trace_create_event_list_view(struct pevent *pevent,
 					struct event_filter *filter,
kernel-shark/include/trace-graph.h +8 -8
index 7e66838..0f35e59 100644
@@ -29,8 +29,8 @@ struct graph_info;
 
 typedef void (graph_select_cb)(struct graph_info *ginfo, guint64 time);
 typedef void (graph_filter_cb)(struct graph_info *ginfo,
-			       struct filter_task *task_filter,
-			       struct filter_task *hide_tasks);
+			       struct filter_id *task_filter,
+			       struct filter_id *hide_tasks);
 
 /* Used for quereing what plots are defined */
 enum graph_plot_type {
@@ -248,10 +248,10 @@ struct graph_info {
 
 	gboolean		read_comms;	/* Read all comms on first load */
 
-	struct filter_task	*task_filter;
+	struct filter_id	*task_filter;
 	gint			filter_task_selected;
 
-	struct filter_task	*hide_tasks;
+	struct filter_id	*hide_tasks;
 
 	/* Box info for plot data info window */
 	gint			plot_data_x;
@@ -296,9 +296,9 @@ static inline GtkWidget *trace_graph_get_window(struct graph_info *ginfo)
 
 void trace_graph_refresh(struct graph_info *ginfo);
 
-struct filter_task_item *
+struct filter_id_item *
 trace_graph_filter_task_find_pid(struct graph_info *ginfo, gint pid);
-struct filter_task_item *
+struct filter_id_item *
 trace_graph_hide_task_find_pid(struct graph_info *ginfo, gint pid);
 void trace_graph_filter_toggle(struct graph_info *ginfo);
 void trace_graph_filter_add_remove_task(struct graph_info *info,
@@ -331,8 +331,8 @@ int trace_graph_load_filters(struct graph_info *ginfo,
 int trace_graph_save_filters(struct graph_info *ginfo,
 			     struct tracecmd_xml_handle *handle);
 void trace_graph_update_filters(struct graph_info *ginfo,
-				struct filter_task *task_filter,
-				struct filter_task *hide_tasks);
+				struct filter_id *task_filter,
+				struct filter_id *hide_tasks);
 void trace_graph_refresh_filters(struct graph_info *ginfo);
 
 /* plots */
kernel-shark/include/trace-view-store.h +6 -6
index 03141b1..1204c4b 100644
@@ -117,8 +117,8 @@ struct trace_view_store
 	gint			all_events; /* set 1 when all events are enabled */
 						/* else */
 	struct event_filter	*event_filter; /* Filtered events */
-	struct filter_task	*task_filter;	/* hash of tasks to filter on */
-	struct filter_task	*hide_tasks;	/* hash of tasks to not display */
+	struct filter_id	*task_filter;	/* hash of tasks to filter on */
+	struct filter_id	*hide_tasks;	/* hash of tasks to not display */
 
 	gint			all_cpus;   /* set 1 when all cpus are enabled */
 						/* else */
@@ -141,13 +141,13 @@ gint trace_view_store_get_timestamp_page(TraceViewStore *store, guint64 ts);
 
 gint trace_view_store_get_timestamp_visible_row(TraceViewStore *store, guint64 ts);
 
-void trace_view_store_filter_tasks(TraceViewStore *store, struct filter_task *filter);
+void trace_view_store_filter_tasks(TraceViewStore *store, struct filter_id *filter);
 
-void trace_view_store_hide_tasks(TraceViewStore *store, struct filter_task *filter);
+void trace_view_store_hide_tasks(TraceViewStore *store, struct filter_id *filter);
 
 void trace_view_store_assign_filters(TraceViewStore *store,
-				     struct filter_task *task_filter,
-				     struct filter_task *hide_tasks);
+				     struct filter_id *task_filter,
+				     struct filter_id *hide_tasks);
 
 TraceViewRecord *trace_view_store_get_row(TraceViewStore *store, gint row);
 
kernel-shark/include/trace-view.h +2 -2
index 93a10f6..036f51e 100644
@@ -34,8 +34,8 @@ void trace_view_reload(GtkWidget *view, struct tracecmd_input *handle,
 void trace_view(int argc, char **argv);
 
 void trace_view_update_filters(GtkWidget *treeview,
-			       struct filter_task *task_filter,
-			       struct filter_task *hide_tasks);
+			       struct filter_id *task_filter,
+			       struct filter_id *hide_tasks);
 
 void trace_view_make_selection_visible(GtkWidget *treeview);
 
kernel-shark/kernel-shark.c +50 -50

280 lines not on this page · raw message

kernel-shark/trace-filter-hash.c +72 -71

262 lines not on this page · raw message

kernel-shark/trace-filter.c +9 -9
index bd8cb11..f5c3f29 100644
@@ -2076,13 +2076,13 @@ int trace_filter_save_events(struct tracecmd_xml_handle *handle,
 }
 
 int trace_filter_save_tasks(struct tracecmd_xml_handle *handle,
-			    struct filter_task *filter)
+			    struct filter_id *filter)
 {
 	char buffer[100];
 	int *pids;
 	int i;
 
-	pids = filter_task_pids(filter);
+	pids = filter_ids(filter);
 	if (!pids)
 		return -1;
 
@@ -2171,7 +2171,7 @@ int trace_filter_load_events(struct event_filter *event_filter,
 	return 0;
 }
 
-int trace_filter_load_task_filter(struct filter_task *filter,
+int trace_filter_load_task_filter(struct filter_id *filter,
 				  struct tracecmd_xml_handle *handle,
 				  struct tracecmd_xml_system_node *node)
 {
@@ -2190,8 +2190,8 @@ int trace_filter_load_task_filter(struct filter_task *filter,
 		if (strcmp(name, "Task") == 0) {
 			task = tracecmd_xml_node_value(handle, node);
 			pid = atoi(task);
-			if (!filter_task_find_pid(filter, pid))
-				filter_task_add_pid(filter, pid);
+			if (!filter_id_find(filter, pid))
+				filter_id_add(filter, pid);
 		}
 		node = tracecmd_xml_node_next(node);
 	}
@@ -2201,8 +2201,8 @@ int trace_filter_load_task_filter(struct filter_task *filter,
 
 int trace_filter_load_filters(struct tracecmd_xml_handle *handle,
 			      const char *system_name,
-			      struct filter_task *task_filter,
-			      struct filter_task *hide_tasks)
+			      struct filter_id *task_filter,
+			      struct filter_id *hide_tasks)
 {
 	struct tracecmd_xml_system *system;
 	struct tracecmd_xml_system_node *syschild;
@@ -2240,8 +2240,8 @@ int trace_filter_load_filters(struct tracecmd_xml_handle *handle,
 
 int trace_filter_save_filters(struct tracecmd_xml_handle *handle,
 			      const char *system_name,
-			      struct filter_task *task_filter,
-			      struct filter_task *hide_tasks)
+			      struct filter_id *task_filter,
+			      struct filter_id *hide_tasks)
 {
 
 	tracecmd_xml_start_system(handle, system_name);
kernel-shark/trace-graph.c +24 -24

132 lines not on this page · raw message

kernel-shark/trace-view-main.c +11 -11
index 56a5a34..a088bbb 100644
@@ -49,8 +49,8 @@ struct trace_tree_info {
 	GtkWidget		*spin;
 	gint			filter_enabled;
 	gint			filter_task_selected;
-	struct filter_task	*task_filter;
-	struct filter_task	*hide_tasks;
+	struct filter_id	*task_filter;
+	struct filter_id	*hide_tasks;
 };
 
 void usage(char *prog)
@@ -243,17 +243,17 @@ filter_list_clicked (gpointer data)
 }
 
 static void update_task_filter(struct trace_tree_info *info,
-			       struct filter_task *filter)
+			       struct filter_id *filter)
 {
-	struct filter_task_item *task;
+	struct filter_id_item *task;
 	gint pid = info->filter_task_selected;
 
-	task = filter_task_find_pid(filter, pid);
+	task = filter_id_find(filter, pid);
 
 	if (task)
-		filter_task_remove_pid(filter, pid);
+		filter_id_remove(filter, pid);
 	else
-		filter_task_add_pid(filter, pid);
+		filter_id_add(filter, pid);
 
 	if (info->filter_enabled)
 		trace_view_update_filters(info->trace_tree,
@@ -399,7 +399,7 @@ do_tree_popup(GtkWidget *widget, GdkEventButton *event, gpointer data)
 			text = g_malloc(len);
 			g_assert(text);
 
-			if (filter_task_find_pid(info->task_filter, pid))
+			if (filter_id_find(info->task_filter, pid))
 				snprintf(text, len, "Remove %s-%d from filter", comm, pid);
 			else
 				snprintf(text, len, "Add %s-%d to filter", comm, pid);
@@ -409,7 +409,7 @@ do_tree_popup(GtkWidget *widget, GdkEventButton *event, gpointer data)
 			gtk_menu_item_set_label(GTK_MENU_ITEM(menu_filter_add_task),
 						text);
 
-			if (filter_task_find_pid(info->hide_tasks, pid))
+			if (filter_id_find(info->hide_tasks, pid))
 				snprintf(text, len, "Show %s-%d", comm, pid);
 			else
 				snprintf(text, len, "Hide %s-%d", comm, pid);
@@ -519,8 +519,8 @@ void trace_view(int argc, char **argv)
 
 	memset(&tree_info, 0, sizeof(tree_info));
 	tree_info.handle = handle;
-	tree_info.task_filter = filter_task_hash_alloc();
-	tree_info.hide_tasks = filter_task_hash_alloc();
+	tree_info.task_filter = filter_id_hash_alloc();
+	tree_info.hide_tasks = filter_id_hash_alloc();
 
 	/* --- Main window --- */
 
kernel-shark/trace-view-store.c +15 -15
index f5d0a04..29e064e 100644
@@ -231,7 +231,7 @@ trace_view_store_finalize (GObject *object)
 	g_free(store->rows);
 	g_free(store->cpu_items);
 
-	filter_task_hash_free(store->task_filter);
+	filter_id_hash_free(store->task_filter);
 
 	if (store->spin) {
 		g_object_unref(store->spin);
@@ -1184,10 +1184,10 @@ static gboolean view_task(TraceViewStore *store, gint pid)
 {
 	return (!store->task_filter ||
 		!filter_task_count(store->task_filter) ||
-		filter_task_find_pid(store->task_filter, pid)) &&
+		filter_id_find(store->task_filter, pid)) &&
 		(!store->hide_tasks ||
 		 !filter_task_count(store->hide_tasks) ||
-		 !filter_task_find_pid(store->hide_tasks, pid));
+		 !filter_id_find(store->hide_tasks, pid));
 }
 
 static gboolean show_task(TraceViewStore *store, struct pevent *pevent,
@@ -1295,30 +1295,30 @@ static void update_filter_tasks(TraceViewStore *store)
 	merge_sort_rows_ts(store);
 }
 
-void trace_view_store_filter_tasks(TraceViewStore *store, struct filter_task *filter)
+void trace_view_store_filter_tasks(TraceViewStore *store, struct filter_id *filter)
 {
 	g_return_if_fail (TRACE_VIEW_IS_LIST (store));
 
 	/* We may pass in the store->task_filter. Don't free it if we do */
 	if (store->task_filter && store->task_filter != filter)
-		filter_task_hash_free(store->task_filter);
+		filter_id_hash_free(store->task_filter);
 
 	if (store->task_filter != filter)
-		store->task_filter = filter_task_hash_copy(filter);
+		store->task_filter = filter_id_hash_copy(filter);
 
 	update_filter_tasks(store);
 }
 
-void trace_view_store_hide_tasks(TraceViewStore *store, struct filter_task *filter)
+void trace_view_store_hide_tasks(TraceViewStore *store, struct filter_id *filter)
 {
 	g_return_if_fail (TRACE_VIEW_IS_LIST (store));
 
 	/* We may pass in the store->task_filter. Don't free it if we do */
 	if (store->hide_tasks && store->hide_tasks != filter)
-		filter_task_hash_free(store->hide_tasks);
+		filter_id_hash_free(store->hide_tasks);
 
 	if (store->hide_tasks != filter)
-		store->hide_tasks = filter_task_hash_copy(filter);
+		store->hide_tasks = filter_id_hash_copy(filter);
 
 	update_filter_tasks(store);
 }
@@ -1331,23 +1331,23 @@ void trace_view_store_update_filter(TraceViewStore *store)
 }
 
 void trace_view_store_assign_filters(TraceViewStore *store,
-				     struct filter_task *task_filter,
-				     struct filter_task *hide_tasks)
+				     struct filter_id *task_filter,
+				     struct filter_id *hide_tasks)
 {
 	g_return_if_fail (TRACE_VIEW_IS_LIST (store));
 
 	/* We may pass in the store->task_filter. Don't free it if we do */
 	if (store->task_filter && store->task_filter != task_filter)
-		filter_task_hash_free(store->task_filter);
+		filter_id_hash_free(store->task_filter);
 
 	if (store->hide_tasks && store->hide_tasks != hide_tasks)
-		filter_task_hash_free(store->hide_tasks);
+		filter_id_hash_free(store->hide_tasks);
 
 	if (store->hide_tasks != hide_tasks)
-		store->hide_tasks = filter_task_hash_copy(hide_tasks);
+		store->hide_tasks = filter_id_hash_copy(hide_tasks);
 
 	if (store->task_filter != task_filter)
-		store->task_filter = filter_task_hash_copy(task_filter);
+		store->task_filter = filter_id_hash_copy(task_filter);
 }
 
 /*****************************************************************************
kernel-shark/trace-view.c +2 -2
index 1dd3adc..377f2db 100644
@@ -301,8 +301,8 @@ void trace_view_make_selection_visible(GtkWidget *treeview)
 }
 
 void trace_view_update_filters(GtkWidget *treeview,
-			       struct filter_task *task_filter,
-			       struct filter_task *hide_tasks)
+			       struct filter_id *task_filter,
+			       struct filter_id *hide_tasks)
 {
 	GtkTreeView *tree = GTK_TREE_VIEW(treeview);
 	TraceViewRecord *vrec;
Signature · 1 line
2.17.1
#1 lore raw

PATCH v2 2/2 trace-filter: Change the hashing function used when filtering

The hashing function used in trace-filter-hash is changed. The new hashing functions is based on the Donald E. Knuth's Multiplicative hashing, suggested in his book "The Art of Computer Programming". This improves the performance, but also removes the restrictions resulting from using the Paul Hsieh's super fast hash, published under the terms of the GPL 2.0 license.

Paul Hsieh's hash function, defined in trace-hash-local.h, is still used in trace-graph.c, trace-plot.c, trace-plot-cpu.c and trace-plot-task.c. Because trace-hash-local.h is no longer included in trace-filter-hash.h, it has to be included explicitly in these four source files.

---
 kernel-shark/include/trace-filter-hash.h | 37 +++++++++++++++++++++++-
 kernel-shark/trace-filter-hash.c         |  6 ++--
 kernel-shark/trace-graph.c               |  1 +
 kernel-shark/trace-plot-cpu.c            |  1 +
 kernel-shark/trace-plot-task.c           |  1 +
 kernel-shark/trace-plot.c                |  1 +
 6 files changed, 43 insertions(+), 4 deletions(-)
kernel-shark/include/trace-filter-hash.h +36 -1
index 5cc39dc..98c9ab3 100644
@@ -20,7 +20,7 @@
 #ifndef _TRACE_FILTER_HASH_H
 #define _TRACE_FILTER_HASH_H
 
-#include "trace-hash-local.h"
+#include <stdint.h>
 
 struct filter_id_item {
 	struct filter_id_item	*next;
@@ -47,4 +47,39 @@ static inline int filter_task_count(struct filter_id *hash)
 	return hash->count;
 }
 
+/*
+ * Hashing functions, based on Donald E. Knuth's Multiplicative hashing.
+ * See The Art of Computer Programming (TAOCP).
+ */
+
+static inline uint8_t knuth_hash8(uint32_t val)
+{
+	/*
+	 * Multiplicative hashing function.
+	 * Multiplication by the Prime number, closest to the golden
+	 * ratio of 2^8.
+	 */
+	return UINT8_C(val) * UINT8_C(157);
+}
+
+static inline uint16_t knuth_hash16(uint32_t val)
+{
+	/*
+	 * Multiplicative hashing function.
+	 * Multiplication by the Prime number, closest to the golden
+	 * ratio of 2^16.
+	 */
+	return UINT16_C(val) * UINT16_C(40507);
+}
+
+static inline uint32_t knuth_hash(uint32_t val)
+{
+	/*
+	 * Multiplicative hashing function.
+	 * Multiplication by the Prime number, closest to the golden
+	 * ratio of 2^32.
+	 */
+	return val * UINT32_C(2654435761);
+}
+
 #endif /* _TRACE_FILTER_HASH_H */
kernel-shark/trace-filter-hash.c +3 -3
index cf41250..703109c 100644
@@ -30,7 +30,7 @@
 struct filter_id_item *
 filter_id_find(struct filter_id *hash, int id)
 {
-	int key = trace_hash(id) % FILTER_HASH_SIZE;
+	int key = knuth_hash8(id);
 	struct filter_id_item *item = hash->hash[key];
 
 	while (item) {
@@ -44,7 +44,7 @@ filter_id_find(struct filter_id *hash, int id)
 
 void filter_id_add(struct filter_id *hash, int id)
 {
-	int key = trace_hash(id) % FILTER_HASH_SIZE;
+	int key = knuth_hash8(id);
 	struct filter_id_item *item;
 
 	item = calloc(1, sizeof(*item));
@@ -59,7 +59,7 @@ void filter_id_add(struct filter_id *hash, int id)
 
 void filter_id_remove(struct filter_id *hash, int id)
 {
-	int key = trace_hash(id) % FILTER_HASH_SIZE;
+	int key = knuth_hash8(id);
 	struct filter_id_item **next = &hash->hash[key];
 	struct filter_id_item *item;
 
kernel-shark/trace-graph.c +1 -0
index b652297..1aba417 100644
@@ -33,6 +33,7 @@
 #include "trace-graph.h"
 #include "trace-filter-hash.h"
 #include "trace-filter.h"
+#include "trace-hash-local.h"
 #include "trace-gui.h"
 
 #include "event-utils.h"
kernel-shark/trace-plot-cpu.c +1 -0
index 8374809..d2a0523 100644
@@ -22,6 +22,7 @@
 
 #include "trace-graph.h"
 #include "trace-local.h"
+#include "trace-hash-local.h"
 #include "cpu.h"
 
 struct cpu_plot_info {
kernel-shark/trace-plot-task.c +1 -0
index 3b7e81f..c846221 100644
@@ -23,6 +23,7 @@
 #include "trace-graph.h"
 #include "trace-filter.h"
 #include "trace-local.h"
+#include "trace-hash-local.h"
 
 #define RED 0xff
 #define GREEN (0xff<<16)
kernel-shark/trace-plot.c +1 -0
index dc5b3af..bf2cec0 100644
@@ -21,6 +21,7 @@
 #include <string.h>
 #include "trace-graph.h"
 #include "trace-local.h"
+#include "trace-hash-local.h"
 
 void trace_graph_plot_free(struct graph_info *ginfo)
 {
Signature · 1 line
2.17.1
#2 lore raw

Re: [PATCH v2 2/2] trace-filter: Change the hashing function used when filtering

Quoted 8 lines · On Tue, 19 Jun 2018 16:22:59 +0300 "Yordan Karadzhov (VMware)"…

The hashing function used in trace-filter-hash is changed. The new hashing functions is based on the Donald E. Knuth's Multiplicative hashing, suggested in his book "The Art of Computer Programming". This improves the performance, but also removes the restrictions resulting from using the Paul Hsieh's super fast hash, published under the terms of the GPL 2.0 license.

Quoted 8 lines

Paul Hsieh's hash function, defined in trace-hash-local.h, is still used in trace-graph.c, trace-plot.c, trace-plot-cpu.c and trace-plot-task.c. Because trace-hash-local.h is no longer included in trace-filter-hash.h, it has to be included explicitly in these four source files.

---

I've applied these but haven't pushed them out yet. Which files need to be changed from GPL to LGPL? Now that we have removed the GPL code from the filter hash.

-- Steve

#3 lore raw

Re: [PATCH v2 2/2] trace-filter: Change the hashing function used when filtering

Quoted 17 lines · Steven Rostedt
Quoted 14 lines · On Tue, 19 Jun 2018 16:22:59 +0300 "Yordan Karadzhov (VMware)"…

The hashing function used in trace-filter-hash is changed. The new hashing functions is based on the Donald E. Knuth's Multiplicative hashing, suggested in his book "The Art of Computer Programming". This improves the performance, but also removes the restrictions resulting from using the Paul Hsieh's super fast hash, published under the terms of the GPL 2.0 license.

Paul Hsieh's hash function, defined in trace-hash-local.h, is still used in trace-graph.c, trace-plot.c, trace-plot-cpu.c and trace-plot-task.c. Because trace-hash-local.h is no longer included in trace-filter-hash.h, it has to be included explicitly in these four source files.

Quoted 7 lines
Quoted 2 lines

---

I've applied these but haven't pushed them out yet. Which files need to be changed from GPL to LGPL? Now that we have removed the GPL code from the filter hash.

I would like to have trace-filter-hash.h and trace-filter-hash.c changed to LGPL. Also I would like trace-filter-hash.o to became part of libtracecmd and respectively trace-filter-hash.h to be moved to /include/trace-cmd/

Thank you very much!

Yordan

Quoted 2 lines

-- Steve

#4 lore raw

Re: [PATCH v2 2/2] trace-filter: Change the hashing function used when filtering

In reply to Yordan Karadzhov (VMware)
Quoted 33 lines · On Tue, 19 Jun 2018 16:22:59 +0300 "Yordan Karadzhov (VMware)"…
kernel-shark/include/trace-filter-hash.h +17 -1
index 5cc39dc..98c9ab3 100644
@@ -20,7 +20,7 @@
 #ifndef _TRACE_FILTER_HASH_H
 #define _TRACE_FILTER_HASH_H
 
-#include "trace-hash-local.h"
+#include <stdint.h>
 
 struct filter_id_item {
 	struct filter_id_item	*next;
@@ -47,4 +47,39 @@ static inline int filter_task_count(struct filter_id *hash)
 	return hash->count;
 }
 
+/*
+ * Hashing functions, based on Donald E. Knuth's Multiplicative hashing.
+ * See The Art of Computer Programming (TAOCP).
+ */
+
+static inline uint8_t knuth_hash8(uint32_t val)
+{
+	/*
+	 * Multiplicative hashing function.
+	 * Multiplication by the Prime number, closest to the golden
+	 * ratio of 2^8.
+	 */
+	return UINT8_C(val) * UINT8_C(157);
+}
+
+static inline uint16_t knuth_hash16(uint32_t val)

kernel-shark/include/trace-filter-hash.h static inline int filter_task_count(struct filter_id *hash) · line 75

Quoted 10 lines
kernel-shark/include/trace-filter-hash.h +10 -0
+{
+	/*
+	 * Multiplicative hashing function.
+	 * Multiplication by the Prime number, closest to the golden
+	 * ratio of 2^16.
+	 */
+	return UINT16_C(val) * UINT16_C(40507);
+}
+
+static inline uint32_t knuth_hash(uint32_t val)

BTW, is there any reason to have these in the header file? Shouldn't they be in a C file?

The reason I ask is because this is going to be in a more public file, and I need to rename the functions for namespace reasons. These are someone out of place for a library header.

-- Steve

Quoted 9 lines
kernel-shark/include/trace-filter-hash.h +9 -0
+{
+	/*
+	 * Multiplicative hashing function.
+	 * Multiplication by the Prime number, closest to the golden
+	 * ratio of 2^32.
+	 */
+	return val * UINT32_C(2654435761);
+}
+
#5 lore raw

Re: [PATCH v2 2/2] trace-filter: Change the hashing function used when filtering

Quoted 49 lines · Steven Rostedt
Quoted 33 lines · On Tue, 19 Jun 2018 16:22:59 +0300 "Yordan Karadzhov (VMware)"…
kernel-shark/include/trace-filter-hash.h +17 -1
index 5cc39dc..98c9ab3 100644
@@ -20,7 +20,7 @@
  #ifndef _TRACE_FILTER_HASH_H
  #define _TRACE_FILTER_HASH_H
 
-#include "trace-hash-local.h"
+#include <stdint.h>
 
  struct filter_id_item {
  	struct filter_id_item	*next;
@@ -47,4 +47,39 @@ static inline int filter_task_count(struct filter_id *hash)
  	return hash->count;
  }
 
+/*
+ * Hashing functions, based on Donald E. Knuth's Multiplicative hashing.
+ * See The Art of Computer Programming (TAOCP).
+ */
+
+static inline uint8_t knuth_hash8(uint32_t val)
+{
+	/*
+	 * Multiplicative hashing function.
+	 * Multiplication by the Prime number, closest to the golden
+	 * ratio of 2^8.
+	 */
+	return UINT8_C(val) * UINT8_C(157);
+}
+
+static inline uint16_t knuth_hash16(uint32_t val)

kernel-shark/include/trace-filter-hash.h static inline int filter_task_count(struct filter_id *hash) · line 75

Quoted 10 lines
kernel-shark/include/trace-filter-hash.h +10 -0
+{
+	/*
+	 * Multiplicative hashing function.
+	 * Multiplication by the Prime number, closest to the golden
+	 * ratio of 2^16.
+	 */
+	return UINT16_C(val) * UINT16_C(40507);
+}
+
+static inline uint32_t knuth_hash(uint32_t val)

BTW, is there any reason to have these in the header file? Shouldn't they be in a C file?

Quoted 3 lines

The reason I ask is because this is going to be in a more public file, and I need to rename the functions for namespace reasons. These are someone out of place for a library header.

My only reason for having the hash functions in the header is to make sure that the user will be aware that those are cheap and fast functions, but using those functions makes sense only in the case when we have relatively small number of items in the hash table. Nevertheless, If you prefer the implementation to be in the .c file this is OK.

Yordan

Quoted 12 lines

-- Steve

Quoted 9 lines
kernel-shark/include/trace-filter-hash.h +9 -0
+{
+	/*
+	 * Multiplicative hashing function.
+	 * Multiplication by the Prime number, closest to the golden
+	 * ratio of 2^32.
+	 */
+	return val * UINT32_C(2654435761);
+}
+
#6 lore raw

Re: [PATCH v2 2/2] trace-filter: Change the hashing function used when filtering

Quoted 7 lines · On Wed, 20 Jun 2018 21:04:48 +0300 Yordan Karadzhov <[email protected]> wrote:

My only reason for having the hash functions in the header is to make sure that the user will be aware that those are cheap and fast functions, but using
those functions makes sense only in the case when we have relatively small number of items in the hash table. Nevertheless, If you prefer the implementation
to be in the .c file this is OK.

Either that, or in a local header file. I don't think we need to export this as part of libtracecmd.a

I'll make the changes.

Thanks!

-- Steve