“Fast Kernel Headers” Tree -v1: Eliminate the Linux Kernel's “Dependency Hell”

[RustyRussell]

Ingo Molnar was always one of my favourite scary kernel devs. This kind of massive rewrite was always a key strength of OG devs, who were prepared to tackle maintenance tasks beyond the limits of mortal sanity. The result of such ongoing struggles is why the Linux kernel still works after decades of active development, despite radical changing requirements.

[smcameron]

Says Rusty Russell, who's pretty goddam scary himself. :)

[yjftsjthsd-h]

A question that I've been mulling over: How do we create more people like this? Better documentation? A... "brief guide to the entire kernel" blog series? Aggressively pushing GSoC project mentoring?

[IshKebab]

To be fair nobody who wasn't in the inner circle would contemplate doing this amount of work when the likely outcome would be getting shut down by a Linus rant.

[dstroot]

"Don't forget that Linux became only possible because 20 years of OS research was carefully studied, analyzed, discussed and thrown away."

— Ingo Molnar

http://www.ussg.iu.edu/hypermail/linux/kernel/9906.0/0746.ht... to the Linux Kernel mailing list in 1999.

[numbsafari]

This is how I feel about the Go programming language.

So often you see people ranting about the Go team either being ignorant or scornful of PL research.

I always wonder if those same people are Agile Manifesto zealots at work.

[Quarrel]

Thanks for that.

What a great thread supporting the choices that Linus & the core team made at the time, given the hindsight we now have.

I'm not sure I would have agreed with Linus in '99 (and I was doing a Phd in the OS networking space then!).

Your bigger picture quote is great too. In academia it is easy to get yourself stuck in local minima, unable to see the better path beyond the hill of similar research surrounding you.

[inter_netuser]

link broken?

[fit2rule]

Hey now, the full quote is a little cheekier:

    > platitudes hardly provide compelling evidence for ignoring 20 years
    > of networking/OS research and architecting unnecessary copies into the.  
    > core of an OS that wants to be taken seriously...

    dont forget that Linux became only possible because 20 years of OS research was carefully studied, analyzed, discussed and thrown away.

    -- mingo<endquote>

.. don't you go ignoring the fact he was talking about zero-copy in the kernel!

[yrral]

Kudos to getting this out. I can't imagine working on a series of patches for 2 years for build cleanups/speedups on a separate branch, having to periodically rebase against master and throwing away my work 3 times in order to figure out how to do it correctly. At any company I have worked for, I would have been fired for being unproductive/afraid of making changes.

[binkHN]

This is one of the values of open source. Sometimes it's simply a labor of love. Since you're not "on the clock" to get the work done, you, sometimes, spend a little more time to improve the result, and the result reaches much farther than the for-profit company you work for.

[encryptluks2]

And this is the problem with many companies. They are more concerned about getting something done, even if it is broken or insecure, than doing something correctly. At least with open source, many people are passionate about it and an unemployed developer, student or other people can contribute openly.

[dv_dt]

Why not work on it and release in smaller batches though?

[srcreigh]

It's actually a little more than 1 year - late 2020 to present

[gitgud]

Here's the [1] patch cover letter sent to Linus Torvalds (similar to a Pull Request I suppose)

[1] https://lore.kernel.org/lkml/[email protected]/T/#u

[formerly_proven]

    From: Ingo Molnar
    Subject: [PATCH 0000/2297] Eliminate the Linux kernel's "Dependency Hell"
    
    ...
    25,288 files changed, 178,024 insertions(+), 74,720 deletions(-)

[kangalioo]

Where did the additional 100kLOC come from?

[charcircuit]

>2298 emails

When will Linux move to a site like github / gitlab / something similar self hosted that supports people proposing changes without having to send every single person interested in the development of Linux thousands of emails.

[londons_explore]

You have to have an awfully good reason to add 100k lines of code to a project... And I don't think merely shaving 50% off the build time is enough.

Think how many lines are now duplicate (and therefore need to be updated in twice as many places, and bugs introduced when a copy is missed).

Think how much extra stuff someone needs to skim through looking for the relevant file or part of the file.

If the 100k lines were in their own subdirectory and added a major new feature, it would be worth it. But spread across the whole codebase, and introducing more duplication and chances for bugs I think outweighs a 'neater' header file system.

The 'dependency hell' is only an issue for people who only want to build part of the kernel anyway. If you're building the whole lot, you might as well just include everything and it'll work great.

[commandlinefan]

> I got to over 500 commits in this tree and had to throw away my second attempt

But wait, why didn't you just break the task down into sub-tasks that could be estimated in four-hour increments in the first place? Every single "scrum master" I've ever labored under has insisted that every software development task can be broken down this way.

[Arch-TK]

Clearly Ingo is just an inexperienced developer who struggles to do this simple task. Maybe he needs more training?

[klysm]

I hadn’t thought about it, but this is a great counter example to the (bad) assumptions of scrum.

[bigdict]

Can't imagine the amount of whack-a-mole and backtracking involved in refactoring this many headers in a large project. I've done this for a small project and it's a migraine inducing type of work. Yet so valuable. Kudos!

[Gibbon1]

I have a firmware project written in C that I maintain. Probably 200k lines of code. I feel like I'm constantly fretting how to keep the headers and dependencies from becoming a hot mess. At the same time not exploding the number of headers either.

[rwmj]

He writes:

