diff options
author | Richard Purdie <rpurdie@linux.intel.com> | 2009-07-21 19:44:23 +0100 |
---|---|---|
committer | Richard Purdie <rpurdie@linux.intel.com> | 2009-07-21 19:44:23 +0100 |
commit | 8f5363d16de17459b654ca780e5bbd6e04b6bb73 (patch) | |
tree | 7c8d6bf31d85c65210a9e1b9fe7ab227963970f3 | |
parent | 133e9e6064195942a95ff58c18a6578de7bcadc7 (diff) | |
download | poky-8f5363d16de17459b654ca780e5bbd6e04b6bb73.tar.gz |
bitbake: Optimise runqueue recursive dependency calculations removing a bottleneck in world builds
Signed-off-by: Richard Purdie <rpurdie@linux.intel.com>
-rw-r--r-- | bitbake-dev/lib/bb/runqueue.py | 190 | ||||
-rw-r--r-- | bitbake/lib/bb/runqueue.py | 193 |
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: | |||
340 | to optimise the execution order. | 340 | to optimise the execution order. |
341 | """ | 341 | """ |
342 | 342 | ||
343 | depends = [] | ||
344 | runq_build = [] | 343 | runq_build = [] |
345 | recursive_tdepends = {} | 344 | recursive_tdepends = {} |
345 | runq_recrdepends = [] | ||
346 | tdepends_fnid = {} | ||
346 | 347 | ||
347 | taskData = self.taskData | 348 | taskData = self.taskData |
348 | 349 | ||
@@ -354,9 +355,9 @@ class RunQueue: | |||
354 | 355 | ||
355 | # Step A - Work out a list of tasks to run | 356 | # Step A - Work out a list of tasks to run |
356 | # | 357 | # |
357 | # Taskdata gives us a list of possible providers for a every target | 358 | # Taskdata gives us a list of possible providers for every build and run |
358 | # ordered by priority (build_targets, run_targets). It also gives | 359 | # target ordered by priority. It also gives information on each of those |
359 | # information on each of those providers. | 360 | # providers. |
360 | # | 361 | # |
361 | # To create the actual list of tasks to execute we fix the list of | 362 | # To create the actual list of tasks to execute we fix the list of |
362 | # providers and then resolve the dependencies into task IDs. This | 363 | # providers and then resolve the dependencies into task IDs. This |
@@ -364,10 +365,14 @@ class RunQueue: | |||
364 | # rdeptast, recrdeptask, idepends). | 365 | # rdeptast, recrdeptask, idepends). |
365 | 366 | ||
366 | for task in range(len(taskData.tasks_name)): | 367 | for task in range(len(taskData.tasks_name)): |
368 | depends = [] | ||
369 | recrdepends = [] | ||
367 | fnid = taskData.tasks_fnid[task] | 370 | fnid = taskData.tasks_fnid[task] |
368 | fn = taskData.fn_index[fnid] | 371 | fn = taskData.fn_index[fnid] |
369 | task_deps = self.dataCache.task_deps[fn] | 372 | task_deps = self.dataCache.task_deps[fn] |
370 | 373 | ||
374 | bb.msg.debug(2, bb.msg.domain.RunQueue, "Processing %s:%s" %(fn, taskData.tasks_name[task])) | ||
375 | |||
371 | if fnid not in taskData.failed_fnids: | 376 | if fnid not in taskData.failed_fnids: |
372 | 377 | ||
373 | # Resolve task internal dependencies | 378 | # Resolve task internal dependencies |
@@ -407,6 +412,8 @@ class RunQueue: | |||
407 | # | 412 | # |
408 | # e.g. do_sometask[depends] = "targetname:do_someothertask" | 413 | # e.g. do_sometask[depends] = "targetname:do_someothertask" |
409 | # (makes sure sometask runs after targetname's someothertask) | 414 | # (makes sure sometask runs after targetname's someothertask) |
415 | if fnid not in tdepends_fnid: | ||
416 | tdepends_fnid[fnid] = set() | ||
410 | idepends = taskData.tasks_idepends[task] | 417 | idepends = taskData.tasks_idepends[task] |
411 | for (depid, idependtask) in idepends: | 418 | for (depid, idependtask) in idepends: |
412 | if depid in taskData.build_targets: | 419 | if depid in taskData.build_targets: |
@@ -414,122 +421,37 @@ class RunQueue: | |||
414 | depdata = taskData.build_targets[depid][0] | 421 | depdata = taskData.build_targets[depid][0] |
415 | if depdata is not None: | 422 | if depdata is not None: |
416 | dep = taskData.fn_index[depdata] | 423 | dep = taskData.fn_index[depdata] |
417 | depends.append(taskData.gettask_id(dep, idependtask)) | 424 | taskid = taskData.gettask_id(dep, idependtask) |
418 | 425 | depends.append(taskid) | |
419 | # Create a list of recursive dependent tasks (from tdepends) and cache | 426 | if depdata != fnid: |
420 | def get_recursive_tdepends(task): | 427 | tdepends_fnid[fnid].add(taskid) |
421 | if not task: | 428 | |
422 | return [] | 429 | |
423 | if task in recursive_tdepends: | 430 | # Resolve recursive 'recrdeptask' dependencies (A) |
424 | return recursive_tdepends[task] | ||
425 | |||
426 | fnid = taskData.tasks_fnid[task] | ||
427 | taskids = taskData.gettask_ids(fnid) | ||
428 | |||
429 | rectdepends = taskids | ||
430 | nextdeps = taskids | ||
431 | while len(nextdeps) != 0: | ||
432 | newdeps = [] | ||
433 | for nextdep in nextdeps: | ||
434 | for tdepend in taskData.tasks_tdepends[nextdep]: | ||
435 | if tdepend not in rectdepends: | ||
436 | rectdepends.append(tdepend) | ||
437 | newdeps.append(tdepend) | ||
438 | nextdeps = newdeps | ||
439 | recursive_tdepends[task] = rectdepends | ||
440 | return rectdepends | ||
441 | |||
442 | # Using the list of tdepends for this task create a list of | ||
443 | # the recursive idepends we have | ||
444 | def get_recursive_idepends(task): | ||
445 | if not task: | ||
446 | return [] | ||
447 | rectdepends = get_recursive_tdepends(task) | ||
448 | |||
449 | recidepends = [] | ||
450 | for tdepend in rectdepends: | ||
451 | for idepend in taskData.tasks_idepends[tdepend]: | ||
452 | recidepends.append(idepend) | ||
453 | return recidepends | ||
454 | |||
455 | def add_recursive_build(depid, depfnid): | ||
456 | """ | ||
457 | Add build depends of depid to depends | ||
458 | (if we've not see it before) | ||
459 | (calls itself recursively) | ||
460 | """ | ||
461 | if str(depid) in dep_seen: | ||
462 | return | ||
463 | dep_seen.append(depid) | ||
464 | if depid in taskData.build_targets: | ||
465 | depdata = taskData.build_targets[depid][0] | ||
466 | if depdata is not None: | ||
467 | dep = taskData.fn_index[depdata] | ||
468 | # Need to avoid creating new tasks here | ||
469 | taskid = taskData.gettask_id(dep, taskname, False) | ||
470 | if taskid is not None: | ||
471 | depends.append(taskid) | ||
472 | fnid = taskData.tasks_fnid[taskid] | ||
473 | #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid]) | ||
474 | else: | ||
475 | fnid = taskData.getfn_id(dep) | ||
476 | for nextdepid in taskData.depids[fnid]: | ||
477 | if nextdepid not in dep_seen: | ||
478 | add_recursive_build(nextdepid, fnid) | ||
479 | for nextdepid in taskData.rdepids[fnid]: | ||
480 | if nextdepid not in rdep_seen: | ||
481 | add_recursive_run(nextdepid, fnid) | ||
482 | for (idependid, idependtask) in get_recursive_idepends(taskid): | ||
483 | if idependid not in dep_seen: | ||
484 | add_recursive_build(idependid, fnid) | ||
485 | |||
486 | def add_recursive_run(rdepid, depfnid): | ||
487 | """ | ||
488 | Add runtime depends of rdepid to depends | ||
489 | (if we've not see it before) | ||
490 | (calls itself recursively) | ||
491 | """ | ||
492 | if str(rdepid) in rdep_seen: | ||
493 | return | ||
494 | rdep_seen.append(rdepid) | ||
495 | if rdepid in taskData.run_targets: | ||
496 | depdata = taskData.run_targets[rdepid][0] | ||
497 | if depdata is not None: | ||
498 | dep = taskData.fn_index[depdata] | ||
499 | # Need to avoid creating new tasks here | ||
500 | taskid = taskData.gettask_id(dep, taskname, False) | ||
501 | if taskid is not None: | ||
502 | depends.append(taskid) | ||
503 | fnid = taskData.tasks_fnid[taskid] | ||
504 | #print "Added %s (%s) due to %s" % (taskid, taskData.fn_index[fnid], taskData.fn_index[depfnid]) | ||
505 | else: | ||
506 | fnid = taskData.getfn_id(dep) | ||
507 | for nextdepid in taskData.depids[fnid]: | ||
508 | if nextdepid not in dep_seen: | ||
509 | add_recursive_build(nextdepid, fnid) | ||
510 | for nextdepid in taskData.rdepids[fnid]: | ||
511 | if nextdepid not in rdep_seen: | ||
512 | add_recursive_run(nextdepid, fnid) | ||
513 | for (idependid, idependtask) in get_recursive_idepends(taskid): | ||
514 | if idependid not in dep_seen: | ||
515 | add_recursive_build(idependid, fnid) | ||
516 | |||
517 | # Resolve recursive 'recrdeptask' dependencies | ||
518 | # | 431 | # |
519 | # e.g. do_sometask[recrdeptask] = "do_someothertask" | 432 | # e.g. do_sometask[recrdeptask] = "do_someothertask" |
520 | # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively) | 433 | # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively) |
434 | # We cover the recursive part of the dependencies below | ||
521 | if 'recrdeptask' in task_deps and taskData.tasks_name[task] in task_deps['recrdeptask']: | 435 | if 'recrdeptask' in task_deps and taskData.tasks_name[task] in task_deps['recrdeptask']: |
522 | for taskname in task_deps['recrdeptask'][taskData.tasks_name[task]].split(): | 436 | for taskname in task_deps['recrdeptask'][taskData.tasks_name[task]].split(): |
523 | dep_seen = [] | 437 | recrdepends.append(taskname) |
524 | rdep_seen = [] | 438 | for depid in taskData.rdepids[fnid]: |
525 | idep_seen = [] | 439 | if depid in taskData.run_targets: |
440 | depdata = taskData.run_targets[depid][0] | ||
441 | if depdata is not None: | ||
442 | dep = taskData.fn_index[depdata] | ||
443 | taskid = taskData.gettask_id(dep, taskname, False) | ||
444 | if taskid is not None: | ||
445 | depends.append(taskid) | ||
526 | for depid in taskData.depids[fnid]: | 446 | for depid in taskData.depids[fnid]: |
527 | add_recursive_build(depid, fnid) | 447 | # Won't be in build_targets if ASSUME_PROVIDED |
528 | for rdepid in taskData.rdepids[fnid]: | 448 | if depid in taskData.build_targets: |
529 | add_recursive_run(rdepid, fnid) | 449 | depdata = taskData.build_targets[depid][0] |
530 | deptaskid = taskData.gettask_id(fn, taskname, False) | 450 | if depdata is not None: |
531 | for (idependid, idependtask) in get_recursive_idepends(deptaskid): | 451 | dep = taskData.fn_index[depdata] |
532 | add_recursive_build(idependid, fnid) | 452 | taskid = taskData.gettask_id(dep, taskname, False) |
453 | if taskid is not None: | ||
454 | depends.append(taskid) | ||
533 | 455 | ||
534 | # Rmove all self references | 456 | # Rmove all self references |
535 | if task in depends: | 457 | if task in depends: |
@@ -540,13 +462,51 @@ class RunQueue: | |||
540 | newdep.append(dep) | 462 | newdep.append(dep) |
541 | depends = newdep | 463 | depends = newdep |
542 | 464 | ||
543 | |||
544 | self.runq_fnid.append(taskData.tasks_fnid[task]) | 465 | self.runq_fnid.append(taskData.tasks_fnid[task]) |
545 | self.runq_task.append(taskData.tasks_name[task]) | 466 | self.runq_task.append(taskData.tasks_name[task]) |
546 | self.runq_depends.append(set(depends)) | 467 | self.runq_depends.append(set(depends)) |
547 | self.runq_revdeps.append(set()) | 468 | self.runq_revdeps.append(set()) |
548 | 469 | ||
549 | runq_build.append(0) | 470 | runq_build.append(0) |
471 | runq_recrdepends.append(recrdepends) | ||
472 | |||
473 | # | ||
474 | # Build a list of recursive cumulative dependencies for each fnid | ||
475 | # We do this by fnid, since if A depends on some task in B | ||
476 | # we're interested in later tasks B's fnid might have but B itself | ||
477 | # doesn't depend on | ||
478 | # | ||
479 | # Algorithm is O(tasks) + O(tasks)*O(fnids) | ||
480 | # | ||
481 | reccumdepends = {} | ||
482 | for task in range(len(self.runq_fnid)): | ||
483 | fnid = self.runq_fnid[task] | ||
484 | if fnid not in reccumdepends: | ||
485 | reccumdepends[fnid] = set() | ||
486 | if task in self.runq_depends: | ||
487 | reccumdepends[fnid].update(self.runq_depends[task]) | ||
488 | if fnid in tdepends_fnid: | ||
489 | reccumdepends[fnid].update(tdepends_fnid[fnid]) | ||
490 | for task in range(len(self.runq_fnid)): | ||
491 | taskfnid = self.runq_fnid[task] | ||
492 | for fnid in reccumdepends: | ||
493 | if task in reccumdepends[fnid]: | ||
494 | reccumdepends[fnid].add(task) | ||
495 | if taskfnid in reccumdepends: | ||
496 | reccumdepends[fnid].update(reccumdepends[taskfnid]) | ||
497 | |||
498 | |||
499 | # Resolve recursive 'recrdeptask' dependencies (B) | ||
500 | # | ||
501 | # e.g. do_sometask[recrdeptask] = "do_someothertask" | ||
502 | # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively) | ||
503 | for task in range(len(self.runq_fnid)): | ||
504 | if len(runq_recrdepends[task]) > 0: | ||
505 | taskfnid = self.runq_fnid[task] | ||
506 | for dep in reccumdepends[taskfnid]: | ||
507 | for taskname in runq_recrdepends[task]: | ||
508 | if taskData.tasks_name[dep] == taskname: | ||
509 | self.runq_depends[task].add(dep) | ||
550 | 510 | ||
551 | # Step B - Mark all active tasks | 511 | # Step B - Mark all active tasks |
552 | # | 512 | # |
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) |