Date: Sat, 31 Jan 2015 12:27:40 +0000 (UTC) From: Konstantin Belousov <kib@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r277970 - head/sys/kern Message-ID: <201501311227.t0VCReEb032947@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: kib Date: Sat Jan 31 12:27:40 2015 New Revision: 277970 URL: https://svnweb.freebsd.org/changeset/base/277970 Log: The dependency chain for priority-inheritance mutexes could be subverted by userspace into cycle. Both umtx_propagate_priority() and umtx_repropagate_priority() would then loop infinitely, owning the spinlock. Check for the cycle using standard Floyd' algorithm before doing the pass in the affected functions. Add simple check for condition of tricking the thread into a wait for itself, which could be easily simulated by usermode without race. Found by: Eric van Gyzen <eric@vangyzen.net> In collaboration with: Eric van Gyzen <eric@vangyzen.net> Tested by: pho MFC after: 1 week Modified: head/sys/kern/kern_umtx.c Modified: head/sys/kern/kern_umtx.c ============================================================================== --- head/sys/kern/kern_umtx.c Sat Jan 31 12:27:18 2015 (r277969) +++ head/sys/kern/kern_umtx.c Sat Jan 31 12:27:40 2015 (r277970) @@ -1302,6 +1302,47 @@ umtx_pi_adjust_thread(struct umtx_pi *pi return (1); } +static struct umtx_pi * +umtx_pi_next(struct umtx_pi *pi) +{ + struct umtx_q *uq_owner; + + if (pi->pi_owner == NULL) + return (NULL); + uq_owner = pi->pi_owner->td_umtxq; + if (uq_owner == NULL) + return (NULL); + return (uq_owner->uq_pi_blocked); +} + +/* + * Floyd's Cycle-Finding Algorithm. + */ +static bool +umtx_pi_check_loop(struct umtx_pi *pi) +{ + struct umtx_pi *pi1; /* fast iterator */ + + mtx_assert(&umtx_lock, MA_OWNED); + if (pi == NULL) + return (false); + pi1 = pi; + for (;;) { + pi = umtx_pi_next(pi); + if (pi == NULL) + break; + pi1 = umtx_pi_next(pi1); + if (pi1 == NULL) + break; + pi1 = umtx_pi_next(pi1); + if (pi1 == NULL) + break; + if (pi == pi1) + return (true); + } + return (false); +} + /* * Propagate priority when a thread is blocked on POSIX * PI mutex. @@ -1319,6 +1360,8 @@ umtx_propagate_priority(struct thread *t pi = uq->uq_pi_blocked; if (pi == NULL) return; + if (umtx_pi_check_loop(pi)) + return; for (;;) { td = pi->pi_owner; @@ -1362,6 +1405,8 @@ umtx_repropagate_priority(struct umtx_pi mtx_assert(&umtx_lock, MA_OWNED); + if (umtx_pi_check_loop(pi)) + return; while (pi != NULL && pi->pi_owner != NULL) { pri = PRI_MAX; uq_owner = pi->pi_owner->td_umtxq; @@ -1694,6 +1739,11 @@ do_lock_pi(struct thread *td, struct umu continue; } + if ((owner & ~UMUTEX_CONTESTED) == id) { + error = EDEADLK; + break; + } + if (try != 0) { error = EBUSY; break;
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201501311227.t0VCReEb032947>