switch everything over to our own hashtable

give us a calloc to use from our code

diff --git a/hashtable.h b/hashtable.h
index e59a995fd92347a361a785a2d5e36c646b1a7656..c877d9f1753d9dc0bd3e0a7d2dc4181f7ac636c4 100644 (file)
--- a/hashtable.h
+++ b/hashtable.h
@@ -18,7 +18,7 @@ template<typename _Key, typename _Val>
 /** Hashtable class.  By default it is snapshotting, but you can pass
                in your own allocation functions. */
 
-template<typename _Key, typename _Val, typename _KeyInt, int _Shift, void * (* _malloc)(size_t)=malloc, void * (* _calloc)(size_t, size_t)=calloc, void (*_free)(void *)=free>
+template<typename _Key, typename _Val, typename _KeyInt, int _Shift=0, void * (* _malloc)(size_t)=malloc, void * (* _calloc)(size_t, size_t)=calloc, void (*_free)(void *)=free>
        class HashTable {
  public:
        HashTable(unsigned int initialcapacity=1024, double factor=0.5) {
@@ -100,6 +100,32 @@ template<typename _Key, typename _Val, typename _KeyInt, int _Shift, void * (* _
                table[(((_KeyInt)key)&mask)>>_Shift]=newptr;
        }
 
+       /** Put a key entry into the table. */
+  _Val * ensureptr(_Key key) {
+               if(size > threshold) {
+                       //Resize
+                 unsigned int newsize = capacity << 1;
+                 resize(newsize);
+         }
+
+         struct hashlistnode<_Key,_Val> *ptr = table[(((_KeyInt)key) & mask)>>_Shift];
+               size++;
+               struct hashlistnode<_Key,_Val> *search = ptr;
+
+               while(search!=NULL) {
+                       if (search->key==key) {
+                               return &search->val;
+                       }
+                       search=search->next;
+               }
+
+               struct hashlistnode<_Key,_Val> *newptr=(struct hashlistnode<_Key,_Val> *)new struct hashlistnode<_Key,_Val>;
+               newptr->key=key;
+               newptr->next=ptr;
+               table[(((_KeyInt)key)&mask)>>_Shift]=newptr;
+               return &newptr->val;
+       }
+
        /** Lookup the corresponding value for the given key. */
        _Val get(_Key key) {
                struct hashlistnode<_Key,_Val> *search = table[(((_KeyInt)key) & mask)>>_Shift];
@@ -113,6 +139,19 @@ template<typename _Key, typename _Val, typename _KeyInt, int _Shift, void * (* _
                return (_Val)0;
        }
 
+       /** Lookup the corresponding value for the given key. */
+       _Val * getptr(_Key key) {
+               struct hashlistnode<_Key,_Val> *search = table[(((_KeyInt)key) & mask)>>_Shift];
+
+               while(search!=NULL) {
+                       if (search->key==key) {
+                               return & search->val;
+                       }
+                       search=search->next;
+               }
+               return (_Val *) NULL;
+       }
+
        /** Check whether the table contains a value for the given key. */
        bool contains(_Key key) {
                struct hashlistnode<_Key,_Val> *search = table[(((_KeyInt)key) & mask)>>_Shift];

diff --git a/model.cc b/model.cc
index e18fda15248399cda859339296447ca2b35bd9f5..de8f10c0c3efb9d0d8e0cd660b61633b79e10e46 100644 (file)
--- a/model.cc
+++ b/model.cc
@@ -27,9 +27,9 @@ ModelChecker::ModelChecker()
        diverge(NULL),
        nextThread(THREAD_ID_T_NONE),
        action_trace(new action_list_t()),
-       thread_map(new std::map<int, Thread *>),
-       obj_map(new std::map<const void *, action_list_t>()),
-       obj_thrd_map(new std::map<void *, std::vector<action_list_t> >()),
+       thread_map(new HashTable<int, Thread *, int>()),
+       obj_map(new HashTable<const void *, action_list_t, uintptr_t, 4>()),
+       obj_thrd_map(new HashTable<void *, std::vector<action_list_t>, uintptr_t, 4 >()),
        thrd_last_action(new std::vector<ModelAction *>(1)),
        node_stack(new NodeStack()),
        next_backtrack(NULL),
@@ -40,9 +40,9 @@ ModelChecker::ModelChecker()
 /** @brief Destructor */
 ModelChecker::~ModelChecker()
 {
-       std::map<int, Thread *>::iterator it;
+       /*      std::map<int, Thread *>::iterator it;
        for (it = thread_map->begin(); it != thread_map->end(); it++)
-               delete (*it).second;
+       delete (*it).second;*/
        delete thread_map;
 
        delete obj_thrd_map;
@@ -102,7 +102,7 @@ Thread * ModelChecker::schedule_next_thread()
        Thread *t;
        if (nextThread == THREAD_ID_T_NONE)
                return NULL;
-       t = (*thread_map)[id_to_int(nextThread)];
+       t = thread_map->get(id_to_int(nextThread));
 
        ASSERT(t != NULL);
 
@@ -190,7 +190,7 @@ ModelAction * ModelChecker::get_last_conflict(ModelAction *act)
                        return NULL;
        }
        /* linear search: from most recent to oldest */
-       action_list_t *list = &(*obj_map)[act->get_location()];
+       action_list_t *list = obj_map->ensureptr(act->get_location());
        action_list_t::reverse_iterator rit;
        for (rit = list->rbegin(); rit != list->rend(); rit++) {
                ModelAction *prev = *rit;
@@ -349,7 +349,7 @@ ModelAction * ModelChecker::process_rmw(ModelAction * act) {
  * @param rf The action that curr reads from. Must be a write.
  */
 void ModelChecker::r_modification_order(ModelAction * curr, const ModelAction *rf) {
-       std::vector<action_list_t> *thrd_lists = &(*obj_thrd_map)[curr->get_location()];
+       std::vector<action_list_t> *thrd_lists = obj_thrd_map->ensureptr(curr->get_location());
        unsigned int i;
        ASSERT(curr->is_read());
 
@@ -381,7 +381,7 @@ void ModelChecker::r_modification_order(ModelAction * curr, const ModelAction *r
  * @param curr The current action. Must be a write.
  */
 void ModelChecker::w_modification_order(ModelAction * curr) {
-       std::vector<action_list_t> *thrd_lists = &(*obj_thrd_map)[curr->get_location()];
+       std::vector<action_list_t> *thrd_lists = obj_thrd_map->ensureptr(curr->get_location());
        unsigned int i;
        ASSERT(curr->is_write());
 
@@ -425,9 +425,9 @@ void ModelChecker::add_action_to_lists(ModelAction *act)
        int tid = id_to_int(act->get_tid());
        action_trace->push_back(act);
 
-       (*obj_map)[act->get_location()].push_back(act);
+       obj_map->ensureptr(act->get_location())->push_back(act);
 
-       std::vector<action_list_t> *vec = &(*obj_thrd_map)[act->get_location()];
+       std::vector<action_list_t> *vec = obj_thrd_map->ensureptr(act->get_location());
        if (tid >= (int)vec->size())
                vec->resize(next_thread_id);
        (*vec)[tid].push_back(act);
@@ -453,7 +453,7 @@ ModelAction * ModelChecker::get_last_action(thread_id_t tid)
  */
 ModelAction * ModelChecker::get_last_seq_cst(const void *location)
 {
-       action_list_t *list = &(*obj_map)[location];
+       action_list_t *list = obj_map->ensureptr(location);
        /* Find: max({i in dom(S) | seq_cst(t_i) && isWrite(t_i) && samevar(t_i, t)}) */
        action_list_t::reverse_iterator rit;
        for (rit = list->rbegin(); rit != list->rend(); rit++)
@@ -488,7 +488,7 @@ ClockVector * ModelChecker::get_cv(thread_id_t tid) {
  */
 void ModelChecker::build_reads_from_past(ModelAction *curr)
 {
-       std::vector<action_list_t> *thrd_lists = &(*obj_thrd_map)[curr->get_location()];
+       std::vector<action_list_t> *thrd_lists = obj_thrd_map->ensureptr(curr->get_location());
        unsigned int i;
        ASSERT(curr->is_read());
 
@@ -580,7 +580,7 @@ void ModelChecker::print_summary(void)
 
 int ModelChecker::add_thread(Thread *t)
 {
-       (*thread_map)[id_to_int(t->get_id())] = t;
+       thread_map->put(id_to_int(t->get_id()), t);
        scheduler->add_thread(t);
        return 0;
 }

diff --git a/model.h b/model.h
index 8593b98f06a186aa7e297cd661219edf1c69c264..b6099c69750b066d74d1d4a566834237edf3b097 100644 (file)
--- a/model.h
+++ b/model.h
@@ -6,7 +6,6 @@
 #define __MODEL_H__
 
 #include <list>
-#include <map>
 #include <vector>
 #include <cstddef>
 #include <ucontext.h>
@@ -46,7 +45,7 @@ public:
 
        int add_thread(Thread *t);
        void remove_thread(Thread *t);
-       Thread * get_thread(thread_id_t tid) { return (*thread_map)[id_to_int(tid)]; }
+       Thread * get_thread(thread_id_t tid) { return thread_map->get(id_to_int(tid)); }
 
        thread_id_t get_next_id();
        int get_num_threads();
@@ -93,13 +92,13 @@ private:
 
        ucontext_t *system_context;
        action_list_t *action_trace;
-       std::map<int, Thread *> *thread_map;
+       HashTable<int, Thread *, int> *thread_map;
 
        /** Per-object list of actions. Maps an object (i.e., memory location)
         * to a trace of all actions performed on the object. */
-       std::map<const void *, action_list_t> *obj_map;
+       HashTable<const void *, action_list_t, uintptr_t, 4> *obj_map;
 
-       std::map<void *, std::vector<action_list_t> > *obj_thrd_map;
+       HashTable<void *, std::vector<action_list_t>, uintptr_t, 4 > *obj_thrd_map;
        std::vector<ModelAction *> *thrd_last_action;
        NodeStack *node_stack;
        ModelAction *next_backtrack;

diff --git a/mymemory.cc b/mymemory.cc
index e8518182c55a71800637c981f1d3ad0db0cc3b2d..a365bb4c9c43894c4134b2676486a1f7b11577b4 100644 (file)
--- a/mymemory.cc
+++ b/mymemory.cc
@@ -13,10 +13,37 @@ int howManyFreed = 0;
 static mspace sStaticSpace = NULL;
 #endif
 
+/** Non-snapshotting calloc for our use. */
+void *MYCALLOC(size_t count, size_t size) {
+#if USE_MPROTECT_SNAPSHOT
+       static void *(*callocp)(size_t count, size_t size)=NULL;
+       char *error;
+       void *ptr;
+
+       /* get address of libc malloc */
+       if (!callocp) {
+               callocp = ( void * ( * )( size_t, size_t ) )dlsym(RTLD_NEXT, "calloc");
+               if ((error = dlerror()) != NULL) {
+                       fputs(error, stderr);
+                       exit(EXIT_FAILURE);
+               }
+       }
+       ptr = callocp(count, size);
+       return ptr;
+#else
+       if( !snapshotrecord) {
+               createSharedMemory();
+       }
+       if( NULL == sStaticSpace )
+               sStaticSpace = create_mspace_with_base( ( void * )( snapshotrecord->mSharedMemoryBase ), SHARED_MEMORY_DEFAULT -sizeof( struct SnapShot ), 1 );
+       return mspace_calloc( sStaticSpace, count, size );
+#endif
+}
+
 /** Non-snapshotting malloc for our use. */
 void *MYMALLOC(size_t size) {
 #if USE_MPROTECT_SNAPSHOT
-       static void *(*mallocp)(size_t size);
+       static void *(*mallocp)(size_t size)=NULL;
        char *error;
        void *ptr;
 

diff --git a/mymemory.h b/mymemory.h
index fb6df12cd6791e85b1553d3c51da3ba89e67e2e2..4c44f5be514c4e8fdd9344f2cee7fb939ca8a3ad 100644 (file)
--- a/mymemory.h
+++ b/mymemory.h
@@ -28,6 +28,7 @@
 #define SNAPSHOTALLOC
 
 void *MYMALLOC(size_t size);
+void *MYCALLOC(size_t count, size_t size);
 void MYFREE(void *ptr);
 
 void system_free( void * ptr );

diff --git a/snapshot.cc b/snapshot.cc
index 9020bb70e840ab445ab059fe3a0a2cbda7fb7653..95a6593a44829c1ae4c1152203b2bbee1162cb94 100644 (file)
--- a/snapshot.cc
+++ b/snapshot.cc
@@ -3,7 +3,7 @@
 #include <unistd.h>
 #include <signal.h>
 #include <stdlib.h>
-#include <map>
+#include "hashtable.h"
 #include <cstring>
 #include <cstdio>
 #include "snapshot.h"
@@ -281,7 +281,7 @@ snapshot_id takeSnapshot( ){
  */
 void rollBack( snapshot_id theID ){
 #if USE_MPROTECT_SNAPSHOT
-       std::map< void *, bool, std::less< void * >, MyAlloc< std::pair< const void *, bool > > > duplicateMap;
+       HashTable< void *, bool, uintptr_t, 4, MYMALLOC, MYCALLOC, MYFREE> duplicateMap;
        for(unsigned int region=0; region<snapshotrecord->lastRegion;region++) {
                if( mprotect(snapshotrecord->regionsToSnapShot[region].basePtr, snapshotrecord->regionsToSnapShot[region].sizeInPages*sizeof(struct SnapShotPage), PROT_READ | PROT_WRITE ) == -1 ){
                        perror("mprotect");
@@ -290,14 +290,8 @@ void rollBack( snapshot_id theID ){
                }
        }
        for(unsigned int page=snapshotrecord->snapShots[theID].firstBackingPage; page<snapshotrecord->lastBackingPage; page++) {
-               bool oldVal = false;
-               if( duplicateMap.find( snapshotrecord->backingRecords[page].basePtrOfPage ) != duplicateMap.end() ){
-                       oldVal = true;
-               }
-               else{
-                       duplicateMap[ snapshotrecord->backingRecords[page].basePtrOfPage ] = true;
-               }
-               if(  !oldVal ){
+               if( !duplicateMap.contains(snapshotrecord->backingRecords[page].basePtrOfPage )) {
+                       duplicateMap.put(snapshotrecord->backingRecords[page].basePtrOfPage, true);
                        memcpy(snapshotrecord->backingRecords[page].basePtrOfPage, &snapshotrecord->backingStore[page], sizeof(struct SnapShotPage));
                }
        }