为什么PCI桥的枚举用这样一种奇怪的顺序？

motalelf

初始状态：PCI桥的树中，BIOS已经初始化了部分PCI桥，分配了总线号；另一部分，BIOS未初始化，需kernel来分配总线号。

那么，我们需要做的，是两次深度优先遍历PCI桥的树。
第一次： 一旦遇到BIOS未初始化的PCI桥，既向上返回一层，目的是统计BIOS分配到的最大总线号；
第二次： 一旦遇到BIOS已初始化的PCI桥，既向下深入一层，目的是继续分配总线号；

既两次遍历，但每个节点只处理一次，要么在第一次中被统计，要么在第二次中被分配总线号。


但是kernel不是这么做的，它只是一次遍历PCI桥的树。
pci_do_scan_bus中的两次遍历只是个假象，因为pass是个局部变量，只有当子节点的两遍都完成后才向上返回父节点。

我画了一个图，对PCI桥的结构做了一些简化，希望更突出本质问题。

圆圈表示BIOS已初始化的PCI桥；
黑蛋表示BIOS未初始化，需要kernel来初始化的PCI桥；
数字表示递归的各层中pass的值，如“112”表示递归进行到了第三层。并且第一层中pass==1，第二层中pass==1，第三层中pass==2。

kernel遍历的过程是这样的：1(统计) -->11(统计) -->111(统计) --> 112(分配) -->12(分配) -->122(分配) --> 122(分配) --> 2(分配).................................

这棵树只被遍历了一次，而且112,12,122,122时，为PCI桥分配总线号都是错误的。因为在我画的图中，右子树全部是黑蛋，但是实际情况中，右子树完全可能都是圆圈，既还有BIOS已分配的总线号未统计上来。这样，在统计完右子树之前，就为左子树中的黑蛋分配了总线号。完全可能造成总线号重复的情况。

只有在2,22,222时，既递归的每层中，pass都等于2时，才能证明已经遍历了所有圆圈，统计出来黑蛋应该使用那些总线号。

[ 本帖最后由 motalelf 于 2007-10-25 17:20 编辑 ]

motalelf

抱歉，我的绘画造诣有待提高~~~~~