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

On Sun, May 21, 2023, 6:18 PM Konstantin Belousov <kostikbel@gmail.com>
wrote:

> 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?
>

Yes. Today it's a simple linked list. Given each node has different
matching, many of the classic methods of having a tree are tricky to apply.
And it's a bunch of integer compares... so I'm not sure it is worth doing
more than moving the matching into devd... fork/exec is way more expensive
as is the I/O to read the klds into memory.

Warner

> 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.
>