SipHash in the kernel

Posted Jul 15, 2024 13:34 UTC (Mon) by Wol (subscriber, #4433)
In reply to: SipHash in the kernel by LtWorf
Parent article: SipHash in the kernel

Except the existing implementations already do exactly that.

I got involved in a discussion about hashing, for some reason, and the kernel algorithms go as far as completely rebuilding the hash list if they think an attack is under way.

It's not that expensive in the grand scheme of things. Either the hash list is small, or it's badly degraded. So either the cost IS minimal, or it's RELATIVELY minimal.

Cheers,
Wol

SipHash in the kernel

Posted Jul 15, 2024 16:05 UTC (Mon) by Wol (subscriber, #4433) [Link]

And I'm somewhat out of my depth here, but it's something along the lines of:

Set up a second hash table.
Tell the search algorithm to search both tables.
Add all new entries to the new table.
Use something like RCU to copy entries from the old table to the new.

So performance is still degraded for a little bit as the old table still has to be searched, but it improves rapidly as normal processing will remove a load of entries from the degraded hash, and RCU will remove the rest. Or even it doesn't bother cleaning up the old hash straight away, as it expects normal operation to reap a lot of entries pretty quickly.

Cheers,
Wol