Bug report: Memory corrupion due to stale robust_list.head pointer

Bug report: Memory corrupion due to stale robust_list.head pointer

[d.dorau]

[-- Attachment #1.1: Type: text/plain, Size: 1887 bytes --]

Hello,

I recently came across a memory corruption in the member "tsd" of struct 
pthread
in a scenario where a pthread mutex is intentionally held during fork().
I experienced this using the lastest release 1.1.23.

I found that during fork musl resets self->robust_list.pending and 
self->robust_list.off,
but not the robust_list.head. The stale pointer to the previously held and 
reset
mutex turned out to be the cause for the following corruption.

I therefore suggest to also reset the list head on fork as such:

--- a/src/process/fork.c.orig   2019-09-23 11:41:01.381626360 +0200
+++ b/src/process/fork.c        2019-09-23 11:41:26.657819473 +0200
@@ -27,6 +27,7 @@
                self->tid = __syscall(SYS_gettid);
                self->robust_list.off = 0;
                self->robust_list.pending = 0;
+               self->robust_list.head = &self->robust_list.head;
                self->next = self->prev = self;
                __thread_list_lock = 0;
                libc.threads_minus_1 = 0;


This resolves the issue.

I am very well aware of the fact that aquiring a mutex during fork and 
re-initializing 
in the child appears to result in undefined behaviour (as of 
pthread_mutex_init(3posix))
or to be controversial at least.

However I believe that it should't result in a memory corruption as a 
result.

To reproduce I wrote a small example which triggers and shows the 
curruption.
It also contains a description of the program flow and memory corruption.

Please find it attached to this mail.

Please note that the routine to print the robust_list is hacked using 
hardcoded
offsets which are aimed at my 32-Bit platform.


Best regards,
Daniel





--
AVM Audiovisuelles Marketing und Computersysteme GmbH
Alt-Moabit 95, 10559 Berlin
HRB 23075 AG Charlottenburg
Geschäftsführer: Johannes Nill
 

[-- Attachment #1.2: Type: text/html, Size: 3795 bytes --]

[-- Attachment #2: pthread_fork_demo.c --]
[-- Type: application/octet-stream, Size: 9818 bytes --]

/********************************************************************************
 *
 *      main() needs to hold a mutex on a resource while forking.
 *      Therefore it utilizes pthread_atfork to aquire the mutex before
 *      fork() and to release it afterwards in the parent process.
 *
 *      Since that mutex is not valid any longer in the child process after
 *      fork, it needs to be reinitialized using pthread_mutex_init.
 *      Because the childs robust list head is not cleared during fork,
 *      it still holds a stale reference to mutex M1.
 *
 *      If a second thread is then created which aquires this mutex M1,
 *      in alternation with the main thread using mutex M2, this stale
 *      link will eventually lead to corruption of the seconds thread's
 *      tsd member because the main thread's pthread_mutex_unlock call
 *      does not recognize the second's thread robust list head.
 *
 *      Please follow the following flow which illustrates how the
 *      linked lists lead to the memory corruption.
 *
 *      The example program below contains a helper function
 *      print_robust_list() which prints the robust list in order to show
 *      the links.
 *      The sleep() calls in the example program are included to
 *      do the mutex lock/unlock calls in the order below:
 *
 *
 *      Main Thread                                                 Second Thread
 *                             --- is link via next
 *                             === is link via prev
 *
 *      after fork():
 *      RL --> M1
 *
 *      after pthread_create():
 *      RL --> M1                                                   RL
 *
 *      after second thread locks M1:
 *      RL -->  M1 -----------------------------------------------> RL
 *                 ===============================================>
 *                 <-----------------------------------------------
 *
 *
 *      after main thread locks M2:
 *      RL -->  M2  -->  M1  -------------------------------------> RL
 *         <==      <==      <------------------------------------
 *
 *
 *      after second thread unlocks M1:
 *      RL -->  M2  ----------------------------------------------> RL ---> M1
 *         <==                                                         <---
 *                  <======================================================
 *
 *
 *      after main thread unlocks M2:
 *      RL -------------------------------------------------------> RL
 *         <======================================================
 *
 *      The last step overwrites thread->tsd of the second thread with
 *      the address of the main thread's robust list head.
 *
 *
 *      OUTPUT:
 *      Running the example program shows the following output:
 *
 *      init mutex
 *      init mutex
 *      prepare fork
 *      after fork parent
 *      after fork child
 *      init mutex
 *      malloc=0x564be180
 *      pthread_setspecific done key=0
 *      tsd=77214e00 tsd[0]=564be180
 *      thread_func: lock &mutex_one
 *      robust list of thread_func
 *      &head=0x77214dcc head=0x564be140 offset=0
 *      mutex ptr=0x564be140
 *            type=1
 *            lock=3719
 *            count=0
 *            prev=77214dcc
 *      main: lock &mutex_two
 *      robust list of thread_func
 *      &head=0x77214dcc head=0x564be140 offset=0
 *      mutex ptr=0x564be140
 *            type=1
 *            lock=3719
 *            count=0
 *            prev=564be170     <-- M1 prev is changed by the main
 *                                  thread aquiring M2
 *      pthread_getspecific = 0x564be180
 *      tsd=77214e00 tsd[0]=564be180
 *      thread_func: unlock &mutex_one
 *      robust list of thread_func
 *      &head=0x77214dcc head=0x564be140 offset=0
 *      mutex ptr=0x564be140
 *            type=1
 *            lock=0
 *            count=0
 *            prev=564be170
 *      main: unlock &mutex_two
 *      pthread_getspecific = 0x77214dcc    <--- Second thread's tsd is corrupted
 *      tsd=772e4e8c tsd[0]=77214dcc
 *      destructor for 0x77214dcc
 *
 *
 *      The proposed solution is to clear the robust list during fork().
 *
 *******************************************************************************/



#define _GNU_SOURCE
#include <pthread.h>
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <errno.h>
#include <stdlib.h>
#include <sys/types.h>


pthread_mutex_t mutex_one, mutex_two, mutex_three;
pthread_t thread;
pthread_key_t key;
pthread_once_t key_once = PTHREAD_ONCE_INIT;


#define lock(mutex) dolock(mutex, __func__, #mutex)
void dolock(pthread_mutex_t *mutex, const char *func, char *name)
{
    int ret;

    printf("%s: lock %s\n", func, name);
    ret = pthread_mutex_lock(mutex);
    if (ret != 0) {
        printf("pthread_mutex_lock %s failed(%d)\n", name, errno);
    }
}

#define unlock(mutex) dounlock(mutex, __func__, #mutex)
void dounlock(pthread_mutex_t *mutex, const char *func, char *name)
{
    int ret;

    printf("%s: unlock %s\n", func, name);
    ret = pthread_mutex_unlock(mutex);
    if (ret != 0) {
        printf("pthread_mutex_unlock %s failed(%d)\n", name, errno);
    }
}


void init_mutex(pthread_mutex_t *lock)
{
    int ret;

    printf("init mutex\n");
    pthread_mutexattr_t attr;
    ret = pthread_mutexattr_init(&attr);
    if (ret != 0) {
        printf("pthread_mutexattr_init failed (%d)\n", errno);
        return;
    }
    ret = pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ERRORCHECK);
    if (ret != 0) {
        printf("pthread_mutexattr_settype failed (%d)\n", errno);
        return;
    }
    ret = pthread_mutex_init(lock, &attr);
    if (ret != 0) {
        printf("pthread_mutex_init failed (%d)\n", errno);
        return;
    }
    pthread_mutexattr_destroy(&attr);
}

void prepare_fork(void)
{
    int ret;

    printf("prepare fork\n");
    ret = pthread_mutex_lock(&mutex_one);
    if (ret != 0) {
        printf("lock mutex_one failed (%d)\n", errno);
    }
}

void after_fork_parent(void)
{
    int ret;

    printf("after fork parent\n");
    ret = pthread_mutex_unlock(&mutex_one);
    if (ret != 0) {
        printf("parent unlock mutex_one failed (%d)\n", errno);
    }
}

void after_fork_child(void)
{
    printf("after fork child\n");
    init_mutex(&mutex_one);
}

void destructor(void* ptr)
{
    printf("destructor for %p\n", ptr);
    free(ptr);
}

void make_key(void)
{
    int ret;
    ret = pthread_key_create(&key, destructor);
    if (ret != 0) {
        printf("pthread_key_create failed (%d)\n", errno);
    }
}


/*-------------------------------------------------------------------------------------*\
 * Note: offsets in struct pthread hardcoded from pthread_impl.h assuming a 32 bit
 * system.
\*-------------------------------------------------------------------------------------*/
void print_robust_list(pthread_t thread, const char* func)
{
    void* head;
    void* next;

    printf("robust list of %s\n", func);
    head = ((void**)thread)[20];

    printf("&head=%p head=%p\n", &((void**)thread)[20], head);

    next = head;
    while (next != (void*)&((unsigned int*)thread)[20]) {
        printf("mutex ptr=%p\n", next);
        printf("      type=%d\n", ((int*)next)[-4]);
        printf("      lock=%d\n", ((int*)next)[-3]);
        printf("      count=%d\n", ((int*)next)[1]);
        printf("      prev=%x\n", ((int*)next)[-1]);
        next = *(void**)(next);
    }
}


/*-------------------------------------------------------------------------------------*\
\*-------------------------------------------------------------------------------------*/
void *thread_func(void* arg)
{
    void *ptr;

    pthread_once(&key_once, make_key);
    if ((ptr = pthread_getspecific(key)) == NULL) {
        ptr = malloc(512);
        printf("malloc=%p\n", ptr);
    }
    pthread_setspecific(key, ptr);
    printf("pthread_setspecific done key=%u\n", (unsigned)key);
    printf("tsd=%x tsd[0]=%x\n", ((unsigned int*)pthread_self())[19], ((unsigned int*)((unsigned int*)pthread_self())[19])[(unsigned)key]);

    lock(&mutex_one);
    print_robust_list(pthread_self(), __func__);

    sleep(2);

    print_robust_list(pthread_self(), __func__);
    printf("pthread_getspecific = %p\n", pthread_getspecific(key));
    printf("tsd=%x tsd[0]=%x\n", ((unsigned int*)pthread_self())[19], ((unsigned int*)((unsigned int*)pthread_self())[19])[(unsigned)key]);

    unlock(&mutex_one);
    print_robust_list(pthread_self(), __func__);

    sleep(4);

    printf("pthread_getspecific = %p\n", pthread_getspecific(key));
    printf("tsd=%x tsd[0]=%x\n", ((unsigned int*)pthread_self())[19], ((unsigned int*)((unsigned int*)pthread_self())[19])[(unsigned)key]);
    return NULL;
}


/*-------------------------------------------------------------------------------------*\
\*-------------------------------------------------------------------------------------*/
int main(int argc, char *argv[])
{
    int ret;
    pid_t child;

    init_mutex(&mutex_one);

    ret = pthread_atfork(prepare_fork, after_fork_parent, after_fork_child);

    if (ret != 0) {
        printf("pthread_atfork failed (%d)\n", errno);
        return 0;
    }

    child = fork();
    if (child < 0) {
        printf("fork failed (%d)\n", errno);
        return 0;
    }
    if (child > 0) {
        sleep(10);  /* do not clutter debug output with prompt */
        return 0;
    }

    init_mutex(&mutex_two);

    ret = pthread_create(&thread, NULL, thread_func, NULL);
    if (ret != 0) {
        printf("pthread_create failed (%d)\n", errno);
        return 0;
    }

    sleep(2);

    lock(&mutex_two);

    sleep(2);

    unlock(&mutex_two);

    ret = pthread_join(thread, NULL);
    if (ret != 0) {
        printf("pthread_join failed (%d)\n", errno);
    }

    return 0;
}

Re: Bug report: Memory corrupion due to stale robust_list.head pointer

[Rich Felker]

On Wed, Sep 25, 2019 at 12:05:18PM +0200, d.dorau@avm.de wrote:
> Hello,
> 
> I recently came across a memory corruption in the member "tsd" of struct 
> pthread
> in a scenario where a pthread mutex is intentionally held during fork().
> I experienced this using the lastest release 1.1.23.
> 
> I found that during fork musl resets self->robust_list.pending and 
> self->robust_list.off,
> but not the robust_list.head. The stale pointer to the previously held and 
> reset
> mutex turned out to be the cause for the following corruption.
> 
> I therefore suggest to also reset the list head on fork as such:
> 
> --- a/src/process/fork.c.orig   2019-09-23 11:41:01.381626360 +0200
> +++ b/src/process/fork.c        2019-09-23 11:41:26.657819473 +0200
> @@ -27,6 +27,7 @@
>                 self->tid = __syscall(SYS_gettid);
>                 self->robust_list.off = 0;
>                 self->robust_list.pending = 0;
> +               self->robust_list.head = &self->robust_list.head;
>                 self->next = self->prev = self;
>                 __thread_list_lock = 0;
>                 libc.threads_minus_1 = 0;
> 
> 
> This resolves the issue.
> 
> I am very well aware of the fact that aquiring a mutex during fork and 
> re-initializing 
> in the child appears to result in undefined behaviour (as of 
> pthread_mutex_init(3posix))
> or to be controversial at least.
> 
> However I believe that it should't result in a memory corruption as a 
> result.

This is definitely undefined behavior, for exactly the types of reason
you encountered. I agree it's useful to limit the scope of memory
corruption that might occur on such invalid usage though.

Your patch is probably ok but before merging I'd like to take some
time to consider whether there are any valid usage cases it breaks (so
far, I don't think so) and whether any other easily-caught cases are
missed. For example, it is possible that the child attempts to use the
mutex in non-UB ways like locking or unlocking it, but those should
produce errors before even touching the robust list. In theory there's
a tid-reuse problem that could allow child to unlock a mutex that used
to be held by another thread in the parent, but (1) this can only be
hit if the child is doing non-AS-safe things after a MT fork, and (2)
musl already avoids this problem by using the robust list even for
non-robust mutexes. I don't think (2) is 100% complete in the case
where a MT program forks with non-pshared mutexes and the child makes
new threads, but this is very very far into UB territory.

> To reproduce I wrote a small example which triggers and shows the 
> curruption.
> It also contains a description of the program flow and memory corruption.
> 
> Please find it attached to this mail.
> 
> Please note that the routine to print the robust_list is hacked using 
> hardcoded
> offsets which are aimed at my 32-Bit platform.

Thanks for the detailed report.

Rich

Re: Bug report: Memory corrupion due to stale robust_list.head pointer

[Rich Felker]

On Wed, Sep 25, 2019 at 08:21:10AM -0400, Rich Felker wrote:
> On Wed, Sep 25, 2019 at 12:05:18PM +0200, d.dorau@avm.de wrote:
> > Hello,
> > 
> > I recently came across a memory corruption in the member "tsd" of struct 
> > pthread
> > in a scenario where a pthread mutex is intentionally held during fork().
> > I experienced this using the lastest release 1.1.23.
> > 
> > I found that during fork musl resets self->robust_list.pending and 
> > self->robust_list.off,
> > but not the robust_list.head. The stale pointer to the previously held and 
> > reset
> > mutex turned out to be the cause for the following corruption.
> > 
> > I therefore suggest to also reset the list head on fork as such:
> > 
> > --- a/src/process/fork.c.orig   2019-09-23 11:41:01.381626360 +0200
> > +++ b/src/process/fork.c        2019-09-23 11:41:26.657819473 +0200
> > @@ -27,6 +27,7 @@
> >                 self->tid = __syscall(SYS_gettid);
> >                 self->robust_list.off = 0;
> >                 self->robust_list.pending = 0;
> > +               self->robust_list.head = &self->robust_list.head;
> >                 self->next = self->prev = self;
> >                 __thread_list_lock = 0;
> >                 libc.threads_minus_1 = 0;
> > 
> > 
> > This resolves the issue.
> > 
> > I am very well aware of the fact that aquiring a mutex during fork and 
> > re-initializing 
> > in the child appears to result in undefined behaviour (as of 
> > pthread_mutex_init(3posix))
> > or to be controversial at least.
> > 
> > However I believe that it should't result in a memory corruption as a 
> > result.
> 
> This is definitely undefined behavior, for exactly the types of reason
> you encountered. I agree it's useful to limit the scope of memory
> corruption that might occur on such invalid usage though.
> 
> Your patch is probably ok but before merging I'd like to take some
> time to consider whether there are any valid usage cases it breaks (so
> far, I don't think so) and whether any other easily-caught cases are
> missed. For example, it is possible that the child attempts to use the
> mutex in non-UB ways like locking or unlocking it, but those should
> produce errors before even touching the robust list. In theory there's
> a tid-reuse problem that could allow child to unlock a mutex that used
> to be held by another thread in the parent, but (1) this can only be
> hit if the child is doing non-AS-safe things after a MT fork, and (2)
> musl already avoids this problem by using the robust list even for
> non-robust mutexes. I don't think (2) is 100% complete in the case
> where a MT program forks with non-pshared mutexes and the child makes
> new threads, but this is very very far into UB territory.

I was thinking it might be valid for fork to walk the robust list and
put all locked non-pshared mutexes from the parent in a
permanently-unusable state in the child, before clearing the robust
list pointer. However, on further consideration it doesn't seem valid
to even access the robust list at all in the child, since it might
contain entries which exist in shared memory and which could be
unlocked by the parent (thereby invalidating the prev/next pointers)
before the child can access them. So I think we should just be content
that the cases tid-reuse can affect are UB anyway.

Note that all of this is an aside, and does not seem like a
counterindication for the safety patch proposed above.

Rich