Date: Sun, 21 May 2023 21:19:53 -0400 From: Warner Losh <imp@bsdimp.com> To: Konstantin Belousov <kostikbel@gmail.com> Cc: Hans Petter Selasky <hps@selasky.org>, "freebsd-arch@freebsd.org" <freebsd-arch@freebsd.org> Subject: Re: [RFC] An idea for general kernel post-processing automation in FreeBSD Message-ID: <CANCZdfq3jsT%2BLz7AfVXvm51YckDLXurofSdt9MWNcu6rJkMSjg@mail.gmail.com> In-Reply-To: <ZGq03_RdpqXppA-h@kib.kiev.ua> References: <b0461320-fb92-95cf-609b-3550eb30a589@selasky.org> <CANCZdfowk1oQnw30hk%2BA-pSq0_QK52dahF6x3AUi=A76J18R9w@mail.gmail.com> <ZGq03_RdpqXppA-h@kib.kiev.ua>
index | next in thread | previous in thread | raw e-mail
[-- Attachment #1 --] 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. > [-- Attachment #2 --] <div dir="auto"><div><br><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, May 21, 2023, 6:18 PM Konstantin Belousov <<a href="mailto:kostikbel@gmail.com" target="_blank" rel="noreferrer">kostikbel@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Sun, May 21, 2023 at 05:34:26PM -0600, Warner Losh wrote:<br> > On Sun, May 21, 2023 at 2:13 PM Hans Petter Selasky <<a href="mailto:hps@selasky.org" rel="noreferrer noreferrer" target="_blank">hps@selasky.org</a>> wrote:<br> > <br> > > However, if the data in question is sorted at compile time, then zero<br> > > time will be spent sorting the data in the kernel. When a kernel module<br> > > is loaded and the sysinit/constructors are already sorted by their<br> > > subsystem/order/priority, all you need to do is to merge two sorted<br> > > lists into another sorted list, and this is pretty much linear.<br> > ><br> > > The question is, who can sort the sysinits:<br> > ><br> > <br> > The bigger question is "Do we even want to do that?"<br> > <br> > Switching to a faster sort gets us from milliseconds to microseconds<br> > without adding a lot of hair.<br> > <br> > <br> > > 1) "ld" can sort symbols by name, but encoding the priority into the<br> > > symbol name is difficult, especially when arithmetic expressions are<br> > > used. The C-pre-processor can only concat stuff. No, character<br> > > arithmetic is possible. This solution is not possible.<br> > ><br> > > 2) The constructor attribute in "C" can take a priority argument,<br> > > probably 32-bit and we need 64-bits. Sounds great, but how can you edit<br> > > these lists and merge the constructors? What about destructors and<br> > > priority. Maybe possible.<br> > ><br> > > 3) The compiler can output strings to a magic file during compilation,<br> > > like the name of global variables to collect and sort. The C-compiler<br> > > has #error and #warning, but there is no #write_to_file, simply<br> > > speaking. Another solution is to store the file output into a separate<br> > > section in the object files and use objcopy to extract the text later<br> > > on, and process it.<br> > ><br> > <br> > These are all fragile. I don't think the benefit makes the fragility<br> > worth it.<br> I agree. Linker tricks are cute but often depend on minor features of<br> linkers that break often.<br> <br> > <br> > > It may also be another way to fetch PCI/USB device ID information,<br> > > instead of using linker hints. Currently when probing USB devices, devd<br> > > has a linear list of hints it iterates. That means for every device<br> > > being plugged, you need to search all products supported for a match.<br> > > This is slow. Instead a tool could at least sort the entries, so a<br> > > binary search type function could be used, resulting in O(log2(N))<br> > > searching time, instead of O(N).<br> > ><br> > <br> > Except that data is pathologically heterogeneous. There's nothing to sort<br> > in any meaningful way. And it's all about the runtime environment, which<br> > is impossible to know at build time (today we do it at run time). The linker<br> > hints file to know which of many things to load is almost optimal... Each<br> > file is different, especially for PCI, which is why we pre-process it once<br> > and put it into the linker hints.... So it's pretty good once the system is<br> > running, but at startup we parse it multiple times and likely would do more<br> > as we move more towards MINIMAL. It's been suggested that we move<br> BTW, if we are moving to MINIMAL (which I quite like), then with the<br> proposed approach we need to merge at least N + 1 lists, where N is the number<br> of modules. Can the merge be done in place without incurring n**2<br> behaviour?<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto">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. </div><div dir="auto"><br></div><div dir="auto">Warner</div><div dir="auto"><br></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> > this into devd, so the data persists in its most useful form for a long<br> > time,<br> > and that's not a bad suggestion for dealing with the growing number of<br> > execs to make this all work... It's very Unix Tooly, but also there's likely<br> > a good case to be made to optimize here... There's some ordering issues<br> > that would need to be worked out too...<br> <br> Overall, my feel is the same: if better sort can be used to speed this up,<br> it is better to not create a monster build system. In kernel, we are not<br> limited by ABI or POSIX constraints.<br> </blockquote></div></div></div>help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CANCZdfq3jsT%2BLz7AfVXvm51YckDLXurofSdt9MWNcu6rJkMSjg>