From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from gandalf.ozlabs.org (gandalf.ozlabs.org [150.107.74.76]) by passt.top (Postfix) with ESMTPS id DBEA05A0274 for ; Thu, 7 Dec 2023 06:53:59 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gibson.dropbear.id.au; s=202312; t=1701928435; bh=RdKB3VxWqEwxP7sTuJl670UcTjoX9GB6ntOvuMElH5g=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=fjLoJWA7qMU4+I9NuxrAV/fLibTrRRSnH0SdFSyAAkFa+g6N0Z4JOMlLinoJBW9+q dcrKRXZsWwnGD6ssKKSQWvRQ0sm3S74NPAh4Y+ODxhZe5NCunCkxmUC3Ou+kmlivfT tIgNUpfJuxpboum7Ixuz6yOpb+/Dw4u3KJCBcceIM0xZTMzsrkJBH47Gzw/nXE0ZHB Fkv+ukeqt76AypFrFBAHHc2wkiNaYtDJ1nRwpuvNHdNuoFl0Hbv4tRC8vkcOj055LK iRQoGcTkALdsLjdo7R5QX1o8RY8pBPMKLxppLsE2NYrhWPL1DnouYNfx3n2bmo8H4O A+8bQz/XJAUhg== Received: by gandalf.ozlabs.org (Postfix, from userid 1007) id 4Sm3Nz66Kxz4x1v; Thu, 7 Dec 2023 16:53:55 +1100 (AEDT) From: David Gibson To: Stefano Brivio , passt-dev@passt.top Subject: [PATCH v2 3/4] tcp: Implement hash table with indices rather than pointers Date: Thu, 7 Dec 2023 16:53:52 +1100 Message-ID: <20231207055353.1245933-4-david@gibson.dropbear.id.au> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20231207055353.1245933-1-david@gibson.dropbear.id.au> References: <20231207055353.1245933-1-david@gibson.dropbear.id.au> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Message-ID-Hash: 23PZ7WEOLEWUEE6EINLXLH2PQAG3SCQH X-Message-ID-Hash: 23PZ7WEOLEWUEE6EINLXLH2PQAG3SCQH X-MailFrom: dgibson@gandalf.ozlabs.org X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: David Gibson X-Mailman-Version: 3.3.8 Precedence: list List-Id: Development discussion and patches for passt Archived-At: Archived-At: List-Archive: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: We implement our hash table with pointers to the entry for each bucket (or NULL). However, the entries are always allocated within the flow table, meaning that a flow index will suffice, halving the size of the hash table. For TCP, just a flow index would be enough, but future uses will want to expand the hash table to cover indexing either side of a flow, so use a flow_sidx_t as the type for each hash bucket. Signed-off-by: David Gibson --- flow.h | 11 +++++++++++ tcp.c | 33 ++++++++++++++++++++++----------- 2 files changed, 33 insertions(+), 11 deletions(-) diff --git a/flow.h b/flow.h index c2a5190..959b461 100644 --- a/flow.h +++ b/flow.h @@ -53,6 +53,17 @@ static_assert(sizeof(flow_sidx_t) <= sizeof(uint32_t), #define FLOW_SIDX_NONE ((flow_sidx_t){ .flow = FLOW_MAX }) +/** + * flow_sidx_eq() - Test if two sidx values are equal + * @a, @b: sidx values + * + * Return: true iff @a and @b refer to the same side of the same flow + */ +static inline bool flow_sidx_eq(flow_sidx_t a, flow_sidx_t b) +{ + return (a.flow == b.flow) && (a.side == b.side); +} + union flow; void flow_table_compact(struct ctx *c, union flow *hole); diff --git a/tcp.c b/tcp.c index cd8e64e..8dc9f31 100644 --- a/tcp.c +++ b/tcp.c @@ -574,7 +574,7 @@ static unsigned int tcp6_l2_flags_buf_used; #define CONN(idx) (&(FLOW(idx)->tcp)) /* Table for lookup from remote address, local port, remote port */ -static struct tcp_tap_conn *tc_hash[TCP_HASH_TABLE_SIZE]; +static flow_sidx_t tc_hash[TCP_HASH_TABLE_SIZE]; static_assert(ARRAY_SIZE(tc_hash) >= FLOW_MAX, "Safe linear probing requires hash table larger than connection table"); @@ -1197,10 +1197,12 @@ static unsigned int tcp_conn_hash(const struct ctx *c, static inline unsigned tcp_hash_probe(const struct ctx *c, const struct tcp_tap_conn *conn) { + flow_sidx_t sidx = FLOW_SIDX(conn, TAPSIDE); unsigned b = tcp_conn_hash(c, conn); /* Linear probing */ - while (tc_hash[b] && tc_hash[b] != conn) + while (!flow_sidx_eq(tc_hash[b], FLOW_SIDX_NONE) && + !flow_sidx_eq(tc_hash[b], sidx)) b = mod_sub(b, 1, TCP_HASH_TABLE_SIZE); return b; @@ -1215,7 +1217,7 @@ static void tcp_hash_insert(const struct ctx *c, struct tcp_tap_conn *conn) { unsigned b = tcp_hash_probe(c, conn); - tc_hash[b] = conn; + tc_hash[b] = FLOW_SIDX(conn, TAPSIDE); flow_dbg(conn, "hash table insert: sock %i, bucket: %u", conn->sock, b); } @@ -1228,16 +1230,18 @@ static void tcp_hash_remove(const struct ctx *c, const struct tcp_tap_conn *conn) { unsigned b = tcp_hash_probe(c, conn), s; + union flow *flow = flow_at_sidx(tc_hash[b]); - if (!tc_hash[b]) + if (!flow) return; /* Redundant remove */ flow_dbg(conn, "hash table remove: sock %i, bucket: %u", conn->sock, b); /* Scan the remainder of the cluster */ - for (s = mod_sub(b, 1, TCP_HASH_TABLE_SIZE); tc_hash[s]; + for (s = mod_sub(b, 1, TCP_HASH_TABLE_SIZE); + (flow = flow_at_sidx(tc_hash[s])); s = mod_sub(s, 1, TCP_HASH_TABLE_SIZE)) { - unsigned h = tcp_conn_hash(c, tc_hash[s]); + unsigned h = tcp_conn_hash(c, &flow->tcp); if (!mod_between(h, s, b, TCP_HASH_TABLE_SIZE)) { /* tc_hash[s] can live in tc_hash[b]'s slot */ @@ -1247,7 +1251,7 @@ static void tcp_hash_remove(const struct ctx *c, } } - tc_hash[b] = NULL; + tc_hash[b] = FLOW_SIDX_NONE; } /** @@ -1262,10 +1266,10 @@ void tcp_tap_conn_update(const struct ctx *c, struct tcp_tap_conn *old, { unsigned b = tcp_hash_probe(c, old); - if (!tc_hash[b]) + if (!flow_at_sidx(tc_hash[b])) return; /* Not in hash table, nothing to update */ - tc_hash[b] = new; + tc_hash[b] = FLOW_SIDX(new, TAPSIDE); debug("TCP: hash table update: old index %u, new index %u, sock %i, " "bucket: %u", FLOW_IDX(old), FLOW_IDX(new), new->sock, b); @@ -1288,15 +1292,17 @@ static struct tcp_tap_conn *tcp_hash_lookup(const struct ctx *c, in_port_t eport, in_port_t fport) { union inany_addr aany; + union flow *flow; unsigned b; inany_from_af(&aany, af, faddr); b = tcp_hash(c, &aany, eport, fport); - while (tc_hash[b] && !tcp_hash_match(tc_hash[b], &aany, eport, fport)) + while ((flow = flow_at_sidx(tc_hash[b])) && + !tcp_hash_match(&flow->tcp, &aany, eport, fport)) b = mod_sub(b, 1, TCP_HASH_TABLE_SIZE); - return tc_hash[b]; + return &flow->tcp; } /** @@ -3087,6 +3093,11 @@ static void tcp_sock_refill_init(const struct ctx *c) */ int tcp_init(struct ctx *c) { + unsigned b; + + for (b = 0; b < TCP_HASH_TABLE_SIZE; b++) + tc_hash[b] = FLOW_SIDX_NONE; + if (c->ifi4) tcp_sock4_iov_init(c); -- 2.43.0