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 entry.condition.Init((void*)physicalAddress, "user mutex"); 115 status_t error = entry.condition.Wait(locker.Get(), flags, timeout); 116 117 if (error != B_OK && entry.locked) 118 error = B_OK; 119 120 if (!entry.locked) { 121 // if nobody woke us up, we have to dequeue ourselves 122 lastWaiter = !remove_user_mutex_entry(&entry); 123 } else { 124 // otherwise the waker has done the work of marking the 125 // mutex or semaphore uncontended 126 lastWaiter = false; 127 } 128 129 return error; 130 } 131 132 133 static status_t 134 user_mutex_lock_locked(int32* mutex, addr_t physicalAddress, 135 const char* name, uint32 flags, bigtime_t timeout, MutexLocker& locker) 136 { 137 // mark the mutex locked + waiting 138 set_ac(); 139 int32 oldValue = atomic_or(mutex, 140 B_USER_MUTEX_LOCKED | B_USER_MUTEX_WAITING); 141 clear_ac(); 142 143 if ((oldValue & (B_USER_MUTEX_LOCKED | B_USER_MUTEX_WAITING)) == 0 144 || (oldValue & B_USER_MUTEX_DISABLED) != 0) { 145 // clear the waiting flag and be done 146 set_ac(); 147 atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING); 148 clear_ac(); 149 return B_OK; 150 } 151 152 bool lastWaiter; 153 status_t error = user_mutex_wait_locked(mutex, physicalAddress, name, 154 flags, timeout, locker, lastWaiter); 155 156 if (lastWaiter) { 157 set_ac(); 158 atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING); 159 clear_ac(); 160 } 161 162 return error; 163 } 164 165 166 static void 167 user_mutex_unlock_locked(int32* mutex, addr_t physicalAddress, uint32 flags) 168 { 169 UserMutexEntry* entry = sUserMutexTable.Lookup(physicalAddress); 170 if (entry == NULL) { 171 // no one is waiting -- clear locked flag 172 set_ac(); 173 atomic_and(mutex, ~(int32)B_USER_MUTEX_LOCKED); 174 clear_ac(); 175 return; 176 } 177 178 // Someone is waiting -- set the locked flag. It might still be set, 179 // but when using userland atomic operations, the caller will usually 180 // have cleared it already. 181 set_ac(); 182 int32 oldValue = atomic_or(mutex, B_USER_MUTEX_LOCKED); 183 clear_ac(); 184 185 // unblock the first thread 186 entry->locked = true; 187 entry->condition.NotifyOne(); 188 189 if ((flags & B_USER_MUTEX_UNBLOCK_ALL) != 0 190 || (oldValue & B_USER_MUTEX_DISABLED) != 0) { 191 // unblock and dequeue all the other waiting threads as well 192 while (UserMutexEntry* otherEntry = entry->otherEntries.RemoveHead()) { 193 otherEntry->locked = true; 194 otherEntry->condition.NotifyOne(); 195 } 196 197 // dequeue the first thread and mark the mutex uncontended 198 sUserMutexTable.Remove(entry); 199 set_ac(); 200 atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING); 201 clear_ac(); 202 } else { 203 bool otherWaiters = remove_user_mutex_entry(entry); 204 if (!otherWaiters) { 205 set_ac(); 206 atomic_and(mutex, ~(int32)B_USER_MUTEX_WAITING); 207 clear_ac(); 208 } 209 } 210 } 211 212 213 static status_t 214 user_mutex_sem_acquire_locked(int32* sem, addr_t physicalAddress, 215 const char* name, uint32 flags, bigtime_t timeout, MutexLocker& locker) 216 { 217 // The semaphore may have been released in the meantime, and we also 218 // need to mark it as contended if it isn't already. 219 set_ac(); 220 int32 oldValue = atomic_get(sem); 221 clear_ac(); 222 while (oldValue > -1) { 223 set_ac(); 224 int32 value = atomic_test_and_set(sem, oldValue - 1, oldValue); 225 clear_ac(); 226 if (value == oldValue && value > 0) 227 return B_OK; 228 oldValue = value; 229 } 230 231 bool lastWaiter; 232 status_t error = user_mutex_wait_locked(sem, physicalAddress, name, flags, 233 timeout, locker, lastWaiter); 234 235 if (lastWaiter) { 236 set_ac(); 237 atomic_test_and_set(sem, 0, -1); 238 clear_ac(); 239 } 240 241 return error; 242 } 243 244 245 static void 246 user_mutex_sem_release_locked(int32* sem, addr_t physicalAddress) 247 { 248 UserMutexEntry* entry = sUserMutexTable.Lookup(physicalAddress); 249 if (!entry) { 250 // no waiters - mark as uncontended and release 251 set_ac(); 252 int32 oldValue = atomic_get(sem); 253 clear_ac(); 254 while (true) { 255 int32 inc = oldValue < 0 ? 2 : 1; 256 set_ac(); 257 int32 value = atomic_test_and_set(sem, oldValue + inc, oldValue); 258 clear_ac(); 259 if (value == oldValue) 260 return; 261 oldValue = value; 262 } 263 } 264 265 bool otherWaiters = remove_user_mutex_entry(entry); 266 267 entry->locked = true; 268 entry->condition.NotifyOne(); 269 270 if (!otherWaiters) { 271 // mark the semaphore uncontended 272 set_ac(); 273 atomic_test_and_set(sem, 0, -1); 274 clear_ac(); 275 } 276 } 277 278 279 static status_t 280 user_mutex_lock(int32* mutex, const char* name, uint32 flags, bigtime_t timeout) 281 { 282 // wire the page and get the physical address 283 VMPageWiringInfo wiringInfo; 284 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)mutex, true, 285 &wiringInfo); 286 if (error != B_OK) 287 return error; 288 289 // get the lock 290 { 291 MutexLocker locker(sUserMutexTableLock); 292 error = user_mutex_lock_locked(mutex, wiringInfo.physicalAddress, name, 293 flags, timeout, locker); 294 } 295 296 // unwire the page 297 vm_unwire_page(&wiringInfo); 298 299 return error; 300 } 301 302 303 static status_t 304 user_mutex_switch_lock(int32* fromMutex, int32* toMutex, const char* name, 305 uint32 flags, bigtime_t timeout) 306 { 307 // wire the pages and get the physical addresses 308 VMPageWiringInfo fromWiringInfo; 309 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)fromMutex, true, 310 &fromWiringInfo); 311 if (error != B_OK) 312 return error; 313 314 VMPageWiringInfo toWiringInfo; 315 error = vm_wire_page(B_CURRENT_TEAM, (addr_t)toMutex, true, &toWiringInfo); 316 if (error != B_OK) { 317 vm_unwire_page(&fromWiringInfo); 318 return error; 319 } 320 321 // unlock the first mutex and lock the second one 322 { 323 MutexLocker locker(sUserMutexTableLock); 324 user_mutex_unlock_locked(fromMutex, fromWiringInfo.physicalAddress, 325 flags); 326 327 error = user_mutex_lock_locked(toMutex, toWiringInfo.physicalAddress, 328 name, flags, timeout, locker); 329 } 330 331 // unwire the pages 332 vm_unwire_page(&toWiringInfo); 333 vm_unwire_page(&fromWiringInfo); 334 335 return error; 336 } 337 338 339 // #pragma mark - kernel private 340 341 342 void 343 user_mutex_init() 344 { 345 if (sUserMutexTable.Init() != B_OK) 346 panic("user_mutex_init(): Failed to init table!"); 347 } 348 349 350 // #pragma mark - syscalls 351 352 353 status_t 354 _user_mutex_lock(int32* mutex, const char* name, uint32 flags, 355 bigtime_t timeout) 356 { 357 if (mutex == NULL || !IS_USER_ADDRESS(mutex) || (addr_t)mutex % 4 != 0) 358 return B_BAD_ADDRESS; 359 360 syscall_restart_handle_timeout_pre(flags, timeout); 361 362 status_t error = user_mutex_lock(mutex, name, flags | B_CAN_INTERRUPT, 363 timeout); 364 365 return syscall_restart_handle_timeout_post(error, timeout); 366 } 367 368 369 status_t 370 _user_mutex_unlock(int32* mutex, uint32 flags) 371 { 372 if (mutex == NULL || !IS_USER_ADDRESS(mutex) || (addr_t)mutex % 4 != 0) 373 return B_BAD_ADDRESS; 374 375 // wire the page and get the physical address 376 VMPageWiringInfo wiringInfo; 377 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)mutex, true, 378 &wiringInfo); 379 if (error != B_OK) 380 return error; 381 382 { 383 MutexLocker locker(sUserMutexTableLock); 384 user_mutex_unlock_locked(mutex, wiringInfo.physicalAddress, flags); 385 } 386 387 vm_unwire_page(&wiringInfo); 388 389 return B_OK; 390 } 391 392 393 status_t 394 _user_mutex_switch_lock(int32* fromMutex, int32* toMutex, const char* name, 395 uint32 flags, bigtime_t timeout) 396 { 397 if (fromMutex == NULL || !IS_USER_ADDRESS(fromMutex) 398 || (addr_t)fromMutex % 4 != 0 || toMutex == NULL 399 || !IS_USER_ADDRESS(toMutex) || (addr_t)toMutex % 4 != 0) { 400 return B_BAD_ADDRESS; 401 } 402 403 return user_mutex_switch_lock(fromMutex, toMutex, name, 404 flags | B_CAN_INTERRUPT, timeout); 405 } 406 407 408 status_t 409 _user_mutex_sem_acquire(int32* sem, const char* name, uint32 flags, 410 bigtime_t timeout) 411 { 412 if (sem == NULL || !IS_USER_ADDRESS(sem) || (addr_t)sem % 4 != 0) 413 return B_BAD_ADDRESS; 414 415 syscall_restart_handle_timeout_pre(flags, timeout); 416 417 // wire the page and get the physical address 418 VMPageWiringInfo wiringInfo; 419 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)sem, true, 420 &wiringInfo); 421 if (error != B_OK) 422 return error; 423 424 { 425 MutexLocker locker(sUserMutexTableLock); 426 error = user_mutex_sem_acquire_locked(sem, wiringInfo.physicalAddress, 427 name, flags | B_CAN_INTERRUPT, timeout, locker); 428 } 429 430 vm_unwire_page(&wiringInfo); 431 return syscall_restart_handle_timeout_post(error, timeout); 432 } 433 434 435 status_t 436 _user_mutex_sem_release(int32* sem) 437 { 438 if (sem == NULL || !IS_USER_ADDRESS(sem) || (addr_t)sem % 4 != 0) 439 return B_BAD_ADDRESS; 440 441 // wire the page and get the physical address 442 VMPageWiringInfo wiringInfo; 443 status_t error = vm_wire_page(B_CURRENT_TEAM, (addr_t)sem, true, 444 &wiringInfo); 445 if (error != B_OK) 446 return error; 447 448 { 449 MutexLocker locker(sUserMutexTableLock); 450 user_mutex_sem_release_locked(sem, wiringInfo.physicalAddress); 451 } 452 453 vm_unwire_page(&wiringInfo); 454 return B_OK; 455 } 456