Re: [PATCH v2 15/36] block: use topological sort for permission update

[Vladimir Sementsov-Ogievskiy]

03.02.2021 21:38, Kevin Wolf wrote:
> Am 28.01.2021 um 19:04 hat Vladimir Sementsov-Ogievskiy geschrieben:
> > 28.01.2021 20:13, Kevin Wolf wrote:
> > > Am 28.01.2021 um 10:34 hat Vladimir Sementsov-Ogievskiy geschrieben:
> > > > 27.01.2021 21:38, Kevin Wolf wrote:
> > > > > Am 27.11.2020 um 15:45 hat Vladimir Sementsov-Ogievskiy geschrieben:
> > > > > > -static int bdrv_check_perm(BlockDriverState *bs, BlockReopenQueue *q,
> > > > > > -                           uint64_t cumulative_perms,
> > > > > > -                           uint64_t cumulative_shared_perms,
> > > > > > -                           GSList *ignore_children, Error **errp)
> > > > > > +static int bdrv_node_check_perm(BlockDriverState *bs, BlockReopenQueue *q,
> > > > > > +                                uint64_t cumulative_perms,
> > > > > > +                                uint64_t cumulative_shared_perms,
> > > > > > +                                GSList *ignore_children, Error **errp)
> > > > > >     {
> > > > > >         BlockDriver *drv = bs->drv;
> > > > > >         BdrvChild *c;
> > > > > > @@ -2166,21 +2193,43 @@ static int bdrv_check_perm(BlockDriverState *bs, 
> > > > > > BlockReopenQueue *q,
> > > > > >         /* Check all children */
> > > > > >         QLIST_FOREACH(c, &bs->children, next) {
> > > > > >             uint64_t cur_perm, cur_shared;
> > > > > > -        GSList *cur_ignore_children;
> > > > > >             bdrv_child_perm(bs, c->bs, c, c->role, q,
> > > > > >                             cumulative_perms, cumulative_shared_perms,
> > > > > >                             &cur_perm, &cur_shared);
> > > > > > +        bdrv_child_set_perm_safe(c, cur_perm, cur_shared, NULL);
> > > > >
> > > > > This "added" line is actually old code. What is removed here is the
> > > > > recursive call of bdrv_check_update_perm(). This is what the code below
> > > > > will have to replace.
> > > >
> > > > yes, we'll use explicit loop instead of recursion
> > > >
> > > > > > +    }
> > > > > > +
> > > > > > +    return 0;
> > > > > > +}
> > > > > > +
> > > > > > +static int bdrv_check_perm(BlockDriverState *bs, BlockReopenQueue *q,
> > > > > > +                           uint64_t cumulative_perms,
> > > > > > +                           uint64_t cumulative_shared_perms,
> > > > > > +                           GSList *ignore_children, Error **errp)
> > > > > > +{
> > > > > > +    int ret;
> > > > > > +    BlockDriverState *root = bs;
> > > > > > +    g_autoptr(GSList) list = bdrv_topological_dfs(NULL, NULL, root);
> > > > > > +
> > > > > > +    for ( ; list; list = list->next) {
> > > > > > +        bs = list->data;
> > > > > > +
> > > > > > +        if (bs != root) {
> > > > > > +            if (!bdrv_check_parents_compliance(bs, ignore_children, errp)) {
> > > > > > +                return -EINVAL;
> > > > > > +            }
> > > > >
> > > > > At this point bs still had the old permissions, but we don't access
> > > > > them. As we're going in topological order, the parents have already been
> > > > > updated if they were a child covered in bdrv_node_check_perm(), so we're
> > > > > checking the relevant values. Good.
> > > > >
> > > > > What about the root node? If I understand correctly, the parents of the
> > > > > root nodes wouldn't have been checked in the old code. In the new state,
> > > > > the parent BdrvChild already has to contain the new permission.
> > > > >
> > > > > In bdrv_refresh_perms(), we already check parent conflicts, so no change
> > > > > for all callers going through it. Good.
> > > > >
> > > > > bdrv_reopen_multiple() is less obvious. It passes permissions from the
> > > > > BDRVReopenState, without applying the permissions first.
> > > >
> > > > It will be changed in the series
> > > >
> > > > > Do we check the
> > > > > old parent permissions instead of the new state here?
> > > >
> > > > We use given (new) cumulative permissions for bs, and recalculate
> > > > permissions for bs subtree.
> > >
> > > Where do we actually set them? I would expect a
> > > bdrv_child_set_perm_safe() call somewhere, but I can't see it in the
> > > call path from bdrv_reopen_multiple().
> >
> > You mean parent BdrvChild objects? Then this question applies as well
> > to pre-patch code.
>
> I don't think so. The pre-patch code doesn't rely on the permissions
> already being set in the BdrvChild object, but it gets them passed in
> parameters. Changing the graph first and relying on the information in
> BdrvChild is the new approach that you're introducing.

New code still pass permissions as parameters for root node. And only
inside subtree we rely on updated parents. But that's correct due to
topological order of updating.


OK, that's incorrect for the following case: when one of the parents (X)
of inner node in bs subtree IS NOT in the bs subtree but IS in reopen queue.
And we'll use wrong permission of X. Still:

1. It's preexisting. bdrv_check_update_perm() doesn't take reopen queue
in mind when calculate cumulative permissions (and ignore_children doesn't
help for the described case

2. We can hope that on next permission update, started from node X, permissions
will become more correct

3. At the end of series permission calculation in bdrv_reopen_multiple is
rewritten anyway.


> > So, we just call bdrv_check_perm() for bs in bdrv_reopen_multiple.. I
> > think the answer is like this:
> >
> > if state->perm and state->shared_perm are different from actual
> > cumulative permissions (before reopne), then we must have the
> > parent(s) of the node in same bs_queue. Then, corresponding children
> > are updated as part of another bdrv_check_perm call from same loop in
> > bdrv_reopen_multiple().
> >
> > Let's check how state->perm and state->shared_perm are set:
> >
> > bdrv_reopen_queue_child()
> >
> >      /* This needs to be overwritten in bdrv_reopen_prepare() */
> >      bs_entry->state.perm = UINT64_MAX;
> >      bs_entry->state.shared_perm = 0;
> >
> >
> > ...
> > bdrv_reopen_prepare()
> >
> >         bdrv_reopen_perm(queue, reopen_state->bs,
> >                       &reopen_state->perm, &reopen_state->shared_perm);
> >
> > and bdrv_reopen_perm() calculate cumulative permissions, taking
> > permissions from the queue, for parents which exists in queue.
>
> Right, but it stores the new permissions in reopen_state, not in the
> BdrvChild objects that this patch is looking it. Or am I missing
> something?
>
> > Not sure how much it correct, keeping in mind that we may look at a
> > node in queue, for which bdrv_reopen_perm was not yet called, but the
> > idea is clean.
>
> I don't think the above code can work correctly without something
> actually updating the BdrvChild first.
>
> > > > It follows old behavior. The only thing is changed that pre-patch we
> > > > do DFS recursion starting from bs (and probably visit some nodes
> > > > several times), after-patch we first do topological sort of bs subtree
> > > > and go through the list. The order of nodes is better and we visit
> > > > each node once.
> > >
> > > It's not the only thing that changes. Maybe this is what makes the patch
> > > hard to understand, because it seems to do two steps at once:
> > >
> > > 1. Change the order in which nodes are processed
> > >
> > > 2. Replace bdrv_check_update_perm() with bdrv_check_parents_compliance()
> >
> > hmm, yes. But we do bdrv_check_parents_compliance() only for nodes
> > inside subtree, for all except root.  So, for them we have updated
> > permissions.
>
> Ah! This might be the missing piece that makes it safe.
>
> Maybe worth a comment?
>
> Kevin


--
Best regards,
Vladimir