Re: [PATCH 0000/2297] [ANNOUNCE, RFC] "Fast Kernel Headers" Tree -v1: Eliminate the Linux kernel's "Dependency Hell"
From: Ingo Molnar
Date: Tue Jan 04 2022 - 19:06:09 EST
* Arnd Bergmann <arnd@xxxxxxxx> wrote:
> From what I could tell, linux/sched.h was not the only such problem, but
> I saw similarly bad issues with linux/fs.h (which is what I posted about
> in November/December), linux/mm.h and linux/netdevice.h on the high
> level, in low-level headers there are huge issues with linux/atomic.h,
> linux/mutex.h, linux/pgtable.h etc. I expect that you have addressed
> these as well,
Correct, each of these was a problem - and a *lot* of other headers in
addition to those:
kepler:~/mingo.tip.git> git diff --stat v5.16-rc8.. include/linux/ arch/*/include/asm/ | grep changed
1335 files changed, 59677 insertions(+), 56582 deletions(-)
and I reduced all the kernels that showed up in the bloat-profile to a
fraction of their orignal size:
------------------------------------------------------------------------------------------
| Combined, preprocessed C code size of header, without line markers,
| with comments stripped:
------------------------------.-----------------------------.-----------------------------
| v5.16-rc7 | -fast-headers-v1
|-----------------------------|-----------------------------
#include <linux/sched.h> | LOC: 13,292 | headers: 324 | LOC: 769 | headers: 64
#include <linux/wait.h> | LOC: 9,369 | headers: 235 | LOC: 483 | headers: 46
#include <linux/rcupdate.h> | LOC: 8,975 | headers: 224 | LOC: 1,385 | headers: 86
#include <linux/hrtimer.h> | LOC: 10,861 | headers: 265 | LOC: 229 | headers: 37
#include <linux/fs.h> | LOC: 22,497 | headers: 427 | LOC: 1,993 | headers: 120
#include <linux/cred.h> | LOC: 17,257 | headers: 368 | LOC: 4,830 | headers: 129
#include <linux/dcache.h> | LOC: 10,545 | headers: 253 | LOC: 858 | headers: 65
#include <linux/cgroup.h> | LOC: 33,518 | headers: 522 | LOC: 2,477 | headers: 111
#include <linux/module.h> | LOC: 16,948 | headers: 339 | LOC: 2,239 | headers: 122
#include <linux/kobject.h> | LOC: 15,210 | headers: 318 | LOC: 799 | headers: 59
#include <linux/device.h> | LOC: 20,505 | headers: 408 | LOC: 2,131 | headers: 123
#include <linux/gfp.h> | LOC: 13,543 | headers: 303 | LOC: 181 | headers: 26
#include <linux/slab.h> | LOC: 14,037 | headers: 307 | LOC: 999 | headers: 74
#include <linux/mm.h> | LOC: 26,727 | headers: 453 | LOC: 1,855 | headers: 133
#include <linux/mmzone.h> | LOC: 12,755 | headers: 293 | LOC: 832 | headers: 64
#include <linux/swap.h> | LOC: 38,292 | headers: 559 | LOC: 11,085 | headers: 294
#include <linux/writeback.h> | LOC: 36,481 | headers: 550 | LOC: 1,566 | headers: 92
#include <linux/gfp.h> | LOC: 13,543 | headers: 303 | LOC: 181 | headers: 26
#include <linux/skbuff.h> | LOC: 36,130 | headers: 558 | LOC: 1,209 | headers: 89
#include <linux/tcp.h> | LOC: 60,133 | headers: 725 | LOC: 3,829 | headers: 153
#include <linux/udp.h> | LOC: 59,411 | headers: 721 | LOC: 3,236 | headers: 146
#include <linux/filter.h> | LOC: 54,172 | headers: 689 | LOC: 4,087 | headers: 73
#include <linux/interrupt.h> | LOC: 14,085 | headers: 340 | LOC: 2,629 | headers: 124
#include <net/sock.h> | LOC: 58,880 | headers: 715 | LOC: 1,543 | headers: 98
#include <asm/processor.h> | LOC: 7,821 | headers: 204 | LOC: 618 | headers: 41
#include <asm/page.h> | LOC: 1,540 | headers: 97 | LOC: 1,193 | headers: 82
#include <asm/pgtable.h> | LOC: 12,949 | headers: 297 | LOC: 5,742 | headers: 217
<linux/atomic.h> wasn't a particularly big problem - but it does get
included everywhere, so I moved the most common atomic_t definition into
<linux/types.h> (on 64-bit kernels), which allowed a big reduction for the
majority of cases that don't use the atomic APIs:
#include <linux/atomic.h> | LOC: 176 | headers: 26
#include <linux/atomic_api.h> | LOC: 2,785 | headers: 52
But <linux/atomic_api.h> is still included in ~75% of .c files, mostly for
good reasons, because it's a very popular low level API.
> but I'd like to make sure that your changes are reasonably complete on
> arm32 and arm64 to avoid having to do the big cleanup more than once.
I did test ARM64 extensively in terms of build coverage - but not in terms
of header bloat, and I'm sure more could be done there!
> My approach to the large mid-level headers is somewhat different: rather
> than completely avoiding them from getting included, I would like to
> split up the structure definitions from the inline functions.
That's a big chunk of what the -fast-headers tree does: I've split over 85
headers into <linux/header_types.h> and <linux/header_api.h>...
I've also split up headers further where needed, in particular mm.h
required multiple levels of splitting to get the dependencies of the most
commonly used <linux/mm_types.h> and <linux/mm_api.h> headers under
control:
kepler:~/mingo.tip.git> ls -ldt include/linux/mm*api*.h
-rw-rw-r-- 1 mingo mingo 77130 Jan 4 13:32 include/linux/mm_api.h
-rw-rw-r-- 1 mingo mingo 22227 Jan 4 13:32 include/linux/mmzone_api.h
-rw-rw-r-- 1 mingo mingo 6759 Jan 4 13:32 include/linux/mm_api_extra.h
-rw-rw-r-- 1 mingo mingo 479 Jan 4 13:31 include/linux/mm_api_exe_file.h
-rw-rw-r-- 1 mingo mingo 960 Jan 4 13:31 include/linux/mm_api_truncate.h
-rw-rw-r-- 1 mingo mingo 1262 Jan 4 13:31 include/linux/mm_api_kvmalloc.h
-rw-rw-r-- 1 mingo mingo 719 Jan 4 13:31 include/linux/mm_api_gate_area.h
-rw-rw-r-- 1 mingo mingo 1342 Jan 4 13:31 include/linux/mm_api_kasan.h
-rw-rw-r-- 1 mingo mingo 3007 Jan 4 13:31 include/linux/mm_api_tlb_flush.h
The results are pretty nice:
# vanilla:
#include <linux/mm.h> | LOC: 26,728 | headers: 453
# -fast-headers:
#include <linux/mm.h> | LOC: 1,855 | headers: 132 # == mm_types.h
#include <linux/mm_types.h> | LOC: 1,855 | headers: 131
#include <linux/mm_api.h> | LOC: 8,587 | headers: 229
And <linux/mm_api.h> is now included only in about 25% of the .c files - in
the vanilla kernel the use percentage is over ~90%.
But despite all those reductions, <linux/mm_api.h> is still a header with
one of the largest cumulative footprints within a (distro) kernel build:
| stripped lines of code
| _____________________________
| | headers included recursively
| | _______________________________
| | | usage in a distro kernel build
____________ | | | _________________________________________
| header name | | | | million lines of comment-stripped C code
| | | | |
#include <linux/spinlock_api.h> | LOC: 5,142 | headers: 123 | 10,168 | MLOC: 52.2 | #############
#include <linux/device/driver.h> | LOC: 4,132 | headers: 169 | 12,306 | MLOC: 50.8 | ############
#include <linux/mm_api.h> | LOC: 8,584 | headers: 230 | 5,135 | MLOC: 44.0 | ###########
#include <linux/skbuff_api.h> | LOC: 8,404 | headers: 190 | 5,065 | MLOC: 42.5 | ##########
#include <linux/atomic_api.h> | LOC: 2,785 | headers: 52 | 15,282 | MLOC: 42.5 | ##########
#include <asm/spinlock.h> | LOC: 4,039 | headers: 83 | 10,168 | MLOC: 41.0 | ##########
#include <asm/qrwlock.h> | LOC: 4,039 | headers: 82 | 10,168 | MLOC: 41.0 | ##########
#include <asm-generic/qrwlock.h> | LOC: 4,039 | headers: 81 | 10,168 | MLOC: 41.0 | ##########
#include <linux/page_ref.h> | LOC: 5,397 | headers: 168 | 7,578 | MLOC: 40.8 | ##########
#include <asm/qspinlock.h> | LOC: 3,990 | headers: 80 | 10,169 | MLOC: 40.5 | ##########
#include <linux/device_types.h> | LOC: 2,131 | headers: 122 | 17,424 | MLOC: 37.1 | #########
#include <linux/module.h> | LOC: 2,239 | headers: 122 | 16,472 | MLOC: 36.8 | #########
#include <net/cfg80211.h> | LOC: 29,004 | headers: 423 | 1,205 | MLOC: 34.9 | ########
#include <linux/pci.h> | LOC: 7,092 | headers: 232 | 4,849 | MLOC: 34.3 | ########
#include <linux/netdevice_api.h> | LOC: 8,434 | headers: 225 | 4,065 | MLOC: 34.2 | ########
#include <linux/refcount_api.h> | LOC: 3,421 | headers: 87 | 9,776 | MLOC: 33.4 | ########
( The 'MLOC' footprint estimate is number of usages times
preprocessed-stripped-header size. )
I've reduced header bloat through three primary angles of attack:
- reducing number of inclusions
- reducing header size itself, by type/API splitting & by segmenting
headers along API usage frequency
- decoupling headers from each other
As you can see, fast-headers -v1 is much improved (on x86), but there's
plenty of work left, such as <net/cfg80211.h>. :-)
> Linus didn't really like my approach,
Yeah, so without having a significant build time speedup I didn't like my
approach(es) either, which is why I didn't post this tree for a long time. :-)
But the results speak for themselves IMO, and we cannot ignore this: my
project actually accelerated as I progressed, because the kernel rebuilds,
especially incremental ones, became faster and faster...
Linux kernel header dependencies need to be simplified.
> but I suspect he'll have similar
> concerns about your solution for linux/sched.h, especially if we end up
> applying the same hack to other commonly used structures (sk_buff,
> mm_struct, super_block) in the end.
So the per_task approach is pretty much unavoidable under the constraint of
having no runtime overhead, given that task_struct is a historic union of a
zillion types, where 99% of the users don't actually need to know about
those types.
( We could eventually get rid of per_task() as well, by turning complex
embedded structs into pointers - but that has runtime overhead due to the
indirections, and I tried hard to make this approach runtime-invariant,
at least conceptually. )
The header splitting I've done is fundamentally clean (at least
aspirationally), mostly done along conceptual boundaries or API families.
It's how we'd have implemented many of those headers if we had a time
machine and went back 30 years. ;-)
> I should be able to come up with a less handwavy reply after I've
> actually studied your approach better.
Looking forward to it!
Thanks,
Ingo