[RFC,0/3] Fix ENOMEM errors during policy reload

Message

Ondrej Mosnacek Nov. 13, 2018, 1:52 p.m. UTC

This patchset is an alternative, hopefully better (but also more risky),
solution of the ENOMEM problem ([1]) that I first tried to solve in [2].

In this version I encapsulate the initial SID table within sidtab and
also switch back from converting the sidtab in-place to converting into
a new sidtab and then just switching the pointer (keeping the code ready
for switching to RCU locks).

The change is split into three patches for easier review. Some changes
done in the first two patches are effectively undone by the last patch,
so it might actually make more sense to send the final version as one
squashed patch (please let me know which is better for you).

The first patch moves the sidtab conversion logic into sidtab.c. This
allows hiding sidtab_insert() from sidtab.h in the second patch, where
it becomes an internal function.

The second patch separates the handling of initial SIDs into a separate
lookup table inside sidtab. After this change, the main table always
contains N entries with keys from 0 to (N-1). This property is then
leveraged in the last patch.

Finally, the third patch rewrites the main sidtab to a more efficient
implementation that also gracefully handles context conversions during
policy reloads, which no longer produces the ENOMEM errors.

After applying this patchset, the time it takes to insert new sidtab
entries is drastically reduced. I measured the time to populate the
table with N new entries by repeatedly writing to
/sys/fs/selinux/context. A graph of the results is available at [3].

The SID -> context lookups are now also faster. With the old
implementation, these are O(N) once N goes above 128. The new
implementation can handle them theoretically in O(log N), but in
practice the slope is almost flat, so they are practically
almost constant-time.

Review and feedback welcome.

[1] https://github.com/SELinuxProject/selinux-kernel/issues/38
[2] https://lore.kernel.org/selinux/[e-mail]/
[3] https://docs.google.com/spreadsheets/d/e/2PACX-1vRUArNJR6kckm2SEs4dRZlijNVdCTmsNuWRGe7X3fC01YkBHpxXHnmcssxEiMF3Z7ivtXN2L5MC0ry-/pubhtml

Ondrej Mosnacek (3):
  selinux: refactor sidtab conversion
  selinux: use separate table for initial SID lookup
  selinux: overhaul sidtab to fix bug and improve performance

 security/selinux/ss/mls.c      |  23 +-
 security/selinux/ss/mls.h      |   3 +-
 security/selinux/ss/policydb.c |  10 +-
 security/selinux/ss/services.c | 188 +++++------
 security/selinux/ss/services.h |   2 +-
 security/selinux/ss/sidtab.c   | 550 ++++++++++++++++++++-------------
 security/selinux/ss/sidtab.h   |  90 ++++--
 7 files changed, 498 insertions(+), 368 deletions(-)