Re: [Qemu-devel] [RFC PATCH] Introduce RCU-enabled DQs (v2)

[Paolo Bonzini <pbonzini@redhat.com>]

Il 25/08/2013 15:06, Mike Day ha scritto:
> 
> Paolo Bonzini <pbonzini@redhat.com> writes:
> 
>> Just a couple of questions, one of them on the new macro...
>>
>>> +/* prior to publication of the elm->prev->next value, some list
>>> + * readers  may still see the removed element when following
>>> + * the antecedent's next pointer.
>>> + */
>>> +
>>> +#define QLIST_REMOVE_RCU(elm, field) do {                       \
>>> +    if ((elm)->field.le_next != NULL) {                         \
>>> +       (elm)->field.le_next->field.le_prev =                    \
>>> +        (elm)->field.le_prev;                                   \
>>> +    }                                                           \
>>> +    atomic_rcu_set((elm)->field.le_prev, (elm)->field.le_next); \
>>> +} while (/*CONSTCOND*/0)
>>
>> Why is the barrier needed here, but not in Linux's list_del_rcu?
>>
>> I think it is not needed because all involved elements have already been
>> published and just have their pointers shuffled.
> 
> I read this as more than shuffling pointers. The intent here is 
> that the previous element's next pointer is being updated to omit the
> current element from the list.

Sorry if I were too concise... by "having their pointers shuffled" I
meant that all assigned values were already present in the list.  The
important point is that no new node has to be published in the list.

The importance of the write barrier with RCU is to ensure an item is
fully ready before it is added to a data structure.  For this to be
true, all writes to the item must be complete before a pointer to the
item is first written in memory.  Here, the pointer had already been
written in memory, so there's nothing to complete.

> atomic_set always deferences the pointer passed to it, and
> (field)->le_pre is a double pointer. So looking at the macro:
> 
> #define atomic_set(ptr, i) ((*(__typeof__(*ptr) *volatile) (ptr)) = (i))
> 
> It translates to: 
> 
> ( ( * (__typeof(*elm->field.le_prev) *volatile) (elm)->field.le_prev)  = 
> elm->field.le_next; ) 
> 
> Which is: 
> 
>  *((struct *elm) *volatile)(elm)->field.le_prev = elm->field.le_next; 
> 
> Which is:
> 
> *(elm)->field.le_prev = elm->field.le_next;
> 
> Because field.le_prev is a double pointer that has previously been set
> to &prev (the address of the previous list element) this is assiging the
> *previous* element's next pointer, the way I read it.

Correct.

> The Linux list_del_rcu is dealing with a singly linked list and
> therefore does not set a value in the previous node's element. 

Note that Linux list_head is a circular list; hlist is a singly-linked
list.  list_del_rcu still modifies the previous pointer via
__list_del_entry:

    static inline void __list_del_entry(struct list_head *entry)
    {
        __list_del(entry->prev, entry->next);
    }

    static inline void __list_del(struct list_head * prev,
                                  struct list_head * next)
    {
        next->prev = prev;
        prev->next = next;
    }


> But I'm still unclear on whether or not the memory barrier is needed
> because the deleted element won't be reclaimed right away.

Right.  That memory barrier is not needed here, it is included in the
implementation of synchronize_rcu.

Paolo