RFC: Deadlock in multithreaded application when doing IO and fork.

[Carlos O'Donell-6]

Community,

I've seen what I believe to be the following deadlock
scenario in a multithreaded application when doing
IO and forking.

It is safe to call fork in a multthreaded environment.
It is also safe to do IO in a multithreaded environment.
Doing both at the same time is supposed to be safe,
but is known to be dangerous if you don't know what
you're doing.

The following deadlock scenario looks like a bug in glibc.

Thread A:

* Calls fork() which runs pthread_atfork handlers.
* Malloc's registered handler runs and locks out all other
  threads from doing allocations by causing them to block.
* Tries to take the IO list lock via _IO_list_lock()
  -> _IO_lock_lock(list_all_lock);

Thread B:

* Calls _IO_flush_all()
  -> _IO_flush_all_lockp (do_lock=1)
  -> _IO_lock_lock (list_all_lock); ...
* Walks the list of open fp's and tries to take each
  fp's lock and flush.

Thread C:

* Calls _IO_getdelim which takes only the fp lock
  and then tries to call either malloc or realloc.
* Tries to take arena lock to allocate memory.

So in summary:
Thread A waits on thread B for the list_all_lock lock.
Thread B waits on thread C for the fp file lock.
Thread C waits on thread A for the arena lock.

The window for this to happen is small.

You need at least three threads.

One possible fix looks like this:

Thread A:

* Calls fork() which runs pthread_atfork handlers.
* Run malloc's registered handler *last*
* Malloc's handler does:
  - Call _IO_list_lock() first.
  - Lock all arenas last.
* Continue with fork processing...

Thread B:
...

Thread C:
...

The salient point is that the last thing we do
is lock list_all_lock and then lock the arenas.

In this case A and B each try to acquire list_all_lock
before locking the arenas, and that ensures that other
threads are able to make forward progress or are
blocked, but not deadlocked.

The wrinkle here is that once you take list_all_lock
another thread could be inside malloc and trigger an
assertion or debug output, which will block, and
deadlock fork() e.g.

T1 T2
fork
take list_all_lock
                        calls malloc
                        takes arena lock.
                        malloc aborts and tries to do IO.
                                or
                        user define malloc tries to do IO.
                        blocks on list_all_lock.
blocks on arena lock

This seems like a better scenario than before. Now we only
deadlock in a failure scenario during a smaller window.

We could detect this in malloc by doing a trylock on the
list_all_lock and avoid the IO, continuing on to calling
abort().

In abort() we will flush all the IO *without* taking locks
(calls _IO_flush_all_lockp(do_lock=0)) since abort()
might be called from anywhere.

User malloc handlers will have to setup pthread_atfork
handlers to notify themselves of the upcoming fork and
that they should stop doing IO or risk inconsistent
state in the child and deadlock in the parent.

I don't see any serious performance arguments against
this fix, we are simply changing the order of the lock
acquisition. I might actually argue that by moving the
arena locking last, we actually allow other threads to
make progress while we run our handlers.

There are some arguments that can be made for locking
arenas early in the process and how that impacts performance
for the forking thread (but deteriorates it for all other
threads).

Comments?

Cheers,
Carlos.

[Roland McGrath-4]

I think it certainly makes sense for the malloc atfork handlers always to
run last.  Otherwise a user atfork handler can produce deadlock with the
user's own code in other threads in ways that don't really seem to be under
the user's control.  For example:

T1 T2
                                        takes user lock L
fork
        malloc atfork takes malloc locks
        user atfork blocks locking L
                                        calls malloc
                                                blocks on malloc locks

In fact, it's pretty easy to set this up so it always deadlocks, not even
needing a race (e.g. T2 creates T1 after locking L and then uses a
pthread_barrier to wait for T2 to enter its atfork handler before T2 calls
malloc).  That seems like a good test case to write, since I think you can
write one like this and pretty easily see that it is POSIX-compliant.

With user atfork handlers that call malloc themselves, it can probably get
even weirder.  (Calling malloc in an atfork handler seems like a bad idea
all around, but AFAICT it is kosher under POSIX.)

It's less clear whether that's really sufficient for all kosher scenarios.
If I understood you correctly, the scenario you cited is one that in the
best case would lead to a crash.  That is, the user has provoked undefined
behavior.  In that case, it's as kosher to deadlock as it is to crash
coherently with malloc assertions, albeit much less useful.  So we don't
have a hard mandate to avoid those deadlock cases.  Hence it's a tradeoff
of difficulty, maintenance burden, and performance hits vs being extra nice
in helping people diagnose their own bugs.  Similarly, setting malloc hooks
is something that really requires knowing about subtleties and internal
implementation issues already and probably always will, so putting the onus
on people who write their own malloc hooks (and especially people who think
that using malloc hooks in a multithreaded program is something they should
be doing) is fine.

I'm not all that clear on the details of the further mitigations you
suggest after the atfork change.  I think the right things to do are
(in this order):
1. write the aforementioned test and verify it always deadlocks
2. fix that test by making the malloc atfork handlers always run last
3. commit those
4. reconsider remaining undesireable scenarios in that context


Thanks,
Roland

[Carlos O'Donell-6]

On 01/31/2013 07:05 PM, Roland McGrath wrote:

> I think it certainly makes sense for the malloc atfork handlers always to
> run last.  Otherwise a user atfork handler can produce deadlock with the
> user's own code in other threads in ways that don't really seem to be under
> the user's control.  For example:
>
> T1 T2
> takes user lock L
> fork
> malloc atfork takes malloc locks
> user atfork blocks locking L
> calls malloc
> blocks on malloc locks
>
> In fact, it's pretty easy to set this up so it always deadlocks, not even
> needing a race (e.g. T2 creates T1 after locking L and then uses a
> pthread_barrier to wait for T2 to enter its atfork handler before T2 calls
> malloc).  That seems like a good test case to write, since I think you can
> write one like this and pretty easily see that it is POSIX-compliant.

Agreed. I wouldn't dream of submitting a fix for this without also having
a reliable test case.

> With user atfork handlers that call malloc themselves, it can probably get
> even weirder.  (Calling malloc in an atfork handler seems like a bad idea
> all around, but AFAICT it is kosher under POSIX.)

Agreed. We do support calling malloc from atfork handlers with some special
code in malloc, which we might be able remove if we just force malloc to
run last and ensure we don't allocate anything before we unlock the arenas.

> It's less clear whether that's really sufficient for all kosher scenarios.
> If I understood you correctly, the scenario you cited is one that in the
> best case would lead to a crash.  That is, the user has provoked undefined
> behavior.  In that case, it's as kosher to deadlock as it is to crash
> coherently with malloc assertions, albeit much less useful.  So we don't
> have a hard mandate to avoid those deadlock cases.  Hence it's a tradeoff
> of difficulty, maintenance burden, and performance hits vs being extra nice
> in helping people diagnose their own bugs.  Similarly, setting malloc hooks
> is something that really requires knowing about subtleties and internal
> implementation issues already and probably always will, so putting the onus
> on people who write their own malloc hooks (and especially people who think
> that using malloc hooks in a multithreaded program is something they should
> be doing) is fine.

You are correct, that the fix I propose opens up a deadlock in what is
effectively undefined behaviour e.g. you're on your way to abort().

I would like the *default* implementation to try and avoid the deadlock,
and I would like the documentation of the malloc hooks to provide
sufficient explanation of the situation that you could write your own
malloc hook that operates correctly under multi-threaded fork.

I feel like providing a trivial example that works is our responsibility.

> I'm not all that clear on the details of the further mitigations you
> suggest after the atfork change.  I think the right things to do are
> (in this order):

Thanks, I'll break it up like this.

> 1. write the aforementioned test and verify it always deadlocks
> 2. fix that test by making the malloc atfork handlers always run last

The fix actually requires two things:
(a) Run all atfork prepare handlers.
(b) Lock list_all_lock to prevent more IO.
(c) After (b) run malloc atfork handler e.g. run handler last.

Note that (a) can be rolled into the start of malloc's atfork
handler. Though at that point it's not just a malloc atfork handler,
it's realy a libc generic atfork handler that is doing the work of
shutting down IO *and* memory allocations in order to ensure
consistency after the fork.

> 3. commit those
> 4. reconsider remaining undesireable scenarios in that context

Right, which is "Default malloc implementation must avoid IO in
undefined scenario or deadlock." Which is a "nice to users"
situation.

Cheers,
Carlos.

[Roland McGrath-4]

> The fix actually requires two things:
> (a) Run all atfork prepare handlers.
> (b) Lock list_all_lock to prevent more IO.
> (c) After (b) run malloc atfork handler e.g. run handler last.

I don't understand the (b) requirement.  It's not required to fix the
deadlock test case I described (there is no stdio use at all in that case).
Whatever it's about, it seems like it should be a follow-up change after
the basic change to run malloc atfork last.

[Carlos O'Donell-6]

On 02/01/2013 01:51 PM, Roland McGrath wrote:
>> The fix actually requires two things:
>> (a) Run all atfork prepare handlers.
>> (b) Lock list_all_lock to prevent more IO.
>> (c) After (b) run malloc atfork handler e.g. run handler last.
>
> I don't understand the (b) requirement.  It's not required to fix the
> deadlock test case I described (there is no stdio use at all in that case).
> Whatever it's about, it seems like it should be a follow-up change after
> the basic change to run malloc atfork last.
 
Sorry, I didn't realize you were comparing the solution
against your particular strawman testcase.

You are correct, in that (b) is not required to fix
your testcase, but it is required to fix the deadlock
that I see with 3 threads stdio and malloc.

I have no problem breaking up the work into even
more chunks.

Cheers,
Carlos.

[Rich Felker]

On Thu, Jan 31, 2013 at 06:02:38PM -0500, Carlos O'Donell wrote:
> Community,
>
> I've seen what I believe to be the following deadlock
> scenario in a multithreaded application when doing
> IO and forking.
>
> It is safe to call fork in a multthreaded environment.

But not safe to use async-signal-unsafe functions in the child after
fork. In particular, malloc is not legal after fork in a
multi-threaded program, so the simplest solution would be to remove
all the atfork handling for malloc.

I realize however this may be unpopular...

Rich

[Roland McGrath-4]

> But not safe to use async-signal-unsafe functions in the child after
> fork. In particular, malloc is not legal after fork in a
> multi-threaded program, so the simplest solution would be to remove
> all the atfork handling for malloc.

The issues at hand are in the atfork handlers that run in the parent.
There are no restrictions on what calls those can make.

[Rich Felker]

On Fri, Feb 01, 2013 at 01:01:38PM -0800, Roland McGrath wrote:
> > But not safe to use async-signal-unsafe functions in the child after
> > fork. In particular, malloc is not legal after fork in a
> > multi-threaded program, so the simplest solution would be to remove
> > all the atfork handling for malloc.
>
> The issues at hand are in the atfork handlers that run in the parent.
> There are no restrictions on what calls those can make.

I'm not claiming it's disallowed to poke with malloc in the parent.
I'm claiming it's useless to use atfork handlers to attempt to give
the child a consistent malloc state because the child is not allowed
to use malloc anyway.

Rich

[KOSAKI Motohiro-2]

> But not safe to use async-signal-unsafe functions in the child after
> fork. In particular, malloc is not legal after fork in a
> multi-threaded program, so the simplest solution would be to remove
> all the atfork handling for malloc.

But the simplest solution break several applications. Example, OpenJDK call
opendir("/proc/self/fd") when spawning new process and our opendir uses
malloc internally.

So, fixing rare race and breaking major application don't seem good deal,
at least to me.

[Rich Felker]

On Fri, Feb 01, 2013 at 04:30:16PM -0500, KOSAKI Motohiro wrote:

> > But not safe to use async-signal-unsafe functions in the child after
> > fork. In particular, malloc is not legal after fork in a
> > multi-threaded program, so the simplest solution would be to remove
> > all the atfork handling for malloc.
>
> But the simplest solution break several applications. Example, OpenJDK call
> opendir("/proc/self/fd") when spawning new process and our opendir uses
> malloc internally.
>
> So, fixing rare race and breaking major application don't seem good deal,
> at least to me.

That's why I said my solution might not be popular. I think OpenJDK
should be fixed to avoid this UB, but I agree if you have applications
working now, it's somewhat unreasonable to say "what you're doing is
UB, so we're going to break it now" without giving them ample warning
and time to correct their programs...

Rich

[Carlos O'Donell-6]

On 02/01/2013 04:06 PM, Rich Felker wrote:

> On Fri, Feb 01, 2013 at 01:01:38PM -0800, Roland McGrath wrote:
>>> But not safe to use async-signal-unsafe functions in the child after
>>> fork. In particular, malloc is not legal after fork in a
>>> multi-threaded program, so the simplest solution would be to remove
>>> all the atfork handling for malloc.
>>
>> The issues at hand are in the atfork handlers that run in the parent.
>> There are no restrictions on what calls those can make.
>
> I'm not claiming it's disallowed to poke with malloc in the parent.
> I'm claiming it's useless to use atfork handlers to attempt to give
> the child a consistent malloc state because the child is not allowed
> to use malloc anyway.

While that is true, we actually go to great lengths to make as much
as possible work in the child after the fork.

Why?

Probably because it's hard to do any useful work without malloc :-)

I seem to remember that previous POSIX specifications didn't have
the restricting statement that says only async-signal safe functions
may be called after fork()?

The malloc atfork handlers look to be 10+ years old. Thus we likely
have applications in the wild that need malloc et. al. to continue
working after the fork.

The test case that actually triggers this could be fixed by removing
the malloc atfork handlers.

However, it would be a regression in the supported functionality
we have in glibc.

I'm just happy we don't have to make multithreaded fork
async-signal safe!

Cheers,
Carlos.

[Florian Weimer-5]

On 02/01/2013 12:02 AM, Carlos O'Donell wrote:

> another thread could be inside malloc and trigger an
> assertion or debug output, which will block, and
> deadlock fork() e.g.
>
> T1 T2
> fork
> take list_all_lock
> calls malloc
> takes arena lock.
> malloc aborts and tries to do IO.
> or
> user define malloc tries to do IO.
> blocks on list_all_lock.
> blocks on arena lock

The bug discussed in this old thread is now fixed on master, with commit
29d794863cd6e03115d3670707cc873a9965ba92.

IMO, the deadlock you describe is not relevant because list_all_lock is
only taken on fflush (NULL) or if a stdio stream is opened or closed.
abort does not flush the streams under list_all_lock (ugh).  Opening or
closing a stdio stream performs malloc or free, so it will potentially
deadlock even without the presence of list_all_lock, just involving the
malloc locks.  A malloc calling into stdio is just undefined.  We get
away with it to some extent because we implement both, but an interposed
malloc cannot do this.

Florian