linux-kernel - RE: Very slow clang kernel config ..

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Sat, 1 May 2021 21:58:55 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     'Linus Torvalds' <torvalds@...ux-foundation.org>,
        Tom Stellard <tstellar@...hat.com>
CC:     Nick Desaulniers <ndesaulniers@...gle.com>,
        Masahiro Yamada <masahiroy@...nel.org>,
        Nathan Chancellor <nathan@...nel.org>,
        "Linux Kernel Mailing List" <linux-kernel@...r.kernel.org>,
        clang-built-linux <clang-built-linux@...glegroups.com>,
        Fangrui Song <maskray@...gle.com>,
        Serge Guelton <sguelton@...hat.com>,
        Sylvestre Ledru <sylvestre@...illa.com>
Subject: RE: Very slow clang kernel config ..

From: Linus Torvalds
> Sent: 01 May 2021 17:32
> 
> On Fri, Apr 30, 2021 at 8:33 PM Tom Stellard <tstellar@...hat.com> wrote:
> >
> > Yes, it's intentional.  Dynamic linking libraries from other packages is
> > the Fedora policy[1], and clang and llvm are separate packages (in Fedora).
> 
> Side note: I really wish Fedora stopped doing that.
> 
> Shared libraries are not a good thing in general. They add a lot of
> overhead in this case, but more importantly they also add lots of
> unnecessary dependencies and complexity, and almost no shared
> libraries are actually version-safe, so it adds absolutely zero
> upside.

It's 'swings and roundabouts'...

I used a system where the libc.so the linker found was actually
an archive library, one member being libc.so.1.
The function that updated utmp and utmpx (last login details)
was in the archive part.
This code had incorrect locking and corrupted the files.
While the fix was easy, getting in 'installed' wasn't because all
the programs that used it needed to be relinked - hard when some
where provided as commercial binaries by 3rd parties.

I've also done some experiments with the mozilla web browser.
This loaded about 30 libraries at program startup.
The elf symbol hashing rules don't help at all!
Every symbol gets looked for in every library (often checking
for a non-weak symbol having found a weak definition).
So the hash of the symbol is calculated.
It is remaindered by the hash table size and the linked list scanned.
Now the hash table size is the prime below the power of 2 below
the number of symbols (well was when I did this).
So the average hash chain has about 1.5 entries.
With 30 libraries this is ~45 string compares.
If all the strings start with similar strings (C++classes)
then the strcmp() are quite long.

I played around with the hash table size.
It really didn't matter whether it was a prime or not.
For libc the distribution was always horrid - with some
quite long hash chains.
Making the hash table larger than the number of symbols
(perhaps 2 powers of 2 above) would be more likely to
make the hash hit an empty list - and skip all the strcmp().

The other 'trick' was a rewrite of the dynamic loader to
generate a single symbol table that contained all the symbols
of all the libraries loaded at program startup.
Process the libraries in the right order and this is easy.
That made a considerable improvement to program startup.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)