[PATCH v5 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items

[PATCH v5 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

This series of patches fixes a O(n^2) algorithm in the menu items
generation scripts.

Testing is still needed on linux_xen, hurd, and kfreebsd.

Mathieu

Mathieu Desnoyers (5):
  grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
  grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu
    items
  grub-mkconfig hurd: Fix quadratic algorithm for sorting menu items
  grub-mkconfig kfreebsd: Fix quadratic algorithm for sorting menu items
  Cleanup: grub-mkconfig_lib: remove unused version comparison functions

 util/grub-mkconfig_lib.in   | 59 +++----------------------------------
 util/grub.d/10_hurd.in      | 14 +++++----
 util/grub.d/10_kfreebsd.in  | 12 +++++---
 util/grub.d/10_linux.in     | 12 +++++---
 util/grub.d/20_linux_xen.in | 18 ++++++-----
 5 files changed, 39 insertions(+), 76 deletions(-)

-- 
2.30.2

[PATCH v5 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

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). For instance, GNU coreutils' sort 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 with GNU
coreutils' sort 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.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Reviewed-by: Robbie Harwood <rharwood@redhat.com>
---
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 ...

Changes since v3:
- Modify version_sort to expect arguments, and call "version_sort -r",
  rather than copying it as a "version_reverse_sort".
- Specify that O(n*log(n)) merge sort is specific to GNU coreutils' sort.

Changes since v4:
- Combine sed -e '...' -e '...' into sed -e '...; ...'
---
 util/grub-mkconfig_lib.in |  8 ++++----
 util/grub.d/10_linux.in   | 12 ++++++++----
 2 files changed, 12 insertions(+), 8 deletions(-)

diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in
index 301d1ac22..fc14afdb3 100644
--- a/util/grub-mkconfig_lib.in
+++ b/util/grub-mkconfig_lib.in
@@ -204,16 +204,16 @@ version_sort ()
 {
   case $version_sort_sort_has_v in
     yes)
-      LC_ALL=C sort -V;;
+      LC_ALL=C sort -V $@;;
     no)
-      LC_ALL=C sort -n;;
+      LC_ALL=C sort -n $@;;
     *)
       if sort -V </dev/null > /dev/null 2>&1; then
         version_sort_sort_has_v=yes
-	LC_ALL=C sort -V
+	LC_ALL=C sort -V $@
       else
         version_sort_sort_has_v=no
-        LC_ALL=C sort -n
+        LC_ALL=C sort -n $@
       fi;;
    esac
 }
