Re: [PATCH 1/3] rhashtable: further improve stability of rhashtable_walk

[NeilBrown <neilb@suse.com>]

[-- Attachment #1: Type: text/plain, Size: 3125 bytes --]

On Fri, Jul 06 2018, Paolo Abeni wrote:

> On Fri, 2018-07-06 at 17:11 +1000, NeilBrown wrote:
>> If the sequence:
>>    obj = rhashtable_walk_next(iter);
>>    rhashtable_walk_stop(iter);
>>    rhashtable_remove_fast(ht, &obj->head, params);
>>    rhashtable_walk_start(iter);
>> 
>>  races with another thread inserting or removing
>>  an object on the same hash chain, a subsequent
>>  rhashtable_walk_next() is not guaranteed to get the "next"
>>  object. It is possible that an object could be
>>  repeated, or missed.
>
> The above scenario is very similar to the one I'm running:
>
>    rhashtable_walk_next(iter);
>    rhashtable_walk_stop(iter);     
>    // rhashtable change not yet identified, could be either
>    // remove, insert or even rehash
>    rhashtable_walk_start(iter);
>    rhashtable_walk_next(iter);
>
> but I'm seeing use-after-free there. I'll try this patch to see if
> solves my issue.
>
> Note: the code under test is a pending new patch I'm holding due to the
> above issue, I can send it as RFC to share the code if you think it may
> help.

I'd suggest post it.  I may not get a chance to look at it, but if you
don't post it, then I definitely won't :-)

>
>> @@ -867,15 +866,39 @@ void *rhashtable_walk_next(struct rhashtable_iter *iter)
>>  	bool rhlist = ht->rhlist;
>>  
>>  	if (p) {
>> -		if (!rhlist || !(list = rcu_dereference(list->next))) {
>> -			p = rcu_dereference(p->next);
>> -			list = container_of(p, struct rhlist_head, rhead);
>> -		}
>> -		if (!rht_is_a_nulls(p)) {
>> -			iter->skip++;
>> -			iter->p = p;
>> -			iter->list = list;
>> -			return rht_obj(ht, rhlist ? &list->rhead : p);
>> +		if (!rhlist && iter->p_is_unsafe) {
>> +			/*
>> +			 * First time next() was called after start().
>> +			 * Need to find location of 'p' in the list.
>> +			 */
>> +			struct rhash_head *p;
>> +
>> +			iter->skip = 0;
>> +			rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
>> +				iter->skip++;
>> +				if (p <= iter->p)
>> +					continue;
>
> Out of sheer ignorance, I really don't understand the goal of the above
> conditional ?!?

I hoped the patch description would cover that:
     With this patch:
     - a new object is always inserted after the last object with a
       smaller address, or at the start.  This preserves the property,
       important when allowing objects to be removed and re-added, that
       an object is never inserted *after* a position that it previously
       held in the list.

The items in each table slot are stored in order of the address of the
item.  So to find the first item in a slot that was not before the
previously returned item (iter->p), we step forward while this item is
<= that one. 

Does that help at all?

NeilBrown


>
> Should it possibly be something like:
> 				if (p != iter->p->next)
>
> instead? 
> But I think we can't safely dereference 'p' yet ?!?
>
> I'm sorry for the possibly dumb comments, rhashtable internals are
> somewhat obscure to me, but I'm really interested in this topic.
>
> Cheers,
>
> Paolo

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]