From 8f5363d16de17459b654ca780e5bbd6e04b6bb73 Mon Sep 17 00:00:00 2001 From: Richard Purdie Date: Tue, 21 Jul 2009 19:44:23 +0100 Subject: bitbake: Optimise runqueue recursive dependency calculations removing a bottleneck in world builds Signed-off-by: Richard Purdie --- bitbake-dev/lib/bb/runqueue.py | 190 ++++++++++++++++------------------------- 1 file changed, 75 insertions(+), 115 deletions(-) (limited to 'bitbake-dev/lib/bb') diff --git a/bitbake-dev/lib/bb/runqueue.py b/bitbake-dev/lib/bb/runqueue.py index 4f0996dad..1be2aa0db 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 # -- cgit v1.2.3