devicetree.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Frank Rowand <frowand.list@gmail.com>
To: Chintan Pandya <cpandya@codeaurora.org>,
	robh+dt@kernel.org, devicetree@vger.kernel.org
Cc: linux-kernel@vger.kernel.org, linux-arm-msm@vger.kernel.org
Subject: Re: [PATCH] of: use hash based search in of_find_node_by_phandle
Date: Thu, 25 Jan 2018 11:54:46 -0800	[thread overview]
Message-ID: <5a7793df-725e-608d-778b-cb81fde0cc64@gmail.com> (raw)
In-Reply-To: <1516875247-19599-1-git-send-email-cpandya@codeaurora.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 <cpandya@codeaurora.org>
> ---
>  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 <linux/cpu.h>
>  #include <linux/module.h>
>  #include <linux/of.h>
> +#include <linux/hashtable.h>
>  #include <linux/of_graph.h>
>  #include <linux/spinlock.h>
>  #include <linux/slab.h>
> @@ -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 <asm/setup.h>  /* for COMMAND_LINE_SIZE */
>  #include <asm/page.h>
>  
> +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 <linux/notifier.h>
>  #include <linux/property.h>
>  #include <linux/list.h>
> +#include <linux/hashtable.h>
>  
>  #include <asm/byteorder.h>
>  #include <asm/errno.h>
> @@ -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;
> 

  parent reply	other threads:[~2018-01-25 19:54 UTC|newest]

Thread overview: 9+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-01-25 10:14 [PATCH] of: use hash based search in of_find_node_by_phandle Chintan Pandya
     [not found] ` <1516875247-19599-1-git-send-email-cpandya-sgV2jX0FEOL9JmXXK+q4OQ@public.gmane.org>
2018-01-25 14:50   ` Rob Herring
2018-01-26  7:22     ` Chintan Pandya
2018-01-26 15:21       ` Rob Herring
2018-01-25 19:54 ` Frank Rowand [this message]
     [not found]   ` <5a7793df-725e-608d-778b-cb81fde0cc64-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
2018-01-26  8:22     ` Chintan Pandya
2018-01-26 21:27       ` Frank Rowand
2018-01-26 21:29         ` Frank Rowand
     [not found]           ` <c1c21be3-c279-653c-2529-a9cc325865cc-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>
2018-01-26 21:34             ` Frank Rowand

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=5a7793df-725e-608d-778b-cb81fde0cc64@gmail.com \
    --to=frowand.list@gmail.com \
    --cc=cpandya@codeaurora.org \
    --cc=devicetree@vger.kernel.org \
    --cc=linux-arm-msm@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=robh+dt@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).