[Buildroot] [PATCH 00/11] support/graphs: fixup and speedup graph dependencies (branch yem/graphs-from-make-2)

[Buildroot] [PATCH 00/11] support/graphs: fixup and speedup graph dependencies (branch yem/graphs-from-make-2)

[Yann E. MORIN]

Hello All!

This series is a joint effort with Thomas, to get a graph-depends that
is more reliable (does not forget some dependencies), and faster.

TL;DR: we fixed it, and it is faster. ;-)

Long story:

Currently, graph-depends is used in three ways: to graph the dependency
tree (which is its prime objective, hence the name), to check for
circular dependencies, and to compute the list of recursive direct or
reverse dependencies.

In so doing, graph-depends needs to build up the dependency tree, so it
calls to make to get an initial list of packages, and then iteratively
calls it again and again to get the dependencies, until none are
returned anymore. Running make is rather costly, because it scans the
entire collection of .mk; running it iteratively is thus in O(n), with n
the dependency depth.

This series was started with the realissation that 'make' already knows
about the dependency tree (that's its job, damned!).

So, this series stats with some commits which actually fix graph-depends
to not forget any dependency, then cut down on madatory dependencies.

Building upon that, we introduce the necesary infrastructure in our
Makefiles, to return the dependency tree, and use that from
graph-depends.

Incidentally, we also notice that recursive, direct and reverse,
dependencies can also be had from make in a much les costly manner than
with graph-depends.


Regards,
Yann E. MORIN.


The following changes since commit 13c43455a05b036002e79808ca1c8e0d91d7871b

  Merge branch 'next' (2018-12-02 08:16:10 +0100)


are available in the git repository at:

  git://git.buildroot.org/~ymorin/git/buildroot.git

for you to fetch changes up to 176c21d13a1e9af82e4801e5b43ea86dead4f007

  supprt/graph-depends: use the new make-based dependency tree (2018-12-02 09:49:43 +0100)


----------------------------------------------------------------
Thomas Petazzoni (3):
      support/scripts/graph-depends: use proper rootpkg in remove_extra_deps()
      support/scripts/graph-depends: introduce MANDATORY_DEPS array
      support/scripts/graph-depends: make sure mandatory deps are displayed

Yann E. MORIN (8):
      support/graph-depends: drop legacy target-exceptions
      support/graph-depends: add option to exclude mandatory deps
      support/graph-depends: also cut on host-skeleton
      support/graph-depends: also cut on host-tar
      support/graph-depends: also cut on host-gzip
      infra/pkg-generic: use pure Makefile-based recursive dependencies
      core: add make-based full-dependency list
      supprt/graph-depends: use the new make-based dependency tree

 Makefile                      |   4 ++
 fs/common.mk                  |   8 +++
 package/pkg-generic.mk        |  10 +--
 package/pkg-utils.mk          |  13 ++++
 support/scripts/brpkgutil.py  | 106 ++++++++++++++---------------
 support/scripts/graph-depends | 155 +++++++++++-------------------------------
 6 files changed, 119 insertions(+), 177 deletions(-)

-- 
.-----------------.--------------------.------------------.--------------------.
|  Yann E. MORIN  | Real-Time Embedded | /"\ ASCII RIBBON | Erics' conspiracy: |
| +33 662 376 056 | Software  Designer | \ / CAMPAIGN     |  ___               |
| +33 223 225 172 `------------.-------:  X  AGAINST      |  \e/  There is no  |
| http://ymorin.is-a-geek.org/ | _/*\_ | / \ HTML MAIL    |   v   conspiracy.  |
'------------------------------^-------^------------------^--------------------'

[Buildroot] [PATCH 01/11] support/graph-depends: drop legacy target-exceptions

[Yann E. MORIN]

Currently, we avoid drawing the dependencies that we call 'target
exceptions', becasue they initially were returned by 'show-targets',
when they in fact were not really packages and thus should not be on
the graph.

However, those two exceptions have no longer been reported in the output
of show-targets since we merged very old initial top-level parallel
build way back in 2014, with commit a24877586a56 (Makefile: add support
for top-level parallel make), where they had been converted into purely
internal rules.

4 years have passed, we can now drop those exceptions from the
graph-depends script.

This concludes the cleanup initiated three years ago with commit
0b32791f0076 (graph-depends: remove absent targets from
TARGET_EXCEPTIONS).

Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
---
 support/scripts/graph-depends | 9 ---------
 1 file changed, 9 deletions(-)

diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index 3c091da5e0..3526a51662 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -100,12 +100,6 @@ def pkg_node_name(pkg):
     return "_" + pkg.replace("-", "")
 
 
-TARGET_EXCEPTIONS = [
-    "target-finalize",
-    "target-post-image",
-]
-
-
 # Basic cache for the results of the is_dep() function, in order to
 # optimize the execution time. The cache is a dict of dict of boolean
 # values. The key to the primary dict is "pkg", and the key of the
@@ -384,9 +378,6 @@ def main():
         allpkgs.append('all')
         filtered_targets = []
         for tg in targets:
-            # Skip uninteresting targets
-            if tg in TARGET_EXCEPTIONS:
-                continue
             dependencies.append(('all', tg))
             filtered_targets.append(tg)
         deps = get_all_depends(filtered_targets, get_depends_func)
-- 
2.14.1

[Buildroot] [PATCH 01/11] support/graph-depends: drop legacy target-exceptions

[Thomas Petazzoni]

Hello,

On Sun,  2 Dec 2018 10:04:33 +0100, Yann E. MORIN wrote:
> Currently, we avoid drawing the dependencies that we call 'target
> exceptions', becasue they initially were returned by 'show-targets',
> when they in fact were not really packages and thus should not be on
> the graph.
> 
> However, those two exceptions have no longer been reported in the output
> of show-targets since we merged very old initial top-level parallel
> build way back in 2014, with commit a24877586a56 (Makefile: add support
> for top-level parallel make), where they had been converted into purely
> internal rules.
> 
> 4 years have passed, we can now drop those exceptions from the
> graph-depends script.
> 
> This concludes the cleanup initiated three years ago with commit
> 0b32791f0076 (graph-depends: remove absent targets from
> TARGET_EXCEPTIONS).
> 
> Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
> Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
> ---
>  support/scripts/graph-depends | 9 ---------
>  1 file changed, 9 deletions(-)

Applied to master, thanks.

Thomas
-- 
Thomas Petazzoni, CTO, Bootlin
Embedded Linux and Kernel engineering
https://bootlin.com

[Buildroot] [PATCH 02/11] support/scripts/graph-depends: use proper rootpkg in remove_extra_deps()

[Yann E. MORIN]

From: Thomas Petazzoni <thomas.petazzoni@bootlin.com>

The remove_extra_deps() function removes dependencies that we are not
interested in seeing in the dependency graph. It does this for all
packages, except the 'all' package, which on full dependency graphs is
the root of the tree.

However, this doesn't take into account package-specific dependency
graphs (i.e make <pkg>-graph-depends) where the root is not 'all', but
'<pkg>'. Due to this, dependencies on "mandatory deps" were not
visible at all, i.e the toolchain package (and its dependencies) and
the skeleton package (and its dependencies) were not displayed in
package-specific dependency graphs.

To fix this, we use the existing rootpkg variable instead of
hardcoding 'all'.

Signed-off-by: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
---
 support/scripts/graph-depends | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index 3526a51662..f1b6b142fb 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -205,12 +205,12 @@ def check_circular_deps(deps):
 
 # This functions trims down the dependency list of all packages.
 # It applies in sequence all the dependency-elimination methods.
-def remove_extra_deps(deps, transitive):
+def remove_extra_deps(deps, rootpkg, transitive):
     for pkg in list(deps.keys()):
-        if not pkg == 'all':
+        if not pkg == rootpkg:
             deps[pkg] = remove_mandatory_deps(pkg, deps)
     for pkg in list(deps.keys()):
-        if not transitive or pkg == 'all':
+        if not transitive or pkg == rootpkg:
             deps[pkg] = remove_transitive_deps(pkg, deps)
     return deps
 
@@ -401,7 +401,7 @@ def main():
     if check_only:
         sys.exit(0)
 
-    dict_deps = remove_extra_deps(dict_deps, args.transitive)
+    dict_deps = remove_extra_deps(dict_deps, rootpkg, args.transitive)
     dict_version = brpkgutil.get_version([pkg for pkg in allpkgs
                                           if pkg != "all" and not pkg.startswith("root")])
 
-- 
2.14.1

[Buildroot] [PATCH 02/11] support/scripts/graph-depends: use proper rootpkg in remove_extra_deps()

[Thomas Petazzoni]

Hello,

On Sun,  2 Dec 2018 10:04:34 +0100, Yann E. MORIN wrote:
> From: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
> 
> The remove_extra_deps() function removes dependencies that we are not
> interested in seeing in the dependency graph. It does this for all
> packages, except the 'all' package, which on full dependency graphs is
> the root of the tree.
> 
> However, this doesn't take into account package-specific dependency
> graphs (i.e make <pkg>-graph-depends) where the root is not 'all', but
> '<pkg>'. Due to this, dependencies on "mandatory deps" were not
> visible at all, i.e the toolchain package (and its dependencies) and
> the skeleton package (and its dependencies) were not displayed in
> package-specific dependency graphs.
> 
> To fix this, we use the existing rootpkg variable instead of
> hardcoding 'all'.
> 
> Signed-off-by: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
> Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
> ---
>  support/scripts/graph-depends | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)

Applied to master, thanks.

Thomas
-- 
Thomas Petazzoni, CTO, Bootlin
Embedded Linux and Kernel engineering
https://bootlin.com

[Buildroot] [PATCH 03/11] support/scripts/graph-depends: introduce MANDATORY_DEPS array

[Yann E. MORIN]

From: Thomas Petazzoni <thomas.petazzoni@bootlin.com>

This array will be re-used in another function in a follow-up commit,
so it makes sense to factor it out.

Signed-off-by: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
---
 support/scripts/graph-depends | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index f1b6b142fb..d2b100f385 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -170,10 +170,15 @@ def remove_transitive_deps(pkg, deps):
     return new_d
 
 
+# List of dependencies that all/many packages have, and that we want
+# to trim when generating the dependency graph.
+MANDATORY_DEPS = ['toolchain', 'skeleton']
+
+
 # This function removes the dependency on some 'mandatory' package, like the
 # 'toolchain' package, or the 'skeleton' package
 def remove_mandatory_deps(pkg, deps):
-    return [p for p in deps[pkg] if p not in ['toolchain', 'skeleton']]
+    return [p for p in deps[pkg] if p not in MANDATORY_DEPS]
 
 
 # This function will check that there is no loop in the dependency chain
-- 
2.14.1

[Buildroot] [PATCH 03/11] support/scripts/graph-depends: introduce MANDATORY_DEPS array

[Thomas Petazzoni]

Hello,

On Sun,  2 Dec 2018 10:04:35 +0100, Yann E. MORIN wrote:
> From: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
> 
> This array will be re-used in another function in a follow-up commit,
> so it makes sense to factor it out.
> 
> Signed-off-by: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
> Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
> ---
>  support/scripts/graph-depends | 7 ++++++-
>  1 file changed, 6 insertions(+), 1 deletion(-)

Applied to master, thanks.

Thomas
-- 
Thomas Petazzoni, CTO, Bootlin
Embedded Linux and Kernel engineering
https://bootlin.com

[Buildroot] [PATCH 04/11] support/graph-depends: add option to exclude mandatory deps

[Yann E. MORIN]

Some times, multiple dependency graphs for a set of packages (mostly
the application-level packages for the project) are included in reports
(e.g. delivery notes). Repeating the mandatory dependencies on all
those graphs is useless and clutters the important dependencies.

When we had only two such mandatory dependencies (toolchain, skeleton),
it was manageable to list them as manual exclusions:
    -x toolchain -x skeleton

But we now have quite a few such dependencies, and it becomes a bit more
cumbersome to manage, not counting the ones we may add in the future.

Add an option to exclude all those mandatory dependencies, tio generate
neat graphs.

Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
---
 support/scripts/graph-depends | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index d2b100f385..d17efe4cc0 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -302,6 +302,8 @@ def parse_args():
                         "'host' to stop on host packages.")
     parser.add_argument("--exclude", "-x", metavar="PACKAGE", dest="exclude_list", action="append",
                         help="Like --stop-on, but do not add PACKAGE to the graph.")
+    parser.add_argument("--exclude-mandatory", "-X", action="store_true",
+                        help="Like if -x was passed for all mandatory dependencies.")
     parser.add_argument("--colors", "-c", metavar="COLOR_LIST", dest="colors",
                         default="lightblue,grey,gainsboro",
                         help="Comma-separated list of the three colors to use" +
@@ -355,6 +357,9 @@ def main():
     else:
         exclude_list = args.exclude_list
 
+    if args.exclude_mandatory:
+        exclude_list += MANDATORY_DEPS
+
     if args.direct:
         get_depends_func = brpkgutil.get_depends
         arrow_dir = "forward"
-- 
2.14.1

[Buildroot] [PATCH 05/11] support/scripts/graph-depends: make sure mandatory deps are displayed

[Yann E. MORIN]

From: Thomas Petazzoni <thomas.petazzoni@bootlin.com>

The current graph-depends implementation filters out a number of
"mandatory" dependencies that all packages have: dependency on
"toolchain" and dependency on "skeleton".

Despite this filtering, in full graph dependencies, "toolchain" and
"skeleton" are still shown, because they are target packages, and
therefore appear in the result of "make show-targets". Thanks to this,
they will be visible as dependencies of the "ALL" node, which is the
root of the dependency tree.

However, as we are going to introduce host-skeleton as a "mandatory
dependency" to be filtered out, this is no longer going to work.

This commit adjusts the remove_extra_deps() function to ensure that
when a mandatory dependency is removed, this dependency exists between
the root of the dependency tree and the mandatory dependency.

This issue was noticed by Yann E. Morin, and this commit provides a
different implementation than what Yann proposed in
https://patchwork.ozlabs.org/patch/910453/.

Signed-off-by: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
[yann.morin.1998 at free.fr:
  - list mandatory deps before removing them
  - fix flake8 warnings
]
Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
---
 support/scripts/graph-depends | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index d17efe4cc0..5c5de7dd0b 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -181,6 +181,12 @@ def remove_mandatory_deps(pkg, deps):
     return [p for p in deps[pkg] if p not in MANDATORY_DEPS]
 
 
+# This function returns all dependencies of pkg that are part of the
+# mandatory dependencies:
+def get_mandatory_deps(pkg, deps):
+    return [p for p in deps[pkg] if p in MANDATORY_DEPS]
+
+
 # This function will check that there is no loop in the dependency chain
 # As a side effect, it builds up the dependency cache.
 def check_circular_deps(deps):
@@ -213,6 +219,9 @@ def check_circular_deps(deps):
 def remove_extra_deps(deps, rootpkg, transitive):
     for pkg in list(deps.keys()):
         if not pkg == rootpkg:
+            for d in get_mandatory_deps(pkg, deps):
+                if d not in deps[rootpkg]:
+                    deps[rootpkg].append(d)
             deps[pkg] = remove_mandatory_deps(pkg, deps)
     for pkg in list(deps.keys()):
         if not transitive or pkg == rootpkg:
-- 
2.14.1

[Buildroot] [PATCH 06/11] support/graph-depends: also cut on host-skeleton

[Yann E. MORIN]

host-skeleton is a dependency of almost all packages, except a very few.
As such, it clutters the dependency graph uselessly.

Do with it as we do for the skeleton: cut the dependency chains.

Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
---
 support/scripts/graph-depends | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index 5c5de7dd0b..c3e5d83ee8 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -172,7 +172,7 @@ def remove_transitive_deps(pkg, deps):
 
 # List of dependencies that all/many packages have, and that we want
 # to trim when generating the dependency graph.
-MANDATORY_DEPS = ['toolchain', 'skeleton']
+MANDATORY_DEPS = ['toolchain', 'skeleton', 'host-skeleton']
 
 
 # This function removes the dependency on some 'mandatory' package, like the
-- 
2.14.1

[Buildroot] [PATCH 07/11] support/graph-depends: also cut on host-tar

[Yann E. MORIN]

When host-tar is needed, it is a mandatory dependency of all packages.
As such, drawing the dependency lines toward host-tar would uselessly
clutter the graph.

So, like for the skeleton and host-skeleton, we cut the dependency chains
toward host-tar.

Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
---
 support/scripts/graph-depends | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index c3e5d83ee8..3143c61cc4 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -172,7 +172,7 @@ def remove_transitive_deps(pkg, deps):
 
 # List of dependencies that all/many packages have, and that we want
 # to trim when generating the dependency graph.
-MANDATORY_DEPS = ['toolchain', 'skeleton', 'host-skeleton']
+MANDATORY_DEPS = ['toolchain', 'skeleton', 'host-skeleton', 'host-tar']
 
 
 # This function removes the dependency on some 'mandatory' package, like the
-- 
2.14.1

[Buildroot] [PATCH 08/11] support/graph-depends: also cut on host-gzip

[Yann E. MORIN]

When host-gzip is needed, it is a mandatory dependency of all packages.
As such, drawing the dependency lines toward host-gzip would uselessly
clutter the graph.

So, like for the skeleton, host-skeleton, and host-tar, we cut the
dependency chains toward host-gzip.

Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
---
 support/scripts/graph-depends | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index 3143c61cc4..29134c8237 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -172,7 +172,7 @@ def remove_transitive_deps(pkg, deps):
 
 # List of dependencies that all/many packages have, and that we want
 # to trim when generating the dependency graph.
-MANDATORY_DEPS = ['toolchain', 'skeleton', 'host-skeleton', 'host-tar']
+MANDATORY_DEPS = ['toolchain', 'skeleton', 'host-skeleton', 'host-tar', 'host-gzip']
 
 
 # This function removes the dependency on some 'mandatory' package, like the
-- 
2.14.1

[Buildroot] [PATCH 09/11] infra/pkg-generic: use pure Makefile-based recursive dependencies

[Yann E. MORIN]

Calling to the graph-depends script is very costly, as it calls back to
'make' a lot of time.

It turns out that we already have the list of recursive dependencies, so
we can just print that.

As for the reverse dependencies, doing like the first-level reverse
dependencies would be extremely costly (with n enabled packages, in
O(n?)), so we instead add a new macro that recursively build that list
only when expanded.

From defconfig, C++, wchar, locales, ssp, and allyespackageconfig,
tweaked for even more packages (qt5 not qt4, luajit to avoid multi
providers, etc...), the timings for X-show-recursive-rdepends are:

                    before      after       speedup     #rdeps
    libnss          0m22.932s   0m5.796s     3.96x      3
    qt5base         0m41.176s   0m5.709s     7.21x      61
    libjpeg         0m56.185s   0m5.943s     9.45x      218
    libxml2         0m54.964s   0m5.772s     9.52x      261
    freetype        0m46.754s   0m6.140s     7.61x      271
    libpng          0m53.577s   0m6.366s     8.41x      292
    sqlite          1m15.222s   0m6.413s    11.73x      700
    readline        1m13.805s   0m7.618s     9.69x      862
    libopenssl      1m25.471s   0m6.585s    12.98x      869
    libzlib         1m11.807s   0m9.829s     7.30x      1000
    toolchain       1m23.712s   1m17.542s    1.08x      2050
    skeleton        1m27.839s   3m32.565s    0.41x      2053 (+1)
    host-skeleton   1m27.405s   14m12.237s   0.10x      2111 (+2)

  - speedup: ratio before/after
  - #rdeps: number of recursive reverse dependencies, with the extra
            dependencies returned with this patch, see below for the
            reason.

So, for a low-level package with a lot of reverse dependencies, like
libzlibz, libopenssl or readline are, the timings are already very much
in favour of the change. This is less impressive with packages that
have few dependencies (libnss), but still much faster.

However, the extreme cases that skeleton and host-skeleton are, are
horribly penalised by this change, with skeleton doubling in time, and
host-skeleton being almost ten times slower. These two can be considered
degenerate cases: even the toolchain virtual package, which is virtually
a dependency of everything, is still (marginally) faster.

These two degenerate skeletons cases are however really not the most
interesting cases, most of the time: the underlying use-case for
*-show-recursive-rdepends is to understand why a specific package comes
into the build, and most of the time, such a package is more like
libzlib or libopenssl or such, and thus with much less dependencies than
the degenerate skeleton cases.

Also, remember that the config tested has as much packages enabled as
possible, so is in itself a degenerate case. With simpler and more
realistic configurations, the gains would probably be a bit lower than
reported above, but various tests still report good improvements
overall. (note: coming up with a 'realistic' configuration is pretty
hard, as everyone have their notion of what is realtistic in their
context, so nothing displayed here; timings are left as an exercise for
the interested parties to report aggravation in their cases).

Note that, more recursive reverse dependencies may be displayed now,
since we do not apply the exceptions applied in graph-depends. For
example, host-skeleton gains two new recursive reverse dependencies:
skeleton and toolchain, which are both exceptions in graph-depends.

As for direct (not reverse) dependencies: the gain is not as fantastic
as for reverse ones, but it is still noticeable, just a few examples for
%-show-recursive-depends:

                    before      after       speedup     #deps
    libzlib         0m45.892s   0m5.845s     7.85x      1
    qt5base         0m54.684s   0m35.877s    1.52x      178
    sqlite          0m46.628s   0m5.799s     8.04x      23

(PS. Thanks to Joseph for suggesting a list of interesting packages
to test!))

Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
Cc: Thomas De Schampheleire <patrickdepinguin@gmail.com>
Cc: Joseph Kogut <joseph.kogut@gmail.com>

---
Note: in the following patches, we change the way graph-depends gets
the dependency tree, and that does also speeds it up. However, that
future speedup gets the recursive reverse dependencies only down to
about 25s which, although faster than the previous timings, is till a
tad slower than the new timings this patch brings. The only advantage
would be that the 25s are about constant, whatever the package, so the
degenerate cases above are normalised top 25s as well. Since they are
not that important, it is better to really speed up the vast majority of
packages.
---
 package/pkg-generic.mk |  6 ++----
 package/pkg-utils.mk   | 13 +++++++++++++
 2 files changed, 15 insertions(+), 4 deletions(-)

diff --git a/package/pkg-generic.mk b/package/pkg-generic.mk
index a27aa1f7fd..ae4bac509f 100644
--- a/package/pkg-generic.mk
+++ b/package/pkg-generic.mk
@@ -815,15 +815,13 @@ $(1)-show-depends:
 			@echo $$($(2)_FINAL_ALL_DEPENDENCIES)
 
 $(1)-show-recursive-depends:
-			@cd "$$(CONFIG_DIR)" && \
-			$$(TOPDIR)/support/scripts/graph-depends -p $(1) -f -q
+			@echo $$($(2)_FINAL_RECURSIVE_DEPENDENCIES)
 
 $(1)-show-rdepends:
 			@echo $$($(2)_RDEPENDENCIES)
 
 $(1)-show-recursive-rdepends:
-			@cd "$$(CONFIG_DIR)" && \
-			$$(TOPDIR)/support/scripts/graph-depends -p $(1) --reverse -f -q
+			@echo $$(call pkg-recursive-rdependencies,$(1))
 
 $(1)-show-build-order: $$(patsubst %,%-show-build-order,$$($(2)_FINAL_ALL_DEPENDENCIES))
 	@:
diff --git a/package/pkg-utils.mk b/package/pkg-utils.mk
index bffd79dfb0..fb96d3e62e 100644
--- a/package/pkg-utils.mk
+++ b/package/pkg-utils.mk
@@ -53,6 +53,19 @@ suitable-extractor = $(INFLATE$(suffix $(1)))
 extractor-dependency = $(firstword $(INFLATE$(filter-out \
 	$(EXTRACTOR_DEPENDENCY_PRECHECKED_EXTENSIONS),$(suffix $(1)))))
 
+# Return all the reverse dependencies of a package list
+# $(1): the space-separated list of packages (zero, one or more)
+define pkg-recursive-rdependencies
+	$(sort \
+		$(foreach p,$(sort $(1)), \
+			$(sort \
+				$($(call UPPERCASE,$(p))_RDEPENDENCIES) \
+				$(call pkg-recursive-rdependencies,$($(call UPPERCASE,$(p))_RDEPENDENCIES),$(2) .) \
+			) \
+		) \
+	)
+endef
+
 # check-deprecated-variable -- throw an error on deprecated variables
 # example:
 #   $(eval $(call check-deprecated-variable,FOO_MAKE_OPT,FOO_MAKE_OPTS))
-- 
2.14.1

[Buildroot] [PATCH 10/11] core: add make-based full-dependency list

[Yann E. MORIN]

Currently, when we need to build the full dependency graph, we call make
to show the list of packages (make show-targets), and then call it again
and again iteratively while it returns new packages.

Since calling make will parse the whole set of our Makefiles, this takes
quite a bit of time (~4s each here), and the total can get pretty long.

However, make being make, already builds the whole dependency tree
information, so we can just ask for it.

Add a new top-level rule 'show-dependency-tree' that displays the whole
set of dependencies for all packages. For each package, its name, type
and version is displayed, then all the direct, first-level dependencies
are dumped. We choose a format that is not unlike the dot-graph format,
because it is both easy to read as a human, and easy to parse as a
machine:

    foo: target 1.2.3
    foo -> bar host-meh
    bar: target virtual
    bar -> buz
    buz: target 2.3.4
    buz ->
    host-meh: host virtual
    host-meh -> host-bleark
    host-bleark: host 3.4.5
    host-bleark ->
    rootfs-meh: host
    rootfs-meh -> host-bleark

To be noted: rootfs are currently reported as if they were 'host'
packages, to stay aligned with how graph-depends currently treats them.
Ideally, graph-depends could be enhanced to recognise them separately,
but that is another story.

For just plain defconfig, which is about the smallest config we can have
with an internal toolchain, we already have a seven-fold improvement
(with the graph-depends rule modified to not run the pdf generation, to
be able to just compare the tree generation):

    $ time make graph-depends
    real    0m27.344s
    $ time make show-dependency-tree
    real    0m3.848s

From defconfig, C++, wchar, locales, ssp, and allyespackageconfig,
tweaked for even more packages (qt5 not qt4, luajit to avoid multi
providers, etc...), the timings are (graph-depends still modified to
not generate the pdf):

    $ time make graph-depends
    real    1m56.459s
    $ time make show-dependency-tree
    real    0m5.748s

There. I don't think those numbers need any explanation whatsoever;
they do speak on their own. OK, for maths sake, the ratio is about
twenty-fold. So, "yeah", I guess... ;-)

Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
Cc: Thomas De Schampheleire <patrickdepinguin@gmail.com>
---
 Makefile               | 4 ++++
 fs/common.mk           | 8 ++++++++
 package/pkg-generic.mk | 4 ++++
 3 files changed, 16 insertions(+)

diff --git a/Makefile b/Makefile
index 37df98520e..7a50c19de9 100644
--- a/Makefile
+++ b/Makefile
@@ -846,6 +846,10 @@ graph-depends-requirements:
 	@dot -? >/dev/null 2>&1 || \
 		{ echo "ERROR: The 'dot' program from Graphviz is needed for graph-depends" >&2; exit 1; }
 
+.PHONY: show-dependency-tree
+show-dependency-tree: $(patsubst %,%-show-dependency-tree,$(PACKAGES) $(TARGETS_ROOTFS))
+	@:
+
 .PHONY: graph-depends
 graph-depends: graph-depends-requirements
 	@$(INSTALL) -d $(GRAPHS_DIR)
diff --git a/fs/common.mk b/fs/common.mk
index 1625b65d0e..ba651fd4b7 100644
--- a/fs/common.mk
+++ b/fs/common.mk
@@ -45,6 +45,10 @@ ROOTFS_COMMON_DEPENDENCIES = \
 	$(BR2_TAR_HOST_DEPENDENCY) \
 	$(if $(PACKAGES_USERS)$(ROOTFS_USERS_TABLES),host-mkpasswd)
 
+rootfs-common-show-dependency-tree: $(patsubst %,%-show-dependency-tree,$(ROOTFS_COMMON_DEPENDENCIES))
+	$(info rootfs-common: host)
+	$(info rootfs-common -> $(foreach d,$(ROOTFS_COMMON_DEPENDENCIES),$(d)))
+
 .PHONY: rootfs-common
 rootfs-common: $(ROOTFS_COMMON_DEPENDENCIES) target-finalize
 	@$(call MESSAGE,"Generating root filesystems common tables")
@@ -77,6 +81,10 @@ ROOTFS_$(2)_TARGET_DIR = $$(ROOTFS_$(2)_DIR)/target
 
 ROOTFS_$(2)_DEPENDENCIES += rootfs-common
 
+rootfs-$(1)-show-dependency-tree: $$(patsubst %,%-show-dependency-tree,$$(ROOTFS_$(2)_DEPENDENCIES))
+	$$(info rootfs-$(1): host)
+	$$(info rootfs-$(1) -> $$(foreach d,$$(ROOTFS_$(2)_DEPENDENCIES),$$(d)))
+
 ifeq ($$(BR2_TARGET_ROOTFS_$(2)_GZIP),y)
 ROOTFS_$(2)_COMPRESS_EXT = .gz
 ROOTFS_$(2)_COMPRESS_CMD = gzip -9 -c
diff --git a/package/pkg-generic.mk b/package/pkg-generic.mk
index ae4bac509f..4b3100115d 100644
--- a/package/pkg-generic.mk
+++ b/package/pkg-generic.mk
@@ -827,6 +827,10 @@ $(1)-show-build-order: $$(patsubst %,%-show-build-order,$$($(2)_FINAL_ALL_DEPEND
 	@:
 	$$(info $(1))
 
+$(1)-show-dependency-tree: $$(patsubst %,%-show-dependency-tree,$$($(2)_FINAL_ALL_DEPENDENCIES))
+	$$(info $(1): $(4) $$(if $$($(2)_IS_VIRTUAL),virtual,$$($(2)_DL_VERSION)))
+	$$(info $(1) -> $$(foreach d,$$($(2)_FINAL_ALL_DEPENDENCIES),$$(d)))
+
 $(1)-graph-depends: graph-depends-requirements
 	$(call pkg-graph-depends,$(1),--direct)
 
-- 
2.14.1

[Buildroot] [PATCH 11/11] supprt/graph-depends: use the new make-based dependency tree

[Yann E. MORIN]

Now that we can get the whole dependency tree from make, use it to
speed up things considerably.

So far, we had three functions to get the dependencies information:
get_depends(), get_rdepends(), and, somehow unrelated, get_version().

Because of the way %-show-{,r}depends works, getting the dependency tree
was expensive, the three functions all took a set of packages for which
to get the dependencies, in an attempt to limit the time it took to get
that tree.

Now, getting the tree is much, much less costly, and we can get the
whole tree as cheaply as we previously got only the first-level
dependencies.

Furthemore, we can now also get the version information at the same
time, and that also brings in whether the package is virtual or not,
target or host.

So, we drop all three helper functions, and replace them with a single
one that returns all that information in one go: full dependency tree,
per-package type, and per-package version.

Note: since commit 2d29fd96a (pkg-virtual: remove VERSION/SOURCE),
virtual packages are no longer reported as having a 'virtual' version,
so have since been displayed as regular packages in the graphs. Although
noone complained, this patch incidentally restores the initial
behaviour, and virtual packages are now correctly displayed as such
again.

Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
Cc: Thomas De Schampheleire <patrickdepinguin@gmail.com>

---
Note: as I rewrote brpkgutil.py almost entirely now, and as I also
substantially modified graph-depends, I added my (C) to them. We don't
usually have copyright information in our files (no .mk or no Config.in
and such have that), so I think it would be OK to just drop the (C) in
there as well, especially since the Berne convention does not require it
for a work to be protected and recognised anyway:
    https://en.wikipedia.org/wiki/Copyright_symbol

Beside, the authorship information is already present in the git log,
and it is much more accurate in there than it is in the files
themselves.
---
 support/scripts/brpkgutil.py  | 106 ++++++++++++++++++--------------------
 support/scripts/graph-depends | 117 +++++-------------------------------------
 2 files changed, 64 insertions(+), 159 deletions(-)

diff --git a/support/scripts/brpkgutil.py b/support/scripts/brpkgutil.py
index e70d525353..39e9c5ce7e 100644
--- a/support/scripts/brpkgutil.py
+++ b/support/scripts/brpkgutil.py
@@ -1,67 +1,61 @@
 # Copyright (C) 2010-2013 Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
+# Copyright (C) 2018 Yann E. MORIN <yann.morin.1998@free.fr>
 
 import logging
 import sys
+import os
 import subprocess
 
 
-# Execute the "make <pkg>-show-version" command to get the version of a given
-# list of packages, and return the version formatted as a Python dictionary.
-def get_version(pkgs):
-    logging.info("Getting version for %s" % pkgs)
-    cmd = ["make", "-s", "--no-print-directory"]
-    for pkg in pkgs:
-        cmd.append("%s-show-version" % pkg)
-    p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
-    output = p.communicate()[0]
-    if p.returncode != 0:
-        logging.error("Error getting version %s" % pkgs)
-        sys.exit(1)
-    output = output.split("\n")
-    if len(output) != len(pkgs) + 1:
-        logging.error("Error getting version")
-        sys.exit(1)
-    version = {}
-    for i in range(0, len(pkgs)):
-        pkg = pkgs[i]
-        version[pkg] = output[i]
-    return version
+# This function returns a tuple of three dictionaries, all using package
+# names as keys:
+# - a dictionary which values are the lists of packages that are the
+#   dependencies of the package used as key;
+# - a dictionary which values are the type of the package used as key;
+# - a dictionary which values are the version of the package used as key,
+#   'virtual' for a virtual package, or the empty string for a rootfs.
+#
+# 'direction' can be either 'direct' or 'forward' to get the direct (aka
+# forward) dependencies, or 'back' or 'reverse' to get the reverse (aka
+# backward) dependencies.
+def get_dependency_tree(direction="direct"):
+    logging.info("Getting dependency tree...")
 
-
-def _get_depends(pkgs, rule):
-    logging.info("Getting dependencies for %s" % pkgs)
-    cmd = ["make", "-s", "--no-print-directory"]
-    for pkg in pkgs:
-        cmd.append("%s-%s" % (pkg, rule))
-    p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
-    output = p.communicate()[0]
-    if p.returncode != 0:
-        logging.error("Error getting dependencies %s\n" % pkgs)
-        sys.exit(1)
-    output = output.split("\n")
-    if len(output) != len(pkgs) + 1:
-        logging.error("Error getting dependencies")
-        sys.exit(1)
     deps = {}
-    for i in range(0, len(pkgs)):
-        pkg = pkgs[i]
-        pkg_deps = output[i].split(" ")
-        if pkg_deps == ['']:
-            deps[pkg] = []
+    types = {}
+    versions = {}
+
+    # Special case for the 'all' top-level fake package
+    deps['all'] = []
+    types['all'] = 'target'
+    versions['all'] = ''
+
+    cmd = ["make", "-s", "--no-print-directory", "show-dependency-tree"]
+    with open(os.devnull, 'wb') as devnull:
+        p = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=devnull, universal_newlines=True)
+        output = p.communicate()[0]
+
+    for l in output.splitlines():
+        if " -> " in l:
+            pkg = l.split(" -> ")[0]
+            if direction == "forward" or direction == "direct":
+                try:
+                    deps[pkg] += l.split(" -> ")[1].split()
+                except KeyError:
+                    deps[pkg] = l.split(" -> ")[1].split()
+            elif direction == "back" or direction == "reverse":
+                for p in l.split(" -> ")[1].split():
+                    try:
+                        deps[p].append(pkg)
+                    except KeyError:
+                        deps[p] = [pkg]
+            else:
+                raise ValueError('direction must be one of: direct, forward, reverse, back')
         else:
-            deps[pkg] = pkg_deps
-    return deps
+            pkg, type_version = l.split(": ", 1)
+            t, v = "{} -".format(type_version).split(None, 2)[:2]
+            deps['all'].append(pkg)
+            types[pkg] = t
+            versions[pkg] = v
 
-
-# Execute the "make <pkg>-show-depends" command to get the list of
-# dependencies of a given list of packages, and return the list of
-# dependencies formatted as a Python dictionary.
-def get_depends(pkgs):
-    return _get_depends(pkgs, 'show-depends')
-
-
-# Execute the "make <pkg>-show-rdepends" command to get the list of
-# reverse dependencies of a given list of packages, and return the
-# list of dependencies formatted as a Python dictionary.
-def get_rdepends(pkgs):
-    return _get_depends(pkgs, 'show-rdepends')
+    return (deps, types, versions)
diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
index 29134c8237..139a5dee80 100755
--- a/support/scripts/graph-depends
+++ b/support/scripts/graph-depends
@@ -20,10 +20,10 @@
 #    configuration.
 #
 # Copyright (C) 2010-2013 Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
+# Copyright (C) 2018 Yann E. MORIN <yann.morin.1998@free.fr>
 
 import logging
 import sys
-import subprocess
 import argparse
 from fnmatch import fnmatch
 
@@ -36,63 +36,6 @@ MODE_PKG = 2    # draw dependency graph for a given package
 allpkgs = []
 
 
-# Execute the "make show-targets" command to get the list of the main
-# Buildroot PACKAGES and return it formatted as a Python list. This
-# list is used as the starting point for full dependency graphs
-def get_targets():
-    logging.info("Getting targets")
-    cmd = ["make", "-s", "--no-print-directory", "show-targets"]
-    p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
-    output = p.communicate()[0].strip()
-    if p.returncode != 0:
-        return None
-    if output == '':
-        return []
-    return output.split(' ')
-
-
-# Recursive function that builds the tree of dependencies for a given
-# list of packages. The dependencies are built in a list called
-# 'dependencies', which contains tuples of the form (pkg1 ->
-# pkg2_on_which_pkg1_depends, pkg3 -> pkg4_on_which_pkg3_depends) and
-# the function finally returns this list.
-def get_all_depends(pkgs, get_depends_func):
-    dependencies = []
-
-    # Filter the packages for which we already have the dependencies
-    filtered_pkgs = []
-    for pkg in pkgs:
-        if pkg in allpkgs:
-            continue
-        filtered_pkgs.append(pkg)
-        allpkgs.append(pkg)
-
-    if len(filtered_pkgs) == 0:
-        return []
-
-    depends = get_depends_func(filtered_pkgs)
-
-    deps = set()
-    for pkg in filtered_pkgs:
-        pkg_deps = depends[pkg]
-
-        # This package has no dependency.
-        if pkg_deps == []:
-            continue
-
-        # Add dependencies to the list of dependencies
-        for dep in pkg_deps:
-            dependencies.append((pkg, dep))
-            deps.add(dep)
-
-    if len(deps) != 0:
-        newdeps = get_all_depends(deps, get_depends_func)
-        if newdeps is not None:
-            dependencies += newdeps
-
-    return dependencies
-
-
 # The Graphviz "dot" utility doesn't like dashes in node names. So for
 # node names, we strip all dashes. Also, nodes can't start with a number,
 # so we prepend an underscore.
@@ -230,7 +173,7 @@ def remove_extra_deps(deps, rootpkg, transitive):
 
 
 # Print the attributes of a node: label and fill-color
-def print_attrs(outfile, pkg, version, depth, colors):
+def print_attrs(outfile, pkg, pkg_type, pkg_version, depth, colors):
     name = pkg_node_name(pkg)
     if pkg == 'all':
         label = 'ALL'
@@ -239,13 +182,11 @@ def print_attrs(outfile, pkg, version, depth, colors):
     if depth == 0:
         color = colors[0]
     else:
-        if pkg.startswith('host') \
-                or pkg.startswith('toolchain') \
-                or pkg.startswith('rootfs'):
+        if pkg_type == "host":
             color = colors[2]
         else:
             color = colors[1]
-    if version == "virtual":
+    if pkg_version == "virtual":
         outfile.write("%s [label = <<I>%s</I>>]\n" % (name, label))
     else:
         outfile.write("%s [label = \"%s\"]\n" % (name, label))
@@ -256,13 +197,13 @@ done_deps = []
 
 
 # Print the dependency graph of a package
-def print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
+def print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list,
                    arrow_dir, draw_graph, depth, max_depth, pkg, colors):
     if pkg in done_deps:
         return
     done_deps.append(pkg)
     if draw_graph:
-        print_attrs(outfile, pkg, dict_version.get(pkg), depth, colors)
+        print_attrs(outfile, pkg, dict_types[pkg], dict_versions[pkg], depth, colors)
     elif depth != 0:
         outfile.write("%s " % pkg)
     if pkg not in dict_deps:
@@ -270,17 +211,15 @@ def print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
     for p in stop_list:
         if fnmatch(pkg, p):
             return
-    if dict_version.get(pkg) == "virtual" and "virtual" in stop_list:
+    if dict_versions[pkg] == "virtual" and "virtual" in stop_list:
         return
-    if pkg.startswith("host-") and "host" in stop_list:
+    if dict_types[pkg] == "host" and "host" in stop_list:
         return
     if max_depth == 0 or depth < max_depth:
         for d in dict_deps[pkg]:
-            if dict_version.get(d) == "virtual" \
-               and "virtual" in exclude_list:
+            if dict_versions[d] == "virtual" and "virtual" in exclude_list:
                 continue
-            if d.startswith("host-") \
-               and "host" in exclude_list:
+            if dict_types[d] == "host" and "host" in exclude_list:
                 continue
             add = True
             for p in exclude_list:
@@ -290,7 +229,7 @@ def print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
             if add:
                 if draw_graph:
                     outfile.write("%s -> %s [dir=%s]\n" % (pkg_node_name(pkg), pkg_node_name(d), arrow_dir))
-                print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
+                print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list,
                                arrow_dir, draw_graph, depth + 1, max_depth, d, colors)
 
 
@@ -352,6 +291,7 @@ def main():
 
     if args.package is None:
         mode = MODE_FULL
+        rootpkg = 'all'
     else:
         mode = MODE_PKG
         rootpkg = args.package
@@ -370,13 +310,11 @@ def main():
         exclude_list += MANDATORY_DEPS
 
     if args.direct:
-        get_depends_func = brpkgutil.get_depends
         arrow_dir = "forward"
     else:
         if mode == MODE_FULL:
             logging.error("--reverse needs a package")
             sys.exit(1)
-        get_depends_func = brpkgutil.get_rdepends
         arrow_dir = "back"
 
     draw_graph = not args.flat_list
@@ -389,46 +327,19 @@ def main():
         logging.error("Error: incorrect color list '%s'" % args.colors)
         sys.exit(1)
 
-    # In full mode, start with the result of get_targets() to get the main
-    # targets and then use get_all_depends() for all targets
-    if mode == MODE_FULL:
-        targets = get_targets()
-        dependencies = []
-        allpkgs.append('all')
-        filtered_targets = []
-        for tg in targets:
-            dependencies.append(('all', tg))
-            filtered_targets.append(tg)
-        deps = get_all_depends(filtered_targets, get_depends_func)
-        if deps is not None:
-            dependencies += deps
-        rootpkg = 'all'
-
-    # In pkg mode, start directly with get_all_depends() on the requested
-    # package
-    elif mode == MODE_PKG:
-        dependencies = get_all_depends([rootpkg], get_depends_func)
-
-    # Make the dependencies a dictionnary { 'pkg':[dep1, dep2, ...] }
-    dict_deps = {}
-    for dep in dependencies:
-        if dep[0] not in dict_deps:
-            dict_deps[dep[0]] = []
-        dict_deps[dep[0]].append(dep[1])
+    dict_deps, dict_types, dict_versions = brpkgutil.get_dependency_tree(arrow_dir)
 
     check_circular_deps(dict_deps)
     if check_only:
         sys.exit(0)
 
     dict_deps = remove_extra_deps(dict_deps, rootpkg, args.transitive)
-    dict_version = brpkgutil.get_version([pkg for pkg in allpkgs
-                                          if pkg != "all" and not pkg.startswith("root")])
 
     # Start printing the graph data
     if draw_graph:
         outfile.write("digraph G {\n")
 
-    print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
+    print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list,
                    arrow_dir, draw_graph, 0, args.depth, rootpkg, colors)
 
     if draw_graph:
-- 
2.14.1

[Buildroot] [PATCH 11/11] supprt/graph-depends: use the new make-based dependency tree

[Matthew Weber]

All,

On Sun, Dec 2, 2018 at 3:05 AM Yann E. MORIN <yann.morin.1998@free.fr> wrote:
>
> Now that we can get the whole dependency tree from make, use it to
> speed up things considerably.
>
> So far, we had three functions to get the dependencies information:
> get_depends(), get_rdepends(), and, somehow unrelated, get_version().
>
> Because of the way %-show-{,r}depends works, getting the dependency tree
> was expensive, the three functions all took a set of packages for which
> to get the dependencies, in an attempt to limit the time it took to get
> that tree.
>
> Now, getting the tree is much, much less costly, and we can get the
> whole tree as cheaply as we previously got only the first-level
> dependencies.
>
> Furthemore, we can now also get the version information at the same
> time, and that also brings in whether the package is virtual or not,
> target or host.
>
> So, we drop all three helper functions, and replace them with a single
> one that returns all that information in one go: full dependency tree,
> per-package type, and per-package version.
>
> Note: since commit 2d29fd96a (pkg-virtual: remove VERSION/SOURCE),
> virtual packages are no longer reported as having a 'virtual' version,
> so have since been displayed as regular packages in the graphs. Although
> noone complained, this patch incidentally restores the initial
> behaviour, and virtual packages are now correctly displayed as such
> again.
>
> Signed-off-by: "Yann E. MORIN" <yann.morin.1998@free.fr>
> Cc: Thomas Petazzoni <thomas.petazzoni@bootlin.com>
> Cc: Thomas De Schampheleire <patrickdepinguin@gmail.com>

Wow that is quite a bit faster.  Very cool

Tested-by: Matthew Weber <matthew.weber@rockwellcollins.com>

>
> ---
> Note: as I rewrote brpkgutil.py almost entirely now, and as I also
> substantially modified graph-depends, I added my (C) to them. We don't
> usually have copyright information in our files (no .mk or no Config.in
> and such have that), so I think it would be OK to just drop the (C) in
> there as well, especially since the Berne convention does not require it
> for a work to be protected and recognised anyway:
>     https://en.wikipedia.org/wiki/Copyright_symbol
>
> Beside, the authorship information is already present in the git log,
> and it is much more accurate in there than it is in the files
> themselves.
> ---
>  support/scripts/brpkgutil.py  | 106 ++++++++++++++++++--------------------
>  support/scripts/graph-depends | 117 +++++-------------------------------------
>  2 files changed, 64 insertions(+), 159 deletions(-)
>
> diff --git a/support/scripts/brpkgutil.py b/support/scripts/brpkgutil.py
> index e70d525353..39e9c5ce7e 100644
> --- a/support/scripts/brpkgutil.py
> +++ b/support/scripts/brpkgutil.py
> @@ -1,67 +1,61 @@
>  # Copyright (C) 2010-2013 Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
> +# Copyright (C) 2018 Yann E. MORIN <yann.morin.1998@free.fr>
>
>  import logging
>  import sys
> +import os
>  import subprocess
>
>
> -# Execute the "make <pkg>-show-version" command to get the version of a given
> -# list of packages, and return the version formatted as a Python dictionary.
> -def get_version(pkgs):
> -    logging.info("Getting version for %s" % pkgs)
> -    cmd = ["make", "-s", "--no-print-directory"]
> -    for pkg in pkgs:
> -        cmd.append("%s-show-version" % pkg)
> -    p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
> -    output = p.communicate()[0]
> -    if p.returncode != 0:
> -        logging.error("Error getting version %s" % pkgs)
> -        sys.exit(1)
> -    output = output.split("\n")
> -    if len(output) != len(pkgs) + 1:
> -        logging.error("Error getting version")
> -        sys.exit(1)
> -    version = {}
> -    for i in range(0, len(pkgs)):
> -        pkg = pkgs[i]
> -        version[pkg] = output[i]
> -    return version
> +# This function returns a tuple of three dictionaries, all using package
> +# names as keys:
> +# - a dictionary which values are the lists of packages that are the
> +#   dependencies of the package used as key;
> +# - a dictionary which values are the type of the package used as key;
> +# - a dictionary which values are the version of the package used as key,
> +#   'virtual' for a virtual package, or the empty string for a rootfs.
> +#
> +# 'direction' can be either 'direct' or 'forward' to get the direct (aka
> +# forward) dependencies, or 'back' or 'reverse' to get the reverse (aka
> +# backward) dependencies.
> +def get_dependency_tree(direction="direct"):
> +    logging.info("Getting dependency tree...")
>
> -
> -def _get_depends(pkgs, rule):
> -    logging.info("Getting dependencies for %s" % pkgs)
> -    cmd = ["make", "-s", "--no-print-directory"]
> -    for pkg in pkgs:
> -        cmd.append("%s-%s" % (pkg, rule))
> -    p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
> -    output = p.communicate()[0]
> -    if p.returncode != 0:
> -        logging.error("Error getting dependencies %s\n" % pkgs)
> -        sys.exit(1)
> -    output = output.split("\n")
> -    if len(output) != len(pkgs) + 1:
> -        logging.error("Error getting dependencies")
> -        sys.exit(1)
>      deps = {}
> -    for i in range(0, len(pkgs)):
> -        pkg = pkgs[i]
> -        pkg_deps = output[i].split(" ")
> -        if pkg_deps == ['']:
> -            deps[pkg] = []
> +    types = {}
> +    versions = {}
> +
> +    # Special case for the 'all' top-level fake package
> +    deps['all'] = []
> +    types['all'] = 'target'
> +    versions['all'] = ''
> +
> +    cmd = ["make", "-s", "--no-print-directory", "show-dependency-tree"]
> +    with open(os.devnull, 'wb') as devnull:
> +        p = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=devnull, universal_newlines=True)
> +        output = p.communicate()[0]
> +
> +    for l in output.splitlines():
> +        if " -> " in l:
> +            pkg = l.split(" -> ")[0]
> +            if direction == "forward" or direction == "direct":
> +                try:
> +                    deps[pkg] += l.split(" -> ")[1].split()
> +                except KeyError:
> +                    deps[pkg] = l.split(" -> ")[1].split()
> +            elif direction == "back" or direction == "reverse":
> +                for p in l.split(" -> ")[1].split():
> +                    try:
> +                        deps[p].append(pkg)
> +                    except KeyError:
> +                        deps[p] = [pkg]
> +            else:
> +                raise ValueError('direction must be one of: direct, forward, reverse, back')
>          else:
> -            deps[pkg] = pkg_deps
> -    return deps
> +            pkg, type_version = l.split(": ", 1)
> +            t, v = "{} -".format(type_version).split(None, 2)[:2]
> +            deps['all'].append(pkg)
> +            types[pkg] = t
> +            versions[pkg] = v
>
> -
> -# Execute the "make <pkg>-show-depends" command to get the list of
> -# dependencies of a given list of packages, and return the list of
> -# dependencies formatted as a Python dictionary.
> -def get_depends(pkgs):
> -    return _get_depends(pkgs, 'show-depends')
> -
> -
> -# Execute the "make <pkg>-show-rdepends" command to get the list of
> -# reverse dependencies of a given list of packages, and return the
> -# list of dependencies formatted as a Python dictionary.
> -def get_rdepends(pkgs):
> -    return _get_depends(pkgs, 'show-rdepends')
> +    return (deps, types, versions)
> diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends
> index 29134c8237..139a5dee80 100755
> --- a/support/scripts/graph-depends
> +++ b/support/scripts/graph-depends
> @@ -20,10 +20,10 @@
>  #    configuration.
>  #
>  # Copyright (C) 2010-2013 Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
> +# Copyright (C) 2018 Yann E. MORIN <yann.morin.1998@free.fr>
>
>  import logging
>  import sys
> -import subprocess
>  import argparse
>  from fnmatch import fnmatch
>
> @@ -36,63 +36,6 @@ MODE_PKG = 2    # draw dependency graph for a given package
>  allpkgs = []
>
>
> -# Execute the "make show-targets" command to get the list of the main
> -# Buildroot PACKAGES and return it formatted as a Python list. This
> -# list is used as the starting point for full dependency graphs
> -def get_targets():
> -    logging.info("Getting targets")
> -    cmd = ["make", "-s", "--no-print-directory", "show-targets"]
> -    p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
> -    output = p.communicate()[0].strip()
> -    if p.returncode != 0:
> -        return None
> -    if output == '':
> -        return []
> -    return output.split(' ')
> -
> -
> -# Recursive function that builds the tree of dependencies for a given
> -# list of packages. The dependencies are built in a list called
> -# 'dependencies', which contains tuples of the form (pkg1 ->
> -# pkg2_on_which_pkg1_depends, pkg3 -> pkg4_on_which_pkg3_depends) and
> -# the function finally returns this list.
> -def get_all_depends(pkgs, get_depends_func):
> -    dependencies = []
> -
> -    # Filter the packages for which we already have the dependencies
> -    filtered_pkgs = []
> -    for pkg in pkgs:
> -        if pkg in allpkgs:
> -            continue
> -        filtered_pkgs.append(pkg)
> -        allpkgs.append(pkg)
> -
> -    if len(filtered_pkgs) == 0:
> -        return []
> -
> -    depends = get_depends_func(filtered_pkgs)
> -
> -    deps = set()
> -    for pkg in filtered_pkgs:
> -        pkg_deps = depends[pkg]
> -
> -        # This package has no dependency.
> -        if pkg_deps == []:
> -            continue
> -
> -        # Add dependencies to the list of dependencies
> -        for dep in pkg_deps:
> -            dependencies.append((pkg, dep))
> -            deps.add(dep)
> -
> -    if len(deps) != 0:
> -        newdeps = get_all_depends(deps, get_depends_func)
> -        if newdeps is not None:
> -            dependencies += newdeps
> -
> -    return dependencies
> -
> -
>  # The Graphviz "dot" utility doesn't like dashes in node names. So for
>  # node names, we strip all dashes. Also, nodes can't start with a number,
>  # so we prepend an underscore.
> @@ -230,7 +173,7 @@ def remove_extra_deps(deps, rootpkg, transitive):
>
>
>  # Print the attributes of a node: label and fill-color
> -def print_attrs(outfile, pkg, version, depth, colors):
> +def print_attrs(outfile, pkg, pkg_type, pkg_version, depth, colors):
>      name = pkg_node_name(pkg)
>      if pkg == 'all':
>          label = 'ALL'
> @@ -239,13 +182,11 @@ def print_attrs(outfile, pkg, version, depth, colors):
>      if depth == 0:
>          color = colors[0]
>      else:
> -        if pkg.startswith('host') \
> -                or pkg.startswith('toolchain') \
> -                or pkg.startswith('rootfs'):
> +        if pkg_type == "host":
>              color = colors[2]
>          else:
>              color = colors[1]
> -    if version == "virtual":
> +    if pkg_version == "virtual":
>          outfile.write("%s [label = <<I>%s</I>>]\n" % (name, label))
>      else:
>          outfile.write("%s [label = \"%s\"]\n" % (name, label))
> @@ -256,13 +197,13 @@ done_deps = []
>
>
>  # Print the dependency graph of a package
> -def print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
> +def print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list,
>                     arrow_dir, draw_graph, depth, max_depth, pkg, colors):
>      if pkg in done_deps:
>          return
>      done_deps.append(pkg)
>      if draw_graph:
> -        print_attrs(outfile, pkg, dict_version.get(pkg), depth, colors)
> +        print_attrs(outfile, pkg, dict_types[pkg], dict_versions[pkg], depth, colors)
>      elif depth != 0:
>          outfile.write("%s " % pkg)
>      if pkg not in dict_deps:
> @@ -270,17 +211,15 @@ def print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
>      for p in stop_list:
>          if fnmatch(pkg, p):
>              return
> -    if dict_version.get(pkg) == "virtual" and "virtual" in stop_list:
> +    if dict_versions[pkg] == "virtual" and "virtual" in stop_list:
>          return
> -    if pkg.startswith("host-") and "host" in stop_list:
> +    if dict_types[pkg] == "host" and "host" in stop_list:
>          return
>      if max_depth == 0 or depth < max_depth:
>          for d in dict_deps[pkg]:
> -            if dict_version.get(d) == "virtual" \
> -               and "virtual" in exclude_list:
> +            if dict_versions[d] == "virtual" and "virtual" in exclude_list:
>                  continue
> -            if d.startswith("host-") \
> -               and "host" in exclude_list:
> +            if dict_types[d] == "host" and "host" in exclude_list:
>                  continue
>              add = True
>              for p in exclude_list:
> @@ -290,7 +229,7 @@ def print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
>              if add:
>                  if draw_graph:
>                      outfile.write("%s -> %s [dir=%s]\n" % (pkg_node_name(pkg), pkg_node_name(d), arrow_dir))
> -                print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
> +                print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list,
>                                 arrow_dir, draw_graph, depth + 1, max_depth, d, colors)
>
>
> @@ -352,6 +291,7 @@ def main():
>
>      if args.package is None:
>          mode = MODE_FULL
> +        rootpkg = 'all'
>      else:
>          mode = MODE_PKG
>          rootpkg = args.package
> @@ -370,13 +310,11 @@ def main():
>          exclude_list += MANDATORY_DEPS
>
>      if args.direct:
> -        get_depends_func = brpkgutil.get_depends
>          arrow_dir = "forward"
>      else:
>          if mode == MODE_FULL:
>              logging.error("--reverse needs a package")
>              sys.exit(1)
> -        get_depends_func = brpkgutil.get_rdepends
>          arrow_dir = "back"
>
>      draw_graph = not args.flat_list
> @@ -389,46 +327,19 @@ def main():
>          logging.error("Error: incorrect color list '%s'" % args.colors)
>          sys.exit(1)
>
> -    # In full mode, start with the result of get_targets() to get the main
> -    # targets and then use get_all_depends() for all targets
> -    if mode == MODE_FULL:
> -        targets = get_targets()
> -        dependencies = []
> -        allpkgs.append('all')
> -        filtered_targets = []
> -        for tg in targets:
> -            dependencies.append(('all', tg))
> -            filtered_targets.append(tg)
> -        deps = get_all_depends(filtered_targets, get_depends_func)
> -        if deps is not None:
> -            dependencies += deps
> -        rootpkg = 'all'
> -
> -    # In pkg mode, start directly with get_all_depends() on the requested
> -    # package
> -    elif mode == MODE_PKG:
> -        dependencies = get_all_depends([rootpkg], get_depends_func)
> -
> -    # Make the dependencies a dictionnary { 'pkg':[dep1, dep2, ...] }
> -    dict_deps = {}
> -    for dep in dependencies:
> -        if dep[0] not in dict_deps:
> -            dict_deps[dep[0]] = []
> -        dict_deps[dep[0]].append(dep[1])
> +    dict_deps, dict_types, dict_versions = brpkgutil.get_dependency_tree(arrow_dir)
>
>      check_circular_deps(dict_deps)
>      if check_only:
>          sys.exit(0)
>
>      dict_deps = remove_extra_deps(dict_deps, rootpkg, args.transitive)
> -    dict_version = brpkgutil.get_version([pkg for pkg in allpkgs
> -                                          if pkg != "all" and not pkg.startswith("root")])
>
>      # Start printing the graph data
>      if draw_graph:
>          outfile.write("digraph G {\n")
>
> -    print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
> +    print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list,
>                     arrow_dir, draw_graph, 0, args.depth, rootpkg, colors)
>
>      if draw_graph:
> --
> 2.14.1
>
> _______________________________________________
> buildroot mailing list
> buildroot at busybox.net
> http://lists.busybox.net/mailman/listinfo/buildroot



-- 

Matthew Weber | Pr. Software Engineer | Commercial Avionics

COLLINS AEROSPACE

400 Collins Road NE, Cedar Rapids, Iowa 52498, USA

Tel: +1 319 295 7349 | FAX: +1 319 263 6099

matthew.weber at collins.com | collinsaerospace.com



CONFIDENTIALITY WARNING: This message may contain proprietary and/or
privileged information of Collins Aerospace and its affiliated
companies. If you are not the intended recipient, please 1) Do not
disclose, copy, distribute or use this message or its contents. 2)
Advise the sender by return email. 3) Delete all copies (including all
attachments) from your computer. Your cooperation is greatly
appreciated.