src/system/kernel/locks/user_mutex.cpp

   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 }