Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1249366 > unrolled thread

[PATCH 0/14] init: deps: dependency based (parallelized) init

Back to article view | Back to linux.kernel

Contents

  [PATCH 0/14] init: deps: dependency based (parallelized) init Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:20 +0200
    [PATCH 04/14] init: deps: order network interfaces by link order Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:20 +0200
      Re: [PATCH 04/14] init: deps: order network interfaces by link order Linus Torvalds <torvalds@linux-foundation.org> - 2015-10-17 20:30 +0200
        Re: [PATCH 04/14] init: deps: order network interfaces by link order Alexander Holler <holler@ahsoftware.de> - 2015-10-17 20:40 +0200
          Re: [PATCH 04/14] init: deps: order network interfaces by link order Linus Torvalds <torvalds@linux-foundation.org> - 2015-10-17 21:00 +0200
            Re: [PATCH 04/14] init: deps: order network interfaces by link order Linus Torvalds <torvalds@linux-foundation.org> - 2015-10-17 21:10 +0200
              Re: [PATCH 04/14] init: deps: order network interfaces by link order Alexander Holler <holler@ahsoftware.de> - 2015-10-17 21:20 +0200
                Re: [PATCH 04/14] init: deps: order network interfaces by link order Linus Torvalds <torvalds@linux-foundation.org> - 2015-10-17 21:40 +0200
                Re: [PATCH 04/14] init: deps: order network interfaces by link order Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2015-10-17 21:40 +0200
                  Re: [PATCH 04/14] init: deps: order network interfaces by link order Alexander Holler <holler@ahsoftware.de> - 2015-10-17 22:00 +0200
                    Re: [PATCH 04/14] init: deps: order network interfaces by link order Alexander Holler <holler@ahsoftware.de> - 2015-10-17 23:30 +0200
              Re: [PATCH 04/14] init: deps: order network interfaces by link order Alexander Holler <holler@ahsoftware.de> - 2015-10-17 23:40 +0200
            Re: [PATCH 04/14] init: deps: order network interfaces by link order Alexander Holler <holler@ahsoftware.de> - 2015-10-17 21:10 +0200
          Re: [PATCH 04/14] init: deps: order network interfaces by link order Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2015-10-17 21:00 +0200
          Re: [PATCH 04/14] init: deps: order network interfaces by link order Linus Torvalds <torvalds@linux-foundation.org> - 2015-10-17 21:10 +0200
            Re: [PATCH 04/14] init: deps: order network interfaces by link order Alexander Holler <holler@ahsoftware.de> - 2015-10-17 21:10 +0200
    [PATCH 03/14] init: deps: dt: use (HW-specific) dependencies provided by the DT too Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:20 +0200
    [PATCH 06/14] dtc: deps: Automatically add new property 'dependencies' which contains a list of referenced phandles Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:20 +0200
    [PATCH 07/14] dtc: deps: introduce new (virtual) property no-dependencies Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:20 +0200
    [PATCH 09/14] dtc: deps: Add option to print dependency graph as dot (Graphviz) Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:20 +0200
    [PATCH 02/14] init: deps: use annotated initcalls for a dependency based (optionally parallelized) init Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:20 +0200
    [PATCH 01/14] init: deps: introduce annotated initcalls Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:20 +0200
    [PATCH 14/14] dt: dts: deps: omap: beagle: make some remote-endpoints non-dependencies Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:30 +0200
    [PATCH 13/14] dt: dts: deps: imx6q: make some remote-endpoints non-dependencies Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:30 +0200
    [PATCH 12/14] dt: dts: deps: kirkwood: dockstar: add dependency ehci -> usb power regulator Alexander Holler <holler@ahsoftware.de> - 2015-10-17 19:30 +0200
    Re: [PATCH 0/14] init: deps: dependency based (parallelized) init Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2015-10-17 19:50 +0200
      Re: [PATCH 0/14] init: deps: dependency based (parallelized) init Alexander Holler <holler@ahsoftware.de> - 2015-10-17 20:30 +0200
        Re: [PATCH 0/14] init: deps: dependency based (parallelized) init Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2015-10-17 20:40 +0200
          Re: [PATCH 0/14] init: deps: dependency based (parallelized) init Alexander Holler <holler@ahsoftware.de> - 2015-10-17 21:50 +0200
            Re: [PATCH 0/14] init: deps: dependency based (parallelized) init Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2015-10-17 22:30 +0200
              Re: [PATCH 0/14] init: deps: dependency based (parallelized) init Alexander Holler <holler@ahsoftware.de> - 2015-10-17 22:40 +0200
    Re: [PATCH 11/14] init: deps: annotate various initcalls Linus Torvalds <torvalds@linux-foundation.org> - 2015-10-17 20:50 +0200
      Re: [PATCH 11/14] init: deps: annotate various initcalls Alexander Holler <holler@ahsoftware.de> - 2015-10-17 21:10 +0200

Page 1 of 2  [1] 2  Next page →

#1249366 — [PATCH 0/14] init: deps: dependency based (parallelized) init

Hello,

here is the newest version of my patches to use a dependency based
initialization order. It now works without DT too.

Background:

Currently initcalls are ordered by some levels and the link order. This
means whenever a file is renamed, changes directory or a Makefile is
modified the order with which initcalls are called might change. This
might result in problems. Furthermore, the required dependencies are
often not documented, sometimes there are comments in the source or in a
commit message, but most often the knowledge why a specific initcall
belongs to a specific initcall level isn't obvious without carefully
examing he source. And initcalls are used by drivers and subsystems, and
the count of both have grown quiet a lot in the last years. So it's
rather difficult to maintain a proper link order.
Another problem is that the link order can't be modified dynamically at
boot time to include dependencies dictated by the hardware. To circumvent
this, a brute-force trial-and-error mechanism called deferred probes has
been introduced, but this approach, while beeing KISS, has its own
problems.

To solve these problems I've written patches to use a topological sort at
boot time which uses dependencies to calculate the order with which
initcalls are called.

Why? What are the benefits (assuming correct dependencies are available)?

- It offers a clear in-source documentation for dependencies between
  initcalls.
- It is robust in regard to file or directory name changes and changes in
  a Makefile.
- If enabled, the order with which drivers for interfaces are called
  (e.g. network interfaces, hard disks), can be defined independent of
  the link order. These might result in more stable interface names or
  numbers.
- If enabled, it makes the the deferred probes obsolete, which might
  result in faster boot times.
- If enabled, it is possible to call initcalls in parallel. E.g. the
  shipped kernel for Fedora 21 (4.1.7-100.fc21.x86_64) contains around
  560 initcalls. These are all called in series. Also some of them use
  asynchronous stuff by themself, most don't do.

Drawbacks:

- It requires a small amount of time to calculate the order a boot time.
  But this time is most often smaller than the time saved by using
  multiple cores to call initcalls or by not needing deferred probes.
- Dependencies are required. For everything which can be build as a
  module, looking at modules.dep might give some pointers. Looking at
  the help from menuconfig also might give some pointers. But in the
  end, the most preferable way would be if maintainers or other people
  which have a deeper knowledge about the source and functionality
  would add the dependencies.

