Sources Bugzilla – Bug 13690
pthread_mutex_unlock potentially cause invalid access
Last modified: 2012-12-03 23:57:07 UTC
It seems pthread_mutex_unlock() potentially cause invalid access on most platforms (except for i386 and x86_64). In nptl/pthread_mutex_unlock.c, lll_unlock() is called like this: lll_unlock (mutex->__data.__lock, PTHREAD_MUTEX_PSHARED (mutex)); And PTHREAD_MUTEX_PSHARED() is defined like this: # define PTHREAD_MUTEX_PSHARED(m) \ ((m)->__data.__kind & 128) On most platforms, lll_unlock() is defined as a macro like this: #define lll_unlock(lock, private) \ ((void) ({ \ int *__futex = &(lock); \ int __val = atomic_exchange_rel (__futex, 0); \ if (__builtin_expect (__val > 1, 0)) \ lll_futex_wake (__futex, 1, private); \ })) Thus, the lll_unlock() call in pthread_mutex_unlock.c will be expanded as: int *__futex = &(mutex->__data.__lock); int __val = atomic_exchange_rel (__futex, 0); if (__builtin_expect (__val > 1, 0)) /* A */ lll_futex_wake (__futex, 1, ((mutex)->__data.__kind & 128)); /* B */ On point "A", the mutex is actually unlocked, so other threads can lock the mutex, unlock, destroy and free. If the mutex was destroyed and freed by other thread, reading '__kind' on point "B" is not valid. This can happen with this example in pthread_mutex_destroy manual. http://pubs.opengroup.org/onlinepubs/007904875/functions/pthread_mutex_destroy.html ------------------------------------------------------------------------ Destroying Mutexes A mutex can be destroyed immediately after it is unlocked. For example, consider the following code: struct obj { pthread_mutex_t om; int refcnt; ... }; obj_done(struct obj *op) { pthread_mutex_lock(&op->om); if (--op->refcnt == 0) { pthread_mutex_unlock(&op->om); (A) pthread_mutex_destroy(&op->om); (B) free(op); } else (C) pthread_mutex_unlock(&op->om); } In this case obj is reference counted and obj_done() is called whenever a reference to the object is dropped. Implementations are required to allow an object to be destroyed and freed and potentially unmapped (for example, lines A and B) immediately after the object is unlocked (line C). ------------------------------------------------------------------------ In this example, (A) and (B) can be executed in middle of (C) execution. It can happen in this way (explanation by KOSAKI-san): 1) Thread-1) atomic_exchange_rel(0) 2) preempt 3) Thread-2) call mutex_lock(). (ok, it's success) 4) Thread-2) call mutex_unlock() 5) Thread-2) call mutex_destroy() 6) Thread-2) free(mutex) 7) preempt 8) Thread-3) reuse memory of the mutex 9) preempt 10) Thread-1) dereference (mutex)->__data__.__kind Copying __kind to a local variable before atomic_exchange_rel will fix this.
Nemoto-san, Do you think you could come up with a patch to fix this? I think we need to adjust ntpl/pthread_mutex_unlock.c to pass down private as a copy of a local variable.
(In reply to comment #1) > Do you think you could come up with a patch to fix this? > > I think we need to adjust ntpl/pthread_mutex_unlock.c to pass down private as a > copy of a local variable. Though fixing just one lll_unlock call in pthread_mutex_unlock.c seems so easy, I wonder there might be other places to fix, but not sure. For example: * lll_futex_wake call in __pthread_mutex_unlock_full (PP mutex case) * lll_unlock call in __pthread_rwlock_unlock So I hope nptl experts fix this properly. Thank you.
(In reply to comment #2) > For example: > * lll_futex_wake call in __pthread_mutex_unlock_full (PP mutex case) > * lll_unlock call in __pthread_rwlock_unlock > > So I hope nptl experts fix this properly. > Thank you. Start slowly. Fix the first known problem. Then move on to the next. Do you think you could come up with a patch to *only* fix the lll_unlock usage problem?
Analogous bugs are ENDEMIC in glibc/NPTL and so far there's been a complete unwillingless to fix them or even acknowledge that they exist. See http://sourceware.org/bugzilla/show_bug.cgi?id=12674 Fixing the issue to ensure that a synchronization object's memory is not touched whatsoever after it's unlocked/posted is non-trivial, but once you figure out the solution, it's rather general-purpose. A while back I audited all my synchronization primitives in musl libc for similar bugs and fixed them, so it might be a useful source for ideas to fix glibc/NPTL.
Created attachment 6222 [details] a patch to fix only lll_unlock,lll_robust_unlock call in pthread_mutex_unlock
(In reply to comment #3) > Start slowly. Fix the first known problem. Then move on to the next. > > Do you think you could come up with a patch to *only* fix the lll_unlock usage > problem? OK, I just have uploaded a patch with obvious fixes only.
(In reply to comment #4) > Analogous bugs are ENDEMIC in glibc/NPTL and so far there's been a complete > unwillingless to fix them or even acknowledge that they exist. See > http://sourceware.org/bugzilla/show_bug.cgi?id=12674 > > Fixing the issue to ensure that a synchronization object's memory is not > touched whatsoever after it's unlocked/posted is non-trivial, but once you > figure out the solution, it's rather general-purpose. A while back I audited > all my synchronization primitives in musl libc for similar bugs and fixed them, > so it might be a useful source for ideas to fix glibc/NPTL. I've assigned myself to BZ#12674 and I'll review the issue. Thank you for bringing up the issue.
(In reply to comment #6) > (In reply to comment #3) > > Start slowly. Fix the first known problem. Then move on to the next. > > > > Do you think you could come up with a patch to *only* fix the lll_unlock usage > > problem? > > OK, I just have uploaded a patch with obvious fixes only. Nemoto-san, Thank you very much for posting the patch! What kind of testing have you done with the patch? Do you have a small test case that can trigger the failure even sporadically? It would be nice to get a test case added that documents the class of failure we tried to fix.
For all bugs like this, I suspect hitting the race condition will require running the test case for months or years. That's part of why bugs like this are so frustrating: imagine your mission-critical system crashing just a couple times a year and the crash not being reproducible. It might be easier to hit the race with some extreme usage of scheduling priorities to prevent the unlocking thread from executing for a long time.
(In reply to comment #9) > For all bugs like this, I suspect hitting the race condition will require > running the test case for months or years. That's part of why bugs like this > are so frustrating: imagine your mission-critical system crashing just a couple > times a year and the crash not being reproducible. It might be easier to hit > the race with some extreme usage of scheduling priorities to prevent the > unlocking thread from executing for a long time. I agree, but a test case need not be an exact representation of your application under test. The trick I normally use is to preload an auditing library and use the plt_enter and plt_exit stubs to slow down a thread, widening the race window or in some cases making it a 100% reliable reproducer. Such a trick is a perfectly acceptable way to make a test case, but might be hard to use in this situation.
If that's acceptable, you could just make the test case either a gdb script or a dedicated ptrace-using parent process that puts a breakpoint at the right location to hit the race...
(In reply to comment #8) > What kind of testing have you done with the patch? > > Do you have a small test case that can trigger the failure even sporadically? > > It would be nice to get a test case added that documents the class of failure > we tried to fix. Unfortunately I could not reproduce the problem and do not have any test case. Actually, this problem was discovered by an code analysis from a report that indicates futex_wake syscall was called with a wrong private flag. So my patch is just a theoretical fix.
(In reply to comment #11) > If that's acceptable, you could just make the test case either a gdb script or > a dedicated ptrace-using parent process that puts a breakpoint at the right > location to hit the race... I like the idea of a ptrace-using parent process to trigger the race condition, but it's fragile. I like your suggestion though.
Nemoto-san, The patch looks good to me. My only worry is that the performance of the robust unlock fast path is impacted. I notice that PTHREAD_ROBUST_MUTEX_PSHARED always returns LLL_SHARED. Therefore it would be optimal if instead of a temporary we just passed down LLL_SHARED (a constant). I don't know why glibc has the PTHREAD_ROBUST_MUTEX_PSHARED macro. The code comment says: ~~~ /* The kernel when waking robust mutexes on exit never uses FUTEX_PRIVATE_FLAG FUTEX_WAKE. */ #define PTHREAD_ROBUST_MUTEX_PSHARED(m) LLL_SHARED ~~~ Which appears to imply that at some point in the future it might not always return LLL_SHARED. Therefore your patch is correct. Can you verify that the instruction sequences generated are identical given the optimization level -O2 used to compile glibc?
(In reply to comment #14) > Can you verify that the instruction sequences generated are identical given the > optimization level -O2 used to compile glibc? Yes, I verified __pthread_mutex_unlock_full code sequences are identical.
(In reply to comment #15) > (In reply to comment #14) > > Can you verify that the instruction sequences generated are identical given the > > optimization level -O2 used to compile glibc? > > Yes, I verified __pthread_mutex_unlock_full code sequences are identical. Nemoto-san, Thank you for checking. I've gone through the patch and I think it's good, but I'd like someone else to also review the change. Given that Jakub commented on the patch on libc-alpha I'll ask him to review the patch attached to this issue. Jakub, Could you please review this patch?
(In reply to comment #0) > Thus, the lll_unlock() call in pthread_mutex_unlock.c will be expanded as: > int *__futex = &(mutex->__data.__lock); > int __val = atomic_exchange_rel (__futex, 0); > if (__builtin_expect (__val > 1, 0)) /* A */ > lll_futex_wake (__futex, 1, ((mutex)->__data.__kind & 128)); /* B */ > > On point "A", the mutex is actually unlocked, so other threads can > lock the mutex, unlock, destroy and free. If the mutex was destroyed > and freed by other thread, reading '__kind' on point "B" is not valid. You read the code incorrectly. If B is reached there must be another thread using the mutex. It is currently waiting. In that case it is invalid to destroy the mutex. In any case would there be another memory access, from the thread which is woken by the lll_futex_wake call. The same applies to whatever you try to change with your patch. Again, as long as a thread is waiting on a mutex you cannot destroy it legally. Show me a place where the code is accessing the futex after the unlock when there is no locker.
You misunderstand the race. Suppose thread A is unlocking the mutex and gets descheduled after the atomic_exchange_rel but before the lll_futex_wake, and thread B is waiting to lock the mutex. At this point, as far thread B can observe, A is no longer a user of the mutex. Thread B obtains the mutex, performs some operations, unlocks the mutex, and assuming (correctly) that it's now the last user of the mutex, destroys it and frees the memory it occupied. Now at some later point, thread A gets scheduled again and crashes accessing freed memory. If you're wondering how thread B could wake up without thread A calling lll_futex_wake, here are several reasons: 1. Never going to sleep due to value mismatch on the original futex wait call. 2. Receipt of a signal, and value mismatch when the signal handler returns and futex wait is called again. 3. Spurious wakes that look like successful returns from wait. These do exist in Linux, and I have not been able to determine the reason, but I have a test program which can successfully produce them in one case (unrelated to mutexes).
Given Ulrich's comments I'm going back to review the code. I'd like this fixed before the 2.16 release, and therefore I'm marking this with a target milestone of 2.16.
Please also examine the corresponding bug for sem_post, #12674, which is exactly the same type of bug.
Removing glibc_2.15 keyword as backport suitability can't be judged until there is a fix on master. After this is fixed on master, anyone wanting a backport should feel free to attach a tested backport patch to this bug (or a new bug, if this one is closed as fixed).
Jakub, could you review this one, please?