Skip to contentSkip to conversation

rhashtable updates

PATCH In review Daniel Borkmann 7 participants 27 messages Feb 25, 2015 – Mar 13, 2015

Subsystems (6)
lore
Share & tools
lore
#0 lore raw

cover rhashtable updates

As discussed, I'm sending out rhashtable fixups for -net.

I have a couple of more patches I was working on last week pending, i.e. to get rid of ht->nelems and ht->shift atomic operations which speed-up pure insertions/deletions, e.g. on my laptop I have 2 threads, inserting 7M entries each, that will reduce insertion time from ~1,450 ms to 865 ms (performance should even be better after removing the grow/shrink indirections). I guess that however is rather something for net-next.

Thanks,
Daniel

Daniel Borkmann (2):
rhashtable: unconditionally grow when max_shift is not specified
rhashtable: remove indirection for grow/shrink decision functions

 include/linux/rhashtable.h | 13 -----------
 lib/rhashtable.c           | 58 ++++++++++++++--------------------------------
 lib/test_rhashtable.c      |  3 +--
 net/netfilter/nft_hash.c   |  2 --
 net/netlink/af_netlink.c   |  2 --
 net/tipc/socket.c          |  2 --
 6 files changed, 19 insertions(+), 61 deletions(-)
Signature · 1 line
1.9.3
#1 lore raw

PATCH 1/2 rhashtable: unconditionally grow when max_shift is not specified

While commit c0c09bfdc415 ("rhashtable: avoid unnecessary wakeup for worker queue") rightfully moved part of the decision making of whether we should expand or shrink from the expand/shrink functions themselves into insert/delete functions in order to avoid unnecessary worker wake-ups, it however introduced a regression by doing so.

Before that change, if no max_shift was specified (= 0) on rhashtable initialization, rhashtable_expand() would just grow unconditionally and lets the available memory be the limiting factor. After that change, if no max_shift was specified, there would be _no_ expansion step at all.

Given that netlink and tipc have a max_shift specified, it was not visible there, but Josh Hunt reported that if nft that starts out with a default element hint of 3 if not otherwise provided, would slow i.e. inserts down trememdously as it cannot grow larger to relax table occupancy.

Given that the test case verifies shrinks/expands manually, we also must remove pointer to the helper functions to explicitly avoid parallel resizing on insertions/deletions. test_bucket_stats() and test_rht_lookup() could also be wrapped around rhashtable mutex to explicitly synchronize a walk from resizing, but I think that defeats the actual test case which intended to have explicit test steps, i.e. 1) inserts, 2) expands, 3) shrinks, 4) deletions, with object verification after each stage.

Fixes c0c09bfdc415 ("rhashtable: avoid unnecessary wakeup for worker queue")
Cc Ying Xue <[email protected]>
Cc Josh Hunt <[email protected]>
---
 lib/rhashtable.c      | 2 +-
 lib/test_rhashtable.c | 2 --
 2 files changed, 1 insertion(+), 3 deletions(-)
lib/rhashtable.c +1 -1
index e3a04e4..bcf119b 100644
@@ -251,7 +251,7 @@ bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size)
 {
 	/* Expand table when exceeding 75% load */
 	return atomic_read(&ht->nelems) > (new_size / 4 * 3) &&
-	       (ht->p.max_shift && atomic_read(&ht->shift) < ht->p.max_shift);
+	       (!ht->p.max_shift || atomic_read(&ht->shift) < ht->p.max_shift);
 }
 EXPORT_SYMBOL_GPL(rht_grow_above_75);
 
lib/test_rhashtable.c +0 -2
index 58b9953..f9e9d73 100644
@@ -202,8 +202,6 @@ static int __init test_rht_init(void)
 		.key_len = sizeof(int),
 		.hashfn = jhash,
 		.nulls_base = (3U << RHT_BASE_SHIFT),
-		.grow_decision = rht_grow_above_75,
-		.shrink_decision = rht_shrink_below_30,
 	};
 	int err;
 
