From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [63.128.21.124]) by mx.groups.io with SMTP id smtpd.web11.2011.1610633951074701099 for ; Thu, 14 Jan 2021 06:19:12 -0800 Authentication-Results: mx.groups.io; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=aG66Hr8L; spf=pass (domain: redhat.com, ip: 63.128.21.124, mailfrom: lersek@redhat.com) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1610633950; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=Ez0b+K1hq3uu3GW4erUR/ofT/NJpdA3VBEh7cmR/Jek=; b=aG66Hr8LZBPu8QdvJoArJBJuwajb+HVRfCaI3CrcgDdbPFSnx4dnSd7D/C84gG5hlAlLn4 M56JrDCDkqHqVvmEMa9wrL5mjhXumKzDVpABjEMzRgLJO7gJGqaBu1reZeuW/lxXJK6Aa4 LSSFXlghQ2coc6zC+UhctpILLh3Oa2A= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-358-E_vgAZ3QOoaqqxbbNt-8cQ-1; Thu, 14 Jan 2021 09:19:04 -0500 X-MC-Unique: E_vgAZ3QOoaqqxbbNt-8cQ-1 Received: from smtp.corp.redhat.com (int-mx08.intmail.prod.int.phx2.redhat.com [10.5.11.23]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 86CE1107ACF9; Thu, 14 Jan 2021 14:19:03 +0000 (UTC) Received: from lacos-laptop-7.usersys.redhat.com (ovpn-114-110.ams2.redhat.com [10.36.114.110]) by smtp.corp.redhat.com (Postfix) with ESMTP id 4810819C71; Thu, 14 Jan 2021 14:19:02 +0000 (UTC) Subject: Re: [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList() To: =?UTF-8?Q?Philippe_Mathieu-Daud=c3=a9?= , devel@edk2.groups.io Cc: Ray Ni , Zhichao Gao References: <20210113085453.10168-1-lersek@redhat.com> <20210113085453.10168-9-lersek@redhat.com> <543264c0-1709-073b-e82b-8dcdf412213f@redhat.com> From: "Laszlo Ersek" Message-ID: Date: Thu, 14 Jan 2021 15:19:01 +0100 MIME-Version: 1.0 In-Reply-To: <543264c0-1709-073b-e82b-8dcdf412213f@redhat.com> X-Scanned-By: MIMEDefang 2.84 on 10.5.11.23 Authentication-Results: relay.mimecast.com; auth=pass smtp.auth=CUSA124A263 smtp.mailfrom=lersek@redhat.com X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit On 01/13/21 14:14, Philippe Mathieu-Daudé wrote: > On 1/13/21 9:54 AM, Laszlo Ersek wrote: >> The current implementation of EfiShellRemoveDupInFileList(): >> - has quadratic time complexity, as a disadvantage, and >> - needs no dynamic memory, as an advantage. >> >> Because the UEFI Shell Spec requires >> EFI_SHELL_PROTOCOL.RemoveDupInFileList() to succeed at all times, keep the >> current method as a fallback (it cannot fail due to needing no dynamic >> memory). >> >> However, as a higher priority option, call the new ShellSortFileList() >> function at first, separating out and releasing duplicates. >> (ShellSortFileList() can fail due to EFI_OUT_OF_RESOURCES.) >> >> Beyond improving the runtime of EfiShellRemoveDupInFileList(), this change >> has the extremely desirable effect that the ShellOpenFileMetaArg() >> function in the ShellPkg/Library/UefiShellLib instance will produce file >> lists that are sorted by FullName. >> >> Consequently, when used with wildcards, the ATTRIB, CP, FOR, LOAD, >> LOADPCIROM, LS, MV, RM, TOUCH, TYPE commands will process files in >> FullName order. (LS in recursive mode uses wildcards internally.) >> >> Before: >> >>> FS2:\> dir -r -sfo apps >>> [...] >>> FileInfo,"FS2:\apps\" >>> FileInfo,"FS2:\apps\X64" >>> FileInfo,"FS2:\apps\AARCH64" >>> FileInfo,"FS2:\" >>> FileInfo,"FS2:\apps\IA32" >>> FileInfo,"FS2:\apps\X64\DumpDynPcd.efi" >>> FileInfo,"FS2:\apps\X64\SmiHandlerProfileInfo.efi" >>> FileInfo,"FS2:\apps\X64\" >>> FileInfo,"FS2:\apps\X64\VariableInfo.efi" >>> FileInfo,"FS2:\apps\X64\MemoryProfileInfo.efi" >>> FileInfo,"FS2:\apps\X64\AcpiViewApp.efi" >>> FileInfo,"FS2:\apps\X64\Cpuid.efi" >>> FileInfo,"FS2:\apps\" >>> FileInfo,"FS2:\apps\AARCH64\DumpDynPcd.efi" >>> FileInfo,"FS2:\apps\AARCH64\" >>> FileInfo,"FS2:\apps\AARCH64\VariableInfo.efi" >>> FileInfo,"FS2:\apps\AARCH64\MemoryProfileInfo.efi" >>> FileInfo,"FS2:\apps\AARCH64\AcpiViewApp.efi" >>> FileInfo,"FS2:\apps\" >>> FileInfo,"FS2:\apps\IA32\DumpDynPcd.efi" >>> FileInfo,"FS2:\apps\IA32\SmiHandlerProfileInfo.efi" >>> FileInfo,"FS2:\apps\IA32\" >>> FileInfo,"FS2:\apps\IA32\VariableInfo.efi" >>> FileInfo,"FS2:\apps\IA32\MemoryProfileInfo.efi" >>> FileInfo,"FS2:\apps\IA32\AcpiViewApp.efi" >>> FileInfo,"FS2:\apps\IA32\Cpuid.efi" >>> FileInfo,"FS2:\apps\" >> >> After: >> >>> FS2:\> dir -r -sfo apps >>> [...] >>> FileInfo,"FS2:\" >>> FileInfo,"FS2:\apps\" >>> FileInfo,"FS2:\apps\AARCH64" >>> FileInfo,"FS2:\apps\IA32" >>> FileInfo,"FS2:\apps\X64" >>> FileInfo,"FS2:\apps\" >>> FileInfo,"FS2:\apps\AARCH64\" >>> FileInfo,"FS2:\apps\AARCH64\AcpiViewApp.efi" >>> FileInfo,"FS2:\apps\AARCH64\DumpDynPcd.efi" >>> FileInfo,"FS2:\apps\AARCH64\MemoryProfileInfo.efi" >>> FileInfo,"FS2:\apps\AARCH64\VariableInfo.efi" >>> FileInfo,"FS2:\apps\" >>> FileInfo,"FS2:\apps\IA32\" >>> FileInfo,"FS2:\apps\IA32\AcpiViewApp.efi" >>> FileInfo,"FS2:\apps\IA32\Cpuid.efi" >>> FileInfo,"FS2:\apps\IA32\DumpDynPcd.efi" >>> FileInfo,"FS2:\apps\IA32\MemoryProfileInfo.efi" >>> FileInfo,"FS2:\apps\IA32\SmiHandlerProfileInfo.efi" >>> FileInfo,"FS2:\apps\IA32\VariableInfo.efi" >>> FileInfo,"FS2:\apps\" >>> FileInfo,"FS2:\apps\X64\" >>> FileInfo,"FS2:\apps\X64\AcpiViewApp.efi" >>> FileInfo,"FS2:\apps\X64\Cpuid.efi" >>> FileInfo,"FS2:\apps\X64\DumpDynPcd.efi" >>> FileInfo,"FS2:\apps\X64\MemoryProfileInfo.efi" >>> FileInfo,"FS2:\apps\X64\SmiHandlerProfileInfo.efi" >>> FileInfo,"FS2:\apps\X64\VariableInfo.efi" >> >> Regarding LS in non-SFO mode, the stability of ShellSortFileList() shows. >> The ShellSortFileList() call added to LS in the previous patch re-sorts >> the output of ShellOpenFileMetaArg(); and so this patch improves the >> ordering between identical FileNames: >> >> Before: >> >>> FS2:\> dir -r apps >>> Directory of: FS2:\apps\ >>> 01/01/1970 01:00 r 0 . >>> 01/01/1970 01:00 r 0 .. >>> 12/22/2020 17:53 4,096 AARCH64 >>> 12/22/2020 17:53 4,096 IA32 >>> 12/22/2020 17:53 4,096 X64 >>> 0 File(s) 0 bytes >>> 5 Dir(s) >>> Directory of: FS2:\apps\X64\ >>> 01/01/1970 01:00 r 0 . >>> 01/01/1970 01:00 r 0 .. >>> 12/22/2020 17:53 126,656 AcpiViewApp.efi >>> 12/22/2020 17:53 38,784 Cpuid.efi >>> 12/22/2020 17:52 18,752 DumpDynPcd.efi >>> 12/22/2020 17:52 26,304 MemoryProfileInfo.efi >>> 12/22/2020 17:52 34,240 SmiHandlerProfileInfo.efi >>> 12/22/2020 17:52 11,456 VariableInfo.efi >>> 6 File(s) 256,192 bytes >>> 2 Dir(s) >>> Directory of: FS2:\apps\AARCH64\ >>> 01/01/1970 01:00 r 0 . >>> 01/01/1970 01:00 r 0 .. >>> 12/22/2020 17:53 139,264 AcpiViewApp.efi >>> 12/22/2020 17:52 32,768 DumpDynPcd.efi >>> 12/22/2020 17:52 40,960 MemoryProfileInfo.efi >>> 12/22/2020 17:52 20,480 VariableInfo.efi >>> 4 File(s) 233,472 bytes >>> 2 Dir(s) >>> Directory of: FS2:\apps\IA32\ >>> 01/01/1970 01:00 r 0 . >>> 01/01/1970 01:00 r 0 .. >>> 12/22/2020 17:53 105,536 AcpiViewApp.efi >>> 12/22/2020 17:53 36,096 Cpuid.efi >>> 12/22/2020 17:52 17,344 DumpDynPcd.efi >>> 12/22/2020 17:52 24,192 MemoryProfileInfo.efi >>> 12/22/2020 17:52 30,720 SmiHandlerProfileInfo.efi >>> 12/22/2020 17:52 10,880 VariableInfo.efi >>> 6 File(s) 224,768 bytes >>> 2 Dir(s) >>> >>> FS2:\> dir apps\*\*.efi >>> Directory of: FS2:\apps\*\ >>> 12/22/2020 17:53 126,656 AcpiViewApp.efi >>> 12/22/2020 17:53 139,264 AcpiViewApp.efi >>> 12/22/2020 17:53 105,536 AcpiViewApp.efi >>> 12/22/2020 17:53 38,784 Cpuid.efi >>> 12/22/2020 17:53 36,096 Cpuid.efi >>> 12/22/2020 17:52 18,752 DumpDynPcd.efi >>> 12/22/2020 17:52 32,768 DumpDynPcd.efi >>> 12/22/2020 17:52 17,344 DumpDynPcd.efi >>> 12/22/2020 17:52 26,304 MemoryProfileInfo.efi >>> 12/22/2020 17:52 40,960 MemoryProfileInfo.efi >>> 12/22/2020 17:52 24,192 MemoryProfileInfo.efi >>> 12/22/2020 17:52 34,240 SmiHandlerProfileInfo.efi >>> 12/22/2020 17:52 30,720 SmiHandlerProfileInfo.efi >>> 12/22/2020 17:52 11,456 VariableInfo.efi >>> 12/22/2020 17:52 20,480 VariableInfo.efi >>> 12/22/2020 17:52 10,880 VariableInfo.efi >>> 16 File(s) 714,432 bytes >>> 0 Dir(s) >> >> After: >> >>> FS2:\> dir -r apps >>> Directory of: FS2:\apps\ >>> 01/01/1970 01:00 r 0 . >>> 01/01/1970 01:00 r 0 .. >>> 12/22/2020 17:53 4,096 AARCH64 >>> 12/22/2020 17:53 4,096 IA32 >>> 12/22/2020 17:53 4,096 X64 >>> 0 File(s) 0 bytes >>> 5 Dir(s) >>> Directory of: FS2:\apps\AARCH64\ >>> 01/01/1970 01:00 r 0 . >>> 01/01/1970 01:00 r 0 .. >>> 12/22/2020 17:53 139,264 AcpiViewApp.efi >>> 12/22/2020 17:52 32,768 DumpDynPcd.efi >>> 12/22/2020 17:52 40,960 MemoryProfileInfo.efi >>> 12/22/2020 17:52 20,480 VariableInfo.efi >>> 4 File(s) 233,472 bytes >>> 2 Dir(s) >>> Directory of: FS2:\apps\IA32\ >>> 01/01/1970 01:00 r 0 . >>> 01/01/1970 01:00 r 0 .. >>> 12/22/2020 17:53 105,536 AcpiViewApp.efi >>> 12/22/2020 17:53 36,096 Cpuid.efi >>> 12/22/2020 17:52 17,344 DumpDynPcd.efi >>> 12/22/2020 17:52 24,192 MemoryProfileInfo.efi >>> 12/22/2020 17:52 30,720 SmiHandlerProfileInfo.efi >>> 12/22/2020 17:52 10,880 VariableInfo.efi >>> 6 File(s) 224,768 bytes >>> 2 Dir(s) >>> Directory of: FS2:\apps\X64\ >>> 01/01/1970 01:00 r 0 . >>> 01/01/1970 01:00 r 0 .. >>> 12/22/2020 17:53 126,656 AcpiViewApp.efi >>> 12/22/2020 17:53 38,784 Cpuid.efi >>> 12/22/2020 17:52 18,752 DumpDynPcd.efi >>> 12/22/2020 17:52 26,304 MemoryProfileInfo.efi >>> 12/22/2020 17:52 34,240 SmiHandlerProfileInfo.efi >>> 12/22/2020 17:52 11,456 VariableInfo.efi >>> 6 File(s) 256,192 bytes >>> 2 Dir(s) >>> >>> FS2:\> dir apps\*\*.efi >>> Directory of: FS2:\apps\*\ >>> 12/22/2020 17:53 139,264 AcpiViewApp.efi >>> 12/22/2020 17:53 105,536 AcpiViewApp.efi >>> 12/22/2020 17:53 126,656 AcpiViewApp.efi >>> 12/22/2020 17:53 36,096 Cpuid.efi >>> 12/22/2020 17:53 38,784 Cpuid.efi >>> 12/22/2020 17:52 32,768 DumpDynPcd.efi >>> 12/22/2020 17:52 17,344 DumpDynPcd.efi >>> 12/22/2020 17:52 18,752 DumpDynPcd.efi >>> 12/22/2020 17:52 40,960 MemoryProfileInfo.efi >>> 12/22/2020 17:52 24,192 MemoryProfileInfo.efi >>> 12/22/2020 17:52 26,304 MemoryProfileInfo.efi >>> 12/22/2020 17:52 30,720 SmiHandlerProfileInfo.efi >>> 12/22/2020 17:52 34,240 SmiHandlerProfileInfo.efi >>> 12/22/2020 17:52 20,480 VariableInfo.efi >>> 12/22/2020 17:52 10,880 VariableInfo.efi >>> 12/22/2020 17:52 11,456 VariableInfo.efi >>> 16 File(s) 714,432 bytes >>> 0 Dir(s) >> >> Cc: Philippe Mathieu-Daudé >> Cc: Ray Ni >> Cc: Zhichao Gao >> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151 >> Signed-off-by: Laszlo Ersek >> Reviewed-by: Zhichao Gao >> --- >> >> Notes: >> v2: >> - no changes >> - pick up Zhichao's R-b >> >> ShellPkg/Application/Shell/ShellProtocol.c | 16 ++++++++++++++++ >> 1 file changed, 16 insertions(+) > > Reviewed-by: Philippe Mathieu-Daude > Thank you Phil for reviewing the series! Laszlo