bitbake: Optimise runqueue recursive dependency calculations removing a bottleneck in world builds

Signed-off-by: Richard Purdie <rpurdie@linux.intel.com>

2 files changed, 151 insertions, 232 deletions

diff --git a/bitbake-dev/lib/bb/runqueue.py b/bitbake-dev/lib/bb/runqueue.py
index 4f0996dad6..1be2aa0db2 100644
--- a/bitbake-dev/lib/bb/runqueue.py
+++ b/bitbake-dev/lib/bb/runqueue.py
@@ -340,9 +340,10 @@ class RunQueue:
         to optimise the execution order.
         """
 
-        depends = []
         runq_build = []
         recursive_tdepends = {}
+        runq_recrdepends = []
+        tdepends_fnid = {}
 
         taskData = self.taskData
 
@@ -354,9 +355,9 @@ class RunQueue:
 
         # Step A - Work out a list of tasks to run
         #
-        # Taskdata gives us a list of possible providers for a every target 
-        # ordered by priority (build_targets, run_targets). It also gives
-        # information on each of those providers.
+        # Taskdata gives us a list of possible providers for every build and run
+        # target ordered by priority. It also gives information on each of those 
+        # providers.
         #
         # To create the actual list of tasks to execute we fix the list of 
         # providers and then resolve the dependencies into task IDs. This 
@@ -364,10 +365,14 @@ class RunQueue:
         # rdeptast, recrdeptask, idepends).
 
         for task in range(len(taskData.tasks_name)):
+            depends = []
+            recrdepends = []
             fnid = taskData.tasks_fnid[task]
             fn = taskData.fn_index[fnid]
             task_deps = self.dataCache.task_deps[fn]
 
+            bb.msg.debug(2, bb.msg.domain.RunQueue, "Processing %s:%s" %(fn, taskData.tasks_name[task]))
+
             if fnid not in taskData.failed_fnids:
 
                 # Resolve task internal dependencies 
@@ -407,6 +412,8 @@ class RunQueue:
                 #
                 # e.g. do_sometask[depends] = "targetname:do_someothertask"
                 # (makes sure sometask runs after targetname's someothertask)
+                if fnid not in tdepends_fnid:
+                    tdepends_fnid[fnid] = set()
                 idepends = taskData.tasks_idepends[task]
                 for (depid, idependtask) in idepends:
                     if depid in taskData.build_targets:
@@ -414,122 +421,37 @@ class RunQueue:
                         depdata = taskData.build_targets[depid][0]
                         if depdata is not None:
                             dep = taskData.fn_index[depdata]
-                            depends.append(taskData.gettask_id(dep, idependtask))
-
-                # Create a list of recursive dependent tasks (from tdepends) and cache
-                def get_recursive_tdepends(task):
-                    if not task:
-                        return []
-                    if task in recursive_tdepends:
-                        return recursive_tdepends[task]
-
-                    fnid = taskData.tasks_fnid[task]
-                    taskids = taskData.gettask_ids(fnid)
-
-                    rectdepends = taskids
-                    nextdeps = taskids
-                    while len(nextdeps) != 0:
-                        newdeps = []
-                        for nextdep in nextdeps:
-                            for tdepend in taskData.tasks_tdepends[nextdep]:
-                                if tdepend not in rectdepends:
-                                    rectdepends.append(tdepend)
-                                    newdeps.append(tdepend)
-                        nextdeps = newdeps
-                    recursive_tdepends[task] = rectdepends
-                    return rectdepends
-
-                # Using the list of tdepends for this task create a list of 
-                # the recursive idepends we have
-                def get_recursive_idepends(task):
-                    if not task:
-                        return []
-                    rectdepends = get_recursive_tdepends(task)
-
-                    recidepends = []
-                    for tdepend in rectdepends:
-                        for idepend in taskData.tasks_idepends[tdepend]:
-                            recidepends.append(idepend)
-                    return recidepends
-
-                def add_recursive_build(depid, depfnid):
-                    """
-                    Add build depends of depid to depends
-                    (if we've not see it before)
-                    (calls itself recursively)
-                    """
-                    if str(depid) in dep_seen:
-                        return
-                    dep_seen.append(depid)
-                    if depid in taskData.build_targets:
-                        depdata = taskData.build_targets[depid][0]
-                        if depdata is not None:
-                            dep = taskData.fn_index[depdata]
-                            # Need to avoid creating new tasks here
-                            taskid = taskData.gettask_id(dep, taskname, False)
-                            if taskid is not None:
-                                depends.append(taskid)
-                                fnid = taskData.tasks_fnid[taskid]
-                                #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid])
-                            else:
-                                fnid = taskData.getfn_id(dep)
-                            for nextdepid in taskData.depids[fnid]:
-                                if nextdepid not in dep_seen:
-                                    add_recursive_build(nextdepid, fnid)
-                            for nextdepid in taskData.rdepids[fnid]:
-                                if nextdepid not in rdep_seen:
-                                    add_recursive_run(nextdepid, fnid)
-                            for (idependid, idependtask) in get_recursive_idepends(taskid):
-                                if idependid not in dep_seen:
-                                    add_recursive_build(idependid, fnid)
-
-                def add_recursive_run(rdepid, depfnid):
-                    """
-                    Add runtime depends of rdepid to depends
-                    (if we've not see it before)
-                    (calls itself recursively)
-                    """
-                    if str(rdepid) in rdep_seen:
-                        return
-                    rdep_seen.append(rdepid)
-                    if rdepid in taskData.run_targets:
-                        depdata = taskData.run_targets[rdepid][0]
-                        if depdata is not None:
-                            dep = taskData.fn_index[depdata]
-                            # Need to avoid creating new tasks here
-                            taskid = taskData.gettask_id(dep, taskname, False)
-                            if taskid is not None:
-                                depends.append(taskid)
-                                fnid = taskData.tasks_fnid[taskid]
-                                #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid])
-                            else:
-                                fnid = taskData.getfn_id(dep)
-                            for nextdepid in taskData.depids[fnid]:
-                                if nextdepid not in dep_seen:
-                                    add_recursive_build(nextdepid, fnid)
-                            for nextdepid in taskData.rdepids[fnid]:
-                                if nextdepid not in rdep_seen:
-                                    add_recursive_run(nextdepid, fnid)
-                            for (idependid, idependtask) in get_recursive_idepends(taskid):
-                                if idependid not in dep_seen:
-                                    add_recursive_build(idependid, fnid)
-
-                # Resolve recursive 'recrdeptask' dependencies 
+                            taskid = taskData.gettask_id(dep, idependtask)
+                            depends.append(taskid)
+                            if depdata != fnid:
+                                tdepends_fnid[fnid].add(taskid)
+
+
+                # Resolve recursive 'recrdeptask' dependencies (A)
                 #
                 # e.g. do_sometask[recrdeptask] = "do_someothertask"
                 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
+                # We cover the recursive part of the dependencies below
                 if 'recrdeptask' in task_deps and taskData.tasks_name[task] in task_deps['recrdeptask']:
                     for taskname in task_deps['recrdeptask'][taskData.tasks_name[task]].split():
-                        dep_seen = []
-                        rdep_seen = []
-                        idep_seen = []
+                        recrdepends.append(taskname)
+                        for depid in taskData.rdepids[fnid]:
+                            if depid in taskData.run_targets:
+                                depdata = taskData.run_targets[depid][0]
+                                if depdata is not None:
+                                    dep = taskData.fn_index[depdata]
+                                    taskid = taskData.gettask_id(dep, taskname, False)
+                                    if taskid is not None:
+                                        depends.append(taskid)
                         for depid in taskData.depids[fnid]:
-                            add_recursive_build(depid, fnid)
-                        for rdepid in taskData.rdepids[fnid]:
-                            add_recursive_run(rdepid, fnid)
-                        deptaskid = taskData.gettask_id(fn, taskname, False)
-                        for (idependid, idependtask) in get_recursive_idepends(deptaskid):
-                            add_recursive_build(idependid, fnid)
+                            # Won't be in build_targets if ASSUME_PROVIDED
+                            if depid in taskData.build_targets:
+                                depdata = taskData.build_targets[depid][0]
+                                if depdata is not None:
+                                    dep = taskData.fn_index[depdata]
+                                    taskid = taskData.gettask_id(dep, taskname, False)
+                                    if taskid is not None:
+                                        depends.append(taskid)
 
                 # Rmove all self references
                 if task in depends:
@@ -540,13 +462,51 @@ class RunQueue:
                           newdep.append(dep)
                     depends = newdep
 
-
             self.runq_fnid.append(taskData.tasks_fnid[task])
             self.runq_task.append(taskData.tasks_name[task])
             self.runq_depends.append(set(depends))
             self.runq_revdeps.append(set())
 
             runq_build.append(0)
+            runq_recrdepends.append(recrdepends)
+
+        #
+        # Build a list of recursive cumulative dependencies for each fnid
+        # We do this by fnid, since if A depends on some task in B
+        # we're interested in later tasks B's fnid might have but B itself 
+        # doesn't depend on
+        #
+        # Algorithm is O(tasks) + O(tasks)*O(fnids)
+        #
+        reccumdepends = {}
+        for task in range(len(self.runq_fnid)):
+            fnid = self.runq_fnid[task]
+            if fnid not in reccumdepends:
+                reccumdepends[fnid] = set()
+            if task in self.runq_depends:
+                reccumdepends[fnid].update(self.runq_depends[task])
+            if fnid in tdepends_fnid:
+                reccumdepends[fnid].update(tdepends_fnid[fnid])
+        for task in range(len(self.runq_fnid)):
+            taskfnid = self.runq_fnid[task]
+            for fnid in reccumdepends:
+                if task in reccumdepends[fnid]:
+                    reccumdepends[fnid].add(task)
+                    if taskfnid in reccumdepends:
+                        reccumdepends[fnid].update(reccumdepends[taskfnid])
+
+
+        # Resolve recursive 'recrdeptask' dependencies (B)
+        #
+        # e.g. do_sometask[recrdeptask] = "do_someothertask"
+        # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
+        for task in range(len(self.runq_fnid)):
+            if len(runq_recrdepends[task]) > 0:
+                taskfnid = self.runq_fnid[task]
+                for dep in reccumdepends[taskfnid]:
+                    for taskname in runq_recrdepends[task]:
+                        if taskData.tasks_name[dep] == taskname:
+                            self.runq_depends[task].add(dep)
 
         # Step B - Mark all active tasks
         #
diff --git a/bitbake/lib/bb/runqueue.py b/bitbake/lib/bb/runqueue.py
index 9b3cbdf5db..ebc70ee61c 100644
--- a/bitbake/lib/bb/runqueue.py
+++ b/bitbake/lib/bb/runqueue.py
@@ -321,9 +321,10 @@ class RunQueue:
         to optimise the execution order.
         """
 
-        depends = []
         runq_build = []
         recursive_tdepends = {}
+        runq_recrdepends = []
+        tdepends_fnid = {}
 
         taskData = self.taskData
 
@@ -335,9 +336,9 @@ class RunQueue:
 
         # Step A - Work out a list of tasks to run
         #
-        # Taskdata gives us a list of possible providers for a every target 
-        # ordered by priority (build_targets, run_targets). It also gives
-        # information on each of those providers.
+        # Taskdata gives us a list of possible providers for every build and run
+        # target ordered by priority. It also gives information on each of those 
+        # providers.
         #
         # To create the actual list of tasks to execute we fix the list of 
         # providers and then resolve the dependencies into task IDs. This 
@@ -345,10 +346,14 @@ class RunQueue:
         # rdeptast, recrdeptask, idepends).
 
         for task in range(len(taskData.tasks_name)):
+            depends = []
+            recrdepends = []
             fnid = taskData.tasks_fnid[task]
             fn = taskData.fn_index[fnid]
             task_deps = self.dataCache.task_deps[fn]
 
+            bb.msg.debug(2, bb.msg.domain.RunQueue, "Processing %s:%s" %(fn, taskData.tasks_name[task]))
+
             if fnid not in taskData.failed_fnids:
 
                 # Resolve task internal dependencies 
@@ -388,6 +393,8 @@ class RunQueue:
                 #
                 # e.g. do_sometask[depends] = "targetname:do_someothertask"
                 # (makes sure sometask runs after targetname's someothertask)
+                if fnid not in tdepends_fnid:
+                    tdepends_fnid[fnid] = set()
                 idepends = taskData.tasks_idepends[task]
                 for (depid, idependtask) in idepends:
                     if depid in taskData.build_targets:
@@ -395,122 +402,37 @@ class RunQueue:
                         depdata = taskData.build_targets[depid][0]
                         if depdata is not None:
                             dep = taskData.fn_index[depdata]
-                            depends.append(taskData.gettask_id(dep, idependtask))
-
-                # Create a list of recursive dependent tasks (from tdepends) and cache
-                def get_recursive_tdepends(task):
-                    if not task:
-                        return []
-                    if task in recursive_tdepends:
-                        return recursive_tdepends[task]
-
-                    fnid = taskData.tasks_fnid[task]
-                    taskids = taskData.gettask_ids(fnid)
-
-                    rectdepends = taskids
-                    nextdeps = taskids
-                    while len(nextdeps) != 0:
-                        newdeps = []
-                        for nextdep in nextdeps:
-                            for tdepend in taskData.tasks_tdepends[nextdep]:
-                                if tdepend not in rectdepends:
-                                    rectdepends.append(tdepend)
-                                    newdeps.append(tdepend)
-                        nextdeps = newdeps
-                    recursive_tdepends[task] = rectdepends
-                    return rectdepends
-
-                # Using the list of tdepends for this task create a list of 
-                # the recursive idepends we have
-                def get_recursive_idepends(task):
-                    if not task:
-                        return []
-                    rectdepends = get_recursive_tdepends(task)
-
-                    recidepends = []
-                    for tdepend in rectdepends:
-                        for idepend in taskData.tasks_idepends[tdepend]:
-                            recidepends.append(idepend)
-                    return recidepends
-
-                def add_recursive_build(depid, depfnid):
-                    """
-                    Add build depends of depid to depends
-                    (if we've not see it before)
-                    (calls itself recursively)
-                    """
-                    if str(depid) in dep_seen:
-                        return
-                    dep_seen.append(depid)
-                    if depid in taskData.build_targets:
-                        depdata = taskData.build_targets[depid][0]
-                        if depdata is not None:
-                            dep = taskData.fn_index[depdata]
-                            # Need to avoid creating new tasks here
-                            taskid = taskData.gettask_id(dep, taskname, False)
-                            if taskid is not None:
-                                depends.append(taskid)
-                                fnid = taskData.tasks_fnid[taskid]
-                                #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid])
-                            else:
-                                fnid = taskData.getfn_id(dep)
-                            for nextdepid in taskData.depids[fnid]:
-                                if nextdepid not in dep_seen:
-                                    add_recursive_build(nextdepid, fnid)
-                            for nextdepid in taskData.rdepids[fnid]:
-                                if nextdepid not in rdep_seen:
-                                    add_recursive_run(nextdepid, fnid)
-                            for (idependid, idependtask) in get_recursive_idepends(taskid):
-                                if idependid not in dep_seen:
-                                    add_recursive_build(idependid, fnid)
-
-                def add_recursive_run(rdepid, depfnid):
-                    """
-                    Add runtime depends of rdepid to depends
-                    (if we've not see it before)
-                    (calls itself recursively)
-                    """
-                    if str(rdepid) in rdep_seen:
-                        return
-                    rdep_seen.append(rdepid)
-                    if rdepid in taskData.run_targets:
-                        depdata = taskData.run_targets[rdepid][0]
-                        if depdata is not None:
-                            dep = taskData.fn_index[depdata]
-                            # Need to avoid creating new tasks here
-                            taskid = taskData.gettask_id(dep, taskname, False)
-                            if taskid is not None:
-                                depends.append(taskid)
-                                fnid = taskData.tasks_fnid[taskid]
-                                #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid])
-                            else:
-                                fnid = taskData.getfn_id(dep)
-                            for nextdepid in taskData.depids[fnid]:
-                                if nextdepid not in dep_seen:
-                                    add_recursive_build(nextdepid, fnid)
-                            for nextdepid in taskData.rdepids[fnid]:
-                                if nextdepid not in rdep_seen:
-                                    add_recursive_run(nextdepid, fnid)
-                            for (idependid, idependtask) in get_recursive_idepends(taskid):
-                                if idependid not in dep_seen:
-                                    add_recursive_build(idependid, fnid)
-
-                # Resolve recursive 'recrdeptask' dependencies 
+                            taskid = taskData.gettask_id(dep, idependtask)
+                            depends.append(taskid)
+                            if depdata != fnid:
+                                tdepends_fnid[fnid].add(taskid)
+
+
+                # Resolve recursive 'recrdeptask' dependencies (A)
                 #
                 # e.g. do_sometask[recrdeptask] = "do_someothertask"
                 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
+                # We cover the recursive part of the dependencies below
                 if 'recrdeptask' in task_deps and taskData.tasks_name[task] in task_deps['recrdeptask']:
                     for taskname in task_deps['recrdeptask'][taskData.tasks_name[task]].split():
-                        dep_seen = []
-                        rdep_seen = []
-                        idep_seen = []
+                        recrdepends.append(taskname)
+                        for depid in taskData.rdepids[fnid]:
+                            if depid in taskData.run_targets:
+                                depdata = taskData.run_targets[depid][0]
+                                if depdata is not None:
+                                    dep = taskData.fn_index[depdata]
+                                    taskid = taskData.gettask_id(dep, taskname, False)
+                                    if taskid is not None:
+                                        depends.append(taskid)
                         for depid in taskData.depids[fnid]:
-                            add_recursive_build(depid, fnid)
-                        for rdepid in taskData.rdepids[fnid]:
-                            add_recursive_run(rdepid, fnid)
-                        deptaskid = taskData.gettask_id(fn, taskname, False)
-                        for (idependid, idependtask) in get_recursive_idepends(deptaskid):
-                            add_recursive_build(idependid, fnid)
+                            # Won't be in build_targets if ASSUME_PROVIDED
+                            if depid in taskData.build_targets:
+                                depdata = taskData.build_targets[depid][0]
+                                if depdata is not None:
+                                    dep = taskData.fn_index[depdata]
+                                    taskid = taskData.gettask_id(dep, taskname, False)
+                                    if taskid is not None:
+                                        depends.append(taskid)
 
                 # Rmove all self references
                 if task in depends:
@@ -521,13 +443,51 @@ class RunQueue:
                           newdep.append(dep)
                     depends = newdep
 
-
             self.runq_fnid.append(taskData.tasks_fnid[task])
             self.runq_task.append(taskData.tasks_name[task])
             self.runq_depends.append(set(depends))
             self.runq_revdeps.append(set())
 
             runq_build.append(0)
+            runq_recrdepends.append(recrdepends)
+
+        #
+        # Build a list of recursive cumulative dependencies for each fnid
+        # We do this by fnid, since if A depends on some task in B
+        # we're interested in later tasks B's fnid might have but B itself 
+        # doesn't depend on
+        #
+        # Algorithm is O(tasks) + O(tasks)*O(fnids)
+        #
+        reccumdepends = {}
+        for task in range(len(self.runq_fnid)):
+            fnid = self.runq_fnid[task]
+            if fnid not in reccumdepends:
+                reccumdepends[fnid] = set()
+            if task in self.runq_depends:
+                reccumdepends[fnid].update(self.runq_depends[task])
+            if fnid in tdepends_fnid:
+                reccumdepends[fnid].update(tdepends_fnid[fnid])
+        for task in range(len(self.runq_fnid)):
+            taskfnid = self.runq_fnid[task]
+            for fnid in reccumdepends:
+                if task in reccumdepends[fnid]:
+                    reccumdepends[fnid].add(task)
+                    if taskfnid in reccumdepends:
+                        reccumdepends[fnid].update(reccumdepends[taskfnid])
+
+
+        # Resolve recursive 'recrdeptask' dependencies (B)
+        #
+        # e.g. do_sometask[recrdeptask] = "do_someothertask"
+        # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
+        for task in range(len(self.runq_fnid)):
+            if len(runq_recrdepends[task]) > 0:
+                taskfnid = self.runq_fnid[task]
+                for dep in reccumdepends[taskfnid]:
+                    for taskname in runq_recrdepends[task]:
+                        if taskData.tasks_name[dep] == taskname:
+                            self.runq_depends[task].add(dep)
 
         # Step B - Mark all active tasks
         #
@@ -607,7 +567,7 @@ class RunQueue:
         if len(self.runq_fnid) == 0:
             if not taskData.abort:
                 bb.msg.fatal(bb.msg.domain.RunQueue, "All buildable tasks have been run but the build is incomplete (--continue mode). Errors for the tasks that failed will have been printed above.")
-            else:               
+            else:
                 bb.msg.fatal(bb.msg.domain.RunQueue, "No active tasks and not in --continue mode?! Please report this bug.")
 
         bb.msg.note(2, bb.msg.domain.RunQueue, "Pruned %s inactive tasks, %s left" % (delcount, len(self.runq_fnid)))
@@ -644,7 +604,6 @@ class RunQueue:
 
         bb.msg.note(2, bb.msg.domain.RunQueue, "Compute totals (have %s endpoint(s))" % len(endpoints))
 
-
         # Calculate task weights 
         # Check of higher length circular dependencies
         self.runq_weight = self.calculate_task_weights(endpoints)