Signature · 1 line
1.9.3
maintainer
#2 lore raw

Re: [PATCH net 1/2] rhashtable: unconditionally grow when max_shift is not specified

lib/test_rhashtable.c static int __init test_rht_init(void) · line 206

Quoted 12 lines · Daniel Borkmann
lib/test_rhashtable.c +0 -2
index 58b9953..f9e9d73 100644
@@ -202,8 +202,6 @@ static int __init test_rht_init(void)
 		.key_len = sizeof(int),
 		.hashfn = jhash,
 		.nulls_base = (3U << RHT_BASE_SHIFT),
-		.grow_decision = rht_grow_above_75,
-		.shrink_decision = rht_shrink_below_30,
 	};
 	int err;

I assume you wanted this chunk in patch 2.

#3 lore raw

Re: [PATCH net 1/2] rhashtable: unconditionally grow when max_shift is not specified

Quoted 15 lines · Thomas Graf

lib/test_rhashtable.c static int __init test_rht_init(void) · line 206

Quoted 12 lines · Daniel Borkmann
lib/test_rhashtable.c +0 -2
index 58b9953..f9e9d73 100644
@@ -202,8 +202,6 @@ static int __init test_rht_init(void)
  		.key_len = sizeof(int),
  		.hashfn = jhash,
  		.nulls_base = (3U << RHT_BASE_SHIFT),
-		.grow_decision = rht_grow_above_75,
-		.shrink_decision = rht_shrink_below_30,
  	};
  	int err;

I assume you wanted this chunk in patch 2.

No, it's in this chunk on purpose. ;)

I've tried to explain it here in the commit message:

Given that the test case verifies shrinks/expands manually, we also must remove pointer to the helper functions to explicitly avoid parallel resizing on insertions/deletions. test_bucket_stats() and test_rht_lookup() could also be wrapped around rhashtable mutex to explicitly synchronize a walk from resizing, but I think that defeats the actual test case which intended to have explicit test steps, i.e. 1) inserts, 2) expands, 3) shrinks, 4) deletions, with object verification after each stage.

If we leave it as is, the test case may fail due to a resize run competing in parallel with the walk (as it's not using Herbert's API) - I assume the purpose of the test case was to test expands and shrinks manually in stages and walk/verify the table after each step.

Cheers,
Daniel

#4 lore raw

Re: [PATCH net 1/2] rhashtable: unconditionally grow when max_shift is not specified

Quoted 1 line · Daniel Borkmann

On 02/25/2015 05:28 PM, Thomas Graf wrote:

...

Quoted 6 lines
Quoted 1 line

I assume you wanted this chunk in patch 2.

No, it's in this chunk on purpose. ;)

I've tried to explain it here in the commit message:

Quoted 8 lines

Given that the test case verifies shrinks/expands manually, we also must remove pointer to the helper functions to explicitly avoid parallel resizing on insertions/deletions. test_bucket_stats() and test_rht_lookup() could also be wrapped around rhashtable mutex to explicitly synchronize a walk from resizing, but I think that defeats the actual test case which intended to have explicit test steps, i.e. 1) inserts, 2) expands, 3) shrinks, 4) deletions, with object verification after each stage.

Note, the reason of this exercise is, because the semantics of max_shift == 0 have changed. A resize on inserts _before_ this change was impossible, now it becomes possible, so we have to disallow resizes (only) for the test case module specifically.

maintainer Acked-by
#5 lore raw

Re: [PATCH net 1/2] rhashtable: unconditionally grow when max_shift is not specified

Quoted 4 lines · Daniel Borkmann

Note, the reason of this exercise is, because the semantics of max_shift == 0 have changed. A resize on inserts _before_ this change was impossible, now it becomes possible, so we have to disallow resizes (only) for the test case module specifically.

OK, I see what you are doing here. I will work on an improved test case with parallel resizes after Herbert's rehashing.

#6 lore raw

PATCH 2/2 rhashtable: remove indirection for grow/shrink decision functions

In reply to Daniel Borkmann

