From owner-svn-src-stable-10@FreeBSD.ORG Sat Feb 7 08:35:19 2015 Return-Path: Delivered-To: svn-src-stable-10@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 4CB80664; Sat, 7 Feb 2015 08:35:19 +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 1DAA3A9F; Sat, 7 Feb 2015 08:35:19 +0000 (UTC) Received: from svn.freebsd.org ([127.0.1.70]) by svn.freebsd.org (8.14.9/8.14.9) with ESMTP id t178ZI07057096; Sat, 7 Feb 2015 08:35:18 GMT (envelope-from kib@FreeBSD.org) Received: (from kib@localhost) by svn.freebsd.org (8.14.9/8.14.9/Submit) id t178ZI8p057095; Sat, 7 Feb 2015 08:35:18 GMT (envelope-from kib@FreeBSD.org) Message-Id: <201502070835.t178ZI8p057095@svn.freebsd.org> X-Authentication-Warning: svn.freebsd.org: kib set sender to kib@FreeBSD.org using -f From: Konstantin Belousov Date: Sat, 7 Feb 2015 08:35:18 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-10@freebsd.org Subject: svn commit: r278345 - stable/10/sys/kern X-SVN-Group: stable-10 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-stable-10@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: SVN commit messages for only the 10-stable src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 07 Feb 2015 08:35:19 -0000 Author: kib Date: Sat Feb 7 08:35:18 2015 New Revision: 278345 URL: https://svnweb.freebsd.org/changeset/base/278345 Log: MFC r277970: Check for the cycle in the chain of dependency for priority-inheritance mutexes. Modified: stable/10/sys/kern/kern_umtx.c Directory Properties: stable/10/ (props changed) Modified: stable/10/sys/kern/kern_umtx.c ============================================================================== --- stable/10/sys/kern/kern_umtx.c Sat Feb 7 08:14:20 2015 (r278344) +++ stable/10/sys/kern/kern_umtx.c Sat Feb 7 08:35:18 2015 (r278345) @@ -1667,6 +1667,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. @@ -1684,6 +1725,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; @@ -1727,6 +1770,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; @@ -2059,8 +2104,7 @@ do_lock_pi(struct thread *td, struct umu continue; } - if ((flags & UMUTEX_ERROR_CHECK) != 0 && - (owner & ~UMUTEX_CONTESTED) == id) { + if ((owner & ~UMUTEX_CONTESTED) == id) { error = EDEADLK; break; }