Skip to content
  • Vladimir Sementsov-Ogievskiy's avatar
    bd57f8f7
    block: use topological sort for permission update · bd57f8f7
    Vladimir Sementsov-Ogievskiy authored
    
    
    Rewrite bdrv_check_perm(), bdrv_abort_perm_update() and bdrv_set_perm()
    to update nodes in topological sort order instead of simple DFS. With
    topologically sorted nodes, we update a node only when all its parents
    already updated. With DFS it's not so.
    
    Consider the following example:
    
        A -+
        |  |
        |  v
        |  B
        |  |
        v  |
        C<-+
    
    A is parent for B and C, B is parent for C.
    
    Obviously, to update permissions, we should go in order A B C, so, when
    we update C, all parent permissions already updated. But with current
    approach (simple recursion) we can update in sequence A C B C (C is
    updated twice). On first update of C, we consider old B permissions, so
    doing wrong thing. If it succeed, all is OK, on second C update we will
    finish with correct graph. But if the wrong thing failed, we break the
    whole process for no reason (it's possible that updated B permission
    will be less strict, but we will never check it).
    
    Also new approach gives a way to simultaneously and correctly update
    several nodes, we just need to run bdrv_topological_dfs() several times
    to add all nodes and their subtrees into one topologically sorted list
    (next patch will update bdrv_replace_node() in this manner).
    
    Test test_parallel_perm_update() is now passing, so move it out of
    debugging "if".
    
    We also need to support ignore_children in
    bdrv_parent_perms_conflict()
    
    For test 283 order of conflicting parents check is changed.
    
    Note also that in bdrv_check_perm() we don't check for parents conflict
    at root bs, as we may be in the middle of permission update in
    bdrv_reopen_multiple(). bdrv_reopen_multiple() will be updated soon.
    
    Signed-off-by: default avatarVladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
    Reviewed-by: default avatarKevin Wolf <kwolf@redhat.com>
    Message-Id: <20210428151804.439460-14-vsementsov@virtuozzo.com>
    Signed-off-by: default avatarKevin Wolf <kwolf@redhat.com>
    bd57f8f7
    block: use topological sort for permission update
    Vladimir Sementsov-Ogievskiy authored
    
    
    Rewrite bdrv_check_perm(), bdrv_abort_perm_update() and bdrv_set_perm()
    to update nodes in topological sort order instead of simple DFS. With
    topologically sorted nodes, we update a node only when all its parents
    already updated. With DFS it's not so.
    
    Consider the following example:
    
        A -+
        |  |
        |  v
        |  B
        |  |
        v  |
        C<-+
    
    A is parent for B and C, B is parent for C.
    
    Obviously, to update permissions, we should go in order A B C, so, when
    we update C, all parent permissions already updated. But with current
    approach (simple recursion) we can update in sequence A C B C (C is
    updated twice). On first update of C, we consider old B permissions, so
    doing wrong thing. If it succeed, all is OK, on second C update we will
    finish with correct graph. But if the wrong thing failed, we break the
    whole process for no reason (it's possible that updated B permission
    will be less strict, but we will never check it).
    
    Also new approach gives a way to simultaneously and correctly update
    several nodes, we just need to run bdrv_topological_dfs() several times
    to add all nodes and their subtrees into one topologically sorted list
    (next patch will update bdrv_replace_node() in this manner).
    
    Test test_parallel_perm_update() is now passing, so move it out of
    debugging "if".
    
    We also need to support ignore_children in
    bdrv_parent_perms_conflict()
    
    For test 283 order of conflicting parents check is changed.
    
    Note also that in bdrv_check_perm() we don't check for parents conflict
    at root bs, as we may be in the middle of permission update in
    bdrv_reopen_multiple(). bdrv_reopen_multiple() will be updated soon.
    
    Signed-off-by: default avatarVladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
    Reviewed-by: default avatarKevin Wolf <kwolf@redhat.com>
    Message-Id: <20210428151804.439460-14-vsementsov@virtuozzo.com>
    Signed-off-by: default avatarKevin Wolf <kwolf@redhat.com>
Loading