* [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