[RFC] An idea for general kernel post-processing automation in FreeBSD

Hi,

I got to know Alexander Richardson was doing some profiling on kernel 
startup and basically found 1000 SYSINITs causes the CPU to spend 1000^2 
CPU instructions on sorting during startup, roughly speaking. This is 
noticable. The first proposal for speedup reduces the CPU overhead by 
50x. Due to the use of qsort() in the early kernel start phase, I was a 
bit skeptical, but Colin Percival pointed out that the stack depth of 
the kernel qsort() is of order log2(N). However there is still an issue 
about varying qsort() runtime.

https://reviews.freebsd.org/D39916

However, if the data in question is sorted at compile time, then zero 
time will be spent sorting the data in the kernel. When a kernel module 
is loaded and the sysinit/constructors are already sorted by their 
subsystem/order/priority, all you need to do is to merge two sorted 
lists into another sorted list, and this is pretty much linear.

The question is, who can sort the sysinits:

1) "ld" can sort symbols by name, but encoding the priority into the 
symbol name is difficult, especially when arithmetic expressions are 
used. The C-pre-processor can only concat stuff. No, character 
arithmetic is possible. This solution is not possible.

2) The constructor attribute in "C" can take a priority argument, 
probably 32-bit and we need 64-bits. Sounds great, but how can you edit 
these lists and merge the constructors? What about destructors and 
priority. Maybe possible.

3) The compiler can output strings to a magic file during compilation, 
like the name of global variables to collect and sort. The C-compiler 
has #error and #warning, but there is no #write_to_file, simply 
speaking. Another solution is to store the file output into a separate 
section in the object files and use objcopy to extract the text later 
on, and process it.

The advantage of passing commands from the build to a post-processing 
tool: There is only one configuration source, like 
sys/amd64/conf/GENERIC . Output into this "magic file" only happens if 
the code is actually compiled. If it is not compiled, then there is no 
output.

In the most simple case, all compiled sysinits can output a line of 
7-bit ASCII text into this "magic file", to tell some tool where these 
structures are and to sort them before linking.

This may be useful for embedded projects. Maybe you want to expose 
certain kernel functionality via a simple HTTP compatible service in the 
kernel? Then this "magic file" can be used to tell a post-processing 
tools about all the functionality present in the kernel. And based on 
this, generate appropriate HTML files, JSON parsing, JavaScript and so 
on, and bundle it into the kernel. Instead of registering commands on a 
linked list, use lex and yacc to build an efficient argument parser.

It may also be another way to fetch PCI/USB device ID information, 
instead of using linker hints. Currently when probing USB devices, devd 
has a linear list of hints it iterates. That means for every device 
being plugged, you need to search all products supported for a match. 
This is slow. Instead a tool could at least sort the entries, so a 
binary search type function could be used, resulting in O(log2(N)) 
searching time, instead of O(N).

I've put up a review for FreeBSD-14-main for discussion at:

https://reviews.freebsd.org/D40193

Depending patches are:

https://cgit.freebsd.org/src/commit/?id=805d759338a2be939fffc8bf3f25cfaab981a9be

https://reviews.freebsd.org/D40190
https://reviews.freebsd.org/D40191
https://reviews.freebsd.org/D40192

--HPS