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: <20081119212142.GG6753@linux.vnet.ibm.com>
Date:	Wed, 19 Nov 2008 13:21:42 -0800
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	Eric Dumazet <dada1@...mosbay.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

On Wed, Nov 19, 2008 at 09:39:57PM +0100, Eric Dumazet wrote:
> 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

With Arnaldo's change -- probably should prototype and test to find
the other inevitable bugs.  :-/

							Thanx, Paul
--
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