[PATCH v2 net-next 0/3] rhashtable: Wildcard and scored lookups

[PATCH v2 net-next 0/3] rhashtable: Wildcard and scored lookups

[Tom Herbert]

This patch set implements:
  - A compare function can be passed in the lookup. This allows for
    comparison to include "wildcard fields"
  - Order insertion within a bucket, so that entries with more specific
    information can be matched first.
  - Scored lookups. This is like the socket lookups. It allows
    different levels of matching, and returning one of N possible
    best matches with a uniform distribution based on flow hash.

Testing: Tested this in conjunction with ILA development. Will be
posting ILA patches shortly.

V2:
 - Added rhashtable_lookup_ordered_cmpfn to ensure that greatest
   ordered matching entry is found during rehashing
 - Minor cleanup to scored lookup patch

Tom Herbert (3):
  rhashtable: Allow lookup function to have compare function agument
  rhashtable: Add a function for in order insertion and lookup in
    buckets
  rhashtable: Add scored lookups

 include/linux/rhashtable.h | 194 +++++++++++++++++++++++++++++++++++++++++++--
 lib/rhashtable.c           |  20 ++---
 2 files changed, 196 insertions(+), 18 deletions(-)

-- 
1.8.1

[PATCH v2 net-next 1/3] rhashtable: Allow lookup function to have compare function agument

[Tom Herbert]

Added rhashtable_lookup_fast_cmpfn which does a lookup in an rhash table
with the compare function being taken from an argument. This allows
different compare functions to be used on the same table.

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 include/linux/rhashtable.h | 20 +++++++++++++++-----
 1 file changed, 15 insertions(+), 5 deletions(-)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 843ceca..78a4e9b 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -513,19 +513,21 @@ static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
 }
 
 /**
- * rhashtable_lookup_fast - search hash table, inlined version
+ * rhashtable_lookup_fast_cmpfn - search hash table, inlined version
  * @ht:		hash table
  * @key:	the pointer to the key
  * @params:	hash table parameters
+ * @obj_cmpfn:	compare function
  *
  * Computes the hash value for the key and traverses the bucket chain looking
  * for a entry with an identical key. The first matching entry is returned.
  *
  * Returns the first entry on which the compare function returned true.
  */
