6 ms·

Why Spinlocks Are Bad On iOS

70 points by lilyball 11y ago

jamessu 11y ago
If a scheduler change breaks userland apps, that sounds like a scheduler bug to me... Any word on whether there is going to be a rollback/further scheduler changes to make spinlocks useful again?
- eridius 11y ago
  There will not. QOS was a very large and intentional change, and it's critical to getting great performance out of iOS and to make the fanless MacBook work at all. In general, Apple has never encouraged anyone to use spinlocks, and as I mentioned at the end, as long as your critical section is really tiny and CPU-bound you're unlikely to actually have a problem in practice. Note that spinlocks have always had a problem with priority inversion (OSSpinLock's back-off algorithm is just to call syscall_thread_switch with a 1ms delay every 1024 iterations, which is not bad but doesn't solve all priority inversions anyway).
- gaze 11y ago
  Those folks shouldn't have been using spinlocks!
umanwizard 11y ago
> since threads spinning on a spinlock are always runnable, this means that if there's enough high-QOS threads waiting on a lock held by a lower-QOS thread, the thread that owns the lock will never execute. Is this true? OSSpinLock (at least on OS X) calls thread_switch for 1ms every 1024 iterations (which as far as I understand is basically sleeping[1]). Presumably it's not runnable while it's sleeping? After 100 * 1024 iterations it will also ask to be throttled to the lowest priority for 1ms, again with thread_switch. [1] http://web.mit.edu/darwin/src/modules/xnu/osfmk/man/thread_switch.html http://web.mit.edu/darwin/src/modules/xnu/osfmk/man/thread_s...
- eridius 11y ago
  I didn't go into OSSpinLock specifics because I didn't want the distraction. The naive spinlock shown in the post certainly is always runnable. OSSpinLock's behavior helps with priority inversions, but it doesn't solve the issue with QOS. If there's enough threads of a high QOS blocked on an OSSpinLock it can still livelock. Only truly unbounded backoff can solve that in all cases, but that can lead to high-QOS threads being delayed for a long time (according to the Apple engineer it could result in "tens of seconds" of delay, which is obviously not acceptable for a high-QOS thread).
  - comex 11y ago
    Why not "just" fall back to a mutex after enough spinning? I guess this would require an extra branch in the unlocking function (to check whether there are threads blocked in the kernel that need to be woken up), but that doesn't sound too awful especially as the branch would very rarely be taken. (It would sort of break OSSpinLock's ABI though. Sort of.) AKA an adaptive mutex.
    - eridius 11y ago
      (rewritten after looking up Linux's adaptive mutex) Assuming you mean something like http://stackoverflow.com/a/25168942/582 http://stackoverflow.com/a/25168942/582, you basically need a full mutex anyway, so I'm not sure why you wouldn't just use a mutex directly. I don't think you can really implement this adaptive mutex in userland because you can't just use a spinlock + a mutex (you'd have to lock the mutex every time anyway, which defeats the point of having the spinlock) and syscalls are not considered public API (the kernel is allowed to change syscalls between versions, libc/libsystem is the only public API for them). FWIW pthread mutexes were sped up 2-2.5x in "new OSs" to compensate for spinlocks being illegal (https://twitter.com/catfish_man/status/676852111527706624 https://twitter.com/catfish_man/status/676852111527706624).
      - pcwalton 11y ago
        > you'd have to lock the mutex every time anyway I don't understand. Could you explain this in more detail? In Linux, adaptive mutexes are implemented entirely in userspace with futex as the primitive syscall. This is because atomic CAS (cmpxchg, ldrex/strex, etc) suffices to ensure synchronization during the spinning.
devit 11y ago
Did Apple seriously silently change all programs to use what seems to be real-time scheduling? That obviously breaks the whole system, spinlocks or not (threads doing long CPU-bound computations will block everything else).
- eridius 11y ago
  It's been like this for over a year at this point. The whole system appears to still work.
- mwfunk 11y ago
  No? Really? Seriously? See also pthread_spin_lock on your friendly neighborhood Linux box or other post-2001 POSIXy system.
- astrange 11y ago
  Threads using the realtime policy in Darwin don't block the system, because if they run out their requested time they're heavily demoted. You can cause pretty bad performance by running too long in user-interactive or in OpenCL, so, like, don't do that.
altonzheng 11y ago
Great writeup. Brings me back to my OS class... fun times :)
cbsmith 11y ago
Honestly, naive spinlocks in a mobile OS just generally seem like a bad idea. You just aren't going to get great results.
- spotman 11y ago
  Agreed. This is one of those areas that most mobile developers are better off with a little less rope to hang themselves. The expression hurry up and wait comes to mind. I would rather have a thread sleeping while it waits for slightly less perceptual performance than a thread spinning and chewing through my battery because it's waiting as fast as it can.
