MdeModulePkg: CoreValidateHandle Optimization

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

Before entering BIOS setup, CoreValidateHandle function executed
over 600,000 times during BDS phase on latest 8S server platform.
In CoreValidateHandle function, current implementation will go
through the doubly-linked list handle database in each call, and
this will have big impact on boot performance.
The optimization is using Red-black tree to store the EFI handle
address when insert each EFI handle into the handle database, and
remove the handle from Red-black tree if the handle is removed
from the handle database. CoreValidateHandle function changed to
go through the Red-black tree.
After verification on latest 8S server platform, BDS boot time can
save 20s+ after this change.

Cc: Ray Ni <ray.ni@intel.com>
Cc: Star Zeng <star.zeng@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Signed-off-by: Andrew Fish <afish@apple.com>
Tested-by: Xiaoqiang Zhang <xiaoqiang.zhang@intel.com>

4 files changed, 97 insertions, 11 deletions

diff --git a/MdeModulePkg/Core/Dxe/DxeMain.h b/MdeModulePkg/Core/Dxe/DxeMain.h
index 53e26703f8..cd3940d34b 100644
--- a/MdeModulePkg/Core/Dxe/DxeMain.h
+++ b/MdeModulePkg/Core/Dxe/DxeMain.h
@@ -84,6 +84,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
 #include <Library/DxeServicesLib.h>

 #include <Library/DebugAgentLib.h>

 #include <Library/CpuExceptionHandlerLib.h>

+#include <Library/OrderedCollectionLib.h>

 

 //

 // attributes for reserved memory before it is promoted to system memory

@@ -2790,4 +2791,15 @@ MergeMemoryMap (
   IN UINTN                      DescriptorSize

   );

 

+/**

+  Initializes "handle" support.

+

+  @return Status code.

+

++**/

+EFI_STATUS

+CoreInitializeHandleServices (

+  VOID

+  );

+

 #endif

diff --git a/MdeModulePkg/Core/Dxe/DxeMain.inf b/MdeModulePkg/Core/Dxe/DxeMain.inf
index 090970aec6..cc315ac92a 100644
--- a/MdeModulePkg/Core/Dxe/DxeMain.inf
+++ b/MdeModulePkg/Core/Dxe/DxeMain.inf
@@ -95,6 +95,7 @@
   CpuExceptionHandlerLib

   PcdLib

   ImagePropertiesRecordLib

+  OrderedCollectionLib

 

 [Guids]

   gEfiEventMemoryMapChangeGuid                  ## PRODUCES             ## Event

