[PATCH v2 00/10] multiple packages: shell usability improvements

public inbox for devel@edk2.groups.io
 help / color / mirror / Atom feed

* [PATCH v2 00/10] multiple packages: shell usability improvements
@ 2021-01-13  8:54 Laszlo Ersek
  2021-01-13  8:54 ` [PATCH v2 01/10] ShellPkg/Comp: add file buffering Laszlo Ersek
                   ` (10 more replies)
  0 siblings, 11 replies; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel
  Cc: Andrew Fish, Anthony Perard, Ard Biesheuvel, Benjamin You,
	Guo Dong, Jordan Justen, Julien Grall, Leif Lindholm, Maurice Ma,
	Peter Grehan, Philippe Mathieu-Daudé, Ray Ni, Rebecca Cran,
	Sami Mujawar, Zhichao Gao

Repo:   https://pagure.io/lersek/edk2.git
Branch: shell_usability_improvements_v2

Changes in v2:

- no code changes in any of the v1 patches,

- pick up v1 feedback tags from Ard and Zhichao,

- add two new patches, for resolving OrderedCollectionLib in EmulatorPkg
  and UefiPayloadPkg.

Additionally, I have posted the following pre-requisite series, for
edk2-platforms:

  [edk2-devel] [edk2-platforms PATCH 0/3]
  add OrderedCollectionLib class resolution

  https://www.redhat.com/archives/edk2-devel-archive/2021-January/msg00694.html
  https://edk2.groups.io/g/devel/message/70210
  Message-Id: <20210113082843.9095-1-lersek@redhat.com>

The v1 posting was at:

  https://edk2.groups.io/g/devel/message/69590
  https://www.redhat.com/archives/edk2-devel-archive/2021-January/msg00070.html
  Message-Id: <20210104154235.31785-1-lersek@redhat.com>

v1 blurb:

This series addresses various usability shortcomings that I've recently
run into, while working with large directory trees on FAT and/or
virtio-fs in the UEFI shell.

* add file buffering to the COMP command
  https://bugzilla.tianocore.org/show_bug.cgi?id=3123

* ArmVirtPkg, OvmfPkg: set PcdShellFileOperationSize to 0x20000
  https://bugzilla.tianocore.org/show_bug.cgi?id=3125

* Shell: pathname / filename sorting
  https://bugzilla.tianocore.org/show_bug.cgi?id=3151

* ArmVirtPkg, OvmfPkg: disable list length checks in NOOPT and DEBUG
  builds
  https://bugzilla.tianocore.org/show_bug.cgi?id=3152

Beyond testing the series locally, I've also heavily subjected it to
local CI runs, including ECC (relevant for ShellPkg).

Cc: Andrew Fish <afish@apple.com>
Cc: Anthony Perard <anthony.perard@citrix.com>
Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
Cc: Benjamin You <benjamin.you@intel.com>
Cc: Guo Dong <guo.dong@intel.com>
Cc: Jordan Justen <jordan.l.justen@intel.com>
Cc: Julien Grall <julien@xen.org>
Cc: Leif Lindholm <leif@nuviainc.com>
Cc: Maurice Ma <maurice.ma@intel.com>
Cc: Peter Grehan <grehan@freebsd.org>
Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
Cc: Ray Ni <ray.ni@intel.com>
Cc: Rebecca Cran <rebecca@bsdio.com>
Cc: Sami Mujawar <sami.mujawar@arm.com>
Cc: Zhichao Gao <zhichao.gao@intel.com>

Thanks
Laszlo

Laszlo Ersek (10):
  ShellPkg/Comp: add file buffering
  OvmfPkg: raise PcdShellFileOperationSize to 128KB
  ArmVirtPkg: raise PcdShellFileOperationSize to 128KB
  EmulatorPkg: add OrderedCollectionLib class resolution
  UefiPayloadPkg: add OrderedCollectionLib class resolution
  ShellPkg/ShellCommandLib: add ShellSortFileList()
  ShellPkg/Ls: sort output by FileName in non-SFO mode
  ShellPkg/ShellProtocol: sort files by FullName in
    RemoveDupInFileList()
  OvmfPkg: disable list length checks in NOOPT and DEBUG builds
  ArmVirtPkg: disable list length checks in NOOPT and DEBUG builds

 ArmVirtPkg/ArmVirt.dsc.inc                                                 |   2 +-
 ArmVirtPkg/ArmVirtQemu.dsc                                                 |   1 +
 ArmVirtPkg/ArmVirtQemuKernel.dsc                                           |   1 +
 EmulatorPkg/EmulatorPkg.dsc                                                |   1 +
 OvmfPkg/AmdSev/AmdSevX64.dsc                                               |   1 +
 OvmfPkg/Bhyve/BhyveX64.dsc                                                 |   1 +
 OvmfPkg/OvmfPkgIa32.dsc                                                    |   3 +
 OvmfPkg/OvmfPkgIa32X64.dsc                                                 |   3 +
 OvmfPkg/OvmfPkgX64.dsc                                                     |   3 +
 OvmfPkg/OvmfXen.dsc                                                        |   1 +
 ShellPkg/Application/Shell/ShellProtocol.c                                 |  16 +
 ShellPkg/Include/Library/ShellCommandLib.h                                 |  81 +++++
 ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c                 | 312 ++++++++++++++++++++
 ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h                 |  19 ++
 ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf               |   1 +
 ShellPkg/Library/UefiShellDebug1CommandsLib/Comp.c                         | 127 +++++++-
 ShellPkg/Library/UefiShellDebug1CommandsLib/UefiShellDebug1CommandsLib.inf |   1 +
 ShellPkg/Library/UefiShellLevel2CommandsLib/Ls.c                           |  14 +
 ShellPkg/ShellPkg.dsc                                                      |   1 +
 UefiPayloadPkg/UefiPayloadPkg.dsc                                          |   1 +
 20 files changed, 586 insertions(+), 4 deletions(-)


base-commit: ebfe2d3eb5ac7fd92d74011edb31303a181920c7
-- 
2.19.1.3.g30247aa5d201


^ permalink raw reply	[flat|nested] 31+ messages in thread

* [PATCH v2 01/10] ShellPkg/Comp: add file buffering
  2021-01-13  8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
@ 2021-01-13  8:54 ` 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
                   ` (9 subsequent siblings)
  10 siblings, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel; +Cc: Philippe Mathieu-Daudé, Ray Ni, Zhichao Gao

The COMP shell command compares two files byte for byte. In order to
retrieve the bytes to compare, it currently invokes
gEfiShellProtocol->ReadFile() on both files, using a single-byte buffer
every time. This is very inefficient; the underlying
EFI_FILE_PROTOCOL.Read() function may be costly.

Read both file operands in chunks of "PcdShellFileOperationSize" bytes.
Draw bytes for comparison from the internal read-ahead buffers.

Some ad-hoc measurements on my laptop, using OVMF, and the 4KB default of
"PcdShellFileOperationSize":

- When comparing two identical 1MB files that are served by EnhancedFatDxe
  on top of VirtioScsiDxe, this patch brings no noticeable improvement;
  the comparison completes in <1s both before and after.

- When comparing two identical 1MB files served by VirtioFsDxe, the
  comparison time improves from 2 minutes 25 seconds to <1s.

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=3123
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/Library/UefiShellDebug1CommandsLib/UefiShellDebug1CommandsLib.inf |   1 +
 ShellPkg/Library/UefiShellDebug1CommandsLib/Comp.c                         | 127 +++++++++++++++++++-
 2 files changed, 125 insertions(+), 3 deletions(-)

diff --git a/ShellPkg/Library/UefiShellDebug1CommandsLib/UefiShellDebug1CommandsLib.inf b/ShellPkg/Library/UefiShellDebug1CommandsLib/UefiShellDebug1CommandsLib.inf
index ed94477a0642..74ad5facf6b1 100644
--- a/ShellPkg/Library/UefiShellDebug1CommandsLib/UefiShellDebug1CommandsLib.inf
+++ b/ShellPkg/Library/UefiShellDebug1CommandsLib/UefiShellDebug1CommandsLib.inf
@@ -113,6 +113,7 @@ [LibraryClasses]
   BcfgCommandLib
 
 [Pcd]
+  gEfiShellPkgTokenSpaceGuid.PcdShellFileOperationSize        ## CONSUMES
   gEfiShellPkgTokenSpaceGuid.PcdShellProfileMask              ## CONSUMES
 
 [Protocols]
diff --git a/ShellPkg/Library/UefiShellDebug1CommandsLib/Comp.c b/ShellPkg/Library/UefiShellDebug1CommandsLib/Comp.c
index 0a5d13f01c7b..0df0b3149369 100644
--- a/ShellPkg/Library/UefiShellDebug1CommandsLib/Comp.c
+++ b/ShellPkg/Library/UefiShellDebug1CommandsLib/Comp.c
@@ -21,6 +21,16 @@ typedef enum {
   InPrevDiffPoint
 } READ_STATUS;
 
