Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
On Thu, May 19, 2022 at 04:52:54PM -0400, Mathieu Desnoyers wrote: > - On May 19, 2022, at 2:36 PM, Daniel Kiper dki...@net-space.pl wrote: > > Did you consider Oskari's comment sent in the other email? > > I just did, sorry for the delay, I missed his email because it was only > sent to the list. My bad. That's on me for making assumptions on how people filter mailing lists from their inbox. Hopefully this one will arrive sooner ;) - Oskari signature.asc Description: PGP signature ___ Grub-devel mailing list Grub-devel@gnu.org https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH v2 3/5] cryptodisk: Add options to cryptomount to support keyfiles
On Thu, 19 May 2022 20:23:12 +0200
Daniel Kiper wrote:
> On Fri, May 13, 2022 at 12:00:49PM -0500, Glenn Washburn wrote:
> > From: John Lane
> >
> > Add the options --key-file, --keyfile-offset, and --keyfile-size to
> > cryptomount and code to put read the requested key file data and pass
> > via the cargs struct. Note, key file data is for all intents and purposes
> > equivalent to a password given to cryptomount. So there is no need to
> > enable support for key files in the various crypto backends (eg. LUKS1)
> > because the key data is passed just as if it were a password.
> >
> > Signed-off-by: John Lane
> > gnu...@cyberdimension.org: rebase, patch split, small fixes, commit message
> > Signed-off-by: Denis 'GNUtoo' Carikli
> > developm...@efficientek.com: rebase and rework to use cryptomount arg
> > passing,
> > minor fixes, improve commit message
> > Signed-off-by: Glenn Washburn
> > ---
> > grub-core/disk/cryptodisk.c | 104 +++-
> > include/grub/cryptodisk.h | 2 +
> > include/grub/file.h | 2 +
> > 3 files changed, 107 insertions(+), 1 deletion(-)
> >
> > diff --git a/grub-core/disk/cryptodisk.c b/grub-core/disk/cryptodisk.c
> > index 9f5dc7acb..94640b502 100644
> > --- a/grub-core/disk/cryptodisk.c
> > +++ b/grub-core/disk/cryptodisk.c
> > @@ -42,6 +42,9 @@ static const struct grub_arg_option options[] =
> > {"all", 'a', 0, N_("Mount all."), 0, 0},
> > {"boot", 'b', 0, N_("Mount all volumes with `boot' flag set."), 0, 0},
> > {"password", 'p', 0, N_("Password to open volumes."), 0,
> > ARG_TYPE_STRING},
> > +{"key-file", 'k', 0, N_("Key file"), 0, ARG_TYPE_STRING},
> > +{"keyfile-offset", 'O', 0, N_("Key file offset (bytes)"), 0,
> > ARG_TYPE_INT},
> > +{"keyfile-size", 'S', 0, N_("Key file data size (bytes)"), 0,
> > ARG_TYPE_INT},
> > {0, 0, 0, 0, 0, 0}
> >};
> >
> > @@ -1172,6 +1175,103 @@ grub_cmd_cryptomount (grub_extcmd_context_t ctxt,
> > int argc, char **args)
> >cargs.key_len = grub_strlen (state[3].arg);
> > }
> >
> > + if (state[4].set) /* keyfile */
> > +{
> > + char tmp_errmsg[GRUB_MAX_ERRMSG];
> > + const char *p = NULL;
> > + grub_file_t keyfile;
> > + unsigned long long keyfile_offset = 0, keyfile_size = 0;
> > +
> > + if (state[5].set) /* keyfile-offset */
> > + {
> > + grub_errno = GRUB_ERR_NONE;
> > + keyfile_offset = grub_strtoull (state[5].arg, , 0);
> > +
> > + if (state[5].arg[0] == '\0' || *p != '\0')
> > + {
> > + if (grub_errno != GRUB_ERR_NONE)
> > + {
> > + grub_strncpy (tmp_errmsg, grub_errmsg, GRUB_MAX_ERRMSG);
> > + return grub_error (grub_errno,
> > +N_("non-numeric or invalid keyfile offset
> > `%s': %s"),
> > +state[5].arg, tmp_errmsg);
> > + }
> > + else
> > + return grub_error (GRUB_ERR_BAD_ARGUMENT,
> > + N_("invalid keyfile offset `%s': non-numeric"
> > + " characters at end of number"),
> > + state[5].arg);
>
> I think this does not give us a lot of value. I would just do
>
>if (state[5].arg[0] == '\0' || *p != '\0')
> return grub_error (GRUB_ERR_BAD_NUMBER, ...
Even low value error information can be quite valuable to those that
need it. Despite that, I'll make the suggested change.
>
> > + }
> > + }
> > +
> > + if (state[6].set) /* keyfile-size */
> > + {
> > + grub_errno = GRUB_ERR_NONE;
> > + keyfile_size = grub_strtoull (state[6].arg, , 0);
> > +
> > + if (state[6].arg[0] == '\0' || *p != '\0')
> > + {
> > + if (grub_errno != GRUB_ERR_NONE)
> > + {
> > + grub_strncpy (tmp_errmsg, grub_errmsg, GRUB_MAX_ERRMSG);
> > + return grub_error (grub_errno,
> > +N_("non-numeric or invalid keyfile offset
> > `%s': %s"),
> > +state[5].arg, tmp_errmsg);
> > + }
> > + else
> > + return grub_error (GRUB_ERR_BAD_ARGUMENT,
> > + N_("invalid keyfile offset `%s': non-numeric"
> > + " characters at end of number"),
> > + state[6].arg);
>
> Ditto.
>
> > + }
> > +
> > + if (keyfile_size > GRUB_CRYPTODISK_MAX_KEYFILE_SIZE)
> > + return grub_error (GRUB_ERR_OUT_OF_RANGE,
> > + N_("key file size exceeds maximum (%d)"),
> > + GRUB_CRYPTODISK_MAX_KEYFILE_SIZE);
> > +
> > + if (keyfile_size == 0)
> > + return grub_error (GRUB_ERR_OUT_OF_RANGE, N_("key file size is 0"));
>
> Nit, I would move this before the "if (keyfile_size > ...". This would
> be more natural.
Sure thing.
Glenn
>
> Daniel
___
Grub-devel
Re: Linux DRTM on UEFI platforms
Hey Ard, Apologies for the lag in response, I wanted to have this to you sooner, but between a variety of events and working on building consensus on how to address your comments made it drag out a little. Before reading this message, I would recommend reading the proposal posted to the top of this thread, as it details an approach that builds on Matthew's callback proposal along with addressing your concerns with measurements. In this message, I want to provide you direct answers to the points you raised independent of the reply at the top of this thread to help map where your concerns influenced the proposal. On 3/31/22 03:13, Ard Biesheuvel wrote: > On Thu, 31 Mar 2022 at 02:36, Daniel P. Smith > wrote: >> >> Greetings Matthew, >> >> First thank you to you and James for taking time out of your busy >> schedules to sit down with us and work through all of this. >> >> Hey Ard, >> >> On 3/30/22 03:02, Ard Biesheuvel wrote:>> 1) From an EFI maintainer >> perspective, is making the contract between the boot stub and the kernel explicit viable? >>> >>> No. The direction of travel has been to define EFI boot only in terms >>> of the handover from the loader to the stub. What happens next is up >>> to the architecture, and is deliberately not specified, because it is >>> considered to be internal Linux ABI. We've deviated from this once for >>> Xen on ARM, but this means we have already painted ourselves into a >>> corner when it comes the way we use DT internally at the handover >>> point between stub and kernel proper, and I am not eager to repeat >>> that. Locking down the stub-to-kernel protocol for all architectures >>> is not the way to go. >> >> To help provide some visual context, for EFI today there is, >> >> bzImage >> [EFI boot manager] -> [[efi-stub] -> [setup kernel] -> [main kernel]] >> >> Where the efi-stub is responsible for interacting with firmware to >> configure the system, store that configuration for the setup kernel and >> the main kernel, and then call EBS before entering the setup kernel. >> >> For Secure Launch the flow (on Intel) is, >> >> CPU instruction bzImage >> [preamble] -> [ACM] -> [[sl-stub] -> [setup kernel] -> [main kernel]] >> >> In order to make the CPU instruction call to enter the ACM the system >> must be in a very specific quiescent state. This includes but not >> exhaustively, >> * EBS must have been called >> * TPM should have all localities closed >> * IOMMU PMRs must be programmed appropriately >> * TXT heap space allocated >> * TXT heap space populated with config structures >> * All APs must be in a specific idle state >> * Execution is on the BSP >> Carrying all this out is what is considered the DRTM preamble. >> > > Thanks for the explanation, this is really helpful. Your welcome. >> This is the wrinkle because the setup kernel and main kernel are both >> predicated on the efi-stub and the efi-stub is predicated on running >> before EBS. > > Matthew suggested this already, but can you explain why handling this > in a callback is not an option? I'd by sympathetic to specifying a > Linux specific protocol that can be grabbed before EBS() but can be > invoked after (but not, say after SetVirtualAddressMap(), to keep > things simple). That should allow us to call back into firmware to > perform the secure launch right before handing over. Apologies, I was not meaning to suggest this was not an option. As you can see in the proposal posted, this approach is in fact being embraced. It is not explicit stated in the proposal, but the approach for the Secure Launch spec is to not explicitly dictate the location of the DL Handler. If a firmware manufacturer wants to implement a Secure Launch compliant DL Handler in firmware, this certainly would be welcomed, but should not be a requirement to enable Secure Launch. For instance, in the prototype the DL Handler is actually implemented as a stub in the setup kernel as that is the direction we are moving towards but may not be how the final implementation works. > My other suggestion, to use a minimal EFI environment just to boot the > kernel, still seems viable to me as well, but it would boil down to > mostly the same, thing, i.e., to inject an intermediate boot stage > between the call to the firmware's EBS() and calling the entrypoint of > the kernel proper. What I do like about this approach is that the EFI > stub could execute unprivileged, which means the secure launch kernel > could track *exactly* what the EFI stub is doing in terms of memory > accesses and protocol invocations, which seems a bit more robust than > the approximation of 'this might be interesting enough to measure' > that the industry seems to have settled on. IMHO that is the beauty of the Secure Launch spec. Just as you suggest, your EFI environment shim could track what the EFI stub does and record it in the SLRT. In addition, your shim could also
Re: Linux DRTM on UEFI platforms
Greetings, Based on the discussions that occurred in this thread, there seems to be two issues at hand that should be decoupled, as their solutions can and should be implemented independently. These are: - the handling of the Dynamic Launch preamble - providing the complete kernel configuration for measurement For the former, it is believed there is a consensus that Matthew's proposed callback approach would be the preferred method. Through some contemplating and prototyping, the determination is that this will in fact be an approach that will ultimately benefit the TrenchBoot project itself. In general, the preamble consists of two activities: 1. preparing the contents in memory and 2. preparing the hardware in order to call the Dynamic Launch instruction. In past implementations, these two activities were conducted sequentially, but in reality the time delta between the two may be arbitrary. Introducing this separation does not introduce any security concerns due to how the Dynamic Launch works. Any tampering of the contents in memory will either cause the Dynamic Launch to fail or result in a detectable difference in the Dynamic Launch measurement chain. In order to separate the hardware interactions into what will be called the DLE Handler, this will require a collection of information regarding how the environment is set up. When working through what would be required, this led to the realization that this really should be generalized into a formal specification for TrenchBoot's Secure Launch. This will enable a reusable solution for the TrenchBoot project, versus implementing a one-off solution for Linux. A prototype of is near completion, for which below is a visual depiction along with a step-by-step walk through of how it would work for efi-stub. Secure Launch Flow: +-+ | | +-->| Secure Launch +---+ | | Resource Table | | | | |+--|---+ | +++| | DLME | || | v | || | +---+| +-+-+ v | | || +--+-+ | +-+ | | Secure Launch || || +-->| +--->| Entry || | Bootloader(s) | | | DLE Handler | | | || |+-+ | | | +---+| ++ +-+ +--+ A quick note on the flow diagram, for simplicity all entities prior to the DLE Handler are represented by the "Bootloader(s)" block due to the fact that what entities are involved can and will vary. This is where both GRUB and efi-stub are being represented even though for Linux EFI, GRUB is considered the bootmanager while efi-stub is the bootloader. An efi-stub walk-thru: 1. - GRUB 1.1 - GRUB will initialize the Secure Launch Resource Table (SLRT) 1.2 - GRUB will set up DLE Handler and register it in SLRT 1.5 - GRUB will load Linux kernel 1.3 - GRUB will set up DL environment appropriately for HW platform 1.4 - GRUB will record DL setup in SLRT 1.5 - GRUB will record SLRT location in platform's DL config structure 1.5 - GRUB will register SLRT in EFI configuration table under SL GUID 1.6 - GRUB will invoke efi-stub 2. - efi-stub 2.1 - efi-stub will check if SL GUID is in EFI configuration table 2.2 - for each efi-stub config action, an SLRT EFI config event will be recorded 2.3 - efi-stub calls EBS() then jumps to DLE Handler registered in SLRT while passing the SLRT address 3. - DL Handler 3.1 - DL Handler will retrieve SL Entry from SLRT 3.2 - DL Handler will prepare HW for calling DL CPU instruction 3.3 - DL Handler will execute DL CPU instruction 4. SL Entry 4.1 SL Entry will retrieve SLRT address from platform's DL config struct 4.2 SL Entry will use policy in SLRT to determine what to measure 4.3 SL Entry will set up HW to what Linux expects 4.4 SL Entry will jump into Linux setup kernel 4.5 SL Entry will record measurements into TPM prior to init process starting While Matthew's original proposal was around having a location in the efi-stub for the callback to be registered, it is felt that it would be better suited as part of the Secure Launch specification. What is proposed is for the address of the DL Handler to be stored in the SLRT, details for the SLRT are below. Then the bootloader that is responsible for loading the DL Handler will register the SLRT in the EFI configuration table. Checking for the SLRT GUID in the EFI configuration table will enable the EFI bootoader responsible for calling EBS, in this case efi-stub, to know that a Dynamic Launch has been
Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
- On May 19, 2022, at 2:36 PM, Daniel Kiper dki...@net-space.pl wrote:
[...]
>
> Could you do the same in util/grub.d/20_linux_xen.in? Both should be
> kept in sync. And you are not first one who updates 10_linux.in only.
> If you could make a patch which adds something like "Keep logic in sync
> with..." to the util/grub.d/10_linux.in and util/grub.d/20_linux_xen.in
> that would be perfect.
AFAIU, 20_linux_xen.in does:
while [ "x${xen_list}" != "x" ] ; do
list="${linux_list}"
current_xen=`version_find_latest $xen_list`
[]
while [ "x$list" != "x" ] ; do
linux=`version_find_latest $list`
[...]
list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
done
if [ x"$is_top_level" != xtrue ]; then
echo ' }'
fi
xen_list=`echo $xen_list | tr ' ' '\n' | fgrep -vx "$current_xen" | tr '\n'
' '`
done
Which adds yet another loop iterating on each item of "xen_list". For each of
those,
there is an iteration on "linux_list".
I can do the change, like I can do the change for other OSes, but I don't have
the environment to test those changes. Would you be OK if I submit an untested
patch for someone else to try out ?
I notice that 10_hurd.in and 10_kfreebsd.in also have the exact same
inefficient pattern.
Would you be OK if I also change them and let the change be tested by those who
have
those environments ?
>
> Did you consider Oskari's comment sent in the other email?
I just did, sorry for the delay, I missed his email because it was only
sent to the list.
Thanks,
Mathieu
>
> Daniel
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
___
Grub-devel mailing list
Grub-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH v2 4/5] cryptodisk: Use enum constants as indexes into cryptomount option array
On Thu, 19 May 2022 20:24:11 +0200
Daniel Kiper wrote:
> On Fri, May 13, 2022 at 12:00:50PM -0500, Glenn Washburn wrote:
> > Signed-off-by: Glenn Washburn
> > ---
> > grub-core/disk/cryptodisk.c | 53 ++---
> > 1 file changed, 32 insertions(+), 21 deletions(-)
> >
> > diff --git a/grub-core/disk/cryptodisk.c b/grub-core/disk/cryptodisk.c
> > index 94640b502..ecbda7ce9 100644
> > --- a/grub-core/disk/cryptodisk.c
> > +++ b/grub-core/disk/cryptodisk.c
> > @@ -35,6 +35,17 @@ GRUB_MOD_LICENSE ("GPLv3+");
> >
> > grub_cryptodisk_dev_t grub_cryptodisk_list;
> >
> > +enum
> > + {
> > +OPTION_UUID,
> > +OPTION_ALL,
> > +OPTION_BOOT,
> > +OPTION_PASSWORD,
> > +OPTION_KEYFILE,
> > +OPTION_KEYFILE_OFFSET,
> > +OPTION_KEYFILE_SIZE
> > + };
>
> I would prefer constants here.
I chose enum because that is consistent with many other commands. By
"constants" do you mean CPP defined macros? I can imagine you would
mean variables with the "const" property. Without having done an
exhaustive search, I don't believe any commands use CPP macros for the
index. Here's a list of files for commands that use enums as the index:
grub-core/commands/i386/pc/drivemap.c
grub-core/commands/file.c
grub-core/commands/pgp.c
grub-core/commands/search_wrap.c
grub-core/term/gfxterm_background.c
grub-core/term/serial.c
grub-core/term/terminfo.c
The benefits of enum over CPP macro is that inserting into the enum
list automatically renumbers the subsequent constants in the list. I
failing to think of a good way to do that with CPP macros. Could you
explain a little further precisely what you're wanting (maybe I've
guessed wrong) and why you see it as superior to using enums?
Glenn
>
> Otherwise patches LGTM.
>
> Daniel
___
Grub-devel mailing list
Grub-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
- On May 5, 2022, at 7:02 PM, Oskari Pirhonen xxc3ncore...@gmail.com wrote:
> On Thu, May 05, 2022 at 10:24:56AM -0400, Mathieu Desnoyers wrote:
[...]
>
> Instead of creating a separate function, would it be better to let
> `version_sort()` accept an argument/set of arguments?
>
>> +
>> version_test_numeric ()
>> {
>>version_test_numeric_a="$1"
>> diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in
>> index ca068038e..8178318f5 100644
>> --- a/util/grub.d/10_linux.in
>> +++ b/util/grub.d/10_linux.in
>> @@ -195,9 +195,15 @@ title_correction_code=
>> # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
>> submenu_indentation=""
>>
>> +# Perform a reverse version sort on the entire list.
>> +# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all
>> +# other files to order the '.old' files after their non-old counterpart
>> +# in reverse-sorted order.
>> +
>> +reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/
>> 1$/! s/$/ 2/' | version_reverse_sort | sed -e 's/ 1$/.old/' -e 's/ 2$//')
>
> That way you could do something like this instead:
>
>... | version_sort -r | ...
>
> - Oskari
>
Done (for next version of patch),
Thanks!
Mathieu
>> +
>> is_top_level=true
>> -while [ "x$list" != "x" ] ; do
>> - linux=`version_find_latest $list`
>> +for linux in $reverse_sorted_list; do
>>gettext_printf "Found linux image: %s\n" "$linux" >&2
>>basename=`basename $linux`
>>dirname=`dirname $linux`
>> @@ -293,8 +299,6 @@ while [ "x$list" != "x" ] ; do
>> linux_entry "${OS}" "${version}" recovery \
>> "${GRUB_CMDLINE_LINUX_RECOVERY} ${GRUB_CMDLINE_LINUX}"
>>fi
>> -
>> - list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
>> done
>>
>> # If at least one kernel was found, then we need to
>> --
>> 2.30.2
>>
>>
>> ___
>> Grub-devel mailing list
>> Grub-devel@gnu.org
>> https://lists.gnu.org/mailman/listinfo/grub-devel
>
> ___
> Grub-devel mailing list
> Grub-devel@gnu.org
> https://lists.gnu.org/mailman/listinfo/grub-devel
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
___
Grub-devel mailing list
Grub-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
- On May 3, 2022, at 1:15 PM, Mihai Moldovan io...@ionic.de wrote: > Just a nit, feel free to ignore it... > > > * On 5/3/22 4:42 PM, Mathieu Desnoyers wrote: >> How does the following paragraph sound ? >> >> >> Here is the improved algorithm proposed: >> >> - Prepare a list with all the relevant information for ordering by a single >> sort(1) execution. This is done by renaming ".old" suffixes by " 1" and >> by suffixing all other files with " 2", thus making sure the ".old" entries >> will follow the non-old entries in reverse-sorted-order. >> - Call version_reverse_sort on the list (sort -r -V): A single execution of >> sort(1) will reverse-sort the list in O(n*log(n)) with a merge sort. > > This is correct for GNU coreutils's sort, but nothing (I'm mostly thinking of > SUS/POSIX here) mandates that the sort utility must either use merge sort or > have O(n*log(n)) time complexity. > > Given that you're using version sort, which is a GNU extension, it probably > can't be anything than GNU sort anyway, though, so the point still holds by > implicity. I'm using the same sort already used in version_sort(). It uses sort -V if available, but there is a fallback to sort if -V is not available. Therefore, nothing implies a version sort, so nothing implies a GNU extension. So your point about other sort not necessarily being O(nlog(n)) merge sort is valid. I will remove this statement from the next patch version commit message. Thanks, Mathieu -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com ___ Grub-devel mailing list Grub-devel@gnu.org https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH 0/7] Various docs improvements
On Wed, May 11, 2022 at 09:56:17PM -0500, Glenn Washburn wrote: > The first 4 patches need no explanation. The 5th patch creates a new section > just for loader commands and moves loader commands to that section from the > general commands section. Patch #6 adds an itemized list of currently > under-documented loader commands to the text part of the loader command > section. And patch #7 adds a new section for undocumented commands and > contains an itemized list of undocumented commands (now minimally documented!) > > These two lists of undocumented commands was partially generated by grepping > for command registration in the source and pulling out the registered command > name and help string. The hope is that these two lists will make it easier for > non-programmers (or anyone) to contribute to GRUB by choosing a command to > flesh out. Also, I wanted this list so that I have a way to quickly see all > the available commands to choose potentially interesting ones for use. So > far I've found some commands that I didn't know existed. > > I don't particularly like how patch #6 renders to html, with the justification > of the two itemized lists (one of the undocumented loader commands and the > other the documented loader commands) being different. I'm open to suggestiong > on how this might be improved. > > Glenn > > Glenn Washburn (7): > docs: Fix spelling typo and remove unnecessary spaces > docs: Make note that sendkey is only available on i386-pc > docs: Make note of i386-pc specific usage of halt command > docs: Markup loader commands with @command tag > docs: Create command section for loader commands > docs: Add under documented loader commands to beginning of loader > section > docs: Add section for general undocumented commands For all the patches Reviewed-by: Daniel Kiper ... Thank you for doing this! Daniel ___ Grub-devel mailing list Grub-devel@gnu.org https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH v3] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
On Thu, May 05, 2022 at 10:24:56AM -0400, Mathieu Desnoyers wrote:
> The current implementation of the 10_linux script implements its menu
> items sorting in bash with a quadratic algorithm, calling "sed", "sort",
> "head", and "grep" to compare versions between individual lines, which
> is annoyingly slow for kernel developers who can easily end up with
> 50-100 kernels in /boot.
>
> As an example, on a Intel(R) Core(TM) i7-8650U CPU @ 1.90GHz, running:
>
> /usr/sbin/grub-mkconfig > /dev/null
>
> With 44 kernels in /boot, this command takes 10-15 seconds to complete.
> After this fix, the same command runs in 5 seconds.
>
> With 116 kernels in /boot, this command takes 40 seconds to complete.
> After this fix, the same command runs in 8 seconds.
>
> For reference, the quadratic algorithm here is:
>
> while [ "x$list" != "x" ] ; do <--- outer loop
> linux=`version_find_latest $list`
> version_find_latest()
> for i in "$@" ; do<--- inner loop
> version_test_gt()
> fork+exec sed
> version_test_numeric()
> version_sort
> fork+exec sort
> fork+exec head -n 1
> fork+exec grep
> list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
> tr
> fgrep
> tr
>
> So all commands executed under version_test_gt() are executed
> O(n^2) times where n is the number of kernel images in /boot.
>
> Here is the improved algorithm proposed:
>
> - Prepare a list with all the relevant information for ordering by a single
> sort(1) execution. This is done by renaming ".old" suffixes by " 1" and
> by suffixing all other files with " 2", thus making sure the ".old" entries
> will follow the non-old entries in reverse-sorted-order.
> - Call version_reverse_sort on the list (sort -r -V): A single execution of
> sort(1) will reverse-sort the list in O(n*log(n)) with a merge sort.
> - Replace the " 1" suffixes by ".old", and remove the " 2" suffixes.
> - Iterate on the reverse-sorted list to output each menu entry item.
>
> Therefore, the algorithm proposed has O(n*log(n)) complexity compared to
> the prior O(n^2) complexity. Moreover, the constant time required for each
> list entry is much less because sorting is done within a single execution
> of sort(1) rather than requiring O(n^2) executions of sed(1), sort(1),
> head(1), and grep(1) in sub-shells.
>
> I notice that the same quadratic sorting is done for other supported
> OSes, so I suspect similar gains can be obtained there, but I limit the
> scope of this patch to Linux because this is the platform on which I can
> test.
>
> Signed-off-by: Mathieu Desnoyers
> ---
> Changes since v1:
> - Escape the dot from .old in the sed match pattern, thus ensuring it
> matches ".old" rather than "[any character]old".
> - Use "sed" rather than "sed -e" everywhere for consistency.
> - Document the new algorithm in the commit message.
>
> Changes since v2:
> - Rename version_reverse_sort_sort_has_v to version_sort_sort_has_v,
> - Combine multiple sed executions into a single sed -e ... -e ...
> ---
> util/grub-mkconfig_lib.in | 18 ++
> util/grub.d/10_linux.in | 12
> 2 files changed, 26 insertions(+), 4 deletions(-)
>
> diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in
> index 301d1ac22..201b8b7c8 100644
> --- a/util/grub-mkconfig_lib.in
> +++ b/util/grub-mkconfig_lib.in
> @@ -218,6 +218,24 @@ version_sort ()
> esac
> }
>
> +version_reverse_sort ()
> +{
> + case $version_sort_sort_has_v in
> +yes)
> + LC_ALL=C sort -r -V;;
> +no)
> + LC_ALL=C sort -r -n;;
> +*)
> + if sort -V /dev/null 2>&1; then
> +version_sort_sort_has_v=yes
> +LC_ALL=C sort -r -V
> + else
> +version_sort_sort_has_v=no
> +LC_ALL=C sort -r -n
> + fi;;
> + esac
> +}
> +
> version_test_numeric ()
> {
>version_test_numeric_a="$1"
> diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in
> index ca068038e..8178318f5 100644
> --- a/util/grub.d/10_linux.in
> +++ b/util/grub.d/10_linux.in
> @@ -195,9 +195,15 @@ title_correction_code=
> # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
> submenu_indentation=""
>
> +# Perform a reverse version sort on the entire list.
> +# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all
> +# other files to order the '.old' files after their non-old counterpart
> +# in reverse-sorted order.
> +
> +reverse_sorted_list=$(echo $list | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/
> 1$/! s/$/ 2/' | version_reverse_sort | sed -e 's/ 1$/.old/' -e 's/ 2$//')
> +
> is_top_level=true
> -while [ "x$list" != "x" ] ; do
> - linux=`version_find_latest $list`
> +for linux in $reverse_sorted_list; do
>gettext_printf "Found linux image: %s\n" "$linux" >&2
>basename=`basename $linux`
>dirname=`dirname $linux`
> @@ -293,8 +299,6 @@ while [ "x$list" != "x" ] ; do
>
Re: [PATCH v2 4/5] cryptodisk: Use enum constants as indexes into cryptomount option array
On Fri, May 13, 2022 at 12:00:50PM -0500, Glenn Washburn wrote:
> Signed-off-by: Glenn Washburn
> ---
> grub-core/disk/cryptodisk.c | 53 ++---
> 1 file changed, 32 insertions(+), 21 deletions(-)
>
> diff --git a/grub-core/disk/cryptodisk.c b/grub-core/disk/cryptodisk.c
> index 94640b502..ecbda7ce9 100644
> --- a/grub-core/disk/cryptodisk.c
> +++ b/grub-core/disk/cryptodisk.c
> @@ -35,6 +35,17 @@ GRUB_MOD_LICENSE ("GPLv3+");
>
> grub_cryptodisk_dev_t grub_cryptodisk_list;
>
> +enum
> + {
> +OPTION_UUID,
> +OPTION_ALL,
> +OPTION_BOOT,
> +OPTION_PASSWORD,
> +OPTION_KEYFILE,
> +OPTION_KEYFILE_OFFSET,
> +OPTION_KEYFILE_SIZE
> + };
I would prefer constants here.
Otherwise patches LGTM.
Daniel
___
Grub-devel mailing list
Grub-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH v2 3/5] cryptodisk: Add options to cryptomount to support keyfiles
On Fri, May 13, 2022 at 12:00:49PM -0500, Glenn Washburn wrote:
> From: John Lane
>
> Add the options --key-file, --keyfile-offset, and --keyfile-size to
> cryptomount and code to put read the requested key file data and pass
> via the cargs struct. Note, key file data is for all intents and purposes
> equivalent to a password given to cryptomount. So there is no need to
> enable support for key files in the various crypto backends (eg. LUKS1)
> because the key data is passed just as if it were a password.
>
> Signed-off-by: John Lane
> gnu...@cyberdimension.org: rebase, patch split, small fixes, commit message
> Signed-off-by: Denis 'GNUtoo' Carikli
> developm...@efficientek.com: rebase and rework to use cryptomount arg passing,
> minor fixes, improve commit message
> Signed-off-by: Glenn Washburn
> ---
> grub-core/disk/cryptodisk.c | 104 +++-
> include/grub/cryptodisk.h | 2 +
> include/grub/file.h | 2 +
> 3 files changed, 107 insertions(+), 1 deletion(-)
>
> diff --git a/grub-core/disk/cryptodisk.c b/grub-core/disk/cryptodisk.c
> index 9f5dc7acb..94640b502 100644
> --- a/grub-core/disk/cryptodisk.c
> +++ b/grub-core/disk/cryptodisk.c
> @@ -42,6 +42,9 @@ static const struct grub_arg_option options[] =
> {"all", 'a', 0, N_("Mount all."), 0, 0},
> {"boot", 'b', 0, N_("Mount all volumes with `boot' flag set."), 0, 0},
> {"password", 'p', 0, N_("Password to open volumes."), 0,
> ARG_TYPE_STRING},
> +{"key-file", 'k', 0, N_("Key file"), 0, ARG_TYPE_STRING},
> +{"keyfile-offset", 'O', 0, N_("Key file offset (bytes)"), 0,
> ARG_TYPE_INT},
> +{"keyfile-size", 'S', 0, N_("Key file data size (bytes)"), 0,
> ARG_TYPE_INT},
> {0, 0, 0, 0, 0, 0}
>};
>
> @@ -1172,6 +1175,103 @@ grub_cmd_cryptomount (grub_extcmd_context_t ctxt, int
> argc, char **args)
>cargs.key_len = grub_strlen (state[3].arg);
> }
>
> + if (state[4].set) /* keyfile */
> +{
> + char tmp_errmsg[GRUB_MAX_ERRMSG];
> + const char *p = NULL;
> + grub_file_t keyfile;
> + unsigned long long keyfile_offset = 0, keyfile_size = 0;
> +
> + if (state[5].set) /* keyfile-offset */
> + {
> + grub_errno = GRUB_ERR_NONE;
> + keyfile_offset = grub_strtoull (state[5].arg, , 0);
> +
> + if (state[5].arg[0] == '\0' || *p != '\0')
> + {
> + if (grub_errno != GRUB_ERR_NONE)
> + {
> + grub_strncpy (tmp_errmsg, grub_errmsg, GRUB_MAX_ERRMSG);
> + return grub_error (grub_errno,
> + N_("non-numeric or invalid keyfile offset
> `%s': %s"),
> + state[5].arg, tmp_errmsg);
> + }
> + else
> + return grub_error (GRUB_ERR_BAD_ARGUMENT,
> +N_("invalid keyfile offset `%s': non-numeric"
> + " characters at end of number"),
> +state[5].arg);
I think this does not give us a lot of value. I would just do
if (state[5].arg[0] == '\0' || *p != '\0')
return grub_error (GRUB_ERR_BAD_NUMBER, ...
> + }
> + }
> +
> + if (state[6].set) /* keyfile-size */
> + {
> + grub_errno = GRUB_ERR_NONE;
> + keyfile_size = grub_strtoull (state[6].arg, , 0);
> +
> + if (state[6].arg[0] == '\0' || *p != '\0')
> + {
> + if (grub_errno != GRUB_ERR_NONE)
> + {
> + grub_strncpy (tmp_errmsg, grub_errmsg, GRUB_MAX_ERRMSG);
> + return grub_error (grub_errno,
> + N_("non-numeric or invalid keyfile offset
> `%s': %s"),
> + state[5].arg, tmp_errmsg);
> + }
> + else
> + return grub_error (GRUB_ERR_BAD_ARGUMENT,
> +N_("invalid keyfile offset `%s': non-numeric"
> + " characters at end of number"),
> +state[6].arg);
Ditto.
> + }
> +
> + if (keyfile_size > GRUB_CRYPTODISK_MAX_KEYFILE_SIZE)
> + return grub_error (GRUB_ERR_OUT_OF_RANGE,
> +N_("key file size exceeds maximum (%d)"),
> +GRUB_CRYPTODISK_MAX_KEYFILE_SIZE);
> +
> + if (keyfile_size == 0)
> + return grub_error (GRUB_ERR_OUT_OF_RANGE, N_("key file size is 0"));
Nit, I would move this before the "if (keyfile_size > ...". This would
be more natural.
Daniel
___
Grub-devel mailing list
Grub-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH v2 00/15] Dynamic allocation of memory regions and IBM vTPM v2
On Wed, May 18, 2022 at 11:24:48AM -0400, Stefan Berger wrote: > On 4/14/22 11:30, Daniel Kiper wrote: > > On Thu, Apr 07, 2022 at 04:41:04PM +0200, Daniel Kiper wrote: > > > On Mon, Mar 28, 2022 at 05:22:25PM +1100, Daniel Axtens wrote: > > > > Hi all, > > > > > > > > This is, at long last, an updated version of my series extending > > > > Patrick's > > > > dynamic memory regions to ieee1275. > > > > > > > > Noteworthy changes: > > > > > > > > - reworked debug prints as grub_dprintfs. Folded the ieee1275 ones > > > > into the > > > > ieee1275 patches. > > > > > > > > - reworked the ieee1275 runtime memory claiming to be more resilient > > > > and better > > > > documented. > > > > > > > > - fixed comment style and hopefully addressed all other change > > > > requests. > > > > > > > > - grub will now try asking for contiguous memory and then, if that > > > > fails, for > > > > discontiguous memory - in case region merging with the > > > > discontiguous memory > > > > is sufficient to allow the eventual allocation to succeed. > > > > > > Patrick, all mm and EFI code got my RB. Could you test it with your > > > Argon changes? If these changes pass your tests I will merge them. > > > > Patrick, ping? > > > > To be more precise, I am thinking about the patches up to #10. > > > > Daniel > > Any way we can make progress with this series before it gets all forgotten > about? It is not and it will not be forgotten. I am waiting for some allocator tests reports. When I get them I will merge allocator stuff and review the rest of the code from this patch series. Sadly folks who are going to test the code are busy with other stuff. Though I am pinging them... Anyway, sorry for delay... Daniel ___ Grub-devel mailing list Grub-devel@gnu.org https://lists.gnu.org/mailman/listinfo/grub-devel
Re: [PATCH v3] efidisk: pass buffers with higher alignment
On 2022-05-18 10:59, Stefan Agner wrote:
> Some devices report a IoAlign value of 2, however seem to require a
> buffer with higher alignment.
After releasing Home Assistant OS 8.0 publicly, some systems still
refuse to boot even with this patch applied. See bug reports collected
in this issue:
https://github.com/home-assistant/operating-system/issues/1912
At least in one instance using block size alignment helped. I am going
to change to block size aligned unconditionally, and see how that
behaves in wider deployment.
--
Stefan
>
> The UEFI specification is saying: "IoAlign values of 0 and 1 mean that
> the buffer can be placed anywhere in memory. Otherwise, IoAlign must
> be a power of 2, and the requirement is that the start address of a
> buffer must be evenly divisible by IoAlign with no remainder."
>
> It seems that this got misinterpreted by some vendors assuming IoAlign
> is 2^IoAlign. There is also such a hint in an example in earlier
> versions of the Driver Writer's Guide:
> ScsiPassThruMode.IoAlign = 2; // Data must be alligned on 4-byte boundary
>
> However, it is unsafe to just blindly align buffers by 2^IoAlign, as
> this would lead to an overflow for systems which use block size
> alignment (e.g. 512 bytes, for example U-Boot).
>
> Work around by using an alignment of at least BlockSize (typically 512
> bytes) in case alignment is requested. Also make sure that IoAlign is
> still respected as per UEFI specification if a higher alignment than
> block size is requested.
>
> Note: The problem has only noticed with compressed squashfs. It seems
> that ext4 (and presumably other file system drivers) pass buffers with
> a higher alignment already.
>
> Acked-by: Heinrich Schuchardt
> Signed-off-by: Stefan Agner
> ---
> grub-core/disk/efi/efidisk.c | 18 --
> 1 file changed, 16 insertions(+), 2 deletions(-)
>
> diff --git a/grub-core/disk/efi/efidisk.c b/grub-core/disk/efi/efidisk.c
> index 9e20af70e..c4eb4f4e7 100644
> --- a/grub-core/disk/efi/efidisk.c
> +++ b/grub-core/disk/efi/efidisk.c
> @@ -553,8 +553,22 @@ grub_efidisk_readwrite (struct grub_disk *disk,
> grub_disk_addr_t sector,
>d = disk->data;
>bio = d->block_io;
>
> - /* Set alignment to 1 if 0 specified */
> - io_align = bio->media->io_align ? bio->media->io_align : 1;
> + /*
> + * If IoAlign is > 1, it should represent the required alignment. However,
> + * some UEFI implementation on Intel NUC systems seem to use IoAlign=2 but
> + * require 2^IoAlign.
> + * Make sure to align to at least block size if IO alignment is required.
> + */
> + if (bio->media->io_align > 1)
> +{
> + if (bio->media->io_align < bio->media->block_size)
> +io_align = bio->media->block_size;
> + else
> +io_align = bio->media->io_align;
> +}
> + else
> +io_align = 1;
> +
>num_bytes = size << disk->log_sector_size;
>
>if ((grub_addr_t) buf & (io_align - 1))
___
Grub-devel mailing list
Grub-devel@gnu.org
https://lists.gnu.org/mailman/listinfo/grub-devel
