[lttng-dev] [PATCH 01/16] Fix: wfcqueue nonblocking dequeue

[Mathieu Desnoyers]

* Lai Jiangshan (laijs at cn.fujitsu.com) wrote:
> On 11/21/2012 03:40 AM, Mathieu Desnoyers wrote:
> > Failures were not handled in the nonblocking dequeue implementation.
> > 
> > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > ---
> >  urcu/static/wfcqueue.h |   11 +++++++++++
> >  1 file changed, 11 insertions(+)
> > 
> > diff --git a/urcu/static/wfcqueue.h b/urcu/static/wfcqueue.h
> > index 8733771..a284b58 100644
> > --- a/urcu/static/wfcqueue.h
> > +++ b/urcu/static/wfcqueue.h
> > @@ -312,6 +312,8 @@ ___cds_wfcq_dequeue(struct cds_wfcq_head *head,
> >  		return NULL;
> >  
> >  	node = ___cds_wfcq_node_sync_next(&head->node, blocking);
> > +	if (!blocking && node == CDS_WFCQ_WOULDBLOCK)
> > +		return CDS_WFCQ_WOULDBLOCK;
> >  
> >  	if ((next = CMM_LOAD_SHARED(node->next)) == NULL) {
> >  		/*
> > @@ -332,6 +334,15 @@ ___cds_wfcq_dequeue(struct cds_wfcq_head *head,
> >  		if (uatomic_cmpxchg(&tail->p, node, &head->node) == node)
> >  			return node;
> 
> Is it this simpler?
> we had just loaded node->next via "if ((next = CMM_LOAD_SHARED(node->next)) == NULL)"
> 
> 
> +		if (!blocking)
> +			return CDS_WFCQ_WOULDBLOCK
> 
> >  		next = ___cds_wfcq_node_sync_next(node, blocking);
> 
> and remove the following.

So let's see. We have met the condition
  "if ((next = CMM_LOAD_SHARED(node->next)) == NULL) {"

Therefore, it means that it appears, at that point, that the queue has
only one node. So usually, after this test succeeds, we'll have to set
the queue state to empty. There is only one case where this will not be
done: if a concurrent enqueue adds a node between this test and the
cmpxchg that follows. In that case, we'll notice this because cmpxchg
fails, and instead of setting the queue to "empty", we'll simply wait
for enqueue to complete adding the new node, and move head forward.

The approach you propose is to consider that if cmpxchg fails, we
will very likely have to block. Well, that would skip a call to
___cds_wfcq_node_sync_next, and semantically would be still right,
because the only way cmpxchg can fail is if the tail pointer is being
changed concurrently, which would typically make us block.

However, we'd still need to perform "head->node.next = node;" before we
return CDS_WFCQ_WOULDBLOCK, because _cds_wfcq_node_init() has already
set the head next pointer to NULL, and we need to undo that.

Thoughts ?

Thanks,

Mathieu

> 
> > +		/*
> > +		 * In nonblocking mode, if we would need to block to
> > +		 * get node's next, set the head next node pointer
> > +		 * (currently NULL) back to its original value.
> > +		 */
> > +		if (!blocking && next == CDS_WFCQ_WOULDBLOCK) {
> > +			head->node.next = node;
> > +			return CDS_WFCQ_WOULDBLOCK;
> > +		}
> >  	}
> >  
> >  	/*

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com