public inbox for devel@edk2.groups.io
 help / color / mirror / Atom feed
* [PATCH v2 0/3] Add function QuickSort into MdePkg/BaseLib
@ 2021-10-15 23:25 IanX Kuo
  2021-10-15 23:25 ` [PATCH v2 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
                   ` (2 more replies)
  0 siblings, 3 replies; 6+ messages in thread
From: IanX Kuo @ 2021-10-15 23:25 UTC (permalink / raw)
  To: devel; +Cc: amy.chan, ray.ni, IanX Kuo

From: IanX Kuo <ianx.kuo@intel.com>

1. MdeModulePkg/SortLib: Use QuickSort instead of QuickSortWorker
1-1: Drop cast (V2)

2. CryptLib/CryptLib: Remove duplicate QuickSortWorker
3. CpuCacheInfoLib: Remove MdeModulePkg dependency
3-1: Drop cast (V2)
3-2: Add runtime check (V2)

IanX Kuo (3):
  MdeModulePkg/SortLib: Add QuickSort function on BaseLib
  CryptoPkg/CryptLib: Add QuickSort function on BaseLib
  UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib

 .../Library/BaseCryptLib/SysCall/CrtWrapper.c |  92 +-------------
 .../Library/BaseSortLib/BaseSortLib.c         | 115 +----------------
 .../Library/UefiSortLib/UefiSortLib.c         | 116 +-----------------
 .../Library/CpuCacheInfoLib/CpuCacheInfoLib.c |   9 +-
 .../CpuCacheInfoLib/DxeCpuCacheInfoLib.inf    |   2 -
 .../CpuCacheInfoLib/InternalCpuCacheInfoLib.h |   1 -
 .../CpuCacheInfoLib/PeiCpuCacheInfoLib.inf    |   2 -
 7 files changed, 18 insertions(+), 319 deletions(-)

-- 
2.30.0.windows.1


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

