On Mon, Nov 14, 2016 at 02:48:32PM +0100, Luis R. Rodriguez wrote: > On Sun, Nov 13, 2016 at 06:34:13PM +0100, Lukas Wunner wrote: > > On Mon, Nov 07, 2016 at 10:39:54PM +0100, Luis R. Rodriguez wrote: > > > On Mon, Oct 10, 2016 at 02:51:04PM +0200, Rafael J. Wysocki wrote: > > > > One of the actions carried out by device_link_add() is to reorder > > > > the lists used for device shutdown and system suspend/resume to > > > > put the consumer device along with all of its children and all of > > > > its consumers (and so on, recursively) to the ends of those lists > > > > in order to ensure the right ordering between all of the supplier > > > > and consumer devices. > > > > > > There's no explanation as to why this order is ensured to be > > > correct, I think its important to document this. From our discussions > > > at Plumbers it seems the order is ensured due to the fact that order > > > was already implicitly provided through platform firmware (ACPI > > > enumeration is one), adjusting order on the dpm list is just shuffling > > > order between consumer / provider, but nothing else. > > > > ACPI specifies a hierarchy and the order on the dpm_list and > > devices_kset is such that children are behind their parent. > > > > A device link specifies a dependency that exists in addition > > to the hierarchy, hence consumers need to be moved behind > > their supplier. And not only the consumers themselves but > > also recursively their children and consumers. Essentially > > the entire subtree is moved to the back. That happens in > > device_reorder_to_tail() in patch 2. > > Ah neat, I failed to notice this full subtree tree move, its > rather important. > > > If another device is enumerated which acts as a supplier to > > an existing other supplier, that other supplier and all its > > dependents are moved behind the newly enumerated device, > > and so on. > > > > That is probably correct so long as no loops are introduced > > in the dependency graph. > > "Probably" is what concerns me, there is no formality about > the correctness of this.
It's a typo, I meant to say "provably correct". Sorry. Quite a difference in meaning. :-) > > That is checked by device_is_dependent(), > > which is called from device_link_add(), and the addition of the > > link is aborted if a loop is detected. > > And that is sufficient ? The device links turn the device tree into a directed acyclic graph. For the dpm_list and devices_kset, that graph is flattened into a one-dimensional form such that all ancestors and suppliers of a device appear in front of that device in the lists. I'm not a graph theorist and can't provide a formal proof. I think Rafael is a Dr., maybe he can do it. :-) I merely looked at this from a practical point of view, i.e. I tried to come up with corner cases where dependencies are added that would result in incorrect ordering, and concluded that I couldn't find any. Thanks, Lukas