Grant Likely [Tue, 8 Jan 2008 19:20:40 +0000 (06:20 +1100)]
[POWERPC] Add of_find_matching_node() helper function
Similar to of_find_compatible_node(), of_find_matching_node() and
for_each_matching_node() allow you to iterate over the device tree
looking for specific nodes, except that they take of_device_id
tables instead of strings.
This also moves of_match_node() from driver/of/device.c to
driver/of/base.c to colocate it with the of_find_matching_node which
depends on it.
Signed-off-by: Grant Likely <grant.likely@secretlab.ca> Signed-off-by: Paul Mackerras <paulus@samba.org>
All the __devexit functions are now appropriately tagged. This fixes
some ppc link warnings.
Signed-off-by: Stephen Neuendorffer <stephen.neuendorffer@xilinx.com> Acked-by: Peter Korsgaard <jacmet@sunsite.dk> Signed-off-by: Grant Likely <grant.likely@secretlab.ca>
This now better describes what the UBoot device tree generator
actually does. In particular:
1) Nodes have a label derived from the device name, and a node name
derived from a generic version of the device type, e.g. 'ethernet',
'serial', etc.
2) Usage of compound nodes (representing more than one device in the
same IP) which actually works. This requires having a valid
compatible node, and all the other things that a bus normally has.
I've chosen 'xlnx,compound' as the bus name to describe these compound
nodes.
In addition, I've clarified some of the language relating to how mhs
nodes should be represent in the device tree.
Signed-off-by: Stephen Neuendorffer <stephen.neuendorffer@xilinx.com> Signed-off-by: Grant Likely <grant.likely@secretlab.ca>
Stefan Roese [Mon, 31 Dec 2007 05:41:15 +0000 (16:41 +1100)]
[POWERPC] 4xx: PCIe: Increase max busses per port to 64
Because of how big mapping the config space is (1M per bus), we limit how
many busses we support for now. In the long run, we could replace that
with something akin to kmap_atomic instead.
This patch changes the limit from currently 16 to 64.
Signed-off-by: Stefan Roese <sr@denx.de> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
Olof Johansson [Fri, 28 Dec 2007 04:16:29 +0000 (22:16 -0600)]
[POWERPC] pasemi: Distribute interrupts evenly across cpus
By default the OpenPIC on PWRficient will bias to one core (since that
will improve changes of the other core being able to stay idle/powered
down). However, this conflicts with most irq load balancing schemes,
since setting an interrupt to be delivered to either core doesn't really
result in the load being shared. It also doesn't work well with the
soft irq disable feature of PPC, since EE will stay on until the first
interrupt is taken while soft disabled.
Set the gconf0 config bit that enables even distribution of interrupts
among the two cores.
Olof Johansson [Thu, 20 Dec 2007 19:11:18 +0000 (13:11 -0600)]
[POWERPC] pasemi: Implement NMI support
Some PWRficient-based boards have a NMI button that's wired up to a GPIO
as interrupt source. By configuring the openpic accordingly, these get
delivered as a machine check with high priority, instead of as an external
interrupt.
The device tree contains a property "nmi-source" in the openpic node
for these systems, and it's the (hwirq) source for the input.
Also, for these interrupts, the IACK is read from another register than
the regular (MCACK instead), but they are EOI'd as usual. So implement
said function for the mpic driver.
Finally, move a couple of external function defines to include/ instead
of local under sysdev. Being able to mask/unmask and eoi directly saves
us from setting up a dummy irq handler that will never be called.
Josh Boyer [Mon, 24 Dec 2007 16:42:02 +0000 (10:42 -0600)]
[POWERPC] 4xx: Use machine_device_initcall for bus probe
Some machine_xx_initcall macros were recently added that check for the machine
type before calling the function. This converts the 4xx platforms to use those
for bus probing.
Josh Boyer [Mon, 24 Dec 2007 14:44:47 +0000 (08:44 -0600)]
[POWERPC] Conditionally compile e200 and e500 platforms in cputable
The e200 and e500 platforms are separated in various parts of the kernel with
ifdefs, most notably reg_booke.h and traps.c. The new machine_check rework
requires them to be similarly separated in cputable.c to avoid compile errors.
Stefan Roese [Sat, 15 Dec 2007 08:10:56 +0000 (19:10 +1100)]
[POWERPC] 4xx: Change Kilauea PCIe bus ranges in dts file
Currently we have some limitations in the 4xx PCIe driver and can't
support all possible PCIe busses. But the current limits in the
dts file are quite low (only 16 busses per RC). This patch increases
the number to 64 per RC.
Signed-off-by: Stefan Roese <sr@denx.de> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
Renaming the CPU nodes with generic names put the CPU model in
the "model" property and thus broke the PowerPC 440EP(x)/440GR(x)
identical PVR workaround. The updates it to use the new model property
for CPU identification.
Josh Boyer [Thu, 6 Dec 2007 19:20:05 +0000 (13:20 -0600)]
[POWERPC] 4xx: Rename CPU nodes to avoid dtc incompatibility
Recent DTC versions disallow certain special characters in full paths without
being quoted with {}. That however breaks compatibility with older DTC
versions. Work around this by renaming the CPU nodes for the 4xx files to a
generic node name, and specify the processor type in the model property of the
CPU node.
Stefan Roese [Sat, 1 Dec 2007 10:25:00 +0000 (21:25 +1100)]
[POWERPC] 4xx: Change Kilauea dts to support new EMAC device tree properties
The recent changes from Benjamin Herrenschmidt to the ibm_newemac now
make it possible to support other 4xx variants by just defining the
correct properties in the device tree. In this case of the 405EX we
need to define "has-mdio" in the RGMII node and "has-inverted-stacr-oc"
and "has-new-stacr-staopc" in the EMAC node same as on the 440EPx.
Signed-off-by: Stefan Roese <sr@denx.de> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
Stefan Roese [Tue, 20 Nov 2007 10:19:16 +0000 (21:19 +1100)]
[POWERPC] 4xx: Fix TLB 0 problem with CONFIG_SERIAL_TEXT_DEBUG
Right now TLB entry 0 ist used as UART0 mapping for the early debug
output (via CONFIG_SERIAL_TEXT_DEBUG). This causes problems when many
TLB's get used upon Linux bootup (e.g. while PCIe scanning behind
bridges and/or switches on 440SPe platforms). This will overwrite the
TLB 0 entry and further debug output's may crash/hang the system.
This patch moves the early debug UART0 TLB entry from 0 to 62 as done
in arch/powerpc. This way it is in the "pinned" area and will not get
overwritten. Also the arch/ppc/mm/44x_mmu.c code is now synced with the
newer code from arch/powerpc.
Signed-off-by: Stefan Roese <sr@denx.de> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
This is a UIC cascade handler rework to use set_irq_chained_handler() for
cascade, just like othe ppc platforms do. With current implementation we have
additional redirection for irq handler and we call generic_handle_irq twice
(once for the primary uic and the other time for handling cascade interrupt).
This causes Ingo's realtime support patch to stop working on 4xx.
Not sure of any other possible problems though, but with
set_irq_chained_handler() we can abolish "struct irqaction cascade" from the
chip descriptor and call generic_handle_irq() once, directly for cascade irq.
[POWERPC] 4xx: make UIC use generic level irq handler
This patch makes PowerPC 4xx UIC use generic level irq handler instead
of a custom handle_uic_irq() function. We ack only edge irqs in mask_ack
callback, since acking a level irq on UIC has no effect if the interrupt
is still asserted by the device, even if the interrupt is already masked.
So, to really de-assert the interrupt we need to de-assert the external
source first *and* ack it on UIC then. The handle_level_irq() function
masks and ack's the interrupt with mask_ack callback prior to calling
the actual ISR and unmasks it at the end. So, to use it with UIC interrupts
we need to ack level irqs in the unmask callback instead, after the ISR
has de-asserted the external interrupt source. Even if we ack the interrupt
that we didn't handle (unmask/ack it at the end of the handler, while
next irq is already pending) it will not de-assert the irq, untill we
de-assert its exteral source.
Stefan Roese [Fri, 21 Dec 2007 04:39:38 +0000 (15:39 +1100)]
[POWERPC] 4xx: Add 440SPe revA runtime detection to PCIe
This patch adds runtime detection of the 440SPe revision A chips. These
chips are equipped with a slighly different PCIe core and need special/
different initialization. The compatible node is changed to
"plb-pciex-440spe" ("A" and "B" dropped). This is needed for boards that
can be equipped with both PPC revisions like the AMCC Yucca.
Signed-off-by: Stefan Roese <sr@denx.de> Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
[POWERPC] pci32: 4xx embedded platforms want to reassign all PCI resources
This makes 4xx embedded platforms re-assign all PCI resources as we
pretty much never care about what the various firmwares have done on
these, it's generally not compatible with the way the kernel will map
the bridges.
We still need to also enable bus renumbering on some of them, but I
will do that from a separate patch after I've fixed 4xx PCIe to handle
all bus numbers.
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
This improves the way the 4xx PCI-E code handles checking for a link
and adds explicit testing of CRS result codes on config space accesses.
This should make it more reliable.
Also, bridges with no link are now still created, though config space
accesses beyond the root complex are filtered. This is one step toward
eventually supporting hotplug.
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
[POWERPC] 4xx: remove bogus "ranges" property in Bamboo EBC node
This removes a bogus empty "ranges" property in the EBC device node
of the Bamboo board device-tree.
The "ranges" property should be created by the wrapper code when it is
implemented. Until then, remove the empty property since it incorrectly
implies that there is a 1:1 address mapping between the EBC and the OPB.
This also fixes a warning from newer DTCs.
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
[POWERPC] 4xx: Rework clock probing in boot wrapper
This reworks the boot wrapper library function that probes
the chip clocks. Better separate the base function that is
used on 440GX,SPe,EP,... from the uart fixups as those need
different device-tree path on different processors.
Also, rework the function itself based on the arch/ppc code
from Eugene Surovegin which I find more readable, and which
handles one more bypass case. Also handle the subtle difference
between 440EP/EPx and 440SPe/GX, on the former, PerClk is derived
from the PLB clock while on the later, it's derived from the OPB.
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
[POWERPC] 4xx: Wire up 440EP USB controller support to Bamboo board
This adds the definition of the on-chip OHCI controller to the
Bamboo board's device-tree. This is enough to get it probed and
working, though a separate patch fixing a bug in the OHCI driver
is needed to make it reliable.
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
[POWERPC] 4xx: EP405 boards support for arch/powerpc
Brings EP405 support to arch/powerpc. The IRQ routing for the CPLD
comes from a device-tree property, PCI is working to the point where
I can see the video card, USB device, and south bridge.
This should work with both EP405 and EP405PC.
I've not totally figured out how IRQs are wired on this hardware
though, thus at this stage, expect only USB interrupts working,
pretty much the same as what arch/ppc did.
Also, the flash, nvram, rtc and temp control still have to be wired.
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
This adds to the previous 2 patches the support for the 4xx PCI Express
cells as found in the 440SPe revA, revB and 405EX.
Unfortunately, due to significant differences between these, and other
interesting "features" of those pieces of HW, the code isn't as simple
as it is for PCI and PCI-X and some of the functions differ significantly
between the 3 implementations. Thus, not only this code can only support
those 3 implementations for now and will refuse to operate on any other,
but there are added ifdef's to avoid the bloat of building a fairly large
amount of code on platforms that don't need it.
Also, this code currently only supports fully initializing root complex
nodes, not endpoint. Some more code will have to be lifted from the
arch/ppc implementation to add the endpoint support, though it's mostly
differences in memory mapping, and the question on how to represent
endpoint mode PCI in the device-tree is thus open.
Many thanks to Stefan Roese for testing & fixing up the 405EX bits !
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Stefan Roese <sr@denx.de> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
This adds base support code for the 4xx PCI-X bridge. It also provides
placeholders for the PCI and PCI-E version but they aren't supported
with this patch.
The bridges are configured based on device-tree properties.
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
[POWERPC] Reworking machine check handling and Fix 440/440A
This adds a cputable function pointer for the CPU-side machine
check handling. The semantic is still the same as the old one,
the one in ppc_md. overrides the one in cputable, though
ultimately we'll want to change that so the CPU gets first.
This removes CONFIG_440A which was a problem for multiplatform
kernels and instead fixes up the IVOR at runtime from a setup_cpu
function. The "A" version of the machine check also tweaks the
regs->trap value to differenciate the 2 versions at the C level.
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Josh Boyer <jwboyer@linux.vnet.ibm.com>
Stephen Rothwell [Fri, 21 Dec 2007 04:37:07 +0000 (15:37 +1100)]
[POWERPC] Make non-PCI build work again
Maple and pasemi both require PCI as does CONFIG_OF_PLATFORM_PCI.
The default setting of CONFIG_ISA_DMA_API is set to match the protection
around the relevant routines in asm/dma.h.
I also had to remove the PMAC platform from the combined build. The
precis is that to build a 64 bit kernel with no PCI, you can only include
pSeries and iSeries.
Signed-off-by: Stephen Rothwell <sfr@canb.auug.org.au> Signed-off-by: Paul Mackerras <paulus@samba.org>
Stephen Rothwell [Fri, 21 Dec 2007 04:23:48 +0000 (15:23 +1100)]
[POWERPC] Pointers marked as __iomem do not need to be volatile
Fixes this warning:
arch/powerpc/platforms/powermac/pci.c: In function 'u3_ht_cfg_access':
arch/powerpc/platforms/powermac/pci.c:354: warning: return discards qualifiers from pointer target type
arch/powerpc/platforms/powermac/pci.c:358: warning: return discards qualifiers from pointer target type
Signed-off-by: Stephen Rothwell <sfr@canb.auug.org.au> Signed-off-by: Paul Mackerras <paulus@samba.org>
These hooks ensure that a decrementer interrupt is not pending when
suspending; otherwise, problems may occur on 6xx/7xx/7xxx-based
systems (except for powermacs, which use a separate suspend path).
For example, with deep sleep on the 831x, a pending decrementer will
cause a system freeze because the SoC thinks the decrementer interrupt
would have woken the system, but the core must have interrupts
disabled due to the setup required for deep sleep.
Changed via-pmu.c to use the new ppc_md hooks, and made the arch_*
functions call the generic_* functions unconditionally. -- paulus
Signed-off-by: Scott Wood <scottwood@freescale.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
Andre Detsch [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: DMA Restart after SIGSEGV
This fixes the behavior of spufs when a spu tries a DMA operation
based on a wrong / unavailable address.
Instead of just generating a SIGBUS signal, spufs now
generates a SIGSEGV signal and restarts the problematic DMA operation
after the execution of the application's signal handler. This allows
applications to employ user-level paging systems.
Although the restart_dma function is called before the application's
signal handler, the operation is not actually performed at this time,
since the spu context is already stopped. The operation only takes
place when spu_run is restarted (which happens automatically).
Signed-off-by: Andre Detsch <adetsch@br.ibm.com> Signed-off-by: Arnd Bergmann <arnd@arndb.de> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Aegis Lin [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: Use separate timer for /proc/spu_loadavg calculation
The original spusched_timer was designed to take effect only when
a context is waiting in the runqueue.
This change adds an additional lower-freq timer has been added to
purely handle the spu_load updates. The new timer will be triggered
per LOAD_FREQ ticks.
Signed-off-by: Aegis Lin <aegislin@gmail.com> Signed-off-by: Arnd Bergmann <arnd@arndb.de> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Make most places that use spu_acquire/spu_acquire_saved interruptible,
this allows getting out of the spufs code when e.g. pressing ctrl+c.
There are a few places where we get called e.g. from spufs teardown
routines were we can't simply err out so these are left with a comment.
For now I've also not touched the poll routines because it's open what
libspe would expect in terms of interrupted system calls.
Acked-by: Arnd Bergmann <arnd.bergmann@de.ibm.com> Signed-off-by: Christoph Hellwig <hch@lst.de> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
The simple attr macros currently used by spufs can't deal with the
handlers returning errors, which is required to make the state_mutex
interruptible. This adds a local copy that allows for an error
return from the get/set handlers.
Signed-off-by: Christoph Hellwig <hch@lst.de> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Luke Browning [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: decouple spu scheduler from spufs_spu_run (asynchronous scheduling)
Change spufs_spu_run so that the context is queued directly to the
scheduler and the controlling thread advances directly to spufs_wait()
for spe errors and exceptions.
nosched contexts are treated the same as before.
Fixes from Christoph Hellwig <hch@lst.de>
Signed-off-by: Luke Browning <lukebr@linux.vnet.ibm.com> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Masato Noguchi [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: don't set reserved bits in spu interrupt status
This changes the spu context switch code to not write to reserved bits
of spu interrupt status register.
The architecture book says the reserved fields should be set to zero.
Signed-off-by: Masato Noguchi <Masato.Noguchi@jp.sony.com> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Luke Browning [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: reorganize spu_run_init
This cleans up spu_run_init so that it does all of the spu
initialization for spufs_run_spu. It initializes the spu context as
much as possible before it activates the spu and writes the runcntl
register.
Signed-off-by: Luke Browning <lukebr@linux.vnet.ibm.com> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Jeremy Kerr [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: rework class 0 and 1 interrupt handling
Based on original patches from
Arnd Bergmann <arnd.bergman@de.ibm.com>; and
Luke Browning <lukebr@linux.vnet.ibm.com>
Currently, spu contexts need to be loaded to the SPU in order to take
class 0 and class 1 exceptions.
This change makes the actual interrupt-handlers much simpler (ie,
set the exception information in the context save area), and defers the
handling code to the spufs_handle_class[01] functions, called from
spufs_run_spu.
This should improve the concurrency of the spu scheduling leading to
greater SPU utilization when SPUs are overcommited.
Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Jeremy Kerr [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: use #defines for SPU class [012] exception status
Add a few #defines for the class 0, 1 and 2 interrupt status bits, and
use them instead of magic numbers when we're setting or checking for
these interrupts.
Also, add a #define for the class 2 mailbox threshold interrupt mask.
Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Luke Browning [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: add backing ops for privcntl register
This change encapsulates the spu_privcntl_RW register so that it can
be written through backing ops. This is necessary so that spu contexts
can be initialized and queued to the scheduler in spufs_run_spu.
Signed-off-by: Luke Browning <lukebr@linux.vnet.ibm.com> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Arnd Bergmann [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: block fault handlers in spu_acquire_runnable
This change disables the logic that faults-in spu contexts under the
covers from the page fault handler. When a fault requires a runnable
context, the handler will block until the context is scheduled by
other means.
Signed-off-by: Arnd Bergmann <arnd.bergmann@de.ibm.com> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Jeremy Kerr [Thu, 20 Dec 2007 07:39:59 +0000 (16:39 +0900)]
[POWERPC] spufs: move fault, lscsa_alloc and switch code to spufs module
Currently, part of the spufs code (switch.o, lscsa_alloc.o and fault.o)
is compiled directly into the kernel.
This change moves these components of spufs into the kernel.
The lscsa and switch objects are fairly straightforward to move in.
For the fault.o module, we split the fault-handling code into two
parts: a/p/p/c/spu_fault.c and a/p/p/c/spufs/fault.c. The former is for
the in-kernel spu_handle_mm_fault function, and we move the rest of the
fault-handling code into spufs.
Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Masato Noguchi [Wed, 5 Dec 2007 02:49:31 +0000 (13:49 +1100)]
[POWERPC] cell: wrap master run control bit
Add platform specific SPU run control routines to the spufs. The current
spufs implementation uses the SPU master run control bit (MFC_SR1[S]) to
control SPE execution, but the PS3 hypervisor does not support the use of
this feature.
This change adds the run control wrapper routies spu_enable_spu() and
spu_disable_spu(). The bare metal routines use the master run control
bit, and the PS3 specific routines use the priv2 run control register.
An outstanding enhancement for the PS3 would be to add a guard to check
for incorrect access to the spu problem state when the spu context is
disabled. This check could be implemented with a flag added to the spu
context that would inhibit mapping problem state pages, and a routine
to unmap spu problem state pages. When the spu is enabled with
ps3_enable_spu() the flag would be set allowing pages to be mapped,
and when the spu is disabled with ps3_disable_spu() the flag would be
cleared and mapped problem state pages would be unmapped.
Signed-off-by: Masato Noguchi <Masato.Noguchi@jp.sony.com> Signed-off-by: Geoff Levand <geoffrey.levand@am.sony.com> Signed-off-by: Jeremy Kerr <jk@ozlabs.org> Signed-off-by: Paul Mackerras <paulus@samba.org>
Emil Medve [Tue, 13 Nov 2007 16:24:04 +0000 (03:24 +1100)]
[POWERPC] Optimize counting distinct entries in the relocation sections
When a module has relocation sections with tens of thousands of
entries, counting the distinct/unique entries only (i.e. no
duplicates) at load time can take tens of seconds and up to minutes.
The sore point is the count_relocs() function which is called as part
of the architecture specific module loading processing path:
Here count_relocs is being called to find out how many distinct
targets of R_PPC_REL24 relocations there are, since each distinct
target needs a PLT entry or a stub created for it.
The previous counting algorithm has O(n^2) complexity. Basically two
solutions were proposed on the e-mail list: a hash based approach and
a sort based approach.
The hash based approach is the fastest (O(n)) but the has it needs
additional memory and for certain corner cases it could take lots of
memory due to the degeneration of the hash. One such proposal was
submitted here:
The sort based approach is slower (O(n * log n + n)) but if the
sorting is done "in place" it doesn't need additional memory.
This has O(n + n * log n) complexity with no additional memory
requirements.
This commit implements the in-place sort option.
Signed-off-by: Emil Medve <Emilian.Medve@Freescale.com> Signed-off-by: Paul Mackerras <paulus@samba.org>
projects / linux-2.6 / log