* [PATCH v2 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
  2021-10-15 23:25 [PATCH v2 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
@ 2021-10-15 23:25 ` IanX Kuo
  2021-10-15 23:25 ` [PATCH v2 2/3] CryptoPkg/CryptLib: " IanX Kuo
  2021-10-15 23:25 ` [PATCH v2 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
  2 siblings, 0 replies; 6+ messages in thread
From: IanX Kuo @ 2021-10-15 23:25 UTC (permalink / raw)
  To: devel; +Cc: amy.chan, ray.ni, IanX Kuo, Jian J Wang, Liming Gao

From: IanX Kuo <ianx.kuo@intel.com>

REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675

Use QuickSort instead of QuickSortWorker

Cc: Ray Ni <ray.ni@intel.com>
Cc: Jian J Wang <jian.j.wang@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
 .../Library/BaseSortLib/BaseSortLib.c         | 115 +----------------
 .../Library/UefiSortLib/UefiSortLib.c         | 116 +-----------------
 2 files changed, 8 insertions(+), 223 deletions(-)

diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec..0903943ee4 100644
--- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
+++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
@@ -1,7 +1,7 @@
 /** @file
   Library used for sorting routines.
 
-  Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>
+  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
   SPDX-License-Identifier: BSD-2-Clause-Patent
 
 **/
@@ -13,114 +13,6 @@
 #include <Library/MemoryAllocationLib.h>
 #include <Library/SortLib.h>
 
-/**
-  Worker function for QuickSorting.  This function is identical to PerformQuickSort,
-  except that is uses the pre-allocated buffer so the in place sorting does not need to
-  allocate and free buffers constantly.
-
-  Each element must be equal sized.
-
-  if BufferToSort is NULL, then ASSERT.
-  if CompareFunction is NULL, then ASSERT.
-  if Buffer is NULL, then ASSERT.
-
-  if Count is < 2 then perform no action.
-  if Size is < 1 then perform no action.
-
-  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
-                                 on return a buffer of sorted elements
-  @param[in] Count               the number of elements in the buffer to sort
-  @param[in] ElementSize         Size of an element in bytes
-  @param[in] CompareFunction     The function to call to perform the comparison
-                                 of any 2 elements
-  @param[in] Buffer              Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-QuickSortWorker (
-  IN OUT VOID                           *BufferToSort,
-  IN CONST UINTN                        Count,
-  IN CONST UINTN                        ElementSize,
-  IN       SORT_COMPARE                 CompareFunction,
-  IN VOID                               *Buffer
-  )
-{
-  VOID        *Pivot;
-  UINTN       LoopCount;
-  UINTN       NextSwapLocation;
-
-  ASSERT(BufferToSort     != NULL);
-  ASSERT(CompareFunction  != NULL);
-  ASSERT(Buffer  != NULL);
-
-  if ( Count < 2
-    || ElementSize  < 1
-   ){
-    return;
-  }
-
-  NextSwapLocation = 0;
-
-  //
-  // pick a pivot (we choose last element)
-  //
-  Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));
-
-  //
-  // Now get the pivot such that all on "left" are below it
-  // and everything "right" are above it
-  //
-  for ( LoopCount = 0
-      ; LoopCount < Count -1
-      ; LoopCount++
-     ){
-    //
-    // if the element is less than the pivot
-    //
-    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
-      //
-      // swap
-      //
-      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
-      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
-
-      //
-      // increment NextSwapLocation
-      //
-      NextSwapLocation++;
-    }
-  }
-  //
-  // swap pivot to it's final position (NextSwapLocaiton)
-  //
-  CopyMem (Buffer, Pivot, ElementSize);
-  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
-  //
-  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element
-  // IE list is sorted left half, pivot element, sorted right half...
-  //
-  if (NextSwapLocation >= 2) {
-    QuickSortWorker(
-      BufferToSort,
-      NextSwapLocation,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-
-  if ((Count - NextSwapLocation - 1) >= 2) {
-    QuickSortWorker(
-      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
-      Count - NextSwapLocation - 1,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-  return;
-}
 /**
   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 
@@ -156,12 +48,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);
   ASSERT(Buffer != NULL);
 
-  QuickSortWorker(
+  QuickSort (
     BufferToSort,
     Count,
     ElementSize,
     CompareFunction,
-    Buffer);
+    Buffer
+    );
 
   FreePool(Buffer);
   return;
diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
index 46dc443638..29d8735c22 100644
--- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
+++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
@@ -1,7 +1,7 @@
 /** @file
   Library used for sorting routines.
 
-  Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>
+  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
   SPDX-License-Identifier: BSD-2-Clause-Patent
 
 **/
@@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL   *mUnicodeCollation = NULL;
   }                                   \
 }
 
-/**
-  Worker function for QuickSorting.  This function is identical to PerformQuickSort,
-  except that is uses the pre-allocated buffer so the in place sorting does not need to
-  allocate and free buffers constantly.
-
-  Each element must be equal sized.
-
-  if BufferToSort is NULL, then ASSERT.
-  if CompareFunction is NULL, then ASSERT.
-  if Buffer is NULL, then ASSERT.
-
-  if Count is < 2 then perform no action.
-  if Size is < 1 then perform no action.
-
-  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
-                                 on return a buffer of sorted elements
-  @param[in] Count               the number of elements in the buffer to sort
-  @param[in] ElementSize         Size of an element in bytes
-  @param[in] CompareFunction     The function to call to perform the comparison
-                                 of any 2 elements
-  @param[in] Buffer              Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-QuickSortWorker (
-  IN OUT VOID                           *BufferToSort,
-  IN CONST UINTN                        Count,
-  IN CONST UINTN                        ElementSize,
-  IN       SORT_COMPARE                 CompareFunction,
-  IN VOID                               *Buffer
-  )
-{
-  VOID        *Pivot;
-  UINTN       LoopCount;
-  UINTN       NextSwapLocation;
-
-  ASSERT(BufferToSort     != NULL);
-  ASSERT(CompareFunction  != NULL);
-  ASSERT(Buffer  != NULL);
-
-  if ( Count < 2
-    || ElementSize  < 1
-   ){
-    return;
-  }
-
-  NextSwapLocation = 0;
-
-  //
-  // pick a pivot (we choose last element)
-  //
-  Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));
-
-  //
-  // Now get the pivot such that all on "left" are below it
-  // and everything "right" are above it
-  //
-  for ( LoopCount = 0
-      ; LoopCount < Count -1
-      ; LoopCount++
-     ){
-    //
-    // if the element is less than the pivot
-    //
-    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
-      //
-      // swap
-      //
-      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
-      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
-
-      //
-      // increment NextSwapLocation
-      //
-      NextSwapLocation++;
-    }
-  }
-  //
-  // swap pivot to it's final position (NextSwapLocaiton)
-  //
-  CopyMem (Buffer, Pivot, ElementSize);
-  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
-  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
-  //
-  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element
-  // IE list is sorted left half, pivot element, sorted right half...
-  //
-  if (NextSwapLocation >= 2) {
-    QuickSortWorker(
-      BufferToSort,
-      NextSwapLocation,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-
-  if ((Count - NextSwapLocation - 1) >= 2) {
-    QuickSortWorker(
-      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
-      Count - NextSwapLocation - 1,
-      ElementSize,
-      CompareFunction,
-      Buffer);
-  }
-
-  return;
-}
 /**
   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 
@@ -173,12 +64,13 @@ PerformQuickSort (
   Buffer = AllocateZeroPool(ElementSize);
   ASSERT(Buffer != NULL);
 
-  QuickSortWorker(
+  QuickSort (
     BufferToSort,
     Count,
     ElementSize,
     CompareFunction,
-    Buffer);
+    Buffer
+    );
 
   FreePool(Buffer);
   return;
-- 
2.30.0.windows.1


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

* [PATCH v2 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
  2021-10-15 23:25 [PATCH v2 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
  2021-10-15 23:25 ` [PATCH v2 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
@ 2021-10-15 23:25 ` IanX Kuo
  2021-10-16 14:59   ` [edk2-devel] " Marvin Häuser
  2021-10-15 23:25 ` [PATCH v2 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
  2 siblings, 1 reply; 6+ messages in thread
From: IanX Kuo @ 2021-10-15 23:25 UTC (permalink / raw)
  To: devel
  Cc: amy.chan, ray.ni, IanX Kuo, Jiewen Yao, Jian J Wang, Xiaoyu Lu,
	Guomin Jiang

From: IanX Kuo <ianx.kuo@intel.com>

REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675

Use QuickSort instead of QuickSortWorker

Cc: Ray Ni <ray.ni@intel.com>
Cc: Jiewen Yao <jiewen.yao@intel.com>
Cc: Jian J Wang <jian.j.wang@intel.com>
Cc: Xiaoyu Lu <xiaoyux.lu@intel.com>
Cc: Guomin Jiang <guomin.jiang@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
 .../Library/BaseCryptLib/SysCall/CrtWrapper.c | 92 +------------------
 1 file changed, 2 insertions(+), 90 deletions(-)

diff --git a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
index 42235ab96a..b10edaae5b 100644
--- a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
+++ b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
@@ -2,7 +2,7 @@
   C Run-Time Libraries (CRT) Wrapper Implementation for OpenSSL-based
   Cryptographic Library.
 
-Copyright (c) 2009 - 2017, Intel Corporation. All rights reserved.<BR>
+Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.<BR>
 SPDX-License-Identifier: BSD-2-Clause-Patent
 
 **/
@@ -22,91 +22,6 @@ int
   IN  VOID  *Buffer2
   );
 
-//
-// Duplicated from EDKII BaseSortLib for qsort() wrapper
-//
-STATIC
-VOID
-QuickSortWorker (
-  IN OUT    VOID          *BufferToSort,
-  IN CONST  UINTN         Count,
-  IN CONST  UINTN         ElementSize,
-  IN        SORT_COMPARE  CompareFunction,
-  IN        VOID          *Buffer
-  )
-{
-  VOID        *Pivot;
-  UINTN       LoopCount;
-  UINTN       NextSwapLocation;
-
-  ASSERT(BufferToSort    != NULL);
-  ASSERT(CompareFunction != NULL);
-  ASSERT(Buffer          != NULL);
-
-  if (Count < 2 || ElementSize  < 1) {
-    return;
-  }
-
-  NextSwapLocation = 0;
-
-  //
-  // Pick a pivot (we choose last element)
-  //
-  Pivot = ((UINT8 *)BufferToSort + ((Count - 1) * ElementSize));
-
-  //
-  // Now get the pivot such that all on "left" are below it
-  // and everything "right" are above it
-  //
-  for (LoopCount = 0; LoopCount < Count - 1;  LoopCount++)
-  {
-    //
-    // If the element is less than the pivot
-    //
-    if (CompareFunction ((VOID *)((UINT8 *)BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0) {
-      //
-      // Swap
-      //
-      CopyMem (Buffer, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
-      CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), (UINT8 *)BufferToSort + ((LoopCount) * ElementSize), ElementSize);
-      CopyMem ((UINT8 *)BufferToSort + ((LoopCount) * ElementSize), Buffer, ElementSize);
-
-      //
-      // Increment NextSwapLocation
-      //
-      NextSwapLocation++;
-    }
-  }
-  //
-  // Swap pivot to its final position (NextSwapLocation)
-  //
-  CopyMem (Buffer, Pivot, ElementSize);
-  CopyMem (Pivot, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
-  CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), Buffer, ElementSize);
-
-  //
-  // Now recurse on 2 partial lists.  Neither of these will have the 'pivot' element.
-  // IE list is sorted left half, pivot element, sorted right half...
-  //
-  QuickSortWorker (
-    BufferToSort,
-    NextSwapLocation,
-    ElementSize,
-    CompareFunction,
-    Buffer
-    );
-
-  QuickSortWorker (
-    (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
-    Count - NextSwapLocation - 1,
-    ElementSize,
-    CompareFunction,
-    Buffer
-    );
-
-  return;
-}
-
 //---------------------------------------------------------
 // Standard C Run-time Library Interface Wrapper
 //---------------------------------------------------------
@@ -337,10 +252,7 @@ void qsort (void *base, size_t num, size_t width, int (*compare)(const void *, c
   Buffer = malloc (width);
   ASSERT (Buffer != NULL);
 
-  //
-  // Re-use PerformQuickSort() function Implementation in EDKII BaseSortLib.
-  //
-  QuickSortWorker (base, (UINTN)num, (UINTN)width, (SORT_COMPARE)compare, Buffer);
+  QuickSort (base, (UINTN)num, (UINTN)width, (BASE_SORT_COMPARE)compare, Buffer);
 
   free (Buffer);
   return;
-- 
2.30.0.windows.1


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

* [PATCH v2 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
  2021-10-15 23:25 [PATCH v2 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
  2021-10-15 23:25 ` [PATCH v2 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
  2021-10-15 23:25 ` [PATCH v2 2/3] CryptoPkg/CryptLib: " IanX Kuo
@ 2021-10-15 23:25 ` IanX Kuo
  2021-10-16 14:57   ` [edk2-devel] " Marvin Häuser
  2 siblings, 1 reply; 6+ messages in thread
From: IanX Kuo @ 2021-10-15 23:25 UTC (permalink / raw)
  To: devel; +Cc: amy.chan, ray.ni, IanX Kuo, Eric Dong, Rahul Kumar

From: IanX Kuo <ianx.kuo@intel.com>

REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675

Remove MdeModulePkg dependency

Cc: Eric Dong <eric.dong@intel.com>
Cc: Ray Ni <ray.ni@intel.com>
Cc: Rahul Kumar <rahul1.kumar@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
 UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c     | 9 ++++++++-
 .../Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf       | 2 --
 .../Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h    | 1 -
 .../Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf       | 2 --
 4 files changed, 8 insertions(+), 6 deletions(-)

diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
index c0077d6770..45c2ca13dc 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
@@ -282,6 +282,7 @@ CpuCacheInfoCollectCpuCacheInfoData (
   UINTN                     LocalCacheInfoCount;
   UINTN                     Index;
   UINTN                     NextIndex;
+  VOID                      *QuickSortBuffer;
 
   //
   // Get number of Packages and Package ID.
@@ -369,7 +370,13 @@ CpuCacheInfoCollectCpuCacheInfoData (
     //
     // Sort LocalCacheInfo array by CPU package ID, core type, cache level and cache type.
     //
-    PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare);
+    QuickSortBuffer = AllocateZeroPool (sizeof (*LocalCacheInfo));
+    ASSERT (QuickSortBuffer != NULL);
+    if (QuickSortBuffer == NULL) {
+      return EFI_OUT_OF_RESOURCES;
+    }
+
+    QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), CpuCacheInfoCompare, QuickSortBuffer);
     CopyMem (CacheInfo, LocalCacheInfo, sizeof (*CacheInfo) * LocalCacheInfoCount);
     DEBUG_CODE (
       CpuCacheInfoPrintCpuCacheInfoTable (CacheInfo, LocalCacheInfoCount);
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
index c3d3f1e799..fdd79970f9 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
@@ -25,7 +25,6 @@
 
 [Packages]
   MdePkg/MdePkg.dec
-  MdeModulePkg/MdeModulePkg.dec
   UefiCpuPkg/UefiCpuPkg.dec
 
 [LibraryClasses]
@@ -34,7 +33,6 @@
   BaseMemoryLib
   MemoryAllocationLib
   UefiBootServicesTableLib
-  SortLib
 
 [Protocols]
   gEfiMpServiceProtocolGuid
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
index 26e1f46516..829a9f43ce 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
@@ -17,7 +17,6 @@
 #include <Library/DebugLib.h>
 #include <Library/BaseMemoryLib.h>
 #include <Library/MemoryAllocationLib.h>
-#include <Library/SortLib.h>
 #include <Library/CpuCacheInfoLib.h>
 
 typedef union {
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
index 0864497849..c643fc89be 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
@@ -25,7 +25,6 @@
 
 [Packages]
   MdePkg/MdePkg.dec
-  MdeModulePkg/MdeModulePkg.dec
   UefiCpuPkg/UefiCpuPkg.dec
 
 [LibraryClasses]
@@ -34,7 +33,6 @@
   BaseMemoryLib
   MemoryAllocationLib
   PeiServicesTablePointerLib
-  SortLib
 
 [Ppis]
   gEdkiiPeiMpServices2PpiGuid
-- 
2.30.0.windows.1


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

* Re: [edk2-devel] [PATCH v2 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
  2021-10-15 23:25 ` [PATCH v2 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
@ 2021-10-16 14:57   ` Marvin Häuser
  0 siblings, 0 replies; 6+ messages in thread
From: Marvin Häuser @ 2021-10-16 14:57 UTC (permalink / raw)
  To: devel, ianx.kuo; +Cc: amy.chan, ray.ni, Eric Dong, Rahul Kumar

Hey IanX,

On 16.10.21 01:25, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Remove MdeModulePkg dependency
>
> Cc: Eric Dong <eric.dong@intel.com>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Rahul Kumar <rahul1.kumar@intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
>   UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c     | 9 ++++++++-
>   .../Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf       | 2 --
>   .../Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h    | 1 -
>   .../Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf       | 2 --
>   4 files changed, 8 insertions(+), 6 deletions(-)
>
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
> index c0077d6770..45c2ca13dc 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
> @@ -282,6 +282,7 @@ CpuCacheInfoCollectCpuCacheInfoData (
>     UINTN                     LocalCacheInfoCount;
>     UINTN                     Index;
>     UINTN                     NextIndex;
> +  VOID                      *QuickSortBuffer;
>   
>     //
>     // Get number of Packages and Package ID.
> @@ -369,7 +370,13 @@ CpuCacheInfoCollectCpuCacheInfoData (
>       //
>       // Sort LocalCacheInfo array by CPU package ID, core type, cache level and cache type.
>       //
> -    PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare);
> +    QuickSortBuffer = AllocateZeroPool (sizeof (*LocalCacheInfo));
> +    ASSERT (QuickSortBuffer != NULL);

Sorry, maybe I should have been more specific. Asserting on dynamic 
memory allocations is a bad idea (independently of whether it's 
otherwise handled or not) as this makes all kinds of analyses harder, 
for example fuzz-testing would just die with ASSERTs enabled, and static 
analysis may draw incorrect conclusions from this incorrect assertion. 
Disabling ASSERTs for analyses can work, but it may decrease their 
efficacy (e.g. fuzz-testing can no longer verify invariants this way, 
and static analysis may start emitting more False Positives). This is an 
edk2-wide problem that I hope to address with a new macro in the near 
future. For now, if it does not interrupt your testing much, I'd prefer 
dropping it.

I still believe this data could just live on the stack, avoiding this 
issue entirely.

> +    if (QuickSortBuffer == NULL) {
> +      return EFI_OUT_OF_RESOURCES;
> +    }

Thanks!

Best regards,
Marvin

> +
> +    QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), CpuCacheInfoCompare, QuickSortBuffer);
>       CopyMem (CacheInfo, LocalCacheInfo, sizeof (*CacheInfo) * LocalCacheInfoCount);
>       DEBUG_CODE (
>         CpuCacheInfoPrintCpuCacheInfoTable (CacheInfo, LocalCacheInfoCount);
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
> index c3d3f1e799..fdd79970f9 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
> @@ -25,7 +25,6 @@
>   
>   [Packages]
>     MdePkg/MdePkg.dec
> -  MdeModulePkg/MdeModulePkg.dec
>     UefiCpuPkg/UefiCpuPkg.dec
>   
>   [LibraryClasses]
> @@ -34,7 +33,6 @@
>     BaseMemoryLib
>     MemoryAllocationLib
>     UefiBootServicesTableLib
> -  SortLib
>   
>   [Protocols]
>     gEfiMpServiceProtocolGuid
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
> index 26e1f46516..829a9f43ce 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
> @@ -17,7 +17,6 @@
>   #include <Library/DebugLib.h>
>   #include <Library/BaseMemoryLib.h>
>   #include <Library/MemoryAllocationLib.h>
> -#include <Library/SortLib.h>
>   #include <Library/CpuCacheInfoLib.h>
>   
>   typedef union {
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
> index 0864497849..c643fc89be 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
> @@ -25,7 +25,6 @@
>   
>   [Packages]
>     MdePkg/MdePkg.dec
> -  MdeModulePkg/MdeModulePkg.dec
>     UefiCpuPkg/UefiCpuPkg.dec
>   
>   [LibraryClasses]
> @@ -34,7 +33,6 @@
>     BaseMemoryLib
>     MemoryAllocationLib
>     PeiServicesTablePointerLib
> -  SortLib
>   
>   [Ppis]
>     gEdkiiPeiMpServices2PpiGuid


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

* Re: [edk2-devel] [PATCH v2 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
  2021-10-15 23:25 ` [PATCH v2 2/3] CryptoPkg/CryptLib: " IanX Kuo
@ 2021-10-16 14:59   ` Marvin Häuser
  0 siblings, 0 replies; 6+ messages in thread
From: Marvin Häuser @ 2021-10-16 14:59 UTC (permalink / raw)
  To: devel, ianx.kuo
  Cc: amy.chan, ray.ni, Jiewen Yao, Jian J Wang, Xiaoyu Lu,
	Guomin Jiang

Hey IanX,

On 16.10.21 01:25, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Use QuickSort instead of QuickSortWorker
>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Jiewen Yao <jiewen.yao@intel.com>
> Cc: Jian J Wang <jian.j.wang@intel.com>
> Cc: Xiaoyu Lu <xiaoyux.lu@intel.com>
> Cc: Guomin Jiang <guomin.jiang@intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
>   .../Library/BaseCryptLib/SysCall/CrtWrapper.c | 92 +------------------
>   1 file changed, 2 insertions(+), 90 deletions(-)
>
> diff --git a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
> index 42235ab96a..b10edaae5b 100644
> --- a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
> +++ b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
> @@ -2,7 +2,7 @@
>     C Run-Time Libraries (CRT) Wrapper Implementation for OpenSSL-based
>     Cryptographic Library.
>   
> -Copyright (c) 2009 - 2017, Intel Corporation. All rights reserved.<BR>
> +Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.<BR>
>   SPDX-License-Identifier: BSD-2-Clause-Patent
>   
>   **/
> @@ -22,91 +22,6 @@ int
>     IN  VOID  *Buffer2
>     );
>   
> -//
> -// Duplicated from EDKII BaseSortLib for qsort() wrapper
> -//
> -STATIC
> -VOID
> -QuickSortWorker (
> -  IN OUT    VOID          *BufferToSort,
> -  IN CONST  UINTN         Count,
> -  IN CONST  UINTN         ElementSize,
> -  IN        SORT_COMPARE  CompareFunction,
> -  IN        VOID          *Buffer
> -  )
> -{
> -  VOID        *Pivot;
> -  UINTN       LoopCount;
> -  UINTN       NextSwapLocation;
> -
> -  ASSERT(BufferToSort    != NULL);
> -  ASSERT(CompareFunction != NULL);
> -  ASSERT(Buffer          != NULL);
> -
> -  if (Count < 2 || ElementSize  < 1) {
> -    return;
> -  }
> -
> -  NextSwapLocation = 0;
> -
> -  //
> -  // Pick a pivot (we choose last element)
> -  //
> -  Pivot = ((UINT8 *)BufferToSort + ((Count - 1) * ElementSize));
> -
> -  //
> -  // Now get the pivot such that all on "left" are below it
> -  // and everything "right" are above it
> -  //
> -  for (LoopCount = 0; LoopCount < Count - 1;  LoopCount++)
> -  {
> -    //
> -    // If the element is less than the pivot
> -    //
> -    if (CompareFunction ((VOID *)((UINT8 *)BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0) {
> -      //
> -      // Swap
> -      //
> -      CopyMem (Buffer, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
> -      CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), (UINT8 *)BufferToSort + ((LoopCount) * ElementSize), ElementSize);
> -      CopyMem ((UINT8 *)BufferToSort + ((LoopCount) * ElementSize), Buffer, ElementSize);
> -
> -      //
> -      // Increment NextSwapLocation
> -      //
> -      NextSwapLocation++;
> -    }
> -  }
> -  //
> -  // Swap pivot to its final position (NextSwapLocation)
> -  //
> -  CopyMem (Buffer, Pivot, ElementSize);
> -  CopyMem (Pivot, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
> -  CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), Buffer, ElementSize);
> -
> -  //
> -  // Now recurse on 2 partial lists.  Neither of these will have the 'pivot' element.
> -  // IE list is sorted left half, pivot element, sorted right half...
> -  //
> -  QuickSortWorker (
> -    BufferToSort,
> -    NextSwapLocation,
> -    ElementSize,
> -    CompareFunction,
> -    Buffer
> -    );
> -
> -  QuickSortWorker (
> -    (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
> -    Count - NextSwapLocation - 1,
> -    ElementSize,
> -    CompareFunction,
> -    Buffer
> -    );
> -
> -  return;
> -}
> -
>   //---------------------------------------------------------
>   // Standard C Run-time Library Interface Wrapper
>   //---------------------------------------------------------
> @@ -337,10 +252,7 @@ void qsort (void *base, size_t num, size_t width, int (*compare)(const void *, c
>     Buffer = malloc (width);
>     ASSERT (Buffer != NULL);
>   
> -  //
> -  // Re-use PerformQuickSort() function Implementation in EDKII BaseSortLib.
> -  //
> -  QuickSortWorker (base, (UINTN)num, (UINTN)width, (SORT_COMPARE)compare, Buffer);
> +  QuickSort (base, (UINTN)num, (UINTN)width, (BASE_SORT_COMPARE)compare, Buffer);

Same as the other occurrence, can this cast be dropped?

Best regards,
Marvin

>   
>     free (Buffer);
>     return;


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

end of thread, other threads:[~2021-10-16 14:59 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2021-10-15 23:25 [PATCH v2 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-15 23:25 ` [PATCH v2 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-15 23:25 ` [PATCH v2 2/3] CryptoPkg/CryptLib: " IanX Kuo
2021-10-16 14:59   ` [edk2-devel] " Marvin Häuser
2021-10-15 23:25 ` [PATCH v2 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2021-10-16 14:57   ` [edk2-devel] " Marvin Häuser

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