From owner-svn-src-all@FreeBSD.ORG Sat Jan 31 12:27:41 2015 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 4E312494; Sat, 31 Jan 2015 12:27:41 +0000 (UTC) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:1900:2254:2068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 205726A5; Sat, 31 Jan 2015 12:27:41 +0000 (UTC) Received: from svn.freebsd.org ([127.0.1.70]) by svn.freebsd.org (8.14.9/8.14.9) with ESMTP id t0VCRfYT032948; Sat, 31 Jan 2015 12:27:41 GMT (envelope-from kib@FreeBSD.org) Received: (from kib@localhost) by svn.freebsd.org (8.14.9/8.14.9/Submit) id t0VCReEb032947; Sat, 31 Jan 2015 12:27:40 GMT (envelope-from kib@FreeBSD.org) Message-Id: <201501311227.t0VCReEb032947@svn.freebsd.org> X-Authentication-Warning: svn.freebsd.org: kib set sender to kib@FreeBSD.org using -f From: Konstantin Belousov Date: Sat, 31 Jan 2015 12:27:40 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: svn commit: r277970 - head/sys/kern X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 31 Jan 2015 12:27:41 -0000 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 In collaboration with: Eric van Gyzen 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;