Replace O(n^2) bus iterators with new a host iterator (for bus 0) and a new pci bridge child bus iterator.
Signed-off-by: Kevin O'Connor kevin@koconnor.net --- src/pci.c | 2 + src/pci.h | 12 +++++++ src/pciinit.c | 94 +++++++++++++++++++++++---------------------------------- 3 files changed, 52 insertions(+), 56 deletions(-)
diff --git a/src/pci.c b/src/pci.c index 6031c9f..7697583 100644 --- a/src/pci.c +++ b/src/pci.c @@ -137,6 +137,8 @@ pci_probe_devices(void) MaxPCIBus = bus; } else { rootbus = parent->rootbus; + if (!parent->firstchild) + parent->firstchild = dev; }
// Populate pci_device info. diff --git a/src/pci.h b/src/pci.h index a2a5a4c..b19b2e9 100644 --- a/src/pci.h +++ b/src/pci.h @@ -44,6 +44,7 @@ struct pci_device { u8 rootbus; struct pci_device *next; struct pci_device *parent; + struct pci_device *firstchild;
// Configuration space device information u16 vendor, device; @@ -68,9 +69,20 @@ static inline u32 pci_classprog(struct pci_device *pci) { return (pci->class << 8) | pci->prog_if; }
+// Iterator for every PCI device in the system #define foreachpci(PCI) \ for (PCI=PCIDevices; PCI; PCI=PCI->next)
+// Iterator for every PCI device on the main host bus (bus 0) +#define foreachhostpci(PCI) \ + for (PCI=PCIDevices; PCI && pci_bdf_to_bus(PCI->bdf) == 0; PCI=PCI->next) + +// Iterator for every PCI device hanging off a PCI bridge +#define foreachchildpci(PCI, PARENT) \ + for (PCI=PARENT->firstchild \ + ; PCI && pci_bdf_to_bus(PCI->bdf) == pci_bdf_to_bus(PARENT->bdf) \ + ; PCI=PCI->next) + int pci_next(int bdf, int bus); #define foreachbdf(BDF, BUS) \ for (BDF=pci_next(pci_bus_devfn_to_bdf((BUS), 0)-1, (BUS)) \ diff --git a/src/pciinit.c b/src/pciinit.c index e384a68..b87825d 100644 --- a/src/pciinit.c +++ b/src/pciinit.c @@ -236,17 +236,16 @@ static void pci_bios_init_device(struct pci_device *pci) pci_init_device(pci_device_tbl, pci, NULL); }
-static void pci_bios_init_device_in_bus(int bus) +static void pci_bios_init_devices(void) { struct pci_device *pci; - foreachpci(pci) { - u8 pci_bus = pci_bdf_to_bus(pci->bdf); - if (pci_bus < bus) - continue; - if (pci_bus > bus) - break; + foreachhostpci(pci) { pci_bios_init_device(pci); } + + foreachpci(pci) { + pci_init_device(pci_isa_bridge_tbl, pci, NULL); + } }
@@ -369,10 +368,10 @@ static void pci_bios_bus_reserve(struct pci_bus *bus, int type, u32 size) bus->r[type].max = size; }
-static void pci_bios_check_device_in_bus(int bus); - -static void pci_bios_check_device(struct pci_bus *bus, struct pci_device *dev) +static void pci_bios_check_device(struct pci_device *dev) { + struct pci_bus *bus = &busses[pci_bdf_to_bus(dev->bdf)]; + if (dev->class == PCI_CLASS_BRIDGE_PCI) { if (dev->secondary_bus >= busses_count) { /* should never trigger */ @@ -380,8 +379,13 @@ static void pci_bios_check_device(struct pci_bus *bus, struct pci_device *dev) busses_count, dev->secondary_bus); return; } - struct pci_bus *s = busses + dev->secondary_bus; - pci_bios_check_device_in_bus(dev->secondary_bus); + dprintf(1, "PCI: check devices bus %d\n", dev->secondary_bus); + struct pci_device *pci; + foreachchildpci(pci, dev) { + pci_bios_check_device(pci); + } + + struct pci_bus *s = &busses[dev->secondary_bus]; int type; for (type = 0; type < PCI_REGION_TYPE_COUNT; type++) { u32 limit = (type == PCI_REGION_TYPE_IO) ? @@ -419,18 +423,6 @@ static void pci_bios_check_device(struct pci_bus *bus, struct pci_device *dev) } }
-static void pci_bios_check_device_in_bus(int bus) -{ - struct pci_device *pci; - - dprintf(1, "PCI: check devices bus %d\n", bus); - foreachpci(pci) { - if (pci_bdf_to_bus(pci->bdf) != bus) - continue; - pci_bios_check_device(&busses[bus], pci); - } -} - #define ROOT_BASE(top, sum, max) ALIGN_DOWN((top)-(sum),(max) ?: 1)
// Setup region bases (given the regions' size and alignment) @@ -496,17 +488,19 @@ static u32 pci_bios_bus_get_addr(struct pci_bus *bus, int type, u32 size) #define PCI_MEMORY_SHIFT 16 #define PCI_PREF_MEMORY_SHIFT 16
-static void pci_bios_map_device_in_bus(int bus); - -static void pci_bios_map_device(struct pci_bus *bus, struct pci_device *dev) +static void pci_bios_map_device(struct pci_device *dev) { + struct pci_bus *bus = &busses[pci_bdf_to_bus(dev->bdf)]; + u16 bdf = dev->bdf; + + dprintf(1, "PCI: map device bdf=%02x:%02x.%x\n" + , pci_bdf_to_bus(bdf), pci_bdf_to_dev(bdf), pci_bdf_to_fn(bdf)); + if (dev->class == PCI_CLASS_BRIDGE_PCI) { if (dev->secondary_bus >= busses_count) { return; } - struct pci_bus *s = busses + dev->secondary_bus; - u32 base, limit; - + struct pci_bus *s = &busses[dev->secondary_bus]; int type; for (type = 0; type < PCI_REGION_TYPE_COUNT; type++) { s->r[type].base = pci_bios_bus_get_addr(bus, type, s->r[type].size); @@ -514,9 +508,8 @@ static void pci_bios_map_device(struct pci_bus *bus, struct pci_device *dev) dprintf(1, "PCI: init bases bus %d (secondary)\n", dev->secondary_bus); pci_bios_init_bus_bases(s);
- base = s->r[PCI_REGION_TYPE_IO].base; - limit = base + s->r[PCI_REGION_TYPE_IO].size - 1; - u16 bdf = dev->bdf; + u32 base = s->r[PCI_REGION_TYPE_IO].base; + u32 limit = base + s->r[PCI_REGION_TYPE_IO].size - 1; pci_config_writeb(bdf, PCI_IO_BASE, base >> PCI_IO_SHIFT); pci_config_writew(bdf, PCI_IO_BASE_UPPER16, 0); pci_config_writeb(bdf, PCI_IO_LIMIT, limit >> PCI_IO_SHIFT); @@ -534,7 +527,10 @@ static void pci_bios_map_device(struct pci_bus *bus, struct pci_device *dev) pci_config_writel(bdf, PCI_PREF_BASE_UPPER32, 0); pci_config_writel(bdf, PCI_PREF_LIMIT_UPPER32, 0);
- pci_bios_map_device_in_bus(dev->secondary_bus); + struct pci_device *pci; + foreachchildpci(pci, dev) { + pci_bios_map_device(pci); + } return; }
@@ -558,20 +554,6 @@ static void pci_bios_map_device(struct pci_bus *bus, struct pci_device *dev) } }
-static void pci_bios_map_device_in_bus(int bus) -{ - struct pci_device *pci; - - foreachpci(pci) { - u16 bdf = pci->bdf; - if (pci_bdf_to_bus(bdf) != bus) - continue; - dprintf(1, "PCI: map device bdf=%02x:%02x.%x\n" - , pci_bdf_to_bus(bdf), pci_bdf_to_dev(bdf), pci_bdf_to_fn(bdf)); - pci_bios_map_device(&busses[bus], pci); - } -} -
/**************************************************************** * Main setup code @@ -603,7 +585,10 @@ pci_setup(void) dprintf(1, "=== PCI new allocation pass #1 ===\n"); busses = malloc_tmp(sizeof(*busses) * busses_count); memset(busses, 0, sizeof(*busses) * busses_count); - pci_bios_check_device_in_bus(0 /* host bus */); + struct pci_device *pci; + foreachhostpci(pci) { + pci_bios_check_device(pci); + } if (pci_bios_init_root_regions(start, end) != 0) { panic("PCI: out of address space\n"); } @@ -611,15 +596,12 @@ pci_setup(void) dprintf(1, "=== PCI new allocation pass #2 ===\n"); dprintf(1, "PCI: init bases bus 0 (primary)\n"); pci_bios_init_bus_bases(&busses[0]); - pci_bios_map_device_in_bus(0 /* host bus */); - - pci_bios_init_device_in_bus(0 /* host bus */); - - struct pci_device *pci; - foreachpci(pci) { - pci_init_device(pci_isa_bridge_tbl, pci, NULL); + foreachhostpci(pci) { + pci_bios_map_device(pci); }
+ pci_bios_init_devices(); + free(busses); busses_count = 0; }