On Wed, Sep 6, 2023 at 11:46 AM 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 slot indexing into it rather than a pointer, then > this results in only 2 additional kvcalloc() calls and the complete > removal of the kmem_cache itself. > > The caching characteristics of iterating a single array are better due > to locality of reference. Running "perf stat -r 100 -d load_policy" > has shown a runtime reduction of at least 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. > > On 64-bit machines, the memory usage of the hash table slots is cut in > half due to the use of u32 indices instead of memory pointers. Since > ~65k hash slots are used between the regular and cond. tables with the > default Fedora 38 policy, this equates to around 256KB of memory saved. > > Notes: > > A couple helper functions avtab_get_chain() and avtab_get_node() are > introduced to provide more standardized interfaces for use in functions > that need to search through the hash table. > > NULL_NODE_IDX defines a sentinel value which helps determinine if a spot > in the hash table or the "next" member of an avtab_node are valid. > > This patch causes the cond. rules table to waste memory as the size > requested for the kvcalloc() is the size of the regular rules table. > These tables rarely, if ever, have the same number of rules in practice. > The next patch addresses this shortcoming. > > Signed-off-by: Jacob Satterfield <jsatterfield.linux@xxxxxxxxx> Reviewed-by: Stephen Smalley <stephen.smalley.work@xxxxxxxxx> > --- > security/selinux/ss/avtab.c | 75 +++++++++++++++---------------- > security/selinux/ss/avtab.h | 28 ++++++++++-- > security/selinux/ss/conditional.c | 13 +++--- > security/selinux/ss/services.c | 20 +++++---- > 4 files changed, 81 insertions(+), 55 deletions(-) >
