[v4,0/3] selinux: avtab arrays and refactors

Message

Jacob Satterfield Nov. 2, 2023, 3:45 p.m. UTC

As the refpolicy and the default Fedora policy continue to grow in
size, especially with regard to rules / access vectors, the memory
usage of the policydb and runtime to search through it increases.
Looking at /proc/slabinfo indicates that the avtab_node_cachep
kmem_cache is significantly responsible for overall memory usage and
was a good target for optimizations. Running "perf stat" on the
"load_policy" command shows that a majority of time is spent adding
rules into the avtab.

This patch series is an attempt at optimizing these hot spots within
the security server implementation to help it scale with additional
rules in the future.

Patch 1 refactors the internal avtab.c to remove duplicative code
and homogenize comparisons between data structures.

Patch 2 computes the number of conditional avtab rules instead of
using the regular avtab table size as a hint to avtab_alloc() to get
a properly sized hashtable. 

Patch 3 changes avtab to use arrays instead of a kmem_cache for the
individual nodes of the hashtable and depends on patch 3 due to the
pre-allocation of the array to prevent growing or shrinking it.

Changelog:

v4:
- selinux: avtab iteration macros
  - dropped from the patch series until the use-case for it becomes
    more apparent in future patches
- selinux: refactor avtab_node comparisons
  - unchanged
- selinux: fix conditional avtab slot hint
  - created from "use arrays for avtab hashtable nodes" patch
  - added comments in avtab.c explaining the use of the nrules param
- selinux: use arrays for avtab hashtable nodes
  - split independent code to "fix conditional avtab slot hint" patch
    to ease reviewing and allow independent merging
  - fixed an edge case exercised by this patch that causes a NULL
    deref in avtab_destroy(); discovered by clang-analyzer

v3:
- selinux: simplify avtab_insert_node() prototype
  - dropped, already merged
- selinux: avtab iteration macros
  - reverted changes to avtab_destroy() which created a UAF bug
- selinux: refactor avtab_node comparisons
  - fixed indent issues in avtab_node_cmp()
  - removed unlikely() macro in avtab_insert()

v2:
- selinux: use arrays for avtab hashtable nodes
  - rewritten to use pointers instead of indices
  - NULL_NODE_IDX and NODES_ARRAY_IDX macros removed
  - getter functions removed
  - two-pass algorithm used to compute cond. table size prior to
    allocating the array
- selinux: hweight optimization in avtab_read_item
  - dropped, already merged
- selinux: shrink conditional avtab node array
  - dropped, not needed due to new allocation approach
- selinux: refactor avtab_node comparisons
  - newly added
- selinux: avtab iteration macros
  - newly added
- selinux: simplify avtab_insert_node() prototype
  - newly added

Jacob Satterfield (4):
  selinux: refactor avtab_node comparisons
  selinux: avtab iteration macros
  selinux: fix conditional avtab slot hint
  selinux: use arrays for avtab hashtable nodes

 security/selinux/ss/avtab.c       | 179 ++++++++++++++----------------
 security/selinux/ss/avtab.h       |   4 +-
 security/selinux/ss/conditional.c |  38 ++++---
 security/selinux/ss/conditional.h |   2 +-
 4 files changed, 115 insertions(+), 108 deletions(-)