Re: [PATCH 1/2] MdePkg/BaseLib: Add IsNodeInList() function.

["Marvin Häuser" <Marvin.Haeuser@outlook.com>]

Hey Liming,

Thanks for your reply! Sure, that works as well, though usually I prefer to write a static function or a macro instead of repeating.
If you prefer this, I'll get a V2 ready that way. Though shouldn't it be ASSERT ((!FeaturePcdGet (PcdVerifyNodeInList) || IsNodeInList (FirstEntry, SecondEntry)) && InternalBaseLibIsListValid (FirstEntry)); ?
Correct me if I'm wrong, but wouldn't your suggestion not ASSERT if the feature is enabled, the entry is not in the list, but the list is valid? ((TRUE && FALSE) || TRUE) would return TRUE.

Thanks,
Marvin.

> -----Original Message-----
> From: Gao, Liming [mailto:liming.gao@intel.com]
> Sent: Wednesday, August 2, 2017 2:12 PM
> To: Marvin.Haeuser@outlook.com; edk2-devel@lists.01.org
> Cc: Kinney, Michael D <michael.d.kinney@intel.com>
> Subject: RE: [PATCH 1/2] MdePkg/BaseLib: Add IsNodeInList() function.
> 
> Marvin:
>   How about directly use PCD checker with IsNodeInList()?
> 
>   ASSERT (IsNodeInList (FirstEntry, SecondEntry)); ==> ASSERT
> (FeaturePcdGet (PcdVerifyNodeInList) && IsNodeInList (FirstEntry,
> SecondEntry))|| InternalBaseLibIsListValid (FirstEntry));
> 
> Thanks
> Liming
> >-----Original Message-----
> >From: edk2-devel [mailto:edk2-devel-bounces@lists.01.org] On Behalf Of
> >Marvin H?user
> >Sent: Friday, July 28, 2017 12:20 AM
> >To: edk2-devel@lists.01.org
> >Cc: Kinney, Michael D <michael.d.kinney@intel.com>; Gao, Liming
> ><liming.gao@intel.com>
> >Subject: Re: [edk2] [PATCH 1/2] MdePkg/BaseLib: Add IsNodeInList()
> function.
> >
> >Hi Liming,
> >
> >Comments are inline. Thanks for your response!
> >
> >Regards,
> >Marvin.
> >
> >> -----Original Message-----
> >> From: Gao, Liming [mailto:liming.gao@intel.com]
> >> Sent: Thursday, July 27, 2017 5:32 PM
> >> To: Marvin.Haeuser@outlook.com; edk2-devel@lists.01.org
> >> Cc: Kinney, Michael D <michael.d.kinney@intel.com>
> >> Subject: RE: [PATCH 1/2] MdePkg/BaseLib: Add IsNodeInList() function.
> >>
> >> Marvin:
> >>   Once this API is exposed as the public library API, what code will
> >> you
> >update
> >> to consume this API?
> >
> >The code which gave me the idea for this patch is this:
> >https://github.com/tianocore/edk2-platforms/blob/devel-
> >MinPlatform/Silicon/Intel/KabylakeSiliconPkg/Pch/PchSmiDispatcher/Smm/
> I
> >o
> >Trap.c#L508
> >ForwardLink is obviously checked against EFI_BAD_POINTER to verify
> >whether the entry is still valid. Though, after being freed, the value
> >stored in this location may just be overwritten.
> >The code linked currently doesn't seem to do anything as ForwardLink is
> >never set to EFI_BAD_POINTER, though it can be updated with
> >IsNodeInList() to function (regardless of the entry being freed).
> >It seems to me that this is a leftover from the EDK era as EDK's
> >RemoveEntryList() does set the Links to EFI_BAD_POINTER.
> >
> >>
> >>   And, for the patch, I have two comments.
> >> 1) Original logic uses PcdVerifyNodeInList to turn on the
> >> verification of NodeInList. New logic always turns on it. Because
> >> this check takes much overhead, this PCD is FALSE as the default value in
> MdePkg.dec.
> >> 2) In IsListEmpty(), ASSERT() is missing for
> >> InternalBaseLibIsListValid (ListHead).
> >
> >Sorry for these oversights. Would you prefer an internal, static
> >function or a macro to do the PCD check and following the ASSERTin v2?
> >
> >>
> >> Thanks
> >> Liming
> >> > -----Original Message-----
> >> > From: edk2-devel [mailto:edk2-devel-bounces@lists.01.org] On Behalf
> >> > Of Marvin H?user
> >> > Sent: Tuesday, July 25, 2017 12:53 AM
> >> > To: edk2-devel@lists.01.org
> >> > Cc: Kinney, Michael D <michael.d.kinney@intel.com>
> >> > Subject: Re: [edk2] [PATCH 1/2] MdePkg/BaseLib: Add IsNodeInList()
> >> function.
> >> >
> >> > Hey Mike,
> >> >
> >> > In contrast to setting 'BackLink' and 'ForwardLink' to dummy values
> >> > such as EFI_BAD_POINTER, verifying that a node is part of a known
> >> > list is a safe way to determine whether a link is still valid
> >> > without needing to keep the memory allocated. If the Node, which
> >> > had its links set to dummys, is freed, the dummy values may be
> >> > overwriten and the check would pass despite the node being invalid.
> >> > This can, for example, be
> >> used in OpenKabylake's PchSmiDispatcher, which does the described
> >> check against EFI_BAD_POINTER (though if I remember correctly, the
> >> value is actually never explicitely set). The issue is that some
> >> function may pass a handle that was unregistered to the function.
> >> IsNodeInList() can be used to determine whether it was previously
> removed.
> >> >
> >> > Thanks for your response!
> >> >
> >> > Regards,
> >> > Marvin.
> >> >
> >> > > -----Original Message-----
> >> > > From: Kinney, Michael D [mailto:michael.d.kinney@intel.com]
> >> > > Sent: Monday, July 24, 2017 6:31 PM
> >> > > To: Marvin Häuser <Marvin.Haeuser@outlook.com>; edk2-
> >> > > devel@lists.01.org; Kinney, Michael D
> >> > > <michael.d.kinney@intel.com>
> >> > > Cc: Gao, Liming <liming.gao@intel.com>
> >> > > Subject: RE: [PATCH 1/2] MdePkg/BaseLib: Add IsNodeInList()
> function.
> >> > >
> >> > > Hi Marvin,
> >> > >
> >> > > Can you provide a few more details on why you would like to see
> >> > > tis internal function promoted to a library class API?
> >> > >
> >> > > Thanks,
> >> > >
> >> > > Mike
> >> > >
> >> > > > -----Original Message-----
> >> > > > From: Marvin Häuser [mailto:Marvin.Haeuser@outlook.com]
> >> > > > Sent: Sunday, July 23, 2017 3:11 AM
> >> > > > To: edk2-devel@lists.01.org
> >> > > > Cc: Kinney, Michael D <michael.d.kinney@intel.com>; Gao, Liming
> >> > > > <liming.gao@intel.com>
> >> > > > Subject: [PATCH 1/2] MdePkg/BaseLib: Add IsNodeInList() function.
> >> > > >
> >> > > > This patch adds IsNodeInList() to BaseLib, which verifies the
> >> > > > given Node is part of the doubly-linked List provided.
> >> > > >
> >> > > > Contributed-under: TianoCore Contribution Agreement 1.1
> >> > > > Signed-off-by: Marvin Haeuser <Marvin.Haeuser@outlook.com>
> >> > > > ---
> >> > > >  MdePkg/Library/BaseLib/LinkedList.c       | 70
> >> > > > +++++++++++++++++++-
> >> > > >  MdePkg/Include/Library/BaseLib.h          | 25 +++++++
> >> > > >  MdePkg/Library/BaseLib/BaseLibInternals.h | 28 --------
> >> > > >  3 files changed, 94 insertions(+), 29 deletions(-)
> >> > > >
> >> > > > diff --git a/MdePkg/Library/BaseLib/LinkedList.c
> >> > > > b/MdePkg/Library/BaseLib/LinkedList.c
> >> > > > index ba373f4b7be3..b364ae41c647 100644
> >> > > > --- a/MdePkg/Library/BaseLib/LinkedList.c
> >> > > > +++ b/MdePkg/Library/BaseLib/LinkedList.c
> >> > > > @@ -1,7 +1,7 @@
> >> > > >  /** @file
> >> > > >    Linked List Library Functions.
> >> > > >
> >> > > > -  Copyright (c) 2006 - 2013, Intel Corporation. All rights
> >> > > > reserved.<BR>
> >> > > > +  Copyright (c) 2006 - 2017, Intel Corporation. All rights
> >> > > > reserved.<BR>
> >> > > >    This program and the accompanying materials
> >> > > >    are licensed and made available under the terms and
> >> > > > conditions of the BSD License
> >> > > >    which accompanies this distribution.  The full text of the
> >> > > > license may be found at @@ -113,6 +113,74 @@
> >> > > > InternalBaseLibIsNodeInList (  }
> >> > > >
> >> > > >  /**
> >> > > > +  Checks whether Node is part of a doubly-linked list.
> >> > > > +
> >> > > > +  If List is NULL, then ASSERT().
> >> > > > +  If List->ForwardLink is NULL, then ASSERT().
> >> > > > +  If List->BackLink is NULL, then ASSERT().
> >> > > > +  If Node is NULL, then ASSERT();  If
> >> > > > + PcdMaximumLinkedListLength is not zero, and List contains
> >> > > > more than
> >> > > > +  PcdMaximumLinkedListLength nodes, then ASSERT().
> >> > > > +
> >> > > > +  @param  List  A pointer to a node in a linked list.
> >> > > > +  @param  Node  A pointer to the node to locate.
> >> > > > +
> >> > > > +  @retval TRUE   Node is in List.
> >> > > > +  @retval FALSE  Node isn't in List, or List is invalid.
> >> > > > +
> >> > > > +**/
> >> > > > +BOOLEAN
> >> > > > +EFIAPI
> >> > > > +IsNodeInList (
> >> > > > +  IN      CONST LIST_ENTRY      *List,
> >> > > > +  IN      CONST LIST_ENTRY      *Node
> >> > > > +  )
> >> > > > +{
> >> > > > +  UINTN             Count;
> >> > > > +  CONST LIST_ENTRY  *Ptr;
> >> > > > +
> >> > > > +  //
> >> > > > +  // Test the validity of List and Node  //  ASSERT (List !=
> >> > > > + NULL); ASSERT (List->ForwardLink != NULL);  ASSERT
> >> > > > + (List->BackLink != NULL);  ASSERT (Node != NULL);
> >> > > > +
> >> > > > +  //
> >> > > > +  // ASSERT List not too long
> >> > > > +  //
> >> > > > +  ASSERT (InternalBaseLibIsNodeInList (ListHead, Entry,
> >> > > > + FALSE));
> >> > > > +
> >> > > > +  Count = 0;
> >> > > > +  Ptr   = List;
> >> > > > +
> >> > > > +  //
> >> > > > +  // Check to see if Node is a member of List.
> >> > > > +  // Exit early if the number of nodes in List >=
> >> > > > PcdMaximumLinkedListLength
> >> > > > +  //
> >> > > > +  do {
> >> > > > +    Ptr = Ptr->ForwardLink;
> >> > > > +    if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
> >> > > > +      Count++;
> >> > > > +
> >> > > > +      //
> >> > > > +      // Return if the linked list is too long
> >> > > > +      //
> >> > > > +      if (Count == PcdGet32 (PcdMaximumLinkedListLength)) {
> >> > > > +        return (BOOLEAN)(Ptr == Node);
> >> > > > +      }
> >> > > > +    }
> >> > > > +
> >> > > > +    if (Ptr == Node) {
> >> > > > +      return TRUE;
> >> > > > +    }
> >> > > > +  } while (Ptr != List);
> >> > > > +
> >> > > > +  return FALSE;
> >> > > > +}
> >> > > > +
> >> > > > +/**
> >> > > >    Initializes the head node of a doubly-linked list, and
> >> > > > returns the pointer to
> >> > > >    the head node of the doubly-linked list.
> >> > > >
> >> > > > diff --git a/MdePkg/Include/Library/BaseLib.h
> >> > > > b/MdePkg/Include/Library/BaseLib.h
> >> > > > index 791849b80406..4f3f4fd51f3f 100644
> >> > > > --- a/MdePkg/Include/Library/BaseLib.h
> >> > > > +++ b/MdePkg/Include/Library/BaseLib.h
> >> > > > @@ -2869,6 +2869,31 @@ PathCleanUpDirectories(
> >> > > >
> >> > > >
> >> > > >  /**
> >> > > > +  Checks whether Node is part of a doubly-linked list.
> >> > > > +
> >> > > > +  If List is NULL, then ASSERT().
> >> > > > +  If List->ForwardLink is NULL, then ASSERT().
> >> > > > +  If List->BackLink is NULL, then ASSERT().
> >> > > > +  If Node is NULL, then ASSERT();  If
> >> > > > + PcdMaximumLinkedListLength is not zero, and List contains
> >> > > > more than
> >> > > > +  PcdMaximumLinkedListLength nodes, then ASSERT().
> >> > > > +
> >> > > > +  @param  List  A pointer to a node in a linked list.
> >> > > > +  @param  Node  A pointer to the node to locate.
> >> > > > +
> >> > > > +  @retval TRUE   Node is in List.
> >> > > > +  @retval FALSE  Node isn't in List, or List is invalid.
> >> > > > +
> >> > > > +**/
> >> > > > +BOOLEAN
> >> > > > +EFIAPI
> >> > > > +IsNodeInList (
> >> > > > +  IN      CONST LIST_ENTRY      *List,
> >> > > > +  IN      CONST LIST_ENTRY      *Node
> >> > > > +  );
> >> > > > +
> >> > > > +
> >> > > > +/**
> >> > > >    Initializes the head node of a doubly linked list, and
> >> > > > returns the pointer to
> >> > > >    the head node of the doubly linked list.
> >> > > >
> >> > > > diff --git a/MdePkg/Library/BaseLib/BaseLibInternals.h
> >> > > > b/MdePkg/Library/BaseLib/BaseLibInternals.h
> >> > > > index ea387ce37d27..9dca97a0dcc9 100644
> >> > > > --- a/MdePkg/Library/BaseLib/BaseLibInternals.h
> >> > > > +++ b/MdePkg/Library/BaseLib/BaseLibInternals.h
> >> > > > @@ -340,34 +340,6 @@ InternalSwitchStack (
> >> > > >
> >> > > >
> >> > > >  /**
> >> > > > -  Worker function that locates the Node in the List.
> >> > > > -
> >> > > > -  By searching the List, finds the location of the Node in List.
> >> > > > At the same time,
> >> > > > -  verifies the validity of this list.
> >> > > > -
> >> > > > -  If List is NULL, then ASSERT().
> >> > > > -  If List->ForwardLink is NULL, then ASSERT().
> >> > > > -  If List->backLink is NULL, then ASSERT().
> >> > > > -  If Node is NULL, then ASSERT();
> >> > > > -  If PcdMaximumLinkedListLength is not zero, and prior to
> >> > > > insertion the number
> >> > > > -  of nodes in ListHead, including the ListHead node, is
> >> > > > greater than or
> >> > > > -  equal to PcdMaximumLinkedListLength, then ASSERT().
> >> > > > -
> >> > > > -  @param  List  A pointer to a node in a linked list.
> >> > > > -  @param  Node  A pointer to one nod.
> >> > > > -
> >> > > > -  @retval TRUE   Node is in List.
> >> > > > -  @retval FALSE  Node isn't in List, or List is invalid.
> >> > > > -
> >> > > > -**/
> >> > > > -BOOLEAN
> >> > > > -EFIAPI
> >> > > > -IsNodeInList (
> >> > > > -  IN      CONST LIST_ENTRY      *List,
> >> > > > -  IN      CONST LIST_ENTRY      *Node
> >> > > > -  );
> >> > > > -
> >> > > > -/**
> >> > > >    Worker function that returns a bit field from Operand.
> >> > > >
> >> > > >    Returns the bitfield specified by the StartBit and the
> >> > > > EndBit from Operand.
> >> > > > --
> >> > > > 2.12.2.windows.2
> >> >
> >> > _______________________________________________
> >> > edk2-devel mailing list
> >> > edk2-devel@lists.01.org
> >> > https://lists.01.org/mailman/listinfo/edk2-devel
> >_______________________________________________
> >edk2-devel mailing list
> >edk2-devel@lists.01.org
> >https://lists.01.org/mailman/listinfo/edk2-devel