svn commit: r278345 - stable/10/sys/kern

[Konstantin Belousov]

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;
 		}