+//
+// Buffer type, for reading both file operands in chunks.
+//
+typedef struct {
+  UINT8 *Data;     // dynamically allocated buffer
+  UINTN Allocated; // the allocated size of Data
+  UINTN Next;      // next position in Data to fetch a byte at
+  UINTN Left;      // number of bytes left in Data for fetching at Next
+} FILE_BUFFER;
+
 /**
   Function to print differnt point data.
 
@@ -76,6 +86,106 @@ PrintDifferentPoint(
   ShellPrintEx (-1, -1, L"*\r\n");
 }
 
+/**
+  Initialize a FILE_BUFFER.
+
+  @param[out] FileBuffer  The FILE_BUFFER to initialize. On return, the caller
+                          is responsible for checking FileBuffer->Data: if
+                          FileBuffer->Data is NULL on output, then memory
+                          allocation failed.
+**/
+STATIC
+VOID
+FileBufferInit (
+  OUT FILE_BUFFER *FileBuffer
+  )
+{
+  FileBuffer->Allocated = PcdGet32 (PcdShellFileOperationSize);
+  FileBuffer->Data      = AllocatePool (FileBuffer->Allocated);
+  FileBuffer->Left      = 0;
+}
+
+/**
+  Uninitialize a FILE_BUFFER.
+
+  @param[in,out] FileBuffer  The FILE_BUFFER to uninitialize. The caller is
+                             responsible for making sure FileBuffer was first
+                             initialized with FileBufferInit(), successfully or
+                             unsuccessfully.
+**/
+STATIC
+VOID
+FileBufferUninit (
+  IN OUT FILE_BUFFER *FileBuffer
+  )
+{
+  SHELL_FREE_NON_NULL (FileBuffer->Data);
+}
+
+/**
+  Read a byte from a SHELL_FILE_HANDLE, buffered with a FILE_BUFFER.
+
+  @param[in] FileHandle      The SHELL_FILE_HANDLE to replenish FileBuffer
+                             from, if needed.
+
+  @param[in,out] FileBuffer  The FILE_BUFFER to read a byte from. If FileBuffer
+                             is empty on entry, then FileBuffer is refilled
+                             from FileHandle, before outputting a byte from
+                             FileBuffer to Byte. The caller is responsible for
+                             ensuring that FileBuffer was successfully
+                             initialized with FileBufferInit().
+
+  @param[out] BytesRead      On successful return, BytesRead is set to 1 if the
+                             next byte from FileBuffer has been stored to Byte.
+                             On successful return, BytesRead is set to 0 if
+                             FileBuffer is empty, and FileHandle is at EOF.
+                             When an error is returned, BytesRead is not set.
+
+  @param[out] Byte           On output, the next byte from FileBuffer. Only set
+                             if (a) EFI_SUCCESS is returned and (b) BytesRead
+                             is set to 1 on output.
+
+  @retval EFI_SUCCESS  BytesRead has been set to 0 or 1. In the latter case,
+                       Byte has been set as well.
+
+  @return              Error codes propagated from
+                       gEfiShellProtocol->ReadFile().
+**/
+STATIC
+EFI_STATUS
+FileBufferReadByte (
+  IN     SHELL_FILE_HANDLE FileHandle,
+  IN OUT FILE_BUFFER       *FileBuffer,
+     OUT UINTN             *BytesRead,
+     OUT UINT8             *Byte
+  )
+{
+  UINTN      ReadSize;
+  EFI_STATUS Status;
+
+  if (FileBuffer->Left == 0) {
+    ReadSize = FileBuffer->Allocated;
+    Status = gEfiShellProtocol->ReadFile (FileHandle, &ReadSize,
+                                  FileBuffer->Data);
+    if (EFI_ERROR (Status)) {
+      return Status;
+    }
+    if (ReadSize == 0) {
+      *BytesRead = 0;
+      return EFI_SUCCESS;
+    }
+    FileBuffer->Next = 0;
+    FileBuffer->Left = ReadSize;
+  }
+
+  *BytesRead = 1;
+  *Byte      = FileBuffer->Data[FileBuffer->Next];
+
+  FileBuffer->Next++;
+  FileBuffer->Left--;
+  return EFI_SUCCESS;
+}
+
 /**
   Function for 'comp' command.
 
@@ -107,6 +217,8 @@ ShellCommandRunComp (
   UINT8               OneByteFromFile2;
   UINT8               *DataFromFile1;
   UINT8               *DataFromFile2;
+  FILE_BUFFER         FileBuffer1;
+  FILE_BUFFER         FileBuffer2;
   UINTN               InsertPosition1;
   UINTN               InsertPosition2;
   UINTN               DataSizeFromFile1;
@@ -234,10 +346,15 @@ ShellCommandRunComp (
       if (ShellStatus == SHELL_SUCCESS) {
         DataFromFile1 = AllocateZeroPool ((UINTN)DifferentBytes);
         DataFromFile2 = AllocateZeroPool ((UINTN)DifferentBytes);
-        if (DataFromFile1 == NULL || DataFromFile2 == NULL) {
+        FileBufferInit (&FileBuffer1);
+        FileBufferInit (&FileBuffer2);
+        if (DataFromFile1 == NULL || DataFromFile2 == NULL ||
+            FileBuffer1.Data == NULL || FileBuffer2.Data == NULL) {
           ShellStatus = SHELL_OUT_OF_RESOURCES;
           SHELL_FREE_NON_NULL (DataFromFile1);
           SHELL_FREE_NON_NULL (DataFromFile2);
+          FileBufferUninit (&FileBuffer1);
+          FileBufferUninit (&FileBuffer2);
         }
       }
 
@@ -247,9 +364,11 @@ ShellCommandRunComp (
           DataSizeFromFile2 = 1;
           OneByteFromFile1 = 0;
           OneByteFromFile2 = 0;
-          Status = gEfiShellProtocol->ReadFile (FileHandle1, &DataSizeFromFile1, &OneByteFromFile1);
+          Status = FileBufferReadByte (FileHandle1, &FileBuffer1,
+                     &DataSizeFromFile1, &OneByteFromFile1);
           ASSERT_EFI_ERROR (Status);
-          Status = gEfiShellProtocol->ReadFile (FileHandle2, &DataSizeFromFile2, &OneByteFromFile2);
+          Status = FileBufferReadByte (FileHandle2, &FileBuffer2,
+                     &DataSizeFromFile2, &OneByteFromFile2);
           ASSERT_EFI_ERROR (Status);
 
           TempAddress++;
@@ -346,6 +465,8 @@ ShellCommandRunComp (
 
         SHELL_FREE_NON_NULL (DataFromFile1);
         SHELL_FREE_NON_NULL (DataFromFile2);
+        FileBufferUninit (&FileBuffer1);
+        FileBufferUninit (&FileBuffer2);
 
         if (DiffPointNumber == 0) {
           ShellPrintHiiEx(-1, -1, NULL, STRING_TOKEN (STR_COMP_FOOTER_PASS), gShellDebug1HiiHandle);
-- 
2.19.1.3.g30247aa5d201



^ permalink raw reply related	[flat|nested] 31+ messages in thread

* [PATCH v2 02/10] OvmfPkg: raise PcdShellFileOperationSize to 128KB
  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  8:54 ` Laszlo Ersek
  2021-01-15  9:34   ` Philippe Mathieu-Daudé
  2021-01-13  8:54 ` [PATCH v2 03/10] ArmVirtPkg: " Laszlo Ersek
                   ` (8 subsequent siblings)
  10 siblings, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel; +Cc: Ard Biesheuvel, Jordan Justen, Philippe Mathieu-Daudé

Some UEFI shell commands read and write files in chunks. The chunk size is
given by "PcdShellFileOperationSize", whose default in
"ShellPkg/ShellPkg.dec" is 4KB (0x1000).

The virtio-fs daemon of QEMU advertizes a 128KB maximum buffer size by
default, for the FUSE_WRITE operation.

By raising PcdShellFileOperationSize 32-fold, the number of FUSE write
requests shrinks proportionately, when writing large files. And when a
Virtio Filesystem is not used, a 128KB chunk size is still not
particularly wasteful.

Some ad-hoc measurements on my laptop, using OVMF:

- The time it takes to copy a ~270MB file from a Virtio Filesystem to the
  same Virtio Filesystem improves from ~9 seconds to ~1 second.

- The time it takes to compare two identical ~270MB files on the same
  Virtio Filesystem improves from ~11 seconds to ~3 seconds.

Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
Cc: Jordan Justen <jordan.l.justen@intel.com>
Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3125
Signed-off-by: Laszlo Ersek <lersek@redhat.com>
Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
---

Notes:
    v2:
    - no changes
    - pick up Ard's A-b

 OvmfPkg/OvmfPkgIa32.dsc    | 2 ++
 OvmfPkg/OvmfPkgIa32X64.dsc | 2 ++
 OvmfPkg/OvmfPkgX64.dsc     | 2 ++
 3 files changed, 6 insertions(+)

diff --git a/OvmfPkg/OvmfPkgIa32.dsc b/OvmfPkg/OvmfPkgIa32.dsc
index 75c5f46a7786..8b6dbb834505 100644
--- a/OvmfPkg/OvmfPkgIa32.dsc
+++ b/OvmfPkg/OvmfPkgIa32.dsc
@@ -562,6 +562,8 @@ [PcdsFixedAtBuild]
   #
 !include NetworkPkg/NetworkPcds.dsc.inc
 
+  gEfiShellPkgTokenSpaceGuid.PcdShellFileOperationSize|0x20000
+
 !if $(SMM_REQUIRE) == TRUE
   gUefiCpuPkgTokenSpaceGuid.PcdCpuSmmStackSize|0x4000
 !endif
diff --git a/OvmfPkg/OvmfPkgIa32X64.dsc b/OvmfPkg/OvmfPkgIa32X64.dsc
index 8693248b4ea0..4d7a26636a72 100644
--- a/OvmfPkg/OvmfPkgIa32X64.dsc
+++ b/OvmfPkg/OvmfPkgIa32X64.dsc
@@ -568,6 +568,8 @@ [PcdsFixedAtBuild.X64]
   #
 !include NetworkPkg/NetworkPcds.dsc.inc
 
+  gEfiShellPkgTokenSpaceGuid.PcdShellFileOperationSize|0x20000
+
 !if $(SMM_REQUIRE) == TRUE
   gUefiCpuPkgTokenSpaceGuid.PcdCpuSmmStackSize|0x4000
 !endif
diff --git a/OvmfPkg/OvmfPkgX64.dsc b/OvmfPkg/OvmfPkgX64.dsc
index 70ff2bcf2342..10f6a64d7f47 100644
--- a/OvmfPkg/OvmfPkgX64.dsc
+++ b/OvmfPkg/OvmfPkgX64.dsc
@@ -568,6 +568,8 @@ [PcdsFixedAtBuild]
   #
 !include NetworkPkg/NetworkPcds.dsc.inc
 
+  gEfiShellPkgTokenSpaceGuid.PcdShellFileOperationSize|0x20000
+
 !if $(SMM_REQUIRE) == TRUE
   gUefiCpuPkgTokenSpaceGuid.PcdCpuSmmStackSize|0x4000
 !endif
-- 
2.19.1.3.g30247aa5d201



^ permalink raw reply related	[flat|nested] 31+ messages in thread

* [PATCH v2 03/10] ArmVirtPkg: raise PcdShellFileOperationSize to 128KB
  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  8:54 ` [PATCH v2 02/10] OvmfPkg: raise PcdShellFileOperationSize to 128KB Laszlo Ersek
@ 2021-01-13  8:54 ` Laszlo Ersek
  2021-01-15 15:59   ` Philippe Mathieu-Daudé
  2021-01-13  8:54 ` [PATCH v2 04/10] EmulatorPkg: add OrderedCollectionLib class resolution Laszlo Ersek
                   ` (7 subsequent siblings)
  10 siblings, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel; +Cc: Ard Biesheuvel, Leif Lindholm, Philippe Mathieu-Daudé

Some UEFI shell commands read and write files in chunks. The chunk size is
given by "PcdShellFileOperationSize", whose default in
"ShellPkg/ShellPkg.dec" is 4KB (0x1000).

The virtio-fs daemon of QEMU advertizes a 128KB maximum buffer size by
default, for the FUSE_WRITE operation.

By raising PcdShellFileOperationSize 32-fold, the number of FUSE write
requests shrinks proportionately, when writing large files. And when a
Virtio Filesystem is not used, a 128KB chunk size is still not
particularly wasteful.

Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
Cc: Leif Lindholm <leif@nuviainc.com>
Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3125
Signed-off-by: Laszlo Ersek <lersek@redhat.com>
Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
---

Notes:
    v2:
    - no changes
    - pick up Ard's A-b

 ArmVirtPkg/ArmVirtQemu.dsc       | 1 +
 ArmVirtPkg/ArmVirtQemuKernel.dsc | 1 +
 2 files changed, 2 insertions(+)

diff --git a/ArmVirtPkg/ArmVirtQemu.dsc b/ArmVirtPkg/ArmVirtQemu.dsc
index ef5d6dbeaddc..b8bc08d73921 100644
--- a/ArmVirtPkg/ArmVirtQemu.dsc
+++ b/ArmVirtPkg/ArmVirtQemu.dsc
@@ -204,6 +204,7 @@ [PcdsFixedAtBuild.common]
 !endif
 
   gEfiMdePkgTokenSpaceGuid.PcdReportStatusCodePropertyMask|3
+  gEfiShellPkgTokenSpaceGuid.PcdShellFileOperationSize|0x20000
 
 [PcdsFixedAtBuild.AARCH64]
   # Clearing BIT0 in this PCD prevents installing a 32-bit SMBIOS entry point,
diff --git a/ArmVirtPkg/ArmVirtQemuKernel.dsc b/ArmVirtPkg/ArmVirtQemuKernel.dsc
index f8f5f7f4b94b..2ef86f96688f 100644
--- a/ArmVirtPkg/ArmVirtQemuKernel.dsc
+++ b/ArmVirtPkg/ArmVirtQemuKernel.dsc
@@ -174,6 +174,7 @@ [PcdsFixedAtBuild.common]
 !endif
 
   gEfiMdePkgTokenSpaceGuid.PcdReportStatusCodePropertyMask|3
+  gEfiShellPkgTokenSpaceGuid.PcdShellFileOperationSize|0x20000
 
 [PcdsPatchableInModule.common]
   # we need to provide a resolution for this PCD that supports PcdSet64()
-- 
2.19.1.3.g30247aa5d201



^ permalink raw reply related	[flat|nested] 31+ messages in thread

* [PATCH v2 04/10] EmulatorPkg: add OrderedCollectionLib class resolution
  2021-01-13  8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
                   ` (2 preceding siblings ...)
  2021-01-13  8:54 ` [PATCH v2 03/10] ArmVirtPkg: " Laszlo Ersek
@ 2021-01-13  8:54 ` Laszlo Ersek
  2021-01-13 13:20   ` Philippe Mathieu-Daudé
  2021-01-18 16:48   ` [edk2-devel] " Laszlo Ersek
  2021-01-13  8:54 ` [PATCH v2 05/10] UefiPayloadPkg: " Laszlo Ersek
                   ` (6 subsequent siblings)
  10 siblings, 2 replies; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel; +Cc: Andrew Fish, Jordan Justen, Philippe Mathieu-Daudé, Ray Ni

A subsequent patch in the series will make the

  ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf

instance dependent on the OrderedCollectionLib class. Because the shell
binary in this platform consumes the above UefiShellCommandLib instance,
resolve OrderedCollectionLib.

Cc: Andrew Fish <afish@apple.com>
Cc: Jordan Justen <jordan.l.justen@intel.com>
Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
Cc: Ray Ni <ray.ni@intel.com>
Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
Signed-off-by: Laszlo Ersek <lersek@redhat.com>
---

Notes:
    v2:
    - new patch

 EmulatorPkg/EmulatorPkg.dsc | 1 +
 1 file changed, 1 insertion(+)

diff --git a/EmulatorPkg/EmulatorPkg.dsc b/EmulatorPkg/EmulatorPkg.dsc
index de8144844c57..9ecc37334305 100644
--- a/EmulatorPkg/EmulatorPkg.dsc
+++ b/EmulatorPkg/EmulatorPkg.dsc
@@ -453,6 +453,7 @@ [Components]
       NULL|ShellPkg/Library/UefiShellInstall1CommandsLib/UefiShellInstall1CommandsLib.inf
       NULL|ShellPkg/Library/UefiShellNetwork1CommandsLib/UefiShellNetwork1CommandsLib.inf
       HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingLib.inf
+      OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.inf
       SortLib|MdeModulePkg/Library/UefiSortLib/UefiSortLib.inf
       PrintLib|MdePkg/Library/BasePrintLib/BasePrintLib.inf
 #      SafeBlockIoLib|ShellPkg/Library/SafeBlockIoLib/SafeBlockIoLib.inf
-- 
2.19.1.3.g30247aa5d201



^ permalink raw reply related	[flat|nested] 31+ messages in thread

* [PATCH v2 05/10] UefiPayloadPkg: add OrderedCollectionLib class resolution
  2021-01-13  8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
                   ` (3 preceding siblings ...)
  2021-01-13  8:54 ` [PATCH v2 04/10] EmulatorPkg: add OrderedCollectionLib class resolution Laszlo Ersek
@ 2021-01-13  8:54 ` Laszlo Ersek
  2021-01-13 13:20   ` Philippe Mathieu-Daudé
  2021-01-18 16:48   ` [edk2-devel] " Laszlo Ersek
  2021-01-13  8:54 ` [PATCH v2 06/10] ShellPkg/ShellCommandLib: add ShellSortFileList() Laszlo Ersek
                   ` (5 subsequent siblings)
  10 siblings, 2 replies; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel; +Cc: Benjamin You, Guo Dong, Maurice Ma, Philippe Mathieu-Daudé

A subsequent patch in the series will make the

  ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf

instance dependent on the OrderedCollectionLib class. Because the shell
binary in this platform consumes the above UefiShellCommandLib instance,
resolve OrderedCollectionLib.

Cc: Benjamin You <benjamin.you@intel.com>
Cc: Guo Dong <guo.dong@intel.com>
Cc: Maurice Ma <maurice.ma@intel.com>
Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
Signed-off-by: Laszlo Ersek <lersek@redhat.com>
---

Notes:
    v2:
    - new patch

 UefiPayloadPkg/UefiPayloadPkg.dsc | 1 +
 1 file changed, 1 insertion(+)

diff --git a/UefiPayloadPkg/UefiPayloadPkg.dsc b/UefiPayloadPkg/UefiPayloadPkg.dsc
index ae62a9c4d66b..24dab157f1ef 100644
--- a/UefiPayloadPkg/UefiPayloadPkg.dsc
+++ b/UefiPayloadPkg/UefiPayloadPkg.dsc
@@ -556,6 +556,7 @@ [Components.X64]
       DebugLib|MdePkg/Library/UefiDebugLibConOut/UefiDebugLibConOut.inf
       DevicePathLib|MdePkg/Library/UefiDevicePathLib/UefiDevicePathLib.inf
       HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingLib.inf
+      OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.inf
       PcdLib|MdePkg/Library/DxePcdLib/DxePcdLib.inf
       ShellCEntryLib|ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf
       ShellCommandLib|ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
-- 
2.19.1.3.g30247aa5d201



^ permalink raw reply related	[flat|nested] 31+ messages in thread

* [PATCH v2 06/10] ShellPkg/ShellCommandLib: add ShellSortFileList()
  2021-01-13  8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
                   ` (4 preceding siblings ...)
  2021-01-13  8:54 ` [PATCH v2 05/10] UefiPayloadPkg: " Laszlo Ersek
@ 2021-01-13  8:54 ` 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
                   ` (4 subsequent siblings)
  10 siblings, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel; +Cc: Philippe Mathieu-Daudé, Ray Ni, Zhichao Gao

Introduce the ShellSortFileList() function, for sorting an
EFI_SHELL_FILE_INFO list, by FileName or by FullName.

Duplicates can be kept in the same list, or separated out to a new list.
In either case, the relative order between duplicates does not change (the
sorting is stable).

For the sorting, use OrderedCollectionLib rather than SortLib:

- The PerformQuickSort() function from the latter has quadratic worst-case
  time complexity, plus it is implemented recursively (see
  "MdeModulePkg/Library/UefiSortLib/UefiSortLib.c"). It can also not
  return an error on memory allocation failure.

- In comparison, the Red-Black Tree instance of OrderedCollectionLib sorts
  in O(n*log(n)) worst-case time, contains no recursion with the default
  PcdValidateOrderedCollection=FALSE setting, and the OrderedCollectionLib
  class APIs return errors appropriately.

The OrderedCollectionLib APIs do not permit duplicates natively, but by
using lists as collection entries, stable sorting of duplicates can be
achieved.

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/ShellPkg.dsc                                        |   1 +
 ShellPkg/Include/Library/ShellCommandLib.h                   |  81 +++++
 ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf |   1 +
 ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h   |  19 ++
 ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c   | 312 ++++++++++++++++++++
 5 files changed, 414 insertions(+)

diff --git a/ShellPkg/ShellPkg.dsc b/ShellPkg/ShellPkg.dsc
index c42bc9464a0f..a8b6de334284 100644
--- a/ShellPkg/ShellPkg.dsc
+++ b/ShellPkg/ShellPkg.dsc
@@ -47,6 +47,7 @@ [LibraryClasses.common]
   ShellCommandLib|ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
   ShellCEntryLib|ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf
   HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingLib.inf
+  OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.inf
 
   PeCoffGetEntryPointLib|MdePkg/Library/BasePeCoffGetEntryPointLib/BasePeCoffGetEntryPointLib.inf
   BcfgCommandLib|ShellPkg/Library/UefiShellBcfgCommandLib/UefiShellBcfgCommandLib.inf
diff --git a/ShellPkg/Include/Library/ShellCommandLib.h b/ShellPkg/Include/Library/ShellCommandLib.h
index 63fcac82a2de..bc1afed5e7f5 100644
--- a/ShellPkg/Include/Library/ShellCommandLib.h
+++ b/ShellPkg/Include/Library/ShellCommandLib.h
@@ -714,4 +714,85 @@ CatSDumpHex (
   IN UINTN   DataSize,
   IN VOID    *UserData
   );
+
+//
+// Determines the ordering operation for ShellSortFileList().
+//
+typedef enum {
+  //
+  // Sort the EFI_SHELL_FILE_INFO objects by the FileName field, in increasing
+  // order, using gUnicodeCollation->StriColl().
+  //
+  ShellSortFileListByFileName,
+  //
+  // Sort the EFI_SHELL_FILE_INFO objects by the FullName field, in increasing
+  // order, using gUnicodeCollation->StriColl().
+  //
+  ShellSortFileListByFullName,
+  ShellSortFileListMax
+} SHELL_SORT_FILE_LIST;
+
+/**
+  Sort an EFI_SHELL_FILE_INFO list, optionally moving duplicates to a separate
+  list.
+
+  @param[in,out] FileList  The list of EFI_SHELL_FILE_INFO objects to sort.
+
+                           If FileList is NULL on input, then FileList is
+                           considered an empty, hence already sorted, list.
+
+                           Otherwise, if (*FileList) is NULL on input, then
+                           EFI_INVALID_PARAMETER is returned.
+
+                           Otherwise, the caller is responsible for having
+                           initialized (*FileList)->Link with
+                           InitializeListHead(). No other fields in the
+                           (**FileList) head element are accessed by this
+                           function.
+
+                           On output, (*FileList) is sorted according to Order.
+                           If Duplicates is NULL on input, then duplicate
+                           elements are preserved, sorted stably, on
+                           (*FileList). If Duplicates is not NULL on input,
+                           then duplicates are moved (stably sorted) to the
+                           new, dynamically allocated (*Duplicates) list.
+
+  @param[out] Duplicates   If Duplicates is NULL on input, (*FileList) will be
+                           a monotonically ordered list on output, with
+                           duplicates stably sorted.
+
+                           If Duplicates is not NULL on input, (*FileList) will
+                           be a strictly monotonically oredered list on output,
+                           with duplicates separated (stably sorted) to
+                           (*Duplicates). All fields except Link will be
+                           zero-initialized in the (**Duplicates) head element.
+                           If no duplicates exist, then (*Duplicates) is set to
+                           NULL on output.
+
+  @param[in] Order         Determines the comparison operation between
+                           EFI_SHELL_FILE_INFO objects.
+
+  @retval EFI_INVALID_PARAMETER  (UINTN)Order is greater than or equal to
+                                 (UINTN)ShellSortFileListMax. Neither the
+                                 (*FileList) nor the (*Duplicates) list has
+                                 been modified.
+
+  @retval EFI_INVALID_PARAMETER  (*FileList) was NULL on input. Neither the
+                                 (*FileList) nor the (*Duplicates) list has
+                                 been modified.
+
+  @retval EFI_OUT_OF_RESOURCES   Memory allocation failed. Neither the
+                                 (*FileList) nor the (*Duplicates) list has
+                                 been modified.
+
+  @retval EFI_SUCCESS            Sorting successful, including the case when
+                                 FileList is NULL on input.
+**/
+EFI_STATUS
+EFIAPI
+ShellSortFileList (
+  IN OUT EFI_SHELL_FILE_INFO  **FileList,
+     OUT EFI_SHELL_FILE_INFO  **Duplicates OPTIONAL,
+  IN     SHELL_SORT_FILE_LIST Order
+  );
 #endif //_SHELL_COMMAND_LIB_
