From nobody Wed May 24 15:20:02 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 4QRFHN1jL0z4Cq90 for ; Wed, 24 May 2023 15:20:16 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Received: from mail-wr1-f42.google.com (mail-wr1-f42.google.com [209.85.221.42]) (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 4QRFHM4HQnz3vmx for ; Wed, 24 May 2023 15:20:15 +0000 (UTC) (envelope-from jrtc27@jrtc27.com) Authentication-Results: mx1.freebsd.org; none Received: by mail-wr1-f42.google.com with SMTP id ffacd0b85a97d-309550d4f73so710304f8f.1 for ; Wed, 24 May 2023 08:20:15 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1684941614; x=1687533614; h=to:references:message-id:content-transfer-encoding:cc:date :in-reply-to:from:subject:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=xnDuZBORWC60m72U02OgsKTEn/r0p/P/cyGy360vspg=; b=Sisn9YOwoYT6bcgfEplsWZE7evnr0lGKPQPXRtTKYzeGGCzzuvwi7OTt561Dj1b5Hd hwblj/ad/kUyb7Xcn0mZny2dPL+Uy7tCB0fQf+L/bzvSPrqD8HxkiVzj+KQKgmxHOAe6 fR7z6a3vMYRDfI9u/D5GxBQr9BU/WpZmeOyGYleOWtC+zxFyPKit6TGBPBVcnc/Y/kcV bk/rmU6WyOWJBwnXxFIamz18wAK5pTrpYDhVaaYUXKmFl6HIqox/tJN+IVf29Znnf4we CZcUMjSCsqVeM2a4YEvp0dN4RJypXalfc9WPFiPgiwVT+tdvbOCrIVPom+9hLxy02ecL o6iQ== X-Gm-Message-State: AC+VfDxLj7Jb/2IhClN1MvXADz6jLzTZrSu0rC7thhw3P+DSZQSSwIxz Yx6/aH4l890rSwJt3UID8rMkwQ== X-Google-Smtp-Source: ACHHUZ7vegOBqNuRusVWwd24m14GciMpAojl/xf8ikyVosna6EXzzbEqWVOBU2RpIntY/LEuUtRdgg== X-Received: by 2002:a5d:424c:0:b0:30a:3ae0:f455 with SMTP id s12-20020a5d424c000000b0030a3ae0f455mr155859wrr.2.1684941613883; Wed, 24 May 2023 08:20:13 -0700 (PDT) Received: from smtpclient.apple ([131.111.5.246]) by smtp.gmail.com with ESMTPSA id l1-20020a05600012c100b0030630de6fbdsm14735270wrx.13.2023.05.24.08.20.13 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Wed, 24 May 2023 08:20:13 -0700 (PDT) Content-Type: text/plain; charset=utf-8 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 (Mac OS X Mail 16.0 \(3731.500.231\)) Subject: Re: [RFC] An idea for general kernel post-processing automation in FreeBSD From: Jessica Clarke In-Reply-To: <39e6793a-33f9-8f48-30d3-eaa30d321452@selasky.org> Date: Wed, 24 May 2023 16:20:02 +0100 Cc: Emmanuel Vadot , Kyle Evans , John Baldwin , Mark Johnston , Warner Losh , Konstantin Belousov , "freebsd-arch@freebsd.org" Content-Transfer-Encoding: quoted-printable Message-Id: <47B35276-B92A-49BC-A0FB-B71BA38ADA2A@freebsd.org> References: <394775eb-1000-60d9-2ddd-5c2aca6c99ea@selasky.org> <08ba506f-66c5-35eb-e992-ecf9dfeccf93@selasky.org> <20230524082850.ffc8793b6bb1b47325ae0139@bidouilliste.com> <39e6793a-33f9-8f48-30d3-eaa30d321452@selasky.org> To: Hans Petter Selasky X-Mailer: Apple Mail (2.3731.500.231) X-Rspamd-Queue-Id: 4QRFHM4HQnz3vmx X-Spamd-Bar: ---- X-Spamd-Result: default: False [-4.00 / 15.00]; REPLY(-4.00)[]; ASN(0.00)[asn:15169, ipnet:209.85.128.0/17, country:US] X-Rspamd-Pre-Result: action=no action; module=replies; Message is reply to one we originated X-ThisMailContainsUnwantedMimeParts: N On 24 May 2023, at 10:47, Hans Petter Selasky wrote: >=20 > On 5/24/23 08:28, Emmanuel Vadot wrote: >>>> +1. >=20 > Hi, >=20 >>>> Also, the concern over the runtime for the potential worst-case for = qsort >>>> seems_way_ overblown compared to the actual unsorted arrays one = will get >>>> out of the linker. The only possible downside of qsort that = matters in >>>> this case is the stack usage. > I think it is fair to say there are two levels of questions: >=20 > The first question is: > Runtime sorting vs Compile time sorting >=20 > The second question is: > Mathematically correct or System/Political correct sorting >=20 > Level 1: >=20 > 1.1) Runtime sorting puts the least requirements on the toolchain. = Data is concated in an unsorted binary object section. But in order to = read and debug this section, special tools are needed. >=20 > 1.2) Compiletime sorting puts more requirements on the toolchain. = Referring Jessica Clarke, this is a "gross hack". On the other hand, = debugging and visibility makes this desirable. I=E2=80=99ve been deliberately staying out of my thread, but this is = blatantly false. I said that in response to *one specific part of your = proposed implementation*, which is completely different to saying it = about the general concept. The full quote is: >> If you are worried multiple DEFINE_MUTEX(lock) will result in = multiple global symbols having the same "lock" name, all you need to do = is pass through the ${.TARGET} variable from "make" as a define, = stripping a few invalid characters, and macro-concat that to the locally = generated global variable name, and you are all good. >=20 > You could. But that=E2=80=99s a pretty gross hack IMO, and depending = on how you do it may still not be unique. Not to mention it=E2=80=99s = going to further bloat the symbol tables with these long names. So this is some pretty horrendous misquoting. Do not do that again. I am = extremely unimpressed. Jess > Level 2: >=20 > Should an appropriate sorting function be used or not? >=20 > Typically there are like 1K of entries to sort, but speaking about the = indexer, there are far less sorting keys for the 1K of entries. >=20 > 2.1) libkern's qsort() aka https://en.wikipedia.org/wiki/Quicksort >=20 > Using Quicksort is basically like first randomizing the data, and then = sorting it again. It is not optimal in any ways with regards to CPU = time. But system wise you could save code by using the same sorting = algorithm over and over again. >=20 > 2.2) mergesort() >=20 > Using mergesort() has a predictable executing time, bound to log2(N) * = N, where N is the number of elements to sort. The code in question = already allocates a new array to store the output of the sort, and a = kernel mergesort() routine could easily use the output array as = temporary storage. >=20 > 2.3) radixsort() >=20 > There are less 64-bit keys than sysinits, and I see a radix sort = algorithm would complete in less than log2(N) * N time. Radix sort is an = in-place sorting algorithm, and requires little code. It works similarly = to QuickSort, but doesn't go around a guess pivots. It already knows = them, because there is a sorting key. >=20 > 2.4) insertionsort() >=20 > When arrays are already sorted, the execution time is O(N), else = O(N=C2=B2) >=20 > 2.5) bubblesort() >=20 > Sorting time is more or less constant O(N=C2=B2). >=20 >=20 >=20 >=20 > In case compile time sorting is selected, there is no need for runtime = sorting. FreeBSD controls the build of all kernel modules, in-tree and = out-of-the tree. We go by source and not binaries, and that is our = strength. This can be an ABI contract thing for SYSINITs and kernel = modules. >=20 >=20 > In case runtime sorting is selected, I see a radix sorter as the less = CPU and stack intensive algorithm. This would be the mathematically = correct choice. qsort() as-of-today is the politically correct choice. = Less code, but more CPU and stack. >=20 >>>>=20 >>> IMO sorting at runtime is a minor feature by itself, too. I = mentioned >>> in one of the reviews somewhere, we have in the past have had bugs = due >>> to poor specification of sysinit order within a subsystem -- I'm >>> recalling a specific one that wasn't even that long ago, maybe three >>> or four years, that manu@ had hit because he did or didn't include >>> some device in his config that ended up shifting link order of other >>> objects and reversing two sysinits into an order that wasn't = actually >>> functional. >> Yes this problem was a pain to debug (I mean just to understand the >> actual problem), and iirc it was never solved, I only had the issue = on >> one machine that I don't use anymore and the problem went away and >> re-apears from time to time when sysinits where added. >>> We can still add some bits to test that (preferably a >>> tunable to reverse order within a subsystem rather than having to >>> re-link the kernel) even with sorting at link-time, but it sure does >>> look a lot less fragile if we have to sort it anyways and we just >>> reverse one criteria. >=20 > I think if you could just diff two plaintext files, listing all the = constructors in the correct order, that would be of great help when = problems arise in this area. You cannot always rely on having a console = during bringup. >=20 >=20 > At the mention of manu@, I remember how difficult it was to bringup = the graphics driver code and kernel modules which are common among = FreeBSD desktop users. What do you do, if all you have is a black = screen, and you need to debug something? >=20 >=20 >=20 > Does it make sense if I enumerate and collect the different views on = this issue on a WikiPage at FreeBSD.org, so it doesn't get lost for the = future? >=20 >=20 >=20 > --HPS