to3m 11y ago
The article suggests that new Macbook/OS X might be just as bad, but the linked twitter thread (https://twitter.com/Catfish_Man/status/676851988596809728 https://twitter.com/Catfish_Man/status/676851988596809728) makes the situation there sound rather less serious. The issue appears to be slow progress, rather than a total lack of it. (I had the same problem years ago with somebody's spinlocks on Windows running on a single-CPU system; the obvious functions to yield a timeslice will yield only to a thread of equal or higher priority, meaning you can starve a lower-priority thread. But even when this happens, the lower-priority thread does get a timeslice eventually - which sounds like the OS X situation.)
tsu 11y ago
it seems to me spinlocks are fundamentally dangerous in user space because you cannot disable preemption in user space as you can in kernel space.
cballard 11y ago
I wonder why they're writing a new KVO library, given that KVO is very awkward in Swift. Something like ReactiveCocoa's PropertyType/MutablePropertyType is a much safer approach.

70 points by lilyball 11y ago

If a scheduler change breaks userland apps, that sounds like a scheduler bug to me... Any word on whether there is going to be a rollback/further scheduler changes to make spinlocks useful again?

eridius 11y ago
There will not. QOS was a very large and intentional change, and it's critical to getting great performance out of iOS and to make the fanless MacBook work at all. In general, Apple has never encouraged anyone to use spinlocks, and as I mentioned at the end, as long as your critical section is really tiny and CPU-bound you're unlikely to actually have a problem in practice. Note that spinlocks have always had a problem with priority inversion (OSSpinLock's back-off algorithm is just to call syscall_thread_switch with a 1ms delay every 1024 iterations, which is not bad but doesn't solve all priority inversions anyway).
gaze 11y ago
Those folks shouldn't have been using spinlocks!

umanwizard 11y ago

> since threads spinning on a spinlock are always runnable, this means that if there's enough high-QOS threads waiting on a lock held by a lower-QOS thread, the thread that owns the lock will never execute. Is this true? OSSpinLock (at least on OS X) calls thread_switch for 1ms every 1024 iterations (which as far as I understand is basically sleeping[1]). Presumably it's not runnable while it's sleeping? After 100 * 1024 iterations it will also ask to be throttled to the lowest priority for 1ms, again with thread_switch. [1] http://web.mit.edu/darwin/src/modules/xnu/osfmk/man/thread_switch.html http://web.mit.edu/darwin/src/modules/xnu/osfmk/man/thread_s...

eridius 11y ago
I didn't go into OSSpinLock specifics because I didn't want the distraction. The naive spinlock shown in the post certainly is always runnable. OSSpinLock's behavior helps with priority inversions, but it doesn't solve the issue with QOS. If there's enough threads of a high QOS blocked on an OSSpinLock it can still livelock. Only truly unbounded backoff can solve that in all cases, but that can lead to high-QOS threads being delayed for a long time (according to the Apple engineer it could result in "tens of seconds" of delay, which is obviously not acceptable for a high-QOS thread).
- comex 11y ago
  Why not "just" fall back to a mutex after enough spinning? I guess this would require an extra branch in the unlocking function (to check whether there are threads blocked in the kernel that need to be woken up), but that doesn't sound too awful especially as the branch would very rarely be taken. (It would sort of break OSSpinLock's ABI though. Sort of.) AKA an adaptive mutex.
  - eridius 11y ago
    (rewritten after looking up Linux's adaptive mutex) Assuming you mean something like http://stackoverflow.com/a/25168942/582 http://stackoverflow.com/a/25168942/582, you basically need a full mutex anyway, so I'm not sure why you wouldn't just use a mutex directly. I don't think you can really implement this adaptive mutex in userland because you can't just use a spinlock + a mutex (you'd have to lock the mutex every time anyway, which defeats the point of having the spinlock) and syscalls are not considered public API (the kernel is allowed to change syscalls between versions, libc/libsystem is the only public API for them). FWIW pthread mutexes were sped up 2-2.5x in "new OSs" to compensate for spinlocks being illegal (https://twitter.com/catfish_man/status/676852111527706624 https://twitter.com/catfish_man/status/676852111527706624).
    - pcwalton 11y ago
      > you'd have to lock the mutex every time anyway I don't understand. Could you explain this in more detail? In Linux, adaptive mutexes are implemented entirely in userspace with futex as the primitive syscall. This is because atomic CAS (cmpxchg, ldrex/strex, etc) suffices to ensure synchronization during the spinning.

devit 11y ago

Did Apple seriously silently change all programs to use what seems to be real-time scheduling? That obviously breaks the whole system, spinlocks or not (threads doing long CPU-bound computations will block everything else).

eridius 11y ago
It's been like this for over a year at this point. The whole system appears to still work.
mwfunk 11y ago
No? Really? Seriously? See also pthread_spin_lock on your friendly neighborhood Linux box or other post-2001 POSIXy system.
astrange 11y ago
Threads using the realtime policy in Darwin don't block the system, because if they run out their requested time they're heavily demoted. You can cause pretty bad performance by running too long in user-interactive or in OpenCL, so, like, don't do that.

altonzheng 11y ago

Great writeup. Brings me back to my OS class... fun times :)

cbsmith 11y ago

Honestly, naive spinlocks in a mobile OS just generally seem like a bad idea. You just aren't going to get great results.

spotman 11y ago
Agreed. This is one of those areas that most mobile developers are better off with a little less rope to hang themselves. The expression hurry up and wait comes to mind. I would rather have a thread sleeping while it waits for slightly less perceptual performance than a thread spinning and chewing through my battery because it's waiting as fast as it can.

to3m 11y ago

The article suggests that new Macbook/OS X might be just as bad, but the linked twitter thread (https://twitter.com/Catfish_Man/status/676851988596809728 https://twitter.com/Catfish_Man/status/676851988596809728) makes the situation there sound rather less serious. The issue appears to be slow progress, rather than a total lack of it. (I had the same problem years ago with somebody's spinlocks on Windows running on a single-CPU system; the obvious functions to yield a timeslice will yield only to a thread of equal or higher priority, meaning you can starve a lower-priority thread. But even when this happens, the lower-priority thread does get a timeslice eventually - which sounds like the OS X situation.)

tsu 11y ago

it seems to me spinlocks are fundamentally dangerous in user space because you cannot disable preemption in user space as you can in kernel space.

cballard 11y ago

I wonder why they're writing a new KVO library, given that KVO is very awkward in Swift. Something like ReactiveCocoa's PropertyType/MutablePropertyType is a much safer approach.