Zack's Kernel News

Global Hash Table Implementation

What can happen in big software projects is that developers implement the same low-level feature over and over again. Some sort of helper code would be useful, so they create it in their little area of the project and use it happily, never realizing that there are similar helpers scattered all over the codebase.

One such useful gizmo is the hash table. Sasha Levin recently submitted some code for a simple hash table implementation, specifically so it wouldn't need to be reimplemented all over the place by other kernel hackers.

The whole point of a hash table is that it's fast. You put in a key, and you get out the value, quick as a wink, and your code can continue on its merry way. This is especially important when the hash table is in the operating system kernel, because if the kernel is slow, it can make all the user programs slow as well. So, among other optimizations, Sasha's code used macros wherever possible, to shunt as much actual work as possible onto the compiler. Things like the size of the hash key, for example, can be calculated at compile time and not take up any cycles in the running kernel.

[...]