[PATCH 0/4] rhashtable hash cleanups

[PATCH 0/4] rhashtable hash cleanups

[Herbert Xu]

Hi:

Nothing to see here, just a bunch of simple clean-ups before
I move onto something more substantial (hopefully).

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

[PATCH 1/4] rhashtable: Move masking back into key_hashfn

[Herbert Xu]

This patch reverts commit c88455ce50ae4224d84960ce2baa53e61580df27
("rhashtable: key_hashfn() must return full hash value") because
the only user of it always masks the hash value.

Signed-off-by: Herbert Xu <herbert.xu@redhat.com>
---

 lib/rhashtable.c |    5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index b1c19c5..7661056 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -83,7 +83,8 @@ static u32 obj_raw_hashfn(struct rhashtable *ht,
 static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
 		      const void *key, u32 len)
 {
-	return ht->p.hashfn(key, len, tbl->hash_rnd) >> HASH_RESERVED_SPACE;
+	return rht_bucket_index(tbl, ht->p.hashfn(key, len, tbl->hash_rnd) >>
+				     HASH_RESERVED_SPACE);
 }
 
 static u32 head_hashfn(struct rhashtable *ht,
@@ -622,7 +623,7 @@ void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
 	tbl = rht_dereference_rcu(ht->tbl, ht);
 	hash = key_hashfn(ht, tbl, key, ht->p.key_len);
 restart:
-	rht_for_each_rcu(he, tbl, rht_bucket_index(tbl, hash)) {
+	rht_for_each_rcu(he, tbl, hash) {
 		if (!compare(rht_obj(ht, he), arg))
 			continue;
 		rcu_read_unlock();

[PATCH 2/4] rhashtable: Use head_hashfn instead of obj_raw_hashfn

[Herbert Xu]

Now that we don't have cross-table hashes, we no longer need to
keep the entire hash value so all users of obj_raw_hashfn can
use head_hashfn instead.

Signed-off-by: Herbert Xu <herbert.xu@redhat.com>
---

 lib/rhashtable.c |   12 +++++-------
 1 file changed, 5 insertions(+), 7 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 7661056..0bda8dd 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -403,7 +403,7 @@ static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 	rcu_read_lock();
 
 	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = obj_raw_hashfn(ht, old_tbl, rht_obj(ht, obj));
+	hash = head_hashfn(ht, old_tbl, obj);
 
 	spin_lock_bh(bucket_lock(old_tbl, hash));
 
@@ -415,7 +415,7 @@ static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 	 */
 	tbl = rht_dereference_rcu(ht->future_tbl, ht);
 	if (tbl != old_tbl) {
-		hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+		hash = head_hashfn(ht, tbl, obj);
 		spin_lock(bucket_lock(tbl, hash));
 	}
 
@@ -428,7 +428,6 @@ static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 
 	no_resize_running = tbl == old_tbl;
 
-	hash = rht_bucket_index(tbl, hash);
 	head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
 
 	if (rht_is_a_nulls(head))
@@ -444,11 +443,11 @@ static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 
 exit:
 	if (tbl != old_tbl) {
-		hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+		hash = head_hashfn(ht, tbl, obj);
 		spin_unlock(bucket_lock(tbl, hash));
 	}
 
-	hash = obj_raw_hashfn(ht, old_tbl, rht_obj(ht, obj));
+	hash = head_hashfn(ht, old_tbl, obj);
 	spin_unlock_bh(bucket_lock(old_tbl, hash));
 
 	rcu_read_unlock();
@@ -487,9 +486,8 @@ static bool __rhashtable_remove(struct rhashtable *ht,
 	unsigned hash;
 	bool ret = false;
 
-	hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+	hash = head_hashfn(ht, tbl, obj);
 	lock = bucket_lock(tbl, hash);
-	hash = rht_bucket_index(tbl, hash);
 
 	spin_lock_bh(lock);
 

[PATCH 3/4] rhashtable: Remove key length argument to key_hashfn

[Herbert Xu]

key_hashfn has only one caller and it doesn't really need to supply
the key length as an extra parameter.

Signed-off-by: Herbert Xu <herbert.xu@redhat.com>
---

 lib/rhashtable.c |    7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 0bda8dd..91b52da 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -81,9 +81,10 @@ static u32 obj_raw_hashfn(struct rhashtable *ht,
 }
 
 static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
-		      const void *key, u32 len)
+		      const void *key)
 {
-	return rht_bucket_index(tbl, ht->p.hashfn(key, len, tbl->hash_rnd) >>
+	return rht_bucket_index(tbl, ht->p.hashfn(key, ht->p.key_len,
+						  tbl->hash_rnd) >>
 				     HASH_RESERVED_SPACE);
 }
 
@@ -619,7 +620,7 @@ void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
 	rcu_read_lock();
 
 	tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = key_hashfn(ht, tbl, key, ht->p.key_len);
+	hash = key_hashfn(ht, tbl, key);
 restart:
 	rht_for_each_rcu(he, tbl, hash) {
 		if (!compare(rht_obj(ht, he), arg))

[PATCH 4/4] rhashtable: Remove obj_raw_hashfn

[Herbert Xu]

Now that the only caller of obj_raw_hashfn is head_hashfn, we can
simply kill it and fold it into the latter.

This patch also moves the common shift from head_hashfn/key_hashfn
into rht_bucket_index.

Signed-off-by: Herbert Xu <herbert.xu@redhat.com>
---

 lib/rhashtable.c |   25 +++++++------------------
 1 file changed, 7 insertions(+), 18 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 91b52da..5f9af45 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -63,36 +63,25 @@ static void *rht_obj(const struct rhashtable *ht, const struct rhash_head *he)
 
 static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
 {
-	return hash & (tbl->size - 1);
-}
-
-static u32 obj_raw_hashfn(struct rhashtable *ht,
-			  const struct bucket_table *tbl, const void *ptr)
-{
-	u32 hash;
-
-	if (unlikely(!ht->p.key_len))
-		hash = ht->p.obj_hashfn(ptr, tbl->hash_rnd);
-	else
-		hash = ht->p.hashfn(ptr + ht->p.key_offset, ht->p.key_len,
-				    tbl->hash_rnd);
-
-	return hash >> HASH_RESERVED_SPACE;
+	return (hash >> HASH_RESERVED_SPACE) & (tbl->size - 1);
 }
 
 static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
 		      const void *key)
 {
 	return rht_bucket_index(tbl, ht->p.hashfn(key, ht->p.key_len,
-						  tbl->hash_rnd) >>
-				     HASH_RESERVED_SPACE);
+						  tbl->hash_rnd));
 }
 
 static u32 head_hashfn(struct rhashtable *ht,
 		       const struct bucket_table *tbl,
 		       const struct rhash_head *he)
 {
-	return rht_bucket_index(tbl, obj_raw_hashfn(ht, tbl, rht_obj(ht, he)));
+	const char *ptr = rht_obj(ht, he);
+
+	return likely(ht->p.key_len) ?
+	       key_hashfn(ht, tbl, ptr + ht->p.key_offset) :
+	       rht_bucket_index(tbl, ht->p.obj_hashfn(ptr, tbl->hash_rnd));
 }
 
 #ifdef CONFIG_PROVE_LOCKING

[PATCH 0/4 v2] rhashtable hash cleanups

[Herbert Xu]

Hi:

This is a rebase on top of the nested lock annotation fix.

Nothing to see here, just a bunch of simple clean-ups before
I move onto something more substantial (hopefully).

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

[PATCH 1/4] rhashtable: Move masking back into key_hashfn

[Herbert Xu]

This patch reverts commit c88455ce50ae4224d84960ce2baa53e61580df27
("rhashtable: key_hashfn() must return full hash value") because
the only user of it always masks the hash value.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---

 lib/rhashtable.c |    5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index d7f3db5..ff9cc33 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -83,7 +83,8 @@ static u32 obj_raw_hashfn(struct rhashtable *ht,
 static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
 		      const void *key, u32 len)
 {
-	return ht->p.hashfn(key, len, tbl->hash_rnd) >> HASH_RESERVED_SPACE;
+	return rht_bucket_index(tbl, ht->p.hashfn(key, len, tbl->hash_rnd) >>
+				     HASH_RESERVED_SPACE);
 }
 
 static u32 head_hashfn(struct rhashtable *ht,
@@ -622,7 +623,7 @@ void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
 	tbl = rht_dereference_rcu(ht->tbl, ht);
 	hash = key_hashfn(ht, tbl, key, ht->p.key_len);
 restart:
-	rht_for_each_rcu(he, tbl, rht_bucket_index(tbl, hash)) {
+	rht_for_each_rcu(he, tbl, hash) {
 		if (!compare(rht_obj(ht, he), arg))
 			continue;
 		rcu_read_unlock();

[PATCH 2/4] rhashtable: Use head_hashfn instead of obj_raw_hashfn

[Herbert Xu]

Now that we don't have cross-table hashes, we no longer need to
keep the entire hash value so all users of obj_raw_hashfn can
use head_hashfn instead.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---

 lib/rhashtable.c |   12 +++++-------
 1 file changed, 5 insertions(+), 7 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index ff9cc33..03fdaf8 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -403,7 +403,7 @@ static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 	rcu_read_lock();
 
 	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = obj_raw_hashfn(ht, old_tbl, rht_obj(ht, obj));
+	hash = head_hashfn(ht, old_tbl, obj);
 
 	spin_lock_bh(bucket_lock(old_tbl, hash));
 
@@ -415,7 +415,7 @@ static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 	 */
 	tbl = rht_dereference_rcu(ht->future_tbl, ht);
 	if (tbl != old_tbl) {
-		hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+		hash = head_hashfn(ht, tbl, obj);
 		spin_lock_nested(bucket_lock(tbl, hash), RHT_LOCK_NESTED);
 	}
 
@@ -428,7 +428,6 @@ static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 
 	no_resize_running = tbl == old_tbl;
 
-	hash = rht_bucket_index(tbl, hash);
 	head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
 
 	if (rht_is_a_nulls(head))
@@ -444,11 +443,11 @@ static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 
 exit:
 	if (tbl != old_tbl) {
-		hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+		hash = head_hashfn(ht, tbl, obj);
 		spin_unlock(bucket_lock(tbl, hash));
 	}
 
-	hash = obj_raw_hashfn(ht, old_tbl, rht_obj(ht, obj));
+	hash = head_hashfn(ht, old_tbl, obj);
 	spin_unlock_bh(bucket_lock(old_tbl, hash));
 
 	rcu_read_unlock();
@@ -487,9 +486,8 @@ static bool __rhashtable_remove(struct rhashtable *ht,
 	unsigned hash;
 	bool ret = false;
 
-	hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+	hash = head_hashfn(ht, tbl, obj);
 	lock = bucket_lock(tbl, hash);
-	hash = rht_bucket_index(tbl, hash);
 
 	spin_lock_bh(lock);
 

[PATCH 3/4] rhashtable: Remove key length argument to key_hashfn

[Herbert Xu]

key_hashfn has only one caller and it doesn't really need to supply
the key length as an extra parameter.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---

 lib/rhashtable.c |    7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 03fdaf8..838cccc 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -81,9 +81,10 @@ static u32 obj_raw_hashfn(struct rhashtable *ht,
 }
 
 static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
-		      const void *key, u32 len)
+		      const void *key)
 {
-	return rht_bucket_index(tbl, ht->p.hashfn(key, len, tbl->hash_rnd) >>
+	return rht_bucket_index(tbl, ht->p.hashfn(key, ht->p.key_len,
+						  tbl->hash_rnd) >>
 				     HASH_RESERVED_SPACE);
 }
 
@@ -619,7 +620,7 @@ void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
 	rcu_read_lock();
 
 	tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = key_hashfn(ht, tbl, key, ht->p.key_len);
+	hash = key_hashfn(ht, tbl, key);
 restart:
 	rht_for_each_rcu(he, tbl, hash) {
 		if (!compare(rht_obj(ht, he), arg))

[PATCH 4/4] rhashtable: Remove obj_raw_hashfn

[Herbert Xu]

Now that the only caller of obj_raw_hashfn is head_hashfn, we can
simply kill it and fold it into the latter.

This patch also moves the common shift from head_hashfn/key_hashfn
into rht_bucket_index.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---

 lib/rhashtable.c |   25 +++++++------------------
 1 file changed, 7 insertions(+), 18 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 838cccc..6ffc793 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -63,36 +63,25 @@ static void *rht_obj(const struct rhashtable *ht, const struct rhash_head *he)
 
 static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
 {
-	return hash & (tbl->size - 1);
-}
-
-static u32 obj_raw_hashfn(struct rhashtable *ht,
-			  const struct bucket_table *tbl, const void *ptr)
-{
-	u32 hash;
-
-	if (unlikely(!ht->p.key_len))
-		hash = ht->p.obj_hashfn(ptr, tbl->hash_rnd);
-	else
-		hash = ht->p.hashfn(ptr + ht->p.key_offset, ht->p.key_len,
-				    tbl->hash_rnd);
-
-	return hash >> HASH_RESERVED_SPACE;
+	return (hash >> HASH_RESERVED_SPACE) & (tbl->size - 1);
 }
 
 static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
 		      const void *key)
 {
 	return rht_bucket_index(tbl, ht->p.hashfn(key, ht->p.key_len,
-						  tbl->hash_rnd) >>
-				     HASH_RESERVED_SPACE);
+						  tbl->hash_rnd));
 }
 
 static u32 head_hashfn(struct rhashtable *ht,
 		       const struct bucket_table *tbl,
 		       const struct rhash_head *he)
 {
-	return rht_bucket_index(tbl, obj_raw_hashfn(ht, tbl, rht_obj(ht, he)));
+	const char *ptr = rht_obj(ht, he);
+
+	return likely(ht->p.key_len) ?
+	       key_hashfn(ht, tbl, ptr + ht->p.key_offset) :
+	       rht_bucket_index(tbl, ht->p.obj_hashfn(ptr, tbl->hash_rnd));
 }
 
 #ifdef CONFIG_PROVE_LOCKING

Re: [PATCH 1/4] rhashtable: Move masking back into key_hashfn

[Thomas Graf]

On 03/12/15 at 02:49pm, Herbert Xu wrote:
> This patch reverts commit c88455ce50ae4224d84960ce2baa53e61580df27
> ("rhashtable: key_hashfn() must return full hash value") because
> the only user of it always masks the hash value.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Need for this is gone with new rehashing.

Acked-by: Thomas Graf <tgraf@suug.ch>

Re: [PATCH 2/4] rhashtable: Use head_hashfn instead of obj_raw_hashfn

[Thomas Graf]

On 03/12/15 at 02:49pm, Herbert Xu wrote:
> Now that we don't have cross-table hashes, we no longer need to
> keep the entire hash value so all users of obj_raw_hashfn can
> use head_hashfn instead.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Acked-by: Thomas Graf <tgraf@suug.ch>

Re: [PATCH 3/4] rhashtable: Remove key length argument to key_hashfn

[Thomas Graf]

On 03/12/15 at 02:49pm, Herbert Xu wrote:
> key_hashfn has only one caller and it doesn't really need to supply
> the key length as an extra parameter.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Acked-by: Thomas Graf <tgraf@suug.ch>

Re: [PATCH 4/4] rhashtable: Remove obj_raw_hashfn

[Thomas Graf]

On 03/12/15 at 02:49pm, Herbert Xu wrote:
> Now that the only caller of obj_raw_hashfn is head_hashfn, we can
> simply kill it and fold it into the latter.
> 
> This patch also moves the common shift from head_hashfn/key_hashfn
> into rht_bucket_index.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Acked-by: Thomas Graf <tgraf@suug.ch>

Re: [PATCH 0/4 v2] rhashtable hash cleanups

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Thu, 12 Mar 2015 14:49:23 +1100

> This is a rebase on top of the nested lock annotation fix.
> 
> Nothing to see here, just a bunch of simple clean-ups before
> I move onto something more substantial (hopefully).

I've applied this series, but please look into the bug Thomas
reported before making any further changes to rhashtable.

Thanks.