5 ms·

Moreover, is "every lock requires a syscall" accurate? Probably depends on target platform and standard library, but my impression was that at low contention it

Moreover, is "every lock requires a syscall" accurate? Probably depends on target platform and standard library, but my impression was that at low contention it doesn't really require syscalls, at least on Linux and glibc's pthread.

kevincox 3y ago
Definitely not. I don't think there many standard libraries that use syscalls for every lock. It is near universal to attempt a lock in user space (maybe even spin a few times) and only call the kernel if you need to wait. So low-contention locks should very rarely make a syscall.
- adzm 3y ago
  Critical sections in Windows certainly behave this way with a configurable spin count.
m4nu3l 3y ago
That's my understanding too. In Linux mutexes are implemented by futexes (Fast User-Space mutexes). If there is no contention they are guaranteed to not perform a syscall https://en.wikipedia.org/wiki/Futex https://en.wikipedia.org/wiki/Futex
- cout 3y ago
  Maybe this has changed, but last time I looked at futexes there was no syscall for locking (assuming no contention), but unlocking always made a syscall. This was many years ago so it could be different now.
  - m4nu3l 3y ago
    The code isn't the easiest to read but in glibc it seems that the syscall is only performed if waiters are detected in userspace during an unlock operation https://github.com/lattera/glibc/blob/master/nptl/pthread_mutex_unlock.c#LL161C2-L161C16 https://github.com/lattera/glibc/blob/master/nptl/pthread_mu...
    - gpderetta 3y ago
      Indeed You only need to FUTEX_WAKE if you know there are waiters (or of you lost track of the number of waiters).
      - m4nu3l 3y ago
        What can cause the mutex to lose track of the number of waiters?
        ot 3y ago
        Generally you have a small number of bits to count the waiters, because the mutex state has to be a word you can CAS and so you have either 32 or 64 bits to pack all the state you need. If your counter saturates you lose track of the waiters, and you have to fallback somehow.
        m4nu3l 3y ago
        Makes sense, thanks for the explanation!
    - tialaramex 3y ago
      Although it's not the code C++ will be using the Rust implementation is a bit easier to follow: https://doc.rust-lang.org/src/std/sys/unix/locks/futex_mutex.rs.html https://doc.rust-lang.org/src/std/sys/unix/locks/futex_mutex... Unlock is just:: self.futex.swap(0, Release) -- if the value we get back is 2 then we know at least one thread is asleep waiting on this futex, so we need a system call to wake them, but in the uncontended case we're done immediately.
maldev 3y ago
You can literally just do an atomic swap on some memory location. Three lines of assembly, like. mov rax, 1 ; load the value to exchange into rax acquire_lock: ; attempt to acquire the lock xchg byte [ADDR_LOCK], al ; atomically swap the lock value with rax test al, al ; test if the original lock value was 0 (unlocked) jnz acquire_lock ; if it was not, loop until we can acquire the lock The downside is you want a backoff to sleep the thread so it doesn't go into a loop. But the actual lock code is simple. You can easily have this be your function "AcquireLock()" and then do while(!AcquireLock()) { //pause thread execution. } And I think this is where they get the syscall being needed, since this will normally require a syscall to pause the thread from the scheduler.

kevincox 3y ago

Definitely not. I don't think there many standard libraries that use syscalls for every lock. It is near universal to attempt a lock in user space (maybe even spin a few times) and only call the kernel if you need to wait. So low-contention locks should very rarely make a syscall.

adzm 3y ago
Critical sections in Windows certainly behave this way with a configurable spin count.

m4nu3l 3y ago

That's my understanding too. In Linux mutexes are implemented by futexes (Fast User-Space mutexes). If there is no contention they are guaranteed to not perform a syscall https://en.wikipedia.org/wiki/Futex https://en.wikipedia.org/wiki/Futex

cout 3y ago
Maybe this has changed, but last time I looked at futexes there was no syscall for locking (assuming no contention), but unlocking always made a syscall. This was many years ago so it could be different now.
- m4nu3l 3y ago
  The code isn't the easiest to read but in glibc it seems that the syscall is only performed if waiters are detected in userspace during an unlock operation https://github.com/lattera/glibc/blob/master/nptl/pthread_mutex_unlock.c#LL161C2-L161C16 https://github.com/lattera/glibc/blob/master/nptl/pthread_mu...
  - gpderetta 3y ago
    Indeed You only need to FUTEX_WAKE if you know there are waiters (or of you lost track of the number of waiters).
    - m4nu3l 3y ago
      What can cause the mutex to lose track of the number of waiters?
      - ot 3y ago
        Generally you have a small number of bits to count the waiters, because the mutex state has to be a word you can CAS and so you have either 32 or 64 bits to pack all the state you need. If your counter saturates you lose track of the waiters, and you have to fallback somehow.
        m4nu3l 3y ago
        Makes sense, thanks for the explanation!
  - tialaramex 3y ago
    Although it's not the code C++ will be using the Rust implementation is a bit easier to follow: https://doc.rust-lang.org/src/std/sys/unix/locks/futex_mutex.rs.html https://doc.rust-lang.org/src/std/sys/unix/locks/futex_mutex... Unlock is just:: self.futex.swap(0, Release) -- if the value we get back is 2 then we know at least one thread is asleep waiting on this futex, so we need a system call to wake them, but in the uncontended case we're done immediately.

maldev 3y ago

You can literally just do an atomic swap on some memory location. Three lines of assembly, like. mov rax, 1 ; load the value to exchange into rax acquire_lock: ; attempt to acquire the lock xchg byte [ADDR_LOCK], al ; atomically swap the lock value with rax test al, al ; test if the original lock value was 0 (unlocked) jnz acquire_lock ; if it was not, loop until we can acquire the lock The downside is you want a backoff to sleep the thread so it doesn't go into a loop. But the actual lock code is simple. You can easily have this be your function "AcquireLock()" and then do while(!AcquireLock()) { //pause thread execution. } And I think this is where they get the syscall being needed, since this will normally require a syscall to pause the thread from the scheduler.