The change in MdePkg is good to me. Reviewed-by: Liming Gao <gaoliming@...>

Thanks Liming, could you please also give the reviewed-by.

Hi Ard, also need your reviewed-by for ArmPkg. Then this changes could be upstream and finished.

Thanks

Abner

Ard and Abner:

 I am OK to add these three PCDs PcdPciMmio32Translation, PcdPciMmio64Translation, PcdPciIoTranslation to MdePkg.

Thanks

Liming

-----Original Message-----
From: Ma, Hua <hua.ma@intel.com>
Sent: Monday, October 11, 2021 6:45 PM
To: devel@edk2.groups.io
Cc: Ma, Hua <hua.ma@intel.com>; Wang, Jian J <jian.j.wang@intel.com>;
Liming Gao <gaoliming@byosoft.com.cn>; Bi, Dandan <dandan.bi@intel.com>;
Ni, Ray <ray.ni@intel.com>
Subject: [PATCH] MdeModulePkg/Core/Dxe: Acquire a lock when iterating
gHandleList

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

This patch fixes the following issue:

The global variable gHandleList is a linked list.
This list is locked when a entry is added or removed from the list, but there is no
lock when iterating this list in function CoreValidateHandle().
It can lead to "Handle.c (76): CR has Bad Signature" assertion if the iterated
entry in the list is just removed by other task during iterating.
Locking the list when iterating can fix this issue.

Cc: Jian J Wang <jian.j.wang@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Dandan Bi <dandan.bi@intel.com>
Cc: Ray Ni <ray.ni@intel.com>
Signed-off-by: Hua Ma <hua.ma@intel.com>
---
MdeModulePkg/Core/Dxe/Hand/DriverSupport.c | 10 ++---
MdeModulePkg/Core/Dxe/Hand/Handle.c | 47 ++++++++++++++--------
MdeModulePkg/Core/Dxe/Hand/Handle.h | 3 +-
MdeModulePkg/Core/Dxe/Hand/Notify.c | 2 +-
4 files changed, 39 insertions(+), 23 deletions(-)

