Re: [PATCH v4 02/27] ntsync: Introduce NTSYNC_IOC_WAIT_ALL.

[Peter Zijlstra]

On Thu, Apr 18, 2024 at 11:35:11AM +0200, Peter Zijlstra wrote:
> On Wed, Apr 17, 2024 at 03:03:05PM -0500, Elizabeth Figura wrote:
> 
> > Ach. I wrote this with the idea that the race isn't meaningful, but
> > looking at it again you're right—there is a harmful race here.
> > 
> > I think it should be fixable by moving the atomic_read inside the lock,
> > though.
> 
> Right, I've ended up with the (as yet untested) below. I'll see if I can
> find time later to actually test things.

Latest hackery... I tried testing this but I'm not having luck using the
patched wine as per the other email.

---
--- a/drivers/misc/ntsync.c
+++ b/drivers/misc/ntsync.c
@@ -18,6 +18,7 @@
 #include <linux/sched/signal.h>
 #include <linux/slab.h>
 #include <linux/spinlock.h>
+#include <linux/mutex.h>
 #include <uapi/linux/ntsync.h>
 
 #define NTSYNC_NAME	"ntsync"
@@ -43,6 +44,7 @@ enum ntsync_type {
 
 struct ntsync_obj {
 	spinlock_t lock;
+	int dev_locked;
 
 	enum ntsync_type type;
 
@@ -132,14 +134,107 @@ struct ntsync_device {
 	 * wait_all_lock is taken first whenever multiple objects must be locked
 	 * at the same time.
 	 */
-	spinlock_t wait_all_lock;
+	struct mutex wait_all_lock;
 
 	struct file *file;
 };
 
+/*
+ * Single objects are locked using obj->lock.
+ *
+ * Multiple objects are 'locked' while holding dev->wait_all_lock to avoid lock
+ * order issues. In this case however, single objects are not locked by holding
+ * obj->lock, but by setting obj->dev_locked.
+ *
+ * This means that in order to lock a single object, the sequence is slightly
+ * more complicated than usual. Specifically it needs to check obj->dev_locked
+ * after acquiring obj->lock, if set, it needs to drop the lock and acquire
+ * dev->wait_all_lock in order to serialize against the multi-object operation.
+ */
+
+static void dev_lock_obj(struct ntsync_device *dev, struct ntsync_obj *obj)
+{
+	lockdep_assert_held(&dev->wait_all_lock);
+	lockdep_assert(obj->dev == dev);
+	spin_lock(&obj->lock);
+	/*
+	 * By setting obj->dev_locked inside obj->lock, it is ensured that
+	 * anyone holding obj->lock must see the value.
+	 */
+	obj->dev_locked = 1;
+	spin_unlock(&obj->lock);
+}
+
+static void dev_unlock_obj(struct ntsync_device *dev, struct ntsync_obj *obj)
+{
+	lockdep_assert_held(&dev->wait_all_lock);
+	lockdep_assert(obj->dev == dev);
+	spin_lock(&obj->lock);
+	obj->dev_locked = 0;
+	spin_unlock(&obj->lock);
+}
+
+static void obj_lock(struct ntsync_obj *obj)
+{
+	struct ntsync_device *dev = obj->dev;
+
+	for (;;) {
+		spin_lock(&obj->lock);
+		if (likely(!obj->dev_locked))
+			break;
+
+		spin_unlock(&obj->lock);
+		mutex_lock(&dev->wait_all_lock);
+		spin_lock(&obj->lock);
+		/*
+		 * obj->dev_locked should be set and released under the same
+		 * wait_all_lock section, since we now own this lock, it should
+		 * be clear.
+		 */
+		lockdep_assert(!obj->dev_locked);
+		spin_unlock(&obj->lock);
+		mutex_unlock(&dev->wait_all_lock);
+	}
+}
+
+static void obj_unlock(struct ntsync_obj *obj)
+{
+	spin_unlock(&obj->lock);
+}
+
+static bool ntsync_lock_obj(struct ntsync_device *dev, struct ntsync_obj *obj)
+{
+	bool all;
+
+	obj_lock(obj);
+	all = atomic_read(&obj->all_hint);
+	if (unlikely(all)) {
+		obj_unlock(obj);
+		mutex_lock(&dev->wait_all_lock);
+		dev_lock_obj(dev, obj);
+	}
+
+	return all;
+}
+
+static void ntsync_unlock_obj(struct ntsync_device *dev, struct ntsync_obj *obj, bool all)
+{
+	if (all) {
+		dev_unlock_obj(dev, obj);
+		mutex_unlock(&dev->wait_all_lock);
+	} else {
+		obj_unlock(obj);
+	}
+}
+
+#define ntsync_assert_held(obj) \
+	lockdep_assert((lockdep_is_held(&(obj)->lock) != LOCK_STATE_NOT_HELD) || \
+		       ((lockdep_is_held(&(obj)->dev->wait_all_lock) != LOCK_STATE_NOT_HELD) && \
+			(obj)->dev_locked))
+
 static bool is_signaled(struct ntsync_obj *obj, __u32 owner)
 {
-	lockdep_assert_held(&obj->lock);
+	ntsync_assert_held(obj);
 
 	switch (obj->type) {
 	case NTSYNC_TYPE_SEM:
@@ -171,11 +266,11 @@ static void try_wake_all(struct ntsync_d
 
 	lockdep_assert_held(&dev->wait_all_lock);
 	if (locked_obj)
-		lockdep_assert_held(&locked_obj->lock);
+		lockdep_assert(locked_obj->dev_locked);
 
 	for (i = 0; i < count; i++) {
 		if (q->entries[i].obj != locked_obj)
-			spin_lock_nest_lock(&q->entries[i].obj->lock, &dev->wait_all_lock);
+			dev_lock_obj(dev, q->entries[i].obj);
 	}
 
 	for (i = 0; i < count; i++) {
@@ -211,7 +306,7 @@ static void try_wake_all(struct ntsync_d
 
 	for (i = 0; i < count; i++) {
 		if (q->entries[i].obj != locked_obj)
-			spin_unlock(&q->entries[i].obj->lock);
+			dev_unlock_obj(dev, q->entries[i].obj);
 	}
 }
 
@@ -220,7 +315,7 @@ static void try_wake_all_obj(struct ntsy
 	struct ntsync_q_entry *entry;
 
 	lockdep_assert_held(&dev->wait_all_lock);
-	lockdep_assert_held(&obj->lock);
+	lockdep_assert(obj->dev_locked);
 
 	list_for_each_entry(entry, &obj->all_waiters, node)
 		try_wake_all(dev, entry->q, obj);
@@ -230,7 +325,8 @@ static void try_wake_any_sem(struct ntsy
 {
 	struct ntsync_q_entry *entry;
 
-	lockdep_assert_held(&sem->lock);
+	ntsync_assert_held(sem);
+	lockdep_assert(sem->type == NTSYNC_TYPE_SEM);
 
 	list_for_each_entry(entry, &sem->any_waiters, node) {
 		struct ntsync_q *q = entry->q;
@@ -250,7 +346,8 @@ static void try_wake_any_mutex(struct nt
 {
 	struct ntsync_q_entry *entry;
 
-	lockdep_assert_held(&mutex->lock);
+	ntsync_assert_held(mutex);
+	lockdep_assert(mutex->type == NTSYNC_TYPE_MUTEX);
 
 	list_for_each_entry(entry, &mutex->any_waiters, node) {
 		struct ntsync_q *q = entry->q;
@@ -276,7 +373,8 @@ static void try_wake_any_event(struct nt
 {
 	struct ntsync_q_entry *entry;
 
-	lockdep_assert_held(&event->lock);
+	ntsync_assert_held(event);
+	lockdep_assert(event->type == NTSYNC_TYPE_EVENT);
 
 	list_for_each_entry(entry, &event->any_waiters, node) {
 		struct ntsync_q *q = entry->q;
@@ -302,6 +400,7 @@ static int post_sem_state(struct ntsync_
 	__u32 sum;
 
 	lockdep_assert_held(&sem->lock);
+	lockdep_assert(sem->type == NTSYNC_TYPE_SEM);
 
 	if (check_add_overflow(sem->u.sem.count, count, &sum) ||
 	    sum > sem->u.sem.max)
@@ -317,6 +416,7 @@ static int ntsync_sem_post(struct ntsync
 	__u32 __user *user_args = argp;
 	__u32 prev_count;
 	__u32 args;
+	bool all;
 	int ret;
 
 	if (copy_from_user(&args, argp, sizeof(args)))
@@ -325,30 +425,18 @@ static int ntsync_sem_post(struct ntsync
 	if (sem->type != NTSYNC_TYPE_SEM)
 		return -EINVAL;
 
-	if (atomic_read(&sem->all_hint) > 0) {
-		spin_lock(&dev->wait_all_lock);
-		spin_lock_nest_lock(&sem->lock, &dev->wait_all_lock);
-
-		prev_count = sem->u.sem.count;
-		ret = post_sem_state(sem, args);
-		if (!ret) {
-			try_wake_all_obj(dev, sem);
-			try_wake_any_sem(sem);
-		}
-
-		spin_unlock(&sem->lock);
-		spin_unlock(&dev->wait_all_lock);
-	} else {
-		spin_lock(&sem->lock);
+	all = ntsync_lock_obj(dev, sem);
 
-		prev_count = sem->u.sem.count;
-		ret = post_sem_state(sem, args);
-		if (!ret)
-			try_wake_any_sem(sem);
-
-		spin_unlock(&sem->lock);
+	prev_count = sem->u.sem.count;
+	ret = post_sem_state(sem, args);
+	if (!ret) {
+		if (all)
+			try_wake_all_obj(dev, sem);
+		try_wake_any_sem(sem);
 	}
 
+	ntsync_unlock_obj(dev, sem, all);
+
 	if (!ret && put_user(prev_count, user_args))
 		ret = -EFAULT;
 
@@ -377,6 +465,7 @@ static int ntsync_mutex_unlock(struct nt
 	struct ntsync_device *dev = mutex->dev;
 	struct ntsync_mutex_args args;
 	__u32 prev_count;
+	bool all;
 	int ret;
 
 	if (copy_from_user(&args, argp, sizeof(args)))
@@ -387,30 +476,18 @@ static int ntsync_mutex_unlock(struct nt
 	if (mutex->type != NTSYNC_TYPE_MUTEX)
 		return -EINVAL;
 
-	if (atomic_read(&mutex->all_hint) > 0) {
-		spin_lock(&dev->wait_all_lock);
-		spin_lock_nest_lock(&mutex->lock, &dev->wait_all_lock);
-
-		prev_count = mutex->u.mutex.count;
-		ret = unlock_mutex_state(mutex, &args);
-		if (!ret) {
-			try_wake_all_obj(dev, mutex);
-			try_wake_any_mutex(mutex);
-		}
+	all = ntsync_lock_obj(dev, mutex);
 
-		spin_unlock(&mutex->lock);
-		spin_unlock(&dev->wait_all_lock);
-	} else {
-		spin_lock(&mutex->lock);
-
-		prev_count = mutex->u.mutex.count;
-		ret = unlock_mutex_state(mutex, &args);
-		if (!ret)
-			try_wake_any_mutex(mutex);
-
-		spin_unlock(&mutex->lock);
+	prev_count = mutex->u.mutex.count;
+	ret = unlock_mutex_state(mutex, &args);
+	if (!ret) {
+		if (all)
+			try_wake_all_obj(dev, mutex);
+		try_wake_any_mutex(mutex);
 	}
 
+	ntsync_unlock_obj(dev, mutex, all);
+
 	if (!ret && put_user(prev_count, &user_args->count))
 		ret = -EFAULT;
 
@@ -438,6 +515,7 @@ static int ntsync_mutex_kill(struct ntsy
 {
 	struct ntsync_device *dev = mutex->dev;
 	__u32 owner;
+	bool all;
 	int ret;
 
 	if (get_user(owner, (__u32 __user *)argp))
@@ -448,28 +526,17 @@ static int ntsync_mutex_kill(struct ntsy
 	if (mutex->type != NTSYNC_TYPE_MUTEX)
 		return -EINVAL;
 
-	if (atomic_read(&mutex->all_hint) > 0) {
-		spin_lock(&dev->wait_all_lock);
-		spin_lock_nest_lock(&mutex->lock, &dev->wait_all_lock);
+	all = ntsync_lock_obj(dev, mutex);
 
-		ret = kill_mutex_state(mutex, owner);
-		if (!ret) {
+	ret = kill_mutex_state(mutex, owner);
+	if (!ret) {
+		if (all)
 			try_wake_all_obj(dev, mutex);
-			try_wake_any_mutex(mutex);
-		}
-
-		spin_unlock(&mutex->lock);
-		spin_unlock(&dev->wait_all_lock);
-	} else {
-		spin_lock(&mutex->lock);
-
-		ret = kill_mutex_state(mutex, owner);
-		if (!ret)
-			try_wake_any_mutex(mutex);
-
-		spin_unlock(&mutex->lock);
+		try_wake_any_mutex(mutex);
 	}
 
+	ntsync_unlock_obj(dev, mutex, all);
+
 	return ret;
 }
 
@@ -477,34 +544,22 @@ static int ntsync_event_set(struct ntsyn
 {
 	struct ntsync_device *dev = event->dev;
 	__u32 prev_state;
+	bool all;
 
 	if (event->type != NTSYNC_TYPE_EVENT)
 		return -EINVAL;
 
-	if (atomic_read(&event->all_hint) > 0) {
-		spin_lock(&dev->wait_all_lock);
-		spin_lock_nest_lock(&event->lock, &dev->wait_all_lock);
+	all = ntsync_lock_obj(dev, event);
 
-		prev_state = event->u.event.signaled;
-		event->u.event.signaled = true;
+	prev_state = event->u.event.signaled;
+	event->u.event.signaled = true;
+	if (all)
 		try_wake_all_obj(dev, event);
-		try_wake_any_event(event);
-		if (pulse)
-			event->u.event.signaled = false;
+	try_wake_any_event(event);
+	if (pulse)
+		event->u.event.signaled = false;
 
-		spin_unlock(&event->lock);
-		spin_unlock(&dev->wait_all_lock);
-	} else {
-		spin_lock(&event->lock);
-
-		prev_state = event->u.event.signaled;
-		event->u.event.signaled = true;
-		try_wake_any_event(event);
-		if (pulse)
-			event->u.event.signaled = false;
-
-		spin_unlock(&event->lock);
-	}
+	ntsync_unlock_obj(dev, event, all);
 
 	if (put_user(prev_state, (__u32 __user *)argp))
 		return -EFAULT;
@@ -984,7 +1039,7 @@ static int ntsync_wait_all(struct ntsync
 
 	/* queue ourselves */
 
-	spin_lock(&dev->wait_all_lock);
+	mutex_lock(&dev->wait_all_lock);
 
 	for (i = 0; i < args.count; i++) {
 		struct ntsync_q_entry *entry = &q->entries[i];
@@ -1004,7 +1059,7 @@ static int ntsync_wait_all(struct ntsync
 
 	try_wake_all(dev, q, NULL);
 
-	spin_unlock(&dev->wait_all_lock);
+	mutex_unlock(&dev->wait_all_lock);
 
 	/* sleep */
 
@@ -1012,7 +1067,7 @@ static int ntsync_wait_all(struct ntsync
 
 	/* and finally, unqueue */
 
-	spin_lock(&dev->wait_all_lock);
+	mutex_lock(&dev->wait_all_lock);
 
 	for (i = 0; i < args.count; i++) {
 		struct ntsync_q_entry *entry = &q->entries[i];
@@ -1029,7 +1084,7 @@ static int ntsync_wait_all(struct ntsync
 		put_obj(obj);
 	}
 
-	spin_unlock(&dev->wait_all_lock);
+	mutex_unlock(&dev->wait_all_lock);
 
 	signaled = atomic_read(&q->signaled);
 	if (signaled != -1) {
@@ -1056,7 +1111,7 @@ static int ntsync_char_open(struct inode
 	if (!dev)
 		return -ENOMEM;
 
-	spin_lock_init(&dev->wait_all_lock);
+	mutex_init(&dev->wait_all_lock);
 
 	file->private_data = dev;
 	dev->file = file;