Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Close Look at a Spinlock

blog.regehr.org

Post reply on HN
Print view View original

21–30 of 30 posts

Re: A Close Look at a Spinlock

#21

Post by remexre »

monocasa wrote: post #19
dataflow wrote: post #15

Earlier quoted context omitted.

Spins are so short and well-defined that I wonder why the kernel doesn't just examine a handful of instructions around the program counter and guess if the thread is spinning or not before scheduling it for another time slice. Seems like a really nice and simple kind of heuristic to implement.

Oh jeeze, I don't think there'd be anything simple about having to divine facts about user space by the code flow graph near the interrupted instruction on basically every thread switch.

Maybe hardware support would make it viable, at least at an academic level.

Re: A Close Look at a Spinlock

#22

Post by dataflow »

monocasa wrote: post #19
dataflow wrote: post #15

Earlier quoted context omitted.

Spins are so short and well-defined that I wonder why the kernel doesn't just examine a handful of instructions around the program counter and guess if the thread is spinning or not before scheduling it for another time slice. Seems like a really nice and simple kind of heuristic to implement.

Oh jeeze, I don't think there'd be anything simple about having to divine facts about user space by the code flow graph near the interrupted instruction on basically every thread switch.

You don't need to worry about the CFG here, a spinlock is literally just a ~4-instruction loop (or a few more, depending on the form you use). All you need is to handle a few common codegen patterns. Like if you see the instruction pointer in the middle of a mov + xchg + test + jne sequence then you know it's a spinlock. If you don't detect it in some canonical form then you're back where we are now; whatever. It's not complicated.

Re: A Close Look at a Spinlock

#23

Post by logicchains »

sydthrowaway wrote: post #4

One thing I don’t get is how blocking is implemented once you have basic mutual exclusion working? Lets say you try to take the lock, but you spin, waiting for it. But say in your OS now you want the thread to go to sleep until it’s available.. how is actually implemented without spinning and using CPU?

>But say in your OS now you want the thread to go to sleep until it’s available.. how is actually implemented without spinning and using CPU?

If you're facing such low-latency constraints that you need a spinlock, you wouldn't want the thread to sleep, instead you'd pin the core and have the dedicated core constantly spinning. That's how it's done in HFT. You can use a fancy network card like SolarFlare with efvi_drivers to bypass the kernel completely for network IO (spin waiting on the network card). Basically you need to treat the kernel like it's a paedophile trying to molest your children, and do everything you can to stop it touching your low-latency threads.

Re: A Close Look at a Spinlock

#24

Post by fulafel »

sydthrowaway wrote: post #4

One thing I don’t get is how blocking is implemented once you have basic mutual exclusion working? Lets say you try to take the lock, but you spin, waiting for it. But say in your OS now you want the thread to go to sleep until it’s available.. how is actually implemented without spinning and using CPU?

Your program has to use a kernel level synchronisation primitive that supports blocking by sleeping, like a pipe, if you don't want to spin.

Re: A Close Look at a Spinlock

#25

Post by monocasa »

dataflow wrote: post #22
monocasa wrote: post #19

Earlier quoted context omitted.

Oh jeeze, I don't think there'd be anything simple about having to divine facts about user space by the code flow graph near the interrupted instruction on basically every thread switch.

You don't need to worry about the CFG here, a spinlock is literally just a ~4-instruction loop (or a few more, depending on the form you use). All you need is to handle a few common codegen patterns. Like if you see the instruction pointer in the middle of a mov + xchg + test + jne sequence then you know it's a spinlock. If you don't detect it in some canonical form then you're back where we are now; whatever. It's n…

The issue with spin locks isn't the lock sequence itself, it's the code between it being locked and unlocked.

Re: A Close Look at a Spinlock

#26

Post by dataflow »

monocasa wrote: post #25
dataflow wrote: post #22

Earlier quoted context omitted.

You don't need to worry about the CFG here, a spinlock is literally just a ~4-instruction loop (or a few more, depending on the form you use). All you need is to handle a few common codegen patterns. Like if you see the instruction pointer in the middle of a mov + xchg + test + jne sequence then you know it's a spinlock. If you don't detect it in some canonical form then you're back where we are now; whatever. It's n…

The issue with spin locks isn't the lock sequence itself, it's the code between it being locked and unlocked.

I'm not sure which issue you're referring to, but the one I was trying to address was the one above about the spinning itself causing a priority inversion: "you now have a descheduled thread that owns the lock and a spinning thread waiting to acquire it, which is a recipe for priority inversion."

Re: A Close Look at a Spinlock

#27

Post by monocasa »

dataflow wrote: post #26
monocasa wrote: post #25

