1209 lines · 26.5 KB · C
RawDownload
// SPDX-License-Identifier: GPL-2.0-only/* * ntsync.c - Kernel driver for NT synchronization primitives * * Copyright (C) 2024 Elizabeth Figura <zfigura@codeweavers.com> */ #include <linux/anon_inodes.h>#include <linux/atomic.h>#include <linux/file.h>#include <linux/fs.h>#include <linux/hrtimer.h>#include <linux/ktime.h>#include <linux/miscdevice.h>#include <linux/module.h>#include <linux/mutex.h>#include <linux/overflow.h>#include <linux/sched.h>#include <linux/sched/signal.h>#include <linux/slab.h>#include <linux/spinlock.h>#include <uapi/linux/ntsync.h> #define NTSYNC_NAME	"ntsync" enum ntsync_type {	NTSYNC_TYPE_SEM,	NTSYNC_TYPE_MUTEX,	NTSYNC_TYPE_EVENT,}; /* * Individual synchronization primitives are represented by * struct ntsync_obj, and each primitive is backed by a file. * * The whole namespace is represented by a struct ntsync_device also * backed by a file. * * Both rely on struct file for reference counting. Individual * ntsync_obj objects take a reference to the device when created. * Wait operations take a reference to each object being waited on for * the duration of the wait. */ struct ntsync_obj {	spinlock_t lock;	int dev_locked; 	enum ntsync_type type; 	struct file *file;	struct ntsync_device *dev; 	/* The following fields are protected by the object lock. */	union {		struct {			__u32 count;			__u32 max;		} sem;		struct {			__u32 count;			pid_t owner;			bool ownerdead;		} mutex;		struct {			bool manual;			bool signaled;		} event;	} u; 	/*	 * any_waiters is protected by the object lock, but all_waiters is	 * protected by the device wait_all_lock.	 */	struct list_head any_waiters;	struct list_head all_waiters; 	/*	 * Hint describing how many tasks are queued on this object in a	 * wait-all operation.	 *	 * Any time we do a wake, we may need to wake "all" waiters as well as	 * "any" waiters. In order to atomically wake "all" waiters, we must	 * lock all of the objects, and that means grabbing the wait_all_lock	 * below (and, due to lock ordering rules, before locking this object).	 * However, wait-all is a rare operation, and grabbing the wait-all	 * lock for every wake would create unnecessary contention.	 * Therefore we first check whether all_hint is zero, and, if it is,	 * we skip trying to wake "all" waiters.	 *	 * Since wait requests must originate from user-space threads, we're	 * limited here by PID_MAX_LIMIT, so there's no risk of overflow.	 */	atomic_t all_hint;}; struct ntsync_q_entry {	struct list_head node;	struct ntsync_q *q;	struct ntsync_obj *obj;	__u32 index;}; struct ntsync_q {	struct task_struct *task;	__u32 owner; 	/*	 * Protected via atomic_try_cmpxchg(). Only the thread that wins the	 * compare-and-swap may actually change object states and wake this	 * task.	 */	atomic_t signaled; 	bool all;	bool ownerdead;	__u32 count;	struct ntsync_q_entry entries[];}; struct ntsync_device {	/*	 * Wait-all operations must atomically grab all objects, and be totally	 * ordered with respect to each other and wait-any operations.	 * If one thread is trying to acquire several objects, another thread	 * cannot touch the object at the same time.	 *	 * This device-wide lock is used to serialize wait-for-all	 * operations, and operations on an object that is involved in a	 * wait-for-all.	 */	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. * In this case however, individual 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){	ntsync_assert_held(obj); 	switch (obj->type) {	case NTSYNC_TYPE_SEM:		return !!obj->u.sem.count;	case NTSYNC_TYPE_MUTEX:		if (obj->u.mutex.owner && obj->u.mutex.owner != owner)			return false;		return obj->u.mutex.count < UINT_MAX;	case NTSYNC_TYPE_EVENT:		return obj->u.event.signaled;	} 	WARN(1, "bad object type %#x\n", obj->type);	return false;} /* * "locked_obj" is an optional pointer to an object which is already locked and * should not be locked again. This is necessary so that changing an object's * state and waking it can be a single atomic operation. */static void try_wake_all(struct ntsync_device *dev, struct ntsync_q *q,			 struct ntsync_obj *locked_obj){	__u32 count = q->count;	bool can_wake = true;	int signaled = -1;	__u32 i; 	lockdep_assert_held(&dev->wait_all_lock);	if (locked_obj)		lockdep_assert(locked_obj->dev_locked); 	for (i = 0; i < count; i++) {		if (q->entries[i].obj != locked_obj)			dev_lock_obj(dev, q->entries[i].obj);	} 	for (i = 0; i < count; i++) {		if (!is_signaled(q->entries[i].obj, q->owner)) {			can_wake = false;			break;		}	} 	if (can_wake && atomic_try_cmpxchg(&q->signaled, &signaled, 0)) {		for (i = 0; i < count; i++) {			struct ntsync_obj *obj = q->entries[i].obj; 			switch (obj->type) {			case NTSYNC_TYPE_SEM:				obj->u.sem.count--;				break;			case NTSYNC_TYPE_MUTEX:				if (obj->u.mutex.ownerdead)					q->ownerdead = true;				obj->u.mutex.ownerdead = false;				obj->u.mutex.count++;				obj->u.mutex.owner = q->owner;				break;			case NTSYNC_TYPE_EVENT:				if (!obj->u.event.manual)					obj->u.event.signaled = false;				break;			}		}		wake_up_process(q->task);	} 	for (i = 0; i < count; i++) {		if (q->entries[i].obj != locked_obj)			dev_unlock_obj(dev, q->entries[i].obj);	}} static void try_wake_all_obj(struct ntsync_device *dev, struct ntsync_obj *obj){	struct ntsync_q_entry *entry; 	lockdep_assert_held(&dev->wait_all_lock);	lockdep_assert(obj->dev_locked); 	list_for_each_entry(entry, &obj->all_waiters, node)		try_wake_all(dev, entry->q, obj);} static void try_wake_any_sem(struct ntsync_obj *sem){	struct ntsync_q_entry *entry; 	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;		int signaled = -1; 		if (!sem->u.sem.count)			break; 		if (atomic_try_cmpxchg(&q->signaled, &signaled, entry->index)) {			sem->u.sem.count--;			wake_up_process(q->task);		}	}} static void try_wake_any_mutex(struct ntsync_obj *mutex){	struct ntsync_q_entry *entry; 	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;		int signaled = -1; 		if (mutex->u.mutex.count == UINT_MAX)			break;		if (mutex->u.mutex.owner && mutex->u.mutex.owner != q->owner)			continue; 		if (atomic_try_cmpxchg(&q->signaled, &signaled, entry->index)) {			if (mutex->u.mutex.ownerdead)				q->ownerdead = true;			mutex->u.mutex.ownerdead = false;			mutex->u.mutex.count++;			mutex->u.mutex.owner = q->owner;			wake_up_process(q->task);		}	}} static void try_wake_any_event(struct ntsync_obj *event){	struct ntsync_q_entry *entry; 	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;		int signaled = -1; 		if (!event->u.event.signaled)			break; 		if (atomic_try_cmpxchg(&q->signaled, &signaled, entry->index)) {			if (!event->u.event.manual)				event->u.event.signaled = false;			wake_up_process(q->task);		}	}} /* * Actually change the semaphore state, returning -EOVERFLOW if it is made * invalid. */static int release_sem_state(struct ntsync_obj *sem, __u32 count){	__u32 sum; 	ntsync_assert_held(sem); 	if (check_add_overflow(sem->u.sem.count, count, &sum) ||	    sum > sem->u.sem.max)		return -EOVERFLOW; 	sem->u.sem.count = sum;	return 0;} static int ntsync_sem_release(struct ntsync_obj *sem, void __user *argp){	struct ntsync_device *dev = sem->dev;	__u32 __user *user_args = argp;	__u32 prev_count;	__u32 args;	bool all;	int ret; 	if (copy_from_user(&args, argp, sizeof(args)))		return -EFAULT; 	if (sem->type != NTSYNC_TYPE_SEM)		return -EINVAL; 	all = ntsync_lock_obj(dev, sem); 	prev_count = sem->u.sem.count;	ret = release_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; 	return ret;} /* * Actually change the mutex state, returning -EPERM if not the owner. */static int unlock_mutex_state(struct ntsync_obj *mutex,			      const struct ntsync_mutex_args *args){	ntsync_assert_held(mutex); 	if (mutex->u.mutex.owner != args->owner)		return -EPERM; 	if (!--mutex->u.mutex.count)		mutex->u.mutex.owner = 0;	return 0;} static int ntsync_mutex_unlock(struct ntsync_obj *mutex, void __user *argp){	struct ntsync_mutex_args __user *user_args = argp;	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)))		return -EFAULT;	if (!args.owner)		return -EINVAL; 	if (mutex->type != NTSYNC_TYPE_MUTEX)		return -EINVAL; 	all = ntsync_lock_obj(dev, mutex); 	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; 	return ret;} /* * Actually change the mutex state to mark its owner as dead, * returning -EPERM if not the owner. */static int kill_mutex_state(struct ntsync_obj *mutex, __u32 owner){	ntsync_assert_held(mutex); 	if (mutex->u.mutex.owner != owner)		return -EPERM;

Lines 1–500 of 1209.