[1/2] trace-cmd: Make a global tracecmd_quick_hash() instead of a local knuth_hash()

Commit Message

Steven Rostedt Sept. 20, 2019, 3:15 p.m. UTC

From: "Steven Rostedt (VMware)" <[e-mail]>

As the 32 bit Knuth algorith produces the same results as the small
sizes[1], create a single algorithm that takes in a @bits parameter that
will return a masked result. And replace the local version of knuth_hash()
used by the trace-cmd filter code. This will also be used to remove other
copies of knuth_hash().

[1] https://lore.kernel.org/r/[e-mail]

Signed-off-by: Steven Rostedt (VMware) <[e-mail]>
---
 include/trace-cmd/trace-filter-hash.h | 24 ++++++++++++++++++++++++
 lib/trace-cmd/trace-filter-hash.c     | 20 +++++---------------
 2 files changed, 29 insertions(+), 15 deletions(-)

Patch

diff --git a/include/trace-cmd/trace-filter-hash.h b/include/trace-cmd/trace-filter-hash.h
index e94bc87d1e1d..4111c41eeb2d 100644
--- a/include/trace-cmd/trace-filter-hash.h
+++ b/include/trace-cmd/trace-filter-hash.h
@@ -19,6 +19,30 @@  struct tracecmd_filter_id {
 	int				count;
 };
 
+/**
+ * tracecmd_quick_hash - A quick (non secured) hash alogirthm
+ * @val: The value to perform the hash on
+ * @bits: The size in bits you need to return
+ *
+ * This is a quick hashing function adapted from Donald E. Knuth's 32
+ * bit multiplicative hash.  See The Art of Computer Programming (TAOCP).
+ * Multiplication by the Prime number, closest to the golden ratio of
+ * 2^32.
+ *
+ * @bits is used to max the result for use cases that require
+ * a power of 2 return value that is less than 32 bits. Any value
+ * of @bits greater than 31 (or zero), will simply return the full hash on @val.
+ */
+static inline uint32_t tracecmd_quick_hash(uint32_t val, unsigned int bits)
+{
+	val *= UINT32_C(2654435761);
+
+	if (!bits || bits > 31)
+		return val;
+
+	return val & ((1 << bits) - 1);
+}
+
 struct tracecmd_filter_id_item *
   tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id);
 void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id);
diff --git a/lib/trace-cmd/trace-filter-hash.c b/lib/trace-cmd/trace-filter-hash.c
index 45ca68c2959e..f5f0fb09403b 100644
--- a/lib/trace-cmd/trace-filter-hash.c
+++ b/lib/trace-cmd/trace-filter-hash.c
@@ -12,23 +12,13 @@ 
 
 #include "trace-filter-hash.h"
 
-#define FILTER_HASH_SIZE	256
-
-static inline uint8_t knuth_hash(uint32_t val)
-{
-	/*
-	 * Small table hashing function adapted from Donald E. Knuth's 32 bit
-	 * multiplicative hash.  See The Art of Computer Programming (TAOCP).
-	 * Multiplication by the Prime number, closest to the golden ratio of
-	 * 2^8.
-	 */
-	return UINT8_C(val) * UINT8_C(157);
-}
+#define FILTER_HASH_BITS	8
+#define FILTER_HASH_SIZE	(1 << FILTER_HASH_BITS)
 
 struct tracecmd_filter_id_item *
 tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)
 {
-	int key = knuth_hash(id);
+	int key = tracecmd_quick_hash(id, FILTER_HASH_BITS);
 	struct tracecmd_filter_id_item *item = hash->hash[key];
 
 	while (item) {
@@ -42,7 +32,7 @@  tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id)
 
 void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id)
 {
-	int key = knuth_hash(id);
+	int key = tracecmd_quick_hash(id, FILTER_HASH_BITS);
 	struct tracecmd_filter_id_item *item;
 
 	item = calloc(1, sizeof(*item));
@@ -57,7 +47,7 @@  void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id)
 
 void tracecmd_filter_id_remove(struct tracecmd_filter_id *hash, int id)
 {
-	int key = knuth_hash(id);
+	int key = tracecmd_quick_hash(id, FILTER_HASH_BITS);
 	struct tracecmd_filter_id_item **next = &hash->hash[key];
 	struct tracecmd_filter_id_item *item;