Skip to content

Commit 69786bb

Browse files
nitsanwnitsanw
committed
Fix #205 : remove/put do not have getAndSet semantics expected from CM
1 parent cfd5ae8 commit 69786bb

2 files changed

Lines changed: 179 additions & 60 deletions

File tree

‎jctools-core/src/main/java/org/jctools/maps/NonBlockingHashMap.java‎

Lines changed: 76 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -13,14 +13,15 @@
1313
*/
1414
package org.jctools.maps;
1515

16+
import org.jctools.util.RangeUtil;
17+
1618
import java.io.IOException;
1719
import java.io.Serializable;
1820
import java.lang.reflect.Field;
1921
import java.util.*;
2022
import java.util.concurrent.ConcurrentMap;
2123
import java.util.concurrent.atomic.AtomicLongFieldUpdater;
2224
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
23-
import org.jctools.util.RangeUtil;
2425

2526
import static org.jctools.util.UnsafeAccess.UNSAFE;
2627

@@ -711,72 +712,87 @@ private static final Object putIfMatch( final NonBlockingHashMap topmap, final O
711712
idx = (idx+1)&(len-1); // Reprobe!
712713
} // End of spinning till we get a Key slot
713714

714-
// ---
715-
// Found the proper Key slot, now update the matching Value slot. We
716-
// never put a null, so Value slots monotonically move from null to
717-
// not-null (deleted Values use Tombstone). Thus if 'V' is null we
718-
// fail this fast cutout and fall into the check for table-full.
719-
if( putval == V ) return V; // Fast cutout for no-change
720-
721-
// See if we want to move to a new table (to avoid high average re-probe
722-
// counts). We only check on the initial set of a Value from null to
723-
// not-null (i.e., once per key-insert). Of course we got a 'free' check
724-
// of newkvs once per key-compare (not really free, but paid-for by the
725-
// time we get here).
726-
if( newkvs == null && // New table-copy already spotted?
727-
// Once per fresh key-insert check the hard way
728-
((V == null && chm.tableFull(reprobe_cnt,len)) ||
729-
// Or we found a Prime, but the JMM allowed reordering such that we
730-
// did not spot the new table (very rare race here: the writing
731-
// thread did a CAS of _newkvs then a store of a Prime. This thread
732-
// reads the Prime, then reads _newkvs - but the read of Prime was so
733-
// delayed (or the read of _newkvs was so accelerated) that they
734-
// swapped and we still read a null _newkvs. The resize call below
735-
// will do a CAS on _newkvs forcing the read.
736-
V instanceof Prime) )
737-
newkvs = chm.resize(topmap,kvs); // Force the new table copy to start
738-
// See if we are moving to a new table.
739-
// If so, copy our slot and retry in the new table.
740-
if( newkvs != null )
741-
return putIfMatch(topmap,chm.copy_slot_and_check(topmap,kvs,idx,expVal),key,putval,expVal);
715+
while ( true ) { // Spin till we insert a value
716+
// ---
717+
// Found the proper Key slot, now update the matching Value slot. We
718+
// never put a null, so Value slots monotonically move from null to
719+
// not-null (deleted Values use Tombstone). Thus if 'V' is null we
720+
// fail this fast cutout and fall into the check for table-full.
721+
if( putval == V ) return V; // Fast cutout for no-change
722+
723+
// See if we want to move to a new table (to avoid high average re-probe
724+
// counts). We only check on the initial set of a Value from null to
725+
// not-null (i.e., once per key-insert). Of course we got a 'free' check
726+
// of newkvs once per key-compare (not really free, but paid-for by the
727+
// time we get here).
728+
if( newkvs == null && // New table-copy already spotted?
729+
// Once per fresh key-insert check the hard way
730+
((V == null && chm.tableFull(reprobe_cnt,len)) ||
731+
// Or we found a Prime, but the JMM allowed reordering such that we
732+
// did not spot the new table (very rare race here: the writing
733+
// thread did a CAS of _newkvs then a store of a Prime. This thread
734+
// reads the Prime, then reads _newkvs - but the read of Prime was so
735+
// delayed (or the read of _newkvs was so accelerated) that they
736+
// swapped and we still read a null _newkvs. The resize call below
737+
// will do a CAS on _newkvs forcing the read.
738+
V instanceof Prime) )
739+
newkvs = chm.resize(topmap,kvs); // Force the new table copy to start
740+
// See if we are moving to a new table.
741+
// If so, copy our slot and retry in the new table.
742+
if( newkvs != null )
743+
return putIfMatch(topmap,chm.copy_slot_and_check(topmap,kvs,idx,expVal),key,putval,expVal);
742744

743-
// ---
744-
// We are finally prepared to update the existing table
745-
assert !(V instanceof Prime);
746-
747-
// Must match old, and we do not? Then bail out now. Note that either V
748-
// or expVal might be TOMBSTONE. Also V can be null, if we've never
749-
// inserted a value before. expVal can be null if we are called from
750-
// copy_slot.
751-
752-
if( expVal != NO_MATCH_OLD && // Do we care about expected-Value at all?
753-
V != expVal && // No instant match already?
754-
(expVal != MATCH_ANY || V == TOMBSTONE || V == null) &&
755-
!(V==null && expVal == TOMBSTONE) && // Match on null/TOMBSTONE combo
756-
(expVal == null || !expVal.equals(V)) ) // Expensive equals check at the last
757-
return V; // Do not update!
758-
759-
// Actually change the Value in the Key,Value pair
760-
if( CAS_val(kvs, idx, V, putval ) ) {
761-
// CAS succeeded - we did the update!
762-
// Both normal put's and table-copy calls putIfMatch, but table-copy
763-
// does not (effectively) increase the number of live k/v pairs.
764-
if( expVal != null ) {
765-
// Adjust sizes - a striped counter
766-
if( (V == null || V == TOMBSTONE) && putval != TOMBSTONE ) chm._size.add( 1);
767-
if( !(V == null || V == TOMBSTONE) && putval == TOMBSTONE ) chm._size.add(-1);
768-
}
769-
} else { // Else CAS failed
745+
// ---
746+
// We are finally prepared to update the existing table
747+
assert !(V instanceof Prime);
748+
749+
// Must match old, and we do not? Then bail out now. Note that either V
750+
// or expVal might be TOMBSTONE. Also V can be null, if we've never
751+
// inserted a value before. expVal can be null if we are called from
752+
// copy_slot.
753+
if( expVal != NO_MATCH_OLD && // Do we care about expected-Value at all?
754+
V != expVal && // No instant match already?
755+
(expVal != MATCH_ANY || V == TOMBSTONE || V == null) &&
756+
!(V==null && expVal == TOMBSTONE) && // Match on null/TOMBSTONE combo
757+
(expVal == null || !expVal.equals(V)) ) // Expensive equals check at the last
758+
return V; // Do not update!
759+
760+
// Actually change the Value in the Key,Value pair
761+
if( CAS_val(kvs, idx, V, putval ) ) break;
762+
763+
// CAS failed
764+
// Because we have no witness, we do not know why it failed.
765+
// Indeed, by the time we look again the value under test might have flipped
766+
// a thousand times and now be the expected value (despite the CAS failing).
767+
// Check for the never-succeed condition of a Prime value and jump to any
768+
// nested table, or else just re-run.
769+
770+
// We would not need this load at all if CAS returned the value on which
771+
// the CAS failed (AKA witness). The new CAS semantics are supported via
772+
// VarHandle in JDK9.
770773
V = val(kvs,idx); // Get new value
774+
771775
// If a Prime'd value got installed, we need to re-run the put on the
772776
// new table. Otherwise we lost the CAS to another racing put.
773-
// Simply retry from the start.
774777
if( V instanceof Prime )
775778
return putIfMatch(topmap,chm.copy_slot_and_check(topmap,kvs,idx,expVal),key,putval,expVal);
779+
780+
// Simply retry from the start.
781+
// NOTE: need the fence, since otherwise 'val(kvs,idx)' load could be hoisted
782+
// out of loop.
783+
int dummy = DUMMY_VOLATILE;
784+
}
785+
786+
// CAS succeeded - we did the update!
787+
// Both normal put's and table-copy calls putIfMatch, but table-copy
788+
// does not (effectively) increase the number of live k/v pairs.
789+
if( expVal != null ) {
790+
// Adjust sizes - a striped counter
791+
if( (V == null || V == TOMBSTONE) && putval != TOMBSTONE ) chm._size.add( 1);
792+
if( !(V == null || V == TOMBSTONE) && putval == TOMBSTONE ) chm._size.add(-1);
776793
}
777-
// Win or lose the CAS, we are done. If we won then we know the update
778-
// happened as expected. If we lost, it means "we won but another thread
779-
// immediately stomped our update with no chance of a reader reading".
794+
795+
// We won; we know the update happened as expected.
780796
return (V==null && expVal!=null) ? TOMBSTONE : V;
781797
}
782798