Currently, all real users of rhashtable default their grow and shrink decision functions to rht_grow_above_75() and rht_shrink_below_30(), so that there's currently no need to have this explicitly selectable.

It can/should be generic and private inside rhashtable until a real use case pops up. Since we can make this private, we'll save us this additional indirection layer and can improve insertion/deletion time as well.

Reference: http://patchwork.ozlabs.org/patch/443040/

---
 include/linux/rhashtable.h | 13 -----------
 lib/rhashtable.c           | 56 ++++++++++++++--------------------------------
 lib/test_rhashtable.c      |  1 +
 net/netfilter/nft_hash.c   |  2 --
 net/netlink/af_netlink.c   |  2 --
 net/tipc/socket.c          |  2 --
 6 files changed, 18 insertions(+), 58 deletions(-)
include/linux/rhashtable.h +0 -13
index cb2104b..d438eeb 100644
@@ -79,12 +79,6 @@ struct rhashtable;
  * @locks_mul: Number of bucket locks to allocate per cpu (default: 128)
  * @hashfn: Function to hash key
  * @obj_hashfn: Function to hash object
- * @grow_decision: If defined, may return true if table should expand
- * @shrink_decision: If defined, may return true if table should shrink
- *
- * Note: when implementing the grow and shrink decision function, min/max
- * shift must be enforced, otherwise, resizing watermarks they set may be
- * useless.
  */
 struct rhashtable_params {
 	size_t			nelem_hint;
@@ -98,10 +92,6 @@ struct rhashtable_params {
 	size_t			locks_mul;
 	rht_hashfn_t		hashfn;
 	rht_obj_hashfn_t	obj_hashfn;
-	bool			(*grow_decision)(const struct rhashtable *ht,
-						 size_t new_size);
-	bool			(*shrink_decision)(const struct rhashtable *ht,
-						   size_t new_size);
 };
 
 /**
@@ -193,9 +183,6 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params);
 void rhashtable_insert(struct rhashtable *ht, struct rhash_head *node);
 bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *node);
 
-bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size);
-bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size);
-
 int rhashtable_expand(struct rhashtable *ht);
 int rhashtable_shrink(struct rhashtable *ht);
 
lib/rhashtable.c +17 -39

129 lines not on this page · raw message

lib/test_rhashtable.c +1 -0
index f9e9d73..67c7593 100644
@@ -201,6 +201,7 @@ static int __init test_rht_init(void)
 		.key_offset = offsetof(struct test_obj, value),
 		.key_len = sizeof(int),
 		.hashfn = jhash,
+		.max_shift = 1, /* we expand/shrink manually here */
 		.nulls_base = (3U << RHT_BASE_SHIFT),
 	};
 	int err;
net/netfilter/nft_hash.c +0 -2
index 61e6c40..c82df0a 100644
@@ -192,8 +192,6 @@ static int nft_hash_init(const struct nft_set *set,
 		.key_offset = offsetof(struct nft_hash_elem, key),
 		.key_len = set->klen,
 		.hashfn = jhash,
-		.grow_decision = rht_grow_above_75,
-		.shrink_decision = rht_shrink_below_30,
 	};
 
 	return rhashtable_init(priv, &params);
net/netlink/af_netlink.c +0 -2
index 2702673..05919bf 100644
@@ -3126,8 +3126,6 @@ static int __init netlink_proto_init(void)
 		.key_len = sizeof(u32), /* portid */
 		.hashfn = jhash,
 		.max_shift = 16, /* 64K */
-		.grow_decision = rht_grow_above_75,
-		.shrink_decision = rht_shrink_below_30,
 	};
 
 	if (err != 0)
net/tipc/socket.c +0 -2
index f73e975..b4d4467 100644
@@ -2364,8 +2364,6 @@ int tipc_sk_rht_init(struct net *net)
 		.hashfn = jhash,
 		.max_shift = 20, /* 1M */
 		.min_shift = 8,  /* 256 */
