From: "Laszlo Ersek" <lersek@redhat.com>
To: devel@edk2.groups.io
Cc: "Philippe Mathieu-Daudé" <philmd@redhat.com>,
"Ray Ni" <ray.ni@intel.com>,
"Zhichao Gao" <zhichao.gao@intel.com>
Subject: [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList()
Date: Wed, 13 Jan 2021 09:54:51 +0100 [thread overview]
Message-ID: <20210113085453.10168-9-lersek@redhat.com> (raw)
In-Reply-To: <20210113085453.10168-1-lersek@redhat.com>
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(+)
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 8:55 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 ` Laszlo Ersek [this message]
2021-01-13 13:14 ` [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList() Philippe Mathieu-Daudé
2021-01-14 14:19 ` Laszlo Ersek
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=20210113085453.10168-9-lersek@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