From: "Gao, Zhichao" <zhichao.gao@intel.com>
To: Laszlo Ersek <lersek@redhat.com>,
edk2-devel-groups-io <devel@edk2.groups.io>
Cc: "Philippe Mathieu-Daudé" <philmd@redhat.com>,
"Ni, Ray" <ray.ni@intel.com>
Subject: Re: [PATCH 6/8] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList()
Date: Wed, 13 Jan 2021 03:04:26 +0000 [thread overview]
Message-ID: <MWHPR11MB16478DF6CD09FE4049ACDC43F6A90@MWHPR11MB1647.namprd11.prod.outlook.com> (raw)
In-Reply-To: <20210104154235.31785-7-lersek@redhat.com>
Reviewed-by: Zhichao Gao <zhichao.gao@intel.com>
Thanks,
Zhichao
> -----Original Message-----
> From: Laszlo Ersek <lersek@redhat.com>
> Sent: Monday, January 4, 2021 11:43 PM
> To: edk2-devel-groups-io <devel@edk2.groups.io>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>; Ni, Ray <ray.ni@intel.com>;
> Gao, Zhichao <zhichao.gao@intel.com>
> Subject: [PATCH 6/8] ShellPkg/ShellProtocol: sort files by FullName in
> RemoveDupInFileList()
>
> 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>
> ---
> ShellPkg/Application/Shell/ShellProtocol.c | 16 ++++++++++++++++
> 1 file changed, 16 insertions(+)
>
> diff --git a/ShellPkg/Application/Shell/ShellProtocol.c
> b/ShellPkg/Application/Shell/ShellProtocol.c
> index 4e639fe35e4f..e79c39058b3e 100644
> --- a/ShellPkg/Application/Shell/ShellProtocol.c
> +++ b/ShellPkg/Application/Shell/ShellProtocol.c
> @@ -1855,6 +1855,8 @@ EfiShellRemoveDupInFileList(
> IN EFI_SHELL_FILE_INFO **FileList
> )
> {
> + EFI_STATUS Status;
> + EFI_SHELL_FILE_INFO *Duplicates;
> EFI_SHELL_FILE_INFO *ShellFileListItem;
> EFI_SHELL_FILE_INFO *ShellFileListItem2;
> EFI_SHELL_FILE_INFO *TempNode;
> @@ -1862,6 +1864,20 @@ EfiShellRemoveDupInFileList(
> if (FileList == NULL || *FileList == NULL) {
> return (EFI_INVALID_PARAMETER);
> }
> +
> + Status = ShellSortFileList (
> + FileList,
> + &Duplicates,
> + ShellSortFileListByFullName
> + );
> + if (!EFI_ERROR (Status)) {
> + EfiShellFreeFileList (&Duplicates);
> + return EFI_SUCCESS;
> + }
> + //
> + // Fall back to the slow method that needs no extra memory, and so
> + cannot // fail.
> + //
> for ( ShellFileListItem = (EFI_SHELL_FILE_INFO*)GetFirstNode(&(*FileList)->Link)
> ; !IsNull(&(*FileList)->Link, &ShellFileListItem->Link)
> ; ShellFileListItem = (EFI_SHELL_FILE_INFO*)GetNextNode(&(*FileList)->Link,
> &ShellFileListItem->Link)
> --
> 2.19.1.3.g30247aa5d201
>
next prev parent reply other threads:[~2021-01-13 3:04 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-01-04 15:42 [PATCH 0/8] ShellPkg, ArmVirtPkg, OvmfPkg: shell usability improvements Laszlo Ersek
2021-01-04 15:42 ` [PATCH 1/8] ShellPkg/Comp: add file buffering Laszlo Ersek
2021-01-11 1:24 ` Gao, Zhichao
2021-01-04 15:42 ` [PATCH 2/8] OvmfPkg: raise PcdShellFileOperationSize to 128KB Laszlo Ersek
2021-01-04 15:42 ` [PATCH 3/8] ArmVirtPkg: " Laszlo Ersek
2021-01-04 15:42 ` [PATCH 4/8] ShellPkg/ShellCommandLib: add ShellSortFileList() Laszlo Ersek
2021-01-13 3:03 ` Gao, Zhichao
2021-01-04 15:42 ` [PATCH 5/8] ShellPkg/Ls: sort output by FileName in non-SFO mode Laszlo Ersek
2021-01-13 3:04 ` Gao, Zhichao
2021-01-04 15:42 ` [PATCH 6/8] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList() Laszlo Ersek
2021-01-13 3:04 ` Gao, Zhichao [this message]
2021-01-04 15:42 ` [PATCH 7/8] OvmfPkg: disable list length checks in NOOPT and DEBUG builds Laszlo Ersek
2021-01-04 15:42 ` [PATCH 8/8] ArmVirtPkg: " Laszlo Ersek
2021-01-04 16:12 ` [PATCH 0/8] ShellPkg, ArmVirtPkg, OvmfPkg: shell usability improvements Ard Biesheuvel
2021-01-08 8:34 ` [edk2-devel] " 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=MWHPR11MB16478DF6CD09FE4049ACDC43F6A90@MWHPR11MB1647.namprd11.prod.outlook.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