-		.grow_decision = rht_grow_above_75,
-		.shrink_decision = rht_shrink_below_30,
 	};
 
 	return rhashtable_init(&tn->sk_rht, &rht_params);
Signature · 1 line
1.9.3
#7 lore raw

RE: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

From: Daniel Borkmann

Quoted 8 lines

Currently, all real users of rhashtable default their grow and shrink decision functions to rht_grow_above_75() and rht_shrink_below_30(), so that there's currently no need to have this explicitly selectable.

It can/should be generic and private inside rhashtable until a real use case pops up. Since we can make this private, we'll save us this additional indirection layer and can improve insertion/deletion time as well.

...

lib/rhashtable.c static struct bucket_table *bucket_table_alloc(struct rhashtable *ht, · line 255

Quoted 6 lines
lib/rhashtable.c +1 -0
+static bool rht_grow_above_75(const struct rhashtable *ht, size_t new_size)
 {
 	/* Expand table when exceeding 75% load */
 	return atomic_read(&ht->nelems) > (new_size / 4 * 3) &&
 	       (!ht->p.max_shift || atomic_read(&ht->shift) < ht->p.max_shift);
 }

Why not cache the 'number of items before we need to expand' value after each expansion, setting it to 'infinite' when expansion is disabled. Then the above check is a simple comparison.
You probably don't even need an atomic_read() - provided something is double checked once the first test determines that an expansion is needed.

David

#8 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

On 02/25/2015 04:41 PM, David Laight wrote:
...

Quoted 5 lines

Why not cache the 'number of items before we need to expand' value after each expansion, setting it to 'infinite' when expansion is disabled. Then the above check is a simple comparison.
You probably don't even need an atomic_read() - provided something is double checked once the first test determines that an expansion is needed.

Did you read my cover letter? ;)

#9 lore raw

RE: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

From: Daniel Borkmann [

Quoted 9 lines · David Laight

...

Quoted 5 lines

Why not cache the 'number of items before we need to expand' value after each expansion, setting it to 'infinite' when expansion is disabled. Then the above check is a simple comparison.
You probably don't even need an atomic_read() - provided something is double checked once the first test determines that an expansion is needed.

Did you read my cover letter? ;)

I probably didn't infer the relevant references :-)

Actually even if some code wanted other rules, provided they are based on comparing the 'number of items' to a preset limit the limit could be set during expansion/contraction.

David

#10 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

Quoted 9 lines · David Laight

From: Daniel Borkmann [

Quoted 8 lines · David Laight

...

Quoted 5 lines

Why not cache the 'number of items before we need to expand' value after each expansion, setting it to 'infinite' when expansion is disabled. Then the above check is a simple comparison.
You probably don't even need an atomic_read() - provided something is double checked once the first test determines that an expansion is needed.

Quoted 7 lines
Quoted 1 line

Did you read my cover letter? ;)

I probably didn't infer the relevant references :-)

Actually even if some code wanted other rules, provided they are based on comparing the 'number of items' to a preset limit the limit could be set during expansion/contraction.

The shift itself doesn't need to be atomic, if we store that in the table directly instead of rhashtable, once on allocation it's being set and can stay immutable during its table lifetime.

The nelems can be a percpu_counter where we have a batched sync point and can make that dependent on the current table shift as we don't need to be overly precise, we can just read the sync'ed value. Currently, nelems are also being used by rhashtable users outside of the core code to track if we are still allowed to insert new elements, but I think we might also want to address that at some point.

#11 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

Quoted 7 lines · Daniel Borkmann

The nelems can be a percpu_counter where we have a batched sync point and can make that dependent on the current table shift as we don't need to be overly precise, we can just read the sync'ed value. Currently, nelems are also being used by rhashtable users outside of the core code to track if we are still allowed to insert new elements, but I think we might also want to address that at some point.

There is no need to track number of elements, using either an atomic_t or percpu_counter. This adds unnecessary burden.

1) Automatic shrinking is a non issue. This will free very little memory, compared to previous peak usage (including objects put in rhashtable). If hash grown to a certain point, it's likely it will grow again later.

