Re: Spinlocks: Factor our GENERIC_LOCKBREAK in order to avoid spin with irqs disable

[Jeremy Fitzhardinge <jeremy@goop.org>]

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