diff --git a/MdeModulePkg/Core/Dxe/DxeMain/DxeMain.c b/MdeModulePkg/Core/Dxe/DxeMain/DxeMain.c
index 17d510a287..8a877330dd 100644
--- a/MdeModulePkg/Core/Dxe/DxeMain/DxeMain.c
+++ b/MdeModulePkg/Core/Dxe/DxeMain/DxeMain.c
@@ -277,6 +277,12 @@ DxeMain (
   MemoryProfileInit (HobStart);

 

   //

+  // Start the Handle Services.

+  //

+  Status = CoreInitializeHandleServices ();

+  ASSERT_EFI_ERROR (Status);

+

+  //

   // Start the Image Services.

   //

   Status = CoreInitializeImageServices (HobStart);

diff --git a/MdeModulePkg/Core/Dxe/Hand/Handle.c b/MdeModulePkg/Core/Dxe/Hand/Handle.c
index 24e4fbf5f3..b5ff3fdcd1 100644
--- a/MdeModulePkg/Core/Dxe/Hand/Handle.c
+++ b/MdeModulePkg/Core/Dxe/Hand/Handle.c
@@ -15,10 +15,11 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
 // gProtocolDatabaseLock - Lock to protect the mProtocolDatabase

 // gHandleDatabaseKey    -  The Key to show that the handle has been created/modified

 //

-LIST_ENTRY  mProtocolDatabase     = INITIALIZE_LIST_HEAD_VARIABLE (mProtocolDatabase);

-LIST_ENTRY  gHandleList           = INITIALIZE_LIST_HEAD_VARIABLE (gHandleList);

-EFI_LOCK    gProtocolDatabaseLock = EFI_INITIALIZE_LOCK_VARIABLE (TPL_NOTIFY);

-UINT64      gHandleDatabaseKey    = 0;

+LIST_ENTRY          mProtocolDatabase     = INITIALIZE_LIST_HEAD_VARIABLE (mProtocolDatabase);

+LIST_ENTRY          gHandleList           = INITIALIZE_LIST_HEAD_VARIABLE (gHandleList);

+EFI_LOCK            gProtocolDatabaseLock = EFI_INITIALIZE_LOCK_VARIABLE (TPL_NOTIFY);

+UINT64              gHandleDatabaseKey    = 0;

+ORDERED_COLLECTION  *gOrderedHandleList   = NULL;

 

 /**

   Acquire lock on gProtocolDatabaseLock.

@@ -45,6 +46,60 @@ CoreReleaseProtocolLock (
 }

 

 /**

+  Comparator function for two opaque pointers, ordering on (unsigned) pointer

+  value itself.

+  Can be used as both Key and UserStruct comparator.

+

+  @param[in] Pointer1  First pointer.

+

+  @param[in] Pointer2  Second pointer.

+

+  @retval <0  If Pointer1 compares less than Pointer2.

+

+  @retval  0  If Pointer1 compares equal to Pointer2.

+

+  @retval >0  If Pointer1 compares greater than Pointer2.

+**/

+STATIC

+INTN

+EFIAPI

+PointerCompare (

+  IN CONST VOID  *Pointer1,

+  IN CONST VOID  *Pointer2

+  )

+{

+  if (Pointer1 == Pointer2) {

+    return 0;

+  }

+

+  if ((UINTN)Pointer1 < (UINTN)Pointer2) {

+    return -1;

+  }

+

+  return 1;

+}

+

+/**

+  Initializes "handle" support.

+

+  @return Status code.

+

+**/

+EFI_STATUS

+CoreInitializeHandleServices (

+  VOID

+  )

+{

+  gOrderedHandleList = OrderedCollectionInit (PointerCompare, PointerCompare);

+

+  if (gOrderedHandleList == NULL) {

+    return EFI_OUT_OF_RESOURCES;

+  }

+

+  return EFI_SUCCESS;

+}

+

+/**

   Check whether a handle is a valid EFI_HANDLE

   The gProtocolDatabaseLock must be owned

 

@@ -59,8 +114,7 @@ CoreValidateHandle (
   IN  EFI_HANDLE  UserHandle

   )

 {

-  IHANDLE     *Handle;

-  LIST_ENTRY  *Link;

+  ORDERED_COLLECTION_ENTRY  *Entry;

 

   if (UserHandle == NULL) {

     return EFI_INVALID_PARAMETER;

@@ -68,11 +122,9 @@ CoreValidateHandle (
 

   ASSERT_LOCKED (&gProtocolDatabaseLock);

 

-  for (Link = gHandleList.BackLink; Link != &gHandleList; Link = Link->BackLink) {

-    Handle = CR (Link, IHANDLE, AllHandles, EFI_HANDLE_SIGNATURE);

-    if (Handle == (IHANDLE *)UserHandle) {

-      return EFI_SUCCESS;

-    }

+  Entry = OrderedCollectionFind (gOrderedHandleList, UserHandle);

+  if (Entry != NULL) {

+    return EFI_SUCCESS;

   }

 

   return EFI_INVALID_PARAMETER;

@@ -453,6 +505,16 @@ CoreInstallProtocolInterfaceNotify (
     }

 

     //

+    // Add this handle to the ordered list of all handles

+    // in the system

+    //

+    Status = OrderedCollectionInsert (gOrderedHandleList, NULL, Handle);

+    if (EFI_ERROR (Status)) {

+      CoreFreePool (Handle);

+      goto Done;

+    }

+

+    //

     // Initialize new handler structure

     //

     Handle->Signature = EFI_HANDLE_SIGNATURE;

@@ -825,6 +887,11 @@ CoreUninstallProtocolInterface (
   //

   if (IsListEmpty (&Handle->Protocols)) {

     Handle->Signature = 0;

+    OrderedCollectionDelete (

+      gOrderedHandleList,

+      OrderedCollectionFind (gOrderedHandleList, Handle),

+      NULL

+      );

     RemoveEntryList (&Handle->AllHandles);

     CoreFreePool (Handle);

   }