FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Ares updates
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
 
Post new topic   Reply to topic     Forum Index -> Ares
View previous topic :: View next topic  
Author Message
sean



Joined: 24 Jun 2004
Posts: 609
Location: Bay Area, CA

PostPosted: Tue Mar 07, 2006 7:02 pm    Post subject: Reply with quote

kris wrote:
Not sure on that one, although having a fixed size thread-list would be OK assuming it were easily configurable somehow ...

Talking about Phobos, it exhibits a similar deadlock ~ just not with that example (it's a lot more complex, unfortunately). However, when Phobos deadlocks, the threads are in what seem to be identical scenarios vis-a-vis the GC: one thread appears to be attempting a bigAlloc() whilst another is trying to GC ~ the killer is that *all* threads end up with a 'disable' count of more than zero: a value of 1 for the two contending threads and a value of 2 for all others. This would seem to indicate that Thread.pauseAll() was actually invoked twice (for those with a value of 2).

This is actually legal in Ares--you can suspend a thread as many times as you want, similar to locking a reentrant mutex--but the mechanism is such that only one thread can enter suspendAll at a time. I suspect that Phobos doesn't use mutual exclusion here, which is probably why it deadlocks (I'll check it out and submit a patch to Walter if this is so). But Ares was deadlocking for a slightly different reason, though the circumstances are nearly indentical.
Quote:
Thus the thread-state exposed by the debugger, both in terms of the disable state and the relevant stack traces, look almost identical for Phobos in the complex case as it does with Ares in the simplistic case of the above example.

What does this all mean? Well, it tends to indicate the Phobos design has a hole in it (because it certainly does deadlock in the same manner: that's the reason I tried Ares for this issue). Thus, adopting the Phobos strategy may not be a good idea. In other words, I was vaguely hoping, once you get this example working, that the real application will work on Ares where it ultimately fails on Phobos ... the threading models may be sufficiently different to warrant that (I'm trying to get Valgrind to help catch the Phobos issue for me, but not having much luck).

If you can send me a zip file with support for 25 threads, I'll let you know if it is deadlock free Smile

Once I finish with the thread fixes I'll get a test release out to you. Assuming it's good, then I'll publish it to the rest of the world. I realized another assumption I'd made about thread-GC interaction was incorrect as well, and I'm mulling over how best to fix it.


Last edited by sean on Tue Mar 07, 2006 11:00 pm; edited 1 time in total
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Tue Mar 07, 2006 7:32 pm    Post subject: Reply with quote

OK ~ thanks, Sean
Back to top
View user's profile Send private message
sean



Joined: 24 Jun 2004
Posts: 609
Location: Bay Area, CA

PostPosted: Wed Mar 08, 2006 1:16 am    Post subject: Reply with quote

I feel pretty confident about the fixes I've made, so I'm putting version 0.16 online with the following changes. If it turns out there are yet more deadlock issues to be resolved I'll update the release in-place:

* Merged in DMD 149 changes.
* Renamed std.stdarg to std.vararg.
* Added std.regexp from Phobos.
* Added std.bitarray from Phobos.
* Added std.unicode, which includes functionality from std.io.convert.Unicode (ie. from Mango).
* Added std.string. This module may contain some functionality from Phobos, but only when there is an overlap in desired functionality. Most or all functions here will be template functions and will require implicit template instantiation to operate correctly. At the moment, some functions are commented out because template overloading is not yet implemented.
* Changed inline asm in a math function to refer to the parameter by name rather than stack offset. This will be marginally less efficient, but should be more maintainable and hopefully will allow the code to be inlined at some point.
* Rearranged code in std.atomic to use 'static if' to avoid the need for concept parameters.
* Renamed onInvalidUtfError to onUnicodeError.
* Reversed template parameters in std.atomic in anticipation of implicit template instantiation.
* Refactored ares.object and dmdrt.object to more closely match Phobos. The presence of TypeInfo objects is necessary, and the rest should ease merging a bit.
* Rebuilt dmdrt.typeinfo to match phobos.std.typeinfo. It seems DMD references TypeInfo modules by some form of the decorated name, and storing them in differently named files was not working.

[edit] Oops... the changelog doesn't mention the changes made to std.thread. Some refactoring took place there and in dmdgc to fix deadlock and access violation issues.
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Wed Mar 08, 2006 3:19 am    Post subject: Reply with quote

Got the changes, thanks.

That's a lot better for the example, yet I'm still having deadlock issues within the GC. The nice thing about Ares is that it's so easy to enable tracing within the GC. But that itself seems to have some problems:

1) the invariant() checks have this kind of thing scattered around:
Code:
       // Assure we're called on the right thread
       debug (THREADINVARIANT) assert(self == pthread_self());

which causes a stack overflow, since it makes a function-call. BTW, does the GC make an assumption that it can't be fullCollected() from any but the initializing thread? That assert would seem to indicate so?

2) the gcx.bucket list is being clobbered while an invariant executes. I presume because it's being traversed within an invariant(), which are probably not synched?

