Two commits has been pushed to linux-4.7.y-sl branch.
First one is an embedded rewritten version of CK's original skip list in 0480 bfs. It is similar to the code changes what CK has made in 0497, but my implementation are different in
1. Just keep one data structure, that's skiplist_node.
2. Remove kmalloc/kfree completely.
3. Remove value in skiplist_node and use container_of() to obtain the pointer of structure which skiplist_node is embedded in.
The second commit is a new implementation of skip list. In the new implementation:
A customized search function should be defined using DEFINE_SKIPLIST_INSERT macro and be used for skip list insert operation.
Random Level should be customized implemented and set to node->level then pass to the customized skiplist_insert function.
Levels start at zero and go up to (NUM_SKIPLIST_LEVEL -1).
NUM_SKIPLIST_LEVEL in this implementation is 8 instead of origin 16, considering that there will be 256 entries to enable the top level when using random level p=0.5, and that number is more than enough for a run queue in a scheduler usage. And it also help to reduce the memory usage of the embedded skip list node in task_struct to about 50%.
Based on testing, the first 8 bits in microseconds of niffies are suitable for random level population. find_first_bit() is used to satisfy p = 0.5 between each levels, and there should be platform hardware supported instruction(known as ctz/clz) to speed up this function.
The skiplist level for a task is populated when task is created and doesn't change in task's life time. When task is being inserted into run queue, this skiplist level is set to task's sl_node->level, the skiplist insert function may change it based on current level of the skip lsit.
And there is a lot enhancement in insert/delete function.
The hackbench and kernel compilation sanity both show improvement comparing the baseline version.
You can download the all in one patch of baseline version and this new implementation and have a try.
Edit: Change typo silently.