From patchwork Fri Nov 28 16:48:29 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Grant Likely X-Patchwork-Id: 41710 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-la0-f69.google.com (mail-la0-f69.google.com [209.85.215.69]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 532CF244C2 for ; Fri, 28 Nov 2014 16:48:45 +0000 (UTC) Received: by mail-la0-f69.google.com with SMTP id ge10sf900860lab.4 for ; Fri, 28 Nov 2014 08:48:44 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:delivered-to:from:subject:to:cc :in-reply-to:references:date:message-id:sender:precedence:list-id :x-original-sender:x-original-authentication-results:mailing-list :list-post:list-help:list-archive:list-unsubscribe; bh=gbAXjDMYxffzmNougzTx8tSrjvs7bdtU/XhIJGOxPWc=; b=A82xD/CsCv89MCw2wI8TZYj3imPJEfHO0nbUxYtkkh5Agw7tnO6Yve/o+HKP9BySZP G5VbEcDC04muBH+ode/o54cHC+bKyOfkoE1zA3t7phi1WZZbWdl4kx0X+UnyCUEKwJhr VRW/ducOfi4s2zH5GY1CwOxZbJ5ooe46aL3Oyx+cp/PNOfK5brEaufwl7HmMLSYWXXNR 0kzfs5oVF9Tb19G/apDbXvyltRN5bMT1NcTaby3SUC5oRe++mItJyXkNJ9U8fJnUuq41 Nrlf+Xhyo7WjDUZaipRUVZxTQ5nNihty2q777FLLgFLOEliMPtIp/cTezPKlW3M1Bu5B LRZA== X-Gm-Message-State: ALoCoQkkV93xsZ0ZHf4Y8SZ4uXk9wg229W6X6WKQc9tUGOXi+7RSGbS1iSdFxvc2O4UnuWU+7Fho X-Received: by 10.180.106.67 with SMTP id gs3mr10196149wib.3.1417193324233; Fri, 28 Nov 2014 08:48:44 -0800 (PST) MIME-Version: 1.0 X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.5.227 with SMTP id v3ls1010156lav.91.gmail; Fri, 28 Nov 2014 08:48:44 -0800 (PST) X-Received: by 10.152.21.9 with SMTP id r9mr45278487lae.76.1417193324069; Fri, 28 Nov 2014 08:48:44 -0800 (PST) Received: from mail-lb0-f170.google.com (mail-lb0-f170.google.com. [209.85.217.170]) by mx.google.com with ESMTPS id kw6si10516850lac.24.2014.11.28.08.48.44 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 28 Nov 2014 08:48:44 -0800 (PST) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.217.170 as permitted sender) client-ip=209.85.217.170; Received: by mail-lb0-f170.google.com with SMTP id w7so5890519lbi.29 for ; Fri, 28 Nov 2014 08:48:44 -0800 (PST) X-Received: by 10.112.235.196 with SMTP id uo4mr44067692lbc.66.1417193323919; Fri, 28 Nov 2014 08:48:43 -0800 (PST) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.112.184.201 with SMTP id ew9csp121689lbc; Fri, 28 Nov 2014 08:48:42 -0800 (PST) X-Received: by 10.68.69.48 with SMTP id b16mr73279437pbu.59.1417193321820; Fri, 28 Nov 2014 08:48:41 -0800 (PST) Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id ek5si16970119pbd.113.2014.11.28.08.48.41 for ; Fri, 28 Nov 2014 08:48:41 -0800 (PST) Received-SPF: none (google.com: devicetree-owner@vger.kernel.org does not designate permitted sender hosts) client-ip=209.132.180.67; Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751166AbaK1Qsk (ORCPT + 4 others); Fri, 28 Nov 2014 11:48:40 -0500 Received: from mail-wi0-f170.google.com ([209.85.212.170]:40631 "EHLO mail-wi0-f170.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751163AbaK1Qsj (ORCPT ); Fri, 28 Nov 2014 11:48:39 -0500 Received: by mail-wi0-f170.google.com with SMTP id bs8so21448525wib.3 for ; Fri, 28 Nov 2014 08:48:38 -0800 (PST) X-Received: by 10.180.198.52 with SMTP id iz20mr35592333wic.60.1417193318176; Fri, 28 Nov 2014 08:48:38 -0800 (PST) Received: from trevor.secretlab.ca (host86-166-84-117.range86-166.btcentralplus.com. [86.166.84.117]) by mx.google.com with ESMTPSA id bm1sm15684094wjb.45.2014.11.28.08.48.36 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 28 Nov 2014 08:48:37 -0800 (PST) Received: by trevor.secretlab.ca (Postfix, from userid 1000) id CC876C40884; Fri, 28 Nov 2014 16:48:29 +0000 (GMT) From: Grant Likely Subject: Re: [PATCH] Patch to improve device tree structure To: frowand.list@gmail.com Cc: Gaurav Minocha , "devicetree@vger.kernel.org" , Rob Herring In-Reply-To: <546CEFC4.805@gmail.com> References: <1416199976-21147-1-git-send-email-gaurav.minocha.os@gmail.com> <20141118151026.D2D63C40966@trevor.secretlab.ca> <546BF447.6080300@gmail.com> <546CEFC4.805@gmail.com> Date: Fri, 28 Nov 2014 16:48:29 +0000 Message-Id: <20141128164829.CC876C40884@trevor.secretlab.ca> Sender: devicetree-owner@vger.kernel.org Precedence: list List-ID: X-Mailing-List: devicetree@vger.kernel.org X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: grant.likely@linaro.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.217.170 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 List-Post: , List-Help: , List-Archive: List-Unsubscribe: , On Wed, 19 Nov 2014 11:30:12 -0800 , Frank Rowand wrote: > On 11/19/2014 5:56 AM, Grant Likely wrote: > > On Wed, Nov 19, 2014 at 1:37 AM, Frank Rowand wrote: > >> On 11/18/2014 7:10 AM, Grant Likely wrote: > >>> On Sun, 16 Nov 2014 20:52:56 -0800 > >>> , Gaurav Minocha > >>> wrote: > >>>> This patch improves the implementation of device tree structure. > >>>> > >>>> Traditional child and sibling linked list in device tree structure > >>>> is removed and is replaced by list_head (i.e. circular doubly linked > >>>> list) already available in Linux kernel. > >>>> > >>>> Signed-off-by: Gaurav Minocha > >>> > >>> Hi Gaurav, > >>> > >>> So, after you've done this work, I need to you rebase it (and of course > >>> it is non-trivial) onto linux-next. I've already got a patch queued up > >>> which gets rid of the of_allnodes/allnext list which will have conflicts > >>> with this patch. > >>> > >>> I'll make comments below where still relevant. > >> > >> Grant, > >> > >> My first reaction to this patch was that moving to using struct list_head > >> made the code less readable plus increased the size of struct device_node. > >> > >> I reworked the changes to drivers/of/base.c to see if I could make > >> it a little more readable. And I see below that you also have some > >> suggestions that make it more readable. > >> > >> Even after that, I'm still feeling that the gain of moving to a more > >> standard list data type might not be greater than the downsides in > >> terms of readability and space. The current list implementation does > >> seem like a decent fit to the problem space. > > > > Moving to list_head has a couple of nice benefits. The prime > > motification is that using a standard list_head means that the OF code > > can be migrated to use the standard rcu operations and get rid of manual > > of_node_{get,put} management in the majority of code paths. > > Oh yeah, I remember you mentioning that before. That is what was missing > from Gaurav's patch header, explaining the value of the change. If this > is the end goal, then I think it would be valuable to add a second patch > to the series that shows what the actual changes for rcu will be so that > the cost vs benefit of the end result can be evaluated. > > > > A second reason to do this is it becomes easy to add nodes to the end of > > the list instead of the beginning. It's a small thing, but it makes > > unflattening simpler. > > Not a big change. In the unflatten_dt_node() part of the patch, the > result was 4 lines deleted, 3 lines added. With my attached patch to > remove the next field, it would have been 8 lines deleted, 3 lines > added -- thus list_head is an even greater simplification. But still > tiny. > > > > I've also considered switching to a hlist_head/hlist_node to keep the > > footprint the same.* With an hlist_head the cost is a wash, but looses > > the ability to do O(1) addition to the end of the list. > > > > * Gaurav's patch removes the *child and *sibling pointers, but doesn't > > remove the *next pointer which can also be dropped. So, three pointers > > get dropped from the structure. Using list_head adds 4 pointers (Net > > +1). hlist_head adds 3 (Net 0). > > I include a patch below to also drop the *next pointer. Not to actually > propose submitting the patch, but to suggest that Gaurav's patch should be > counted as a net of +2 pointers. I expect that you will accept either a > list_head of an hlist_head patch, but if you do not then I will submit the > below patch to remove *next or a patch to rename *next to match the actual > usage of the field. > > I still do not have a strong opinion, but I am still feeling that the gain > probably does not outweigh the cost. > > -Frank > > > > > g. > > > > From: Frank Rowand > > Decrease size of struct device_node by one pointer. > The pointer is only used during the unflattening of the > device tree at boot. > > The cost of removing the pointer is chasing through the > sibling list to add new nodes instead of using the > cached 'last_child'. The cost is expected to be in the > noise level. > > Signed-off-by: Frank Rowand > --- > drivers/of/fdt.c | 14 +++++++++----- > include/linux/of.h | 1 - > 2 files changed, 9 insertions(+), 6 deletions(-) > > Index: b/include/linux/of.h > =================================================================== > --- a/include/linux/of.h > +++ b/include/linux/of.h > @@ -55,7 +55,6 @@ struct device_node { > struct device_node *parent; > struct device_node *child; > struct device_node *sibling; > - struct device_node *next; /* next device of same type */ > struct device_node *allnext; /* next in list of all nodes */ > struct kobject kobj; > unsigned long _flags; > Index: b/drivers/of/fdt.c > =================================================================== > --- a/drivers/of/fdt.c > +++ b/drivers/of/fdt.c > @@ -226,12 +226,16 @@ static void * unflatten_dt_node(void *bl > *allnextpp = &np->allnext; > if (dad != NULL) { > np->parent = dad; > - /* we temporarily use the next field as `last_child'*/ > - if (dad->next == NULL) > + if (dad->child == NULL) > dad->child = np; > - else > - dad->next->sibling = np; > - dad->next = np; > + else { > + struct device_node *next; > + > + next = dad->child; > + while (next->sibling) > + next = next->sibling; > + next->sibling = np; > + } > } > } > /* process properties */ Instead of keeping it always in order, what about reordering the whole list after all the nodes at a given level are unflattened? That would avoid traversing the entire sibling list on every node addition. Like this: g. >From de46de766eb4d2240208bf83fdae955361069352 Mon Sep 17 00:00:00 2001 From: Grant Likely Date: Fri, 28 Nov 2014 16:03:33 +0000 Subject: [PATCH] of: Drop ->next pointer from struct device_node The ->next pointer in struct device_node is a hanger-on from when it was used to iterate over the whole tree by a particular device_type property value. Those days are long over, but the fdt unflattening code still uses it to put nodes in the unflattened tree into the same order as node in the flat tree. By reworking the unflattening code to reverse the list after unflattening all the children of a node, the pointer can be dropped which gives a small amount of memory savings. Signed-off-by: Grant Likely Cc: Gaurav Minocha Cc: Frank Rowand --- drivers/of/fdt.c | 24 ++++++++++++++++++------ include/linux/of.h | 1 - 2 files changed, 18 insertions(+), 7 deletions(-) diff --git a/drivers/of/fdt.c b/drivers/of/fdt.c index 7f6ee31d5650..a41f9fdb1aa0 100644 --- a/drivers/of/fdt.c +++ b/drivers/of/fdt.c @@ -226,12 +226,8 @@ static void * unflatten_dt_node(void *blob, prev_pp = &np->properties; if (dad != NULL) { np->parent = dad; - /* we temporarily use the next field as `last_child'*/ - if (dad->next == NULL) - dad->child = np; - else - dad->next->sibling = np; - dad->next = np; + np->sibling = dad->child; + dad->child = np; } } /* process properties */ @@ -329,6 +325,22 @@ static void * unflatten_dt_node(void *blob, if (*poffset < 0 && *poffset != -FDT_ERR_NOTFOUND) pr_err("unflatten: error %d processing FDT\n", *poffset); + + /* + * Reverse the child list. Some drivers assumes node order matches .dts + * node order + */ + if (!dryrun && np->child) { + struct device_node *child = np->child; + np->child = NULL; + while (child) { + struct device_node *next = child->sibling; + child->sibling = np->child; + np->child = child; + child = next; + } + } + if (nodepp) *nodepp = np; diff --git a/include/linux/of.h b/include/linux/of.h index 8b021db3e16e..3f0f0ffbd5e5 100644 --- a/include/linux/of.h +++ b/include/linux/of.h @@ -56,7 +56,6 @@ struct device_node { struct device_node *parent; struct device_node *child; struct device_node *sibling; - struct device_node *next; /* next device of same type */ struct kobject kobj; unsigned long _flags; void *data;