svn commit: r277970 - head/sys/kern

[Konstantin Belousov]

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 at vangyzen.net>
  In collaboration with:	Eric van Gyzen <eric at 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;