[PATCH] bb.build.addtask: add simple check for circular dependency

[PATCH] bb.build.addtask: add simple check for circular dependency

[Ulf Samuelsson]

 From 864e49bedbdab480c5ada9588ce8f980f23919dd Mon Sep 17 00:00:00 2001
From: Ulf Samuelsson <ulf@emagii.com>
Date: Thu, 17 Jan 2019 19:07:17 +0100
Subject: [PATCH] bb.build.addtask: add simple check for circular dependency

Signed-off-by: Ulf Samuelsson <ulf@emagii.com>
---
  bitbake/lib/bb/build.py | 48 
++++++++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 48 insertions(+)

diff --git a/bitbake/lib/bb/build.py b/bitbake/lib/bb/build.py
index 3e2a94e..887ced1 100644
--- a/bitbake/lib/bb/build.py
+++ b/bitbake/lib/bb/build.py
@@ -43,6 +43,25 @@ logger = logging.getLogger('BitBake.Build')

  __mtime_cache = {}

+KNOWN_TASKS = {
+    'do_fetch' :           1 ,
+    'do_unpack' :          2 ,
+    'do_patch' :           3 ,
+    'do_configure' :       4 ,
+    'do_compile' :         5 ,
+    'do_install' :         6 ,
+    'do_package' :         7 ,
+    'do_package_data' :    8 ,
+    'do_rootfs' :          9 ,
+    'do_image_qa' :       10 ,
+    'do_image' :          11 ,
+    'do_image_tar' :      12 ,
+    'do_image_ubifs' :    12 ,
+    'do_image_jffs2' :    12 ,
+    'do_image_complete' : 13 ,
+    'do_build' :          14
+}
+
  def cached_mtime_noerror(f):
      if f not in __mtime_cache:
          try:
@@ -820,7 +839,34 @@ def add_tasks(tasklist, d):
      # don't assume holding a reference
      d.setVar('_task_deps', task_deps)

+def circular(after, before):
+    if after == None:
+        return False
+    if before == None:
+        return False
+    for a in after.split():
+        if a in KNOWN_TASKS:
+            for b in before.split():
+                if a == b:
+                    return True
+                if b in KNOWN_TASKS:
+                    if KNOWN_TASKS[b] < KNOWN_TASKS[a]:
+                        return True
+                    else:
+                        # tasks OK
+                        pass
+                else:
+                    # b is unknown
+                    pass
+        else:
+            # a is unknown
+            pass
+
  def addtask(task, before, after, d):
+    if circular(after, before):
+        logger.error("addtask: %s cannot be after %s and before %s" % 
(task, after, before))
+        raise
+
      if task[:3] != "do_":
          task = "do_" + task

@@ -909,3 +955,5 @@ def tasksbetween(task_start, task_end, d):
          chain.pop()
      follow_chain(task_start, task_end)
      return outtasks
+
+
-- 
2.7.4

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Richard Purdie]

On Thu, 2019-01-17 at 19:15 +0100, Ulf Samuelsson wrote:
>  From 864e49bedbdab480c5ada9588ce8f980f23919dd Mon Sep 17 00:00:00
> 2001
> From: Ulf Samuelsson <ulf@emagii.com>
> Date: Thu, 17 Jan 2019 19:07:17 +0100
> Subject: [PATCH] bb.build.addtask: add simple check for circular
> dependency

We really can't hardcode a list of tasks like this in bitbake :(

The list is also incorrect (at a quick look its packagedata and
populate_sysroot is missing).

We'll need to come up with a better algorithm than this. From
experience with circular task dependencies within bitbake's runqueue,
this is a hard problem though.

Cheers,

Richard

