Re: [PATCH v2] of: cache phandle nodes to reduce cost of of_find_node_by_phandle()

From: Frank Rowand
Date: Mon Feb 12 2018 - 15:33:15 EST

Next message: Laura Abbott: "Re: [PATCH] staging: android: ion: Restrict cache maintenance to dma mapped memory"
Previous message: Mathieu Poirier: "[PATCH 2/3] perf util: Use target->per_thread and target->system_wide flags"
In reply to: Chintan Pandya: "Re: [PATCH v2] of: cache phandle nodes to reduce cost of of_find_node_by_phandle()"
Next in thread: Rob Herring: "Re: [PATCH v2] of: cache phandle nodes to reduce cost of of_find_node_by_phandle()"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

On 02/12/18 02:51, Chintan Pandya wrote:
>
>
> On 2/12/2018 11:57 AM, frowand.list@xxxxxxxxx wrote:
>> From: Frank Rowand <frank.rowand@xxxxxxxx>
>>
>> Create a cache of the nodes that contain a phandle property.Â Use this
>> cache to find the node for a given phandle value instead of scanning
>> the devicetree to find the node.Â If the phandle value is not found
>> in the cache, of_find_node_by_phandle() will fall back to the tree
>> scan algorithm.
>>
>> The cache is initialized in of_core_init().
>>
>> The cache is freed via a late_initcall_sync() if modules are not
>> enabled.
>>
>> Signed-off-by: Frank Rowand <frank.rowand@xxxxxxxx>
>> ---
>>
>> Changes since v1:
>> ÂÂ - change short description from
>> ÂÂÂÂ of: cache phandle nodes to reduce cost of of_find_node_by_phandle()
>> ÂÂ - rebase on v4.16-rc1
>> ÂÂ - reorder new functions in base.c to avoid forward declaration
>> ÂÂ - add locking around kfree(phandle_cache) for memory ordering
>> ÂÂ - add explicit check for non-null of phandle_cache in
>> ÂÂÂÂ of_find_node_by_phandle().Â There is already a check for !handle,
>> ÂÂÂÂ which prevents accessing a null phandle_cache, but that dependency
>> ÂÂÂÂ is not obvious, so this check makes it more apparent.
>> ÂÂ - do not free phandle_cache if modules are enabled, so that
>> ÂÂÂÂ cached phandles will be available when modules are loaded
>
> Most of the gain from this cache will already be achieved for kernel
> init calls. As the discussion started with boot_time_gain vs
> mem_overhead, we seem to be loosing here as mem_overhead will be for
> eternal for small savings. We can live without this, IMO.

Please line wrap your emails so I don't have to.

I was addressing the other maintainer's concern. This was an attempt
to free the memory if modules are not a factor, otherwise provide the
reduced overhead for drivers that are loaded as modules.

I won't bike shed over this.

The memory cost is quite small relative to the boot time reduction gain
For systems with little boot time speedup, the memory used is especially
small. For systems with larger boot time speedup, the memory used is still
not large, though it is "forever" if modules are configured on. If modules
are configured on, then the system designer has already decided that they
are willing to use more memory to gain the module functionality.

If modules are not configured on, then the cache is freed as late as
possible using the init functions. There are some calls to
of_find_node_by_phandle() after this point (on the system that I tested
on), but those are in asynchronous threads that are not preventing
the boot from completing (and thus not an issue for those who are
tuning for minimal boot time).

So the question for when modules are configured on comes down to: which
is more important, the reduced phandle lookup overhead provided by the
cache or the additional memory used by the cache? My preference is to
just free the memory instead of providing the phandle access overhead
reduction for a theoretical case of lots of modular drivers (though the
patch implements the opposite). If a system with lots of modular drivers
demonstrates a phandle lookup overhead issue then the implementation can
be revisited.

Whichever way Rob wants to answer this question is fine with me, I
consider it a theoretical non-issue at the moment.

