1 /* 2 * Copyright 2018, Jérôme Duval, jerome.duval@gmail.com. 3 * Copyright 2015, Hamish Morrison, hamishm53@gmail.com. 4 * Copyright 2010, Ingo Weinhold, ingo_weinhold@gmx.de. 5 * Distributed under the terms of the MIT License. 6 */ 7 8 9 #include <user_mutex.h> 10 #include <user_mutex_defs.h> 11 12 #include <condition_variable.h> 13 #include <kernel.h> 14 #include <lock.h> 15 #include <smp.h> 16 #include <syscall_restart.h> 17 #include <util/AutoLock.h> 18 #include <util/OpenHashTable.h> 19 #include <vm/vm.h> 20 #include <vm/VMArea.h> 21 22 23 struct UserMutexEntry; 24 typedef DoublyLinkedList<UserMutexEntry> UserMutexEntryList; 25 26 struct UserMutexEntry : public DoublyLinkedListLinkImpl<UserMutexEntry> { 27 addr_t address; 28 ConditionVariable condition; 29 bool locked; 30 UserMutexEntryList otherEntries; 31 UserMutexEntry* hashNext; 32 }; 33 34 struct UserMutexHashDefinition { 35 typedef addr_t KeyType; 36 typedef UserMutexEntry ValueType; 37 38 size_t HashKey(addr_t key) const 39 { 40 return key >> 2; 41 } 42 43 size_t Hash(const UserMutexEntry* value) const 44 { 45 return HashKey(value->address); 46 } 47 48 bool Compare(addr_t key, const UserMutexEntry* value) const 49 { 50 return value->address == key; 51 } 52 53 UserMutexEntry*& GetLink(UserMutexEntry* value) const 54 { 55 return value->hashNext; 56 } 57 }; 58 59 typedef BOpenHashTable<UserMutexHashDefinition> UserMutexTable; 60 61 62 static UserMutexTable sUserMutexTable; 63 static mutex sUserMutexTableLock = MUTEX_INITIALIZER("user mutex table"); 64 65 66 static void 67 add_user_mutex_entry(UserMutexEntry* entry) 68 { 69 UserMutexEntry* firstEntry = sUserMutexTable.Lookup(entry->address); 70 if (firstEntry != NULL) 71 firstEntry->otherEntries.Add(entry); 72 else 73 sUserMutexTable.Insert(entry); 74 } 75 76 77 static bool 78 remove_user_mutex_entry(UserMutexEntry* entry) 79 { 80 UserMutexEntry* firstEntry = sUserMutexTable.Lookup(entry->address); 81 if (firstEntry != entry) { 82 // The entry is not the first entry in the table. Just remove it from 83 // the first entry's list. 84 firstEntry->otherEntries.Remove(entry); 85 return true; 86 } 87 88 // The entry is the first entry in the table. Remove it from the table and, 89 // if any, add the next entry to the table. 90 sUserMutexTable.Remove(entry); 91 92 firstEntry = entry->otherEntries.RemoveHead(); 93 if (firstEntry != NULL) { 94 firstEntry->otherEntries.MoveFrom(&entry->otherEntries); 95 sUserMutexTable.Insert(firstEntry); 96 return true; 97 } 98 99 return false; 100 } 101 102 103 static status_t 104 user_mutex_wait_locked(int32* mutex, addr_t physicalAddress, const char* name, 105 uint32 flags, bigtime_t timeout, MutexLocker& locker, bool& lastWaiter) 106 { 107 // add the entry to the table 108 UserMutexEntry entry; 109 entry.address = physicalAddress; 110 entry.locked = false; 111 add_user_mutex_entry(&entry); 112 113 // wait 114 ConditionVariableEntry waitEntry; 115 entry.condition.Init((void*)physicalAddress, "user mutex"); 116 entry.condition.Add(&waitEntry); 117 118 locker.Unlock(); 119 status_t error = waitEntry.Wait(flags, timeout); 120 locker.Lock(); 121 122 if (error != B_OK && entry.locked) 123 error = B_OK; 124 125 if (!entry.locked) { 126 // if nobody woke us up, we have to dequeue ourselves 127 lastWaiter = !remove_user_mutex_entry(&entry); 128 } else { 129 // otherwise the waker has done the work of marking the 130 // mutex or semaphore uncontended 131 lastWaiter = false; 132 } 133 134 return error; 135 } 136 137 138 static status_t 139 user_mutex_lock_locked(int32* mutex, addr_t physicalAddress, 140 const char* name, uint32 flags, bigtime_t timeout, MutexLocker& locker) 141 { 142 // mark the mutex locked + waiting 143 set_ac(); 144 int32 oldValue = atomic_or(mutex, 145 B_USER_MUTEX_LOCKED | B_USER_MUTEX_WAITING); 146 clear_ac(); 147 148 if ((oldValue & (B_USER_MUTEX_LOCKED | B_USER_MUTEX_WAITING)) == 0 149 || (oldValue & B_USER_MUTEX_DISABLED) != 0) { 150 // clear the waiting flag and be done 151 set_ac(); 152 atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING); 153 clear_ac(); 154 return B_OK; 155 } 156 157 bool lastWaiter; 158 status_t error = user_mutex_wait_locked(mutex, physicalAddress, name, 159 flags, timeout, locker, lastWaiter); 160 161 if (lastWaiter) { 162 set_ac(); 163 atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING); 164 clear_ac(); 165 } 166 167 return error; 168 } 169 170 171 static void 172 user_mutex_unlock_locked(int32* mutex, addr_t physicalAddress, uint32 flags) 173 { 174 UserMutexEntry* entry = sUserMutexTable.Lookup(physicalAddress); 175 if (entry == NULL) { 176 // no one is waiting -- clear locked flag 177 set_ac(); 178 atomic_and(mutex, ~(int32)B_USER_MUTEX_LOCKED); 179 clear_ac(); 180 return; 181 } 182 183 // Someone is waiting -- set the locked flag. It might still be set, 184 // but when using userland atomic operations, the caller will usually 185 // have cleared it already. 186 set_ac(); 187 int32 oldValue = atomic_or(mutex, B_USER_MUTEX_LOCKED); 188 clear_ac(); 189 190 // unblock the first thread 191 entry->locked = true; 192 entry->condition.NotifyOne(); 193 194 if ((flags & B_USER_MUTEX_UNBLOCK_ALL) != 0 195 || (oldValue & B_USER_MUTEX_DISABLED) != 0) { 196 // unblock and dequeue all the other waiting threads as well 197 while (UserMutexEntry* otherEntry = entry->otherEntries.RemoveHead()) { 198 otherEntry->locked = true; 199 otherEntry->condition.NotifyOne(); 200 } 201 202 // dequeue the first thread and mark the mutex uncontended 203 sUserMutexTable.Remove(entry); 204 set_ac(); 205 atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING); 206 clear_ac(); 207 } else { 208 bool otherWaiters = remove_user_mutex_entry(entry); 209 if (!otherWaiters) { 210 set_ac(); 211 atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING); 212 clear_ac(); 213 } 214 } 215 } 216 217 218 static status_t 219 user_mutex_sem_acquire_locked(int32* sem, addr_t physicalAddress, 220 const char* name, uint32 flags, bigtime_t timeout, MutexLocker& locker) 221 { 222 // The semaphore may have been released in the meantime, and we also 223 // need to mark it as contended if it isn't already. 224 set_ac(); 225 int32 oldValue = atomic_get(sem); 226 clear_ac(); 227 while (oldValue > -1) { 228 set_ac(); 229 int32 value = atomic_test_and_set(sem, oldValue - 1, oldValue); 230 clear_ac(); 231 if (value == oldValue && value > 0) 232 return B_OK; 233 oldValue = value; 234 } 235 236 bool lastWaiter; 237 status_t error = user_mutex_wait_locked(sem, physicalAddress, name, flags, 238 timeout, locker, lastWaiter); 239 240 if (lastWaiter) { 241 set_ac(); 242 atomic_test_and_set(sem, 0, -1); 243 clear_ac(); 244 } 245 246 return error; 247 } 248 249 250 static void 251 user_mutex_sem_release_locked(int32* sem, addr_t physicalAddress) 252 { 253 UserMutexEntry* entry = sUserMutexTable.Lookup(physicalAddress); 254 if (!entry) { 255 // no waiters - mark as uncontended and release 256 set_ac(); 257 int32 oldValue = atomic_get(sem); 258 clear_ac(); 259 while (true) { 260 int32 inc = oldValue < 0 ? 2 : 1; 261 set_ac(); 262 int32 value = atomic_test_and_set(sem, oldValue + inc, oldValue); 263 clear_ac(); 264 if (value == oldValue) 265 return; 266 oldValue = value; 267 } 268 } 269 270 bool otherWaiters = remove_user_mutex_entry(entry); 271 272 entry->locked = true; 273 entry->condition.NotifyOne(); 274 275 if (!otherWaiters) { 276 // mark the semaphore uncontended 277 set_ac(); 278 atomic_test_and_set(sem, 0, -1); 279 clear_ac(); 280 } 281 } 282 283 284 static status_t 285 user_mutex_lock(int32* mutex, const char* name, uint32 flags, bigtime_t timeout) 286 { 287 // wire the page and get the physical address 288 VMPageWiringInfo wiringInfo; 289 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)mutex, true, 290 &wiringInfo); 291 if (error != B_OK) 292 return error; 293 294 // get the lock 295 { 296 MutexLocker locker(sUserMutexTableLock); 297 error = user_mutex_lock_locked(mutex, wiringInfo.physicalAddress, name, 298 flags, timeout, locker); 299 } 300 301 // unwire the page 302 vm_unwire_page(&wiringInfo); 303 304 return error; 305 } 306 307 308 static status_t 309 user_mutex_switch_lock(int32* fromMutex, int32* toMutex, const char* name, 310 uint32 flags, bigtime_t timeout) 311 { 312 // wire the pages and get the physical addresses 313 VMPageWiringInfo fromWiringInfo; 314 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)fromMutex, true, 315 &fromWiringInfo); 316 if (error != B_OK) 317 return error; 318 319 VMPageWiringInfo toWiringInfo; 320 error = vm_wire_page(B_CURRENT_TEAM, (addr_t)toMutex, true, &toWiringInfo); 321 if (error != B_OK) { 322 vm_unwire_page(&fromWiringInfo); 323 return error; 324 } 325 326 // unlock the first mutex and lock the second one 327 { 328 MutexLocker locker(sUserMutexTableLock); 329 user_mutex_unlock_locked(fromMutex, fromWiringInfo.physicalAddress, 330 flags); 331 332 error = user_mutex_lock_locked(toMutex, toWiringInfo.physicalAddress, 333 name, flags, timeout, locker); 334 } 335 336 // unwire the pages 337 vm_unwire_page(&toWiringInfo); 338 vm_unwire_page(&fromWiringInfo); 339 340 return error; 341 } 342 343 344 // #pragma mark - kernel private 345 346 347 void 348 user_mutex_init() 349 { 350 if (sUserMutexTable.Init() != B_OK) 351 panic("user_mutex_init(): Failed to init table!"); 352 } 353 354 355 // #pragma mark - syscalls 356 357 358 status_t 359 _user_mutex_lock(int32* mutex, const char* name, uint32 flags, 360 bigtime_t timeout) 361 { 362 if (mutex == NULL || !IS_USER_ADDRESS(mutex) || (addr_t)mutex % 4 != 0) 363 return B_BAD_ADDRESS; 364 365 syscall_restart_handle_timeout_pre(flags, timeout); 366 367 status_t error = user_mutex_lock(mutex, name, flags | B_CAN_INTERRUPT, 368 timeout); 369 370 return syscall_restart_handle_timeout_post(error, timeout); 371 } 372 373 374 status_t 375 _user_mutex_unlock(int32* mutex, uint32 flags) 376 { 377 if (mutex == NULL || !IS_USER_ADDRESS(mutex) || (addr_t)mutex % 4 != 0) 378 return B_BAD_ADDRESS; 379 380 // wire the page and get the physical address 381 VMPageWiringInfo wiringInfo; 382 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)mutex, true, 383 &wiringInfo); 384 if (error != B_OK) 385 return error; 386 387 { 388 MutexLocker locker(sUserMutexTableLock); 389 user_mutex_unlock_locked(mutex, wiringInfo.physicalAddress, flags); 390 } 391 392 vm_unwire_page(&wiringInfo); 393 394 return B_OK; 395 } 396 397 398 status_t 399 _user_mutex_switch_lock(int32* fromMutex, int32* toMutex, const char* name, 400 uint32 flags, bigtime_t timeout) 401 { 402 if (fromMutex == NULL || !IS_USER_ADDRESS(fromMutex) 403 || (addr_t)fromMutex % 4 != 0 || toMutex == NULL 404 || !IS_USER_ADDRESS(toMutex) || (addr_t)toMutex % 4 != 0) { 405 return B_BAD_ADDRESS; 406 } 407 408 return user_mutex_switch_lock(fromMutex, toMutex, name, 409 flags | B_CAN_INTERRUPT, timeout); 410 } 411 412 413 status_t 414 _user_mutex_sem_acquire(int32* sem, const char* name, uint32 flags, 415 bigtime_t timeout) 416 { 417 if (sem == NULL || !IS_USER_ADDRESS(sem) || (addr_t)sem % 4 != 0) 418 return B_BAD_ADDRESS; 419 420 syscall_restart_handle_timeout_pre(flags, timeout); 421 422 // wire the page and get the physical address 423 VMPageWiringInfo wiringInfo; 424 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)sem, true, 425 &wiringInfo); 426 if (error != B_OK) 427 return error; 428 429 { 430 MutexLocker locker(sUserMutexTableLock); 431 error = user_mutex_sem_acquire_locked(sem, wiringInfo.physicalAddress, 432 name, flags | B_CAN_INTERRUPT, timeout, locker); 433 } 434 435 vm_unwire_page(&wiringInfo); 436 return syscall_restart_handle_timeout_post(error, timeout); 437 } 438 439 440 status_t 441 _user_mutex_sem_release(int32* sem) 442 { 443 if (sem == NULL || !IS_USER_ADDRESS(sem) || (addr_t)sem % 4 != 0) 444 return B_BAD_ADDRESS; 445 446 // wire the page and get the physical address 447 VMPageWiringInfo wiringInfo; 448 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)sem, true, 449 &wiringInfo); 450 if (error != B_OK) 451 return error; 452 453 { 454 MutexLocker locker(sUserMutexTableLock); 455 user_mutex_sem_release_locked(sem, wiringInfo.physicalAddress); 456 } 457 458 vm_unwire_page(&wiringInfo); 459 return B_OK; 460 } 461