[PATCH v2 1/7] OvmfPkg: introduce PciCapLib

[Laszlo Ersek <lersek@redhat.com>]

Add a library class, and a BASE lib instance, to work more easily with PCI
capabilities in PCI config space. Functions are provided to parse
capabilities lists, and to locate, describe, read and write capabilities.
PCI config space access is abstracted away.

Cc: Ard Biesheuvel <ard.biesheuvel@linaro.org>
Cc: Jordan Justen <jordan.l.justen@intel.com>
Suggested-by: Jordan Justen <jordan.l.justen@intel.com>
Contributed-under: TianoCore Contribution Agreement 1.1
Signed-off-by: Laszlo Ersek <lersek@redhat.com>
---

Notes:
    v2:
    - move library from MdePkg to OvmfPkg, for initial introduction

 OvmfPkg/OvmfPkg.dec                             |    4 +
 OvmfPkg/Library/BasePciCapLib/BasePciCapLib.inf |   38 +
 OvmfPkg/Include/Library/PciCapLib.h             |  429 +++++++++
 OvmfPkg/Library/BasePciCapLib/BasePciCapLib.h   |   60 ++
 OvmfPkg/Library/BasePciCapLib/BasePciCapLib.c   | 1007 ++++++++++++++++++++
 5 files changed, 1538 insertions(+)

diff --git a/OvmfPkg/OvmfPkg.dec b/OvmfPkg/OvmfPkg.dec
index c01a2ca7219a..74818a2e2a19 100644
--- a/OvmfPkg/OvmfPkg.dec
+++ b/OvmfPkg/OvmfPkg.dec
@@ -31,6 +31,10 @@ [LibraryClasses]
   #
   NvVarsFileLib|Include/Library/NvVarsFileLib.h
 
+  ##  @libraryclass  Provides services to work with PCI capabilities in PCI
+  #                  config space.
+  PciCapLib|Include/Library/PciCapLib.h
+
   ##  @libraryclass  Access QEMU's firmware configuration interface
   #
   QemuFwCfgLib|Include/Library/QemuFwCfgLib.h
