Detect and fix circular dependencies (branch yem/fixes)

Hello All!

We currently have two circular dependencies:

    cups -> avahi -> libglade -> libgtk2 -> cups
    cups -> avahi -> libgtk3 -> cups

This series fixes those two loops (by cutting the avahi -> libgtk{2,3} dependency).

It also adds support for detecting future such circular dependencies, and makes the graph-depends script robust in such a situation.

Changes v2 -> v3:
- break the loop on avahi -> libgtk{2,3} (Thomas)
- consistency in variables and options (Thomas)

Changes v1 -> v2:
- optimise the loop detection (Thomas, Arnout)
- add timings for the new check (Thomas)
- actually fix the two loops
- enhance graph-depends to only check dependencies

Regards,
Yann E. MORIN.

The following changes since commit b5ad2ce5a35a7909307de806b9606c560b5cb85d:

fio: depends on BR2_TOOLCHAIN_HAS_SYNC_4 (2016-02-07 22:23:52 +0100)

are available in the git repository at:

git://git.busybox.net/~ymorin/git/buildroot yem/fixes

for you to fetch changes up to f0509ca9d1287b071a0cb1d965ead2bccdac5bc1:

core: add a make target to check the dependencies (2016-02-07 22:31:30 +0100)

----------------------------------------------------------------
Yann E. MORIN (6):
package/avahi: break circular dependencies support/graph-depends: add option to specify output file
core: catch failures in graph-depends support/graph-depends: detect circular dependencies support/graph-depends: teach it to only check dependencies
core: add a make target to check the dependencies

 Makefile                      | 10 ++++++--
 package/avahi/avahi.mk        | 15 ++----------
 package/pkg-generic.mk        |  8 ++++---
 support/scripts/graph-depends | 56 ++++++++++++++++++++++++++++++++++++++-----
 4 files changed, 65 insertions(+), 24 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.  |
'------------------------------^-------^------------------^--------------------'

We currently have two circular dependency chains:

    avahi -> libglade -> libgtk2 -> cups -> avahi
    avahi -> libgtk3 -> cups -> avahi

The cups -> avahi dependency makes sense, as cups would be able to use Bonjour and mDNS to find printers, so we want to keep that dependency.

The libgtk2 -> cups and libgtk3 -> cups dependencies also make sense, to be able to offer cups in the print dialogs.

However, the avahi -> libglade and avahi -> libgtk3 dependencies do not really make sense. As Thomas puts it:

The avahi GUI programs seem really useless to me. On Debian/Ubuntu distributions, they are not even packaged within the main avahi packages, but as separate packages, probably indicating that they are not very commonly used.

So, we drop the avahi -> libglade and avahi -> libgtk3 dependencies, to break the circular dependency chain.

---
Changes v2 -> v3:
- break the loop at the avahi -> libgtk{2,3} deps (Thomas)

---
 package/avahi/avahi.mk | 15 ++-------------
 1 file changed, 2 insertions(+), 13 deletions(-)

index 9c6b609..7229673 100644
@@ -71,6 +71,8 @@ AVAHI_CONF_ENV = \
 AVAHI_CONF_OPTS = \
 	--disable-qt3 \
 	--disable-qt4 \
+	--disable-gtk \
+	--disable-gtk3 \
 	--disable-gdbm \
 	--disable-pygtk \
 	--disable-mono \

@@ -126,19 +128,6 @@ else
 AVAHI_CONF_OPTS += --disable-glib --disable-gobject
 endif
 
-ifeq ($(BR2_PACKAGE_LIBGLADE),y)
-AVAHI_DEPENDENCIES += libglade
-else
-AVAHI_CONF_OPTS += --disable-gtk
-endif
-
-ifeq ($(BR2_PACKAGE_LIBGTK3),y)
-AVAHI_DEPENDENCIES += libgtk3
-AVAHI_CONF_OPTS += --enable-gtk3
-else
-AVAHI_CONF_OPTS += --disable-gtk3
-endif
-
 ifeq ($(BR2_PACKAGE_PYTHON),y)
 AVAHI_CONF_ENV += \
 	am_cv_pathless_PYTHON=python \

1.9.1

Currently, graph-depends outputs the dotfile program to stdout, and uses stderr to trace the dependencies it is currently looking for.

Redirection was done because the output was directly piped into the dot program to generate the final PDF/SVG/... dependency graph, but that meant that an error in the graph-depends script was never caught (because shell pipes only return the final command exit status, and an empty dot program is perfectly valid so dot would not complain).

