Hi Frank, Linux v4.17 and later will no longer boot on a G3 PowerMac. The boot hangs very early, before any video driver loads. Stan and I were able to bisect the regression between v4.16 and v4.17 and arrived at commit 0b3ce78e90fc ("of: cache phandle nodes to reduce cost of of_find_node_by_phandle()"). I don't see any obvious bug in 0b3ce78e90fc or b9952b5218ad. But if you revert these from v4.18 (which is also affected) that certainly resolves the issue. I did see this in the kernel messages: Duplicate name in PowerPC,750, renamed to "l2-cache#1" Duplicate name in mac-io, renamed to "ide#1" Duplicate name in ide#1, renamed to "atapi-disk#1" Duplicate name in multifunc-device, renamed to "pci1799,1#1" No idea whether that's relevant; I haven't done any further investigation. Complete dmesg output is attached. Please let me know if there's any more information you need to help find the bug. Thanks. -- On Sun, 4 Mar 2018, frowand.list@gmail.com wrote: > From: Frank Rowand > > 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. > > If the devicetree is created by the dtc compiler, with all phandle > property values auto generated, then the size required by the cache > could be 4 * (1 + number of phandles) bytes. This results in an O(1) > node lookup cost for a given phandle value. Due to a concern that the > phandle property values might not be consistent with what is generated > by the dtc compiler, a mask has been added to the cache lookup algorithm. > To maintain the O(1) node lookup cost, the size of the cache has been > increased by rounding the number of entries up to the next power of > two. > > The overhead of finding the devicetree node containing a given phandle > value has been noted by several people in the recent past, in some cases > with a patch to add a hashed index of devicetree nodes, based on the > phandle value of the node. One concern with this approach is the extra > space added to each node. This patch takes advantage of the phandle > property values auto generated by the dtc compiler, which begin with > one and monotonically increase by one, resulting in a range of 1..n > for n phandle values. This implementation should also provide a good > reduction of overhead for any range of phandle values that are mostly > in a monotonic range. > > Performance measurements by Chintan Pandya > of several implementations of patches that are similar to this one > suggest an expected reduction of boot time by ~400ms for his test > system. If the cache size was decreased to 64 entries, the boot > time was reduced by ~340 ms. The measurements were on a 4.9.73 kernel > for arch/arm64/boot/dts/qcom/sda670-mtp.dts, contains 2371 nodes and > 814 phandle values. > > Reported-by: Chintan Pandya > Signed-off-by: Frank Rowand > --- > > Changes since v3: > - of_populate_phandle_cache(): add check for failed memory allocation > > Changes since v2: > - add mask to calculation of phandle cache entry > - which results in better overhead reduction for devicetrees with > phandle properties not allocated in the monotonically increasing > range of 1..n > - due to mask, number of entries in cache potentially increased to > next power of two > - minor fixes as suggested by reviewers > - no longer using live_tree_max_phandle() so do not move it from > drivers/of/resolver.c to drivers/of/base.c > > 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 > > drivers/of/base.c | 86 ++++++++++++++++++++++++++++++++++++++++++++++--- > drivers/of/of_private.h | 3 ++ > drivers/of/resolver.c | 3 -- > 3 files changed, 85 insertions(+), 7 deletions(-) > > diff --git a/drivers/of/base.c b/drivers/of/base.c > index ad28de96e13f..e71d157d7149 100644 > --- a/drivers/of/base.c > +++ b/drivers/of/base.c > @@ -91,10 +91,72 @@ int __weak of_node_to_nid(struct device_node *np) > } > #endif > > +static struct device_node **phandle_cache; > +static u32 phandle_cache_mask; > + > +/* > + * Assumptions behind phandle_cache implementation: > + * - phandle property values are in a contiguous range of 1..n > + * > + * If the assumptions do not hold, then > + * - the phandle lookup overhead reduction provided by the cache > + * will likely be less > + */ > +static void of_populate_phandle_cache(void) > +{ > + unsigned long flags; > + u32 cache_entries; > + struct device_node *np; > + u32 phandles = 0; > + > + raw_spin_lock_irqsave(&devtree_lock, flags); > + > + kfree(phandle_cache); > + phandle_cache = NULL; > + > + for_each_of_allnodes(np) > + if (np->phandle && np->phandle != OF_PHANDLE_ILLEGAL) > + phandles++; > + > + cache_entries = roundup_pow_of_two(phandles); > + phandle_cache_mask = cache_entries - 1; > + > + phandle_cache = kcalloc(cache_entries, sizeof(*phandle_cache), > + GFP_ATOMIC); > + if (!phandle_cache) > + goto out; > + > + for_each_of_allnodes(np) > + if (np->phandle && np->phandle != OF_PHANDLE_ILLEGAL) > + phandle_cache[np->phandle & phandle_cache_mask] = np; > + > +out: > + 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); > + > + 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 +1083,32 @@ 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; > + phandle masked_handle; > > if (!handle) > return NULL; > > raw_spin_lock_irqsave(&devtree_lock, flags); > - for_each_of_allnodes(np) > - if (np->phandle == handle) > - break; > + > + masked_handle = handle & phandle_cache_mask; > + > + if (phandle_cache) { > + if (phandle_cache[masked_handle] && > + handle == phandle_cache[masked_handle]->phandle) > + np = phandle_cache[masked_handle]; > + } > + > + if (!np) { > + for_each_of_allnodes(np) > + if (np->phandle == handle) { > + if (phandle_cache) > + phandle_cache[masked_handle] = np; > + 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..fa70650136b4 100644 > --- a/drivers/of/of_private.h > +++ b/drivers/of/of_private.h > @@ -131,6 +131,9 @@ 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 > + > /* 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..b2ca8185c8c6 100644 > --- a/drivers/of/resolver.c > +++ b/drivers/of/resolver.c > @@ -19,9 +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; >