On Thu, 13 Oct 2011, Grant Likely wrote: > For the deferred case; here is an example of the additional > constraint. Consider the following hierarchy: > > -A > +-B > | +-C > | +-D > | > +-E > +-F > +-G > > dpm_list could be ordered in at least the following ways (depending on > exactly when devices get registered). There are many permutation, but > children are always be listed after its direct parent. > > 1) ABECDFG (breadth first) > 2) AEBFGCD (breadth first) > 3) ABCDEFG (depth first) > 4) AEFGBCD (depth first) > > Now, assume that device B depends on device F, and also assume that > there is no way either to express that in the hierarchy or even for > the constraint to be known at device registration time (the is exactly > the situation we're dealing with on embedded platforms). Only the > driver for B knows that it needs a resource provided by F's driver. > So, the situation becomes that the ordering of dpm_list must now also > be sorted so that non-tree dependencies are also accounted for. Of > the list above, only sort order 4 meets the new constraint. > > The question then becomes, how can the dpm_list get resorted > dynamically at runtime to ensure that the new constraints are always > met without breaking old ones. Here are some options I can think of: > > 1) When a deferred probe succeeds, move the deferred device to the > end of the dpm_list. Then the new sort order might be one of: > > 1) AECDFGB > 2) AEFGCDB > 3) ACDEFGB > 4) AEFGCDB > > However, that approach breaks the guarantee that children appear after > their parents (C & D appear before B in all cases above) How can a device acquire children before it has a driver? > 2a) When a deferred probe succeeds, move the deferred device and it's > entire child hierarchy to the end of the list to become one of: This is the same as the above, under the reasonable assumption that devices without drivers can't have any children. Or to be more carefully precise, that a device with children won't need to defer a probe. We can check that easily enough: Fail a deferral if the device already has children. > 2b) alternately, when *any* probe succeeds, move the deferred device > and its children to the end of the list. This continues to maintain > the parent-child relationship, and it ensures that the dpm_list is > always also sorted in probe-order (devices bound to drivers will > collect at the end of the list). We do not want to move entire hierarchies. And in fact, even in 1 or 2a, we would have to do the move from _within_ the deferred probe routine, not afterward, to make sure that it occurs before any children are added (and after all the prerequisite devices have been registered). > 3) Add devices to dpm_list after successful probe instead of at > device_add time. > > Potential problem: this means that only devices with drivers actually > get suspend/resume calls. I don't know nearly enough about the PM > subsystem, but I suspect that this is a problem. Yes, this is no good. > 4) ignore parent-child relationships entirely and just move devices to > the end of the list on successful probe. If it probed successfully, > then it can be successfully suspended regardless of whether it has any > children. That breaks the parent-child ordering, but guarantees the > probe order ordering. Any devices without drivers will end up > collecting at the beginning of the list, and will be suspended after > all the devices with drivers. > > Problem: Same as with 3, I suspect that even devices without drivers > need to process PM suspend, which makes this option unworkable. > > ... > > For my money, I think that option 2b shows the most promise despite > the potential O(N^2) complexity. There may be a better algorithm for > doing the runtime reordering that isn't O(N^2) that I haven't thought > of. Having a list that is strongly ordered both on hierarchy *and* > probe order I think is the right thing to do, even without deferred > probe support. The answer is 1, but do the move at the appropriate time within the probe routine. Alan Stern -- To unsubscribe from this list: send the line "unsubscribe linux-mmc" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
