rhashtable: Notify on resize to allow signaling interrupted dumps

A deferred resize of nl_table causes the offsets that Netlink diag keeps to become inaccurate. Mark the dump as inconsistent and have user space request a new dump.

Signed-off-by Thomas Graf <[email protected]>

---
 net/netlink/af_netlink.c | 10 ++++++++++
 net/netlink/af_netlink.h |  1 +
 net/netlink/diag.c       |  1 +
 3 files changed, 12 insertions(+)

net/netlink/af_netlink.c +0 -0

index 7a94185..e214557 100644

net/netlink/af_netlink.c +9 -0

+EXPORT_SYMBOL_GPL(nl_table_seq);
+
 static DECLARE_WAIT_QUEUE_HEAD(nl_table_wait);
 
 static int netlink_dump(struct sock *sk);

@@ -3071,6 +3074,12 @@ static const struct net_proto_family netlink_family_ops = {
 	.owner	= THIS_MODULE,	/* for consistency 8) */
 };
 
+static void nl_table_resize_notify(const struct rhashtable *ht,
+				   enum rht_resize_op op)
+{
+	atomic_inc(&nl_table_seq);
+}
+
 static int __net_init netlink_net_init(struct net *net)
 {
 #ifdef CONFIG_PROC_FS

@@ -3124,6 +3133,7 @@ static int __init netlink_proto_init(void)
 		.max_shift = 16, /* 64K */
 		.grow_decision = rht_grow_above_75,
 		.shrink_decision = rht_shrink_below_30,
+		.resize_notify = nl_table_resize_notify,
 	};
 
 	if (err != 0)

net/netlink/af_netlink.h +1 -0