Add an option to tell graph-depends where to store the generated dot program, and keep stdout as the default if not specified.

---
Changes v2 -> v3:
- rename variable to a consistent 'outfile' name (Thomas)
- don't change the Makefiles now (Thomas)

---
 support/scripts/graph-depends | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)

index fd8ad2f..74ba995 100755
@@ -38,6 +38,8 @@ max_depth = 0
 transitive = True
 
 parser = argparse.ArgumentParser(description="Graph packages dependencies")
+parser.add_argument("--outfile", "-o", metavar="DOT_FILE", dest="outfile",
+                    help="File in which to generate the dot representation")
 parser.add_argument("--package", '-p', metavar="PACKAGE",
                     help="Graph the dependencies of PACKAGE")
 parser.add_argument("--depth", '-d', metavar="DEPTH", dest="depth", type=int, default=0,

@@ -60,6 +62,11 @@ parser.add_argument("--no-transitive", dest="transitive", action='store_false',
                     help="Draw (do not draw) transitive dependencies")
 args = parser.parse_args()
 
+if args.outfile is None:
+    outfile = sys.stdout
+else:
+    outfile = open(args.outfile, "wb")
+
 if args.package is None:
     mode = MODE_FULL
 else:

@@ -339,10 +346,10 @@ def print_attrs(pkg):
             color = target_colour
     version = dict_version.get(pkg)
     if version == "virtual":
-        print("%s [label = <<I>%s</I>>]" % (name, label))
+        outfile.write("%s [label = <<I>%s</I>>]\n" % (name, label))
     else:
-        print("%s [label = \"%s\"]" % (name, label))
-    print("%s [color=%s,style=filled]" % (name, color))
+        outfile.write("%s [label = \"%s\"]\n" % (name, label))
+    outfile.write("%s [color=%s,style=filled]\n" % (name, color))
 
 # Print the dependency graph of a package
 def print_pkg_deps(depth, pkg):

@@ -369,13 +376,13 @@ def print_pkg_deps(depth, pkg):
                     add = False
                     break
             if add:
-                print("%s -> %s" % (pkg_node_name(pkg), pkg_node_name(d)))
+                outfile.write("%s -> %s\n" % (pkg_node_name(pkg), pkg_node_name(d)))
                 print_pkg_deps(depth+1, d)
 
 # Start printing the graph data
-print("digraph G {")
+outfile.write("digraph G {\n")
 
 done_deps = []
 print_pkg_deps(0, rootpkg)
 
-print("}")
+outfile.write("}\n")

1.9.1

Currently, we generate the dependency graph in a single command, piping the stdout of support/scripts/.graph-depends to the stdin of dot.

Unfortunately, this means we can't catch a failure of graph-depends, as the shell can only treturn the exit code of the last command in a pipe.

Still, we do want to keep the output of graph-depends, and we in fact do keep it by mean of a tee.

graph-depends has just gained the ability to generate its output to a file, so we break the pipe in two differnet commands, so we can bail out on graph-depends errors.

Do that for the two call sites.

---
Changes v2 -> v3;
- split out of the previous patch (Thomas)

---
 Makefile               | 6 ++++--
 package/pkg-generic.mk | 8 +++++---
 2 files changed, 9 insertions(+), 5 deletions(-)

index 68259fd..7c5daa4 100644
@@ -721,8 +721,10 @@ graph-depends: graph-depends-requirements
 	@$(INSTALL) -d $(GRAPHS_DIR)
 	@cd "$(CONFIG_DIR)"; \
 	$(TOPDIR)/support/scripts/graph-depends $(BR2_GRAPH_DEPS_OPTS) \
-	|tee $(GRAPHS_DIR)/$(@).dot \
-	|dot $(BR2_GRAPH_DOT_OPTS) -T$(BR_GRAPH_OUT) -o $(GRAPHS_DIR)/$(@).$(BR_GRAPH_OUT)
+		-o $(GRAPHS_DIR)/$(@).dot
+	dot $(BR2_GRAPH_DOT_OPTS) -T$(BR_GRAPH_OUT) \
+		-o $(GRAPHS_DIR)/$(@).$(BR_GRAPH_OUT) \
+		$(GRAPHS_DIR)/$(@).dot
 
 graph-size:
 	$(Q)mkdir -p $(GRAPHS_DIR)

index 1e024d3..e22babb 100644
@@ -668,9 +668,11 @@ $(1)-show-depends:
 $(1)-graph-depends: graph-depends-requirements
 			@$$(INSTALL) -d $$(GRAPHS_DIR)
 			@cd "$$(CONFIG_DIR)"; \
-			$$(TOPDIR)/support/scripts/graph-depends -p $(1) $$(BR2_GRAPH_DEPS_OPTS) \
-			|tee $$(GRAPHS_DIR)/$$(@).dot \
-			|dot $$(BR2_GRAPH_DOT_OPTS) -T$$(BR_GRAPH_OUT) -o $$(GRAPHS_DIR)/$$(@).$$(BR_GRAPH_OUT)
+			$$(TOPDIR)/support/scripts/graph-depends $$(BR2_GRAPH_DEPS_OPTS) \
+				-p $(1) -o $$(GRAPHS_DIR)/$$(@).dot
+			dot $$(BR2_GRAPH_DOT_OPTS) -T$$(BR_GRAPH_OUT) \
+				-o $$(GRAPHS_DIR)/$$(@).$$(BR_GRAPH_OUT) \
+				$$(GRAPHS_DIR)/$$(@).dot
 
 $(1)-all-source:	$(1)-source
 $(1)-all-source:	$$(foreach p,$$($(2)_FINAL_ALL_DEPENDENCIES),$$(p)-all-source)

1.9.1

Currently, if there is a circular dependency in the packages, the graph-depends script just errors out with a Python RuntimeError which is not caught, resulting in a very-long backtrace which does not provide any hint as what the real issue is (even if "RuntimeError: maximum recursion depth exceeded" is a pretty good hint at it).

We fix that by recursing the dependency chain of each package, until we either end up with a package with no dependency, or with a package already seen along the current dependency chain.

We need to introduce a new function, check_circular_deps(), because we can't re-use the existing ones:

- remove_mandatory_deps() does not iterate,

- remove_transitive_deps() does iterate, but we do not call it for the top-level package if it is not 'all'

- it does not make sense to use those functions anyway, as they were not designed to _check_ but to _act_ on the dependency chain.

Since we've had time-related issues in the past, we do not want to introduce yet another time-hog, so here are timings with the circular dependency check:

    $ time python -m cProfile -s cumtime support/scripts/graph-depends
    [...]
             28352654 function calls (20323050 primitive calls) in 87.292 seconds

       Ordered by: cumulative time

       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
            1    0.012    0.012   87.292   87.292 graph-depends:24(<module>)
           21    0.000    0.000   73.685    3.509 subprocess.py:473(_eintr_retry_call)
            7    0.000    0.000   73.655   10.522 subprocess.py:768(communicate)
            7   73.653   10.522   73.653   10.522 {method 'read' of 'file' objects}
          5/1    0.027    0.005   43.488   43.488 graph-depends:164(get_all_depends)
            5    0.003    0.001   43.458    8.692 graph-depends:135(get_depends)
            1    0.001    0.001   25.712   25.712 graph-depends:98(get_version)
            1    0.001    0.001   13.457   13.457 graph-depends:337(remove_extra_deps)
         1717    1.672    0.001   13.050    0.008 graph-depends:290(remove_transitive_deps)
    9784086/2672326    5.079    0.000   11.363    0.000 graph-depends:274(is_dep)
    2883343/1980154    2.650    0.000    6.942    0.000 graph-depends:262(is_dep_uncached)
            1    0.000    0.000    4.529    4.529 graph-depends:121(get_targets)
      2883343    1.123    0.000    1.851    0.000 graph-depends:246(is_dep_cache_insert)
      9784086    1.783    0.000    1.783    0.000 graph-depends:255(is_dep_cache_lookup)
      2881580    0.728    0.000    0.728    0.000 {method 'update' of 'dict' objects}
            1    0.001    0.001    0.405    0.405 graph-depends:311(check_circular_deps)
    12264/1717    0.290    0.000    0.404    0.000 graph-depends:312(recurse)
    [...]
    real    1m27.371s
    user    1m15.075s
    sys     0m12.673s

The cumulative time spent in check_circular_deps is just below 0.5s, which is largely less than 1% of the total run time.

---
Note: I'm not completely happy with the way the code detects the end of the dependency chain, but at least it works and is a starting point for further discussion. Python experts will happily point me in the right direction! ;-)

---
Chamges v1 -> v2:
- store packages known to not cause loops, to cut short on the visiting algorithm
- use the local variable 'deps', not the global 'dict_deps'
- add timing report

---
 support/scripts/graph-depends | 27 +++++++++++++++++++++++++++
 1 file changed, 27 insertions(+)

index 74ba995..ec32b20 100755
@@ -313,6 +313,32 @@ def remove_transitive_deps(pkg,deps):
 def remove_mandatory_deps(pkg,deps):
     return [p for p in deps[pkg] if p not in ['toolchain', 'skeleton']]
 
+# 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):
+    def recurse(pkg):
+        if not pkg in list(deps.keys()):
+            return
+        if pkg in not_loop:
+            return
+        not_loop.append(pkg)
+        chain.append(pkg)
+        for p in deps[pkg]:
+            if p in chain:
+                sys.stderr.write("\nRecursion detected for  : %s\n" % (p))
+                while True:
+                    _p = chain.pop()
+                    sys.stderr.write("which is a dependency of: %s\n" % (_p))
+                    if p == _p:
+                        sys.exit(1)
+            recurse(p)
+        chain.pop()
+
+    not_loop = []
+    chain = []
+    for pkg in list(deps.keys()):
+        recurse(pkg)
+
 # This functions trims down the dependency list of all packages.
 # It applies in sequence all the dependency-elimination methods.
 def remove_extra_deps(deps):

@@ -324,6 +350,7 @@ def remove_extra_deps(deps):
             deps[pkg] = remove_transitive_deps(pkg,deps)
     return deps
 
+check_circular_deps(dict_deps)
 dict_deps = remove_extra_deps(dict_deps)
 dict_version = get_version([pkg for pkg in allpkgs
                                 if pkg != "all" and not pkg.startswith("root")])

1.9.1

Add an option to graph-depends to only do the dependency checks and not generate the dot program.

---
 support/scripts/graph-depends | 10 ++++++++++
 1 file changed, 10 insertions(+)

index ec32b20..13ddc94 100755
@@ -38,6 +38,8 @@ max_depth = 0
 transitive = True
 
 parser = argparse.ArgumentParser(description="Graph packages dependencies")
+parser.add_argument("--check-only", "-C", dest="check_only", action="store_true", default=False,
+                    help="Only do the dependency checks (circular deps...)")
 parser.add_argument("--outfile", "-o", metavar="DOT_FILE", dest="outfile",
                     help="File in which to generate the dot representation")
 parser.add_argument("--package", '-p', metavar="PACKAGE",

@@ -62,9 +64,14 @@ parser.add_argument("--no-transitive", dest="transitive", action='store_false',
                     help="Draw (do not draw) transitive dependencies")
 args = parser.parse_args()
 
+check_only = args.check_only
+
 if args.outfile is None:
     outfile = sys.stdout
 else:
+    if check_only:
+        sys.stderr.write("don't specify outfile and check-only at the same time\n")
+        sys.exit(1)
     outfile = open(args.outfile, "wb")
 
 if args.package is None:

@@ -351,6 +358,9 @@ def remove_extra_deps(deps):
     return deps
 
 check_circular_deps(dict_deps)
+if check_only:
+    sys.exit(0)
+
 dict_deps = remove_extra_deps(dict_deps)
 dict_version = get_version([pkg for pkg in allpkgs
                                 if pkg != "all" and not pkg.startswith("root")])

1.9.1

Add a make target that will checks the dependencies of all packages. This will currently only detect circular dependencies, but more tests can be added later if need be.

This can then be used in the autobuilders to automatically report dependency issues.

---
 Makefile | 4 ++++
 1 file changed, 4 insertions(+)

index 7c5daa4..9daf011 100644
@@ -733,6 +733,10 @@ graph-size:
 		--file-size-csv $(GRAPHS_DIR)/file-size-stats.csv \
 		--package-size-csv $(GRAPHS_DIR)/package-size-stats.csv
 
+check-dependencies:
+	@cd "$(CONFIG_DIR)"; \
+	$(TOPDIR)/support/scripts/graph-depends -C
+
 else # ifeq ($(BR2_HAVE_DOT_CONFIG),y)
 
 all: menuconfig

1.9.1

Dear Yann E. MORIN,

Applied after adding a comment in avahi.mk to explain why we disabled gtk2/gtk3 support.

Applied after changing the metavar from DOT_FILE to OUT_FILE, in order to be consistent with the rest of the patch.

All applied. To be honest, I only quickly skimmed through the circular dependency checking function. It seemed reasonable, but I clearly didn't do a very thorough verification of it.

What about submitting an autobuild-run patch now to make use of this functionality? :-)

Thanks!

Thomas

Thomas Petazzoni, CTO, Free Electrons
Embedded Linux, Kernel and Android engineering
http://free-electrons.com