Issue 3498 in pharo: remove:ifAbsent: in linked list leads to interruption/sync problems

Status: Accepted
Owner: stephane.ducasse

New issue 3498 by stephane.ducasse: remove:ifAbsent: in linked list leads  
to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

If you fill an issue for the first time, please read "How to report bugs"
at http://www.pharo-project.org/community/issue-tracking

Pharo image: <core, dev or web>
Pharo core version: <copy from World/System/About>
Virtual machine used: <ex: pharo-vm-0.15.2f-linux>
Class browser used if applicable: <ex: O2PackageBrowserAdaptor. If you
don't
know, print "SystemBrowser default">

Steps to reproduce:
1.
2.
3.


Paste or attach stack trace if applicable (look at the file PharoDebug.log
located in the same directory as your image):

Updates:
        Status: Fixed
        Cc: adrian.lienhard
        Labels: Milestone-1.2

Comment #1 on issue 3498 by stephane.ducasse: remove:ifAbsent: in linked  
list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

the definition is

remove: aLinkOrObject ifAbsent: aBlock
        "Remove aLink from the receiver. If it is not there, answer the result of
        evaluating aBlock."
        |link|
        link := self linkOf: aLinkOrObject ifAbsent: [^aBlock value].
        self removeLink: link.
        ^aLinkOrObject


and andreas suggests to revert to use the squeak version


remove: aLink ifAbsent: aBlock
        "Remove aLink from the receiver. If it is not there, answer the result of
        evaluating aBlock."

        | tempLink |
        aLink == firstLink
                ifTrue: [firstLink := aLink nextLink.
                                aLink == lastLink
                                        ifTrue: [lastLink := nil]]
                ifFalse: [tempLink := firstLink.
                                [tempLink == nil ifTrue: [^aBlock value].
                                 tempLink nextLink == aLink]
                                        whileFalse: [tempLink := tempLink nextLink].
                                tempLink nextLink: aLink nextLink.
                                aLink == lastLink
                                        ifTrue: [lastLink := tempLink]].
        aLink nextLink: nil.
        ^aLink

Comment #2 on issue 3498 by stephane.ducasse: remove:ifAbsent: in linked  
list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

andreas wrote on squeak-dev:
Oh, I also just noticed something else: It seems as if the VMMaker changes  
for atomic suspend never made it into the main line. I just posted the  
relevant bits but that means you have another workaround. You can use the  
Cog VM, which has had these changes from the beginning. By using Cog, the  
primitive suspend will never fail and consequently the (still broken) code  
in LinkedList>>remove:ifAbsent: will never be executed.

Comment #3 on issue 3498 by stephane.ducasse: remove:ifAbsent: in linked  
list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

The bug is probably linked to the fact that the vm does preempt == while  
the other definition is based on messages and can be preempted.

Adrian what do you think?

Updates:
        Cc: marcus.denker

Comment #4 on issue 3498 by marianopeck: remove:ifAbsent: in linked list  
leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

Stef, I am not Adrian, but yes, I think that can be the reasons. Just take  
the example of Andreas. When you do foo == nil, when that's compiled, it  
put a special bytcode for the == primitive (no method is send).
It seems the scheduler can change processes during method sends. In most  
clases, this may not be a problem. But if you cahnge foo == nil, by foo  
isNil, it may be a point where it can be preempted. And maybe there are  
places where this cannot happen, probably the place where the the processes  
are managed or the code needed for that, like Andras said, process, delay,  
semaphore, etc.

What I don't understand is that I thought that the compiler replaces foo  
isNil by foo == nil. And if this is the case, then what has been explained  
doesn't make sense :(

2010/12/31  <[hidden email]>:
No, only #ifNil: is a selector handled specially by Compiler.

Nicolas

Thanks nicolas. I cannot remember this by hearth.

For me this is really strange to have that rely on the way the execution
engine make subtle differences between similar entity at the language level.
I'm probably too idiot to understand why language semantics is mixed with optimization of the underlying execution engine.


On Dec 31, 2010, at 3:15 PM, Nicolas Cellier wrote:

Comment #5 on issue 3498 by rydier: remove:ifAbsent: in linked list leads  
to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

