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

[PATCH 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.


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

 include/linux/rhashtable.h | 122 ++++++++++++++++++++++++++++++++++++++++++---
 lib/rhashtable.c           |  20 ++++----
 2 files changed, 125 insertions(+), 17 deletions(-)

-- 
1.8.1

[PATCH net-next 1/3] rhashtable: Add a function for in order insertion 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.

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

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 843ceca..8e27159 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;
 };
 
 /**
@@ -560,6 +563,37 @@ restart:
 	return NULL;
 }
 
+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,
@@ -571,6 +605,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;
@@ -633,11 +668,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 a60a6d3..0de37e0 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

Re: [PATCH net-next 1/3] rhashtable: Add a function for in order insertion in buckets

[Herbert Xu]

Tom Herbert <tom@herbertland.com> 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.
> 
> Signed-off-by: Tom Herbert <tom@herbertland.com>

I think this is fundamentally broken with respect to rehashing.
During a rehash you're going to have some elements in the old table
and some in the new table.  At which point all your ordering
guarantees go out of the window.

I actually need something quite similar for IPsec.  What I was
planning on doing is have the actual objects hang off an ordered
list object.  The ordered list would then be the thing that you
insert into rhashtable.  This means that during rehashing they
get moved atomically.

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 net-next 1/3] rhashtable: Add a function for in order insertion in buckets

[Tom Herbert]

On Tue, Jul 14, 2015 at 2:57 AM, Herbert Xu <herbert@gondor.apana.org.au> wrote:
> Tom Herbert <tom@herbertland.com> 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.
>>
>> Signed-off-by: Tom Herbert <tom@herbertland.com>
>
Hi Herbert,

> I think this is fundamentally broken with respect to rehashing.
> During a rehash you're going to have some elements in the old table
> and some in the new table.  At which point all your ordering
> guarantees go out of the window.
>
Yes, good observation.

> I actually need something quite similar for IPsec.  What I was
> planning on doing is have the actual objects hang off an ordered
> list object.  The ordered list would then be the thing that you
> insert into rhashtable.  This means that during rehashing they
> get moved atomically.
>
Hmm, I do like the simplicity of a flat linear search.

Scored lookups can provides the same functionality, but requires that
we scan all the elements so I see some overhead compared to doing
ordered insertion. One way to resolve the rehash problem is search any
future table after we find a hit in the first table to see if there
are any entries that would precede the element already found. So in
the common non-rehash case lookup happens as it does now except that
we would always check for future_tbl.

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 net-next 1/3] rhashtable: Add a function for in order insertion in buckets

[Herbert Xu]

On Tue, Jul 14, 2015 at 09:42:49AM -0700, Tom Herbert wrote:
>
> Scored lookups can provides the same functionality, but requires that
> we scan all the elements so I see some overhead compared to doing
> ordered insertion. One way to resolve the rehash problem is search any
> future table after we find a hit in the first table to see if there
> are any entries that would precede the element already found. So in
> the common non-rehash case lookup happens as it does now except that
> we would always check for future_tbl.

There is another problem with this approach and that is it breaks
the logic for determining hash collission attack.  Since you're
intentionally inserting multiple elements with the same hash, the
chain length would be inflated.

The other reason I wanted to have this logic outside of rhashtable
is because for IPsec, the wildcards may in fact change after a
"rehash".  For example we may move from a /32 granularity to a
/31 granlarity at the requst of the admin.  In that case you can't
just mix the chain from the old table with the new.

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 net-next 1/3] rhashtable: Add a function for in order insertion in buckets

[Tom Herbert]

On Tue, Jul 14, 2015 at 4:58 PM, Herbert Xu <herbert@gondor.apana.org.au> wrote:
> On Tue, Jul 14, 2015 at 09:42:49AM -0700, Tom Herbert wrote:
>>
>> Scored lookups can provides the same functionality, but requires that
>> we scan all the elements so I see some overhead compared to doing
>> ordered insertion. One way to resolve the rehash problem is search any
>> future table after we find a hit in the first table to see if there
>> are any entries that would precede the element already found. So in
>> the common non-rehash case lookup happens as it does now except that
>> we would always check for future_tbl.
>
> There is another problem with this approach and that is it breaks
> the logic for determining hash collission attack.  Since you're
> intentionally inserting multiple elements with the same hash, the
> chain length would be inflated.
>
Conceptually, I agree with you, but I would point out that we've had
this model of intentional collisions for a while in socket lookup. I
would assume that it's a goal to use rhashtable for socket tables, so
we'll need some solution that works with that!

> The other reason I wanted to have this logic outside of rhashtable
> is because for IPsec, the wildcards may in fact change after a
> "rehash".  For example we may move from a /32 granularity to a
> /31 granlarity at the requst of the admin.  In that case you can't
> just mix the chain from the old table with the new.
>
Where ordering elements in the table can't be sustained, scoring would
be used (e.g. scoring function can be changed on the fly, but ordering
rules can't be).

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 net-next 1/3] rhashtable: Add a function for in order insertion in buckets

[Herbert Xu]

On Tue, Jul 14, 2015 at 05:59:53PM -0700, Tom Herbert wrote:
>
> Conceptually, I agree with you, but I would point out that we've had
> this model of intentional collisions for a while in socket lookup. I
> would assume that it's a goal to use rhashtable for socket tables, so
> we'll need some solution that works with that!

Why you couldn't have them hang off a node as I described earlier?

> > The other reason I wanted to have this logic outside of rhashtable
> > is because for IPsec, the wildcards may in fact change after a
> > "rehash".  For example we may move from a /32 granularity to a
> > /31 granlarity at the requst of the admin.  In that case you can't
> > just mix the chain from the old table with the new.
> >
> Where ordering elements in the table can't be sustained, scoring would
> be used (e.g. scoring function can be changed on the fly, but ordering
> rules can't be).

I'm not sure whether we're talking about the same thing here.

Let me describe the IPsec case more clearly.  We have wildcards
and non-wildcards.  Only the non-wildcards would be hashed.  The
wild cards are checked outside of the hash table.  The tricky bit
is that the admin can flip a switch and we may either have to move
previously wildcard entries that are no longer wildcards into the
hash table, or move non-wildcard entries out of the table and into
the wildcard list.

And of course we want to do this without imposing locking on the
reader :)

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 net-next 2/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 | 17 +++++++++++++----
 1 file changed, 13 insertions(+), 4 deletions(-)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 8e27159..05171c3 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -526,9 +526,10 @@ static inline int rhashtable_compare(struct rhashtable_compare_arg *arg,
  *
  * 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,
@@ -544,8 +545,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();
@@ -563,6 +564,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);
+}
+
 struct rht_insert_pos {
 	struct rhash_head __rcu *head;
 	struct rhash_head __rcu **pos;
-- 
1.8.1

Re: [PATCH net-next 2/3] rhashtable: allow lookup function to have compare function agument

[Thomas Graf]

On 07/13/15 at 05:39pm, 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>

Does this preserve the inlining guarantee? I remember Herbert had
to write this carefully in order to avoid indirect calls.

Re: [PATCH net-next 2/3] rhashtable: allow lookup function to have compare function agument

[Tom Herbert]

On Tue, Jul 14, 2015 at 2:44 AM, Thomas Graf <tgraf@suug.ch> wrote:
> On 07/13/15 at 05:39pm, 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>
>
> Does this preserve the inlining guarantee? I remember Herbert had
> to write this carefully in order to avoid indirect calls.

It looks like the compare functions are still being properly inlined.
This is gcc 4.4.7.

Thanks,
Tom

[PATCH 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 highest 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 | 64 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 64 insertions(+)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 05171c3..317bc793 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,67 @@ 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 > best_score) {
+			result = he;
+			best_score = score;
+			matches = 1;
+			khash = flow_hash;
+		} else if (score && 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 - search hash table, inlined version
  * @ht:		hash table
-- 
1.8.1