Re: [PATCH 01/11] qspinlock: A simple generic 4-byte queue spinlock

[Peter Zijlstra]

On Mon, Jun 16, 2014 at 04:49:18PM -0400, Konrad Rzeszutek Wilk wrote:
> > Index: linux-2.6/kernel/locking/mcs_spinlock.h
> > ===================================================================
> > --- linux-2.6.orig/kernel/locking/mcs_spinlock.h
> > +++ linux-2.6/kernel/locking/mcs_spinlock.h
> > @@ -17,6 +17,7 @@
> >  struct mcs_spinlock {
> >  	struct mcs_spinlock *next;
> >  	int locked; /* 1 if lock acquired */
> > +	int count;
> 
> This could use a comment.

like so?

	int count; /* nesting count, see qspinlock.c */


> > +static inline u32 encode_tail(int cpu, int idx)
> > +{
> > +	u32 tail;
> > +
> > +	tail  = (cpu + 1) << _Q_TAIL_CPU_OFFSET;
> > +	tail |= idx << _Q_TAIL_IDX_OFFSET; /* assume < 4 */
> 
> Should there an
> 
> ASSSERT (idx < 4)
> 
> just in case we screw up somehow (I can't figure out how, but
> that is partially why ASSERTS are added).

#ifdef CONFIG_DEBUG_SPINLOCK
	BUG_ON(idx > 3);
#endif

might do, I suppose.

> > +/**
> > + * queue_spin_lock_slowpath - acquire the queue spinlock
> > + * @lock: Pointer to queue spinlock structure
> > + * @val: Current value of the queue spinlock 32-bit word
> > + *
> > + * (queue tail, lock bit)
> 
> Except it is not a lock bit. It is a lock uint8_t.

It is indeed, although that's an accident of implementation. I could do
s/bit// and not mention the entire storage angle at all?

> Is the queue tail at this point the composite of 'cpu|idx'?

Yes, as per {en,de}code_tail() above.

> > + *
> > + *              fast      :    slow                                  :    unlock
> > + *                        :                                          :
> > + * uncontended  (0,0)   --:--> (0,1) --------------------------------:--> (*,0)
> > + *                        :       | ^--------.                    /  :
> > + *                        :       v           \                   |  :
> > + * uncontended            :    (n,x) --+--> (n,0)                 |  :
> 
> So many CPUn come in right? Is 'n' for the number of CPUs?

Nope, 'n' for any one specific tail, in particular the first one to
arrive. This is the 'uncontended queue' case as per the label, so we
need a named value for the first, in order to distinguish between the
state to the right (same tail, but unlocked) and the state below
(different tail).

> > + *   queue                :       | ^--'                          |  :
> > + *                        :       v                               |  :
> > + * contended              :    (*,x) --+--> (*,0) -----> (*,1) ---'  :
> > + *   queue                :         ^--'                             :
> 
> And here um, what are the '*' for? Are they the four different
> types of handlers that can be nested? So task, sofitrq, hardisk, and
> nmi?

'*' as in wildcard, any tail, specifically not 'n'.

> > +void queue_spin_lock_slowpath(struct qspinlock *lock, u32 val)
> > +{
> > +	struct mcs_spinlock *prev, *next, *node;
> > +	u32 new, old, tail;
> > +	int idx;
> > +
> > +	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
> > +
> > +	node = this_cpu_ptr(&mcs_nodes[0]);
> > +	idx = node->count++;
> 
> If this is the first time we enter this, wouldn't idx end up
> being 1?

Nope, postfix ++ returns first and increments later.

> > +	tail = encode_tail(smp_processor_id(), idx);
> > +
> > +	node += idx;
> 
> Meaning we end up skipping the 'mcs_nodes[0]' one altogether - even
> on the first 'level' (task, softirq, hardirq, nmi)? Won't that
> cause us to blow past the array when we are nested at the nmi
> handler?

Seeing how its all static storage, which is automagically initialized to
0, combined with the postfix ++ (as opposed to the prefix ++) we should
be getting 0 here.

> > +	node->locked = 0;
> > +	node->next = NULL;
> > +
> > +	/*
> > +	 * trylock || xchg(lock, node)
> > +	 *
> > +	 * 0,0 -> 0,1 ; trylock
> > +	 * p,x -> n,x ; prev = xchg(lock, node)
> 
> I looked at that for 10 seconds and I was not sure what you meant.
> Is this related to the MCS document you had pointed to? It would help
> if you mention that the comments follow the document. (But they
> don't seem to)
> 
> I presume what you mean is that if we are the next after the
> lock-holder we need only to update the 'next' (or the
> composite value of smp_processor_idx | idx) to point to us.
> 
> As in, swap the 'L' with 'I' (looking at the doc)

They are the 'tail','lock' tuples, so this composite atomic operation
completes either:

  0,0 -> 0,1  -- we had no tail, not locked; into: no tail, locked.

OR

  p,x -> n,x  -- tail was p; into: tail is n; preserving locked.

> > +	 */
> > +	for (;;) {
> > +		new = _Q_LOCKED_VAL;
> > +		if (val)
> 
> Could you add a comment here, like this:
> 
> /*
>  * N.B. Initially 'val' will have some value (as we are called
>  * after the _Q_LOCKED_VAL could not be set by queue_spin_lock).
>  * But on subsequent iterations, either the lock holder will
>  * decrement the val (queue_spin_unlock - to zero) and we
>  * needn't to record our status in the queue as we have set the
>  * Q_LOCKED_VAL (new) and are the lock holder. Or we are next
>  * in line and need to record our 'next' (aka, smp_processor_id() | idx)
>  * position. */
>  */

The idea was that:

  0,0 -> 0,1
  p,x -> n,x

Completely covers what this composite atomic does.

> > +			new = tail | (val & _Q_LOCKED_MASK);
> > +
> > +		old = atomic_cmpxchg(&lock->val, val, new);
> > +		if (old == val)
> > +			break;
> > +
> > +		val = old;
> > +	}
> > +
> > +	/*
> > +	 * we won the trylock; forget about queueing.
> > +	 */
> > +	if (new == _Q_LOCKED_VAL)
> > +		goto release;
> > +
> > +	/*
> > +	 * if there was a previous node; link it and wait.
> > +	 */
> > +	if (old & ~_Q_LOCKED_MASK) {
> > +		prev = decode_tail(old);
> > +		ACCESS_ONCE(prev->next) = node;
> > +
> > +		arch_mcs_spin_lock_contended(&node->locked);
> > +	}
> > +
> > +	/*
> > +	 * we're at the head of the waitqueue, wait for the owner to go away.
> > +	 *
> > +	 * *,x -> *,0
> > +	 */
> > +	while ((val = atomic_read(&lock->val)) & _Q_LOCKED_MASK)
> > +		cpu_relax();
> > +
> > +	/*
> > +	 * claim the lock:
> > +	 *
> > +	 * n,0 -> 0,1 : lock, uncontended
> > +	 * *,0 -> *,1 : lock, contended
> > +	 */
> > +	for (;;) {
> > +		new = _Q_LOCKED_VAL;
> > +		if (val != tail)
> > +			new |= val;
> 
> You lost me here. If we are at the head of the queue, and the owner
> has called queue_spin_unlock (hence made us get out of the 'val = atomic_read'
> loop, how can val != tail?

Remember:

> > +	tail = encode_tail(smp_processor_id(), idx);

So if value != tail, that means the tail pointer doesn't point to us
anymore, another cpu/idx queued itself and is now last.

> I suspect it has something to do with the comment, but I am still unsure
> what it means.
> 
> Could you help a bit in explaining it in English please?

(refer to the state diagram, if we count states left->right,
top->bottom, then this is: 5->2 or 7->8

 n,0 -> 0,1:

   the lock is free and the tail points to the first queued; this means
   that unqueueing implies wiping the tail, at the same time, acquire
   the lock.

 *,0 -> *,1:

   the lock is free and the tail doesn't point to the first queued; this
   means that unqueueing doesn't touch the tail pointer but only sets
   the lock.

> > +
> > +		old = atomic_cmpxchg(&lock->val, val, new);
> > +		if (old == val)
> > +			break;
> > +
> > +		val = old;
> > +	}
> > +
> > +	/*
> > +	 * contended path; wait for next, release.
> > +	 */
> > +	if (new != _Q_LOCKED_VAL) {
> 
> Hm, wouldn't it be just easier to do a 'goto restart' where
> restart label points at the first loop statement? Ah never
> mind - we have already inserted ourselves in the previous's
> node.
> 
> But that is confusing - we have done: "prev->next = node;"
> 
> And then exited out of 'val = atomic_read(&lock->val))' which
> suggests that queue_spin_unlock has called us. How can we be
> contended again?

We're not contended again; we're in the 'contended queued' case, which
means that 'tail' didn't point to us anymore, in that case, we must kick
our next node such that it will now drop out of
arch_mcs_spin_lock_contended() and goes wait on the 'locked' state.

So what we do here is wait for 'node->next' to be set; it might still be
NULL if the other cpu is between:

  prev = xchg(lock->tail, node);

and:

  prev->next = node;

Once we observe the next node, we call arch_mcs_spin_unlock_contended()
on it, which sets its mcs_spinlock::locked and makes the new 'top of
queue' drop out of arch_mcs_spin_lock_contended and spin on the 'locked'
state as said above.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/