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