On Thu, Dec 13, 2018 at 11:13:58AM +0100, Roman Penyaev wrote:
> On 2018-12-12 18:13, Andrea Parri wrote:
> > On Wed, Dec 12, 2018 at 12:03:57PM +0100, Roman Penyaev wrote:
>
> [...]
>
> > > +static inline void list_add_tail_lockless(struct list_head *new,
> > > + struct list_head *head)
> > > +{
> > > + struct list_head *prev;
> > > +
> > > + new->next = head;
> > > +
> > > + /*
> > > + * Initially ->next of a new element must be updated with the head
> > > + * (we are inserting to the tail) and only then pointers are
> > > atomically
> > > + * exchanged. XCHG guarantees memory ordering, thus ->next should
> > > be
> > > + * updated before pointers are actually swapped.
> > > + */
> > > +
> > > + prev = xchg(&head->prev, new);
> > > +
> > > + /*
> > > + * It is safe to modify prev->next and new->prev, because a new
> > > element
> > > + * is added only to the tail and new->next is updated before XCHG.
> > > + */
> >
> > IIUC, you're also relying on "some" ordering between the atomic load
> > of &head->prev above and the store to prev->next below: consider the
> > following snippet for two concurrent list_add_tail_lockless()'s:
> >
> > {Initially: List := H -> A -> B}
> >
> > CPU0 CPU1
> >
> > list_add_tail_lockless(C, H): list_add_tail_lockless(D, H):
> >
> > C->next = H D->next = H
> > prev = xchg(&H->prev, C) // =B prev = xchg(&H->prev, D) // =C
> > B->next = C C->next = D
> > C->prev = B D->prev = C
> >
> > Here, as annotated, CPU0's xchg() "wins" over CPU1's xchg() (i.e., the
> > latter reads the value of &H->prev that the former stored to that same
> > location).
> >
> > As you noted above, the xchg() guarantees that CPU0's store to C->next
> > is "ordered before" CPU0's store to &H->prev.
> >
> > But we also want CPU1's load from &H->prev to be ordered before CPU1's
> > store to C->next, which is also guaranteed by the xchg() (or, FWIW, by
> > the address dependency between these two memory accesses).
> >
> > I do not see what could guarantee "C->next == D" in the end, otherwise.
> >
> > What am I missing?
>
> Hi Andrea,
>
> xchg always acts as a full memory barrier, i.e. mfence in x86 terms. So the
> following statement should be always true, otherwise nothing should work as
> the same code pattern is used in many generic places:
>
> CPU0 CPU1
>
> C->next = H
> xchg(&ptr, C)
> C = xchg(&ptr, D)
> C->next = D
>
>
> This is the only guarantee we need, i.e. make it simplier:
>
> C->next = H
> mfence mfence
> C->next = D
>
> the gurantee that two stores won't reorder. Pattern is always the same: we
> prepare chunk of memory on CPU0 and do pointers xchg, CPU1 sees chunks of
> memory with all stores committed by CPU0 (regardless of CPU1 does loads
> or stores to this chunk).
>
> I am repeating the same thing which you also noted, but I just want to be
> sure that I do not say nonsense. So basically repeating to myself.
>
> Ok, let's commit that. Returning to your question: "I do not see what
> could guarantee "C->next == D" in the end"
>
> At the end of what? Lockless insert procedure (insert to tail) relies only
> on "head->prev". This is the single "place" where we atomically exchange
> list elements and "somehow" chain them. So insert needs only actual
> "head->prev", and xchg provides this guarantees to us.
When all the operations reported in the snippet have completed (i.e.,
executed and propagated to memory).
To rephrase my remark:
I am saying that we do need some ordering between the xchg() and the
program-order _subsequent stores, and implicitly suggesting to write
this down in the comment. As I wrote, this ordering _is provided by
the xchg() itself or by the dependency; so, maybe, something like:
/*
* [...] XCHG guarantees memory ordering, thus new->next is
* updated before pointers are actually swapped and pointers
* are swapped before prev->next is updated.
*/
Adding a snippet, say in the form you reported above, would not hurt
of course. ;-)
Andrea
>
> But there is also a user of the list, who needs to iterate over the list
> or to delete elements, etc, i.e. this user of the list needs list fully
> committed to the memory. This user takes write_lock(). So answering your
> question (if I understood it correctly): at the end write_lock() guarantees
> that list won't be seen as corrupted and updates to the last element, i.e.
> "->next" or "->prev" pointers of the last element are committed and seen
> correctly.
>
> --
> Roman
>
>
>
>
>
