bugGNUstep - Bugs: bug #35263, libobjc2 can enter a deadlock...

Group
 
 

bug #35263: libobjc2 can enter a deadlock during dtable initialization

Submitter:  Morten Hustveit <mortenhustveit>
Submitted:  Sat 07 Jan 2012 05:00:19 PM UTC
   
 
Category:  Libraries Severity:  3 - Normal
Item Group:  Bug Status:  None
Privacy:  Public Assigned to:  None
Open/Closed:  Open
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Thu 19 Jan 2012 01:58:51 PM UTC, comment #8: 


>  If you only got the global lock, you have to make sure that every single class that might potentially receive messages in another thread is initialized before you go multi-threaded,


On the contrary ... with the gnu runtime all you have to do is avoid any +initialize waiting for another thread ... which is a very easy contract to honor.

But the discussion of which contract is easier is rather academic ... in practice we have to try to honor both contracts :-(

Richard Frith-Macdonald <CaS>
Group Member
Thu 19 Jan 2012 01:49:53 PM UTC, comment #7: 

Hi guys,

Just some thoughts on this: Having per class locks for +initialize is not only the Apple compatible behaviour, but imho also a contract that is easier to honour: You just have to keep the set of classes being initialized in thread A disjoint from those you send messages to from thread B (and vice-versa).
And while I agree that this can be quite tedious for a complex application, it's even worse with the GCC runtime: If you only got the global lock, you have to make sure that every single class that might potentially receive messages in another thread is initialized before you go multi-threaded, which really isn't feasible at all for a non-trivial application.

For example, in DBusKit I need a whole pile of code that postpones creation of a worker thread until all +initialize methods in the related DBusKit classes have run just to work around this limitation of the GCC runtime. Not a single line of this stuff is actually required with libobjc2. 

Cheers,

Niels

Niels Grewe <thebeing>
Group Member
Thu 19 Jan 2012 09:09:00 AM UTC, comment #6: 

Here a mail from David that comments on a mail from Richard in reply to this bug report. Most likely this will get completely unreadable, but I don't want that information to get lost.


> On 11 Jan 2012, at 09:16, Fred Kiefer wrote:
>
>> To Richard's comment that we could adopt the GCC runtime solution:
> I don't think I actually advocated that.
>
>> I wrote the
>> patch that did that in the GCC runtime originally, and it's what the GNUstep
>> runtime used to do.
> Not sure what he's talking about here ... the current GCC behavior was written by me and then improved by Nicola ... so perhaps he's talking about the earlier version of the +initialize code which wasn't thread-safe?

No, I wrote the code in the version of GCC libobjc in GNUstep svn that implemented this.  I assumed that had been ported upstream to GCC, I hadn't realised that you reinvented the wheel.

>> I fixed this behaviour because people rely on the Apple
>> behaviour - there are lots of fun deadlock scenarios you can get into from
>> only being able to enter one +initialize method at once in each thread.
> Not clear on this either ... the Apple behavior?  In the GCC runtime there's a global lock so, once one thread enters a +initialize no other thread can do so until the first thread exits again, but the first thread can enter +initialize in any/all classes.  That means that, as long as your +initialize implementation doesn't wait for any other thread (directly or indirectly), the GCC runtime avoids deadlocks. That's why I (slightly) prefer the GCC runtime behavior ... it 's relatively easy to avoid deadlock.

I initially implemented the single-lock version in GNUstep libobjc.  The reason that I implemented the Apple-compatible behaviour was that I got reports of deadlocks with the single-lock version.  This is because there are existing applications that do things like spawn a new thread in +initialize and send messages from that thread and exit the +initialize once the thread returned. These then hit the global lock and deadlock. 

They only deadlocked on GNUstep, so from the user perspective this is a bug: my code works on Cocoa, doesn't work on GNUstep = GNUstep sucks.

People notified me of a bug, which was also an Apple incompatibility, and I fixed it.  Now other people are complaining that their code - which uses a GCC-specific, undocumented, behaviour - does not work. 

>> Reverting to the old behaviour would just mean getting a different set of
>> potential deadlocks, and they would be deadlocks that a) only showed up on
>> GNUstep and not Cocoa, and b) made it hard to write code that was
>> deadlock-free on both Cocoa and GNUstep.
> Valid point ... but these deadlocks are rare (so far we have one bug report for the apple behavior, and have not had any for the gcc behavior).  So I don't think it makes sense to change the GCC runtime to copy an undocumented behavior of the Apple runtime which is rarely relevant and doesn't actually improve things.  What we do need to be aware of is that existing initialization code which is fine with the GCC runtime might deadlock with the Apple runtime.
>
> It sounds like David is saying he won't fix libobjc2 and wants libobc to reproduce the apple bug instead. 

