ntsync.c

   1// SPDX-License-Identifier: GPL-2.0-only
   2/*
   3 * ntsync.c - Kernel driver for NT synchronization primitives
   4 *
   5 * Copyright (C) 2024 Elizabeth Figura <zfigura@codeweavers.com>
   6 */
   7
   8#include <linux/anon_inodes.h>
   9#include <linux/atomic.h>
  10#include <linux/file.h>
  11#include <linux/fs.h>
  12#include <linux/hrtimer.h>
  13#include <linux/ktime.h>
  14#include <linux/miscdevice.h>
  15#include <linux/module.h>
  16#include <linux/mutex.h>
  17#include <linux/overflow.h>
  18#include <linux/sched.h>
  19#include <linux/sched/signal.h>
  20#include <linux/slab.h>
  21#include <linux/spinlock.h>
  22#include <uapi/linux/ntsync.h>
  23
  24#define NTSYNC_NAME	"ntsync"
  25
  26enum ntsync_type {
  27	NTSYNC_TYPE_SEM,
  28	NTSYNC_TYPE_MUTEX,
  29	NTSYNC_TYPE_EVENT,
  30};
  31
  32/*
  33 * Individual synchronization primitives are represented by
  34 * struct ntsync_obj, and each primitive is backed by a file.
  35 *
  36 * The whole namespace is represented by a struct ntsync_device also
  37 * backed by a file.
  38 *
  39 * Both rely on struct file for reference counting. Individual
  40 * ntsync_obj objects take a reference to the device when created.
  41 * Wait operations take a reference to each object being waited on for
  42 * the duration of the wait.
  43 */
  44
  45struct ntsync_obj {
  46	spinlock_t lock;
  47	int dev_locked;
  48
  49	enum ntsync_type type;
  50
  51	struct file *file;
  52	struct ntsync_device *dev;
  53
  54	/* The following fields are protected by the object lock. */
  55	union {
  56		struct {
  57			__u32 count;
  58			__u32 max;
  59		} sem;
  60		struct {
  61			__u32 count;
  62			pid_t owner;
  63			bool ownerdead;
  64		} mutex;
  65		struct {
  66			bool manual;
  67			bool signaled;
  68		} event;
  69	} u;
  70
  71	/*
  72	 * any_waiters is protected by the object lock, but all_waiters is
  73	 * protected by the device wait_all_lock.
  74	 */
  75	struct list_head any_waiters;
  76	struct list_head all_waiters;
  77
  78	/*
  79	 * Hint describing how many tasks are queued on this object in a
  80	 * wait-all operation.
  81	 *
  82	 * Any time we do a wake, we may need to wake "all" waiters as well as
  83	 * "any" waiters. In order to atomically wake "all" waiters, we must
  84	 * lock all of the objects, and that means grabbing the wait_all_lock
  85	 * below (and, due to lock ordering rules, before locking this object).
  86	 * However, wait-all is a rare operation, and grabbing the wait-all
  87	 * lock for every wake would create unnecessary contention.
  88	 * Therefore we first check whether all_hint is zero, and, if it is,
  89	 * we skip trying to wake "all" waiters.
  90	 *
  91	 * Since wait requests must originate from user-space threads, we're
  92	 * limited here by PID_MAX_LIMIT, so there's no risk of overflow.
  93	 */
  94	atomic_t all_hint;
  95};
  96
  97struct ntsync_q_entry {
  98	struct list_head node;
  99	struct ntsync_q *q;
 100	struct ntsync_obj *obj;
 101	__u32 index;
 102};
 103
 104struct ntsync_q {
 105	struct task_struct *task;
 106	__u32 owner;
 107
 108	/*
 109	 * Protected via atomic_try_cmpxchg(). Only the thread that wins the
 110	 * compare-and-swap may actually change object states and wake this
 111	 * task.
 112	 */
 113	atomic_t signaled;
 114
 115	bool all;
 116	bool ownerdead;
 117	__u32 count;
 118	struct ntsync_q_entry entries[];
 119};
 120
 121struct ntsync_device {
 122	/*
 123	 * Wait-all operations must atomically grab all objects, and be totally
 124	 * ordered with respect to each other and wait-any operations.
 125	 * If one thread is trying to acquire several objects, another thread
 126	 * cannot touch the object at the same time.
 127	 *
 128	 * This device-wide lock is used to serialize wait-for-all
 129	 * operations, and operations on an object that is involved in a
 130	 * wait-for-all.
 131	 */
 132	struct mutex wait_all_lock;
 133
 134	struct file *file;
 135};
 136
 137/*
 138 * Single objects are locked using obj->lock.
 139 *
 140 * Multiple objects are 'locked' while holding dev->wait_all_lock.
 141 * In this case however, individual objects are not locked by holding
 142 * obj->lock, but by setting obj->dev_locked.
 143 *
 144 * This means that in order to lock a single object, the sequence is slightly
 145 * more complicated than usual. Specifically it needs to check obj->dev_locked
 146 * after acquiring obj->lock, if set, it needs to drop the lock and acquire
 147 * dev->wait_all_lock in order to serialize against the multi-object operation.
 148 */
 149
 150static void dev_lock_obj(struct ntsync_device *dev, struct ntsync_obj *obj)
 151{
 152	lockdep_assert_held(&dev->wait_all_lock);
 153	lockdep_assert(obj->dev == dev);
 154	spin_lock(&obj->lock);
 155	/*
 156	 * By setting obj->dev_locked inside obj->lock, it is ensured that
 157	 * anyone holding obj->lock must see the value.
 158	 */
 159	obj->dev_locked = 1;
 160	spin_unlock(&obj->lock);
 161}
 162
 163static void dev_unlock_obj(struct ntsync_device *dev, struct ntsync_obj *obj)
 164{
 165	lockdep_assert_held(&dev->wait_all_lock);
 166	lockdep_assert(obj->dev == dev);
 167	spin_lock(&obj->lock);
 168	obj->dev_locked = 0;
 169	spin_unlock(&obj->lock);
 170}
 171
 172static void obj_lock(struct ntsync_obj *obj)
 173{
 174	struct ntsync_device *dev = obj->dev;
 175
 176	for (;;) {
 177		spin_lock(&obj->lock);
 178		if (likely(!obj->dev_locked))
 179			break;
 180
 181		spin_unlock(&obj->lock);
 182		mutex_lock(&dev->wait_all_lock);
 183		spin_lock(&obj->lock);
 184		/*
 185		 * obj->dev_locked should be set and released under the same
 186		 * wait_all_lock section, since we now own this lock, it should
 187		 * be clear.
 188		 */
 189		lockdep_assert(!obj->dev_locked);
 190		spin_unlock(&obj->lock);
 191		mutex_unlock(&dev->wait_all_lock);
 192	}
 193}
 194
 195static void obj_unlock(struct ntsync_obj *obj)
 196{
 197	spin_unlock(&obj->lock);
 198}
 199
 200static bool ntsync_lock_obj(struct ntsync_device *dev, struct ntsync_obj *obj)
 201{
 202	bool all;
 203
 204	obj_lock(obj);
 205	all = atomic_read(&obj->all_hint);
 206	if (unlikely(all)) {
 207		obj_unlock(obj);
 208		mutex_lock(&dev->wait_all_lock);
 209		dev_lock_obj(dev, obj);
 210	}
 211
 212	return all;
 213}
 214
 215static void ntsync_unlock_obj(struct ntsync_device *dev, struct ntsync_obj *obj, bool all)
 216{
 217	if (all) {
 218		dev_unlock_obj(dev, obj);
 219		mutex_unlock(&dev->wait_all_lock);
 220	} else {
 221		obj_unlock(obj);
 222	}
 223}
 224
 225#define ntsync_assert_held(obj) \
 226	lockdep_assert((lockdep_is_held(&(obj)->lock) != LOCK_STATE_NOT_HELD) || \
 227		       ((lockdep_is_held(&(obj)->dev->wait_all_lock) != LOCK_STATE_NOT_HELD) && \
 228			(obj)->dev_locked))
 229
 230static bool is_signaled(struct ntsync_obj *obj, __u32 owner)
 231{
 232	ntsync_assert_held(obj);
 233
 234	switch (obj->type) {
 235	case NTSYNC_TYPE_SEM:
 236		return !!obj->u.sem.count;
 237	case NTSYNC_TYPE_MUTEX:
 238		if (obj->u.mutex.owner && obj->u.mutex.owner != owner)
 239			return false;
 240		return obj->u.mutex.count < UINT_MAX;
 241	case NTSYNC_TYPE_EVENT:
 242		return obj->u.event.signaled;
 243	}
 244
 245	WARN(1, "bad object type %#x\n", obj->type);
 246	return false;
 247}
 248
 249/*
 250 * "locked_obj" is an optional pointer to an object which is already locked and
 251 * should not be locked again. This is necessary so that changing an object's
 252 * state and waking it can be a single atomic operation.
 253 */
 254static void try_wake_all(struct ntsync_device *dev, struct ntsync_q *q,
 255			 struct ntsync_obj *locked_obj)
 256{
 257	__u32 count = q->count;
 258	bool can_wake = true;
 259	int signaled = -1;
 260	__u32 i;
 261
 262	lockdep_assert_held(&dev->wait_all_lock);
 263	if (locked_obj)
 264		lockdep_assert(locked_obj->dev_locked);
 265
 266	for (i = 0; i < count; i++) {
 267		if (q->entries[i].obj != locked_obj)
 268			dev_lock_obj(dev, q->entries[i].obj);
 269	}
 270
 271	for (i = 0; i < count; i++) {
 272		if (!is_signaled(q->entries[i].obj, q->owner)) {
 273			can_wake = false;
 274			break;
 275		}
 276	}
 277
 278	if (can_wake && atomic_try_cmpxchg(&q->signaled, &signaled, 0)) {
 279		for (i = 0; i < count; i++) {
 280			struct ntsync_obj *obj = q->entries[i].obj;
 281
 282			switch (obj->type) {
 283			case NTSYNC_TYPE_SEM:
 284				obj->u.sem.count--;
 285				break;
 286			case NTSYNC_TYPE_MUTEX:
 287				if (obj->u.mutex.ownerdead)
 288					q->ownerdead = true;
 289				obj->u.mutex.ownerdead = false;
 290				obj->u.mutex.count++;
 291				obj->u.mutex.owner = q->owner;
 292				break;
 293			case NTSYNC_TYPE_EVENT:
 294				if (!obj->u.event.manual)
 295					obj->u.event.signaled = false;
 296				break;
 297			}
 298		}
 299		wake_up_process(q->task);
 300	}
 301
 302	for (i = 0; i < count; i++) {
 303		if (q->entries[i].obj != locked_obj)
 304			dev_unlock_obj(dev, q->entries[i].obj);
 305	}
 306}
 307
 308static void try_wake_all_obj(struct ntsync_device *dev, struct ntsync_obj *obj)
 309{
 310	struct ntsync_q_entry *entry;
 311
 312	lockdep_assert_held(&dev->wait_all_lock);
 313	lockdep_assert(obj->dev_locked);
 314
 315	list_for_each_entry(entry, &obj->all_waiters, node)
 316		try_wake_all(dev, entry->q, obj);
 317}
 318
 319static void try_wake_any_sem(struct ntsync_obj *sem)
 320{
 321	struct ntsync_q_entry *entry;
 322
 323	ntsync_assert_held(sem);
 324	lockdep_assert(sem->type == NTSYNC_TYPE_SEM);
 325
 326	list_for_each_entry(entry, &sem->any_waiters, node) {
 327		struct ntsync_q *q = entry->q;
 328		int signaled = -1;
 329
 330		if (!sem->u.sem.count)
 331			break;
 332
 333		if (atomic_try_cmpxchg(&q->signaled, &signaled, entry->index)) {
 334			sem->u.sem.count--;
 335			wake_up_process(q->task);
 336		}
 337	}
 338}
 339
 340static void try_wake_any_mutex(struct ntsync_obj *mutex)
 341{
 342	struct ntsync_q_entry *entry;
 343
 344	ntsync_assert_held(mutex);
 345	lockdep_assert(mutex->type == NTSYNC_TYPE_MUTEX);
 346
 347	list_for_each_entry(entry, &mutex->any_waiters, node) {
 348		struct ntsync_q *q = entry->q;
 349		int signaled = -1;
 350
 351		if (mutex->u.mutex.count == UINT_MAX)
 352			break;
 353		if (mutex->u.mutex.owner && mutex->u.mutex.owner != q->owner)
 354			continue;
 355
 356		if (atomic_try_cmpxchg(&q->signaled, &signaled, entry->index)) {
 357			if (mutex->u.mutex.ownerdead)
 358				q->ownerdead = true;
 359			mutex->u.mutex.ownerdead = false;
 360			mutex->u.mutex.count++;
 361			mutex->u.mutex.owner = q->owner;
 362			wake_up_process(q->task);
 363		}
 364	}
 365}
 366
 367static void try_wake_any_event(struct ntsync_obj *event)
 368{
 369	struct ntsync_q_entry *entry;
 370
 371	ntsync_assert_held(event);
 372	lockdep_assert(event->type == NTSYNC_TYPE_EVENT);
 373
 374	list_for_each_entry(entry, &event->any_waiters, node) {
 375		struct ntsync_q *q = entry->q;
 376		int signaled = -1;
 377
 378		if (!event->u.event.signaled)
 379			break;
 380
 381		if (atomic_try_cmpxchg(&q->signaled, &signaled, entry->index)) {
 382			if (!event->u.event.manual)
 383				event->u.event.signaled = false;
 384			wake_up_process(q->task);
 385		}
 386	}
 387}
 388
 389/*
 390 * Actually change the semaphore state, returning -EOVERFLOW if it is made
 391 * invalid.
 392 */
 393static int release_sem_state(struct ntsync_obj *sem, __u32 count)
 394{
 395	__u32 sum;
 396
 397	ntsync_assert_held(sem);
 398
 399	if (check_add_overflow(sem->u.sem.count, count, &sum) ||
 400	    sum > sem->u.sem.max)
 401		return -EOVERFLOW;
 402
 403	sem->u.sem.count = sum;
 404	return 0;
 405}
 406
 407static int ntsync_sem_release(struct ntsync_obj *sem, void __user *argp)
 408{
 409	struct ntsync_device *dev = sem->dev;
 410	__u32 __user *user_args = argp;
 411	__u32 prev_count;
 412	__u32 args;
 413	bool all;
 414	int ret;
 415
 416	if (copy_from_user(&args, argp, sizeof(args)))
 417		return -EFAULT;
 418
 419	if (sem->type != NTSYNC_TYPE_SEM)
 420		return -EINVAL;
 421
 422	all = ntsync_lock_obj(dev, sem);
 423
 424	prev_count = sem->u.sem.count;
 425	ret = release_sem_state(sem, args);
 426	if (!ret) {
 427		if (all)
 428			try_wake_all_obj(dev, sem);
 429		try_wake_any_sem(sem);
 430	}
 431
 432	ntsync_unlock_obj(dev, sem, all);
 433
 434	if (!ret && put_user(prev_count, user_args))
 435		ret = -EFAULT;
 436
 437	return ret;
 438}
 439
 440/*
 441 * Actually change the mutex state, returning -EPERM if not the owner.
 442 */
 443static int unlock_mutex_state(struct ntsync_obj *mutex,
 444			      const struct ntsync_mutex_args *args)
 445{
 446	ntsync_assert_held(mutex);
 447
 448	if (mutex->u.mutex.owner != args->owner)
 449		return -EPERM;
 450
 451	if (!--mutex->u.mutex.count)
 452		mutex->u.mutex.owner = 0;
 453	return 0;
 454}
 455
 456static int ntsync_mutex_unlock(struct ntsync_obj *mutex, void __user *argp)
 457{
 458	struct ntsync_mutex_args __user *user_args = argp;
 459	struct ntsync_device *dev = mutex->dev;
 460	struct ntsync_mutex_args args;
 461	__u32 prev_count;
 462	bool all;
 463	int ret;
 464
 465	if (copy_from_user(&args, argp, sizeof(args)))
 466		return -EFAULT;
 467	if (!args.owner)
 468		return -EINVAL;
 469
 470	if (mutex->type != NTSYNC_TYPE_MUTEX)
 471		return -EINVAL;
 472
 473	all = ntsync_lock_obj(dev, mutex);
 474
 475	prev_count = mutex->u.mutex.count;
 476	ret = unlock_mutex_state(mutex, &args);
 477	if (!ret) {
 478		if (all)
 479			try_wake_all_obj(dev, mutex);
 480		try_wake_any_mutex(mutex);
 481	}
 482
 483	ntsync_unlock_obj(dev, mutex, all);
 484
 485	if (!ret && put_user(prev_count, &user_args->count))
 486		ret = -EFAULT;
 487
 488	return ret;
 489}
 490
 491/*
 492 * Actually change the mutex state to mark its owner as dead,
 493 * returning -EPERM if not the owner.
 494 */
 495static int kill_mutex_state(struct ntsync_obj *mutex, __u32 owner)
 496{
 497	ntsync_assert_held(mutex);
 498
 499	if (mutex->u.mutex.owner != owner)
 500		return -EPERM;
 501
 502	mutex->u.mutex.ownerdead = true;
 503	mutex->u.mutex.owner = 0;
 504	mutex->u.mutex.count = 0;
 505	return 0;
 506}
 507
 508static int ntsync_mutex_kill(struct ntsync_obj *mutex, void __user *argp)
 509{
 510	struct ntsync_device *dev = mutex->dev;
 511	__u32 owner;
 512	bool all;
 513	int ret;
 514
 515	if (get_user(owner, (__u32 __user *)argp))
 516		return -EFAULT;
 517	if (!owner)
 518		return -EINVAL;
 519
 520	if (mutex->type != NTSYNC_TYPE_MUTEX)
 521		return -EINVAL;
 522
 523	all = ntsync_lock_obj(dev, mutex);
 524
 525	ret = kill_mutex_state(mutex, owner);
 526	if (!ret) {
 527		if (all)
 528			try_wake_all_obj(dev, mutex);
 529		try_wake_any_mutex(mutex);
 530	}
 531
 532	ntsync_unlock_obj(dev, mutex, all);
 533
 534	return ret;
 535}
 536
 537static int ntsync_event_set(struct ntsync_obj *event, void __user *argp, bool pulse)
 538{
 539	struct ntsync_device *dev = event->dev;
 540	__u32 prev_state;
 541	bool all;
 542
 543	if (event->type != NTSYNC_TYPE_EVENT)
 544		return -EINVAL;
 545
 546	all = ntsync_lock_obj(dev, event);
 547
 548	prev_state = event->u.event.signaled;
 549	event->u.event.signaled = true;
 550	if (all)
 551		try_wake_all_obj(dev, event);
 552	try_wake_any_event(event);
 553	if (pulse)
 554		event->u.event.signaled = false;
 555
 556	ntsync_unlock_obj(dev, event, all);
 557
 558	if (put_user(prev_state, (__u32 __user *)argp))
 559		return -EFAULT;
 560
 561	return 0;
 562}
 563
 564static int ntsync_event_reset(struct ntsync_obj *event, void __user *argp)
 565{
 566	struct ntsync_device *dev = event->dev;
 567	__u32 prev_state;
 568	bool all;
 569
 570	if (event->type != NTSYNC_TYPE_EVENT)
 571		return -EINVAL;
 572
 573	all = ntsync_lock_obj(dev, event);
 574
 575	prev_state = event->u.event.signaled;
 576	event->u.event.signaled = false;
 577
 578	ntsync_unlock_obj(dev, event, all);
 579
 580	if (put_user(prev_state, (__u32 __user *)argp))
 581		return -EFAULT;
 582
 583	return 0;
 584}
 585
 586static int ntsync_sem_read(struct ntsync_obj *sem, void __user *argp)
 587{
 588	struct ntsync_sem_args __user *user_args = argp;
 589	struct ntsync_device *dev = sem->dev;
 590	struct ntsync_sem_args args;
 591	bool all;
 592
 593	if (sem->type != NTSYNC_TYPE_SEM)
 594		return -EINVAL;
 595
 596	all = ntsync_lock_obj(dev, sem);
 597
 598	args.count = sem->u.sem.count;
 599	args.max = sem->u.sem.max;
 600
 601	ntsync_unlock_obj(dev, sem, all);
 602
 603	if (copy_to_user(user_args, &args, sizeof(args)))
 604		return -EFAULT;
 605	return 0;
 606}
 607
 608static int ntsync_mutex_read(struct ntsync_obj *mutex, void __user *argp)
 609{
 610	struct ntsync_mutex_args __user *user_args = argp;
 611	struct ntsync_device *dev = mutex->dev;
 612	struct ntsync_mutex_args args;
 613	bool all;
 614	int ret;
 615
 616	if (mutex->type != NTSYNC_TYPE_MUTEX)
 617		return -EINVAL;
 618
 619	all = ntsync_lock_obj(dev, mutex);
 620
 621	args.count = mutex->u.mutex.count;
 622	args.owner = mutex->u.mutex.owner;
 623	ret = mutex->u.mutex.ownerdead ? -EOWNERDEAD : 0;
 624
 625	ntsync_unlock_obj(dev, mutex, all);
 626
 627	if (copy_to_user(user_args, &args, sizeof(args)))
 628		return -EFAULT;
 629	return ret;
 630}
 631
 632static int ntsync_event_read(struct ntsync_obj *event, void __user *argp)
 633{
 634	struct ntsync_event_args __user *user_args = argp;
 635	struct ntsync_device *dev = event->dev;
 636	struct ntsync_event_args args;
 637	bool all;
 638
 639	if (event->type != NTSYNC_TYPE_EVENT)
 640		return -EINVAL;
 641
 642	all = ntsync_lock_obj(dev, event);
 643
 644	args.manual = event->u.event.manual;
 645	args.signaled = event->u.event.signaled;
 646
 647	ntsync_unlock_obj(dev, event, all);
 648
 649	if (copy_to_user(user_args, &args, sizeof(args)))
 650		return -EFAULT;
 651	return 0;
 652}
 653
 654static void ntsync_free_obj(struct ntsync_obj *obj)
 655{
 656	fput(obj->dev->file);
 657	kfree(obj);
 658}
 659
 660static int ntsync_obj_release(struct inode *inode, struct file *file)
 661{
 662	ntsync_free_obj(file->private_data);
 663	return 0;
 664}
 665
 666static long ntsync_obj_ioctl(struct file *file, unsigned int cmd,
 667			     unsigned long parm)
 668{
 669	struct ntsync_obj *obj = file->private_data;
 670	void __user *argp = (void __user *)parm;
 671
 672	switch (cmd) {
 673	case NTSYNC_IOC_SEM_RELEASE:
 674		return ntsync_sem_release(obj, argp);
 675	case NTSYNC_IOC_SEM_READ:
 676		return ntsync_sem_read(obj, argp);
 677	case NTSYNC_IOC_MUTEX_UNLOCK:
 678		return ntsync_mutex_unlock(obj, argp);
 679	case NTSYNC_IOC_MUTEX_KILL:
 680		return ntsync_mutex_kill(obj, argp);
 681	case NTSYNC_IOC_MUTEX_READ:
 682		return ntsync_mutex_read(obj, argp);
 683	case NTSYNC_IOC_EVENT_SET:
 684		return ntsync_event_set(obj, argp, false);
 685	case NTSYNC_IOC_EVENT_RESET:
 686		return ntsync_event_reset(obj, argp);
 687	case NTSYNC_IOC_EVENT_PULSE:
 688		return ntsync_event_set(obj, argp, true);
 689	case NTSYNC_IOC_EVENT_READ:
 690		return ntsync_event_read(obj, argp);
 691	default:
 692		return -ENOIOCTLCMD;
 693	}
 694}
 695
 696static const struct file_operations ntsync_obj_fops = {
 697	.owner		= THIS_MODULE,
 698	.release	= ntsync_obj_release,
 699	.unlocked_ioctl	= ntsync_obj_ioctl,
 700	.compat_ioctl	= compat_ptr_ioctl,
 701};
 702
 703static struct ntsync_obj *ntsync_alloc_obj(struct ntsync_device *dev,
 704					   enum ntsync_type type)
 705{
 706	struct ntsync_obj *obj;
 707
 708	obj = kzalloc(sizeof(*obj), GFP_KERNEL);
 709	if (!obj)
 710		return NULL;
 711	obj->type = type;
 712	obj->dev = dev;
 713	get_file(dev->file);
 714	spin_lock_init(&obj->lock);
 715	INIT_LIST_HEAD(&obj->any_waiters);
 716	INIT_LIST_HEAD(&obj->all_waiters);
 717	atomic_set(&obj->all_hint, 0);
 718
 719	return obj;
 720}
 721
 722static int ntsync_obj_get_fd(struct ntsync_obj *obj)
 723{
 724	FD_PREPARE(fdf, O_CLOEXEC,
 725		   anon_inode_getfile("ntsync", &ntsync_obj_fops, obj, O_RDWR));
 726	if (fdf.err)
 727		return fdf.err;
 728	obj->file = fd_prepare_file(fdf);
 729	return fd_publish(fdf);
 730}
 731
 732static int ntsync_create_sem(struct ntsync_device *dev, void __user *argp)
 733{
 734	struct ntsync_sem_args args;
 735	struct ntsync_obj *sem;
 736	int fd;
 737
 738	if (copy_from_user(&args, argp, sizeof(args)))
 739		return -EFAULT;
 740
 741	if (args.count > args.max)
 742		return -EINVAL;
 743
 744	sem = ntsync_alloc_obj(dev, NTSYNC_TYPE_SEM);
 745	if (!sem)
 746		return -ENOMEM;
 747	sem->u.sem.count = args.count;
 748	sem->u.sem.max = args.max;
 749	fd = ntsync_obj_get_fd(sem);
 750	if (fd < 0)
 751		ntsync_free_obj(sem);
 752
 753	return fd;
 754}
 755
 756static int ntsync_create_mutex(struct ntsync_device *dev, void __user *argp)
 757{
 758	struct ntsync_mutex_args args;
 759	struct ntsync_obj *mutex;
 760	int fd;
 761
 762	if (copy_from_user(&args, argp, sizeof(args)))
 763		return -EFAULT;
 764
 765	if (!args.owner != !args.count)
 766		return -EINVAL;
 767
 768	mutex = ntsync_alloc_obj(dev, NTSYNC_TYPE_MUTEX);
 769	if (!mutex)
 770		return -ENOMEM;
 771	mutex->u.mutex.count = args.count;
 772	mutex->u.mutex.owner = args.owner;
 773	fd = ntsync_obj_get_fd(mutex);
 774	if (fd < 0)
 775		ntsync_free_obj(mutex);
 776
 777	return fd;
 778}
 779
 780static int ntsync_create_event(struct ntsync_device *dev, void __user *argp)
 781{
 782	struct ntsync_event_args args;
 783	struct ntsync_obj *event;
 784	int fd;
 785
 786	if (copy_from_user(&args, argp, sizeof(args)))
 787		return -EFAULT;
 788
 789	event = ntsync_alloc_obj(dev, NTSYNC_TYPE_EVENT);
 790	if (!event)
 791		return -ENOMEM;
 792	event->u.event.manual = args.manual;
 793	event->u.event.signaled = args.signaled;
 794	fd = ntsync_obj_get_fd(event);
 795	if (fd < 0)
 796		ntsync_free_obj(event);
 797
 798	return fd;
 799}
 800
 801static struct ntsync_obj *get_obj(struct ntsync_device *dev, int fd)
 802{
 803	struct file *file = fget(fd);
 804	struct ntsync_obj *obj;
 805
 806	if (!file)
 807		return NULL;
 808
 809	if (file->f_op != &ntsync_obj_fops) {
 810		fput(file);
 811		return NULL;
 812	}
 813
 814	obj = file->private_data;
 815	if (obj->dev != dev) {
 816		fput(file);
 817		return NULL;
 818	}
 819
 820	return obj;
 821}
 822
 823static void put_obj(struct ntsync_obj *obj)
 824{
 825	fput(obj->file);
 826}
 827
 828static int ntsync_schedule(const struct ntsync_q *q, const struct ntsync_wait_args *args)
 829{
 830	ktime_t timeout = ns_to_ktime(args->timeout);
 831	clockid_t clock = CLOCK_MONOTONIC;
 832	ktime_t *timeout_ptr;
 833	int ret = 0;
 834
 835	timeout_ptr = (args->timeout == U64_MAX ? NULL : &timeout);
 836
 837	if (args->flags & NTSYNC_WAIT_REALTIME)
 838		clock = CLOCK_REALTIME;
 839
 840	do {
 841		if (signal_pending(current)) {
 842			ret = -ERESTARTSYS;
 843			break;
 844		}
 845
 846		set_current_state(TASK_INTERRUPTIBLE);
 847		if (atomic_read(&q->signaled) != -1) {
 848			ret = 0;
 849			break;
 850		}
 851		ret = schedule_hrtimeout_range_clock(timeout_ptr, 0, HRTIMER_MODE_ABS, clock);
 852	} while (ret < 0);
 853	__set_current_state(TASK_RUNNING);
 854
 855	return ret;
 856}
 857
 858/*
 859 * Allocate and initialize the ntsync_q structure, but do not queue us yet.
 860 */
 861static int setup_wait(struct ntsync_device *dev,
 862		      const struct ntsync_wait_args *args, bool all,
 863		      struct ntsync_q **ret_q)
 864{
 865	int fds[NTSYNC_MAX_WAIT_COUNT + 1];
 866	const __u32 count = args->count;
 867	size_t size = array_size(count, sizeof(fds[0]));
 868	struct ntsync_q *q;
 869	__u32 total_count;
 870	__u32 i, j;
 871
 872	if (args->pad || (args->flags & ~NTSYNC_WAIT_REALTIME))
 873		return -EINVAL;
 874
 875	if (size >= sizeof(fds))
 876		return -EINVAL;
 877
 878	total_count = count;
 879	if (args->alert)
 880		total_count++;
 881
 882	if (copy_from_user(fds, u64_to_user_ptr(args->objs), size))
 883		return -EFAULT;
 884	if (args->alert)
 885		fds[count] = args->alert;
 886
 887	q = kmalloc(struct_size(q, entries, total_count), GFP_KERNEL);
 888	if (!q)
 889		return -ENOMEM;
 890	q->task = current;
 891	q->owner = args->owner;
 892	atomic_set(&q->signaled, -1);
 893	q->all = all;
 894	q->ownerdead = false;
 895	q->count = count;
 896
 897	for (i = 0; i < total_count; i++) {
 898		struct ntsync_q_entry *entry = &q->entries[i];
 899		struct ntsync_obj *obj = get_obj(dev, fds[i]);
 900
 901		if (!obj)
 902			goto err;
 903
 904		if (all) {
 905			/* Check that the objects are all distinct. */
 906			for (j = 0; j < i; j++) {
 907				if (obj == q->entries[j].obj) {
 908					put_obj(obj);
 909					goto err;
 910				}
 911			}
 912		}
 913
 914		entry->obj = obj;
 915		entry->q = q;
 916		entry->index = i;
 917	}
 918
 919	*ret_q = q;
 920	return 0;
 921
 922err:
 923	for (j = 0; j < i; j++)
 924		put_obj(q->entries[j].obj);
 925	kfree(q);
 926	return -EINVAL;
 927}
 928
 929static void try_wake_any_obj(struct ntsync_obj *obj)
 930{
 931	switch (obj->type) {
 932	case NTSYNC_TYPE_SEM:
 933		try_wake_any_sem(obj);
 934		break;
 935	case NTSYNC_TYPE_MUTEX:
 936		try_wake_any_mutex(obj);
 937		break;
 938	case NTSYNC_TYPE_EVENT:
 939		try_wake_any_event(obj);
 940		break;
 941	}
 942}
 943
 944static int ntsync_wait_any(struct ntsync_device *dev, void __user *argp)
 945{
 946	struct ntsync_wait_args args;
 947	__u32 i, total_count;
 948	struct ntsync_q *q;
 949	int signaled;
 950	bool all;
 951	int ret;
 952
 953	if (copy_from_user(&args, argp, sizeof(args)))
 954		return -EFAULT;
 955
 956	ret = setup_wait(dev, &args, false, &q);
 957	if (ret < 0)
 958		return ret;
 959
 960	total_count = args.count;
 961	if (args.alert)
 962		total_count++;
 963
 964	/* queue ourselves */
 965
 966	for (i = 0; i < total_count; i++) {
 967		struct ntsync_q_entry *entry = &q->entries[i];
 968		struct ntsync_obj *obj = entry->obj;
 969
 970		all = ntsync_lock_obj(dev, obj);
 971		list_add_tail(&entry->node, &obj->any_waiters);
 972		ntsync_unlock_obj(dev, obj, all);
 973	}
 974
 975	/*
 976	 * Check if we are already signaled.
 977	 *
 978	 * Note that the API requires that normal objects are checked before
 979	 * the alert event. Hence we queue the alert event last, and check
 980	 * objects in order.
 981	 */
 982
 983	for (i = 0; i < total_count; i++) {
 984		struct ntsync_obj *obj = q->entries[i].obj;
 985
 986		if (atomic_read(&q->signaled) != -1)
 987			break;
 988
 989		all = ntsync_lock_obj(dev, obj);
 990		try_wake_any_obj(obj);
 991		ntsync_unlock_obj(dev, obj, all);
 992	}
 993
 994	/* sleep */
 995
 996	ret = ntsync_schedule(q, &args);
 997
 998	/* and finally, unqueue */
 999
1000	for (i = 0; i < total_count; i++) {
1001		struct ntsync_q_entry *entry = &q->entries[i];
1002		struct ntsync_obj *obj = entry->obj;
1003
1004		all = ntsync_lock_obj(dev, obj);
1005		list_del(&entry->node);
1006		ntsync_unlock_obj(dev, obj, all);
1007
1008		put_obj(obj);
1009	}
1010
1011	signaled = atomic_read(&q->signaled);
1012	if (signaled != -1) {
1013		struct ntsync_wait_args __user *user_args = argp;
1014
1015		/* even if we caught a signal, we need to communicate success */
1016		ret = q->ownerdead ? -EOWNERDEAD : 0;
1017
1018		if (put_user(signaled, &user_args->index))
1019			ret = -EFAULT;
1020	} else if (!ret) {
1021		ret = -ETIMEDOUT;
1022	}
1023
1024	kfree(q);
1025	return ret;
1026}
1027
1028static int ntsync_wait_all(struct ntsync_device *dev, void __user *argp)
1029{
1030	struct ntsync_wait_args args;
1031	struct ntsync_q *q;
1032	int signaled;
1033	__u32 i;
1034	int ret;
1035
1036	if (copy_from_user(&args, argp, sizeof(args)))
1037		return -EFAULT;
1038
1039	ret = setup_wait(dev, &args, true, &q);
1040	if (ret < 0)
1041		return ret;
1042
1043	/* queue ourselves */
1044
1045	mutex_lock(&dev->wait_all_lock);
1046
1047	for (i = 0; i < args.count; i++) {
1048		struct ntsync_q_entry *entry = &q->entries[i];
1049		struct ntsync_obj *obj = entry->obj;
1050
1051		atomic_inc(&obj->all_hint);
1052
1053		/*
1054		 * obj->all_waiters is protected by dev->wait_all_lock rather
1055		 * than obj->lock, so there is no need to acquire obj->lock
1056		 * here.
1057		 */
1058		list_add_tail(&entry->node, &obj->all_waiters);
1059	}
1060	if (args.alert) {
1061		struct ntsync_q_entry *entry = &q->entries[args.count];
1062		struct ntsync_obj *obj = entry->obj;
1063
1064		dev_lock_obj(dev, obj);
1065		list_add_tail(&entry->node, &obj->any_waiters);
1066		dev_unlock_obj(dev, obj);
1067	}
1068
1069	/* check if we are already signaled */
1070
1071	try_wake_all(dev, q, NULL);
1072
1073	mutex_unlock(&dev->wait_all_lock);
1074
1075	/*
1076	 * Check if the alert event is signaled, making sure to do so only
1077	 * after checking if the other objects are signaled.
1078	 */
1079
1080	if (args.alert) {
1081		struct ntsync_obj *obj = q->entries[args.count].obj;
1082
1083		if (atomic_read(&q->signaled) == -1) {
1084			bool all = ntsync_lock_obj(dev, obj);
1085			try_wake_any_obj(obj);
1086			ntsync_unlock_obj(dev, obj, all);
1087		}
1088	}
1089
1090	/* sleep */
1091
1092	ret = ntsync_schedule(q, &args);
1093
1094	/* and finally, unqueue */
1095
1096	mutex_lock(&dev->wait_all_lock);
1097
1098	for (i = 0; i < args.count; i++) {
1099		struct ntsync_q_entry *entry = &q->entries[i];
1100		struct ntsync_obj *obj = entry->obj;
1101
1102		/*
1103		 * obj->all_waiters is protected by dev->wait_all_lock rather
1104		 * than obj->lock, so there is no need to acquire it here.
1105		 */
1106		list_del(&entry->node);
1107
1108		atomic_dec(&obj->all_hint);
1109
1110		put_obj(obj);
1111	}
1112
1113	mutex_unlock(&dev->wait_all_lock);
1114
1115	if (args.alert) {
1116		struct ntsync_q_entry *entry = &q->entries[args.count];
1117		struct ntsync_obj *obj = entry->obj;
1118		bool all;
1119
1120		all = ntsync_lock_obj(dev, obj);
1121		list_del(&entry->node);
1122		ntsync_unlock_obj(dev, obj, all);
1123
1124		put_obj(obj);
1125	}
1126
1127	signaled = atomic_read(&q->signaled);
1128	if (signaled != -1) {
1129		struct ntsync_wait_args __user *user_args = argp;
1130
1131		/* even if we caught a signal, we need to communicate success */
1132		ret = q->ownerdead ? -EOWNERDEAD : 0;
1133
1134		if (put_user(signaled, &user_args->index))
1135			ret = -EFAULT;
1136	} else if (!ret) {
1137		ret = -ETIMEDOUT;
1138	}
1139
1140	kfree(q);
1141	return ret;
1142}
1143
1144static int ntsync_char_open(struct inode *inode, struct file *file)
1145{
1146	struct ntsync_device *dev;
1147
1148	dev = kzalloc(sizeof(*dev), GFP_KERNEL);
1149	if (!dev)
1150		return -ENOMEM;
1151
1152	mutex_init(&dev->wait_all_lock);
1153
1154	file->private_data = dev;
1155	dev->file = file;
1156	return nonseekable_open(inode, file);
1157}
1158
1159static int ntsync_char_release(struct inode *inode, struct file *file)
1160{
1161	struct ntsync_device *dev = file->private_data;
1162
1163	kfree(dev);
1164
1165	return 0;
1166}
1167
1168static long ntsync_char_ioctl(struct file *file, unsigned int cmd,
1169			      unsigned long parm)
1170{
1171	struct ntsync_device *dev = file->private_data;
1172	void __user *argp = (void __user *)parm;
1173
1174	switch (cmd) {
1175	case NTSYNC_IOC_CREATE_EVENT:
1176		return ntsync_create_event(dev, argp);
1177	case NTSYNC_IOC_CREATE_MUTEX:
1178		return ntsync_create_mutex(dev, argp);
1179	case NTSYNC_IOC_CREATE_SEM:
1180		return ntsync_create_sem(dev, argp);
1181	case NTSYNC_IOC_WAIT_ALL:
1182		return ntsync_wait_all(dev, argp);
1183	case NTSYNC_IOC_WAIT_ANY:
1184		return ntsync_wait_any(dev, argp);
1185	default:
1186		return -ENOIOCTLCMD;
1187	}
1188}
1189
1190static const struct file_operations ntsync_fops = {
1191	.owner		= THIS_MODULE,
1192	.open		= ntsync_char_open,
1193	.release	= ntsync_char_release,
1194	.unlocked_ioctl	= ntsync_char_ioctl,
1195	.compat_ioctl	= compat_ptr_ioctl,
1196};
1197
1198static struct miscdevice ntsync_misc = {
1199	.minor		= MISC_DYNAMIC_MINOR,
1200	.name		= NTSYNC_NAME,
1201	.fops		= &ntsync_fops,
1202	.mode		= 0666,
1203};
1204
1205module_misc_device(ntsync_misc);
1206
1207MODULE_AUTHOR("Elizabeth Figura <zfigura@codeweavers.com>");
1208MODULE_DESCRIPTION("Kernel driver for NT synchronization primitives");
1209MODULE_LICENSE("GPL");