remove: aLinkOrObject ifAbsent: aBlock
        "Remove aLink from the receiver. If it is not there, answer the result of
        evaluating aBlock."
        |link|
        link := self linkOf: aLinkOrObject ifAbsent: [^aBlock value].
        self removeLink: link ifAbsent: [^aBlock value].
        ^aLinkOrObject

Comment #6 on issue 3498 by rydier: remove:ifAbsent: in linked list leads  
to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

For the record, it was rewritten to accept regular objects as well as links  
as arguments (in which case a ValueLink for the object is created with  
add/found and removed with remove)

removeLink:ifAbsent: is exactly the same as remove:ifAbsent: in Squeak

The reason I did not add the ifAbsent: block to the removeLink: call in new  
remove:ifAbsent: was pure ignorance, I was not aware LinkedLists methods  
were supposed to be thread-safe, for instance add:after: is not, neither in  
Pharo nor Squeak.

The version currently in Pharo (without ifAbsent:) is perfectly valid if  
thread-safeness is not a criterion.

Comment #7 on issue 3498 by stephane.ducasse: remove:ifAbsent: in linked  
list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

Thanks henrik! We assume your changes :).
Adrian can you let us know if reverting remove:ifAbsent: is of any help for  
you.

Comment #8 on issue 3498 by adrian.lienhard: remove:ifAbsent: in linked  
list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

Sure, I'm going to report back when I know that reverting the change solves  
the problem. Since the meantime between failure is about 2 weeks, this will  
take a month or so to know with some confidence.

Comment #9 on issue 3498 by rydier: remove:ifAbsent: in linked list leads  
to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

Reverting works, or changing the call in suspend to removeLink:ifAbsent:  
(which is the same as old remove:ifAbsent:)

Would be nice if you could try with the version I posted in #5 though, as  
it both preserves the new functionality of being able to pass regular  
objects, as well as (afaict) introduces no new possible suspension points  
compared to the old version which could lead to this error.

The difference is removeLink:ifAbsent: is called instead of removeLink:,  
which does not raise an error with the empty block argument, ie:
If the link has been removed by another process while my process is blocked  
after linkOf:, but before removeLink:ifAbsent:, the removeLink:ifAbsent:  
would execute the (in Process >> suspend case) empty block and do nothing  
rather than the default in removeLink: of raising an error.

Comment #10 on issue 3498 by stephane.ducasse: remove:ifAbsent: in linked  
list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

adrian: I'll try that...
But I still don't understand why the change in Pharo that makes  
LinkedList>>remove:ifAbsent: non thread safe can cause the problem since  
this code is executed by the timerEvent process, which runs at the highest  
priority. This process should never be suspended during the execution of  
remove:ifAbsent:. What do I miss?

Andreas: The problem isn't thread-safety, at least in the classical  
definition. What happens is that if you're removing processes by using  
LinkedList>>remove: you are subject to a race condition where the semaphore  
gets signaled *while* you are removing the the process. Obviously,  
hillarity ensues at this point, which is why I made primitive suspend do  
the Right Thing (i.e., remove the process primitively). There are two  
parameters which affect if you're likely to see the effect or not: One is  
the number of suspension points (real sends) in the method. The more you  
have, the more likely you're affected. The second one is whether the method  
can tolerate having the process removed "underneith its feet". Both are far  
worse in Pharo.

Comment #11 on issue 3498 by [hidden email]: remove:ifAbsent: in  
linked list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

Adrian could you have a look because I'm too busy to get concentrated?
Because for me this is one of the important last issue for 1.2

Comment #12 on issue 3498 by [hidden email]: remove:ifAbsent: in  
linked list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

I suggest to apply the change attached (this is from comment #5).

We have been using this in production for 2 weeks and haven't seen the  
problem since. It's a bit early to tell for sure whether its really solved,  
but it seems so. It's certainly a safe change so it would be good to push  
that into 1.2.

Attachments:
        FixLinkedList.1.cs  447 bytes

Updates:
        Status: Closed

Comment #13 on issue 3498 by [hidden email]: remove:ifAbsent: in  
linked list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

12308

Comment #14 on issue 3498 by [hidden email]: remove:ifAbsent: in  
linked list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

added to 11419

Updates:
        Labels: Milestone-1.1.2

Comment #15 on issue 3498 by [hidden email]: remove:ifAbsent: in  
linked list leads to interruption/sync problems
http://code.google.com/p/pharo/issues/detail?id=3498

(No comment was entered for this change.)