performance optimization solution for semodule -i some.pp

[hurricane618]

In my process of using selinux, I found that when semodule -i some.pp loads a large number of modules with rules, the loading time increases rapidly.

(none) /tmp # time semodule -i 1.pp
real    0m 1.00s
user    0m 0.79s
sys 0m 0.09s
(none) /tmp # time semodule -i 2.pp
real    0m 1.99s
user    0m 1.75s
sys 0m 0.12s
(none) /tmp # time semodule -i 3.pp
real    0m 4.30s
user    0m 4.05s
sys 0m 0.13s
(none) /tmp # time semodule -i 4.pp
real    0m 7.75s
user    0m 7.49s
sys 0m 0.15s
(none) /tmp # time semodule -i 5.pp
real    0m 11.97s
user    0m 11.62s
sys 0m 0.20s

Then, I analyzed and found a function nodups_specs in libselinux/src/label_file.c. The algorithm complexity of implementing this function is O(N^2). In my use scenario, the N number would be over 20,000, so it would be performed hundreds of millions of times. It takes 12s to install the policy.

Therefore, I propose an optimization solution to this problem. The purpose of this function is to check for duplicates. The original function implementation is a double-layer loop to find duplicates. I'd like to propose a new implementation that uses hash tables to check for duplicates. The algorithm complexity of new implementing is O(N). The new solution is tested in my environment. The result is that the loading time is reduced to less than 1s.

What do you think of this solution? I want to submit my optimization implementation to the community.

[bachradsusi]

Hello, please send your idea and patch to the SELinux mailing list at selinux@vger.kernel.org. It is the main communication channel for this project, and it will reach a wider audience.

[bachradsusi]

Also please read https://github.com/SELinuxProject/selinux/blob/master/CONTRIBUTING.md to get some hints how to contribute code

[hurricane618]

Thanks a lot, I submit my patch to SELinux mailing list.

https://lore.kernel.org/selinux/20230209114253.120485-1-wanghuizhao1@huawei.com/T/#t