Re: [Qemu-devel] [PATCH 6/6] block: Fix permissions after bdrv_reopen()

[Kevin Wolf <kwolf@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 2171 bytes --]

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 <kwolf@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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 801 bytes --]