Date: Sun, 21 May 2023 17:34:26 -0600 From: Warner Losh <imp@bsdimp.com> To: Hans Petter Selasky <hps@selasky.org> Cc: "freebsd-arch@freebsd.org" <freebsd-arch@freebsd.org> Subject: Re: [RFC] An idea for general kernel post-processing automation in FreeBSD Message-ID: <CANCZdfowk1oQnw30hk%2BA-pSq0_QK52dahF6x3AUi=A76J18R9w@mail.gmail.com> In-Reply-To: <b0461320-fb92-95cf-609b-3550eb30a589@selasky.org> References: <b0461320-fb92-95cf-609b-3550eb30a589@selasky.org>
next in thread | previous in thread | raw e-mail | index | archive | help
--000000000000eeed4205fc3c984d Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Sun, May 21, 2023 at 2:13=E2=80=AFPM Hans Petter Selasky <hps@selasky.or= g> 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. > 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 linke= r 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 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 likel= y a good case to be made to optimize here... There's some ordering issues that would need to be worked out too... Warner --000000000000eeed4205fc3c984d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div class=3D"gmail_quote">= <div dir=3D"ltr" class=3D"gmail_attr">On Sun, May 21, 2023 at 2:13=E2=80=AF= PM Hans Petter Selasky <<a href=3D"mailto:hps@selasky.org">hps@selasky.o= rg</a>> wrote:</div><blockquote class=3D"gmail_quote" style=3D"margin:0p= x 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> 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></blockquote><div><br></div>= <div>The bigger question is "Do we even want to do that?"</div><d= iv><br></div><div>Switching to a faster sort gets us from milliseconds to m= icroseconds</div><div>without adding a lot of hair.</div><div>=C2=A0</div><= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex"> 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></blockquote><div><br></div><div>These are all fragi= le. I don't think the benefit makes the fragility</div><div>worth it.</= div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px = 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">It m= ay 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></blockquote><div><br></div><div>Except= that data is pathologically heterogeneous. There's nothing to sort</di= v><div>in any meaningful way. And it's all about the runtime environmen= t, which</div><div>is impossible to know at build time (today we do it at r= un time). The linker</div><div>hints file to know which of many things to l= oad is almost optimal... Each</div><div>file is different, especially for P= CI, which is=C2=A0why we pre-process it once</div><div>and put it into the = linker hints.... So it's pretty good once the system is</div><div>runni= ng, but at startup we parse it multiple times and likely would do more</div= ><div>as we move more towards MINIMAL. It's been suggested that we move= </div><div>this into devd, so the data persists in its most useful form for= a long time,</div><div>and that's not a bad suggestion for dealing wit= h the growing number of</div><div>execs to make this all work... It's v= ery Unix Tooly, but also there's likely</div><div>a good case to be mad= e to optimize here... There's some ordering issues</div><div>that would= need to be worked out too...</div><div><br></div><div>Warner</div></div></= div> --000000000000eeed4205fc3c984d--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CANCZdfowk1oQnw30hk%2BA-pSq0_QK52dahF6x3AUi=A76J18R9w>