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>
next in thread | previous in thread | raw e-mail | index | archive | help
--0000000000000a106905fc3e124e Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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=E2=80=AFPM Hans Petter Selasky <hps@selask= y.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 modu= le > > > 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 ed= it > > > 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 separat= e > > > 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, de= vd > > > 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 so= rt > > in any meaningful way. And it's all about the runtime environment, whic= h > > 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... Ea= ch > > 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 syste= m > 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. > --0000000000000a106905fc3e124e Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"auto"><div><br><br><div class=3D"gmail_quote"><div dir=3D"ltr" = class=3D"gmail_attr">On Sun, May 21, 2023, 6:18 PM Konstantin Belousov <= <a href=3D"mailto:kostikbel@gmail.com" target=3D"_blank" rel=3D"noreferrer"= >kostikbel@gmail.com</a>> wrote:<br></div><blockquote class=3D"gmail_quo= te" style=3D"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=E2=80=AFPM Hans Petter Selasky <<a hre= f=3D"mailto:hps@selasky.org" rel=3D"noreferrer noreferrer" target=3D"_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 thei= r<br> > > subsystem/order/priority, all you need to do is to merge two sort= ed<br> > > lists into another sorted list, and this is pretty much linear.<b= r> > ><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<b= r> > without adding a lot of hair.<br> > <br> > <br> > > 1) "ld" can sort symbols by name, but encoding the prio= rity 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 yo= u edit<br> > > these lists and merge the constructors? What about destructors an= d<br> > > priority. Maybe possible.<br> > ><br> > > 3) The compiler can output strings to a magic file during compila= tion,<br> > > like the name of global variables to collect and sort. The C-comp= iler<br> > > has #error and #warning, but there is no #write_to_file, simply<b= r> > > speaking. Another solution is to store the file output into a sep= arate<br> > > section in the object files and use objcopy to extract the text l= ater<br> > > on, and process it.<br> > ><br> > <br> > These are all fragile. I don't think the benefit makes the fragili= ty<br> > worth it.<br> I agree.=C2=A0 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 devi= ce<br> > > being plugged, you need to search all products supported for a ma= tch.<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... E= ach<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 num= ber<br> of modules.=C2=A0 Can the merge be done in place without incurring n**2<br> behaviour?<br></blockquote></div></div><div dir=3D"auto"><br></div><div dir= =3D"auto">Yes. Today it's a simple linked list. Given each node has dif= ferent 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.=C2=A0</div><div = dir=3D"auto"><br></div><div dir=3D"auto">Warner</div><div dir=3D"auto"><br>= </div><div dir=3D"auto"><div class=3D"gmail_quote"><blockquote class=3D"gma= il_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-lef= t:1ex"> > this into devd, so the data persists in its most useful form for a lon= g<br> > time,<br> > and that's not a bad suggestion for dealing with the growing numbe= r of<br> > execs to make this all work... It's very Unix Tooly, but also ther= e's likely<br> > a good case to be made to optimize here... There's some ordering i= ssues<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.=C2=A0 In kernel, we are = not<br> limited by ABI or POSIX constraints.<br> </blockquote></div></div></div> --0000000000000a106905fc3e124e--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CANCZdfq3jsT%2BLz7AfVXvm51YckDLXurofSdt9MWNcu6rJkMSjg>