Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.albasani.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: Alexander Terekhov <terekhov@web.de>
Newsgroups: comp.programming.threads
Subject: Re: usage of vyukov's mpsc queue
Date: Wed, 21 Sep 2011 14:02:14 +0200
Organization: A noiseless patient Spider
Lines: 95
Message-ID: <4E79D246.E338E050@web.de>
References: <3b312755-24d8-4505-8cfe-1644c458c4d5@j1g2000yqn.googlegroups.com> <4E79BA45.B3622870@web.de> <2011092106580817537-ephisinowitz@yahoocom>
Reply-To: terekhov@web.de
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Injection-Info: mx04.eternal-september.org; posting-host="MCbSEzW5qwGLFMNXJh39IQ"; logging-data="15157"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19Y5YhE6MZzc3q11ymUdedpwkIDLgoAvDQ="
X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U)
X-Accept-Language: en
Cancel-Lock: sha1:Ofh1A+t8OTUmSobx7KjvK5+NnGs=
Xref: x330-a1.tempe.blueboxinc.net comp.programming.threads:586


Ephi Sinowitz wrote:
[...]
> Why I don't see any contention here. Just to ensure we are talking
> about the same thing. (The link in the original post was a little off.)
> http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue

You posted

<quote>

void MPSC_Queue::push(void* item)
{
    item->next = NULL;
    void* old_head = InterlockedExchangePointer((void *volatile
*)&m_head, item);
    // BLOCK POINT
    old_head->next = item;  // Do I need to ensure this is visible to
the consumer thread?
}

</quote>

which looks like mpscq_push() of non-intrusive version posted at

http://groups.google.com/group/lock-free/browse_thread/thread/55df71b87acb8201

<quote>

struct mpscq_node_t 
{ 
    mpscq_node_t* volatile  next; 
    void*                   state; 

}; 

struct mpscq_t 
{ 
    mpscq_node_t* volatile  head; 
    mpscq_node_t*           tail; 

}; 

void mpscq_create(mpscq_t* self, mpscq_node_t* stub) 
{ 
    stub->next = 0; 
    self->head = stub; 
    self->tail = stub; 

} 

void mpscq_push(mpscq_t* self, mpscq_node_t* n) 
{ 
    n->next = 0; 
    mpscq_node_t* prev = XCHG(&self->head, n); // serialization-point 
wrt producers 
    prev->next = n; // serialization-point wrt consumer 

} 

mpscq_node_t* mpscq_pop(mpscq_t* self) 
{ 
    mpscq_node_t* tail = self->tail; 
    mpscq_node_t* next = tail->next; // serialization-point wrt 
producers 
    if (next) 
    { 
        self->tail = next; 
        tail->state = next->state; 
        return tail; 
    } 
    return 0; 

} 

</quote>

Intrusive version aside for a moment, lets start with non-intrusive
version....

To repeat:

You need to make prev->next = n store atomic-release store.

Consumer's next = tail->next load must be atomic-acquire load.

Producer's RMW can be totally relaxed with respect to memory barriers if
implemented as load-reserve/store-conditional or CAS loop (making
subsequent stores control-dependent).

OTOH, for loopless XCHG-style RMW you need to ensure that it has acquire
semantics (InterlockedExchangePointerAcquire in MS terms).

regards,
alexander.