[PATCH v3 09/15] tcp: Re-use flow hash for initial sequence number generation

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

We generate TCP initial sequence numbers, when we need them, from a hash
of the source and destination addresses and ports, plus a timestamp.
Moments later, we generate another hash of the same information, plus a few
extras to slot the connection into the flow table.

With some tweaks to the flow_hash_insert() interface and changing the
order we can re-use that hash table hash for the initial sequence
number, rather than calculating another one.  It won't generate
identical results, but that doesn't matter as long as the sequence
numbers are well scattered.

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
 flow.c | 30 ++++++++++++++++++++++++------
 flow.h |  2 +-
 tcp.c  | 35 +++++++++++++----------------------
 3 files changed, 38 insertions(+), 29 deletions(-)

diff --git a/flow.c b/flow.c
index 3d016c3..e4ea931 100644
--- a/flow.c
+++ b/flow.c
@@ -281,16 +281,16 @@ static uint64_t flow_sidx_hash(const struct ctx *c, flow_sidx_t sidx)
 }
 
 /**
- * flow_hash_probe() - Find hash bucket for a flow
- * @c:		Execution context
+ * flow_hash_probe_() - Find hash bucket for a flow, given hash
+ * @hash:	Raw hash value for flow & side
  * @sidx:	Flow and side to find bucket for
  *
  * Return: If @sidx is in the hash table, its current bucket, otherwise a
  *         suitable free bucket for it.
  */
