use unfair spinlock when running on hypervisor.

The patch below allows to patch ticket spinlock code to behave similar to old unfair spinlock when hypervisor is detected. After patching unlocked

Quoted 3 lines · Gleb Natapov

The patch below allows to patch ticket spinlock code to behave similar to old unfair spinlock when hypervisor is detected. After patching unlocked

The question is what happens when you have a system with unfair memory and you run the hypervisor on that. There it could be much worse.

Your new code would starve again, right?

There's a reason the ticket spinlocks were added in the first place.

Quoted 8 lines · Andi Kleen

Quoted 3 lines · Gleb Natapov

The patch below allows to patch ticket spinlock code to behave similar to old unfair spinlock when hypervisor is detected. After patching unlocked

The question is what happens when you have a system with unfair memory and you run the hypervisor on that. There it could be much worse.

How much worse performance hit could be?

Quoted 3 lines

Your new code would starve again, right?

Yes, of course it may starve with unfair spinlock. Since vcpus are not always running there is much smaller chance then vcpu on remote memory node will starve forever. Old kernels with unfair spinlocks are running fine in VMs on NUMA machines with various loads.

Quoted 2 lines

There's a reason the ticket spinlocks were added in the first place.

I understand that reason and do not propose to get back to old spinlock on physical HW! But with virtualization performance hit is unbearable.

Quoted 8 lines

Quoted 3 lines

Your new code would starve again, right?

Yes, of course it may starve with unfair spinlock. Since vcpus are not always running there is much smaller chance then vcpu on remote memory node will starve forever. Old kernels with unfair spinlocks are running fine in VMs on NUMA machines with various loads.

Try it on a NUMA system with unfair memory.

Quoted 3 lines

I understand that reason and do not propose to get back to old spinlock on physical HW! But with virtualization performance hit is unbearable.

Extreme unfairness can be unbearable too.

We are running everything on NUMA (since all modern machines are now NUMA).
At what scale do the issues become observable?

Quoted 6 lines

Quoted 4 lines

I understand that reason and do not propose to get back to old spinlock on physical HW! But with virtualization performance hit is unbearable.

Extreme unfairness can be unbearable too.

Well, the question is what happens first. In our experience, vcpu overcommit is a lot more painful. People will never see the NUMA unfairness issue if they can't use kvm due to the vcpu overcommit problem.

Quoted 3 lines · Avi Kivity

We are running everything on NUMA (since all modern machines are now NUMA).
At what scale do the issues become observable?

On Intel platforms it's visible starting with 4 sockets.

Quoted 7 lines

Quoted 7 lines

Quoted 4 lines

I understand that reason and do not propose to get back to old spinlock on physical HW! But with virtualization performance hit is unbearable.

Extreme unfairness can be unbearable too.

Quoted 4 lines

Well, the question is what happens first. In our experience, vcpu overcommit is a lot more painful. People will never see the NUMA unfairness issue if they can't use kvm due to the vcpu overcommit problem.

You really have to address both, if you don't fix them both users will eventually into one of them and be unhappy.

That's definitely the long term plan. I consider Gleb's patch the first step.

Do you have any idea how we can tackle both problems?

Quoted 7 lines · Andi Kleen

Quoted 3 lines · Avi Kivity

We are running everything on NUMA (since all modern machines are now NUMA).
At what scale do the issues become observable?

On Intel platforms it's visible starting with 4 sockets.

Can you recommend a benchmark that shows bad behaviour? I'll run it with

ticket spinlocks and Gleb's patch. I have a 4-way Nehalem-EX, presumably the huge number of threads will magnify the problem even more there.

Do you have any idea how we can tackle both problems?

Quoted 9 lines · Avi Kivity

Quoted 7 lines · Andi Kleen

Quoted 4 lines · Avi Kivity

We are running everything on NUMA (since all modern machines are now NUMA).
At what scale do the issues become observable?

Quoted 5 lines

Quoted 3 lines

On Intel platforms it's visible starting with 4 sockets.

Can you recommend a benchmark that shows bad behaviour? I'll run it with

Pretty much anything with high lock contention.

