Am 15.09.2017 um 21:06 hat Eric Blake geschrieben:
> On 09/15/2017 05:10 AM, Kevin Wolf wrote:
> > If we switch between read-only and read-write, the permissions that
> > image format drivers need on bs->file change, too. Make sure to update
> > the permissions during bdrv_reopen().
> >
> > Signed-off-by: Kevin Wolf
> > ---
> > include/block/block.h | 1 +
> > block.c | 64
> > +++
> > 2 files changed, 65 insertions(+)
> >
>
> > +static BlockReopenQueueEntry *find_parent_in_reopen_queue(BlockReopenQueue
> > *q,
> > + BdrvChild *c)
> > +{
> > +BlockReopenQueueEntry *entry;
> > +
> > +QSIMPLEQ_FOREACH(entry, q, entry) {
> > +BlockDriverState *bs = entry->state.bs;
> > +BdrvChild *child;
> > +
> > +QLIST_FOREACH(child, &bs->children, next) {
> > +if (child == c) {
> > +return entry;
>
> An O(n^2) loop. Is it going to bite us at any point in the future, or
> are we generally dealing with a small enough queue size and BDS graph to
> not worry about it?
The loops you're quoting aren't O(n^2), they don't loop over the same
thing. This part is O(n) in terms of BdrvChild elements looked at.
The thing that worried me a bit more is the caller:
+QLIST_FOREACH(c, &bs->parents, next_parent) {
+parent = find_parent_in_reopen_queue(q, c);
This is indeed O(n^2) (again with n = number of BdrvChild elements) in
the pathological worst case of a quorum node where all children point to
the same node.
As soon as all parents of the node are distinct - and I don't see any
reason why they wouldn't in practice - we're back to O(n) because each
BdrvChild belongs to only one parent. Even if we ever introduce a driver
where having the same node as a child in a constant number of different
roles makes sense for a parent (i.e. anything that doesn't involve an
(unbounded) array of children), we would still be O(n) with an additional
small constant factor.
So I think in practice we should be okay.
Kevin
signature.asc
Description: PGP signature
