SAFE public projects git trees. - safe/jmp/linux-2.6/blob - drivers/pci/probe.c

   1 /*
   2  * probe.c - PCI detection and setup code
   3  */
   4
   5 #include <linux/kernel.h>
   6 #include <linux/delay.h>
   7 #include <linux/init.h>
   8 #include <linux/pci.h>
   9 #include <linux/slab.h>
  10 #include <linux/module.h>
  11 #include <linux/cpumask.h>
  12 #include "pci.h"
  13
  14 #define CARDBUS_LATENCY_TIMER   176     /* secondary latency timer */
  15 #define CARDBUS_RESERVE_BUSNR   3
  16 #define PCI_CFG_SPACE_SIZE      256
  17 #define PCI_CFG_SPACE_EXP_SIZE  4096
  18
  19 /* Ugh.  Need to stop exporting this to modules. */
  20 LIST_HEAD(pci_root_buses);
  21 EXPORT_SYMBOL(pci_root_buses);
  22
  23 LIST_HEAD(pci_devices);
  24
  25 /*
  26  * Some device drivers need know if pci is initiated.
  27  * Basically, we think pci is not initiated when there
  28  * is no device in list of pci_devices.
  29  */
  30 int no_pci_devices(void)
  31 {
  32         return list_empty(&pci_devices);
  33 }
  34
  35 EXPORT_SYMBOL(no_pci_devices);
  36
  37 #ifdef HAVE_PCI_LEGACY
  38 /**
  39  * pci_create_legacy_files - create legacy I/O port and memory files
  40  * @b: bus to create files under
  41  *
  42  * Some platforms allow access to legacy I/O port and ISA memory space on
  43  * a per-bus basis.  This routine creates the files and ties them into
  44  * their associated read, write and mmap files from pci-sysfs.c
  45  */
  46 static void pci_create_legacy_files(struct pci_bus *b)
  47 {
  48         b->legacy_io = kzalloc(sizeof(struct bin_attribute) * 2,
  49                                GFP_ATOMIC);
  50         if (b->legacy_io) {
  51                 b->legacy_io->attr.name = "legacy_io";
  52                 b->legacy_io->size = 0xffff;
  53                 b->legacy_io->attr.mode = S_IRUSR | S_IWUSR;
  54                 b->legacy_io->read = pci_read_legacy_io;
  55                 b->legacy_io->write = pci_write_legacy_io;
  56                 device_create_bin_file(&b->dev, b->legacy_io);
  57
  58                 /* Allocated above after the legacy_io struct */
  59                 b->legacy_mem = b->legacy_io + 1;
  60                 b->legacy_mem->attr.name = "legacy_mem";
  61                 b->legacy_mem->size = 1024*1024;
  62                 b->legacy_mem->attr.mode = S_IRUSR | S_IWUSR;
  63                 b->legacy_mem->mmap = pci_mmap_legacy_mem;
  64                 device_create_bin_file(&b->dev, b->legacy_mem);
  65         }
  66 }
  67
  68 void pci_remove_legacy_files(struct pci_bus *b)
  69 {
  70         if (b->legacy_io) {
  71                 device_remove_bin_file(&b->dev, b->legacy_io);
  72                 device_remove_bin_file(&b->dev, b->legacy_mem);
  73                 kfree(b->legacy_io); /* both are allocated here */
  74         }
  75 }
  76 #else /* !HAVE_PCI_LEGACY */
  77 static inline void pci_create_legacy_files(struct pci_bus *bus) { return; }
  78 void pci_remove_legacy_files(struct pci_bus *bus) { return; }
  79 #endif /* HAVE_PCI_LEGACY */
  80
  81 /*
  82  * PCI Bus Class Devices
  83  */
  84 static ssize_t pci_bus_show_cpuaffinity(struct device *dev,
  85                                         int type,
  86                                         struct device_attribute *attr,
  87                                         char *buf)
  88 {
  89         int ret;
  90         cpumask_t cpumask;
  91
  92         cpumask = pcibus_to_cpumask(to_pci_bus(dev));
  93         ret = type?
  94                 cpulist_scnprintf(buf, PAGE_SIZE-2, cpumask):
  95                 cpumask_scnprintf(buf, PAGE_SIZE-2, cpumask);
  96         buf[ret++] = '\n';
  97         buf[ret] = '\0';
  98         return ret;
  99 }
 100
 101 static ssize_t inline pci_bus_show_cpumaskaffinity(struct device *dev,
 102                                         struct device_attribute *attr,
 103                                         char *buf)
 104 {
 105         return pci_bus_show_cpuaffinity(dev, 0, attr, buf);
 106 }
 107
 108 static ssize_t inline pci_bus_show_cpulistaffinity(struct device *dev,
 109                                         struct device_attribute *attr,
 110                                         char *buf)
 111 {
 112         return pci_bus_show_cpuaffinity(dev, 1, attr, buf);
 113 }
 114
 115 DEVICE_ATTR(cpuaffinity,     S_IRUGO, pci_bus_show_cpumaskaffinity, NULL);
 116 DEVICE_ATTR(cpulistaffinity, S_IRUGO, pci_bus_show_cpulistaffinity, NULL);
 117
 118 /*
 119  * PCI Bus Class
 120  */
 121 static void release_pcibus_dev(struct device *dev)
 122 {
 123         struct pci_bus *pci_bus = to_pci_bus(dev);
 124
 125         if (pci_bus->bridge)
 126                 put_device(pci_bus->bridge);
 127         kfree(pci_bus);
 128 }
 129
 130 static struct class pcibus_class = {
 131         .name           = "pci_bus",
 132         .dev_release    = &release_pcibus_dev,
 133 };
 134
 135 static int __init pcibus_class_init(void)
 136 {
 137         return class_register(&pcibus_class);
 138 }
 139 postcore_initcall(pcibus_class_init);
 140
 141 /*
 142  * Translate the low bits of the PCI base
 143  * to the resource type
 144  */
 145 static inline unsigned int pci_calc_resource_flags(unsigned int flags)
 146 {
 147         if (flags & PCI_BASE_ADDRESS_SPACE_IO)
 148                 return IORESOURCE_IO;
 149
 150         if (flags & PCI_BASE_ADDRESS_MEM_PREFETCH)
 151                 return IORESOURCE_MEM | IORESOURCE_PREFETCH;
 152
 153         return IORESOURCE_MEM;
 154 }
 155
 156 /*
 157  * Find the extent of a PCI decode..
 158  */
 159 static u32 pci_size(u32 base, u32 maxbase, u32 mask)
 160 {
 161         u32 size = mask & maxbase;      /* Find the significant bits */
 162         if (!size)
 163                 return 0;
 164
 165         /* Get the lowest of them to find the decode size, and
 166            from that the extent.  */
 167         size = (size & ~(size-1)) - 1;
 168
 169         /* base == maxbase can be valid only if the BAR has
 170            already been programmed with all 1s.  */
 171         if (base == maxbase && ((base | size) & mask) != mask)
 172                 return 0;
 173
 174         return size;
 175 }
 176
 177 static u64 pci_size64(u64 base, u64 maxbase, u64 mask)
 178 {
 179         u64 size = mask & maxbase;      /* Find the significant bits */
 180         if (!size)
 181                 return 0;
 182
 183         /* Get the lowest of them to find the decode size, and
 184            from that the extent.  */
 185         size = (size & ~(size-1)) - 1;
 186
 187         /* base == maxbase can be valid only if the BAR has
 188            already been programmed with all 1s.  */
 189         if (base == maxbase && ((base | size) & mask) != mask)
 190                 return 0;
 191
 192         return size;
 193 }
 194
 195 static inline int is_64bit_memory(u32 mask)
 196 {
 197         if ((mask & (PCI_BASE_ADDRESS_SPACE|PCI_BASE_ADDRESS_MEM_TYPE_MASK)) ==
 198             (PCI_BASE_ADDRESS_SPACE_MEMORY|PCI_BASE_ADDRESS_MEM_TYPE_64))
 199                 return 1;
 200         return 0;
 201 }
 202
 203 static void pci_read_bases(struct pci_dev *dev, unsigned int howmany, int rom)
 204 {
 205         unsigned int pos, reg, next;
 206         u32 l, sz;
 207         struct resource *res;
 208
 209         for(pos=0; pos<howmany; pos = next) {
 210                 u64 l64;
 211                 u64 sz64;
 212                 u32 raw_sz;
 213
 214                 next = pos+1;
 215                 res = &dev->resource[pos];
 216                 res->name = pci_name(dev);
 217                 reg = PCI_BASE_ADDRESS_0 + (pos << 2);
 218                 pci_read_config_dword(dev, reg, &l);
 219                 pci_write_config_dword(dev, reg, ~0);
 220                 pci_read_config_dword(dev, reg, &sz);
 221                 pci_write_config_dword(dev, reg, l);
 222                 if (!sz || sz == 0xffffffff)
 223                         continue;
 224                 if (l == 0xffffffff)
 225                         l = 0;
 226                 raw_sz = sz;
 227                 if ((l & PCI_BASE_ADDRESS_SPACE) ==
 228                                 PCI_BASE_ADDRESS_SPACE_MEMORY) {
 229                         sz = pci_size(l, sz, (u32)PCI_BASE_ADDRESS_MEM_MASK);
 230                         /*
 231                          * For 64bit prefetchable memory sz could be 0, if the
 232                          * real size is bigger than 4G, so we need to check
 233                          * szhi for that.
 234                          */
 235                         if (!is_64bit_memory(l) && !sz)
 236                                 continue;
 237                         res->start = l & PCI_BASE_ADDRESS_MEM_MASK;
 238                         res->flags |= l & ~PCI_BASE_ADDRESS_MEM_MASK;
 239                 } else {
 240                         sz = pci_size(l, sz, PCI_BASE_ADDRESS_IO_MASK & 0xffff);
 241                         if (!sz)
 242                                 continue;
 243                         res->start = l & PCI_BASE_ADDRESS_IO_MASK;
 244                         res->flags |= l & ~PCI_BASE_ADDRESS_IO_MASK;
 245                 }
 246                 res->end = res->start + (unsigned long) sz;
 247                 res->flags |= pci_calc_resource_flags(l);
 248                 if (is_64bit_memory(l)) {
 249                         u32 szhi, lhi;
 250
 251                         pci_read_config_dword(dev, reg+4, &lhi);
 252                         pci_write_config_dword(dev, reg+4, ~0);
 253                         pci_read_config_dword(dev, reg+4, &szhi);
 254                         pci_write_config_dword(dev, reg+4, lhi);
 255                         sz64 = ((u64)szhi << 32) | raw_sz;
 256                         l64 = ((u64)lhi << 32) | l;
 257                         sz64 = pci_size64(l64, sz64, PCI_BASE_ADDRESS_MEM_MASK);
 258                         next++;
 259 #if BITS_PER_LONG == 64
 260                         if (!sz64) {
 261                                 res->start = 0;
 262                                 res->end = 0;
 263                                 res->flags = 0;
 264                                 continue;
 265                         }
 266                         res->start = l64 & PCI_BASE_ADDRESS_MEM_MASK;
 267                         res->end = res->start + sz64;
 268 #else
 269                         if (sz64 > 0x100000000ULL) {
 270                                 printk(KERN_ERR "PCI: Unable to handle 64-bit "
 271                                         "BAR for device %s\n", pci_name(dev));
 272                                 res->start = 0;
 273                                 res->flags = 0;
 274                         } else if (lhi) {
 275                                 /* 64-bit wide address, treat as disabled */
 276                                 pci_write_config_dword(dev, reg,
 277                                         l & ~(u32)PCI_BASE_ADDRESS_MEM_MASK);
 278                                 pci_write_config_dword(dev, reg+4, 0);
 279                                 res->start = 0;
 280                                 res->end = sz;
 281                         }
 282 #endif
 283                 }
 284         }
 285         if (rom) {
 286                 dev->rom_base_reg = rom;
 287                 res = &dev->resource[PCI_ROM_RESOURCE];
 288                 res->name = pci_name(dev);
 289                 pci_read_config_dword(dev, rom, &l);
 290                 pci_write_config_dword(dev, rom, ~PCI_ROM_ADDRESS_ENABLE);
 291                 pci_read_config_dword(dev, rom, &sz);
 292                 pci_write_config_dword(dev, rom, l);
 293                 if (l == 0xffffffff)
 294                         l = 0;
 295                 if (sz && sz != 0xffffffff) {
 296                         sz = pci_size(l, sz, (u32)PCI_ROM_ADDRESS_MASK);
 297                         if (sz) {
 298                                 res->flags = (l & IORESOURCE_ROM_ENABLE) |
 299                                   IORESOURCE_MEM | IORESOURCE_PREFETCH |
 300                                   IORESOURCE_READONLY | IORESOURCE_CACHEABLE;
 301                                 res->start = l & PCI_ROM_ADDRESS_MASK;
 302                                 res->end = res->start + (unsigned long) sz;
 303                         }
 304                 }
 305         }
 306 }
 307
 308 void __devinit pci_read_bridge_bases(struct pci_bus *child)
 309 {
 310         struct pci_dev *dev = child->self;
 311         u8 io_base_lo, io_limit_lo;
 312         u16 mem_base_lo, mem_limit_lo;
 313         unsigned long base, limit;
 314         struct resource *res;
 315         int i;
 316
 317         if (!dev)               /* It's a host bus, nothing to read */
 318                 return;
 319
 320         if (dev->transparent) {
 321                 printk(KERN_INFO "PCI: Transparent bridge - %s\n", pci_name(dev));
 322                 for(i = 3; i < PCI_BUS_NUM_RESOURCES; i++)
 323                         child->resource[i] = child->parent->resource[i - 3];
 324         }
 325
 326         for(i=0; i<3; i++)
 327                 child->resource[i] = &dev->resource[PCI_BRIDGE_RESOURCES+i];
 328
 329         res = child->resource[0];
 330         pci_read_config_byte(dev, PCI_IO_BASE, &io_base_lo);
 331         pci_read_config_byte(dev, PCI_IO_LIMIT, &io_limit_lo);
 332         base = (io_base_lo & PCI_IO_RANGE_MASK) << 8;
 333         limit = (io_limit_lo & PCI_IO_RANGE_MASK) << 8;
 334
 335         if ((io_base_lo & PCI_IO_RANGE_TYPE_MASK) == PCI_IO_RANGE_TYPE_32) {
 336                 u16 io_base_hi, io_limit_hi;
 337                 pci_read_config_word(dev, PCI_IO_BASE_UPPER16, &io_base_hi);
 338                 pci_read_config_word(dev, PCI_IO_LIMIT_UPPER16, &io_limit_hi);
 339                 base |= (io_base_hi << 16);
 340                 limit |= (io_limit_hi << 16);
 341         }
 342
 343         if (base <= limit) {
 344                 res->flags = (io_base_lo & PCI_IO_RANGE_TYPE_MASK) | IORESOURCE_IO;
 345                 if (!res->start)
 346                         res->start = base;
 347                 if (!res->end)
 348                         res->end = limit + 0xfff;
 349         }
 350
 351         res = child->resource[1];
 352         pci_read_config_word(dev, PCI_MEMORY_BASE, &mem_base_lo);
 353         pci_read_config_word(dev, PCI_MEMORY_LIMIT, &mem_limit_lo);
 354         base = (mem_base_lo & PCI_MEMORY_RANGE_MASK) << 16;
 355         limit = (mem_limit_lo & PCI_MEMORY_RANGE_MASK) << 16;
 356         if (base <= limit) {
 357                 res->flags = (mem_base_lo & PCI_MEMORY_RANGE_TYPE_MASK) | IORESOURCE_MEM;
 358                 res->start = base;
 359                 res->end = limit + 0xfffff;
 360         }
 361
 362         res = child->resource[2];
 363         pci_read_config_word(dev, PCI_PREF_MEMORY_BASE, &mem_base_lo);
 364         pci_read_config_word(dev, PCI_PREF_MEMORY_LIMIT, &mem_limit_lo);
 365         base = (mem_base_lo & PCI_PREF_RANGE_MASK) << 16;
 366         limit = (mem_limit_lo & PCI_PREF_RANGE_MASK) << 16;
 367
 368         if ((mem_base_lo & PCI_PREF_RANGE_TYPE_MASK) == PCI_PREF_RANGE_TYPE_64) {
 369                 u32 mem_base_hi, mem_limit_hi;
 370                 pci_read_config_dword(dev, PCI_PREF_BASE_UPPER32, &mem_base_hi);
 371                 pci_read_config_dword(dev, PCI_PREF_LIMIT_UPPER32, &mem_limit_hi);
 372
 373                 /*
 374                  * Some bridges set the base > limit by default, and some
 375                  * (broken) BIOSes do not initialize them.  If we find
 376                  * this, just assume they are not being used.
 377                  */
 378                 if (mem_base_hi <= mem_limit_hi) {
 379 #if BITS_PER_LONG == 64
 380                         base |= ((long) mem_base_hi) << 32;
 381                         limit |= ((long) mem_limit_hi) << 32;
 382 #else
 383                         if (mem_base_hi || mem_limit_hi) {
 384                                 printk(KERN_ERR "PCI: Unable to handle 64-bit address space for bridge %s\n", pci_name(dev));
 385                                 return;
 386                         }
 387 #endif
 388                 }
 389         }
 390         if (base <= limit) {
 391                 res->flags = (mem_base_lo & PCI_MEMORY_RANGE_TYPE_MASK) | IORESOURCE_MEM | IORESOURCE_PREFETCH;
 392                 res->start = base;
 393                 res->end = limit + 0xfffff;
 394         }
 395 }
 396
 397 static struct pci_bus * pci_alloc_bus(void)
 398 {
 399         struct pci_bus *b;
 400
 401         b = kzalloc(sizeof(*b), GFP_KERNEL);
 402         if (b) {
 403                 INIT_LIST_HEAD(&b->node);
 404                 INIT_LIST_HEAD(&b->children);
 405                 INIT_LIST_HEAD(&b->devices);
 406         }
 407         return b;
 408 }
 409
 410 static struct pci_bus * __devinit
 411 pci_alloc_child_bus(struct pci_bus *parent, struct pci_dev *bridge, int busnr)
 412 {
 413         struct pci_bus *child;
 414         int i;
 415
 416         /*
 417          * Allocate a new bus, and inherit stuff from the parent..
 418          */
 419         child = pci_alloc_bus();
 420         if (!child)
 421                 return NULL;
 422
 423         child->self = bridge;
 424         child->parent = parent;
 425         child->ops = parent->ops;
 426         child->sysdata = parent->sysdata;
 427         child->bus_flags = parent->bus_flags;
 428         child->bridge = get_device(&bridge->dev);
 429
 430         /* initialize some portions of the bus device, but don't register it
 431          * now as the parent is not properly set up yet.  This device will get
 432          * registered later in pci_bus_add_devices()
 433          */
 434         child->dev.class = &pcibus_class;
 435         sprintf(child->dev.bus_id, "%04x:%02x", pci_domain_nr(child), busnr);
 436
 437         /*
 438          * Set up the primary, secondary and subordinate
 439          * bus numbers.
 440          */
 441         child->number = child->secondary = busnr;
 442         child->primary = parent->secondary;
 443         child->subordinate = 0xff;
 444
 445         /* Set up default resource pointers and names.. */
 446         for (i = 0; i < 4; i++) {
 447                 child->resource[i] = &bridge->resource[PCI_BRIDGE_RESOURCES+i];
 448                 child->resource[i]->name = child->name;
 449         }
 450         bridge->subordinate = child;
 451
 452         return child;
 453 }
 454
 455 struct pci_bus *__ref pci_add_new_bus(struct pci_bus *parent, struct pci_dev *dev, int busnr)
 456 {
 457         struct pci_bus *child;
 458
 459         child = pci_alloc_child_bus(parent, dev, busnr);
 460         if (child) {
 461                 down_write(&pci_bus_sem);
 462                 list_add_tail(&child->node, &parent->children);
 463                 up_write(&pci_bus_sem);
 464         }
 465         return child;
 466 }
 467
 468 static void pci_fixup_parent_subordinate_busnr(struct pci_bus *child, int max)
 469 {
 470         struct pci_bus *parent = child->parent;
 471
 472         /* Attempts to fix that up are really dangerous unless
 473            we're going to re-assign all bus numbers. */
 474         if (!pcibios_assign_all_busses())
 475                 return;
 476
 477         while (parent->parent && parent->subordinate < max) {
 478                 parent->subordinate = max;
 479                 pci_write_config_byte(parent->self, PCI_SUBORDINATE_BUS, max);
 480                 parent = parent->parent;
 481         }
 482 }
 483
 484 /*
 485  * If it's a bridge, configure it and scan the bus behind it.
 486  * For CardBus bridges, we don't scan behind as the devices will
 487  * be handled by the bridge driver itself.
 488  *
 489  * We need to process bridges in two passes -- first we scan those
 490  * already configured by the BIOS and after we are done with all of
 491  * them, we proceed to assigning numbers to the remaining buses in
 492  * order to avoid overlaps between old and new bus numbers.
 493  */
 494 int __devinit pci_scan_bridge(struct pci_bus *bus, struct pci_dev *dev, int max, int pass)
 495 {
 496         struct pci_bus *child;
 497         int is_cardbus = (dev->hdr_type == PCI_HEADER_TYPE_CARDBUS);
 498         u32 buses, i, j = 0;
 499         u16 bctl;
 500
 501         pci_read_config_dword(dev, PCI_PRIMARY_BUS, &buses);
 502
 503         pr_debug("PCI: Scanning behind PCI bridge %s, config %06x, pass %d\n",
 504                  pci_name(dev), buses & 0xffffff, pass);
 505
 506         /* Disable MasterAbortMode during probing to avoid reporting
 507            of bus errors (in some architectures) */
 508         pci_read_config_word(dev, PCI_BRIDGE_CONTROL, &bctl);
 509         pci_write_config_word(dev, PCI_BRIDGE_CONTROL,
 510                               bctl & ~PCI_BRIDGE_CTL_MASTER_ABORT);
 511
 512         if ((buses & 0xffff00) && !pcibios_assign_all_busses() && !is_cardbus) {
 513                 unsigned int cmax, busnr;
 514                 /*
 515                  * Bus already configured by firmware, process it in the first
 516                  * pass and just note the configuration.
 517                  */
 518                 if (pass)
 519                         goto out;
 520                 busnr = (buses >> 8) & 0xFF;
 521
 522                 /*
 523                  * If we already got to this bus through a different bridge,
 524                  * ignore it.  This can happen with the i450NX chipset.
 525                  */
 526                 if (pci_find_bus(pci_domain_nr(bus), busnr)) {
 527                         printk(KERN_INFO "PCI: Bus %04x:%02x already known\n",
 528                                         pci_domain_nr(bus), busnr);
 529                         goto out;
 530                 }
 531
 532                 child = pci_add_new_bus(bus, dev, busnr);
 533                 if (!child)
 534                         goto out;
 535                 child->primary = buses & 0xFF;
 536                 child->subordinate = (buses >> 16) & 0xFF;
 537                 child->bridge_ctl = bctl;
 538
 539                 cmax = pci_scan_child_bus(child);
 540                 if (cmax > max)
 541                         max = cmax;
 542                 if (child->subordinate > max)
 543                         max = child->subordinate;
 544         } else {
 545                 /*
 546                  * We need to assign a number to this bus which we always
 547                  * do in the second pass.
 548                  */
 549                 if (!pass) {
 550                         if (pcibios_assign_all_busses())
 551                                 /* Temporarily disable forwarding of the
 552                                    configuration cycles on all bridges in
 553                                    this bus segment to avoid possible
 554                                    conflicts in the second pass between two
 555                                    bridges programmed with overlapping
 556                                    bus ranges. */
 557                                 pci_write_config_dword(dev, PCI_PRIMARY_BUS,
 558                                                        buses & ~0xffffff);
 559                         goto out;
 560                 }
 561
 562                 /* Clear errors */
 563                 pci_write_config_word(dev, PCI_STATUS, 0xffff);
 564
 565                 /* Prevent assigning a bus number that already exists.
 566                  * This can happen when a bridge is hot-plugged */
 567                 if (pci_find_bus(pci_domain_nr(bus), max+1))
 568                         goto out;
 569                 child = pci_add_new_bus(bus, dev, ++max);
 570                 buses = (buses & 0xff000000)
 571                       | ((unsigned int)(child->primary)     <<  0)
 572                       | ((unsigned int)(child->secondary)   <<  8)
 573                       | ((unsigned int)(child->subordinate) << 16);
 574
 575                 /*
 576                  * yenta.c forces a secondary latency timer of 176.
 577                  * Copy that behaviour here.
 578                  */
 579                 if (is_cardbus) {
 580                         buses &= ~0xff000000;
 581                         buses |= CARDBUS_LATENCY_TIMER << 24;
 582                 }
 583
 584                 /*
 585                  * We need to blast all three values with a single write.
 586                  */
 587                 pci_write_config_dword(dev, PCI_PRIMARY_BUS, buses);
 588
 589                 if (!is_cardbus) {
 590                         child->bridge_ctl = bctl;
 591                         /*
 592                          * Adjust subordinate busnr in parent buses.
 593                          * We do this before scanning for children because
 594                          * some devices may not be detected if the bios
 595                          * was lazy.
 596                          */
 597                         pci_fixup_parent_subordinate_busnr(child, max);
 598                         /* Now we can scan all subordinate buses... */
 599                         max = pci_scan_child_bus(child);
 600                         /*
 601                          * now fix it up again since we have found
 602                          * the real value of max.
 603                          */
 604                         pci_fixup_parent_subordinate_busnr(child, max);
 605                 } else {
 606                         /*
 607                          * For CardBus bridges, we leave 4 bus numbers
 608                          * as cards with a PCI-to-PCI bridge can be
 609                          * inserted later.
 610                          */
 611                         for (i=0; i<CARDBUS_RESERVE_BUSNR; i++) {
 612                                 struct pci_bus *parent = bus;
 613                                 if (pci_find_bus(pci_domain_nr(bus),
 614                                                         max+i+1))
 615                                         break;
 616                                 while (parent->parent) {
 617                                         if ((!pcibios_assign_all_busses()) &&
 618                                             (parent->subordinate > max) &&
 619                                             (parent->subordinate <= max+i)) {
 620                                                 j = 1;
 621                                         }
 622                                         parent = parent->parent;
 623                                 }
 624                                 if (j) {
 625                                         /*
 626                                          * Often, there are two cardbus bridges
 627                                          * -- try to leave one valid bus number
 628                                          * for each one.
 629                                          */
 630                                         i /= 2;
 631                                         break;
 632                                 }
 633                         }
 634                         max += i;
 635                         pci_fixup_parent_subordinate_busnr(child, max);
 636                 }
 637                 /*
 638                  * Set the subordinate bus number to its real value.
 639                  */
 640                 child->subordinate = max;
 641                 pci_write_config_byte(dev, PCI_SUBORDINATE_BUS, max);
 642         }
 643
 644         sprintf(child->name, (is_cardbus ? "PCI CardBus #%02x" : "PCI Bus #%02x"), child->number);
 645
 646         /* Has only triggered on CardBus, fixup is in yenta_socket */
 647         while (bus->parent) {
 648                 if ((child->subordinate > bus->subordinate) ||
 649                     (child->number > bus->subordinate) ||
 650                     (child->number < bus->number) ||
 651                     (child->subordinate < bus->number)) {
 652                         pr_debug("PCI: Bus #%02x (-#%02x) is %s "
 653                                 "hidden behind%s bridge #%02x (-#%02x)\n",
 654                                 child->number, child->subordinate,
 655                                 (bus->number > child->subordinate &&
 656                                  bus->subordinate < child->number) ?
 657                                         "wholly" : "partially",
 658                                 bus->self->transparent ? " transparent" : "",
 659                                 bus->number, bus->subordinate);
 660                 }
 661                 bus = bus->parent;
 662         }
 663
 664 out:
 665         pci_write_config_word(dev, PCI_BRIDGE_CONTROL, bctl);
 666
 667         return max;
 668 }
 669
 670 /*
 671  * Read interrupt line and base address registers.
 672  * The architecture-dependent code can tweak these, of course.
 673  */
 674 static void pci_read_irq(struct pci_dev *dev)
 675 {
 676         unsigned char irq;
 677
 678         pci_read_config_byte(dev, PCI_INTERRUPT_PIN, &irq);
 679         dev->pin = irq;
 680         if (irq)
 681                 pci_read_config_byte(dev, PCI_INTERRUPT_LINE, &irq);
 682         dev->irq = irq;
 683 }
 684
 685 #define LEGACY_IO_RESOURCE      (IORESOURCE_IO | IORESOURCE_PCI_FIXED)
 686
 687 /**
 688  * pci_setup_device - fill in class and map information of a device
 689  * @dev: the device structure to fill
 690  *
 691  * Initialize the device structure with information about the device's
 692  * vendor,class,memory and IO-space addresses,IRQ lines etc.
 693  * Called at initialisation of the PCI subsystem and by CardBus services.
 694  * Returns 0 on success and -1 if unknown type of device (not normal, bridge
 695  * or CardBus).
 696  */
 697 static int pci_setup_device(struct pci_dev * dev)
 698 {
 699         u32 class;
 700
 701         sprintf(pci_name(dev), "%04x:%02x:%02x.%d", pci_domain_nr(dev->bus),
 702                 dev->bus->number, PCI_SLOT(dev->devfn), PCI_FUNC(dev->devfn));
 703
 704         pci_read_config_dword(dev, PCI_CLASS_REVISION, &class);
 705         dev->revision = class & 0xff;
 706         class >>= 8;                                /* upper 3 bytes */
 707         dev->class = class;
 708         class >>= 8;
 709
 710         pr_debug("PCI: Found %s [%04x/%04x] %06x %02x\n", pci_name(dev),
 711                  dev->vendor, dev->device, class, dev->hdr_type);
 712
 713         /* "Unknown power state" */
 714         dev->current_state = PCI_UNKNOWN;
 715
 716         /* Early fixups, before probing the BARs */
 717         pci_fixup_device(pci_fixup_early, dev);
 718         class = dev->class >> 8;
 719
 720         switch (dev->hdr_type) {                    /* header type */
 721         case PCI_HEADER_TYPE_NORMAL:                /* standard header */
 722                 if (class == PCI_CLASS_BRIDGE_PCI)
 723                         goto bad;
 724                 pci_read_irq(dev);
 725                 pci_read_bases(dev, 6, PCI_ROM_ADDRESS);
 726                 pci_read_config_word(dev, PCI_SUBSYSTEM_VENDOR_ID, &dev->subsystem_vendor);
 727                 pci_read_config_word(dev, PCI_SUBSYSTEM_ID, &dev->subsystem_device);
 728
 729                 /*
 730                  *      Do the ugly legacy mode stuff here rather than broken chip
 731                  *      quirk code. Legacy mode ATA controllers have fixed
 732                  *      addresses. These are not always echoed in BAR0-3, and
 733                  *      BAR0-3 in a few cases contain junk!
 734                  */
 735                 if (class == PCI_CLASS_STORAGE_IDE) {
 736                         u8 progif;
 737                         pci_read_config_byte(dev, PCI_CLASS_PROG, &progif);
 738                         if ((progif & 1) == 0) {
 739                                 dev->resource[0].start = 0x1F0;
 740                                 dev->resource[0].end = 0x1F7;
 741                                 dev->resource[0].flags = LEGACY_IO_RESOURCE;
 742                                 dev->resource[1].start = 0x3F6;
 743                                 dev->resource[1].end = 0x3F6;
 744                                 dev->resource[1].flags = LEGACY_IO_RESOURCE;
 745                         }
 746                         if ((progif & 4) == 0) {
 747                                 dev->resource[2].start = 0x170;
 748                                 dev->resource[2].end = 0x177;
 749                                 dev->resource[2].flags = LEGACY_IO_RESOURCE;
 750                                 dev->resource[3].start = 0x376;
 751                                 dev->resource[3].end = 0x376;
 752                                 dev->resource[3].flags = LEGACY_IO_RESOURCE;
 753                         }
 754                 }
 755                 break;
 756
 757         case PCI_HEADER_TYPE_BRIDGE:                /* bridge header */
 758                 if (class != PCI_CLASS_BRIDGE_PCI)
 759                         goto bad;
 760                 /* The PCI-to-PCI bridge spec requires that subtractive
 761                    decoding (i.e. transparent) bridge must have programming
 762                    interface code of 0x01. */
 763                 pci_read_irq(dev);
 764                 dev->transparent = ((dev->class & 0xff) == 1);
 765                 pci_read_bases(dev, 2, PCI_ROM_ADDRESS1);
 766                 break;
 767
 768         case PCI_HEADER_TYPE_CARDBUS:               /* CardBus bridge header */
 769                 if (class != PCI_CLASS_BRIDGE_CARDBUS)
 770                         goto bad;
 771                 pci_read_irq(dev);
 772                 pci_read_bases(dev, 1, 0);
 773                 pci_read_config_word(dev, PCI_CB_SUBSYSTEM_VENDOR_ID, &dev->subsystem_vendor);
 774                 pci_read_config_word(dev, PCI_CB_SUBSYSTEM_ID, &dev->subsystem_device);
 775                 break;
 776
 777         default:                                    /* unknown header */
 778                 printk(KERN_ERR "PCI: device %s has unknown header type %02x, ignoring.\n",
 779                         pci_name(dev), dev->hdr_type);
 780                 return -1;
 781
 782         bad:
 783                 printk(KERN_ERR "PCI: %s: class %x doesn't match header type %02x. Ignoring class.\n",
 784                        pci_name(dev), class, dev->hdr_type);
 785                 dev->class = PCI_CLASS_NOT_DEFINED;
 786         }
 787
 788         /* We found a fine healthy device, go go go... */
 789         return 0;
 790 }
 791
 792 /**
 793  * pci_release_dev - free a pci device structure when all users of it are finished.
 794  * @dev: device that's been disconnected
 795  *
 796  * Will be called only by the device core when all users of this pci device are
 797  * done.
 798  */
 799 static void pci_release_dev(struct device *dev)
 800 {
 801         struct pci_dev *pci_dev;
 802
 803         pci_dev = to_pci_dev(dev);
 804         kfree(pci_dev);
 805 }
 806
 807 static void set_pcie_port_type(struct pci_dev *pdev)
 808 {
 809         int pos;
 810         u16 reg16;
 811
 812         pos = pci_find_capability(pdev, PCI_CAP_ID_EXP);
 813         if (!pos)
 814                 return;
 815         pdev->is_pcie = 1;
 816         pci_read_config_word(pdev, pos + PCI_EXP_FLAGS, &reg16);
 817         pdev->pcie_type = (reg16 & PCI_EXP_FLAGS_TYPE) >> 4;
 818 }
 819
 820 /**
 821  * pci_cfg_space_size - get the configuration space size of the PCI device.
 822  * @dev: PCI device
 823  *
 824  * Regular PCI devices have 256 bytes, but PCI-X 2 and PCI Express devices
 825  * have 4096 bytes.  Even if the device is capable, that doesn't mean we can
 826  * access it.  Maybe we don't have a way to generate extended config space
 827  * accesses, or the device is behind a reverse Express bridge.  So we try
 828  * reading the dword at 0x100 which must either be 0 or a valid extended
 829  * capability header.
 830  */
 831 int pci_cfg_space_size(struct pci_dev *dev)
 832 {
 833         int pos;
 834         u32 status;
 835
 836         pos = pci_find_capability(dev, PCI_CAP_ID_EXP);
 837         if (!pos) {
 838                 pos = pci_find_capability(dev, PCI_CAP_ID_PCIX);
 839                 if (!pos)
 840                         goto fail;
 841
 842                 pci_read_config_dword(dev, pos + PCI_X_STATUS, &status);
 843                 if (!(status & (PCI_X_STATUS_266MHZ | PCI_X_STATUS_533MHZ)))
 844                         goto fail;
 845         }
 846
 847         if (pci_read_config_dword(dev, 256, &status) != PCIBIOS_SUCCESSFUL)
 848                 goto fail;
 849         if (status == 0xffffffff)
 850                 goto fail;
 851
 852         return PCI_CFG_SPACE_EXP_SIZE;
 853
 854  fail:
 855         return PCI_CFG_SPACE_SIZE;
 856 }
 857
 858 static void pci_release_bus_bridge_dev(struct device *dev)
 859 {
 860         kfree(dev);
 861 }
 862
 863 struct pci_dev *alloc_pci_dev(void)
 864 {
 865         struct pci_dev *dev;
 866
 867         dev = kzalloc(sizeof(struct pci_dev), GFP_KERNEL);
 868         if (!dev)
 869                 return NULL;
 870
 871         INIT_LIST_HEAD(&dev->global_list);
 872         INIT_LIST_HEAD(&dev->bus_list);
 873
 874         pci_msi_init_pci_dev(dev);
 875
 876         return dev;
 877 }
 878 EXPORT_SYMBOL(alloc_pci_dev);
 879
 880 /*
 881  * Read the config data for a PCI device, sanity-check it
 882  * and fill in the dev structure...
 883  */
 884 static struct pci_dev * __devinit
 885 pci_scan_device(struct pci_bus *bus, int devfn)
 886 {
 887         struct pci_dev *dev;
 888         u32 l;
 889         u8 hdr_type;
 890         int delay = 1;
 891
 892         if (pci_bus_read_config_dword(bus, devfn, PCI_VENDOR_ID, &l))
 893                 return NULL;
 894
 895         /* some broken boards return 0 or ~0 if a slot is empty: */
 896         if (l == 0xffffffff || l == 0x00000000 ||
 897             l == 0x0000ffff || l == 0xffff0000)
 898                 return NULL;
 899
 900         /* Configuration request Retry Status */
 901         while (l == 0xffff0001) {
 902                 msleep(delay);
 903                 delay *= 2;
 904                 if (pci_bus_read_config_dword(bus, devfn, PCI_VENDOR_ID, &l))
 905                         return NULL;
 906                 /* Card hasn't responded in 60 seconds?  Must be stuck. */
 907                 if (delay > 60 * 1000) {
 908                         printk(KERN_WARNING "Device %04x:%02x:%02x.%d not "
 909                                         "responding\n", pci_domain_nr(bus),
 910                                         bus->number, PCI_SLOT(devfn),
 911                                         PCI_FUNC(devfn));
 912                         return NULL;
 913                 }
 914         }
 915
 916         if (pci_bus_read_config_byte(bus, devfn, PCI_HEADER_TYPE, &hdr_type))
 917                 return NULL;
 918
 919         dev = alloc_pci_dev();
 920         if (!dev)
 921                 return NULL;
 922
 923         dev->bus = bus;
 924         dev->sysdata = bus->sysdata;
 925         dev->dev.parent = bus->bridge;
 926         dev->dev.bus = &pci_bus_type;
 927         dev->devfn = devfn;
 928         dev->hdr_type = hdr_type & 0x7f;
 929         dev->multifunction = !!(hdr_type & 0x80);
 930         dev->vendor = l & 0xffff;
 931         dev->device = (l >> 16) & 0xffff;
 932         dev->cfg_size = pci_cfg_space_size(dev);
 933         dev->error_state = pci_channel_io_normal;
 934         set_pcie_port_type(dev);
 935
 936         /* Assume 32-bit PCI; let 64-bit PCI cards (which are far rarer)
 937            set this higher, assuming the system even supports it.  */
 938         dev->dma_mask = 0xffffffff;
 939         if (pci_setup_device(dev) < 0) {
 940                 kfree(dev);
 941                 return NULL;
 942         }
 943
 944         return dev;
 945 }
 946
 947 void pci_device_add(struct pci_dev *dev, struct pci_bus *bus)
 948 {
 949         device_initialize(&dev->dev);
 950         dev->dev.release = pci_release_dev;
 951         pci_dev_get(dev);
 952
 953         set_dev_node(&dev->dev, pcibus_to_node(bus));
 954         dev->dev.dma_mask = &dev->dma_mask;
 955         dev->dev.dma_parms = &dev->dma_parms;
 956         dev->dev.coherent_dma_mask = 0xffffffffull;
 957
 958         pci_set_dma_max_seg_size(dev, 65536);
 959         pci_set_dma_seg_boundary(dev, 0xffffffff);
 960
 961         /* Fix up broken headers */
 962         pci_fixup_device(pci_fixup_header, dev);
 963
 964         /*
 965          * Add the device to our list of discovered devices
 966          * and the bus list for fixup functions, etc.
 967          */
 968         INIT_LIST_HEAD(&dev->global_list);
 969         down_write(&pci_bus_sem);
 970         list_add_tail(&dev->bus_list, &bus->devices);
 971         up_write(&pci_bus_sem);
 972 }
 973
 974 struct pci_dev *__ref pci_scan_single_device(struct pci_bus *bus, int devfn)
 975 {
 976         struct pci_dev *dev;
 977
 978         dev = pci_scan_device(bus, devfn);
 979         if (!dev)
 980                 return NULL;
 981
 982         pci_device_add(dev, bus);
 983
 984         return dev;
 985 }
 986 EXPORT_SYMBOL(pci_scan_single_device);
 987
 988 /**
 989  * pci_scan_slot - scan a PCI slot on a bus for devices.
 990  * @bus: PCI bus to scan
 991  * @devfn: slot number to scan (must have zero function.)
 992  *
 993  * Scan a PCI slot on the specified PCI bus for devices, adding
 994  * discovered devices to the @bus->devices list.  New devices
 995  * will have an empty dev->global_list head.
 996  */
 997 int pci_scan_slot(struct pci_bus *bus, int devfn)
 998 {
 999         int func, nr = 0;
1000         int scan_all_fns;
1001
1002         scan_all_fns = pcibios_scan_all_fns(bus, devfn);
1003
1004         for (func = 0; func < 8; func++, devfn++) {
1005                 struct pci_dev *dev;
1006
1007                 dev = pci_scan_single_device(bus, devfn);
1008                 if (dev) {
1009                         nr++;
1010
1011                         /*
1012                          * If this is a single function device,
1013                          * don't scan past the first function.
1014                          */
1015                         if (!dev->multifunction) {
1016                                 if (func > 0) {
1017                                         dev->multifunction = 1;
1018                                 } else {
1019                                         break;
1020                                 }
1021                         }
1022                 } else {
1023                         if (func == 0 && !scan_all_fns)
1024                                 break;
1025                 }
1026         }
1027         return nr;
1028 }
1029
1030 unsigned int __devinit pci_scan_child_bus(struct pci_bus *bus)
1031 {
1032         unsigned int devfn, pass, max = bus->secondary;
1033         struct pci_dev *dev;
1034
1035         pr_debug("PCI: Scanning bus %04x:%02x\n", pci_domain_nr(bus), bus->number);
1036
1037         /* Go find them, Rover! */
1038         for (devfn = 0; devfn < 0x100; devfn += 8)
1039                 pci_scan_slot(bus, devfn);
1040
1041         /*
1042          * After performing arch-dependent fixup of the bus, look behind
1043          * all PCI-to-PCI bridges on this bus.
1044          */
1045         pr_debug("PCI: Fixups for bus %04x:%02x\n", pci_domain_nr(bus), bus->number);
1046         pcibios_fixup_bus(bus);
1047         for (pass=0; pass < 2; pass++)
1048                 list_for_each_entry(dev, &bus->devices, bus_list) {
1049                         if (dev->hdr_type == PCI_HEADER_TYPE_BRIDGE ||
1050                             dev->hdr_type == PCI_HEADER_TYPE_CARDBUS)
1051                                 max = pci_scan_bridge(bus, dev, max, pass);
1052                 }
1053
1054         /*
1055          * We've scanned the bus and so we know all about what's on
1056          * the other side of any bridges that may be on this bus plus
1057          * any devices.
1058          *
1059          * Return how far we've got finding sub-buses.
1060          */
1061         pr_debug("PCI: Bus scan for %04x:%02x returning with max=%02x\n",
1062                 pci_domain_nr(bus), bus->number, max);
1063         return max;
1064 }
1065
1066 struct pci_bus * pci_create_bus(struct device *parent,
1067                 int bus, struct pci_ops *ops, void *sysdata)
1068 {
1069         int error;
1070         struct pci_bus *b;
1071         struct device *dev;
1072
1073         b = pci_alloc_bus();
1074         if (!b)
1075                 return NULL;
1076
1077         dev = kmalloc(sizeof(*dev), GFP_KERNEL);
1078         if (!dev){
1079                 kfree(b);
1080                 return NULL;
1081         }
1082
1083         b->sysdata = sysdata;
1084         b->ops = ops;
1085
1086         if (pci_find_bus(pci_domain_nr(b), bus)) {
1087                 /* If we already got to this bus through a different bridge, ignore it */
1088                 pr_debug("PCI: Bus %04x:%02x already known\n", pci_domain_nr(b), bus);
1089                 goto err_out;
1090         }
1091
1092         down_write(&pci_bus_sem);
1093         list_add_tail(&b->node, &pci_root_buses);
1094         up_write(&pci_bus_sem);
1095
1096         memset(dev, 0, sizeof(*dev));
1097         dev->parent = parent;
1098         dev->release = pci_release_bus_bridge_dev;
1099         sprintf(dev->bus_id, "pci%04x:%02x", pci_domain_nr(b), bus);
1100         error = device_register(dev);
1101         if (error)
1102                 goto dev_reg_err;
1103         b->bridge = get_device(dev);
1104
1105         b->dev.class = &pcibus_class;
1106         b->dev.parent = b->bridge;
1107         sprintf(b->dev.bus_id, "%04x:%02x", pci_domain_nr(b), bus);
1108         error = device_register(&b->dev);
1109         if (error)
1110                 goto class_dev_reg_err;
1111         error = device_create_file(&b->dev, &dev_attr_cpuaffinity);
1112         if (error)
1113                 goto dev_create_file_err;
1114
1115         /* Create legacy_io and legacy_mem files for this bus */
1116         pci_create_legacy_files(b);
1117
1118         b->number = b->secondary = bus;
1119         b->resource[0] = &ioport_resource;
1120         b->resource[1] = &iomem_resource;
1121
1122         return b;
1123
1124 dev_create_file_err:
1125         device_unregister(&b->dev);
1126 class_dev_reg_err:
1127         device_unregister(dev);
1128 dev_reg_err:
1129         down_write(&pci_bus_sem);
1130         list_del(&b->node);
1131         up_write(&pci_bus_sem);
1132 err_out:
1133         kfree(dev);
1134         kfree(b);
1135         return NULL;
1136 }
1137
1138 struct pci_bus * __devinit pci_scan_bus_parented(struct device *parent,
1139                 int bus, struct pci_ops *ops, void *sysdata)
1140 {
1141         struct pci_bus *b;
1142
1143         b = pci_create_bus(parent, bus, ops, sysdata);
1144         if (b)
1145                 b->subordinate = pci_scan_child_bus(b);
1146         return b;
1147 }
1148 EXPORT_SYMBOL(pci_scan_bus_parented);
1149
1150 #ifdef CONFIG_HOTPLUG
1151 EXPORT_SYMBOL(pci_add_new_bus);
1152 EXPORT_SYMBOL(pci_scan_slot);
1153 EXPORT_SYMBOL(pci_scan_bridge);
1154 EXPORT_SYMBOL_GPL(pci_scan_child_bus);
1155 #endif
1156
1157 static int __init pci_sort_bf_cmp(const struct pci_dev *a, const struct pci_dev *b)
1158 {
1159         if      (pci_domain_nr(a->bus) < pci_domain_nr(b->bus)) return -1;
1160         else if (pci_domain_nr(a->bus) > pci_domain_nr(b->bus)) return  1;
1161
1162         if      (a->bus->number < b->bus->number) return -1;
1163         else if (a->bus->number > b->bus->number) return  1;
1164
1165         if      (a->devfn < b->devfn) return -1;
1166         else if (a->devfn > b->devfn) return  1;
1167
1168         return 0;
1169 }
1170
1171 /*
1172  * Yes, this forcably breaks the klist abstraction temporarily.  It
1173  * just wants to sort the klist, not change reference counts and
1174  * take/drop locks rapidly in the process.  It does all this while
1175  * holding the lock for the list, so objects can't otherwise be
1176  * added/removed while we're swizzling.
1177  */
1178 static void __init pci_insertion_sort_klist(struct pci_dev *a, struct list_head *list)
1179 {
1180         struct list_head *pos;
1181         struct klist_node *n;
1182         struct device *dev;
1183         struct pci_dev *b;
1184
1185         list_for_each(pos, list) {
1186                 n = container_of(pos, struct klist_node, n_node);
1187                 dev = container_of(n, struct device, knode_bus);
1188                 b = to_pci_dev(dev);
1189                 if (pci_sort_bf_cmp(a, b) <= 0) {
1190                         list_move_tail(&a->dev.knode_bus.n_node, &b->dev.knode_bus.n_node);
1191                         return;
1192                 }
1193         }
1194         list_move_tail(&a->dev.knode_bus.n_node, list);
1195 }
1196
1197 static void __init pci_sort_breadthfirst_klist(void)
1198 {
1199         LIST_HEAD(sorted_devices);
1200         struct list_head *pos, *tmp;
1201         struct klist_node *n;
1202         struct device *dev;
1203         struct pci_dev *pdev;
1204         struct klist *device_klist;
1205
1206         device_klist = bus_get_device_klist(&pci_bus_type);
1207
1208         spin_lock(&device_klist->k_lock);
1209         list_for_each_safe(pos, tmp, &device_klist->k_list) {
1210                 n = container_of(pos, struct klist_node, n_node);
1211                 dev = container_of(n, struct device, knode_bus);
1212                 pdev = to_pci_dev(dev);
1213                 pci_insertion_sort_klist(pdev, &sorted_devices);
1214         }
1215         list_splice(&sorted_devices, &device_klist->k_list);
1216         spin_unlock(&device_klist->k_lock);
1217 }
1218
1219 static void __init pci_insertion_sort_devices(struct pci_dev *a, struct list_head *list)
1220 {
1221         struct pci_dev *b;
1222
1223         list_for_each_entry(b, list, global_list) {
1224                 if (pci_sort_bf_cmp(a, b) <= 0) {
1225                         list_move_tail(&a->global_list, &b->global_list);
1226                         return;
1227                 }
1228         }
1229         list_move_tail(&a->global_list, list);
1230 }
1231
1232 static void __init pci_sort_breadthfirst_devices(void)
1233 {
1234         LIST_HEAD(sorted_devices);
1235         struct pci_dev *dev, *tmp;
1236
1237         down_write(&pci_bus_sem);
1238         list_for_each_entry_safe(dev, tmp, &pci_devices, global_list) {
1239                 pci_insertion_sort_devices(dev, &sorted_devices);
1240         }
1241         list_splice(&sorted_devices, &pci_devices);
1242         up_write(&pci_bus_sem);
1243 }
1244
1245 void __init pci_sort_breadthfirst(void)
1246 {
1247         pci_sort_breadthfirst_devices();
1248         pci_sort_breadthfirst_klist();
1249 }
1250