diff --git a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
index a1b5601c96b6..08ca7cb78842 100644
--- a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
+++ b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
@@ -42,6 +42,7 @@ [LibraryClasses]
   ShellLib
   HiiLib
   HandleParsingLib
+  OrderedCollectionLib
 
 [Protocols]
   gEfiUnicodeCollation2ProtocolGuid                       ## CONSUMES
diff --git a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
index 8ecc2f6bf5a2..0ca291e4f9bf 100644
--- a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
+++ b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
@@ -39,6 +39,7 @@
 #include <Library/HiiLib.h>
 #include <Library/UefiBootServicesTableLib.h>
 #include <Library/UefiLib.h>
+#include <Library/OrderedCollectionLib.h>
 
 typedef struct{
   LIST_ENTRY                  Link;
@@ -60,6 +61,24 @@ typedef struct {
   CHAR16            *Path;
 } SHELL_COMMAND_FILE_HANDLE;
 
+//
+// Collects multiple EFI_SHELL_FILE_INFO objects that share the same name.
+//
+typedef struct {
+  //
+  // A string that compares equal to either the FileName or the FullName fields
+  // of all EFI_SHELL_FILE_INFO objects on SameNameList, according to
+  // gUnicodeCollation->StriColl(). The string is not dynamically allocated;
+  // instead, it *aliases* the FileName or FullName field of the
+  // EFI_SHELL_FILE_INFO object that was first encountered with this name.
+  //
+  CONST CHAR16 *Alias;
+  //
+  // A list of EFI_SHELL_FILE_INFO objects whose FileName or FullName fields
+  // compare equal to Alias, according to gUnicodeCollation->StriColl().
+  //
+  LIST_ENTRY SameNameList;
+} SHELL_SORT_UNIQUE_NAME;
 
 #endif //_UEFI_COMMAND_LIB_INTERNAL_HEADER_
 
diff --git a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
index 345808a1eac6..b06d22592d33 100644
--- a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
+++ b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
@@ -1909,3 +1909,315 @@ CatSDumpHex (
 
   return RetVal;
 }
+
+/**
+  ORDERED_COLLECTION_USER_COMPARE function for SHELL_SORT_UNIQUE_NAME objects.
+
+  @param[in] Unique1AsVoid  The first SHELL_SORT_UNIQUE_NAME object (Unique1),
+                            passed in as a pointer-to-VOID.
+
+  @param[in] Unique2AsVoid  The second SHELL_SORT_UNIQUE_NAME object (Unique2),
+                            passed in as a pointer-to-VOID.
+
+  @retval <0  If Unique1 compares less than Unique2.
+
+  @retval  0  If Unique1 compares equal to Unique2.
+
+  @retval >0  If Unique1 compares greater than Unique2.
+**/
+STATIC
+INTN
+EFIAPI
+UniqueNameCompare (
+  IN CONST VOID *Unique1AsVoid,
+  IN CONST VOID *Unique2AsVoid
+  )
+{
+  CONST SHELL_SORT_UNIQUE_NAME *Unique1;
+  CONST SHELL_SORT_UNIQUE_NAME *Unique2;
+
+  Unique1 = Unique1AsVoid;
+  Unique2 = Unique2AsVoid;
+
+  //
+  // We need to cast away CONST for EFI_UNICODE_COLLATION_STRICOLL.
+  //
+  return gUnicodeCollation->StriColl (
+                              gUnicodeCollation,
+                              (CHAR16 *)Unique1->Alias,
+                              (CHAR16 *)Unique2->Alias
+                              );
+}
+
+/**
+  ORDERED_COLLECTION_KEY_COMPARE function for SHELL_SORT_UNIQUE_NAME objects.
+
+  @param[in] UniqueAliasAsVoid  The CHAR16 string UniqueAlias, passed in as a
+                                pointer-to-VOID.
+
+  @param[in] UniqueAsVoid       The SHELL_SORT_UNIQUE_NAME object (Unique),
+                                passed in as a pointer-to-VOID.
+
+  @retval <0  If UniqueAlias compares less than Unique->Alias.
+
+  @retval  0  If UniqueAlias compares equal to Unique->Alias.
+
+  @retval >0  If UniqueAlias compares greater than Unique->Alias.
+**/
+STATIC
+INTN
+EFIAPI
+UniqueNameAliasCompare (
+  IN CONST VOID *UniqueAliasAsVoid,
+  IN CONST VOID *UniqueAsVoid
+  )
+{
+  CONST CHAR16                 *UniqueAlias;
+  CONST SHELL_SORT_UNIQUE_NAME *Unique;
+
+  UniqueAlias = UniqueAliasAsVoid;
+  Unique      = UniqueAsVoid;
+
+  //
+  // We need to cast away CONST for EFI_UNICODE_COLLATION_STRICOLL.
+  //
+  return gUnicodeCollation->StriColl (
+                              gUnicodeCollation,
+                              (CHAR16 *)UniqueAlias,
+                              (CHAR16 *)Unique->Alias
+                              );
+}
+
+/**
+  Sort an EFI_SHELL_FILE_INFO list, optionally moving duplicates to a separate
+  list.
+
+  @param[in,out] FileList  The list of EFI_SHELL_FILE_INFO objects to sort.
+
+                           If FileList is NULL on input, then FileList is
+                           considered an empty, hence already sorted, list.
+
+                           Otherwise, if (*FileList) is NULL on input, then
+                           EFI_INVALID_PARAMETER is returned.
+
+                           Otherwise, the caller is responsible for having
+                           initialized (*FileList)->Link with
+                           InitializeListHead(). No other fields in the
+                           (**FileList) head element are accessed by this
+                           function.
+
+                           On output, (*FileList) is sorted according to Order.
+                           If Duplicates is NULL on input, then duplicate
+                           elements are preserved, sorted stably, on
+                           (*FileList). If Duplicates is not NULL on input,
+                           then duplicates are moved (stably sorted) to the
+                           new, dynamically allocated (*Duplicates) list.
+
+  @param[out] Duplicates   If Duplicates is NULL on input, (*FileList) will be
+                           a monotonically ordered list on output, with
+                           duplicates stably sorted.
+
+                           If Duplicates is not NULL on input, (*FileList) will
+                           be a strictly monotonically oredered list on output,
+                           with duplicates separated (stably sorted) to
+                           (*Duplicates). All fields except Link will be
+                           zero-initialized in the (**Duplicates) head element.
+                           If no duplicates exist, then (*Duplicates) is set to
+                           NULL on output.
+
+  @param[in] Order         Determines the comparison operation between
+                           EFI_SHELL_FILE_INFO objects.
+
+  @retval EFI_INVALID_PARAMETER  (UINTN)Order is greater than or equal to
+                                 (UINTN)ShellSortFileListMax. Neither the
+                                 (*FileList) nor the (*Duplicates) list has
+                                 been modified.
+
+  @retval EFI_INVALID_PARAMETER  (*FileList) was NULL on input. Neither the
+                                 (*FileList) nor the (*Duplicates) list has
+                                 been modified.
+
+  @retval EFI_OUT_OF_RESOURCES   Memory allocation failed. Neither the
+                                 (*FileList) nor the (*Duplicates) list has
+                                 been modified.
+
+  @retval EFI_SUCCESS            Sorting successful, including the case when
+                                 FileList is NULL on input.
+**/
+EFI_STATUS
+EFIAPI
+ShellSortFileList (
+  IN OUT EFI_SHELL_FILE_INFO  **FileList,
+     OUT EFI_SHELL_FILE_INFO  **Duplicates OPTIONAL,
+  IN     SHELL_SORT_FILE_LIST Order
+  )
+{
+  LIST_ENTRY               *FilesHead;
+  ORDERED_COLLECTION       *Sort;
+  LIST_ENTRY               *FileEntry;
+  EFI_SHELL_FILE_INFO      *FileInfo;
+  SHELL_SORT_UNIQUE_NAME   *Unique;
+  EFI_STATUS               Status;
+  EFI_SHELL_FILE_INFO      *Dupes;
+  LIST_ENTRY               *NextFileEntry;
+  CONST CHAR16             *Alias;
+  ORDERED_COLLECTION_ENTRY *SortEntry;
+  LIST_ENTRY               *TargetFileList;
+  ORDERED_COLLECTION_ENTRY *NextSortEntry;
+  VOID                     *UniqueAsVoid;
+
+  if ((UINTN)Order >= (UINTN)ShellSortFileListMax) {
+    return EFI_INVALID_PARAMETER;
+  }
+
+  if (FileList == NULL) {
+    //
+    // FileList is considered empty, hence already sorted, with no duplicates.
+    //
+    if (Duplicates != NULL) {
+      *Duplicates = NULL;
+    }
+    return EFI_SUCCESS;
+  }
+
+  if (*FileList == NULL) {
+    return EFI_INVALID_PARAMETER;
+  }
+  FilesHead = &(*FileList)->Link;
+
+  //
+  // Collect all the unique names.
+  //
+  Sort = OrderedCollectionInit (UniqueNameCompare, UniqueNameAliasCompare);
+  if (Sort == NULL) {
+    return EFI_OUT_OF_RESOURCES;
+  }
+
+  BASE_LIST_FOR_EACH (FileEntry, FilesHead) {
+    FileInfo = (EFI_SHELL_FILE_INFO *)FileEntry;
+
+    //
+    // Try to record the name of this file as a unique name.
+    //
+    Unique = AllocatePool (sizeof (*Unique));
+    if (Unique == NULL) {
+      Status = EFI_OUT_OF_RESOURCES;
+      goto UninitSort;
+    }
+    Unique->Alias = ((Order == ShellSortFileListByFileName) ?
+                     FileInfo->FileName :
+                     FileInfo->FullName);
+    InitializeListHead (&Unique->SameNameList);
+
+    Status = OrderedCollectionInsert (Sort, NULL, Unique);
+    if (EFI_ERROR (Status)) {
+      //
+      // Only two errors are possible: memory allocation failed, or this name
+      // has been encountered before. In either case, the
+      // SHELL_SORT_UNIQUE_NAME object being constructed has to be released.
+      //
+      FreePool (Unique);
+      //
+      // Memory allocation failure is fatal, while having seen the same name
+      // before is normal.
+      //
+      if (Status == EFI_OUT_OF_RESOURCES) {
+        goto UninitSort;
+      }
+      ASSERT (Status == EFI_ALREADY_STARTED);
+    }
+  }
+
+  //
+  // If separation of duplicates has been requested, allocate the list for
+  // them.
+  //
+  if (Duplicates != NULL) {
+    Dupes = AllocateZeroPool (sizeof (*Dupes));
+    if (Dupes == NULL) {
+      Status = EFI_OUT_OF_RESOURCES;
+      goto UninitSort;
+    }
+    InitializeListHead (&Dupes->Link);
+  }
+
+  //
+  // No memory allocation beyond this point; thus, no chance to fail. We can
+  // now migrate the EFI_SHELL_FILE_INFO objects from (*FileList) to Sort.
+  //
+  BASE_LIST_FOR_EACH_SAFE (FileEntry, NextFileEntry, FilesHead) {
+    FileInfo = (EFI_SHELL_FILE_INFO *)FileEntry;
+    //
+    // Look up the SHELL_SORT_UNIQUE_NAME that matches FileInfo's name.
+    //
+    Alias = ((Order == ShellSortFileListByFileName) ?
+             FileInfo->FileName :
+             FileInfo->FullName);
+    SortEntry = OrderedCollectionFind (Sort, Alias);
+    ASSERT (SortEntry != NULL);
+    Unique = OrderedCollectionUserStruct (SortEntry);
+    //
+    // Move FileInfo from (*FileList) to the end of the list of files whose
+    // names all compare identical to FileInfo's name.
+    //
+    RemoveEntryList (&FileInfo->Link);
+    InsertTailList (&Unique->SameNameList, &FileInfo->Link);
+  }
+
+  //
+  // All EFI_SHELL_FILE_INFO objects originally in (*FileList) have been
+  // distributed to Sort. Now migrate them back to (*FileList), advancing in
+  // unique name order.
+  //
+  for (SortEntry = OrderedCollectionMin (Sort);
+       SortEntry != NULL;
+       SortEntry = OrderedCollectionNext (SortEntry)) {
+    Unique = OrderedCollectionUserStruct (SortEntry);
+    //
+    // The first FileInfo encountered for each unique name goes back on
+    // (*FileList) unconditionally. Further FileInfo instances for the same
+    // unique name -- that is, duplicates -- are either returned to (*FileList)
+    // or separated, dependent on the caller's request.
+    //
+    TargetFileList = FilesHead;
+    BASE_LIST_FOR_EACH_SAFE (FileEntry, NextFileEntry, &Unique->SameNameList) {
+      RemoveEntryList (FileEntry);
+      InsertTailList (TargetFileList, FileEntry);
+      if (Duplicates != NULL) {
+        TargetFileList = &Dupes->Link;
+      }
+    }
+  }
+
+  //
+  // We're done. If separation of duplicates has been requested, output the
+  // list of duplicates -- and free that list at once, if it's empty (i.e., if
+  // no duplicates have been found).
+  //
+  if (Duplicates != NULL) {
+    if (IsListEmpty (&Dupes->Link)) {
+      FreePool (Dupes);
+      *Duplicates = NULL;
+    } else {
+      *Duplicates = Dupes;
+    }
+  }
+  Status = EFI_SUCCESS;
+
+  //
+  // Fall through.
+  //
+UninitSort:
+  for (SortEntry = OrderedCollectionMin (Sort);
+       SortEntry != NULL;
+       SortEntry = NextSortEntry) {
+    NextSortEntry = OrderedCollectionNext (SortEntry);
+    OrderedCollectionDelete (Sort, SortEntry, &UniqueAsVoid);
+    Unique = UniqueAsVoid;
+    ASSERT (IsListEmpty (&Unique->SameNameList));
+    FreePool (Unique);
+  }
+  OrderedCollectionUninit (Sort);
+
+  return Status;
+}
-- 
2.19.1.3.g30247aa5d201



^ permalink raw reply related	[flat|nested] 31+ messages in thread

* [PATCH v2 07/10] ShellPkg/Ls: sort output by FileName in non-SFO mode
  2021-01-13  8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
                   ` (5 preceding siblings ...)
  2021-01-13  8:54 ` [PATCH v2 06/10] ShellPkg/ShellCommandLib: add ShellSortFileList() Laszlo Ersek
@ 2021-01-13  8:54 ` 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
                   ` (3 subsequent siblings)
  10 siblings, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel; +Cc: Philippe Mathieu-Daudé, Ray Ni, Zhichao Gao

Sorting the LS output in non-SFO mode by FileName is best demonstrated
with two examples.

(1a) Before:

> FS2:\> dir -r apps
> Directory of: FS2:\apps\
> 01/01/1970  01:00 <DIR> r           0  .
> 12/22/2020  17:53 <DIR>         4,096  X64
> 12/22/2020  17:53 <DIR>         4,096  AARCH64
> 01/01/1970  01:00 <DIR> r           0  ..
> 12/22/2020  17:53 <DIR>         4,096  IA32
>           0 File(s)           0 bytes
>           5 Dir(s)
> Directory of: FS2:\apps\X64\
> 12/22/2020  17:52              18,752  DumpDynPcd.efi
> 12/22/2020  17:52              34,240  SmiHandlerProfileInfo.efi
> 01/01/1970  01:00 <DIR> r           0  .
> 12/22/2020  17:52              11,456  VariableInfo.efi
> 12/22/2020  17:52              26,304  MemoryProfileInfo.efi
> 12/22/2020  17:53             126,656  AcpiViewApp.efi
> 12/22/2020  17:53              38,784  Cpuid.efi
> 01/01/1970  01:00 <DIR> r           0  ..
>           6 File(s)     256,192 bytes
>           2 Dir(s)
> Directory of: FS2:\apps\AARCH64\
> 12/22/2020  17:52              32,768  DumpDynPcd.efi
> 01/01/1970  01:00 <DIR> r           0  .
> 12/22/2020  17:52              20,480  VariableInfo.efi
> 12/22/2020  17:52              40,960  MemoryProfileInfo.efi
> 12/22/2020  17:53             139,264  AcpiViewApp.efi
> 01/01/1970  01:00 <DIR> r           0  ..
>           4 File(s)     233,472 bytes
>           2 Dir(s)
> Directory of: FS2:\apps\IA32\
> 12/22/2020  17:52              17,344  DumpDynPcd.efi
> 12/22/2020  17:52              30,720  SmiHandlerProfileInfo.efi
> 01/01/1970  01:00 <DIR> r           0  .
> 12/22/2020  17:52              10,880  VariableInfo.efi
> 12/22/2020  17:52              24,192  MemoryProfileInfo.efi
> 12/22/2020  17:53             105,536  AcpiViewApp.efi
> 12/22/2020  17:53              36,096  Cpuid.efi
> 01/01/1970  01:00 <DIR> r           0  ..
>           6 File(s)     224,768 bytes
>           2 Dir(s)

(1b) 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\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)

