* [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items
@ 2022-05-20 14:37 Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 1/5] grub-mkconfig linux: " Mathieu Desnoyers
` (5 more replies)
0 siblings, 6 replies; 16+ messages in thread
From: Mathieu Desnoyers @ 2022-05-20 14:37 UTC (permalink / raw)
To: grub-devel; +Cc: 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
^ permalink raw reply [flat|nested] 16+ messages in thread
* [RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-20 14:37 [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
@ 2022-05-20 14:37 ` Mathieu Desnoyers
2022-05-26 15:13 ` Daniel Kiper
2022-05-20 14:37 ` [RFC PATCH v3 2/5] grub-mkconfig linux_xen: " Mathieu Desnoyers
` (4 subsequent siblings)
5 siblings, 1 reply; 16+ messages in thread
From: Mathieu Desnoyers @ 2022-05-20 14:37 UTC (permalink / raw)
To: grub-devel; +Cc: 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>
---
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.
---
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 ca068038e..001a97ce3 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_sort -r | 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
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
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [RFC PATCH v3 2/5] grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu items
2022-05-20 14:37 [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 1/5] grub-mkconfig linux: " Mathieu Desnoyers
@ 2022-05-20 14:37 ` Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 3/5] grub-mkconfig hurd: " Mathieu Desnoyers
` (3 subsequent siblings)
5 siblings, 0 replies; 16+ messages in thread
From: Mathieu Desnoyers @ 2022-05-20 14:37 UTC (permalink / raw)
To: grub-devel; +Cc: Mathieu Desnoyers, xen-devel
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
---
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 f45559ff8..3178eb430 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/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
+reverse_sorted_linux_list=$(echo ${linux_list} | tr ' ' '\n' | sed -e 's/\.old$/ 1/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e '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`
@@ -349,13 +354,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
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [RFC PATCH v3 3/5] grub-mkconfig hurd: Fix quadratic algorithm for sorting menu items
2022-05-20 14:37 [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 1/5] grub-mkconfig linux: " Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 2/5] grub-mkconfig linux_xen: " Mathieu Desnoyers
@ 2022-05-20 14:37 ` Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 4/5] grub-mkconfig kfreebsd: " Mathieu Desnoyers
` (2 subsequent siblings)
5 siblings, 0 replies; 16+ messages in thread
From: Mathieu Desnoyers @ 2022-05-20 14:37 UTC (permalink / raw)
To: grub-devel; +Cc: Mathieu Desnoyers, Samuel Thibault
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>
---
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 2ab3a97e6..e0f290ae8 100644
--- a/util/grub.d/10_hurd.in
+++ b/util/grub.d/10_hurd.in
@@ -195,11 +195,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/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e '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',
@@ -219,8 +225,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
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [RFC PATCH v3 4/5] grub-mkconfig kfreebsd: Fix quadratic algorithm for sorting menu items
2022-05-20 14:37 [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
` (2 preceding siblings ...)
2022-05-20 14:37 ` [RFC PATCH v3 3/5] grub-mkconfig hurd: " Mathieu Desnoyers
@ 2022-05-20 14:37 ` Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions Mathieu Desnoyers
2022-05-20 16:08 ` [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
5 siblings, 0 replies; 16+ messages in thread
From: Mathieu Desnoyers @ 2022-05-20 14:37 UTC (permalink / raw)
To: grub-devel; +Cc: Mathieu Desnoyers, debian-bsd
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
---
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..930d8df9c 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/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e '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
^ permalink raw reply related [flat|nested] 16+ messages in thread
* [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions
2022-05-20 14:37 [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
` (3 preceding siblings ...)
2022-05-20 14:37 ` [RFC PATCH v3 4/5] grub-mkconfig kfreebsd: " Mathieu Desnoyers
@ 2022-05-20 14:37 ` Mathieu Desnoyers
2022-05-26 21:07 ` Robbie Harwood
2022-05-20 16:08 ` [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
5 siblings, 1 reply; 16+ messages in thread
From: Mathieu Desnoyers @ 2022-05-20 14:37 UTC (permalink / raw)
To: grub-devel; +Cc: 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>
---
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
^ permalink raw reply related [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items
2022-05-20 14:37 [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
` (4 preceding siblings ...)
2022-05-20 14:37 ` [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions Mathieu Desnoyers
@ 2022-05-20 16:08 ` Mathieu Desnoyers
2022-05-26 15:24 ` Daniel Kiper
5 siblings, 1 reply; 16+ messages in thread
From: Mathieu Desnoyers @ 2022-05-20 16:08 UTC (permalink / raw)
To: grub-devel
Sorry, the subject prefix for this patch series should have been [RFC PATCH v4 n/5].
----- On May 20, 2022, at 10:37 AM, Mathieu Desnoyers mathieu.desnoyers@efficios.com wrote:
> 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
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-20 14:37 ` [RFC PATCH v3 1/5] grub-mkconfig linux: " Mathieu Desnoyers
@ 2022-05-26 15:13 ` Daniel Kiper
2022-05-26 18:34 ` Mathieu Desnoyers
0 siblings, 1 reply; 16+ messages in thread
From: Daniel Kiper @ 2022-05-26 15:13 UTC (permalink / raw)
To: Mathieu Desnoyers; +Cc: grub-devel
On Fri, May 20, 2022 at 10:37:37AM -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). 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>
> ---
> 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.
> ---
> 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 ca068038e..001a97ce3 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_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
Nit, I think you can use one "-e" argument for sed, e.g. sed -e 's/\.old$/ 1/; / 1$/! s/$/ 2/'.
Otherwise patches LGTM.
Please hold on with rebase. I am going to push one more patch before
your patch series which may potentially conflict with your changes.
I will drop you a line when you can do it.
Daniel
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items
2022-05-20 16:08 ` [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
@ 2022-05-26 15:24 ` Daniel Kiper
0 siblings, 0 replies; 16+ messages in thread
From: Daniel Kiper @ 2022-05-26 15:24 UTC (permalink / raw)
To: Mathieu Desnoyers; +Cc: grub-devel
On Fri, May 20, 2022 at 12:08:05PM -0400, Mathieu Desnoyers wrote:
> Sorry, the subject prefix for this patch series should have been [RFC PATCH v4 n/5].
Next time you can drop RFC from the subject.
Daniel
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-26 15:13 ` Daniel Kiper
@ 2022-05-26 18:34 ` Mathieu Desnoyers
2022-06-08 18:10 ` Daniel Kiper
0 siblings, 1 reply; 16+ messages in thread
From: Mathieu Desnoyers @ 2022-05-26 18:34 UTC (permalink / raw)
To: Daniel Kiper; +Cc: grub-devel
----- On May 26, 2022, at 11:13 AM, Daniel Kiper dkiper@net-space.pl wrote:
> On Fri, May 20, 2022 at 10:37:37AM -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). 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>
>> ---
>> 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.
>> ---
>> 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 ca068038e..001a97ce3 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_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
>
> Nit, I think you can use one "-e" argument for sed, e.g. sed -e 's/\.old$/ 1/; /
> 1$/! s/$/ 2/'.
Good point, done.
>
> Otherwise patches LGTM.
>
> Please hold on with rebase. I am going to push one more patch before
> your patch series which may potentially conflict with your changes.
OK.
> I will drop you a line when you can do it.
Allright, I'll wait for you to reach out before sending the rebased final
non-RFC series.
Thanks,
Mathieu
>
> Daniel
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions
2022-05-20 14:37 ` [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions Mathieu Desnoyers
@ 2022-05-26 21:07 ` Robbie Harwood
2022-05-27 6:07 ` Michael Chang
0 siblings, 1 reply; 16+ messages in thread
From: Robbie Harwood @ 2022-05-26 21:07 UTC (permalink / raw)
To: Mathieu Desnoyers, grub-devel; +Cc: Mathieu Desnoyers
[-- Attachment #1: Type: text/plain, Size: 479 bytes --]
Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
> 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>
Be well,
--Robbie
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 861 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions
2022-05-26 21:07 ` Robbie Harwood
@ 2022-05-27 6:07 ` Michael Chang
2022-05-27 14:56 ` Robbie Harwood
0 siblings, 1 reply; 16+ messages in thread
From: Michael Chang @ 2022-05-27 6:07 UTC (permalink / raw)
To: The development of GNU GRUB; +Cc: Mathieu Desnoyers
On Thu, May 26, 2022 at 05:07:11PM -0400, Robbie Harwood wrote:
> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
>
> > 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>
Hm. This seems to contradict your proposed patch to use distro specific
sort by hooking into those functions got removed here.
mkconfig: use distro sorts when available
https://www.mail-archive.com/grub-devel@gnu.org/msg33357.html
I'd like to know more your comments about this as those hooks might
still be needed or where to keep distribution's sort ?
Thanks,
Michael
>
> Be well,
> --Robbie
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> https://lists.gnu.org/mailman/listinfo/grub-devel
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions
2022-05-27 6:07 ` Michael Chang
@ 2022-05-27 14:56 ` Robbie Harwood
2022-05-27 21:45 ` Daniel Kiper
2022-05-30 13:31 ` Mathieu Desnoyers
0 siblings, 2 replies; 16+ messages in thread
From: Robbie Harwood @ 2022-05-27 14:56 UTC (permalink / raw)
To: Michael Chang via Grub-devel, The development of GNU GRUB
Cc: Michael Chang, Mathieu Desnoyers
[-- Attachment #1: Type: text/plain, Size: 1187 bytes --]
Michael Chang via Grub-devel <grub-devel@gnu.org> writes:
> On Thu, May 26, 2022 at 05:07:11PM -0400, Robbie Harwood wrote:
>> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
>>
>>> 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>
>
> Hm. This seems to contradict your proposed patch to use distro specific
> sort by hooking into those functions got removed here.
>
> mkconfig: use distro sorts when available
> https://www.mail-archive.com/grub-devel@gnu.org/msg33357.html
>
> I'd like to know more your comments about this as those hooks might
> still be needed or where to keep distribution's sort ?
The series does, yes - both can't be applied as-is. I'm fine to rebase
mine, but haven't done it yet. I don't mind adding them back if I need
to.
Be well,
--Robbie
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 861 bytes --]
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions
2022-05-27 14:56 ` Robbie Harwood
@ 2022-05-27 21:45 ` Daniel Kiper
2022-05-30 13:31 ` Mathieu Desnoyers
1 sibling, 0 replies; 16+ messages in thread
From: Daniel Kiper @ 2022-05-27 21:45 UTC (permalink / raw)
To: Robbie Harwood
Cc: Michael Chang via Grub-devel, Michael Chang, Mathieu Desnoyers
On Fri, May 27, 2022 at 10:56:38AM -0400, Robbie Harwood wrote:
> Michael Chang via Grub-devel <grub-devel@gnu.org> writes:
>
> > On Thu, May 26, 2022 at 05:07:11PM -0400, Robbie Harwood wrote:
> >> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
> >>
> >>> 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>
> >
> > Hm. This seems to contradict your proposed patch to use distro specific
> > sort by hooking into those functions got removed here.
> >
> > mkconfig: use distro sorts when available
> > https://www.mail-archive.com/grub-devel@gnu.org/msg33357.html
> >
> > I'd like to know more your comments about this as those hooks might
> > still be needed or where to keep distribution's sort ?
>
> The series does, yes - both can't be applied as-is. I'm fine to rebase
> mine, but haven't done it yet. I don't mind adding them back if I need
> to.
I prefer to drop unused code now and add it back when it is needed.
Daniel
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions
2022-05-27 14:56 ` Robbie Harwood
2022-05-27 21:45 ` Daniel Kiper
@ 2022-05-30 13:31 ` Mathieu Desnoyers
1 sibling, 0 replies; 16+ messages in thread
From: Mathieu Desnoyers @ 2022-05-30 13:31 UTC (permalink / raw)
To: Robbie Harwood; +Cc: Michael Chang via Grub-devel, Michael Chang
----- On May 27, 2022, at 10:56 AM, Robbie Harwood rharwood@redhat.com wrote:
> Michael Chang via Grub-devel <grub-devel@gnu.org> writes:
>
>> On Thu, May 26, 2022 at 05:07:11PM -0400, Robbie Harwood wrote:
>>> Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
>>>
>>>> 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>
>>
>> Hm. This seems to contradict your proposed patch to use distro specific
>> sort by hooking into those functions got removed here.
>>
>> mkconfig: use distro sorts when available
>> https://www.mail-archive.com/grub-devel@gnu.org/msg33357.html
>>
>> I'd like to know more your comments about this as those hooks might
>> still be needed or where to keep distribution's sort ?
>
> The series does, yes - both can't be applied as-is. I'm fine to rebase
> mine, but haven't done it yet. I don't mind adding them back if I need
> to.
Please be mindful not to add back the quadratic sorting algorithm as you
do that.
Thanks,
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 16+ messages in thread
* Re: [RFC PATCH v3 1/5] grub-mkconfig linux: Fix quadratic algorithm for sorting menu items
2022-05-26 18:34 ` Mathieu Desnoyers
@ 2022-06-08 18:10 ` Daniel Kiper
0 siblings, 0 replies; 16+ messages in thread
From: Daniel Kiper @ 2022-06-08 18:10 UTC (permalink / raw)
To: Mathieu Desnoyers; +Cc: grub-devel
On Thu, May 26, 2022 at 02:34:41PM -0400, Mathieu Desnoyers wrote:
> ----- On May 26, 2022, at 11:13 AM, Daniel Kiper dkiper@net-space.pl wrote:
> > On Fri, May 20, 2022 at 10:37:37AM -0400, Mathieu Desnoyers wrote:
[...]
> > Please hold on with rebase. I am going to push one more patch before
> > your patch series which may potentially conflict with your changes.
>
> OK.
>
> > I will drop you a line when you can do it.
>
> Allright, I'll wait for you to reach out before sending the rebased final
> non-RFC series.
You can go ahead and rebase.
Thanks,
Daniel
^ permalink raw reply [flat|nested] 16+ messages in thread
end of thread, other threads:[~2022-06-08 18:11 UTC | newest]
Thread overview: 16+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-05-20 14:37 [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 1/5] grub-mkconfig linux: " Mathieu Desnoyers
2022-05-26 15:13 ` Daniel Kiper
2022-05-26 18:34 ` Mathieu Desnoyers
2022-06-08 18:10 ` Daniel Kiper
2022-05-20 14:37 ` [RFC PATCH v3 2/5] grub-mkconfig linux_xen: " Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 3/5] grub-mkconfig hurd: " Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 4/5] grub-mkconfig kfreebsd: " Mathieu Desnoyers
2022-05-20 14:37 ` [RFC PATCH v3 5/5] Cleanup: grub-mkconfig_lib: remove unused version comparison functions Mathieu Desnoyers
2022-05-26 21:07 ` Robbie Harwood
2022-05-27 6:07 ` Michael Chang
2022-05-27 14:56 ` Robbie Harwood
2022-05-27 21:45 ` Daniel Kiper
2022-05-30 13:31 ` Mathieu Desnoyers
2022-05-20 16:08 ` [RFC PATCH v3 0/5] grub-mkconfig: Fix quadratic algorithm for sorting menu items Mathieu Desnoyers
2022-05-26 15:24 ` Daniel Kiper
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.