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

On Sun, May 21, 2023 at 05:34:26PM -0600, Warner Losh wrote:
> On Sun, May 21, 2023 at 2:13 PM Hans Petter Selasky <hps@selasky.org> wrote:
> 
> > 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:
> >
> 
> The bigger question is "Do we even want to do that?"
> 
> Switching to a faster sort gets us from milliseconds to microseconds
> without adding a lot of hair.
> 
> 
> > 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.
> >
> 
> These are all fragile. I don't think the benefit makes the fragility
> worth it.
I agree.  Linker tricks are cute but often depend on minor features of
linkers that break often.

> 
> > 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).
> >
> 
> Except that data is pathologically heterogeneous. There's nothing to sort
> in any meaningful way. And it's all about the runtime environment, which
> is impossible to know at build time (today we do it at run time). The linker
> hints file to know which of many things to load is almost optimal... Each
> file is different, especially for PCI, which is why we pre-process it once
> and put it into the linker hints.... So it's pretty good once the system is
> running, but at startup we parse it multiple times and likely would do more
> as we move more towards MINIMAL. It's been suggested that we move
BTW, if we are moving to MINIMAL (which I quite like), then with the
proposed approach we need to merge at least N + 1 lists, where N is the number
of modules.  Can the merge be done in place without incurring n**2
behaviour?

> this into devd, so the data persists in its most useful form for a long
> time,
> and that's not a bad suggestion for dealing with the growing number of
> execs to make this all work... It's very Unix Tooly, but also there's likely
> a good case to be made to optimize here... There's some ordering issues
> that would need to be worked out too...

Overall, my feel is the same: if better sort can be used to speed this up,
it is better to not create a monster build system.  In kernel, we are not
limited by ABI or POSIX constraints.