Re: [RFC PATCH v3] drivercore: Add driver probe deferral mechanism

[Valdis . Kletnieks]

On Thu, 22 Sep 2011 15:19:01 MDT, Grant Likely said:
> On Thu, Sep 22, 2011 at 2:29 PM, Alan Cox <alan@xxxxxxxxxxxxxxxxxxx> wrote:
> > Definitely what is needed for some of the x86 SoC stuff and would let us
> > rip out some of the special case magic for the SCU discovery.
> >
> > First thing that strikes me is driver_bound kicks the processing queue
> > again. That seems odd - surely this isn't needed because any driver that
> > does initialise this time and may allow something else to get going will
> > queue the kick itself. Thus this seems to just add overhead.
> >
> > It all looks a bit O(N²) if we don't expect the drivers that might
> > trigger something else binding to just say 'hey I'm one of the
> > troublemakers'
> 
> The way I read it, absolute worst case is when every device but one
> depends on another device.  In that case I believe it will be
> O(Nlog(N)).  (Every device gets probed on the first pass, but only the
> last one gets probed.  Then it goes through N-1 devices to the result
> of only 1 more device getting probed, then N-2, etc.). 

That is indeed O(N**2) not Nlog(N).  The total number of probes is (N+1)(N)/2
To get it to O(Nlog(N)), you'd have to probe N devices the first pass, N/2 devices
on the second pass, N/4 on the third, and so on.

Attachment: pgp00000.pgp
Description: PGP signature