2) Growing can be triggered when any bucket has more than X elems, and that is given for free at insert time.
X could be log2(buckets)/2 I guess. (aka shift/2)

A global limit on number of elements should be controlled by rhashtable users - if needed -, not in the rhashtable itself.

#12 lore raw

RE: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

From: Eric Dumazet
...

Quoted 4 lines

1) Automatic shrinking is a non issue. This will free very little memory, compared to previous peak usage (including objects put in rhashtable). If hash grown to a certain point, it's likely it will grow again later.

FWIW I tend to agree.

Quoted 3 lines

2) Growing can be triggered when any bucket has more than X elems, and that is given for free at insert time.
X could be log2(buckets)/2 I guess. (aka shift/2)

That won't work if someone is managing to break the hash function. You need some approximation to the total count as well.
OTOH there is no point growing the table if the current list isn't 'full'.

Quoted 2 lines

A global limit on number of elements should be controlled by rhashtable users - if needed -, not in the rhashtable itself.

Possibly you could require the user to give an approximation of the number of elements.

David

#13 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

Quoted 3 lines · David Laight

That won't work if someone is managing to break the hash function. You need some approximation to the total count as well.
OTOH there is no point growing the table if the current list isn't 'full'.

Well, if hash function is broken, having 1,000,000 elements in one bucket will kill your host, even if hash table has 1 million buckets.

Better find this out sooner than later.

#14 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

In reply to Eric Dumazet

On 02/25/2015 06:41 PM, Eric Dumazet wrote:
...

Quoted 7 lines

There is no need to track number of elements, using either an atomic_t or percpu_counter. This adds unnecessary burden.

1) Automatic shrinking is a non issue. This will free very little memory, compared to previous peak usage (including objects put in rhashtable). If hash grown to a certain point, it's likely it will grow again later.

So you are saying that shrinking is most likely a rather undesirable use-case in rhashtable?

Quoted 3 lines

2) Growing can be triggered when any bucket has more than X elems, and that is given for free at insert time.
X could be log2(buckets)/2 I guess. (aka shift/2)

Yes, I think such a facility can be added easily.

Quoted 2 lines

A global limit on number of elements should be controlled by rhashtable users - if needed -, not in the rhashtable itself.

Makes sense, thanks for the suggestion! I'll experiment with the above per bucket tracking a bit if you're okay with that, and also unfiddle the rht counter internals from netlink.

Thanks,
Daniel

#15 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

Quoted 5 lines · Daniel Borkmann

On 02/25/2015 06:41 PM, Eric Dumazet wrote:
...

Quoted 3 lines

There is no need to track number of elements, using either an atomic_t or percpu_counter. This adds unnecessary burden.

Quoted 7 lines
Quoted 4 lines

1) Automatic shrinking is a non issue. This will free very little memory, compared to previous peak usage (including objects put in rhashtable). If hash grown to a certain point, it's likely it will grow again later.

So you are saying that shrinking is most likely a rather undesirable use-case in rhashtable?

Main point of rhashtable is to start with a small/reasonable size, and only big consumers need to _expand_ the table.

Like, instead of having 512000 slots in TCP hash table, start with a 2^10 size.

Like my laptop currently has :

TCP established hash table entries: 131072 (order: 8, 1048576 bytes)

Which is kind of ridiculous....

But if any workload had to grow the table to 2^20 slots, we had to consume GB of memory anyway to hold sockets and everything.

Trying to shrink is simply not worth it, unless you expect your host never reboots and you desperately need back these 8 MBytes of memory.

#16 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

Quoted 24 lines · Eric Dumazet
Quoted 5 lines · Daniel Borkmann

On 02/25/2015 06:41 PM, Eric Dumazet wrote:
...

Quoted 3 lines

There is no need to track number of elements, using either an atomic_t or percpu_counter. This adds unnecessary burden.

Quoted 7 lines
Quoted 4 lines

