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 <[email protected]> > > --- > > 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
