* [PATCH v2 net-next 1/3] rhashtable: Allow lookup function to have compare function agument
2015-07-14 23:45 [PATCH v2 net-next 0/3] rhashtable: Wildcard and scored lookups Tom Herbert
@ 2015-07-14 23:45 ` Tom Herbert
2015-07-17 12:08 ` Thomas Graf
2015-07-14 23:45 ` [PATCH v2 net-next 2/3] rhashtable: Add a function for in order insertion and lookup in buckets Tom Herbert
2015-07-14 23:45 ` [PATCH v2 net-next 3/3] rhashtable: Add scored lookups Tom Herbert
2 siblings, 1 reply; 10+ messages in thread
From: Tom Herbert @ 2015-07-14 23:45 UTC (permalink / raw)
To: davem, netdev, tgraf, herbert; +Cc: kernel-team
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
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v2 net-next 2/3] rhashtable: Add a function for in order insertion and lookup in buckets
2015-07-14 23:45 [PATCH v2 net-next 0/3] rhashtable: Wildcard and scored lookups Tom Herbert
2015-07-14 23:45 ` [PATCH v2 net-next 1/3] rhashtable: Allow lookup function to have compare function agument Tom Herbert
@ 2015-07-14 23:45 ` Tom Herbert
2015-07-15 5:54 ` Herbert Xu
2015-07-14 23:45 ` [PATCH v2 net-next 3/3] rhashtable: Add scored lookups Tom Herbert
2 siblings, 1 reply; 10+ messages in thread
From: Tom Herbert @ 2015-07-14 23:45 UTC (permalink / raw)
To: davem, netdev, tgraf, herbert; +Cc: kernel-team
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
^ permalink raw reply related [flat|nested] 10+ messages in thread* [PATCH v2 net-next 3/3] rhashtable: Add scored lookups
2015-07-14 23:45 [PATCH v2 net-next 0/3] rhashtable: Wildcard and scored lookups Tom Herbert
2015-07-14 23:45 ` [PATCH v2 net-next 1/3] rhashtable: Allow lookup function to have compare function agument Tom Herbert
2015-07-14 23:45 ` [PATCH v2 net-next 2/3] rhashtable: Add a function for in order insertion and lookup in buckets Tom Herbert
@ 2015-07-14 23:45 ` Tom Herbert
2015-07-15 0:18 ` Herbert Xu
2 siblings, 1 reply; 10+ messages in thread
From: Tom Herbert @ 2015-07-14 23:45 UTC (permalink / raw)
To: davem, netdev, tgraf, herbert; +Cc: kernel-team
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
^ permalink raw reply related [flat|nested] 10+ messages in thread