Bug 16742 - race condition: pthread_atfork() called before first malloc() results in unexpected locking behaviour/deadlocks
Summary: race condition: pthread_atfork() called before first malloc() results in unex...
Status: RESOLVED FIXED
Alias: None
Product: glibc
Classification: Unclassified
Component: malloc (show other bugs)
Version: 2.19
: P2 normal
Target Milestone: 2.24
Assignee: Florian Weimer
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-03-22 18:35 UTC by prumpf
Modified: 2016-04-14 12:53 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Last reconfirmed:
fweimer: security-


Attachments
Test case (318 bytes, text/x-csrc)
2014-03-22 18:35 UTC, prumpf
Details
proposed patch (2.85 KB, patch)
2014-06-12 20:10 UTC, prumpf
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description prumpf 2014-03-22 18:35:17 UTC
Created attachment 7488 [details]
Test case

This issue appears with pthreads and NPTL on the latest git version of glibc (and the latest git version of Perl).

I'm not sure this is a bug according to the specifications, but it is both extremely counterintuitive and occurs in practice, with the latest version of Perl: https://rt.perl.org/Public/Bug/Display.html?id=121490  I believe it is worth fixing.

When pthread_atfork() is called prior to the first malloc() call in the program, the malloc atfork handlers are called before the user's atfork handlers, resulting in unpredictable locking order and deadlocks.

Here's a test case:

#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void lock(void)
{
  pthread_mutex_lock(&mutex);
}

void unlock(void)
{
  pthread_mutex_unlock(&mutex);
}

void *lock_then_malloc(void *dummy)
{
  pthread_mutex_lock(&mutex);
  sleep(2);
  volatile void *throwaway = malloc(1024);
  pthread_mutex_unlock(&mutex);
  return NULL;
}

int main(int argc, char **argv)
{
  pthread_attr_t attr;
  pthread_t tid;

  volatile void *throwaway;
  if (argc > 1)
    throwaway = malloc(1024);

  pthread_atfork(lock, unlock, unlock);

  pthread_attr_init(&attr);
  pthread_create(&tid, &attr, lock_then_malloc, NULL);

  sleep(1);
  fork();

  return 0;
}


The expected behaviour is that the program terminates (after two seconds) whether or not an extra argument is supplied; the actual behaviour is that the program terminates only if an extra argument is present: the (otherwise useless) call to malloc() means ptmalloc_init() gets called before rather than after main() calls pthread_atfork(), changing the order in which atfork handlers are run. In the case without an extra argument, the main thread then holds the mutex and is waiting on malloc/arena.c's list_lock, while the other thread hold list_lock and is waiting on the mutex.

This is essentially what Perl does: it calls pthread_atfork() before first calling malloc(), then locks a mutex both in the atfork handler and in another thread which then calls malloc().

While I think this definitely needs to be fixed, I'm not sure what the best fix would be. A simplistic workaround would be to call malloc() from pthread_create(), while a more elegant solution would be to allow a priority argument for pthread_atfork(), with user-defined handlers always ending up outside of malloc/glibc-defined handlers. The ChangeLog suggests there once existed a function called __register_atfork_malloc(), which might have done this already.

(Note that we never get to unlock(), so it's irrelevant whether pthread_mutex_unlock() works after the fork(). )
Comment 1 prumpf 2014-06-12 20:10:17 UTC
Created attachment 7633 [details]
proposed patch
Comment 2 prumpf 2014-06-12 20:12:47 UTC
I've attached a patch that would fix this issue (and a closely-related one described at https://sourceware.org/ml/libc-alpha/2013-01/msg01051.html), but which I'm not entirely satisfied is the right thing to do yet (it also contains a debugging XXX). Still, it might serve as a starting point for fixing this. The draft message I'd prepared for it follows:

------------

This is a bug report and proposed patch for the git version of glibc; it is specific to NPTL.

There appear to be at least two deadlock problems caused by the order in which atfork handlers, in particular ptmalloc_lock_all, are run.

https://sourceware.org/bugzilla/show_bug.cgi?id=16742 means ptmalloc_lock_all must be run after other atfork handlers, even if registered after them.
https://sourceware.org/ml/libc-alpha/2013-01/msg01051.html is a bit trickier: it demonstrates that lock ordering should be "lock IO list before taking malloc locks", which means ptmalloc_lock_all has to be run with the IO list lock already held. Other solutions would work as well, but I've focussed on that one since it puts the least constraints on libio. This bug can be reproduced by running a test program with the right breakpoints set in gdb.
I've prepared a patch that I believe fixes the problem, but I'm not overly attached to doing it this way.

This patch fixes both deadlocks and introduces the concept of an atfork handler's priority—a high-priority handler is run inside of a low-priority one; it creates a new atfork handler for the IO lock, and gives it priority intermediate between low-priority user handlers and the high-priority malloc atfork handler; it uses a high priority for malloc's atfork handler; it adjusts register-atfork.c and unregister-atfork.c so they keep the __fork_handlers list sorted by priority.
 
The complication introduced by this patch is unfortunate, but I believe it is the best approach. However, an alternative would be: don't introduce a priority level; put _IO_list_lock into an atfork handler that's installed first; make thread_atfork install malloc's atfork handler at the end of the list, no matter what. (I believe that approach would leave us with very fragile code and without the ability to put more of our MT-specific fork code into atfork handlers.)
I believe there are no new restrictions on libio code, but there is a (new?) restriction on malloc: code must not hold malloc locks while waiting for I/O to finish, unless it gets the I/O lock first. In particular, this applies to diagnostic output and malloc.c's assert(), which might deadlock rather than printing a message.
In addition to the alternative mentioned above, I've also considered another approach: pretend to take both the I/O and the malloc lock or neither: first lock A, then try to lock B; in the failure case, unlock A, lock B, then try to lock A, and so on. However, that's complicated, doesn't extend well to the case of several high-priority atfork handlers, and might result in a livelock.
I do not suggest making the priority level accessible from user space: it's easy enough for glibc users to implement their own priority system or call pthread_atfork() in the right order.
Comment 3 Florian Weimer 2016-04-14 08:03:04 UTC
Can you retest with current master?  I believe this bug is fixed there, but in a completely different fashion (the fork handler mechanism is not used by malloc anymore).
Comment 4 prumpf 2016-04-14 12:47:36 UTC
Excellent, that's a much more elegant fix.

I can confirm the test case now works as expected (commit 186fe877f3df0b84d57dfbf0386f6332c6aa69bc), so I consider this bug fixed.

Thank you!
Comment 5 Florian Weimer 2016-04-14 12:53:46 UTC
Fixed in 2.24 per comment 4.

(I don't think this can be abused for a denial-of-service attack, so I'm clearing the security flag.)