by Tom Herbert

On Sun, May 06, 2018 at 08:00:49AM +1000, NeilBrown wrote:
>
> The insert function must (and does) take the lock on the bucket before
> testing if there is a "next" table.
> If one inserter finds that it has locked the "last" table (because there
> is no next) and successfully inserts, then the other inserter cannot
> have locked that table yet, else it would have inserted. When it does,
> it will find what the first inserter inserted.

If you release the lock to the first table then it may be deleted
by the resize thread. Hence the other inserter may not have even
started from the same place.

Cheers,
--
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

2018-05-06 05:21:54

by Herbert Xu

On Mon, May 07 2018, Herbert Xu wrote:

> On Mon, May 07, 2018 at 08:24:41AM +1000, NeilBrown wrote:
>>
>> This is true, but I don't see how it is relevant.
>> At some point, each thread will find that the table they have just
>> locked for their search key, has a NULL 'future_tbl' pointer.
>> At the point, the thread can know that the key is not in any table,
>> and that no other thread can add the key until the lock is released.
>
> The updating of future_tbl is not synchronised with insert threads.
> Therefore it is entirely possible that two inserters end up on
> different tables as their "latest" table. This must not be allowed
> to occur.

I disagree.
Certainly the update of future_tbl is not synchronised with insert
threads.
However there is only a single update to any given future_tbl (from NULL
to non-NULL) and two insert threads for the same key will see that
update in a synchronized way as they look at it while holding the bucket
lock for that key.
It is certainly true if that two inserters can end up on different
tables as their "latest" table, but that doesn't result in a problem.
e.g. T1 might see A as the latest table, and T2 might see B where
A.future_tbl == B
In that case, T2 must have examined A (under the lock) *after* T1
examined A, and so will have seen if T1 inserted anything.

Thanks,
NeilBrown

Attachments:

signature.asc (847.00 B)

2018-05-08 00:55:41

by NeilBrown

[permalink] [raw]

Subject: Re: [PATCH 6/8] rhashtable: further improve stability of rhashtable_walk

On Mon, May 07 2018, Herbert Xu wrote:

> On Sun, May 06, 2018 at 07:50:54AM +1000, NeilBrown wrote:
>>
>> Do we? How could we fix it for both rhashtable and rhltable?
>
> Well I suggested earlier to insert the walker object into the
> hash table, which would be applicable regardless of whether it
> is a normal rhashtable of a rhltable.

Oh yes, that idea. I had considered it and discarded it.
Moving a walker object around in an rcu-list is far from straight
forward. A lockless iteration of the list would need to be very careful
not to be tripped up by the walker-object. I don't think we want to
make the search code more complex.

I explored the idea a bit more and I think that any solution that we
came up with along those lines would look quite different for regular
rhash_tables than for rhl_tables. So it is probably best to keep them
quite separate.
i.e. use the scheme I proposed for rhashtables and use something else
entirely for rhltables.

My current thinking for a stable walk for rhl tables goes like this:

- we embed
struct rhl_cursor {
struct rhl_cursor *next;
int unseen;
}
in struct rhashtable_iter.

- on rhashtable_stop(), we:
+ lock the current hash chain
+ find the next object that is still in the table (after ->p).
+ count the number of objects from there to the end to the
end of the rhlist_head.next list.
+ store that count in rhl_cursor.unseen
+ change the ->next pointer at the end of the list to point to the
rhl_cursor, but with the lsb set. If there was already an
rhl_cursor there, they are chained together on ->next.

- on rhashtable_start(), we lock the hash chain and search the hash
chain and sub-chains for ->p or the rhl_cursor.
If ->p is still there, that can be used as a reliable anchor.
If ->p isn't found but the rhl_cursor is, then the 'unseen' counter
tells us where to start in that rhl_list.
If neither are found, then we start at the beginning of the hash chain.
If the rhl_cursor is found, it is removed.

- lookup and insert can almost completely ignore the cursor.
rhl_for_each_rcu() needs to detect the end-of-list by looking for
lsb set, but that is the only change.
As _insert() adds new objects to the head of the rhlist, that
won't disturb the accuracy of the 'unseen' count. The newly inserted
object won't be seen by the walk, but that is expected.

- delete needs some extra handling.
+ When an object is deleted from an rhlist and the list does not become
empty, then it counts the number of objects to the end of the list,
and possibly decrements the 'unseen' counter on any rhl_cursors that
are at the end of the list.
+ when an object is deleted resulting in an empty rhlist, any
cursors at the end of the list needs to be moved to the next
list in the hash chain, and their 'unseen' count needs to be set to
the length of the list.
If there is no next object in the hash chain, then the iter.slot is
incremented and the rhlist_curs is left unconnected.

- rehash needs to remove any cursors from the end of an rhlist before
moving them to the new table. The cursors are left disconnected.

I'm happy to implement this if you think the approach is workable and
the functionality is necessary. However there are no current users of
rhltable_walk_inter that would benefit from this.

Thanks,
NeilBrown

Attachments:

signature.asc (847.00 B)

2018-05-08 01:14:57

by NeilBrown

[permalink] [raw]

Subject: Re: [PATCH 2/8] rhashtable: remove nulls_base and related code.

On Mon, May 07 2018, Herbert Xu wrote:

> On Sun, May 06, 2018 at 07:37:49AM +1000, NeilBrown wrote:
>>
>> I can see no evidence that this is required for anything, as it isn't
>> use and I'm fairly sure that in it's current form - it cannot be used.
>
> Search for nulls in net/ipv4. This is definitely used throughout
> the network stack. As the aim is to convert as many existing hash
> tables to rhashtable as possible, we want to keep this.

Yes, I'm sure that nulls lists are very useful and I can see them used
in net/ipv4 (and I would like to use them myself). I don't want to
remove the nulls list concept from rhashtable, and my patch doesn't do
that.

It just removes nulls_base (as the subject says) and stops setting any
particular value in the nulls pointer, because the value is currently
never tested.

The point of nulls lists is, as I'm sure you know, to detect if an
object was moved to a different chain and to restart the search in that
case.
This means that on an unsuccessful search, we need to test
get_nulls_value() of the tail pointer.
Several times in net/ipv4/inet_hashtables.c (for example) we see code
like:

/*
* if the nulls value we got at the end of this lookup is
* not the expected one, we must restart lookup.
* We probably met an item that was moved to another chain.
*/
if (get_nulls_value(node) != slot)
goto begin;

which does exactly that. This test-and-restart cannot be done by a
caller to rhashtable_lookup_fast() as the caller doesn't even get to
the tail nulls.
It would need to be done in rhashtable.[ch].
If you like, I can make this functionality work rather than just
removing the useless parts.

I would change INIT_RHT_NULLS_HEAD() to return to be
#define INIT_RHT_NULLS_HEAD(ptr, ht, hash) \
((ptr) = (void*)NULLS_MARKER(((unsigned long)ptr)>>1)

Then when __rhashtable_lookup() comes to the end of the chain
without finding anything it would do something like
if (get_nulls_value(he)<<1 == (unsigned long)head)
goto restart;

where 'head' is the head of the list that we would have saved at the
start.

i.e. instead of using a nulls_base and limiting the size of the hash, we
store the address of the bucket in the nulls.

In my mind that should be a separate patch. First remove the unused,
harmful code. Then add code to provide useful functionality. But
I can put the two together in one patch if you would prefer that.

Thanks,
NeilBrown

Attachments:

signature.asc (847.00 B)