Re: [PATCH 2/3] tcp: Implement hash table with indices rather than pointers

On Thu, 7 Dec 2023 12:04:18 +1100
David Gibson <david(a)gibson.dropbear.id.au> wrote:

...
  On Wed, Dec 06, 2023 at 08:37:27PM +0100, Stefano
Brivio wrote:
  On Mon,  4 Dec 2023 14:16:10 +1100
 David Gibson <david(a)gibson.dropbear.id.au> 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 <david(a)gibson.dropbear.id.au>
 ---
  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).   
 
 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 == 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.   
 
 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. 
Ah, right, sorry, for a moment I read this as:

	!flow_sidx_eq(tc_hash[b], FLOW_SIDX_NONE) &&
	flow_sidx_eq(tc_hash[b], sidx);

where sidx != FLOW_SIDX_NONE would have the first comparison redundant.
But it's not the case, of course.

-- 
Stefano