> Signed-off-by: Ulf Samuelsson <ulf@emagii.com>
> ---
>   bitbake/lib/bb/build.py | 48 
> ++++++++++++++++++++++++++++++++++++++++++++++++
>   1 file changed, 48 insertions(+)
> 
> diff --git a/bitbake/lib/bb/build.py b/bitbake/lib/bb/build.py
> index 3e2a94e..887ced1 100644
> --- a/bitbake/lib/bb/build.py
> +++ b/bitbake/lib/bb/build.py
> @@ -43,6 +43,25 @@ logger = logging.getLogger('BitBake.Build')
> 
>   __mtime_cache = {}
> 
> +KNOWN_TASKS = {
> +    'do_fetch' :           1 ,
> +    'do_unpack' :          2 ,
> +    'do_patch' :           3 ,
> +    'do_configure' :       4 ,
> +    'do_compile' :         5 ,
> +    'do_install' :         6 ,
> +    'do_package' :         7 ,
> +    'do_package_data' :    8 ,
> +    'do_rootfs' :          9 ,
> +    'do_image_qa' :       10 ,
> +    'do_image' :          11 ,
> +    'do_image_tar' :      12 ,
> +    'do_image_ubifs' :    12 ,
> +    'do_image_jffs2' :    12 ,
> +    'do_image_complete' : 13 ,
> +    'do_build' :          14
> +}
> +
>   def cached_mtime_noerror(f):
>       if f not in __mtime_cache:
>           try:
> @@ -820,7 +839,34 @@ def add_tasks(tasklist, d):
>       # don't assume holding a reference
>       d.setVar('_task_deps', task_deps)
> 
> +def circular(after, before):
> +    if after == None:
> +        return False
> +    if before == None:
> +        return False
> +    for a in after.split():
> +        if a in KNOWN_TASKS:
> +            for b in before.split():
> +                if a == b:
> +                    return True
> +                if b in KNOWN_TASKS:
> +                    if KNOWN_TASKS[b] < KNOWN_TASKS[a]:
> +                        return True
> +                    else:
> +                        # tasks OK
> +                        pass
> +                else:
> +                    # b is unknown
> +                    pass
> +        else:
> +            # a is unknown
> +            pass
> +
>   def addtask(task, before, after, d):
> +    if circular(after, before):
> +        logger.error("addtask: %s cannot be after %s and before %s"
> % 
> (task, after, before))
> +        raise
> +
>       if task[:3] != "do_":
>           task = "do_" + task
> 
> @@ -909,3 +955,5 @@ def tasksbetween(task_start, task_end, d):
>           chain.pop()
>       follow_chain(task_start, task_end)
>       return outtasks
> +
> +

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Ulf Samuelsson]

> 17 jan. 2019 kl. 22:05 skrev Richard Purdie <richard.purdie@linuxfoundation.org>:
> 
>> On Thu, 2019-01-17 at 19:15 +0100, Ulf Samuelsson wrote:
>> From 864e49bedbdab480c5ada9588ce8f980f23919dd Mon Sep 17 00:00:00
>> 2001
>> From: Ulf Samuelsson <ulf@emagii.com>
>> Date: Thu, 17 Jan 2019 19:07:17 +0100
>> Subject: [PATCH] bb.build.addtask: add simple check for circular
>> dependency
> 
> We really can't hardcode a list of tasks like this in bitbake :(
> 
> The list is also incorrect (at a quick look its packagedata and
> populate_sysroot is missing).

I would say it may be incomplete, but it is only wrong, if they are in the wrong order.

> 
> We'll need to come up with a better algorithm than this. From
> experience with circular task dependencies within bitbake's runqueue,
> this is a hard problem though.

It is an attempt to do a reasonable effort.
It will not handle a lot of user tasks which depends on each other for sure...
Is it better to have no detection, than a detection which works on the most common cases?
I will not have the time to look into a clean cover all cases algorithm, unfortunately.

