Zack's Kernel News
Zack's Kernel News
Zack Brown reports on improving a hashing function, constant values adjustable at boot time, and dealing with an Intel design flaw.
Improving a Hashing Function
Amir Goldstein posted a small fix to a kernel function that would produce a unique hash value for an input string. He noticed that for 64-bit values, some bits were lost before calculating the hash – resulting in a slightly less good hash. For 32-bit values, he said, no bits were lost, and the code was left unchanged, but since the relevant stringhash.h file had no official maintainer, and Linus Torvalds had done some work on it in the past, Amir asked Linus what he thought of the fix and for advice on how to test it. As Amir put it, "I wouldn't even know where to begin testing its affects, or how to prove if there really is a problem."
Linus dug back into his memory, saying he believed the lost bits were intentional, though he acknowledged, "it's a long time ago, and we've changed some of the hashing since."
But Linus also said, "you're wrong that it's a no-op on 32-bit. It's a very expensive and pointless multiplication there too, even if the shift ends up being a no-op. The name hashing is pretty performance-sensitive."
[...]
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
US / Canada
UK / Australia