[RFC PATCH 0/9] dt: dependencies (for deterministic driver initialization order based on the DT)

[Alexander Holler]

Hello,

if I would have to describe the Linux kernels init system (before userspace
starts), it would be like:
Unknown functions with almost unknown functionality are called in an almost
random order.

That reminded me that a kernel-maintainer once said to me:
"We should aim to make things synchronous, deterministic and
stuff-happens-in-the-correct-order."

Looks like either the target moved or no Wilhelm Tell was around. ;)

This is an attempt to reach the target for the case of (platform-)drivers.
It is a mere starting point to reach the final target but it works on two
DT enabled ARM devices I have and it hasn't any implications on other
architectures, platforms or whatever. If the new configuration option,
which is only available if DT is enabled, isn't turned on, there is no
increase of code size or similiar.

So what are these patches I'm posting here?
They offer an imho solid base to fix the 3. problem. they build a deterministic
order in which (platform-)drivers should be initialized, based on datas
(dependencies) found in the device tree. They also offer a starting point to fix
the other 2 problems (unknown functions and unknown functionality) by showing a
way how the long range target of known functions with known functionality could
be reached.

Unfortunately work still isn't done. As written above, this is just a starting
point, neiter complete nor perfect. It is what I could do behind closed doors,
by spending a limited amount of time and resources (I've started to look at
that stuff 3-4 weeks ago, sometimes after 3.14 appeared), so it can be blamed
quick & dirty. But it should be already enough to explain and test the concepts.

Enough forewords.

This is a small patch series to use a deterministic dependency based device
and driver initialization order on machines which are using device tree.
The dependency graph will not only be build based on the device tree itself,
but will use dependencies based on phandle references in the .dts,
automatically added by dtc through a new property.
Manualy adding dependencies to the .dts is possible too.

Advantages:

- Correct order of initialization without any "dirty tricks" in drivers or the
  machine init code. The order in which devices/drivers will be initialized
  depends only on the DT and the topological sort algorithm used by the
  kernel, not some code elsewhere. That means less code and more homogeneity
  across different SOCs.
- Might be(come) a little faster because the number of deferred probes should
  be minimized (they might not even be necessary anymore at all).
- Using a modified algorithm, it's possible to build a list of drivers which
  can be initialized in parallel, e.g. using n threads, where n equals the
  number of cores. I have not tested nor implemented it, because I don't have
  any multicore DT based board with which I easily can use a (patched) mainline
  kernel, just locked down multicore things I don't want to go through the
  pain of unlocking them.
- Funny dependency graphs when using Graphviz.

Disadvantages:

- To use this feature correctly, binary blobs must be regenerated by
  recompiling them to include properties with dependencies. Without
  recompiling them there will be no advantage.
- Binary blobs will be slightly larger (some kb, see numbers below).
- Many .dts might need manual work to add some dependencies. Also most
  dependencies will be discovered automatically (based on phandle references
  in the .dts, some devices might need additional dependencies.


Some numbers (using kernel 3.14.3):

Dockstar (Kirkwood):
	Works out of the box.
	Size of dtb without dependencies:	9166
	Size of dtb with dependencies:		9579
	Graph with 34 nodes, 56 edges
	Boot to panic (no root) no deps run 1-4:
	1.325474 1.325458 1.325449 1.325494
	Boot to panic (no root) deps run 1-4:
	4.509989 4.484608 4.316221 4.485310
	The large difference in time isn't because of the depency based
	init but because ehci detected the connected hd before the panic
	occured when deps were enabled. Withoout deps, the panic
	already happend without any discovered usb-storage. I haven't
	checked why.
	The actual times to boot from USB-HD are 3.417248 without
	dependencies versus 5.618293 with. I still have to check where
	the difference of more than a second does come from, a difference
	like on the BBB (see below) should be more reasonable.

BeagleBoneBlack A5C (AM3359):
	Had to disable ethernet (driver crashes).
	Size of dtb without dependencies:	31379
	Size of dtb with dependencies:		33300
	Graph with 145 nodes, 266 edges
	Boot to panic (no root) no deps run 1-4:
	1.229431 1.229516 1.229509 1.229557
	Boot to panic (no root) deps run 1-4:
	1.361780 1.361442 1.361532 1.361699

BeagleBoard C4 (OMAP34xx):
	Had to disable usb (driver crashes) and several other problems,
	but an unpatched 3.14.y doesn't really work too (which was the
	reason I looked at what happes and did these patches).
	Size of dtb without dependencies:	57003
	Size of dtb with dependencies:		62580
	Graph with 390 nodes, 848 edges
	Boot to panic (no root) no deps run 1-4:
	3.386535 3.343566 3.381469 3.357208
	Boot to panic (no root) deps run 1-4:
	5.961425 5.907714 6.053680 5.957855