‎jctools-core/src/test/java/org/jctools/maps/KeyAtomicityTest.java‎

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
package org.jctools.maps;
2+
3+
import org.junit.Test;
4+
5+
import java.util.*;
6+
import java.util.concurrent.CountDownLatch;
7+
import java.util.concurrent.atomic.AtomicBoolean;
8+
9+
import static org.junit.Assert.assertEquals;
10+
11+
public class KeyAtomicityTest
12+
{
13+
static final int THREAD_SEGMENT = 1000000;
14+
15+
@Test
16+
public void putReturnValuesAreDistinct() throws Exception
17+
{
18+
Map<String, Long> map = new NonBlockingHashMap<>();
19+
map.put("K", -1l);
20+
int processors = Runtime.getRuntime().availableProcessors();
21+
CountDownLatch ready = new CountDownLatch(processors);
22+
CountDownLatch start = new CountDownLatch(1);
23+
CountDownLatch done = new CountDownLatch(processors);
24+
AtomicBoolean keepRunning = new AtomicBoolean(true);
25+
PutKey[] putKeys = new PutKey[processors];
26+
for (int i = 0; i < processors; i++)
27+
{
28+
putKeys[i] = new PutKey(map, "K", keepRunning, ready, start, done, i * THREAD_SEGMENT);
29+
Thread t = new Thread(putKeys[i]);
30+
t.setName("Putty McPutkey-"+i);
31+
t.start();
32+
}
33+
ready.await();
34+
start.countDown();
35+
Thread.sleep(1000);
36+
keepRunning.set(false);
37+
done.await();
38+
Set<Long> values = new HashSet((int)(processors*THREAD_SEGMENT));
39+
long totalKeys = 0;
40+
for (PutKey putKey : putKeys)
41+
{
42+
values.addAll(putKey.values);
43+
totalKeys += putKey.endIndex - putKey.startIndex;
44+
}
45+
assertEquals(totalKeys, values.size());
46+
}
47+
48+
static class PutKey implements Runnable
49+
{
50+
final Map<String, Long> map;
51+
final String key;
52+
final AtomicBoolean keepRunning;
53+
final CountDownLatch ready;
54+
final CountDownLatch start;
55+
final CountDownLatch done;
56+
final int startIndex;
57+
int endIndex;
58+
59+
List<Long> values = new ArrayList<>(THREAD_SEGMENT);
60+
61+
PutKey(
62+
Map<String, Long> map,
63+
String key,
64+
AtomicBoolean keepRunning, CountDownLatch ready,
65+
CountDownLatch start,
66+
CountDownLatch done,
67+
int startIndex)
68+
{
69+
this.map = map;
70+
this.key = key;
71+
this.keepRunning = keepRunning;
72+
this.ready = ready;
73+
this.start = start;
74+
this.done = done;
75+
this.startIndex = startIndex;
76+
assert startIndex >= 0 && startIndex + THREAD_SEGMENT > 0;
77+
}
78+
79+
@Override
80+
public void run()
81+
{
82+
ready.countDown();
83+
try
84+
{
85+
start.await();
86+
}
87+
catch (InterruptedException e)
88+
{
89+
e.printStackTrace();
90+
return;
91+
}
92+
long limit = startIndex + THREAD_SEGMENT;
93+
long v = startIndex;
94+
String k = key;
95+
for (; v < limit && keepRunning.get(); v++)
96+
{
97+
values.add(map.put(k, v));
98+
}
99+
endIndex = (int) v;
100+
done.countDown();
101+
}
102+
}
103+
}

0 commit comments

Comments
 (0)