(2a) Before:

> FS2:\> dir apps\*\*.efi
> Directory of: FS2:\apps\*\
> 12/22/2020  17:52              18,752  DumpDynPcd.efi
> 12/22/2020  17:52              34,240  SmiHandlerProfileInfo.efi
> 12/22/2020  17:52              11,456  VariableInfo.efi
> 12/22/2020  17:52              26,304  MemoryProfileInfo.efi
> 12/22/2020  17:53             126,656  AcpiViewApp.efi
> 12/22/2020  17:53              38,784  Cpuid.efi
> 12/22/2020  17:52              32,768  DumpDynPcd.efi
> 12/22/2020  17:52              20,480  VariableInfo.efi
> 12/22/2020  17:52              40,960  MemoryProfileInfo.efi
> 12/22/2020  17:53             139,264  AcpiViewApp.efi
> 12/22/2020  17:52              17,344  DumpDynPcd.efi
> 12/22/2020  17:52              30,720  SmiHandlerProfileInfo.efi
> 12/22/2020  17:52              10,880  VariableInfo.efi
> 12/22/2020  17:52              24,192  MemoryProfileInfo.efi
> 12/22/2020  17:53             105,536  AcpiViewApp.efi
> 12/22/2020  17:53              36,096  Cpuid.efi
>          16 File(s)     714,432 bytes
>           0 Dir(s)

(2b) After:

> 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)

(In example (2), note that the sorting is stable; that is, whatever order
is established between identical FileNames by ShellOpenFileMetaArg(), it
is preserved by ShellSortFileList().)

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/Library/UefiShellLevel2CommandsLib/Ls.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)

diff --git a/ShellPkg/Library/UefiShellLevel2CommandsLib/Ls.c b/ShellPkg/Library/UefiShellLevel2CommandsLib/Ls.c
index da2b1acab47c..8b97926d7f47 100644
--- a/ShellPkg/Library/UefiShellLevel2CommandsLib/Ls.c
+++ b/ShellPkg/Library/UefiShellLevel2CommandsLib/Ls.c
@@ -489,6 +489,20 @@ PrintLsOutput(
       PrintSfoVolumeInfoTableEntry(ListHead);
     }
 
+    if (!Sfo) {
+      //
+      // Sort the file list by FileName, stably.
+      //
+      // If the call below fails, then the EFI_SHELL_FILE_INFO list anchored to
+      // ListHead will not be changed in any way.
+      //
+      ShellSortFileList (
+        &ListHead,
+        NULL,                       // Duplicates
+        ShellSortFileListByFileName
+        );
+    }
+
     for ( Node = (EFI_SHELL_FILE_INFO *)GetFirstNode(&ListHead->Link), LongestPath = 0
         ; !IsNull(&ListHead->Link, &Node->Link)
         ; Node = (EFI_SHELL_FILE_INFO *)GetNextNode(&ListHead->Link, &Node->Link)
-- 
2.19.1.3.g30247aa5d201



^ permalink raw reply related	[flat|nested] 31+ messages in thread

* [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList()
  2021-01-13  8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
                   ` (6 preceding siblings ...)
  2021-01-13  8:54 ` [PATCH v2 07/10] ShellPkg/Ls: sort output by FileName in non-SFO mode Laszlo Ersek
@ 2021-01-13  8:54 ` Laszlo Ersek
  2021-01-13 13:14   ` Philippe Mathieu-Daudé
  2021-01-13  8:54 ` [PATCH v2 09/10] OvmfPkg: disable list length checks in NOOPT and DEBUG builds Laszlo Ersek
                   ` (2 subsequent siblings)
  10 siblings, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel; +Cc: Philippe Mathieu-Daudé, Ray Ni, Zhichao Gao

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



^ permalink raw reply related	[flat|nested] 31+ messages in thread

* [PATCH v2 09/10] OvmfPkg: disable list length checks in NOOPT and DEBUG builds
  2021-01-13  8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
                   ` (7 preceding siblings ...)
  2021-01-13  8:54 ` [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList() Laszlo Ersek
@ 2021-01-13  8:54 ` Laszlo Ersek
  2021-01-15  9:30   ` Philippe Mathieu-Daudé
  2021-01-13  8:54 ` [PATCH v2 10/10] ArmVirtPkg: " Laszlo Ersek
  2021-01-19 18:39 ` [edk2-devel] [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
  10 siblings, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel
  Cc: Anthony Perard, Ard Biesheuvel, Jordan Justen, Julien Grall,
	Leif Lindholm, Peter Grehan, Philippe Mathieu-Daudé,
	Rebecca Cran, Sami Mujawar

In NOOPT and DEBUG builds, if "PcdMaximumLinkedListLength" is nonzero,
then several LIST_ENTRY *node* APIs in BaseLib compare the *full* list
length against the PCD.

This turns the time complexity of node-level APIs from constant to linear,
and that of full-list manipulations from linear to quadratic.

As an example, consider the EFI_SHELL_FILE_INFO list, which is a data
structure that's widely used in the UEFI shell. I randomly extracted 5000
files from "/usr/include" on my laptop, spanning 1095 subdirectories out
of 1538, and then ran "DIR -R" in the UEFI shell on this tree. These are
the wall-clock times:

           PcdMaximumLinkedListLength  PcdMaximumLinkedListLength
           =1,000,000                  =0
           --------------------------  ---------------------------
FAT        4 min 31 s                        18 s
virtio-fs  5 min 13 s                  1 min 33 s

Checking list lengths against an arbitrary maximum (default: 1,000,000)
seems useless even in NOOPT and DEBUG builds, while the cost is
significant; so set the PCD to 0.

Cc: Anthony Perard <anthony.perard@citrix.com>
Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
Cc: Jordan Justen <jordan.l.justen@intel.com>
Cc: Julien Grall <julien@xen.org>
Cc: Leif Lindholm <leif@nuviainc.com>
Cc: Peter Grehan <grehan@freebsd.org>
Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
Cc: Rebecca Cran <rebecca@bsdio.com>
Cc: Sami Mujawar <sami.mujawar@arm.com>
Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3152
Signed-off-by: Laszlo Ersek <lersek@redhat.com>
Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
---

Notes:
    v2:
    - no changes
    - pick up Ard's A-b

 OvmfPkg/AmdSev/AmdSevX64.dsc | 1 +
 OvmfPkg/Bhyve/BhyveX64.dsc   | 1 +
 OvmfPkg/OvmfPkgIa32.dsc      | 1 +
 OvmfPkg/OvmfPkgIa32X64.dsc   | 1 +
 OvmfPkg/OvmfPkgX64.dsc       | 1 +
 OvmfPkg/OvmfXen.dsc          | 1 +
 6 files changed, 6 insertions(+)

diff --git a/OvmfPkg/AmdSev/AmdSevX64.dsc b/OvmfPkg/AmdSev/AmdSevX64.dsc
index dad8635c3388..e6d545ab522f 100644
--- a/OvmfPkg/AmdSev/AmdSevX64.dsc
+++ b/OvmfPkg/AmdSev/AmdSevX64.dsc
@@ -441,6 +441,7 @@ [PcdsFixedAtBuild]
   gEfiMdeModulePkgTokenSpaceGuid.PcdStatusCodeMemorySize|1
   gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE
   gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10
+  gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0
 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048)
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800
diff --git a/OvmfPkg/Bhyve/BhyveX64.dsc b/OvmfPkg/Bhyve/BhyveX64.dsc
index 33edf3d2d6b5..a1f43eaa4d9c 100644
--- a/OvmfPkg/Bhyve/BhyveX64.dsc
+++ b/OvmfPkg/Bhyve/BhyveX64.dsc
@@ -431,6 +431,7 @@ [PcdsFixedAtBuild]
   gEfiMdeModulePkgTokenSpaceGuid.PcdStatusCodeMemorySize|1
   gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE
   gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10
+  gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0
 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048)
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800
diff --git a/OvmfPkg/OvmfPkgIa32.dsc b/OvmfPkg/OvmfPkgIa32.dsc
index 8b6dbb834505..e5184ef06731 100644
--- a/OvmfPkg/OvmfPkgIa32.dsc
+++ b/OvmfPkg/OvmfPkgIa32.dsc
@@ -478,6 +478,7 @@ [PcdsFixedAtBuild]
   gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE
 !endif
   gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10
+  gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0
 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048)
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800
diff --git a/OvmfPkg/OvmfPkgIa32X64.dsc b/OvmfPkg/OvmfPkgIa32X64.dsc
index 4d7a26636a72..3bfec9196eba 100644
--- a/OvmfPkg/OvmfPkgIa32X64.dsc
+++ b/OvmfPkg/OvmfPkgIa32X64.dsc
@@ -482,6 +482,7 @@ [PcdsFixedAtBuild]
   gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE
 !endif
   gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10
+  gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0
 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048)
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800
diff --git a/OvmfPkg/OvmfPkgX64.dsc b/OvmfPkg/OvmfPkgX64.dsc
index 10f6a64d7f47..1376158e37e3 100644
--- a/OvmfPkg/OvmfPkgX64.dsc
+++ b/OvmfPkg/OvmfPkgX64.dsc
@@ -484,6 +484,7 @@ [PcdsFixedAtBuild]
   gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE
 !endif
   gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10