The difference in boot time is mainly based on the function which
matches drivers to devices based on the compatible string. This
is currently not solved very elegant and walks through multiple
list multiple times. The actual sorting is very fast (just some ms).

For people which do like pictures, I've put the dependency graph for
the Dockstar online: http://ahsoftware.de/dt-kirkwood-dockstar.svg
And a far more complicated dependency graph for the BeagleBoard:
http://ahsoftware.de/dt-omap3-beagle.svg

These pictures makes it easy to see what this feature is about. All the cyan
arrows are the new dependencies, the black ones are the dependecies as
currently used (for device but not driver initialization). So you see, there
is quiet a difference.
If I'm right, those pictures also visualize which drivers could be initialized
in parallel (I haven't checked it, I would have to read the Graphviz
documentation or check the whole graph to be sure). But on a first look at it,
it looks like dot (Graphviz) placed all the nodes which can be initialized in
parallel on the same row. So there are quiet some drivers which could be
initialized in parallel, taking advantage of multiple cores to reduce boot time.

(Just in case you wonder what the first number in the nodes in the pictures
might be, it is the phandle of the device tree node and is usually generated
automatically by dtc and might change when the .dts changes. This number
doesn't have any meaning in regard to the initialization order.)

What follows are the patches I've done, ready to test this feature. These are

- 3 patches for the in-kernel dtc (to add dependencies to the dtb),
- 1 patch for the kernel to use these dependencies to build the initialization
  order and create devices,
- 1 patch to register drivers based on the built order,
- 1 patch to show which changes are necessary for some drivers,
- 2 patches to use this feature on kirkwood (very good as small example),
- 1 patch to use this feature on omap2+ (and am33xx),

These patches are based on 3.14.3 and unfortunately don't apply cleanly to
3.15-rcN. But I'm currently too lazy to rebase them as I usually use a stable
kernel to test things I change. And as this is just a RFC, please use 3.14.x
to test these patches.

All patches do explain further what and how they do. And if I get the OK
that they will be merged (after any necessary clean up), I would write
a document for Documentation too (if really wanted, I assume you already have
noticed that I'm not a native english speaker/writer).

My suggestion to continue:

- Merge the first 5 patches (maybe after they got cleaned up). So they won't
disappear and people will find a starting point in the kernel to continue
work on. They don't do any harm and don't increase codesize if the new
kernel option they introduce is disabled. It also might be a good idea to
merge them in order to get the new dependencies into binary DT blobs
as early as possible, even if it might still need some time until they
really will be used.

- Have a look at the other patches. Especially the one for the Kirkwood which
changes the initializazion order by just adding one dependency (ehci vs.
regulator) to the .dts. This shows how such could be done without any changes
on the drivers source code.


If you ask why I did those patches: For the same reason a mountain climber
does climb a mountain. That also explains my limited motivation and
resources. ;)


Regards,

Alexander Holler


LKML-disclaimer (unfortunately necessary):
Please keep away with comments about style, typos or spelling errors in
comments and similiar silly stuff if you have nothing else to say.
Feel free to comment functionality or real errors, but not style, form or
other bureaucrazy things.
And please keep in mind that I'm neiter your intern, your student, your pupil,
nor your child.