No, I'm saying that I won't reintroduce a bug that I already fixed. 

> I'd rather not bother trying to get GCC libobjc changed until/unless we can find a fix which cures both deadlocks (it's a hard argument to say to a FSF project they should change something to fix one by replacing it with a worse one which is Apple compatible).

Fixing the GCC runtime is the correct fix, because it is buggy.  +initialize is supposed to block all messages to that class until it completes.  There are two buggy behaviours:

- Not blocking (GCC used to do this)
- Blocking all unrelated +initialize methods (GCC and GNUstep used to do this)

Apple does not document that it does not block other classes receiving +initialize methods any more than NSLock's -lock method doesn't block any other locks.  It is implicit.  The exact phrase in the documentation is:

> The runtime sends initialize to each class in a program exactly one time just before the class, or any class that inherits from it, is sent its first message from within the program. (Thus the method may never be invoked if the class is not used.) The runtime sends the initialize message to classes in a thread-safe manner.


Nowhere in this does it say that the +initialize method will block anything else, only that it will complete before any other messages sent to that class or its subclasses (other than ones sent from within the +initialize method).  The GCC runtime (and old versions of the GNUstep runtime) introduced undocumented serialisation constraints.  This was / is a bug.

Fred Kiefer <FredKiefer>
Group Member
Wed 11 Jan 2012 12:02:26 PM UTC, comment #5: 

To assist with reproducing the second test case, I have created a virtual machine image (630 MB bzip2) containing Debian sid, GNUstep from SVN and the test case.  Here is how you download and run the image:

On the host computer:

  1. wget http://www.ping.uio.no/~mortehu/gnustep-test.img.bz2 -O- | bunzip2 > gnustep-test.img

  2. sudo -E kvm -drive if=virtio,file=gnustep-test.img,media=disk -smp 2

On the virtual machine:

  1. Log in as "user" (no password)

  2. while true; do ./libobjc2-deadlock-2; echo -n .; done

Some observations:

  * When I dropped the "-smp 2" option to kvm, the test case deadlocked on 20 out of 20 runs

  * With the "-smp 2" option, the test case can take several hundred runs between each deadlock on my computer

Morten Hustveit <mortenhustveit>
Wed 11 Jan 2012 09:16:30 AM UTC, comment #4: 

Another comment from David, he seems to have trouble with the https connection:

To Richard's comment that we could adopt the GCC runtime solution: I wrote the patch that did that in the GCC runtime originally, and it's what the GNUstep runtime used to do.  I fixed this behaviour because people rely on the Apple behaviour - there are lots of fun deadlock scenarios you can get into from only being able to enter one +initialize method at once in each thread.  Reverting to the old behaviour would just mean getting a different set of potential deadlocks, and they would be deadlocks that a) only showed up on GNUstep and not Cocoa, and b) made it hard to write code that was deadlock-free on both Cocoa and GNUstep.

The second test case, however, does look like it shows a valid bug in GNUstep if it actually does cause a deadlock.  I can't reproduce this though. I've now run the test over 5,000 times and can't reproduce the deadlock - the test succeeded every time.

