Merge "of: cache phandle nodes to reduce cost of of_find_node_by_phandle()"
diff --git a/drivers/of/base.c b/drivers/of/base.c
index a0bccb5..431a051 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -198,10 +198,70 @@
return 0;
}
+static struct device_node **phandle_cache;
+static u32 phandle_cache_mask;
+
+/*
+ * Assumptions behind phandle_cache implementation:
+ * - phandle property values are in a contiguous range of 1..n
+ *
+ * If the assumptions do not hold, then
+ * - the phandle lookup overhead reduction provided by the cache
+ * will likely be less
+ */
+static void of_populate_phandle_cache(void)
+{
+ unsigned long flags;
+ u32 cache_entries;
+ struct device_node *np;
+ u32 phandles = 0;
+
+ raw_spin_lock_irqsave(&devtree_lock, flags);
+
+ kfree(phandle_cache);
+ phandle_cache = NULL;
+
+ for_each_of_allnodes(np)
+ if (np->phandle && np->phandle != OF_PHANDLE_ILLEGAL)
+ phandles++;
+
+ cache_entries = roundup_pow_of_two(phandles);
+ phandle_cache_mask = cache_entries - 1;
+
+ phandle_cache = kcalloc(cache_entries, sizeof(*phandle_cache),
+ GFP_ATOMIC);
+
+ if (phandle_cache)
+ for_each_of_allnodes(np)
+ if (np->phandle && np->phandle != OF_PHANDLE_ILLEGAL)
+ phandle_cache[np->phandle & phandle_cache_mask] = np;
+
+ raw_spin_unlock_irqrestore(&devtree_lock, flags);
+}
+
+#ifndef CONFIG_MODULES
+static int __init of_free_phandle_cache(void)
+{
+ unsigned long flags;
+
+ raw_spin_lock_irqsave(&devtree_lock, flags);
+
+ kfree(phandle_cache);
+ phandle_cache = NULL;
+
+ raw_spin_unlock_irqrestore(&devtree_lock, flags);
+
+ return 0;
+}
+late_initcall_sync(of_free_phandle_cache);
+#endif
+
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);
@@ -1093,16 +1153,32 @@
*/
struct device_node *of_find_node_by_phandle(phandle handle)
{
- struct device_node *np;
+ struct device_node *np = NULL;
unsigned long flags;
+ phandle masked_handle;
if (!handle)
return NULL;
raw_spin_lock_irqsave(&devtree_lock, flags);
- for_each_of_allnodes(np)
- if (np->phandle == handle)
- break;
+
+ masked_handle = handle & phandle_cache_mask;
+
+ if (phandle_cache) {
+ if (phandle_cache[masked_handle] &&
+ handle == phandle_cache[masked_handle]->phandle)
+ np = phandle_cache[masked_handle];
+ }
+
+ if (!np) {
+ for_each_of_allnodes(np)
+ if (np->phandle == handle) {
+ if (phandle_cache)
+ phandle_cache[masked_handle] = np;
+ 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 18bbb451..dca2fe5 100644
--- a/drivers/of/of_private.h
+++ b/drivers/of/of_private.h
@@ -86,6 +86,9 @@
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
+
/* 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 46325d6..67b1d72 100644
--- a/drivers/of/resolver.c
+++ b/drivers/of/resolver.c
@@ -21,9 +21,6 @@
#include <linux/string.h>
#include <linux/slab.h>
-/* illegal phandle value (set when unresolved) */
-#define OF_PHANDLE_ILLEGAL 0xdeadbeef
-
/**
* Find a node with the give full name by recursively following any of
* the child node links.