From patchwork Thu Jan 25 10:14:07 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chintan Pandya X-Patchwork-Id: 10183841 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 BF1D860383 for ; Thu, 25 Jan 2018 10:14:24 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id AE1792821F for ; Thu, 25 Jan 2018 10:14:24 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A2DAB28797; Thu, 25 Jan 2018 10:14:24 +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=ham 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 1A90E2821F for ; Thu, 25 Jan 2018 10:14:23 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751374AbeAYKOW (ORCPT ); Thu, 25 Jan 2018 05:14:22 -0500 Received: from smtp.codeaurora.org ([198.145.29.96]:52830 "EHLO smtp.codeaurora.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751242AbeAYKOU (ORCPT ); Thu, 25 Jan 2018 05:14:20 -0500 Received: by smtp.codeaurora.org (Postfix, from userid 1000) id 3B21B60A5F; Thu, 25 Jan 2018 10:14:20 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=codeaurora.org; s=default; t=1516875260; bh=nVepSIlc6SghgXJFJ6YSWAlVWKsImf4HSVPaSrpxN4I=; h=From:To:Cc:Subject:Date:From; b=iCy/D7MgpgSoRaqUC0ik7fajOt4S9GAbN/CJRvNKBS/PrvxruWS0N7c7RhrEOuzz/ osCcejg2HRaCXkXvts/XfAWyXGKwVYHgYZN4UBCmstNobms47q3Ab1VR8Un4FTKksM qZXznAVxrw/Ks/jZg6qLUCravQh8CnVzWHE1X1ek= 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 EBA85601D2; Thu, 25 Jan 2018 10:14:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=codeaurora.org; s=default; t=1516875259; bh=nVepSIlc6SghgXJFJ6YSWAlVWKsImf4HSVPaSrpxN4I=; h=From:To:Cc:Subject:Date:From; b=oMgIuWPn610MHbhbXIVwhySE/gH4vK5Q6eBwla3TFDrPOQFR97XcWQ1uS8ec/ul9V Sm6o5S9mYnnWRxGdZdSGsrD9Ia7KZKe6mhEHr0PEXlSMS2Om0mzbCW3MuGf1y8ZkGP 30mIGtPqAn/BcArMiE/mtjPVXeHpnx1NRDB5ZlC0= DMARC-Filter: OpenDMARC Filter v1.3.2 smtp.codeaurora.org EBA85601D2 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] of: use hash based search in of_find_node_by_phandle Date: Thu, 25 Jan 2018 15:44:07 +0530 Message-Id: <1516875247-19599-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 finding 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. Implement, device-phandle relation in hash-table so that look up can be faster. Change-Id: I4a2bc7eff6de142e4f91a7bf474893a45e61c128 Signed-off-by: Chintan Pandya --- drivers/of/base.c | 9 +++++++-- drivers/of/fdt.c | 18 ++++++++++++++++++ include/linux/of.h | 6 ++++++ 3 files changed, 31 insertions(+), 2 deletions(-) diff --git a/drivers/of/base.c b/drivers/of/base.c index a0bccb5..3e06316 100644 --- a/drivers/of/base.c +++ b/drivers/of/base.c @@ -25,6 +25,7 @@ #include #include #include +#include #include #include #include @@ -1099,10 +1100,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 c0914fb..f0e78a7 100644 --- a/drivers/of/fdt.c +++ b/drivers/of/fdt.c @@ -31,6 +31,10 @@ #include /* for COMMAND_LINE_SIZE */ #include +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 @@ -227,6 +231,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 299aeb1..5b3f4f1 100644 --- a/include/linux/of.h +++ b/include/linux/of.h @@ -25,6 +25,7 @@ #include #include #include +#include #include #include @@ -61,6 +62,7 @@ struct device_node { struct kobject kobj; unsigned long _flags; void *data; + struct hlist_node hash; #if defined(CONFIG_SPARC) const char *path_component_name; unsigned int unique_id; @@ -68,6 +70,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;