summaryrefslogtreecommitdiffstats
path: root/bitbake/lib
diff options
context:
space:
mode:
authorRichard Purdie <rpurdie@linux.intel.com>2009-07-21 19:44:23 +0100
committerRichard Purdie <rpurdie@linux.intel.com>2009-07-21 19:44:23 +0100
commit8f5363d16de17459b654ca780e5bbd6e04b6bb73 (patch)
tree7c8d6bf31d85c65210a9e1b9fe7ab227963970f3 /bitbake/lib
parent133e9e6064195942a95ff58c18a6578de7bcadc7 (diff)
downloadpoky-8f5363d16de17459b654ca780e5bbd6e04b6bb73.tar.gz
bitbake: Optimise runqueue recursive dependency calculations removing a bottleneck in world builds
Signed-off-by: Richard Purdie <rpurdie@linux.intel.com>
Diffstat (limited to 'bitbake/lib')
-rw-r--r--bitbake/lib/bb/runqueue.py193
1 files changed, 76 insertions, 117 deletions
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:
321 to optimise the execution order. 321 to optimise the execution order.
322 """ 322 """
323 323
324 depends = []
325 runq_build = [] 324 runq_build = []
326 recursive_tdepends = {} 325 recursive_tdepends = {}
326 runq_recrdepends = []
327 tdepends_fnid = {}
327 328
328 taskData = self.taskData 329 taskData = self.taskData
329 330
@@ -335,9 +336,9 @@ class RunQueue:
335 336
336 # Step A - Work out a list of tasks to run 337 # Step A - Work out a list of tasks to run
337 # 338 #
338 # Taskdata gives us a list of possible providers for a every target 339 # Taskdata gives us a list of possible providers for every build and run
339 # ordered by priority (build_targets, run_targets). It also gives 340 # target ordered by priority. It also gives information on each of those
340 # information on each of those providers. 341 # providers.
341 # 342 #
342 # To create the actual list of tasks to execute we fix the list of 343 # To create the actual list of tasks to execute we fix the list of
343 # providers and then resolve the dependencies into task IDs. This 344 # providers and then resolve the dependencies into task IDs. This
@@ -345,10 +346,14 @@ class RunQueue:
345 # rdeptast, recrdeptask, idepends). 346 # rdeptast, recrdeptask, idepends).
346 347
347 for task in range(len(taskData.tasks_name)): 348 for task in range(len(taskData.tasks_name)):
349 depends = []
350 recrdepends = []
348 fnid = taskData.tasks_fnid[task] 351 fnid = taskData.tasks_fnid[task]
349 fn = taskData.fn_index[fnid] 352 fn = taskData.fn_index[fnid]
350 task_deps = self.dataCache.task_deps[fn] 353 task_deps = self.dataCache.task_deps[fn]
351 354
355 bb.msg.debug(2, bb.msg.domain.RunQueue, "Processing %s:%s" %(fn, taskData.tasks_name[task]))
356
352 if fnid not in taskData.failed_fnids: 357 if fnid not in taskData.failed_fnids:
353 358
354 # Resolve task internal dependencies 359 # Resolve task internal dependencies
@@ -388,6 +393,8 @@ class RunQueue:
388 # 393 #
389 # e.g. do_sometask[depends] = "targetname:do_someothertask" 394 # e.g. do_sometask[depends] = "targetname:do_someothertask"
390 # (makes sure sometask runs after targetname's someothertask) 395 # (makes sure sometask runs after targetname's someothertask)
396 if fnid not in tdepends_fnid:
397 tdepends_fnid[fnid] = set()
391 idepends = taskData.tasks_idepends[task] 398 idepends = taskData.tasks_idepends[task]
392 for (depid, idependtask) in idepends: 399 for (depid, idependtask) in idepends:
393 if depid in taskData.build_targets: 400 if depid in taskData.build_targets:
@@ -395,122 +402,37 @@ class RunQueue:
395 depdata = taskData.build_targets[depid][0] 402 depdata = taskData.build_targets[depid][0]
396 if depdata is not None: 403 if depdata is not None:
397 dep = taskData.fn_index[depdata] 404 dep = taskData.fn_index[depdata]
398 depends.append(taskData.gettask_id(dep, idependtask)) 405 taskid = taskData.gettask_id(dep, idependtask)
399 406 depends.append(taskid)
400 # Create a list of recursive dependent tasks (from tdepends) and cache 407 if depdata != fnid:
401 def get_recursive_tdepends(task): 408 tdepends_fnid[fnid].add(taskid)
402 if not task: 409
403 return [] 410
404 if task in recursive_tdepends: 411 # Resolve recursive 'recrdeptask' dependencies (A)
405 return recursive_tdepends[task]
406
407 fnid = taskData.tasks_fnid[task]
408 taskids = taskData.gettask_ids(fnid)
409
410 rectdepends = taskids
411 nextdeps = taskids
412 while len(nextdeps) != 0:
413 newdeps = []
414 for nextdep in nextdeps:
415 for tdepend in taskData.tasks_tdepends[nextdep]:
416 if tdepend not in rectdepends:
417 rectdepends.append(tdepend)
418 newdeps.append(tdepend)
419 nextdeps = newdeps
420 recursive_tdepends[task] = rectdepends
421 return rectdepends
422
423 # Using the list of tdepends for this task create a list of
424 # the recursive idepends we have
425 def get_recursive_idepends(task):
426 if not task:
427 return []
428 rectdepends = get_recursive_tdepends(task)
429
430 recidepends = []
431 for tdepend in rectdepends:
432 for idepend in taskData.tasks_idepends[tdepend]:
433 recidepends.append(idepend)
434 return recidepends
435
436 def add_recursive_build(depid, depfnid):
437 """
438 Add build depends of depid to depends
439 (if we've not see it before)
440 (calls itself recursively)
441 """
442 if str(depid) in dep_seen:
443 return
444 dep_seen.append(depid)
445 if depid in taskData.build_targets:
446 depdata = taskData.build_targets[depid][0]
447 if depdata is not None:
448 dep = taskData.fn_index[depdata]
449 # Need to avoid creating new tasks here
450 taskid = taskData.gettask_id(dep, taskname, False)
451 if taskid is not None:
452 depends.append(taskid)
453 fnid = taskData.tasks_fnid[taskid]
454 #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid])
455 else:
456 fnid = taskData.getfn_id(dep)
457 for nextdepid in taskData.depids[fnid]:
458 if nextdepid not in dep_seen:
459 add_recursive_build(nextdepid, fnid)
460 for nextdepid in taskData.rdepids[fnid]:
461 if nextdepid not in rdep_seen:
462 add_recursive_run(nextdepid, fnid)
463 for (idependid, idependtask) in get_recursive_idepends(taskid):
464 if idependid not in dep_seen:
465 add_recursive_build(idependid, fnid)
466
467 def add_recursive_run(rdepid, depfnid):
468 """
469 Add runtime depends of rdepid to depends
470 (if we've not see it before)
471 (calls itself recursively)
472 """
473 if str(rdepid) in rdep_seen:
474 return
475 rdep_seen.append(rdepid)
476 if rdepid in taskData.run_targets:
477 depdata = taskData.run_targets[rdepid][0]
478 if depdata is not None:
479 dep = taskData.fn_index[depdata]
480 # Need to avoid creating new tasks here
481 taskid = taskData.gettask_id(dep, taskname, False)
482 if taskid is not None:
483 depends.append(taskid)
484 fnid = taskData.tasks_fnid[taskid]
485 #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid])
486 else:
487 fnid = taskData.getfn_id(dep)
488 for nextdepid in taskData.depids[fnid]:
489 if nextdepid not in dep_seen:
490 add_recursive_build(nextdepid, fnid)
491 for nextdepid in taskData.rdepids[fnid]:
492 if nextdepid not in rdep_seen:
493 add_recursive_run(nextdepid, fnid)
494 for (idependid, idependtask) in get_recursive_idepends(taskid):
495 if idependid not in dep_seen:
496 add_recursive_build(idependid, fnid)
497
498 # Resolve recursive 'recrdeptask' dependencies
499 # 412 #
500 # e.g. do_sometask[recrdeptask] = "do_someothertask" 413 # e.g. do_sometask[recrdeptask] = "do_someothertask"
501 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively) 414 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
415 # We cover the recursive part of the dependencies below
502 if 'recrdeptask' in task_deps and taskData.tasks_name[task] in task_deps['recrdeptask']: 416 if 'recrdeptask' in task_deps and taskData.tasks_name[task] in task_deps['recrdeptask']:
503 for taskname in task_deps['recrdeptask'][taskData.tasks_name[task]].split(): 417 for taskname in task_deps['recrdeptask'][taskData.tasks_name[task]].split():
504 dep_seen = [] 418 recrdepends.append(taskname)
505 rdep_seen = [] 419 for depid in taskData.rdepids[fnid]:
506 idep_seen = [] 420 if depid in taskData.run_targets:
421 depdata = taskData.run_targets[depid][0]
422 if depdata is not None:
423 dep = taskData.fn_index[depdata]
424 taskid = taskData.gettask_id(dep, taskname, False)
425 if taskid is not None:
426 depends.append(taskid)
507 for depid in taskData.depids[fnid]: 427 for depid in taskData.depids[fnid]:
508 add_recursive_build(depid, fnid) 428 # Won't be in build_targets if ASSUME_PROVIDED
509 for rdepid in taskData.rdepids[fnid]: 429 if depid in taskData.build_targets:
510 add_recursive_run(rdepid, fnid) 430 depdata = taskData.build_targets[depid][0]
511 deptaskid = taskData.gettask_id(fn, taskname, False) 431 if depdata is not None:
512 for (idependid, idependtask) in get_recursive_idepends(deptaskid): 432 dep = taskData.fn_index[depdata]
513 add_recursive_build(idependid, fnid) 433 taskid = taskData.gettask_id(dep, taskname, False)
434 if taskid is not None:
435 depends.append(taskid)
514 436
515 # Rmove all self references 437 # Rmove all self references
516 if task in depends: 438 if task in depends:
@@ -521,13 +443,51 @@ class RunQueue:
521 newdep.append(dep) 443 newdep.append(dep)
522 depends = newdep 444 depends = newdep
523 445
524
525 self.runq_fnid.append(taskData.tasks_fnid[task]) 446 self.runq_fnid.append(taskData.tasks_fnid[task])
526 self.runq_task.append(taskData.tasks_name[task]) 447 self.runq_task.append(taskData.tasks_name[task])
527 self.runq_depends.append(set(depends)) 448 self.runq_depends.append(set(depends))
528 self.runq_revdeps.append(set()) 449 self.runq_revdeps.append(set())
529 450
530 runq_build.append(0) 451 runq_build.append(0)
452 runq_recrdepends.append(recrdepends)
453
454 #
455 # Build a list of recursive cumulative dependencies for each fnid
456 # We do this by fnid, since if A depends on some task in B
457 # we're interested in later tasks B's fnid might have but B itself
458 # doesn't depend on
459 #
460 # Algorithm is O(tasks) + O(tasks)*O(fnids)
461 #
462 reccumdepends = {}
463 for task in range(len(self.runq_fnid)):
464 fnid = self.runq_fnid[task]
465 if fnid not in reccumdepends:
466 reccumdepends[fnid] = set()
467 if task in self.runq_depends:
468 reccumdepends[fnid].update(self.runq_depends[task])
469 if fnid in tdepends_fnid:
470 reccumdepends[fnid].update(tdepends_fnid[fnid])
471 for task in range(len(self.runq_fnid)):
472 taskfnid = self.runq_fnid[task]
473 for fnid in reccumdepends:
474 if task in reccumdepends[fnid]:
475 reccumdepends[fnid].add(task)
476 if taskfnid in reccumdepends:
477 reccumdepends[fnid].update(reccumdepends[taskfnid])
478
479
480 # Resolve recursive 'recrdeptask' dependencies (B)
481 #
482 # e.g. do_sometask[recrdeptask] = "do_someothertask"
483 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
484 for task in range(len(self.runq_fnid)):
485 if len(runq_recrdepends[task]) > 0:
486 taskfnid = self.runq_fnid[task]
487 for dep in reccumdepends[taskfnid]:
488 for taskname in runq_recrdepends[task]:
489 if taskData.tasks_name[dep] == taskname:
490 self.runq_depends[task].add(dep)
531 491
532 # Step B - Mark all active tasks 492 # Step B - Mark all active tasks
533 # 493 #
@@ -607,7 +567,7 @@ class RunQueue:
607 if len(self.runq_fnid) == 0: 567 if len(self.runq_fnid) == 0:
608 if not taskData.abort: 568 if not taskData.abort:
609 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.") 569 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.")
610 else: 570 else:
611 bb.msg.fatal(bb.msg.domain.RunQueue, "No active tasks and not in --continue mode?! Please report this bug.") 571 bb.msg.fatal(bb.msg.domain.RunQueue, "No active tasks and not in --continue mode?! Please report this bug.")
612 572
613 bb.msg.note(2, bb.msg.domain.RunQueue, "Pruned %s inactive tasks, %s left" % (delcount, len(self.runq_fnid))) 573 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:
644 604
645 bb.msg.note(2, bb.msg.domain.RunQueue, "Compute totals (have %s endpoint(s))" % len(endpoints)) 605 bb.msg.note(2, bb.msg.domain.RunQueue, "Compute totals (have %s endpoint(s))" % len(endpoints))
646 606
647
648 # Calculate task weights 607 # Calculate task weights
649 # Check of higher length circular dependencies 608 # Check of higher length circular dependencies
650 self.runq_weight = self.calculate_task_weights(endpoints) 609 self.runq_weight = self.calculate_task_weights(endpoints)