diff --git a/OvmfPkg/Library/BasePciCapLib/BasePciCapLib.inf b/OvmfPkg/Library/BasePciCapLib/BasePciCapLib.inf
new file mode 100644
index 000000000000..9a7428a589c2
--- /dev/null
+++ b/OvmfPkg/Library/BasePciCapLib/BasePciCapLib.inf
@@ -0,0 +1,38 @@
+## @file
+# Work with PCI capabilities in PCI config space.
+#
+# Provides functions to parse capabilities lists, and to locate, describe, read
+# and write capabilities. PCI config space access is abstracted away.
+#
+# Copyright (C) 2018, Red Hat, Inc.
+#
+# 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
+# http://opensource.org/licenses/bsd-license.php
+#
+# THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
+# WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
+##
+
+[Defines]
+  INF_VERSION    = 1.27
+  BASE_NAME      = BasePciCapLib
+  FILE_GUID      = 6957540D-F7B5-4D5B-BEE4-FC14114DCD3C
+  MODULE_TYPE    = BASE
+  VERSION_STRING = 1.0
+  LIBRARY_CLASS  = PciCapLib
+
+[Sources]
+  BasePciCapLib.h
+  BasePciCapLib.c
+
+[Packages]
+  MdePkg/MdePkg.dec
+  OvmfPkg/OvmfPkg.dec
+
+[LibraryClasses]
+  BaseMemoryLib
+  DebugLib
+  MemoryAllocationLib
+  OrderedCollectionLib
diff --git a/OvmfPkg/Include/Library/PciCapLib.h b/OvmfPkg/Include/Library/PciCapLib.h
new file mode 100644
index 000000000000..22a1ad624bd3
--- /dev/null
+++ b/OvmfPkg/Include/Library/PciCapLib.h
@@ -0,0 +1,429 @@
+/** @file
+  Library class to work with PCI capabilities in PCI config space.
+
+  Provides functions to parse capabilities lists, and to locate, describe, read
+  and write capabilities. PCI config space access is abstracted away.
+
+  Copyright (C) 2018, Red Hat, Inc.
+
+  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
+  http://opensource.org/licenses/bsd-license.php
+
+  THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
+  WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
+**/
+
+#ifndef __PCI_CAP_LIB_H__
+#define __PCI_CAP_LIB_H__
+
+#include <Uefi/UefiBaseType.h>
+
+//
+// Base structure for representing a PCI device -- down to the PCI function
+// level -- for the purposes of this library class. This is a forward
+// declaration that is completed below. Concrete implementations are supposed
+// to inherit and extend this type.
+//
+typedef struct PCI_CAP_DEV PCI_CAP_DEV;
+
+/**
+  Read the config space of a given PCI device (both normal and extended).
+
+  PCI_CAP_DEV_READ_CONFIG performs as few config space accesses as possible
+  (without attempting 64-bit wide accesses).
+
+  PCI_CAP_DEV_READ_CONFIG returns an unspecified error if accessing Size bytes
+  from SourceOffset exceeds the config space limit of the PCI device. Fewer
+  than Size bytes may have been read in this case.
+
+  @param[in] PciDevice           Implementation-specific unique representation
+                                 of the PCI device in the PCI hierarchy.
+
+  @param[in] SourceOffset        Source offset in the config space of the PCI
+                                 device to start reading from.
+
+  @param[out] DestinationBuffer  Buffer to store the read data to.
+
+  @param[in] Size                The number of bytes to transfer.
+
+  @retval RETURN_SUCCESS  Size bytes have been transferred from config space to
+                          DestinationBuffer.
+
+  @return                 Unspecified error codes. Fewer than Size bytes may
+                          have been read.
+**/
+typedef
+RETURN_STATUS
+(EFIAPI *PCI_CAP_DEV_READ_CONFIG) (
+  IN  PCI_CAP_DEV *PciDevice,
+  IN  UINT16      SourceOffset,
+  OUT VOID        *DestinationBuffer,
+  IN  UINT16      Size
+  );
+
+/**
+  Write the config space of a given PCI device (both normal and extended).
+
+  PCI_CAP_DEV_WRITE_CONFIG performs as few config space accesses as possible
+  (without attempting 64-bit wide accesses).
+
+  PCI_CAP_DEV_WRITE_CONFIG returns an unspecified error if accessing Size bytes
+  at DestinationOffset exceeds the config space limit of the PCI device. Fewer
+  than Size bytes may have been written in this case.
+
+  @param[in] PciDevice          Implementation-specific unique representation
+                                of the PCI device in the PCI hierarchy.
+
+  @param[in] DestinationOffset  Destination offset in the config space of the
+                                PCI device to start writing at.
+
+  @param[in] SourceBuffer       Buffer to read the data to be stored from.
+
+  @param[in] Size               The number of bytes to transfer.
+
+  @retval RETURN_SUCCESS  Size bytes have been transferred from SourceBuffer to
+                          config space.
+
+  @return                 Unspecified error codes. Fewer than Size bytes may
+                          have been written.
+**/
+typedef
+RETURN_STATUS
+(EFIAPI *PCI_CAP_DEV_WRITE_CONFIG) (
+  IN PCI_CAP_DEV *PciDevice,
+  IN UINT16      DestinationOffset,
+  IN VOID        *SourceBuffer,
+  IN UINT16      Size
+  );
+
+//
+// Complete the PCI_CAP_DEV type here. The base abstraction only requires
+// config space accessors.
+//
+struct PCI_CAP_DEV {
+  PCI_CAP_DEV_READ_CONFIG  ReadConfig;
+  PCI_CAP_DEV_WRITE_CONFIG WriteConfig;
+};
+
+//
+// Opaque data structure representing parsed PCI Capabilities Lists.
+//
+typedef struct PCI_CAP_LIST PCI_CAP_LIST;
+
+//
+// Opaque data structure representing a PCI Capability in a parsed Capability
+// List.
+//
+typedef struct PCI_CAP PCI_CAP;
+
+//
+// Distinguishes whether a Capability ID is 8-bit wide and interpreted in
+// normal config space, or 16-bit wide and interpreted in extended config
+// space. Capability ID definitions are relative to domain.
+//
+typedef enum {
+  PciCapNormal,
+  PciCapExtended
+} PCI_CAP_DOMAIN;
+
+//
+// Public data structure that PciCapGetInfo() fills in about a PCI_CAP object.
+//
+typedef struct {
+  PCI_CAP_DOMAIN Domain;
+  UINT16         CapId;
+  //
+  // The capability identified by Domain and CapId may have multiple instances
+  // in config space. NumInstances provides the total count of occurrences of
+  // the capability. It is always positive.
+  //
+  UINT16 NumInstances;
+  //
+  // Instance is the serial number, in capabilities list traversal order (not
+  // necessarily config space offset order), of the one capability instance
+  // that PciCapGetInfo() is reporting about. Instance is always smaller than
+  // NumInstances.
+  //
+  UINT16 Instance;
+  //
+  // The offset in config space at which the capability header of the
+  // capability instance starts.
+  //
+  UINT16 Offset;
+  //
+  // The deduced maximum size of the capability instance, including the
+  // capability header. This hint is an upper bound, calculated -- without
+  // regard to the internal structure of the capability -- from (a) the next
+  // lowest offset in configuration space that is known to be used by another
+  // capability, and (b) from the end of the config space identified by Domain,
+  // whichever is lower.
+  //
+  UINT16 MaxSizeHint;
+  //
+  // The version number of the capability instance. Always zero when Domain is
+  // PciCapNormal.
+  //
+  UINT8 Version;
+} PCI_CAP_INFO;
+
+
+/**
+  Parse the capabilities lists (both normal and extended, as applicable) of a
+  PCI device.
+
+  If the PCI device has no capabilities, that per se will not fail
+  PciCapListInit(); an empty capabilities list will be represented.
+
+  If the PCI device is found to be PCI Express, then an attempt will be made to
+  parse the extended capabilities list as well. If the first extended config
+  space access -- via PciDevice->ReadConfig() with SourceOffset=0x100 and
+  Size=4 -- fails, that per se will not fail PciCapListInit(); the device will
+  be assumed to have no extended capabilities.
+
+  @param[in] PciDevice  Implementation-specific unique representation of the
+                        PCI device in the PCI hierarchy.
+
+  @param[out] CapList   Opaque data structure that holds an in-memory
+                        representation of the parsed capabilities lists of
+                        PciDevice.
+
+  @retval RETURN_SUCCESS           The capabilities lists have been parsed from
+                                   config space.
+
+  @retval RETURN_OUT_OF_RESOURCES  Memory allocation failed.
+
+  @retval RETURN_DEVICE_ERROR      A loop or some other kind of invalid pointer
+                                   was detected in the capabilities lists of
+                                   PciDevice.
+
+  @return                          Error codes propagated from
+                                   PciDevice->ReadConfig().
+**/
+RETURN_STATUS
+EFIAPI
+PciCapListInit (
+  IN  PCI_CAP_DEV  *PciDevice,
+  OUT PCI_CAP_LIST **CapList
+  );
+
+
+/**
+  Free the resources used by CapList.
+
+  @param[in] CapList  The PCI_CAP_LIST object to free, originally produced by
+                      PciCapListInit().
+**/
+VOID
+EFIAPI
+PciCapListUninit (
+  IN PCI_CAP_LIST *CapList
+  );
+
+
+/**
+  Locate a capability instance in the parsed capabilities lists.
+
+  @param[in] CapList   The PCI_CAP_LIST object produced by PciCapListInit().
+
+  @param[in] Domain    Distinguishes whether CapId is 8-bit wide and
+                       interpreted in normal config space, or 16-bit wide and
+                       interpreted in extended config space. Capability ID
+                       definitions are relative to domain.
+
+  @param[in] CapId     Capability identifier to look up.
+
+  @param[in] Instance  Domain and CapId may identify a multi-instance
+                       capability. When Instance is zero, the first instance of
+                       the capability is located (in list traversal order --
+                       which may not mean increasing config space offset
+                       order). Higher Instance values locate subsequent
+                       instances of the same capability (in list traversal
+                       order).
+
+  @param[out] Cap      The capability instance that matches the search
+                       criteria. Cap is owned by CapList and becomes invalid
+                       when CapList is freed with PciCapListUninit().
+                       PciCapListFindCap() may be called with Cap set to NULL,
+                       in order to test the existence of a specific capability
+                       instance.
+
+  @retval RETURN_SUCCESS    The capability instance identified by (Domain,
+                            CapId, Instance) has been found.
+
+  @retval RETURN_NOT_FOUND  The requested (Domain, CapId, Instance) capability
+                            instance does not exist.
+**/
+RETURN_STATUS
+EFIAPI
+PciCapListFindCap (
+  IN  PCI_CAP_LIST   *CapList,
+  IN  PCI_CAP_DOMAIN Domain,
+  IN  UINT16         CapId,
+  IN  UINT16         Instance,
+  OUT PCI_CAP        **Cap    OPTIONAL
+  );
+
+
+/**
+  Locate the first instance of the capability given by (Domain, CapId) such
+  that the instance's Version is greater than or equal to MinVersion.
+
+  This is a convenience function that may save client code calls to
+  PciCapListFindCap() and PciCapGetInfo().
+
+  @param[in] CapList     The PCI_CAP_LIST object produced by PciCapListInit().
+
+  @param[in] Domain      Distinguishes whether CapId is 8-bit wide and
+                         interpreted in normal config space, or 16-bit wide and
+                         interpreted in extended config space. Capability ID
+                         definitions are relative to domain.
+
+  @param[in] CapId       Capability identifier to look up.
+
+  @param[in] MinVersion  The minimum version that the capability instance is
+                         required to have. Note that all capability instances
+                         in Domain=PciCapNormal have Version=0.
+
+  @param[out] Cap        The first capability instance that matches the search
+                         criteria. Cap is owned by CapList and becomes invalid
+                         when CapList is freed with PciCapListUninit().
+                         PciCapListFindCapVersion() may be called with Cap set
+                         to NULL, in order just to test whether the search
+                         criteria are satisfiable.
+
+  @retval RETURN_SUCCESS    The first capability instance matching (Domain,
+                            CapId, MinVersion) has been located.
+
+  @retval RETURN_NOT_FOUND  No capability instance matches (Domain, CapId,
+                            MinVersion).
+**/
+RETURN_STATUS
+EFIAPI
+PciCapListFindCapVersion (
+  IN  PCI_CAP_LIST   *CapList,
+  IN  PCI_CAP_DOMAIN Domain,
+  IN  UINT16         CapId,
+  IN  UINT8          MinVersion,
+  OUT PCI_CAP        **Cap      OPTIONAL
+  );
+
+
+/**
+  Get information about a PCI Capability instance.
+
+  @param[in] Cap    The capability instance to get info about, located with
+                    PciCapListFindCap*().
+
+  @param[out] Info  A PCI_CAP_INFO structure that describes the properties of
+                    Cap.
+
+  @retval RETURN_SUCCESS  Fields of Info have been set.
+
+  @return                 Unspecified error codes, if filling in Info failed
+                          for some reason.
+**/
+RETURN_STATUS
+EFIAPI
+PciCapGetInfo (
+  IN  PCI_CAP      *Cap,
+  OUT PCI_CAP_INFO *Info
+  );
+
+
+/**
+  Read a slice of a capability instance.
+
+  The function performs as few config space accesses as possible (without
+  attempting 64-bit wide accesses). PciCapRead() performs bounds checking on
+  SourceOffsetInCap and Size, and only invokes PciDevice->ReadConfig() if the
+  requested transfer falls within Cap.
+
+  @param[in] PciDevice           Implementation-specific unique representation
+                                 of the PCI device in the PCI hierarchy.
+
+  @param[in] Cap                 The capability instance to read, located with
+                                 PciCapListFindCap*().
+
+  @param[in] SourceOffsetInCap   Source offset relative to the capability
+                                 header to start reading from. A zero value
+                                 refers to the first byte of the capability
+                                 header.
+
+  @param[out] DestinationBuffer  Buffer to store the read data to.
+
+  @param[in] Size                The number of bytes to transfer.
+
+  @retval RETURN_SUCCESS          Size bytes have been transferred from Cap to
+                                  DestinationBuffer.
+
+  @retval RETURN_BAD_BUFFER_SIZE  Reading Size bytes starting from
+                                  SourceOffsetInCap would not (entirely) be
+                                  contained within Cap, as suggested by
+                                  PCI_CAP_INFO.MaxSizeHint. No bytes have been
+                                  read.
+
+  @return                         Error codes propagated from
+                                  PciDevice->ReadConfig(). Fewer than Size
+                                  bytes may have been read.
+**/
+RETURN_STATUS
+EFIAPI
+PciCapRead (
+  IN  PCI_CAP_DEV *PciDevice,
+  IN  PCI_CAP     *Cap,
+  IN  UINT16      SourceOffsetInCap,
+  OUT VOID        *DestinationBuffer,
+  IN  UINT16      Size
+  );
+
+
+/**
+  Write a slice of a capability instance.
+
+  The function performs as few config space accesses as possible (without
+  attempting 64-bit wide accesses). PciCapWrite() performs bounds checking on
+  DestinationOffsetInCap and Size, and only invokes PciDevice->WriteConfig() if
+  the requested transfer falls within Cap.
+
+  @param[in] PciDevice               Implementation-specific unique
+                                     representation of the PCI device in the
+                                     PCI hierarchy.
+
+  @param[in] Cap                     The capability instance to write, located
+                                     with PciCapListFindCap*().
+
+  @param[in] DestinationOffsetInCap  Destination offset relative to the
+                                     capability header to start writing at. A
+                                     zero value refers to the first byte of the
+                                     capability header.
+
+  @param[in] SourceBuffer            Buffer to read the data to be stored from.
+
+  @param[in] Size                    The number of bytes to transfer.
+
+  @retval RETURN_SUCCESS          Size bytes have been transferred from
+                                  SourceBuffer to Cap.
+
+  @retval RETURN_BAD_BUFFER_SIZE  Writing Size bytes starting at
+                                  DestinationOffsetInCap would not (entirely)
+                                  be contained within Cap, as suggested by
+                                  PCI_CAP_INFO.MaxSizeHint. No bytes have been
+                                  written.
+
+  @return                         Error codes propagated from
+                                  PciDevice->WriteConfig(). Fewer than Size
+                                  bytes may have been written.
+**/
+RETURN_STATUS
+EFIAPI
+PciCapWrite (
+  IN PCI_CAP_DEV *PciDevice,
+  IN PCI_CAP     *Cap,
+  IN UINT16      DestinationOffsetInCap,
+  IN VOID        *SourceBuffer,
+  IN UINT16      Size
+  );
+
+#endif // __PCI_CAP_LIB_H__
diff --git a/OvmfPkg/Library/BasePciCapLib/BasePciCapLib.h b/OvmfPkg/Library/BasePciCapLib/BasePciCapLib.h
new file mode 100644
index 000000000000..e631745834d9
--- /dev/null
+++ b/OvmfPkg/Library/BasePciCapLib/BasePciCapLib.h
@@ -0,0 +1,60 @@
+/** @file
+  Work with PCI capabilities in PCI config space -- internal type definitions.
+
+  Copyright (C) 2018, Red Hat, Inc.
+
+  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
+  http://opensource.org/licenses/bsd-license.php
+
+  THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
+  WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
+**/
+
+#ifndef __BASE_PCI_CAP_LIB_H__
+#define __BASE_PCI_CAP_LIB_H__
+
+#include <Library/OrderedCollectionLib.h>
+
+#include <Library/PciCapLib.h>
+
+//
+// Structure that uniquely identifies a capability instance and serves as key
+// for insertion and lookup.
+//
+typedef struct {
+  PCI_CAP_DOMAIN Domain;
+  UINT16         CapId;
+  UINT16         Instance;
+} PCI_CAP_KEY;
+
+//
+// In Instance==0 PCI_CAP objects, store NumInstances directly. In Instance>0
+// PCI_CAP objects, link Instance#0 of the same (Domain, CapId). This way
+// NumInstances needs maintenance in one object only, per (Domain, CapId) pair.
+//
+typedef union {
+  UINT16  NumInstances;
+  PCI_CAP *InstanceZero;
+} PCI_CAP_NUM_INSTANCES;
+
+//
+// Complete the incomplete PCI_CAP structure here.
+//
+struct PCI_CAP {
+  PCI_CAP_KEY           Key;
+  PCI_CAP_NUM_INSTANCES NumInstancesUnion;
+  UINT16                Offset;
+  UINT16                MaxSizeHint;
+  UINT8                 Version;
+};
+
+//
+// Complete the incomplete PCI_CAP_LIST structure here.
+//
+struct PCI_CAP_LIST {
+  ORDERED_COLLECTION *Capabilities;
+};
+
+#endif // __BASE_PCI_CAP_LIB_H__
diff --git a/OvmfPkg/Library/BasePciCapLib/BasePciCapLib.c b/OvmfPkg/Library/BasePciCapLib/BasePciCapLib.c
new file mode 100644
index 000000000000..6789359f0a54
--- /dev/null
+++ b/OvmfPkg/Library/BasePciCapLib/BasePciCapLib.c
@@ -0,0 +1,1007 @@
+/** @file
+  Work with PCI capabilities in PCI config space.
+
+  Provides functions to parse capabilities lists, and to locate, describe, read
+  and write capabilities. PCI config space access is abstracted away.
+
+  Copyright (C) 2018, Red Hat, Inc.
+
+  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
+  http://opensource.org/licenses/bsd-license.php
+
+  THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS, WITHOUT
+  WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
+**/
+
+#include <IndustryStandard/PciExpress21.h>
+
+#include <Library/BaseMemoryLib.h>
+#include <Library/DebugLib.h>
+#include <Library/MemoryAllocationLib.h>
+
+#include "BasePciCapLib.h"
+
+
+/**
+  Compare a standalone PCI_CAP_KEY against a PCI_CAP containing an embedded
+  PCI_CAP_KEY.
+
+  @param[in] PciCapKey  Pointer to the bare PCI_CAP_KEY.
+
+  @param[in] PciCap     Pointer to the PCI_CAP with the embedded PCI_CAP_KEY.
+
+  @retval <0  If PciCapKey compares less than PciCap->Key.
+
+  @retval  0  If PciCapKey compares equal to PciCap->Key.
+
+  @retval >0  If PciCapKey compares greater than PciCap->Key.
+**/
+STATIC
+INTN
+EFIAPI
+ComparePciCapKey (
+  IN CONST VOID *PciCapKey,
+  IN CONST VOID *PciCap
+  )
+{
+  CONST PCI_CAP_KEY *Key1;
+  CONST PCI_CAP_KEY *Key2;
+
+  Key1 = PciCapKey;
+  Key2 = &((CONST PCI_CAP *)PciCap)->Key;
+
+  if (Key1->Domain < Key2->Domain) {
+    return -1;
+  }
+  if (Key1->Domain > Key2->Domain) {
+    return 1;
+  }
+  if (Key1->CapId < Key2->CapId) {
+    return -1;
+  }
+  if (Key1->CapId > Key2->CapId) {
+    return 1;
+  }
+  if (Key1->Instance < Key2->Instance) {
+    return -1;
+  }
+  if (Key1->Instance > Key2->Instance) {
+    return 1;
+  }
+  return 0;
+}
+
+
+/**
+  Compare two PCI_CAP objects based on PCI_CAP.Key.
+
+  @param[in] PciCap1  Pointer to the first PCI_CAP.
+
+  @param[in] PciCap2  Pointer to the second PCI_CAP.
+
+  @retval <0  If PciCap1 compares less than PciCap2.
+
+  @retval  0  If PciCap1 compares equal to PciCap2.
+
+  @retval >0  If PciCap1 compares greater than PciCap2.
+**/
+STATIC
+INTN
+EFIAPI
+ComparePciCap (
+  IN CONST VOID *PciCap1,
+  IN CONST VOID *PciCap2
+  )
+{
+  CONST PCI_CAP_KEY *PciCap1Key;
+
+  PciCap1Key = &((CONST PCI_CAP *)PciCap1)->Key;
+  return ComparePciCapKey (PciCap1Key, PciCap2);
+}
+
+
+/**
+  Compare the standalone UINT16 config space offset of a capability header
+  against a PCI_CAP containing an embedded Offset.
+
+  @param[in] CapHdrOffset  Pointer to the bare UINT16 config space offset.
+
+  @param[in] PciCap        Pointer to the PCI_CAP with the embedded Offset.
+
+  @retval <0  If CapHdrOffset compares less than PciCap->Offset.
+
+  @retval  0  If CapHdrOffset compares equal to PciCap->Offset.
+
+  @retval >0  If CapHdrOffset compares greater than PciCap->Offset.
+**/
+STATIC
+INTN
+EFIAPI
+ComparePciCapOffsetKey (
+  IN CONST VOID *CapHdrOffset,
+  IN CONST VOID *PciCap
+  )
+{
+  UINT16 Offset1;
+  UINT16 Offset2;
+
+  Offset1 = *(CONST UINT16 *)CapHdrOffset;
+  Offset2 = ((CONST PCI_CAP *)PciCap)->Offset;
+  //
+  // Note: both Offset1 and Offset2 are promoted to INT32 below, and the
+  // subtraction takes place between INT32 values.
+  //
+  return Offset1 - Offset2;
+}
+
+
+/**
+  Compare two PCI_CAP objects based on PCI_CAP.Offset.
+
+  @param[in] PciCap1  Pointer to the first PCI_CAP.
+
+  @param[in] PciCap2  Pointer to the second PCI_CAP.
+
+  @retval <0  If PciCap1 compares less than PciCap2.
+
+  @retval  0  If PciCap1 compares equal to PciCap2.
+
+  @retval >0  If PciCap1 compares greater than PciCap2.
+**/
+STATIC
+INTN
+EFIAPI
+ComparePciCapOffset (
+  IN CONST VOID *PciCap1,
+  IN CONST VOID *PciCap2
+  )
+{
+  UINT16 Offset1;
+  UINT16 Offset2;
+
+  Offset1 = ((CONST PCI_CAP *)PciCap1)->Offset;
+  Offset2 = ((CONST PCI_CAP *)PciCap2)->Offset;
+  //
+  // Note: both Offset1 and Offset2 are promoted to INT32 below, and the
+  // subtraction takes place between INT32 values.
+  //
+  return Offset1 - Offset2;
+}
+
+
+/**
+  Insert a new instance of the PCI capability given by (Domain, CapId) in
+  CapList.
+
+  @param[in,out] CapList        The PCI_CAP_LIST into which the new PCI_CAP
+                                should be inserted. CapList will own the new
+                                PCI_CAP structure.
+
+  @param[in,out] CapHdrOffsets  Link the new PCI_CAP structure into the
+                                (non-owning) CapHdrOffsets collection as well.
+                                CapHdrOffsets orders the PCI_CAP structures
+                                based on the PCI_CAP.Offset member, and enables
+                                the calculation of PCI_CAP.MaxSizeHint.
+
+  @param[in] Domain             Whether the capability is normal or extended.
+
+  @param[in] CapId              Capability ID (specific to Domain).
+
+  @param[in] Offset             Config space offset at which the standard
+                                header of the capability starts. The caller is
+                                responsible for ensuring that Offset be DWORD
+                                aligned. The caller is also responsible for
+                                ensuring that Offset be within the config space
+                                identified by Domain.
+
+  @param[in] Version            The version number of the capability. The
+                                caller is responsible for passing 0 as Version
+                                if Domain is PciCapNormal.
+
+  @retval RETURN_SUCCESS           Insertion successful.
+
+  @retval RETURN_OUT_OF_RESOURCES  Memory allocation failed.
+
+  @retval RETURN_DEVICE_ERROR      A PCI_CAP with Offset is already linked by
+                                   CapHdrOffsets. This indicates a loop in the
+                                   capabilities list being parsed.
+**/
+STATIC
+RETURN_STATUS
+InsertPciCap (
+  IN OUT PCI_CAP_LIST       *CapList,
+  IN OUT ORDERED_COLLECTION *CapHdrOffsets,
+  IN     PCI_CAP_DOMAIN     Domain,
+  IN     UINT16             CapId,
+  IN     UINT16             Offset,
+  IN     UINT8              Version
+  )
+{
+  PCI_CAP                  *PciCap;
+  RETURN_STATUS            Status;
+  ORDERED_COLLECTION_ENTRY *PciCapEntry;
+  PCI_CAP                  *InstanceZero;
+
+  ASSERT ((Offset & 0x3) == 0);
+  ASSERT (Offset < (Domain == PciCapNormal ?
+                    PCI_MAX_CONFIG_OFFSET : PCI_EXP_MAX_CONFIG_OFFSET));
+  ASSERT (Domain == PciCapExtended || Version == 0);
+
+  //
+  // Set InstanceZero to suppress incorrect compiler/analyzer warnings.
+  //
+  InstanceZero = NULL;
+
+  //
+  // Allocate PciCap, and populate it assuming it is the first occurrence of
+  // (Domain, CapId). Note that PciCap->MaxSizeHint is not assigned the final
+  // value just yet.
+  //
+  PciCap = AllocatePool (sizeof *PciCap);
+  if (PciCap == NULL) {
+    return RETURN_OUT_OF_RESOURCES;
+  }
+  PciCap->Key.Domain                     = Domain;
+  PciCap->Key.CapId                      = CapId;
+  PciCap->Key.Instance                   = 0;
+  PciCap->NumInstancesUnion.NumInstances = 1;
+  PciCap->Offset                         = Offset;
+  PciCap->MaxSizeHint                    = 0;
+  PciCap->Version                        = Version;
+
+  //
+  // Add PciCap to CapList.
+  //
+  Status = OrderedCollectionInsert (CapList->Capabilities, &PciCapEntry,
+             PciCap);
+  if (RETURN_ERROR (Status)) {
+    if (Status == RETURN_OUT_OF_RESOURCES) {
+      goto FreePciCap;
+    }
+    ASSERT (Status == RETURN_ALREADY_STARTED);
+    //
+    // PciCap is not the first instance of (Domain, CapId). Add it as a new
+    // instance, taking the current instance count from Instance#0. Note that
+    // we don't bump the instance count maintained in Instance#0 just yet, to
+    // keep rollback on errors simple.
+    //
+    InstanceZero = OrderedCollectionUserStruct (PciCapEntry);
+    PciCap->Key.Instance = InstanceZero->NumInstancesUnion.NumInstances;
+    PciCap->NumInstancesUnion.InstanceZero = InstanceZero;
+
+    ASSERT (PciCap->Key.Instance > 0);
+    Status = OrderedCollectionInsert (CapList->Capabilities, &PciCapEntry,
+               PciCap);
+    if (Status == RETURN_OUT_OF_RESOURCES) {
+      goto FreePciCap;
+    }
+  }
+  //
+  // At this point, PciCap has been inserted in CapList->Capabilities, either
+  // with Instance==0 or with Instance>0. PciCapEntry is the iterator that
+  // links PciCap.
+  //
+  ASSERT_RETURN_ERROR (Status);
+
+  //
+  // Link PciCap into CapHdrOffsets too, to order it globally based on config
+  // space offset. Note that partial overlaps between capability headers is not
+  // possible: Offset is DWORD aligned, normal capability headers are 16-bit
+  // wide, and extended capability headers are 32-bit wide. Therefore any two
+  // capability headers either are distinct or start at the same offset
+  // (implying a loop in the respective capabilities list).
+  //
+  Status = OrderedCollectionInsert (CapHdrOffsets, NULL, PciCap);
+  if (RETURN_ERROR (Status)) {
+    if (Status == RETURN_ALREADY_STARTED) {
+      //
+      // Loop found; map return status accordingly.
+      //
+      Status = RETURN_DEVICE_ERROR;
+    }
+    goto DeletePciCapFromCapList;
+  }
+
+  //
+  // Now we can bump the instance count maintained in Instance#0, if PciCap is
+  // not the first instance of (Domain, CapId).
+  //
+  if (PciCap->Key.Instance > 0) {
+    InstanceZero->NumInstancesUnion.NumInstances++;
+  }
+  return RETURN_SUCCESS;
+
+DeletePciCapFromCapList:
+  OrderedCollectionDelete (CapList->Capabilities, PciCapEntry, NULL);
+
+FreePciCap:
+  FreePool (PciCap);
+
+  return Status;
+}
+
+
+/**
+  Calculate the MaxSizeHint member for a PCI_CAP object.
+
+  CalculatePciCapMaxSizeHint() may only be called once all capability instances
+  have been successfully processed by InsertPciCap().
+
+  @param[in,out] PciCap  The PCI_CAP object for which to calculate the
+                         MaxSizeHint member. The caller is responsible for
+                         passing a PCI_CAP object that has been created by a
+                         successful invocation of InsertPciCap().
+
+  @param[in] NextPciCap  If NextPciCap is NULL, then the caller is responsible
+                         for PciCap to represent the capability instance with
+                         the highest header offset in all config space. If
+                         NextPciCap is not NULL, then the caller is responsible
+                         for (a) having created NextPciCap with a successful
+                         invocation of InsertPciCap(), and (b) NextPciCap being
+                         the direct successor of PciCap in config space offset
+                         order, as ordered by ComparePciCapOffset().
+**/
+STATIC
+VOID
+CalculatePciCapMaxSizeHint (
+  IN OUT PCI_CAP *PciCap,
+  IN     PCI_CAP *NextPciCap OPTIONAL
+  )
+{
+  UINT16 ConfigSpaceSize;
+
+  ConfigSpaceSize = (PciCap->Key.Domain == PciCapNormal ?
+                     PCI_MAX_CONFIG_OFFSET : PCI_EXP_MAX_CONFIG_OFFSET);
+  //
+  // The following is guaranteed by the interface contract on
+  // CalculatePciCapMaxSizeHint().
+  //
+  ASSERT (NextPciCap == NULL || PciCap->Offset < NextPciCap->Offset);
+  //
+  // The following is guaranteed by the interface contract on InsertPciCap().
+  //
+  ASSERT (PciCap->Offset < ConfigSpaceSize);
+  //
+  // Thus we can safely subtract PciCap->Offset from either of
+  // - ConfigSpaceSize
+  // - and NextPciCap->Offset (if NextPciCap is not NULL).
+  //
+  // PciCap extends from PciCap->Offset to NextPciCap->Offset (if any), except
+  // it cannot cross config space boundary.
+  //
+  if (NextPciCap == NULL || NextPciCap->Offset >= ConfigSpaceSize) {
+    PciCap->MaxSizeHint = ConfigSpaceSize - PciCap->Offset;
+    return;
+  }
+  PciCap->MaxSizeHint = NextPciCap->Offset - PciCap->Offset;
+}
+
+
+/**
+  Debug dump a PCI_CAP_LIST object at the DEBUG_VERBOSE level.
+
+  @param[in] CapList  The PCI_CAP_LIST object to dump.
+**/
+STATIC
+VOID
+EFIAPI
+DebugDumpPciCapList (
+  IN PCI_CAP_LIST *CapList
+  )
+{
+  DEBUG_CODE_BEGIN ();
+  ORDERED_COLLECTION_ENTRY *PciCapEntry;
+
+  for (PciCapEntry = OrderedCollectionMin (CapList->Capabilities);
+       PciCapEntry != NULL;
+       PciCapEntry = OrderedCollectionNext (PciCapEntry)) {
+    PCI_CAP       *PciCap;
+    RETURN_STATUS Status;
+    PCI_CAP_INFO  Info;
+
+    PciCap = OrderedCollectionUserStruct (PciCapEntry);
+    Status = PciCapGetInfo (PciCap, &Info);
+    //
+    // PciCapGetInfo() cannot fail in this library instance.
+    //
+    ASSERT_RETURN_ERROR (Status);
+
+    DEBUG ((DEBUG_VERBOSE,
+      "%a:%a: %a 0x%04x %03u/%03u v0x%x @0x%03x+0x%03x\n", gEfiCallerBaseName,
+      __FUNCTION__, (Info.Domain == PciCapNormal ? "Norm" : "Extd"),
+      Info.CapId, Info.Instance, Info.NumInstances, Info.Version, Info.Offset,
+      Info.MaxSizeHint));
+  }
+  DEBUG_CODE_END ();
+}
+
+
+/**
+  Empty a collection of PCI_CAP structures, optionally releasing the referenced
+  PCI_CAP structures themselves. Release the collection at last.
+
+  @param[in,out] PciCapCollection  The collection to empty and release.
+
+  @param[in] FreePciCap            TRUE if the PCI_CAP structures linked by
+                                   PciCapCollection should be released. When
+                                   FALSE, the caller is responsible for
+                                   retaining at least one reference to each
+                                   PCI_CAP structure originally linked by
+                                   PciCapCollection.
+**/
+STATIC
+VOID
+EmptyAndUninitPciCapCollection (
+  IN OUT ORDERED_COLLECTION *PciCapCollection,
+  IN     BOOLEAN            FreePciCap
+  )
+{
+  ORDERED_COLLECTION_ENTRY *PciCapEntry;
+  ORDERED_COLLECTION_ENTRY *NextEntry;
+
+  for (PciCapEntry = OrderedCollectionMin (PciCapCollection);
+       PciCapEntry != NULL;
+       PciCapEntry = NextEntry) {
+    PCI_CAP *PciCap;
+
+    NextEntry = OrderedCollectionNext (PciCapEntry);
+    OrderedCollectionDelete (PciCapCollection, PciCapEntry, (VOID **)&PciCap);
+    if (FreePciCap) {
+      FreePool (PciCap);
+    }
+  }
+  OrderedCollectionUninit (PciCapCollection);
+}
+
+
+/**
+  Parse the capabilities lists (both normal and extended, as applicable) of a
+  PCI device.
+
+  If the PCI device has no capabilities, that per se will not fail
+  PciCapListInit(); an empty capabilities list will be represented.
+
+  If the PCI device is found to be PCI Express, then an attempt will be made to
+  parse the extended capabilities list as well. If the first extended config
+  space access -- via PciDevice->ReadConfig() with SourceOffset=0x100 and
+  Size=4 -- fails, that per se will not fail PciCapListInit(); the device will
+  be assumed to have no extended capabilities.
+
+  @param[in] PciDevice  Implementation-specific unique representation of the
+                        PCI device in the PCI hierarchy.
+
+  @param[out] CapList   Opaque data structure that holds an in-memory
+                        representation of the parsed capabilities lists of
+                        PciDevice.
+
+  @retval RETURN_SUCCESS           The capabilities lists have been parsed from
+                                   config space.
+
+  @retval RETURN_OUT_OF_RESOURCES  Memory allocation failed.
+
+  @retval RETURN_DEVICE_ERROR      A loop or some other kind of invalid pointer
+                                   was detected in the capabilities lists of
+                                   PciDevice.
+
+  @return                          Error codes propagated from
+                                   PciDevice->ReadConfig().
+**/
+RETURN_STATUS
+EFIAPI
+PciCapListInit (
+  IN  PCI_CAP_DEV  *PciDevice,
+  OUT PCI_CAP_LIST **CapList
+  )
+{
+  PCI_CAP_LIST             *OutCapList;
+  RETURN_STATUS            Status;
+  ORDERED_COLLECTION       *CapHdrOffsets;
+  UINT16                   PciStatusReg;
+  BOOLEAN                  DeviceIsExpress;
+  ORDERED_COLLECTION_ENTRY *OffsetEntry;
+
+  //
+  // Allocate the output structure.
+  //
+  OutCapList = AllocatePool (sizeof *OutCapList);
+  if (OutCapList == NULL) {
+    return RETURN_OUT_OF_RESOURCES;
+  }
+  //
+  // The OutCapList->Capabilities collection owns the PCI_CAP structures and
+  // orders them based on PCI_CAP.Key.
+  //
+  OutCapList->Capabilities = OrderedCollectionInit (ComparePciCap,
+                               ComparePciCapKey);
+  if (OutCapList->Capabilities == NULL) {
+    Status = RETURN_OUT_OF_RESOURCES;
+    goto FreeOutCapList;
+  }
+
+  //
+  // The (temporary) CapHdrOffsets collection only references PCI_CAP
+  // structures, and orders them based on PCI_CAP.Offset.
+  //
+  CapHdrOffsets = OrderedCollectionInit (ComparePciCapOffset,
+                    ComparePciCapOffsetKey);
+  if (CapHdrOffsets == NULL) {
+    Status = RETURN_OUT_OF_RESOURCES;
+    goto FreeCapabilities;
+  }
+
+  //
+  // Whether the device is PCI Express depends on the normal capability with
+  // identifier EFI_PCI_CAPABILITY_ID_PCIEXP.
+  //
+  DeviceIsExpress = FALSE;
+
+  //
+  // Check whether a normal capabilities list is present. If there's none,
+  // that's not an error; we'll just return OutCapList->Capabilities empty.
+  //
+  Status = PciDevice->ReadConfig (PciDevice, PCI_PRIMARY_STATUS_OFFSET,
+                        &PciStatusReg, sizeof PciStatusReg);
+  if (RETURN_ERROR (Status)) {
+    goto FreeCapHdrOffsets;
+  }
+  if ((PciStatusReg & EFI_PCI_STATUS_CAPABILITY) != 0) {
+    UINT8 NormalCapHdrOffset;
+
+    //
+    // Fetch the start offset of the normal capabilities list.
+    //
+    Status = PciDevice->ReadConfig (PciDevice, PCI_CAPBILITY_POINTER_OFFSET,
+                          &NormalCapHdrOffset, sizeof NormalCapHdrOffset);
+    if (RETURN_ERROR (Status)) {
+      goto FreeCapHdrOffsets;
+    }
+
+    //
+    // Traverse the normal capabilities list.
+    //
+    NormalCapHdrOffset &= 0xFC;
+    while (NormalCapHdrOffset > 0) {
+      EFI_PCI_CAPABILITY_HDR NormalCapHdr;
+
+      Status = PciDevice->ReadConfig (PciDevice, NormalCapHdrOffset,
+                            &NormalCapHdr, sizeof NormalCapHdr);
+      if (RETURN_ERROR (Status)) {
+        goto FreeCapHdrOffsets;
+      }
+
+      Status = InsertPciCap (OutCapList, CapHdrOffsets, PciCapNormal,
+                 NormalCapHdr.CapabilityID, NormalCapHdrOffset, 0);
+      if (RETURN_ERROR (Status)) {
+        goto FreeCapHdrOffsets;
+      }
+
+      if (NormalCapHdr.CapabilityID == EFI_PCI_CAPABILITY_ID_PCIEXP) {
+        DeviceIsExpress = TRUE;
+      }
+      NormalCapHdrOffset = NormalCapHdr.NextItemPtr & 0xFC;
+    }
+  }
+
+  //
+  // If the device has been found PCI Express, attempt to traverse the extended
+  // capabilities list. It starts right after the normal config space.
+  //
+  if (DeviceIsExpress) {
+    UINT16 ExtendedCapHdrOffset;
+
+    ExtendedCapHdrOffset = PCI_MAX_CONFIG_OFFSET;
+    while (ExtendedCapHdrOffset > 0) {
+      PCI_EXPRESS_EXTENDED_CAPABILITIES_HEADER ExtendedCapHdr;
+
+      Status = PciDevice->ReadConfig (PciDevice, ExtendedCapHdrOffset,
+                            &ExtendedCapHdr, sizeof ExtendedCapHdr);
+      //
+      // If the first extended config space access fails, assume the device has
+      // no extended capabilities. If the first extended config space access
+      // succeeds but we read an "all bits zero" extended capability header,
+      // that means (by spec) the device has no extended capabilities.
+      //
+      if (ExtendedCapHdrOffset == PCI_MAX_CONFIG_OFFSET &&
+          (RETURN_ERROR (Status) ||
+           IsZeroBuffer (&ExtendedCapHdr, sizeof ExtendedCapHdr))) {
+        break;
+      }
+      if (RETURN_ERROR (Status)) {
+        goto FreeCapHdrOffsets;
+      }
+
+      Status = InsertPciCap (OutCapList, CapHdrOffsets, PciCapExtended,
+                 ExtendedCapHdr.CapabilityId, ExtendedCapHdrOffset,
+                 ExtendedCapHdr.CapabilityVersion);
+      if (RETURN_ERROR (Status)) {
+        goto FreeCapHdrOffsets;
+      }
+
+      ExtendedCapHdrOffset = ExtendedCapHdr.NextCapabilityOffset & 0xFFC;
+      if (ExtendedCapHdrOffset > 0 &&
+          ExtendedCapHdrOffset < PCI_MAX_CONFIG_OFFSET) {
+        //
+        // Invalid capability pointer.
+        //
+        Status = RETURN_DEVICE_ERROR;
+        goto FreeCapHdrOffsets;
+      }
+    }
+  }
+
+  //
+  // Both capabilities lists have been parsed; compute the PCI_CAP.MaxSizeHint
+  // members if at least one capability has been found. In parallel, evacuate
+  // the CapHdrOffsets collection.
+  //
+  // At first, set OffsetEntry to the iterator of the PCI_CAP object with the
+  // lowest Offset (if such exists).
+  //
+  OffsetEntry = OrderedCollectionMin (CapHdrOffsets);
+  if (OffsetEntry != NULL) {
+    ORDERED_COLLECTION_ENTRY *NextOffsetEntry;
+    PCI_CAP                  *PciCap;
+
+    //
+    // Initialize NextOffsetEntry to the iterator of the PCI_CAP object with
+    // the second lowest Offset (if such exists).
+    //
+    NextOffsetEntry = OrderedCollectionNext (OffsetEntry);
+    //
+    // Calculate MaxSizeHint for all PCI_CAP objects except the one with the
+    // highest Offset.
+    //
+    while (NextOffsetEntry != NULL) {
+      PCI_CAP *NextPciCap;
+
+      OrderedCollectionDelete (CapHdrOffsets, OffsetEntry, (VOID **)&PciCap);
+      NextPciCap = OrderedCollectionUserStruct (NextOffsetEntry);
+      CalculatePciCapMaxSizeHint (PciCap, NextPciCap);
+
+      OffsetEntry = NextOffsetEntry;
+      NextOffsetEntry = OrderedCollectionNext (OffsetEntry);
+    }
+    //
+    // Calculate MaxSizeHint for the PCI_CAP object with the highest Offset.
+    //
+    OrderedCollectionDelete (CapHdrOffsets, OffsetEntry, (VOID **)&PciCap);
+    CalculatePciCapMaxSizeHint (PciCap, NULL);
+  }
+  ASSERT (OrderedCollectionIsEmpty (CapHdrOffsets));
+  OrderedCollectionUninit (CapHdrOffsets);
+
+  DebugDumpPciCapList (OutCapList);
+  *CapList = OutCapList;
+  return RETURN_SUCCESS;
+
+FreeCapHdrOffsets:
+  EmptyAndUninitPciCapCollection (CapHdrOffsets, FALSE);
+
+FreeCapabilities:
+  EmptyAndUninitPciCapCollection (OutCapList->Capabilities, TRUE);
+
+FreeOutCapList:
+  FreePool (OutCapList);
+
+  ASSERT (RETURN_ERROR (Status));
+  DEBUG ((DEBUG_ERROR, "%a:%a: %r\n", gEfiCallerBaseName, __FUNCTION__,
+    Status));
+  return Status;
+}
+
+
+/**
+  Free the resources used by CapList.
+
+  @param[in] CapList  The PCI_CAP_LIST object to free, originally produced by
+                      PciCapListInit().
+**/
+VOID
+EFIAPI
+PciCapListUninit (
+  IN PCI_CAP_LIST *CapList
+  )
+{
+  EmptyAndUninitPciCapCollection (CapList->Capabilities, TRUE);
+  FreePool (CapList);
+}
+
+
+/**
+  Locate a capability instance in the parsed capabilities lists.
+
+  @param[in] CapList   The PCI_CAP_LIST object produced by PciCapListInit().
+
+  @param[in] Domain    Distinguishes whether CapId is 8-bit wide and
+                       interpreted in normal config space, or 16-bit wide and
+                       interpreted in extended config space. Capability ID
+                       definitions are relative to domain.
+
+  @param[in] CapId     Capability identifier to look up.
+
+  @param[in] Instance  Domain and CapId may identify a multi-instance
+                       capability. When Instance is zero, the first instance of
+                       the capability is located (in list traversal order --
+                       which may not mean increasing config space offset
+                       order). Higher Instance values locate subsequent
+                       instances of the same capability (in list traversal
+                       order).
+
+  @param[out] Cap      The capability instance that matches the search
+                       criteria. Cap is owned by CapList and becomes invalid
+                       when CapList is freed with PciCapListUninit().
+                       PciCapListFindCap() may be called with Cap set to NULL,
+                       in order to test the existence of a specific capability
+                       instance.
+
+  @retval RETURN_SUCCESS    The capability instance identified by (Domain,
+                            CapId, Instance) has been found.
+
+  @retval RETURN_NOT_FOUND  The requested (Domain, CapId, Instance) capability
+                            instance does not exist.
+**/
+RETURN_STATUS
+EFIAPI
+PciCapListFindCap (
+  IN  PCI_CAP_LIST   *CapList,
+  IN  PCI_CAP_DOMAIN Domain,
+  IN  UINT16         CapId,
+  IN  UINT16         Instance,
+  OUT PCI_CAP        **Cap    OPTIONAL
+  )
+{
+  PCI_CAP_KEY              Key;
+  ORDERED_COLLECTION_ENTRY *PciCapEntry;
+
+  Key.Domain   = Domain;
+  Key.CapId    = CapId;
+  Key.Instance = Instance;
+
+  PciCapEntry = OrderedCollectionFind (CapList->Capabilities, &Key);
+  if (PciCapEntry == NULL) {
+    return RETURN_NOT_FOUND;
+  }
+  if (Cap != NULL) {
+    *Cap = OrderedCollectionUserStruct (PciCapEntry);
+  }
+  return RETURN_SUCCESS;
+}
+
+
+/**
+  Locate the first instance of the capability given by (Domain, CapId) such
+  that the instance's Version is greater than or equal to MinVersion.
+
+  This is a convenience function that may save client code calls to
+  PciCapListFindCap() and PciCapGetInfo().
+
+  @param[in] CapList     The PCI_CAP_LIST object produced by PciCapListInit().
+
+  @param[in] Domain      Distinguishes whether CapId is 8-bit wide and
+                         interpreted in normal config space, or 16-bit wide and
+                         interpreted in extended config space. Capability ID
+                         definitions are relative to domain.
+
+  @param[in] CapId       Capability identifier to look up.
+
+  @param[in] MinVersion  The minimum version that the capability instance is
+                         required to have. Note that all capability instances
+                         in Domain=PciCapNormal have Version=0.
+
+  @param[out] Cap        The first capability instance that matches the search
+                         criteria. Cap is owned by CapList and becomes invalid
+                         when CapList is freed with PciCapListUninit().
+                         PciCapListFindCapVersion() may be called with Cap set
+                         to NULL, in order just to test whether the search
+                         criteria are satisfiable.
+
+  @retval RETURN_SUCCESS    The first capability instance matching (Domain,
+                            CapId, MinVersion) has been located.
+
+  @retval RETURN_NOT_FOUND  No capability instance matches (Domain, CapId,
+                            MinVersion).
+**/
+RETURN_STATUS
+EFIAPI
+PciCapListFindCapVersion (
+  IN  PCI_CAP_LIST   *CapList,
+  IN  PCI_CAP_DOMAIN Domain,
+  IN  UINT16         CapId,
+  IN  UINT8          MinVersion,
+  OUT PCI_CAP        **Cap      OPTIONAL
+  )
+{
+  PCI_CAP_KEY              Key;
+  ORDERED_COLLECTION_ENTRY *PciCapEntry;
+
+  //
+  // Start the version checks at Instance#0 of (Domain, CapId).
+  //
+  Key.Domain   = Domain;
+  Key.CapId    = CapId;
+  Key.Instance = 0;
+
+  for (PciCapEntry = OrderedCollectionFind (CapList->Capabilities, &Key);
+       PciCapEntry != NULL;
+       PciCapEntry = OrderedCollectionNext (PciCapEntry)) {
+    PCI_CAP *PciCap;
+
+    PciCap = OrderedCollectionUserStruct (PciCapEntry);
+    //
+    // PCI_CAP.Key ordering keeps instances of the same (Domain, CapId)
+    // adjacent to each other, so stop searching if either Domain or CapId
+    // changes.
+    //
+    if (PciCap->Key.Domain != Domain || PciCap->Key.CapId != CapId) {
+      break;
+    }
+    if (PciCap->Version >= MinVersion) {
+      //
+      // Match found.
+      //
+      if (Cap != NULL) {
+        *Cap = PciCap;
+      }
+      return RETURN_SUCCESS;
+    }
+  }
+  return RETURN_NOT_FOUND;
+}
+
+
+/**
+  Get information about a PCI Capability instance.
+
+  @param[in] Cap    The capability instance to get info about, located with
+                    PciCapListFindCap*().
+
+  @param[out] Info  A PCI_CAP_INFO structure that describes the properties of
+                    Cap.
+
+  @retval RETURN_SUCCESS  Fields of Info have been set.
+
+  @return                 Unspecified error codes, if filling in Info failed
+                          for some reason.
+**/
+RETURN_STATUS
+EFIAPI
+PciCapGetInfo (
+  IN  PCI_CAP      *Cap,
+  OUT PCI_CAP_INFO *Info
+  )
+{
+  PCI_CAP *InstanceZero;
+
+  InstanceZero = (Cap->Key.Instance == 0 ? Cap :
+                  Cap->NumInstancesUnion.InstanceZero);
+
+  Info->Domain       = Cap->Key.Domain;
+  Info->CapId        = Cap->Key.CapId;
+  Info->NumInstances = InstanceZero->NumInstancesUnion.NumInstances;
+  Info->Instance     = Cap->Key.Instance;
+  Info->Offset       = Cap->Offset;
+  Info->MaxSizeHint  = Cap->MaxSizeHint;
+  Info->Version      = Cap->Version;
+
+  return RETURN_SUCCESS;
+}
+
+
+/**
+  Read a slice of a capability instance.
+
+  The function performs as few config space accesses as possible (without
+  attempting 64-bit wide accesses). PciCapRead() performs bounds checking on
+  SourceOffsetInCap and Size, and only invokes PciDevice->ReadConfig() if the
+  requested transfer falls within Cap.
+
+  @param[in] PciDevice           Implementation-specific unique representation
+                                 of the PCI device in the PCI hierarchy.
+
+  @param[in] Cap                 The capability instance to read, located with
+                                 PciCapListFindCap*().
+
+  @param[in] SourceOffsetInCap   Source offset relative to the capability
+                                 header to start reading from. A zero value
+                                 refers to the first byte of the capability
+                                 header.
+
+  @param[out] DestinationBuffer  Buffer to store the read data to.
+
+  @param[in] Size                The number of bytes to transfer.
+
+  @retval RETURN_SUCCESS          Size bytes have been transferred from Cap to
+                                  DestinationBuffer.
+
+  @retval RETURN_BAD_BUFFER_SIZE  Reading Size bytes starting from
+                                  SourceOffsetInCap would not (entirely) be
+                                  contained within Cap, as suggested by
+                                  PCI_CAP_INFO.MaxSizeHint. No bytes have been
+                                  read.
+
+  @return                         Error codes propagated from
+                                  PciDevice->ReadConfig(). Fewer than Size
+                                  bytes may have been read.
+**/
+RETURN_STATUS
+EFIAPI
+PciCapRead (
+  IN  PCI_CAP_DEV *PciDevice,
+  IN  PCI_CAP     *Cap,
+  IN  UINT16      SourceOffsetInCap,
+  OUT VOID        *DestinationBuffer,
+  IN  UINT16      Size
+  )
+{
+  //
+  // Note: all UINT16 values are promoted to INT32 below, and addition and
+  // comparison take place between INT32 values.
+  //
+  if (SourceOffsetInCap + Size > Cap->MaxSizeHint) {
+    return RETURN_BAD_BUFFER_SIZE;
+  }
+  return PciDevice->ReadConfig (PciDevice, Cap->Offset + SourceOffsetInCap,
+                      DestinationBuffer, Size);
+}
+
+
+/**
+  Write a slice of a capability instance.
+
+  The function performs as few config space accesses as possible (without
+  attempting 64-bit wide accesses). PciCapWrite() performs bounds checking on
+  DestinationOffsetInCap and Size, and only invokes PciDevice->WriteConfig() if
+  the requested transfer falls within Cap.
+
+  @param[in] PciDevice               Implementation-specific unique
+                                     representation of the PCI device in the
+                                     PCI hierarchy.
+
+  @param[in] Cap                     The capability instance to write, located
+                                     with PciCapListFindCap*().
+
+  @param[in] DestinationOffsetInCap  Destination offset relative to the
+                                     capability header to start writing at. A
+                                     zero value refers to the first byte of the
+                                     capability header.
+
+  @param[in] SourceBuffer            Buffer to read the data to be stored from.
+
+  @param[in] Size                    The number of bytes to transfer.
+
+  @retval RETURN_SUCCESS          Size bytes have been transferred from
+                                  SourceBuffer to Cap.
+
+  @retval RETURN_BAD_BUFFER_SIZE  Writing Size bytes starting at
+                                  DestinationOffsetInCap would not (entirely)
+                                  be contained within Cap, as suggested by
+                                  PCI_CAP_INFO.MaxSizeHint. No bytes have been
+                                  written.
+
+  @return                         Error codes propagated from
+                                  PciDevice->WriteConfig(). Fewer than Size
+                                  bytes may have been written.
+**/
+RETURN_STATUS
+EFIAPI
+PciCapWrite (
+  IN PCI_CAP_DEV *PciDevice,
+  IN PCI_CAP     *Cap,
+  IN UINT16      DestinationOffsetInCap,
+  IN VOID        *SourceBuffer,
+  IN UINT16      Size
+  )
+{
+  //
+  // Note: all UINT16 values are promoted to INT32 below, and addition and
+  // comparison take place between INT32 values.
+  //
+  if (DestinationOffsetInCap + Size > Cap->MaxSizeHint) {
+    return RETURN_BAD_BUFFER_SIZE;
+  }
+  return PciDevice->WriteConfig (PciDevice,
+                      Cap->Offset + DestinationOffsetInCap, SourceBuffer,
+                      Size);
+}
-- 
2.14.1.3.gb7cf6e02401b