From: Alexey Izbyshev <izbyshev@ispras.ru>
To: musl@lists.openwall.com
Subject: [musl] Illegal killlock skipping when transitioning to single-threaded state
Date: Wed, 07 Sep 2022 03:46:53 +0300 [thread overview]
Message-ID: <b78eff8d05538224665e71a2fd985c13@ispras.ru> (raw)
Hi,
While reading pthread_exit() implementation I noticed that it can set
"libc.need_locks" to -1 while still holding the killlock of the exiting
thread:
if (!--libc.threads_minus_1) libc.need_locks = -1;
If the remaining thread attempts to acquire the same killlock
concurrently (which is valid for joinable threads), it works fine
because LOCK() resets "libc.need_locks" only after a_cas():
int need_locks = libc.need_locks;
if (!need_locks) return;
/* fast path: INT_MIN for the lock, +1 for the congestion */
int current = a_cas(l, 0, INT_MIN + 1);
if (need_locks < 0) libc.need_locks = 0;
if (!current) return;
However, because "libc.need_locks" is reset when using LOCK() for any
other lock too, the following could happen (E is the exiting thread, R
is the remaining thread):
E: libc.need_locks = -1
R: LOCK(unrelated_lock)
R: libc.need_locks = 0
R: UNLOCK(unrelated_lock)
R: LOCK(E->killlock) // skips locking, now both R and E think they are
holding the lock
R: UNLOCK(E->killlock)
E: UNLOCK(E->killlock)
The lack of mutual exclusion means that the tid reuse problem that
killlock is supposed to prevent might occur.
Moreover, when UNLOCK(E->killlock) is called concurrently by R and E,
a_fetch_add() could be done twice if timing is such that both threads
notice that "l[0] < 0":
/* Check l[0] to see if we are multi-threaded. */
if (l[0] < 0) {
if (a_fetch_add(l, -(INT_MIN + 1)) != (INT_MIN + 1)) {
__wake(l, 1, 1);
}
}
In that case E->killlock will be assigned to INT_MAX (i.e. "unlocked
with INT_MAX waiters"). This is a bad state because the next LOCK() will
wrap it to "unlocked" state instead of locking. Also, if more than two
threads attempt to use it, a deadlock will occur if two
supposedly-owners execute a_fetch_add() concurrently in UNLOCK() after a
third thread registered itself as a waiter because the lock will wrap to
INT_MIN.
Reordering the "libc.need_locks = -1" assignment and UNLOCK(E->killlock)
and providing a store barrier between them should fix the issue.
Thanks,
Alexey
next reply other threads:[~2022-09-07 0:47 UTC|newest]
Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-07 0:46 Alexey Izbyshev [this message]
2022-09-19 15:29 ` Rich Felker
2022-10-03 6:16 ` Alexey Izbyshev
2022-10-03 12:33 ` Rich Felker
2022-10-03 13:26 ` Szabolcs Nagy
2022-10-03 21:27 ` Szabolcs Nagy
2022-10-03 22:54 ` Rich Felker
2022-10-03 23:05 ` Rich Felker
2022-10-04 13:50 ` Alexey Izbyshev
2022-10-04 14:12 ` Rich Felker
2022-10-04 14:19 ` Rich Felker
2022-10-04 15:43 ` Alexey Izbyshev
2022-10-04 15:57 ` Rich Felker
2022-10-04 18:15 ` Alexey Izbyshev
2022-10-04 23:21 ` Rich Felker
2022-10-04 16:24 ` James Y Knight
2022-10-04 16:45 ` Rich Felker
2022-10-05 13:52 ` James Y Knight
2022-10-04 16:01 ` Alexey Izbyshev
2022-10-04 2:58 ` Rich Felker
2022-10-04 3:00 ` Rich Felker
2022-10-04 4:59 ` Rich Felker
2022-10-04 8:16 ` Szabolcs Nagy
2022-10-04 10:18 ` Alexey Izbyshev
2022-10-04 5:16 ` Alexey Izbyshev
2022-10-04 8:31 ` Szabolcs Nagy
2022-10-04 10:28 ` Alexey Izbyshev
2022-10-05 1:00 ` Rich Felker
2022-10-05 12:10 ` Alexey Izbyshev
2022-10-05 14:03 ` Rich Felker
2022-10-05 14:37 ` Rich Felker
2022-10-05 16:23 ` Alexey Izbyshev
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=b78eff8d05538224665e71a2fd985c13@ispras.ru \
--to=izbyshev@ispras.ru \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).