Best Regards,
Ulf Samuelsson
> 
> Cheers,
> 
> Richard
> 
>> Signed-off-by: Ulf Samuelsson <ulf@emagii.com>
>> ---
>>  bitbake/lib/bb/build.py | 48 
>> ++++++++++++++++++++++++++++++++++++++++++++++++
>>  1 file changed, 48 insertions(+)
>> 
>> diff --git a/bitbake/lib/bb/build.py b/bitbake/lib/bb/build.py
>> index 3e2a94e..887ced1 100644
>> --- a/bitbake/lib/bb/build.py
>> +++ b/bitbake/lib/bb/build.py
>> @@ -43,6 +43,25 @@ logger = logging.getLogger('BitBake.Build')
>> 
>>  __mtime_cache = {}
>> 
>> +KNOWN_TASKS = {
>> +    'do_fetch' :           1 ,
>> +    'do_unpack' :          2 ,
>> +    'do_patch' :           3 ,
>> +    'do_configure' :       4 ,
>> +    'do_compile' :         5 ,
>> +    'do_install' :         6 ,
>> +    'do_package' :         7 ,
>> +    'do_package_data' :    8 ,
>> +    'do_rootfs' :          9 ,
>> +    'do_image_qa' :       10 ,
>> +    'do_image' :          11 ,
>> +    'do_image_tar' :      12 ,
>> +    'do_image_ubifs' :    12 ,
>> +    'do_image_jffs2' :    12 ,
>> +    'do_image_complete' : 13 ,
>> +    'do_build' :          14
>> +}
>> +
>>  def cached_mtime_noerror(f):
>>      if f not in __mtime_cache:
>>          try:
>> @@ -820,7 +839,34 @@ def add_tasks(tasklist, d):
>>      # don't assume holding a reference
>>      d.setVar('_task_deps', task_deps)
>> 
>> +def circular(after, before):
>> +    if after == None:
>> +        return False
>> +    if before == None:
>> +        return False
>> +    for a in after.split():
>> +        if a in KNOWN_TASKS:
>> +            for b in before.split():
>> +                if a == b:
>> +                    return True
>> +                if b in KNOWN_TASKS:
>> +                    if KNOWN_TASKS[b] < KNOWN_TASKS[a]:
>> +                        return True
>> +                    else:
>> +                        # tasks OK
>> +                        pass
>> +                else:
>> +                    # b is unknown
>> +                    pass
>> +        else:
>> +            # a is unknown
>> +            pass
>> +
>>  def addtask(task, before, after, d):
>> +    if circular(after, before):
>> +        logger.error("addtask: %s cannot be after %s and before %s"
>> % 
>> (task, after, before))
>> +        raise
>> +
>>      if task[:3] != "do_":
>>          task = "do_" + task
>> 
>> @@ -909,3 +955,5 @@ def tasksbetween(task_start, task_end, d):
>>          chain.pop()
>>      follow_chain(task_start, task_end)
>>      return outtasks
>> +
>> +
> 

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Burton, Ross]

On Thu, 17 Jan 2019 at 22:50, Ulf Samuelsson <yocto@emagii.com> wrote:
> > We really can't hardcode a list of tasks like this in bitbake :(
> >
> > The list is also incorrect (at a quick look its packagedata and
> > populate_sysroot is missing).
>
> I would say it may be incomplete, but it is only wrong, if they are in the wrong order.

Richard's point was that those task names are oe-core specific.
Bitbake doesn't know or care about the specific names.

Ross

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Ulf Samuelsson]

So if KNOWN_TASKS is defined in a configuration file in oe-core, it would be OK?
It needs to be extended to check for KNOWN_TASKS == None of course.

Best Regards,
Ulf Samuelsson
+46 722 427 437

> 18 jan. 2019 kl. 00:17 skrev Burton, Ross <ross.burton@intel.com>:
> 
> On Thu, 17 Jan 2019 at 22:50, Ulf Samuelsson <yocto@emagii.com> wrote:
>>> We really can't hardcode a list of tasks like this in bitbake :(
>>> 
>>> The list is also incorrect (at a quick look its packagedata and
>>> populate_sysroot is missing).
>> 
>> I would say it may be incomplete, but it is only wrong, if they are in the wrong order.
> 
> Richard's point was that those task names are oe-core specific.
> Bitbake doesn't know or care about the specific names.
> 
> Ross

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Richard Purdie]

