Duplicate keys in a dictionary when using PhysicalAddress as a key

Question

So, I had an interesting problem when I get duplicate keys in a C # dictionary when using a key of type PhysicalAddress. This is interesting because it only happens after a very long period of time, and I cannot reproduce it using the same code in unit test on a completely different machine. I can reliably play it on a computer running Windows XP SP3, but only after it starts for several days at a time, and even then it appears only once.

Below is the code I'm using, and below is the log output for this piece of code.

the code:

private void ProcessMessages() { IDictionary<PhysicalAddress, TagData> displayableTags = new Dictionary<PhysicalAddress, TagData>(); while (true) { try { var message = incomingMessages.Take(cancellationToken.Token); VipTagsDisappeared tagsDisappeared = message as VipTagsDisappeared; if (message is VipTagsDisappeared) { foreach (var tag in tagDataRepository.GetFromTagReports(tagsDisappeared.Tags)) { log.DebugFormat(CultureInfo.InvariantCulture, "Lost tag {0}", tag); RemoveTag(tag, displayableTags); } LogKeysAndValues(displayableTags); PublishCurrentDisplayableTags(displayableTags); } else if (message is ClearAllTags) { displayableTags.Clear(); eventAggregator.Publish(new TagReaderError()); } else if (message is VipTagsAppeared) { foreach (TagData tag in tagDataRepository.GetFromTagReports(message.Tags)) { log.DebugFormat(CultureInfo.InvariantCulture, "Detected tag ({0}) with Exciter Id ({1})", tag.MacAddress, tag.ExciterId); if (tagRules.IsTagRssiWithinThreshold(tag) && tagRules.IsTagExciterValid(tag)) { log.DebugFormat(CultureInfo.InvariantCulture, "Detected tag is displayable ({0})", tag); bool elementAlreadyExists = displayableTags.ContainsKey(tag.MacAddress); if (elementAlreadyExists) { displayableTags[tag.MacAddress].Rssi = tag.Rssi; } else { displayableTags.Add(tag.MacAddress, tag); } } else { log.DebugFormat(CultureInfo.InvariantCulture, "Detected tag is not displayable ({0})", tag); RemoveTag(tag, displayableTags); } } LogKeysAndValues(displayableTags); PublishCurrentDisplayableTags(displayableTags); } else { log.WarnFormat(CultureInfo.InvariantCulture, "Received message of unknown type {0}.", message.GetType()); } } catch (OperationCanceledException) { break; } } } private void PublishCurrentDisplayableTags(IDictionary<PhysicalAddress, TagData> displayableTags) { eventAggregator.Publish(new CurrentDisplayableTags(displayableTags.Values.Distinct().ToList())); } private void RemoveTag(TagData tag, IDictionary<PhysicalAddress, TagData> displayableTags) { displayableTags.Remove(tag.MacAddress); // Now try to remove any duplicates and if there are then log it out bool removalWasSuccesful = displayableTags.Remove(tag.MacAddress); while (removalWasSuccesful) { log.WarnFormat(CultureInfo.InvariantCulture, "Duplicate tag removed from dictionary: {0}", tag.MacAddress); removalWasSuccesful = displayableTags.Remove(tag.MacAddress); } } private void LogKeysAndValues(IDictionary<PhysicalAddress, TagData> displayableTags) { log.TraceFormat(CultureInfo.InvariantCulture, "Keys"); foreach (var physicalAddress in displayableTags.Keys) { log.TraceFormat(CultureInfo.InvariantCulture, "Address: {0}", physicalAddress); } log.TraceFormat(CultureInfo.InvariantCulture, "Values"); foreach (TagData physicalAddress in displayableTags.Values) { log.TraceFormat(CultureInfo.InvariantCulture, "Address: {0} Name: {1}", physicalAddress.MacAddress, physicalAddress.Name); } } 

And process messages are processed as follows:

 Thread processingThread = new Thread(ProcessMessages); 

GetFromTagReports Code

 public IEnumerable<TagData> GetFromTagReports(IEnumerable<TagReport> tagReports) { foreach (var tagReport in tagReports) { TagData tagData = GetFromMacAddress(tagReport.MacAddress); tagData.Rssi = tagReport.ReceivedSignalStrength; tagData.ExciterId = tagReport.ExciterId; tagData.MacAddress = tagReport.MacAddress; tagData.Arrived = tagReport.TimeStamp; yield return tagData; } } public TagData GetFromMacAddress(PhysicalAddress macAddress) { TagId physicalAddressToTagId = TagId.Parse(macAddress); var personEntity = personFinder.ByTagId(physicalAddressToTagId); if (personEntity.Person != null && !(personEntity.Person is UnknownPerson)) { return new TagData(TagType.Person, personEntity.Person.Name); } var tagEntity = tagFinder.ByTagId(physicalAddressToTagId); if (TagId.Invalid == tagEntity.Tag) { return TagData.CreateUnknownTagData(macAddress); } var equipmentEntity = equipmentFinder.ById(tagEntity.MineSuiteId); if (equipmentEntity.Equipment != null && !(equipmentEntity.Equipment is UnknownEquipment)) { return new TagData(TagType.Vehicle, equipmentEntity.Equipment.Name); } return TagData.CreateUnknownTagData(macAddress); } 

If the physical address is created

 var physicalAddressBytes = new byte[6]; ByteWriter.WriteBytesToBuffer(physicalAddressBytes, 0, protocolDataUnit.Payload, 4, 6); var args = new TagReport { Version = protocolDataUnit.Version, MacAddress = new PhysicalAddress(physicalAddressBytes), BatteryStatus = protocolDataUnit.Payload[10], ReceivedSignalStrength = IPAddress.NetworkToHostOrder(BitConverter.ToInt16(protocolDataUnit.Payload, 12)), ExciterId = IPAddress.NetworkToHostOrder(BitConverter.ToInt16(protocolDataUnit.Payload, 14)) }; public static void WriteBytesToBuffer(byte[] oldValues, int oldValuesStartindex, byte[] newValues, int newValuesStartindex, int max) { var loopmax = (max > newValues.Length || max < 0) ? newValues.Length : max; for (int i = 0; i < loopmax; ++i) { oldValues[oldValuesStartindex + i] = newValues[newValuesStartindex + i]; } } 

Please note the following:

• Each tag in messages. Tags contain a "new" physical address.
• Each returned TagData is also "new."
• The 'tagRules' methods do not modify the passed in the tag.
• Individual testing with an attempt to put two PhysicalAddress instances (which were created from the same bytes) in the dictionary throws a KeyAlreadyExists exception.
• I also tried TryGetValue and gave the same result.

Log output, where everything is in order:

 2013-04-26 18:28:34,347 [8] DEBUG ClassName - Detected tag (000CCC756081) with Exciter Id (0) 2013-04-26 18:28:34,347 [8] DEBUG ClassName - Detected tag is displayable (Unknown: ?56081) 2013-04-26 18:28:34,347 [8] TRACE ClassName - Keys 2013-04-26 18:28:34,347 [8] TRACE ClassName - Address: 000CCC755898 2013-04-26 18:28:34,347 [8] TRACE ClassName - Address: 000CCC756081 2013-04-26 18:28:34,347 [8] TRACE ClassName - Address: 000CCC755A27 2013-04-26 18:28:34,347 [8] TRACE ClassName - Address: 000CCC755B47 2013-04-26 18:28:34,347 [8] TRACE ClassName - Values 2013-04-26 18:28:34,347 [8] TRACE ClassName - Address: 000CCC755898 Name: Scotty McTester 2013-04-26 18:28:34,347 [8] TRACE ClassName - Address: 000CCC756081 Name: ?56081 2013-04-26 18:28:34,347 [8] TRACE ClassName - Address: 000CCC755A27 Name: JDTest1 2013-04-26 18:28:34,347 [8] TRACE ClassName - Address: 000CCC755B47 Name: 33 1 2013-04-26 18:28:34,347 [8] TRACE ClassName - Current tags: Scotty McTester, ?56081, JDTest1, 33 1 

The output of the log, where we get the duplicate key:

 2013-04-26 18:28:35,608 [8] DEBUG ClassName - Detected tag (000CCC756081) with Exciter Id (0) 2013-04-26 18:28:35,608 [8] DEBUG ClassName - Detected tag is displayable (Unknown: ?56081) 2013-04-26 18:28:35,608 [8] TRACE ClassName - Keys 2013-04-26 18:28:35,608 [8] TRACE ClassName - Address: 000CCC755898 2013-04-26 18:28:35,608 [8] TRACE ClassName - Address: 000CCC756081 2013-04-26 18:28:35,618 [8] TRACE ClassName - Address: 000CCC755A27 2013-04-26 18:28:35,618 [8] TRACE ClassName - Address: 000CCC755B47 2013-04-26 18:28:35,618 [8] TRACE ClassName - Address: 000CCC756081 2013-04-26 18:28:35,618 [8] TRACE ClassName - Values 2013-04-26 18:28:35,618 [8] TRACE ClassName - Address: 000CCC755898 Name: Scotty McTester 2013-04-26 18:28:35,618 [8] TRACE ClassName - Address: 000CCC756081 Name: ?56081 2013-04-26 18:28:35,648 [8] TRACE ClassName - Address: 000CCC755A27 Name: JDTest1 2013-04-26 18:28:35,648 [8] TRACE ClassName - Address: 000CCC755B47 Name: 33 1 2013-04-26 18:28:35,648 [8] TRACE ClassName - Address: 000CCC756081 Name: ?56081 2013-04-26 18:28:35,648 [8] TRACE ClassName - Current tags: Scotty McTester, ?56081, JDTest1, 33 1, ?56081 

Note that everything happens in one thread (see [8]), so there is no way to change the dictionary at the same time. Excerpts from the same journal and process instance. Also note that in the second set of logs we end up with two identical keys!

What I'm learning: I changed PhysicalAddress to a string to see if I can remove this from the list of suspects.

My questions:

• Is there a problem that I do not see in the code above?
• Is there a problem with equality methods in PhysicalAddress? (What is the only error from time to time?)
• Is there a problem with the Dictionary?

Answer 1

The dictionary expects an immutable object as a key, with a stable implementation of GetHashCode / Equals. This means that after the object is placed in the dictionary, the value returned by GetHashCode should not change, and any changes made to this object should not affect the Equals method.

Although the PhysicalAddress class was designed to be immutable, it still contains several extension points where its immutability is erroneous.

Firstly, it can be changed using an array of input bytes, which is not copied, but transmitted by reference, for example:

 var data = new byte[] { 1,2,3 }; var mac = new PhysicalAddress(data); data[0] = 0; 

Secondly, PhysicalAddress is not a private class and can be modified by a derived implementation by overriding the Constructor / GetHashCode / Equals methods. But this use case is more like a hack, so we will ignore it, as well as changes through reflection.

Your situation can only be achieved by placing the PhysicalAddress object in the dictionary, and then modifying its original byte array and then transferring it to a new instance of PhysicalAddress.

Fortunately, the implementation of the “GetHashCode” PhysicalAddress calculates the hash only once, and if the same instance is modified, it is still placed in the same dictionary, and again located on Equals.

But if the original byte array is transferred to another instance of PhysicalAddress, where the hash has not yet been calculated, the hash is recounted to a new byte [] value, the new bucket is located, and the duplicate is inserted into the dictionary. In rare cases, the same bucket may be located from a new hash, and again, no duplicate is inserted.

Here is the code that reproduces the problem:

 using System; using System.Collections.Generic; using System.Net.NetworkInformation; class App { static void Main() { var data = new byte[] { 1,2,3,4 }; var mac1 = new PhysicalAddress(data); var mac2 = new PhysicalAddress(data); var dictionary = new Dictionary<PhysicalAddress,string>(); dictionary[mac1] = "A"; Console.WriteLine("Has mac1:" + dictionary.ContainsKey(mac1)); //Console.WriteLine("Has mac2:" + dictionary.ContainsKey(mac2)); data[0] = 0; Console.WriteLine("After modification"); Console.WriteLine("Has mac1:" + dictionary.ContainsKey(mac1)); Console.WriteLine("Has mac2:" + dictionary.ContainsKey(mac2)); dictionary[mac2] = "B"; foreach (var kvp in dictionary) Console.WriteLine(kvp.Key + "=" + kvp.Value); } } 

Pay attention to the commented line - if we uncomment it, the ContainsKey method will precompile the hash for mac2, and it will be the same even after modification.

So, my recommendation is to find the piece of code that generates the PhysicalAddress instances and create a new byte array for each constructor call.