[musl] Protect pthreads' mutexes against use-after-destroy

[musl] Protect pthreads' mutexes against use-after-destroy

[jvoisin]

Ohai,

as discussed on irc, Android's bionic has a check to prevent
use-after-destroy on phtread mutexes
(https://github.com/LineageOS/android_bionic/blob/e0aac7df6f58138dae903b5d456c947a3f8092ea/libc/bionic/pthread_mutex.cpp#L803),
and musl doesn't.

While odds are that this is a super-duper common bug, it would still be
nice to have this kind of protection, since it's cheap, and would
prevent/make it easy to diagnose weird states.

Is this something that should/could be implemented?

o/

Re: [musl] Protect pthreads' mutexes against use-after-destroy

[Rich Felker]

On Tue, Jan 09, 2024 at 03:37:17PM +0100, jvoisin wrote:
> Ohai,
> 
> as discussed on irc, Android's bionic has a check to prevent
> use-after-destroy on phtread mutexes
> (https://github.com/LineageOS/android_bionic/blob/e0aac7df6f58138dae903b5d456c947a3f8092ea/libc/bionic/pthread_mutex.cpp#L803),
> and musl doesn't.
> 
> While odds are that this is a super-duper common bug, it would still be
> nice to have this kind of protection, since it's cheap, and would
> prevent/make it easy to diagnose weird states.
> 
> Is this something that should/could be implemented?
> 
> o/

I think you meant that the odds are it's not common. There's already
enough complexity in the code paths for supporting all the different
mutex types that my leaning would be, if we do any hardening for
use-after-destroy, that it should probably just take the form of
putting the object in a state that will naturally deadlock or error
rather than adding extra checks to every path where it's used.

If OTOH we do want it to actually trap in all cases where it's used
after destroy, the simplest way to achieve that is probably to set it
up as a non-robust non-PI recursive or errorchecking mutex with
invalid prev/next pointers and owner of 0x3fffffff. Then the only
place that would actually have to have an explicit trap is trylock in
the code path:

        if (own == 0x3fffffff) return ENOTRECOVERABLE;

where it could trap if type isn't robust. The unlock code path would
trap on accessing invalid prev/next pointers.

Rich

Re: [musl] Protect pthreads' mutexes against use-after-destroy

[enh]

On Tue, Jan 9, 2024 at 11:07 AM Rich Felker <dalias@libc.org> wrote:
>
> On Tue, Jan 09, 2024 at 03:37:17PM +0100, jvoisin wrote:
> > Ohai,
> >
> > as discussed on irc, Android's bionic has a check to prevent
> > use-after-destroy on phtread mutexes
> > (https://github.com/LineageOS/android_bionic/blob/e0aac7df6f58138dae903b5d456c947a3f8092ea/libc/bionic/pthread_mutex.cpp#L803),
> > and musl doesn't.
> >
> > While odds are that this is a super-duper common bug, it would still be
> > nice to have this kind of protection, since it's cheap, and would
> > prevent/make it easy to diagnose weird states.
> >
> > Is this something that should/could be implemented?
> >
> > o/
>
> I think you meant that the odds are it's not common.

it was common enough (and hard enough to debug) that we added this
"best effort" error detection to bionic :-)

(the other "surely no-one actually does that?" mistake i can think of
in this area is that a surprising number of people seem to think that
`pthread_mutex_lock(NULL)` means something. i'm still not sure _what_
they think it means!)

> There's already
> enough complexity in the code paths for supporting all the different
> mutex types that my leaning would be, if we do any hardening for
> use-after-destroy, that it should probably just take the form of
> putting the object in a state that will naturally deadlock or error
> rather than adding extra checks to every path where it's used.

yeah, the _other_ reason we have the abort is that we've struggled
over the years to make it clear to the _callers_ that -- just because
you crash/hang in libc -- it's the _caller's_ bug. explicitly saying
so helps. (though we still get a decent number of people who don't
read/don't understand.)

> If OTOH we do want it to actually trap in all cases where it's used
> after destroy, the simplest way to achieve that is probably to set it
> up as a non-robust non-PI recursive or errorchecking mutex with
> invalid prev/next pointers and owner of 0x3fffffff. Then the only
> place that would actually have to have an explicit trap is trylock in
> the code path:
>
>         if (own == 0x3fffffff) return ENOTRECOVERABLE;
>
> where it could trap if type isn't robust. The unlock code path would
> trap on accessing invalid prev/next pointers.
>
> Rich

Re: [musl] Protect pthreads' mutexes against use-after-destroy

[Rich Felker]

On Tue, Jan 09, 2024 at 02:07:26PM -0500, Rich Felker wrote:
> On Tue, Jan 09, 2024 at 03:37:17PM +0100, jvoisin wrote:
> > Ohai,
> > 
> > as discussed on irc, Android's bionic has a check to prevent
> > use-after-destroy on phtread mutexes
> > (https://github.com/LineageOS/android_bionic/blob/e0aac7df6f58138dae903b5d456c947a3f8092ea/libc/bionic/pthread_mutex.cpp#L803),
> > and musl doesn't.
> > 
> > While odds are that this is a super-duper common bug, it would still be
> > nice to have this kind of protection, since it's cheap, and would
> > prevent/make it easy to diagnose weird states.
> > 
> > Is this something that should/could be implemented?
> > 
> > o/
> 
> I think you meant that the odds are it's not common. There's already
> enough complexity in the code paths for supporting all the different
> mutex types that my leaning would be, if we do any hardening for
> use-after-destroy, that it should probably just take the form of
> putting the object in a state that will naturally deadlock or error
> rather than adding extra checks to every path where it's used.
> 
> If OTOH we do want it to actually trap in all cases where it's used
> after destroy, the simplest way to achieve that is probably to set it
> up as a non-robust non-PI recursive or errorchecking mutex with
> invalid prev/next pointers and owner of 0x3fffffff. Then the only
> place that would actually have to have an explicit trap is trylock in
> the code path:
> 
>         if (own == 0x3fffffff) return ENOTRECOVERABLE;
> 
> where it could trap if type isn't robust. The unlock code path would
> trap on accessing invalid prev/next pointers.

Unfortunately I discovered a problem we need to deal with in
researching for this: at some point Linux quietly changed the futex
ABI, so that bit 29 is no longer reserved but potentially a tid bit.
This was documented in 9c40365a65d62d7c06a95fb331b3442cb02d2fd9 but
apparently actually happened at the source level a long time before
that. So, we cannot assume 0x3fffffff is not a valid tid, and thereby
cannot assume 0x7fffffff is not equal to ownerdead|valid_tid.

This probably means we need to find a way to encode "not recoverable"
as 0x40000000, as 0 is now the _only_ value in the low-30-bits that
can't potentially be a valid tid.

I'll look at this more over the next day or two. It's probably fixable
but requires fiddling with delicate logic.

Note that the only in-the-wild breakage possible is on systems where
the pid/tid limit has been set extremely high, where attempts to lock
a recursive or errorchecking mutex owned by a thread with tid
0x3fffffff could malfunction.

Rich

Re: [musl] Protect pthreads' mutexes against use-after-destroy

[Rich Felker]

On Tue, Jan 09, 2024 at 03:27:37PM -0800, enh wrote:
> On Tue, Jan 9, 2024 at 11:07 AM Rich Felker <dalias@libc.org> wrote:
> >
> > On Tue, Jan 09, 2024 at 03:37:17PM +0100, jvoisin wrote:
> > > Ohai,
> > >
> > > as discussed on irc, Android's bionic has a check to prevent
> > > use-after-destroy on phtread mutexes
> > > (https://github.com/LineageOS/android_bionic/blob/e0aac7df6f58138dae903b5d456c947a3f8092ea/libc/bionic/pthread_mutex.cpp#L803),
> > > and musl doesn't.
> > >
> > > While odds are that this is a super-duper common bug, it would still be
> > > nice to have this kind of protection, since it's cheap, and would
> > > prevent/make it easy to diagnose weird states.
> > >
> > > Is this something that should/could be implemented?
> > >
> > > o/
> >
> > I think you meant that the odds are it's not common.
> 
> it was common enough (and hard enough to debug) that we added this
> "best effort" error detection to bionic :-)

Thanks! That's useful information (and disturbing...)

> > There's already
> > enough complexity in the code paths for supporting all the different
> > mutex types that my leaning would be, if we do any hardening for
> > use-after-destroy, that it should probably just take the form of
> > putting the object in a state that will naturally deadlock or error
> > rather than adding extra checks to every path where it's used.
> 
> yeah, the _other_ reason we have the abort is that we've struggled
> over the years to make it clear to the _callers_ that -- just because
> you crash/hang in libc -- it's the _caller's_ bug. explicitly saying
> so helps. (though we still get a decent number of people who don't
> read/don't understand.)

That's a problem we've just not tried to address in musl, but indeed
it does happen fairly often. If we did try at some point, I think it
would be by setting up a state to make the reason more clear in the
debugger, not producing any output. But personally I'd like to keep
driving home the message that the point of crash does not mean
anything about responsibility for the crash, even if it means
responding to lots of bogus "bug reports"...

Rich

Re: [musl] Protect pthreads' mutexes against use-after-destroy

[Rich Felker]

On Tue, Jan 09, 2024 at 08:55:50PM -0500, Rich Felker wrote:
> On Tue, Jan 09, 2024 at 02:07:26PM -0500, Rich Felker wrote:
> > On Tue, Jan 09, 2024 at 03:37:17PM +0100, jvoisin wrote:
> > > Ohai,
> > > 
> > > as discussed on irc, Android's bionic has a check to prevent
> > > use-after-destroy on phtread mutexes
> > > (https://github.com/LineageOS/android_bionic/blob/e0aac7df6f58138dae903b5d456c947a3f8092ea/libc/bionic/pthread_mutex.cpp#L803),
> > > and musl doesn't.
> > > 
> > > While odds are that this is a super-duper common bug, it would still be
> > > nice to have this kind of protection, since it's cheap, and would
> > > prevent/make it easy to diagnose weird states.
> > > 
> > > Is this something that should/could be implemented?
> > > 
> > > o/
> > 
> > I think you meant that the odds are it's not common. There's already
> > enough complexity in the code paths for supporting all the different
> > mutex types that my leaning would be, if we do any hardening for
> > use-after-destroy, that it should probably just take the form of
> > putting the object in a state that will naturally deadlock or error
> > rather than adding extra checks to every path where it's used.
> > 
> > If OTOH we do want it to actually trap in all cases where it's used
> > after destroy, the simplest way to achieve that is probably to set it
> > up as a non-robust non-PI recursive or errorchecking mutex with
> > invalid prev/next pointers and owner of 0x3fffffff. Then the only
> > place that would actually have to have an explicit trap is trylock in
> > the code path:
> > 
> >         if (own == 0x3fffffff) return ENOTRECOVERABLE;
> > 
> > where it could trap if type isn't robust. The unlock code path would
> > trap on accessing invalid prev/next pointers.
> 
> Unfortunately I discovered a problem we need to deal with in
> researching for this: at some point Linux quietly changed the futex
> ABI, so that bit 29 is no longer reserved but potentially a tid bit.
> This was documented in 9c40365a65d62d7c06a95fb331b3442cb02d2fd9 but
> apparently actually happened at the source level a long time before
> that. So, we cannot assume 0x3fffffff is not a valid tid, and thereby
> cannot assume 0x7fffffff is not equal to ownerdead|valid_tid.
> 
> This probably means we need to find a way to encode "not recoverable"
> as 0x40000000, as 0 is now the _only_ value in the low-30-bits that
> can't potentially be a valid tid.
> 
> I'll look at this more over the next day or two. It's probably fixable
> but requires fiddling with delicate logic.
> 
> Note that the only in-the-wild breakage possible is on systems where
> the pid/tid limit has been set extremely high, where attempts to lock
> a recursive or errorchecking mutex owned by a thread with tid
> 0x3fffffff could malfunction.

OK, more fun. The kernel documentation (locking/robust-futex-ABI.rst)
is *wrong*. It claims that, when processing the robust list for a
dying task, the only actions are:

 1) if bit 31 (0x80000000) is set in that word, then attempt a futex
    wakeup on that address, which will waken the next thread that has
    used to the futex mechanism to wait on that address, and
 2) atomically set  bit 30 (0x40000000) in the 'lock word'.

However, 2 is incorrect. There is no "set bit 30" operation in the
kernel. Rather, it atomically replaces the old lock value (tid of the
dying task, possibly with bit 31 added on for "waiters present") with
0x40000000 (no waiters) or 0xc0000000 (maybe waiters), clearing out
the tid of the dying task.

Thus, we cannot use 0x40000000 as the "not recoverable" value; this is
the only value the kernel ever used for "owner died" state.

At first this sounds good: we should be able to use any value with bit
30 set, including something like 0x7fffffff like we're using now, as
the "not recoverable" state. Unfortunately, that's not quite true. The
kernel's robust list processing at task death masks off bit 30, so if
a task with tid 0x3fffffff were to die with the unrecoverable mutex in
its robust list or or pending slot, it would wrongly get converted
back by the kernel from "not recoverable" state to "owner died" state.

Naively one would expect an already not-recoverable not to be able to
be added to the robust list, and this is correct; however, it can be
added to the pending slot if a thread attempting to lock it was
suspended after checking the old state, before it was in
not-recoverable state, but before attempting the atomic CAS to take
the lock, seeing that fail, and removing it from the pending slot.

I don't see any solution to this problem without having one or more
values of the low 30 bits (bits 0-29) that are reserved and guaranteed
never to match a real task. AIUI, Linux presently doesn't support more
than 22 bits of tid anyway, so this probably is not a real issue, but
it is an issue for future-proofing the user-kernel interface. What
we're doing now (using 0x7fffffff as the unrecoverable value) is
unsafe if Linux or any kernel purporting to honor the Linux syscall
API/ABI ever supports full 30-bit tids.

I think we should probably ask the kernel folks to reinstate the
original specification that bit 29 (0x20000000) is reserved and
guaranteed not to be present in a valid tid. If that's deemed
inappropriate, just reserving a single value 0x3fffffff that's
guaranteed not to be a real tid should suffice. Either would make what
we're doing now (based on the old pre-2020 documentation) valid and
future-proof once again.

Rich

Re: [musl] Protect pthreads' mutexes against use-after-destroy

[enh]

On Tue, Jan 9, 2024 at 5:58 PM Rich Felker <dalias@libc.org> wrote:
>
> On Tue, Jan 09, 2024 at 03:27:37PM -0800, enh wrote:
> > On Tue, Jan 9, 2024 at 11:07 AM Rich Felker <dalias@libc.org> wrote:
> > >
> > > On Tue, Jan 09, 2024 at 03:37:17PM +0100, jvoisin wrote:
> > > > Ohai,
> > > >
> > > > as discussed on irc, Android's bionic has a check to prevent
> > > > use-after-destroy on phtread mutexes
> > > > (https://github.com/LineageOS/android_bionic/blob/e0aac7df6f58138dae903b5d456c947a3f8092ea/libc/bionic/pthread_mutex.cpp#L803),
> > > > and musl doesn't.
> > > >
> > > > While odds are that this is a super-duper common bug, it would still be
> > > > nice to have this kind of protection, since it's cheap, and would
> > > > prevent/make it easy to diagnose weird states.
> > > >
> > > > Is this something that should/could be implemented?
> > > >
> > > > o/
> > >
> > > I think you meant that the odds are it's not common.
> >
> > it was common enough (and hard enough to debug) that we added this
> > "best effort" error detection to bionic :-)
>
> Thanks! That's useful information (and disturbing...)

yeah ... dan albert (who owns the Android NDK) points out that with a
large enough ecosystem, any mistake you can imagine -- and many you
can't -- aren't just possible, they're probable :-)

> > > There's already
> > > enough complexity in the code paths for supporting all the different
> > > mutex types that my leaning would be, if we do any hardening for
> > > use-after-destroy, that it should probably just take the form of
> > > putting the object in a state that will naturally deadlock or error
> > > rather than adding extra checks to every path where it's used.
> >
> > yeah, the _other_ reason we have the abort is that we've struggled
> > over the years to make it clear to the _callers_ that -- just because
> > you crash/hang in libc -- it's the _caller's_ bug. explicitly saying
> > so helps. (though we still get a decent number of people who don't
> > read/don't understand.)
>
> That's a problem we've just not tried to address in musl, but indeed
> it does happen fairly often. If we did try at some point, I think it
> would be by setting up a state to make the reason more clear in the
> debugger, not producing any output. But personally I'd like to keep
> driving home the message that the point of crash does not mean
> anything about responsibility for the crash, even if it means
> responding to lots of bogus "bug reports"...

from the other thread on the musl list right now where someone doesn't
realize they need to type `run` in the debugger, i'll let you draw
your own conclusion about how successful i think that's likely to be
:-) the trouble with the "someone's wrong on the internet, i must
correct them" approach is that it doesn't scale...

but, yes, we've had some value from a related idea of having the
software that generates a crash dump do the "first level triage" of a
crash and explicitly say things like "null pointer dereference" or
"this code aborted --- see if it logged anything first" and so on.

> Rich

Re: [musl] Protect pthreads' mutexes against use-after-destroy

[Rich Felker]

[-- Attachment #1: Type: text/plain, Size: 1749 bytes --]

On Tue, Jan 09, 2024 at 02:07:26PM -0500, Rich Felker wrote:
> On Tue, Jan 09, 2024 at 03:37:17PM +0100, jvoisin wrote:
> > Ohai,
> > 
> > as discussed on irc, Android's bionic has a check to prevent
> > use-after-destroy on phtread mutexes
> > (https://github.com/LineageOS/android_bionic/blob/e0aac7df6f58138dae903b5d456c947a3f8092ea/libc/bionic/pthread_mutex.cpp#L803),
> > and musl doesn't.
> > 
> > While odds are that this is a super-duper common bug, it would still be
> > nice to have this kind of protection, since it's cheap, and would
> > prevent/make it easy to diagnose weird states.
> > 
> > Is this something that should/could be implemented?
> > 
> > o/
> 
> I think you meant that the odds are it's not common. There's already
> enough complexity in the code paths for supporting all the different
> mutex types that my leaning would be, if we do any hardening for
> use-after-destroy, that it should probably just take the form of
> putting the object in a state that will naturally deadlock or error
> rather than adding extra checks to every path where it's used.
> 
> If OTOH we do want it to actually trap in all cases where it's used
> after destroy, the simplest way to achieve that is probably to set it
> up as a non-robust non-PI recursive or errorchecking mutex with
> invalid prev/next pointers and owner of 0x3fffffff. Then the only
> place that would actually have to have an explicit trap is trylock in
> the code path:
> 
>         if (own == 0x3fffffff) return ENOTRECOVERABLE;
> 
> where it could trap if type isn't robust. The unlock code path would
> trap on accessing invalid prev/next pointers.

Draft attached in case anyone wants to play with it. This could
probably be something we could consider to adopt.

[-- Attachment #2: trap_use_after_destroy.diff --]
[-- Type: text/plain, Size: 1829 bytes --]

diff --git a/src/thread/pthread_mutex_destroy.c b/src/thread/pthread_mutex_destroy.c
index 8d1bf77b..c56e9fbd 100644
--- a/src/thread/pthread_mutex_destroy.c
+++ b/src/thread/pthread_mutex_destroy.c
@@ -6,5 +6,13 @@ int pthread_mutex_destroy(pthread_mutex_t *mutex)
 	 * type (tracking ownership), it might be in the pending slot of a
 	 * robust_list; wait for quiescence. */
 	if (mutex->_m_type > 128) __vm_wait();
+
+	/* Setup a non-robust errorchecking mutex in ownerdead state so
+	 * use after destruction can be trapped. */
+	mutex->_m_type = 3;
+	mutex->_m_prev = mutex->_m_next = 0;
+	mutex->_m_lock = 0x7fffffff;
+	mutex->_m_count = 0;
+
 	return 0;
 }
diff --git a/src/thread/pthread_mutex_trylock.c b/src/thread/pthread_mutex_trylock.c
index a24e7c58..8d6102cb 100644
--- a/src/thread/pthread_mutex_trylock.c
+++ b/src/thread/pthread_mutex_trylock.c
@@ -21,7 +21,11 @@ int __pthread_mutex_trylock_owner(pthread_mutex_t *m)
 			return 0;
 		}
 	}
-	if (own == 0x3fffffff) return ENOTRECOVERABLE;
+	if (own == 0x3fffffff) {
+		/* Catch use-after-destroy */
+		if (!(type & 8)) a_crash();
+		return ENOTRECOVERABLE;
+	}
 	if (own || (old && !(type & 4))) return EBUSY;
 
 	if (type & 128) {
diff --git a/src/thread/pthread_mutex_unlock.c b/src/thread/pthread_mutex_unlock.c
index b66423e6..fe159804 100644
--- a/src/thread/pthread_mutex_unlock.c
+++ b/src/thread/pthread_mutex_unlock.c
@@ -14,8 +14,11 @@ int __pthread_mutex_unlock(pthread_mutex_t *m)
 		self = __pthread_self();
 		old = m->_m_lock;
 		int own = old & 0x3fffffff;
-		if (own != self->tid)
+		if (own != self->tid) {
+			/* Catch use-after-destroy */
+			if (own == 0x3fffffff && !(type & 8)) a_crash();
 			return EPERM;
+		}
 		if ((type&3) == PTHREAD_MUTEX_RECURSIVE && m->_m_count)
 			return m->_m_count--, 0;
 		if ((type&4) && (old&0x40000000))

Re: [musl] Protect pthreads' mutexes against use-after-destroy

[julien.voisin]

> Draft attached in case anyone wants to play with it. This could
> probably be something we could consider to adopt.

Couldn't a macro like `#define mutex_is_destroyed (!(m->_m_type & 8) && (m->_m_lock == 0x3fffffff)` be
used instead? Or at least named constants instead of `8` and `0x3fffffff`.

Also, the code-style seems inconsistent:

```
+       if (own == 0x3fffffff) {
+               /* Catch use-after-destroy */
+               if (!(type & 8)) a_crash();                                                                                                                                                      
+               return ENOTRECOVERABLE;
+       }
```

vs 

```
+                       /* Catch use-after-destroy */
+                       if (own == 0x3fffffff && !(type & 8)) a_crash();
                        return EPERM;
```

Both are the same check, yet only one has both conditions in a single `if`.

Re: [musl] Protect pthreads' mutexes against use-after-destroy

[Rich Felker]

On Sun, Jan 21, 2024 at 12:06:14PM +0000, julien.voisin@dustri.org wrote:
> > Draft attached in case anyone wants to play with it. This could
> > probably be something we could consider to adopt.
> 
> Couldn't a macro like `#define mutex_is_destroyed (!(m->_m_type & 8) && (m->_m_lock == 0x3fffffff)` be
> used instead? Or at least named constants instead of `8` and `0x3fffffff`..

Maybe something like that, but that's a change I'd like to make in a
consistent uniform way for all of the uses of magic numbers in the
mutex implementation. Just introducing it in a single place like this
doesn't really help readability; in some ways it makes it less
readable since you can't see how it's interacting with the other
tests.

If doing it, I think it would probably make more sense not to have
that predicate macro, but instead something like:

	if (own == M_UNRECOVERABLE && !(m->_m_type & MT_ROBUST))

because seeing the individual parts is relevant to understanding:

> Also, the code-style seems inconsistent:
> 
> ```
> +       if (own == 0x3fffffff) {
> +               /* Catch use-after-destroy */
> +               if (!(type & 8)) a_crash();                                                                                                                                                      
> +               return ENOTRECOVERABLE;
> +       }
> ```
> 
> vs 
> 
> ```
> +                       /* Catch use-after-destroy */
> +                       if (own == 0x3fffffff && !(type & 8)) a_crash();
>                         return EPERM;
> ```
> 
> Both are the same check, yet only one has both conditions in a single `if`.

These are decision trees on what to do in exceptional cases. The aim
is not to present a consistent "style" between two functions that do
different things and have different decision trees for how to act.

Rich