index 7518375..51c23c0 100644
@@ -74,5 +74,6 @@ struct netlink_table {
 
 extern struct netlink_table *nl_table;
 extern rwlock_t nl_table_lock;
+extern atomic_t nl_table_seq;
 
 #endif

net/netlink/diag.c +1 -0

index 3ee63a3..50aa385 100644
@@ -112,6 +112,7 @@ static int __netlink_diag_dump(struct sk_buff *skb, struct netlink_callback *cb,
 	int ret = 0, num = 0, i;
 
 	req = nlmsg_data(cb->nlh);
+	cb->seq = atomic_read(&nl_table_seq);
 
 	for (i = 0; i < htbl->size; i++) {
 		struct rhash_head *pos;

Quoted 19 lines · Thomas Graf

A deferred resize of nl_table causes the offsets that Netlink diag keeps to become inaccurate. Mark the dump as inconsistent and have user space request a new dump.

Signed-off-by Thomas Graf <[email protected]>

---
 net/netlink/af_netlink.c | 10 ++++++++++
 net/netlink/af_netlink.h |  1 +
 net/netlink/diag.c       |  1 +
 3 files changed, 12 insertions(+)

net/netlink/af_netlink.c +0 -0

index 7a94185..e214557 100644
@@ -91,6 +91,9 @@ static inline int netlink_is_kernel(struct sock *sk)
 struct netlink_table *nl_table;
 EXPORT_SYMBOL_GPL(nl_table);
 

net/netlink/af_netlink.c static inline int netlink_is_kernel(struct sock *sk) · line 94

Quoted 1 line

net/netlink/af_netlink.c +1 -0

+atomic_t nl_table_seq;

It sounds like the atomic variable is not initialized.

Thanks for the review. We also need to avoid hitting 0 when we overflow on a seq increment. The netfilter code is doing this correctly but several other users are suffering from this as well.

I'll address this in v2 together with the other discussed changes.

Quoted 5 lines · Thomas Graf

Thanks for the review. We also need to avoid hitting 0 when we overflow on a seq increment. The netfilter code is doing this correctly but several other users are suffering from this as well.

Quoted 1 line

I'll address this in v2 together with the other discussed changes.

Could you hold off for a bit? I've got some changes that touch this area that I'd like to push out. Basically I'm trying to eliminate direct access of rhashtable internals from the existing users.

Hope it will still be possible, I need it for GC in timeout support for nftables sets.

Quoted 3 lines · Patrick McHardy

Hope it will still be possible, I need it for GC in timeout support for nftables sets.

This should be able to use the same walk that you're currently using for dump once we add the restart, no?

Could you hold off for a bit? I've got some changes that touch this area that I'd like to push out. Basically I'm trying to eliminate direct access of rhashtable internals from the existing users.

lib/rhashtable.c +4 -0

+int rhashtable_walk_start(struct rhashtable_iter *iter)
+{
+	struct rhashtable *ht = iter->ht;
+	int err;

lib/rhashtable.c +29 -0

+/**
+ * rhashtable_walk_next - Return the next object and advance the iterator
+ * @iter:	Hash table iterator
+ *
+ * Note that you must call rhashtable_walk_stop when you are finished
+ * with the walk.
+ *
+ * Returns the next object or NULL when the end of the table is reached.
+ */
+void *rhashtable_walk_next(struct rhashtable_iter *iter)
+{
+	const struct bucket_table *tbl;
+	struct rhashtable *ht = iter->ht;
+	struct rhash_head *p = iter->p;
+
+	tbl = rht_dereference_rcu(ht->tbl, ht);
+
+	if (p) {
+		p = rht_dereference_bucket(p->next, tbl, iter->slot);
+		goto next;
+	}
+
+	for (; iter->slot < tbl->size; iter->slot++) {
+		int skip = iter->skip;
+
+		iter->lock = bucket_lock(tbl, iter->slot);
+		spin_lock_bh(iter->lock);
+
+		rht_for_each(p, tbl, iter->slot) {

lib/rhashtable.c +10 -0

+		}
+		spin_unlock_bh(iter->lock);
+
+		iter->skip = 0;
+	}
+
+	iter->p = NULL;
+	return NULL;
+}
+EXPORT_SYMBOL_GPL(rhashtable_walk_next);

Quoted 9 lines · Herbert Xu

lib/rhashtable.c +9 -0

+int rhashtable_walk_start(struct rhashtable_iter *iter)
+{
+	struct rhashtable *ht = iter->ht;
+	int err;
+
+	err = mutex_lock_interruptible(&ht->mutex);
+	rcu_read_lock();
+
+	if (!err)

lib/rhashtable.c exit: · line 838

Quoted 5 lines

lib/rhashtable.c +5 -0

+		mutex_unlock(&ht->mutex);
+
+	return err;
+}
+EXPORT_SYMBOL_GPL(rhashtable_walk_start);

This doesn't seem to work for Netlink dumps as it would define a RCU read side section across user read()s.

I assume you relying on RCU to defer the initial table relinking in the resizing to be postponed. Wouldn't it be better to hold the mutex instead, we could sleep during the dump.

Same here, we leave the iterator with the bucket lock held.

Some existing rhashtable users get too intimate with it by walking the buckets directly. This prevents us from easily changing the internals of rhashtable.

This patch adds the helpers rhashtable_walk_init/next/end which will replace these custom walkers.

They are meant to be usable for both procfs seq_file walks as well as walking by a netlink dump. The iterator structure should fit inside a netlink dump cb structure, with at least one element to spare.

lib/rhashtable.c +12 -0

+/**
+ * rhashtable_walk_start - Start a hash table walk
+ * @iter:	Hash table iterator
+ *
+ * Start a hash table walk.
+ *
+ * Returns zero if successful.  Returns -EINTR if we couldn't
+ * obtain the resize lock.
+ */
+int rhashtable_walk_start(struct rhashtable_iter *iter)
+{
+	struct rhashtable *ht = iter->ht;

That doesn't look right to me.
Surely you shouldn't be calling rcu_read_lock() when the mutex request is interrupted.

So maybe:

	err = mutex_lock_interruptible(&ht->mutex);
	if (err)
		return err;
	rcu_read_lock();

Quoted 10 lines

That doesn't look right to me.
Surely you shouldn't be calling rcu_read_lock() when the mutex request is interrupted.

So maybe:

	err = mutex_lock_interruptible(&ht->mutex);
	if (err)
		return err;
	rcu_read_lock();

No, we need to grab the RCU read lock while holding the mutex in order to prevent future resizes from happening once we release the mutex.

We don't want to hold the mutex which would stop other walks from starting.

I really think the amount of time and effort being put into making the walker function properly is excessive.

Let's just say that if you want to use rhashtable, you have to use a linked list, or similar separate mechanism, to have stable walks of the entire set of objects.

As otherwise we'd be looking at fixing the existing users (in particular, nft_hash) properly which might take a lot more time.

Quoted 3 lines · Herbert Xu

As otherwise we'd be looking at fixing the existing users (in particular, nft_hash) properly which might take a lot more time.

I take that back. Looks like my walkers would be no good for netfilter anyway since it wants to do nested walks, meaning no locks can be taken.

So I think I'll just have to tackle netfilter first in which case the walk function would be no use anyway since I could just fix netlink by itself.

OK. I'll wait for your netfilter approach before posting NLM_F_INTR patches.

Quoted 3 lines · Thomas Graf

OK. I'll wait for your netfilter approach before posting NLM_F_INTR patches.

Why would we still need the INTR stuff given that Dave has asked for this to be done outside of rhashtable?

What I'm planning on doing right now is to divide rhashtable users into two camps, lockless insert/removal vs. locked insert/removal. netfilter will obviously fall into the latter camp.

For those with locked insert/removal I will make resizing/rehashing synchronous since there is zero benefit from doing it in a separate thread.

Once that is done you can then easily walk the table by just holding the lock, which is what netfilter does today.

Because libraries like libnl already handle this transparently for various user space apps. Those apps are not even aware of the problem and always get a consistent dump if the kernel implements INTR.

Because making it synchronous does not help the Netlink dump problem at all, see below.

Also, a sync resize causes a random inserts/removal to take a lot longer. This leads to less predictable insert/removal times. I have no objection to offering both sync and async resizing as long as the choice of balance is configurable.

The point is that for netfilter as it stands it makes no sense to go lockless because its modus operandi is to hold a single lock over everything, including walking/dumping.

No objection. I have a patch prepared which allows the user to provide ht->mutex himself so nfset can provide its own existing mutex to rhashtable and lock out the resizes from inserts, removals and dump iterations automatically That would restore the old behaviour of the nfset API without major surgery.

Quoted 6 lines · Thomas Graf

No objection. I have a patch prepared which allows the user to provide ht->mutex himself so nfset can provide its own existing mutex to rhashtable and lock out the resizes from inserts, removals and dump iterations automatically That would restore the old behaviour of the nfset API without major surgery.

If you take the mutex you might as well just make it synchronous. There is zero difference.

Maybe you misunderstood my email. I'm not making it synchronous for everybody, just those that always take a lock on inserts/removals and therefore don't need per-bucket locks.

This is unrelated to resize run control though, the reason is that I'm converting tcp_hashinfo et al and they require a hybrid approach. The tables may be too big to construct a parallel data structure, we don't want to hold off inserts or deletes while the expensive dump is underway. Even though we can't build a shadow structure while locking everybody else out, we still want to provide a way to somehow achieve consistent information. I think that NLM_F_INTR with fallback to restarting the dump is a good option and very easy to implement. In that case, we want to lock out resize from dumping iterations but still allow parallel insert/delete.

Quoted 11 lines

This is unrelated to resize run control though, the reason is that I'm converting tcp_hashinfo et al and they require a hybrid approach. The tables may be too big to construct a parallel data structure, we don't want to hold off inserts or deletes while the expensive dump is underway. Even though we can't build a shadow structure while locking everybody else out, we still want to provide a way to somehow achieve consistent information. I think that NLM_F_INTR with fallback to restarting the dump is a good option and very easy to implement. In that case, we want to lock out resize from dumping iterations but still allow parallel insert/delete.

Well I guess Dave needs to make the call. Do we want to allow lockless walks over the hash table or not?

Personally I don't think a linked list is that big a deal. But then you guys were agonsing over a single pointer so who knows.

For netlink a linked list is no big deal, but for something like TCP sockets it really is.

Quoted 6 lines · Thomas Graf

No objection. I have a patch prepared which allows the user to provide ht->mutex himself so nfset can provide its own existing mutex to rhashtable and lock out the resizes from inserts, removals and dump iterations automatically That would restore the old behaviour of the nfset API without major surgery.

If you take the mutex you might as well just make it synchronous. There is zero difference.

Maybe you misunderstood my email. I'm not making it synchronous for everybody, just those that always take a lock on inserts/removals and therefore don't need per-bucket locks.

Actually I have a patchset queued that adds runtime additions and removals, both active and timeout based. So netfilter won't have pure synchronous behaviour anymore.

Quoted 4 lines · Patrick McHardy

Actually I have a patchset queued that adds runtime additions and removals, both active and timeout based. So netfilter won't have pure synchronous behaviour anymore.

Can you show us the patchset?

Quoted 7 lines · Herbert Xu

Quoted 4 lines · Patrick McHardy

Actually I have a patchset queued that adds runtime additions and removals, both active and timeout based. So netfilter won't have pure synchronous behaviour anymore.

Can you show us the patchset?

Sure, will send it over tomorrow.

Quoted 7 lines · Patrick McHardy

Quoted 6 lines · Herbert Xu

Quoted 4 lines · Patrick McHardy

Actually I have a patchset queued that adds runtime additions and removals, both active and timeout based. So netfilter won't have pure synchronous behaviour anymore.

Quoted 3 lines

Quoted 1 line

Can you show us the patchset?

Sure, will send it over tomorrow.

So how are you handling the locking in these cases?

Quoted 10 lines

That doesn't look right to me.
Surely you shouldn't be calling rcu_read_lock() when the mutex request is interrupted.

So maybe:

	err = mutex_lock_interruptible(&ht->mutex);
	if (err)
		return err;
	rcu_read_lock();

No, we need to grab the RCU read lock while holding the mutex in order to prevent future resizes from happening once we release the mutex.

But if err is non-zero you don't hold the mutex. Presumably the calling code also errors out immediately, so the RCU lock isn't needed at all.

Here are the first two patches, one to add the primitives and one to demonstrate its use in netlink. In fact while testing this I found that the existing netlink walking code is totally broken.

Some existing rhashtable users get too intimate with it by walking the buckets directly. This prevents us from easily changing the internals of rhashtable.

This patch adds the helpers rhashtable_walk_init/next/end which will replace these custom walkers.

They are meant to be usable for both procfs seq_file walks as well as walking by a netlink dump. The iterator structure should fit inside a netlink dump cb structure, with at least one element to spare.

Signed-off-by Herbert Xu <[email protected]>

This patch gets rid of the manual rhashtable walk in netlink which touches rhashtable internals that should not be exposed. It does so by using the rhashtable iterator primitives.

In fact the existing code was very buggy. Some sockets weren't shown at all while others were shown more than once.

Signed-off-by Herbert Xu <[email protected]>

Quoted 4 lines

Here are the first two patches, one to add the primitives and one to demonstrate its use in netlink. In fact while testing this I found that the existing netlink walking code is totally broken.

So this is a repost of the same thing. These lockless iterators won't be usable by netfilter as it stands because it wants to do nested walks and also isn't currently lockless.

However, I'll wait for Patrick to post his pending patches to see what exactly he needs before implementing helpers for that case.

I'm holding off on this series for now.

Let me know if you want me to do something different.

No problems. Here is a new version of these two patches which hopefully should work on netfilter as well.

Quoted 3 lines · Herbert Xu

No problems. Here is a new version of these two patches which hopefully should work on netfilter as well.

And here is the patch for netfilter.

-- >8 --
This patch gets rid of the manual rhashtable walk in nft_hash which touches rhashtable internals that should not be exposed. It does so by using the rhashtable iterator primitives.

Note that I'm leaving nft_hash_destroy alone since it's only invoked on shutdown and it shouldn't be affected by changes to rhashtable internals (or at least not what I'm planning to change).

Signed-off-by Herbert Xu <[email protected]>

Quoted 3 lines

No problems. Here is a new version of these two patches which hopefully should work on netfilter as well.

And here is the patch for netfilter.

-- >8 --
This patch gets rid of the manual rhashtable walk in nft_hash which touches rhashtable internals that should not be exposed. It does so by using the rhashtable iterator primitives.

Note that I'm leaving nft_hash_destroy alone since it's only invoked on shutdown and it shouldn't be affected by changes to rhashtable internals (or at least not what I'm planning to change).

Signed-off-by Herbert Xu <[email protected]>

Quoted 4 lines

I'm holding off on this series for now.

Let me know if you want me to do something different.

No problems. Here is a new version of these two patches which hopefully should work on netfilter as well.

Note that the major functional difference compared to the previous one is that resizes are now handled properly and will cause the iterator to restart from scratch.

However, as with all existing hash table walker implementations, if you remove an element from the chain that we're walking over while we're waiting for user-space to give us a new buffer, then the walk may miss elements that are still on that chain.

Lock out table resizes while dumping Netlink sockets to user space. This keeps disruptions to a minimum for readers which don't handle the NLM_F_DUMP_INTR flag.

Signed-off-by Thomas Graf <[email protected]>

---
 net/netlink/diag.c | 3 +++
 1 file changed, 3 insertions(+)

net/netlink/diag.c +3 -0

index 50aa385..be4ea6e 100644
@@ -114,6 +114,8 @@ static int __netlink_diag_dump(struct sk_buff *skb, struct netlink_callback *cb,
 	req = nlmsg_data(cb->nlh);
 	cb->seq = atomic_read(&nl_table_seq);
 
+	mutex_lock(&ht->mutex);
+
 	for (i = 0; i < htbl->size; i++) {
 		struct rhash_head *pos;
 

@@ -161,6 +163,7 @@ static int __netlink_diag_dump(struct sk_buff *skb, struct netlink_callback *cb,
 		num++;
 	}
 done:
+	mutex_unlock(&ht->mutex);
 	cb->args[0] = num;
 	cb->args[1] = protocol;
 

Signature · 1 line

1.9.3

Quoted 3 lines · Thomas Graf

Lock out table resizes while dumping Netlink sockets to user space. This keeps disruptions to a minimum for readers which don't handle the NLM_F_DUMP_INTR flag.

This doesn't lock them out for the duration of the entire dump of course, so the benefit seems rather small. Still with this patch, they will need to handle NLM_F_DUMP_INTR or will get unpredictable behaviour, in which case I'd think it makes more sense to not even try this, all it does is hide parts of the brokenness.

An alternative would be to set a flag in ht when a dump begins that indicates to skip resizing operations and on the end of the dump perform any resizing operations that might be necessary. Herbert disagrees though and he might be right.

Quoted 10 lines · Patrick McHardy

Quoted 3 lines · Thomas Graf

Lock out table resizes while dumping Netlink sockets to user space. This keeps disruptions to a minimum for readers which don't handle the NLM_F_DUMP_INTR flag.

This doesn't lock them out for the duration of the entire dump of course, so the benefit seems rather small. Still with this patch, they will need to handle NLM_F_DUMP_INTR or will get unpredictable behaviour, in which case I'd think it makes more sense to not even try this, all it does is hide parts of the brokenness.

If it would lock out the resize for the entire dump I would not have done patches 1 and 2 ;-)

I does provide better behaviour if the whole dump fits into a single buffer or if it fits into 2 buffers and we are already dumping into the 2nd buffer when the resize occurs. Otherwise we will see resizes and thus tons of duplicates even in those scenarios even if no insert or removal occurs in parallel.

In the case of Netlink diag that should be typical case. Most systems will not have 1000s of Netlink sockets in parallel.

Quoted 4 lines

An alternative would be to set a flag in ht when a dump begins that indicates to skip resizing operations and on the end of the dump perform any resizing operations that might be necessary. Herbert disagrees though and he might be right.

I don't like the flag as it prevents resizes (and possibly rehashes further down the road) for a long period of time. The hashtable becomes attackable.

I think its preferrable to make the need to handle NETLINK_F_DUMP_INTR as noticable as possible and not hide it. Silent failure is the worst kind of failure.

Yeah. The point could be made that this is a regression though. We didn't require userspace to deal with interruptions before, and the behaviour was well defined and acceptable for most cases, its not anymore.

So I think it should be handled by the kernel, without changes to userspace.

Quoted 3 lines · Patrick McHardy

I think its preferrable to make the need to handle NETLINK_F_DUMP_INTR as noticable as possible and not hide it. Silent failure is the worst kind of failure.

I agree to that. The point here is to avoid unnecessary use of NETLINK_F_DUMP_INTR if all entries fit into a single message buffer.

OK I think I have a solution for you guys. But first you'll need to wait for me to undo the nulls stuff so I can steal that bit which is central to my solution.

Essentially I need a bit to indicate an entry in the bucket chain should be skipped, either because it has just been removed or that it is a walker entry (see xfrm_state_walk).

The way it'll work then is exactly the same as xfrm_state_walk, except that the linked list is broken up into individual buckets.

Of course we'll still need to postpone resizes (and rehashes which is what my work is about) during a walk but I think that's a fair price to pay.

Quoted 12 lines · Herbert Xu

OK I think I have a solution for you guys. But first you'll need to wait for me to undo the nulls stuff so I can steal that bit which is central to my solution.

Essentially I need a bit to indicate an entry in the bucket chain should be skipped, either because it has just been removed or that it is a walker entry (see xfrm_state_walk).

The way it'll work then is exactly the same as xfrm_state_walk, except that the linked list is broken up into individual buckets.

Quoted 3 lines

Of course we'll still need to postpone resizes (and rehashes which is what my work is about) during a walk but I think that's a fair price to pay.

I failed to address the security aspect of this approach. Obviously this can only work if the only entites doing the walk are trusted. Which means that the vast majority (if not all) hash table users would be excluded, in particular, netlink.

Quoted 4 lines · Herbert Xu

I failed to address the security aspect of this approach. Obviously this can only work if the only entites doing the walk are trusted. Which means that the vast majority (if not all) hash table users would be excluded, in particular, netlink.

OK maybe we can get around this. So we will postpone the resize or rehash when a walk is in place, however, when we hit a hard limit, i.e., when insert would otherwise fail, then we do the rehash regardless of any outstanding walks. The walks will just behave erratically or we could force them to start from scratch again.

Exactly. I think we also need a timer to abort walks because if only a single walker is allowed, an attacker could start a walk and not complete it to block out everybody else.

Quoted 6 lines · Herbert Xu

Quoted 4 lines · Herbert Xu

I failed to address the security aspect of this approach. Obviously this can only work if the only entites doing the walk are trusted. Which means that the vast majority (if not all) hash table users would be excluded, in particular, netlink.

Quoted 6 lines

OK maybe we can get around this. So we will postpone the resize or rehash when a walk is in place, however, when we hit a hard limit, i.e., when insert would otherwise fail, then we do the rehash regardless of any outstanding walks. The walks will just behave erratically or we could force them to start from scratch again.

Exactly. I think we also need a timer to abort walks because if only a single walker is allowed, an attacker could start a walk and not complete it to block out everybody else.

Quoted 5 lines · Thomas Graf

Quoted 3 lines · Patrick McHardy

I think its preferrable to make the need to handle NETLINK_F_DUMP_INTR as noticable as possible and not hide it. Silent failure is the worst kind of failure.

Quoted 2 lines

I agree to that. The point here is to avoid unnecessary use of NETLINK_F_DUMP_INTR if all entries fit into a single message buffer.

OK I think I have a solution for you guys. But first you'll need to wait for me to undo the nulls stuff so I can steal that bit which is central to my solution.

Essentially I need a bit to indicate an entry in the bucket chain should be skipped, either because it has just been removed or that it is a walker entry (see xfrm_state_walk).

The way it'll work then is exactly the same as xfrm_state_walk, except that the linked list is broken up into individual buckets.

Of course we'll still need to postpone resizes (and rehashes which is what my work is about) during a walk but I think that's a fair price to pay.

This also means handling insertion failures but I think that should be acceptable if we make it based on a configurable maximum chain length along with forced resize/rehash where possible.

Note that this can be made optional, i.e., if the user can afford memory to do their own walking (e.g., xfrm_state), then none of this needs to happen and it'll just work as it does now. IOW if you don't use this special rhashtable walk function then you're not affected.

Without having seen your code, can we make it configurable on what the bit is used for? Use of nulls marker is a strict requirement for some targeted users of rhashtable.

Quoted 4 lines · Thomas Graf

Without having seen your code, can we make it configurable on what the bit is used for? Use of nulls marker is a strict requirement for some targeted users of rhashtable.

What do they need this for?

An entry can move between different tables and thus chains need to be marked to identify what list a lookup ended up searching in. It's not the nulls marker itself that is needed, it's the bits in the last next pointer identifying the list that the nulls marker allows to be used which are essential.

Quoted 6 lines · Thomas Graf

An entry can move between different tables and thus chains need to be marked to identify what list a lookup ended up searching in. It's not the nulls marker itself that is needed, it's the bits in the last next pointer identifying the list that the nulls marker allows to be used which are essential.

Can you describe in more detail how it's going to be used? I don't see how I could use the bit if you need it to indicate the end of the list.

The usage will be identical to how __inet_lookup_listener() uses it. If at the end of the lookup, we ended up in a different table than we started, the lookup is restarted as an entry has moved to another table while we were moving over it.

Quoted 5 lines · Thomas Graf

The usage will be identical to how __inet_lookup_listener() uses it. If at the end of the lookup, we ended up in a different table than we started, the lookup is restarted as an entry has moved to another table while we were moving over it.

Who uses this stuff apart from ip_dynaddr?

Quoted 7 lines · Herbert Xu

Quoted 5 lines · Thomas Graf

The usage will be identical to how __inet_lookup_listener() uses it. If at the end of the lookup, we ended up in a different table than we started, the lookup is restarted as an entry has moved to another table while we were moving over it.

Quoted 1 line

Who uses this stuff apart from ip_dynaddr?

OK it's there for fast socket recycling. Given that and the fact that everyone seems to be happy with restarting the dump after a resize, I think we should just go with that.

Anybody who wants a better walk can always implement their own data structure outside of rhashtable.

What did you think of the idea to let the user store the walker bit for rhashtable?

Quoted 6 lines · Thomas Graf

An entry can move between different tables and thus chains need to be marked to identify what list a lookup ended up searching in. It's not the nulls marker itself that is needed, it's the bits in the last next pointer identifying the list that the nulls marker allows to be used which are essential.

Can you describe in more detail how it's going to be used? I don't see how I could use the bit if you need it to indicate the end of the list.

Quoted 11 lines · Herbert Xu

Quoted 6 lines · Thomas Graf

An entry can move between different tables and thus chains need to be marked to identify what list a lookup ended up searching in. It's not the nulls marker itself that is needed, it's the bits in the last next pointer identifying the list that the nulls marker allows to be used which are essential.

Can you describe in more detail how it's going to be used? I don't see how I could use the bit if you need it to indicate the end of the list.

Another thought: Instead of storing that bit in the next pointer, we could require the user to store this bit, i.e. two new function pointers to rhashtable_params, set_walk_bit() and get_walk_bit(), which take the hashed object as argument and if a rhashtable user requires consistent dumps he can provide these functions to store the flag.

On the danger of repeating myself, every (converted) user requires that we at least keep the existing semantics since it is exposed to userspace. My opinion is that NLM_F_DUMP_INTR is fine if userspace indicates support, but without that, we have to take care of that in the kernel.

An automatic restart handles this well. Userspace always had to expect duplicates.

Quoted 5 lines · Patrick McHardy

On the danger of repeating myself, every (converted) user requires that we at least keep the existing semantics since it is exposed to userspace. My opinion is that NLM_F_DUMP_INTR is fine if userspace indicates support, but without that, we have to take care of that in the kernel.

Absolutely agreed. I think this is an excellent low cost path for future users where dumps are rare.

Quoted 2 lines

An automatic restart handles this well. Userspace always had to expect duplicates.

Maybe I don't understand the restart yet. How do you restart if the dump was already started and the user has read part of the dump?

Quoted 6 lines · Thomas Graf

Quoted 2 lines · Patrick McHardy

An automatic restart handles this well. Userspace always had to expect duplicates.

Maybe I don't understand the restart yet. How do you restart if the dump was already started and the user has read part of the dump?

You use the mutex to prevent concurrent resizes and dumps, for dumps that have left the kernel you simply reset the iterator state after a resize operation.

Quoted 11 lines · Patrick McHardy

Quoted 6 lines · Thomas Graf

Quoted 2 lines · Patrick McHardy

An automatic restart handles this well. Userspace always had to expect duplicates.

Maybe I don't understand the restart yet. How do you restart if the dump was already started and the user has read part of the dump?

You use the mutex to prevent concurrent resizes and dumps, for dumps that have left the kernel you simply reset the iterator state after a resize operation.

I see, so we possibly see a lot of duplicates but we will never miss any entries.

So in summary we do:

2) We allow rhashtable users to opt in to Herbert's consistent walker relying on the use of an additional bit.

2) If user supports NLM_F_DUMP_INTR we block out resizes during message construction and set NLM_F_DUMP_INTR if a resize/rehash interrupted us while the user read.

3) If (1) and (2) are not available we do (2) but restart the dump on interruption thus causing duplicates but never missing any entries.

I think this offers good flexibility for new users and compatibility for existing users.

Quoted 7 lines

Essentially I need a bit to indicate an entry in the bucket chain should be skipped, either because it has just been removed or that it is a walker entry (see xfrm_state_walk).

The way it'll work then is exactly the same as xfrm_state_walk, except that the linked list is broken up into individual buckets.

Quoted 3 lines

Of course we'll still need to postpone resizes (and rehashes which is what my work is about) during a walk but I think that's a fair price to pay.

If I understand this correctly we also need to block out parallel walkers and we need to start taking bucket locks while walking to modify the walker mark bit in peace.

Quoted 3 lines

Lock out table resizes while dumping Netlink sockets to user space. This keeps disruptions to a minimum for readers which don't handle the NLM_F_DUMP_INTR flag.

This doesn't lock them out for the duration of the entire dump of course, so the benefit seems rather small. Still with this patch, they will need to handle NLM_F_DUMP_INTR or will get unpredictable behaviour, in which case I'd think it makes more sense to not even try this, all it does is hide parts of the brokenness.

An alternative would be to set a flag in ht when a dump begins that indicates to skip resizing operations and on the end of the dump perform any resizing operations that might be necessary. Herbert disagrees though and he might be right.

From: Patrick McHardy

Quoted 4 lines

An alternative would be to set a flag in ht when a dump begins that indicates to skip resizing operations and on the end of the dump perform any resizing operations that might be necessary. Herbert disagrees though and he might be right.

Can you rely on being told when the dump completes? If the program is killed in the middle then it can't tell you.

I suspect you'd have to suppress resize for some time interval after a partial dump.
Unfortunately two continuous dumps would be likely to suppress it forever. Maybe sleep user space dump requests for the first block while any resize (esp. grow) is pending.

What is passed to userspace as the 'continue from here' marker? Even without resize there are likely to be issues if something nearer the head of a hash chain being processed is deleted.

An alternative would be to set a flag in ht when a dump begins that indicates to skip resizing operations and on the end of the dump perform any resizing operations that might be necessary. Herbert disagrees though and he might be right.