From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from gandalf.ozlabs.org (mail.ozlabs.org [IPv6:2404:9400:2221:ea00::3]) by passt.top (Postfix) with ESMTPS id 76FEF5A026F for ; Thu, 7 Dec 2023 02:09:42 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gibson.dropbear.id.au; s=202312; t=1701911376; bh=2S5fImfNGmAoNuQppaLXLa+DVll2GOme8sKsaa8gPSw=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=lS8d9Ylvo/1asqaiQSKYpI13ZnLRmEQvXcoHla9FuwEUbHKsy5jRj7Cuk0XqsiuX+ oRiFvoq0OqHxAmcwKJHDsieN79qUA0O2Law6kD+lMOvEyN7k7fXwOzuhK2+IAifZXh tOEWDIHmYO2FKPeW3HGt9p49rz+hJ50XbIZLdtOKWbFaEZx77o8u5th1ZNrOnWDuQt tb3Izu1L1N7RVEr8EDHGDLTYtvKj+DmVl6VdJgN5BIpMO7RDvR7GY1i5D2D9RSZ+r+ xIszySjLvGTVqkuGP3QMIeW9Hivi954qYdg8zG3yLR3ojZp5kWZ2bwsuBjKbQIyf+m AmafRRo/MJQCQ== Received: by gandalf.ozlabs.org (Postfix, from userid 1007) id 4Slx4w09Blz4wc6; Thu, 7 Dec 2023 12:09:36 +1100 (AEDT) Date: Thu, 7 Dec 2023 12:04:18 +1100 From: David Gibson To: Stefano Brivio Subject: Re: [PATCH 2/3] tcp: Implement hash table with indices rather than pointers Message-ID: References: <20231204031611.3566791-1-david@gibson.dropbear.id.au> <20231204031611.3566791-3-david@gibson.dropbear.id.au> <20231206203727.31014fd6@elisabeth> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="9DMcFfkqH8r6CvhB" Content-Disposition: inline In-Reply-To: <20231206203727.31014fd6@elisabeth> Message-ID-Hash: I7QVUY5BIX57WBEHKHN4ITK264UWW324 X-Message-ID-Hash: I7QVUY5BIX57WBEHKHN4ITK264UWW324 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: 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: --9DMcFfkqH8r6CvhB Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Dec 06, 2023 at 08:37:27PM +0100, Stefano Brivio wrote: > On Mon, 4 Dec 2023 14:16:10 +1100 > David Gibson wrote: >=20 > > 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 ta= ble. > >=20 > > 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. > >=20 > > Signed-off-by: David Gibson > > --- > > flow.h | 11 +++++++++++ > > tcp.c | 34 +++++++++++++++++++++++----------- > > 2 files changed, 34 insertions(+), 11 deletions(-) > >=20 > > 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) <=3D sizeof(uint32= _t), > > =20 > > #define FLOW_SIDX_NONE ((flow_sidx_t){ .flow =3D FLOW_MAX }) >=20 > In hindsight, while reviewing the functions below: FLOW_MAX should > probably be MAX_FROM_BITS(FLOW_INDEX_BITS) - 1 instead (and those >=3D > 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). Right, either that or name the variable MAX_NUM_FLOWS or something. Eh, whatever. > > +/** > > + * 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 =3D=3D b.flow) && (a.side =3D=3D b.side); > > +} > > + > > union flow; > > =20 > > 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)) > > =20 > > /* 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]; > > =20 > > static_assert(ARRAY_SIZE(tc_hash) >=3D 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 =3D FLOW_SIDX(conn, TAPSIDE); > > unsigned b; > > =20 > > /* Linear probing */ > > - for (b =3D tcp_conn_hash(c, conn); tc_hash[b] && tc_hash[b] !=3D conn; > > + for (b =3D tcp_conn_hash(c, conn); > > + !flow_sidx_eq(tc_hash[b], FLOW_SIDX_NONE) && >=20 > 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. Yes: we need to stop when we reach something matching @sidx *or* we hit an empty entry. Otherwise we'll never terminate if the entry isn't in there. > 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. Yeah, I wondered that too, it's probably a good idea for safety. I'll look at implementing that. > > + !flow_sidx_eq(tc_hash[b], sidx); > > b =3D (b + 1) % TCP_HASH_TABLE_SIZE) > > ; >=20 > I respect the fact that this is fundamentally a for loop. :) On the > other hand: >=20 > unsigned b =3D tcp_conn_hash(c, conn); >=20 > while (!flow_sidx_eq(tc_hash[b], sidx)) > b =3D (b + 1) % TCP_HASH_TABLE_SIZE); >=20 > ...would be a bit more readable? Hm, fair point. I think the while looked uglier in some earlier versions before I added the _probe() helper so it was duplicated in several places. > > =20 > > @@ -1216,7 +1219,7 @@ static void tcp_hash_insert(const struct ctx *c, = struct tcp_tap_conn *conn) > > { > > unsigned b =3D tcp_hash_probe(c, conn); > > =20 > > - tc_hash[b] =3D conn; > > + tc_hash[b] =3D FLOW_SIDX(conn, TAPSIDE); > > flow_dbg(conn, "hash table insert: sock %i, bucket: %u", conn->sock, = b); > > } > > =20 > > @@ -1229,16 +1232,18 @@ static void tcp_hash_remove(const struct ctx *c, > > const struct tcp_tap_conn *conn) > > { > > unsigned b =3D tcp_hash_probe(c, conn), s; > > + union flow *flow =3D flow_at_sidx(tc_hash[b]); > > =20 > > - if (!tc_hash[b]) > > + if (!flow) > > return; /* Redundant remove */ > > =20 > > flow_dbg(conn, "hash table remove: sock %i, bucket: %u", conn->sock, = b); > > =20 > > /* Scan the remainder of the cluster */ > > - for (s =3D (b + 1) % TCP_HASH_TABLE_SIZE; tc_hash[s]; > > + for (s =3D (b + 1) % TCP_HASH_TABLE_SIZE; > > + (flow =3D flow_at_sidx(tc_hash[s])); > > s =3D (s + 1) % TCP_HASH_TABLE_SIZE) { > > - unsigned h =3D tcp_conn_hash(c, tc_hash[s]); > > + unsigned h =3D tcp_conn_hash(c, &flow->tcp); > > =20 > > 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, > > } > > } > > =20 > > - tc_hash[b] =3D NULL; > > + tc_hash[b] =3D FLOW_SIDX_NONE; > > } > > =20 > > /** > > @@ -1263,10 +1268,10 @@ void tcp_tap_conn_update(const struct ctx *c, s= truct tcp_tap_conn *old, > > { > > unsigned b =3D tcp_hash_probe(c, old); > > =20 > > - if (!tc_hash[b]) > > + if (!flow_at_sidx(tc_hash[b])) > > return; /* Not in hash table, nothing to update */ > > =20 > > - tc_hash[b] =3D new; > > + tc_hash[b] =3D FLOW_SIDX(new, TAPSIDE); > > =20 > > 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(con= st struct ctx *c, > > in_port_t eport, in_port_t fport) > > { > > union inany_addr aany; > > + union flow *flow; > > unsigned b; > > =20 > > inany_from_af(&aany, af, faddr); > > =20 > > for (b =3D tcp_hash(c, &aany, eport, fport); > > - tc_hash[b] && !tcp_hash_match(tc_hash[b], &aany, eport, fport); > > + (flow =3D flow_at_sidx(tc_hash[b])) > > + && !tcp_hash_match(&flow->tcp, &aany, eport, fport); >=20 > Same as above about readability (somehow clashing with correctness). >=20 > > b =3D (b + 1) % TCP_HASH_TABLE_SIZE) > > ; > > =20 > > - return tc_hash[b]; > > + return &flow->tcp; > > } > > =20 > > /** > > @@ -3090,6 +3097,11 @@ static void tcp_sock_refill_init(const struct ct= x *c) > > */ > > int tcp_init(struct ctx *c) > > { > > + unsigned b; > > + > > + for (b =3D 0; b < TCP_HASH_TABLE_SIZE; b++) > > + tc_hash[b] =3D FLOW_SIDX_NONE; > > + > > if (c->ifi4) > > tcp_sock4_iov_init(c); > > =20 >=20 --=20 David Gibson | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson --9DMcFfkqH8r6CvhB Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEEO+dNsU4E3yXUXRK2zQJF27ox2GcFAmVxGgAACgkQzQJF27ox 2Gf4Dg//auaBY5ZfJhK+tjcslHozQcImMyPd2Xi/wibWPzL3g/amznba/+UqwipL H/36z6OuKY9KjlWXUofwLJC+CATCfZ860VZN7FcJsc/Dd9bfW+OsPuKnaRERspBD 3GiHUT/Y0iKXD/tu7issUaB2cNtelSUFERx4VN6/CClBKzQpL8NW9tJrSi4nnEq3 RjG1hlCnOe2JCjfM+wefUfFX8/jLAR+WtwYe1WPe9WKIsiGnQ2oA0eYJYxcYnFcA 69rGHsO/DFOFTG29WIQ5Q4qn4X65ThOk1h12yNvDb5MN/YV3rgTw76HP9KjOYmBE w9jY1IvNTFvgPBIfEUOM2RgbhYFkC9aJUNSO4KqfgmntvLArfQnLK1J8NVeKlMYS s+3CWyCbfBjWsCr/81ObZ+6miXUzH25hH4vfZBg0/zQ4d/fcKrgJH/ieX0GCP4yl KqMzO3vho17ucq1XOoDM88cGTHaMQ6lpIHl+u0NsgkqznkFB8Pf03QDHDRfCe+50 lJANic4DDQvQHkUSmg+fEwhaxTYwM9DYnIBTmIIksRW9PWQ7wrQWSCvLyQuRdl01 1AHYuWnrQ75JTPPlH/gPnd4CQUou4CIw4yTvtACNj4YRbaPvBSAb+5iyy2BhvDiL 34f2UG7oQ2/Hfw85JJzaBY8pyJ9tdPq6uC2GyXwKsfr918vmO+8= =U5Tv -----END PGP SIGNATURE----- --9DMcFfkqH8r6CvhB--