[PATCH v5 12/19] tcp, flow: Replace TCP specific hash function with general flow hash

[David Gibson <david@gibson.dropbear.id.au>]

Currently we match TCP packets received on the tap connection to a TCP
connection via a hash table based on the forwarding address and both
ports.  We hope in future to allow for multiple guest side addresses, or
for multiple interfaces which means we may need to distinguish based on
the endpoint address and pif as well.  We also want a unified hash table
to cover multiple protocols, not just TCP.

Replace the TCP specific hash function with one suitable for general flows,
or rather for one side of a general flow.  This includes all the
information from struct flowside, plus the L4 protocol number.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
 flow.c       | 35 +++++++++++++++++++++++++++---
 flow.h       | 19 ++++++++++++++++
 flow_table.h |  2 ++
 tcp.c        | 61 ++++++++++------------------------------------------
 4 files changed, 64 insertions(+), 53 deletions(-)

diff --git a/flow.c b/flow.c
index aff077b..fdd22b7 100644
--- a/flow.c
+++ b/flow.c
@@ -116,9 +116,9 @@ static struct timespec flow_timer_run;
  * @faddr:	Forwarding address (pointer to in_addr or in6_addr)
  * @fport:	Forwarding port
  */
-static void flowside_from_af(struct flowside *fside, sa_family_t af,
-			     const void *eaddr, in_port_t eport,
-			     const void *faddr, in_port_t fport)
+void flowside_from_af(struct flowside *fside, sa_family_t af,
+		      const void *eaddr, in_port_t eport,
+		      const void *faddr, in_port_t fport)
 {
 	if (faddr)
 		inany_from_af(&fside->faddr, af, faddr);
@@ -397,6 +397,35 @@ void flow_alloc_cancel(union flow *flow)
 	flow_new_entry = NULL;
 }
 
+/**
+ * flow_hash() - Calculate hash value for one side of a flow
+ * @c:		Execution context
+ * @proto:	Protocol of this flow (IP L4 protocol number)
+ * @pif:	pif of the side to hash
+ * @fside:	Flowside (must not have unspecified parts)
+ *
+ * Return: hash value
+ */
+uint64_t flow_hash(const struct ctx *c, uint8_t proto, uint8_t pif,
+		   const struct flowside *fside)
+{
+	struct siphash_state state = SIPHASH_INIT(c->hash_secret);
+
+	/* For the hash table to work, we need complete information in the
+	 * flowside.
+	 */
+	ASSERT(pif != PIF_NONE &&
+	       !inany_is_unspecified(&fside->faddr) && fside->fport != 0 &&
+	       !inany_is_unspecified(&fside->eaddr) && fside->eport != 0);
+
+	inany_siphash_feed(&state, &fside->faddr);
+	inany_siphash_feed(&state, &fside->eaddr);
+
+	return siphash_final(&state, 38, (uint64_t)proto << 40 |
+			     (uint64_t)pif << 32 |
+			     fside->fport << 16 | fside->eport);
+}
+
 /**
  * flow_defer_handler() - Handler for per-flow deferred and timed tasks
  * @c:		Execution context
diff --git a/flow.h b/flow.h
index 437579b..6d68e09 100644
--- a/flow.h
+++ b/flow.h
@@ -147,6 +147,25 @@ struct flowside {
 	in_port_t		eport;
 };
 
+/**
+ * flowside_eq() - Check if two flowsides are equal
+ * @left, @right:	Flowsides to compare
+ *
+ * Return: true if equal, false otherwise
+ */
+static inline bool flowside_eq(const struct flowside *left,
+			       const struct flowside *right)
+{
+	return inany_equals(&left->eaddr, &right->eaddr) &&
+	       left->eport == right->eport &&
+	       inany_equals(&left->faddr, &right->faddr) &&
+	       left->fport == right->fport;
+}
+
+void flowside_from_af(struct flowside *fside, sa_family_t af,
+		      const void *eaddr, in_port_t eport,
+		      const void *faddr, in_port_t fport);
+
 /**
  * struct flow_common - Common fields for packet flows
  * @side[]:	Information for each side of the flow
diff --git a/flow_table.h b/flow_table.h
index 91ade0a..0083c87 100644
--- a/flow_table.h
+++ b/flow_table.h
@@ -126,5 +126,7 @@ void flow_activate(struct flow_common *f);
 #define FLOW_ACTIVATE(flow_)			\
 	(flow_activate(&(flow_)->f))
 
+uint64_t flow_hash(const struct ctx *c, uint8_t proto, uint8_t pif,
+		   const struct flowside *fside);
 
 #endif /* FLOW_TABLE_H */
