From: David Gibson <david@gibson.dropbear.id.au>
To: passt-dev@passt.top, Stefano Brivio <sbrivio@redhat.com>
Cc: David Gibson <david@gibson.dropbear.id.au>
Subject: [PATCH 3/3] tcp: Don't account for hash table size in tcp_hash()
Date: Mon, 4 Dec 2023 14:16:11 +1100 [thread overview]
Message-ID: <20231204031611.3566791-4-david@gibson.dropbear.id.au> (raw)
In-Reply-To: <20231204031611.3566791-1-david@gibson.dropbear.id.au>
Currently tcp_hash() returns the hash bucket for a value, that is the hash
modulo the size of the hash table. Usually it's a bit more flexible to
have hash functions return a "raw" hash value and perform the modulus in
the callers. That allows the same hash function to be used for multiple
tables of different sizes, or to re-use the hash for other purposes.
We don't do anything like that with tcp_hash() at present, but we have some
plans to do so. Prepare for that by making tcp_hash() and tcp_conn_hash()
return raw hash values.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
tcp.c | 23 ++++++++++-------------
1 file changed, 10 insertions(+), 13 deletions(-)
diff --git a/tcp.c b/tcp.c
index 7e438b7..6b12feb 100644
--- a/tcp.c
+++ b/tcp.c
@@ -1159,18 +1159,15 @@ static int tcp_hash_match(const struct tcp_tap_conn *conn,
* @eport: Guest side endpoint port
* @fport: Guest side forwarding port
*
- * Return: hash value, already modulo size of the hash table
+ * Return: hash value, needs to be adjusted for table size
*/
-static unsigned int tcp_hash(const struct ctx *c, const union inany_addr *faddr,
- in_port_t eport, in_port_t fport)
+static uint64_t tcp_hash(const struct ctx *c, const union inany_addr *faddr,
+ in_port_t eport, in_port_t fport)
{
struct siphash_state state = SIPHASH_INIT(c->hash_secret);
- uint64_t hash;
inany_siphash_feed(&state, faddr);
- hash = siphash_final(&state, 20, (uint64_t)eport << 16 | fport);
-
- return (unsigned int)(hash % TCP_HASH_TABLE_SIZE);
+ return siphash_final(&state, 20, (uint64_t)eport << 16 | fport);
}
/**
@@ -1178,10 +1175,10 @@ static unsigned int tcp_hash(const struct ctx *c, const union inany_addr *faddr,
* @c: Execution context
* @conn: Connection
*
- * Return: hash value, already modulo size of the hash table
+ * Return: hash value, needs to be adjusted for table size
*/
-static unsigned int tcp_conn_hash(const struct ctx *c,
- const struct tcp_tap_conn *conn)
+static uint64_t tcp_conn_hash(const struct ctx *c,
+ const struct tcp_tap_conn *conn)
{
return tcp_hash(c, &conn->faddr, conn->eport, conn->fport);
}
@@ -1201,7 +1198,7 @@ static inline unsigned tcp_hash_probe(const struct ctx *c,
unsigned b;
/* Linear probing */
- for (b = tcp_conn_hash(c, conn);
+ for (b = tcp_conn_hash(c, conn) % TCP_HASH_TABLE_SIZE;
!flow_sidx_eq(tc_hash[b], FLOW_SIDX_NONE) &&
!flow_sidx_eq(tc_hash[b], sidx);
b = (b + 1) % TCP_HASH_TABLE_SIZE)
@@ -1243,7 +1240,7 @@ static void tcp_hash_remove(const struct ctx *c,
for (s = (b + 1) % TCP_HASH_TABLE_SIZE;
(flow = flow_at_sidx(tc_hash[s]));
s = (s + 1) % TCP_HASH_TABLE_SIZE) {
- unsigned h = tcp_conn_hash(c, &flow->tcp);
+ unsigned h = tcp_conn_hash(c, &flow->tcp) % TCP_HASH_TABLE_SIZE;
if (in_mod_range(h, b, s, TCP_HASH_TABLE_SIZE)) {
/* tc_hash[s] can live in tc_hash[b]'s slot */
@@ -1299,7 +1296,7 @@ static struct tcp_tap_conn *tcp_hash_lookup(const struct ctx *c,
inany_from_af(&aany, af, faddr);
- for (b = tcp_hash(c, &aany, eport, fport);
+ for (b = tcp_hash(c, &aany, eport, fport) % TCP_HASH_TABLE_SIZE;
(flow = flow_at_sidx(tc_hash[b]))
&& !tcp_hash_match(&flow->tcp, &aany, eport, fport);
b = (b + 1) % TCP_HASH_TABLE_SIZE)
--
@@ -1159,18 +1159,15 @@ static int tcp_hash_match(const struct tcp_tap_conn *conn,
* @eport: Guest side endpoint port
* @fport: Guest side forwarding port
*
- * Return: hash value, already modulo size of the hash table
+ * Return: hash value, needs to be adjusted for table size
*/
-static unsigned int tcp_hash(const struct ctx *c, const union inany_addr *faddr,
- in_port_t eport, in_port_t fport)
+static uint64_t tcp_hash(const struct ctx *c, const union inany_addr *faddr,
+ in_port_t eport, in_port_t fport)
{
struct siphash_state state = SIPHASH_INIT(c->hash_secret);
- uint64_t hash;
inany_siphash_feed(&state, faddr);
- hash = siphash_final(&state, 20, (uint64_t)eport << 16 | fport);
-
- return (unsigned int)(hash % TCP_HASH_TABLE_SIZE);
+ return siphash_final(&state, 20, (uint64_t)eport << 16 | fport);
}
/**
@@ -1178,10 +1175,10 @@ static unsigned int tcp_hash(const struct ctx *c, const union inany_addr *faddr,
* @c: Execution context
* @conn: Connection
*
- * Return: hash value, already modulo size of the hash table
+ * Return: hash value, needs to be adjusted for table size
*/
-static unsigned int tcp_conn_hash(const struct ctx *c,
- const struct tcp_tap_conn *conn)
+static uint64_t tcp_conn_hash(const struct ctx *c,
+ const struct tcp_tap_conn *conn)
{
return tcp_hash(c, &conn->faddr, conn->eport, conn->fport);
}
@@ -1201,7 +1198,7 @@ static inline unsigned tcp_hash_probe(const struct ctx *c,
unsigned b;
/* Linear probing */
- for (b = tcp_conn_hash(c, conn);
+ for (b = tcp_conn_hash(c, conn) % TCP_HASH_TABLE_SIZE;
!flow_sidx_eq(tc_hash[b], FLOW_SIDX_NONE) &&
!flow_sidx_eq(tc_hash[b], sidx);
b = (b + 1) % TCP_HASH_TABLE_SIZE)
@@ -1243,7 +1240,7 @@ static void tcp_hash_remove(const struct ctx *c,
for (s = (b + 1) % TCP_HASH_TABLE_SIZE;
(flow = flow_at_sidx(tc_hash[s]));
s = (s + 1) % TCP_HASH_TABLE_SIZE) {
- unsigned h = tcp_conn_hash(c, &flow->tcp);
+ unsigned h = tcp_conn_hash(c, &flow->tcp) % TCP_HASH_TABLE_SIZE;
if (in_mod_range(h, b, s, TCP_HASH_TABLE_SIZE)) {
/* tc_hash[s] can live in tc_hash[b]'s slot */
@@ -1299,7 +1296,7 @@ static struct tcp_tap_conn *tcp_hash_lookup(const struct ctx *c,
inany_from_af(&aany, af, faddr);
- for (b = tcp_hash(c, &aany, eport, fport);
+ for (b = tcp_hash(c, &aany, eport, fport) % TCP_HASH_TABLE_SIZE;
(flow = flow_at_sidx(tc_hash[b]))
&& !tcp_hash_match(&flow->tcp, &aany, eport, fport);
b = (b + 1) % TCP_HASH_TABLE_SIZE)
--
2.43.0
prev parent reply other threads:[~2023-12-04 3:16 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-12-04 3:16 [PATCH 0/3] RFC: TCP hash change changes, in preparation for flow table David Gibson
2023-12-04 3:16 ` [PATCH 1/3] tcp: Switch hash table to linear probing instead of chaining David Gibson
2023-12-06 22:43 ` Stefano Brivio
2023-12-07 4:11 ` David Gibson
2023-12-11 9:00 ` Stefano Brivio
2023-12-04 3:16 ` [PATCH 2/3] tcp: Implement hash table with indices rather than pointers David Gibson
2023-12-06 19:37 ` Stefano Brivio
2023-12-07 1:04 ` David Gibson
2023-12-07 5:10 ` David Gibson
2023-12-07 6:20 ` Stefano Brivio
2023-12-04 3:16 ` David Gibson [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20231204031611.3566791-4-david@gibson.dropbear.id.au \
--to=david@gibson.dropbear.id.au \
--cc=passt-dev@passt.top \
--cc=sbrivio@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://passt.top/passt
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for IMAP folder(s).