netdev - Re: [PATCH 1/3] rcu: Introduce hlist

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <4924799D.4010606@cosmosbay.com>
Date:	Wed, 19 Nov 2008 21:39:57 +0100
From:	Eric Dumazet <dada1@...mosbay.com>
To:	paulmck@...ux.vnet.ibm.com
CC:	Corey Minyard <minyard@....org>,
	David Miller <davem@...emloft.net>,
	Stephen Hemminger <shemminger@...tta.com>,
	benny+usenet@...rsen.dk,
	Linux Netdev List <netdev@...r.kernel.org>,
	Christoph Lameter <cl@...ux-foundation.org>,
	Evgeniy Polyakov <zbr@...emap.net>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Christian Bell <christian@...i.com>
Subject: Re: [PATCH 1/3] rcu: Introduce hlist_nulls variant of hlist

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


--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html