-static inline unsigned flow_hash_probe(const struct ctx *c, flow_sidx_t sidx)
+static inline unsigned flow_hash_probe_(uint64_t hash, flow_sidx_t sidx)
 {
-	unsigned b = flow_sidx_hash(c, sidx) % FLOW_HASH_SIZE;
+	unsigned b = hash % FLOW_HASH_SIZE;
 
 	/* Linear probing */
 	while (!flow_sidx_eq(flow_hashtab[b], FLOW_SIDX_NONE) &&
@@ -300,17 +300,35 @@ static inline unsigned flow_hash_probe(const struct ctx *c, flow_sidx_t sidx)
 	return b;
 }
 
+/**
+ * flow_hash_probe() - Find hash bucket for a flow
+ * @c:		Execution context
+ * @sidx:	Flow and side to find bucket for
+ *
+ * Return: If @sidx is in the hash table, its current bucket, otherwise a
+ *         suitable free bucket for it.
+ */
+static inline unsigned flow_hash_probe(const struct ctx *c, flow_sidx_t sidx)
+{
+	return flow_hash_probe_(flow_sidx_hash(c, sidx), sidx);
+}
+
 /**
  * flow_hash_insert() - Insert side of a flow into into hash table
  * @c:		Execution context
  * @sidx:	Flow & side index
+ *
+ * Return: raw (un-modded) hash value of side of flow
  */
-void flow_hash_insert(const struct ctx *c, flow_sidx_t sidx)
+uint64_t flow_hash_insert(const struct ctx *c, flow_sidx_t sidx)
 {
-	unsigned b = flow_hash_probe(c, sidx);
+	uint64_t hash = flow_sidx_hash(c, sidx);
+	unsigned b = flow_hash_probe_(hash, sidx);
 
 	flow_hashtab[b] = sidx;
 	flow_dbg(flow_at_sidx(sidx), "hash table insert: bucket: %u", b);
+
+	return hash;
 }
 
 /**
diff --git a/flow.h b/flow.h
index adb5d44..e1aeeed 100644
--- a/flow.h
+++ b/flow.h
@@ -158,7 +158,7 @@ static inline bool flow_sidx_eq(flow_sidx_t a, flow_sidx_t b)
 	return (a.flow == b.flow) && (a.side == b.side);
 }
 
-void flow_hash_insert(const struct ctx *c, flow_sidx_t sidx);
+uint64_t flow_hash_insert(const struct ctx *c, flow_sidx_t sidx);
 void flow_hash_remove(const struct ctx *c, flow_sidx_t sidx);
 flow_sidx_t flow_hash_lookup(const struct ctx *c, uint8_t proto, uint8_t pif,
 			     int af, const void *eaddr, const void *faddr,
diff --git a/tcp.c b/tcp.c
index b6d046f..008eb0d 100644
--- a/tcp.c
+++ b/tcp.c
@@ -1578,28 +1578,16 @@ static void tcp_tap_window_update(struct tcp_tap_conn *conn, unsigned wnd)
 }
 
 /**
- * tcp_seq_init() - Calculate initial sequence number according to RFC 6528
- * @c:		Execution context
- * @conn:	TCP connection, with faddr, fport, eaddr, eport populated
+ * tcp_init_seq() - Calculate initial sequence number according to RFC 6528
+ * @hash:	Hash of connection details
  * @now:	Current timestamp
  */
-static void tcp_seq_init(const struct ctx *c, struct tcp_tap_conn *conn,
-			 const struct timespec *now)
+static uint32_t tcp_init_seq(uint64_t hash, const struct timespec *now)
 {
-	struct siphash_state state = SIPHASH_INIT(c->hash_secret);
-	uint64_t hash;
-	uint32_t ns;
-
-	inany_siphash_feed(&state, &TAPFSIDE(conn)->faddr);
-	inany_siphash_feed(&state, &TAPFSIDE(conn)->eaddr);
-	hash = siphash_final(&state, 36,
-			     (uint64_t)TAPFSIDE(conn)->fport << 16 |
-			     TAPFSIDE(conn)->eport);
-
 	/* 32ns ticks, overflows 32 bits every 137s */
-	ns = (now->tv_sec * 1000000000 + now->tv_nsec) >> 5;
+	uint32_t ns = (now->tv_sec * 1000000000 + now->tv_nsec) >> 5;
 
-	conn->seq_to_tap = ((uint32_t)(hash >> 32) ^ (uint32_t)hash) + ns;
+	return ((uint32_t)(hash >> 32) ^ (uint32_t)hash) + ns;
 }
 
 /**
@@ -1758,6 +1746,7 @@ static void tcp_conn_from_tap(struct ctx *c,
 	const struct sockaddr *sa;
 	struct tcp_tap_conn *conn;
 	union flow *flow;
+	uint64_t hash;
 	socklen_t sl;
 	int s, mss;
 
@@ -1824,10 +1813,10 @@ static void tcp_conn_from_tap(struct ctx *c,
 	conn->seq_from_tap = conn->seq_init_from_tap + 1;
 	conn->seq_ack_to_tap = conn->seq_from_tap;
 
-	tcp_seq_init(c, conn, now);
-	conn->seq_ack_from_tap = conn->seq_to_tap;
+	hash = flow_hash_insert(c, FLOW_SIDX(conn, TAPSIDE));
 
-	flow_hash_insert(c, FLOW_SIDX(conn, TAPSIDE));
+	conn->seq_to_tap = tcp_init_seq(hash, now);
+	conn->seq_ack_from_tap = conn->seq_to_tap;
 
 	if (!bind(s, sa, sl)) {
 		tcp_rst(c, conn);	/* Nobody is listening then */
@@ -2518,6 +2507,8 @@ static void tcp_tap_conn_from_sock(struct ctx *c,
 				   struct tcp_tap_conn *conn, int s,
 				   const struct timespec *now)
 {
+	uint64_t hash;
+
 	ASSERT(flowside_complete(SOCKFSIDE(conn)));
 
 	conn->f.type = FLOW_TCP;
@@ -2544,8 +2535,8 @@ static void tcp_tap_conn_from_sock(struct ctx *c,
 	FLOW_FWD_DBG(conn, TAPSIDE);
 	ASSERT(flow_complete(&conn->f));
 
-	tcp_seq_init(c, conn, now);
-	flow_hash_insert(c, FLOW_SIDX(conn, TAPSIDE));
+	hash = flow_hash_insert(c, FLOW_SIDX(conn, TAPSIDE));
+	conn->seq_to_tap = tcp_init_seq(hash, now);
 
 	conn->seq_ack_from_tap = conn->seq_to_tap;
 
-- 
@@ -1578,28 +1578,16 @@ static void tcp_tap_window_update(struct tcp_tap_conn *conn, unsigned wnd)
 }
 
 /**
- * tcp_seq_init() - Calculate initial sequence number according to RFC 6528
- * @c:		Execution context
- * @conn:	TCP connection, with faddr, fport, eaddr, eport populated
+ * tcp_init_seq() - Calculate initial sequence number according to RFC 6528
+ * @hash:	Hash of connection details
  * @now:	Current timestamp
  */
-static void tcp_seq_init(const struct ctx *c, struct tcp_tap_conn *conn,
-			 const struct timespec *now)
+static uint32_t tcp_init_seq(uint64_t hash, const struct timespec *now)
 {
-	struct siphash_state state = SIPHASH_INIT(c->hash_secret);
-	uint64_t hash;
-	uint32_t ns;
-
-	inany_siphash_feed(&state, &TAPFSIDE(conn)->faddr);
-	inany_siphash_feed(&state, &TAPFSIDE(conn)->eaddr);
-	hash = siphash_final(&state, 36,
-			     (uint64_t)TAPFSIDE(conn)->fport << 16 |
-			     TAPFSIDE(conn)->eport);
-
 	/* 32ns ticks, overflows 32 bits every 137s */
-	ns = (now->tv_sec * 1000000000 + now->tv_nsec) >> 5;
+	uint32_t ns = (now->tv_sec * 1000000000 + now->tv_nsec) >> 5;
 
-	conn->seq_to_tap = ((uint32_t)(hash >> 32) ^ (uint32_t)hash) + ns;
+	return ((uint32_t)(hash >> 32) ^ (uint32_t)hash) + ns;
 }
 
 /**
@@ -1758,6 +1746,7 @@ static void tcp_conn_from_tap(struct ctx *c,
 	const struct sockaddr *sa;
 	struct tcp_tap_conn *conn;
 	union flow *flow;
+	uint64_t hash;
 	socklen_t sl;
 	int s, mss;
 
@@ -1824,10 +1813,10 @@ static void tcp_conn_from_tap(struct ctx *c,
 	conn->seq_from_tap = conn->seq_init_from_tap + 1;
 	conn->seq_ack_to_tap = conn->seq_from_tap;
 
-	tcp_seq_init(c, conn, now);
-	conn->seq_ack_from_tap = conn->seq_to_tap;
+	hash = flow_hash_insert(c, FLOW_SIDX(conn, TAPSIDE));
 
-	flow_hash_insert(c, FLOW_SIDX(conn, TAPSIDE));
+	conn->seq_to_tap = tcp_init_seq(hash, now);
+	conn->seq_ack_from_tap = conn->seq_to_tap;
 
 	if (!bind(s, sa, sl)) {
 		tcp_rst(c, conn);	/* Nobody is listening then */
@@ -2518,6 +2507,8 @@ static void tcp_tap_conn_from_sock(struct ctx *c,
 				   struct tcp_tap_conn *conn, int s,
 				   const struct timespec *now)
 {
+	uint64_t hash;
+
 	ASSERT(flowside_complete(SOCKFSIDE(conn)));
 
 	conn->f.type = FLOW_TCP;
@@ -2544,8 +2535,8 @@ static void tcp_tap_conn_from_sock(struct ctx *c,
 	FLOW_FWD_DBG(conn, TAPSIDE);
 	ASSERT(flow_complete(&conn->f));
 
-	tcp_seq_init(c, conn, now);
-	flow_hash_insert(c, FLOW_SIDX(conn, TAPSIDE));
+	hash = flow_hash_insert(c, FLOW_SIDX(conn, TAPSIDE));
+	conn->seq_to_tap = tcp_init_seq(hash, now);
 
 	conn->seq_ack_from_tap = conn->seq_to_tap;
 
-- 
2.43.0