linux-kernel - Re: [PATCH] of: use hash based search in of_find_node_by

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Thu, 25 Jan 2018 08:50:18 -0600
From:   Rob Herring <robh+dt@...nel.org>
To:     Chintan Pandya <cpandya@...eaurora.org>
Cc:     Frank Rowand <frowand.list@...il.com>,
        "open list:OPEN FIRMWARE AND FLATTENED DEVICE TREE BINDINGS" 
        <devicetree@...r.kernel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        linux-arm-msm <linux-arm-msm@...r.kernel.org>
Subject: Re: [PATCH] of: use hash based search in of_find_node_by_phandle

On Thu, Jan 25, 2018 at 4:14 AM, Chintan Pandya <cpandya@...eaurora.org> wrote:
> of_find_node_by_phandle() takes a lot of time finding

Got some numbers for what is "a lot of time"?

> 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.

By right side, you mean a deep path?

>
> Implement, device-phandle relation in hash-table so
> that look up can be faster.
>
> Change-Id: I4a2bc7eff6de142e4f91a7bf474893a45e61c128

Run checkpatch.pl

> Signed-off-by: Chintan Pandya <cpandya@...eaurora.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/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;

Always base your patches on the latest -rc at least. This won't apply.

This grows struct device_node for every single node which we recently
worked on to shrink (which is why this won't apply). So I'm now
sensitive to anything that grows it. I'd really prefer something out
of band.

I'd guess that there's really only a few phandle lookups that occur
over and over. The clock controller, interrupt controller, etc. What
if you just had a simple array of previously found nodes for a cache
and of_find_node_by_phandle can check that array first. Probably 8-16
entries would be enough. If that still has too much trashing, you
could also have a lookup count for each entry and expel the least used
first. Or maybe the list_lru would work here.

Rob