Re: [PATCH] of: use hash based search in of_find_node_by_phandle
From: Rob Herring <hidden>
Date: 2018-01-25 14:50:41
Also in:
linux-arm-msm, lkml
On Thu, Jan 25, 2018 at 4:14 AM, Chintan Pandya [off-list ref] 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 <redacted> --- drivers/of/base.c | 9 +++++++-- drivers/of/fdt.c | 18 ++++++++++++++++++ include/linux/of.h | 6 ++++++ 3 files changed, 31 insertions(+), 2 deletions(-)
[...]
quoted hunk ↗ jump to hunk
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 -- To unsubscribe from this list: send the line "unsubscribe devicetree" in the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org More majordomo info at http://vger.kernel.org/majordomo-info.html