Bug 6225 - ConcurrentDictionary sometimes only compares HashCodes of keys when it needs to compare key values as well
Summary: ConcurrentDictionary sometimes only compares HashCodes of keys when it needs ...
Status: RESOLVED FIXED
Alias: None
Product: Class Libraries
Classification: Mono
Component: mscorlib ()
Version: 2.10.x
Hardware: PC Linux
: --- normal
Target Milestone: Untriaged
Assignee: Martin Baulig
URL:
Depends on:
Blocks:
 
Reported: 2012-07-20 21:13 UTC by Kevin Gadd
Modified: 2014-11-25 05:02 UTC (History)
5 users (show)

Tags:
Is this bug a regression?: ---
Last known good build:


Attachments
Test case (1.71 KB, text/plain)
2012-07-20 21:21 UTC, Kevin Gadd
Details


Notice (2018-05-24): bugzilla.xamarin.com is now in read-only mode.

Please join us on Visual Studio Developer Community and in the Xamarin and Mono organizations on GitHub to continue tracking issues. Bugzilla will remain available for reference in read-only mode. We will continue to work on open Bugzilla bugs, copy them to the new locations as needed for follow-up, and add the new items under Related Links.

Our sincere thanks to everyone who has contributed on this bug tracker over the years. Thanks also for your understanding as we make these adjustments and improvements for the future.


Please create a new report on GitHub or Developer Community with your current version information, steps to reproduce, and relevant error messages or log files if you are hitting an issue that looks similar to this resolved bug and you do not yet see a matching new report.

Related Links:
Status:
RESOLVED FIXED

Description Kevin Gadd 2012-07-20 21:13:23 UTC
The ConcurrentDictionary implementation in mono's mscorlib (at least in version 2.10.8.1 (Debian 2.10.8.1-ubuntu2.1) ) is broken in that it does not fully compare the values of keys in some circumstances.

The scenario as best I have been able to identify it is this:

You have two objects you are using as keys - let's call them KeyA and KeyB.
KeyA and KeyB both have a HashCode (GetHashCode()) of N.
KeyA and KeyB do *not* compare as Equal using .Equals(), or reference equality.
You add a value for KeyA to the ConcurrentDictionary.
You do .TryGetValue on the ConcurrentDictionary using KeyB as the key.

What should happen in this case is:
ConcurrentDictionary.ListFind gets invoked to search for KeyB inside the dictionary. It calls ListSearch, which returns the last node that it finds that is a candidate for a match. From reading the disassembly if this method it appears it will return nodes that are *not* an exact match.
ListFind should then check the result from ListSearch to ensure that it is a match, by both comparing the .Key and .SubKey of the node against the .Key and .SubKey for the key being searched for.
ListFind would then identify that it was returned the node for KeyA, and reject it because it does not match KeyB. TryGetValue will then return false.

Instead, what seems to happen is:
ListFind gets a result from ListSearch, but *only checks the .Key* to see if it is a match with the requested key. Because KeyA and KeyB have the same HashCode, their .Key members match. .SubKey is never checked to see if the keys are actually equivalent values (i.e. Equals returns true), only their hashes. In this case, that means that TryGetValue will return true despite the fact that it is returning a value for a different key entirely.

I will attempt to build a reduced test case for this (it is difficult because I have to reproduce an exact internal layout for the ConcurrentDictionary to get it to fail in this manner - I have a reliable failure in my application that I have tracked down to ConcurrentDictionary), but I am pretty certain this is busted just by reading the code (and reliably tracking the failure down to ConcurrentDictionary with Console.WriteLine logging.)
Comment 1 Kevin Gadd 2012-07-20 21:21:21 UTC
Created attachment 2241 [details]
Test case

Managed to come up with a test case to reproduce this (apparently the bug really is as simple as it seems).

Here is the output I get when running it:
root@hildr:~/class_inheritance# mono test.exe
Added [[1, KeyA], ValueA] to dict
TryGetValue(keyA, out foundValue) == True; foundValue == ValueA
TryGetValue(keyB, out foundValue) == True; foundValue == ValueA
Added [[1, KeyB], ValueB] to dict
TryGetValue(keyA, out foundValue) == True; foundValue == ValueA
TryGetValue(keyB, out foundValue) == True; foundValue == ValueB
Comment 2 Kevin Gadd 2012-07-20 21:23:38 UTC
For reference here is the output from running test.exe (the same version compiled by dmcs) on Windows with .NET 4.0:

C:\Users\Kevin\Desktop\mono>test.exe
Added [[1, KeyA], ValueA] to dict
TryGetValue(keyA, out foundValue) == True; foundValue == ValueA
TryGetValue(keyB, out foundValue) == False; foundValue ==
Added [[1, KeyB], ValueB] to dict
TryGetValue(keyA, out foundValue) == True; foundValue == ValueA
TryGetValue(keyB, out foundValue) == True; foundValue == ValueB
Comment 3 Jérémie Laval 2012-08-15 17:00:21 UTC
That bug is fixed on master, may need to be backported to the 2-10 branch.
Comment 4 Miguel de Icaza [MSFT] 2012-08-15 17:01:58 UTC
Would be nice to bring this to mono-2-10 and mobile-master.

Since these are part of the TPL, we should do entire copies of the latest.
Comment 5 Vlad 2013-07-29 08:40:52 UTC
I had a similar problem when TryGetValue returned value of removed key which was the value for the another existing key. I didn't reproduce it but perhaps the same bug described here.
Comment 6 Marek Safar 2014-11-25 05:02:33 UTC
Resolved in master