From mboxrd@z Thu Jan 1 00:00:00 1970 From: Frank Rowand Subject: Re: [PATCH] of: use hash based search in of_find_node_by_phandle Date: Thu, 25 Jan 2018 11:54:46 -0800 Message-ID: <5a7793df-725e-608d-778b-cb81fde0cc64@gmail.com> References: <1516875247-19599-1-git-send-email-cpandya@codeaurora.org> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Return-path: In-Reply-To: <1516875247-19599-1-git-send-email-cpandya@codeaurora.org> Content-Language: en-US Sender: linux-arm-msm-owner@vger.kernel.org To: Chintan Pandya , robh+dt@kernel.org, devicetree@vger.kernel.org Cc: linux-kernel@vger.kernel.org, linux-arm-msm@vger.kernel.org List-Id: devicetree@vger.kernel.org On 01/25/18 02:14, Chintan Pandya wrote: > of_find_node_by_phandle() takes a lot of time finding > right node when your intended device is too right-side > in the fdt. Reason is, we search each device serially > from the fdt, starting from left-most to right-most. Please give me a pointer to the code that is doing this search. -Frank > > Implement, device-phandle relation in hash-table so > that look up can be faster. > > Change-Id: I4a2bc7eff6de142e4f91a7bf474893a45e61c128 > Signed-off-by: Chintan Pandya > --- > drivers/of/base.c | 9 +++++++-- > drivers/of/fdt.c | 18 ++++++++++++++++++ > include/linux/of.h | 6 ++++++ > 3 files changed, 31 insertions(+), 2 deletions(-) > > diff --git a/drivers/of/base.c b/drivers/of/base.c > index a0bccb5..3e06316 100644 > --- a/drivers/of/base.c > +++ b/drivers/of/base.c > @@ -25,6 +25,7 @@ > #include > #include > #include > +#include > #include > #include > #include > @@ -1099,10 +1100,14 @@ struct device_node *of_find_node_by_phandle(phandle handle) > if (!handle) > return NULL; > > - raw_spin_lock_irqsave(&devtree_lock, flags); > - for_each_of_allnodes(np) > + spin_lock(&dt_hash_spinlock); > + hash_for_each_possible(dt_hash_table, np, hash, handle) > if (np->phandle == handle) > break; > + > + spin_unlock(&dt_hash_spinlock); > + > + raw_spin_lock_irqsave(&devtree_lock, flags); > of_node_get(np); > raw_spin_unlock_irqrestore(&devtree_lock, flags); > return np; > diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c > index c0914fb..f0e78a7 100644 > --- a/drivers/of/fdt.c > +++ b/drivers/of/fdt.c > @@ -31,6 +31,10 @@ > #include /* for COMMAND_LINE_SIZE */ > #include > > +static bool dt_hash_needs_init = true; > +DECLARE_HASHTABLE(dt_hash_table, DT_HASH_BITS); > +DEFINE_SPINLOCK(dt_hash_spinlock); > + > /* > * of_fdt_limit_memory - limit the number of regions in the /memory node > * @limit: maximum entries > @@ -227,6 +231,20 @@ static void populate_properties(const void *blob, > pprev = &pp->next; > } > > + /* > + * In 'dryrun = true' cases, np is some non-NULL junk. So, protect > + * against those cases. > + */ > + if (!dryrun && np->phandle) { > + spin_lock(&dt_hash_spinlock); > + if (dt_hash_needs_init) { > + dt_hash_needs_init = false; > + hash_init(dt_hash_table); > + } > + hash_add(dt_hash_table, &np->hash, np->phandle); > + spin_unlock(&dt_hash_spinlock); > + } > + > /* With version 0x10 we may not have the name property, > * recreate it here from the unit name if absent > */ > diff --git a/include/linux/of.h b/include/linux/of.h > index 299aeb1..5b3f4f1 100644 > --- a/include/linux/of.h > +++ b/include/linux/of.h > @@ -25,6 +25,7 @@ > #include > #include > #include > +#include > > #include > #include > @@ -61,6 +62,7 @@ struct device_node { > struct kobject kobj; > unsigned long _flags; > void *data; > + struct hlist_node hash; > #if defined(CONFIG_SPARC) > const char *path_component_name; > unsigned int unique_id; > @@ -68,6 +70,10 @@ struct device_node { > #endif > }; > > +#define DT_HASH_BITS 6 > +extern DECLARE_HASHTABLE(dt_hash_table, DT_HASH_BITS); > +extern spinlock_t dt_hash_spinlock; > + > #define MAX_PHANDLE_ARGS 16 > struct of_phandle_args { > struct device_node *np; >