tcp: Switch hash table to linear probing instead of chaining

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 <david@gibson.dropbear.id.au>
Signed-off-by: Stefano Brivio <sbrivio@redhat.com>

1 files changed, 28 insertions, 0 deletions

diff --git a/util.h b/util.h
index 53bb54b..9446ea7 100644
--- a/util.h
+++ b/util.h
@@ -227,6 +227,34 @@ int __daemon(int pidfile_fd, int devnull_fd);
 int fls(unsigned long x);
 int write_file(const char *path, const char *buf);
 
+/**
+ * mod_sub() - Modular arithmetic subtraction
+ * @a:		Minued, unsigned value < @m
+ * @b:		Subtrahend, unsigned value < @m
+ * @m:		Modulus, must be less than (UINT_MAX / 2)
+ *
+ * Returns (@a - @b) mod @m, correctly handling unsigned underflows.
+ */
+static inline unsigned mod_sub(unsigned a, unsigned b, unsigned m)
+{
+	if (a < b)
+		a += m;
+	return a - b;
+}
+
+/**
+ * mod_between() - Determine if a value is in a cyclic range
+ * @x, @i, @j:	Unsigned values < @m
+ * @m:		Modulus
+ *
+ * Returns true iff @x is in the cyclic range of values from @i..@j (mod @m),
+ * inclusive of @i, exclusive of @j.
+ */
+static inline bool mod_between(unsigned x, unsigned i, unsigned j, unsigned m)
+{
+	return mod_sub(x, i, m) < mod_sub(j, i, m);
+}
+
 /*
  * Workarounds for https://github.com/llvm/llvm-project/issues/58992
  *