On Fri, 2019-01-18 at 05:30 +0100, Ulf Samuelsson wrote:
> So if KNOWN_TASKS is defined in a configuration file in oe-core, it
> would be OK?
> It needs to be extended to check for KNOWN_TASKS == None of course.

No, this is too fragile. We then have to maintain two different lists
of tasks. If we did that we may as well just remove the generic tasks
mechanism and hardcode the tasks list in the metadata.

As I mentioned, we need to come up with something which detects the
task loops generically.

Cheers,

Richard

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Ulf Samuelsson]

> 18 jan. 2019 kl. 12:29 skrev Richard Purdie <richard.purdie@linuxfoundation.org>:
> 
>> On Fri, 2019-01-18 at 05:30 +0100, Ulf Samuelsson wrote:
>> So if KNOWN_TASKS is defined in a configuration file in oe-core, it
>> would be OK?
>> It needs to be extended to check for KNOWN_TASKS == None of course.
> 
> No, this is too fragile. We then have to maintain two different lists
> of tasks. If we did that we may as well just remove the generic tasks
> mechanism and hardcode the tasks list in the metadata.
> 
Why do we need two lists?

We need to know in what order the generic tasks are executed, that is all.

Then we need to see if an addtask is violating that order.
If the ”after” or ”before” is not a generic task, the check cannot catch that.

If the user decides to not use the generic tasks, and create new ones
with the same name, as the generic tasks, but rearranges the order, there will be a problem, but I do not see any other problems.

Please enlighten me!


> As I mentioned, we need to come up with something which detects the
> task loops generically.
> 
> Cheers,
> 
> Richard
> 
> 
> 

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Richard Purdie]

On Fri, 2019-01-18 at 15:16 +0100, Ulf Samuelsson wrote:
> > 18 jan. 2019 kl. 12:29 skrev Richard Purdie <
> > richard.purdie@linuxfoundation.org>:
> > 
> > > On Fri, 2019-01-18 at 05:30 +0100, Ulf Samuelsson wrote:
> > > So if KNOWN_TASKS is defined in a configuration file in oe-core,
> > > it
> > > would be OK?
> > > It needs to be extended to check for KNOWN_TASKS == None of
> > > course.
> > 
> > No, this is too fragile. We then have to maintain two different
> > lists
> > of tasks. If we did that we may as well just remove the generic
> > tasks
> > mechanism and hardcode the tasks list in the metadata.
> > 
> Why do we need two lists?

If we change one of these "generic" tasks, we then need to remember to
also update KNOWN_TASKS. The same information is being encoded in two
places.

Maintaining the same information in two different places means one of
those places inevitably ends up out of date.

> We need to know in what order the generic tasks are executed, that is
> all.
> 
> Then we need to see if an addtask is violating that order.
> If the ”after” or ”before” is not a generic task, the check cannot
> catch that.
> 
> If the user decides to not use the generic tasks, and create new ones
> with the same name, as the generic tasks, but rearranges the order,
> there will be a problem, but I do not see any other problems.
> 
> Please enlighten me!

This has the problem that the code will find some subset of the bugs
but not all of them. We'll then get users reporting that the tests
failed and asking for the checks to be improved.

So no, we are not doing this, sorry.

Cheers,

Richard

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Ulf Samuelsson]

> 18 jan. 2019 kl. 15:40 skrev Richard Purdie <richard.purdie@linuxfoundation.org>:
> 
> On Fri, 2019-01-18 at 15:16 +0100, Ulf Samuelsson wrote:
>>> 18 jan. 2019 kl. 12:29 skrev Richard Purdie <
>>> richard.purdie@linuxfoundation.org>:
>>> 
>>>> On Fri, 2019-01-18 at 05:30 +0100, Ulf Samuelsson wrote:
>>>> So if KNOWN_TASKS is defined in a configuration file in oe-core,
>>>> it
>>>> would be OK?
>>>> It needs to be extended to check for KNOWN_TASKS == None of
>>>> course.
>>> 
>>> No, this is too fragile. We then have to maintain two different
>>> lists
>>> of tasks. If we did that we may as well just remove the generic
>>> tasks
>>> mechanism and hardcode the tasks list in the metadata.
>>> 
>> Why do we need two lists?
> 
> If we change one of these "generic" tasks, we then need to remember to
> also update KNOWN_TASKS. The same information is being encoded in two
> places.
> 
> Maintaining the same information in two different places means one of
> those places inevitably ends up out of date.

