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

[Stefano Brivio <sbrivio@redhat.com>]

On Thu, 7 Dec 2023 12:04:18 +1100
David Gibson <david@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@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@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