Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1401637 > unrolled thread

[PATCH v2 2/5] of: Support hashtable lookups for phandles

Started byPantelis Antoniou <pantelis.antoniou@konsulko.com>
First post2016-05-16 19:00 +0200
Last post2016-05-16 22:20 +0200
Articles 3 — 2 participants

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH v2 2/5] of: Support hashtable lookups for phandles Pantelis Antoniou <pantelis.antoniou@konsulko.com> - 2016-05-16 19:00 +0200
    Re: [PATCH v2 2/5] of: Support hashtable lookups for phandles Rob Herring <robherring2@gmail.com> - 2016-05-16 21:40 +0200
      Re: [PATCH v2 2/5] of: Support hashtable lookups for phandles Pantelis Antoniou <pantelis.antoniou@konsulko.com> - 2016-05-16 22:20 +0200

#1401637 — [PATCH v2 2/5] of: Support hashtable lookups for phandles

FromPantelis Antoniou <pantelis.antoniou@konsulko.com>
Date2016-05-16 19:00 +0200
Subject[PATCH v2 2/5] of: Support hashtable lookups for phandles
Message-ID<rzu26-13S-17@gated-at.bofh.it>
When a device tree contains a lot of phandles, resolving one
takes time because the original method uses a search against
all nodes (not just the ones with phandles).

Signed-off-by: Pantelis Antoniou <pantelis.antoniou@konsulko.com>
---
 drivers/of/base.c       | 41 ++++++++++++++++++++++++++++++++++++++---
 drivers/of/dynamic.c    |  8 ++++++++
 drivers/of/of_private.h | 33 +++++++++++++++++++++++++++++++++
 include/linux/of.h      |  2 ++
 4 files changed, 81 insertions(+), 3 deletions(-)

diff --git a/drivers/of/base.c b/drivers/of/base.c
index 20bbc2f..436a088 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -27,6 +27,7 @@
 #include <linux/slab.h>
 #include <linux/string.h>
 #include <linux/proc_fs.h>
+#include <linux/rhashtable.h>
 
 #include "of_private.h"
 
@@ -41,6 +42,18 @@ static const char *of_stdout_options;
 
 struct kset *of_kset;
 
+const struct rhashtable_params of_phandle_ht_params = {
+	.key_offset = offsetof(struct device_node, phandle), /* base offset */
+	.key_len = sizeof(phandle),
+	.head_offset = offsetof(struct device_node, ht_node),
+	.automatic_shrinking = true,
+};
+
+struct rhashtable *of_phandle_ht;
+
+/* default is false */
+bool of_phandle_ht_is_disabled;
+
 /*
  * Used to protect the of_aliases, to hold off addition of nodes to sysfs.
  * This mutex must be held whenever modifications are being made to the
@@ -162,6 +175,12 @@ int __of_attach_node_post(struct device_node *np)
 	struct property *pp;
 	int rc;
 
+	if (of_phandle_ht_available()) {
+		rc = of_phandle_ht_insert(np);
+		WARN(rc, "insert to phandle hash fail @%s\n",
+				of_node_full_name(np));
+	}
+
 	if (!IS_ENABLED(CONFIG_SYSFS))
 		return 0;
 
@@ -194,6 +213,17 @@ void __init of_core_init(void)
 	struct device_node *np;
 	int ret;
 
+	of_phandle_ht = kzalloc(sizeof(*of_phandle_ht), GFP_KERNEL);
+	if (!of_phandle_ht) {
+		pr_warn("devicetree: Failed to allocate hashtable\n");
+		return;
+	}
+	ret = rhashtable_init(of_phandle_ht, &of_phandle_ht_params);
+	if (ret) {
+		pr_warn("devicetree: Failed to initialize hashtable\n");
+		return;
+	}
+
 	/* Create the kset, and register existing nodes */
 	mutex_lock(&of_mutex);
 	of_kset = kset_create_and_add("devicetree", NULL, firmware_kobj);
@@ -1073,9 +1103,14 @@ struct device_node *of_find_node_by_phandle(phandle handle)
 		return NULL;
 
 	raw_spin_lock_irqsave(&devtree_lock, flags);
