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. -- To unsubscribe from this list: send the line "unsubscribe devicetree" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