Can you suggest anything, Sean?
Back to top
View user's profile Send private message
sean



Joined: 24 Jun 2004
Posts: 609
Location: Bay Area, CA

PostPosted: Wed Mar 08, 2006 11:55 am    Post subject: Reply with quote

kris wrote:
Got the changes, thanks.

That's a lot better for the example, yet I'm still having deadlock issues within the GC.

Darn! Wink Do you mean that the deadlocks are within the GC itself? Points of interaction with std.thread in this release are:

thread_suspendAll();
thread_scanAll();
thread_resumeAll();

The GC code itself should be mutually exclusive when >1 thread is running.
Quote:
The nice thing about Ares is that it's so easy to enable tracing within the GC. But that itself seems to have some problems:

1) the invariant() checks have this kind of thing scattered around:
Code:
       // Assure we're called on the right thread
       debug (THREADINVARIANT) assert(self == pthread_self());

which causes a stack overflow, since it makes a function-call. BTW, does the GC make an assumption that it can't be fullCollected() from any but the initializing thread? That assert would seem to indicate so?

This shouldn't be the case. A fullCollect is triggered by whichever thread is attempting to allocate memory, when the GC deems necessary. Perhaps that's simply an old, useless comment? I haven't done any testing with D on Linux, really.
Quote:
2) the gcx.bucket list is being clobbered while an invariant executes. I presume because it's being traversed within an invariant(), which are probably not synched?

See above. Entry into the GC code is protected by a mutex, so there should be no concurrency problems except when the thread code is entered to suspend, scan, and resume thread activity. I'll have to look at the GC code today though and see if I can figure anything out. I ran your demo app on Windows and had no problems with it after my changes, so either this is a more complex case or it's Linux-specific.

By the way, I put up a new zipfile this morning because I'd messed up some edits of a Linux makefile. Next time I'll test build on both platforms before releasing. Embarassed
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Wed Mar 08, 2006 12:53 pm    Post subject: Reply with quote

If I change the code in gcx.d to look like this (around line 270-ish)
Code:

         else{
                         printf ("no pages\n");
                         if (!gcx.fullcollectshell())   // collect to find a new page
         {
             //gcx.newPool(1);
         }
                         printf ("> done\n");
                        }


then whenever it deadlocks, that "no pages" message is the last thing printed. Then I removed the message, added a synchronized(GC.gcLock) around fullCollect(), but after several hours something managed to squeeze in there and deadlock in the same manner (within the GC). RUnning under the debugger is the only way to check the status (break; look at the thread states)

The 'real' code is, unfortunately, quite a bit more complex than the simple example. All code is tested on Win32.

Are there some other places where I should try adding a synch?
Back to top
View user's profile Send private message
sean



Joined: 24 Jun 2004
Posts: 609
Location: Bay Area, CA

PostPosted: Wed Mar 08, 2006 12:58 pm    Post subject: Reply with quote

If I recall, gcx.fullcollectshell is basically a synchronized wrapper around fullCollect, so that should have taken care of things. If you want to be even less granular, use a common mutex to synchronize all the gc_* calls in dmdgc/gc.d. If that doesn't get rid of the deadlock then something really weird is going on.

By the way, that std.thread uses the built-in hash map for storing thread references confuses things a bit because adding a thread actually hits the GC, which in turn may try to scan the thread list. I had to fix a bug early on in how the hash code operates to get this working, as it was messing with the map structure, then allocating, then completing the map modifications. It's a long shot, but I suppose it's possible this could be related to adding or removing threads from this list if doing so is hitting the GC at an unexpected time. I haven't run into this problem since the initial fix, but then I'm not running multithreaded programs in D for hours at a time Wink
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Wed Mar 08, 2006 1:47 pm    Post subject: Reply with quote

FullCollectShell() is a wrapper, but it ain't synchronized Smile

Here's another GC problem:
Code:
void main()
{
        char[] msg = "hello ";

        msg ~= "there";
        printf ("?.*s\n", msg);
}


prints garbage. I was about to post an NG bug-report, but it works fine with Phobos ...
Back to top
View user's profile Send private message
sean



Joined: 24 Jun 2004
Posts: 609
Location: Bay Area, CA

PostPosted: Wed Mar 08, 2006 2:30 pm    Post subject: Reply with quote

Sigh... it's just going to be one of those weeks, I think Wink I realized what the deadlocking problem is as soon as I walked out the door earlier. Basically, the thread code is not allowed to interact with the GC at all from within its lock on the global thread list, as it will always result in this race condition:

- thread A calls 'new', enters the GC, and stalls
- thread B attempts to add a new thread to the global thread list and blocks on the GC mutex while allocating a new node or whatever
- thread A wakes up, realizes the GC is out of memory and triggers a collection which blocks on the global thread list mutex held by thread B

The lock on the global thread list must be in place to keep threads from suspending one another, though if it's assumed that threads will only ever be suspended by the GC then we could probably rely on the GC's mutex to guarantee this. However, that would still require the use of a lock-free list to keep memory synchronized, and this is probably too complicated to be worthwhile.