1) Automatic shrinking is a non issue. This will free very little memory, compared to previous peak usage (including objects put in rhashtable). If hash grown to a certain point, it's likely it will grow again later.

So you are saying that shrinking is most likely a rather undesirable use-case in rhashtable?

Main point of rhashtable is to start with a small/reasonable size, and only big consumers need to _expand_ the table.

Like, instead of having 512000 slots in TCP hash table, start with a 2^10 size.

Like my laptop currently has :

TCP established hash table entries: 131072 (order: 8, 1048576 bytes)

Quoted 7 lines

Which is kind of ridiculous....

But if any workload had to grow the table to 2^20 slots, we had to consume GB of memory anyway to hold sockets and everything.

Trying to shrink is simply not worth it, unless you expect your host never reboots and you desperately need back these 8 MBytes of memory.

That may be true in the TCP case, but for not for nftables. We might have many sets and, especially when used to represent more complicated classification algorithms, their size might change by a lot.

#17 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

In reply to Eric Dumazet
Quoted 8 lines · Eric Dumazet

There is no need to track number of elements, using either an atomic_t or percpu_counter. This adds unnecessary burden.

1) Automatic shrinking is a non issue. This will free very little memory, compared to previous peak usage (including objects put in rhashtable). If hash grown to a certain point, it's likely it will grow again later.

Quoted 6 lines

2) Growing can be triggered when any bucket has more than X elems, and that is given for free at insert time.
X could be log2(buckets)/2 I guess. (aka shift/2)

A global limit on number of elements should be controlled by rhashtable users - if needed -, not in the rhashtable itself.

I don't think we need to kill shrink to get rid of the elements counters. It looks all users of shrink could trigger it manually by maintaing their own element counter, we just have to export the shrink function.

I just want to point out here that TCP is not the only future use case. The station table for mac80211 has recently been converted. We need to keep all of them on the radar.

maintainer
#18 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

From: "[email protected]" <[email protected]>
Date: Thu, 26 Feb 2015 10:02:35 +0000

Quoted 3 lines

I just want to point out here that TCP is not the only future use case. The station table for mac80211 has recently been converted. We need to keep all of them on the radar.

Just wanted to note in passing that I wonder how legal net/core/neighbour.c:neigh_hash_grow() is. It's growing an RCU hashtable without using rhashtable. :-)

#19 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

Quoted 10 lines · David Miller

From: "[email protected]" <[email protected]>
Date: Thu, 26 Feb 2015 10:02:35 +0000

Quoted 3 lines

I just want to point out here that TCP is not the only future use case. The station table for mac80211 has recently been converted. We need to keep all of them on the radar.

Just wanted to note in passing that I wonder how legal net/core/neighbour.c:neigh_hash_grow() is. It's growing an RCU hashtable without using rhashtable. :-)

I would like to note that it seem premature to convert all these users without having the fundamental problems solved, specifically the unbounded growing hash chains with async resizing.

It seems to me that we have enough use cases right now that problems have become quite visible, and until we're sure they're actually solvable for all these different use cases I'd advocate for not moving more subsystems to use this.

maintainer
#20 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

From: Patrick McHardy <[email protected]>
Date: Sat, 28 Feb 2015 00:48:40 +0000

Quoted 4 lines

It seems to me that we have enough use cases right now that problems have become quite visible, and until we're sure they're actually solvable for all these different use cases I'd advocate for not moving more subsystems to use this.

No objections.

#21 lore raw

RE: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

In reply to Eric Dumazet
Quoted 4 lines

1) Automatic shrinking is a non issue. This will free very little memory, compared to previous peak usage (including objects put in rhashtable). If hash grown to a certain point, it's likely it will grow again later.

Shrink could be done 'on demand' from the 'user' when the number of elements is known to have significantly reduced.

Quoted 3 lines

2) Growing can be triggered when any bucket has more than X elems, and that is given for free at insert time.
X could be log2(buckets)/2 I guess. (aka shift/2)

If growing is triggered when a bucket has more than X elems, then setting X very high will stop automatic growing.
Growing would then only be done in response to user requests.