Quoted 2 lines

Do you have any idea how we can tackle both problems?

Apparently Xen has something, perhaps that can be leveraged (but I haven't looked at their solution in detail)

Otherwise I would probably try to start with a adaptive spinlock that at some point calls into the HV (or updates shared memory?), like john cooper suggested. The tricky part here would be to find the thresholds and fit that state into
paravirt ops and the standard spinlock_t.

There are two separate problems: the more general problem is that the hypervisor can put a vcpu to sleep while holding a lock, causing other vcpus to spin until the end of their time slice. This can only be addressed with hypervisor help.

Quoted 5 lines · Avi Kivity

There are two separate problems: the more general problem is that the hypervisor can put a vcpu to sleep while holding a lock, causing other vcpus to spin until the end of their time slice. This can only be addressed with hypervisor help.

Fyi - I have a early patch ready to address this issue. Basically I am using host-kernel memory (mmap'ed into guest as io-memory via ivshmem driver) to hint host whenever guest is in spin-lock'ed section, which is read by host scheduler to defer preemption.

Guest side:

static inline void spin_lock(spinlock_t *lock)

{
	raw_spin_lock(&lock->rlock);

+ __get_cpu_var(gh_vcpu_ptr)->defer_preempt++;

}

static inline void spin_unlock(spinlock_t *lock)
{

(quoted diff) +1 -0

+	__get_cpu_var(gh_vcpu_ptr)->defer_preempt--;
        raw_spin_unlock(&lock->rlock);

}

Quoted 6 lines

Guest side:

static inline void spin_lock(spinlock_t *lock)

{
	raw_spin_lock(&lock->rlock);

+ __get_cpu_var(gh_vcpu_ptr)->defer_preempt++;

1) __this_cpu_inc() should be faster

2) Isnt a bit late to do this increment _after_
raw_spin_lock(&lock->rlock);

Quoted 5 lines · Avi Kivity

There are two separate problems: the more general problem is that the hypervisor can put a vcpu to sleep while holding a lock, causing other vcpus to spin until the end of their time slice. This can only be addressed with hypervisor help.

Fyi - I have a early patch ready to address this issue. Basically I am using host-kernel memory (mmap'ed into guest as io-memory via ivshmem driver) to hint host whenever guest is in spin-lock'ed section, which is read by host scheduler to defer preemption.

One pathological case where this may actually hurt is routines in guest like flush_tlb_others_ipi() which take a spinlock and then enter a while() loop waiting for other cpus to ack something. In this case, deferring preemption just because guest is in critical section actually hurts! Hopefully the upper bound for deferring preemtion and the fact that such routines may not be frequently hit should help alleviate such situations.

Quoted 4 lines

Fyi - I have a early patch ready to address this issue. Basically I am using host-kernel memory (mmap'ed into guest as io-memory via ivshmem driver) to hint host whenever guest is in spin-lock'ed section, which is read by host scheduler to defer preemption.

Looks like a ni.ce simple way to handle this for the kernel.

However I suspect user space will hit the same issue sooner or later. I assume your way is not easily extensable to futexes?

So do you defer during the whole spinlock region or just during the spin?

I assume the the first?

Quoted 11 lines · Srivatsa Vaddagiri

Quoted 5 lines · Avi Kivity

There are two separate problems: the more general problem is that the hypervisor can put a vcpu to sleep while holding a lock, causing other vcpus to spin until the end of their time slice. This can only be addressed with hypervisor help.

Fyi - I have a early patch ready to address this issue. Basically I am using host-kernel memory (mmap'ed into guest as io-memory via ivshmem driver) to hint host whenever guest is in spin-lock'ed section, which is read by host scheduler to defer preemption.

Looks like a ni.ce simple way to handle this for the kernel.

However I suspect user space will hit the same issue sooner or later. I assume your way is not easily extensable to futexes?

Quoted 5 lines · Avi Kivity

There are two separate problems: the more general problem is that the hypervisor can put a vcpu to sleep while holding a lock, causing other vcpus to spin until the end of their time slice. This can only be addressed with hypervisor help.

Fyi - I have a early patch ready to address this issue. Basically I am using host-kernel memory (mmap'ed into guest as io-memory via ivshmem driver) to hint host whenever guest is in spin-lock'ed section, which is read by host scheduler to defer preemption.

Guest side:

static inline void spin_lock(spinlock_t *lock)

{
	raw_spin_lock(&lock->rlock);

+ __get_cpu_var(gh_vcpu_ptr)->defer_preempt++;
}

static inline void spin_unlock(spinlock_t *lock)
{

(quoted diff) +1 -0

+	__get_cpu_var(gh_vcpu_ptr)->defer_preempt--;
        raw_spin_unlock(&lock->rlock);

}

[similar changes to other spinlock variants]

Quoted 14 lines

Guest side:

static inline void spin_lock(spinlock_t *lock)

{
	raw_spin_lock(&lock->rlock);

+ __get_cpu_var(gh_vcpu_ptr)->defer_preempt++;
}

static inline void spin_unlock(spinlock_t *lock)
{

(quoted diff) +1 -0

+	__get_cpu_var(gh_vcpu_ptr)->defer_preempt--;
        raw_spin_unlock(&lock->rlock);

}

Quoted 1 line

[similar changes to other spinlock variants]

Great, this is a nice way to improve it.

You might want to consider playing with first taking a ticket, and then if we fail to acquire the lock immediately, then increment defer_preempt before we start spinning.

The downside of this would be if we waste all our slice on spinning and then preempted in the critical section. But with ticket locks you can easily see how many entries in the queue in front of you. So you could experiment with starting to defer preempt when we notice we are getting toward the head of the queue.

Have you also looked at how s390 checks if the owning vcpu is running and if so it spins, if not yields to the hypervisor. Something like turning it into an adaptive lock. This could be applicable as well.

Quoted 22 lines · Nick Piggin

Quoted 14 lines

Guest side:

static inline void spin_lock(spinlock_t *lock)

{
	raw_spin_lock(&lock->rlock);

+ __get_cpu_var(gh_vcpu_ptr)->defer_preempt++;
}

static inline void spin_unlock(spinlock_t *lock)
{

(quoted diff) +1 -0

+	__get_cpu_var(gh_vcpu_ptr)->defer_preempt--;
        raw_spin_unlock(&lock->rlock);

}

Quoted 1 line

[similar changes to other spinlock variants]

Great, this is a nice way to improve it.

You might want to consider playing with first taking a ticket, and then if we fail to acquire the lock immediately, then increment defer_preempt before we start spinning.

Quoted 5 lines

The downside of this would be if we waste all our slice on spinning and then preempted in the critical section. But with ticket locks you can easily see how many entries in the queue in front of you. So you could experiment with starting to defer preempt when we notice we are getting toward the head of the queue.

Mm - my goal is to avoid long spin times in the first place (because the owning vcpu was descheduled at an unfortunate time i.e while it was holding a lock). From that sense, I am targetting preemption-defer of lock *holder* rather than of lock acquirer. So ideally whenever somebody tries to grab a lock, it should be free most of the time, it can be held only if the owner is currently running - which means we won't have to spin too long for the lock.

Quoted 3 lines

Have you also looked at how s390 checks if the owning vcpu is running and if so it spins, if not yields to the hypervisor. Something like turning it into an adaptive lock. This could be applicable as well.

I don't think even s390 does adaptive spinlocks. Also afaik s390 zVM does gang scheduling of vcpus, which reduces the severity of this problem very much - essentially lock acquirer/holder are run simultaneously on different cpus all the time. Gang scheduling is on my list of things to look at much later (although I have been warned that its a scalablility nightmare!).

Holding a ticket in the queue is effectively the same as holding the lock, from the pov of processes waiting behind.

The difference of course is that CPU cycles do not directly reduce latency of ticket holders (only the owner). Spinlock critical sections should tend to be several orders of magnitude shorter than context switch times. So if you preempt the guy waiting at the head of the queue, then it's almost as bad as preempting the lock holder.

Quoted 9 lines

Quoted 3 lines

Have you also looked at how s390 checks if the owning vcpu is running and if so it spins, if not yields to the hypervisor. Something like turning it into an adaptive lock. This could be applicable as well.

I don't think even s390 does adaptive spinlocks. Also afaik s390 zVM does gang scheduling of vcpus, which reduces the severity of this problem very much - essentially lock acquirer/holder are run simultaneously on different cpus all the time. Gang scheduling is on my list of things to look at much later (although I have been warned that its a scalablility nightmare!).

It effectively is pretty well an adaptive lock. The spinlock itself doesn't sleep of course, but it yields to the hypervisor if the owner has been preempted. This is pretty close to analogous with Linux adaptive mutexes.

s390 also has the diag9c instruction which I suppose somehow boosts priority of a preempted contended lock holder. In spite of any other possible optimizations in their hypervisor like gang scheduling, diag9c apparently provides quite a large improvement in some cases.

So I think these things are fairly important to look at.

Ok got it - although that approach is not advisable in some cases for ex: when the lock holder vcpu and lock acquired vcpu are scheduled on the same pcpu by the hypervisor (which was experimented with in [1] where they foud a huge hit in perf).

Quoted 8 lines · Nick Piggin

Holding a ticket in the queue is effectively the same as holding the lock, from the pov of processes waiting behind.

The difference of course is that CPU cycles do not directly reduce latency of ticket holders (only the owner). Spinlock critical sections should tend to be several orders of magnitude shorter than context switch times. So if you preempt the guy waiting at the head of the queue, then it's almost as bad as preempting the lock holder.

Ok got it - although that approach is not advisable in some cases for ex: when the lock holder vcpu and lock acquired vcpu are scheduled on the same pcpu by the hypervisor (which was experimented with in [1] where they foud a huge hit in perf).

I agree that in general we should look at deferring preemption of lock acquirer esp when its at "head" as you suggest - I will consider that approach as the next step (want to incrementally progress basically!).

Quoted 10 lines

Quoted 9 lines

Quoted 3 lines

Have you also looked at how s390 checks if the owning vcpu is running and if so it spins, if not yields to the hypervisor. Something like turning it into an adaptive lock. This could be applicable as well.

I don't think even s390 does adaptive spinlocks. Also afaik s390 zVM does gang scheduling of vcpus, which reduces the severity of this problem very much - essentially lock acquirer/holder are run simultaneously on different cpus all the time. Gang scheduling is on my list of things to look at much later (although I have been warned that its a scalablility nightmare!).

Quoted 3 lines

It effectively is pretty well an adaptive lock. The spinlock itself doesn't sleep of course, but it yields to the hypervisor if the owner has been preempted. This is pretty close to analogous with Linux adaptive mutexes.

Oops you are right - sorry should have checked more closely earlier. Given that we may not be able to always guarantee that locked critical sections will not be preempted (ex: when a real-time task takes over), we will need a combination of both approaches (i.e request preemption defer on lock hold path + yield on lock acquire path if owner !scheduled). The advantage of former approach is that it could reduce job turnaround times in most cases (as lock is available when we want or we don't have to wait too long for it).

Quoted 4 lines

s390 also has the diag9c instruction which I suppose somehow boosts priority of a preempted contended lock holder. In spite of any other possible optimizations in their hypervisor like gang scheduling, diag9c apparently provides quite a large improvement in some cases.

Ok - thx for that pointer - will have a look at diag9c.

Quoted 1 line

So I think these things are fairly important to look at.

I agree ..

- vatsa

Quoted 4 lines

Ok got it - although that approach is not advisable in some cases for ex: when the lock holder vcpu and lock acquired vcpu are scheduled on the same pcpu by the hypervisor (which was experimented with in [1] where they foud a huge hit in perf).

Sure but if you had adaptive yielding, that solves that problem.

Quoted 7 lines

Oops you are right - sorry should have checked more closely earlier. Given that we may not be able to always guarantee that locked critical sections will not be preempted (ex: when a real-time task takes over), we will need a combination of both approaches (i.e request preemption defer on lock hold path + yield on lock acquire path if owner !scheduled). The advantage of former approach is that it could reduce job turnaround times in most cases (as lock is available when we want or we don't have to wait too long for it).

Both I think would be good. It might be interesting to talk with the s390 guys and see if they can look at ticket locks and preempt defer techniques too (considering they already do the other half of the equation well).

And they aren't even using ticket spinlocks!!

Quoted 1 line · Nick Piggin

And they aren't even using ticket spinlocks!!

I suppose they simply don't have unfair memory. Makes things easier.

That would certainly be a part of it, I'm sure they have stronger fairness and guarantees at the expense of some performance. We saw the spinlock starvation first on 8-16 core Opterons I think, wheras Altix had been over 1024 cores and POWER7 1024 threads now apparently without reported problems.

So I think actively enforcing fairness at the lock level would be required. Something like if it is detected that a core is not making

Quoted 2 lines · Andi Kleen

Quoted 1 line

Quoted 1 line

Your new code would starve again, right?

Try it on a NUMA system with unfair memory.

We are running everything on NUMA (since all modern machines are now NUMA). At what scale do the issues become observable?

Quoted 3 lines

We are running everything on NUMA (since all modern machines are now NUMA). At what scale do the issues become observable?

My 6-month-old laptop is NUMA? Comes as a surprise to me, and to the perfectly-running NUMA=n kernel I'm running.

Or did you mean a less broad phrase than "all modern machines"?

Quoted 3 lines · Avi Kivity

Quoted 2 lines · Andi Kleen

Quoted 1 line

Quoted 1 line

Your new code would starve again, right?

Try it on a NUMA system with unfair memory.

Quoted 2 lines

We are running everything on NUMA (since all modern machines are now NUMA). At what scale do the issues become observable?

My 6-month-old laptop is NUMA? Comes as a surprise to me, and to the perfectly-running NUMA=n kernel I'm running.

Or did you mean a less broad phrase than "all modern machines"?

Quoted 10 lines · Andi Kleen

Quoted 8 lines

Quoted 3 lines

Your new code would starve again, right?

Yes, of course it may starve with unfair spinlock. Since vcpus are not always running there is much smaller chance then vcpu on remote memory node will starve forever. Old kernels with unfair spinlocks are running fine in VMs on NUMA machines with various loads.

Try it on a NUMA system with unfair memory.

We are running everything on NUMA (since all modern machines are now NUMA). At what scale do the issues become observable?

Quoted 3 lines

Quoted 3 lines

I understand that reason and do not propose to get back to old spinlock on physical HW! But with virtualization performance hit is unbearable.

Quoted 2 lines

Extreme unfairness can be unbearable too.

Well, the question is what happens first. In our experience, vcpu overcommit is a lot more painful. People will never see the NUMA unfairness issue if they can't use kvm due to the vcpu overcommit problem.

What I'd like to see eventually is a short-term-unfair, long-term-fair spinlock. Might make sense for bare metal as well. But it won't be easy to write.

Collecting the contention/usage statistics on a per spinlock basis seems complex. I believe a practical approximation to this are adaptive mutexes where upon hitting a spin time threshold, punt and let the scheduler reconcile fairness.

Quoted 4 lines

Collecting the contention/usage statistics on a per spinlock basis seems complex. I believe a practical approximation to this are adaptive mutexes where upon hitting a spin time threshold, punt and let the scheduler reconcile fairness.

That would probably work, except: how do you get the adaptive spinlock into a paravirt op without slowing down a standard kernel?

Quoted 5 lines · Andi Kleen

Quoted 4 lines

Collecting the contention/usage statistics on a per spinlock basis seems complex. I believe a practical approximation to this are adaptive mutexes where upon hitting a spin time threshold, punt and let the scheduler reconcile fairness.

Quoted 3 lines

That would probably work, except: how do you get the adaptive spinlock into a paravirt op without slowing down a standard kernel?

It only ever comes into play in the case where the spinlock is contended anyway -- surely it shouldn't be _that_ much of a performance issue?

What I'd like to see eventually is a short-term-unfair, long-term-fair spinlock. Might make sense for bare metal as well. But it won't be easy to write.