Date: Tue, 23 May 2023 00:54:12 +0200 From: Hans Petter Selasky <hps@selasky.org> To: Warner Losh <imp@bsdimp.com> Cc: Konstantin Belousov <kostikbel@gmail.com>, "freebsd-arch@freebsd.org" <freebsd-arch@freebsd.org> Subject: Re: [RFC] An idea for general kernel post-processing automation in FreeBSD Message-ID: <b6300144-41bb-53c9-b103-117547ff8a27@selasky.org> In-Reply-To: <CANCZdfq4D3N12c6h_Hy7Mvyg_d%2BpZBnN39CvpDU14-qDEhMFXQ@mail.gmail.com> References: <b0461320-fb92-95cf-609b-3550eb30a589@selasky.org> <CANCZdfowk1oQnw30hk%2BA-pSq0_QK52dahF6x3AUi=A76J18R9w@mail.gmail.com> <ZGq03_RdpqXppA-h@kib.kiev.ua> <394775eb-1000-60d9-2ddd-5c2aca6c99ea@selasky.org> <CANCZdfq4D3N12c6h_Hy7Mvyg_d%2BpZBnN39CvpDU14-qDEhMFXQ@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 5/22/23 16:28, Warner Losh wrote: > On Mon, May 22, 2023 at 3:56 AM Hans Petter Selasky <hps@selasky.org> wrote: > >> On 5/22/23 02:18, Konstantin Belousov 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?" >> >> Hi, >> >>>> Switching to a faster sort gets us from milliseconds to microseconds >>>> without adding a lot of hair. >> >> When you can more than double the benefit by simple means, why not just >> do that? >> > > Cost benefit ratio is terrible: Remove a millisecond at boot in exchange > for a less robust build and population of sysinit is a poor trade. Hi Warner, The biggest cost may be the human factor, taking the time to do a review. >> I know embedded CPUs run at kHz speeds when booting up, and only later >> on when clocks and such are properly setup, you get the GHz speeds. >> > > None of the tier-1 platforms do this, and we shouldn't drive optimizations > for fringe, tier-2 environments (including FIRECRACKER) when they come > with a real cost. Presorting is one that comes with a cost greater than > anything > else collin has done. My main objection to using qsort() in the startup area, is the algorithm is not constant time. It can be anything from fast to almost like bubble sort, still after recent changes. The stack usage seems under control. Given all sysinits use 64-bits of indexing, why not put a radix sorter inside there? It would match the performance of mergesort() and do the sorting in-place. Then the time variance wouldn't be that huge, and I would find that more acceptable than Quick Sort's way. > >> And Linux pre-sorts the initializers too, by a simple "level". It looks >> like they encode it into the symbol name itself. >> > > Interesting, but not relevant > > Honestly, I think we'd be better off with moving to a priority queue / heap > to get the order. We only need a partial ordering, and using a heap with > a priority queue has good worst / best case properties. It's what CAM uses > to pick the next work to do, though there'd be no reuse. Plus, it could > be done with pointers, which is way cheaper than copying entire entries > around. Pre-sorting would preclude doing things like this. This is not correct. Look at the code. > Basically, pre-sorting will make the build more complicated for what's, > at best, a marginal gain in an area that almost nobody cares about. The mechanism I propose can be used for more than pre-sorting symbols, likely weighing the cost. >>>>> 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. >> >> Yes, the linker supported sorting tricks are fragile. My proposal is to >> use the already existing named sections for this. This is supported all >> over the place, gcc, clang and so on. >> > > As someone who has fought with those schemes, I'd like to register > my strong opposition to expanding them unless we get a large benefit. > No such benefit has been articulated, so I'd say they are a non-starter. The benefit is larger. Many things end up in various named sections. And making a single section for all the tiny bits we need, would perhaps make life simpler in the end. One named section instead of many named sections. >>>>> 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). >>>>> > I still don't like any of this. I think it's extra complication looking for > a > problem to solve... I'm not a fan. OK --HPS
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?b6300144-41bb-53c9-b103-117547ff8a27>