+  gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0
 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048)
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800
diff --git a/OvmfPkg/OvmfXen.dsc b/OvmfPkg/OvmfXen.dsc
index 7d31e88907ca..f3fe85d57209 100644
--- a/OvmfPkg/OvmfXen.dsc
+++ b/OvmfPkg/OvmfXen.dsc
@@ -358,6 +358,7 @@ [PcdsFixedAtBuild]
   gEfiMdeModulePkgTokenSpaceGuid.PcdStatusCodeMemorySize|1
   gEfiMdeModulePkgTokenSpaceGuid.PcdResetOnMemoryTypeInformationChange|FALSE
   gEfiMdePkgTokenSpaceGuid.PcdMaximumGuidedExtractHandler|0x10
+  gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0
 !if ($(FD_SIZE_IN_KB) == 1024) || ($(FD_SIZE_IN_KB) == 2048)
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxVariableSize|0x2000
   gEfiMdeModulePkgTokenSpaceGuid.PcdMaxAuthVariableSize|0x2800
-- 
2.19.1.3.g30247aa5d201



^ permalink raw reply related	[flat|nested] 31+ messages in thread

* [PATCH v2 10/10] ArmVirtPkg: disable list length checks in NOOPT and DEBUG builds
  2021-01-13  8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
                   ` (8 preceding siblings ...)
  2021-01-13  8:54 ` [PATCH v2 09/10] OvmfPkg: disable list length checks in NOOPT and DEBUG builds Laszlo Ersek
@ 2021-01-13  8:54 ` 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
  10 siblings, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-13  8:54 UTC (permalink / raw)
  To: devel
  Cc: Ard Biesheuvel, Julien Grall, Leif Lindholm,
	Philippe Mathieu-Daudé, Sami Mujawar

In NOOPT and DEBUG builds, if "PcdMaximumLinkedListLength" is nonzero,
then several LIST_ENTRY *node* APIs in BaseLib compare the *full* list
length against the PCD.

This turns the time complexity of node-level APIs from constant to linear,
and that of full-list manipulations from linear to quadratic.

(See some example OVMF numbers in the previous patch.)

Checking list lengths against an arbitrary maximum -- default value, and
current ArmVirtPkg setting: 1,000,000 -- seems useless even in NOOPT and
DEBUG builds, while the cost is significant; so set the PCD to 0.

Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
Cc: Julien Grall <julien@xen.org>
Cc: Leif Lindholm <leif@nuviainc.com>
Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
Cc: Sami Mujawar <sami.mujawar@arm.com>
Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3152
Signed-off-by: Laszlo Ersek <lersek@redhat.com>
Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
---

Notes:
    v2:
    - no changes
    - pick up Ard's A-b

 ArmVirtPkg/ArmVirt.dsc.inc | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/ArmVirtPkg/ArmVirt.dsc.inc b/ArmVirtPkg/ArmVirt.dsc.inc
index 9ec92930472d..d9abadbe708c 100644
--- a/ArmVirtPkg/ArmVirt.dsc.inc
+++ b/ArmVirtPkg/ArmVirt.dsc.inc
@@ -290,7 +290,7 @@ [PcdsFeatureFlag.AARCH64]
 [PcdsFixedAtBuild.common]
   gEfiMdePkgTokenSpaceGuid.PcdMaximumUnicodeStringLength|1000000
   gEfiMdePkgTokenSpaceGuid.PcdMaximumAsciiStringLength|1000000
-  gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|1000000
+  gEfiMdePkgTokenSpaceGuid.PcdMaximumLinkedListLength|0
   gEfiMdePkgTokenSpaceGuid.PcdSpinLockTimeout|10000000
   gEfiMdePkgTokenSpaceGuid.PcdUefiLibMaxPrintBufferSize|320
 
-- 
2.19.1.3.g30247aa5d201


^ permalink raw reply related	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList()
  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
  0 siblings, 1 reply; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-13 13:14 UTC (permalink / raw)
  To: Laszlo Ersek, devel; +Cc: Ray Ni, Zhichao Gao

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>


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 07/10] ShellPkg/Ls: sort output by FileName in non-SFO mode
  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é
  0 siblings, 0 replies; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-13 13:15 UTC (permalink / raw)
  To: Laszlo Ersek, devel; +Cc: Ray Ni, Zhichao Gao

On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> Sorting the LS output in non-SFO mode by FileName is best demonstrated
> with two examples.
> 
> (1a) Before:
> 
>> FS2:\> dir -r apps
>> Directory of: FS2:\apps\
>> 01/01/1970  01:00 <DIR> r           0  .
>> 12/22/2020  17:53 <DIR>         4,096  X64
>> 12/22/2020  17:53 <DIR>         4,096  AARCH64
>> 01/01/1970  01:00 <DIR> r           0  ..
>> 12/22/2020  17:53 <DIR>         4,096  IA32
>>           0 File(s)           0 bytes
>>           5 Dir(s)
>> Directory of: FS2:\apps\X64\
>> 12/22/2020  17:52              18,752  DumpDynPcd.efi
>> 12/22/2020  17:52              34,240  SmiHandlerProfileInfo.efi
>> 01/01/1970  01:00 <DIR> r           0  .
>> 12/22/2020  17:52              11,456  VariableInfo.efi
>> 12/22/2020  17:52              26,304  MemoryProfileInfo.efi
>> 12/22/2020  17:53             126,656  AcpiViewApp.efi
>> 12/22/2020  17:53              38,784  Cpuid.efi
>> 01/01/1970  01:00 <DIR> r           0  ..
>>           6 File(s)     256,192 bytes
>>           2 Dir(s)
>> Directory of: FS2:\apps\AARCH64\
>> 12/22/2020  17:52              32,768  DumpDynPcd.efi
>> 01/01/1970  01:00 <DIR> r           0  .
>> 12/22/2020  17:52              20,480  VariableInfo.efi
>> 12/22/2020  17:52              40,960  MemoryProfileInfo.efi
>> 12/22/2020  17:53             139,264  AcpiViewApp.efi
>> 01/01/1970  01:00 <DIR> r           0  ..
>>           4 File(s)     233,472 bytes
>>           2 Dir(s)
>> Directory of: FS2:\apps\IA32\
>> 12/22/2020  17:52              17,344  DumpDynPcd.efi
>> 12/22/2020  17:52              30,720  SmiHandlerProfileInfo.efi
>> 01/01/1970  01:00 <DIR> r           0  .
>> 12/22/2020  17:52              10,880  VariableInfo.efi
>> 12/22/2020  17:52              24,192  MemoryProfileInfo.efi
>> 12/22/2020  17:53             105,536  AcpiViewApp.efi
>> 12/22/2020  17:53              36,096  Cpuid.efi
>> 01/01/1970  01:00 <DIR> r           0  ..
>>           6 File(s)     224,768 bytes
>>           2 Dir(s)
> 
> (1b) 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\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)
> 
> (2a) Before:
> 
>> FS2:\> dir apps\*\*.efi
>> Directory of: FS2:\apps\*\
>> 12/22/2020  17:52              18,752  DumpDynPcd.efi
>> 12/22/2020  17:52              34,240  SmiHandlerProfileInfo.efi
>> 12/22/2020  17:52              11,456  VariableInfo.efi
>> 12/22/2020  17:52              26,304  MemoryProfileInfo.efi
>> 12/22/2020  17:53             126,656  AcpiViewApp.efi
>> 12/22/2020  17:53              38,784  Cpuid.efi
>> 12/22/2020  17:52              32,768  DumpDynPcd.efi
>> 12/22/2020  17:52              20,480  VariableInfo.efi
>> 12/22/2020  17:52              40,960  MemoryProfileInfo.efi
>> 12/22/2020  17:53             139,264  AcpiViewApp.efi
>> 12/22/2020  17:52              17,344  DumpDynPcd.efi
>> 12/22/2020  17:52              30,720  SmiHandlerProfileInfo.efi
>> 12/22/2020  17:52              10,880  VariableInfo.efi
>> 12/22/2020  17:52              24,192  MemoryProfileInfo.efi
>> 12/22/2020  17:53             105,536  AcpiViewApp.efi
>> 12/22/2020  17:53              36,096  Cpuid.efi
>>          16 File(s)     714,432 bytes
>>           0 Dir(s)
> 
> (2b) After:
> 
>> 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)
> 
> (In example (2), note that the sorting is stable; that is, whatever order
> is established between identical FileNames by ShellOpenFileMetaArg(), it
> is preserved by ShellSortFileList().)
> 
> 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/Library/UefiShellLevel2CommandsLib/Ls.c | 14 ++++++++++++++
>  1 file changed, 14 insertions(+)

Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 06/10] ShellPkg/ShellCommandLib: add ShellSortFileList()
  2021-01-13  8:54 ` [PATCH v2 06/10] ShellPkg/ShellCommandLib: add ShellSortFileList() Laszlo Ersek
@ 2021-01-13 13:19   ` Philippe Mathieu-Daudé
  0 siblings, 0 replies; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-13 13:19 UTC (permalink / raw)
  To: Laszlo Ersek, devel; +Cc: Ray Ni, Zhichao Gao

On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> Introduce the ShellSortFileList() function, for sorting an
> EFI_SHELL_FILE_INFO list, by FileName or by FullName.
> 
> Duplicates can be kept in the same list, or separated out to a new list.
> In either case, the relative order between duplicates does not change (the
> sorting is stable).
> 
> For the sorting, use OrderedCollectionLib rather than SortLib:
> 
> - The PerformQuickSort() function from the latter has quadratic worst-case
>   time complexity, plus it is implemented recursively (see
>   "MdeModulePkg/Library/UefiSortLib/UefiSortLib.c"). It can also not
>   return an error on memory allocation failure.
> 
> - In comparison, the Red-Black Tree instance of OrderedCollectionLib sorts
>   in O(n*log(n)) worst-case time, contains no recursion with the default
>   PcdValidateOrderedCollection=FALSE setting, and the OrderedCollectionLib
>   class APIs return errors appropriately.
> 
> The OrderedCollectionLib APIs do not permit duplicates natively, but by
> using lists as collection entries, stable sorting of duplicates can be
> achieved.
> 
> 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/ShellPkg.dsc                                        |   1 +
>  ShellPkg/Include/Library/ShellCommandLib.h                   |  81 +++++
>  ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf |   1 +
>  ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h   |  19 ++
>  ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c   | 312 ++++++++++++++++++++
>  5 files changed, 414 insertions(+)

Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 05/10] UefiPayloadPkg: add OrderedCollectionLib class resolution
  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
  1 sibling, 0 replies; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-13 13:20 UTC (permalink / raw)
  To: Laszlo Ersek, devel; +Cc: Benjamin You, Guo Dong, Maurice Ma

On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> A subsequent patch in the series will make the
> 
>   ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> 
> instance dependent on the OrderedCollectionLib class. Because the shell
> binary in this platform consumes the above UefiShellCommandLib instance,
> resolve OrderedCollectionLib.
> 
> Cc: Benjamin You <benjamin.you@intel.com>
> Cc: Guo Dong <guo.dong@intel.com>
> Cc: Maurice Ma <maurice.ma@intel.com>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> ---
> 
> Notes:
>     v2:
>     - new patch
> 
>  UefiPayloadPkg/UefiPayloadPkg.dsc | 1 +
>  1 file changed, 1 insertion(+)

Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 04/10] EmulatorPkg: add OrderedCollectionLib class resolution
  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
  1 sibling, 0 replies; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-13 13:20 UTC (permalink / raw)
  To: Laszlo Ersek, devel; +Cc: Andrew Fish, Jordan Justen, Ray Ni

On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> A subsequent patch in the series will make the
> 
>   ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> 
> instance dependent on the OrderedCollectionLib class. Because the shell
> binary in this platform consumes the above UefiShellCommandLib instance,
> resolve OrderedCollectionLib.
> 
> Cc: Andrew Fish <afish@apple.com>
> Cc: Jordan Justen <jordan.l.justen@intel.com>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Cc: Ray Ni <ray.ni@intel.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> ---
> 
> Notes:
>     v2:
>     - new patch
> 
>  EmulatorPkg/EmulatorPkg.dsc | 1 +
>  1 file changed, 1 insertion(+)

Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 01/10] ShellPkg/Comp: add file buffering
  2021-01-13  8:54 ` [PATCH v2 01/10] ShellPkg/Comp: add file buffering Laszlo Ersek
@ 2021-01-13 18:42   ` Philippe Mathieu-Daudé
  0 siblings, 0 replies; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-13 18:42 UTC (permalink / raw)
  To: Laszlo Ersek, devel; +Cc: Ray Ni, Zhichao Gao

On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> The COMP shell command compares two files byte for byte. In order to
> retrieve the bytes to compare, it currently invokes
> gEfiShellProtocol->ReadFile() on both files, using a single-byte buffer
> every time. This is very inefficient; the underlying
> EFI_FILE_PROTOCOL.Read() function may be costly.
> 
> Read both file operands in chunks of "PcdShellFileOperationSize" bytes.
> Draw bytes for comparison from the internal read-ahead buffers.
> 
> Some ad-hoc measurements on my laptop, using OVMF, and the 4KB default of
> "PcdShellFileOperationSize":
> 
> - When comparing two identical 1MB files that are served by EnhancedFatDxe
>   on top of VirtioScsiDxe, this patch brings no noticeable improvement;
>   the comparison completes in <1s both before and after.
> 
> - When comparing two identical 1MB files served by VirtioFsDxe, the
>   comparison time improves from 2 minutes 25 seconds to <1s.

Wow o_O

Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>

> 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=3123
> 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/Library/UefiShellDebug1CommandsLib/UefiShellDebug1CommandsLib.inf |   1 +
>  ShellPkg/Library/UefiShellDebug1CommandsLib/Comp.c                         | 127 +++++++++++++++++++-
>  2 files changed, 125 insertions(+), 3 deletions(-)


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 08/10] ShellPkg/ShellProtocol: sort files by FullName in RemoveDupInFileList()
  2021-01-13 13:14   ` Philippe Mathieu-Daudé