We could insert a check if the KNOWN_TASKS is valid in a verification test.
When building core-image-minimal, the task order within core-image-minimal is analyzed, (dependencies on all other recipes is filtered away).
Then you find out if there are tasks added, missing, and/or in the wrong order.

Best Regards,
Ulf Samuelsson

> 
>> We need to know in what order the generic tasks are executed, that is
>> all.
>> 
>> Then we need to see if an addtask is violating that order.
>> If the ”after” or ”before” is not a generic task, the check cannot
>> catch that.
>> 
>> If the user decides to not use the generic tasks, and create new ones
>> with the same name, as the generic tasks, but rearranges the order,
>> there will be a problem, but I do not see any other problems.
>> 
>> Please enlighten me!
> 
> This has the problem that the code will find some subset of the bugs
> but not all of them. We'll then get users reporting that the tests
> failed and asking for the checks to be improved.
> 
> So no, we are not doing this, sorry.
> 
> Cheers,
> 
> Richard
> 
> 

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Burton, Ross]

On Fri, 18 Jan 2019 at 15:08, Ulf Samuelsson <yocto@emagii.com> wrote:
> We could insert a check if the KNOWN_TASKS is valid in a verification test.
> When building core-image-minimal, the task order within core-image-minimal is analyzed, (dependencies on all other recipes is filtered away).
> Then you find out if there are tasks added, missing, and/or in the wrong order.

What about people who add new tasks?  Do they now need to go and
extend KNOWN_TASKS correctly too?

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Alexander Kanavin]

> On 18 Jan 2019, at 16.34, Burton, Ross <ross.burton@intel.com> wrote:
> 
>> On Fri, 18 Jan 2019 at 15:08, Ulf Samuelsson <yocto@emagii.com> wrote:
>> We could insert a check if the KNOWN_TASKS is valid in a verification test.
>> When building core-image-minimal, the task order within core-image-minimal is analyzed, (dependencies on all other recipes is filtered away).
>> Then you find out if there are tasks added, missing, and/or in the wrong order.
> 
> What about people who add new tasks?  Do they now need to go and
> extend KNOWN_TASKS correctly too?

I might be missing something, but isn’t the right moment to detect loops when the task graph is fully formed? Then just run generic DFS on it, not a difficult or heavy algorithm.

Alex

Re: [PATCH] bb.build.addtask: add simple check for circular dependency

[Ulf Samuelsson]

> 18 jan. 2019 kl. 16:56 skrev Alexander Kanavin <alex.kanavin@gmail.com>:
> 
> 
> 
>>> On 18 Jan 2019, at 16.34, Burton, Ross <ross.burton@intel.com> wrote:
>>> 
>>> On Fri, 18 Jan 2019 at 15:08, Ulf Samuelsson <yocto@emagii.com> wrote:
>>> We could insert a check if the KNOWN_TASKS is valid in a verification test.
>>> When building core-image-minimal, the task order within core-image-minimal is analyzed, (dependencies on all other recipes is filtered away).
>>> Then you find out if there are tasks added, missing, and/or in the wrong order.
>> 
>> What about people who add new tasks?  Do they now need to go and
>> extend KNOWN_TASKS correctly too?
> 
> I might be missing something, but isn’t the right moment to detect loops when the task graph is fully formed? Then just run generic DFS on it, not a difficult or heavy algorithm.
> 
> Alex

The problem in our system was that the build crashed before that.

Best Regards,
Ulf Samuelsson