1/*
2 * Copyright 2023, Haiku, Inc. All rights reserved.
3 * Copyright 2018, J��r��me Duval, jerome.duval@gmail.com.
4 * Copyright 2015, Hamish Morrison, hamishm53@gmail.com.
5 * Copyright 2010, Ingo Weinhold, ingo_weinhold@gmx.de.
6 * Distributed under the terms of the MIT License.
7 */
8
9
10#include <user_mutex.h>
11#include <user_mutex_defs.h>
12
13#include <condition_variable.h>
14#include <kernel.h>
15#include <lock.h>
16#include <smp.h>
17#include <syscall_restart.h>
18#include <util/AutoLock.h>
19#include <util/ThreadAutoLock.h>
20#include <util/OpenHashTable.h>
21#include <vm/vm.h>
22#include <vm/VMArea.h>
23#include <arch/generic/user_memory.h>
24
25
26/*! One UserMutexEntry corresponds to one mutex address.
27 *
28 * The mutex's "waiting" state is controlled by the rw_lock: a waiter acquires
29 * a "read" lock before initiating a wait, and an unblocker acquires a "write"
30 * lock. That way, unblockers can be sure that no waiters will start waiting
31 * during unblock, and they can thus safely (without races) unset WAITING.
32 */
33struct UserMutexEntry {
34	generic_addr_t		address;
35	UserMutexEntry*		hash_next;
36	int32				ref_count;
37
38	rw_lock				lock;
39	ConditionVariable	condition;
40};
41
42struct UserMutexHashDefinition {
43	typedef generic_addr_t	KeyType;
44	typedef UserMutexEntry	ValueType;
45
46	size_t HashKey(generic_addr_t key) const
47	{
48		return key >> 2;
49	}
50
51	size_t Hash(const UserMutexEntry* value) const
52	{
53		return HashKey(value->address);
54	}
55
56	bool Compare(generic_addr_t key, const UserMutexEntry* value) const
57	{
58		return value->address == key;
59	}
60
61	UserMutexEntry*& GetLink(UserMutexEntry* value) const
62	{
63		return value->hash_next;
64	}
65};
66
67typedef BOpenHashTable<UserMutexHashDefinition> UserMutexTable;
68
69
70struct user_mutex_context {
71	UserMutexTable table;
72	rw_lock lock;
73};
74static user_mutex_context sSharedUserMutexContext;
75static const char* kUserMutexEntryType = "umtx entry";
76
77
78// #pragma mark - user atomics
79
80
81static int32
82user_atomic_or(int32* value, int32 orValue, bool isWired)
83{
84	int32 result;
85	if (isWired) {
86		set_ac();
87		result = atomic_or(value, orValue);
88		clear_ac();
89		return result;
90	}
91
92	return user_access([=, &result] {
93		result = atomic_or(value, orValue);
94	}) ? result : INT32_MIN;
95}
96
97
98static int32
99user_atomic_and(int32* value, int32 andValue, bool isWired)
100{
101	int32 result;
102	if (isWired) {
103		set_ac();
104		result = atomic_and(value, andValue);
105		clear_ac();
106		return result;
107	}
108
109	return user_access([=, &result] {
110		result = atomic_and(value, andValue);
111	}) ? result : INT32_MIN;
112}
113
114
115static int32
116user_atomic_get(int32* value, bool isWired)
117{
118	int32 result;
119	if (isWired) {
120		set_ac();
121		result = atomic_get(value);
122		clear_ac();
123		return result;
124	}
125
126	return user_access([=, &result] {
127		result = atomic_get(value);
128	}) ? result : INT32_MIN;
129}
130
131
132static int32
133user_atomic_test_and_set(int32* value, int32 newValue, int32 testAgainst,
134	bool isWired)
135{
136	int32 result;
137	if (isWired) {
138		set_ac();
139		result = atomic_test_and_set(value, newValue, testAgainst);
140		clear_ac();
141		return result;
142	}
143
144	return user_access([=, &result] {
145		result = atomic_test_and_set(value, newValue, testAgainst);
146	}) ? result : INT32_MIN;
147}
148
149
150// #pragma mark - user mutex context
151
152
153static int
154dump_user_mutex(int argc, char** argv)
155{
156	if (argc != 2) {
157		print_debugger_command_usage(argv[0]);
158		return 0;
159	}
160
161	addr_t threadID = parse_expression(argv[1]);
162	if (threadID == 0)
163		return 0;
164
165	Thread* thread = Thread::GetDebug(threadID);
166	if (thread == NULL) {
167		kprintf("no such thread\n");
168		return 0;
169	}
170
171	if (thread->wait.type != THREAD_BLOCK_TYPE_CONDITION_VARIABLE) {
172		kprintf("thread is not blocked on cvar (thus not user_mutex)\n");
173		return 0;
174	}
175
176	ConditionVariable* variable = (ConditionVariable*)thread->wait.object;
177	if (variable->ObjectType() != kUserMutexEntryType) {
178		kprintf("thread is not blocked on user_mutex\n");
179		return 0;
180	}
181
182	UserMutexEntry* entry = (UserMutexEntry*)variable->Object();
183
184	const bool physical = (sSharedUserMutexContext.table.Lookup(entry->address) == entry);
185	kprintf("user mutex entry %p\n", entry);
186	kprintf("  address:  0x%" B_PRIxPHYSADDR " (%s)\n", entry->address,
187		physical ? "physical" : "virtual");
188	kprintf("  refcount: %" B_PRId32 "\n", entry->ref_count);
189	kprintf("  lock:     %p\n", &entry->lock);
190
191	int32 mutex = 0;
192	status_t status = B_ERROR;
193	if (!physical) {
194		status = debug_memcpy(thread->team->id, &mutex,
195			(void*)entry->address, sizeof(mutex));
196	}
197
198	if (status == B_OK)
199		kprintf("  mutex:    0x%" B_PRIx32 "\n", mutex);
200
201	entry->condition.Dump();
202
203	return 0;
204}
205
206
207void
208user_mutex_init()
209{
210	sSharedUserMutexContext.lock = RW_LOCK_INITIALIZER("shared user mutex table");
211	if (sSharedUserMutexContext.table.Init() != B_OK)
212		panic("user_mutex_init(): Failed to init table!");
213
214	add_debugger_command_etc("user_mutex", &dump_user_mutex,
215		"Dump user-mutex info",
216		"<thread>\n"
217		"Prints info about the user-mutex a thread is blocked on.\n"
218		"  <thread>  - Thread ID that is blocked on a user mutex\n", 0);
219}
220
221
222struct user_mutex_context*
223get_team_user_mutex_context()
224{
225	struct user_mutex_context* context =
226		thread_get_current_thread()->team->user_mutex_context;
227	if (context != NULL)
228		return context;
229
230	Team* team = thread_get_current_thread()->team;
231	TeamLocker teamLocker(team);
232	if (team->user_mutex_context != NULL)
233		return team->user_mutex_context;
234
235	context = new(std::nothrow) user_mutex_context;
236	if (context == NULL)
237		return NULL;
238
239	context->lock = RW_LOCK_INITIALIZER("user mutex table");
240	if (context->table.Init() != B_OK) {
241		delete context;
242		return NULL;
243	}
244
245	team->user_mutex_context = context;
246	return context;
247}
248
249
250void
251delete_user_mutex_context(struct user_mutex_context* context)
252{
253	if (context == NULL)
254		return;
255
256	// This should be empty at this point in team destruction.
257	ASSERT(context->table.IsEmpty());
258	delete context;
259}
260
261
262static UserMutexEntry*
263get_user_mutex_entry(struct user_mutex_context* context,
264	generic_addr_t address, bool noInsert = false, bool alreadyLocked = false)
265{
266	ReadLocker tableReadLocker;
267	if (!alreadyLocked)
268		tableReadLocker.SetTo(context->lock, false);
269
270	UserMutexEntry* entry = context->table.Lookup(address);
271	if (entry != NULL) {
272		atomic_add(&entry->ref_count, 1);
273		return entry;
274	} else if (noInsert)
275		return entry;
276
277	tableReadLocker.Unlock();
278	WriteLocker tableWriteLocker(context->lock);
279
280	entry = context->table.Lookup(address);
281	if (entry != NULL) {
282		atomic_add(&entry->ref_count, 1);
283		return entry;
284	}
285
286	entry = new(std::nothrow) UserMutexEntry;
287	if (entry == NULL)
288		return entry;
289
290	entry->address = address;
291	entry->ref_count = 1;
292	rw_lock_init(&entry->lock, "UserMutexEntry lock");
293	entry->condition.Init(entry, kUserMutexEntryType);
294
295	context->table.Insert(entry);
296	return entry;
297}
298
299
300static void
301put_user_mutex_entry(struct user_mutex_context* context, UserMutexEntry* entry)
302{
303	if (entry == NULL)
304		return;
305
306	const generic_addr_t address = entry->address;
307	if (atomic_add(&entry->ref_count, -1) != 1)
308		return;
309
310	WriteLocker tableWriteLocker(context->lock);
311
312	// Was it removed & deleted while we were waiting for the lock?
313	if (context->table.Lookup(address) != entry)
314		return;
315
316	// Or did someone else acquire a reference to it?
317	if (atomic_get(&entry->ref_count) > 0)
318		return;
319
320	context->table.Remove(entry);
321	tableWriteLocker.Unlock();
322
323	rw_lock_destroy(&entry->lock);
324	delete entry;
325}
326
327
328static status_t
329user_mutex_wait_locked(UserMutexEntry* entry,
330	uint32 flags, bigtime_t timeout, ReadLocker& locker)
331{
332	ConditionVariableEntry waiter;
333	entry->condition.Add(&waiter);
334	locker.Unlock();
335
336	return waiter.Wait(flags, timeout);
337}
338
339
340static bool
341user_mutex_prepare_to_lock(UserMutexEntry* entry, int32* mutex, bool isWired)
342{
343	ASSERT_READ_LOCKED_RW_LOCK(&entry->lock);
344
345	int32 oldValue = user_atomic_or(mutex,
346		B_USER_MUTEX_LOCKED | B_USER_MUTEX_WAITING, isWired);
347	if ((oldValue & B_USER_MUTEX_LOCKED) == 0
348			|| (oldValue & B_USER_MUTEX_DISABLED) != 0) {
349		// possibly unset waiting flag
350		if ((oldValue & B_USER_MUTEX_WAITING) == 0) {
351			rw_lock_read_unlock(&entry->lock);
352			rw_lock_write_lock(&entry->lock);
353			if (entry->condition.EntriesCount() == 0)
354				user_atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING, isWired);
355			rw_lock_write_unlock(&entry->lock);
356			rw_lock_read_lock(&entry->lock);
357		}
358		return true;
359	}
360
361	return false;
362}
363
364
365static status_t
366user_mutex_lock_locked(UserMutexEntry* entry, int32* mutex,
367	uint32 flags, bigtime_t timeout, ReadLocker& locker, bool isWired)
368{
369	if (user_mutex_prepare_to_lock(entry, mutex, isWired))
370		return B_OK;
371
372	status_t error = user_mutex_wait_locked(entry, flags, timeout, locker);
373
374	// possibly unset waiting flag
375	if (error != B_OK && entry->condition.EntriesCount() == 0) {
376		WriteLocker writeLocker(entry->lock);
377		if (entry->condition.EntriesCount() == 0)
378			user_atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING, isWired);
379	}
380
381	return error;
382}
383
384
385static void
386user_mutex_unblock(UserMutexEntry* entry, int32* mutex, uint32 flags, bool isWired)
387{
388	WriteLocker entryLocker(entry->lock);
389	if (entry->condition.EntriesCount() == 0) {
390		// Nobody is actually waiting at present.
391		user_atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING, isWired);
392		return;
393	}
394
395	int32 oldValue = 0;
396	if ((flags & B_USER_MUTEX_UNBLOCK_ALL) == 0) {
397		// This is not merely an unblock, but a hand-off.
398		oldValue = user_atomic_or(mutex, B_USER_MUTEX_LOCKED, isWired);
399		if ((oldValue & B_USER_MUTEX_LOCKED) != 0)
400			return;
401	}
402
403	if ((flags & B_USER_MUTEX_UNBLOCK_ALL) != 0
404			|| (oldValue & B_USER_MUTEX_DISABLED) != 0) {
405		// unblock all waiting threads
406		entry->condition.NotifyAll(B_OK);
407	} else {
408		if (!entry->condition.NotifyOne(B_OK))
409			user_atomic_and(mutex, ~(int32)B_USER_MUTEX_LOCKED, isWired);
410	}
411
412	if (entry->condition.EntriesCount() == 0)
413		user_atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING, isWired);
414}
415
416
417static status_t
418user_mutex_sem_acquire_locked(UserMutexEntry* entry, int32* sem,
419	uint32 flags, bigtime_t timeout, ReadLocker& locker, bool isWired)
420{
421	// The semaphore may have been released in the meantime, and we also
422	// need to mark it as contended if it isn't already.
423	int32 oldValue = user_atomic_get(sem, isWired);
424	while (oldValue > -1) {
425		int32 value = user_atomic_test_and_set(sem, oldValue - 1, oldValue, isWired);
426		if (value == oldValue && value > 0)
427			return B_OK;
428		oldValue = value;
429	}
430
431	return user_mutex_wait_locked(entry, flags,
432		timeout, locker);
433}
434
435
436static void
437user_mutex_sem_release(UserMutexEntry* entry, int32* sem, bool isWired)
438{
439	WriteLocker entryLocker(entry->lock);
440	if (entry->condition.NotifyOne(B_OK) == 0) {
441		// no waiters - mark as uncontended and release
442		int32 oldValue = user_atomic_get(sem, isWired);
443		while (true) {
444			int32 inc = oldValue < 0 ? 2 : 1;
445			int32 value = user_atomic_test_and_set(sem, oldValue + inc, oldValue, isWired);
446			if (value == oldValue)
447				return;
448			oldValue = value;
449		}
450	}
451
452	if (entry->condition.EntriesCount() == 0) {
453		// mark the semaphore uncontended
454		user_atomic_test_and_set(sem, 0, -1, isWired);
455	}
456}
457
458
459// #pragma mark - syscalls
460
461
462struct UserMutexContextFetcher {
463	UserMutexContextFetcher(int32* mutex, uint32 flags)
464		:
465		fInitStatus(B_OK),
466		fShared((flags & B_USER_MUTEX_SHARED) != 0),
467		fAddress(0)
468	{
469		if (!fShared) {
470			fContext = get_team_user_mutex_context();
471			if (fContext == NULL) {
472				fInitStatus = B_NO_MEMORY;
473				return;
474			}
475
476			fAddress = (addr_t)mutex;
477		} else {
478			fContext = &sSharedUserMutexContext;
479
480			// wire the page and get the physical address
481			fInitStatus = vm_wire_page(B_CURRENT_TEAM, (addr_t)mutex, true,
482				&fWiringInfo);
483			if (fInitStatus != B_OK)
484				return;
485			fAddress = fWiringInfo.physicalAddress;
486		}
487	}
488
489	~UserMutexContextFetcher()
490	{
491		if (fInitStatus != B_OK)
492			return;
493
494		if (fShared)
495			vm_unwire_page(&fWiringInfo);
496	}
497
498	status_t InitCheck() const
499		{ return fInitStatus; }
500
501	struct user_mutex_context* Context() const
502		{ return fContext; }
503
504	generic_addr_t Address() const
505		{ return fAddress; }
506
507	bool IsWired() const
508		{ return fShared; }
509
510private:
511	status_t fInitStatus;
512	bool fShared;
513	struct user_mutex_context* fContext;
514	VMPageWiringInfo fWiringInfo;
515	generic_addr_t fAddress;
516};
517
518
519static status_t
520user_mutex_lock(int32* mutex, const char* name, uint32 flags, bigtime_t timeout)
521{
522	UserMutexContextFetcher contextFetcher(mutex, flags);
523	if (contextFetcher.InitCheck() != B_OK)
524		return contextFetcher.InitCheck();
525
526	// get the lock
527	UserMutexEntry* entry = get_user_mutex_entry(contextFetcher.Context(),
528		contextFetcher.Address());
529	if (entry == NULL)
530		return B_NO_MEMORY;
531	status_t error = B_OK;
532	{
533		ReadLocker entryLocker(entry->lock);
534		error = user_mutex_lock_locked(entry, mutex,
535			flags, timeout, entryLocker, contextFetcher.IsWired());
536	}
537	put_user_mutex_entry(contextFetcher.Context(), entry);
538
539	return error;
540}
541
542
543static status_t
544user_mutex_switch_lock(int32* fromMutex, uint32 fromFlags,
545	int32* toMutex, const char* name, uint32 toFlags, bigtime_t timeout)
546{
547	UserMutexContextFetcher fromFetcher(fromMutex, fromFlags);
548	if (fromFetcher.InitCheck() != B_OK)
549		return fromFetcher.InitCheck();
550
551	UserMutexContextFetcher toFetcher(toMutex, toFlags);
552	if (toFetcher.InitCheck() != B_OK)
553		return toFetcher.InitCheck();
554
555	// unlock the first mutex and lock the second one
556	UserMutexEntry* fromEntry = NULL,
557		*toEntry = get_user_mutex_entry(toFetcher.Context(), toFetcher.Address());
558	if (toEntry == NULL)
559		return B_NO_MEMORY;
560	status_t error = B_OK;
561	{
562		ConditionVariableEntry waiter;
563
564		bool alreadyLocked = false;
565		{
566			ReadLocker entryLocker(toEntry->lock);
567			alreadyLocked = user_mutex_prepare_to_lock(toEntry, toMutex,
568				toFetcher.IsWired());
569			if (!alreadyLocked)
570				toEntry->condition.Add(&waiter);
571		}
572
573		const int32 oldValue = user_atomic_and(fromMutex, ~(int32)B_USER_MUTEX_LOCKED,
574			fromFetcher.IsWired());
575		if ((oldValue & B_USER_MUTEX_WAITING) != 0) {
576			fromEntry = get_user_mutex_entry(fromFetcher.Context(),
577				fromFetcher.Address(), true);
578			 if (fromEntry != NULL) {
579				 user_mutex_unblock(fromEntry, fromMutex, fromFlags,
580					 fromFetcher.IsWired());
581			 }
582		}
583
584		if (!alreadyLocked)
585			error = waiter.Wait(toFlags, timeout);
586	}
587	put_user_mutex_entry(fromFetcher.Context(), fromEntry);
588	put_user_mutex_entry(toFetcher.Context(), toEntry);
589
590	return error;
591}
592
593
594status_t
595_user_mutex_lock(int32* mutex, const char* name, uint32 flags,
596	bigtime_t timeout)
597{
598	if (mutex == NULL || !IS_USER_ADDRESS(mutex) || (addr_t)mutex % 4 != 0)
599		return B_BAD_ADDRESS;
600
601	syscall_restart_handle_timeout_pre(flags, timeout);
602
603	status_t error = user_mutex_lock(mutex, name, flags | B_CAN_INTERRUPT,
604		timeout);
605
606	return syscall_restart_handle_timeout_post(error, timeout);
607}
608
609
610status_t
611_user_mutex_unblock(int32* mutex, uint32 flags)
612{
613	if (mutex == NULL || !IS_USER_ADDRESS(mutex) || (addr_t)mutex % 4 != 0)
614		return B_BAD_ADDRESS;
615
616	UserMutexContextFetcher contextFetcher(mutex, flags);
617	if (contextFetcher.InitCheck() != B_OK)
618		return contextFetcher.InitCheck();
619	struct user_mutex_context* context = contextFetcher.Context();
620
621	// In the case where there is no entry, we must hold the read lock until we
622	// unset WAITING, because otherwise some other thread could initiate a wait.
623	ReadLocker tableReadLocker(context->lock);
624	UserMutexEntry* entry = get_user_mutex_entry(context,
625		contextFetcher.Address(), true, true);
626	if (entry == NULL) {
627		user_atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING, contextFetcher.IsWired());
628		tableReadLocker.Unlock();
629	} else {
630		tableReadLocker.Unlock();
631		user_mutex_unblock(entry, mutex, flags, contextFetcher.IsWired());
632	}
633	put_user_mutex_entry(context, entry);
634
635	return B_OK;
636}
637
638
639status_t
640_user_mutex_switch_lock(int32* fromMutex, uint32 fromFlags,
641	int32* toMutex, const char* name, uint32 toFlags, bigtime_t timeout)
642{
643	if (fromMutex == NULL || !IS_USER_ADDRESS(fromMutex)
644			|| (addr_t)fromMutex % 4 != 0 || toMutex == NULL
645			|| !IS_USER_ADDRESS(toMutex) || (addr_t)toMutex % 4 != 0) {
646		return B_BAD_ADDRESS;
647	}
648
649	return user_mutex_switch_lock(fromMutex, fromFlags, toMutex, name,
650		toFlags | B_CAN_INTERRUPT, timeout);
651}
652
653
654status_t
655_user_mutex_sem_acquire(int32* sem, const char* name, uint32 flags,
656	bigtime_t timeout)
657{
658	if (sem == NULL || !IS_USER_ADDRESS(sem) || (addr_t)sem % 4 != 0)
659		return B_BAD_ADDRESS;
660
661	syscall_restart_handle_timeout_pre(flags, timeout);
662
663	UserMutexContextFetcher contextFetcher(sem, flags);
664	if (contextFetcher.InitCheck() != B_OK)
665		return contextFetcher.InitCheck();
666	struct user_mutex_context* context = contextFetcher.Context();
667
668	UserMutexEntry* entry = get_user_mutex_entry(context, contextFetcher.Address());
669	if (entry == NULL)
670		return B_NO_MEMORY;
671	status_t error;
672	{
673		ReadLocker entryLocker(entry->lock);
674		error = user_mutex_sem_acquire_locked(entry, sem,
675			flags | B_CAN_INTERRUPT, timeout, entryLocker, contextFetcher.IsWired());
676	}
677	put_user_mutex_entry(context, entry);
678
679	return syscall_restart_handle_timeout_post(error, timeout);
680}
681
682
683status_t
684_user_mutex_sem_release(int32* sem, uint32 flags)
685{
686	if (sem == NULL || !IS_USER_ADDRESS(sem) || (addr_t)sem % 4 != 0)
687		return B_BAD_ADDRESS;
688
689	UserMutexContextFetcher contextFetcher(sem, flags);
690	if (contextFetcher.InitCheck() != B_OK)
691		return contextFetcher.InitCheck();
692	struct user_mutex_context* context = contextFetcher.Context();
693
694	UserMutexEntry* entry = get_user_mutex_entry(context,
695		contextFetcher.Address());
696	{
697		user_mutex_sem_release(entry, sem, contextFetcher.IsWired());
698	}
699	put_user_mutex_entry(context, entry);
700
701	return B_OK;
702}
703