PCI总线的配置

在PCI总线中，系统软件使用深度优先DFS算法对PCI总线树进行遍历，DFS算法和广度优先BFS(Breadth First Search)算法是遍历树型结构的常用算法。与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。
(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号。

2.4.4 PCI总线Device号的分配

一条PCI总线会挂接各种各样的PCI设备，而每一个PCI设备在PCI总线下具有唯一的设备号。系统软件通过总线号和设备号定位一个PCI设备之后，才能访问这个PCI设备的配置寄存器。值得注意的是，系统软件使用“地址寻址方式”访问PCI设备的存储器和I/O地址空间，这与访问配置空间使用的“ID寻址方式”不同。
PCI设备的IDSEL信号与PCI总线的AD[31:0]信号的连接关系决定了该设备在这条PCI总线的设备号。如上文所述，每一个PCI设备都使用独立的IDSEL信号，该信号将与PCI总线的AD[31:0]信号连接，IDSEL信号的含义见第1.2.2节。
在此我们简要回顾PCI的配置读写事务使用的时序。如图1?3所示，PCI总线事务由一个地址周期加若干个数据周期组成。在进行配置读写请求总线事务时，C/BE#信号线的值在地址周期中为0x1010或者为0x1011，表示当前总线事务为配置读或者配置写请求。此时出现在AD[31:0]总线上的值并不是目标设备的PCI总线地址，而是目标设备的ID号，这与PCI总线进行I/O或者存储器请求时不同，因为PCI总线使用ID号而不是PCI总线地址对配置空间进行访问。
如图2?12所示，在配置读写总线事务的地址周期中，AD[10:0]信号已经被Function Number和Register Number使用，因此PCI设备的IDSEL只能与AD[31:11]信号连接。
认真的读者一定可以发现在CONFIG_ADDRESS寄存器中Device Number字段一共有5位可以表示32个设备，而AD[31:11]只有21位，显然在这两者之间无法建立一一对应的映射关系。因此在一条PCI总线上如果有21个以上的PCI设备，那么总是有几个设备无法与AD[31:11]信号线连接，从而PCI总线无法访问这些设备。因为PCI总线在配置请求的地址周期中，只能使用第31~11这些AD信号，所以在一条总线上最多也只能挂接21个PCI设备。这21个设备可能是从0到20，也可能是从11到31排列。从而系统软件在遍历PCI总线时，还是需要从0到31遍历整条PCI总线。
在实际的应用中，一条PCI总线能够挂接21个设备已经足够了，实际上由于PCI总线的负载能力有限，即便总线频率为33MHz的情况下，在一条PCI总线中最多也只能挂接10个负载，一条PCI总线所能挂接的负载详见表1?1。AD信号线与PCI设备IDSEL线的连接关系如图2?14所示。