And last but not least, these feature is totally optional. If disabled,
nothing changes.


Some words about the patches:

Patch 1 introduces annotated initcalls, patch 2 uses them and patch 3
adds hardware specific dependencies from the device tree to the existent
set of dependencies.

Patch 4 and 5 are examples about how to achieve a stable initialization
order for various type of drivers. The two patches are doing this for
network interfaces (based on the existing link order) and I2C busses
(based on the new driver IDs). I leave it for discussion which one should
be used. My suggestion would be to order the IDs like the link order and
then use the order based on IDs. That would get rid of the link order while
also beeing downwards compatible.

Patches 6-9 do contain changes for dtc to enhance the binary blob (dtb)
with type information for phandles (the dependencies used by patch 3).
I've already posted these patches a year ago.

Patch 10 contains the list of driver IDs I've annotated and is NOT meant
for merging. Patch 11 contains all the changes on drivers I've annotated
and is NOT meant for merge too. I've no idea how such patches might end
up in the kernel (in fact I've no idea what's necessary for any patch),
therefor these two patches are there to offer a quick start to evaluate
this feature.

The final 3 patches contain a few changes for the DTs of 3 ARM boards.

Because I don't want to fiddle with problems in the unstable mainline tree,
these patches are based on the latest stable kernel (4.2.3). But besides
the big patch (11) with all the driver changes, they apply without problems
to the current mainline too. And the necessary changes to use the big patch
on mainline should be trivial, as all the changes in this patch are trivial
too.

I've tested this patch series with several ARM(32) systems, x86 and x86_64
and the boot time was faster on allmost all systems. Either through
avoiding deferred probes (on single core machines) or by using the
parallel initialization. And keep in mind that, also I've already
annotated quiet a lot of initcalls, a big bunch of them still are left
and therefor are still called in series using just one core and not in
parallel.

Keep in mind that these patches are an offer, I wasn't paid for them and
I don't need them in the mainline kernel.
As long as you are able to use a polite language, you can send me any
comment, regardless if it's good or bad. But, please, keep away with
Baby-Speak or contumelious comments.

And, just in case, I'm aware that adding the necessary dependencies means
some effort and a lot of (trivial) commits and therefor having all
possible initcalls annotated would be a long term goal. But, besides that
this could be done smoothly without any need to hurry, I think it makes
sense. Otherwise, in my humble opinion, the problems to keep an overview
and ordering initcalls will just become worse.


Alexander Holler
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1249367 — [PATCH 04/14] init: deps: order network interfaces by link order

In order to provide stable interface numbers, network interface drivers
will be ordered by the link order. This is easy to accomplish by adding
dependencies.

Assuming three different ethernet-drivers, without any special code,
the dependency graph would not require any special order inbetween them
and would look like that:

    eth-driver-base
   /      |       \
eth-x   eth-y    eth-z

Now we just add dependencies. With the additional dependencies the graph
looks like:

 eth-driver-base
  |     | |
eth-x   | |
  |     | |
eth-y  -| |
  |       |
eth-z  ---|

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 include/linux/driver_ids.h | 11 +++++++++++
 init/dependencies.c        |  9 +++++++++
 2 files changed, 20 insertions(+)

diff --git a/include/linux/driver_ids.h b/include/linux/driver_ids.h
index 60964fe..1133a68 100644
--- a/include/linux/driver_ids.h
+++ b/include/linux/driver_ids.h
@@ -15,6 +15,17 @@
 enum {
 	drvid_unused,
 	/* To be filled */
+
+	/*
+	 * Network drivers will be ordered according to the link order
+	 * (which means not necessarily according to their appearance
+	 * here).
+	 * This provides stable interface numbers.
+	 * Therefor their IDs have to be in the following block.
+	 */
+	drvid_network_drivers_start,
+	drvid_network_drivers_end,
+
 	drvid_max
 };
 
diff --git a/init/dependencies.c b/init/dependencies.c
index b484f67..027fc4b 100644
--- a/init/dependencies.c
+++ b/init/dependencies.c
@@ -301,12 +301,21 @@ static int __init add_dependencies(void)
 static void __init build_inventory(void)
 {
 	const struct _annotated_initcall *ac;
+	unsigned id_last_network_driver = 0;
 
 	ac = __annotated_initcall_start;
 	for (; ac < __annotated_initcall_end; ++ac) {
 		include_node[ac->id] = true;
 		annotated_initcall_by_drvid[ac->id] = ac;
 		nvertices = max(nvertices, ac->id);
+		/* order network drivers by link order*/
+		if (ac->id > drvid_network_drivers_start &&
+				ac->id < drvid_network_drivers_end) {
+			if (id_last_network_driver)
+				add_initcall_dependency(ac->id,
+					id_last_network_driver);
+			id_last_network_driver = ac->id;
+		}
 	}
 }
 
-- 
2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249411 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

On Sat, Oct 17, 2015 at 10:14 AM, Alexander Holler <holler@ahsoftware.de> wrote:
>
> Assuming three different ethernet-drivers, without any special code,
> the dependency graph would not require any special order inbetween them
> and would look like that:

This seems *fundamentally* wrong.

This is in no way specific to network drivers (or to disk drivers, or
to anything else).

So requiring extra logic for this implies that something is seriously wrong.

If two drivers aren't ordered by dependencies, they should always be
in link order, regardless of any hacks like these. If they're not,
things are wrong.

I think your problem is that you make that dependency thing a separate
ordering, so now it matters whether a driver has a dependency or not.

If something like this is to work, it has to work *with* the normal
ordering, not outside of it and then have these kinds of broken
special cases.

The normal init orderings (ie core -> postcore -> arch -> subsys -> fs
-> rootfs -> device -> late) should just be an extra dependency, I
think.

The way that you just insert the annotated dependencies in between
levels 6 and 7 ("device" and "late") can't be right. It means - for
example - that you can't have subsystems that have dependencies.

So I really think that if we do dependencies, then the current levels
have to be added as dependencies, so that "subsys_initcall(xyz)"
basically means "xyz depends on the 'subsys' event, and 'subsys_end'
depends on xyz". Then within that, you might have another bus driver
that in turn depends on 'xyz'.

Because right now afaik we do have dependencies like that, which we
sort out by link ordering (things like 'drm depends on pci' - I'm not
actually sure that one is true, but it might be).

                     Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249412 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

Am 17.10.2015 um 20:23 schrieb Linus Torvalds:
> On Sat, Oct 17, 2015 at 10:14 AM, Alexander Holler <holler@ahsoftware.de> wrote:
>>
>> Assuming three different ethernet-drivers, without any special code,
>> the dependency graph would not require any special order inbetween them
>> and would look like that:
>
> This seems *fundamentally* wrong.
>
> This is in no way specific to network drivers (or to disk drivers, or
> to anything else).
>
> So requiring extra logic for this implies that something is seriously wrong.
>
> If two drivers aren't ordered by dependencies, they should always be
> in link order, regardless of any hacks like these. If they're not,
> things are wrong.
>
> I think your problem is that you make that dependency thing a separate
> ordering, so now it matters whether a driver has a dependency or not.

