Add a hash function for 64-bit int to improve the performance of val_loc_map in FuncN...
authorweiyu <weiyuluo1232@gmail.com>
Mon, 21 Oct 2019 22:08:34 +0000 (15:08 -0700)
committerweiyu <weiyuluo1232@gmail.com>
Mon, 21 Oct 2019 22:08:34 +0000 (15:08 -0700)
Makefile
funcnode.cc
funcnode.h
hashfunction.cc [new file with mode: 0644]
hashfunction.h [new file with mode: 0644]

index f9d3424..4329fc4 100644 (file)
--- 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
index 8cb39da..c739a28 100644 (file)
@@ -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);
index 0bcc73b..fab4db5 100644 (file)
@@ -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 (file)
index 0000000..eca9caf
--- /dev/null
@@ -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 (file)
index 0000000..2f0627d
--- /dev/null
@@ -0,0 +1,8 @@
+#ifndef __HASH_FUNCTION__
+#define __HASH_FUNCTION__
+
+#include <stdint.h>
+
+unsigned int int64_hash(uint64_t key);
+
+#endif