futex code and barriers

futex code and barriers

[Peter Zijlstra]

Hi All,

While looking through the futex code I stumbled upon the following bit:

kernel/futex.c:

	/* add_wait_queue is the barrier after __set_current_state. */
	__set_current_state(TASK_INTERRUPTIBLE);
	add_wait_queue(&q.waiters, &wait);


However,

void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
	unsigned long flags;

	wait->flags &= ~WQ_FLAG_EXCLUSIVE;
	spin_lock_irqsave(&q->lock, flags);
	__add_wait_queue(q, wait);
	spin_unlock_irqrestore(&q->lock, flags);
}

static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
{
	list_add(&new->task_list, &head->task_list);
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}

static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

Non of which implies a full barrier.

Re: futex code and barriers

[Jiri Kosina]

On Tue, 29 Apr 2008, Peter Zijlstra wrote:

> While looking through the futex code I stumbled upon the following bit:
> kernel/futex.c:
> 	/* add_wait_queue is the barrier after __set_current_state. */
> 	__set_current_state(TASK_INTERRUPTIBLE);
> 	add_wait_queue(&q.waiters, &wait);
> However,
> void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
> {
> 	unsigned long flags;
> 
> 	wait->flags &= ~WQ_FLAG_EXCLUSIVE;
> 	spin_lock_irqsave(&q->lock, flags);
> 	__add_wait_queue(q, wait);
> 	spin_unlock_irqrestore(&q->lock, flags);
> }
[ ... ]
> Non of which implies a full barrier.

Well I am probably missing the point, but what about the lock and unlock 
of the spinlock?

-- 
Jiri Kosina
SUSE Labs

Re: futex code and barriers

[Peter Zijlstra]

On Tue, 2008-04-29 at 14:43 +0200, Jiri Kosina wrote:
> On Tue, 29 Apr 2008, Peter Zijlstra wrote:
> 
> > While looking through the futex code I stumbled upon the following bit:
> > kernel/futex.c:
> > 	/* add_wait_queue is the barrier after __set_current_state. */
> > 	__set_current_state(TASK_INTERRUPTIBLE);
> > 	add_wait_queue(&q.waiters, &wait);
> > However,
> > void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
> > {
> > 	unsigned long flags;
> > 
> > 	wait->flags &= ~WQ_FLAG_EXCLUSIVE;
> > 	spin_lock_irqsave(&q->lock, flags);
> > 	__add_wait_queue(q, wait);
> > 	spin_unlock_irqrestore(&q->lock, flags);
> > }
> [ ... ]
> > Non of which implies a full barrier.
> 
> Well I am probably missing the point, but what about the lock and unlock 
> of the spinlock?

See Documentation/memory-barriers.txt

quoted:

---

 (1) LOCK operation implication:

     Memory operations issued after the LOCK will be completed after the LOCK
     operation has completed.

     Memory operations issued before the LOCK may be completed after the LOCK
     operation has completed.

 (2) UNLOCK operation implication:

     Memory operations issued before the UNLOCK will be completed before the
     UNLOCK operation has completed.

     Memory operations issued after the UNLOCK may be completed before the
     UNLOCK operation has completed.

 (3) LOCK vs LOCK implication:

     All LOCK operations issued before another LOCK operation will be completed
     before that LOCK operation.

 (4) LOCK vs UNLOCK implication:

     All LOCK operations issued before an UNLOCK operation will be completed
     before the UNLOCK operation.

     All UNLOCK operations issued before a LOCK operation will be completed
     before the LOCK operation.

 (5) Failed conditional LOCK implication:

     Certain variants of the LOCK operation may fail, either due to being
     unable to get the lock immediately, or due to receiving an unblocked
     signal whilst asleep waiting for the lock to become available.  Failed
     locks do not imply any sort of barrier.

Therefore, from (1), (2) and (4) an UNLOCK followed by an unconditional LOCK is
equivalent to a full barrier, but a LOCK followed by an UNLOCK is not.

[!] Note: one of the consequences of LOCKs and UNLOCKs being only one-way
    barriers is that the effects of instructions outside of a critical section
    may seep into the inside of the critical section.

A LOCK followed by an UNLOCK may not be assumed to be full memory barrier
because it is possible for an access preceding the LOCK to happen after the
LOCK, and an access following the UNLOCK to happen before the UNLOCK, and the
two accesses can themselves then cross:

        *A = a;
        LOCK
        UNLOCK
        *B = b;

may occur as:

        LOCK, STORE *B, STORE *A, UNLOCK

Locks and semaphores may not provide any guarantee of ordering on UP compiled
systems, and so cannot be counted on in such a situation to actually achieve
anything at all - especially with respect to I/O accesses - unless combined
with interrupt disabling operations.

See also the section on "Inter-CPU locking barrier effects".


As an example, consider the following:

        *A = a;
        *B = b;
        LOCK
        *C = c;
        *D = d;
        UNLOCK
        *E = e;
        *F = f;

The following sequence of events is acceptable:

        LOCK, {*F,*A}, *E, {*C,*D}, *B, UNLOCK

        [+] Note that {*F,*A} indicates a combined access.

But none of the following are:

        {*F,*A}, *B,    LOCK, *C, *D,   UNLOCK, *E
        *A, *B, *C,     LOCK, *D,       UNLOCK, *E, *F
        *A, *B,         LOCK, *C,       UNLOCK, *D, *E, *F
        *B,             LOCK, *C, *D,   UNLOCK, {*F,*A}, *E

Re: futex code and barriers

[Oleg Nesterov]

On 04/29, Peter Zijlstra wrote:
> Hi All,
> 
> While looking through the futex code I stumbled upon the following bit:
> 
> kernel/futex.c:
> 
> 	/* add_wait_queue is the barrier after __set_current_state. */

As for me, the comment is very confusing at least.

> 	__set_current_state(TASK_INTERRUPTIBLE);
> 	add_wait_queue(&q.waiters, &wait);

Not sure I understand this code, but probably it is correct.

Yes, add_wait_queue() is not a barrier, and both __set_current_state()
and the "!plist_node_empty()" check below can leak into the
add_wait_queue's critical section.

But wake_futex()->wake_up_all() has to lock/unlock the same q->lock,
so I think we can't miss the event.

IOW, when wake_futex()->wake_up_all() takes q->lock, it must see
TASK_INTERRUPTIBLE.

If wake_futex() takes q->lock before us, we must see the result
of plist_del() after add_wait_queue() (more precisely, after
add_wait_queue()->spin_lock(q->lock).

But I'd like to know maintainer's opinion, I don't trust myself ;)

Oleg.