summaryrefslogtreecommitdiffstats
path: root/bitbake/lib/bb/runqueue.py
diff options
context:
space:
mode:
authorRichard Purdie <richard.purdie@linuxfoundation.org>2012-06-26 18:00:58 +0000
committerRichard Purdie <richard.purdie@linuxfoundation.org>2012-06-28 16:32:57 +0100
commit5fa6036d49ed7befe6ad50ec95c61a50aec48195 (patch)
tree20c9213096b40af9e3e251eae8c21e621e86c75a /bitbake/lib/bb/runqueue.py
parentbe22b92627408af79e1d62e23e838f5c01cf4fae (diff)
downloadpoky-5fa6036d49ed7befe6ad50ec95c61a50aec48195.tar.gz
bitbake: runqueue: Reimplement recrdepends so it works more correctly
Currently, recrdepends is extremely greedy. For example: do_foo[rdepends] = "somedep:sometask" addtask foo which adds foo with *no* dependencies, will suddenly start appearing as a dependency in every task which uses recrdepends. So far this has been mildy annoying but we now have use cases where this makes no sense at all. This reworks the recrdepends code to avoid this problem. To do this we can no longer collapse things into lists just based on file ID. The problem is this code is extremely performance sensitive. The "preparing runqueue" phase spends a lot of time in these recursive dependency calculations so any change here could negatively impact the user experience. As such, this code has been carefully tested on convoluted dependency trees with operations like "time bitbake world -g". The net result of this change and the preceeding changes combined is a net speed up of these operations in all cases measured. Tests were made comparing "bitbake world -g" task-depends.dot before and after this patch. There *are* differences for example -nativesdk do_build dependencies on -native recipes are no longer present. All removed dependencies appear to be sensible improvements to the system. The "rdepends" cross contamination issue above is also fixed. (Bitbake rev: 82d73423c57569b984ee0ae3d93e3c3bd5dc5216) Signed-off-by: Richard Purdie <richard.purdie@linuxfoundation.org>
Diffstat (limited to 'bitbake/lib/bb/runqueue.py')
-rw-r--r--bitbake/lib/bb/runqueue.py100
1 files changed, 42 insertions, 58 deletions
diff --git a/bitbake/lib/bb/runqueue.py b/bitbake/lib/bb/runqueue.py
index c45287d035..e927afbb86 100644
--- a/bitbake/lib/bb/runqueue.py
+++ b/bitbake/lib/bb/runqueue.py
@@ -375,9 +375,7 @@ class RunQueueData:
375 """ 375 """
376 376
377 runq_build = [] 377 runq_build = []
378 recursive_tdepends = {} 378 recursivetasks = {}
379 runq_recrdepends = []
380 tdepends_fnid = {}
381 379
382 taskData = self.taskData 380 taskData = self.taskData
383 381
@@ -423,9 +421,15 @@ class RunQueueData:
423 if taskid is not None: 421 if taskid is not None:
424 depends.add(taskid) 422 depends.add(taskid)
425 423
424 def add_resolved_dependencies(depids, tasknames, depends):
425 for depid in depids:
426 for taskname in tasknames:
427 taskid = taskData.gettask_id_fromfnid(depid, taskname)
428 if taskid is not None:
429 depends.add(taskid)
430
426 for task in xrange(len(taskData.tasks_name)): 431 for task in xrange(len(taskData.tasks_name)):
427 depends = set() 432 depends = set()
428 recrdepends = []
429 fnid = taskData.tasks_fnid[task] 433 fnid = taskData.tasks_fnid[task]
430 fn = taskData.fn_index[fnid] 434 fn = taskData.fn_index[fnid]
431 task_deps = self.dataCache.task_deps[fn] 435 task_deps = self.dataCache.task_deps[fn]
@@ -459,8 +463,6 @@ class RunQueueData:
459 # 463 #
460 # e.g. do_sometask[depends] = "targetname:do_someothertask" 464 # e.g. do_sometask[depends] = "targetname:do_someothertask"
461 # (makes sure sometask runs after targetname's someothertask) 465 # (makes sure sometask runs after targetname's someothertask)
462 if fnid not in tdepends_fnid:
463 tdepends_fnid[fnid] = set()
464 idepends = taskData.tasks_idepends[task] 466 idepends = taskData.tasks_idepends[task]
465 for (depid, idependtask) in idepends: 467 for (depid, idependtask) in idepends:
466 if depid in taskData.build_targets: 468 if depid in taskData.build_targets:
@@ -471,8 +473,6 @@ class RunQueueData:
471 if taskid is None: 473 if taskid is None:
472 bb.msg.fatal("RunQueue", "Task %s in %s depends upon non-existent task %s in %s" % (taskData.tasks_name[task], fn, idependtask, dep)) 474 bb.msg.fatal("RunQueue", "Task %s in %s depends upon non-existent task %s in %s" % (taskData.tasks_name[task], fn, idependtask, dep))
473 depends.add(taskid) 475 depends.add(taskid)
474 if depdata != fnid:
475 tdepends_fnid[fnid].add(taskid)
476 irdepends = taskData.tasks_irdepends[task] 476 irdepends = taskData.tasks_irdepends[task]
477 for (depid, idependtask) in irdepends: 477 for (depid, idependtask) in irdepends:
478 if depid in taskData.run_targets: 478 if depid in taskData.run_targets:
@@ -483,24 +483,17 @@ class RunQueueData:
483 if taskid is None: 483 if taskid is None:
484 bb.msg.fatal("RunQueue", "Task %s in %s rdepends upon non-existent task %s in %s" % (taskData.tasks_name[task], fn, idependtask, dep)) 484 bb.msg.fatal("RunQueue", "Task %s in %s rdepends upon non-existent task %s in %s" % (taskData.tasks_name[task], fn, idependtask, dep))
485 depends.add(taskid) 485 depends.add(taskid)
486 if depdata != fnid:
487 tdepends_fnid[fnid].add(taskid)
488 486
489 # Resolve recursive 'recrdeptask' dependencies (A) 487 # Resolve recursive 'recrdeptask' dependencies (Part A)
490 # 488 #
491 # e.g. do_sometask[recrdeptask] = "do_someothertask" 489 # e.g. do_sometask[recrdeptask] = "do_someothertask"
492 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively) 490 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
493 # We cover the recursive part of the dependencies below 491 # We cover the recursive part of the dependencies below
494 if 'recrdeptask' in task_deps and taskData.tasks_name[task] in task_deps['recrdeptask']: 492 if 'recrdeptask' in task_deps and taskData.tasks_name[task] in task_deps['recrdeptask']:
495 for taskname in task_deps['recrdeptask'][taskData.tasks_name[task]].split(): 493 tasknames = task_deps['recrdeptask'][taskData.tasks_name[task]].split()
496 recrdepends.append(taskname) 494 recursivetasks[task] = tasknames
497 add_build_dependencies(taskData.depids[fnid], [taskname], depends) 495 add_build_dependencies(taskData.depids[fnid], tasknames, depends)
498 add_runtime_dependencies(taskData.rdepids[fnid], [taskname], depends) 496 add_runtime_dependencies(taskData.rdepids[fnid], tasknames, depends)
499
500 # Rmove all self references
501 if task in depends:
502 logger.debug(2, "Task %s (%s %s) contains self reference! %s", task, taskData.fn_index[taskData.tasks_fnid[task]], taskData.tasks_name[task], depends)
503 depends.remove(task)
504 497
505 self.runq_fnid.append(taskData.tasks_fnid[task]) 498 self.runq_fnid.append(taskData.tasks_fnid[task])
506 self.runq_task.append(taskData.tasks_name[task]) 499 self.runq_task.append(taskData.tasks_name[task])
@@ -509,48 +502,39 @@ class RunQueueData:
509 self.runq_hash.append("") 502 self.runq_hash.append("")
510 503
511 runq_build.append(0) 504 runq_build.append(0)
512 runq_recrdepends.append(recrdepends)
513 505
514 # 506 # Resolve recursive 'recrdeptask' dependencies (Part B)
515 # Build a list of recursive cumulative dependencies for each fnid
516 # We do this by fnid, since if A depends on some task in B
517 # we're interested in later tasks B's fnid might have but B itself
518 # doesn't depend on
519 #
520 # Algorithm is O(tasks) + O(tasks)*O(fnids)
521 #
522 reccumdepends = {}
523 for task in xrange(len(self.runq_fnid)):
524 fnid = self.runq_fnid[task]
525 if fnid not in reccumdepends:
526 if fnid in tdepends_fnid:
527 reccumdepends[fnid] = tdepends_fnid[fnid]
528 else:
529 reccumdepends[fnid] = set()
530 reccumdepends[fnid].update(self.runq_depends[task])
531 for task in xrange(len(self.runq_fnid)):
532 taskfnid = self.runq_fnid[task]
533 for fnid in reccumdepends:
534 if task in reccumdepends[fnid]:
535 reccumdepends[fnid].add(task)
536 if taskfnid in reccumdepends:
537 reccumdepends[fnid].update(reccumdepends[taskfnid])
538
539
540 # Resolve recursive 'recrdeptask' dependencies (B)
541 # 507 #
542 # e.g. do_sometask[recrdeptask] = "do_someothertask" 508 # e.g. do_sometask[recrdeptask] = "do_someothertask"
543 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively) 509 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
544 for task in xrange(len(self.runq_fnid)): 510 # We need to do this separately since we need all of self.runq_depends to be complete before this is processed
545 if len(runq_recrdepends[task]) > 0: 511 extradeps = {}
546 taskfnid = self.runq_fnid[task] 512 for task in recursivetasks:
547 for dep in reccumdepends[taskfnid]: 513 extradeps[task] = set()
548 # Ignore self references 514 tasknames = recursivetasks[task]
549 if dep == task: 515 seendeps = set()
550 continue 516 seenfnid = []
551 for taskname in runq_recrdepends[task]: 517
552 if taskData.tasks_name[dep] == taskname: 518 def generate_recdeps(t):
553 self.runq_depends[task].add(dep) 519 newdeps = set()
520 add_resolved_dependencies([taskData.tasks_fnid[t]], tasknames, newdeps)
521 extradeps[task].update(newdeps)
522 seendeps.add(t)
523 newdeps.add(t)
524 for i in newdeps:
525 for n in self.runq_depends[i]:
526 if n not in seendeps:
527 generate_recdeps(n)
528 generate_recdeps(task)
529
530 for task in xrange(len(taskData.tasks_name)):
531 # Add in extra dependencies
532 if task in extradeps:
533 self.runq_depends[task].update(extradeps[task])
534 # Remove all self references
535 if task in self.runq_depends[task]:
536 logger.debug(2, "Task %s (%s %s) contains self reference! %s", task, taskData.fn_index[taskData.tasks_fnid[task]], taskData.tasks_name[task], self.runq_depends[task])
537 self.runq_depends[task].remove(task)
554 538
555 # Step B - Mark all active tasks 539 # Step B - Mark all active tasks
556 # 540 #