• Thomas Graf's avatar
    [PKT_SCHED]: improve hashing performance of cls_fw · c5c13faf
    Thomas Graf authored
    Calculate hashtable size to fit into a page instead of a hardcoded
    256 buckets hash table. Results in a 1024 buckets hashtable on
    most systems.
    
    Replace old naive extract-8-lsb-bits algorithm with a better
    algorithm xor'ing 3 or 4 bit fields at the size of the hashtable
    array index in order to improve distribution if the majority of
    the lower bits are unused while keeping zero collision behaviour
    for the most common use case.
    
    Thanks to Wang Jian <lark@linux.net.cn> for bringing this issue
    to attention and to Eran Mann <emann@mrv.com> for the initial
    idea for this new algorithm.
    Signed-off-by: default avatarThomas Graf <tgraf@suug.ch>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    c5c13faf
cls_fw.c 8.26 KB