From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by passt.top (Postfix) with ESMTP id 4485D5A026F for ; Wed, 6 Dec 2023 20:38:00 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1701891479; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=20tDLT5XP/IcqVMUazYniga6rT1fgh7Odk87sX84nfE=; b=MrgjcvOB3+S9JY7G+YAmDsNvryKhGZCkPqqIELCCHTdVdiI6nWp6RVwcuJX/jA9/p601Cc UoLLPNFI4xL9KA4QuYSAFh2g+uCmTNm1UO8q+pDL5N4OW5Mif3HsGMzJiT9zHmT8S2yIgv 9atjFUjCl4QB1YHTvtp4Lji+tQ71DtA= Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-251-ZAM7RTxmNrG3ME2jA8DXTw-1; Wed, 06 Dec 2023 14:37:52 -0500 X-MC-Unique: ZAM7RTxmNrG3ME2jA8DXTw-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.rdu2.redhat.com [10.11.54.4]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 340C728BBCD3; Wed, 6 Dec 2023 19:37:50 +0000 (UTC) Received: from elisabeth (unknown [10.39.208.4]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 6C2672026D66; Wed, 6 Dec 2023 19:37:49 +0000 (UTC) Date: Wed, 6 Dec 2023 20:37:27 +0100 From: Stefano Brivio To: David Gibson Subject: Re: [PATCH 2/3] tcp: Implement hash table with indices rather than pointers Message-ID: <20231206203727.31014fd6@elisabeth> In-Reply-To: <20231204031611.3566791-3-david@gibson.dropbear.id.au> References: <20231204031611.3566791-1-david@gibson.dropbear.id.au> <20231204031611.3566791-3-david@gibson.dropbear.id.au> Organization: Red Hat MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.4 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Message-ID-Hash: 625Y2DNBAX3H4CSO5IQ35K5RHTCQI46P X-Message-ID-Hash: 625Y2DNBAX3H4CSO5IQ35K5RHTCQI46P X-MailFrom: sbrivio@redhat.com 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: passt-dev@passt.top 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: On Mon, 4 Dec 2023 14:16:10 +1100 David Gibson wrote: > 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 | 34 +++++++++++++++++++++++----------- > 2 files changed, 34 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 }) In hindsight, while reviewing the functions below: FLOW_MAX should probably be MAX_FROM_BITS(FLOW_INDEX_BITS) - 1 instead (and those >= comparisons would happily become >), so that we don't need to have a "maximum" value that's also not allowed (then, strictly speaking, it's more than the maximum). > +/** > + * 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 09acf7f..7e438b7 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,13 @@ 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; > > /* Linear probing */ > - for (b = tcp_conn_hash(c, conn); tc_hash[b] && tc_hash[b] != conn; > + for (b = tcp_conn_hash(c, conn); > + !flow_sidx_eq(tc_hash[b], FLOW_SIDX_NONE) && Do we actually need to check for FLOW_SIDX_NONE explicitly? That is, sidx we get as input here should never be FLOW_SIDX_NONE. I wonder if it makes sense to take care of the possible "overflow" outcome from step L4. of algorithm L you mentioned in 1/3. It *shouldn't* because you're enforcing the minimum size of the hash table, I wonder if it's a good idea anyway. > + !flow_sidx_eq(tc_hash[b], sidx); > b = (b + 1) % TCP_HASH_TABLE_SIZE) > ; I respect the fact that this is fundamentally a for loop. :) On the other hand: unsigned b = tcp_conn_hash(c, conn); while (!flow_sidx_eq(tc_hash[b], sidx)) b = (b + 1) % TCP_HASH_TABLE_SIZE); ...would be a bit more readable? > > @@ -1216,7 +1219,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); > } > > @@ -1229,16 +1232,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 = (b + 1) % TCP_HASH_TABLE_SIZE; tc_hash[s]; > + 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, tc_hash[s]); > + unsigned h = tcp_conn_hash(c, &flow->tcp); > > if (in_mod_range(h, b, s, TCP_HASH_TABLE_SIZE)) { > /* tc_hash[s] can live in tc_hash[b]'s slot */ > @@ -1248,7 +1253,7 @@ static void tcp_hash_remove(const struct ctx *c, > } > } > > - tc_hash[b] = NULL; > + tc_hash[b] = FLOW_SIDX_NONE; > } > > /** > @@ -1263,10 +1268,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); > @@ -1289,16 +1294,18 @@ 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); > > for (b = tcp_hash(c, &aany, eport, fport); > - tc_hash[b] && !tcp_hash_match(tc_hash[b], &aany, eport, fport); > + (flow = flow_at_sidx(tc_hash[b])) > + && !tcp_hash_match(&flow->tcp, &aany, eport, fport); Same as above about readability (somehow clashing with correctness). > b = (b + 1) % TCP_HASH_TABLE_SIZE) > ; > > - return tc_hash[b]; > + return &flow->tcp; > } > > /** > @@ -3090,6 +3097,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); > -- Stefano