From 5913f2641506c0c6df32baf2556f683d7c5e6185 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Thu, 7 Dec 2023 16:53:51 +1100 Subject: 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 Signed-off-by: Stefano Brivio --- util.h | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) (limited to 'util.h') 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 * -- cgit v1.2.3