When a computer first powers up or undergoes a reset, the system software actually knows very little about the hardware connected to it. To establish communication, configuration software must systematically scan the PCI Express (PCIe) fabric to discover the machine’s topology, a process known as enumeration.
Here is a step-by-step walkthrough of how system software discovers devices, handles missing hardware, and assigns bus numbers using a depth-first search.
Discovering Devices via Vendor IDs
The enumeration process relies heavily on a unique identifier built into every piece of PCIe hardware. The configuration software probes the system by attempting to read the Vendor ID register for every possible combination of Bus, Device, and Function (BDF) number.
The Vendor ID is a hardwired 16-bit value uniquely assigned to each hardware manufacturer by the PCI-SIG. If the software reads a location and receives a valid Vendor ID, it knows a Function exists at that specific address. Once a device is found, the software checks its Header Type field to determine what kind of device it is: a value of 0 indicates an Endpoint, while a value of 1 indicates a PCI-to-PCI (P2P) bridge.
Handling Missing or Unready Devices
While probing the topology, the software will inevitably try to communicate with empty slots or devices that are still booting up. PCIe handles these two scenarios elegantly to prevent the system from crashing during enumeration:
- The Device is Not Present: If the software targets an empty slot, the upstream bridge returns a “Completion without data” packet containing an Unsupported Request (UR) status. To maintain compatibility with older legacy software, the Root Complex translates this UR status and returns a data value of all ones (FFFFh) to the processor. The enumeration software expects to see FFFFh when probing for devices; it simply understands this means the device isn’t there, and it does not treat it as a system error.
- The Device is Not Ready: Sometimes a device is physically present but needs time to initialize, such as loading its configuration registers from an external EEPROM. If accessed before it is ready, the device returns a Configuration Request Retry Status (CRS). To prevent the software from stalling, the Root Complex can feed the host an artificial Vendor ID of 0001h. Software interprets this fake ID as a signal that the device is present but experiencing a lengthy delay, allowing the software to perform other tasks and query the device again later.
Assigning Bus Numbers: The Depth-First Search
To route traffic successfully, every bus in the PCIe tree must be assigned a unique number. The system starts with the Root Complex, which is assigned Bus 0.
From there, the software utilizes a strict “depth-first search” algorithm to discover and number the rest of the topology. Here is how the process unfolds:
- Scanning the Bus: The software begins scanning Bus 0, looking for valid Vendor IDs.
- Discovering a Bridge: When it finds a device with a Header Type of 1, it knows it has found a bridge that creates a new bus.
- Assigning Initial Numbers: The software programs the bridge with three numbers:
- The Primary Bus Number (the bus it is currently on, e.g., 0).
- The Secondary Bus Number (the new bus it creates downstream, e.g., 1).
- The Subordinate Bus Number. Because the software doesn’t yet know how many buses exist further down this branch, it temporarily sets this to the maximum possible value of 255.
- Diving Deeper (The Depth-First Rule): Instead of continuing to scan the rest of Bus 0, the software immediately pauses its current scan and drops down to search the newly discovered Bus 1.
- Reaching the Bottom: The software repeats this process—finding a bridge, numbering the new bus, and immediately diving down—until it hits a bus that only contains Endpoints (or is completely empty).
- Updating and Backing Up: Once the software reaches the bottom of a branch, it knows exactly what the highest bus number on that branch is. It updates the upstream bridge’s Subordinate Bus Number to reflect this true highest number. Finally, it backs up one level to the previous bus and continues scanning across from where it left off.
Through this methodical process of probing Vendor IDs and diving down every bridge it finds, the configuration software successfully maps the entire PCIe fabric, numbering every bus and identifying every Endpoint so the system can begin routing data.