Re: [PATCH 2/5] drivercore: Add driver probe deferral mechanism

Alan Stern
2011-10-14T15:37:41Z

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