As to maintenance overhead: it was surprisingly low overhead to keep dependencies at a minimum across upstream kernel releases - there were typically just around ~5 dependency additions that need to be addressed. This makes me hopeful that an optimal 'fast' state of header dependencies can be maintained going forward - once the initial set of fixes are in of course.

It seems like this could regress quickly just by a developer adding a "bad" dependency to some core header which happened to #include a lot of code by accident. Don't we need tools to ensure this doesn't regress? Like something which warns "this git commit increases the amount of compiled code by 20%".

[phkahler]

Not sure, but isn't a large part of it keeping #include out of header files? That's easy to spot, but can be hard to untangle once its done.

[egberts]

I’ve embarked down this same path with GCC 2.7.4 from a … while … back.

Ingo is on the right track.

I’ve always thought that this stuff should have been dealt with by the GCC (in form of pre-cached header files).

So sad that it is a thorny issue to this day (for large scale projects); so glad that this issue is now alive so it can be dealt with once and for all.

I envision some type of *.ho filetype to hold these quasi-compiled headers for the next build iteration.

[da-x]

> For the 'reference' subsystem of the scheduler, I also improved build speed by consolidating .c files into roughly equal size build units. Instead of 20+ separate .o's, there's now just 4 .o's being built. Obviously this approach does not scale to the over 30,000 .c files in the kernel, but I wanted to demonstrate it because optimizing at that level brings the next level of build performance, and it might be feasible for a handful of other core kernel subsystems.

This is important, realizing that compilation units rarely collide on private namespace usage. Called 'compilation unit grouping', or 'CU grouping', I implemented this once at a customer's and reduced build time of a large C++ project by 2x.

[kzrdude]

Merging CU's should preferably be done by the build tool and not have to be written into the .c source files themselves.

[rep_movsd]

I remember doing this - one C file with about 100 lines from #include "file001.c" to #include "file299.c"

These were files from a library that used a large number of tiny files, we prefered to embed this in our project rather than link in.

Massive build time reduction.

There is some technical name for this other than "compilation unit grouping" - I forget what

[jcelerier]

If you use CMake it's just a matter of setting -DCMAKE_UNITY_BUILD=1

[cerved]

The hero we need but don't deserve

[stefan_]

This kids is exactly why nobody maintains out-of-tree kernel drivers.

[unmole]

Meh. There are loads of reasons why maintaining out of tree drivers is a bad idea. But this patch set is unlikly to cause any problems.

[phkahler]

>> This kids is exactly why nobody maintains out-of-tree kernel drivers.

After this it should be easier to maintain out of tree stuff since it eliminates "dependency hell".

[jonahbenton]

Very curious to see the reaction to this. Such a massive restructuring of the trees, header dependencies, and some of the machinery- these facts with which so many people are so familiar. There are few "who moved my cheese" events like moving code around.

For the other humans whose brains work on the kernel- the abrupt shock of moving to a vaguely familiar but in the end quite different house. Yes, the old one was suboptimal in various ways but this new one...

Few people's brains work like Ingo's. And he has had 2 years to work and iterate through the mental model. Field day here for the Science, Technology, and Society crowd, watching how old dogs deal with new tricks.

[bcwarner]

What's the process like for approving and implementing a series of patches this huge in quantity? Seems like it would almost require stalling on other pending issues for a significant amount of time while this is worked in.

[colonwqbang]

It can probably be merged piece by piece, so it won't be a problem.

The reason he wrote the full patch series out like this, is because he wanted to measure the speed gains. Without significant speed gains it would be difficult to convince the kernel developers to make a big uncomfortable change like this.

[taeric]

If it does as advertised, probably should not affect too much. Specifically, moving implicit dependencies to explicit should not impact anyone using the dependency. Might trip up code that is adding a new implicit?

[throwaway81523]

GCC needs something like that too. Building on a big multicore box turns out to not get that much parallelism, because of the dependency ordering.

[vrodic]

Sounds like headers in general are not necessarily a good idea.

They provide flexibility but at a cost.

I enjoyed Borland Pascal compilation speeds and clean dependencies before switching to Linux. I miss it, together with Delphi.

[rep_movsd]

C++ has been trying modules, and Gabriel Dos Reis from Microsoft has gotten a pretty decent standard and implementation done. It's likely it will be added to the C++23 standard. The biggest issue seems to be "What cross compiler format do we use for the compiled modules" (the equivalent of DCUs). The other problem is that macros have to still work, and code that uses them will not benefit as much from modules.

The gains in compilation speed (including linking) and dependency information tracking is phenomenal though. It would certainly bring C++ in line with languages like Java, Rust etc.

The CPPCon 2021 talk about this is enlightening.

If C++ gets modules, there is no reason why C can't use the same model - since the compilers will have that stuff anyway.

[gravypod]

Hopefully the Linux kernel will eventually get automated presubmits for IWYU and other things.

[astrostl]

I find it fascinating to consider the potential impact on energy consumption, human time, hardware and hosting costs, etc. of just one patch to just one thing.

[mtnygard]

I was wondering the same thing. Something like the Linux kernel gets built and rebuilt constantly by build systems and users all over the world. Even marginal improvements in build cost become big when there's such a large multiplier.

[remexre]

Does the kernel currently use precompiled headers? Anyone know how much they ought to help with this sorta scenario? (Like, presumably their gains would be lessened by this patchset, but could they have gotten halfway there on performance on their own?)

[egberts]

And Ingo probably had the greatest heads up over the rest of us by having his new kernel perform the fastest iterative kernel rebuilds, probably using all permutation of kernel option settings for rebuildings.