@ 2021-01-14 14:19     ` Laszlo Ersek
  0 siblings, 0 replies; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-14 14:19 UTC (permalink / raw)
  To: Philippe Mathieu-Daudé, devel; +Cc: Ray Ni, Zhichao Gao

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


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 09/10] OvmfPkg: disable list length checks in NOOPT and DEBUG builds
  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é
  0 siblings, 0 replies; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-15  9:30 UTC (permalink / raw)
  To: Laszlo Ersek, devel
  Cc: Anthony Perard, Ard Biesheuvel, Jordan Justen, Julien Grall,
	Leif Lindholm, Peter Grehan, Rebecca Cran, Sami Mujawar

On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> In NOOPT and DEBUG builds, if "PcdMaximumLinkedListLength" is nonzero,
> then several LIST_ENTRY *node* APIs in BaseLib compare the *full* list
> length against the PCD.
> 
> This turns the time complexity of node-level APIs from constant to linear,
> and that of full-list manipulations from linear to quadratic.
> 
> As an example, consider the EFI_SHELL_FILE_INFO list, which is a data
> structure that's widely used in the UEFI shell. I randomly extracted 5000
> files from "/usr/include" on my laptop, spanning 1095 subdirectories out
> of 1538, and then ran "DIR -R" in the UEFI shell on this tree. These are
> the wall-clock times:
> 
>            PcdMaximumLinkedListLength  PcdMaximumLinkedListLength
>            =1,000,000                  =0
>            --------------------------  ---------------------------
> FAT        4 min 31 s                        18 s
> virtio-fs  5 min 13 s                  1 min 33 s
> 
> Checking list lengths against an arbitrary maximum (default: 1,000,000)
> seems useless even in NOOPT and DEBUG builds, while the cost is
> significant; so set the PCD to 0.
> 
> Cc: Anthony Perard <anthony.perard@citrix.com>
> Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
> Cc: Jordan Justen <jordan.l.justen@intel.com>
> Cc: Julien Grall <julien@xen.org>
> Cc: Leif Lindholm <leif@nuviainc.com>
> Cc: Peter Grehan <grehan@freebsd.org>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Cc: Rebecca Cran <rebecca@bsdio.com>
> Cc: Sami Mujawar <sami.mujawar@arm.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3152
> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
> ---
> 
> Notes:
>     v2:
>     - no changes
>     - pick up Ard's A-b
> 
>  OvmfPkg/AmdSev/AmdSevX64.dsc | 1 +
>  OvmfPkg/Bhyve/BhyveX64.dsc   | 1 +
>  OvmfPkg/OvmfPkgIa32.dsc      | 1 +
>  OvmfPkg/OvmfPkgIa32X64.dsc   | 1 +
>  OvmfPkg/OvmfPkgX64.dsc       | 1 +
>  OvmfPkg/OvmfXen.dsc          | 1 +
>  6 files changed, 6 insertions(+)

Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 10/10] ArmVirtPkg: disable list length checks in NOOPT and DEBUG builds
  2021-01-13  8:54 ` [PATCH v2 10/10] ArmVirtPkg: " Laszlo Ersek
@ 2021-01-15  9:31   ` Philippe Mathieu-Daudé
  0 siblings, 0 replies; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-15  9:31 UTC (permalink / raw)
  To: Laszlo Ersek, devel
  Cc: Ard Biesheuvel, Julien Grall, Leif Lindholm, Sami Mujawar

On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> In NOOPT and DEBUG builds, if "PcdMaximumLinkedListLength" is nonzero,
> then several LIST_ENTRY *node* APIs in BaseLib compare the *full* list
> length against the PCD.
> 
> This turns the time complexity of node-level APIs from constant to linear,
> and that of full-list manipulations from linear to quadratic.
> 
> (See some example OVMF numbers in the previous patch.)
> 
> Checking list lengths against an arbitrary maximum -- default value, and
> current ArmVirtPkg setting: 1,000,000 -- seems useless even in NOOPT and
> DEBUG builds, while the cost is significant; so set the PCD to 0.
> 
> Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
> Cc: Julien Grall <julien@xen.org>
> Cc: Leif Lindholm <leif@nuviainc.com>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Cc: Sami Mujawar <sami.mujawar@arm.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3152
> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
> ---
> 
> Notes:
>     v2:
>     - no changes
>     - pick up Ard's A-b
> 
>  ArmVirtPkg/ArmVirt.dsc.inc | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)

Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 02/10] OvmfPkg: raise PcdShellFileOperationSize to 128KB
  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
  0 siblings, 1 reply; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-15  9:34 UTC (permalink / raw)
  To: Laszlo Ersek, devel; +Cc: Ard Biesheuvel, Jordan Justen

Hi Laszlo,

On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> Some UEFI shell commands read and write files in chunks. The chunk size is
> given by "PcdShellFileOperationSize", whose default in
> "ShellPkg/ShellPkg.dec" is 4KB (0x1000).
> 
> The virtio-fs daemon of QEMU advertizes a 128KB maximum buffer size by
> default, for the FUSE_WRITE operation.

I delayed this patch review because I couldn't find where this value
is advertized in QEMU (virtiofsd is very new to me). Can you enlighten
me please?

> By raising PcdShellFileOperationSize 32-fold, the number of FUSE write
> requests shrinks proportionately, when writing large files. And when a
> Virtio Filesystem is not used, a 128KB chunk size is still not
> particularly wasteful.
> 
> Some ad-hoc measurements on my laptop, using OVMF:
> 
> - The time it takes to copy a ~270MB file from a Virtio Filesystem to the
>   same Virtio Filesystem improves from ~9 seconds to ~1 second.
> 
> - The time it takes to compare two identical ~270MB files on the same
>   Virtio Filesystem improves from ~11 seconds to ~3 seconds.
> 
> Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
> Cc: Jordan Justen <jordan.l.justen@intel.com>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3125
> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
> ---
> 
> Notes:
>     v2:
>     - no changes
>     - pick up Ard's A-b
> 
>  OvmfPkg/OvmfPkgIa32.dsc    | 2 ++
>  OvmfPkg/OvmfPkgIa32X64.dsc | 2 ++
>  OvmfPkg/OvmfPkgX64.dsc     | 2 ++
>  3 files changed, 6 insertions(+)


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 02/10] OvmfPkg: raise PcdShellFileOperationSize to 128KB
  2021-01-15  9:34   ` Philippe Mathieu-Daudé
@ 2021-01-15 10:09     ` Laszlo Ersek
  2021-01-15 15:58       ` Philippe Mathieu-Daudé
  0 siblings, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-15 10:09 UTC (permalink / raw)
  To: Philippe Mathieu-Daudé, devel; +Cc: Ard Biesheuvel, Jordan Justen

On 01/15/21 10:34, Philippe Mathieu-Daudé wrote:
> Hi Laszlo,
>
> On 1/13/21 9:54 AM, Laszlo Ersek wrote:
>> Some UEFI shell commands read and write files in chunks. The chunk size is
>> given by "PcdShellFileOperationSize", whose default in
>> "ShellPkg/ShellPkg.dec" is 4KB (0x1000).
>>
>> The virtio-fs daemon of QEMU advertizes a 128KB maximum buffer size by
>> default, for the FUSE_WRITE operation.
>
> I delayed this patch review because I couldn't find where this value
> is advertized in QEMU (virtiofsd is very new to me). Can you enlighten
> me please?

Yes, absolutely. It's really difficult to find. I actually started to
capture all that information in what would be commit 6f7bc7196ff2
("OvmfPkg/VirtioFsDxe: implement the wrapper function for FUSE_WRITE",
2020-12-21), or perhaps in this patch even -- but in the end, it was
such a divergent set of commits, originating actually in the "libfuse"
project, from which virtiofsd was forked, that I decided to drop it.

So, in virtiofsd, you actually have to look for the *page count* that
corresponds to 128KB -- FUSE_DEFAULT_MAX_PAGES_PER_REQ (32).

In the fuse_session_new() function, we have

    se->conn.max_write = UINT_MAX;
    se->bufsize = FUSE_MAX_MAX_PAGES * getpagesize() + FUSE_BUFFER_HEADER_SIZE;

In the do_init() function, which handles the FUSE_INIT request, we have

    size_t bufsize = se->bufsize;

then

    if (!(arg->flags & FUSE_MAX_PAGES)) {
        size_t max_bufsize = FUSE_DEFAULT_MAX_PAGES_PER_REQ * getpagesize() +
                             FUSE_BUFFER_HEADER_SIZE;
        if (bufsize > max_bufsize) {
            bufsize = max_bufsize;
        }
    }

and later

    if (se->conn.max_write > bufsize - FUSE_BUFFER_HEADER_SIZE) {
        se->conn.max_write = bufsize - FUSE_BUFFER_HEADER_SIZE;
    }

and then

    outarg.max_write = se->conn.max_write;

It's super convoluted, because a bunch of flags are handled, and they
all control the buffer size one way or another, and so the various
limits are converted and enforced back and forth. In practice, the
virtio-fs driver in OVMF does not set the FUSE_MAX_PAGES flag in the
FUSE_INIT request, and so in virtiofsd, we first reduce "bufsize" from

  FUSE_MAX_MAX_PAGES             * getpagesize() + FUSE_BUFFER_HEADER_SIZE;

to

  FUSE_DEFAULT_MAX_PAGES_PER_REQ * getpagesize() + FUSE_BUFFER_HEADER_SIZE;

and then calculate "max_write" by subtracting FUSE_BUFFER_HEADER_SIZE.
The result is

  FUSE_DEFAULT_MAX_PAGES_PER_REQ * getpagesize()

which is 128 KB.

In the libfuse project <https://github.com/libfuse/libfuse.git>, one
related commit is:

  https://github.com/libfuse/libfuse/commit/027d0d17c8a4

and before that,

  https://github.com/libfuse/libfuse/commit/97f4a9cb4fc69

If you try to peek even before that, you end up with historical commits
like

  https://github.com/libfuse/libfuse/commit/065f222cd5850

So basically the *origin* of max_write=128KB is untraceable :) But, at
least the present behavior can be found; it comes from libfuse commit
027d0d17c8a4.

Approaching the same topic from the FUSE client in the Linux kernel,
commit 5da784cce430 ("fuse: add max_pages to init_out", 2018-10-01) is
relevant; it also points to the following discussion on LKML:
<https://lkml.org/lkml/2012/7/5/136>.

Again it's convoluted; the direct answer to your question is,
"max_write=128KB comes from FUSE_DEFAULT_MAX_PAGES_PER_REQ, because the
FUSE_MAX_PAGES flag is not requested in the FUSE_INT operation".

Thanks,
Laszlo

>
>> By raising PcdShellFileOperationSize 32-fold, the number of FUSE write
>> requests shrinks proportionately, when writing large files. And when a
>> Virtio Filesystem is not used, a 128KB chunk size is still not
>> particularly wasteful.
>>
>> Some ad-hoc measurements on my laptop, using OVMF:
>>
>> - The time it takes to copy a ~270MB file from a Virtio Filesystem to the
>>   same Virtio Filesystem improves from ~9 seconds to ~1 second.
>>
>> - The time it takes to compare two identical ~270MB files on the same
>>   Virtio Filesystem improves from ~11 seconds to ~3 seconds.
>>
>> Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
>> Cc: Jordan Justen <jordan.l.justen@intel.com>
>> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
>> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3125
>> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
>> Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
>> ---
>>
>> Notes:
>>     v2:
>>     - no changes
>>     - pick up Ard's A-b
>>
>>  OvmfPkg/OvmfPkgIa32.dsc    | 2 ++
>>  OvmfPkg/OvmfPkgIa32X64.dsc | 2 ++
>>  OvmfPkg/OvmfPkgX64.dsc     | 2 ++
>>  3 files changed, 6 insertions(+)
>

^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 02/10] OvmfPkg: raise PcdShellFileOperationSize to 128KB
  2021-01-15 10:09     ` Laszlo Ersek
@ 2021-01-15 15:58       ` Philippe Mathieu-Daudé
  2021-01-15 18:22         ` Laszlo Ersek
  0 siblings, 1 reply; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-15 15:58 UTC (permalink / raw)
  To: Laszlo Ersek, devel; +Cc: Ard Biesheuvel, Jordan Justen

On 1/15/21 11:09 AM, Laszlo Ersek wrote:
> On 01/15/21 10:34, Philippe Mathieu-Daudé wrote:
>> On 1/13/21 9:54 AM, Laszlo Ersek wrote:
>>>
>>> The virtio-fs daemon of QEMU advertizes a 128KB maximum buffer size by
>>> default, for the FUSE_WRITE operation.
>>
>> I delayed this patch review because I couldn't find where this value
>> is advertized in QEMU (virtiofsd is very new to me). Can you enlighten
>> me please?
> 
> Yes, absolutely. It's really difficult to find. I actually started to
> capture all that information in what would be commit 6f7bc7196ff2
> ("OvmfPkg/VirtioFsDxe: implement the wrapper function for FUSE_WRITE",
> 2020-12-21), or perhaps in this patch even -- but in the end, it was
> such a divergent set of commits, originating actually in the "libfuse"
> project, from which virtiofsd was forked, that I decided to drop it.
> 
> So, in virtiofsd, you actually have to look for the *page count* that
> corresponds to 128KB -- FUSE_DEFAULT_MAX_PAGES_PER_REQ (32).
> 
> In the fuse_session_new() function, we have
> 
>     se->conn.max_write = UINT_MAX;
>     se->bufsize = FUSE_MAX_MAX_PAGES * getpagesize() + FUSE_BUFFER_HEADER_SIZE;
> 
> In the do_init() function, which handles the FUSE_INIT request, we have
> 
>     size_t bufsize = se->bufsize;
> 
> then
> 
>     if (!(arg->flags & FUSE_MAX_PAGES)) {
>         size_t max_bufsize = FUSE_DEFAULT_MAX_PAGES_PER_REQ * getpagesize() +
>                              FUSE_BUFFER_HEADER_SIZE;
>         if (bufsize > max_bufsize) {
>             bufsize = max_bufsize;
>         }
>     }
> 
> and later
> 
>     if (se->conn.max_write > bufsize - FUSE_BUFFER_HEADER_SIZE) {
>         se->conn.max_write = bufsize - FUSE_BUFFER_HEADER_SIZE;
>     }
> 
> and then
> 
>     outarg.max_write = se->conn.max_write;
> 
> It's super convoluted, because a bunch of flags are handled, and they
> all control the buffer size one way or another, and so the various
> limits are converted and enforced back and forth. In practice, the
> virtio-fs driver in OVMF does not set the FUSE_MAX_PAGES flag in the
> FUSE_INIT request, and so in virtiofsd, we first reduce "bufsize" from
> 
>   FUSE_MAX_MAX_PAGES             * getpagesize() + FUSE_BUFFER_HEADER_SIZE;
> 
> to
> 
>   FUSE_DEFAULT_MAX_PAGES_PER_REQ * getpagesize() + FUSE_BUFFER_HEADER_SIZE;
> 
> and then calculate "max_write" by subtracting FUSE_BUFFER_HEADER_SIZE.
> The result is
> 
>   FUSE_DEFAULT_MAX_PAGES_PER_REQ * getpagesize()
> 
> which is 128 KB.
> 
> 
> In the libfuse project <https://github.com/libfuse/libfuse.git>, one
> related commit is:
> 
>   https://github.com/libfuse/libfuse/commit/027d0d17c8a4
> 
> and before that,
> 
>   https://github.com/libfuse/libfuse/commit/97f4a9cb4fc69
> 
> If you try to peek even before that, you end up with historical commits
> like
> 
>   https://github.com/libfuse/libfuse/commit/065f222cd5850
> 
> So basically the *origin* of max_write=128KB is untraceable :) But, at
> least the present behavior can be found; it comes from libfuse commit
> 027d0d17c8a4.
> 
> 
> Approaching the same topic from the FUSE client in the Linux kernel,
> commit 5da784cce430 ("fuse: add max_pages to init_out", 2018-10-01) is
> relevant; it also points to the following discussion on LKML:
> <https://lkml.org/lkml/2012/7/5/136>.
> 
> Again it's convoluted; the direct answer to your question is,
> "max_write=128KB comes from FUSE_DEFAULT_MAX_PAGES_PER_REQ, because the
> FUSE_MAX_PAGES flag is not requested in the FUSE_INT operation".

Thanks a lot for the full explanation!
I'm glad I asked this early enough so this was fresh in your
memory :) At least we got it archived on the list.

Shouldn't QEMU announce this via a better mechanism? I.e. a
fw_cfg entry? This is so convoluted (as you said) than I'm
worried libfuse change a parameter and we end having a debug
nightmare figuring the root cause...

Anyhow this is not blocking this patch, so:
Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>

Regards,

Phil.


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 03/10] ArmVirtPkg: raise PcdShellFileOperationSize to 128KB
  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
  0 siblings, 1 reply; 31+ messages in thread
From: Philippe Mathieu-Daudé @ 2021-01-15 15:59 UTC (permalink / raw)
  To: Laszlo Ersek, devel; +Cc: Ard Biesheuvel, Leif Lindholm

On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> Some UEFI shell commands read and write files in chunks. The chunk size is
> given by "PcdShellFileOperationSize", whose default in
> "ShellPkg/ShellPkg.dec" is 4KB (0x1000).
> 
> The virtio-fs daemon of QEMU advertizes a 128KB maximum buffer size by
> default, for the FUSE_WRITE operation.
> 
> By raising PcdShellFileOperationSize 32-fold, the number of FUSE write
> requests shrinks proportionately, when writing large files. And when a
> Virtio Filesystem is not used, a 128KB chunk size is still not
> particularly wasteful.
> 
> Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
> Cc: Leif Lindholm <leif@nuviainc.com>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3125
> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
> ---
> 
> Notes:
>     v2:
>     - no changes
>     - pick up Ard's A-b
> 
>  ArmVirtPkg/ArmVirtQemu.dsc       | 1 +
>  ArmVirtPkg/ArmVirtQemuKernel.dsc | 1 +
>  2 files changed, 2 insertions(+)

(Similar comment that OVMF patch, QEMU should advertise properly the
maximum buffer size).

Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [PATCH v2 02/10] OvmfPkg: raise PcdShellFileOperationSize to 128KB
  2021-01-15 15:58       ` Philippe Mathieu-Daudé