diff --git a/MdeModulePkg/Core/Dxe/Hand/DriverSupport.c
b/MdeModulePkg/Core/Dxe/Hand/DriverSupport.c
index feabf12faf..eb8a765d2c 100644
--- a/MdeModulePkg/Core/Dxe/Hand/DriverSupport.c
+++ b/MdeModulePkg/Core/Dxe/Hand/DriverSupport.c
@@ -68,7 +68,7 @@ CoreConnectController (
//
// Make sure ControllerHandle is valid
//
- Status = CoreValidateHandle (ControllerHandle);
+ Status = CoreValidateHandle (ControllerHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
@@ -154,7 +154,7 @@ CoreConnectController (
//
// Make sure the DriverBindingHandle is valid
//
- Status = CoreValidateHandle (ControllerHandle);
+ Status = CoreValidateHandle (ControllerHandle, TRUE);
if (EFI_ERROR (Status)) {
//
// Release the protocol lock on the handle database @@ -268,7 +268,7 @@
AddSortedDriverBindingProtocol (
//
// Make sure the DriverBindingHandle is valid
//
- Status = CoreValidateHandle (DriverBindingHandle);
+ Status = CoreValidateHandle (DriverBindingHandle, FALSE);
if (EFI_ERROR (Status)) {
return;
}
@@ -746,7 +746,7 @@ CoreDisconnectController (
//
// Make sure ControllerHandle is valid
//
- Status = CoreValidateHandle (ControllerHandle);
+ Status = CoreValidateHandle (ControllerHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
@@ -755,7 +755,7 @@ CoreDisconnectController (
// Make sure ChildHandle is valid if it is not NULL
//
if (ChildHandle != NULL) {
- Status = CoreValidateHandle (ChildHandle);
+ Status = CoreValidateHandle (ChildHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
diff --git a/MdeModulePkg/Core/Dxe/Hand/Handle.c
b/MdeModulePkg/Core/Dxe/Hand/Handle.c
index 6eccb41ecb..b4f389bb35 100644
--- a/MdeModulePkg/Core/Dxe/Hand/Handle.c
+++ b/MdeModulePkg/Core/Dxe/Hand/Handle.c
@@ -55,31 +55,46 @@ CoreReleaseProtocolLock (
Check whether a handle is a valid EFI_HANDLE

@param UserHandle The handle to check
+ @param IsLocked The protocol lock is acquried or not

@retval EFI_INVALID_PARAMETER The handle is NULL or not a valid
EFI_HANDLE.
+ @retval EFI_NOT_FOUND The handle is not found in the handle
database.
@retval EFI_SUCCESS The handle is valid EFI_HANDLE.

**/
EFI_STATUS
CoreValidateHandle (
- IN EFI_HANDLE UserHandle
+ IN EFI_HANDLE UserHandle,
+ IN BOOLEAN IsLocked
)
{
IHANDLE *Handle;
LIST_ENTRY *Link;
+ EFI_STATUS Status;

if (UserHandle == NULL) {
return EFI_INVALID_PARAMETER;
}

+ if (IsLocked) {
+ ASSERT_LOCKED(&gProtocolDatabaseLock);
+ } else {
+ CoreAcquireProtocolLock ();
+ }
+
+ Status = EFI_NOT_FOUND;
for (Link = gHandleList.BackLink; Link != &gHandleList; Link = Link->BackLink) {
Handle = CR (Link, IHANDLE, AllHandles, EFI_HANDLE_SIGNATURE);
if (Handle == (IHANDLE *) UserHandle) {
- return EFI_SUCCESS;
+ Status = EFI_SUCCESS;
+ break;
}
}

- return EFI_INVALID_PARAMETER;
+ if (!IsLocked) {
+ CoreReleaseProtocolLock ();
+ }
+ return Status;
}


@@ -428,7 +443,7 @@ CoreInstallProtocolInterfaceNotify (
//
InsertTailList (&gHandleList, &Handle->AllHandles);
} else {
- Status = CoreValidateHandle (Handle);
+ Status = CoreValidateHandle (Handle, TRUE);
if (EFI_ERROR (Status)) {
DEBUG((DEBUG_ERROR, "InstallProtocolInterface: input handle at 0x%x is
invalid\n", Handle));
goto Done;
@@ -723,7 +738,7 @@ CoreUninstallProtocolInterface (
//
// Check that UserHandle is a valid handle
//
- Status = CoreValidateHandle (UserHandle);
+ Status = CoreValidateHandle (UserHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
@@ -899,7 +914,7 @@ CoreGetProtocolInterface (
IHANDLE *Handle;
LIST_ENTRY *Link;

- Status = CoreValidateHandle (UserHandle);
+ Status = CoreValidateHandle (UserHandle, TRUE);

if (EFI_ERROR (Status)) {
return NULL;
}
@@ -1013,7 +1028,7 @@ CoreOpenProtocol (
//
// Check for invalid UserHandle
//
- Status = CoreValidateHandle (UserHandle);
+ Status = CoreValidateHandle (UserHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
@@ -1023,11 +1038,11 @@ CoreOpenProtocol (
//
switch (Attributes) {
case EFI_OPEN_PROTOCOL_BY_CHILD_CONTROLLER :
- Status = CoreValidateHandle (ImageHandle);
+ Status = CoreValidateHandle (ImageHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
- Status = CoreValidateHandle (ControllerHandle);
+ Status = CoreValidateHandle (ControllerHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
@@ -1037,17 +1052,17 @@ CoreOpenProtocol (
break;
case EFI_OPEN_PROTOCOL_BY_DRIVER :
case EFI_OPEN_PROTOCOL_BY_DRIVER | EFI_OPEN_PROTOCOL_EXCLUSIVE :
- Status = CoreValidateHandle (ImageHandle);
+ Status = CoreValidateHandle (ImageHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
- Status = CoreValidateHandle (ControllerHandle);
+ Status = CoreValidateHandle (ControllerHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
break;
case EFI_OPEN_PROTOCOL_EXCLUSIVE :
- Status = CoreValidateHandle (ImageHandle);
+ Status = CoreValidateHandle (ImageHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
@@ -1249,16 +1264,16 @@ CoreCloseProtocol (
//
// Check for invalid parameters
//
- Status = CoreValidateHandle (UserHandle);
+ Status = CoreValidateHandle (UserHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
- Status = CoreValidateHandle (AgentHandle);
+ Status = CoreValidateHandle (AgentHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
if (ControllerHandle != NULL) {
- Status = CoreValidateHandle (ControllerHandle);
+ Status = CoreValidateHandle (ControllerHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
@@ -1443,7 +1458,7 @@ CoreProtocolsPerHandle (
UINTN ProtocolCount;
EFI_GUID **Buffer;

- Status = CoreValidateHandle (UserHandle);
+ Status = CoreValidateHandle (UserHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
diff --git a/MdeModulePkg/Core/Dxe/Hand/Handle.h
b/MdeModulePkg/Core/Dxe/Hand/Handle.h
index 83eb2b9f3a..b962d80a29 100644
--- a/MdeModulePkg/Core/Dxe/Hand/Handle.h
+++ b/MdeModulePkg/Core/Dxe/Hand/Handle.h
@@ -251,7 +251,8 @@ CoreReleaseProtocolLock ( **/ EFI_STATUS
CoreValidateHandle (
- IN EFI_HANDLE UserHandle
+ IN EFI_HANDLE UserHandle,
+ IN BOOLEAN IsLocked
);

//
diff --git a/MdeModulePkg/Core/Dxe/Hand/Notify.c
b/MdeModulePkg/Core/Dxe/Hand/Notify.c
index 553413a350..f4e7c01e96 100644
--- a/MdeModulePkg/Core/Dxe/Hand/Notify.c
+++ b/MdeModulePkg/Core/Dxe/Hand/Notify.c
@@ -188,7 +188,7 @@ CoreReinstallProtocolInterface (
PROTOCOL_INTERFACE *Prot;
PROTOCOL_ENTRY *ProtEntry;

- Status = CoreValidateHandle (UserHandle);
+ Status = CoreValidateHandle (UserHandle, FALSE);
if (EFI_ERROR (Status)) {
return Status;
}
--
2.32.0.windows.2

-----Original Message-----
From: Kuo, IanX <ianx.kuo@intel.com>
Sent: Tuesday, October 12, 2021 8:06 AM
To: devel@edk2.groups.io
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kuo,
IanX <ianx.kuo@intel.com>; Kinney, Michael D
<michael.d.kinney@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>;
Liu, Zhiguang <zhiguang.liu@intel.com>
Subject: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort function on
BaseLib

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

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

Add QuickSort function into BaseLib

Cc: Ray Ni <ray.ni@intel.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
MdePkg/Include/Library/BaseLib.h | 49 ++++++++
MdePkg/Library/BaseLib/BaseLib.inf | 1 +
MdePkg/Library/BaseLib/QuickSort.c | 116 ++++++++++++++++++
.../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
4 files changed, 168 insertions(+), 1 deletion(-) create mode 100644
MdePkg/Library/BaseLib/QuickSort.c

diff --git a/MdePkg/Include/Library/BaseLib.h
b/MdePkg/Include/Library/BaseLib.h
index 2452c1d92e..0ae0f4e6af 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -2856,6 +2856,55 @@ RemoveEntryList ( //

// Math Services

//

+/**

+ Prototype for comparison function for any two element types.

+

+ @param[in] Buffer1 The pointer to first buffer.

+ @param[in] Buffer2 The pointer to second buffer.

+

+ @retval 0 Buffer1 equal to Buffer2.

+ @return <0 Buffer1 is less than Buffer2.

+ @return >0 Buffer1 is greater than Buffer2.

+**/

+typedef

+INTN

+(EFIAPI *BASE_SORT_COMPARE)(

+ IN CONST VOID *Buffer1,

+ IN CONST VOID *Buffer2

+ );

+

+/**

+ This function is identical to perform QuickSort,

+ 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 BufferOneElement is NULL, then ASSERT.

+ if ElementSize is < 1, then ASSERT.

+

+ if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.

+ It's used by QuickSort() for swapping in sorting.

+**/

+VOID

+EFIAPI

+QuickSort (

+ IN OUT VOID *BufferToSort,

+ IN CONST UINTN Count,

+ IN CONST UINTN ElementSize,

+ IN BASE_SORT_COMPARE CompareFunction,

+ OUT VOID *BufferOneElement

+ );



/**

Shifts a 64-bit integer left between 0 and 63 bits. The low bits
are filled

diff --git a/MdePkg/Library/BaseLib/BaseLib.inf
b/MdePkg/Library/BaseLib/BaseLib.inf
index 6efa5315b6..cebda3b210 100644
--- a/MdePkg/Library/BaseLib/BaseLib.inf
+++ b/MdePkg/Library/BaseLib/BaseLib.inf
@@ -32,6 +32,7 @@
SwapBytes16.c

LongJump.c

SetJump.c

+ QuickSort.c

RShiftU64.c

RRotU64.c

RRotU32.c

diff --git a/MdePkg/Library/BaseLib/QuickSort.c
b/MdePkg/Library/BaseLib/QuickSort.c
new file mode 100644
index 0000000000..a825c072b0
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,116 @@
+/** @file

+ Math worker functions.

+

+ Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>

+ SPDX-License-Identifier: BSD-2-Clause-Patent

+

+**/

+

+#include "BaseLibInternals.h"

+

+/**

+ This function is identical to perform QuickSort,

+ 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 BufferOneElement is NULL, then ASSERT.

+ if ElementSize is < 1, then ASSERT.

+

+ if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.

+ It's used by QuickSort() for swapping in sorting.

+**/

+VOID

+EFIAPI

+QuickSort (

+ IN OUT VOID *BufferToSort,

+ IN CONST UINTN Count,

+ IN CONST UINTN ElementSize,

+ IN BASE_SORT_COMPARE CompareFunction,

+ OUT VOID *BufferOneElement

+ )

+{

+ VOID *Pivot;

+ UINTN LoopCount;

+ UINTN NextSwapLocation;

+

+ ASSERT (BufferToSort != NULL);

+ ASSERT (CompareFunction != NULL);

+ ASSERT (BufferOneElement != NULL);

+ ASSERT (ElementSize >= 1);

+

+ if (Count < 2) {

+ 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 or equal to the pivot

+ //

+ if (CompareFunction ((VOID*) ((UINT8*) BufferToSort +
+ ((LoopCount) * ElementSize)), Pivot) <= 0){

+ //

+ // swap

+ //

+ CopyMem (BufferOneElement, (UINT8*) BufferToSort +
+ (NextSwapLocation * ElementSize), ElementSize);

+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation *
+ ElementSize), (UINT8*) BufferToSort + ((LoopCount) *
ElementSize), ElementSize);

+ CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize),
+ BufferOneElement, ElementSize);

+

+ //

+ // increment NextSwapLocation

+ //

+ NextSwapLocation++;

+ }

+ }

+ //

+ // swap pivot to it's final position (NextSwapLocation)

+ //

+ CopyMem (BufferOneElement, Pivot, ElementSize);

+ CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation *
+ ElementSize), ElementSize);

+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize),
+ BufferOneElement, 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...

+ //

+ if (NextSwapLocation >= 2) {

+ QuickSort (

+ BufferToSort,

+ NextSwapLocation,

+ ElementSize,

+ CompareFunction,

+ BufferOneElement

+ );

+ }

+

+ if ((Count - NextSwapLocation - 1) >= 2) {

+ QuickSort (

+ (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,

+ Count - NextSwapLocation - 1,

+ ElementSize,

+ CompareFunction,

+ BufferOneElement

+ );

+ }

+}

diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
index eae1a7158d..d09bd12bef 100644
--- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
+++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
@@ -1,7 +1,7 @@
## @file

# Base Library implementation for use with host based unit tests.

#

-# Copyright (c) 2007 - 2020, Intel Corporation. All rights
reserved.<BR>

+# Copyright (c) 2007 - 2021, Intel Corporation. All rights
+reserved.<BR>

# Portions copyright (c) 2008 - 2009, Apple Inc. All rights
reserved.<BR>

# Portions copyright (c) 2011 - 2013, ARM Ltd. All rights
reserved.<BR>

# Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All
rights reserved.<BR>

@@ -33,6 +33,7 @@
SwapBytes16.c

LongJump.c

SetJump.c

+ QuickSort.c

RShiftU64.c

RRotU64.c

RRotU32.c

--
2.30.0.windows.1

-----Original Message-----
From: Kuo, IanX <ianx.kuo@intel.com>
Sent: Tuesday, October 12, 2021 8:06 AM
To: devel@edk2.groups.io
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kuo, IanX <ianx.kuo@intel.com>; Kinney, Michael D
<michael.d.kinney@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>; Liu, Zhiguang <zhiguang.liu@intel.com>
Subject: [PATCH v9 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib

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

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

Add QuickSort function into BaseLib

Cc: Ray Ni <ray.ni@intel.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
MdePkg/Include/Library/BaseLib.h | 49 ++++++++
MdePkg/Library/BaseLib/BaseLib.inf | 1 +
MdePkg/Library/BaseLib/QuickSort.c | 116 ++++++++++++++++++
.../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
4 files changed, 168 insertions(+), 1 deletion(-)
create mode 100644 MdePkg/Library/BaseLib/QuickSort.c

diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/BaseLib.h
index 2452c1d92e..0ae0f4e6af 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -2856,6 +2856,55 @@ RemoveEntryList (
//

// Math Services

//

+/**

+ Prototype for comparison function for any two element types.

+

+ @param[in] Buffer1 The pointer to first buffer.

+ @param[in] Buffer2 The pointer to second buffer.

+

+ @retval 0 Buffer1 equal to Buffer2.

+ @return <0 Buffer1 is less than Buffer2.

+ @return >0 Buffer1 is greater than Buffer2.

+**/

+typedef

+INTN

+(EFIAPI *BASE_SORT_COMPARE)(

+ IN CONST VOID *Buffer1,

+ IN CONST VOID *Buffer2

+ );

+

+/**

+ This function is identical to perform QuickSort,

+ 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 BufferOneElement is NULL, then ASSERT.

+ if ElementSize is < 1, then ASSERT.

+

+ if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.

+ It's used by QuickSort() for swapping in sorting.

+**/

+VOID

+EFIAPI

+QuickSort (

+ IN OUT VOID *BufferToSort,

+ IN CONST UINTN Count,

+ IN CONST UINTN ElementSize,

+ IN BASE_SORT_COMPARE CompareFunction,

+ OUT VOID *BufferOneElement

+ );



/**

Shifts a 64-bit integer left between 0 and 63 bits. The low bits are filled

diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/BaseLib.inf
index 6efa5315b6..cebda3b210 100644
--- a/MdePkg/Library/BaseLib/BaseLib.inf
+++ b/MdePkg/Library/BaseLib/BaseLib.inf
@@ -32,6 +32,7 @@
SwapBytes16.c

LongJump.c

SetJump.c

+ QuickSort.c

RShiftU64.c

RRotU64.c

RRotU32.c

diff --git a/MdePkg/Library/BaseLib/QuickSort.c b/MdePkg/Library/BaseLib/QuickSort.c
new file mode 100644
index 0000000000..a825c072b0
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,116 @@
+/** @file

+ Math worker functions.

+

+ Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>

+ SPDX-License-Identifier: BSD-2-Clause-Patent

+

+**/

+

+#include "BaseLibInternals.h"

+

+/**

+ This function is identical to perform QuickSort,

+ 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 BufferOneElement is NULL, then ASSERT.

+ if ElementSize is < 1, then ASSERT.

+

+ if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.

+ It's used by QuickSort() for swapping in sorting.

+**/

+VOID

+EFIAPI

+QuickSort (

+ IN OUT VOID *BufferToSort,

+ IN CONST UINTN Count,

+ IN CONST UINTN ElementSize,

+ IN BASE_SORT_COMPARE CompareFunction,

+ OUT VOID *BufferOneElement

+ )

+{

+ VOID *Pivot;

+ UINTN LoopCount;

+ UINTN NextSwapLocation;

+

+ ASSERT (BufferToSort != NULL);

+ ASSERT (CompareFunction != NULL);

+ ASSERT (BufferOneElement != NULL);

+ ASSERT (ElementSize >= 1);

+

+ if (Count < 2) {

+ 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 or equal to the pivot

+ //

+ if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0){

+ //

+ // swap

+ //

+ CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);

+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) *
ElementSize), ElementSize);

+ CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, ElementSize);

+

+ //

+ // increment NextSwapLocation

+ //

+ NextSwapLocation++;

+ }

+ }

+ //

+ // swap pivot to it's final position (NextSwapLocation)

+ //

+ CopyMem (BufferOneElement, Pivot, ElementSize);

+ CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);

+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), BufferOneElement, 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...

+ //

+ if (NextSwapLocation >= 2) {

+ QuickSort (

+ BufferToSort,

+ NextSwapLocation,

+ ElementSize,

+ CompareFunction,

+ BufferOneElement

+ );

+ }

+

+ if ((Count - NextSwapLocation - 1) >= 2) {

+ QuickSort (

+ (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,

+ Count - NextSwapLocation - 1,

+ ElementSize,

+ CompareFunction,

+ BufferOneElement

+ );

+ }

+}

diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
index eae1a7158d..d09bd12bef 100644
--- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
+++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
@@ -1,7 +1,7 @@
## @file

# Base Library implementation for use with host based unit tests.

#

-# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>

+# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>

# Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>

# Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>

# Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All rights reserved.<BR>

@@ -33,6 +33,7 @@
SwapBytes16.c

LongJump.c

SetJump.c

+ QuickSort.c

RShiftU64.c

RRotU64.c

RRotU32.c

--
2.30.0.windows.1