I'm making dependencies the only ordering for annotated initcalls.

Otherwise it's impossible to call initcalls in parallel. I've seen a 
stable topological sort somewhere, but whenever you want to parallelize 
the initcalls, the stable ordering would be gone anyway. So I've decided 
not to look further at a stable topological sort.

> If something like this is to work, it has to work *with* the normal
> ordering, not outside of it and then have these kinds of broken
> special cases.
>
> The normal init orderings (ie core -> postcore -> arch -> subsys -> fs
> -> rootfs -> device -> late) should just be an extra dependency, I
> think.
>
> The way that you just insert the annotated dependencies in between
> levels 6 and 7 ("device" and "late") can't be right. It means - for
> example - that you can't have subsystems that have dependencies.

Sorry, but that's wrong.

I've choosen to place initcalls between 5 and 6 to make it easier to 
move both, subsystems as well as normal drivers to the (new) level with 
annotated initcalls. If you look at what I've already "annotated", you 
will see there are quiet a lot initcalls I've moved from below 6 to the 
new level.

> So I really think that if we do dependencies, then the current levels
> have to be added as dependencies, so that "subsys_initcall(xyz)"
> basically means "xyz depends on the 'subsys' event, and 'subsys_end'
> depends on xyz". Then within that, you might have another bus driver
> that in turn depends on 'xyz'.

It would be absolutely no problem to introduce "virtual" initcalls for 
any level, e.g. just

depencies = {
	everything_below
}

initcall foo()
{
	return 0;
}

annotated_initcall(foo, id, dependencies),

Regards,

Alexander Holler
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249420 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

On Sat, Oct 17, 2015 at 11:37 AM, Alexander Holler <holler@ahsoftware.de> wrote:
>
> I'm making dependencies the only ordering for annotated initcalls.

Yeah, and quite frankly, that just means that I'm not going to merge it.

We do not do "flag-day" things. We've done them in the past, and it
has always been a major and unacceptable pain.

And if the dependency ordering is "outside" of the traditional
link-time ordering, then it is by definition a flag-day event. Every
time you add a dependency to even just *one* driver, it magically
changes ordering wrt all the other drivers, because now it's in a
different ordering domain.

So please reconsider. Or stop cc'ing me. Because "flag day" changes
really are not acceptable.

                       Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249425 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

On Sat, Oct 17, 2015 at 12:01 PM, Alexander Holler <holler@ahsoftware.de> wrote:
>
> That isn't a flag day thing. It's a config option everyone can turn on and
> off whenever he wants.

That's a flag-day thing. We've done it (drm comes to mind - several times).

I'm disappointed, because I _know_ I pointed you in the direction of
stable sorting about a month ago. I really had hoped you'd have taken
that into account.

                      Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249430 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

Am 17.10.2015 um 21:08 schrieb Linus Torvalds:
> On Sat, Oct 17, 2015 at 12:01 PM, Alexander Holler <holler@ahsoftware.de> wrote:
>>
>> That isn't a flag day thing. It's a config option everyone can turn on and
>> off whenever he wants.
>
> That's a flag-day thing. We've done it (drm comes to mind - several times).
>
> I'm disappointed, because I _know_ I pointed you in the direction of
> stable sorting about a month ago. I really had hoped you'd have taken
> that into account.

It's impossible to take it into account because I don't want to miss the 
parallelize functionality. And without that, all the stuff doesn't offer 
enough benefits to be worse the effort but just adds some time necessary 
to do the sorting. It might solve the deferred probe problems, but 
without much benefit.

Regards,

Alexander Holler

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249434 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

On Sat, Oct 17, 2015 at 12:14 PM, Alexander Holler <holler@ahsoftware.de> wrote:
>
> It's impossible to take it into account because I don't want to miss the
> parallelize functionality. And without that, all the stuff doesn't offer
> enough benefits to be worse the effort but just adds some time necessary to
> do the sorting. It might solve the deferred probe problems, but without much
> benefit.

Quite frankly, the alleged advantage of parallelization of the init
sequence is *very* questionable.

But even if you were to want to parallelize things at that level, you'd still

 (a) want to make *that* a flag (to debug) and make it opt-in (so
you'd have another "this module can be done in parallel" marker)

 (b) end up with all the other drivers *not* being parallel, because
they were all written to not have everything happen at once.

 (c) want to avoid the whole flag-day things

so even then you'd want to sort everything using that topological
stable sort, so that you can sanely mix things, and then mark
individual drivers as "I'd like to run in parallel with the rest of
the init sequence".

The main thing that being parallel would change is likely that you'd
also have to add some kind of "I'm done" completion for each module
(or dependency point), so that things that depend on other things
(that have *started*) can explicitly wait for those other things to
actually end.

We have something like that for our "sync" points right now with the
whole asynchronous machinery. It's somewhat general (although I think
almost all users end up just doing "async_synchronize_full()", even
though we do have a cookie-based one) and I suspect the cookie-based
one could be used for individual drivers and their completions.

But I really think the whole "do initcalls in parallel" is a very bad
idea _regardless_ of anything else. We almost never actually have
initcalls that really take a lot of time, and when we do, we already
handle the big ones with the async machinery, which is actually a lot
more powerful and flexible than some "run initcalls in parallel",
exactly because you can run *parts* serially (like basic discovery),
and then run other parts asynchronously (like "spin up disk" or "wait
for power stable" or whatever - *after* you have discovered the
device).

So I personally think our async thing is much more powerful and useful
than some random "let's run initcalls in parallel".

                 Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249435 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

On Sat, Oct 17, 2015 at 09:14:34PM +0200, Alexander Holler wrote:
> Am 17.10.2015 um 21:08 schrieb Linus Torvalds:
> >On Sat, Oct 17, 2015 at 12:01 PM, Alexander Holler <holler@ahsoftware.de> wrote:
> >>
> >>That isn't a flag day thing. It's a config option everyone can turn on and
> >>off whenever he wants.
> >
> >That's a flag-day thing. We've done it (drm comes to mind - several times).
> >
> >I'm disappointed, because I _know_ I pointed you in the direction of
> >stable sorting about a month ago. I really had hoped you'd have taken
> >that into account.
> 
> It's impossible to take it into account because I don't want to miss the
> parallelize functionality. And without that, all the stuff doesn't offer
> enough benefits to be worse the effort but just adds some time necessary to
> do the sorting. It might solve the deferred probe problems, but without much
> benefit.

Again, parallelizing does not solve anything, and causes more problems
_and_ makes things take longer.  Try it, we have done it in the past and
proven this, it's pretty easy to test :)

thanks,

greg k-h
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249441 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

