RandomAccessReferenceMap.update() can randomly corrupt the map

[GoogleCodeExporter]

What steps will reproduce the problem?
You have a ARM set up like this:
   direct1 <=> "AAAA"

You do this:
newSet = new Set()
newSet.add(newDirect)
newSet.add(direct1)
ARM.update(newSet)

update() clears the old mappings, but tries to preserve them if the same
direct objects are referenced in the new set. Here's how this could go awry:

* update() clears both maps
* update() can't find newDirect in the old mapping, so it calls
getUniqueRandomReference(), which randomly returns "AAAA". It checks that
"AAAA" is not in the current mapping, and it's not (It was just cleared).
* update() sets the mapping newDirect <=> "AAAA"
* update() then looks at direct1, sees that it is in the old mapping, and
sets it in the new mapping direct1 <=> "AAAA", corrupting the indirect to
direct mapping which is now "AAAA" -> direct1

How to fix it:

* Change getUniqueRandomReference to take in a list of invalid indirect 
keys and ensure the generated one is not in that list
* Preserve the old indirect to direct map in update()
* Pass in the keys of the old indirect to direct map to
getUniqueRandomReference 

What version of the product are you using? On what operating system?
SVN revision 574.

Original issue reported on code.google.com by cyounk...@gmail.com on 6 Aug 2009 at 7:33

[GoogleCodeExporter]

I believe, and correct me if I am wrong here, that the chances of this 
happening are
so far fetched that the amount of work to mitigate this nullify the benefit of 
going
through this work.

Also, with how impropable this situation is, is it worth affecting the 
performance of
an otherwise performant object?

Original comment by chrisisbeef on 2 Dec 2009 at 7:28

[GoogleCodeExporter]

Original comment by chrisisbeef on 2 Dec 2009 at 7:55

• Added labels: Priority-Low
• Removed labels: Priority-Medium

[GoogleCodeExporter]

Well, I guess it depends on whether or not you want this thing to actually work 
reliably.

These are unchecked insertions, so the probability of a collision is the # of
elements in the map / the keyspace of the map keys. Multiply this by the number 
of
insertions to get roughly the probability of a collision on an update(). It's 
small
problems like this that are extremely elusive and hard to track down.

In the report I stated how to fix it. It would take at most 10 minutes to 
change and
test.

Original comment by cyounk...@gmail.com on 2 Dec 2009 at 11:46

[GoogleCodeExporter]

Younkins is right IMO. I'll fix this before 2.0.

Original comment by manico.james@gmail.com on 1 Nov 2010 at 5:59

• Added labels: Milestone-Release2.0, Priority-High
• Removed labels: Priority-Low

[GoogleCodeExporter]

Original comment by manico.james@gmail.com on 1 Nov 2010 at 6:01

• Changed state: Accepted

[GoogleCodeExporter]

Original comment by chrisisbeef on 20 Nov 2010 at 9:16

• Added labels: Component-Other

[GoogleCodeExporter]

Original comment by manico.james@gmail.com on 29 May 2012 at 3:20