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/20181031122718.18735-1-omosnace@xxxxxxxxxx/ [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(-) -- 2.17.2