Am 17.10.2015 um 21:36 schrieb Greg Kroah-Hartman:
> On Sat, Oct 17, 2015 at 09:14:34PM +0200, Alexander Holler wrote:
>> Am 17.10.2015 um 21:08 schrieb Linus Torvalds:
>>> On Sat, Oct 17, 2015 at 12:01 PM, Alexander Holler <holler@ahsoftware.de> wrote:
>>>>
>>>> That isn't a flag day thing. It's a config option everyone can turn on and
>>>> off whenever he wants.
>>>
>>> That's a flag-day thing. We've done it (drm comes to mind - several times).
>>>
>>> I'm disappointed, because I _know_ I pointed you in the direction of
>>> stable sorting about a month ago. I really had hoped you'd have taken
>>> that into account.
>>
>> It's impossible to take it into account because I don't want to miss the
>> parallelize functionality. And without that, all the stuff doesn't offer
>> enough benefits to be worse the effort but just adds some time necessary to
>> do the sorting. It might solve the deferred probe problems, but without much
>> benefit.
>
> Again, parallelizing does not solve anything, and causes more problems
> _and_ makes things take longer.  Try it, we have done it in the past and
> proven this, it's pretty easy to test :)

I've tested it, otherwise I wouldn't have posted the patches.

Unfortunately it's quiet a lot of work to add dependencies for everything.

So maybe I'm able to offer some better numbers in a year or such, when I 
was bored often enough to add more dependencies for initcalls.

Not to mention that small changes in the order can have quiet big 
differences in the boot time, so it's quiet hard to parallelize stuff 
(add dependencies) correctly like e.g. the pci/acpi/processor stuff. 
Especially because many reasons for the current order aren't mentioned 
in the source and are hard to see without specific knowledge about the HW.

Alexander Holler
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249469 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

Am 17.10.2015 um 21:58 schrieb Alexander Holler:

> Unfortunately it's quiet a lot of work to add dependencies for everything.

And (just in case of), also I'm a non-native English writer, I know the 
difference between quiet and quite. But, unfortunately, that doesn't 
prevent me to type it wrong. It's like "teh" instead of "the". 
Unfortunately I'm not very good in writing English fast without errors, 
but that doesn't mean I'm dumb (also many native English writers prefer 
to assume that).

Regards,

Alexander Holler
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249472 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

Am 17.10.2015 um 21:08 schrieb Linus Torvalds:
> On Sat, Oct 17, 2015 at 12:01 PM, Alexander Holler <holler@ahsoftware.de> wrote:
>>
>> That isn't a flag day thing. It's a config option everyone can turn on and
>> off whenever he wants.
>
> That's a flag-day thing. We've done it (drm comes to mind - several times).
>
> I'm disappointed, because I _know_ I pointed you in the direction of
> stable sorting about a month ago. I really had hoped you'd have taken
> that into account.

Sorry, but I have to add another comment about that stable topological 
sort which can be easily found by searching the web.

As the author mentioned, he has done some search on that topic too and 
has found nothing. So, either I would have to trust his word (and his 
non-public proof) that it works or I would have to prove it myself.

Besides that he says it's based on bubble sort, which is known for its 
speed. So I would have had to write in C in order to see if the speed 
would be acceptable and would still be without any proof that it always 
works correctly.

Regards,

Alexander Holler
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249428 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

Am 17.10.2015 um 20:52 schrieb Linus Torvalds:
> On Sat, Oct 17, 2015 at 11:37 AM, Alexander Holler <holler@ahsoftware.de> wrote:
>>
>> I'm making dependencies the only ordering for annotated initcalls.
>
> Yeah, and quite frankly, that just means that I'm not going to merge it.
>
> We do not do "flag-day" things. We've done them in the past, and it
> has always been a major and unacceptable pain.

That isn't a flag day thing. It's a config option everyone can turn on 
and off whenever he wants.

>
> And if the dependency ordering is "outside" of the traditional
> link-time ordering, then it is by definition a flag-day event. Every
> time you add a dependency to even just *one* driver, it magically
> changes ordering wrt all the other drivers, because now it's in a
> different ordering domain.
>
> So please reconsider. Or stop cc'ing me. Because "flag day" changes
> really are not acceptable.

I'm choosing the second option. I will answer further mails on that 
topic, but will remove you from cc. Besides that I consider these 
patches as a total failure and will not post any further version.

Alexander Holler
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249421 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

On Sat, Oct 17, 2015 at 08:37:35PM +0200, Alexander Holler wrote:
> I'm making dependencies the only ordering for annotated initcalls.
> 
> Otherwise it's impossible to call initcalls in parallel.

We don't ever want to call initcalls in parallel, unless they can
properly handle it.  All drivers can tell the driver core to use
parallel probing if they know they can handle it.  See 'enum probe_type'
for this.

Trying to call initcalls or driver probes in parallel blindly has been
proven to both take a longer amount of time, and cause problems for
drivers that aren't expecting it.  The research on this was done years
ago when people were starting to work on booting quicker, and the end
result is what we have now where drivers that know they can handle this,
can tell the core to let them probe in this manner.

The outcome of this work is the sub-second boot time we have today.  If
your systems are taking longer to boot, then please look into the
drivers that are causing this, that is where the real issue is, not in
the core of the kernel.

thanks,

greg k-h
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249426 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

On Sat, Oct 17, 2015 at 11:37 AM, Alexander Holler <holler@ahsoftware.de> wrote:
>
> Otherwise it's impossible to call initcalls in parallel. I've seen a stable
> topological sort somewhere, but whenever you want to parallelize the
> initcalls, the stable ordering would be gone anyway. So I've decided not to
> look further at a stable topological sort.

So five seconds of googling gave me freely usable source code for a
stable topological sort, that also has a nice reported added
advantage:

 "An interesting property of a stable topological sort is that cyclic
dependencies are tolerated and resolved according to original order of
elements in sequence. This is a desirable feature for many
applications because it allows to sort any sequence with any
imaginable dependencies between the elements"

which seems to be *exactly* what you'd want, especially considering
that right now your patches add extra "no-dependency" markers exactly
because of the cyclical problem.

I think it was the #2 hit on google for "stable topological sort". I
didn't look closely at the source code, but it was not big.

And no, since we don't actually want to parallelize the initcalls
anyway (I had this discussion with you just a month ago), your
objections seem even more questionable. We have separate machinery for
"do this asynchronously", and we want to _keep_ that separate.

                 Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249427 — Re: [PATCH 04/14] init: deps: order network interfaces by link order

Am 17.10.2015 um 21:03 schrieb Linus Torvalds:
> On Sat, Oct 17, 2015 at 11:37 AM, Alexander Holler <holler@ahsoftware.de> wrote:
>>
>> Otherwise it's impossible to call initcalls in parallel. I've seen a stable
>> topological sort somewhere, but whenever you want to parallelize the
>> initcalls, the stable ordering would be gone anyway. So I've decided not to
>> look further at a stable topological sort.
>
> So five seconds of googling gave me freely usable source code for a
> stable topological sort, that also has a nice reported added
> advantage:
>
>   "An interesting property of a stable topological sort is that cyclic
> dependencies are tolerated and resolved according to original order of
> elements in sequence. This is a desirable feature for many
> applications because it allows to sort any sequence with any
> imaginable dependencies between the elements"
>
> which seems to be *exactly* what you'd want, especially considering
> that right now your patches add extra "no-dependency" markers exactly
> because of the cyclical problem.

