From: Frank Rowand <[email protected]>
Create a cache of the nodes that contain a phandle property. Use this
cache to find the node for a given phandle value instead of scanning
the devicetree to find the node. If the phandle value is not found
in the cache, of_find_node_by_phandle() will fall back to the tree
scan algorithm.
The cache is initialized in of_core_init().
The cache is freed via a late_initcall_sync().
---
Some of_find_by_phandle() calls may occur before the cache is
initialized or after it is freed. For example, for the qualcomm
qcom-apq8074-dragonboard, 11 calls occur before the initialization
and 80 occur after the cache is freed (out of 516 total calls.)
Signed-off-by: Frank Rowand <[email protected]>
---
drivers/of/base.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++---
drivers/of/of_private.h | 5 +++
drivers/of/resolver.c | 21 ------------
3 files changed, 86 insertions(+), 25 deletions(-)
diff --git a/drivers/of/base.c b/drivers/of/base.c
index 26618ba8f92a..c3091d0e391f 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -95,10 +95,14 @@ int __weak of_node_to_nid(struct device_node *np)
}
#endif
+static void of_populate_phandle_cache(void);
+
void __init of_core_init(void)
{
struct device_node *np;
+ of_populate_phandle_cache();
+
/* Create the kset, and register existing nodes */
mutex_lock(&of_mutex);
of_kset = kset_create_and_add("devicetree", NULL, firmware_kobj);
@@ -990,6 +994,72 @@ int of_modalias_node(struct device_node *node, char *modalias, int len)
}
EXPORT_SYMBOL_GPL(of_modalias_node);
+phandle live_tree_max_phandle(void)
+{
+ struct device_node *node;
+ phandle max_phandle;
+ unsigned long flags;
+
+ raw_spin_lock_irqsave(&devtree_lock, flags);
+ max_phandle = 0;
+ for_each_of_allnodes(node) {
+ if (node->phandle != OF_PHANDLE_ILLEGAL &&
+ node->phandle > max_phandle)
+ max_phandle = node->phandle;
+ }
+ raw_spin_unlock_irqrestore(&devtree_lock, flags);
+
+ return max_phandle;
+}
+
+static struct device_node **phandle_cache;
+static u32 max_phandle_cache;
+
+static int __init of_free_phandle_cache(void)
+{
+ max_phandle_cache = 0;
+ kfree(phandle_cache);
+ phandle_cache = NULL;
+
+ return 0;
+}
+late_initcall_sync(of_free_phandle_cache);
+
+static void of_populate_phandle_cache(void)
+{
+ unsigned long flags;
+ phandle max_phandle;
+ u32 nodes = 0;
+ struct device_node *np;
+
+ if (phandle_cache)
+ return;
+
+ max_phandle = live_tree_max_phandle();
+
+ raw_spin_lock_irqsave(&devtree_lock, flags);
+
+ for_each_of_allnodes(np)
+ nodes++;
+
+ /* sanity cap for malformed tree */
+ if (max_phandle > nodes)
+ max_phandle = nodes;
+
+ phandle_cache = kzalloc((max_phandle + 1) * sizeof(*phandle_cache),
+ GFP_KERNEL);
+
+ for_each_of_allnodes(np)
+ if (np->phandle != OF_PHANDLE_ILLEGAL &&
+ np->phandle <= max_phandle &&
+ np->phandle)
+ phandle_cache[np->phandle] = np;
+
+ max_phandle_cache = max_phandle;
+
+ raw_spin_unlock_irqrestore(&devtree_lock, flags);
+}
+
/**
* of_find_node_by_phandle - Find a node given a phandle
* @handle: phandle of the node to find
@@ -999,16 +1069,23 @@ int of_modalias_node(struct device_node *node, char *modalias, int len)
*/
struct device_node *of_find_node_by_phandle(phandle handle)
{
- struct device_node *np;
+ struct device_node *np = NULL;
unsigned long flags;
if (!handle)
return NULL;
raw_spin_lock_irqsave(&devtree_lock, flags);
- for_each_of_allnodes(np)
- if (np->phandle == handle)
- break;
+
+ if (handle <= max_phandle_cache)
+ np = phandle_cache[handle];
+
+ if (!np || np->phandle != handle) {
+ for_each_of_allnodes(np)
+ if (np->phandle == handle)
+ break;
+ }
+
of_node_get(np);
raw_spin_unlock_irqrestore(&devtree_lock, flags);
return np;
diff --git a/drivers/of/of_private.h b/drivers/of/of_private.h
index 92a9a3687446..77005978d60a 100644
--- a/drivers/of/of_private.h
+++ b/drivers/of/of_private.h
@@ -135,6 +135,11 @@ extern void __of_update_property_sysfs(struct device_node *np,
extern void __of_sysfs_remove_bin_file(struct device_node *np,
struct property *prop);
+/* illegal phandle value (set when unresolved) */
+#define OF_PHANDLE_ILLEGAL 0xdeadbeef
+
+extern phandle live_tree_max_phandle(void);
+
/* iterators for transactions, used for overlays */
/* forward iterator */
#define for_each_transaction_entry(_oft, _te) \
diff --git a/drivers/of/resolver.c b/drivers/of/resolver.c
index cfaeef5f6cb1..0384ce8fdc3b 100644
--- a/drivers/of/resolver.c
+++ b/drivers/of/resolver.c
@@ -22,27 +22,6 @@
#include "of_private.h"
-/* illegal phandle value (set when unresolved) */
-#define OF_PHANDLE_ILLEGAL 0xdeadbeef
-
-static phandle live_tree_max_phandle(void)
-{
- struct device_node *node;
- phandle phandle;
- unsigned long flags;
-
- raw_spin_lock_irqsave(&devtree_lock, flags);
- phandle = 0;
- for_each_of_allnodes(node) {
- if (node->phandle != OF_PHANDLE_ILLEGAL &&
- node->phandle > phandle)
- phandle = node->phandle;
- }
- raw_spin_unlock_irqrestore(&devtree_lock, flags);
-
- return phandle;
-}
-
static void adjust_overlay_phandles(struct device_node *overlay,
int phandle_delta)
{
--
Frank Rowand <[email protected]>
Hi Rob,
Please ignore this one. My signed-off is below the first "---".
-Frank
On 01/31/18 12:02, [email protected] wrote:
> From: Frank Rowand <[email protected]>
>
> Create a cache of the nodes that contain a phandle property. Use this
> cache to find the node for a given phandle value instead of scanning
> the devicetree to find the node. If the phandle value is not found
> in the cache, of_find_node_by_phandle() will fall back to the tree
> scan algorithm.
>
> The cache is initialized in of_core_init().
>
> The cache is freed via a late_initcall_sync().
>
> ---
>
> Some of_find_by_phandle() calls may occur before the cache is
> initialized or after it is freed. For example, for the qualcomm
> qcom-apq8074-dragonboard, 11 calls occur before the initialization
> and 80 occur after the cache is freed (out of 516 total calls.)
>
> Signed-off-by: Frank Rowand <[email protected]>
> ---
> drivers/of/base.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++---
> drivers/of/of_private.h | 5 +++
> drivers/of/resolver.c | 21 ------------
> 3 files changed, 86 insertions(+), 25 deletions(-)
>
> diff --git a/drivers/of/base.c b/drivers/of/base.c
> index 26618ba8f92a..c3091d0e391f 100644
> --- a/drivers/of/base.c
> +++ b/drivers/of/base.c
> @@ -95,10 +95,14 @@ int __weak of_node_to_nid(struct device_node *np)
> }
> #endif
>
> +static void of_populate_phandle_cache(void);
> +
> void __init of_core_init(void)
> {
> struct device_node *np;
>
> + of_populate_phandle_cache();
> +
> /* Create the kset, and register existing nodes */
> mutex_lock(&of_mutex);
> of_kset = kset_create_and_add("devicetree", NULL, firmware_kobj);
> @@ -990,6 +994,72 @@ int of_modalias_node(struct device_node *node, char *modalias, int len)
> }
> EXPORT_SYMBOL_GPL(of_modalias_node);
>
> +phandle live_tree_max_phandle(void)
> +{
> + struct device_node *node;
> + phandle max_phandle;
> + unsigned long flags;
> +
> + raw_spin_lock_irqsave(&devtree_lock, flags);
> + max_phandle = 0;
> + for_each_of_allnodes(node) {
> + if (node->phandle != OF_PHANDLE_ILLEGAL &&
> + node->phandle > max_phandle)
> + max_phandle = node->phandle;
> + }
> + raw_spin_unlock_irqrestore(&devtree_lock, flags);
> +
> + return max_phandle;
> +}
> +
> +static struct device_node **phandle_cache;
> +static u32 max_phandle_cache;
> +
> +static int __init of_free_phandle_cache(void)
> +{
> + max_phandle_cache = 0;
> + kfree(phandle_cache);
> + phandle_cache = NULL;
> +
> + return 0;
> +}
> +late_initcall_sync(of_free_phandle_cache);
> +
> +static void of_populate_phandle_cache(void)
> +{
> + unsigned long flags;
> + phandle max_phandle;
> + u32 nodes = 0;
> + struct device_node *np;
> +
> + if (phandle_cache)
> + return;
> +
> + max_phandle = live_tree_max_phandle();
> +
> + raw_spin_lock_irqsave(&devtree_lock, flags);
> +
> + for_each_of_allnodes(np)
> + nodes++;
> +
> + /* sanity cap for malformed tree */
> + if (max_phandle > nodes)
> + max_phandle = nodes;
> +
> + phandle_cache = kzalloc((max_phandle + 1) * sizeof(*phandle_cache),
> + GFP_KERNEL);
> +
> + for_each_of_allnodes(np)
> + if (np->phandle != OF_PHANDLE_ILLEGAL &&
> + np->phandle <= max_phandle &&
> + np->phandle)
> + phandle_cache[np->phandle] = np;
> +
> + max_phandle_cache = max_phandle;
> +
> + raw_spin_unlock_irqrestore(&devtree_lock, flags);
> +}
> +
> /**
> * of_find_node_by_phandle - Find a node given a phandle
> * @handle: phandle of the node to find
> @@ -999,16 +1069,23 @@ int of_modalias_node(struct device_node *node, char *modalias, int len)
> */
> struct device_node *of_find_node_by_phandle(phandle handle)
> {
> - struct device_node *np;
> + struct device_node *np = NULL;
> unsigned long flags;
>
> if (!handle)
> return NULL;
>
> raw_spin_lock_irqsave(&devtree_lock, flags);
> - for_each_of_allnodes(np)
> - if (np->phandle == handle)
> - break;
> +
> + if (handle <= max_phandle_cache)
> + np = phandle_cache[handle];
> +
> + if (!np || np->phandle != handle) {
> + for_each_of_allnodes(np)
> + if (np->phandle == handle)
> + break;
> + }
> +
> of_node_get(np);
> raw_spin_unlock_irqrestore(&devtree_lock, flags);
> return np;
> diff --git a/drivers/of/of_private.h b/drivers/of/of_private.h
> index 92a9a3687446..77005978d60a 100644
> --- a/drivers/of/of_private.h
> +++ b/drivers/of/of_private.h
> @@ -135,6 +135,11 @@ extern void __of_update_property_sysfs(struct device_node *np,
> extern void __of_sysfs_remove_bin_file(struct device_node *np,
> struct property *prop);
>
> +/* illegal phandle value (set when unresolved) */
> +#define OF_PHANDLE_ILLEGAL 0xdeadbeef
> +
> +extern phandle live_tree_max_phandle(void);
> +
> /* iterators for transactions, used for overlays */
> /* forward iterator */
> #define for_each_transaction_entry(_oft, _te) \
> diff --git a/drivers/of/resolver.c b/drivers/of/resolver.c
> index cfaeef5f6cb1..0384ce8fdc3b 100644
> --- a/drivers/of/resolver.c
> +++ b/drivers/of/resolver.c
> @@ -22,27 +22,6 @@
>
> #include "of_private.h"
>
> -/* illegal phandle value (set when unresolved) */
> -#define OF_PHANDLE_ILLEGAL 0xdeadbeef
> -
> -static phandle live_tree_max_phandle(void)
> -{
> - struct device_node *node;
> - phandle phandle;
> - unsigned long flags;
> -
> - raw_spin_lock_irqsave(&devtree_lock, flags);
> - phandle = 0;
> - for_each_of_allnodes(node) {
> - if (node->phandle != OF_PHANDLE_ILLEGAL &&
> - node->phandle > phandle)
> - phandle = node->phandle;
> - }
> - raw_spin_unlock_irqrestore(&devtree_lock, flags);
> -
> - return phandle;
> -}
> -
> static void adjust_overlay_phandles(struct device_node *overlay,
> int phandle_delta)
> {
>
FYI, we noticed the following commit (built with gcc-7):
commit: 965aa3fac087bd026f614824b821ef0238e77d60 ("of: cache phandle nodes to decrease cost of of_find_node_by_phandle()")
url: https://github.com/0day-ci/linux/commits/frowand-list-gmail-com/of-cache-phandle-nodes-to-decrease-cost-of-of_find_node_by_phandle/20180203-165032
base: https://git.kernel.org/cgit/linux/kernel/git/robh/linux.git for-next
in testcase: trinity
with following parameters:
runtime: 300s
test-description: Trinity is a linux system call fuzz tester.
test-url: http://codemonkey.org.uk/projects/trinity/
on test machine: qemu-system-i386 -enable-kvm -smp 2 -m 320M
caused below changes (please refer to attached dmesg/kmsg for entire log/backtrace):
+----------------------------------------------------------------+------------+------------+
| | 3a6fbcb2e2 | 965aa3fac0 |
+----------------------------------------------------------------+------------+------------+
| boot_successes | 6 | 0 |
| boot_failures | 0 | 8 |
| BUG:sleeping_function_called_from_invalid_context_at_mm/slab.h | 0 | 8 |
+----------------------------------------------------------------+------------+------------+
[ 0.224970] BUG: sleeping function called from invalid context at mm/slab.h:419
[ 0.226666] in_atomic(): 1, irqs_disabled(): 1, pid: 1, name: swapper/0
[ 0.226666] 1 lock held by swapper/0/1:
[ 0.226666] #0: (devtree_lock){....}, at: [<ba54064f>] of_core_init+0x2c/0x120
[ 0.226666] CPU: 0 PID: 1 Comm: swapper/0 Not tainted 4.15.0-rc3-00024-g965aa3f #2
[ 0.226666] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.10.2-1 04/01/2014
[ 0.226666] Call Trace:
[ 0.226666] dump_stack+0x90/0xc1
[ 0.226666] ___might_sleep+0x116/0x12a
[ 0.226666] __might_sleep+0x6a/0x71
[ 0.226666] slab_pre_alloc_hook+0x34/0x3a
[ 0.226666] __kmalloc+0x5a/0x109
[ 0.226666] ? of_core_init+0x56/0x120
[ 0.226666] of_core_init+0x56/0x120
[ 0.226666] driver_init+0x3a/0x3c
[ 0.226666] kernel_init_freeable+0x81/0x182
[ 0.226666] ? rest_init+0xdc/0xdc
[ 0.226666] kernel_init+0xd/0xd5
[ 0.226666] ret_from_fork+0x19/0x24
[ 0.241320] clocksource: jiffies: mask: 0xffffffff max_cycles: 0xffffffff, max_idle_ns: 6370867519511994 ns
[ 0.243356] futex hash table entries: 512 (order: 4, 65536 bytes)
[ 0.250186] xor: measuring software checksum speed
[ 0.286678] pIII_sse : 9343.200 MB/sec
[ 0.320011] prefetch64-sse: 11689.200 MB/sec
[ 0.321792] xor: using function: prefetch64-sse (11689.200 MB/sec)
[ 0.323356] prandom: seed boundary self test passed
[ 0.327067] prandom: 100 self tests passed
[ 0.328603] pinctrl core: initialized pinctrl subsystem
[ 0.331923] NET: Registered protocol family 16
[ 0.336737] cpuidle: using governor menu
[ 0.340969] ACPI: bus type PCI registered
[ 0.343398] PCI: Using configuration type 1 for base access
[ 0.436695] raid6: mmxx1 gen() 2907 MB/s
[ 0.493355] raid6: mmxx2 gen() 3451 MB/s
[ 0.550029] raid6: sse1x1 gen() 2757 MB/s
[ 0.606694] raid6: sse1x2 gen() 3498 MB/s
[ 0.663347] raid6: sse2x1 gen() 5895 MB/s
[ 0.720015] raid6: sse2x1 xor() 4209 MB/s
[ 0.776680] raid6: sse2x2 gen() 7216 MB/s
[ 0.833351] raid6: sse2x2 xor() 4559 MB/s
[ 0.834868] raid6: using algorithm sse2x2 gen() 7216 MB/s
[ 0.836529] raid6: .... xor() 4559 MB/s, rmw enabled
[ 0.836675] raid6: using intx1 recovery algorithm
[ 0.843471] ACPI: Added _OSI(Module Device)
[ 0.846675] ACPI: Added _OSI(Processor Device)
[ 0.848185] ACPI: Added _OSI(3.0 _SCP Extensions)
[ 0.850008] ACPI: Added _OSI(Processor Aggregator Device)
[ 0.866591] ACPI: Interpreter enabled
[ 0.866794] ACPI: (supports S0 S3 S5)
[ 0.868181] ACPI: Using IOAPIC for interrupt routing
[ 0.870131] PCI: Using host bridge windows from ACPI; if necessary, use "pci=nocrs" and report a bug
[ 0.875152] ACPI: Enabled 2 GPEs in block 00 to 0F
[ 0.935608] ACPI: PCI Root Bridge [PCI0] (domain 0000 [bus 00-ff])
[ 0.936701] acpi PNP0A03:00: _OSC: OS supports [Segments MSI]
[ 0.938597] acpi PNP0A03:00: _OSC failed (AE_NOT_FOUND); disabling ASPM
[ 0.940511] PCI host bridge to bus 0000:00
[ 0.943349] pci_bus 0000:00: root bus resource [io 0x0000-0x0cf7 window]
[ 0.945289] pci_bus 0000:00: root bus resource [io 0x0d00-0xffff window]
[ 0.946682] pci_bus 0000:00: root bus resource [mem 0x000a0000-0x000bffff window]
[ 0.949313] pci_bus 0000:00: root bus resource [mem 0x14000000-0xfebfffff window]
[ 0.950022] pci_bus 0000:00: root bus resource [bus 00-ff]
[ 0.953447] pci 0000:00:00.0: [8086:1237] type 00 class 0x060000
[ 0.958202] pci 0000:00:01.0: [8086:7000] type 00 class 0x060100
[ 0.962102] pci 0000:00:01.1: [8086:7010] type 00 class 0x010180
[ 0.969205] pci 0000:00:01.1: reg 0x20: [io 0xc080-0xc08f]
[ 0.973389] pci 0000:00:01.1: legacy IDE quirk: reg 0x10: [io 0x01f0-0x01f7]
[ 0.976678] pci 0000:00:01.1: legacy IDE quirk: reg 0x14: [io 0x03f6]
[ 0.978604] pci 0000:00:01.1: legacy IDE quirk: reg 0x18: [io 0x0170-0x0177]
[ 0.980009] pci 0000:00:01.1: legacy IDE quirk: reg 0x1c: [io 0x0376]
[ 0.984299] pci 0000:00:01.3: [8086:7113] type 00 class 0x068000
[ 0.986761] pci 0000:00:01.3: quirk: [io 0x0600-0x063f] claimed by PIIX4 ACPI
[ 0.989387] pci 0000:00:01.3: quirk: [io 0x0700-0x070f] claimed by PIIX4 SMB
[ 0.991639] pci 0000:00:02.0: [1234:1111] type 00 class 0x030000
[ 0.996679] pci 0000:00:02.0: reg 0x10: [mem 0xfd000000-0xfdffffff pref]
[ 1.003345] pci 0000:00:02.0: reg 0x18: [mem 0xfebf0000-0xfebf0fff]
[ 1.014696] pci 0000:00:02.0: reg 0x30: [mem 0xfebe0000-0xfebeffff pref]
[ 1.018248] pci 0000:00:03.0: [8086:100e] type 00 class 0x020000
[ 1.023352] pci 0000:00:03.0: reg 0x10: [mem 0xfebc0000-0xfebdffff]
[ 1.033133] pci 0000:00:03.0: reg 0x14: [io 0xc000-0xc03f]
[ 1.050890] pci 0000:00:03.0: reg 0x30: [mem 0xfeb80000-0xfebbffff pref]
[ 1.060444] pci 0000:00:04.0: [1af4:1001] type 00 class 0x010000
[ 1.066682] pci 0000:00:04.0: reg 0x10: [io 0xc040-0xc07f]
[ 1.076693] pci 0000:00:04.0: reg 0x14: [mem 0xfebf1000-0xfebf1fff]
[ 1.100012] pci 0000:00:04.0: reg 0x20: [mem 0xfe000000-0xfe003fff 64bit pref]
[ 1.114367] pci 0000:00:05.0: [8086:25ab] type 00 class 0x088000
[ 1.120936] pci 0000:00:05.0: reg 0x10: [mem 0xfebf2000-0xfebf200f]
[ 1.144467] pci_bus 0000:00: on NUMA node 0
[ 1.151614] ACPI: PCI Interrupt Link [LNKA] (IRQs 5 *10 11)
[ 1.154737] ACPI: PCI Interrupt Link [LNKB] (IRQs 5 *10 11)
[ 1.157861] ACPI: PCI Interrupt Link [LNKC] (IRQs 5 10 *11)
[ 1.160975] ACPI: PCI Interrupt Link [LNKD] (IRQs 5 10 *11)
[ 1.166813] ACPI: PCI Interrupt Link [LNKS] (IRQs *9)
[ 1.173478] pci 0000:00:02.0: vgaarb: setting as boot VGA device
[ 1.175299] pci 0000:00:02.0: vgaarb: VGA device added: decodes=io+mem,owns=io+mem,locks=none
[ 1.176692] pci 0000:00:02.0: vgaarb: bridge control possible
[ 1.178458] vgaarb: loaded
[ 1.190067] EDAC MC: Ver: 3.0.0
[ 1.193600] EDAC DEBUG: edac_mc_sysfs_init: device mc created
[ 1.199892] PCI: Using ACPI for IRQ routing
[ 1.200009] PCI: pci_cache_line_size set to 32 bytes
[ 1.201544] e820: reserve RAM buffer [mem 0x0009fc00-0x0009ffff]
To reproduce:
git clone https://github.com/intel/lkp-tests.git
cd lkp-tests
bin/lkp qemu -k <bzImage> job-script # job-script is attached in this email
Thanks,
lkp