Detect and fix circular dependencies

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 libgtk{2,3} <- cups dependency).

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

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 530c5a55959f161f49dc095641a24ede649725be:

vboot-utils: fix RSA redefinition build error with old compilers (2016-01-23 13:09:29 +0100)

are available in the git repository at:

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

for you to fetch changes up to 00edb6450d0b45ee3c0ae850f7d3a72d5aad711f:

core: add a make target to check the dependencies (2016-01-24 16:42:28 +0100)

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

 Makefile                      | 10 ++++++--
 package/libgtk2/libgtk2.mk    | 10 +++-----
 package/libgtk3/libgtk3.mk    | 11 ++-------
 package/pkg-generic.mk        |  8 ++++---
 support/scripts/graph-depends | 56 ++++++++++++++++++++++++++++++++++++++-----
 5 files changed, 68 insertions(+), 27 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 a circular dependency chain:

    avahi -> libglade -> libgtk2 -> 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 avahi -> libglade -> libgtk2 chain also makes some sense, to provide a GUI frontend for avahi.

Since the libgtk2 -> cups does not look that it would be tremendously useful, that's the one we drop in this patch.

---
 package/libgtk2/libgtk2.mk | 10 +++-------
 1 file changed, 3 insertions(+), 7 deletions(-)

index 17cdfcb..d6ffaec 100644
@@ -28,7 +28,9 @@ LIBGTK2_CONF_OPTS += \
 	--with-x \
 	--x-includes=$(STAGING_DIR)/usr/include/X11 \
 	--x-libraries=$(STAGING_DIR)/usr/lib \
-	--with-gdktarget=x11
+	--with-gdktarget=x11 \
+	--disable-cups
+
 LIBGTK2_DEPENDENCIES += \
 	fontconfig xlib_libX11 xlib_libXext xlib_libXrender
 

@@ -84,12 +86,6 @@ else
 LIBGTK2_CONF_OPTS += --without-libtiff
 endif
 
-ifeq ($(BR2_PACKAGE_CUPS),y)
-LIBGTK2_DEPENDENCIES += cups
-else
-LIBGTK2_CONF_OPTS += --disable-cups
-endif
-
 ifeq ($(BR2_PACKAGE_LIBGTK2_DEMO),)
 define LIBGTK2_POST_INSTALL_TWEAKS
 	rm -rf $(TARGET_DIR)/usr/share/gtk-2.0/demo $(TARGET_DIR)/usr/bin/gtk-demo

1.9.1

Yann,

I tend to disagree with this analysis. 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. It is also highly unlikely that such ready-made applications will be used on embedded systems.

On the other hand, when you enable Gtk2 or Gtk3 to create your own graphical applications, you may be interested in being able to have the print dialogs support CUPS.

So in the:

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

I would rather tend to break the dependency between "avahi -> libglade" rather than between "libgtk2 -> cups".

(This comment obviously also applies to your patch 2/6).

What do you think ? What do others think ?

Thanks!

Thomas

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

Thomas, All,

On 2016-02-06 23:46 +0100, Thomas Petazzoni spake thusly:

I have absolutely no preference between the two. The only I'm tangentially interested in is the cups -> avahi dependency.

So I'm fine with your proposal as well.

Regards,
Yann E. MORIN.

.-----------------.--------------------.------------------.--------------------.
|  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.  |
'------------------------------^-------^------------------^--------------------'

Dear Yann E. MORIN,

There is indeed a subjective decision to be made here. But I believe it's better to loose some relatively useless GUI programs, rather than the some printing support in a GUI library.

Fully agreed that keeping this dependency is important, and the most important on of the chain.

Thanks!

Thomas

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

We currently have a circular dependency chain:

    cups -> avahi -> libgtk3 -> cups

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 avahi -> libgtk3 chain also makes some sense, to provide a GUI frontend for avahi.

Since the libgtk3 -> cups does not look that it would be tremendously useful, that's the one we drop in this patch.

---
 package/libgtk3/libgtk3.mk | 11 ++---------
 1 file changed, 2 insertions(+), 9 deletions(-)

index d268b56..26301be 100644
@@ -22,7 +22,8 @@ LIBGTK3_CONF_OPTS = \
 	--disable-glibtest \
 	--enable-explicit-deps=no \
 	--enable-gtk2-dependency \
-	--disable-introspection
+	--disable-introspection \
+	--disable-cups
 
 LIBGTK3_DEPENDENCIES = host-pkgconf host-libgtk3 atk libglib2 cairo pango gdk-pixbuf
 

@@ -96,14 +97,6 @@ else
 LIBGTK3_CONF_OPTS += --disable-xkb
 endif
 
-ifeq ($(BR2_PACKAGE_CUPS),y)
-LIBGTK3_CONF_OPTS += --enable-cups
-LIBGTK3_CONF_ENV += ac_cv_path_CUPS_CONFIG=$(STAGING_DIR)/usr/bin/cups-config
-LIBGTK3_DEPENDENCIES += cups
-else
-LIBGTK3_CONF_OPTS += --disable-cups
-endif
-
 ifeq ($(BR2_PACKAGE_LIBGTK3_DEMO),y)
 LIBGTK3_DEPENDENCIES += hicolor-icon-theme shared-mime-info
 else

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 fd8ad2f..78be2ba 100755
@@ -306,6 +306,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):

@@ -317,6 +343,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

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.

Change the calling sites to use that option, call graph-depends and dot as two separate commands, so we can bail out on graph-depends error.

---
 Makefile                      |  6 ++++--
 package/pkg-generic.mk        |  8 +++++---
 support/scripts/graph-depends | 19 +++++++++++++------
 3 files changed, 22 insertions(+), 11 deletions(-)

index 17c181b..20927de 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..e396a5d 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)

index 78be2ba..e872ed4 100755
@@ -38,6 +38,8 @@ max_depth = 0
 transitive = True
 
 parser = argparse.ArgumentParser(description="Graph packages dependencies")
+parser.add_argument("--output", "-o", metavar="DOT_FILE", dest="dotfile",
+                    help="File in which to generate the dot program")
 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.dotfile is None:
+    outfile = sys.stdout
+else:
+    outfile = open(args.dotfile, "wb")
+
 if args.package is None:
     mode = MODE_FULL
 else:

@@ -366,10 +373,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):

@@ -396,13 +403,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

Dear Yann E. MORIN,

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

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 e872ed4..21b2370 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",
+                    help="Only do the dependency checks (circular deps...)")
 parser.add_argument("--output", "-o", metavar="DOT_FILE", dest="dotfile",
                     help="File in which to generate the dot program")
 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.dotfile is None:
     outfile = sys.stdout
 else:
+    if check_only:
+        sys.stderr.write("don't specify output file and check-only at the same time\n")
+        sys.exit(1)
     outfile = open(args.dotfile, "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 20927de..0532f3b 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