That's the stable topological sort I've mentioned the link to in the 
discussion with you.

>
> I think it was the #2 hit on google for "stable topological sort". I
> didn't look closely at the source code, but it was not big.
>
> And no, since we don't actually want to parallelize the initcalls
> anyway (I had this discussion with you just a month ago), your
> objections seem even more questionable. We have separate machinery for
> "do this asynchronously", and we want to _keep_ that separate.

I've understood that now.

Sorry for wasting your time.

Alexander Holler
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249368 — [PATCH 03/14] init: deps: dt: use (HW-specific) dependencies provided by the DT too

This patch adds dependencies provided by the hardware description in
the used DT. This avoids the use of the deferred probe mechanism
on most (if not all) DT based kernels.

Drawback is that the binary DT blob has to be enhanced with type
information for phandles (which are used as dependencies) which
needs a modified dtc.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 drivers/of/base.c   | 114 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/of.h  |   3 ++
 init/dependencies.c |   4 ++
 3 files changed, 121 insertions(+)

diff --git a/drivers/of/base.c b/drivers/of/base.c
index 8b5a187..423ddff 100644
--- a/drivers/of/base.c
+++ b/drivers/of/base.c
@@ -12,6 +12,8 @@
  *  Reconsolidated from arch/x/kernel/prom.c by Stephen Rothwell and
  *  Grant Likely.
  *
+ *  The dependency related stuff was done by Alexander Holler.
+ *
  *      This program is free software; you can redistribute it and/or
  *      modify it under the terms of the GNU General Public License
  *      as published by the Free Software Foundation; either version
@@ -2308,3 +2310,115 @@ struct device_node *of_graph_get_remote_port(const struct device_node *node)
 	return of_get_next_parent(np);
 }
 EXPORT_SYMBOL(of_graph_get_remote_port);
+
+#ifdef CONFIG_DEPENDENCIES
+
+static const struct _annotated_initcall * __init find_matching_driver(
+	const struct _annotated_initcall *from, const struct device_node *node)
+{
+	while (++from != __annotated_initcall_end)
+		if (from->driver &&
+				__of_match_node(from->driver->of_match_table,
+					node))
+			return from;
+	return NULL;
+}
+
+static int __init add_dep_list(const struct device_node *node, unsigned drvid)
+{
+	const __be32 *list, *list_end;
+	uint32_t ph;
+	int size = 0;
+	int rc = 0;
+	const struct device_node *dep;
+	const struct _annotated_initcall *ac;
+
+	list = __of_get_property(node, "dependencies", &size);
+	if (!list || !size || size % sizeof(*list))
+		return 0;
+	list_end = list + size / sizeof(*list);
+	while (list < list_end) {
+		ph = be32_to_cpup(list++);
+		if (unlikely(!ph)) {
+			/* Should never happen */
+			if (node->name)
+				pr_warn("phandle == 0 for %s\n", node->name);
+			continue;
+		}
+		dep = of_find_node_by_phandle(ph);
+		if (unlikely(!dep)) {
+			pr_err("No DT node for dependency with phandle 0x%x found\n",
+				ph);
+			continue;
+		}
+		ac = __annotated_initcall_start - 1;
+		while ((ac = find_matching_driver(ac, dep))) {
+			if (!ac->id)
+				continue;
+			rc = add_initcall_dependency(drvid, ac->id);
+			if (rc)
+				return rc;
+		}
+	}
+
+	return rc;
+}
+
+static int __init add_deps(unsigned parent, const struct device_node *node)
+{
+	struct device_node *child;
+	const struct _annotated_initcall *ac;
+	int rc = 0;
+	bool found_one_driver = false;
+
+	if (!__of_device_is_available(node))
+		return 0;
+	if (__of_get_property(node, "compatible", NULL)) {
+		ac = __annotated_initcall_start - 1;
+		while ((ac = find_matching_driver(ac, node))) {
+			if (!ac->id)
+				continue;
+			found_one_driver = true;
+			rc = add_initcall_dependency(ac->id, parent);
+			if (unlikely(rc))
+				return rc;
+			rc = add_dep_list(node, ac->id);
+			if (unlikely(rc))
+				return rc;
+			for_each_child_of_node(node, child) {
+				rc = add_deps(ac->id, child);
+				if (unlikely(rc))
+					return rc;
+			}
+		}
+		if (found_one_driver)
+			return rc;
+	}
+	for_each_child_of_node(node, child) {
+		rc = add_deps(parent, child);
+		if (unlikely(rc))
+			break;
+	}
+
+	return rc;
+}
+
+int __init of_add_dependencies(void)
+{
+	int rc = 0;
+	struct device_node *child;
+	struct device_node *root =  of_find_node_by_path("/");
+
+	if (unlikely(!root))
+		return -EINVAL;
+
+	for_each_child_of_node(root, child) {
+		rc = add_deps(0, child);
+		if (unlikely(rc))
+			break;
+	}
+	of_node_put(root);
+
+	return rc;
+}
+#endif /* CONFIG_DEPENDENCIES */
diff --git a/include/linux/of.h b/include/linux/of.h
index edc068d..e3b65c8 100644
--- a/include/linux/of.h
+++ b/include/linux/of.h
@@ -1101,4 +1101,7 @@ static inline int of_overlay_destroy_all(void)
 
 #endif
 
+/* Inserts dependencies for drivers referenced in the loaded DT. */
+int __init of_add_dependencies(void);
+
 #endif /* _LINUX_OF_H */
diff --git a/init/dependencies.c b/init/dependencies.c
index c47817c..b484f67 100644
--- a/init/dependencies.c
+++ b/init/dependencies.c
@@ -17,6 +17,7 @@
 #include <linux/device.h>
 #include <linux/mod_devicetable.h>
 #include <linux/init.h>
+#include <linux/of.h>
 
 #if defined(CONFIG_DEPENDENCIES_PRINT_INIT_ORDER) \
 	|| defined(CONFIG_DEPENDENCIES_PRINT_CALLS)
@@ -335,6 +336,9 @@ static int __init build_order(void)
 
 	build_inventory();
 	add_dependencies();