diff --git a/tcp.c b/tcp.c
index 9895c19..983a537 100644
--- a/tcp.c
+++ b/tcp.c
@@ -523,7 +523,7 @@ static struct iovec	tcp_iov			[UIO_MAXIOV];
 
 #define CONN(idx)		(&(FLOW(idx)->tcp))
 
-/* Table for lookup from remote address, local port, remote port */
+/* Table for lookup from flowside information */
 static flow_sidx_t tc_hash[TCP_HASH_TABLE_SIZE];
 
 static_assert(ARRAY_SIZE(tc_hash) >= FLOW_MAX,
@@ -1073,46 +1073,6 @@ static int tcp_opt_get(const char *opts, size_t len, uint8_t type_find,
 	return -1;
 }
 
-/**
- * tcp_hash_match() - Check if a connection entry matches address and ports
- * @conn:	Connection entry to match against
- * @faddr:	Guest side forwarding address
- * @eport:	Guest side endpoint port
- * @fport:	Guest side forwarding port
- *
- * Return: 1 on match, 0 otherwise
- */
-static int tcp_hash_match(const struct tcp_tap_conn *conn,
-			  const union inany_addr *faddr,
-			  in_port_t eport, in_port_t fport)
-{
-	const struct flowside *tapside = TAPFLOW(conn);
-
-	if (inany_equals(&tapside->faddr, faddr) &&
-	    tapside->eport == eport && tapside->fport == fport)
-		return 1;
-
-	return 0;
-}
-
-/**
- * tcp_hash() - Calculate hash value for connection given address and ports
- * @c:		Execution context
- * @faddr:	Guest side forwarding address
- * @eport:	Guest side endpoint port
- * @fport:	Guest side forwarding port
- *
- * Return: hash value, needs to be adjusted for table size
- */
-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);
-
-	inany_siphash_feed(&state, faddr);
-	return siphash_final(&state, 20, (uint64_t)eport << 16 | fport);
-}
-
 /**
  * tcp_conn_hash() - Calculate hash bucket of an existing connection
  * @c:		Execution context
@@ -1125,8 +1085,7 @@ static uint64_t tcp_conn_hash(const struct ctx *c,
 {
 	const struct flowside *tapside = TAPFLOW(conn);
 
-	return tcp_hash(c, &tapside->faddr, tapside->eport,
-			tapside->fport);
+	return flow_hash(c, IPPROTO_TCP, conn->f.pif[TAPSIDE(conn)], tapside);
 }
 
 /**
@@ -1201,25 +1160,26 @@ static void tcp_hash_remove(const struct ctx *c,
  * tcp_hash_lookup() - Look up connection given remote address and ports
  * @c:		Execution context
  * @af:		Address family, AF_INET or AF_INET6
+ * @eaddr:	Guest side endpoint address (guest local address)
  * @faddr:	Guest side forwarding address (guest remote address)
  * @eport:	Guest side endpoint port (guest local port)
  * @fport:	Guest side forwarding port (guest remote port)
  *
  * Return: connection pointer, if found, -ENOENT otherwise
  */
