| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <CAGudoHFcz1wQgQ53sy-HPJvJhx_DHhXcVVg3FfrFKHHdxt=scg@mail.gmail.com>
Date: Sat, 21 Oct 2023 14:13:52 +0200
From: Mateusz Guzik <mjguzik@...il.com>
To: Dave Chinner <david@...morbit.com>
Cc: Christian Brauner <brauner@...nel.org>,
Dave Chinner <dchinner@...hat.com>,
linux-kernel@...r.kernel.org, linux-fsdevel@...r.kernel.org,
linux-bcachefs@...r.kernel.org,
Kent Overstreet <kent.overstreet@...ux.dev>,
Alexander Viro <viro@...iv.linux.org.uk>
Subject: Re: (subset) [PATCH 22/32] vfs: inode cache conversion to hash-bl
It was bugging me that find_inode_fast is at the top of the profile
(modulo the locking routine).
Internals don't look too bad (it skips collisions without taking
locks), so I started wondering if hashing is any good.
I re-ran the scan of 20 mln and started counting visited inodes for
each call, got this:
[0, 1) 58266 | |
[1, 2) 385228 |@@@ |
[2, 3) 1252480 |@@@@@@@@@@ |
[3, 4) 2710082 |@@@@@@@@@@@@@@@@@@@@@@@ |
[4, 5) 4385945 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[5, 6) 5662628 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[6, 7) 6074390 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[7, 8) 5575381 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[8, 9) 4475706 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[9, 10) 3183676 |@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[10, 11) 2041743 |@@@@@@@@@@@@@@@@@ |
[11, 12) 1189850 |@@@@@@@@@@ |
[12, 13) 637683 |@@@@@ |
[13, 14) 313830 |@@ |
[14, 15) 143277 |@ |
[15, 16) 61501 | |
[16, 17) 25116 | |
[17, 18) 9693 | |
[18, 19) 3435 | |
[19, 20) 1120 | |
[20, 21) 385 | |
[21, 22) 99 | |
[22, 23) 45 | |
[23, 24) 15 | |
[24, 25) 2 | |
[25, 26) 2 | |
[26, 27) 2 | |
I compared this to literally just taking the ino & i_hash_mask as the
value, got this:
[0, 1) 119800 | |
[1, 2) 508063 |@@@ |
[2, 3) 1576390 |@@@@@@@@@@@ |
[3, 4) 2763163 |@@@@@@@@@@@@@@@@@@@ |
[4, 5) 3696348 |@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[5, 6) 5975274 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[6, 7) 7253615 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[7, 8) 6563736 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[8, 9) 5012728 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ |
[9, 10) 3495208 |@@@@@@@@@@@@@@@@@@@@@@@@@ |
[10, 11) 1606659 |@@@@@@@@@@@ |
[11, 12) 459458 |@@@ |
[12, 13) 3940 | |
[13, 14) 21 | |
[14, 15) 6 | |
[15, 16) 2 | |
That is to say distribution is much better, in particular the longest
streak is 15 (as opposed to 26).
While I'm not saying just taking ino is any good, I am saying there is
room for improvement here as far as one mount point is concerned.
Side note is that sb could have a randomly generated seed instead of
its address, which should help distributing this better.
So tl;dr hash distribution leaves some room for improvement and
*maybe* I'll prod it some time next month. One can also grow the table
of course, but that's for later.
--
Mateusz Guzik <mjguzik gmail.com>
Powered by blists - more mailing lists