+#ifdef CONFIG_OF
+	of_add_dependencies();
+#endif
 	if (topological_sort())
 		return -EINVAL; /* cycle found */
 	pr_debug("init: vertices: %u edges %u count %u\n",
-- 
2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249369 — [PATCH 06/14] dtc: deps: Automatically add new property 'dependencies' which contains a list of referenced phandles

During the step from .dts to .dtb the information about dependcies
contained in the .dts through phandle references is lost. This makes it
impossible to use the binary blob to create a dependency graph without
knowing the semantic of all cell arrays.

Therefor automatically add a new property called 'dependencies' to all
nodes which have phandle references in one of their properties.

This new property will contain an array of phandles with one value for
every phandle referenced by other properties in the node.

If such a property already exists (e.g. to manually add dependencies
through the .dts), the existing list will be expanded.

Added phandles will be the phandle of either the referenced node itself
(if it has a property named 'compatible', or of the next parent of the
referenced node which as property named 'compatible'. This ensures only
dependencies to drivers will be added.

References to phandles of parent or child nodes will not be added to this
property, because this information is already contained in the blob (in
the form of the tree itself).

No dependencies to disabled nodes will be added.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 scripts/dtc/Makefile       |   3 +-
 scripts/dtc/Makefile.dtc   |   1 +
 scripts/dtc/dependencies.c | 108 +++++++++++++++++++++++++++++++++++++++++++++
 scripts/dtc/dtc.c          |  12 ++++-
 scripts/dtc/dtc.h          |   3 ++
 5 files changed, 125 insertions(+), 2 deletions(-)
 create mode 100644 scripts/dtc/dependencies.c

diff --git a/scripts/dtc/Makefile b/scripts/dtc/Makefile
index 2a48022..1174cf9 100644
--- a/scripts/dtc/Makefile
+++ b/scripts/dtc/Makefile
@@ -4,7 +4,7 @@ hostprogs-y	:= dtc
 always		:= $(hostprogs-y)
 
 dtc-objs	:= dtc.o flattree.o fstree.o data.o livetree.o treesource.o \
-		   srcpos.o checks.o util.o
+		   srcpos.o checks.o util.o dependencies.o
 dtc-objs	+= dtc-lexer.lex.o dtc-parser.tab.o
 
 # Source files need to get at the userspace version of libfdt_env.h to compile
@@ -13,6 +13,7 @@ HOSTCFLAGS_DTC := -I$(src) -I$(src)/libfdt
 
 HOSTCFLAGS_checks.o := $(HOSTCFLAGS_DTC)
 HOSTCFLAGS_data.o := $(HOSTCFLAGS_DTC)
+HOSTCFLAGS_dependencies.o := $(HOSTCFLAGS_DTC)
 HOSTCFLAGS_dtc.o := $(HOSTCFLAGS_DTC)
 HOSTCFLAGS_flattree.o := $(HOSTCFLAGS_DTC)
 HOSTCFLAGS_fstree.o := $(HOSTCFLAGS_DTC)
diff --git a/scripts/dtc/Makefile.dtc b/scripts/dtc/Makefile.dtc
index bece49b..5fb5343 100644
--- a/scripts/dtc/Makefile.dtc
+++ b/scripts/dtc/Makefile.dtc
@@ -6,6 +6,7 @@
 DTC_SRCS = \
 	checks.c \
 	data.c \
+	dependencies.c \
 	dtc.c \
 	flattree.c \
 	fstree.c \
diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c
new file mode 100644
index 0000000..dd4658c
--- /dev/null
+++ b/scripts/dtc/dependencies.c
@@ -0,0 +1,108 @@
+/*
+ * Code to add a property which contains dependencies (used phandle references)
+ * to all (driver) nodes which are having phandle references.
+ *
+ * Copyright (C) 2014 Alexander Holler <holler@ahsoftware.de>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#include <dtc.h>
+
+/* Searches upwards for a node with a property 'compatible' */
+static struct node *find_compatible_not_disabled(struct node *node)
+{
+	struct property *prop;
+
+	while (node) {
+		prop = get_property(node, "compatible");
+		if (prop) {
+			prop = get_property(node, "status");
+			if (prop)
+				if (!prop->val.len ||
+					(strcmp(prop->val.val, "okay") &&
+						strcmp(prop->val.val, "ok")))
+					return NULL; /* disabled */
+			return node;
+		}
+		node = node->parent;
+	}
+	return NULL;
+}
+
+static bool is_parent_of(struct node *node1, struct node *node2)
+{
+	while (node2) {
+		if (node2->parent == node1)
+			return true;
+		node2 = node2->parent;
+	}
+	return false;
+
+}
+
+static void add_deps(struct node *dt, struct node *node, struct property *prop)
+{
+	struct marker *m = prop->val.markers;
+	struct node *refnode;
+	cell_t phandle;
+	struct property *prop_deps;
+	unsigned i;
+	cell_t *cell;
+	struct node *source;
+	struct node *target;
+
+	for_each_marker_of_type(m, REF_PHANDLE) {
+		assert(m->offset + sizeof(cell_t) <= prop->val.len);
+
+		refnode = get_node_by_ref(dt, m->ref);
+		if (!refnode) {
+			fprintf(stderr,
+				"ERROR: Reference to non-existent node or label \"%s\"\n",
+				m->ref);
+			continue;
+		}
+
+		source = find_compatible_not_disabled(node);
+		target = find_compatible_not_disabled(refnode);
+		if (!source || !target || source == target ||
+				is_parent_of(source, target) ||
+				is_parent_of(target, source))
+			continue;
+		phandle = get_node_phandle(dt, target);
+		prop_deps = get_property(source, "dependencies");
+		if (!prop_deps) {
+			add_property(source,
+			     build_property("dependencies",
+				data_append_cell(empty_data, phandle)));
+			continue;
+		}
+		cell = (cell_t *)prop_deps->val.val;
+		for (i = 0; i < prop_deps->val.len/4; ++i)
+			if (*cell++ == cpu_to_fdt32(phandle))
+				break;
+		if (i < prop_deps->val.len/4)
+			continue; /* avoid duplicates */
+		prop_deps->val = data_append_cell(prop_deps->val, phandle);
+	}
+}
+
+static void process_nodes_props(struct node *dt, struct node *node)
+{
+	struct node *child;
+	struct property *prop;
+
+	for_each_property(node, prop)
+		add_deps(dt, node, prop);
+
+	for_each_child(node, child)
+		process_nodes_props(dt, child);
+}
+
+void add_dependencies(struct boot_info *bi)
+{
+	process_nodes_props(bi->dt, bi->dt);
+}
diff --git a/scripts/dtc/dtc.c b/scripts/dtc/dtc.c
index 8c4add6..28def27 100644
--- a/scripts/dtc/dtc.c
+++ b/scripts/dtc/dtc.c
@@ -51,7 +51,7 @@ static void fill_fullpaths(struct node *tree, const char *prefix)
 #define FDT_VERSION(version)	_FDT_VERSION(version)
 #define _FDT_VERSION(version)	#version
 static const char usage_synopsis[] = "dtc [options] <input file>";
-static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sW:E:hv";
+static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sDW:E:hv";
 static struct option const usage_long_opts[] = {
 	{"quiet",            no_argument, NULL, 'q'},
 	{"in-format",         a_argument, NULL, 'I'},
@@ -66,6 +66,7 @@ static struct option const usage_long_opts[] = {
 	{"force",            no_argument, NULL, 'f'},
 	{"include",           a_argument, NULL, 'i'},
 	{"sort",             no_argument, NULL, 's'},
+	{"no-deps",          no_argument, NULL, 'D'},
 	{"phandle",           a_argument, NULL, 'H'},
 	{"warning",           a_argument, NULL, 'W'},
 	{"error",             a_argument, NULL, 'E'},
@@ -93,6 +94,7 @@ static const char * const usage_opts_help[] = {
 	"\n\tTry to produce output even if the input tree has errors",
 	"\n\tAdd a path to search for include files",
 	"\n\tSort nodes and properties before outputting (useful for comparing trees)",
+	"\n\tDo not automatically add dependencies for phandle references",
 	"\n\tValid phandle formats are:\n"
 	 "\t\tlegacy - \"linux,phandle\" properties only\n"
 	 "\t\tepapr  - \"phandle\" properties only\n"
@@ -112,6 +114,7 @@ int main(int argc, char *argv[])
 	const char *outname = "-";
 	const char *depname = NULL;
 	bool force = false, sort = false;
+	bool dependencies = true;
 	const char *arg;
 	int opt;
 	FILE *outf = NULL;
@@ -179,6 +182,10 @@ int main(int argc, char *argv[])
 			sort = true;
 			break;
 
+		case 'D':
+			dependencies = false;
+			break;
+
 		case 'W':
 			parse_checks_option(true, false, optarg);
 			break;
@@ -236,6 +243,9 @@ int main(int argc, char *argv[])
 	if (sort)
 		sort_tree(bi);
 
+	if (dependencies)
+		add_dependencies(bi);
+
 	if (streq(outname, "-")) {
 		outf = stdout;
 	} else {
diff --git a/scripts/dtc/dtc.h b/scripts/dtc/dtc.h
index 56212c8..6facad1 100644
--- a/scripts/dtc/dtc.h
+++ b/scripts/dtc/dtc.h
@@ -266,4 +266,7 @@ struct boot_info *dt_from_source(const char *f);
 
 struct boot_info *dt_from_fs(const char *dirname);
 
+/* Dependencies */
+void add_dependencies(struct boot_info *bi);
+
 #endif /* _DTC_H */
-- 
2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249370 — [PATCH 07/14] dtc: deps: introduce new (virtual) property no-dependencies

In some cases it makes sense to handle some phandles not as dependencies.

This is escpecially true for 'remote-endpoint' properties, because these
otherwise introducing dependency cycles into the graph. To avoid these,
one end of each remote-endpoint pairs has not to be handled as a
dependency.

The syntax is like

	foo {
		remote-endpoint = <&bar>;
	};
	bar {
		remote-endpoint = <&foo>;
		no-dependencies = <&foo>;
	};

Without that 'no-dependencies' property dtc would automatically add a
dependency to foo to the property 'dependencies' of the node bar.
But with that 'no-dependencies' it will not automatically add the
listed dependencies.

The property 'no-dependencies' is virtual property and will not be added
to any output file.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 scripts/dtc/dependencies.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c
index dd4658c..77d5c54 100644
--- a/scripts/dtc/dependencies.c
+++ b/scripts/dtc/dependencies.c
@@ -44,6 +44,23 @@ static bool is_parent_of(struct node *node1, struct node *node2)
 
 }
 
+static bool is_no_dependency(struct node *dt, struct property *prop, cell_t ph)
+{
+	struct node *node;
+	unsigned i;
+	cell_t *cell = (cell_t *)(prop->val.val);
+
+	for (i = 0; i < prop->val.len/4; ++i) {
+		node = get_node_by_phandle(dt, cpu_to_fdt32(*cell++));
+		if (node) {
+			node = find_compatible_not_disabled(node);
+			if (node && get_node_phandle(dt, node) == ph)
+				return true;
+		}
+	}
+	return false;
+}
+
 static void add_deps(struct node *dt, struct node *node, struct property *prop)
 {
 	struct marker *m = prop->val.markers;
@@ -73,6 +90,10 @@ static void add_deps(struct node *dt, struct node *node, struct property *prop)
 				is_parent_of(target, source))
 			continue;
 		phandle = get_node_phandle(dt, target);
+		prop_deps = get_property(node, "no-dependencies");
+		if (prop_deps && is_no_dependency(dt, prop_deps, phandle))
+			/* avoid adding non-dependencies */
+			continue;
 		prop_deps = get_property(source, "dependencies");
 		if (!prop_deps) {
 			add_property(source,
@@ -102,7 +123,19 @@ static void process_nodes_props(struct node *dt, struct node *node)
 		process_nodes_props(dt, child);
 }
 
+static void del_prop_no_dependencies(struct node *node)
+{
+	struct node *child;
+
+	if (!node)
+		return;
+	delete_property_by_name(node, "no-dependencies");
+	for_each_child(node, child)
+		del_prop_no_dependencies(child);
+}
+
 void add_dependencies(struct boot_info *bi)
 {
 	process_nodes_props(bi->dt, bi->dt);
+	del_prop_no_dependencies(bi->dt);
 }
-- 
2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1249371 — [PATCH 09/14] dtc: deps: Add option to print dependency graph as dot (Graphviz)

Add option -T do print a dependency graph in dot format for
generating a picture with Graphviz.

E.g.

	dtc -T foo.dts | dot -T svg -o foo.svg

would generate the picture foo.png with the dependency graph.

Convential dependencies (those based on the tree structure) are having
black arrows, dependencies based on the property 'dependencies' are
having cyan arrows.

Option -D to not automatically add dependencies does still work, so
you could build a classic dependency graph with

	dtc -D -T foo.dts | dot -T png -o foo_no_auto_deps.png

This works with binary blobs as input too. E.g.

	CROSS_COMPILE=gcc-foo ARCH=arm make foo.dtb
	scripts/dtc/dtc -I dtb -T arch/arm/boot/dts/foo.dtb

would print the dot file.

Signed-off-by: Alexander Holler <holler@ahsoftware.de>
---
 scripts/dtc/dependencies.c | 49 ++++++++++++++++++++++++++++++++++++++++------
 scripts/dtc/dtc.c          | 19 +++++++++++++++---
 scripts/dtc/dtc.h          |  2 +-
 3 files changed, 60 insertions(+), 10 deletions(-)

diff --git a/scripts/dtc/dependencies.c b/scripts/dtc/dependencies.c
index 360d8f5..76e4d91 100644
--- a/scripts/dtc/dependencies.c
+++ b/scripts/dtc/dependencies.c
@@ -331,7 +331,7 @@ static void __init topological_sort(void)
 			depth_first_search(i);
 }
 
-static int __init add_dep_list(struct device_node *node)
+static int __init add_dep_list(struct device_node *node, bool print_dot)
 {
 	const __be32 *list, *list_end;
 	uint32_t ph;
@@ -361,6 +361,9 @@ static int __init add_dep_list(struct device_node *node)
 		rc = insert_edge(node->phandle, ph);
 		if (rc)
 			break;
+		if (print_dot)
+			printf("      node0x%x -> node0x%x [color=cyan]\n",
+				node->phandle, ph);
 	}
 
 	return rc;
@@ -385,9 +388,10 @@ static const char *of_prop_next_string(struct property *prop, const char *cur)
 }
 
 static int __init add_deps_lnx(struct device_node *parent,
-				struct device_node *node)
+				struct device_node *node, bool print_dot)
 {
 	struct device_node *child;
+	const char *cp;
 	int rc = 0;
 
 	if (!__of_device_is_available(node))
@@ -408,13 +412,34 @@ static int __init add_deps_lnx(struct device_node *parent,
 			return -EINVAL;
 		}
 		order.parent_by_phandle[node->phandle] = parent->phandle;
-		rc = add_dep_list(node);
+		if (print_dot) {
+			struct property *prop;
+
+			printf("    node0x%x [label=\"0x%x %s", node->phandle,
+						node->phandle, node->name);
+			if (node->full_name)
+				printf(" (%s)", node->full_name);
+			prop = get_property(node, "compatible");
+			if (prop) {
+				printf("\\n");
+				for (cp = of_prop_next_string(prop, NULL); cp;
+				     cp = of_prop_next_string(prop, cp)) {
+					if (cp != prop->val.val)
+						putchar(' ');
+					printf("%s", cp);
+				}
+			}
+			printf("\"];\n");
+			printf("      node0x%x -> node0x%x\n", node->phandle,
+							parent->phandle);
+		}
+		rc = add_dep_list(node, print_dot);
 		if (unlikely(rc))
 			return rc;
 		parent = node; /* change the parent only if node is a driver */
 	}
 	for_each_child_of_node(node, child) {
-		rc = add_deps_lnx(parent, child);
+		rc = add_deps_lnx(parent, child, print_dot);
 		if (unlikely(rc))
 			break;
 	}
@@ -457,7 +482,7 @@ void __init of_init_print_order(const char *name)
 	}
 }
 
-int __init of_init_build_order(struct device_node *root)
+int __init of_init_build_order(struct device_node *root, const char *print_dot)
 {
 	struct device_node *child;
 	int rc = 0;
@@ -469,12 +494,24 @@ int __init of_init_build_order(struct device_node *root)
 	calc_max_phandle(root);
 	order.old_max_phandle = order.max_phandle;
 
+	if (print_dot) {
+		printf("digraph G {\n");
+		printf("    node0x%x [label=\"0x%x root (/)\"];\n",
+			order.max_phandle+1, order.max_phandle+1);
+	}
+
 	for_each_child_of_node(root, child) {
-		rc = add_deps_lnx(root, child);
+		rc = add_deps_lnx(root, child, print_dot);
 		if (unlikely(rc))
 			break;
 	}
 
+	if (print_dot) {
+		printf("  graph [label=\"Dependency Graph for %s (%u nodes, %u edges)\"];\n",
+			print_dot, graph.nvertices, graph.nedges);
+		printf("}\n");
+	}
+
 	of_node_put(root);
 	topological_sort();
 
diff --git a/scripts/dtc/dtc.c b/scripts/dtc/dtc.c
index 494c531..b1ca363 100644
--- a/scripts/dtc/dtc.c
+++ b/scripts/dtc/dtc.c
@@ -51,7 +51,7 @@ static void fill_fullpaths(struct node *tree, const char *prefix)
 #define FDT_VERSION(version)	_FDT_VERSION(version)
 #define _FDT_VERSION(version)	#version
 static const char usage_synopsis[] = "dtc [options] <input file>";
-static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sDtW:E:hv";
+static const char usage_short_opts[] = "qI:O:o:V:d:R:S:p:fb:i:H:sDtTW:E:hv";
 static struct option const usage_long_opts[] = {
 	{"quiet",            no_argument, NULL, 'q'},
 	{"in-format",         a_argument, NULL, 'I'},
@@ -68,6 +68,7 @@ static struct option const usage_long_opts[] = {
 	{"sort",             no_argument, NULL, 's'},
 	{"no-deps",          no_argument, NULL, 'D'},
 	{"initialization-order", no_argument, NULL, 't'},
+	{"dot",              no_argument, NULL, 'T'},
 	{"phandle",           a_argument, NULL, 'H'},
 	{"warning",           a_argument, NULL, 'W'},
 	{"error",             a_argument, NULL, 'E'},
@@ -97,6 +98,7 @@ static const char * const usage_opts_help[] = {
 	"\n\tSort nodes and properties before outputting (useful for comparing trees)",
 	"\n\tDo not automatically add dependencies for phandle references",
 	"\n\tPrint (default) initialization order",
+	"\n\tPrint dot with dependency graph (for use with Graphviz)",
 	"\n\tValid phandle formats are:\n"
 	 "\t\tlegacy - \"linux,phandle\" properties only\n"
 	 "\t\tepapr  - \"phandle\" properties only\n"
@@ -118,6 +120,7 @@ int main(int argc, char *argv[])
 	bool force = false, sort = false;
 	bool dependencies = true;
 	bool init_order = false;
+	bool print_dot = false;
 	const char *arg;
 	int opt;
 	FILE *outf = NULL;
@@ -193,6 +196,10 @@ int main(int argc, char *argv[])
 			init_order = true;
 			break;
 
+		case 'T':
+			print_dot = true;
+			break;
+
 		case 'W':
 			parse_checks_option(true, false, optarg);
 			break;
@@ -254,12 +261,18 @@ int main(int argc, char *argv[])
 		add_dependencies(bi);
 
 	if (init_order) {
-		if (of_init_build_order(bi->dt))
+		if (of_init_build_order(bi->dt, 0))
 			exit(2);
 		of_init_print_order(arg);
 		exit(0);
 	}
 
+	if (print_dot) {
+		if (of_init_build_order(bi->dt, arg))
+			exit(2);
+		exit(0);
+	}
+
 	if (streq(outname, "-")) {
 		outf = stdout;
 	} else {
@@ -286,7 +299,7 @@ int main(int argc, char *argv[])
 	 * This is done after the output was saved because it
 	 * changes the tree slightly.
 	 */
-	if (of_init_build_order(bi->dt))
+	if (of_init_build_order(bi->dt, 0))
 		exit(2);
 
 	exit(0);
diff --git a/scripts/dtc/dtc.h b/scripts/dtc/dtc.h
index 9ae4bfc..8ef8e6f 100644
--- a/scripts/dtc/dtc.h
+++ b/scripts/dtc/dtc.h
@@ -269,6 +269,6 @@ struct boot_info *dt_from_fs(const char *dirname);
 /* Dependencies */
 void add_dependencies(struct boot_info *bi);
 void of_init_print_order(const char *name);
-int of_init_build_order(struct node *root);
+int of_init_build_order(struct node *root, const char *print_dot);
 
 #endif /* _DTC_H */
-- 
2.1.0

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web