lkml.org 
[lkml]   [2018]   [Dec]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 3/3] epoll: use rwlock in order to reduce ep_poll_callback() contention
On 2018-12-13 12:19, Andrea Parri wrote:
> 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. ;-)

Sure thing. Will extend the comments.

--
Roman

\
 
 \ /
  Last update: 2018-12-13 13:19    [W:0.254 / U:0.636 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site