From patchwork Fri Jan 26 08:31:36 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chintan Pandya X-Patchwork-Id: 10185301 X-Patchwork-Delegate: agross@codeaurora.org Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id E7CA160383 for ; Fri, 26 Jan 2018 08:32:19 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id D3602290F6 for ; Fri, 26 Jan 2018 08:32:19 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id C45F3290FA; Fri, 26 Jan 2018 08:32:19 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=unavailable version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 3E873290F6 for ; Fri, 26 Jan 2018 08:32:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752388AbeAZIcF (ORCPT ); Fri, 26 Jan 2018 03:32:05 -0500 Received: from smtp.codeaurora.org ([198.145.29.96]:50886 "EHLO smtp.codeaurora.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752132AbeAZIcD (ORCPT ); Fri, 26 Jan 2018 03:32:03 -0500 Received: by smtp.codeaurora.org (Postfix, from userid 1000) id EF8D36028B; Fri, 26 Jan 2018 08:32:02 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=codeaurora.org; s=default; t=1516955523; bh=ze0BBZEdvr6W+chaBAz9QWwvog24by1qNxMI8VArpSI=; h=From:To:Cc:Subject:Date:From; b=hFATE4tx/imIda1p9H0XoCgvWZtg/90urM8eK76NgxBoHAlclAcDzR2wXMj2jT0jk 8QF8WGLeZixA4IUtjhKWwaLgwF9dEEAICACrS29La55+8bp0P9T4j8LdEQC76Y/MuK MjyqpsWpjaxOCCs/0XRRdfN4xn0/dhOgLE/Ff2sg= Received: from cpandya-linux.qualcomm.com (blr-c-bdr-fw-01_globalnat_allzones-outside.qualcomm.com [103.229.19.19]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (128/128 bits)) (No client certificate requested) (Authenticated sender: cpandya@smtp.codeaurora.org) by smtp.codeaurora.org (Postfix) with ESMTPSA id 485916028B; Fri, 26 Jan 2018 08:32:00 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=codeaurora.org; s=default; t=1516955522; bh=ze0BBZEdvr6W+chaBAz9QWwvog24by1qNxMI8VArpSI=; h=From:To:Cc:Subject:Date:From; b=R1CpVehmEUfUIYVZbsiLaV4guKSZRrmb7SdVhxlkGJ9US33eJ43EG8gQErHLjf00L NLHvivQHXA0wIEcwnyxFA4srSglycmhs/DjzkSZNFM4RZMmS1MxIcp2fisA14r8aJy d8RhFCbtu9C2P+LWc7KEgZfjk415OrSQwinjrb/s= DMARC-Filter: OpenDMARC Filter v1.3.2 smtp.codeaurora.org 485916028B Authentication-Results: pdx-caf-mail.web.codeaurora.org; dmarc=none (p=none dis=none) header.from=codeaurora.org Authentication-Results: pdx-caf-mail.web.codeaurora.org; spf=none smtp.mailfrom=cpandya@codeaurora.org From: Chintan Pandya To: robh+dt@kernel.org, frowand.list@gmail.com, devicetree@vger.kernel.org Cc: linux-kernel@vger.kernel.org, linux-arm-msm@vger.kernel.org, Chintan Pandya Subject: [PATCH v2] of: use hash based search in of_find_node_by_phandle Date: Fri, 26 Jan 2018 14:01:36 +0530 Message-Id: <1516955496-17236-1-git-send-email-cpandya@codeaurora.org> X-Mailer: git-send-email 1.9.1 Sender: linux-arm-msm-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-arm-msm@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP of_find_node_by_phandle() takes a lot of time (1ms per call) to find right node when your intended device is too deeper in the fdt. Reason is, we search for each device serially in the fdt. See this, struct device_node *__of_find_all_nodes(struct device_node *prev) { struct device_node *np; if (!prev) { np = of_root; } else if (prev->child) { np = prev->child; } else { /* Walk back up looking for a sibling, or the end of the structure */ np = prev; while (np->parent && !np->sibling) np = np->parent; np = np->sibling; /* Might be null at the end of the tree */ } return np; } #define for_each_of_allnodes_from(from, dn) \ for (dn = __of_find_all_nodes(from); dn; dn = __of_find_all_nodes(dn)) #define for_each_of_allnodes(dn) for_each_of_allnodes_from(NULL, dn) Implement, device-phandle relation in hash-table so that look up can be faster, irrespective of where my device is defined in the DT. There are ~6.7k calls to of_find_node_by_phandle() and total improvement observed during boot is 400ms. Signed-off-by: Chintan Pandya --- drivers/of/base.c | 8 ++++++-- drivers/of/fdt.c | 18 ++++++++++++++++++ include/linux/of.h | 6 ++++++ 3 files changed, 30 insertions(+), 2 deletions(-) diff --git a/drivers/of/base.c b/drivers/of/base.c index 26618ba..bfbfa99 100644 --- a/drivers/of/base.c +++ b/drivers/of/base.c @@ -1005,10 +1005,14 @@ struct device_node *of_find_node_by_phandle(phandle handle) if (!handle) return NULL; - raw_spin_lock_irqsave(&devtree_lock, flags); - for_each_of_allnodes(np) + spin_lock(&dt_hash_spinlock); + hash_for_each_possible(dt_hash_table, np, hash, handle) if (np->phandle == handle) break; + + spin_unlock(&dt_hash_spinlock); + + raw_spin_lock_irqsave(&devtree_lock, flags); of_node_get(np); raw_spin_unlock_irqrestore(&devtree_lock, flags); return np; diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c index 4675e5a..62a9a4c 100644 --- a/drivers/of/fdt.c +++ b/drivers/of/fdt.c @@ -33,6 +33,10 @@ #include "of_private.h" +static bool dt_hash_needs_init = true; +DECLARE_HASHTABLE(dt_hash_table, DT_HASH_BITS); +DEFINE_SPINLOCK(dt_hash_spinlock); + /* * of_fdt_limit_memory - limit the number of regions in the /memory node * @limit: maximum entries @@ -242,6 +246,20 @@ static void populate_properties(const void *blob, pprev = &pp->next; } + /* + * In 'dryrun = true' cases, np is some non-NULL junk. So, protect + * against those cases. + */ + if (!dryrun && np->phandle) { + spin_lock(&dt_hash_spinlock); + if (dt_hash_needs_init) { + dt_hash_needs_init = false; + hash_init(dt_hash_table); + } + hash_add(dt_hash_table, &np->hash, np->phandle); + spin_unlock(&dt_hash_spinlock); + } + /* With version 0x10 we may not have the name property, * recreate it here from the unit name if absent */ diff --git a/include/linux/of.h b/include/linux/of.h index d3dea1d..2e3ba84 100644 --- a/include/linux/of.h +++ b/include/linux/of.h @@ -25,6 +25,7 @@ #include #include #include +#include #include #include @@ -69,6 +70,7 @@ struct device_node { #endif unsigned long _flags; void *data; + struct hlist_node hash; #if defined(CONFIG_SPARC) const char *path_component_name; unsigned int unique_id; @@ -76,6 +78,10 @@ struct device_node { #endif }; +#define DT_HASH_BITS 6 +extern DECLARE_HASHTABLE(dt_hash_table, DT_HASH_BITS); +extern spinlock_t dt_hash_spinlock; + #define MAX_PHANDLE_ARGS 16 struct of_phandle_args { struct device_node *np;