Received: by 10.223.176.46 with SMTP id f43csp1930662wra; Thu, 25 Jan 2018 02:15:01 -0800 (PST) X-Google-Smtp-Source: AH8x225lvn0VnRT89zGSm3kbiDATCEhe9MCKo/nOD63o91F1P7a8cd7Ydejf35eQJOQXwm8GVhA+ X-Received: by 10.98.28.209 with SMTP id c200mr6101941pfc.24.1516875301478; Thu, 25 Jan 2018 02:15:01 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1516875301; cv=none; d=google.com; s=arc-20160816; b=JOJynqi3LG8ZuZ9xcy/vla74yL93/bkoEETNY3MbaoIDBKXA+mDLhX52hzCUi4MPZx Pf58BJ5JQBUkfG/6qP99D/ZIRC7JVraHRGM4I0PepZWkr1GuRAClh/lwHunq6iZBqxjQ mNqDuusP+Y/9K49fW9E0tOJyLiB0730n4k1kqEsX5QGozrKinMpfVpw/vTfoi4aEXXhL QroScyiQVqHnOsTN/TrGd0LbW6welapzQ8ckQpNhzafSsx2xFvaQjF8TfUQFHOQOYnho C0gO402TONveWxMInR7dcvfdy8N2h5p6xuVC8SLKQkDQfPuGxfxOLmZkK+jflKGr+dsJ lgYQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:message-id:date:subject:cc:to:from :dmarc-filter:dkim-signature:dkim-signature :arc-authentication-results; bh=sAliBZjnpEZBP5rP/HfoGPZQPh4BMoNQX5Bqsl9w/D4=; b=Z6kwDIZhsS9GregjJcgOKyb/AQBZzts8NJauOKDQbs3IYs7WegmSrsKVT8re5DKAdz QYo8l3fFO7AdYxt+MMgdSXubZj0djUrL4gWKOfyyztOpZFMXXBsj5kiD40NW+uc/S1rn KEDEc4HwiJ/OwEZW2xNwDSPM5pEq05HvTbL1RzYgQj5qw+v+gv08JhWrMeuP2jOhakDI 2eOodNbqlnr7lBquhq+pQE6P3uXDeYIeqLpbLOCmtebKhHmkr8UmkNrlYO5xKFbTLQA3 bZEm38GtJbGaS2Fag89Z+l7n2BwPYGetdaK243hr0uEMdO0umtbRRv0LB+BBlA508100 k0aA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@codeaurora.org header.s=default header.b=iCy/D7Mg; dkim=pass header.i=@codeaurora.org header.s=default header.b=oMgIuWPn; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id w8-v6si1771789plk.597.2018.01.25.02.14.46; Thu, 25 Jan 2018 02:15:01 -0800 (PST) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@codeaurora.org header.s=default header.b=iCy/D7Mg; dkim=pass header.i=@codeaurora.org header.s=default header.b=oMgIuWPn; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751475AbeAYKOX (ORCPT + 99 others); Thu, 25 Jan 2018 05:14:23 -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= X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on pdx-caf-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.8 required=2.0 tests=ALL_TRUSTED,BAYES_00, DKIM_SIGNED,T_DKIM_INVALID autolearn=no autolearn_force=no version=3.4.0 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-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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; -- The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project