selinux.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Paul Moore <paul@paul-moore.com>
To: Linus Torvalds <torvalds@linux-foundation.org>
Cc: "Christian Göttsche" <cgzones@googlemail.com>,
	selinux@vger.kernel.org, linux-security-module@vger.kernel.org,
	linux-kernel@vger.kernel.org
Subject: Re: [GIT PULL] selinux/selinux-pr-20231030
Date: Tue, 31 Oct 2023 21:31:48 -0400	[thread overview]
Message-ID: <CAHC9VhQs9H-f8qZbwMgcF=LHEwspxvdJSNhhjwGu5K-ExYjPZw@mail.gmail.com> (raw)
In-Reply-To: <CAHk-=whOtZK1g_dzEnb5NEB8ssNqotmHy3CkUwbnab_4phFRdw@mail.gmail.com>

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 ;)

-- 
paul-moore.com

  reply	other threads:[~2023-11-01  1:32 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-10-31  2:16 [GIT PULL] selinux/selinux-pr-20231030 Paul Moore
2023-10-31  6:12 ` Linus Torvalds
2023-11-01  1:31   ` Paul Moore [this message]
2023-10-31  6:31 ` pr-tracker-bot

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAHC9VhQs9H-f8qZbwMgcF=LHEwspxvdJSNhhjwGu5K-ExYjPZw@mail.gmail.com' \
    --to=paul@paul-moore.com \
    --cc=cgzones@googlemail.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-security-module@vger.kernel.org \
    --cc=selinux@vger.kernel.org \
    --cc=torvalds@linux-foundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).