Add a hash function for 64-bit int to improve the performance of val_loc_map in FuncN...

diff --git a/Makefile b/Makefile
index f9d34249619660effdb7d03b74d65d54463259fb..4329fc46d50542fd0106c184f7c2a3ab705ea878 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 \
           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
 
 CPPFLAGS += -Iinclude -I.
 LDFLAGS := -ldl -lrt -rdynamic -lpthread

diff --git a/funcnode.cc b/funcnode.cc
index 8cb39da9697efbbe0f7a8da397c2988f314f2c57..c739a284a0d4b0c7aaac36cd54eb480576714d73 100644 (file)
--- 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);
 
        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();
        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();
        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();
        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();
        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();
                        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);
        }
 
        curr_pred->set_exit(predicate_tree_exit);

diff --git a/funcnode.h b/funcnode.h
index 0bcc73b58e2f59324e4d6aefd99d49816f6ff257..fab4db50903af3bd5e4146b18b42ce5ce135c01c 100644 (file)
--- a/funcnode.h
+++ b/funcnode.h
@@ -2,12 +2,13 @@
 #define __FUNCNODE_H__
 
 #include "hashset.h"
 #define __FUNCNODE_H__
 
 #include "hashset.h"

+#include "hashfunction.h"

 #include "classlist.h"
 #include "threads-model.h"
 
 #define MAX_DIST 10
 #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;
 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 */
        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;
 
        /* 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
+++ 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 (file)
index 0000000..2f0627d
--- /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