Re: pserialize(9) vs. TAILQ

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

On 19 Nov, 2014, at 00:34 , Masao Uebayashi <uebayasi%gmail.com@localhost> wrote:
> On Wed, Nov 19, 2014 at 1:05 AM, Dennis Ferguson
> <dennis.c.ferguson%gmail.com@localhost> wrote:
>> 
>> On 18 Nov, 2014, at 22:13 , Masao Uebayashi <uebayasi%gmail.com@localhost> wrote:
>>> In the TAILQ case, where readers iterate a list by TAILQ_FOREACH(),
>>> TAILQ_REMOVE() is safely used as the update operation, because:
>>> 
>>> - Readers only see tqe_next in TAILQ_FOREACH(), and
>>> - Pointer assignment (done in TAILQ_REMOVE()) is atomic.
>>> 
>>> If this is correct, pserialize(9) should be updated to be clearer;
>>> probably this TAILQ example is worth being added there.
>> 
>> I don't think TAILQ is a good example for this.  While TAILQ_REMOVE()
>> will work, none of the TAILQ_INSERT_*() macros can be reliably used
>> with concurrent readers so it isn't clear how the list you are
>> removing stuff from could have been built.
> 
> If there is a promise that readers iterate list only in forward
> direction (using tqe_next / tqh_first), the actual update operation by
> writers is the pointer assignment to link the new element.  (Note that
> next pointer in the new element is not visible until it is linked.)
> This is common to any list, and TAILQ is not an exception.

That's very true, but the code is only correct if the writes occur
in the order the C code has them written (i.e. tqe_next in the
new element is written before writing the tqe_next of the existing
list element to point at it).  To ensure the compiler or the
cache hardware doesn't reorder those writes it needs a write barrier
inserted to enforce the order as written.

Making sure there are memory barriers where they are needed is the
hardest part of writing data structure update code designed to operate
with concurrent readers, since the C code still looks perfectly correct
without them.

Dennis Ferguson