diff --git a/util/grub.d/10_linux.in b/util/grub.d/10_linux.in
index b4a4d6900..c6a1ec935 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/; / 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/; 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`
@@ -295,8 +301,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

[PATCH v5 2/5] grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

The current implementation of the 20_linux_xen 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 their boot partition.

This fix is ported from the 10_linux script, which has a similar
quadratic code pattern.

[ Note: this is untested. I would be grateful if anyone with a Xen
  environment could test it before it is merged. ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: xen-devel@lists.xenproject.org
---
Changes since v4:
- Combine sed -e '...' -e '...' into sed -e '...; ...'
---
 util/grub.d/20_linux_xen.in | 18 ++++++++++--------
 1 file changed, 10 insertions(+), 8 deletions(-)

diff --git a/util/grub.d/20_linux_xen.in b/util/grub.d/20_linux_xen.in
index 51a983926..4382303c1 100644
--- a/util/grub.d/20_linux_xen.in
+++ b/util/grub.d/20_linux_xen.in
@@ -237,11 +237,17 @@ esac
 # 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 xen_list and linux_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_xen_list=$(echo ${xen_list} | tr ' ' '\n' | sed -e 's/\.old$/ 1/; / 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/; s/ 2$//')
+reverse_sorted_linux_list=$(echo ${linux_list} | tr ' ' '\n' | sed -e 's/\.old$/ 1/; / 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/; s/ 2$//')
+
 is_top_level=true
 
-while [ "x${xen_list}" != "x" ] ; do
-    list="${linux_list}"
-    current_xen=`version_find_latest $xen_list`
+for current_xen in ${reverse_sorted_xen_list}; do
     xen_basename=`basename ${current_xen}`
     xen_dirname=`dirname ${current_xen}`
     rel_xen_dirname=`make_system_path_relative_to_its_root $xen_dirname`
@@ -273,8 +279,7 @@ while [ "x${xen_list}" != "x" ] ; do
        fi
     done
 
-    while [ "x$list" != "x" ] ; do
-	linux=`version_find_latest $list`
+    for linux in ${reverse_sorted_linux_list}; do
 	gettext_printf "Found linux image: %s\n" "$linux" >&2
 	basename=`basename $linux`
 	dirname=`dirname $linux`
@@ -351,13 +356,10 @@ while [ "x${xen_list}" != "x" ] ; do
 	    linux_entry "${OS}" "${version}" "${xen_version}" recovery \
 		"${GRUB_CMDLINE_LINUX_RECOVERY} ${GRUB_CMDLINE_LINUX}" "${GRUB_CMDLINE_XEN}"
 	fi
-
-	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
 
 # If at least one kernel was found, then we need to
-- 
2.30.2

[PATCH v5 3/5] grub-mkconfig hurd: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

The current implementation of the 10_hurd 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 their boot partition.

This fix is ported from the 10_linux script, which has a similar
quadratic code pattern.

[ Note: this is untested. I would be grateful if anyone with a Hurd
  environment could test it before it is merged. ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Samuel Thibault <samuel.thibault@ens-lyon.org>
---
Changes since v4:
- Combine sed -e '...' -e '...' into sed -e '...; ...'
---
 util/grub.d/10_hurd.in | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/util/grub.d/10_hurd.in b/util/grub.d/10_hurd.in
index 2fafa4e59..4294bbe4c 100644
--- a/util/grub.d/10_hurd.in
+++ b/util/grub.d/10_hurd.in
@@ -197,11 +197,17 @@ title_correction_code=
 # Extra indentation to add to menu entries in a submenu. We're not in a submenu
 # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
 submenu_indentation=""
-is_top_level=true
 
-while [ "x$kernels" != "x" ] ; do
-  kernel=`version_find_latest $kernels`
+# Perform a reverse version sort on the entire kernels 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_kernels=$(echo ${kernels} | tr ' ' '\n' | sed -e 's/\.old$/ 1/; / 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/; s/ 2$//')
 
+is_top_level=true
+
+for kernel in ${reverse_sorted_kernels}; do
   # The GRUB_DISABLE_SUBMENU option used to be different than others since it was
   # mentioned in the documentation that has to be set to 'y' instead of 'true' to
   # enable it. This caused a lot of confusion to users that set the option to 'y',
@@ -221,8 +227,6 @@ while [ "x$kernels" != "x" ] ; do
 
   hurd_entry "$kernel" advanced
   hurd_entry "$kernel" recovery
-
-  kernels=`echo $kernels | tr ' ' '\n' | fgrep -vx "$kernel" | tr '\n' ' '`
 done
 
 # If at least one kernel was found, then we need to
-- 
2.30.2

[PATCH v5 4/5] grub-mkconfig kfreebsd: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

The current implementation of the 10_kfreebsd 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 their boot partition.

This fix is ported from the 10_linux script, which has a similar
quadratic code pattern.

[ Note: this is untested. I would be grateful if anyone with a kfreebsd
  environment could test it before it is merged. ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: debian-bsd@lists.debian.org
---
Changes since v4:
- Combine sed -e '...' -e '...' into sed -e '...; ...'
---
 util/grub.d/10_kfreebsd.in | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

diff --git a/util/grub.d/10_kfreebsd.in b/util/grub.d/10_kfreebsd.in
index 199b20e16..0a67decaa 100644
--- a/util/grub.d/10_kfreebsd.in
+++ b/util/grub.d/10_kfreebsd.in
@@ -157,10 +157,16 @@ 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/; / 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/; s/ 2$//')
+
 is_top_level=true
 
-while [ "x$list" != "x" ] ; do
-  kfreebsd=`version_find_latest $list`
+for kfreebsd in ${reverse_sorted_list}; do
   gettext_printf "Found kernel of FreeBSD: %s\n" "$kfreebsd" >&2
   basename=`basename $kfreebsd`
   dirname=`dirname $kfreebsd`
@@ -238,8 +244,6 @@ while [ "x$list" != "x" ] ; do
   if [ "x${GRUB_DISABLE_RECOVERY}" != "xtrue" ]; then
     kfreebsd_entry "${OS}" "${version}" recovery "-s"
   fi
-
-  list=`echo $list | tr ' ' '\n' | fgrep -vx "$kfreebsd" | tr '\n' ' '`
 done
 
 # If at least one kernel was found, then we need to
-- 
2.30.2

[PATCH v5 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions

[Mathieu Desnoyers]

There are no users left of version_find_latest(), version_test_gt(), and
version_test_numeric(). Remove those unused helper functions. Using
those helper functions is what caused the quadratic sorting performance
issues in the first place, so removing them is a net win.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Reviewed-by: Robbie Harwood <rharwood@redhat.com>
---
 util/grub-mkconfig_lib.in | 51 ---------------------------------------
 1 file changed, 51 deletions(-)

diff --git a/util/grub-mkconfig_lib.in b/util/grub-mkconfig_lib.in
index fc14afdb3..de1bb5310 100644
--- a/util/grub-mkconfig_lib.in
+++ b/util/grub-mkconfig_lib.in
@@ -218,57 +218,6 @@ version_sort ()
    esac
 }
 
-version_test_numeric ()
-{
-  version_test_numeric_a="$1"
-  version_test_numeric_cmp="$2"
-  version_test_numeric_b="$3"
-  if [ "$version_test_numeric_a" = "$version_test_numeric_b" ] ; then
-    case "$version_test_numeric_cmp" in
-      ge|eq|le) return 0 ;;
-      gt|lt) return 1 ;;
-    esac
-  fi
-  if [ "$version_test_numeric_cmp" = "lt" ] ; then
-    version_test_numeric_c="$version_test_numeric_a"
-    version_test_numeric_a="$version_test_numeric_b"
-    version_test_numeric_b="$version_test_numeric_c"
-  fi
-  if (echo "$version_test_numeric_a" ; echo "$version_test_numeric_b") | version_sort | head -n 1 | grep -qx "$version_test_numeric_b" ; then
-    return 0
-  else
-    return 1
-  fi
-}
-
-version_test_gt ()
-{
-  version_test_gt_a="`echo "$1" | sed -e "s/[^-]*-//"`"
-  version_test_gt_b="`echo "$2" | sed -e "s/[^-]*-//"`"
-  version_test_gt_cmp=gt
-  if [ "x$version_test_gt_b" = "x" ] ; then
-    return 0
-  fi
-  case "$version_test_gt_a:$version_test_gt_b" in
-    *.old:*.old) ;;
-    *.old:*) version_test_gt_a="`echo "$version_test_gt_a" | sed -e 's/\.old$//'`" ; version_test_gt_cmp=gt ;;
-    *:*.old) version_test_gt_b="`echo "$version_test_gt_b" | sed -e 's/\.old$//'`" ; version_test_gt_cmp=ge ;;
-  esac
-  version_test_numeric "$version_test_gt_a" "$version_test_gt_cmp" "$version_test_gt_b"
-  return "$?"
-}
-
-version_find_latest ()
-{
-  version_find_latest_a=""
-  for i in "$@" ; do
-    if version_test_gt "$i" "$version_find_latest_a" ; then
-      version_find_latest_a="$i"
-    fi
-  done
-  echo "$version_find_latest_a"
-}
-
 # One layer of quotation is eaten by "" and the second by sed; so this turns
 # ' into \'.
 grub_quote () {
-- 
2.30.2

Re: [PATCH v5 2/5] grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu items

[Jason Andryuk]

On Thu, Jun 9, 2022 at 2:50 PM Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
>
> The current implementation of the 20_linux_xen 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 their boot partition.
>
> This fix is ported from the 10_linux script, which has a similar
> quadratic code pattern.
>
> [ Note: this is untested. I would be grateful if anyone with a Xen
>   environment could test it before it is merged. ]

Hi, Mathieu,

I tested by manually applying patch 2/5 on top of Fedora 36's
installed /etc/grub.d/20_linux_xen, and manually applying patch 1/5 to
/usr/share/grub/grub-mkconfig_lib.  It seems to generate grub.cfg
menuentry-ies in the correct order.

Note for patch 1/5, it's best practice to use "$@" with the double
quotes to prevent word splitting of arguments.  Doesn't really matter
for that function at this time though.

Regards,
Jason

Re: [PATCH v5 3/5] grub-mkconfig hurd: Fix quadratic algorithm for sorting menu items

[Samuel Thibault]

Hello,

Mathieu Desnoyers, le jeu. 09 juin 2022 14:50:22 -0400, a ecrit:
> The current implementation of the 10_hurd 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 their boot partition.
> 
> This fix is ported from the 10_linux script, which has a similar
> quadratic code pattern.
> 
> [ Note: this is untested. I would be grateful if anyone with a Hurd
>   environment could test it before it is merged. ]
> 
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Cc: Samuel Thibault <samuel.thibault@ens-lyon.org>

Tested-by: Samuel Thibault <samuel.thibault@ens-lyon.org>

> ---
> Changes since v4:
> - Combine sed -e '...' -e '...' into sed -e '...; ...'
> ---
>  util/grub.d/10_hurd.in | 14 +++++++++-----
>  1 file changed, 9 insertions(+), 5 deletions(-)
> 
> diff --git a/util/grub.d/10_hurd.in b/util/grub.d/10_hurd.in
> index 2fafa4e59..4294bbe4c 100644
> --- a/util/grub.d/10_hurd.in
> +++ b/util/grub.d/10_hurd.in
> @@ -197,11 +197,17 @@ title_correction_code=
>  # Extra indentation to add to menu entries in a submenu. We're not in a submenu
>  # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
>  submenu_indentation=""
> -is_top_level=true
>  
> -while [ "x$kernels" != "x" ] ; do
> -  kernel=`version_find_latest $kernels`
> +# Perform a reverse version sort on the entire kernels 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_kernels=$(echo ${kernels} | tr ' ' '\n' | sed -e 's/\.old$/ 1/; / 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/; s/ 2$//')
>  
> +is_top_level=true
> +
> +for kernel in ${reverse_sorted_kernels}; do
>    # The GRUB_DISABLE_SUBMENU option used to be different than others since it was
>    # mentioned in the documentation that has to be set to 'y' instead of 'true' to
>    # enable it. This caused a lot of confusion to users that set the option to 'y',
> @@ -221,8 +227,6 @@ while [ "x$kernels" != "x" ] ; do
>  
>    hurd_entry "$kernel" advanced
>    hurd_entry "$kernel" recovery
> -
> -  kernels=`echo $kernels | tr ' ' '\n' | fgrep -vx "$kernel" | tr '\n' ' '`
>  done
>  
>  # If at least one kernel was found, then we need to
> -- 
> 2.30.2
> 

-- 
Samuel
---
Pour une évaluation indépendante, transparente et rigoureuse !
Je soutiens la Commission d'Évaluation de l'Inria.

Re: [PATCH v5 2/5] grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

----- On Jun 10, 2022, at 4:00 PM, Jason Andryuk jandryuk@gmail.com wrote:

> On Thu, Jun 9, 2022 at 2:50 PM Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
>>
>> The current implementation of the 20_linux_xen 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 their boot partition.
>>
>> This fix is ported from the 10_linux script, which has a similar
>> quadratic code pattern.
>>
>> [ Note: this is untested. I would be grateful if anyone with a Xen
>>   environment could test it before it is merged. ]
> 
> Hi, Mathieu,
> 
> I tested by manually applying patch 2/5 on top of Fedora 36's
> installed /etc/grub.d/20_linux_xen, and manually applying patch 1/5 to
> /usr/share/grub/grub-mkconfig_lib.  It seems to generate grub.cfg
> menuentry-ies in the correct order.

Noted. Added your Tested-by to patch 2/5. Thanks!

> 
> Note for patch 1/5, it's best practice to use "$@" with the double
> quotes to prevent word splitting of arguments.  Doesn't really matter
> for that function at this time though.

I'll update patch 1/5 with this change. It's best practice indeed. I notice
that there are quite a few other places in grub-mkconfig_lib.in that do
follow this best practice though.

Thanks,

Mathieu

> 
> Regards,
> Jason

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

Re: [PATCH v5 3/5] grub-mkconfig hurd: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers]

----- On Jun 11, 2022, at 7:55 PM, samuel thibault samuel.thibault@ens-lyon.org wrote:

> Hello,
> 
> Mathieu Desnoyers, le jeu. 09 juin 2022 14:50:22 -0400, a ecrit:
>> The current implementation of the 10_hurd 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 their boot partition.
>> 
>> This fix is ported from the 10_linux script, which has a similar
>> quadratic code pattern.
>> 
>> [ Note: this is untested. I would be grateful if anyone with a Hurd
>>   environment could test it before it is merged. ]
>> 
>> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>> Cc: Samuel Thibault <samuel.thibault@ens-lyon.org>
> 
> Tested-by: Samuel Thibault <samuel.thibault@ens-lyon.org>

Noted. Adding your Tested-by tag to the message for my
next round. Thanks!

Mathieu

> 
>> ---
>> Changes since v4:
>> - Combine sed -e '...' -e '...' into sed -e '...; ...'
>> ---
>>  util/grub.d/10_hurd.in | 14 +++++++++-----
>>  1 file changed, 9 insertions(+), 5 deletions(-)
>> 
>> diff --git a/util/grub.d/10_hurd.in b/util/grub.d/10_hurd.in
>> index 2fafa4e59..4294bbe4c 100644
>> --- a/util/grub.d/10_hurd.in
>> +++ b/util/grub.d/10_hurd.in
>> @@ -197,11 +197,17 @@ title_correction_code=
>>  # Extra indentation to add to menu entries in a submenu. We're not in a submenu
>>  # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
>>  submenu_indentation=""
>> -is_top_level=true
>>  
>> -while [ "x$kernels" != "x" ] ; do
>> -  kernel=`version_find_latest $kernels`
>> +# Perform a reverse version sort on the entire kernels 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_kernels=$(echo ${kernels} | tr ' ' '\n' | sed -e 's/\.old$/ 1/;
>> / 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/; s/ 2$//')
>>  
>> +is_top_level=true
>> +
>> +for kernel in ${reverse_sorted_kernels}; do
>>    # The GRUB_DISABLE_SUBMENU option used to be different than others since it was
>>    # mentioned in the documentation that has to be set to 'y' instead of 'true' to
>>    # enable it. This caused a lot of confusion to users that set the option to 'y',
>> @@ -221,8 +227,6 @@ while [ "x$kernels" != "x" ] ; do
>>  
>>    hurd_entry "$kernel" advanced
>>    hurd_entry "$kernel" recovery
>> -
>> -  kernels=`echo $kernels | tr ' ' '\n' | fgrep -vx "$kernel" | tr '\n' ' '`
>>  done
>>  
>>  # If at least one kernel was found, then we need to
>> --
>> 2.30.2
>> 
> 
> --
> Samuel
> ---
> Pour une évaluation indépendante, transparente et rigoureuse !
> Je soutiens la Commission d'Évaluation de l'Inria.

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com