1/*
2 * Copyright 2010, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include <user_mutex.h>
8#include <user_mutex_defs.h>
9
10#include <condition_variable.h>
11#include <kernel.h>
12#include <lock.h>
13#include <smp.h>
14#include <syscall_restart.h>
15#include <util/AutoLock.h>
16#include <util/OpenHashTable.h>
17#include <vm/vm.h>
18#include <vm/VMArea.h>
19
20
21struct UserMutexEntry;
22typedef DoublyLinkedList<UserMutexEntry> UserMutexEntryList;
23
24struct UserMutexEntry : public DoublyLinkedListLinkImpl<UserMutexEntry> {
25	addr_t				address;
26	ConditionVariable	condition;
27	bool				locked;
28	UserMutexEntryList	otherEntries;
29	UserMutexEntry*		hashNext;
30};
31
32struct UserMutexHashDefinition {
33	typedef addr_t			KeyType;
34	typedef UserMutexEntry	ValueType;
35
36	size_t HashKey(addr_t key) const
37	{
38		return key >> 2;
39	}
40
41	size_t Hash(const UserMutexEntry* value) const
42	{
43		return HashKey(value->address);
44	}
45
46	bool Compare(addr_t key, const UserMutexEntry* value) const
47	{
48		return value->address == key;
49	}
50
51	UserMutexEntry*& GetLink(UserMutexEntry* value) const
52	{
53		return value->hashNext;
54	}
55};
56
57typedef BOpenHashTable<UserMutexHashDefinition> UserMutexTable;
58
59
60static UserMutexTable sUserMutexTable;
61static mutex sUserMutexTableLock = MUTEX_INITIALIZER("user mutex table");
62
63
64static void
65add_user_mutex_entry(UserMutexEntry* entry)
66{
67	UserMutexEntry* firstEntry = sUserMutexTable.Lookup(entry->address);
68	if (firstEntry != NULL)
69		firstEntry->otherEntries.Add(entry);
70	else
71		sUserMutexTable.Insert(entry);
72}
73
74
75static bool
76remove_user_mutex_entry(UserMutexEntry* entry)
77{
78	UserMutexEntry* firstEntry = sUserMutexTable.Lookup(entry->address);
79	if (firstEntry != entry) {
80		// The entry is not the first entry in the table. Just remove it from
81		// the first entry's list.
82		firstEntry->otherEntries.Remove(entry);
83		return true;
84	}
85
86	// The entry is the first entry in the table. Remove it from the table and,
87	// if any, add the next entry to the table.
88	sUserMutexTable.Remove(entry);
89
90	firstEntry = entry->otherEntries.RemoveHead();
91	if (firstEntry != NULL) {
92		firstEntry->otherEntries.MoveFrom(&entry->otherEntries);
93		sUserMutexTable.Insert(firstEntry);
94		return true;
95	}
96
97	return false;
98}
99
100
101static status_t
102user_mutex_lock_locked(vint32* mutex, addr_t physicalAddress, const char* name,
103	uint32 flags, bigtime_t timeout, MutexLocker& locker)
104{
105	// mark the mutex locked + waiting
106	int32 oldValue = atomic_or(mutex,
107		B_USER_MUTEX_LOCKED | B_USER_MUTEX_WAITING);
108
109	// The mutex might have been unlocked (or disabled) in the meantime.
110	if ((oldValue & (B_USER_MUTEX_LOCKED | B_USER_MUTEX_WAITING)) == 0
111			|| (oldValue & B_USER_MUTEX_DISABLED) != 0) {
112		// clear the waiting flag and be done
113		atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING);
114		return B_OK;
115	}
116
117	// we have to wait
118
119	// add the entry to the table
120	UserMutexEntry entry;
121	entry.address = physicalAddress;
122	entry.locked = false;
123	add_user_mutex_entry(&entry);
124
125	// wait
126	ConditionVariableEntry waitEntry;
127	entry.condition.Init((void*)physicalAddress, "user mutex");
128	entry.condition.Add(&waitEntry);
129
130	locker.Unlock();
131	status_t error = waitEntry.Wait(flags, timeout);
132	locker.Lock();
133
134	// dequeue
135	if (!remove_user_mutex_entry(&entry)) {
136		// no one is waiting anymore -- clear the waiting flag
137		atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING);
138	}
139
140	if (error != B_OK
141			&& (entry.locked || (*mutex & B_USER_MUTEX_DISABLED) != 0)) {
142		// timeout or interrupt, but the mutex was unlocked or disabled in time
143		error = B_OK;
144	}
145
146	return error;
147}
148
149
150static void
151user_mutex_unlock_locked(vint32* mutex, addr_t physicalAddress, uint32 flags)
152{
153	if (UserMutexEntry* entry = sUserMutexTable.Lookup(physicalAddress)) {
154		// Someone is waiting -- set the locked flag. It might still be set,
155		// but when using userland atomic operations, the caller will usually
156		// have cleared it already.
157		int32 oldValue = atomic_or(mutex, B_USER_MUTEX_LOCKED);
158
159		// unblock the first thread
160		entry->locked = true;
161		entry->condition.NotifyOne();
162
163		if ((flags & B_USER_MUTEX_UNBLOCK_ALL) != 0
164				|| (oldValue & B_USER_MUTEX_DISABLED) != 0) {
165			// unblock all the other waiting threads as well
166			for (UserMutexEntryList::Iterator it
167					= entry->otherEntries.GetIterator();
168				UserMutexEntry* otherEntry = it.Next();) {
169				otherEntry->locked = true;
170				otherEntry->condition.NotifyOne();
171			}
172		}
173	} else {
174		// no one is waiting -- clear locked flag
175		atomic_and(mutex, ~(int32)B_USER_MUTEX_LOCKED);
176	}
177}
178
179
180static status_t
181user_mutex_lock(int32* mutex, const char* name, uint32 flags, bigtime_t timeout)
182{
183	// wire the page and get the physical address
184	VMPageWiringInfo wiringInfo;
185	status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)mutex, true,
186		&wiringInfo);
187	if (error != B_OK)
188		return error;
189
190	// get the lock
191	{
192		MutexLocker locker(sUserMutexTableLock);
193		error = user_mutex_lock_locked(mutex, wiringInfo.physicalAddress, name,
194			flags, timeout, locker);
195	}
196
197	// unwire the page
198	vm_unwire_page(&wiringInfo);
199
200	return error;
201}
202
203
204static status_t
205user_mutex_switch_lock(int32* fromMutex, int32* toMutex, const char* name,
206	uint32 flags, bigtime_t timeout)
207{
208	// wire the pages and get the physical addresses
209	VMPageWiringInfo fromWiringInfo;
210	status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)fromMutex, true,
211		&fromWiringInfo);
212	if (error != B_OK)
213		return error;
214
215	VMPageWiringInfo toWiringInfo;
216	error = vm_wire_page(B_CURRENT_TEAM, (addr_t)toMutex, true, &toWiringInfo);
217	if (error != B_OK) {
218		vm_unwire_page(&fromWiringInfo);
219		return error;
220	}
221
222	// unlock the first mutex and lock the second one
223	{
224		MutexLocker locker(sUserMutexTableLock);
225		user_mutex_unlock_locked(fromMutex, fromWiringInfo.physicalAddress,
226			flags);
227
228		error = user_mutex_lock_locked(toMutex, toWiringInfo.physicalAddress,
229			name, flags, timeout, locker);
230	}
231
232	// unwire the pages
233	vm_unwire_page(&toWiringInfo);
234	vm_unwire_page(&fromWiringInfo);
235
236	return error;
237}
238
239
240// #pragma mark - kernel private
241
242
243void
244user_mutex_init()
245{
246	if (sUserMutexTable.Init() != B_OK)
247		panic("user_mutex_init(): Failed to init table!");
248}
249
250
251// #pragma mark - syscalls
252
253
254status_t
255_user_mutex_lock(int32* mutex, const char* name, uint32 flags,
256	bigtime_t timeout)
257{
258	if (mutex == NULL || !IS_USER_ADDRESS(mutex) || (addr_t)mutex % 4 != 0)
259		return B_BAD_ADDRESS;
260
261	syscall_restart_handle_timeout_pre(flags, timeout);
262
263	status_t error = user_mutex_lock(mutex, name, flags | B_CAN_INTERRUPT,
264		timeout);
265
266	return syscall_restart_handle_timeout_post(error, timeout);
267}
268
269
270status_t
271_user_mutex_unlock(int32* mutex, uint32 flags)
272{
273	if (mutex == NULL || !IS_USER_ADDRESS(mutex) || (addr_t)mutex % 4 != 0)
274		return B_BAD_ADDRESS;
275
276	// wire the page and get the physical address
277	VMPageWiringInfo wiringInfo;
278	status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)mutex, true,
279		&wiringInfo);
280	if (error != B_OK)
281		return error;
282
283	{
284		MutexLocker locker(sUserMutexTableLock);
285		user_mutex_unlock_locked(mutex, wiringInfo.physicalAddress, flags);
286	}
287
288	vm_unwire_page(&wiringInfo);
289
290	return B_OK;
291}
292
293
294status_t
295_user_mutex_switch_lock(int32* fromMutex, int32* toMutex, const char* name,
296	uint32 flags, bigtime_t timeout)
297{
298	if (fromMutex == NULL || !IS_USER_ADDRESS(fromMutex)
299			|| (addr_t)fromMutex % 4 != 0 || toMutex == NULL
300			|| !IS_USER_ADDRESS(toMutex) || (addr_t)toMutex % 4 != 0) {
301		return B_BAD_ADDRESS;
302	}
303
304	return user_mutex_switch_lock(fromMutex, toMutex, name,
305		flags | B_CAN_INTERRUPT, timeout);
306}
307