Whether X should be constant, or log2(buckets)/n is another matter. Or something like N1 + (N2 * log2(buckets))/64 in any case it only needs recalculating after an auto-grow.

David

maintainer
#22 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

In reply to Eric Dumazet
Quoted 18 lines · Eric Dumazet
Quoted 7 lines · Daniel Borkmann

The nelems can be a percpu_counter where we have a batched sync point and can make that dependent on the current table shift as we don't need to be overly precise, we can just read the sync'ed value. Currently, nelems are also being used by rhashtable users outside of the core code to track if we are still allowed to insert new elements, but I think we might also want to address that at some point.

There is no need to track number of elements, using either an atomic_t or percpu_counter. This adds unnecessary burden.

1) Automatic shrinking is a non issue. This will free very little memory, compared to previous peak usage (including objects put in rhashtable). If hash grown to a certain point, it's likely it will grow again later.

Quoted 6 lines

2) Growing can be triggered when any bucket has more than X elems, and that is given for free at insert time.
X could be log2(buckets)/2 I guess. (aka shift/2)

A global limit on number of elements should be controlled by rhashtable users - if needed -, not in the rhashtable itself.

I agree in the strongest terms :)

Cheers,

Signature · 3 lines
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
maintainer
#23 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

Quoted 9 lines · Herbert Xu
Quoted 8 lines · Eric Dumazet

There is no need to track number of elements, using either an atomic_t or percpu_counter. This adds unnecessary burden.

1) Automatic shrinking is a non issue. This will free very little memory, compared to previous peak usage (including objects put in rhashtable). If hash grown to a certain point, it's likely it will grow again later.

Quoted 8 lines
Quoted 6 lines

2) Growing can be triggered when any bucket has more than X elems, and that is given for free at insert time.
X could be log2(buckets)/2 I guess. (aka shift/2)

A global limit on number of elements should be controlled by rhashtable users - if needed -, not in the rhashtable itself.

I agree in the strongest terms :)

I agree that the max elements should be enforced by users as done by Netlink right now. I'm also fine with ditching nelems from rhashtable as long as shrinking is covered. Patrick mentioned several times by now that nft sets want to have shrinking.

maintainer
#24 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

Quoted 5 lines · Thomas Graf

I agree that the max elements should be enforced by users as done by Netlink right now. I'm also fine with ditching nelems from rhashtable as long as shrinking is covered. Patrick mentioned several times by now that nft sets want to have shrinking.

My plan is to have expansions triggered solely through insert, either immediate or delayed, and shrinking will only be done when explicitly requested by the user.

Cheers,

Signature · 3 lines
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
maintainer Acked-by on v1 2/2
#25 lore raw

Re: [PATCH net 2/2] rhashtable: remove indirection for grow/shrink decision functions

In reply to Daniel Borkmann
Quoted 4 lines · Daniel Borkmann

Currently, all real users of rhashtable default their grow and shrink decision functions to rht_grow_above_75() and rht_shrink_below_30(), so that there's currently no need to have this explicitly selectable.

Quoted 8 lines

It can/should be generic and private inside rhashtable until a real use case pops up. Since we can make this private, we'll save us this additional indirection layer and can improve insertion/deletion time as well.

Reference: http://patchwork.ozlabs.org/patch/443040/

Nice

maintainer
#26 lore raw
In reply to Daniel Borkmann

From: Daniel Borkmann <[email protected]>
Date: Wed, 25 Feb 2015 16:31:52 +0100

Quoted 9 lines

As discussed, I'm sending out rhashtable fixups for -net.

I have a couple of more patches I was working on last week pending, i.e. to get rid of ht->nelems and ht->shift atomic operations which speed-up pure insertions/deletions, e.g. on my laptop I have 2 threads, inserting 7M entries each, that will reduce insertion time from ~1,450 ms to 865 ms (performance should even be better after removing the grow/shrink indirections). I guess that however is rather something for net-next.

Series applied, thanks.