summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorRichard Purdie <richard.purdie@linuxfoundation.org>2018-01-28 10:36:06 +0000
committerRichard Purdie <richard.purdie@linuxfoundation.org>2018-02-06 11:06:30 +0000
commitdafa1ac8646954fa02db2a3e572adc6a957edd39 (patch)
tree28cddabf52a39914b8d707775749f1fa0ff672cf
parent2ae62f0d2b4f130a12b4b3bed38a9cd82a5bb6cf (diff)
downloadpoky-dafa1ac8646954fa02db2a3e572adc6a957edd39.tar.gz
bitbake: runqueue: Rewrite and optimize recrdepends handling
This is a performance sensitive piece of code and the shear number of recursive loops is causing a significant and unscalable performance pain point. This change moves to a two step approach, firstly generating a list of recursive dependencies for any task, then applying this to the recursive tasks, iterating over things until no further dependencies are added. It was noticed an optimisation is possible and the list of recursive tasks need not contain the taskname, only the base task id. This allows a significant performance improvement and limits the size of the resursive task lists, improving speed. (Bitbake rev: eba738ac5672556eaab4f3374c8025c322761c4a) Signed-off-by: Richard Purdie <richard.purdie@linuxfoundation.org>
-rw-r--r--bitbake/lib/bb/runqueue.py134
1 files changed, 83 insertions, 51 deletions
diff --git a/bitbake/lib/bb/runqueue.py b/bitbake/lib/bb/runqueue.py
index bbfe9eeee0..d7acfabef4 100644
--- a/bitbake/lib/bb/runqueue.py
+++ b/bitbake/lib/bb/runqueue.py
@@ -74,9 +74,6 @@ def build_tid(mc, fn, taskname):
74 return "multiconfig:" + mc + ":" + fn + ":" + taskname 74 return "multiconfig:" + mc + ":" + fn + ":" + taskname
75 return fn + ":" + taskname 75 return fn + ":" + taskname
76 76
77def tid_replacetask(tid, taskname):
78 return tid.rsplit(":", 1)[0] + ":" + taskname
79
80class RunQueueStats: 77class RunQueueStats:
81 """ 78 """
82 Holds statistics on the tasks handled by the associated runQueue 79 Holds statistics on the tasks handled by the associated runQueue
@@ -670,71 +667,106 @@ class RunQueueData:
670 recursiveitasks[tid].append(newdep) 667 recursiveitasks[tid].append(newdep)
671 668
672 self.runtaskentries[tid].depends = depends 669 self.runtaskentries[tid].depends = depends
670 # Remove all self references
671 self.runtaskentries[tid].depends.discard(tid)
673 672
674 #self.dump_data() 673 #self.dump_data()
675 674
675 self.init_progress_reporter.next_stage()
676
676 # Resolve recursive 'recrdeptask' dependencies (Part B) 677 # Resolve recursive 'recrdeptask' dependencies (Part B)
677 # 678 #
678 # e.g. do_sometask[recrdeptask] = "do_someothertask" 679 # e.g. do_sometask[recrdeptask] = "do_someothertask"
679 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively) 680 # (makes sure sometask runs after someothertask of all DEPENDS, RDEPENDS and intertask dependencies, recursively)
680 # We need to do this separately since we need all of runtaskentries[*].depends to be complete before this is processed 681 # We need to do this separately since we need all of runtaskentries[*].depends to be complete before this is processed
681 self.init_progress_reporter.next_stage() 682
682 extradeps = True 683 # Generating/interating recursive lists of dependencies is painful and potentially slow
684 # Precompute recursive task dependencies here by:
685 # a) create a temp list of reverse dependencies (revdeps)
686 # b) walk up the ends of the chains (when a given task no longer has dependencies i.e. len(deps) == 0)
687 # c) combine the total list of dependencies in cumulativedeps
688 # d) optimise by pre-truncating 'task' off the items in cumulativedeps (keeps items in sets lower)
689
690
691 revdeps = {}
692 deps = {}
693 cumulativedeps = {}
694 for tid in self.runtaskentries:
695 deps[tid] = set(self.runtaskentries[tid].depends)
696 revdeps[tid] = set()
697 cumulativedeps[tid] = set()
698 # Generate a temp list of reverse dependencies
699 for tid in self.runtaskentries:
700 for dep in self.runtaskentries[tid].depends:
701 revdeps[dep].add(tid)
702 # Find the dependency chain endpoints
703 endpoints = set()
704 for tid in self.runtaskentries:
705 if len(deps[tid]) == 0:
706 endpoints.add(tid)
707 # Iterate the chains collating dependencies
708 while endpoints:
709 next = set()
710 for tid in endpoints:
711 for dep in revdeps[tid]:
712 cumulativedeps[dep].add(fn_from_tid(tid))
713 cumulativedeps[dep].update(cumulativedeps[tid])
714 if tid in deps[dep]:
715 deps[dep].remove(tid)
716 if len(deps[dep]) == 0:
717 next.add(dep)
718 endpoints = next
719 #for tid in deps:
720 # if len(deps[tid]) != 0:
721 # bb.warn("Sanity test failure, dependencies left for %s (%s)" % (tid, deps[tid]))
722
683 # Loop here since recrdeptasks can depend upon other recrdeptasks and we have to 723 # Loop here since recrdeptasks can depend upon other recrdeptasks and we have to
684 # resolve these recursively until we aren't adding any further extra dependencies 724 # resolve these recursively until we aren't adding any further extra dependencies
725 extradeps = True
685 while extradeps: 726 while extradeps:
686 extradeps = {} 727 extradeps = 0
687 728 for tid in recursivetasks:
688 for taskcounter, tid in enumerate(recursivetasks):
689 extradeps[tid] = set()
690
691 tasknames = recursivetasks[tid] 729 tasknames = recursivetasks[tid]
692 seendeps = set()
693 seenbasedeps = set()
694
695 def generate_recdeps(t):
696 newdeps = set()
697 basetid = fn_from_tid(t)
698 if basetid not in seenbasedeps:
699 for taskname in tasknames:
700 newtid = tid_replacetask(t, taskname)
701 if newtid in self.runtaskentries and newtid not in seendeps:
702 newdeps.add(newtid)
703 extradeps[tid].add(newtid)
704 seenbasedeps.add(basetid)
705 seendeps.add(t)
706 newdeps.add(t)
707 for i in newdeps:
708 if i not in self.runtaskentries:
709 # Not all recipes might have the recrdeptask task as a task
710 continue
711 for n in self.runtaskentries[i].depends:
712 if n not in seendeps:
713 generate_recdeps(n)
714 generate_recdeps(tid)
715 730
731 totaldeps = set(self.runtaskentries[tid].depends)
716 if tid in recursiveitasks: 732 if tid in recursiveitasks:
733 totaldeps.update(recursiveitasks[tid])
717 for dep in recursiveitasks[tid]: 734 for dep in recursiveitasks[tid]:
718 generate_recdeps(dep) 735 if dep not in self.runtaskentries:
736 continue
737 totaldeps.update(self.runtaskentries[dep].depends)
719 738
720 for tid in self.runtaskentries: 739 deps = set()
721 # Add in extra dependencies 740 for dep in totaldeps:
722 if tid in extradeps: 741 if dep in cumulativedeps:
723 extradeps[tid].difference_update(self.runtaskentries[tid].depends) 742 deps.update(cumulativedeps[dep])
724 self.runtaskentries[tid].depends.update(extradeps[tid]) 743
725 # Remove circular references so that do_a[recrdeptask] = "do_a do_b" can work 744 for t in deps:
726 self.runtaskentries[tid].depends.difference_update(recursivetasksselfref) 745 for taskname in tasknames:
727 extradeps[tid].difference_update(recursivetasksselfref) 746 newtid = t + ":" + taskname
728 if not len(extradeps[tid]): 747 if newtid == tid:
729 del extradeps[tid] 748 continue
730 if tid not in recursivetasks: 749 if newtid in self.runtaskentries and newtid not in self.runtaskentries[tid].depends:
731 bb.warn(tid) 750 extradeps += 1
732 # Remove all self references 751 self.runtaskentries[tid].depends.add(newtid)
733 if tid in self.runtaskentries[tid].depends:
734 logger.debug(2, "Task %s contains self reference!", tid)
735 self.runtaskentries[tid].depends.remove(tid)
736 752
737 bb.debug(1, "Added %s recursive dependencies in this loop" % len(extradeps)) 753 # Handle recursive tasks which depend upon other recursive tasks
754 deps = set()
755 for dep in self.runtaskentries[tid].depends.intersection(recursivetasks):
756 deps.update(self.runtaskentries[dep].depends.difference(self.runtaskentries[tid].depends))
757 for newtid in deps:
758 for taskname in tasknames:
759 if not newtid.endswith(":" + taskname):
760 continue
761 if newtid in self.runtaskentries:
762 extradeps += 1
763 self.runtaskentries[tid].depends.add(newtid)
764
765 bb.debug(1, "Added %s recursive dependencies in this loop" % extradeps)
766
767 # Remove recrdeptask circular references so that do_a[recrdeptask] = "do_a do_b" can work
768 for tid in self.runtaskentries:
769 self.runtaskentries[tid].depends.difference_update(recursivetasksselfref)
738 770
739 self.init_progress_reporter.next_stage() 771 self.init_progress_reporter.next_stage()
740 772