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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <1436917549-3666965-4-git-send-email-tom@herbertland.com>
Date:	Tue, 14 Jul 2015 16:45:49 -0700
From:	Tom Herbert <tom@...bertland.com>
To:	<davem@...emloft.net>, <netdev@...r.kernel.org>, <tgraf@...g.ch>,
	<herbert@...dor.apana.org.au>
CC:	<kernel-team@...com>
Subject: [PATCH v2 net-next 3/3] rhashtable: Add scored lookups

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@...bertland.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

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html