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

[Grant Likely]

On Mon, 12 May 2014 18:47:51 +0200, Alexander Holler <holler@xxxxxxxxxxxxx> wrote:
> 
> 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.

Rather than a dtb schema change, for the most common properties (irqs,
clocks, gpios), we could extract dependencies at boot time. I don't like
the idea of adding a separate depends-on property because it is very
easy to get it out of sync with the actual binding data (dtc is not the
only tool that manipulates .dtbs. Firmware will fiddle with it too).

g.

> - 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.
> 
> 
> _______________________________________________
> linux-arm-kernel mailing list
> linux-arm-kernel@xxxxxxxxxxxxxxxxxxx
> http://lists.infradead.org/mailman/listinfo/linux-arm-kernel

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