#8 Legal series of updates corrupts map (2)

open
nobody
None
5
2009-08-18
2009-08-18
Nick Reeves
No

This is a follow on bug for "Legal series of updates corrupts map" - ID: 2810344, since sourceforge doesn't allow bugs to be reopened.

The changes in 1.1.2 create a partial fix for the original bug, but unfortunately the bug still occurs as can be found using the same Bug.java, reattached to this bug report for convenience.

The bug now occurs less reliably. I invite users of this excellent library to add comments if they can reproduce it, describing their set up.

It wasn't reproducible for cliffc on the single machine he tried, but was reproducible for me on the following two machines:

1st machine (as described in the original bug report for 2810344):
Java version is the latest Sun Java 6 JDK - Java(TM) SE Runtime Environment (build 1.6.0_14-b08)
CPU is Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz
OS is Ubuntu 9.04 32 bit

2nd machine:
Java version - Java(TM) SE Runtime Environment (build 1.6.0_14-b08)
CPU - AMD Athlon(tm) 64 X2 Dual Core Processor 5600+
OS - Windows Vista

Discussion

  • Nick Reeves

    Nick Reeves - 2009-08-18
     
  • Andrew M.

    Andrew M. - 2009-08-28

    I don't do Java or multi-threading so this may be off, but the problem appears to be the boolean remove/replace methods returning false when they actually succeeded.

    When thread A is swapping a value in, it first makes sure that V == expVal (if needed), BUT between the check and the CAS, thread B can modify V, and then thread A's CAS goes through, but V is now swapped with thread B's value, which may or may not be expVal. Replace/return then check the previous value against expVal, see that it's not what they expected, and fail, even though thread A's CAS succeeded.

    The bug repro'd quite easily on my E8400, and my attempts at fixes worked, but I don't have any faith in them being proper (a Pair class that returned the V and a boolean indicating whether the value CAS was successful, or just checking expVal on a successful CAS for a valid value and returning that instead of V so the compares trigger true).

     
  • Andrew M.

    Andrew M. - 2009-08-28

    Wait what. That made perfect sense until I remembered the COMPARE part of CAS, but then why did my fixes work? The values have to be due to remove/replace completing but returning the wrong value, but how is that happening!

     
  • Andrew M.

    Andrew M. - 2009-08-28

    Oh. remove/replace are using == on the putIfMatch return value, not .equals. That's what's causing spurious failures and forcing a retry even after the value was properly written. So my fixes were working because they either signal'd a successful write without regard to the values, or returned the reference to the right object by returning expVal

    I suppose the "simple" fix is "return (V==null && expVal!=null) ? TOMBSTONE : expVal;" instead of returning V so the object references are the same if needed?

     
  • Comment has been marked as spam. 
    Undo

    You can see all pending comments posted by this user  here

    Anonymous - 2010-01-12

    floodyberry, I also get the bug, but I'm not following your fix.

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks