xref: /linux/drivers/pci/probe.c (revision 98366c20a275e957416e9516db5dcb7195b4e101)
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 
1298