Received: by 10.223.176.46 with SMTP id f43csp1199083wra; Fri, 26 Jan 2018 13:40:39 -0800 (PST) X-Google-Smtp-Source: AH8x224JonsLWdux+sYsrfjLDixa59/1PdhgJOxkiSAdk6Orl6abb8B39JchOCr9mbfo5tfENVTg X-Received: by 2002:a17:902:714c:: with SMTP id u12-v6mr15909451plm.1.1517002839735; Fri, 26 Jan 2018 13:40:39 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1517002839; cv=none; d=google.com; s=arc-20160816; b=fYaZiv9R2vgNWuG0/Y9tLxmUyUC4foOn+7AKPh+7HuvqSzeKllsAKmMpzWqQGHCLtD YGyQ559SX8OkEDeSzLD6O7HTsFJ78r1eaHlCs71NscGtR+VZqasCZH9QssQ3BmIwyMM3 wafDzXB8Dj2UDKK2Z3dnKCuRxs71qzmW2LzM0k8FKLPYg7opiXeGeeD33fgxWgxr541+ s2lDD9jnth7oHj8gSb1M8uX49PKlglyVrP0LW/WjtN6asMEE/Zqxw6kTSjFx+P3GOmiN vpHL9rX7RSPTcANpdtb9K07DNAyGawWr/SNkXOb+3w+h3CpNc5gzcZgniHhYMVECcnip nhBg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:user-agent:in-reply-to :content-disposition:mime-version:references:message-id:subject:cc :to:from:date:arc-authentication-results; bh=9p6FfrdWpOy4vJcPmmt71QqmJTropVhHPBN86YqB3SU=; b=A22lALlNHFLsjKNkyWI7cRJbx5f8wFb/Y4oSafovnk5Qn+66iG4JcnBkztzAFNxxBR yhnwDDEDbeAOIZWsLWUwsgLH38R9lvrjuviA2OICcIJrB/hTLK+sM6OK6Eh3gEod78pi wRL2h1CRIW8XQXiHhwXav3aR6aduYAQVNz+znzg6E1dZE/v/k8sPW/XSTfE3A6NpJJ/W LiQHD8ponLpHultmDy9TGyMQLGJv0iQiV4pawfQzHZtSy+kuNnwZyY0RvSs8bhlI/239 wM/+DN7PPgG5fSybJEfAt+Jb9LhYwyE0EKx9xwGLAP9JP3t9lqG6cVlUnQFpwQE3sbjL +dWA== ARC-Authentication-Results: i=1; mx.google.com; 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 b2si3505962pgr.434.2018.01.26.13.40.25; Fri, 26 Jan 2018 13:40:39 -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; 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 S1751879AbeAZVjs (ORCPT + 99 others); Fri, 26 Jan 2018 16:39:48 -0500 Received: from mail-ot0-f178.google.com ([74.125.82.178]:42436 "EHLO mail-ot0-f178.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751674AbeAZVjq (ORCPT ); Fri, 26 Jan 2018 16:39:46 -0500 Received: by mail-ot0-f178.google.com with SMTP id s3so1626111otc.9; Fri, 26 Jan 2018 13:39:46 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=9p6FfrdWpOy4vJcPmmt71QqmJTropVhHPBN86YqB3SU=; b=NElHifywdyzKk8vB49pRHyBkAydbv2SiLum/L33rBmOgs2TEmhiNLlmhEwCsMDOP9l F1Ksjers3rcSZHeEtCNsn63JBC0zl6iXTZLWlcT0YCx7ftLNdDcb4Cj88Qvo9uMFUT1w dcPE9UE4UEKlQv79SEhEpe1ZducL+gRDO7fTkhG1OD5U4mGaJJBbf4w2QW3s/X8gVH4K iDqf7HFjnws3053lffUUG2pOfi9VnHrwjCprInLUgsMsJ6pVzzSzya8AHN+1/Khoa03K cdkkbZSVNnsflbfUC1MZb0uForDgpHhrVUZQKtEHety9QXwvvyXSTGE4HHIJWvefq90L EIqQ== X-Gm-Message-State: AKwxytdP1JJ4zLFQL3BO3hYhd+8b8+qLwFLU5eT4z6BYaF+lsLVVuqTa p+gTCp05gykSXbLSYw80rg== X-Received: by 10.157.68.133 with SMTP id v5mr3657381ote.93.1517002784634; Fri, 26 Jan 2018 13:39:44 -0800 (PST) Received: from localhost (216-188-254-6.dyn.grandenetworks.net. [216.188.254.6]) by smtp.gmail.com with ESMTPSA id q8sm4180899otc.62.2018.01.26.13.39.43 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 26 Jan 2018 13:39:43 -0800 (PST) Date: Fri, 26 Jan 2018 15:39:43 -0600 From: Rob Herring To: Chintan Pandya Cc: Rasmus Villemoes , Frank Rowand , "open list:OPEN FIRMWARE AND FLATTENED DEVICE TREE BINDINGS" , "linux-kernel@vger.kernel.org" , linux-arm-msm Subject: Re: [PATCH v2] of: use hash based search in of_find_node_by_phandle Message-ID: <20180126213943.7zwijanlbrq3y666@rob-hp-laptop> References: <1516955496-17236-1-git-send-email-cpandya@codeaurora.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20170609 (1.8.3) Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, Jan 26, 2018 at 09:34:59AM -0600, Rob Herring wrote: > On Fri, Jan 26, 2018 at 9:14 AM, Chintan Pandya wrote: > > > >> I'm probably missing something obvious, but: Aren't phandles in practice > >> small consecutive integers assigned by dtc? If so, why not just have a > >> smallish static array mapping the small phandle values directly to > >> device node, instead of adding a pointer to every struct device_node? Or > >> one could determine the size of the array dynamically (largest seen > >> phandle value, capping at something sensible, e.g. 1024). > > I do have some concerns that is a bit fragile and dependent on dtc's > implementations. However, I guess we already kind of are with overlay > phandles. > > > Haven't noticed this earlier !! If following is known or true, we can avoid > > using hash-table and save per device_node hlish_node. > > > > 1. How to know max phandle value without traversing tree once? In my > > case, > > max is 1263. > > We already have to know it for overlays. Plus unflattening has to > handle phandles specially already, so it would be easy to do there if > we aren't already. > > Then the question what to do with overlays. For now, we can probably > assume too few phandles to matter. > > > 2. Although, I haven't observed collision but is it like every > > device_node > > is associated with unique phandle value ? > > Yes, phandles must be unique. > > >> In either case, one would still need to keep the code doing the > >> whole-tree traversal for handling large phandle values, but I think the > >> above should make lookup O(1) in most cases. > > > > I would refrain doing this because that will make this API inconsistent in > > terms > > of time taken by different nodes. I see that people do change their device > > placing in DT and that changes time taken in of_* APIs for them but > > affecting > > others. > > Who cares. It's the total time that matters. It's obviously not a > problem until you have 1000s of lookups as no one cared until recently > (though you aren't the first with a hash table lookup). > > >> Alternatively, one could just count the number of nodes with a phandle, > >> allocate an array of that many pointers (so the memory use is certainly > >> no more than if adding a pointer to each device_node), and sort it by > >> phandle, so one can do lookup using a binary search. > >> > >> Rasmus > > > > This is certainly doable if current approach is not welcomed due to > > addition on hlish_node in device_node. > > I certainly prefer an out of band approach as that's easier to turn of > if we want to save memory. > > Still, I'd like to see some data on a cache based approach and reasons > why that won't work. I was curious, so I implemented it. It ends up being similar to Rasmus's 1st suggestion. The difference is we don't try to store all entries, but rather implement a hash table that doesn't handle collisions. Relying on the fact that phandles are just linearly allocated from 0, we just mask the high bits of the phandle to get the index. Using the unittest (modified to run twice), the time for 192 calls goes from ~50us to ~30us. Can you try out on your setup and try different array sizes. 8<---------------------------------------------------------------------- diff --git a/drivers/of/base.c b/drivers/of/base.c index dd0b4201f1cc..cb88adf4f3db 100644 --- a/drivers/of/base.c +++ b/drivers/of/base.c @@ -986,6 +986,13 @@ int of_modalias_node(struct device_node *node, char *modalias, int len) } EXPORT_SYMBOL_GPL(of_modalias_node); +static ktime_t elapsed; +static int call_count; + +#define PHANDLE_CACHE_SZ 64 +#define PHANDLE_CACHE_HASH(x) ((x) & (PHANDLE_CACHE_SZ - 1)) +static struct device_node *phandle_cache[PHANDLE_CACHE_SZ]; + /** * of_find_node_by_phandle - Find a node given a phandle * @handle: phandle of the node to find @@ -997,16 +1004,30 @@ struct device_node *of_find_node_by_phandle(phandle handle) { struct device_node *np; unsigned long flags; + ktime_t t1, t2; if (!handle) return NULL; raw_spin_lock_irqsave(&devtree_lock, flags); - for_each_of_allnodes(np) - if (np->phandle == handle) - break; + t1 = ktime_get(); + np = phandle_cache[PHANDLE_CACHE_HASH(handle)]; + if (!np || np->phandle != handle) { + for_each_of_allnodes(np) + if (np->phandle == handle) { + phandle_cache[PHANDLE_CACHE_HASH(handle)] = np; + break; + } + + } + of_node_get(np); + t2 = ktime_get(); + elapsed = ktime_add(elapsed, ktime_sub(t2, t1)); + call_count++; raw_spin_unlock_irqrestore(&devtree_lock, flags); + if (!(call_count % 32)) + printk("of_find_node_by_phandle called %d times totalling %lld ns", call_count, elapsed); return np; } EXPORT_SYMBOL(of_find_node_by_phandle);