《PCI Express体系结构导读》随记 —— 第I篇 第2章 PCI总线的桥与配置（23）

接前一篇文章：《PCI Express体系结构导读》随记 —— 第I篇 第2章 PCI总线的桥与配置（22）

2.4?PCI总线的配置

PCI总线定义了两类配置请求，一个是Type 00h配置请求，另一个是Type 01h配置请求。PCI总线使用这些配置请求访问PCI总线树上的设备配置空间，包括PCI桥和PCI Agent设备的配置空间。

其中，HOST主桥或者PCI桥使用Type 00h配置请求，来访问与HOST主桥或者PCI桥直接相连的PCI Agent设备或者PCI桥（此时PCI桥作为一个PCI设备，接收访问其配置空间的读写请求）；而HOST主桥或者PCI桥使用Type 01h配置请求，需要至少穿越一个PCI桥，访问没有与其直接相连的PCI Agent设备或者PCI桥。如图2-8所示，HOST主桥可以使用Type 00h配置请求访问PCI设备01，而使用Type 01h配置请求通过PCI桥1、2或者3转换为Type 00h配置请求之后，访问PCI总线树上的PCI设备11、21、22、31和32。也就是说，最终Type 01h配置请求（都）将会被转换为Type 00h配置请求，然后再访问PCI Agent设备。

2.4.3 PCI总线树Bus号的初始化

在一个处理器系统中，每一个HOST主桥都推出一颗PCI总线树。在一颗PCI总线树中有多少个PCI桥（包括HOST主桥），就含有多少条PCI总线。系统软件在遍历当前PCI总线树时，需要首先对这些PCI总线进行编号，即初始化PCI桥的Primary、Secondary和Subordinate Bus Number寄存器。

在一个处理器系统中，一般将与HOST主桥直接相连的PCI总线被命名为PCI总线0。然后系统软件使用DFS（Depth First Search，深度优先搜索）算法，依次对其它PCI总线进行编号。值得注意的是，与HOST主桥直接相连的PCI总线，其编号都为0，因此当处理器系统中存在多个HOST主桥时，将有多个编号为0的PCI总线，但是这些编号为0的PCI总线分属不同的PCI总线域，其含义并不相同（如上图中的PCI总线x0和PCI总线y0）。

在一个处理器系统中，PCI总线树的结构如图2-13所示（当然在一个实际的处理器系统中，很少会出现这样复杂的PCI总线树结构，本节采用这个结构的目的是便于说明PCI总线号的分配过程）：

在PCI总线中，系统软件使用深度优先算法对PCI总线树进行遍历。深度优先（Depth First Search，DFS）算法与广度优先（Breadth First Search，BFS）算法是遍历树型结构的常用算法。与BFS算法相比，DFS算法的空间复杂度较低，因此绝大多数系统在遍历PCI总线树时，都使用DFS算法而不是BFS算法。

DFS是搜索算法的一种，其实现机制是沿着一颗树的深度遍历各个节点，并尽可能深地搜索树的分支。DFS的算法为线性时间复杂度，适合对拓扑结构未知的树进行遍历。在一个处理器系统的初始化阶段，PCI总线树的拓扑结构是未知的，适合使用DFS算法进行遍历。下文以图2-13为例，说明系统软件如何使用DFS算法，分配PCI总线号，并初始化PCI桥中的Primary Bus Number、Secondary Bus Number和Subordinate Bus number寄存器。

所谓DFS算法是指按照深度优先的原则遍历PCI胖树，其步骤如下：?

（1）HOST主桥扫描PCI总线0上的设备。系统软件首先忽略所有这条总线上的PCI Agent设备，因为在这些设备之下不会挂接新的PCI总线。例如PCI设备01下不可能挂接新的PCI总线；

（2）HOST主桥首先发现PCI桥1，并将PCI桥1的Secondary Bus命名为PCI总线1。系统软件将初始化PCI桥1的配置空间，将PCI桥1的Primary Bus Number寄存器赋值为0，而将Secondary Bus Number寄存器赋值为1，即PCI桥1的上游PCI总线号为0，而下游PCI总线号为1；

（3）扫描PCI总线1，发现PCI桥2，并将PCI桥2的Secondary Bus命名为PCI总线2。系统软件将初始化PCI桥2的配置空间，将PCI桥2的Primary Bus Number寄存器赋值为1，而将Secondary Bus Number寄存器赋值为2；

（4）扫描PCI总线2，发现PCI桥3，并将PCI桥3的Secondary Bus命名为PCI总线3。系统软件将初始化PCI桥3的配置空间，将PCI桥3的Primary Bus Number寄存器赋值为2，而将Secondary Bus Number寄存器赋值为3；

（5）扫描PCI总线3，没有发现任何PCI桥，这表示PCI总线3下不可能有新的总线，此时系统软件将PCI桥3的Subordinate Bus number寄存器赋值为3。系统软件在完成PCI总线3的扫描后，将回退到PCI总线3的上一级总线，即PCI总线2，继续进行扫描；

（6）在重新扫描PCI总线2时，系统软件发现PCI总线2上除了PCI桥3之外没有发现新的PCI桥，而PCI桥3之下的所有设备已经完成了扫描过程，此时系统软件将PCI桥2的Subordinate Bus number寄存器赋值为3。继续回退到PCI总线1；

（7）PCI总线1上除了PCI桥2外，没有其它桥片，于是继续回退到PCI总线0，并将PCI桥1的Subordinate Bus number寄存器赋值为3；

（8）在PCI总线0上，系统软件扫描到PCI桥4，则首先将PCI桥4的Primary Bus Number寄存器赋值为0，而将Secondary Bus Number寄存器赋值为4，即PCI桥1的上游PCI总线号为0，而下游PCI总线号为4（注意，步骤（2）中，PCI桥1的上游PCI总线号为0，而下游PCI总线号为1）；

（9）系统软件发现PCI总线4上没有任何PCI桥，将结束对PCI总线4的扫描，并将PCI桥4的Subordinate Bus number寄存器赋值为4，之后回退到PCI总线4的上游总线，即PCI总线0继续进行扫描；

（10）系统软件发现在PCI总线0上的两个桥片PCI总线0和PCI总线4都已完成扫描后，将结束对PCI总线的DFS遍历全过程。

从以上算法可以看出，PCI桥的Primary Bus和Secondary Bus号的分配在遍历PCI总线树的过程中从上向下分配，而Subordinate Bus号是从下向上分配的，因为只有确定了一个PCI桥之下究竟有多少条PCI总线后，才能初始化该PCI桥的Subordinate Bus号。

更多内容请看下回。