Fred Kiefer <FredKiefer>
Group Member
Mon 09 Jan 2012 01:46:59 PM UTC, comment #3: 

I have attached a new test case which deadlocks using GNUstep base classes.  The program I'm working on triggers this bug 90% of the time (it starts 9 threads at startup and uses many classes), but this small test case only triggers it about 10% of the time.

You may want to use a bash command line like this to run it until it hangs:

while true; do ./libobjc2-deadlock-2; echo -n .; done

I have run this command line many times, and it has never printed more than 30 dots before hanging.

Note: I'm not entirely sure this test case triggers the exact same bug.

(file #24773)

Morten Hustveit <mortenhustveit>
Sun 08 Jan 2012 10:43:31 PM UTC, comment #2: 

I would say that the GNU runtime does the right thing here,  but that's judging by what behavior seems a little more predictable/usable.
If we take the Apple implementation as the reference, then copying that is the correct behavior.
But both behaviors are correct as far as the documentated behavior of +initialize is concerned (ie both enforce the rule that no other method of a class may be executed before the first +initialize of the class completes).

The GNU runtime serialises +initialize by using a global lock to ensure that only one thread is executing a +initialize method at a time. You can deadlock it by having a +initialize method block waiting for another thread to do something which can't be done without the other thread calling +initialize, but of course the deadlock in this bug report can't occur when +initialize is serialized using a global lock.

The Apple runtime serialises +initialize using per-class locking, so other threads can initialise other classes without having to wait.  This will deadlock if it calls a method  which involves another thread doing anything with the class being initialized, but won't deadlock when calling methods which involve other threads initialising other classes.

I like Fred's notion that we could avoid the deadlock reported here, but it's hard to see how we would do that apart from changing libobjc2 to adopt the GNU runtime's solution ... which is not much better.


Richard Frith-Macdonald <CaS>
Group Member
Sun 08 Jan 2012 07:25:16 PM UTC, comment #1: 

I just want to pass on the comment by David Chisnall, he still doesn't seem to use Savannah. I am myself not totally convinced that David is right here. Even though Apple doesn't support that behaviour doesn't mean libobjc2 should not have it. Although it means, nobody should rely on it :-(

Here David's comment:

This can be closed as 'works as expected'.  The attached test program deadlocks in exactly the same way on OS X as it does with libobjc2 - the bug is in the test, not in the runtime.

The contract for +initialize is that it is guaranteed to complete before any other message (by any thread) that does not originate within the +initialise method itself will be received by the class receiving the +initialize method.  This means that the code in the test case can not possibly pass on any conforming Objective-C implementation.

It does 'work' with the GCC runtime, because of a long-standing bug where the GCC runtime doesn't correctly do any serialisation of +initialise so this test case contains a race condition instead of a deadlock.

Fred Kiefer <FredKiefer>
Group Member
Sat 07 Jan 2012 05:00:19 PM UTC, original submission:  

`dtable_for_class' contains some logic for waiting for an `initialize' call in another thread.  This seems to break when the other thread is similarly waiting for us.

I have attached a test-case which reproduces this behavior on every run on my computer using revision 28758 on GNU/Linux.  I have also attached the Helgrind log of a single run.

Morten Hustveit <mortenhustveit>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #24773:  libobjc2-deadlock-2.m added by mortenhustveit (551B - text/x-objcsrc)
file #24758:  libobjc2-deadlock.m added by mortenhustveit (781B - text/x-objcsrc)
file #24759:  helgrind.txt added by mortenhustveit (17KiB - text/plain)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by thebeing (Posted a comment)
  • -email is unavailable- added by CaS (Posted a comment)
  • -email is unavailable- added by FredKiefer (Posted a comment)
  • -email is unavailable- added by mortenhustveit (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2012-01-09 mortenhustveit Attached File- Added libobjc2-deadlock-2.m, #24773
    2012-01-07 mortenhustveit Attached File- Added libobjc2-deadlock.m, #24758
        Attached File- Added helgrind.txt, #24759

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code