From patchwork Mon Feb 12 06:27:48 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Frank Rowand X-Patchwork-Id: 871896 Return-Path: X-Original-To: incoming-dt@patchwork.ozlabs.org Delivered-To: patchwork-incoming-dt@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=none (mailfrom) smtp.mailfrom=vger.kernel.org (client-ip=209.132.180.67; helo=vger.kernel.org; envelope-from=devicetree-owner@vger.kernel.org; receiver=) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="JGc17SO3"; dkim-atps=neutral Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 3zfwjN5s7Tz9t3x for ; Mon, 12 Feb 2018 17:28:40 +1100 (AEDT) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932442AbeBLG2i (ORCPT ); Mon, 12 Feb 2018 01:28:38 -0500 Received: from mail-pg0-f65.google.com ([74.125.83.65]:35256 "EHLO mail-pg0-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932396AbeBLG2h (ORCPT ); Mon, 12 Feb 2018 01:28:37 -0500 Received: by mail-pg0-f65.google.com with SMTP id l131so1380508pga.2; Sun, 11 Feb 2018 22:28:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id; bh=jsQtOuSfP1EckA+EMUZvwNyumqxWDeRl/wXfBCNMQNY=; b=JGc17SO3gniJio5l75qGKIP7YmG9f80owFzigiWEWw5EtLzusX9yGeiKiqMZCvYJ40 JySRixfhuDpo1lZeB0U1GjHUvDp7nqR3co5Zvoo4lDITkf1JGwhZd8/vzmIRbwM8vvFB URLSSza493+0LLadF4ULLBYA5PBJABKAu+tavLWsQYe3OsXCs0VowSH3I6u3v9YODzGM Pj/5g70vcGMn+HPE99nhKHhzA8ZaJsARFaTTy3Bix5JXbppDsDcICO7aFao8Mx6rXrw5 MnTe+8WVFJ4VOAcgEIeoMziojjV3nsdxxNqAVYCDAJkhnx8Mjut16Jteq8Stq43mbhfI fKBQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id; bh=jsQtOuSfP1EckA+EMUZvwNyumqxWDeRl/wXfBCNMQNY=; b=Ws3dVcLonFLKIjDMDXg9B7pnKtNQXlB8tKxtOw3t0VF22WAkaHBzR3LvoDZqU/i5Jt f1QgGy/0sNskLjQq3BexpJgPd1KNuvPgNKqT8Rcit6+5jBJTRGilleI7OqeJM30KWk4f gZKTMUd4h5TSzpMyhPCQsU2nZpVYvpH5KAHvRgDRIDwM1dwDnSNGoTIIIoytRw5a6tdC Ow7IwmlKDWYygASWEMHzOBgSuwq4HMnYxgQjl4yi5wFgBl6E2ArMEc8jer/7vE89a38P 8Urn47C6o4qPC5MvkmztFRvWdtkkEI65OJFSBxeHB+BELt93oXksNCDz431V78YZQPqw GdhQ== X-Gm-Message-State: APf1xPCCT3GUxOk64UgLF0si+sFJjTC2RVIkaIXGD7W4J/GEDTPSDFi8 VxrmGd+3gypjrBtx/gEAzN8= X-Google-Smtp-Source: AH8x224z+QPCgeEpUyIm1A0ZwYnYZ/mKKkeU6OKmTEu+m7nA7P6BrEXZ465i0lmMKQ4kSbd2sxSZeg== X-Received: by 10.99.120.66 with SMTP id t63mr8738892pgc.111.1518416917167; Sun, 11 Feb 2018 22:28:37 -0800 (PST) Received: from localhost.localdomain (c-73-93-215-6.hsd1.ca.comcast.net. [73.93.215.6]) by smtp.gmail.com with ESMTPSA id 63sm20462572pgi.71.2018.02.11.22.28.35 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sun, 11 Feb 2018 22:28:36 -0800 (PST) From: frowand.list@gmail.com To: Rob Herring , cpandya@codeaurora.org Cc: devicetree@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH v2] of: cache phandle nodes to reduce cost of of_find_node_by_phandle() Date: Sun, 11 Feb 2018 22:27:48 -0800 Message-Id: <1518416868-8804-1-git-send-email-frowand.list@gmail.com> X-Mailer: git-send-email 1.9.1 Sender: devicetree-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: devicetree@vger.kernel.org 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. Signed-off-by: Frank Rowand --- 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 | 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; + } + + 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) + nodes++; + + /* sanity cap for malformed tree */ + if (max_phandle > nodes) + max_phandle = nodes; + + 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); + /* 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) {