Date: Sun, 21 May 2023 22:13:20 +0200 From: Hans Petter Selasky <hps@selasky.org> To: "freebsd-arch@freebsd.org" <freebsd-arch@FreeBSD.org> Subject: [RFC] An idea for general kernel post-processing automation in FreeBSD Message-ID: <b0461320-fb92-95cf-609b-3550eb30a589@selasky.org>
next in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?b0461320-fb92-95cf-609b-3550eb30a589>