Re: [PATCH v2] UefiCpuPkg/PiSmmCpuDxeSmm: Improve the performance of GetFreeToken()

["Ni, Ray" <ray.ni@intel.com>]

Eric,
You are right! I added the missing line back.

Thanks,
Ray 

> -----Original Message-----
> From: Ray Ni <niruiyu@users.noreply.github.com>
> Sent: Friday, April 10, 2020 10:07 AM
> To: devel@edk2.groups.io
> Cc: Ni, Ray <ray.ni@intel.com>; Dong, Eric <eric.dong@intel.com>; Zeng, Star <star.zeng@intel.com>
> Subject: [PATCH v2] UefiCpuPkg/PiSmmCpuDxeSmm: Improve the performance of GetFreeToken()
> 
> Today's GetFreeToken() runs at the algorithm complexity of O(n)
> where n is the size of the token list.
> 
> The change introduces a new global variable FirstFreeToken and it
> always points to the first free token. So the algorithm complexity
> of GetFreeToken() decreases from O(n) to O(1).
> 
> The improvement matters when some SMI code uses StartupThisAP()
> service for each of the AP such that the algorithm complexity
> becomes O(n) * O(m) where m is the AP count.
> 
> As next steps,
> 1. PROCEDURE_TOKEN.Used field can be optimized out because
> all tokens before FirstFreeToken should have "Used" set while all
> after FirstFreeToken should have "Used" cleared.
> 2. ResetTokens() can be optimized to only reset tokens before
> FirstFreeToken.
> 
> Signed-off-by: Ray Ni <ray.ni@intel.com>
> Cc: Eric Dong <eric.dong@intel.com>
> Cc: Star Zeng <star.zeng@intel.com>
> ---
>  UefiCpuPkg/PiSmmCpuDxeSmm/MpService.c      | 73 ++++++++--------------
>  UefiCpuPkg/PiSmmCpuDxeSmm/PiSmmCpuDxeSmm.h |  3 +-
>  2 files changed, 28 insertions(+), 48 deletions(-)
> 
> diff --git a/UefiCpuPkg/PiSmmCpuDxeSmm/MpService.c b/UefiCpuPkg/PiSmmCpuDxeSmm/MpService.c
> index c285a70ebb..b3f6c9e6a6 100644
> --- a/UefiCpuPkg/PiSmmCpuDxeSmm/MpService.c
> +++ b/UefiCpuPkg/PiSmmCpuDxeSmm/MpService.c
> @@ -1,7 +1,7 @@
>  /** @file
>  SMM MP service implementation
> 
> -Copyright (c) 2009 - 2020, Intel Corporation. All rights reserved.<BR>
> +Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.<BR>
>  Copyright (c) 2017, AMD Incorporated. All rights reserved.<BR>
> 
>  SPDX-License-Identifier: BSD-2-Clause-Patent
> @@ -453,6 +453,11 @@ ResetTokens (
> 
>      Link = GetNextNode (&gSmmCpuPrivate->TokenList, Link);
>    }
> +
> +  //
> +  // Reset the FirstFreeToken to the beginning of token list upon exiting SMI.
> +  //
> +  gSmmCpuPrivate->FirstFreeToken = GetFirstNode (&gSmmCpuPrivate->TokenList);
>  }
> 
>  /**
> @@ -1060,23 +1065,21 @@ IsTokenInUse (
>  /**
>    Allocate buffer for the SPIN_LOCK and PROCEDURE_TOKEN.
> 
> +  @return First token of the token buffer.
>  **/
> -VOID
> +LIST_ENTRY *
>  AllocateTokenBuffer (
>    VOID
>    )
>  {
>    UINTN               SpinLockSize;
>    UINT32              TokenCountPerChunk;
> -  UINTN               ProcTokenSize;
>    UINTN               Index;
> -  PROCEDURE_TOKEN     *ProcToken;
>    SPIN_LOCK           *SpinLock;
>    UINT8               *SpinLockBuffer;
> -  UINT8               *ProcTokenBuffer;
> +  PROCEDURE_TOKEN     *ProcTokens;
> 
>    SpinLockSize = GetSpinLockProperties ();
> -  ProcTokenSize = sizeof (PROCEDURE_TOKEN);
> 
>    TokenCountPerChunk = FixedPcdGet32 (PcdCpuSmmMpTokenCountPerChunk);
>    ASSERT (TokenCountPerChunk != 0);
> @@ -1092,49 +1095,22 @@ AllocateTokenBuffer (
>    SpinLockBuffer = AllocatePool (SpinLockSize * TokenCountPerChunk);
>    ASSERT (SpinLockBuffer != NULL);
> 
> -  ProcTokenBuffer = AllocatePool (ProcTokenSize * TokenCountPerChunk);
> -  ASSERT (ProcTokenBuffer != NULL);
> +  ProcTokens = AllocatePool (sizeof (PROCEDURE_TOKEN) * TokenCountPerChunk);
> +  ASSERT (ProcTokens != NULL);
> 
>    for (Index = 0; Index < TokenCountPerChunk; Index++) {
>      SpinLock = (SPIN_LOCK *)(SpinLockBuffer + SpinLockSize * Index);
>      InitializeSpinLock (SpinLock);
> 
> -    ProcToken = (PROCEDURE_TOKEN *)(ProcTokenBuffer + ProcTokenSize * Index);
> -    ProcToken->Signature = PROCEDURE_TOKEN_SIGNATURE;
> -    ProcToken->SpinLock = SpinLock;
> -    ProcToken->Used = FALSE;
> -    ProcToken->RunningApCount = 0;
> +    ProcTokens[Index].Signature      = PROCEDURE_TOKEN_SIGNATURE;
> +    ProcTokens[Index].SpinLock       = SpinLock;
> +    ProcTokens[Index].Used           = FALSE;
> +    ProcTokens[Index].RunningApCount = 0;
> 
> -    InsertTailList (&gSmmCpuPrivate->TokenList, &ProcToken->Link);
> +    InsertTailList (&gSmmCpuPrivate->TokenList, &ProcTokens[Index].Link);
>    }
> -}
> 
> -/**
> -  Find first free token in the allocated token list.
> -
> -  @retval    return the first free PROCEDURE_TOKEN.
> -
> -**/
> -PROCEDURE_TOKEN *
> -FindFirstFreeToken (
> -  VOID
> -  )
> -{
> -  LIST_ENTRY        *Link;
> -  PROCEDURE_TOKEN   *ProcToken;
> -
> -  Link = GetFirstNode (&gSmmCpuPrivate->TokenList);
> -  while (!IsNull (&gSmmCpuPrivate->TokenList, Link)) {
> -    ProcToken = PROCEDURE_TOKEN_FROM_LINK (Link);
> -
> -    if (!ProcToken->Used) {
> -      return ProcToken;
> -    }
> -
> -    Link = GetNextNode (&gSmmCpuPrivate->TokenList, Link);
> -  }
> -
> -  return NULL;
> +  return &ProcTokens[0].Link;
>  }
> 
>  /**
> @@ -1154,12 +1130,15 @@ GetFreeToken (
>  {
>    PROCEDURE_TOKEN  *NewToken;
> 
> -  NewToken = FindFirstFreeToken ();
> -  if (NewToken == NULL) {
> -    AllocateTokenBuffer ();
> -    NewToken = FindFirstFreeToken ();
> +  //
> +  // If FirstFreeToken meets the end of token list, enlarge the token list.
> +  // Set FirstFreeToken to the first free token.
> +  //
> +  if (gSmmCpuPrivate->FirstFreeToken == &gSmmCpuPrivate->TokenList) {
> +    gSmmCpuPrivate->FirstFreeToken = AllocateTokenBuffer ();
>    }
> -  ASSERT (NewToken != NULL);
> +  NewToken = PROCEDURE_TOKEN_FROM_LINK (gSmmCpuPrivate->FirstFreeToken);
> +  gSmmCpuPrivate->FirstFreeToken = GetNextNode (&gSmmCpuPrivate->TokenList, gSmmCpuPrivate->FirstFreeToken);
> 
>    NewToken->Used = TRUE;
>    NewToken->RunningApCount = RunningApsCount;
> @@ -1781,7 +1760,7 @@ InitializeDataForMmMp (
> 
>    InitializeListHead (&gSmmCpuPrivate->TokenList);
> 
> -  AllocateTokenBuffer ();
> +  gSmmCpuPrivate->FirstFreeToken = AllocateTokenBuffer ();
>  }
> 
>  /**
> diff --git a/UefiCpuPkg/PiSmmCpuDxeSmm/PiSmmCpuDxeSmm.h b/UefiCpuPkg/PiSmmCpuDxeSmm/PiSmmCpuDxeSmm.h
> index fe7e8b0323..17f4bd34fa 100644
> --- a/UefiCpuPkg/PiSmmCpuDxeSmm/PiSmmCpuDxeSmm.h
> +++ b/UefiCpuPkg/PiSmmCpuDxeSmm/PiSmmCpuDxeSmm.h
> @@ -1,7 +1,7 @@
>  /** @file
>  Agent Module to load other modules to deploy SMM Entry Vector for X86 CPU.
> 
> -Copyright (c) 2009 - 2019, Intel Corporation. All rights reserved.<BR>
> +Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.<BR>
>  Copyright (c) 2017, AMD Incorporated. All rights reserved.<BR>
> 
>  SPDX-License-Identifier: BSD-2-Clause-Patent
> @@ -255,6 +255,7 @@ typedef struct {
> 
>    PROCEDURE_WRAPPER               *ApWrapperFunc;
>    LIST_ENTRY                      TokenList;
> +  LIST_ENTRY                      *FirstFreeToken;
>  } SMM_CPU_PRIVATE_DATA;
> 
>  extern SMM_CPU_PRIVATE_DATA  *gSmmCpuPrivate;
> --
> 2.21.0.windows.1