@ 2021-01-15 18:22         ` Laszlo Ersek
  0 siblings, 0 replies; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-15 18:22 UTC (permalink / raw)
  To: Philippe Mathieu-Daudé, devel; +Cc: Ard Biesheuvel, Jordan Justen

Hi Phil,

On 01/15/21 16:58, Philippe Mathieu-Daudé wrote:
> On 1/15/21 11:09 AM, Laszlo Ersek wrote:
>> On 01/15/21 10:34, Philippe Mathieu-Daudé wrote:
>>> On 1/13/21 9:54 AM, Laszlo Ersek wrote:
>>>>
>>>> The virtio-fs daemon of QEMU advertizes a 128KB maximum buffer size by
>>>> default, for the FUSE_WRITE operation.
>>>
>>> I delayed this patch review because I couldn't find where this value
>>> is advertized in QEMU (virtiofsd is very new to me). Can you enlighten
>>> me please?
>>
>> Yes, absolutely. It's really difficult to find. I actually started to
>> capture all that information in what would be commit 6f7bc7196ff2
>> ("OvmfPkg/VirtioFsDxe: implement the wrapper function for FUSE_WRITE",
>> 2020-12-21), or perhaps in this patch even -- but in the end, it was
>> such a divergent set of commits, originating actually in the "libfuse"
>> project, from which virtiofsd was forked, that I decided to drop it.
>>
>> So, in virtiofsd, you actually have to look for the *page count* that
>> corresponds to 128KB -- FUSE_DEFAULT_MAX_PAGES_PER_REQ (32).
>>
>> In the fuse_session_new() function, we have
>>
>>     se->conn.max_write = UINT_MAX;
>>     se->bufsize = FUSE_MAX_MAX_PAGES * getpagesize() + FUSE_BUFFER_HEADER_SIZE;
>>
>> In the do_init() function, which handles the FUSE_INIT request, we have
>>
>>     size_t bufsize = se->bufsize;
>>
>> then
>>
>>     if (!(arg->flags & FUSE_MAX_PAGES)) {
>>         size_t max_bufsize = FUSE_DEFAULT_MAX_PAGES_PER_REQ * getpagesize() +
>>                              FUSE_BUFFER_HEADER_SIZE;
>>         if (bufsize > max_bufsize) {
>>             bufsize = max_bufsize;
>>         }
>>     }
>>
>> and later
>>
>>     if (se->conn.max_write > bufsize - FUSE_BUFFER_HEADER_SIZE) {
>>         se->conn.max_write = bufsize - FUSE_BUFFER_HEADER_SIZE;
>>     }
>>
>> and then
>>
>>     outarg.max_write = se->conn.max_write;
>>
>> It's super convoluted, because a bunch of flags are handled, and they
>> all control the buffer size one way or another, and so the various
>> limits are converted and enforced back and forth. In practice, the
>> virtio-fs driver in OVMF does not set the FUSE_MAX_PAGES flag in the
>> FUSE_INIT request, and so in virtiofsd, we first reduce "bufsize" from
>>
>>   FUSE_MAX_MAX_PAGES             * getpagesize() + FUSE_BUFFER_HEADER_SIZE;
>>
>> to
>>
>>   FUSE_DEFAULT_MAX_PAGES_PER_REQ * getpagesize() + FUSE_BUFFER_HEADER_SIZE;
>>
>> and then calculate "max_write" by subtracting FUSE_BUFFER_HEADER_SIZE.
>> The result is
>>
>>   FUSE_DEFAULT_MAX_PAGES_PER_REQ * getpagesize()
>>
>> which is 128 KB.
>>
>>
>> In the libfuse project <https://github.com/libfuse/libfuse.git>, one
>> related commit is:
>>
>>   https://github.com/libfuse/libfuse/commit/027d0d17c8a4
>>
>> and before that,
>>
>>   https://github.com/libfuse/libfuse/commit/97f4a9cb4fc69
>>
>> If you try to peek even before that, you end up with historical commits
>> like
>>
>>   https://github.com/libfuse/libfuse/commit/065f222cd5850
>>
>> So basically the *origin* of max_write=128KB is untraceable :) But, at
>> least the present behavior can be found; it comes from libfuse commit
>> 027d0d17c8a4.
>>
>>
>> Approaching the same topic from the FUSE client in the Linux kernel,
>> commit 5da784cce430 ("fuse: add max_pages to init_out", 2018-10-01) is
>> relevant; it also points to the following discussion on LKML:
>> <https://lkml.org/lkml/2012/7/5/136>.
>>
>> Again it's convoluted; the direct answer to your question is,
>> "max_write=128KB comes from FUSE_DEFAULT_MAX_PAGES_PER_REQ, because the
>> FUSE_MAX_PAGES flag is not requested in the FUSE_INT operation".
> 
> Thanks a lot for the full explanation!
> I'm glad I asked this early enough so this was fresh in your
> memory :) At least we got it archived on the list.
> 
> Shouldn't QEMU announce this via a better mechanism? I.e. a
> fw_cfg entry? This is so convoluted (as you said) than I'm
> worried libfuse change a parameter and we end having a debug
> nightmare figuring the root cause...

Wait, I think you don't have the full picture.

(1) In the FUSE_INIT *response*, virtiofsd advertizes "max_write". This
value is critically important to the virtio-fs driver in OVMF
(OvmfPkg/VirtioFsDxe), and indeed said driver adheres to this limit
closely. When the driver serves an EFI_FILE_PROTOCOL.Write() request, it
breaks the write into chunks of "max_write" bytes, for individual
FUSE_WRITE operations to be sent to virtiofsd.

Please refer to edk2 commits

- 6f7bc7196ff2 ("OvmfPkg/VirtioFsDxe: implement the wrapper function for
FUSE_WRITE", 2020-12-21), and

- 44f43f94cebe ("OvmfPkg/VirtioFsDxe: implement
EFI_FILE_PROTOCOL.Write()", 2020-12-21).

In fact, max_write=128KB is obvious; the reason for that is that the
virtiofsd log contains this value, when the FUSE_INIT request is
processed and answered.

This is one half of the picture -- the important half.

(2) The much less important half is this patch. This patch is a "best
effort" optimization, based on the *empirical value* of 128KB that's
advertized for max_write.

If virtiofsd were modified and it changed the max_write default to 64KB
or 256KB, then this PCD setting would no longer match. But, that would
not be a tragedy, exactly how it is not a tragedy *right now* that the
current PCD setting is 4KB. The patch is a small, static optimization
based on empirical data. It is not foolproof, and it doesn't *have* to be.

So, the complexity is entirely hidden in how virtiofsd calculates the
128 KB value for max_write. That's in fact a virtiofsd implementation
detail. What matters is that the OVMF driver for virtio-fs sees
max_write=128KB *clearly announced* in the FUSE_INIT response, and that
the driver rigorously honors that limit.

Conversely, the present patch is absolutely secondary; it is a "low
hanging fruit", ad-hoc optimization, at a higher level. The PCD change
affects e.g. the CP command in the UEFI shell, even if you only use a
FAT filesystem. In that case, the PCD change is entirely pointless --
but it does not hurt, and the change is still very simple.

It's unreasonable to expect that the CP command flexibly adhere to the
optimal / maximal write size for the particular filesystem it is writing
to. That's not the job of the CP command -- it is the job of the
filesystem driver under CP. But, by increasing the buffer size of CP
(and of some other UEFI shell commands that work with files), based on
some empirical data, we *permit* the virtio-fs driver to work better
under CP -- without harming CP on filesystems different from virtio-fs.
As the commit message says, "And when a Virtio Filesystem is not used, a
128KB chunk size is still not particularly wasteful".

> 
> Anyhow this is not blocking this patch, so:
> Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>

Thanks!
Laszlo

^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [edk2-devel] [PATCH v2 03/10] ArmVirtPkg: raise PcdShellFileOperationSize to 128KB
  2021-01-15 15:59   ` Philippe Mathieu-Daudé
@ 2021-01-15 19:03     ` Laszlo Ersek
  0 siblings, 0 replies; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-15 19:03 UTC (permalink / raw)
  To: devel, philmd; +Cc: Ard Biesheuvel, Leif Lindholm

On 01/15/21 16:59, Philippe Mathieu-Daudé wrote:
> On 1/13/21 9:54 AM, Laszlo Ersek wrote:
>> Some UEFI shell commands read and write files in chunks. The chunk size is
>> given by "PcdShellFileOperationSize", whose default in
>> "ShellPkg/ShellPkg.dec" is 4KB (0x1000).
>>
>> The virtio-fs daemon of QEMU advertizes a 128KB maximum buffer size by
>> default, for the FUSE_WRITE operation.
>>
>> By raising PcdShellFileOperationSize 32-fold, the number of FUSE write
>> requests shrinks proportionately, when writing large files. And when a
>> Virtio Filesystem is not used, a 128KB chunk size is still not
>> particularly wasteful.
>>
>> Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
>> Cc: Leif Lindholm <leif@nuviainc.com>
>> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
>> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3125
>> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
>> Acked-by: Ard Biesheuvel <ard.biesheuvel@arm.com>
>> ---
>>
>> Notes:
>>     v2:
>>     - no changes
>>     - pick up Ard's A-b
>>
>>  ArmVirtPkg/ArmVirtQemu.dsc       | 1 +
>>  ArmVirtPkg/ArmVirtQemuKernel.dsc | 1 +
>>  2 files changed, 2 insertions(+)
> 
> (Similar comment that OVMF patch, QEMU should advertise properly the
> maximum buffer size).

It does! :)

> Reviewed-by: Philippe Mathieu-Daude <philmd@redhat.com>

Thanks!
Laszlo

> 
> 
> 
> 
> 
> 


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [edk2-devel] [PATCH v2 04/10] EmulatorPkg: add OrderedCollectionLib class resolution
  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   ` Laszlo Ersek
  2021-01-19  7:55     ` 回复: " gaoliming
  1 sibling, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-18 16:48 UTC (permalink / raw)
  To: devel; +Cc: Andrew Fish, Jordan Justen, Philippe Mathieu-Daudé, Ray Ni

Ping -- Ray, can you please check this?; it's a one-liner patch.

Thanks.
Laszlo

On 01/13/21 09:54, Laszlo Ersek wrote:
> A subsequent patch in the series will make the
> 
>   ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> 
> instance dependent on the OrderedCollectionLib class. Because the shell
> binary in this platform consumes the above UefiShellCommandLib instance,
> resolve OrderedCollectionLib.
> 
> Cc: Andrew Fish <afish@apple.com>
> Cc: Jordan Justen <jordan.l.justen@intel.com>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Cc: Ray Ni <ray.ni@intel.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> ---
> 
> Notes:
>     v2:
>     - new patch
> 
>  EmulatorPkg/EmulatorPkg.dsc | 1 +
>  1 file changed, 1 insertion(+)
> 
> diff --git a/EmulatorPkg/EmulatorPkg.dsc b/EmulatorPkg/EmulatorPkg.dsc
> index de8144844c57..9ecc37334305 100644
> --- a/EmulatorPkg/EmulatorPkg.dsc
> +++ b/EmulatorPkg/EmulatorPkg.dsc
> @@ -453,6 +453,7 @@ [Components]
>        NULL|ShellPkg/Library/UefiShellInstall1CommandsLib/UefiShellInstall1CommandsLib.inf
>        NULL|ShellPkg/Library/UefiShellNetwork1CommandsLib/UefiShellNetwork1CommandsLib.inf
>        HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingLib.inf
> +      OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.inf
>        SortLib|MdeModulePkg/Library/UefiSortLib/UefiSortLib.inf
>        PrintLib|MdePkg/Library/BasePrintLib/BasePrintLib.inf
>  #      SafeBlockIoLib|ShellPkg/Library/SafeBlockIoLib/SafeBlockIoLib.inf
> 


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [edk2-devel] [PATCH v2 05/10] UefiPayloadPkg: add OrderedCollectionLib class resolution
  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   ` Laszlo Ersek
  2021-01-19  4:29     ` Guo Dong
  1 sibling, 1 reply; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-18 16:48 UTC (permalink / raw)
  To: devel; +Cc: Benjamin You, Guo Dong, Maurice Ma, Philippe Mathieu-Daudé

Ping -- Benjamin, Guo, Maurice, this is a one-liner for UefiPayloadPkg;
please approve.

Thanks
Laszlo

On 01/13/21 09:54, Laszlo Ersek wrote:
> A subsequent patch in the series will make the
> 
>   ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> 
> instance dependent on the OrderedCollectionLib class. Because the shell
> binary in this platform consumes the above UefiShellCommandLib instance,
> resolve OrderedCollectionLib.
> 
> Cc: Benjamin You <benjamin.you@intel.com>
> Cc: Guo Dong <guo.dong@intel.com>
> Cc: Maurice Ma <maurice.ma@intel.com>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
> Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> ---
> 
> Notes:
>     v2:
>     - new patch
> 
>  UefiPayloadPkg/UefiPayloadPkg.dsc | 1 +
>  1 file changed, 1 insertion(+)
> 
> diff --git a/UefiPayloadPkg/UefiPayloadPkg.dsc b/UefiPayloadPkg/UefiPayloadPkg.dsc
> index ae62a9c4d66b..24dab157f1ef 100644
> --- a/UefiPayloadPkg/UefiPayloadPkg.dsc
> +++ b/UefiPayloadPkg/UefiPayloadPkg.dsc
> @@ -556,6 +556,7 @@ [Components.X64]
>        DebugLib|MdePkg/Library/UefiDebugLibConOut/UefiDebugLibConOut.inf
>        DevicePathLib|MdePkg/Library/UefiDevicePathLib/UefiDevicePathLib.inf
>        HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingLib.inf
> +      OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.inf
>        PcdLib|MdePkg/Library/DxePcdLib/DxePcdLib.inf
>        ShellCEntryLib|ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf
>        ShellCommandLib|ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> 


^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [edk2-devel] [PATCH v2 05/10] UefiPayloadPkg: add OrderedCollectionLib class resolution
  2021-01-18 16:48   ` [edk2-devel] " Laszlo Ersek
