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 21 struct UserMutexEntry; 22 typedef DoublyLinkedList<UserMutexEntry> UserMutexEntryList; 23 24 struct UserMutexEntry : public DoublyLinkedListLinkImpl<UserMutexEntry> { 25 addr_t address; 26 ConditionVariable condition; 27 bool locked; 28 UserMutexEntryList otherEntries; 29 UserMutexEntry* hashNext; 30 }; 31 32 struct 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 57 typedef BOpenHashTable<UserMutexHashDefinition> UserMutexTable; 58 59 60 static UserMutexTable sUserMutexTable; 61 static mutex sUserMutexTableLock = MUTEX_INITIALIZER("user mutex table"); 62 63 64 static void 65 add_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 75 static bool 76 remove_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 101 static status_t 102 user_mutex_lock_locked(int32* 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 150 static void 151 user_mutex_unlock_locked(int32* 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 180 static status_t 181 user_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 204 static status_t 205 user_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 243 void 244 user_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 254 status_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 270 status_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 294 status_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