The most irritating part is that even gc.addRoot is protected by the GC mutex, so the straightforward method of overriding operator new isn't feasible either.

So far, I can think of two options:

1. Use a static array to store thread pointers and limit the number of threads that can be created, similar to Phobos
2. Make clever use of a linked-list as follows:
      - allocate the head node when the thread module is initialized and add it to the list of GC roots
      - allocate all later nodes via malloc and don't explicitly add them to be scanned by the GC, assuming that the GC will be able to follow pointers from the root on collections
Option 2 sounds preferable so far, but I'm busy this evening so it will take me a few days to make the changes. The easiest temporary fix would be to use option 1, which will require chages to Thread.add, Thread.remove, Thread.opApply, and Thread.getAll (though nothing actually calls Thread.getAll so it could be stubbed out).

Having given the Phobos issue some more thought, I'm not entirely sure why Phobos is deadlocking any more, as the way it works seems reasonable if somewhat inefficient in places. But then I haven't looked at the Phobos code yet.

I saw the garbled string issue yesterday while playing with your thread example so I'll look at that as well. My guess is that moving code from dmdgc/gc.d to dmdrt/memory.d a few updates ago is the cuplrit, but it seems a bit odd as I didn't change any of the logic but for replacing a malloc call or two with realloc instead.
Back to top
View user's profile Send private message
sean



Joined: 24 Jun 2004
Posts: 609
Location: Bay Area, CA

PostPosted: Wed Mar 08, 2006 9:05 pm    Post subject: Reply with quote

I thought of a simple way to handle the thread list and had the time to implement it on the ride home. I've put up a new version of 0.16 with the fix included. Let me know if it resolves the deadlock issue.

As for the weird string corruption issue, it will have to wait until tomorrow.
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Wed Mar 08, 2006 10:54 pm    Post subject: Reply with quote

sean wrote:
I thought of a simple way to handle the thread list and had the time to implement it on the ride home. I've put up a new version of 0.16 with the fix included. Let me know if it resolves the deadlock issue.

Thread list looks good! Unfortunately, deadlock is notably quicker to occur with this version.

Also, dmd 0.149 doesn't like the in{}body{} part of add() and remove() ~ with those there, it complains about the need for "this" when dereferencing Thread.m_next and Thread.m_prev.

Wish I could give you some good news Sad
Back to top
View user's profile Send private message
sean



Joined: 24 Jun 2004
Posts: 609
Location: Bay Area, CA

PostPosted: Thu Mar 09, 2006 1:03 am    Post subject: Reply with quote

kris wrote:
sean wrote:
I thought of a simple way to handle the thread list and had the time to implement it on the ride home. I've put up a new version of 0.16 with the fix included. Let me know if it resolves the deadlock issue.

Thread list looks good! Unfortunately, deadlock is notably quicker to occur with this version.

Also, dmd 0.149 doesn't like the in{}body{} part of add() and remove() ~ with those there, it complains about the need for "this" when dereferencing Thread.m_next and Thread.m_prev.

Wish I could give you some good news Sad

LOL. Like I said earlier, it's just one of those weeks Smile However, this is really starting to confuse me as the new code doesn't allocate or touch the GC at all from within Thread.slock protected code, so I'm beginning to wonder if the deadlock might be something else. I don't suppose you have a small test case that deadlocks, or can tell me where the deadlocked threads are stuck? In the meantime, I'll try to reproduce it with the small case you posted earlier--I've only let it run for maybe 30 seconds so far.
Back to top
View user's profile Send private message
sean



Joined: 24 Jun 2004
Posts: 609
Location: Bay Area, CA

PostPosted: Thu Mar 09, 2006 3:53 am    Post subject: Reply with quote

Just a quick update--I checked in a fix for the array append bug. And I checked in a small fix for the new Thread list code as well. I haven't been able to reproduce the deadlock yet, but I'll let the test case run overnight and see what happens. I've updated the zipfile with these changes as well.
Back to top
View user's profile Send private message
sean



Joined: 24 Jun 2004
Posts: 609
Location: Bay Area, CA

PostPosted: Thu Mar 09, 2006 11:06 am    Post subject: Reply with quote

And one more small fix for an access violation I suspect would have occurred. New zipfile, etc.
Back to top
View user's profile Send private message
kris



Joined: 27 Mar 2004
Posts: 1494
Location: South Pacific

PostPosted: Fri Mar 10, 2006 2:39 am    Post subject: Reply with quote

sean wrote:
Just a quick update--I checked in a fix for the array append bug. And I checked in a small fix for the new Thread list code as well. I haven't been able to reproduce the deadlock yet, but I'll let the test case run overnight and see what happens. I've updated the zipfile with these changes as well.

I'll give it a whirl then. The example you have is rather unlikely to deadlock, since it doesn't allocate within the threads. I'll try to get this beastie cut down to size where you can try it out ...
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> Ares All times are GMT - 6 Hours
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
Page 8 of 9

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group