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

["Zeng, Star" <star.zeng@intel.com>]

Reviewed-by: Star Zeng <star.zeng@intel.com>

> -----Original Message-----
> From: Dong, Eric <eric.dong@intel.com>
> Sent: Friday, April 10, 2020 11:00 AM
> To: Ray Ni <niruiyu@users.noreply.github.com>; devel@edk2.groups.io
> Cc: Ni, Ray <ray.ni@intel.com>; Zeng, Star <star.zeng@intel.com>
> Subject: RE: [PATCH v3] UefiCpuPkg/PiSmmCpuDxeSmm: Improve the
> performance of GetFreeToken()
> 
> Reviewed-by: Eric Dong <eric.dong@intel.com>
> 
> > -----Original Message-----
> > From: Ray Ni [mailto:niruiyu@users.noreply.github.com]
> > Sent: Friday, April 10, 2020 10:51 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 v3] 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.
> >
> > v2: add missing line in InitializeDataForMmMp.
> > v3: update copyright year to 2020.
> >
> > 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      | 71
> ++++++++--------------
> >  UefiCpuPkg/PiSmmCpuDxeSmm/PiSmmCpuDxeSmm.h |  3 +-
> >  2 files changed, 27 insertions(+), 47 deletions(-)
> >
> > diff --git a/UefiCpuPkg/PiSmmCpuDxeSmm/MpService.c
> > b/UefiCpuPkg/PiSmmCpuDxeSmm/MpService.c
> > index c285a70ebb..93cac5e4fa 100644
> > --- a/UefiCpuPkg/PiSmmCpuDxeSmm/MpService.c
> > +++ b/UefiCpuPkg/PiSmmCpuDxeSmm/MpService.c
> > @@ -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..c9b3b739f3 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 - 2020, 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