From: "Laszlo Ersek" <lersek@redhat.com>
To: "Philippe Mathieu-Daudé" <philmd@redhat.com>, devel@edk2.groups.io
Cc: Ray Ni <ray.ni@intel.com>, Zhichao Gao <zhichao.gao@intel.com>
Subject: Re: [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList()
Date: Thu, 14 Jan 2021 15:19:01 +0100 [thread overview]
Message-ID: <f6496b67-e04d-c0ee-a126-33854c7df77e@redhat.com> (raw)
In-Reply-To: <543264c0-1709-073b-e82b-8dcdf412213f@redhat.com>
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 <DIR> r 0 .
>>> 01/01/1970 01:00 <DIR> r 0 ..
>>> 12/22/2020 17:53 <DIR> 4,096 AARCH64
>>> 12/22/2020 17:53 <DIR> 4,096 IA32
>>> 12/22/2020 17:53 <DIR> 4,096 X64
>>> 0 File(s) 0 bytes
>>> 5 Dir(s)
>>> Directory of: FS2:\apps\X64\
>>> 01/01/1970 01:00 <DIR> r 0 .
>>> 01/01/1970 01:00 <DIR> 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 <DIR> r 0 .
>>> 01/01/1970 01:00 <DIR> 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 <DIR> r 0 .
>>> 01/01/1970 01:00 <DIR> 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 <DIR> r 0 .
>>> 01/01/1970 01:00 <DIR> r 0 ..
>>> 12/22/2020 17:53 <DIR> 4,096 AARCH64
>>> 12/22/2020 17:53 <DIR> 4,096 IA32
>>> 12/22/2020 17:53 <DIR> 4,096 X64
>>> 0 File(s) 0 bytes
>>> 5 Dir(s)
>>> Directory of: FS2:\apps\AARCH64\
>>> 01/01/1970 01:00 <DIR> r 0 .
>>> 01/01/1970 01:00 <DIR> 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 <DIR> r 0 .
>>> 01/01/1970 01:00 <DIR> 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 <DIR> r 0 .
>>> 01/01/1970 01:00 <DIR> 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é <philmd@redhat.com>
>> Cc: Ray Ni <ray.ni@intel.com>
>> Cc: Zhichao Gao <zhichao.gao@intel.com>
>> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
>> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
>> Reviewed-by: Zhichao Gao <zhichao.gao@intel.com>
>> ---
>>
>> 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 <philmd@redhat.com>
>
Thank you Phil for reviewing the series!
Laszlo
next prev parent reply other threads:[~2021-01-14 14:19 UTC|newest]
Thread overview: 31+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-01-13 8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
2021-01-13 8:54 ` [PATCH v2 01/10] ShellPkg/Comp: add file buffering Laszlo Ersek
2021-01-13 18:42 ` Philippe Mathieu-Daudé
2021-01-13 8:54 ` [PATCH v2 02/10] OvmfPkg: raise PcdShellFileOperationSize to 128KB Laszlo Ersek
2021-01-15 9:34 ` Philippe Mathieu-Daudé
2021-01-15 10:09 ` Laszlo Ersek
2021-01-15 15:58 ` Philippe Mathieu-Daudé
2021-01-15 18:22 ` Laszlo Ersek
2021-01-13 8:54 ` [PATCH v2 03/10] ArmVirtPkg: " Laszlo Ersek
2021-01-15 15:59 ` Philippe Mathieu-Daudé
2021-01-15 19:03 ` [edk2-devel] " Laszlo Ersek
2021-01-13 8:54 ` [PATCH v2 04/10] EmulatorPkg: add OrderedCollectionLib class resolution Laszlo Ersek
2021-01-13 13:20 ` Philippe Mathieu-Daudé
2021-01-18 16:48 ` [edk2-devel] " Laszlo Ersek
2021-01-19 7:55 ` 回复: " gaoliming
2021-01-13 8:54 ` [PATCH v2 05/10] UefiPayloadPkg: " Laszlo Ersek
2021-01-13 13:20 ` Philippe Mathieu-Daudé
2021-01-18 16:48 ` [edk2-devel] " Laszlo Ersek
2021-01-19 4:29 ` Guo Dong
2021-01-13 8:54 ` [PATCH v2 06/10] ShellPkg/ShellCommandLib: add ShellSortFileList() Laszlo Ersek
2021-01-13 13:19 ` Philippe Mathieu-Daudé
2021-01-13 8:54 ` [PATCH v2 07/10] ShellPkg/Ls: sort output by FileName in non-SFO mode Laszlo Ersek
2021-01-13 13:15 ` Philippe Mathieu-Daudé
2021-01-13 8:54 ` [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList() Laszlo Ersek
2021-01-13 13:14 ` Philippe Mathieu-Daudé
2021-01-14 14:19 ` Laszlo Ersek [this message]
2021-01-13 8:54 ` [PATCH v2 09/10] OvmfPkg: disable list length checks in NOOPT and DEBUG builds Laszlo Ersek
2021-01-15 9:30 ` Philippe Mathieu-Daudé
2021-01-13 8:54 ` [PATCH v2 10/10] ArmVirtPkg: " Laszlo Ersek
2021-01-15 9:31 ` Philippe Mathieu-Daudé
2021-01-19 18:39 ` [edk2-devel] [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=f6496b67-e04d-c0ee-a126-33854c7df77e@redhat.com \
--to=devel@edk2.groups.io \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox