lkml.org 
[lkml]   [2008]   [Jul]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: Spinlocks: Factor our GENERIC_LOCKBREAK in order to avoid spin with irqs disable
Nick Piggin wrote:
> On Tuesday 08 July 2008 06:14, Jeremy Fitzhardinge wrote:
>
>
>> The other point, of course, is that ticket locks are massive overkill
>> for the problem they're trying to solve.
>>
>
> No they aren't.
>
>
>
>> It's one thing to introduce an
>> element of fairness into spinlocks, its another to impose strict FIFO
>> ordering. It would be enough to make the locks "polite" by preventing a
>> new lock-holder from taking the lock while its under contention.
>> Something like:
>>
>> union lock {
>> unsigned short word;
>> struct { unsigned char lock, count; };
>> };
>>
>> spin_lock: # ebx - lock pointer
>> movw $0x0001, %ax # add 1 to lock, 0 to count
>> xaddw %ax, (%ebx) # attempt to take lock and test user count
>> testw %ax,%ax
>> jnz slow
>>
>> taken: ret
>>
>> # slow path
>> slow: lock incb 1(%ebx) # inc count
>>
>> 1: rep;nop
>> cmpb $0,(%ebx)
>> jnz 1b # wait for unlocked
>>
>> movb $1,%al # attempt to take lock (count already increased)
>> xchgb %al,(%ebx)
>> testb %al,%al
>> jnz 1b
>>
>> lock decb 1(%ebx) # drop count
>> jmp taken
>>
>> spin_unlock:
>> movb $0,(%ebx)
>> ret
>>
>>
>> The uncontended fastpath is similar to the pre-ticket locks, but it
>> refuses to take the lock if there are other waiters, even if the lock is
>> not currently held. This prevents the rapid lock-unlock cycle on one
>> CPU from starving another CPU, which I understand was the original
>> problem tickets locks were trying to solve.
>>
>
> They prevent lots of unfairness and starvation problems. The most
> prominent one (ie. actually observed in Linux) was a single CPU
> being totally starved by N others (to the point where lockup timers
> would kick in).
>

Yep. My understanding was that the specific case was that cpu A was
repeatedly taking and releasing the lock, while other cpus spin waiting
for it, and that the cache coherence logic kept the cacheline owned by A
(presumably because it kept modifying it). Ticket locks work well in
this case because, as you say, it enforces a fairness policy that the
hardware doesn't implement. Are there other cases that ticket locks
help with? Does the algorithm above solve the starvation issue?

> As an aside, these locks you propose are also a lot more costly in
> the contended path. 4 vs 1 atomic operations on the lock cacheline
> is not so great.
>

Yep, that's not great. But it doesn't bounce cache lines around as much
either, so perhaps it doesn't make much difference.

But really, I was being my own devil's advocate, to see if there's some
other lock algorithm which satisfies both the normal ticket-lock case
and the virtualization case.

I have no real objections to ticket locks, so long as I can turn them off ;)

J


\
 
 \ /
  Last update: 2008-07-08 07:59    [W:0.059 / U:5.224 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site