LWN: Comments on "Shrinking the kernel with link-time garbage collection"

Shrinking the kernel with link-time garbage collection

maskray — Mon, 01 Mar 2021 05:01:45 +0000

I managed to convince binutils that generic SHF_LINK_ORDER (not just arm) is useful, in particular, __patchable_function_entries needs it. H.J. Lu kindly implemented it and another nice syntax `,unique` in binutils 2.35.

SHF_LINK_ORDER unfortunately has some pitfalls. I have a summary in https://maskray.me/blog/2021-01-31-metadata-sections-comd...

The asteroid belt

fest3er — Sun, 07 Jan 2018 04:43:00 +0000

(I like to pick nits....)

I trust you meant Jupiter....

Shrinking the kernel with intelligent config

fest3er — Sun, 07 Jan 2018 04:39:10 +0000

Any reason the output of 'lshw' can't be twerked and combined with a file that lists 'hardware to be added' and 'features to be included' to provide input to a kernel configurator? You don't so much need to know how the hardware is laid out as you need to know which hardware is present. The configurator should then be able to enable just those bits of kit and features and dependencies....

Shrinking the kernel with intelligent config

Wol — Fri, 05 Jan 2018 12:01:01 +0000

I've got to have a running kernel first.

Plus I think there's other stuff wrong with it from my view.

Plus I think it defines things as modules, not loaded in.

Plus what happens if the plug-in hardware is still awaiting delivery.

Localmodconfig is a good idea, don't get me wrong. But it doesn't satisfy all use cases, and building a kernel specifically configured to a known hardware set is one of them.

(Don't forget I run gentoo :-) so building targeted kernels is normal. And I've been floating around the linux scene since kernel 1.3 ... :-)

Cheers,
Wol

Shrinking the kernel with intelligent config

HelloWorld — Fri, 05 Jan 2018 00:40:10 +0000

What's wrong with `make localmodconfig`?

Shrinking the kernel with intelligent config

gregkh — Thu, 04 Jan 2018 21:31:48 +0000

> From what I've picked up no-one's even considering this, but what I'd like to see is the kernel config system made much simpler.

This comes up all the time, everyone wants it done, no one has actually taken the time to do it :(

The asteroid belt

Wol — Thu, 04 Jan 2018 20:54:18 +0000

> The tiny computing space is just like an asteroid field; numerous projects exist, but they lack the required center of gravity for effective and self-sustained communities to form naturally around them. Consolidation efforts are moving slowly because of that. The end result is a highly fragmented space with relatively few developers per project and, therefore, fewer resources to rely upon when issues come up. Vulnerabilities are more likely to turn into a security nightmare.

Actually, as an astronomer, they DON'T lack the required centre of gravity (at least, that's not the main problem). The asteroid belt has insufficient distance between it and Mars and Saturn, so should a cluster of asteroids happen to form and start coalescing (as you'd expect), every time Saturn goes past the gravitational disruption pushes them apart again. They're literally torn apart by gravitational tides from nearby larger objects.

Which could also be a good analogy as to what happens to these small projects - the developers are heavily subjected to being lured away by larger projects in the same general eco-system.

Cheers,
Wol

Shrinking the kernel with intelligent config

Wol — Thu, 04 Jan 2018 20:42:26 +0000

From what I've picked up no-one's even considering this, but what I'd like to see is the kernel config system made much simpler.

It would be nice if there was a hardware section, so you could, say, select "AMD system". This would then ask you "which processor", "which chipset", "which motherboard" etc, and that will select the options to pull in all the drivers for that specific hardware.

If you've got fixed hardware, like a router for example, you would then be able to compile all the drivers into the kernel, plus maybe a load of modules for USB for stuff you want to support. It would be great for size reduction - and security - making it far easier to create targeted monolithic kernels with no extra stuff beyond what you need.

Cheers,
Wol

Shrinking the kernel with link-time garbage collection

smitty_one_each — Sat, 23 Dec 2017 00:18:05 +0000

Indeed, 692F will have you jamming to Talking Heads "Burning Down the House", albeit briefly.

Shrinking the kernel with link-time garbage collection

liw — Fri, 22 Dec 2017 18:37:59 +0000

During this time of the year, in the northern parts of the northern hemisphere, it is good to repeat that often: 640K ought to be enough for everyone. Any hotter and it'll get really uncomfortable.

Shrinking the kernel with link-time garbage collection

smitty_one_each — Fri, 22 Dec 2017 16:41:32 +0000

> "So what does "tiny" actually mean? Let's define it as a sub-megabyte system or thereabout. "

"See? See? I told you that nobody really *needed* more than 640K of memory," said Gill Bates.

Shrinking the kernel with link-time garbage collection

linusw — Fri, 22 Dec 2017 08:55:55 +0000

I just love this metaphor with the open source gravity field.

It comes close to describing how it actually works and correspond with the social law that people like to belong to something and to get recognition from their peers.

Shrinking the kernel with link-time garbage collection

flussence — Fri, 22 Dec 2017 00:20:43 +0000

Another thing came to mind re-reading this just now: routers. OpenWRT/LEDE has dropped or declined to support quite a few models as Linux has grown too big for them over the years, and the flash size is comparable to what you'd have available to install coreboot in.

Compile as one huge object

mwsealey — Mon, 18 Dec 2017 16:06:38 +0000

Multi-file compilation is a thing. You can actually use both together - the key aspect if LTO as per the article is putting each function and data item in it's own named section, because the linker can only act on individual sections as an unbreakable unit. Multi-file complication would still allow you to do this, but also provide greater inlining opportunities at the compiler level (for functional equivalence or tail-calling) which the linker has less information about.

It's probably best to leave the MFC part on a per module/subsystem basis (so, anything that gets a built-in.o) and then LTO both the main kernel binary and any modules. The difficulty is going to be making sure that public functions do not
get LTO'd away, while C99 inlining somewhat forces preservation of the 'original' function even if it inlines everything, LTO could strip it out if there's no out-of-line reference to it, and then your modules wouldn't load.

It's a pain in the backside, all told, but the results are always worth it.

Let's see some numbers!

npitre — Mon, 18 Dec 2017 16:03:42 +0000

Numbers will come in a subsequent article after more methods are exposed then compared.

Shrinking the kernel with link-time garbage collection

pabs — Sun, 17 Dec 2017 03:39:59 +0000

This work would probably be useful for Intel's KVM based Clear Containers, now renamed to Kata Containers:

https://katacontainers.io/

Let's see some numbers!

david.a.wheeler — Sun, 17 Dec 2017 02:03:28 +0000

I'd very much like to see before-and-after numbers. If the work reduces memory use by 10 bytes, it probably doesn't matter. I suspect that approaches are more effective when combined, but even so, I'd like to see if the effort appear to have the desired result.

Shrinking the kernel with link-time garbage collection

ThinkRob — Sun, 17 Dec 2017 01:45:31 +0000

One "mainstream" (aka not embedded) use might be those of us running coreboot. Some laptops have pretty limited flash, and there's not enough room for a Linux payload *and* another toy or two. So anything that might get the kernel down to the point where it all fits is nice.

That said, "mainstream" might be a stretch. I mean, there may be dozens of us. But still... "There are dozens of us! Dozens!" ;)

