[PATCH] kernel-shark: Increase the size of the task hash

[Steven Rostedt <rostedt@xxxxxxxxxxx>]

From: Steven Rostedt (VMware) <rostedt@xxxxxxxxxxx>

When loading a data file that contained 100,000s of tasks, using a 256
bucket size hash crippled it. By increasing the hash to 2^16 (65536) it
solves the issue (still small enough not to waste too much memory).

In the process, I changed the knuth_hash() in libkshark.c to use the 32
bit version and just have the key use what it needs:

  key = knuth_hash();
  key += knuth_hash >> SHIFT;
  key &= (1 << SHIFT) - 1;

Signed-off-by: Steven Rostedt (VMware) <rostedt@xxxxxxxxxxx>
---
diff --git a/kernel-shark/src/libkshark.c b/kernel-shark/src/libkshark.c
index 4201fa02..41572e18 100644
--- a/kernel-shark/src/libkshark.c
+++ b/kernel-shark/src/libkshark.c
@@ -252,19 +252,19 @@ void kshark_free(struct kshark_context *kshark_ctx)
 	free(kshark_ctx);
 }
 
-static inline uint8_t knuth_hash(uint32_t val)
+static inline uint32_t knuth_hash(uint32_t val)
 {
 	/*
-	 * Small table hashing function adapted from Donald E. Knuth's 32 bit
+	 * 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.
+	 * 2^32.
 	 */
-	return UINT8_C(val) * UINT8_C(157);
+	return val * UINT32_C(2654435761);
 }
 
 static struct kshark_task_list *
-kshark_find_task(struct kshark_context *kshark_ctx, uint8_t key, int pid)
+kshark_find_task(struct kshark_context *kshark_ctx, uint32_t key, int pid)
 {
 	struct kshark_task_list *list;
 
@@ -280,9 +280,12 @@ static struct kshark_task_list *
 kshark_add_task(struct kshark_context *kshark_ctx, int pid)
 {
 	struct kshark_task_list *list;
-	uint8_t key;
+	uint32_t key;
 
 	key = knuth_hash(pid);
+	key += key >> KS_TASK_HASH_SHIFT;
+	key &= (1 << KS_TASK_HASH_SHIFT) - 1;
+
 	list = kshark_find_task(kshark_ctx, key, pid);
 	if (list)
 		return list;
diff --git a/kernel-shark/src/libkshark.h b/kernel-shark/src/libkshark.h
index 04e9cbfc..3407db19 100644
--- a/kernel-shark/src/libkshark.h
+++ b/kernel-shark/src/libkshark.h
@@ -72,7 +72,8 @@ struct kshark_entry {
 };
 
 /** Size of the task's hash table. */
-#define KS_TASK_HASH_SIZE 256
+#define KS_TASK_HASH_SHIFT 16
+#define KS_TASK_HASH_SIZE (1 << KS_TASK_HASH_SHIFT)
 
 /** Linked list of tasks. */
 struct kshark_task_list {