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