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