RFR(trivial): 8222394: HashMap.compute() throws CME on an empty Map if clear() called concurrently

Wed Apr 24 23:48:23 UTC 2019

Hi Patrick,

I guess I'm not sure what you're proposing here. You've updated the patch; are 
you proposing that this change be integrated?

Or are you posting code changes, not as a proposal to integrate, but merely to 
serve as a discussion point about the policy for throwing 
ConcurrentModificationException?

Either way (or something else) is fine; I just don't want to run off in one 
direction if you had intended the other.

s'marks

On 4/15/19 3:51 AM, Patrick Zhang OS wrote:
> Hi Stuart,
> 
> Thanks. I intentionally modified the map in remapping functions, just like those tests in http://hg.openjdk.java.net/jdk/jdk/file/00c0906bf4d1/test/jdk/java/util/Map/FunctionalCMEs.java. My original tests were: create two threads, modify or perform read-only operations in each, and verify those CMEs. There seems some inconsistencies:
> 1. clear() would modify the map completely, so it can be more 'defensible' (Martin mentioned so in Jira), while other modifying functions like put()/remove()/merge() are 'weaker', so ++modCount happens conditionally, say there would be really some structural modifications in map.
> 2. compute()/computeIfAbsent() throws CME almost unconditionally, while functions like forEach()/computeIfPresent()/iterator.next() are touching the map content practically so these are wrapped by if-clauses.
> 
> So the concern is how to undertand "throw CME on a best-effort basis",
> if I want to try best to detect the risk of bugs in program, unconditionlly throwing CME can be the right way to go, e.g. do ++modCount in removeNode() without telling if the removing would really occur,
> if I want to make it more logically rigorous, we might need this: http://cr.openjdk.java.net/~qpzhang/8222394/webrev.02 for compute()/computeIfAbsent(). Centainly I know it has to afford the risk of missing bugs.
> 
> Regards
> Patrick
> 
> -----Original Message-----
> From: Stuart Marks <stuart.marks at oracle.com>
> Sent: Saturday, April 13, 2019 4:15 AM
> To: Patrick Zhang OS <patrick at os.amperecomputing.com>
> Cc: core-libs-dev <core-libs-dev at openjdk.java.net>
> Subject: Re: RFR(trivial): 8222394: HashMap.compute() throws CME on an empty Map if clear() called concurrently
> 
> [I'm about to leave for a week's vacation, so I won't be able to respond further until after I return]
> 
> Hi Patrick,
> 
> A bit of background about my thinking on this proposal.
> 
> The Collections Framework has a set of weird edge cases ("tricky", as you say) that I'll describe as "state-dependent" behavior, where operations that seem illegal on their face might or might not throw an exception depending on the current state of the system. The current state potentially depends on everything that happened previously, including input to the program.
> 
> As an example of this, consider the following code snippet:
> 
>       List<String> list1 = Collections.emptyList();
>       List<String> list2 = getStringsFromSomewhere();
>       list1.addAll(list2);
> 
> What happens on the third line? The spec for Collections.emptyList() [1] says that the returned list is immutable. You might think, then, that addAll() will throw UnsupportedOperationException.
> 
> What actually happens is, "it depends."
> 
> If list2 has elements, then addAll() will throw UOE as expected. However, if
> list2 happens to be empty, then addAll() returns false, because nothing was added.
> 
> To me, the code above clearly has a bug: it's calling a mutator method on an immutable collection. The only time this doesn't throw an exception is if list2 is empty, so it can't possibly have any useful effect in this case.
> Presumably getStringsFromSomewhere() will return some actual strings from time to time. If this happens rarely, we might put this code into production, and it might blow up unexpectedly when a different set of inputs causes list2 to be nonempty.
> 
> (Aside 1: the Java 9 unmodifiable collections throw UOE unconditionally, so
> List.of().addAll(List.of()) will throw UOE.)
> 
> (Aside 2: even though it's inconsistent and arguably wrong, I don't think this behavior of emptyList() should be changed, for compatibility reasons.)
> 
> I think you can see the analogy with HashMap.compute(). The cases from the tests essentially do this:
> 
>       var m = new HashMap<K, V>();
>       // possible modifications to m
>       m.compute(someKey, (k, v) -> {
>           m.clear();
>           return someValue;
>       });
> 
> Looking at this code, and not knowing the state of m, it seems to me it has a bug. The spec for compute() [2] says "The remapping function should not modify this map during computation" and there's a call to clear() right there. Indeed, the current code always throws ConcurrentModificationException.
> 
> You're proposing that it not throw CME in the case where m is empty, when
> clear() has no effect. This is similar to the case above; if m is often empty, then this code appears to "work". But if the program's input were to change and m becomes non-empty, it'll throw CME unexpectedly. On the other hand, it would allow clear() in exactly the cases where it has no effect.
> 
> Overall I don't see that the system is improved by this change. It allows a particular operation only when it has no effect (thus adding no value), and it increases the risk of bugs in programs going undetected.
> 
> s'marks
> 
> 
> [1]
> https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Collections.html#emptyList()
> 
> [2]
> https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Map.html#compute(K,java.util.function.BiFunction)
> 
> 
> 
> 
> On 4/12/19 2:46 AM, Patrick Zhang OS wrote:
>> Created a ticket to track it, welcome any comments. Thanks.
>>
>> JBS https://bugs.openjdk.java.net/browse/JDK-8222394
>> Webrev: http://cr.openjdk.java.net/~qpzhang/map.clear/webrev.01
>>
>> Regards
>> Patrick
>>
>> -----Original Message-----
>> From: core-libs-dev <core-libs-dev-bounces at openjdk.java.net> On Behalf Of Patrick Zhang OS
>> Sent: Saturday, March 30, 2019 1:34 PM
>> To: core-libs-dev <core-libs-dev at openjdk.java.net>
>> Subject: ConcurrentModificationException thrown by HashMap.compute() operating on an empty Map, expected/unexpected?
>>
>> Hi,
>> Here I have a case simplified from a practical issue that throws ConcurrentModificationException (CME) unexpectedly (I think). [0] creates a HashMap, keeps it empty, and calls m.computeIfAbsent() or m.compute(), in which a "sneaky" m.clear() occurs, some of the test cases throw CME although there were no "structural" changes in fact. (A structural modification is defined as "any operation that adds or deletes one or more mappings...").
>>
>> This case cannot be reproduced with jdk8u, while jdk9 and beyond can, after the bug [1] got fixed for computeIfAbsent() concurrent co-modification issues. A couple of test cases [2] were introduced at that time, and the focus was to verify the behaviors at resizing, while empty maps were not tested.
>>
>> A possible "fix" for this issue is to move the unconditional "modCount++" [3] into the if-clause, which indicates that a "structural" change would be happening indeed.
>>
>> public void clear() {
>>       Node<K,V>[] tab;
>> -   modCount++;
>>       if ((tab = table) != null && size > 0) {
>> +        modCount++;
>>             size = 0;
>>             for (int i = 0; i < tab.length; ++i)
>>               tab[i] = null;
>>           }
>> }
>>
>> Therefore, a dilemma here is "modCount++ before-if-clause but overkills some cases" vs. "modCount++ into-if-clause but weakens the CME checking potentially". I want to make balance regarding how to "throw CME on a best-effort basis" more appropriately. Any suggestion?
>>
>> I understand that CME here in HashMap.java cannot guarantee much and may be only for debugging purpose, any concurrent modification needs to be typically accomplished by synchronizing on some object that naturally encapsulates the map. So the mentioned issue is a just a tricky case.
>>
>> [0]http://cr.openjdk.java.net/~qpzhang/map.clear/webrev.01/test/jdk/java/util/concurrent/ConcurrentMap/ConcurrentModification.java.udiff.html
>> [1]https://bugs.openjdk.java.net/browse/JDK-8071667
>> [2]http://hg.openjdk.java.net/jdk/jdk/file/5a9d780eb9dd/test/jdk/java/util/Map/FunctionalCMEs.java
>> [3]http://hg.openjdk.java.net/jdk/jdk/file/1042cac8bc2a/src/java.base/share/classes/java/util/HashMap.java#l860
>>
>> Regards
>> Patrick
>>