[edk2-devel] [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList()
Philippe Mathieu-Daudé
philmd at redhat.com
Wed Jan 13 13:14:49 UTC 2021
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 at redhat.com>
> Cc: Ray Ni <ray.ni at intel.com>
> Cc: Zhichao Gao <zhichao.gao at intel.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
> Signed-off-by: Laszlo Ersek <lersek at redhat.com>
> Reviewed-by: Zhichao Gao <zhichao.gao at 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 at redhat.com>
-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#70250): https://edk2.groups.io/g/devel/message/70250
Mute This Topic: https://groups.io/mt/79646586/1813853
Group Owner: devel+owner at edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [edk2-devel-archive at redhat.com]
-=-=-=-=-=-=-=-=-=-=-=-
More information about the edk2-devel-archive
mailing list