As it already said in the comment, we don't want to create loops in
parent->child relations. So, when we try to append @to to @c, we should
check that @c is not in @to children subtree, and we should check it
recursively, not only the first level. The patch provides BFS-based
search, to check the relations.

This is needed for further fleecing-hook filter usage: we need to
append it to source, when the hook is already a parent of target, and
source may be in a backing chain of target (fleecing-scheme). So, on
appending, the hook should not became a child (direct or through
children subtree) of the target.

Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
---
 block.c | 33 ++++++++++++++++++++++++++++-----
 1 file changed, 28 insertions(+), 5 deletions(-)

diff --git a/block.c b/block.c
index 4f5ff2cc12..8f04f293da 100644
--- a/block.c
+++ b/block.c
@@ -3536,7 +3536,7 @@ void bdrv_close_all(void)
 
 static bool should_update_child(BdrvChild *c, BlockDriverState *to)
 {
-    BdrvChild *to_c;
+    GList *queue = NULL, *pos;
 
     if (c->role->stay_at_node) {
         return false;
@@ -3572,13 +3572,36 @@ static bool should_update_child(BdrvChild *c, BlockDriverState *to)
      * if A is a child of B, that means we cannot replace A by B there
      * because that would create a loop.  Silently detaching A from B
      * is also not really an option.  So overall just leaving A in
-     * place there is the most sensible choice. */
-    QLIST_FOREACH(to_c, &to->children, next) {
-        if (to_c == c) {
-            return false;
+     * place there is the most sensible choice.
+     *
+     * We would also create a loop in any cases where @c is only
+     * indirectly referenced by @to. Prevent this by returning false
+     * if @c is found (by breadth-first search) anywhere in the whole
+     * subtree of @to.
+     */
+
+    pos = queue = g_list_append(queue, to);
+    while (pos) {
+        BlockDriverState *v = pos->data;
+        BdrvChild *c2;
+
+        QLIST_FOREACH(c2, &v->children, next) {
+            if (c2 == c) {
+                g_list_free(queue);
+                return false;
+            }
+
+            if (g_list_find(queue, c2->bs)) {
+                continue;
+            }
+
+            queue = g_list_append(queue, c2->bs);
         }
+
+        pos = pos->next;
     }
 
+    g_list_free(queue);
     return true;
 }
 
-- 
2.18.0

On 29.12.18 13:20, Vladimir Sementsov-Ogievskiy wrote:
> As it already said in the comment, we don't want to create loops in
> parent->child relations. So, when we try to append @to to @c, we should
> check that @c is not in @to children subtree, and we should check it
> recursively, not only the first level. The patch provides BFS-based
> search, to check the relations.
> 
> This is needed for further fleecing-hook filter usage: we need to
> append it to source, when the hook is already a parent of target, and
> source may be in a backing chain of target (fleecing-scheme). So, on
> appending, the hook should not became a child (direct or through
> children subtree) of the target.
> 
> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
> ---
>  block.c | 33 ++++++++++++++++++++++++++++-----
>  1 file changed, 28 insertions(+), 5 deletions(-)

Just two technical details:

> diff --git a/block.c b/block.c
> index 4f5ff2cc12..8f04f293da 100644
> --- a/block.c
> +++ b/block.c
> @@ -3536,7 +3536,7 @@ void bdrv_close_all(void)
>  
>  static bool should_update_child(BdrvChild *c, BlockDriverState *to)
>  {
> -    BdrvChild *to_c;
> +    GList *queue = NULL, *pos;

GSList should be sufficient, I think.

>  
>      if (c->role->stay_at_node) {
>          return false;
> @@ -3572,13 +3572,36 @@ static bool should_update_child(BdrvChild *c, BlockDriverState *to)
>       * if A is a child of B, that means we cannot replace A by B there
>       * because that would create a loop.  Silently detaching A from B
>       * is also not really an option.  So overall just leaving A in
> -     * place there is the most sensible choice. */
> -    QLIST_FOREACH(to_c, &to->children, next) {
> -        if (to_c == c) {
> -            return false;
> +     * place there is the most sensible choice.
> +     *
> +     * We would also create a loop in any cases where @c is only
> +     * indirectly referenced by @to. Prevent this by returning false
> +     * if @c is found (by breadth-first search) anywhere in the whole
> +     * subtree of @to.
> +     */
> +
> +    pos = queue = g_list_append(queue, to);
> +    while (pos) {
> +        BlockDriverState *v = pos->data;
> +        BdrvChild *c2;
> +
> +        QLIST_FOREACH(c2, &v->children, next) {
> +            if (c2 == c) {
> +                g_list_free(queue);
> +                return false;
> +            }
> +
> +            if (g_list_find(queue, c2->bs)) {
> +                continue;
> +            }
> +
> +            queue = g_list_append(queue, c2->bs);

Appending to pos should be a bit quicker, I presume.  (And you can
probably ignore the result, or just assert that the first argument was
returned.)

Max

>          }
> +
> +        pos = pos->next;
>      }
>  
> +    g_list_free(queue);
>      return true;
>  }
>  
> 

14.01.2019 17:32, Max Reitz wrote:
> On 29.12.18 13:20, Vladimir Sementsov-Ogievskiy wrote:
>> As it already said in the comment, we don't want to create loops in
>> parent->child relations. So, when we try to append @to to @c, we should
>> check that @c is not in @to children subtree, and we should check it
>> recursively, not only the first level. The patch provides BFS-based
>> search, to check the relations.
>>
>> This is needed for further fleecing-hook filter usage: we need to
>> append it to source, when the hook is already a parent of target, and
>> source may be in a backing chain of target (fleecing-scheme). So, on
>> appending, the hook should not became a child (direct or through
>> children subtree) of the target.
>>
>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>> ---
>>   block.c | 33 ++++++++++++++++++++++++++++-----
>>   1 file changed, 28 insertions(+), 5 deletions(-)
> 
> Just two technical details:
> 
>> diff --git a/block.c b/block.c
>> index 4f5ff2cc12..8f04f293da 100644
>> --- a/block.c
>> +++ b/block.c
>> @@ -3536,7 +3536,7 @@ void bdrv_close_all(void)
>>   
>>   static bool should_update_child(BdrvChild *c, BlockDriverState *to)
>>   {
>> -    BdrvChild *to_c;
>> +    GList *queue = NULL, *pos;
> 
> GSList should be sufficient, I think.
> 
>>   
>>       if (c->role->stay_at_node) {
>>           return false;
>> @@ -3572,13 +3572,36 @@ static bool should_update_child(BdrvChild *c, BlockDriverState *to)
>>        * if A is a child of B, that means we cannot replace A by B there
>>        * because that would create a loop.  Silently detaching A from B
>>        * is also not really an option.  So overall just leaving A in
>> -     * place there is the most sensible choice. */
>> -    QLIST_FOREACH(to_c, &to->children, next) {
>> -        if (to_c == c) {
>> -            return false;
>> +     * place there is the most sensible choice.
>> +     *
>> +     * We would also create a loop in any cases where @c is only
>> +     * indirectly referenced by @to. Prevent this by returning false
>> +     * if @c is found (by breadth-first search) anywhere in the whole
>> +     * subtree of @to.
>> +     */
>> +
>> +    pos = queue = g_list_append(queue, to);
>> +    while (pos) {
>> +        BlockDriverState *v = pos->data;
>> +        BdrvChild *c2;
>> +
>> +        QLIST_FOREACH(c2, &v->children, next) {
>> +            if (c2 == c) {
>> +                g_list_free(queue);
>> +                return false;
>> +            }
>> +
>> +            if (g_list_find(queue, c2->bs)) {
>> +                continue;
>> +            }
>> +
>> +            queue = g_list_append(queue, c2->bs);
> 
> Appending to pos should be a bit quicker, I presume.  (And you can
> probably ignore the result, or just assert that the first argument was
> returned.)

So, even better is to use GQueue, strange that I didn't.

> 
> Max
> 
>>           }
>> +
>> +        pos = pos->next;
>>       }
>>   
>> +    g_list_free(queue);
>>       return true;
>>   }
>>   
>>
> 
> 


-- 
Best regards,
Vladimir

On 14.01.19 17:13, Vladimir Sementsov-Ogievskiy wrote:
> 14.01.2019 17:32, Max Reitz wrote:
>> On 29.12.18 13:20, Vladimir Sementsov-Ogievskiy wrote:
>>> As it already said in the comment, we don't want to create loops in
>>> parent->child relations. So, when we try to append @to to @c, we should
>>> check that @c is not in @to children subtree, and we should check it
>>> recursively, not only the first level. The patch provides BFS-based
>>> search, to check the relations.
>>>
>>> This is needed for further fleecing-hook filter usage: we need to
>>> append it to source, when the hook is already a parent of target, and
>>> source may be in a backing chain of target (fleecing-scheme). So, on
>>> appending, the hook should not became a child (direct or through
>>> children subtree) of the target.
>>>
>>> Signed-off-by: Vladimir Sementsov-Ogievskiy <vsementsov@virtuozzo.com>
>>> ---
>>>   block.c | 33 ++++++++++++++++++++++++++++-----
>>>   1 file changed, 28 insertions(+), 5 deletions(-)
>>
>> Just two technical details:
>>
>>> diff --git a/block.c b/block.c
>>> index 4f5ff2cc12..8f04f293da 100644
>>> --- a/block.c
>>> +++ b/block.c
>>> @@ -3536,7 +3536,7 @@ void bdrv_close_all(void)
>>>   
>>>   static bool should_update_child(BdrvChild *c, BlockDriverState *to)
>>>   {
>>> -    BdrvChild *to_c;
>>> +    GList *queue = NULL, *pos;
>>
>> GSList should be sufficient, I think.
>>
>>>   
>>>       if (c->role->stay_at_node) {
>>>           return false;
>>> @@ -3572,13 +3572,36 @@ static bool should_update_child(BdrvChild *c, BlockDriverState *to)
>>>        * if A is a child of B, that means we cannot replace A by B there
>>>        * because that would create a loop.  Silently detaching A from B
>>>        * is also not really an option.  So overall just leaving A in
>>> -     * place there is the most sensible choice. */
>>> -    QLIST_FOREACH(to_c, &to->children, next) {
>>> -        if (to_c == c) {
>>> -            return false;
>>> +     * place there is the most sensible choice.
>>> +     *
>>> +     * We would also create a loop in any cases where @c is only
>>> +     * indirectly referenced by @to. Prevent this by returning false
>>> +     * if @c is found (by breadth-first search) anywhere in the whole
>>> +     * subtree of @to.
>>> +     */
>>> +
>>> +    pos = queue = g_list_append(queue, to);
>>> +    while (pos) {
>>> +        BlockDriverState *v = pos->data;
>>> +        BdrvChild *c2;
>>> +
>>> +        QLIST_FOREACH(c2, &v->children, next) {
>>> +            if (c2 == c) {
>>> +                g_list_free(queue);
>>> +                return false;
>>> +            }
>>> +
>>> +            if (g_list_find(queue, c2->bs)) {
>>> +                continue;
>>> +            }
>>> +
>>> +            queue = g_list_append(queue, c2->bs);
>>
>> Appending to pos should be a bit quicker, I presume.  (And you can
>> probably ignore the result, or just assert that the first argument was
>> returned.)
> 
> So, even better is to use GQueue, strange that I didn't.

Because it has a tail pointer built in?  Hu, yeah, that's even better. :-)

Max