-static inline void *rhashtable_lookup_fast(
+static inline void *rhashtable_lookup_fast_cmpfn(
 	struct rhashtable *ht, const void *key,
-	const struct rhashtable_params params)
+	const struct rhashtable_params params,
+	rht_obj_cmpfn_t obj_cmpfn)
 {
 	struct rhashtable_compare_arg arg = {
 		.ht = ht,
@@ -541,8 +543,8 @@ static inline void *rhashtable_lookup_fast(
 restart:
 	hash = rht_key_hashfn(ht, tbl, key, params);
 	rht_for_each_rcu(he, tbl, hash) {
-		if (params.obj_cmpfn ?
-		    params.obj_cmpfn(&arg, rht_obj(ht, he)) :
+		if (obj_cmpfn ?
+		    obj_cmpfn(&arg, rht_obj(ht, he)) :
 		    rhashtable_compare(&arg, rht_obj(ht, he)))
 			continue;
 		rcu_read_unlock();
@@ -560,6 +562,14 @@ restart:
 	return NULL;
 }
 
+static inline void *rhashtable_lookup_fast(
+	struct rhashtable *ht, const void *key,
+	const struct rhashtable_params params)
+{
+	return rhashtable_lookup_fast_cmpfn(ht, key, params,
+					    params.obj_cmpfn);
+}
+
 /* Internal function, please use rhashtable_insert_fast() instead */
 static inline int __rhashtable_insert_fast(
 	struct rhashtable *ht, const void *key, struct rhash_head *obj,
-- 
1.8.1

[PATCH v2 net-next 2/3] rhashtable: Add a function for in order insertion and lookup in buckets

[Tom Herbert]

The obj_orderfn function may be specified in the parameters for a
rhashtable. When inserting an element this function is used to order
objects in a bucket list (greatest to least ordering value).This
allows entries to have wild card fields, where entries with
more specific information match are placed first in the bucket.
When a lookup is done, the first match found will contain
the most specific match.

In order to maintain ordering guarantees during rehash, the
rhashtable_lookup_ordered_cmpfn was added. This function will check
future tables for matches that would have a greater insertion order
than a match found in an older table.

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 include/linux/rhashtable.h | 108 +++++++++++++++++++++++++++++++++++++++++++--
 lib/rhashtable.c           |  20 ++++-----
 2 files changed, 115 insertions(+), 13 deletions(-)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 78a4e9b..651b5226 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -92,6 +92,7 @@ typedef u32 (*rht_hashfn_t)(const void *data, u32 len, u32 seed);
 typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
 			       const void *obj);
+typedef int (*rht_obj_orderfn_t)(const void *obj);
 
 struct rhashtable;
 
@@ -111,6 +112,7 @@ struct rhashtable;
  * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
  * @obj_hashfn: Function to hash object
  * @obj_cmpfn: Function to compare key with object
+ * @obj_orderfn: Function to order an object for in-order insertion
  */
 struct rhashtable_params {
 	size_t			nelem_hint;
@@ -127,6 +129,7 @@ struct rhashtable_params {
 	rht_hashfn_t		hashfn;
 	rht_obj_hashfn_t	obj_hashfn;
 	rht_obj_cmpfn_t		obj_cmpfn;
+	rht_obj_orderfn_t	obj_orderfn;
 };
 
 /**
@@ -570,6 +573,104 @@ static inline void *rhashtable_lookup_fast(
 					    params.obj_cmpfn);
 }
 
+/**
+ * rhashtable_lookup_ordered_cmpfn - search table that uses ordered insertion
+ * @ht:		hash table
+ * @key:	the pointer to the key
+ * @params:	hash table parameters
+ * @obj_cmpfn:	compare function
+ *
+ * Computes the hash value for the key and traverses the bucket chain looking
+ * for a entry that matches the key. The bucket chains are assumed to be
+ * ordered. When a match is found this is recorded as a candidate. The
+ * search proceeds to future tables (rehash is in progress) to check is there
+ * is match which which have greater ordering precedence.
+ *
+ * Returns the first entry on which the compare function returned true adhering
+ * to ordering guarantee.
+ */
+static inline void *rhashtable_lookup_ordered_cmpfn(
+	struct rhashtable *ht, const void *key,
+	const struct rhashtable_params params,
+	rht_obj_cmpfn_t obj_cmpfn)
+{
+	struct rhashtable_compare_arg arg = {
+		.ht = ht,
+		.key = key,
+	};
+	const struct bucket_table *tbl;
+	struct rhash_head *he, *result = NULL;
+	unsigned int hash;
+
+	rcu_read_lock();
+
+	tbl = rht_dereference_rcu(ht->tbl, ht);
+restart:
+	hash = rht_key_hashfn(ht, tbl, key, params);
+	rht_for_each_rcu(he, tbl, hash) {
+		if (obj_cmpfn ?
+		    obj_cmpfn(&arg, rht_obj(ht, he)) :
+		    rhashtable_compare(&arg, rht_obj(ht, he)))
+			continue;
+		if (unlikely(result)) {
+			if (params.obj_orderfn(he) > params.obj_orderfn(result))
+				result = he;
+		} else {
+			result = he;
+		}
+		break;
+	}
+
+	/* Ensure we see any new tables. */
+	smp_rmb();
+
+	tbl = rht_dereference_rcu(tbl->future_tbl, ht);
+	if (unlikely(tbl))
+		goto restart;
+	rcu_read_unlock();
+
+	return result ? rht_obj(ht, result) : NULL;
+}
+
+static inline void *rhashtable_lookup_ordered(
+	struct rhashtable *ht, const void *key,
+	const struct rhashtable_params params)
+{
+	return rhashtable_lookup_ordered_cmpfn(ht, key, params,
+					      params.obj_cmpfn);
+}
+
+struct rht_insert_pos {
+	struct rhash_head __rcu *head;
+	struct rhash_head __rcu **pos;
+};
+
+static inline void rht_insert_pos(struct rhashtable *ht,
+				  struct rhash_head *obj,
+				  struct bucket_table *tbl,
+				  unsigned int hash,
+				  struct rht_insert_pos *ipos)
+{
+	struct rhash_head __rcu *head, **pos;
+
+	pos = &tbl->buckets[hash];
+
+	if (ht->p.obj_orderfn) {
+		int obj_order = ht->p.obj_orderfn(rht_obj(ht, obj));
+
+		rht_for_each_rcu(head, tbl, hash) {
+			if (ht->p.obj_orderfn(rht_obj(ht, head)) <= obj_order)
+				break;
+			pos = &head->next;
+		}
+	} else {
+		head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
+	}
+
+	ipos->head = head;
+	ipos->pos = pos;
+}
+
 /* Internal function, please use rhashtable_insert_fast() instead */
 static inline int __rhashtable_insert_fast(
 	struct rhashtable *ht, const void *key, struct rhash_head *obj,
@@ -581,6 +682,7 @@ static inline int __rhashtable_insert_fast(
 	};
 	struct bucket_table *tbl, *new_tbl;
 	struct rhash_head *head;
+	struct rht_insert_pos ipos;
 	spinlock_t *lock;
 	unsigned int elasticity;
 	unsigned int hash;
@@ -643,11 +745,11 @@ slow_path:
 
 	err = 0;
 
-	head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
+	rht_insert_pos(ht, obj, tbl, hash, &ipos);
 
-	RCU_INIT_POINTER(obj->next, head);
+	RCU_INIT_POINTER(obj->next, ipos.head);
 
-	rcu_assign_pointer(tbl->buckets[hash], obj);
+	rcu_assign_pointer(*ipos.pos, obj);
 
 	atomic_inc(&ht->nelems);
 	if (rht_grow_above_75(ht, tbl))
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index cc0c697..0e09524 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -162,9 +162,10 @@ static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)
 		rht_dereference_rcu(old_tbl->future_tbl, ht));
 	struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
 	int err = -ENOENT;
-	struct rhash_head *head, *next, *entry;
+	struct rhash_head *next, *entry;
 	spinlock_t *new_bucket_lock;
 	unsigned int new_hash;
+	struct rht_insert_pos ipos;
 
 	rht_for_each(entry, old_tbl, old_hash) {
 		err = 0;
@@ -184,15 +185,14 @@ static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)
 	new_bucket_lock = rht_bucket_lock(new_tbl, new_hash);
 
 	spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING);
-	head = rht_dereference_bucket(new_tbl->buckets[new_hash],
-				      new_tbl, new_hash);
+	rht_insert_pos(ht, entry, new_tbl, new_hash, &ipos);
 
-	if (rht_is_a_nulls(head))
+	if (rht_is_a_nulls(ipos.head))
 		INIT_RHT_NULLS_HEAD(entry->next, ht, new_hash);
 	else
-		RCU_INIT_POINTER(entry->next, head);
+		RCU_INIT_POINTER(entry->next, ipos.head);
 
-	rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
+	rcu_assign_pointer(*ipos.pos, entry);
 	spin_unlock(new_bucket_lock);
 
 	rcu_assign_pointer(*pprev, next);
@@ -436,7 +436,7 @@ int rhashtable_insert_slow(struct rhashtable *ht, const void *key,
 			   struct rhash_head *obj,
 			   struct bucket_table *tbl)
 {
-	struct rhash_head *head;
+	struct rht_insert_pos ipos;
 	unsigned int hash;
 	int err;
 
@@ -459,11 +459,11 @@ int rhashtable_insert_slow(struct rhashtable *ht, const void *key,
 
 	err = 0;
 
-	head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
+	rht_insert_pos(ht, obj, tbl, hash, &ipos);
 
-	RCU_INIT_POINTER(obj->next, head);
+	RCU_INIT_POINTER(obj->next, ipos.head);
 
-	rcu_assign_pointer(tbl->buckets[hash], obj);
+	rcu_assign_pointer(*ipos.pos, obj);
 
 	atomic_inc(&ht->nelems);
 
-- 
1.8.1

[PATCH v2 net-next 3/3] rhashtable: Add scored lookups

[Tom Herbert]

This patch adds a mechanism to do scored lookups in an rhashtable.
This mechanism is based on the UDP and TCP listener socket lookup
functions.

When a bucket is traversed, a matching score is computed for each entry
and the input key. The entry with the greatest non-zero score is
returned, and if there are multiple entries with the highest score then
one entry is selected by modulo on a hash value for the key (which must
be separate from the hash used to determine the bucket).

Signed-off-by: Tom Herbert <tom@herbertland.com>
---
 include/linux/rhashtable.h | 66 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 651b5226..13aa3f9 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -24,6 +24,7 @@
 #include <linux/list_nulls.h>
 #include <linux/workqueue.h>
 #include <linux/mutex.h>
+#include <linux/random.h>
 #include <linux/rcupdate.h>
 
 /*
@@ -93,6 +94,8 @@ typedef u32 (*rht_obj_hashfn_t)(const void *data, u32 len, u32 seed);
 typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
 			       const void *obj);
 typedef int (*rht_obj_orderfn_t)(const void *obj);
+typedef unsigned int (*rht_obj_scorefn_t)(struct rhashtable_compare_arg *arg,
+					  const void *obj);
 
 struct rhashtable;
 
@@ -515,6 +518,69 @@ static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
 	return memcmp(ptr + ht->p.key_offset, arg->key, ht->p.key_len);
 }
 
+
+/**
+ * rhashtable_lookup_scored - search hash table with scoring
+ * @ht:		hash table
+ * @key:	the pointer to the key
+ * @params:	hash table parameters
+ * @obj_scorefn: Scoring function
+ * @flow_hash:	hash value used to select when multiple matches are found
+ *
+ * Computes the hash value for the key and traverses the bucket chain computing
+ * a match score for each object on the list and the key. The entry with the
+ * highest score is returned. If there is more than one entry with the highest
+ * score, then one of the entries is selected based on a hash of the input key.
+ */
+static inline void *rhashtable_lookup_scored(
+	struct rhashtable *ht, const void *key,
+	const struct rhashtable_params params,
+	rht_obj_scorefn_t obj_scorefn,
+	unsigned int flow_hash)
+{
+	struct rhashtable_compare_arg arg = {
+		.ht = ht,
+		.key = key,
+	};
+	const struct bucket_table *tbl;
+	struct rhash_head *he, *result = NULL;
+	unsigned int hash, score;
+	unsigned int best_score = 0, khash = 0;
+	int matches = 0;
+
+	rcu_read_lock();
+
+	tbl = rht_dereference_rcu(ht->tbl, ht);
+restart:
+	hash = rht_key_hashfn(ht, tbl, key, params);
+	rht_for_each_rcu(he, tbl, hash) {
+		score = obj_scorefn(&arg, rht_obj(ht, he));
+		if (!score) {
+			continue;
+		} else if (score > best_score) {
+			result = he;
+			best_score = score;
+			matches = 1;
+			khash = flow_hash;
+		} else if (score == best_score) {
+			matches++;
+			if (reciprocal_scale(khash, matches) == 0)
+				result = he;
+			khash = next_pseudo_random32(khash);
+		}
+	}
+
+	/* Ensure we see any new tables. */
+	smp_rmb();
+
+	tbl = rht_dereference_rcu(tbl->future_tbl, ht);
+	if (unlikely(tbl))
+		goto restart;
+	rcu_read_unlock();
+
+	return result ? rht_obj(ht, result) : NULL;
+}
+
 /**
  * rhashtable_lookup_fast_cmpfn - search hash table, inlined version
  * @ht:		hash table
-- 
1.8.1

Re: [PATCH v2 net-next 3/3] rhashtable: Add scored lookups

[Herbert Xu]

On Tue, Jul 14, 2015 at 04:45:49PM -0700, Tom Herbert wrote:
>
> +		} else if (score == best_score) {
> +			matches++;
> +			if (reciprocal_scale(khash, matches) == 0)
> +				result = he;
> +			khash = next_pseudo_random32(khash);
> +		}

Note that during a rehash you can encounter the same object multiple
times, does this logic still work in that case?

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

Re: [PATCH v2 net-next 3/3] rhashtable: Add scored lookups

[Tom Herbert]

On Tue, Jul 14, 2015 at 5:18 PM, Herbert Xu <herbert@gondor.apana.org.au> wrote:
> On Tue, Jul 14, 2015 at 04:45:49PM -0700, Tom Herbert wrote:
>>
>> +             } else if (score == best_score) {
>> +                     matches++;
>> +                     if (reciprocal_scale(khash, matches) == 0)
>> +                             result = he;
>> +                     khash = next_pseudo_random32(khash);
>> +             }
>
> Note that during a rehash you can encounter the same object multiple
> times, does this logic still work in that case?
>
I would think. The property being supported here is uniform
distribution, *not* consistency.

Tom

> 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

Re: [PATCH v2 net-next 2/3] rhashtable: Add a function for in order insertion and lookup in buckets

[Herbert Xu]

On Tue, Jul 14, 2015 at 04:45:48PM -0700, Tom Herbert wrote:
> The obj_orderfn function may be specified in the parameters for a
> rhashtable. When inserting an element this function is used to order
> objects in a bucket list (greatest to least ordering value).This
> allows entries to have wild card fields, where entries with
> more specific information match are placed first in the bucket.
> When a lookup is done, the first match found will contain
> the most specific match.
> 
> In order to maintain ordering guarantees during rehash, the
> rhashtable_lookup_ordered_cmpfn was added. This function will check
> future tables for matches that would have a greater insertion order
> than a match found in an older table.
> 
> Signed-off-by: Tom Herbert <tom@herbertland.com>

There is another problem with exposing rhashtable directly to these
duplicate entries.  It breaks the logic on when to resize.  In the
worst case on a server with a single port you can end up with a
large hash table where everything is stored in a single chain.

Granted you can work around this by teaching rhashtable to count
identical entries as a single entry.  But I really think it's much
easier to just have this logic sit on top of rhashtable instead of
inside it.

The memory cost is merely 8 bytes per local port, is it really too
much?

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

Re: [PATCH v2 net-next 2/3] rhashtable: Add a function for in order insertion and lookup in buckets

[Tom Herbert]

On Tue, Jul 14, 2015 at 10:54 PM, Herbert Xu
<herbert@gondor.apana.org.au> wrote:
> On Tue, Jul 14, 2015 at 04:45:48PM -0700, Tom Herbert wrote:
>> The obj_orderfn function may be specified in the parameters for a
>> rhashtable. When inserting an element this function is used to order
>> objects in a bucket list (greatest to least ordering value).This
>> allows entries to have wild card fields, where entries with
>> more specific information match are placed first in the bucket.
>> When a lookup is done, the first match found will contain
>> the most specific match.
>>
>> In order to maintain ordering guarantees during rehash, the
>> rhashtable_lookup_ordered_cmpfn was added. This function will check
>> future tables for matches that would have a greater insertion order
>> than a match found in an older table.
>>
>> Signed-off-by: Tom Herbert <tom@herbertland.com>
>
> There is another problem with exposing rhashtable directly to these
> duplicate entries.  It breaks the logic on when to resize.  In the
> worst case on a server with a single port you can end up with a
> large hash table where everything is stored in a single chain.
>
> Granted you can work around this by teaching rhashtable to count
> identical entries as a single entry.  But I really think it's much
> easier to just have this logic sit on top of rhashtable instead of
> inside it.
>
> The memory cost is merely 8 bytes per local port, is it really too
> much?
>
Okay, it looks like there is already an additional hlist_node in
skc_common that can be used for a secondary hash. It's conceivable
this can be generalized and used in the TCP listeners also in
combination with rhashtable.

Tom

> 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

Re: [PATCH v2 net-next 1/3] rhashtable: Allow lookup function to have compare function agument

[Thomas Graf]

On 07/14/15 at 04:45pm, Tom Herbert wrote:
> Added rhashtable_lookup_fast_cmpfn which does a lookup in an rhash table
> with the compare function being taken from an argument. This allows
> different compare functions to be used on the same table.
> 
> Signed-off-by: Tom Herbert <tom@herbertland.com>

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

Re: [PATCH v2 net-next 2/3] rhashtable: Add a function for in order insertion and lookup in buckets

[Thomas Graf]

On 07/15/15 at 12:46pm, Tom Herbert wrote:
> On Tue, Jul 14, 2015 at 10:54 PM, Herbert Xu
> > The memory cost is merely 8 bytes per local port, is it really too
> > much?
> >
> Okay, it looks like there is already an additional hlist_node in
> skc_common that can be used for a secondary hash. It's conceivable
> this can be generalized and used in the TCP listeners also in
> combination with rhashtable.

Are you dropping this series entirely then?