trace-filter: Change the naming convention used in trace-filter-hash
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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -117,8 +117,8 @@ struct trace_view_storegint 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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
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 intrace-graph.c,trace-plot.c,trace-plot-cpu.candtrace-plot-task.c. Becausetrace-hash-local.his no longer included intrace-filter-hash.h, it has to be included explicitly in these four source files.Signed-off-by Yordan Karadzhov (VMware) <[email protected]>---
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
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 intrace-graph.c,trace-plot.c,trace-plot-cpu.candtrace-plot-task.c. Becausetrace-hash-local.his no longer included intrace-filter-hash.h, it has to be included explicitly in these four source files.
Quoted 7 lines
Quoted 2 lines
Signed-off-by Yordan Karadzhov (VMware) <[email protected]>---
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
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@@ -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 ); +} +
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@@ -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 ); +} +
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