From nobody Sun May 21 23:34:26 2023 X-Original-To: freebsd-arch@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4QPcPC3vlBz4CctK for ; Sun, 21 May 2023 23:34:39 +0000 (UTC) (envelope-from wlosh@bsdimp.com) Received: from mail-ej1-x631.google.com (mail-ej1-x631.google.com [IPv6:2a00:1450:4864:20::631]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "smtp.gmail.com", Issuer "GTS CA 1D4" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4QPcPC2BNsz3Jk3 for ; Sun, 21 May 2023 23:34:39 +0000 (UTC) (envelope-from wlosh@bsdimp.com) Authentication-Results: mx1.freebsd.org; none Received: by mail-ej1-x631.google.com with SMTP id a640c23a62f3a-96f8d485ef3so271330266b.0 for ; Sun, 21 May 2023 16:34:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bsdimp-com.20221208.gappssmtp.com; s=20221208; t=1684712077; x=1687304077; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=WeWIRTfWZ57nrH5LPyWd1mWnDr255lp8XNBAyLk+J50=; b=RIzbq00nFdbo8w4uCOLJV/r/VVcPoNcZJMIC+NcI7EtJumd8SQYYthv/xSbpIJ1iMV pHjY8/GqL/Z+IUzMXWYzj1CpAHDeQ5CE4IhpKKAMFIBDVl36diile87X8wI6ZHrsr1VO 7iWz7Wg/q3V0Oyk/l6aC1t69GeZn641OgR7FN8sIC9qtFh9QZwoY+/gHElds5i6F7HjV guyO3f3elcFVpohPEOcbMFuUIzOWKe/td2CZddFeW+EMqNiGkEijUq2m9Vhtn/QGHeCR 1fBSicl57KYOyHeRNMmhMbbvNhXhFefKwJKjLdJ9CQME4c6xUy2hXovojZg50OXE0uP0 3eYQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684712078; x=1687304078; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=WeWIRTfWZ57nrH5LPyWd1mWnDr255lp8XNBAyLk+J50=; b=OJHygf920uFQHgc2m9sE1VvPk9G7rJVaSQGO/yJWiWi1zSoYyRXZDPocuKBmuwR6PK vvDlph6K5LxGxd/K7SqJN324W2N4fnMCkPKY9ZkSCS6xgO8/aS/6/TWGpmcUjKgPcXax GpM7Sd8I/JNTIRMb/vJBksxwvI02+6ZWwyrZ7Hq+IHGPQvsHh2dhb4WxpNIQfHCbZvUA wm1kQo2jwYsC9qi9RMse2fGcyCSuBknWu9+AeSfFAX+CpfIOkZuYMZPXade7pxxaJJg2 klFJdPVfiJSSq61I0GMVSXy1BdRAvPItSSsjtUhSCRms8pZobirQC91ftish/i5LmjhE bz9g== X-Gm-Message-State: AC+VfDwBO4OVbvC4AtZzxg01D2YbbVxktYQP0nmSXG6Q6hAm7nwh2auc ay9eDGZMuN9eJxTUsvCy0/DKHPKDdQ+lfFz1InCxYdI2a7vjqD12Gr8= X-Google-Smtp-Source: ACHHUZ76osqzzXC+j3Vln4LBbWPwe1dWBTqMSoXnJYQb6000pYgMWWQ9rFv1KKpmrweJmRgOiJ0nvm1xsC+XY14jxj4= X-Received: by 2002:a17:907:7285:b0:96f:1f69:279d with SMTP id dt5-20020a170907728500b0096f1f69279dmr8522362ejc.33.1684712077580; Sun, 21 May 2023 16:34:37 -0700 (PDT) List-Id: Discussion related to FreeBSD architecture List-Archive: https://lists.freebsd.org/archives/freebsd-arch List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-freebsd-arch@freebsd.org MIME-Version: 1.0 References: In-Reply-To: From: Warner Losh Date: Sun, 21 May 2023 17:34:26 -0600 Message-ID: Subject: Re: [RFC] An idea for general kernel post-processing automation in FreeBSD To: Hans Petter Selasky Cc: "freebsd-arch@freebsd.org" Content-Type: multipart/alternative; boundary="000000000000eeed4205fc3c984d" X-Rspamd-Queue-Id: 4QPcPC2BNsz3Jk3 X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:15169, ipnet:2a00:1450::/32, country:US] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N --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 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


=
On Sun, May 21, 2023 at 2:13=E2=80=AF= PM Hans Petter Selasky <hps@selasky.o= rg> 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 m= icroseconds
without adding a lot of hair.
=C2=A0
<= 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
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 fragi= le. I don't think the benefit makes the fragility
worth it.
=C2=A0
It m= ay 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 environmen= t, which
is impossible to know at build time (today we do it at r= un time). The linker
hints file to know which of many things to l= oad is almost optimal... Each
file is different, especially for P= CI, which is=C2=A0why we pre-process it once
and put it into the = linker hints.... So it's pretty good once the system is
runni= ng, 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 wit= h the growing number of
execs to make this all work... It's v= ery Unix Tooly, but also there's likely
a good case to be mad= e to optimize here... There's some ordering issues
that would= need to be worked out too...

Warner
--000000000000eeed4205fc3c984d--