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 572B15A026F for ; Thu, 7 Dec 2023 05:37:10 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gibson.dropbear.id.au; s=202312; t=1701923823; bh=y0RMd8Cyt93cwUAh6gdAFD6kfDDLM6zKE6QDTiqO0aM=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=BpUKzyCNIXsel+nT6ohrbPUpwo2n7gpDzBYgIWodS2IBnqQG/rOtRlGd+yFbpewK0 odnZRVuON7+7FpowlvEoq1HdsL6DqEOb9ViDQ204j/O36CDgIwKHZkDaHmG4PvbGwX MsoHp2TnIm6jHkutktjCbN4gDL9adZNek+ZK+b5v2vc7nK3xeeETUQH4TEyfE2ezTt fQsKbbs/Nw5eq85x5eku8/AeowkCQorKeR8gnOPv1FvJIv9TFSpRFaOLMA+zhu/aJZ 9KJUqTMIchNjE4QdQczBkhQ2126PbVncJHjdYm1FnuAoN/u6ldaqpHLXC3cI7MxVIY 3WCwyAnT3Ltng== Received: by gandalf.ozlabs.org (Postfix, from userid 1007) id 4Sm1hH5ZQLz4wdB; Thu, 7 Dec 2023 15:37:03 +1100 (AEDT) Date: Thu, 7 Dec 2023 15:11:42 +1100 From: David Gibson To: Stefano Brivio Subject: Re: [PATCH 1/3] tcp: Switch hash table to linear probing instead of chaining Message-ID: References: <20231204031611.3566791-1-david@gibson.dropbear.id.au> <20231204031611.3566791-2-david@gibson.dropbear.id.au> <20231206234329.67bd6a38@elisabeth> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="+jHbdmZnA08Fo7ch" Content-Disposition: inline In-Reply-To: <20231206234329.67bd6a38@elisabeth> Message-ID-Hash: 3KPJPKP2LO5PCT6BLIWPJE7YHUX2JQBW X-Message-ID-Hash: 3KPJPKP2LO5PCT6BLIWPJE7YHUX2JQBW 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: --+jHbdmZnA08Fo7ch Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Dec 06, 2023 at 11:43:29PM +0100, Stefano Brivio wrote: > On Mon, 4 Dec 2023 14:16:09 +1100 > David Gibson wrote: >=20 > > Currently we deal with hash collisions by letting a hash bucket contain > > multiple entries, forming a linked list using an index in the connection > > structure. > >=20 > > That's a pretty standard and simple approach, but in our case we can use > > an even simpler one: linear probing. Here if a hash bucket is occupied > > we just move onto the next one until we find a feww one. This slightly > > simplifies lookup and more importantly saves some precious bytes in the > > connection structure by removing the need for a link. It does require = some > > additional complexity for hash removal. > >=20 > > This approach can perform poorly with hash table load is high. However= , we > > already size our hash table of pointers larger than the connection tabl= e, > > which puts an upper bound on the load. It's relatively cheap to decrea= se > > that bound if we find we need to. > >=20 > > I adapted the linear probing operations from Knuth's The Art of Computer > > Programming, Volume 3, 2nd Edition. Specifically Algorithm L and Algor= ithm > > R in Section 6.4. Note that there is an error in Algorithm R as printe= d, > > see errata at [0]. > >=20 > > [0] https://www-cs-faculty.stanford.edu/~knuth/all3-prepre.ps.gz > >=20 > > Signed-off-by: David Gibson > > --- > > tcp.c | 111 +++++++++++++++++++++++++++-------------------------- > > tcp_conn.h | 2 - > > util.h | 13 +++++++ > > 3 files changed, 69 insertions(+), 57 deletions(-) > >=20 > > diff --git a/tcp.c b/tcp.c > > index 17c7cba..09acf7f 100644 > > --- a/tcp.c > > +++ b/tcp.c > > @@ -573,22 +573,12 @@ static unsigned int tcp6_l2_flags_buf_used; > > =20 > > #define CONN(idx) (&(FLOW(idx)->tcp)) > > =20 > > -/** conn_at_idx() - Find a connection by index, if present > > - * @idx: Index of connection to lookup > > - * > > - * Return: pointer to connection, or NULL if @idx is out of bounds > > - */ > > -static inline struct tcp_tap_conn *conn_at_idx(unsigned idx) > > -{ > > - if (idx >=3D FLOW_MAX) > > - return NULL; > > - ASSERT(CONN(idx)->f.type =3D=3D FLOW_TCP); > > - return CONN(idx); > > -} > > - > > /* Table for lookup from remote address, local port, remote port */ > > static struct tcp_tap_conn *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= "); > > + > > /* Pools for pre-opened sockets (in init) */ > > int init_sock_pool4 [TCP_SOCK_POOL_SIZE]; > > int init_sock_pool6 [TCP_SOCK_POOL_SIZE]; > > @@ -1196,6 +1186,27 @@ static unsigned int tcp_conn_hash(const struct c= tx *c, > > return tcp_hash(c, &conn->faddr, conn->eport, conn->fport); > > } > > =20 > > +/** > > + * tcp_hash_probe() - Find hash bucket for a connection > > + * @c: Execution context > > + * @conn: Connection to find bucket for > > + * > > + * Return: If @conn is in the table, its current bucket, otherwise a s= uitable > > + * free bucket for it. > > + */ > > +static inline unsigned tcp_hash_probe(const struct ctx *c, > > + const struct tcp_tap_conn *conn) > > +{ > > + unsigned b; > > + > > + /* Linear probing */ > > + for (b =3D tcp_conn_hash(c, conn); tc_hash[b] && tc_hash[b] !=3D conn; > > + b =3D (b + 1) % TCP_HASH_TABLE_SIZE) > > + ; > > + > > + return b; > > +} > > + > > /** > > * tcp_hash_insert() - Insert connection into hash table, chain link > > * @c: Execution context > > @@ -1203,14 +1214,10 @@ static unsigned int tcp_conn_hash(const struct = ctx *c, > > */ > > static void tcp_hash_insert(const struct ctx *c, struct tcp_tap_conn *= conn) > > { > > - int b; > > + unsigned b =3D tcp_hash_probe(c, conn); > > =20 > > - b =3D tcp_hash(c, &conn->faddr, conn->eport, conn->fport); > > - conn->next_index =3D tc_hash[b] ? FLOW_IDX(tc_hash[b]) : -1U; > > tc_hash[b] =3D conn; > > - > > - flow_dbg(conn, "hash table insert: sock %i, bucket: %i, next: %p", > > - conn->sock, b, (void *)conn_at_idx(conn->next_index)); > > + flow_dbg(conn, "hash table insert: sock %i, bucket: %u", conn->sock, = b); > > } > > =20 > > /** > > @@ -1221,23 +1228,27 @@ static void tcp_hash_insert(const struct ctx *c= , struct tcp_tap_conn *conn) > > static void tcp_hash_remove(const struct ctx *c, > > const struct tcp_tap_conn *conn) > > { > > - struct tcp_tap_conn *entry, *prev =3D NULL; > > - int b =3D tcp_conn_hash(c, conn); > > + unsigned b =3D tcp_hash_probe(c, conn), s; > > =20 > > - for (entry =3D tc_hash[b]; entry; > > - prev =3D entry, entry =3D conn_at_idx(entry->next_index)) { > > - if (entry =3D=3D conn) { > > - if (prev) > > - prev->next_index =3D conn->next_index; > > - else > > - tc_hash[b] =3D conn_at_idx(conn->next_index); > > - break; > > + if (!tc_hash[b]) > > + return; /* Redundant remove */ > > + > > + flow_dbg(conn, "hash table remove: sock %i, bucket: %u", conn->sock, = b); > > + > > + /* Scan the remainder of the cluster */ > > + for (s =3D (b + 1) % TCP_HASH_TABLE_SIZE; tc_hash[s]; > > + s =3D (s + 1) % TCP_HASH_TABLE_SIZE) { > > + unsigned h =3D tcp_conn_hash(c, tc_hash[s]); > > + > > + if (in_mod_range(h, b, s, TCP_HASH_TABLE_SIZE)) { > > + /* tc_hash[s] can live in tc_hash[b]'s slot */ > > + debug("hash table remove: shuffle %u -> %u", s, b); > > + tc_hash[b] =3D tc_hash[s]; > > + b =3D s; > > } > > } >=20 > This makes intuitively sense to me, but I can't wrap my head around the > fact that it corresponds to algorithm R. Step R3 implies that, if h *is* > (cyclically) between b and s, you should skip the move and go back to R2 > right away. The condition here seems to be reversed, though. What am I > missing? Ugh... this is doing my head in a bit, because there are a bunch of stacked negatives. Ok, so the original is: "If r lies cyclically between i and j, go back to R2" Or equivalently a loop body of if (in_mod_range(r, i, j)) continue; /* Step R4/R1 stuff */ Now in this version we have r =3D> h, i =3D> s and j =3D> b, so if (in_mod_range(h, s, b)) continue; /* Step R4/R1 stuff */ Or equivalently if (!in_mod_range(h, s, b)) /* Step R4/R1 stuff */; And because of how "cyclically between" works, that becomes: if (in_mod_range(h, b, s)) /* Step R4/R1 stuff */; Which is what I have. But... the original is probing backwards through buckets whereas I'm probing forwards, which I think reverses it again. Yeah.. I'm pretty sure my version is wrong. If h =3D=3D (s-1) > b, for example, it definitely can't live in slot b, because probing would start at slot s-1, and never reach b. Hrm.. I'm going to switch mine to stepping backwards, like the Knuth, just so I'm less confused. --=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 --+jHbdmZnA08Fo7ch Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEEO+dNsU4E3yXUXRK2zQJF27ox2GcFAmVxRe4ACgkQzQJF27ox 2Gd+lQ//RL5wTzBEGOg79/PR4jsBBZpsQ5y5+AA034SMvseHQTBxBIzO0Ww98Uki 74Jk8ABlki3Gj+D9UO4E/a3c0oJEu5YLrUy1MtRWcKGPg5eQffXb/dqNvtEQzk7G ynXIyl00MKkV/UCYeWOxDNc60+EbdEy9Zy0gsf+ZSj6Ziawvj6TpW51Lb5BGmiGm 9vfyrrs5Ze4oVD7JaXFTJcJ1EOcRSrqBxiedvnAx3fHIuHKpt4awqf50gtIBmtzI YxFluHmjvBr4S32kPIaUT4xtVJyyBJxX6Di54okeJOn4LUfIVubF5RcTkoKIFOB9 Ui5vk50qbVB5VwnHcI4cKTWLQH59XIgMaOOILWD6SCr6Gy4Jll7mhtVR5CLUERFx hl9Qzqkp3gZEFRa9Z8tsUTG3W/SJN3du9up7aLP/+zyFNt/lgcnN3LQja5E+CWt4 ICTvLvGvMx6MnEPZmrFuD7gKhZ2wHvSb/FdqZsm1t/OA6imFnxlhNIj7GFCsP3q0 7oN34wZhQGVkkGZNlzmearHSrnj+hNaWjsB4K4EysrGuCmcad3HxRgfvbv7jjspf ujwBIT93Xk2klKO+sADJm/H0k90kUzU14SpzW3RkH3RINYTB4qpHRpOfA8w49sx9 9ELUmGV+8i07wgHDJsnsUUU0AuhxwytaYT10pLBMhrnHG0sKwdo= =Qdll -----END PGP SIGNATURE----- --+jHbdmZnA08Fo7ch--