Re: [PATCH 1/3] rcu: Introduce hlist_nulls variant of hlist

[Eric Dumazet <dada1@cosmosbay.com>]

Paul E. McKenney a écrit :
> On Wed, Nov 19, 2008 at 06:53:20PM +0100, Eric Dumazet wrote:
>> Paul E. McKenney a écrit :
>>>> +
>>>> +/**
>>>> + * hlist_nulls_del_init_rcu - deletes entry from hash list with 
>>>> re-initialization
>>>> + * @n: the element to delete from the hash list.
>>>> + *
>>>> + * Note: hlist_nulls_unhashed() on the node return true after this. It 
>>>> is
>>>> + * useful for RCU based read lockfree traversal if the writer side
>>>> + * must know if the list entry is still hashed or already unhashed.
>>>> + *
>>>> + * In particular, it means that we can not poison the forward pointers
>>>> + * that may still be used for walking the hash list and we can only
>>>> + * zero the pprev pointer so list_unhashed() will return true after
>>>> + * this.
>>>> + *
>>>> + * The caller must take whatever precautions are necessary (such as
>>>> + * holding appropriate locks) to avoid racing with another
>>>> + * list-mutation primitive, such as hlist_nulls_add_head_rcu() or
>>>> + * hlist_nulls_del_rcu(), running on this same list.  However, it is
>>>> + * perfectly legal to run concurrently with the _rcu list-traversal
>>>> + * primitives, such as hlist_nulls_for_each_entry_rcu().
>>>> + */
>>>> +static inline void hlist_nulls_del_init_rcu(struct hlist_nulls_node *n)
>>>> +{
>>>> +	if (!hlist_nulls_unhashed(n)) {
>>>> +		__hlist_nulls_del(n);
>>>> +		n->pprev = NULL;
>>>> +	}
>>>> +}
>>> The point here is to allow an RCU reader to grab the update-side lock
>>> while holding a reference to an hlist_nulls_node, and then be able to
>>> blindly call hlist_nulls_del_init_rcu() without having to do any complex
>>> check to see if the element has already been deleted?
>>> But this only works if each free operation waits for a grace period.
>>> If using SLAB_DESTROY_BY_RCU, the would-be deleter still needs to
>>> revalidate after grabbing the update-side lock, right?  Hmmm...
>> <start a brain refresh cycle>
>>  <read again your questions>
>>    Tilt... 
>>
>> hlist_nulls_del_init_rcu() is only used by a writer, exactly
>> like hlist_del_init_rcu().
>> I see nothing special about SLAB_DESTROY_BY_RCU here.
>>
>> static inline void hlist_del_init_rcu(struct hlist_node *n)
>> {
>>        if (!hlist_unhashed(n)) {
>>                __hlist_del(n);
>>                n->pprev = NULL;
>>        }
>> }
> 
> Not a problem, as you don't use it the way I was thinking.
> 
> For whatever it is worth, here is a more complete use case, on the
> off-chance that it becomes useful some time:
> 
> 	retry:
> 	rcu_read_lock();
> 	hlist_nulls_for_each_entry_rcu(tpos, pos, head, hn_node) {
> 		if (!(curgen = still_valid(tpos)))
> 			goto retry;
> 		if (needs_deletion(tpos)) {
> 			spin_lock(&update_side_lock);
> 			if (still_valid(tpos) == curgen)
> 				hlist_nulls_del_init_rcu(pos);
> 			spin_unlock(&update_side_lock);
> 		}
> 	}
> 	rcu_read_unlock();
> 
> This approach requires that the key and a generation number be encoded
> into a single word, and that the generation number be changed on each
> allocation and on each free.

Hum, we should add this template in Documentation/RCU  I guess

Thanks