Compile as one huge object

gutschke — Sat, 16 Dec 2017 17:44:55 +0000

Compilers aren't optimized for this use case, and tend to run out of memory if you try to naively load everything into them at the same time. But even if that was taken care of, you are going to run into a lot of conflicts with incompatible reuse of symbols. You should try this one day on any project that is bigger than just a "toy" example. It usually turns out to be insanely painful.

You also lose out on a lot of the error messages that you would normally *want* to get, when there are layering violations and code reaches into private implementation details of other parts of the system. So, in practice, you'd have to maintain the code so that it can be compiled in the traditional fashion (that would happen during normal development cycles) and so that it can be compiled as one big file. That's very painful for the developers.

As far as I can tell, there are some compilers that internally do something similar to what you are suggesting. And with proper compiler support, it can of course be made to work. But honestly, from the developer's point of view, it ends up looking very similar to what is described in this article. And it would still need the same source-code annotations to help the compiler figure out which references are life and which ones aren't.

Compile as one huge object

pbonzini — Sat, 16 Dec 2017 17:40:48 +0000

That's exactly what link-time optimization does.

Compile as one huge object

mpr22 — Sat, 16 Dec 2017 16:16:23 +0000

Well, it would at least let you know whether your compiler's execution time is polynomial in the size of the translation unit.

Compile as one huge object

epa — Sat, 16 Dec 2017 12:59:15 +0000

I would have expected to skip the linking step altogether by concatenating all the source files into a big lump and then building that with optimization turned on. Some munging might be needed for symbols which are defined in multiple source files, but surely it's manageable.

Shrinking the kernel with link-time garbage collection

flussence — Sat, 16 Dec 2017 07:17:57 +0000

This is cool work! It'd be nice for us mainstream users as well as embedded; my vmlinuz images have almost doubled in size since I first put together this desktop…

Shrinking the kernel with link-time garbage collection

foom — Sat, 16 Dec 2017 04:09:23 +0000

This "missing forward reference" use case was recently discussed on the "generic-abi" email list. The conclusion was that the SHF_LINK_ORDER flag's semantics should be slightly extended to cover this. Unfortunately, it's not yet implemented in the GNU linker nor assembler. However, if you use recent clang and lld, you can see it in action today. (A patch was posted for gold, but doesn't seem to have been applied yet)

E.g. here's a slightly modified example from article. I've removed the ".reloc" hack, and modified the .section line, in red, to create a section marked with SHF_LINK_ORDER (that's the "o" in the "ao" flag):

In file test.s:

        .section .text.foobar,"ax"
.globl foobar
foobar:
        mov     r3, #0
        mov     r2, #0x5a
1:        strt    r2, [r0]
2:        mov     r0, r3
        bx      lr

        .section .fixup.text.foobar,"ax"
3:         mov     r3, #-57
        b       2b

        .section __ex_table.text.foobar, "ao", %progbits,.text.foobar
4:            .long   1b, 3b

In file test2.c:

int foobar();
int main() {
  foobar();
}

I run:

$ clang -target arm-linux-gnueabihf -c -o test.o test.s
$ clang -target arm-linux-gnueabihf -c -o test2.o test2.c
$ clang -target arm-linux-gnueabihf -o test test2.o test.o -Wl,--gc-sections -fuse-ld=lld

Doing an "objdump -x test", you will see that the "__ex_table.text.foobar" section made it into the output file. If you then comment out the call in main() to "foobar()", you'll see the __ex_table disappears too.

I'd recommend the kernel folks get the GNU tools to implement these semantics, so that weird no-op reloc tricks aren't needed.