-	for_each_of_allnodes(np)
-		if (np->phandle == handle)
-			break;
+	/* when we're ready use the hash table (and not disabled) */
+	if (of_phandle_ht_available() && !of_phandle_ht_is_disabled)
+		np = of_phandle_ht_lookup(handle);
+	else { /* fallback */
+		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/dynamic.c b/drivers/of/dynamic.c
index 34ca783..931b905 100644
--- a/drivers/of/dynamic.c
+++ b/drivers/of/dynamic.c
@@ -11,6 +11,7 @@
 #include <linux/slab.h>
 #include <linux/string.h>
 #include <linux/proc_fs.h>
+#include <linux/rhashtable.h>
 
 #include "of_private.h"
 
@@ -44,6 +45,13 @@ EXPORT_SYMBOL(of_node_put);
 void __of_detach_node_post(struct device_node *np)
 {
 	struct property *pp;
+	int rc;
+
+	if (of_phandle_ht_available()) {
+		rc = of_phandle_ht_remove(np);
+		WARN(rc, "remove from phandle hash fail @%s\n",
+				of_node_full_name(np));
+	}
 
 	if (!IS_ENABLED(CONFIG_SYSFS))
 		return;
diff --git a/drivers/of/of_private.h b/drivers/of/of_private.h
index 10b0342..386ae71 100644
--- a/drivers/of/of_private.h
+++ b/drivers/of/of_private.h
@@ -101,4 +101,37 @@ static inline int of_overlay_init(void)
 }
 #endif
 
+extern const struct rhashtable_params of_phandle_ht_params;
+extern struct rhashtable *of_phandle_ht;
+
+/* for unittest use */
+extern bool of_phandle_ht_is_disabled;
+
+static inline bool of_phandle_ht_available(void)
+{
+	return of_phandle_ht != NULL;
+}
+
+static inline int of_phandle_ht_insert(struct device_node *np)
+{
+	if (!np || !np->phandle)
+		return 0;
+	return rhashtable_insert_fast(of_phandle_ht,
+		&np->ht_node, of_phandle_ht_params);
+}
+
+static inline int of_phandle_ht_remove(struct device_node *np)
+{
+	if (!np || !np->phandle)
+		return 0;
+	return rhashtable_remove_fast(of_phandle_ht,
+		&np->ht_node, of_phandle_ht_params);
+}
+
+static inline struct device_node *of_phandle_ht_lookup(phandle handle)
+{
+	return rhashtable_lookup_fast(of_phandle_ht,
+			&handle, of_phandle_ht_params);
+}
+
 #endif /* _LINUX_OF_PRIVATE_H */
diff --git a/include/linux/of.h b/include/linux/of.h
index 18a8e59..9de9a3f 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/rhashtable.h>
 
 #include <asm/byteorder.h>
 #include <asm/errno.h>
@@ -52,6 +53,7 @@ struct device_node {
 	phandle phandle;
 	const char *full_name;
 	struct fwnode_handle fwnode;
+	struct rhash_head ht_node;
 
 	struct	property *properties;
 	struct	property *deadprops;	/* removed properties */
-- 
1.7.12

[toc] | [next] | [standalone]

#1401727

FromRob Herring <robherring2@gmail.com>
Date2016-05-16 21:40 +0200
Message-ID<rzwwW-2Lc-15@gated-at.bofh.it>
In reply to#1401637
On Mon, May 16, 2016 at 11:52 AM, Pantelis Antoniou
<pantelis.antoniou@konsulko.com> wrote:
> When a device tree contains a lot of phandles, resolving one
> takes time because the original method uses a search against
> all nodes (not just the ones with phandles).
>
> Signed-off-by: Pantelis Antoniou <pantelis.antoniou@konsulko.com>
> ---
>  drivers/of/base.c       | 41 ++++++++++++++++++++++++++++++++++++++---
>  drivers/of/dynamic.c    |  8 ++++++++
>  drivers/of/of_private.h | 33 +++++++++++++++++++++++++++++++++
>  include/linux/of.h      |  2 ++
>  4 files changed, 81 insertions(+), 3 deletions(-)
>
> diff --git a/drivers/of/base.c b/drivers/of/base.c
> index 20bbc2f..436a088 100644
> --- a/drivers/of/base.c
> +++ b/drivers/of/base.c
> @@ -27,6 +27,7 @@
>  #include <linux/slab.h>
>  #include <linux/string.h>
>  #include <linux/proc_fs.h>
> +#include <linux/rhashtable.h>
>
>  #include "of_private.h"
>
> @@ -41,6 +42,18 @@ static const char *of_stdout_options;
>
>  struct kset *of_kset;
>
> +const struct rhashtable_params of_phandle_ht_params = {

static

> +       .key_offset = offsetof(struct device_node, phandle), /* base offset */
> +       .key_len = sizeof(phandle),
> +       .head_offset = offsetof(struct device_node, ht_node),
> +       .automatic_shrinking = true,
> +};
> +
> +struct rhashtable *of_phandle_ht;
> +
> +/* default is false */
> +bool of_phandle_ht_is_disabled;

I think this should go. The unittest alone is not enough reason to keep.

> +
>  /*
>   * Used to protect the of_aliases, to hold off addition of nodes to sysfs.
>   * This mutex must be held whenever modifications are being made to the
> @@ -162,6 +175,12 @@ int __of_attach_node_post(struct device_node *np)
>         struct property *pp;
>         int rc;
>
> +       if (of_phandle_ht_available()) {

This can never be false as this function should only get called after init.

> +               rc = of_phandle_ht_insert(np);
> +               WARN(rc, "insert to phandle hash fail @%s\n",
> +                               of_node_full_name(np));
> +       }
> +
>         if (!IS_ENABLED(CONFIG_SYSFS))
>                 return 0;
>
> @@ -194,6 +213,17 @@ void __init of_core_init(void)
>         struct device_node *np;
>         int ret;
>
> +       of_phandle_ht = kzalloc(sizeof(*of_phandle_ht), GFP_KERNEL);
> +       if (!of_phandle_ht) {
> +               pr_warn("devicetree: Failed to allocate hashtable\n");
> +               return;
> +       }
> +       ret = rhashtable_init(of_phandle_ht, &of_phandle_ht_params);
> +       if (ret) {
> +               pr_warn("devicetree: Failed to initialize hashtable\n");
> +               return;
> +       }
> +
>         /* Create the kset, and register existing nodes */
>         mutex_lock(&of_mutex);
>         of_kset = kset_create_and_add("devicetree", NULL, firmware_kobj);
> @@ -1073,9 +1103,14 @@ struct device_node *of_find_node_by_phandle(phandle handle)
>                 return NULL;
>
>         raw_spin_lock_irqsave(&devtree_lock, flags);
> -       for_each_of_allnodes(np)
> -               if (np->phandle == handle)
> -                       break;
> +       /* when we're ready use the hash table (and not disabled) */
> +       if (of_phandle_ht_available() && !of_phandle_ht_is_disabled)

Just "if (of_phandle_ht)"

> +               np = of_phandle_ht_lookup(handle);
> +       else { /* fallback */
> +               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/dynamic.c b/drivers/of/dynamic.c
> index 34ca783..931b905 100644
> --- a/drivers/of/dynamic.c
> +++ b/drivers/of/dynamic.c
> @@ -11,6 +11,7 @@
>  #include <linux/slab.h>
>  #include <linux/string.h>
>  #include <linux/proc_fs.h>
> +#include <linux/rhashtable.h>
>
>  #include "of_private.h"
>
> @@ -44,6 +45,13 @@ EXPORT_SYMBOL(of_node_put);
>  void __of_detach_node_post(struct device_node *np)
>  {
>         struct property *pp;
> +       int rc;
> +
> +       if (of_phandle_ht_available()) {

Likewise, this can't be false either.

> +               rc = of_phandle_ht_remove(np);
> +               WARN(rc, "remove from phandle hash fail @%s\n",
> +                               of_node_full_name(np));
> +       }
>
>         if (!IS_ENABLED(CONFIG_SYSFS))
>                 return;
> diff --git a/drivers/of/of_private.h b/drivers/of/of_private.h
> index 10b0342..386ae71 100644
> --- a/drivers/of/of_private.h
> +++ b/drivers/of/of_private.h
> @@ -101,4 +101,37 @@ static inline int of_overlay_init(void)
>  }
>  #endif
>
> +extern const struct rhashtable_params of_phandle_ht_params;
> +extern struct rhashtable *of_phandle_ht;
> +
> +/* for unittest use */
> +extern bool of_phandle_ht_is_disabled;
> +
> +static inline bool of_phandle_ht_available(void)
> +{
> +       return of_phandle_ht != NULL;
> +}
> +
> +static inline int of_phandle_ht_insert(struct device_node *np)
> +{
> +       if (!np || !np->phandle)
> +               return 0;
> +       return rhashtable_insert_fast(of_phandle_ht,
> +               &np->ht_node, of_phandle_ht_params);
> +}
> +
> +static inline int of_phandle_ht_remove(struct device_node *np)
> +{
> +       if (!np || !np->phandle)
> +               return 0;
> +       return rhashtable_remove_fast(of_phandle_ht,
> +               &np->ht_node, of_phandle_ht_params);
> +}
> +
> +static inline struct device_node *of_phandle_ht_lookup(phandle handle)
> +{
> +       return rhashtable_lookup_fast(of_phandle_ht,
> +                       &handle, of_phandle_ht_params);
> +}
> +
>  #endif /* _LINUX_OF_PRIVATE_H */
> diff --git a/include/linux/of.h b/include/linux/of.h
> index 18a8e59..9de9a3f 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/rhashtable.h>
>
>  #include <asm/byteorder.h>
>  #include <asm/errno.h>
> @@ -52,6 +53,7 @@ struct device_node {
>         phandle phandle;
>         const char *full_name;
>         struct fwnode_handle fwnode;
> +       struct rhash_head ht_node;

Place next to .phandle as both will be accessed at the same time.

>
>         struct  property *properties;
>         struct  property *deadprops;    /* removed properties */
> --
> 1.7.12
>

[toc] | [prev] | [next] | [standalone]

#1401751

FromPantelis Antoniou <pantelis.antoniou@konsulko.com>
Date2016-05-16 22:20 +0200
Message-ID<rzx9E-3hX-13@gated-at.bofh.it>
In reply to#1401727
Hi Rob,

> On May 16, 2016, at 22:37 , Rob Herring <robherring2@gmail.com> wrote:
> 
> On Mon, May 16, 2016 at 11:52 AM, Pantelis Antoniou
> <pantelis.antoniou@konsulko.com> wrote:
>> When a device tree contains a lot of phandles, resolving one
>> takes time because the original method uses a search against
>> all nodes (not just the ones with phandles).
>> 
>> Signed-off-by: Pantelis Antoniou <pantelis.antoniou@konsulko.com>
>> ---
>> drivers/of/base.c       | 41 ++++++++++++++++++++++++++++++++++++++---
>> drivers/of/dynamic.c    |  8 ++++++++
>> drivers/of/of_private.h | 33 +++++++++++++++++++++++++++++++++
>> include/linux/of.h      |  2 ++
>> 4 files changed, 81 insertions(+), 3 deletions(-)
>> 
>> diff --git a/drivers/of/base.c b/drivers/of/base.c
>> index 20bbc2f..436a088 100644
>> --- a/drivers/of/base.c
>> +++ b/drivers/of/base.c
>> @@ -27,6 +27,7 @@
>> #include <linux/slab.h>
>> #include <linux/string.h>
>> #include <linux/proc_fs.h>
>> +#include <linux/rhashtable.h>
>> 
>> #include "of_private.h"
>> 
>> @@ -41,6 +42,18 @@ static const char *of_stdout_options;
>> 
>> struct kset *of_kset;
>> 
>> +const struct rhashtable_params of_phandle_ht_params = {
> 
> static
> 

No, it won’t work. The rhashtable API requires using this at every call.


>> +       .key_offset = offsetof(struct device_node, phandle), /* base offset */
>> +       .key_len = sizeof(phandle),
>> +       .head_offset = offsetof(struct device_node, ht_node),
>> +       .automatic_shrinking = true,
>> +};
>> +
>> +struct rhashtable *of_phandle_ht;
>> +
>> +/* default is false */
>> +bool of_phandle_ht_is_disabled;
> 
> I think this should go. The unittest alone is not enough reason to keep.
> 

Hmm, OK.

>> +
>> /*
>>  * Used to protect the of_aliases, to hold off addition of nodes to sysfs.
>>  * This mutex must be held whenever modifications are being made to the
>> @@ -162,6 +175,12 @@ int __of_attach_node_post(struct device_node *np)
>>        struct property *pp;
>>        int rc;
>> 
>> +       if (of_phandle_ht_available()) {
> 
> This can never be false as this function should only get called after init.
> 

How about a BUG_ON() just in case something weird is going on?

>> +               rc = of_phandle_ht_insert(np);
>> +               WARN(rc, "insert to phandle hash fail @%s\n",
>> +                               of_node_full_name(np));
>> +       }
>> +
>>        if (!IS_ENABLED(CONFIG_SYSFS))
>>                return 0;
>> 
>> @@ -194,6 +213,17 @@ void __init of_core_init(void)
>>        struct device_node *np;
>>        int ret;
>> 
>> +       of_phandle_ht = kzalloc(sizeof(*of_phandle_ht), GFP_KERNEL);
>> +       if (!of_phandle_ht) {
>> +               pr_warn("devicetree: Failed to allocate hashtable\n");
>> +               return;
>> +       }
>> +       ret = rhashtable_init(of_phandle_ht, &of_phandle_ht_params);
>> +       if (ret) {
>> +               pr_warn("devicetree: Failed to initialize hashtable\n");
>> +               return;
>> +       }
>> +
>>        /* Create the kset, and register existing nodes */
>>        mutex_lock(&of_mutex);
>>        of_kset = kset_create_and_add("devicetree", NULL, firmware_kobj);
>> @@ -1073,9 +1103,14 @@ struct device_node *of_find_node_by_phandle(phandle handle)
>>                return NULL;
>> 
>>        raw_spin_lock_irqsave(&devtree_lock, flags);
>> -       for_each_of_allnodes(np)
>> -               if (np->phandle == handle)
>> -                       break;
>> +       /* when we're ready use the hash table (and not disabled) */
>> +       if (of_phandle_ht_available() && !of_phandle_ht_is_disabled)
> 
> Just "if (of_phandle_ht)”
> 

OK


>> +               np = of_phandle_ht_lookup(handle);
>> +       else { /* fallback */
>> +               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/dynamic.c b/drivers/of/dynamic.c
>> index 34ca783..931b905 100644
>> --- a/drivers/of/dynamic.c
>> +++ b/drivers/of/dynamic.c
>> @@ -11,6 +11,7 @@
>> #include <linux/slab.h>
>> #include <linux/string.h>
>> #include <linux/proc_fs.h>
>> +#include <linux/rhashtable.h>
>> 
>> #include "of_private.h"
>> 
>> @@ -44,6 +45,13 @@ EXPORT_SYMBOL(of_node_put);
>> void __of_detach_node_post(struct device_node *np)
>> {
>>        struct property *pp;
>> +       int rc;
>> +
>> +       if (of_phandle_ht_available()) {
> 
> Likewise, this can't be false either.
> 

OK

>> +               rc = of_phandle_ht_remove(np);
>> +               WARN(rc, "remove from phandle hash fail @%s\n",
>> +                               of_node_full_name(np));
>> +       }
>> 
>>        if (!IS_ENABLED(CONFIG_SYSFS))
>>                return;
>> diff --git a/drivers/of/of_private.h b/drivers/of/of_private.h
>> index 10b0342..386ae71 100644
>> --- a/drivers/of/of_private.h
>> +++ b/drivers/of/of_private.h
>> @@ -101,4 +101,37 @@ static inline int of_overlay_init(void)
>> }
>> #endif
>> 
>> +extern const struct rhashtable_params of_phandle_ht_params;
>> +extern struct rhashtable *of_phandle_ht;
>> +
>> +/* for unittest use */
>> +extern bool of_phandle_ht_is_disabled;
>> +
>> +static inline bool of_phandle_ht_available(void)
>> +{
>> +       return of_phandle_ht != NULL;
>> +}
>> +
>> +static inline int of_phandle_ht_insert(struct device_node *np)
>> +{
>> +       if (!np || !np->phandle)
>> +               return 0;
>> +       return rhashtable_insert_fast(of_phandle_ht,
>> +               &np->ht_node, of_phandle_ht_params);
>> +}
>> +
>> +static inline int of_phandle_ht_remove(struct device_node *np)
>> +{
>> +       if (!np || !np->phandle)
>> +               return 0;
>> +       return rhashtable_remove_fast(of_phandle_ht,
>> +               &np->ht_node, of_phandle_ht_params);
>> +}
>> +
>> +static inline struct device_node *of_phandle_ht_lookup(phandle handle)
>> +{
>> +       return rhashtable_lookup_fast(of_phandle_ht,
>> +                       &handle, of_phandle_ht_params);
>> +}
>> +
>> #endif /* _LINUX_OF_PRIVATE_H */
>> diff --git a/include/linux/of.h b/include/linux/of.h
>> index 18a8e59..9de9a3f 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/rhashtable.h>
>> 
>> #include <asm/byteorder.h>
>> #include <asm/errno.h>
>> @@ -52,6 +53,7 @@ struct device_node {
>>        phandle phandle;
>>        const char *full_name;
>>        struct fwnode_handle fwnode;
>> +       struct rhash_head ht_node;
> 
> Place next to .phandle as both will be accessed at the same time.
> 

OK.

>> 
>>        struct  property *properties;
>>        struct  property *deadprops;    /* removed properties */
>> --
>> 1.7.12

Regards

— Pantelis

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web