From patchwork Thu Jun 9 18:50:21 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Mathieu Desnoyers X-Patchwork-Id: 12875912 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id 1DC33C433EF for ; Thu, 9 Jun 2022 18:50:51 +0000 (UTC) Received: from list by lists.xenproject.org with outflank-mailman.345661.571336 (Exim 4.92) (envelope-from ) id 1nzNEn-0008Mf-8e; Thu, 09 Jun 2022 18:50:33 +0000 X-Outflank-Mailman: Message body and most headers restored to incoming version Received: by outflank-mailman (output) from mailman id 345661.571336; Thu, 09 Jun 2022 18:50:33 +0000 Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1nzNEn-0008MY-4d; Thu, 09 Jun 2022 18:50:33 +0000 Received: by outflank-mailman (input) for mailman id 345661; Thu, 09 Jun 2022 18:50:32 +0000 Received: from se1-gles-sth1-in.inumbo.com ([159.253.27.254] helo=se1-gles-sth1.inumbo.com) by lists.xenproject.org with esmtp (Exim 4.92) (envelope-from ) id 1nzNEm-0008MS-7d for xen-devel@lists.xenproject.org; Thu, 09 Jun 2022 18:50:32 +0000 Received: from mail.efficios.com (mail.efficios.com [167.114.26.124]) by se1-gles-sth1.inumbo.com (Halon) with ESMTPS id 08143099-e825-11ec-bd2c-47488cf2e6aa; Thu, 09 Jun 2022 20:50:30 +0200 (CEST) Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id 5A8574128F6; Thu, 9 Jun 2022 14:50:28 -0400 (EDT) Received: from mail.efficios.com ([127.0.0.1]) by localhost (mail03.efficios.com [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id Cdaco1Q1VkzD; Thu, 9 Jun 2022 14:50:28 -0400 (EDT) Received: from localhost (localhost [127.0.0.1]) by mail.efficios.com (Postfix) with ESMTP id E265B412B3B; Thu, 9 Jun 2022 14:50:27 -0400 (EDT) Received: from mail.efficios.com ([127.0.0.1]) by localhost (mail03.efficios.com [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id 0jctropM8IS9; Thu, 9 Jun 2022 14:50:27 -0400 (EDT) Received: from thinkos.internal.efficios.com (192-222-180-24.qc.cable.ebox.net [192.222.180.24]) by mail.efficios.com (Postfix) with ESMTPSA id 7D691412C30; Thu, 9 Jun 2022 14:50:27 -0400 (EDT) X-BeenThere: xen-devel@lists.xenproject.org List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Errors-To: xen-devel-bounces@lists.xenproject.org Precedence: list Sender: "Xen-devel" X-Inumbo-ID: 08143099-e825-11ec-bd2c-47488cf2e6aa DKIM-Filter: OpenDKIM Filter v2.10.3 mail.efficios.com E265B412B3B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=default; t=1654800627; bh=X19fc2ZJzlK+2LLBPb6sjkiFfHHu0f+h2vgW4rhOtaM=; h=From:To:Date:Message-Id:MIME-Version; b=ZTchHqWwc67DZj2lqEkw7mDhWZCF5dI334JQ9WQlbx3E8zey19t5KaAxuWvWeRxvB paszcqumr+nQbv2QiVrZDFIRsvAl7TdGarogQ7JV+GkgLu413bQ/JookNa38SP4q65 AQXmXUbk/9VotSgg26bOXp7CmkZhlUAydI3UAG65rZMb8pwO06F9osklhFUYTtRHaZ pKF+Z/h+6BZAzm+jT2nJ3a8dxlnS/LDn+QHNJqP8cUvYd5PsxukDe+nuM8Ptd6S1XD GB2KVT1dKcnxe2ZPxfDcyTlNMQMYFeLKPDsLmxwpGxnAq88Xoh2QnA18vshJu3N/bI bDda1Q51GzK4w== X-Virus-Scanned: amavisd-new at efficios.com From: Mathieu Desnoyers To: grub-devel@gnu.org, Daniel Kiper Cc: Mathieu Desnoyers , xen-devel@lists.xenproject.org Subject: [PATCH v5 2/5] grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu items Date: Thu, 9 Jun 2022 14:50:21 -0400 Message-Id: <20220609185024.447922-3-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: <20220609185024.447922-1-mathieu.desnoyers@efficios.com> References: <20220609185024.447922-1-mathieu.desnoyers@efficios.com> MIME-Version: 1.0 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 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