Re: [RFC PATCH 4/6] kernel: faster queue spinlock implementation

[Rik van Riel <riel@redhat.com>]

On 01/22/2013 06:13 PM, Michel Lespinasse wrote:

> Because of these limitations, the MCS queue spinlock implementation does
> not always compare favorably to ticket spinlocks under moderate contention.
>
> This alternative queue spinlock implementation has some nice properties:
>
> - One single atomic operation (xchg) during acquire
> - One single memory store for unlock. No busy looping either.
>    Actually, the unlock is so short that we can just inline it.
> - Same basic API as with the MCS spinlock

There is one thing I do not understand about these locks.

> +static inline void
> +q_spin_unlock(struct q_spinlock *lock, struct q_spinlock_node *node)
> +{
> +	q_spin_unlock_mb();	/* guarantee release store semantics */
> +	ACCESS_ONCE(node->token->wait) = false;
> +	preempt_enable();
> +}

Here you set wait to false, in the CPU-local (on the current CPU)
queue lock token. Afterwards, the same CPU could try to lock another
lock, using the same token...

> +DEFINE_PER_CPU(struct q_spinlock_token *, q_spinlock_token[2]);
> +
> +static inline struct q_spinlock_token *
> +____q_spin_lock(struct q_spinlock *lock,
> +		struct q_spinlock_token **percpu_token)
>   {
> +	/*
> +	 * Careful about reentrancy here - if we are interrupted and the code
> +	 * running in that interrupt tries to get another queue spinlock,
> +	 * it must not use the same percpu_token that we're using here.
> +	 */
> +
> +	struct q_spinlock_token *token, *prev;
> +
> +	token = __this_cpu_read(*percpu_token);
> +	token->wait = true;
> +	prev = xchg(&lock->token, token);
> +	__this_cpu_write(*percpu_token, prev);
> +	while (ACCESS_ONCE(prev->wait))
>   		cpu_relax();
>   	q_spin_lock_mb();	/* guarantee acquire load semantics */
> +	return token;
>   }

Here a CPU trying to take the lock will spin on the previous
CPU's token.

However, the previous CPU can immediately re-use its token.

It looks like it might be possible for the CPU trying to
acquire the lock to miss prev->wait being set to false, and
continue spinning.

If this lock type is widely used, could that lead to a deadlock?

Is there something in your code that guarantees the scenario
I described cannot happen, and I just missed it?