| Message ID | 78932582fa556fd5fd6e8886e80e993f.paul@paul-moore.com (mailing list archive) |
|---|---|
| State | Accepted |
| Delegated to: | Paul Moore |
| Headers | show |
| Series | [GIT,PULL] selinux/selinux-pr-20231030 | expand |
On Mon, 30 Oct 2023 at 16:16, Paul Moore <paul@paul-moore.com> wrote: > > * Use a better hashing function for the SELinux role tansition hash > table. Bah. While the old hash function was garbage, the new one is quite expensive. Maybe it's worth it. But generally, if you find that "oh, just doing a modulus with a power of two drops all high bits", the first thing to try is probably to just do "hash_long(x, N)" to get N bits instead. Assuming the input is somewhat ok in one word, it does a fairly good job of mixing the bits with a simple multiply-and-shift. Yes, yes, jhash is a fine hash, but it does a quite *lot* of (simple) ALU ops. While "hash_long()" is often small enough to be inlined. I also note that filenametr_hash() does the old "one byte at a time" hash and partial_name_hash(). Is there any reason that code doesn't use the "full_name_hash()" which does things a word at a time? Probably doesn't matter, but since I looked at this to see what the new hashing was, I noticed... Linus
The pull request you sent on Mon, 30 Oct 2023 22:16:31 -0400:
> https://git.kernel.org/pub/scm/linux/kernel/git/pcmoore/selinux.git tags/selinux-pr-20231030
has been merged into torvalds/linux.git:
https://git.kernel.org/torvalds/c/f5fc9e4a117d4c118c95abb37e9d34d52b748c99
Thank you!
On Tue, Oct 31, 2023 at 2:13 AM Linus Torvalds <torvalds@linux-foundation.org> wrote: > On Mon, 30 Oct 2023 at 16:16, Paul Moore <paul@paul-moore.com> wrote: > > > > * Use a better hashing function for the SELinux role tansition hash > > table. > > Bah. > > While the old hash function was garbage, the new one is quite expensive. > > Maybe it's worth it. > > But generally, if you find that "oh, just doing a modulus with a power > of two drops all high bits", the first thing to try is probably to > just do "hash_long(x, N)" to get N bits instead. > > Assuming the input is somewhat ok in one word, it does a fairly good > job of mixing the bits with a simple multiply-and-shift. > > Yes, yes, jhash is a fine hash, but it does a quite *lot* of (simple) > ALU ops. While "hash_long()" is often small enough to be inlined. We probably should do some performance measurements of the various hash tables in the SELinux code and use that to drive some decisions on what functions we use. There have been some in the past for specific tables, but I don't think we've done anything comprehensive, or recent. This latest change obviously focused more on ensuring a better distribution, which can help, but if the digest calculation is too slow it probably doesn't matter. > I also note that filenametr_hash() does the old "one byte at a time" > hash and partial_name_hash(). Is there any reason that code doesn't > use the "full_name_hash()" which does things a word at a time? Likely just a matter of no one looking at it and realizing it can be improved. I'll toss this on the todo list, it should take all of five minutes. > Probably doesn't matter, but since I looked at this to see what the > new hashing was, I noticed... No harm in mentioning it, feedback is always welcome, but you know what else is even more welcome? Patches ;)
Hi Linus, Seven SELinux patches for v6.7, the highlights are below: * Improve the SELinux debugging configuration controls in Kconfig. * Print additional information about the hash table chain lengths when when printing SELinux debugging information. * Simplify the SELinux access vector hash table calcaulations. * Use a better hashing function for the SELinux role tansition hash table. * Improve SELinux load policy time through the use of optimized functions for calculating the number of bits set in a field. * Addition of a __counted_by annotation. * Simplify the avtab_inert_node() function through a simplified prototype. Please merge for v6.7-rc1, thanks. -Paul -- The following changes since commit 0bb80ecc33a8fb5a682236443c1e740d5c917d1d: Linux 6.6-rc1 (2023-09-10 16:28:41 -0700) are available in the Git repository at: https://git.kernel.org/pub/scm/linux/kernel/git/pcmoore/selinux.git tags/selinux-pr-20231030 for you to fetch changes up to 19c1c9916dbf9b05157a0c4970f61f952c0cb86a: selinux: simplify avtab_insert_node() prototype (2023-10-03 17:07:07 -0400) ---------------------------------------------------------------- selinux/stable-6.7 PR 20231030 ---------------------------------------------------------------- Christian Göttsche (4): selinux: print sum of chain lengths^2 for hash tables selinux: improve debug configuration selinux: simplify avtab slot calculation selinux: improve role transition hashing Jacob Satterfield (2): selinux: hweight optimization in avtab_read_item selinux: simplify avtab_insert_node() prototype Kees Cook (1): selinux: Annotate struct sidtab_str_cache with __counted_by security/selinux/Kconfig | 10 ++++++++++ security/selinux/Makefile | 2 ++ security/selinux/ss/avtab.c | 37 +++++++++++-------------------------- security/selinux/ss/hashtab.c | 5 +++++ security/selinux/ss/hashtab.h | 1 + security/selinux/ss/policydb.c | 6 +++--- security/selinux/ss/sidtab.c | 2 +- 7 files changed, 33 insertions(+), 30 deletions(-) -- paul-moore.com