On Fri, Nov 3, 2023 at 1:30 PM Jacob Satterfield <jsatterfield.linux@xxxxxxxxx> wrote: > > The current avtab hashtable employs a separate chaining collision > resolution strategy where each bucket/chain holds an ordered linked list > of pointers to kmem_cache allocated avtab_node elements. > > On Fedora 38 (x86_64) using the default policy, avtab_node_cachep > uses 573 slabs each containing 170 objects totaling 2,337,840 bytes. > A call to kmem_cache_zalloc() is required for every single rule, which > in the default policy is currently 96,730 and continually rising. > > When both sets of avtab_node (regular and cond.) are turned into arrays > with the hash table chain heads pointing into it, this results in only > two additional kvcalloc() calls and the complete removal of the > kmem_cache itself and its memory and runtime overheads. > > Running "perf stat -r 100 -d load_policy" has shown a runtime reduction > of around 10% on a Fedora 38 x86_64 VM with this single patch. Future > patches focused on improving the hash table's collision resolution > strategy and array layout (struct-of-arrays vs. array-of-structs) may > elicit even more caching and therefore runtime performance improvements. > > To prevent the conditional table from under-allocating the avtab_node > array, which creates a heap-overflow bug, the two-pass algorithm in the > patch "selinux: fix conditional avtab slot hint" is required. > > Signed-off-by: Jacob Satterfield <jsatterfield.linux@xxxxxxxxx> Reviewed-by: Stephen Smalley <stephen.smalley.work@xxxxxxxxx>
