From 82fc4d8f92765f5e0c5e3688c128be6c8d6c310f Mon Sep 17 00:00:00 2001
From: weiyu <weiyuluo1232@gmail.com>
Date: Mon, 21 Oct 2019 15:08:34 -0700
Subject: [PATCH] Add a hash function for 64-bit int to improve the performance
 of val_loc_map in FuncNode when running mb_rc_test

---
 Makefile        |  2 +-
 funcnode.cc     |  8 ++++----
 funcnode.h      |  5 +++--
 hashfunction.cc | 12 ++++++++++++
 hashfunction.h  |  8 ++++++++
 5 files changed, 28 insertions(+), 7 deletions(-)
 create mode 100644 hashfunction.cc
 create mode 100644 hashfunction.h

diff --git a/Makefile b/Makefile
index f9d34249..4329fc46 100644
--- a/Makefile
+++ b/Makefile
@@ -6,7 +6,7 @@ OBJECTS := libthreads.o schedule.o model.o threads.o librace.o action.o \
 	   snapshot.o malloc.o mymemory.o common.o mutex.o conditionvariable.o \
 	   context.o execution.o libannotate.o plugins.o pthread.o futex.o fuzzer.o \
 	   sleeps.o history.o funcnode.o funcinst.o predicate.o printf.o newfuzzer.o \
-	   concretepredicate.o waitobj.o
+	   concretepredicate.o waitobj.o hashfunction.o
 
 CPPFLAGS += -Iinclude -I.
 LDFLAGS := -ldl -lrt -rdynamic -lpthread
diff --git a/funcnode.cc b/funcnode.cc
index 8cb39da9..c739a284 100644
--- a/funcnode.cc
+++ b/funcnode.cc
@@ -22,11 +22,11 @@ FuncNode::FuncNode(ModelHistory * history) :
 	predicate_tree_entry->add_predicate_expr(NOPREDICATE, NULL, true);
 	predicate_tree_exit = new Predicate(NULL, false, true);
 
-	// Memories that are reclaimed after each execution
+	/* Snapshot data structures below */
 	action_list_buffer = new SnapList<action_list_t *>();
 	read_locations = new loc_set_t();
 	write_locations = new loc_set_t();
-	val_loc_map = new HashTable<uint64_t, loc_set_t *, uint64_t, 0>();
+	val_loc_map = new HashTable<uint64_t, loc_set_t *, uint64_t, 0, snapshot_malloc, snapshot_calloc, snapshot_free, int64_hash>();
 	loc_may_equal_map = new HashTable<void *, loc_set_t *, uintptr_t, 0>();
 
 	//values_may_read_from = new value_set_t();
@@ -38,7 +38,7 @@ void FuncNode::set_new_exec_flag()
 	action_list_buffer = new SnapList<action_list_t *>();
 	read_locations = new loc_set_t();
 	write_locations = new loc_set_t();
-	val_loc_map = new HashTable<uint64_t, loc_set_t *, uint64_t, 0>();
+	val_loc_map = new HashTable<uint64_t, loc_set_t *, uint64_t, 0, snapshot_malloc, snapshot_calloc, snapshot_free, int64_hash>();
 	loc_may_equal_map = new HashTable<void *, loc_set_t *, uintptr_t, 0>();
 
 	//values_may_read_from = new value_set_t();
@@ -306,7 +306,7 @@ void FuncNode::update_predicate_tree(action_list_t * act_list)
 			inst_id_map.put(next_inst, inst_counter++);
 
 		it = it->getNext();
-		curr_pred->incr_expl_count();
+		/*-- curr_pred->incr_expl_count(); */
 	}
 
 	curr_pred->set_exit(predicate_tree_exit);
diff --git a/funcnode.h b/funcnode.h
index 0bcc73b5..fab4db50 100644
--- a/funcnode.h
+++ b/funcnode.h
@@ -2,12 +2,13 @@
 #define __FUNCNODE_H__
 
 #include "hashset.h"
+#include "hashfunction.h"
 #include "classlist.h"
 #include "threads-model.h"
 
 #define MAX_DIST 10
-typedef ModelList<FuncInst *> func_inst_list_mt;
 
+typedef ModelList<FuncInst *> func_inst_list_mt;
 typedef enum edge_type {
 	IN_EDGE, OUT_EDGE, BI_EDGE
 } edge_type_t;
@@ -101,7 +102,7 @@ private:
 	loc_set_t * write_locations;
 
 	/* Keeps track of locations that have the same values written to */
-	HashTable<uint64_t, loc_set_t *, uint64_t, 0> * val_loc_map;
+	HashTable<uint64_t, loc_set_t *, uint64_t, 0, snapshot_malloc, snapshot_calloc, snapshot_free, int64_hash> * val_loc_map;
 
 	/* Keeps track of locations that may share the same value as key, deduced from val_loc_map */
 	HashTable<void *, loc_set_t *, uintptr_t, 0> * loc_may_equal_map;
diff --git a/hashfunction.cc b/hashfunction.cc
new file mode 100644
index 00000000..eca9cafa
--- /dev/null
+++ b/hashfunction.cc
@@ -0,0 +1,12 @@
+#include "hashfunction.h"
+
+/* Hash function for 64-bit integers */
+unsigned int int64_hash(uint64_t key) {
+	key = (~key) + (key << 18); // key = (key << 18) - key - 1;
+	key = key ^ (key >> 31);
+	key = key * 21; // key = (key + (key << 2)) + (key << 4);
+	key = key ^ (key >> 11);
+	key = key + (key << 6);
+	key = key ^ (key >> 22);
+	return (unsigned int) key;
+}
diff --git a/hashfunction.h b/hashfunction.h
new file mode 100644
index 00000000..2f0627d4
--- /dev/null
+++ b/hashfunction.h
@@ -0,0 +1,8 @@
+#ifndef __HASH_FUNCTION__
+#define __HASH_FUNCTION__
+
+#include <stdint.h>
+
+unsigned int int64_hash(uint64_t key);
+
+#endif
-- 
2.34.1