@ 2021-01-19  4:29     ` Guo Dong
  0 siblings, 0 replies; 31+ messages in thread
From: Guo Dong @ 2021-01-19  4:29 UTC (permalink / raw)
  To: devel@edk2.groups.io, lersek@redhat.com
  Cc: You, Benjamin, Ma, Maurice, Philippe Mathieu-Daudé


Reviewed-by: Guo Dong <guo.dong@intel.com>

> -----Original Message-----
> From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of Laszlo
> Ersek
> Sent: Monday, January 18, 2021 9:49 AM
> To: devel@edk2.groups.io
> Cc: You, Benjamin <benjamin.you@intel.com>; Dong, Guo
> <guo.dong@intel.com>; Ma, Maurice <maurice.ma@intel.com>; Philippe
> Mathieu-Daudé <philmd@redhat.com>
> Subject: Re: [edk2-devel] [PATCH v2 05/10] UefiPayloadPkg: add
> OrderedCollectionLib class resolution
> 
> Ping -- Benjamin, Guo, Maurice, this is a one-liner for UefiPayloadPkg;
> please approve.
> 
> Thanks
> Laszlo
> 
> On 01/13/21 09:54, Laszlo Ersek wrote:
> > A subsequent patch in the series will make the
> >
> >   ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> >
> > instance dependent on the OrderedCollectionLib class. Because the shell
> > binary in this platform consumes the above UefiShellCommandLib instance,
> > resolve OrderedCollectionLib.
> >
> > Cc: Benjamin You <benjamin.you@intel.com>
> > Cc: Guo Dong <guo.dong@intel.com>
> > Cc: Maurice Ma <maurice.ma@intel.com>
> > Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> > Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
> > Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> > ---
> >
> > Notes:
> >     v2:
> >     - new patch
> >
> >  UefiPayloadPkg/UefiPayloadPkg.dsc | 1 +
> >  1 file changed, 1 insertion(+)
> >
> > diff --git a/UefiPayloadPkg/UefiPayloadPkg.dsc
> b/UefiPayloadPkg/UefiPayloadPkg.dsc
> > index ae62a9c4d66b..24dab157f1ef 100644
> > --- a/UefiPayloadPkg/UefiPayloadPkg.dsc
> > +++ b/UefiPayloadPkg/UefiPayloadPkg.dsc
> > @@ -556,6 +556,7 @@ [Components.X64]
> >
> DebugLib|MdePkg/Library/UefiDebugLibConOut/UefiDebugLibConOut.inf
> >        DevicePathLib|MdePkg/Library/UefiDevicePathLib/UefiDevicePathLib.inf
> >
> HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingLib
> .inf
> > +
> OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib
> /BaseOrderedCollectionRedBlackTreeLib.inf
> >        PcdLib|MdePkg/Library/DxePcdLib/DxePcdLib.inf
> >        ShellCEntryLib|ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf
> >
> ShellCommandLib|ShellPkg/Library/UefiShellCommandLib/UefiShellCommandL
> ib.inf
> >
> 
> 
> 
> 
> 


^ permalink raw reply	[flat|nested] 31+ messages in thread

* 回复: [edk2-devel] [PATCH v2 04/10] EmulatorPkg: add OrderedCollectionLib class resolution
  2021-01-18 16:48   ` [edk2-devel] " Laszlo Ersek
@ 2021-01-19  7:55     ` gaoliming
  0 siblings, 0 replies; 31+ messages in thread
From: gaoliming @ 2021-01-19  7:55 UTC (permalink / raw)
  To: devel, lersek
  Cc: 'Andrew Fish', 'Jordan Justen',
	'Philippe Mathieu-Daudé', 'Ray Ni'

Acked-by: Liming Gao <gaoliming@byosoft.com.cn>

> -----邮件原件-----
> 发件人: bounce+27952+70500+4905953+8761045@groups.io
> <bounce+27952+70500+4905953+8761045@groups.io> 代表 Laszlo Ersek
> 发送时间: 2021年1月19日 0:48
> 收件人: devel@edk2.groups.io
> 抄送: Andrew Fish <afish@apple.com>; Jordan Justen
> <jordan.l.justen@intel.com>; Philippe Mathieu-Daudé
> <philmd@redhat.com>; Ray Ni <ray.ni@intel.com>
> 主题: Re: [edk2-devel] [PATCH v2 04/10] EmulatorPkg: add
> OrderedCollectionLib class resolution
> 
> Ping -- Ray, can you please check this?; it's a one-liner patch.
> 
> Thanks.
> Laszlo
> 
> On 01/13/21 09:54, Laszlo Ersek wrote:
> > A subsequent patch in the series will make the
> >
> >   ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> >
> > instance dependent on the OrderedCollectionLib class. Because the shell
> > binary in this platform consumes the above UefiShellCommandLib instance,
> > resolve OrderedCollectionLib.
> >
> > Cc: Andrew Fish <afish@apple.com>
> > Cc: Jordan Justen <jordan.l.justen@intel.com>
> > Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> > Cc: Ray Ni <ray.ni@intel.com>
> > Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
> > Signed-off-by: Laszlo Ersek <lersek@redhat.com>
> > ---
> >
> > Notes:
> >     v2:
> >     - new patch
> >
> >  EmulatorPkg/EmulatorPkg.dsc | 1 +
> >  1 file changed, 1 insertion(+)
> >
> > diff --git a/EmulatorPkg/EmulatorPkg.dsc b/EmulatorPkg/EmulatorPkg.dsc
> > index de8144844c57..9ecc37334305 100644
> > --- a/EmulatorPkg/EmulatorPkg.dsc
> > +++ b/EmulatorPkg/EmulatorPkg.dsc
> > @@ -453,6 +453,7 @@ [Components]
> >
> NULL|ShellPkg/Library/UefiShellInstall1CommandsLib/UefiShellInstall1Com
> mandsLib.inf
> >
> NULL|ShellPkg/Library/UefiShellNetwork1CommandsLib/UefiShellNetwork1
> CommandsLib.inf
> >
> HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingL
> ib.inf
> > +
> OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeLi
> b/BaseOrderedCollectionRedBlackTreeLib.inf
> >        SortLib|MdeModulePkg/Library/UefiSortLib/UefiSortLib.inf
> >        PrintLib|MdePkg/Library/BasePrintLib/BasePrintLib.inf
> >  #
> SafeBlockIoLib|ShellPkg/Library/SafeBlockIoLib/SafeBlockIoLib.inf
> >
> 
> 
> 
> 
> 




^ permalink raw reply	[flat|nested] 31+ messages in thread

* Re: [edk2-devel] [PATCH v2 00/10] multiple packages: shell usability improvements
  2021-01-13  8:54 [PATCH v2 00/10] multiple packages: shell usability improvements Laszlo Ersek
                   ` (9 preceding siblings ...)
  2021-01-13  8:54 ` [PATCH v2 10/10] ArmVirtPkg: " Laszlo Ersek
@ 2021-01-19 18:39 ` Laszlo Ersek
  10 siblings, 0 replies; 31+ messages in thread
From: Laszlo Ersek @ 2021-01-19 18:39 UTC (permalink / raw)
  To: devel
  Cc: Andrew Fish, Anthony Perard, Ard Biesheuvel, Benjamin You,
	Guo Dong, Jordan Justen, Julien Grall, Leif Lindholm, Maurice Ma,
	Peter Grehan, Philippe Mathieu-Daudé, Ray Ni, Rebecca Cran,
	Sami Mujawar, Zhichao Gao

On 01/13/21 09:54, Laszlo Ersek wrote:
> Repo:   https://pagure.io/lersek/edk2.git
> Branch: shell_usability_improvements_v2
> 
> Changes in v2:
> 
> - no code changes in any of the v1 patches,
> 
> - pick up v1 feedback tags from Ard and Zhichao,
> 
> - add two new patches, for resolving OrderedCollectionLib in EmulatorPkg
>   and UefiPayloadPkg.

Merged as commit range e68c2a22caae..6e5586863148, via
<https://github.com/tianocore/edk2/pull/1370>.

Thanks for the reviews; especially thanks to Phil for reviewing the
whole series!

Laszlo

> 
> Additionally, I have posted the following pre-requisite series, for
> edk2-platforms:
> 
>   [edk2-devel] [edk2-platforms PATCH 0/3]
>   add OrderedCollectionLib class resolution
> 
>   https://www.redhat.com/archives/edk2-devel-archive/2021-January/msg00694.html
>   https://edk2.groups.io/g/devel/message/70210
>   Message-Id: <20210113082843.9095-1-lersek@redhat.com>
> 
> The v1 posting was at:
> 
>   https://edk2.groups.io/g/devel/message/69590
>   https://www.redhat.com/archives/edk2-devel-archive/2021-January/msg00070.html
>   Message-Id: <20210104154235.31785-1-lersek@redhat.com>
> 
> v1 blurb:
> 
> This series addresses various usability shortcomings that I've recently
> run into, while working with large directory trees on FAT and/or
> virtio-fs in the UEFI shell.
> 
> * add file buffering to the COMP command
>   https://bugzilla.tianocore.org/show_bug.cgi?id=3123
> 
> * ArmVirtPkg, OvmfPkg: set PcdShellFileOperationSize to 0x20000
>   https://bugzilla.tianocore.org/show_bug.cgi?id=3125
> 
> * Shell: pathname / filename sorting
>   https://bugzilla.tianocore.org/show_bug.cgi?id=3151
> 
> * ArmVirtPkg, OvmfPkg: disable list length checks in NOOPT and DEBUG
>   builds
>   https://bugzilla.tianocore.org/show_bug.cgi?id=3152
> 
> Beyond testing the series locally, I've also heavily subjected it to
> local CI runs, including ECC (relevant for ShellPkg).
> 
> Cc: Andrew Fish <afish@apple.com>
> Cc: Anthony Perard <anthony.perard@citrix.com>
> Cc: Ard Biesheuvel <ard.biesheuvel@arm.com>
> Cc: Benjamin You <benjamin.you@intel.com>
> Cc: Guo Dong <guo.dong@intel.com>
> Cc: Jordan Justen <jordan.l.justen@intel.com>
> Cc: Julien Grall <julien@xen.org>
> Cc: Leif Lindholm <leif@nuviainc.com>
> Cc: Maurice Ma <maurice.ma@intel.com>
> Cc: Peter Grehan <grehan@freebsd.org>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Rebecca Cran <rebecca@bsdio.com>
> Cc: Sami Mujawar <sami.mujawar@arm.com>
> Cc: Zhichao Gao <zhichao.gao@intel.com>
> 
> Thanks
> Laszlo
> 
> Laszlo Ersek (10):
>   ShellPkg/Comp: add file buffering
>   OvmfPkg: raise PcdShellFileOperationSize to 128KB
>   ArmVirtPkg: raise PcdShellFileOperationSize to 128KB
>   EmulatorPkg: add OrderedCollectionLib class resolution
>   UefiPayloadPkg: add OrderedCollectionLib class resolution
>   ShellPkg/ShellCommandLib: add ShellSortFileList()
>   ShellPkg/Ls: sort output by FileName in non-SFO mode
>   ShellPkg/ShellProtocol: sort files by FullName in
>     RemoveDupInFileList()
>   OvmfPkg: disable list length checks in NOOPT and DEBUG builds
>   ArmVirtPkg: disable list length checks in NOOPT and DEBUG builds
> 
>  ArmVirtPkg/ArmVirt.dsc.inc                                                 |   2 +-
>  ArmVirtPkg/ArmVirtQemu.dsc                                                 |   1 +
>  ArmVirtPkg/ArmVirtQemuKernel.dsc                                           |   1 +
>  EmulatorPkg/EmulatorPkg.dsc                                                |   1 +
>  OvmfPkg/AmdSev/AmdSevX64.dsc                                               |   1 +
>  OvmfPkg/Bhyve/BhyveX64.dsc                                                 |   1 +
>  OvmfPkg/OvmfPkgIa32.dsc                                                    |   3 +
>  OvmfPkg/OvmfPkgIa32X64.dsc                                                 |   3 +
>  OvmfPkg/OvmfPkgX64.dsc                                                     |   3 +
>  OvmfPkg/OvmfXen.dsc                                                        |   1 +
>  ShellPkg/Application/Shell/ShellProtocol.c                                 |  16 +
>  ShellPkg/Include/Library/ShellCommandLib.h                                 |  81 +++++
>  ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c                 | 312 ++++++++++++++++++++
>  ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h                 |  19 ++
>  ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf               |   1 +
>  ShellPkg/Library/UefiShellDebug1CommandsLib/Comp.c                         | 127 +++++++-
>  ShellPkg/Library/UefiShellDebug1CommandsLib/UefiShellDebug1CommandsLib.inf |   1 +
>  ShellPkg/Library/UefiShellLevel2CommandsLib/Ls.c                           |  14 +
>  ShellPkg/ShellPkg.dsc                                                      |   1 +
>  UefiPayloadPkg/UefiPayloadPkg.dsc                                          |   1 +
>  20 files changed, 586 insertions(+), 4 deletions(-)
> 
> 
> base-commit: ebfe2d3eb5ac7fd92d74011edb31303a181920c7
> 


^ permalink raw reply	[flat|nested] 31+ messages in thread

end of thread, other threads:[~2021-01-19 18:39 UTC | newest]

Thread overview: 31+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
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
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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox