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 <kw...@redhat.com> > > --- > > 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