>>
>> Â drivers/of/base.cÂÂÂÂÂÂ | 93 ++++++++++++++++++++++++++++++++++++++++++++++---
>> Â drivers/of/of_private.h |Â 5 +++
>> Â drivers/of/resolver.cÂÂ | 21 -----------
>> Â 3 files changed, 94 insertions(+), 25 deletions(-)
>>
>> diff --git a/drivers/of/base.c b/drivers/of/base.c
>> index ad28de96e13f..b3597c250837 100644
>> --- a/drivers/of/base.c
>> +++ b/drivers/of/base.c
>> @@ -91,10 +91,88 @@ int __weak of_node_to_nid(struct device_node *np)
>> Â }
>> Â #endif
>> Â +static struct device_node **phandle_cache;
>> +static u32 max_phandle_cache;
>> +
>> +phandle live_tree_max_phandle(void)
>> +{
>> +ÂÂÂ struct device_node *node;
>> +ÂÂÂ phandle max_phandle;
>> +ÂÂÂ unsigned long flags;
>> +
>> +ÂÂÂ raw_spin_lock_irqsave(&devtree_lock, flags);
>> +
>> +ÂÂÂ max_phandle = 0;
>> +ÂÂÂ for_each_of_allnodes(node) {
>> +ÂÂÂÂÂÂÂ if (node->phandle != OF_PHANDLE_ILLEGAL &&
>> +ÂÂÂÂÂÂÂÂÂÂÂ node->phandle > max_phandle)
>> +ÂÂÂÂÂÂÂÂÂÂÂ max_phandle = node->phandle;
>> +ÂÂÂÂÂÂÂ }
>
> This closing curly bracket needs proper indentation.

Thanks, will fix.

>> +
>> +ÂÂÂ raw_spin_unlock_irqrestore(&devtree_lock, flags);
>> +
>> +ÂÂÂ return max_phandle;
>> +}
>> +
>> +static void of_populate_phandle_cache(void)
>> +{
>> +ÂÂÂ unsigned long flags;
>> +ÂÂÂ phandle max_phandle;
>> +ÂÂÂ u32 nodes = 0;
>> +ÂÂÂ struct device_node *np;
>> +
>> +ÂÂÂ if (phandle_cache)
>> +ÂÂÂÂÂÂÂ return;
>> +
>> +ÂÂÂ max_phandle = live_tree_max_phandle();
>> +
>> +ÂÂÂ raw_spin_lock_irqsave(&devtree_lock, flags);
>> +
>> +ÂÂÂ for_each_of_allnodes(np)
>
> This is 1ms call.
>
>> +ÂÂÂÂÂÂÂ nodes++;
>
> We can calculate total nodes in live_tree_max_phandle to save 1ms.>
>> +
>> +ÂÂÂ /* sanity cap for malformed tree */
>> +ÂÂÂ if (max_phandle > nodes)
>> +ÂÂÂÂÂÂÂ max_phandle = nodes;
>
> Or rather, we can take this entire thing to live_tree_max_phandle().

See my answer to Rasmus' review comments to see why I'll consider this
in the future, but not for this patch series.

>> +
>> +ÂÂÂ phandle_cache = kzalloc((max_phandle + 1) * sizeof(*phandle_cache),
>> +ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ GFP_ATOMIC);
>> +
>> +ÂÂÂ for_each_of_allnodes(np)
>> +ÂÂÂÂÂÂÂ if (np->phandle != OF_PHANDLE_ILLEGALÂ &&
>> +ÂÂÂÂÂÂÂÂÂÂÂ np->phandle <= max_phandle &&
>> +ÂÂÂÂÂÂÂÂÂÂÂ np->phandle)
>> +ÂÂÂÂÂÂÂÂÂÂÂ phandle_cache[np->phandle] = np;
>> +
>> +ÂÂÂ max_phandle_cache = max_phandle;
>> +
>> +ÂÂÂ raw_spin_unlock_irqrestore(&devtree_lock, flags);
>> +}
>> +
>> +#ifndef CONFIG_MODULES
>> +static int __init of_free_phandle_cache(void)
>> +{
>> +ÂÂÂ unsigned long flags;
>> +
>> +ÂÂÂ raw_spin_lock_irqsave(&devtree_lock, flags);
>> +
>> +ÂÂÂ max_phandle_cache = 0;
>> +ÂÂÂ kfree(phandle_cache);
>> +ÂÂÂ phandle_cache = NULL;
>> +
>> +ÂÂÂ raw_spin_unlock_irqrestore(&devtree_lock, flags);
>> +
>> +ÂÂÂ return 0;
>> +}
>> +late_initcall_sync(of_free_phandle_cache);
>> +#endif
>> +
>> Â void __init of_core_init(void)
>> Â {
>> ÂÂÂÂÂ struct device_node *np;
>> Â +ÂÂÂ of_populate_phandle_cache();
>> +
>> ÂÂÂÂÂ /* Create the kset, and register existing nodes */
>> ÂÂÂÂÂ mutex_lock(&of_mutex);
>> ÂÂÂÂÂ of_kset = kset_create_and_add("devicetree", NULL, firmware_kobj);
>> @@ -1021,16 +1099,23 @@ int of_modalias_node(struct device_node *node, char *modalias, int len)
>> ÂÂ */
>> Â struct device_node *of_find_node_by_phandle(phandle handle)
>> Â {
>> -ÂÂÂ struct device_node *np;
>> +ÂÂÂ struct device_node *np = NULL;
>> ÂÂÂÂÂ unsigned long flags;
>> Â ÂÂÂÂÂ if (!handle)
>> ÂÂÂÂÂÂÂÂÂ return NULL;
>> Â ÂÂÂÂÂ raw_spin_lock_irqsave(&devtree_lock, flags);
>> -ÂÂÂ for_each_of_allnodes(np)
>> -ÂÂÂÂÂÂÂ if (np->phandle == handle)
>> -ÂÂÂÂÂÂÂÂÂÂÂ break;
>> +
>> +ÂÂÂ if (phandle_cache && handle <= max_phandle_cache)
>> +ÂÂÂÂÂÂÂ np = phandle_cache[handle];
>> +
>> +ÂÂÂ if (!np || np->phandle != handle) {
>> +ÂÂÂÂÂÂÂ 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/of_private.h b/drivers/of/of_private.h
>> index 0c609e7d0334..18e03c9d4b55 100644
>> --- a/drivers/of/of_private.h
>> +++ b/drivers/of/of_private.h
>> @@ -131,6 +131,11 @@ extern void __of_update_property_sysfs(struct device_node *np,
>> Â extern void __of_sysfs_remove_bin_file(struct device_node *np,
>> ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ struct property *prop);
>> Â +/* illegal phandle value (set when unresolved) */
>> +#define OF_PHANDLE_ILLEGALÂÂÂ 0xdeadbeef
>> +
>> +extern phandle live_tree_max_phandle(void);
>
> Why do we need this to be public API ? It was not previously and no
> good use-case for this now.

It is not public. It is private ("of_private.h") to the devicetree
code. It is used by the overlay code (look at top of tree, not
an old kernel).

>> +
>> Â /* iterators for transactions, used for overlays */
>> Â /* forward iterator */
>> Â #define for_each_transaction_entry(_oft, _te) \
>> diff --git a/drivers/of/resolver.c b/drivers/of/resolver.c
>> index 740d19bde601..a7580c24737a 100644
>> --- a/drivers/of/resolver.c
>> +++ b/drivers/of/resolver.c
>> @@ -19,27 +19,6 @@
>> Â Â #include "of_private.h"
>> Â -/* illegal phandle value (set when unresolved) */
>> -#define OF_PHANDLE_ILLEGALÂÂÂ 0xdeadbeef
>> -
>> -static phandle live_tree_max_phandle(void)
>> -{
>> -ÂÂÂ struct device_node *node;
>> -ÂÂÂ phandle phandle;
>> -ÂÂÂ unsigned long flags;
>> -
>> -ÂÂÂ raw_spin_lock_irqsave(&devtree_lock, flags);
>> -ÂÂÂ phandle = 0;
>> -ÂÂÂ for_each_of_allnodes(node) {
>> -ÂÂÂÂÂÂÂ if (node->phandle != OF_PHANDLE_ILLEGAL &&
>> -ÂÂÂÂÂÂÂÂÂÂÂÂÂÂÂ node->phandle > phandle)
>> -ÂÂÂÂÂÂÂÂÂÂÂ phandle = node->phandle;
>> -ÂÂÂ }
>> -ÂÂÂ raw_spin_unlock_irqrestore(&devtree_lock, flags);
>> -
>> -ÂÂÂ return phandle;
>> -}
>> -
>> Â static void adjust_overlay_phandles(struct device_node *overlay,
>> ÂÂÂÂÂÂÂÂÂ int phandle_delta)
>> Â {
>>
>
> Chintan

Next message: Laura Abbott: "Re: [PATCH] staging: android: ion: Restrict cache maintenance to dma mapped memory"
Previous message: Mathieu Poirier: "[PATCH 2/3] perf util: Use target->per_thread and target->system_wide flags"
In reply to: Chintan Pandya: "Re: [PATCH v2] of: cache phandle nodes to reduce cost of of_find_node_by_phandle()"
Next in thread: Rob Herring: "Re: [PATCH v2] of: cache phandle nodes to reduce cost of of_find_node_by_phandle()"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]