Earlier quoted context omitted.

The issue with spin locks isn't the lock sequence itself, it's the code between it being locked and unlocked.

I'm not sure which issue you're referring to, but the one I was trying to address was the one above about the spinning itself causing a priority inversion: "you now have a descheduled thread that owns the lock and a spinning thread waiting to acquire it, which is a recipe for priority inversion."

A) it's not just a priority inversion. The problem happens with simple round robin schedulers too.

B) The problem is the descheduled thread which has the lock and isn't in the lock sequence. Simply killing the time slice of the spinning thread without knowing what it's waiting on may lead to even worse behavior.

The answer here is simple: just don't use pure spinlocks if you can be preempted.

Re: A Close Look at a Spinlock

#28

Post by dataflow »

monocasa wrote: post #27
dataflow wrote: post #26

Earlier quoted context omitted.

I'm not sure which issue you're referring to, but the one I was trying to address was the one above about the spinning itself causing a priority inversion: "you now have a descheduled thread that owns the lock and a spinning thread waiting to acquire it, which is a recipe for priority inversion."

A) it's not just a priority inversion. The problem happens with simple round robin schedulers too. B) The problem is the descheduled thread which has the lock and isn't in the lock sequence. Simply killing the time slice of the spinning thread without knowing what it's waiting on may lead to even worse behavior. The answer here is simple: just don't use pure spinlocks if you can be preempted.

> it's not just a priority inversion.

Did I claim it was...?

> Simply killing the time slice of the spinning thread without knowing what it's waiting on may lead to even worse behavior.

It's not obvious to me how likely this is compared to the other case, but if you're trying to make a case for why a kernel doing that would result in worse behavior in typical cases, it would probably help to explain this.

> The answer here is simple: just don't use pure spinlocks if you can be preempted.

I don't get why you're arguing with me on this. I wasn't telling anyone to use spinlocks, nor claiming this is the one and only problem with spinlocks. I was just saying a kernel could be a little smarter about a particular case by examining the instruction sequence.

Re: A Close Look at a Spinlock

#29

Post by jlokier »

dataflow wrote: post #15
lovecg wrote: post #14

Earlier quoted context omitted.

True spinlocks in user space are rarely a good idea. You would use a spinlock in the first place because you assume that the critical section is short, but the kernel often gets in the way of that assumption. The thread in the critical section can run out of its time slice, or there’s an interrupt etc. etc. And once this happens, you now have a descheduled thread that owns the lock and a spinning thread waiting to ac…

Spins are so short and well-defined that I wonder why the kernel doesn't just examine a handful of instructions around the program counter and guess if the thread is spinning or not before scheduling it for another time slice. Seems like a really nice and simple kind of heuristic to implement.

Your idea works well for other kinds of more abstract critical sections too, such as code regions where a garbage collection should be temporarily deferred.

Or in embedded systems where code is running at supervisor level, regions where an interrupt should be deferred, thereby allowing interrupt-disable and interrupt-enable instructions to be avoided.

An alternative which is reasonably fast on modern CPUs is to have a spinlock implementation in the kernel VDSO (or equivalent).

Something a bit like that was done in uCLinux for old ARMs, except instead of a spinlock, they put atomic compare-and-swap in the VDSO, as the CPU didn't have an instruction for that. The kernel checked the userspace address on interrupts, and altered the PC register to redo the compare if the sequence was interrupted.

So that didn't extend the timeslice to allow the operation to complete. Instead it unwound the operation to ensure correct semantics. With a spinlock/mutex combination, cutting short the spinning phase when the task is descheduled by the kernel would be similar, and would allow the "normal" spin count to be unlimited.

Re: A Close Look at a Spinlock

#30

Post by munch117 »

dataflow wrote: post #28
monocasa wrote: post #27

Earlier quoted context omitted.

A) it's not just a priority inversion. The problem happens with simple round robin schedulers too. B) The problem is the descheduled thread which has the lock and isn't in the lock sequence. Simply killing the time slice of the spinning thread without knowing what it's waiting on may lead to even worse behavior. The answer here is simple: just don't use pure spinlocks if you can be preempted.

> it's not just a priority inversion. Did I claim it was...? > Simply killing the time slice of the spinning thread without knowing what it's waiting on may lead to even worse behavior. It's not obvious to me how likely this is compared to the other case, but if you're trying to make a case for why a kernel doing that would result in worse behavior in typical cases, it would probably help to explain this. > The answe…

Your idea doesn't solve the problem. By the time the lock acquirer is pre-empted and the kernel has a chance to do something clever, a significant fraction of a timeslice has already been wasted.
Post reply on HN