-static struct tcp_tap_conn *tcp_hash_lookup(const struct ctx *c,
-					    sa_family_t af, const void *faddr,
+static struct tcp_tap_conn *tcp_hash_lookup(const struct ctx *c, sa_family_t af,
+					    const void *eaddr, const void *faddr,
 					    in_port_t eport, in_port_t fport)
 {
-	union inany_addr aany;
+	struct flowside fside;
 	union flow *flow;
 	unsigned b;
 
-	inany_from_af(&aany, af, faddr);
+	flowside_from_af(&fside, af, eaddr, eport, faddr, fport);
 
-	b = tcp_hash(c, &aany, eport, fport) % TCP_HASH_TABLE_SIZE;
+	b = flow_hash(c, IPPROTO_TCP, PIF_TAP, &fside) % TCP_HASH_TABLE_SIZE;
 	while ((flow = flow_at_sidx(tc_hash[b])) &&
-	       !tcp_hash_match(&flow->tcp, &aany, eport, fport))
+	       !flowside_eq(&flow->f.side[TAPSIDE(flow)], &fside))
 		b = mod_sub(b, 1, TCP_HASH_TABLE_SIZE);
 
 	return &flow->tcp;
@@ -2523,7 +2483,8 @@ int tcp_tap_handler(struct ctx *c, uint8_t pif, sa_family_t af,
 	optlen = MIN(optlen, ((1UL << 4) /* from doff width */ - 6) * 4UL);
 	opts = packet_get(p, idx, sizeof(*th), optlen, NULL);
 
-	conn = tcp_hash_lookup(c, af, daddr, ntohs(th->source), ntohs(th->dest));
+	conn = tcp_hash_lookup(c, af, saddr, daddr,
+			       ntohs(th->source), ntohs(th->dest));
 
 	/* New connection from tap */
 	if (!conn) {
-- 
@@ -523,7 +523,7 @@ static struct iovec	tcp_iov			[UIO_MAXIOV];
 
 #define CONN(idx)		(&(FLOW(idx)->tcp))
 
-/* Table for lookup from remote address, local port, remote port */
+/* Table for lookup from flowside information */
 static flow_sidx_t tc_hash[TCP_HASH_TABLE_SIZE];
 
 static_assert(ARRAY_SIZE(tc_hash) >= FLOW_MAX,
@@ -1073,46 +1073,6 @@ static int tcp_opt_get(const char *opts, size_t len, uint8_t type_find,
 	return -1;
 }
 
-/**
- * tcp_hash_match() - Check if a connection entry matches address and ports
- * @conn:	Connection entry to match against
- * @faddr:	Guest side forwarding address
- * @eport:	Guest side endpoint port
- * @fport:	Guest side forwarding port
- *
- * Return: 1 on match, 0 otherwise
- */
-static int tcp_hash_match(const struct tcp_tap_conn *conn,
-			  const union inany_addr *faddr,
-			  in_port_t eport, in_port_t fport)
-{
-	const struct flowside *tapside = TAPFLOW(conn);
-
-	if (inany_equals(&tapside->faddr, faddr) &&
-	    tapside->eport == eport && tapside->fport == fport)
-		return 1;
-
-	return 0;
-}
-
-/**
- * tcp_hash() - Calculate hash value for connection given address and ports
- * @c:		Execution context
- * @faddr:	Guest side forwarding address
- * @eport:	Guest side endpoint port
- * @fport:	Guest side forwarding port
- *
- * Return: hash value, needs to be adjusted for table size
- */
-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);
-
-	inany_siphash_feed(&state, faddr);
-	return siphash_final(&state, 20, (uint64_t)eport << 16 | fport);
-}
-
 /**
  * tcp_conn_hash() - Calculate hash bucket of an existing connection
  * @c:		Execution context
@@ -1125,8 +1085,7 @@ static uint64_t tcp_conn_hash(const struct ctx *c,
 {
 	const struct flowside *tapside = TAPFLOW(conn);
 
-	return tcp_hash(c, &tapside->faddr, tapside->eport,
-			tapside->fport);
+	return flow_hash(c, IPPROTO_TCP, conn->f.pif[TAPSIDE(conn)], tapside);
 }
 
 /**
@@ -1201,25 +1160,26 @@ static void tcp_hash_remove(const struct ctx *c,
  * tcp_hash_lookup() - Look up connection given remote address and ports
  * @c:		Execution context
  * @af:		Address family, AF_INET or AF_INET6
+ * @eaddr:	Guest side endpoint address (guest local address)
  * @faddr:	Guest side forwarding address (guest remote address)
  * @eport:	Guest side endpoint port (guest local port)
  * @fport:	Guest side forwarding port (guest remote port)
  *
  * Return: connection pointer, if found, -ENOENT otherwise
  */
-static struct tcp_tap_conn *tcp_hash_lookup(const struct ctx *c,
-					    sa_family_t af, const void *faddr,
+static struct tcp_tap_conn *tcp_hash_lookup(const struct ctx *c, sa_family_t af,
+					    const void *eaddr, const void *faddr,
 					    in_port_t eport, in_port_t fport)
 {
-	union inany_addr aany;
+	struct flowside fside;
 	union flow *flow;
 	unsigned b;
 
-	inany_from_af(&aany, af, faddr);
+	flowside_from_af(&fside, af, eaddr, eport, faddr, fport);
 
-	b = tcp_hash(c, &aany, eport, fport) % TCP_HASH_TABLE_SIZE;
+	b = flow_hash(c, IPPROTO_TCP, PIF_TAP, &fside) % TCP_HASH_TABLE_SIZE;
 	while ((flow = flow_at_sidx(tc_hash[b])) &&
-	       !tcp_hash_match(&flow->tcp, &aany, eport, fport))
+	       !flowside_eq(&flow->f.side[TAPSIDE(flow)], &fside))
 		b = mod_sub(b, 1, TCP_HASH_TABLE_SIZE);
 
 	return &flow->tcp;
@@ -2523,7 +2483,8 @@ int tcp_tap_handler(struct ctx *c, uint8_t pif, sa_family_t af,
 	optlen = MIN(optlen, ((1UL << 4) /* from doff width */ - 6) * 4UL);
 	opts = packet_get(p, idx, sizeof(*th), optlen, NULL);
 
-	conn = tcp_hash_lookup(c, af, daddr, ntohs(th->source), ntohs(th->dest));
+	conn = tcp_hash_lookup(c, af, saddr, daddr,
+			       ntohs(th->source), ntohs(th->dest));
 
 	/* New connection from tap */
 	if (!conn) {
-- 
2.45.0