X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=concurrent-hashmap%2Fhashmap.h;h=8e6f196cb0e8c73d8a02f9dee01b152dddea7cc9;hb=1438eb7c0715e53611a717e593bfa3fe1bd30588;hp=6ea5e769bd09b667f7bc3424dc4a4917010946c8;hpb=fce370a6252cdea0ae220afd0c38160018658c5d;p=model-checker-benchmarks.git diff --git a/concurrent-hashmap/hashmap.h b/concurrent-hashmap/hashmap.h index 6ea5e76..8e6f196 100644 --- a/concurrent-hashmap/hashmap.h +++ b/concurrent-hashmap/hashmap.h @@ -14,6 +14,9 @@ #include #include +#include "common.h" +#include "sc_annotation.h" + #define relaxed memory_order_relaxed #define release memory_order_release #define acquire memory_order_acquire @@ -64,6 +67,12 @@ struct Value { { } + + bool equals(Value *other) { + if (!other) + return false; + return vX == other->vX && vY == other->vY && vZ == other->vZ; + } }; class Entry { @@ -110,7 +119,7 @@ class HashMap { static const int SEGMENT_MASK = CONCURRENCY_LEVEL - 1; - Segment segments[CONCURRENCY_LEVEL]; + Segment *segments[CONCURRENCY_LEVEL]; static const int DEFAULT_INITIAL_CAPACITY = 16; @@ -123,6 +132,9 @@ class HashMap { for (int i = 0; i < capacity; i++) { atomic_init(&table[i], NULL); } + for (int i = 0; i < CONCURRENCY_LEVEL; i++) { + segments[i] = new Segment; + } } int hashKey(Key *x) { @@ -137,7 +149,8 @@ class HashMap { } Value* get(Key *key) { - int hash = hashKey(key); // throws null pointer exception if key null + MODEL_ASSERT (key); + int hash = hashKey(key); // Try first without locking... atomic *tab = table; @@ -147,7 +160,16 @@ class HashMap { Value *res = NULL; // Should be a load acquire + // This load action here makes it problematic for the SC analysis, what + // we need to do is as follows: if the get() method ever acquires the + // lock, we ignore this operation for the SC analysis, and otherwise we + // take it into consideration + + //SC_BEGIN(); Entry *firstPtr = first->load(acquire); + //SC_KEEP(); + //SC_END(); + e = firstPtr; while (e != NULL) { if (e->hash == hash && eq(key, e->key)) { @@ -156,70 +178,130 @@ class HashMap { return res; else break; - // Loading the next entry - e = e->next.load(acquire); } + // Loading the next entry + e = e->next.load(acquire); } // Recheck under synch if key apparently not there or interference - Segment seg = segments[hash & SEGMENT_MASK]; - seg.lock(); // Critical region begins + Segment *seg = segments[hash & SEGMENT_MASK]; + seg->lock(); // Critical region begins // Not considering resize now, so ignore the reload of table... - atomic *newFirst = &tab[index]; // Synchronized by locking, no need to be load acquire - Entry *newFirstPtr = newFirst->load(relaxed); + Entry *newFirstPtr = first->load(relaxed); if (e != NULL || firstPtr != newFirstPtr) { e = newFirstPtr; while (e != NULL) { if (e->hash == hash && eq(key, e->key)) { res = e->value.load(seq_cst); + seg->unlock(); // Critical region ends return res; } // Synchronized by locking e = e->next.load(relaxed); } } - seg.unlock(); // Critical region ends + seg->unlock(); // Critical region ends return NULL; } Value* put(Key *key, Value *value) { - // Don't allow NULL value - //ASSERT (value != NULL); + // Don't allow NULL key or value + MODEL_ASSERT (key && value); int hash = hashKey(key); - Segment seg = segments[hash & SEGMENT_MASK]; + Segment *seg = segments[hash & SEGMENT_MASK]; atomic *tab; - seg.lock(); // Critical region begins + seg->lock(); // Critical region begins tab = table; int index = hash & (capacity - 1); atomic *first = &tab[index]; Entry *e; - Value *res = NULL; + Value *oldValue = NULL; // The written of the entry is synchronized by locking Entry *firstPtr = first->load(relaxed); e = firstPtr; while (e != NULL) { if (e->hash == hash && eq(key, e->key)) { - // FIXME: This could be an acquire?? - res = e->value.load(acquire); + // FIXME: This could be a relaxed (because locking synchronize + // with the previous put())?? + oldValue = e->value.load(acquire); e->value.store(value, seq_cst); - seg.unlock(); // Don't forget to unlock before return - return res; + seg->unlock(); // Don't forget to unlock before return + return oldValue; } + // Synchronized by locking + e = e->next.load(relaxed); } // Add to front of list Entry *newEntry = new Entry(hash, key, value, firstPtr); // Publish the newEntry to others - tab[index].store(newEntry, release); - seg.unlock(); // Critical region ends + first->store(newEntry, release); + seg->unlock(); // Critical region ends return NULL; } + + Value* remove(Key *key, Value *value) { + MODEL_ASSERT (key); + int hash = hashKey(key); + Segment *seg = segments[hash & SEGMENT_MASK]; + atomic *tab; + + seg->lock(); // Critical region begins + tab = table; + int index = hash & (capacity - 1); + + atomic *first = &tab[index]; + Entry *e; + Value *oldValue = NULL; + + // The written of the entry is synchronized by locking + Entry *firstPtr = first->load(relaxed); + e = firstPtr; + + while (true) { + if (e != NULL) { + seg->unlock(); // Don't forget to unlock + return NULL; + } + if (e->hash == hash && eq(key, e->key)) + break; + // Synchronized by locking + e = e->next.load(relaxed); + } + + // FIXME: This could be a relaxed (because locking synchronize + // with the previous put())?? + oldValue = e->value.load(acquire); + // If the value parameter is NULL, we will remove the entry anyway + if (value != NULL && value->equals(oldValue)) { + seg->unlock(); + return NULL; + } + + // Force the get() to grab the lock and retry + e->value.store(NULL, relaxed); + + // The strategy to remove the entry is to keep the entries after the + // removed one and copy the ones before it + Entry *head = e->next.load(relaxed); + Entry *p; + p = first->load(relaxed); + while (p != e) { + head = new Entry(p->hash, p->key, p->value.load(relaxed), head); + p = p->next.load(relaxed); + } + + // Publish the new head to readers + first->store(head, release); + seg->unlock(); // Critical region ends + return oldValue; + } }; #endif