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 348D45A026F for ; Wed, 6 Dec 2023 23:43:44 +0100 (CET) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1701902623; 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=Iy9XUyE9hzn2tAc9X8A5m8qz0m7ih1lCtXoOgLdCVkk=; b=Y7yK1PWnaYdC/NYV7p9moat3xCDHMYGfWOL+3KlZlOiN25hxE4yBhMsNt/RIurdkSHaEYF cHZ95QNfKh36fYx3xOCuP4IhguNka6f5BRmDFKgTsRH/yEicu2fnevlu7HHPSezvQJ8F1z UglL7QYDszSJGmzi7QYNWisdXO0kNVA= Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-231-O7gXVapYOyqC_TZTRqwfEg-1; Wed, 06 Dec 2023 17:43:39 -0500 X-MC-Unique: O7gXVapYOyqC_TZTRqwfEg-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.rdu2.redhat.com [10.11.54.1]) (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 59B2988F5A5; Wed, 6 Dec 2023 22:43:39 +0000 (UTC) Received: from elisabeth (unknown [10.39.208.4]) by smtp.corp.redhat.com (Postfix) with ESMTPS id 9445A3C2E; Wed, 6 Dec 2023 22:43:38 +0000 (UTC) Date: Wed, 6 Dec 2023 23:43:29 +0100 From: Stefano Brivio To: David Gibson Subject: Re: [PATCH 1/3] tcp: Switch hash table to linear probing instead of chaining Message-ID: <20231206234329.67bd6a38@elisabeth> In-Reply-To: <20231204031611.3566791-2-david@gibson.dropbear.id.au> References: <20231204031611.3566791-1-david@gibson.dropbear.id.au> <20231204031611.3566791-2-david@gibson.dropbear.id.au> Organization: Red Hat MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.1 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Message-ID-Hash: B2INXIALPLVEP7PZEVOPNLE7IAW372F4 X-Message-ID-Hash: B2INXIALPLVEP7PZEVOPNLE7IAW372F4 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:09 +1100 David Gibson wrote: > 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. > > 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. > > This approach can perform poorly with hash table load is high. However, we > already size our hash table of pointers larger than the connection table, > which puts an upper bound on the load. It's relatively cheap to decrease > that bound if we find we need to. > > I adapted the linear probing operations from Knuth's The Art of Computer > Programming, Volume 3, 2nd Edition. Specifically Algorithm L and Algorithm > R in Section 6.4. Note that there is an error in Algorithm R as printed, > see errata at [0]. > > [0] https://www-cs-faculty.stanford.edu/~knuth/all3-prepre.ps.gz > > Signed-off-by: David Gibson > --- > tcp.c | 111 +++++++++++++++++++++++++++-------------------------- > tcp_conn.h | 2 - > util.h | 13 +++++++ > 3 files changed, 69 insertions(+), 57 deletions(-) > > 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; > > #define CONN(idx) (&(FLOW(idx)->tcp)) > > -/** 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 >= FLOW_MAX) > - return NULL; > - ASSERT(CONN(idx)->f.type == 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]; > > +static_assert(ARRAY_SIZE(tc_hash) >= 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 ctx *c, > return tcp_hash(c, &conn->faddr, conn->eport, conn->fport); > } > > +/** > + * 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 suitable > + * 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 = tcp_conn_hash(c, conn); tc_hash[b] && tc_hash[b] != conn; > + b = (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 = tcp_hash_probe(c, conn); > > - b = tcp_hash(c, &conn->faddr, conn->eport, conn->fport); > - conn->next_index = tc_hash[b] ? FLOW_IDX(tc_hash[b]) : -1U; > tc_hash[b] = 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); > } > > /** > @@ -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 = NULL; > - int b = tcp_conn_hash(c, conn); > + unsigned b = tcp_hash_probe(c, conn), s; > > - for (entry = tc_hash[b]; entry; > - prev = entry, entry = conn_at_idx(entry->next_index)) { > - if (entry == conn) { > - if (prev) > - prev->next_index = conn->next_index; > - else > - tc_hash[b] = 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 = (b + 1) % TCP_HASH_TABLE_SIZE; tc_hash[s]; > + s = (s + 1) % TCP_HASH_TABLE_SIZE) { > + unsigned h = 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] = tc_hash[s]; > + b = s; > } > } 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? -- Stefano